\documentclass[]{article}
\usepackage[utf8]{inputenc}
\usepackage{algorithmic}
\usepackage{graphicx}
\usepackage{listings}
\DeclareGraphicsRule{*}{mps}{*}{}
\lstset{language=c}

\title{BrainFuck-based Microprocessor}
\author{Andre Masella}

\begin{document}

\maketitle

\begin{abstract}
This is a description of how a processor designed around the BrainFuck language could be implemented. BrainFuck is a simple language as close to a Turing machine as possible.
\end{abstract}

\section{Introduction}
BrainFuck is a simple language involving only eight instructions: input, output, increment, decrement, advance, retreat and a loop construct. This processor is intended to be 8-bit, but since the instructions require only 3-bits, it could be implemented in more or less.

\section{The BrainFuck Language}
The BrainFuck language operates on a few simple instructions. From the perspective of the programmer, they have a single ``pointer'' $p$. The instructions are:

\begin{description}
\item[$.$] --- Set the value of the pointer to the value on the external bus.(In C, the call \lstinline!*p = bus!.)
\item[$,$] --- Set the value of the bus to the value at the pointer.(In C, the call \lstinline!bus = *p!.)
\item[$+$] --- Increment the value at $p$. (In C, \lstinline!(*p)++!.)
\item[$-$] --- Decrement the value at $p$. (In C, \lstinline!(*p)--!.)
\item[$>$] --- Advance $p$. (In C, \lstinline!p++!.)
\item[$<$] --- Retreat $p$. (In C, \lstinline!p--!.)
 \newcommand{\loopconstruct}{$\left[  x \right] $}
