2022q1 Homework3 (quiz3)

contributed by < Risheng1128 >

作業說明
測驗題目

測驗 1

延伸問題:

• 解釋上述程式碼運作原理
• 比較 Linux 核心 GENMASK 巨集的實作，闡述其額外的考量
• 舉出 Linux 核心原始程式碼中二處 GENMASK 巨集和 include/linux/bitfield.h 的應用案例

程式碼運作原理

討論以下的程式碼，目的為產生一組從 l bit 到 h bit 為 1 的 mask

#define GENMASK(h, l) \
    (((~0UL) >> (LEFT)) & ((~0UL) >> (l) << (RIGHT)))

這邊題目考慮 64 位元的系統，最直觀的方式就是將 0xFFFFFFFFFFFFFFFFUL 分別右移和左移後進行 AND 運算，即可得到 mask ，以下採用題目 8 位元的範例作簡單解釋

GENMASK(6,4) = 0b01110000
     0b01111111 
   & 0b11110000
   ------------
     0b01110000

從以上範例可以推論出右移的部份為 7 - 6 = 1 , 左移的部份為 4 ，把結果套成 64 位元的系統，可以得到解答

LEFT = 63 - h
RIGHT = l
不過這邊有個問題沒有釐清，還不確定為什麼題目要 >> l

Linux 核心 GENMASK

在 github 中搜尋 GENMASK 後發現有兩處定義，分別位於 include/linux/bits.h 和 tools/power/x86/intel-speed-select/isst.h

分析 include/linux/bits.h

以下為 GENMASK 實作原始碼

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

#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 由兩個不同的巨集函式 GENMASK_INPUT_CHECK 及 __GENMASK 所組成，首先討論 GENMASK_INPUT_CHECK 的部份，由先前的 commit 可以得知 GENMASK_INPUT_CHECK 的功能是為了保持輸入參數的正確性，也就是確保 first argument 為 high bit 且 second argument 為 low bit ，同時如果在編譯時期就得知兩個 arguments 的數值，則 high bit 要大於 low bit

GENMASK() and GENMASK_ULL() are supposed to be called with the high bit as the first argument and the low bit as the second argument. Mixing them will return a mask with zero bits set.

To prevent such mistakes from appearing again, add compile time sanity checking to the arguments of GENMASK() and GENMASK_ULL(). If both arguments are known at compile time, and the low bit is higher than the high bit, break the build to detect the mistake immediately.

由上述的原始碼可以清楚得知 GENMASK_INPUT_CHECK 有兩種實作，由巨集 __ASSEMBLY__ 決定要使用哪一種 (line 6) ，根據 include/uapi/linux/const.h 裡面的註解及原始碼可以清楚得知巨集 __ASSEMBLY__ 是用來區分常數巨集在 assembler 和 C code 的實作

/* Some constant macros are used in both assembler and
 * C code.  Therefore we cannot annotate them always with
 * 'UL' and other type specifiers unilaterally.  We
 * use the following macros to deal with this.
 *
 * Similarly, _AT() will cast an expression with a type in C, but
 * leave it unchanged in asm.
 */

#ifdef __ASSEMBLY__
#define _AC(X,Y)	X
#define _AT(T,X)	X
#else
#define __AC(X,Y)	(X##Y)
#define _AC(X,Y)	__AC(X,Y)
#define _AT(T,X)	((T)(X))
#endif

因此我們可以得知 GENMASK_INPUT_CHECK 會根據使用在 assembler 或是 C code 有不同的實作

• 使用在 assembler 時， GENMASK_INPUT_CHECK 為 0
• 使用在 C code 時， GENMASK_INPUT_CHECK 為 (BUILD_BUG_ON_ZERO(__builtin_choose_expr(__is_constexpr((l) > (h)), (l) > (h), 0)))

接著可以討論在 C code 的情況，從巨集 BUILD_BUG_ON_ZERO 開始，從 include/linux/build_bug.h 可以找到原始碼

#ifdef __CHECKER__
#define BUILD_BUG_ON_ZERO(e) (0)
#else /* __CHECKER__ */
/*
 * Force a compilation error if condition is true, but also produce a
 * result (of value 0 and type int), so the expression can be used
 * e.g. in a structure initializer (or where-ever else comma expressions
 * aren't permitted).
 */
#define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); })))
#endif /* __CHECKER__ */

