Andrew Que Sites list Photos
Projects Contact
Main

April 04, 2021

Command Handler Lookup Table

Preamble: Before this series of articles begins it should be noted that the techniques explored here are generally not needed. The speed gains for most processors are negligible. Only specially constrained system—such as needing fast responses on very slow microprocessor—will benefit from the these techniques. However, there may be some lessons that port to other applications and make this series of exploratory articles worthwhile. My interest in writing this article set was to explore such options irrespective of how useful their real-world application might be.

As an embedded programmer I’ve written a number of serial protocols over the years. Serial communication is often used for the device to talk to a host computer or connect several devices together. The protocols consists of several characters grouped together to form a packet. These packets are most often binary data and use an natural integer number, the command, to denote the purpose of the packet transaction. This is very typical.

In software there is some method for dispatching specific commands to sections of code that handle that specific command. The most basic are simply switch statements.

typedef enum
{
  COMMAND__START,
  COMMAND__STOP,
  COMMAND__FORWARD,
  COMMAND__BACKWARD
} Command;

void handleCommand( Command command )
{
  switch ( command )
  {
    case COMMAND__START :    // ...
    case COMMAND__STOP :     // ...
    case COMMAND__FORWARD :  // ...
    case COMMAND__BACKWARD : // ...
  }
}

That becomes inefficient when there are a lot of commands because they are basically a series of if-statements. A rule of thumb one can assume that 50% of them are executed for each command, and if there are a 1000 commands that means 500 compares for every command. In addition this isn’t very modular. All the commands are handling code is in a single location. A better option is to use a lookup table that matches command numbers to a function that can handle the command.

void startCommand( void );
void stopCommand( void );
void forwardCommand( void );
void backwardCommand( void );

typedef enum
{
  COMMAND__START,
  COMMAND__STOP,
  COMMAND__FORWARD,
  COMMAND__BACKWARD,

  NUMBER_OF_COMMANDS
} Command;

typedef void (*CommandHandler)( void );

CommandHandler const COMMAND_HANDLERS[ NUMBER_OF_COMMANDS ] =
{
  startCommand,
  stopCommand,
  forwardCommand,
  backwardCommand
};

void handleCommand( Command command )
{
  COMMAND_HANDLERS[ command ]();
}

Most of the protocols I design use a lookup table. This table is defined in a C file with nothing else in it. Then a general dispatch can use this table without knowing anything about the commands being executed. This allows the protocol to remain general and only the commands themselves be application specific.

In implementation the command handler function has more parameters and a return value.

typedef bool (*CommandHandler)
(
  uint8_t const * input,
  uint16_t inputSize,
  uint8_t * output,
  uint16_t outputSize,
  uint16_t * outputBytes
);

Here is a more typical command handler function. It receives a pointer to either the entire packet, or the portion of the packet that has the command data. In addition, it receives a pointer to output data—data that is used in sending a response to the command. There is a location of where this data is to be stored, how much data can be stored there, and a pointer to set to denote how much data the handler function used. The handler itself is Boolean. I typically use a true on failure return result. This allows a Boolean flag to simply use a logical OR to run several function and at the end see if any of them failed.

bool isError = false;
isError |= function1();
isError |= function2();
isError |= function3();
isError |= function4();

if ( isError )
  // ...

Serial protocols differ depending on the application. The lookup table portion happens in the dispatcher. There can be a number of steps that take place before this such as packet integrity checking (such as verifying a CRC) as well as the maintenance of the transport layer. The dispatcher has to unpack enough of the packet to get the command number. It might also have to unpack an address to see if the packet is even directed to the current device. The command number also has to be verified.

In the example show, command number verification is as simple as checking that the number is less than the total number of commands. If so, there is a handler function in the lookup table. This isn’t always the case. Sometimes the command numbers are such there are gaps in command numbers.

typedef enum
{
  // Status commands
  COMMAND__VERSION = 0,
  COMMAND__ERROR_STATUS,
  COMMAND__GET_POSITION ,

  // Control commands
  COMMAND__START = 10,
  COMMAND__STOP,
  COMMAND__FORWARD,
  COMMAND__BACKWARD,

  NUMBER_OF_COMMANDS
} Command;

