trunk/c_pco0/c_pco0.tex

%$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_pco0/c_pco0.tex,v 1.4 2003/03/03 23:50:43 dtashley Exp $

\chapter{\cpcozerolongtitle{}}

\label{cpco0}

\beginchapterquote{``For any serious purpose, intelligence is a very minor gift.''}
                     {G. H. Hardy, \cite{bibref:b:mathematiciansapology:1940}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%Section tag: INT0
\label{cpco0:sint0}

In this chapter, we explain in detail the way that
practical microcontroller software is constructed.
Such discussion is essential for two reasons:

\begin{itemize}
\item Practical techniques of construction, because they have 
      been honed over time, usually represent best practices.
      The techniques presented in this chapter represent worthy
      techniques for constructing embedded systems, and may
      serve as a guide for the construction of embedded software.
\item Software engineers often grasp concepts intuitively that they
      cannot express formally.  Many of the tendencies and best practices
      described in this chapter have a formal basis that can and should be
      studied and investigated.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Measurement Of Time}
%Section tag: MOT0
\label{cpco0:smot0}

As we've mentioned previously, most software components in a
typical small embedded system are state machines with transition
functions that depend on inputs and on time.

Because time is such a perasive concept in microcontroller software,
the decision about how time is to be measured and tested is the
single most important design decision in terms of ROM consumption.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Countdown Software Timers}
%Subsection tag: CST0
\label{cpco0:smot0:scst0}

The most common mechanism for allowing state machines to make transitions
which are partly based on time is the 
\index{countdown software timer}\emph{countdown software timer},
which is most commonly called a 
\index{software timer}\emph{software timer}.

A software timer is an unsigned byte or word which is decremented at a 
periodic rate, but never decremented beyond zero.  All software 
timers in a system are typically decremented by one system process.
A process which uses a software timer will set (assign) it to
a non-zero value representing a time delay, and then test it against 
zero to check if the time delay has elapsed.  This approach has
several advantages:

\begin{itemize}
\item Setting a software timer (assigning it to a non-zero
      value) is a very inexpensive and compact test.  (Because
      the setting of software timers occurs many times throughout
      ROM, this savings can be substantial.  Additionally,
      there is a savings in execution time.)
\item A test of a byte against zero is typically a very 
      inexpensive and compact test.  (Because tests for
      expired timers occur many times throughout ROM,
      this savings can be substantial.  Additionally, there
      is a large savings in execution time because 
      in a typical software load, \emph{many} transition
      functions depend on expired timers.)
\item Decrements of single bytes, as are required
      to decrement software timers, are also inexpensive operations.
\end{itemize}

Because software timers are either one unsigned byte (8 bits) or
one unsigned word (16 bits), it is not possible to have ``one size
fits all'', as the range of a software timer and its precision
are mutually exclusive.  Very typically, software timers are arranged 
in either binary decades (for example, 2 ms/count, 4 ms/count, 
8 ms/count, 16 ms/count, etc.) or in the more conventional
1-2-5 decades (for example, 1 ms/count, 2 ms/count, 5 ms/count,
10 ms/count, etc.).

Because the process which uses a software timer as a time 
reference and the process which decrements a software timer
are asynchronous, a process which sets a software timer has no 
control over whether the timer will be decremented for the
first time immediately or after the period-per-count of the timer.
Generally, if $\tau$ is the period-per-count of a software timer and
the software timer is set to the value of $N$, the process that
sets the software timer can be assured that the time $T$ until the
software timer reaches zero will meet the inequality

\begin{equation}
\label{eq:cpco0:smot0:scst0:00}
(N-1) \tau < T \leq N \tau ,
\end{equation}

\noindent{}where the interval is open on the left because 
it is not possible to test a software timer at
the same instant it is set.

Despite the inequality supplied by 
(\ref{eq:cpco0:smot0:scst0:00}), it is common in practice to calculate
the value to which a software timer should be set as

\begin{equation}
\label{eq:cpco0:smot0:scst0:01}
N = \left\lfloor { \frac{T}{\tau} } \right\rfloor .
\end{equation}

(\ref{eq:cpco0:smot0:scst0:01}) is commonly used because there
are other sources of delay in a software system that compensate
for the lower bound in (\ref{eq:cpco0:smot0:scst0:00}), and because
values of $N$ are seldom close to zero, so any error due to the
lower bound is small in relation to $T$.

