x86-64組合語言：和C語言一起計算Fibonacci數列！

Fibonacci數列是一個相當知名的數列。它的得名，據說是Fibonacci用來描述用它來描述一對兔子生長情形而來的。關於這個數列許多詳細的資料，以及可怕的公式，可以參閱維基百科、OEIS網站、以及這裡。

在很多程式語言的書籍裡面，都會把Fibonacci數列的計算放在範例，或者是當作練習題，因為這個數列的計算可以使用到遞迴（Recursion。函數自己呼叫自己。我把這個叫做「把皮球踢給未來的自己」，當然，講得好聽點也可以說是「世代傳承」）的概念。

回到我們的主題吧！整個程式都用組合語言來寫的話，其實是一件雖然有樂趣但是會使用掉很多時間，還可能會有不少難以抓出的錯誤。為了練習最想要練習的部份，我們可以把程式的一部分用C語言構成，剩下的重點部份才使用組合語言，分別完成之後，把他們像樂高玩具一樣接在一起就好了！

我們首先制定計算Fibonacci數列的函數原型。先制定原型，然後寫在main.c的上方。接著，依照所制定的原型，來填入組合語言指令，最後開始方便的進行測試。有了GCC替我們精心安排的main函數，我們就可以把焦點放在組合語言指令序列上面了！

那接著就來看程式長什麼樣子囉！這組成是因為有超過一個檔案，所以製作了Makefile。所以，如果要執行的話，請在terminal上面輸入：

make run

首先是main.c：

#include <stdio.h>

/*
 * 宣告組合語言程式的函數原型
 * unsigned long long 是64位元整數
 */
unsigned long long fib(unsigned long long n);

int main()
{
  int i;
  for (i = 0; i < 30; i++)
    {
      printf("%lu\n", fib(i + 1));
    }
  return 0;
}

接著是本次的大重點，fib.s。

        .section .text

        /*
        這是用來計算fibonacci數列的函數
        我們把fibonacci數列定義成：
        fib(1) = 1
        fib(2) = 1
        fib(n) = fib(n - 1) + fib(n - 2)

        對應的C語言函數原型是：
        unsigned long long fib(unsigned long long n)
        */
        .global fib
        .type fib, @function
fib:
        /*進行堆疊框架(stack frame)的配置*/
        push %rbp
        mov %rsp, %rbp
        /*現在堆疊位址已經向16位元組對齊了*/

        /*
        n == 1 ?
        fib(1) = 1
        */
        cmp $1, %rdi
        jne fib_not_1
        mov $1, %rax
        jmp fib_end
fib_not_1:
        /*
        n == 2 ?
        fib(2) = 1
        */
        cmp $2, %rdi
        jne fib_others
        mov $1, %rax
        jmp fib_end
fib_others:
        /*fib(n) = fib(n - 1) + fib(n - 2)*/
        xor %rax, %rax

        /*算fib(n - 1)*/
        sub $1, %rdi
        push %rdi
        call fib
        pop %rdi

        /*算fib(n - 2)*/
        sub $1, %rdi
        push %rax
        call fib
        pop %rcx
        
        add %rcx, %rax
fib_end:
        /*還原堆疊框架的配置*/
        mov %rbp, %rsp
        pop %rbp
        ret

最後是Makefile

build: ./build/fib

run: ./build/fib
        ./build/fib

./build/fib: main.c fib.s
        mkdir -p ./build
        gcc main.c fib.s -o ./build/fib

.PHONY: clean
clean:
        rm -r ./build