FSM / Dispatch

Dispatch in C: switch, Function Pointers, and Jump Tables

Dispatch is choosing which code to run from a value, and C offers three forms with genuinely different costs. A switch over a dense range of small integers usually becomes a jump table: one bounds check and one indirect branch, constant time regardless of how many cases exist. A switch over a sparse or wide range becomes a chain of comparisons or a binary search, whose cost grows with the number of cases. A table of function pointers is an explicit jump table you control, at the cost of an indirect call the compiler cannot inline and a pointer per entry in RAM or flash. Choosing between them is a code-size and timing decision, and on a part where the dispatch runs per received byte it is a measurable one. The design of the state machine itself - what the states are, which transitions are legal, how to prove it cannot reach an undefined state - is the eighth stage of Embedded DSA at /dsa/graphs.

How it is built

• A switch over consecutive small integers is the case compilers optimise best. Given a dense range they emit a bounds check and an indexed branch, so every case costs the same. Adding a case with a distant value can silently convert the whole switch into a comparison chain, which is why the generated code is worth checking after an edit.
• An if-else ladder or a sparse switch costs comparisons proportional to how far down the chain the match is, so the cost depends on the input. In a per-byte parser that turns into a data-dependent execution time, which is exactly what a worst-case analysis has to account for.
• A function-pointer table gives constant-time dispatch you control and can place in flash. The cost is an indirect call the compiler cannot inline or analyse, which means it also cannot prove anything about what the callee touches - so surrounding optimisation gets more conservative.
• Computed dispatch through a table needs the index validated before use. An out-of-range index on a function-pointer table jumps to whatever the adjacent memory holds, which is unbounded behaviour rather than a wrong answer.
• Designated initialisers make a dispatch table safe to maintain: writing `[STATE_IDLE] = on_idle` binds each entry to its enumerator by name, so adding a state in the middle of the enum cannot silently shift every handler by one. Positional initialisation of a dispatch table is a defect waiting for the next edit.
• Enumerations are not a closed set at runtime. A value read from a frame or from flash can hold anything the underlying type allows, so a switch over an enum still needs a default case, and a table lookup still needs a range check.

Design procedure

1. Prefer a switch over a dense enum for state dispatch, and keep the enumerators consecutive so the compiler can emit a jump table.
2. Check the generated code after adding a case; one distant value can convert a jump table into a comparison chain.
3. Use a function-pointer table when handlers are registered at runtime or must live in flash, and validate the index before every call.
4. Initialise dispatch tables with designated initialisers so entries bind to enumerators by name rather than by position.
5. Give every switch over an enum a default case that handles the impossible value, because the underlying type permits it.
6. For the state machine's design - legal transitions, unreachable states, proving completeness - work through /dsa/graphs.

Key terms

Jump table

A bounds check plus one indexed branch. Constant time, and what a dense switch becomes.

Comparison chain

What a sparse switch becomes. Cost depends on which case matches.

Function-pointer table

Explicit dispatch you control, at the cost of an uninlinable indirect call.

Designated initialiser

[STATE_X] = handler. Binds by name so inserting an enumerator cannot shift the table.

Index validation

Required before any table call. An out-of-range index is an unbounded jump, not a wrong answer.

Open enum

An enum variable can hold any value its underlying type permits, so default cases are mandatory.

Worked example

#include <stddef.h>

typedef enum { ST_IDLE = 0, ST_HDR, ST_BODY, ST_CRC, ST_COUNT } state_t;

/* Dense switch: usually one bounds check and one indirect branch. */
void step_switch(state_t s, uint8_t b) {
    switch (s) {
    case ST_IDLE: on_idle(b); break;
    case ST_HDR:  on_hdr(b);  break;
    case ST_BODY: on_body(b); break;
    case ST_CRC:  on_crc(b);  break;
    default:      on_bad(b);  break;   /* an enum can hold anything */
    }
}

