Content
Source: Sun Wukong Seeking Knowledge
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, no action can be executed, and it can directly transition to a new state. Next State: The new state to transition to after the condition is met. “Next State” is relative to the “Current State”; once the “Next State” is activated, it becomes the new “Current State”.
Traditional Finite State Machine (FSM) Implementation Method
As shown in the figure, this is a timer counter, which has two states: a setting state and a timing state.
Setting State
The “+” and “-” buttons are used to set the initial countdown. When the countdown value is set, press the confirm button to start the timing, which switches to the timing state.
Timing State
Pressing “+” and “-” will input the password. “+” represents 1, “-” represents input 0, and the password consists of 4 digits.
Confirm Button: The timing can only be stopped if the entered password equals the default password; otherwise, the timer goes directly to zero and executes the relevant operations.
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. Dispatch state machine events
***************************************/
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, code is coherent and easy to understand.
Disadvantages
-
As the number of states or events increases, the code state functions need frequent modifications, and the code volume of state event handling functions will continue to increase.
-
The state machine is not encapsulated, leading to poor portability.
-
Entering and exiting operations of states are not implemented. Entering and exiting are particularly important in state machines.
-
Entry events: Triggered only once when entering, mainly used for necessary initialization of the state.
-
Exit events: Triggered only once during state transitions, mainly used to clear intermediate parameters generated by the state, providing a clean environment for the next entry.
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, so a two-dimensional table can be used to represent state transitions.
(*) The transition to setting occurs only 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);
}
Advantages
-
Each state is relatively independent from the user’s perspective, and adding events and states does not require modifying existing state event handling functions.
-
The state machine can be encapsulated, providing better portability. Function pointer safe conversion allows users to extend state machines and events with private attributes while using a unified base state machine interface.
typedef void (*Tran)(struct StateTableTag *me, Event const *e); void Bomb2_setting_ARM (Bomb2 *me, Event const *e); typedef struct Bomb { struct StateTableTag *me; // Must be the first member uint8_t private; }
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 number of handling functions will increase rapidly, leading to scattered logic when reading the code.
-
Entering and exiting actions are not implemented.
One-Dimensional State Transition Table
Implementation principle:
typedef void (*fp_action)(EVT_TYPE evt,void* param);
/* Basic structure of transition table */
struct tran_evt_t
{
EVT_TYPE evt;
uint8_t next_state;
};
/* Description of state */
struct fsm_state_t
{
fp_action enter_action; // Enter 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;
}
/* Body of 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" }
};
/* Build 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 state machine */
void bomb3_init(void)
{
bomb3.state_table = state_table; // Point to state table
bomb3.cur_state = setting;
bomb3.defuse_code = 8; //1000
}
/* Dispatch state machine events */
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 all possible transitions match the currently triggered event */
for(uint8_t i=0;i<x;i++)
{
if(p_tran[i]->evt == evt)// Event will trigger 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[_tran[i]->next_state].enter_action){
bomb3.state_table[_tran[i]->next_state].enter_action(NULL);// Execute enter action
}
/* Update current state */
bomb3.cur_state = p_tran[i]->next_state;
}
else
{
bomb3.state_table[bomb3.cur_state].action(evt,param);
}
}
}
/*************************************************************************
setting state related
************************************************************************/
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},
}
/* timing state related */
Advantages
-
Each state is relatively independent from the user’s perspective, and adding events and states does not require modifying existing state event handling functions.
-
Implemented entering and exiting actions.
-
Easy to design based on state transition diagrams (state transition diagrams list the possible transitions of each state, which is the transition table here).
-
Flexible implementation, can implement complex logic, such as the previous state, adding monitoring conditions to reduce the number of events. Can implement non-completely event-driven.
Disadvantages
-
Function granularity is 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.
QP Embedded Real-Time Framework
Features
Event-Driven Programming
Hollywood Principle: Unlike traditional sequential programming methods such as “super loop” or traditional RTOS tasks, most modern event-driven systems are constructed based on the Hollywood principle (Don’t call me; I’ll call you).
Object-Oriented
Classes and single inheritance.
Tools
QM, a software that describes state machines through UML class diagrams and can automatically generate C code:
QS software tracking tool:
QEP Implementation of Finite State Machine (FSM)
/* qevent.h ----------------------------------------------------------------*/
typedef struct QEventTag
{
QSignal sig;
uint8_t dynamic_;
} QEvent;
/* qep.h -------------------------------------------------------------------*/
typedef uint8_t QState; /* status returned from a state-handler function */
typedef QState (*QStateHandler) (void *me, QEvent const *e); /* argument list */
typedef struct QFsmTag /* Finite State Machine */
{
QStateHandler state; /* current active state */
}QFsm;
#define QFsm_ctor(me_, initial_) ((me_)->state = (initial_))
void QFsm_init (QFsm *me, QEvent const *e);
void QFsm_dispatch(QFsm *me, QEvent const *e);
#define Q_RET_HANDLED ((QState)0)
#define Q_RET_IGNORED ((QState)1)
#define Q_RET_TRAN ((QState)2)
#define Q_HANDLED() (Q_RET_HANDLED)
#define Q_IGNORED() (Q_RET_IGNORED)
#define Q_TRAN(target_) (((QFsm *)me)->state = (QStateHandler) (target_),Q_RET_TRAN)
enum QReservedSignals
{
Q_ENTRY_SIG = 1,
Q_EXIT_SIG,
Q_INIT_SIG,
Q_USER_SIG
};
/* file qfsm_ini.c ---------------------------------------------------------*/
#include "qep_port.h" /* the port of the QEP event processor */
#include "qassert.h" /* embedded systems-friendly assertions */
void QFsm_init(QFsm *me, QEvent const *e)
{
(*me->state)(me, e); /* execute the top-most initial transition */
/* enter the target */
(void)(*me->state)(me , &QEP_reservedEvt_[Q_ENTRY_SIG]);
}
/* file qfsm_dis.c ---------------------------------------------------------*/
void QFsm_dispatch(QFsm *me, QEvent const *e)
{
QStateHandler s = me->state; /* save the current state */
QState r = (*s)(me, e); /* call the event handler */
if (r == Q_RET_TRAN) /* transition taken? */
{
(void)(*s)(me, &QEP_reservedEvt_[Q_EXIT_SIG]); /* exit the source */
(void)(*me->state)(me, &QEP_reservedEvt_[Q_ENTRY_SIG]);/*enter target*/
}
}
Implement the above timer example
#include "qep_port.h" /* the port of the QEP event processor */
#include "bsp.h" /* board support package */
enum BombSignals /* all signals for the Bomb FSM */
{
UP_SIG = Q_USER_SIG,
DOWN_SIG,
ARM_SIG,
TICK_SIG
};
typedef struct TickEvtTag
{
QEvent super; /* derive from the QEvent structure */
uint8_t fine_time; /* the fine 1/10 s counter */
}TickEvt;
typedef struct Bomb4Tag
{
QFsm super; /* derive from QFsm */
uint8_t timeout; /* number of seconds till explosion */
uint8_t code; /* currently entered code to disarm the bomb */
uint8_t defuse; /* secret defuse code to disarm the bomb */
} Bomb4;
void Bomb4_ctor (Bomb4 *me, uint8_t defuse);
QState Bomb4_initial(Bomb4 *me, QEvent const *e);
QState Bomb4_setting(Bomb4 *me, QEvent const *e);
QState Bomb4_timing (Bomb4 *me, QEvent const *e);
/*--------------------------------------------------------------------------*/
/* the initial value of the timeout */
#define INIT_TIMEOUT 10
/*..........................................................................*/
void Bomb4_ctor(Bomb4 *me, uint8_t defuse) {
QFsm_ctor_(&me->super, (QStateHandler)&Bomb4_initial);
me->defuse = defuse; /* the defuse code is assigned at instantiation */
}
/*..........................................................................*/
QState Bomb4_initial(Bomb4 *me, QEvent const *e) {
(void)e;
me->timeout = INIT_TIMEOUT;
return Q_TRAN(&Bomb4_setting);
}
/*..........................................................................*/
QState Bomb4_setting(Bomb4 *me, QEvent const *e) {
switch (e->sig){
case UP_SIG:{
if (me->timeout < 60) {
++me->timeout;
BSP_display(me->timeout);
}
return Q_HANDLED();
}
case DOWN_SIG: {
if (me->timeout > 1) {
--me->timeout;
BSP_display(me->timeout);
}
return Q_HANDLED();
}
case ARM_SIG: {
return Q_TRAN(&Bomb4_timing); /* transition to "timing" */
}
}
return Q_IGNORED();
}
/*..........................................................................*/
void Bomb4_timing(Bomb4 *me, QEvent const *e) {
switch (e->sig) {
case Q_ENTRY_SIG: {
me->code = 0; /* clear the defuse code */
return Q_HANDLED();
}
case UP_SIG: {
me->code <<= 1;
me->code |= 1;
return Q_HANDLED();
}
case DOWN_SIG: {
me->code <<= 1;
return Q_HANDLED();
}
case ARM_SIG: {
if (me->code == me->defuse) {
return Q_TRAN(&Bomb4_setting);
}
return Q_HANDLED();
}
case TICK_SIG: {
if (((TickEvt const *)e)->fine_time == 0) {
--me->timeout;
BSP_display(me->timeout);
if (me->timeout == 0) {
BSP_boom(); /* destroy the bomb */
}
}
return Q_HANDLED();
}
}
return Q_IGNORED();
}
Advantages
- Uses an object-oriented design approach, providing good portability.
- Implements entering and exiting actions.
- Appropriate granularity, and the granularity of events is controllable.
- State switching is efficient by changing pointers.
- Can be extended to hierarchical state machines.
Disadvantages
- Defining events and controlling event granularity is the biggest difficulty in design, such as whether to treat receiving a frame of data from the serial port as a separate event or to treat the receipt of data as one event. Additionally, for displays, how to design events using this programming method.
QP Introduction to Hierarchical State Machines (HSM)
Initialization:
The implementation of initializing a hierarchical state machine: At initialization, the user-selected state is always the lowest-level state. For example, after the calculator is powered on, it should enter the start state. This involves a problem: there is a state transition path from the initial top (top state) to begin. When we set the state to begin, how to search for this path becomes crucial (knowing the path is necessary to correctly enter begin and execute the entry and exit events of the transitional states along the path).
void QHsm_init(QHsm *me, QEvent const *e)
{
Q_ALLEGE((*me->state)(me, e) == Q_RET_TRAN);
t = (QStateHandler)&QHsm_top; /* HSM starts in the top state */
do { /* drill into the target... */
QStateHandler path[QEP_MAX_NEST_DEPTH_];
int8_t ip = (int8_t)0; /* transition entry path index */
path[0] = me->state; /* This state is begin */
/* By executing an empty signal, find the path from the bottom state to the top state */
(void)QEP_TRIG_(me->state, QEP_EMPTY_SIG_);
while (me->state != t) {
path[++ip] = me->state;
(void)QEP_TRIG_(me->state, QEP_EMPTY_SIG_);
}
/* Switch to begin */
me->state = path[0]; /* restore the target of the initial tran. */
/* Drill down to the lowest state, executing all entry events along the path */
Q_ASSERT(ip < (int8_t)QEP_MAX_NEST_DEPTH_);
do { /* retrace the entry path in reverse (desired) order... */
QEP_ENTER_(path[ip]); /* enter path[ip] */
} while ((--ip) >= (int8_t)0);
t = path[0]; /* current state becomes the new source */
} while (QEP_TRIG_(t, Q_INIT_SIG) == Q_RET_TRAN);
me->state = t;
}
State Switching:
/*.................................................................*/
QState result(Calc *me, QEvent const *e)
{
switch (e->sig)
{you
case ENTER_SIG:{
break;
}
case EXIT_SIG:{
break;
}
case C_SIG:
{
printf("clear");
return Q_HANDLED();
}
case B_SIG:
{
return Q_TRAN(&begin);
}
}
return Q_SUPER(&reday);
}
/*.ready为result和begin的超状态................................................*/
QState ready(Calc *me, QEvent const *e)
{
switch (e->sig)
{
case ENTER_SIG:{
break;
}
case EXIT_SIG:{
break;
}
case OPER_SIG:
{
return Q_TRAN(&opEntered);
}
}
return Q_SUPER(&on);
}
void QHsm_dispatch(QHsm *me, QEvent const *e)
{
QStateHandler path[QEP_MAX_NEST_DEPTH_];
QStateHandler s;
QStateHandler t;
QState r;
t = me->state; /* save the current state */
do { /* process the event hierarchically... */
s = me->state;
r = (*s)(me, e); /* invoke state handler s */
} while (r == Q_RET_SUPER); // Current state cannot handle the event until finding a state that can handle the event.
if (r == Q_RET_TRAN) { /* transition taken? */
int8_t ip = (int8_t)(-1); /* transition entry path index */
int8_t iq; /* helper transition entry path index */
path[0] = me->state; /* save the target of the transition */
path[1] = t;
while (t != s) { /* exit current state to transition source s... */
if (QEP_TRIG_(t, Q_EXIT_SIG) == Q_RET_HANDLED) {/* exit handled? */
(void)QEP_TRIG_(t, QEP_EMPTY_SIG_); /* find superstate of t */
}
t = me->state; /* me->state holds the superstate */
}
. . .
}
me->state = t; /* set new state or restore the current state */
}
t = path[0]; /* target of the transition */
if (s == t) { /* (a) check source==target (transition to self) */
QEP_EXIT_(s) /* exit the source */
ip = (int8_t)0; /* enter the target */
}
else {
(void)QEP_TRIG_(t, QEP_EMPTY_SIG_); /* superstate of target */
t = me->state;
if (s == t) { /* (b) check source==target->super */
ip = (int8_t)0; /* enter the target */
}
else {
(void)QEP_TRIG_(s, QEP_EMPTY_SIG_); /* superstate of src */
/* (c) check source->super==target->super */
if(me->state == t) {
QEP_EXIT_(s) /* exit the source */
ip = (int8_t)0; /* enter the target */
}
else {
/* (d) check source->super==target */
if (me->state == path[0]) {
QEP_EXIT_(s) /* exit the source */
}
else { /* (e) check rest of source==target->super->super..
* and store the entry path along the way */
....
Components of the QP Real-Time Framework
Memory Management
Using memory pools, for low-performance MCUs, memory is extremely limited. Introducing memory management is essential because the entire architecture uses events as the primary means of task communication, and events are parameterized. The same type of event may be triggered multiple times, and after event processing is completed, the event needs to be cleared. Therefore, it is necessary to create memory pools for different events.
For memory pools of different block sizes, the alignment issue of each block’s starting address needs to be considered. When initializing the memory pool, we divide the memory pool based on block size + header size. Assuming a 2-byte structure, if divided by 2, and assuming the MCU is 4-byte aligned, then half of the structure’s starting addresses will be unaligned. In this case, space needs to be reserved for each block to ensure alignment.
Event Queue
Each active object maintains an event queue, and events are derived from base events. Different types of events only need to add their base event members to the active object’s queue, and when retrieved, the additional parameters can be obtained through a forced conversion.
Event Dispatching
Direct event sending:
- QActive_postLIFO()
Publish-subscribe event sending:
-
The vertical axis represents signals (the base class of events).
-
Active objects support 64 priority levels, and each active object is required to have a unique priority.
-
The bit position of the priority indicates which active objects subscribe to a certain event, and after the event is triggered, events are dispatched to active objects based on priority.
Timed Events
Unordered linked list:
Cooperative scheduler QV:
Introduction to QP Nano
- Fully supports hierarchical state nesting, including guaranteed entry/exit actions for any state transition topology under up to 4 levels of state nesting.
- Supports up to 8 concurrently executing, deterministic, thread-safe event queue active objects.
- Supports a one-byte wide (255 signals) signal and a scalable parameter that can be configured to 0 (no parameters), 1, 2, or 4 bytes.
- Uses a FIFO queuing strategy for direct event dispatching.
- Each active object has a one-time timer event (timer), with a configurable dynamic range of 0 (no timer event), 1, 2, or 4 bytes.
- Built-in cooperative vanilla kernel.
- Built-in preemptive RTC kernel named QK-nano (see Chapter 6, Section 6.3.8).
- Low-power architecture with idle callback functions for easy implementation of power-saving modes.
- Prepared for non-standard extensions of C compilers for popular low-end CPU architectures in the code (e.g., allocating constant objects in code space, reentrant functions, etc.).
- Error handling strategy based on assertions.
Code Style:
References
http://www.state-machine.com/ (QP Official Website)
Source: https://blog.csdn.net/qq_36969440/article/details/110387716
Copyright belongs to the original author. If there are copyright issues, please contact me for deletion, thank you~
Finally
That’s all for today. If you found it helpful, be sure to give alike~
Bug Jun’s unique, permanent, and free sharing platform for embedded technology knowledge~
Recommended Albums Click the blue text to jump
☞ MCU Advanced Album 
☞ Embedded C Language Advanced Album
☞ “Bug Says” Album
☞ Album|Linux Application Programming Collection
☞ Album|Learn Some Network Knowledge
☞ Album|Handwritten C Language
☞ Album|Handwritten C++ Language
☞ Album|Experience Sharing
☞ Album|Power Control Technology