Jump to content
 

What every embedded programmer should know about ...

  • entries
    26
  • comments
    10
  • views
    1,327

Contributors to this blog

Tokenizing Keywords - Part 2

Sign in to follow this  
N9WXU

81 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.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
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.

  STRNCMP IF-ELSE
GNGSA 399 121
GPGSV 585 123
GLGSV 724 59
GPRMC 899 83
GPGGA 283 113

 

These are the CPU cycles required on a PIC16F1939.  You can verify in the simulator.

That is all for now.  Stay tuned, next time we will show a nice way to manage this maintenance problem.

Good Luck

example2.c

example2.X.zip

  • Like 1
Sign in to follow this  


0 Comments


Recommended Comments

There are no comments to display.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Add a comment...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...