Subversion Repositories eco32

% This file is part of the MMIXware package (c) Donald E Knuth 1999

@i boilerplate.w %<< legal stuff: PLEASE READ IT BEFORE MAKING ANY CHANGES!

\def\title{MMIX-SIM}

\def\MMIX{\.{MMIX}}

\def\NNIX{\hbox{\mc NNIX}}

\def\Hex#1{\hbox{$^{\scriptscriptstyle\#}$\tt#1}} % experimental hex constant

\def\<#1>{\hbox{$\langle\,$#1$\,\rangle$}}\let\is=\longrightarrow

\def\dts{\mathinner{\ldotp\ldotp}}

\def\bull{\smallskip\textindent{$\bullet$}}

@s xor normal @q unreserve a C++ keyword @>

@s bool normal @q unreserve a C++ keyword @>

@*Introduction. This program simulates a simplified version of the \MMIX\

computer. Its main goal is to help people create and test \MMIX\ programs for

{\sl The Art of Computer Programming\/} and related publications. It provides

only a rudimentary terminal-oriented interface, but it has enough

infrastructure to support a cool graphical user interface --- which could be

added by a motivated reader. (Hint, hint.)

\MMIX\ is simplified in the following ways:

\bull

There is no pipeline, and there are no

caches. Thus, commands like \.{SYNC} and \.{SYNCD} and \.{PREGO} do nothing.

\bull

Simulation applies only to user programs, not to an operating system kernel.

Thus, all addresses must be nonnegative; ``privileged'' commands such as

\.{PUT}~\.{rK,z} or \.{RESUME}~\.1 or \.{LDVTS}~\.{x,y,z} are not allowed;

instructions should be executed only from addresses in segment~0

(addresses less than \Hex{2000000000000000}).

Certain special registers remain constant: $\rm rF=0$,

$\rm rK=\Hex{ffffffffffffffff}$,

$\rm rQ=0$;

$\rm rT=\Hex{8000000500000000}$,

$\rm rTT=\Hex{8000000600000000}$,

$\rm rV=\Hex{369c200400000000}$.

\bull

No trap interrupts are implemented, except for a few special cases of \.{TRAP}

that provide rudimentary input-output.

@^interrupts@>

\bull

All instructions take a fixed amount of time, given by the rough estimates

stated in the \MMIX\ documentation. For example, \.{MUL} takes $10\upsilon$,

\.{LDB} takes $\mu+\upsilon\mkern1mu$; all times are expressed in terms of

$\mu$ and~$\upsilon$, ``mems'' and ``oops.'' The clock register~rC increases by

@^mems@>

@^oops@>

$2^{32}$ for each~$\mu$ and 1~for each~$\upsilon$. But the interval

counter~rI decreases by~1 for each instruction, and the usage

counter~rU increases by~1 for each instruction.

@^rC@>

@^rI@>

@^rU@>

@ To run this simulator, assuming \UNIX/ conventions, you say

`\.{mmix} \ \.{progfile} \.{args...}',

where \.{progfile} is an output of the \.{MMIXAL} assembler,

\.{args...} is a sequence of optional command-line arguments passed

to the simulated program, and \ is any subset of the following:

@^command line arguments@>

\bull \.{-t}\quad Trace each instruction the first $n$ times it

is executed. (The notation \.{} in this option, and in several

other options and interactive commands below, stands for a decimal integer.)

\bull \.{-e}\quad Trace each instruction that raises an arithmetic

exception belonging to the given bit pattern. (The notation \.{} in this

option, and in several other commands below, stands for a hexadecimal integer.)

The exception bits are DVWIOUZX as they appear in rA, namely

\Hex{80} for~D (integer divide check), \Hex{40} for~V (integer overflow),

\dots, \Hex{01} for~X (floating inexact). The option \.{-e} by itself

is equivalent to \.{-eff}, tracing all eight exceptions.

\bull \.{-r}\quad Trace details of the register stack. This option

shows all the ``hidden'' loads and stores that occur when octabytes are

written from the ring of local registers into memory, or read from memory into

that ring. It also shows the full details of \.{SAVE} and \.{UNSAVE}

operations.

\bull \.{-l}\quad List the source line corresponding to each traced

instruction, filling gaps of length $n$ or less.

For example, if one instruction came from line 10 of the source file

and the next instruction to be traced came from line 12, line 11 would

be shown also, provided that $n\ge1$. If \.{} is omitted it is

assumed to be~3.

\bull \.{-s}\quad Show statistics of running time with each traced instruction.

\bull \.{-P}\quad Show the program profile (that is, the frequency counts

of each instruction that was executed) when the simulation ends.

\bull \.{-L}\quad List the source lines corresponding to each instruction

that appears in the program profile, filling gaps of length $n$ or less.

This option implies \.{-P}.  If \.{} is omitted it is assumed to be~3.

\bull \.{-v}\quad Be verbose: \kern-2.5ptTurn on all options.

(More precisely, the \.{-v} option is

shorthand for \.{-t9999999999}~\.{-e} \.{-r} \.{-s} \.{-l10}~\.{-L10}.)

\bull \.{-q}\quad Be quiet: Cancel all previously specified options.

\bull \.{-i}\quad Go into interactive mode before starting the simulation.

\bull \.{-I}\quad Go into interactive mode when the simulated program

halts or pauses for a breakpoint.

\bull \.{-b}\quad Set the buffer size of source lines to $\max(72,n)$.

\bull \.{-c}\quad Set the capacity of the local register ring

to $\max(256,n)$; this number must be a power of~2.

\bull \.{-f}\quad Use the named file for standard input to the

simulated program. This option should be used whenever the simulator

is not being used interactively, because the simulator will not recognize

end of file when standard input has been defined in any other way.

\bull \.{-D}\quad Prepare the named file for use by other

simulators, instead of actually doing a simulation.

\bull \.{-?}\quad Print the ``\.{Usage}'' message, which summarizes

the command-line options.

\smallskip\noindent

The author recommends \.{-t2} \.{-l} \.{-L} for initial offline debugging.

While the program is being simulated, an {\it interrupt\/}

signal (usually control-C) will cause the simulator to

@^interrupts@>

break and go into interactive mode after tracing the current instruction,

even if \.{-i} and \.{-I} were not specified on the command line.

@ In interactive mode, the user is prompted `\.{mmix>}' and a variety of

