---
tags: linux2022
---

# 2022q1 Homework (quiz2)
contributed by <`ibat10clw`>
> [quiz2](https://hackmd.io/@sysprog/linux2022-quiz2#2022q1-%E7%AC%AC-2-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)

## 測驗1
### 程式碼運作原理

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

觀察上述程式碼, ` a >> 1 ` 和 ` b >> 1` 可視為除以 2 的運算, 但當 a 以及 b 為奇數時回傳值會與正確結果差 1

因此 EXP1 需要在 a 和 b 都是奇數的情況下為 1, 其餘情況為 0

在二進位下判斷奇偶的方法可以透過確認 LSB 來做判斷, 若 LSB = 1 為奇數, LSB = 0 為偶數
所以可以將 a 和 b 與 1 做 bitwise and 來確認 LSB 的結果

* `EXP1 = a & b & 1`

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

從加法器的角度切入 sum 和 carry 分別能以下列操作表示:
* sum: `x ^ y`
* carry: `(x & y) << 1`

把上面兩者的結果相加等同於 (x + y), 回到題目部份剛好也是兩個運算式相加, 但其中有一個 right shift, 可判斷為 (sum + carry) >> 1 後變成的結果

嘗試將 sum 和 carry 相加後做 right shift
* `(((x ^ y) + (x & y) << 1)) >> 1`
`= (((x ^ y) >> 1) + (x & y))`
`= (x & y) + ((x ^ y) >> 1)`

最後便可推得下列結果
* `EXP2 = (x & y), EXP3 = (x ^ y)`

### 觀察編譯器行為

0000000000000000 <average>:
   0:	f3 0f 1e fa          	endbr64 
   4:	55                   	push   %rbp
   5:	48 89 e5             	mov    %rsp,%rbp
   8:	89 7d fc             	mov    %edi,-0x4(%rbp)
   b:	89 75 f8             	mov    %esi,-0x8(%rbp)
   e:	8b 45 fc             	mov    -0x4(%rbp),%eax
  11:	23 45 f8             	and    -0x8(%rbp),%eax
  14:	89 c2                	mov    %eax,%edx
  16:	8b 45 fc             	mov    -0x4(%rbp),%eax
  19:	33 45 f8             	xor    -0x8(%rbp),%eax
  1c:	d1 e8                	shr    %eax
  1e:	01 d0                	add    %edx,%eax
  20:	5d                   	pop    %rbp
  21:	c3                   	retq   

* 上面是 -O0 產生的組合語言程式碼
* 組合語言指令解析:
* `push src:` 將 src 的資料 push 進 stack
* `mov dest src:` 將 src 的資料搬到 dest
* `xor dest src:` 將 dest 與 src 做 XOR 後存回 dest
* `add dest src:` 將 dest 與 src 做 ADD 後存回 dest
* `shr:` shift right
* `pop dest:` 將 stack 的資料 pop 給 dest

0000000000000000 <average>:
   0:	f3 0f 1e fa          	endbr64 
   4:	89 f8                	mov    %edi,%eax
   6:	31 f0                	xor    %esi,%eax
   8:	d1 e8                	shr    %eax
   a:	21 f7                	and    %esi,%edi
   c:	01 f8                	add    %edi,%eax
   e:	c3                   	retq   

* 上面是 -O1 產生的組合語言程式碼
* 與 -O0 最大的差別是少了 stack 相關的操作

0000000000000000 <average>:
   0:	f3 0f 1e fa          	endbr64 
   4:	89 f8                	mov    %edi,%eax
   6:	21 f7                	and    %esi,%edi
   8:	31 f0                	xor    %esi,%eax
   a:	d1 e8                	shr    %eax
   c:	01 f8                	add    %edi,%eax
   e:	c3                   	retq   

* 上面是 -O2 和 -O3 產生的組合語言程式碼
* 與 -O1 的差別運算順序有些許不同

## 測驗2
### 程式碼運作原理

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

* 解題靈感來自於 [LeetCode 136. single number](https://leetcode.com/problems/single-number/), 透過 XOR 能夠找出 single number 的特性來做思考
* 由於程式碼左半邊的 `a ^` 的部份以固定, 因此想令括號內的結果等價為下列情形:
* `a ^ b`: 當 b 比較大的時候, `a ^ a ^ b` 能夠將 a 消掉, 正好將 b 作為回傳值
* `a ^ a`: 當 a 比較大的時候, `a ^ a ^ a` 由於 a ^ a 的結果是 0, a ^ 0 後又會恢復為 a, 將 a 回傳正好也是最大值

1. 首先根據提示 EXP5 為一個 logical 的運算, 根據 C 語言規格, 邏輯運算結果只會是 0 或 1, 在灌上一個負號後的最後能產生的結果只會是 `0xffffffff` 或 `0x00000000`

1. 再來考慮 & 的特性
* `x & 1 = x`: 不變
* `x & 0 = 0`: 強制歸零

可以根據上述兩種可能的結果繼續推測 EXP4 的可能

1. 回到第一點的討論, EXP4 根據提示為 bitwise 的操作, 而我們希望能夠產出一個 XOR 的結果, 因此這邊填入 `a ^ b`

1. 由於 EXP4 也已經做選擇, 根據 & 運算性質的討論可得最後結論:
* `a ^ ((a ^ b) & -(1))`: 由於 `a ^ b` 不變最後結果剩下 b
* `a ^ ((a ^ b) & -(0))`: 由於括號內被歸零最後結果剩下 a

也就是當實際狀況 a > b 時, 我們希望 EXP5 的結果為 false, 最後結果才能將 a 留下, 因此 EXP5 可填入 `a < b`

同樣的驗證實際情況為 a < b 時, 因 EXP5 的結果為 true, 括號內不變而兩個 a 抵銷後最後留下了 b

整理上述的原理後可得下列結果
* `EXP4 = a ^ b`, `EXP5 = a > b`

## 測驗3
### 程式碼運作原理

#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;
}

以上的程式碼其實就是老師測驗題上提供的演算法的實作

* 程式的最一開始先判斷特例情況, 若有任一數字為 0 則可以直接得到 GCD
* 當兩個數字都為偶數的情況下, $GCD(u, v)$ 可化簡為 $2 * GCD( \frac{u}{2} , \frac{v}{2})$, 第 6 行的迴圈便是為了簡化而做紀錄, u 和 v 每除了一次 2, 最後就要乘回來一次, 把次數紀錄在變數 shift
* 根據演算法提示, 只要 u 和 v 為一奇一偶的情況則可以進一步化簡
* if u is odd and v is even, then $GCD(u, v) = GCD(u, \frac{v}{2})$
* else if u is even and v is odd, then $GCD(u, v) = GCD(\frac{u}{2}, v)$
* 第 9 和 12 行的 while 是在找尋進一步化簡的可能
* 14 至 19 行則是在實現減法版本的 Euclidean algorithm, 並在每次 do-wile 的開頭嘗試化簡的可能
* if u < v, then $GCD(u, v) = GCD(u, v - u)$
* else $GCD(u, v) = GCD(v, u - v)$

* `COND = u != 1 && v` 根據 Euclidean algorithm 的終止條件而設立
* 其中 `u != 1` 是因為當 `u == 1` 時 u 的值就不會在改變了
* `RET = u << shift` 根據前面推導若在 for 迴圈的階段有做化簡則最後要乘回來

## 測驗4
### 程式碼運作原理

#include <stddef.h>
size_t naive(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    for (size_t k = 0; k < bitmapsize; ++k) {
        uint64_t bitset = bitmap[k];
        size_t p = k * 64;
        for (int i = 0; i < 64; i++) {
            if ((bitset >> i) & 0x1)
                out[pos++] = p + i;
        }
    }
    return pos;
}

上面的程式碼能夠找出在二進位表示中 bitset 的 bit 為 1 的位置, 並且將其紀錄在 out 裡面, 最後能夠根據回傳的 pos 在 out 中取出有效的紀錄

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;
}

