CDA4101, Summer A 1999, Assignment 3

Due Thursday 5/27 at the start of class

Submitting Homework Online. I would like you to submit Assignment 3 online. If you have more than one source file, then upload all of them, including any data files that your program reads. In addition to uploading all of your source code, please hand in a printout of all your source code, and a printout of the input file and the output file.

You are to write a translator for a Very Simple Machine (VSM not to be confused with VMS!). You may use C, C++, ADA, PASCAL, or JAVA. In C++ and C there is a very nice function in <string.h> called strtok. Do not implement the condition codes, I am including the information so that your translations will be logically correct.

VSM has the following features

8 16-bit registers that are named R0, R1, R2, ..., R7.
Memory is organized as words of 16-bits, so reading and writing are simplified.
All arithmetic and boolean operations only work on registers. In other words, in order to work on a value stored in memory, it must first be loaded into a register, and in order to store a value into memory, the result must be calculated in a register and then stored into memory.
The 'direction' of operations in VSM is left to right, so that SUM R0, R1, R2 means reg2 = reg1 + reg0;
BAND R0, R1, R2 means reg2 = reg1 BAND reg0.

IMMEDIATE values can be symbolic addresses (names), or numbers. If they are numbers, the default base is base 10. By placing an 'h' after a number it will be assumed to be hex. For decimal numbers, you may use a - sign to indicate that the number is negative, eg. -1. For hex, you must use 2's complement to represent a negative. There are no # signs in VSM. An immediate value may represent a number for a calculation, or the address of a value.

Examples:

VSM Code Explanation

SUM R0,R1,R1 reg1 = reg1 + reg0

SUM R1,R4,R5 reg5 = reg4 + reg1

LOAD TOTAL,R3
SUM R3,R1,R1 Bring the memory location TOTAL into a register and then add it to register 1

LOAD 5,R3 Load the contents of memory location 5 into register 3.

MOVI 6,R5
SUM R5,R1,R1 Bring the immediate value 6 into register 5, then add it to register 1

MOVI 0Fh,R5 Bring the immediate value of 0F hex into register 5

MOVI 0FFFFh,R5 Bring the immediate value of -1 hex into register 5

TOP:
...
...
JMP TOP A jump to a label. TOP is the destination of the jump.

VSM Code	Explanation
SUM R0,R1,R1	reg1 = reg1 + reg0
SUM R1,R4,R5	reg5 = reg4 + reg1
LOAD TOTAL,R3 SUM R3,R1,R1	Bring the memory location TOTAL into a register and then add it to register 1
LOAD 5,R3	Load the contents of memory location 5 into register 3.
MOVI 6,R5 SUM R5,R1,R1	Bring the immediate value 6 into register 5, then add it to register 1
MOVI 0Fh,R5	Bring the immediate value of 0F hex into register 5
MOVI 0FFFFh,R5	Bring the immediate value of -1 hex into register 5
TOP: ... ... JMP TOP	A jump to a label. TOP is the destination of the jump.

Here are the instructions that VSM understands. DEST, SRCA, and SRCB are always register numbers from R0 to R7. IMMEDIATE is any number, or a symbolic name representing a number (a variable name in higher level languages).

SUM  SRCB, SRCA, DEST
	DEST = SRCA + SRCB
	Add SRCB to SRCA store result in DEST.
	Affects all four condition codes: C, V, Z, N. 
	All operands are registers.
BAND  SRCB, SRCA, DEST
	DEST = SRCA BAND SRCB
	Perform Boolean AND of SRCB with SRCA store result in DEST.
	Affects condition codes N and Z; clears C and V.
	All operands are registers.
NOT  SRCA, DEST
	DEST = NOT SRCA
	Perform Boolean NOT of SRCA store result in DEST.
	Affects condition codes N and Z; clears C and V.
	All operands are registers.
MOV  SRCA, DEST
	DEST = SRCA
	Copy SRCA to DEST.
	Affects condition codes N and Z; clears C and V.
	All operands are registers.
MOVI IMMEDIATE, DEST
	DEST = IMMEDIATE
	Copy IMMEDIATE value to DEST.
	Affects condition codes N and Z; clears C and V.
	DEST is a register, IMMEDIATE is a number or a symbolic constant.
LSH  SRCA, DEST
	DEST = LSH SRCA
	Shift SRCA 1 bit to the left store result in DEST, fill with 0.
	Affects condition codes N, Z and C; clears V.
	All operands are registers.
RSH  SRCA, DEST
	DEST = RSH SRCA
	Shift SRCA 1 bit to the right store result in DEST, fill with 0.
	Affects condition codes N and Z; clears O and V.
	All operands are registers.
LOAD IMMEDIATE, DEST
	Read the value from memory that is stored at the address held 
	in IMMEDIATE. Store the result in DEST.
	DEST is a register, IMMEDIATE is a number or a symbolic constant,
	representing an address in memory.
	Affects condition codes N and Z; clears C and V.
STORE SRCA, IMMEDIATE
	Write the value in SRCA to the memory location whose address is
	the value of IMMEDIATE.
	SRCA is a register, IMMEDIATE is a number or a symbolic constant,
	representing an address in memory.
	Doesn't affect any condition codes.
