% Content-encoding: UTF-8
\documentclass[ngerman]{article}
\usepackage[utf8]{inputenc}
\usepackage{multicol,babel}
\setcounter{secnumdepth}{0}
\setcounter{tocdepth}{0}

\renewcommand{\reftextbefore}{auf der vor\-herigen Seite}
\renewcommand{\reftextfacebefore}{auf der gegen\-über\-lie\-genden Seite}
\renewcommand{\reftextafter}{auf der näch\-sten Seite}
\renewcommand{\reftextfaceafter}{auf der gegen\-über\-lie\-genden Seite}
\renewcommand{\reftextfaraway}[1]{auf Seite~\pageref{#1}}

\begin{document}
% \renewcommand{\figurename}{Tabelle}

\title{Forth im FPGA — Teil 2, b16}
%\ifx\shorttitle\undefined\else
%\shorttitle{Forth im FPGA}
%\fi
\author{Ulrich Hoffmann}
\maketitle

\begin{figure*}[b]
\begin{center}
\includegraphics[width=0.55\textwidth]{2009-04/b16-small}
\caption{\label{b16-small:block}Blockschaltbild des {\sf b16-small}--Prozessors [3]}
\end{center}
\end{figure*} 

In diesem zweiten Artikel über Forth im FPGA widmen wir uns der Frage,
wie Bernd Paysans {\sf b16}-Prozessor [2] auf dem Altera--DE1-Entwicklungsboard, 
das wir in Teil 1 vorgestellt haben, realisiert wird. 

Dann wollen wir einfache Beispiel--Programme für {\sf b16} programmieren und den Assembler benutzen, daraus {\sf b16}--Maschinencode zu erzeugen und diesen ablaufen zu lassen.
Die auf dem DE1--Board verfügbare 7--Segment--Anzeige wollen wir dabei als Debug--Hilfe einsetzen.

\begin{multicols}{2}
\section{b16}

Der {\sf b16}--Prozessor lehnt sich in seiner Architektur an den {\sf c18}--Chip [1] von Chuck Moore an: Eine Stack--Maschine in von Neumann--Architektur (gemeinsamer Speicher für Instruktionen und Daten) mit zusätzlichem separaten Daten-- und Return--Stack und einem reduzierten Instruktionssatz von nur 32 Instruktionen.

Eine Besonderheit ist die Art, wie Instruktionen kodiert sind: In einem Speicherwort werden mehrere Instruktionen in sogenannten \emph{Slots} gepackt dargestellt. 
Benötigt eine Instruktion Operanden, so kann sie nur in den ersten Slots auftreten, die restlichen Bits des Speicherwortes bilden dann die Operanden.
Operationen auf dem Stack --- wie \texttt{and}, \texttt{+} oder \texttt{drop} 
--- benötigen keine Operanden und können daher in jedem Slot stehen. 

%Weil es sich um eine 0--Address--Maschine handelt, können viele Instruktionen %durch wenige Bits kodiert werden. 

\begin{figure*}[t]
\begin{center}
\begin{tabular}{llllllllll}
	&0 	&1   	 &2 	&3 &	4 &	5 &	6 &	7 	&Kommentar\\
	\hline
0 	&nop 	&call &	jmp &	ret& 	jz &	jnz 	&jc 	&jnc &	Sprungziel im Rest der Instruktion\\
	&nop 	&exec &	goto &	ret &	gz &	gnz &	gc &	gnc &	für Slot 3\\
	\hline
8 	&xor 	&com  &	and &	or &	+ &	+c &	2/ &	c2/& 	\\
\hline
10 	&!+ 	&@+   & 	@& 	lit &	c!+ &	c@+ &	c@ 	&litc & \\ 	
	&!. 	&@.   &	@ 	&lit &	c!. &	c@. &	c@ &	litc &	für Slot 1\\
\hline
18 	&nip 	&drop &	over &	dup &	>r &	nop & 	r> &	nop & \\ 	
\end{tabular}
\caption{\label{b16-small:instr}Die Instruktionen des {\sf b16-small}--Prozessors [3]}
\end{center}
\end{figure*}


Bernd Paysan hat vom {\sf b16} zwei Varianten vorgestellt: 
\begin{enumerate}

   \item Der ursprüngliche {\sf b16} [2],
      der ein Adress--Register \texttt{A} im Stile des {\sf c18} zur
      Adressierung von Speicherzellen besitzt und bei dem \texttt{NOS}, das
      zweite Element des Datenstacks, und \texttt{R}, das oberste Element 
      des Return--Stacks, explizit als Register ausgeführt sind. 

   \item {\sf b16-small} [3], eine weiter vereinfachte Version, bei der 
      \texttt{NOS} und \texttt{R} in die jeweiligen Stacks integriert und 
      \texttt{A} entfallen ist. 
      Auch unterscheiden sich bedingte Sprünge von denen im {\sf b16} 
      dadurch, dass sie wie in Forth das oberste Datenstack--Element entfernen.
      Abbildung \vref{b16-small:block} zeigt den Aufbau von {\sf b16-small} 
      (Das Register P ist der Programmzähler, der auch als nulltes Element 
      des Return-Stacks angesehen werden kann).

\end{enumerate}

Weder \texttt{b16} noch \texttt{b16-small} (oder \texttt{c18}) haben die Instruktion \texttt{swap}. Statt dessen verwendet man zunächst \texttt{over} und dann später \texttt{nip}, um das überschüssige Stack--Element zu entfernen. Als Phrase ließe sich das als \\ \texttt{over >r nip r>} formulieren.

Wir wollen uns im Folgenden auf \texttt{b16-small} konzentrieren und einige seiner Eigenheiten ansprechen. Für eine vollständige Beschreibung inklusive komplettem Verilog--Quellcode sei auf Bernd Paysans {\sf b16-small}-Artikel [3] verwiesen.
{\sf b16-small} besitzt 32 Instruktionen, die in 5 Bits dargestellt werden.
Der Instruktionssatz ist in Abbildung \vref{b16-small:instr} zu sehen.

Ein {\sf b16-small}--Speicherwort ist 16 Bit breit. Es wird in 4 Slots aufgeteilt, die 1 Bit und drei mal 5 Bits haben. Die obersten 4 Bits des ersten Slots werden implizit als 0 angenommen, womit darin also nur eine \texttt{nop} oder \texttt{call}--Instruktion dargestellt werden kann. 

\begin{center}
\begin{tabular}{|cc|c|c|c|}
\hline
implizit & Slot 0 & Slot 1 & Slot 2 & Slot 3\\
0000 & a & bbbbb & ccccc & ddddd\\
\hline
\end{tabular}
\end{center}

{\sf b16-small}--Sprungbefehle sind bedingte und unbedingte Sprünge und Unterprogrammaufrufe. 
Sprungbefehle, die in Slot 0, 1 oder 2 stehen, nehmen ihr Sprungziel aus den restlichen Bits des Instruktionswortes: die entsprechenden Bits im Befehlszählregister werden ersetzt. Tritt ein Sprungbefehl in Slot 3 auf,
so erwartet er das Sprungziel auf dem Datenstack.

Die Auto--Inkrement--Speicherbefehle \texttt{!+ ( val addr -- addr' )} und \texttt{@+ ( addr -- cal addr')} (sowie ihre Byte-Varianten \texttt{c!+ c@+}) verwerfen die Speicheradresse nicht, sondern erhöhen sie auf die nächste Adresse. Das Auto-Inkrement wird allerdings unterdrückt, wenn diese Befehle in Slot 1 auftreten (In Slot 0 können ja nur \texttt{nop} oder \texttt{call} stehen).

\section{{\sf b16-small} programmieren}

Bernd Paysan hat basierend auf gforth für {\sf b16-small} einen Assembler geschrieben. Ihn und das gesamte {\sf b16-small}--Projekt stellt Bernd über das Subversion--Repository der Forth--Gesellschaft zur Verfügung [4].
Von dort lässt es sich bequem auf den eigenen Computer bringen\footnote{Subversion gehört  unter Mac OS X und Linux in der Regel zum Lieferumfang, unter Windows ist die Implementierung TortoiseSVN [5] (\url{http://tortoisesvn.tigris.org/}) weit verbreitet, bei dem dann das Importieren über den Windows-Explorer geschieht.}:

\begin{verbatim}
svn co http://www.forth-ev.de/repos/b16-small
\end{verbatim}

Wir finden dann die {\sf b16-small}--Verilog--Beschreibung (\texttt{.v}--Files), den Assembler (\texttt{b16.fs}), Dokumentation (\texttt{.lyx} und \texttt{.pdf}) sowie Beispielprogramme (\texttt{.asm} unter anderem auch die Triceps-Anwendung, die wir 2009 auf dem Linux-Tag in Berlin präsentiert haben).

Wir wollen ein ganz einfaches {\sf b16-small}--Programm schreiben und uns die Eigenheiten des Assemblers ansehen, der eng an Forth
angelehnt ist. Unser \emph{Hallo b16}--Programm soll die Zahlen 3 und 4 zusammenzählen und dann in einer Endlos--Schleife enden,
die das Resultat immerwährend um eins vermindert --- so ein {\sf b16}--Programm kann ja nicht einfach anhalten. Wir schreiben Folgendes:

\begin{verbatim}
#! /usr/bin/gforth b16-asm.fs

$2000 org

: boot
    3 #c 4 #c +
    
    BEGIN -1 # +   
    AGAIN 
;;

$3FFE org
     boot ;;

\ print verilog hex for $2000 bytes
$2000 $2000 .hex b16.hex       
$2000 $2000 .hexh b16h.hex
$2000 $2000 .hexl b16l.hex      

.end                    \ end of test program

\end{verbatim}

% $ syntax highlight

Der \texttt{org}--Befehl legt fest, an welcher Speicherzelle mit dem Assemblieren
begonnen werden soll. 

Unterprogramme werden mit \texttt{:} eingeleitet. Wird der so definierte Name später verwendet,
so wird ein Unterprogrammaufruf assembliert.

Anders als in Forth, aber so wie im klassichen Forth--Assembler, gibt es auch in 
diesem Assembler keinen 
Compiler/Interpreter--Zustand. Es wird immer interpretiert.
Das ist vermutlich auch der Grund, warum Literale explizit mit \texttt{\#} (oder wenn es
Byte--Literale sind mit \texttt{c\#}) assembliert werden und dies nicht implizit geschieht.
Im {\sf b16-small}--Maschinencode werden die Literale in nachfolgenden Programmzellen
abgelegt und bei der späteren Ausführung von dort auf den Stack geladen. Der Programmzähler
P wandert also weiter, wenn im aktuellen Instruktionswort \texttt{lit}--Befehle ausgeführt 
werden. 

Der Assembler unterstützt auch Schleifen und Bedingungen in klassischer Forth--Art. Wir verwenden
hier eine \texttt{BEGIN AGAIN}--Endlosschleife, um vom Wert auf dem Stack immer wieder 1 abzuziehen.

Da {\sf b16-small} keine Subtraktions--Instruktion hat, wird hier -1 addiert, um den Wert auf dem 
Stack um 1 zu vermindern. Wir könnten statt dessen auch das Macro

\begin{verbatim}
macro: - com +c end-macro
\end{verbatim}

definieren, das die Subtraktion durch  Additon des 2er--Komplements
realisiert, wobei ausgenutzt wird, dass \texttt{com} das Carry--Bit setzt. Diese und viele
andere nützliche Macro--Definitionen finden sich im File \texttt{b16-prim.asm}.

Auch das Wort \texttt{;} verhält sich anders als in Forth: Es kompiliert im Prinzip nur eine 
\texttt{ret}--Instruktion und kann also auch mitten im Wort stehen. Zusätzlich führt \texttt{;}
auch eine \emph{Tail--Call--Optimierung} durch, die abschließende Unterprogrammaufrufe
in Sprünge umwandelt, um den Return--Stack weniger zu belasten.
Das Wort \texttt{;;} beendet eine Definition, ohne ein \texttt{ret} zu assemblieren, und sorgt dafür, 
dass das letzte Instruktionswort
ggf.\ mit \texttt{nop}--Instruktionen aufgefüllt wird.

Unser Programm wird ab \texttt{\$2000} assembliert, da der {\sf b16-small} so
konfiguriert ist, dass dort bis \texttt{\$3FFF} Boot-RAM liegt (vgl.\ \texttt{b16-top.v}):

\begin{verbatim}
 ...
 always @(r or w or sel or addr_i or SRAM_DQ)
  begin
   data <= 0;
   casez({ r, sel })
     4'b1100: data <= sfr_data;
     4'b1010: data <= { bootramh[addr_i[12:1]], 
                        bootraml[addr_i[12:1]] };
     4'b1001: data <= SRAM_DQ;
   endcase // case(sel)
 end
 
 always @(addr)
  if(addr[15:8] == 8'hff)      sel <= 3'b100;
  else if(addr[15:13] == 3'h1) sel <= 3'b010;
  else                         sel <= 3'b001;
 ...
\end{verbatim} 

Den anderen Speicherbereichen ist Peripherie (sfr=Special Function Register, \texttt{\$FF00} bis \texttt{\$FFFF}) 
und Block--RAM (\texttt{\$0000} bis \texttt{\$1FFF} und \texttt{\$4000} bis \texttt{\$FEFF}) zugeordnet.

Bei einem Reset führt {\sf b16-small} seine erste Instruktion an der Adresse \texttt{\$3FFE} aus. An dieser Stelle assemblieren
wir einen Unterprogrammaufruf zu unserem Programm \texttt{boot}.

Das Programm wird mit \texttt{./b16-asm hello-b16.asm} übersetzt und erzeugt
unter anderem die beiden Files \texttt{b16h.hex} und \texttt{b16l.hex}, in denen die höher-- und niederwertigen Bytes
des {\sf b16-small}--Maschinenprogramms liegen. Wir können uns aber auch das File \texttt{b16.hex} ansehen,
das noch 16--Bit--Worte enthält. Vielleicht ist es ganz interessant, anhand der Befehlstabelle einmal 
selbst die Instruktionen zu dekodieren? (Sprünge gehen bei {\sf b16-small} immer an gerade Adressen,
das Sprungziel in Sprung--Instruktionen wird um ein Bit nach links geschoben.) 

\begin{footnotesize}
\begin{verbatim}
@0000 5EEC \ 0000-10111-10111-01100   nop clit clit +
@0001 0304 \ Operanden für die clits  3 4
@0002 4D80 \ 0000-10011-01100-00000   nop lit + nop
@0003 FFFF \ Operand für lit          -1
@0004 0802 \ 0000-00010-00000-00010   nop jmp 2
@0005 0000 \                          nop nop nop nop
@0006 0000 \                          nop nop nop nop
...
@0FFF 9000 \ 0001-00100-00000-00000   call 2000
\end{verbatim}
\end{footnotesize}

Die {\sf b16-small}-Verilog--Beschreibung (vgl.\ \texttt{b16top.v}) bindet die Hex-Files ein, um damit 
den {\sf b16}-Speicher zu ini\-ti\-ali\-sie\-ren. 

Ein Lauf des {\sf b16-small}--Programms könnte so aussehen:

\begin{verbatim}
P    Inst/Slot  op      TOS  NOS
4000 9000/0     01 call 0000 0000   
2002 5EEC/0     00 nop  0000 0000 
2002 5EEC/1     17 litc 0000 0000 
2003 5EEC/2     17 litc 0003 0000 
2004 5EEC/3     0C +    0004 0003 
2006 4D80/0     00 nop  0007 0000 
2006 4D80/1     13 lit  0007 0000 
2008 4D80/2     0C +    FFFF 0007 
2008 4D80/3     00 nop  0006 0000 
200A 0802/0     00 nop  0006 0000 
200A 0802/1     02 jmp  0006 0000  
2006 4D80/0     00 nop  0006 0000 
2006 4D80/1     13 lit  0006 0000 
2008 4D80/2     0C +    FFFF 0006 
2008 4D80/3     00 nop  0005 0000 
200A 0802/0     00 nop  0005 0000 
200A 0802/1     02 jmp  0005 0000
...
\end{verbatim}

Der Programmzähler P enthält dabei immer die Adresse der nächsten Instruktion, da er durch 
das Laden des Instruktionsregisters bereits erhöht wird.

\section{Auf der Hardware ausführen}

Um dieses Programm mit dem {\bf b16-small} auf dem FPGA--Board 
laufen zu lassen, öffnen wir in Quartus das {\sf b16-small}--Projekt--File \texttt{b16.qpf}. Das Design kann
dann mit {\sf Processing>Start Compilation} übersetzt werden. Es entsteht ein {\sf b16-small} aus der Verilog--Beschreibung
mit zugehörigem Binärprogramm in den \texttt{.hex}--Files. Diese Übersetzung sollte ohne Fehler durchlaufen und
das Ergebnis dann auf das DE1--Board geladen werden ({\sf Tools>Programmer>Start}). 

Aber, oh! Enttäuschung! Außer dass ein paar Leuchtdioden angehen und einige aus 
bleiben\footnote{Einige Signalleitungen sind an die grünen Leuchtdioden angeschlossen:\\ \texttt{assign LEDG = \{ SRAM\_WE\_N, SRAM\_CE\_N, SRAM\_OE\_N, SRAM\_UB\_N, SRAM\_LB\_N, sel\};}, vgl.\ \texttt{b16top.v}}%
, kann man nicht beobachten,
ob unser Programm läuft oder ob überhaupt irgendwas funktioniert.

Zum Glück lässt sich die auf dem DE1--Board vorhandene 7--Segment--Anzeige zur Darstellung von Werten verwenden. Sie ist
im Peripherie--Bereich an der Adresse \texttt{\$FF00} zu finden. Wir ergänzen unser Programm um

\begin{verbatim}
macro: ! ( a b -- )  !. drop  end-macro

: boot
    3 #c 4 #c +
    
    dup $FF00 # !
    
    BEGIN -1 # +   
    AGAIN 
;;
\end{verbatim}

% $ Syntax Highlight

und geben unser Ergebnis so auf der 7--Segment--Anzeige aus.

Im File \texttt{regmap.asm} werden symbolische Namen für angeschlossene Peripherie vereinbart. Dort hat die 7--Segment--Anzeige den Namen \texttt{LED7}, den wir auch hätten verwenden können, wenn wir mit \texttt{include regmap.asm} die Definitionen eingebunden hätten. Der Anschluss der 7--Segment--Anzeige selbst an den Prozessor ist im \mbox{File} \texttt{sfr.v} beschrieben. Die Dekodierung der 7--Segment--Elemente
wird in den von Altera bereitgestellten Files \texttt{SEG7\_LUT.v} und \texttt{SEG7\_LUT\_4.v} definiert und ist in Abbildung \vref{fpga:7segment} auszugsweise dargestellt.  

Wir übersetzen das Programm und das Design erneut und nach dem Laden in den FPGA ertönt ein Freudenschrei: Die 7--Segment--Anzeige zeigt 
\texttt{0007}! Unser erstes {\sf b16-small}--Programm läuft!

Aber auch das Zählen würden wir ja gerne sehen. Wir ändern unser Programm abermals:

\begin{verbatim}
include regmap.asm

$2000 org

: wait ( u -- ) 
    BEGIN
      dup
    WHILE
      1000 # BEGIN -1 # + dup  -UNTIL drop
      -1 # +
    REPEAT drop
;
      
: boot
    3 #c 4 #c +
    
    dup LED7 # !
    
    BEGIN -1 # +  
       dup LED7 # ! 
       1000 # wait  
    AGAIN 
;;
\end{verbatim}
% $ Syntax Highlite

In der Endlos--Schleife geben wir den Zähler aus, warten aber eine Weile, damit unser langsames Auge auch sehen kann, was da passiert:
Countdown. Das Warten wird durch das Wort \texttt{wait} erledigt, das einfach CPU--Zyklen verbrät. Da kommt natürlich sofort der
Wunsch nach einem richtigen Timer auf\ldots Was für die zukünftigen Überlegungen.


\section*{Ausblick}
Wir haben unser erstes {\sf b16-small}--Programm geschrieben und auf dem FPGA--Board laufen lassen. Die 7--Segment--Anzeige können wir
von Programmen aus ansteuern. Um in die {\sf b16}--Interna hineinzusehen, wäre es aber auch sinnvoll, die Anzeige vielleicht direkt an das P--Register oder an TOS zu knüpfen. Dazu müssen wir den {\sf b16}--Verilog--Code anpassen. Dieser Aufgabe werden wir uns im nächsten Teil dieser Artikelserie widmen. Auch wollen wir dann einen Piezo einsetzen, um ein wenig Rabatz--IO zu machen.

\end{multicols}
\vspace*{-7mm}
\section*{Literatur}
\vspace*{-2mm}
\begin{small}
{}[1] \url{http://www.colorforth.com/inst.htm} Homepage von Charles Moore, Forth--Prozessor {\sf c18}\\
{}[2] \url{http://www.jwdt.com/~paysan/b16.pdf} b16 — Ein Forth Prozessor im FPGA, Bernd Paysan, Forth Tagung 2003\\
{}[3] \url{http://www.jwdt.com/~paysan/b16.pdf} b16-small — Less is More, Bernd Paysan, EuroForth 2004\\
{}[4] \url{http://www.forth-ev.de/repos/b16-small} b16-small SVN--Repository\\
{}[5] \url{http://tortoisesvn.tigris.org/} TortoiseSVN, Windows--Explorer--Integration für Subversion
\end{small}
\vspace*{-1ex}
\begin{figure}
\begin{samepage}
\begin{multicols}{2}
\begin{footnotesize}
\texttt{SEG7\_LUT.v}
\begin{quote}
\begin{listing}{1}
module SEG7_LUT(oSEG, iDIG);
input  [3:0] iDIG;
output [6:0] oSEG;
reg    [6:0] oSEG;

always @(iDIG) begin
    case(iDIG)
    4'h1: oSEG = 7'b1111001;        // ---t----
    4'h2: oSEG = 7'b0100100;        // |      |
    4'h3: oSEG = 7'b0110000;        // lt    rt
    4'h4: oSEG = 7'b0011001;        // |      |
    4'h5: oSEG = 7'b0010010;        // ---m----
    4'h6: oSEG = 7'b0000010;        // |      |
    4'h7: oSEG = 7'b1111000;        // lb    rb
    4'h8: oSEG = 7'b0000000;        // |      |
    4'h9: oSEG = 7'b0011000;        // ---b----
    4'ha: oSEG = 7'b0001000;
    4'hb: oSEG = 7'b0000011;
    4'hc: oSEG = 7'b1000110;
    4'hd: oSEG = 7'b0100001;
    4'he: oSEG = 7'b0000110;
    4'hf: oSEG = 7'b0001110;
    4'h0: oSEG = 7'b1000000;
endcase end endmodule
\end{listing}
\end{quote}
\columnbreak
\texttt{SEG7\_LUT\_4.f}
\begin{quote}
\begin{listing}{1}
module SEG7_LUT_4 (oSEG0, oSEG1, oSEG2, oSEG3, iDIG);
input  [15:0] iDIG;
output [6:0]  oSEG0, oSEG1, oSEG2, oSEG3;

SEG7_LUT u0 (oSEG0, iDIG[3:0]);
SEG7_LUT u1 (oSEG1, iDIG[7:4]);
SEG7_LUT u2 (oSEG2, iDIG[11:8]);
SEG7_LUT u3 (oSEG3, iDIG[15:12]);

endmodule
\end{listing}
\end{quote}

aus \texttt{b16top.v}
\begin{quote}
\begin{listing}{222}
  SEG7_LUT_4 u0 (HEX0, HEX1, HEX2, HEX3, LED7);
\end{listing}
\end{quote}
\end{footnotesize}
\end{multicols}\nopagebreak
\vspace*{-3ex}
\caption{\label{fpga:7segment}Die Dekodierung für die 7--Segment--Anzeige}
\end{samepage}
\end{figure}
%\newpage

%\begin{quote}
%\begin{small}
%\label{fpga:listing}
% \listinginput[1]{1}{2009-01/DE1LEDs.v}
%\end{small}
%\end{quote}

\end{document}