In this command numbering system, there are 7 commands, but 13 command table entries. The command table can simply use NULL to denote areas that are not valid commands. The dispatcher must then check to see if the command handler is valid before running it.

CommandHandler const COMMAND_HANDLERS[ NUMBER_OF_COMMANDS ] =
{
  versionCommand,      // 0  COMMAND__VERSION
  errorStatusCommand,  // 1  COMMAND__ERROR_STATUS
  getPositionCommand,  // 2  COMMAND__GET_POSITION
  NULL,                // 3
  NULL,                // 4
  NULL,                // 5
  NULL,                // 6
  NULL,                // 7
  NULL,                // 8
  NULL,                // 9
  startCommand,        // 10 COMMAND__START
  stopCommand,         // 11 COMMAND__STOP
  forwardCommand,      // 12 COMMAND__FORWARD
  backwardCommand      // 13 COMMAND__BACKWARD
};

void dispatcher( Command command )
{
  if ( ( command < NUMBER_OF_COMMANDS )
    && ( NULL != COMMAND_HANDLERS[ command ] ) )
  {
    COMMAND_HANDLERS[ command ]();
  }
}

I’ve worked on a number of applications needing a serial interface requiring a protocol like this and each application has unique protocol requirements. Some are single client/server configurations, some are multi-drop, some bidirectional, etc., etc. The lookup table command handler is part of all these system. What happens if the command is not a number, but instead a text string? That will be the topic of our next article.

April 05, 2021

Basic String Command Handler Lookup Table

In the previous article of this series I wrote about how a lookup table can be used by serial protocols to map a command to a handler function for a clean and efficient method to process commands. In this article we will look at what changes if the protocol uses text rather than binary data.

Recently I had to implement a text-based protocol based on JSON in an embedded system. There is still a command as there is with the binary protocol, but now the field is a text string rather than an integer number. I can still use a lookup table, but it requires some changes to do so. Let us begin with the lookup table itself.

typedef void (*CommandHandler)( void );

typedef struct
{
  char const * command;
  CommandHandler handler;
} CommandEntry;

CommandHandler const COMMAND_HANDLERS[ NUMBER_OF_COMMANDS ] =
{
  { "version",     versionCommand      },
  { "errorStatus", errorStatusCommand  },
  { "getPosition", getPositionCommand  },
  { "start",       startCommand        },
  { "stop",        stopCommand         },
  { "forward",     forwardCommand      },
  { "backward",    backwardCommand     },

  { NULL, NULL },
};

The lookup table now has two elements: the command string, and the handler function. This implementation is NULL terminated. That is, the last element in the table has NULL values so the dispatch function can tell if it has reached the end of the table.

void dispatcher( char const * command )
{
  unsigned index = 0;
  bool isFound = false;

  // Find command handler.
  while ( ( NULL != COMMAND_HANDLERS[ index ].command )
       && ( ! isFound ) )
  {
    isFound = ( 0 == strcmp( command, COMMAND_HANDLERS[ index ].command ) );
    if ( ! isFound )
      index += 1;
  }

  if ( isFound )
    COMMAND_HANDLERS[ index ].handler();
}

The dispatcher now just looks through the list of command strings for a match the command is found. If the command is found, it can be run. If not, the the requested command doesn’t exist and the error can be handled accordingly.

This is a perfectly functional solution, but not very efficient. In the first article I pointed out that using a switch statement means that on average 50% of the compares can be assumed to happen for each command issued. The same is true with this form of lookup table because we have simply taken the switch statement and turned it into table form. The lookup table is functionally equivalent to:

void dispatcher( char const * command )
{
  if ( 0 == strcmp( command, "version" ) )
    versionCommand();
  else
  if ( 0 == strcmp( command, "errorStatus" ) )
    errorStatusCommand();
  else
  if ( 0 == strcmp( command, "getPosition" ) )
    getPositionCommand();
  else
  if ( 0 == strcmp( command, "start" ) )
    startCommand();
  else
  if ( 0 == strcmp( command, "stop" ) )
    stopCommand();
  else
  if ( 0 == strcmp( command, "forward" ) )
    forwardCommand();
  else
  if ( 0 == strcmp( command, "backward" ) )
    backwardCommand();
  else
  {
    // Command is not found.
  }
}

