Write 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