Front Panel

Designing Software for

Embedded User Interfaces

Niall Desmond Murphy

R&D Books
Lawrence, Kansas 66046
R&D Books
an imprint of Miller Freeman, Inc.
1601 West 23rd Street, Suite 200
Lawrence, KS 66046
USA

Designations used by companies to distinguish their products are often claimed as trademarks. In
all instances where R&D is aware of a trademark claim, the product name appears in initial capi-
tal letters, in all capital letters, or in accordance with the vendor’s capitalization preference. Read-
ers should contact the appropriate companies for more complete information on trademarks and
trademark registrations. All trademarks and registered trademarks in this book are the property of
their respective holders.

Copyright  1998 by Miller Freeman, Inc., except where noted otherwise. Published by R&D
Books, an imprint of Miller Freeman, Inc. All rights reserved. Printed in the United States of
America. No part of this publication may be reproduced or distributed in any form or by any
means, or stored in a database or retrieval system, without the prior written permission of the
publisher; with the exception that the program listings may be entered, stored, and executed in
a computer system, but they may not be reproduced for publication.

The programs in this book are presented for instructional value. The programs have been care-
fully tested, but are not guaranteed for any particular purpose. The publisher does not offer any
warranties and does not guarantee the accuracy, adequacy, or completeness of any information
herein and is not responsible for any errors or omissions. The publisher assumes no liability for
damages resulting from the use of the information in this book or for any infringement of the
intellectual property rights of third parties that would result from the use of this information.

Cover art created by Robert Ward.

Distributed in the U.S. and Canada by:

Publishers Group West
P.O. Box 8843
Emeryville, CA 94662
ISBN: 0-87930-528-2

R&D Developer Series

ii
 Chapter 3

Scheduling and Managing

User Events
Chapter 2 discussed the model-view-controller (MVC) paradigm used to decompose a
system. Serious discussion of the controller was not handled in that chapter, because it
is better discussed in tandem with queuing and tasking, which I will cover in this chap-
ter. When an event has been successfully detected, it may not be possible to respond to
it immediately, so the response may have to be scheduled for execution at a later time.
Queues and tasks allow us to schedule and control such asynchronous activity.
This chapter makes use of the functionality provided by a real-time operating sys-
tem (RTOS). The RTOS used in the examples is µC/OS (Labrosse, 1992), but its
functionality is similar to that provided by any other RTOS. If you are not familiar
with the use of an RTOS, you may want to read Appendix A before proceeding.

3.1 User Events on the Desktop

With a desktop operating system, much of the interpretation of events has been han-
dled for you. Some simple function allows you to request the next key pressed by the
user. Any queuing, debouncing, or mapping from the codes returned by the keyboard
to standard ASCII characters has already been performed. If the system has a graphi-
cal user interface (GUI), mouse events may have already been associated with the
object the user selected. In some cases, the control is passed to the graphics environ-
ment via a function called something like ProcessUserEvents(). That function reads

27
28 — Front Panel: Designing Software for Embedded User Interfaces

the event queue and calls the appropriate function for each event as it is popped off
the queue. Much of the flow of control is hidden from the programmer, as it should
be. There is no reason for the programmer to know how the key or mouse events are
read, filtered, or queued by the system.
However, the embedded programmer is often faced with hardware designed
in-house that cannot be integrated with a commercial operating system. Many of the
principles implemented by the operating system or by GUI toolkit vendors are the same
as those you can implement in your own embedded system. The principles are the same
whether the interface is as complex as a full GUI or as simple as a digital watch.

3.2 Polling versus Interrupts

At the lowest level, events are detected by the hardware. Software must detect any
change in order to handle the event. There are three basic methods.
• Polling from the main flow of control
• Timed polling
• Interrupts

3.2.1 Polling from the Main Line

Polling from the main flow of control means reading the hardware once every time
around the main loop.

void main(void)
{
initialize();
while (1)
{
e = readEvent();
if (e is a valid event)
{
processEvent(e);
}
}
}

This technique works in simple cases, but if processing an event takes longer than
the time for an event to occur, some events may be missed. Events cannot be queued
to be processed later. This gets more difficult if there are several kinds of events that
you need to prioritize. Because of these restrictions and because of its simplicity, this
approach is not discussed any further.
 Scheduling and Managing User Events — 29

3.2.2 Timed Polling

Timed polling involves reading the hardware on a regular, timed basis. If an event is
found, it is queued. The main flow of control then reads the queue after each event
has been processed. Polling of the hardware could be triggered by a timed interrupt.
If an RTOS is available, it is preferable to have an RTOS task wake up from a sleep
every time a read is due. So now there are two loops: one for the polling task and one
for the task processing the events. Each loop runs in a separate task, so they are exe-
cuted in parallel.

void keyPollTask(void)
{
while (1)
{
e = readEvent();
if (e is a valid event)
{
enqueue(e);
}
sleep(poll_period);
}
}
void eventProcessingTask(void)
{
while (1)
{
e = dequeue();
processEvent(e);
}
}

This arrangement allows the user to type ahead. The extra events sit on the queue
until the event-handling loop is ready for them. The flow of control can be seen in Fig-
ure 3.1. The event e2 was detected before e1 had been completely processed. If the
poll had not taken place before the processing of e1 was complete, the event could
have been missed completely. The polling period must be chosen so that no events are
missed. At the same time, the higher the frequency of polling, the more CPU cycles
are spent checking for events, even when no events have taken place. Missing events
is less likely if the hardware latches an event so that it can be detected an arbitrary
period of time after the occurrence. The latched data is then cleared by software so
that the hardware is ready for the next event. This is only a partial solution because
during the period that data is in the latch waiting to be read, no further events can be
detected. The latch has effectively provided a queue of length one.
30 — Front Panel: Designing Software for Embedded User Interfaces

If there are delays in the hardware during the readEvent() function, the control
can switch to the event being processed during those delays. A delay may be inserted
to allow an output signal to settle before reading the input. These context switches are
not shown in Figure 3.1.
If you are concerned that the polling interval you have chosen may miss events
occasionally, simply run the system with the polling set at half the design frequency. If
no events are missed, you can trust the design frequency. Such a check is worth the
effort, because operators will get quicker at using the device over the years, possibly
quicker than the testers. As well as decreasing the frequency, it is also useful to increase
the polling frequency during testing. Some motion detection devices may generate an
event on every poll. This stream of events may be in danger of flooding another part of
the system. Increasing the polling frequency stress-tests such conditions.

3.2.3 Interrupts
To use interrupts, the event-detecting circuit must be wired to one of the processor
interrupt lines, while the polling methods require only that the event-detecting circuit
be readable, usually using the address and data lines. An interrupt, unless disabled,
immediately switches the flow of control to the interrupt service routine (ISR). Simi-
lar to timed polling, the ISR queues the event until the main flow of control has time
to process it. Figure 3.2 shows the timing diagram for the same events with interrupts.

Figure 3.1 Task-timing diagram for two events.

e1 detected e2 detected No event detected

Polling Task
Polling period

Start handling e1 Start handling e2

Event-handling
Task

Finish handling e1 Finish handling e2

This timing diagram shows two events detected by the polling task.
The event-handling task processes each one in turn.
 Scheduling and Managing User Events — 31

Note that there is no interrupt when there is no event. In this case, the time between
the detection of e1 and e2 is not predefined. Interrupts are useful when the event is
very brief and may be missed by a polling routine.
The interrupt mechanism can be used without an RTOS. Effectively, the inter-
rupt supplies one thread of control while the main flow of execution provides
another. Obviously, the interrupt mechanism can still be used if there is an RTOS
available, but note that it is not possible to place the interrupt’s thread of control into
the priority order dictated by the RTOS. This may be important if you do not want
the keyboard-scanning routines to interfere with other high-priority work that the
processor must perform. Disabling the interrupt during some high-priority sections
of the code may be an option, but this can increase the complexity of the code.
The overhead associated with polling, when there is no input present, might make
you think that the interrupt-driven system is more efficient. This is not always the case.
The average overhead in the interrupt-driven system is lower, but the average can be a
misleading metric. Consider a keypad that is polled every 10 milliseconds (ms). It takes
0.1ms to poll the keypad when there are no keys selected and 0.3ms to perform the poll
when there is a key present. So the overhead associated with the keypad is between 1
percent and 3 percent of the total CPU bandwidth. It is likely to be 3 percent when the
system is doing most of its work. This is because once the user presses a key, he is
likely to keep it depressed for several polls. Say, the user holds down a button for
300ms. During that time, the event is detected and enqueued to the event-handling task.

Figure 3.2 Task-timing diagram for interrupts.

e1 detected e2 detected

Interrupt Handler

Start handling e1 Completely handle e2

Main Control Loop

Finish handling e1

This timing diagram shows two events detected by the polling task.
The event-handling task processes each one in turn.
32 — Front Panel: Designing Software for Embedded User Interfaces

The event-handling task processed that event. Say that event takes 250ms. The event is
complete, but during its processing, the overhead from the keypad is 3 percent because
the user kept his finger on the key. This is not unrealistic, because most people move
their fingers slowly relative to computer speeds. A similar scenario arises with motion
devices such as a mouse or a dial. While one movement is being processed, it is quite
likely the user has made another movement. The events from a motion device arrive in
bursts. For these bursts of activity, the timed polling approach has another advantage.
The change between two consecutive reads reflects the speed at which the device is
moved. This makes it easier to apply rate-sensitive algorithms to the response. This is
not true of an interrupt-driven approach because the time between successive reads var-
ies, and measuring that time may be nontrivial.
Now, look at the response in an interrupt-driven system. If the key input is not fil-
tered electronically, the interrupt may have to be debounced by disabling or ignoring
the interrupt for a certain period. Sometimes, it is not possible to disable the interrupt
without the risk of missing other events. If the interrupt is not disabled, many interrupts
may take up a large percentage of processor time at the exact moment an event needs to
be processed. If you can disable interrupts, you need to find an appropriate point in the
code at which the interrupts can be reenabled. If you wait until the event is processed,
you risk missing a second event.
If the period for which you disable the interrupts is the same as the poll period, the
overhead when the system is busy is the same for both designs. Picking the same figure
for the poll period and for the interrupt disable time is reasonable, because this is the
amount of time that can pass without missing an event. The performance during the rest
of the time is often irrelevant. If there is no system activity on the user interface, the
processor responsible for the user interface will have spare CPU cycles available.
For highly responsive systems, interrupts are the only way to detect events, but on a
user interface, you should always give timed polling serious consideration. The over-
head is bounded and predictable, the hardware is less complex, and most important, the
software is easier to write and, therefore, to debug.

3.3 Queuing
Whether the input event is detected in a polling task or in an interrupt, the request has
to be queued. If you have an RTOS, it provides a queue structure. The enqueue and
dequeue operations are atomic, avoiding any problems caused by simultaneous
access. If you do not have an RTOS, you can implement the queue by using an array
as a circular buffer. You also need some means of locking that data to ensure that it is
not read while it is being written. Disabling interrupts while the queue is being read is
the simplest way. Within the interrupt routine itself, other interrupts have to be dis-
abled while the queue is being written to protect against nested interrupts causing
overlapping writes to the queue.
 Scheduling and Managing User Events — 33

