2025q1 第 4 週測驗題

目的: 檢驗學員對 bitops 及數值系統的認知

作答表單: 測驗 1
作答表單: 測驗 2, 3

測驗 1

CRC (循環冗餘校驗，Cyclic Redundancy Check) 是種用於網路與儲存設備的錯誤檢測演算法。發送端指定一個數值作為除數，並對訊息進行除法運算來取得餘數，然後將餘數附加到訊息的末尾。接收端對該訊息執行相同的運算來驗證是否有錯誤，如果餘數不為零，則表示訊息有誤。由於這種方法不會修改訊息內容 (冗餘性)，且計算方式只是將被除數位移後再相減 (循環碼)，因此稱為 CRC。

當 CRC 演算法的除數 (正式名稱為 check value) 長度為 n 個位元時，稱為 n-bit CRC。CRC32C 是 CRC32 的變體，其除數為 32 位元的二進位數。多項式如下：

$$P(x)=x^{32}+x^{28}+x^{27}+x^{26}+x^{25}+x^{23}+x^{22}+x^{20}+x^{19}+x^{18}+x^{14}+x^{13}+x^{11}+x^{10}+x^9+x^8+x^6+1$$

對應的十六進位表示為 0x1EDC6F41

CRC 不把資料當作數字，而是當作多項式係數來處理。例如，8-bit 資料 11010101 可以表示為：

$$1\cdot x^7+1\cdot x^6+0\cdot x^5+1\cdot x^4+0\cdot x^3+1\cdot x^2+0\cdot x^1+1\cdot x^0$$

即：

$$x^7+x^6+x^4+x^2+x^0$$

計算 CRC 時，使用資料的多項式去除以預先指定的 CRC 多項式，取餘數作為校驗碼。例如，給定資料 11010101（8-bit），若用 0x1EDC6F41 來除，就會得到一個 32-bit 餘數，這就是 CRC32 的值。

CRC 計算時，不是使用標準的數字除法，而是透過 XOR 運算來模擬二進位多項式的除法。最後留下來的 32-bit 餘數，就是 CRC32 校驗碼。

接下來我們採用位元反轉方式。至於使用該方法的原因，可見 Fast CRC32。

最初的實作:

uint32_t crc32_naive(uint32_t crc, uint8_t v)
{
    crc ^= v;
    for (int bit = 0; bit < 8; bit++) {
        if (crc & 1)
            crc = (crc >> 1) ^ UINT32_C(0x82f63b78);
        else
            crc = (crc >> 1);
    }
    return crc;
}

現代編譯器可以將三元運算子最佳化為條件移動 (conditional move，簡稱 cmov) 指令，以避免分支。因此，我們可將 if-else 改為三元運算子：

for (int bit = 0; bit < 8; bit++)
    crc = (crc & 1) ? ((crc >> 1) ^ UINT32_C(0x82f63b78)) : (crc >> 1);

接著我們可發現 P 的哪些位元會進行 XOR 運算，完全由 crc 較低 8 個位元所決定。因此，可改寫為：

crc = (crc >> 1) ^ A;
crc = (crc >> 1) ^ B;
...
crc = (crc >> 1) ^ H;

將其重寫為單一運算式：

(crc >> 8) ^ (A >> 7) ^ (B >> 6) ^ (C >> 5) ^ (D >> 4) ^ (E >> 3) ^ (F >> 2) ^ (G >> 1) ^ H

將 A 至 H 合併為單一值 T，則可簡化為：

(crc >> 8) ^ T

我們可預先計算 T，因為它僅由 256 種排列組合組成。知名的模擬器專案 QEMU 就採用該手法，參見 util/crc32c.c

static const uint32_t crc32c_table[256] = {
    0x00000000L, 0xF26B8303L, 0xE13B70F7L, 0x1350F3F4L,
    ...
    0xBE2DA0A5L, 0x4C4623A6L, 0x5F16D052L, 0xAD7D5351L
};

uint32_t crc32c(uint32_t crc, const uint8_t *data, unsigned int length)
{
    while (length--) {
        crc = crc32c_table[(crc ^ *data++) & 0xFFL] ^ (crc >> 8);
    }
    return crc ^ 0xffffffff;
}

上述方式需要佔用 1 KiB 的空間來保存表格。

參見 Fast CRC32 提到的 "Half-Byte Algorithm"，我們可將 8-bit 表格查詢拆分為二次 4-bit 查詢，產生器如下:

