fibbonacci.s

# Write a program that calculates the n-th Fibonnaci number without memoization.

    .data
    # 0x400
N:  .word 9
    # 0x404
R:  .word 0

    .text
    # PLAN:
    #  - main loop calls the recurisve function
    #  - the result should be added to the stack and then the top 
    #    two values should be used to calculate the 
    #
    # Function FB:
    #  - a0 contains the return value of the execution.
    #  - a2 takes the current N parameter.
    #  - for n = 0 set a1 to 0 and return
    #  - for n = 1 set a1 to 1 and return
    #  - we need to balance the stack and save the current state there
    
    
    # Setup -----------------------------------------------------------------
    
    lui gp, %hi(N)
    addi gp, gp, %lo(N)
    lw a2, 0(gp)
    
    addi sp, x0, 0x600
    
    # End Setup -------------------------------------------------------------
    
    add gp, x0, x0
    
    # Main ------------------------------------------------------------------
    
    jal ra, Fibb
    
    lui gp, %hi(R) # Save the result from a2 to the result address
    addi gp, gp, %lo(R)
    sw a0, 0(gp)
    
    jal x0, Exit
    
    # Functions -------------------------------------------------------------
    
Fibb:
    # PLAN:
    #  - use t3 for loading utility values
    #  - a0 expects to get a return value
    #  - a2 expect to receive the N parameter
    #  - use s2 to save N and s3 for returned values
    Case0:
        addi t3, x0, 0
        bne a2, t3, Case1
        addi a0, x0, 0
        jr ra
    Case1:
        addi t3, x0, 1
        bne a2, t3, CaseN
        addi a0, x0, 1
        jr ra
    CaseN:
        addi sp, sp, -24
        sw ra, 20(sp)
        sw s0, 16(sp)
        sw s2, 12(sp)
        sw s3, 8(sp)
        addi s0, sp, 24 # Set the current frame pointer
        
        add s2, a2, x0
        
        addi a2, s2, -1 # Calculate Fib(n-1)
        jal ra, Fibb
        add s3, a0, x0
        
        addi a2, s2, -2 # Calculate Fib(n-2)
        jal ra, Fibb
        add a0, s3, a0 # Save the sum to the output.
        
        lw ra, 20(sp)
        lw s0, 16(sp)
        lw s2, 12(sp)
        lw s3, 8(sp)
        addi sp, sp, 24
        
        jr ra
    
Exit:
    add x0, x0, x0