Lab 8: String Processing and Recursion

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.

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.

• The name and type declaration of the function you create must be: int a_to_i(char* str)
• You cannot use the built-in scanf("%d",...) function to read the integer from the input. You must read it as a string using fgets(), and then parse it using your own a_to_i() function.
• For the purpose of using fgets(), you may assume that the input string will not be longer than 20 digits. For the purpose of parsing its value, you may assume that the final numerical value will not be larger than what can fit in an int variable.
• You cannot use the built-in atoi() function that is part of the C library. You must write your own function!
• Hint: Your function should traverse the string one character at a time, from left to right, and construct the integer value using successive multiplications by 10 and additions, until the end of the string is reached. (The input will never contains strings that are overly long.)
• For printing the value read and parsed, you should use printf("%d\n",...).

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.

• Tip: Convert your C program line-by-line to its assembly equivalent. Doing it any other way will take you much longer.
• You cannot use syscall 5 to read an integer from the input. You must read a string and parse it using your own function a_to_i.
• For printing the value read and parsed, you should use syscall 1 to print the integer.
• You must follow all of the procedure calling conventions discussed in class. Specifically, the address of the string read by main must be passed to a_to_i in register $a0, and the resulting integer value must be returned in register $v0.
• You have a lot of leeway in choosing the registers used by main and a_to_i to do their work, 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.
• For this part, if you think you do not need to save $ra on the stack because a_to_i is a "leaf" procedure, that is okay, although you are encouraged to always save $ra on the stack in every procedure you write. You do not need to save/restore $fp and $gp because you will likely not be needing them.

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.

Exercise 2: Computing the factorial of a number

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:

• factorial(0) = 1
• factorial(N) = N * factorial(N-1)

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. A non-recursive implementation of the function will receive zero credit.

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

• The function must have the following name and type: unsigned int factorial(unsigned int n)
• Points will be deducted if the return type of factorial is not unsigned int.

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

• As before, main() procedure repeatedly reads a string from a line of input, and calls a_to_i() to convert it to an integer.
• Then, main() calls factorial to compute the factorial of this number.
• Finally, main() uses printf("%d\n",...) to print the factorial.
• These steps are repeated until a 0 value is read by main, its factorial (=1) computed and printed, and then the program terminates.

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, 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).

• Tip: Convert your C program one line-by-line to its assembly equivalent. Doing it any other way will take you much longer.
• Be sure to use the unsigned version of multiplication and addition instructions. This way, the value of the largest factorial that fits in a register is doubled! You will lose points if your entire calculation is not unsigned.
• You must follow all of the procedure calling conventions discussed in class. Specifically, arguments must be passed to a_to_i and factorial in register $a0, 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.
• You do not need to save/restore $fp and $gp because you will likely not be needing them. However, $ra, and any temporary registers ($t0-$t9) and saved registers ($s0-$s7) must be saved/restored according to conventions exactly as discussed in class.

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