2023q1 Homework2 (quiz2)

contributed by < LiChiiiii>

測驗題目：quiz2

測驗一

運作原理

考慮 next_pow2 可針對給定無號 64 位元數值 x，找出最接近且大於等於 2 的冪的值，例如:

• next_pow2(7) = 8
• next_pow2(13) = 16
• next_pow2(42) = 64

最初想法是將 x 左移 1 後，最高位元的 1 保留下來，其餘設定為 0 ，根據測驗一的題目實作，利用 shift 和 or 將最高位元的 1 至最低位元的 bit 皆設定為 1 ，最後回傳 x+1 即為答案。
Example:

x   = 0000011001000000
x   = 0000011111111111
x+1 = 0000100000000000

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

發現：如果 x 剛好是 2 的冪，那麼應該要回傳 x 本身，但上述程式碼不會回傳 x 。
Example:

x   = 0000010000000000
x   = 0000011111111111
x+1 = 0000100000000000

因此可加上條件式判斷 x 是否剛好是 2 的冪，避免不必要的操作。

if((x & (x - 1)) == 0) return x;

用 __builtin_clzl 改寫

__builtin_clzl(x) 回傳 x 中有多少個 leading 0-bits ，當64 減去 __builtin_clzl(x) 即可找到最高位元的位置。

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

在 Linux 核心原始程式碼找出類似的使用案例並解釋

在 The Linux Kernel API 中找到 __roundup_pow_of_two 實作。其原始程式碼在 linux/log2.h 。

__roundup_pow_of_two

給定一個無號整數 n，回傳該值最接近且大於等於 2 的冪的值，若 n 為 2 的冪則回傳 n。

unsigned long __roundup_pow_of_two(unsigned long n)
{
	return 1UL << fls_long(n - 1);
}

:stars: fls_long 用來找從最高位元開始連續的 0 的個數，也就是找到出現第一個 1 的位置。linux/bitops.h

static inline unsigned fls_long(unsigned long l)
{
	if (sizeof(l) == 4)
		return fls(l);
	return fls64(l);
}

如果 l 是一個 32 位元的整數（即sizeof(l) == 4），則調用 fls 函數。
如果 l 是一個 64 位元的整數（即sizeof(l) > 4），則調用 fls64 函數。

__roundup_pow_of_two 使用案例

在 commit 8758768 可以看到原本的 i40iw_qp_round_up 被替換成 roundup_pow_of_two。

i40iw_qp_round_up 實作概念與 next_pow2 相同，在 for loop 的每次循環中，將 scount 乘以2，然後將 wqdepth 右移 scount 位，並將結果與 wqdepth 進行位元或運算，這樣的效果是將最高位元的 1 至最低位元的 bit 皆設定為 1 ，其時間複雜度為 O(log wqdepth)。

roundup_pow_of_two 是將最高位元開始連續的 0 的個數作為 unsigned long 1 向左移的次數，其時間複雜度為 O(1)。

-/**
-  * i40iw_qp_roundup - return round up QP WQ depth
-  * @wqdepth: WQ depth in quantas to round up
-  */
- static int i40iw_qp_round_up(u32 wqdepth)
- {
- 	int scount = 1;
- 	for (wqdepth--; scount <= 16; scount *= 2)
- 		wqdepth |= wqdepth >> scount;
- 	return ++wqdepth;
- }

enum i40iw_status_code i40iw_get_sqdepth(u32 sq_size, u8 shift, u32 *sqdepth)
{
-    *sqdepth = i40iw_qp_round_up((sq_size << shift) + I40IW_SQ_RSVD);
+    *sqdepth = roundup_pow_of_two((sq_size << shift) + I40IW_SQ_RSVD);

    ...
}

當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？

x86 中有一條稱為 bsrq 的指令，可以實現尋找最高位元 1 的位置的功能，其運作方式與 clz 函式類似。編譯器可以將 clz 函式轉換為 bsrq 指令來實現對應的功能。
實際執行 cc -O2 -std=c99 -S next_pow2.c ，可在 next_pow2.s 第 22 行看到 bsrq 指令。

next_pow2.s

    .file   "next_pow2.c"
    .text
    .p2align 4
    .globl  next_pow2
    .type   next_pow2, @function
next_pow2:
.LFB0:
    .cfi_startproc
    endbr64
    movl    $1, %eax
    testq   %rdi, %rdi
    je  .L1
    leaq    -1(%rdi), %rdx
    movq    %rdi, %rax
    testq   %rdi, %rdx
    jne .L8
.L1:
    ret
    .p2align 4,,10
    .p2align 3
.L8:
    bsrq    %rdi, %rax
    movl    $64, %ecx
    xorq    $63, %rax
    subl    %eax, %ecx
    movl    $1, %eax
    salq    %cl, %rax
    ret
    .cfi_endproc