It is also instructive to calculate the maximum ``coarseness'' when 
software timers are arranged in binary decades or 1-2-5 decades
and consequently a period-per-count $\tau$ which precisely accomodates
the maximum period $T$ cannot be chosen.  In the case of binary decades,
the inequality

\begin{equation}
\label{eq:cpco0:smot0:scst0:02}
\frac{255}{2} \tau < T \leq 255 \tau
\end{equation}

\noindent{}holds, as if it were true that $T \leq 255 \tau /2$, 
then we would choose
a software timer with the next smaller period $\tau ' = \tau / 2$.
Thus we are always assured that

\begin{equation}
\label{eq:cpco0:smot0:scst0:03}
\tau < 127.5 T .
\end{equation}

\noindent{}Thus, with a binary decade arrangement of software timers, we
can always choose the timer period $N \tau$ with a granularity of about
1 part in 127.5 or better.

The analogous question for software timers arranged in 1-2-5 decades
leads to this inequality:

\begin{equation}
\label{eq:cpco0:smot0:scst0:04}
\frac{255}{2.5} \tau < T \leq 255 \tau ,
\end{equation}

\noindent{}where the factor ``2.5'' appears because the largest
change in $\tau$ will occur from ``2'' to ``5'' in a 1-2-5 decade
arrangement.  Again, the same argument made earlier 
applies---if $T \leq 255 \tau / 2.5$, then it would \emph{always}
be possible to choose a software timer with the next smaller period.
Thus we are always assured that

\begin{equation}
\label{eq:cpco0:smot0:scst0:05}
\tau < 102 T .
\end{equation}

\noindent{}Thus, with a 1-2-5 decade arrangement of software timers, we
can always choose the timer period $N \tau$ with a granularity of about
1 part in 102 or better.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{On-Demand Two's Complement Timekeeping}
%Subsection tag: ODT0
\label{cpco0:smot0:sodt0}

Often, software timers as described in Section \ref{cpco0:smot0:scst0}
immediately above won't meet a particular timing requirement because
the period to be measured is quite large, but it must be measured with
fair precision.\footnote{A typical requirement with these characteristics
is that a delay be 60 minutes $\pm$ 5 seconds.  This requirement
represents a precision of 1 part in 720, which is more precision
than a 1-byte software timer can offer.}  

In such situations, one 
option is to offer extended-precision (i.e. 16- or 24-bit) software timers.
However, another popular option is to provide a function call which
will allow retrieval of the most precise time measurement available,
typically maintained as a multiple-precision integer.  A typical
design decision in microcontroller work would be a 5-byte multiple-precision
integer counter, maintaining the number of milliseconds since the 
microcontroller was reset.  Such a counter will measure time periods
of up to about 35 years.

Note that in using the value obtained from a function call
which obtains a maximum-precision time count, it is not
necessary to use all the bytes of the result.  For example,
using the least significant two bytes of such a counter
(assuming that the counter represents milliseconds) will
allow the measurement of time periods up to about 65 seconds
with 1ms of resolution.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Invocation Counting}
%Subsection tag: ICN0
\label{cpco0:smot0:sicn0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Timer Events}
%Subsection tag: TEV0
\label{cpco0:smot0:stev0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Interface Styles}
%Section tag: IST0
\label{cpco0:sist0}

Without exception, the paradigm of decomposition for small microcontroller
software is a collection of concurrent cooperating state machines.  In other
words, we imagine
the software system as collection of state machines\footnote{\ldots{} or processes or 
timed automatons or elementary hybrid machines or state machine thingies
or thingamabobs or whatever it is in your lingo, man \ldots{}.} which are
\emph{independent} or \emph{concurrent}:  that is, they can in most 
cases change state independently
of one another.  However, at the same time, we envision these
state machines as \emph{cooperating}:  that is, they have ways 
of exchanging information and of synchronizing when necessary.

In this section, we enumerate and discuss all of the interface
types between 
concurrent cooperating state machines.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection[1-Writer $n$-Reader RAM Variable Interface]
           {1-Writer \mbox{\boldmath $n$}-Reader RAM Variable Interface}