/* Table dispatch, with entries bound by NAME not position: */
typedef void (*handler_t)(uint8_t);
static const handler_t TABLE[ST_COUNT] = {
    [ST_IDLE] = on_idle,
    [ST_HDR]  = on_hdr,
    [ST_BODY] = on_body,
    [ST_CRC]  = on_crc,
};

void step_table(state_t s, uint8_t b) {
    if ((size_t)s >= ST_COUNT || TABLE[s] == NULL) {
        on_bad(b);                      /* validate BEFORE the call */
        return;
    }
    TABLE[s](b);
}

# Cost of each form, on a per-byte parser:
#
#   form                  time            size        inlinable
#   dense switch          constant        table+code     yes
#   sparse switch         O(cases)        code only      yes
#   if-else ladder        O(position)     code only      yes
#   pointer table         constant        ptr/entry      NO

# Designing the machine itself:  /dsa/graphs

Common pitfalls

Why a state machine, and when not to use one

A state machine is the right structure when behaviour depends on history: what happens on this input depends on what happened before. Making that history explicit - a named state, a table of transitions - converts a tangle of flags into something you can draw, review and test exhaustively. It is the wrong structure when there is no history, and wrapping stateless logic in one adds ceremony without adding clarity.

How it is built

• The three parts are a state variable, a transition function mapping state and event to a new state, and actions attached to transitions or states.
• The alternative it replaces is a set of boolean flags whose valid combinations are implicit and whose invalid ones are unreachable only by accident.
• An explicit state enumeration makes the illegal combinations unrepresentable rather than merely unreached.
• The transition table can be exhaustively tested, because the state and event sets are both finite and small.
• Hierarchical machines factor shared behaviour into a parent state, which avoids repeating the same transition in every child.

Design procedure

1. Look for the flags first: three related booleans usually mean five legal states out of eight combinations.
2. Enumerate the states and the events before writing any code, and draw the diagram.
3. Handle every state and event pair explicitly, even if the action is to ignore it, so the omissions are visible.
4. Keep actions out of the transition logic where possible, so the machine can be tested without side effects.
5. Use a flat machine until the repetition is genuinely painful, then factor rather than starting hierarchical.

Key terms

State

A named condition that determines how the next event is handled.

Event

Something that can cause a transition: a timeout, a byte, a completion.

Transition

A state and event pair mapping to a new state and an action.

Illegal state

A combination the design does not permit. An enumeration makes it unrepresentable.

Hierarchical state

A parent whose transitions apply to all its children.

Worked example

The flags that are really a state machine:

  bool connected, authenticating, streaming;

  Eight combinations, five of them meaningless. Nothing prevents
  streaming && !connected, and every function that reads them has
  to know which combinations are real.

  typedef enum { S_IDLE, S_CONNECTING, S_AUTH, S_STREAMING, S_ERROR,
                 S_COUNT } State;

  Five states, all legal, and the illegal combinations cannot be
  written down.

And when a state machine is the wrong answer:

  // no history: the output depends only on the input
  Level classify(uint16_t adc) {
      if (adc < LOW)  return LEVEL_LOW;
      if (adc < HIGH) return LEVEL_MID;
      return LEVEL_HIGH;
  }

  Wrapping this in a state machine adds a state variable that is
  written and read in the same call and never influences anything.
  The test is whether the past matters; here it does not.

Common pitfalls

Switch, table, or function pointer

There are three usual implementations, and they differ in what the compiler can check, what the code costs, and how easy the machine is to change. A switch is the simplest and hardest to survey; a transition table is data and can be inspected and validated; a function-pointer table is the most flexible and gives up the compiler's exhaustiveness checking. The choice should follow the size of the machine.

How it is built

• A nested switch on state then event is direct, needs no data structures, and lets -Wswitch check exhaustiveness.
• A two-dimensional table indexed by state and event makes every transition visible in one place and testable as data.
• A function-pointer table per state allows the handler to be replaced at runtime, which a switch cannot do.
• Table approaches lose the compiler's exhaustiveness check, so a new state must be caught by a test instead.
• Table size grows as states times events, which is fine while both are small and wasteful when the table is sparse.

