# 2022q1 Homework2 (quiz2)
contributed by < `jim12312321` >
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz2)

## 測驗 1 ： 兩數取平均

#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
    return (a >> 1) + (b >> 1) + (EXP1);
}

解析：
在 2 進位中左移/右移 1 個 bit ，相當於對原本的數字乘/除 2 ，因此 `(a >> 1) + (b >> 1)` 就相當於 $\dfrac{a}{2}+\dfrac{b}{2}$ 。

但是要特別注意一點，**整數除法是無條件捨去**，因此當 a 和 b 同為奇數時，需補 1。

==因此可以知道， `EXP1` 需要判斷 a 和 b 同為奇數時等於 1 ，否則等於 0 。==

`EXP1`
$\rightarrow$ a & b & 1

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

解析：
考慮 1 個 bit 的平均，可知首先要兩 bit 相加(不考慮進位)，則這個操作等同取 `^` ，接著要考慮是否有可能進位，這個操作等同取 `&` ，之後還要除 2 (對應題目中的 `>> 1`) 。

操作的步數與題目要求的空格數吻合，我們可以合理猜測在 `EXP2` 和 `EXP3` 中有一個為 `a ^ b` ，另一個為 `a & b` ！

接著繼續考慮 1 個 bit 的平均，並以 1+1 為例。

依照取平均的正常流程可知步驟應為：
1.兩數相加( 1 ^ 1)
2.補上進位( (1 ^ 1) + (1 & 1) << 1)
3.除以 2( ((1 ^ 1) + (1 & 1) << 1) >> 1)

接著我們對 `((1 ^ 1) + (1 & 1) << 1) >> 1` 進行化簡。
`((1 ^ 1) + (1 & 1) << 1) >> 1`
`= (1 ^ 1) >> 1 + (1 & 1) << 1 >> 1` (乘法分配律)
`= (1 ^ 1) >> 1 + (1 & 1)` (化簡)

==因此根據上述化簡，我們可以得知==
`EXP2`
$\rightarrow$ a & b
`EXP3`
$\rightarrow$ a ^ b

### 延伸問題 2
#### 設定
以下使用引數 `-O3 -S -fverbose-asm`
- `-O3`
- 使用最高等級最佳化
- `-S`
- 輸出組合語言代碼
- `-fverbose-asm`
- 輸出更多資訊
#### 組合語言代碼解析
- 第一小題組合語言代碼

movl    %edi, %eax      # a, tmp91
movl    %esi, %edx      # b, tmp92
andl    %esi, %edi      # b, tmp94
shrl    %eax            # tmp91
shrl    %edx            # tmp92
andl    $1, %edi        #, tmp95
addl    %edx, %eax      # tmp92, tmp93
addl    %edi, %eax      # tmp95, tmp90
ret

步驟解析：
- `movl %edi, %eax`
- 將 a 中存的值傳給暫存器 `％eax`
- `movl %esi, %edx`
- 將 b 中存的值傳給暫存器 `％edx`
- `andl %esi, %edi`
- b &= a (a & b)
- `shrl %eax`
- 將暫存器 `%eax` 右移 1 個 bit (a >> 1)
- `shrl %edx`
- 將暫存器 `%edx` 右移 1 個 bit (b >> 1)
- `andl $1, %edi`
- `%edx` &= 1 (a & b & 1)
- `addl %edx, %eax`
- `%eax` += `%edx` ((a >> 1) + (b >> 1))
- `addl %edi, %eax`
- `%eax` += b ((a >> 1) + (b >> 1) + (a & b & 1))
- `ret`
- return

- 第二小題組合語言代碼

movl    %edi, %eax      # a, tmp89
andl    %esi, %edi      # b, tmp91
xorl    %esi, %eax      # b, tmp89
shrl    %eax            # tmp90
addl    %edi, %eax      # tmp91, tmp88
ret