.LFE0:
    .size   next_pow2, .-next_pow2
    .ident  "GCC: (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0"
    .section    .note.GNU-stack,"",@progbits
    .section    .note.gnu.property,"a"
    .align 8
    .long   1f - 0f
    .long   4f - 1f
    .long   5
0:
    .string "GNU"
1:
    .align 8
    .long   0xc0000002
    .long   3f - 2f
2:
    .long   0x3
3:
    .align 8
4:   

:stars: BSR (Bit Scan Reverse) 指令和 bsrq 指令差別在哪裡？

BSR (Bit Scan Reverse) 指令和 bsrq 指令都是在 x86 架構的指令集中的位元運算指令，它們的主要區別在於操作數的大小。

具體而言，BSR 指令是用於 16 位元或 32 位元操作數的位元運算，而 bsrq 指令是用於 64 位元操作數的位元運算。因此，它們分別可以從指定的操作數中尋找最高位元 (MSB) 的位置並將其傳回。

chatGPT

測驗二

運作原理

給定一整數 n ，回傳將 1 到 n 的二進位表示法依序串接在一起所得到的二進位字串，其所代表的十進位數字 mod

${10}^9+7$ 之值。

len ：用來紀錄整數 i 之 bit 長度，也就是要左移的位元數。

迴圈會從 i = 1 開始執行至 i = n，也就是說， bit 長度會越來越長。當 i 為 2 的冪時，代表進位到下一個 bit ， 因此執行 len++ 增加 bit 長度，而每次循環會將前面迴圈的結果向左移 len 個位元數，利用 or 與 i 合併後，再做 mod M 的運算來避免 overflow 。

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0; /* the bit length to be shifted */
    /* use long here as it potentially could overflow for int */
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!(i & (i-1)))
            len++;
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

嘗試使用 __builtin_{clz,ctz,ffs} 改寫，並改進

$mod$

${10}^9+7$ 的運算

int __builtin_ffs (int x)

Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

