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

### 測驗 `1`
參照 [你所不知道的 C 語言: bitwise 操作](https://hackmd.io/@sysprog/c-bitwise#%E4%BD%A0%E6%89%80%E4%B8%8D%E7%9F%A5%E9%81%93%E7%9A%84-C-%E8%AA%9E%E8%A8%80-bitwise-%E6%93%8D%E4%BD%9C)，考慮 next_pow2 可針對給定無號 64 位元數值 x，找出最接近且大於等於 2 的冪的值，例如:
- `next_pow2(7)` = 8
- `next_pow2(13)` = 16
- `next_pow2(42)` = 64

測驗題題目中提到的一種實作方式為:

#include <stdint.h>
static inline uint64_t pow2(uint8_t e) { return ((uint64_t)1) << e; }

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

它採用的方法是先取 `uint64_t` 的最小與最大的 2 的冪的值，分別以次冪數形式儲存在 `lo` 跟 `hi` 中，也就是 $2^{lo} = 2^0$ 與 $2^{hi} = 2^{63}$ ，並且將 `x` 與 `test = (lo + hi)/2` 次冪數的值 $2^{test}$ 做比較，若 `x` 比較小，則將上限次冪 `hi` 縮小成 `test` 的值，反之，若 `x` 比較大，則將下限次冪 `lo` 增加到 `test + 1` 的值，最後的回傳結果有兩種
1. `return pow2(test)`
當 `x` 剛好等於 $2^{test}$ 時，則直接回傳 $2^{test}$
2. `return pow2(lo)`
當 `x` 並不是 2 的冪的值，則回傳最接近且大於 `x` 的 2 的冪的值，即 $2^{lo}$

而題目提到另一種使用位元運算的實作分支，它所做的事情是以擁有最大位元的 `1` 為界，向後「填補」位元為 `0` 的位元

x = 0010000000000000
x = 0011000000000000
x = 0011110000000000
x = 0011111111000000
x = 0011111111111111

當「填補」的動作完成後，為了符合預期，找出最接近且大於等於 2 的冪的值，可以進行以下操作

return x + 1;

則可以得到預期的結果

x = 0100000000000000 // x = 2^15  (in decimal)

欲在 64 位元的大小完成以上實作，嘗試改寫為以下:

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 = 8
    x |= x >> 16;
    x |= x >> 32; // BBBB = 32
    return x + 1; // CCCC = x + 1
}

舉例來說， 64 位元的 `x = 00100...0` 丟進 `next_pow2` 執行結束後，會得到 `00111...1 + 1 = 01000...0` ，換成十進位為 $2^{62}$ ，即為預期的輸出

