Aerospace Software Ltd.

Objective Real-Time Software on the ADSP21XX

Lookup Tables and the ADSP 21XX

General

In order to handle objects effectively, one needs a clear understanding of the Data Address Generator file and the do until loop mechanism. These constructs provide a way to handle lookup tables and perform register indirect jumps, to do such neat things as finite state machines inside multiple identical objects.

Loop Restrictions

When coding counted loops, the following restrictions should be borne in mind.

The last instruction of a loop may not be a call. The call will return after the loop, thereby destroying the stacks.
One may not jump out of a loop, never to return. This act will also destroy the stacks.
Nested loops may not end on the same label. This will confuse the loop comparator.

Loop Restrictions

The last instruction of a loop may not be a call.

One may not jump out of a loop, never to return.

Nested loops may not end on the same label.

Therefore, if time is not critical, always follow the loop until label with a nop. When speed is of the essence, you can put an instruction in there, provided that it is not a call. Nested loops are best explained by having a look at example 1.

Example 1.  Nested Loops

cntr = 10;
do loopout until ce;
   cntr = 100;
   do loopin until ce;
      /* do loop stuff 1000 times in here */
loopin:  nop;
loopout: nop;

Data Address Generators

The 21XX family has two data address register files. Each file has a set of four registers which allow linear or circular addressing of arrays. The DAGs have a few limitations that one needs to be aware of.

The DAG1 file can be used for DM only.
The DAG2 file can be used for DM or PM.
Only DAG1 can perform bit reversed addressing.

Therefore, use DAG1 for table lookups and DAG2 for register indirect jumps.

Data Address Generators

Use DAG1 for table lookups and DAG2 for register indirect jumps.

Each DAG is a set of registers that are used in combination. The i-register contains the address. The m-register contains the modifier that will be added to the i-register AFTER the access had taken place. The l-register contains the length of a circular buffer. Ensure that the relevant l-register is zero, for linear addressing.

A typical indirect access instruction looks like this:

   ar = dm(i1, m1);

This instruction will move the data pointed to by the i1, to the accumulator ar, after which i1 will be post modified by m1, in anticipation of the next access.

While it is possible to mix and match i and m-registers, this should be avoided, simply because it is confusing, which can cause bugs.

Handling Multiple Objects

Multiple objects can be handled by a loop, which will cause the same code to be executed repeatedly, to service each object in turn. Typically, a system will have a bunch of common stuff to perform after which it has to service a set of identical objects, such as four audio CODECs. This can be performed in a simple scheduling loop.

Assume that the System States module (STA) performs the main scheduling loop, as shown in example 2 below.

Example 2.  Object Scheduling

#define STA_OBJ_MAX     4

/*
 * Start of scheduling loop
 */
sta_schedule:
   /* do common stuff */

   /* handle 4 objects */
   m1 = STA_OBJ_MAX;
   cntr = STA_OBJ_MAX;
   do sta_obj_loop until ce;
      ar = m1;             /* decrement the object counter */
      ar = ar - 1;
      m1 = ar;             /* keep the object counter in m1 */
      call obj_handler;    /* call the object handler */
sta_obj_loop: nop;

   jump sta_schedule;      /* do forever until the power fails... */

Note that we keep the object counter in m1. We'll talk more about that later.

Table Lookups

If we save the object instance number in ax1, then a lookup of an object variable can be performed as indicated in example 3 below.

Example 3.  Table Lookup

/* ax1 has the object instance number 0..3 */
ay0 = ^lookuptable;  /* get the table address */
ar = ax1 + ay0;      /* compute the lookup address */
i1 = ar;             /* m1 don't care, if we are not going to use i1 again */
ar = dm(i1, m1);     /* lookup */

This example will work, but it is not very optimal. Alternatively, we can use the post modify function of the DAGs to our advantage for a 25% speedup on the above example. If we keep the object instance in a modify register m1, the lookup code can simplify a little.

Example 4.  Improved Table Lookup

/* m1 is the object index 0..3 */
i1 = ^lookuptable;   /* get the table address */
modify(i1, m1);      /* post modify i1 */
ar = dm(i1, m1);     /* lookup the value */

This is the way to handle objective code. It is not as efficient as simply addressing a bunch of named variables, but the advantage is that you need only debug one piece of code, instead of multiple copies thereof.

Arrays of Variables

The advantage is that you need only debug one piece of code, instead of multiple copies thereof.

As you would be using this table lookup function a lot, it is a good candidate to turn into a macro, as shown in example 5.

Example 5.  Object Read Macro

/*
/*
 * Macro:         MAC_RD_DM
 * Description:   Read a data memory array
 * Parameters:    addr = DM address (^TABLE)
 *                index = DM index (ar)
 * Constraints:   m2 = modified
 *                i2 = modified
 * Returns:       data (ar)
 */
#define  MAC_RD_DM(data, addr, index)  \
   i2 = addr;           /* get the table address */ \
   m2 = index;          /* get the table index */ \
   modify(i2, m2);      /* post modify i1 */ \
   data = dm(i2, m2);   /* read the value */

Now that this macro is defined, you need never worry about how table lookups work anymore. In objective code, this macro will be used very often, for every variable that you want to read from an array. Clearly, you also need a reverse thereof, that will save a variable in an array.

Example 6.  Object Write macro

