2023q1 Homework2 (quiz2)

contributed by < paulpeng-popo >

題目

測驗一

解釋程式碼原理

輸入一個數，目標是找到最接近且大於等於 2 的冪的值，舉例來說

\(next\_pow2(7) = 8\)
\(next\_pow2(13) = 16\)
\(next\_pow2(42) = 64\)

最初的想法，就是找出最左邊的 1，然後讓它左移 1 就完成了，程式如下：

uint64_t my_next_pow2(uint64_t x) {
    x |= x >> 32;
    x |= x >> 16;
    x |= x >> 8;
    x |= x >> 4;
    x |= x >> 2;
    x |= x >> 1;
    return (x ^ (x >> 1)) << 1;
}

運作如下，利用二分法的概念，逐步設定 (set 1) 每一部份對應的位置

x = 0010000000000000                      // input x
x = 00100000 00100000                     // x |= x >> 8;
x = 0010 0010 0010 0010                   // x |= x >> 4;
x = 00 10 10 10 10 10 10 10               // x |= x >> 2;
x = 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1       // x |= x >> 1;

當然，細看最後一行 return，會發現有點冗長，最後經過 JoshuaLee0321 提醒用 x + 1 其實就能取代 (x ^ (x >> 1)) << 1

接著回到老師給出的 snippets

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 >> AAAA;
    x |= x >> 16;
    x |= x >> BBBB;
    return CCCC;
}

可以發現與我先前的程式相似，只是 bottom-up 和 top-down 的差別，因此也能進一步把前 7 次 rshift 1 合併成

    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;

那這邊我發現一個小問題，就是雖然我們的目的是找出最接近且大於等於 2 的冪的值，但若輸入本身就是 2 的冪，那應該是要回傳自己還是 下一個冪 ?

uint64_t next_pow2(uint64_t x)
{
    uint8_t lo = 0, hi = 63;
    while (lo < hi) {
        uint8_t test = (lo + hi)/2;
        if (x < pow2(test)) { hi = test; }
        else if (pow2(test) < x) { lo = test+1; }
        else { return pow2(test); }
    }
    return pow2(lo);
}

我拿 next_pow2 跟 bitwise 的 next_pow2 比較

next_pow2(64)          // output = 64

// bitwise
next_pow2(64)          // output = 128

結果沒錯，兩個函式並不等價
根據我在 Linux Kernel 看到 next_pow2 的用法，我認為應該 2 的冪應該要回傳自己
因此將 bitwise 的 next_pow2 修改成如下：

    uint64_t y = x;
    ...
    return y == ((x+1) >> 1) && y ? y : x + 1;

這樣就可以回傳本來是冪次的 x

參考 yanjiew1 的程式說明後，發現有較簡單的作法，也就是先將輸入的 x 減 1 後，再去做 set，這樣就可以讓最後的結果維持一樣

    x--;
    ...
    return x + 1;

用 __builtin_clzl 改寫

int __builtin_clz (unsigned int x)
int __builtin_clzl (unsigned long)

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

__builtin_clzl 會回傳最左邊的 1 其前面有幾個 0，因此我只要把 1 左移 64 - n 個 bit 就可以得到答案了

同時也注意到 __builtin_clzl 可能會有 undefined behavior，所以我們要先處理 x = 0 的情況

uint64_t next_pow2(uint64_t x)
{
    if (!x)
        return 1;
    if (!(x & (x - 1)))
        return x;
    return 1 << (64 - __builtin_clzl(x));
}

Linux 核心原始程式碼類似的使用案例

在 Dec 17 2014 之前的 commits，我們可以在 util.h 找到 next_pow2 的 definition

這裡的 next_pow2_l 使用條件編譯的方式增加了對 unsigned long 的支援

static inline unsigned next_pow2(unsigned x)
{
	if (!x)
		return 1;
	return 1ULL << (32 - __builtin_clz(x - 1));
}

static inline unsigned long next_pow2_l(unsigned long x)
{
#if BITS_PER_LONG == 64
	if (x <= (1UL << 31))
		return next_pow2(x);
	return (unsigned long)next_pow2(x >> 32) << 32;
#else
	return next_pow2(x);
#endif
}

而在之後，這兩個函式被 roundup_pow_of_two 取代，其中有提到 fls_long 是用來找從 MSB 開始出現第一個 1 的位置，而 fls_long 的實作中也可以見到 clz 的身影
linux/include/linux/bitops.h
額外參考資料：linux2021 彙整學員們的作業成果














static inline __attribute__((const))
unsigned long __roundup_pow_of_two(unsigned long n)
{
	return 1UL << fls_long(n - 1);
}