The length of the queue depends on the nature of the input. In desktop systems, a
lot of type-ahead is appropriate, allowing the user to type commands or sentences.
Most embedded systems do not need more than one-key type-ahead. If key-up as well
as key-down events are detected, you may want to allow a longer queue. Motion
devices that generate a stream of events also require a longer queue. Once the queue is
full, most systems function if the following events are thrown away. Users soon real-
ize that they have limited type-ahead (or move-ahead, in the case of a motion device).
If you discard events, you must ensure that events do not depend on each other. If a
key-down occurs, the logic of the controller may be upset if the corresponding key-up
never occurs. If this is the case, the queue must be sized to cope with the highest pos-
sible input rates and never lose events.
A general-purpose queue contains elements of a fixed size. µC/OS allows only a
single void pointer as the element of the queue. In the example that follows, I main-
tain a separate array to hold the data and point to it from the µC/OS queue.
The structure placed on the queue defines a protocol between the physical layer
and the controller. Consider a control system with the display shown in Figure 3.3,
which illustrates the screen layout when running the keyq example program on the
companion disk. The user can view and set three parameters: temperature, pressure,
and flow. The LED lights when the key next to it is selected. The corresponding set-
ting then appears in the numeric display, and the user can adjust the values using the
arrow keys. If the display is not touched for 10 seconds, it times out, the numeric dis-
play goes blank, and all LEDs are turned off. The display is also capable of displaying
two different alarms: high temperature and high pressure. So the task managing the

Figure 3.3 keyq example screen layout.

87
Alarms

Temperature HIGH TEMPERATURE

Pressure

Flow

= LED off = LED on

34 — Front Panel: Designing Software for Embedded User Interfaces

display can handle three types of event: key events, alarm events, and timeouts. I can
place these three types of events on the queue using the following structures.

/*
Key Mapping
*/
typedef enum { TEMP_KEY, PRES_KEY, FLOW_KEY, UP_KEY, DOWN_KEY,
NO_KEY} KeyValue;

typedef enum { HIGH_TEMPERATURE, HIGH_PRESSURE } AlarmType;

typedef struct {
AlarmType type;
Boolean value;
} AlarmStruct;

/* Packet Structure */
typedef enum {KEY_PACKET, ALARM_PACKET, TIMEOUT_PACKET} PacketType;
typedef struct {
PacketType type;
union {
KeyValue keyValue;
AlarmStruct alarm;
} data;
} QPacket;

By storing the data for the different types of event in a union, I can minimize the
size of the packet I place on the queue. Notice that there is no data associated with the
timeout. The fact that it occurred is sufficient information because there is only one
type of timeout.

3.4 Is an RTOS Needed?

For many small projects, no RTOS is required. Many complex programs would be
almost impossible to write without one. A lot of projects fall somewhere in between,
leaving the developers wondering if the learning curve, and possibly a license fee, are
worth the investment.
An RTOS provides the ability to manage time, so the more limiting and complex
the time constraints of the program, the more likely you can benefit from an RTOS.
User interfaces tend to be slower than many other parts of the software, and they do
not need to react as fast as process control feedback loops or communications soft-
ware. However, the processor that controls the front panel generally has other respon-
sibilities. An RTOS allows the designer to limit the processor time that responding to
user events may consume. On many devices, it is not acceptable to allow the user to
halt some operations by repeatedly pressing on a key. Even if the key press is invalid
 Scheduling and Managing User Events — 35

and meaningless, handling it may consume processor time that should be spent on
some other activity. It is possible to manage such timing issues by carefully structur-
ing the code to provide for each of several functions that get processed in turn. How-
ever, this can lead to spaghetti code. If you have a function that takes a relatively large
amount of time, you may have to place a function call in the middle of it, which
passes control to an unrelated area of the software to allow it to meet some deadline.
Such out-of-place calls are a sure sign that it is time to invest in an RTOS.
Because an RTOS supports multiple stacks and multiple threads of control, it
allows one event to be halted while a more important event is processed. The task that
has been halted can resume from the point at which it was before the context switch.
Interrupts provide a similar ability, but with some limitations. An interrupt requires an
external event. Sometimes, a task is driven by an internal event, such as a
queue-not-empty event. Generating an interrupt to reflect the internal event may be
difficult and may require extra hardware. Interrupt handlers work well when the work
they must perform can be restricted to a small time-slice. If an event triggers a func-
tion that will take several seconds to process, interrupts will prove unsuitable.
One approach to the task decomposition is to dedicate one task to the user inter-
face, while a number of other tasks manage the other responsibilities of the processor.
This works if user events can always be processed in a very short time. A fast proces-
sor may mean that the computations resulting from the event can be performed
quickly, but interfacing with other hardware may slow things down considerably. This
leads to timing requirements at two levels, which in turn leads to at least two tasks.
Assume that you are required to detect all key events and that the mechanical charac-
teristics of the key dictate that the shortest period during which the key event is
detectable is 50ms. If key events are polled, then a task must run every 50ms, or
faster, depending on whether the events are latched by the hardware. The polling itself
is generally a quick job and does not cause any other deadlines to be missed. The sec-
ond requirement is that while the event is being processed, a far longer period is
needed. Events may vary dramatically in the amount of time they take to be pro-
cessed, but this variation must not interfere with the performance of other tasks with
real-time deadlines. There is a danger that a continuous series of user events may halt
any task with a lower priority than the event-processing task.
Therefore, you generally want the polling task to have a higher priority than other
tasks that might delay the polling long enough that a user event may be missed. The
event processing task should run at a lower priority than tasks that cannot afford to be
delayed by user events. You will see another reason for the relative priorities of these
two tasks after I examine the tasks in the keyq example in the next section. The keyq
example is so small that it would not normally require an RTOS, but it is used here to
illustrate some important issues.
36 — Front Panel: Designing Software for Embedded User Interfaces

Although this analysis attempts to give you enough information to decide if an

RTOS is required for a particular project, the hardest part by far is to predict the tim-
ing behavior of your program before it is written. This is one area in which there is no
substitute for experience.

3.5 The Tasks

Using the queue defined previously as the communications protocol, I will divide the
keyq system into three tasks. The first is the keyPoll task, which polls the keypad and
sends a timeout if no keypad activity happens for 10 seconds. This task implements
the physical layer. The second is the monitor task, which raises alarms if the process
goes outside predefined temperature and pressure limits. The third task is the mvc
task. This task contains the model’s data and performs all the work of interpreting
events (the controller) and refreshing the display (the view). Figure 3.4 shows the var-
ious subsystems.
The interpretation of an event in the keyPoll task is independent of context. You
are merely interpreting which physical key was pressed. Once the event has been
passed to the controller, the controller can interpret that event using context supplied
by the model and the view. The pollKey() function is called to read the current char-
acter, if there is one. In the example code on the companion disk, this function merely

Figure 3.4 Task decomposition of keyq example.

Monitor

Event Queue Model

Controller
View
Physical Output
Layer
Physical Input Layer
(Key Poll task)

The three tasks of our example system communicate with one queue.
 Scheduling and Managing User Events — 37

uses the DOS functions kbhit() and getch(). In a real embedded system, the hard-
ware would be accessed rather than using kbhit() and getch(). Note that the delay
at the bottom of the loop is not equal to the poll period. The poll period is actually the
delay at the bottom of the loop plus the time it takes for one execution of the loop.

void far keyPollStart(void *data)

{
KeyValue key;
int timeoutCounter = 0;
data = data; /* avoid compiler warning */
while (1)
{
key = pollKey();
if (key != NO_KEY)
{
enqueueKey(key);
timeoutCounter = 0;
}
/*
Decide if no key has been pressed for
approximately 10 seconds
*/
timeoutCounter++;
if (timeoutCounter == 6*10)
{
enqueueTimeout();
}
/*
A delay is necessary here to ensure that this task does not
continuously poll, hogging the CPU. Note that 0.16 seconds
is fast enough to read the keys because they have already
been queued. Many keypads can have a complete key event in
0.05 seconds and if the keypad has not been polled in that
time then it is too late - the event has been missed.
*/
OSTimeDly(TICKS_PER_SECOND / 6); /* delays 0.16 second */
} /* end while (1) */
}

The calls to enqueueKey() and enqueueTimeout() place the appropriate event on

the queue. The actual implementation is µC/OS-dependent because µC/OS supports
only queue elements of type void pointer. For this reason, larger buffers have been
associated with the queue in the enqueuing functions.
Once the data is on the queue, the controller must have a way to extract it. The
infinite loop of the mvc task performs the first step of this interpretation.
38 — Front Panel: Designing Software for Embedded User Interfaces

void far mvcStart(void *data)

{
UBYTE errCode;
void *msg;
QPacket *packetPtr;
data = data; /* avoid warning */
initDisplay();
/* Initialise the model's data */
GS_settings.temperature = 10;
GS_settings.pressure = 20;
GS_settings.flow = 30;
while (1)
{
/*
Wait for next event.
Second argument is 0 meaning block until queue contains data.
*/
msg = OSQPend(G_mvcQueue, 0, &errCode);
assert (errCode == OS_NO_ERR);
packetPtr = (QPacket *) msg;
switch (packetPtr->type)
{
case KEY_PACKET:
handleKey(packetPtr->[Link]);
break;
case ALARM_PACKET:
handleAlarm(&packetPtr->[Link]);
break;
case TIMEOUT_PACKET:
handleTimeout();
break;
default:
assert(FALSE);
}
refreshDisplay();
} /* end while */
}

Note that this loop has no delay. The blocking point is the call to OSQPend(), which
does not return until there is some data on the queue. Thus this task consumes no CPU
cycles while there is no activity on the queue. Once an event does appear on the
queue, this task is ready to receive it.
The monitor task spends most of its time monitoring the hypothetical process
driven by the device. Whenever the temperature or pressure exceeds the acceptable
limit, the alarm is posted to the queue. In the example on the companion disk, I sim-
ply raise the alarms on a timed basis.
These tasks are actually configured and launched from the main function, but the
details are highly µC/OS-dependent, so I will not dwell on them here. There is more
information on task initialization in Appendix A.
 Scheduling and Managing User Events — 39

3.5.1 Priority in a Tasking System

It is important for the mvc task that reads the queue to run at a lower priority than the
tasks supplying the queue. That is because if the mvc task ran at a higher priority, it
would prevent the keyPoll task from checking for a new event while the mvc task
was processing an event, so a poll would not take place at the end of a poll period.
The poll would be deferred until the mvc task completed processing that event. The
chances of missing an event would be exactly the same as if polling from the main
flow of control. It also means that the queue length would never be greater than one.
Every time an event was placed on the queue, the mvc task would process that event
and prevent any further activity on the keyPoll task. Compare Figure 3.5 with Figure
3.1 to see the difference in the sequence of actions. If you decide that Figure 3.5 is
actually the preferred behavior for your application, the two tasks should probably be
merged into one.