/*
/*
 * Macro:         MAC_WR_DM
 * Description:   Write to a data memory array
 * Parameters:    addr = DM address (^TABLE)
 *                data = data to write to DM (ar)
 *                index = DM index (ay1)
 * Constraints:   m2 = modified
 *                i2 = modified
 * Returns:       none
 */
#define  MAC_WR_DM(data, addr, index)  \
   i2 = addr;           /* get the DM table address */ \
   m2 = index;          /* get the table index */ \
   modify(i2, m2);      /* post modify i1 */ \
   dm(i2, m2) = data;   /* save the value */

Finite State Machines

A finite state machine is a construct that can be in only one state at any one time. Furthermore, all the possible states and events are pre-defined, which ensures that all possible actions of the machine are known. This ensures deterministic behaviour, which is essential in any real-time system. Finite state machines are easy to debug, since while they can perform the wrong action, they cannot perform anything that is totally unexpected. Even a complex finite state machine usually works reasonably well the very first time around, which is unusual for any piece of software.

Finite State Machines are Deterministic

It can be in only one state at any one time.

A finite state machine can perform the wrong action, but it cannot perform anything that is totally unexpected.

Register indirect jumps are useful for the operation of table driven finite state machines. Unfortunately the 21XX cannot perform a register indirect call, which would have been neater, but we can construct a good finite state machine using a jump table.

States and Events

A State is a condition of rest, or maximum inertia.

An Event is whatever happened to cause a State change.

If you have trouble defining a State, it is probably an Event...

Assume that we have a finite state machine with four events that need to be handled. This is an example of actions that can be performed through a maintenance port on a system. Assume that the finite state machine is part of a module called Menu (MNU).

Example 7.  Finite State Machine

#define  MNU_LAST_EVENT    4

/*
 * Define the constant table in Program Memory
 * so it will be downloaded from EPROM at startup
 */
.VAR/PM/RAM/seg=INT_PM  MNU_TABLE[MNU_LAST_EVENT];

.INIT MNU_TABLE:
   ^mnu_initialize,  /* power up */
   ^mnu_load_eprom,  /* load a new software version */
   ^mnu_setup,       /* setup the system defaults */
   ^mnu_test;        /* test the system */

/*
 * Menu Finite State Machine
 * use DAG2 for PM access
 * m4 has the event number 1..4
 */
mnu_start:
   i4 = ^MNU_TABLE;     /* get the PM table address */
   modify(i4, m4);      /* post modify i4 */
   ar = pm(i4, m4);     /* lookup the jump address */
   i5 = ar;
   jump (i5);           /* jump to the event handler */
mnu_continue:           /* the return address of the event handler */

This is a very simple finite state machine, having only four events and only one state (Or four states with one event per state, depending on how you want to interpret it). The neat thing is that a state machine such as this, can be used by many objects, just keep the object number in m1.

A machine with multiple states and events and a multi dimensional lookup table, is best avoided. The processor architecture makes one dimensional arrays easy to handle, therefore one should stick to it, in the interest of speed. Anything requiring a multi dimensional table, can also be done with a one dimensional table. After all, all of memory is a one dimensional table!

One Dimensional Tables

Anything requiring a multi dimensional table, can also be done with a one dimensional table.

An important thing is to keep the flow of the program neat and tidy. Although the state machine operates with a jump to the event handler, ensure that all handlers will return to the next line at mnu_continue, just as if it was a call to a procedure. This will ensure that the code remains easy to read and understand.

Since all your finite state machines are likely going to be of the one dimensional kind as above, you can turn this little critter into a macro too, as described in example 8.

Example 8.  Finite State Machine Macro

/*
/*
 * Macro:         MAC_MACHINE
 * Description:   Finite State Machine macro
 *                Performs a jump to an event handler
 * Parameters:    table = State Transition Table address (^TABLE)
 *                event = Event number (ar)
 * Constraints:   modifies i4, m4, i6, ar
 * Returns:       none
 */
#define  MAC_MACHINE(table, event) \
   m4 = event;          /* get the event */ \
   i4 = table;          /* get the PM table address */ \
   modify(i4, m4);      /* create a table pointer */ \
   ar = pm(i4, m4);     /* lookup the jump address */ \
   i6 = ar; \
   jump (i6);           /* jump to the event handler */

Wow, now we can write object oriented finite state machines. Wheeee! Note that it may be wise to add a range check on the event number in ar, since a bad lookup will result in very weird and wonderful behaviour!

Complex Finite State Machines

In a complex finite state machine, every event handler can be made to return a next event in m4, which will allow the machine to loop on itself until the next event is set to a value that is out of range, indicating that the job is done.

An example where this feature can be handy, is the processing of a serial protocol. If the first event idicates that a bit was received, the receiver handler may find that it was the last bit of a message, which means that the CRC needs to be tested, so it then returns a CRC event, to cause the CRC handler to be activated. The CRC handler may reject or accept the message, causing something else to happen.

Finite State Machine Testing

The whole machine can be readily tested by injecting events into the event number.

This loopback method ensures that every event is handled by a short and simple event handler, which is easy to test in isolation. The whole machine can be readily tested by injecting events into the event number m4 and one would need only a single breakpoint, to see what happened and what it is going to do next. This easy test capability is probably the main reason for the popularity of finite state machines.