So far the last few articles of this series have talked about sorting a lookup table at run time to enable the use of a binary search to speed up string lookups. Sorting the constant list at run time is a bit inefficient and sorting the list at compile time would eliminate the sorting setup time as well as any additional memory. It is actually fairly simple to do if using a make based project build. In this article we will examine the details of using a Makefile to build the lookup table as part of the build process.

There are a number of ways this can be done the method explored here is to have the lookup table declared as a string table. The file in which it is declared compiles in one of two ways. When a compiler define is set the file is designed to run on the build machine. It will sort the lookup table and print the results. When run without the define it will include a file that is the output of the previous system and use that lookup table.

Here we see an example of a lookup table. It starts by including all of the files that declare the various command handlers. Note how these are wrapped in a #if section. When building the lookup table these files are not needed—only when actually declaring the lookup table.

The next section is the lookup table itself. Note that although the lookup table is actually a string and a function, the deceleration is done with two strings. The sort program needs strings, but will output the command handler without quotes in the built output.

Following the lookup table is the program that can sort the list just above it. This program uses the standard library’s build-in qsort function for doing the sorting. The sorted output is printed to standard out and formatted to be the body of an array of command handlers. That is the end of all the code that runs at compile time.

The last section starts with declaring the actual lookup table used by the program. It includes a file in the middle of the HANDLERS table. This works because in C, a #include is like any other pre-processor macro. All it does is substitute the contents of the specified file at that location. In this case it is simply importing all the values of the lookup table from what is presumably the output of the previous section of the file.

Lastly is a function to actually use the lookup table. It is a binary search of the sorted array to find and return the handler for the given command just like we’ve outlines in previous articles. That’s it for the lookup table itself.

The other part of the setup is the Makefile.

PROJECT_NAME = lookup

# Location to store object files.
OBJECT_DIRECTORY ?= /tmp/$(PROJECT_NAME)

# Lookup table files.
LOOKUP_FILE := lookupTable.c    # <- File to create lookup table.
LOOKUP_OUT  := sortedTable.inc  # <- Sorted lookup table output file.

# Compiler flags.
# Turn on just about every warning and treat them all as errors.
# Enforce strict C99 compliance.
# Level 2 optimization (some warnings only happen when inline functions are
# enabled).
CFLAGS =                                    \
  -Wall                                     \
  -Werror                                   \
  -Wextra                                   \
  -Werror-implicit-function-declaration     \
  -Wpointer-arith                           \
  -std=c99                                  \
  -pedantic                                 \
  -O2

