Three Elegant Embedded Software Architectures You Deserve!

Translating into specific behaviors, it boils down to three questions:

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

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

「Code Listing List4:」

switch(StateVal)
{
    case S0:
  switch(EvntID)
  {
   case E1:
    action_S0_E1(); /* Response to event E1 in state S0 */
    StateVal = new state value;/* State transition, no transition means omit this line */
    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 pseudo-code example above is a general case; actual applications are far from this complex. Although there may be many events in a system, many events may be meaningless for a specific state.

For example, in Code Listing List4, if E2, … Em have no meaning for the system in state S0, then the code for events E2, … Em is unnecessary in the case of S0, and state S0 only needs to consider the handling of event E1.

Since there is a nesting of two switch-case statements, there is a question of which nests which. Therefore, the switch-case method has two writing styles: state nested events and events nested states. Both styles are valid, each with its pros and cons; which one to choose is left to the designer based on specific circumstances.

One last point to note about the switch-case method is that because it compares from top to bottom, the further down you go, the longer the lookup time. Therefore, it is important to pay attention to the arrangement order of states and events in their respective switch statements. States and events with high frequency or real-time requirements should be placed as early as possible.

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 call the node in the table Node_SnEm, which is the system’s response to event Em in state Sn. The response mentioned here includes two aspects: output action and state transition. A state machine node is generally a structure variable similar to that in Code Listing List5.

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

This structure in Code Listing List5 has two members: fpAction and u8NxtStat. fpAction is a function pointer pointing to a function with the form void func(void * pEvnt), which standardizes the encapsulation of the action sequence in 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 in the function func.

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

Looking at the function func above, we find that the function has a parameter pEvnt, which is a pointer of type void *. During the actual operation of the program, it points to a variable that can store events. 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 the 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 the event and the current state of the state machine allow us to quickly locate in the table shown 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 fpAction, if event Em is meaningless for state Sn, what should we do with fpAction in the state machine node Node_SnEm?

My answer is: let it point to a null function! Didn’t we just say that doing nothing is also a response?

u8NxtStat stores a state value of the state machine. We know that when the state machine responds to an event, it outputs actions, which means calling the encapsulated function pointed to by the function pointer fpAction. After the function call ends, the program returns to the calling function, and the response to the event is considered complete. The next step is to consider the state transition.

It may be that the state remains 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 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 Code Listing List5.

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 this sequence is 0.
• (3) The common difference of this sequence is 1.

The characteristics and requirements of “events” as the vertical axis are exactly the same as those of the “states” used as the horizontal axis. Among the data types provided by C language, there is no better option than enumeration that meets these requirements, so it is highly recommended to make the set of state values and event types as enumeration constants. The advantages of the table-driven method include: unified calling interface and fast 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 Code Listing List5, the framework code created is shown in Code Listing List6.

Finding the target using 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.

「Code Listing List6:」

extern struct fsm_node g_arFsmDrvTbl[][]; /* State machine driving table */
INT8U u8CurStat = 0; /* Temporary state */
INT8U u8EvntTyp = 0; /* Temporary event type */
void* pEvnt = NULL; /* Temporary event variable address */
struct fsm_node stNodeTmp = {NULL, 0}; /* Temporary state machine node */
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 the state machine node */
stNodeTmp.fpAction(pEvnt ); /* Action response */
set_cur_state(stNodeTmp.u8NxtStat); /* State transition */
.....

The table-driven method is excellent, but there are some minor issues with the programs written using it. Let’s first look at the characteristics of the programs written according to the table-driven method.

As mentioned earlier, the table-driven method can standardize the part of the state machine scheduling into framework code, which is highly applicable. Regardless of what 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 (state, event, action, transition, and the “condition” element will be discussed later) in the diagram with 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.

Such a code format, if someone does not have a state transition diagram at hand, will be utterly bewildered by it, leading to 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 cumbersome and error-prone. If we inadvertently fill in the wrong position in the array, the program will run contrary to the designer’s intentions.

It is far less convenient and safer than making changes in the switch-case method. The biggest feature of the Extended State Machine is that it checks conditions before responding to events, deciding which actions to execute and which state to transition to based on the results.

In other words, when the system is in state Sn and event Em occurs, 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 Code Listing List5, if the system is in state Sn and event Em occurs, 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?!

Looking at the example diagram of the table-driven method shown in Figure 4, if we remove the vertical axis representing events from the table and only keep the horizontal axis representing states, merging one column into one cell, will the previous problem be solved? Yes! This is the long-lost “Kuaijiang Baodian” — the truncated table-driven method!!

The truncated table-driven method, also known as the compressed table-driven method, combines a one-dimensional state table with an event switch-case. The compressed table-driven method uses a one-dimensional array as the driving table, with the array index being 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 strictly specifies the state to transition to after the output action of the state machine is complete. Instead, it allows the action encapsulation function to return a state and uses this state as the new state of the state machine.

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

The example code in Code Listing List7 includes the structure of the compressed state machine node and the framework code for calling the state machine.

「Code Listing List7:」

struct fsm_node /* Compressed state machine node structure */
{
 INT8U (*fpAction)(void* pEvnt); /* Event handler 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 Code Listing List5, you will find that the structure of struct fsm_node in Code Listing List7 has changed. First, the form of the function pointed to by fpAction has changed. The action encapsulation function func now looks like this:

INT8U func(void * pEvnt);

The current action encapsulation function func is required to return a value of type INT8U, which is the state the state machine wants to transition to. 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 delegates this task to the action encapsulation function func. The state machine will transition to 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, so how does func know which event triggered it? Look at the parameter void * pEvnt of func.

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

Another member u8StatChk is added to the structure of the compressed state machine node in Code Listing List7. What is it used for?

Those who play with C language arrays know that we must be very careful to prevent array out-of-bounds access.

We need to know that the driving table of the compressed table-driven method is a one-dimensional array indexed by state values. 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, no different from other binary data in memory. Regardless of what value is placed in the PC register of the microcontroller, it has no objection. Suppose the program unexpectedly modifies the variable storing the current state of the state machine, causing the variable value to become an illegal state.

When an event occurs, the program will address the driving table using this illegal state value, leading to memory leakage, where the program mistakenly uses unknown data in the leaked memory as a function address. It is not surprising that it fails to run!

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 u8StatChk for this node is 6.

In the framework code example in Code Listing List7, 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 legal, and the event is normally responded to. If they are inconsistent, the current state is deemed illegal, and it goes to unexpected handling, maximizing the safety of the program’s operation.

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 running away is if the state variable is an enumeration, then the framework code can 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 already know the definition form of the action encapsulation function in the compressed table-driven method. What does the function look like? Code Listing List8 is a standard example.

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

From Code Listing List8, we can see that the action encapsulation function is essentially the specific implementation of the event switch-case. The function determines the event type from the parameter pEvnt and selects the action response based on the event type, determining the state of the state machine transition, 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 ends the introduction to the compressed table-driven method.

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.

As mentioned earlier, there are three main methods to implement state machines 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 treating the function 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 because the two are essentially the same.

The essence of the compressed table-driven method is a one-to-one mapping from an integer value (the 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, you can find the function address through the state value, and you can also find the state value in reverse through the function address.

Using a global integer variable to record the state value, and then looking up the driving table for the function address, you might as well directly use a global function pointer to record the state, why bother with that?! This is the past and present of the function pointer method.

The action encapsulation functions written using the function pointer method are very similar to the example function in Code 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 crash.

Having discussed so much about state machines, I believe everyone has already felt the superiority of this tool. State machines are indeed incredibly useful! In fact, what we have been talking about all along is finite state machines (now you know why the code often includes the abbreviation fsm!), and there is a more advanced and complex type of state machine known as hierarchical state machines (usually abbreviated as HSM).

Simply put, 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 of hierarchical state machines is somewhat imprecise, as parallel state machines also have multiple state machines, but the state machines in hierarchical state machines have a parent-child relationship, whereas those in 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 concepts, making it functionally more powerful. When a problem is challenging to solve with a finite state machine, it is time for the hierarchical state machine to step in.

I do not fully understand the theory of hierarchical state machines, so I won’t 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 it is the easiest step. The more important skill is to use the state machine to analyze and dissect real problems: defining states, extracting events, determining transition relationships, specifying actions, and so on, forming a complete state transition diagram, and finally optimizing the transition diagram to achieve the best.

Turning real problems into state transition diagrams means that a significant part of the work is done. This task requires the qualities of an architect, while the remaining task of coding according to the state diagram is more characteristic of a coder’s work.

Scan to add me on WeChat

Join the technical group

Share

Collect

Like

View