\documentstyle[newcen,utility,margins,rpulse,underscore,11pt]{report}
\title{Technical Guide to the 6.111 C Simulator}
\author{Mark W. Eichin}


\begin{document}
\bibliographystyle{plain}

\maketitle
\newpage
\tableofcontents
\newpage

\chapter{Introduction}

The C simulator is a time compression sequential digital logic
simulator. It compiles a circuit description into a C program, which
can then be executed with varying inputs or with input streams from
other programs as appropriate.

This Technical Guide will describe the inner workings and design of
the simulator library and macro packages, as well as the flow of
control used in building a simulation. While simple instructions are
provided for producing straightforward simulations, improvements are
only possible with an understanding of the system. Also, it is
expected that complex extensions (such as a UART module, for example)
would be implemented in a more efficient manner than would happen with
high level gate based implementation.

The system is designed to conform to the dpANS C standard\footnote{as
tested with the Free Software Foundation GCC v1.21}, as well as being
usable with existing C compilers\footnote{4.3BSD Vax Portable C
Compiler}. It has also been tested for portability\footnote{MetaWare
High C compiler, IBM 4.3BSD release.}\footnote{Macintosh Programmers
Workshop C, 1.0, Mac II} on machines of moderately interesting
architectures.

\chapter{Building Submodules}
Complex submodules should either be
\begin{itemize}
\item implemented in C as new functions, or
\item implemented as simulator subunits.
\end{itemize}

New functions are straightforward to implement, and fast as well, if you are
familiar with the internal workings of the simulator.

\section{Submodule}

A submodule, which can be either a user defined circuit element or a
primitive, has three important components:
\begin{itemize}
\item a macro header, which is stripped out to provide
``sugar''\footnote{Syntactic Sugar, some language extension used
solely to sweeten a particularly unpalatable syntax for the user.}
macros which are the users view of the circuit element
\item comments describing what the function of the module is. These
are often overlooked by engineers who either are in a hurry to
implement their device or who assume it is straightforward and obvious
\item the driver routine for the function, which gets called every
time any input line changes.
\end{itemize}

\subsection{Macro Header}
Two pieces of information are needed by the compiler to give the user
a simple interface to the module: a procedure declaration and a macro
``connector''. The procedure declaration can be simply
\begin{code}
int my_func();
\end{code}

This is extracted from the source file, where a line
\begin{code}
#define FUNCTION my_func
\end{code}
signals both the start of the header information and the name of the
function being defined in this module.

\subsection{Connector macros}

The connector macro is much more complex. To implement a gate's
connection to the wires in a circuit, the gate must first be assembled
as a list. The first element of the list is a procedure, the rest of
the elements are later passed to it as arguments. Thus, a typical list
for an xor gate would consist of {\em (xor_func C A B)\/}, and the
procedure would be called with {\em (C A B)\/} as arguments.

Once the connector list is assembled, it has to be attached to its
inputs. (The outputs are already ``attached'' by virtue of their being
arguments to the procedure.) The list becomes a property of all the
inputs, and when any of them change, the procedure is automatically
run. 

\subsection{Connector macro builders}

For the user's convenience, {\em make_binop, make_unop, make_tracer\/}
are provided to produce circuit one output elements with two inputs,
one input, or a no-output element with one input (for ``tracing'' a
line, either monitoring for some specific change or recording the
values outside of the simulator.) These are constructed\footnote{See
{\em chains.c}} using the {\em make_anop\/} macro. This macro is
called with the list of arguments, the list of dependencies (which
are generally subsets, though not strictly so) and the lengths of the
argument lists. Due to the lack of a {\em varargs\/} concept for C
macros, these lengths are used to index into other macros, which are
predefined for a reasonable range of values (0-10). In order to handle
longer procedure macros with with make_anop, simply create more macros
in the style of {\em make_arg0-10\/} and {\em make_dep0-9\/} with the
appropriate parameter.

\section{Preprocessing}

