## A Simple Procedure in MIPS Assembly

When writing procedures in assembly, you should begin by asking:

- How many parameters are passed into the procedure?
- How many values will result from the computation in this procedure?
- Does the procedure I’m writing call other procedures (or itself)?

The answers to these questions have direct consequences on the code you need to write. The specifics depend on the ISA with which you work. With MIPS, if the answer to (1) is “*less than or equal to 4″*, all the parameters can be passed using registers (**$a0**, **$a1**, **$a2**, and **$a3**). If the answer to (2) is something like *“two words of data,”* the returned values can be reported to the caller in registers **$v0** and **$v1**.

On the other hand, if the answer to (1) is *“more than 4”* and/or if the answer to (2) is *“more than two words,”* your needs exceed the number of registers available in the MIPS ISA. This is not the end of the world, though, as with a bit more code you can use the stack to handle this passing around of data.

Question (3) determines whether you’re writing a** leaf procedure** (one that doesn’t call **any** other functions) or a procedure with nested procedure calls. We will explore both cases in this week’s lab. In preparation, you should first study carefully sections **8.1-8.2 in our zyBook.**

After reading, work out a solution to the following problem and have it committed to your git repository by the start of your lab session.

## Setup

Create the **Lab06** folder in your **git repository** and copy all of the source files from **~cs206/Labs/Lab06**.

## Exercise 1: A Leaf Procedure

In this exercise you will complete the program in** prelab.s** by writing a procedure called **my_func** which computes the value of the following mathematical expression:

You will be working toward implementing the assembly equivalent of the following C function:

1 2 3 4 5 |
int my_func(int x, int y) { return (4*x) - ((2*y) + C); } |

where **x** and **y** are function parameters, and C is a global variable defined in the main program.

Review the MIPS register conventions in **Figure 8.1.2 (COD Figure 2.11)** of your textbook. The values for **x** and **y** will be passed into to the procedure using the **argument registers**. The value for **C** is a constant defined in the **data segment of the program**. The procedure should compute and return the result using the appropriate **return value register**. Keep in mind that your procedure **must not modify** any of the registers which the convention promises to preserve!

After completing the function, add code to the main program to call **my_func** twice with different inputs and then print out the sum of the results of the two calls. The arguments are given in the assembly source code.

Note that **my_func** is a **leaf procedure**, which means that there is **no need to work with an activation record or ****stack frame**. Use MARS to test your program to ensure that it outputs the correct result. Then, add a breakpoint **at the start of your function**. Run your program to the breakpoint and take note of the value of register** $ra** each time that **my_func** is called. Write these address values in hexadecimal in comments at the end of your assembly source code. For each of these addresses, indicate to what line of your program they correspond.

## Exercise 2: The Collatz Conjecture

The Collatz conjecture states that following the recursive application of the rules below, for any given input **n** the result will eventually **reach 1**:

- if n is
**even**, n = n/2 - if n is
**odd**, n = 3*n + 1 - if n is
**one**, stop

If you think about this carefully, it is very natural to define *recursive function *to compute the next numbers in a Collatz sequence that starts with a given input value **n**. We can do this as follows; assume that this function will be named **collatz** and that it returns an integer number. As with all recursive function definitions, we start with the statement of a *base case :*

**collatz(1) =1**

When **n**, the argument to the function is not equal to 1, we have two possible cases:

(a) when **n **is even: **collatz(n) = n/2**

(b) when **n **is odd: **collatz(n) = 3*n +1**

For example, suppose we start with **n = 13**, using our recursive function, we have:

**collatz(13) = 3*13 +1 = 40****collatz(40) = 40/2 = 20****collatz(20) = 20/2 = 10****collatz(10) = 10/2 = 5****collatz(5) = 3*5 + 1 = 16****collatz(16) = 16/2 = 8****collatz(8) = 8/2 = 4****collatz(4) = 4/2 = 2****collatz(2) = 2/2 = 1****collatz(1) = 1**: since we arrived at the base case, the recursion stops.

Starting from n = 13 and recording each number generated by this recursive function, the following sequence emerges:

13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Counting the number of values from the starting **n **until we arrive at the base case, inclusively, for **n=13**, we determine that the sequence has **length 10**.

In this exercise you will write a **C program** that uses a *recursive function *to compute the **Collatz sequence lengths **for integers 1…100. We have provided a basic outline in the** collatz.c** file you should have copied at the beginning of the prelab. Complete the functions as specified.** Do not make structural changes to the code**. The file is available for you to copy from **~cs206/Labs/Lab06/collatz.c** (or you can just copy and paste). Be sure to create a **Makefile** to compile your collatz program. Refer back to Lab 4 if you need help with Makefiles.

Note that there are different ways in which you can determine whether a number is even or odd, in C. One option is to use the modulo operator **%** to get the remainder of the integer division by 2. Another way uses the bitwise *and *operator **&** to that end. You can read a discussion of the merits and the drawbacks of each one at http://stackoverflow.com/questions/160930/how-do-i-check-if-an-integer-is-even-or-odd. Feel free to use the method you like best.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <stdio.h> #define MAX_ITEMS 100 int collatz(int n) { // TODO implement this function to return // if n is 1: 1 // if n is even: n / 2 // if n is odd: 3 * n + 1 // checking for even/oddness in C is a debatable topic: // http://stackoverflow.com/questions/160930/how-do-i-check-if-an-integer-is-even-or-odd } int find_length(int n) { // TODO: implement a recursive function to count the number of // calls to collatz needed to reach 1 starting with n. // We suggest you follow the same structure as the following // factorial function: // int sub1 (int i) // { // return i - 1; // } // int factorial (int i) // { // if (i <= 1) // return 1; // else // return i * factorial (sub1(i)); // } } int main(void) { int i; for (i=1; i<MAX_ITEMS; i++){ printf ("%d ==> %d\n", i, find_length(i)); } return 0; } |

To verify your work, the first 13 lines of output should be:

1 ==> 1 2 ==> 2 3 ==> 8 4 ==> 3 5 ==> 6 6 ==> 9 7 ==> 17 8 ==> 4 9 ==> 20 10 ==> 7 11 ==> 15 12 ==> 10 13 ==> 10

## Submit

The deliverables for this pre-lab assignment are your files **prelab.s **and **collatz.c**. Once you have debugged them to your heart’s content push them to your gitlab repository.

## Grading Rubric

**25 points total:**

**[15 points]**Exercise 1: Leaf procedure implemented in**prelab.s**. Function returns the proper value. The static variable C is properly defined in the**data segment**.**$ra**is noted for the two calls to my_func**in a comment**.**[10 points]**Exercise 2:**collatz.c**is completed correctly using a recursive function (**find_length**) and a leaf function (**collatz**). C Coding conventions are followed (including adding good comments and creating a proper Makefile).

## Recent Comments