IoT Case Studies IoT Fundamentals

Advantages and Disadvantages of Finite State Machine; Switch-cases, C/C++ Pointers, and Lookup Tables (Part II)

This is the second and final part of our efficient Finite State Machine, FSM, implementation. You can reference the first part of the series and learn some more generalities about Finite State Machines here.

INTRODUCTION

Finite State Machines (FSM) are simply a mathematical computation of a series of cause and events. An FSM is based on states and computes a series of events based on the state of the machine’s inputs, i.e for the state SENSOR_READ if a sensor read is higher than a threshold value, our FSM would trigger a relay (aka a control event) or send an external alert. States are the FSM’s DNA dictating internal behavior or interactions with an environment, such as accepting input or producing an output which may or may not cause the system to change or transition its state. And, it is our job as hardware engineers to choose properly the FSM states and trigger events to obtain the desired behavior that fits the need of our custom development or project.

In part one of this FSM tutorial series, we created an FSM using the classic switch-case implementation. Now we will explore and learn more to create an FSM using C/C++ pointers, which will allow you to develop a more robust application with simpler firmware maintenance expectations.

Note:

The code used in this tutorial was demonstrated at the Arduino day Bogotá by Jose Garcia, one of Ubidots hardware engineers on April 7, 2018. You can see the full code parts and speaker notes here.

The Switch-Case Disadvantages:

In the first part of our FSM tutorial, we looked at the Switch-Case and how to implement a simple routine. Now, we’ll expand on this idea by introducing “Pointers” and how to apply them to simplify your FSM routine.

A switch-case implementation is very similar to an if-else routine; our firmware will loop over each case, evaluate every one of them and see if the trigger case condition is reached. Let’s look at a sample routine below:

switch(state) {
case 1:
/* make some stuff for state 1 */
state = 2;
break;
case 2:
/* make some stuff for state 2 */
state = 3;
break;
case 3:
/* make some stuff for state 3 */
state = 1;
break;
default:
/* make some stuff by default */
state = 1;
}

Above you will find a simple FSM with three states; in the infinite loop the firmware will go to the first case, checks if the state variable equals one, if yes, runs its routine; if not, it proceeds to case 2, checks again the state value; if case 2 is not satisfied, the code execution will move along to case 3, and so until the state is reached, or the cases have been exhausted.

Before getting into the code, let’s understand a bit more about some possible disadvantages of the switch-case or if-else implementations so we can see how to improve our firmware develop.

Let’s suppose that the initial state variable is 3, our firmware will have to make 3 different value validations, this may not be an issue for small FSM but imagine a typical industrial production machine with hundreds or thousands of states. The routine will need to make several useless value checks, ultimately resulting in an inefficient use of resources. This inefficiency becomes our first disadvantage – the microcontroller is limited in resources and will be overloaded with inefficiency FSM routines. Accordingly, it is our duty as intelligent engineers to save as much many computing resources on the microcontroller as possible.

Now, imagine again a FSM with thousands of states, if you are a new developer and need to implement a change in one of those states you will have to look into thousands of lines inside your main loop() routine, this routine usually may include a lot of other stuff not related with the machine itself so it becomes a little hard to begin a debug if you center all the FSM logic inside the main loop(). Here comes the second problem, with switch – case routines you create can be unnecessarily complex FSM that is too long to debug errors.

Finally, a code with a bunch of if-else or thousands of switch-case is not elegant nor readable the majority of embedded programmers – this being the final disadvantage.

C/C++ Pointers

Now let’s see how can we implement a concise FSM using C/C++ pointers. A pointer, as its name, suggests, ‘points’ to somewhere inside the microcontroller. In C/C++, a “pointer” points to a memory address and is intended to retrieve information from the said memory address. A pointer is used to get the stored value of a variable during execution time without knowing specifically the memory address of the variable itself. Using pointers properly will be a huge benefit to the structure of your routine and the simplicity to maintain or edit the programming in the future.

Point Code Example:

int a = 1462;
int myAddressPointer = &a;
int myAddressValue = *myAddressPointer;

Let’s analyze what happens in the code above. The variable myAddressPointer points to the memory address of variable a (1462), while the variable myAddressValue retrieves the value of the memory address pointed to by myAddressPointer. Accordingly, it can be expected to get a value of 874 from myAddressPointer and of 1462 for myAddressValue. Why is this useful for our use-case? Because in memory we do not store only values, we also store the functions and methods’ behaviors. For example, the memory space 874 is storing the 1462 value, but this storage address can also manage functions to calculate a current intensity in kA that is stored. Using pointers we gain access to this added functionality and usability of memory addresses without the need to declare a function statement in another part of the code. A typical function pointer can be implemented as below:

void (*funcPtr) (void);

Can you imagine how to use this tool in our FSM? You can just create a dynamic pointer that ‘points’ to the different functions or states of our FSM instead of a variable. If we have a single variable that stores a pointer that dynamically changes where it ‘points’ we would change the FSM states based on the input conditions, this being the true value of pointers for our use case.

