Goals

This assignment will give you more practice with MIPS and make sure you're solid on MIPS procedure calling. By the end you should have no qualms about jaling all over the place. We'll also give you a bit of exposure to converting the squishy MIPS instructions we've been writing to their equivalent number representation. And lastly, you'll get to use a little bit of this understanding of instruction representation to decipher your first piece of self modifying code! (optional - but it's awesome so you should totally do it anyways.)

This is also a great opportunity for you to practice commenting your MIPS! Yay documentation! No, but seriously, you should have comments everywhere. It makes it oh so much easier to understand what's going on for the readers, which makes it oh so much more likely for you to get credit for your work! =)

Submitting your Solutions

Problem 0

Copy the contents of ~cs61c/hw/04 to a suitable location in your home directory.

Problem 1

P&H Exercise 2.14. Reproduced here for ease of reference:

The MIPS translation of the C segment:

while (save[i] == k)
    i += 1;

on page 74 uses both a conditional branch and an unconditional jump each time through the loop:

Loop:   sll     $t1, $s3, 2     # Temp reg $t1 = 4 * i
        add     $t1, $t1, $s6   # $t1 = address of save [i]
        lw      $t0, 0($t1)     # Temp reg $t0 = save[i]
        bne     $t0, $s5, Exit  # go to Exit if save[i]!=k
        addi    $s3, $s3, 1     # i = i + 1
        j       Loop            # go to Loop
Exit:

Only poor compilers would produce code with this loop over-head. Rewrite the assembly code so that it uses at most one branch or jump each time through the loop. How many instructions are executed before and after the optimization if the number of iterations of the loop is 10 (i.e., save[i + 10] does not equal k and save[i] ,..., save[i + 9] equal k )?

Save your answer to a file named hw4q1.s.

Problem 2

P&H Exercise 2.15.

Save your answer to a file named hw4q2.s.

Problem reproduced here for ease of reference.

Implement the following C code in MIPS, assuming that set_array is the first function called:

int i;
void set_array(int num){
	int array[10];
	for (i=0; i<10; i++){
		array[i] = compare(num, i);
	}
}

int compare(int a, int b){
	if (sub(a, b) >= 0)
		return 1;
	else
		return 0;
}

int sub (int a, int b) {
	return a-b;
}

Be sure to handle the stack pointer appropriately. The Array declared in set_array is allocated on the stack, and i corresponds to $s0. Draw the status of the stack before calling set_array and during each function call. Indicate the names of registers and variables stored on the stack and mark the location of $sp.

NOTE: I removed all references to $fp that are seen in the book for this problem. Since we did not cover the $fp register in lecture, using $fp is optional for this problem

Problem 3

Write the following VectorSum function as a MIPS procedure call:

struct vector {
    int x;
    int y;
};

void VectorSum(struct vector* vp, struct vector** vectors, int len) {
       ...
}

The function VectorSum takes an array of pointers to struct vector and calculates the sum of all vectors. The sum of two vectors (x1,y1) and (x2,y2) is simply (x1+x2, y1+y2). The resulting vector should be stored in the struct vector pointed to by vp.

You can assume the integer x is stored at lower memory address than y. Therefore, if the address of a struct vector is at 0x50000, than the member x is located at 0x50000, and the member y is located at 0x50004.

Save your answer to a file named hw4q3.s.

Problem 4

Write two recursive MIPS functions: one called insert and one called print, that will insert a value into and print the contents of, respectively, the sorted linked list set up in hw4q4.s. The skeleton code follows:

.data
L9: .word 9 0
L8: .word 8 L9
L7: .word 7 L8
L6: .word 6 L7
L4: .word 4 L6
L3: .word 3 L4
L2: .word 2 L3
L1: .word 1 L2
L0: .word 0 L1

L5: .word 5 0

.text
main:   la $a0 L0
        la $a1 L5
        move $s0 $a0
        jal insert
        move $a0 $v0
        jal print
        addiu $v0 $zero 10
        syscall

insert:

print:  

(also contained in hw4q4.s)

Especially for insert, you'd probably do yourself a big favor by writing a bit of C code first. A correctly working program will print "0123456789" (Note the lack of punctuation or newlines). No, changing around the structure of the defined linked list, while somewhat clever, will not get you credit for this problem - we want to see functioning MIPS code! (and don't hard code the solution to just work for inserting a node containing 5!)

Problem 5

Translate the following MIPS instructions (which copies a string from $s0 to $s1) to their corresponing number represtations:

1 main:   addiu   $t0 $zero 0
2 loop:   addu    $t1 $s1 $t0
3         addu    $t2 $s2 $t0
4         lb      $t3 0($t1)
5         sb      $t3 0($t2)
6         addiu   $t0 $t0 1
7         bne     $t3 $zero loop

Also included is hw4q5.txt. There a section for each line number which is labeled according to the line number and instruction text. In each section, include the binary representation of the instruction, with spaces demarcating the logical divisions in the instruction. Also include a list of what the names of the different parts of the instruction are followed by the decimal value contained in that section. For example, if this was the line of code I was translating:

1 main:   add   $t7 $t8 $t9

Then this would be my answer for that line:

================================
1 main:   add   $t7 $t8 $t9
================================

000000 11000 11001 01111 00000 100000

Type: R
op: 0
rs: 24
rt: 25
rd: 15
shamt: 0
funct: 32

Extra For Experts

Self modifying code! Don't worry, this example won't totally blow your mind:

.data
array:  .word 0 0 0 0 0 0 0 0 0 0

.text
main:   la      $s0 array
loop:   addiu   $a0 $zero 10
        beq     $a0 $zero Exit
        addiu   $a0 $a0 -1
        jal     morph
        addu    $t0 $s0 $v0
        sw      $v0 0($t0)
        j       loop
Exit:   addiu   $v0 $zero 10
        syscall

morph:  sll     $v0 $a0 2
        la      $t0 loop
        lw      $t1 0($t0)
        addiu   $t1 $t1 -1
        sw      $t1 0($t0)
        jr      $ra

(also contained in hw4q6.s)

For this problem explain what lines accomplish the self modification (and how), what the effect of the modification is, and what the overall behavior of the program is. Place your answers in hw4q6.txt.

NOTE: The MARS simulator has a bug in it that does not allow for self modifying code. If we can fix this we will, but for now, try to run through the code mentally.