CRC校驗算法詳解、C語言實現(xiàn)

一、前言

1.1 CRC算法介紹

CRC（Cyclic Redundancy Check）校驗算法是一種廣泛應(yīng)用于數(shù)據(jù)通信和存儲系統(tǒng)中的錯誤檢測方法，主要用于檢測數(shù)據(jù)在傳輸過程中是否發(fā)生了改變。

CRC算法通過計算一個固定長度的校驗碼，將該校驗碼附加到原始數(shù)據(jù)的末尾，接收方在接收到數(shù)據(jù)后重新計算校驗碼并與接收到的校驗碼進行比較，以此判斷數(shù)據(jù)在傳輸過程中是否發(fā)生了錯誤。

這種校驗機制不僅能夠檢測出大多數(shù)類型的錯誤，而且計算效率高，占用資源少，因此在各種通信協(xié)議、文件系統(tǒng)、磁盤驅(qū)動器和網(wǎng)絡(luò)協(xié)議中都有廣泛應(yīng)用。

CRC算法的原理基于多項式除法。在CRC校驗中，數(shù)據(jù)被視為一個系數(shù)為0或1的多項式序列，而CRC校驗碼則是通過使用一個預(yù)定義的生成多項式對該數(shù)據(jù)多項式進行模2除法運算得到的。

生成多項式的選擇對CRC算法的錯誤檢測能力有重要影響，通常選取的生成多項式能夠檢測出盡可能多類型的錯誤。

在計算CRC校驗碼時，原始數(shù)據(jù)與生成多項式的模2除法的結(jié)果被附加到數(shù)據(jù)的末尾，形成一個完整的數(shù)據(jù)包。

在接收端，同樣使用生成多項式對數(shù)據(jù)包進行模2除法，如果余數(shù)為零，則認(rèn)為數(shù)據(jù)在傳輸過程中未發(fā)生錯誤。

CRC算法的具體實現(xiàn)過程如下：

1. 將待發(fā)送的數(shù)據(jù)視為一個二進制多項式D(x)，其中每一位代表一個系數(shù)。
2. 選取一個生成多項式G(x)，該多項式的長度決定了CRC校驗碼的長度。
3. 對D(x)乘以x^n（n為生成多項式的長度減1），形成一個與G(x)同階的多項式。
4. 使用生成多項式G(x)對該擴展后的多項式進行模2除法，得到的余數(shù)即為CRC校驗碼。
5. 將CRC校驗碼附加到原始數(shù)據(jù)的末尾，形成完整的數(shù)據(jù)包。
6. 在接收端，對數(shù)據(jù)包再次進行相同的模2除法運算，若余數(shù)為零，則認(rèn)為數(shù)據(jù)包未發(fā)生錯誤。

CRC校驗算法在實際應(yīng)用中非常靈活，可以通過選擇不同的生成多項式來適應(yīng)不同場合的需求。例如，CRC-32使用一個32位的生成多項式，可以檢測出絕大多數(shù)常見的錯誤類型，包括所有奇數(shù)位錯誤、所有雙位錯誤（在數(shù)據(jù)長度不超過31位的情況下）、所有突發(fā)錯誤（長度小于等于32位）以及大多數(shù)長度超過32位的突發(fā)錯誤。

在C語言中實現(xiàn)CRC算法時，可以利用位運算和循環(huán)結(jié)構(gòu)來高效地完成模2除法運算。下面是使用標(biāo)準(zhǔn)C庫函數(shù)和位運算符來實現(xiàn)。

下面是一個CRC-32算法的C語言實現(xiàn)示例：

#include <stdint.h>

uint32_t crc32(const unsigned char *buf, size_t len) {
    uint32_t crc = 0xFFFFFFFF;
    const unsigned char *end = buf + len;
    uint32_t table[256];

    // Pre-compute the CRC table
    for (int i = 0; i < 256; i++) {
        uint32_t c = i;
        for (int j = 0; j < 8; j++) {
            if (c & 1) {
                c = 0xEDB88320 ^ (c >> 1);
            } else {
                c = c >> 1;
            }
        }
        table[i] = c;
    }

    // Process each byte of the data
    while (buf < end) {
        crc = table[(crc ^ *buf++) & 0xFF] ^ (crc >> 8);
    }

    return crc ^ 0xFFFFFFFF;
}

這段代碼首先預(yù)計算了一個CRC表，用于加速后續(xù)的模2除法運算，然后逐字節(jié)處理輸入數(shù)據(jù)，最終返回CRC校驗碼。通過這種方式，CRC算法能在保證準(zhǔn)確性的同時，達到較高的計算速度，滿足實時性和效率的要求。