%Subsection tag: own0
\label{cpco0:sist0:sown0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Finite State Machine RAM Variable Interface}
%Subsection tag: fsm0
\label{cpco0:sist0:sfsm0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{The General FSM RAM Variable Interface}
%Subsubsection tag: gfs0
\label{cpco0:sist0:sfsm0:sgfs0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{The RAM Variable Semaphore}
%Subsubsection tag: rvs0
\label{cpco0:sist0:sfsm0:srvs0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Reduction Of Combinational Mappings}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Reduction Of Sequential Mappings}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Debouncing}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Filtering}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{ROM Reduction Techniques}
%Section tag: rrs0
\label{cpco0:srrs0}

Microcontroller products are very sensitive to ROM consumption, and
a primary goal is to create a software load that meets all requirements
with minimal ROM.  Semiconductor manufacturers often design 
microcontroller families so that there is a continuum of microcontroller
variants which differ only in the amount of ROM and RAM available,
and in some cases a microcontroller software developer is able to 
substitute a different part with more ROM if a ROM boundary is reached.
However, semiconductor manufacturers always create a pricing schema
where the part with more ROM costs more, and so even if a part with
more ROM is available, there may be substantial management pressure to
shoehorn a software load into the smaller part rather than use the
more expensive part. In many cases, no substitute part with more ROM
is available, so the software load \emph{must} fit.

In this section, we discuss strategies for reducing ROM consumption
in an embedded software load.  For the most part, these are strategies
that can be adopted retroactively when a software load does not fit.
However, it should also be noted that ROM efficiency \emph{starts}
with using some of the construction techniques presented in this chapter
in order to create a ROM-efficient system from the start.  For example, 
an inefficient design decision regarding the measurement of time
would be hard to recover from.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Modifying The Largest Software Component First}
%Subsection tag: mlf0
\label{cpco0:srrs0:smlf0}

One observation which is helpful is that the largest software components
in a system tend to have the most absolute ROM waste.\footnote{Thanks
to Lou Miller \cite{bibref:i:loumiller} for this insight.}  
Therefore, the quickest way to significantly reduce the ROM consumption
of an embedded software load is often to analyze and optimize the 
largest software component.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Optimizing \emph{near} Versus \emph{far} Allocation Of RAM}
%Subsection tag: nvf0
\label{cpco0:srrs0:snvf0}

