# 2022q1 Homework2 (quiz2)
contributed by `mm0809`
## 測驗 `1`
### 程式運作原理
```c
#include <stdint.h>
uint32_t average(uint32_t a, uint32_t b)
{
return (a >> 1) + (b >> 1) + (EXP1);
}
```
`(a + b) / 2` 並不能以 `a / 2 + b / 2` 表示。因為若被除數除不盡，則餘數會被省略，導致**先加後除**與**先除後加**結果不同。
| a | b | a/2 + b/2 | (a+b)/2 |
| --- | --- | --------- | ------- |
| 1 | 2 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 2 | 2 | 2 | 2 |
| 3 | 3 | 2 | 3 |
當 `a` 和 `b` 都是奇數時就會有誤差出現，因為 `/2` 會有餘數 `1`，而相加以後兩個餘數 1 又可以被 2 除盡。
因此我們可以改寫： `a >> 2 + b >> 2 + (a & b & 1)`
故 `EXP1 = a & b & 1`
```c
uint32_t average(uint32_t a, uint32_t b)
{
return (EXP2) + ((EXP3) >> 1);
}
```
要改寫 `(a + b) / 2` 可以先重 `a + b` 下手，最後再使用 `>> 1` 達到 `/ 2` 的效果。
兩個整數做加法可以想像成有一整排的 full adder 針對每個 bit 做運算。
以 full adder 的觀點來看，我們可以先算 `SUM` 然後再加上 `CARRY IN`。
| a | b | SUM | CARRY OUT |
| --- | --- | --- | --------- |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
`SUM` 對應的操作是 `a ^ b`， `CARRY OUT` 對應的操作是 `a & b`。 `CARRY OUT` 是下一個 bit 的 `CARRY IN` ，因此 `CARRY IN` 為 `(a & b) << 1` 。
最後可以得知 `a + b` 為 `(a ^ b) + (a & b) << 1`。
`(a + b) / 2 = (a + b) >> 1 = (a ^ b) >> 1 + a & b` 。
故 `EXP2 = a & b` ， `EXP3 = a ^ b`。
### 比較編譯器最佳化輸出
以下為各版本使用 `gcc -O3 -S` 編譯出來的結果
`版本 1`
```c
#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
return low + (high - low) / 2;
}
```
```
average: // %edi = low, %esi = high
endbr64
movl %esi, %eax // high
subl %edi, %eax // high - low
shrl %eax // (high - low) >> 1
addl %edi, %eax // low + (high -low) >> 1
ret
```
> 相較於 `-O0` 從 `-01` 開始， parameter 不會被 push 到 stack 裡面，作一些不必要的操作。
> ```c
> // gcc -O0 -S
> average:
> endbr64
> pushq %rbp
> movq %rsp, %rbp
> movl %edi, -4(%rbp)
> movl %esi, -8(%rbp)
> movl -8(%rbp), %eax
> subl -4(%rbp), %eax
> shrl %eax
> movl %eax, %edx
> movl -4(%rbp), %eax
> addl %edx, %eax
> popq %rbp
> ret
> ```
`版本 2`
```c
#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
return (low >> 1) + (high >> 1) + (low & high & 1);
}
```
```
average:
endbr64
movl %edi, %eax // low
movl %esi, %edx // high
andl %esi, %edi // low & high
shrl %eax // low >> 1
shrl %edx // high >> 1
andl $1, %edi // low & high & 1
addl %edx, %eax // low >> 1 + high >> 1
addl %edi, %eax // low >> 1 + high >> 1 + low & high & 1
ret
```
`版本 3`
```c=
#include <stdint.h>
uint32_t average(uint32_t low, uint32_t high)
{
return (low & high) + ((low ^ high) >> 1);
}
```
```
average:
endbr64
movl %edi, %eax // low
andl %esi, %edi // low & high
xorl %esi, %eax // low ^ high
shrl %eax // (low ^ high) >> 1
addl %edi, %eax // low & high (low ^ high) >> 1
ret
```
當編編譯器最佳化開到 `-O3` 時並不會很難看懂，本來以為最佳化開越大越難讀懂，比起 `-O0` 更好讀懂，做得很俐落。可能是因為本題的程式碼短，而且精簡沒有多餘的操作。
### Linux 核心實作：average.h
```c
#define DECLARE_EWMA(name, _precision, _weight_rcp) \
struct ewma_##name { \
unsigned long internal; \
}; \
static inline void ewma_##name##_init(struct ewma_##name *e) \
{ \
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
/* \
* Even if you want to feed it just 0/1 you should have \
* some bits for the non-fractional part... \
*/ \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
e->internal = 0; \
}
```
`name` 用來生成 struct 物件跟建立對應的 helper function。
在 Linux 時做出來的 EWMA 中使用 fixed-precision value 紀錄數值。因此需要指定 `_precision` 。在資料結構中是使用 `unsigned long` 來記錄數值。
`_weight_rcp` 是用來設定 EWMA 公式中的 $\alpha$ ，且為了計算速度， `_weight_tcp` 必須是 power of 2 。
$$
S_t = \begin{cases}
Y_0, &t = 0 \\
\alpha Y_t + (1-\alpha)\times S_{t-1}, & t> 0
\end{cases}
$$
$$
\alpha = \frac{1}{\_weight\_rcp}
$$
```c
static inline unsigned long \
ewma_##name##_read(struct ewma_##name *e) \
{ \
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
return e->internal >> (_precision); \
} \
```
`ewma_##name##read` 這個 helper function 可以讓我們讀出整數部位。
從 `return e->internal >> (_precision)` 可以知道會在輸出時把小數部位去掉。
```c
static inline void ewma_##name##_add(struct ewma_##name *e, \
unsigned long val) \
{ \
unsigned long internal = READ_ONCE(e->internal); \
unsigned long weight_rcp = ilog2(_weight_rcp); \
unsigned long precision = _precision; \
\
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
\
WRITE_ONCE(e->internal, internal ? \
(((internal << weight_rcp) - internal) + \
(val << precision)) >> weight_rcp : \
(val << precision)); \
}
```
`ewma_##name##_add` 這個 helper function 把 `val` 加入 EWMA 的計算中。最後一行有一個 Conditional expression `? :` 用來判斷是否為第一個值，並且實現 EWMA 的公式。
$$
S_t = \begin{cases}
Y_0, &t = 0 \\
\alpha Y_t + (1-\alpha)\times S_{t-1}, & t> 0
\end{cases}
$$
`val << precision` 是把 `val` 轉換為 fixed-precision 的表示。
針對 `((internal << weight_rcp) - internal + val << precision) >> weight_rcp`
可表示成 `internal - internal >> weight_rcp + (val << precision) >> weight_rcp`
把 `>> weight_rcp` 替換成 `_weight_rcp` 可得：
$$
internal\times(1 - \frac{1}{\_weight\_rcp}) + \frac{1}{\_weight\_rcp} \times (val\_precision)
$$
符合上述的公式。
這個 macro 被使用在 net 和 gpu 相關的 driver。
本來以為網路相關的是用來決定 TCP timeout 的時間，後來後來查關鍵字 `rssi` ， 全名是 Received Signal Strength Indication，跟無線傳輸的訊號強度有關。
gpu 的則是跟 psr(Panel Self-Refresh) 有關，是一種讓螢幕省電的技術。
:::info
- [x] 解釋上述程式碼運作的原理
- [x] 比較上述實作在編譯器最佳化開啟的狀況，對應的組合語言輸出，並嘗試解讀 (可研讀 CS:APP 第 3 章)
- [x] 研讀 Linux 核心原始程式碼 include/linux/average.h，探討其 Exponentially weighted moving average (EWMA) 實作，以及在 Linux 核心的應用
:::
## 測驗 `2`
### 程式運作原理
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((EXP4) & -(EXP5));
}
```
* 若 `a >= b` 則 `((EXP4) & -(EXP5))` 須為 `0` ，因為 `a ^ 0 = a`
* 若 `a <= b` 則 `((EXP4) & -(EXP5))` 須為 `a ^ b` 因為 `a ^ a ^ b = b`
所以 `((EXP4) & -(EXP5))` 只有兩種可能，分別為 `0` 和 `a ^ b`。
可以假設 `EXP4 = a ^ b` 。 又在 `a >= b` 時 `EXP5` 須為 `1` 且在 `a <= b` 時 `EXP5` 須為 `0` ，因此 `EXP5 = a < b or a <= b` 。因為題目要求以最精簡為主因此選擇 `a < b`。
### 有號整數版本
```c
#include <stdint.h>
uint32_t max(uint32_t a, uint32_t b)
{
return a ^ ((a ^ b) & -(a < b));
}
```
遠本版本的實作主要用到兩種操作：
* a ^ a ^ b = b
* `<` : a < b 回傳 1 ， a >= b 回傳 0。
這兩個性質不管是有號或無號數均成立，因此可以沿用原始版本。
:::info
- [x] 解釋上述程式碼運作的原理
- [x] 針對 32 位元無號/有號整數，撰寫同樣 branchless 的實作
- [ ] Linux 核心也有若干 branchless / branch-free 的實作，例如 lib/sort.c:
:::
## 測驗 `3`
```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;
}
```
```c
if (!u || !v) return u | v;
```
實現了 GCD 演算法中的
* If both x and y are 0, gcd is zero $gcd(0, 0)$
* $gcd(x, 0)=x$ and $gcd(y, 0)=y$ because everything divides 0
```c
int shift;
for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}
```
實現了 GCD 演算法中的
* If x and y are both even, $gcd(x,y)=2\times gcd(\frac{x}{2}, \frac{y}{2})$ because 2 is a common divisor. Multiplication with 2 can be done with bitwise shift operator.
所以最後算出來的最大公因數還要 `<< shift`
```c
while (!(u & 1))
u /= 2;
```
實現了 GCD 演算法中的
* If x is even and y is odd, $gcd(x,y)=gcd(\frac{x}{2},y)$
```c
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;
```
這裡做的演算法與下方的程式類似。只是以 `v -= u` 實現 `v = u % v`。也就是說用減法去取餘數。因此 `COND = v` 。
當 `v` 歸零時 `u` 就會是最大公因數，但因為一開始有考慮到兩數都是偶數時，可以先除 2 ，因此最後的答案還要做修正。 `RET = u << shift`
```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;
}
```
### 用 `__builtin_ctz` 改寫
```c
unsigned int min(unsigned int a, unsigned int b)
{
return a ^ ((a ^ b) & -(a > b));
}
uint64_t gcd64(uint64_t u, uint64_t v)
{
if (!u || !v) return u | v;
int ctzu = __builtin_ctz(u);
int shift = min(ctzu, __builtin_ctz(v));
u >>= ctzu;
v >>= shift;
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;
}
```
相較於原始版本，我把所有跟 `/2` 有關的操作都換成 `__builtin_ctz` ， 減少 `while` 的判斷。
我使用 perf 去必較效能，驗證新版的效能提升。
```bash
kuan@Athena:~/linux2022/q_w2/q3$ sudo perf stat --repeat 5 ./gcd.out
Performance counter stats for './gcd.out' (5 runs):
7,911.68 msec task-clock # 1.000 CPUs utilized ( +- 0.01% )
1,007 context-switches # 127.331 /sec ( +- 0.35% )
0 cpu-migrations # 0.000 /sec
45 page-faults # 5.637 /sec ( +- 1.14% )
26,813,705,619 cycles # 3.389 GHz ( +- 0.00% )
16,452,869,650 instructions # 0.61 insn per cycle ( +- 0.00% )
6,851,737,624 branches # 866.028 M/sec ( +- 0.00% )
1,162,687,024 branch-misses # 16.97% of all branches ( +- 0.01% )
7.91487 +- 0.00124 seconds time elapsed ( +- 0.02% )
kuan@Athena:~/linux2022/q_w2/q3$ sudo perf stat --repeat 5 ./gcd_ctz.out
Performance counter stats for './gcd_ctz.out' (5 runs):
3,640.03 msec task-clock # 1.000 CPUs utilized ( +- 0.05% )
460 context-switches # 126.318 /sec ( +- 0.30% )
0 cpu-migrations # 0.000 /sec
44 page-faults # 12.088 /sec ( +- 1.24% )
12,329,884,870 cycles # 3.387 GHz ( +- 0.00% )
11,695,305,346 instructions # 0.95 insn per cycle ( +- 0.00% )
2,173,622,865 branches # 597.144 M/sec ( +- 0.00% )
371,237,562 branch-misses # 17.08% of all branches ( +- 0.01% )
3.64181 +- 0.00178 seconds time elapsed ( +- 0.05% )
```
`gcd_out` 和 `gcd_ctz.out` 分別為原始版本和改良版本。從運行時間可以得知改良版本的效能大約是原始版本的兩倍。再深入觀察可得知改良版的 cycles, branch 和 branch miss 數量大幅下降，印證了我們用 `__builtin_ctz` 把 `while` 取代掉後有助於降低 branch 和運算。
### linux kernel: lib/math/gcd.c
```c
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;
}
}
```
```c
unsigned long r = a | b;
b >>= __ffs(b);
if (b == 1)
return r & -r;
```
這裡的 `if` 是用來判斷 `b` 是否是 2 的冪次方，若 `b` 為 2 的冪次方，則 `gcd(a, b)` 必為 2 的冪次方 (1, 2, 4, 8...) 。
> 定義 $U(K) = 2^x$ 為 2 的冪次方中， $2^x$ 為數字 K 的因數，且為最大。
> 且 $U(K)$ 可透過 `K & -K` 取得。因為 `-K = ~K + 1` 最後的 `+ 1` 可以讓 `~k` 中連續的 1 進位，直到遇上第一個 0，此時 0 的位置即為 `K` 第一位為 1 的位置。
因此此時 `gcd(a, b)` 為 $min\,(\,U(a), \, U(b)\,)$ ， 換句話說就是要找 `a, b` 兩數第一個 1 的位置的最小值。 因此可先 `r = a | b` 最後再 `return r & -r` 。
```c
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;
}
```
最後 for 迴圈的部分跟題目的 while 迴圈類似。遠本題目 while 迴圈的中止條件是 `v == 0` ， linux kernel 版本的則是提前判斷 `a == 0` 並回傳值。若 `a == b` 則下一個 cycle `a = 0` ， 所以當 `a == b` 回傳 `a << __ffs(r)` ，這裡的 ` << __ffs(r)` 的作用跟題目的 `<< shift` 一樣。
理論上 `if(a == b)` 就足以滿足所有的情況，但是 linux kernel 為了追求效率增加了一個判斷 `a == 1` ，若沒有提前判斷，則還需要多跑 `b` 個 cycle。
我使用 `perf` 來驗證我的想法，結果如下。
```bash
// No if(a == 1)
kuan@Athena:~/linux2022/q_w2/q3$ sudo perf stat --repeat 5 ./gcd_kernel.out
Performance counter stats for './gcd_kernel.out' (5 runs):
3,469.76 msec task-clock # 1.000 CPUs utilized ( +- 0.03% )
437 context-switches # 126.003 /sec ( +- 0.42% )
0 cpu-migrations # 0.000 /sec
45 page-faults # 12.854 /sec ( +- 1.14% )
11,749,988,006 cycles # 3.386 GHz ( +- 0.00% )
10,470,285,345 instructions # 0.89 insn per cycle ( +- 0.00% )
2,271,862,655 branches # 654.761 M/sec ( +- 0.00% )
391,531,278 branch-misses # 17.23% of all branches ( +- 0.00% )
3.47131 +- 0.00112 seconds time elapsed ( +- 0.03% )
// with if(a == 1)
kuan@Athena:~/linux2022/q_w2/q3$ sudo perf stat --repeat 5 ./gcd_kernel.out
Performance counter stats for './gcd_kernel.out' (5 runs):
3,085.58 msec task-clock # 1.000 CPUs utilized ( +- 0.06% )
390 context-switches # 126.459 /sec ( +- 0.47% )
0 cpu-migrations # 0.000 /sec
44 page-faults # 14.390 /sec ( +- 0.55% )
10,449,478,448 cycles # 3.387 GHz ( +- 0.04% )
10,309,367,245 instructions # 0.99 insn per cycle ( +- 0.00% )
2,642,511,309 branches # 856.407 M/sec ( +- 0.00% )
336,945,564 branch-misses # 12.75% of all branches ( +- 0.06% )
3.08701 +- 0.00201 seconds time elapsed ( +- 0.06% )
```
```c
// benchmark
int main(void)
{
for (int i = 1; i < 10000; i++) {
for (int j = 1; j < 10000; j++) {
gcd64(i, j);
}
}
return 0;
}
```
從 perf 測出來的數據來看，雖然 branch 增加但是 branch-misses 並沒有增且，而且跑的 cycle 數更少。
:::info
- [x] 解釋上述程式碼運作的原理
- [x] 在 x86_64 上透過 __builtin_ctz 改寫 GCD，分析對效能的提升;
- [x] Linux 核心中也內建 GCD (而且還不只一種實作)，例如 lib/math/gcd.c，請解釋其實作手法和探討在核心內的應用場景。
:::
## 測驗 `4`
```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 ^= t` 會把最靠近 `LSB` 的 `1` 換為 `0`。比如說：
* 當 `bitset = 0x00001010` 則 `t = 0x00000010`
可以透過 `t = bitset & -bitset` 達到。 為了幫助理解，先把 `-bitset` 換成 `~bitset + 1`。
設 `bitset = 0x00001010` ，先考慮 `bitsey & ~bitset`：
* `bitset = 0x00001010` `~bitset = 0x11110101`
* 這樣算出來的值會是 `0x00000000`
若考慮 `bitsey & (~bitset + 1)`
* `bitset = 0x00001010` `~bitset = 0x11110110`
* * 這樣算出來的值會是 `0x00000010`
這是因為對 `~bitset` 加 1 會讓**連續的1** 進位到 `bitset` 第一個 `1` 的位置。
:::info
- [x] 解釋上述程式運作原理，並舉出這樣的程式碼用在哪些真實案例中;
- [ ] 設計實驗，檢驗 ctz/clz 改寫的程式碼相較原本的實作有多少改進？應考慮到不同的 bitmap density;
- [ ] 思考進一步的改進空間
- [ ] 閱讀 Data Structures in the Linux Kernel 並舉出 Linux 核心使用 bitmap 的案例
:::
## 測驗 `5`
`fractionToDecimal` 分成兩部分處理：
* 初始化 & 小數點之前
* 小數點之後
```c
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;
}
```
`result` 用來儲存輸出的字串， `p` 用來把 `char` 填入字串中。接著排除當 `denominator ==0` 或 `numerator == 0` 的特殊狀況。
```c
/* 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++ = '-';
```
這裡把 `n` 和 `d` 強制轉成正整數，為了後面的計算方便。並且決定輸出字串的正負號。
```c
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++ = '.';
```
這裡開始計算小數點前的數字，用 `sprintf` 把 `division` 填入輸出字串中。因為 `sprintf` 部會更改 `p` 到下一個填入的位置，因此要使用 `result + strlen(result)` 更新位置。
```c
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;
```
```c
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;
}
```
這裡負責處理小數點後的輸出，並且把小數點後的數字暫時放在 `decimal` 裡，因為如我果有循環小數出現，輸出需要再循環的前後加上 `()` 。
循環的判定方法是根據 `remainder` 是否跟前面的是否有重複，因為除數固定， 被除數一樣時答案會一樣。
建立一個 `hash table` 以 `ramainder` 為 key 紀錄在 `decimal` 字串的 index。每次更新 `remainder` 時就先在 `hash table` 裡查詢是否有重複。
若找到重複的，也就是 `pos > 0` 則先把在 `decimal` 裡非循環的小數部分填入 `result` 中。因此 `PPP = pos--`。
若沒找到重複的則要新增節點到對應的 list 中。根據 `find` 可以知道 hash 的方法是 `key % size` 。 因此 `MMM = list_add` 、 `EEE = &heads[remainder % size]` 。
`
:::info
- [x] 解釋上述程式碼運作原理，指出其中不足，並予以改進
- [ ] 在 Linux 核心原始程式碼的 mm/ 目錄 (即記憶體管理) 中，找到特定整數比值 (即 fraction) 和 bitwise 操作的程式碼案例，予以探討和解說其應用場景
:::
## 測驗 `6`
```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)
```
我們要計算 `t` 的起始位置，然後再減去參考位置，就會是 `t` 的 alignment。
因此 `M = _h` 、 `X = 0` 。
:::info
- [x] 解釋上述程式碼運作原理
- [ ] 在 Linux 核心原始程式碼中找出 __alignof__ 的使用案例 2 則，並針對其場景進行解說
- [ ] 在 Linux 核心源使程式碼找出 ALIGN, ALIGN_DOWN, ALIGN_UP 等巨集，探討其實作機制和用途，並舉例探討 (可和上述第二點的案例重複)。思索能否對 Linux 核心提交貢獻，儘量共用相同的巨集
:::
## 測驗 `7`
```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;
}
```
`is_divisble` 用來判斷是不是某個識字的倍數，以判斷 3 的倍數為例：
* `uint64_t M = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;`
* `n * M <= M - 1` 可以判斷 `n` 是否為 3 的倍數。因為當 `n` 為 3 的倍數時會因為 overflow 的關係使得 `n * M = n * 1` ， 小於 `M - 1`。 當 `n` 不為 3 的倍數時 必定至少有 ` UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1` ， 因為不是 3 的倍數無法完整的透過 overflow 讓 `UINT64_C(0xFFFFFFFFFFFFFFFF) / 3` 歸零。
* 但是當 `n` 大於 `UINT64_C(0xFFFFFFFFFFFFFFFF) / 3` 會出現錯誤，因為根據上述的推斷可知 `n * M = n * 1` ， 使得 `n * 1 <= M - 1` 不成立。在 function `is_divisible` 有個細節是 `n` 被宣告為 `uint32_t` ， 因此不會有 `n > UINT64_C(0xFFFFFFFFFFFFFFFF)` / 3 的情況發生。
要根據 `div3` 和 `div5` 輸出對應的字串，相關參數如下：
| div3 | div5 | start | length |
| ---- | ---- | ----- | ------ |
| 0 | 0 | 8 | 2 |
| 1 | 0 | 0 | 4 |
| 0 | 1 | 4 | 4 |
| 1 | 1 | 0 | 8 |
`length = (2 << KK1) << kk2` 固 `KK1 = div3` 、 `KK2 = div5` 。
從 `div3 = div5 = 1` 和 `div3 = div5 = 0` 的情況可推知 `KK3 = div3 << 2` 。
Sign in with Wallet
Connect another wallet