深入解析 CRC-16 與 CRC-32 算法實現：從原理到代碼

前言

在數據通訊與存儲領域，循環冗餘校驗（CRC）是保證數據完整性的核心手段。本文將系統講解 CRC-16 與 CRC-32 的數學原理、查表法生成機制，並提供可直接嵌入項目的 C/C++ 完整實現代碼，幫助開發者「知其然，更知其所以然」。

核心多項式定義

CRC 算法的骨架是生成多項式，常用標準如下：

• CRC-16 (IBM)：0x8005 → x¹⁶ + x¹⁵ + x² + 1
• CRC-CCITT：0x1021 → x¹⁶ + x¹² + x⁵ + 1（抗錯能力更強）
• CRC-32 (IEEE 802.3)：0x04C10DB7 → x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1

注意：最高位 xⁿ 恒為 1，存儲時通常省略。

查表法核心：預計算 256 項查表

查表法將 8 位移位運算壓縮為一次查表 + 一次異或，極大提升速度。表的生成邏輯是模擬「以每個可能的字節為初始值，經過 8 次移位反饋」的過程：

16 位 CRC 表生成

void BuildTable16(unsigned short poly) {
    for (int i = 0; i < 256; ++i) {
        unsigned short data = (unsigned short)(i << 8);
        unsigned short accum = 0;
        for (int j = 0; j < 8; ++j) {
            if ((data ^ accum) & 0x8000)
                accum = (accum << 1) ^ poly;
            else
                accum <<= 1;
            data <<= 1;
        }
        Table_CRC[i] = accum;
    }
}

32 位 CRC 表生成

void BuildTable32(unsigned long poly) {
    for (int i = 0; i < 256; ++i) {
        unsigned long data = (unsigned long)(i << 24);
        unsigned long accum = 0;
        for (int j = 0; j < 8; ++j) {
            if ((data ^ accum) & 0x80000000)
                accum = (accum << 1) ^ poly;
            else
                accum <<= 1;
            data <<= 1;
        }
        Table_CRC[i] = accum;
    }
}

高效計算 CRC 值

有了查表，實際校驗只需幾行代碼：

CRC-16 / CRC-CCITT 計算

unsigned short CRC_16(const unsigned char* data, unsigned long len) {
    BuildTable16(0x8005); // 或 0x1021
    unsigned short crc = 0;
    for (unsigned long i = 0; i < len; ++i)
        crc = (crc << 8) ^ (unsigned short)Table_CRC[(crc >> 8) ^ data[i]];
    return crc;
}

CRC-32 計算

unsigned long CRC_32(const unsigned char* data, unsigned long len) {
    BuildTable32(0x04C10DB7);
    unsigned long crc = 0;
    for (unsigned long i = 0; i < len; ++i)
        crc = (crc << 8) ^ Table_CRC[(crc >> 24) ^ data[i]];
    return crc;
}

工程落地建議

1. 初始化與反轉：部分協議要求初始值為 0xFFFF 或結果需按位反轉，請根據具體標準調整。
2. 線程安全：查表可聲明為 static const，避免重複生成；多線程環境下建議使用 thread_local 或鎖保護。
3. 效能優化：針對大數據塊，可展開循環處理 4/8 字節，配合 SIMD 指令集進一步加速。

總結

通過理解多項式除法與移位反饋的等價性，我們不再盲目複製查表常數，而是能夠根據任意多項式自動生成查表，並靈活應對不同協議的 CRC 變體。掌握這套「造表—查表」通用框架，即可在嵌入式、網絡協議、文件校驗等場景游刃有餘。