int __builtin_ctz (unsigned int 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.

int __builtin_clz (unsigned int 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.

• 想法： 使用函式計算最高位元開始算起的 0 之個數，及最低位元開始算啟的 0 之個數，若是 2 的冪，則兩者 0 之個數相加應為 31 （因為回傳型態為 int 是 32 bits）
• 實作： 將 __builtin_clz(i) + __builtin_ctz(i) = 31 作為 2 的冪之條件式判斷。

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0; 
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (__builtin_clz(i)+ __builtin_ctz(i) == 31)
            len++;
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

以上程式碼改寫並沒有增進效能，於是又想了其他改寫方式。

• 想法： 程式碼中的條件式是為了確定左移的位元數，那是否可以直接計算需左移的位元數，以減少分支存在？
• 實作： __builtin_clz 會回傳從最高位元開始連續的 0 之個數，將 32 bits 減去 __builtin_clz(i) 即為需左移的位元數。

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    long ans = 0;
    for (int i = 1; i <= n; i++){
        ans = (i | (ans << (32 - __builtin_clz(i)))) % M;
    }

    return ans;
}

測驗三

運作原理

UTF-8 字元可由 1, 2, 3, 4 個位元組構成。其中單一位元組的 UTF-8 由 ASCII 字元構成，其 MSB 必為 0。
UTF-8 的多位元組字元是由一個首位元組和 1, 2 或 3 個後續位元組所構成。首位元組可以表示其 UTF-8 字元是幾個位元組所組成，舉例來說，2 bytes 的字元其首位元組之最高位元開始存在連續 2 個 1，下表為多位元組字元的規則：

	UTF-8
ASCII	0xxx.xxxx
2 bytes	110x.xxxx 10xx.xxxx
3 bytes	1110.xxxx 10xx.xxxx 10xx.xxxx

以下程式碼使用了 SWAR（SIMD Within A Register）算法，計算給定的 UTF-8 編碼的字串中字元數量。
程式碼中使用 for 迴圈來一次處理 8 bytes ，所以先透過 len>>3 （也就是 len/8）來計算總共有幾個 8 bytes ，接著在迴圈中將 not bit6 and bit7 這個想法實作，並透過 __builtin_popcount 計算有多少 1，來紀錄有幾個 continuation byte （也就是 10xx.xxxx），最後將 continuation byte 的數量從總字串長度中減去，即可確定字元數量。

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

第 16 行：利用 (1 << 3) * (len / 8) 得到總字串長度，再減去 continuation byte 的數量。

第 17 行：如果 len & 7 不等於 0，則說明 len 不是 8 的倍數，此時調用 count_utf8 函數計算在迴圈內未被處理到的 bytes ，回傳值再加入 count 中。

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

swar_count_utf8 中的循環次數比 count_utf8 少，因為對於一次處理 8 bytes 的長度範圍，使用位元運算進行計數，減少了循環的次數。而 count_utf8 則需要遍歷每個 byte 進行判斷，增加了循環的次數。

• 實驗設計：亂數產生長度為 1000000 的字串實作在 swar_count_utf8 和 count_utf8 ， 再利用 perf 重複執行 100 次並計算 instructions 和 cycles 的數量，從以下結果可以明顯看到 count_utf8 使用到較多的指令數量，花費較多的運行時間。

$sudo perf stat --repeat 100 -e instructions,cycles ./swar_count_utf8

 Performance counter stats for './swar_count_utf8' (100 runs):

         9058,4543      instructions              #    1.47  insn per cycle           ( +-  0.00% )
         6114,8381      cycles                                                        ( +-  0.29% )

         0.0167870 +- 0.0000631 seconds time elapsed  ( +-  0.38% )

$sudo perf stat --repeat 100 -e instructions,cycles ./count_utf8

 Performance counter stats for './count_utf8' (100 runs):

         9609,5870      instructions              #    1.44  insn per cycle           ( +-  0.00% )
         6602,1809      cycles                                                        ( +-  0.56% )

         0.0175909 +- 0.0000975 seconds time elapsed  ( +-  0.55% )

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

在 /fs/unicode/utf8-norm.c 找到 UTF-8 和 Unicode 相關字串處理的程式碼。
utf8byte() 是一個 UTF-8 字串的解碼器，用於從 UTF-8 字符串中提取規範化形式的單個字節，並處理了 UTF-8 字符串的解碼和解析過程中可能出現的各種特殊情況。這段程式碼存在一些重複的部分，可以將重複部分抽取出來，另外建立函式來改進可讀性。

utf8byte(struct utf8cursor *u8c)

int utf8byte(struct utf8cursor *u8c)
{
	utf8leaf_t *leaf;
	int ccc;

	for (;;) {
		/* Check for the end of a decomposed character. */
		if (u8c->p && *u8c->s == '\0') {
			u8c->s = u8c->p;
			u8c->p = NULL;
		}

		/* Check for end-of-string. */
		if (!u8c->p && (u8c->len == 0 || *u8c->s == '\0')) {
			/* There is no next byte. */
			if (u8c->ccc == STOPPER)
				return 0;
			/* End-of-string during a scan counts as a stopper. */
			ccc = STOPPER;
			goto ccc_mismatch;
		} else if ((*u8c->s & 0xC0) == 0x80) {
			/* This is a continuation of the current character. */
			if (!u8c->p)
				u8c->len--;
			return (unsigned char)*u8c->s++;
		}

		/* Look up the data for the current character. */
		if (u8c->p) {
			leaf = utf8lookup(u8c->um, u8c->n, u8c->hangul, u8c->s);
		} else {
			leaf = utf8nlookup(u8c->um, u8c->n, u8c->hangul,
					   u8c->s, u8c->len);
		}

		/* No leaf found implies that the input is a binary blob. */
		if (!leaf)
			return -1;

		ccc = LEAF_CCC(leaf);
		/* Characters that are too new have CCC 0. */
		if (u8c->um->tables->utf8agetab[LEAF_GEN(leaf)] >
		    u8c->um->ntab[u8c->n]->maxage) {
			ccc = STOPPER;
		} else if (ccc == DECOMPOSE) {
			u8c->len -= utf8clen(u8c->s);
			u8c->p = u8c->s + utf8clen(u8c->s);
			u8c->s = LEAF_STR(leaf);
			/* Empty decomposition implies CCC 0. */
			if (*u8c->s == '\0') {
				if (u8c->ccc == STOPPER)
					continue;
				ccc = STOPPER;
				goto ccc_mismatch;
			}

			leaf = utf8lookup(u8c->um, u8c->n, u8c->hangul, u8c->s);
			if (!leaf)
				return -1;
			ccc = LEAF_CCC(leaf);
		}

		/*
		 * If this is not a stopper, then see if it updates
		 * the next canonical class to be emitted.
		 */
		if (ccc != STOPPER && u8c->ccc < ccc && ccc < u8c->nccc)
			u8c->nccc = ccc;

		/*
		 * Return the current byte if this is the current
		 * combining class.
		 */
		if (ccc == u8c->ccc) {
			if (!u8c->p)
				u8c->len--;
			return (unsigned char)*u8c->s++;
		}

		/* Current combining class mismatch. */
ccc_mismatch:
		if (u8c->nccc == STOPPER) {
			/*
			 * Scan forward for the first canonical class
			 * to be emitted.  Save the position from
			 * which to restart.
			 */
			u8c->ccc = MINCCC - 1;
			u8c->nccc = ccc;
			u8c->sp = u8c->p;
			u8c->ss = u8c->s;
			u8c->slen = u8c->len;
			if (!u8c->p)
				u8c->len -= utf8clen(u8c->s);
			u8c->s += utf8clen(u8c->s);
		} else if (ccc != STOPPER) {
			/* Not a stopper, and not the ccc we're emitting. */
			if (!u8c->p)
				u8c->len -= utf8clen(u8c->s);
			u8c->s += utf8clen(u8c->s);
		} else if (u8c->nccc != MAXCCC + 1) {
			/* At a stopper, restart for next ccc. */
			u8c->ccc = u8c->nccc;
			u8c->nccc = MAXCCC + 1;
			u8c->s = u8c->ss;
			u8c->p = u8c->sp;
			u8c->len = u8c->slen;
		} else {
			/* All done, proceed from here. */
			u8c->ccc = STOPPER;
			u8c->nccc = STOPPER;
			u8c->sp = NULL;
			u8c->ss = NULL;
			u8c->slen = 0;
		}
	}
}

測驗四

運作原理

此程式碼是為了檢查從最高位元開始是否只包含一段連續的 1，使用一個 for 迴圈不斷的左移 x ，並檢查最高位元是否為 1 ，直到 x 等於零就結束迴圈回傳 true ，否則繼續左移 x ，若發現最高位元為 0 即回傳 false 。

#include <stdint.h>
#include <stdbool.h>

bool is_pattern(uint16_t x)
{
    if (!x)
        return 0;

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

    return true;
}

改寫成精簡的程式碼，先計算 x 的 2 補數 （ ~x + 1 ） ，兩者做 XOR 來保證高位元的值為連續的 1 ，即可在最後比較大小來檢查是否特定樣式。

bool is_pattern(uint16_t x)
{
    const uint16_t n = ~x + 1;
    return (n ^ x) < x;
}

Example:

x        = 1111110000000000
~x+1     = 0000010000000000
x^(~x+1) = 1111100000000000 < x    // 符合特定樣式

x        = 1101110000000000
~x+1     = 0010010000000000
x^(~x+1) = 1111100000000000 > x    // 不符合特定樣式

在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇

參見 Data Structures in the Linux Kernel 找到 BITMAP_FIRST_WORD_MASK 和 BITMAP_LAST_WORD_MASK 實作，其原始程式碼在 linux/bitmap.h 。

BITMAP_FIRST_WORD_MASK

此函式用來獲得從最高位元開始包含連續 1 的 mask ，參數 start 代表從最低位元開始算起含有 0 的個數，其餘為 1 。
將 0xFFFFFFFF 左移 (start) & (BITS_PER_LONG - 1) ，其中 BITS_PER_LONG 是一個常量，表示 unsigned long 型別的位數，通常是 32 位元或 64 位元，取決於機器的架構。

#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))

Example:

BITMAP_FIRST_WORD_MASK(4) = 0xFFFFFFF0
/* 以下為計算過程 */  
~0UL << (4) & (32 - 1))
0xFFFFFFFF << (4 & 31)
0xFFFFFFFF << 4

