;;; Shreyas Vaidya
;;; 115415522
;;; shreyasv

;;; Implementation that computes the nth fibonacci number.

    .global isqrt                 ; exposes fib as a label for the linker
isqrt:                            ; the label: the next instruction starts isqrt()
    ;; Add your code here.
    cpi r24, 2          ; comparing n with 2
    brlo 2f         ; if n < 2, branch to 2
    movw r18, r24       ; r18 contains n (storage)
    lsr r24         ; shifts n one byte right
    lsr r24         ; shifts n one byte right
    mov r22, r24        ; moves n>>2 passed as parameter to r22
    mov r23, r25        ; ^same but with high byte
    push r23        ; push high byte, which contains n>>2
    push r22        ; push low byte, which contains n>>2
    call isqrt      ; recursive call for isqrt
    pop r22         ; pops value from recursive call to r22
    pop r23         ; ^same but with high byte
    lsl r24         ; shifts n one byte left
    mov r22, r24        ; moves isqrt(n>>2)<<1 passed to r22
    mov r23, r25        ; ^same but with high byte
    mov r20, r22        ; storage for large (for mult)
    mov r21, r23        ; ^same but with high byte
    inc r20         ; increments small & stores in large
    mul r20, r20        ; large * large
    mov r20, r0     ; mult gets stored in r0, moved to r20
    clr r1          ; clears r1 register (stored mult)
    cp r18, r20     ; if(n < large * large)
    brlo 3f         ; jumps to 3f
    cp r18, r20     ; if(n < large * large)
    brge 4f         ; jumps to 4f

2:  clr r25         ; returns n & clears
    jmp 1f

3:  movw r24, r22       ; returns small
    jmp 1f

4:  inc r22         ; increments small by 1, which is large
    movw r24, r22       ; returns large
    jmp 1f

1:
    ret                     ; returns.  necessary.