% $Id: isa.tex,v 1.7 2023/01/25 13:48:20 leavens Exp leavens $
\documentclass[11pt,addpoints,letterpaper]{exam}
\input{macros}
\newcommand{\ACCUM}{\textsf{ACCUM}}
\newcommand{\PC}{\textsf{PC}}
\newcommand{\IR}{\textit{IR}}
\newcommand{\MEMORYNAME}{\textrm{memory}}
\newcommand{\MEMORY}[1]{\ensuremath{\MEMORYNAME[#1]}}
\newcommand{\AND}{\ensuremath{\:\wedge\:}}
\newcommand{\GETS}{\ensuremath{\leftarrow}}
\newcommand{\IFO}[2]{\textrm{\textbf{if} \ensuremath{#1} \textbf{then}
    \{\ensuremath{#2}\} }}
\newcommand{\IF}[3]{\textrm{\textbf{if} #1 \textbf{then} #2 \textbf{else} #3}}
\newcommand{\EQUALS}{\ensuremath{=}} % or {\ensuremath{\:\texttt{==}\:}}
%
\begin{document}
\noindent
~
\hfill COP 3402 --- Systems Software
\hfill \today \\

\begin{center}
{\huge Tiny Machine ISA}
\end{center}

\section{Tiny Machine VM Architecture}

The Tiny Machine is a von Neumann machine with a single register, the
accumulator ($\ACCUM$) and a single memory. It is word-addressed and
each instruction occupies a single word.

\subsection{Registers}

The VM has only one built-in user-accessible register, the accumulator
($\ACCUM$).

\subsection{Instruction Format}

The Instruction Set Architecture (ISA) has instructions that
may have two components, which are input and output as integers
(i.e., they have the C type int) named as follows:

\begin{tabular}{|l|l|}
\hline
OP &	is the operation code \\
\hline
ADDR & 	an address in the memory \\
\hline
\end{tabular}

The list of instructions and details on their execution appears in Appendix A.

\subsection{VM Cycles}

The VM instruction cycle conceptually does the following for each
instruction:

\begin{enumerate}
\item
  Let $\IR$ be the instruction in the memory at the location given by $\PC$.
  (Note that $\IR$ could be considered to be the contents of a register.)

\item
  The $\PC$ is made to point to the next location in memory (it is
  incremented by 1).

\item
The instruction $\IR$ is executed
The OP component of this instruction ($\IR$.OP) indicates the operation
to be executed. For example, if $\IR$.OP encodes the instruction ADD,
then the machine adds the memory value at the address given (by the
$\IR$.ADDR field of the instruction) to the accumulator.
Note that arithmetic overflows and underflows happen as in C \textbf{int}
arithmetic.
\end{enumerate}

This instruction cycle is repeated endlessly until the machine halts
by executing a HLT instruction.

\subsection{VM Initial/Default Values}

When the VM starts execution, $\PC$ and $\ACCUM$ are all $0$.
This means that execution starts with the instruction at memory element $0$.
Similarly, the initial values in memory are all zero ($0$), before the
program is loaded.

\subsection{Size Limits}

The following constants define the size limitations of the VM.
\begin{itemize}
\item
\lstinline!MAX_ADDR! is 65536
\end{itemize}

\subsection{Invariants}

The VM enforces the following invariant and will halt with an error
message (written to stderr) if violated:

\begin{itemize}
\item
   $0 \leq \PC \AND \PC < \texttt{MAX\_ADDR}$
\end{itemize}

\appendix
\section{Appendix A: Instructions}

In the following table, italicized names (such as $a$) are
meta-variables that refer to integers.  If an instruction's ADDR field is
notated as $-$, then its value does not matter (we use \texttt{0} as a
placeholder for such values in examples).

\begin{tabular}{|r|l|l|p{10cm}|}
\hline
OP  & OP  & M   & Comment \\
Code Num. & Mnemonic & & (Explanation) \\
\hline
0  & LIT  & $n$ & Literal $n$ put in accumulator: $\ACCUM \GETS n$ \\
\hline
1  & LOD  & $a$ & Load from address $a$: $\ACCUM \GETS \MEMORY{a}$ \\
\hline
2  & STO  & $a$ & Store to address $a$: $\MEMORY{a} \GETS \ACCUM$ \\
\hline
3  & ADD  & $a$ & Add value in $a$ to accumulator: \\
   &      &     & $\ACCUM \GETS \ACCUM + \MEMORY{a}$ \\
\hline
4  & SUB  & $a$ & Subtract value in $a$ from accumulator: \\
   &      &     & $\ACCUM \GETS \ACCUM - \MEMORY{a}$ \\
\hline
5  & CIN  & $-$ & Read a character from stdin,
                  with -1 representing EOF or error: \\
   &      &     & $\ACCUM \GETS \textbf{getc}()$ \\
\hline
6  & COU  & $-$ & Print a character to stdout: \\
   &      &     & $\textbf{putc}(\ACCUM)$ \\
\hline
7  & HLT  &     & Halt the program's execution \\
\hline
8  & JMP  & $a$ & Jump to the given address: \\
   &      &     & $\PC \GETS a$ \\
\hline
9 & SKZ  & $a$ & Skip if zero: \\
   &      &     & \IFO{\ACCUM \EQUALS 0}{\PC \GETS \PC + 1} \\
\hline
10 & SKG  & $a$ & Skip if greater than zero: \\
   &      &     & \IFO{\ACCUM > 0}{\PC \GETS \PC + 1} \\
\hline
11 & SKL  & $a$ & Skip if less than zero: \\
   &      &     & \IFO{\ACCUM < 0}{\PC \GETS \PC + 1} \\
\hline
12 & OR   & $a$ & Bitwise-or the value in $a$ to accumulator: \\
   &      &     & $\ACCUM \GETS \ACCUM \vee \MEMORY{a}$ \\
\hline
13 & AND  & $a$ & Bitwise-and the value in $a$ to accumulator: \\
   &      &     & $\ACCUM \GETS \ACCUM \wedge \MEMORY{a}$ \\
\hline
14 & NOT  & $-$ & Bitwise complement the value in the accumulator: \\
   &      &     & $\ACCUM \GETS \neg \ACCUM$ \\
\hline
15 & NDB  & $-$ & Stop printing debugging output \\
\hline
\end{tabular}

\section{Appendix B: Examples}

\subsection{A Simple Example Showing Output Formatting}

The following very simple example shows the expected formatting.
Suppose the input is the following file (\texttt{tm-test0.txt}, 
the name of this file is passed to the VM on the Unix command line):

\LSTFILE{tm-test0.txt}

Running the VM with the above input produces the following output
(written to stdout). Note that there are two parts to the output: (1)
a listing of the instructions in the program one per line, following a
header, with mnemonics for each instruction and (2) a trace of the
program's execution, following the line \texttt{Tracing ...} (all on
standard output).  
The trace of execution shows the state of the built-in registers
($\PC$ and $\ACCUM$)
and the memory's values, the first 100 locations with values printed
in hexadecimal notation
(as that is more convenient for reading instructions)
and the rest of the locations with values printed in decimal.
However, only the first of a run on zero values are shown,
as most locations hold zero (since that is the initial value).
After this output of the program state, there is a line printed
(on stdout) that starts with
\texttt{==> addr: }
followed by: (a) the address of the instruction being executed,
then (b) the instruction with its mnemonic and ADDR value,
then after showing the instruction being executed (and after the
instruction's execution by the VM) the state is again shown
(in the same format as before).
The output of the instruction and the
resulting state are show after is each instruction executed.

\LSTFILE{tm-test0.out}

\subsection{A More Involved Example}

The following example has a more complex program and shows some of the
details of the machine's execution.

\subsubsection{Input File}

The following is the contents of
the file \texttt{tm-test1.txt}:

\LSTFILE{tm-test1.txt}

\subsubsection{Output (To Stdout)}

Running the VM with the above input produces the following output
(written to stdout).

\LSTFILE{tm-test1.out}

\end{document}
