Question

LC-3 Programming Help!!

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.

1. 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
2. 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)
3. callee executes code for function
4. 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
5. 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 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 variable 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. 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 implmentation required 49 lines of code including blank lines. Setup/cleanup was 17 lines.

*********************************************************************************************************************************************************************************************************************

printnum.asm:

; ------------------------------------------------------------------------
; Begin reserved section - do not change ANYTHING is this section

               .ORIG x3000
               BR Main

option         .BLKW 1          ; select routine to test
data1          .BLKW 1          ; use ONLY for testing
data2          .BLKW 1          ; use ONLY for testing

stackBase      .FILL X4000      ; initial sttack pointer

Main           LD R6,stackBase  ; initialize stack pointer
               LD R0,option     ; select routine to test
               BRZ testPrintNum ; option = 0 means test printNum

               ADD R0,R0,#-1
               BRZ testGetDigit ; option = 1 means test getDidit

               ADD R0,R0,#-1
               BRZ testDivRem   ; option = 2 means test divRem

               HALT             ; invalid option if here

testPrintNum                    ; call printNum(x, base)
               LD R0,data2
               PUSH R0          ; push base argument
               LD R0,data1
               PUSH R0          ; push value argument
               JSR printNum
               ADD R6,R6,#2     ; caller clean up 2 parameters
               BR endTest

testGetDigit                    ; call getChar(val)
               LD R0,data1
               PUSH R0          ; push argument (val to convert to ASCII)
               JSR getDigit     ; 
               POP R0           ; get the corresponding character
               ADD R6,R6,#1     ; caller clean up 1 parameter
               OUT              ; print the digit
               NEWLN
               BR endTest

testDivRem                      ; call divRem(num, denom, *quotient, *remainder)
               LEA R0,data2     ; get pointer to remainder (&data2)
               PUSH R0
               LEA R0,data1     ; get pointer to quotient (&data1)
               PUSH R0
               LD R0,data2
               PUSH R0          ; push demoninator
               LD R0,data1
               PUSH R0          ; push numerator
               JSR divRem       ; call routine
               ADD R6,R6,#4     ; caller clean up 4 parameters

endTest        LEA R0,endMsg
               PUTS
theEnd         HALT             ; look at data1/data2 for quotient/remainder

                                ; useful constants
endMsg         .STRINGz "\nTest complete!\n"

negSign        .FILL    x2D     ; ASCII '-'
digits         .STRINGZ "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" ; up to base 36

; end reserved section

; ------------------------------------------------------------------------
; Author: your name goes here
; ------------------------------------------------------------------------
;
; C declaration: char getDigit (int val);

getDigit                        ; callee setup

                                ; code for getDigit

                                ; callee cleanup
               RET              ; return
; ------------------------------------------------------------------------
;
; C declaration: void divRem(int num, int denom, int*quotient, int*remainder);

divRem                          ; callee setup

                                ; code for dicRem

                                ; callee cleanup
               RET              ; return
; ------------------------------------------------------------------------
;
; C declaration: void printNum (int val, int base);

printNum                        ; callee setup

                                ; code for printNum

                                ; callee cleanup
               RET              ; return
; ------------------------------------------------------------------------
               .END

Answer 1

; ------------------------------------------------------------------------
; Begin reserved section - do not change ANYTHING is this section

               .ORIG x3000
               BR Main

option         .BLKW 1          ; select routine to test
data1          .BLKW 1          ; use ONLY for testing
data2          .BLKW 1          ; use ONLY for testing

stackBase      .FILL X4000      ; initial sttack pointer

Main           LD R6,stackBase ; initialize stack pointer
               LD R0,option     ; select routine to test
               BRZ testPrintNum ; option = 0 means test printNum

               ADD R0,R0,#-1
               BRZ testGetDigit ; option = 1 means test getDidit

               ADD R0,R0,#-1
               BRZ testDivRem   ; option = 2 means test divRem

               HALT             ; invalid option if here

testPrintNum                    ; call printNum(x, base)
               LD R0,data2
               PUSH R0          ; push base argument
               LD R0,data1
               PUSH R0          ; push value argument
               JSR printNum
               ADD R6,R6,#2     ; caller clean up 2 parameters
               NEWLN
               BR endTest

testGetDigit                    ; call getChar(val)
               LD R0,data1
               PUSH R0          ; push argument (val to convert to ASCII)
               JSR getDigit     ;
               POP R0           ; get the corresponding character
               ADD R6,R6,#1     ; caller clean up 1 parameter
               OUT              ; print the character
           NEWLN
               BR endTest

