Linux 核心設計/實作 (Spring 2023)

作業要求

2023q1 Homework2 (作業區)
L03: quiz2

• 回答第 2 周測驗題從測驗一到測驗四 (採用 2 月 23 日晚間定案的題目)，附帶的「延伸問題」也需要完成
• 解釋程式運作原理時，應提供對應的 Graphviz 圖例，可參照 Linked List 題目 1 + 分析
• 比照 課前測驗參考解答: Q1, Linked list 題目分析 和 參考題解 的模式來撰寫共筆，需要詳細分析自己的思路、參閱的材料 (以第一手材料為主，包含 C 語言規格書的章節)，以及進行相關實驗。

測驗 1

參照 你所不知道的 C 語言: bitwise 操作 ，考慮 next_pow2 可針對給定無號

$64$ 位元數值

$x$ ，找出最接近且大於等於

$2$ 的冪的值，例如:

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

運作原理

• 在二進位中，每個位元皆可各自表示為
  $2$ 的冪之值 (e.g. 0001 =
  $2^0$, 0010 =
  $2^1$, 0100 =
  $2^2$, 1000 =
  $2^3$) 。
• 利用 bitwise 操作，將原本數值 x 中，從最高位元的
  $1$ 至最低位元中的每個位元皆設定為
  $1$ (e.g. 00001101 -> 00001111 ) 。
• 設定最高位元至最低位元為
  $1$ 後再加
  $1$ ，即可進位為
  $2$ 的冪的值 (e.g. 00001111 + 1 = 00010000 =
  $2^4$) 。

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
}

延伸問題

測驗 2

LeetCode 1680. Concatenation of Consecutive Binary Numbers 給定一整數

$n$ ，回傳將

$1$ 到

$n$ 的二進位表示法依序串接在一起所得到的二進位字串，其所代表的十進位數字

$mod$

${10}^9$ +

$7$ 之值。

• Example
  $2$ :

Input: n = 3
Output: 27

Explanation of solution:
i            !(i & (i - 1))        len          ans
1 ->  1             1               1             1
2 -> 10             1               2          1 10
3 -> 11             0               2       1 10 11  = 27(dec)

運作原理

• 每一個
  $2$ 的冪之值，各自可作為二進位表示法中的最小 bit length 之值 (e.g. 100 為
  $len$ =
  $3$ 最小值， 111 為
  $len$ =
  $3$ 最大值) 。
• 因為要與上一個連續 Binary Number 串接前，需考慮到目前 Binary Number 的預留位元長度。所以判斷要串接的 Binary Number 之位元長度時，只需考慮到最小 bit length 之值，以此來決定位元長度 len 之值。
• 對照上述 Example
  $2$ ， if(!(DDDD)) 為判斷是否為
  $2$ 的冪之值 (位元長度 = i 的最小值) 。
• (i | (EEEE)) 則為左移預留長度，並與上一個連續 Binary Number 進行 bitwise 串接。

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

延伸問題

測驗 3

UTF-8 字元可由

$1$,

$2$,

$3$,

$4$ 個位元組構成。其中單一位元組的 UTF-8 由 ASCII 字元構成，其 MSB 必為 0。
UTF-8 的多位元組字元是由一個首位元組和

$1$,

$2$ 或

$3$ 個後續位元組 (continuation byte(s)) 所構成。後續位元組的最高

$2$ 個位元會設定為 10 。

ASCII	0xxx.xxxx
2 bytes	110x.xxxx 10xx.xxxx
3 bytes	1110.xxxx 10xx.xxxx 10xx.xxxx
4 bytes	1111.0xxx 10xx.xxxx 10xx.xxxx 10xx.xxxx

若輸入的字串是一個有效的 UTF-8 序列，則計算其中的後續位元組數量，並將此數字從總字串長度中減去，即可確定字元數量。

運作原理

• 逐行拆解程式碼，將原本傳入並佔用一個 byte 的字串 buf ，轉換其型態成 unsigned integer type (64-bit)，並且佔用
  $8$ 個 byte 。
• 從原本 buf[0], buf[1], .. , buf[7]的
  $8$ 次處理，調整為 qword[0] 的
  $1$ 次處理。意即讀取 qword[0] 同為一次讀取 buf 中 index 0~7 的陣列元素。並且將 end 指向 qword[len >> 3] 的位址。
• for 迴圈中輸入的 t0 一共包含
  $8$ 個位元組，進行 not bit6 and bit7 操做，以 population count 指令來計算其中的後續位元組數量 (不是 UTF-8 字元數量)。
• (1 << 3) * (len / 8) 可得到
  $8$ 的倍數，再減去 count 來得到 UTF-8 字元數量。
• 最後，若 len 不為
  $8$ 的倍數，則以 count_utf8 來計算 buf 中的 UTF-8 字元個數。

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

    return count;
}

延伸問題

測驗 4

判定

$16$ 位元無號整數是否符合特定樣式 (pattern)

Valid pattern:
pattern: 8000 (32768)  ->  1000 0000 0000 0000
pattern: c000 (49152)  ->  1100 0000 0000 0000
pattern: e000 (57344)  ->  1110 0000 0000 0000
pattern: f000 (61440)  ->  1111 0000 0000 0000
pattern: f800 (63488)
pattern: fc00 (64512)
pattern: fe00 (65024)
pattern: ff00 (65280)   .
pattern: ff80 (65408)   .
pattern: ffc0 (65472)   .
pattern: ffe0 (65504)
pattern: fff0 (65520)
pattern: fff8 (65528)
pattern: fffc (65532)
pattern: fffe (65534)  ->  1111 1111 1111 1110
pattern: ffff (65535)  ->  1111 1111 1111 1111

運作原理

• 直觀解法可參照測驗說明的程式碼，從最高位元往低位元逐一檢查所有的 1 是否皆連續相鄰。
• 改寫測驗說明中的程式碼，以避免使用到迴圈。首先觀察 (n ^ x) < FFFF 的特性，exclusive or ^ 的邏輯運算，可透過 (x ^ ~x) 將二進位數字的所有位元設定為
  $1$ 。
• 若把 x 作
  $2$'s complement (~x + 1) ，之後再進行 exclusive or ^ 運算，得到的結果皆比原數少一個最低位的
  $1$ (e.g. 11110000 vs 11100000) ，並且皆小於原數。
• 反之，若不符合測驗中的特定樣式，則 x 作
  $2$'s complement 之後，無法將最低位
  $1$ 後的位元皆清零 (e.g. ~(11110100) + 1 = 00001100) 。進行 exclusive or ^ 運算後，反而會大於原數 (連續相鄰的 1 皆被保留) 。

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

延伸問題