diff options
| -rw-r--r-- | AUTHORS | 4 | ||||
| -rw-r--r-- | NEWS | 2 | ||||
| -rw-r--r-- | doc/COPYING.MIX.DOC | 13 | ||||
| -rw-r--r-- | doc/MIX.DOC | 526 | ||||
| -rw-r--r-- | doc/Makefile.am | 2 | ||||
| -rw-r--r-- | samples/Makefile.am | 4 | ||||
| -rw-r--r-- | samples/elevator.mixal | 305 | ||||
| -rw-r--r-- | samples/mystery.mixal | 28 |
8 files changed, 883 insertions, 1 deletions
@@ -12,3 +12,7 @@ Michael Scholz wrote the German translation po/de.po. Sergey Poznyakoff provided patches to mixlib/mix_scanner.l improving MIXAL compliance. + +Eric S. Raymond contributed the documentation file doc/MIX.DOC and the +samples sample/elevator.mixal, sample/mistery.mixal from his MIXAL +package. @@ -10,6 +10,8 @@ Please send mdk bug reports to bug-mdk@gnu.org. * Version 1.2.7 - Upgrade to Guile 2.0. Thanks to Aleix Conchillo. +- Samples and documentation from TAOCP, via MIXAL. Thanks to Eric + S. Raymond. --------------------------------------------------------------------------- * Version 1.2.6 (10/10/10): 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 + diff --git a/samples/Makefile.am b/samples/Makefile.am index 7ec030a..19c9c27 100644 --- a/samples/Makefile.am +++ b/samples/Makefile.am @@ -13,4 +13,6 @@ SUBDIRS = tests EXTRA_DIST = primes.result hello.mixal primes.mixal echo.mixal \ - permutations.mixal permutations.cardrd isains.mixal + permutations.mixal permutations.cardrd isains.mixal \ + elevator.mixal mistery.mixal + diff --git a/samples/elevator.mixal b/samples/elevator.mixal new file mode 100644 index 0000000..98e8f1d --- /dev/null +++ b/samples/elevator.mixal @@ -0,0 +1,305 @@ +*** The elevator simulation +in equ 1:1 Definition of fields +llink1 equ 2:3 within nodes +rlink1 equ 4:5 +nextinst equ 0:2 +out equ 1:1 +llink2 equ 2:3 +rlink2 equ 4:5 +*** Fixed-size tables and list heads +wait con *+2(llink1),*+2(rlink1) List head for WAIT list + con 0 NEXTTIME = 0 always +man1 con *-2(llink1),*-2(rlink1) This node represents action + con 0 M1 and it is initially the + jmp M1 sole entry in the WAIT list. +elev1 con 0 This node represents the + con 0 elevator actions, except + jmp E1 for E5 and E9. +elev2 con 0 This node represents the + con 0 independent elevator + jmp E5 at E5. +elev3 con 0 This node represents the + con 0 independent elevator + jmp E9 at E9. +avail con 0 Link to available nodes +time con 0 Current simulated time +queue equ *-3 + con *-3(llink2),*-3(rlink2) List head for QUEUE[0] + con *-3(llink2),*-3(rlink2) List head for QUEUE[1] + con *-3(llink2),*-3(rlink2) All queues initially + con *-3(llink2),*-3(rlink2) are empty + con *-3(llink2),*-3(rlink2) List head for QUEUE[4] +elevator equ *-3 + con *-3(llink2),*-3(rlink2) List head for ELEVATOR + con 0 + con 0 "Padding" for CALL table + con 0 (see lines 183-186) + con 0 +call con 0 CALLUP[0], CALLCAR[0], CALLDOWN[0] + con 0 CALLUP[1], CALLCAR[1], CALLDOWN[1] + con 0 CALLUP[2], CALLCAR[2], CALLDOWN[2] + con 0 CALLUP[3], CALLCAR[3], CALLDOWN[3] + con 0 CALLUP[4], CALLCAR[4], CALLDOWN[4] + con 0 + con 0 "Padding" for CALL table + con 0 (see lines 178-181) + con 0 +D1 con 0 Indicates door open, activity +D2 con 0 Indicates prolonged standstill +D3 con 0 Indicates door open, inactivity +*** Subroutines and control routine +insert stj 9F Insert NODE(C) to left of NODE(rI1): + ld2 3,1(llink2) rI2 <- LLINK2(rI1). + st2 3,6(llink2) LLINK2(C) <- rI2. + st6 3,1(llink2) LLINK2(rI1) <- C. + st6 3,2(rlink2) RLINK2(rI2) <- C. + st1 3,6(rlink2) RLINK2(C) <- rI1. +9H jmp * Exit from subroutine. +delete stj 9F Delete NODE(C) from its list: + ld1 3,6(llink2) P <- LLINK2(C). + ld2 3,6(rlink2) Q <- RLINK2(C). + st1 3,2(llink2) LLINK2(Q) <- P. + st2 3,1(rlink2) RLINK2(P) <- Q. +9H jmp * Exit from subroutine. +immed stj 9F Insert NODE(C) first in WAIT list: + lda time + sta 1,6 Set NEXTTIME(C) <- TIME. + ent1 wait P <- LOC(WAIT). + jmp 2F Insert NODE(C) to right of NODE(P). +hold add time rA <- TIME + rA. +sortin stj 9F Sort NODE(C) into WAIT list. + sta 1,6 Set NEXTTIME(C) <- rA. + ent1 wait P <- LOC(WAIT). + ld1 0,1(llink1) P <- LLINK1(P). + cmpa 1,1 Compare NEXTTIME fields, right to left. + jl *-2 Repeat until NEXTTIME(C) >= NEXTTIME(P). +2H ld2 0,1(rlink1) Q <- RLINK1(P). + st2 0,6(rlink1) RLINK1(C) <- Q. + st1 0,6(llink1) LLINK1(C) <- P. + st6 0,1(rlink1) RLINK1(P) <- C. + st6 0,2(llink1) LLINK1(Q) <- C. +9H jmp * Exit from subroutine. +deletew stj 9F Delete NODE(C) from WAIT list: + ld1 0,6(llink1) (This is same as lines 58-63 + ld2 0,6(rlink1) except LLINK1, RLINK1 are used + st1 0,2(llink1) instead of LLINK2, RLINK2.) + st2 0,1(rlink1) +9H jmp * +cycle1 stj 2,6(nextinst) Set NEXTINST(C) <- rJ. + jmp cycle +holdc stj 2,6(nextinst) Set NEXTINST(C) <- rJ. + jmp hold Insert NODE(C) in WAIT, delay (rA). +cycle ld6 wait(rlink1) Set current node C <- RLINK1(LOC(WAIT)). + lda 1,6 NEXTTIME(C) + sta time becomes new value of simulated TIME. + jmp deletew Remove NODE(C) from WAIT list. + jmp 2,6 Jump to NEXTINST(C). +*** Coroutine M. M1. Enter, prepare for successor. +M1 jmp values Computer IN, OUT, INTERTIME, GIVEUPTIME. + lda intertime INTERTIME is computed by VALUES subroutine. + jmp hold Put NODE(C) in WAIT, delay INTERTIME. + ld6 avail C <- AVAIL. + j6p 1F If AVAIL != A, jump. + ld6 poolmax + inc6 4 C <- POOLMAX + 4 + ld6 poolmax POOLMAX <- C. + jmp *+3 +1H lda 0,6(rlink1) + sta avail AVAIL <- RLINK1(AVAIL). + ld1 infloor rI1 <- INFLOOR (computed by VALUES above). + st1 0,6(in) IN(C) <- rI1. + ld2 outfloor rI2 <- OUTFLOOR (computed by VALUES). + st2 3,6(out) OUT(C) <- rI2. + enta 39 Put constant 39 (JMP operation code) + sta 2,6 into third word of node format (6). +M2 enta 0,4 M2. Signal and wait. Set rA <- FLOOR. + deca 0,1 FLOOR <- IN + st6 temp Save value of C. + janz 2F Jump if FLOOR != IN. + ent6 elev1 Set C <- LOC(ELEV1). + lda 2,6(nextinst) Is elevator positioned at E6? + deca E6 + janz 3F + enta E3 If so, reposition at E3. + sta 2,6(nextinst) + jmp deletew Remove it from WAIT list + jmp 4F and reinsert it at front of WAIT. +3H lda D3 + jaz 2F Jump if D3 = 0. + st6 D1 Otherwise set D1 != 0. + stz D3 Set D3 <- 0. +4H jmp immed Insert ELEV1 at front of WAIT list. + jmp M3 (rI1, rI2 have changed.) +2H dec2 0,1 rI2 <- OUT - IN. + enta 1 + j2p *+3 Jump if going up. + sta call,1(5:5) Set CALLDOWN(IN) <- 1. + jmp *+2 + sta call,1(1:1) Set CALLUP(IN) <- 1. + lda D2 + jaz decision If D2 = 0, call the DECISION subroutine. + lda elev1+2(nextinst) + deca E1 If the elevator is at E1, call + jaz decision the DECISION subroutine. +M3 ld6 temp M3. Enter queue. + ld1 0,6(in) + ent1 queue,1 rI1 <- LOC(QUEUE[IN]). + jmp insert Insert NODE(C) at right end of QUEUE[IN]. +M4A lda giveuptime + jmp holdc Wait GIVEUPTIME units. +M4 lda 0,6(in) M4. Give up. + deca 0,4 IN(C) - FLOOR + janz *+3 + lda D1 FLOOR = IN(C) + janz M4A See exercise 7. +M6 jmp delete M6. Get out. MODE(C) is deleted + lda avail from QUEUE or ELEVATOR. + sta 0,6(rlink1) AVAIL <= C. + st6 avail + jmp cycle +M5 jmp delete M5. Get in. NODE(C) is deleted + ent1 elevator from QUEUE. + jmp insert Insert it at right of ELEVATOR. + enta 1 + ld2 3,6(out) + sta call,2(3:3) Set CALLCAR[OUT(C)] <- 1. + j5nz cycle Jump if STATE != NEUTRAL. + dec2 0,4 + ent5 0,2 Set STATE to proper direction. + ent6 elev2 Set C <- LOC(ELEV2). + jmp deletew Remove E5 action from WAIT list. + enta 25 + jmp E5A Restart E5 action 25 units from now. +*** Coroutine E. +E1A jmp cycle1 Set NEXTINST <- E1, go to CYCLE. +E1 equ * E1. Wait for call. (no action) +E2A jmp holdc +E2 j5n 1F E2. Change of state? + lda call+1,4 State is GOINGUP. + add call+2,4 + add call+3,4 + add call+4,4 + jap E3 Are there calls for higher floors? + lda call-1,4(3:3) If not, have passenger in the + add call-2,4(3:3) elevator called for lower floors? + add call-3,4(3:3) + add call-4,4(3:3) + jmp 2F +1H lda call-1,4 State is GOINGDOWN. + add call-2,4 + add call-3,4 + add call-4,4 + jap E3 Are there calls for lower floors? [right???] + lda call+1,4(3:3) If not, have passenger in the + add call+2,4(3:3) elevator called for higher floors? + add call+3,4(3:3) + add call+4,4(3:3) +2H enn5 0,5 Reverse direction of STATE. + stz call,4 Set CALL variable to zero. + janz E3 Jump if calls for opposite direction, + ent5 0 otherwise, set STATE <- NEUTRAL. +E3 ent6 elev3 E3. Open door. + lda 0,6 If activity E9 is already scheduled, + janz deletew remove it from the WAIT list. + enta 300 + jmp hold Schedule activity E9 after 300 units. + ent6 elev2 + enta 76 + jmp hold Schedule activity E5 after 76 units. + st6 D2 Set D2 != 0. + st6 D1 Set D1 != 0. + enta 20 +E4A ent6 elev1 + jmp holdc +E4 enta 0,4 E4. Let people out, in. + sla 4 Set OUT field of rA to FLOOR. + ent6 elevator C <- LOC(ELEVATOR). +1H ld6 3,6(llink2) C <- LLINK2(C). + cmp6 =elevator= Search ELEVATOR list, right to left. + je 1F If C = LOC(ELEVATOR), search is complete. + cmpa 3,6(out) Compare OUT(C) with FLOOR. + jne 1B If not equal, continue search, + enta M6 otherwise, prepare to send man to M6. + jmp 2F +1H ld6 queue+3,4(rlink2) Set C <- RLINK2(LOC(QUEUE[FLOOR])). + cmp6 3,6(rlink2) Is C = RLINK2(C)? + je 1F If so, the queue is empty. + jmp deletew If not, cancel action M4 for the man. + enta M5 Prepare to send man to M5. +2H sta 2,6(nextinst) Set NEXTINST(C). + jmp immed Put him at front of WAIT list. + enta 25 + jmp E4A Wait 25 units and repeat E4. +1H stz D1 Set D1 <- 0. + st6 D3 Set D3 != 0. + jmp cycle Return to simulate other events. +E5A jmp holdc +E5 lda D1 E5. Close door. + jaz *+3 Is D1 = 0? + enta 40 If not, people are still getting in or out. + jmp E5A Wait 40 units, repeat E5. + stz D3 If D1 = 0, set D3 <- 0. + enta 20 + ent6 elev1 +E6A jmp holdc Wait 20 units, then go to E6. +E6 j5n *+2 E6. Prepare to move. + stz call,4(1:3) If STATE != GOINGDOWN, CALLUP and CALLCAR + j5p *+2 on this floor are reset. + stz call,4(3:5) If != GOINGUP, reset CALLCAR and CALLDOWN. + j5z decision Perform DECISION subroutine. +E6B j5z E1A If STATE = NEUTRAL, go to E1 and wait. + lda D2 + jaz *+4 + ent6 elev3 Otherwise, if D2 != 0, + jmp deletew cancel activity E9 + stz elev3 (see line 202). + enta 15 + ent6 elev1 Wait 15 units of time. + j5n E8A If STATE = GOINGDOWN, go to E8. +E7A jmp holdc +E7 inc4 1 E7. Go up a floor. + enta 51 + jmp holdc Wait 51 units. + lda call,4(1:3) Is CALLCAR[FLOOR] or CALLUP[FLOOR] != 0? + jap 1F + ent1 -2,4 If not, + j1z 2F is FLOOR = 2? + lda call,4(5:5) If not, is CALLDOWN[FLOOR] != 0? + jaz E7 If not, repeat step E7. +2H lda call+1,4 + add call+2,4 + add call+3,4 + add call+4,4 + janz E7 Are there calls for higher floors? +1H enta 14 It is time to stop the elevator. + jmp E2A Wait 14 units and go to E2. +E8A jmp holdc +* ... (see exercise 8) + + + + + + + + + + + + + + + +E9 stz 0,6 E9. Set inaction indicator. + stz D2 D2 <- 0. + jmp decision Perform DECISION subroutine. + jmp cycle Return to simulation of other events. + +* (fill in VALUES, DECISION routines here) + +begin ent4 2 Start with FLOOR = 2 + ent5 0 and STATE = NEUTRAL. + jmp cycle Begin simulation. +poolmax end begin Storage pool follows literals, temp storage + +* Warning: there's probably a typo or two in this file. diff --git a/samples/mystery.mixal b/samples/mystery.mixal new file mode 100644 index 0000000..faa1775 --- /dev/null +++ b/samples/mystery.mixal @@ -0,0 +1,28 @@ +* Mystery program +* (Knuth, vol 1, p 153) + +printer equ 18 +buf orig *+3000 +1H ent1 1 + ent2 0 + ldx 4F +2H ent3 0,1 +3H stz buf,2 + inc2 1 + dec3 1 + j3p 3B + stx buf,2 + inc2 1 + inc1 1 + cmp1 =75= + jl 2B + enn2 2400 + out buf+2400,2(printer) + inc2 24 + j2n *-2 + hlt + +4H con "aaaaa" + end 1B + +* End of mystery.mix |