Given the following definition of the Fibonacci sequence: fib(0) = 0 fib(1) = 1 fib(n) = fib(n - 1) + fib(n - 2) Your task is to implement the function extern int fib(unsigned int n) in assembler, so that it can be called from a C program. To do this, proceed as follows.

b) Implement the missing function fib in the file fib.S. c) Implement the function recursively and use the stack.

These are the files we have been given:

fib.S:

.global fib fib: MOV pc, lr // return ("return")

libRA.c:

// External interface // ==================

external void hex(int p); extern void newline(); extern void put(char c); extern void exit(int ret);

// Booleans // ========

#define true 1 #define false 0

// Helper for printing // =================== // This function assumes that the argument is a null-terminated string. // The strings we have seen in previous Assembly programs were not // null-terminated. Do not use this implementation outside this project!

void println(char* chars){ while(*chars) put(*chars++); newline(); }

// Linear congruential random number generator // =========================================== // This is a bad random number generator. Do not reuse it in other projects. // Join our master lecture on Information Security for more details. // https://stackoverflow.com/questions/47191747/generating-random-numbers-without-using-cstdlib

#define MY_RAND_MAX = 2147483647 static unsigned long my_rand_state = 1;

void srand(unsigned long seed){ my_rand_state = seed; }

long rand(){ my_rand_state = (my_rand_state * 1103515245 + 12345) % 2147483648; return my_rand_state; }

// Register Sorcery // ================ // It's none of your business!

struct ArmRegisters { int sr[13]; }; #define DUMP_REGISTERS(TARGET_NAME) \ struct ArmRegisters TARGET_NAME; \ asm volatile("STR r0 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[0])); \ asm volatile("STR r1 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[1])); \ asm volatile("STR r2 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[2])); \ asm volatile("STR r3 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[3])); \ asm volatile("STR r4 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[4])); \ asm volatile("STR r5 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[5])); \ asm volatile("STR r6 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[6])); \ asm volatile("STR r7 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[7])); \ asm volatile("STR r8 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[8])); \ asm volatile("STR r9 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[9])); \ asm volatile("STR r10 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[10])); \ asm volatile("STR r11 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[11])); \ asm volatile("STR r12 , [%[addr]]" : : [addr] "r" (&TARGET_NAME.sr[12]));

int arm_eval_restored_register(struct ArmRegisters a, struct ArmRegisters b, int n) { if (a.sr[n] != b.sr[n]){ println("Start: register was not restored."); println("Register:"); hex(n); println("Value before call:"); hex(a.sr[n]); println("Value after call:"); hex(b.sr[n]); println("End: register was not restored."); return 1 << (n+1); } } return 0; }

int arm_eval_restored_registers(struct ArmRegisters a, struct ArmRegisters b){ return arm_eval_restored_register(a,b,4) | arm_eval_restored_register(a,b,5) | arm_eval_restored_register(a,b,6) | arm_eval_restored_register(a,b,7) | arm_eval_restored_register(a,b,8) | arm_eval_restored_register(a,b,9) | arm_eval_restored_register(a,b,10); // arm_eval_restored_register(a,b,11) | // arm_eval_restored_register(a,b,12) ; // https://community.arm.com/developer/tools-software/oss-platforms/f/dev-platforms-forum/5436/i-want-to-know-meaning-of-r12-register }

libRA.S:

.global newline newline: STMFD sp!, {r7, lr} MOV r7, #4 // write syscall MOV r0, #1 // file descriptor LDR r1, =nl // address of newline MOV r2, #1 // length SWI #0 LDMFD sp!, {r7, pc}

.global put put: // parameters in r1 STMFD sp!, {r7, lr} LDR r1, =buf STRB r0, [r1] MOV r7, #4 // write syscall MOV r0, #1 // file descriptor MOV r2, #1 // length SWI #0 LDMFD sp!, {r7, pc}

.global hex hex: // output from r0 STMFD sp!, {r4, r7, lr} MOV r4, r0 MOV r3, #8 MOV r7, #4 // write syscall MOV r0, #1 // file descriptor MOV r2, #1 // length hexloop: LDR r1, =lut ADD r1, r1, r4, lsr #28 SWI #0 MOV r4, r4, lsl #4 SUBS r3, r3, #1 BNE hexloop BL newline LDMFD sp!, {r4, r7, pc}

.global exit exit: MOV r7, #1 SWI #0

.data buf: .ascii " " lut: .ascii "0123456789abcdef" nl: .ascii " "

main.c:

#include "./libRA.c" external int fib(unsigned int n);

void _start() { println("Calculate fib(n) with n: 1-10:"); for (int i = 1; i < 10; i ++) { hex(fib(i)); } exit(0); }