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:

typedef bool_t (*guardHandler_t)(void);
typedef void (*effectHandler_t)(void);

typedef struct statemachineRule_t {
    uint8_t         trigger;
    guardHandler_t  guard;
    effectHandler_t effect;
    uint8_t         state;
} statemachineRule_t;

#define INVALID 0xFFu
#define STATE( s ) { INVALID, NULL, NULL, s }

enum states {
    sOff    ,
    sOn     ,
    sDimming
};

enum triggers {
    tPressOn    ,
    tPressOff   ,
    tPressUp    ,
    tPressDown  ,
    tReleaseUp  ,
    tReleaseDown
};

const stateMachineRule_t rules[] =
{
//    trigger     , guard       , effect            , next state
STATE( sOff ),
    { tPressOn    , NONE        , eSetDefaultOnLevel, sOn        },
STATE( sOn ),
    { tPressOff   , NONE        , eTurnOff          , sOff       },
    { tPressUp    , NONE        , eDimUp            , sDimming   },
    { tPressDown  , NONE        , eDimDown          , sDimming   },
STATE( sDimming ),
    { tPressOff   , NONE        , eTurnOff          , sOff       },
    { tReleaseUp  , NONE        , eStopDimming      , sOn        },
    { tReleaseDown, gLevelIsZero, eStopDimming      , sOff       },
    { tReleaseDown, ELSE        , eStopDimming      , sOn        }
}

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.

typedef struct statemachine_t {
    const stateMachineRule_t rules[];
    const uint8_t            nrOfRules;
    uint8_t                  currentState;
} statemachine_t;


void ProcessTrigger(
    stateMachine_t  *pStateMachine,
    const trigger_t trigger       ) {

    uint8_t internalState = INVALID;

    for ( size_t i = 0u; i < pStateMachine->nrOfRules; ++i ) {
        stateMachineRule_t rule = pStateMachine->rules[i];
        if ( rule.trigger == INVALID ) {
            internalState = rule.state;
            continue;
        }

        if (   (internalState == pStateMachine->currentState)
            && (trigger == rule.trigger)
            && rule.guard() ) {
        
            rule.effect();
            pStateMachine->currentState = rule.state;
            break;
        }
    }
}

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 al