Many electronics projects involve the device transitioning from one state to another. On a high level, it could be that your project is initially in a state where it awaits input, and once it receives it, it goes to another state where it performs a series of actions, eventually returning back to the initial state. On a lower level, many communications protocols are often simple or increasingly complex state machines. In many cases, an elegantly implemented state machine can simplify your code and make it easier to manage.

There are several methods to implement state machines programmatically starting from simple if-conditions to state variables and switch structures. In this tutorial I’ll cover a slightly more advanced method of using callbacks or “function pointers” as they are implemented in C. This has some performance benefits, makes up for some clean code, and you’ll learn a bit on the way!

State Machines with Conditionals

First, to introduce the idea of a state machine, lets take a simple example: Blinking LEDs. Imagine you want the LED to turn on for a second, and then turn off. We could do it with a simple 2-state machine:

enum states { 
  LED_ON,
  LED_OFF
};

enum states state = LED_OFF;

while(1) {
  if(state == LED_OFF) {
    led_on();
    state = LED_ON;
  } else {
    led_off();
    state = LED_OFF;
  }
  sleep(1); // sleep for a second
}

If you can understand the code above, you have pretty much grasped the fundamentals of state machines. We have some processing specific to given state, and when we want to go to another state, we use a variable (in this example it’s called state) to do that. And by the way, if you haven’t encountered enum before, you should check out Enumerated type in Wikipedia. It’s a very handful tool to add to your C coding arsenal.

Now let’s add some complexity and say we want the LED to turn on for 2 seconds, then off for 1, again on for 1 second and then off for 3 seconds. We could add more if:s, but let’s use a switch this time (and ignore that this could be implemented in other ways, too):

enum states { 
  LED_ON2S,
  LED_OFF1S,
  LED_ON1S,
  LED_OFF3S
};

enum states state = LED_ON2S;
int secs = 0;

while(1) {
  switch(state) {
  case LED_ON2S:
    led_on(); // make sure LED is on
    if(secs >= 1) {
      state = LED_OFF1S; // turn LED off on next round
      secs = 0;
    }
    break;
  case LED_OFF1S:
    led_off(); // make sure LED is off
    state = LED_ON1S; // LED back on on next round
    break;
  case LED_ON1S:
    led_on();
    state = LED_OFF3S;
    secs = 0; // next state will need this again
    break;
  case LED_OFF3S:
    led_off();
    if(secs >= 2) {
      state = LED_ON2S; // restart cycle on next round
      secs = 0;
    }
    break;
  }

  sleep(1); // sleep for a second
  secs++;
}

Now the important thing here isn’t to understand how exactly the different delays are achieved (and I’m not 100 % sure they work exactly :), but to see the basic structure again: Do some state-specific stuff, and if it’s time to move on, update the state variable.

The code above is still understandable, but let’s say we have 10 states, each taking up 10-20 lines of code. We’ll have a switch with over 100 lines. Furthermore, if the compiler implements the switch with a series of conditionals (which is highly likely), a 10 ifs starts to become a performance issue.

Especially in interrupt handlers with limited clock cycles to spare this will become a serious problem: Let’s imagine a communications protocol running at 250 kHz, where an AVR running at 16 MHz will have 64 clock cycles per interrupt (minus overhead) – a big switch could eat up a significant portion of that! Are there any alternatives?

Function Pointers

To understand function pointers in C, you first need to understand how a processor (or a microcontroller) works. The code you write in C is compiled and translated into machine instructions, which are executed by the processor. Code is stored in memory (for PC, it is in system memory, AVR microcontrollers use Harvard architecture and have a separate instruction memory space, stored in flash memory), and the processor essentially executes an instruction, and then increments a register (usual called the instruction pointer) to read the next instruction.

Conditional structures and function calls are implemented with special instructions that modify the instruction pointer, allowing the processor to jump to another location in the instruction memory. For example, the led_on() function might be 10 instructions located at address 0x1234, and every time it is called, there would be a assembly instruction similar to this:

rcall 0x1234

This would make the processor to jump to that address and continue execution there (call functions also usually save the position where we were before the call, allowing the execution to return back to next instruction after the call returns).

Now function pointer is essentially a variable that holds the instruction address where to jump. By changing the value of that variable, we can change where the rcall goes. It’s easiest to understand by example:

#include <avr/io.h>
#define F_CPU 20000000UL
#include <util/delay.h>

void led_toggle() {
  PINB |= 1;
}

int main() {
  void (*funcptr)() = led_toggle;

  LED_DDR |= 1;

  while(1) {
    (*funcptr)();
    _delay_ms(100);
  }

  return 1;
}

Now if we compile this to assembly with avr-gcc -mmcu=attiny2313 -S example.c and compare the resulting example.s with version that just calls led_toggle() directly, we see the code change a bit:

