Various Techniques for State Machines in Embedded Systems

State machines are ubiquitous in embedded software, and you might say, what is so difficult about state machines? Aren’t they just switches? Switch is merely the most basic point; there are many more operations regarding state machines that you may not have encountered. 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. “Next State” is relative to the “Current State”; once the “Next State” is activated, it becomes the new “Current State”.
Various Techniques for State Machines in Embedded Systems

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 the timer, transitioning to the Timing State.

Timing State:

  • Pressing “+” or “-” will input the password; “+” represents 1, and “-” represents 0; the password consists of 4 digits.
  • Confirm button: Only when the entered password equals the default password can the timer be stopped by pressing the confirm button; otherwise, the timer will go directly to zero and execute the relevant operations.
Various Techniques for State Machines in Embedded Systems

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;
  }
}
Various Techniques for State Machines in Embedded Systems

Advantages: Simple, coherent code reading, easy to understand.

Disadvantages:

  1. 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.
  2. The state machine is not encapsulated, leading to poor portability.
  3. It does not implement entry and exit operations for states. Entry and exit are particularly important in state machines. Entry Event: Triggers only once when entering, mainly for necessary initialization of the state. Exit Event: Triggers only once during state transition, mainly 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; state transitions are driven by events, so a two-dimensional table can represent state transitions.

Various Techniques for State Machines in Embedded Systems

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

Various Techniques for State Machines in Embedded Systems

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 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 entry 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; 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).
  • It is flexible and can implement complex logic, such as the previous state, and add monitoring conditions to reduce the number of events. It 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.

5. QP Embedded Real-Time Framework

Event-Driven Programming

The 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:

Various Techniques for State Machines in Embedded Systems

Tools

QM: A software that describes state machines through UML class diagrams and can automatically generate C code.

Various Techniques for State Machines in Embedded Systems

QS software tracing tool:

Various Techniques for State Machines in Embedded Systems
Various Techniques for State Machines in Embedded Systems

6. QEP Implementation of Finite State Machine (FSM)

Various Techniques for State Machines in Embedded Systems
/* 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 entry and exit 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 challenge in design. For example, when a serial port receives a frame of data, should the updates of these variables be treated as a separate event, or should the receipt of data from the serial port be treated as one event? Additionally, for displays, if using this programming method, how to design events?

7. QP Implementation of Hierarchical State Machines

Various Techniques for State Machines in Embedded Systems

Initialization of the hierarchical state machine: During initialization, the user-selected state is always the lowest-level state. For example, in the calculator, after powering 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; /* Here the state is begin */
            
            /* By executing an empty signal, find the path from the lowest 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 transition. */
      /* Drill down to the lowest state, executing all entry events in 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:

Various Techniques for State Machines in Embedded Systems
/*.................................................................*/
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 */
}
Various Techniques for State Machines in Embedded Systems
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.. */
                     ...
                }
            }
        }
    }

8. Components of the QP Real-Time Framework

Various Techniques for State Machines in Embedded Systems
Various Techniques for State Machines in Embedded Systems

Memory Management

Using memory pools, for low-performance MCUs, memory is extremely limited. Introducing memory management is essential in the entire architecture, as events are 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 not be aligned. In this case, space needs to be reserved for each block to ensure alignment.

Various Techniques for State Machines in Embedded Systems

Event Queue

Each active object maintains an event queue. Events are derived from base events, and different types of events only need to add their base event members to the active object’s queue. Finally, when retrieved, the additional parameters can be obtained through a forced conversion.

Various Techniques for State Machines in Embedded Systems

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 priorities, and each active object must 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.
Various Techniques for State Machines in Embedded Systems

Code Style

Various Techniques for State Machines in Embedded Systems

Reference link: https://pan.baidu.com/s/18LQhr7qumRSQvHqQgE4UnA

Extraction code: qqqq

QP Official Website: http://www.state-machine.com/

Various Techniques for State Machines in Embedded Systems

END

Source: Embedded Miscellaneous

Copyright belongs to the original author. If there is any infringement, please contact for deletion.▍Recommended ReadingThe internal structure of the Titan missile guidance computer is exposed!Why are embedded salaries much lower than pure software salaries?Why are Chinese programmers less creative than foreign programmers?→ Follow for more updates ←

Related posts

  1. Practical Microcontroller Programming Experience Summary
  2. An Open Source MCU-Level Command Line Interaction Component
  3. High Reliability Design Methods for PCBs in Industrial Control Systems
  4. Control Scheme for Industrial Waste Gas Treatment System
  5. Siemens SPPA-T3000 Control System Exposes Critical Vulnerabilities, Leaving Global Power Plants at Risk!
  6. Methods for Outputting Debug Information in Embedded Development
  7. Industry Focus: Design of Next-Generation Avionics Software Based on Software Virtualization Technology
  8. Embedded Development: Understanding MCU Power Up and Down
  9. How to Write Maintainable Embedded Programming Code?
  10. Introduction to PLC Basic Working Methods
  11. MicroBit Three-Level Elevator Project
  12. A Simple Analysis of the Differences Between STM32 and 51 Microcontrollers
  13. Upgrading Five-Phase Ten-Shot Board Machines to Three-Phase Six-Shot
  14. How to Implement Real-Time Power Load Forecasting System with Industrial PC
  15. Industrial Grade ARMxy Computer: The Smart Choice for Field Environment Processing
  16. How AI Enhances Robotics: Key Applications
  17. Common Touchscreen All-in-One Machine Fault Solutions (Part 1)
  18. Essential Structure of Medical Ultrasound Diagnostic Equipment
  19. Setback! China’s Two Major Chip Giants Suffer Heavy Blow

Leave a Comment