參考 sparse type checking ，可以清楚知道巨集 __CHECKER__ 是要判斷程式的語義 (semantics) ，接著分析 BUILD_BUG_ON_ZERO(e) ，從上述註解可以得知當 BUILD_BUG_ON_ZERO(e) 的條件 e 為 true 時，會報出編譯器錯誤

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

接著參考 bit-field 得到上述原始碼的詳細分析，首先分析 (-!!(e))

• !!(e)： 對 e 做兩次 NOT ，確保結果一定是 0 或 1
• -!!(e)： 對 !!(e) 乘上 -1 ，因此結果會是 0 或 -1

可以得到 -!!(e) 的結果一定是 0 或 -1 ，即當 e 不合法時 -!!(e) 為 -1 ，反之 e 合法時 -!!(e) 為 0 ，搭配上前面的 struct { int: 可以得到以下結論

• 當 e 為合法時，宣告一個 structure 中有一個 int ，其中有 0 bit 的 bit-field
• 當 e 為不合法時，宣告一個 structure 中有一個 int ，其中有 -1 bit 的 bit-field

參考 C99 標準，可以得知 bit-field 的 width 不能為負數，因此會產生編譯器錯誤，且沒有變數名稱的 bit-field (稱為 unnamed bit-field) 其 width 可以為 0 ，且不會使用到任何空間

6.7.2.1

• 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. If the value is zero, the declaration shall have no declarator.

• A bit-field declaration with no declarator, but only a colon and a width, indicates an unnamed bit-field. As a special case, a bit-field structure member with a width of 0 indicates that no further bit-field is to be packed into the unit in which the previous bit-field, if any, was placed.

• 108. An unnamed bit-field structure member is useful for padding to conform to externally imposed layouts.

接著分析 __builtin_choose_expr ， __builtin_choose_expr 為 GNU extension ，可以參考 Other Built-in Functions Provided by GCC ，以下為 prototype 以及說明

type __builtin_choose_expr (const_exp, exp1, exp2)

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.

從以上的說明可以得知 __builtin_choose_expr 的目的是用來判斷 const_exp 是否為非 0 的 constant expression ，如果是則回傳 exp1 ，不是則回傳 exp2 ，至於什麼是 constant expression ? 可以參考 C99 標準，如下所示

6.6.6
A constant expression can be evaluated during translation rather than runtime, and accordingly may be used in any place that a constant may be.

最後分析巨集函式 __is_constexpr() ，可以在 include/linux/const.h 中找到，以下為原始碼

/*
 * This returns a constant expression while determining if an argument is
 * a constant expression, most importantly without evaluating the argument.
 * Glory to Martin Uecker <[e-mail]>
 */
#define __is_constexpr(x) \
	(sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8)))

首先根據以前的 commit 可以得知使用 __is_constexpr(x) 的原因

However, it turns out that __builtin_constant_p() does not always return a compile time constant [0]. It was thought this problem was fixed with gcc 4.9 [1], but apparently this is not the case [2].

Switch to use __is_constexpr() instead which always returns a compile time constant, regardless of its inputs.

可以得知原本使用 __builtin_constant_p() ，由於其不總是回傳 compile time constant ，才會換成巨集函式 __is_constexpr()

接著可以開始分析 __is_constexpr() 的實作，這邊參考 Linux Kernel's __is_constexpr Macro 的解說

考慮 ((void *)((long)(x) * 0l)) ，首先 (long)(x) 是為了避免 x 可能為指標型態的情況，接著參考以下 C99 規格，定義了 integer constant expression 以及 null pointer constant ，並考慮兩種情況

6.3.2.3 Pointers

An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant.

6.6 Constant expressions

An integer constant expression shall have integer type and shall only have operands that are integer constants, enumeration constants, character constants, sizeof expressions whose results are integer constants, and floating constants that are the immediate operands of casts. Cast operators in an integer constant expression shall only convert arithmetic types to integer types, except as part of an operand to the sizeof operator.

• 如果 x 是 integer constant expression ，根據上述 C99 規格 6.3.2.3 小節，可以得知 ((long)(x) * 0l) 為值為 0 的 integer constant expression ，且 (void *)((long)(x) * 0l) 為 null pointer constant
• 如果 x 不是 integer constant expression ，則 (void *)((long)(x) * 0l) 就不是 null pointer constant

