Real Software, Automotive, and Software Leadership

Introduction:

One can find lots of great articles on state machines and even a few good ones on coding a state machine. However, I have noticed most examples are written in modern languages (or scripts) and seem to be more samples of the language syntax and features than to show how state tables can produce code that fits into a small space, fast at execution, can easily add features, efficiently change current states, and can be maintained professionally (not hack in a new state and impact large sections of code causing lots of all-nighters). Given that, I thought it might be nice to write down and show some old and simple coding techniques for basic state tables. Forgive the pictures. I know its tough to think code through in pictures. I will gladly send you the source files – see at the bottom.

Background. What Is Simple State Table:

A great analogy of a state table is the rooms in your house. To get to your bedroom, you must enter through the front door (state 0), once in your living room (state 1) may have two choices to go to next – the hallway (state 2) or the dining room (state 3), if you pick the hallway (state 2) you can then access bedroom 1 (state 4) or bedroom 2 (state 5), or bedroom 3 (state 6). You select your room (state 4). Fig. 1. To get back out of the room, you would reverse the process, only accessing rooms that were available to you. With further examination, you see you could not access bedroom 6 if you were in the kitchen, that would require you go to the dining room, then the hallway, then the bedroom. If your still not completely confident you understand state tables, I suggest googling them – as I mentioned, lots of good articles that explain them far better than I do. Understanding them is essential before getting into our sample program and map.

How Can A State Table Help You With Problems:

Engineers fix problems. It’s what they are paid to do. State tables can be a great way to fix those problems (maybe even some personal problems). Take HTML as an example. Let’s say you have chartered with coding up a parser of HTML. And you need to process it a character at a time as it’s characters come across the TCP/IP network. You know there are lots of functions and functions within functions you will have to deal with, and at some point, you will have to return to those functions and their state that they were in when you left. In this simple example we start at state 0, and two things may come down the line: <header> or <body>, and you will need to shift into one those states, and then enter new states, even with the possibility that your current state is one of those states you need to move to. In this example, these two states can share sub-states, such as <Title>. So <body> leads to <title> which can lead to <body>. I shiver at the possibilities.

Hopefully, you get the point – and state tables can be an efficient way to process these characters and their requested states, recursive or sub-states or otherwise, etc. State tables can also process these requests quickly. In our example the HTML is coming at us fast down the wire, so there is no time to stop and execute a huge switch/case statement for each character.

Let’s examine a less popular scenario an SW engineer might face: An automotive ECU will need to processes commands as they come across the CAN network (very fast). Data from OS2 sensors, fuel sensors, knock sensors, etc. All of these can move to new states or be dependent on states from which they came or on other states, etc. Specific to this example, one can see how a small footprint (our ECU is running an RTOS) and quick executing state table is needed.

When pondering the possibilities, a good state table can be used for many proposes. Writing a compiler, a complex terminal emulator, a parser for your newly invented script language, and handling a variety of communications quickly to name a few. The list is vast.

*This article is not meant to be a comprehensive HTML nor ECU guide, I am just using a fictional function or two as an example.

Challenges:

So, you are ready now with your state table knowledge and mapped out the flow to solve the programming problem you have been assigned. However, you still face challenges. How can you get your state table code into a small space, make it quick, and keep track of memory contents of your states? In modern languages, they have great ways to implement state table: Multiple dimensional arrays, the ever-popular Switch/Case statement, etc. etc. These all have benefits as well as downfalls, and you may find in many cases these languages and syntax meet your needs. Example of this: Perhaps your states only have 2 or 3 options. However, maybe the language complies too large if you have massive number of states dependent on other states. Maybe given your compiler executing large Switch/Case statements is slow at runtime. And lastly, how do you keep track of states if you are using one state, then enter another, but want to return with your old data intact without creating huge lists of global variables? Think in terms of your HTML parser again. States can call on selected states to do functions and return while other states requesting the same function. These are crux of the problems we will attempt to address with the coding sample that we will be discussing below.

Our Program/Framework:

For problem definition, I chose Disney Princesses and their kingdoms. They each have a kingdom in which they live, and these kingdoms can overlap. You can only enter a kingdom from overlapping kingdoms (like the rooms of our house in Fig. 1). Each Princess has her specific data for that kingdom (handsome dude, fancy dress, castle, etc.) within her instance of the kingdom. We also need a way to follow through the kingdoms, and when we return from one kingdom, we want to return to the Princess and her specific data we meet in the previous kingdom. I provided a kingdom map so you can see how the kingdoms overlap and what kingdoms are accessible from which kingdom. The map also includes the characters that signal our crossover (start and end) into a new kingdom. To make it challenging, I randomly threw each kingdom and their overlaps on the map. See Fig 2.

