Three Elegant Embedded Software Architectures You Deserve!

The implementation of a state machine consists of three elements: state, event, and response. When converted into specific behaviors, it can be summarized in three sentences.

• What happened?
• What state is the system currently in?
• In this state, what should the system do when this event occurs?

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

States are organized using switch-case, and events are also organized using switch-case, then one switch-case is inserted into each case of another switch-case.

Program Listing List4:

switch(StateVal)
{
    case S0:
  switch(EvntID)
  {
   case E1:
    action_S0_E1(); /*Response to event E1 in S0 state*/
    StateVal = new state value;/*State transition, if no transition, this line is omitted*/
    break;
   case E2:
    action_S0_E2(); /*Response to event E2 in S0 state*/
    StateVal = new state value;
    break;
   ......
   case Em:
    action_S0_Em(); /*Response to event Em in S0 state*/
    StateVal = new state value;
    break;
   default:
    break;
  }
  break;
    case S1:
  ......
  break;
    ......
    case Sn:
  ......
  break;
    default:
  break;
}

The pseudo-code example above is just a general case; actual applications are far from this complex. Although there may be many types of events in a system, many events may be meaningless for a certain state.

For example, in Program Listing List4, if E2, …, Em are meaningless for the system in S0 state, then the code related to events E2, …, Em under the S0 case does not need to be written; the S0 state only needs to consider the handling of event E1.

Since it involves nesting between two switch-cases, there is the issue of which one nests which, so there are two ways to write the switch-case method: state nested events and events nested states. Both methods are valid and have their pros and cons; which one to choose is left to the designer’s discretion based on specific situations.

One last point to note about the switch-case method is that since the principle of switch-case is to compare one by one from top to bottom, the later it is positioned, the longer the lookup time will be. Therefore, attention should be paid to the order of states and events in their respective switch statements; it is not recommended to arrange them in order as in Program Listing List4. States and events that occur frequently or have high real-time requirements should be placed as far forward 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, where the intersection [Sn, Em] represents the response of the system to event Em when in state Sn.

As shown in Figure 4, I call the node in the table Node_SnEm, which is the response of the system to event Em when in state Sn. The response here includes two aspects: output actions and state transitions. The state machine node is generally a structure variable similar to that in Program Listing List5.

struct fsm_node
{
    void (*fpAction)(void* pEvnt);
    INT8U u8NxtStat;
};

This structure in Program Listing List5 has two members: fpAction and u8NxtStat. fpAction is a function pointer that points to a function with the form void func(void * pEvnt); this function func is a standardized encapsulation of the action sequence during state transitions.

In other words, during a state transition, regardless of how many actions are output, how many variables are operated on, or how many functions are called, all these behaviors are handled in the function func.

Once the actions are encapsulated, the address of the encapsulated function func is handed to the function pointer fpAction, so that to output actions, you only need to call the function pointer fpAction.

Looking at the above func function, you will notice that it has a parameter pEvnt, which is a pointer of type void *. During the actual execution of the program, it points to a variable that can store events, and through this pointer, we can obtain all information about the event; this parameter is quite necessary.

Events generally include two attributes: the type of the event and the content of the event.

For instance, in a key event, we not only need to know that this is a key event but also which key was pressed.

The type of the event and the current state of the state machine can quickly locate in the table shown in Figure 4 and determine which action encapsulation function to call. However, for the action encapsulation function to correctly respond to the event, it also needs to know what the content of the event is; this 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 * type to increase flexibility.

Regarding the last question about fpAction: if event Em is meaningless for state Sn, what should the fpAction in the state machine node Node_SnEm point to?

My answer is: Then let it point to a null function! As mentioned before, 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. After the function call is complete, the program returns to the calling function, and the state machine’s response to the event is considered finished. The next step is to consider the issue of state transition.

The state may remain unchanged, or it may transition to a new state; how to decide? The state stored in u8NxtStat is the answer the state machine wants!

The table shown in Figure 4 is reflected in C language code as a two-dimensional array, where the first dimension represents the states of the state machine, and the second dimension represents the uniformly classified events, and the elements of the array are the structure constants from Program Listing List5.

If using the table-driven method in the program, there are some special considerations to keep in mind. 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.

The characteristic and requirements for “events” as the vertical axis are completely consistent with those for “states” used as the horizontal axis. Among the data types provided by C language, there is no option that meets the above requirements better than enumeration; 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 are: unified calling interface and rapid positioning.

The table-driven method shields the differences in handling various events under different states, allowing the common parts of the processing process to be extracted and made into standardized, unified framework code, forming a unified calling interface.

Based on the state machine node structure from Program Listing List5, the framework code is shown in Program Listing List6.

Program Listing List6:

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*/
.....

The table-driven method is good, but there are still some small issues with the programs written using it. Let’s first look at the characteristics of the programs written using the table-driven method.

As mentioned earlier, the table-driven method can standardize the parts of the state machine scheduling 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 then implement the elements in the diagram (states, events, actions, transitions, and the relevant “condition” elements will be discussed later) using 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 you will also see many unrelated functions, which are the action encapsulation functions mentioned earlier.

This kind of code, if you don’t have a state transition diagram at hand, will confuse anyone who looks at it, and this format directly leads to the problem of poor code readability.

If we want to add a state to the state machine, it reflects in the code as adding a column to the driving table, and we also need to add several action encapsulation functions.

If the driving table is large, doing this work can be quite tedious and prone to errors. If you accidentally fill in the wrong position in the array, then the program will run contrary to the designer’s intent.

