/*************************
 * COSC 065 Fall 2006    *
 * Fibonacci Demo        *
 * D.W. Brylow           *
 *************************/
	
#include <cosc065.h>

.rodata

FMT:	.string "%d\n"

.text
.globl main

main:
        /* Function prolog. */
        /* Sets up environment for user program to execute. */
        stwu    r1,-32(r1)  /* Make room on Stack for O/S values.  */
        mflr    r0          /* Store O/S return address on Stack.  */
        stw     r0,36(r1)
        stw     r31,28(r1)  /* Store O/S frame pointer on Stack.   */
        mr      r31,r1      /* new stack top is now frame pointer. */

        /* Start of your program. */
loop:
	bl	getInt
	cmpwi	r3, 0	    /* Watch for EOF.                      */
	blt	done

	bl	fib

	mr	r4, r3      /* Print out integer result.           */
	lis	r3, FMT@ha
	addi	r3, r3, FMT@l
	bl	printf

	b	loop	
done:

        /* End of your program. */

        /* Function epilogue. */
        /* Restores the environment from the O/S. */
	mr	r1, r31     /* Discard stack below frame pointer.  */
	lwz	r31,28(r1)  /* Restore O/S frame pointer.          */
	lwz	r0, 36(r1)
	mtlr	r0          /* Restore O/S return address.         */
	lwz	r1, 0(r1)   /* Restore O/S Stack pointer.          */
	li r3, 0            /* Return value of 0 (normal exit).    */
        blr                 /* Return to Operating System.         */


/*******************
 * Fib function
 *******************/

        /* Need room for:
         *   parent SP    0(FP)
	 *   child  LR    4(FP)
         *   param 'n'    8(FP)
         *   temp1       12(FP)
         *   temp2       16(FP)
         *   parent FP   28(FP)
         *   parent LR   36(FP)  (Actually in parent's record)
         * 6 words * 4 bytes = 24 bytes.   Round up to 32 (multiple of 16)
         * Frame Size (size of Activation Record) = 32
         *
         * ACTIVATION RECORD LAYOUT  for function fib
         *
         *    +---------+
         * 36 |LR_parent|
         *    +---------+        ^
         * 32 |SP_old   |        |  parent's stack frame
         *    +---------+ -------+
         * 28 |FP_parent|
         *    +---------+
         * 24 |  ?      |
         *    +---------+
         * 20 |  ?      |
         *    +---------+
         * 16 |  temp2  |
         *    +---------+
         * 12 |  temp1  |
         *    +---------+
         *  8 |  x      |
         *    +---------+
         *  4 |LR_child |
         *    +---------+        ^
         *  0 |SP_parent|        |  fib's stack frame
         *    +---------+ -------+  <--- FP_fib
         */


fib:				/* PROLOG: Build stack frame.   */
	stwu 	r1, -32(r1)	/* Allocate stack frame.        */
	mflr	r0		/* Save link register           */
	stw	r0, 36(r1)	/*  in parent's stack frame.    */
	stw	r31, 28(r1)	/* Save frame pointer.          */
	mr	r31, r1		/* Set new frame pointer.       */
                                /* PROLOG END                   */

	cmpwi	r3, 1		/* Recursive base case.         */
	ble	fibdone		/*  If (n == 1) return n.       */

	stw	r3, 8(r31)	/* Preserve n in stack frame.   */
	subi	r3, r3, 1	/* Calculate (n - 1)            */
	bl	fib		/* Recursive fib(n - 1)         */
	stw	r3, 12(r31)	/* temp1 = fib(n - 1)           */

	lwz	r3, 8(r31)	/* Get pristine n from frame.   */
	subi	r3, r3, 2	/* Calculate (n - 2).           */
	bl	fib		/* Recursive fib(n - 2).        */
	stw	r3, 16(r31)	/* temp2 = fib(n - 2).          */

	lwz	r3, 12(r31)	/* Add together temp1 and temp2 */
	lwz	r4, 16(r31)
	add	r3, r3, r4

fibdone:			/* EPILOGUE: Tear down frame.   */
	mr	r1, r31		/* Reset SP to equal FP.        */
	lwz	r31, 28(r1)	/* Restore parent FP.           */
	lwz	r0, 36(r1)	/* Restore parent LR.           */
	mtlr	r0
	lwz	r1, 0(r1)	/* Restore parent stack.        */
	blr			/* Return to parent function.   */
                                /* EPILOGUE END                 */



/*******************
 * getInt
 * Calls getchar repeatedly to read in characters from
 *  the O/S which are interpreted as a multi-digit,
 *  positive integer.  Filters out unwanted non-digits.
 * Returns EOF if end of file reached.
 *******************/

        /* Need room for:
         *   parent SP    0(FP)
	 *   child  LR    4(FP)
         *   old r13      8(FP)
         *   parent FP   12(FP)
         *   parent LR   20(FP) (Actually in parent's record)
         * 4 words * 4 bytes = 16 bytes.   Round up to 16 (multiple of 16)
         * Frame Size (size of Activation Record) = 16
         *
         * ACTIVATION RECORD LAYOUT  for function getInt
         *
         *    +---------+
         * 20 |LR_parent|
         *    +---------+        ^
         * 16 |SP_old   |        |  parent's stack frame
         *    +---------+ -------+
         * 12 |FP_parent|
         *    +---------+
         *  8 | old r13 |
         *    +---------+
         *  4 |LR_child |
         *    +---------+        ^
         *  0 |SP_parent|        |  getInt's stack frame
         *    +---------+ -------+  <--- FP_getInt
         */

#define TOTAL r13

getInt:				/* PROLOG: Build stack frame.   */
        stwu    r1, -16(r1)	/* Allocate stack frame.        */
        mflr    r0		/* Save link register           */
        stw     r0, 20(r1)	/*  in parent's stack frame.    */
        stw     r31, 12(r1)	/* Save frame pointer.          */
        mr      r31, r1		/* Set new frame pointer.       */
                                /* PROLOG END                   */

	stw	TOTAL, 8(r31)	/* Save TOTAL in record, so that*/
				/*  parent function doesn't have*/
				/*  to steer clear of r13.      */

	li	TOTAL, 0	/* Initialize grand total.	*/
	
giloop:
        bl      getchar		/* Get a character from O/S.	*/
        cmpwi   r3, 0		/* Check for EOF.		*/
        blt     gieof
        cmpwi   r3, '0'		/* Check for non-digits.	*/
        blt     gidone
        cmpwi   r3, '9'
        bgt     gidone

        subi    r3, r3, '0'	/* Subtract ASCII offset of '0'.*/
				/* Horner's Algorithm.		*/
        mulli   TOTAL, TOTAL, 10
        add     TOTAL, TOTAL, r3
        b       giloop
gidone:
	mr	r3, TOTAL	/* Return value in r3, like all	*/
				/*  good functions.		*/
gieof:				/* EPILOGUE: Tear down frame.   */
	lwz	TOTAL, 8(r31)	/* Restore parent r13 value.	*/
	mr      r1, r31         /* Reset SP to equal FP.        */
        lwz     r31, 12(r1)     /* Restore parent FP.           */
        lwz     r0, 20(r1)      /* Restore parent LR.           */
        mtlr    r0
        lwz     r1, 0(r1)       /* Restore parent stack.        */
        blr                     /* Return to parent function.   */
                                /* EPILOGUE END                 */