A custom preprocessor could have been written to perform this
operation automatically, however that could have drastically reduced
the portability of the system. The only specialized handlers used are
two awk scripts:
\begin{itemize}
\item mkchn.awk: takes the chains.c file and converts it to a valid C
file by backslash-quoting the ends of the lines of the long macros
used in chains.c. This permits chains.c to be more readable and easier
to maintain.
\item mkfunc.awk: takes all modules in the funclib directory and grabs
the {\tt \#define FUNCTION my_func} lines and the actual {\tt
\#define} for the connection macro.
\end{itemize}
Awk is sufficiently portable that this is not a major concern, and in
any case the operations can either be done on a machine that does have
them, or done by hand with a text editor.



\chapter{Control Flow}

\section{File organization}

The system is currently made of two distinct subsystems, the function
libraries (with all of the primitive elements) and the support
libraries (the main control loop, the debugging aids, event
processing, and memory management tools). When an executable is
built, it simply links all of the objects mentioned in the makefile
and then links against {\tt libfunc.a\/} which contains the individual
primitive elements.

\section{Program Flow}

A typical simulation flows as follows:
\begin{itemize}
\item {\tt init_run()} sets startup values and initializes the memory
allocator.
\item the {\tt master} wirelist is initialized to begin holding wires.
\item {\tt FileArgs()} parses the arguments looking for -i and -o
directives to indicate where input and output are to go. Leaving out
-i implies no input, while -i - implies standard input.
\item {\tt MAKEWIRE()} is used to declare the wires and name them and
add them to the {\tt master} wirelist.  This macro, if expanded, can
be seen to actually use separate strings for the name and the
variable, but this was deemed too confusing for typical users. If it
is appropriate, simply add another macro to chains.c that behaves
differently.
\item Macros such as {\tt AND(), OR(), OUTPUT()} are used to hook
gates to wires.
\item {\tt run_all()} runs through all wires in the {\tt master}
wirelist. 
\end{itemize}

\section{Data Structure}

The entire simulation can be chased down from the {\tt master}
wirelist\footnote{Somewhat like pretty-printing a lisp structure.} to
show all of the data handled by the simulator.

\catcode`_=12
\newenvironment{struct}%
{\begin{list}{}{\renewcommand{\makelabel}[1]{{\bf $\bullet$}{\tt ##1:}}}}%
{\end{list}}

\begin{struct}
\item[Wirelist] can contain two types of records:
\begin{struct}
\item[wire] which are the wires (runs of wire which carry
the same signal) themselves
\item[wfile] which is an input file that can modify arbitrary wires by
name. 
\end{struct}
\item[Wire] carries several types of records:
\begin{struct}
\item[symname] is the symbolic name of the wire (for printout and
reference in the input file.)
\item[deps] is the list of argument lists which should be run when
this wire changes.
\item[now] is a pointer into the timeline for this wire indicating the
current value, to be read by any procedure examining this wire.
\item[then] is a pointer into the timeline for this wire indicating
the next value that this value will take and when it will take it.
\item[future] is the root of a timeline going into the future (for
further expansion; it currently doesn't ever change.)
\item[past] is the root of a timeline going backwards into the past
(for recording what scrolls off of future, especially for logging
offline; not currently used.)
\item[contention] is a record containing the current set of sources
which are driving this Wire in other than tristate mode, to be used to
reevaluate the {\tt now} value when changes occur.
\end{struct}
\item[Depend] a single item of a dependency list, with a data field
pointing to a Deps vector.
\item[Deps] is simply a list of Generic items, used as a procedure
handle and arglist in the wire, and also used to pass things around
the constructor macros.
\item[Generic] is a union of ``useful'' types which would be elements
of an argument list. These include:
\begin{struct}
\item[genint] integer
\item[genstring] pointer to character, simple string
\item[gentime] Time, actually long value (for delay element)
\item[genwire] Wire (discussed above)
\item[genfunc] Pointer to function returning integer (node function.)
\end{struct}
\item[Event] has a tag of the state and a value of the time at which
the state became valid. These states are
\begin{struct}
\item[LOGIC_HI] +5v, logical ``1'' or high value, assured assertion
\item[LOGIC_LOW] 0v, logical ``0'' or low value, assured assertion
\item[EARLY_HI] Earliest time a high could be asserted (if EARLY\_HI is not
followed by a LOGIC\_HI, a race condition is probably exists)
\item[EARLY_LOW] Earliest time a low could be asserted (if EARLY\_HI is not
followed by a LOGIC\_LOW, a race condition is probably exists)
\item[TRISTATE] This line is not driving, and thus an added signal
will not contend for the line.
\item[CONTENDING] This line is in contention, refer to the Contention
record for detail.
\item[FILE_FETCH] This line has input on some file stream pending.
{\em this is obsolete, with the WFile structure doing the work now.}
\end{struct}
\item[Ctl] A control tag is a low level tag that should only be seen
by the bottom level procedures. They signal different things to the
{\tt INC} and {\tt DEC} procedures:
\begin{struct}
\item[END] Stop, this is the end of the rope. If data is also end then
this is the end of a rope piece as well (and thus at the end of an
aligned block.)
\item[BEGIN] Stop (if backing up), this is the beginning of the rope,
and guaranteed to be at the start of an aligned block of data.
\item[NEXT_FORWARD] the data points to the aligned start of a rope
piece that has the next forward rope element.
\item[NEXT_BACKWARD] the data points to the aligned tail of a rope
piece that has the next backward rope element.
\item[NEXT_FORWARD_UNALIGNED] the data points to the unaligned start
of a rope piece that has the next forward rope element.
\item[NEXT_BACKWARD_UNALIGNED] the data points to the unaligned tail
of a rope piece that has the next backward rope element.
\item[FREELIST] this item is an element of the freelist, and the data
field points to another element.
\end{struct}
\end{struct}

\chapter{Document Production}

This Technical Document, and the accompanying User Guide, were
produced with the \LaTeX\/ document production system. Some tools were
created to make this task easier, such as
\begin{itemize}
\item A ``code'' environment, derived from the verbatim environment,
which sets text without interpreting punctuation or spaces, in a
typewriter style font.\footnote{Derived directly from {\tt
latex.tex}\cite{latextex} with changes to line breaking and tab
handling.}
\item A modified ``frepcode'' environment which could read an
arbitrary external file (to permit including live examples directly
into the text.) in code style.\footnote{Simple change to ``code''.}
\item An ``rpulse'' document style option, and ``wave'' environment,
for simple typesetting of waveforms.\footnote{Inspired by work done by
Robert French for 6.004.}
\item A tool to convert simulator data files into \LaTeX\/ code using
the ``wave'' environment to simplify including waveforms. It performs
auto scaling to fit the wave across the page.
\end{itemize}

\begin{figure}
\caption{Awk script to make ``wave'' text from simulator data files}

\begin{frepcode}{../src/awk/makewave.awk}
\end{frepcode}

\end{figure}

\section{utility.sty --- generic useful styles including ``code''}

\begin{frepcode}{utility.sty}
\end{frepcode}

\section{rpulse.sty --- \LaTeX\/ style file for producing waveforms}

\begin{frepcode}{rpulse.sty}
\end{frepcode}

\bibliography{usrdoc}
\end{document}
