Spring 06 CS61C Homework 4

MIPS Procedures

Updated (2/13/06)

  1. Fixed typo at questino 5. The resulting vector should be stored in the struct vector pointed by vp.
  2. Added clarification on struct vector memory layout.

Corresponding Reading

Problems

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 72 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.

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

Below is a C code that prints the sum of an array of vectors:

/*
 * Compute sum of an array of vectors
 */
#include <stdio.h>
#include <stdlib.h>
#define NUMVECTORS 4

struct vector {
    int x;
    int y;
};

struct vector *vectors[NUMVECTORS];

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

int main()
{
    int i;
    struct vector retv;

    for (i = 0; i < NUMVECTORS; i++) {
        vectors[i] = (struct vector*) malloc(sizeof(struct vector));
        if (!vectors[i]) {
            printf("Out of memory\n"); return 1;
        }
    }

    FillVectorsFromFile(vectors, NUMVECTORS);

    VectorSum(&retv, vectors, NUMVECTORS);

    printf("Sum of vector = (%d,%d)\n", retv.x, retv.y);
    return 0;
}

The function FillVectorsFromFile() reads values from a file to initialize the vector array passed. You task is to complete the VectorSum procedure in MIPS assembly code. You should follow the calling convention described in the book.

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.

Submission

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