How to implement finite state machine in C

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.

state machine in c

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,



26 comments

    1. 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.

  1. 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?

  2. 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.

  3. //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.

  4. 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!

  5. 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.

  6. 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?

  7. 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.

  8. 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

Leave a Reply

Your email address will not be published. Required fields are marked *