步驟解析：
- `movl %edi, %eax`
- 將 a 中存的值傳給暫存器 `％eax`
- `andl %esi, %edi`
- a &= b (a & b)
- `xorl %esi, %eax`
- `%eax` ^= b (a ^ b)
- `shrl %eax`
- 將暫存器 `%eax` 右移 1 個 bit ((a ^ b) >> 1)
- `addl %edi, %eax`
- `%eax` += a ((a & b) + ((a ^ b) >> 1))
- `ret`
- return
>參考資料：
>- [x86 Instruction Set Reference](https://c9x.me/x86/)
>- [3 GNU lightning’s instruction set](https://www.gnu.org/software/lightning/manual/html_node/The-instruction-set.html#The-instruction-set)
>- [AT&T assembly syntax and IA-32 instructions ](https://gist.github.com/mishurov/6bcf04df329973c15044)

:::info
雜記︰
我其實沒有查到 x86_64-linux-gnu 的完整組合語言指令集，只能透過一些上面的參考資料去腦補指令集的操作流程，如果後續有找到會再補充上來。
:::

:::warning
TODO: 延伸問題 3
:::

---

## 測驗 2 ：兩數取最大值

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

解析︰
XOR 可理解為「找不同」，因此 `((EXP4) & -(EXP5))` 中的值應為 a 與最大值間相同位元處是 0 ，不同處是 1 的數字。

>e.g.
>1.
> &emsp;a = 15, b = 14
> &emsp;a 為最大值，因此 `((EXP4) & -(EXP5))` 應為 $0000_2$
>2.
> &emsp;a = 14, b = 15
> &emsp;b 為最大值，因此 `((EXP4) & -(EXP5))` 應為 $0001_2$

由上面的例子我們可以推知，當 a > b 時，`((EXP4) & -(EXP5))` 應該要是全為 0 的 bitmask ，而當 a < b 時，`((EXP4) & -(EXP5))` 應該要是 a ^ b 的 bitmask 。

另外根據題目要求我們可以得知 `EXP5` 為 `a` 和 `b` 的比較操作，因此 `-(EXP5)` 只有兩種可能的值，即為 0 或 -1 ，而 0 就是全為 0 的 bitmask ， -1 是全為 1 的 bitmask。

==因此我們可以得知 `EXP4` 的作用為取出 a,b 間的不同， `EXP5` 的作用為製造 bitmask ，使特定情況下 `EXP4` 能發揮作用==

`EXP4`
$\rightarrow$ a ^ b

`EXP5`
$\rightarrow$ a < b or a <= b

### 延伸問題 2

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

解析：
因為在有號數或無號數時， XOR 都能發揮「找不同」的作用，因此以下就後面的 `a < b` 進行討論。
在有號數的版本中情況和無號數相同，當 `a >= b` 應該回傳 `a` ，因此此時的 bitmask （原本 `EXP5` 的位置） 應該應該輸出 0 ，使得回傳值變成 `a ^ 0` 。當 `a < b` 應該回傳 `b` ，因此此時的 bitmask （原本 `EXP5` 的位置） 應該應該輸出 -1 ，使得回傳值變成 `a ^ (a ^ b)`。

因此有號數的版本中原先 `EXP5` 的位置中一樣可填入 `a < b` 或 `a <= b` 達成取最大值的效果。

:::warning
TODO: 延伸問題 3
:::

---

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

解析：

首先先來看在 [測驗 3](https://hackmd.io/@sysprog/linux2022-quiz2#%E6%B8%AC%E9%A9%97-3) 中提供的 GCD 演算法
> 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\times gcd(\dfrac{x}{2},\dfrac{y}{2})$ because 2 is a common divisor.<br>Multiplication with 2 can be done with bitwise shift operator.
> 4. If x is even and y is odd, $gcd(x,y) = gcd(\dfrac{x}{2},y)$.
> 5. On similar lines, if x is odd and y is even, then $gcd(x,y) = gcd(x,\dfrac{y}{2})$. It is because 2 is not a common divisor.

了解完演算法後，接著就來看程式碼的實現方式！

if (!u || !v) return u | v;

這行對應演算法中的第 1 步和第 2 步。

for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }

這段中可以先看迴圈的中止條件 `!((u| v) & 1)` ，從這裡可以發現，當 `u` 和 `v` 同時為偶數時迴圈繼續，否則終止，因此此時 `shift` 就是用來計算直到 `u` 和 `v` 不同時為偶數時，他們兩個間的最大公因數是 2 的幾次方。對應演算法中的第 3 行。

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

接著這段是在把 `u` 中含有的 2 因數全部去除 (因為上一段中已經確定 `u` 和 `v` 沒有 2 的因數了)，可以把這段對應到演算法中的第 4 行。
(當然此時我們並不能確定到底 `u` 或 `v` 是奇或偶，但在執行完這段後，我們可以確定 `u` 一定為奇數)

do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (COND);

接著由於是 do-while 迴圈，因此我們先看內容最後再來看 `COND` 。首先根據驗算法第 5 行的做法，將 `v` 也變成奇數，此時可以確定 `u` 和 `v` 都是奇數。接下來的一段 if-else 就是透過相減，確保 `u` 是目前 `u` 和 `v` 的最大奇數公因數，因此終止條件 (`COND`) 就是用來判斷是否還需要繼續找最大奇數公因數。

`COND`
$\rightarrow$ v

而當迴圈終止時，此時的 `u` 就是原本 `u` 和 `v` 間的最大奇數公因數。因此要再將原先算好的兩者之間最大 2 的次方的公因數補回去。

`RET`
$\rightarrow$ u << shift

### 延伸問題 2
>在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升

int min(int a, int b)
{
    return a ^ ((a ^ b) & -(a > b));
}

uint64_t gcd64_ctz(uint64_t u, uint64_t v)
{
    if (!u || !v) return u | v;
    int shift;
    /*because __builtin_ctz(0) is undefined behavior*/
    if (u)
        shift = __builtin_ctz(u);
    if (v)
        shift = min(shift,__builtin_ctz(v));

    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 (v);
    return u << shift;
}

搭配 `min` 取得兩數之間最小的 `ctz` 。

- 效能分析
- 使用方法

    $perf record -F 'max' ./your_executable_file
    $perf report

- 使用數字

    u = 6515616114612142224
    v = 2164452161421431516

- `gcd64`

- `gcd64_ctz`

### 延伸問題 3
>Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景。

#### gcd 實作手法解析

在 [lib/math/gcd.c](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c) 中有提供兩種實作方法，但本質上沒什麼差別，只差在判斷 `__ffs` 能不能用。

在進入程式碼解釋及探討應用場景前，我們先來看看 `__ffs` 是什麼？
`__ffs(unsigned long word)` 的作用找到 `word` 中第 1 個 1 的位置，要注意當 `word` 中沒有任何 1 的時候， `__ffs(unsigned long word)` 屬於未定義行為。
> 參考：
> [__ffs](https://www.kernel.org/doc/htmldocs/kernel-api/API---ffs.html)

:::info
備註：
[ffs (linux)](https://github.com/torvalds/linux/blob/705d84a366cfccda1e7aec1113a5399cd2ffee7d/arch/parisc/include/asm/bitops.h) 與 [ffs (wiki)](https://en.wikipedia.org/wiki/Find_first_set) 中有一點落差，直接看例子能直觀的感受。
> e.g.
> $000100_2$
> In Linux:&emsp;&emsp;&emsp;&emsp;&emsp;ffs $\rightarrow$ 2
> In Wiki example: &emsp;ffs $\rightarrow$ 3
:::

接著來看在 [lib/math/gcd.c](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c) 中提供的 gcd 實現演算法吧！

unsigned long gcd(unsigned long a, unsigned long b)
{
	unsigned long r = a | b;

	if (!a || !b)
		return r;

	b >>= __ffs(b);
	if (b == 1)
		return r & -r;

	for (;;) {
		a >>= __ffs(a);
		if (a == 1)
			return r & -r;
		if (a == b)
			return a << __ffs(r);

		if (a < b)
			swap(a, b);
		a -= b;
	}
}

由於 gcd 的演算法上面已經列過，這邊就不重複說明。要進入解析之前，可以先來看看在程式碼中每當出現 `b == 1` 或 `a == 1` 時就會出現的 `r & -r` 是什麼。 `r = a | b` 就跟原本題目中程式碼的 `u | v` 的效果一樣，但是在特定條件下要回傳的 `r & -r` 就是很棒的寫法了(至少我這麼覺得)， 由於 2 補數的運算邏輯，因此 `r & -r` 在 `a && b` 的情況下必為 `a` 和 `b` 之間的最大 2 的次方的公因數。

因此當 `((b >>= __ffs(b)) == 1) || ((a >>= __ffs(a)) == 1)` 時就表示兩者間沒有除了 `r & -r` 以外的其他公因數了(類似題目中 `shift` 的作用)，因此要回傳 `r & -r` 。

接著在理解 `r` 跟 `__ffs` 的作用後，就能直覺的了解當 `a == b` 時，回傳 `a << __ffs(r)` 的用意了(將最大 2 的次方的公因數補回去當前的最大公因數！)。

#### 應用場景
先來個簡單的，以下程式碼是利用 [lib/math/gcd.c](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c) 中提供的 gcd 實作 Lowest common multiple (最小公倍數)。
> 來源： [linux/lib/math/lcm.c](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/lib/math/lcm.c)

/* Lowest common multiple */
unsigned long lcm(unsigned long a, unsigned long b)
{
	if (a && b)
		return (a / gcd(a, b)) * b;
	else
		return 0;
}
EXPORT_SYMBOL_GPL(lcm);

可以看到這個想法很簡單，也很直覺。

接著來看到在 [linux/drivers/iio/afe/iio-rescale.c](https://github.com/torvalds/linux/blob/79160a603bdb51916226caf4a6616cc4e1c58a58/drivers/iio/afe/iio-rescale.c) 中的 gcd 應用。

> 節錄自 [linux/drivers/iio/afe/iio-rescale.c](https://github.com/torvalds/linux/blob/79160a603bdb51916226caf4a6616cc4e1c58a58/drivers/iio/afe/iio-rescale.c) 第 196 至 211 行。

/*
 * Calculate the scaling factor, 1 / (gain * sense), or
 * gain_div / (gain_mult * sense), while trying to keep the
 * numerator/denominator from overflowing.
 */
factor = gcd(sense, 1000000);
rescale->numerator = 1000000 / factor;
rescale->denominator = sense / factor;

factor = gcd(rescale->numerator, gain_mult);
rescale->numerator /= factor;
rescale->denominator *= gain_mult / factor;

factor = gcd(rescale->denominator, gain_div);
rescale->numerator *= gain_div / factor;
rescale->denominator /= factor;

先不管 iio 到底是什麼(我也不懂...)，但是從註解還有程式碼中我們可以很清楚的看到，透過 gcd 能幫助找到兩特定值之間的最大公因數，進而防止某些值 overflow 。

---

## 測驗 4 ： BitMap

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

從 naive 的版本中可以發現，整個程式的目的是為了紀錄 bitmap 裡每個 bitset 中的第一個 1 位於從最低位元算起的哪個位置，若 bitset 中沒有 1 則不紀錄，最後回傳有多少不為 0 的 bitset 。

在簡單了解程式碼的目的後，我們再來看 improved 的板本。

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

再根據題目的提示後可知， `EXP6` 的目的在於找出目前最低位元的 1 ，其他更高位元全部清 0 。

若達成這種效果可以利用 `&` 搭配反轉所有 bits 僅留最低位元的 1 來完成。

`EXP6`
$\rightarrow$ bitset & -bitset

#### 應用場景

我暫時找不到該下什麼關鍵字才能更明確的找到應用實例。因此以下我先講我覺得這樣的程式碼能怎樣被應用。

- 壓縮

能把一個 bitmap 轉換成用 `out` 、 `pos` 和將裡面的每筆資料進行去除 tailing zeros 之後的 bitmap 就能表示的方式，能壓縮原本 bitmap 所需的空間，若 bitmap 越稀疏，則壓縮效果越好。

> 以下例子直接沿用上面的程式碼及程式邏輯
> e.g.
> 假設今天有一個 bitsize 為 4 的bitmap `bm`
>
> bm:
> >0xFEDCBA9876543210
> 0xEFCDAB8967452301
> 0x1111000011110000
> 0x8888888888888888
>
>經過上面程式運算之後可得 `out` 和 `pos`
>
> pos = 4
> >out[0] = $0\times64+4 = 4$
> out[1] = $1\times64+0 = 64$
> out[2] = $2\times64+16 = 144$
> out[3] = $3\times64+3 = 195$
>
>搭配經過對每個內容去除 tailing zeros後的 `bm_rtz`
>
> bm_rtz:
> >0x0FEDCBA987654321
> 0xEFCDAB8967452301
> 0x0000111100001111
> 0x1111111111111111
>
> 就能還原成原本的 bitmap 了！

若是今天 bitmap 中 set bits 是稀疏的，壓縮效果會更好。

> bm:
> >0x0000000000010000
> 0x0010110102100000
> 0x0F0E000100600000
> 0x0000000100000000
>
> pos = 4
> >out[0] = $0\times64+16 = 16$
> out[1] = $1\times64+20 = 84$
> out[2] = $2\times64+21 = 149$
> out[3] = $3\times64+32 = 224$
>
>搭配經過對每個內容去除 tailing zeros後的 `bm_rtz`
>
> bm_rtz:
> >0x0000000000000001
> 0x0000000101101021
> 0x000000F0E0001006
> 0x0000000000000001

:::warning
TODO: 延伸問題 2 3 4
:::

---

## 測驗 5 ： LeetCode 166. Fraction to Recurring Decimal

- 結構體

struct rem_node {
    int key;
    int index;
    struct list_head link;
}; 

結構圖解：

digraph G {
    rankdir = LR;
    splines = false;
    
    node[shape = "record"]
    rem_node[label ="<n> rem_node|{<k>key|<i>index|{<s>link|{prev|next}}}",width = 1.3]   
}

- `find` 函式

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

根據 hash 值在對應的 heads 中尋找對應的 key ，若有則回傳該 key 的 index ，若沒有則回傳 -1 。

- `fractionToDecimal` 函式
由於程式很長，所以會分段講解。

- 判斷除數被除數是否為 0 ，除數為 0 回傳 0 ，被除數為 0 回傳空字串。

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

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

- 將除數及被除數進行 `abs`

    if (n < 0)
        n = -n;
    if (d < 0)
        d = -d;

:::info
改進： branchless

    n = n ^ ((n ^ -n) & -(n < 0));
    d = d ^ ((d ^ -d) & -(d < 0));

:::

- 判斷輸出結果正負

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

:::info
改進： bitwise operation

    bool sign = (numerator < 0) ^ (denominator < 0);

:::

- 計算結果與輸出

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

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

:::info
改進： branchless

    sprintf(p, "%ld", division ^ ((division ^ -division) & -(division < 0)));

:::

- 有餘數，繼續

    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;

- 建立並初始化存放所有餘數的 `heads`

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

- 餘數處理
由於一開始並不會立刻進入循環小數的處理因此先跳過 `pos == -1` 的情況，先講解後續的程式碼。

    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;

建立一個 node 並把當前的餘數存進 key 跟把目前的 i (當前重複處理幾次餘數)存進 index 。
接著把這個 node 放進 heads 中的前端，，並依據在 `find` 中對應的 hash 方式放進對應的 heads[hash] 中。
最後更新 decimal 和 remainder 。
`MMM`
$\rightarrow$ list_add
`EEE`
$\rightarrow$ &heads[remainder % size]

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

若在 heads 中找到 remainder 則表示已經進入重複循環了，接著從當前的餘數開始往回找重複幾個數字，最後輸出結果。
`PPP`
$\rightarrow$ pos--

### 延伸問題 2
>在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景

:::warning
TODO: 延伸問題 2
:::

---

## 測驗 6 ： `__alignof__` 實作

在進入程式碼前，我們先來看 [`__alignof__`](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 是什麼。
>The keyword `__alignof__` determines the alignment requirement of a function, object, or a type, or the minimum alignment usually required by a type. --[`__alignof__`](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html)

/*
 * 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)

逐步拆解這個 marco 可以發現它的本質是兩個 `(char *)` (pointer of char) 相減的結果，並藉此取得兩個地址間相差多少 bytes 。但是對 c 不熟的人看到這裡可能會開始冒出一堆疑惑(就像是我!)，`(struct { char c; t _h; } *)0` 是什麼寫法？為什麼 struct 中還要多一個 `char c` ？

- `(struct { char c; t _h; } *)0` 是什麼?

首先 `(struct { char c; t _h; } *)` 只是表示內含 `{ char c; t _h; }` 的 pointer of struct ，本質上他還是某種型態的 pointer ，所以像是 `(char *)` 或是 `(void *)` 都是合法的。回到正題，`(struct { char c; t _h; } *)0` 是什麼？上網搜尋會找到很多有關這個問題的討論。
> [Is (int *)0 a null pointer? -stackoverflow](https://stackoverflow.com/questions/21386995/is-int-0-a-null-pointer)
> [What does (char*) 0 mean? -stackoverflow](https://stackoverflow.com/questions/36931022/what-does-char-0-mean)
> [What does (char *)0 mean in c? -stackoverflow](https://stackoverflow.com/questions/6072931/what-does-char-0-mean-in-c)
> [what is the meaning of (char*)1? -stackoverflow](https://stackoverflow.com/questions/37924622/what-is-the-meaning-of-char1)

相信概念不夠清楚的人看完這些討論後，應該會更一頭霧水，有人說
>(char*) 0 Is not a null character, but a pointer to a character at address 0.

而在其他篇中有人認為
>In C (char *) 0 is treated in a special way - it is guaranteed to produce a null-pointer value of type char *.

還有人補充
>In both C and C++, (int *)0 is a constant expression whose value is a null pointer. It is not, however, a null pointer constant.

因此還是來找找 [C99 standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 吧！
乍看之下，`(char *)0` 這種表示法挺像是 `cast` 的，因此來看看 [C99 standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 中 §6.5.4 (Cast operators) 的說明，可以在第 3 點中看到以下說明：
>Conversions that involve pointers, other than where permitted by the constraints of 6.5.16.1, shall be specified by means of an explicit cast.

由於這是一個有關指標的轉換但不確定是不是 §6.5.16.1 中規定的例外狀況，因此我們再跳到 §6.5.16.1 看有關指標轉型的說明。
而在 §6.5.16.1 中規定有關 pointer assignment 的規定，因為與這個無關就不放上來了。

看到這裡似乎可以把 `(char *)0` 當成把 0 轉換成 pointer of char 。這樣第一個回復的內容似乎是正確的？接著我們再來看看 §6.3.2.3 第 3 點中的說明。

根據 [C99 standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 中 §6.3.2.3 第 3 點中的說明。
>An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.
If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.

來舉個例子說明吧！
>e.g
>int *p = 0; //null pointer constant
>int *p = (void *)0; //null pointer constant
>int *p = (int *)0; //null pointer

所以 `(struct { char c; t _h; } *)0` 是一種 null pointer 。

題外話，那 `(int *)1` 是什麼呢？按照以上的說明可知， `(int *)1` 是把 1 cast 成 pointer of int ，所以 `(int *)0` 跟 `(int *)1` 是不一樣的。

- 為什麼 struct 中還要多一個 `char c` ？
根據[你所不知道的 C 語言：記憶體管理、對齊及硬體特性 中 data alignment](https://hackmd.io/@sysprog/c-memory?type=view#data-alignment) 的章節提到， struct 會自動做 alignment 以達到最好的存取速度。
因此 struct 中的 `char c` 會依據後續的資料來決定要 padding 多少。
> e.g.
> 後面接 `char` ，因為一樣是 `char` 所以不用 padding。
> 後面接 `int` ，以 `int` （4 bytes） 為基準，因此 padding 3 bytes 。
> 後面接 `long` ，以 `long` （8 bytes） 為基準，因此 padding 7 bytes 。

利用這個特性就可以從 `char` 經過 padding 之後的地址，知道後面我們好奇的那個資料型態需要用多少 bytes 來 align 。

`M`
$\rightarrow$ _h

`X`
$\rightarrow$ 0

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

在 [linux/drivers/usb/gadget/u_f.h](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/drivers/usb/gadget/u_f.h) 可以看到 `__alignof__` 被拿來計算與下一個 `groupname` (`groupname##__next`) 間的 offset 。

#define vla_item(groupname, type, name, n) \
	size_t groupname##_##name##__offset = ({			       \
		size_t offset = 0;					       \
		if (groupname##__next != SIZE_MAX) {			       \
			size_t align_mask = __alignof__(type) - 1;	       \
			size_t size = array_size(n, sizeof(type));	       \
			offset = (groupname##__next + align_mask) &	       \
				  ~align_mask;				       \
			if (check_add_overflow(offset, size,		       \
					       &groupname##__next)) {          \
				groupname##__next = SIZE_MAX;		       \
				offset = 0;				       \
			}						       \
		}							       \
		offset;							       \
	})

### 延伸問題 3
>在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集，探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻，儘量共用相同的巨集

在 [linux/include/uapi/linux/const.h](https://github.com/torvalds/linux/blob/master/include/uapi/linux/const.h) 中可以找到對齊相關的程式碼
> 以下程式碼節錄自 [const.h](https://github.com/torvalds/linux/blob/master/include/uapi/linux/const.h) 第 31,32 行

#define __ALIGN_KERNEL(x, a)		__ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask)	(((x) + (mask)) & ~(mask))

- `__ALIGN_KERNEL_MASK`
針對特定的 bitmask (e.g. $15_{10} = 1111_2$) 進行向上對齊
- `__ALIGN_KERNEL`
在 `__ALIGN_KERNEL_MASK` 的基礎上，對特定長度的數字(通常是 $2^n ,n \in N$) 進行向上對齊

接著在 [linux/include/linux/align.h](https://github.com/torvalds/linux/blob/master/include/linux/align.h) 中可以找到向上對齊/向下對齊的程式碼。
> 以下程式碼節錄自 [align.h](https://github.com/torvalds/linux/blob/master/include/linux/align.h) 第 7 至 9 行

/* @a is a power of 2 value */
#define ALIGN(x, a)		__ALIGN_KERNEL((x), (a))
#define ALIGN_DOWN(x, a)	__ALIGN_KERNEL((x) - ((a) - 1), (a))

- `ALIGN`
本來在 `__ALIGN_KERNEL` 中就是向上對齊了，所以他就是向上對齊。
- `ALIGN_DOWN`
在要對齊的地址中先 `- ((a) - 1)` ，達到把 `a - 1`以下的位元全部 clear 並且不 `+1` ，完成向下對齊。

---

## 測驗 7 ： 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;
}

直接看 `length` 會不知道他要做什麼，因此我們先從`&"FizzBuzz%u"[(9 >> div5) >> (KK3)]` 說起。當 div5 等於 1 時（輪到 5 的倍數，先不討論 15 的倍數），要輸出 `Buzz` ，而此時 `&"FizzBuzz%u"[(9 >> div5)]` 會等於 `Buzz%u` ，另外 `strncpy` 會把 `src` 中的字串從前到後根據 `length` 複製到 `dest` 。
因此可知 `KK3` 的作用是在 3 的倍數（包含 15 的倍數）時，讓字串變成 `"FizzBuzz%u"` ，接著要讓 $1001_{2}$ 變成 $0000_2$ 至少要右移 4 。

`KK3`
$\rightarrow$ div3 << 2

接著來看 `length` 在 3 的倍數時（字串此時是 `FizzBuzz%u` ），要等於 4 ；在 5 的倍數時（字串此時是 `Buzz%u` ），要等於 4 ；最後在 15 的倍數時（字串此時是 `FizzBuzz%u` ）要等於 8 。

`KK1`
$\rightarrow$ div3
`KK2`
$\rightarrow$ div5