---
# System prepended metadata

title: 2022q1 Homework3 (quiz3)
tags: [linux2022]

---

# 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`

![](https://i.imgur.com/ZBRaiby.jpg)

[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
```
![](https://i.imgur.com/vi4c21k.jpg)

## 測驗 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;
}
```

![](https://i.imgur.com/8i49Sa2.png)

可以看見 `(~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)