# 2022q1 Homework3 (quiz3)
contributed by < [tommy2234](https://github.com/tommy2234) >
題目連結 [quiz3](https://hackmd.io/@sysprog/linux2022-quiz3#2022q1-%E7%AC%AC-3-%E9%80%B1%E6%B8%AC%E9%A9%97%E9%A1%8C)
## 測驗 1
GENMASK
```cpp
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
答案：
```cpp
#define GENMASK(h, l) \
(((~0UL) >> (63 - h)) & ((~0UL) >> (l) << (l)))
```
- 0UL 代表 unsigned long 的 0，也就是 64 個 bits 的 0，所以 ~0UL 就得到 64 個 1 的 bits
- 前半段的 `((~0UL) >> (63 - h))` 將比 h 高位的 bits 清零，後半段的 `((~0UL) >> (l) << (l))` 則是將比 l 低位的 bits 清零
將前後兩者做 and 就可以產生 bit l 到 bit h 為 1 ，其他 bits 為 0 的 mask
:::warning
TODO
1. 比較 Linux 核心 `GENMASK` 巨集的實作，闡述其額外的考量
2. 舉出 Linux 核心原始程式碼中二處 `GENMASK` 巨集和 [include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 的應用案例
:::
---
## 測驗 2
考慮以下程式碼:
函式 `fo_fd` 接受指定的地址 `v`，填入一個 `fd` 結構體，並確保第一個成員的地址得以依據〈[你所不知道的 C 語言：記憶體管理、對齊及硬體特性](https://hackmd.io/@sysprog/c-memory)〉描述，對 4 個位元組進行向下對齊 (即 C++ Boost 描述的 [align_down](https://www.boost.org/doc/libs/1_78_0/doc/html/align/reference.html#align.reference.functions.align_down))。
```cpp
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};
}
```
EXP1 : `(struct foo *) (v & ~3)`
函式傳入的 v 是 fd 的起始位置，而我們要使其第一個成員的位址對 4 個位元組進行向下對齊，也就是要使位址變成 4 bytes 的倍數，因此我們使用 `(v & ~3)
` 清除 v 中最小的兩個位元，再將其轉型為 `(struct foo *)` 。
:::warning
TODO
在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說
:::
---
## 測驗 3
考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 LeetCode [190\. Reverse Bits](https://leetcode.com/problems/reverse-bits/) 的描述。
```cpp
#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;
}
```
一開始的 `x = (x >> 4) | (x << 4)` 將 8 個位元前後做交換，由此可推得後面兩行操作也是想要用相同的方式，將前後兩組 4 位元分別用前後交換的方式反轉，如此由大至小直到每個每個位元都被反轉為止。
- EXP2 : `(x && 0x33) << 2`
- EXP3 : `(x && 0x55) << 1`
我們每次反轉一半，不斷遞迴直到完成反轉，這樣的手法類似 merge sort 裡面 divide and conquer 的概念。
:::warning
TODO
在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
:::
---
## 測驗 4
```cpp
#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__})))
```
從 `foreach_int` 和 `foreach_ptr` 的定義裡可以看到 for 迴圈裡的 iterator 被宣告成 `_foreach_i` 這個變數，而 EXP4 和 EXP5 是迴圈尾部的 statement ， 也就是要對 `_foreach_i` 做 increment。
- EXP4 : `++_foreach_i`
- EXP5 : `++_foreach_i`
:::warning
TODO
在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景
:::
---
## 測驗 5
針對 LeetCode [29\. Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)，以下是可能的實作:
```cpp
#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;
}
```
兩數相除的結果其實就是被除數能夠減去除數而不小於零的最大次數，本題依照這樣的思路設計。
- Steps:
1. 一開始先將結果的正負號存在 signal ，並且將兩數都化為正數再計算。
2. 每次迴圈都計算 `dvd < (dvs << shift)` 的條件下 shift 的最大值，然後把 `1 << shift` （也就是 2 的 shift 次方）累計在 res，再把 dvd 減去 `dvs << shift`。
3. 最後 `res * signal` 就是商數。另外 `INT_MIN / (-1)` 的結果會 overflow 需要特別處理，此時回傳 `INT_MAX`。
- ans :
EXP6 : `dvs << shift`
EXP7 : `dvd -= dvs << shift`
:::warning
TODO
1. 解釋上述程式碼運作原理，指出可改進之處，並予以實作
2. 在 Linux 核心原始程式碼中找出針對整數/浮點數/[定點數](https://en.wikipedia.org/wiki/Fixed-point_arithmetic)除法特別撰寫的程式碼，並予以討論
:::
---
## 測驗 7
考慮 `ilog32` 函式可針對給定的 32 位元無號數，計算扣除開頭的 `0`，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:
```cpp
int ilog32(uint32_t v)
{
int ret = v > 0;
int m = (v > 0xFFFFU) << 4;
v >>= m;
ret |= m;
m = (v > 0xFFU) << 3;
v >>= m;
ret |= m;
m = (v > 0xFU) << 2;
v >>= m;
ret |= m;
m = EXP10;
v >>= m;
ret |= m;
EXP11;
return ret;
}
```
此題用的方法是根據傳入的 v 的大小，一次向右 shift 數個位元，m 為每次需要 shift 的次數，並且將 shift 的次數累計在 ret ，最後累計的 shift 次數就是最高位的 1 所在的位置，也就是 (32 - number of leading 0's) 。
1. `m = (v > 0xFFFFU) << 4;`
`v >>= m;`
若最高位的 1 在第 16 位以上，就向右 shift 16 位。
2. `m = (v > 0xFFU) << 3`
`v >>= m;`
若最高位的 1 在第 8 位以上，就向右 shift 8 位。
3. `m = (v > 0xFU) << 2`
`v >>= m;`
若最高位的 1 在第 4 位以上，就向右 shift 4 位。
以此類推， `EXP10` 要填入 `(v > 0x3) << 1` ， `EXP11` 要填入 `ret += v > 0x1`。
:::warning
1. 在 Linux 核心原始程式碼找出類似實作並解說其應用場景
2. 研讀論文《[Using de Bruijn Sequences to Index a 1 in a Computer Word](http://supertech.csail.mit.edu/papers/debruijn.pdf)》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 `ilog`
3. 運用〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉和〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉提及的技巧，實作編譯時期 (compile-time) 的 `ilog2` 實作
:::
---
## 測驗 8
從 binary tree 中移除節點的程式碼如下：
```cpp
void remove_data(tree &t, int d)
{
tnode **p = &t;
while (*p != 0 && (*p)->data != d) {
if (d < (*p)->data)
EXP12;
else
EXP13;
}
tnode *q = *p;
if (!q)
return;
if (!q->left)
*p = q->right;
else if (!q->right)
*p = q->left;
else {
tnode **r = &q->right;
while ((*r)->left)
r = EXP14;
q->data = (*r)->data;
q = *r;
*r = q->right;
}
delete q;
}
```
其中第一個 while 迴圈的部份是在搜索 data 的位置，而二元樹的規則是左小右大，因此若 d 小於當前節點的 data，就要往左找，反之要往右找。
因此：
- EXP12 : `p = &(*p)->left`
- EXP13 : `p = &(*p)->right`
下方第二個 while 迴圈的目的是為了找到 right subtree 中最小的 node ，也就是 right subtree 中最左邊的 node ，來替補當前要被刪除的 node。
因此：
- EXP14 : `&(*r)->left`
:::warning
TODO
1. 以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升
2. 研讀 [Static B-Trees](https://en.algorithmica.org/hpc/data-structures/s-tree/)，探討針對記憶體佈局 (memory layout) 的改進策略
:::
Sign in with Wallet
Connect another wallet