P7: Printing A Number Using Recursion In LC3

See Progress page for due date

The Assignment

This assignment has three objectives:

To learn how to write an LC3 assembly language program of significant size,
to extend your familiarity with the LC3 instruction set,
and to further your understanding of pointers and how the stack is used for function calls.

You will need to complete a LC3 assembly language program and write three functions. If you correctly implemented the C version of this assignment (very similar to the second programming assignment P2), you will simply need to convert the C code you wrote to assembly language. You will be the compiler. You will find it useful to use your C version as an "oracle" that can give you the correct answers so that you easily test this version with many different test cases.

The Stack Protocol

The following outline is the protocol for passing arguments to a function and returning values. Everything is stored on the runtime stack so that space is used only when the function is executing. As a result the actual address of arguments and locals may change from call to call. However, the layout of the stack frame (activation record) is constant. Thus, the offests from the frame pointer (FP) to the parameters/locals are constant. All parameters and locals are accessed using LDR/STR with fixed offsets from the frame pointer. The stack pointer (SP) changes as the function is called and after the call (and caller cleanup) returns to the same value as before the call started.

Since a stack in a LIFO data structure, the caller/callee code is symmetric. The caller setup/cleanup is the first/last code executed. And the callee setup/cleanup is the first/last code of the function.

caller setup
1. caller pushes the arguments from righ to left. This results in the left most argument being on the top of the stack when JSR is executed.
2. caller executes JSR

callee setup
1. callee makes space for return value (if any) by decrementing SP (R6)
2. callee save the return address (R7) by pushing it onto stack
3. callee save caller's frame pointer (R5) by pushing it onto stack
4. callee sets the frame pointer (R5) to the address of the first local
5. callee makes space for the locals by decrementing SP (R6)

callee executes code for function

callee cleanup
1. callee stores return value (if any)
2. callee removes local variables by incrementing SP (R6)
3. callee pops caller's frame pointer (R5) to restore it
4. callee pops return address (R7) to restore it
5. callee executes RET

caller cleanup
1. caller pops/stores return value (if there is one)
2. caller removes arguments by incrementing SP (R6)

Stack Frame For `divRem(), printNum(), getDigit()`

Study the C header for these functions (also found in the Files tab). Since two function are void, no space for a return value is allocated. Each figure represents the stack frame after the callee has completed the setup and is ready to begin execution (callee step 3). Make sure you can correlate the sequence of steps in the subroutine call with the the diagram and you understand how the stack frame is built up a little bit at a time.

These stack frames assume that there is a single local for divRem, two locals for printNum() and no local for getDigit(). The notation (N/A) represents a memory location that is not used.


lo             divRem()                            printNum()                             getDigit()
^           +==================+              +==================+                   +==================+
|  FP --> 0 | negDenominator   | <-- SP    -1 | remainder        | <-- SP  FP -->  0 |    N/A           |
|           |------------------|              |------------------|                   +==================+
|        +1 | caller's FP      |     FP --> 0 | quotient         |                +1 | caller's FP      | <-- SP
|           |------------------|              |------------------|                   |------------------|
         +2 | return address   |           +1 | caller's FP      |                +2 | return address   |
            |------------------|              |------------------|                   |------------------|
mem      +3 | numerator        |           +2 | return address   |                +3 | return val       |
addr        |------------------|              |------------------|                   |------------------|
         +4 | denominator      |           +3 | x                |                +4 | val              |
|           |------------------|              |------------------|                   +==================+
|        +5 | ptr to quotient  |           +4 | base             |
|           |------------------|              +==================+
|        +6 | ptr to remainder |
v           +==================+
hi

Combined Stack Frames

You should draw picture(s) that show the state of the stack when printNum() calls divRem() and when it calls itself recursively. In the box labeled caller's FP, draw arrows to show where the pointer points to. Similarly, draw arrow to show where the pointer parameters in divRem() point to. While this is not required, making these drawings will help you understand how to write the code and how to debug your code. Here is a blank form you can print and fill in..

Writing the LC3 code

You are now ready to implement the LC3 version of this code. Start with this the file printnum.asm. You may also want to grab Makefile. Implement one function at a time. The easiest one is getDigit(), followed by divRem(). You may NOT add any additional variables to the code beyond those in the supplied code. All data MUST be stored on the stack. The only variables your code may access by name are negSign and digits.

Like previous LC3 programs, test values will be stored in memory locations. To execute the program, set values as follows before stepping/continuing the program:

option = 0 - execute printNum() (data1 = number, data2 = base). When the program halts, the number is printed.
option = 1 - execute getDigit() (data1 = value). When the program halts, the ASCII digit is printed.
option = 2 - execute divMod() (data1 = numerator, data2 = denominator). When the program halts, the quotient/remainder are in data1/data2.

You may NOT use the variables data1/data2 in your code, nor may you created additional variables using .BLKW/.FILL.

This is a complex program, though it does not contain that many lines of code. The complexity comes from understanding how the stack is used in fucntion calls. You should do incremental development and thoroughly test each section of code as you write it. A good place to start is the function getDigit(). Since the callers setup/cleanup is provided for you in the testing section, you might first write the callee's setup/cleanup code. This is very mechanical if you follow the outline provided earlier. Test it by stepping through the code. You should observe the caller pushing arguments and getting the return value off the stack. You should observe the callee completing the setup and completing the cleanup. Your function doesn't do anything at this point except the setup/cleanup. A check is to verify that the stack pointer (R6) has returned to its original value.

Now you can begin to write the actual code for getDigit(). You may find it useful to get a pointer to digits using the LC3 instruction LEA. Given the pointer and the parameter, you can easily access the ASCII code corresponding to the parameter. Recall the relationship between array access (array[index]) and pointer arithmetic (*(array + index)). A reference implementation contined 17 lines of code including blank lines. Setup/cleanup code was 7 lines.

Next you will want to work on divRem(). This code contains a loop to subtract the divisor from the numerator until the quotient and remainder are found. The tricky thing is the pointer variables. The value of a pointer variable is the address where a value is located. The C code *pointer will generate two LC3 instructions. First, you will need a LDR instruction to get the value of the pointer. This will be followed by a LDR/STR to get/set the value at that address. A reference implementation contained 43 lines of code including blank lines. Setup/cleanup code was 7 lines.

Finally, you work on printNum(). You might first write the code to print numbers that only require a single digit. Such test cases will not require any recursive calls, nor a call to divRem(). Once that code is complete, add the call to divRem(). Test with numbers where the quotient is 0 (i.e. single digit numbers). Finally, add the recursion to handle multiple digit numbers. A reference implmentation required 49 lines of code including blank lines. Setup/cleanup was 17 lines.

Assignment Submission

Submit the single file printnum.asm to the Checkin tab of the course website. Alternatively, from a terminal execute:


   ~cs270/bin/checkin P7 printnum.asm