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