得知了這樣的差異，可以繼續考慮 8 ? ((void *)((long)(x) * 0l)) : (int *)8 ，這邊的第一個 8 可以視為永遠都是 true ，因此都會執行 expression ，接著參考 C99 標準，我們可以得知為什麼這邊要使用三元運算子，且 conditional-expression 為何是 (int *)8

6.5.15 Conditional operator

… 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

• 如果有一個 operand 為 null pointer constant ，那結果會回傳另外一個 operand 的型態
• 如果有一個 operand 型態為 void * 或是 void 的 qualified versions (含有 const 或 volatile 等等的 qualifiers) ，則結果會回傳適當的 void 的 qualified version

而 (int *)8 中的 8 是為了要對齊地址，不要讓編譯器產生 warning ，最後可以得到兩個最終結論

• 如果 x 是 integer constant expression ，則 sizeof(int) == sizeof(*((int *) (NULL))) 成立，回傳 1
• 如果 x 不是 integer constant expression ，則 sizeof(int) == sizeof(*((void *)(....))) 不成立，回傳 0

最後總結 GENMASK_INPUT_CHECK 的實作

• 如果 (l) > (h) 是 integer constant expression ， __is_constexpr 回傳 1 ，且 __builtin_choose_expr 回傳 (l) > (h) ，這時有兩種情況
  • 如果 (l) > (h) 成立，則 BUILD_BUG_ON_ZERO 的條件為 true ，會發起編譯器錯誤
  • 如果 (l) > (h) 不成立，則 BUILD_BUG_ON_ZERO 的條件為 false ，因此編譯通過且回傳 0
• 如果 (l) > (h) 不是 integer constant expression ， __is_constexpr 回傳 0 ，且 __builtin_choose_expr 回傳 0 ，此時 BUILD_BUG_ON_ZERO 的條件為 false ，因此編譯通過且回傳 0

接著分析 __GENMASK 的部份，以下為實作程式碼

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

和小考的實作相似，由於 GENMASK_INPUT_CHECK 通過編譯會回傳 0 ，因此不會影響到 __GENMASK 的結果，所以原始碼才將兩者的結果加起來

分析 tools/power/x86/intel-speed-select/isst.h

以下為 GENMASK 實作原始碼

#define GENMASK(h, l) (((~0UL) << (l)) & (~0UL >> (sizeof(long) * 8 - 1 - (h))))

這邊的實作和我們題目的實作幾乎一樣，只差在這邊的 GENMASK 會根據 long 的大小改變 MSB 的位置

---

測驗 2

延伸問題:

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

程式碼運作原理

考慮以下程式碼

static inline struct fd to_fd(unsigned long v)
{
    return (struct fd){EXP1, v & 3};
}

首先，根據題目敘述

填入一個 fd 結構體，並確保第一個成員的地址得以對 4 個位元組進行向下對齊

可以得知 fd 的第一個成員地址必須向下對齊 4 個位元組，因此可以使用以下的方式，如此一來可以將成員地址的最低 2 位元都清為 0 ，即為 4 的倍數

(v & ~3)

接著觀察結構 fd 的宣告，可以看到抑一個成員的型態為 struct foo *

struct fd {
    struct foo *foo;
    unsigned int flags;
};

只要將 v & -3 轉型成 struct foo * 即可，因此最後的答案為

EXP1 = (struct foo *) (v & -3)

---

測驗 3

延伸問題:

• 解釋上述程式碼運作原理
• 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

解題

這題有點難想，參考了 課前測驗參考解答: Q1 裡提到 32-bit 的位元反轉實作，搭配程式碼測試寫出了以下程式

uint8_t rev8(uint8_t x)
{
    x = (x >> 4) | (x << 4);               
    x = ((x & 0xCC) >> 2) | ((x << 2) & 0xCC);
    x = ((x & 0xAA) >> 1) | ((x << 1) & 0xAA);
    return x;
}

將上述程式碼 line 3 (x << 2) & 0xCC) 和 line 4 ((x << 1) & 0xAA) 的分別改寫則可得到表單答案 (原本是先 << 再 & 改成先 & 再 <<)

EXP1 = (x & 0x33) << 2
EXP2 = (x & 0x55) << 1

程式碼運作原理

接著可以開始討論到底做了什麼，這邊使用 x = 0x87 做測試，一共有三個步驟

