2023q1 第 2 週測驗題

目的: 檢驗學員對 bitwise 的認知

作答表單: 測驗 1-2 (針對 Linux 核心「設計」課程)
作答表單: 測驗 3-4 (針對 Linux 核心「實作」課程)

測驗 `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);
}

然而上述程式碼存在分支，於是我們可考慮建構以下「填補」位元表示中的 1:

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

最初 x 是 0010000000000000，經過一系列操作後，成為 0011111111111111，亦即設定 (set，即指派為 1) 自原本最高位元到最低位元中，所有的位元。

我們嘗試改寫為以下:

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 >> AAAA;
    x |= x >> 16;
    x |= x >> BBBB;
    return CCCC;
}

請補完程式碼，使其符合預期。作答規範:

AAAA 和 BBBB 皆為數值，且 AAAA 小於 BBBB
CCCC 為表示式

延伸問題:

解釋上述程式碼原理，並用 __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.
在 Linux 核心原始程式碼找出類似的使用案例並解釋
當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？

提示: 可執行 cc -O2 -std=c99 -S next_pow2.c 並觀察產生的 next_pow2.s 檔案，確認 bsrq 指令 (表示 "Bit Scan Reverse")

測驗 `2`

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

n

，回傳將 1 到

n

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

10^{9} + 7

之值。

測試資料 1:
輸入： n = 1
輸出： 1

"1" 於二進位中對應著十進位中 1 的值

測試資料 2:
輸入： n = 3
輸出： 27

二進位中，1 、 2 、 3 對應著 1, 10 和 11。
將它們串接在一起，我們得到 11011，其對應著十進位數值 27

測試資料 3:
輸入： n = 12
輸出： 505379714

串接結果為 1101110010111011110001001101010111100
該十進位值為 118505380540
mod
$10^{9} + 7$ 後，結果為 505379714

以下是可能的實作:

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++) {
        /* 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 (!(DDDD))
            len++;
        ans = (i | (EEEE)) % M;
    }
    return ans;
}

請補完程式碼，使其符合預期。作答規範:

DDDD 和 EEEE 皆為表示式

延伸問題:

解釋上述程式碼運作原理
嘗試使用 __builtin_{clz,ctz,ffs} 改寫，並改進 mod
$10^{9} + 7$ 的運算

測驗 `3`

SIMD within a register (SWAR) 是軟體最佳化技巧之一，以下展示 SWAR 運用於 64 位元微處理器架構，原本判斷 2 個 32 位元寬度的整數是否都是奇數 (odd)，可能會這樣撰寫:

#include <stdint.h>
bool both_odd(uint32_t x, uint32_t y) {
    return (x & 1) && (y & 1);
}

但我們可先組合 (compound) 2 個 32 位元寬度的整數為 1 個 64 位元整數，再運用特製的 bitmask，從而減少運算量:

static uint64_t SWAR_ODD_MASK = (1L << 32) + 1;
bool both_odd_swar(uint64_t xy) {
    return (xy & SWAR_ODD_MASK) == SWAR_ODD_MASK;
}

測試程式:

static inline uint64_t bit_compound(uint32_t x, uint32_t y) {
    return ((0L + x) << 32) | ((y + 0L) & (-1L >> 32));
}

int main()
{
    int x = 12345678;
    int y = 9012345;
    uint64_t xy = bit_compound(x, y);
    printf("%d, %d\n", both_odd(x, y), both_odd_swar(xy));
}

延伸閱讀: SIMD and SWAR Techniques

UTF-8 字元可由 1, 2, 3, 4 個位元組構成。其中單一位元組的 UTF-8 由 ASCII 字元構成，其 MSB 必為 0。

UTF-8 的多位元組字元是由一個首位元組和 1, 2 或 3 個後續位元組 (continuation byte(s)) 所構成。後續位元組的最高 2 個位元會設定為 10。對於首位元組，最高的 2 個位元始終為 11，下表展現多位元組字元的規則:

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 序列，則計算其中的後續位元組數量，並將此數字從總字串長度中減去，即可確定字元數量。

將位元組轉換為 (以二補數表示) 有號整數的位元組，並與 "magic number" 進行比較，就足以確定它是否為後續位元組。對應的程式碼如下:

#include <stddef.h>
#include <stdint.h>

size_t count_utf8(const char *buf, size_t len)
{
    const int8_t *p = (const int8_t *) buf;
    size_t counter = 0;
    for (size_t i = 0; i < len; i++) {
        /* -65 is 0b10111111, anything larger in two-complement's should start
         * new code point.
         */
        if (p[i] > -65)
            counter++;
    }
    return counter;
}

SWAR 通常不易實作，因此，我們觀察它們的位元模式：(從最低位元起算) 第 7 位元為 1，且第 6 位元為 0。於是我們可採用以下表示式:

not bit6 and bit7

再計算 (使用 population count 指令) 有多少位元組裡頭的 1 (即具有此屬性)。

__builtin_popcount

輸入的位元組

t0 = [00xx.xxxx|01xx.xxxx|10xx.xxxx|11xx.xxxx]
                          ^^^^^^^^^
                          continuation byte

反向運算 (not bit6)

t1 = ~t0
t1 = [11xx.xxxx|10xx.xxxx|01xx.xxxx|00xx.xxxx]

隔離反向的第 6 個位元

t2 = t1 & 0x40404040
t2 = [0100.0000|0000.0000|0100.0000|0000.0000]

對第 6 個位元，向左位移 1 個位元 (移至第 7 個位元的位置)

t3 = t2 + t2
t3 = [1000.0000|0000.0000|1000.0000|0000.0000]

進行 not bit6 and bit7

t4 = t0 & t3
t4 = [00xx.xxxx|01xx.xxxx|10xx.xxxx|11xx.xxxx] &
     [1000.0000|0000.0000|1000.0000|0000.0000]
   = [0000.0000|0000.0000|1000.0000|0000.0000]
                          ^^^^^^^^^
                          the only non-zero byte

以 population count 指令計算，即 popcount(t4)

SWAR 實作如下:

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

    return count;
}

請補完程式碼，使其運作符合預期。作答規範:

AAAA, BBBB, CCCC, DDDD 皆為常數
以最精簡的方式展現

測驗 `4`

以下程式碼可判定 16 位元無號整數是否符合特定樣式 (pattern):

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

符合上述程式碼的樣式，如下:

pattern: 8000 (32768)
pattern: c000 (49152)
pattern: e000 (57344)
pattern: f000 (61440)
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)
pattern: ffff (65535)

改寫上述程式碼，使其達到等價行為，但更精簡有效。

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

EEEE = ?
FFFF = ?

延伸問題:

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

參見 Data Structures in the Linux Kernel

2023q1 第 2 週測驗題

測驗 1

測驗 2

測驗 3

測驗 4

測驗 `1`

測驗 `2`

測驗 `3`

測驗 `4`