A3-b: Fibonacci REPL

400 points

CMake target: a3b

cmake --build .build --target a3b

You can receive points for either A3-a or A3-b, but not both!

Computing a number from the Fibonacci Sequence can be very time consuming and repetitive especially if you previously computed that number. Why not spice your implementation of the Fibonacci Sequence up a bit by considering a REPL version?

This assignment is all about saving and reusing results and some (slightly) more advanced user interaction. It requires you to work with explicit memory management (through functions like malloc, realloc, or free), which can be a bit of a challenge in a low-level language like Assembly.

Use the a3b-fib-repl.S file for your implementations (main and my_fib) for this part.

---

Subroutine

The implementations from A3-a will recalculate the entire Fibonacci sequence for every call. This is quite wasteful for your compute resources (at least if you value computation time over storage in the so-called space-time-tradeoff). In this assignment, you are addressing that issue with a reworked my_fib subroutine. The new signature is as follows:

uint64_t *my_fib(uint64_t i, uint64_t *arr, uint64_t size)

This routine not only takes the index of the Fibonacci number to calculate (i) but now also takes a pointer to an array (arr) of already computed Fibonacci numbers (the length of which is indicated by size). It furthermore no longer returns a computed value, but rather also a pointer to an array. The arr argument can be NULL in the case that there are no pre-calculated numbers.

When the function is called, there are two possible executions:

1. $\texttt{size} > \texttt{i}$: the Fibonacci sequence is already calculated up to the requested index

2. $\texttt{size} \le \texttt{i}$: the Fibonacci sequence is not yet calculated up to the requested index

Handling the first case is trivial (as no work has to be done and the array should stay untouched), for the second, however, the function should:

• resize the array to fit the Fibonacci sequence up to the requested index

• calculate the missing numbers (without recalculating any existing numbers)

• return a pointer to the new array

while not allocating more memory than needed for the sequence or leaking any memory.

---

Main Program (REPL)

Write a main routine that continuously asks the user for an index and then prints the associated Fibonacci number, until the user enters a non-numeric input, at which point the program should exit gracefully (Hint: you may want to read the scanf man page to learn how inputs that do not match the format specifier are handled).

The output of a program run should look as follows:

Enter an index: <x>
F_<x> = <fib(x)>
Enter an index: <y>
F_<y> = <fib(y)>
Enter an index: <z>
F_<z> = <fib(z)>
Enter an index: q
Exiting...

The program should make use of the full functionality offered by the revised my_fib function, so properly keep track of the already calculated sequence of numbers (and its length). This will be tested by the TA handling your submission.

---

Memory safety

Starting from this assignment, you will work closely with memory allocation and manipulation. We expect your program to precisely handle memory, without any memory errors. The CodeGrade environment will test whether your program safely accesses and releases memory, by means of address sanitization.

It is now the perfect time to familiarize yourself with address sanitization and memory errors. All upcoming assignments will require an intuition for memory-related issues, which would ideally be developed during this assignment.