Design procedure

1. Use a switch for a small machine, omitting the default so a new state is a warning at every site.
2. Use a table once the machine is large enough that reading the switch stops being practical.
3. Add a test asserting every state and event pair has a defined entry, replacing the check the switch gave you.
4. Bounds-check the state and event before indexing any table, since an out-of-range index reads arbitrary memory.
5. Keep a COUNT enumerator so the table dimensions follow the enumeration automatically.

Key terms

Transition table

A two-dimensional array of next states indexed by state and event.

Dispatch table

An array of function pointers, one per state or per transition.

Exhaustiveness

Every state and event handled. Checked by the compiler for a switch, by a test for a table.

COUNT enumerator

A final enumerator equal to the number of members, used to size arrays.

Sparse table

One where most entries are the same. Wastes space that a switch would not.

Worked example

The same machine, three ways:

  // SWITCH - compiler checks exhaustiveness, no default clause
  switch (state) {
  case S_IDLE:
      if (ev == EV_CONNECT) state = S_CONNECTING;
      break;
  case S_CONNECTING:
      if (ev == EV_OK)   state = S_AUTH;
      if (ev == EV_FAIL) state = S_ERROR;
      break;
  ...
  }                       // adding S_RETRY warns here

  // TABLE - every transition visible, testable as data
  static const State NEXT[S_COUNT][EV_COUNT] = {
      [S_IDLE]       = { [EV_CONNECT] = S_CONNECTING },
      [S_CONNECTING] = { [EV_OK] = S_AUTH, [EV_FAIL] = S_ERROR },
  };

  if (state < S_COUNT && ev < EV_COUNT)       // bounds first
      state = NEXT[state][ev];

  // DISPATCH - one handler per state, replaceable at runtime
  static State (*const HANDLER[S_COUNT])(Event) = {
      [S_IDLE] = on_idle, [S_CONNECTING] = on_connecting,
  };

The table loses the compiler's check, so it needs a test that replaces it:

  for (int s = 0; s < S_COUNT; s++)
      for (int e = 0; e < EV_COUNT; e++)
          assert(NEXT[s][e] < S_COUNT);   // 0 means "stay", which
                                          // must be deliberate

Common pitfalls

Events, queues, and where the machine runs

A state machine needs events, and where those events come from decides most of the system's structure. Handling an event directly in the interrupt that produced it makes the machine part of the handler, with all the constraints that implies. Queueing it and running the machine in the main loop decouples the two, at the cost of latency and a queue that can fill.

How it is built

• Direct dispatch from a handler gives minimum latency and puts the entire machine under interrupt-context rules.
• Queued dispatch pushes an event and returns, running the machine in the main loop where it may take as long as it needs.
• The queue must be lock-free or protected, since one side is an interrupt handler and the other is not.
• A full queue is a real state that needs a decision: drop the newest, drop the oldest, or overwrite and record the loss.
• Events carrying data need the payload copied into the queue, since a pointer into a buffer the producer will reuse is a lifetime bug.

Design procedure

1. Queue by default, and dispatch directly only where the latency requirement genuinely demands it.
2. Size the queue from the worst-case burst rather than the average rate.
3. Decide and document the overflow policy, and count occurrences so it is visible rather than silent.
4. Copy the payload into the event, or use a pool the consumer returns, rather than passing a pointer into a shared buffer.
5. Keep the machine itself free of blocking calls, so a slow action cannot stall event processing.

Key terms

Direct dispatch

Running the transition inside the interrupt that produced the event.

Queued dispatch

Pushing an event and running the machine in another context.

Event payload

Data carried with the event. Copied, or owned by a pool, never borrowed.

Overflow policy

What happens when the queue is full. A decision, not an accident.