CRC校驗算法憑借其高效的錯誤檢測能力，在數(shù)據(jù)通信和存儲系統(tǒng)中發(fā)揮著不可或缺的作用。無論是嵌入式系統(tǒng)、網(wǎng)絡(luò)通信還是文件系統(tǒng)，CRC都是確保數(shù)據(jù)完整性和可靠性的一種重要手段。

1.2 CRC校驗算法分類

CRC（Cyclic Redundancy Check）校驗算法是一種基于多項式除法的錯誤檢測方法，用于數(shù)據(jù)傳輸和存儲中的完整性驗證。CRC算法的分類主要依據(jù)生成多項式的長度和特性，這些差異導(dǎo)致了CRC校驗碼的不同長度和錯誤檢測能力。CRC16、CRC32、CRC8等都是根據(jù)生成多項式的位數(shù)命名的，分別表示16位、32位和8位的校驗碼長度。

CRC校驗算法分類的情況：

1. CRC8：
   • CRC8生成的校驗碼長度為8位（1字節(jié)）。它通常用于小數(shù)據(jù)量的校驗，比如在一些簡單的通信協(xié)議中，或者是對字節(jié)級數(shù)據(jù)進行校驗。
   • 由于校驗碼長度較短，CRC8的沖突概率較高，但是計算速度非?？?。
2. CRC16：
   • CRC16生成的校驗碼長度為16位（2字節(jié)）。它適用于中等大小的數(shù)據(jù)塊校驗，例如在串行通信中或者對短消息進行校驗。
   • CRC16的沖突概率比CRC8低，但仍然存在一定的可能性，尤其是在校驗較長的數(shù)據(jù)流時。
3. CRC32：
   • CRC32生成的校驗碼長度為32位（4字節(jié)）。它是最常見的CRC算法，適用于對大型數(shù)據(jù)塊、文件或者網(wǎng)絡(luò)數(shù)據(jù)包進行校驗。
   • CRC32提供了更高級別的錯誤檢測能力，沖突率極低，適合于需要高度可靠性的數(shù)據(jù)傳輸場景。
   • 計算CRC32雖然相對于CRC16和CRC8要稍微慢一些，但由于現(xiàn)代處理器的速度，這種差異在實際應(yīng)用中往往可以忽略。

除了上述常見的CRC版本，還有CRC64，生成64位的校驗碼，適用于要求極高可靠性的應(yīng)用中。

1.3 為什么有CRC16、CRC32等不同版本？

不同版本的CRC校驗算法之所以存在，主要是為了平衡錯誤檢測能力和計算效率。在某些情況下，可能不需要過于強大的錯誤檢測能力，例如在短距離、低噪聲環(huán)境下的通信，這時使用CRC8或CRC16就足夠了，因為它們計算速度快，硬件實現(xiàn)簡單，可以節(jié)省資源。

然而，在長距離、高噪聲環(huán)境下，或者在需要高度可靠性的數(shù)據(jù)傳輸中，比如互聯(lián)網(wǎng)數(shù)據(jù)包的傳輸，CRC32或CRC64就是更好的選擇，因為它們可以檢測到更多類型的錯誤，盡管計算成本會相應(yīng)增加。

此不同的應(yīng)用領(lǐng)域可能有各自的標(biāo)準(zhǔn)和要求，比如在某些通信協(xié)議中，CRC16的特定變體（如CRC-CCITT、CRC-16/ARC）是被規(guī)定的，而在其他地方，比如壓縮文件和網(wǎng)絡(luò)傳輸中，CRC32可能是首選。

CRC16、CRC32等不同版本的CRC校驗算法是為了適應(yīng)不同應(yīng)用場景的需求，它們在錯誤檢測能力和計算效率之間提供了不同的權(quán)衡。

1.5 查表法

在CRC（Cyclic Redundancy Check）算法的實現(xiàn)中，經(jīng)常使用一個預(yù)計算的查找表（lookup table），這個查找表就是一個數(shù)組，用來加速CRC的計算過程。這個數(shù)組通常被稱為“CRC表”或“CRC查找表”。

CRC算法的核心是基于二進制的多項式除法，其中使用的除數(shù)是一個固定的多項式（即生成多項式）。在軟件實現(xiàn)中，特別是當(dāng)需要快速計算CRC校驗值時，查找表可以顯著減少計算量。

查找表的工作原理：

