CS 61C (Summer 2008)

Lab Assignment 5

Goals

These exercises are intended to give you more practice with function calling—in particular, what goes onto the stack— plus an introduction to logic operators.

Reading

Sections 2.5-2.7 in P&H.

Initial preparation

You must work with a partner on these exercises.

Copy the directory ~cs61c/labs/05 to an appropriate directory under your home directory.

Exercise 1 (2 points)

The file swap.s provides a test call to the code you'll be supplying for this exercise.

Part a

Translate the following procedure directly to MIPS assembly language, and place your code under the swap label in swap.s. The temp variable, like all local variables in C (when not optimized), is stored on the stack. In other words, you cannot use $t0 or $s0 to hold temp. You may need $t0 briefly, but you must still use the stack to hold temp. Hint: you will need to use 6 lw/sw instructions.

This exercise is slightly contrived, and could be easier if we let you optimize and use a register to hold the temp variable, but part of the point of this exercise is to see what kind of difference optimization can make.

void swap (int *px, int *py) {
    int temp;
    temp = *px;
    *px = *py;
    *py = temp;
}

Part b

Now modify your solution to the previous step to implement the following buggy version of the swap procedure.

void swap (int *px, int *py) {
    int *temp;
    *temp = *px;
    *px = *py;
    *py = *temp;
}

Part c

As you should have learned from the Binky pointer video earlier this summer, the bug is that the temp pointer is dereferenced without being initialized. Why might a programmer not notice this even after testing the buggy swap?  In other words: what situation would allow buggy swap to seem to work correctly?

Part d

Supply the definition of a C procedure proc to be called in the main program immediately prior to the call to the buggy swap(as shown below), that will guarantee that swap will crash when the uninitialized temp pointer is dereferenced (it should cause a crash on *temp). Also explain why your call guarantees this crash. Hint: your proc procedure will leave something on the stack.

int main () {
    int a = 1, b = 2;
    proc(/* Some args might go here */);
    swap(&a, &b);
}

Explain all your code to your TA for checkoff.

Exercise 2 (1 point)

Add the prologue and epilogue to the code in nchoosek.s so that it computes "n choose k". the number of combinations of n distinct elements taken k at a time. (This is also the (n,k) entry in Pascal's triangle.)

Show your test run to your TA for checkoff.

Exercise 3 (1 point)

Write two versions of a function named first1pos (starting from first1pos.s) that, given a value in $a0, returns in $v0 the position of the leftmost bit in the word in $a0. If $a0 contains 0, store -1 in $v0. You are allowed to modify $a0 in the process of finding this position. Positions range from 0 (the rightmost bit) to 31 (the sign bit).

One of your solutions should repeatedly shift $a0, checking the sign bit at each shift (What does this imply about the direction you should shift?). The other should start a mask at 0x80000000 and repeatedly shift it right to check each bit in $a0.

You may wish to split this work between partners, with one of you doing one version and the other doing the second. Explain your code to your partner once you finish, then show your test run to your TA for checkoff.