Goals For this assignment you will write programs in C and LC-3 assembly code. Both programs will perform the identical recursive algorithm. The goals of this programming assignment are:

1. To solidify your understanding of the stack memory model.

2. To understand how recursion is implemented in C and at the assembly level.

3. To extend your assembly coding skills.

The Assignment

STEP ONE: C Program

Write a C program called pa7.c that prints a 16-bit hexadecimal number that is input by the user. The number must be positive, meaning it must be in the range 0x0000 to 0x7fff. Use the recursive algorithm described in this document. First, implement a main program that inputs a hexadecimal number (%x) from the user and calls the following function to print it:

void printHexNumber(unsigned int iValue);

The program should print an error when the value is out of the range shown above. You cannot use any C print functions such as printf or sprintf. Instead, implement the print function so that when the input value is less than 16, the single ASCII character for the input value is printed. Print "0" to "9" for the values 0 to 9, and "a" to "f" for the values 0xA to 0xF. If the value exceeds 16, make a recursive call to printHexNumber() with a parameter equal to the input value divided by 16. After the recursive call, print the modulo 16 of the input value, i.e. the last digit of the number. Test your program with at least the input values 0x1234, 0x6789, 0x789a, and 0x3bcf. Make sure that the output has only lowercase letters. You should also implement a function to print a single hex digit, with the following prototype:

void printHexDigit(unsigned int iDigit);

The only code required for the C program are the main entry point and the two functions shown. Please do not use any global variables.

STEP TWO: LC-3 Program

Convert the pa7.asm example program from an iterative method to a recursive method. The PRINT function must be modified to call itself in exactly the same manner as the C program from the previous step. The program which you have been given implements a function called OUTPUT that outputs a hexadecimal digit and another function called DIVIDE that divides the numerator by a power of two denominator. You may use these functions in your code. Please leave the initial data value in address x3001 so that we can test your program. No error handling is required in the assembly program, so the input data value must be between 0x0000 and 0x7fff.

Your modified PRINT function must follow the stack protocol shown below, which is the one used by the LC-3 C compiler:

1. The caller pushes parameters onto the stack.

2. The callee makes room for the return value, if one exists.

3. The callee pushes the return address of the caller from R7.

4. The callee pushes the frame pointer of the caller from R5.

5. The callee sets up its own frame pointer.

6. The callee executes its function code.

7. The callee stores the return value, if one exists, onto the stack.

8. The callee pops the frame pointer of the caller to R5.

9. The callee pops the return address of the caller to R7.

10. The callee returns using the RET command.

11. The caller pops the return value, if one exists, off the stack.

12. The caller cleans up the stack to remove the parameters it pushed.

This stack protocol is shown in the functions provided in pa7.asm. Changes should be required only to the PRINT function for this assignment. We recommend that you completely understand the provided code before you make changes. This assignment does not require very many lines of code, but you will have to make the modifications carefully. During lab hours we will be glad to explain the provided code, but we will not show you how to modify the code for the assignment.