* 使用 __builtin_ctzll 改寫後的結果如上, 只要當前的 bitset 不為 0, 就透過 __builtin_ctzll 從右往左找出第一個 bit 為 1 的位置
* 透過 left shift 將 1 移動到 __builtin_ctzll 回傳的位置, 最後在根據 XOR 的特性將對應位置的 bit 化為0, 而其他 bit 不變, 直到 bitset 歸零為止

綜合上述整理可得結果
* `EXP6 = 0b1L << __builtin_ctzll(bitset)`
## 測驗5
### 程式碼運作原理

struct rem_node {
    int key;
    int index;
    struct list_head link;
};  
    
static int find(struct list_head *heads, int size, int key)
{
    struct rem_node *node;
    int hash = key % size;
    list_for_each_entry (node, &heads[hash], link) {
        if (key == node->key)
            return node->index;
    }
    return -1;
}

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;
    }

    long long n = numerator;
    long long d = denominator;

    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++ = '.';

    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, &heads[EEE]);

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

    strcpy(p, decimal);
    return result;
}

* 程式的計算方法是模擬手算長除法時的情況
* 其中 24 ~ 33 行的部份為處理除數或被除數為零的特例, 可以直接得到結果
* 43 ~ 44 行透過將兩數相除判斷是否需要在最後結果加上負號
* 47 ~ 52 行進行了第一輪計算, 並透過 sprintf 將結果 int 的資料轉為 string 放入 result 中, 同時檢查 remainder 是否為 0, 若可以整除的話可以直接得出結果
* 54 ~ 55行透過 result 的整數部份找出放置 `'.'` 的位置後將其置入
* 57 ～ 64 行在為了後續計算建立一個 hash table, 其中 size 為 bucket 的數量
* 66行開始為長除法的計算, 長除法中判斷循環小數的方式為出現了重複的餘數
每次 for 迴圈的開始都會透過 hash 回傳的 pos 確認是否餘數已經出現過了
* 當 `pos >= 0` : 代表已能確認循環的部份, 透過回傳的 pos 先將 decimal 不循環的部份複製到 p, 之後擺上 `'('` , 把 decimal 剩下的部份還有 `')'` 跟 null terminator 放入後回傳結果
* 當 `pos == -1` : 代表尚未發現循環的部份, 因此將該輪的結果放入 hash list 中
* 84 ~ 85 行為長除法每次都需要將數字最後補零的操作
* 88 ~ 89 若能成功將餘數清為零, 則將 decimal 整個複製給 p, 最後將結果回傳

