Due 11:59pm on Wednesday, November 14, 2018.
Let us revisit Lab 5, Exercise 4. In Lab 5, you wrote C code for a recursive function that generates all binary patterns of length N. Now, you will wite MIPS assembly code to do the same.
Specifically, write a recursive function that, given a number N, generates all binary patterns of length N. For example, for N=3, it will output:
000 001 010 011 100 101 110 111
Likewise, if N were 4, the output will be 16 lines long, corresponding to the binary strings of length 4, in increasing order, starting with 0000 and ending with 1111.
Your MIPS assembly implementation must be recursive. A non-recursive implementation will receive zero credit. See Lab 5 for more details on the exercise.
Assume N will not be more than 10. Name your file ex1.asm, and test using your own inputs as well as the input/output sample files.
Tip: The easiest way to develop the assembly code here is to convert your C code from Lab 5 to assembly line-by-line. Just be sure to start with correct C code that is properly recursive.
For convenience, repeated below is information from Lab 8 about assembly coding templates for writing procedures, and also the factorial coding example.
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.
Reminder: Before beginning work, it is generally a good idea to run the following command so your terminal environment is set up properly:
% /home/montek/comp411/bin/comp411start
Sample inputs and corresponding outputs are provided under /home/montek/comp411/samples/lab9. 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 (i.e., the file ex1.asm) must be submitted electronically by 11:59pm on Wednesday, November 14.
How to submit: Navigate to the folder where these files are stored (~/comp411lab/lab9), and run the following command for running a self-checking script (which does not submit the files):
% cd ~/comp411lab/lab9
% selfchecklab9
If the self-check did not report any errors, you can submit your work as follows:
% cd ~/comp411lab/lab9
% submitlab9
In case of any problems, please contact the instructor or the TAs.