An alternative approach to Lab 5

Introduction

There is alternative approach to Lab 5 based on a data-driven methodology rather than the dispatch table method described in the lab. The notes in the file ~courses/ref/assemblyProgramming.ps (pages 132-136) provide some general theory for this approach and give a simple example. Students who took ELE 428 (Engineering Algorithms and Data Structures) have also encountered the general data-driven approach to state machines in Lab 4 for that course last year.

The state machine in Lab 5 differs from the simple state machines discussed in the notes in several ways:

1. First, the inputs that cause state transitions are not simple numbers like 00, 01, 10, or 11 that come from a single input stream. Rather, they are events that come from different hardware components (such as the two bumper switches) or are generated internally (the time out events). This requires a more sophisticated method for obtaining an event and converting it into a simple binary number that can be used to drive a data-driven state machine.
2. Next, the states in Lab 5 have associated behavior that must be performed each time a state is entered.
3. Furthermore, each state has an associated parameter--its maximum duration--that is used to generate an internal timeout event.
4. Finally, there are common things that should be done periodically in Lab 5 (such as display current state name and/or battery voltage.)

Consequently, the simple translation of a state diagram to data structures and the simulation algorithm must be slightly modified. The next sections discuss some possibilities for these changes.

Lab 5 State Data Structure

What information is needed to describe the kinds of state used in Lab 5?

Clearly, we need to describe the state transitions. Assuming there are 4 possible events, the next state for each of these events must be described in the state data structure. Since each state can be identified with an 8-bit integer (allowing up to 256 different states, although we only need have 6 here), the 4 possible next states can be described with 4 bytes.

In addition, we need to describe the maximum duration for a state. This occupies another byte. A pointer to a null-terminating string takes up 2 more bytes and, finally, a pointer to a state specific initialization subroutine uses 2 more bytes. In total, then, the total number amount of memory required to completely describe each state is 9 bytes. Since there are 6 states, all of the state descriptors fit into 54 bytes, a modest amount of memory.

FORWARD_desc
             fcb FWD_TURN       ;next State if time out
             fcb REVERSE        ;next State if Front collision
             fcb FORWARD        ;next State if Rear collision
             fcb STOP           ;next State if TEND (global time out)
             fcb TALARM_FWD     ;maximum duration in state
             fdb doForward      ;function pointer on entering state
             fdb forwardName    ;pointer to state name (string)

The suggested approach involves two algorithms:

1. The state machine implementation (doStateMachine).
2. The event gatherer (getEvent).

/* Assume statePtr is a pointer to a state descriptor record */
/*    i.e. statePtr is the address of the record's first byte */
/* Assume that currentState is the current state number (between 0 and 5) */
repeat
     setTimeOut(statePtr->timeOut)
     invoke subroutine statePtr->function
     repeat 
       wait for an event /* call getEvent until it returns something != -1 */
       nextState = statePtr[eventNumber]
     until nextState != currentState
     currentState = nextState
     determine statePtr
until forever

The getEvent subroutine is simpler than the doStateMachine routine. Initially, however, I recommend you use a simple stub for getEvent and concentrate on getting a working version of doStateMachine.

Although it is possible to write each of these core routines in about 21 lines of code each, you should not aim for such compact code. However, if you find that you need more than 60 instructions for either of these routines, you are likely using the wrong approach.

Caveats

The data-driven state machine approach is powerful, but may not always be the best solution. Some of the assembly language techniques are tricky to use properly. I recommend that you not even consider using this alternate approach unless you feel you are an above-average assembly-language programmer (relative to your classmates.) Even then, however, you may well decide to use the more straightforward (but, arguably, less elegant) solution outlined in the lab.