How to implement finite state machine in C

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;
}