Article - Example state machine code for microcontrollers

[jakeypoo]

Howdy,

I wanted to share a write-up I put together on a piece of code I use regularly when a microcontroller application calls for a state machine. It goes over some example state machine code and explains some basics about how state machines work. Take a look if you're interested: http://www.heptapod.com/lib/statemachines/

The example uses an atmega328, but the concepts could be applied to any micro that uses C. It might be a little basic if you already know this stuff, but I hope it helps any beginners or intermediate folks out there trying to get away from writing the giant while(1) loops in their event-driven microcontroller code. 

[Mechatrommer]

now you have giant switch. tell me mr programmer, how in the world you can get rid of the giant loop? its the essence of making a program continually running without reaching the exit() code...

[elgonzo]

It would perhaps be easier and more maintainable code if you would put the statemachine in a lookup table where you query for current state and event (like input) and get the new state. Every state has an associated "enter state" action/function pointer (and optionally an "leave state" action, if necessary).

To do state transitions, you will have just a generic routine that based on the current state does something like the following:
1. Wait for event.
2. Lookup the new state for {current state, event}.
3. Execute "Enter state" action of new state.
4. Goto 1.

What is needed for that approach are two data structures. One for the lookup:

Code: [Select]

typedef struct
{
    currentState;
    event;
    newState;
} StateMachine;

and one that associates the states with the "Enter state" actions:
 

Code: [Select]

typedef struct
{
    state;
    enterStateActionPointer;
} StateAction;


Alternatively, if you have lots of states and or lots of events, the StateMachine structure from above could be split into something like this:

Code: [Select]

typedef struct
{
    event;
    newState;
} StateTransition;

typedef struct
{
    state;
    StateTransition[]; // array or lookup/hash table
} StateMachine;

(Note, the pseudo-code above is just one of many ways how you could create data structures for a state machine)

Right now, you have kind of spaghetti code that mixes management of the state machine and the actions that are associated with certain states. Having the code it like you do is not really a problem if your source code is small -- but then again, a simple nested switch block is as short and more readable. As soon as the number of possible states becomes larger, your approach leads to code that makes it difficult to read and maintain; it will also make it difficult to see the whole state machine that is embedded within the code...

[jakeypoo]

@Mechatrommer - I believe switch statements are better for compiler optimization, so a large switch statement is less evil than a large group of if-else statements as far as the optimizer sees it.

@elgonzo - Lookup table implementations are a good approach, but I think more appropriate where every event should trigger a new state. I found in microcontrollers you more often need an event handler that can change its behaviour when you change modes or something like that. It stays pretty easy to manage if you keep your code encapsulated. Maybe it's not the cleanest approach, but it has been pretty reliable and easy to read/maintain for me in the past. 

[tggzzz]

Switch statements are either better or worse for the compiler depending on the complexity of the code, the compiler, and the optimisation switches used.

Switch statements are OK for trivial state machines, but become a nightmare for complex state machines - particularly if they have to be maintained over a period by multiple programmers.

There are many different ways of encoding a state machine in a low/medium level language such as C. Each way has associated advantages and disadvantages - there is no "one best way".

Many people represent their state machines at a "higher level", and then use a tool to mechanically translate it into whatever language they are using.

Your approach is not sufficient when considering debugging and system integration. For those it is highly beneficial to explicitly abstract the concept of "state" and "event" into two data structures, and then log each event+state+time as it occurs. That will enable you to demonstrate that the problem is in other parts of your system, thus saving you time and money (and hair). Done properly, none of the debugging/logging code changes when the FSM changes.

[jakeypoo]

There are absolutely other ways to code a state machine in C, I just wanted to share my approach. If you're concerned about automated testing/debugging then this is probably a little more basic than what you need.

[tggzzz]

There are absolutely other ways to code a state machine in C, I just wanted to share my approach. If you're concerned about automated testing/debugging then this is probably a little more basic than what you need.

The approaches are beneficial for all testing and debugging whether automated or manual - and more importantly for spotting obscure intermittent faults and then isolating the faulty code.