Now the complaint I had against using a switch statement again applies and the lookup process isn’t very efficient. So is there a better way?

April 06, 2021

Binary Search Lookup Table

In the last article of this series I asked the question if there was a more efficient way to implement a string lookup table for command handlers. One fairly simple method is to sort the lookup table by command and use a binary search.

If the command list is alphabetically sorted, one could start by checking the requested command against the command name midway through the list. If there isn’t a match, the command either comes before or after this point because the list is sorted. For example if the issues command is bar and the middle command is foo we know we must search before this point because b is before f. This is a classic binary search technique. Let’s look at a full example of a search.

Binary search example

Here we have a list of words that are alphabetically sorted. Shown is the search path for Train. It begins in the middle of the list which is Horse. We have two partitions, Bike to Foot and Mule to Wagon. Because the first letter of Train comes after the first letter in Horse, we move to the right partition Mule-Wagon and select the middle which is Starship. Now we have two new partitions: Mule to Rocket, and Train to Wagon. Train comes after Starship so the Tain-Wagon partition is selected with the middle being Truck. Partition again. To the left is just Train and to the right just Wagon. Train comes before Truck so we select the left partition. The middle is Train, which happens to be the item we are search to find and the search is complete. Now let us look at an implementation.

enum { TABLE_LENGTH = 15 };

static char const * const TABLE[ TABLE_LENGTH ] =
{
  "Bike",     "Boat",      "Bus",   "Car",   "Dog Sled",
  "Elephant""Foot",      "Horse""Mule",  "Plane",
  "Rocket",   "Spaceship""Train""Truck""Wagon"
};

bool find( char const * key )
{
  bool isFound = false;
  unsigned partition = ( TABLE_LENGTH + 1 ) / 2;
  unsigned index = TABLE_LENGTH / 2;

  while ( ( ! isFound )
       && ( partition > 0 ) )
  {
    partition /= 2;

    int compare = strcmp( key, TABLE[ index ] );

    if ( 0 == compare )
      isFound = true;
    else
    if ( compare > 0 )
      // Must be after this.
      index += partition;
    else
      // Must be before this.
      index -= partition;
  }

  return isFound;
}

In this example we are just looking for some value using the same word set as in the graphic above. The find function returns true if the word was found, false if not. It illustrates the basics of how the search works. To function as a lookup we need to associate data with the key term being searched for.

typedef struct
{
  char const * key;
  int value;
} TableEntry;

enum { TABLE_LENGTH = 15 };
static TableEntry const TABLE[ TABLE_LENGTH ] =
{
  { "Bike",       10 }{ "Boat",       20 }{ "Bus",        30 },
  { "Car",        40 }{ "Dog Sled",   50 }{ "Elephant",   60 },
  { "Foot",       70 }{ "Horse",      80 }{ "Mule",       90 },
  { "Plane",     110 }{ "Rocket",    120 }{ "Spaceship"130 },
  { "Train",     140 }{ "Truck",     150 }{ "Wagon",     160 }
};

int find( char const * key )
{
  int result = -1;
  unsigned partition = ( TABLE_LENGTH + 1 ) / 2;
  unsigned index = TABLE_LENGTH / 2;

  while ( ( -1 == result )
       && ( partition > 0 ) )
  {
    partition /= 2;
    int compare = strcmp( key, TABLE[ index ].key );

    if ( 0 == compare )
      result = TABLE[ index ].value;
    else
    if ( compare > 0 )
      index += partition;
    else
      index -= partition;
  }

  return result;
}

Here we have added an integer lookup. The implementation is the same no matter the data type of the value. One item to note is that we use a token return value for when the key isn’t found. In this case we use -1. If being used as a function lookup table NULL serves the same purpose. A token return value isn’t ideal for all situations. The function could return a Boolean result denoting if the find was successful or not, and a pointer to store the result passed as a parameter. This would be needed if the entire return space is valid.

typedef struct
{
  char const * key;
  uint8_t value;
} TableEntry;