3.5.2 Allowing Multiple Tasks Access to the Display

In the example, the mvc task is the only task that has access to the model or to the
physical display. In some cases, you may want different tasks to have access to the
display. If some user events take time to process, you may want to perform other
updates in parallel. Say you have a bar graph that is updated several times a second to

Figure 3.5 Task-timing diagram with reversed

priorities.
e1 detected e2 detected No event detected

Polling Task
Polling period Read held off
by this amount

Handle e1 Handle e2

Event-handling
Task

This timing diagram shows two events detected by the polling task in which the
polling task's priority is lower than the event-handling task. e2 is detected later
than in Figure 3.1 and could possibly have been missed.
40 — Front Panel: Designing Software for Embedded User Interfaces

give real-time feedback of one of the monitored parameters. If some of the key-press
events take more than a second to process, the bar graph appears to freeze briefly. A
case could be made that one task should manage the key events while another updates
the bar graph.
Breaking up the responsibility for updating the user interface raises a couple of
issues. The hardware controlled by each task may be linked. The LEDs that make up
the bar graph may be controlled by the same controller chip that controls other LEDs
on the display. If two tasks simultaneously access that controller chip, the LED’s dis-
play may become corrupted. Another example would be a graphics screen driven by a
VGA controller. VGA controllers are not reentrant, so two tasks interleaving their
access might lead to unpredictable results.
The hardware can be protected by a lock at the time of the update. Such locks,
sometimes called resources, are supplied by most RTOSs. You can allocate one lock
for each piece of the user interface hardware, or a single lock can be used for the
whole front panel. Because all the updates to the user interface happen in a few
refresh functions, it is straightforward to pick the places at which the hardware needs
to be locked and unlocked.
A more complex issue is how to protect the model. Although the refresh functions
localize hardware access, the model tends to be updated from several places, which can
lead to a lot of locking and unlocking of resources. There is a small performance pen-
alty here, but a much bigger cost is the increased complexity of the code. The only way
to avoid the locks is to make each task own a portion of the model, and to make sure no
task needs to access the model belonging to the others. This is not always practical.
Once several locks are used, the biggest danger is that the locks dictate that the
tasks spend most of their time waiting for each other. When this happens, any
improved response time for the short events is lost because the short event must wait
for the longer event to complete and release its locks. In this case, the whole purpose
of sharing the user interface over a number of tasks is defeated.
Before allowing a number of tasks to access the model and the user interface hard-
ware, analyze the interactions to see if parallelism is really needed. In the bar graph
example, will the user notice a slight pause in the graph’s movement if he is concen-
trating on the response to the key he just pressed? If some of your events take more
than a second to execute, examine the work they are doing and decide if some portion
of it is unrelated to the user interface and could be spawned off to another task. The
next section studies an example of this.

3.5.3 Breaking Up Long Events into Shorter Events

Suppose the user presses a button that starts a motor. I want to tell the user that the
motor is running by lighting a LED. I want to provide the feedback only when the
motor is running at a constant speed, and it takes a couple of seconds to reach that
speed. The code that handles the key press could issue the commands to the motor and
 Scheduling and Managing User Events — 41

monitor the motor speed until it is stable. The user interface is now paralyzed for
those few seconds while the motor accelerates because the mvc task cannot read the
queue while it is monitoring the motor speed.
A reasonable solution is to pass the responsibility for controlling the motor to
another task. The mvc task now makes the request to start the motor and then reverts to
processing the next user event. The response to the key event may also include a key
click or some other feedback so that the user knows that the key press was detected.
The mvc task still has the responsibility for lighting a LED once the motor has reached
its stable speed. This can be achieved via a second event that is queued from the
motor-controlling task to the mvc task. Figure 3.6 shows the path of the event. In
between item 2 and item 3, it is possible that the mvc task processed other events from
the queue. The choice to use one queue to carry the key events and the motor-controller
events was arbitrary; two queues could have been used, with the mvc task reading both.
Breaking up the processing of starting the motor this way means that the mvc task
has two short jobs to process instead of one long one. In general, the user interface
software is more responsive if it has many small events to handle rather than fewer
large events.

3.5.4 A Task with a View

Another approach to the problem of allowing several tasks access to the display is to
dedicate a single task to the view and the physical output layer. If there is a single

Figure 3.6 Message sequence for slow event broken up

into two events.

keyPoll 1

3 mvc

Motor
2
Controller

1. The key event is passed to the mvc task.

2. The start motor request is passed to the motor controller.
3. The motor controller informs the mvc task that the motor has reached a stable speed.
42 — Front Panel: Designing Software for Embedded User Interfaces

queue to this task, any other task in the system can make a request to it. The overhead
of placing the requests on a queue may prove comparable to the overhead of locking
resources, and the design that evolves is a good deal easier to maintain.
Figure 3.7 shows this architecture. The monitor could now hold the model data for
the alarms and instruct the view to display them directly. The request on the queue to
the view would indicate which alarm to illuminate.
The model for the settings does not move, however, and still lives in the
model/controller task. This could be seen as dividing the model into two portions, or it
could be seen as two separate models. Even though some of the model resides in the
monitor task, there is no need for any controller logic because none of the user events
affect the alarm display.
The protocol to the view allows any elements on the display to be activated. The
view task sees the LEDs simply as three LEDs and may not know about their relation-
ship to the temperature, pressure, and flow settings. When the controller decides to
display the temperature, the request to the view is to display the number 78. The view
is not aware of the meaning of the number, and it cannot distinguish one type of set-
ting from another. All the logic that allows settings to be manipulated is still in the
model/controller task.
The view task is a convenient place to manage any timed activity that is purely
visual, with no interaction with the model data, such as flashing LEDs. The view task
would wait on its queue of requests, as well as wait on a timer that indicates when the
state of the flashing elements should be toggled.

Figure 3.7 Separating the view task from the model.

Monitor Display Queue

Physical Output
+Model of View
Layer
Alarms

User Event Queue

Model
Controller
of Settings
Physical Input Layer
(KeyPoll task)

View and physical output layer have spawned off to another task,
which has its own queue.
 Scheduling and Managing User Events — 43

Another possible use for the view task is multiplexing LEDs to reduce the number
of control lines necessary (Labrosse, 1995). LEDs are often multiplexed in hardware
by a dedicated LED controller chip, but multiplexing can also be performed in soft-
ware to reduce the system hardware cost. The view task is a good place to manage
this operation.
A queued protocol is trivial to convert to a protocol that can pass over a network or
serial link. Now that I have separated the view, I have opened up the possibility of
maintaining the model on a separate processor. This can be an attractive option for
graphics systems in which the rendering of lines and arcs can be CPU intensive. One
processor can be dedicated to managing the display, while all the application-specific
control is performed on a separate processor. In such an architecture, the requests on
the queue are at the level of requesting a line to be drawn between certain points, or an
arc to be drawn with a given radius.

3.6 Different Queues for Different Events

As an alternative to the QPacket structure shown previously, each of the three types of
data could be put on its own queue. This allows each queue to contain simpler struc-
tures. If you choose this route, there are several dangers. The RTOS you use may not
give you a convenient way to block on multiple queues. If this is the case, it will be
necessary to poll each queue in turn, adding to the delay between an event occurring
and the event being processed.
Also, you must watch out for any dependencies between the order of events on one
queue and another. Whether a key was pressed just before or after an alarm was
annunciated may matter if the key’s function is to disable or silence the alarm. A desk-
top example would be a mouse and a keyboard. If the mouse and keyboard events are
handled on different queues and if both queues contain some elements when the task
comes to read them, then there is no way of knowing which occurred first, the mouse
event or the typing. If the typing is directed at the window containing the mouse, the
typing may occasionally appear in the wrong window if the user works quickly.

If the order of events of differing types is related, keep them in the same
queue.

Even if you have several queues, each one is not restricted to one writer. Many
tasks can write to a queue, and one task can write to many queues. On the reading
side, the relationship is not so flexible. Even if your RTOS allows it, more than one
reader of a queue is bad practice — events that pass through the queue may go to one
of a number of tasks. The writer would not be sure which task received the packets.
44 — Front Panel: Designing Software for Embedded User Interfaces

Depending on the priorities of the tasks, one task may consume all the events and the
others may get none. By giving each its own queue, this sharing of events can be more
easily controlled. Figure 3.8 illustrates these configurations.

3.7 Queue Read-Ahead

Events from a motion detection device, such as a mouse, tend to occur in bursts. For
example, if the mouse moves quickly from one side of the screen to the other, four or
five events may appear in the queue before being processed. More typical motion
devices in embedded systems are trackballs, dials, mechanical sliders, and
thumb-wheels. These devices produce responses that can lead to the system response
lagging behind the user’s input. After the user finishes moving the control device, out-
put continues to change until all events on the queue are processed. In order to reduce
this lag, the reading task may look ahead on the queue to combine several events
before processing them.
When a mouse event is popped off the queue, the next event on the queue is exam-
ined. If it is a mouse event, it is popped. The change in position for both events is
combined by adding changes in the X direction and the Y direction. This effectively is
vector addition. It is even simpler if the device, such as a dial, has only one dimen-
sion. When two events are combined, the queue checks again to see if the next event is
of the same type and another merge can take place. Once the queue is empty or the
next event is of a different type, the combined events are processed as a single event.

Figure 3.8 Only one reader per queue allowed.

Two writers,
one reader – OK. One writer,
two queues – OK.

One queue,
two readers – not OK.
 Scheduling and Managing User Events — 45

With this technique, many intermediate steps may be skipped. If the processor is
fast enough to keep up with the events, there will never be more than one event in the
queue and no events combined. As the processor falls further behind, the queue grows
longer and more events are combined on each pass. If the user moves the mouse
quickly, he will see the mouse redrawn only in a few positions. If the mouse is moved
more slowly, it is redrawn at each intermediate step. This behavior should be more
acceptable to the user than allowing the mouse displayed on the screen to lag the
movement of the user’s hand. Similarly, if a dial updates a numeric display, then the
faster the user turns the dial, the larger the numeric value change each time the display
is updated.
Take care if the intermediate values are recorded. Consider a drawing tool that lets
the user draw a freehand curve with a mouse or other pointer. A line is drawn that
joins all the points on the screen visited by the mouse. The optimization just described
might result in fewer longer lines between the points as a result of the merge, rather
than a greater number of short lines.
In order to implement this technique, it has to be possible to look at the top ele-
ment of the queue without removing it. This allows the main event-handling loop to
pop the element later if it is an event of a different type. Some RTOSs allow the pro-
gram to examine the top element of the queue without removing it. If yours does not,
you can add this functionality by adding a layer above the RTOS-supplied queues.
This layer pops an element and stores it when a read is requested. If the element is
subsequently popped, it returns the stored element as the top of the queue. This code
does not need to be made reentrant because it would be called only from the task that
is reading the queue, and as I have already discussed, there should be only one reader.

