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