MIX and MIXAL tutorial
**********************

In the book series The Art of Computer Programming, by Donald 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 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 which will teach you the basics of the MIX architecture and how to program a MIX computer using MIXAL.

The MIX computer
================

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

MIX architecture
----------------

The basic information storage unit in the MIX computer is the byte, which stores positive values in the range 0-63 . Note that a MIX byte can then be represented as six bits, instead of the eight bits used for a regular byte. Unless otherwise stated, we will use the word byte to refer to a MIX six-bit byte.

A MIX word is defined as a set of five bytes plus a sign. The bytes within a word are numbered from one to five, with byte number one being the most significant one. The sign is denoted by index 0. Graphically:

      -----------------------------------------------
     |   0   |   1   |   2   |   3   |   4   |   5   |
      -----------------------------------------------
     |  +/-  | byte  | byte  | byte  | byte  | byte  |
      -----------------------------------------------

Sample MIX words are: - 12 00 11 01 63 and + 12 11 34 43 00.

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

The MIX computer stores information in registers, which can store either a word or two bytes and a sign (see below), and memory cells, each one of which contains 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:

rA
     A register. General purpose register holding a word. Usually its contents serve as the operand of arithmetic and storing instructions.

rX
     X register. General purpose register holding a word. Often it acts as an extension for or a replacement of rA.

rJ
     J (jump) register. This register stores positive two-byte values, usually representing a jump address.

rI1, rI2, rI3, rI4, rI5, 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.

In addition, the MIX computer contains:

  * An overflow toggle (a single bit with values on or off). In this manual, this toggle is denoted OV.

  * A comparison indicator (having three values: EQUAL, GREATER or LESS). In this manual, this indicator is denoted CM, and its possible values are abbreviated as E, G and L.

  * Input-output block devices. Each device is labelled as un, where n runs from 0 to 20. In Knuth's definition, u0 through u7 are magnetic tape units, u8 through u15 are disks and drums, u16 is a card reader, u17 is a card writer, u18 is a line printer, u19 is a typewriter terminal and u20 is a paper tape. Our implementation maps these devices to disk files, except for u19, which represents the standard output.

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 (see Devices). These words are interpreted by the device either as binary information (for devices 0-16), or as representing printable characters (for devices 17-20). In the last case, each MIX byte is mapped onto a character according to the following table:

00      01   A   02   B   03   C
04   D   05   E   06   F   07   G
08   H   09   I   10   d   11   J
12   K   13   L   14   M   15   N
16   O   17   P   18   Q   19   R
20   s   21   p   22   S   23   T
24   U   25   V   26   W   27   X
28   Y   29   Z   30   0   31   1
32   2   33   3   34   4   35   5
36   6   37   7   38   8   39   9
40   .   41   ,   42   (   43   )
44   +   45   -   46   *   47   /
48   =   49   $   50   <   51   >
52   @   53   ;   54   :   55   '

The value 0 represents a whitespace. Lowercase letters (d, s, p) 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 location counter (also known as program counter in other architectures).

The next section gives a complete description of the available MIX binary instructions.

MIX 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.

Instruction structure
.....................

MIX instructions are codified as words with the following subfield structure:

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

or, graphically:

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

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

     [rI2] = + 00 63
     [31] = - 10 11 00 11 22

where [n] denotes the contents of the nth memory cell and [rI2] the contents of register rI2. (In general, [X] will denote the contents of entity X; thus, by definition, V = [M](MOD).) Let us consider the binary instruction I = - 00 32 02 11 10. For this instruction we have:

     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

Note that when computing V using a word and an fspec, we apply a left padding to the bytes selected by 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 OPCODE 10 is LD2. Thus we can rewrite the above instruction as:

     LD2  -32,2(1:3)

or, for a generic instruction:

     MNEMONIC  ADDRESS,INDEX(MOD)

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.

Loading operators
.................

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

LDA
     Put in rA the contents of cell no. M. OPCODE = 8, MOD = fspec. rA <- V.

LDX
     Put in rX the contents of cell no. M. OPCODE = 15, MOD = fspec. rX <- V.

LDi
     Put in rIi the contents of cell no. M. OPCODE = 8 + i, MOD = fspec. rIi <- V.

LDAN
     Put in rA the contents of cell no. M, with opposite sign. OPCODE = 16, MOD = fspec. rA <- -V.

LDXN
     Put in rX the contents of cell no. M, with opposite sign. OPCODE = 23, MOD = fspec. rX <- -V.

