Nowadays many applications either small or complex use the finite state machine (FSM). A finite state machine in C is one of the popular design patterns for the embedded system. A finite state machine makes the development easy and smooth.
There are a lot of devices which use event base states, like coffee machine, vending machine, POS devices, door lock system, etc. Some POS devices are used the event table in which events are registered with an event handler. This event handler executes when the relevant events come.
A finite state machine can have multiple states, it can switch from one state to another state on the basis of internal or external input. This input could be timer expiry signal, hardware or software interrupt .. etc. In the finite state machine, the procedure to change one state to another state is called transition.
In this article, I will describe some approaches for implementing a state machine in C.
For example, I am considering an ATM machine and creating its sample state machine in C. The state of the ATM machine could be changed through the coming events. I have mentioned below the sample stats of the ATM machine.
Here I have found a very useful Embedded Systems Programming courses for beginners, as well as experienced mobile and desktop software developers by Jeremy Willden.
The Sample States of the ATM Â machine.
- Idle State
- Card Inserted State
- Pin entered State
- Option Selected State
- Amount Entered State
Initially, the ATM machine would be in the Idle state, When a user inserts the card then it change their state and processes the card. After the card processing, ATM again changes their state and ask the user to enter the pin number. When the user entered the pin then it asks for choice ( Balance inquiry, withdrawal, Deposit) and after that change the state and ask to enter the amount and dispatch the entered amount.
Above figure describe the states of the ATM machine.
Recommended steps to create the state machine
- Gather the information which the user wants.
- Analyze the all gather information and sketch the state transition diagram.
- create a code skeleton of the state machine.
- Make sure the transition (changing state) work properly
- Implement all the required information in the code skeleton of the state machine.
- Test the implemented state machine.
There are two most popular approaches for implementing an event-based state machine in C. The selection of both approaches depends on the requirement and situations.
- Using the conditional statement (nested switch or nested if-else).
- Using the lookup table
Using the conditional statement
This is the simplest way to implement the state machine. We have used if-else or the switch case to check the states and triggered the event. If the combination of states and triggered an event match, execute the event handler to serve the service and update the next state. It depends on a requirement that checks first states or the event.
In the below sample code, I am verifying the states first and after that checks the triggered event. If you want you can reverse the procedure that means you can check the event first and after that checks the states.
#include <stdio.h> //Different state of ATM machine typedef enum { Idle_State, Card_Inserted_State, Pin_Eentered_State, Option_Selected_State, Amount_Entered_State, } eSystemState; //Different type events typedef enum { Card_Insert_Event, Pin_Enter_Event, Option_Selection_Event, Amount_Enter_Event, Amount_Dispatch_Event } eSystemEvent; //Prototype of eventhandlers eSystemState AmountDispatchHandler(void) { return Idle_State; } eSystemState EnterAmountHandler(void) { return Amount_Entered_State; } eSystemState OptionSelectionHandler(void) { return Option_Selected_State; } eSystemState EnterPinHandler(void) { return Pin_Eentered_State; } eSystemState InsertCardHandler(void) { return Card_Inserted_State; } int main(int argc, char *argv[]) { eSystemState eNextState = Idle_State; eSystemEvent eNewEvent; while(1) { //Read system Events eSystemEvent eNewEvent = ReadEvent(); switch(eNextState) { case Idle_State: { if(Card_Insert_Event == eNewEvent) { eNextState = InsertCardHandler(); } } break; case Card_Inserted_State: { if(Pin_Enter_Event == eNewEvent) { eNextState = EnterPinHandler(); } } break; case Pin_Eentered_State: { if(Option_Selection_Event == eNewEvent) { eNextState = OptionSelectionHandler(); } } break; case Option_Selected_State: { if(Amount_Enter_Event == eNewEvent) { eNextState = EnterAmountHandler(); } } break; case Amount_Entered_State: { if(Amount_Dispatch_Event == eNewEvent) { eNextState = AmountDispatchHandler(); } } break; default: break; } } return 0; }
Using the lookup table
A lookup table is also a very good technique to implement the state machine. Using the c language we can implement a lookup table in many ways. In the below section, I am describing some ways to implement the state machine using the function pointer and lookup table.
A state machine in c using a 2D array
We will create a 2D array containing the function pointers. In which rows and columns represented by the states and events of the finite state machine. This 2D array initializes using the designated initializer.
It is the simplest way to implement the state machine, using this technique we can reduce the length of the code. The most important feature of this technique in the future if you want to add any new states or events, we can easily integrate with it without any huge hurdle.
Let’s see an example,
#include <stdio.h> //Different state of ATM machine typedef enum { Idle_State, Card_Inserted_State, Pin_Eentered_State, Option_Selected_State, Amount_Entered_State, last_State } eSystemState; //Different type events typedef enum { Card_Insert_Event, Pin_Enter_Event, Option_Selection_Event, Amount_Enter_Event, Amount_Dispatch_Event, last_Event } eSystemEvent; //typedef of 2d array typedef eSystemState (*const afEventHandler[last_State][last_Event])(void); //typedef of function pointer typedef eSystemState (*pfEventHandler)(void); //function call to dispatch the amount and return the ideal state eSystemState AmountDispatchHandler(void) { return Idle_State; } //function call to Enter amount and return amount enetered state eSystemState EnterAmountHandler(void) { return Amount_Entered_State; } //function call to option select and return the option selected state eSystemState OptionSelectionHandler(void) { return Option_Selected_State; } //function call to enter the pin and return pin entered state eSystemState EnterPinHandler(void) { return Pin_Eentered_State; } //function call to processing track data and return card inserted state eSystemState InsertCardHandler(void) { return Card_Inserted_State; } int main(int argc, char *argv[]) { eSystemState eNextState = Idle_State; eSystemEvent eNewEvent; // Table to define valid states and event of finite state machine static afEventHandler StateMachine = { [Idle_State] ={[Card_Insert_Event]= InsertCardHandler }, [Card_Inserted_State] ={[Pin_Enter_Event] = EnterPinHandler }, [Pin_Eentered_State] ={[Option_Selection_Event] = OptionSelectionHandler}, [Option_Selected_State] ={[Amount_Enter_Event] = EnterAmountHandler}, [Amount_Entered_State] ={[Amount_Dispatch_Event] = AmountDispatchHandler}, }; while(1) { // assume api to read the next event eSystemEvent eNewEvent = ReadEvent(); //Check NULL pointer and array boundary if( ( eNextState < last_State) && (eNewEvent < last_Event) && StateMachine[eNextState][eNewEvent]!= NULL) { // function call as per the state and event and return the next state of the finite state machine eNextState = (*StateMachine[eNextState][eNewEvent])(); } else { //Invalid } } return 0; }
One thing needs to remember, here table is sparse, if the states and events are increasing, this technique increases the wastage of the memory. So before creating the state machine diagram we need to account all the things very precisely at the beginning of the design.
State machine using an array of structure
This is an elegant way to create a finite state machine. The states and events of the state machine are encapsulated in a structure with a function pointer (Event handler) Â call at the proper state and event.
#include <stdio.h> //Different state of ATM machine typedef enum { Idle_State, Card_Inserted_State, Pin_Eentered_State, Option_Selected_State, Amount_Entered_State, last_State } eSystemState; //Different type events typedef enum { Card_Insert_Event, Pin_Enter_Event, Option_Selection_Event, Amount_Enter_Event, Amount_Dispatch_Event, last_Event } eSystemEvent; //typedef of function pointer typedef eSystemState (*pfEventHandler)(void); //structure of state and event with event handler typedef struct { eSystemState eStateMachine; eSystemEvent eStateMachineEvent; pfEventHandler pfStateMachineEvnentHandler; } sStateMachine; //function call to dispatch the amount and return the ideal state eSystemState AmountDispatchHandler(void) { return Idle_State; } //function call to Enter amount and return amount entered state eSystemState EnterAmountHandler(void) { return Amount_Entered_State; } //function call to option select and return the option selected state eSystemState OptionSelectionHandler(void) { return Option_Selected_State; } //function call to enter the pin and return pin entered state eSystemState EnterPinHandler(void) { return Pin_Eentered_State; } //function call to processing track data and return card inserted state eSystemState InsertCardHandler(void) { return Card_Inserted_State; } //Initialize array of structure with states and event with proper handler sStateMachine asStateMachine [] = { {Idle_State,Card_Insert_Event,InsertCardHandler}, {Card_Inserted_State,Pin_Enter_Event,EnterPinHandler}, {Pin_Eentered_State,Option_Selection_Event,OptionSelectionHandler}, {Option_Selected_State,Amount_Enter_Event,EnterAmountHandler}, {Amount_Entered_State,Amount_Dispatch_Event,AmountDispatchHandler} }; //main function int main(int argc, char *argv[]) { eSystemState eNextState = Idle_State; while(1) { //Api read the event eSystemEvent eNewEvent = read_event(); if((eNextState < last_State) && (eNewEvent < last_Event)&& (asStateMachine[eNextState].eStateMachineEvent == eNewEvent) && (asStateMachine[eNextState].pfStateMachineEvnentHandler != NULL)) { // function call as per the state and event and return the next state of the finite state machine eNextState = (*asStateMachine[eNextState].pfStateMachineEvnentHandler)(); } else { //Invalid } } return 0; }
Recommended Articles for you,
- How to pass an array as a parameter in C?
- How to access a two-dimensional array using pointers in C?
- Brief Introduction of switch case in C.
- A brief description of the pointer in C.
- Dangling, Void, Null and Wild Pointers
- How to use a function pointer in C?
- Replace the nested switch case using an array and function pointer.
- Function pointer in structure.
- Pointer Arithmetic in C.
- void pointer in C.
- 10 questions about dynamic memory allocation.
- Memory Layout in C.
- 100 C interview Questions
- File handling in C.
- C format specifiers.
Nice article on the basics. Thank you
Thank you John..
eSystemEvent eNewEvent = ReadEvent();
Can you explain this line?
In this article ReadEvent() behaves like the third party or standard library which returns the current occurred event. For example, In POS device we have read function which when you pressed the key, swipe the card or insert the card then it returns relevant event value. On the basis of this event value, you call the relevant function, like when you swipe the card in POS device then an event value (MAG_CARD_EVENT) return by the read function.
Thank you.
So, basically, this function will vary for each program?
It is not vary for program but vary with device, each device have their own API to read the events.
got it. Thank you
From where can I learn these type of embedded programming?
Some embedded applications include making task array and then their functionality is similar to an operating system. How can I learn these types of the programs?
There are a lot of magazines which is published the article regarding the Finite state machine.
What if we have timer based events. For example, upon occurrence “Card_Insert_Event”, the state will be changed to “Card_Inserted_State”, then let say we start two timers t1 and t2 (t1 < t2). now the expected event is "Pin_Enter_Event" within t1 expires. if t1 expires and no event then we ask "Do you want more time" and if even t2 expires and no event then next state will be "Idle_state".
Can I know how to add timers and how to handle them. Thank you.
//structure of state and event with event handler
typedef struct
{
eSystemState eStateMachine;
eSystemEvent eStateMachineEvent;
pfEventHandler pfStateMachineEvnentHandler;
}sStateMachine;
do you really need to include the “eSystemState eStateMachine; ” in this structure, in fact I don’t see you using that any where.
the next state is determined by the array index rather than the “eSystemState eStateMachine; ” variable. In the below code, you have placed the array elements aligning with the enumeration values.
sStateMachine asStateMachine [] = {
{Idle_State,Card_Insert_Event,InsertCardHandler},
{Card_Inserted_State,Pin_Enter_Event,EnterPinHandler},
{Pin_Eentered_State,Option_Selection_Event,OptionSelectionHandler},
{Option_Selected_State,Amount_Enter_Event,EnterAmountHandler},
{Amount_Entered_State,Amount_Dispatch_Event,AmountDispatchHandler}
};
I suppose you’ve created an additional variable just to avoid confusion while creating the table.
thanks
I am not able to write the read_event() for my state machine program . Can you please help me
Hi, nice example.
I’m referring now to the last implementation so the “State machine using an array of structure”.
Concerning the ATM machine of this example suppose to have to manage more than one single transition from each state.
Suppose to be into the Idle State and no event occur, I suppose to have to add another entry into the asStateMachine, name it with Nothing_To_Do_Event (of course I’ve also to add it to the eSystemEvent struct):
sStateMachine asStateMachine [] = {
{Idle_State ,Nothing_To_Do_Event ,IdleStateHandler},
{Idle_State ,Card_Insert_Event ,InsertCardHandler},
{Card_Inserted_State ,Pin_Enter_Event ,EnterPinHandler},
{Pin_Eentered_State ,Option_Selection_Event ,OptionSelectionHandler},
{Option_Selected_State ,Amount_Enter_Event ,EnterAmountHandler},
{Amount_Entered_State ,Amount_Dispatch_Event ,AmountDispatchHandler}
};
Now when I’m into the main loop I suppose to have also to change the selection logic for the next state because I can have more than a single entry for each state, so the main function has to rewritten in a similar way:
int main(int argc, char *argv[])
{
// Init FSM state and event
eSystemState eNextState = Idle_State;
int i=0;
while(1)
{
// ————————————————————
// FSM core
// ————————————————————
// Perform the event reading task
eSystemEvent eNewEvent = read_event();
// Check if the state is valid
if ( (eNextState < last_State) && (eNewEvent < last_Event) )
{
// Looking for the correct state-event
for( i=0; i < sizeof(asStateMachine)/sizeof(asStateMachine[0]); i++ )
{
if( (asStateMachine[i].eStateMachine == eNextState) &&
(asStateMachine[i].eStateMachineEvent == eNewEvent) )
{
//state match
eNextState = (*asStateMachine[eNextState].pfStateMachineEventHandler)();
break;
}
}
}
else
{
//Invalid
}
// ————————————————————
// EXECUTION OF OTHER CODE
// ————————————————————
// … other stuff here …
}
return 0;
}
make sense?
Thank!
I think this line
eNextState = (*asStateMachine[eNextState].pfStateMachineEventHandler)();
should be
eNextState = (*asStateMachine[i].pfStateMachineEventHandler)();
Before changing it, you code didn’t follow the ATM state transitions.
I am not able to write the read_event() for my state machine program . Can you please help me
It is only an assumed function.
You’ve based your solutions upon a weak assumptions: a) neither state has more than one output path, but in real life a state can commute from two or more events. Even more, b) neither state returns to its caller. Do your solutions handle well those scenarios?
I’ve answered myself: No, the array of structs solution does not handle multiple events in the same state (b). And the (a) problem is an easy one to solve.
Hello Amlendra,
This post is too good for beginners. I need to ask one simple question We have so much algoriths in C like sorting, data structures but first time I encountered there is something which exists known as state machine. Can you name some of the techniques I want to learn more