/* CRC32C polynomial */
#define POLY  0xEDB88320
void generate() {
    printf("static const uint32_t crc32_table[16] = {\n");
    for (size_t i = 0; i < 16; i++) {
        uint32_t crc = i;
        for (uint32_t j = 0; j < 4; j++)
            crc = (crc >> 1) ^ (-(int)(crc & 1) & POLY);
        printf("    0x%08X%s", crc, (i % 4 == 3) ? ",\n" : ", ");
    }

    printf("};\n");
}

godbolt

以下程式碼 (部分遮蔽) 具備與 crc32_naive 完全等效的行為。

uint32_t crc32_u8(uint32_t crc, uint8_t v)
{
    crc ^= v;
    static const uint32_t crc32_table[] = {
        0x00000000, 0x105ec76f, 0x20bd8ede, 0x30e349b1, 
        0x417b1dbc, 0x5125dad3, 0x61c69362, 0x7198540d, 
        0x82f63b78, 0x92a8fc17, 0xa24bb5a6, 0xb21572c9, 
        AAAA,       BBBB,       CCCC,       DDDD,
    };
    
    crc = (crc >> 4) ^ crc32_table[crc & 0x0F];
    crc = (crc >> 4) ^ crc32_table[crc & 0x0F];
    return crc;
}

補完程式碼，使其運作符合預期，AAAA 到 DDDD 均為十六進位數值，亦即以 0x 開頭，小寫字母。

延伸問題:

1. 在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼
2. 設計實驗來分析 Fast CRC32 提出的手法 (要涵蓋 branchless 和查表的變形)，並與硬體的 CRC32 指令效能進行比較。
3. 以 x86-64 或 Arm64 為探討標的，說明 Linux 核心如何使用硬體加速的 CRC32 指令

---

測驗 2

以下程式碼實作小型的模組化合成器 (Synthesizer 或 Synth)，得以處理多個「聲音」及其內部互連的元件來產生音訊。程式的核心架構是由代表振盪器、envelope、濾波器和混音器的各個節點所構成。每個聲音都包含這些節點，它們連接一起以便產生並調整聲音的特性。

程式碼使用定點數，而用 Q notation，以下是產生正弦波表格的 Python 程式:

import math

# Generate 128 sample values for a sine wave
lut = []
for i in range(128):
    angle = (i / 128.0) * (2 * math.pi)
    lut.append(round(math.sin(angle) * 127))

# Append an extra value (0) to make interpolation easier, as in the C version.
lut.append(0)

# Print the lookup table values as a comma-separated string (without [ and ])
print(', '.join(map(str, lut)))

該輸出結果導向至 sine-table.h 檔案。

程式碼輸出多種波形:

對應的函式原型:

• q15_t sawtooth_wave(q15_t input)
• q15_t sine_wave(q15_t input)
• q15_t square_wave(q15_t input)

音訊合成器的程式碼可見 main.c (部分遮蔽)，編譯並執行:

$ cc -O2 -o main -Wall main.c
$ ./main

預期會輸出 out.wav，其內容為〈一閃一閃亮晶晶〉，可用 MPlayer 一類的工具播放。

補完程式碼以符合預期，作答規範：

• AAAA 到 EEEE 為十六進位數值 (即 0x 開頭)，大寫英文字母，最精簡的方式書寫
• FFFF 為 C 語言表示式，使用一致的縮排 (注意空白字元)，不能用除法和取餘數運算子，且 FFFF 應有 hexadecimal integer literal (即 0x 開頭的數值)
• GGGG 和 HHHH 為 Q15_ 開頭的巨集名稱

延伸問題:

1. 解釋上述程式碼運作原理，搭配「信號與系統」教材
2. 探討定點數的使用和其精確度
3. 改進 MIDI 一閃一閃亮晶晶的音效輸出

---

測驗 3

chat.c (部分遮蔽) 實作精簡的聊天伺服器，可用 TCP 連線工具 (如 telnet) 存取。

作答規範：

• IIII 和 JJJJ 為 C 語言表示式

延伸問題:

1. 解釋上述程式碼運作原理
2. 學習 jserv/ttt 程式碼，在不使用 (n)curses 一類現成的函式庫前提下，改進網路聊天室的文字呈現介面
3. 在既有的程式碼之上，實作帳號登入 (login) 及基本管理功能，並該有線上與否的提示，留意 ping value 的處理機制