state machines tutorials

Question

I am just wondering if anyone know of some good tutorials on the Internet for developing state machines. Or ebooks?

I am starting working on state machines and just need something general to get me started.

Answer 1

State machines are very simple in C if you use function pointers.

Basically you need 2 arrays - one for state function pointers and one for state transition rules. Every state function returns the code, you lookup state transition table by state and return code to find the next state and then just execute it.

int entry_state(void);
int foo_state(void);
int bar_state(void);
int exit_state(void);

/* array and enum below must be in sync! */
int (* state[])(void) = { entry_state, foo_state, bar_state, exit_state};
enum state_codes { entry, foo, bar, end};

enum ret_codes { ok, fail, repeat};
struct transition {
    enum state_codes src_state;
    enum ret_codes   ret_code;
    enum state_codes dst_state;
};
/* transitions from end state aren't needed */
struct transition state_transitions[] = {
    {entry, ok,     foo},
    {entry, fail,   end},
    {foo,   ok,     bar},
    {foo,   fail,   end},
    {foo,   repeat, foo},
    {bar,   ok,     end},
    {bar,   fail,   end},
    {bar,   repeat, foo}};

#define EXIT_STATE end
#define ENTRY_STATE entry

int main(int argc, char *argv[]) {
    enum state_codes cur_state = ENTRY_STATE;
    enum ret_codes rc;
    int (* state_fun)(void);

    for (;;) {
        state_fun = state[cur_state];
        rc = state_fun();
        if (EXIT_STATE == cur_state)
            break;
        cur_state = lookup_transitions(cur_state, rc);
    }

    return EXIT_SUCCESS;
}

I don't put lookup_transitions() function as it is trivial.

That's the way I do state machines for years.

Answer 2

I prefer using function pointers over gigantic switch statements, but in contrast to qrdl's answer I normally don't use explicit return codes or transition tables.

Also, in most cases you'll want a mechanism to pass along additional data. Here's an example state machine:

#include <stdio.h>

struct state;
typedef void state_fn(struct state *);

struct state
{
    state_fn * next;
    int i; // data
};

state_fn foo, bar;

void foo(struct state * state)
{
    printf("%s %i\n", __func__, ++state->i);
    state->next = bar;
}

void bar(struct state * state)
{
    printf("%s %i\n", __func__, ++state->i);
    state->next = state->i < 10 ? foo : 0;
}

int main(void)
{
    struct state state = { foo, 0 };
    while(state.next) state.next(&state);
}

Answer 3

Unfortunately, most of the articles on state machines are written for C++ or other languages that have direct support for polymorphism as it's nice to model the states in an FSM implementation as classes that derive from an abstract state class.

However, it's pretty easy to implement state machines in C using either switch statements to dispatch events to states (for simple FSMs, they pretty much code right up) or using tables to map events to state transitions.

There are a couple of simple, but decent articles on a basic framework for state machines in C here:

• http://www.gedan.net/2008/09/08/finite-state-machine-matrix-style-c-implementation/
• http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/

Edit: Site "under maintenance", web archive links:

• http://web.archive.org/web/20160517005245/http://www.gedan.net/2008/09/08/finite-state-machine-matrix-style-c-implementation
• http://web.archive.org/web/20160808120758/http://www.gedan.net/2009/03/18/finite-state-machine-matrix-style-c-implementation-function-pointers-addon/

switch statement-based state machines often use a set of macros to 'hide' the mechanics of the switch statement (or use a set of if/then/else statements instead of a switch) and make what amounts to a "FSM language" for describing the state machine in C source. I personally prefer the table-based approach, but these certainly have merit, are widely used, and can be effective especially for simpler FSMs.

One such framework is outlined by Steve Rabin in "Game Programming Gems" Chapter 3.0 (Designing a General Robust AI Engine).

A similar set of macros is discussed here:

• https://contrarymotion.net/2008/02/12/some-code-snippets-for-a-simple-c-state-machine/

If you're also interested in C++ state machine implementations there's a lot more that can be found. I'll post pointers if you're interested.

Answer 4

State machines are not something that inherently needs a tutorial to be explained or even used. What I suggest is that you take a look at the data and how it needs to be parsed.

For example, I had to parse the data protocol for a Near Space balloon flight computer, it stored data on the SD card in a specific format (binary) which needed to be parsed out into a comma seperated file. Using a state machine for this makes the most sense because depending on what the next bit of information is we need to change what we are parsing.

The code is written using C++, and is available as ParseFCU. As you can see, it first detects what version we are parsing, and from there it enters two different state machines.

It enters the state machine in a known-good state, at that point we start parsing and depending on what characters we encounter we either move on to the next state, or go back to a previous state. This basically allows the code to self-adapt to the way the data is stored and whether or not certain data exists at all even.

In my example, the GPS string is not a requirement for the flight computer to log, so processing of the GPS string may be skipped over if the ending bytes for that single log write is found.

State machines are simple to write, and in general I follow the rule that it should flow. Input going through the system should flow with certain ease from state to state.

Answer 5

This is all you need to know.

int state = 0;
while (state < 3)
{
    switch (state)
    {
        case 0:
            // Do State 0 Stuff
            if (should_go_to_next_state)
            {
                state++;
            }
            break;
        case 1:
            // Do State 1 Stuff    
            if (should_go_back) 
            {
                state--;
            }    
            else if (should_go_to_next_state) 
            {
                state++;
            }
            break;
        case 2:
            // Do State 2 Stuff    
            if (should_go_back_two) 
            {
                state -= 2;
            }    
            else if (should_go_to_next_state) 
            {
                state++;
            }
            break;
        default:
            break;
    }
}

Answer 6

There is a lot of lesson to learn handcrafting state machines in C, but let me also suggest Ragel state machine compiler:

http://www.complang.org/ragel/

It has quite simple way of defining state machines and then you can generate graphs, generate code in different styles (table-driven, goto-driven), analyze that code if you want to, etc. And it's powerful, can be used in production code for various protocols.

Answer 7

Real-Time Object-Oriented Modeling was fantastic (published in 1994 and now selling for as little as 81 cents, plus $3.99 shipping).

Answer 8

State machines can be very complex for a complex problem. They are also subject to unexpected bugs. They can turn into a nightmare if someone runs into a bug or needs to change the logic in the future. They are also difficult to follow and debug without the state diagram. Structured programming is much better (for example you would probably not use a state machine at mainline level). You can use structured programming even in interrupt context (which is where state machines are usually used). See this article "Macros to simulate multi-tasking/blocking code at interrupt level" found at codeproject.com.