// step 1
x = (x >> 4) | (x << 4);

計算過程

x       = 0b10000111
x >> 4  = 0b00001000
x << 4  = 0b01110000
(x >> 4) | (x << 4) = 0b01111000
結果: x = 0b01111000

從結果可以看出第一個步驟是將低 4 位元和高 4 位元互換位置

// step 2
x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2);

計算過程

x               = 0b01111000
(x & 0xCC) >> 2 = 0b00010010
(x & 0x33) << 2 = 0b11000000
((x & 0xCC) >> 2) | ((x & 0x33) << 2) = 0b11010010
結果: x = 0b11010010

將 8-bit 看成兩個部份 (4, 4)
(x & 0xCC) >> 2: 分別將兩部份中的高 2 位元取出，並且移動到低 2 位元的位置
(x & 0x33) << 2: 分別將兩部份中的低 2 位元取出，並且移動到高 2 位元的位置

結論: 分別將兩部份的高 2 位元和低 2 位元交換

// step 3
x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1);

計算過程

x = 0b11010010
(x & 0xAA) >> 1 = 0b01000001
(x & 0x55) << 1 = 0b10100000
((x & 0xAA) >> 1) | ((x & 0x55) << 1) = 0b11100101
結果: x = 0b11100001

將 8-bit 看成兩個部份 (4, 4)
(x & 0xAA) >> 1: 分別將兩部份中的奇數位元取出，並且移動到偶數位元的位置
(x & 0x55) << 1: 分別將兩部份中的偶數位元取出，並且移動到奇數位元的位置

結論: 分別將兩部份的奇數和偶數位元交換

由以上分析可以發現，主要可以看成先切一半接著交換位置，再對一半的一半做一樣的事，直到不能再分割為止

Linux 核心原始碼中的類似技巧

搜尋 reverse bit 後，在 drivers/input/joystick/psxpad-spi.c 發現相似的巨集

#define REVERSE_BIT(x) ((((x) & 0x80) >> 7) | (((x) & 0x40) >> 5) | \
	(((x) & 0x20) >> 3) | (((x) & 0x10) >> 1) | (((x) & 0x08) << 1) | \
	(((x) & 0x04) << 3) | (((x) & 0x02) << 5) | (((x) & 0x01) << 7))

To Do: 理解該程式碼功能

---

測驗 4

延伸問題:

• 解釋上述程式碼運作原理
• 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景

程式碼運作原理

考慮以下程式碼，可以看到這兩個巨集函式主要是使用 for 迴圈進行迭代

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

為了可以更清楚看到巨集展開的樣貌，這邊針對測試觀察

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

首先 foreach_int 的部份，巨集展開如下所示

for (unsigned _foreach_i = 
     (((i) = ((int[]){0, -1, 100, 0, -99})[0]), 0); 
     _foreach_i < sizeof((int[]){0, -1, 100, 0, -99}) / sizeof(int); 
     (i) = ((int[]){0, -1, 100, 0, -99, 0})[EXP4])

展開後就很明顯 EXP4 主要是用來控制下一個資料，因此可以推論 EXP4 = ++_foreach_i

接著換 foreach_ptr 的部份，巨集展開如下所示

for (unsigned _foreach_i = 
     (((p) = (void *) ((typeof(p)[]){"Hello", "world"})[0]), 0); 
     (p); (p) = (void *) ((typeof(p)[]){"Hello", "world", NULL})[EXP5],
          _foreach_no_nullval(_foreach_i, p, ((const void *[]){"Hello", "world"})))

和 EXP4 相同， EXP5 也是用來控制下一個資料，因此我們可以得知 EXP5 = ++_foreach_i

---

測驗 5

延伸問題:

• 解釋上述程式碼運作原理，指出可改進之處，並予以實作
• 在 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼，並予以討論

解題

在解釋程式之前，先將 EXP6 和 EXP7 解出來，參考以下程式碼

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

首先 EXP6 的部份 (位於上述程式的 line 2) 。先參考 line 7 的程式碼，對應之後可以推論 EXP6 = dvs << shift ，後續會解釋程式邏輯

接著換 EXP7 (位於上述程式的 line 10) 。首先發現如果沒有 EXP7 ，則 while 會變成無窮迴圈，因此可以推論 EXP7 是一個 dvd 變小或是 dvs 變大的運算，接著看了上述的程式碼後，可以得知 dvd 要減去 dvs << shift ，因此 EXP7 = dvd -= dvs << shift

