Extracting a specific substring in C

Question

I have a string like this:

char buffer[] = "blablabla$GPTXT->SOME CODES HERE<-\r\n$GPRMCblablabla";

It is sent from an external device and changes every 1 second.

The string length is over 1000 bytes and consisted of some standard sentences beginning with "$GPXXX" and ending with CRLF. I've written the following function to extract a specific sentence:

int findString(char *src, char *dst, int desLen, char *what2find, char termChar)
{
    char *temp;
    temp = strstr(src, what2find); ;
    if (temp == NULL)
        return 0;
    else
        temp += strlen(what2find);
    int j = 0;
    while (j<(desLen-1))
    {
        if (temp[j]==termChar)
            break;
        dst[j]= temp[j];
        j++;
    }
    dst[j] = '\0';
    return 1;
}

So:

 int main()
 {
  char buffer[] =       
  "$GPGGA,123519,4807.038,N,01131.000,E,1,08,0.9,545.4,M,46.9,M,,*47\r\n
  $GPGSA,A,3,04,05,,09,12,,,24,,,,,2.5,1.3,2.1*39\r\n
  $GPGSV,2,1,08,01,40,083,46,02,17,308,41,12,07,344,39,14,22,228,45*75\r\n
  $GPRMC,123519,A,4807.038,N,01131.000,E,022.4,084.4,230394,003.1,W*6A\r\n
  $GPVTG,054.7,T,034.4,M,005.5,N,010.2,K*48\r\n";

  char dst[50];
  findString(buffer,dst,50,"$GPTXT",'$');
 }

finds and return the desired sentence.

But this code has the following problems:

1. It is very heuristic. I wonder if there exists some better solutions.
2. It depends on a character (i.e. '$') for termination. It may terminate after finding a '$' but not "$GPXXX". The optimal solution may find the characters between two strings, e.g. "$GPTXT" and "$GPRMC". I don't know if it is optimally achievable.

Note that the host processor is a 4Mhz ARM MCU!

P.S: The above-mentioned function works fine in my project. I just want to widen my C programming knowledge!

P.S. 2: Both answers from Lundin and David C. Rankin are nice. Unfortunately I can not accept both of them as answer!

Answer 1

As far as performance goes, there isn't much you can improve without doing manual optimization tricks. Such things are already implemented in the library functions though.

The main issue I see here is that you copy data into the destination before you know if the string actually contains a termination character. By doing so, you save a bit of time as you can copy and search at the same time. But you also end up copying data before the input has been verified.

What's best in your case, I don't know. It depends on how reliable your input is. If you have already verified it previously, then your copy+check in one might be the best choice. If it's some raw data from a serial bus (UART etc), it might be wisest to verify the data before you copy. I will show a version that does the verification first, it will be safer although possibly slightly slower than what you currently have.

---

General code review:

Style/best practices

• Pointer parameters to data that isn't modified should be const qualified.
• Using a plain int for error handling isn't ideal. You actually have several possible errors here: missing search string, missing terminator, potential buffer overflow. Even if your program doesn't need to know what went wrong, it might ease debugging and it costs you nothing extra to add.

• The while loop could have been replaced with a for loop, for better readability:

  for(size_t i=0; i<desLen-1; i++)
  {
    if(temp[i]==termChar)
    {
      break;
    }
    dst[i]=temp[i];
  }
  

Performance

• The length of the search key could be determined at compile-time.
• Consider dropping the terminating character parameter if what2find[0] could be said to always contain it.
• Some micro-optimizations with C99 restrict are possible. I'll show an example below.

---

Here is a different version which contains more detailed error handling and checks for termination before copy:

#include <string.h>
#include <stdbool.h>

typedef enum
{
  STRFIND_OK,
  STRFIND_KEY_NOT_FOUND,
  STRFIND_TERMINATOR_NOT_FOUND,
  STRFIND_BUFFER_OVERFLOW,
} strfind_result_t;

strfind_result_t strfind_cpy (const char* str, 
                              size_t      key_size,
                              const char  key[key_size], 
                              char        terminator,
                              size_t      dst_size, 
                              char        dst [dst_size])
{
  char* start = strstr(str, key);
  if(start == NULL)
  {
    return STRFIND_KEY_NOT_FOUND;
  }

  start += key_size-1;
  char* end = strchr(start, terminator);
  if(end == NULL)
  {
    return STRFIND_TERMINATOR_NOT_FOUND;
  }

  size_t length = (size_t)(end-start);
  if(length+1 > dst_size)
  {
    return STRFIND_BUFFER_OVERFLOW;
  }

  memcpy(dst, start, length);
  dst[length] = '\0';

  return STRFIND_OK;
}

C99 pointer-to-VLA are used to ensure data size integrity of the buffers. If the verification of data isn't needed, strchr could be replaced with a for loop like the one demonstrated above.

memcpy is the fastest possible copy. It will be faster than copy character-by-character, since the library implementation will work on 32 bit chunks that your ARM likes better than copying individual bytes. So my code might actually be faster (or it may be slower), you'll have to benchmark it.

Further micro-optimization is possible with C99 restrict:

strfind_result_t strfind_cpy (const char* restrict  str, 
                              size_t                key_size,
                              const char* restrict  key, 
                              char                  terminator,
                              size_t                dst_size, 
                              char* restrict        dst);

This tells the compiler that none of the pointers passed point at the same buffer. This may improve performance ever so slightly, depending on how your compiler handles pointer aliasing internally. Check the disassembled code to see if restrict gave any benefits.