3.8 Directing Event Traffic

Once an event is popped off the queue, the controller must decide what the event
really means in the current context. Some events have a single purpose. Other events,
such as the UP and DOWN keys in the temperature/pressure/flow example, perform
different actions depending on the context. To discuss this issue in detail, I will first
examine more code from the example. I will use the architecture in Figure 3.4, in
which the model, controller, view, and physical output layer all live in the one task.
The model data is stored in the following data structures.

typedef struct {
int temperature;
int pressure;
int flow;
} Settings;
46 — Front Panel: Designing Software for Embedded User Interfaces

static Settings GS_settings;

typedef struct {
Boolean highTemperature;
Boolean highPressure;
} Alarms;
static Alarms GS_alarms;

The alarms are updated simply by the handleAlarm() function, which is called from
the infinite loop of the mvc task, and which you have already seen.

void handleAlarm(AlarmStruct *alarmPtr)

{
switch (alarmPtr->type)
{
case HIGH_TEMPERATURE:
/* Turn alarm on or off as appropriate */
GS_alarms.highTemperature = alarmPtr->value;
break;
case HIGH_PRESSURE:
/* Turn alarm on or off as appropriate */
GS_alarms.highPressure = alarmPtr->value;
break;
default:
assert(FALSE);
}
}

This function makes simple changes to the model, which are then copied to the view
by the refreshAlarms() function. In the DOS example, this function prints the
strings on the screen. A real embedded system may turn lights on instead.

void refreshAlarms(void)
{
if (GS_alarms.highTemperature)
{
gotoxy(40,15);
puts(" HIGH TEMPERATURE");
}

else
{
/* Clear the alarm if it was displayed */
gotoxy(40,15);
puts(" ");
}
 Scheduling and Managing User Events — 47

if (GS_alarms.highPressure)
{
gotoxy(40,17);
puts(" HIGH PRESSURE");
}
else
{
/* Clear the alarm if it was displayed */
gotoxy(40,17);
puts(" ");
}
}

3.8.1 The Focus

Manipulation of the model for temperature, pressure, and flow settings is not so sim-
ple. Pressing the key associated with one of these settings causes it to be displayed.
You must keep track of the one that is displayed, which is called the focus. The con-
cept of focus is well established on desktop user interfaces where the keyboard focus
is on a particular window depending on the mouse position. A focus is useful when
some piece of hardware can be directed to control a number of different data items.
Such a multiplexed control uses the focus to decide which of the data items to control.
Changing the focus redirects the events generated by the multiplexed control or
changes the interpretation of those events. In this example, the value of the focus is
stored in GS_focusValuePtr.

/*
The GS_focusValuePtr points to the value in the model that is being
modified.
*/
static int *GS_focusValuePtr = NULL;

When a key event for one of the settings occurs, the focus is adjusted by setting
GS_focusValuePtr to point at one of the three values in GS_settings. If the key is
an arrow key, the value in the model is adjusted via the pointer.

void handleKey(KeyValue key)

{
switch (key)
{
case TEMP_KEY:
GS_focusValuePtr = &GS_settings.temperature;
break;
48 — Front Panel: Designing Software for Embedded User Interfaces

case PRES_KEY:
GS_focusValuePtr = &GS_settings.pressure;
break;
case FLOW_KEY:
GS_focusValuePtr = &GS_settings.flow;
break;
case UP_KEY:
/* Increment the focus value if there is one */
if (GS_focusValuePtr != NULL)
{
(*GS_focusValuePtr) ++;
if ((*GS_focusValuePtr) > 100)
{
*GS_focusValuePtr = 100;
}
}
break;
case DOWN_KEY:
/* Decrement the focus value */
if (GS_focusValuePtr != NULL)
{
(*GS_focusValuePtr) --;
if ((*GS_focusValuePtr) < 0)
{
*GS_focusValuePtr = 0;
}
}
break;
default:
assert(FALSE);
}
}

This mechanism of using a focus is implemented with a pointer to the integer to be

changed. A more realistic case would use a pointer to a structure, and this structure
would contain information such as maximum and minimum limits to restrict the
amount of change the user can make to the value.
A slightly different implementation is needed if the data is of different types, say,
an integer and a floating-point number or a sequence of strings used in a text menu.
However, the same principle can be applied by using an enumerated type to identify
one of several types of update that can be performed. In some cases, the data structure
that represents the view, rather than the model, can be used. In C++, the focus is often
represented by a pointer to an object.
Figure 3.9 shows that the focus of the arrow keys has a choice among the three
settings available.

A focus is most useful when a piece of input hardware is shared among

several parts of the model.
 Scheduling and Managing User Events — 49

3.8.2 Callbacks
A callback is a function called in response to an event. Its name stems from a module,
object, or subsystem wanting to say: “If event X happens, then call me back.” The
function to be called is then recorded in some way so that it can be invoked when X
occurs. If either the number of focuses or the number of enumerated values used by
the focus are large, it can become difficult to manage and callbacks may be a good
alternative. If the choice is among several actions rather than among several pieces of
data, you should consider applying callbacks.
This mechanism matches the requirements of buttons well. Each button is associ-
ated with a callback function; that is, the action to be performed when the button is
pressed. In the handleKey() function already discussed, a switch statement is used
to distinguish among the buttons. Unfortunately, the switch statement is static; it can-
not be changed at run time. To examine how callbacks can be used on a device in
which the buttons change meanings, I will use the example of a simple digital watch.
This digital watch in Figure 3.10 has three buttons. It has two modes: time-of-day
mode and stopwatch mode. Depending on the mode, the buttons change meaning. In
typical digital watch style, I have written each of the meanings on each of the buttons,
and the user has to figure out on the fly which one applies. Most digital watches use a
small icon in the LCD to distinguish modes. Because I wrote this example in text
mode in DOS, the mode is displayed as an explicit string below the watch face. Note
also that the time of day can be adjusted in the normal time-of-day mode. There is no
special mode for updating the current time such as you would find on most real digital
watches. Those simplifications aside, this is a suitable case for callbacks because the
buttons change their associated actions depending on the mode and on whether the
stopwatch is running. This watch displays hours and minutes in time-of-day mode and
minutes and seconds in stopwatch mode.

Figure 3.9 The focus of the arrow keys can be directed

at any one of the three settings.

Temperature

Pressure

Flow
50 — Front Panel: Designing Software for Embedded User Interfaces

If each button has a function associated with it and those functions are stored in an
array of function pointers, then you can change them at run time to alter the behavior
of the buttons. The following definitions allow us to use such an array.

typedef enum { BOTTOM_LEFT_KEY, TOP_RIGHT_KEY,

BOTTOM_RIGHT_KEY, NO_KEY} KeyValue;

#define NUMBER_OF_KEYS 3

typedef void (*CallbackFn)(void);

/*
This is the array that will hold the callback for each key
*/
static CallbackFn GS_keyCallbacks[NUMBER_OF_KEYS];

The keys are polled in the same fashion as the previous example, but the packets
on the queue are a little simpler because there are no alarms to pass. The timeout mes-
sage is replaced with a one-second timer used to drive the ticking of the watch. The
new packet is as follows.

Figure 3.10 The watch example.

Up-Reset
12:00
Mode Down-Start/Stop

Mode = Time-Of-Day

The left-hand button changes between time-of-day mode and stop-watch mode.
The two buttons on the right have different meanings, depending on the mode.
In stop-watch mode, the lower-right button can mean start or stop,
depending on whether the stop-watch is running.
 Scheduling and Managing User Events — 51

typedef enum { KEY_PACKET, ONE_SECOND_TIMER_PACKET } PacketType;

/*
This packet does not require a union because there is only
one packet with an associated value.
*/
typedef struct {
PacketType type;
KeyValue keyValue;
} QPacket;

The data being manipulated is the time of day and the current time on the stopwatch.
Whether the time of day or the current stopwatch time is displayed is in the domain of
the view.

/* Model Data */
typedef struct {
int hrs;
int mins;
int secs;
} TimeOfDay;
typedef struct {
Boolean running;
int mins;
int secs;
} StopWatchTimer;
static TimeOfDay GS_timeOfDay;
static StopWatchTimer GS_stopWatch;
/* View Data */
typedef enum { TIME_OF_DAY_MODE, STOP_WATCH_MODE } DisplayMode;
static DisplayMode GS_displayMode = TIME_OF_DAY_MODE;

Even though the seconds of the time of day are stored, they are not displayed on the
watch face.
Now that the data structures are in place, I can initialize the callbacks as follows.

GS_keyCallbacks[BOTTOM_LEFT_KEY] = setModeToStopWatch;
GS_keyCallbacks[TOP_RIGHT_KEY] = incrementTimeOfDay;
GS_keyCallbacks[BOTTOM_RIGHT_KEY] = decrementTimeOfDay;

The entries in the array are assigned to functions that I will now define. The two
mode-change functions, setModeToTimeOfDay() and setModeToStopWatch(), rede-
fine the buttons on the right-hand side of the digital watch to functions appropriate to
the new mode. The bottom-right button also changes roles, depending on whether the
stopwatch is running.
52 — Front Panel: Designing Software for Embedded User Interfaces

void setModeToTimeOfDay(void)
{
GS_keyCallbacks[BOTTOM_LEFT_KEY] = setModeToStopWatch;
GS_keyCallbacks[TOP_RIGHT_KEY] = incrementTimeOfDay;
GS_keyCallbacks[BOTTOM_RIGHT_KEY] = decrementTimeOfDay;
GS_displayMode = TIME_OF_DAY_MODE;
}
void setModeToStopWatch(void)
{
GS_keyCallbacks[BOTTOM_LEFT_KEY] = setModeToTimeOfDay;
/*
Bottom left means start or stop depending on whether we are running.
*/
if (GS_stopWatch.running == TRUE)
{
GS_keyCallbacks[BOTTOM_RIGHT_KEY] = stopStopWatch;
}
else
{
GS_keyCallbacks[BOTTOM_RIGHT_KEY] = startStopWatch;
}

GS_keyCallbacks[TOP_RIGHT_KEY] = resetStopWatch;

GS_displayMode = STOP_WATCH_MODE;
}

The following two functions perform the tasks associated with the two right-hand but-
tons while in time-of-day mode.

void incrementTimeOfDay(void)
{
GS_timeOfDay.mins ++;
if ( GS_timeOfDay.mins == 60 )
{
GS_timeOfDay.mins = 0;
GS_timeOfDay.hrs ++;
if ( GS_timeOfDay.hrs == 24 )
{
GS_timeOfDay.hrs = 0;
}
}
}
 Scheduling and Managing User Events — 53