程式碼運作原理

/**
 *  @fn     divide()
 *  @brief  回傳兩個有號整數的除法
 */
int divide(int dividend, int divisor)
{
    int signal = 1;
    unsigned int dvd = dividend;
    /** 
     * 判斷 dividend 是否小於 0
     * 如果是，將 signal 變號 (可用 bitwise 優化)
     * 如果是，利用 2's complement 將 dvd 從負數編碼變成正數 
     */
    if (dividend < 0) {
        signal *= -1;
        dvd = ~dvd + 1;
    }

    unsigned int dvs = divisor;
    /** 
     * 判斷 divisor 是否小於 0
     * 如果是，將 signal 變號 (可用 bitwise 優化)
     * 如果是，利用 2's complement 將 dvs 從負數編碼變成正數 
     */
    if (divisor < 0) {
        signal *= -1;
        dvs = ~dvs + 1;
    }

    int shift = 0;
    // 計算 dvs << shift 最接近 dvd 但大於等於 dvd 的 shift 數值
    while (dvd > (dvs << shift))
        shift++;

    unsigned int res = 0;
    while (dvd >= dvs) {
        // 計算 dvs << shift 最接近 dvd 但小於等於 dvd 的 shift 數值
        while (dvd < (dvs << shift))
            shift--;
        // res += 2^shift (加上每一次迭代的商)
        res |= (unsigned int) 1 << shift;
        // 將 dvd 減去商乘上除數
        dvd -= dvs << shift;
    }

    // 如果 signal 為 1 表示結果為正數，但商也大於 INT_MAX 時進入，直接回傳 INT_MAX
    if (signal == 1 && res >= INT_MAX)
        return INT_MAX;
    // 回傳整數的商 (要乘上正負號)
    return res * signal;
}

舉個簡單的例子，假設 dividend = 255 且 divisor = 3

首先討論上述程式碼 line 32 的位置，以下展示迴圈的執行

                             shift
dvd             0b 11111111    

dvs << shift    0b       11    0
dvs << shift    0b      110    1
dvs << shift    0b     1100    2
dvs << shift    0b    11000    3
dvs << shift    0b   110000    4
dvs << shift    0b  1100000    5
dvs << shift    0b 11000000    6
dvs << shift    0b110000000    7

結果: shift = 7 時，離開迴圈

接著討論 line 36 的 while 所執行的情況，以下為執行步驟

+---------------- 第一次迭代 ----------------
初始 shift = 7

line 38 - while (dvd < (dvs << shift))

                             shift
dvd             0b 11111111
dvs << shift    0b110000000    7
dvs << shift    0b 11000000    6

結果: shift = 6 時，離開迴圈

line 41 - res |= (unsigned int) 1 << shift;
res = 0b01000000

line 43 - dvd -= dvs << shift;
dvd = 0b00111111

+---------------- 第二次迭代 ----------------
初始 shift = 6

line 38 - while (dvd < (dvs << shift))

                             shift
dvd             0b 00111111
dvs << shift    0b 11000000    6
dvs << shift    0b  1100000    5
dvs << shift    0b   110000    4

結果: shift = 4 時，離開迴圈

line 41 - res |= (unsigned int) 1 << shift;
res = 0b01010000

line 43 - dvd -= dvs << shift;
dvd = 0b00001111

+---------------- 第三次迭代 ----------------
初始 shift = 4

line 38 - while (dvd < (dvs << shift))

                             shift
dvd             0b 00001111
dvs << shift    0b   110000    4
dvs << shift    0b    11000    3
dvs << shift    0b     1100    2

結果: shift = 2 時，離開迴圈

line 41 - res |= (unsigned int) 1 << shift;
res = 0b01010100

line 43 - dvd -= dvs << shift;
dvd = 0b00000011

+---------------- 第四次迭代 ----------------
初始 shift = 2

line 38 - while (dvd < (dvs << shift))

                             shift
dvd             0b 00000011
dvs << shift    0b     1100    2
dvs << shift    0b      110    1
dvs << shift    0b       11    0


結果: shift = 0 時，離開迴圈

line 41 - res |= (unsigned int) 1 << shift;
res = 0b01010101

line 43 - dvd -= dvs << shift;
dvd = 0b00000000

