A different approach to state machines – part 3

Last time we applied some code size optimization to our state machine implementation. In this part we improve the maintainability (and arguably readability) of the code. The code size won in the previous post came at the expense of some extra lines of source code in the form of the guard and effect handlers. Luckily, there exists a little-known pre-processor trick that can help us here: ‘X Macros’. In essence an X Macro is a function-like macro with another function-like macro as argument. The replacement token list is a list of ‘calls’ to the function-like macro with one or more ‘regular’ parameters. Are you still with me? Ok, let’s see an example:

#define EFFECTS( FUN )       \
    FUN( SetDefaultOnLevel ) \
    FUN( TurnOff )           \
    FUN( DimUp )             \
    FUN( DimDown )           \
    FUN( StopDimming )

// add 'e' prefix to the effect name
#define ENUM_ITEM( item ) e##item,

// create a function prototype from the effect name with prefix 'handle'
#define PROTOTYPE_ITEM( item ) static void handle##item(void);

// create a case statement for effect in which the corresponding function
// is called
#define CASE_ITEM( item ) case e##item : handle##item(); break;

// effects enumeration
enum {
    EFFECTS( ENUM_ITEM )
};

// effects function prototypes
EFFECTS( PROTOTYPE_ITEM )

// effect handler implementation
static void effectHandler(uint8_t effect) {
    switch( effect ) {
        EFFECTS( CASE_ITEM )
        default :
            break;
    }
}

Which expands to (layout adjusted for clarity):

// effects enumeration
enum {
    eSetDefaultOnLevel,
    eTurnOff          ,
    eDimUp            ,
    eDimDown          ,
    eStopDimming      , // I love how C99 allows this!
};

// effects function prototypes
static void handleSetDefaultOnLevel(void);
static void handleTurnOff(void);
static void handleDimUp(void);
static void handleDimDown(void);
static void handleStopDimming(void);

// effect handler implementation
static void effectHandler(uint8_t effect) {
    switch( effect ) {
        case eSetDefaultOnLevel : handleSetDefaultOnLevel(); break;
        case eTurnOff           : handleTurnOff()          ; break;
        case eDimUp             : handleDimUp()            ; break;
        case eDimDown           : handleDimDown()          ; break;
        case eStopDimming       : handleStopDimming()      ; break;
        default :
            break;
    }
}

The ENUM_ITEM, PROTOTYPE_ITEM and CASE_ITEM macros can be factored out in a separate file, which can be reused for multiple state machines. Note how we only need to add one line to the effects macro to add an effect, versus adding an enumeration, a function prototype and a case statement! The lines of code could be further reduced by factoring out the standard implementation of the effectHandler function, but I prefer to leave some clues about what is going on with all these macros. I feel their usage in this specific case pays off. Just make sure you do not go overboard with nasty pre-processor tricks; they can be notoriously hard to read and debug. The complete sources can be downloaded from statemachine_part3.zip

A different approach to state machines – part 2

In the last part we looked at a different approach for implementing state machines. In this part we will refine the implementation with the goal descrease the code size. In this post, I discussed the advantage of using a switch statement over writing a jumptable yourself. Applying this to the statemachine implementation decreases the code size by replacing ‘costly’ function pointers with bytes. A further descrease is possible since the compiler can reduce the number of ‘actual’ (non-inlined) functions. The guard and effect functions will each be replaced by a single function containing a switch statement to select the correct guard/effect.

//
// Updates to types. Note that the role of guardHandler_t and effectHandler has
// changed. Members of these types have been added to statemachine_t. These
// functions are responsible for handling ALL guards and effects for this
// statemachine.
//
typedef bool (*guardHandler_t)(uint8_t guard);
typedef void (*effectHandler_t)(uint8_t effect);

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

typdef struct statemachine_t {
    guardHandler_t           guardHandler;
    effectHandler_t          effectHandler;
    const statemachineRule_t *pRules;
    const uint8_t            nrOfRules;
    uint8_t                  currentState;
}

// Example guard and effect handler. Note that the guard handler always returns
// true for unknown cases. This makes the implementation of the NONE and ELSE
// guards trivial. It will also help if we start introducing state entry and
// exit functions. Note that NONE and ELSE are identical from an implementation
// perspective, but mean something different from intent. NONE indicates there
// are no conditions to be met for applying the transition. ELSE indicates the
// transition should be taken if all the alternative conditions are false.
//
bool guardHandler(uint8_t guard) {
    switch( guard ) {
        case gLevelIsZero : return levelIsZero();
        default : return true;
    }
}

void effectHandler(uint8_t effect) {
    switch( effect ) {
        case eSetDefaultOnLevel : return setDefaultOnLevel(); break;
        case eTurnOff           : return turnOff()          ; break;
        case eDimUp             : return dimUp()            ; break;
        case eDimDown           : return dimDown()          ; break;
        case eStopDimming       : return stopDimming()      ; break;
        default : return true;
    }
}

// Updates to state machine handler. effectHandler and guardHandler are now
// members of statemachine and are allowed to be NULL. The guards and effects
// are identified by a byte and fed as a parameter to these functions.
//
static void statemachine_ApplyTrigger(
    statemachine_t *pStatemachine,
    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)
            && (   (pStatemachine->guardHandler == NULL)
                || pStatemachine->guardHandler(rule.guard)) ) {
        
            if ( pStatemachine->effectHandler ) {
                pStatemachine->effectHandler( rule.effect );
            }
            pStatemachine->currentState = rule.state;
            break;
        }
    }
}

As with the previous post you can find a complete compileable example here. A quick test with ‘gcc’ and ‘size’ shows a code size decrease of roughly 500 bytes on my machine which is 10% of the complete code size. Pretty spectacular if you consider the complete code already contains quite some overhead by linking to standard libraries. I will provide some more in depth analysis on code size when we proceed refining the implementation in the next part of this series.

$ gcc -o statemachine_part1 statemachine_part1.c -Os -std=c99
$ gcc -o statemachine_part2 statemachine_part2.c -Os -std=c99

$ size statemachine_part1 
   text    data     bss     dec     hex filename
   4561    2132     480    7173    1c05 statemachine_part1

$ size statemachine_part2 
   text    data     bss     dec     hex filename
   4081    2132     480    6693    1a25 statemachine_part2

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