LDiN
     Put in rIi the contents of cell no. M, with opposite sign. OPCODE = 16 + i, MOD = fspec. rIi <- -V.

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

     LD3    13,1(3:3)
      ^      ^ ^  ^
      |      | |  |
      |      | |   --- MOD = 27 = 3*8 + 3
      |      |  --- INDEX = 1
      |       --- ADDRESS = 00 13
       --- OPCODE = 11

Let us suppose that, prior to the execution of this instruction, the state of the MIX computer is the following:

     [rI1] = - 00 01
     [rI3] = + 24 12
     [12] = - 01 02 03 04 05

As, in this case, M = 13 + [rI1] = 12, we have:

     V = [M](3:3) = (- 01 02 03 04 05)(3:3)
       = + 00 00 00 00 03

(note that the specified subfield is left-padded with null bytes to complete a word). Hence, the MIX state, after execution of the instruction, will be:

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

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

LDX 12(0:0)     [rX] = - 00 00 00 00 00

LDX 12(0:1)     [rX] = - 00 00 00 00 01

LDX 12(3:5)     [rX] = + 00 00 03 04 05

LDX 12(3:4)     [rX] = + 00 00 00 03 04

LDX 12(0:5)     [rX] = - 01 02 03 04 05

Storing operators
.................

The following instructions are the inverse of the load operations; they are used to store a subfield of a register in 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 with the far right side of the register.

STA
     Store rA. OPCODE = 24, MOD = fspec. V <- rA.

STX
     Store rX. OPCODE = 31, MOD = fspec. V <- rX.

STi
     Store rIi. OPCODE = 24 + i, MOD = fspec. V <- rIi.

STJ
     Store rJ. OPCODE = 32, MOD = fspec. V <- rJ.

STZ
     Store zero. OPCODE = 33, MOD = fspec. V <- 0.

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

     [1200] = - 20 21 22 23 24
     [rA] = + 01 02 03 04 05

we will end up with

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

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

Arithmetic operators
....................

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

ADD
     Add and set OV if overflow. OPCODE = 1, MOD = fspec. rA <- rA +V.

SUB
     Sub and set OV if overflow. OPCODE = 2, MOD = fspec. rA <- rA - V.

MUL
     Multiply V times rA and store the ten-byte product in rAX. OPCODE = 3, MOD = fspec. rAX <- rA x V.

DIV
     rAX is considered a ten-byte number, and it is divided by V. OPCODE = 4, MOD = fspec. rA <- rAX / V, rX <- reminder.