void decrementTimeOfDay(void)
{
GS_timeOfDay.mins --;
if ( GS_timeOfDay.mins == -1 )
{
GS_timeOfDay.mins = 59;
GS_timeOfDay.hrs --;
if ( GS_timeOfDay.hrs == -1 )
{
GS_timeOfDay.hrs = 23;
}
}
}

The three stopwatch functions are associated with the two right-hand buttons while
in stopwatch mode. The bottom-right button is associated with startStopWatch() or
stopStopWatch(), depending on whether the stopwatch is running.

void startStopWatch(void)
{
GS_stopWatch.running = TRUE;
GS_keyCallbacks[BOTTOM_RIGHT_KEY] = stopStopWatch;
}

void stopStopWatch(void)
{
GS_stopWatch.running = FALSE;
GS_keyCallbacks[BOTTOM_RIGHT_KEY] = startStopWatch;
}
void resetStopWatch(void)
{
GS_stopWatch.mins = 0;
GS_stopWatch.secs = 0;
}

The infinite loop of the mvc task is of the same form as the temperature/pres-
sure/flow example, but the handleKey() function has changed dramatically. Instead
of having a large switch statement to handle all possibilities, it now has only to acti-
vate the appropriate callback.

void handleKey(KeyValue key)

{
GS_keyCallbacks[key]();
}
54 — Front Panel: Designing Software for Embedded User Interfaces

This function is simple because all buttons use callbacks. In some cases, you may
use a mixture involving a switch statement to cover the keys or events whose mean-
ings never change and the callback mechanism for the remainder.
The remainder of the code for this example manages the timing for the seconds
ticking by and for refreshing the display, neither of which relates to the callback
mechanism directly, so I will not investigate it further. You will see more of the call-
back mechanism when you look at the code for buttons on graphical displays.
One word of caution about using callbacks: They make the flow of control harder
to predict by reading the code. In the example just given, any meaning could be attrib-
uted to a button at run time, and there is no way in C to limit that flexibility. Program-
mers who use Smalltalk see this as a natural form of message passing. However, it
makes tracking defects difficult. If you have a set of callback functions for mechanical
buttons and a completely different set of callback functions for graphical buttons, you
may want to guarantee a compiler warning if you assign a callback of one type when
a different one is expected. This is possible if you give the two types of callback dif-
ferent signatures, as in the following example.

typedef void (*GraphicalCallbackFn)(void);

static GraphicalCallbackFn GS_graphCallbacks[NUM_GRAPH_BUTTONS];
typedef void (*MechanicalCallbackFn)(int mechanicalButtonIndex);
/*
This is the array that will hold the callback for each
mechanical button
*/
static MechanicalCallbackFn GS_mechCallbacks[NUM_MECH_BUTTONS];
void someMechanicalCallbackFunction(int mechanicalButtonIndex);
void someGraphicalCallbackFunction(void);
void setCallback(void)
{
/* This line is OK */
GS_mechCallbacks[0] = someMechanicalCallbackFunction;
/* This will generate a compiler warning */
GS_mechCallbacks[0] = someGraphicalCallbackFunction;
}

The second line of the function generates a warning because the assignment is
expecting a function that takes an integer as an argument. This does not save you from
assigning one of the mechanical button callbacks to the wrong button, but at least it
avoids some more obvious errors. In Chapter 7 when I discuss C++, you will see call-
back mechanisms that are much safer.
 Chapter 4

Finite-State Machines and

Table-Driven Software
Finite-state machines (FSMs) are frequently used as tools for modeling many systems
and provide a means of controlling the flow of a program. They are also easy to repre-
sent in diagram form, which has obvious advantages during design and documenta-
tion phases.
FSMs are a special case of table-driven code. Table-driven code controls the flow
of events using data structures to dictate the order of function calls rather than using
explicit calls within a function. It would not make sense to structure all of your code
in this way, but in a few areas it can be very effective.

4.1 The FSM as a Poor Man’s Real-Time

Operating System
The FSMs described in this chapter are not used to schedule pseudo-parallel threads
of execution. In simple embedded systems, you may use an FSM to manage the flow
of control in order to allocate CPU cycles between a set of logically distinct threads of
control. While in a given state, the function associated with that state is executed and
that function has control of the processor until it returns. On completion of the func-
tion associated with one state, the state machine progresses to the next state and runs

55
56 — Front Panel: Designing Software for Embedded User Interfaces

the function associated with this new state. This loop continues with each state, giving
each function a chance to run. Such an implementation is a poor man’s RTOS. Using
an FSM in such a way works on small systems but does not scale well, and it makes it
difficult to implement any sort of priority scheme. FSMs are completely unsuitable if
some of the threads of control have hard real-time deadlines and others do not. In such
a scenario, an RTOS is required. I describe this type of FSM to distinguish it from the
FSMs I am concerned with in this chapter. The FSMs implemented here are used
purely to manage the sequence of inputs from the user and have no effect on schedul-
ing CPU time.

4.2 Drawing the FSM

An FSM consists of a set of states and a set of transitions between those states. In
any given state, there are a set of legal input values. Each value causes one transition
to occur.
The simple example in Figure 4.1 shows the three possible states of a door. The
door may be Open, Closed, or Locked. In order to Lock the door, it must be Closed.
When the door is unlocked from the Locked state, it becomes Closed again. There are
no transitions from the Open state to the Locked state. This means that no single input
could cause this transition. If the door is Open and the input Lock is applied, no transi-
tion occurs. This input is considered illegal. As the machine’s implementor, it is up to
you to decide if illegal actions are ignored, flagged to the user as an error, or cause the
program to halt. The source of the input will affect your decision. Sometimes, the
input is the keys the user pressed, in which case, an illegal transition simply means
that the user pressed a key with no associated action. In other cases, the input is fil-
tered before it reaches the FSM, and an illegal input may represent a bug in the filter.

Figure 4.1 The three states for a door.

input = Lock
input = Close
Open Closed Locked

input = Unlock
 Finite-State Machines and Table-Driven Software — 57

You should always be aware of how visible the FSMs are to the user. Some FSMs
are used to manage processes of which the user is not aware. In other cases, I want the
current state of a machine, or machines, to be visible to the user. For example, the ele-
ment currently highlighted in a menu represents a certain state. Sometimes, the state
itself is not visible, but the transitions are visible to the user. Each transition may be
associated with an action function, and that function may interact with the user, mak-
ing the user aware that a transition took place.
I will repeat the door example here with a slightly different syntax to show a func-
tion call associated with each input. Let us assume that the door FSM must generate
the appropriate noises when the user makes a change. Those noises are generated by
the functions Slam() and Click(). Figure 4.2 shows this slightly more capable FSM.
For the purists, an FSM that has an action associated with each transition is a
Mealy FSM. Alternatively, you may associate the actions with each state. Such an
FSM is called a Moore FSM (Hendricksen, 1989). I will not discuss the Moore FSM
variety further.

4.3 Why User Interface Code Needs FSMs

In a user interface, the use of FSMs is more common than in many other areas of pro-
gramming. One reason for this is that the FSM is used to store state across numerous
events, or inputs. The current state gives a context to the next input. This context dic-
tates the meaning of the input. In many cases, the response to a user input depends on
the history of previous inputs. In other cases, the response depends on the history of
previous inputs to a particular area of the interface but is completely independent of
inputs to other areas. A filter on all the inputs can decide which inputs drive each FSM.

Figure 4.2 A door with associated functions.

Lock/Click()
Close/Slam()
Open Closed Locked

Unlock/Click()
58 — Front Panel: Designing Software for Embedded User Interfaces

Much of the time, the user is aware of this state information. He realizes that
pressing the Quit button while in a submenu has a different effect than pressing the
Quit button while at the top-level menu.

4.3.1 States and Modes in the User Model

Where separate states represent separate modes of operation, it is important that the
mode be apparent to the user. On a word processor, any time I find myself typing in
over-type mode when I thought I was in insert mode, I curse the fact that I did not spot
the mode I was using. (Modes have a bad reputation and are considered contributors
to unusable interfaces. It is more often because the mode is not visible or obvious to
the user rather than the mode itself that causes the difficulty.) Consider a drawing tool
in which the modes are Draw_Line, Draw_Box, and Draw_Arc. If the user cannot tell
the mode from the appearance of the interface, he may drag the mouse and only then
realize he is drawing a box when he intended to draw a line. The user is forced to
undo the action just performed and then change to the correct mode. If the cursor is in
the shape of a small box, however, the user is unlikely to make that mistake. This is an
example of making the FSM (with transitions between the Draw_Line, Draw_Box, and
Draw_Arc states) more visible to make navigation easier for the user.
It may be tempting to use an FSM to implement an Undo facility. This is not as
simple as it seems. If an Undo key retraces the last transition performed, there should
also be a transition function that can reverse the effect of the last transition. It is also
important to check if the event could have been interpreted on a different level than
the level at which the FSM has been implemented. As long as this warning has been
observed, it can be useful to record every state visited in order to provide a multistep
Undo feature.

4.4 Limits of the FSM

An FSM has no memory apart from the current state. A decision can be made based on
the current state, because there is a different transition for each of the possible last
states. However, it is not possible to make a decision based on the last time this state
was visited. If you want to build a machine that allows the program to visit each state
once, at most, data would have to be maintained outside the FSM to record the states
that have been visited. More powerful machines can be built at a cost. You may add
new rules to the machine, such as a valid/invalid flag that can be toggled for each state.
Depending on actions outside the machine, some states can change their behavior.
This may be useful. However, once you go beyond the basic elements, the machine is
more difficult to represent in a simple diagram that other engineers can understand. If
the FSM has been enhanced, the reader will have to learn those enhancements before
he can understand the diagrammatic representation. For FSMs that are visible to the
 Finite-State Machines and Table-Driven Software — 59

user, this is an important trade-off, because the state diagram can often be used to doc-
ument the behavior of the interface. Unfortunately, many real-world programs have
characteristics that are too complex to model with a simple FSM. More complex
mechanisms must be used. The menu example later in this chapter shows such a system.

4.5 How Many States? How Many FSMs?

Having several states per interface allows the limited number of inputs available to the
user more meanings than would be otherwise possible. Each input can have a different
meaning in each state, allowing the number of meanings to be the number of possible
inputs multiplied by the number of states. The maximum number of possibilities, how-
ever, are rarely used. These meanings, in FSM terminology, are transitions.
Do not assume that the interface should be seen as one large FSM. It is often
more useful from the user’s and programmer’s point of view to model the interface
as a collection of FSMs. One FSM may model the possible states of a button (which
is not as simple as you might think). Several instances of that FSM are required if
there are many buttons. Another FSM may model the different states of the whole
system: Booting, Running, and Self_Test_Mode. There would be only one such
FSM per system.
Attempting to combine many FSMs into one has some attractions. The specifica-
tion of the interface could be represented in one large diagram. Testing could be per-
formed according to how many states have been visited, and one of the test completion
goals would be that all states must have been reached during the test process.
Unfortunately, the disadvantages far outweigh the advantages. One large FSM
that combines all possible states for an interface would have more states than the
sum of the smaller FSMs. Consider two FSMs; call them A and B. The number of
states in an FSM that combines all the possibilities is the product of the number of
states in A and the number of states in B. Not only have the number of states
increased, but the meaning of each state has grown more complex. When the FSMs
are decomposed, there may be a state that represents Menu_Is_Selected and another
state in the other FSM that represents Key_Is_Depressed. In the combined FSM,
there is a state called Menu_Is_Selected_And_Key_Is_Depressed.
Although few programmers might attempt to combine an entire complex inter-
face into one FSM, it is tempting to combine related FSMs. If you have a large and
complex FSM, consider decomposing it into several simpler FSMs. If you have sev-
eral small FSMs that depend on each other’s behavior, you may have a candidate for
combining them into one.
60 — Front Panel: Designing Software for Embedded User Interfaces

