# 2022q1 Homework3 (quiz3)
###### tags: `linux2022`
> [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3)
## 測驗 1
在 Linux 核心原始程式碼，[include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 提及一個巨集 `GENMASK`，其作用是依據給定的範圍，產生連續的 bitmask，(h, l) 之間為 `1`，例如:
* `GENMASK(6, 4)` 產生 01110000
* `GENMASK(39, 21)` 產生 0x000000ffffe00000
已知我們使用的微處理器架構為 64 位元，且 `unsigned long` 為 8 位元組寬度 (符合 [LP64](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models) 資料模型)，以下是可能的 `GENMASK` 巨集的定義:
```c
#define GENMASK(h, l) \
(((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))
```
`LEFT=63-h`
`RIGHT=l`
```c
GENMASK(6, 4) = 01110000
~0 >> 1 = 01111111 (1 = 8-h-1 = 7-h)
~0 >> 4 = 00001111
~0 >> 4 << 4 = 11110000
GENMASK(6, 4) = (~0 >> 1) & (~0 >> 4 << 4)
```
:::info
延伸問題:
- [X] 解釋上述程式碼運作原理
- [X] 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量
- [ ] 舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例
:::
### GENMASK 實作
* 實作定義在 [include/linux/bits.h](https://github.com/torvalds/linux/blob/master/include/linux/bits.h)
```c
#define __GENMASK(h, l) \
(((~UL(0)) - (UL(1) << (l)) + 1) & \
(~UL(0) >> (BITS_PER_LONG - 1 - (h))))
#define GENMASK(h, l) \
(GENMASK_INPUT_CHECK(h, l) + __GENMASK(h, l))
```
* `GENMASK_INPUT_CHECK` 主要是用來確認是否 `l < h`，而且在確認 `l < h` 時，還會考慮 `l` 與 `h` 是否為 constant expression，否則在 compile time 得到 error
```c
/*
* Create a contiguous bitmask starting at bit position @l and ending at
* position @h. For example
* GENMASK_ULL(39, 21) gives us the 64bit vector 0x000000ffffe00000.
*/
#if !defined(__ASSEMBLY__)
#include <linux/build_bug.h>
#define GENMASK_INPUT_CHECK(h, l) \
(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
__is_constexpr((l) > (h)), (l) > (h), 0)))
#else
/*
* BUILD_BUG_ON_ZERO is not available in h files included from asm files,
* disable the input check if that is the case.
*/
#define GENMASK_INPUT_CHECK(h, l) 0
#endif
```
* [`__builtin_choose_expr (const_exp, exp1, exp2)`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 為 GCC 的 built-in function
* returns exp1 if `const_exp`, which is an integer constant expression, is nonzero. Otherwise it returns `exp2` (類似 `? :`)
* if `const_exp` evaluates to true, `exp2` is not evaluated even if it has side effects
* `BUILD_BUG_ON_ZERO()` 講解可見 [bit-field](https://hackmd.io/@unknowntpo/B1WzhkvKL/%2F%40sysprog%2Fc-bitfield%3Ftype%3Dview)，`l > h` 時會產生非零值，可以在 compile-time 的時候被告知有錯
* `__is_constexpr` 定義在 [tools/include/linux/const.h](https://github.com/torvalds/linux/blob/34c5c89890d6295621b6f09b18e7ead9046634bc/tools/include/linux/const.h)
```c
#define __is_constexpr(x) \
(sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))
```
[Linux Kernel's __is_constexpr Macro](https://stackoverflow.com/questions/49481217/linux-kernels-is-constexpr-macro) 提到
* **如果 `x` 是 Constant expressions** (§6.6.6)，乘上 0 時，根據 (§6.3.2.3) 知道會是 constant expression with the value 0，cast `void *` 會成為 null pointer constant
* if one operand is a null pointer constant, the result has the type of the other operand; otherwise, one operand is a pointer to void or a qualified version of void, in which case the result type is a pointer to an appropriately qualified version of void (§6.5.15.6)
```c
sizeof(int) == sizeof(*((int *) (NULL))) // if `x` was an integer constant expression
sizeof(int) == sizeof(*((void *)(....))) // otherwise
```
* 根據 [GNU C extension](https://gcc.gnu.org/onlinedocs/gcc/Pointer-Arith.html) 知道 `sizeof(void)==1`，因此當 `x` 是 integer constant expression 時，透過 `__is_constexpr` 會得到 1，否則 0
繼續讀 [Linux 核心原始程式碼巨集: max, min](https://hackmd.io/@sysprog/linux-macro-minmax) 相關實驗
## 測驗 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};
}
```
函式 `to_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))。其中 `struct foo;` 運用〈[你所不知道的 C 語言：指標篇](https://hackmd.io/@sysprog/c-pointer)〉提及的 forward declaration 技巧，可在實作階段才提供具體 `struct foo` 的定義。
在 [include/linux/align.h](https://github.com/torvalds/linux/blob/a48b0872e69428d3d02994dcfad3519f01def7fa/include/linux/align.h) 中可見 `ALIGN_DOWN`
```c
#define ALIGN_DOWN(x, a) __ALIGN_KERNEL((x) - ((a) - 1), (a))
```
[include/linux/const.h](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/include/uapi/linux/const.h)
```c
#define __ALIGN_KERNEL(x, a) __ALIGN_KERNEL_MASK(x, (typeof(x))(a) - 1)
#define __ALIGN_KERNEL_MASK(x, mask) (((x) + (mask)) & ~(mask))
```
舉例 `ALIGN_DOWN(7, 4)` :
1. `ALIGN_DOWN(x, a)`
$x = 7 = 000111_b$
$a = 4 = 000100_b$
2. `__ALIGN_KERNEL(x, a) `
$x - (a-1) = 000100_b$
$4 - 1 = 000011_b$
3. `__ALIGN_KERNEL_MASK(x, mask)`
$(000100_b + 000011_b)\&111100_b=000100_b$
其實就可以看成 `x & ~(a-1) = 7 & ~3 = 000111 & 111100 = 000100`
[Memory Operands](https://chi_gitbook.gitbooks.io/personal-note/content/memory_operands.html) 所畫的每一個小方塊代表的是一個byte。題目要求「起始位址」一定要是4個byte的整數倍，因此，v 為向下對齊到能被 4 整除的地址，求得 `EXP1 = v & ~3`
## 測驗 3
考慮以下程式碼，能將輸入的 8 位元無號整數逐一位元反轉，如同 [LeetCode 190. Reverse Bits](https://leetcode.com/problems/reverse-bits/) 的描述。
```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;
}
```
`0xCC = 11001100`, `EXP2 = (x & 0x33) << 2 = 00110011 << 2`
`0xAA = 10101010`, `EXP3 = (x & 0x55) << 1 = 01010101 << 1`
透過不斷切一半互換概念，例如 `x = 10100101`:
`10100101 >> 4 | 10100101 << 4 = 01011010`
`(01011010 & 11001100) >> 2 | (01011010 & 00110011) << 2 = 01011010`
`(01011010 & 10101010) >> 1 | (01011010 & 01010101) << 1 = 10100101`
## 測驗 4
延伸〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉，我們嘗試將 [foreach 巨集](https://en.wikipedia.org/wiki/Foreach_loop) 予以擴充，使得支援以下寫法:
```c
int i;
foreach_int(i, 0, -1, 100, 0, -99) {
printf("i is %i\n", i);
}
const char *p;
foreach_ptr(p, "Hello", "world") {
printf("p is %s\n", p);
}
```
預期輸出如下:
```
i is 0
i is -1
i is 100
i is 0
i is -99
p is Hello
p is world
```
```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__})))
```
#### _foreach_no_nullval
```c
#define _foreach_no_nullval(i, p, arr) \
assert((i) >= sizeof(arr) / sizeof(arr[0]) || (p))
```
`assert` 裡的條件應為真，否則程式中指，因此，當 `i` 小於 `sizeof(arr)/sizeof(arr[0])` 且 `p` 為是 NULL，程式中止，後面會在 `foreach_ptr` 做個舉例
#### foreach_int
> 在 C99 規格書 (6.5.17) 中明確規範 Comma operator
> **Syntax**
> expression , assignment-expression
> **Semantics**
> The left operand of a comma operator is evaluated as a void expression; there is a sequence point after its evaluation. Then the right operand is evaluated; the result has its type and value.
```c
unsigned _foreach_i = (((i) = ((int[]){__VA_ARGS__})[0]), 0)
```
* `__VA_ARGS__` 是 [Variadic Macros](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html) 為不定參數巨集，將最後一個有命名的變數之後連同逗號一併替換掉 (`...`)，並將第一個元素賦值給 `i`，接著將 `0` 賦值給 `_foreach_i`
```c
_foreach_i < sizeof((int[]){__VA_ARGS__}) / sizeof(int)
```
* 迴圈終止條件為 `_foreach_i` 大於 `...` 的元素個數
```c
(i) = ((int[]){__VA_ARGS__, 0})[EXP4]
```
* `EXP4 = ++_foreach_i`，將各個元素賦值給 `i`，如不慎寫成 `_foreach_i++` 會讓第一個元素重複出現
#### foreach_ptr
```c
unsigned _foreach_i = (((i) = (void *) ((typeof(i)[]){__VA_ARGS__})[0]), 0)
```
* `typeof(i)` 得到 `i` 的型態，同樣地將第一個元素 (此元素為 pointer) 轉型成 `void*` 賦值給 `i`，接著將 `0` 賦值給 `_foreach_i`
```c
(i)
```
* 迴圈終止條件為 `i` 是 NULL
```c
(i) = (void *) ((typeof(i)[]){__VA_ARGS__, \
NULL})[EXP5], \
_foreach_no_nullval(_foreach_i, i, \
((const void *[]){__VA_ARGS__})))
```
* `EXP5 = ++_foreach_i`
以下程式碼會使 `_foreach_no_nullval` 觸發終止條件
```c
const char *p;
foreach_ptr(p, "Hello", NULL, "world") {
printf("p is %s\n", p);
}
```
## 測驗 5
針對 [LeetCode 29. Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)，以下是可能的實作:
```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;
// 用 shift 快速找到比被除數大的數
while (dvd > (EXP6))
shift++;
unsigned int res = 0;
// 當被除數比除數大時
while (dvd >= dvs) {
// 當除數 left shift 比被除數大
while (dvd < (dvs << shift))
shift--;
// set shift 的那個 bit
res |= (unsigned int) 1 << shift;
EXP7;
}
if (signal == 1 && res >= INT_MAX)
return INT_MAX;
return res * signal;
}
```
`EXP6 = dvs << shift`
`EXP7 = dvd -= dvs << shift`
例如 :
$10 = 1010, 3 = 0011$
`第 18 行` : $shift = 2$，表示 $3*4 > 10$
Loop 1 :
$dvd = 10, dvs = 3$
`第 26 行` : $shift = 1$，表示 $3*2 < 10$，這個 $2$ 就是商
`第 30 行` : $10 - 3*2 = 4$，這個 $4$ 是餘式，是下一次迴圈的被除數
Loop 2 :
$dvd = 4, dvs = 3$
`第 26 行` : $shift = 0$，表示 $3*1 < 4$，這個 $1$ 就是商
`第 30 行` : $4 - 3*1 = 1$，這個 $1$ 餘式，$1 < 3$，停止迴圈
## 測驗 6
針對 [LeetCode 149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)，以下是可能的實作:
```c
#include <stdbool.h>
#include "list.h"
struct Point {
int x, y;
};
struct point_node {
int p1, p2;
struct list_head link;
};
static bool can_insert(struct list_head *head, int p1, int p2)
{
struct point_node *pn;
list_for_each_entry (pn, head, link)
return EXP8;
return true;
}
static int gcd(int x, int y)
{
while (y) {
int tmp = y;
y = x % y;
x = tmp;
}
return x;
}
static int maxPoints(struct Point *points, int pointsSize)
{
if (pointsSize <= 2)
return pointsSize;
int i, j, slope_size = pointsSize * pointsSize / 2 + 133;
int *dup_cnts = malloc(pointsSize * sizeof(int));
int *hori_cnts = malloc(pointsSize * sizeof(int));
int *vert_cnts = malloc(pointsSize * sizeof(int));
int *slope_cnts = malloc(slope_size * sizeof(int));
memset(hori_cnts, 0, pointsSize * sizeof(int));
memset(vert_cnts, 0, pointsSize * sizeof(int));
memset(slope_cnts, 0, slope_size * sizeof(int));
for (i = 0; i < pointsSize; i++)
dup_cnts[i] = 1;
struct list_head *heads = malloc(slope_size * sizeof(*heads));
for (i = 0; i < slope_size; i++)
INIT_LIST_HEAD(&heads[i]);
for (i = 0; i < pointsSize; i++) {
for (j = i + 1; j < pointsSize; j++) {
if (points[i].x == points[j].x)
hori_cnts[i]++, hori_cnts[j]++;
if (points[i].y == points[j].y)
vert_cnts[i]++, vert_cnts[j]++;
if (points[i].x == points[j].x && points[i].y == points[j].y)
dup_cnts[i]++, dup_cnts[j]++;
if (points[i].x != points[j].x && points[i].y != points[j].y) {
int dx = points[j].x - points[i].x;
int dy = points[j].y - points[i].y;
int tmp = gcd(dx, dy);
dx /= tmp;
dy /= tmp;
int hash = dx * dy - 1333 * (dx + dy);
if (hash < 0)
hash = -hash;
hash %= slope_size;
if (can_insert(&heads[hash], i, j)) {
struct point_node *pn = malloc(sizeof(*pn));
pn->p1 = i;
pn->p2 = j;
EXP9;
}
}
}
}
for (i = 0; i < slope_size; i++) {
int index = -1;
struct point_node *pn;
list_for_each_entry (pn, &heads[i], link) {
index = pn->p1;
slope_cnts[i]++;
}
if (index >= 0)
slope_cnts[i] += dup_cnts[index];
}
int max_num = 0;
for (i = 0; i < pointsSize; i++) {
if (hori_cnts[i] + 1 > max_num)
max_num = hori_cnts[i] + 1;
if (vert_cnts[i] + 1 > max_num)
max_num = vert_cnts[i] + 1;
}
for (i = 0; i < slope_size; i++) {
if (slope_cnts[i] > max_num)
max_num = slope_cnts[i];
}
return max_num;
}
```
## 測驗 7
考慮 `ilog32` 函式可針對給定的 32 位元無號數，計算扣除開頭的 `0`，最少需要多少位元才可儲存 (the minimum number of bits required to store an unsigned 32-bit value without any leading zero bits)，以下是一個可能的實作:
```c=
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;
}
```
`EXP10 = (v > 0x3U) << 1`
`EXP11 = ret += v >> 1;`
* 首先我們觀察以下程式碼，當 `v` 大過 `0xFFFF ` 時，`m = 1 << 4`，並將 `v >> 16`，以及 set `ret` 所對應的 bit
```c
int m = (v > 0xFFFFU) << 4;
v >>= m;
ret |= m;
```
* 同理可推得 `EXP10 = (v > 0x3U) << 1`
* 假設測資為 `v = 0x111111U` 在第 15 行時，`v = 0x11U`，此時的 `ret` 為 `0x101 = 5`。同樣地，`v = 0x11111U` 在第 15 行時，`v = 0x1U`，此時的 `ret` 也為 `0x101 = 5`
* 最後 `ret` 結果會加 1 或不加 1 是取決於 `v >> 1` 後是否等於 0，因此可推得 `ret += v >> 1;`
## 測驗 8
考慮以下 C++ 二元搜尋樹的程式:
```c
typedef struct tnode *tree;
struct tnode {
int data;
tnode *left;
tnode *right;
tnode(int d)
{
data = d;
left = right = 0;
}
};
```
`remove_data` 為刪除樹中 `data` 為 `d` 的節點函式
```c=
void remove_data(tree &t, int d)
{
tnode *p = t;
tnode *q;
while (p != 0 && p->data != d) {
if (d < p->data) {
q = p;
p = p->left;
} else {
q = p;
p = p->right;
}
}
if (p != 0) {
if (p->left == 0)
if (p == t)
t = p->right;
else if (p == q->left)
q->left = p->right;
else
q->right = p->right;
else if (p->right == 0)
if (p == t)
t = p->left;
else if (p == q->left)
q->left = p->left;
else
q->right = p->left;
else {
tnode *r = p->right;
while (r->left) {
q = r;
r = r->left;
}
p->data = r->data;
if (r == p->right)
p->right = r->right;
else
q->left = r->right;
p = r;
}
delete p;
}
}
```
假設今天有一二元搜尋樹，如下圖所示
```graphviz
digraph G {
rankdir = TB
node[shape = "record"]
tnode1[label = "<a>趙 | {data = 5 | {<l>*left | <r>*right}}"]
tnode2[label = "<a>錢 | {data = 3 | {<l>*left | <r>*right}}"]
tnode3[label = "<a>孫 | {data = 7 | {<l>*left | <r>*right}}"]
tnode4[label = "<a>李 | {data = 6 | {<l>*left | <r>*right}}"]
tnode5[label = "<a>周 | {data = 8 | {<l>*left | <r>*right}}"]
tnode6[label = "<a>吳 | {data = 4 | {<l>*left | <r>*right}}"]
tnode1:<r> -> tnode3:<a>
tnode1:<l> -> tnode2:<a>
tnode3:<l> -> tnode4:<a>
tnode3:<r> -> tnode5:<a>
tnode2:<r> -> tnode6:<a>
}
```
若我們要刪除 `data` 為 7 的值，由 5~13 行可得到以下 `p` 與 `q` 兩個指標
```graphviz
digraph G {
rankdir = TB
node[shape = "record"]
tnode1[label = "<a>趙 | {data = 5 | {<l>*left | <r>*right}}"]
tnode2[label = "<a>錢 | {data = 3 | {<l>*left | <r>*right}}"]
tnode3[label = "<a>孫 | {data = 7 | {<l>*left | <r>*right}}"]
tnode4[label = "<a>李 | {data = 6 | {<l>*left | <r>*right}}"]
tnode5[label = "<a>周 | {data = 8 | {<l>*left | <r>*right}}"]
tnode6[label = "<a>吳 | {data = 4 | {<l>*left | <r>*right}}"]
p[shape = plaintext, label = "p"]
q[shape = plaintext, label = "q"]
tnode1:<r> -> tnode3:<a>
tnode1:<l> -> tnode2:<a>
tnode3:<l> -> tnode4:<a>
tnode3:<r> -> tnode5:<a>
tnode2:<r> -> tnode6:<a>
p -> tnode3:<a>
q -> tnode1:<a>
}
```
欲刪除的 `p` 有 left child 與 right child，因此進入 29 行，根據 [Binary Search Tree: Sort(排序)、Delete(刪除資料)](http://alrightchiu.github.io/SecondRound/binary-search-tree-sortpai-xu-deleteshan-chu-zi-liao.html) 提到的 Case 3，我們需要找到趙的 Successor 來當作替身
> Successor找的是「right subtree中Key最小的node」
Predecessor找的是「left subtree中Key最大的node」
透過 30~34 行就能找到趙的 Successor 是周，35 行就使出了替身攻擊
```graphviz
digraph G {
rankdir = TB
node[shape = "record"]
tnode1[label = "<a>趙 | {data = 5 | {<l>*left | <r>*right}}"]
tnode2[label = "<a>錢 | {data = 3 | {<l>*left | <r>*right}}"]
tnode3[label = "<a>孫 | {data = 8 | {<l>*left | <r>*right}}"]
tnode4[label = "<a>李 | {data = 6 | {<l>*left | <r>*right}}"]
tnode5[label = "<a>周 | {data = 8 | {<l>*left | <r>*right}}"]
tnode6[label = "<a>吳 | {data = 4 | {<l>*left | <r>*right}}"]
p[shape = plaintext, label = "p"]
q[shape = plaintext, label = "q"]
r[shape = plaintext, label = "r"]
tnode1:<r> -> tnode3:<a>
tnode1:<l> -> tnode2:<a>
tnode3:<l> -> tnode4:<a>
tnode3:<r> -> tnode5:<a>
tnode2:<r> -> tnode6:<a>
p -> tnode3:<a>
q -> tnode3:<a>
r -> tnode5:<a>
}
```
如果 `r == p->right`，則 `r` 的 right pointer 指派給 `p` 的 right pointer
```graphviz
digraph G {
rankdir = TB
node[shape = "record"]
tnode1[label = "<a>趙 | {data = 5 | {<l>*left | <r>*right}}"]
tnode2[label = "<a>錢 | {data = 3 | {<l>*left | <r>*right}}"]
tnode3[label = "<a>孫 | {data = 8 | {<l>*left | <r>*right}}"]
tnode4[label = "<a>李 | {data = 6 | {<l>*left | <r>*right}}"]
tnode5[label = "<a>周 | {data = 8 | {<l>*left | <r>*right}}"]
tnode6[label = "<a>吳 | {data = 4 | {<l>*left | <r>*right}}"]
p[shape = plaintext, label = "p"]
q[shape = plaintext, label = "q"]
r[shape = plaintext, label = "r"]
NULL[shape = plaintext, label = "NULL"]
tnode1:<r> -> tnode3:<a>
tnode1:<l> -> tnode2:<a>
tnode3:<l> -> tnode4:<a>
tnode3:<r> -> NULL
tnode2:<r> -> tnode6:<a>
p -> tnode3:<a>
q -> tnode3:<a>
r -> tnode5:<a>
}
```
最後透過 `p = r` ，並 `delete p` 刪除節點
函式 `remove_data` 嘗試將指定的資料，自給定的二元搜尋樹移除，但原本的 `remove_data` 過於冗長，於是我們可善用 indirect pointer 改寫為以下:
```c=
void remove_data(tree &t, int d)
{
tnode **p = &t;
while (*p != 0 && (*p)->data != d) {
if (d < (*p)->data)
p = &(*p)->left; // EXP12
else
p = &(*p)->right; // 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 = &(*r)->left; // EXP14
q->data = (*r)->data;
q = *r;
*r = q->right;
}
delete q;
}
```
```graphviz
digraph G {
rankdir = TB
node[shape = "record"]
tnode1[label = "<a>趙 | {data = 5 | {<l>*left | <r>*right}}"]
tnode2[label = "<a>錢 | {data = 3 | {<l>*left | <r>*right}}"]
tnode3[label = "<a>孫 | {data = 7 | {<l>*left | <r>*right}}"]
tnode4[label = "<a>李 | {data = 6 | {<l>*left | <r>*right}}"]
tnode5[label = "<a>周 | {data = 8 | {<l>*left | <r>*right}}"]
tnode6[label = "<a>吳 | {data = 4 | {<l>*left | <r>*right}}"]
t[shape = plaintext, label = "t"]
p[shape = plaintext, label = "p"]
p -> t
t -> tnode1:<a>
tnode1:<r> -> tnode3:<a>
tnode1:<l> -> tnode2:<a>
tnode3:<l> -> tnode4:<a>
tnode3:<r> -> tnode5:<a>
tnode2:<r> -> tnode6:<a>
}
```
假設我們一樣要刪除孫，第 10~21 行的圖示如下
```graphviz
digraph G {
rankdir = TB
node[shape = "record"]
tnode1[label = "<a>趙 | {data = 5 | {<l>*left | <r>*right}}"]
tnode2[label = "<a>錢 | {data = 3 | {<l>*left | <r>*right}}"]
tnode3[label = "<a>孫 | {data = 7 | {<l>*left | <r>*right}}"]
tnode4[label = "<a>李 | {data = 6 | {<l>*left | <r>*right}}"]
tnode5[label = "<a>周 | {data = 8 | {<l>*left | <r>*right}}"]
tnode6[label = "<a>吳 | {data = 4 | {<l>*left | <r>*right}}"]
p[shape = plaintext, label = "p"]
q[shape = plaintext, label = "q"]
r[shape = plaintext, label = "r"]
p -> tnode1:<r>
q -> tnode1:<r>
r -> tnode3:<r>
tnode1:<r> -> tnode3:<a>
tnode1:<l> -> tnode2:<a>
tnode3:<l> -> tnode4:<a>
tnode3:<r> -> tnode5:<a>
tnode2:<r> -> tnode6:<a>
}
```
第 22 行一樣是替身攻擊 `q->data = (*r)->data;`
```graphviz
digraph G {
rankdir = TB
node[shape = "record"]
tnode1[label = "<a>趙 | {data = 5 | {<l>*left | <r>*right}}"]
tnode2[label = "<a>錢 | {data = 3 | {<l>*left | <r>*right}}"]
tnode3[label = "<a>孫 | {data = 8 | {<l>*left | <r>*right}}"]
tnode4[label = "<a>李 | {data = 6 | {<l>*left | <r>*right}}"]
tnode5[label = "<a>周 | {data = 8 | {<l>*left | <r>*right}}"]
tnode6[label = "<a>吳 | {data = 4 | {<l>*left | <r>*right}}"]
p[shape = plaintext, label = "p"]
q[shape = plaintext, label = "q"]
r[shape = plaintext, label = "r"]
p -> tnode1:<r>
q -> tnode1:<r>
r -> tnode3:<r>
tnode1:<r> -> tnode3:<a>
tnode1:<l> -> tnode2:<a>
tnode3:<l> -> tnode4:<a>
tnode3:<r> -> tnode5:<a>
tnode2:<r> -> tnode6:<a>
}
```
## 測驗 9
考慮以下進行記憶體地址對齊 (alignment) 的巨集:
```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))
```
作用是向上對齊 (roundup)，請補完程式碼，使其行為符合預期。
* 當 `x = 1~16`，`ROUND_UP_TO_ALIGNMENT_SIZE(x)` 得到 16
* 當 `x = 16~32`，`ROUND_UP_TO_ALIGNMENT_SIZE(x)` 得到 32
而確認是否為 16 的倍數只需要看最後 4 個 bit 是否為 0，也就是 $a_0=a_1=a_2=a_3=0$，二進位轉十進位如下式
$...a_5a_4a_3a_2a_1a_0 = a_0\cdot2^0 + a_1\cdot2^1 + a_2\cdot2^2 + a_3\cdot2^3 + a_4\cdot2^4 + a_5\cdot2^5 + ...$
因此可推得 `~(NNN) = 11110000 = ~(16 - 1)`，其中 `NNN = MAX_ALIGNMENT - 1`
為推得 `MMM`，將 `x` 的臨界值代入，觀察
* `x = 1`，`x + 16 - MMM = 17 - MMM`
* `x = 16`，`x + 16 - MMM = 32 - MMM`
由上可知，當 `MMM = 1` 時，AND bitmask `~(NNN)` 可得 16
## 測驗 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)); \
})
```
注意: 當除數 (即 divisor) 為負值時，行為沒有定義。
參考執行結果:
* DIVIDE_ROUND_CLOSEST(7, 3) = 2
* DIVIDE_ROUND_CLOSEST(6, 3) = 2
* DIVIDE_ROUND_CLOSEST(5, 3) = 2
`RRR = (__x) + ((__d) >> 1)`
`SSS = (__x) - ((__d) >> 1)`
* `((typeof(x)) -1) > 0` 可用於檢查是否為無號數，因為 `-1 = 0xFFFFFFFF`，假設 `x` 為 `uint32_t`，那麼 `(uint32_t) -1` 等於 $2^{32}-1$
* `(((__x) > 0) == ((__d) > 0))` 用於檢查被除數與除數是否同時大於 0，或同時小於等於 0
因此，觸發 `(((__x) - ((__d) >> 1)) / (__d))` 的條件為，「除數與被除數皆為有號整數」且「除數與被除數其中一項為小於或等於 0」，表示要進到被除數為非正整數的除法
首先討論被除數 `x` 為正的情況，將被除數 `x` ，除數 `d` 表示成 $x = q \cdot d + r$，我們可以改寫為 $\dfrac{x}{d} = q + \dfrac{r}{d}$，其中整數部分為 $q$，小數部分為 $\dfrac{r}{d}$，當 $\dfrac{r}{d} > 0.5$ 時，我們要想辦法讓它加上某個數使其能進位，反之，當 $\dfrac{r}{d} < 0.5$ 時，加上的某個數不能使其進位，而這個數就是 $0.5$，例如 : $7/3 = 2.333 = 2 + 0.333$
* 當 $\dfrac{r}{d} > 0.5$ 時，$\dfrac{r}{d} + 0.5 > 1$
* 當 $\dfrac{r}{d} < 0.5$ 時，$\dfrac{r}{d} + 0.5 < 1$
接著討論負數情況，由 $-7/3 = -2.333 = -2 + (-0.333)$ 可看出，如果仍是加上 $0.5$，那麼值就會變成 $1$，因此是減去 $0.5$
利用 Matlab 畫圖，觀看直接相除 vs. 上述提到方法
```matlab
x = -10:1:10
y = 3
figure()
z = fix(x / y)
plot(x, z, 'LineWidth', 4)
for i = 1:length(x)
if x(i) > 0
z(i) = fix((x(i) + y / 2) / y)
else
z(i) = fix((x(i) - y / 2) / y)
end
end
hold on
plot(x, z, 'LineWidth', 4)
hold off
title('Divided by 3 (x / 3)')
xticks(x)
legend({'Non-fixed', 'Fixed'}, 'Location', 'northwest')
grid on
```
## 測驗 11
考慮以下計算整數開平方根的實作:
```c
/*
* fls - find last (most-significant) bit set
* @x: the word to search
* */
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;
}
```
假設 `word = 8` ，畫以下程式碼圖解，假設在 32 位元電腦上
```c
if (!(word & (~0ul << 16))) {
num -= 16;
word <<= 16;
}
```
可以看見 `(~0ul << 16)` 是 mask，因為 `~0ul` 是 `0xFFFFFFFF` ， 而 `word & (~0ul << 16)` 為 `false` 表示 `first set` 不在前半部，並將 `num` 減去 `16`，同時 `word` 左移 `16`，下一個 mask 為 `(~0ul << (32 - 8))`
```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 != 0) {
b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
```
`m` 是用於描述 `x` 需要幾位數來表示，假設 `x = 80 = ...0101 0000`，`fls(x)=6`，`(fls(x) & ~1UL)` 得 `6`，`1UL << (fls(x) & ~1UL)` 為 `64 = ...0100 0000`
## 參考資料
* [[Linux Kernel慢慢學]探討Designated Initializers](https://meetonfriday.com/posts/39485259/)
* [bit-field](https://hackmd.io/@unknowntpo/B1WzhkvKL/%2F%40sysprog%2Fc-bitfield%3Ftype%3Dview)
* [Linux Kernel's __is_constexpr Macro](https://stackoverflow.com/questions/49481217/linux-kernels-is-constexpr-macro)
Sign in with Wallet
Connect another wallet