State machine in C

Most of simple microcontroller applications can be modelled through finite-state machine (FSM). This is a simple and powerful approach. Now the question is “how should I implement it?”.

Using an object oriented language like C++ usually lead to the implementation of the state pattern. I had to implement it using C for an MSP430 microcontroller.

Searching the web for FSM implementation gives lot of results that usually target the hardware engineers, VHDL and synthesis and optimization.

The naive implementation is to use a switch statement and implement the logic of the states in it. You can easily implement such Mealy or Moore FSM.

The problem with that approach is that as the FSM becomes more and more complicated (and it always does…), it becomes a nightmare to debug and to modify it.

A more elegant way

Using a transition table and matrix in C is another option. There are a couple of thread on stackoverflow about that. I’ve also found this nice post about transition table using array in C approach.

Using this method allows you to have a state machine “manager” code that doesn’t change, all you have to do is create the matrix and implement the actions. The only change that I have done is to switch the index of EVENTS and STATES in the array, because usually you have a fixed number of EVENTS and a variable and always increasing number of STATES, so the 2D array grows vertically.

typedef enum STATE
{
	STATE_A,
	STATE_B,
	STATE_C,
	STATE_D,
	STATES_COUNT
} STATE;

typedef enum EVENT
{
	EVENT_1,
	EVENT_2,
	EVENT_3,
	EVENT_START,
	EVENT_TIMEOUT,
	EVENTS_COUNT
} EVENT;

typedef void (*TPF)();

typedef struct TRANSITION
{
	STATE next_state;
	TPF action;
} TRANSITION;

extern TRANSITION transition_table[ STATES_COUNT ][ EVENTS_COUNT ];
TRANSITION transition_table[ STATES_COUNT ][ EVENTS_COUNT ] = { ... }

The core of the program moves the FSM through the transition table processing the events and performing the relative actions.

	/* process all the occurred events */
	while ( !vStackIsEmpty( g_pEventStack ) )
	{
		EVENT event = (EVENT) vStackPop( g_pEventStack );

		transition_table[ state ][ event ].action();
		state = transition_table[ state ][ event ].next_state;
	}

The g_pEventStack is a global variable of an event stack. In the best case the stack is filled from the interrupts as the events occur. In the worst case you have have an event that require polling, so it is up to you to monitor the event and push an event on the stack every time the polled signal change. Of course the stack implementation must take in account that you can have racing conditions.

Automatic code generation for FSM

Now this is a pretty powerful implementation, but working with a transition table matrix is also error prone. Is there something that can help with that?

Of course.. Doing some research I have found a powerful tool, a state machine compiler (scm). Starting from a description language of the FSM it can generate the source code for many different languages. I’ve spent some time with it and it can be really powerful. The description of the state machine can be generated from graphical tools, like qfsm. My problem is that I find the generated code not so clean, and I want to have the complete control over the source code that I compile, so I’ve dumped that solution, even if I think that is really useful, and I could use it on a more complex project.

The good news is that qfsm is a simple and nice project and it can generate transition tables!

qfsm example
qfsm example

This is the corresponding output:

"States/Events";" EVENT_1";" EVENT_2";" EVENT_4";" EVENT_TIMEOUT"
A;"B action_x";"-";"-";"-"
B;"-";"C action_z";"B dummy";"A action_y"
C;"A action_y";"-";"-";"-"

Now using a script file with some awk commands it is quite easy to generate an .h and .c files with the enums for states and events, the transition matrix and even helper functions to print the text of the current state and event, based on the enum, which can be really helpful during debug…

The actions prototypes are generated using the extern directive:

extern void action_x();
extern void action_y();
extern void action_z();

In this way if you modify the FSM, adding a new action and forget to implement it in the code, the linker will complain about the missing method!

So, every time you want to change the behaviour of your application you do it graphically, you regenerate the source files and compile it. That’s it!

2 thoughts on “State machine in C

    1. I never played with it. I’ve read about it a long time ago. I find fascinating and powerful the idea, but honestly I tend to be skeptical with new revolutionary solutions that will solve all your problems… But I’m open and ready to be surprised if it is the case.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.