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! =)

Readings

P&H (4th): Chapter 2, section 5 through 7.

Submitting your Solutions

Problem 0

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

Problem 1

For the following two parts, translate the given C code to MIPS assembly code using a minimum number of instructions (do not write the assembly code for a functionally equivalent but different C code). Assume that a, b, i, j are in registers $s0, $s1, $t0, $t1, respectively. Also, for part 2, assume that register $s2 holds the base address of the int array D.

for (i = 0; i < j; i++)
    a -= b;

while (a < 10) {
    D[a+10] = b;
    a += 1;
}

Problem 2

Consider the following C code:

int compare(int a, int b) {
   if (odd(a)) {
      return 1;
   } else if (odd(b)) {
      return 2;
   }
   return 0;

}
int odd(int x) {
   return x & 1;
}

1. Translate this piece of C code to MIPS assembly using a minimum number of instructions. In the worst case, how many MIPS instructions does it takes to execute the compare() function?
2. Sometimes small functions, for example, the odd() function above, are copy and pasted into functions that call them to eliminate function calling overhead. Rewrite your answer to part 1 so that instead of defining and calling the odd() function, compare() simply does the operation in its place. Is there a reduction in the number of MIPS instructions (in the worst case) it takes to execute the compare() function with this technique? If so, by how much?

Problem 3

Write the following VectorNorm function as a MIPS procedure call:

struct vector {
    int x;
    int y;
};

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

The function VectorNorm takes an array of pointers to struct vector and replaces each of the struct vector by a vector that's perpendicular (or normal) to that vector. The vector perpendicular to the vector (x1,y1) is simply (y1, -x1). The function should replace each of the vector in vectors by the corresponding perpendicular vector (there are infinitely many such vectors, but we'll use the one given by the formula).

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. Also, len denotes the size of vectors.

Save your answer to a file named hw4q3.s.

Problem 4

Write two recursive MIPS functions: one called removeOdd and one called print, that will remove the odd indexed (index starts counting from 1) elements and print the contents of, respectively, the 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
L5: .word 5 L6
L4: .word 4 L5
L3: .word 3 L4
L2: .word 2 L3
L1: .word 1 L2
L0: .word 0 L1

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

removeOdd:

print:  

(also contained in hw4q4.s)

Especially for removeOdd, you'd probably do yourself a big favor by writing a bit of C code first. A correctly working program will print "13579" (Note the lack of punctuation or newlines) because 0, 2, 4, 6, 8 are the first, third, fifth, seventh, and ninth elements of the linked list, respectively. 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 the given linked list!)

Problem 5

Translate the following MIPS instructions (which compares the two string $s0 and $s1 and return the index at which they have identical characters) to their corresponding number representations:

1 main:   addiu   $t0 $zero 0
2 loop:   addu    $t1 $s1 $t0
3         addu    $t2 $s2 $t0
4         lb      $t3 0($t1)
5         lb      $t4 0($t2)
6         addiu   $t0 $t0 1
7         beq     $t3 $zero done
8         beq     $t4 $zero done
9         bne     $t3 $t4 loop
10 done:  add     $v0 $t0 $zero
11        jr      $ra

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.