% architecture.tex
% Written by Andy Goth and his merry band of hackers :^)
%
% We want a nice duplexed report format here...
\documentclass[twoside]{report}
\begin{document}
% Use \reg{name} when naming a register.  The $ is automatically added.
\newcommand{\reg}[1]{\texttt{\$#1}}
\newcommand{\blank}{%
	\rule{0.3ex}{0.0pt}%
	\rule{0.3pt}{0.5ex}%
	\rule{1.5em}{0.3pt}%
	\rule{0.3pt}{0.5ex}%
	\rule{0.3ex}{0.0pt}%
}
%
\begin{titlepage}
\vspace*{4cm}
\centering
\rule{\textwidth}{4pt}			\\
\Huge
\sf
Architectural Design Document		\\
High Performance BCD Adder		\\
\Large
\rule{\textwidth}{4pt}			\\
CSE 3322-001				\\
Dr. Patterson				\\
\vspace{2cm}
Team 10					\\
\rule{0.5\textwidth}{1pt}		\\
Andy Goth, Jimmy Lee			\\
Jitan Patel, Christiana Faminu		\\
\vspace{4cm}
\rule{\textwidth}{4pt}			\\
May 2003
\end{titlepage}
%
%\tableofcontents
%\listoffigures
%
\chapter{Overview} % ==========================================================
%
\section{Introduction} % ------------------------------------------------------
%
This document describes the architecture of a machine designed explicitly for
the purpose of efficiently adding pairs of arbitrarily-sized positive integers.
It also explains how the adder program works and how to use it effectively.
%
\section{Basic Organization} % ------------------------------------------------
%
This machine uses elements of the RISC design philosophy plus additional
registers and instructions as appropriate to aid in summation of BCD values.
%
\subsection{Components}
%
The machine consists of an instruction set, two register sets, one
pseudoregister set, and a Von Neumann-style random-access memory.
%
\subsection{Word Size}
%
The machine's word size is 32 bits, and, in keeping with RISC design goals, the
sixteen normal registers, the instructions, and the individual memory elements
are each one word wide.
%
\subsection{Register Sets}
%
In contrast with RISC, there exists a second register set consisting of sixteen
four-bit registers each capable of storing a BCD digit in the range 0--9.
Furthermore, there is a pseudoregister set whose purpose is to group BCD
registers.
%
\subsection{Memory}
%
Memory is word-addressable, and it is impossible (also unnecessary) to directly
read or write individual bits or bytes or to make unaligned memory accesses.
Both code and data are stored in the same memory.  The machine is able to
separately address 65,536 words of memory, and addresses outside that range wrap
around.

Since the same memory is used to store data, it is possible for a program to
modify itself.  Note that it is possible for a program to accidentally allow
the machine to start executing ``garbage'' data or uninitialized memory, so
caution must be exercised.
%
\section{Implementation} % ----------------------------------------------------
%
The architecture is currently implemented as an assembler and a virtual machine
running on a host computer system.  The assembler translates assembly language
into the machine's native bytecode, and the virtual machine loads the
assembler's output as a memory image and executes instructions one-by-one.

Also included in the package containing the assembler and virtual machine is
a program to get numbers from the user, add them, and display the sum.

See the assembler, virtual machine, and adder chapters for more details.
%
\section{Data Types} % --------------------------------------------------------
%
The machine supports three basic data types: \emph{binary}, \emph{BCD}, and
\emph{ASCII}.  It has instructions for reading, manipulating, and writing
values of these types.
%
\subsection{Binary}
%
The \emph{binary} type is most common in this architecture.  Binary values are
encoded using the standard base-two place value scheme, with the least
significant bit numbered 0.
%
\subsubsection{Binary words}
%
\emph{Binary words} comprise the standard integer type.  Binary words are
always unsigned numbers in the range 0--4,294,967,295.  A binary word can be
stored in a memory address or in a normal register.

Binary words are read from or written to registers or memory by all instructions
except \texttt{badd} and \texttt{baddi}.
%
\subsubsection{Boolean words}
%
\emph{Boolean words} are a special case of binary words for which a literal
value of \texttt{0x00000000} is defined to be \texttt{false} and all other
values are considered \texttt{true}.  (By convention, whenever an expression or
instruction sets a booolean to \texttt{true}, it sets it to
\texttt{0x00000001}.)

One example of a boolean word is the \reg{cf} register which is used to track
the carry-out status of the most recent \texttt{badd} or \texttt{baddi}
operation.

Boolean words, specifically the carry flag, are used by the \texttt{disp},
\texttt{badd}, and \texttt{baddi} instructions.
%
\subsubsection{Immediate values}
%
\emph{Immediate values} are used as static parameters to instructions.
In this instruction set, immediate values are always unsigned and are four or
sixteen bits in width.  Four-bit immediates are in the rage 0--15, and
sixteen-bit immediates are 0--65,535.

Immediate values are primarily used as memory addresses.  Depending on the
instruction, the value may represent an absolute address, a based-register
address, or a mathematical constant.

Immediate values are used by all instructions except \texttt{badd},
\texttt{add}, and \texttt{min}.  OF these instructions, all use eight-bit
immediates except \texttt{baddi} and \texttt{beqi}, each of which use both a
four-bit immediate an eight-bit immediate.
%
\subsection{Binary-Coded Decimal (BCD)}
%
The main purpose of this architecture is to add \emph{binary-coded decimal}
values; therefore it has extensive BCD support.  BCD values are encoded using
groups of four bits to represent individual digits in the range 0--9.  Because
this architecture is only designed for BCD addition, not subtraction or other
operations, it always treats BCD numbers as unsigned.
%
\subsubsection{BCD digits}
%
\emph{BCD digits} are BCD values in the range 0--9.  A single BCD digit can be
stored in a BCD register (\reg{u7}--\reg{u0}, \reg{v7}--\reg{v0}), encoded in an
ASCII array (see below), or packed as an invididual nibble in a larger BCD
number in memory.

BCD digits are used by the \texttt{badd} and \texttt{baddi} instructions.
%
\subsubsection{BCD halfwords}
%
\emph{BCD halfwords} are groups of four BCD digits.  A BCD halfword is an
unsigned value in the range 0--9,999.  BCD halfwords can be stored in the BCD
pseudoregisters \reg{uh}, \reg{ul}, \reg{vh}, or \reg{vl}, or are packed into
BCD arrays in memory.

BCD halfwords are used by the \texttt{la} instruction.
%
\subsubsection{BCD words}
%
\emph{BCD words} are groups of eight BCD digits.  A BCD word is an unsigned
value in the range 0--99,999,999.  BCD words can be stored as \reg{u} or
\reg{v}, or are part of BCD arrays in memory.

BCD words are used by the \texttt{lb} and \texttt{sb} instructions.
%
\subsubsection{BCD arrays}
%
\emph{BCD arrays} are arbitrarily-sized unsigned values, although in the
addition program they are limited to 128 digits plus a possible carry.
Therefore the remainder of this document describes them as such.

BCD arrays are stored in fixed 16-word buffers capable of storing up to 128 BCD
digits.  The least-significant BCD word is stored at the \emph{lowest} memory
address.  There are three separate BCD arrays (named \texttt{x}, \texttt{y},
and \texttt{z}), and their widths are stored in registers \reg{xw}, \reg{yw},
and \reg{zw}.  The width values are required because zero-padding is guaranteed
only within the most-significant word of the BCD array, and beyond that data
remains uninitialized for the sake of efficiency.

The carry flag register (\reg{cf}) is recognized by the \texttt{disp}
instruction to represent the 129th digit of the BCD array to display.  If
\reg{cf} is \texttt{true}, a leading `\texttt{1}' is prepended to the BCD
array.  However, this extra digit cannot (easily) be used as part of any
calculations, so it is not possible to use a 129-digit BCD array as an input to
the add function.

BCD arrays are used by the \texttt{disp} instruction.
%
\subsection{ASCII}
%
Because the machine must interface with a terminal that speaks only
\emph{ASCII}, the instruction set supports converting ASCII values to BCD so
that they may be processed.  As far as the machine is concerned, an ASCII digit
is a BCD digit using an eight-bit encoding.  To determine the value of each
digit (byte), the machine subtracts 48 (the ASCII code for `\texttt{0}').  

\begin{table}[htp]
\caption{ASCII\ $\Leftrightarrow$\ BCD Conversion}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|l|}
\cline{1-3}\cline{5-7}
\multicolumn{2}{|c|}{ASCII} & BCD   & & \multicolumn{2}{|c|}{ASCII} & BCD   \\
\cline{1-2}\cline{5-6}
Dec         & Hex           & Value & & Dec & Hex                   & Value \\
\cline{1-3}\cline{5-7}
\texttt{48} & \texttt{0x30} & 0     & & \texttt{53} & \texttt{0x35} & 5     \\
\texttt{49} & \texttt{0x31} & 1     & & \texttt{54} & \texttt{0x36} & 6     \\
\texttt{50} & \texttt{0x32} & 2     & & \texttt{55} & \texttt{0x37} & 7     \\
\texttt{51} & \texttt{0x33} & 3     & & \texttt{56} & \texttt{0x38} & 8     \\
\texttt{52} & \texttt{0x34} & 4     & & \texttt{57} & \texttt{0x39} & 9     \\
\cline{1-3}\cline{5-7}
\end{tabular}
\end{center}
\end{table}
%
\subsubsection{ASCII words}
%
\emph{ASCII words} are treated as 32-bit unpacked BCD values.  One digit is
stored in each eight-bit byte (character) of the ASCII word, so the range is
0--9,999.  The value stored in bits 7--0 (the bottom byte) is considered to be
the least-significant digit.

ASCII words are used by the \texttt{la} instruction.
%
\subsubsection{ASCII arrays}
%
\emph{ASCII arrays} are arbitrarily-sized unsigned numbers, but since the
\texttt{read} instruction supports a maximum of 128 digits, this document will
deal only with 128-digit ASCII arrays.

Like the BCD array convention, ASCII arrays are stored in fixed buffers capable
of storing up to 128 digits.  However, since an ASCII digit is eight bits
whereas a BCD digit is only four, an ASCII array is 32 words wide as opposed to
16 for BCD.  Also unlike the BCD array convention, the least-significant ASCII
word is stored at the \emph{highest} memory address.  Furthermore, ASCII arrays
are completely zero-padded, where BCD arrays are zero-padded only to fill the
most-significant word.

ASCII arrays are used by the \texttt{read} instruction.
%
\begin{table}[htp]
\caption{BCD Arrays vs. ASCII Arrays}
\begin{tabular}{|l|l|l|}
\hline
Attribute	& BCD Arrays			& ASCII Arrays		\\
\hline
Digits in array	& 128 digits			& 128 digits		\\
Digit width	& Four bits			& Eight bits		\\
Digit packing	& Eight digits per word		& Four digits per word	\\
Digit count	& Stored in register		& Stored in register	\\
Array size	& 16 words			& 32 words		\\
Array name(s)	& \texttt{x}, \texttt{y}, \texttt{z}	& Unnamed	\\
Purpose		& Mathematics, storage, display	& Temporary input buffer\\
Least-sig. word	& Lowest memory address		& Highest memory address\\
Zero padding	& Fill most-significant word	& Fill array		\\
Registers	& \reg{xw}, \reg{yw}, \reg{zw}, \reg{cf}& None		\\
Instructions	& Displayed by \texttt{disp}	& Generated by \texttt{read} \\
\hline
ASCII $\Rightarrow$ BCD	& \multicolumn{2}{|l|}{%
\begin{tabular}{@{}p{0.75\textwidth}@{}}
In a loop, use \texttt{la} two times to load two ASCII words into
\reg{u7}--\reg{u0} or similar and write them as one BCD word with \texttt{sb}.
Repeat for every eight ASCII words in the ASCII array.
\end{tabular}}								\\ \hline
\end{tabular}
\end{table}
%
\begin{table}[htp]
\caption{Data Types}
\begin{tabular}{@{\extracolsep{\fill}}|l|l|l|l|}
\hline
Type		& Range(s)	& Width & Location(s)	\\
\hline
\hline
%
Binary word						& % Type
\begin{tabular}{@{}ll@{}}
0--4,294,967,295
\end{tabular}						& % Range
\begin{tabular}{@{}l@{}}
32 bits						\\
(1 word)
\end{tabular}						& % Width
\begin{tabular}{@{$\bullet$\ }l@{}}
Normal register					\\
Memory address
\end{tabular}						\\% Location
\hline
%
Boolean word						& % Type
\begin{tabular}{@{}l@{$\ =\ $}l@{}}
\texttt{false}	& \texttt{0x00000000}		\\
\texttt{true}	& all else
\end{tabular}						& % Range
\begin{tabular}{@{}l@{}}
32 bits						\\
(1 word)
\end{tabular}						& % Width
\begin{tabular}{@{$\bullet$\ }l@{}}
Normal register					\\
Memory address
\end{tabular}						\\% Location
\hline
%
Immediate						& % Type
\begin{tabular}{@{}ll@{}}
Four-bit:	& 0--15				\\
Sixteen-bit:	& 0--65,535
\end{tabular}						& % Range
\begin{tabular}{@{}l@{}}
4 bits or					\\
16 bits
\end{tabular}						& % Width
\begin{tabular}{@{$\bullet$\ }l@{}}
Instruction word
\end{tabular}						\\% Location
\hline
\hline
%
BCD digit						& % Type
0--9							& % Range
\begin{tabular}{@{}l@{}}
4 bits						\\
($\frac{1}{8}$\ word)
\end{tabular}						& % Width
\begin{tabular}{@{$\bullet$\ }l@{}}
\reg{u7}--\reg{u0}, \reg{v7}--\reg{v0}		\\
Larger BCD value
\end{tabular}						\\% Location
\hline
%
BCD halfword						& % Type
0--9,999						& % Range
\begin{tabular}{@{}l@{}}
16 bits						\\
($\frac{1}{2}$\ word)
\end{tabular}						& % Width
\begin{tabular}{@{$\bullet$\ }l@{}}
\reg{uh}, \reg{ul}, \reg{vh}, \reg{vl}		\\
Larger BCD value
\end{tabular}						\\% Location
\hline
%
BCD word						& % Type
0--99,999,999						& % Range
\begin{tabular}{@{}l@{}}
32 bits						\\
(1 word)
\end{tabular}						& % Width
\begin{tabular}{@{$\bullet$\ }l@{}}
\reg{u}, \reg{v}					\\
Larger BCD value
\end{tabular}						\\% Location
\hline
%
BCD array						& % Type
\begin{tabular}{@{}ll@{}}
Normal:		& 0--$(10^{128} - 1)$		\\
With \reg{cf}:	& 0--$\big(2(10^{128}) - 1\big)$\\
\end{tabular}						& % Range
\begin{tabular}{@{}l@{}}
16 words					\\
\rule{1em}{0em}plus				\\
1--2 regs					\\
\end{tabular}						& % Width
\begin{tabular}{@{$\bullet$\ }l@{}}
Digits: \texttt{x}, \texttt{y}, \texttt{z}	\\
Width: \reg{xw}, \reg{yw}, \reg{zw}		\\
Leading digit: \reg{cf}
\end{tabular}						\\% Location
\hline
\hline
%
ASCII word						& % Type
0--9,999						& % Range
\begin{tabular}{@{}l@{}}
32 bits						\\
(1 word)
\end{tabular}						& % Width
\begin{tabular}{@{$\bullet$\ }l@{}}
Memory word					\\
$\Rightarrow$\ \reg{uh}, \reg{ul}, \reg{vh}, \reg{vl}
\end{tabular}						\\% Location
\hline
%
ASCII array						& % Type
0--$(10^{128} - 1)$					& % Range
32 words						& % Width
\begin{tabular}{@{$\bullet$\ }l@{}}
Memory buffer					\\
$\Rightarrow$\ \texttt{x} and \reg{xw}		\\
$\Rightarrow$\ \texttt{y} and \reg{yw}		\\
$\Rightarrow$\ \texttt{z} and \reg{zw}
\end{tabular}						\\% Location
\hline
\end{tabular}
\end{table}
%
\chapter{The Assembler} % =====================================================
%
The assembler forms one half of the implementation of this architecture.  It is
responsible for reading a preprocessed assembly-language program on input and
producing a memory image and label map on output suitable for execution by the
virtual machine.
%
\section{Conventions} % -------------------------------------------------------
%
\subsection{Whitespace}
%
\emph{Whitespace} is spaces, horizontal tabs, vertical tabs, newlines, and page
breaks.  Whitespace is used as a general delimeter.
%
\subsection{Comments}
%
\emph{Comments} are explanatory blocks of text ignored by the assembler.
Comments begin with the `\texttt{\#}' character and extend to the end of the
line.  Whenever a `\texttt{\#}' is encountered (except as part of a character
literal), the assembler simply stops processing the current line and skips to
the next one.  Basically, a comment is handled the same as a newline character.
%
\subsection{Labels}
%
\emph{Labels} associate names with memory addresses.

To define a label, type a name not already in use followed by a colon
(`\texttt{:}').  Label names consist of upper- and lowercase letters
(`\texttt{A}'--`\texttt{Z}', `\texttt{a}'--`\texttt{z}'), underscores and
periods (`\texttt{\_}', `\texttt{.}'), and numbers
(`\texttt{0}'--`\texttt{9}').  A label's name may not begin with a number.

Each label has a value equal to the memory address it indicates.  To use the
label's value in a program, simply type an at-sign ('\texttt{@}') and then
label's name.  Since a label's value is just an integer at heart, label names
may be used as part of more complicated expression evaluation.  For example, the
distance in words between two labels can be determined by typing
`\texttt{@label2 - @label1}'.

There is no requirement to define a label before using it.

Certain special label names are used to indicate to the virtual machine what
initial values to set each of the registers to at boot time.  The virtual
machine, as is explained below, reads the first word following the label and
uses it to initialize the register or registers indicated by the name of the
label.

The \texttt{.nreg} label is used to set a default value for all normal
registers.  If unspecified, the default value is \texttt{0xdeadbeef}, which
aids in debugging because it quickly indicates which registers are unused.

The \texttt{.breg} label is like \texttt{.nreg} except that it sets the default
for BCD registers.  Also, only the bottom four bits of the first word following
the label are used, as is the case with the individual BCD register initializer
labels.

Any register (aside from the pseudoregisters) can be individually initialized
by creating a label whose name is a period followed by the register name; then
the label is followed by a word whose value is used to initialize the register.

The following code will set up the registers to have some sensible defaults:

\begin{verbatim}
.nreg: 0xdeadbeef;                  # Default to 0xdeadbeef, which is
                                    # easily spotted in a debugger
                                    # environment
.breg: 0x0000000f;                  # Default to 0xf, an invalid
                                    # value, to flush out inadvertent
                                    # uses of uninitialized data
.zero: 0x00000000;                  # $zero should always be 0
  .xw: 0x00000000;                  # BCD x = 0
  .yw: 0x00000000;                  # BCD y = 0
  .c0: addi($r1, $zero, @label);    # Example instruction
  .cf: 0x00000000;                  # Clear carry
  .pc: @entry;                      # Start program at entry

entry:                              # Entry point of program
\end{verbatim}
%
\subsection{Integer Constants}
%
\emph{Integer constants} are values used as part of expression evaluation or
passed as operands to instructions.

Integer constants can be typed using one of five formats: \emph{decimal},
\emph{binary}, \emph{octal}, \emph{hexadecimal}, and \emph{character}.  Prefixes
and hexadecimal values are case-insensitive.  Character literals may make use
of the special backslash escape sequences described in backslash escape
sequence table (below).

In the integer constants table, all the example constant values evaluate to the
same value, decimal 42.

\begin{table}[htp]
\caption{Integer Constants}
\begin{center}
\begin{tabular}{|l|l|l|l|l|}
\hline
Format & Base & Allowed Digits & Syntax & Example \\
\hline
Decimal								& % Format
10								& % Base
`\texttt{0}'--`\texttt{9}'					& % Digits
\blank								& % Syntax
\texttt{42} 							\\% Example
%
Binary								& % Format
2								& % Base
`\texttt{0}'--`\texttt{1}'					& % Digits
\texttt{0b}\blank						& % Syntax
\texttt{0b00101010}						\\% Example
%
Octal								& % Format
8								& % Base
`\texttt{0}'--`\texttt{7}'					& % Digits
\texttt{0}\blank						& % Syntax
\texttt{052} 							\\% Example
%
Hexadecimal							& % Format
16								& % Base
`\texttt{0}'--`\texttt{9}', `\texttt{a}'--`\texttt{f}'		& % Digits
\texttt{0x}\blank						& % Syntax
\texttt{0x2a} 							\\% Example
%
Character							& % Format
256								& % Base
`\texttt{$\backslash$x00}'--`\texttt{$\backslash$xff}'		& % Digits
\texttt{'}\blank\texttt{'}					& % Syntax
\texttt{'*'}							\\% Example
\hline
\end{tabular}
\end{center}
\end{table}
%
\begin{table}[htp]
\caption{Backslash Escape Sequences}
\begin{center}
\begin{tabular}{|@{$~\backslash$}l|l|l|l|}
\hline
\multicolumn{1}{|l|}{Code}%
	& \multicolumn{2}{|c|}{Value}	& Description			\\
\cline{2-3}
\multicolumn{1}{|l|}{}%
	& Dec		& Hex		&				\\
\hline
\blank	& ---	       	& ---		& Byte with octal value \blank	\\
x\blank	& ---		& ---	& Byte with hexadecimal value \blank	\\
\texttt{a}& \texttt{7} 	& \texttt{0x07}	& Alert (bell)			\\
\texttt{b}& \texttt{8} 	& \texttt{0x08}	& Backspace			\\
\texttt{e}& \texttt{27}	& \texttt{0x1b}	& Escape character		\\
\texttt{f}& \texttt{12} & \texttt{0x0c}	& Form feed			\\
\texttt{n}& \texttt{10} & \texttt{0x0a}	& Newline character		\\
\texttt{r}& \texttt{13} & \texttt{0x0d}	& Carriage return		\\
\texttt{t}& \texttt{9}  & \texttt{0x09}	& Horizontal tab		\\
\texttt{v}& \texttt{11} & \texttt{0x0b}	& Vertical tab			\\
$\backslash$&\texttt{92}& \texttt{0x5c}	& Backslash			\\
\texttt{'}& \texttt{39} & \texttt{0x27}	& Single quote			\\
\hline
\end{tabular}
\end{center}
\end{table}
%
\subsection{Expressions}
%
The syntax for expressions is primarily borrowed from C.  Expressions are
terminated with semicolons (`\texttt{;}') and can be separated with commas
(`\texttt{,}').  See table for supported operators.

\begin{table}[tp]
\caption{Expression Evaluation and Operator Precedence}
\begin{center}
\small
\begin{tabular}{|l|ll|l|}
\hline
Expression & Evaluates To & \multicolumn{2}{r|}{Associativity}		\\
\hline
\multicolumn{4}{|c|}{(Highest Precedence)}				\\
\hline
\texttt{(a)}								&
\multicolumn{2}{|l|}{%
\texttt{a} (overrides operator precedence)%
}									& LR \\
\texttt{const}								&
\multicolumn{2}{|l|}{%
Constant integer value
}									& LR \\
\texttt{@label}								&
\multicolumn{2}{|l|}{%
Address associated with the given label
}									& LR \\
\texttt{\$reg}								&
\multicolumn{2}{|l|}{%
Encoding of the given register
}									& LR \\
\texttt{insn(arg1, arg2, arg3)}						&
\multicolumn{2}{|l|}{%
Binary representation of the given assembly instruction
}									& LR \\
\hline
\texttt{-a}								&
\multicolumn{2}{|l|}{%
Two's-complement of \texttt{a}
}									& RL \\
\texttt{\~{}a}								&
\multicolumn{2}{|l|}{%
One's-complement of \texttt{a}
}									& RL \\
\texttt{!a}								&
\multicolumn{2}{|l|}{%
Logical inverse of \texttt{a}
}									& RL \\
\hline
\texttt{a * b}								&
\multicolumn{2}{|l|}{%
Product of \texttt{a} and \texttt{b}
}									& LR \\
\texttt{a / b}								&
\multicolumn{2}{|l|}{%
Quotient of \texttt{a} divided by \texttt{b}
}									& LR \\
\texttt{a \% b}								&
\multicolumn{2}{|l|}{%
Remainder of \texttt{a} divided by \texttt{b}
}									& LR \\
\hline
\texttt{a + b}								&
\multicolumn{2}{|l|}{%
Sum of \texttt{a} and \texttt{b}
}									& LR \\
\texttt{a - b}								&
\multicolumn{2}{|l|}{%
Sum of \texttt{a} and $-$\texttt{b}
}									& LR \\
\hline
\texttt{a << b}								&
\multicolumn{2}{|l|}{%
Product of \texttt{a} and $2^\texttt{b}$
}									& LR \\
\texttt{a >> b}								&
\multicolumn{2}{|l|}{%
Quotient of \texttt{a} divided by $2^\texttt{b}$
}									& LR \\
\hline
\texttt{a < b}								&
\multicolumn{2}{|l|}{%
\texttt{true} if \texttt{a} is less than \texttt{b}
}									& LR \\
\texttt{a <= b}								&
\multicolumn{2}{|l|}{%
\texttt{true} if \texttt{a} is at most \texttt{b}
}									& LR \\
\texttt{a > b}								&
\multicolumn{2}{|l|}{%
\texttt{true} if \texttt{a} is greater than \texttt{b}
}									& LR \\
\texttt{a >= b}								&
\multicolumn{2}{|l|}{%
\texttt{true} if \texttt{a} is at least \texttt{b}
}									& LR \\
\hline
\texttt{a == b}								&
\multicolumn{2}{|l|}{%
\texttt{true} if \texttt{a} is equal to \texttt{b}
}									& LR \\
\texttt{a != b}								&
\multicolumn{2}{|l|}{%
\texttt{true} if \texttt{a} is not equal to \texttt{b}
}									& LR \\
\hline
\texttt{a \& b}								&
\multicolumn{2}{|l|}{%
Bitwise \texttt{and} of \texttt{a} and \texttt{b}
}									& LR \\
\hline
\texttt{a \^{} b}							&
\multicolumn{2}{|l|}{%
Bitwise \texttt{xor} of \texttt{a} and \texttt{b}
}									& LR \\
\hline
\texttt{a | b}								&
\multicolumn{2}{|l|}{%
Bitwise \texttt{or} of \texttt{a} and \texttt{b}
}									& LR \\
\hline
\texttt{a \&\& b}							&
\multicolumn{2}{|l|}{%
If \texttt{a}, then \texttt{b}, else \texttt{false}
}									& LR \\
\hline
\texttt{a || b}								&
\multicolumn{2}{|l|}{%
If \texttt{a}, then \texttt{true}, else \texttt{b}
}									& LR \\
\hline
\texttt{a ?~b :~c}							&
\multicolumn{2}{|l|}{%
If \texttt{a}, then \texttt{b}, else \texttt{c}
}									& RL \\
\hline
\multicolumn{4}{|c|}{(Lowest Precedence)}				\\
\hline
\end{tabular}
\normalsize
\end{center}
\end{table}
%
\subsection{Instructions}
%
\emph{Machine instructions} appear in assembly language programs as mnemonics
followed by three operands.  The operands appear in a list surrounded by
parentheses and separated by commas (whitespace optional).  See the instruction
set chapter for details.
%
\subsection{Registers}
%
\emph{Register} operands are mnemonic codes preceded by a dollar sign
(`\texttt{\$}').  As far as the assembler is concerned, a register is simply
another form of ``spelling'' integer constant, which is to say, whenever a
register appears in the assembly source, the assembler translates it to an
integer value equal to its encoding in the compiled bytecode.

See the register set chapter for details.
%
\subsection{Immediates}
%
\emph{Immediate operands} are unsigned integer values given as operands to
instructions.  Immediate values may be typed literally or can be the product of
expression evaluation.

Note that since instructions and registers evaluate to integers, they may be
used as immediate values.  By the same token, immediate values may be entered
directly as if they were instructions; this is useful for filling memory arrays
with precalculated values.
%
\section{Programs} % ----------------------------------------------------------
%
Simply put, an assembly program is a list of labels and expressions.
%
\subsection{Definitions}
%
As written above, labels are colon-terminated (`:').  Expressions are
semicolon-terminated (`;').  As stated above, expressions can be integer
constants, assembly instructions, register names, `@'-preced label names, or
any combination thereof joined by the operators listed in the expression
evaluation table.

Naturally, comments are ignored by the assembler and have no effect whatsoever
on the output machine code and label map.
%
\subsection{Pitfalls}
%
Unfortunately, this simplistic view leads to a gross lack in error-checking by
the assembler.  The only things it checks for, aside from basic syntax, are
that every label used in the program is defined exactly once and that every
instruction name is valid.  Therefore, the following program will be accepted
by the assembler:

\begin{verbatim}
top:   0x12345678;
       addi(5, 5, 5);
       $u;
       cshri(@bottom, $u5, $cf);
bottom:
\end{verbatim}

Given this input, the assembler will generate correct image and map files, but
the virtual machine will choke on them immediately for two reasons:
\begin{itemize}
\item \texttt{0x12345678} is not a valid instruction in the current instruction
set.  Upon seeing this value used as an instruction, the virtual machine will
terminate the program with an error message.
\item As discussed in the label section, \reg{pc}, by default, is set to
\texttt{0xdeadbeef}, and the above program does not correctly override this
value.  Therefore, the virtual machine will most likely start execution in
unmapped memory and will there hit an invalid instruction.
\end{itemize}
%
\section{Preprocessing with GNU m4} % -----------------------------------------
%
The supplied adder program is written using the GNU m4 macro language.  The m4
utility reads the m4 source and translates it into assembly language ready to
be interpreterd by the assembler.  This is used to implement pseudoinstructions
and assembler directives, among other things.

By way of example, GNU m4 is used to convert m4 source into processed output as
follows:

\begin{verbatim}
[andy@chainsaw|cse3322]$ m4 adder.m4 > adder.asm
\end{verbatim}

See the GNU m4 manual for more information.
%
\section{Execution} % ---------------------------------------------------------
%
The assembler is executed by invoking the ``asm'' program (it must have this
name in order to work properly) with three filename arguments: the source
assembly and the image and map files to create.

\begin{verbatim}
[andy@chainsaw|cse3322]$ ./asm adder.asm adder.img adder.map
\end{verbatim}

If all goes well, the assembler will finish momentarily without printing
anything to the screen.  But if there are syntax errors or other problems, such
as file-not-found or out-of-memory, diagnostics are emitted so the user can
correct the problem(s).
%
\section{Output} % ------------------------------------------------------------
%
The assembler produces two output files: the memory image and the label map.
%
\subsection{Memory Image}
%
The memory image is an unformatted binary file containing the direct
translation of each of the expressions (instructions, etc.) in the assembly
source file.  To save disk space, its length is limited to the number of words
actually defined in the assembly source, with the assumption that the virtual
machine will pad the remainder of memory to fill out the 65,536-word address
space.

Each word in the memory image is stored as a little-endian four-byte value, as
demonstrated by the following:

\begin{verbatim}
[andy@chainsaw|cse3322]$ echo "0x12345678;"   >  code.asm
[andy@chainsaw|cse3322]$ echo "0xdeadbeef;"   >> code.asm
[andy@chainsaw|cse3322]$ echo "('A' << 24) |" >> code.asm
[andy@chainsaw|cse3322]$ echo "('n' << 16) |" >> code.asm
[andy@chainsaw|cse3322]$ echo "('d' <<  8) |" >> code.asm
[andy@chainsaw|cse3322]$ echo "('y' <<  0);"  >> code.asm
[andy@chainsaw|cse3322]$ ./asm code.asm code.img code.map
[andy@chainsaw|cse3322]$ xxd code.img
00000000: 1234 5678 dead beef 416e 6479  .4Vx....Andy
\end{verbatim}
%
\subsection{Label Map}
%
The label map is a plain text file matching the label names found in the
assembly source file with their addresses.  Each line contains first the label
name followed by whitespace and then the address as a sixteen-bit unsigned
hexadecimal integer value.

\begin{verbatim}
[andy@chainsaw|cse3322]$ echo "label1:"  >  code.asm
[andy@chainsaw|cse3322]$ echo "0;1;2;3;" >> code.asm
[andy@chainsaw|cse3322]$ echo "label2:"  >> code.asm
[andy@chainsaw|cse3322]$ echo "label3:"  >> code.asm
[andy@chainsaw|cse3322]$ echo "4;5;"     >> code.asm
[andy@chainsaw|cse3322]$ echo "label4:"  >> code.asm
[andy@chainsaw|cse3322]$ ./asm code.asm code.img code.map
[andy@chainsaw|cse3322]$ cat code.map
label1               0000
label2               0004
label3               0004
label4               0006
\end{verbatim}

It is strongly recommended that all programs have a label after all
instructions and other word values.  The address of this final label equals the
number of words in the program.  The virtual machine needs this label to
determine where the final code block ends.
%
\chapter{The Virtual Machine} % ===============================================
%
The virtual machine interactively simulates the execution of the processor.  It
also provides the link between the program and user: the prompt.

The virtual uses a simple VT100-compatible command-line interface.  As such,
displaying it in an old version of MS Telnet will prove visually disastrous,
and using a monochrome telnet/ssh client such as Hummingbird will cause most of
the display formatting to be lost, rendering the display more difficult to
read.  Instead use a suitable terminal emulator such as the Linux console, a
color xterm, the Mac OS X terminal application, or PuTTY for MS Windows.
%
\section{Overview} % ----------------------------------------------------------
%
The virtual machine loads a memory image produced by the assembler and executes
it.  It also loads a label map to (1) read the initial values for the
registers, and (2) augment the memory dump display.

The program communicates with the virtual machine and therefore the user via
the \texttt{read} and \texttt{disp} instructions.  When the \texttt{read}
instruction executes, the program halts long enough for the user to give input,
which can be instructions to the virtual machine rather than to the program.

See the instruction set chapter for details, particularly the section on
\texttt{read}.
%
\chapter{Register Sets} % =====================================================
%
\section{Overview} % ----------------------------------------------------------
%
This architecture has three \emph{register sets}, which are collections of
little bits of memory for use in calculations and other operations.  The design
of this machine is such that only loading, storing, and jumping/branching
directly involve memory; therefore there must be a rich register set to make it
possible to perform all the calculations necessary with a minimum of memory
accesses.
%
\section{Normal Register Set} % -----------------------------------------------
%
The \emph{normal register set} is used by most of the instructions in the
machine.  all the registers with the exception of \reg{zero} are fully
general-purpose (\reg{zero} is immutable).

The purpose of each of the different registers is defined by convention but can
be ignored if a good reason exists.

\reg{c0} and \reg{c1} are used for storing executable code, useful for
self-modifying programs.  These registers can be set through immediate loads
and through reading the program's own code.

\reg{xw}, \reg{yw}, and \reg{zw} are for tracking the number of significant
words in three different BCD values, \texttt{x}, \texttt{y}, and \texttt{z},
which are stored in arbitrarily-sized regions of memory.

\reg{r0}--\reg{r7} have no particular meaning except as defined by programs
using them.  They can be used to store numerical values, Boolean truth values,
bitfields, memory addresses---anything of use.

\reg{cf} can be used like any other normal register.  It has two special
characteristics:
\begin{itemize}
\item Its value is modified by the \texttt{badd} instruction to reflect its
carry-out status.
\item The \texttt{disp} instruction interprets its value to determine whether
or not to display a leading \texttt{1}.
\end{itemize}

\reg{pc} is used to indicate the address in memory of the next instruction to
execute.

\begin{table}[tp]
\caption{Normal Register Set}
\begin{center}
\begin{tabular}{|l|r|r|l|}
\hline
Register	& \multicolumn{2}{c|}{Encoding}	& \\ \cline{2-3}
Name		& Dec		& Hex		& Description \\
\hline
\reg{zero}	& \texttt{0}	& \texttt{0x0}	&
Literal value \texttt{0x00000000}		\\
\reg{c0}	& \texttt{1}	& \texttt{0x1}	&
Compiled instruction register \texttt{0}	\\
\reg{c1}	& \texttt{2}	& \texttt{0x2}	&
Compiled instruction register \texttt{1}	\\
\reg{r0}	& \texttt{3}	& \texttt{0x3}	&
General-purpose register \texttt{0}		\\
\reg{r1}	& \texttt{4}	& \texttt{0x4}	&
General-purpose register \texttt{1}		\\
\reg{r2}	& \texttt{5}	& \texttt{0x5}	&
General-purpose register \texttt{2}		\\
\reg{r3}	& \texttt{6}	& \texttt{0x6}	&
General-purpose register \texttt{3}		\\
\reg{r4}	& \texttt{7}	& \texttt{0x7}	&
General-purpose register \texttt{4}		\\
\reg{r5}	& \texttt{8}	& \texttt{0x8}	&
General-purpose register \texttt{5}		\\
\reg{r6}	& \texttt{9}	& \texttt{0x9}	&
General-purpose register \texttt{6}		\\
\reg{r7}	& \texttt{10}	& \texttt{0xa}	&
General-purpose register \texttt{7}		\\
\reg{xw}	& \texttt{11}	& \texttt{0xb}	&
Word count for BCD value \texttt{x}		\\
\reg{yw}	& \texttt{12}	& \texttt{0xc}	&
Word count for BCD value \texttt{y}		\\
\reg{zw}	& \texttt{13}	& \texttt{0xd}	&
Word count for BCD value \texttt{z}		\\
\reg{cf}	& \texttt{14}	& \texttt{0xe}	&
Carry flag					\\
\reg{pc}	& \texttt{15}	& \texttt{0xf}	&
Program counter					\\
\hline
\end{tabular}
\end{center}
\end{table}
%
\section{BCD Pseudoregister Set} % --------------------------------------------
%
The \emph{BCD pseudoregister set} is so named because each pseudoregister is
only a means of referring to groups of actual one-digit BCD registers.  The BCD
pseudoregister set is used by certain instructions capable of working with
multiple BCD digits at a time.  These pseudoregisters are used to indicate
which digits to operate on.

The \reg{uh}, \reg{ul}, \reg{vh}, and \reg{vl} pseudoregisters each indicate a
group of four BCD digits, as shown in the BCD register and pseudoregister set
tables.  \reg{u} and \reg{v} refer to groups of eight BCD digits.

\begin{table}[tp]
\caption{BCD Pseudoregister Set}
\begin{center}
\begin{tabular}{|l|r|r|l|l|}
\hline
%
Register &
\multicolumn{2}{c|}{Encoding}       & Pseudoregister & Associated BCD \\
\cline{2-3}
Name     & Dec        & Hex          & Type \& Width & Digit Registers \\
%
\hline
%
\reg{u}  & \texttt{0} & \texttt{0x0} & BCD Word     & \reg{u7}--\reg{u0} \\
\reg{uh} & \texttt{1} & \texttt{0x1} & BCD Halfword & \reg{u7}--\reg{u4} \\
\reg{ul} & \texttt{2} & \texttt{0x2} & BCD Halfword & \reg{u3}--\reg{u0} \\
\reg{v}  & \texttt{3} & \texttt{0x3} & BCD Word     & \reg{v7}--\reg{v0} \\
\reg{vh} & \texttt{4} & \texttt{0x4} & BCD Halfword & \reg{v7}--\reg{v4} \\
\reg{vl} & \texttt{5} & \texttt{0x5} & BCD Halfword & \reg{v3}--\reg{v0} \\
%
\hline
\end{tabular}
\end{center}
\end{table}
%
\section{BCD Register Set} % --------------------------------------------------
%
The \emph{BCD register set} is used by special BCD load/store and mathematics
instructions.  Each BCD register stores digits in the range 0--9.

There are two sets of BCD registers: \reg{u} and \reg{v}, not to be confused
with the in-memory BCD arrays \texttt{x}, \texttt{y}, and \texttt{z}.

The BCD pseudoregisters \reg{u} and \reg{v} each comprise eight BCD digits,
which can be addressed all at once (``BCD words''), in groups of four (``BCD
halfwords'') using the BCD pseudoregisters \reg{uh}, \reg{ul}, \reg{vh},
\reg{vl}, or individually (``BCD digits'') using the BCD registers presented in
this section.

\begin{table}[tp]
\caption{BCD Register Set}
\begin{center}
\begin{tabular}{|l|r|r|l|l|}
\hline
%
Register &
\multicolumn{2}{c|}{Encoding} &
\multicolumn{2}{c|}{Bit Position} \\
\cline{2-5}
Name	   & Dec	& Hex		& BCD Word	& BCD Halfword \\
%
\hline
%
\reg{u0} & \texttt{0}	& \texttt{0x0}	& \reg{u[0]}	& \reg{ul[0]} \\
\reg{u1} & \texttt{1}	& \texttt{0x1}	& \reg{u[1]}	& \reg{ul[1]} \\
\reg{u2} & \texttt{2}	& \texttt{0x2}	& \reg{u[2]}	& \reg{ul[2]} \\
\reg{u3} & \texttt{3}	& \texttt{0x3}	& \reg{u[3]}	& \reg{ul[3]} \\
\hline
\reg{u4} & \texttt{4}	& \texttt{0x4}	& \reg{u[4]}	& \reg{uh[0]} \\
\reg{u5} & \texttt{5}	& \texttt{0x5}	& \reg{u[5]}	& \reg{uh[1]} \\
\reg{u6} & \texttt{6}	& \texttt{0x6}	& \reg{u[6]}	& \reg{uh[2]} \\
\reg{u7} & \texttt{7}	& \texttt{0x7}	& \reg{u[7]}	& \reg{uh[3]} \\
\hline
\reg{v0} & \texttt{8}	& \texttt{0x8}	& \reg{v[0]}	& \reg{vl[0]} \\
\reg{v1} & \texttt{9}	& \texttt{0x9}	& \reg{v[1]}	& \reg{vl[1]} \\
\reg{v2} & \texttt{10}	& \texttt{0xa}	& \reg{v[2]}	& \reg{vl[2]} \\
\reg{v3} & \texttt{11}	& \texttt{0xb}	& \reg{v[3]}	& \reg{vl[3]} \\
\hline
\reg{v4} & \texttt{12}	& \texttt{0xc}	& \reg{v[4]}	& \reg{vh[0]} \\
\reg{v5} & \texttt{13}	& \texttt{0xd}	& \reg{v[5]}	& \reg{vh[1]} \\
\reg{v6} & \texttt{14}	& \texttt{0xe}	& \reg{v[6]}	& \reg{vh[2]} \\
\reg{v7} & \texttt{15}	& \texttt{0xf}	& \reg{v[7]}	& \reg{vh[3]} \\
%
\hline
\end{tabular}
\end{center}
\end{table}
%
\chapter{Instruction Set} % ===================================================
%
\section{Overview} % ----------------------------------------------------------
%
The instruction set contains a total of 19 instructions, divided into four
groups: \emph{user interface instructions}, \emph{memory instructions},
\emph{branch instructions}, and \emph{mathematical instructions}.

This architecture has an instruction set finely tuned for the task at hand,
specifically, adding large BCD numbers.  As such, some instructions may seem
eccentric, but they are in fact very useful for this particular job.
%
\subsection{Conventions}
%
\subsubsection{Register Operand Naming}
%
\reg{1} indicates the first \emph{register operand}, \reg{2} the second, and so
on.  Register operands are encoded using the tables given in the register set
chapter.
%
\subsubsection{Memory Addresses}
%
\emph{Absolute memory addresses} are named \texttt{addr}.
\emph{based-register memory addresses} are formed by adding an offset register
\reg{1} to \texttt{addr}.  See the particular instruction for details.
%
\subsubsection{Immediates}
%
\emph{Immediate values} are named \texttt{imm}.  Immediate values are always
unsigned.  The assembler automatically wraps immediate values to the correct
range.  Note that memory addresses are simply a special case of immediates.
%
\subsubsection{Encoding}
%
\emph{Instruction encoding} is given by a table following the description of
each of the instructions.  The top row of the table names the instruction and
the operands, and the remaining rows specify individual fields of the encoded
machine instruction.  The left column indicates which bits comprise the field,
and the right column lists the value that goes in the field.  A field can be
constant (to name an instruction or to add padding), a register (in which case
the register set is also given in the table), or an immediate (the table will
give the acceptable range of values).
%
\section{User Interface Instructions} % ---------------------------------------
%
\subsection{\texttt{read}: Get Command From User}
%
The \texttt{read} instruction gets commands from the user by displaying a
prompt at which the user can type.  The list of recognized commands is given in
the following table.  Additional commands for watching memory addresses and so
on will later be defined during the development of the virtual machine.

\begin{table}[htp]
\caption{\texttt{read} Commands}
\begin{center}
\begin{tabular}{|l|p{0.5\textwidth}|}
\hline
Command	& Meaning							\\
\hline
\multicolumn{2}{|c|}{Handled by program}				\\
\hline
\texttt{IN ARRAY 1 numeric-string}					&
Check validity of numeric-string; copy numeric-string to the given
address as an ASCII array; set \reg{1} to 0; set \reg{2} to the number
of digits entered; proceed to next machine instruction.			\\
\texttt{IN ARRAY 2 numeric-string}					&
Check validity of numeric-string; copy numeric-string to the given
address as an ASCII array; set \reg{1} to 1; set \reg{2} to the number
of digits entered; proceed to next machine instruction.			\\
\texttt{ADD ARRAYS}							&
Set \reg{1} to 2; proceed to next machine instruction.			\\
\hline
\multicolumn{2}{|c|}{Handled by virtual machine}			\\
\hline
\texttt{EXIT}								&
Immediately terminate program.						\\
\texttt{HELP}								&
Display usage information; get next command from user.			\\
\texttt{RUN}								&
Enable continuous run mode; get next command from user.			\\
\texttt{TRACE}								&
Enable execution trace mode; get next command from user.		\\
\texttt{REG}								&
Display all registers; get next command from user.			\\
\texttt{MEM addr}							&
Shows a block of memory starting at addr; get next command from user.	\\
(all else)								&
Print error message; get next command from user.			\\
\hline
\end{tabular}
\end{center}
\end{table}

After \texttt{read} returns, \reg{1} will contain the command code, and in the
case of \texttt{IN ARRAY}, the memory block starting at \texttt{addr} will
contain, as an ASCII array, the numeric string entered by the user following
the command name, and \reg{2} will contain the number of digits in the ASCII
array.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{read \$1, \$2, addr}}			\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{0}		& \texttt{0x00}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{addr}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{disp}: Display BCD Array}
%
The \texttt{disp} instruction displays the BCD array stored in address
\texttt{addr[\$2]}.  \reg{1} is the number of significant words in the BCD
array.  If \reg{cf} is \texttt{true}, the number displayed is prefixed with a
`\texttt{1}'.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{disp \$1, addr[\$2]}}			\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{1}		& \texttt{0x01}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{addr}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\section{Memory Instructions} % -----------------------------------------------
%
\subsection{\texttt{lw}: Load Binary Word}
%
The \texttt{lw} instruction copies the binary word at the address
\texttt{addr[\$2]} into the register \reg{1}.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{lw \$1, addr[\$2]}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{16}		& \texttt{0x10}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{addr}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{lb}: Load BCD Word}
%
The \texttt{lb} instruction reads a BCD word from the address
\texttt{addr[\$2]} into the pseudoregister \reg{1}.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{lw \$1, addr[\$2]}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{17}		& \texttt{0x11}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& \reg{u}, \reg{v}	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{addr}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{la}: Load ASCII Word}
%
The \texttt{la} instruction reads an ASCII word from the address
\texttt{addr[\$2]} into the pseudoregister \reg{1}.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{lw \$1, addr[\$2]}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{18}		& \texttt{0x12}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		&%
\reg{uh}, \reg{ul}, \reg{vh}, \reg{vl}					\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{addr}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{sw}: Store Binary Word}
%
The \texttt{sw} instruction copies the binary word in the register \reg{1} to
the address \texttt{addr[\$2]}.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{lw \$1, addr[\$2]}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{19}		& \texttt{0x13}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{addr}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{sb}: Store BCD Word}
%
The \texttt{sb} instruction copies a BCD word from the pseudoregister \reg{1}
to the address \texttt{addr[\$2]}.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{lw \$1, addr[\$2]}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{20}		& \texttt{0x14}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& \reg{u}, \reg{v}	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{addr}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{xw}: Exchange Binary Word}
%
The \texttt{xw} instruction swaps the binary word at the address
\texttt{addr[\$2]} with the binary word in the register \reg{1}.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{lw \$1, addr[\$2]}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{21}		& \texttt{0x15}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{addr}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\section{Branch Instructions} % -----------------------------------------------
%
\subsection{\texttt{beqi}: Branch If Equal To Immediate}
%
The \texttt{beqi} instruction jumps to the address \texttt{addr} if the
register \reg{1} and the immediate \texttt{imm} have equal values.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{beqi \$1, imm, addr}}			\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{32}		& \texttt{0x20}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \texttt{imm}	& 0--15			\\
\texttt{16} & \texttt{31} & \texttt{addr}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{beqsi}: Branch If Equal To Shifted Immediate}
%
The \texttt{beqsi} instruction jumps to the address \texttt{addr} if the
register \reg{1} is equal to the immediate \texttt{imm} shifted left by four bit
positions (i.e. multiplied by 16).

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{beqi \$1, imm, addr}}			\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{33}		& \texttt{0x21}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \texttt{imm}	& 0--15			\\
\texttt{16} & \texttt{31} & \texttt{addr}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{bgt}: Branch If Greater Than}
%
The \texttt{bgt} instruction jumps to the address \texttt{addr} if the
register \reg{1} is greater than the register \reg{2}.  \reg{1} and \reg{2} are
treated as unsigned binary words.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{bgt \$1, \$2, addr}}			\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{34}		& \texttt{0x22}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{addr}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\section{Mathematical Instructions} % -----------------------------------------
%
\subsection{\texttt{lui}: Load Upper From Immediate}
%
The \texttt{lui} instruction copies the immediate \texttt{imm} into the upper
sixteen bits of the register \reg{1}.  The lower sixteen bits of \reg{1} are
unaffected.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{lui \$1, imm}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{48}		& \texttt{0x30}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \texttt{0}		& \texttt{0x0}		\\
\texttt{16} & \texttt{31} & \texttt{imm}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{min}: Find Minimum}
%
The \texttt{min} instruction sets register \reg{1} equal to the lesser of the
two registers \reg{2} and \reg{3}.  \texttt{min} treats \reg{1}, \reg{2}, and
\reg{3} as unsigned binary words.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{min \$1, \$2, \$3}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{49}		& \texttt{0x31}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{19} & \reg{3}		& Normal register set	\\
\texttt{20} & \texttt{31} & \texttt{0}		& \texttt{0x000}	\\
\end{tabular}
\end{center}
%
\subsection{\texttt{addi}: Add With Immediate}
%
The \texttt{addi} instruction performs an addition between register \reg{2} and
immediate \texttt{imm} and stores the result in \reg{1}.  Overflows are
ignored, and the carry flag \reg{cf} has no effect.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{addi \$1, \$2, imm}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{50}		& \texttt{0x32}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& BCD register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& BCD register set	\\
\texttt{16} & \texttt{31} & \texttt{imm}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{badd}: BCD Addition}
%
The \texttt{badd} instruction adds the BCD registers \reg{2} and \reg{3} and
the carry flag \reg{cf} and stores the sum modulo 10 in the BCD register
\reg{1}.  If the sum in decimal is greater than 9, the carry flag \reg{cf} is
set to \texttt{true}, otherwise it is set to \texttt{false}.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{badd \$1, \$2, \$3}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{51}		& \texttt{0x33}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& BCD register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& BCD register set	\\
\texttt{16} & \texttt{19} & \reg{3}		& BCD register set	\\
\texttt{20} & \texttt{31} & \texttt{0}		& \texttt{0x000}	\\
\end{tabular}
\end{center}
%
\subsection{\texttt{sub}: Subtract}
%
The \texttt{sub} instruction subtracts the register \reg{3} from \reg{2} and stores the result in \reg{1}.  Overflows are ignored, and \reg{cf} has no effect.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{sub \$1, \$2, \$3}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{52}		& \texttt{0x34}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{19} & \reg{3}		& Normal register set	\\
\texttt{20} & \texttt{31} & \texttt{0}		& \texttt{0x000}	\\
\end{tabular}
\end{center}
%
\subsection{\texttt{adds}: Add Shifted}
%
The \texttt{adds} instruction adds \reg{2} shifted left by \texttt{imm} bit
positions to \reg{1}.  Overflows are ignored---the upper bits are simply
discarded.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{adds \$1, \$2, imm}}				\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{53}		& \texttt{0x35}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{imm}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{cshri}: Ceiling Shift Right By Immediate}
%
The \texttt{cshri} instruction shifts \reg{2} right by \texttt{imm} bit
positions and stores the result in register \reg{1}.  If any zeroes are shifted
out of \reg{2}, \texttt{1} is added to the result to give the effect of rounding
up.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{cshri \$1, \$2, imm}}			\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{54}		& \texttt{0x36}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{imm}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\subsection{\texttt{fshri}: Floor Shift Right By Immediate}
%
The \texttt{cshri} instruction shifts \reg{2} right by \texttt{imm} bit
positions and stores the result in register \reg{1}.  Zeroes shifted out of
\reg{2} are ignored, giving the effect of rounding down.

\begin{center}
\begin{tabular}{@{[}r@{--}r@{]:~}ll}
\multicolumn{4}{c}{\texttt{fshri \$1, \$2, imm}}			\\
\hline
\texttt{ 0} & \texttt{ 7} & \texttt{56}		& \texttt{0x37}		\\
\texttt{ 8} & \texttt{11} & \reg{1}		& Normal register set	\\
\texttt{12} & \texttt{15} & \reg{2}		& Normal register set	\\
\texttt{16} & \texttt{31} & \texttt{imm}	& 0--65,535		\\
\end{tabular}
\end{center}
%
\begin{table}[hp]
\caption{Instruction Set Summary}
\footnotesize
\begin{tabular}{|ll|c|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{2}{|c|}{Mnemonic \&} & \multicolumn{8}{|c|}{Bits} \\
\cline{3-10}
\multicolumn{2}{|c|}{Operands} &
\texttt{31}--\texttt{28} & \texttt{27}--\texttt{24} &
\texttt{23}--\texttt{20} & \texttt{19}--\texttt{16} &
\texttt{15}--\texttt{12} & \texttt{11}--\texttt{08} &
\texttt{07}--\texttt{04} & \texttt{03}--\texttt{00} \\
\hline
\hline
%
\texttt{read} & \texttt{\$1, \$2, addr} &
\multicolumn{4}{|c|}{\texttt{addr}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x00}} \\
\hline
%
\texttt{disp} & \texttt{\$1, addr[\$2]} &
\multicolumn{4}{|c|}{\texttt{addr}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x01}} \\
\hline
\hline
%
\texttt{lw} & \texttt{\$1, addr[\$2]} &
\multicolumn{4}{|c|}{\texttt{addr}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x10}} \\
\hline
%
\texttt{lb} & \texttt{\$1, addr[\$2]} &
\multicolumn{4}{|c|}{\texttt{addr}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x11}} \\
\hline
%
\texttt{la} & \texttt{\$1, addr[\$2]} &
\multicolumn{4}{|c|}{\texttt{addr}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x12}} \\
\hline
%
\texttt{sw} & \texttt{\$1, addr[\$2]} &
\multicolumn{4}{|c|}{\texttt{addr}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x13}} \\
\hline
%
\texttt{sb} & \texttt{\$1, addr[\$2]} &
\multicolumn{4}{|c|}{\texttt{addr}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x14}} \\
\hline
%
\texttt{xw} & \texttt{\$1, addr[\$2]} &
\multicolumn{4}{|c|}{\texttt{addr}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x15}} \\
\hline
\hline
%
\texttt{beqi} & \texttt{\$1, imm, addr} &
\multicolumn{4}{|c|}{\texttt{addr}} & \texttt{imm} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x20}} \\
\hline
%
\texttt{beqsi} & \texttt{\$1, imm, addr} &
\multicolumn{4}{|c|}{\texttt{addr}} & \texttt{imm} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x22}} \\
\hline
%
\texttt{bgt} & \texttt{\$1, \$2, addr} &
\multicolumn{4}{|c|}{\texttt{addr}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x22}} \\
\hline
\hline
%
\texttt{lui} & \texttt{\$1, imm} &
\multicolumn{4}{|c|}{\texttt{imm}} & \texttt{0x0} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x30}} \\
\hline
%
\texttt{min} & \texttt{\$1, \$2, \$3} &
\multicolumn{3}{|c|}{\texttt{0x000}} & \reg{3} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x31}} \\
\hline
%
\texttt{addi} & \texttt{\$1, \$2, imm} &
\multicolumn{4}{|c|}{\texttt{imm}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x32}} \\
\hline
%
\texttt{badd} & \texttt{\$1, \$2, \$3} &
\multicolumn{3}{|c|}{\texttt{0x000}} & \reg{3} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x33}} \\
\hline
%
\texttt{sub} & \texttt{\$1, \$2, \$3} &
\multicolumn{3}{|c|}{\texttt{0x000}} & \reg{3} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x34}} \\
\hline
%
\texttt{adds} & \texttt{\$1, \$2, imm} &
\multicolumn{4}{|c|}{\texttt{imm}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x35}} \\
\hline
%
\texttt{cshri} & \texttt{\$1, \$2, imm} &
\multicolumn{4}{|c|}{\texttt{imm}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x36}} \\
\hline
%
\texttt{fshri} & \texttt{\$1, \$2, imm} &
\multicolumn{4}{|c|}{\texttt{imm}} & \reg{2} & \reg{1} &
\multicolumn{2}{|c|}{\texttt{0x37}} \\
\hline
\end{tabular}
\normalsize
\end{table}
%
\end{document}
% The end.