BITMAP_LAST_WORD_MASK

此函式用來獲得從最低位元開始包含連續 1 的 mask ，參數 nbits 代表從最低位元開始算起含有 1 的個數，其餘為 0 。

#define BITMAP_LAST_WORD_MASK(nbits) (~0UL >> (-(nbits) & (BITS_PER_LONG - 1)))

假設 BITS_PER_LONG 為 32 ，那麼實作就是將 0xFFFFFFFF 右移 32 - nbits 。

Example:

BITMAP_LAST_WORD_MASK(4) = 0x0000000F
/* 以下為計算過程 */  
~0UL >> (-(4) & (32 - 1))
0xFFFFFFFF >> (-4 & 31)
0xFFFFFFFF >> 28

實際應用

這是一個用於清除 bitmap 指定範圍內的位元數的函數

map : 指向 bitmap 的 pointer
start : bitmap 中需要被清除的第一個 bit 的位置
len : 需要被清除的 bit 的數量

void __bitmap_clear(unsigned long *map, unsigned int start, int len)
{
	unsigned long *p = map + BIT_WORD(start);
	const unsigned int size = start + len;
	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);

	while (len - bits_to_clear >= 0) {
		*p &= ~mask_to_clear;
		len -= bits_to_clear;
		bits_to_clear = BITS_PER_LONG;
		mask_to_clear = ~0UL;
		p++;
	}
	if (len) {
		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
		*p &= ~mask_to_clear;
	}
}