C state-machine design

Question

I am crafting a small project in mixed C and C++. I am building one small-ish state-machine at the heart of one of my worker thread.

I was wondering if you gurus on SO would share your state-machine design techniques.

NOTE: I am primarily after tried & tested implementation techniques.

UPDATED: Based on all the great input gathered on SO, I've settled on this architecture:

Answer 1

Your question is quite generic,
Here are two reference articles that might be useful,

1. Embedded State Machine Implementation

   This article describes a simple approach to implementing a state machine for an embedded system. For purposes of this article, a state machine is defined as an algorithm that can be in one of a small number of states. A state is a condition that causes a prescribed relationship of inputs to outputs, and of inputs to next states.
   A savvy reader will quickly note that the state machines described in this article are Mealy machines. A Mealy machine is a state machine where the outputs are a function of both present state and input, as opposed to a Moore machine, in which the outputs are a function only of state.

2. Coding State Machines in C and C++

   My preoccupation in this article is with state-machine fundamentals and some straightforward programming guidelines for coding state machines in C or C++. I hope that these simple techniques can become more common, so that you (and others) can readily see the state-machine structure right from the source code.

Answer 2

This series of Ars OpenForum posts about a somewhat complicated bit of control logic includes a very easy-to-follow implementation as a state machine in C.

Answer 3

State machines that I've designed before (C, not C++) have all come down to a struct array and a loop. The structure basically consists of a state and event (for lookup) and a function that returns the new state, something like:

typedef struct {
    int st;
    int ev;
    int (*fn)(void);
} tTransition;

Then you define your states and events with simple defines (the ANY ones are special markers, see below):

#define ST_ANY              -1
#define ST_INIT              0
#define ST_ERROR             1
#define ST_TERM              2
: :
#define EV_ANY              -1
#define EV_KEYPRESS       5000
#define EV_MOUSEMOVE      5001

Then you define all the functions that are called by the transitions:

static int GotKey (void) { ... };
static int FsmError (void) { ... };

