%
% Mite's object format
%
% Reuben Thomas
%
% made HeVeA-friendly 2/6/06
%


\documentclass{article}
\usepackage{a4,mite,bitfield}


\title{Mite's object format}
\author{Reuben Thomas}
\date{6th November 2000}

\begin{document}
\maketitle

\section{Introduction}

Mite's assembler writes object modules in the format given below, which is a direct encoding of the concrete syntax.


\section{Presentation}

Hexadecimal numbers are followed by an ``h''; for example, $100=64\mathrm{h}$. Binary numbers are similarly suffixed ``b''.

The encoding is presented diagrammatically. Boxes representing bit fields are concatenated to make bytes or larger words:

\begin{center}
\begin{bitfield}{8}
\bits[r]{3}{3}{}\bits[r]{1}{1}{}\bits[r]{4}{4}{} \\
\end{bitfield}
\end{center}
\noindent These in turn are listed vertically. The contents of a bit field is given either as literal binary digits (\conc{01101001}), or as a \bitname{name}. Fields are usually labelled with their width:

\begin{center}
\begin{bitfield}{8}
\bits[r]{5}{5}{}\bits[r]{3}{3}{} \\
\end{bitfield}
\end{center}
\noindent The most significant bit is at the left-hand end of the word, and the least significant at the right-hand end. Multi-byte words are stored with their bytes in little-endian order.

Boxes labelled in ordinary type (box) represent units which themselves have internal structure. Boxes labelled in italics (\bitnum{scatola}) are numbers (see section~\ref{obj:number}). Optional units are shown as dashed boxes:

\begin{center}
\begin{bitfield}{1}
\bits[dr]{1}{1}{} \\
\end{bitfield}
\end{center}
\noindent Lists are denoted by a stack:

\begin{center}
\begin{bitfield}{1}
\bitstack{}{1}{\bits[r]{1}{1}{}} \\
\end{bitfield}
\end{center}

\section{Number\label{obj:number}}

Unsigned numbers are encoded as follows:

\begin{enumerate}
\item A list of 7-bit words is formed by repeatedly removing the least significant seven bits of the number until none of the remaining bits is set.
\item The 7-bit words are turned into bytes by the addition of a bit at the most significant end, which is zero for all the quantities except the first.
\item The bytes are stored in the reverse order to that in which they were generated.
\end{enumerate}
Signed numbers are encoded in the same way except that the list is formed by repeatedly removing the least significant seven bits of the number until all the remaining bits are the same as the most significant bit of the previous 7-bit word. Three-component numbers are encoded as three consecutive numbers.


\subsection{Width\label{obj:width}}

Widths of quantities are encoded as

\begin{center}
\begin{tabular}{cc} \toprule
\bf Width & \bf Code \\ \midrule
\conc{1} & 00b \\
\conc{2} & 01b \\
\conc{4} & 10b \\
\conc{a} & 11b \\
\bottomrule \end{tabular}
\end{center}

\section{Identifier\label{obj:identifier}}

All strings are ASCII-encoded, preceded by a number giving their length.


\section{Item}

Stack items are encoded as a number (see section~\ref{obj:number}).


\section{Address\label{obj:address}}

Local addresses give the number of a label (see section~\ref{obj:location}), and are stored as a number. External addresses are stored as an identifier.\pagebreak

Address types are encoded as

\begin{center}
\begin{tabular}{cc} \toprule
\bf Type & \bf Code \\ \midrule
Register & 00b \\
Local label & 01b \\
Global label & 10b \\
\bottomrule \end{tabular}
\end{center}

\section{Manifest\label{obj:manifest}}

The type of a manifest quantity is given by an \bitname{op type} field, which is encoded as

\begin{center}
\begin{tabular}{lc} \toprule
\multicolumn{1}{c}{\bf Operand type} & \bf\bitname{op type} \\ \midrule
number & 000b \\
3-component number & 001b \\
constant & 010b \\
local label & 100b \\
local label plus offset & 101b \\
external label & 110b \\
external label plus offset & 111b \\
\bottomrule \end{tabular}
\end{center}
\noindent Constants are encoded as a single byte; for \conc{ashift} the byte is 00h. A label expression is represented as the number or name of the label followed by the offset, which is a three-component number (see section~\ref{obj:number}).


\section{Lists\label{obj:lists}}

The list elements are stored consecutively. The length is encoded as a number directly before the list elements.


\section{Instruction}

Instructions are encoded as the opcode followed by the operands, encoded in order from left to right. The operands are encoded as in the preceding sections; lists of items and types enclosed in brackets are stored as lists.\pagebreak


\subsection{\conc{MOV} and \conc{DEF}}

A \conc{MOV} instruction whose second operand is a register is encoded as 0000~0000b. \conc{DEF} and \conc{MOV} with a manifest second operand are encoded as

\begin{center}
\begin{bitfield}{8}
\bitsl{1}{0}\bitsl{3}{011}\bitsn{1}{inst}\bitsn{3}{op type} \\
\end{bitfield}
\end{center}
\noindent where the \bitname{inst} bit is clear for \conc{MOV} and set for \conc{DEF}, and the \bitname{op type} field gives the type of the value, encoded as in section~\ref{obj:manifest}.


\subsection{Data processing}


\subsubsection{Three-operand}

\begin{center}
\begin{bitfield}{8}
\bitsl{1}{0}\bitsn{3}{inst}\bitsl{3}{011}\bitsn{1}{dest}
\end{bitfield}
\end{center}
\noindent The \bitname{inst} field indicates the instruction:

\begin{center}
\begin{tabular}{cc} \toprule
\bf Instruction & \bf\bitname{inst} \\ \midrule
\conc{ADD} & 000b \\
\conc{SUB} & 001b \\
\conc{AND} & 010b \\
\conc{OR} & 100b \\
\conc{XOR} & 101b \\
\bottomrule \end{tabular}
\end{center}
\noindent The \bitname{dest} bit is set if the destination is present.


\subsubsection{Four-operand}

\begin{center}
\begin{bitfield}{8}
\bitsl{1}{0}\bitsn{2}{inst}\bitsl{3}{011}\bitsn{1}{quot}\bitsn{1}{rem}
\end{bitfield}
\end{center}
\noindent The \bitname{inst} field indicates the instruction:

\begin{center}
\begin{tabular}{cc} \toprule
\bf Instruction & \bf\bitname{inst} \\ \midrule
\conc{DIV} & 00b \\
\conc{DIVS} & 01b \\
\conc{DIVSZ} & 10b \\
\bottomrule \end{tabular}
\end{center}
\noindent The \bitname{quot} bit is set if the first destination is present, and the \bitname{rem} bit if the second destination is present.


\subsection{Memory}

\begin{center}
\begin{bitfield}{8}
\bitsl{1}{0}\bitsn{1}{inst}\bitsl{3}{011}\bitsn{1}{off}\bitsn{2}{width}
\end{bitfield}
\end{center}
\noindent The \bitname{inst} bit is clear for \conc{LD} and set for \conc{ST}. The \bitname{off} bit is set if a third (offset) register is given. The \bitname{width} field gives the width of the quantities being transferred, encoded as in section~\ref{obj:width}.


\subsection{Branch}

\begin{center}
\begin{bitfield}{8}
\bitsl{2}{11}\bitsn{2}{adr}\bitsn{4}{condition} \\
\end{bitfield}
\end{center}
\noindent The \bitname{adr} field encodes the address type as in section~\ref{obj:address}. The condition is encoded as

\begin{center}
\begin{tabular}{cc} \toprule
\bf Condition & \bf\bitname{condition} \\ \midrule
\conc{AL} & 0001b \\
\conc{EQ} & 0010b \\
\conc{NE} & 0011b \\
\conc{MI} & 0100b \\
\conc{PL} & 0101b \\
\conc{CS} & 0110b \\
\conc{CC} & 0111b \\
\conc{VS} & 1000b \\
\conc{VC} & 1001b \\
\conc{HI} & 1010b \\
\conc{LS} & 1011b \\
\conc{LT} & 1100b \\
\conc{GE} & 1101b \\
\conc{LE} & 1110b \\
\conc{GT} & 1111b \\
\bottomrule \end{tabular}
\end{center}

\subsection{Call and return}

\conc{CALL} is encoded as

\begin{center}
\begin{bitfield}{8}
\bitsl{3}{011}\bitsn{1}{f}\bitsn{1}{c}\bitsn{1}{v}\bitsn{2}{adr} \\
\end{bitfield}
\end{center}
\noindent where the \bitname{f} bit is set for \conc{CALLF}, the \bitname{c} bit is set if the \conc{C} modifier is used, and the \bitname{v} bit if the \conc{V} modifier is used. The \bitname{adr} field encodes the address type as in section~\ref{obj:address}. The argument types are alternately 1 and 3-component numbers.\pagebreak

\conc{RET} is encoded as

\begin{center}
\begin{bitfield}{8}
\bitsl{4}{1000}\bitsl{3}{011}\bitsn{1}{f} \\
 \end{bitfield}
\end{center}
\noindent where the \conc{f} bit is set for \conc{RETF}.


\subsection{\conc{SYNC}}

\noindent \conc{SYNC} is encoded as a separate instruction immediately following the instruction to which it is attached. Its opcode is 0001~0101b. It is not counted as a separate directive in the count in the module header (see section~\ref{obj:module}).


\subsection{\conc{NEW}}

\begin{center}
\begin{bitfield}{8}
\bitsl{4}{1001}\bitsl{3}{011}\bitsn{1}{c} \\
\end{bitfield}
\end{center}
\noindent If the \bitname{c} bit is set, a chunk is being declared.


\subsection{Datum}


\subsubsection{Literal}

\begin{center}
\begin{bitfield}{8}
\bitsl{3}{011}\bitsn{2}{width}\bitsn{3}{op type} \\
\bitstack{}{8}{\bits{}{8}{manifest}} \\
\end{bitfield}
\end{center}
\noindent The \bitname{width} field gives the width of the literals. The \bitname{op type} field gives the literal type, encoded as in section~\ref{obj:manifest}. The list of manifests follows.


\subsubsection{Space}

\begin{center}
\begin{bitfield}{8}
\bitsl{2}{00}\bitsl{3}{011}\bitsn{1}{zero}\bitsn{2}{width} \\
\end{bitfield}
\end{center}
\noindent The \bitname{zero} bit is set if the space is zero-initialised; the \bitname{width} field gives the width of the words being reserved.\pagebreak


\subsection{Other instructions\label{obj:other}}

The remaining instructions are encoded thus:

\begin{center}
\begin{tabular}{cc} \toprule
\bf Instruction & \bf\bitname{inst} \\ \midrule
\conc{UNDEF} & 0000 0001b\\
\conc{SWAP} & 0000 0010b\\
\conc{NEG} & 0000 0100b \\
\conc{NOT} & 0000 0101b \\
\conc{MUL} & 0000 1000b \\
\conc{SL} & 0000 1001b \\
\conc{SRL} & 0000 1010b \\
\conc{SRA} & 0001 0000b \\
\conc{COPY} & 0001 0001b \\
\conc{CATCH} & 0001 0010b \\
\conc{THROW} & 0001 0100b \\
\conc{KILL} & 0010 0000b \\
\conc{RANK} & 0010 0001b \\
\conc{REBIND} & 0010 0010b \\
\conc{ESC} & 0010 0100b \\
\bottomrule \end{tabular}
\end{center}


\section{Location\label{obj:location}}

Labellings, handlers and subroutines are encoded thus:

\begin{center}
\begin{bitfield}{8}
\bitsl{2}{10}\bitsl{3}{011}\bitsn{2}{lab type}\bitsn{1}{ind} \\
\bits[d]{}{8}{name} \\
\end{bitfield}
\end{center}

\noindent The \bitname{lab type} field gives the type of label, encoded as

\begin{center}
\begin{tabular}{cc} \toprule
\bf Label type & \bf \bitname{lab type} \\ \midrule
ordinary & 00b \\
handler & 01b \\
subroutine & 10b \\
leaf subroutine & 11b \\
\bottomrule \end{tabular}
\end{center}

\noindent If the \bitname{ind} bit is set the label is indirectable. A public label has an identifier after the opcode byte, starting with an underscore. (This means that the encoding is ambiguous, as the underscore could also represent part of another instruction.)

The labels are numbered consecutively from one.\pagebreak

Functions are encoded

\begin{center}
\begin{bitfield}{8}
\bitsl{1}{1}\bitsl{3}{011}\bitsn{1}{l}\bitsn{1}{v}\bitsn{1}{c}\bitsn{1}{pub} \\
\bits[d]{}{8}{name} \\
\end{bitfield}
\end{center}
\noindent where the \bitname{l} bit is set if the function is a leaf, the \bitname{v} bit is set if it is variadic, the \bitname{c} bit is set if it returns a chunk, and the \bitname{pub} bit if the label is public. A public function has an identifier after the opcode byte.


\section{Data}

\begin{center}
\begin{bitfield}{8}
\bitsl{3}{100}\bitsl{3}{011}\bitsn{1}{ro}\bitsn{1}{pub} \\
\bits[d]{}{8}{name} \\
\end{bitfield}
\end{center}
\noindent If the \bitname{ro} bit is set the following data is read-only; otherwise it is read-write. If the \bitname{pub} bit is set it is public, otherwise it is private. A public data label has an identifier after the opcode byte.


\section{Module\label{obj:module}}

\begin{center}
\begin{bitfield}{1}
\bits{}{1}{header} \\
\bitstack{}{1}{\bits{}{1}{directive}} \\
\end{bitfield}
\end{center}
\noindent A module consists of a header and a list of directives.

\begin{center}
\begin{bitfield}{32}
\bitsl{32}{AD2BC0DEh} \\
\bitsn{8}{version} \\
\bitsn{24}{length} \\
\bits{}{32}{\textit{labels}} \\
\end{bitfield}
\end{center}
\noindent The header starts with a magic number. Next comes a byte containing the version number of the encoding. The current version number is 0. Next comes the length of the module in bytes excluding the header, and finally the number of labels.

\end{document}
