# 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` 等相關函數。
Sign in with Wallet
Connect another wallet