path: root/doc/mdk_tut.texi

@c -*-texinfo-*-
@c This is part of the GNU MDK Reference Manual.
@c Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2014, 2020
@c   Free Software Foundation, Inc.
@c See the file mdk.texi for copying conditions.

@node MIX and MIXAL tutorial, Getting started, Installing MDK, Top
@comment  node-name,  next,  previous,  up
@chapter MIX and MIXAL tutorial
@cindex MIX
@cindex MIXAL

In the book series @cite{The Art of Computer Programming}, by D. Knuth,
a virtual computer, the MIX, is used by the author (together with the
set of binary instructions that the virtual CPU accepts) to illustrate
the algorithms and skills that every serious programmer should
master. Like any other real computer, there is a symbolic assembler
language that can be used to program the MIX: the MIX assembly language,
or MIXAL for short.  In the following subsections you will find a tutorial
on these topics, which will teach you the basics of the MIX architecture
and how to program a MIX computer using MIXAL.

@menu
* The MIX computer::            Architecture and instruction set
                                of the MIX computer.
* MIXAL::                       The MIX assembly language.
@end menu

@node The MIX computer, MIXAL, MIX and MIXAL tutorial, MIX and MIXAL tutorial
@comment  node-name,  next,  previous,  up
@section The MIX computer

In this section, you will find a description of the MIX computer,
its components and instruction set.

@menu
* MIX architecture::
* MIX instruction set::
@end menu

@node MIX architecture, MIX instruction set, The MIX computer, The MIX computer
@comment  node-name,  next,  previous,  up
@subsection MIX architecture
@cindex byte
@cindex MIX byte
@cindex word
@cindex MIX word
@cindex MIX architecture
@cindex MIX computer
@cindex register
@cindex MIX register
@cindex field specification
@cindex fspec
@cindex instruction
@cindex MIX instruction
@cindex address
@cindex memory cell
@cindex cell
@cindex memory
@cindex index

The basic information storage unit in the MIX computer is the
@dfn{byte}, which stores positive values in the range 0-63 . Note that a
MIX byte can be then represented as 6 bits, instead of the common 8 bits
for a @emph{regular} byte. Unless otherwise stated, we shall use the
word @dfn{byte} to refer to a MIX 6-bit byte.

A MIX @dfn{word} is defined as a set of 5 bytes plus a sign. The bytes
within a word are numbered from 1 to 5, being byte number one the most
significant one. The sign is denoted by index 0. Graphically,

@example
 -----------------------------------------------
|   0   |   1   |   2   |   3   |   4   |   5   |
 -----------------------------------------------
|  +/-  | byte  | byte  | byte  | byte  | byte  |
 -----------------------------------------------
@end example
@noindent
Sample MIX words are @samp{- 12 00 11 01 63} and @samp{+ 12 11 34 43
00}.

You can refer to subfields within a word using a @dfn{field
specification} or @dfn{fspec} of the form ``(@var{L}:@var{R})'', where
@var{L} denotes the first byte, and @var{R} the last byte of the
subfield.
When @var{L} is zero, the subfield includes the word's
sign. An fspec can also be represented as a single value @code{F}, given
by @code{F = 8*L + R} (thus the fspec @samp{(1:3)}, denoting the first
three bytes of a word, is represented by the integer 11).

The MIX computer stores information in @dfn{registers}, that can store
either a word or two bytes and sign (see below), and @dfn{memory cells},
each one containing a word. Specifically, the MIX computer has 4000
memory cells with addresses 0 to 3999 (i.e., two bytes are enough to
address a memory cell) and the following registers:

@cindex rA
@cindex rX
@cindex rJ
@cindex rIn
@cindex register

@table @asis
@item @code{rA}
A register. General purpose register holding a word. Usually its
contents serves as the operand of arithmetic and storing instructions.
@item @code{rX}
X register. General purpose register holding a word. Often it acts as an
extension or a replacement of @samp{rA}.
@item @code{rJ}
J (jump) register. This register stores positive two-byte values,
usually representing a jump address.
@item @code{rI1}, @code{rI2}, @code{rI3}, @code{rI4}, @code{rI5}, @code{rI6}
Index registers. These six registers can store a signed two-byte
value. Their contents are used as indexing values for the computation of
effective memory addresses.
@end table

@cindex @sc{ov}
@cindex @sc{cm}
@cindex @code{un}
@cindex overflow toggle
@cindex comparison indicator
@cindex input-output devices
@noindent
In addition, the MIX computer contains:

@itemize @minus
@item
An @dfn{overflow toggle} (a single bit with values @dfn{on} or
@dfn{off}). In this manual, this toggle is denoted @sc{ov}.
@item
A @dfn{comparison indicator} (having three values: @dfn{EQUAL},
@dfn{GREATER} or @dfn{LESS}). In this manual, this indicator is denoted
@sc{cm}, and its possible values are abbreviated as @dfn{E}, @dfn{G} and
@dfn{L}.
@item
Input-output block devices. Each device is labelled as @code{un}, where
@code{n} runs from 0 to 20. In Knuth's definition, @code{u0} through
@code{u7} are magnetic tape units, @code{u8} through @code{15} are disks
and drums, @code{u16} is a card reader, @code{u17} is a card writer,
@code{u18} is
a line printer and, @code{u19} is a typewriter terminal, and @code{u20},
a paper tape. Our implementation maps these devices to disk files,
except for @code{u19}, which represents the standard output.
@end itemize

As noted above, the MIX computer communicates with the external world by
a set of input-output devices which can be ``connected'' to it. The
computer interchanges information using blocks of words whose length
depends on the device at hand (@pxref{Devices}). These words are
interpreted by the device either as binary information (for devices
0-16), or as representing printable characters (devices 17-20). In the
last case, each MIX byte is mapped onto a character according to the
following table:

@multitable  {00} {C} {00} {C} {00} {C} {00} {C}
@item  00 @tab  @tab 01 @tab A @tab 02 @tab B @tab 03 @tab C
@item  04 @tab D @tab 05 @tab E @tab 06 @tab F @tab 07 @tab G
@item  08 @tab H @tab 09 @tab I @tab 10 @tab ~ @tab 11 @tab J
@item  12 @tab K @tab 13 @tab L @tab 14 @tab M @tab 15 @tab N
@item  16 @tab O @tab 17 @tab P @tab 18 @tab Q @tab 19 @tab R
@item  20 @tab [ @tab 21 @tab # @tab 22 @tab S @tab 23 @tab T
@item  24 @tab U @tab 25 @tab V @tab 26 @tab W @tab 27 @tab X
@item  28 @tab Y @tab 29 @tab Z @tab 30 @tab 0 @tab 31 @tab 1
@item  32 @tab 2 @tab 33 @tab 3 @tab 34 @tab 4 @tab 35 @tab 5
@item  36 @tab 6 @tab 37 @tab 7 @tab 38 @tab 8 @tab 39 @tab 9
@item  40 @tab . @tab 41 @tab , @tab 42 @tab ( @tab 43 @tab )
@item  44 @tab + @tab 45 @tab - @tab 46 @tab * @tab 47 @tab /
@item  48 @tab = @tab 49 @tab $ @tab 50 @tab < @tab 51 @tab >
@item  52 @tab @@ @tab 53 @tab ; @tab 54 @tab : @tab 55 @tab '
@end multitable
@noindent
The value 0 represents a whitespace. The characters @code{~}, @code{[} and
@code{#} correspond to symbols not representable as ASCII characters
(uppercase delta, sigma and gamma, respectively), and byte values 56-63
have no associated character.

Finally, the MIX computer features a virtual CPU which controls the
above components, and which is able to execute a rich set of
instructions (constituting its machine language, similar to those
commonly found in real CPUs), including arithmetic, logical, storing,
comparison and jump instructions. Being a typical von Neumann computer,
the MIX CPU fetches binary instructions from memory sequentially (unless
a jump instruction is found), and stores the address of the next
instruction to be executed in an internal register called @dfn{location
counter} (also known as program counter in other architectures).

The next section, @xref{MIX instruction set}, gives a complete description
of the available MIX binary instructions.

@node MIX instruction set,  , MIX architecture, The MIX computer
@comment  node-name,  next,  previous,  up
@subsection MIX instruction set
@cindex instruction set

The following subsections fully describe the instruction set of the MIX
computer. We begin with a description of the structure of binary
instructions and the notation used to refer to their subfields. The
remaining subsections are devoted to describing the actual instructions
available to the MIX programmer.

@menu
* Instruction structure::
* Loading operators::
* Storing operators::
* Arithmetic operators::
* Address transfer operators::
* Comparison operators::
* Jump operators::
* Input-output operators::
* Conversion operators::
* Shift operators::
* Miscellaneous operators::
* Execution times::
@end menu

@node Instruction structure, Loading operators, MIX instruction set, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Instruction structure

MIX @dfn{instructions} are codified as words with the following subfield
structure:

@multitable @columnfractions .15 .20 .65
@item @emph{Subfield} @tab @emph{fspec} @tab @emph{Description}
@item ADDRESS @tab (0:2)
@tab The first two bytes plus sign are the @dfn{address} field. Combined
with the INDEX field, denotes the memory address to be used by the
instruction.
@item INDEX @tab (3:3)
@tab The third byte is the @dfn{index}, normally used for indexing the
address@footnote{The actual memory address the instruction refers to, is
obtained by adding to ADDRESS the value of the @samp{rI} register
denoted by INDEX.}.
@item MOD @tab (4:4)
@tab Byte four is used either as an operation code modifier or as a field
specification.
@item OPCODE @tab (5:5)
@tab The last (least significant) byte in the word denotes the operation
code.
@end multitable

@noindent
or, graphically,

@example
 ------------------------------------------------
|   0   |   1   |   2   |   3   |   4   |   5    |
 ------------------------------------------------
|        ADDRESS        | INDEX |  MOD  | OPCODE |
 ------------------------------------------------
@end example

For a given instruction, @samp{M} stands for
the memory address obtained after indexing the ADDRESS subfield
(using its INDEX byte), and @samp{V} is the contents of the
subfield indicated by MOD of the memory cell with address @samp{M}. For
instance, suppose that we have the following contents of MIX registers
and memory cells:

@example
[rI2] = + 00 63
[31] = - 10 11 00 11 22
@end example
@noindent
where @samp{[n]} denotes the contents of the nth memory cell and
@samp{[rI2]} the contents of register @samp{rI2}@footnote{In general,
@samp{[X]} will denote the contents of entity @samp{X}; thus, by
definition, @w{@samp{V = [M](MOD)}}.}.  Let us consider the binary
instruction @w{@samp{I = - 00 32 02 11 10}}. For this instruction we
have:

@example
ADDRESS = - 00 32 = -32
INDEX = 02 = 2
MOD = 11 = (1:3)
OPCODE = 10

M = ADDRESS + [rI2] = -32 + 63 = 31
V = [M](MOD) = (- 10 11 00 11 22)(1:3) = + 00 00 10 11 00
@end example

Note that, when computing @samp{V} using a word and an fspec, we apply
a left padding to the bytes selected by @samp{MOD} to obtain a
complete word as the result.

In the following subsections, we will
assign to each MIX instruction a mnemonic, or symbolic name. For
instance, the mnemonic of @samp{OPCODE} 10 is @samp{LD2}. Thus we can
rewrite the above instruction as

@example
LD2  -32,2(1:3)
@end example
@noindent
or, for a generic instruction:

@example
MNEMONIC  ADDRESS,INDEX(MOD)
@end example
@noindent
Some instructions are identified by both the OPCODE and the MOD
fields. In these cases, the MOD will not appear in the above symbolic
representation. Also when ADDRESS or INDEX are zero, they can be
omitted.  Finally, MOD defaults to (0:5) (meaning the
whole word).

@node Loading operators, Storing operators, Instruction structure, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Loading operators
@cindex loading operators

The following instructions are used to load memory contents into a
register.

@ftable @code
@item LDA
Put in rA the contents of cell no. M.
OPCODE = 8, MOD = fspec. @code{rA <- V}.
@item LDX
Put in rX the contents of cell no. M.
OPCODE = 15, MOD = fspec. @code{rX <- V}.
@item LDi
Put in rIi the contents of cell no. M.
OPCODE = 8 + i, MOD = fspec. @code{rIi <- V}.
@item LDAN
Put in rA the contents of cell no. M, with opposite sign.
OPCODE = 16, MOD = fspec. @code{rA <- -V}.
@item LDXN
Put in rX the contents of cell no. M, with opposite sign.
OPCODE = 23, MOD = fspec. @code{rX <- -V}.
@item LDiN
Put in rIi the contents of cell no. M, with opposite sign.
OPCODE = 16 + i, MOD = fspec. @code{rIi <- -V}.
@end ftable

In all the above load instructions the @samp{MOD} field selects the
bytes of the memory cell with address @samp{M} which are loaded into the
requisite register (indicated by the @samp{OPCODE}).  For instance, the
word @w{@samp{+ 00 13 01 27 11}} represents the instruction

@example
LD3    13,1(3:3)
 ^      ^ ^  ^
 |      | |  |
 |      | |   --- MOD = 27 = 3*8 + 3
 |      |  --- INDEX = 1
 |       --- ADDRESS = 00 13
  --- OPCODE = 11
@end example
Let us suppose that, prior to this instruction execution, the state of
the MIX computer is the following:

@example
[rI1] = - 00 01
[rI3] = + 24 12
[12] = - 01 02 03 04 05
@end example
@noindent
As, in this case, @w{@samp{M = 13 + [rI1] = 12}}, we have

@example
V = [M](3:3) = (- 01 02 03 04 05)(3:3)
  = + 00 00 00 00 03
@end example
@noindent
(note that the specified subfield is left-padded with null bytes to
complete a word). Hence, the MIX state, after the instruction execution,
will be

@example
[rI1] = - 00 01
[rI3] = + 00 03
[12] = - 01 02 03 04 05
@end example

To further illustrate loading operators, the following table shows the
contents of @samp{rX} after different @samp{LDX} instructions:

@table @samp
@item LDX 12(0:0)     [rX] = - 00 00 00 00 00
@item LDX 12(0:1)     [rX] = - 00 00 00 00 01
@item LDX 12(3:5)     [rX] = + 00 00 03 04 05
@item LDX 12(3:4)     [rX] = + 00 00 00 03 04
@item LDX 12(0:5)     [rX] = - 01 02 03 04 05
@end table


@node Storing operators, Arithmetic operators, Loading operators, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Storing operators
@cindex storing operators

The following instructions are the inverse of the load
operations: they are used to store a subfield of a register
into a memory location. Here, MOD represents the subfield of the memory
cell that is to be overwritten with bytes from a register. These bytes
are taken beginning by the rightmost side of the register.

@ftable @code
@item STA
Store rA. OPCODE = 24, MOD = fspec. @code{V <- rA}.
@item STX
Store rX. OPCODE = 31, MOD = fspec. @code{V <- rX}.
@item STi
Store rIi. OPCODE = 24 + i, MOD = fspec. @code{V <- rIi}.
@item STJ
Store rJ. OPCODE = 32, MOD = fspec. @code{V <- rJ}.
@item STZ
Store zero. OPCODE = 33, MOD = fspec. @code{V <- 0}.
@end ftable

By way of example, consider the instruction @samp{STA 1200(2:3)}. It
causes the MIX to fetch bytes no. 4 and 5 of register A and copy them to
bytes 2 and 3 of memory cell no. 1200 (remember that, for these
instructions, MOD specifies a subfield of @emph{the memory
address}). The other bytes of the memory cell retain their
values. Thus, if prior to the instruction execution we have

@example
[1200] = - 20 21 22 23 24
[rA] = + 01 02 03 04 05
@end example
@noindent
we will end up with

@example
[1200] = - 20 04 05 23 24
[rA] = + 01 02 03 04 05
@end example

As a second example, @samp{ST2 1000(0)} will set the sign of
@samp{[1000]} to that of @samp{[rI2]}.

@node Arithmetic operators, Address transfer operators, Storing operators, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Arithmetic operators
@cindex arithmetic operators

The following instructions perform arithmetic operations between rA and
rX register and memory contents.

@ftable @code
@item ADD
Add and set OV if overflow. OPCODE = 1, MOD = fspec.
@w{@code{rA <- rA +V}}.
@item SUB
Sub and set OV if overflow. OPCODE = 2, MOD = fspec.
@w{@code{rA <- rA - V}}.
@item MUL
Multiply V times rA and store the 10-bytes product in rAX.
OPCODE = 3, MOD = fspec. @w{@code{rAX <- rA x V}}.
@item DIV
rAX is considered a 10-bytes number, and it is divided by V.
OPCODE = 4, MOD = fspec. @w{@code{rA <- rAX / V}}, @code{rX} <- reminder.
@end ftable

In all the above instructions, @samp{[rA]} is one of the operands
of the binary arithmetic operation, the other being @samp{V} (that is,
the specified subfield of the memory cell with address @samp{M}), padded
with zero bytes on its left-side to complete a word. In multiplication
and division, the register @samp{X} comes into play as a right-extension
of the register @samp{A}, so that we are able to handle 10-byte numbers
whose more significant bytes are those of @samp{rA} (the sign of this
10-byte number is that of @samp{rA}: @samp{rX}'s sign is ignored).

Addition and subtraction of MIX words can give rise to overflows, since
the result is stored in a register with room to only 5 bytes (plus
sign). When this occurs, the operation result modulo @w{1,073,741,823}
(the maximum value storable in a MIX word) is stored in @samp{rA}, and
the overflow toggle is set to TRUE.

@node Address transfer operators, Comparison operators, Arithmetic operators, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Address transfer operators
@cindex address transfer operators

In these instructions, @samp{M} (the address of the instruction after
indexing) is used as a number instead of as the address of a memory
cell. Consequently, @samp{M} can have any valid word value (i.e., it's
not limited to the 0-3999 range of a memory address).

@ftable @code
@item ENTA
Enter @samp{M} in [rA]. OPCODE = 48, MOD = 2. @code{rA <- M}.
@item ENTX
Enter @samp{M} in [rX]. OPCODE = 55, MOD = 2. @code{rX <- M}.
@item ENTi
Enter @samp{M} in [rIi]. OPCODE = 48 + i, MOD = 2. @code{rIi <- M}.
@item ENNA
Enter @samp{-M} in [rA]. OPCODE = 48, MOD = 3. @code{rA <- -M}.
@item ENNX
Enter @samp{-M} in [rX]. OPCODE = 55, MOD = 3. @code{rX <- -M}.
@item ENNi
Enter @samp{-M} in [rIi]. OPCODE = 48 + i, MOD = 3. @code{rIi <- -M}.
@item INCA
Increase [rA] by @samp{M}. OPCODE = 48, MOD = 0. @code{rA <- rA + M}.
@item INCX
Increase [rX] by @samp{M}. OPCODE = 55, MOD = 0. @code{rX <- rX + M}.
@item INCi
Increase [rIi] by @samp{M}. OPCODE = 48 + i, MOD = 0. @code{rIi <- rIi + M}.
@item DECA
Decrease [rA] by @samp{M}. OPCODE = 48, MOD = 1. @code{rA <- rA - M}.
@item DECX
Decrease [rX] by @samp{M}. OPCODE = 55, MOD = 1. @code{rX <- rX - M}.
@item DECi
Decrease [rIi] by @samp{M}. OPCODE = 48 + i, MaOD = 0. @code{rIi <- rIi - M}.
@end ftable

In the above instructions, the subfield @samp{ADDRESS} acts as an
immediate (indexed) operand, and allow us to set directly the contents
of the MIX registers without an indirection to the memory cells (in a
real CPU this would mean that they are faster that the previously
discussed instructions, whose operands are fetched from memory). So, if
you want to store in @samp{rA} the value -2000 (- 00 00 00 31 16), you
can use the binary instruction @w{+ 31 16 00 03 48}, or, symbolically,

@example
ENNA 2000
@end example
@noindent
Used in conjunction with the store operations (@samp{STA}, @samp{STX},
etc.), these instructions also allow you to set memory cells contents to
concrete values.

Note that in these address transfer operators, the @samp{MOD} field is
not a subfield specificator, but serves to define (together with
@samp{OPCODE}) the concrete operation to be performed.

@node Comparison operators, Jump operators, Address transfer operators, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Comparison operators
@cindex comparison operators

So far, we have learned how to move values around between the MIX
registers and its memory cells, and also how to perform arithmetic
operations using these values. But, in order to write non-trivial
programs, other functionalities are needed. One of the most common is
the ability to compare two values, which, combined with jumps, will
allow the execution of conditional statements.
The following instructions compare the value of a register with @samp{V}, and
set the @sc{cm} indicator to the result of the comparison (i.e. to
@samp{E}, @samp{G} or @samp{L}, equal, greater or lesser respectively).

@ftable @code
@item CMPA
Compare [rA] with V. OPCODE = 56, MOD = fspec.
@item CMPX
Compare [rX] with V. OPCODE = 63, MOD = fspec.
@item CMPi
Compare [rIi] with V. OPCODE = 56 + i, MOD = fspec.
@end ftable

As explained above, these instructions modify the value of the MIX
comparison indicator; but maybe you are asking yourself how do you use
this value: enter jump operators, in the next subsection.

@node Jump operators, Input-output operators, Comparison operators, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Jump operators
@cindex jump operators

The MIX computer has an internal register, called the @dfn{location
counter}, which stores the address of the next instruction to be fetched
and executed by the virtual CPU. You cannot directly modify the contents
of this internal register with a load instruction: after fetching the
current instruction from memory, it is automatically increased in one
unit by the MIX. However, there is a set of instructions (which we call
jump instructions) which can alter the contents of the location counter
provided some condition is met. When this occurs, the value of the next
instruction address that would have been fetched in the absence of the
jump is stored in @samp{rJ} (except for @code{JSJ}), and the location
counter is set to the value of @samp{M} (so that the next instruction is
fetched from this new address). Later on, you can return to the point
when the jump occurred reading the address stored in @samp{rJ}.

The MIX computer provides the following jump instructions:
With these instructions you force a jump to the specified address. Use
@samp{JSJ} if you do not care about the return address.

@ftable @code
@item JMP
Unconditional jump. OPCODE = 39, MOD = 0.
@item JSJ
Unconditional jump, but rJ is not modified. OPCODE = 39, MOD = 1.
@end ftable

These instructions check the overflow toggle to decide whether to jump
or not.

@ftable @code
@item JOV
Jump if OV is set (and turn it off). OPCODE = 39, MOD = 2.
@item JNOV
Jump if OV is not set (and turn it off). OPCODE = 39, MOD = 3.
@end ftable

In the following instructions, the jump is conditioned to the contents of the
comparison flag:

@ftable @code
@item JL
Jump if @w{@code{[CM] = L}}. OPCODE = 39, MOD = 4.
@item JE
Jump if @w{@code{[CM] = E}}. OPCODE = 39, MOD = 5.
@item JG
Jump if @w{@code{[CM] = G}}. OPCODE = 39, MOD = 6.
@item JGE
Jump if @code{[CM]} does not equal @code{L}. OPCODE = 39, MOD = 7.
@item JNE
Jump if @code{[CM]} does not equal @code{E}. OPCODE = 39, MOD = 8.
@item JLE
Jump if @code{[CM]} does not equal @code{G}. OPCODE = 39, MOD = 9.
@end ftable

You can also jump conditioned to the value stored in the MIX registers,
using the following instructions:

@ftable @code
@item JAN
@itemx JAZ
@itemx JAP
@itemx JANN
@itemx JANZ
@itemx JANP
@itemx JAE
@itemx JAO
Jump if the content of rA is, respectively, negative, zero, positive,
non-negative, non-zero, non-positive, even or odd.
OPCODE = 40, MOD = 0, 1, 2, 3, 4, 5, 6, 7.
@item JXN
@itemx JXZ
@itemx JXP
@itemx JXNN
@itemx JXNZ
@itemx JXNP
@itemx JXE
@itemx JXO
Jump if the content of rX is, respectively, negative, zero, positive,
non-negative, non-zero, non-positive, even or odd.
OPCODE = 47, MOD = 0, 1, 2, 3, 4, 5, 6, 7.
@item JiN
@itemx JiZ
@itemx JiP
@itemx JiNN
@itemx JiNZ
@itemx JiNP
Jump if the content of rIi is, respectively, negative, zero, positive,
non-negative, non-zero or non-positive.
OPCODE = 40 + i, MOD = 0, 1, 2, 3, 4, 5.
@end ftable


@node Input-output operators, Conversion operators, Jump operators, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Input-output operators
@cindex input-output operators

As explained in previous sections (@pxref{MIX architecture}), the MIX
computer can interact with a series of block devices. To that end, you
have at your disposal the following instructions:

@ftable @code
@item IN
Transfer a block of words from the specified unit to memory, starting at
address M.
OPCODE = 36, MOD = I/O unit.
@item OUT
Transfer a block of words from memory (starting at address M) to the
specified unit.
OPCODE = 37, MOD = I/O unit.
@item IOC
Perform a control operation (given by M) on the specified unit.
OPCODE = 35, MOD = I/O unit.
@item JRED
Jump to M if the specified unit is ready.
OPCODE = 38, MOD = I/O unit.
@item JBUS
Jump to M if the specified unit is busy.
OPCODE = 34, MOD = I/O unit.
@end ftable
@noindent
In all the above instructions, the @samp{MOD} subfile must be in the
range 0-20, since it denotes the operation's target device. The
@samp{IOC} instruction makes sense for magnetic tape devices (@samp{MOD} =
0-7): it shifts the read/write pointer by the number of blocks
given by @samp{M} (if it equals zero, the tape is rewound), paper tape
devices (@samp{MOD} = 20): @samp{M} should be 0, the tape is rewound,
and disk/drum devices (@samp{MOD} = 8-15): it moves the read/write
pointer to the block specified in rX and @samp{M} should be 0@footnote{In
Knuth's original definition, there are other control operations available,
but they do not make sense when implementing the devices as disk files (as
we do in @sc{mdk} simulator). For the same reason, @sc{mdk} devices are
always ready, since all input-output operations are performed using
synchronous system calls.}.


@node Conversion operators, Shift operators, Input-output operators, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Conversion operators
@cindex conversion operators

The following instructions convert between numerical values and their
character representations.

@ftable @code
@item NUM
Convert rAX, assumed to contain a character representation of a number,
to its numerical value and store it in rA.
OPCODE = 5, MOD = 0.
@item CHAR
Convert the number stored in rA to a character representation and store
it in rAX.
OPCODE = 5, MOD = 1.
@end ftable
@noindent
Digits are represented in MIX by the range of values 30-39 (digits
0-9). Thus, if the contents of @samp{rA} and @samp{rX} are, for instance,

@example
[rA] = + 30 30 31 32 33
[rX] = + 31 35 39 30 34
@end example
@noindent
the represented number is 0012315904, and @samp{NUM} will store this
value in @samp{rA} (i.e., we end up with @samp{[rA]} = @w{+ 0 46 62 52
0} = 12315904).

If any byte in @samp{rA} or @samp{rB} does not belong to the range
30-39, it is interpreted by @samp{NUM} as the digit obtained by taking
its value modulo 10. E.g. values 0, 10, 20, 30, 40, 50, 60 all represent the
digit 0; 2, 12, 22, etc. represent the digit 2, and so on. For
instance, the number 0012315904 mentioned above could also be
represented as

@example
[rA] = + 10 40 31 52 23
[rX] = + 11 35 49 20 54
@end example

@samp{CHAR} performs the inverse operation, using only the values 30
to 39 for representing digits 0-9.

@node Shift operators, Miscellaneous operators, Conversion operators, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Shift operators
@cindex shift
@cindex shift operators

The following instructions perform byte-wise shifts of the contents of
@samp{rA} and @samp{rX}.

@ftable @code
@item SLA
@itemx SRA
@itemx SLAX
@itemx SRAX
@itemx SLC
@itemx SRC
Shift rA or rAX left, right, or rAX circularly (see example below)
left or right. M specifies the number of bytes to be shifted.
OPCODE = 6, MOD = 0, 1, 2, 3, 4, 5.
@end ftable

@noindent
The following instructions perform binary shifts of the contents of @samp{rA} and @samp{rX}.

@ftable @code
@item SLB
@itemx SRB
Shift rAX left or right binary. M specifies the number of binary places to shift.
OPCODE = 6, MOD = 6, 7
@end ftable

@noindent
If we begin with, say, @samp{[rA]} = @w{- 01 02 03 04 05}, we would
have the following modifications to @samp{rA} contents when performing
the instructions on the left column:

@multitable {SLA 00} {[rA] = - 00 00 00 00 00}
@item SLA 2 @tab [rA] = - 03 04 05 00 00
@item SLA 6 @tab [rA] = - 00 00 00 00 00
@item SRA 1 @tab [rA] = - 00 01 02 03 04
@end multitable

@noindent
Note that the sign is unaffected by shift operations. On the other
hand, @samp{SLC}, @samp{SRC}, @samp{SLAX}, @samp{SRAX}, @samp{SLB} and
@samp{SRB} treat @samp{rA} and @samp{rX} as a single 10-bytes register
(ignoring again the signs). For instance, if we begin with @samp{[rA]}
= @w{+ 01 02 03 04 05} and @samp{[rX]} = @w{- 06 07 08 09 10}, we
would have:

@multitable {SLC 00} {[rA] = - 00 00 00 00 00} {[rA] = - 00 00 00 00 00}
@item SLC 3 @tab [rA] = + 04 05 06 07 08 @tab [rX] = - 09 10 01 02 03
@item SLAX 3 @tab [rA] = + 04 05 06 07 08 @tab [rX] = - 09 10 00 00 00
@item SRC 4 @tab [rA] = + 07 08 09 10 01 @tab [rX] = - 02 03 04 05 06
@item SRAX 4 @tab [rA] = + 00 00 00 00 01 @tab [rX] = - 02 03 04 05 06
@item SLB 1 @tab [rA] = + 02 04 06 08 10 @tab [rX] = - 12 14 16 18 20
@end multitable

@node Miscellaneous operators, Execution times, Shift operators, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Miscellaneous operators
@cindex miscellaneous operators

Finally, we list in the following table three miscellaneous MIX
instructions which do not fit in any of the previous subsections:

@ftable @code
@item MOVE
Move MOD words from M to the location stored in rI1.
OPCODE = 7, MOD = no. of words.
@item NOP
No operation. OPCODE = 0, MOD = 0.
@item HLT
Halt. Stops instruction fetching. OPCODE = 5, MOD = 2.
@end ftable
@noindent
The only effect of executing @samp{NOP} is increasing the location
counter, while @samp{HLT} usually marks program termination.

@node Execution times,  , Miscellaneous operators, MIX instruction set
@comment  node-name,  next,  previous,  up
@subsubsection Execution times

@cindex exection time
@cindex time

When writing MIXAL programs (or any kind of programs, for that
matter), we shall often be interested in their execution
time. Loosely speaking, we will be interested in the answer to the
question: how long does it take a program to execute? Of course, this
execution time will be a function of the input size, and the answer to
our question is commonly given as the asymptotic behaviour as a
function of the input size. At any rate, to compute this asymptotic
behaviour, we need a measure of how long execution of a single
instruction takes in our (virtual) CPU. Therefore, each MIX
instruction will have an associated execution time, given in arbitrary
units (in a real computer, the value of this unit will depend on the
hardware configuration). When our MIX virtual machine executes
programs, it will (optionally) give you the value of their execution
time based upon the execution time of each single instruction.

In the following table, the execution times (in the above mentioned
arbitrary units) of the MIX instructions are given.

@multitable {INSSSS} {01} {INSSSS} {01} {INSSSS} {01} {INSSSS} {01}
@item @code{NOP} @tab 1 @tab @code{ADD} @tab 2 @tab @code{SUB}
@tab 2 @tab @code{MUL} @tab 10
@item @code{DIV} @tab 12 @tab @code{NUM} @tab 10 @tab @code{CHAR}
@tab 10 @tab @code{HLT} @tab 10
@item @code{SLx} @tab 2 @tab @code{SRx} @tab 2 @tab @code{LDx}
@tab  2 @tab @code{STx} @tab 2
@item @code{JBUS} @tab 1 @tab @code{IOC} @tab 1 @tab @code{IN}
@tab  1@tab @code{OUT} @tab 1
@item @code{JRED} @tab 1 @tab @code{Jx} @tab 1 @tab @code{INCx}
@tab  1 @tab @code{DECx} @tab 1
@item @code{ENTx} @tab 1 @tab @code{ENNx} @tab 1 @tab @code{CMPx}
@tab  1 @tab @code{MOVE} @tab 1+2F
@end multitable

In the above table, 'F' stands for the number of blocks to be moved
(given by the @code{FSPEC} subfield of the instruction); @code{SLx} and
@code{SRx} are a short cut for the byte-shifting operations; @code{LDx}
denote all the loading operations; @code{STx} are the storing
operations; @code{Jx} stands for all the jump operations, and so on with
the rest of abbreviations.

@node MIXAL,  , The MIX computer, MIX and MIXAL tutorial
@comment  node-name,  next,  previous,  up
@section MIXAL
@cindex MIXAL
@cindex MIX assembly language
@cindex assembly

In the previous sections we have listed all the available MIX binary
instructions. As we have shown, each instruction is represented by a
word which is fetched from memory and executed by the MIX virtual
CPU. As is the case with real computers, the MIX knows how to decode
instructions in binary format (the so--called machine language), but a
human programmer would have a tough time if she were to write her
programs in machine language. Fortunately, the MIX computer can be
programmed using an assembly language, MIXAL, which provides a symbolic
way of writing the binary instructions understood by the imaginary MIX
computer. If you have used assembler languages before, you will find
MIXAL a very familiar language. MIXAL source files are translated
to machine language by a MIX assembler, which produces a binary file (the
actual MIX program) which can be directly loaded into the MIX memory and
subsequently executed.

In this section, we describe MIXAL, the MIX assembly language. The
implementation of the MIX assembler program and MIX computer simulator
provided by @sc{mdk} are described later on (@pxref{Getting started}).

@menu
* Basic structure::             Writing basic MIXAL programs.
* MIXAL directives::            Assembler directives.
* Expressions::                 Evaluation of expressions.
* W-expressions::               Evaluation of w-expressions.
* Local symbols::               Special symbol table entries.
* Literal constants::           Specifying an immediate operand.
@end menu

@node Basic structure, MIXAL directives, MIXAL, MIXAL
@comment  node-name,  next,  previous,  up
@subsection Basic program structure

The MIX assembler reads MIXAL files line by line, producing, when
required, a binary instruction, which is associated to a predefined
memory address. To keep track of the current address, the assembler
maintains an internal location counter which is incremented each time an
instruction is compiled. In addition to MIX instructions, you can
include in MIXAL file assembly directives (or pseudoinstructions)
addressed at the assembler itself (for instance, telling it where the
program starts and ends, or to reposition the location counter; see below).

MIX instructions and assembler directives@footnote{We shall call them,
collectively, MIXAL instructions.} are written in MIXAL (one per
source file line) according to the following pattern:

@example
[LABEL]   MNEMONIC  [OPERAND]   [COMMENT]
@end example

@noindent
where @samp{OPERAND} is of the form

@example
[ADDRESS][,INDEX][(MOD)]
@end example

Items between square brackets are optional, and

@table @code
@item LABEL
is an alphanumeric identifier (a @dfn{symbol}) which gets the current
value of the location counter, and can be used in subsequent
expressions,
@item MNEMONIC
is a literal denoting the operation code of the instruction
(e.g. @code{LDA}, @code{STA}; see @pxref{MIX instruction set}) or an
assembly pseudoinstruction (e.g. @code{ORIG}, @code{EQU}),
@item ADDRESS
is an expression evaluating to the address subfield of the instruction,
@item INDEX
is an expression evaluating to the index subfield of the instruction, which
defaults to 0 (i.e., no use of indexing) and can only be used when
@code{ADDRESS} is present,
@item MOD
is an expression evaluating to the mod subfield of the instruction. Its
default value, when omitted, depends on @code{OPCODE},
@item COMMENT
any number of spaces after the operand mark the beginning of a comment,
i.e. any text separated by white space from the operand is ignored by
the assembler (note that spaces are not allowed within the
@samp{OPERAND} field).
@end table

Note that spaces are @emph{not} allowed between the @code{ADDRESS},
@code{INDEX} and @code{MOD} fields if they are present. White space is
used to separate the label, operation code and operand parts of the
instruction@footnote{In fact, Knuth's definition of MIXAL restricts the
column number at which each of these instruction parts must start. The
MIXAL assembler included in @sc{mdk}, @code{mixasm}, does not impose
such restriction.}.

We have already listed the mnemonics associated with each MIX
instruction; sample MIXAL instructions representing MIX instructions
are:
@example
HERE     LDA  2000         HERE represents the current location counter
         LDX  HERE,2(1:3)  this is a comment
         JMP  1234
@end example

@node MIXAL directives, Expressions, Basic structure, MIXAL
@comment  node-name,  next,  previous,  up
@subsection MIXAL directives

MIXAL instructions can be either one of the MIX machine instructions
(@pxref{MIX instruction set}) or one of the following assembly
pseudoinstructions:

@ftable @code
@item ORIG
Sets the value of the memory address to which following instructions
will be allocated after compilation.
@item EQU
Used to define a symbol's value, e.g. @w{@code{SYM  EQU  2*200/3}}.
@item CON
The value of the given expression is copied directly into the current
memory address.
@item ALF
Takes as operand five characters, constituting the five bytes of a word
which is copied directly into the current memory address.
@item END
Marks the end of the program. Its operand gives the start address for
program execution.
@end ftable

The operand of @code{ORIG}, @code{EQU}, @code{CON} and @code{END} can be
any expression evaluating to a constant MIX word, i.e., either a simple
MIXAL expression (composed of numbers, symbols and binary operators,
@pxref{Expressions}) or a w-expression (@pxref{W-expressions}).

All MIXAL programs must contain an @code{END} directive, with a twofold
end: first, it marks the end of the assembler job, and, in the second
place, its (mandatory) operand indicates the start address for the
compiled program (that is, the address at which the virtual MIX machine
must begin fetching instructions after loading the program). It is also
very common (although not mandatory) to include at least an @code{ORIG}
directive to mark the initial value of the assembler's location counter
(remember that it stores the address associated with each compiled MIX
instruction). Thus, a minimal MIXAL program would be

@example
          ORIG  2000    set the initial compilation address
          NOP           this instruction will be loaded at address 2000
          HLT           and this one at address 2001
          END   2000    end of program; start at address 2000
this line is not parsed by the assembler
@end example
@noindent
The assembler will generate two binary instructions (@code{NOP} (@w{+ 00
00 00 00 00}) and @code{HLT} (+ 00 00 02 05)), which will be loaded at
addresses 2000 and 2001. Execution of the program will begin at address
2000. Every MIXAL program should also include a @code{HLT} instruction,
which will mark the end of program execution (but not of program
compilation).

The @code{EQU} directive allows the definition of symbolic names for
specific values. For instance, we could rewrite the above program as
follows:

@example
START     EQU   2000
          ORIG  START
          NOP
          HLT
          END   START
@end example
@noindent
which would give rise to the same compiled code. Symbolic constants (or
symbols, for short) can also be implicitly defined placing them in the
@code{LABEL} field of a MIXAL instruction: in this case, the assembler
assigns to the symbol the value of the location counter before compiling
the line. Hence, a third way of writing our trivial program is

@example
          ORIG  2000
START     NOP
          HLT
          END   START
@end example

The @code{CON} directive allows you to directly specify the contents of
the memory address pointed by the location counter. For instance, when
the assembler encounters the following code snippet

@example
          ORIG  1150
          CON   -1823473
@end example
@noindent
it will assign to the memory cell number 1150 the contents @w{- 00 06 61
11 49} (which corresponds to the decimal value -1823473).

Finally, the @code{ALF} directive lets you specify the memory contents
as a set of five (optionally quoted) characters, which are translated by
the assembler to their byte values, conforming in that way the binary
word that is to be stored in the corresponding memory cell. This
directive comes in handy when you need to store printable messages in a
memory address, as in the following example @footnote{In the original
MIXAL definition, the @code{ALF} argument is not quoted. You can write
the operand (as the @code{ADDRESS} field) without quotes, but, in this
case, you must follow the alignment rules of the original MIXAL
definition (namely, the @code{ADDRESS} must start at column 17).}:

@example
          OUT  MSG       MSG is not yet defined here (future reference)
MSG       ALF  "THIS "   MSG gets defined here
          ALF  "IS A "
          ALF  "MESSA"
          ALF  "GE.  "
@end example
@noindent
The above snippet also shows the use of a @dfn{future reference}, that
is, the usage of a symbol (@code{MSG} in the example) prior of its actual
definition. The MIXAL assembler is able to handle future references
subject to some limitations which are described in the following section
(@pxref{Expressions}).

@cindex comments

Any line starting with an asterisk is treated as a comment and ignored
by the assembler.

@example
* This is a comment: this line is ignored.
    * This line is an error: * must be in column 1.
@end example

As noted in the previous section, comments can also be located after the
@code{OPERAND} field of an instruction, separated from it by white
space, as in

@example
LABEL     LDA   100  This is also a comment
@end example

@node Expressions, W-expressions, MIXAL directives, MIXAL
@comment  node-name,  next,  previous,  up
@subsection Expressions
@cindex operator
@cindex binary operator
@cindex unary operator
The @code{ADDRESS}, @code{INDEX} and @code{MOD} fields of a MIXAL
instruction can be expressions, formed by numbers, identifiers and
binary operators (@code{+ - * / // :}). @code{+} and @code{-} can also
be used as unary operators. Operator precedence is from left to right:
there is no other operator precedence rule, and parentheses cannot be
used for grouping. A stand-alone asterisk denotes the current memory
location; thus, for instance,

@example
     4+2**
@end example

@noindent
evaluates to 6 (4 plus 2) times the current memory location. White space
is not allowed within expressions.

The special binary operator @code{:} has the same meaning as in fspecs,
i.e.,

@example
A:B = 8*A + B
@end example
@noindent
while @code{A//B} stands for the quotient of the ten-byte number @w{@code{A} 00
00 00 00 00} (that is, A right-padded with 5 null bytes or, what amounts
to the same, multiplied by 64 to the fifth power) divided by
@code{B}. Sample expressions are:

@example
18-8*3 = 30
14/3 = 4
1+3:11 = 4:11 = 43
1//64 = (01 00 00 00 00 00)/(00 00 00 01 00) = (01 00 00 00 00)
@end example
@noindent
Note that all MIXAL expressions evaluate to a MIX word (by definition).

All symbols appearing within an expression must be previously defined. Future
references are only allowed when appearing standalone (or modified by
an unary operator) in the @code{ADDRESS} part of a MIXAL instruction,
e.g.

@example
* OK: stand alone future reference
         STA  -S1(1:5)
* ERROR: future reference in expression
         LDX  2-S1
S1       LD1  2000
@end example

@node W-expressions, Local symbols, Expressions, MIXAL
@comment  node-name,  next,  previous,  up
@subsection W-expressions
@cindex w-expressions

Besides expressions, as described above (@pxref{Expressions}), the MIXAL
assembler is able to handle the so called @dfn{w-expressions} as the
operands of the directives @code{ORIG}, @code{EQU}, @code{CON} and
@code{END} (@pxref{MIXAL directives}). The general form of a
w-expression is the following:

@example
     WEXP = EXP[(EXP)][,WEXP]
@end example
@noindent
where @code{EXP} stands for an expression and square brackets denote
optional items. Thus, a w-expression is made by an expression, followed
by an optional expression between parenthesis, followed by any number
of similar constructs separated by commas. Sample w-expressions are:

@example
2000
235(3)
S1+3(S2),3000
S1,S2(3:5),23
@end example

W-expressions are evaluated from left to right as follows:

@itemize
@item
Start with an accumulated result @samp{w} equal to 0.
@item
Take the first expression of the comma-separated list and evaluate
it. For instance, if the w-expression is @samp{S1+2(2:4),2000(S2)}, we
evaluate first @samp{S1+2}; let's suppose that @samp{S1} equals
265230: then @samp{S1+2 = 265232 = + 00 01 00 48 16}.
@item
Evaluate the expression within parenthesis, reducing it to an f-spec
of the form @samp{L:R}. In our previous example, the expression
between parenthesis already has the desired form: 2:4.
@item
Substitute the bytes of the accumulated result @samp{w} designated by
the f-spec using those of the previous expression value. In our sample,
@samp{w = + 00 00 00 00 00}, and we must substitute bytes 2, 3 and 4 of
@samp{w} using values from 265232. We need 3 bytes, and we take the
least significant ones: 00, 48, and 16, and insert them in positions
2, 3 and 4 of @samp{w}, obtaining @samp{w = + 00 00 48 16 00}.
@item
Repeat this operation with the remaining terms, acting on the new
value of @samp{w}. In our example, if, say, @samp{S2 = 1:1}, we must
substitute the first byte of @samp{w} using one byte (the least
significant) from 2000, that is, 16 (since 2000 = + 00 00 00 31 16)
and, therefore, we obtain @samp{w = + 16 00 48 16 00}; summing up, we
have obtained @samp{265232(1:4),2000(1:1) = + 16 00 48 16 00 =
268633088}.
@end itemize

As a second example, in the w-expression
@example
1(1:2),66(4:5)
@end example
@noindent
we first take two bytes from 1 (00 and 01) and store them as bytes 1 and
2 of the result (obtaining @w{@samp{+ 00 01 00 00 00}}) and, afterwards,
take two bytes from 66 (01 and 02) and store them as bytes 4 and 5 of
the result, obtaining @w{@samp{+ 00 01 00 01 02}} (262210). The process
is repeated for each new comma-separated example. For instance:

@example
1(1:1),2(2:2),3(3:3),4(4:4) = 01 02 03 04 00
@end example

As stated before, w-expressions can only appear as the operands of MIXAL
directives taking a constant value (@code{ORIG}, @code{EQU}, @code{CON}
and @code{END}). Future references are @emph{not} allowed within
w-expressions (i.e., all symbols appearing in a w-expression must be
defined before it is used).

@node Local symbols, Literal constants, W-expressions, MIXAL
@comment  node-name,  next,  previous,  up
@subsection Local symbols
@cindex local symbols

Besides user defined symbols, MIXAL programmers can use the so called
@dfn{local symbols}, which are symbols of the form @code{[1-9][HBF]}. A
local symbol @code{nB} refers to the address of the last previous
occurrence of @code{nH} as a label, while @code{nF} refers to the next
@code{nH} occurrence. Unlike user defined symbols, @code{nH} can appear
multiple times in the @code{LABEL} part of different MIXAL
instructions. The following code shows an instance of local symbols'
usage:

@example
* line 1
1H    LDA  100
* line 2: 1B refers to address of line 1, 3F refers to address of line 4
      STA  3F,2(1B//2)
* line 3: redefinition of 1H
1H    STZ
* line 4: 1B refers to address of line 3
3H    JMP  1B
@end example

Note that a @code{B} local symbol never refers to a definition in its
own line, that is, in the following program:

@example
		ORIG 1999
ST		NOP
3H		EQU 69
3H		ENTA 3B  local symbol 3B refers to 3H in previous line
		HLT
		END ST
@end example
@noindent
the contents of @samp{rA} is set to 69 and @emph{not} to 2001. An
specially tricky case occurs when using local symbols in conjunction
with @code{ORIG} pseudoinstructions. To wit@footnote{The author wants to
thank Philip E. King for pointing these two special cases of local
symbol usage to him.},

@example
		ORIG 1999
ST		NOP
3H		CON 10
		ENT1 *
		LDA 3B
** rI1 is 2001, rA is 10.  So far so good!
3H		ORIG 3B+1000
** at this point 3H equals 2003
** and the location counter equals 3000.
		ENT2 *
		LDX 3B
** rI2 contains 3000, rX contains 2003.
		HLT
		END ST
@end example

@node Literal constants,  , Local symbols, MIXAL
@comment  node-name,  next,  previous,  up
@subsection Literal constants
@cindex literal constants

MIXAL allows the introduction of @dfn{literal constants}, which are
automatically stored in memory addresses after the end of the program by
the assembler. Literal constants are denoted as @code{=wexp=}, where
@code{wexp} is a w-expression (@pxref{W-expressions}). For instance, the
code

@example
L         EQU   5
          LDA   =20-L=
@end example

causes the assembler to add after the program's end an instruction
with contents 15 (@samp{20-L}), and to assemble the above code as the
instruction @w{@code{ LDA a}}, where @code{a} stands for the address
in which the value 15 is stored. In other words, the compiled code is
equivalent to the following:

@example
L         EQU  5
          LDA  a
@dots{}
a         CON  20-L
          END  start
@end example