---
tags: linux2022, quiz
---

# 2022q1 Homework3 (quiz3)

contributed by < `freshLiver` >

## 第一題 - `GENMASK` (LEFT, RIGHT)

// 產生一個第 `l` 到第 `h` 個位元皆為 1、而其他位元則為 0 的數值
#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

這段程式碼是利用對 `~0UL`（64 個 1）進行位移來將重疊部份（第 `l` 到 `h` 位元）以外的部份皆設為 0，而需要設為 0 的區段有：

- 前 `63 - h` 個位元：因此 ==LEFT== 應為 `(63 - h)`。
- 後 `l` 個位元：由於已經先右移 `l` 位元了，所以要再左移 `l` 位元才能使最低 `l` 位元皆為 0，因此 ==RIGHT== 應為 `l`。

### 比較 Linux 核心 `GENMASK` 巨集的實作，闡述其額外的考量

#### 先備知識

在看 Linux 核心中 `GENMASK` 的實作之前，要先來了解相關巨集以及 [GNU C Extensions](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 的用途以及原理：

##### 巨集 - `UL`

// include/uapi/linux/const.h
#define __AC(X,Y)      (X##Y)
#define _AC(X,Y)       __AC(X,Y)
#define _UL(x)         (_AC(x, UL))

// include/vdso/const.h
#define UL(x)          (_UL(x))

`UL` 是一個定義在 [include/vdso/const.h](https://github.com/torvalds/linux/blob/master/include/vdso/const.h) 中的巨集，展開後會變成 `(((x##Y)))`，而其中的 `##` [token concatenation](https://gcc.gnu.org/onlinedocs/cpp/Concatenation.html#Concatenation)，可以在前處理階段時將 `x`、`y` 兩個 token 合併，因此這個巨集展該後相當於在 `x` 後加上一個 `UL` 後綴。

接著根據 [n1570 的 6.4.4.1 Integer constants](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf#%5B%7B%22num%22%3A162%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C-27%2C816%2Cnull%5D) 可以知道 `U` 以及 `L` 分別代表了 **unsigned-suffix** 以及 **long-suffix**。而在 6.4.4.1 的第 2 項則說明了這個後綴是用來指定一整數常數的型別：

> 2. An integer constant begins with a digit, but has no period or exponent part. It may have a prefix that specifies its base and a **suffix that specifies its type**.

因此可以知道這個巨集是用來表示整數常數 `x` 為 64 位元無號整數（[LP64](https://en.wikipedia.org/wiki/64-bit_computing#64-bit_data_models)）。

##### 巨集 - `BUILD_BUG_ON_ZERO`

// include/linux/build_bug.h
#ifdef __CHECKER__
#define BUILD_BUG_ON_ZERO(e) (0)
#else 
#define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
#endif

:::warning
TODO : `__CHECKER__` 在哪被定義
:::

這是一個定義在 [include/linux/build_bug.h](https://github.com/torvalds/linux/blob/master/include/linux/build_bug.h) 的巨集，可以看到當 `__CHECKER__` 有被定義時，這個巨集會展開成：

((int)(sizeof(struct { int:(-!!(e)); })))

這邊使用了 Bit-Fields 的技巧，

> 4. The expression that specifies the width of a bit-field shall be an integer constant expression with a **nonnegative value** that does not exceed the width of an object of the type that would be specified were the colon and expression omitted. $^{122)}$ If the value is zero, the declaration shall have no declarator.

而根據 [6.5.3.3 Unary arithmetic operators](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf#%5B%7B%22num%22%3A219%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C-27%2C816%2Cnull%5D) 的第 5 項中則有明確規範一元運算子 `!` 的結果只會是 `0` 或 `1`：

> 5. The result of the logical negation operator ! is 0 if the value of its operand compares unequal to 0, **1 if the value of its operand compares equal to 0**. The result has type int. The expression !E is equivalent to (0==E).

因此當 `e` 為非 0 時，這個 bit-field 的 width 會是 `-1`，但由於 bit-field 的 width 必須為非負整數，所以會產生錯誤造成編譯失敗；相對的，當 `__CHECKER__` 沒定義或是 `e` 為 0 時則不會出現錯誤，而是會展開成常數 0 或是一個回傳 0 的表示式。

:::success
在 [bit-field](https://hackmd.io/@sysprog/c-bitfield?type=view) 一文中則有更詳細的說明。
:::

##### Extension - `__builtin_choose_expr(const_exp, expr1, expr2)`

`__builtin_choose_expr` 是 [GCC 的內建函式](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)，根據文件中對這個函式的說明：

> You can use the built-in function \__builtin_choose_expr to evaluate code depending on the value of a constant expression. This built-in function returns exp1 if const_exp, which is an integer constant expression, is nonzero. Otherwise it returns exp2.
>
> This built-in function is analogous to the ‘? :’ operator in C, except that the expression returned has its type unaltered by promotion rules. Also, the built-in function does not evaluate the expression that is not chosen. For example, if const_exp evaluates to true, exp2 is not evaluated even if it has side effects.
>
> This built-in function can return an lvalue if the chosen argument is an lvalue.
>
> If exp1 is returned, the return type is the same as exp1’s type. Similarly, if exp2 is returned, its return type is the same as exp2.

可以知道，這個內建函式跟三元運算子 `?:;` 相似，都是根據條件是否成立來決定要進行的操作，但 `__builtin_choose_expr` 這個函式要求條件 `const_expr` 必須為常數，否則會造成編譯失敗。

:::warning
TODO : 與 `?:;` 的用途、優缺點比較
:::

##### 巨集 - `__is_constexpr`

#define __is_constexpr(x) \
	(sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))

這個巨集被定義在 [include/linux/const.h](https://github.com/torvalds/linux/blob/master/include/linux/const.h) 中，可以用來檢查 `x` 是否能夠在**編譯時期**被視為常數。

:::warning
TODO : 原理
:::

若是 `x` 能夠在編譯階段被視為常數的話，這個巨集就會回傳 `1`，否則則會回傳 0。

#### GENMASK 實作

在 [include/linux/bits.h](https://github.com/torvalds/linux/blob/master/include/linux/bits.h) 中有定義 `GENMASK` 相關的巨集：

// include/linux/bits.h
#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` 又會根據 `__ASSEMBLY__` 的定義與否展開成不同的內容：

#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

可以看到若是 `__ASSEMBLY__` 有被定義的話，就會展開成

#define GENMASK_INPUT_CHECK(h, l) \
	(BUILD_BUG_ON_ZERO(__builtin_choose_expr( \
		__is_constexpr((l) > (h)), (l) > (h), 0)))

而從前面的說明可以知道這段可以應該 2 種情況討論：

- 若 `(l) > (h)` 能夠在編譯時期被確認是成立：
1. `__is_constexpr` 在編譯時期被相當於 1
2. `__builtin_choose_expr` 會選擇 `(l) > (h)` 的表示式
3. 由於 `(l) > (h)` 成立，所以 `BUILD_BUG_ON_ZERO` 會產生錯誤、造成編譯失敗
- 若 `(l) > (h)` 在編譯時期被確認是**不成立**，或**無法確認是否成立**：
1. `__is_constexpr` 在編譯時期被相當於 0
2. `__builtin_choose_expr` 會選擇 `0` 的表示式
3. 由於 `0` 代表不成立，所以 `BUILD_BUG_ON_ZERO` 不會產生錯誤

因此可以知道這段複雜的巨集用意是在避免使用**常數**作為 `GENMASK` 巨集的參數時誤將傳入數值比 `h` 大的 `l`。

:::warning
在 GCC 內建函式中有類似的函式 [`__builtin_constant_p(exp)`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 能夠作到與 `__is_constexpr` 相似的檢查，而原先的 `GENMASK` 巨集也是依賴這個內建函式進行檢查，但在 [2018 年 3 月時被反應](https://lore.kernel.org/lkml/[e-mail]/) `__builtin_constant_p` 在編譯時可能無法在正確的時間點檢查 `exp`，因此會造成 `__builtin_choose_expr` 的 `const_expr` 部份被認為是非常數而導致編譯失敗。直到在 [2021 年 3 月時才改用 `__is_constexpr`](https://github.com/torvalds/linux/commit/f747e6667ebb2ffb8133486c9cd19800d72b0d98) 來取代 `__builtin_constant_p` 進行判斷。
:::

而在檢查完 `h`、`l` 之後（或因 `__ASSEMBLY__` 未定義而不進行檢查），就會接著產生 mask 的部份：

#define __GENMASK(H, L) \
	(((~UL(0)) - (UL(1) << (L)) + 1) & \
	 (~UL(0) >> (BITS_PER_LONG - 1 - (H))))

:::info
因為 `1` 與 `l` 的字型非常相似，所以為了愛護眼睛，我將巨集的 `h` 以及 `l` 改用大寫字母 `H` 以及 `L` 替代。
:::

可以看到這個巨集一樣是對 64 位元的無號整數 0 取一補數來產生 64 個 1 進行位移，而這邊將這個巨集分成兩部份討論：

- `((~UL(0)) - (UL(1) << (L)) + 1)` 的部份：
- `(~UL(0))`：產生 64 個 1
- `- (UL(1) << (L))`：將第 `L` 個位元值設成 0
- `+ 1`：使用 `+ 1` **進位的特性**，將最低位的 0（也就是第 `L` 個位元）設成 1，而其它更低的位元（即第 `0` 至 `L-1` 位元）則會因進位被設成 0
- 到這邊可以產生==第 `L-1` ~ 0 位元皆為 0 的 mask==
- `(~UL(0) >> (BITS_PER_LONG - 1 - (H)))` 的部份：
- `(~UL(0)`：產生 64 個 1
- `(BITS_PER_LONG - 1 - (H))`：由於位元的編號是從 0 開始，所以最高位應為 63（即 `BITS_PER_LONG - 1`），而 `- (H)` 則是找出應要右移的位數
- `>> (BITS_PER_LONG - 1 - (H))`：右移讓最高的 `63 - (H)` 個位元為 0
- 到這邊可以產生==第 `63` ~ `H+1` 位元皆為 0 的 mask==

最後再將兩個 mask 進行 AND 運算即可產生第 `H` ~ `L` 位元皆為 1 的 mask。

### Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例

---

## 第二題 - `ALIGN_DOWN` (EXP1)

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};
}

這段程式碼是要將一地址 `v` 看作是結構體 `foo` 的起始位置，若地址 `v` 沒有以 4 位元組進行對齊的話，則需要將地址向下對齊，因此 EXP1 要先捨去地址的後 2 個位元，然後再轉型成結構體 `foo` 的指標，即 ==EXP1== 應為 `(struct foo *)(v & ~3)`。

### 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說

在[第九題的延伸問題](#%E6%89%BE%E5%87%BA%E4%B8%A6%E8%AA%AA%E6%98%8E-Linux-%E6%A0%B8%E5%BF%83%E4%B8%AD-round-upround-down-%E7%9A%84%E6%87%89%E7%94%A8%E5%A0%B4%E5%90%88)中一併討論。

---

## 第三題 - [LeetCode 190. Reverse Bits](https://leetcode.com/problems/reverse-bits/) (EXP2, EXP3)

#include <stdint.h>
uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);        // 以 4 位元為單位，兩段互換
    x = ((x & 0xCC) >> 2) | (EXP2); // 以 2 位元為單位，0,1 2,3 段兩兩互換
    x = ((x & 0xAA) >> 1) | (EXP3); // 以 1 位元為單位，0,1 2,3 4,5 6,7 段兩兩互換
    return x;
}

將 $n$ 個位元以不同單位大小分割成偶數段，每次將奇數部份以及偶數部份透過位移以及 bitwise-or 互換，而因為 `0xCC` 與 `0xAA` 分別代表 `0b11001100` 與 `0x10101010`，即分別為單位大小為 2 位元及 1 位元的偶數段部份，所以 EXP2 與 EXP3 應為對應單位大小的奇數段部份。因此 ==EXP2== 應為 `0x33` (`0b00110011`)，而 ==EXP3== 則應為 `0x55` (`0b01010101`)

### 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

在 [include/linux/bitrev.h](https://github.com/torvalds/linux/blob/master/include/linux/bitrev.h) 中包含了 1, 2, 4 位元組反轉的巨集實作，可以看到大致上分成 3 種實作方式：

1. bitwise 反轉（常數）

當要反轉的值屬於常數時，則會直接使用與測驗題相似的方式，應該是為了讓編譯器能夠將常數運算直接最佳化掉。

2. 查表（非常數且無硬體指令）

在 [lib/bitrev.c](https://github.com/torvalds/linux/blob/master/lib/bitrev.c) 中有透過陣列 `byte_rev_table` 列舉了 8 位元對應的反轉結果，因此當 `CONFIG_HAVE_ARCH_BITREVERSE` 沒有被定義時，可以不用以 4, 2, 1 位元作為單位大小進行反轉，直接透過查表找到該位元組對應的反轉結果即可。

3. 反轉指令（非常數但有硬體指令）

在某些架構的指令集中可能有能夠反轉位元的指令，像是 [ARM 的 `RBIT` 指令](https://developer.arm.com/documentation/dui0489/h/arm-and-thumb-instructions/rev--rev16--revsh--and-rbit) 就能夠直接反轉一個 32 位元的資料。因此在 `CONFIG_HAVE_ARCH_BITREVERSE` 有被定義時就能夠直接使用指令進行更有效率的反轉操作。

---

## 第四題 - foreach (EXP4, EXP5)

#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__})))

兩個 `for each` 巨集的實作概念都差不多，使用了 [Variadic Macro](https://gcc.gnu.org/onlinedocs/cpp/Variadic-Macros.html) 進行陣列宣告，並透過 `for` 迴圈以及 `,` 運算子：

> 在規格書中的 [6.5.17 Comma operator](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf#%5B%7B%22num%22%3A270%2C%22gen%22%3A0%7D%2C%7B%22name%22%3A%22XYZ%22%7D%2C0%2C792%2C0%5D) 中關於 `,` 這個運算子的說明：
> 1. Syntax :
> ```
> expression:
> assignment-expression
> expression , assignment-expression
> ```
> 2. The left operand of a comma operator is evaluated as a void expression; there is a sequence point between its evaluation and that of the right operand. Then the right operand is evaluated; the result has its type and value.
> 3. **EXAMPLE** As indicated by the syntax, the comma operator (as described in this subclause) cannot appear in contexts where a comma is used to separate items in a list (such as arguments to functions or lists of initializers). On the other hand, it can be used within a parenthesized expression or within the second expression of a conditional operator in such contexts. In the function call `f(a, (t=3, t+2), c)` the function has three arguments, the second of which has the value 5.

因此在 `for` 迴圈的初始化部份會先執行 `,` 左側，也就是先將陣列的第一個元素賦值給變數 `i`，最後才會將 `,` 右側的 `0`，也就是陣列的初始 index 賦值給 `_foreach_i`。

除了初始化用來儲存陣列的變數 `i` 以及陣列 index 的變數 `_foreach_i` 之外，每次迴圈結束還需要增加 `_foreach_i` 並將 `i` 移動到下一個元素，因此 `_foreach_i` 可以直接透過 `++_foreach_i` 或 `_foreach_i++` 增加，但 `i` 由於並不是指標，所以必須重新初始化陣列，並將下一個元素透過 `_foreach_i` 賦值給 `i`，因此 ==EXP4== 與 ==EXP5== 皆應為 `++_foreach_i` 才能在每次迭代結束時將正確的元素重新賦值給 `i`。

### 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

透過 `$ grep -rP --include="*.[ch]" "\\[\\].*__VA_ARGS__.*"` 尋找相關用法大多是用來初始化陣列或是檢查巨集參數的數量，其中與這題比較相近的是：

// drivers/gpu/drm/i915/i915_reg.h
/*
 * Given the arbitrary numbers in varargs, pick the 0-based __index'th number.
 *
 * Always prefer _PICK_EVEN() over this if the numbers are evenly spaced.
 */
#define _PICK(__index, ...) (((const u32 []){ __VA_ARGS__ })[__index])

除了透過單純宣告成一個陣列之外，還能透過指定 index 來取得目標參數。

---

## 第五題 - [LeetCode 29. Divide Two Integers](https://leetcode.com/problems/divide-two-integers/)

#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;
}

### 指出可改進部份並實作

無乘法、無迴圈以外的 branch

int divide(int dividend, int divisor)
{
    uint32_t sign = 0;

    int dvd_mask = dividend >> 31;
    sign ^= dvd_mask & 0xFFFFFFFF;
    // explicitly cast to unsigned to avoid overflow
    uint32_t dvd = (uint32_t) (dividend ^ dvd_mask) - dvd_mask;

    int dvs_mask = divisor >> 31;
    sign ^= dvs_mask & 0xFFFFFFFF;
    // explicitly cast to unsigned to avoid overflow
    uint32_t dvs = (uint32_t) (divisor ^ dvs_mask) - dvs_mask;

    uint8_t shift = 0;
    while (dvd > (dvs << shift))
        ++shift;

    uint32_t res = 0;
    while (dvd >= dvs) {
        while (dvd < (dvs << shift))
            --shift;
        // 1 should be unsigned to avoid overflow (1 << 31)
        res |= 1U << shift;
        dvd -= dvs << shift;
    }

    res |= -!!(res > 0x7FFFFFFFU && !sign) & 0x7FFFFFFFU;
    // explicitly cast to unsigned to avoid overflow
    res ^= (uint32_t)(res > 0x7FFFFFFFU && !sign) << 31;
    return (res ^ sign) - sign;
}

### 找出並討論 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼

---

## 第六題 - [LeetCode 149. Max Points on a Line](https://leetcode.com/problems/max-points-on-a-line/)

#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;
}

### 指出可改進部份並實作

### 擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行

---

## 第七題 - `ilog32`

/**
 * @brief 對於一 32 位元無號整數 @v 最少需要幾位元才能儲存
 *
 * 儲存最少需要的位元數 = 最高位元 1 的位置 (32-clz)
 * 因此可以可以透過 BITMASK 將資料分成高位元以及低位元兩部份，並檢查最高位元的 1
 * 在哪部份：
 * - 若是不在高位元部份就縮小範圍再檢查一次。
 * - 若是在高位元部份的話就紀錄並移除低位元部份，然後縮小範圍再重新檢查一次。
 */
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;
}

以二元搜尋的概念找出最高位元的 1 的位置，從中間開始，每次都將檢查範圍縮小一半，當最高位 1 位於高位元部份時，則可以右移掉低位元部份，讓兩種狀況能以相同的形式繼續進行檢查。若是以這個邏輯實作的話，只要重複三行程式碼：

    // 檢查最高位 1 是否在 16 - 31 位元
    int m = (v > 0xFFFFU) << 4;
    v >>= m;  // 若是的話 m 會變成 16，否則為 0 (代表能夠捨棄的位元數)
    ret |= m;  // 相當於 ret += m，即用來紀錄最高位 1 的位置


    // 檢查最高位 1 是否在 或 8 - 31 位元
    m = (v > 0xFFU) << 3;
    v >>= m;  // 若是的話 m 為 8，否則為 0 (代表能夠捨棄的位元數)
    ret |= m;

    // 檢查最高位 1 是否在 或 4 - 31 位元
    m = (v > 0xFU) << 2;
    v >>= m;  // 若是的話 m 為 4，否則為 0 (代表能夠捨棄的位元數)
    ret |= m;

    // 檢查最高位 1 是否在 或 2 - 31 位元
    m = (v > 0x3U) << 1; /* EXP10 */
    v >>= m;  // 若是的話 m 為 2，否則為 0 (代表能夠捨棄的位元數)
    ret |= m;

    // 檢查最高位 1 是否在 或 1 - 31 位元
    m = (v > 0x1U) << 0;
    v >>= m;  // 若是的話 m 為 1，否則為 0 (代表能夠捨棄的位元數)
    ret |= m;

可以簡單的知道 ==EXP10== 應為 `(v > 0x3U) << 1`，即用來檢查最高位元 1 是否在第 2 至 31 位元。

但這樣會因為每次都分成兩長度不為 0 的部份，所以最多只能檢查 31 個位元，造成當 `v == 1` 時會產生錯誤結果，因此最後還需要檢查 `v` 是否在第 0 個位元，即 `v` 是否為 0：

    ret += (v > 0);

這邊要注意的是，由於前面都是透過 `|` 設定 `ret` 的第 0 至第 5 位元來紀錄所需位元數，因此最後需要改用 `+`，才不會在某些情況（第 23 行條件成立時）產生錯誤結果。

在了解檢查機制之後，需要注意到在原程式碼的一開始宣告 `int ret = v > 0;` 時就已經先檢查 `v > 0` 的情況了，所以需要改用 `+` 的是第 23 至 25 行的部份：

    // 檢查最高位 1 是否在 或 1 - 31 位元
    m = (v > 0x1U) << 0;
    v >>= m;  // 若是的話 m 為 1，否則為 0 (代表能夠捨棄的位元數)
    ret += m;

而這邊又可以在進行簡化（左移 `0` 可以忽略、`v` 不須再右移、`m` 與 `ret` 的操作可以合併）：

    ret += (v > 0x1);

應此 ==EXP11== 最精簡的表示法應為 `ret += v > 1`。

### 在 Linux 核心原始程式碼找出類似實作並解說其應用場景

[quiz4 的 ilog2 說明](https://hackmd.io/@freshLiver/linux2022q1-hw4-quiz#ilog2-巨集)。

### 缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 ilog

研讀論文[《Using de Bruijn Sequences to Index a 1 in a Computer Word》](http://supertech.csail.mit.edu/papers/debruijn.pdf)

### 實作編譯時期 (compile-time) 的 ilog2 實作

運用〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉和〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉提及的技巧

---

## 第八題 - 二元搜尋樹 (C++)

typedef struct tnode *tree;                   
struct tnode {
    int data;   
    tnode *left;
    tnode *right;
    tnode(int d)
    {       
        data = d;
        left = right = 0;
    }           
};

// native.cpp
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;
    }
}

使用 indirect pointer 改寫簡化：

// improve.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;
}

### 以更精簡、高效且符合 C99 標準進行實作探討效率的提升

### 探討針對記憶體佈局 (memory layout) 的改進策略

研讀 [Static B-Trees](https://en.algorithmica.org/hpc/data-structures/s-tree/)

---

## 第九題 - ALIGN_UP

/* 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))

與實作四捨五入的概念（加上 `0.5` 再捨去小數點部份）有點相似，直接對地址加上對齊大小（這段程式碼為 16 位元組對齊），接著再捨去地址的最低 4 位元，因此 `~(NNN)` 應為除最低 4 位元皆為 1 的數，即 ==NNN== 應為 `MAX_ALIGNMENT - 1` (15)。

但是直接加上對齊大小會讓已對齊的地址也被向上對齊，因此要先讓原地址 `x` 減 1 才能確保已對齊的地址向上對齊後保持不變，所以 ==MMM== 應為 1。

### 撰寫出對應 ROUND_DOWN 巨集

#define MAX_ALIGNMENT 16
#define ROUND_DOWN_TO_ALIGNMENT_SIZE(x) ((x) & ~(MAX_ALIGNMENT - 1))

跟第二題的概念相同，直接捨棄地址最後的 $log_2(MAX\_ALIGNMENT)-1$ 個位元。

### 找出並說明 Linux 核心中 round-up/round-down 的應用場合

md raid metadata

// driver/md/raid1.h
/*
 * each barrier unit size is 64MB fow now
 * note: it must be larger than RESYNC_DEPTH
 */
#define BARRIER_UNIT_SECTOR_BITS	17
#define BARRIER_UNIT_SECTOR_SIZE	(1<<17)

// driver/md/raid1.c
static sector_t align_to_barrier_unit_end(sector_t start_sector,
					  sector_t sectors)
{
	sector_t len;

	WARN_ON(sectors == 0);
	/*
	 * len is the number of sectors from start_sector to end of the
	 * barrier unit which start_sector belongs to.
	 */
	len = round_up(start_sector + 1, BARRIER_UNIT_SECTOR_SIZE) -
	      start_sector;

	if (len > sectors)
		len = sectors;

	return len;
}

---

## 第十題 - DIVIDE_ROUND_CLOSEST

#define DIVIDE_ROUND_CLOSEST(x, divisor)                          \
    ({                                                            \
        /* evaluate once */;                                      \
        typeof(x) __x = x;                                        \
        typeof(divisor) __d = divisor;                            \
        /* check unsigned or not */;                              \
        (((typeof(x)) -1) > 0 || ((typeof(divisor)) -1) > 0 ||    \
         (((__x) > 0) == ((__d) > 0)))                            \
            ? ((7777 /* RRR */) / (__d))                          \
            : ((8888 /* SSS */) / (__d));                         \
    })

/**
 * True : SSS 皆可以用 "被除數 + 0.5 * 除數" 表示
 *  - TTT 兩數皆為無號
 *      1. 皆為正數 : SSS = 被除數 + 0.5 * 除數
 *      2. 皆非 0 : divide by zero，不處理
 *
 *  - FTT 被除數為有號，除數為無號
 *      1. 皆為正數 : SSS = 被除數 + 0.5 * 除數
 *      2. 除數必為 0 : divide by zero，不處理
 *
 *  - TFT 被除數為無號，除數為有號
 *      1. 皆為正數 : SSS = 被除數 + 0.5 * 除數
 *      2. 被除數為 0，除數為負數 : 0 >= SSS > 除數
 *      3. 被除數為 0，除數為 0 : divide by zero，不處理
 *
 *  - FFT 兩數皆為有號數
 *      1. 皆為正數 : SSS = 被除數 + 0.5 * 除數
 *      2. 皆為負數 : SSS = 被除數 - 0.5 * |除數|
 *      3. 被除數為 0，除數為負數 : 0 >= SSS > 除數
 *      4. 被除數為負數，除數為 0 : divide by zero，不處理
 *      5. 被除數為 0，除數為 0 : divide by zero，不處理
 *
 *  - FTF 被除數為無號，除數為有號，恰一數為非正數
 *      1. 被除數為 0，除數為正 : -除數 < SSS < 除數
 *      2. 被除數為正，除數為負 : SSS = 被除數 + 0.5 * |除數|
 *      3. 被除數為正，除數為 0 : divide by zero，不處理
 *
 *  - TFF 被除數為有號，除數為無號，恰一數為非正數
 *      1. 被除數為 0，除數為正 : -除數 < SSS < 除數
 *      1. 被除數為負，除數為正 : 
 *      1. 被除數為正，除數為 0 : divide by zero，不處理
 *
 *  - TTF 兩數皆為無號數，但恰有一數為非正數 (0)
 *      1. 被除數為 0，除數為正數 : -除數 < SSS < 除數
 *      2. 被除數為正數，除數為 0 : divide by zero，不處理
 *
 * 
 * False : RRR 皆可以用 "被除數 - 0.5 * 除數" 表示
 *  - FFF 兩數皆為有號型別，且恰有一數為非正數 :
 *      1. 被除數為正，除數為負 : RRR = 被除數 + 0.5 * |除數|
 *      2. 被除數為負，除數為正 : RRR = 被除數 - 0.5 * 除數
 *      3. 被除數為 0，除數為正 : -除數 < RRR < 除數
 *      4. 被除數為正，除數為 0 : divide by zero，不處理
 *
 */

### 找出並說明 Linux 核心中 div round-up/closest 的實作與使用情景

在 `insmod` 時，會使用到定義在 `include/linux/module_decompress.c` 中的 [`module_decompress`](https://hackmd.io/rJ7YiwC_TSa6C5l2i-p0kg?both#%E5%82%B3%E9%81%9E%E6%A0%B8%E5%BF%83%E6%A8%A1%E7%B5%84%E5%8F%83%E6%95%B8)，而其中又會使用到 `DIV_ROUND_UP` 來確保核心模組解壓縮後仍有足夠空間能儲存資訊。

## 第十一題 - Integer Square Root

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;
} 

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;
        XXX;

        if (x >= b) {
            YYY;
            y += m;
        }
        ZZZ;
    }

    return y;
}

### 嘗試利用硬體的 clz/ctz 指令改寫

### 在 Linux 核心找出類似的巨集和程式碼，說明其應用場景