# 2022q1 Homework2 (quiz2)
contributed by < [Tcc0403](https://github.com/Tcc0403) >
[測驗連結](https://hackmd.io/@sysprog/linux2022-quiz2#2022q1-%E7%AC%AC-2-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)
## 測驗一
>考慮以下對二個無號整數取平均值的程式碼:
>```c
>#include <stdint.h>
>uint32_t average(uint32_t a, uint32_t b)
>{
> return (a + b) / 2;
>}
>```
>這個直覺的解法會有 overflow 的問題，若我們已知 a, b 數值的大小，可用下方程式避免 overflow:
>```c
>#include <stdint.h>
> uint32_t average(uint32_t low, uint32_t high)
> {
> return low + (high - low) / 2;
> }
>```
>可改寫為以下兩種等價實作:
> ```c
> #include <stdint.h>
> uint32_t average(uint32_t a, uint32_t b)
> {
> return (a >> 1) + (b >> 1) + (EXP1);
> }
> ```
>
> ```c
> uint32_t average(uint32_t a, uint32_t b)
> {
> return (EXP2) + ((EXP3) >> 1);
> }
> ```
### 題目分析
#### 第一種等價實作:
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
前兩項的操作為右移一位元，可以視作為 `a`, `b` 兩值除以 2
$\frac{a+b}{2}=\frac{a}{2}+\frac{b}{2}$ 看似沒有問題，但先進行右移操作，會忽略 `a`, `b` 兩值相加最低位元進位的情況，
因此我們需要補上第三項，判斷最低位元相加是否進位，若有進位則加 1
|a[0]|b[0]|Carry|
|-|-|-|
|0|0|0|
|0|1|0|
|1|0|0|
|1|1|1|
觀察真值表可以得到 $Carry = a_0 \cdot b_0$
* 使用位元遮罩取得最低位元 $a_0 = a \cdot \mathrm{0x0001},\ b_0 = b \cdot \mathrm{0x0001}$
* 整理成以下等式:
$$\begin{split}
Carry &= a_0 \cdot b_0\\
&= (a \cdot \mathrm{0x0001}) \cdot (b \cdot \mathrm{0x0001})\\
&= a \cdot b \cdot \mathrm{0x0001}
\end{split}$$
轉成程式碼，第三項 `EXP1` 即為 `a & b & 1`
#### 第二種等價實作:
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
回顧半加器 ([Half adder](https://en.wikipedia.org/wiki/Adder_(electronics)#Half_adder)) 實作方法
|A|B|Carry|Sum
|-|-|-|-|
|0|0|0|0|
|0|1|0|1|
|1|0|0|1|
|1|1|1|0|
由真值表可得 $Carry = A \cdot B,\ Sum = A \oplus B$
進行多位元加法時，除了計算兩數在該位元的加總值 (Sum) ，計算出的進位值 (Carry) 還得進位至高位元 (i.e. 第 $i$ 位元所計算出的進位值必須加到第 $i+1$ 位元)
轉成程式碼即為 `a & b + (a ^ b) << 1`，等價於 `a + b`
`a & b + (a ^ b) << 1` 兩項分別右移一位 $\to$ `(a & b) >> 1 + (a ^ b)`，即為兩數平均`(a + b) / 2`
`EXP2` = `a & b`, `EXP3` = `a ^ b`
:::success
延伸問題
1. 解釋上述程式碼運作的原理
2. 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 [CS:APP 第 3 章](https://hackmd.io/@sysprog/CSAPP-ch3))
3. 研讀 Linux 核心原始程式碼 [include/linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h)，探討其 [Exponentially weighted moving average](https://en.wikipedia.org/wiki/Moving_average#Exponential_moving_average) (EWMA) 實作，以及在 Linux 核心的應用
>移動平均（Moving average)，又稱滾動平均值、滑動平均，在統計學中是種藉由建立整個資料集合中不同子集的一系列平均數，來分析資料點的計算方法。
移動平均通常與時間序列資料一起使用，以消除短期波動，突出長期趨勢或周期。短期和長期之間的[閾值](https://terms.naer.edu.tw/detail/1085244/)取決於應用，移動平均的參數將相應地設置。例如，它通常用於對財務數據進行技術分析，如股票價格、收益率或交易量。它也用於經濟學中研究國內生產總值、就業或其他宏觀經濟時間序列。
:::
### 延伸問題 : 研讀[ include/linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h)
#### EWMA 實作
`DECLARE_EWMA(name, _precision, _weight_rcp)` 巨集依據引數宣告相應的結構體以及操作相關函式
+ 結構體中僅有一個 `unsigned long` 型態的成員 `internal`
+ 操作相關函式有 `init`, `read`, `add`
+ `_precision` 決定 `internal` 中要用多少位元當作小數部分，即計算平均的精度
+ `＿weight_rcp` 決定計算新的平均值時，新數值與原本平均值的權重
為了計算效率，必須為 2 的冪
觀察 `add` 函式中實際計算新平均數的程式碼段落
```c
WRITE_ONCE(e->internal, internal ? \
(((internal << weight_rcp) - internal) + \
(val << precision)) >> weight_rcp : \
(val << precision));
```
+ `weight_rcp` 為以 2 為底的 `_weight_rcp` 之對數
+ 如果是第一次執行 `add` ，此時 `internal` 為 0，便直接將新數值作為平均值依照前面訂定的精度格式寫入
+ 其餘情況則按照以下方式更新平均值
$$
\text{new average} = \frac{(\text{＿weight_rcp}-1)\cdot\text{average} + \text{new value}}{\text{＿weight_rcp}}
$$
在實作方法中，由於權重必定為 2 的冪，便可以使用位移操作取代計算效率較低的除法操作，
## 測驗二
> 改寫〈[解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)〉一文的「不需要分支的設計」一節提供的程式碼 min，我們得到以下實作 (max):
> ```c
> #include <stdint.h>
> uint32_t max(uint32_t a, uint32_t b)
> {
> return a ^ ((EXP4) & -(EXP5));
> }
> ```
### 題目分析
觀察題目提及的 `min` 函式
```c
int32_t min(int32_t a, int32_t b) {
int32_t diff = (a - b);
return b + (diff & (diff >> 31));
}
```
該函式中先計算 `diff = a - b`，再透過 bitwise 操作觀察最高位元判斷正負:
+ 若最高位元是 1 ，表示 `diff` 為負，即 `a < b`， `diff & (diff >> 31)` 會得到 `diff` ， `b + (diff & (diff >> 31)` 所得到的結果即為 `a`
:::warning
對有號負數數進行右移是 implementation-defined，在不同環境可能會有不同結果，上述假設對有號負數右移為算術位移 (Arithmetic shift)
摘錄自 C99 [6.5.7] ***Bitwise shift operators*** :
> The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type
> or if E1 has a signed type and a nonnegative value, the value of the result is the integral
> part of the quotient of E1 / 2E2. If E1 has a signed type and a negative value, the
> resulting value is implementation-defined.
:::
+ 若最高位元是 0 ，表示 `diff` 為正， 即 `a > b` ， `diff & (diff >> 31)` 會得到 0 ， `b + (diff & (diff >> 31)` 所得到的結果即為 `b`
上述函式在判斷最高位元時，順便將此判斷式作為位元遮罩得到相應的修正量，以達成 branchless
分析原題目 `max` 函式
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
可以將 `a` 視作原本給定的值， `EXP4` 視作相應的修正量， `EXP5` 為判斷式兼位元遮罩:
+ 若 a 較大，則後面不需要修正量，此時作為判斷式兼位元遮罩的 `EXP5` 需要等於 0 ， 即 `a < b`
+ 若 a 較小，使 `a < b` 為 1，由於二補數編碼的關係，前面加上負號可將其變為 0xFFFF 的位元遮罩，與 `EXP4` 做位元運算會得到 `EXP4` ，要使原式 `a ^ (EXP4) = b`，透過與 a 自己做 `XOR` 運算再與欲得之值 `b` 做 `XOR` 便能成立，即 `EXP4` = `a ^ b`
:::success
延伸問題
1. 解釋上述程式碼運作的原理
2. 針對 32 位元無號/有號整數，撰寫同樣 [branchless](https://en.wikipedia.org/wiki/Branch_(computer_science)) 的實作
3. Linux 核心也有若干 branchless / branch-free 的實作，例如 [lib/sort.c](https://github.com/torvalds/linux/blob/master/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` 檢索。
:::
### 延伸問題 : 針對 32 位元無號/有號整數的 branchless 實作
#### 有號整數的 `max` :
改寫上方的有號整數版本 `min`
```c
int32_t max(int32_t a, int32_t b) {
int32_t diff = (a - b);
return a + (-diff & (diff >> 31));
}
```
+ `(diff >> 31)` 作為判斷式兼位元遮罩，按照上面分析， `diff` 為正時位元遮罩為 `0`，回傳值即是第一項，故改寫為 `a`
+ 若 `diff` 為負，需要回傳 `b` = `a + (b - a)` = `a + (-diff)`，故原本的修量需要補上負號才能正確回傳 `b`
#### 無號整數的 `min` :
改寫上方的無號整數版本的 `max`
```c
#include <stdint.h>
uint32_t min(uint32_t a, uint32_t b)
{
return a ^ ((a ^ b) & -(a > b));
}
```
只要修改判斷式成立的條件即可
## 測驗三
> 考慮以下 64 位元 GCD ([greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor), 最大公因數) 求值函式:
> ```c
> #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;
> }
> ```
> 改寫為以下等價實作:
> ```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;
> }
> ```
### 題目分析
等價實作中的 do-while 迴圈與原程式中的 while 迴圈皆是在進行輾轉相除法，結束條件為除數等於零，觀察兩段程式碼可以發現 `v` 皆是當中的除數，因此 `COND` 同樣也是 `v`
由於在等價實作中，進行輾轉相除法之前先提出了 `u`, `v` 兩數為最大的 2 的冪公因數，在回傳之前，必須先將由輾轉相除法得到的被除數 `u` 進行修正，將上面提出的最大的 2 的冪公因數乘回去，`RET` 即 `u << shift`
:::success
延伸問題
1. 解釋上述程式運作原理;
2. 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
3. Linux 核心中也內建 GCD (而且還不只一種實作)，例如 [lib/math/gcd.c](https://github.com/torvalds/linux/blob/master/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 (v);
return u<<shift;
}
```
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. Mulitplication with $2$ can be done with betwise 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.
以下分段說明：
```c
if (!u || !v) return u | v;
```
$\to$ 對應至 GCD 演算法第 2 點
* $gcd(x,0)=x$ and $gcd(0, y)=y$ because everything divides 0.
若 u 和 v 中其中一數為 0 ，則直接回傳另一數
> `x | 0` 會得到 x
```c
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
$\to$ 對應至 GCD 演算法第 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. Mulitplication with $2$ can be done with betwise shift operator.
先取出`u` 和 `v` 之間屬於 $2^n$ 的公因數，`shift` 即為最大的 $n$
```c
while (!(u & 1))
u /= 2;
```
$\to$ 對應至 GCD 演算法第4 點
* If x is even and y is odd, $gcd(x, y) = gcd(\dfrac{x}{2}, y)$.
當 `u` 為偶數時，可以除以 $2$
```c
do {
while (!(v & 1))
v /= 2;
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
```
$\to$ 其中 `while(!(v &1)) v /= 2;` 對應至 GCD 演算法第 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.
可以透過迴圈不變性 (loop invariant) 來幫助解讀程式
* `u` 為被除數
* `v` 為除數
當除數 `v`為 0 時結束迴圈，被除數 `u` 為進入迴圈前 `u` 和 `v` 的最大公因數
:::warning
事實上 `u` 在迴圈前不一定是被除數，因為先前透過 GCD 演算法第 4 點去除不必要的計算
:::
```c
return u << shift;
```
最後回傳最大公因數時，乘上原先取出屬於 $2^n$ 的公因數，可以透過左移達成
### 延伸問題 : 透過 `__builtin_ctz` 改寫程式
已知除法運算會耗費較多時間，我們可以利用 `__builtin_ctz` (編譯器會產生對應到現代微處理器的專門指令) 搭配上述針對二進位特性調整的演算法，減少除法的使用
改寫之前先透過 perf 分析程式，將一百萬組由 `rand` 函式生成的亂數傳入 `gcd64` 函式執行
```shell
$ gcc -g3 -O0 gcd.c -o gcd
$ perf record ./gcd
$ perf annotate
```
由上圖可以發現，花費 CPU 週期數最多的段落為迴圈當中的 `v /= 2` 運算，佔據約 28%
以下為改寫過後的程式
```c
uint64_t gcd64_ctz(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int shift = __builtin_ctzll(u | v);
u = u >> __builtin_ctzll(u);
do {
v = v >> __builtin_ctzll(v);
if (u < v) {
v -= u;
} else {
uint64_t t = u - v;
u = v;
v = t;
}
} while (v);
return u << shift;
}
```
透過 perf 分析前後差異
```shell
$ gcc -g -O0 gcdcmp.c -o gcdcmp
$ perf record ./gcdcmp
$ perf report
```
將同樣一百萬筆由 `rand` 函式所產生的亂數傳入 `gcd64` 和 `gcd64_ctz` 函式比較，發現改寫過後的版本花費時間幾乎是原來的一半
### 延伸問題 : [lib/math/gcd.c](https://github.com/torvalds/linux/blob/master/lib/math/gcd.c) 實作手法
## 測驗四
> 在影像處理中，[bit array](https://en.wikipedia.org/wiki/Bit_array) (也稱 bitset) 廣泛使用，考慮以下程式碼:
> ```c
> #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;
> }
> ```
> 考慮 GNU extension 的 [__builtin_ctzll](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 的行為是回傳由低位往高位遇上連續多少個 0 才碰到 1。
>
> 用以改寫的程式碼如下:
> ```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;
> }
> ```
> 其中第 9 行的作用是找出目前最低位元的 1，並紀錄到 t 變數。舉例來說，若目前 bitset 為 $000101_b$，那 t 就會變成 $000001_b$ ，接著就可以透過 XOR 把該位的 1 清掉，其他保留 (此為 XOR 的特性)。
### 題目分析
題目提示要考慮到 -bitwise 的特性，在二補數編碼中，恰巧最低位元的 1 之下的位元皆會保留
(e.g. $-(0010\underline{1000})_b = 1101\underline{1000}_b,\ -(101110\underline{10})_b = 010001\underline{10}_b$)
利用此特性，自己與自己的負數(二補數)進行 `AND` 操作，即可找出最低位元的 1
`EXP6` 即為 `bitset & -bitset'
:::success
延伸問題
1. 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
2. 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 [bitmap density](http://www.vki.com/2013/Support/docs/vgltools-3.html);
3. 思考進一步的改進空間;
4. 閱讀 [Data Structures in the Linux Kernel](https://0xax.gitbooks.io/linux-insides/content/DataStructures/linux-datastructures-3.html) 並舉出 Linux 核心使用 bitmap 的案例;
:::
### 程式運作原理
## 測驗五
> 以下是 LeetCode [166. Fraction to Recurring Decimal](https://leetcode.com/problems/fraction-to-recurring-decimal/) 的可能實作:
> ```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)
> {
> 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;
> }
> ```
> 請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。
### 題目分析
先觀察 `PPP`, `MMM`, `EEE` 所處迴圈(第 77-97 行)的用途，可以大致分成三個部分:
+ 第 78-88 行: 尋找 `remainder` 是否存在於 hashmap 之中
+ 若存在，將小數部分依格式更新到 `result` 後，結束該函式並回傳
+ 若不存在，則繼續往下執行
+ 第 89-93 行: 建立節點，插入對應的 hashmap 位置
+ 第 95-96 行: 更新小數部分，並計算下一位的 `remainder`
`PPP > 0` 為條件式的 while 迴圈，負責更新循環小數前的部分，前面透過 `find` 函數取得循環小數開始的位數 `pos`，所以這裡需要更新 `pos` 個位數，由於該迴圈內部沒有額外操作，透過 `pos--` 使迴圈執行的同時遞減 `pos`， `PPP` 即 `pos--`
`MMM`, `EEE` 處於同一行，該行的作用為將建立好的節點插入對應的 hashmap 位置， `MMM` 即是 list API 插入節點的巨集 `list_add` ，至於要插入哪一個 head (heads[?])，需要回頭去看 hash 是如何計算，找到 `find` 函式有寫到 `hash = key % size` ，上面呼叫 `find` 函式時，是將 `remainder` 傳入 ， `EEE` 即是 `heads[remainder % size]`
:::success
延伸問題
1. 解釋上述程式碼運作原理，指出其中不足，並予以改進
>例如，判斷負號只要寫作 `bool isNegative = numerator < 0 ^ denominator < 0;`
搭配研讀 [The simple math behind decimal-binary conversion algorithms](https://indepth.dev/posts/1019/the-simple-math-behind-decimal-binary-conversion-algorithms)
2. 在 Linux 核心原始程式碼的 `mm/` 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景
:::
## 測驗六
> [`__alignof__`](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 是 GNU extension，以下是其可能的實作方式:
> ```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__`](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 等價。
### 題目分析
觀察題目中的實作方法，發現是兩個位址相減
先透過結構體指標 `struct {char c; t _h; } *`將 0 視作該結構體的起始位址，
再存取型態為 `t` 的結構體成員 `_h` 位址，減去前一個成員的位址，
便可算出型態 `t` 在當前環境的 alignment
`M` 即是上述提到要測試的型態成員 `_h`，由於成員 `c` 作為第一個成員，起始位址與結構體相同，
`X` 即是一開始設定的結構體起始位址 0
:::success
延伸問題
1. 解釋上述程式碼運作原理
2. 在 Linux 核心原始程式碼中找出 [`__alignof__`](https://gcc.gnu.org/onlinedocs/gcc/Alignment.html) 的使用案例 2 則，並針對其場景進行解說
3. 在 Linux 核心源使程式碼找出 `ALIGN`, `ALIGN_DOWN`, `ALIGN_UP` 等巨集，探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻，儘量共用相同的巨集
:::
## 測驗七
> 考慮貌似簡單卻蘊含實作深度的 [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) 題目:
> + 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
> + 如果是 5 的倍數，印出 “Buzz”
> + 如果是 15 的倍數，印出 “FizzBuzz”
> + 如果都不是，就印出數字本身
>
> 直覺的實作程式碼如下: (naive.c)
> ```c
> #include <stdio.h>
> int main() {
> for (unsigned int i = 1; i < 100; i++) {
> if (i % 3 == 0) printf("Fizz");
> if (i % 5 == 0) printf("Buzz");
> if (i % 15 == 0) printf("FizzBuzz");
> if ((i % 3) && (i % 5)) printf("%u", i);
> printf("\n");
> }
> return 0;
> }
> ```
> 觀察 `printf` 的(格式)字串，可分類為以下三種:
> 1. 整數格式字串 `"%d"` : 長度為 2 B
> 2. “Fizz” 或 “Buzz” : 長度為 4 B
> 3. “FizzBuzz” : 長度為 8
>
> 考慮下方程式碼:
> ```cmake
> char fmt[M9];
> strncpy(fmt, &"FizzBuzz%u"[start], length);
> fmt[length] = '\0';
> printf(fmt, i);
> printf("\n");
> ```
> 我們若能精準從給定輸入 i 的規律去控制 `start` 及 `length`，即可符合 FizzBuzz 題意:
> ```c
> string literal: "fizzbuzz%u"
> offset: 0 4 8
> ```
> 以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (`bitwise.c`)
> ```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"[(9 >> div5) >> (KK3)], length);
> fmt[length] = '\0';
>
> printf(fmt, i);
> printf("\n");
> }
> return 0;
> }
> ```
> 其中 `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/)，甚至 gcc-9 還內建了 [FizzBuzz optimization](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853) (Bug 82853 - Optimize x % 3 == 0 without modulo)。
> 請補完，使得程式碼符合預期，儘量以最簡短且符合一致排版的形式來撰寫。
### 題目分析
依據題目需求，先整理各個條件所對應的長度 `length` 和起點 `start`:
| | length | start |
| -------- | -------- | -------- |
| 3 的倍數 | 4 | 0 |
| 5 的倍數 | 4 | 4 |
| 15 的倍數 | 8 | 0 |
| 都不是|2|8|
可以發現長度 `length` 都是 2 的冪
+ 符合零個條件時，長度為 2
+ 符合一個條件時，長度為 4
+ 符合兩個條件時，長度為 8
符合條件數與所需的位移量剛好相等，可將判斷條件的布林值直接帶入 `KK1`, `KK2`，分別為 `div3`, `div5`
再來起點的部分，題目已經先給定了 `9 >> div5` 的操作，透過真值表觀察位移量
| | 9 >> div5 | (9 >> div5) >> (KK3) | KK3 |
| -------- | -------- | -------- |---- |
| 3 的倍數 | 9 | 0 | $\geq$ 3 |
| 5 的倍數 | 4 | 4 | 0 |
| 15 的倍數 | 4 | 0 | $\geq$ 2 |
| 都不是 | 9 | 8 | ?|
發現題目有問題
:::success
延伸問題
1. 解釋上述程式運作原理並評估 `naive.c` 和 `bitwise.c` 效能落差
+ 避免 stream I/O 帶來的影響，可將 `printf` 更換為 sprintf
2. 分析 [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/) 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 `bitwise.c` 程式碼，試圖運用更少的指令來實作出 branchless;
+ 參照 [fastmod: A header file for fast 32-bit division remainders on 64-bit hardware](https://github.com/lemire/fastmod)
4. 研讀 [The Fastest FizzBuzz Implementation](https://tech.marksblogg.com/fastest-fizz-buzz.html) 及其 [Hacker News 討論](https://news.ycombinator.com/item?id=29413656)，提出 throughput (吞吐量) 更高的 Fizzbuzz 實作
5. 解析 Linux 核心原始程式碼 [kernel/time/timekeeping.c](https://github.com/torvalds/linux/blob/master/kernel/time/timekeeping.c) 裡頭涉及到除法運算的機制，探討其快速除法的實作 (注意: 你可能要對照研讀 `kernel/time/` 目錄的標頭檔和程式碼)
>過程中，你可能會發現可貢獻到 Linux 核心的空間，請充分討論
:::
Sign in with Wallet
Connect another wallet