---
# System prepended metadata

title: 2022q1 Homework2 (quiz2)
tags: [linux2022]

---

# 2022q1 Homework2 (quiz2)
contributed by < [`leewei05`](https://github.com/leewei05) >

###### tags: `linux2022`

## [測驗 1](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-1)

:::info
- [x] 解釋下方程式碼運作的原理
- [ ] 比較下方實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 CS:APP 第 3 章)
- [ ] 研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用
>移動平均（Moving average)，又稱滾動平均值、滑動平均，在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數，來分析資料點的計算方法。
移動平均通常與時間序列資料一起使用，以消除短期波動，突出長期趨勢或周期。短期和長期之間的閾值取決於應用，移動平均的參數將相應地設置。例如，它通常用於對財務數據進行技術分析，如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。
:::

這個直覺的解法會有 overflow 的問題，若我們已知 a, b 數值的大小，可用下方程式避免 overflow:

```c 
#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}
```
接著我們可改寫為以下等價的實作:

下列程式碼 a 與 b 分別先除 2 再相加，當兩個數值皆為奇數時平均數會少加 1，故透過 `a & b & 1` 來判斷是否把少加的 1 加回去。

```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    //                            EXP1
    return (a >> 1) + (b >> 1) + (a & b & 1);
    // a = 6, b = 4, avg = 3 + 2 + 0 = 5
    // a = 6, b = 3, avg = 3 + 1 + 0 = 4
    // a = 5, b = 3, avg = 2 + 1 + 1 = 4
}
```

