MIX (Knuth)

Not to be confused with MIX.

MIX is a computer architecture created by Donald Knuth. Knuth is writing a grand monography The Art of Computer Programming, and in older editions of that book, he used to present example subroutines and programs in this architecture.

MIX is decidedly not an esoteric language, it deliberately resembles the languages of real computers at the time it was invented (before 1969).

CPU

General

The size of a MIX byte depends on the machine: a byte stores a natural number less than 64 on binary machines, 100 on decimal machines, or any limit between 64 and 100 in general.

A machine word in MIX is an integer made of a sign and five bytes. These are called byte 5 for the least significant byte to byte 1 for the most significant, and the sign counts as byte 0 (even though it's not a full byte, it can only store plus or minus).

The memory of a MIX computer holds 4000 words. Data and instructions are stored in the same memory. Since MIX is an old computer, there are no caches, all memory accesses take the same time.

MIX has eight main registers: rA (accumulator), rI1, rI2, rI3, rI4, rI5, rI6 (index registers), rX (extension registers). Of these, rA and rX are full words, but the index registers rI1..rI6 are limited to a sign and the two lower bytes, and trying to assign any value that does not have zero in bytes 1..3 has an undefined behavior. In addition, there is a program counter, an rJ register that contains the return address after the last jump, an arithmetic overflow flag, and comparison flags.

There is one instruction per word, and are executed sequentially unless a branch instruction changes the program counter. An instruction has the format ±AAIFC, where the opcode C is byte 5. Byte 3 called I, which must be less than 7, allows indexed mode for any instruction. Execution of the instruction starts by computing a value called M by indexing the first three bytes ±AA with an index register: M = ±AA + rI_I if I is nonzero, or M = ±AA if I is zero. The resulting M must also fit in two bytes and a sign, or else its value is undefined. All instructions then care only about the value of M, F and C, rather than the original ±AAI.

Instruction set

Most instructions come in series of eight, where the source or destination operand is one of the eight main registers, decided by the low three bits of the opcode C. The series of instructions like this are as follows: here x is one of A, 1, 2, 3, 4, 5, 6, X, which use the register rA, rI1..rI6, rX respectively.

• LDx loads the word with address M from memory to the register.
• LDxN loads the word with address M from the memory to the register but then flips the sign of the register.
• STx stores the register to memory address M.
• CMPx compares the value of the register with the word at address M in memory, and sets the comparison flags to the result, indicating equal, less, or greater.
• Jxcc is a conditional branch to address M, depending on the value of the register. Here, cc is a condition: one of N (negative), Z (zero), P (positive), NN (nonnegative), NZ (nonzero), NP (nonpositive).
• ENTx loads the (immediate or indexed value) M into the register.
• ENNx is the same, but then flips the sign of the register.
• INCx adds the (immediate or indexed value) M to the register, putting the destination to the same register.
• DECx subtracts M from the register, putting the destination to the same register.

Other general purpose instructions, which don't come in such series of eight, are:

• JMP is an unconditional jump to address M.
• Jcc are conditional jumps to address M depending on the comparison flags, where cc a condition code chosen from L (less), E (equal), G (greater), GE (less or equal), NE (not equal), LE (less or equal). For example, JL branches if the register had a lower value than the memory at the last CMPx instruction.
• JOV and JNOV are conditional jumps if the overflow flag is set or not set respectively.
• STJ stores the rJ register to a memory cell. All of the above jump instructions put one plus the address of the jump instruction to rJ before jumping, thus rJ contains the return address after a subroutine call. Subroutines usually store this return value to the ±AA field of a jump instruction with STJ before they do another jump. This results in self-modifying code.
• JSJ is an unconditional jump, but unlike all other jump instructions, it does not modify the rJ register.
• ADD adds the memory word at address M to the accumulator rA, putting the result in rA.
• SUB subtracts the memory word at address M from the accumulator rA, putting the result in rA.
• MUL multiplies the memory word at address M with the accumulator rA, and puts the high word of the two-word result in rA and the low word in rX.
• DIV performs a division. The divisor is two words long, the high word and sign is in register rA, the low word is in rX (whose sign is ignored). The divisor is the memory word at address M. The instruction puts the quotient (truncated towards zero) in rA and the remainder in rX, or an undefined value into both of those registers if the division overflows or if the divisor is zero.
• STZ stores +0 to the memory word at address M.
• SLA and SRA shift the magnitude bytes of the accumulator rA by M bytes to the left or right (the most significant bytes are on the left), shifting in zeros from the side.
• SLAX and SRAX shifts the magnitude bytes of the registers rA and rX taken together as a ten-byte word (rA is on the left), shifting in zeros from the side.
• SLC and SRC cyclically shifts the magnitude bytes of the registers rA and rX taken as a ten-byte word left or right cyclically. None of the shift instructions modifies the signs of the registers.
• MOVE copies several bytes from memory to memory. The word count is F, the first source word is at address M, the first destination word at address rI1. The copies are done one word at a time, so if M < rI1 < M + C, then the first rI1-M bytes are repeated cyclically. As a side effect, rI1 is incremented by F.
• NOP does nothing.
• NUM converts a ten-digit decimal string, one digit per byte, to an unsigned single word integer. The input string is in rA (five most significant digits) and rX (five least significant digits), and the remainder divided by 10 of each byte of the input gives a digit. The output is in the mantissa bytes of rA, the sign is unchanged.
• CHAR converts an unsigned single word integer rA to decimal. The output is ten digits, stored in individual bytes of rA and rX, but 30 is added to each digit. Signs are unchanged. These last three instructions ignore the value M.

In addition to the above section, MIX has IO instructions, floating-point instructions, and some versions have nonstandard extensions too.

Field selection

Many instructions can operate on just a field of a word, where a field can be any non-empty range of the six bytes (including the sign). For some instructions, byte F is interpreted as a field specification to choose such a field. In that case, F has the format h+8*l, which selects the range from byte h to byte l inclusive, and 0≤h≤l≤5. Very often, F=5, meaning to operate on a full word.

• The LDx and LDxN instructions extract the specified field of the memory word, and loads only that to the register. The magnitude bytes in the field chosen are shifted to the least significant bytes of the register, the bytes above them filled with zero. If the field specification includes the sign, that is loaded to the sign of the register, otherwise the sign is filled with plus.
• In the ADD, SUB, MUL and DIV instructions, the second operand is the specified field of the memory word, but the instructions operate on the whole register or registers as the second operand and output.
• The STx and STJ instruction puts the whole register to the specified field of the memory word, and doesn't modify the other bytes of the memory word. If the field doesn't include byte 5, then the less significant magnitude bytes of the register are thus shifted to the left, and the more significant ones are ignored.
• Similarly, STZ modifies the specified field of the memory word only.
• However, the CMPx instructions use F to select the same field both from the register and the memory word, comparing those fields without shifting anything.

Other instructions use the byte F for other purposes, the most common of which is distinguishing between sub-instructions with the same opcode.

• Specifically, for a fixed register x, the immediate instructions INCx, DECx, ENTx, ENNx are distinguished only by F.
• For a fixed register x, in the conditional branches Jxcc, the condition code cc is decided by F.
• Opcode 39 multiplexes the branch instructions Jcc, JMP, JOV, JNOV, JSJ by the value F.
• Opcode 5 multiplexes the instructions NUM, CHAR, HLT and some nonstandard extensions.
• Opcode 6 multiplexes between the shift instructions.

Misc

The overflow flag is set when an arithmetic operation on rA or rX (ADD, SUB, INCx, DECx, DIV, NUM) overflows. Recall that overflowing an index register or the indexed value M has undefined behavior though, so overflow need not be detected there. The overflow flag is only cleared by the JOV and JNOV conditional branches, not by other instructions. The shift instructions don't affect the overflow flag.

As MIX uses sign-magnitude representation, the sign of a zero is defined in all operations, and can be read by field access or shifting, but in practice this rarely matters. The rules for the sign of a zero in arithmetic operations is as follows. When computing M for the ENTx or ENNx instructions, if I is nonzero and M is zero, then M has the sign of the instruction. In the ADD, SUB, INCx, DECx instructions, if the result is zero, the sign of the destination register is unchanged. Comparisons and conditional branches ignore the sign of a zero value. The MUL and DIV instructions act on the signs and magnitudes independently. For MUL, both output registers get a plus sign if the sign of the two operands were the same, or a minus sign if they were different. For DIV, the sign of the quotient output is plus if the divisor and the dividend have the same sign, or minus if they have different sign, and the remainder output has the sign of the dividend.

IO

MIX computers can vary in what IO devices they're connected to.

Text input and output can use either 80-column Hollerith punched cards, or a teletype and tape reader. Text input is one character per byte using a custom MIX character code, which defines 55 characters, although some devices may support only some of those characters. (This is necessary because EBCDIC doesn't fit into a MIX byte.)

More expensive versions of MIX may use magnetic tape or hard disk for storing larger amounts of data. Both of these do binary IO of blocks full MIX words.

IO is memory-mapped, reading or writing a block at a time. IO may happen in the background while the CPU continues executing other instructions. Background output may continue to access the data from memory. Only one operation per device can run in the background, when you start a second operation for the same device, the CPU will first wait until the previous operation completes. There is no interrupt support though, so the CPU has to poll the IO devices for when the operation is completed.

Blocks are fixed size, the block size is determined implicitly by the device. The block is one card (80 characters) for card reader and card punch, one line of fixed 70 characters for the teletype, one line of a fixed 160 characters for the printer, and 100 word for tape or disk drives. Text is represented as five characters per word, one in each byte, sign unused.

Devices are identified by a number: the teletype is 19, line printer is 18, Hollerith card reader and card punch are 16 and 17 respectively, magnetic tape drives are numbered 0..7, disk drives 8..15.

IO instructions are:

• HLT halts the machine, but the operator can continue it with no state changed.
• JRED, JBUS conditional jump to address M if the IO device number F is ready (i.e. has completed the previous operation so all input is available in memory or output buffer in memory reusable) or not ready respectively
• IN starts to read a block from IO device number F to memory starting at address M. For disks, rX gives the sector number.
• OUT starts to write a block to IO device number F from memory starting at address M. For disks, rX gives the sector number.
• IOC does an IO control operation on IO device number F, the operation determined by M and the device. If M 0, a line printer starts on the top of a new page, a disk tries to pre-seek to sector rX, a magnetic tape rewinds to the start of the tape. If M is positive or negative, a magnetic tape skips M blocks of the tape forwards or -M blocks of the tape backwards.

Startup and assembly

For startup, a MIX computer loads a single block from the punch card reader or ticker tape. TAOCP defines a text-based executable format for programs, in which memory words are stored as text in decimal numbers. This format can be then loaded with a simple bootstrap program (which is on the first two cards), which can use the NUM instruction to convert the words from decimal. The format cannot be binary because cards or paper tape cannot represent all MIX words.

TAOCP also defines an assembly language format MIXAL for MIX prorgams, and gives most program listings in that assembly language. This can then be assembled to the above mentioned executable formats. While assembly programs are often independent of the byte size, programs in the executable format work only for a specific byte size.

Extensions

TAOCP suggests some optional extensions to MIX, both in the main text and exercises. Extensions include:

• Floating point arithmetic operations. Floating-point numbers are a single word long. The floating-point format uses the byte size as the base, so the exponent shifts the value by an entire byte. Byte 1 of the word contains the biased exponent, bytes 2..5 contain the mantissa. The additional instructions for MIX with a floating point unit are:
  • FADD, FSUB, FMUL, and FDIV do floating point addition, subtraction, multiplication, and division respectively, all of which operate on rA and the memory word at address M as inputs and rA as output.
  • FCMP does tolerant comparison of rA with the memory word at address M, the tolerance is given by the word at address 0, output to the comparison flags.
  • FLOT converts integer to floating point, in place in rA.
  • FIX converts floating point to integer, in place in rA, with the overflow flag set and an undefined output in rA on overflow.
• Bitwise operations for binary machines (bitwise shift left/right, jump if even/odd, AND, XOR). The instructions are:
  • SLB and SRB: shift the magnitude bytes of rA and rX together by M bits
  • JAO, JAE, JXO, JXE: conditional jump to address M if rA is odd or even, rX is odd or even respectively.
  • AND, OR, XOR computes the corresponding bitwise operation of the magnitude bytes of rA and M, result goes to magnitude bytes of rA, sign of rA is unchanged.
• An interrupt system for IO and timers, together with memory accessible only in system mode, described in exercise 1.4.4.18.
• Advanced indexing by values of the I field of instructions greater than 6, described in exercises 2.2.2.3 to 5.
• Attaching the rX register to the traffic lights at an intersections, as well as the overflow counter for a pedestrian crossing button, described in exercise 1.3.2.20.

MIXPC extensions

The extensions listed here are nonstandard and are not part of TAOCP nor mentioned by Knuth.

MIXPC does not implement floating point, but does implement XOR and jump if even/odd (the latter works even in decimal mode, and are available for index registers too). There is also no paper tape in MIXPC (unit 19 is only the typewriter), and there is the command for the operator (but not the program) to rewind the card reader.

In addition there are four new devices:

• 32 (Music): IOC will stop any sound that is currently playing. To play a time, use OUT, where rX stores the frequency of the tone in decihertz and M is the duration in PC clock ticks.
• 33 (Lights): There are four lights which can be turned on/off independently. Use IOC to control them; the rX register tells which lights to turn on/off. Only fields 2:5 are used; any byte which is nonzero means light on, and zero means light off. (MIXPC displays them to the left of the typewriter paper)
• 34 (Random number generator): IOC will seed the random number generator; M is the seed. If M is zero, use the time of day to seed. IN will read one word into memory; all five bytes including sign are randomized to valid values in a uniform way. An implementation can ignore seeding if using a pure noise source or whatever, in which case IOC on unit 34 simply does nothing.
• 35 (Clock): IN reads one record, which contains the current time of day. The sign of this record is always positive and fields 1 and 2 are zero, while field 3 stores hours, field 4 stores minutes, and field 5 stores seconds.
• 36 (Television): Is a monochrome green CRT with 80x40 resolution. The pixels go left to right, starting on the top row, and each MIX word represents five pixels from field 1 to field 5 (sign is ignored).

The assembler included with MIXPC also uses a bootstrap program that fits on only one card, although decks from other assemblers can still be used with MIXPC too, and decks from MIXPC's assembler can still be used with other MIX implementations too. However, MIXPC is using PC character set, so if using the format from the book with MIXPC if the program contains any negative numbers, you must use character code 233 to represent MIX character code 10 (in the PC character set, 233 is the code of theta). The reverse is unnecessary though; MIXPC's assembler does not punch any Greek alphabets.

The MIXPC assembler also has some other features:

• EJMP, EJSJ, and INS pseudo-ops, which work something like COME FROM and NEXT FROM.
• BASE pseudo-op, to control whether the target computer is binary or decimal. If omitted, it outputs a deck which is compatible with both binary and decimal computers (although the number of cards is a lot more as a result).
• PUNCH and DECK pseudo-ops, which punch additional cards after the end of the program, to be read by the program after it is loaded. (This is not useful when using actual cards (since you could just use those cards directly instead, and manually compile the deck), but on modern computers it is convenient.)
• Equal-sign expressions that match will have the same address. (Use an explicit CON pseudo-op if you want to specify the addresses yourself instead.)
• The $ expression which represents the current base (usable only if the BASE command is specified, or as the operand to ENT?, ENN?, INC?, or DEC?; if there is no BASE command, no compile-time arithmetic is possible on this expression).
• FILL pseudo-op to fill to the specified address.
• COPY pseudo-op to fill to the specified address with a copy of the previous instruction.
• HOLES pseudo-op to punch "0" in the first character position of all cards other than the first and last one, to make it easier to sort the cards if they get mixed up. (Of course it won't work if they get mixed up with other decks, but if you drop the cards on the floor and there are no other computer cards, then it will work.) (This feature is not useful for modern computers, but is applicable to actual computer cards, like the opposite from PUNCH and DECK.)
• Quoted strings of arbitrary length.
• Two pass assembly, so that future references are possible.

These new pseudo-ops can be used even in programs that target a standard MIX computer; the resulting compiled program does not need to run only on MIXPC.

In order that anyone who is curious or for whatever other reason wants to examine the bootstrap card used by programs generated by the MIXPC assembler, it is included here. The quotations marks are not a part of it. You may notice difference from the one in TAOCP, which needs two cards rather than just one card.

" N O6 A O4    H N ENX   E K BU    I OALH   A. PAEN D LB    E  AEU  ABG G  9     "

MIX256

A variant of MIX (that isn't quite MIX, because MIX requires a byte size in range 64 to 100), where a byte has 8-bits, so can have 256 values.

The CHAR instruction works a bit differently, because numbers can now be larger than 10¹⁰. If the number fits in ten digits then the effect is the same as in normal MIX: the magnitude of rA is formatted to decimal digits and written to rA (five high order digits) and rX (five low order digits). Otherwise, the magnitude of rA is formatted in a mixed base {8, 32, 8, 32, 8, 32, 8, 32, 8, 32}, where the three high bits of each byte are written as the letters "STUVWXYZ" ("S" means 0), the five low bits of each byte is written as the characters "BCDEFGHIKLMNOPQRSTUVWXYZ23456789" ("B" means zero, "9" means 31), then the ten formatted digits are written from highest to lowest order into the magnitude bytes of rA and rX consecutively, so that fields 1, 3, 5 of rA and fields 2, 4 of rX store three bits. In either case, the signs of the registers and the overflow flag are unchanged. (Programs can format a signed word for punching into card by the instructions {OVERBAR EQU 20(1:1); CHAR; JANN *+2; SUB OVERBAR}. This works equally on traditional MIX and MIX256.)

There is a new NUME instruction that can be used to convert from the above decimal number format to a number. If field 1 of rA has is not one of the characters "BCDEFGHISTUVWXYZ", then the instruction behaves like NUM, that is, the reminder of each of the ten bytes in rA and rX are considered as the decimal digits of this number, and the resulting number is written to the magnitude of rA. Otherwise, ten bytes in rA and rX will be considered as mixed base {8, 32, 8, 32, 8, 32, 8, 32, 8, 32} digits, such that the reminder of the bytes modulo 40 are converted to digit values using the look-up table {0, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 24, 25, 26, 27, 28, 29, 30, 31}; the digit values in the base 8 positions are taken modulo 10, converted by the lookup table {0, 1, 0, 1, 2, 3, 4, 5, 6, 7}, and the resulting number is stored into the magnitude part of rA. In either case, the sign of rA and rX, the contents of rX, and the overflow flag, are unaffected, regardless of the result. NUME is encoded by C=5 and F=100. Assemblers that support NUME should assemble NUM instead for machines with base at most 100. (Programs can scan a signed word in the above punched format by the instructions { LDA OVERBAR(0:0); CMP OVERBAR(1:1); JGE *+2; LDAN OVERBAR(0:0); NUME}. The first instruction can be omitted for compliant card reader drivers. This works on both traditional MIX machines and MIX256, provided you replace NUME with NUM on traditional machines.)

History

MIX is defined in The Art of Computer Programming volume 1 (chapter 1.3), of which the first edition is from 1969, but I believe MIX is slightly older than that. MIX is used to write example subroutines and programs in the first three volumes of TAOCP in the first three editions (first two editions of volume 3).

Being a typical 60s computer however, Knuth has found that by the late 1990s, MIX has become obsolete. Knuth has thus designed the modern architecture MMIX to replace it. MMIX is used for the examples in volume 4A, and will be using it in future volumes (4B, 4C, 5). Eventually he will update all the examples in the first three volumes too, so the final and glorious edition of TAOCP will use only MMIX.

Instruction opcodes

The encoding of the registers for sets of instructions is:

register	rA	rI1	rI2	rI3	rI4	rI5	rI6	rX
encoding	0	1	2	3	4	5	6	7

The encoding of instructions, including some extensions, is:

C	F	Mnemonic	Time	instruction set extension
0	ignored	NOP	1
1	field	ADD	2
1	6	FADD	4	floating-point (4.2.1)
2	field	SUB	2
2	6	FSUB	4	floating-point (4.2.1)
3	field	MUL	10
3	6	FMUL	9	floating-point (4.2.1)
4	field	DIV	12
4	6	FDIV	11	floating-point (4.2.1)
5	0	NUM	10
5	1	CHAR	10
5	2	HLT	∞
5	3*	AND	?	unknown (4.5.4, 6.4)
5	4*	OR	?	unknown (6.4)
5	5	XOR	2	xor (2.5)
5	6	FLOT	3	floating-point (4.2.1)
5	7	FIX	3	floating-point (4.2.1)
5	9	INT	?	memory protection and interrupt (1.4.4)
5	100	NUME	?	large byte size (non-canon)
6	0	SLA	2
6	1	SRA	2
6	2	SLAX	2
6	3	SRAX	2
6	4	SLC	2
6	5	SRC	2
6	6	SLB	2	binary (4.5.2)
6	7	SRB	2	binary (4.5.2)
7	count	MOVE	2F+1
8+x	field	LDx	2
16+x	field	LDxN	2
24+x	field	STx	2
32	field	STJ	2
33	field	STZ	2
34	device	JBUS	1
35	device	IOC	1w
36	device	IN	1w
37	device	OUT	1w
38	device	JRED	1
39	0	JMP	1
39	1	JSJ	1
39	2	JOV	1
39	3	JNOV	1
39	4	JL	1
39	5	JE	1
39	6	JG	1
39	7	JGE	1
39	8	JNE	1
39	9	JLE	1
40+x	0	JxN	1
40+x	1	JxZ	1
40+x	2	JxP	1
40+x	3	JxNN	1
40+x	4	JxNZ	1
40+x	5	JxNP	1
40	6	JAE	1	binary (4.5.2)
40	7	JAO	1	binary (4.5.2)
47	6	JXE	1	binary (4.5.2)
47	7	JXO	1	binary (4.2.1, 4.5.2)
48+x	0	INCx	1
48+x	1	DECx	1
48+x	2	ENTx	1
48+x	3	ENNx	1
56+x	field	CMPx	2
56	6	FCMP	4	floating-point (4.2.1)

• The AND nonstandard instruction is defined in 4.5.4 and is used in an assembly listing, but the encoding doesn't seem to be specified anywhere in the books. The OR nonstandard instruction is used in an assembly listing in 6.4 but the encoding doesn't seem to be specified anywhere. David A. Smallberg's MIX old interpreter assigns the C=5, F=3 to AND, F=4 to OR, but it also seems to have these instructions and XOR affect the sign of rA, which contradicts TAOCP chapter 2.5.

The timings with ^w means that if the I/O is busy, first it must wait until it is ready before continuing.

Character codes

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

Note: Zero indicates a space, 10 and 20 and 21 are Greek alphabets, and character codes higher than 55 are not valid. The characters above are for the old version. The new version has some Greek alphabets difference: Δ instead of Θ and Σ instead of Φ. Character code 10 is also used to represent a "negative zero" on a card (positions 0 and 11 punched for Hollerith cards).

Implementations

• GNU MIX
• MIXPC