1. 預(yù)計算：
   在CRC算法的初始化階段，程序會預(yù)先計算出所有可能的8位（或其他位數(shù)，取決于查找表的設(shè)計）輸入與生成多項式進行模2除法的結(jié)果，并將這些結(jié)果存儲在一個數(shù)組中。這個數(shù)組的大小通常是256個元素，每個元素對應(yīng)一個8位輸入的CRC校驗值。
2. 快速計算：
   當(dāng)實際計算數(shù)據(jù)的CRC校驗值時，算法會對數(shù)據(jù)進行逐字節(jié)處理。對于每個字節(jié)，算法會在查找表中查找對應(yīng)的CRC值，然后與之前計算得到的部分CRC值進行異或操作。這個過程會重復(fù)直到所有的數(shù)據(jù)字節(jié)都被處理完畢。
3. 最終CRC值：
   在處理完所有數(shù)據(jù)后，累積的CRC值會經(jīng)過可能的反轉(zhuǎn)（reflect）和初始值（seed）調(diào)整，得到最終的CRC校驗值。

使用查找表的主要優(yōu)點是減少了每次迭代中的復(fù)雜計算，尤其是避免了多項式除法，而代之以簡單的數(shù)組查找和異或操作，這在大多數(shù)現(xiàn)代計算機架構(gòu)上是非?？焖俚?。

查找表的生成：

查找表的生成涉及對每一個可能的8位輸入（從0到255）執(zhí)行CRC算法的完整計算過程，并存儲最終結(jié)果。這個過程只在程序啟動時執(zhí)行一次，之后就可以復(fù)用這個查找表來快速計算任何數(shù)據(jù)的CRC校驗值。

查找表的使用使得CRC計算在軟件中變得既快速又高效，尤其在實時系統(tǒng)和大量數(shù)據(jù)處理中，這一點尤為重要。

二、代碼實操

2.1 文件校驗-CRC8

下面是一個使用C語言實現(xiàn)的CRC8校驗值計算的示例代碼。這里使用一個常見的生成多項式 0x07（也就是多項式 x^8 + x^2 + x^1 + x^0）來生成CRC8校驗和。 使用一個查找表來優(yōu)化計算過程。

#include <stdio.h>
#include <stdint.h>
#include <fcntl.h>
#include <unistd.h>

// CRC8生成多項式
#define POLYNOMIAL 0x07

// 初始化CRC8查找表
uint8_t crc8_table[256];

void init_crc8_table(void)
{
    uint8_t i, j;
    for (i = 0; i < 256; i++)
    {
        uint8_t crc = i;
        for (j = 8; j; j--)
        {
            if (crc & 0x80)
                crc = (crc << 1) ^ POLYNOMIAL;
            else
                crc <<= 1;
        }
        crc8_table[i] = crc;
    }
}

uint8_t crc8(const void *data, size_t len)
{
    const uint8_t *byte = data;
    uint8_t crc = 0x00;

    for (; len > 0; len--)
    {
        crc = crc8_table[(crc ^ *byte++) & 0xFF];
    }

    return crc;
}

int main(int argc, char *argv[])
{
    int fd;
    uint8_t buffer[4096];
    size_t bytes_read;
    uint8_t crc;

    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s filenamen", argv[0]);
        return 1;
    }

    // 初始化CRC8查找表
    init_crc8_table();

    // 打開文件
    fd = open(argv[1], O_RDONLY);
    if (fd == -1)
    {
        perror("Error opening file");
        return 1;
    }

    // 讀取文件并計算CRC8校驗值
    crc = 0x00;
    while ((bytes_read = read(fd, buffer, sizeof(buffer))) > 0)
    {
        crc = crc8(buffer, bytes_read);
    }

    close(fd);

    // 輸出CRC8校驗值
    printf("CRC8 checksum: 0x%02Xn", crc);

    return 0;
}

這段代碼首先定義了一個CRC8查找表，并通過init_crc8_table函數(shù)進行初始化。crc8函數(shù)用于計算給定數(shù)據(jù)塊的CRC8校驗值，它使用查找表來進行快速計算。main函數(shù)負(fù)責(zé)打開文件、讀取數(shù)據(jù)并調(diào)用crc8函數(shù)來計算整個文件的CRC8校驗值。

2.2 文件校驗-CRC16

下面是使用CRC16并采用CCITT標(biāo)準(zhǔn)生成多項式（0x1021，即多項式x^16 + x^12 + x^5 + x^0）來計算文件CRC16校驗值的C語言代碼示例。與之前的CRC8示例類似，這里也會使用查找表來優(yōu)化計算過程。

#include <stdio.h>
#include <stdint.h>
#include <fcntl.h>
#include <unistd.h>

// CRC16 CCITT生成多項式
#define POLYNOMIAL 0x1021