接著由於 line 36 的條件不成立，因此離開迴圈

最後因為 line 50 回傳 res * signal ，即 0b01010101

指出可改進之處

---

測驗 6

延伸問題:

• 解釋上述程式碼運作原理，指出可改進之處，並予以實作
• 擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行

解題

考慮以下程式碼

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 maxPoints(struct Point *points, int pointsSize)
{
    ...
    if (can_insert(&heads[hash], i, j)) {
        struct point_node *pn = malloc(sizeof(*pn));
        pn->p1 = i;
        pn->p2 = j;
        EXP9;
    }
    ...
}

首先討論 EXP8 的部份，可以得知函式 can_insert() 是用來判斷節點是否可以加到 hash table 上

ToDo: 理解程式碼中…

---

測驗 7

延伸問題:

• 解釋上述程式碼運作原理
• 在 Linux 核心原始程式碼找出類似實作並解說其應用場景
• 研讀論文《Using de Bruijn Sequences to Index a 1 in a Computer Word》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 ilog
• 運用〈你所不知道的 C 語言：前置處理器應用篇〉和〈你所不知道的 C 語言：數值系統篇〉提及的技巧，實作編譯時期 (compile-time) 的 ilog2 實作

解題

考慮以下程式碼

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

觀察程式碼後，從上述程式碼的 line 4 7 10 可以找到規律， v 根據條件分別右移 16 8 及 4 因此可以推論 EXP10 為右移 2 的情況，故 EXP10 = (v > 0x3U) << 1

EXP11 的部份就有點難想，我是測試才發現如果沒有 EXP11 的話回傳值在某些測資會小於正確答案 1 ，因此這格的答案算是 try and error 出來的，EXP11 = ret += v > 1 ，後續會講解

程式碼運作原理

int ilog32(uint32_t v)
{
    int ret = v > 0;
    /**
     * 如果 v > 0xFFFFU ，表示 v 需要至少使用 16 個位元儲存，此時 m = 16
     * 如果 v <= 0xFFFFU，表示 v 不需要用到 16 個位元儲存，此時 m = 0
     */
    int m = (v > 0xFFFFU) << 4;
    /**
     * 如果 v > 0xFFFFU ，將 v 右移 16，接著只考慮高於 16 位元的位置即可 
     * 如果 v <= 0xFFFFU，則 v 將不會改變
     */
    v >>= m;
    // 使用 OR 加上會使用到的位元數
    ret |= m;
    /**
     * 如果 v > 0xFFU ，表示 v 需要至少使用 8 個位元儲存，此時 m = 8
     * 如果 v <= 0xFFU，表示 v 不需要用到 8 個位元儲存，此時 m = 0
     */
    m = (v > 0xFFU) << 3;
    /**
     * 如果 v > 0xFFU ，將 v 右移 8，接著只考慮高於 8 位元的位置即可 
     * 如果 v <= 0xFFU，則 v 將不會改變
     */
    v >>= m;
    // 使用 OR 加上會使用到的位元數
    ret |= m;
    /**
     * 如果 v > 0xFU ，表示 v 需要至少使用 4 個位元儲存，此時 m = 4
     * 如果 v <= 0xFU，表示 v 不需要用到 4 個位元儲存，此時 m = 0
     */
    m = (v > 0xFU) << 2;
    /**
     * 如果 v > 0xFU ，將 v 右移 4，接著只考慮高於 4 位元的位置即可 
     * 如果 v <= 0xFU，則 v 將不會改變
     */
    v >>= m;
    // 使用 OR 加上會使用到的位元數
    ret |= m;
    /**
     * 如果 v > 0x3U ，表示 v 需要至少使用 2 個位元儲存，此時 m = 2
     * 如果 v <= 0x3U，表示 v 不需要用到 2 個位元儲存，此時 m = 0
     */
    m = (v > 0x3U) << 1;
    /**
     * 如果 v > 0x3U ，將 v 右移 2，接著只考慮高於 2 位元的位置即可 
     * 如果 v <= 0x3U，則 v 將不會改變
     */
    v >>= m;
    // 使用 OR 加上會使用到的位元數
    ret |= m;
    // 如果最後 v > 1 ， ret 要在加 1  
    ret += v > 1;
    return ret;
}

根據上述程式碼，舉個簡單的例子，假設 v = 0x7FFFFF

