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 FSMs which is efficient, easier to read, maintain and scale up.

In case you are not familiar with FSMs and their applications, all I can say for now is that FSMs are a very nice way to write non-blocking code on a single-threaded or single-tasking environment (such as a microcontroller)! Wikipedia has some good explanation on what are them and how/why to use FSMs.

The traditional approach when it comes to writing an FSM is usually something like this (considering an FSM to blink an LED):

While this approach works just fine, it gets harder to read and maintain once the FSMs scales up: intermediate states (which shouldn’t need to get exposed to external code) have to be created and maintained (usually by using enumerations). The enumeration for our simple FSM would be something like:

Really, why do we need those intermediate states (highlighted)?

What is even worse is that a slightly more complex FSM will usually have a lot more intermediate states!

It is also worth mentioning that all states are exposed to the application thus making a direct call like myLEDFSM(STATE_ON_WAIT) possible (while usually not desirable and potentially catastrophic).

There must be another way to write readable and maintainable FSMs!

My inspiration for the idea I present on this article came from Coroutines: a special case of a subroutine which can have not only multiple exit points, but multiple entry points as well (subroutines traditionally sport only a single entry point and can have multiple exit points). Along with multiple entry points, Coroutines also include facilities to suspend and resume their execution state making them a nice way to implement cooperative multitasking!

But (yeah, there is always a but) Coroutines are not supported natively by C language, that is only possible by using third-party libraries which can add a lot more code then we really want here.

Anyway, the idea is to create a function (subroutine) which is gonna store all FSM states and that can jump internally to any state without using switch statements. How can we do that? Pointers to the rescue!

Yes, pointers. They are one of the major strengths of C and also the source of most bugs and headaches for programmers. Since they are so powerful, maybe there is a way to use them to create our “switchless” FSM?

Of course there is! But we will need the help of another fairly misunderstood command: goto! What? First pointers now goto? Are you kidding me?

Relax dear reader, I understand that for lots of people, goto is archaic statement which has almost no use on modern programming techniques but believe me, goto is your friend and so are pointers! We just need to understand how to use them properly!

Implementation

Our implementation is pretty straightforward: a local variable is used to store our state (actually the entry-point for the desired state). In the beginning of our FSM we jump, using goto, to the address pointed to by the variable!

In order to prevent it from jumping to a null address, we add some logic that tests against null, so that we only jump if the variable is not null, otherwise execution proceeds. This test also has a welcome side-effect: by setting the local control variable to null we can force the FSM to reset and run the initialization code!

There are three macros to handle FSM operation. The first one is FSM_START. It handles jumping to the desired state or proceeding with the FSM init code. Note that this macro also creates and initializes a local static variable (jumper) which stores current “state” (actually it stores the return address, which in this case is equivalent to FSM state):

The next piece and core of our FSM code is the FSM_YIELD macro:

Note that FSM_YIELD stores the desired next state of the FSM and returns. That means you always yield to the next state you want to run (and it could be even the current state) and return execution flow to the caller. Does it sound familiar? Of course it does! This is light-weight cooperative multitasking!

Finally we have another macro to reset the FSM:

It sets the local control variable to null, forcing the FSM to run its initialization code next time it is called.

Usage

Now that we saw the basics of how this implementation works, let’s rewrite the LED FSM using the new method:

Note that if we do not need to return current state, its code is even simpler:

Before anything else, I need to say that no, this code does not perform exactly like the one with switch statement, this is because our new method only exposes two possible states to the application: STATE_DUMMY and STATE_ON, if we call myLEDFSM with any other state as a parameter it defaults to LED_IDLE which turns LED off and resets the FSM, keeping it into the idle (off) state.

Of course that means our enumeration now can be as simple as:

Because this method does not use a computed goto or a branch table, it should be almost as efficient as switch for small FSMs and maybe even more efficient than the later for FSMs with several states. On the other hand, if your FSM has several exposed states which can be controlled externally then maybe this method is not for you.

I’ve been using this method to write FSMs to handle communication protocols and it made my life much easier than using long switch constructions to handle several intermediate states.

That’s it for now, stay tuned because next time I will show a real-world application of this method! And if you have any comment or suggestion, feel free to post it here!

An Alternate Way to Write State Machines (FSM)
Tagged on:             

Leave a Reply