/************************* * COSC 065 Fall 2006 * * Fibonacci Demo * * D.W. Brylow * *************************/ #include .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 */