All these function are written to take no variables and return the new state for the state machine. Because they all follow the same form and take no parameters, there's use made of "global" variables for information passing where necessary. This isn't as bad as it sounds since the FSM is usually locked up inside a single compilation unit and all variables are static to that unit (which is why I used quotes around "global" above - they're more shared than truly global). As with all globals, it requires care.

The transitions array then defines all possible transitions and the functions that get called for those transitions (including the catch-all last one):

tTransition trans[] = {
    { ST_INIT, EV_KEYPRESS, &GotKey},
    : :
    { ST_ANY, EV_ANY, &FsmError}
};
#define TRANS_COUNT (sizeof(trans)/sizeof(*trans))

The workings of the FSM then become a relatively simple loop:

state = ST_INIT;
while (state != ST_TERM) {
    event = GetNextEvent();
    for (i = 0; i < TRANS_COUNT; i++) {
        if ((state == trans[i].st) || (ST_ANY == trans[i].st)) {
            if ((event == trans[i].ev) || (EV_ANY == trans[i].ev)) {
                state = (trans[i].fn)();
                break;
            }
        }
    }
}

As alluded to above, note the use of ST_ANY and EV_ANY as wildcards, allowing an event to call a function no matter the current state, and guaranteeing that, if you reach the end of the transitions array, you get an error stating your FSM hasn't been built correctly.

I've used code similar for this on a great many communications projects, such as an early implementation of the OSI layered model and protocols for embedded systems. It's big advantage was its simplicity and relative ease in changing the transitions array.

I've no doubt there will be higher-level abstractions which may be more suitable nowadays but I suspect they'll all boil down to this same sort of structure.

Answer 4

The other answers are good, but a very "lightweight" implementation I've used when the state machine is very simple looks like:

enum state { ST_NEW, ST_OPEN, ST_SHIFT, ST_END };

enum state current_state = ST_NEW;

while (current_state != ST_END)
{
    input = get_input();

    switch (current_state)
    {
        case ST_NEW:
        /* Do something with input and set current_state */
        break;

        case ST_OPEN:
        /* Do something different and set current_state */
        break;

        /* ... etc ... */
    }
}

I would use this when the state machine is simple enough that the function pointer & state transition table approach is overkill. This is often useful for character-by-character or word-by-word parsing.

Answer 5

Be sure to check the work of Miro Samek (state-space blog, state-machine website, presentation, book). His articles at the C/C++ Users Journal were great.

Answer 6

I've done something similar to what paxdiablo describes, only instead of an array of state/event transitions, I set up a 2-dimensional array of function pointers, with the event value as the index of one axis and the current state value as the other. Then I just call state = state_table[event][state](params) and the right thing happens. Cells representing invalid state/event combinations get a pointer to a function that says so, of course.

Obviously, this only works if the state and event values are both contiguous ranges and start at 0 or close enough.

Answer 7

You might consider the State Machine Compiler http://smc.sourceforge.net/

This splendid open source utility accepts a description of a state machine in a simple language and compiles it to any one of a dozen or so languages - including C and C++. The utility itself is written in Java, and can be included as part of a build.

The reason to do this, rather than hand coding using GoF State pattern or any other approach, is that once your state machine is expressed as code, the underlying structure tends to disappear under the weight of boilerplate that needs to be generated to support it. Using this approach gives you an excellent separation of concerns, and you keep the structure of your state machine 'visible'. The auto-generated code goes into modules that you don't need to touch, so that you can go back and fiddle with the state machine's structure without impacting the supporting code that you have written.

Sorry, I am being over-enthusiastic, and doubtless putting everyone off. But it is a top notch utility, and well-documented too.

Answer 8

Extremely untested, but fun to code, now in a more refined version than my original answer; up-to-date versions can be found at mercurial.intuxication.org:

sm.h

#ifndef SM_ARGS
#error "SM_ARGS undefined: " \
    "use '#define SM_ARGS (void)' to get an empty argument list"
#endif

#ifndef SM_STATES
#error "SM_STATES undefined: " \
    "you must provide a list of comma-separated states"
#endif

typedef void (*sm_state) SM_ARGS;
static const sm_state SM_STATES;

#define sm_transit(STATE) ((sm_state (*) SM_ARGS)STATE)

#define sm_def(NAME) \
    static sm_state NAME ## _fn SM_ARGS; \
    static const sm_state NAME = (sm_state)NAME ## _fn; \
    static sm_state NAME ## _fn SM_ARGS

example.c

#include <stdio.h>

#define SM_ARGS (int i)
#define SM_STATES EVEN, ODD
#include "sm.h"

sm_def(EVEN)
{
    printf("even %i\n", i);
    return ODD;
}

sm_def(ODD)
{
    printf("odd  %i\n", i);
    return EVEN;
}

int main(void)
{
    int i = 0;
    sm_state state = EVEN;

    for(; i < 10; ++i)
        state = sm_transit(state)(i);

    return 0;
}

Answer 9

Saw this somewhere

#define FSM
#define STATE(x)      s_##x :
#define NEXTSTATE(x)  goto s_##x

FSM {
  STATE(x) {
    ...
    NEXTSTATE(y);
  }

  STATE(y) {
    ...
    if (x == 0)
      NEXTSTATE(y);
    else
      NEXTSTATE(x);
  }
}

Answer 10

Pardon me for breaking every rule in computer science, but a state machine is one of the few (I can count only two off hand) places where a goto statement is not only more efficent, but also makes your code cleaner and easier to read. Because goto statements are based on lables, you can name your states instead of having to keep track of a mess of numbers or use an enum. It also makes for much cleaner code since you don't need all the extra cruft of function pointers or huge switch statements and while loops. Did I mention it's more efficient too?

Here's what a state machine might look like:

void state_machine() {
first_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }

second_state:
    // Do some stuff here
    switch(some_var) {
    case 0:
        goto first_state;
    case 1:
        goto second_state;
    default:
        return;
    }
}

You get the general idea. The point is that you can implement the state machine in an efficent way and one that is relatively easy to read and screams at the reader that they are looking at a state machine. Note that if you are using goto statements, you must still be careful as it is very easy to shoot yourself in the foot while doing so.

Answer 11

The technique I like for state machines (at least ones for program control) is to use function pointers. Each state is represented by a different function. The function takes an input symbol and returns the function pointer for the next state. The central dispatch loop monitors takes the next input, feeds it to the current state, and processes the result.

The typing on it gets a little odd, since C doesn't have a way to indicate types of function pointers returning themselves, so the state functions return void*. But you can do something like this:

typedef void* (*state_handler)(input_symbol_t);
void dispatch_fsm()
{
    state_handler current = initial_handler;
    /* Let's assume returning null indicates end-of-machine */
    while (current) {
        current = current(get_input);
    }
 }

Then your individual state functions can switch on their input to process and return the appropriate value.

Answer 12

Coming to this late (as usual) but scanning the answers to date I thinks something important is missing;

I have found in my own projects that it can be very helpful to not have a function for every valid state/event combination. I do like the idea of effectively having a 2D table of states/events. But I like the table elements to be more than a simple function pointer. Instead I try to organize my design so at it's heart it comprises a bunch of simple atomic elements or actions. That way I can list those simple atomic elements at each intersection of my state/event table. The idea is that you don't have to define a mass of N squared (typically very simple) functions. Why have something so error-prone, time consuming, hard to write, hard to read, you name it ?