:::success
延伸問題
1. 解釋上述程式碼原理，並用 [`__builtin_clzl`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫
> `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.
> `int __builtin_clzl (unsigned long)`
> Similar to `__builtin_clz` , except the argument type is unsigned long.
2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
3. 當上述 `clz` 內建函式已運用時，編譯器能否產生對應的 x86 指令？
> 提示: 可執行 `cc -O2 -std=c99 -S next_pow2.c` 並觀察產生的 `next_pow2.s` 檔案，確認 `bsrq` 指令 (表示 “[Bit Scan Reverse](https://c9x.me/x86/html/file_module_x86_id_20.html)”)
:::

1. 解釋上述程式碼原理，並用 `__builtin_clzl` 改寫

uint64_t next_pow2(uint64_t x)
{
    uint64_t num = __builtin_clzl(x);
    x >>= (64 - num);
    x = 1;
    x <<= (64 - num);
    return x;
}

int main() {
    uint64_t input = 128;
    printf("%lu\n", next_pow2(input - 1));
    return 0;
}

我的作法是使用 `__builtin_clzl` 取得 `x` 的領頭 0-bits 數量，間接得知最接近最高位元的 1-bit 所在的是第幾個位元，於是我使用右移位移運算子將左邊出現的第一個 1-bit 移至最低位元的右邊，也就是說我將所有 1-bits 清除，如下例

uint64_t x = 0010...01;  // num = 1
x >>= (64 - num);  // x = 0000...00

接著將 `x` 代 1 ，再將它左移至原本最左邊出現的 1-bit 的左邊一個位元

x = 1;  // x = 0000...01
x <<= (64 - num); // x = 0100...00

至此步驟已經實現了找出大於 `x` 的最小 2 的次冪，不過根據題意，當 `x` 剛好是 2 的次冪時，應回傳原本的數，當我正要開始思考判斷式該如何寫時，< [fewletter](https://hackmd.io/@fewletter/HJF4nKaCi#%E8%A7%A3%E9%87%8B%E4%B8%8A%E8%BF%B0%E7%A8%8B%E5%BC%8F%E7%A2%BC%E5%8E%9F%E7%90%86%EF%BC%8C%E4%B8%A6%E7%94%A8-__builtin_clzl-%E6%94%B9%E5%AF%AB) >提出了一個很棒的想法，我們看下面這行程式碼

next_pow2(input - 1)

`input` 是要丟入 `next_pow2()` 執行的 64 位元數值，若將 `input - 1` 丟入 `next_pow2()` 中執行，就可以達成前述的效果

2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋
我找到的類似應用是 Linux V4L2 ，它是一種用於攝影機的驅動程式，一些重要參數的設定都被包含在 V4L2 中，下方是部份的程式碼

void example_bitwise_usage(struct v4l2_format *fmt)
{
    // 檢查是否有 XRGB 格式的支援
    if ((fmt->fmt.pix.pixelformat & 0xFFFF) == ('X' | ('R' << 8) | ('G' << 16) | ('B' << 24))) {
        fmt->fmt.pix.pixelformat = V4L2_PIX_FMT_XRGB32;
    }
}

首先觀察 `if` 判斷式的 `==` 左邊， `fmt->fmt.pix.pixelformat` 代表像素格式的設定，因此這裡是在提取目前的格式設定。而 `==` 右邊則是 XRGB 的格式，`'x', 'R', 'G', 'B'` 個別代表透明度、紅、綠、藍色的像素格式識別碼，它們各佔有 8 bits ，總共有 32 bits 。若 `if` 判斷式滿足即表示目前的格式設定為 XRGB 格式，代表系統支援 XRGB ，則可將像素格式設定為 `V4L2_PIX_FMT_XRGB32`

3. 當上述 `clz` 內建函式已運用時，編譯器能否產生對應的 x86 指令？
> 提示: 可執行 `cc -O2 -std=c99 -S next_pow2.c` 並觀察產生的 `next_pow2.s` 檔案，確認 `bsrq` 指令
執行後產生的 `.s` 檔部份程式碼

next_pow2:
.LFB13:
	.cfi_startproc
	endbr64
	bsrq	%rdi, %rdi
	movl	$64, %ecx
	movl	$1, %eax
	xorq	$63, %rdi
	subl	%edi, %ecx
	salq	%cl, %rax
	ret
	.cfi_endproc

結果顯示有產生對應的 `bsrq` 指令

### 測驗 `2`

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0;
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!(i & (i - 1)))  // DDDD = i & (i - 1)
            len++;
        ans = (i | (ans << len)) % M;  // EEEE = ans << len
    }
    return ans;
}

`if` 判別式在 `for` 迴圈中的作用是判斷 `i` 是否為 2 的次冪，判別方式如下

i = 1000 // (8 in dec)
// so (i - 1) = 111

if (!(i & (i - 1))) == if (!(1000 & 111)) == if (true)

判斷 2 的次冪是為了要進行位元左移， `i` 的值不斷增加，當剛好變為 2 的次冪時，二進位表示法即會進位一次，此時位元左移的次數就要加 1

i | (ans << len)

由 `|` 將 `i` 與左移的 `ans` 接在一起
:::info
詢問 ChatGPT 上述程式碼中 `M` 的用途

得知 `M` 的用途是為了限制結果不要超出範圍以外，稱之為「對 M 取模」
:::

:::success
延伸問題
1. 嘗試使用 [`__builtin_{clz,ctz,ffs}`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫，並改進 mod $10^9+7$ 的運算
:::

1. 使用 `__builtin_clz()` 與 `__builtin_ctz()` 重新實作
以下為更動的程式碼

if ((__builtin_clz(i) + __builtin_ctz(i) + 1) == 32)

使用 `__builtin_clz()` 跟 `__builtin_ctz()` 這兩個函式，我就可以找出從頭端跟從尾端數到 1-bit 為止的 0-bits 的數量，假如 `i` 是 2 的次冪的話，前述兩個函式的總和值 +1 就會等於 `int` 資料型態的空間大小 4 bytes ( 32 bits )

2. 改進 mod $10^9+7$ 的運算
題目中的 `concatenatedBinary()` 回傳之資料型態為 `int` ，但 `ans` 的資料型態為 `long int` ，經過 `M` 取模後可能會有 overflow 的問題，原因是 `M` 所取的質數為 $10^9 + 7$ ，連 `int` 最大值 2,147,483,647 的一半都還不到，若想完整地串連起來擁有較大值的 `int` 型態級數就會出現問題
為了改進 mod $10^9+7$ 的運算，以減少 overflow 的可能性，可以將 `M` 取值為比 $2^{k-1}$ 還要小的最大質數 ( k 為 `ans` 資料型態所佔用的 bits 數) ，故可取 `M` $= 2^{63} - 59$ ，不過函式的傳回值必須改為 `long`

const uint64_t M = (UINT64_C(1) << 63) - UINT64_C(59);

使用修改後的程式碼重新測試 `n = 12` 時的結果為 $118,505,380,540$ 共 12 位數，近似於 $2^{36}$ ，比原本取模 `M` $= 10^9 + 7$ 時的結果還要大，且也符合真正的位元數

// 1,2,...,12 end to end in binary
0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100
-> 1 1011 1001 0111 0111 1000 1001 1010 1011 1100 ( 37 bits )

雖然結果符合預期，但光是 `n = 12` 就需要佔用 37 bits 的空間，約為 `M` 所佔用空間 64 bits 的一半，因此能操作的 `n` 值上限不高，為了避免 overflow 的潛在不安因素，可以加入判斷式限制 `n` 的值不要超過上限即可
假如 `n = 25` 為安全範圍的上限，進行例外排除

if (n > 25)
    return 0;

### 測驗 `3`
參考 < [seasonwang](https://hackmd.io/@seasonwang/S1iI3p6Rj#%E6%B8%AC%E9%A9%97-3) > ，修正編譯有誤的片段程式，如下所示

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;
+   const usin64_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;  // AAAA = 3
    count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;  // BBBB = 7 , CCCC = 7 , DDDD = 0

    return count;
}

1. 上述程式碼的運作原理，建立的 `qword` 指向 `buf` 的地址，而 `end` 則指向 `qword[len >> 3]` 的地址， `len >> 3` 相當於 `len / 8`
2. 接著 `for` 迴圈的作用是計算 `qword` 到 `end` 之間**不為 UTF-8 的 bytes 數**，配合 `__builtin_popcountll` 計算個數
3. `(1 << 3) * (len / 8)` 會得到 8 的倍數，再扣除 `count` 後可得 UTF-8 的總數
4. `len & 7` 可視為 `len % 8` 的反義，若 `len` 為 8 的倍數，則 `len & 7` 為 `false` ，故 `count += 0`
5. 反之若 `len` 不為 8 的被數，則進入函式 `count_utf8` 以計算剩餘的 bytes 是否還有 UTF-8 ，最後回傳的 `count` 即為 `buf` 中之 UTF-8 總數
### 測驗 `4`

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

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

    return true;
}

以上的程式碼是在判斷 `x` 的 Most Significant Bit ( MSB ) 是否為 1 ，並且它後面的位元為連續的 1-bit ，例如

1000
1110
1111 1111

若滿足這種型態，則回傳 `true` ，反之則回傳 `false`
若要將程式碼進行改寫，達成等價的行為，但更精簡有效，可以寫成如下形式

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

原理是藉由 `~x + 1` 使 `n` 中最接近 Least Significant Bit ( LSB ) 的 1-bit 所在的位元與 `x` 相同，如此一來便可藉由 `n XOR x` 將最靠近 LSB 的 1-bit 變為 0-bit ，而其他位元則如同執行 `OR` 運算，如下所示

x = 10010010
n = 01101110
(n ^ x) = 11111100

上述的運算中，可以看到一個性質，就是 MSB 之後是否為連續的 1-bits 將會影響運算結果的大小，舉例來說

// case 1
x = 10010010
(n ^ x) = 11111100
(n ^ x) > x
// case 2
x = 11111110
(n ^ x) = 11111100
(n ^ x) < x

藉由此性質，可以判斷 `x` 是否符合特定樣式

:::success
延伸問題
1. 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇
> 參見 [Data Structures in the Linux Kernel](https://0xax.gitbooks.io/linux-insides/content/DataStructures/linux-datastructures-3.html)
:::

1. 應用範疇
我找到的應用範疇是型別 `cpumask_t` ，它在 Linux Kernel 中被廣泛運用在檢視及操作 CPU 的狀態，位於 [`include/linux/bitmap.h`](https://github.com/torvalds/linux/blob/16f73eb02d7e1765ccab3d2018e0bd98eb93d973/include/linux/bitmap.h) 當中
以下為其中一個 API
:::info
`cpumask_of()` 是 Linux kernel 中一個用來創建 CPU 集合的函數，其原型定義如下：

cpumask_t cpumask_of(int cpu);

該函數接受一個整數 cpu，返回一個包含指定 CPU 的位元遮罩 `cpumask_t` ，例如， `cpumask_of(0)` 會返回一個只有第一個 CPU 為 1，其他位元都為 0 的 `cpumask_t` 值。

`cpumask_of()` 函數常被用於創建進程的 CPU 選擇集合。在 Linux kernel 中，每個進程都可以綁定到一個或多個 CPU 上運行。進程的 CPU 選擇集合通常表示為一個 `cpumask_t` 位元遮罩，用來指定哪些 CPU 可以用於運行進程。

例如，以下代碼展示了如何使用 `cpumask_of()` 函數創建一個包含第一個 CPU 和第二個 CPU 的選擇集合：

#include <linux/cpumask.h>

cpumask_t my_cpuset;
cpumask_clear(&my_cpuset);    // 初始化選擇集合為空
cpumask_set_cpu(0, &my_cpuset);
cpumask_set_cpu(1, &my_cpuset);

在這個例子中， `cpumask_clear()` 函數用來初始化 `my_cpuset` 為空集合。接下來， `cpumask_set_cpu()` 函數用來將第一個 CPU 和第二個 CPU 分別加入選擇集合中。

透過使用 `cpumask_of()` 函數，可以方便地創建包含指定 CPU 的選擇集合，進而用於進程的 CPU 調度和管理。
> ChatGPT
:::

它的功能是取得指定 CPU 的遮罩，得以檢視及更動該 CPU 的狀態

假如一項進程需要 5 個 CPU 運行，則可以透過 `cpumask_set_cpu` 來選擇要綁定的 5 個 CPU 運行進程