genau

Overview

PDF manual "genau.pdf" available

Purpose of the program

Current version: 1.1.8

The genau program reads a lookup-table-based automata description and creates a C function to simulate the automata.
An automata is a state machine. An internal state is kept. If an input occurs the state machine generates output and may change into another state.
New state and output depend on both current state and input.

License

The program is published under the terms of a BSD-style license.

Lookup table versus function

State machines are often described by drawn state diagrams. This is extremly difficult to use in the C programming language.
Other types of representations are lookup tables or a function.
A lookup table in C might look like this:

typedef struct {
  int old_state; int input; int new_state; int output;
} state_machine_rule;

state_machine_rule my_state_machine[] = {
  { 0, 0, 0, 0},
  { 0, 1, 1, 0},
  { 0, 2, 1, 1},
  ...
};

Such a lookup table is easy to maintain. Unfortunately lookups take time. In best case - you manually sorted the entries and write a good lookup function - lookup time grows logarithmically with the number of entries.
For unsorted lookup tables there is a linear grow.
Also when using wildcards like

{ 0, -1, 0, 3}

for "when in state 0 and any input not explicitly mentioned occurs, remain in state 0 and return output 3", time grows faster than logarithmic over the number of entries.
 
Writing a function in C directly like

int state_machine_function(int *state, int input)
{
  int back = 0;
  if(state) {
    switch(state) {
      case 0: {
      switch(input) {
        case 0:  { *state = 0; back = 0; } break;
        case 1:  { *state = 1; back = 0; } break;
        case 2:  { *state = 1; back = 1; } break;
        default: { *state = 0; back = 3; } break;
      }
      ...
      }
    }
  }
  return back;
}

produces faster code but is difficult to maintain.
 
So the solution is to manually edit and maintain a lookup table and to produce a C function automatically from it.