Run-to-completion

The property that one event is fully processed before the next is taken.

Worked example

The lifetime bug that queueing invites:

  // WRONG - the event borrows the DMA buffer
  void DMA_IRQHandler(void) {
      Event e = { .kind = EV_RX, .data = dma_buf, .len = n };
      queue_push(&e);
      dma_restart(dma_buf);      // reused before the consumer runs
  }

  The main loop dequeues the event and reads dma_buf, which is now
  being overwritten by the next transfer. The data is sometimes
  right, which is worse than always wrong.

  // Copy into the event
  Event e = { .kind = EV_RX, .len = n };
  memcpy(e.payload, dma_buf, n);      // bounded by sizeof e.payload
  queue_push(&e);

  // Or hand over ownership from a pool
  Buffer *b = pool_take();
  if (b) { dma_restart(b->data); e.buf = current; queue_push(&e); }

And the overflow policy, made visible:

  if (!queue_push(&e)) {
      dropped_events++;          // counted, not silent
  }

A queue that silently discards under load looks like a system that occasionally
misses an input, which sends the investigation to the sensor.

Common pitfalls

Timeouts, and the states you forget

Most real state machines are wrong in the same way: every state has a transition for the event that is supposed to happen and none for the event never arriving. A timeout is a state's answer to that, and adding one to every waiting state is usually the single largest correctness improvement a machine gets - because a system that hangs is worse than one that fails.

How it is built

• Any state that waits for an external response needs a timeout, since the response may never come.
• The timeout is an event like any other, so it fits the existing transition structure without special handling.
• A timer must be started on entry to the state and cancelled on exit, or a stale expiry fires in a later state.
• The timeout value comes from the worst-case response time plus margin, not from what looks reasonable.
• The transition on timeout is a design decision: retry with a bound, degrade, or enter an error state.

Design procedure

1. Enumerate the states that wait for something external; each one needs a timeout.
2. Start the timer on state entry and cancel it on every exit path, including the error ones.
3. Bound retries explicitly, and define what happens when the bound is reached.
4. Test the timeout paths deliberately by not sending the response, since they are otherwise never exercised.
5. Log timeouts distinctly from other failures, since a system that recovers via timeout is degraded rather than healthy.

Key terms

Timeout event

An event generated when a state has waited too long. Ordinary in every other respect.

Stale timer

An expiry from a state that has already been left. Prevented by cancelling on exit.

Retry bound

A cap on attempts, so a failing peer does not produce an infinite loop.

Degraded operation

Continuing with reduced function after a failure, rather than stopping.

Liveness

The property that the machine always eventually makes progress.

Worked example

The machine that hangs, and the same one with timeouts:

  S_WAIT_ACK:
      case EV_ACK:  state = S_DONE;  break;
      // and if the ACK never arrives? Nothing. Forever.

  S_WAIT_ACK:
      case EV_ACK:
          timer_cancel();
          state = S_DONE;
          break;
      case EV_TIMEOUT:
          if (++retries < MAX_RETRIES) {
              send_request();
              timer_start(ACK_TIMEOUT_MS);   // restart for the retry
              /* stay in S_WAIT_ACK */
          } else {
              state = S_ERROR;               // bounded, not infinite
          }
          break;

And the stale timer, which is the bug this introduces if you are careless:

  S_WAIT_ACK -> EV_ACK -> S_DONE       but the timer still runs
  ...later, in S_DONE, EV_TIMEOUT fires
  S_DONE has no case for it -> ignored, or worse, handled by a
  default clause that transitions somewhere

  Cancelling on EVERY exit path from the state - including the
  successful one - is what prevents it.

Common pitfalls

Testing a state machine exhaustively

A state machine is one of the few structures in firmware that can be tested completely: the state set and the event set are both finite and small, so every pair can be exercised. That makes a class of bug - an unhandled combination - findable by construction rather than by luck, provided the machine is separated from the actions it triggers.

How it is built

