A different approach to state machines

Especially useful for embedded control systems, state machines are an intuitive and effective tool for design and documentation. In this post I am going to describe an approach to implementing state machines I came up with a couple of years ago. Shortly after, I discovered very similar ideas have been in use in the industry for quite some time. Still, the approach does not seem to be commonly known. This is a real shame; the proposed implementation of state machines can lead to a roughly 2.5 times smaller code size, while being extremely easy to read and maintain.

Readability is actually the starting point of this exercise. What if we could just execute our state machine design? As an example we will use the state diagram below. I use hungarian notation to differentiate (s)tates, (t)riggers, (g)uards and (e)ffects. This will become more helpful once we refine the state machine implementation later on [1].

statemachine

Jotting down circles and arrows is not very convenient in text [2], but state machines can be easily expressed in text as well, see below.

sOff :
    tPressOn                    / eSetDefaultOnLevel -> sOn
sOn :
    tPressOff                   / eTurnOff           -> sOff
    tPressUp                    / eDimUp             -> sDimming
    tPressDown                  / eDimDown           -> sDimming
sDimming :
    tPressOff                   / eTurnOff           -> sOff
    tReleaseUp                  / eStopDimming       -> sOn
    tReleaseDown [gLevelIsZero] / eStopDimming       -> sOff
    tReleaseDown [gELSE]        / eStopDimming       -> sOn

Theoretically, we could already write this format as a multi-line string in a source file, parse and interpret it. This, however, would be very inefficient in terms of code size and execution speed. As an alternative write the state machine in tabular format as an array of structs:

  1typedef bool_t (*guardHandler_t)(void);
  2typedef void (*effectHandler_t)(void);
  3
  4typedef struct statemachineRule_t {
  5    uint8_t         trigger;
  6    guardHandler_t  guard;
  7    effectHandler_t effect;
  8    uint8_t         state;
  9} statemachineRule_t;
 10
 11#define INVALID 0xFFu
 12#define STATE( s ) { INVALID, NULL, NULL, s }
 13
 14enum states {
 15    sOff    ,
 16    sOn     ,
 17    sDimming
 18};
 19
 20enum triggers {
 21    tPressOn    ,
 22    tPressOff   ,
 23    tPressUp    ,
 24    tPressDown  ,
 25    tReleaseUp  ,
 26    tReleaseDown
 27};
 28
 29const stateMachineRule_t rules[] =
 30{
 31//    trigger     , guard       , effect            , next state
 32STATE( sOff ),
 33    { tPressOn    , NONE        , eSetDefaultOnLevel, sOn        },
 34STATE( sOn ),
 35    { tPressOff   , NONE        , eTurnOff          , sOff       },
 36    { tPressUp    , NONE        , eDimUp            , sDimming   },
 37    { tPressDown  , NONE        , eDimDown          , sDimming   },
 38STATE( sDimming ),
 39    { tPressOff   , NONE        , eTurnOff          , sOff       },
 40    { tReleaseUp  , NONE        , eStopDimming      , sOn        },
 41    { tReleaseDown, gLevelIsZero, eStopDimming      , sOff       },
 42    { tReleaseDown, ELSE        , eStopDimming      , sOn        }
 43}

Note how close the implementation is to the original design! There is one things left to do; implement the engine for the state machine. Luckily, this is surprisingly simple for this first iteration.

  1typedef struct statemachine_t {
  2    const stateMachineRule_t rules[];
  3    const uint8_t            nrOfRules;
  4    uint8_t                  currentState;
  5} statemachine_t;
  6
  7
  8void ProcessTrigger(
  9    stateMachine_t  *pStateMachine,
 10    const trigger_t trigger       ) {
 11
 12    uint8_t internalState = INVALID;
 13
 14    for ( size_t i = 0u; i < pStateMachine->nrOfRules; ++i ) {
 15        stateMachineRule_t rule = pStateMachine->rules[i];
 16        if ( rule.trigger == INVALID ) {
 17            internalState = rule.state;
 18            continue;
 19        }
 20
 21        if (   (internalState == pStateMachine->currentState)
 22            && (trigger == rule.trigger)
 23            && rule.guard() ) {
 24        
 25            rule.effect();
 26            pStateMachine->currentState = rule.state;
 27            break;
 28        }
 29    }
 30}

I left out some minor details such as the guard and effects functions. Here is a completely self contained .c file that can be compiled into an executable example. In practice you will want to put the state machine engine definitions and implementation in a separate component. This is one of the refinements we will make in a next post.


1. I usually avoid Hungarian notation for indicating types. Here, however, it serves a dual purpose. The descriptive names of state, triggers, guards and effects are likely to clash with existing function or variable names. The prefix prevents most of the clashes. It also allows the reader to differentiate between the types without verbose descriptive names.