@.mmix>@>

commands can be typed online. Any command-line option can be given

in response to such a prompt (including the `\.-' that begins the option),

and the following operations are also available:

\bull Simply typing \ or \.n\ to the \.{mmix>} prompt causes

one \MMIX\ instruction to be executed and traced; then the user is prompted

again.

\bull \.c continues simulation until the program halts or reaches

a breakpoint. (Actually the command is `\.c\', but we won't

bother to mention the \ in the following description.)

\bull \.q quits (terminates the simulation), after printing the

profile (if it was requested) and the final statistics.

\bull \.s prints out the current statistics (the clock times and the

current instruction location). We have already discussed the \.{-s} option

on the command line, which

causes these statistics to be printed automatically;

but a lot of statistics can fill up a lot of file space, so users may

prefer to see the statistics only on demand.

\bull \.{l}, \.{g}, \.{\$}, \.{rA}, \.{rB}, \dots,

\.{rZZ}, and \.{M} will show the current value of a local register,

global register, dynamically numbered register, special register, or memory

location. Here \.{} specifies the type of value to be displayed;

if \.{} is `\.!', the value will be given in decimal notation;

if \.{} is `\..' it will be given in floating point notation;

if \.{} is `\.\#' it will be given in hexadecimal, and

if \.{} is `\."'  it will be given as a string of eight one-byte

characters. Just typing \.{} by itself will repeat the most recently shown

value, perhaps in another format; for example, the command `\.{l10\#}'

will show local register 10 in hexadecimal notation, then the command

`\.!' will show it in decimal and `\..' will show it as a floating point

number. If \.{} is empty, the previous type will be repeated;

the default type is decimal. Register \.{rA} is equivalent to \.{g22},

according to the numbering used in \.{GET} and \.{PUT} commands.

The `\.{}' in any of these commands can also have the form

`\.{=}', where the value is a decimal or floating point or

hexadecimal or string constant. (The syntax rules for floating point constants

appear in {\mc MMIX-ARITH}. A string constant is treated as in the

\.{BYTE} command of \.{MMIXAL}, but padded at the left with zeros if

fewer than eight characters are specified.) This assigns a new value

