2025q1 Homework4 (quiz3+4)

contributed by <As7r1d>

2025q1 第 3 週測驗題

2025q1 第 4 週測驗題

測驗1

循環冗餘校驗，Cyclic Redundancy Check　
運作方式如下：

1. 選擇一個生成多項式
2. 透過 XOR 運算來模擬二進位多項式的除法
3. LSB-first（低位元先處理）的方法計算 CRC （例如 Fast CRC，採用位元反轉方式）

其中

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

這 8 次 shift & XOR 的過程，唯一影響的其實只有最開始的 8 位（最低 8 bit）。
該過程又可以改為預先合併為某個值存在 table 中方便查表
將每個 uint8_t v 處理時拆成兩次 4-bit 的查表，兩次查 4-bit（16 個項目）的小表格取代一次查 8-bit（256 個項目）的大表格。

在 Linux 核心原始程式碼中找到 CRC32 的應用案例至少 3 處，並探討其原始程式碼

設計實驗來分析 Fast CRC32 提出的手法 (要涵蓋 branchless 和查表的變形)，並與硬體的 CRC32 指令效能進行比較。

以 x86-64 或 Arm64 為探討標的，說明 Linux 核心如何使用硬體加速的 CRC32 指令