Code and Life

Programming, electronics and other cool tech stuff

Supported by

Supported by Picotech

Tutorial: State Machines with C Callbacks

State machine

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!

19 comments

Rafael Carrascosa:

Great technique! I’ll keep that close just in case :)
Thank you for sharing!

Christopher Williams:

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)!

I think this is what you want:

typedef void (*funcptr)();
typedef funcptr (*StateFunc)();

// States
StateFunc led_on();
StateFunc led_off();

This is a good read too: http://c-faq.com/decl/recurfuncp.html

Joonas Pihlajamaa:

Cool! Thanks also for the link, a very good read.

Pete Vidler:

Nice article. I often use a table-based approach for this sort of thing, myself:

http://petevidler.com/2011/03/handling-delays-without-blocking/

Rose Ames:

Great article! But are you sure that a compiler will turn a case statement into a chain of conditionals? I would expect it to use a branch table (at least if the case values are sequential integers, as they would be in your example).

Joonas Pihlajamaa:

I did a test compile with switch on integers 0 to 9 calling functions do0() to do9(), and at least without optimization the while(1) switch(++state) part compiles to 80 lines of assembly loads, comparisons and conditional jumps.

Joonas Pihlajamaa:

-O1 and -O2 on the other hand seems to do result in a branch table, so on that level there is no performance increase with function pointers, it’s then only about C code elegance (big switch vs. function pointers). Good call!

Søren Poulsen:

It’s possible to break the type recursion using a struct instead of void *.

typedef struct functor functor;
struct functor {
functor (*call)();
};
inline functor wrap(struct functor(*b)()) {
struct functor a = {b};
return a;
}

functor led_on();
functor led_off();

functor led_on() {
return wrap(led_off); // next state
}

functor led_off() {
return wrap(led_on); // next state
}

int main() {
functor statefunc = wrap(led_on);
while(1) {
statefunc = statefunc.call();
}
return 1; // should not get here
}

With -O2 gcc generates identical code. So at least it’s not slower, but I don’t know if it’s any prettier. :)

Søren Poulsen:

Just realized the same thing was suggested by the faq Christopher Williams linked to. (http://c-faq.com/decl/recurfuncp.html)
Sorry for the noise :)

Joonas Pihlajamaa:

Thanks. It might even be that void * and typecast in the calling function is at least as elegant as the ways to avoid it. :) And don’t worry about the noise, few people follow the links in any case (I know I don’t often do that)

Gustavo:

Great!

RSel:

Without typecast:


#include
#define F_CPU 20000000UL
#include

// 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() {
void* (*statefunc)() = led_on;

DDRB |= 1;

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

return 1; // should not get here
}

Eddy:

Where are the callbacks? You have used indirect calls but those are not callbacks. Callbacks occur when you call a function and the function calls you back when it needs to notify you.

Joonas Pihlajamaa:

You are right that the technique I’m describing is more about function pointers, but whether they can also be called callbacks starts to verge on philosophical. Wikipedia defines callbacks as:

In computer programming, a callback is a piece of executable code that is passed as an argument to other code, which is expected to call back (execute) the argument at some convenient time

Now the final example in my LED blink example does not /pass/ the callback function to other code as an argument, but a convention is made where it /returns/ a callback function that is called at a later point in time. So the question becomes that can returning a function pointer be considered passing code to other code, and thus can the technique be called a “callback”.

Some might think not, but the example could as well be rewritten with a schedule_next(callback); type of statement instead of return value. Would it then be a proper callback?

I’d say there is enough ambiguity in the term to use it in this one, or at least it is not wrong enough for me to start changing the short-url and headline of this article. :D And most people seem to understand what I’m getting at regardless of the term (and I’m mostly using the function pointer term myself). But nevertheless, it is not a callback in the most direct sense of the term.

John Ahcafr:

I tried to find the callbacks, but couldn’t…? I did find the indirect calls though. Callbacks usually happen when you refer to a function and it sends you back an answer to your query.

David:

Hello.
I am not very experienced in programming but I am playing with embedded C as a hobby and I have read about function pointers and used them in one or two very simple cases, but I cannot understand a couple of details of this code:

[code]
#include
#define F_CPU 20000000UL
#include

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
}
[/code]

Could you elaborate upon the meaning of these two lines?:
typedef void *(*StateFunc)();
statefunc = (StateFunc)(*statefunc)();

I do understand that the “void *led_on();” is a function that returns a pointer, but I can’t explain those two lines above without it ending up in confusion.

Any elaboration would be really appreciated, and thanks for an interesting article.

Joonas Pihlajamaa:

The typedef allows one to define a shorthand for another type. For example:

typedef long long LL;
LL bignum; // now same as “long long bignum;”

However, for function pointers, the new type does not go after, but inside the definition, but it works the same:

typedef void *(*StateFunc)();
StateFunc x = y; // now same as “void *(*x)() = y;”

And because the state function is defined to return “any pointer” (void *), we have to cast it to correct type so the compiler won’t complain:

statefunc = (StateFunc)(*statefunc)();

This is essentially the same as:

void * ptr = (*statefunc)();
statefunc = (StateFunc)ptr;

This is the same thing one does with memory allocation function void *malloc(size_t size):

char *str = (char *)malloc(128);

Hope this clarifies things! And as said, the exact syntax is hard to remember, I’m quite sure I had to google it to make this tutorial as well. :)

David:

Yes thank you, that made it very clear.
I have actually never delved into dynamic memory allocation, perhaps in part due to the large memory resources of the controllers I’ve used.

I have been reading about how to implement state machines in C but all the other examples I have found have been quite convoluted in comparison to the one in your article.

I like this technique and I am glad I found this, thank you for sharing your experience.

Jacob Vig:

Though I am a graduate in electrical engineering still I have more interest in particularly studying this type of code which can be applied in real life applications.