Techniques and Strategies for Implementing State Machine Design in C Language
The state machine pattern is a behavioral pattern, and using polymorphism to implement the switching behavior of different states is indeed a very good approach. It’s just a pity that in embedded environments, sometimes only pure C code can be written, and considerations such as code reentrancy and multi-task request jumps are also needed, so implementing it really requires careful thought.
Recently, while looking at an open-source system, I came across the implementation of a state machine, so I tried writing one myself and am sharing it with everyone.
First, let’s analyze what an ordinary state machine actually needs to accomplish.
A state machine stores changes from the starting moment to the present, and based on the current input, decides the next state. This means that the state machine needs to store states, obtain inputs (which we call transition conditions), and make responses.
As shown in the figure above, {s1, s2, s3} are all states, and the arrow c1/a1 indicates that when in state s1 and the input is c1, it jumps to s2 and performs operation a1. At the bottom is a set of inputs, and the state machine should respond as follows:
When a specific state encounters an unrecognized input, it defaults to entering a trap state; once in the trap state, no matter what input is received, it is impossible to exit. To represent this automaton, we define its states and input types as follows:
typedef int State; typedef int Condition; #define STATES 3 + 1 #define STATE_1 0 #define STATE_2 1 #define STATE_3 2 #define STATE_TRAP 3 #define CONDITIONS 2 #define CONDITION_1 0 #define CONDITION_2 1
In an embedded environment, due to limited storage space, all such elements are defined as macros. Furthermore, to minimize uncertainty in execution time, we utilize an O(1) jump table to simulate state transitions. First, we define the jump types:
typedef void (*ActionType)(State state, Condition condition); typedef struct { State next; ActionType action; } Trasition, * pTrasition;
Then, following the transition relationships shown in the figure above, first define the three transitions plus one trap transition:
// (s1, c1, s2, a1)
Trasition t1 = {
STATE_2,
action_1
};
// (s2, c2, s3, a2)
Trasition t2 = {
STATE_3,
action_2
};
// (s3, c1, s2, a3)
Trasition t3 = {
STATE_2,
action_3
};
// (s, c, trap, a1)
Trasition tt = {
STATE_TRAP,
action_trap
}; The actions involved are to be performed by the user; here, only a single output statement is defined.
void action_1(State state, Condition condition)
{
printf("Action 1 triggered.
");
} Then, by defining a jump table, the jump relationships described above can be expressed.
pTrasition transition_table[STATES][CONDITIONS] = {
/* c1, c2*/
/* s1 */&t1, &tt,
/* s2 */&tt, &t2,
/* s3 */&t3, &tt,
/* st */&tt, &tt,
}; Finally, we define the state machine. If we do not need to account for multi-task requests, the state machine simply needs to store the current state—for example:
typedef struct
{
State current;
} StateMachine, * pStateMachine;
State step(pStateMachine machine, Condition condition)
{
pTrasition t = transition_table[machine->current][condition];
(*(t->action))(machine->current, condition);
machine->current = t->next;
return machine->current;
} However, a problem of data inconsistency arises when a state transition is already in progress and another task simultaneously requests a transition. For instance, if Task 1 (s1, c1/a1 → s2) and Task 2 (s2, c2/a2 → s3) execute sequentially, the system can successfully reach state s3. Yet, if Task 2 preempts execution control while operation a1 is running, the current state perceived by Task 2 remains s1; encountering condition c2 in state s1 causes the system to enter a “trap” state rather than reaching s3. In other words, the state transition becomes nondeterministic—an outcome that is intolerable. Consequently, the state machine must be redesigned to incorporate an “in-transaction” condition and a condition queue for storing inputs. The revised code is as follows:
#define E_OK 0
#define E_NO_DATA 1
#define E_OVERFLOW 2
typedef struct
{
Condition queue[QMAX];
int head;
int tail;
bool overflow;
} ConditionQueue, * pConditionQueue;
int push(ConditionQueue * queue, Condition c)
{
unsigned int flags;
Irq_Save(flags);
if ((queue->head == queue->tail + 1) || ((queue->head == 0) && (queue->tail == 0)))
{
queue->overflow = true;
Irq_Restore(flags);
return E_OVERFLOW;
}
else
{
queue->queue[queue->tail] = c;
queue->tail = (queue->tail + 1) % QMAX;
Irq_Restore(flags);
}
return E_OK;
}
int poll(ConditionQueue * queue, Condition * c)
{
unsigned int flags;
Irq_Save(flags);
if (queue->head == queue->tail)
{
Irq_Restore(flags);
return E_NO_DATA;
}
else
{
*c = queue->queue[queue->head];
queue->overflow = false;
queue->head = (queue->head + 1) % QMAX;
Irq_Restore(flags);
}
return E_OK;
}
typedef struct
{
State current;
bool inTransaction;
ConditionQueue queue;
} StateMachine, * pStateMachine;
static State __step(pStateMachine machine, Condition condition)
{
State current = machine -> current;
pTrasition t = transition_table[current][condition];
(*(t->action))(current, condition);
current = t->next;
machine->current = current;
return current;
}
State step(pStateMachine machine, Condition condition)
{
Condition next_condition;
int status;
State current;
if (machine->inTransaction)
{
push(&(machine->queue), condition);
return STATE_INTRANSACTION;
}
else
{
machine->inTransaction = true;
current = __step(machine, condition);
status = poll(&(machine->queue), &next_condition);
while(status == E_OK)
{
__step(machine, next_condition);
status = poll(&(machine->queue), &next_condition);
}
machine->inTransaction = false;
return current;
}
}
void initialize(pStateMachine machine, State s)
{
machine->current = s;
machine->inTransaction = false;
machine->queue.head = 0;
machine->queue.tail = 0;
machine->queue.overflow = false;
}