Write and test an ARMv8 program to find Fibonacci numbers. Consider the following C code that outlines Fibonacci function:

long long int fib (long long int n) { if (n == 0) return 0; else if (n==1) return 1; else return fib(n-1) + fib (n-2); }

You need to write a main function that calls the recursive fib function and passes an argument n. The function fib calls itself (recursively) twice to compute fib(n-1) and fib (n-2). The input to fib (or n) is passed in X0. The function fib returns its result in register X1.

You need to save the return address (contained in X30) and input n (contained in X0) on stack. When you call fib recursively, you are changing the value of n and thus modifying X0. You need the old value when you return from a recursive call. After calling fib(n-1) and before calling fib(n-2), you must also save X1 which contains the result returned by fib(n-1) on stack. This is because fib(n-2) will also return its result in X1. After returning from fib (n-2), you need to retrieve previously saved result from fib(n-1), add it to the result returned by fib(n-2) and return the sum again in X1. If you are careful in how you are using other registers, you do not need to save any other values on stack. Also remember you need to increment or decrement stack pointer in increments of 16. If you are saving 3 values each time you enter fib (X0, X1 and X30), you need to decrement and increment SP by 32.

Here is a pseudo assembly code you can use to write fib. I am hoping you already know how to declare data section, initialize variable n and main program which gets the address of n, reads the value from memory and calls fib by storing n in X0.

fib: Check in n=0, if yes, return zero in X1 Check if n=1, if yes return one in X1 If n >1, then ....Decrement SP by 32 ....Save X30 on stack ....Save X0 (n) on stack ....Calculate n-1 in X0 ....Call fib (that is fib(n-1)) ....Save X1 on stack (result from fib(n-1)) ....Retrieve previously saved n from stack into X0 ....Calculate n-2 in X0 ....Call fib (that is call fib(n-2)) ....Retrieve previous result from fib(n-1) saved on stack say into X2 ....Add X1= X1+X2 (that is fib(n-1)+fib(n-2)) ....Retrieve X30 from stack ....Increment SP by 32 ....Return

Test input: n = 7

Submit: ARMv8 code, a read me file, a snapshot of stack before main calls fib (first call) and a snapshot of stack when n becomes 0 (just before the recursion starts unwinding). Also show a snapshot of register contents at the time main calls fib (showing that X0 contains n), and a snapshot showing the final values in registers (to show that X1 contains the final result).

Test using DS-5.