# 2023q1 Homework2 (quiz2)
contributed by < `LiChiiiii`>

>測驗題目：[quiz2](https://hackmd.io/@sysprog/linux2023-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](https://www.kernel.org/doc/html/latest/core-api/kernel-api.html#c.is_power_of_2) 中找到 `__roundup_pow_of_two` 實作。其原始程式碼在 [linux/log2.h](https://github.com/torvalds/linux/blob/master/include/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);
}

:::info
:stars: `fls_long` 用來找從最高位元開始連續的 0 的個數，也就是找到出現第一個 1 的位置。[linux/bitops.h](https://github.com/torvalds/linux/blob/master/include/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](https://github.com/torvalds/linux/commit/8758768ad8aa9fc0d56417315dec65b610fc3a21) 可以看到原本的 `i40iw_qp_round_up` 被替換成 `roundup_pow_of_two`。

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

> [color=lightgreen] `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` 指令。
:::spoiler 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:   

:::
>
:::info
:stars: `BSR (Bit Scan Reverse)` 指令和 `bsrq` 指令差別在哪裡？
>BSR (Bit Scan Reverse) 指令和 bsrq 指令都是在 x86 架構的指令集中的位元運算指令，它們的主要區別在於操作數的大小。
>
>具體而言，BSR 指令是用於 16 位元或 32 位元操作數的位元運算，而 bsrq 指令是用於 64 位元操作數的位元運算。因此，它們分別可以從指定的操作數中尋找最高位元 (MSB) 的位置並將其傳回。
>
> [name=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`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 計算有多少 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](https://github.com/torvalds/linux/blob/master/fs/unicode/utf8-norm.c) 找到 UTF-8 和 Unicode 相關字串處理的程式碼。
`utf8byte()` 是一個 UTF-8 字串的解碼器，用於從 UTF-8 字符串中提取規範化形式的單個字節，並處理了 UTF-8 字符串的解碼和解析過程中可能出現的各種特殊情況。這段程式碼存在一些重複的部分，可以將重複部分抽取出來，另外建立函式來改進可讀性。
:::spoiler `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](https://0xax.gitbooks.io/linux-insides/content/DataStructures/linux-datastructures-3.html) 找到 `BITMAP_FIRST_WORD_MASK` 和 `BITMAP_LAST_WORD_MASK` 實作，其原始程式碼在 [linux/bitmap.h](https://github.com/torvalds/linux/blob/16f73eb02d7e1765ccab3d2018e0bd98eb93d973/include/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;
	}
}