Many microcontrollers have two different categories of RAM, which are
usually called \emph{near} and \emph{far} RAM; although some microcontrollers
use different nomenclature---for example \emph{zero page} RAM rather than
\emph{near} RAM.  Usually, \emph{near} and \emph{far} are also 
the `C' keywords used.

Usually, \emph{near} RAM has three advantages over \emph{far} RAM:

\begin{itemize}
\item Machine instructions to access (load, store, test, perform
      arithmetic on) near RAM locations are more compact than the
      corresponding instructions on far RAM.  This normally comes
      directly from the machine-language encoding of instructions:
      most typically the address of a near location requires one byte
      to encode while the address of a far location requires two.
\item Machine instructions to access (load, store, test, perform
      arithmetic on) near RAM locations require less time to
      execute than the
      corresponding instructions on far RAM.  This is normally
      strongly related to the more compact encoding, as there
      are fewer ROM fetches involved.
\item In many cases, certain instructions can operate only on near
      operands.  This means that certain operations applied to
      near operands require only one machine instruction,
      but require at least three (load, operate, store) when 
      applied to far operands.
\end{itemize}

It is intuitively clear that to minimize ROM consumption, assuming that
we have a limited amount of near RAM and cannot place all variables
in near RAM, we must place the most frequently-accessed (throughout
all of ROM) variables in near RAM.

In practice, the allocation of most frequently accessed variables to 
near RAM happens both formally and informally in microcontroller 
software developments.  

Informally, it occurs because it is known
from experience that certain RAM variables are frequently accessed
and should be placed in near RAM---for example, in most automobile
modules, ignition switch position is referenced many times throughout
ROM and software developers know from experience that this is best placed
in near RAM. 

Formally, software developers often produce home-made tools to analyze
the number of times throughout ROM that each variable is referenced, and then
use this information to allocate variables into near and far RAM.
Unfortunately, this process is usually manual and cumbersome.
To the best of our knowledge, as of 9/2001, no compiler will analyze
variable reference information and allocate variables automatically.
(The best way to accompish this would probably to introduce an
addtional keyword that advises the development tools to analyze
the number of references and automatically choose whether a variable should be 
near or far.  \texttt{autonearfar} strikes us as a suitably
suggestive keyword.)


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Storage Of Intermediate Results In Near RAM}
%Subsection tag: sir0
\label{cpco0:srrs0:ssir0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Suppression Of \emph{Else} Clauses}
%Subsection tag: sec0
\label{cpco0:srrs0:ssec0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Reassignment Of State Variable State Values}
%Subsection tag: rsv0
\label{cpco0:srrs0:srsv0}

Generally, a state machine constains both a discrete state and a
``continuous'' state (software timers).  (In the strictest sense,
the software timers are not discrete state, but they are typically
modeled this way.)  It can be advantageous to give careful thought
to how the numerical values of discrete states are assigned.

The following observations can be made about the influence of the
numerical values of discrete states on ROM consumption:

\begin{itemize}
\item Tests against zero may sometimes be cheaper than
      tests against any other value (depending on the processor
      instruction set).  This may imply that the numerical value
      of zero should be assigned to the state which is most
      often tested for.
\item In some cases, assignment to zero may be cheaper than
      assignment to any other value (i.e. a ``clear" instruction
      versus a ``set'' instruction, depending on the instruction
      set).  This may imply that 
      the numerical value of zero should be assigned to the
      state with the most incoming transitions.
\item It may frequently occur that tests for which discrete
      state the system is in are seeking to detect
      not a single state, but rather a group of states (i.e.
      \texttt{if ((state == STATE\_1) || (state == STATE\_2) || \ldots{} )}).
      In such cases, it may be advantageous to assign numerical values
      to make such tests more economical, i.e. it may be advantageous
      to ``equivalence class'' states (we discuss this in subsequent
      paragraphs).
\end{itemize}

We should add more about the equivalence classing of states.  In this
context, we mean equivalence classing under the instruction set of the
microcontroller.  That is, we seek to find some way to assign numerical
values to states so that some instruction (\emph{any} instruction!) will
break them into the classes we desire.  It is also noteworthy that we seek
as much flexibility (as many options) as possible, because we may wish to
create more than two equivalence classes, and we may also
wish for some states to appear in more than one equivalence class.

Examples of methods to equivalence class are:

\begin{itemize}
\item Using a bitwise ``AND'' instruction to mask out all
      but $n$ bits (of an $N$-bit state variable)
      and test the result
      against zero.  This creates two equivalence
      classes, one of cardinality $2^{N-n}$ 
      and the other of cardinality 
      $2^N - 2^{N-n} = (2^n - 1)(2^{N-n})$.
\item Testing (comparing) against a specific value.  This creates
      equivalence classes of arbitrary cardinality.
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Factoring Of \emph{Any} Repeated Operation}
%Subsection tag: far0
\label{cpco0:srrs0:sfar0}

In a typical microcontroller, a subroutine call requires three bytes in ROM
(one byte for the opcode, and two for the address).  Thus, for any
repeated operation which requires over three bytes to accomplish,
it normally is most effective to place the operation in a subroutine.
Such a technique will exact a performance penalty in exchange for
ROM savings.

Most commonly, such a technique is applied to variable assignments which
accompany state transitions.  However, it can also be applied
to subexpressions in state transition functions.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Factoring Of State Transition Functions And Transitions}
%Subsection tag: fst0
\label{cpco0:srrs0:sfst0}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Initialization}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The Interrupt Subsystem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Sleep And Wakeup}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\vfill
\noindent\begin{figure}[!b]
\noindent\rule[-0.25in]{\textwidth}{1pt}
\begin{tiny}
\begin{verbatim}
$RCSfile: c_pco0.tex,v $
$Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_pco0/c_pco0.tex,v $
$Revision: 1.4 $
$Author: dtashley $
$Date: 2003/03/03 23:50:43 $
\end{verbatim}
\end{tiny}
\noindent\rule[0.25in]{\textwidth}{1pt}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% $Log: c_pco0.tex,v $
% Revision 1.4  2003/03/03 23:50:43  dtashley
% Substantial edits.  Safety checkin.
%
% Revision 1.3  2001/09/12 18:08:34  dtashley
% Closing book project temporarily as returning to school for Ph.D.
%
% Revision 1.2  2001/08/31 23:11:17  dtashley
% End of August 2001 safety check-in.
%
% Revision 1.1  2001/08/25 22:51:26  dtashley
% Complex re-organization of book.
%
%End of file C_PCO0.TEX