Lab 8: String Processing, Procedure Calls and Recursion


Your assignment must be submitted electronically by 11:59pm on Friday, November 10.


Exercise 1: Parsing an ASCII string to binary number

Write a function a_to_i that converts a string of ASCII digits into a 32-bit integer. The function will receive as an argument the starting address of the string and must return a 32-bit integer containing the integer value of the string. Assume that the string is an ASCIIZ string, i.e., ends with the null character (ASCII code 0). You don't need to check for errors in the string, i.e., you may assume the string contains only characters '0' through '9' (i.e., their corresponding ASCII codes), and will not represent a negative number or a non-decimal value or too large a number. For example, a_to_i called with the argument "12345" will return the integer 12345.

Starter files are provided: ex1.c and ex1.asm.

First write a C program (ex1.c), where main() repeatedly reads a string from the input using fgets(), then calls a_to_i() with this string as an argument. The function a_to_i() returns an integer, which main prints using printf("%d\n",...). The program should terminate when the integer read is 0.

Next, write the equivalent MIPS assembly program (ex1.asm), that does the same. That is, your main procedure must repeatedly read a string from the input using syscall 8, then call procedure a_to_i with the string just read as an argument. The function a_to_i returns an integer, which main prints using syscall 1. The program should terminate when the integer read is 0.

Write and test your C code (ex1.c) first, then write and test your assembly code (ex1.asm) using your own inputs, as well as sample input files provided. For this assignment, all your assembly code must be in the same file (ex1.asm), with the code for main at the top, and the code for a_to_i pasted below it. We will learn how to work with multiple source files in the next lab assignment.

Exercise 2: Computing the factorial of a number iteratively

In this exercise, you are to write a non-recursive (i.e., simple iterative) implementation of a function factorial() that computes the factorial of N (i.e., N!), using the following definition:

This function takes in a single integer and will return an integer result. 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. Please do not implement using recursion; that will be the topic of the next exercise!

Starter files are provided: ex2.c and ex2.asm.

First implement this function in C. Keep in mind the following:

Add this function to your code from Exercise 1, and call the file ex2.c. Your program should do the following:

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

Once your C code is working correctly, write the equivalent MIPS assembly program (ex2.asm), that does the same. That is, your main procedure must repeatedly read a string from the input using syscall 8, then call procedure a_to_i to convert it to an integer, then call factorial to compute the factorial, and finally use syscall 1 to print the result. The program should terminate when the integer read is 0, but after computing and printing its factorial value (=1).

Once again, all your assembly code must be within one file; name it ex2.asm, with the code for main on top. Test it using your own inputs, and also the sample inputs provided.


Exercise 3: Computing the factorial of a number recursively

C version

In this exercise, you are to write a recursive implementation of a function factorial() that computes the factorial of N, i.e., N!, using the following definition:

This function takes in a single integer and will return an integer result. All other assumptions Exercise 2 still hold, except that the implementation of the factorial function should be recursive. A non-recursive implementation of the function will receive zero credit.

First implement this function in C. Keep the rest of the program from Exercise 2 as is. That is:

Name the file with your C code ex3.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 (ex3.asm), that does the same. Since you are now 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_basic_template.asm) and for other procedures (proc_basic_template.asm). These assume that no procedure call needs more than 4 arguments, and that any local variables are placed in registers, to simplify the assembly coding. These templates generally correspond to the example on Slide 38 of Lecture 8. For now, all your assembly code must be within one file; simply copy-and-paste your procedures below main.

Once again, all your assembly code must be within one file; name it ex3.asm. Test it using your own inputs, and also the sample inputs 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 Friday, November 10.

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

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

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


3 November 2017, Montek Singh, montek@cs.unc.edu