Writing Fibonacci in AArch64 Assembly

The first (and last) time I coded a Fibonnaci sequence was in my first year in college and it was in C. It was confusing and recursion to this day is still a bit of a mystery to me. In this article I will revist the topic and write the sequence in C, Python3 and more significantly aarch64 assembly.

I aim to understand recursion better through the sequence, and get a better grasp of aarch64 assembly programming. Let’s get started.

!Disclaimer!: This article is not a tutorial on aarch64 assembly programming, but rather an illustration of how recursion works in assembly! It requires a fundamental understanding of the architecture and its instructions. If you are new to assembly programming, I recommend you start with a tutorial on the basics of aarch64 assembly programming.

Fibonacci Sequence

The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. The sequence goes like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. However, in some older definitions, the value F₀ = 0 is omitted, so that the sequence starts with F₁ = F₂ = 1 and the sequence goes like this: 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.

It is good to note that the Fibonacci sequence/numbers are pre-determined. For instance, 6 is not a fibonacci number, but 8 is.

Recursion

Recursion is a programming technique where a function calls itself until a base case is reached. It is a powerful tool in programming, but it can be difficult to understand and debug. Recursion is used in many algorithms, including the Fibonacci sequence.

When a function calls itself recursively, the current function does not finish executing immediately. Instead, it pauses and waits for the recursive call to finish before continuing. This process continues until the base case is reached, at which point the function calls begin to return and the original function resumes execution. Through a simple visualization, I will illustrate how the Fibonacci sequence is calculated using recursion.

Besides the Fibonacci sequence, other algorithms use recursion. The factorial algorithm is a good example. However, the article will focus on the Fibonacci sequence and how it is calculated using recursion.

As established, recursion involves the pausing of function execution. This involves the use of a stack to store the state of each function call. The stack is crucial in recursion because it allows the program to keep track of the function calls and their parameters. In the Fibonacci sequence, the stack stores the state of each function call, including the current number being calculated and the previous two numbers in the sequence. Since in assembly programming we manage the stack manually, understanding how the stack works is essential. This will be more evident when we write the Fibonacci sequence in aarch64 assembly.

Writing Fibonacci in C

#include <stdio.h>

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2); // Recursively call fibonacci(n - 1) and fibonacci(n - 2)
}

int main() {
    int n = 10;
    printf("%d ", fibonacci(n)); // Prints the 10 (n)th Fibonacci number

    return 0;
}

Writing Fibonacci in Python3

#!/usr/bin/python3

def fibonacci (n):
	if n <= 1:
		return n
	else:
		return fibonacci(n - 1) + fibonacci(n - 2)


if __name__ == '__main__':

	print(fibonacci(9)) # Prints the 9th Fibonacci number

Writing Fibonacci in AArch64 Assembly

.global _start

.section .text

_start:
    mov x0, #11 // Set nth number to calculate
    bl fibonacci // Call the fibonacci function

    // Exit the program after the Fibonnaci functions returns
    mov x8, #93 // syscall number for exit
    mov x0, #0 // exit status
    svc #0 // Make the syscall

fibonacci:
    // Function prologue
    stp x29, x30, [sp, -16]! // Push x29 and x30 to the stack
    mov x29, sp // Set frame pointer to the current stack pointer
 
    // Base case
    cmp x0, 1 // Check if the argument is less than or equal to 1
    b.le end // If true, return the argument by jumping to the end label. x0 will have the value of n

    // Recursive case
    str x0, [sp, #-16]! // Store the argument (nth fibonacci number to calculate) in the stack

    sub x0, x0, 1
    bl fibonacci // call fibonacci(n - 1)
    str x0, [sp, #8] // Store the result of fibonacci(n - 1) in the stack

    ldr x1, [sp] // load/pop the original argument from the stack
    sub x1, x1, 2
    mov x0, x1 // Set x0 to n - 2 as the argument for the next fibonacci call
    bl fibonacci // call fibonacci(n - 2)
    
    ldr x1, [sp, #8] // load/pop the result of fibonacci(n - 1) from the stack
    add x0, x0, x1 // Add the results of fibonacci(n - 1) and fibonacci(n - 2) and store in x0
    add sp, sp, 16 // Pop the stack

end:
    // Function epilouge
    ldp x29, x30, [sp], 16
    ret

Let me help visualize how this recursive Fibonacci function works with an example of calculating fib(3). I’ll show both the execution flow and stack state:


fib(3) Execution Flow:
                    fib(3)
                   /      \
              fib(2)      fib(1)=1
             /     \
        fib(1)=1   fib(0)=0

Let’s go through it step by step with stack visualization:

1. Initial call to fib(3):
Stack (grows downward):
+------------------+ <- original sp
| x29 (old fp)     |
| x30 (ret addr)   |
+------------------+ <- new sp, new fp (x29)

2. Before first recursive call (fib(2)):
Stack:
+------------------+ <- original sp
| x29 (old fp)     |
| x30 (ret addr)   |
+------------------+
| n=3 (saved)      |
| (space for n-1)  |
+------------------+ <- sp

3. fib(2) starts:
Stack:
+------------------+ <- original sp
| x29 (old fp)     |
| x30 (ret addr)   |
+------------------+
| n=3 (saved)      |
| (space for n-1)  |
+------------------+
| x29 (fp for n=2) |
| x30 (ret addr)   |
+------------------+ <- sp, new fp

4. This continues recursively...

Let’s walk through the code execution for fib(3):

    stp x29, x30, [sp, #-16]!   ; Save fp and lr
    mov x29, sp                  ; Set new fp
    
    cmp x0, #1                  ; Compare 3 <= 1
    ble .base_case              ; Not taken
    
    sub sp, sp, #16            ; Make space for locals
    str x0, [sp]               ; Store 3 on stack
    
    sub x0, x0, #1             ; x0 = 2
    bl fib                     ; Call fib(2)
        |
        |   fib(2):
        |       [same prologue]
        |       cmp x0, #1     ; Compare 2 <= 1
        |       ble .base_case ; Not taken
        |       
        |       [store 2 and call fib(1)]
        |           |
        |           |   fib(1):
        |           |       [prologue]
        |           |       cmp x0, #1    ; Compare 1 <= 1
        |           |       ble .base_case ; Taken!
        |           |       mov x0, x0     ; Return 1
        |           |       [epilogue]
        |           |   Returns 1
        |           |
        |       [store result=1]
        |       [call fib(0) which returns 0]
        |       add results: 1 + 0 = 1
        |   Returns 1
        |
    str x0, [sp, #8]           ; Store result=1
    
    ldr x0, [sp]               ; Load original n=3
    sub x0, x0, #2             ; x0 = 1
    bl fib                     ; Call fib(1) returns 1
    
    ldr x1, [sp, #8]           ; Load previous result (1)
    add x0, x0, x1             ; 1 + 1 = 2
    add sp, sp, #16            ; Clean up stack
    
    ldp x29, x30, [sp], #16    ; Restore fp, lr
    ret                        ; Return 2

Conclusion

In this article, I have written the Fibonacci sequence in C, Python3, and aarch64 assembly. I have also attempted to explain how recursion works and how the Fibonacci sequence is calculated using recursion. I hope this article has helped you understand recursion better and given you an idea of how to implement it in aarch64 assembly.

!Disclaimer (again): This article was not a tutorial on aarch64 assembly programming, but rather an illustration of how recursion works in assembly programming!

I wrote the article with a lot of help from resources online, and I would like to give credit to the following resources: