Tokenizing Keywords - Part 2

Entry posted by N9WXU · January 16, 2019

468 views

Quote

A man's gotta do what a man's gotta do. - Louis L'Amour

When we left off we had just built a test framework that allowed us to quickly and easily try out different ways to identify NMEA keywords. The first method shown was a brute force string compare search. For this week, I promised to write about an if-else decoder. The brute force search was all about applying computing resources to solve the problem. This approach is all about applying human resources to make life easy on the computer. So this solution will suck. Let us press on.

The big problem with the string compare method is each time we discard a word, we start from scratch on the second word. Consider that most NMEA strings from a GPS start with the letters GP. It would be nice to discard every word that does not begin with a G and only look at each letter once. Consider this state machine:

example.dot.png

I did simplify the drawing… every invalid letter will transfer back to state 1 but that would clutter the picture. This would require the smallest number of searches to find the words. So one way to build this is to write a big IF-ELSE construct that covers all the choices. This will step through the letters and end up with a decision on what keyword was found.

enum wordTokens NMEA_findToken(char *word)
{
    enum wordTokens returnValue = NO_WORD;
    char c = *word++;
    if(c == 'G')
    {
        c = *word++;
       if(c == 'P')
       {
           c = *word++;
           if(c == 'G') // gpGga or gpGsv
           {
               c = *word++;
               if(c == 'G') // gpgGa
               {
                   c = *word++;
                   if(c == 'A')
                   {
                       if(*word == 0) // found GPGGA
                       {
                           returnValue = GPGGA;
                       }
                   }
               }
               else if(c == 'S') // gpgSv
               {
                   c = *word++;
                   if(c == 'V')
                   {
                       if(*word == 0) // found GPGSV
                       {
                           returnValue = GPGSV;
                       }
                   }
               }
           }
           else if(c == 'B') // gpBod
           {
               c = *word++;
               if(c == 'O')
               {
                   c = *word++;
                   if(c == 'D')
                   {
                       if(*word == 0)
                       {
                           returnValue = GPBOD;
                       }
                   }
               }
           }
           else if(c == 'D') // gpDcn or gpDbt
           {
               c = *word++;
               if(c == 'C')
               {
                   c = *word++;
                   if(c == 'N')
                   {
                       if(*word == 0)
                       {
                           returnValue = GPDCN;
                       }
                   }
               }
               else if(c == 'B')
               {
                   c = *word++;
                   if(c == 'T')
                   {
                       if(*word == 0)
                       {
                           returnValue = GPDBT;
                       }
                   }
               }
           }
       }
       else if(c == 'N') // gNgsa
       {
           c = *word++;
           if(c == 'G')
           {
               c = *word++;
               if(c == 'S')
               {
                   c = *word++;
                   if(c == 'A')
                   {
                       if(*word == 0)
                       {
                           returnValue = GNGSA;
                       }
                   }
               }
           }
       }
    }
    return returnValue;
}

And it is just that easy. This is fast, small and has only one serious issue in my opinion. I hope you are very happy with the words chosen, because making changes is expensive in programmer time. This example only has 6 6-letter words and is 100 lines of code. They are easy lines, but almost all of them will require rewriting if you change even one word.

Here are the stats so you can compare with last weeks string compare.