It is far more convenient and safer than making changes in the switch-case method. The greatest characteristic of the Extended State Machine is that before the state machine responds to an event, it first judges conditions and then selects 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 structure of the state machine node given in Program Listing List5, if an event Em occurs while the system is in state Sn, after the state machine executes the actions given by fpAction, it 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 of the state machine in the implementation of the table-driven method. ESM, you are so excellent, how can I bear to abandon you?!

Now, looking at the example of the table-driven method shown in Figure 4, if we remove the vertical axis representing events from the table, leaving only the horizontal axis representing states, and merge a column into a cell, can the problems mentioned earlier be solved? Yes! This is the long-lost compressed table-driven method!!

The compressed table-driven method, also known as the one-dimensional state table combined with event switch-case, 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 forces the specification of the state to which the state machine should transition after the output actions are completed; instead, it allows the action encapsulation function to return a state and uses this state as the new state of the state machine.

This characteristic of the compressed table-driven method perfectly solves the problem that the Extended State Machine cannot be used in the table-driven method.

Program Listing List7 contains the structure of the compressed state machine node and the framework code for calling the state machine.

Program Listing List7:

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 List5, you will find changes in the struct fsm_node structure in Program Listing List7. First, the function form pointed to by fpAction has changed; the structure of 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 should 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, it assigns this task to the action encapsulation function func. The state to transition to is whichever state func returns.

The new state has changed from a constant to a variable, making it much more flexible. As mentioned earlier, the action encapsulation function func is responsible for all events that occur; how does func know which event triggered it? Look at the parameter void * pEvnt.

In Program Listing List5, we mentioned that this parameter is used to pass event content to the action encapsulation function, but from the previous description, we know that the memory pointed to by pEvnt contains all information about the event, including the type and content of the event, so through the parameter pEvnt, the action encapsulation function func can also know the type of the event.

Program Listing List7 also has a member u8StatChk in the compressed state machine node structure, which stores a state of the state machine. What is it used for?

Anyone who plays with C language arrays knows to be wary of array bounds.

To know, 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.

In the eyes of the microcontroller, function addresses are just a segment of binary data, and there is no difference between them and other binary data in memory. Regardless of what value is put into the microcontroller’s PC register, the microcontroller has no objection. If the program modifies the variable storing the current state of the state machine due to some unexpected reason, making the variable value become an illegal state.

Then, when an event occurs, the program will use this illegal state value to address the driving table, which will cause memory leakage, and the program will treat the unknown data in the leaked memory as a function address to jump to, and it would be strange if it doesn’t run away!

To prevent such phenomena, 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 List7, before referencing the function pointer fpAction, the program first checks whether the values of the current state and the current node member u8CurStat are consistent; if consistent, it is considered a valid state, and the event responds normally. If not consistent, it is considered an illegal current state, and unexpected handling is performed to maximize the safety of program execution.

Of course, if the leaked memory data just happens to match u8CurStat, then this method really cannot be saved.

Another method to prevent the state machine from running away is if the state variable is an enumeration, then the framework code can know the maximum value of the state value, and before calling the action encapsulation function, check whether the current state value is within the legal range, which can also ensure the safe operation of the state machine.

We already know the definition form of the action encapsulation function in the compressed table-driven method; what does the function look like? Program Listing List8 is a standard example.

Program Listing List8:

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, must have this line even if no transition*/
   break;
   ......
  case Em:
   action_S0_Em(); /*Response to event Em*/
   u8NxtStat = new state value; /*State transition, must have this line even if no transition*/
   break;
  default:
   ; /*Handling unrelated events*/
   break;
 }
 return u8NxtStat ; /*Return new state*/
}

From Program Listing List8, it can be seen that the action encapsulation function is actually the specific implementation of the event switch-case. The function determines the event type based on the parameter pEvnt and selects the action response according to the event type, determines the state transition of the state machine, and finally returns 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 of 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 standard of the table-driven method with the straightforwardness, flexibility, and variability of the switch-case method, complementing each other’s strengths and achieving a win-win situation.

Function Pointer Method

As mentioned earlier, there are mainly three methods to implement a state machine in C language (switch-case method, table-driven method, function pointer method), among which the function pointer method is the most difficult to understand. Its essence is to treat the addresses of action encapsulation functions as states. However, with the previous groundwork of 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 (action encapsulation function). The driving table of the compressed table-driven method is the direct carrier of all mapping relationships. In the driving table, you can find the function address through the state value, and likewise, you can find the state value through the function address.

Instead of using a global integer variable to record the state value and then checking the driving table for the function address, why not directly use a global function pointer to record the state? Why go through all that trouble?! This is the past and present 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 List8, 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, it is almost inevitable that the program will run away.

Summary

Having discussed so much about state machines, I believe everyone has already felt the superiority of this tool; state machines are truly very useful! In fact, what we have been discussing all along is finite state machines (now you know why the code earlier often has the abbreviation fsm!), there is another type of state machine that is even more powerful and complex than finite state machines, which is the hierarchical state machine (generally abbreviated as 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 (this explanation is somewhat inaccurate; parallel state machines also have multiple state machines, but hierarchical state machines have a parent-child relationship while parallel state machines have a peer relationship).

A hierarchical state machine is a multi-state machine structure where a parent state machine contains child state machines, incorporating many object-oriented ideas, so its functionality is also more powerful. When solving a problem with a finite state machine becomes challenging, the hierarchical state machine is called to action.

I do not fully understand the theory of hierarchical state machines, so I will not try to show off 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 the simplest one. The more important skill is to use the state machine tool to analyze and dissect actual problems: dividing 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.

Transforming actual problems into state transition diagrams is already half the work done; this is a task that requires the qualities of an architect, while the remaining task of programming according to the state diagram is a job that requires coding skills.

This article is sourced from the internet, and the copyright belongs to the original author. If there are copyright issues, please contact me for deletion.