2023q1 Homework2 (quiz2)

# 2023q1 Homework2 (quiz2) contributed by < `ShamrockLee` > ### 測驗 `1` 填答後，完整程式碼如下（省略 `#include <stdint.h>` ）： ```c= uint64_t next_pow2(uint64_t x) { x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 8; // AAAA is 8 x |= x >> 16; x |= x >> 32; // BBBB is 32 return x + 1; // CCCC is x + 1 } ``` 這段程式碼的運作方式如下： 1. 以最高位元的值覆蓋更低位元的值。 2. 整個數加一，以得到「最高位的更高一位是 1 ，其他位都是 0 」的數。以 `gcc -O2 -std=c99 -S next_pow2.c` 在 x86_64-linux 環境編譯得到的組合語言節錄如下： ```asm= next_pow2: .LFB0: .cfi_startproc movq %rdi, %rax shrq %rax orq %rdi, %rax movq %rax, %rdx shrq %rax orq %rdx, %rax movq %rax, %rdx shrq %rdx orq %rdx, %rax movq %rax, %rdx shrq %rdx orq %rax, %rdx movq %rdx, %rax shrq %rax orq %rax, %rdx movq %rdx, %rax shrq %rax orq %rdx, %rax movq %rax, %rdx shrq %rdx orq %rdx, %rax movq %rax, %rdx shrq $8, %rdx orq %rax, %rdx movq %rdx, %rax shrq $16, %rax orq %rax, %rdx movq %rdx, %rax shrq $32, %rax orq %rdx, %rax addq $1, %rax ret .cfi_endproc ``` 而這段程式碼顯然能精簡為： ```c= uint64_t next_pow2(uint64_t x) { x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x |= x >> 32; return x + 1; } ``` 對應的組合語言為： ```asm= next_pow2: .LFB0: .cfi_startproc movq %rdi, %rax shrq %rax orq %rax, %rdi movq %rdi, %rax shrq $2, %rax orq %rdi, %rax movq %rax, %rdi shrq $4, %rdi orq %rdi, %rax movq %rax, %rdi shrq $8, %rdi orq %rax, %rdi movq %rdi, %rax shrq $16, %rax orq %rax, %rdi movq %rdi, %rax shrq $32, %rax orq %rdi, %rax addq $1, %rax ret .cfi_endproc ``` 以 GCC 和 Clang 有支援的 `__builtin_clzl` 改寫如下 ```c= uint64_t next_pow2(uint64_t x) { return 1ul << 64 - __builtin_clzl(x); } ``` 對應的組合語言為： ```asm= next_pow2: .LFB0: .cfi_startproc bsrq %rdi, %rdi movl $64, %ecx movl $1, %eax xorq $63, %rdi subl %edi, %ecx salq %cl, %rax ret .cfi_endproc ``` 能看到 `bsrq` (Bit Scan Reverse) 指令。在 Linux 核心中， `include/linux/log2.h` 定義了 `ilog2` 用到了類似的實做技巧。 #### 延伸問題：無分支的 floor_log2_u32 與 ceil_log2_u32 實作（含例外處理）一對一討論時，我未能實作出能維護的無分支 `floor_log2_u32` 與 `ceil_log2_u32` 函式。以下是我在參考 `include/linux/ilog2.h` 的思路後，嘗試實作的過程與結果。期望實作的兩個函式宣告如下： ```c= #include <stdint.h> int32_t floor_log2_u32(uint32_t x); int32_t ceil_log2_u32(uint32_t x); ``` 期望的行為如下： \\[ \text{floor_log2_u32}(x) = \begin{cases} \lfloor \log_2 x \rfloor & (x \gt 0) \\ -1 & (x = 0) \end{cases} (x \in \mathbb Z^+_0) \\] \\[ \text{ceil_log2_u32}(x) = \begin{cases} \lceil \log_2 x \rceil & (x \gt 0) \\ -1 & (x = 0) \end{cases} (x \in \mathbb Z^+_0) \\] `include/linux/log2.h` 當中， `ilog2_u32` 實作如下： ```c= static __always_inline __attribute__((const)) int __ilog2_u32(u32 n) { return fls(n) - 1; } ``` `include/asm-generic/bitops/fls.h` 當中， `fls` 實作如下： ```c= /** * fls - find last (most-significant) bit set * @x: the word to search * * This is defined the same way as ffs. * Note fls(0) = 0, fls(1) = 1, fls(0x80000000) = 32. */ static __always_inline int fls(unsigned int x) { int r = 32; if (!x) return 0; if (!(x & 0xffff0000u)) { x <<= 16; r -= 16; } if (!(x & 0xff000000u)) { x <<= 8; r -= 8; } if (!(x & 0xf0000000u)) { x <<= 4; r -= 4; } if (!(x & 0xc0000000u)) { x <<= 2; r -= 2; } if (!(x & 0x80000000u)) { x <<= 1; r -= 1; } return r; } ``` 將以上 `fls` 改為無分支、不使用 extension 的版本： ```c= static inline uint32_t fls_u32(uint32_t x) { // x_pow2 is x with all non-msb zeroized uint32_t x_pow2 = x >> 1; x_pow2 |= x_pow2 >> 1; x_pow2 |= x_pow2 >> 2; x_pow2 |= x_pow2 >> 4; x_pow2 |= x_pow2 >> 8; // Consider that x might be 0. x_pow2 += (x != 0); return // 0b01010101'01010101'01010101'01010101u (((x_pow2 & 0x55555555u) != 0)) + // 0b01100110'01100110'01100110'01100110u (((x_pow2 & 0x66666666u) != 0) << 1) + // 0b01111000'01111000'01111000'01111000u (((x_pow2 & 0x78787878u) != 0) << 2) + // 0b01111111'10000000'01111111'10000000u (((x_pow2 & 0x7f807f80u) != 0) << 3) + // 0b01111111'11111111'10000000'00000000u (((x_pow2 & 0x7fff8000u) != 0) << 4) + // 0b10000000'00000000'00000000'00000000u (((x_pow2 & 0x80000000u) != 0) << 5); } ``` 此時 ```c= int32_t floor_log2_u32(uint32_t x) { return fls_u32(x) - 1; } ``` 以上實作很自然的滿足了 `floor_log2_u32(0) == -1` ，因此無須另外處理。對於正整數 `x` ， `ceil_log2_u32(x)` 能被定義為 `fls_u32(x - 1)` 。但在 C 標準中， -1 在轉型為無號整數的行為未定義。因此，遵守標準的實作必須處理 `x` 為 0 時的例外情況。以下實作使用 `mask_anybit` 作為處理例外的位元遮罩。如果 x 有任何不為零的位元， mask_anybit 就會是 `0xffffffff` ，否則是 `0` 。 ```c= int32_t ceil_log2_u32(uint32_t x) { uint32_t mask_anybit = x; mask_anybit |= mask_anybit >> 1; mask_anybit |= mask_anybit << 1; mask_anybit |= mask_anybit >> 2; mask_anybit |= mask_anybit << 2; mask_anybit |= mask_anybit >> 4; mask_anybit |= mask_anybit << 4; mask_anybit |= mask_anybit >> 8; mask_anybit |= mask_anybit << 8; mask_anybit |= mask_anybit >> 16; mask_anybit |= mask_anybit << 16; return (fls_u32(mask_anybit & (x - 1))) - (~mask_anybit & 1); } ``` :::warning TODO: 針對 `floor_log2_u32` 及 `ceil_log2_u32`，找出可共用的程式碼，並利用巨集來產生這二個函式。 ::: 更新： `ceil_log2_u32` 的例外處理能透過把兩處 `- 1` 分別換成 `(x != 0)` 與 `(x == 0)` ，不用花那麼多指令週期建立 `mask_anybit` 。 ```c= int32_t ceil_log2_u32(uint32_t x) { return fls_u32(x - (x != 0)) - (x == 0); } ``` 如此一來， `floor_log2_u32` 與 `ceil_log2_u32` 的共通處只剩下「都有呼叫 `fls_u32` 」。對照〈[回顧 bitops 並改進](https://hackmd.io/@sysprog/ByS9w_lHh)〉，能拆解上述無分支的 `ffs` 函數以巨集定義，與 `fls` 共用下半部份程式碼，產生與〈回顧 bitops 並改進〉當中所提出的 `gen_ffs` 、 `gen_fls` 相容的巨集。〈回顧 bitops 並改進〉引入使用 `_Pragma` 運算子包裝的 loop-unrolling directive ，使巨集能同時支援不同長度的輸入值，同時不必增加 branch 。但是當中提出的 ```c _Pragma("GCC unroll 6") ``` 僅支援 GCC 編譯器。考慮到 Clang 也支援 loop unrolling ，能定義巨集 ```c #ifdef __clang__ #define unroll_ffls_branchless _Pragma("clang loop unroll_count(6)") #elif __GNUC__ >= 8 #define unroll_ffls_branchless _Pragma("GCC unroll 6") #else #define unroll_ffls_branchless #endif ``` 並將 `unroll_ffls_branchless` 加在 while loop 之前。這樣無論以 GCC 與 Clang 編譯，迴圈都能正確展開。我曾嘗試寫出能接收輸入值以指定迴圈展開次數的巨集（類似 `pragma_unroll(N)` ），但受限於 * 十進位整數常數（ decimal integer constant ）沒有特定的前綴，無法用以保留前方的空格 * 括號（`()`）不適用 token pasting （`##`）而一直無法實作成功。根本的解決之道，大概是從 GCC 下手，使其支援 Clang 的 [`#pragma unroll N`](https://clang.llvm.org/docs/AttributeReference.html#pragma-unroll-pragma-nounroll) ，而不必再以 conditional directives 繞過編譯器的差異。相關的 [feature request](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=91840) 在 GCC 的 bug tracker 當中有人提出，或許暑假能試著實作。雖然如此，在嘗試過程中發現了 Linux 核心內網路與網路 driver 相關程式的註解中， `transmit` 與其變化形不時被拼錯成 `tranmit` ，因此送了一組 patches 到 Linux 核心，已有部份獲得維護者採納，進入 `net-next` source tree 。觀察上方的 `fls_u32` 能發現函數實作由兩部份構成： 1. 將輸入值最高非零位元以外的位元都設成零。 2. 以二分搜尋定位出非零位元的索引。將 `fls` 與 `ffs` 比較，能發現兩者差異僅在得知非零最高位元或非零最低位元的索引，所以只要改動「將其他位元設成零」的步驟，而能共用定位的步驟。因此，以下將以三個巨集實作這兩種函數： * `__preserve_msb_branchless` 負責「保留非零最高位元」的無分支實作 * `__preserve_lsb_branchless` 負責「保留非零最低位元」的無分支實作 * `__locate_bit_branchless` 負責「定位非零位元索引」的無分支實作〈回顧 bitops 並改進〉對 Linux 核心當中現有實作分析後，發現了「索引從 1 開始」與「索引從 0 零開始」兩種風格，並以「回傳 0 」處理「索引從 0 開始」風格的例外（輸入值為 0 的情形）。這樣一來，「從 0 開始」在輸入值為 0 、為 1 時會對應到同樣的值，而有資訊損失。因此我針對「從 1 的情形」實作運算步驟，並在 `gen_fls_branchless` 與 `gen_ffs_branchless` 內處理「從 0 開始」的例外。以下是實作的程式碼： `__preserve_msb_branchless`: ```c /* Preserve the most significant bit set of X and unset others. * Return zero when non set. */ #define __preserve_msb_branchless(X, type) \ do { \ type __is_nonzero = !!(X); \ (X) = (X) >> 1; \ unroll_ffls_branchless for (size_t _i_exp = 1; \ _i_exp < (sizeof(X) << 3); _i_exp <<= 1) \ { \ (X) |= (X) >> _i_exp; \ } \ (X) += __is_nonzero; \ } while (0) ``` `__preserve_lsb_branchless`: ```c /* Preserve the least significant bit set of X and unset others. * Return zero when non set. */ #define __preserve_lsb_branchless(X, type) \ do { \ unroll_ffls_branchless for (size_t _i_exp = 1; \ _i_exp < (sizeof(X) << 3); _i_exp <<= 1) \ { \ (X) |= (X) << _i_exp; \ } \ type _x_upperfilled = (X); \ (X) = ~(X) + (!!_x_upperfilled); \ (X) &= _x_upperfilled; \ } while (0) ``` `__locate_bit_branchless`: ```c /* Take in an unsigned integer with at most one bit set, and then * output the 1-based digit of that bit. Return 0 if no bits are set. * * Bits higher than (2**64 - 1) will be truncated. * * Determine the result bit value through binary search with the following * masks: * * 0b01010101'01010101'01010101'01010101'01010101'01010101'01010101'01010101u * 0b01100110'01100110'01100110'01100110'01100110'01100110'01100110'01100110u * 0b01111000'01111000'01111000'01111000'01111000'01111000'01111000'01111000u * 0b01111111'10000000'01111111'10000000'01111111'10000000'01111111'10000000u * 0b01111111'11111111'10000000'00000000'01111111'11111111'10000000'00000000u * 0b01111111'11111111'11111111'11111111'10000000'00000000'00000000'00000000u * 0b10000000'00000000'00000000'00000000'00000000'00000000'00000000'00000000u */ #define __locate_bit_branchless(x_pow2, in_type, out_type) \ ((out_type) (((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \ 0x5555555555555555u)))) \ << 0) + \ ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \ 0x6666666666666666u)))) \ << 1) + \ ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \ 0x7878787878787878u)))) \ << 2) + \ ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \ 0x7f807f807f807f80u)))) \ << 3) + \ ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \ 0x7fff80007fff8000u)))) \ << 4) + \ ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \ 0x7fffffff80000000u)))) \ << 5) + \ ((!!((x_pow2) & ((in_type) (((in_type) ~(in_type) 0) & \ 0x8000000000000000u)))) \ << 6))) ``` `gen_fls_branchless`: ```c /* Branchless version of gen_fls */ #define gen_fls_branchless(in_type, out_type, start_from, fn_name) \ static __always_inline out_type fn_name(in_type x) \ { \ __preserve_msb_branchless(x, in_type); \ out_type _ret = __locate_bit_branchless(x, in_type, out_type); \ return _ret - (out_type) ((!(start_from)) & (!(_ret))); \ } } ``` `gen_ffs_branchless`: ```c /* Branchless version of gen_ffs */ #define gen_ffs_branchless(in_type, out_type, start_from, fn_name) \ static __always_inline out_type fn_name(in_type x) \ { \ __preserve_lsb_branchless(x, in_type); \ out_type _ret = __locate_bit_branchless(x, in_type, out_type); \ return _ret - (out_type) ((!(start_from)) & (!(_ret))); \ } ``` 由於界面與〈回顧 bitops 並改進〉的 `gen_fls` 、 `gen_ffs` 一致，故能套用其方法一併定義 `clz` 、 `ctz` 等相關函數。

Read more

COSCUP 2023 Nix Flakes Slides

2023q1 Homework5 (assessment)

2023q1 Homework3 (quiz3)

2023q1 Homework1 (lab0)