University of California at Berkeley
College of Engineering
Department of Electrical Engineering and Computer Science

CS61C, Spring 2008

...HW 4!

[TA] Eric - and the Elders Of 61C

Due Wednesday, Feb 24, 2010 @ 11:59pm

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

Submit your solution by creating a directory named hw4 that contains files named hw4q1.s, hw4q2.s, hw4q3.s, hw4q4.s, and hw4q5.txt. (Note that capitalization matters in file names; the submission program will not accept your submission if your file names differ at all from those specified.) From within that directory, type "submit hw4". This is not a partnership assignment; hand in your own work.

Problem 0

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

$ cp -r ~cs61c/hw/04/ ~/hw4

Problem 1

P&H Exercise 2.18.2, both parts (a) and (b). Save your answers in hw4q1.s

Problem 2

P&H Exercise 2.19.1 and 2.19.2, do part (a) only for both problems. Save your answers in hw4q2.s

Problem 3

Write the following VectorMult function as a MIPS procedure call:

struct vector {
    int x;
    int y;
};

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

The function VectorMult takes an array of pointers to struct vector and multiplies each of the struct vector by scale. The product of vector (x1,y1) and integer scale is simply (x1 * scale, y1 * scale). The function should replace each of the vector in vectors by the corresponding product.

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 remove and one called print, that will remove a value 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
        addi $a1 $0 9
        move $s0 $a0
        jal remove
        move $a0 $v0
        jal print
        addiu $v0 $zero 10
        syscall

remove:

print:  

(also contained in hw4q4.s)

Especially for remove, you'd probably do yourself a big favor by writing a bit of C code first. A correctly working program will print "012345678" (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 removing a node containing 9!)

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         lw      $t3 0($t1)
5         sw      $t3 0($t2)
6         addiu   $t0 $t0 4
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.