Due 11:55pm on Friday, April 17, 2020.
You wrote a recursive C implementation of NchooseK() in Lab 3 Exercise 6. The definition of the function is repeated here for convenience:
NchooseK(n, 0) = 1
NchooseK(n, n) = 1
NchooseK(n, k) = NchooseK(n-1, k-1) + NchooseK(n-1, k)
All other assumptions from Lab 3 still hold. 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 a 32-bit integer.
If your C implementation in Lab 3 was correct, please use that for developing your MIPS code. If it was not correct, please first fix it.
Once you have developed the correct C code, 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).
The "4b" templates should be sufficient for this exercise. Our recommendation is to construct your assembly code in such a manner that the "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.
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.
Method: We suggest you initially develop your code for each procedure in a separate file using the templates provided: main_template4b.asm for main, and proc_template4b.asm for the procedure NchooseK. That will force you to maintain a clean separation between the codes of the two procedures.
To run your code in MARS, first make sure the two assembly files are located in the same folder, and that there are no other .asm files in that folder. Open the two assembly files in MARS. Under Settings, select "Assemble all files in directory". Next, in the Edit window, make sure that the file with main is selected, and then assemble and run.
Submission: Before submission, you will need to combine your code into a single assembly file. Concatenate the two files (main first), and save it as a single file ex1.asm. Move it to a different sub-/folder so it is the only .asm file in that folder. Open it in MARS and assemble and run it to make sure it still runs properly.
Note:
Name the file with all of your assembly code ex1.asm. Test it using your own inputs, and also the sample inputs provided.
Sample inputs and corresponding outputs are provided on the comp411-1sp20.cs.unc.edu server under /home/montek/comp411/samples/lab9.
Your assignment (i.e., the file ex1.asm) must be submitted electronically by 11:55pm on Friday, April 17, 2020.
Once you are satisfied that your assembly program is running fine within MARS on your laptop, copy the file ex1.asm to the server under the appropriate folder in your home directory (e.g., comp411lab/lab8). Then, run the self-checking script:
% cd ~/comp411lab/lab9
% cp /home/montek/comp411/samples/lab9/* .
% selfchecklab9
How to submit: If the final version of either of your programs were edited on the server, first transfer your work back to your laptop. Next, log in to Sakai in a browser window, and look for the lab under "Assignments" in the left panel. Attach the requested files and submit.
In case of any problems, please contact the instructor or the TAs.