• The transition function is pure: state and event in, next state out, with no side effects.
• That purity is what makes exhaustive testing possible, and it requires actions to be returned or dispatched separately rather than performed inline.
• The full cross product of states and events is typically a few dozen cases, which is small enough to enumerate.
• Reachability analysis finds states no event sequence can enter, which are either dead code or a missing transition.
• Sequence tests cover the paths that matter: the happy path, each error path, and each timeout path.

Design procedure

1. Separate the transition from the action, so the transition can be called without side effects.
2. Loop over every state and event pair and assert the result is a valid state.
3. Assert that every state is reachable from the initial state by some sequence, and investigate any that is not.
4. Write a sequence test per scenario, including the ones that end in an error state.
5. Add a test asserting the machine recovers from an illegal state value, since an upset can produce one.

Key terms

Pure transition

State and event to next state, no side effects. What makes exhaustive testing possible.

Cross product

Every state and event pair. Small enough to enumerate for a real machine.

Reachability

Whether a state can be entered by any event sequence.

Dead state

One no sequence reaches. Either unnecessary or a missing transition.

Illegal state recovery

Defined behaviour when the state variable holds a value outside the enumeration.

Worked example

The separation that makes it testable, and the exhaustive test:

  typedef struct { State next; Action act; } Step;

  Step step(State s, Event e);        // pure: no side effects

  void run(Event e) {                 // the impure part, kept thin
      Step r = step(state, e);
      state = r.next;
      perform(r.act);
  }

  // every pair, a few dozen cases
  for (int s = 0; s < S_COUNT; s++)
      for (int e = 0; e < EV_COUNT; e++) {
          Step r = step((State)s, (Event)e);
          assert(r.next < S_COUNT);        // always a valid state
      }

  // reachability
  bool seen[S_COUNT] = { [S_IDLE] = true };
  bool changed = true;
  while (changed) {
      changed = false;
      for (int s = 0; s < S_COUNT; s++) if (seen[s])
          for (int e = 0; e < EV_COUNT; e++) {
              State n = step((State)s, (Event)e).next;
              if (!seen[n]) { seen[n] = true; changed = true; }
          }
  }
  for (int s = 0; s < S_COUNT; s++)
      assert(seen[s]);                 // an unreachable state is a bug

The reachability check is the one that finds a transition you forgot to write,
because the state you added is not reachable from anywhere.

Common pitfalls

Dispatch beyond state machines: command tables and handlers

The same table-driven idea applies wherever a value selects behaviour: a command byte selecting a handler, a message type selecting a parser, a menu selection selecting a screen. Replacing a long if-else chain with a table makes the mapping data rather than control flow - visible in one place, testable as data, and extendable by adding a row.

How it is built

• A table of {code, handler, name} entries turns dispatch into a lookup and makes the full command set inspectable.
• Keeping the table const places it in flash, which on a microcontroller is the difference between free and several bytes of RAM per entry.
• A linear search is fine for a handful of entries; a sorted table with a binary search or a direct index is better for many.
• The table can carry metadata the code needs anyway - argument counts, permission levels, help text - alongside the handler.
• Every dispatch needs a defined response to an unknown code, which a table makes a single explicit case.

Design procedure

1. Define the table as a const array of structs, with the handler signature identical for every entry.
2. Give every handler the same signature, using a context pointer for anything that differs.
3. Handle an unknown code explicitly, and return an error rather than ignoring it silently.
4. Add a test asserting no two entries share a code and that every handler is non-null.
5. Generate help or a command list from the same table, so documentation cannot drift from behaviour.

Key terms

Command table

A const array mapping codes to handlers and metadata.

Uniform signature

Every handler taking the same parameters, so one table can hold them all.

Context pointer

A void * carrying per-call state, so handlers need no globals.

Direct indexing

Using the code as an array index. Constant time, requires a dense code space.

Single source of truth

Deriving help text from the same table that dispatches, so they cannot disagree.