# Code files and object file lists.
DIRECTORIES := $(shell find . -type d -not -path '*/\.*' )
C_FILES     := $(foreach dir,$(DIRECTORIES),$(wildcard $(dir)/*.c))
H_FILES     := $(foreach dir,$(DIRECTORIES),$(wildcard $(dir)/*.h))
OBJECTS     := $(patsubst %.c,$(OBJECT_DIRECTORY)/%.o,$(C_FILES))
EXECUTABLE  := $(PROJECT_NAME)
INCLUDES    := $(foreach dir,$(DIRECTORIES),-I$(dir))
OBJECT_DIRECTORIES := $(foreach dir,$(DIRECTORIES),$(OBJECT_DIRECTORY)/$(patsubst ./%,%,$(dir)))

# Compiler for platform code.
GCC_PATH =
PREFIX = # arm-none-eabi- for ARM-based processors.
CC = $(GCC_PATH)$(PREFIX)gcc
LD = $(GCC_PATH)$(PREFIX)gcc

# Local compiler.
LCC = gcc

# Default build type (everything).
default: $(EXECUTABLE)

# Phony targets.
.PHONY : all clean list

# Dependencies
-include $(C_FILES:%.c=$(OBJECT_DIRECTORY)/%.d)

#-----------------------------------------------------------------------------
#	Define build targets.
#-----------------------------------------------------------------------------

# Object directories.
$(OBJECT_DIRECTORY):
	@echo "Creating object directory: $(OBJECT_DIRECTORY)"
	@mkdir -p $(OBJECT_DIRECTORIES) $(ARTICACTS_DIRECTORY)

# Sorted lookup table.
$(LOOKUP_OUT): $(LOOKUP_FILE) | $(OBJECT_DIRECTORY)
	@echo "Lookup table: $(LOOKUP_OUT)"
	@$(LCC) -DLOOKUP_LIST $(CFLAGS) $(LOOKUP_FILE) -o $(OBJECT_DIRECTORY)/lookupList
	@$(OBJECT_DIRECTORY)/lookupList > $(LOOKUP_OUT)

# Compile C files.
$(OBJECT_DIRECTORY)/%.o: %.c | $(OBJECT_DIRECTORY) $(LOOKUP_OUT)
	@echo "Compiling: $<"
	@$(CC) $(INCLUDES) -c $(CFLAGS) -MMD -o $@ $<

# Linker.
$(EXECUTABLE): $(OBJECTS)
	@echo "Linking: $@"
	@$(LD) $(LFLAGS) -o $@ $(OBJECTS) $(LIBS)

# Clean object C files.
clean:
	@echo "Cleaning project build files..."
	@rm -Rf $(EXECUTABLE) $(LOOKUP_OUT)
	@rm -Rf $(OBJECT_DIRECTORY) $(projectName).a

# List all variables.
list:
	@echo "DIRECTORIES        = $(DIRECTORIES)"
	@echo "C_FILES            = $(C_FILES)"
	@echo "H_FILES            = $(H_FILES)"
	@echo "OBJECTS            = $(OBJECTS)"
	@echo "OBJECT_DIRECTORIES = $(OBJECT_DIRECTORIES)"
	@echo "EXECUTABLE         = $(EXECUTABLE)"
	@echo "OBJECT_DIRECTORY   = $(OBJECT_DIRECTORY)"

Here I am using a universal Makefile. It will simply build every C file in the directory tree. Where it departs for a typical universal Makefile is an additional dependency. There is a rule to make a file called sortedTable.inc. To do this, it runs the local compiler to build lookupTable.c with the define LOOKUP_LIST declared. This will compile a program that will print out the sorted command handler list. After building this program is run and the output redirected to sortedTable.inc thus creating the sorted lookup.

The only other step is to apply this dependency to all the C object files. Without this the build process is setup to first create all the object directories, compile all C files to objects, and then link all objects. The new process now creates all object directories, creates the sorted lookup table, compiles and links. Dependencies still work. A change made to the lookup table will result in a new sorted lookup table list and recompile of lookupTable.c. A change to one of the function handler C files will only recompile that handler. A change to a handler header file will cause lookupTable.c to recompile but not regenerate the lookup table.

This concept can be used for non-make based projects as well. Any compile system with a pre-build command can be used to build the sorted lookup table. Rather than compile and running a local program the Makefile could use a scripting language like Python or even shell utilities to build the sorted list. This would likely require some restructuring of how the initial lookup table is initially declared but is otherwise follows the same setup.

For very small micro processors this method might be the best. There is no sorting overhead on the target processor at all and the binary search adds a negligible amount of code to the lookup process while giving it a lookup speed increase that improves the larger the lookup table.

In the last article in this series we showed how a command lookup table could be implemented be indirectly sorting an index table using the quick sort function of the standard library. There are applications where using the standard library isn’t allowed (such as with medical and avionics devices). In addition, recursive functions are also often not allowed because it can be difficult to ensure there is enough stack space.

The solution is to use a non-recursive sort function. When it comes to general purpose sorting almost nothing beats a quick sort. The downside of the algorithm is that it either needs to be recursive or use a stack. With purely static applications (i.e. applications that use no heap memory) the stack is wasted space after the command lookup table is sorted. It is possible the stack could use memory that is recycled latter on, such as the receive buffers for the communication system the lookup table is going to use after it has been initialized. However it would be better if there were no stack at all.

While you usually cannot beat a quick sort, you can sometimes match its performance. A heapsort has similar performance, and it can be implemented iteratively without the need for a stack.

The setup function first initializes the sorting index table and then sorts it using a heapsort. This can be a drop-in replacement for the setup that uses a quicksort.

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.

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.

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.

A select sort has fairly terrible performance at O( n² ). A quick sort with an average performance of O( n log₂ n ).

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.

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

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.

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.

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 binary search.

If the command list is alphabetically sorted, one could start by checking the issued 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 above this point because b is before f. This is a classic binary search technique. Let’s look at a full example of a search.

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.

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.

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.

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 ⌈ log₂ n ⌉ where n is the number of entries in the table. For our example n is 15, so ⌈ log₂ 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.

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.

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.

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:

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?

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

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.

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.

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.

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.

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.

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.

Last Friday I had a dream about implementing some kind of linked-list tree to speed up string searches used in a command handler I had implemented for work. The following morning I learned the method has a name: Binary Search Tree (BST). By the end of the weekend I had written a lengthy article about implementing a binary search tree when I discovered I made a bad assumption early on.

My mistake: Thinking a generic binary search tree was self-balancing. While the tree worked as a lookup table, it didn’t offer any benefit because the way I had it implemented gave it the same properties as a linear search.

In the process of failing, I rediscovered a binary search. I dismissed using a binary search because you need to start with sorted data. I thought my binary tree was self-balancing, thus the sort would happen as part of the process of assembling the tree. I was also trying to avoid recursive functions and dynamic memory allocation. Quick sorts typically use recursive functions or need a stack that is best implemented with dynamic memory allocation.

The process wasn’t an entire waste, however. The I plan to write an article about using a binary search to improve the speed of a string-based lookup table.