All non-trivial FSMs grow like Topsy until they become intractable - i.e. you can't accurately predict how they will operate. I've even seen an FSM similar to yours that had grown over the years until the turnaround time (customer request to deployed feature) was typically six months. Completely ridiculous of course, and it sank the product.

[jakeypoo]

All non-trivial FSMs grow like Topsy until they become intractable - i.e. you can't accurately predict how they will operate. I've even seen an FSM similar to yours that had grown over the years until the turnaround time (customer request to deployed feature) was typically six months. Completely ridiculous of course, and it sank the product.

Yeah, I don't doubt it. The benefit of using something like a state machine should be that you fit your system to a construct you can implement quickly/reliably. And there's an added benefit of engineers being able to understand logic flow in a FSM better than other programming construct. But of course most of us aren't programmers and we can kludge even the best of code into a mess.

Are there any articles or examples of low-level FSM implementation you would recommend? I didn't find too much in the past specific to microcontrollers, made me want to share.

[elgonzo]

Are there any articles or examples of low-level FSM implementation you would recommend? I didn't find too much in the past specific to microcontrollers, made me want to share.

Have you tried searching...?

There is nothing specific about implementing state machines in MCUs.
There might be application-specific considerations as well as considerations regarding memory footprint of code+data structures, but those are general considerations that apply to any kind code, and are not specific to state machine implementations. (If this is your interest, you should look for articles that talk generally about data structures and their memory footprints + performance characteristics with regard to the C language and your target MCU architecture...)

[tggzzz]

All non-trivial FSMs grow like Topsy until they become intractable - i.e. you can't accurately predict how they will operate. I've even seen an FSM similar to yours that had grown over the years until the turnaround time (customer request to deployed feature) was typically six months. Completely ridiculous of course, and it sank the product.

Yeah, I don't doubt it. The benefit of using something like a state machine should be that you fit your system to a construct you can implement quickly/reliably. And there's an added benefit of engineers being able to understand logic flow in a FSM better than other programming construct. But of course most of us aren't programmers and we can kludge even the best of code into a mess.

Nominally they were programmers. Personally I wouldn't have let them anywhere near a keyboard.

Are there any articles or examples of low-level FSM implementation you would recommend? I didn't find too much in the past specific to microcontrollers, made me want to share.

The trouble is I learned/reinvented various techniques before URLs even existed.

Have a look for Harel StateCharts. IMNSHO, while complete, they are a little overcomplicated.

An old low-level C technique is to have a 2D array of function pointers. Dimension 1 is the current state S (encoded as an integer), dimension 2 is the incoming event E (also encoded as an integer). Each pointer refers to the function to be executed when event E occurs in state S; the function takes whatever actions are necessary and specifies the next state (variant: the next state is encoded in a second parallel 2D array of integers).

Logging consists of recording <time,E,S> tuples. The set of states and events is fully explicitly enumerated, and it is unambiguous what happens when event E happens in state S1 or S2 or...

If you need a new action, then you don't have to dismember entangled switch statements, you just add a new function and point to it.

If an event "should not occur" then that can either be encoded as an empty function or, more usefully as a WTF-function.

Note that the execution time is constant and trivial - an array lookup and indirect jump to a function. Unless the state-event space is very sparse, which is unlikely for real-time systems, the 2D array is also space efficient.

If hierarchical FSMs better represent your problem, then encode encode each event as a class E, each state as a class C (where the class hierarchy matches the state hierarchy), and have a virtual function in classes C for each event E. Then provide methods in the relevant C for each relevant E. "Should not happen" E will trickle up to the base/root class.

Have a look at how various "state machine compilers" implement the FSMs in different languages. The better ones will target different languages and have alternative target  implementations depending on the constraints.
 
One (old) compiler was Bob Martin's "State Map Compiler", see http://smc.sourceforge.net/SmcFaq.htm#RipOff but there are many others.

[tggzzz]

Are there any articles or examples of low-level FSM implementation you would recommend? I didn't find too much in the past specific to microcontrollers, made me want to share.

