Fall 06 CS61C Homework 4

MIPS Procedures

Due October 4th at 11:59PM.

TA of note: Dave J.

Corresponding Reading


Question 1

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

The MIPS translation of the C segment:

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

on page 74 uses both a conditional branch and an unconditional jump each time through the loop. 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*j] do not equal k and save[i] ,..., save[i + 9*j] equal k )?

Save your answer to a file named hw4q1.s.

Question 2

P&H Exercise 2.15.

Save your answer to a file named hw4q2.s.

Question 3

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

Write a MIPS procedure to compute the nth Fibonacci number F(n) where:

F(n) = 0, if n = 0;
        1, if n = 1;
        F(n-1) + F(n-2), otherwise;

Base your algorithm on the recursive algorithm below (do not compile to an iterative solution):

int fib(int n){
        if (n == 0)
                return 0;
        else if (n == 1)
                return 1;
                return fib(n-1) + fib(n-2);

Save your answer to a file named hw4q3.s.

Question 4

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

Write a program in MIPS assembly language to convert an ASCII decimal string to an integer. Your program should expect register $a0 to hold the address of a null-terminated string containing some combination of the digits 0 through 9. Your program should compute the integer value equivalent to this string of digits, then place the number in register $v0. Your program need not handle negative numbers. If a nondigit character appears anywhere in the string, your program should stop with the value -1 in register $v0. For example, if register $a0 points to a sequence of three bytes 50ten , 52ten , 0ten (the null-terminated string "24"), then when the program stops, register $v0 should contain the value 24ten . (The subscript ten means base 10.)

Save your answer to a file named hw4q4.s.

Question 5

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 hw4q5.s.


Save all your files (hw4q1.s, hw4q2.s, hw4q3.s, hw4q4.s, hw4q5.s) in a directory named hw4. From the directory hw4 run:

submit hw4