Paul Fischer holds a B.S.C.S. from the University of Illinois at Champaign-Urbana. He is currently employed by Rockwell International as a software engineer. You may contact him at 6111 Pershing Ave., Downers Grove, IL 60516, (708) 969-2610.
State Machines are used in various applications involving rules, such as data link protocols, screen management, and device control. In simple applications, case statements are generally used, but in complex applications state tables have greater appeal. This article describes state machine implementation using state tables in C.
Definition
A state machine is a relatively simple entity with a primitive memory and a set of rules. The memory provides the state machine with the knowledge of what it is doing right now. The set of rules defines how a state machine reacts to certain events. In essence, a state machine is a tool that allows programmed control over known but dynamic conditions.The following terms are used throughout this article:
Device — the instrument (either logical or physical) that the state machine is controlling. Some examples are a telephone line, a robot, and a data link protocol.
State — the current activity of the device. For example, a telephone line is ringing, a robot is off, a data link protocol is XOFFed.
Event — a stimulus introduced to the device that potentially changes its state. For example, the telephone line is answered, the robot's power button is pushed, a timeout occurs for the data link protocol.
Transition — a passage from one state to another. The direct result of the receipt of a valid event.
State machines are then defined in terms of valid states, valid events for each state, and the transition from one state to another for each valid event. The benefits of a state machine increase with the complexity of the applica- tion. Over 20 states is complex. For the purposes of this article, however, I have created a simple example to illustrate the techniques involved.
Example
The following example walks through a state machine for a video cassette recorder (VCR). It shows the definition of the operation of VCR through a state transition diagram, and how to transform the diagram into C.Figure 1 is the state transition diagram for the VCR, which shows the rules for how the VCR operates. The circles represent the valid states, (states are prefixed with an S_), and the arcs represent transitions. The event that caused the transition is a label on the arc, (events are prefixed with an E_).
Consider the VCR in the state S_OFF. Only two events cause a transition to a new state: the E_POWER event causes the VCR to be placed in the S_POWER state; the E_TAPE_IN event automatically turns the power on and places the VCR in the S_READY state. A valid event does not necessarily cause a transition to a new state. For example, every state except S_OFF accepts an E_CHAN_UP and E_CHAN_DOWN event so that channel selection can occur. These events cause a transition to the same state.
Once the operation of the device has been described in terms of states, events, and transitions, the actual internal operation of the device becomes important. For example when the VCR moves to the S_PLAY state, some action is necessary to cause the tape to begin playing, and "PLAY" must be displayed on the VCR LED display. Another example would be to eject the tape on any transition to the S_OFF state. Actions such as these are taken during the transition and are implemented as a function call or list of function calls. All of these actions are added as the state transition diagram is transformed into a state table.
State Table — C Structures
Listing 1 shows the #defines for all valid states and events and the structure definition of the state table. The four items necessary in the structure to define the state table are: the state, a valid event for that state, the next state to transition to for that event, and a list of functions to perform for the state/event combination. The structure S_TABLE defines each of these. Note that a fixed number of functions are set for the function list.Once the structure is in place, a fairly straightforward procedure is required to transform the diagram in Figure 1 into the state table in Listing 2. For each state, you list the state, a valid event, the next state, and the set of functions to perform. The states are listed in numeric order in the state table, so reading the table is easy. For instance, the S_PLAY state has three valid events: E_STOP, E_CHAN_UP, and E_CHAN_DOWN. When these events are received, the functions in the corresponding function lists are executed, and the device transitions to the next state. Since this code is not going to actually run inside a VCR, the set of functions is limited — display the new state, increment or decrement, and display the channel. If this were a real application, additional functions that caused playing and recording to begin would be referenced in the function list also.
Table Driver
Once the table is defined, there must be some code to read the events and drive the operation of the VCR as specified in the state table. Listing 3 shows the source for the driver, which accepts an event and a standard argument of type pointer to ARG (ARG is defined in Listing 1) . The ARG structure contains everything the state machine needs to store about itself. In this case, it is simply the current state of the VCR and a counter for channel selection. When the driver receives an event, it locates the current state in the state table, finds the event passed in, sets the next state, and executes the function list. All functions are passed the same standard argument ARG. If the event is not found, an error is noted. For the VCR, invalid events are ignored. Other devices may want to take some other type of action.Also included is a function to read events. In general, events are read from some type of queue, be it hardware or software. Events for this program are read from standard I/O. Note that the current state and any other data required is initialized before the event loop begins.
The last task is to write the functions contained in the function lists. Generally, these are small functions, each of which performs one task. When you implement a state table this way, the code provides an excellent, self-contained document for the operation of the device. Listing 4 shows the three functions referenced in the state table.
Alternative Organizations
The state table can be optimized for execution speed and memory allocation.You can improve performance by reducing the search times required each time an event occurs. Through a slight restructuring of the S_TABLE structure, the state can be used as a direct index into the state table. The cur_state field then appears only once, regardless of the number of events for that state. (It really doesn't need to appear at all since the array index can be used.) It is followed by a variable length event list. Then the driver can directly index to the current state upon each invocation. Another performance gain can be realized by placing the events for each state in "most likely to occur" order.
You can add space savings and flexibility by removing the restriction on the number of functions in a function list. When this list is variable length, you gain two benefits. You no longer need to store NULL function pointers as padding, and there is no artificial restriction on the number of functions a state/event combination may have.
As with most benefits, there are also costs to pay. To maintain readability of the state table with the previous suggestions, you will most likely have to process the state table or convert it from data to source. Simple initialized data cannot be used as in the original organization. Also, a different driver would have to be written to handle the different organization.
Summary
For the right application, a state table approach can provide considerable benefits. Its combination of readability and extensibility lets you easily add features. For complex or multiple instance devices, organizing the source code as a mirror of the device's actual operation provides a versatile, straightforward, and efficient means of writing software.