Hello World,

This post discusses how to program a state machine with the C programming language.  The techniques shown here are specific to C.  Why C you may ask?  State machines are frequently used in simple embedded systems without an operating system.  This is a niche that C fills quite nicely.

First, why I am I writing this?  I was inspired by this post on Stack Overflow asking if there was a typical state machine implementation pattern with C.  I have implemented a few state machines in the past, and thought I would share my thoughts on the pro’s and con’s of various implementations.  The thoughts presented here are based mainly on software engineering perspective.  So readability, and maintainability, will be given primary consideration.  Some consideration will also be given to efficiency of storage and operations.

Some other information about writing state machines in C is here:

Coding State Machines in C and C++

A common implementation is the switch statement.  Given that it is provided by the language, it used often.  It would look something like:

Example of state machine using switch statement

void StateMachine( struct StateMachineOutput* out
                 , const struct StateMachineInput* in)
{
  static StateMachineStateEnum state;

  switch (state)
  {
    case STATE_1:
      // do something
      state = STATE_2;
      break;

    case STATE_2:
      // do something
      state = STATE_1;
      break;
  }
}

The advantages to a switch based implementation are:

• Simplicity
• Well documented by the C language
• Static variables are within function scope, so they are available to all states

The disadvantages to a switch based implementation are:

• No control over how the switch is implemented by compiler.
• Does not enforce separation of states.

For a small state machine, the switch is often the ideal choice.  If the enumerations of state and the entire function can fit on a computer monitor (assuming “normal” operating conditions), then the switch statement is often the best implementation (or at least the best first implementation).

However, be aware that it is not up to the programmer how the switch is implemented by the compiler, so it may be generate non-optimal machine code.  For example, there is no guarantee (AFAIK) the order in which the the cases will be evaluated.  Therefore, even if you order your state machine carefully, by putting common states at the first cases followed by less common states, the compiler may chose to evaluate in a different order.  Also, because the variables defined within the function outside the switch can be accessed by all states, there is a potential for unwanted side effects.  Conceptually, it is good to thing of all variables existing in the function, but defined outside the switch body to be the ‘state’ [1].  In this situation, there is not a single variable or structure that is the state, but rather the variables as a whole represent the state.  Variables used in only a single state should be restricted in scope by using braces.  For example:

void StateMachine( struct StateMachineOutput* out
                 , const struct StateMachineInput* in)
{
  static StateMachineStateEnum state;
  int aValue; // note, this is also part of the 'state'

  switch (state)
  {
    case STATE_1:
    {
      int i = 0;
      // do something with i
      state = STATE_2;
    } break;

    case STATE_2:
    {
      // do something
      state = STATE_1;
    } break;
  }
}

A state machine can also be implemented using a look-up table of state functions, along with a state machine function.  For example:

enum StateMachineStateEnum
{
  STATE_1,
  STATE_2,
};

// all state functions have this signature
typedef StateMachineStateEnum (*StateMachineFunction)( struct StateMachineOutput* out
                                                     , const struct StateMachineInput* in)

StateMachineStateEnum StateFunction1( struct StateMachineOutput* out
                                    , const struct StateMachineInput* in)
{
  // do something
  return STATE_2;
}

StateMachineStateEnum StateFunction2( struct StateMachineOutput* out
                                    , const struct StateMachineInput* in)
{
  // do something
  return STATE_1;
}

void StateMachine( struct StateMachineOutput* out
                 , const struct StateMachineInput* in)
{
  static StateMachineStateEnum state = STATE_1;

  // define state functions array in same order as enum
  static StateMachineFunction functions[] =
  {
    StateFunction1,
    StateFunction2
  };

  // call the state function
  state = functions[state](out, in);
}

Some advantages to the table based approach are:

• Clear separation of states.

What do we want from a state machine?

Before continuing with the discussion of state machines, I’ll cover some “typical” needs of a state machine written with C for an embedded system.

• Clear separation of states.
• Minimal overhead in calling state functions.
• State functions that can be made re-entrant.
• Flexibility in memory management.

From a software engineering perspective, we would like a clearly defined between each state.  This includes a separate scope for each states’ local variables.

Designing a state machine

Here are some considerations when designing a state machine in C.  First, don’t over-design.

Create states boundaries when you have to wait for something.  This something might be a register value, or possibly another variable.  When creating a state machine, the state functions should not be blocking.

Instead of a switch statement, or a look-up table, it is possible to implement a state machine with function pointers and a state structure.

Foot notes:

[1] IMHO, with C, many design patterns are implicit rather than explicit.  You often have to ‘read between the lines’, for better or worse.