I also include an optional new state, and an optional function pointer for each cell in the table. The function pointer is there for those exceptional cases where you don't want to just fire off a list of atomic actions.

You know you are doing it right when you can express a lot of different functionality, just by editing your table, with no new code to write.

Answer 13

I have used State Machine Compiler in Java and Python projects to with success.

Answer 14

Simplest case

enum event_type { ET_THIS, ET_THAT };
union event_parm { uint8_t this; uint16_t that; }
static void handle_event(enum event_type event, union event_parm parm)
{
  static enum { THIS, THAT } state;
  switch (state)
  {
    case THIS:
    switch (event)
    {
      case ET_THIS:
      // Handle event.
      break;

      default:
      // Unhandled events in this state.
      break;
    }
    break;

    case THAT:
    // Handle state.
    break;
  }
}

Points: State is private, not only to the compilation unit but also to the event_handler. Special cases may be handled separately from the main switch using whatever construct deemed necessary.

More complex case

When the switch gets bigger than a couple of screens full, split it into functions that handle each state, using a state table to look up the function directly. The state is still private to the event handler. The state handler functions return the next state. If needed some events can still receive special treatment in the main event handler. I like to throw in pseudo-events for state entry and exit and perhaps state machine start:

enum state_type { THIS, THAT, FOO, NA };
enum event_type { ET_START, ET_ENTER, ET_EXIT, ET_THIS, ET_THAT, ET_WHATEVER, ET_TIMEOUT };
union event_parm { uint8_t this; uint16_t that; };
static void handle_event(enum event_type event, union event_parm parm)
{
  static enum state_type state;
  static void (* const state_handler[])(enum event_type event, union event_parm parm) = { handle_this, handle_that };
  enum state_type next_state = state_handler[state](event, parm);
  if (NA != next_state && state != next_state)
  {
    (void)state_handler[state](ET_EXIT, 0);
    state = next_state;
    (void)state_handler[state](ET_ENTER, 0);
  }
}

I am not sure if I nailed the syntax, especially regarding the array of function pointers. I have not run any of this through a compiler. Upon review, I noticed that I forgot to explicitly discard the next state when handling the pseudo events (the (void) parenthesis before the call to state_handler()). This is something that I like to do even if compilers accept the omission silently. It tells readers of the code that "yes, I did indeed mean to call the function without using the return value", and it may stop static analysis tools from warning about it. It may be idiosyncratic because I do not recall having seen anybody else doing this.

Points: adding a tiny bit of complexity (checking if the next state is different from the current), can avoid duplicated code elsewhere, because the state handler functions can enjoy the pseudo events that occur when a state is entered and left. Remember that state cannot change when handling the pseudo events, because the result of the state handler is discarded after these events. You may of course choose to modify the behaviour.

A state handler would look like so:

static enum state_type handle_this(enum event_type event, union event_parm parm)
{
  enum state_type next_state = NA;
  switch (event)
  {
    case ET_ENTER:
    // Start a timer to do whatever.
    // Do other stuff necessary when entering this state.
    break;

    case ET_WHATEVER:
    // Switch state.
    next_state = THAT;
    break;

    case ET_TIMEOUT:
    // Switch state.
    next_state = FOO;
    break;

    case ET_EXIT:
    // Stop the timer.
    // Generally clean up this state.
    break;
  }
  return next_state;
}

More complexity

When the compilation unit becomes too large (whatever you feel that is, I should say around 1000 lines), put each state handler in a separate file. When each state handler becomes longer than a couple of screens, split each event out in a separate function, similar to the way that the state switch was split. You may do this in a number of ways, separately from the state or by using a common table, or combining various schemes. Some of them have been covered here by others. Sort your tables and use binary search if speed is a requirement.

Generic programming

I should like the preprocessor to deal with issues such as sorting tables or even generating state machines from descriptions, allowing you to "write programs about programs". I believe this is what the Boost people are exploiting C++ templates for, but I find the syntax cryptic.

Two-dimensional tables

I have used state/event tables in the past but I have to say that for the simplest cases I do not find them necessary and I prefer the clarity and readability of the switch statement even if it does extend past one screen full. For more complex cases the tables quickly get out of hand as others have noted. The idioms I present here allow you to add a slew of events and states when you feel like it, without having to maintain a memory consuming table (even if it may be program memory).

Disclaimer

Special needs may render these idioms less useful, but I have found them to be very clear and maintainable.