diff options
Diffstat (limited to 'doc')
| -rw-r--r-- | doc/mdk.texi | 860 |
1 files changed, 671 insertions, 189 deletions
diff --git a/doc/mdk.texi b/doc/mdk.texi index 47dc6b9..acf6b09 100644 --- a/doc/mdk.texi +++ b/doc/mdk.texi @@ -71,22 +71,21 @@ approved by the Free Software Foundation. @node Top, Introduction, (dir), (dir) @ifinfo -This file documents the @sc{mdk} utilities to develop programs -using Donald Knuth's MIXAL language. MIXAL is an assembler-like -language for writing programs for the (virtual) MIX computer. They are -described in the first volume of @cite{The Art of Computer Programming} -by D. Knuth (Addison Wesley, 1997), and used throughout the (up to now) -three published volumes. +This file documents the @sc{mdk} utilities to develop, run and debug +programs written in the MIXAL programming language. MIXAL is an +assembler-like language for programming a virtual computer called +MIX. They were created by Donald Knuth in the first volume of @cite{The +Art of Computer Programming} (Addison Wesley, 1997). @sc{mdk} was written by @value{JAO} and is released under the GNU General Public license (@pxref{Copying}), so that users are free to share -and change it. +and improve it. @end ifinfo @menu * Introduction:: -* MIX and MIXAL overview:: Quick tutorial of Knuth's MIX computer. +* MIX and MIXAL tutorial:: Learn the innards of MIX and MIXAL. * Getting started:: Basic usage of the @sc{mdk} tools. * mixvm:: Invoking the MIX virtual machine. * mixasm:: Invoking the MIXAL assembler. @@ -97,7 +96,7 @@ and change it. @detailmenu --- The Detailed Node Listing --- -MIX and MIXAL overview +MIX and MIXAL tutorial * The MIX computer:: Architecture and instruction set of the MIX computer. @@ -110,23 +109,25 @@ The MIX computer MIX instruction set +* Instruction structure:: * Loading operators:: * Storing operators:: * Arithmetic operators:: * Address transfer operators:: * Comparison operators:: * Jump operators:: -* Miscellaneous operators:: * Input-output operators:: * Conversion operators:: +* Shift operators:: +* Miscellaneous operators:: MIXAL -* Instructions:: -* Comments:: -* Expressions:: -* Local symbols:: -* Miscellaneous:: +* Basic structure:: Writing basic MIXAL programs. +* MIXAL directives:: Assembler directives. +* Expressions:: Evaluation of expressions. +* Local symbols:: Special symbol table entries. +* Literal constants:: Specifying an immediate operand. Getting started @@ -154,7 +155,7 @@ Running the program @end detailmenu @end menu -@node Introduction, MIX and MIXAL overview, Top, Top +@node Introduction, MIX and MIXAL tutorial, Top, Top @comment node-name, next, previous, up @unnumbered Introduction @cindex Introduction @@ -165,14 +166,14 @@ associated machine-code and assembly languages to ilustrate the concepts and algorithms as they are presented. The MIX's architecture is a simplified version of those found in real -CSIC CPUs, and the MIX assembly language provides a set of primitives -that will be very familiar to any person with a minimum experience in -assembly programming. The MIX/MIXAL definition is powerful and complete -enough to provide a virtual development platform for writing quite -complex programs, and close enough to real computers to be worth using -when learning programming techniques. At any rate, if you want to read -and learn from Knuth excellent books on computer programming, a MIX -development environment would come in handy. +CISC CPUs, and the MIX assembly language (MIXAL) provides a set of +primitives that will be very familiar to any person with a minimum +experience in assembly programming. The MIX/MIXAL definition is powerful +and complete enough to provide a virtual development platform for +writing quite complex programs, and close enough to real computers to be +worth using when learning programming techniques. At any rate, if you +want to learn or improve your programming skills, a MIX development +environment would come in handy. The @sc{mdk} package aims at providing such virtual development environment on a GNU box. Thus, @sc{mdk} offers you a set of utilities @@ -193,30 +194,26 @@ virtual machine for executing and debugging MIX programs. These binary programs could be written by hand, but it is easier to produce them compiling MIXAL source files, using the MIXAL assembler @code{mixasm}. -This manual gives you a brief survey of MIX and MIXAL, and a thorough +This manual gives you a tutorial of MIX and MIXAL, and a thorough description of the use of the @sc{mdk} utilities. -@node MIX and MIXAL overview, Getting started, Introduction, Top +@node MIX and MIXAL tutorial, Getting started, Introduction, Top @comment node-name, next, previous, up -@chapter MIX and MIXAL overview +@chapter MIX and MIXAL tutorial @cindex MIX @cindex MIXAL In the book series @cite{The Art of Computer Programming}, by D. Knuth, -a virtual computer, the MIX, is used by the author, together with the -set of binary instructions that the virtual CPU accepts, in the example -programs and exercises. Like any other real computer, there is a -symbolic assembler language that can be used to program the MIX: the MIX -assembly language, or MIXAL for short. The MIX computer architecture and -the MIXAL language are defined in volume 1 of the series, -@cite{Fundamental Algorithms}. In the following subsections you will -find a brief survey of these topics, which is not meant to replace the -precise description given in the book (if you are interested in using -the @sc{mdk} utilities, most probably the reason is that you have access -to a copy of TAOCP), but to serve as a quick reminder of key points and -nomenclature used in the rest of this manual. +a virtual computer, the MIX, is used by the author (together with the +set of binary instructions that the virtual CPU accepts) to illustrate +the algorithms and skills that every serious programmer should +master. Like any other real computer, there is a symbolic assembler +language that can be used to program the MIX: the MIX assembly language, +or MIXAL for short. In the following subsections you will find a tutorial +on these topics, which will teach you the basics of the MIX architecture +and how to program a MIX computer using MIXAL. @menu * The MIX computer:: Architecture and instruction set @@ -224,11 +221,11 @@ nomenclature used in the rest of this manual. * MIXAL:: The MIX assembly language. @end menu -@node The MIX computer, MIXAL, MIX and MIXAL overview, MIX and MIXAL overview +@node The MIX computer, MIXAL, MIX and MIXAL tutorial, MIX and MIXAL tutorial @comment node-name, next, previous, up @section The MIX computer -In this section, you will find a brief description of the MIX computer, +In this section, you will find a description of the MIX computer, its components and instruction set. @menu @@ -264,7 +261,7 @@ for a @emph{regular} byte. Unless otherwise stated, we shall use the word @dfn{byte} to refer to a MIX 6-bit byte. A MIX @dfn{word} is defined as a set of 5 bytes plus a sign. The bytes -within a word are numbered for 1 to 5, being byte number one the most +within a word are numbered from 1 to 5, being byte number one the most significant one. The sign is denoted by index 0. Graphically, @example @@ -274,13 +271,17 @@ significant one. The sign is denoted by index 0. Graphically, | +/- | byte | byte | byte | byte | byte | ----------------------------------------------- @end example +@noindent +Sample MIX words are @samp{- 12 00 11 01 63} and @samp{+ 12 11 34 43 +00}. You can refer to subfields within a word using a @dfn{field specification} or @dfn{fspec} of the form @samp{(L:R)}, where @samp{L} denotes the first byte and @samp{R} the last byte of the subfield. When @samp{L} is zero, the subfield includes the word's -sign. An fspec can be also represented as a single value @samp{F}, given -by @code{F = 8*L + R}. +sign. An fspec can also be represented as a single value @samp{F}, given +by @code{F = 8*L + R} (thus the fspec @samp{(1:3)}, denoting the first +three bytes of a word, is represented by the integer 11). The MIX computer stores information in @dfn{registers}, that can store either a word or two bytes and sign (see below), and @dfn{memory cells}, @@ -288,10 +289,16 @@ each one containing a word. Specifically, the MIX computer has 4000 memory cells with addresses 0 to 3999 (i.e., two bytes are enough to address a memory cell) and the following registers: +@cindex rA +@cindex rX +@cindex rJ +@cindex rIn +@cindex register + @table @samp @item rA A register. General purpose register holding a word. Usually its -contents serves as operator for arithmetic and storing instructions. +contents serves as the operand of arithmetic and storing instructions. @item rX X register. General purpose register holding a word. Often it acts as an extension or a replacement of @samp{rA}. @@ -301,7 +308,7 @@ usually representing a jump address. @item rI[1-6] Index registers. These six registers can store a signed two-byte value. Their contents is used as indexing values for the computation of -an effective memory address. +effective memory addresses. @end table @cindex @sc{ov} @@ -320,15 +327,91 @@ An @dfn{overflow toggle} (a single bit with values @dfn{on} or @item A @dfn{comparison indicator} (having three values: @dfn{EQUAL}, @dfn{GREATER} or @dfn{LESS}). In this manual, this indicator is denoted -@sc{cm}. +@sc{cm}, and its possible values are abbreviated as @dfn{E}, @dfn{G} and +@dfn{L}. @item -Input-output devices. Each device is labelled as @samp{Un}, where -@samp{n} runs from 0 to 19@footnote{@samp{U0-7} are magnetic tape units, -@samp{U8-15} are disks and drums, @samp{U16} is a card reader, -@samp{U17} is a card writer, @samp{U18} is a line printer and -@samp{U19}, a paper tape.}. +Input-output block devices. Each device is labelled as @samp{Un}, where +@samp{n} runs from 0 to 20. In Knuth's definition, @samp{U0-7} are +magnetic tape units, @samp{U8-15} are disks and drums, @samp{U16} is a +card reader, @samp{U17} is a card writer, @samp{U18} is a line printer +and, @samp{U19} is a typewriter terminal, and @samp{U20}, a paper +tape. Our implementation maps these devices to disk files, except for +@samp{U19}, which represents the standard output. @end itemize +As noted above, communication of the MIX computer with the external +world is achieved by a set of input-output devices which can be +"connected" to it. Interchange of information is done in blocks of words +whose length depend on the device at hand (see @pxref{Devices}). These +words are interpreted by the device either as binary information (for +devices 0-16), or as representing printable characters (devices +17-20). In the last case, each MIX byte is mapped onto a character +according to the following table: + +@multitable {00} {C} {00} {C} {00} {C} {00} {C} +@item 00 @tab @tab 01 @tab A @tab 02 @tab B @tab 03 @tab C +@item 04 @tab D @tab 05 @tab E @tab 06 @tab F @tab 07 @tab G +@item 08 @tab H @tab 09 @tab I @tab 10 @tab d @tab 11 @tab J +@item 12 @tab K @tab 13 @tab L @tab 14 @tab M @tab 15 @tab N +@item 16 @tab O @tab 17 @tab P @tab 18 @tab Q @tab 19 @tab R +@item 20 @tab s @tab 21 @tab p @tab 22 @tab S @tab 23 @tab T +@item 24 @tab U @tab 25 @tab V @tab 26 @tab W @tab 27 @tab X +@item 28 @tab Y @tab 29 @tab Z @tab 30 @tab 0 @tab 31 @tab 1 +@item 32 @tab 2 @tab 33 @tab 3 @tab 34 @tab 4 @tab 35 @tab 5 +@item 36 @tab 6 @tab 37 @tab 7 @tab 38 @tab 8 @tab 39 @tab 9 +@item 40 @tab . @tab 41 @tab , @tab 42 @tab ( @tab 43 @tab ) +@item 44 @tab + @tab 45 @tab - @tab 46 @tab * @tab 47 @tab / +@item 48 @tab = @tab 49 @tab $ @tab 50 @tab < @tab 51 @tab > +@item 52 @tab @@ @tab 53 @tab ; @tab 54 @tab : @tab 55 @tab ' +@end multitable +@noindent +The value 0 represents a whitespace. Lowercase letters (d, s, p) +correspond to symbols non representable as ASCII characters (uppercase +delta, sigma and gamma, respectively) and byte values 56-63 have no +associated character. + +Finally, the MIX computer features a virtual CPU which controls the +above components, and which is able to execute a rich set of +instructions (constituting its machine language, similar to those +commonly found in real CPUs), including arithmetic, logical, storing, +comparison and jump instructions. Being a typical von Neumann computer, +the MIX CPU fetchs binary instructions from memory sequentially (unless +a jump instruction is found), and stores the address of the next +instruction to be executed in an internal register called @dfn{location +counter} (also known as program counter in other architectures). + +The next section, @xref{MIX instruction set}, gives a complete description +of the available MIX binary instructions. + +@node MIX instruction set, , MIX architecture, The MIX computer +@comment node-name, next, previous, up +@subsection MIX instruction set +@cindex instruction set + +The following subsections fully describe the instruction set of the MIX +computer. We begin with a description of the structure of binary +instructions and the notation used to refer to their subfields. The +remaininig subsections are devoted to describing the actual instructions +available to the MIX programmer. + +@menu +* Instruction structure:: +* Loading operators:: +* Storing operators:: +* Arithmetic operators:: +* Address transfer operators:: +* Comparison operators:: +* Jump operators:: +* Input-output operators:: +* Conversion operators:: +* Shift operators:: +* Miscellaneous operators:: +@end menu + +@node Instruction structure, Loading operators, MIX instruction set, MIX instruction set +@comment node-name, next, previous, up +@subsubsection Instruction structure + MIX @dfn{instructions} are codified as words with the following subfield structure: @@ -363,37 +446,57 @@ or, graphically, ------------------------------------------------ @end example -The MIX computer understands a quite complete set of instructions -commonly found in real computers, including arithmetic, logical, -storing, comparison and jump instructions. We refer the reader to -D. Knuth's TAOCP (volume 1, section 1.3.1) for a complete description of -these instructions. @xref{MIX instruction set}, gives a quick synopsis -of the available instructions. +For a given instruction, @samp{M} stands for +the memory address obtained after indexing the ADDRESS subfield +(using its INDEX byte), and @samp{V} is the contents of the +subfield indicated by MOD of the memory cell with address @samp{M}. For +instance, suppose that we have the following contents of MIX registers +and memory cells: -@node MIX instruction set, , MIX architecture, The MIX computer -@comment node-name, next, previous, up -@subsection MIX instruction set -@cindex instruction set +@example +[rI2] = + 00 63 +[31] = - 10 11 00 11 22 +@end example +@noindent +where @samp{[n]} denotes the contents of the nth memory cell and +@samp{[rI2]} the contents of register @samp{rI2}@footnote{In general, +@samp{[X]} will denote the contents of entity @samp{X}; thus, by +definition, @w{@samp{V = [M](MOD)}}.}. Let us consider the binary +instruction @w{@samp{I = - 00 32 02 11 10}}. For this instruction we +have: -The following subsections summarize the instruction set of the MIX -computer. In this description @samp{M} stands for -the memory address obtained after indexing the ADDRESS subfield of the -instruction (using its INDEX byte), and @samp{V} is the contents of the -subfield indicated by MOD of the memory cell with address @samp{M}. +@example +ADDRESS = - 00 32 = -32 +INDEX = 02 = 2 +MOD = 11 = (1:3) +OPCODE = 10 -@menu -* Loading operators:: -* Storing operators:: -* Arithmetic operators:: -* Address transfer operators:: -* Comparison operators:: -* Jump operators:: -* Miscellaneous operators:: -* Input-output operators:: -* Conversion operators:: -@end menu +M = ADDRESS + [rI2] = -32 + 63 = 31 +V = [M](MOD) = (- 10 11 00 11 22)(1:3) = + 00 00 10 11 00 +@end example -@node Loading operators, Storing operators, MIX instruction set, MIX instruction set +In the following subsections, we will assing to each MIX instruction a +mnemonic, or symbolic name. For instance, the mnemonic of @samp{OPCODE} +10 is @samp{LD2}. Thus we can rewrite the above instruction as + +@example +LD2 -32,2(1:3) +@end example +@noindent +or, for a generic instruction: + +@example +MNEMONIC ADDRESS,INDEX(MOD) +@end example +@noindent +Some instructions are identified by both the OPCODE and the MOD +fields. In these cases, the MOD will not appear in the above symbolic +representation. Also when ADDRESS or INDEX are zero, they can be +omitted. Finally, MOD defaults to (0:5) (meaning the +whole word). + + +@node Loading operators, Storing operators, Instruction structure, MIX instruction set @comment node-name, next, previous, up @subsubsection Loading operators @cindex loading operators @@ -403,27 +506,82 @@ register. @ftable @code @item LDA -Load rA. OPCODE = 8, MOD = fspec. @code{rA <- V}. +Put in rA the contents of cell no. M. +OPCODE = 8, MOD = fspec. @code{rA <- V}. @item LDX -Load rX. OPCODE = 15, MOD = fspec. @code{rX <- V}. +Put in rX the contents of cell no. M. +OPCODE = 15, MOD = fspec. @code{rX <- V}. @item LDi -Load rIi. OPCODE = 8 + i, MOD = fspec. @code{rIi <- V}. +Put in rIi the contents of cell no. M. +OPCODE = 8 + i, MOD = fspec. @code{rIi <- V}. @item LDAN -Load rA negative. OPCODE = 16, MOD = fspec. @code{rA <- -V}. +Put in rA the negative contents of cell no. M. +OPCODE = 16, MOD = fspec. @code{rA <- -V}. @item LDXN -Load rX negative. OPCODE = 23, MOD = fspec. @code{rX <- -V}. +Put in rX the negative contents of cell no. M. +OPCODE = 23, MOD = fspec. @code{rX <- -V}. @item LDiN -Load rIi negative. OPCODE = 16 + i, MOD = fspec. @code{rIi <- -V}. +Put in rIi the negative contents of cell no. M. +OPCODE = 16 + i, MOD = fspec. @code{rIi <- -V}. @end ftable +In all the above load instructions the @samp{MOD} field selects the +bytes of the memory cell with address @samp{M} which are loaded into the +requisite register (indicated by the @samp{OPCODE}). For instance, the +word @w{@samp{+ 00 13 01 27 11}} represents the instruction + +@example +LD3 13,1(3:3) + ^ ^ ^ ^ + | | | | + | | | --- MOD = 27 = 3*8 + 7 + | | --- INDEX = 1 + | --- ADDRESS = 00 13 + --- OPCODE = 11 +@end example +Let us suppose that, prior to this instruction execution, the state of +the MIX computer is the following: + +@example +[rI1] = - 00 01 +[rI3] = + 24 12 +[12] = - 01 02 03 04 05 +@end example +@noindent +As, in this case, @w{@samp{M = 13 + [rI1] = 12}}, we have +@w{@samp{V = [M](3:3) = (- 01 02 03 04 05)(3:3) = + 00 00 00 00 03}} +(note that the specified subfield is left-padded with null bytes to +complete a word). Hence, the MIX state, after the instruction execution, +will be + +@example +[rI1] = - 00 01 +[rI3] = + 00 03 +[12] = - 01 02 03 04 05 +@end example + +To further illustrate loading operators, the following table shows the +contents of @samp{rX} after different @samp{LDX} instructions: + +@table @samp +@item LDX 12(0:0) [rX] = - 00 00 00 00 00 +@item LDX 12(0:1) [rX] = - 00 00 00 00 01 +@item LDX 12(3:5) [rX] = + 00 00 03 04 05 +@item LDX 12(3:4) [rX] = + 00 00 00 03 04 +@item LDX 12(0:5) [rX] = - 01 02 03 04 05 +@end table + @node Storing operators, Arithmetic operators, Loading operators, MIX instruction set @comment node-name, next, previous, up @subsubsection Storing operators @cindex storing operators -The following instructions are used to store a subfield of a register -into a memory location. +The following instructions are the inverse of the load +operations: they are used to store a subfield of a register +into a memory location. Here, MOD represents the subfield of the memory +cell that is to be overwritten with bytes from a register. These bytes +are taken beginning by the rightmost side of the register. @ftable @code @item STA @@ -438,6 +596,27 @@ Store rJ. OPCODE = 32, MOD = fspec. @code{V <- rJ}. Store zero. OPCODE = 33, MOD = fspec. @code{V <- 0}. @end ftable +By way of example, consider the instruction @samp{STA 1200(2:3)}. It +causes the MIX to fetch bytes no. 4 and 5 of register A and copy them to +bytes 2 and 3 of memory cell no. 1200 (remember that, for these +instructions, MOD specifies a subfield of @emph{the memory +address}). The others bytes of the memory cell retain their +values. Thus, if prior to the instruction execution we have + +@example +[1200] = - 20 21 22 23 24 +[rA] = + 01 02 03 04 05 +@end example +@noindent +we will end up with + +@example +[1200] = - 20 04 05 23 24 +[rA] = + 01 02 03 04 05 +@end example + +As a second example, @samp{ST2 1000(0)} will set the sign of +@samp{[1000]} to that of @samp{[rI2]}. @node Arithmetic operators, Address transfer operators, Storing operators, MIX instruction set @comment node-name, next, previous, up @@ -450,98 +629,179 @@ rX register and memory contents. @ftable @code @item ADD Add and set OV if overflow. OPCODE = 1, MOD = fspec. -@code{rA <- rA +V}. +@w{@code{rA <- rA +V}}. @item SUB Sub and set OV if overflow. OPCODE = 2, MOD = fspec. -@code{rA <- rA - V}. +@w{@code{rA <- rA - V}}. @item MUL Multiply V times rA and store the 10-bytes product in rAX. -OPCODE = 3, MOD = fspec. @code{rAX <- rA x V}. +OPCODE = 3, MOD = fspec. @w{@code{rAX <- rA x V}}. @item DIV rAX is considered a 10-bytes number, and it is divided by V. -OPCODE = 4, MOD = fspec. @code{rA <- rAX / V}, @code{rX} <- reminder. +OPCODE = 4, MOD = fspec. @w{@code{rA <- rAX / V}}, @code{rX} <- reminder. @end ftable +In all the above instructions, @samp{[rA]} is one of the operands +of the binary arithmetic operation, the other being @samp{V} (that is, +the specified subfield of the memory cell with address @samp{M}), padded +with zero bytes on its left-side to complete a word. In multiplication +and division, the register @samp{X} comes into play as a right-extension +of the register @samp{A}, so that we are able to handle 10-byte numbers +whose more significant bytes are those of @samp{rA} (the sign of this +10-byte number is that of @samp{rA}: @samp{rX}'s sign is ignored). + +Addition and substraction of MIX words can give rise to overflows, since +the result is stored in a register with room to only 5 bytes (plus +sign). When this occurs, the operation result modulo @w{1,073,741,823} +(the maximum value storable in a MIX word) is stored in @samp{rA}, and +the overflow toggle is set to TRUE. + @node Address transfer operators, Comparison operators, Arithmetic operators, MIX instruction set @comment node-name, next, previous, up @subsubsection Address transfer operators @cindex address transfer operators -In these instructions, M (the address of the instruction after indexing) -is used as a number instead of as the address of a memory cell. +In these instructions, @samp{M} (the address of the instruction after +indexing) is used as a number instead of as the address of a memory +cell. @ftable @code @item ENTA -Enter rA. OPCODE = 48, MOD = 2. @code{rA <- M}. +Enter [rA]. OPCODE = 48, MOD = 2. @code{rA <- M}. @item ENTX -Enter rX. OPCODE = 55, MOD = 2. @code{rX <- M}. +Enter [rX]. OPCODE = 55, MOD = 2. @code{rX <- M}. @item ENTi -Enter rIi. OPCODE = 48 + i, MOD = 2. @code{rIi <- M}. +Enter [rIi]. OPCODE = 48 + i, MOD = 2. @code{rIi <- M}. @item ENNA -Enter negative rA. OPCODE = 48, MOD = 3. @code{rA <- -M}. +Enter negative [rA]. OPCODE = 48, MOD = 3. @code{rA <- -M}. @item ENNX -Enter negative rX. OPCODE = 55, MOD = 3. @code{rX <- -M}. +Enter negative [rX]. OPCODE = 55, MOD = 3. @code{rX <- -M}. @item ENNi -Enter negative rIi. OPCODE = 48 + i, MOD = 3. @code{rIi <- -M}. +Enter negative [rIi]. OPCODE = 48 + i, MOD = 3. @code{rIi <- -M}. @item INCA -Increase rA. OPCODE = 48, MOD = 0. @code{rA <- rA + M}. +Increase [rA]. OPCODE = 48, MOD = 0. @code{rA <- rA + M}. @item INCX -Increase rX. OPCODE = 55, MOD = 0. @code{rX <- rX + M}. +Increase [rX]. OPCODE = 55, MOD = 0. @code{rX <- rX + M}. @item INCi -Increase rIi. OPCODE = 48 + i, MOD = 0. @code{rIi <- rIi + M}. +Increase [rIi]. OPCODE = 48 + i, MOD = 0. @code{rIi <- rIi + M}. @item DECA -Decrease rA. OPCODE = 48, MOD = 1. @code{rA <- rA - M}. +Decrease [rA]. OPCODE = 48, MOD = 1. @code{rA <- rA - M}. @item DECX -Decrease rX. OPCODE = 55, MOD = 0. @code{rX <- rX - M}. +Decrease [rX]. OPCODE = 55, MOD = 0. @code{rX <- rX - M}. @item DECi -Decrease rIi. OPCODE = 48 + i, MOD = 0. @code{rIi <- rIi - M}. +Decrease [rIi]. OPCODE = 48 + i, MOD = 0. @code{rIi <- rIi - M}. @end ftable +In the above instructions, the subfield @samp{ADDRESS} acts as an +immediate (indexed) operand, and allow us to set directly the contents +of the MIX registers without an indirection to the memory cells (in a +real CPU this would mean that they are faster that the previously +discussed instructions, whose operands are fetched from memory). So, if +you want to store in @samp{rA} the value -2000 (- 00 00 00 31 16), you +can use the binary instruction @w{+ 31 16 00 03 48}, or, symbolically, + +@example +ENNA 2000 +@end example +@noindent +Used in conjuction with the store operations (@samp{STA}, @samp{STX}, +etc.), these instructions also allow you to set memory cells contents to +concrete values. + +Note that in these address transfer operators, the @samp{MOD} field is +not a subfield specificator, but serves to define (together with +@samp{OPCODE}) the concrete operation to be performed. @node Comparison operators, Jump operators, Address transfer operators, MIX instruction set @comment node-name, next, previous, up @subsubsection Comparison operators @cindex comparison operators -The following instructions compare the value of a register with V, and -set the CM indicator to the result of the comparison. +So far, we have learned how to move values around between the MIX +registers and its memory cells, and also how to perform arithmetic +operations using these values. But, in order to write non-trivial +programs, other functionalities are needed. One of the most common is +the ability to compare two values, which, combined with jumps, will +allow the execution of conditional statements. +The following instructions compare the value of a register with @samp{V}, and +set the @sc{cm} indicator to the result of the comparison (i.e. to +@samp{E}, @samp{G} or @samp{L}, equal, greater or lesser respectively). @ftable @code @item CMPA -Compare rA with V. OPCODE = 56, MOD = fspec. +Compare [rA] with V. OPCODE = 56, MOD = fspec. @item CMPX -Compare rX with V. OPCODE = 63, MOD = fspec. +Compare [rX] with V. OPCODE = 63, MOD = fspec. @item CMPi -Compare rIi with V. OPCODE = 56 + i, MOD = fspec. +Compare [rIi] with V. OPCODE = 56 + i, MOD = fspec. @end ftable -@node Jump operators, Miscellaneous operators, Comparison operators, MIX instruction set +As explained above, these instructions modify the value of the MIX +comparison indicator; but maybe you are asking yourself how do you use +this value: enter jump operators, in the next subsection. + +@node Jump operators, Input-output operators, Comparison operators, MIX instruction set @comment node-name, next, previous, up @subsubsection Jump operators @cindex jump operators -The following instructions provoke jumps by setting the program -counter (address of the next instruction to fetch) to M (if a condition -is met). If a jump occurs, the value of the next instruction address -that would have been fetched in the absence of the jump is stored in rJ -(except for @code{JSJ}). +The MIX computer has an internal register, called the @dfn{location +counter}, which stores the address of the next instruction to be fetched +and executed by the virtual CPU. You cannot directly modify the contents +of this internal register with a load instruction: after fetching the +current instruction from memory, it is automatically increased in one +unit by the MIX. However, the is a set of instructions (which we call +jump instructions) which can alter the contents of the location counter +provided some condition is met. When this occurs, the value of the next +instruction address that would have been fetched in the absence of the +jump is stored in @samp{rJ} (except for @code{JSJ}), and the location +counter is set to the value of @samp{M} (so that the next instruction is +fetched from this new address). Later on, you can return to the point +when the jump occurred reading the address stored in @samp{rJ}. + +The MIX computer provides the following jump instructions: +With these instructions you force a jump to the specified address. Use +@samp{JSJ} if you do not care about the return address. @ftable @code @item JMP Unconditional jump. OPCODE = 39, MOD = 0. @item JSJ Unconditional jump, but rJ is not modified. OPCODE = 39, MOD = 1. +@end ftable + +These instructions check the overflow toggle to decide whether to jump +or not. + +@ftable @code @item JOV Jump if OV is set (and turn it off). OPCODE = 39, MOD = 2. @item JNOV Jump if OV is not set (and turn it off). OPCODE = 39, MOD = 3. +@end ftable + +In the following instructions, the jump is conditioned to the contents of the +comparison flag: + +@ftable @code @item JL +Jump if @w{@code{[CM] = L}}. OPCODE = 39, MOD = 4. @itemx JE +Jump if @w{@code{[CM] = E}}. OPCODE = 39, MOD = 5. @itemx JG +Jump if @w{@code{[CM] = G}}. OPCODE = 39, MOD = 6. @itemx JGE +Jump if @code{[CM]} does not equal @code{L}. OPCODE = 39, MOD = 7. @itemx JNE +Jump if @code{[CM]} does not equal @code{E}. OPCODE = 39, MOD = 8. @itemx JLE -Jump according to the value of CM. OPCODE = 39, MOD = 4, 5, 6, 7, 8, 9. +Jump if @code{[CM]} does not equal @code{G}. OPCODE = 39, MOD = 9. +@end ftable + +You can also jump conditioned to the value stored in the MIX registers, +using the following instructions: + +@ftable @code @item JAN @itemx JAZ @itemx JAP @@ -571,36 +831,15 @@ non-negative, non-zero or non-positive. OPCODE = 40 + i, MOD = 0, 1, 2, 3, 4, 5. @end ftable -@node Miscellaneous operators, Input-output operators, Jump operators, MIX instruction set -@comment node-name, next, previous, up -@subsubsection Miscellaneous operators -@cindex miscellaneous operators -@ftable @code -@item SLA -@itemx SRA -@itemx SLAX -@itemx SRAX -@itemx SLC -@itemx SRC -Shift rA or rAX left, right, or rAX circularly left or right. M -specifies the number of bytes to be shifted. -OPCODE = 6, MOD = 0, 1, 2, 3, 4, 5. -@item MOVE -Move MOD words from M to the location stored in rI1. -OPCODE = 7, MOD = no. of bytes. -@item NOP -No operation. OPCODE = 0, MOD = 0. -@item HLT -Halt. Stops instruction fetching. OPCODE = 5, MOD = 2. -@end ftable - -@node Input-output operators, Conversion operators, Miscellaneous operators, MIX instruction set +@node Input-output operators, Conversion operators, Jump operators, MIX instruction set @comment node-name, next, previous, up @subsubsection Input-output operators @cindex input-output operators -The following instructions perform input-output operations. +As explained in previous sections (@pxref{MIX architecture}), the MIX +computer can interact with a series of block devices. To that end, you +have at your disposal the following instructions: @ftable @code @item IN @@ -621,8 +860,20 @@ OPCODE = 38, MOD = I/O unit. Jump to M if the specified unit is busy. OPCODE = 34, MOD = I/O unit. @end ftable - -@node Conversion operators, , Input-output operators, MIX instruction set +@noindent +In all the above instructions, the @samp{MOD} subfile must be in the +range 0-20, since it denotes the operation's target device. The +@samp{IOC} instruction only makes sense for tape devices (@samp{MOD} = +0-7 or 20): it shifts the read/write pointer by the number of words +given by @samp{M} (if it equals zero, the tape is rewound)@footnote{In +Knuth's original definition, there are other control operations +available, but they do not make sense when implementing the block +devices as disk files (as we do in @sc{mdk} simulator). For the same +reason, @sc{mdk} devices are always ready, since all input-output +operations are performed using synchronous system calls.}. + + +@node Conversion operators, Shift operators, Input-output operators, MIX instruction set @comment node-name, next, previous, up @subsubsection Conversion operators @cindex conversion operators @@ -640,42 +891,135 @@ Convert the number stored in rA to a character representation and store it in rAX. OPCODE = 5, MOD = 1. @end ftable +@noindent +Digits are represented in MIX by the range of values 30-39 (digits +9-0). Thus, if the contents of @samp{rA} and @samp{rX} is, for instance, + +@example +[rA] = + 30 30 31 32 33 +[rX] = + 31 35 39 30 34 +@end example +@noindent +the represented number is 0012315904, and @samp{NUM} will store this +value in @samp{rA} (i.e., we end up with @samp{[rA]} = @w{+ 0 46 62 52 +0} = 12315904. @samp{CHAR} performs the inverse operation. + +@node Shift operators, Miscellaneous operators, Conversion operators, MIX instruction set +@comment node-name, next, previous, up +@subsubsection Shift operators +@cindex shift +@cindex shift operators + +The following instructions perform byte-wise shifts of the contents of +@samp{rA} and @samp{rX}. + +@ftable @code +@item SLA +@itemx SRA +@itemx SLAX +@itemx SRAX +@itemx SLC +@itemx SRC +Shift rA or rAX left, right, or rAX circularly left or right. M +specifies the number of bytes to be shifted. +OPCODE = 6, MOD = 0, 1, 2, 3, 4, 5. +@end ftable +@noindent +If we begin with, say, @samp{[rA]} = @w{- 01 02 03 04 05}, we would +have the following modifications to @samp{rA} contents when performing +the instructions on the left column: + +@multitable {SLA 00} {[rA] = - 00 00 00 00 00} +@item SLA 2 @tab [rA] = - 03 04 05 00 00 +@item SRA 1 @tab [rA] = - 00 01 02 03 04 +@item SLC 3 @tab [rA] = - 04 05 01 02 03 +@item SRC 24 @tab [rA] = - 05 01 02 03 04 +@end multitable +@noindent +Note that the sign is unaffected by shift operations. On the other hand, +@samp{SLAX} and @samp{SRAX} treat @samp{rA} and @samp{rX} as a single +10-bytes register (ignoring again the signs), so that, if we begin with +@samp{[rA]} = @w{+ 01 02 03 04 05} and @samp{[rX]} = @w{- 06 07 08 09 +10}, executing @samp{SLAX 3} would yield: + +@example +[rA] = + 04 05 06 07 08 [rX] = - 09 10 00 00 00 +@end example + +@node Miscellaneous operators, , Shift operators, MIX instruction set +@comment node-name, next, previous, up +@subsubsection Miscellaneous operators +@cindex miscellaneous operators + +Finally, we list in the following table three miscellaneous MIX +instructions which do not fit in any of the previous subsections: + +@ftable @code +@item MOVE +Move MOD words from M to the location stored in rI1. +OPCODE = 7, MOD = no. of bytes. +@item NOP +No operation. OPCODE = 0, MOD = 0. +@item HLT +Halt. Stops instruction fetching. OPCODE = 5, MOD = 2. +@end ftable +@noindent +The only effect of executing @samp{NOP} is increasing the location +counter, while @samp{HLT} usually marks program termination. -@node MIXAL, , The MIX computer, MIX and MIXAL overview +@node MIXAL, , The MIX computer, MIX and MIXAL tutorial @comment node-name, next, previous, up @section MIXAL @cindex MIXAL @cindex MIX assembly language @cindex assembly -The MIX computer can be programmed using an assembly language, MIXAL, -which provides a symbolic way of writing the binary instructions -understood by the imaginary MIX computer. If you have used assembler -languages before, you will find MIXAL a very familiar language. MIXAL is -fully described in volume 1 of D. Knuth's TAOCP. This section is not -meant as a replacement of the book's description, but as a brief survey -of MIXAL. +In the previous sections we have listed all the available MIX binary +instructions. As we have shown, each instruction is represented by a +word which is fetched from memory and executed by the MIX virtual +CPU. As is the case with real computers, the MIX knows how to decode +instructions in binary format (the so--called machine language), but a +human programmer would have a tough time if she were to write her +programs in machine language. Fortunately, the MIX computer can be +programmed using an assembly language, MIXAL, which provides a symbolic +way of writing the binary instructions understood by the imaginary MIX +computer. If you have used assembler languages before, you will find +MIXAL a very familiar language. MIXAL source files are translated +to machine language by a MIX assembler, which produces a binary file (the +actual MIX program) which can be directly loaded into the MIX memory and +subsequently executed. + +In this section, we describe MIXAL, the MIX assembly language. The +implementation of the MIX assembler program and MIX computer simulator +provided by @sc{mdk} are described later on (@pxref{Getting started}). @menu -* Instructions:: -* Comments:: -* Expressions:: -* Local symbols:: -* Miscellaneous:: +* Basic structure:: Writing basic MIXAL programs. +* MIXAL directives:: Assembler directives. +* Expressions:: Evaluation of expressions. +* Local symbols:: Special symbol table entries. +* Literal constants:: Specifying an immediate operand. @end menu -@node Instructions, Comments, MIXAL, MIXAL +@node Basic structure, MIXAL directives, MIXAL, MIXAL @comment node-name, next, previous, up -@subsection Instructions -@cindex MIXAL instructions -@cindex instructions -@cindex instruction parts +@subsection Basic program structure + +The MIX assembler reads MIXAL files line by line, producing, when +required, a binary instruction, which is associated to a predefined +memory address. To keep track of the current address, the assembler +maintains an internal location counter which is incremented each time an +instruction is compiled. In addition to MIX instructions, you can +include in MIXAL file assembly directives (or pseudoinstructions) +addressed at the assembler itself (for instance, telling it where the +program starts and ends, or to reposition the location counter; see below). -MIX instructions are written in MIXAL according to the following -pattern: +MIX instructions and assembler directives@footnote{We shall call them, +collectively, MIXAL instructions.} are written in MIXAL (one per +source file line) according to the following pattern: @example -[LABEL] OPCODE [OPERAND] [COMMENT] +[LABEL] MNEMONIC [OPERAND] [COMMENT] @end example @noindent @@ -689,13 +1033,13 @@ Items between square brackets are optional, and @table @code @item LABEL -Is an alphanumeric identifier (a @dfn{symbol}) which gets the value of -the current compilation address, and can be used in subsequent +Is an alphanumeric identifier (a @dfn{symbol}) which gets the current +value of the location counter, and can be used in subsequent expressions. -@item OPCODE +@item MNEMONIC Is a literal denoting the operation code of the instruction -(e.g. @code{LDA}, @code{STA}) or an assembly pseudoinstruction -(e.g. @code{ORG}, @code{EQU}). +(e.g. @code{LDA}, @code{STA}; see @pxref{MIX instruction set}) or an +assembly pseudoinstruction (e.g. @code{ORG}, @code{EQU}). @item ADDRESS Expression evaluating to the address subfield of the instruction. @item INDEX @@ -720,6 +1064,19 @@ column number at which each of these instruction parts must start. The MIXAL assembler included in @sc{mdk}, @code{mixasm}, does not impose such restriction.}. +We have already listed the mnemonics associated will each MIX +instructions; sample MIXAL instructions representing MIX instructions +are: +@example +HERE LDA 2000 HERE represents the current location counter + LDX HERE,2(1:3) this is a comment + JMP 1234 +@end example + +@node MIXAL directives, Expressions, Basic structure, MIXAL +@comment node-name, next, previous, up +@subsection MIXAL directives + MIXAL instructions can be either one of the MIX machine instructions (@pxref{MIX instruction set}) or one of the following assembly pseudoinstructions: @@ -741,20 +1098,89 @@ Marks the end of the program. Its operand gives the start address for program execution. @end ftable -Sample MIXAL instructions are +All MIXAL programs must contain an @code{END} directive, with a twofold +end: first, it marks the end of the assembler job, and, in the second +place, its (mandatory) operand indicates the start address for the +compiled program (that is, the address at which the virtual MIX machine +must begin fetching instructions after loading the program). It is also +very common (although not mandatory) to include at least an @code{ORIG} +directive to mark the initial value of the assembler's location counter +(remember that it stores the address associated with each compiled MIX +instruction). Thus, a minimal MIXAL program would be @example -HERE LDA 2000 - LDX HERE,2(1:3) this is a comment - JMP 1234 -NEXT STA HERE*2(8) - ORG 4000 -VALUE EQU NEXT+HERE//2 + ORIG 2000 set the initial compilation adress + NOP this instruction will be loaded at adress 2000 + HLT and this one at address 2001 + END 2000 end of program; execution will start at address 2000 +this line is not parsed by the assembler @end example +@noindent +The assembler will generate two binary instructions (@code{NOP} (@w{+ 00 +00 00 00 00}) and @code{HLT} (+ 00 00 02 05)), which will be loaded at +addresses 2000 and 2001. Execution of the program will begin at address +2000. Every MIXAL program should also include a @code{HLT} instruction, +which will mark the end of program execution (but not of program +compilation). + +The @code{EQU} directive allows the definition of symbolic names for +specific values. For instance, we could rewrite the above program as +follows: + +@example +START EQU 2000 + ORIG START + NOP + HLT + END START +@end example +@noindent +which would give rise to the same compiled code. Symbolic constants (or +symbols, for short) can also be implicitly defined placing them in the +@code{LABEL} field of a MIXAL instruction: in this case, the assembler +assigns to the symbol the value of the location counter before compiling +the line. Hence, a third way of writing our trivial program is + +@example + ORIG 2000 +START NOP + HLT + END START +@end example + +The @code{CON} directive allows you to directly specify the contents of +the memory address pointed by the location counter. For instance, when +the assembler encounters the following code snippet + +@example + ORIG 1150 + CON -1823473 +@end example +@noindent +it will assign to the memory cell number 1150 the contents @w{- 00 06 61 +11 49} (which corresponds to the decimal value -1823473). + +Finally, the @code{ALF} directive let's you specify the memory contents +as a set of five (quoted) characters, which are translated by the +assembler to their byte values, conforming in that way the binary word +that is to be stored in the corresponding memory cell. This directive +comes in handy when you need to store printable messages in a memory +address, as in the following example: + +@example + OUT MSG MSG is not yet defined here (future reference) +MSG ALF "THIS " MSG gets defined here + ALF "IS A " + ALF "MESSA" + ALF "GE. " +@end example +@noindent +The above snippet also shows the use of a @dfn{future reference}, that +is the usage of a symbol (@code{MSG} in the example) prior of its actual +definition. The MIXAL assembler is able to handle future references +subject to some limitations which are described in the following section +(@pxref{Expressions}). -@node Comments, Expressions, Instructions, MIXAL -@comment node-name, next, previous, up -@subsection Comments @cindex comments Any line starting with an asterisk is treated as a comment and ignored @@ -766,14 +1192,14 @@ by the assembler. @end example As noted in the previous section, comments can also be located after the -@samp{OPERAND} field of an instruction, separated from it by white +@code{MNEMONIC} field of an instruction, separated from it by white space, as in @example LABEL LDA 100 This is also a comment @end example -@node Expressions, Local symbols, Comments, MIXAL +@node Expressions, Local symbols, MIXAL directives, MIXAL @comment node-name, next, previous, up @subsection Expressions @cindex operator @@ -795,7 +1221,28 @@ location; thus, for instance, evaluates to 4 plus two times the current memory location. White space is not allowed within expressions. -All symbols appearing within an expression must be defined. Future +The special binary operator @code{:} has the same meaning as in fspecs, +i.e., + +@example +A:B = 8*A + B +@end example +@noindent +while @code{A//B} stands for the quotient of the ten-byte number @w{@code{A} 00 +00 00 00 00} (that is, A right-padded with 5 null bytes or, what amounts +to the same, multiplied by 64 to the fifth power) divided by +@code{B}. Sample expressions are: + +@example +18-8*3 = 30 +14/3 = 4 +1+3:11 = 4:11 = 43 +1//64 = (01 00 00 00 00 00)/(00 00 00 01 00) = (01 00 00 00 00 00) +@end example +@noindent +Note that all MIXAL expressions evaluate to a MIX word (by definition). + +All symbols appearing within an expression must be previously defined. Future references are only allowed when appearing stand-alone (or modified by an unary operator) in the @code{ADDRESS} part of a MIXAL instruction, e.g. @@ -808,7 +1255,7 @@ e.g. S1 LD1 2000 @end example -@node Local symbols, Miscellaneous, Expressions, MIXAL +@node Local symbols, Literal constants, Expressions, MIXAL @comment node-name, next, previous, up @subsection Local symbols @cindex local symbols @@ -833,9 +1280,44 @@ usage: 3H JMP 1B @end example -@node Miscellaneous, , Local symbols, MIXAL +Note that a @code{B} local symbol never refers to a definition in its +own line, that is, in the following program: + +@example + ORIG 1999 +ST NOP +3H EQU 69 +3H ENTA 3B local symbol 3B refers to 3H in previous line + HLT + END ST +@end example +@noindent +the contents of @samp{rA} is set to 69 and @emph{not} to 2001. An +specially tricky case occurs when using local symbols in conjunction +with @code{ORIG} pseudoinstructions. To wit@footnote{The author wants to +thank Philip E. King for pointing these two special cases of local +symbol usage to him.}, + +@example + ORIG 1999 +ST NOP +3H CON 10 + ENT1 * + LDA 3B +** rI1 is 2001, rA is 10. So far so good! +3H ORIG 3B+1000 +** at this point 3H equals 2003 +** and the location counter equals 3000. + ENT2 * + LDX 3B +** rI2 contains 3000, rX contains 2003. + HLT + END ST +@end example + +@node Literal constants, , Local symbols, MIXAL @comment node-name, next, previous, up -@subsection Miscellaneous +@subsection Literal constants @cindex literal constants MIXAL allows the introduction of @dfn{literal constants}, which are @@ -863,14 +1345,14 @@ a CON 20-L @end example -@node Getting started, mixvm, MIX and MIXAL overview, Top +@node Getting started, mixvm, MIX and MIXAL tutorial, Top @comment node-name, next, previous, up @chapter Getting started In this chapter, you will find a sample code-compile-run-debug session using the @sc{mdk} utilities. Familiarity with the MIX mythical computer and its assembly language MIXAL (as described in Knuth's TAOCP) is -assumed; for a compact reminder, see @ref{MIX and MIXAL overview}. +assumed; for a compact reminder, see @ref{MIX and MIXAL tutorial}. @menu * Writing a source file:: A sample MIXAL source file. @@ -946,7 +1428,7 @@ blanks}. The workings of this sample program should be straightforward if you are familiar with MIXAL. See TAOCP vol. 1 for a thorought definition or -@ref{MIX and MIXAL overview}, for a quick tutorial. +@ref{MIX and MIXAL tutorial}, for a quick tutorial. @node Compiling, Running the program, Writing a source file, Getting started @comment node-name, next, previous, up |