Lookup tables

Let’s review another important concept, lookup tables or LUT. LUT is an ordered way to store data, basically, it is a structure type data that stores predefined values. They will be useful for us to store data inside our FSM values.

The main advantage of the LUT is that if they are statical declared; their values can be accessed through memory address which is a very effective value access way in C/C++. Below you can find a typical declaration for LUT for an FSM

void (*const state_table [MAX_STATES][MAX_EVENTS]) (void) =
{ action_s1_e1, action_s1_e2 }, /* procedures for state
{ action_s2_e1, action_s2_e2 }, /* procedures for state
{ action_s3_e1, action_s3_e2 } /* procedures for state
};

It has been a lot of concepts to digest, but they are necessary to implement our new efficient FSM, let’s code it so you can see how easy this kind of FSM can grow in time.

Note: The full code of the FSM can be found here, for simplicity we have split it into 5 parts to make its explanation easier.

Coding

We will create a simple FSM to implement a blink led routine, with this you can adapt the example for your own needs. We will have 2 states: ledOn and ledOff for the FSM and the led will turn off and on every second. Let’s begin.

***********************************
   STATE MACHINE SETUP
 ***********************************/
​
/*
   State machine valid states
*/
typedef enum {
  LED_ON,
  LED_OFF,
  NUM_STATES
} StateType;
​
/*
   State machine table structure
*/
​
typedef struct {
  StateType State;
​
  // Create the function pointer
  void (*function)(void);
} StateMachineType;

The first part is to implement our LUT is to create our states, conveniently we use the enum() method to assign a value of 0 and 1 to our states. The max number of states is also assigned with a value of 2 that makes sense with our FSM architecture. This typedef will be labeled as StatedType so we can instantiate later it in our code.

Next, we create a structure to store our states. See that we also declare a pointer labeled as function, this will be our dynamic memory pointer to call in execution the different FSM states.

/*
    Initial SM state and functions declaration
*/
​
StateType SmState = LED_ON;
​
void Sm_LED_ON();
void Sm_LED_OFF();
​
/*
   LookUp table with states and functions to execute
*/
​
StateMachineType StateMachine[] =
{
  {LED_ON, Sm_LED_ON},
  {LED_OFF, Sm_LED_OFF}
};

Here we create an instance from our states instance with the initial state LED_ON, and we declare our two states and finally create our LUT. See how are related both state declaration and behavior in the LUT so we can access its values easily through its int indexes, aka, to access to the sm_LED_ON() method we should code something like StateMachineInstance[0]; .

/*
   Custom State Functions routines
*/
​
void Sm_LED_ON() {
  // Custom Function Code
  digitalWrite(LED_BUILTIN, HIGH);
  delay(1000);
​
  // Move to next state
  SmState = LED_OFF;
}
​
void Sm_LED_OFF() {
  // Custom Function Code
  digitalWrite(LED_BUILTIN, LOW);
  delay(1000);
​
  // Move to next state
  SmState = LED_ON;
}

In the above code, our methods logic is implemented and includes nothing special besides the state number update at the end of every function.

/*
   Main function state change routine
*/
​
void Sm_Run(void) {
  // Makes sure that the actual state is valid
  if (SmState < NUM_STATES) {
    (*StateMachine[SmState].function) ();
  }
  else {
    // Error exception code
    Serial.println("[ERROR] Not valid state");
  }
}

The functionSm_Run() is the heart of our FSM. Notice that we use a pointer, *, to extract the function memory position from our LUT,  as during execution time we will access dynamically to a memory position in the LUT. The Sm_Run()will always execute multiple instructions, aka FSM events, already stored in a memory address of the microcontroller.

/***********************************
   MAIN ARDUINO FUNCTIONS
 ***********************************/
​
void setup() {
  // put your setup code here, to run once:
  pinMode(LED_BUILTIN, OUTPUT);
}
​
void loop() {
  // put your main code here, to run repeatedly:
  Sm_Run();
}

Our main Arduino functions are now really simple, the infinite loop is always running with the state change routine previously defined. This function will be the one that handles the event to trigger and also to update the actual FSM state.

Conclusions

In this part two of the Finite State Machines and C/C++ Pointers we reviewed the main disadvantages of switch-case FSM routines and identified pointers as a suitable and desirable option to save memory and increase the microcontroller’s functionality.
In review, here are some of the advantages and disadvantages of using pointers in your Finite State Machine Routine:

Advantages:

  • If you need to add more states, you have to simply declare the new transition method and update the lookup table; the main function will be the same.
  • You do not have to perform every if-else statements, the pointer lets the firmware ‘go’ to the desired set of instructions in the memory of the microcontroller.
  • This is a C concise and professional way to implement FSM.

Disadvantages:

  • You need more static memory to store the lookup table that stores the events of the FSM.