2023q1 Homework2 (quiz2)

contributed by <bonianlee>

測驗 1

參照 你所不知道的 C 語言: bitwise 操作，考慮 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}$ ，即為預期的輸出

延伸問題

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

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

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 >提出了一個很棒的想法，我們看下面這行程式碼

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 接在一起

詢問 ChatGPT 上述程式碼中 M 的用途

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

延伸問題

1. 嘗試使用 __builtin_{clz,ctz,ffs} 改寫，並改進 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 > ，修正編譯有誤的片段程式，如下所示

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 是否符合特定樣式

延伸問題

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

參見 Data Structures in the Linux Kernel

1. 應用範疇
   我找到的應用範疇是型別 cpumask_t ，它在 Linux Kernel 中被廣泛運用在檢視及操作 CPU 的狀態，位於 include/linux/bitmap.h 當中
   以下為其中一個 API

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 運行進程