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