enum { TABLE_LENGTH = 15 };
static TableEntry const TABLE[ TABLE_LENGTH ] =
{
  { "Bike",      0x00 }{ "Boat",      0x12 }{ "Bus",       0x24 },
  { "Car",       0x36 }{ "Dog Sled",  0x48 }{ "Elephant",  0x5B },
  { "Foot",      0x6D }{ "Horse",     0x7F }{ "Mule",      0x91 },
  { "Plane",     0xA3 }{ "Rocket",    0xB6 }{ "Spaceship"0xC8 },
  { "Train",     0xDA }{ "Truck",     0xEC }{ "Wagon",     0xFF }
};

bool find( char const * key, uint8_t * result )
{
  bool isFound = false;
  unsigned partition = ( TABLE_LENGTH + 1 ) / 2;
  unsigned index = TABLE_LENGTH / 2;

  while ( ( ! isFound )
       && ( partition > 0 ) )
  {
    partition /= 2;
    int compare = strcmp( key, TABLE[ index ].key );

    if ( 0 == compare )
    {
      isFound = true;
      *result = TABLE[ index ].value;
    }
    else
    if ( compare > 0 )
      index += partition;
    else
      index -= partition;
  }

  return isFound;
}

Our examples will always find a result in no more than 4 comparisons. The maximum number of comparisons done before finding a result is always ⌈ log2 n ⌉ where n is the number of entries in the table. For our example n is 15, so ⌈ log2 15 ⌉ = ⌈ 3.907⋯ ⌉ = 4.

The downside of a binary search is that it requires the data to be sorted. If you are able to specify the lookup table in sorted order this method is easy. If not a sort will be required and that will be the topic for the next article.

April 07, 2021

Sorting for Binary Search Lookup Table

In the last article of this series we looked at using a binary search to increase the speed of finding a command in a lookup table by reducing the number of comparison needing to be performed. However this requires the lookup table to be sorted. If the lookup table isn’t stored sorted, this will need to be done at run time.

By far the simplest sort to implement is a selection sort and is a good place to start.

void selectionSort( char const * array[], size_t arrayLength )
{
  for ( size_t indexA = 0; indexA < arrayLength - 1; indexA += 1 )
  {
    size_t lowest = indexA;
    for ( size_t indexB = indexA + 1; indexB < arrayLength; indexB += 1 )
    {
      int compare = strcmp( array[ indexB ], array[ lowest ] );
      if ( compare < 0 )
        lowest = indexB;
    }

    char const * hold = array[ indexA ];
    array[ indexA ] = array[ lowest ];
    array[ lowest ] = hold;
  }
}

Lookup tables are generally constant and with embedded systems it is best to keep them this way. This is because there is typically more non-volatile memory (typically flash memory) than RAM and constants can be kept in program storage. Our sort algorithm can still be used if instead of sorting the actual lookup table we simply sort a set of indexes into the lookup table.

static char const * TABLE[] =
{
  "which",  "word",    "thing",   "great",  "should""write",
  "some",   "ask",     "after",   "every",  "been",   "if",
  "any",    "house",   "day",     "way",    "going",  "their",
  "from",   "because""would",   "nice",   "just",   "live",
  "first",  "long",    "put",     "were",   "where",  "rain",
  "very",   "thank",   "could",   "before""about",  "hers",
  "walk",   "right",   "your",    "by",     "or",     "jump",
  "other",  "think",   "yours",   "back",   "kind",   "when",
  "work",   "now",     "people",  "these",  "than",   "also",
  "learn",  "each",    "another""how",    "may",    "again",
  "only",   "had",     "went",    "want",   "high",   "find",
  "then",   "give",    "keep",    "more",   "old",    "over",
  "know",   "them",    "much",    "use",    "funny",  "many",
};

enum { TABLE_LENGTH = sizeof( TABLE ) / sizeof( TABLE[ 0 ] ) };

static size_t sorting[ TABLE_LENGTH ];

