CRC-16/CRC-32 演算法原理與 C/C++ 高效實作完整指南

循環冗餘檢查 (CRC) 是資料通訊與儲存領域最常用的錯誤偵測演算法。本文從數學原理出發，詳細推導 CRC-16 (含 CCITT 變體) 與 CRC-32 的查表法運算邏輯，提供可直接嵌入專案的標準 C/C++ 實作碼，並解析查表法生成過程，助你徹底理解「知其然更知其所以然」。

常用 CRC 多項式定義

注意：程式碼中多項式常省略最高位的 1 (如 CRC-16 實際用 0x8005 而非 0x18005)。

核心演算法：位元級運算邏輯

CRC 本質是模 2 多項式除法 (XOR 取代減法)。以 1 位元組資料為例：

1. 資料左移 n 位 (n=16 或 32)，補 0。
2. 若最高位為 1，XOR 多項式；否則僅左移 1 位。
3. 重複 8 次 (1 Byte = 8 bits)，最終餘數即 CRC 值。

查表法優化原理

逐位運算效率低。觀察可知：中間餘數的最高位決定是否 XOR 多項式。由於資料每次只影響最高位判斷，我們可預先計算所有 256 種可能的輸入位元組 (0x00~0xFF) 經 8 步運算後的餘數，建立查找表。運算時僅需：

CRC = (CRC << 8) ^ Table[(CRC >> (n-8)) ^ DataByte];

其中 n 為 CRC 位寬 (16 或 32)。此法將運算從「位元迴圈」降為「單次查表 + XOR + 位移」，速度提升數十倍。

完整 C/C++ 實作碼 (標準 ANSI C，無平台相依)

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

// ===== 多項式常數 =====
static const uint16_t POLY_CRC16   = 0x8005;   // CRC-16 (IBM)
static const uint16_t POLY_CCITT   = 0x1021;   // CRC-CCITT (X.25)
static const uint32_t POLY_CRC32   = 0x04C10DB7; // CRC-32 (IEEE 802.3)

// ===== 查找表 =====
static uint16_t crc16_table[256];
static uint32_t crc32_table[256];
static bool tables_init = false;

// ===== 建表函式 =====
static void build_crc16_table(uint16_t poly) {
    for (int i = 0; i < 256; ++i) {
        uint16_t crc = (uint16_t)(i << 8);
        for (int j = 0; j < 8; ++j) {
            if (crc & 0x8000) crc = (crc << 1) ^ poly;
            else crc <<= 1;
        }
        crc16_table[i] = crc;
    }
}

static void build_crc32_table(uint32_t poly) {
    for (int i = 0; i < 256; ++i) {
        uint32_t crc = (uint32_t)(i << 24);
        for (int j = 0; j < 8; ++j) {
            if (crc & 0x80000000) crc = (crc << 1) ^ poly;
            else crc <<= 1;
        }
        crc32_table[i] = crc;
    }
}

static void ensure_tables_init() {
    if (!tables_init) {
        build_crc16_table(POLY_CRC16); // 預設 CRC-16，若需 CCITT 請自行調用 build_crc16_table(POLY_CCITT)
        build_crc32_table(POLY_CRC32);
        tables_init = true;
    }
}

// ===== 公開 API =====
// CRC-16 / CRC-CCITT (初始值 0x0000, 無最終 XOR, 無反轉)
uint16_t crc16(const uint8_t *data, size_t len, uint16_t poly) {
    if (poly != POLY_CRC16) build_crc16_table(poly); // 支援動態切換多項式
    ensure_tables_init();
    uint16_t crc = 0;
    for (size_t i = 0; i < len; ++i) {
        crc = (crc << 8) ^ crc16_table[((crc >> 8) ^ data[i]) & 0xFF];
    }
    return crc;
}

// CRC-32 (初始值 0xFFFFFFFF, 最終 XOR 0xFFFFFFFF, 輸入/輸出位元反轉 - 標準 IEEE 802.3)
// 注意：此處為簡化示範「無反轉」版本，標準 CRC-32 需配合位元反轉表或執行期反轉
uint32_t crc32_simple(const uint8_t *data, size_t len) {
    ensure_tables_init();
    uint32_t crc = 0; // 標準初始值為 0xFFFFFFFF
    for (size_t i = 0; i < len; ++i) {
        crc = (crc << 8) ^ crc32_table[((crc >> 24) ^ data[i]) & 0xFF];
    }
    return crc; // 標準需返回 crc ^ 0xFFFFFFFF
}

/* === 標準 CRC-32 (IEEE 802.3 / ZIP / PNG) 參考實作 === */
static uint32_t crc32_std_table[256];
static void build_crc32_std_table() {
    for (int i = 0; i < 256; ++i) {
        uint32_t c = (uint32_t)i;
        for (int j = 0; j < 8; ++j)
            c = (c & 1) ? (0xEDB88320 ^ (c >> 1)) : (c >> 1); // 反轉多項式 0x04C10DB7 -> 0xEDB88320
        crc32_std_table[i] = c;
    }
}
uint32_t crc32_standard(const uint8_t *data, size_t len) {
    static bool init = false; if (!init) { build_crc32_std_table(); init = true; }
    uint32_t crc = 0xFFFFFFFF;
    for (size_t i = 0; i < len; ++i)
        crc = (crc >> 8) ^ crc32_std_table[(crc ^ data[i]) & 0xFF];
    return crc ^ 0xFFFFFFFF;
}

關鍵實作細節對照表

驗證測試向量

// CRC-16 (0x8005) : "123456789" -> 0xBB3D (或 0x44C2 視反轉設定)
// CRC-CCITT (0x1021): "123456789" -> 0x29B1 (標準 X.25 初始 0xFFFF)
// CRC-32 (IEEE)    : "123456789" -> 0xCBF43926 (標準檢驗值)

常見陷阱與最佳實務

1. 多項式與參數不匹配：相同多項式若初始值/反轉/最終 XOR 不同，結果完全不同。務必確認通訊協定規範 (如 Modbus 用 CRC-16 0x8005 初始 0xFFFF 且無反轉)。
2. 位元序：網路傳輸通常大端序，但 CRC 運算單位為位元流，需確認資料送入順序。
3. 表格重複建立：靜態區域變數 + 初始化旗標確保全程序只建表一次。
4. 效能優化：可展開迴圈、使用 SIMD (SSE4.2 CRC32 指令)、或採用切片法 (Slicing-by-8/16) 進一步加速。
5. 嵌入式系統：記憶體受限時可捨棄查表法改用逐位運算，或使用 16/32 位元查表 (256 entries 較小)。

掌握 CRC 原理與正確實作，是確保資料完整性、實現通訊協定、檔案校驗的基石。建議專案中封裝為獨立模組，並附上單元測試驗證標準向量。