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.

  1//
  2// Updates to types. Note that the role of guardHandler_t and effectHandler has
  3// changed. Members of these types have been added to statemachine_t. These
  4// functions are responsible for handling ALL guards and effects for this
  5// statemachine.
  6//
  7typedef bool (*guardHandler_t)(uint8_t guard);
  8typedef void (*effectHandler_t)(uint8_t effect);
  9
 10typedef struct statemachineRule_t {
 11    uint8_t trigger;
 12    uint8_t guard;
 13    uint8_t effect;
 14    uint8_t state;
 15} statemachineRule_t;
 16
 17typdef struct statemachine_t {
 18    guardHandler_t           guardHandler;
 19    effectHandler_t          effectHandler;
 20    const statemachineRule_t *pRules;
 21    const uint8_t            nrOfRules;
 22    uint8_t                  currentState;
 23}
 24
 25// Example guard and effect handler. Note that the guard handler always returns
 26// true for unknown cases. This makes the implementation of the NONE and ELSE
 27// guards trivial. It will also help if we start introducing state entry and
 28// exit functions. Note that NONE and ELSE are identical from an implementation
 29// perspective, but mean something different from intent. NONE indicates there
 30// are no conditions to be met for applying the transition. ELSE indicates the
 31// transition should be taken if all the alternative conditions are false.
 32//
 33bool guardHandler(uint8_t guard) {
 34    switch( guard ) {
 35        case gLevelIsZero : return levelIsZero();
 36        default : return true;
 37    }
 38}
 39
 40void effectHandler(uint8_t effect) {
 41    switch( effect ) {
 42        case eSetDefaultOnLevel : return setDefaultOnLevel(); break;
 43        case eTurnOff           : return turnOff()          ; break;
 44        case eDimUp             : return dimUp()            ; break;
 45        case eDimDown           : return dimDown()          ; break;
 46        case eStopDimming       : return stopDimming()      ; break;
 47        default : return true;
 48    }
 49}
 50
 51// Updates to state machine handler. effectHandler and guardHandler are now
 52// members of statemachine and are allowed to be NULL. The guards and effects
 53// are identified by a byte and fed as a parameter to these functions.
 54//
 55static void statemachine_ApplyTrigger(
 56    statemachine_t *pStatemachine,
 57    trigger_t       trigger      ) {
 58
 59    uint8_t internalState = INVALID;
 60
 61    for ( size_t i = 0u; i < pStatemachine->nrOfRules; ++i ) {
 62        statemachineRule_t rule = pStatemachine->rules[i];
 63        if ( rule.trigger == INVALID ) {
 64            internalState = rule.state;
 65            continue;
 66        }
 67
 68        if (   (internalState == pStatemachine->currentState)
 69            && (trigger == rule.trigger)
 70            && (   (pStatemachine->guardHandler == NULL)
 71                || pStatemachine->guardHandler(rule.guard)) ) {
 72        
 73            if ( pStatemachine->effectHandler ) {
 74                pStatemachine->effectHandler( rule.effect );
 75            }
 76            pStatemachine->currentState = rule.state;
 77            break;
 78        }
 79    }
 80}

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