JMP  IMMEDIATE
	Jump to the address IMMEDIATE.
	Doesn't affect any condition codes.
JMPZ IMMEDIATE
	Jump to the address IMMEDIATE if the results of the last operation
	was zero.
	Doesn't affect any condition codes.
JMPN IMMEDIATE
	Jump to the address IMMEDIATE if the results of the last operation
	was negative.
	Doesn't affect any condition codes.
JMPC IMMEDIATE
	Jump to the address IMMEDIATE if the results of the last operation
	caused an unsigned overflow.
	Doesn't affect any condition codes.
JMPO IMMEDIATE
	Jump to the address IMMEDIATE if the results of the last operation
	caused a signed overflow.
	Doesn't affect any condition codes.
IMMEDIATE:
	A label. This is the target of a jump. A label can precede any statement or can
	appear on a line by itself. The ':' must directly follow the IMMEDIATE
	value (this makes it easier for you to parse).

It has been decided by the system analyst (me) that this language is too tedious to use for programming, however the hardware will not be redesigned. So, the programmer (you) has been instructed to create a translator that will translate a language that is Much Better Intuitively (MBI) into the above language. Here are the instructions that MBI will understand.

Notice the following about MBI

MBI instructions have a right to left direction: ADD X, Y means X = X + Y.
LABEL is an immediate value representing an address in the code.
X is the destination location. It is also the first source operand, so ADD X, Y means X = X + Y.
Y is the second source location.
Immediate values in MBI are preceded by a # sign. VSM does not use the #, so it is wrong if it is included in the VSM code.
MBI does not have access to the registers of VSM.
Negative numbers will be stored in 2's complement.

ADD  X, Y
	X = X + Y
SUB  X, Y
	X = X - Y. Subtraction is performed by using 2's complenent.
MUL  X, Y
	X = X * Y. Repeated addition will be fine for this. Assume each number is 
	between -128 and 127. So, you need to worry about the sign, but do not worry
	about overflow.
NOT  X
	X = NOT X
AND  X, Y
	X = X AND Y
OR   X, Y
	X = X OR Y. Use some Boolean Algebra to rewrite this using only ANDs and NOTs.
XOR  X, Y
	X = X XOR Y. Use some Boolean Algebra to rewrite this using only ANDs and NOTs.
MOV  X, Y
	X = Y
SHL X, Y
	Shift Y to the left X number of places. Fill vacated bits with zeroes.
SHRA X, Y
	Shift Y to the right X number of places. Fill vacated bits with copies
	of the sign bit. Arithmetic shift right.
SHRL X, Y
	Shift Y to the right X number of places. Fill vacated bits with zeroes. 
	Logical shift right.
JMP  LABEL
	Jump to the address LABEL.
	Doesn't affect any condition codes.
JMPZ LABEL
	Jump to the address LABEL if the results of the last operation
	was zero.
	Doesn't affect any condition codes.
JMPN LABEL
	Jump to the address LABEL if the results of the last operation
	was negative.
	Doesn't affect any condition codes.
JMPC LABEL
	Jump to the address LABEL if the results of the last operation
	caused an unsigned overflow.
	Doesn't affect any condition codes.
JMPV LABEL
	Jump to the address LABEL if the results of the last operation
	caused a signed overflow.
	Doesn't affect any condition codes.
LABEL:
	This is the target of a jump. A label can precede any statement or can
	appear on a line by itself. The ':' must directly follow the LABEL value
	(this makes it easier for you to parse).

An MBI program cannot access any of the registers of the VSM machine. For ADD, SUB, MUL, OR, XOR the second operand can be a symbolic address, an address or an immeditae value. For the shift instructions, the first operand may be a symbolic address, an address or an immediate value. All immediate values in MBI will be preceded by the # sign, otherwise they will be considered addresses. VSM immediate values do not have a # sign, they can only be in one instruction: MOVI.

Your translator should read a file that is written in MBI and translate it to a program in VSM. Be sure that you don't duplicate any labels in the VSM program. For instance, if there is more than one MUL instruction in the MBI program, be sure that all the labels are unique in the VSM program.

For each language, there will only be one instruction per line. You may use symbolic addresses in each language. Do not be concerned with where these symbolic addresses are created. Assume that some other module will be handling the symbol table. If there is a symbolic address in the MBI program, then use the same symbolic address in the VSM program.

Notice that in the VSM language, all instructions work on registers, except for the instructions MOVI, LOAD, STORE and all the JMP instructions. When referencing a register, just use the number for the register: 0, 1, 2, ... 7.

If an MBI instruction contains a symbolic address, like NUM, as a source then in VSM you must first LOAD the value from NUM into a register. If the symbolic address is used as a destination, then you must STORE the contents of the register into memory at NUM.

Do not be too concerned about multiplying large numbers. Just write the routine to perform multiplication for two numbers that are both between -127 and 128. This way you will avoid the problem of having a result that won't fit in a register.

I will provide a test program at a later date. Test the program using your own test program until that time.