Those of you who have read my blog for a while have seen my posts on the tool Stateflow by The MathWorks, such as the Tips for Readability and the Stateflow Best Practices document on which much of the MathWorks documentation is based. Today I wanted to do something different, dive into State machines at a basic level through a C code example
Starting Simple
We will start with a simple 3 State example, A, B & C, where A is the “Default State”, and there are valid transitions between all 3 states. Further we will treat the State machine function as a “Stateless” function, meaning that all data will be passed into the function.
First, the simplest representation of this in C for clarity of the example
The Statemachine function evaluates the held “current state” of the machine and, following an if / else if structure, flows down to the currently active state.
Once the active state is reached it first checks to see if this is the first time in the state (stateA.isFirst). If so, it performs “entry actions” and sets the entry time (in case there are temporal actions)
Next, it performs any actions associated with the active state, which could be a calculation or calling a sub-function.
Once all these actions are complete, the function checks for exits. If an exit condition exists, it updates the current state and last state variables.
The First Efficiency
The first optimisation is to think about “what is active most of the time. In the current example, we have only three top-level states, so a low number of evaluations are performed. But if at each level we had 10 states, then ordering the states in terms of the percentage time they are active makes sense.
E.g. if in our case
- A : Active 20%
- B : Active 70%
- C : Active 10%
Then the If / Else If tree should be ordered B, A, C.
NOTE: The order of evaluation of the exit conditions should be set based on the precident of the exit, e.g. if two exits could be true at the same time the statemachine designer needs to determine which ‘goes first’
The Data and Children
In this first example we have just one level of states, no child states; this can be easily extended following our pattern.
First the data:
In our current implimentation a simple structure is used: For now we will expand this data structure with a small modification, in the next section we will consider memory optimizations.
Initial
The issue with this approach is fairly clear, while the pattern is easy to follow, you could end up with multiple “twoChild”, “threeChild”,…”nChild” structures following this pattern, further it does not support unique ‘local data’ constructs.
Updated
Child Patterns
The pattern used in the initial code is now extended to the child states
Cyclomatic complexity: Testing the Machine
A quick look a the code above shows how quickly the number of independent branches grow, leading to a high cyclomatic complexity score.
The solution is to limit the depth of the children: As a general rule of thumb, IF logic more then 3 levels deep quickly becomes difficult to maintain. This is done either by re-factoring the state logic into multiple machines, or creating sub-state machine functions that can be indepdendently validated.
Data Efficency versus Clarity
The final topic is on data efficency versus clarity; there are two issues with the current implimentation of the state structure
- Inactive data: Within any state structure only one “state and children” will be active at any time. This means that the data associated with all of the other states is not active and could be colapsed
- Data structure alignment: The “easy to read” version of the array structure can result in alignment issues, e.g. when you are switch between different sized variables
Solution 1: “Common Data”
There are 4 types of data in use
- Current State: This can be changed to a single array of size N, where N is the max depth of the state chart. This requires book keeping to know the “depth” of the child.
- Last State: Like current state this can be changed to a single array size N
- First time in: This can be changed to a uint32 and then using bit logic on the state number to determine if it is the first time in or not
- Local data: The maximum number of floats, doubles, integers used by the state machine can be determined and then a single instance is created.
With the exception of local data there is no impact on the clarity of the code. Because of this thelocal data should be fully commented.
Solution 2: Alignment:
When you follow the approach of #1 you can quickly perform the alignment tasks on the structure.
