2022q1 Homework3 (quiz3)

--- tags: 2022 linux kernel --- # 2022q1 Homework3 (quiz3) contributed by < [`Risheng1128`](https://github.com/Risheng1128) > > [作業說明](https://hackmd.io/@sysprog/linux2022-homework3) > [測驗題目](https://hackmd.io/@sysprog/linux2022-quiz3) ## 測驗 `1` :::info 延伸問題: - [x] 解釋上述程式碼運作原理 - [x] 比較 Linux 核心 `GENMASK` 巨集的實作，闡述其額外的考量 - [ ] 舉出 Linux 核心原始程式碼中二處 `GENMASK` 巨集和 [include/linux/bitfield.h](https://github.com/torvalds/linux/blob/master/include/linux/bitfield.h) 的應用案例 ::: ### 程式碼運作原理討論以下的程式碼，目的為產生一組從 `l` bit 到 `h` bit 為 `1` 的 mask ```c #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` 位元的系統，可以得到解答 :::success `LEFT = 63 - h` `RIGHT = l` 不過這邊有個問題沒有釐清，還不確定為什麼題目要 `>> l` ::: ### Linux 核心 `GENMASK` 在 github 中搜尋 `GENMASK` 後發現有兩處定義，分別位於 [`include/linux/bits.h`](https://github.com/torvalds/linux/blob/master/include/linux/bits.h) 和 [`tools/power/x86/intel-speed-select/isst.h`](https://github.com/torvalds/linux/blob/master/tools/power/x86/intel-speed-select/isst.h) #### 分析 [`include/linux/bits.h`](https://github.com/torvalds/linux/blob/master/include/linux/bits.h) 以下為 `GENMASK` 實作原始碼 ```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 #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](https://github.com/torvalds/linux/commit/295bcca84916cb5079140a89fccb472bb8d1f6e2) 可以得知 `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`](https://github.com/torvalds/linux/blob/master/include/uapi/linux/const.h) 裡面的註解及原始碼可以清楚得知巨集 `__ASSEMBLY__` 是用來區分常數巨集在 assembler 和 C code 的實作 ```c /* 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](https://github.com/torvalds/linux/blob/master/include/linux/build_bug.h) 可以找到原始碼 ```c #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](http://rd-life.blogspot.com/2009/12/sparse-type-checking.html) ，可以清楚知道巨集 `__CHECKER__` 是要判斷程式的語義 (semantics) ，接著分析 `BUILD_BUG_ON_ZERO(e)` ，從上述註解可以得知當 `BUILD_BUG_ON_ZERO(e)` 的條件 `e` 為 `true` 時，會報出編譯器錯誤 ```c #define BUILD_BUG_ON_ZERO(e) ((int)(sizeof(struct { int:(-!!(e)); }))) ``` 接著參考 [bit-field](https://hackmd.io/@sysprog/c-bitfield) 得到上述原始碼的詳細分析，首先分析 `(-!!(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` ，且不會使用到任何空間 :::success 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](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) ，以下為 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 標準，如下所示 :::success 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`](https://github.com/torvalds/linux/blob/master/include/linux/const.h) 中找到，以下為原始碼 ```c /* * This returns a constant expression while determining if an argument is * a constant expression, most importantly without evaluating the argument. * Glory to Martin Uecker <Martin.Uecker@med.uni-goettingen.de> */ #define __is_constexpr(x) \ (sizeof(int) == sizeof(*(8 ? ((void *)((long)(x) * 0l)) : (int *)8))) ``` 首先根據以前的 [commit](https://github.com/torvalds/linux/commit/f747e6667ebb2ffb8133486c9cd19800d72b0d98) 可以得知使用 `__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](https://stackoverflow.com/questions/49481217/linux-kernels-is-constexpr-macro) 的解說考慮 `((void *)((long)(x) * 0l))` ，首先 `(long)(x)` 是為了避免 `x` 可能為指標型態的情況，接著參考以下 C99 規格，定義了 **integer constant expression** 以及 **null pointer constant** ，並考慮兩種情況 :::success 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` :::success 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` :::success 最後總結 `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` 的部份，以下為實作程式碼 ```c #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`](https://github.com/torvalds/linux/blob/master/tools/power/x86/intel-speed-select/isst.h) 以下為 `GENMASK` 實作原始碼 ```c #define GENMASK(h, l) (((~0UL) << (l)) & (~0UL >> (sizeof(long) * 8 - 1 - (h)))) ``` 這邊的實作和我們題目的實作幾乎一樣，只差在這邊的 `GENMASK` 會根據 `long` 的大小改變 MSB 的位置 --- ## 測驗 `2` :::info 延伸問題: - [x] 解釋上述程式碼運作原理 - [ ] 在 Linux 核心原始程式碼找出類似技巧的實作 (例如檔案系統) 並解說 ::: ### 程式碼運作原理考慮以下程式碼 ```c static inline struct fd to_fd(unsigned long v) { return (struct fd){EXP1, v & 3}; } ``` 首先，根據題目敘述 > 填入一個 fd 結構體，並確保第一個成員的地址得以對 4 個位元組進行向下對齊可以得知 fd 的第一個成員地址必須向下對齊 4 個位元組，因此可以使用以下的方式，如此一來可以將成員地址的最低 2 位元都清為 0 ，即為 4 的倍數 ```c (v & ~3) ``` 接著觀察結構 `fd` 的宣告，可以看到抑一個成員的型態為 `struct foo *` ```c struct fd { struct foo *foo; unsigned int flags; }; ``` 只要將 `v & -3` 轉型成 `struct foo *` 即可，因此最後的答案為 > EXP1 = (struct foo *) (v & -3) --- ## 測驗 `3` :::info 延伸問題: - [x] 解釋上述程式碼運作原理 - [ ] 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景 ::: ### 解題這題有點難想，參考了 [課前測驗參考解答: Q1](https://hackmd.io/@sysprog/bitwise-reverse) 裡提到 32-bit 的位元反轉實作，搭配程式碼測試寫出了以下程式 ```c= 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` 做測試，一共有三個步驟 ```c // step 1 x = (x >> 4) | (x << 4); ``` 計算過程 ```shell x = 0b10000111 x >> 4 = 0b00001000 x << 4 = 0b01110000 (x >> 4) | (x << 4) = 0b01111000 結果: x = 0b01111000 ``` :::success 從結果可以看出第一個步驟是將低 4 位元和高 4 位元互換位置 ::: ```c // step 2 x = ((x & 0xCC) >> 2) | ((x & 0x33) << 2); ``` 計算過程 ```shell x = 0b01111000 (x & 0xCC) >> 2 = 0b00010010 (x & 0x33) << 2 = 0b11000000 ((x & 0xCC) >> 2) | ((x & 0x33) << 2) = 0b11010010 結果: x = 0b11010010 ``` :::success 將 8-bit 看成兩個部份 (4, 4) `(x & 0xCC) >> 2`: 分別將兩部份中的高 2 位元取出，並且移動到低 2 位元的位置 `(x & 0x33) << 2`: 分別將兩部份中的低 2 位元取出，並且移動到高 2 位元的位置結論: 分別將兩部份的高 2 位元和低 2 位元交換 ::: ```c // step 3 x = ((x & 0xAA) >> 1) | ((x & 0x55) << 1); ``` 計算過程 ```shell x = 0b11010010 (x & 0xAA) >> 1 = 0b01000001 (x & 0x55) << 1 = 0b10100000 ((x & 0xAA) >> 1) | ((x & 0x55) << 1) = 0b11100101 結果: x = 0b11100001 ``` :::success 將 8-bit 看成兩個部份 (4, 4) `(x & 0xAA) >> 1`: 分別將兩部份中的奇數位元取出，並且移動到偶數位元的位置 `(x & 0x55) << 1`: 分別將兩部份中的偶數位元取出，並且移動到奇數位元的位置結論: 分別將兩部份的奇數和偶數位元交換 ::: 由以上分析可以發現，主要可以看成先切一半接著交換位置，再對**一半的一半**做一樣的事，直到不能再分割為止 ### Linux 核心原始碼中的類似技巧搜尋 `reverse bit` 後，在 [`drivers/input/joystick/psxpad-spi.c`](https://github.com/torvalds/linux/blob/5bfc75d92efd494db37f5c4c173d3639d4772966/drivers/input/joystick/psxpad-spi.c) 發現相似的巨集 ```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)) ``` :::warning To Do: 理解該程式碼功能 ::: --- ## 測驗 `4` :::info 延伸問題: - [x] 解釋上述程式碼運作原理 - [ ] 在 Linux 核心原始程式碼找出類似技巧的實作並解說其應用場景 ::: ### 程式碼運作原理考慮以下程式碼，可以看到這兩個巨集函式主要是使用 `for` 迴圈進行迭代 ```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__}))) ``` 為了可以更清楚看到巨集展開的樣貌，這邊針對測試觀察 ```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); } ``` 首先 `foreach_int` 的部份，巨集展開如下所示 ```c 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` 的部份，巨集展開如下所示 ```c 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` :::info 延伸問題: - [ ] 解釋上述程式碼運作原理，指出可改進之處，並予以實作 - [ ] 在 Linux 核心原始程式碼中找出針對整數/浮點數/定點數除法特別撰寫的程式碼，並予以討論 ::: ### 解題在解釋程式之前，先將 `EXP6` 和 `EXP7` 解出來，參考以下程式碼 ```c= 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` ### 程式碼運作原理 ```c= /** * @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` 所執行的情況，以下為執行步驟 ```diff +---------------- 第一次迭代 ---------------- 初始 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` :::info 延伸問題: - [ ] 解釋上述程式碼運作原理，指出可改進之處，並予以實作 - [ ] 擴充 LeetCode 題目，考慮更多座標點的輸入 (例如超過 10 萬個) 時，設計有效的資料結構以降低記憶體開銷，並確保快速的執行 ::: ### 解題考慮以下程式碼 ```c 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 上 :::warning ToDo: 理解程式碼中... ::: --- ## 測驗 `7` :::info 延伸問題: - [x] 解釋上述程式碼運作原理 - [ ] 在 Linux 核心原始程式碼找出類似實作並解說其應用場景 - [ ] 研讀論文《[Using de Bruijn Sequences to Index a 1 in a Computer Word](http://supertech.csail.mit.edu/papers/debruijn.pdf)》，探討缺乏硬體 ctz/clz 指令的微處理器上，如何實作 branchless 的 ilog - [ ] 運用〈[你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor)〉和〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉提及的技巧，實作編譯時期 (compile-time) 的 ilog2 實作 ::: ### 解題考慮以下程式碼 ```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; } ``` 觀察程式碼後，從上述程式碼的 `line 4 7 10` 可以找到規律， v 根據條件分別右移 `16` `8` 及 `4` 因此可以推論 `EXP10` 為右移 `2` 的情況，故 `EXP10 = (v > 0x3U) << 1` `EXP11` 的部份就有點難想，我是測試才發現如果沒有 `EXP11` 的話回傳值在某些測資會小於正確答案 `1` ，因此這格的答案算是 `try and error` 出來的，`EXP11 = ret += v > 1` ，後續會講解 ### 程式碼運作原理 ```c= 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` :::info 延伸問題: - [ ] 解釋上述程式碼運作原理 - [ ] 以 C99 改寫上述程式碼，並寫出更精簡高效的實作，和最初的實作相比，探討效率的提升 - [ ] 研讀 [Static B-Trees](https://en.algorithmica.org/hpc/data-structures/s-tree/) ，探討針對記憶體佈局 (memory layout) 的改進策略 ::: --- ## 測驗 `9` :::info 延伸問題: - [x] 解釋上述程式碼運作原理，並撰寫出對應 `ROUND_DOWN` 巨集 - [ ] 在 Linux 核心找出類似的巨集和程式碼，說明 round-up/down 的應用場合 ::: ### 程式碼運作原理這邊參考別人的 [Github](https://gist.github.com/zerojiu/5673c6c1cbb21408100381b6cfa07fc5) ，比對後可以得到答案 `MMM = 1u` 且 `NNN = MAX_ALIGNMENT - 1u` 根據以下程式碼，可以得知主要邏輯就是將 `x` 的低 `4` 位元分別加上 `1` ，即 `0b1111` ，接著將低 `4` 位元的部份利用 `&` 清掉 ```c #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` 理解向上對齊後，向下對齊就沒有那麼的難想了，兩者的差別只在於向上對齊需要進位後再清除，而向下對齊可以直接清除即可。以下為實作程式碼 ```c #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` :::info 延伸問題: - [x] 解釋上述程式碼運作原理 - [ ] 在 Linux 核心找出類似的巨集和程式碼，說明 div round-up/closest 的應用場合 ::: ### 程式碼運作原理考慮以下程式碼 ```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)) \ : ((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` 的程式碼從上述的兩種情況可以得到一個結論 :::success `x` 為正時執行 `RRR` 程式碼；為負時執行 `MMM` 程式碼 ::: 因此得到答案 ``` RRR = (__x) + ((__d) >> 1) (將 __x 加上除數的一半(因為 __x 為正)，再經過除法運算得到最靠近的整數) MMM = (__x) - ((__d) >> 1) (將 __x 減上除數的一半(因為 __x 為負)，再經過除法運算得到最靠近的整數) ``` :::warning 不過這邊有找到一個有問題的情況，如果 `x` 為負且 `divisor` 屬於 `unsigned` ，使用以下程式測試 ```c // x = -10, divisor = 3U printf("%d\n", DIVIDE_ROUND_CLOSEST(-10, 3U)); ``` 產生以下結果 ```shell 1431655762 ``` ::: --- ## 測驗 `11` :::info 延伸問題: - [ ] 解釋上述程式碼運作原理，嘗試利用硬體的 clz/ctz 指令改寫 - [ ] 在 Linux 核心找出類似的巨集和程式碼，說明其應用場景 ::: ### 程式碼運作原理考慮以下程式碼，目的是要計算整數開平方 ```c 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](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation) ， :::warning To Do: 理解演算法中 :::