before displaying it. For example, `\.{l10=.1e3}'

sets local register 10 equal to 100; `\.{g250="ABCD",\#a}' sets global

register 250 equal to \Hex{000000414243440a}; `\.{M1000=-Inf}' sets

M$[\Hex{1000}]_8=\Hex{fff0000000000000}$, the representation of $-\infty$.

Special registers other than~rI cannot be set to values disallowed by~\.{PUT}.

Marginal registers cannot be set to nonzero values.

The command `\.{rI=250}' sets the interval counter to 250; this will

cause a break in simulation after 250 instructions have been executed.

\bull \.{+} shows the next $n$ octabytes following the one

most recently shown, in format \.{}. For example, after `\.{l10\#}'

a subsequent `\.{+30}' will show \.{l11}, \.{l12}, \dots, \.{l40} in

hexadecimal notation. After `\.{g200=3}' a subsequent `\.{+30}' will

set \.{g201}, \.{g202}, \dots, \.{g230} equal to~3, but a subsequent

`\.{+30!}' would merely display \.{g201} through~\.{g230} in decimal

notation. Memory addresses will advance by~8 instead of by~1. If \.{}

is empty, the default value $n=1$ is used.

\bull \.{@@} sets the address of the next tetrabyte to be

simulated, sort of like a \.{GO} command.

\bull \.{t} says that the instruction in tetrabyte location $x$ should

always be traced, regardless of its frequency count.

\bull \.{u} undoes the effect of \.{t}.

\bull \.{b[rwx]} sets breakpoints at tetrabyte $x$; here \.{[rwx]}

stands for any subset of the letters \.r, \.w, and/or~\.x, meaning to

break when the tetrabyte is read, written, and/or executed. For example,

`\.{bx1000}' causes a break in the simulation just after the tetrabyte

in \Hex{1000} is executed; `\.{b1000}' undoes this breakpoint;

`\.{brwx1000}' causes a break just after any simulated instruction loads,

stores, or appears in tetrabyte number \Hex{1000}.

\bull \.{T}, \.{D}, \.{P}, \.{S} sets the ``current segment'' to

\.{Text\_Segment}, \.{Data\_Segment}, \.{Pool\_Segment}, or

\.{Stack\_Segment}, respectively, namely to \Hex{0}, \Hex{2000000000000000},

\Hex{4000000000000000}, or \Hex{6000000000000000}. The current segment,

initially \Hex{0}, is added to all

memory addresses in \.{M}, \.{@@}, \.{t}, \.{u}, and \.{b} commands.

@:Text_Segment}\.{Text\_Segment@>

@:Data_Segment}\.{Data\_Segment@>

@:Pool_Segment}\.{Pool\_Segment@>

@:Stack_Segment}\.{Stack\_Segment@>

\bull \.{B} lists all current breakpoints and tracepoints.

\bull \.{i} reads a sequence of interactive commands from the

specified file, one command per line, ignoring blank lines. This feature

can be used to set many breakpoints or to display a number of key

registers, etc. Included lines that begin with \.\% or \.i are ignored;

therefore an included file cannot include {\it another\/} file.

Included lines that begin with a blank space are reproduced in the standard

output, otherwise ignored.

\bull \.h (help) reminds the user of the available interactive commands.

@* Rudimentary I/O.

Input and output are provided by the following ten primitive system calls:

@^I/O@>

@^input/output@>

\bull \.{Fopen}|(handle,name,mode)|. Here |handle| is a

one-byte integer, |name| is a string, and |mode| is one of the

values \.{TextRead}, \.{TextWrite}, \.{BinaryRead}, \.{BinaryWrite},

\.{BinaryReadWrite}. An \.{Fopen} call associates |handle| with the

external file called |name| and prepares to do input and/or output

on that file. It returns 0 if the file was opened successfully; otherwise

returns the value~$-1$. If |mode| is \.{TextWrite}, \.{BinaryWrite}, or

\.{BinaryReadWrite},

any previous contents of the named file are discarded. If |mode| is

\.{TextRead} or \.{TextWrite}, the file consists of ``lines'' terminated

by ``newline'' characters, and it is said to be a text file; otherwise

the file consists of uninterpreted bytes, and it is said to be a binary file.

@.Fopen@>

@.TextRead@>

@.TextWrite@>

@.BinaryRead@>

@.BinaryWrite@>

@.BinaryReadWrite@>

Text files and binary files are essentially equivalent in cases

where this simulator is hosted by an operating system derived from \UNIX/;

in such cases files can be written as text and read as binary or vice versa.

But with other operating systems, text files and binary files often have

quite different representations, and certain characters with byte

codes less than~|' '| are forbidden in text. Within any \MMIX\ program,

the newline character has byte code $\Hex{0a}=10$.

At the beginning of a program three handles have already been opened: The

``standard input'' file \.{StdIn} (handle~0) has mode \.{TextRead}, the

``standard output'' file \.{StdOut} (handle~1) has mode \.{TextWrite}, and the

``standard error'' file \.{StdErr} (handle~2) also has mode \.{TextWrite}.

@.StdIn@>

@.StdOut@>

@.StdErr@>

When this simulator is being run interactively, lines of standard input

should be typed following a prompt that says `\.{StdIn>\ }', unless the \.{-f}

option has been used.

The standard output and standard error files of the simulated program

are intermixed with the output of the simulator~itself.

The input/output operations supported by this simulator can perhaps be

understood most easily with reference to the standard library \.{stdio}

that comes with the \CEE/ language, because the conventions of~\CEE/

have been explained in hundreds of books. If we declare an array

|FILE *file[256]| and set |file[0]=stdin|, |file[1]=stdout|, and

|file[2]=stderr|, then the simulated system call \.{Fopen}|(handle,name,mode)|

is essentially equivalent to the \CEE/ expression

$$\displaylines{

\hskip5em\hbox{(|file[handle]|?

     |(file[handle]=freopen(name,mode_string[mode],file[handle]))|:}\hfill\cr

\hfill\hbox{|(file[handle]=fopen(name,mode_string[mode]))|)? 0: $-1$},%

      \hskip5em\cr}$$

if we set |mode_string|[\.{TextRead}]~=~|"r"|,

|mode_string|[\.{TextWrite}]~=~|"w"|,

|mode_string|[\.{BinaryRead}]~=~|"rb"|,

|mode_string|[\.{BinaryWrite}]~=~|"wb"|, and

|mode_string|[\.{BinaryReadWrite}]~=~|"wb+"|.

\bull \.{Fclose}|(handle)|. If the given file handle has been opened, it is

closed---no longer associated with any file. Again the result is 0 if

successful, or $-1$ if the file was already closed or unclosable.

The \CEE/ equivalent is

$$\hbox{|fclose(file[handle])? -1: 0|}$$

with the additional side effect of setting |file[handle]=NULL|.

\bull \.{Fread}|(handle,buffer,size)|.

The file handle should have been opened with mode \.{TextRead},

\.{BinaryRead}, or \.{BinaryReadWrite}.

@.Fread@>

The next |size| characters are read into \MMIX's memory starting at address

|buffer|. If an error occurs, the value |-1-size| is returned;

otherwise, if the end of file does not intervene, 0~is returned;

otherwise the negative value |n-size| is returned, where |n|~is the number of

characters successfully read and stored. The statement

$$\hbox{|fread(buffer,1,size,file[handle])-size|}$$

has the equivalent effect in \CEE/, in the absence of file errors.

\bull \.{Fgets}|(handle,buffer,size)|.

The file handle should have been opened with mode \.{TextRead},

\.{BinaryRead}, or \.{BinaryReadWrite}.

@.Fgets@>

Characters are read into \MMIX's memory starting at address |buffer|, until

either |size-1| characters have been read and stored or a newline character has

been read and stored; the next byte in memory is then set to zero.

If an error or end of file occurs before reading is complete, the memory

contents are undefined and the value $-1$ is returned; otherwise

the number of characters successfully read and stored is returned.

The equivalent in \CEE/ is

$$\hbox{|fgets(buffer,size,file[handle])? strlen(buffer): -1|}$$

if we assume that no null characters were read in; null characters may,

however, precede a newline, and they are counted just like other characters.

\bull \.{Fgetws}|(handle,buffer,size)|.

@.Fgetws@>

This command is the same as \.{Fgets}, except that it applies to wyde

characters instead of one-byte characters. Up to |size-1| wyde

characters are read; a wyde newline is $\Hex{000a}$. The \CEE/~version,

using conventions of the ISO multibyte string extension (MSE), is

@^MSE@>

approximately

$$\hbox{|fgetws(buffer,size,file[handle])? wcslen(buffer): -1|}$$

where |buffer| now has type |wchar_t*|.

\bull \.{Fwrite}|(handle,buffer,size)|.

The file handle should have been opened with one of the modes \.{TextWrite},

\.{BinaryWrite}, or \.{BinaryReadWrite}.

@.Fwrite@>

The next |size| characters are written from \MMIX's memory starting at address

|buffer|. If no error occurs, 0~is returned;

otherwise the negative value |n-size| is returned, where |n|~is the number of

characters successfully written. The statement

$$\hbox{|fwrite(buffer,1,size,file[handle])-size|}$$

together with |fflush(file[handle])| has the equivalent effect in \CEE/.

\bull \.{Fputs}|(handle,string)|.

The file handle should have been opened with mode \.{TextWrite},

\.{BinaryWrite}, or \.{BinaryReadWrite}.

@.Fputs@>

One-byte characters are written from \MMIX's memory to the file, starting

at address |string|, up to but not including the first byte equal to~zero.

The number of bytes written is returned, or $-1$ on error.

The \CEE/ version is

$$\hbox{|fputs(string,file[handle])>=0? strlen(string): -1|,}$$

together with |fflush(file[handle])|.

\bull \.{Fputws}|(handle,string)|.

The file handle should have been opened with mode \.{TextWrite},

\.{BinaryWrite}, or \.{BinaryReadWrite}.

@.Fputws@>

Wyde characters are written from \MMIX's memory to the file, starting

at address |string|, up to but not including the first wyde equal to~zero.

The number of wydes written is returned, or $-1$ on error.

The \CEE/+MSE version is

$$\hbox{|fputws(string,file[handle])>=0? wcslen(string): -1|}$$

together with |fflush(file[handle])|, where |string| now has type |wchar_t*|.

\bull \.{Fseek}|(handle,offset)|.

The file handle should have been opened with mode \.{BinaryRead},

\.{BinaryWrite}, or \.{BinaryReadWrite}.

@.Fseek@>

This operation causes the next input or output operation to begin at

|offset| bytes from the beginning of the file, if |offset>=0|, or at

|-offset-1| bytes before the end of the file, if |offset<0|. (For

example, |offset=0| ``rewinds'' the file to its very beginning;

|offset=-1| moves forward all the way to the end.) The result is 0

if successful, or $-1$ if the stated positioning could not be done.

The \CEE/ version is

$$\hbox{|fseek(file[handle],@,offset<0? offset+1: offset,@,

              offset<0? SEEK_END: SEEK_SET)|? $-1$: 0.}$$

If a file in mode \.{BinaryReadWrite} is used for both reading and writing,

an \.{Fseek} command must be given when switching from input to output

or from output to input.

\bull \.{Ftell}|(handle)|.

The file handle should have been opened with mode \.{BinaryRead},

\.{BinaryWrite}, or \.{BinaryReadWrite}.

@.Ftell@>

This operation returns the current file position, measured in bytes

from the beginning, or $-1$ if an error has occurred. In this case the

\CEE/ function

$$\hbox{|ftell(file[handle])|}$$

has exactly the same meaning.

\smallskip

Although these ten operations are quite primitive, they provide

the necessary functionality for extremely complex input/output behavior.

For example, every function in the \.{stdio} library of \CEE/,

with the exception of the two administrative operations \\{remove} and

\\{rename}, can be implemented as a subroutine in terms of the six basic

operations \.{Fopen}, \.{Fclose}, \.{Fread}, \.{Fwrite}, \.{Fseek}, and

\.{Ftell}.

Notice that the \MMIX\ function calls are much more consistent than

those in the \CEE/ library. The first argument is always a handle;

the second, if present, is always an address; the third, if present,

is always a size. {\it The result returned is always nonnegative if the

operation was successful, negative if an anomaly arose.} These common

features make the functions reasonably easy to remember.

@ The ten input/output operations of the previous section are invoked by

\.{TRAP} commands with $\rm X=0$, $\rm Y=\.{Fopen}$ or \.{Fclose} or \dots~or

\.{Ftell}, and $\rm Z=\.{Handle}$. If~there are two arguments, the

second argument is placed in \$255. If there are three arguments,

the address of the second is placed in~\$255; the second argument

is M$[\$255]_8$ and the third argument is M$[\$255+8]_8$. The returned

value will be in \$255 when the system call is finished. (See the

example below.)

@ The user program starts at symbolic location \.{Main}. At this time

@.Main@>

@:Pool_Segment}\.{Pool\_Segment@>

the global registers are initialized according to the \.{GREG}

statements in the \.{MMIXAL} program, and \$255 is set to the

numeric equivalent of~\.{Main}. Local register~\$0 is

initially set to the number of {\it command-line arguments\/}; and

@^command line arguments@>

local register~\$1 points to the first such argument, which

is always a pointer to the program name. Each command-line argument is a

pointer to a string; the last such pointer is M$[\$0\ll3+\$1]_8$, and

M$[\$0\ll3+\$1+8]_8$ is zero. (Register~\$1 will point to an octabyte in

\.{Pool\_Segment}, and the command-line strings will be in that segment

too.) Location M[\.{Pool\_Segment}] will be the address of the first

unused octabyte of the pool segment.

Registers rA, rB, rD, rE, rF, rH, rI, rJ, rM, rP, rQ, and rR

are initially zero, and $\rm rL=2$.

A subroutine library loaded with the user program might need to initialize

itself. If an instruction has been loaded into tetrabyte M$[\Hex{90}]_4$,

the simulator actually begins execution at \Hex{90} instead of at~\.{Main};

in this case \$255 holds the location of~\.{Main}.

@^subroutine library initialization@>

@^initialization of a user program@>

(The routine at \Hex{90} can pass control to \.{Main} without increasing~rL,

if it starts with the slightly tricky sequence

$$\.{PUT rW, \$255;{ } PUT rB, \$255;{ } SETML \$255,\#F700;{ } % PUTI rB,0!

      PUT rX,\$255}$$

and eventually says \.{RESUME}; this \.{RESUME} command will restore

\$255 and~rB. But the user program should {\it not\/} really count on

the fact that rL is initially~2.)

@ The main program ends when \MMIX\ executes the system

call \.{TRAP}~\.{0}, which is often symbolically written

`\.{TRAP}~\.{0,Halt,0}' to make its intention clear. The contents

of \$255 at that time are considered to be the value ``returned''

by the main program, as in the |exit| statement of~\CEE/; a nonzero

value indicates an anomalous exit. All open files are closed

@.Halt@>

when the program ends.

@ Here, for example, is a complete program that copies a text file

to the standard output, given the name of the file to be copied.

It includes all necessary error checking.

\vskip-14pt

$$\baselineskip=10pt

\obeyspaces\halign{\qquad\.{#}\hfil\cr

* SAMPLE PROGRAM: COPY A GIVEN FILE TO STANDARD OUTPUT\cr

\noalign{\smallskip}

t        IS   \$255\cr

argc     IS   \$0\cr

argv     IS   \$1\cr

s        IS   \$2\cr

Buf\_Size IS   1000\cr

{}         LOC  Data\_Segment\cr

Buffer   LOC  @@+Buf\_Size\cr

{}         GREG @@\cr

Arg0     OCTA 0,TextRead\cr

Arg1     OCTA Buffer,Buf\_Size\cr

\noalign{\smallskip}

{}         LOC  \#200              main(argc,argv) \{\cr

Main     CMP  t,argc,2          if (argc==2) goto openit\cr

{}         PBZ  t,OpenIt\cr

{}         GETA t,1F              fputs("Usage: ",stderr)\cr

{}         TRAP 0,Fputs,StdErr\cr

{}         LDOU t,argv,0          fputs(argv[0],stderr)\cr

{}         TRAP 0,Fputs,StdErr\cr

{}         GETA t,2F              fputs(" filename\\n",stderr)\cr

Quit     TRAP 0,Fputs,StdErr    \cr

{}         NEG  t,0,1             quit: exit(-1)\cr

{}         TRAP 0,Halt,0\cr

1H       BYTE "Usage: ",0\cr

{}         LOC  (@@+3)\&-4          align to tetrabyte\cr

2H       BYTE " filename",\#a,0\cr

\noalign{\smallskip}

OpenIt   LDOU s,argv,8          openit: s=argv[1]\cr

{}         STOU s,Arg0\cr

{}         LDA  t,Arg0            fopen(argv[1],"r",file[3])\cr

{}         TRAP 0,Fopen,3\cr

{}         PBNN t,CopyIt          if (no error) goto copyit\cr

{}         GETA t,1F              fputs("Can't open file ",stderr)\cr

{}         TRAP 0,Fputs,StdErr\cr

{}         SET  t,s               fputs(argv[1],stderr)\cr

{}         TRAP 0,Fputs,StdErr\cr

{}         GETA t,2F              fputs("!\\n",stderr)\cr

{}         JMP  Quit              goto quit\cr

1H       BYTE "Can't open file ",0\cr

{}         LOC  (@@+3)\&-4          align to tetrabyte\cr

2H       BYTE "!",\#a,0\cr

\noalign{\smallskip}

CopyIt   LDA  t,Arg1            copyit:\cr

{}         TRAP 0,Fread,3         items=fread(buffer,1,buf\_size,file[3])\cr

{}         BN   t,EndIt           if (items < buf\_size) goto endit\cr

{}         LDA  t,Arg1            items=fwrite(buffer,1,buf\_size,stdout)\cr

{}         TRAP 0,Fwrite,StdOut\cr

{}         PBNN t,CopyIt          if (items >= buf\_size) goto copyit\cr

Trouble  GETA t,1F              trouble: fputs("Trouble w...!",stderr)\cr

{}         JMP  Quit              goto quit\cr

1H       BYTE "Trouble writing StdOut!",\#a,0\cr

\noalign{\smallskip}

EndIt    INCL t,Buf\_Size\cr

{}         BN   t,ReadErr         if (ferror(file[3])) goto readerr\cr

{}         STO  t,Arg1+8\cr

{}         LDA  t,Arg1            n=fwrite(buffer,1,items,stdout)\cr

{}         TRAP 0,Fwrite,StdOut\cr

{}         BN   t,Trouble         if (n < items) goto trouble\cr

{}         TRAP 0,Halt,0          exit(0)\cr

ReadErr  GETA t,1F              readerr: fputs("Trouble r...!",stderr)\cr

{}         JMP  Quit              goto quit \}\cr

1H       BYTE "Trouble reading!",\#a,0\cr

}$$

@* Basics. To get started, we define a type that provides semantic sugar.

@=

typedef enum {@!false,@!true}@+@!bool;

@ This program for the 64-bit \MMIX\ architecture is based on 32-bit integer

arithmetic, because nearly every computer available to the author at the time

of writing (1999) was limited in that way. It uses subroutines

from the {\mc MMIX-ARITH} module, assuming only that type \&{tetra}

represents unsigned 32-bit integers. The definition of \&{tetra}

given here should be changed, if necessary, to agree with the

definition in that module.

@^system dependencies@>

@=

typedef unsigned int tetra;

  /* for systems conforming to the LP-64 data model */

typedef struct {tetra h,l;} octa; /* two tetrabytes make one octabyte */

typedef unsigned char byte; /* a monobyte */

@ We declare subroutines twice, once with a prototype and once

with the old-style~\CEE/ conventions. The following hack makes

this work with new compilers as well as the old standbys.

@=

#ifdef __STDC__

#define ARGS(list) list

#else

#define ARGS(list) ()

#endif

@ @=

void print_hex @,@,@[ARGS((octa))@];@+@t}\6{@>

void print_hex(o)

  octa o;

{

  if (o.h) printf("%x%08x",o.h,o.l);

  else printf("%x",o.l);

}

@ Most of the subroutines in {\mc MMIX-ARITH} return an octabyte as

a function of two octabytes; for example, |oplus(y,z)| returns the

sum of octabytes |y| and~|z|. Division inputs the high

half of a dividend in the global variable~|aux| and returns

the remainder in~|aux|.

@=

extern octa zero_octa; /* |zero_octa.h=zero_octa.l=0| */

extern octa neg_one; /* |neg_one.h=neg_one.l=-1| */

extern octa aux,val; /* auxiliary data */

extern bool overflow; /* flag set by signed multiplication and division */

extern int exceptions; /* bits set by floating point operations */

extern int cur_round; /* the current rounding mode */

extern char *next_char; /* where a scanned constant ended */

extern octa oplus @,@,@[ARGS((octa y,octa z))@];

  /* unsigned $y+z$ */

extern octa ominus @,@,@[ARGS((octa y,octa z))@];

  /* unsigned $y-z$ */

extern octa incr @,@,@[ARGS((octa y,int delta))@];

  /* unsigned $y+\delta$ ($\delta$ is signed) */

extern octa oand @,@,@[ARGS((octa y,octa z))@];

  /* $y\land z$ */

extern octa shift_left @,@,@[ARGS((octa y,int s))@];

  /* $y\LL s$, $0\le s\le64$ */

extern octa shift_right @,@,@[ARGS((octa y,int s,int uns))@];

  /* $y\GG s$, signed if |!uns| */

extern octa omult @,@,@[ARGS((octa y,octa z))@];

  /* unsigned $(|aux|,x)=y\times z$ */

extern octa signed_omult @,@,@[ARGS((octa y,octa z))@];

  /* signed $x=y\times z$ */

extern octa odiv @,@,@[ARGS((octa x,octa y,octa z))@];

  /* unsigned $(x,y)/z$; $|aux|=(x,y)\bmod z$ */

extern octa signed_odiv @,@,@[ARGS((octa y,octa z))@];

  /* signed $x=y/z$ */

extern int count_bits @,@,@[ARGS((tetra z))@];

  /* $x=\nu(z)$ */

extern tetra byte_diff @,@,@[ARGS((tetra y,tetra z))@];

  /* half of \.{BDIF} */

extern tetra wyde_diff @,@,@[ARGS((tetra y,tetra z))@];

  /* half of \.{WDIF} */

extern octa bool_mult @,@,@[ARGS((octa y,octa z,bool xor))@];

  /* \.{MOR} or \.{MXOR} */

extern octa load_sf @,@,@[ARGS((tetra z))@];

  /* load short float */

extern tetra store_sf @,@,@[ARGS((octa x))@];

  /* store short float */

extern octa fplus @,@,@[ARGS((octa y,octa z))@];

  /* floating point $x=y\oplus z$ */

extern octa fmult @,@,@[ARGS((octa y ,octa z))@];

  /* floating point $x=y\otimes z$ */

extern octa fdivide @,@,@[ARGS((octa y,octa z))@];

  /* floating point $x=y\oslash z$ */

extern octa froot @,@,@[ARGS((octa,int))@];

  /* floating point $x=\sqrt z$ */

extern octa fremstep @,@,@[ARGS((octa y,octa z,int delta))@];

  /* floating point $x\,{\rm rem}\,z=y\,{\rm rem}\,z$ */

extern octa fintegerize @,@,@[ARGS((octa z,int mode))@];

  /* floating point $x={\rm round}(z)$ */

extern int fcomp @,@,@[ARGS((octa y,octa z))@];

  /* $-1$, 0, 1, or 2 if $yz$, $y\parallel z$ */

extern int fepscomp @,@,@[ARGS((octa y,octa z,octa eps,int sim))@];

  /* $x=|sim|?\ [y\sim z\ (\epsilon)]:\ [y\approx z\ (\epsilon)]$ */

extern octa floatit @,@,@[ARGS((octa z,int mode,int unsgnd,int shrt))@];

  /* fix to float */

extern octa fixit @,@,@[ARGS((octa z,int mode))@];

  /* float to fix */

extern void print_float @,@,@[ARGS((octa z))@];

  /* print octabyte as floating decimal */

extern int scan_const @,@,@[ARGS((char* buf))@];

  /* |val| = floating or integer constant; returns the type */

@ Here's a quick check to see if arithmetic is in trouble.

@d panic(m) {@+fprintf(stderr,"Panic: %s!\n",m);@+exit(-2);@+}

@=

if (shift_left(neg_one,1).h!=0xffffffff)

  panic("Incorrect implementation of type tetra");

@.Incorrect implementation...@>

@ Binary-to-decimal conversion is used when we want to see an octabyte

as a signed integer. The identity $\lfloor(an+b)/10\rfloor=

\lfloor a/10\rfloor n+\lfloor((a\bmod 10)n+b)/10\rfloor$ is helpful here.

@d sign_bit ((unsigned)0x80000000)

@=

void print_int @,@,@[ARGS((octa))@];@+@t}\6{@>

void print_int(o)

  octa o;

{

  register tetra hi=o.h, lo=o.l, r, t;

  register int j;

  char dig[20];

  if (lo==0 && hi==0) printf("0");

  else {

    if (hi&sign_bit) {

      printf("-");

      if (lo==0) hi=-hi;

      else lo=-lo, hi=~hi;

    }

    for (j=0;hi;j++) { /* 64-bit division by 10 */

      r=((hi%10)<<16)+(lo>>16);

      hi=hi/10;

      t=((r%10)<<16)+(lo&0xffff);

      lo=((r/10)<<16)+(t/10);

      dig[j]=t%10;

    }

    for (;lo;j++) {

      dig[j]=lo%10;

      lo=lo/10;

    }

    for (j--;j>=0;j--) printf("%c",dig[j]+'0');

  }

}

@* Simulated memory. Chunks of simulated memory, 2048 bytes each,

are kept in a tree structure organized as a {\it treap},

following ideas of Vuillemin, Aragon, and Seidel

@^Vuillemin, Jean Etienne@>

@^Aragon, Cecilia Rodriguez@>

@^Seidel, Raimund@>

[{\sl Communications of the ACM\/ \bf23} (1980), 229--239;

{\sl IEEE Symp.\ on Foundations of Computer Science\/ \bf30} (1989), 540--546].

Each node of the treap has two keys: One, called |loc|, is the

base address of 512 simulated tetrabytes; it follows the conventions

of an ordinary binary search tree, with all locations in the left subtree

less than the |loc| of a node and all locations in the right subtree

greater than that~|loc|. The other, called |stamp|, can be thought of as the

time the node was inserted into the tree; all subnodes of a given node

have a larger~|stamp|. By assigning time stamps at random, we maintain

a tree structure that almost always is fairly well balanced.

Each simulated tetrabyte has an associated frequency count and

source file reference.

@=

typedef struct {

  tetra tet; /* the tetrabyte of simulated memory */

  tetra freq; /* the number of times it was obeyed as an instruction */

  unsigned char bkpt; /* breakpoint information for this tetrabyte */

  unsigned char file_no; /* source file number, if known */

  unsigned short line_no; /* source line number, if known */

} mem_tetra;

@#

typedef struct mem_node_struct {

  octa loc; /* location of the first of 512 simulated tetrabytes */

  tetra stamp; /* time stamp for treap balancing */

  struct mem_node_struct *left, *right; /* pointers to subtrees */

  mem_tetra dat[512]; /* the chunk of simulated tetrabytes */

} mem_node;

@ The |stamp| value is actually only pseudorandom, based on the

idea of Fibonacci hashing [see {\sl Sorting and Searching}, Section~6.4].

This is good enough for our purposes, and it guarantees that

no two stamps will be identical.

@=

mem_node* new_mem @,@,@[ARGS((void))@];@+@t}\6{@>

mem_node* new_mem()

{

  register mem_node *p;

  p=(mem_node*)calloc(1,sizeof(mem_node));

  if (!p) panic("Can't allocate any more memory");

@.Can't allocate...@>

  p->stamp=priority;

  priority+=0x9e3779b9; /* $\lfloor2^{32}(\phi-1)\rfloor$ */

  return p;

}

@ Initially we start with a chunk for the pool segment, since

the simulator will be putting command-line information there before

it runs the program.

@=

mem_root=new_mem();

mem_root->loc.h=0x40000000;

last_mem=mem_root;

@ @=

tetra priority=314159265; /* pseudorandom time stamp counter */

mem_node *mem_root; /* root of the treap */

mem_node *last_mem; /* the memory node most recently read or written */

@ The |mem_find| routine finds a given tetrabyte in the simulated

memory, inserting a new node into the treap if necessary.

@=

mem_tetra* mem_find @,@,@[ARGS((octa))@];@+@t}\6{@>

mem_tetra* mem_find(addr)

  octa addr;

{

  octa key;

  register int offset;

  register mem_node *p=last_mem;

  key.h=addr.h;

  key.l=addr.l&0xfffff800;

  offset=addr.l&0x7fc;

  if (p->loc.l!=key.l || p->loc.h!=key.h)

    @

        setting |last_mem| and |p| to its location@>;

  return &p->dat[offset>>2];

}

@ @=

{@+register mem_node **q;

  for (p=mem_root; p; ) {

    if (key.l==p->loc.l && key.h==p->loc.h) goto found;

    if ((key.lloc.l && key.h<=p->loc.h) || key.hloc.h) p=p->left;

    else p=p->right;

  }

  for (p=mem_root,q=&mem_root; p && p->stamp

    if ((key.lloc.l && key.h<=p->loc.h) || key.hloc.h) q=&p->left;

    else q=&p->right;

  }

  *q=new_mem();

  (*q)->loc=key;

  @;

  p=*q;

found: last_mem=p;

}

@ At this point we want to split the binary search tree |p| into two

parts based on the given |key|, forming the left and right subtrees

of the new node~|q|. The effect will be as if |key| had been inserted

before all of |p|'s nodes.

@=

{

  register mem_node **l=&(*q)->left,**r=&(*q)->right;

  while (p) {

    if ((key.lloc.l && key.h<=p->loc.h) || key.hloc.h)

      *r=p, r=&p->left, p=*r;

    else *l=p, l=&p->right, p=*l;

  }

  *l=*r=NULL;

}

@* Loading an object file. To get the user's program into memory,

we read in an \MMIX\ object, using modifications of the routines

in the utility program \.{MMOtype}. Complete details of \.{mmo}

format appear in the program for {\mc MMIXAL}; a reader

who hopes to understand this section ought to at least skim

that documentation.

Here we need to define only the basic constants used for interpretation.

@d mm 0x98 /* the escape code of \.{mmo} format */

@d lop_quote 0x0 /* the quotation lopcode */

@d lop_loc 0x1 /* the location lopcode */

@d lop_skip 0x2 /* the skip lopcode */

@d lop_fixo 0x3 /* the octabyte-fix lopcode */

@d lop_fixr 0x4 /* the relative-fix lopcode */

@d lop_fixrx 0x5 /* extended relative-fix lopcode */

@d lop_file 0x6 /* the file name lopcode */

@d lop_line 0x7 /* the file position lopcode */

@d lop_spec 0x8 /* the special hook lopcode */

@d lop_pre 0x9 /* the preamble lopcode */

@d lop_post 0xa /* the postamble lopcode */

@d lop_stab 0xb /* the symbol table lopcode */

@d lop_end 0xc /* the end-it-all lopcode */

@ We do not load the symbol table. (A more ambitious simulator could

implement \.{MMIXAL}-style expressions for interactive debugging,

but such enhancements are left to the interested reader.)

@=

mmo_file=fopen(mmo_file_name,"rb");

if (!mmo_file) {

  register char *alt_name=(char*)calloc(strlen(mmo_file_name)+5,sizeof(char));

  if (!alt_name) panic("Can't allocate file name buffer");

@.Can't allocate...@>

  sprintf(alt_name,"%s.mmo",mmo_file_name);

  mmo_file=fopen(alt_name,"rb");

  if (!mmo_file) {

    fprintf(stderr,"Can't open the object file %s or %s!\n",

@.Can't open...@>

               mmo_file_name,alt_name);

    exit(-3);

  }

  free(alt_name);

}

byte_count=0;

@ @=

FILE *mmo_file; /* the input file */

int postamble; /* have we encountered |lop_post|? */

int byte_count; /* index of the next-to-be-read byte */

byte buf[4]; /* the most recently read bytes */

int yzbytes; /* the two least significant bytes */

int delta; /* difference for relative fixup */

tetra tet; /* |buf| bytes packed big-endianwise */

@ The tetrabytes of an \.{mmo} file are stored in

friendly big-endian fashion, but this program is supposed to work also

on computers that are little-endian. Therefore we read four successive bytes

and pack them into a tetrabyte, instead of reading a single tetrabyte.

@d mmo_err {

     fprintf(stderr,"Bad object file! (Try running MMOtype.)\n");

@.Bad object file@>

     exit(-4);

   }

@=

void read_tet @,@,@[ARGS((void))@];@+@t}\6{@>

void read_tet()

{

  if (fread(buf,1,4,mmo_file)!=4) mmo_err;

  yzbytes=(buf[2]<<8)+buf[3];

  tet=(((buf[0]<<8)+buf[1])<<16)+yzbytes;

}

@ @=

byte read_byte @,@,@[ARGS((void))@];@+@t}\6{@>

byte read_byte()

{

  register byte b;

  if (!byte_count) read_tet();

  b=buf[byte_count];

  byte_count=(byte_count+1)&3;

  return b;

}

@ @=

read_tet(); /* read the first tetrabyte of input */

if (buf[0]!=mm || buf[1]!=lop_pre) mmo_err;

if (ybyte!=1) mmo_err;

if (zbyte==0) obj_time=0xffffffff;

else {

  j=zbyte-1;

  read_tet();@+ obj_time=tet; /* file creation time */

  for (;j>0;j--) read_tet();

}

@ @=

{

  read_tet();

 loop:@+if (buf[0]==mm) switch (buf[1]) {

   case lop_quote:@+if (yzbytes!=1) mmo_err;

    read_tet();@+break;

   @t\4@>@@;

   case lop_post: postamble=1;

     if (ybyte || zbyte<32) mmo_err;