diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/COPYING.MIX.DOC | 13 | ||||
| -rw-r--r-- | doc/MIX.DOC | 526 | ||||
| -rw-r--r-- | doc/Makefile.am | 2 |
3 files changed, 541 insertions, 0 deletions
diff --git a/doc/COPYING.MIX.DOC b/doc/COPYING.MIX.DOC new file mode 100644 index 0000000..4365190 --- /dev/null +++ b/doc/COPYING.MIX.DOC @@ -0,0 +1,13 @@ +The file MIX.DOC, as well as the samples in elevator.mixal and mistery.mixal +are a contribution from Eric S. Raymond's MIXAL. They contain the actual +text of TAOCP vol 1 describing MIXAL and two verbatim programs from the book. +Donald Knuth and Addison Wesley granted Eric permission for distributing the +under the following terms, which we inherit: + +The source code in prime.mix, mystery.mix, and elevator.mix and the +text in MIX.DOC are excerpted from "The Art Of Computer Programming". +Addison-Wesley and Donald Knuth have specifically granted permission +for this material and all other MIX code examples from that book to be +distributed in conjunction with any open-source implementation of MIX +under the license(s) applying to that implementation. + diff --git a/doc/MIX.DOC b/doc/MIX.DOC new file mode 100644 index 0000000..b1f7d62 --- /dev/null +++ b/doc/MIX.DOC @@ -0,0 +1,526 @@ +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. diff --git a/doc/Makefile.am b/doc/Makefile.am index e9c18b8..fbc122c 100644 --- a/doc/Makefile.am +++ b/doc/Makefile.am @@ -19,3 +19,5 @@ mdk_TEXINFOS = mdk_intro.texi mdk_ack.texi mdk_tut.texi mdk_gstart.texi \ mdk_index.texi mdk_gmixvm.texi mdk_install.texi \ mdk_mixguile.texi mdk_copying.texi mdk_findex.texi +EXTRA_DIST = MIX.DOC COPYING.MIX.DOC + |