0 DESCRIPTION OF AN EXPERIMENTAL MACHINE ARCHITECTURE FOR USE WITH BLOCK STRUCTURED LANGUAGES (Version of 2 March 1979) Andrew S. Tanenbaum Johan W. Stevenson Hans van Staveren Informatica Rapport IR Abstract EM‐1 is a machine architecture designed to be interpreted on micro‐ computers. It has an instruction set convenient for compilers, and also has a very compact object program format. Furthermore, the encoding has been done in such a way as to make interpretation with a cost penalty of roughly a factor of 5‐8 feasible. This document describes the machine architecture, its instructions and their meanings. 1 1. INTRODUCTION EM‐1 is an Experimental Machine architecture designed with the fol‐ lowing goals in mind: 1. A compact instruction set, to reduce the amount of memo‐ ry needed for program storage, and to reduce the time needed to transmit programs over communication lines, is desirable. 2. The architecture should ease the task of code generation for high level languages such as Pascal, Algol 68, BCPL, C etc. 3. It should be designed with microprogrammed implementa‐ tions in mind; in particular, the use of many short fields within instructions should be avoided, since their extraction by the microprogram is inefficient. The machine has two operating modes ‐ user and monitor. In user mode a small group of instructions are considered illegal, and cause traps if executed. In monitor mode all instructions are legal. The address space consists of a maximum of 65536 bytes, although fewer may be available at a given installation. The bytes are numbered from 0 to the maximum. Each group of two bytes is regarded as a machine word, that is, bytes 0 and 1 form a word, bytes 2 and 3 form a word, etc. Bytes 1 and 2 do not form a word. The word is addressed by the even byte, which is the low order (rightmost) byte. Most of the machine instructions that reference memory require the offset to be even. For example, LOL 6 means fetch the local variable 6 bytes from the base of the current stack frame. LOL 5 does not exist. As an optimization, the offset actually present in the machine instruc‐ tion at run time is usually in words, rather than in bytes. However, for simplicity, the offset specified in the symbolic assembly language generated by the compiler is always in bytes. The compiler writer need not be aware of the details of the machine encoding. However, since this is a machine reference manual, offsets are given in words unless otherwise specified, e.g. The conversion from bytes (in assembly lan‐ guage) to words (in machine language) is done by the assembler. The basic architecture is based on the concept of a stack. The stack is used for procedure return addresses, actual parameters, local variables, and arithmetic operations. The instruction set contains a number of reverse Polish type instructions that pop two operands from the top of the stack, perform some operation on them, and push the re‐ sult back on the stack. Most stack operands are one word long; a few are several words long; none are an odd number of bytes. There are no visible general registers used for arithmetic operands etc. This is in contrast to most third generation computers, which usu‐ ally have 8 or 16 general registers. The decision not to have a group of 2 general registers was fully intentional, and follows from W.L. van der Poel’s (1968) dictum that a machine should have 0, 1, or an infinite number of any feature. General registers have two primary uses: to hold intermediate results of complicated expressions, e.g. ((a*b + c*d)/e + f*g/h) * i and to hold local variables. Various studies have shown that the average expression has fewer than two operands, making the former use of registers of doubtful value. The present trend toward structured programs consisting of a large num‐ ber of small procedures greatly reduces the value of registers to hold local variables because the large number of procedure calls implies a large overhead in saving and restoring the registers at every call. Furthermore, reverse Polish code is much easier to generate than multi‐register machine code, especially if highly efficient code is de‐ sired. High performance can be achieved by keeping part of the stack in high speed storage (a cache or microprogram scratchpad memory) rather than in primary (core) memory. Although there are no general purpose registers, there are a small number of internal registers with specific functions as follows: PS ‐ PSW. 0 = User mode, 1‐15 = Monitor mode & priority 1‐15 PB ‐ Procedure Base. Points to the bottom of the code PC ‐ Program Counter. Byte number of next instruction EB ‐ External Base. Address of the zeroth external. PD ‐ Procedure Descriptors. Points to the base of the pro‐ cedure descriptors. LB ‐ Local Base. Points to zeroth local variable in the current procedure SP ‐ Stack Pointer. Points to the highest occupied word on the stack HP ‐ Heap Pointer. If HP > SP, access to words above SP but below HP is not permitted. SP >= HP is illegal. ML ‐ Memory Limit. Highest byte implemented on this ma‐ chine. Must be odd. ML is read only. Although virtual memory is not discussed further in this document, EM‐1 has been designed in such a way as to allow a segmented virtual memory to be added to the architecture later. The virtual memory envi‐ sioned consists of a collection of instruction space segments and a col‐ lection of data space segments each with a size of 65536 bytes. Up to 256 segments of each kind are possible. It is assumed that the stack organization, described in the next section, remains unchanged, i.e. that segment D0 (data segment 0) is the stack used for call and arith‐ metic. Other data segments are used only for arrays. Each instruction space segment holds one or more procedures. 3 The only place in the entire architecture that absolute memory ad‐ dresses are used to refer to instructions are in the procedure descrip‐ tors. All branches use relative jumps, and cannot switch segments (for protection reasons). To add instruction segments to the machine, the procedure descriptor will have to include the segment number of a called procedure, as well as its address within the segment. Since the "bytes of parameters" field in the descriptor can be easily limited to one byte, the other byte is available for the segment number. To add segmentation for data, the instructions that manipulate ma‐ chine addresses (LAL, LAE, LOI, STI, etc.) must be changed to manipulate two word addresses, with the bottom word (lower numerical address) con‐ taining the segment number and the upper one the offset. These changes are relatively minor, and do not impact the basic architecture much. The EM‐1 Pascal compiler in fact produces code for both the virtual and non‐virtual versions. Two other areas that are not yet fully worked out are: how to make the size of the monitor, i.e. how many segments is needs transparent to the user program. One idea was to have two "relocation" registers, ib, and db, that automatically are added to all segment numbers generated in user mode, so the user program thinks that it begins with I0 and D0. In monitor mode I0 = 0 and D0 = 0. The other issue is how page faults should be handled. Ideally the microprogram should handle them totally transparently to the monitor, but this is difficult to arrange. One should strive as much as possible for this. 4 2. ORGANIZATION OF THE STACK The base of the stack (starting at address EB) is used for global variables, i.e. variables declared in the outermost block of the pro‐ gram. Following the globals are certain constants, temporaries, tables, and other objects needed by the run time system. Above these come the procedure frames, one frame for each procedure entered but not yet exit‐ ed. A recursive procedure will have one frame for each currently active invocation. A procedure frame consists of 5 zones: 1. The administration area (stack links and return address) 2. The actual parameters 3. The local variables and compiler temporaries 4. The dynamic local generators 5. The operand stack. A sample memory is shown in fig. 1. The first step in the procedure calling sequence is to deposit the 3 word administration area onto the stack (done by the MRK instruction). This block of words contains: the static link (the LB value of the most recent invocation of the statically enclosing procedure), the dynamic link (the LB value of the calling procedure), and the return address of the calling procedure. The exact format and encoding scheme is explicit‐ ly undefined and may vary from implementation to implementation, e.g. it is up to the implementer to decide the order and encoding of the 3 words. The next zone consists of the actual parameters. These are pushed onto the stack by the calling procedure. The exact details are compiler dependent. If a procedure has no actual parameters, this zone will be empty. Note that LB points to the first actual parameter, and not to the first word of the administration zone. Next come the local variables and temporaries. This zone includes arrays whose size is known at compile time. For languages in which array sizes are not all known at compile time, or in which new local objects may be dynamically generated during program execution, the zone above the static local variables is used. Between statements, the stack pointer, SP, will usually point to the highest word of zone 3 or 4. When a "push" instruction is executed, SP will be incremented by 2 and the new word deposited at the address pointed to by SP. The size of the operand stack, the fifth zone, will vary dynamically during expression evaluation. Note that the operand stack must be empty in order for zone 4 to grow. 5 |‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐| | | 65534 | unimplemented memory | | | |‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐| | | <‐ ML | | | user heap | | | | | <‐ HP |‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐| |///////////////////////////////| |/////// inaccessible //////////| |///////////////////////////////| |‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐| | | <‐ SP | | | | <‐ LB | | | user stack and externals | | | | | | | <‐ PD | | |‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐| <‐ EB | | | | | | <‐ PC | user code | | | | | |‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐| <‐ PB | (guard word(s) for checking) | |‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐| | | | | | monitor stack and externals | | | | | |‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐| | | | | | monitor code | | | | | |‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐| | address of 4 word vector | 0 |‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐| Fig. 1. Memory layout showing typical register positions during execution of user code. 6 3. PROCEDURE CALL/RETURN MECHANISM The procedure calling sequence used by EM‐1 is more complicated than that of most machines since it directly supports the linkage needed by block structured languages. Associated with each procedure is a 2 word descriptor. The first (lower address) word contains the number of words required by the procedure’s parameters. The following word con‐ tains the absolute address in memory where the code begins. All the de‐ scriptors are contiguous, and located in the external area. The monitor and user program each have their own procedure descriptors. Procedures are referred to by their descriptor number, beginning at 0. The PD reg‐ ister contains the address where the currently active descriptors (user or monitor) are located. The first step in the calling sequence is carried out by the MRK instruction, which deposits the 3 word administration zone onto the stack. The return address position is not filled in. Instead a one word hole is left there for its subsequent storage. Then the calling procedure pushes any actual parameters onto the stack. Finally, the calling procedure executes a CAL (or CAS) instruc‐ tion which specifies the number of the procedure to be called. This in‐ struction deposits the return address into the location reserved for it, sets LB to point to the first word above the administration zone, and sets PC from the procedure descriptor. When the CAL instruction has been completed, the called procedure starts executing. Normally, the first instruction will be BEG, to ad‐ vance SP, reserving space for local variables, and (possibly) initializ‐ ing them as well to ‐32768. When a procedure is finished, it executes a RET n instruction, which removes the current frame from the stack and resumes execution at the point following the CAL. It also slides the top n words on the stack down to where the administration zone was. For n = 0, no words are moved, but for n > 0 this can be useful for returning values from functions, since the net result of the call is then to leave a value on the stack. In order to reduce instruction length of most call instructions to one byte, a special mechanism is used in some cases. If all the instruc‐ tions between a MRK and its corresponding CAL belong to a certain group (specified below) a special opcode may be used for MRK. This redefines all the opcodes fetched until the CAL has executed. The redefined opcode table is called the "alternate context". Opcodes 0 up to (but exclud‐ ing) CUTOFF have the same meaning as in the regular context. However, CUTOFF+1 means call procedure 1, CUTOFF+2 means call procedure 2, etc. It should now be clear that the permitted instructions are just those with opcodes 1 to CUTOFF‐1. When assigning opcodes to mnemonics, those useful in parameter passing should be given low values. It should be noted that procedures with a variable number of param‐ eters cannot be accommodated. Each such procedure must have some maxi‐ 7 mum number of bytes worth of parameters, and exactly this number must be passed on each call. Of course the programmer or compiler writer is free to use the BEG instruction to advance the stack pointer, thus simu‐ lating the passing of many dummy parameters in one instruction. 8 4. ARRAY DESCRIPTORS Arrays are accessed via array descriptors. The size of a descriptor is 3 words. Array descriptors are always accessed as external vari‐ ables. The 3 words in the descriptor contain lower bound upper bound ‐ lower bound number of bytes per element The offset n in LAR n, SAR n and AAR n is the position of the lower bound (in words) from the base of the externals. The word fetched from the stack by the LAS, SAS, and AAS instructions is a pointer to the de‐ scriptor. The element A[I] is fetched as follows: 1. Stack the address of A (e.g. using LAE, LEX, or LAL) 2. Stack the value of I 3. LAR n The LAR, SAR, and AAR (as well as LAS, SAS, and AAS) instructions pop the index and subtract the lower bound from it. If the result is nega‐ tive, a trap occurs. If zero or positive, it is compared to upper bound ‐ lower bound (the second descriptor word). If it is out of range, a trap occurs. If ok, I‐lower bound is multiplied by the number of bytes per element (the third word). The result is added to the address of A, which replaces A on the stack. At this point LAR, SAR and AAR diverge. AAR is finished. LAR re‐ moves the address and fetches the data item (the size being specified by the descriptor ‐ however, this must be even, except for 1); SAR removes the address and stores the data item now exposed. 9 5. INPUT/OUTPUT EM‐1 makes the basic assumption that it deals only with intelligent peripherals. This means that the underlying interpreter must intervene and make them look that way. Details of device handling and timing are all handled by the interpreter, not the EM‐1 monitor. There is only one i/o instruction: IOX. This instruction starts out by popping a control word from the stack. The low order byte of this word contains the number of some device; the high order byte con‐ tains the function code: ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ | function code | device | ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ Depending on the function code and device, more words may follow on the stack. For the time being the following devices are defined: 0 ‐ The CPU 1 ‐ The terminal 2 ‐ The network The function code depends on the device. For the CPU codes 1‐15 set the CPU priority to 1‐15 respectively. If an i/o operatifinishes on on a device whose priority is lower than the current CPU priority, the interrupt is held until the CPU priority is dropped sufficiently. The terminal can operate in one of two modes: raw mode and line mode. In raw mode every character is passed onto the program as it is received, i.e. each character causes an interrupt. Among other things, the program (or the monitor) must handle rubout, line erase, kill etc. In line mode, entire lines are collected by the interpreter, and inter‐ rupts only generated when an entire line has arrived. In this mode the interpreter detects and processes certain characters in a special way. These are: 0. rubout ‐ cancels the last data character typed 1. erase ‐ cancels the entire current line 2. quit ‐ cancels all pending input and forces an interrupt 3. reboot ‐ reboots the entire operating system from scratch 4. line delimiter ‐ defines the end of line character The program can choose which characters to use for each function, e.g. whether it prefers cr or lf to delimit lines. The functions defined for the terminal are as follows: 0 ‐ Read from the keyboard (a line or character, depending on mode) 1 ‐ Write to the terminal 2 ‐ Set terminal to line mode 3 ‐ Set terminal to raw mode 4 ‐ Define the character used for rubout, erase, quit etc. 10 Read and write each require two more words from the stack. The next word popped is the address of the i/o buffer. The one after that is the size of the buffer in bytes. If the buffer is too small (on input), on‐ ly the specified number of characters is transmitted. The rest of the characters are saved until the next read. The program can tell that this has happened by noting the absence of the end‐of‐line character in the buffer. Also, even in line mode, characters can be requested one at a time by setting the count to 1. Setting the terminal modes do not require any additional words on the stack, but function 4 expects two more words. The top one of these tells which function is being changed, and the next word contains the character. The functions are numbered as above (rubout = 0, erase = 1, etc.) The network only has two functions: read a packet (function code 0) and write a packet (function code 1). Both functions must specify a buffer address and a byte count, just as terminal i/o. If the buffer is too small, the packet is truncated without notice. Note that the inter‐ rupt informs the monitor how long the packet is, so it has no excuse for using a too small buffer. 11 6. MONITOR AND USER MODE EM‐1 is designed to be monoprogrammed, not multiprogrammed. Never‐ theless there is a need for an operating system, albeit a simple one. Two modes are provided, Monitor and User. The operating system runs in Monitor mode, the user program runs in User mode. The operating system can temporarily disable i/o interrupts, and can perform i/o, neither of which is possible in User mode. There are five situations in which the mode changes: 1. Monitor starting up a user (M to U) 2. User making a system call (U to M) 3. Quit signal (U to M or M to M) 4. I/O interrupt (U to M or M to M) 5. Trap (U to M or M to M) At any instant in time, all 9 of the internal registers listed above have values which are used by the hardware (interpreter) to exe‐ cute instructions. When switching from User mode to Monitor mode, 8 changeable registers are stored within the monitor’s external area, and then the new values are loaded, also from the monitor’s external area. ML is a constant for a given installation, and is never stored or reloaded. When switching from Monitor mode to User mode, the 8 change‐ able registers are reloaded from memory, but the monitor’s status is not stored. When a MON instruction is executed, an i/o interrupt occurs, a quit signal received, or a trap caused, the following steps are taken: 1. The interpreter fetches the address of the vectors from absolute location 0. This is normally outside of the monitor. 2. The first word in the vector is the address of the save area. 3. The 8 changeable registers are stored in the save area, providing there is enough room. The second word in the vector is the limit of the save area. They are stored in the order: PS, PB, PC, EB, PD, LB, SP, HP, with PS at the lowest address and HP at the highest. 4. Certain internal variables needed by the interpreter are stored directly following HP. 5. The first vector word is increased by the number of bytes stored (minimum of 16, if no internal variables are used by the interpreter). The first vector word is in effect a stack pointer for the interrupt stack. 6. The 8 changeable registers are reloaded with new values taken from 8 consecutive memory locations. The address 12 of the lowest of these is found in the third vector word, i.e. the third tells where the new PS comes from. 7. The interpreter stores certain status information in mem‐ ory, so the monitor can see why an interrupt occurred. The address of this status buffer is fetched from address 4. At this point execution resumes, usually in Monitor mode. When the mon‐ itor wants to return from an interrupt, it executes an RTI instruction which reverses the process, namely the interpreter removes from the in‐ terrupt stack all the information it deposited there, decrements loca‐ tion 0 appropriately, and resumes execution with the newly popped regis‐ ters. The start user instruction (STU) works similarly, except that no internal variables are restored. Instead the top word on the stack is popped and used to locate the new PS. Registers PB, PC, etc. follow in the usual order. Exactly 8 words are popped. 13 7. LIST OF TRAPS AND INTERRUPTS Each trap or interrupt causes the reason for the trap to be stored in memory at a location pointed to by location 4. This word is some‐ times followed by other information, depending on the kind of trap. W1, W2, etc. indicate these extra status words in the descriptions that fol‐ low. 0 Monitor call 1 Input available. W1 = device 2 I/O error. W1 = device, W2 = type of error 3 Illegal instruction 4. Address error 5 Subscript error 6. Range error 7. Undefined operand 8. Stack overflow (SP >= HP) and (HP <> 0) 9. Overflow 10. Monitor mode operation in User mode 11. Case error 12. Program counter below PB or above EB 13. Error in set type instruction 14. Bad register number in LOR or STR 15. Odd byte count where even one expected 16. Conversion error 17. Double precision error 18. Double precision overflow 8. MACHINE INSTRUCTION FORMATS The machine instruction formats (the program as it appears in the memory of the EM‐1 machine during execution) have been designed in a way so that they are very compact. The following formats are used: ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ f1a | opcode + addr | ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ f1b | opcode | ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ f2a | opcode | address | ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ f2b | escape | opcode | ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ f3a | opcode | 16 bit address | ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ 14 ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ f3b | escape | opcode | address | ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ f4a | escape | opcode | 16 bit address | ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐ The most common instruction+address combinations are encoded in the f1a format, so only 1 byte is needed. This one byte specifies both the op‐ code and the address uniquely. There are no specific bits for "opcode" and "address". For example, the opcode+address pairs of LOL 0, LOL 1, LOL 2, LOL 3, are simply encode as N, N+1, N+2, N+3. When the machine fetches the first byte and finds N+2, it carries out the LOL 2 instruc‐ tion directly, without further bit decoding. For f3a and f4a, the high order (most significant) byte of the 16 bit address directly follows the opcode byte, i.e. the address of the high order address byte is one higher than the address of the opcode byte. The address of the low order byte is one higher than the address of the high order byte. Note that the order of bytes within the 16 bit addresses is in no way related to the position of high and low order bytes within data words. 15 9. ASSEMBLY LANGUAGE INSTRUCTION LIST x is in bytes in assembly language (and must be even and >= 0); in the object program it is in words. These instructions manipulate entire words. When the description speaks of x bytes it is re‐ ferring to the assembly language, e.g. BEG 6 is an assembly lan‐ guage instruction to reserve 6 bytes (i.e. 3 words). y is in bytes in the assembly language, and must be 1,2,4,6,8,10 or higher even integer. Odd numbers, except for 1, are forbidden. The machine language encoding for offset 1 is a special (zero ad‐ dress) instruction; the other instructions have machine offsets in words. In the machine definition, LOI 1 causes the LIB rou‐ tine to be executed, and STI 1 causes SIB to be executed. LIB and SIB are not available to the user. b is in bytes and is >= 0 in both assembly and machine language; it may be odd or even n is a nonnegative integer m in an integer 9.1 LOAD GROUP LOC m ‐ Load constant (i.e. push it onto the stack) LOL x ‐ Load local word x LOE x ‐ Load external word x LOP x ‐ Load parameter (address is at x‐th local) LOF x ‐ Load offsetted. (top of stack + x yield address) LAL x ‐ Load address of local LAE x ‐ Load address of external LEX n ‐ Load lexical. (address of lb n static levels back) LOI y ‐ Load indirect y bytes (address is popped from the stack) LOS ‐ Load indirect (pop byte count, address; count is 1 or even) LDL x ‐ Load double local (two consecutive locals are stacked) LDE x ‐ Load double external (two consecutive externals are stacked) LDF x ‐ Load double offsetted (top of stack + x yield address) 9.2 STORE GROUP STL x ‐ Store local STE x ‐ Store external STP x ‐ Store parameter STF x ‐ Store offsetted STI y ‐ Store indirect y bytes (pop address, then data) STS ‐ Store indirect (pop byte count, then address, then data) SDL x ‐ Store double local SDE x ‐ Store double external SDF x ‐ Store double offsetted 9.3 SINGLE PRECISION ARITHMETIC ADD ‐ Addition 16 SUB ‐ Subtraction MUL ‐ Multiplication DIV ‐ Division MOD ‐ Modulo (remainder) NEG ‐ Negate (two’s complement) SHL ‐ Shift left SHR ‐ Shift right ROL ‐ Rotate left ROR ‐ Rotate right INC ‐ Increment top of stack by 1 DEC ‐ Decrement top of stack by 1 EXG ‐ Exchange top 2 words ADI b ‐ Add the constant b to top of stack; do not check anything ADS ‐ Same as ADD but do not check for anything 9.4 DOUBLE PRECISION ARITHMETIC (Format not defined) DAD ‐ Double add DSB ‐ Double Subtract DMU ‐ Double Multiply DDV ‐ Double Divide DMD ‐ Double Modulo 9.5 FLOATING POINT ARITHMETIC FAD ‐ Floating add FSB ‐ Floating subtract FMU ‐ Floating multiply FDV ‐ Floating divide 9.6 CONVERSION GROUP CID ‐ Convert integer to double CDI ‐ Convert double to integer CIF ‐ Convert integer to floating CFI ‐ Convert floating to integer CDF ‐ Convert double to floating CFD ‐ Convert floating to double 9.7 BOOLEAN GROUP AND x ‐ Boolean and on two groups of x bytes ANS ‐ Boolean and; number of bytes is first popped from stack IOR x ‐ Boolean inclusive or on two groups of x bytes IOS ‐ Boolean inclusive or; nr of bytes is first popped from stack XOR x ‐ Boolean exclusive or on two groups of x bytes XOS ‐ Boolean exclusive or; nr of bytes is first popped from stack COM x ‐ Complement (one’s complement of top x bytes) COS ‐ Complement; first pop number of bytes from stack NOT ‐ Convert top of stack from true to false or v.v. 9.8 SET GROUP INN x ‐ Bit test on x byte set (bit number on top of stack) 17 INS ‐ Bit test; first pop set size, then bit number SET x ‐ Create singleton x word set with bit n on (n is top of stack) SES ‐ Create singleton set; first pop set size, then bit number 9.9 ARRAY GROUP LAR x ‐ Load array element LAS ‐ Load array element; first pop ptr to descriptor from stack SAR x ‐ Store array element SAS ‐ Store array element; first pop ptr to descriptor from stack AAR x ‐ Stack address of array element AAS ‐ Stack address; first pop pointer to descriptor from stack 9.10 COMPARISON GROUP CMI ‐ Compare 2 integers. Push ‐1, 0, or +1 for less, equal, greater CMD ‐ Compare 2 double integers CMF ‐ Compare 2 reals CMU x ‐ Compare 2 blocks of x bytes each CMS ‐ Compare 2 blocks of bytes; pop byte count TLT ‐ True if less (based on previous compare) TLE ‐ True if less or equal TEQ ‐ True if equal TNE ‐ True if not equal TGE ‐ True if greater or equal TGT ‐ True if greater 9.11 BRANCH GROUP BRF n ‐ Branch forward unconditionally n bytes BRB n ‐ Branch backward unconditionally n bytes BLT n ‐ Forward branch less (pop 2 words, branch if top > second) BLE n ‐ Forward branch less or equal BEQ n ‐ Forward branch equal BNE n ‐ Forward branch not equal BGE n ‐ Forward branch greater or equal BGT n ‐ Forward branch greater ZLT n ‐ Forward branch less than zero (pop 1 word, branch negative) ZLE n ‐ Forward branch less or equal to zero ZEQ n ‐ Forward branch equal zero ZNE n ‐ Forward branch not zero ZGE n ‐ Forward branch greater or equal zero ZGT n ‐ Forward branch greater than zero 9.12 PROCEDURE CALL GROUP MRK n ‐ Mark stack (n = 1 + change in static depth of nesting) MRS ‐ Mark stack; first pop the static link from the stack CAL n ‐ Call procedure (with descriptor n) CAS ‐ Call indirect; first pop procedure number from stack RET x ‐ Return. (function result consists of top x bytes) 18 9.13 INCREMENT/DECREMENT/ZERO GROUP INL x ‐ Increment local INE x ‐ Increment external DEL x ‐ Decrement local DEE x ‐ Decrement external ZRL x ‐ Zero local ZRE x ‐ Zero external 9.14 MISCELLANEOUS BEG x ‐ Begin procedure (reserve x bytes for locals) BES ‐ Like BEG, except first pop x from stack RCK x ‐ Range check (trap if top of stack out of range) NOP ‐ No operation BLM x ‐ Block move x bytes; first pop source address, then dest BLS ‐ Block move; like BLM, except first pop x, then addresses LIN n ‐ Line number (set external 0 to n) DUP x ‐ Duplicate top x words DUS ‐ Like DUP, except first pop x CSE x ‐ Case jump; x is external offset of jump table LOR n ‐ Load register (fetch an internal register) STR n ‐ Store register (store an internal register) HLT ‐ Halt the machine 9.14 MONITOR GROUP MON ‐ Monitor call STU ‐ Start user RTI ‐ Return from interrupt or MON call 19 10. The EM‐1 Assembly Language 10.1 Introduction An assembly language program consists of a series of lines, each containing 0 or 1 statements. A machine instruction may not be labeled. In other words, the label field on a machine instruction must be left blank. To insert a local label into the program, put it on a line all by itself, starting in column 1. Local labels are unsigned integers. Pseudoinstructions CON, ROM, and BSS may be labeled with a 1‐6 character label, the first character of which is a letter, followed by letters, digits and periods. Only 1 label per line is allowed. The use of the character "." followed by a number (e.g. .40) is recommended for compiler generated programs, since these are considered as a special case and handled more efficiently by the present assembler. A label consisting of a single period is treated specially. This is a temporary definition of a global data item. The definition is valid through and including the first reference to the data, but there‐ after becomes undefined. For example, . CON 2,4 LAE . Each statement may contain an instruction mnemonic or pseudoin‐ struction. These must begin in column 2 or later (not column 1) and must be followed by a space, semicolon or LF. The mnemonic is terminated by a space. Everything on the line following a semicolon is taken as a comment. All constants are decimal unless started with a zero e.g. 0177, in which case they are octal. Local labels are referred to as *1, *2, etc. in CON and ROM pseu‐ doinstructions but without the asterisk in branch instructions, e.g use. BRF 3 not BRF *3. The notation $procname is used to mean the descriptor number for the procedure with the specified name. An input file may contain many procedures. A procedure consists of zero or more pseudoinstructions, a PRO statement, a (possibly empty) collection of instructions and pseudoinstructions and finally an END statement. The very last statement on the input file must be EOF. The END directly preceeding the EOF may be omitted. Input to the assembler is in lower case. Upper case is used in this document merely to distinguish key words from the surrounding prose. 20 10.2 Pseudoinstructions NOTATION: = an integer constant = a 1‐6 char‐ acter symbol beginning with a letter = integer, real, or "string" (string may incl. ) ext area = the base of the stack. Addressed by LOE, etc. BSS , ‐ Reserve bytes in ext area, initializing all to num2 (0<=num2<=255). CON ,... ‐ Assemble 1 or more constants in ext area If next address is odd, first output a 0 byte. DIC , ... Assemble 1 or more double precision integer constants END ‐ End of Procedure EXC , ‐ Two blocks of instructions preceeding this one are inter‐ changed. The first is the size of the first block. The second is the size of the second one. They are textually interchanged on pass1 of the assembly. EXD ‐ EXport Data. is made available for use in other files. FWP ‐ When a procedure in the current module is forward refeenced, i.e. used before the definition appears, an FWP pseudoinstruction must given prior to the first call of the procedure. If the procedure appears later, but in an‐ other module, such as a library, then FWP must not appear. FWP prevents a procedure name from being made known to other modules. This is useful, for example, for nested procedure definitions to keep inner procedure names from conflicting with names names which are truly global. HOL ‐ bytes are reserved at the START of the ext area re‐ gardless of its present size; its current contents are re‐ located. May not be used after the first PRO. IMD IMport Data. is defined elsewhere but used here. LET , ‐ Assembly time assignment of to MES 21 A special kind of comment. Used by compilers to communi‐ cate with the optimizer, assembler, etc. as follows: MES 0 ‐ An error has occurred, stop assembly. MES 1 ‐ Suppress optimization MES 2 ‐ Use virtual memory (EM‐2) MES 3‐9 ‐ reserved for future use MES 10‐255 ‐ available for users PRO , ‐ = procedure name, = words for parameters ROM ‐ , ... ROM is identical to CON except that it tells the assembler that the words will never be changed during program execu‐ tion. Declaring storage to be ROM instead of CON allows certain optimizations to take place that would otherwise be impossible (e.g. in some cases subranges can be checked at assembly time instead of run time) VIR ‐ Assemble code for virtual memory. 10.3 The Compact Input Language The assembler accepts input in a highly encoded form. This form is intended to reduce the amount of file transport between the compiler and assembler, and also reduce the amount of storage required for storing libraries. When beginning to read the input, the assembler is in neutral state, and expects either a label or an instruction (including the pseu‐ doinstructions). The meaning of the next byte(s) when in neutral state is as follows, where b1, b2 etc represent the succeeding bytes. The no‐ tation consists first of a length field, and then an ar‐ bitrary string of bytes. If the length field starts out with 0‐254, that is the length of the string. If it is 255, the length follows in the next two bytes, low order byte first. 0 Reserved for future use 1‐149 Machine instructions, in the order listed in the input table 150‐162 BSS,CON,DIC,END,EXC,EXD,FWP,HOL,IMD,LET,MES,PRO 163‐179 Reserved for future pseudoinstructions 180‐239 Local labels 0 ‐ 59 (180 is local label 0 etc) 240‐244 (See the Common Table below) 245‐255 Not used . After a label, the assembler is back in neutral state; it can immediate‐ ly accept another label or an instruction in the very next byte. There are no linefeeds used to separate lines. 22 If an opcode has no operands, the assembler is back in neutral state after reading the one byte containing the instruction number. If it has one or more operands (only pseudos have more than 1), the oper‐ ands follow directly, encoded as follows: 0‐239 Integer constant from 0 to 239 240‐255 (See the Common Table below) Common Table for Neutral State and Operands 240 b1 Local label b1 (Used only for CON and ROM) 241 b1 b2 16 bit local label (256*b2 + b1) 242 b1 Global label .0‐.255, with b1 being. the label 243 b1 b2 Global label .0‐.65535 with 256*b2+b1 being the label 244 Global symbol not of the form .xxx 245 Procedure name ($ is not needed) 246 String used in CON or ROM (no quotes) 247 Real value for CON 248 constant 0‐255 (In fact only used for 241‐255 in practice) 249 b1 250 b1 b2 (16 bit constant) 256*b2+b1 255 Delimiter for CON, ROM lists The pseudoinstructions fall into several categories, depending on their operands: Group 1 ‐‐ END has no operands Group 2 ‐‐ BSS, EXC, HOL, MES have a known number of numeric operands Group 3 ‐‐ EXD, FWP, IMD, LET, PRO have a string and some numbers Group 4 ‐‐ CON, ROM have a variable number of various things Group 1 is easy; just go back into neutral state immediately. Groups 2 and 3 use the encoding described above. Group 4 also uses the encoding listed above, with a 255 byte after the last operand to indicate the end of the list. Example (LOC = 53 , BRF = 18 here): 2 1 LOC 10 LOC ‐10 LOC 300 BRF 19 300 .3 CON 4,9,*2,$foo loc .35 would be encoded: 182 181 23 53 10 53 248 10 53 249 44 1 18 19 241 44 1 242 3 152 4 9 240 1 245 146 157 157 0 255 53 242 35 24 11. OFFICIAL EM‐1 MACHINE DEFINITION (* This is an interpreter for EM‐1. It serves as the official machine definition. This interpreter must run on a machine which supports 32 bit arithmetic. Certain aspects of the definition are over specified. In particular: 1. Addresses should only be created by the following instructions: LAL, LAE, LEX, MRK, MRS, CAL, CAS, ADI, ADS The representation of an address on the stack need not be the numerical value of the memory location. 2. The state of the stack is not defined after a trap has aborted an instruction in the middle. For example, it is officially un‐ defined whether the second operand of an ADD instruction has been popped or not if the first one is undefined (‐32768). *) program em1(input,output); label 0; const maxpos= 32767; (* 2**15 ‐1 *) t16 = 65536; (* 2**16 *) t31m1 = 2147483647; (* 2**31 ‐1 *) maxmem = 16383; (* highest byte implemented at this installation *) escape = 0; (* indicates format f3b, f4a used *) statd = 6; (* how far is static link from lb *) dynd = 4; (* how far is dynamic link from lb *) reta = 2; (* how far is the return address from lb *) undefined = ‐32768; (* the range of integers is ‐32767 to +32767 *) nill = ‐1; (* Illegal address *) (* error codes *) oder = 3; ader = 4; suer = 5; raer = 6; uder = 7; sper = 8; over = 9; coer = 10; caer = 11; pcer = 12; seer = 13; rger = 14; dper = 15; dpov = 16; (* The numbers used here are arbitrary; they are not the machine opcodes *) AAR=1; AAS=2; ADD=3; ADI=4; ADS=5; XAND=6; ANS=7; BEG=8; BEQ=9; BES=10; BGE=11; BGT=12; BLE=13; BLM=14; BLS=15; BLT=16; BNE=17; BRB=18; BRF=19; CAL=20; CAS=21; CDF=22; CDI=23; CFD=24; CFI=25; CID=26; CIF=27; CMD=28; CMF=29; CMI=30; CMS=31; CMU=32; COM=33; COS=34; CSE=35; DAD=36; DDV=37; DEC=38; DEE=39; DEL=40; XDIV=41; DMD=42; DMU=43; DSB=44; DUP=45; DUS=46; EXG=47; FAD=48; FDV=49; FMU=50; FSB=51; HLT=52; INC=53; INE=54; INL=55; INN=56; INS=57; IOR=58; IOS=59; IOX=60; LAE=61; LAL=62; LAR=63; LAS=64; LDE=65; LDF=66; LDL=67; LEX=68; LIB=69; LIN=70; LOC=71; LOE=72; LOF=73; LOI=74; LOL=75; LOP=76; LOR=77; LOS=78;XMOD=79; MON=80; MRK=81; MRX=82; MRS=83; MUL=84; MXS=85; NEG=86; NOP=87;XNOT=88; RCK=89; RES=90; RET=91; ROL=92; ROR=93; RTI=94; SAR=95; SAS=96; SDE=97; SDF=98; SDL=99; SES=100; XSET=101;SHL=102;SHR=103;SIB=104;STE=105;STF=106;STI=107;STL=108;STP=109;STR=110; STS=111;STU=112;SUB=113;TEQ=114;TGE=115;TGT=116;TLE=117;TLT=118;TNE=119;XOR=120; XOS=121;ZEQ=122;ZGE=123;ZGT=124;ZLE=125;ZLT=126;ZNE=127;ZRE=128;ZRL=129;ZZZ=130; 25 (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) (* Declarations *) (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) type bitval= 0..1; (* one bit *) bitnr= 0..15; (* bits in machine words are numbered 0 to 15 *) byte= 0..255; (* memory is an array of bytes *) offset= 0..32767; (* positive integers are offsets *) adr= 0..65535; (* a machine word interpreted as an address *) word= ‐32768..32767; (* a machine word interpreted as a signed integer *) fullrange= ‐65535..+65535; (* intermediate results need this range *) doublerange= ‐t31m1..+t31m1; (* double precision range *) table = array [0..255] of byte; bftype= (andf,iorf,xorf); (* tells which boolean operator needed *) var core: array[0..maxmem] of byte; (* em1 machine’s memory *) ps,pb,pc,eb,pd,lb,sp,hp: adr; (* internal machine registers *) s,t,k: word; (* scratch variables *) j,n:offset; (* scratch variable used as index *) a,b:adr; (* scratch variable used for addresses *) dt,ds:doublerange; (* scratch variables for double precision *) rt,rs:real; (* scratch variables for real *) i: bitnr; (* scratch variable for indexing over bits *) opcode: byte; (* holds the opcode during execution *) insr: byte; (* holds the instructionnumber *) opmap1,opmap2: table; (* map the opcode to instructionnumber *) opfmt1,opfmt2:table; (* operand encoding:0=none; 1=f1a; 2=short; 3=long *) base: table; (* map f1a opcode+operand to the operand *) normalmap: boolean; (* true except when in alternate context *) halted: boolean; (* normally false; set to true by halt instruction *) cutoff: byte; (* opcode of first call in alternate context *) 26 (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) (* Memory access routines *) (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) (* memw returns a machine word as a signed integer: ‐32768 <= memw <= +32767 mema returns a machine word as an address : 0 <= mema <= 65535 memb returns a single byte as a positive integer: 0 <= memb <= 255 store(a,v) stores the word or address v at machine address a storeb(a,b) stores the byte b at machine address a All 5 routines check to make sure the address is within range. The word routines also check to see that the address is even. If an addressing error is found, a trap occurs. *) procedure trap(n:offset); forward; function badadr(a:adr):boolean; (* is the address legal? *) begin if odd(a) or (amaxmem) or ( (a>sp) and (amaxmem) or ( (a>sp) and (a= hp then trap(sper); store(sp,x) end; function popw: word; begin popw := memw(sp); sp:=sp‐2 end; function popa: adr; begin popa := mema(sp); sp:=sp‐2 end; procedure pushd(y:doublerange); var lo,hi:adr; begin if y>=0 then begin push(y mod t16); push(y div t16) end else begin hi:=(‐y) div t16; lo:=(‐y) mod t16; if lo = 0 then begin push(0); push(t16‐hi) end else begin push(t16‐lo); push(t16‐1‐hi) end end end; function popd: doublerange; begin a := popa; b:=popa; if (a=32768) and (b=0) then trap(dper); if a<32768 then popd :=t16 *a+b else popd:= ‐(t16 * (t16‐1‐a)+t16‐b) end; procedure pushr(z:real); begin (* Push a real onto the stack *) ; end; function popr: real; begin t := popw; s:=popw; popr := 0.0 (* Covert to real somehow *) end; 30 (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) (* bit manipulation routines (extract, shift, rotate) *) (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) procedure sleft(var w:word); (* 1 bit left shift *) begin if abs(w) > 16383 then trap(over) else w := 2*w end; procedure sright(var w:word); (* 1 bit right shift with sign extension *) begin if w >= 0 then w := w div 2 else w := (w‐1) div 2 end; procedure rleft(var w:word); (* 1 bit left rotate *) begin if w >= 0 then if w < 16384 then w:= 2*w else w:= 2*w‐t16 else if w > ‐16385 then w := 2*w+1 else w:= 2*w+65537 end; procedure rright(var w:word); (* 1 bit right rotate *) begin if odd(w) then if w<0 then w:=(w‐1) div 2 else w := w div 2 ‐ 32768 else if w<0 then w:=(w+t16) div 2 else w:= w div 2 end; function bit(b:bitnr; w:word):bitval; (* return bit b of the word w *) var i:bitnr; begin for i:= 1 to b do rright(w); if odd(w) then bit:=1 else bit:=0 end; function bf(ty:bftype; w1,w2:word):word; (* return boolean fcn of 2 words *) var i:bitnr; j:adr; begin j:=0; for i:= 15 downto 0 do begin j := 2*j; case ty of andf: if bit(i,w1)+bit(i,w2) = 2 then j:=j+1; iorf: if bit(i,w1)+bit(i,w2) > 0 then j:=j+1; xorf: if bit(i,w1)+bit(i,w2) = 1 then j:=j+1 end end; if j <= maxpos then bf:=j else bf:= j ‐ t16 end; function low4(w:word):bitnr; (* return the low order 4 bits *) begin if w >= 0 then low4 := w mod 16 else low4 := 16 ‐ w mod 16 end; 31 (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) (* Double Precision Arithmetic *) (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) procedure dsplit(x:doublerange; var a,b:adr; var positive:boolean); (* Decompose a double precision number x into 2 words, a and b such that abs(x) = 2**16 * a + b or abs(x) = 2**16 * b + a and positive is set to true if x>=0, false otherwise EM‐1 does not officially define where the high or low part is on top, but for this interpreter we have made an arbitrary choice. *) begin positive := true; if x<0 then begin positive:=false; x:=‐x end; a:=x div t16; b:=x mod t16 end; function doubleadd(x,y:doublerange): doublerange; (* Double precision add including overflow checking. *) var a,b,c,d: adr; signx,signy:boolean; r1,r2:doublerange; begin dsplit(x,a,b,signx); dsplit(y,c,d,signy); if signx = signy then begin r1:=b+d; (* low order parts *) r2:=a+c; (* high order parts *) if r1 >=t16 then begin r1:=r1‐t16; r2:=r2+1 end; (* carry *) if r2 > maxpos then trap(dpov); if signx then doubleadd:=t16*r2+r1 else doubleadd:= ‐(t16*r2+r1) end else doubleadd := x+y (* no overflow possible *) end; function doublemultiply(x,y:doublerange): doublerange; (* This function multiplies two double precision numbers, x and y, without requiring intermediate results of 64 bits. The idea is to decompose abs(x) and abs(y) as follows: abs(x) = (2**16) * a + b abs(y) = (2**16) * c + d Then abs(x*y) = (2**32)*a*c + (2**16)*a*d + (2**16)*b*c + b*d *) var a,b,c,d:adr; signx,signy: boolean; r:doublerange; begin dsplit(x,a,b,signx); dsplit(y,c,d,signy); if (a<>0) and (c<>0) then trap(dpov); r := a*d + b*c; if r > maxpos then trap(dpov); if (b div 2) * d > t31m1 div 2 then trap(dpov); if t16*r > t31m1 ‐ b*d then trap(dpov); r := t16*r + b*d; if signx <> signy then r:= ‐r; doublemultiply := r 32 end; 33 (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) (* Leftover routines *) (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) procedure arraycalc(c:adr); (* subscript calculation *) var j:word; size:offset; a:adr; begin j:= popw ‐memw(c); if (j<0) or (j>memw(c+2)) then trap(suer); size := memw(c+4); if (size<0) or ((size >1) and odd(size)) then trap(suer); a := j*size+popa; push(a) end; procedure incpc(n:offset); (* used by branch instructions to increment pc *) begin pc := pc+n; if pc >= eb then trap(pcer) end; procedure chk1(w:word); begin if w = undefined then trap(uder) end; procedure chk2(w1,w2:word); begin chk1(w1); chk1(w2) end; procedure chkovf(z:doublerange); begin if abs(z) > maxpos then trap(over) end; procedure getk(var k: word); (* This routine unstacks k for those instructions that get the size of something from the stack such as ANS, CMS etc. It returns a word quantity *) begin k:=popw; if (odd(k)) then trap(oder) else k:= k div 2 end; 34 (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) (* i/o routines *) (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) procedure doio; begin ; end; 35 (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) (* Initialization and debugging *) (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) procedure initialize; (* start the ball rolling *) (* This is not part of the official machine definition *) var c:char; ndata,ncode:integer; ebx:adr; begin eb:=0; normalmap := true; cutoff := 50; for a:= 0 to maxmem do core[a] := 0; (* read in the main tables *) i := 0; repeat repeat read(c) until c = ’.’; (* skip comment *) read(opmap1[i], opfmt1[i], base[i]); repeat read(c) until c = ’.’; (* skip comment *) read(opmap2[i],opfmt2[i]); i := i + 1 until opmap1[i‐1] < 0; (* read in registers, vectors, data length, and code length *) read(ps,pb,pc,ebx,pd,lb,sp,hp); (* registers *) for i:=1 to 6 do begin read(j); store(2*i,j) end; (* trap vectors *) read(ndata,ncode); (* words of each, respectively *) (* read in data and program *) for n:= 1 to ndata do begin read(j); store(ebx‐2+2*n,j) end; for n:= 1 to ncode do begin read(j); store(pb‐2+2*n,j) end; eb:=ebx; end; procedure dump; var i,k:integer; begin write(output,pc:6, opcode:4, core[pc+2]:4, sp:6, ’ * ’, memw(lb):5, memw(lb+2):6, memw(lb+4):6, ’ * ’); k:=(sp‐13000) div 2; if k>6 then k:=6; for i:=0 to k‐1 do write(memw(sp‐2*k+2*i+2):6); writeln(output) end; 36 (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) (* MAIN LOOP OF THE INTERPRETER *) (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) (* It should be noted that the interpreter (microprogram) for an EM‐1 machine can be written in two fundamentally different ways: (1) the instruction operands are fetched in the main loop, or (2) the in‐ struction operands are fetched after the 256 way branch, by the exe‐ cution routines themselves. In this interpreter, method (1) is used to simplify the description of execution routines. The tables opfmt1 and opfmt2 are used to determine how the operand is encoded. There are 4 possibilities: 0. There is no operand 1. The operand and instruction are together in 1 byte (mini) 2. The operand is one byte long and follows the opcode byte(s) 3. The operand is two bytes long and follows the opcode byte(s) In this interpreter, the main loop determines the operand type, fetches it, and leaves it in the global variable k for the execution routines to use. Consequently, instructions such as LOL, which use three different formats, need only be described once in the body of the interpreter. However, for a production interpreter, or a hardware EM‐1 machine, it is probably better to use method (2), i.e. to let the execution routines themselves fetch their own operands. The reason for this is that each opcode uniquely determines the operand format, so no table lookup in opfmt1, or opfmt2 are needed. In fact the two tables are not needed. Method (2) therefore executes much faster. However, separate execution routines will be needed for LOL with a one byte offset, and LOL with a two byte offset. It is to avoid this additional clutter that method (1) is used here. In a produc‐ tion interpreter, it is envisioned that the main loop will fetch the next instruction byte, and use it as an index into a 256 word table to find the address of the interpreter routine to jump to. The routine jumped to will begin by fetching its operand, if any, without any table lookup, since it knows which format to expect. After doing the work, it returns to the main loop by jumping in‐ directly to a register that contains the address of the main loop. When the alternate context is entered (after some MRK or MRS in‐ structions), this register is reloaded so that an alternate main loop is used, with an alternate branch table. A slight variation on this idea is to have the register contain the address of the branch table, rather than the address of the main loop. Another issue is whether the execution routines for LOL 0, LOL 2, LOL 4, etc. should all have distinct execution routines. Doing so provides for the maximum speed, since the operand is implicit in the routine itself. The disadvantage is that many nearly identical execution routines will then be needed. Another way of doing it is to keep the instruction byte fetched from memory (LOL 0, LOL 2, LOL 4, etc.) in some register, and have all the LOL mini format instruc‐ tions branch to a common routine. This routine can then determine the operand by subtracting the code for LOL 0 from the register, leaving the true operand in the register (as a word quantity of course). This method makes the interpreter smaller, but is a bit 37 slower. 38 To make this important point a little clearer, consider how a production interpreter for the PDP‐11 might appear. Let us assume the following opcodes have been assigned: 30: LOL 0 31: LOL 2 (2 bytes, i.e. next word) 32: LOL 4 33: LOL 6 34: LOL b (format with a one byte offset) 35: LOL w (format with a one word, i.e. two byte offset) Further assume that each of the 6 opcodes will have its own execution routine, i.e. we are making a tradeoff in favor of fast execution and a slightly larger interpreter. Register r5 is the em1 program counter. Register r4 is the em1 LB register Register r3 is the em1 SP register (the stack grows toward high core) Register r2 contains the interpreter address of the main loop The main loop looks like this: movb (r5)+,r0 /fetch the opcode into r0 and increment r5 asl r0 /shift r0 left 1 bit. Now: ‐256<=r0<=+254 jmp *table(r0) /jump to execution routine Notice that no operand fetching has been done. The execution routines for the 6 sample instructions given above might be as follows: lol0: mov (r4),(sp)+ /push local 0 onto stack jmp (r2) /go back to main loop lol2: mov 2(r4),(sp)+ /push local 2 onto stack jmp (r2) /go back to main loop lol4: mov 4(r4),(sp)+ /push local 4 onto stack jmp (r2) /go back to main loop lol6: mov 6(r4),(sp)+ /push local 6 onto stack jmp (r2) /go back to main loop lolb: clr r0 /prepare to fetch the 1 byte operand bisb (r5)+,r0 /operand is now in r0 asl r0 /r0 is now offset from LB in bytes, not words add lb,r0 /r0 is now address of the needed local mov (r0),(sp)+ /push the local onto the stack jmp (r2) lolw: clr r0 /prepare to fetch the 2 byte operand bisb (r5)+,r0 /fetch high order byte first !!! swab r0 /insert high order byte in place bisb (r5)+,r0 /insert low order byte in place asl r0 /convert offset to bytes, from words add lb,r0 /r0 is now address of needed local mov (r0),(sp)+ /stack the local jmp (r2) /done The important thing to notice is where and how the operand fetch occurred: lol0, lol2, lol4, and lol6, (the mini’s) have implicit operands lolb knew it had to fetch one byte, and did so without any table lookup 39 lolw knew it had to fetch a word, and did so, high order byte first *) 40 begin initialize; repeat 0: (* This label is jumped to when a trap is encountered *) opcode := core[pc]; (* fetch the first byte of the instruction *) dump; (* for debugging purposes only *) pc := pc+1; (* advance the program counter *) if normalmap then (* we are not in alternate context *) if opcode <> escape then (* this is the normal case *) begin insr := opmap1[opcode]; case opfmt1[opcode] of 0: (* no operand *); 1: k:=opcode‐base[opcode]; 2: begin k:=core[pc]; pc:=pc+1 end; 3: begin k:=256*core[pc]+core[pc+1]; pc:=pc+2 end end end else (* escaped, i.e. rare opcode *) begin opcode := core[pc]; pc := pc+1; insr := opmap2[opcode]; case opfmt2[opcode] of 0: (* no operand *); 1: begin k:= core[pc]; pc := pc+1 end; 2: begin k:= 256*core[pc]+core[pc+1]; pc:=pc+2 end end end else (* we are now in the alternate context *) if opcode < cutoff then (* low numbered (i.e normal) instr in alt context *) begin insr := opmap1[opcode]; case opfmt1[opcode] of 0: (* no operand *); 1: k := opcode ‐ base[opcode]; 2: begin k:= core[pc]; pc:=pc+1 end; 3: begin k:= 256*core[pc]+core[pc+1]; pc:=pc+2 end end end else (* high numbered alternate context, i.e. a CAL *) begin insr := CAL; k := opcode ‐ cutoff end; 41 (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) (* Routines for the individual instructions *) (*‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐*) case insr of (* LOAD GROUP *) LOC: push(k); ZZZ: push(‐k); (* Assembly language mnemonic is LOC ‐k *) LOL: push(memw(lb+2*k)); LOE: push(memw(eb+2*k)); LOP: push(memw(mema(lb+2*k))); LOF: push(memw(popa+2*k)); LAL: push(lb+2*k); LAE: push(eb+2*k); LEX: begin a:=lb; for j:=1 to k do a:= mema(a‐statd); push(a) end; LOI: begin a:=popa; for j:= 1 to k do push(memw(a‐2+2*j)) end; LIB: push(memb(popa)); (* generated by LOI 1 only *) LOS: begin k:=popw; a:=popa; if k = 1 then push(memb(a)) else if not odd(k) then for j:= 1 to k div 2 do push(memw(a‐2+2*j)) else trap(oder) end; LDL: begin push(memw(lb+2*k)); push(memw(lb+2*k+2)) end; LDE: begin push(memw(eb+2*k)); push(memw(eb+2*k+2)) end; LDF: begin a:=popa; push(memw(a+2*k)); push(memw(a+2*k+2)) end; (* STORE GROUP *) STL: store(lb+2*k,popw); STE: store(eb+2*k,popw); STP: store(mema(lb+2*k),popw); STF: begin a:=popa; store(a+2*k,popw) end; STI: begin a:=popa; for j:= 1 to k do store(a+2*k‐2*j,popw) end; SIB: begin a:=popa; storeb(a,memb(sp)); sp:=sp‐2 end; (* STI 1 *) STS: begin k:=popw; a:=popa; if k = 1 then begin storeb(a,memb(sp)); sp := sp‐2 end else if not odd(k) then for j:= 1 to k div 2 do store(a+k‐2*j,popw) else trap(oder) end; SDL: begin store(lb+2*k+2,popw); store(lb+2*k,popw) end; SDE: begin store(eb+2*k+2,popw); store(eb+2*k,popw) end; SDF: begin a:=popa; store(a+2+2*k,popw); store(a+2*k,popw) end; 42 (* SINGLE PRECISION ARITHMETIC *) ADD: begin t:=popw; s:= popw; chk2(s,t); chkovf(s+t); push(s+t) end; SUB: begin t:=popw; s:= popw; chk2(s,t); chkovf(s‐t); push(s‐t) end; MUL: begin t:=popw; s:= popw; chk2(s,t); chkovf(s*t); push(s*t) end; XDIV: begin t:= popw; s:= popw; chk2(s,t); if t=0 then trap(over) else push(s div t) end; XMOD: begin t:= popw; s:=popw; chk2(s,t); if t=0 then trap(over) else push(s mod t) end; NEG: begin t:=popw; chk1(t); push(‐t) end; SHL: begin t:=popw; s:=popw; for i:= 1 to low4(t) do sleft(s); push(s) end; SHR: begin t:=popw; s:=popw; for i:= 1 to low4(t) do sright(s); push(s) end; ROL: begin t:=popw; s:=popw; for i:= 1 to low4(t) do rleft(s); push(s) end; ROR: begin t:=popw; s:=popw; for i:= 1 to low4(t) do rright(s); push(s) end; INC: begin t:=popw; chk1(t); chkovf(t+1); push(t+1) end; DEC: begin t:=popw; chk1(t); chkovf(t‐1); push(t‐1) end; EXG: begin t:=popw; s:=popw; push(t); push(s) end; (* UNSIGNED ARITHMETIC *) ADI: begin a:=popa; if badadr(a) then trap(ader); push( (a+k) mod t16) end; ADS: begin t:=popw; a:=popa; if a=nill then trap(ader); push((a+t)mod t16)end; (* DOUBLE PRECISION ARITHMETIC *) DAD: begin dt:=popd; ds:=popd; pushd(doubleadd(ds,dt)) end; DSB: begin dt:=popd; ds:=popd; pushd(doubleadd(ds,‐dt)) end; DMU: begin dt:=popd; ds:=popd; pushd(doublemultiply(ds,dt)) end; DDV: begin dt:=popd; ds:=popd; if dt=0 then trap(dpov); pushd(ds div dt) end; DMD: begin dt:=popd; ds:=popd; if dt=0 then trap(dpov); pushd(ds mod dt) end; (* FLOATING POINT ARITHMETIC *) FAD: begin rt:=popr; rs:=popr; pushr(rs+rt) end; FSB: begin rt:=popr; rs:=popr; pushr(rs‐rt) end; FMU: begin rt:=popr; rs:=popr; pushr(rs*rt) end; FDV: begin rt:=popr; rs:=popr; if rt=0 then trap(over); pushr(rs/rt) end; (* CONVERT GROUP *) CID: pushd(popw); CDI: begin dt:=popd; if abs(dt) > maxpos then trap(coer) else push(dt) end; CIF: pushr(popw); CFI: begin rt:=popr; if abs(rt)>maxpos‐0.5 then trap(coer) else push(round(rt)) end; CDF: begin dt:=popd; pushr(dt) end; CFD: begin rt:=popr; if abs(rt) > t31m1‐0.5 then trap(coer) ; pushd( round(rt) ) 43 end; 44 (* BOOLEAN GROUP *) XAND: for j:= 1 to k do begin t:=popw; a:=sp‐2*k+2; store(a,bf(andf,memw(a),t)) end; ANS: begin getk(k); for j:= 1 to k do begin t:=popw; a:=sp‐2*k+2; store(a,bf(andf,memw(a),t)) end; end; IOR: for j:= 1 to k do begin t:=popw; a:=sp‐2*k+2; store(a,bf(iorf,memw(a),t)) end; IOS: begin getk(k); for j:= 1 to k do begin t:=popw; a:=sp‐2*k+2; store(a,bf(iorf,memw(a),t)) end; end; XOR: for j:= 1 to k do begin t:=popw; a:=sp‐2*k+2; store(a,bf(xorf,memw(a),t)) end; XOS: begin getk(k); for j:= 1 to k do begin t:=popw; a:=sp‐2*k+2; store(a,bf(xorf,memw(a),t)) end; end; COM: for j:= 1 to k do store(sp ‐ 2*k + 2*j,bf(xorf,memw(sp‐2*k+2*j),‐1)); COS: begin getk(k); for j := 1 to k do begin store(sp‐2*k+2*j, bf(xorf,memw(sp‐ 2*k + 2*j), ‐1)) end end; XNOT: begin t:=popw; if t=0 then push(1) else push(0) end; 45 (* SET GROUP *) INN: begin t:=popw; if t<0 then trap(seer); i:= t mod 16; t:= t div 16; if t>=k then trap(seer); sp:=sp‐2*k; push(bit(i,memw(sp+2+2*t))); end; INS: begin getk(k); t:=popw; if t<0 then trap(seer); if t>=k then trap(seer); i:= t mod 16; t:= t div 16; sp:=sp‐2*k; push(bit(i,memw(sp+2+2*t))); end; XSET: begin t:=popw; if t<0 then trap(seer); i:= t mod 16; t:= t div 16; if t>=k then trap(seer); for j:= 1 to t do push(0); s:=1; for j:= 1 to i do rleft(s); push(s); for j := 1 to k‐t‐1 do push(0) end; SES: begin getk(k); t:=popw; if t<0 then trap(seer); i:= t mod 16; t:= t div 16; if t>=k then trap(seer); for j:= 1 to t do push(0); s:=1; for j:= 1 to i do rleft(s); push(s); for j := 1 to k‐t‐1 do push(0) end; 46 (* ARRAY GROUP *) LAR: begin arraycalc(eb+2*k); s:= memw(eb+2*k+4); if s=1 then begin a:=popa; push(memb(a)) end else begin a:=popa‐2; for j:= 1 to s div 2 do push(memw(a+2*j)) end end; LAS: begin a:=popa; arraycalc(a); s:= memw(a+4); if s=1 then begin a:=popa; push(memb(a)) end else begin a:=popa‐2; for j:= 1 to s div 2 do push(memw(a+2*j)) end end; SAR: begin arraycalc(eb+2*k); s:= memw(eb+2*k+4); if s=1 then begin a:=popa; storeb(a,memb(sp)); sp:=sp‐2 end else begin a:=popa+s; for j:= 1 to s div 2 do store(a‐2*j,popw) end end; SAS: begin a:=popa; arraycalc(a); s:= memw(a+4); if s=1 then begin a:=popa; storeb(a,memb(sp)); sp:=sp‐2 end else begin a:=popa+s; for j:= 1 to s div 2 do store(a‐2*j,popw) end end; AAR: arraycalc(eb+2*k); AAS: arraycalc(popa); 47 (* COMPARISON GROUP *) CMI: begin t:=popw; s:=popw; if s 0) and (t=0) do begin a:= mema(sp+2‐2*j); b:=mema(sp+2‐2*k‐2*j); if ba then t:= 1; j:=j‐1 end; sp:=sp‐4*k; push(t) end; CMS: begin getk(k); t:= 0; j:= 1; while (j <= k) and (t=0) do begin a:= mema(sp+2‐2*j); b:=mema(sp+2‐2*k‐2*j); if ba then t:= 1; j:=j+1 end; sp:=sp‐4*k; push(t) end; TLT: if popw < 0 then push(1) else push(0); TLE: if popw <= 0 then push(1) else push(0); TEQ: if popw = 0 then push(1) else push(0); TNE: if popw <> 0 then push(1) else push(0); TGE: if popw >= 0 then push(1) else push(0); TGT: if popw > 0 then push(1) else push(0); (* BRANCH GROUP *) BRF: incpc(k); BRB: begin pc := pc‐k; if pc < pb then trap(pcer) end; BLT: begin t:=popw; if popw < t then incpc(k) end; BLE: begin t:=popw; if popw <= t then incpc(k) end; BEQ: begin t:=popw; if popw = t then incpc(k) end; BNE: begin t:=popw; if popw <> t then incpc(k) end; BGE: begin t:=popw; if popw >= t then incpc(k) end; BGT: begin t:=popw; if popw > t then incpc(k) end; ZLT: if popw < 0 then incpc(k); ZLE: if popw <= 0 then incpc(k); ZEQ: if popw = 0 then incpc(k); ZNE: if popw <> 0 then incpc(k); ZGE: if popw >= 0 then incpc(k); ZGT: if popw > 0 then incpc(k); 48 (* PROCEDURE CALL GROUP *) (* There are four ways to mark the stack. The change in static depth can be given as an immediate operand, or the new static link can be provided on the stack. Also, the instruction may switch into alternate context, or not. Only two of these have mneumonics, i.e. can be used by the programmer. These mnemonics are MRK and MRS, corresponding to the immediate and stacked forms respectively. The decision about using alternate context is made by the assembler. The four cases are: MRK: immediate, normal context MRX: immediate, alternate context MRS: stacked, normal context MXS: stacked, alternate context *) MRK: begin a:= lb; for j:= 1 to k do a:= mema(a‐statd); push(a); push(lb); sp := sp+2; (* stay in normal context *) end; MRX: begin a:= lb; for j:= 1 to k do a:= mema(a‐statd); push(a); push(lb); sp := sp+2; normalmap := false end; MRS: begin push(lb); sp := sp+2 end; (* stay in normal context *) MXS: begin push(lb); sp := sp+2; normalmap := false end; CAL: begin a:=pd+4*k; t:= 2*memw(a); store(sp‐t,pc); pc:=mema(a+2); lb:= sp+2‐t; normalmap:=true end; CAS: begin a:=pd+4*popw; t:= 2*memw(a); store(sp‐t,pc); pc:=mema(a+2); lb:= sp+2‐t end; RET: begin pc:= mema(lb‐reta); a:= sp; sp:= lb‐8; lb:=mema(lb‐dynd); for j:= 1 to k do push(memw(a‐2*k+2*j)) end; RES: begin getk(k); pc:= mema(lb‐reta); a:= sp; sp:= lb‐8; lb:=mema(lb‐dynd); for j:= 1 to k do push(memw(a‐2*k+2*j)) end; (* INCREMENT/DECREMENT/ZERO *) INL: begin t:=memw(lb+2*k); chk1(t); chkovf(t+1); store(lb+2*k,t+1) end; INE: begin t:=memw(eb+2*k); chk1(t); chkovf(t+1); store(eb+2*k,t+1) end; DEL: begin t:=memw(lb+2*k); chk1(t); chkovf(t‐1); store(lb+2*k,t‐1) end; DEE: begin t:=memw(eb+2*k); chk1(t); chkovf(t‐1); store(eb+2*k,t‐1) end; ZRL: store(lb+2*k,0); ZRE: store(eb+2*k,0); 49 (* MISCELLANEOUS *) BEG: begin for j:= 1 to k do push(undefined) end; BES: begin getk(k); for j:= 1 to k do push(undefined) end; RCK: if(memw(sp) memw(eb+2*k+2)) then trap(raer); NOP: ; BLM: begin t:=popa; s:=popa; for j := 1 to k do store(t‐2+2*j,memw(s‐2+2*j)) end; BLS: begin getk(k); t:=popa; s:=popa; for j := 1 to k do store(t‐2+2*j,memw(s‐2+2*j)) end; LIN: store(eb,k); DUP: begin for i:= 1 to k do push(memw(sp ‐ 2*k + 2)) end; DUS: begin getk(k); for i:= 1 to k do push(memw(sp ‐ 2*k + 2)) end; CSE: begin t:= popw ‐ memw(eb+2*k); if(t<0) or (t>memw(eb+2*k+2)) then t:=‐1; pc := pb + mema(eb+6+2*k+2*t); if (pc = pb) or (pc >= eb) then trap(caer) end; LOR: case k of 1:push(pd); 2:push(lb); 3:push(sp); 4:push(hp) end; STR: case k of (* In user mode, only hp may be stored *) 1: begin pd := popa; if badadr(pd) then trap(rger) end; 2: begin lb := popa; if badadr(lb) then trap(rger) end; 3: begin sp := popa; if (sp >= hp) or badadr(sp) then trap(rger) end; 4: begin hp := popa; if (sp >= hp) or badadr(hp) then trap(rger) end end; HLT: halted := true; (* MON, STU and RTI have not been worked out entirely yet *) MON: ; RTI: ; STU: ; IOX: doio end (* end of case statement *) until halted end.