---
tags: linux2025
---
# [2025q1](https://wiki.csie.ncku.edu.tw/linux/schedule) 第 4 週測驗題
:::info
目的: 檢驗學員對 [bitops](https://hackmd.io/@sysprog/c-bitwise) 及數值系統的認知
:::
==[作答表單: 測驗 `1`](https://docs.google.com/forms/d/e/1FAIpQLSdgTPAv4jwn4dCNepDTjLoavgP5ljyWfETrLVP5ROiO2ayhTg/viewform?usp=dialog)==
==[作答表單: 測驗 `2`, `3`](https://docs.google.com/forms/d/e/1FAIpQLSd2uyZy_O8WVo5gXg0vTf5tNi61cJ75lEnqc1dOmk_jhoJSUg/viewform?usp=dialog)==
### 測驗 `1`
[CRC](https://en.wikipedia.org/wiki/Cyclic_redundancy_check) (循環冗餘校驗，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](https://create.stephan-brumme.com/crc32/)。
最初的實作:
```c
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 改為三元運算子：
```c
for (int bit = 0; bit < 8; bit++)
crc = (crc & 1) ? ((crc >> 1) ^ UINT32_C(0x82f63b78)) : (crc >> 1);
```
接著我們可發現 P 的哪些位元會進行 XOR 運算，完全由 `crc` 較低 8 個位元所決定。因此，可改寫為：
```c
crc = (crc >> 1) ^ A;
crc = (crc >> 1) ^ B;
...
crc = (crc >> 1) ^ H;
```
將其重寫為單一運算式：
```c
(crc >> 8) ^ (A >> 7) ^ (B >> 6) ^ (C >> 5) ^ (D >> 4) ^ (E >> 3) ^ (F >> 2) ^ (G >> 1) ^ H
```
將 A 至 H 合併為單一值 T，則可簡化為：
```c
(crc >> 8) ^ T
```
我們可預先計算 T，因為它僅由 256 種排列組合組成。知名的模擬器專案 QEMU 就採用該手法，參見 [util/crc32c.c](https://github.com/qemu/qemu/blob/907209e3111dd62a553a19319b422ff8aba5b9c0/util/crc32c.c#L40)
```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](https://create.stephan-brumme.com/crc32/) 提到的 "Half-Byte Algorithm"，我們可將 8-bit 表格查詢拆分為二次 4-bit 查詢，產生器如下:
```c
/* 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](https://godbolt.org/z/WxaPnqqqM)
以下程式碼 (部分遮蔽) 具備與 `crc32_naive` 完全等效的行為。
```c
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` 開頭，小寫字母。
:::success
延伸問題:
1. 在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼
2. 設計實驗來分析 [Fast CRC32](https://create.stephan-brumme.com/crc32/) 提出的手法 (要涵蓋 branchless 和查表的變形)，並與硬體的 CRC32 指令效能進行比較。
3. 以 x86-64 或 Arm64 為探討標的，說明 Linux 核心如何使用硬體加速的 CRC32 指令
:::
---
### 測驗 `2`
以下程式碼實作小型的模組化合成器 (Synthesizer 或 Synth)，得以處理多個「聲音」及其內部互連的元件來產生音訊。程式的核心架構是由代表振盪器、[envelope](https://vocus.cc/article/64ed72c5fd89780001569b27)、濾波器和混音器的各個節點所構成。每個聲音都包含這些節點，它們連接一起以便產生並調整聲音的特性。
程式碼使用定點數，而用 [Q notation](https://en.wikipedia.org/wiki/Q_(number_format))，以下是產生正弦波表格的 Python 程式:
```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` 檔案。
程式碼輸出多種[波形](https://en.wikipedia.org/wiki/Square_wave_(waveform)):
對應的函式原型:
* `q15_t sawtooth_wave(q15_t input)`
* `q15_t sine_wave(q15_t input)`
* `q15_t square_wave(q15_t input)`
音訊合成器的程式碼可見 [main.c](https://gist.github.com/jserv/061b2ac9be06b446f31087357b8e4054) (部分遮蔽)，編譯並執行:
```shell
$ cc -O2 -o main -Wall main.c
$ ./main
```
預期會輸出 `out.wav`，其內容為〈[一閃一閃亮晶晶](https://zh.wikipedia.org/zh-tw/%E4%B8%80%E9%96%83%E4%B8%80%E9%96%83%E4%BA%AE%E6%99%B6%E6%99%B6)〉，可用 [MPlayer](https://help.ubuntu.com/community/MPlayer) 一類的工具播放。
補完程式碼以符合預期，作答規範：
* AAAA 到 EEEE 為十六進位數值 (即 `0x` 開頭)，大寫英文字母，最精簡的方式書寫
* FFFF 為 C 語言表示式，使用一致的縮排 (注意空白字元)，不能用除法和取餘數運算子，且 FFFF 應有 hexadecimal integer literal (即 `0x` 開頭的數值)
* GGGG 和 HHHH 為 `Q15_` 開頭的巨集名稱
:::success
延伸問題:
1. 解釋上述程式碼運作原理，搭配「[信號與系統](https://ocw.aca.ntu.edu.tw/ntu-ocw/ocw/cou/103S207)」教材
2. 探討定點數的使用和其精確度
3. 改進 MIDI 一閃一閃亮晶晶的音效輸出
:::
---
### 測驗 `3`
[chat.c](https://gist.github.com/jserv/3294f32b2824076ac17683fdac2daf24) (部分遮蔽) 實作精簡的聊天伺服器，可用 TCP 連線工具 (如 telnet) 存取。
作答規範：
* IIII 和 JJJJ 為 C 語言表示式
:::success
延伸問題:
1. 解釋上述程式碼運作原理
2. 學習 [jserv/ttt](https://github.com/jserv/ttt) 程式碼，在不使用 (n)curses 一類現成的函式庫前提下，改進網路聊天室的文字呈現介面
3. 在既有的程式碼之上，實作帳號登入 (login) 及基本管理功能，並該有線上與否的提示，留意 [ping value](https://www.business.att.com/resources/knowledge-center/what-is-latency-impact-on-gaming-streaming.html) 的處理機制
:::
Sign in with Wallet
Connect another wallet