The finite state machine (also known as the state machine) on pure С
Almost every microcontroller came across a huge switch-case and painfully debugged them.
And a lot of people, starting to write the implementation of a protocol, thought about how to write it beautifully, gracefully, so that in a month it was clear what you meant, so that it would not wipe out all the memoryand generally crap with butterflies .
And it is here that state machines come to the rescue, they are also finite automata (the ones that are used in regular expressions ).
Actually through regular expressions I came to them.
Recently, I needed to implement simple device functionality with 4 buttons — highlighting two code sequences in potentially chaotic button presses and performing certain actions when a sequence is found.
Let me explain with an example: there are 4 buttons - A, B, C, D and the ACDA code sequence. Then, when pressing B, C, A, D, A, C, D, A, B consecutively, the device should light a light bulb after the 8th (last but one) pressing. From the point of view of regular expressions, the task is simple - we are looking for the substring ACDA in the input line. Once found - light a light bulb. But I didn't want to drag any library for working with regexp into the microcontroller. I felt that everything could be done by myself and easier. Then I decided to try to independently implement the state machine corresponding to the search for this subsequence.
')
And now - a little theory and practice:
The main feature of state machines is that they are described by a set of possible states, a set of signals (events) and a transition table. The transition table is a comparison of the pair from the current state and the incoming signal of the new state.
Imagine that we have an automaton with 3 states and 3 signals that need to be processed. Upon the arrival of each signal, the automat makes a transition to a new state.
Obviously, this code is not very readable and will grow catastrophically with an increase in the number of states and signals.
In addition, if we want to add a single-type action to each transition (for example, logging is something like
Note that the essence of two nested switches is a choice from a table (column and column) and recall that formally, finite automata are conveniently written in a transition table where each row corresponds to a signal, each column corresponds to a state, and at the intersection the state is written machine.
Let's try to simplify the existing code by setting the transition table, sorry for taftology, with the table.
The demonstrated type of data initialization is known as designated inits and was introduced in C99.
Now we need to process the resulting data structure - we write the function doFSM_table:
The code is simpler and clearer, right?
Now a few more bonuses of this record:
To make the resulting automaton even more universal and give it the opportunity to perform some actions other than transition by states, add pointers to handler functions in the table corresponding to the transitions:
In general, this mechanism can be improved for a long time, but this article aims not to develop a universal library for the implementation of finite automata, but to demonstrate how some tasks can be solved much simpler and more compact than in the forehead, without resorting to any sophisticated libraries or languages.
In conclusion, I will give a table that turned out for the task of searching for a subsequence with which I started:
And a lot of people, starting to write the implementation of a protocol, thought about how to write it beautifully, gracefully, so that in a month it was clear what you meant, so that it would not wipe out all the memory
And it is here that state machines come to the rescue, they are also finite automata (the ones that are used in regular expressions ).
Actually through regular expressions I came to them.
Recently, I needed to implement simple device functionality with 4 buttons — highlighting two code sequences in potentially chaotic button presses and performing certain actions when a sequence is found.
Let me explain with an example: there are 4 buttons - A, B, C, D and the ACDA code sequence. Then, when pressing B, C, A, D, A, C, D, A, B consecutively, the device should light a light bulb after the 8th (last but one) pressing. From the point of view of regular expressions, the task is simple - we are looking for the substring ACDA in the input line. Once found - light a light bulb. But I didn't want to drag any library for working with regexp into the microcontroller. I felt that everything could be done by myself and easier. Then I decided to try to independently implement the state machine corresponding to the search for this subsequence.
')
And now - a little theory and practice:
The main feature of state machines is that they are described by a set of possible states, a set of signals (events) and a transition table. The transition table is a comparison of the pair from the current state and the incoming signal of the new state.
Imagine that we have an automaton with 3 states and 3 signals that need to be processed. Upon the arrival of each signal, the automat makes a transition to a new state.
The most intuitive, but cumbersome code for a similar task:
enum states { initial = 0, state_1, state_final }; enum signals { sign0, sign1, sign_N }; enum signals getSignal(); void doFSM() { enum states current_state = initial; while (1) { enum signals current_signal = getSignal(); switch (current_state) { case initial: switch (current_signal) { case sign0: current_state = state_1; break; case sign1: current_state = initial; break; case signN: current_state = state_1; break; } break; case state_1: switch (current_signal) { case sign0: current_state = initial; break; case sign1: current_state = state_1; break; case signN: current_state = state_final; break; } break; case state_final: switch (current_signal) { case sign0: current_state = initial; break; case sign1: current_state = initial; break; case signN: current_state = initial; break; } break; } } } Obviously, this code is not very readable and will grow catastrophically with an increase in the number of states and signals.
In addition, if we want to add a single-type action to each transition (for example, logging is something like
printf("Current = %d, signal = %d\n", current_state, current_signal); ), then it will generate a bunch of changes in the code. When editing such changes, some error will almost certainly be made and debugging will turn into hell.Note that the essence of two nested switches is a choice from a table (column and column) and recall that formally, finite automata are conveniently written in a transition table where each row corresponds to a signal, each column corresponds to a state, and at the intersection the state is written machine.
Let's try to simplify the existing code by setting the transition table, sorry for taftology, with the table.
enum states FSM_table[3][3] = { [initial][sign0] = state_1, [initial][sign1] = initial, [initial][sign_N] = state_1, [state_1][sign0] = initial, [state_1][sign1] = state_1, [state_1][sign_N] = state_final, [state_final][sign0] = initial, [state_final][sign1] = initial, [state_final][sign_N] = initial }; The demonstrated type of data initialization is known as designated inits and was introduced in C99.
Now we need to process the resulting data structure - we write the function doFSM_table:
void doFSM_table() { enum states current_state = initial; while (1) { enum signals current_signal = getSignal(); current_state = FSM_table[current_state][current_signal]; } } The code is simpler and clearer, right?
Now a few more bonuses of this record:
- There is nothing easier than adding a debugging output to every step of the machine:doFSM_table with debugging output
void doFSM_table() { enum states current_state = initial; while (1) { enum signals current_signal = getSignal(); enum states new_state = FSM_table[current_state][current_signal]; printf("Current = %d, signal = %d, new = %d\n", current_state, current_signal, new_state); current_state = new_state; } } - the collected binary code will decrease significantly, which is very useful in microcontrollers
- if necessary, the transition table can be changed directly at run time, for example, when loading a new configuration
To make the resulting automaton even more universal and give it the opportunity to perform some actions other than transition by states, add pointers to handler functions in the table corresponding to the transitions:
Random action automaton at each transition
typedef void (*transition_callback)(enum states state, enum signals signal); struct transition { enum states new_state; transition_callback worker; }; void initial_1_fxn(enum states state, enum signals signal); void initial_1N_fxn(enum states state, enum signals signal); void fxn2(enum states state, enum signals signal); void fxn3(enum states state, enum signals signal); void to_initial_fxn(enum states state, enum signals signal); struct transition FSM_table[3][3] = { [initial][sign0] = {state_1, initial_1_fxn}, [initial][sign1] = {initial, NULL}, [initial][sign_N] = {state_1, initial_1N_fxn}, [state_1][sign0] = {initial, fxn2}, [state_1][sign1] = {state_1, fxn3}, [state_1][sign_N] = {state_final, NULL}, [state_final][sign0] = {initial, to_initial_fxn}, [state_final][sign1] = {initial, to_initial_fxn}, [state_final][sign_N] = {initial, to_initial_fxn} }; void doFSM_table() { enum states current_state = initial; while (1) { enum signals current_signal = getSignal(); enum states new_state = FSM_table[current_state][current_signal].new_state; transition_callback worker = FSM_table[current_state][current_signal].worker; if (worker != NULL) { worker(current_state, current_signal); } current_state = new_state; } } In general, this mechanism can be improved for a long time, but this article aims not to develop a universal library for the implementation of finite automata, but to demonstrate how some tasks can be solved much simpler and more compact than in the forehead, without resorting to any sophisticated libraries or languages.
In conclusion, I will give a table that turned out for the task of searching for a subsequence with which I started:
The resulting state table is:
enum states FSM_table[9][4] = { [initial ... sACDA][bA ... bD] = initial, // . [initial][bA] = sA, // // ABADC [sA][bB] = sAB, [sAB][bA] = sABA, [sABA][bD] = sABAD, [sABAD][bC] = sABADC, // ACDA [sA][bC] = sAC, [sAC][bD] = sACD, [sACD][bA] = sACDA }; Source: https://habr.com/ru/post/241941/
All Articles