static void selectionSort( void )
{
  // Start with 1:1 mapping.
  for ( size_t index = 0; index < TABLE_LENGTH; index += 1 )
    sorting[ index ] = index;

  // Selection sort mapping.
  for ( size_t indexA = 0; indexA < TABLE_LENGTH - 1; indexA += 1 )
  {
    size_t lowest = indexA;
    for ( size_t indexB = indexA + 1; indexB < TABLE_LENGTH; indexB += 1 )
    {
      // Get the indexed values.
      char const * newKey    = TABLE[ sorting[ indexB ] ];
      char const * lowestKey = TABLE[ sorting[ lowest ] ];

      // Compare these values.
      int compare = strcmp( newKey, lowestKey );

      // If this value is the new lowest value.
      if ( compare < 0 )
        lowest = indexB;
    }

    size_t hold = sorting[ indexA ];
    sorting[ indexA ] = sorting[ lowest ];
    sorting[ lowest ] = hold;
  }
}

We start by creating a 1:1 index into the lookup table. Then we sort this list. When it comes time to do the binary search, it too must use the index table.

static bool find( char const * key )
{
  bool isFound = false;

  int left = 0;
  int right = TABLE_LENGTH - 1;

  while ( ( left <= right )
       && ( ! isFound ) )
  {
    int index = ( left + right ) / 2;
    int resultIndex = sorting[ index ];
    int compare = strcmp( key, TABLE[ resultIndex ] );

    if ( 0 == compare )
      isFound = true;
    else
    if ( compare > 0 )
      left = index + 1;
    else
      right = index - 1;
  }

  return isFound;
}

A select sort has fairly terrible performance at O( n2 ). A quick sort with an average performance of O( n log2 ).

void quicksort( int first, int last )
{
  if ( first < last )
  {
    int pivot = first;
    int start = first;
    int end = last;

    while ( start < end )
    {
      while ( ( strcmp( TABLE[ sorting[ start ] ], TABLE[ sorting[ pivot ] ] ) <= 0 )
           && ( start < last ) )
      {
        start += 1;
      }

      while ( strcmp( TABLE[ sorting[ end ] ], TABLE[ sorting[ pivot ] ] ) > 0 )
        end -= 1;

      if ( start < end )
      {
        size_t temp     = sorting[ start ];
        sorting[ start ] = sorting[ end ];
        sorting[ end ]   = temp;
      }
    }

    size_t temp      = sorting[ pivot ];
    sorting[ pivot ] = sorting[ end ];
    sorting[ end ]   = temp;

    quicksort( first, end - 1 );
    quicksort( end + 1, last);
  }
}

There are typically so few elements in a function lookup table it is hardly worth taking the effort to write a quick sort function. However, quick sort is actually built into the C standard library. It requires writing a compare function. Since it already exists, may as well use it.

static int tableEntryCompare( void const * a, void const * b )
{
  TableEntry const * valueA = &TABLE[ *(size_t const *)];
  TableEntry const * valueB = &TABLE[ *(size_t const *)];

  return strcmp( valueA->key, valueB->key );
}

void setup( void)
{
  for ( size_t index = 0; index < TABLE_LENGTH; index += 1 )
    sorting[ index ] = index;

  qsort( sorting, TABLE_LENGTH, sizeof( sorting[ 0 ] ), tableEntryCompare );
}

The standard library actually has a binary search as well so we can do the entire lookup using this functionality.

static int searchCompare( void const * a, void const * b )
{
  char const * key = (char const*)a;
  size_t indexB    = *(size_t const *)b;

  char const * valueB = TABLE[ indexB ];

  return strcmp( key, valueB );
}

static bool find( char const * key )
{
  void * result = bsearch( key, sorting, TABLE_LENGTH, sizeof( sorting[ 0 ] ), searchCompare );

  return ( NULL != result );
}

Unfortunately the way the binary search is implemented it actually takes more lines of code (when cleaned up and fully commented) to use it than to implement it ourselves. So it is easier to simply write out the binary search in the lookup function.

We will finish off with a complete command handler using a binary search, indirect sorting and the standard library quick sort.

This implementation needs to be broken into several files because a demonstration with actual command handlers requires those handlers to be actual functions. However the use of such a system comes down to using the results of the lookup function.

// Get the command handler function.
CommandHandler handler = findHandler( command );
isError = ( NULL == handler );

if ( ! isError )
  // Run the command handler.
  handler();

This implementation is alright if one can live with the additional memory needed for the sorted index and a quick sort function from the standard library which is likely recursive.