// 初始化CRC16查找表
uint16_t crc16_table[256];

void init_crc16_table(void)
{
    uint16_t crc, poly;
    uint8_t i, j;

    for (i = 0; i < 256; i++)
    {
        crc = i;
        for (j = 8; j; j--)
        {
            if (crc & 0x0001)
                crc = (crc >> 1) ^ POLYNOMIAL;
            else
                crc >>= 1;
        }
        crc16_table[i] = crc;
    }
}

uint16_t crc16(const void *data, size_t len)
{
    const uint8_t *byte = data;
    uint16_t crc = 0xFFFF;

    while (len--)
    {
        crc = (crc >> 8) ^ crc16_table[(crc ^ *byte++) & 0xFF];
    }

    return crc;
}

int main(int argc, char *argv[])
{
    int fd;
    uint8_t buffer[4096];
    size_t bytes_read;
    uint16_t crc;

    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s filenamen", argv[0]);
        return 1;
    }

    // 初始化CRC16查找表
    init_crc16_table();

    // 打開文件
    fd = open(argv[1], O_RDONLY);
    if (fd == -1)
    {
        perror("Error opening file");
        return 1;
    }

    // 讀取文件并計算CRC16校驗值
    crc = 0xFFFF;
    while ((bytes_read = read(fd, buffer, sizeof(buffer))) > 0)
    {
        crc = crc16(buffer, bytes_read);
    }

    close(fd);

    // 輸出CRC16校驗值
    printf("CRC16 checksum: 0x%04Xn", crc);

    return 0;
}

這個示例代碼中的init_crc16_table函數(shù)用于生成CRC16的查找表，而crc16函數(shù)則利用該表計算輸入數(shù)據(jù)的CRC16校驗值。在主函數(shù)main中，程序會讀取文件的內(nèi)容并調(diào)用crc16函數(shù)計算CRC16校驗值，最后輸出該值。

2.3 文件校驗-CRC32

下面是一個使用CRC32算法計算文件校驗和的C語言代碼示例。這里使用的是IEEE 802.3標(biāo)準(zhǔn)的多項式（0x04C11DB7），這是最常用的CRC32實現(xiàn)。

#include <stdio.h>
#include <stdint.h>
#include <fcntl.h>
#include <unistd.h>

// CRC32 IEEE 802.3生成多項式
#define POLYNOMIAL 0xEDB88320

// 初始化CRC32查找表
uint32_t crc32_table[256];

void init_crc32_table(void)
{
    uint32_t crc, poly;
    uint8_t i, j;

    for (i = 0; i < 256; i++)
    {
        crc = i;
        for (j = 8; j; j--)
        {
            if (crc & 0x00000001)
                crc = (crc >> 1) ^ POLYNOMIAL;
            else
                crc >>= 1;
        }
        crc32_table[i] = crc;
    }
}

uint32_t crc32(const void *data, size_t len)
{
    const uint8_t *byte = data;
    uint32_t crc = 0xFFFFFFFF;

    while (len--)
    {
        crc = (crc >> 8) ^ crc32_table[(crc ^ *byte++) & 0xFF];
    }

    return crc ^ 0xFFFFFFFF;
}

int main(int argc, char *argv[])
{
    int fd;
    uint8_t buffer[4096];
    size_t bytes_read;
    uint32_t crc;

    if (argc != 2)
    {
        fprintf(stderr, "Usage: %s filenamen", argv[0]);
        return 1;
    }

    // 初始化CRC32查找表
    init_crc32_table();

    // 打開文件
    fd = open(argv[1], O_RDONLY);
    if (fd == -1)
    {
        perror("Error opening file");
        return 1;
    }

    // 讀取文件并計算CRC32校驗值
    crc = 0xFFFFFFFF;
    while ((bytes_read = read(fd, buffer, sizeof(buffer))) > 0)
    {
        crc = crc32(buffer, bytes_read);
    }

    close(fd);

    // 輸出CRC32校驗值
    printf("CRC32 checksum: 0x%08Xn", crc);

    return 0;
}

在這個示例中，init_crc32_table函數(shù)初始化了CRC32的查找表，crc32函數(shù)用于計算輸入數(shù)據(jù)的CRC32校驗值。主函數(shù)main負(fù)責(zé)讀取文件內(nèi)容并調(diào)用crc32函數(shù)計算CRC32校驗值，最后輸出該值。

注意，在CRC32計算結(jié)束時，通常需要對CRC值進行反轉(zhuǎn)（XOR 0xFFFFFFFF），這是為了與大多數(shù)CRC32實現(xiàn)保持一致。