4.6 Use of Constant, Static, Global, and

Automatic Data
Two types of information must be stored to implement an FSM: the table itself, which
is information that does not change, and the current state, which changes throughout
the life of the program. There may be many copies of the current state if there are
many instances of the FSM in use within the program.
The table that represents the states and transitions is declared const. The const
declaration instructs the compiler to place the table in the code segment and may,
therefore, be placed in ROM.
Much of the state information must be maintained between events. After an event
is handled, the program and the stack return to the point where they read the event
queue for the next input. All the functions that have been called to handle the event
have returned and unwound the stack by the time the next event can be handled. The
state, therefore, has to be held in data structures that are not automatic variables of
any of those functions. Note that automatic means local variables that are on the
stack. Local variables can also be constant, in which case they can be accessed from
within the function but not changed, or they can be static, in which case they can be
accessed from within the function, but they hold their value between invocations. The
value is, therefore, not stored on the stack.
This allows two options for storing the current state. It may be stored as a static
variable. The variable has a life that begins when the program starts running and con-
tinues until the program terminates. These variables may have local function scope,
file scope, or global scope. Alternatively, the space may be allocated dynamically on
the heap by malloc().

4.7 Example of an FSM for a Toggle Button

on a GUI
This example implements a toggle-button on a graphical interface. The button latches
itself Down when pressed once. If the user presses it again, it latches itself Up. The text
visible in the button describes the attribute being toggled. For example, the word
“Silence” may indicate that while in the Down state, this button is silencing some
speaker or alarm buzzer. This example was devised for a touch screen, so I assume
that the user presses the graphically depicted button with his finger, although he could
as easily be using a mouse to select it. An FSM could also control a mechanical button
with an associated LED that reflects its state.
 Finite-State Machines and Table-Driven Software — 61

4.7.1 The Four States: Up, Down, Pending_Up, and

Pending_Down
Although the user is aware of the Up and Down states, he is less conscious of the state
of the button while his finger is on it. These states are necessary because it is possible
for the finger to slide off to one side without completing the operation. The rule for the
button is that the finger must be removed from the screen while the button is selected
to complete the operation. This avoids accidentally selecting two neighboring buttons
in a single operation. After an aborted selection, the button must know what state it
should revert to. If you did not have the intermediate states, the state would change
from Up to Down when the finger pressed on it. It would revert to the Up state if the user
slid his finger off the button. This would turn the toggle on and then off, which may
not leave the system in the same state as not turning it on at all. So, if the user slides
his finger off before a release, you will treat this as not selecting the button.
The transition diagram in Figure 4.3 shows the possible states and the transitions
between them. The doNothing() function acts as its title suggests. Such functions are
useful when there are slots in the transition table that you prefer to leave empty. Hav-
ing an empty function avoids having to check if the function pointer is null each time
the transition occurs.

Figure 4.3 The four states of a button.

Button