#define roundup_pow_of_two(n)			\
(						\
	__builtin_constant_p(n) ? (		\
		(n == 1) ? 1 :			\
		(1UL << (ilog2((n) - 1) + 1))	\
				   ) :		\
	__roundup_pow_of_two(n)		\
 )

注意到，roundup_pow_of_two 在第 10 行多做一層判斷，也就是當 n = 1 時，讓值直接為 1，而不繼續呼叫 ilog2((n) - 1) 來處理，猜測原因除了減少函式執行的 clock cycles 數外，也避免了 __builtin_clzll 輸入為 0 的情況

#define ilog2(n) \
( \
	__builtin_constant_p(n) ?	\
	((n) < 2 ? 0 :			\
	 63 - __builtin_clzll(n)) :	\
	(sizeof(n) <= 4) ?		\
	__ilog2_u32(n) :		\
	__ilog2_u64(n)			\
 )

在應用方面比如說 drivers/md/raid5.c 中的 raid5_store_stripe_size，他在裡面就有檢查 new 是否為 2 的冪次方大小

if (new % DEFAULT_STRIPE_SIZE != 0 ||
		new > PAGE_SIZE || new == 0 ||
		new != roundup_pow_of_two(new))
	return -EINVAL;

引用 chatgpt 的解釋

raid5_store_stripe_size() 是 Linux 核心中用於處理 RAID5 塊裝置儲存條帶大小的函式。RAID5 是一種磁碟陣列技術，透過將資料條帶化（striping）儲存在多個磁碟中，並使用奇偶校驗（parity）實現資料冗餘和容錯。

該函式的作用是將使用者傳入的儲存條帶大小值（stripe_size）儲存在 RAID5 塊裝置相關的結構體中，從而影響磁碟陣列的讀寫效能和空間利用效率。具體來說，該函式會檢查儲存條帶大小值是否符合一定的規範，例如必須是 2 的冪次方，且不能小於硬體支援的最小條帶大小等。如果輸入的值不符合要求，函式將返回錯誤碼，否則將更新 RAID5 塊裝置結構體中的儲存條帶大小資訊。

編譯器能否產生對應的 x86 指令

$ gcc -O2 -std=c99 -S test1.c

可以看到第 12 行有 bsr 指令出現





















next_pow2:
.LFB26:
	.cfi_startproc
	endbr64
	movl	$1, %eax
	testq	%rdi, %rdi
	je	.L10
	leaq	-1(%rdi), %rdx
	movq	%rdi, %rax
	testq	%rdi, %rdx
	je	.L10
	bsrq	%rdi, %rax
	movl	$64, %ecx
	xorq	$63, %rax
	subl	%eax, %ecx
	movl	$1, %eax
	sall	%cl, %eax
	cltq
.L10:
	ret
	.cfi_endproc

測驗二

解釋程式碼運作原理

LeetCode 1680. Concatenation of Consecutive Binary Numbers
給定一整數 n，回傳將 1 到 n 的二進位表示法依序串接在一起所得到的二進位字串，其所代表的十進位數字 mod \(10^9 + 7\) 之值。

想法：
- 每次左移 n 個 bit(s)
- 然後跟要 concate 的數字做 OR operation

舉例：concate 1, 2, 3

        |
        v
0000 0000                  // 初始值

       |
       v
0000 0000                  // 左移 n bit(s)，這時 n = 1

0000 0001                  // 跟 1 做 OR

     |
     v
0000 0100                  // 左移 n bit(s)，這時 n = 2

0000 0110                  // 跟 2 做 OR

  |
  v
0001 1000                  // 左移 n bit(s)，這時 n = 2

0001 1011                  // 跟 3 做 OR

輸出 27

該怎麼決定 n
- 可以發現，當要 concate 2 的冪的時候，n 會比前一次多位移 1
- 而非 2 的冪的時候，n 維持前一次的值即可

回到老師給出的 snippets













    for (int i = 1; i <= n; i++) {
        /* removing the rightmost set bit
         * e.g. 100100 -> 100000
         *      000001 -> 000000
         *      000000 -> 000000
         * after removal, if it is 0, then it means it is power of 2
         * as all power of 2 only contains 1 set bit
         * if it is power of 2, we increase the bit length
         */
        if (!(DDDD))
            len++;
        ans = (i | (EEEE)) % M;
    }

可以看到第 10 行用來判斷 i 是否為 2 的冪，是的話，長度 len 加 1
而 12 行用來做位移然後相加，最後處理 mod \(10^9 + 7\)

使用 __builtin_{clz,ctz,ffs} 改寫

