Programming Assignment P8 - C and LC-3 Recursion

P8A - Due Sunday, Nov. 8 at 10:00pm, late submission at 11:59pm.

P8B - Due Sunday, Nov. 15 at 10:00pm, late submission at 11:59pm.

This assignment has four objectives:

To remember C programming and recursion,

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 C and LC3 assembly programs that consist of three functions. For P8A, write the C code. For P8B, convert it 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.
Here are the source files for the P8A, the C assignment:

printnum.h

printnum.c

testPrint.c

Makefile

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 offsets 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. However, you may use the PUSH/POP instructions that are a shortcut for pushing and popping values to/from the stack. 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 is 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 right 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. 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. 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 you 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 data values as follows before stepping/continuing the program:

option = 0 - test printNum() (data1 = number, data2 = base). When the program halts, the number is printed.
option = 1 - test getDigit() (data1 = val). When the program halts, the ASCII character is printed.
option = 2 - test 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 declare additional variables using .FILL/.BLKW.

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. Then 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 it 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 implementation required 49 lines of code including blank lines. Setup/cleanup was 17 lines.

Grading Criteria

For P8A, there will be no preliminary testing, but a test driver has been provided. Final testing will verify getDigit (10 points), divRem (20 points), and printNum (20 points).

For P8B, there will be preliminary testing for divRem. Final testing will verify getDigit (20 points), divRem (30 points), and printNum (40 points), and will make sure that the stack pointer is save and restored correctly (10 points).

Assignment Submission

For P8A, submit the single file printnum.c using the Checkin tab on the course website. For P8B, submit the single file printnum.asm using the Checkin tab on the course website. Alternatively, from a terminal execute:


   ~cs270/bin/checkin P8A printnum.c


   ~cs270/bin/checkin P8B printnum.asm