Up
Pr
es
) s/d
e( oN
at ot
iv
act hi
ng
Button e
e/d Sl ()
as id
le eO
Re ff
/do
No
th
in
g(
Pending_Up ) Pending_Down
Pr
es
s/d
oN
ot
hi ()
ng te
() va
Sl
id cti Button
eO e /a
ff as
/do le
No Re
th
in
g(
) Down

Button
62 — Front Panel: Designing Software for Embedded User Interfaces

The button images are shown next to each state. Drawing the image could be per-
formed by copying prestored bitmaps. In the example code, the image is drawn by
constructing a number of lines, rectangles, and polygons. The drawing method is not
relevant to the code to manage the FSM. The button’s appearance reflects the state, so
it is straightforward for the user to see each state. The 3-D effect is useful to distin-
guish touch-sensitive buttons from other labels on the screen that are not touch-sensi-
tive. At this point, I suggest that you run the fsm program supplied on the companion
disk. It allows you to view the button in each of the described states by selecting it
with the mouse.
The possible inputs are Press, SlideOff, and Release. SlideOff occurs when
the user moves his finger out of the area of this button. Whether he enters the area of
another button is immaterial to this FSM, because this FSM is concerned with only
one button, not with the entire set of buttons on the screen.
These inputs cannot be read directly. As each finger position is read from the dis-
play, it is parsed, or filtered, to detect any higher level events it represents. The button
object may have functionality apart from the FSM that indicates whether the button
area contains the point selected by the finger. A function can then process each posi-
tion, establish exactly which buttons are affected by the latest event, and generate the
appropriate inputs. Such processing, although interesting, is not the subject of this
chapter; see Chapter 5 for further details.
By happy coincidence, this button works nicely if you treat a finger sliding into
the area of the button exactly the same as a Press. This avoids having to create
another input value. If the user slides his finger over the display, entering and leaving
several Up buttons, the only one that transitions into the Down state is the one in the
Pending_Down state when the finger is lifted from the screen.

4.7.2 The Interaction Between the FSMs

In the example, each instance of a Button contains an instance of ButtonState,
which is all the information you need to store to have a unique FSM. Each individual
FSM obeys the same transition rules. However, the state of one FSM has no influence
on the state of any other.
In the example, the transitions are stored as const data. Thus, they cannot be
altered while running. If the FSM did change at run time, it would not be possible to
share the transition table among many instances of the FSM, because changes to the
table that implements the FSM would influence all instances.
Many of the type names in the example restrict the function ButtonProcessFSM()
to handle only buttons. The basic algorithm could be implemented in a more general
way and then used for all FSMs in your system. If data, such as a pointer to the Button
structure, needs to be passed, it can be passed as a void pointer. All the enumerated
values would be passed in as integers. This involves casting, which is less type-safe. In
return, you can reuse the same function. Despite the code reuse, I do not usually create
 Finite-State Machines and Table-Driven Software — 63

a more general FSM-processing function. Most real-world cases involve some excep-
tions. For example, you may wish to change the rules that decide when transitions are
legal. One enhancement is allowing the action function to return a Boolean value and
allowing the transition only if the action function returns TRUE. In other cases, you may
wish to transition to a certain state if an illegal input is received.
If there are many transitions, you may want to sort them and allow a binary search
for the matching input, or you may wish to sort them according to frequency of use, to
allow the most frequent transitions to be found soonest in a linear search.
Amid all the special-case processing, the few lines of code that actually call the
action function and change the state represent a small percentage, so the code reuse
advantage is minor.

4.7.3 The Implementation

Each transition is represented by a constant instance of the ButtonTransition struc-
ture. The structure is shown here, along with a set of type definitions required to
define the transition.

typedef enum {NullInput=0, Press, Release, SlideOff} ButtonInput;

typedef enum { UP, PENDING_DOWN, DOWN, PENDING_UP } ButtonState;
#define NUMBER_OF_STATES 4
/*
This typedef defines a pointer to an action function.
The arguments pass all of the information associated with this
transition in case the action function based on that information.
*/
typedef void (*ButtonFunction)(Button *buttonPtr, ButtonInput input,
ButtonState nextState);
/*
The transition consists of the input, the next state, and
the action function.
*/
typedef struct {
ButtonInput input;
ButtonState nextState;
ButtonFunction transitionFn;
}ButtonTransition;

Each state has a list of such transitions. Each transition is checked for an input match-
ing the user input. When a match is found, transitionFn is called and the state is
assigned to nextState.
The following assignments represent the full set of transitions. Note that the final
entry in each array starts with a NullInput value. This is a terminator and the rest of
the last line is not used.
64 — Front Panel: Designing Software for Embedded User Interfaces

const ButtonTransition UPtransitions[] =

{
/* INPUT NEXT STATE ACTION */
{ Press, PENDING_DOWN, doNothing },
{ NullInput, UP, doNothing }
};
const ButtonTransition PENDING_DOWNtransitions[] =
{
/* INPUT NEXT STATE ACTION */
{ Release, DOWN, activate },
{ SlideOff, UP, doNothing },
{ NullInput, UP, doNothing }
};
const ButtonTransition DOWNtransitions[] =
{
/* INPUT NEXT STATE ACTION */
{ Press, PENDING_UP, doNothing },
{ NullInput, UP, doNothing }
};
const ButtonTransition PENDING_UPtransitions[] =
{
/* INPUT NEXT STATE ACTION */
{ Release, UP, deactivate },
{ SlideOff, DOWN, doNothing },
{ NullInput, UP, doNothing }
};
const ButtonTransition *GS_buttonFSM[NUMBER_OF_STATES] =
{
UPtransitions,
PENDING_DOWNtransitions,
DOWNtransitions,
PENDING_UPtransitions
};

The button itself is represented as a structure. Although one FSM can be used by all
buttons, I must create one Button structure for each button.

struct buttonStruct;
typedef struct buttonStruct Button;
struct buttonStruct
{
int x;
int y;
char *text;
ButtonState state;
void (*actionFnDOWN)(Button *buttonPtr);
void (*actionFnUP)(Button *buttonPtr);
};

The state field in this structure represents the current state of this button within the
FSM. The two function pointer fields are used to call particular functions once the
button has reached the Up or the Down states. There is no function for the
 Finite-State Machines and Table-Driven Software — 65

Pending_Down or Pending_Up states, because no permanent transition has taken

place. Note that these two functions will be different for each button, because each
button has a different job to do.
The buttonProcessFSM() function takes an input and applies it to the Button
that is pointed to by the first argument. Note that only the set of transitions associated
with the current state must be checked. Other transitions are ignored.

void buttonProcessFSM(Button * buttonPtr, ButtonInput input)

{
int i;
/*
First loop through the FSM to find the appropriate transition
*/
for (i=0; GS_buttonFSM[buttonPtr->state][i].input != input; i++)
{
if (GS_buttonFSM[buttonPtr->state][i].input == NullInput)
{
/*
The end of the list has been reached and no input
matched the input
*/
assert(FALSE);
}
}
/*
Some transition is going to take place so set flag to indicate
that the buttons need to be redrawn.
*/
GS_changeHappened = TRUE;
/* Now i indexes the appropriate transition */
/* Call the action function, passing the button, the input and
the nextState */
GS_buttonFSM[buttonPtr->state][i].transitionFn(buttonPtr, input,
GS_buttonFSM[buttonPtr->state][i].nextState);
/* Change the state */
buttonPtr->state = GS_buttonFSM[buttonPtr->state][i].nextState;
}

The three transition functions follow. Some transitions perform no action. When the
button is placed in the Down state or the Up state, one of the button actions takes place.
The actionFnDOWN and actionFnUP pointers may point to any function that takes no
arguments and returns void. These are the callbacks for this button. These functions
perform the application-level work in response to the user’s action on the button.
66 — Front Panel: Designing Software for Embedded User Interfaces

void doNothing(Button *buttonPtr, ButtonInput input,

ButtonState nextState)
{
/* This function simply returns */
}
void activate(Button *buttonPtr, ButtonInput input,
ButtonState nextState)
{
buttonPtr->actionFnDOWN(buttonPtr);
}
void deactivate(Button *buttonPtr, ButtonInput input,
ButtonState nextState)
{
buttonPtr->actionFnUP(buttonPtr);
}

Note that two levels of function pointers are traversed here. The first level uses
pointers stored in the FSM table. These are the same for all buttons and represent the
controller communicating with the model. The second level are functions associated
with each button. These may be different for each button, allowing each button to
have different application-level behavior. In the example, the FSM’s action functions
simply call the buttons actionFnUP() or actionFnDOWN(). In a real case, the button’s
activate() and deactivate() functions may sound a key click, change the cursor’s
appearance, or add other properties to the button.

4.7.4 A Model-View-Controller Interpretation of this FSM

This FSM is part of the model data. The controller provides a stream of inputs, having
filtered the finger positions to interpret them as Press, Release, and SlideOff
events. In the demo program, the view is refreshed once the buttonProcessFSM()
has returned. The view reads the state from the model (i.e., the state field of the but-
ton), decides which color to use to display the button, and decides whether to draw the
button in a raised or sunken state.

4.8 Menu for a Small Text Display

This example implements a menu for a small, one-line text display. It demonstrates a
more powerful table than an FSM. The menu hierarchy means that I still have a sim-
ple graphical method of representing the data in the table. There are no hard and fast
rules for which scenarios suit table-driven code and which ones do not. Unlike FSMs,
there is no mathematical background to more general tables. One way of thinking
about them is as a more general form of the switch statement.
 Finite-State Machines and Table-Driven Software — 67

Menus were once a common way to navigate text interfaces on desktop comput-
ers. More modern GUIs allow pull-down menus. These menus often give the user
access to a dialog to complete the request. Before the age of the GUI, menus often led
to submenus, which led to sub-submenus. That’s because tick boxes, radio buttons,
and other visual gizmos used to construct a request on a GUI were not available on
text displays. Many options on a GUI can be shown at the same time, while a hierar-
chical menu must go through questions one at a time.
Despite the disadvantages, a hierarchical menu is still a necessary tool in embed-
ded systems in which the display device may be a one-line text display or a serial link
to a terminal. Even if a full screen is available, the processing ability of the embedded
CPU or the amount of development time may limit the interaction to text rather than
graphics. The inputs available may be a couple of keys rather than the full keyboard
and mouse available on a typical desktop computer.

4.8.1 Human Factor Issues for Menus

The biggest challenge in a menu is to allow the user to say what he wants. The expres-
sive power of a command line has been lost — probably for the better for most novice
users. However, arguments may need to come from a question-and-answer session at
the lowest level of the menu, making the interaction more time consuming. Limited
display space often means that the user cannot see all of his requests at one time. With
small displays, there are cases in which the user can see the current option but not the
name of the parent menu. If the option facing the user is “Halt job,” it is important for
the user to remember if the parent he navigated through is “Printer” or “Download.”
In the implementation presented here, the full path is always visible while navigating.
When this is not the case, careful wording of the menu items can reduce ambiguity.
When you design a menu, there is a trade-off between the width and depth of the
menu. If each level contains many options, the menu may be only a couple of levels
deep. By keeping menus short, you end up with deep menus that are challenging to
navigate. A long list in which the items differ in value but not in kind, such as printer
types, is acceptable. On the other hand, if the menu itemizes different concepts, such
as commands that may be sent to the printer, longer lists are more intimidating.
The magic number seven is often quoted in cognitive psychology texts (Waern,
1989) as the quantity of information chunks that can be retained in short-term memory.
That suggests that menus with more than seven options are harder to use than those with
fewer than seven. By the time the user looks at option eight, option one has dropped into
a less active part of his memory. If keeping the seven rule leads to deeper menus, it is
better to break the rule. Despite the psychology texts, experiments show that few levels
with many alternatives work better than many levels with few alternatives.
68 — Front Panel: Designing Software for Embedded User Interfaces

Long lists cause navigation difficulty in menus, but deep menus cause more
navigation difficulty. Never add depth to reduce width.

A common navigation aid in menus is to number the items in the menu. This lets
the user know how many options he has viewed and whether the menu has wrapped
around. However, the number may be misconstrued as a value. If the user sees “3
Pressure” as the third menu item, there is a possibility that he may assume that the
value of the pressure is 3. The user may not realize that he must go down one level in
the menu to see the actual pressure value.
If you want to be adventurous, you could try inserting earcons (an icon that you
can hear) into your menus (Brewster et al., 1996). A sound made in response to a key
click in the menu may help prompt the user. This could replace the key click. You
would not want a different sound for each menu item, but the sound at a leaf might be
different from the sound on reaching a node. The top-level menu could have a unique
sound to let you know that you cannot go further up the hierarchy.

4.8.2 The Implementation

The menu is table driven, as was the button in the previous example. The main point
here is that, in many cases, adding rules to the table, beyond the basic FSM, allows us
to create a more powerful tool.
The hypothetical product is the latest in high-tech running footwear. There is a
30-character display along the sole of the trainer, and the owner may configure the
footwear using three buttons marked Up, Down, and Scroll. The colors of the sole,
upper, and lace can be changed at run time, if you pardon the pun. The brightness is
set as a number — very useful for joggers who venture out at night. The air pressure
in the sole is also adjustable via a menu option.

[Link] The Model

All the information about the trainer is stored in the following structure. The declara-
tion of one instance of the trainer is shown below.

typedef enum { RED, GREEN, BLUE, BLACK, WHITE, NUM_COLORS } Color;

typedef struct {
int pressure;
int brightness;
Color soleColor;
Color upperColor;
Color laceColor;
} Trainer;
static Trainer GS_trainer = { 1, 5, RED, RED, BLACK };
 Finite-State Machines and Table-Driven Software — 69

The table consists of several nodes that form a tree. The tree analogy allows us to
use the term branches for options at any level and the term leaf for a node with no fur-
ther branches. Each node contains pointers to its parent node, to one child node, and
to one sibling, which is the next node on the list at its own level. The parent node
points to only one child, and from that child it can reach the other children. This is
more convenient than maintaining one pointer per branch in the parent node, because
the number of branches will vary.
A pointer to the action function is executed when the node is selected. Only leaves
are allowed to have action functions. There is also a string, which is the name of the
node and is used for the display.
I use the convention that down means further into the menu structure, up means
back toward the root of the menu, and next means the adjacent branch on the current
level. Although these definitions of up and down mean that the tree is upside down, it
is the usual way to draw menu trees.

struct menuNode
{
/* parent node */
struct menuNode *upPtr;
/* default selection of the list of child nodes */
struct menuNode *downPtr;
/* The next option in the menu at the current level. */
struct menuNode *nextPtr;
/* The function to call if this leaf is selected.
The actionFn must be NULL if this is not a leaf */
void (*actionFn)(struct menuNode *nodePtr);
/* The name of this node for display purposes */
char * string;
/* If this node is a leaf, and has a value associated
with it then it is pointed to by valuePtr.
It is a pointer to void since the type of the
value may vary */
void *valuePtr;
};
typedef struct menuNode MenuNode;

A typical element follows.

MenuNode mColor={NULL,&mColorSole,&mSettings,NULL,"Color",NULL};

The parent is NULL, indicating that this node is at the top level. mColorSole is the
first node in the list of children of this node. mSettings is the next item in the list at
the current level. The actionFn is set to NULL, because this is not a leaf. The name of
this node "Color" is displayed to the user when this node is navigated. The final
NULL is the pointer to the value associated with the node, which, again, is unused in
this node.
70 — Front Panel: Designing Software for Embedded User Interfaces

Figure 4.4 shows the menu tree. This is the conceptual shape of the tree and repre-
sents the menu as the user sees it. The pointers stored in each node do not connect in
that way, however. The tree in Figure 4.4 requires variable numbers of down pointers,
which involves list management. It is simpler to link the siblings, as shown in Figure
4.5, which shows lines representing the actual pointers. The up pointers are not
shown. Any node with a NULL down pointer is a leaf and has an associated action
function and possibly an associated value.
The table is represented in code by the set of declarations in Listing 4.1. To
resolve forward references, all the structures must be declared before they are defined.
They are declared extern before the set of definitions.
GS_currentNodePtr points at the current node. This gives us a point from which
to navigate. It is declared as follows.

static MenuNode *GS_currentNodePtr;

It is initialized in menuInit() to point to mColor. This allows the menu to be reset at

any time by calling menuInit().
The menuDown(), menuUp(), and menuNext() functions perform the menu naviga-
tion. menuDown() has the extra responsibility of distinguishing between nodes that
have branches and nodes that are leaves. The menuUp() function must realize when it
is at the top level and not attempt to go any further. Because all the menus wrap
around, there is always a valid nextPtr.

Figure 4.4 The menu.

Color Settings Details Exit

Speed Pressure

Sole Lace Size Model

Upper

This diagram shows the menu tree, which is only two levels deep.
 Finite-State Machines and Table-Driven Software — 71

void menuNext(void)
{
GS_currentNodePtr = GS_currentNodePtr->nextPtr;
}
void menuDown(void)
{
if (GS_currentNodePtr->downPtr)
{
GS_currentNodePtr = GS_currentNodePtr->downPtr;
}
else
{
GS_currentNodePtr->actionFn(GS_currentNodePtr);
}
}
void menuUp(void)
{
if (GS_currentNodePtr->upPtr)
{
GS_currentNodePtr = GS_currentNodePtr->upPtr;
}
}

Figure 4.5 The menu shows the pointers as links.

Color Settings Details Exit

Pressure Brightness

Size Model

Sole Upper Lace

This diagram shows the menu tree, which is only two levels deep.
Listing 4.1 The table for a text menu as represented in code by a set of declarations.
/*
UP DOWN NEXT ACTION_FN STRING VALUE_PTR
*/
MenuNode mColor={
NULL, &mColorSole, &mSettings, NULL, "Color", NULL };
MenuNode mSettings={
NULL, &mSetPressure, &mDetails, NULL, "Settings", NULL };
MenuNode mDetails={
NULL, &mDetailsSize, &mExit, NULL, "Details", NULL };
MenuNode mExit={
NULL, NULL, &mColor, exitProgram, "Exit", NULL };
/* Expand out the Color sub-menu */
MenuNode mColorSole={
&mColor, NULL, &mColorUpper, selectColor, "Sole", &GS_trainer.soleColor };
MenuNode mColorUpper={
&mColor, NULL, &mColorLace, selectColor, "Upper", &GS_trainer.upperColor };
MenuNode mColorLace={
&mColor, NULL, &mColorSole, selectColor, "Lace", &GS_trainer.laceColor };
/* Expand the Settings sub-menu */
MenuNode mSetPressure={
&mSettings, NULL, &mSetBrightness, selectInt, "Pressure", &GS_trainer.pressure };
MenuNode mSetBrightness={
&mSettings, NULL, &mSetPressure, selectInt, "Brightness", &GS_trainer.brightness };
/* Expand the Details sub-menu */
MenuNode mDetailsSize={
72 — Front Panel: Designing Software for Embedded User Interfaces

&mDetails, NULL, &mDetailsModel, displaySize, "Size", NULL };

MenuNode mDetailsModel={
&mDetails, NULL, &mDetailsSize, displayModel, "Model", NULL };
 Finite-State Machines and Table-Driven Software — 73

Each leaf performs a task, while the internal nodes exist solely to allow naviga-
tion. Some leaves manipulate a field of the GS_trainer structure. Others just display
more information.
Several action functions implement option lists. When the user presses the Down
key on an option list, the current value is displayed. The Scroll key can be used to
view all possible values. Two asterisks mark the currently selected value, so the user
can distinguish it from the other options that he can scroll through.
By pressing the Down key on a menu item, the user may choose the value to apply
to the GS_trainer structure. For example, pressing the Down key while the display
contains Settings>Pressure = 7 sets the pressure field to the value 7. The display
changes to Settings>Pressure = 7 ** to indicate that the new value has been applied.
I need a function to handle changing values. There are two types of values handled
in the example program: integers and Colors. I will show the code for manipulating
integers; the code for Colors follows the same form. The first function, selectInt(),
is an action function pointed at by the menu structures. The second function,
adjustIntProcessKey(), handles user events once it establishes that he is trying to
change an integer. If the events must be directed to the adjustIntProcessKey()
function rather than one of the navigation functions, GS_eventHandlingFnPtr is set
to point to the adjustIntProcessKey() function. The controller checks this value
before performing any navigation. You can think of selectInt() as the setup func-
tion, while adjustIntProcessKey() does most of the real work involved in changing
a value.
Because the two functions must communicate with one another, GS_proposedInt
cannot belong to either one. It, therefore, has file scope.

static int GS_proposedInt;

void selectInt(MenuNode *nodePtr)
{
char intString[MENU_TEXT_LENGTH+1];
/*
The event handling function consumes all key events until it is cleared
*/
GS_eventHandlingFnPtr = adjustIntProcessKey;
/* Initialise the proposed value to the current value. */
GS_proposedInt = *(int *)(nodePtr->valuePtr);
/* Because we know that the first value displayed is the
current value, tag it with " **". */
sprintf(GS_viewString, " = %d **", GS_proposedInt);
}
74 — Front Panel: Designing Software for Embedded User Interfaces

void adjustIntProcessKey(MenuNode *nodePtr, char key)

{
/*
If it is a return (DOWN) key, accept the change
If the key is backspace (UP), cancel the change
If the key is a space (SCROLL), display the next possible value.
In cases in which we are finished processing then set the
GS_eventHandlingFnPtr back to NULL so that the menu keys
will be processed normally again.
*/
switch (key)
{
case DOWN_KEY:
*(int *)(nodePtr->valuePtr) = GS_proposedInt;
break;
case UP_KEY:
GS_eventHandlingFnPtr = NULL;
/*
We have already updated the display, so we want to
skip the following update by returning now.
*/
return;
case SCROLL_KEY:
/*
This is the one place in the function where it is necessary
to check which particular integer we are adjusting. If
there were a great number of integers, we could consider
adding a field to the MenuNode to store this information
*/
if (nodePtr == &mSetPressure)
{
GS_proposedInt = (GS_proposedInt + 1) %
(MAX_TRAINER_PRESSURE + 1);
}
else if (nodePtr == &mSetBrightness)
{
GS_proposedInt = (GS_proposedInt + 1) %
(MAX_TRAINER_BRIGHTNESS + 1);
}
else
{
assert(FALSE);
}
break;
default:
; /* ignore all other keys */
}
 Finite-State Machines and Table-Driven Software — 75

sprintf(GS_viewString, " = %d", GS_proposedInt);

/* Tag the value if it is the currently selected value. */
if (GS_proposedInt == *(int*)(nodePtr->valuePtr))
{
strcat(GS_viewString, " **");
}
}

The alternative to using GS_eventHandlingFnPtr is having selectInt() not

return to the event loop at all but read the events itself. The following function would
perform this task, and for this small example it would actually work.
void selectInt(MenuNode *nodePtr)
{
char key;
GS_proposedInt = *(int *)(nodePtr->valuePtr);
while(1)
{
if (kbhit())
{
key = getch();
adjustIntProcessKey(nodePtr, key);
if (key == UP_KEY)
{
return;
}
menuUpdateDisplay();
}
}
}

The problem with this function is that if control does not revert to a central event
loop while the user adjusts the current value, that task will not get an opportunity to
process events other than the ones allowed for in the selectInt() function. If I
added a single Exit key that would exit the menu from any point, I would have to
change code in the main event loop. I would also have to update selectInt(). This
would not be a satisfactory arrangement, especially because selectColor() would
probably be coded the same way, leading to three updates. I am going to such pains to
illustrate this mistake because it is so common.
A couple of other functions accessible from the Details menu display the size and
model of the trainer. They have a simple job of displaying the menu with the extra
information tagged on to the end of the menu line.
76 — Front Panel: Designing Software for Embedded User Interfaces

void displaySize(MenuNode *nodePtr)

{
sprintf(GS_viewString, " = %d", TRAINER_SIZE);
}

/*
Currently there is only one model of this trainer. It is called Speedy, so we
can hardcode this piece of information in the leaf for details/model.
*/
void displayModel(MenuNode *nodePtr)
{
strcpy(GS_viewString, " = SPEEDY");
}

The exitProgram() function, accessible from the top level of the menu, provides a
trivial way of escaping from the menu program.

void exitProgram(MenuNode *nodePtr)

{
exit(0);
}

[Link] The View

Given any node, I can display the location. I name the location by naming the whole
path from the top level, so the submenu Sole under Color appears as follows on the
display

Color>Sole

The function menuUpdateDisplay() constructs this string by navigating up the tree

until the top is reached, appending strings as it goes. This string is called the path
because it bears a resemblance to a file system directory path. The textDisplay()
function, which implements the physical layer, is responsible for displaying the con-
structed string. On the companion disk, the example implements a version of text-
Display() that simply displays the string on your PC’s screen.
The GS_viewString is appended to the end of the path before printing. This is a
useful way of inserting data associated with some of the leaves. This is view-only
data, because the information is in string form and cannot be interpreted as easily as
the information in the model, such as the values of settings and colors. The view data
is never used for any purpose other than updating the display. I assume that the
model data is used by the rest of the trainer software to control color, brightness, and
air pressure.
 Finite-State Machines and Table-Driven Software — 77

void menuUpdateDisplay(void)
{
MenuNode *menuNodePtr = GS_currentNodePtr;
char displayString[MENU_TEXT_LENGTH+1];
char stringSoFar[MENU_TEXT_LENGTH+1];
/*
displayString would not need to be initialised here except for
the case in which we are in the main menu and the while loop
below will has zero iterations.
*/

strcpy (displayString, menuNodePtr->string);

strcpy (stringSoFar, menuNodePtr->string);
/*
Ensure that the last character is NULL. If this is
overwritten, the string was too long and there is a bug
somewhere in the program. It will be detected in the assert
below.
*/
displayString[MENU_TEXT_LENGTH] = '\0';
/*
This loop will concatenate all the names of the menu nodes,
placing a >-in between.
*/
while (menuNodePtr->up != NULL)
{
strcpy(displayString, menuNodePtr->upPtr->string);
strcat(displayString, ">");
strcat(displayString, stringSoFar);
strcpy(stringSoFar, displayString);

menuNodePtr = menuNodePtr->upPtr;
}
/*
If a string was set in GS_viewString, append it to
the end of the display string.
*/
strcat(displayString, GS_viewString);
/* Ensure that the string never overruns */
assert(displayString[MENU_TEXT_LENGTH] == '\0');
/* Print the string on the display. */
textDisplay(displayString);
}
78 — Front Panel: Designing Software for Embedded User Interfaces

[Link] The Controller

The function menuProcessKey() is the entry point for the key events that are
received. All menu manipulations start and end here. The global static
GS_eventhandlingFnPtr points to a function that may process key events if the user
enters particular leaves. This is a useful tool for directing events once an action func-
tion has decided that some event processing must be performed independent of the
menu navigation.

void menuProcessKey(char key)

{
/*
Clear this string, any node that requires it will set it.
*/
GS_viewString[0] = '\0';
/*
If a event-handling function is set up, let it process the
key; otherwise, the key is used to navigate the menu.
*/
if (GS_eventHandlingFnPtr)
{
GS_eventHandlingFnPtr(GS_currentNodePtr, key);
}
else
{
switch (key)
{
case DOWN_KEY:
menuDown();
break;
case UP_KEY:
menuUp();
break;
case SCROLL_KEY:
menuNext();
break;
default:
; /* ignore keys that can not be processed */
}
}
}

In order to make the menu a stand-alone executable program, the module menu-
main.c implements a loop capturing all keyboard input and passes it to the controller
(i.e., the menuProcessKey() function). The menumain.c module also defines text-
Display(), which displays the output on the PC screen.
 Finite-State Machines and Table-Driven Software — 79

4.8.3 Advantages of Table-Driven Code

Depending on the types of queries and commands you wish to use, you may want to
add further facilities to your menu. If you add further menu functions or take away
existing features, you will find that the table of nodes is the piece of code that links
them. Updating this table can change the menu’s behavior dramatically. Structuring
the code in this way allows the programmer to see the flow of control easier than if he
has to follow several levels of nested switch statements or if-else-if constructs.
If the table you construct to solve your problem grows large and unwieldy, you
determine if there is a common theme being repeated. If so, it may be possible to
make the table processing more powerful, allowing the table to shrink.
If the menu were implemented using the FSM approach, I would have used one
line of the table for each transition between nodes. Instead, I used one line of the table
for each node. The table using the FSM would have taken 18 table entries instead of
11. The memory saving is irrelevant in comparison with the difficulty of managing and
maintaining large tables. If I had used one structure per transition, I would have also
lost the convenience of having slots to store the name of each node and the valuePtr
field. Having places to put things is one benefit of well-structured code and tables.

Experiment with table contents until you find a structure that matches
your needs.