\item[\loopconstruct] When $\left.\right]$, execution should jump to $\left[\right.$ unless the value at the pointer is zero. (In C \lstinline!while (*p) {x}!.)
\end{description}

For convenience, two additional instructions are provided:
\begin{description}
\item[$zero$] --- Halts the processor.
\item[$\sim$] --- Performs no operation and continues execution.
\end{description}

\section{CPU Layout}
\begin{figure}
\label{fig:cpu}
\centering \includegraphics[height=3in]{BF-CPU}
\caption{Internal Layout of the CPU}
\end{figure}

Figure~\ref{fig:cpu} show the basic outline of the CPU. The register $P$ is the ``pointer'', the register $PC$ is the program counter and the register $SP$ is the stack pointer. $W$ is a working register for the arithmetic unit, which only needs to implement two functions: adding one and subtracting one. There should also be a control signal if the value of the bus is zero ($Z$) and to write a value of zero to the bus ($Z_{out}$). The memory and external bus read-write signal controls the register connected to the devices and should initiate device function.

The control logic is as follows:
\begin{algorithmic}
\STATE assert $PC_{out}$ and $MAR_{in}$ and request a memory read.
\STATE assert $MDR_{out}$ and decode instruction from internal bus.
\end{algorithmic}

The code for each particular instruction is shown below. After the instruction's code is complete, the following should always execute:
\begin{algorithmic}
\STATE assert $PC_{out}$ and $W_{in}$ and select addition.
\STATE assert $W_{out}$ and $PC_{in}$.
\end{algorithmic}

\subsection{Read from External Bus ($.$)}
\begin{algorithmic}
\STATE assert $P_{out}$ and $MAR_{in}$ and request a memory read.
\STATE assert $MDR_{out}$ and $Bus_{out}$.
\end{algorithmic}

\subsection{Write to External Bus ($,$)}
\begin{algorithmic}
\STATE assert $MDR_{in}$ and $Bus_{in}$.
\STATE assert $P_{out}$ and $MAR_{in}$ and request a memory write.
\end{algorithmic}

\subsection{Increment Value ($+$)}
\begin{algorithmic}
\STATE assert $P_{out}$ and $MAR_{in}$ and request a memory read.
\STATE assert $MDR_{out}$ and $W_{in}$ and select addition.
\STATE assert $W_{out}$ and $MDR_{in}$ and request a memory write.
\end{algorithmic}

\subsection{Decrement Value ($-$)}
\begin{algorithmic}
\STATE assert $P_{out}$ and $MAR_{in}$ and request a memory read.
\STATE assert $MDR_{out}$ and $W_{in}$ and select subtraction.
\STATE assert $W_{out}$ and $MDR_{in}$ and request a memory write.
\end{algorithmic}

\subsection{Advance Pointer ($>$)}
\begin{algorithmic}
\STATE assert $P_{out}$ and $W_{in}$ and select addition.
\STATE assert $W_{out}$ and $P_{in}$.
\end{algorithmic}

\subsection{Retreat Pointer ($>$)}
\begin{algorithmic}
\STATE assert $P_{out}$ and $W_{in}$ and select subtraction.
\STATE assert $W_{out}$ and $P_{in}$.
\end{algorithmic}

\subsection{Begin Loop ($\left[\right.$)}
\begin{algorithmic}
\STATE assert $SP_{out}$ and $W_{in}$ and select subtraction.
\STATE assert $W_{out}$ and $SP_{in}$.

\STATE assert $P_{out}$ and $MAR_{in}$ and request a memory read.
\STATE assert $MDR_{out}$.
\IF{$Z$}
\STATE assert $SP_{out}$ and $MAR_{in}$.
\STATE assert $P_{out}$ and $MDR_{in}$ and request a memory write.
\STATE assert $Z_{out}$ and $W_{in}$ and select addition.
\STATE assert $W_{out}$ and $P_{in}$.
\WHILE{$\bar{Z}$}
\STATE assert $PC_{out}$ and $W_{in}$ and select addition.
\STATE assert $W_{out}$ and $PC_{in}$.
\STATE assert $PC_{out}$ and $MAR_{in}$ and request a memory read.
\STATE assert $MDR_{out}$

\IF{value is a begin loop instruction}
\STATE assert $P_{out}$ and $W_{in}$ and select addition.
\STATE assert $W_{out}$ and $P_{in}$.
\ELSIF {value is an end loop instruction}
\STATE assert $P_{out}$ and $W_{in}$ and select subtraction.
\STATE assert $W_{out}$ and $P_{in}$.
\ELSE
\STATE assert $P_{out}$.
\ENDIF
\ENDWHILE
\STATE assert $PC_{out}$ and $W_{in}$ and select subtraction.
\STATE assert $W_{out}$ and $PC_{in}$.
\STATE assert $SP_{out}$, $MAR_{in}$ and $W_{in}$, select subtraction and request memory read.
\STATE assert $MDR_{out}$ and $P_{in}$.
\STATE assert $W_{out}$ and $SP_{in}$.

\ELSE
\STATE assert $SP_{out}$ and $MAR_{in}$.
\STATE assert $PC_{out}$ and $MDR_{in}$ and request a memory write.
\ENDIF
\end{algorithmic}

\subsection{End Loop ($\left.\right]$)}
\begin{algorithmic}
\STATE assert $P_{out}$ and $MAR_{in}$ and request a memory read.
\IF{$Z$}
\STATE assert $SP_{out}$ and select addition.
\STATE assert $W_{out}$ and $SP_{in}$.
\ELSE
\STATE assert $SP_{out}$ and $MAR_{in}$, request a memory read.
\STATE assert $MDR_{out}$ and $PC_{in}$.
\ENDIF
\end{algorithmic}

\subsection{Halt ($zero$)}
This instruction is added for convenience of the programmer. If the processor receives an instruction that is zero, it should stop processing instructions until it is reset. This allows programs downloaded to halt the system when they finish, although, in software, this could be implemented by $\left[-\right]+\left[\right]$.

\subsection{No Operation ($\sim$)}
Again, this instruction is added for the convenience of the programmer. As the name suggests, it does nothing and continues execution.

\section{Initialisation}
The system will require a ROM and RAM on the memory bus. Upon reset, the register $P$ should point to the beginning of the RAM, the register $SP$ should point to the top of RAM and the register $PC$ should point to the beginning of the ROM. The ROM should contain a small monitor program to read values from the bus until the data stops (a value of zero). The ROM need not actually be a ROM. It could be RAM that initially holds this monitor program. The monitor could be implemented by $\left[,>\right]\sim^n$ where $n$ is a sufficient amount of padding to reach the end of the ROM. This can be seen in Figure~\ref{fig:mem}. The memory layout on boot is show on top, and the memory layout as control is transferred from the ROM to the user's program.

\begin{figure}
\label{fig:mem}
\setlength{\unitlength}{3947sp}
\centering \begin{picture}(4734,1974)(1684,-3148)
\thinlines
\put(1726,-3136){\framebox(1050,525){}}
\put(2776,-3136){\framebox(1875,525){}}
\put(4651,-3136){\framebox(1650,525){}}
\put(2776,-2011){\framebox(3600,525){}}
\put(1726,-2011){\framebox(1050,525){}}
\put(1726,-1186){\vector( 0,-1){300}}
\put(2776,-1186){\vector( 0,-1){300}}
\put(6376,-1186){\vector( 0,-1){300}}
\put(4651,-2311){\vector( 0,-1){300}}
\put(2776,-2311){\vector( 0,-1){300}}
\put(6301,-2311){\vector( 0,-1){300}}
\put(2251,-2986){\makebox(0,0)[b]{ROM}}
\put(3601,-2986){\makebox(0,0)[b]{Program}}
\put(5476,-2986){\makebox(0,0)[b]{...}}
\put(5476,-1861){\makebox(0,0)[b]{...}}
\put(2251,-1861){\makebox(0,0)[b]{ROM}}
\put(2926,-2461){\makebox(0,0)[lb]{PC}}
\put(4726,-2461){\makebox(0,0)[lb]{P}}
\put(2851,-1336){\makebox(0,0)[lb]{P}}
\put(1876,-1336){\makebox(0,0)[lb]{PC}}
\put(6226,-2461){\makebox(0,0)[rb]{SP}}
\put(6301,-1336){\makebox(0,0)[rb]{SP}}
\end{picture}
\caption{Memory Layout}
\end{figure}


\section{External Bus}
The external bus would dramatically affect the kind of code written. For a simple 8-bit system, a serial controller might be the external bus. If multiple devices need to be addressed, then something like a serial peripheral interface bus (SPI) could be used. Any address selection would have to be done through the data lines. If the bus had multiple data items, the ROM could be expanded to include an initialisation command that would select a particular piece of hardware from which to copy the user's software.
\end{document}