Have you tried searching...?

C/C++ people (especially C/C++ gurus) tend not to understand what has been achieved in other domains. One result is that C++ is an unholy mess whereas Java isn't. This isn't the place for that debate, but interested parties can search for Gosling's 1996 Java whitepaper, and for the C++ FQA (not FAQ!).

[Mechatrommer]

@Mechatrommer - I believe switch statements are better for compiler optimization, so a large switch statement is less evil than a large group of if-else statements as far as the optimizer sees it.

you were talking about getting rid of "giant loop", you should've said getting rid of "giant if". but well, replacing giant if with giant switch is not entertaining either. so the excuse is moot. otoh an "ideal programmer" doesnt deal with a nonsense such as "compiler optimization" (oh what a troll ) find another good reason then i'm with you my friend

One result is that C++ is an unholy mess whereas Java isn't.

am i not dreaming? what a joke of the century!

[elgonzo]

C/C++ people (especially C/C++ gurus) tend not to understand what has been achieved in other domains. One result is that C++ is an unholy mess whereas Java isn't. This isn't the place for that debate, but interested parties can search for Gosling's 1996 Java whitepaper, and for the C++ FQA (not FAQ!).

Not sure in which direction you are going... I agree with C++ being an abomination, but what has that to do with looking at and understanding simple state machine implementations? How does the Java whitepaper fit into this topic, or was this in reference to C++ being sauerkraut?

[tggzzz]

C/C++ people (especially C/C++ gurus) tend not to understand what has been achieved in other domains. One result is that C++ is an unholy mess whereas Java isn't. This isn't the place for that debate, but interested parties can search for Gosling's 1996 Java whitepaper, and for the C++ FQA (not FAQ!).

Not sure in which direction you are going... I agree with C++ being an abomination, but what has that to do with looking at and understanding simple state machine implementations? How does the Java whitepaper fit into this topic, or was this in reference to C++ being sauerkraut?

It was solely a response to your question about searching - or lack thereof. The C++ mob have long demonstrated a lack of understanding of what has been shown to work/fail outside the C/C++ sphere.

Neither it nor the Java whitepaper nor the C++ FQA has direct relevance to FSMs.

[elgonzo]

It was solely a response to your question about searching - or lack thereof. The C++ mob have long demonstrated a lack of understanding of what has been shown to work/fail outside the C/C++ sphere.

Did you notice that my question was a link you can click and that the search terms within this links are about state machines / implementations, not about C++? What are you talking about?

[tggzzz]

It was solely a response to your question about searching - or lack thereof. The C++ mob have long demonstrated a lack of understanding of what has been shown to work/fail outside the C/C++ sphere.

Did you notice that my question was a link you can click and that the search terms within this links are about state machines / implementations, not about C++? What are you talking about?

Oh good grief. Don't over-interpret what has been written. And please don't snip the context of the conversation - it makes it difficult for you (and others) to follow what was written.

To be extraordinarily explicit, I was amplifying your inference (that while the OP would benefit from having done some searching) by noting that many C/C++ people (probably including the OP) were too narrowly focussed on the C/C++ realm - to the extent that they are too unaware of things outside that narrow realm.

[nctnico]

An external tool may be benificial but it does add complexity to maintaining the source code because there is a dependancy on an extra tool. People maintaining the software will need to learn the extra tool as well.

Perhaps a better way would be to have proper documentation and/or breaking a big statemachine in several small ones. That way someone maintaining the software can keep an eye on the big picture.

[f1rmb]

Java, MCU... Good one :-D

[tggzzz]

An external tool may be benificial but it does add complexity to maintaining the source code because there is a dependancy on an extra tool. People maintaining the software will need to learn the extra tool as well.

Very, very true. Plus there will be very little automated tool support for exploring/reasoning/checking each FSM design, and it will be difficult to recruit someone to a role that won't help them get their next job.

Of course, all that applies to the "domain specific languages" beloved of computer science wannabes that feel unfulfilled unless they are writing compilers. IMNSHO a good library is usually preferable to a DSL.

