Source:Embedded MiscellanyState machines are ubiquitous in embedded software. You might think, what’s so difficult about state machines? Aren’t they just switches? Switch is just the most basic point, and there are many more operations related to state machines that you may not have seen. Below, I will share several implementation methods.
1. Basic Terminology of State Machines
- Current State: Refers to the state currently being occupied.
- Condition: Also known as “event”, when a condition is met, it will trigger an action or execute a state transition.
- Action: The action executed after the condition is met. After the action is completed, it can transition to a new state or remain in the original state. Actions are not mandatory; when the condition is met, it is also possible to transition to a new state without executing any action.
- Next State: The new state to which it will transition after the condition is met. The “next state” is relative to the “current state”; once the “next state” is activated, it becomes the new “current state”.
2. Traditional Finite State Machine (FSM)
As shown in the figure below, this is a timer counter that has two states: one is the setting state, and the other is the timing state.
Setting State:
- “+” and “-” buttons are used to set the initial countdown
- When the countdown value is set, press the confirm button to start timing, which switches to the timing state
Timing State:
- Pressing “+” or “-” will input the password; “+” represents 1, and “-” represents 0, with a total of 4 digits for the password
- Confirm button: Only when the input password equals the default password can the timing be stopped by pressing the confirm button; otherwise, the timer goes directly to zero and executes related operations
3. Nested Switch
/***************************************
1. List all states
***************************************/
typedef enum{
SETTING,
TIMING
} STATE_TYPE;
/***************************************
2. List all events
***************************************/
typedef enum{
UP_EVT,
DOWN_EVT,
ARM_EVT,
TICK_EVT
} EVENT_TYPE;
/***************************************
3. Define structures related to the state machine
***************************************/
struct bomb
{
uint8_t state;
uint8_t timeout;
uint8_t code;
uint8_t defuse_code;
} bomb1;
/***************************************
4. Initialize the state machine
***************************************/
void bomb1_init(void)
{
bomb1.state = SETTING;
bomb1.defuse_code = 6; // 0110
}
/***************************************
5. State machine event dispatch
***************************************/
void bomb1_fsm_dispatch(EVENT_TYPE evt, void* param)
{
switch(bomb1.state)
{
case SETTING:
{
switch(evt)
{
case UP_EVT: // "+" button pressed event
if(bomb1.timeout < 60) ++bomb1.timeout;
bsp_display(bomb1.timeout);
break;
case DOWN_EVT: // "-" button pressed event
if(bomb1.timeout > 0) --bomb1.timeout;
bsp_display(bomb1.timeout);
break;
case ARM_EVT: // "confirm" button pressed event
bomb1.state = TIMING;
bomb1.code = 0;
break;
}
} break;
case TIMING:
{
switch(evt)
{
case UP_EVT: // "+" button pressed event
bomb1.code = (bomb1.code << 1) | 0x01;
break;
case DOWN_EVT: // "-" button pressed event
bomb1.code = (bomb1.code << 1);
break;
case ARM_EVT: // "confirm" button pressed event
if(bomb1.code == bomb1.defuse_code){
bomb1.state = SETTING;
}
else{
bsp_display("bomb!");
}
break;
case TICK_EVT:
if(bomb1.timeout)
{
--bomb1.timeout;
bsp_display(bomb1.timeout);
}
if(bomb1.timeout == 0)
{
bsp_display("bomb!");
}
break;
}
}break;
}
}
Advantages: Simple, coherent code reading, easy to understand
Disadvantages:
- As the number of states or events increases, the code state functions need frequent modifications, and the amount of code in the state event handling functions will continue to increase
- The state machine is not encapsulated, leading to poor portability.
- It does not implement entry and exit operations for states. Entry and exit are particularly important in state machines.Entry Event: Triggered only once when entering, mainly used for necessary initialization of the state.Exit Event: Triggered only once during state transitions, mainly used to clear intermediate parameters generated by the state, providing a clean environment for the next entry
4. State Table
Two-Dimensional State Transition Table
The state machine can be divided into states and events, and the transitions of states are driven by events. Therefore, a two-dimensional table can represent the transitions of states.
Transition to setting only occurs when (code == defuse_code).
/*1. List all states*/
enum
{
SETTING,
TIMING,
MAX_STATE
};
/*2. List all events*/
enum
{
UP_EVT,
DOWN_EVT,
ARM_EVT,
TICK_EVT,
MAX_EVT
};
/*3. Define state table*/
typedef void(*fp_state)(EVT_TYPE evt, void* param);
static const fp_state bomb2_table[MAX_STATE][MAX_EVENT] =
{
{setting_UP, setting_DOWN, setting_ARM, NULL},
{setting_UP, setting_DOWN, setting_ARM, timing_TICK}
};
struct bomb_t
{
const fp_state const *state_table; /* the State-Table */
uint8_t state; /* the current active state */
uint8_t timeout;
uint8_t code;
uint8_t defuse_code;
};
struct bomb bomb2 =
{
.state_table = bomb2_table,
};
void bomb2_init(void)
{
bomb2.defuse_code = 6; // 0110
bomb2.state = SETTING;
}
void bomb2_dispatch(EVT_TYPE evt, void* param)
{
fp_state s = NULL;
if(evt > MAX_EVT)
{
LOG("EVT type error!");
return;
}
s = bomb2.state_table[bomb2.state * MAX_EVT + evt];
if(s != NULL)
{
s(evt, param);
}
}
/* List all state corresponding event handling functions */
void setting_UP(EVT_TYPE evt, void* param)
{
if(bomb1.timeout < 60) ++bomb1.timeout;
bsp_display(bomb1.timeout);
}
Disadvantages: The most obvious disadvantage is that the function granularity is too small; one state and one event will generate one function. When there are many states and events, the handling functions will increase rapidly, and the logic will be dispersed when reading the code. Entry and exit actions are not implemented.
One-Dimensional State Transition Table
Implementation principle:
typedef void(*fp_action)(EVT_TYPE evt, void* param);
/* Basic structure of the transition table */
struct tran_evt_t
{
EVT_TYPE evt;
uint8_t next_state;
};
/* Description of the state */
struct fsm_state_t
{
fp_action enter_action; // Entry action
fp_action exit_action; // Exit action
fp_action action;
tran_evt_t* tran; // Transition table
uint8_t tran_nb; // Size of the transition table
const char* name;
};
/* The body of the state table */
#define ARRAY(x) x, sizeof(x)/sizeof(x[0])
const struct fsm_state_t state_table[] =
{
{setting_enter, setting_exit, setting_action, ARRAY(set_tran_evt), "setting"},
{timing_enter, timing_exit, timing_action, ARRAY(time_tran_evt), "timing"}
};
/* Construct a state machine */
struct fsm
{
const struct state_t * state_table; /* the State-Table */
uint8_t cur_state; /* the current active state */
uint8_t timeout;
uint8_t code;
uint8_t defuse_code;
} bomb3;
/* Initialize the state machine */
void bomb3_init(void)
{
bomb3.state_table = state_table; // Point to the state table
bomb3.cur_state = setting;
bomb3.defuse_code = 8; // 1000
}
/* State machine event dispatch */
void fsm_dispatch(EVT_TYPE evt, void* param)
{
tran_evt_t* p_tran = NULL;
/* Get the transition table of the current state */
p_tran = bomb3.state_table[bomb3.cur_state]->tran;
/* Check if any possible transitions match the currently triggered event */
for(uint8_t i = 0; i < x; i++)
{
if(p_tran[i]->evt == evt) // The event will trigger the transition
{
if(NULL != bomb3.state_table[bomb3.cur_state].exit_action){
bomb3.state_table[bomb3.cur_state].exit_action(NULL); // Execute exit action
}
if(bomb3.state_table[p_tran[i]->next_state].enter_action){
bomb3.state_table[p_tran[i]->next_state].enter_action(NULL); // Execute entry action
}
/* Update the current state */
bomb3.cur_state = p_tran[i]->next_state;
}
else
{
bomb3.state_table[bomb3.cur_state].action(evt, param);
}
}
}
/*************************************************************************
Related to the setting state
************************************************************************/
void setting_enter(EVT_TYPE evt, void* param)
{
}
void setting_exit(EVT_TYPE evt, void* param)
{
}
void setting_action(EVT_TYPE evt, void* param)
{
}
tran_evt_t set_tran_evt[] =
{
{ARM, timing},
};
/* Related to timing state */
Advantages:
- Each state is relatively independent for the user; adding events and states does not require modifying existing state event functions.
- Entry and exit of states are implemented
- It is easy to design based on the state transition diagram (the state transition diagram lists the possible transitions for each state, which is the transition table here)
- Flexible implementation, capable of complex logic, such as tracking the previous state and adding monitoring conditions to reduce the number of events. It can achieve non-completely event-driven behavior
Disadvantages:
- Function granularity is relatively small (smaller than two-dimensional and grows slowly); it can be seen that each state requires at least three functions and all transition relationships need to be listed.