---
tags: linux2022
---

# 2022q1 Homework2 (quiz2)
contributed by < `sternacht` >

> [作業要求](https://hackmd.io/@sysprog/BybKYf5xc)

### 測驗 1

#### 答案
EXP1 = `a & b & 1`
EXP2 = `a & b`
EXP3 = `a ^ b`

#### 延伸 - 解釋程式碼運作的原理
本題描述一個取 a,b 兩值平均值的方式，若是直接相加再除以 2 ，可能面臨 overflow 的風險，而寫成 a + (b - a) / 2 則是比較安全的方式之一，要求將此方式以 bitwise 操作改寫

uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (EXP1);
}

在 bitwise 操作中， `a >> 1` 相當於把 a 除二並捨去小數，於是就可以想到 EXP1 所指的就是要對捨去的小數做進位的動作，因為當 a,b 都是奇數時 (LSB == 1) ， LSB 相加的進位會變成各自的小數被捨棄。因此， EXP1 的表示式要在 a,b 的 LSB 都為 1 的時候為 1 ，其餘為 0 ，答案就是 `a & b & 1`

接著再進一步改寫成

uint32_t average(uint32_t a, uint32_t b)
{
    return (EXP2) + ((EXP3) >> 1);
}

乍看之下看不出個所以然，所以先來看看 & , ^ 等 bistwise 操作在兩個數上的另一個意義。 & 會令兩數同為 1 的 bit 為 1 ，而以加法來看，兩個同為 1 的 bit 會有進位存在，因此可以把 & 想作為 '取得相加後會進位的 bit 並除以 2 '。而 ^ 則是在兩 bit 不相同時會為 1 ，因此可以看成是 '相加後會變成 1 的 bit'。
綜合以上兩個操作，可以把 a + b 寫成 `((a & b) << 1) + (a ^ b)` ，分別表示了有進位與沒有進位的 bit ，接著在把 a + b 除以二取平均，也就是 right shift 一個 bit ， 就變成 `(a & b) + ((a ^ b) >> 1)` ，於是就得到了答案。

#### 延伸 - 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀
利用 `gcc -S -O2 average.c` 命令取得最佳化的組合語言的程式碼如下

average:
.LFB0:
        .cfi_startproc
        endbr64
        movl    %edi, %eax
        movl    %esi, %edx
        andl    %esi, %edi
        shrl    %eax
        shrl    %edx
        andl    $1, %edi
        addl    %edx, %eax
        addl    %edi, %eax
        ret
        .cfi_endpro

從第 5 行開始，前兩行是將傳入值 a, b 搬到暫存器上
第 7 行將 a, b 做 & 操作，此時取得 `a & b`
8,9 行對暫存器中的 a , b 做 shift ，得到 `(a << 1)` 和 `(b << 1)`
第 10 行再回頭做第二次 & 操作，取得 `a & b & 1`
11, 12 行則是將得到的三個值相加

用第二種程式取得的最佳化組合語言如下

average:
.LFB0:
        .cfi_startproc
        endbr64
        movl    %edi, %eax
        andl    %esi, %edi
        orl     %esi, %eax
        shrl    %eax
        addl    %edi, %eax
        ret
        .cfi_endproc

第 5 行將傳入值 b 放到暫存器上
第 6 行做 `a & b` 的操作
第 7, 8 做 `(a | b) << 1`
第 9 行把兩個相加

### 測驗 2

#### 答案

EXP4 = `a ^ b`
EXP5 = `a < b`

#### 延伸 - 解釋程式碼運作的原理
本題要求利用 bitwise 操作求得 a, b 兩者中較大的值

#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
    return a ^ ((EXP4) & -(EXP5));
}

這題的解法要先從 ^ 的幾個特性說起， ^ 也就是 XOR，在 `0 ^ 1` 時為 1 ， `0 ^ 0` 或 `1 ^ 1` 時為 0 ，而且這個操作具有交換率，也就是 (a ^ b) ^ c == a ^ (b ^ c)，延伸可得一個特性是 x ^ (x ^ y) == y，這就可以用交換率解釋 : (x ^ x) = 0 然後得到 (0 ^ y) = y。
接下來先看題目中 EXP5 的部分，因為我們希望當 a 是較大的值時，整個函式會得到 a ^ 0，因此
-EXP5 就要在 a > b 的時候為 0 ，可得到答案是 `a < b`。至於為何要用負號，是因為當 a < b 時，EXP5 會得到 1 ，而我們要把內容轉換成 -1 ，也就是 0xFFFFFFFF 讓 EXP4 與其做 & 操作，得到 EXP4 內的值，最後結合前面提過的 a ^ (a ^ b) == b ， 可得知 EXP4 答案為 `a ^ b`
#### 延伸 - 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
這題運用到的方法不管在有號或是無號數上，只要 (a < b) 的結果正確，那就是通用的。因此有號數的版本只要使讀進來的兩個值型態為有號數即可

#include <stdint.h>
uint32_t max(int32_t a, int32_t b)
{
    return a ^ ((a ^ b) & -(a < b));
}

#### 延伸 - 請在 Linux 核心原始程式碼中，找出更多類似的實作手法
[實作 1](https://github.com/torvalds/linux/commit/6c786bcb29dd684533ec165057f437d5bb34a4b2)
[實作 2](https://github.com/torvalds/linux/commit/747f49ba67b8895a5831ab539de551b916f3738c)

### 測驗 3

#### 答案
COND = `v`
RET = `u << shift`

#### 延伸 - 解釋程式運作原理

題目改寫自 GCD 演算法，對兩數求最大公因數 ([來源](https://hackmd.io/@sysprog/linux2022-quiz2#測驗-3))
1. If both x and y are 0, gcd is zero $gcd(0, 0) = 0$.
2. $gcd(x, 0) = x$ and $gcd(0, y) = y$ because everything divides $0$.
3. If x and y are both even, $gcd(x, y) = 2*gcd(\frac{x}{2}, \frac{y}{2})$ because $2$ is a common divisor. Multiplication with $2$ can be done with bitwise shift operator.
3. If x is even and y is odd, $gcd(x, y) = gcd(\frac{x}{2}, y)$.
4. On similar lines, if x is odd and y is even, then $gcd(x, y) = gcd(x, \frac{y}{2})$. It is because $2$ is not a common divisor.

原本的函式

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

改寫成以下

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
    while (!(u & 1))
        u /= 2;
    do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (COND);
    return RET;
}

雖然改寫後複雜了許多，但本質上還是 GCD 的演算法。多的是 shift 這個變數，這個變數儲存的是
u, v 兩數對 2 的冪的公因數，也就是在除以 $2^{shift}$ 後，必至少有一個數會是奇數，並且可以確定不會再有更多 2 出現在最大公因數裡，於是接下來的操作就是把 u 中多餘的 2 先除掉，這一步我的理解是為了要盡可能減少計算的量，連同後續在 do while 中對 v 做除 2 也是相同的原因。

while (!(u & 1))
        u /= 2;

接著 do while 的部分，在原函式中是用 % (mod) 的方式來取的值，若一開始 u < v，則會變成 u, v 交換，接著在後續的過程中保證 u >= v，直到 v 為 0 ，換句話說，v 是用來判斷函式結束的關鍵。
而改寫後更像是輾轉相除法，用相減來逼近答案，因此要判斷 u 是否大於 v ，以保證相減後獲得的值是大於 0 ，最後結束條件同樣是 v 等於 0， COND 部分可簡寫成 while (v) 來檢查 v 是否為 0。
RET 要回傳的就是結果，因此除了從 GCD 中得到的 u 之外，還要把最前面除掉的 $2^{shift}$ 乘回去，因此 RET 為 `u << shift`

#### 延伸 - 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升
透過 __builtin_ctz 改寫後的程式碼如下，主要將除 2 的部份透過 __builting_ctz 來取代迴圈執行

uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift = __builtin_ctz(u) < __builtin_ctz(v)? \
        __builtin_ctz(u): __builtin_ctz(v);
    u >>= __builtin_ctz(u);
    do {
        v >>= __builtin_ctz(v);
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << shift;
}

撰寫一個簡單的測試，對兩個數求最大公因數並輸出兩個函式分別執行的時間，結果如下圖，使用了 __builtin_ctz 的函式明顯比未使用得來的快。

### 測驗 4

#### 答案
EXP6 = `bitset & -bitset`

#### 延伸 - 解釋程式運作原理，並舉出這樣的程式碼用在哪些真實案例中
本題要求在 EXP6 表示式中取得 bitset 中最低位元的 1 ，而這裡運用的就是 - (負號)的特性。對一個值加負號，就相當於翻轉全部的位元並 +1，也就是 -a = ~a + 1 ，最低的 1 位元之前的所有 0 都會被反轉成 1 ，並在 + 1 之後一路進位，直到最低位元的 1 的位置(被反轉成 0 ，進位後又是 1 )，最後再透過 & 操作來得到答案。

#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    uint64_t bitset;
    for (size_t k = 0; k < bitmapsize; ++k) {
        bitset = bitmap[k];
        while (bitset != 0) {
            uint64_t t = EXP6;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}

測驗 3 的延伸題中，[lib/math/gcd.c](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c) 即用到這個方法來計算 lsbit

### 測驗 5

#### 答案
PPP = `pos--`
MMM = `list_add`
EEE = `&heads[remainder % size]`

#### 延伸 - 解釋上述程式碼運作原理，指出其中不足，並予以改進
這題題目是分數轉成十進位小數的字串的實作，而計算方式是先記錄出現過的餘數，當該餘數再次出現時就表示進入循環小數的部分了，而記錄的方式就是熟悉的 linked-list 結合 hash table，接著看看題目問題出現的地方

char *fractionToDecimal(int numerator, int denominator)
{
    int size = 1024;
    char *result = malloc(size);
    char *p = result;

    if (denominator == 0) {
        result[0] = '\0';
        return result;
    }

    if (numerator == 0) {
        result[0] = '0';
        result[1] = '\0';
        return result;
    }

    /* using long long type make sure there has no integer overflow */
    long long n = numerator;
    long long d = denominator;

    /* deal with negtive cases */
    if (n < 0)
        n = -n;
    if (d < 0)
        d = -d;

    bool sign = (float) numerator / denominator >= 0;
    if (!sign)
        *p++ = '-';

    long long remainder = n % d;
    long long division = n / d;

    sprintf(p, "%ld", division > 0 ? (long) division : (long) -division);
    if (remainder == 0)
        return result;

    p = result + strlen(result);
    *p++ = '.';

    /* Using a map to record all of reminders and their position.
     * if the reminder appeared before, which means the repeated loop begin,
     */
    char *decimal = malloc(size);
    memset(decimal, 0, size);
    char *q = decimal;

    size = 1333;
    struct list_head *heads = malloc(size * sizeof(*heads));
    for (int i = 0; i < size; i++)
        INIT_LIST_HEAD(&heads[i]);

    for (int i = 0; remainder; i++) {
        int pos = find(heads, size, remainder);
        if (pos >= 0) {
            while (PPP > 0)
                *p++ = *decimal++;
            *p++ = '(';
            while (*decimal != '\0')
                *p++ = *decimal++;
            *p++ = ')';
            *p = '\0';
            return result;
        }
        struct rem_node *node = malloc(sizeof(*node));
        node->key = remainder;
        node->index = i;

        MMM(&node->link, EEE);

        *q++ = (remainder * 10) / d + '0';
        remainder = (remainder * 10) % d;
    }

    strcpy(p, decimal);
    return result;
}

最後一個 for 迴圈就是用於判斷循環小數， pos 表示循環小數出現的位置，也可以理解從第幾位之後是循環小數，還沒有循環時， pos 得到的回傳值是 -1， 當 pos 大於 0 之後，程式要將剩餘的十進位小數補滿，補滿的形式是 `整數.非循環小數(循環小數)` ，因此首先 PPP 要補齊的的是非小數部分，以 pos 遞減的方式計算，答案就是 `pos--`。
當還沒循環時，程式要記錄每一個餘數以及對應的小數十進位值，並放進 hash table 中，MMM 根據提示及題意可以判斷出是 `list_add` 或 `list_add_tail` 的其中一種，符合最精簡的原則，前者是較好的答案，再來 EEE 就是具體要放在哪個 heads 的位置，根據另一個函式 `find` 的內容，我們可以得知 hash 值的計算方式就是`remainder % size`，因此得到 EEE 的答案就是 `&heads[remainder % size]`

除了提示中提到計算正負號可以寫作 `bool isNegative = numerator < 0 ^ denominator < 0;` 之外，我在閱讀的過程中，對於 size 值的設定感到有些困惑，考慮到 hash table 要達到盡可能分散進來的值，將 size 值設定的大一些是可以理解的。但對於這樣找循環小數的程式來說，其實只要讓 size = denominator 就夠了，因為我們可以確定的是 remainder 不會大於 denominator，，也就是說 remainder 的範圍就是從 0 到 denominator ，只要遇到重複就表示循環小數發生，因此在最糟的情況下，也只會是每一個 heads 都被放入一次 remainder ，接著就一定會循環了，第二個 size 可以改寫成 `size = (denominator > n)? n: denominator;` ， n 是我們設定的 hash 範圍，範例中是 1333。
同時，如果輸入的 denominator 很大的時候，原先設定的字串長度 1024 也會不夠用導致程式錯誤，將第一個 size 改成以下的條件式 `int size = (denominator > 0)? denominator: -denominator;` 即可。

### 測驗 6

#### 答案
M = `_h`
X = `0`

#### 延伸 - 解釋上述程式碼運作原理

#define ALIGNOF(t) \
    ((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)

先將這提拆分成減號前後兩部份，先細看前面的部份。
在 `(char *)(&((struct { char c; t _h; } *)0)->M)` 中有一個 `struct { char c; t _h; }` 的結構，建立一個此結構的指標，並給與此指標值為 0 ，也就是將這個結構的指標放到記憶體 0 的位址。接著因為 alignment 的緣故， `_h` 會根據型態 t 的不同，與 char `c` 的距離有所改變，而 `_h` 的記憶體起始位址減去 `c`的記憶體起始位址，就是 alignment 的距離，至此我們可以理解前面的部份就是 `_h` 的位址， M = `_h` ，而後面的部份就是 char `c` 的起始位址，本題題目將整個結構放在 0 的位址上， `c` 的起始位置在 0 ， X = 0 。

#### 延伸 - 在 Linux 核心原始程式碼中找出 __alignof__ 的使用案例 2 則，並針對其場景進行解說

- [include/uapi/linux/netfilter_bridge/ebtables.h](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/include/uapi/linux/netfilter_bridge/ebtables.h)
line 90

char data[0] __attribute__ ((aligned (__alignof__(struct ebt_replace))));

利用 `__alignof__` 取得某個 struct alignment，接著用 `__attribute__ (aligned)` 使變數對齊。

- [include/linux/kstrtox.h](https://github.com/torvalds/linux/blob/35e43538af8fd2cb39d58caca1134a87db173f75/include/linux/kstrtox.h)
line 36-37

if (sizeof(unsigned long) == sizeof(unsigned long long) &&
	    __alignof__(unsigned long) == __alignof__(unsigned long long))

這一段看起來很有趣，以我的電腦來說 long long 相當於 64 bits ， long 也是 64 bits，但是在某些不同的架構底下 long 可能是 32 bits，因此這一段程式碼主要就是用在分辨不同的長度，以確保回傳值的長度固定。

### 測驗 7

#### 答案
KK1 = `div3`
KK2 = `div5`
KK3 = `div3 << 2`

#### 延伸 - 解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差
FizzBuzz 的題目要求題目:
- 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
- 如果是 5 的倍數，印出 “Buzz”
- 如果是 15 的倍數，印出 “FizzBuzz”
- 如果都不是，就印出數字本身

而觀察輸出則可以發現輸出的文字就是 "Fizz", "Buzz" 兩個的排列組合，因此給定一個字串 `FizzBuzz`，並透過調整輸出字串的 "起始位置" 及 "長度"，就可以滿足三種不同的輸出形式。
題目的程式碼如下

static inline bool is_divisible(uint32_t n, uint64_t M)
{
    return n * M <= M - 1;
}

static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;

int main(int argc, char **argv)
{
    for (size_t i = 1; i <= 100; i++) {
        uint8_t div3 = is_divisible(i, M3);
        uint8_t div5 = is_divisible(i, M5);
        unsigned int length = (2 << KK1) << KK2;

        char fmt[9];
        strncpy(fmt, &"FizzBuzz%u"[(9 >> div5) >> (KK3)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

首先在決定長度的部分，當 n 是 3 或 5 的倍數時為 2，同時是 3, 5 的倍數時為 8 ，因此 KK1 及 KK2 就分別代表 n 是否為 3, 5 的倍數，以 0, 1 表示，而在其他狀況下，長度為 2 ，也就是字串中用來輸出整數的 `"%d"` 。回頭看前兩行的 div3 跟 div5，從變數名稱大概可以猜得出來其所代表的意涵，實際上的運作方式是這樣的。
當有一個 3 的倍數 n 與 M3 一起傳入， n * M3 會相當於 `(n / 3) * 0xFFFFFFFFFFFFFFFF + n` ，而在溢位之後剩下的就只有 `2n / 3` ，因此在一定範圍內會比 M3 這樣的數字來的小，當 n 不是 3 的倍數時，溢位後仍會剩下 `0xFFFFFFFFFFFFFFFF` 加上一個大於等於 1 的整數，使條件不成立。
於是 KK1 及 KK2 的答案就分別是 div3 及 div5

根據上述獲得的字串長度，接著要知道起始位置，在`(8 >> div5) >> (KK3)`這個部分，可以考慮以下情況時起始位置的不同

> 原題目是寫`(9 >> div5) >> (KK3)`，但應該將 9 改成 8，亦即開頭應該設定在 `%` 的位置，否則其他狀況下的輸出會剩下一個 `u`，不符合題目要求

- 3 的倍數，應該為 0 ，8 要右移至少 4 個 bits
- 5 的倍數，應該為 4 ，8 要右移 1 個 bit
- 15 的倍數，應該為 0 ，要右移 4 個 bits(1 + 至少 3)
- 以上皆非，不須位移

因此我們可以得知 KK3 至少要是 4 ，在符合最簡潔程式碼的條件下 KK3 = `div3 << 2` 是最好的答案