Perhaps a better way would be to have proper documentation and/or breaking a big statemachine in several small ones. That way someone maintaining the software can keep an eye on the big picture.

You can make the argument that the FSM is that documentation.

As for breaking a large FSM into smaller ones, that goes without saying, just as with large functions etc. But sometimes large FSMs are natural and/or are part of the specification being implemented.

[tggzzz]

Java, MCU... Good one :-D

There's Java on a wide range of extremely small MCUs... SIMS. See http://en.wikipedia.org/wiki/Java_Card

[zapta]

Java, MCU... Good one :-D

There's Java on a wide range of extremely small MCUs... SIMS. See http://en.wikipedia.org/wiki/Java_Card

It's used to sandbox executed third party code which is typically not a requirement in most MCU applications that allow leaner solutions.

[Mechatrommer]

Java, MCU... Good one :-D

There's Java on a wide range of extremely small MCUs... SIMS. See http://en.wikipedia.org/wiki/Java_Card

and maybe you can demonstrate (open source maybe?) how FSM is implemented better in java? or in real life application performing better than c/c++?

[tggzzz]

Java, MCU... Good one :-D

There's Java on a wide range of extremely small MCUs... SIMS. See http://en.wikipedia.org/wiki/Java_Card

and maybe you can demonstrate (open source maybe?) how FSM is implemented better in java? or in real life application performing better than c/c++?

Don't be silly.

Better/worse can only be defined relative to requirements and constraints. Hence differing requirements and constraints will lead to different optimal technology.

A valid and increasingly typical use-case for high-performance soft realtime systems: if all your software is written in Java and/or none of your staff know C/C++, then it would be highly suboptimal and non-performant to use C/C++ for and FSM.

I have myself implemented a telecom FSM in Java (implementing part of the ETSI Parlay standard), and it ran significantly faster than the equivalent system in C/C++. "Significantly" means that the engineers responsible for the earlier system were amazed, and an external company was so impressed that they unexpectedly purchased the code.

Don't forget that C compilers have to be so pessimal that when you implement HotSpot-style optimisation and run the code in an emulated processor, it still runs faster than the optimised C code on the same un-emulated processor. Search for HP's Dynamo project to see how and why (you can follow links from http://lambda-the-ultimate.org/node/768 )

[nctnico]

IMHO that very much depends on how the statemachine is implemented. If you use a 2 dimensional array with function pointers (1 dimension is the state and the other the event) then I very much doubt you'll be able to make it run faster in Java.

[Mechatrommer]

Don't be silly.
Better/worse can only be defined relative to requirements and constraints. Hence differing requirements and constraints will lead to different optimal technology.
I have myself implemented a telecom FSM in Java (implementing part of the ETSI Parlay standard), and it ran significantly faster than the equivalent system in C/C++. "Significantly" means that the engineers responsible for the earlier system were amazed, and an external company was so impressed that they unexpectedly purchased the code.

simply taking this sample case doesnt necessarily means one language is better than the other. they are just tools. the result will be good in the hand of a person who knows how to use the tool well.... "engineer" title alone also doesnt necessarily means he is a good guy. do you know him? he probably a bad c programmer and you are a better java programmer. as you said dont be silly, its a relative or differing requirements or constraints. re-quoting your statement...

C/C++ people (especially C/C++ gurus) tend not to understand what has been achieved in other domains. One result is that C++ is an unholy mess whereas Java isn't

this is not general or well accepted conclusion, it is more of your own personal opinion from your personal experience. remember some people are on the other side. well, my personal opinion is somewhat sounded like...

java people (especially java gurus) tend not to understand what has been achieved in other domains. One result is that java is an unholy mess whereas C/C++ isn't

and this is not based merely on my personal opinion alone, its shown everywhere when people posted code questions or examples in the net.. like our mr friend earlier with google search link with general keyword "simple state machine implementation" do you see any java implementation in the top list result? no need speak of, the truth will out, i?

btw, going c/c++ vs <insert any language here> pissing contest is not a worthy thing to do... lets concentrate on algorithm shall we?