# Problem Set #3

##### Due Wednesday, April 21, 1999
Total Points: 75

• This week read all of Chapter 2 and Chapter 5, Sections 5.1 (except for pp. 339-342, the subsection called "A Word about...") and 5.2. We will send email if there are more sections in Chapter 5 that you need not read.

•
• Instructions for turning in problems

• Name the files that you create for the following problems  pos_neg.s, bfind.s, bcount.s and JVM.s, respectively.  Hand in a (preferably double-sided) printout of these in class on Wednesday.  Also, turn in an electronic version of each of these using:
turnin pos_neg.s bfind.s bcount.s JVM.s

Note that if, for some reason, you want to overwrite your previous submission, turn in all 4 files again using the same turnin command.

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

2.

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);

3. (10 + 20 pts) Problems 3.23 and 3.24 from the text.

4.
5. (30 pts) 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.

6. 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 a sample string of bytecodes (look here for the exact format), 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.

Input format for JVM
• You don't need to take input from the user using syscall's.  So you can forget about reading a string, treating parts of it as a hex number, converting this number to decimal and storing it as consecutive bytes. (However, if you already have a working code for this, feel free to keep it as is.)

• Make a separate file called  test.class with the following contents:

.data
instruction_count:
.word    6
bytecode:
.byte    0x15, 0x12, 0x15, 0x06, 0x60, 0x10, 0xA1, 0x64, 0x36, 0x01

This file will be your sample test program.

• The label instruction_count here points to a location that stores not the number of bytes in the bytecode, but the actual number of JVM instructions represented by the bytecode, which is 6 in this case.

• Write your code for instruction-fetch/decode/... in a file called JVM.s assuming the bytecode is present starting at location bytecode and that the number of JVM instructions is stored at instruction_fetch. Note that you no longer need to worry about treating the input as a string or as a hexadecimal number. Each of 0x15, 0x12, and so on, will automatically be converted to base 10 and stored as a single byte which you can treat as a decimal integer between 0 and 255.

• When simulating using SPIM, load both test.class and JVM.s (remember we discussed loading multiple files in section).