CSE 378 - Spring 1998

Machine Organization and Assembly Language Programming

Problem Set #3

Due Wednesday, April 22, 1998

• In preparation for next week's assignment, read all of Chapter 2 and Chapter 5 Sections 5.1 (except for pp. 339-342, the subsection called "A Word about...", and any other subsections that we may announce as not to be covered) through 5.3.

• This is the first real programming assignment in which you will need to use SPIM.

1. Write a procedure in MIPS assembly language that finds the number of nonnegative elements and the number of strictly negative elements in an array of integers.  (15 pts)

   Your procedure, which should be called pos_neg, should take two arguments:  a pointer to the array of integers in $a0, and the count of how many elements are in the array in $a1.   It should return the number of strictly positive elements in $v0 and strictly negative elements in $v1.  Follow the calling conventions described in our lectures and discussions.

   A C prototype for this function is a bit odd, since you are returning two values, but it might look something like:

   typedef struct {int pos, neg;} pos_neg_return;
   pos_neg_return pos_neg(int* array, int count);

2. Write a procedure in MIPS assembly language to convert a character string of ASCII digits into the integer value it represents, like C's atoi() function.  The character string is null terminated, and may or may not include a sign character ('+' or '-').   The address of the string will be the single parameter to your function in $a0, and your function should be called to_int.  Your function should return the integer value corresponding to the string in $v0.  If the string was a valid number, return zero in $v1; otherwise return 1 in $v1, indicating an error condition (in which case the value in $v0 is undefined).

   Recall from Problem Set 1 that there is an ASCII table on p. 142 of the book.  As an example, the string "+24" is represented by four bytes with values 43, 50, 52, 0 in decimal.  (15 pts)

3. Now we get to prepare for the fun part, the basis for your quarter project.  Many calculators (in particular, those by Hewlett-Packard) and various older computers are based on the concept of a stack architecture.  It turns out the Java Virtual Machine (JVM) for the Java programming language is also based on a stack architecture.  (30 pts)

   The JVM is an abstract computing machine which is emulated on another system.  Its basic instructions are called bytecodes.  Below is a small subset of the JVM instruction set:

   Name	Bytecode	Instruction Format	Stack operations	Description
   IADD	0x60	IADD	POP v1, POP v2, PUSH res	Integer add
   ISUB	0x64	ISUB	POP v1, POP v2, PUSH res	Integer sub
   IMUL	0x68	IMUL	POP v1, POP v2, PUSH res	Integer mul
   ILOAD	0x15	ILOAD index	PUSH res	Load from mem at index
   ISTORE	0x36	ISTORE index	POP v1	Store to mem at index
   BIPUSH	0x10	BIPUSH immed	PUSH res	Byte Immediate push
   SIPUSH	0x17	SIPUSH immedhi immedlo	PUSH res	Short Immediate push
   POP	0x57	POP	POP v1	POP value, discard
   IFEQ	0x99	IFEQ offsethi offsetlo	POP v1	Branch if v1==0
   IFNE	0x9A	IFNE offsethi offsetlo	POP v1	Branch if v1!=0
   IFLT	0x9B	IFLT offsethi offsetlo	POP v1	Branch if v1<0
   IFLE	0x9E	IFLE offsethi offsetlo	POP v1	Branch if v1<=0
   IFGT	0x9D	IFGT offsethi offsetlo	POP v1	Branch if v1>0
   IFGE	0x9C	IFGE offsethi offsetlo	POP v1	Branch if v1>=0
   GOTO	0xA7	GOTO offsethi offsetlo	none	Unconditional branch
   IRETURN	0xAC	IRETURN	POP v1	Integer return

Each bytecode is (as you might expect) 1 byte long.  An index (as in ILOAD index) is also one byte long (what it refers to will be specified in the next assignment).  The immedhi immedlo and offsethi offsetlo are two successive bytes which are combined to form a 16-bit immediate value; immed by itself is a single byte.

In Assignment 5, you will simulate the JVM.  The overall process will be:

1. Fetch the next bytecode
2. Decode it
3. Fetch operands
4. Execute the operation
5. Store the results

This week, you will start implementing the first two steps:  you will take as input (using standard MIPS calling conventions) a sample string of bytecodes, and decode that string, printing out onto the display the sequence of instructions and parameters which that string represents.  For example, the string of bytecodes:

0x15, 0x12, 0x15, 0x06, 0x60, 0x10, 0xA1, 0x64, 0x36, 0x01

should result in the display:

ILOAD 18
ILOAD 6
IADD
BIPUSH 161
ISUB
ISTORE 1

You should write your code with the entire 5-step sequence in mind, so it should be fairly modular with separate functions for fetch instruction, decode, etc.  To display a string in MIPS, set register $a0 to the address of the null-terminated string, load a "service type code" of 4 into $v0, and execute the syscall instruction.   To display an int, use "service code" 1 in $v0, and set $a0 to the integer value, then do a syscall.

Note that in the future, you will want to dedicate certain registers to certain functions of the JVM you are simulating - for example, one register for the JVM program counter, one for the JVM stack pointer (separate from your program's stack pointer), etc.