Software Haiku

C:\ant buildandtest

C:\me go and get coffee

C:\unit tests fail

State Machine for embedded systems

This is a bit of a trip in the way-back machine for me. I programmed a bunch of embedded off-highway vehicle controllers using C back in the day.

Most of these systems were based on finite state machines. The goal of the programmer is to contain the machine behaviour into a finite set of behaviours based on state history and present inputs.

The hardest part was tracking down bugs which essentially turned Finite State Machines into Infinite State Machines. Global state variables and monolithic switch statements are notoriously easy to turn into spaghetti this way.

The best implementation for state machine I've seen was handed to me for maintenance when I was a junior. I remember it was wicked hard to understand at first. I gummed my first one up because I did not understand all the beauty that it brought.

Once you get over an innate fear of function pointers, it really is a great and simple state machine implementation. BTW, function pointers used this way are much safer than data pointers because the function pointers are never assigned and cannot be null.

Break this thing into several files when your state machine grows.

// I know this first include isn't very embedded. I need it for Sleeping
#include "windows.h"
#include "stdio.h"

// Declare typedefs for state conditions and actions
typedef unsigned char (*ConditionFunction)(void);
typedef void (*ActionFunction)(void);

// The structure defines an action, a condition and a transition
// If the condition is met, the action is executed and the transition occurs
typedef struct _tagState {
 ConditionFunction Condition;
 ActionFunction Action;
 struct _tagState *nextState;
} StateItem;

// Some sample conditions 
unsigned char falseCondition(void) 
{ return 0; }
unsigned char trueCondition(void)
{ return 1; }

// Some sample actions
void SomeAction(void) 
{ printf ("SomeAction\n"); }

void BootAction (void) 
{ printf ("BootAction\n"); }

void NoAction (void) 
{ printf ("NoAction\n"); }

// The state machine engine.
// Simplicity is bliss
StateItem* ProcessState(StateItem *si) {
 while(1) 
 {
  if(si->Condition() == 0)
  {
   si++;
  }
  else
  {
   si->Action();  
   return si->nextState;
  }
 }
}

// Forward declare states so jumping is unhampered
const StateItem OtherState[];
const StateItem BootState[];

/*
*  The tables represent states, each line is a state item
*  Generally, the last state item performs a state action, 
*  and jumps back to itself. Preceeding items are generally
*  transitions out to other states based on conditions
*/

// Except boot, end all the states with a trueCondition and a jump back to self
const StateItem OtherState[] = {
 {&falseCondition, &SomeAction,  OtherState},
 {&trueCondition, &NoAction,   OtherState}
};


const StateItem BootState[] = {
 {&falseCondition, &SomeAction,  BootState},
 {&trueCondition, &BootAction,  OtherState}
};

// Main just runs the state machine (no inputs or outputs are processed)
// The 'tick' time is 1 second which is slow for an embedded system
// but good for demonstrations
int main(void)
{
 StateItem *StatePtr = BootState;

 while (1) {
  StatePtr = ProcessState(StatePtr);
  Sleep(1000);
 }
  
 return 0;
}