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

一、前言

1.1 CRC算法介紹

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

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

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

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

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

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

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

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

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

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

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

下面是一個(gè)CRC-32算法的C語言實(shí)現(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ù)計(jì)算了一個(gè)CRC表，用于加速后續(xù)的模2除法運(yùn)算，然后逐字節(jié)處理輸入數(shù)據(jù)，最終返回CRC校驗(yàn)碼。通過這種方式，CRC算法能在保證準(zhǔn)確性的同時(shí)，達(dá)到較高的計(jì)算速度，滿足實(shí)時(shí)性和效率的要求。

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

1.2 CRC校驗(yàn)算法分類

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

CRC校驗(yàn)算法分類的情況：

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

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

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

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

然而，在長距離、高噪聲環(huán)境下，或者在需要高度可靠性的數(shù)據(jù)傳輸中，比如互聯(lián)網(wǎng)數(shù)據(jù)包的傳輸，CRC32或CRC64就是更好的選擇，因?yàn)樗鼈兛梢詸z測到更多類型的錯(cuò)誤，盡管計(jì)算成本會相應(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àn)算法是為了適應(yīng)不同應(yīng)用場景的需求，它們在錯(cuò)誤檢測能力和計(jì)算效率之間提供了不同的權(quán)衡。

1.5 查表法

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

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

查找表的工作原理：

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

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

查找表的生成：

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

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

二、代碼實(shí)操

2.1 文件校驗(yàn)-CRC8

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

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

// CRC8生成多項(xiàng)式
#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;
    }

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

    close(fd);

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

    return 0;
}

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

2.2 文件校驗(yàn)-CRC16

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

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

// CRC16 CCITT生成多項(xiàng)式
#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;
    }

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

    close(fd);

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

    return 0;
}

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

2.3 文件校驗(yàn)-CRC32

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

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

// CRC32 IEEE 802.3生成多項(xiàng)式
#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;
    }

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

    close(fd);

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

    return 0;
}

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

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