/* Dennis W. Brylow   */
/* COSC 065 Fall 2007 */
/* Fibonacci demo     */
#include <mips.h>

.data

FMT:    .string "%d\r\n"
FMT2:   .string "Fib of %d = %d\r\n"

.text
.globl main

main:
        /* Function prolog.             */
        /* Sets up environment for user program to execute.         */
        addiu   sp, sp, -32  /* Make room on Stack for O/S values.  */
        sw      ra, 28(sp)   /* Store O/S return address on Stack.  */
        /* Start of your program.       */

loop:   
        jal     getInt       /* Get an 'n' value.                   */
        bnez    v1, done     /* Exit when EOF found.                */
        move    a0, v0
        move    s0, v0
        jal     fib          /* Calculate fib(n).                   */
        la      a0, FMT2
        move    a1, s0
        move    a2, v0
        jal     kprintf      /* Printf result.                      */
        b       loop
                
done:   
        /* End of your program.         */
        /* Function epilogue.           */
        /* Restores the environment from the O/S.                   */
        lw      ra, 28(sp)   /* Restore O/S return address.         */
        addiu   sp, sp, 32   /* Restore O/S stack pointer.          */
        li      v0, 0        /* Return value of 0 (normal exit).    */
        jr      ra           /* Return to Operating System.         */


/* Fibonacci function                                               */
/* Parameters: integer n (desired Fibonacci number.)                */
/* Returns:    nth number in Fibonacci sequence.                    */
/* Algorithm:  Check for base case n == 0, or n == 1                */
/*              otherwise return fib(n - 1) + fib(n - 2).           */


fib:    addiu   sp, sp, -32  /* Build activation record for fib.    */
        sw      ra, 28(sp)   /* Save return address on stack.       */
        sw      a0, 32(sp)   /* Save copy of 'n' on the stack.      */

        addi    t0, zero, 1  /* Check for base cases.               */
        beq     a0, zero, fibdone
        beq     a0, t0, fibdone

        addi    a0, a0, -1   /* Call fib(n - 1).                    */
        jal     fib
        sw      v0, 20(sp)   /* Save result of first call on stack. */
        lw      a0, 32(sp)   /* Get 'n' back from stack.            */
        addi    a0, a0, -2  
        jal     fib          /* Call fib(n - 2).                    */
        lw      t0, 20(sp)
        add     a0, v0, t0   /* Add fib(n - 1) to fib(n - 2).       */
fibdone:
        move    v0, a0       /* Move answer to result register.     */
        lw      ra, 28(sp)   /* Restore return address from stack.  */
        addiu   sp, sp, 32   /* Reclaim activation record.          */
        jr      ra           /* Return from whence we came.         */


/* getInt function                                                  */
/* Parameters: none                                                 */
/* Returns:    v0 contains signed integer read from input.          */
/*             v1 contains flag, 1 for EOF, 0 normally.             */
/* Algorithm:  Check for minus sign, then use Horner's Method to    */
/*             build up value.                                      */
/*             Discard non-digits, break on newline.                */
/*             Multiply final magnitude by sign value.              */


#define EOF   4   /* Integer value of ASCII 'EOF' character.        */
#define TOTAL s7
#define MINUS s6
#define CHAR  t9
#define RETRN 28  /* Activation record offset for return value.     */
                
getInt:
        addiu   sp, sp, -32  /* Create activation record.           */
        sw      ra, RETRN(sp) /* Save return address on stack.      */
        sw      TOTAL, 24(sp) /* Save callee-save registers.        */
        sw      MINUS, 20(sp) /* Save callee-save registers.        */

        move    TOTAL, zero  /* Initialize total to 0.              */
        li      MINUS, 1     /* Init minus flag to 1 (identity).    */

        jal     getchar      /* Get first character.                */
        li      t0, '-'      /* Check for literal ASCII minus sign. */
        bne     t0, v0, gt2  /* IF there is NOT a minus, jump into  */
        li      MINUS, -1    /*  main loop, otherwise invert flag.  */
gtlp:
        jal     getchar         
gt2:    move    CHAR, v0     /* Save last character read.           */

        li      t3, EOF
        li      t2, '\n'
        li      t0, '0'
        li      t1, '9'

        beq     CHAR, t3, gtdn2 /* IF EOF, jump to gtdone2.         */
        beq     CHAR, t2, gtdn  /* IF newline, jump to gtdone.      */
        blt     CHAR, t0, gtlp  /* IF less than '0', try again.     */
        bgt     CHAR, t1, gtlp  /* IF greater than '9', try again.  */
        
        li      t0, '0'      /* Subtract value of ASCII '0' to      */
        sub     CHAR, CHAR, t0  /*  get actual numeral value.       */

        li      t0, 10       /* Horner's Method.  Multiply total by */
                             /*  base, add in next digit.           */
        mul     TOTAL, TOTAL, t0        
        add     TOTAL, TOTAL, CHAR

        b       gtlp

gtdn2:  addi    v1, zero, 1  /* Signal EOF to calling function.     */
        b       gtdn3
                
gtdn:                        /* Multiply by minus flag.             */
        mul     v0, TOTAL, MINUS
        move    v1, zero     /* Clear EOF flag.                     */
gtdn3:  lw      ra, RETRN(sp)
        lw      TOTAL, 24(sp)
        lw      MINUS, 20(sp)
        addiu   sp, sp, 32   /* Restore regs, restore stack.        */
        jr      ra