---
tags: linux2022
---
# 2022q1 Homework3 (quiz3)
contributed by < [`jj97181818`](https://github.com/jj97181818) >
## 測驗 1
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
1. 因為這裡的 unsigned long 為 8 bytes，所以 `~0UL` 有 64 bit 的 1。
2. 先討論 `((~0UL) >> (LEFT))`，為了讓連續的 bitmask 最高位到 `h` 停止，又因 LSB 從第 0 位開始算起，MSB 是第 63 位，所以需要讓 64 bit 的 1 向右移 `63 - h` 位。
3. 再來看 `((~0UL) >> (l) << (RIGHT))`，先將 64 bit 的 1 向右移 `l` 位，為了讓連續的 bitmask 最低位從第 `l` 位開始，就再左移 `l` 位，其餘會補 0，就實現從第 `l` 位開始。
4. 將 `((~0UL) >> (LEFT))` 和 `((~0UL) >> (l) << (RIGHT))` 做 AND 運算，即可同時滿足最高位到 `h`、最低位從 `l` 開始，即 GENMASK 巨集。
因此 `LEFT` = `63 - h`, `RIGHT` = `l`
## 測驗 2
```c
struct foo;
struct fd {
struct foo *foo;
unsigned int flags;
};
enum {
FOO_DEFAULT = 0,
FOO_ACTION,
FOO_UNLOCK,
} FOO_FLAGS;
static inline struct fd to_fd(unsigned long v)
{
return (struct fd){EXP1, v & 3};
}
```
1. `to_fd` 要將指定的位址 v 當作 fd 的起始位址，且要確保以 4 bytes 向下對齊，而向下對齊的巨集：
```c
#define align_down(x) ((x) & ~(MAX_ALIGNMENT - 1))
```
`v & ~(4 - 1)` = `v & ~3` = `v & 1100`
透過將位址 v 的最後兩位 clear 掉，來保證該位址一定為 4 的倍數，做到向下對齊。
2. 因為該位址是 fd 的起始位址，會有個指向 fd 第一個成員 struct foo 的指標，所以會需要在位址前加上 `(struct foo *)`。
因此 `EXP1` = `(struct foo *)(v & ~3)`
## 測驗 3
```c
#include <stdint.h>
uint8_t rev8(uint8_t x)
{
x = (x >> 4) | (x << 4);
x = ((x & 0xCC) >> 2) | (EXP2);
x = ((x & 0xAA) >> 1) | (EXP3);
return x;
}
```
目標是從 12345678 變成 87654321（這裡的 1~8 都是代表著 0 或 1 的值，只是用 1~8 來表示比較能清楚看出 reverse 的過程）：
1. `x = (x >> 4) | (x << 4);`
```
(12345678 >> 4) | (12345678 << 4)
= 00001234 | 56780000
= 56781234
```
這行可以看出從 8 bit 的中間切成兩半，並互換。
2. `x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);`
```
((56781234 & 11001100) >> 2) | ((56781234 & 00110011) << 2)
= (56001200 >> 2) | (00780034 << 2)
= 00560012 | 78003400
= 78563412
```
這行接著上一行切兩半的方式，先用遮罩 0xCC 取得原本位在 1, 2, 5, 6 的值，那 `EXP2` 的位置一定需要保留 3, 4, 7, 8 的位置，才能讓 x 保留原本 1~8 位置的所有值，因此這裡選用 0x33 當作遮罩，並左移兩位，在與 `((x & 0xCC) >> 2)` 做 OR 運算時，即可保留所有資訊，並切從 4 bit 中間切成兩半做互換。
3. `x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);`
```
((78563412 & 10101010) >> 1) | ((78563412 & 01010101) << 1)
= (70503010 >> 1) | (08060402 << 1)
= 07050301 | 80604020
= 87654321
```
這行與上一行同樣的概念，只是改為每兩個 bit 中間切兩半做互換，可以看到這裡用的遮罩為 0xAA，並右移一位，而另外一個遮罩可以推得是 `0x55`，同樣要記得左移一位，就完成互換的動作了。從最初的 12345678 變成 87654321。
因此 `EXP2` = `(x & 0x33) << 2`, `EXP3` = `(x & 0x55) << 1`
## 測驗 4
```c
#include <assert.h>
#define _foreach_no_nullval(i, p, arr) \
assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))
#define foreach_int(i, ...) \
for (unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0); \
_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int); \
(i) = ((int[]){__VA_ARGS__, 0})[EXP4])
#define foreach_ptr(i, ...) \
for (unsigned _foreach_i = \
(((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0); \
(i); (i) = (void *) ((typeof(i)[]){__VA_ARGS__, \
NULL})[EXP5], \
_foreach_no_nullval(_foreach_i, i, \
((const void *[]){__VA_ARGS__})))
```
逗號運算子：`(expression1, expression2)`
首先計算表達式 1，然後計算表達式 2，並為整個表達式返回表達式 2 的值。
1. `foreach_int` macro 中，有個 for 迴圈：
+ 初始條件：`unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0)`
+ `((int[]){__VA_ARGS__})[0]` 為整數陣列，其中 `__VA_ARGS__` 會填入 `foreach_int` 從第二個以後的參數，當作整數陣列的值，並取得整數陣列的第 0 個值，然後將值 assign 給 `i`
+ 在逗號運算子的第一個表達式計算完成後，再將第二個表達式的值 0 回傳給 `_foreach_i`
+ 繼續執行的條件：`_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int)`
+ `sizeof((int[]){__VA_ARGS__}) / sizeof(int)` 會得到整數陣列的元素數量
+ 在 `_foreach_i` 小於元素數量時繼續執行迴圈
+ 遞增：`(i) = ((int[]){__VA_ARGS__, 0})[EXP4]`
+ 將 `_foreach_i` 先加 1，然後就可以讓 i 取得下一個整數陣列的元素
+ EXP4 為 `++_foreach_i`
2. `foreach_ptr` macro 中，也有個 for 迴圈：
+ 初始條件：`unsigned _foreach_i = (((i) = (void *)((typeof(i)[]){__VA_ARGS__})[0]), 0)`
+ `((typeof(i)[]){__VA_ARGS__})[0]` 是一個型別為 `typeof(i)` 的陣列，然後取出陣列第 0 個位置的值，這個值可以預期傳入的是位址，因為這個巨集的名稱是 `foreach_ptr`
+ `((i) = (void *)((typeof(i)[]){__VA_ARGS__})[0])` 將值強轉型為指向 void 的指標，然後 assign 給 `i`。
+ 然後 0 assign 給 `_foreach_i`
+ 繼續執行的條件：`(i)`
+ 只要 `i` 不為 0 就會繼續執行迴圈
+ 遞增：
+ 和 EXP4 一樣的概念，EXP5 為 `++_foreach_i`
```c
(i) = (void *) ((typeof(i)[]){__VA_ARGS__, NULL})[EXP5],
_foreach_no_nullval(_foreach_i, i, ((const void *[]){__VA_ARGS__}))
```
因此 `EXP4` = `++_foreach_i`, `EXP5` = `++_foreach_i`
## 測驗 5
```c
#include <limits.h>
int divide(int dividend, int divisor)
{
int signal = 1;
unsigned int dvd = dividend;
if (dividend < 0) {
signal *= -1;
dvd = ~dvd + 1;
}
unsigned int dvs = divisor;
if (divisor < 0) {
signal *= -1;
dvs = ~dvs + 1;
}
int shift = 0;
while (dvd > (EXP6))
shift++;
unsigned int res = 0;
while (dvd >= dvs) {
while (dvd < (dvs << shift))
shift--;
res |= (unsigned int) 1 << shift;
EXP7;
}
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
}
```
1. 以 `signal` 來紀錄相除結果的正負號，然後如果除數或被除數為負整數，一律改為正整數。
2. `shift` 從 0 開始，當 `dvd > (EXP6)` 時，shift 加 1，因為這題目的是要做除法，這裡的 EXP6 一定會和除數 `dvs` 有關。這個迴圈會在 `shift` 愈來愈大之後在某個條件下停止，可想到的是將 dvs 左移 shift 位，當 shift 愈大，`dvs` 也愈大，直到超過或等於 `dvd` 的大小。這裡 `shift` 的意義是類似商的概念，看除數乘以多大的倍數（左移多少位）能夠比被除數大或至少相等。
3. 在被除數 `dvd` 仍大於等於除數 `dvs` 時，表示可以繼續進行除法。當 `dvs` 左移 `shift` 位會比 `dvd` 大時，就將 `shift` 減 1。`1 << shift;` 的想法是將小於 `dvd` 並左移過後的 `dvs` 只取其最高位元，用 1 左移 `shift` 位來表達。
4. 因為迴圈要 `dvd` 小於 `dvs` 才會停止，EXP7 要更新 `dvd`，而 `dvd` 減去 `dvs` 左移 `shift` 位，就是更新被除數，讓它減去除數乘以一個倍數。
5. 當被除數 `dvd` 不再大於等於除數 `dvs` 時，相除的結果如果超出能表達的最大值，就直接回傳 INT_MAX。其餘則回傳除完的結果。
因此 `EXP6` = `dvs << shift`, `EXP7` = `dvd -= dvs << shift`
## 測驗 6
## 測驗 7
```c
int ilog32(uint32_t v)
{
int ret = v > 0; // 1, 0000 0001
int m = (v > 0xFFFFU) << 4; // 16 , 0001 0000
v >>= m;
ret |= m; // 0001 0001
m = (v > 0xFFU) << 3; // 8, 0000 1000
v >>= m;
ret |= m; // 0001 1001
m = (v > 0xFU) << 2; // 4, 0000 0100
v >>= m;
ret |= m; // 0001 1101
m = EXP10; // EXP10 = (v > 0x3U) << 1 2, 0000 0010
v >>= m;
ret |= m; // 0001 1111
EXP11;
return ret;
}
```
限制：
+ EXP10 和 EXP11 皆包含 > 運算子
ilog32 與 ffs 的實作很像，只是 ffs 是從 LSB 開始找第一個為 1 的 bit，這裡是從 MSB 找第一個為 1 的 bit。
1. 最初的 `ret = v > 0` 是要記錄當 v > 0 時，最高位的 1 也需要一個位元儲存。
2. 程式主體是做以下的操作 4 次。
+ 更新 m
+ 將 v 右移 m 位
+ 更新 ret。
3. 第一次先操作將 32 位元切半來看，比較高位元的 16 bit 中有沒有 1，有的話代表至少要儲存 16 bit（`m` = 16），然後將 v 右移 16 位，為的是方便繼續觀察原本較高位元的 16 bit 中還需要多少 bit 儲存。接著 ret 會記錄到目前為止共需要 16 bit 來存這個 v。
4. 第二次就是將剩下 16 位元切半來看，看比較高位元的 8 bit 中有沒有 1，有的話代表至少要再多存 8 bit（`m` = 8），然後將 v 右移 8 位，方便繼續觀察原本較高位元的 8 bit 中還需要多少 bit 儲存。然後 ret 記錄到目前為止共需要 16 + 8 bit 來存這個 v。
5. 接著第三次和第四次分別是看 8 位元中較高位元的 4 bit，和 4 位元中較高位元的 2 bit，因此 EXP10 為 `(v > 0x3) << 1` 才能查看較高位元的 2 bit 中是否有 1。
6. 最後到 EXP11，只剩下最後兩位還沒判斷，如果 v > 1，那麼就代表最後兩位都需要儲存，而最高位元已經在最初的 `ret` = 1 就有加上一位了，所以只需要再加一位，EXP11 為 v > 1 時 `ret` 加上 1。
因此 `EXP10` = `(v > 0x3) << 1`, `EXP11` = `ret += v > 1`
## 測驗 8
## 測驗 9
### ROUND_UP 巨集
向上對齊：
```c
/* maximum alignment needed for any type on this platform, rounded up to a
power of two */
#define MAX_ALIGNMENT 16
/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
(((x) + MAX_ALIGNMENT - MMM) & ~(NNN))
```
1. 向上對齊是利用位運算的方法，計算記憶體對齊後的大小，這裡的 MAX_ALIGNMENT 是 16 bytes，向上對齊會以 16 的倍數往上取。
例如：原本大小（這裡的 x）為 1~16 的變數，在向上對齊之後大小都會變成 16，17~32 會變成 32，33~48 會變成 48。
2. 左段的程式 `((x) + MAX_ALIGNMENT - MMM)` 是將大小加上 alignment 的大小再減去 MMM，要讓原本大小不足 16 的都補到 16。MMM 應該為 1，因為當 x = 16 時，x + MAX_ALIGNMENT = 16 + 16 = 32，會讓 16 在對齊後變成 32。
3. 右段的程式 `~(NNN)` 是要去除不足 16 的餘數，因為最後算出來的值應該是 16 的倍數。
當 `NNN` = `MAX_ALIGNMENT - 1`時：
~(MX_ALIGNMENT - 1)
= ~(15)
= 11110000
4. `((x) + MAX_ALIGNMENT - 1) & ~(MAX_ALIGNMENT - 1)`
= (x + 16 - 1) & 11110000
= (x + 00001111) & 11110000
因此 `MMM` = `1`, `NNN` = `MAX_ALIGNMENT - 1`
### ROUND_DOWN 巨集
向下對齊：
```c
/* maximum alignment needed for any type on this platform, rounded up to a
power of two */
#define MAX_ALIGNMENT 16
/* Given a size, round up to the next multiple of sizeof(void *) */
#define ROUND_DOWN_TO_ALIGNMENT_SIZE(x) \
((x) & ~(MAX_ALIGNMENT - 1))
```
因為向下對齊是將大小為 1~15 對齊成 0，16~31 對齊成 16，所以不需要加上 MX_ALIGNMENT 來補足不到 16 的餘數，不足的都直接不要了。
### 在 Linux 核心找出類似的巨集和程式碼
> 並說明 round-up/down 的應用場合
在 `linux/include/linux/netfilter_bridge/ebtables.h` 的[第 107 行](https://github.com/torvalds/linux/blob/fc02cb2b37fe2cbf1d3334b9f0f0eab9431766c4/include/linux/netfilter_bridge/ebtables.h#L107) ：
```c
#define EBT_ALIGN(s) (((s) + (__alignof__(struct _xt_align)-1)) & \
~(__alignof__(struct _xt_align)-1))
```
EBT_ALIGN 是做向上對齊。
## 測驗 10
```c
#define DIVIDE_ROUND_CLOSEST(x, divisor) \
({ \
typeof(x) __x = x; \
typeof(divisor) __d = divisor; \
(((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 || \
(((__x) > 0) == ((__d) > 0))) \
? ((RRR) / (__d)) \
: ((SSS) / (__d)); \
})
```
限制：
+ RRR 和 SSS 為表示式，且都包含 (__x) 和 (__d) (注意小括號)
+ RRR 和 SSS 限用 +, -, >>, << 這幾個運算子，可搭配小括號，並以符合 C99 的最精簡形式撰寫
+ 變數在 RRR 和 SSS 出現的順序 (從左到右)，必定是 __x 先於 __d
1. 先看三元運算子的條件
+ `((typeof(x)) -1) > 0` 在 x 的型別為 unsigned 的時候才會為 true
+ `((typeof(divisor)) -1) > 0` 在 divisor 的型別為 unsigned 的時候才會為 true
+ `(((__x) > 0) == ((__d) > 0))` 在兩個值皆大於 0 或小於 0 的時候，才為 true，也就是兩者同號為 true
2. 當上述三元運算子的任一條件為 true，運算結果會是 `((RRR) / (__d))`，即被除數或除數其中一個為 unsigned，或是兩者皆為有號數，但是同號。
3. 當上述三元運算子的條件皆為 false，運算結果會是 `((SSS) / (__d))`，即兩者皆為有號數，且不同號。
4. 所以要找最接近該數字的整數做為商的話，最初的想法是將除完的小數加上 0.5，然後加完之後只取整數的部分。如果加上 0.5 能夠讓讓小數部分進位到整數的話，就代表原本小數後第一位是大於等於 0.5 的，也就是原本就比較靠近該數字取 ceil，即往上找最接近的整數。反之，該數字會比較靠近它取 floor，即往下找最接近的整數。
5. 用題目給的例子來看：
+ DIVIDE_ROUND_CLOSEST(7, 3) = 2
+ 7 除以 3 大約等於 2.3...，2.3 + 0.5 = 2.8
+ 小數點後第一位並沒有進位到整數位，因此 2.3 往下找最接近的整數，即 2。或是 2.8 往下取最近整數。
+ DIVIDE_ROUND_CLOSEST(5, 3) = 2
+ 5 除以 3 大約等於 1.6...，1.6 + 0.5 = 2.1
+ 小數點後第一位有進位到整數位（整數從 1 變為 2），因此 1.6 往上找最接近的整數，即 2。或是 2.1 往下取最近整數。
6. 接著要思考 `RRR`, `SSS` 各自要怎麼表達才能做到上面的想法。因為 `((RRR) / (__d))` 中我能改變的只有 RRR 的部分，所以我做了一些調整，變成：
+ RRR 的部分
```c
以下四行的 / 先表示除到小數點後第一位
floor((__x) / (__d) + 0.5)
= floor((__x) / (__d) + (0.5 * (__d)) / (__d))
= floor(((__x) + 0.5 * (__d)) / (__d))
因為 C 語言中的 / 本來就是無條件捨去小數點第一位，所以可以刪除 floor：
= ((__x) + 0.5 * (__d)) / (__d)
然後 0.5 * (__d) 可改成 (__d) >> 1
= ((__x) + (__d) >> 1) / (__d)
```
+ SSS 的部分
只有被除數和除數為異號時，才會執行到這。經過除法運算之後，因為值為負的，所以原本加 0.5，這裡要換成減 0.5，才能達到讓小數後第一位進位到整數的效果。
```c
以下四行的 / 先表示除到小數點後第一位
floor((__x) / (__d) - 0.5)
= floor((__x) / (__d) + ((-0.5) * (__d)) / (__d))
= floor(((__x) + (-0.5) * (__d)) / (__d))
因為 C 語言中的 / 本來就是無條件捨去小數點第一位，所以可以刪除 floor：
= ((__x) - 0.5 * (__d)) / (__d)
然後 (-0.5) * (__d) 可改成 -(__d) >> 1
= ((__x) - (__d) >> 1) / (__d)
```
因此 `RRR` = `(__x) + (__d) >> 1`, `SSS` = `(__x) - (__d) >> 1`
## 測驗 11
fls 是找最高位 1 的位置。
```c
static inline unsigned long fls(unsigned long word)
{
int num = 64 - 1;
if (!(word & (~0ul << 32))) {
num -= 32;
word <<= 32;
}
if (!(word & (~0ul << (64 - 16)))) {
num -= 16;
word <<= 16;
}
if (!(word & (~0ul << (64 - 8)))) {
num -= 8;
word <<= 8;
}
if (!(word & (~0ul << (64 - 4)))) {
num -= 4;
word <<= 4;
}
if (!(word & (~0ul << (64 - 2)))) {
num -= 2;
word <<= 2;
}
if (!(word & (~0ul << (64 - 1))))
num -= 1;
return num;
}
```
參考 [Digit-by-digit calculation](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation)
假設今天要求 $N^2$ 的平方根 N，
定義 $N^2 = (a_n + ... + a_0)^2$，其中 $a_m$ 會是 $2^m$ 或 $0$（用二進制的概念），
要從 $P_n$ 一直迭代算到 $P_0$，慢慢逼近要求的 N（$P_i$ 會愈來愈靠近 N）：
$\quad\ P_n = a_n$
$\rightarrow P_{n-1} = a_n + a_{n-1}$
$\rightarrow \ ...$
$\rightarrow P_{m+1} = a_n + a_{n-1} + ... + a_{m+1}$
$\rightarrow P_m = a_n + a_{n-1} + ... + a_{m+1} + a_m$
$\rightarrow \ ...$
$\rightarrow P_0 = a_n + a_{n-1} + ... + a_{m+1} + a_m + ... + a_0$
由上可知：$P_m = P_{m+1} + a_m$，而 $a_m$ 會是 $2^m$ 或 $0$。
如果 $P_m^2 = (P_{m+1} + 2^m)^2 \leq N^2$（加上了 $2^m$ 也沒有超過 $N^2$），則 $a_m = 2^m$，且 $P_m = P_{m+1} + 2^m$；反之，則 $a_m = 0$，且 $P_m = P_{m+1}$。
為了避免在每一輪算 $P_m$ 的時候都要用 $P_m$ 的平方去決定 $a_m$ 是 $2^m$ 或 $0$，改用 $X_m = N^2 - P_m^2$（該輪 $P_m^2$ 和原本的 $N^2$ 還差多少，愈小代表 $P_m$ 愈靠近 $N^2$ 的平方根），
然後 $X_m = X_{m+1} - Y_m$（因為 $P_m$ 可能會比 $P_{m+1}$ 來的更靠近 N，所以在與 $N^2$ 的差異上，$X_m$ 可能會比 $X_{m+1}$ 小，其中 $Y_m$ 是 $X_m$ 和 $X_{m+1}$ 的差，是大於等於 0 的），
而 $Y_m = X_{m+1} - X_m = (N^2 - P_{m+1}^2) - (N^2 - P_{m}^2) = P_m^2 - P_{m+1}^2 = 2P_{m+1}a_m + a_m^2$。
上面有寫到會從 $P_n$ 一直迭代算到 $P_0$，首先是 $P_n = a_n$，為了確認 $a_n$ 是 $2^n$ 還是 $0$，將其代入 $P_m^2 = (P_{m+1} + 2^m)^2 \leq N^2 \rightarrow P_n^2 = (0 + 2^m)^2 \leq N^2$，所以確認 $a_n = 2^n$。
前面有提到 $Y_m = 2P_{m+1}a_m + a_m^2$，將其分成 $c_m$ 和 $d_m$ 兩部分：
（在確定 $a_m$ 為 $2^m$ 而不是 $0$ 後，$a_m$ 代入 $2^m$）
$c_m = 2P_{m+1}a_m = 2P_{m+1}2^m = P_{m+1}2^{m+1} \\
d_m = a_m^2 = (2^m)^2 \\
Y_m = \begin{cases}
c_m + d_m & \text{if } a_{m} = 2^{m} \\
0 & \text {if } a_{m} = 0
\end{cases}$
更新 $c_m$, $d_m$：
$c_{m-1} = P_m2^m = (P_{m+1}+a_m)2^m = P_{m+1}2^m + a_m2^{m} = \begin{cases}
c_m/2 + d_m & \text{if } a_{m} = 2^{m} \\
c_m/2 & \text {if } a_{m} = 0
\end{cases} \\
d_{m-1} = a_{m-1}^2 = (2^{m-1})^2 = \frac{d_m}{4}$
當 $c_{-1} = P_02^0 = P_0 = N$ 此時 c 就是要求的平方根。
```c
unsigned long i_sqrt(unsigned long x)
{
unsigned long b, m, y = 0;
if (x <= 1)
return x;
m = 1UL << (fls(x) & ~1UL);
while (m) {
b = y + m; // Y_m = c_m + d_m
y >>= 1; // c_m / 2
if (x >= b) { // X_m >= Y_m
x -= b; // X_{m-1} = X_m - Y_m
y += m; // c_{m-1} = c_m + d_m
}
m >>= 2; // dm / 4
}
return y;
}
```
將程式中的 `b` 看成上述的 $Y_m$，`m` 看成上述的 $d_m$，`x` 看成上述的 $X_m$，`y` 看成上述的 $c_m$，程式就是在迴圈不斷地更新 $c_m$ 和 $d_m$。
因此 `XXX` = `y >>= 1`, `YYY` = `x -= b`, `ZZZ` = `m >>= 2`
Sign in with Wallet
Connect another wallet