ARM assembly 13: Fibonacci

在assembly 12中，我们实现了GCD，它通过recursice的方式来实现计算。今天我们来讲Fibonacci，它的Recursive相比于GCD会更加复杂，所以值得进一步讲解。

首先，我们还是看看Fibonacci的传统实现，那就是

// Function to calculate Fibonacci using a recursive approach
int fibonacciRecursive(int n) {
    if (n <= 1)
        return n;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

首先，我们展示一下code base

.global main
.extern fopen, fprintf, fclose, printf, atoi

.section .data
filename: .asciz "nums.txt"
write_mode: .asciz "w"
format_str: .asciz "%d\n"
format_str_result: .asciz "Fibonacci Number: %d\n"

.section .text

print_num_to_file:
    push {lr}
    push {r0-r5}
    
    mov r5, r0

    // Open the file for writing
    ldr r0, =filename
    ldr r1, =write_mode
    bl fopen
    mov r4, r0               // Store the file pointer in r4

    // Check if fopen succeeded
    cmp r4, #0
    beq close_file

    // Write the number to the file
    mov r0, r4
    ldr r1, =format_str
    mov r2, r5
    bl fprintf

    // Close the file
close_file:
    mov r0, r4
    bl fclose

    pop {r0-r5}
    pop {pc}

fibonacci:
    push {lr} 

    // Replace this with your code! Return value goes in r0
    mov r0, #42

end_fib:
    pop {pc}

main:
    push {r4-r7, lr}

    // Check if argument count (argc) is correct
    cmp r0, #2             // Expecting 2 arguments (program name and n)
    blt exit

    // Convert argument string to integer
    ldr r0, [r1, #4]       // Load address of second argument (n value)
    bl atoi                // Convert string to integer
    mov r4, r0

    // Calculate the nth Fibonacci number
    mov r0, r4
    bl fibonacci

    // Print fib result to our file
    bl print_num_to_file

exit:
    // Exit
    mov r0, #0
    pop {r4-r7, pc}
pi@raspberrypi:~/workspace

Base case

当n <=1时，Fibonacci将返回原始数字0或者1。值得主要的是，因为在base case，我们在此前已经把数值存储到r0中，r0同时作为返回值，不需要修改。

//base cast
// if n<=1, return
cmp r0, #1
ble end_fib
//因为r0已经包含了返回值，我们不做其他额外操作。

Recursive case

在recursive case中，因为返回数包含对fibonacci的两次调用，我们需要额外的地址来存放此前的数据(r0),然后我们就可以只之后的递归中，修改r0。

//Recursive Case
//fibonacci(n-1) + fibonacci(n-2)
//我们将n存放于stack中。
push {r0}
sub r0, r0, #1
bl fibonacci
//此前我们将n push到stack中，现在我们将n取出，备份到r1中。
pop {r1}
//r0中存储了fibonacci(n -1)的数值
push {r0}

//执行 n = n -2
sub r0, r1, #2
bl fibonacci

//sum up fib(n-1) + fib(n-2)

//stack中此前存放了fib(n-1)
pop{r1}
add r0, r0, r1

最后，通过编译，我们就可以实现fibonacci的编译。

原文地址：https://blog.csdn.net/qq_19859865/article/details/142867563

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！