[Paid] STM32 Embedded Resource Package
The implementation of a state machine essentially involves three elements: state, event, and response. This translates into three questions regarding specific behaviors.
- What happened?
- What state is the system currently in?
- In this state, given this event, what should the system do?
There are mainly three methods to implement a state machine in C language: switch-case method, table-driven method, and function pointer method.
Switch-Case Method
The states are organized using switch-case, and the events are also organized using switch-case. Then, one switch-case is inserted into each case of another switch-case.“Program Listing 4:”
switch(StateVal){case S0:switch(EvntID) {case E1: action_S0_E1(); /*Response to event E1 in state S0*/ StateVal = new state value;/*State transition, if not transitioning, this line is unnecessary*/break;case E2: action_S0_E2(); /*Response to event E2 in state S0*/ StateVal = new state value;break; ......case Em: action_S0_Em(); /*Response to event Em in state S0*/ StateVal = new state value;break;default:break; }break;case S1: ......break; ......case Sn: ......break;default:break;}The above pseudo-code example is just a general case; actual applications are far less complex. Although there may be many types of events in a system, many events may not be meaningful for a certain state in practical applications.For example, in Program Listing 4, if E2, …, Em are not meaningful for the system in state S0, then the code related to events E2, …, Em in the case of S0 is unnecessary; state S0 only needs to consider the handling of event E1.Since there is a nesting issue between the two switch-cases, there are two writing styles for the switch-case method: state nested within events and events nested within states. Both styles are valid, each with its pros and cons, and the choice of which to use is left to the designer based on specific circumstances.One last point to note about the switch-case method is that because the principle of switch-case is to compare from top to bottom, the further down it is, the longer the lookup time. Therefore, attention should be paid to the arrangement order of states and events in their respective switch statements. It is not recommended to arrange them in sequential order as in Program Listing 4. States and events that occur frequently or have high real-time requirements should be placed as early as possible.
Table-Driven Method
If the switch-case method is linear, then the table-driven method is planar. The essence of the table-driven method is to solidify the relationship between states and events into a two-dimensional table, treating events as the vertical axis and states as the horizontal axis. The intersection [Sn, Em] represents the system’s response to event Em when in state Sn.
As shown in Figure 4, I refer to the node in the table as the state machine node. The state machine node Node_SnEm is the system’s response to event Em when in state Sn. The response mentioned here includes two aspects: output actions and state transitions. The state machine node is generally a structure variable similar to that in Program Listing 5.
struct fsm_node{void (*fpAction)(void* pEvnt); INT8U u8NxtStat;};This structure in Program Listing 5 has two members: fpAction and u8NxtStat. fpAction is a function pointer that points to a function with the form void func(void * pEvnt), which standardizes the encapsulation of the action sequence during state transitions.In other words, when the state machine transitions states, regardless of how many actions are output, how many variables are manipulated, or how many functions are called, all these behaviors are handled within the function func.Once the actions are encapsulated, the address of the encapsulated function func is assigned to the function pointer fpAction, so that to output actions, one only needs to call the function pointer fpAction.Looking at the above func function, we find that it has a parameter pEvnt, which is a pointer of type void *. During actual program execution, it points to a variable that can store event information. Through this pointer, we can know all the information about the event, making this parameter very necessary. Events generally include two attributes: the type of event and the content of the event.For example, in a key press event, we not only need to know that it is a key press event, but also which key was pressed. The type of event and the current state of the state machine allow us to quickly locate in the table in Figure 4 and determine which action encapsulation function to call. However, to correctly respond to the event, the action encapsulation function also needs to know what the content of the event is, which is the significance of the parameter pEvnt.Due to the diversity of events, the data format for storing event content may vary, so pEvnt is defined as void * to increase flexibility. Regarding the last question about fpAction: if event Em is not meaningful for state Sn, what should the fpAction in the state machine node Node_SnEm point to? My answer is: let it point to a null function! As mentioned earlier, doing nothing is also a response.u8NxtStat stores a state value of the state machine. We know that the state machine responds to events by outputting actions, which means calling the encapsulated function pointed to by the function pointer fpAction. Once the function call is completed, the program returns to the calling function, and the state machine’s response to the event is considered complete. The next step is to consider the state transition.It may either remain in the current state or transition to a new state. How to decide? The state stored in u8NxtStat is the answer the state machine wants!The table in Figure 4 is reflected in C language code as a two-dimensional array, where the first dimension is the state of the state machine and the second dimension is the uniformly classified events, and the elements of the array are the structure constants from Program Listing 5. If the program uses the table-driven method, there are some special considerations. To treat states as the horizontal axis of the table, the set of state values must meet the following conditions:(1) The set is an increasing arithmetic integer sequence.(2) The initial value of the sequence is 0.(3) The common difference of the sequence is 1.“Events” as the vertical axis have characteristics and requirements that are completely consistent with those of the “states” used as the horizontal axis. Among the data types provided by C language, there is no option more suitable than enumeration to meet the above requirements. It is highly recommended to make the set of states and the set of event types into enumeration constants. The advantages of the table-driven method include: unified calling interface and quick positioning.The table-driven method masks the differences in handling various events under different states, allowing the common parts of the processing process to be extracted and made into standardized framework code, forming a unified calling interface. Based on the state machine node structure from Program Listing 5, the framework code is shown in Program Listing 6.The lookup target in the table-driven method is essentially a two-dimensional array addressing operation, so its average efficiency is much higher than that of the switch-case method.“Program Listing 6:”
extern struct fsm_node g_arFsmDrvTbl[][]; /*State machine driving table*/INT8U u8CurStat = 0; /*Current state temporary storage*/INT8U u8EvntTyp = 0; /*Event type temporary storage*/void* pEvnt = NULL; /*Event variable address temporary storage*/struct fsm_node stNodeTmp = {NULL, 0}; /*State machine node temporary storage*/u8CurStat = get_cur_state(); /*Read current state*/u8EvntTyp = get_cur_evnt_typ(); /*Read current triggered event type*/pEvnt = (void*)get_cur_evnt_ptr(); /*Read event variable address*/stNodeTmp = g_arFsmDrvTbl[u8CurStat ][u8EvntTyp ];/*Locate state machine node*/stNodeTmp.fpAction(pEvnt ); /*Action response*/set_cur_state(stNodeTmp.u8NxtStat); /*State transition*/.....While the table-driven method has its advantages, there are still some minor issues with programs written using it. Let’s first look at the characteristics of programs written using the table-driven method. As mentioned earlier, the table-driven method can standardize the state machine scheduling part into framework code that is highly applicable. Regardless of what kind of application the state machine is used to implement, the framework code does not need to be modified; we only need to plan the state transition diagram according to the actual application scenario and implement the various elements (states, events, actions, transitions, and the “conditions” element will be discussed later) in code. I refer to this part of the code as application code.In the application code’s .c file, you will see a two-dimensional array declared as const, which is the state driving table shown in Figure 4, and many unrelated functions, which are the action encapsulation functions mentioned earlier. Such a code, if one does not have a state transition diagram at hand, will leave anyone confused; this format directly leads to poor code readability.If we want to add a state to the state machine, it would mean adding a column to the driving table and also adding several action encapsulation functions. If the driving table is large, this work can be quite tedious and prone to errors. If one accidentally fills in the wrong position in the array, the program will run contrary to the designer’s intentions.It is far less convenient and safe than making changes in the switch-case method. The Extended State Machine’s greatest feature is that it first checks conditions before responding to events, and based on the evaluation results, it decides which actions to execute and which state to transition to.In other words, when an event Em occurs in state Sn, the state to transition to is not necessarily unique. This flexibility is the most valuable advantage of the Extended State Machine.Looking back at the state machine node structure provided in Program Listing 5, if an event Em occurs in state Sn, after executing the actions specified by fpAction, the state machine must transition to the state specified by u8NxtStat.This characteristic of the table-driven method directly eliminates the possibility of applying the Extended State Machine in the table-driven method, so there is no “condition” element in the code implementation of the table-driven method. ESM, you are so excellent, how can I bear to abandon you?!Now, looking at the example in Figure 4 of the table-driven method, if we remove the vertical axis representing events from the table and merge a column into a cell, can the problems mentioned earlier be resolved? Indeed! This is the long-lost “Kua Hua Bao Dian” — the truncated version of the table-driven method!!The truncated table-driven method, also known as the compressed table-driven method, is a combination of a one-dimensional state table and event switch-case. The compressed table-driven method uses a one-dimensional array as the driving table, where the array index represents the various states of the state machine.The elements in the table are called compressed state machine nodes, and the main content of the nodes is still a function pointer pointing to the action encapsulation function, except that this action encapsulation function is not prepared for a specific event but is valid for all events.The node no longer enforces the state to transition to after the output action is completed; instead, it allows the action encapsulation function to return a state, which becomes the new state of the state machine.This characteristic of the compressed table-driven method perfectly solves the problem of the Extended State Machine not being usable in the table-driven method.Program Listing 7 contains the example code for the compressed state machine node structure and the framework code for calling the state machine.“Program Listing 7:”
struct fsm_node /*Compressed state machine node structure*/{ INT8U (*fpAction)(void* pEvnt); /*Event handling function pointer*/ INT8U u8StatChk; /*State check*/};......u8CurStat = get_cur_state(); /*Read current state*/......if(stNodeTmp.u8StatChk == u8CurStat ){ u8CurStat = stNodeTmp.fpAction(pEvnt ); /*Event handling*/ set_cur_state(u8CurStat ); /*State transition*/}else{ state_crash(u8CurStat ); /*Illegal state handling*/}.....Comparing with Program Listing 5, we can see the changes in the struct fsm_node structure in Program Listing 7. First, the function form pointed to by fpAction has changed; the action encapsulation function func now looks like this:
INT8U func(void * pEvnt);Now, the action encapsulation function func is required to return a value of type INT8U, which is the state to which the state machine will transition. In other words, in the compressed table-driven method, the state machine node does not determine the new state of the state machine; instead, this task is assigned to the action encapsulation function func. The state to which the state machine transitions is determined by the return value of func.The new state has changed from a constant to a variable, which naturally increases flexibility. As mentioned earlier, the action encapsulation function func is now responsible for all events that occur, so how does func know which event triggered it? Look at the parameter void * pEvnt of func.In Program Listing 5, we mentioned that this parameter is used to pass event content to the action encapsulation function. However, from the previous description, we know that the memory pointed to by pEvnt contains all the information about the event, including the event type and event content. Therefore, through the parameter pEvnt, the action encapsulation function func can still know the type of the event.In the struct fsm_node structure in Program Listing 7, there is also a member u8StatChk, which stores a state of the state machine. What is it used for? Anyone familiar with C language arrays knows to be wary of array out-of-bounds addressing.It is important to note that the driving table of the compressed table-driven method is a one-dimensional array indexed by state values, and the most important part of the array elements is the addresses of the action encapsulation functions.To the microcontroller, function addresses are just a segment of binary data, no different from other binary data in memory. Regardless of what value is placed into the microcontroller’s PC register, the microcontroller has no objection. Suppose the program inadvertently modifies the variable storing the current state of the state machine, causing its value to become an illegal state.When an event occurs, the program will use this illegal state value to address the driving table, which will lead to memory leaks, as the program will treat unknown data in the leaked memory as a function address. It is no wonder that the program will crash!To prevent this from happening, the compressed state machine node structure adds the member u8StatChk. u8StatChk stores the position of the compressed state machine node in the one-dimensional driving table. For example, if a node is the 7th element in the table, then the value of this node’s member u8StatChk is 6.Looking at the framework code example in Program Listing 7, the program checks whether the current state and the current node’s member u8CurStat are consistent before referencing the function pointer fpAction. If they are consistent, the state is considered valid, and the event is responded to normally. If they are not consistent, the current state is considered illegal, and it transitions to an exception handling routine, maximizing the safety of program execution. Of course, if the leaked memory data happens to match u8CurStat, then this method is truly helpless.Another method to prevent the state machine from crashing is to use enumeration for the state variable, allowing the framework code to know the maximum value of the state value. Before calling the action encapsulation function, it can check whether the current state value is within a valid range, which can also ensure the safe operation of the state machine.We have already understood the definition form of the action encapsulation function in the compressed table-driven method. What does the function look like inside? Program Listing 8 is a standard example.“Program Listing 8:”
INT8U action_S0(void* pEvnt){ INT8U u8NxtStat = 0; INT8U u8EvntTyp = get_evnt_typ(pEvnt);switch(u8EvntTyp ) {case E1: action_S0_E1(); /*Response to event E1*/ u8NxtStat = new state value; /*State transition, even if not transitioning, this line must be present*/break; ......case Em: action_S0_Em(); /*Response to event Em*/ u8NxtStat = new state value; /*State transition, even if not transitioning, this line must be present*/break;default: ; /*Handling unrelated events*/break; }return u8NxtStat ; /*Return new state*/}From Program Listing 8, we can see that the action encapsulation function is essentially the specific implementation of the event switch-case. The function determines the event type based on the parameter pEvnt and selects the action response accordingly, determining the state machine’s transition state, and finally returning the new state as the execution result to the framework code.With such an action encapsulation function, the application of the Extended State Machine can be completely unrestricted! Thus, the introduction to the compressed table-driven method comes to an end.I personally believe that the compressed table-driven method is quite excellent; it combines the simplicity, efficiency, and standardization of the table-driven method with the straightforwardness, flexibility, and variability of the switch-case method, allowing them to complement each other and achieve a harmonious balance.
Function Pointer Method
As mentioned earlier, there are three main methods to implement a state machine in C language (switch-case method, table-driven method, and function pointer method), among which the function pointer method is the most difficult to understand. Its essence is to treat the function address of the action encapsulation function as the state. However, with the groundwork laid by the compressed table-driven method, the function pointer method becomes easier to understand, as the two are essentially the same.The essence of the compressed table-driven method is a one-to-one mapping from an integer value (a state of the state machine) to a function address (the action encapsulation function). The driving table of the compressed table-driven method is the direct carrier of all mapping relationships. In the driving table, one can find the function address through the state value, and conversely, one can find the state value through the function address.We can use a global integer variable to record the state value and then look up the driving table to find the function address. Why not just use a global function pointer to record the state? Why go through all that trouble?! This is the origin and evolution of the function pointer method.The action encapsulation functions written using the function pointer method are quite similar to the example function in Program Listing 8, except that the return value of the function is no longer an integer state value, but the function address of the next action encapsulation function. After the function returns, the framework code stores this function address in the global function pointer variable.Compared to the compressed table-driven method, the safe operation of the state machine is a significant issue in the function pointer method. It is challenging to find a mechanism to check whether the function address in the global function pointer variable is a valid value. If left unchecked, once the data in the function pointer variable is tampered with, the program is almost guaranteed to crash.
Conclusion
Having discussed so much about state machines, I believe everyone has felt the superiority of this tool; state machines are truly powerful! In fact, what we have been discussing all along is the Finite State Machine (FSM), which is why the abbreviation fsm appears frequently in the previous code! There is another type of state machine that is even more advanced and complex than the finite state machine, which is the Hierarchical State Machine (HSM).In simple terms, a system with only one state machine is called a finite state machine, while a system with multiple state machines is called a hierarchical state machine (though this explanation is somewhat imprecise, as parallel state machines also have multiple state machines; however, hierarchical state machines have a parent-child relationship among the state machines, while parallel state machines have a peer relationship).The hierarchical state machine is a multi-state machine structure where a parent state machine contains child state machines, incorporating many object-oriented concepts, making it more powerful than finite state machines. When a problem is challenging to solve with a finite state machine, the hierarchical state machine comes into play.I do not fully understand the theory of hierarchical state machines, so I will not attempt to elaborate here. You can find some professional books on state machine theory to read. To master state machine programming, understanding state machines (mainly referring to finite state machines) is just the first step, and it is the simplest step. The more important skill is to use the state machine as a tool to analyze and dissect actual problems: defining states, extracting events, determining transition relationships, specifying actions, etc., forming a complete state transition diagram, and finally optimizing the transition diagram to achieve the best results.Transforming actual problems into state transition diagrams completes a significant portion of the work; this is a task that requires an architect’s mindset. The remaining task is to program according to the state diagram, which is a task characteristic of a coder.