Initial commit

8 files changed, 205 insertions, 0 deletions

diff --git a/doc/.gitignore b/doc/.gitignore
new file mode 100644
index 0000000..02db5bd
--- /dev/null
+++ b/doc/.gitignore
@@ -0,0 +1,7 @@
+*.aux
+*.dvi
+*.fmt
+*.log
+*.out
+*.ps
+*.toc
diff --git a/doc/Makefile b/doc/Makefile
new file mode 100644
index 0000000..c50ab32
--- /dev/null
+++ b/doc/Makefile
@@ -0,0 +1,25 @@
+LATEX:=latex
+LATEXFLAGS:=-file-line-error -halt-on-error -no-shell-escape
+DVIPS:=dvips
+
+DOC:=doc
+TEXS:=$(wildcard *.tex)
+STYS:=$(wildcard *.sty)
+
+.PHONY: all
+.SECONDARY: $(DOC).fmt
+
+all: $(DOC).ps
+
+%.fmt: preamble.tex $(STYS)
+	$(LATEX) $(LATEXFLAGS) -ini -jobname="$(basename $@)" "&$(LATEX) $<\dump"
+
+%.ps: %.dvi
+	$(DVIPS) $<
+
+%.dvi: %.tex %.fmt $(TEXS)
+	$(LATEX) $(LATEXFLAGS) $<
+	$(LATEX) $(LATEXFLAGS) $<
+
+clean:
+	$(RM) -v $(addprefix $(DOC).,aux log ps fmt dvi toc)
diff --git a/doc/chip.sty b/doc/chip.sty
new file mode 100644
index 0000000..56d061a
--- /dev/null
+++ b/doc/chip.sty
@@ -0,0 +1,29 @@
+\def\eqdef{\stackrel{\mathrm{def}}{=}}
+
+\def\instrop{\mathit{instr}}
+\def\instr#1#2{\instrop(#1)(#2)}
+
+\def\incpcop{\mathit{incpc}}
+\def\incpc#1{\incpcop(#1)}
+
+\def\update#1#2{#1[#2]}
+
+\def\ALUOp{\mathit{ALUOp}}
+\def\Word#1{\mathit{Word}_#1}
+
+\def\Prog{\mathit{Prog}}
+\def\prog{\mathit{prog}}
+
+\def\State{\mathit{State}}
+\def\st{\mathit{st}}
+
+\def\Mem{\mathit{Mem}}
+\def\mem{\mathit{mem}}
+
+\def\pc{\mathit{pc}}
+\def\acc#1{\mathit{acc}_#1}
+
+\def\nandop{\mathit{nand}}
+\def\nand#1#2{\nandop\left(#1,#2\right)}
+\def\xnorop{\mathit{xnor}}
+\def\xnor#1#2{\xnorop\left(#1,#2\right)}
diff --git a/doc/comp.tex b/doc/comp.tex
new file mode 100644
index 0000000..70dc2e5
--- /dev/null
+++ b/doc/comp.tex
@@ -0,0 +1,29 @@
+\section{Components}
+Our chip consists of the following static components:
+
+\begin{itemize}
+	\item An ALU: $\ALUOp \times \Word8 \times \Word8 \to \Word8$.
+	\item The program memory $\prog$: $\Prog \eqdef \Word6^{256}$.
+\end{itemize}
+
+And these volatile components:
+
+\begin{itemize}
+	\item A memory $\mem$: $\Mem \eqdef \Word8^{256}$. Individual words or cells
+		are addressed with one word. We write $\mem.n$ for the cell in $\mem$ at
+		address $n$. We write $\update{\mem}{n\mapsto k}$ for the memory $\mem'$
+		with
+		$$
+			\mem'.i = \begin{cases}
+				k      & \text{if $i=n$,}\\
+				\mem.i & \text{otherwise.}
+			\end{cases}
+		$$
+	\item The accumulators $\acc1$ and $\acc2$ are located at address $0$ and
+		$1$ of the memory, respectively.
+	\item The program counter $\pc$ is located at address $2$ of the memory.
+\end{itemize}
+
+A state $\st$ can be seen as a tuple $(\prog,\mem)$. We define the set of all
+states $\State \eqdef \Word6^{256} \times \Word8^{256}$. An instruction is a
+function $\Mem\to\Mem$. The instruction cycle is a function $\State\to\State$.
diff --git a/doc/doc.tex b/doc/doc.tex
new file mode 100644
index 0000000..33c993d
--- /dev/null
+++ b/doc/doc.tex
@@ -0,0 +1,11 @@
+%&doc
+\begin{document}
+
+\maketitle
+\tableofcontents
+
+\input{intro}
+\input{comp}
+\input{instr}
+
+\end{document}
diff --git a/doc/instr.tex b/doc/instr.tex
new file mode 100644
index 0000000..4bc27e0
--- /dev/null
+++ b/doc/instr.tex
@@ -0,0 +1,85 @@
+\section{Instruction Set}
+\label{sec:instr}
+
+\subsection{The Instruction Cycle}
+The instruction cycle is a function $\State\to\State$. It is defined as
+follows:
+
+$$\mathit{cycle}(\prog,\mem) \eqdef (\prog, \instr{\mem.\pc}{\mem})$$
+
+Here, $\instrop$ is a function that maps words to instructions: $\instrop :
+\Word6 \to \Mem \to \Mem$. It is defined in \autoref{sec:instr}.
+
+\subsection{Instructions}
+The binary representations of the commands defined can be found in
+\autoref{fig:instr:instr-set}.
+
+\begin{table}[b]
+	\centering
+	{\tt
+	\begin{tabular}{!>{\normalfont}l | ^l | *{6}{|^c}}
+		\rowstyle{\normalfont\bfseries}
+		Instruction name & Assembly & 5 & 4 & 3 & 2 & 1 & 0 \\\hline
+		Addition         & add      & 1 & 0 & 0 & 0 & 0 & 0 \\\hline
+		Logical NAND     & nand     & 1 & 0 & 0 & 0 & 0 & 1 \\\hline
+		Equality         & eq       & 1 & 0 & 0 & 0 & 1 & 0 \\\hline
+		Conditional jump & cjmp     & 1 & 1 & 0 & 0 & 0 & 0 \\\hline
+		Store register   & str      & 1 & 1 & 1 & 1 & 1 & 0 \\\hline
+		Load register    & ld       & 1 & 1 & 1 & 1 & 1 & 1 \\\hline
+		Store literal 1  & lit1     & 0 & 0 & \multicolumn{4}{c}{$k$} \\\hline
+		Store literal 2  & lit2     & 0 & 1 & \multicolumn{4}{c}{$k$} \\
+	\end{tabular}
+	}
+	\caption{Instruction set\label{fig:instr:instr-set}}
+\end{table}
+
+The instructions are now described. For this we define an auxiliary function
+$\incpcop$, which increments the program counter:
+$$\incpc{\mem} = \update{\mem}{\pc\mapsto\mem.\pc+1}$$
+
+\subsubsection{Addition}
+$$
+	\instr{\texttt{100000}}{\mem} \eqdef
+	\incpc{\update{\mem}{\acc1\mapsto\mem.\acc1+\mem.\acc2}}
+$$
+
+\subsubsection{Logical NAND}
+$$
+	\instr{\texttt{100001}}{\mem} \eqdef
+	\incpc{\update{\mem}{\acc1\mapsto\nand{\mem.\acc1}{\mem.\acc2}}}
+$$
+
+\subsubsection{Equality}
+$$
+	\instr{\texttt{100001}}{\mem} \eqdef
+	\incpc{\update{\mem}{\acc1\mapsto\xnor{\mem.\acc1}{\mem.\acc2}}}
+$$
+
+\subsubsection{Conditional jump}
+$$
+	\instr{\texttt{110000}}{\mem} \eqdef
+	\begin{cases}
+		\update{\mem}{\pc\mapsto\mem.\acc2} & \text{if $\mem.\acc1\neq0$}\\
+		\incpc{\mem} & \text{otherwise}
+	\end{cases}
+$$
+
+\subsubsection{Store register}
+$$
+	\instr{\texttt{111110}}{\mem} \eqdef
+	\incpc{\update{\mem}{\mem.\acc2\mapsto\mem.\acc1}}
+$$
+
+\subsubsection{Load register}
+$$
+	\instr{\texttt{111111}}{\mem} \eqdef
+	\incpc{\update{\mem}{\acc1\mapsto\mem.(\mem.\acc2)}}
+$$
+
+\subsubsection{Store literal}
+\begin{align*}
+	\instr{\texttt{00}k}{\mem} &\eqdef
+	\incpc{\update{\mem}{\acc1\mapsto(\mem.\acc1 \land \texttt{0xf0})\lor k}} \\
+	\instr{\texttt{01}k}{\mem} &\eqdef
+	\incpc{\update{\mem}{\acc1\mapsto(\mem.\acc1 \land \texttt{0x0f})\lor (k \ll 4)}}
+\end{align*}
diff --git a/doc/intro.tex b/doc/intro.tex
new file mode 100644
index 0000000..6d8b74b
--- /dev/null
+++ b/doc/intro.tex
@@ -0,0 +1 @@
+\section{Introduction}
diff --git a/doc/preamble.tex b/doc/preamble.tex
new file mode 100644
index 0000000..398a351
--- /dev/null
+++ b/doc/preamble.tex
@@ -0,0 +1,18 @@
+\documentclass[a4paper]{article}
+
+\usepackage[british]{babel}
+\usepackage{geometry}
+\usepackage[hidelinks]{hyperref}
+
+\usepackage{amsmath}
+\usepackage{array}
+\newcolumntype{!}{>{\global\let\currentrowstyle\relax}}
+\newcolumntype{^}{>{\currentrowstyle}}
+\newcommand{\rowstyle}[1]{\gdef\currentrowstyle{#1}%
+	#1\ignorespaces}
+
+\usepackage{chip}
+
+\title{Chip} %todo
+\author{Mart Lubbers\and Camil Staps}
+\date{\today}