Worked example

The chain, and the table that replaces it:

  if      (cmd == 0x01) handle_read(args);
  else if (cmd == 0x02) handle_write(args);
  else if (cmd == 0x03) handle_erase(args);
  ...                                  // twenty more

  typedef struct {
      uint8_t code;
      Status (*fn)(const uint8_t *args, size_t n, void *ctx);
      uint8_t min_args;
      const char *help;
  } Command;

  static const Command COMMANDS[] = {
      { 0x01, handle_read,  2, "read <addr> <len>" },
      { 0x02, handle_write, 3, "write <addr> <len> <data>" },
      { 0x03, handle_erase, 1, "erase <sector>" },
  };

  Status dispatch(uint8_t cmd, const uint8_t *a, size_t n, void *ctx) {
      for (size_t i = 0; i < ARRAY_LEN(COMMANDS); i++) {
          if (COMMANDS[i].code != cmd) continue;
          if (n < COMMANDS[i].min_args) return STATUS_BAD_ARGS;
          return COMMANDS[i].fn(a, n, ctx);
      }
      return STATUS_UNKNOWN_COMMAND;      // one explicit case
  }

And help generated from the same rows, so it cannot go stale:

  for (size_t i = 0; i < ARRAY_LEN(COMMANDS); i++)
      print("%02X  %s\n", COMMANDS[i].code, COMMANDS[i].help);

Common pitfalls

More in Embedded C

• Interrupts, Rings & ConcurrencyThe handler is a second thread you did not declare. What is and is not atomic on a single core, the lock-free ring buffer and the conditions it requires, DMA and cache coherency, low-power modes and their wake sources, priority inversion, and debugging a race you cannot reproduce.
• Volatile RegistersMaster volatile keyword usage for memory-mapped registers in embedded C. Interactive simulator shows compiler optimization effects on register reads.
• User-Defined TypesDeclare your own types in embedded C: struct, union, enum, typedef, bitfields, designated initialisers, flexible array members and opaque handles.
• Embedded C + DSA 0 → 100One self-sufficient course connecting beginner C, Embedded C, hardware-facing APIs, bounded data structures, Embedded DSA practice, compiled code, diagnostics and production capstones.
• Bits, Fields & Fixed PointRegister fields and the mask conventions that silently disagree, Gray code and where one-bit-at-a-time matters, fixed-point arithmetic and the intermediate width a multiply needs, the undefined-behaviour traps in ordinary bit idioms, wire-format packing, and what each checksum detects.
• Types / PromotionUnderstand integer promotion and type conversion in embedded C. Interactive lab demonstrates implicit and explicit casting with signed/unsigned types.
• Compiler Workbench & TestingCompile real C for an embedded target and inspect what the compiler produced, then the discipline around it: where to draw the host-testable boundary, reading the generated assembly, undefined behaviour and the sanitizers, the warnings worth enabling, and measuring size and stack.
• Functions & ContractsDesign production C functions and modules with explicit preconditions, postconditions, ownership, status codes, opaque types, reentrancy, HAL seams and failure-state behavior.
• Arrays, Strings & BuffersArrays decay and the length does not travel; strings are a convention, not a type; and every length in a received packet is data rather than fact. Spans, the three string copies, framing and resynchronisation, serialisation, and parsing untrusted input safely.
• Object Layout & StorageWhere an object lives and what it costs: storage duration and linkage, the sections a declaration lands in, struct layout and the padding that makes a struct larger than its members, allocation without a heap, and integrity checks over stored data.
• C Basics & the Translation UnitFrom source text to a linked image: declarations against definitions, the translation unit the compiler actually sees, the preprocessor and what a macro can and cannot do, and the four build stages with the error vocabulary each one produces.
• Embedded CA complete source-to-silicon workbench: C semantics, arrays and APIs, compiler and startup, MMIO, interrupts, DMA and caches, bounded systems, testing, safety evidence and production defense.