In all the above instructions, [rA] is one of the operands of the binary arithmetic operation, the other being V (that is, the specified subfield of the memory cell with address M), padded with zero bytes on its left side to complete a word. In multiplication and division, the register X comes into play as a right-extension of the register A, so that we are able to handle ten-byte numbers whose more significant bytes are those of rA (the sign of this ten-byte number is that of rA; 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 for only five bytes (plus sign). When this occurs, the operation result modulo 1,073,741,823 (the maximum value storable in a MIX word) is stored in rA, and the overflow toggle is set to TRUE.

Address transfer operators
..........................

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

ENTA
     Enter M in [rA]. OPCODE = 48, MOD = 2. rA <- M.

ENTX
     Enter M in [rX]. OPCODE = 55, MOD = 2. rX <- M.

ENTi
     Enter M in [rIi]. OPCODE = 48 + i, MOD = 2. rIi <- M.

ENNA
     Enter -M in [rA]. OPCODE = 48, MOD = 3. rA <- -M.

ENNX
     Enter -M in [rX]. OPCODE = 55, MOD = 3. rX <- -M.

ENNi
     Enter -M in [rIi]. OPCODE = 48 + i, MOD = 3. rIi <- -M.

INCA
     Increase [rA] by M. OPCODE = 48, MOD = 0. rA <- rA + M.

INCX
     Increase [rX] by M. OPCODE = 55, MOD = 0. rX <- rX + M.

INCi
     Increase [rIi] by M. OPCODE = 48 + i, MOD = 0. rIi <- rIi + M.

DECA
     Decrease [rA] by M. OPCODE = 48, MOD = 1. rA <- rA - M.

DECX
     Decrease [rX] by M. OPCODE = 55, MOD = 1. rX <- rX - M.

DECi
     Decrease [rIi] by M. OPCODE = 48 + i, MaOD = 0. rIi <- rIi - M.

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

     ENNA 2000

Used in conjunction with the store operations (STA, STX, etc.), these instructions also allow you to set the contents of memory cells to concrete values.

Note that in these address transfer operators, the MOD field is not a subfield specifier, but serves to define, together with OPCODE, the concrete operation to be performed.

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 V, and set the CM indicator to the result of the comparison, either E, G or L (equal, greater or lesser, respectively).

CMPA
     Compare [rA] with V. OPCODE = 56, MOD = fspec.

CMPX
     Compare [rX] with V. OPCODE = 63, MOD = fspec.

CMPi
     Compare [rIi] with V. OPCODE = 56 + i, MOD = fspec.

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

Jump operators
..............

The MIX computer has an internal register, called the 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 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 rJ (except for JSJ), and the location counter is set to the value of M (so that the next instruction is fetched from this new address). Later on, you can return to the point when the jump occurred by reading the address stored in rJ.

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

JMP
     Unconditional jump. OPCODE = 39, MOD = 0.

JSJ
     Unconditional jump, but rJ is not modified. OPCODE = 39, MOD = 1.

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

JOV
     Jump if OV is set (and turn it off). OPCODE = 39, MOD = 2.

JNOV
     Jump if OV is not set (and turn it off). OPCODE = 39, MOD = 3.

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

JL
     Jump if [CM] = L. OPCODE = 39, MOD = 4.
JE
     Jump if [CM] = E. OPCODE = 39, MOD = 5.
JG
     Jump if [CM] = G. OPCODE = 39, MOD = 6.
JGE
     Jump if [CM] does not equal L. OPCODE = 39, MOD = 7.
JNE
     Jump if [CM] does not equal E. OPCODE = 39, MOD = 8.
JLE
     Jump if [CM] does not equal G. OPCODE = 39, MOD = 9.

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

JAN
JAZ
JAP
JANN
JANZ
JANP
     Jump if the content of rA is, respectively, negative, zero, positive, non-negative, non-zero or non-positive. OPCODE = 40, MOD = 0, 1, 2, 3, 4, 5.

JXN
JXZ
JXP
JXNN
JXNZ
JXNP
     Jump if the content of rX is, respectively, negative, zero, positive, non-negative, non-zero or non-positive. OPCODE = 47, MOD = 0, 1, 2, 3, 4, 5.

JiN
JiZ
JiP
JiNN
JiNZ
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.

Input-output operators
......................

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

IN
     Transfer a block of words from the specified unit to memory, starting at address M. OPCODE = 36, MOD = I/O unit.

OUT
     Transfer a block of words from memory (starting at address M) to the specified unit. OPCODE = 37, MOD = I/O unit.

IOC
     Perform a control operation (given by M) on the specified unit. OPCODE = 35, MOD = I/O unit.

JRED
     Jump to M if the specified unit is ready. OPCODE = 38, MOD = I/O unit.

JBUS
     Jump to M if the specified unit is busy. OPCODE = 34, MOD = I/O unit.

In all the above instructions, the MOD subfile must be in the range 0-20, since it denotes the operation's target device. The IOC instruction only makes sense for tape devices (MOD = 0-7 or 20). It shifts the read/write pointer by the number of words given by M (if it equals zero, the tape is rewound). (In Knuth's original definition, there are other control operations available, but they do not make sense when implementing the block devices as disk files (as we do in the MDK simulator). For the same reason, MDK devices are always ready, since all input-output operations are performed using synchronous system calls.)

Conversion operators
....................

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

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.

CHAR
     Convert the number stored in rA to a character representation and store it in rAX. OPCODE = 5, MOD = 1.

Digits are represented in MIX by the range of values 30-39 (digits 0-9). Thus, if the contents of rA and rX are, for instance:

     [rA] = + 30 30 31 32 33
     [rX] = + 31 35 39 30 34

the represented number is 0012315904, and NUM will store this value in rA (i.e., we end up with [rA] = + 0 46 62 52 0 = 12315904).

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

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

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

Shift operators
...............

The following instructions perform byte-wise shifts of the contents of rA and rX:

SLA
SRA
SLAX
SRAX
SLC
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.

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

SLA 2   [rA] = - 03 04 05 00 00
SLA 6   [rA] = - 00 00 00 00 00
SRA 1   [rA] = - 00 01 02 03 04

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

SLC 3   [rA] =  + 04 05 06 07 08   [rX] = - 09 10 01 02 03
SLAX 3   [rA] = + 04 05 06 07 08   [rX] = - 09 10 00 00 00
SRC 4   [rA] =  + 07 08 09 10 01   [rX] = - 02 03 04 05 06
SRAX 4   [rA] =  + 00 00 00 00 01   [rX] = - 02 03 04 05 06

Miscellaneous operators
.......................

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

MOVE
     Move MOD words from M to the location stored in rI1. OPCODE = 7, MOD = number of words.

NOP
     No operation. OPCODE = 0, MOD = 0.

HLT
     Halt. Stops instruction fetching. OPCODE = 5, MOD = 2.

The only effect of executing NOP is increasing the location counter, while HLT usually marks program termination.

Execution times
...............

When writing MIXAL programs (or any kind of program, for that matter), we will often be interested in their execution time. Loosely speaking, we will be interested in how long it takes 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 behavior as a function of the input size. At any rate, to compute this asymptotic behavior, 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 can give you the value of their execution time based on the execution time of each single instruction.

The execution times of the MIX instructions, in the arbitrary units mentioned above, are:

NOP   1   ADD   2   SUB
2   MUL   10
DIV   12   NUM   10   CHAR
10   HLT   10
SLx   2   SRx   2   LDx
2   STx   2
JBUS   1   IOC   1   IN
1  OUT   1
JRED   1   Jx   1   INCx
1   DECx   1
ENTx   1   ENNx   1   CMPx
1   MOVE   1+2F

Here, 'F' stands for the number of blocks to be moved (given by the FSPEC subfield of the instruction), SLx and SRx are a shortcut for the byte-shifting operations, LDx denotes all the loading operations, STx is the storing operation, Jx stands for all the jump operations, and so on with the rest of the abbreviations.

MIXAL
=====

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 into 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 MDK are described later on (see Getting started).

Basic program structure
-----------------------

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

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

     [LABEL]   MNEMONIC  [OPERAND]   [COMMENT]

where OPERAND is of the form (items between the square brackets are optional):

     [ADDRESS][,INDEX][(MOD)]

And:

LABEL
     is an alphanumeric identifier (a symbol) which gets the current value of the location counter, and can be used in subsequent expressions.

MNEMONIC
     is a literal denoting the operation code of the instruction, such as LDA or STA (see MIX instruction set), or an assembly pseudoinstruction, such as ORG or EQU.

ADDRESS
     is an expression that evaluates to the address subfield of the instruction.

INDEX
     is an expression that evaluates to the index subfield of the instruction, which defaults to 0 (i.e., no use of indexing) and can only be used when ADDRESS is present.

MOD
     is an expression that evaluates to the mod subfield of the instruction. Its default value, when omitted, depends on OPCODE.

COMMENT
     any number of spaces after the operand mark the beginning of a comment. Any text separated by white space from the operand is ignored by the assembler (note that spaces are not allowed within the OPERAND field).

Note that spaces are not allowed between the ADDRESS, INDEX and MOD fields if they are present. White space is used to separate the label, operation code and operand parts of the instruction. (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 MDK, mixasm, does not impose such restrictions.)

We have already listed the mnemonics associated with each MIX instruction. Sample MIXAL instructions representing MIX instructions are:

     HERE     LDA  2000         HERE represents the current location counter
              LDX  HERE,2(1:3)  this is a comment
              JMP  1234

MIXAL directives
----------------

MIXAL instructions can be either one of the MIX machine instructions (see MIX instruction set) or one of the following assembly pseudoinstructions:

ORIG
     Sets the value of the memory address to which subsequent instructions will be allocated after compilation.

EQU
     Used to define a symbol's value, e.g. SYM  EQU  2*200/3.

CON
     The value of the given expression is copied directly into the current memory address.

ALF
     Takes as operand five characters, constituting the five bytes of a word which is copied directly into the current memory address.

END
     Marks the end of the program. Its operand gives the starting address for program execution.

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

All MIXAL programs must contain an END directive, for two reasons. First, it marks the end of the assembler job. Second, its mandatory operand indicates the start address for the compiled program (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 ORIG directive to mark the initial value of the assembler's location counter (remember that the location counter stores the address associated with each compiled MIX instruction). Every MIXAL program should also include a HLT instruction, which will mark the end of program execution (but not of program compilation). Thus, a minimal MIXAL program would be:

               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

The assembler will generate two binary instructions (NOP (+ 00 00 00 00 00) and HLT (+ 00 00 02 05)), which will be loaded at addresses 2000 and 2001. Execution of the program will begin at address 2000.

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

     START     EQU   2000
               ORIG  START
               NOP
               HLT
               END   START

which would give rise to the same compiled code. Symbolic constants (symbols, for short) can also be implicitly defined by placing them in the LABEL field of a MIXAL instruction. In this case, the assembler assigns the value of the location counter to the symbol before compiling the line. Hence, a third way of writing our trivial program is:

               ORIG  2000
     START     NOP
               HLT
               END   START

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

               ORIG  1150
               CON   -1823473

it will assign to the memory cell number 1150 the contents - 00 06 61 11 49 (which corresponds to the decimal value -1823473).

Finally, the ALF directive lets you specify the memory contents as a set of five (quoted) characters, which are translated by the assembler to their byte values, confirming 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:

               OUT  MSG       MSG is not yet defined here (future reference)
     MSG       ALF  "THIS "   MSG gets defined here
               ALF  "IS A "
               ALF  "MESSA"
               ALF  "GE.  "

The above snippet also shows the use of a future reference, which is the usage of a symbol (MSG in the example) prior to its actual definition. The MIXAL assembler is able to handle future references subject to some limitations, which are described in the following section (see Expressions).

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

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

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

     LABEL     LDA   100  This is also a comment

Expressions
-----------

The ADDRESS, INDEX and MOD fields of a MIXAL instruction can be expressions, formed by numbers, identifiers and binary operators (+ - * / // :). + and - 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,

          4+2**

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

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

     A:B = 8*A + B

while A//B stands for the quotient of the ten-byte number A 00 00 00 00 00 (A right-padded with five null bytes or, what amounts to the same, multiplied by 64 to the fifth power) divided by B. Sample expressions are:

     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)

Note that all MIXAL expressions, by definition, evaluate to a MIX word.

All symbols appearing within an expression must be previously defined. Future references are only allowed when appearing stand-alone (or modified by a unary operator) in the ADDRESS part of a MIXAL instruction, e.g.:

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

W-expressions
-------------

Besides expressions, as described above (see Expressions), the MIXAL assembler is able to handle w-expressions as the operands of the directives ORIG, EQU, CON and END (see MIXAL directives). The general form of a w-expression is:

          WEXP = EXP[(EXP)][,WEXP]

where 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 parentheses, followed by any number of similar constructs separated by commas. Sample w-expressions are:

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

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

  * Start with an accumulated result w equal to 0.

  * Take the first expression of the comma-separated list and evaluate it. For instance, if the w-expression is S1+2(2:4),2000(S2), we evaluate first S1+2. Suppose that S1 equals 265230. Then S1+2 = 265232 = + 00 01 00 48 16.

  * Evaluate the expression within parentheses, reducing it to an f-spec of the form L:R. In our previous example, the expression between parentheses already has the desired form: 2:4.

  * Substitute the bytes of the accumulated result w designated by the f-spec using those of the previous expression value. In our sample, w = + 00 00 00 00 00, and we must substitute bytes 2, 3 and 4 of w using values from 265232. We need three bytes, and we take the least significant ones: 00, 48, and 16, and insert them in positions 2, 3 and 4 of w, obtaining w = + 00 00 48 16 00.

  * Repeat this operation with the remaining terms, acting on the new value of w. In our example, if S2 = 1:1, we must substitute the first byte of w using one byte (the least significant) from 2000, which is 16 (since 2000 = + 00 00 00 31 16). Therefore, we obtain w = + 16 00 48 16 00. Summing up, we have obtained 265232(1:4),2000(1:1) = + 16 00 48 16 00 = 268633088.

As a second example, in the w-expression:

     1(1:2),66(4:5)

we first take two bytes from 1 (00 and 01) and store them as bytes 1 and 2 of the result (obtaining + 00 01 00 00 00). Afterwards, we take two bytes from 66 (01 and 02) and store them as bytes 4 and 5 of the result, obtaining + 00 01 00 01 02 (262210). The process is repeated for each new comma-separated example. For instance:

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

As stated before, w-expressions can only appear as the operands of MIXAL directives that take a constant value (ORIG, EQU, CON and END). Future references are not allowed within w-expressions. All symbols appearing in a w-expression must be defined before it is used.

Local symbols
-------------

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

     * 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

Note that a B local symbol never refers to a definition in its own line. In the following program:

     		ORIG 1999
     ST		NOP
     3H		EQU 69
     3H		ENTA 3B  local symbol 3B refers to 3H in previous line
     		HLT
     		END ST

the content of rA is set to 69, not to 2001. An especially tricky case occurs when using local symbols in conjunction with ORIG pseudoinstructions. (The author wants to thank Philip E. King for pointing out these two special cases of local symbol usage.) For 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

Literal constants
-----------------

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

     L         EQU   5
               LDA   =20-L=

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

     L         EQU  5
               LDA  a
     ...
     a         CON  20-L
               END  start