/*
 * COSC 065 - Hardware Systems
 * Fall 2005
 * D.W. Brylow 
 * Lecture 19 deomonstration
 * A recursive Fibonacci function with activation record.
 */
#include <cosc065.h>

.rodata
FMT:	.string "fibonacci(%d) = %d\n"
	
.text
.globl main

#define X r15

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. */

loopmain:	
	bl	getInt
	mr	X, r3
	cmpwi	r3, -1
	beq	done
	bl	fib
	mr	r5, r3
print:	
	lis	r3, FMT@ha
	addi	r3, r3, FMT@l
	mr	r4, X
	bl	printf
	b	loopmain
	
        /* End of your program. */

done:	
        /* 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.         */


	
/**********************
 * Fibonacci Function *
 **********************/
	
	/* Need room for:
	 *   parent LR   36(FP)
	 *   parent FP   28(FP)
	 *   parent SP    0(FP)
	 *   temp1        8(FP)
	 *   temp2       12(FP)
	 *   param 'x'   16(FP)
	 * 6 words * 4 bytes = 24 bytes.   Round up to 32 (multiple of 16)
	 * Frame Size (size of Activation Record) = 32
	 *
	 * ACTIVATION RECORD LAYOUT
	 *
	 *    +---------+
	 * 36 |LR_parent|
	 *    +---------+        ^
	 * 32 |SP_old   |        |  parent's stack frame
	 *    +---------+ -------+
	 * 28 |FP_parent|
	 *    +---------+
	 * 24 |  ?      |
	 *    +---------+
	 * 20 |  ?      |
	 *    +---------+
	 * 16 |  x      |
	 *    +---------+
	 * 12 |  temp2  |
	 *    +---------+
	 *  8 |  temp1  |
	 *    +---------+
	 *  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 (x == 1) return x.	*/

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

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

	lwz	r3, 12(r31)	/* Add together temp1 and temp2	*/
	lwz	r4, 8(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 Function *
 *******************/
	
#define ACCUM r13
#define OLDLR r14
		
getInt: mflr    OLDLR
	li	ACCUM, 0
loopInt:	
	bl	getchar
	cmpwi	r3, 0x0A
	beq	doneInt
	cmpwi	r3, -1
	bne	loop2int
	li	ACCUM, -1
	b	doneInt
loop2int:		
	cmpwi	r3, 0x30
	blt	loopInt
	cmpwi	r3, 0x39
	bgt	loopInt
	
	subi	r3, r3, 0x30
	mulli	ACCUM, ACCUM, 10
	add	ACCUM, ACCUM, r3
	b	loopInt
	
doneInt:
	mr	r3, ACCUM
	mtlr	OLDLR
	blr