CS 14 -- Lab 4

In today's lab, we will work on procedure calls in assembly. We will work both with non-recursive and recursive procedures.

Simple exponentiation

In this lab, we're going to calculate exponents in a straightforward manner. We are going to assume, for simplicity, that both the base and exponents that we're using are non-negative integers.

If we consider, when y > 0, that x^y = x * x^y-1, then we can write a recursive procedure that will rely on itself to calculate x^y-1, and multiply that result by x. When y = 0, we simply observe that x^y = 1, irrespective of the value of x. So, in Java pseudo-code, the procedure would be:

  public static int calcExponent (int x, int y) {
    if (y == 0) {
      return 1;
    } else {
      return x * calcExponent(x, y-1);
    }
  }
    

Instructions you will need

In order to multiply numbers, you will need to know about three instructions:

1. mult (Multiply): This instruction takes two source registers as arguments. It multiplies the values of those two registers and stores the results in two unaddressable registers, HI and LO. Since the multiplication of two 32-bit values yields a 64-bit product, the result of this options is stored into these two 32-bit addresses; the upper 32 bits of the product are stored into HI and the lower 32 bits into LO.

2. mflo (Move From Low): This instruction takes one destination register as an argument. It copies the vaule in the LO register into that destination register.

3. mfhi (Move From High): This instruction takes one destination register as an argument. It copies the vaule in the HI register into that destination register.

Since we will can assume that we will be multiplying numbers of modest magnitude, we can use only the first two of these instructions, like so:

mult $t1, $t2 # {HI, LO} = $t1 * $t2
mflo $t0 # $t0 = LO

The assignment itself

1. Login to the romulus via VNC and use the following command to copy a file into your directory:

   cp ~sfkaplan/public/cs14/calcexponent.s .

2. Bring up your copy of the calcexponent.s file in xemacs. Examine both the __start procedure as well as the printvalue procedure. Note that this latter procedure encapsulates the basic steps for performing the system call for printing integers. It is a simple procedure that doesn't use any of the callee-preserved registers, and so it needs no activation frame.

3. Find the commend labeled TASK 1. Write the printstring procedure. (Hint: It should be quite similar to the printvalue procedure above it.)

4. Find the comment labeled TASK 2. Insert procedure calls to printvalue and printstring such that the base, exponent, and result of calling calcexponent are printed. Two important bits of information:

   • Never mind that you don't yet have a call to calcexponent. You know that when you do write it, its result will be returned in register $v0. Simply assume that at some later time you will insert that call and that $v0 will take on a meaningful value.
   • Look at the bottom of the file. There are two labels, carat, equals, and newline. These should be helpful in formatting your output such that it appears something like this:

     5^3 = 125

5. Load the simulator and test your program. Are printvalue and printstring called correctly? Does it emit the base and the exponent as expected. Do you see how the procedure call is working? Observe the register $ra when the jal instruction is executed.

6. Find the comment labeled TASK 3. Write the calcexponent procedure. This procedure should expect the base value to have been passed by the caller in register $a0, and the exponent value to have been passed in register $a1. It should calculate the exponent, as described above, and return its result in register $v0. Be sure to preserve any callee-preserved registers that the method uses!

7. Find the comment labeled TASK 4. Insert a procedure call to calcexponent to perform the desired exponentiation.

8. Load the simulator and test your program again. Is calcexponent producing the correct value? Is it recurring correctly? Do you see the right output?

Finishing the lab

Email your code to me like so:

cs14-submit lab-4 calcexponent.s

Please be sure to exit xemacs before you logout, lest you create a zombie process that sucks lots of CPU cycles on romulus.