綜合上述整理可得結果
* `PPP = pos--`
* PPP 會影響擺放 `'('` 的位置, 這取決於回傳的 pos, 而 pos 又紀錄了該個 remainder 是第幾 `n` 計算的結果, 因此需要在小數後 `n` 位補上 `'('`
* `MMM = list_add, EEE = size % remainder`
* MMM 和 EEE 為在 hash list 中新增資料的方式, 由於 hash function 為計算傳入參數 `key % size` 的結果, 而在程式碼 67 行傳入的各是 size 和 remainder, 因此加入時同樣加入在 `size % remainder` 個 bucket, 另外由於是 circular doubly linked list, 因此加在尾巴或頭都可以

### 可改進之處
TODO

## 測驗6
### 程式碼運作原理

/*
 * ALIGNOF - get the alignment of a type
 * @t: the type to test
 *
 * This returns a safe alignment for the given type.
 */
#define ALIGNOF(t) \
    ((char *)(&((struct { char c; t _h; } *)0)->M) - (char *)X)

* `__alignof__` 計算的是若想對齊某資料需要花的 byte 數量
* 根據 macro 定義傳入的參數 `t` 以及 `struct` 內會將 `t` 代換掉並同時以 `t` 的資料型態宣告變數 `_h`
* 同時使用一個 literal `0` 來當載體並且計算 `_h` 與這個 `struct` 自身的差距有多少作為對齊所需的 byte 數

根據上述整理可得結果
* `M = _h`
* 因為想計算的是 `t->_h` 與 `t` 的差距, 因此填入 `_h`
* `X = 0`
* 由於前面是用 `0` 來當載體, 後面也要一致
## 測驗7
### 程式碼運作原理

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"[(8 >> div5) >> (KK3)], length);
        fmt[length] = '\0';

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

首先看過整個主程式的執行流程
* 12 ~ 13 行的 is_divisible 用來測試是 i 否為 3 或 5 的倍數, 之後根據測試結果來設定 length
* is_divisible 回傳的值為 0 或 1, 因此 14 行的操作也能看為根據測試結果將 length 乘以 2
* 17 行的部份透過 div5 和 div3 的結果取出 `"FizzBuzz%u"` 中的一部分並將複製到 fmt 中
* 剩下的部份為加入 NULL terminator 以及將其印出

可以發現關鍵在於:
* is_divisible 的實作
* 如何透過 length, div3, div5 取出 `"FizzBuzz%u"` 的片段

#### is_divisible
在閱讀了 [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/faster-remainders-when-the-divisor-is-a-constant-beating-compilers-and-libdivide/) 網頁中提出的方法後得知若想計算除法可以透過乘法的模擬得出
* $\Large \frac{n}{d} = n * \frac{2^N}{d} * \frac{1}{2^N}$

* 其中 $\Large \frac{2^N}{d}$ 是需要預計算的部份, $\Large \frac{1}{2^N}$ 可以透過 shift 得出, 因此往後我們便能只透過乘法來得出除法的結果
* 餘數的部份可從上述公式中的 LSB 乘上 d 後做 right shift 獲得

#### 控制 `"FizzBuzz%u"` 的片段
由於 `"FizzBuzz%u"` 會需要印出的片段分別為:
* Fizz: 位移量 0, 長度 4
* Buzz: 位移量 4, 長度 4
* `%u`: 位移量 8, 長度 2
* FizzBuzz: 位移量0, 長度8

需要控制的變數皆為 powers of 2, 因此可以用 8 為底搭配 right shift 的操作來取出所需片段
綜合上述討論可得：
* `KK1 = div3, KK2 = div5`
* length 是以 2 為底來做 shift 的, 而當 div3 或 div5 的值為 1 時便可以透過 left shift 變為 4 或 8
* `KK3 = div3 << 2`
* 題目已知的部份有 `(8 >> div5) >>` 先討論 div5 為 1 的情況, 結果會變成 `4 >> (KK3)`, 而這時 div3 還沒有用上, 且希望透過 div3 來控制要印出 `FizzBuzz` 或是 `Buzz`
* 這兩者的位移量分別是 0 以及 4, 所以 `KK3` 需要在真的時候產出 2 ,假的時候產出 0 的結果, 以便讓`(8 >> div5) >> (KK3)`能夠符合預期行為
* 因此 KK3 填入 `div3 << 2`