; Load 16-bit address of led_toggle() to r25:r24 registers
ldi r24,lo8(gs(led_toggle))
ldi r25,hi8(gs(led_toggle))

; Store address bytes to memory
std Y+2,r25
std Y+1,r24

; Some initialization code here

; Main loop
.L4:
  ; Load function pointer to r30:r31 and jump there
  ldd r30,Y+1
  ldd r31,Y+2
  icall

  ; _delay_ms(1000) code here

  ; Loop forever
  rjmp .L4

So essentially, instead of rcall we have two 8-bit load instructions and icall. That’s 7 instruction cycles if someone is counting, which is just 4 more than without the pointer. Pretty nice!

State Machine with Function Pointers

Now how do we benefit from function pointers in the context of a state machine? Simple, just wrap the processing for a given state as a function, and call that:

#include <avr/io.h>
#define F_CPU 20000000UL
#include <util/delay.h>

// States
void led_on();
void led_off();

// State pointer
void (*statefunc)() = led_on;

void led_on() {
  PORTB |= 1;
  statefunc = led_off;
}

void led_off() {
  PORTB &= ~1;
  statefunc = led_on;
}

int main() {
  DDRB |= 1;

  while(1) {
    (*statefunc)();
    _delay_ms(1000); // sleep for a second
  }

  return 1; // should not get here
}

We can make one further addition: Instead of setting a global function pointer, let’s just have the state function to return a pointer to the next state function. This will make the code a bit cleaner with maybe a few clock cycle overhead. We’ll use a typedef and some type casting to make the code a little easier to read:

#include <avr/io.h>
#define F_CPU 20000000UL
#include <util/delay.h>

typedef void *(*StateFunc)();

// States
void *led_on();
void *led_off();

void *led_on() {
  PORTB |= 1;
  return led_off; // next state
}

void *led_off() {
  PORTB &= ~1;
  return led_on; // next state
}

int main() {
  StateFunc statefunc = led_on;

  DDRB |= 1;

  while(1) {
    statefunc = (StateFunc)(*statefunc)();
    _delay_ms(1000); // sleep for a second
  }

  return 1; // should not get here
}

Anyone who can write the code below without a void pointer and a type cast, please give your solution in comments, I’d be interested to see the exact line to do it (extra points if you can typedef the StateFunc as a function pointer that returns a function pointer)!

Advanced Case Example: PS/2

Now it’s quite easy to modify the above example to do the more complex LED blinking routine with delays (just add a global secs variable or have it as parameter and reset it when state function changes), but lets not do that. Instead, I’ll show how I modified my minimal PS/2 key sender to use this structure, and include PS/2 receiving while at it.

To generate a 12.5 kHz square wave and have the data to toggle in the middle of high clock, the code sets up a 50 kHz timer, and uses every 4th timer event (in middle of clock high, that’s where a PS/2 device either manipulates data line or reads data sent from PC) to call the current state handler. Other events are just used to generate the clock signal.

// 50 kHz, 20 us between calls
ISR(TIMER0_COMPA_vect) {
  static uint8_t clockPhase = 1;
  static PS2Callback cbCurrent = cbIdle;

  if(clockPhase & 1) { // Middle of high/low
    if(clockPhase & 2) // High
      cbCurrent = (PS2Callback)(*cbCurrent)();
  } else if(generateClock) { // Transition
    // generateClock is only modified on clock high so additional
    // safeguards for clock left low shouldn't be necessary
    if(clockPhase & 2)
      releaseClock();
    else
      holdClock();
  } 

  clockPhase++;
}

With such a structure, handling individual states becomes dramatically easier, as it’s simple to react to sudden events that make PS/2 implementation quite complex, for example PC wanting to interrupt you in the middle of sending a parity bit:

void *cbSendParity() {
  if(isClockLow()) {
    releaseData(); // make sure data is released
    ps2Error = PS2ERROR_INTERRUPTED;
    return cbInhibit;
  }

  if(stateParity & 1) {
    holdData(); // send zero for odd parity
  } else
    releaseData();

  return cbSendStopBit;
}

As you can see, the handler raises a flag for main program to handle and falls back to state where PC has inhibited communications (that state can then continue with data receiving, for example). But if everything is OK, we can just continue with default state procession and send the stop bit next by returning cbSendStopBit state function pointer in the end of the code.

I recommend you download the advanced example code and study it with a editor that has syntax highlighting. I wouldn’t stress too much about understanding everything in there, just getting the feel how this method can be used for some pretty powerful stuff should be enough. Also worth noting is that the code is not standalone, but needs a main() method and some additional utility functions to actually compile – I’m planning a future post which will cover the whole shebang (and some more!). So stay tuned!