int __builtin_ffs (int x);
int __builtin_clz (unsigned int x);
int __builtin_ctz (unsigned int x);

/* __builtin_ffs(x) */
Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

/* __builtin_clz(x) */
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

/* __builtin_ctz(x) */
Returns the number of trailing 0-bits in x, starting at the least significant bit position. If x is 0, the result is undefined.

找出 i 前面連續 0 的個數與後面連續 0 的個數相加是否為 31，如果為 31 代表 i 為 2 的冪次方 ; 接著使用 __builtin_ffs 找到需要位移的長度

    for (int i = 1; i <= n; i++) {
        if (__builtin_clz(i) + __builtin_ctz(i) == 31)
            len = __builtin_ffs(i);
        ans = (i | (ans << len)) % M;
    }

參考 joshualee0321 的作法，發現可以只使用 __builtin_clz 便直接得出 len 的大小，同時也減少使用 branch 的開銷

    for (int i = 1; i <= n; i++) {
        len = 32 - __builtin_clz(i);
        ans = (i | (ans << len)) % M;
    }

改進 mod \(10^9 + 7\) 的運算

在上述程式碼中，i | (ans << len) 的結果有可能在做 modulo M 之前就已經 overflow 了，雖然可能不會造成計算上的錯誤，但讓程式存在 overflow 風險並不是一件好事，因此根據 modulo 的性質

\((A + B) \% M = (A \% M + B \% M) \% M\)
\((A \ast B) \% M = (A \% M \ast B \% M) \% M\)

可以將程式碼改成如下：

    ans = ((i % M) | ((ans % M) << (len % M))) % M;

測驗三

解釋程式碼原理

size_t count_utf8(const char *buf, size_t len)
{
    const int8_t *p = (const int8_t *) buf;
    size_t counter = 0;
    for (size_t i = 0; i < len; i++) {
        /* -65 is 0b10111111, anything larger in two-complement's should start
         * new code point.
         */
        if (p[i] > -65)
            counter++;
    }
    return counter;
}

(待解釋)

size_t swar_count_utf8(const char *buf, size_t len)
{
    const uint64_t *qword = (const uint64_t *) buf;
    const uint64_t *end = qword + len >> 3;

    size_t count = 0;
    for (; qword != end; qword++) {
        const uint64_t t0 = *qword;
        const uint64_t t1 = ~t0;
        const uint64_t t2 = t1 & 0x04040404040404040llu;
        const uint64_t t3 = t2 + t2;
        const uint64_t t4 = t0 & t3;
        count += __builtin_popcountll(t4);
    }

    count = (1 << 3) * (len / 8)  - count;
    count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

    return count;
}

(待解釋)

比較 SWAR 和原本的實作效能落差

可以使用 perf 比較效能
(待解釋)

在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼，探討其原理，並指出可能的改進空間

可以在 unicode.c 中找到有關 unicode 相關的字串處理程式碼

static unicode_t get_utf16_char(const uint8_t *str_i, int str_i_max_len,
				int str_i_idx, int u_ch, unicode_t *ret)
{
	unicode_t c;
	int start_idx = str_i_idx;

	/* Expand OSTA compressed Unicode to Unicode */
	c = str_i[str_i_idx++];
	if (u_ch > 1)
		c = (c << 8) | str_i[str_i_idx++];
	if ((c & SURROGATE_MASK) == SURROGATE_PAIR) {
		unicode_t next;

		/* Trailing surrogate char */
		if (str_i_idx >= str_i_max_len) {
			c = UNICODE_MAX + 1;
			goto out;
		}

		/* Low surrogate must follow the high one... */
		if (c & SURROGATE_LOW) {
			c = UNICODE_MAX + 1;
			goto out;
		}

		WARN_ON_ONCE(u_ch != 2);
		next = str_i[str_i_idx++] << 8;
		next |= str_i[str_i_idx++];
		if ((next & SURROGATE_MASK) != SURROGATE_PAIR ||
		    !(next & SURROGATE_LOW)) {
			c = UNICODE_MAX + 1;
			goto out;
		}

		c = PLANE_SIZE +
		    ((c & SURROGATE_CHAR_MASK) << SURROGATE_CHAR_BITS) +
		    (next & SURROGATE_CHAR_MASK);
	}
out:
	*ret = c;
	return str_i_idx - start_idx;
}

測驗四

解釋程式碼原理

首先觀察老師給出的範例

    for (; x > 0; x <<= 1) {
        if (!(x & 0x8000))
            return false;
    }
    return true;

什麼時候 return false
- 當 (\(x\) & 0x8000) 為 0 時
- \(x\) 為 0xxx … xxxx (binary format 開頭為 0)
  - 其中 X 不全為 0，否則跳出迴圈
