Question

Consider the following C code that outlines Fibonacci function

int fib (int n) {

if (n == 0) return 0;

else if (n==1) return 1;

else return fib(n-1) + fib (n-2);

}

For this programming assignment, write and test an ARMv8 program to find Fibonacci (n).

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 always passed in X1. The function fib always returns its result in register X2.

You need to save the return address (contained in X30) and input n (contained in X1) on stack.

When you call fib recursively, you are changing the value of n and thus modifying X1. 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 X2 which contains the result returned by fib(n-1) on stack. This is

because fib(n-2) will also return its result in X2. 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 X2. 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 (X1, X2 and X30) each time you enter fib, 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 X1.

fib:

check if n is zero, if yes, set X2 =0 and return

check if n is one, if yes, set X2 = 1 and return

//note we did not have to save anything on stack if either of these two conditions

// are true, since we will not be calling fib recursively

if n is greater than 1

decrement stack pointer

save n (X1) and return address (X30) on stack

set X1 = X1-1 , that is n = n-1

call fib (this time with n-1)

upon return from fib (n-1), save X2 on Stack

restore n (X1) from stack

set X1=X1-2

call fib (that is fib(n-2))

upon return

restore previously saved value (X2) from stack

you can load this into X3

set X2 = X2+X3 (new value to be returned)

restore return address (X30)

increment stack pointer

return

Test input: n= 7

Submit: A file containing your ARMv8 code, a read me file (if needed), a snapshot of stack after

main calls fib (first call) and a snapshot of stack when n becomes 1 (just before the recursion

starts unwinding). Also show a snapshot of register contents at the time main calls fib (showing

that X1 contains n), and a snapshot showing the final values in registers (to show that X2

contains the final result).

Answer 1

HELLO I AM ADDING ARMv8 CODE FOR FIBONACCI

PLEASE GO THROUGH IT ONCE
THANK YOU

.syntax unified

.equ maxfib,4000000

previous .req r4
current  .req r5
next     .req r6
sum      .req r7
max      .req r8
tmp      .req r9

.section .rodata
 .align 2
fibstring:
 .asciz "fib is %d\n"
sumstring:
 .asciz "%d\n"

.text
 .align 2
 .global main
 .type main, %function
main:
 stmfd sp!, {r4-r9, lr}
 ldr max,   =maxfib
 mov previous, 1 
 mov current, 1
 mov sum, 0

loop:
 cmp current, max
 bgt last

 add next, current, previous

 movs tmp, current, lsr 1      @ setting the carry flag from lsr 
                               @ this will update the status register
 addcc sum, sum, current       @ we add current to the sum ONLY if carry clear is true 


 mov previous, current
 mov current, next
 b loop

last:
 mov r1, sum  
 ldr r0, =sumstring            @ storing address ofstarting of the string to R0
 bl printf

 mov r0, 0
 ldmfd sp!, {r4-r9, pc}
 mov r7, 1                     
 swi 0