The coded sample we are examining attempts to show, in basic C, three easy to use and simple techniques you can use to implement to solve the problems listed above:

Call address – This address will change with each state. Dynamically replacing this call address is an efficient way to set the current state and not worry about it. Its also fast, and they compile to a small footprint. Fig 3.
Jump tables – Jump tables are quick and easy to read. These enable us to match the next character based on its value in whatever state we are currently in. I first saw the usage of the jump tables technique in the old CP/M operating systems code, so it is by no means a new technique. I feel it is far better than making huge Switch/Case statements and having a large amount of associated machine code generated by them. Fig 4.
No global data – A handle (bread crumb) for each Princess and her kingdom is allocated when her kingdom entered and kept in a stack. We use these handles as bread crumbs. We can traverse our path by using this stack of handles. A bonus note: I have found using handles and keeping your code clean, and reentrant, is just good programming. Fig 5 and Fig 6. Locking this handle and getting a pointer to this data on entry to the state, and unlocking on exit is essential. Here is an example of how to define a pointer to this data for when you lock. Fig. 6.

* There are a few global variables in the framework to facilitate such items as file/io. This was done for simplicity. I do not want to spend a bunch of time explaining how to read a file, nor how to recover from and error accessing this file, as this is not the point of our discussion. The file/io, in this case, is our “stream” and is added as a simple way to feed characters to our state machine.

**These three techniques work even better in Assembler. I chose to sample them in C to cover a broader range of people that may find it useful.

***The framework does not make use of extensive error checking, nor has it been refactored for elegance. I purposely did not add/do these things as they distract from or hide the code techniques I am trying to highlight.

How It Operates (Step By Step):

I use a simple text file. It is opened, and the characters are feed to the state machine one at a time. This file and its bytes are our “stream” of data. Characters in this “stream” can set and end a state. In our test file we use lower case as text and upper case to trigger states on and off. Fig. 3.

Each character from the “stream” is passed to the default processing routine for the current state. When a new state is started, we place the default process routine address of the new state as the routine to start calling and we push that handle on the stack. When a state is ended, we free the handle and pop the BC stack. Fig. 3 and Fig 5.

When a state is started or ended, we allocate or free Princess data for that unique instance of the state. Fig. 5.

As each character is dispatched to the current state, we will use the value of the character as an offset into our ASCII based table and obtain the function number to call in our function table. Fig. 4 and Fig. 5.

Example: Our character has a value of 0x01.

Get the function number at 0x01h (let’s say FUNC2) and call that function number in the function jump table.

Results:

With the rudimentary measuring tools I have on my home PC, I was able to generate the following results running the TableDrivenStateMachine.exe vs. a similar program I wrote utilizing case statements. Both used the same test file:

Disk footprint: Reduced by 10.9% (this is most likely the most inaccurate measurement taken given the compiler gave me multiple results when measuring.)
Memory when loaded: Reduced a by whopping 25% (this is the most accurate measurement taken if we trust Microsoft)
Execution/processing time: Reduced by 15.5% (this is significant as this reduction was measured in nanoseconds using the small test file of ~ 1000 bytes – time savings stack up if we were pushing millions of bytes thorough the state table or paying someone for processing time). I left the debug code for timing and printf state entrance/exit in the code for your convenience.

*Compilers differ in strengths, and results may vary with your compiler choice.

**Neither program was optimized nor refactored for size (I didn’t want to lose the ability to see the flow, tables, and memory usage clearly.)

**None of these measurements were done with professional benchmarking tools. Just Bradley and I spitballing it.

Epilogue:

An additional advantage of the sample framework and techniques is maintainability. I don’t talk about it much, but as you can see, adding a new state or adding a function to a state is very easy and low impact on the overall code. Real-life: Marketing announces, late in the schedule, they need to move a forest. They say if we don’t move the forest, all life as we know will cease to exist. Make a quick change or two to your tables, and you’re the hero of the hour, ready to receive your vast king’s ransom of a bonus.

If you feel this article or framework could help you, I will gladly answer any questions you may have. I will also send you, for free and with no hidden agenda, the complete project source code. I use MS Development Studio and Windows as the environment. It contains simple .c and .h files and includes a test run TEXT file. Setting up a project of your own should be fairly simple. You can add the .c and .h files to your compiler, change your standard library calls if needed, and it should compile easily into the environment/debugger of your choice. As I mentioned, I kept it as simple as possible to make it easy to read, debug, and see it execute. The point is to enable you to extract the state table techniques for your usage and glory. Email me at randallcstevenson@gmail.com or contact me on LinkedIn, and I will gladly send the files.

*Disclaimer: I did not use Vanellope Von Schweetz as a princess as the controversy on her princess status is ongoing.

Things That Bradley and I Love

Simple Table Driven State Machine Techniques

Introduction