testDivRem                      ; call divRem(num, denom, *quotient, *remainder)
               LEA R0,data2     ; get pointer to remainder (&data2)
               PUSH R0
               LEA R0,data1     ; get pointer to quotient (&data1)
               PUSH R0
               LD R0,data2
               PUSH R0          ; push demoninator
               LD R0,data1
               PUSH R0          ; push numerator
               JSR divRem       ; call routine
               ADD R6,R6,#4     ; caller clean up 4 parameters

endTest        LEA R0,endMsg
               PUTS
theEnd         HALT             ; look at data1/data2 for quotient/remainder

                                ; useful constants
endMsg         .STRINGz "Test complete!\n"

negSign        .FILL    x2D     ; ASCII '-'
digits         .STRINGZ "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" ; up to base 36

; end reserved section

; ------------------------------------------------------------------------
; Author: Sean Russell
; ------------------------------------------------------------------------
;
; C declaration: char getDigit (int val);

getDigit        ADD R6,R6,#-1    ; callee setup
       PUSH R7
       PUSH R5
       ADD R5,R6,#0

       LDR R2,R5,#3   ; code for getDigit
       LEA R3,digits
       ADD R2,R3,R2
       LDR R7,R2,#0

       STR R7,R5,#2   ; callee cleanup
       POP R5
       POP R7
                  RET             ; return

; ------------------------------------------------------------------------
;
; C declaration: void divRem(int num, int denom, int*quotient, int*remainder);

divRem            ADD R6,R6,#-1    ; callee setup
       PUSH R7
       PUSH R5
       ADD R5,R6,#0

                LDR R3,R5,#3    ; remainder pointer
       LDR R2,R5,#4   ; quotient pointer
       LDR R1,R5,#5   ; divisor
       LDR R0,R5,#6   ; numerator
       .ZERO R4   ; *quotient = 0
       STR R4,R1,#0
divRemLoop   NOT R4,R2   ; while (numerator >= divisor)
       ADD R4,R4,#1
       ADD R4,R4,R3
       BRn divRemExit
       ADD R3,R4,#0   ; numerator = numerator - divisor;
       LDR R4,R1,#0   ; *quotient = *quotient + 1;
       ADD R4,R4,#1
       STR R4,R1,#0
       BR divRemLoop
divRemExit   STR R3,R0,#0   ; *remainder = numerator

                STR R7,R5,#2   ; callee cleanup
       POP R5
       POP R7
                  RET              ; return
; ------------------------------------------------------------------------
;
; C declaration: void printNum (int val, int base);

;void printNum (int x, int base) {
; int q = 0;
; int r = 0;
; divRem (x,base,&q,&r);
; if (q<=0) {
;    putchar(getDigit(r));
;    return;
; }
; printNum(q,base);
; putchar(getDigit(r));
;}

printNum        ADD R6,R6,#-1    ; callee setup
       PUSH R7
       PUSH R5
       ADD R5,R6,#0

       LDR R0,R5,#3   ; x
       LDR R1,R5,#4   ; base

       ADD R6,R6,#-2   ; allocate two local variables
       .ZERO R2
       STR R2,R5,#-1   ; int q = 0;
       STR R2,R5,#-2   ; int r = 0;

       ADD R2,R5,#-1   ; &q
       ADD R3,R5,#-2   ; &r

       PUSH R3       ; divRem (x,base,&q,&r)
       PUSH R2
       PUSH R1
       PUSH R0
       JSR divRem
       ADD R6,R6,#4

       LDR R0,R5,#-1   ; if (q<=0)
       BRp recurse
      
       LDR R1,R5,#-2   ; putchar(getDigit(r));
       PUSH R1
       JSR getDigit
       POP R0
       OUT
       ADD R6,R6,#1
       BR exit       ; return

recurse       LDR R0,R5,#-1   ; printNum(q,base);
       LDR R1,R5,#4
       PUSH R1
       PUSH R0
       JSR printNum
       ADD R6,R6,#3

       LDR R1,R5,#-2   ; putchar(getDigit(r));
       PUSH R1
       JSR getDigit
       POP R0
       OUT
       ADD R6,R6,#1
       BR exit

exit       ADD R6,R6,#3          
       STR R7,R5,#2   ; callee cleanup
       POP R5
       POP R7
                 RET              ; return
; ------------------------------------------------------------------------
               .END