An Alternative Way to Write State Machines (FSMs)

Writing Finite State Machines (FSMs) in C language can be tedious and sometimes confusing, specially when you have to deal with different waiting states and conditions by using switch statements. In this article I present an alternate way to write state machines which can render more readable and efficient code! Welcome to GPL state machines!

State machines (or finite state machines, FSMs) are computational abstractions which describe an algorithm as a sequence of states, where only one state is valid at a given moment. They are a very good way to write non-blocking code in a cooperative multitasking fashion, but without the need of an operating system. However, our objective here is not to describe how to apply state machines to solve problems, but to demonstrate an alternative way to write them.

Enum/Switch State Machines

Most of C implementations of state machines rely on two key elements:

  1. An enumeration describing all the possible states;
  2. Switch statement with case clauses covering all states;

A typical state machine is shown below:

Writing simple state machines with enum and switch is completely ok and extremely common, but more complex state machines can be challenging, leading to convoluted and harder to read code. Some examples of state machines complexities:

  • There is a need of new intermediate or sub-states;
  • Code that needs to run only when entering or leaving a state and so on.

But what could be the alternative to using switch statement? Of course I am not talking about nested ifs (it would be even more convoluted!). In fact, the answer comes by putting together three  powerful (and sometimes not well known) elements of C language: goto, pointers and labels (hence GPL).

For most of the audience, using goto is probably a bit unusual and most coding standards out there might even forbid using it, but if correctly used, I believe goto is a very powerful element of C language.

But what is a goto anyway? Well, let’s start with a label. In C, just like in assembly, a label evaluates to an address. And goto is nothing else than a jump. The combination of goto and labels allow changing code flow in several ways.  Thus, considering that a label is an address, what else is an address in C?

If you said a pointer, you are absolutely correct!

But how can we put these three elements together to write state machines? That is what you are about to find out!

Goto and Pointers

Our GPL FSM approach relies on three basic macro constructors. These constructors are the building blocks we are going to use to write our state machines.

FSM_START

#define FSM_START() static void *jumper = NULL; if (jumper!=NULL) goto *jumper;

This macro has two very distinct sections. The first one declares a static void pointer variable called jumper. It is the heart of our state machine storing the address of the next FSM state when our FSM is running.

The second part controls the actual change of flow, or jumping to the correct internal FSM state. It basically checks whether the content of jumper is not NULL and jumps (goto) to it! However, if jumper is NULL the code simply proceeds to the next statement. Keep in mind that goto *jumper actually compiles to a “jump to absolute address” instruction!

The code following this macro is usually FSM initialization or startup code.

The second macro performs a yield operation, storing the desired next FSM state and returning control to the main application (outside the FSM).

FSM_YIELD

#define FSM_YIELD(nextState) ({jumper = &&nextState; return;})

This is where most of the magic happens! FSM_YIELD sets the desired next state for the FSM and returns (exits) the function. It accepts a C label as argument which marks the start of the code for that desired state. I chose the term yield because this is a very lightweight method to achieve cooperative multitasking (if you want to see some preemptive multitasking, check my ULWOS)!

Note that on this implementation, we always “yield” to the caller (usually main code), suspending the FSM and storing the desired state for the next iteration!

In case you are curious about the && operator, this is the GCC “address of label” operator! It simply returns the code location (address) of a label and this address is stored into jumper variable. We can use a goto statement to branch to it!

Keep in mind that this is quite different than using a function pointer. A function pointer is expected to point to the entry point of a function, whereas our label pointer works as an internal bridge within the same function. Therefore, we can’t use function pointers for this kind of branching since labels refer to code within a function and calling directly that code would skip function prologue section!

Finally, the last piece of the puzzle is a macro that forces the FSM into its reset state:

FSM_RESET

#define FSM_RESET() ({jumper = NULL; return;})

All it does is to set jumper to NULL and return, forcing the startup code to run on the next FSM iteration.

Now let’s take a look at how we can use these macros to implement a state machine:

State Machine Examples!

We have seen how we can write an FSM using this alternative approach and now it is time for a working example! I decided to design a very simple (and quite common) traffic light state machine.

The first code shows an FSM using the traditional approach of enum and switch:


Now let’s see how the same state machine can be implemented using our GPL FSM:

You can see that our GPL FSM is easier to read, it’s code is smaller and there wasn’t a need to create any enumeration. All you need to do is to create labels and yield to them as needed!

Note that if you have unused labels (such as TL_RED and TL_GREEN on the above example) you might get warnings (if -Wall or -Wunused-label is used) and might get errors if -Werror is used.

How Efficient Is It?

Having seen the coding differences between the two methods, let’s take a look at the resulting code size. The table below compares the two methods on two different platforms (x86-64, using online clang compiler 7.0.0 on the examples above, and ARM 32 bits using GCC 4.9.3).

x86-64 clang 7.0.0 ARM 32 GCC 4.9.3
enum/switch FSM 265 bytes 88 bytes
GPL FSM 225 bytes 78 bytes

Closing

I hope you find GPL FSMs as useful as I do! I truly believe that writing FSMs using this method can more efficient, easier to read and maintainable code. See you next time!

%d bloggers like this: