This has been lifted verbatim from Knuth volume 1. (See README for the reference.) Some examples and witty but nonessential sections that I didn't feel like typing have been omitted. Copyright (C) 1973, 1968 by Addison-Wesley; used without permission. 1.3.1 Description of MIX. ... MIX has a peculiar property in that it is both binary and decimal at the same time. The programmer doesn't actually know whether he is programming a machine with base 2 or base 10 arithmetic. ... Words. The basic unit of information is a -byte-. Each byte contains an -unspecified- amount of information, but it must be capable of holding at least 64 distinct values. That is, we know that any number between 0 and 63, inclusive, can be contained in one byte. Furthermore, each byte contains -at-most- 100 distinct values. On a binary computer a byte must therefore be composed of six bits; on a decimal computer we have two digits per byte. ... An algorithm in MIX should work properly regardless of how big a byte is. Although it is quite possible to write programs which depend on the byte size, this is an illegal act which will not be tolerated; the only legitimate programs are those which would give correct results with all byte sizes. ... A computer word is five bytes plus a sign. The sign position has only two possible values, + and -. Registers. There are nine registers in MIX. The A-register (Accumulator) is five bytes plus sign. The X-register (Extension) is also five bytes plus sign. The I-registers (Index registers) I1, I2, I3, I4, I5, and I6 each hold two bytes plus sign. The J-register (Jump address) holds two bytes, and its sign is always +. We shall use a small letter ``r'' prefixed to the name, to identify a MIX register. Thus, ``rA'' means ``register A''. The A-register has many uses, especially for arithmetic and operating on data. The X-register is an etension on the ``right-hand side'' of rA, and it is used in connection with rA to hold ten bytes of a product or dividend, or it can be used to hold information shifted to the right out of rA. The index registers rI1, rI2, rI3, rI4, rI5, and rI6 are used primarily for counting and for referencing variable memory addresses. The J-register always hold the address of the instruction following the preceding ``JUMP'' intruction, and it is primarily used in connection with subroutines. Besides thesee registers, MIX contains an overflow toggle (a single bit which is either ``on'' or ``off''), a comparison indicator (which has three values: less, equal, or greater), memory (4000 words of storage, each word with five bytes plus sign), and input-output devices (cards, tapes, etc.). Partial fields of words. The five bytes and sign of a computer word are numbered as follows: 0 1 2 3 4 5 +/- Byte Byte Byte Byte Byte. Most of the instructions allow the programmer to use only part of a word if he chooses. In this case a ``field specification'' is given. The allowable fields are those which are adjacent in a computer word, and they are represented by (L:R), where L is the number of the left-hand part and R is the number of the right-hand part of the field. Examples of field specifications are: (0:0), the sign only. (0:2), the sign and first two bytes. (0:5), the whole word. This is the most common field specification. (1:5), the whole word except the sign. (4:4), the fourth byte only. (4:5), the two least significant bytes. The use of these field specifications varies slightly from instruction to instruction, and it will be explained in detail for each instruction where it applies. Although it is generally not important to the programmer, the field (L:R) is denoted in the machine by the single number 8L + R, and this number will fit in one byte. Instruction format. Computer words used for instructions have the following form: 0 1 2 3 4 5 (3) +/- A A I F C. The rightmost byte, C, is the operation code telling what operation is to be performed. For example, C=8 is the operation LDA, ``load the A register''. The F-byte holds a modification of the operation code. F is usually a field specification (L:R)=8L + R; for example, if C=8 and F=11, the operation is ``load the A-register with the (1:3) field''. Sometimes F is used for other purposes; on input-output instructions, for example, F is the number of the affected input or output unit. The left-hand portion of the instruction, +/-AA, is the ``address''. (Note that the sign is part of the address.) The I-field, which comes next to the address, is the ``index specification'', which may be used to modify the address of an instruction. If I=0, the address +/-AA is used without change; otherwise I should contain a number {i} between 1 and 6, and the contents of index register I{i} are added algebraically to +/-AA; the result is used as the address of the instruction. this indexing process takes place on -every- instruction. We will use the letter M to indicate the address after any specified indexing has occurred. (If the addition of the index register to the address +/-AA yields a result which does not fit in two bytes, the value of M is undefined.) In most instructions, M will refer to a memory cell. The terms ``memory cell'' and ``memory location'' are used almost interchangeably in this book. We assume that there are 4000 memory cells, numbered fro 0 to 3999; hence every memory location can be addressed with two bytes. For every instruction in which M is to refer to a memory cell we must have 0 <= M <= 3999, and in this case we will write CONTENTS(M) to denote the value stored in memory location M. On certain instructions, the ``address'' M has another significance, and it may even be negative. Thus, one instruction adds M to an index register, and this operation takes account of the sign of M. Notation. To discuss instructions in a readable manner, we will use the notation OP ADDRESS,I(F) (4) to denote an instruction like (3). Here OP is a symbolic name which is given to the operation code (the C-part) of the instruction; ADDRESS is the +/-AA portion; and I, F represent the I- and F-fields, respectively. If I is zero, the ``,I'' is omitted. If F is the -normal- F-specification for this particular operator, the ``(F)'' need not be written. The normal F- specification for almost all operators is (0:5), representing a whole word. If a different F is standard, it will be mentioned explicity when we discuss a particular operator. ... Rules for each instruction. The remarks following (3) above have defined the quantities M, F, and C for every word used as an instruction. We will now define the actions corresponding to each instruction. [Knuth gives C- and F- values in each instruction's entry; I'm omitting them since you can get them from the opcodes file in this distribution.] Loading operators * LDA (load A). The specified field of CONTENTS(M) replaces the previous contents of register A. On all operations where a partial field is used as an input, the sign is used if it is a part of the field, otherwise the sign + is understood. The field is shifted over to the right-hand part of the register as it is loaded. Examples: If F is the normal field specification (0:5), the entire contents of location M is loaded. If F is (1:5), the absolute value of CONTENTS(M) is loaded with a plus sign. If M contains an -instruction- word and if F is (0:2), the ``+/-AA'' field is loaded as 0 1 2 3 4 5 +/- 0 0 0 A A. ... * LDX (load X). This is the same as LDA, except that rX is loaded instead of rA. * LD{i} (load {i}). This is the same as LDA, except that rI{i} is loaded instead of rA. An index register contains only two bytes (not five) plus sign; bytes 1, 2, 3 are always assumed to be zero. The LD{i} instruction is considered undefined if it would result in setting bytes 1, 2, 3 to anything but zero. In the description of all instructions, ``{i}'' stands for an integer, 1 <= i <= 6. Thus, LD{i} stands for six different instructions: LD1, LD2, ..., LD6. * LDAN (load A negative). * LDXN (load X negative). * LD{i}N (load {i} negative). These eight instructions are the same as LDA, LDX, LD{i}, respectively, except that the -opposite- sign is loaded. Storing operators. * STA (store A). The contents of rA replaces the field of CONTENTS(M) specified by F. The other parts of CONTENTS(M) are unchanged. On a -store- operation the field F has the opposite significance from the -load- operation. The number of bytes in the field is taken from the right- hand side of the the register and shifted -left- if necessary to be inserted in the proper field of CONTENTS(M). The sign is not altered unless it is part of the field. The contents of the register is not affected. ... * STX (store X). Same as STA except rX is stored rather than rA. * ST{i} (store {i}). Same as STA except rI{i} is stored rather than rA. Bytes 1, 2, 3 of an index register are zero; thus if rI1 contains +/- m n this behaves as though it were 0 1 2 3 4 5 +/- 0 0 0 m n. * STJ (store J). Same as ST{i} except rJ is stored, and its sign is always +. On STJ the normal field specification for F is (0:2), -not- (0:5). This is natural, since STJ is almost always done into the address field of an instruction. * STZ (store zero). Same as STA except plus zero is stored. In other words, the specified field of CONTENTS(M) is cleared to zero. Arithmetic operators. On the add, subtract, multiply, and divide operations a field specification is allowed. A field specification of ``(0:6)'' can be used to indicate a ``floating-point'' operation (see Section 4.2 [in Volume 2]), but few of the programs we will write for MIX will use this feature... The standard field specification is, as usual, (0:5). Other fields are treated as in LDA. We will use the letter V to indicate the specified field of CONTENTS(M); thus, V is the value which would have been loaded into register A if the operation code were LDA. * ADD. V is added to rA. If the magnitude of the result is too large for register A, the overflow toggle is set on, and the remainder of the addition appearing in rA is as though a ``1'' had been carried into another register to the left of A. (Otherwise the setting of the overflow toggle is unchanged.) If the result is zero, the sign of rA is unchanged. Example: The sequence of instructions below gives the sum of the five bytes of register A. STA 2000 LDA 2000(5:5) ADD 2000(4:4) ADD 2000(3:3) ADD 2000(2:2) ADD 2000(1:1) This is sometimes called ``sideways addition''. * SUB (subtract). V is subtracted from rA. Overflow may occur as in ADD. Note that because of the variable definition of byte size, overflow will occur in some MIX computers when it would not occur in others... * MUL (multiply). The 10-byte product of V times (rA) replaces registers A and X. The signs of rA and rX are both set to the algebraic sign of the result (i.e., + if the signs of V and rA were the same, and - if they were different). * DIV (divide). The value of rA and rX, treated as a 10-byte number, with the sign of rA, is divided by the value V. If V=0 or if the quotient is more than five bytes in magnitude (this is equivalent to the condition that |rA| >= |V|), registers A and X are filled with undefined information and the overflow toggle is set on. Otherwise the quotient is placed in rA and the remainder is placed in rX. The sign of rA afterward is the algebraic sign of the quotient; the sign of rX afterward is the previous sign of rA. ... Address transfer operators. In the following operations, the (possibly indexed) ``address'' M is used as a signed number, not as the address of a cell in memory. * ENTA (enter A). The quantity M is loaded into rA. The action is equivalent to ``LDA'' from a memory word containing the signed value of M. If M=0, the sign of the instruction is loaded. [I don't think the simulator works that way. Better check...] Examples: ``ENTA 0'' sets rA to zeros. ``ENTA 0,1'' sets rA to the current contents of index register 1, except that -0 is changed to +0. * ENTX (enter X). * ENT{i} (enter {i}). Analogous to ENTA, loading the appropriate register. * ENNA (enter negative A). * ENNX (enter negative X). * ENN{i} (enter negative {i}). Same as ENTA, ENTX, and ENT{i}, except that the opposite sign is loaded. Example: ``ENN3 0,3'' replaces rI3 by its negative. * INCA (increase A). The quantity M is added to rA; the action is equivalent to ``ADD'' from a memory word containing the value of M. Overflow is possible and it is treated just as in ADD. Example: ``INCA 1'' increases the value of rA by one. * INCX (increase X). The quantity M is added to rX. If overflow occurs, the action is equivalent to ADD, except that rX is used instead of rA. Register A is never affected by this instruction. * INC{i} (increase {i}). Add M to rI{i}. Overflow must not occur; if the magnitude of the result is more than two bytes, the result of this instruction is undefined. * DECA (decrease A). * DECX (decrease X). * DEC{i} (decrease {i}). These eight instructions are the same as INCA, INCX, and INC{i}, respectively, except that M is subtracted from the register rather than added. Note that the operation code C is the same for ENTA, ENNA, INCA, AND DECA; the F-field is used to distinguish the various operations in this case. Comparison operators. The comparison operators all compare the value contained in a register with a value contained in memory. The comparison indicator is then set to LESS, EQUAL, or GREATER according to whether the value of the -register- is less than, equal to, or greater than the value of the -memory- -cell-. A minus zero is -equal-to- a plus zero. * CMPA (compare A). The specified field of A is compared with the -same- field of CONTENTS(M). If the field F does not include the sign position, the fields are both thought of as positive; otherwise the sign is taken into account in the comparison. (If F is (0:0) an equal comparison always occurs, since minus zero equals plus zero.) * CMPX (compare X). This is analogous to CMPA. * CMP{i} (compare {i}). Analogous to CMPA. Bytes 1, 2, and 3 of the index register are treated as zero in the comparison. (Thus if F = (1:2), the result cannot be GREATER.) Jump operators. Ordinarily, instructions are executed in sequential oder; i.e., the instruction executed after the one in location P is the instruction found in location P+1. Several ``jump'' instructions allow this sequence to be interrupted. When such a jump takes place, the J-register is normally set to the address of the next instruction (that is, the address of the instruction which would have been next if we hadn't jumped). A ``store J'' instruction then can be used by the programmer, if desired, to set the address field of another command which will later be used to return to the original place in the program. The J-register is changed whenever a jump actually occurs in a program (except JSJ), and it is never changed except when a jump occurs. * JMP (jump). Unconditional jump: the next instruction is taken from location M. * JSJ (jump, save J). Same as JMP except that the contents of rJ are unchanged. * JOV (jump on overflow). If the overflow toggle is on, it is turned off and a JMP occurs; otherwise nothing happens. * JNOV (jump on no overflow). If the overflow toggle is off, a JMP occurs; otherwise it is turned off. * JL, JE, JG, JGE, JNE, JLE (jump on less, equal, greater, greater-or-equal, unequal, less-or-equal). Jump if the comparison indicator is set to the condition indicated. For example, JNE will jump if the comparison indicator is LESS or GREATER. The comparison indicator is not changed by these instructions. * JAN, JAZ, JAP, JANN, JANZ, JANP (jump A negative, zero, positive, nonnegative, nonzero, nonpositive). If the contents of rA satisfy the stated condition, a JMP occurs, otherwise nothing happens. ``Positive'' means -greater- than zero (not zero); ``nonpositive'' means the opposite, i.e., zero or negative. * JXN, JXZ, JXP, JXNN, JXNZ, JXNP (jump X negative, zero, positive, nonnegative, nonzero, nonpositive). * J{i}N, J{i}Z, J{i}P, J{i}NN, J{i}NZ, J{i}NP (jump {i} negative, zero, positive, nonnegative, nonzero, nonpositive). These are analogous to the corresponding operations for rA. Miscellaneous operators. * MOVE. The number of words specified by F is moved, starting from location M to the location specified by the contents of index register 1. The transfer occurs one word at a time, and rI1 is increased by the value of F at the end of the operation. If F=0, nothing happens. Care must be taken when the groups of locations involved overlap... * SLA, SRA, SLAX, SRAX, SLC, SRC (shift left A, shift right A, shift left AX, shift right AX, shift left AX circularly, shift right AX circularly). These are the ``shift'' commands. Signs of registers A, X are not affected in any way. M specifies the number of -bytes- to be shifted left or right; M must be nonnegative. SLA and SRA do not affect rX; the other shifts affect both registers as though they were a single 10-byte register. With SLA, SRA, SLAX, and SRAX, zeros are shifted into the register at one side, and bytes disappear at the other side. The instructions SLC and SRC call for a ``circulating'' shift, in which the bytes that leave one end enter in at the other end. Both rA and rX participate in a circulating shift. Examples: Register A Register X Initial contents + 1 2 3 4 5 - 6 7 8 9 10 SRAX 1 + 0 1 2 3 4 - 5 6 7 8 9 SLA 2 + 2 3 4 0 0 - 5 6 7 8 9 SRC 4 + 6 7 8 9 2 - 3 4 0 0 5 SRA 2 + 0 0 6 7 8 - 3 4 0 0 5 SLC 501 + 0 6 7 8 3 - 4 0 0 5 0 * NOP (no operation). No operation occurs, and this instruction is bypassed. F and M are ignored. * HLT (halt). The machine stops. When the computer operator restarts it, the net effect is equivalent to NOP. Input-output operators. MIX has a fair amount of input-output equipment (all of which is optional at extra cost). Each device is given a number as follows: Unit number Peripheral device Block size t Tape unit no. t (0 <= t <= 7) 100 words d Disk or drum unit no. d (8 <= d <= 15) 100 words 16 Card reader 16 words 17 Card punch 16 words 18 Printer 24 words 19 Typewriter and paper tape 14 words Not every MIX installation will have all of this equipment available; we will occasionally make appropriate assumptions about the presence of certain devices. Some devices may not be used both for input and for output. The number of words mentioned in the above tble is a fixed block size associated with each unit. Input or output with magnetic tape, disk, or drum units reads or writes full words (five bytes plus sign). Input or output with units 16 through 19, however, is always done in a -character-code- where each byte represents one alphnumeric character. Thus, five characters per MIX word are transmitted. The character code is given [in charset.c]... It is not possible to read in or write out all possible values a byte may have, since certain combinations are undefined. Not all input-output devices are capable of handling all the symbols in the character set; for example, the symbols phi and pi which appear amid the letters will perhaps not be acceptable to the card reader. When input of character code is being done, the signs of all words are set to ``+''; on output, signs are ignored. The disk and drum units are large external memory devices each containing b^2 100-word blocks, where b is the byte size. On every IN, OUT, or IOC instruction as defined below, the particular 100-word block referred to by the instruction is specified by the current contents of the two least significant bytes of rX. * IN (input). C=36; F=unit. This instruction initiates the transfer of information from the input unit specified into consecutive locations starting with M. The number of locations transferred is the block size for this unit (see the table above). The machine will wait at this point if a preceding operation for the same unit is not yet complete. The transfer of information which starts with this instruction will not be complete until somewhat later, depending on the speed of the input device, so a program must not refer to the information in memory until then. It is improper to attempt to read any record from magnetic tape which follows the latest record written on that tape. * OUT (output). C=37; F=unit. This instruction starts the transfer of information from memory locations starting at M to the output unit specified. (The machine waits until the unit is ready, if it is not initially ready.) The transfer will not be complete until somewhat later, depending on the speed of the output device, so a program must not alter the information in memory until then. * IOC (input-output control). C=35; F=unit. The machine waits, if necessary, until the specified unit is not busy. Then a control operation is performed, depending on the particular device being used. The following examples are used in various parts of this book: Magnetic tape: If M=0, the tape is rewound. If M<0 the tape is skipped backward -M records, or to the beginning of the tape, whichever comes first. If M>0, the tape is skipped forward; it is improper to skip forward over any records following the one last written on that tape. For example, the sequence ``OUT 100(3); IOC -1(3); IN 2000(3)'' writes out one hundred words onto tape 3, then reads it back in again. Unless the tape reliability is questioned, the last two instructions of that sequence are only a slow way to move words 1000-1099 to locations 2000-2099. The sequence ``OUT 1000(3); IOC +1(3)'' is improper. Disk or drum: M should be zero. The effect is to position the device according to rX so that the next IN or OUT operation on this unit will take less time if it uses the same rX setting. Printer: M should be zero. ``IOC 0(18)'' skips the printer to the top of the following page. Paper tape reader: Rewind the tape. (M should be zero). * JRED (jump ready). C=38; F=unit. A jump occurs if the specified unit is ready, i.e., finished with the preceding operation initiated by IN, OUT, or IOC. * JBUS (jump busy). C=34; F=unit. Same as JRED except the jump occurs under the opposite circumstances, i.e., when the specified unit is -not- ready. Example: In location 1000, the instruction ``JBUS 1000(16)'' will be executed repeatedly until unit 16 is ready. The simple operations above complete MIX's repertoire of input-output instructions. There is no ``tape check'' indicator, etc... Conversion Operators. * NUM (convert to numeric). This operation is used to change the character code into numeric code. M is ignored. Registers A, X are assumed to contain a 10-byte number in character code; the NUM instruction sets the magnitude of rA equal to the numerical value of this number (treated as a decimal number). The value of rX and the sign of rA are unchanged. Bytes 00, 10, 20, 30, 40, ... convert to the digit zero; bytes 01, 11, 21, ... convert to the digit one; etc. Overflow is possible, and in this case the remainder modulo the word size is retained. * CHAR (convert to characters). This operation is used to change numeric code into character code suitable for output to cards or printer. The value in rA is converted into a 10-byte decimal number which is put into register A and X in character code. The signs of rA, rX are unchanged. M is ignored. ... Timing. To give quantitative information as to how ``good'' MIX programs are, each of MIX's operations is assigned an execution time typical for present-day computers. ADD, SUB, all LOAD operations, all STORE operations (including STZ), all shift commands, and all comparison operations take two units of time. MOVE requires one unit plus two for each word moved. MUL requires 10 and DIV requires 12 units. Execution time for floating-point operations is unspecified. All remaining operations take one unit of time, plus the time the computer may be idle on the IN, OUT, IOC, or HLT instructions. Note in particular that ENTA takes on unit of time, while LDA takes two units. The timing rules are easily remembered because of the fact that, except for shifts, MUL, and DIV, the number of units equals the number of references to memory (including the reference to the instruction itself). The ``unit'' of time is a relative measure which we will denote simply by u. It may be regarded as, say, 10 microseconds (for a relatively inexpensive computer) or as 1 microsecond (for a relatively high-priced machine). Example: the sequence LDA 1000; INCA 1; STA 1000 takes exactly 5u.