line 3     - int ret = v > 0;
ret = 1

line 8~15  - int m = (v > 0xFFFFU) << 4;
m = 16
v = 0x7F
ret = 17

line 20~27 - m = (v > 0xFFU) << 3;
m = 0
v = 0x7F
ret = 17

line 32~39 - m = (v > 0xFU) << 2;
m = 4
v = 0x7
ret = 21

line 44~51 - m = (v > 0x3U) << 1;
m = 2
v = 0x1
ret = 23

line 53 - ret += v > 1;
ret = 23

最後結果為 23

稍微研究 line 53 的程式碼 ret += v > 1 可以得知是為了要找 v 的 MSB 是否會在第 3 7 11 15 ... 31 的位置，如果有的話必須再加 1

---

測驗 8

延伸問題:

• 解釋上述程式碼運作原理
• 以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升
• 研讀 Static B-Trees ，探討針對記憶體佈局 (memory layout) 的改進策略

---

測驗 9

延伸問題:

• 解釋上述程式碼運作原理，並撰寫出對應 ROUND_DOWN 巨集
• 在 Linux 核心找出類似的巨集和程式碼，說明 round-up/down 的應用場合

程式碼運作原理

這邊參考別人的 Github ，比對後可以得到答案 MMM = 1u 且 NNN = MAX_ALIGNMENT - 1u

根據以下程式碼，可以得知主要邏輯就是將 x 的低 4 位元分別加上 1 ，即 0b1111 ，接著將低 4 位元的部份利用 & 清掉

#define MAX_ALIGNMENT 16
#define ROUND_UP_TO_ALIGNMENT_SIZE(x) \
    (((x) + MAX_ALIGNMENT - 1u) & ~(MAX_ALIGNMENT - 1u))

以下提供一些測試結果

x    ROUND_UP_TO_ALIGNMENT_SIZE
0               0
5              16
10             16
15             16
20             32
25             32
30             32
35             48
40             48
45             48
50             64

撰寫對應的 ROUND_DOWN

理解向上對齊後，向下對齊就沒有那麼的難想了，兩者的差別只在於向上對齊需要進位後再清除，而向下對齊可以直接清除即可。以下為實作程式碼

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

以下提供一些測試結果

x    ROUND_DOWN_TO_ALIGNMENT_SIZE
0               0
5               0
10              0
15              0
20             16
25             16
30             16
35             32
40             32
45             32
50             48

---

測驗 10

延伸問題:

• 解釋上述程式碼運作原理
• 在 Linux 核心找出類似的巨集和程式碼，說明 div round-up/closest 的應用場合

程式碼運作原理

考慮以下程式碼

#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))                \
            : ((MMM) / (__d));               \
    })

其中最重要的部份在於 line 5 6 的判斷式，以下提供例子判斷 (divisor 不為負數)

• 情況 1 (x 屬於 unsigned 或 divisor 屬於 unsigned)

  • 執行 RRR 的程式碼

• 情況 2 (x 和 divisor 屬於 signed)

  • 如果 x 和 divisor 同號( x 和 divisor 皆為正)，執行 RRR 的程式碼
  • 如果 x 和 divisor 異號( x 為負 divisor 為正)，執行 MMM 的程式碼

從上述的兩種情況可以得到一個結論

x 為正時執行 RRR 程式碼；為負時執行 MMM 程式碼

因此得到答案

RRR = (__x) + ((__d) >> 1) (將 __x 加上除數的一半(因為 __x 為正)，再經過除法運算得到最靠近的整數)
MMM = (__x) - ((__d) >> 1) (將 __x 減上除數的一半(因為 __x 為負)，再經過除法運算得到最靠近的整數)

不過這邊有找到一個有問題的情況，如果 x 為負且 divisor 屬於 unsigned ，使用以下程式測試

// x = -10, divisor = 3U
printf("%d\n", DIVIDE_ROUND_CLOSEST(-10, 3U));

產生以下結果

1431655762

---

測驗 11

延伸問題:

• 解釋上述程式碼運作原理，嘗試利用硬體的 clz/ctz 指令改寫
• 在 Linux 核心找出類似的巨集和程式碼，說明其應用場景

程式碼運作原理

考慮以下程式碼，目的是要計算整數開平方

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

在解題之前可以先討論實作演算法，參考 Digit-by-digit calculation ，

To Do: 理解演算法中