%$Header$ \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