---
tags: NCKU Linux Kernel Internals, C語言
---
# C 語言：goto 和流程控制

[你所不知道的C語言: goto 和流程控制篇](https://hackmd.io/@sysprog/c-control-flow?type=view)

## switch and goto
switch 可依據整數索引值進行[多重分支(multiway branching)](https://en.wikipedia.org/wiki/Multiway_branch)，透過 [jump table](https://en.wikipedia.org/wiki/Branch_table) 的實作技巧提升效率。
### GNU extension: computed goto
根據 [labels as Values](https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html)，我們可以透過 operator `&&` 取得一個 label 的所在位址，儲存在 `void *` 中。

#include <stdio.h>

int main()
{
    static void *jump_table[2] = {
        &&label_A, &&label_B
    };
    
    int i;
    printf("Input a number from 0 to 100:");
    scanf("%d",&i);
    if(i > 100 || i < 0) goto label_def;
    goto *jump_table[i % 2];

label_A:
    printf("Even");
    goto done;
label_B:
    printf("Odd");
    goto done;
label_def:
    printf("Wront input");
    goto done;

done:
    return 0;
}

以這個程式為例，利用 `&&` 將 label 位置放在 `jump_table` ，在判斷輸入的 `i` 是否符合預期的範圍後，透過 `i % 2` index 至應該執行的地方。 這個技巧稱為 **Computed goto**。

根據 [Computed goto for efficient dispatch tables](https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables)，思考一個迴圈執行的同等 switch / computed goto 的程式碼(詳細請看連結)，computed goto 比起 switch 會來得更有效率。

computed goto 和 switch case 的效能差異來自 branch check 和 branch prediction
* 即使程式中的 switch 沒有用到 default case，switch 也必須檢查 default case，因此 switch 會較 computed goto 多花一個 bounds checking 的步驟
* switch 需要預測接下來跳到哪個分支。以前面的程式為例，如果是 switch 版本，會需要對 `i % 2` 做額外的檢查(類似一個 `if(i % 2 == 0)` 的判斷式)，但 computed goto 可以直接透過 `i % 2` index 到正確的執行指令。

### 破除迷思
考慮以下程式:

int main(int argc, char *argv[]) {
    int a = 0;
    switch (a) {
        if(0) { case 0: printf("0");}
        if(0) { case 1: printf("1");}
        if(0) { case 2: printf("2");}
        if(0) { default: printf("no");}
        break;
    }
    return 0;
}

得到的 output 會是 0!

也就是說，當 a = 0，即使 `case 0` 被 if (0) { … } 包圍，裡面的 statement 仍會被執行!而其他的 if (0) 則會充當類似 break 的角色，因而不會被執行到。

## Duff’s Device
[Duff's Device](https://en.wikipedia.org/wiki/Duff%27s_device) 最初是為複製資料而生，透過巧妙地展開迴圈，減少 branch 的使用總量。

節自維基百科上的範例，想像一個以 16-bit 為處理單元的架構，兩個暫存器間的資料搬動可以寫成:

register short *to, *from;
register count;
{
    do {                          /* count > 0 assumed */
        *to = *from++;
    } while (--count > 0);
}

如果可以八個一數的複製呢? `while()` 中的判斷次數就可以減少至 1/8

register short *to, *from;
register count;
{
    register n = count / 8;
    do {
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
        *to = *from++;
    } while (--n > 0);
}

問題來了，`*to = *from++` 成為了 8 個一數的操作，然而 `count` 並不一定可以被 8 整除。顯然我們需要針對任何的 count 值建立一個通用的結構，那就是 Duff's device。

register short *to, *from;
register count;
{
    register n = (count + 7) / 8;  // gives the number of iterations
    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
            } while (--n > 0);
    }
}

可以看到這個設計的巧妙之處: 通過 switch，可以從某個 case 為起點開始運行 `*to = *from++`，因此可以滿足任何的 count 輸入。

[How does Duff's device work?](https://stackoverflow.com/questions/514118/how-does-duffs-device-work) 有還蠻詳盡的 trace。