根據[數值系統的 bit-wise operator 筆記](https://hackmd.io/@sysprog/c-numerics#%E9%81%8B%E7%94%A8-bit-wise-operator)，運用加法器的邏輯思考。兩數的和為 `a ^ b`，兩數的進位為 `(a & b) << 1`，可得 `a + b =  a ^ b + (a & b) << 1`。

```c
(a + b) / 2 = (a ^ b + (a & b) << 1) >> 1
            = (a & b) + ((a ^ b) >> 1)
```
`EXP2` 為 `a & b`，`EXP3` 為 `a ^ b`。

```c
uint32_t average(uint32_t a, uint32_t b)
{
    //      EXP2       EXP3
    return (a & b) + ((a ^ b) >> 1);
}
```

### 編譯器輸出結果分析

環境：Ubuntu 20.04.3 LTS
編譯器版本：gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0

```c
// avg.c
#include <stdio.h>
#include <stdint.h>

uint32_t average(uint32_t low, uint32_t high)
{
    return low + (high - low) / 2;
}

uint32_t average_bitwise(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (a & b & 1);
}

uint32_t average_bitadder(uint32_t a, uint32_t b)
{
    return (a & b) + ((a ^ b) >> 1);
}

int main()
{
    int low = 3;
    int high = 5;
    printf("average is %u", average(low, high));

    return 0;
}
```

gdb 反組譯結果，或是可以透過 `gcc -Og -S avg.c` 輸出組合語言。gcc 預設是匯出 ATT 格式， Intel 格式的則是可以透過 `-masm=intel` 來產生。

```shell
$ gcc -g -o avg -O2 avg.c

$ gdb -q avg
Reading symbols from avg...
(No debugging symbols found in avg)
(gdb) break average
Breakpoint 1 at 0x1149
(gdb) run
Starting program: /home/lee/dev/playground/average/avg

Breakpoint 1, average (low=21845, high=1431654832) at avg.c:5
5       {
(gdb) disassemble
Dump of assembler code for function average:
=> 0x0000555555555149 <+0>:     endbr64
   ...
   0x0000555555555167 <+30>:    retq
End of assembler dump.
```

閱讀 [Intel IA-32 規格書](https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html) 以及 CS:APP 第三章並試著解讀以下的組合語言指令。首先分析 `avg.s` 的內容，`LFB` 以及 `LFE` 分別是 [gcc](https://github.com/gcc-mirror/gcc/blob/releases/gcc-9/gcc/dwarf2out.c#L298) 編譯時根據 [DWARF(除錯輸出格式)](http://eagercon.com/dwarf/dwarf-2.0.0.pdf) 所產生的 label (`.L` 為 [local label](https://sourceware.org/binutils/docs/as/Symbol-Names.html#Symbol-Names))，分別代表函式的開始以及結束。

> Local symbols are defined and used within the assembler, but they are normally not saved in object files. Thus, they are not visible when debugging. 

因為 `gcc -S` 只會編譯 (compile) 程式碼並輸出組合語言，尚未進行組譯 (assemble) 以及連結 (link)，所以可以直接看到組合語言用到的 local label。

```shell
# avg.s
average:
.LFB23:
        ...
.LFE23:
```

`.cfi` 代表 DWARF 所定義的 [`Call Frame Instruction(CFI)`](http://eagercon.com/dwarf/dwarf-2.0.0.pdf)：

> Debuggers often need to be able to view and modify the state of any subroutine activation that is on the call stack. An activation consists of:
• A code location that is within the subroutine. This location is either the place where the
program stopped when the debugger got control (e.g. a breakpoint), or is a place where a
subroutine made a call or was interrupted by an asynchronous event (e.g. a signal).
• An area of memory that is allocated on a stack called a ‘‘call frame.’’ The call frame is
identified by an address on the stack. We refer to this address as the Canonical Frame
Address or CFA.
• A set of registers that are in use by the subroutine at the code location.

根據以上的描述，可以理解成 CFI 為一個子程序 (subroutine) 的起始或是結束觸發點。一個配置於 stack memory 的記憶體區塊稱作 `call frame`，而此 `call frame` 的記憶體位址我們稱作 `Canonical Frame Address(CFA)`。回到下方的組合語言，[`.cfi-startproc`](https://sourceware.org/binutils/docs/as/CFI-directives.html#CFI-directives) 以及 [`.cfi-endproc`](https://sourceware.org/binutils/docs/as/CFI-directives.html#CFI-directives) 分別是組合語言中定義的 CFI directives (指令)，代表著函式的起始以及結束。

> .cfi_startproc is used at the beginning of each function that should have an entry in .eh_frame. It initializes some internal data structures. Don’t forget to close the function by .cfi_endproc.

```shell
# avg.s
average:
.LFB23:
        .cfi_startproc
        endbr64
        ...
        .cfi_endproc
.LFE23:
```

在了解 `endbr64` 指令以前，需要先知道 [ROP](https://en.wikipedia.org/wiki/Return-oriented_programming) 以及 [COP/JOP](https://www.comp.nus.edu.sg/~liangzk/papers/asiaccs11.pdf) 這兩項攻擊手法。黑客可以藉由上述提到的手法竄改原先的指令(e.g. RET, CALL, JUMP)來操作既有的指令。而 Intel 處理器提供的 Control-Flow Enforcement Technology (CET) 則是用來防範上述提到的攻擊，以下是 CET 所提供的兩項主要功能：
- Shadow stack: Return address protection to defend against ROP
- Indirect branch tracking: Free branch protection to defend against COP/JOP

`endbr64` 則是隸屬於 [Indirect branch tracking](https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html) 的指令。

> 18.1.2 Indirect Branch Tracking
> 
> The `ENDBRANCH` instruction is a new instruction that is used to mark valid jump target addresses of indirect calls and jumps in the program. ... The CPU implements a state machine that tracks indirect `JMP` and `CALL` instructions. When one of these instructions is executed, the state machine moves from `IDLE` to `WAIT_FOR_ENDBRANCH` state. In `WAIT_FOR_ENDBRANCH` state the next instruction in the program stream must be an `ENDBRANCH`. If the next instruction is not an `ENDBRANCH`, the processor causes a control protection exception (#CP); otherwise, the state machine moves back to `IDLE` state.

接著我們看 average 函式當中的指令。`mov`


```shell
0000000000000000 <average>:
   0:   f3 0f 1e fa             endbr64
   4:   89 f0                   mov    %esi,%eax
   6:   29 f8                   sub    %edi,%eax
   8:   d1 e8                   shr    %eax
   a:   01 f8                   add    %edi,%eax
   c:   c3                      retq
   d:   0f 1f 00                nopl   (%rax)
```

```shell
0000000000000010 <average_bitwise>:
  10:   f3 0f 1e fa             endbr64
  14:   89 f8                   mov    %edi,%eax
  16:   89 f2                   mov    %esi,%edx
  18:   21 f7                   and    %esi,%edi
  1a:   d1 e8                   shr    %eax
  1c:   d1 ea                   shr    %edx
  1e:   83 e7 01                and    $0x1,%edi
  21:   01 d0                   add    %edx,%eax
  23:   01 f8                   add    %edi,%eax
  25:   c3                      retq
  26:   66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
  2d:   00 00 00

0000000000000030 <average_bitadder>:
  30:   f3 0f 1e fa             endbr64
  34:   89 f8                   mov    %edi,%eax
  36:   21 f7                   and    %esi,%edi
  38:   31 f0                   xor    %esi,%eax
  3a:   d1 e8                   shr    %eax
  3c:   01 f8                   add    %edi,%eax
  3e:   c3                      retq
```


---

## [測驗 2](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-2)

:::info
延伸問題:

- [x] 解釋下方程式碼運作的原理
- [ ] 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
- [ ] Linux 核心也有若干 branchless / branch-free 的實作，例如 lib/sort.c:

```c 
/*
 * Logically, we're doing "if (i & lsbit) i -= size;", but since the
 * branch is unpredictable, it's done with a bit of clever branch-free
 * code instead.
 */
__attribute_const__ __always_inline
static size_t parent(size_t i, unsigned int lsbit, size_t size)
{
    i -= size;
    i -= size & -(i & lsbit);
    return i / 2;
}
```
請在 Linux 核心原始程式碼中，找出更多類似的實作手法。請善用 git log 檢索。

:::

```c
int32_t min(int32_t a, int32_t b) {
    int32_t diff = (a - b);
    return b + (diff & (diff >> 31));
}
```

改寫〈解讀計算機編碼〉一文的「不需要分支的設計」一節提供的程式碼 min，我們得到以下實作 (max):

> EXP4 為 a 和 b 進行某種特別 bitwise 操作，限定用 OR, AND, XOR 這三個運算子
> EXP5 為 a 和 b 的比較操作，亦即 logical operator，限定用 >, <, ==, >=, <=, !=

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

- 假設 a 是比較大的值，右邊的 `((EXP4) & -(EXP5))` 會需要等於 0，因為 `a ^ 0 = a`
- 假設 b 是比較大的值，右邊的 `((EXP4) & -(EXP5))` 會需要是 `b - a`

> 6.5.8 Relational operators
> Each of the operators < (less than), > (greater than), <= (less than or equal to), and >=
(greater than or equal to) shall yield 1 if the specified relation is true and 0 if it is false.92)
The result has type int.

根據上述規格書的內容，`EXP5` 只會返回 1 或是 0。

- 假設 `EXP5 == 1`，則可以得到 `((EXP4) & -1)`，亦等於 `((EXP4) & 0xFFFF)`
- 假設 `EXP5 == 0`，則可以得到 `((EXP4) & 0x0000)`。從第二個條件回推，任何數跟 0 做 AND 運算會等於 0，條件二即符合 `max = a`。
 
根據現有條件，可以推測出 `EXP5` 為 `a <= b`，如果 a 等於 b 那直接回傳 a 也合理。但題目有說到以最精簡的方式撰寫程式碼，那其實 `a < b` 即可。`EXP4` 為 `a ^ b` 也等同於 `b - a`，任何數跟 `0xFFFF` 做 AND 運算都會返回自己。

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

### 32 位元無號/有號整數實作

---

## [測驗 3](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-3)

:::info
- [x] 解釋下方程式運作原理;
- [x] 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
- [ ] Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景。
:::

完整程式碼

```c
#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 則返回另一個非零的變數。如果兩個變數皆為偶數則兩個變數皆除以二，並且把除以二的次數記錄到 `shift`。

```c
    if (!u || !v) return u | v;
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
```

如果 `u` 為偶數則除以二。 `do ... while` 的迴圈裡頭則是實作 [Euclid's algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm#:~:text=In%20mathematics%2C%20the%20Euclidean%20algorithm,them%20both%20without%20a%20remainder.)。根據 Euclid's algorithm 的描述可以推斷`COND` 為 `u != v && u && v`，`RET` 為 `u << shift`。最後需要把一開始兩邊皆除以二的次數乘回 `u` 才會是最大公因數。

```c
    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 (u != v && u && v);
    return u << shift;
```

:::danger
COND = v

不需要 u != v 因為如果 u == v，COND = v 會直接跳出 while loop。而 COND = v 是因為在做輾轉相除法時，只要當 u - v 為 0 時就會跳出 while loop。
:::

### 透過 `__builtin_ctz` 改寫 GCD

> Built-in Function: int __builtin_ctz (unsigned int x)
Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.
> Built-in Function: int __builtin_ctzll (unsigned long long)
Similar to __builtin_ctz, except the argument type is unsigned long long.

根據 gcc 官方文件的描述，可以透過 `__builtin_ctz` 來取得無號數 `x` 的 trailing 0 bits，換句話說即等於 `shift` 的值。而原本題目給定的變數是 `unsigned long long`，即替換 `__builtin_ctz` 為 `__builtin_ctzll`。

```c
#include <stdint.h>
#include <stdio.h>
#define MIN(a,b) (((a)<(b))?(a):(b))

uint64_t gcd64(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int u_ctz = __builtin_ctzll(u);
    int v_ctz = __builtin_ctzll(v);
    u >>= u_ctz; 
    v >>= v_ctz;
    do {
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (v);
    return u << MIN(u_ctz, v_ctz);
}
```

---

## [測驗 4](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-4)

:::info
- [x] 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
- [ ] 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density;
- [ ] 思考進一步的改進空間;
- [ ] 閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例;
:::

其中第 9 行的作用是找出目前最低位元的 1，並紀錄到 t 變數。舉例來說，若目前 bitset 為 $000101_b$，那 t 就會變成 $000001_b$，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。

請補完程式碼。書寫規範:

- bitwise 運算子和運算元之間用一個半形空白區隔，如: bitset | 0x1
- 考慮到 -bitwise 的特性

```c=
#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;
}
```

考慮到 `-bitset` 會對 `bitset` 做二的補數，透過下列程式範例理解：

```c
#include <stdio.h>
#include <stdint.h>

int main()
{
    uint8_t biset = 5;
    printf("%u\n", (int8_t)biset);
    printf("%u\n", (uint8_t)-biset);
    printf("%u\n", (uint8_t)-biset&biset);
    return 0;
}

//5
//251
//1
```

:::danger
EXP6
bitset & -bitset
-bitset & bitset
:::

真實案例：Bloomfilter, Compression

## [測驗 5](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-5)

:::info
- [ ] 解釋上述程式碼運作原理，指出其中不足，並予以改進
例如，判斷負號只要寫作 bool isNegative = numerator < 0 ^ denominator < 0;
搭配研讀 The simple math behind decimal-binary conversion algorithms
- [ ] 在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景
:::

[LeetCode 166. Fraction to Recurring Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal/)

給定 numerator (分子)以及 denominator (分母)，返回小數的字串。如果遇到重複的小數迴圈，則把重複的部分以括號 `()` 表示。

從建立的 Hash table 中找尋特定的 key。

```c
#include <stdbool.h>                       
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
    
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)
{
```

分母為零，則直接返回 `\0` (null terminated string)；分子為零，則返回 `0`。雖然在 Leetcode 題目中有提到輸入的分母並不會為 0，但保險起見，還是檢查分母是否為零以免出現非預期行為。

> Constraints
> - -2^31 <= numerator, denominator <= 2^31 - 1
> - denominator != 0

根據 C 語言規格書，第二個運算元如果為 0 則此行為是 `undefined`。

> The result of the / operator is the quotient from the division of the first operand by the
second; the result of the % operator is the remainder. In both operations, if the value of
the second operand is zero, the behavior is undefined.

```c 
    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;
```

> 6.5.3.3 Unary arithmetic operators
> The result of the unary - operator is the negative of its (promoted) operand. The integer
promotions are performed on the operand, and the result has the promoted type.

Promote 在此解釋為 **型別提升**。例如 `float, double, long double` 皆為浮點數，假設 `float` 跟 `double` 做運算，需要先對 `float` 做型別提升，否則運算的結果會不如預期，因為 `float` 跟 `double` 所佔有的位元組空間不同。

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

> 6.5.3.4 The sizeof and _Alignof operators
> The sizeof operator yields the size (in bytes) of its operand, which may be an
expression or the parenthesized name of a type

判別小數為正數或是負數。`p` 為 pointer to char，在 x84_64 位元的儲存空間為 8 bytes。

> 6.5.3.2 Address and indirection operators
> The unary * operator denotes indirection. If the operand points to a function, the result is
a function designator; if it points to an object, the result is an lvalue designating the
object. If the operand has type ‘‘pointer to type’’, the result has type ‘‘type’’.

根據以上敘述，`p` 為 pointer to char type 則 `*p` 為 char type。如果 `sign` 為負數，則把 `'-'` 寫入至第一個 char slot，即 `result[0]`，並且把 `p` 指標指向 `result[1]`。

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

可以透過下方的小程式了解其中的關係：

```c
#include <stdio.h>
#include <stdlib.h>

int main()
{
    int size = 1024;
    char *result = malloc(size);
    char *p = result;

    printf("result[0]'s value is %c \n", result[0]);
    printf("result[0]'s address %p \n", &result[0]);
    printf("*p's value is %c \n", *p);
    printf("*p's address %p \n", &(*p));
    *p++ = 'a';
    printf("result[0]'s value is %c \n", result[0]);
    printf("*p's address %p \n", &(*p));
    printf("result[1]'s address %p \n", &result[1]);

    return 0;
}
```

可以看到輸出結果如我們預期，一開始 `p` 是指向 `result[0]`。`*p++` 是指派 `a` 至 `result[0]`，再指派 `p` 的指標至下一個 `char` 的起始位置。

```shell
result[0]'s value is  
result[0]'s address 0x55bda8fab2a0 
*p's value is  
*p's address 0x55bda8fab2a0 
result[0]'s value is a 
*p's address 0x55bda8fab2a1 
result[1]'s address 0x55bda8fab2a1 
```

計算除完的結果 (division) 以及餘數 (remainder)，如果整除則直接返回 division。

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

> 7.19.6.6 The sprintf function

```c
#include <stdio.h>
int sprintf(char * restrict s,
const char * restrict format, ...);
```

> 2 The sprintf function is equivalent to fprintf, except that the output is written into
an array (specified by the argument s) rather than to a stream. A null character is written
at the end of the characters written; it is not counted as part of the returned value. If
copying takes place between objects that overlap, the behavior is undefined.
3 The sprintf function returns the number of characters written in the array, not
counting the terminating null character, or a negative value if an encoding error occurred.

> 6.5.2.1 Array subscripting
> A postfix expression followed by an expression in square brackets [] is a subscripted
designation of an element of an array object. The definition of the subscript operator []
is that E1[E2] is identical to (*((E1)+(E2))). Because of the conversion rules that
apply to the binary + operator, if E1 is an array object (equivalently,apointer to the
initial element of an array object) and E2 is an integer, E1[E2] designates the E2-th
element of E1 (counting from zero).

`sprintf` 將會把 `division` 寫入至 `p (pointer to char)` 現在的位置，也就是 `result[0]` (正數)或是 `result[1]` (負數)，並再最後加入 `.` 字元。

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

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

初始化 hash table 的各個 hash slots。

```c
    /* 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]);
```

可以判斷如果 `pos` 小於 0 則表示沒有在 hash table 找到 `remainder`，所以需要把目前 `remainder` 的值加入至目前 hash slot 所處的 linked list 中。而 `find()` 中的 hash function 為 `int hash = key % size;`

根據上述的描述，可以推測 `MMM` 為 `list_add`，而 `EEE` 為 `&heads[remainder % size]`。

```c
        int pos = find(heads, size, remainder);
        if (pos >= 0) {
            ...
        }
        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;
```

如果 pos 有值則表示為有循環小數，所以需要先把循環小數前的數寫到 `p`，故 `PPP = pos--`。

```c
    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;
        }
        ...
    }

    strcpy(p, decimal);
    return result;
}
```

---

## [測驗 6](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-6)

:::info
- [x] 請寫出 M & X 並解釋上述程式碼運作原理
- [ ] 在 Linux 核心原始程式碼中找出 __alignof__ 的使用案例 2 則，並針對其場景進行解說
- [ ] 在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集，探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻，儘量共用相同的巨集
:::

```c
/*
 * 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(t)` 即為計算出 type t 的 alignment。

> 6.3.2.3 Pointers
> An integer may be converted to any pointer type. Except as previously specified, the
result is implementation-defined, might not be correctly aligned, might not point to an
entity of the referenced type, and might be a trap representation.5

```c
        ((struct { char c; t _h; } *)0     // null pointer contant
        &((struct { char c; t _h; } *)0->M // dereference M(_h)
(char *)&((struct { char c; t _h; } *)0->M // cast to pointer to char(_h)
```

下列相減要得出 type t 的 alignment。兩項相減需要為 type t 的 alignment，故 X 為 0。

```c
((char *)(...) - (char *)X)
```

可以透過下列實驗得證，為什麼 dereference type t 的記憶體位置相減會得到 type t 的 alignment。

```c
#include <stdio.h>

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

int main()
{
    struct foo {
        char c; // 1 byte
        // 1 byte padding
        short b; // 2 byte
    };
    
    struct foo1 {
        char c; // 1 byte
        // 7 bytes padding
        long b; // 8 byte
    };
    
    struct foo f;
    struct foo1 f1;
    printf("size of struct foo: %lu\n", sizeof(f));
    printf("%p\n", &f.c);
    printf("%p\n", &f.b);
    printf("gcc built-in alignof: %lu\n", __alignof__(short));
    printf("ALIGNOF: %lu\n", ALIGNOF(short));
    
    printf("size of struct foo1: %lu\n", sizeof(f1));
    printf("%p\n", &f1.c);
    printf("%p\n", &f1.b);
    printf("gcc built-in alignof: %lu\n", __alignof__(long));
    printf("ALIGNOF: %lu\n", ALIGNOF(long));

    return 0;
}

/*
size of struct foo: 4
0x7ffdfd970c4c
0x7ffdfd970c4e
gcc built-in alignof: 2
ALIGNOF: 2

size of struct foo1: 16
0x7ffdfd970c50
0x7ffdfd970c58
gcc built-in alignof: 8
ALIGNOF: 8
*/
```

--

## [測驗 7](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-7)

:::info
- [ ] 解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差
    - 避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf
- [ ] 分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless;
    - 參照 fastmod: A header file for fast 32-bit division remainders on 64-bit hardware
- [ ] 研讀 The Fastest FizzBuzz Implementation 及其 Hacker News 討論，提出 throughput (吞吐量) 更高的 Fizzbuzz 實作
- [ ] 解析 Linux 核心原始程式碼 kernel/time/timekeeping.c 裡頭涉及到除法運算的機制，探討其快速除法的實作 (注意: 你可能要對照研讀 kernel/time/ 目錄的標頭檔和程式碼)過程中，你可能會發現可貢獻到 Linux 核心的空間，請充分討論
:::

以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (bitwise.c)

`KK1 = div5`, `KK2 = div3`, `KK3 = div3 << 2`

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