2023q1 Homework2 (quiz2)

contributed by < ShamrockLee >

測驗 1

填答後，完整程式碼如下（省略 #include <stdint.h> ）：

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 環境編譯得到的組合語言節錄如下：

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

而這段程式碼顯然能精簡為：

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

對應的組合語言為：

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 改寫如下

uint64_t next_pow2(uint64_t x)
{
    return 1ul << 64 - __builtin_clzl(x);
}

對應的組合語言為：

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 的思路後，嘗試實作的過程與結果。

期望實作的兩個函式宣告如下：

#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{array}{ll}\lfloor {\log }_{2}x\rfloor & (x>0)\\ -1& (x=0)\end{array}(x\in {\mathbb{Z}}_0^{+})$$

$$\text{ceil\_log2\_u32}(x)=\{\begin{array}{ll}\lceil {\log }_{2}x\rceil & (x>0)\\ -1& (x=0)\end{array}(x\in {\mathbb{Z}}_0^{+})$$

include/linux/log2.h 當中， ilog2_u32 實作如下：

static __always_inline __attribute__((const))
int __ilog2_u32(u32 n)
{
	return fls(n) - 1;
}

include/asm-generic/bitops/fls.h 當中， fls 實作如下：

/**
 * 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 的版本：

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

此時

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 。

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

TODO: 針對 floor_log2_u32 及 ceil_log2_u32，找出可共用的程式碼，並利用巨集來產生這二個函式。

更新：

ceil_log2_u32 的例外處理能透過把兩處 - 1 分別換成 (x != 0) 與 (x == 0) ，不用花那麼多指令週期建立 mask_anybit 。

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 並改進〉，能拆解上述無分支的 ffs 函數以巨集定義，與 fls 共用下半部份程式碼，產生與 〈回顧 bitops 並改進〉 當中所提出的 gen_ffs 、 gen_fls 相容的巨集。

〈回顧 bitops 並改進〉引入使用 _Pragma 運算子包裝的 loop-unrolling directive ，使巨集能同時支援不同長度的輸入值，同時不必增加 branch 。但是當中提出的

_Pragma("GCC unroll 6")

僅支援 GCC 編譯器。考慮到 Clang 也支援 loop unrolling ，能定義巨集

#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 ，而不必再以 conditional directives 繞過編譯器的差異。相關的 feature request 在 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:

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

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

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

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

/* 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 等相關函數。