---

Example of use:

#include <stdio.h>

int main (void)
{
  const char data[] = "blablabla$GPTXT->SOME CODES HERE<-\r\n$GPRMCblablabla";
  char buf[50];
  strfind_result_t result;

  result = strfind_cpy(data,
                       sizeof "$GPTXT",
                       "$GPTXT",
                       '$',
                       sizeof buf,
                       buf);

  if(result == STRFIND_OK)
  {
    puts(buf);
  }
}

Answer 2

While you have a good presentation of your question, it is still a bit unclear exactly what you are looking to extract between $GPTXT and '$' given that you have the "\r\n" prior to the terminating '$'. It seems unlikely that you would want to retain the carriage return/line feed as part of your returned substring. My best interpretation is that you want "->SOME CODES HERE<-" extracted from the string (drop a comment if this is incorrect).

If this is the case, you can use the \r\n to your advantage in tokenizing the string to return that part between $GPTXT and "\r\n$" by using "\r\n$" as the delimiters passed to strtok. The only additional task needed in your findstr function would be to step past your search string before calling strtok.

In looking at the declaration for findstring, I would tweak the parameters just a bit to make them consistent with most of the other string library functions. That being to reverse the source and dest parameters such that dest comes before src as in strcpy, etc... I'm not a fan of one way over the other, but I have found keeping functions at least as consistent as possible helps avoid inadvertent parameter swaps.

I would also change your termChar to a const char* parameter to allow flexibility in passing the delimiter to use with strtok.

An implementation might look like:

#include <stdio.h>
#include <string.h>

#define TERM   32
#define MAXC 1024
#define DELIM "\r\n$"

char *findstr (char *dest, const char *src, size_t len, const char *srch,
                const char *delim)
{
    char *p = strstr (src, srch);   /* locate beginning of search in src */
    size_t toklen = 0;              /* token length to calculate once */

    if (!p)                         /* validate or return NULL */
        return NULL;

    p += strlen (srch);             /* step past search str */

    /* tokenize p based on delim and validate length < len */
    if ((p = strtok (p, delim)) && (toklen = strlen(p)) < len)
        memcpy (dest, p, toklen+1); /* copy to dest w/nul-char */
    else
        return NULL;                /* or return NULL */

    return dest;
}

int main (void) {

    char buffer[] = "blablabla$GPTXT->SOME CODES HERE<-\r\n$GPRMCblablabla";
    char sub[MAXC] = "";

    if (findstr (sub, buffer, MAXC, "GPTXT", DELIM))
        printf ("sub: '%s'\n", sub);
}

(note: since you have already scanned to length of your token to validate it is less than len, there is no need to scan again by using strcpy to effect the token copy to dest, simply using memcpy will provide an ever-so-slightly more efficient copy)

Example Use/Output

While provides:

$ ./bin/findstr
sub: '->SOME CODES HERE<-'

If you are looking to parse something slightly different, let me know.

Answer 3

Although it's not mentioned in the question, it appears that you're receiving NMEA 0183 sentences. There are libraries (including free, open-source ones) for parsing such inputs, so I'm surprised to see hand-built code here. I recommend you choose a good library, and completely reimplement the code using the library.

---

Assuming you can't use any of the libraries for some reason, I'll continue with review.

You probably only want to recognise what2find at the start of a line, rather than in any other positions in the string. Although it's unlikely, it's possible that it appears (perhaps in a sentence that includes an arbitrary label or comment field).

There are serious problems with the test program - specifically the multi-line string literal. I'm guessing from knowledge of the format that the sentences should all start at beginning of line:

char buffer[] =
    "$GPGGA,123519,4807.038,N,01131.000,E,1,08,0.9,545.4,M,46.9,M,,*47\r\n"
    "$GPGSA,A,3,04,05,,09,12,,,24,,,,,2.5,1.3,2.1*39\r\n"
    "$GPGSV,2,1,08,01,40,083,46,02,17,308,41,12,07,344,39,14,22,228,45*75\r\n"
    "$GPRMC,123519,A,4807.038,N,01131.000,E,022.4,084.4,230394,003.1,W*6A\r\n"
    "$GPVTG,054.7,T,034.4,M,005.5,N,010.2,K*48\r\n";

This also shows a problem with the interface - is it necessary to require the input be modifiable? It seems reasonable that I should be able to pass a pointer to constant chars, and the example itself shows what2find being passed a string literal (which is necessarily const char*. It's also clearer for the reader if you write the destination capacity as sizeof dst rather than as literal 50.

Test should also perform a search for a sentence that exists in the input - at the moment, test coverage is very low.

Consider returning position and length of the result, and let the caller decide whether or not to copy. Alternatively, accept pointer to writeable characters, and null-terminate in-place - but note that that may preclude calling the function several times on the same data; it's more suited to line-by-line processing, perhaps with a callback for each sentence data type.

If you do need to copy within the function, there's no need to write your own strncpy() function.

Rename temp to something more descriptive; remove the empty statement following, and change if/return/else to plain if/return:

int findString(const char *src, char *dst, size_t desLen,
               const char *what2find, char termChar)
{
    char *start = strstr(src, what2find);
    if (!start) { return 0; }

    start += strlen(what2find);
    char *end = strchr(start, '\r');
    size_t length = end - start;
    if (length + 1 > desLen) { return 0; }

    memcpy(dst, start, length);
    dst[length] = '\0';
    return 1;
}