82

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.

1

8 Answers 8

153

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.

5
  • 17
    Nice, thanks for this. The only thing possible flaw here is that the lookup_transitions will likely be linear (O(n)) with this transition table datastructure. Its possible to make it better with multidimentional array - guaranteed O(1). Eg. the table can be represented as a multidimentional array where key is state and the value is an array where the key is the return code and value is the next state: int state_transitions[][3] = { [entry] = { foo, end, foo }, ... } /* ok, fail, repeat */
    – Alex
    Oct 10, 2013 at 21:57
  • 2
    Why don't your state functions return enum instead of ints for the lookup function? You're returning a ret code are you not?
    – Django
    Apr 3, 2016 at 14:37
  • Wouldn't it be much easier to just have src_state and dst_state as function pointers? I don't understand the benefit of having them of enum type, when all you use them for is to look up some function pointers in an array.
    – Multisync
    Aug 17, 2016 at 0:29
  • 3
    @Multisync Generally speaking, state != function, it is common to have several different states that in fact use the same function. For example, you can have couple of functions that prepare message, and one function to send it and one function to receive response, but these two I/O functions will be used in different states.
    – qrdl
    Aug 17, 2016 at 5:51
  • Any state can be considered as one "sub_main_function", due the the actions in these "sub_main_functions", it can change to different state again, let's use a switch, each "case state:" has multi functions in side, anyone with me?
    – Fuevo
    Oct 14, 2019 at 9:23
35

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);
}
6
  • Your main doesn't return a value . . . should it?
    – dreamlax
    Nov 20, 2009 at 10:23
  • 1
    @dreamlax: C99 5.1.2.2.3: reaching the end of main() implicitly returns 0
    – Christoph
    Nov 20, 2009 at 16:01
  • 1
    Really liked this answer. Simple and direct. Good job.
    – AntonioCS
    Feb 13, 2015 at 21:46
  • Sorry, I really don't get it. What happens in the while condition in the last line? Are you calling foo()? Which default arguments are assumed if none are given?
    – Multisync
    Aug 16, 2016 at 19:41
  • 2
    @Multisync The struct initializer in the previous line sets state.next (a function pointer) to the address of foo. So state.next(&state) is the same as foo(&state) (the first iteration of the loop, it points elsewhere later). For comparison, if this were C++, foo() would be a member of the State class (State::foo()) and would not take any parameters. It's body would use this->next = bar instead of state->next = bar. In C you have to pass the equivalent of the this pointer explicitly as there are no stateful class scopes. Jan 19, 2017 at 14:06
12

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:

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

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:

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.

1
7

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.

8
  • 2
    @Chris: Near Space is defined as anything above 60,000 ft, our balloon got to 92,999 ft. At some point the latex balloon starts to become so large because of the decompression (the gas keeps expanding the balloon) that the balloon pops, at which point the near space craft free-falls back to earth (we attach a parachute off course), see the linked Wiki for more information about our Near Space efforts and Google around, it is an absolutely awesome hobby!
    – X-Istence
    Sep 3, 2009 at 5:32
  • 4
    That sounds like a wildly inefficient, ridiculously expensive, perhaps a bit wasteful, and completely awesome hobby.
    – Chris Lutz
    Sep 3, 2009 at 8:49
  • 1
    Many powerful and important experiments have been run from balloon platforms, you have to compare costs with the those of launching an equivalent orbiting platform. By the time you get to circa 100,000 ft, your heat management problem is essential that of a spacecraft: conductive and convective heating/cooling are vanishing by comparison to radiation. Sep 3, 2009 at 14:19
  • 1
    @Chris: We had a budget of $2000 to work with, and we have so far successfully launched two balloons. The most expensive part was the helium to fill the latex balloons which were the second most expensive part.
    – X-Istence
    Sep 3, 2009 at 20:38
  • 1
    @ChrisLutz I'd argue the exact opposite. Compared to the alternative: rockets; It's by far more efficient, less expensive and significantly less wasteful, but slightly less awesome. Jan 19, 2017 at 14:11
6

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;
    }
}
8
  • 9
    I woud consider it better practice to explicitly set the state, but that's just me.
    – Chris Lutz
    Sep 3, 2009 at 5:00
  • 2
    You've left out a lot, for example: substates; events, and event/state combinations; state transition diagrams; guards ("don't change state if"); state entry and state exit methods ("on exiting this state do the following method").
    – ChrisW
    Sep 3, 2009 at 5:05
  • 2
    This is oversimplifying state machines, and not that great of an example.
    – X-Istence
    Sep 3, 2009 at 5:08
  • 2
    Don't over complicate something that is very simple. Sep 3, 2009 at 5:11
  • 1
    Sure, as a skeleton for what a basic state machine might look like this might suffice. But I think it's not quite "all you need to know". Also, you might want to make your state unsigned.
    – mrduclaw
    Sep 3, 2009 at 6:21
4

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.

3

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

3
-6

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.

2
  • Doesn't answer the question. Instead, goes on an editorial about why state machines are bad.
    – the_endian
    Mar 22, 2020 at 6:47
  • Upvoted, for being close to the only correct answer, though the exact wording and the provided link are unfortunate. Automata theory that encompasses state machines is a mathematical model of computation with no direct practical application. We use programming languages said to be Turing-complete on computers that are themselves state machines, and we would not use them to simulate a Turing machine, would we? Why then would we simulate a constrained sub-concept? The algorithms described by the other answers on this page are a retardation and a sign of the crowd mentality in programming.
    – Theo d'Or
    Mar 19, 2021 at 22:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.