Lab 8: Procedure Calls and Recursion in Assembly

Due Wednesday, Nov 7, 2018, 11:59pm

Exercise 1: Computing NchooseK recursively

C version

In this exercise, you are to write a recursive implementation of NchooseK(), similar to lab 3. You should use the following definition:

        NchooseK(n, 0) = 1
        NchooseK(n, n) = 1
        NchooseK(n, k) = NchooseK(n-1, k-1) + NchooseK(n-1, k)

This function takes in two integers and will return an integer result. All other assumptions Exercise 2 still hold, with the exception that the arguments n and k will be on separate lines in the input (because MARS can only handle one number per input line). The implementation of the NchooseK function must be recursive. A non-recursive implementation of the function will receive zero credit. You can assume that the function will be called only with an argument small enough so that the result does not overflow, i.e., fits within 32 bits.

First implement this function in C (or copy your implementation from lab3 if it was correct, and modify the part that reads the input, if needed). Note the following:

• A starter file is provided: ex1.c.
• The function should have the following name and type: int NchooseK(int n, int k)
• The main() procedure repeatedly reads two lines of input, calls NchooseK() to compute NchooseK, and finally uses printf("%d\n",...) to print the NchooseK value.
• These steps are repeated until a 0 value is read by main as the first argument, and then the program terminates.

Name the file with your C code ex1.c. Test it using your own inputs, and also the sample inputs provided.

Assembly version

Once your C code is working correctly, write the equivalent MIPS assembly program, using the provided starter file (ex1.asm). Since you are implementing a procedure that is recursive, you will need to appropriately manage the stack. That is the main challenge of this exercise.

Templates: Assembly coding templates have been provided for the main procedure (main_template4b.asm) and for other procedures (proc_template4b.asm). To simplify the assembly coding, these templates assume the following: (i) no procedure call needs more than 4 arguments; (ii) any local variables are placed in registers and not created on the stack; (iii) no "temporary" registers need to be protected from a subsequent call to another procedure. These templates correspond to Example 4b on Slide 37 of Lecture 9 (Procedure and Stacks).

Assembly coding templates corresponding to Example 5a on Slide 38 of the lecture are also available (main_template5a.asm and proc_template5a.asm)). The only difference here is that these templates also allow you the ability to save "temporaries" on the stack when they need to be protected from subsequent procedure calls.

Our recommendation is to construct your assembly code in such a manner that the simpler "4b" templates can be used. In particular, if, say, proc1 calls proc2, and proc1 has some important values in temporary registers that it must protect from proc2, then proc1 should copy these important values to "saved" registers (e.g., $s0, $s1, etc.), because it is guaranteed that these values will be the same upon return from proc2. However, if you find the style of the "5a" templates more to your liking, you may cerainly use those.

Factorial Example: As an example of how to use these templates to write a recursive procedure, assembly code is provided for calculating factorial in a recursive fashion, using the "4b" templates. Please carefully study the code for the main procedure (fact_main4b.asm), as well as the recursive factorial procedure (fact_proc4b.asm). The two procedures have been concatenated together into a single assembly file (fact4b.asm); open this file in Mars and run it step-by-step to follow the execution of the recursive procedure. Use these files as guidance to develop your code for this exercise.

You may initially develop your code for each procedure in a separate file using the templates provided, but for this lab, all your final assembly code must be within one file; simply copy-and-paste your procedures below main.

• Use the starter file: ex1.asm.
• Important: Convert your C program line-by-line to its assembly equivalent. Doing it any other way will take you much longer.
• You must follow all of the procedure calling conventions discussed in class. Specifically, arguments must be passed to NchooseK in registers $a0 and $a1, and results should be returned in register $v0.
• You have a lot of leeway in choosing the registers used by your procedures but you must follow the caller/callee save-restore conventions for these registers. Even if your code works, you will lose points if you do not follow the calling conventions.
• In particular, $ra, $fp, and any saved registers ($s0-$s7) must be saved/restored according to conventions exactly as discussed in class.
• More discussion of procedure calling conventions and stack management, including more assembly coding templates, is available in the lecture slides.

Name the file with all of your assembly code ex1.asm. Test it using your own inputs, and also the sample inputs provided.

Exercise 2: Pseudo-random number generator

This exercise does not involve procedure calls or stacks. Its purpose is mainly to provide practice in the use of logical and shift operations. In particular, you are to write a pseudo-random number generator (PRNG) using the classic linear feedback shift-register (LFSR) technique (see Wikipedia article).

We will focus on random numbers in the range 1 to 31 only. Given a starting value (sometimes called the "seed") in the range 1..31, the algorithm generates a succession of random numbers in that range, going through all the 31 values, until the starting value is reached again, at which time the program terminates.

The algorithm works as follows. Suppose the current random number is R. Let us represent its binary form using 5 bits, as R₄R₃R₂R₁R₀. The next random number in the sequence is produced by shifting R to the left by one bit position, and inserting a new bit B into the LSB position. The value of B is given by the XOR of R₄ and R₂.

That is:

B = R₄ XOR R₂
next R = R₃R₂R₁R₀B

A C language implementation of the PRNG is provided (ex2.c). Your task is to write an equivalent MIPS program. Name it ex2.asm. Test it by giving it different starting numbers; each time, the output should be a permutation of the numbers 1 to 31, each appearing only once, until the starting number is reached again. You can also test it using the sample input/output files provided.

Test Inputs, Due Date and Submission Procedure

Sample inputs and corresponding outputs are provided under /home/montek/comp411/samples/lab8. You should try running your program on the sample input files provided, and make sure the program's output is identical to that in the sample output files.

Your assignment must be submitted electronically by 11:59pm on Wednesday, November 7.

First copy the files ex1.c, ex1.asm and ex2.asm to the CS Dept server (classroom.cs.unc.edu) under the appropriate folder in your home directory (e.g., comp411lab/lab8). Then, run the self-checking and submit scripts:

% /home/montek/comp411/bin/comp411start
% cd ~/comp411lab/lab8
% selfchecklab8
% submitlab8

In case of any problems, please contact the instructor or the TAs.