什麼時候 return true
- 若 \(x\) 跳出迴圈且為 0，則 return true
for 迴圈作用
- 將 \(x\) 往左移 1 位，但因為 \(x\) 為 uint16_t，因此作用相當於在 LSB 補一 0，而 MSB 捨去 1 個 bit
- 像是 1100 0000 0000 0000 的下一次 iteration 就變成 1000 0000 0000 0000

接著看到測驗-4 老師給出的 pattern 中，全部的數值的 binary format 其開頭皆為連續的 1-bit，而之後的 bits 皆為 0

這就是我們需要的 pattern

要如何精簡以上程式碼，老實說我真想不到，因此只能看圖說故事

bool is_pattern(uint16_t x)
{
    const uint16_t n = -x;
    return (n ^ x) < x;
}

首先，-x 會被先後操作 NOT x 跟 +1，也就是 x 的 2 補數，在這個情況下，x 中的最靠 LSB 側的 1-bit 會維持 set，該 bit 左側皆會被作 NOT，如：

x = 1111 1100 0000 0000 , -x = 0000 0100 0000 0000
x = 1111 0010 0010 0000 , -x = 0000 1101 1110 0000
x = 0000 0010 0000 0000 , -x = 1111 1110 0000 0000

這邊發現，變成 pow of two 的 n，在跟 x 作 XOR 後，the set bit 左側的 bits 都會是 1，而 the set bit 及其右側的 bits 皆為 0，因此 x 總是會比 (n ^ x) 多 1

          the set bit
              |
              v
    n = 0000 0100 0000 0000
    x = 1111 1100 0000 0000
n ^ x = 1111 1000 0000 0000

同理，非 pow of two 的 n，在跟 x 作 XOR 後，the set bit 左側的 bits 都會是 1，這時後 x 總是會比 (n ^ x) 小

                the set bit
                    |
                    v
    n = 0000 1101 1110 0000
    x = 1111 0010 0010 0000
n ^ x = 1111 1111 1100 0000


           the set bit
               |
               v
    n = 1111 1110 0000 0000
    x = 0000 0010 0000 0000
n ^ x = 1111 1100 0000 0000

因此根據以上解釋，我認為程式碼也可以修改如下：
直接判斷 n 是否為 pow of two

int __builtin_popcount (unsigned int x);

Returns the number of 1-bits in x.

bool is_pattern(uint16_t x)
{
    const uint16_t n = -x;
    return __builtin_popcount(n) == 1;
}

或是確認連續 1 和連續 0 是否佔滿 16 個 bits
最後再對 0 作額外判斷

bool is_pattern(uint16_t x)
{
    return x ? (__builtin_clz(~x) + __builtin_ctz(x)) == 16 : 0;
}

在 Linux 核心原始程式碼找出上述 bitmask 及產生器

在 bits.h 可以找到 GENMASK macro 的定義

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

假設 BITS_PER_LONG = 32，則 GENMASK(6, 4) 運作如下

首先利用 GENMASK_INPUT_CHECK 檢查 h 和 l 是否合法 (h \(\ge\) l)
~UL(0) = 1111 1111 1111 1111 1111 1111 1111 1111
UL(1) << 4 = 0000 0000 0000 0000 0000 0000 0001 0000
~UL(0) - (UL(1) << 4) + 1 = 1111 1111 1111 1111 1111 1111 1111 0000
~UL(0) >> (BITS_PER_LONG - 1 - 6) = 0000 0000 0000 0000 0000 0000 0111 1111
最後，將 4 和 5 的結果做 AND \(\Rightarrow\) 0000 0000 0000 0000 0000 0000 0111 0000

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

2023q1 Homework2 (quiz2)

測驗一

解釋程式碼原理

用 __builtin_clzl 改寫

Linux 核心原始程式碼 類似的使用案例

編譯器能否產生對應的 x86 指令

測驗二

解釋程式碼運作原理

使用 __builtin_{clz,ctz,ffs} 改寫

改進 mod \(10^9 + 7\) 的運算

測驗三

解釋程式碼原理

比較 SWAR 和原本的實作效能落差

在 Linux 核心原始程式碼找出 UTF-8 和 Unicode 相關字串處理的程式碼，探討其原理，並指出可能的改進空間

測驗四

解釋程式碼原理

在 Linux 核心原始程式碼找出上述 bitmask 及產生器

Read more

筆記

Leetcode

Assignment3: Single-cycle RISC-V CPU

Assignment2: RISC-V Toolchain

Linux 核心原始程式碼類似的使用案例