Lc3 assembly code and stack

Question

I have the following LC-3 assembly file fib.asm by translating the given C function fib into the equivalent assembly. The idea is to  not attempt to optimize your function. Take a literal approach to translating the C function fib.c as it is givien. I need to write the program which simulates Real time stack as given below for f(3). Can you please help me get the same RTS as given below. I am including the fib.asm and main.asm code.

int fib(int n) {

   int a, b;

   if (n <= 0) {

       return 0;

   }

   else if (n == 1) {

       return 1;

   }

   else {

       a = fib(n - 1);

       b = fib(n - 2);

       return a + b;

   }

}

Fib.asm

.ORIG x4000

FIBFN   ADD R6, R6, #-1 ; Push space for ret. val.

       ADD R6, R6, #-1 ; push the return address

             STR R7, R6, #0

                 ADD R6, R6, #-1 ; Push the dynamic link.

                 STR R5, R6, #0

                 ADD R5, R6, #-1 ; Set the frame pointer.

                 ADD R6, R6, #-1 ; space for a

                 ADD R6, R6, #-1 ; space for b

                 LDR R0, R5, #4 ; Load "n" into R0.

                 BRnz FIB_NEG_ZERO ; If negative or zero...

                 ADD R0, R0, #-1

       BRz FIB_ONE

   

       LDR R0, R5, #4 ; read parameter n

       ADD R0, R0, #-1 ; calculate n-1

       ADD R6, R6, #-1 ; push n-1

       STR R0, R6, #0

       JSR FIBFN ; call self

       LDR R0, R6, #0 ; pop return value

       ADD R6, R6, #1

       STR R0, R5, #-1 ; store a in temp

       

       LDR R0, R5, #4 ; read parameter n

       ADD R0, R0, #-2 ; calculate n-2

       ADD R6, R6, #-1 ; push n-2

       STR R0, R6, #0

       JSR FIBFN ; call self

       LDR R0, R6, #0 ; pop return value

       ADD R6, R6, #1

       STR R0, R5, #-2 ; store b in temp

       

       LDR R1, R5, #-1 ; read temp

       ADD R0, R0, R1 ; Fibonacci(n-1) + Fibonacci(n-2)

       BRnzp FIB_END ; all done

FIB_NEG_ZERO AND R0, R0, #0 ; base case – return 0

   BRnzp FIB_END

       

FIB_ONE ADD R0, R0, #1 ; base case – return 1

   BRnzp FIB_END

FIB_END STR R0, R5, #3 ; write return value (R0)

       ADD R6, R5, #1 ; pop local variables

       ADD R6, R5, #1 ; pop local variables

       LDR R5, R6, #0 ; pop dynamic link

       ADD R6, R6, #1

       LDR R7, R6, #0 ; pop return address

       ADD R6, R6, #1

       RET

.END

Main.asm

       .ORIG x3000

; int main(void)

; NOTE: Do not alter this function.

MAINFN LD R6, INITSP ; Init. the stack pointer.

       ADD R5, R6, #-1 ; Init. the frame pointer.

       ADD R6, R6, #-1 ; Push space for "n".

       LEA R0, PROMPT ; Print the prompt.

       PUTS

       GETC           ; Read an integer.

       OUT

       LD R1, INTNEG

       ADD R0, R0, R1

       STR R0, R5, #0 ; Assign the integer to "n".

       GETC           ; Consume the newline.

       OUT

       LDR R0, R5, #0 ; Push "n".

       ADD R6, R6, #-1

       STR R0, R6, #0

       LD R4, FIBFN

       JSRR R4        ; Call "fib".

       LDR R1, R6, #0 ; Pop the return value.

       ADD R6, R6, #1

       ADD R6, R6, #1 ; Pop "n".

       LEA R0, RES1   ; Print the result.

       PUTS

       LD R2, INTPOS

       LDR R0, R5, #0

       ADD R0, R0, R2

       OUT

       LEA R0, RES2

       PUTS

       ADD R0, R1, R2

       OUT

       LD R0, NEWLINE

       OUT

       ADD R6, R6, #1 ; Pop "n".

       HALT

INITSP .FILL xFE00

PROMPT .STRINGZ "Enter an integer: "

RES1   .STRINGZ "f("

RES2   .STRINGZ ") = "

INTPOS .FILL x30

INTNEG .FILL x-30

NEWLINE .FILL x0A

FIBFN  .FILL x4000

       .END

Answer 1

Honestly, It has a few stack-frame bugs. That fib example? It’s not about Fibonacci.

It’s about how a system manages memory and control flow when things get recursive and messy, happens.

To your question though.

plain truth first: the fib.asm you posted will not give a clean RTS for fib(3) as written. It has a few stack-frame bugs.

The main ones are:

1. Your frame offsets don’t match your frame-pointer setupYou use R5,#4 for n and R5,#3 for return value
2. That part is fine only if you treat locals carefully
3. But then you store a at R5,#-1 and b at R5,#-2, which does not match the way you built the frame
4. You never pop the argument after each recursive call After JSR FIBFN, the callee leaves the return value on top of stack
5. You pop that
6. But the argument you pushed (n-1 or n-2) is still sitting there
7. Your epilogue is wrong

ADD R6, R5, #1

ADD R6, R5, #1

1. is not right
2. You only reset the stack once, then restore old R5, then old R7