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.
Building Submodules
Complex submodules should either be
- implemented in C as new functions, or
- implemented as simulator subunits.
New functions are straightforward to implement, and fast as well, if you are
familiar with the internal workings of the simulator.
Submodule
A submodule, which can be either a user defined circuit element or a
primitive, has three important components:
- 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
- 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
- the driver routine for the function, which gets called every
time any input line changes.
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
<![CDATA[
int my_func();
]]>
This is extracted from the source file, where a line
<![CDATA[
#define FUNCTION my_func
]]>
signals both the start of the header information and the name of the
function being defined in this module.
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 (xor_func C A B), and the
procedure would be called with (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.
Connector macro builders
For the user's convenience, 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
chains.c} using the 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 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 make_arg0-10 and make_dep0-9 with the
appropriate parameter.
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:
- 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.
- mkfunc.awk: takes all modules in the funclib directory and grabs
the #define FUNCTION my_func lines and the actual
#define for the connection macro.
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.
Control Flow
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 libfunc.a which contains the individual
primitive elements.
Program Flow
A typical simulation flows as follows:
- init_run() sets startup values and initializes the memory
allocator.
- the master wirelist is initialized to begin holding wires.
- 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.
- MAKEWIRE() is used to declare the wires and name them and
add them to the 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.
- Macros such as AND(), OR(), OUTPUT() are used to hook
gates to wires.
- run_all() runs through all wires in the master
wirelist.
Data Structure
The entire simulation can be chased down from the master
wirelist\footnote{Somewhat like pretty-printing a lisp structure.} to
show all of the data handled by the simulator.
- Wirelist can contain two types of records:
- wire which are the wires (runs of wire which carry
the same signal) themselves
- wfile which is an input file that can modify arbitrary wires by
name.
- Wire carries several types of records:
- symname is the symbolic name of the wire (for printout and
reference in the input file.)
- deps is the list of argument lists which should be run when
this wire changes.
- now is a pointer into the timeline for this wire indicating the
current value, to be read by any procedure examining this wire.
- 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.
- future is the root of a timeline going into the future (for
further expansion; it currently doesn't ever change.)
- 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.)
- 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 now value when changes occur.
- Depend a single item of a dependency list, with a data field
pointing to a Deps vector.
- 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.
- Generic is a union of ``useful'' types which would be elements
of an argument list. These include:
- genint integer
- genstring pointer to character, simple string
- gentime Time, actually long value (for delay element)
- genwire Wire (discussed above)
- genfunc Pointer to function returning integer (node function.)
- Event has a tag of the state and a value of the time at which
the state became valid. These states are
- LOGIC_HI +5v, logical ``1'' or high value, assured assertion
- LOGIC_LOW 0v, logical ``0'' or low value, assured assertion
- 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)
- 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)
- TRISTATE This line is not driving, and thus an added signal
will not contend for the line.
- CONTENDING This line is in contention, refer to the Contention
record for detail.
- FILE_FETCH This line has input on some file stream pending.
this is obsolete, with the WFile structure doing the work now.
- 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
INC and DEC procedures:
- 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.)
- 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.
- NEXT_FORWARD the data points to the aligned start of a rope
piece that has the next forward rope element.
- NEXT_BACKWARD the data points to the aligned tail of a rope
piece that has the next backward rope element.
- NEXT_FORWARD_UNALIGNED the data points to the unaligned start
of a rope piece that has the next forward rope element.
- NEXT_BACKWARD_UNALIGNED the data points to the unaligned tail
of a rope piece that has the next backward rope element.
- FREELIST this item is an element of the freelist, and the data
field points to another element.
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
- 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 latex.tex with changes to line breaking and tab
handling.}
- 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''.}
- An ``rpulse'' document style option, and ``wave'' environment,
for simple typesetting of waveforms.\footnote{Inspired by work done by
Robert French for 6.004.}
- 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.
\begin{figure}
\caption{Awk script to make ``wave'' text from simulator data files}
\begin{frepcode}{../src/awk/makewave.awk}
\end{frepcode}
\end{figure}
utility.sty --- generic useful styles including ``code''
\begin{frepcode}{utility.sty}
\end{frepcode}
rpulse.sty --- \LaTeX\/ style file for producing waveforms
\begin{frepcode}{rpulse.sty}
\end{frepcode}