關於CRC8/CRC16/CRC32,你要找的全部在這

↑點擊上方藍色字體，關注「嵌入式軟體實戰派」獲得更多精品乾貨。

循環冗餘校驗（英語：Cyclic redundancy check，通稱「CRC」）是一種根據網絡數據包或電腦文件等數據產生簡短固定位數校驗碼的一種散列函數，主要用來檢測或校驗數據傳輸或者保存後可能出現的錯誤。

一句話：CRC是將數據計算出散列的方式，一般用於校驗數據的完整性。它具有簡單、執行效率高等特點。當然，你可以類比於Checksum，但比Checksum複雜些，防碰撞性更好些。

▍CRC的原理
CRC是基於除法的。實際的輸入數據會被解釋為一個長二進位位流（除數），再將其除以另一個固定二進位數（除數，即多項式）。該除法的其餘部分就是校驗值。但是，現實要複雜一些。二進位數（除數和除數）不被視為普通整數值，而是被視為二進位多項式，其中實際位用作係數。輸入數據，看做一串二進位流，用多項式的方式表示為g(x)，而除數是國際標準上的多項式，用h(x)表示。通過g(x)和h(x)做除法，即兩者的異或運算，得出的結果，就是我們所說的CRC運算檢驗結果。例如，1x3 + 0x2 + 1x + 1可以表示為1011b，或者1011b表示為1x3 + 0x2 + 1x + 1，其中是0的位，即以0為係數乘以該項。我們來看看一個數據串11010011101100除以x3 + x + 1是怎樣進行的？

整個運算過程是這樣的：

實際上就是逐個bit移位做異或。

詳見：https://en.wikipedia.org/wiki/Cyclic_redundancy_check

▍CRC的概念

實際上，人們根據不同的需要，做了很多種計算方式，主要差別在於CRC長度、多項式、初始值、結果是否需要異或、是否需要翻轉等等。

首先，來看看幾個概念:

Length: CRC的長度(按bit算，如8,16,32)Name: CRC的名字，讓人一看就知道這是哪種CRCPolinomial: 多項式，通過該多項式來計算CRCFinalXorValue: CRC結果做異或運算的值InputReflected: 指示輸出是否需要翻轉OutputReflected: 指示輸出是否需要翻轉

從上面的CRC名稱可以看出，不同的算法是有不同用途的，這是國際常規的用法定義，其實如果是用戶自己用也沒特別要求，可以自由點。

▍CRC的實現
按照前面章節的「CRC原理」來做C語言實現，就通過數據移位和異或算得。以CRC8為例，代碼如下：

#define CRC_POLYNOMIAL_8    0x0Cuint8 crc_8(uint8 crc, uint8* pdata, uint32 len){    for (uint32 i = 0; i < len; i++)    {        crc ^= pdata[i];        for (uint8 j = 0; j < 8; j++)        {            if ((crc & 0x80u) > 0)            {                crc = ( (uint8)(crc << 1u) ) ^ CRC_POLYNOMIAL_8;            }            else            {                crc <<= 1u;            }        }    }    return crc;}
這個代碼中有個if ((crc & 0x80u) > 0)要解釋下，因為任意數與0做異或，結果是其本身。所以，數據為0時，不做異或。同理，CRC16、CRC32也可以按這種方法做計算，只是多項式和數據位數不一樣而已，在此不累述了。
按移位做異或的方法，有個缺點，就是用了兩層循環，效率不是那麼的高，在嵌入式軟體中，不是那麼受歡迎。
那需要怎麼優化算法呢？那就將多項式預先算個表出來，查表吧。2. 將多項式(Polynomial)生成一個256長度的表，用查表法實現
2.1 多項式生成的表
在開始這個話題之前，我們得回個頭來看看那幾個概念中有個InputReflected和OutputReflected。幹啥呢，吃飽沒事幹啊，算就算，還要翻轉？呵呵！
其實，通過多項式生成表就可以生成正序和逆序，就是為了應付這個「翻轉」的。舉個例子以CRC8_ITU(Polynomial=0x07)看看這個表：
正序表為
const unsigned char crc8_itu__table[] = {    0x00, 0x07, 0x0E, 0x09, 0x1C, 0x1B, 0x12, 0x15, 0x38, 0x3F, 0x36, 0x31, 0x24, 0x23, 0x2A, 0x2D,     0x70, 0x77, 0x7E, 0x79, 0x6C, 0x6B, 0x62, 0x65, 0x48, 0x4F, 0x46, 0x41, 0x54, 0x53, 0x5A, 0x5D,         0xAE, 0xA9, 0xA0, 0xA7, 0xB2, 0xB5, 0xBC, 0xBB, 0x96, 0x91, 0x98, 0x9F, 0x8A, 0x8D, 0x84, 0x83,     0xDE, 0xD9, 0xD0, 0xD7, 0xC2, 0xC5, 0xCC, 0xCB, 0xE6, 0xE1, 0xE8, 0xEF, 0xFA, 0xFD, 0xF4, 0xF3, };
逆序表為
const unsigned char crc8_itu_reversed_table[] = {    0x00, 0x91, 0xE3, 0x72, 0x07, 0x96, 0xE4, 0x75, 0x0E, 0x9F, 0xED, 0x7C, 0x09, 0x98, 0xEA, 0x7B,     0x1C, 0x8D, 0xFF, 0x6E, 0x1B, 0x8A, 0xF8, 0x69, 0x12, 0x83, 0xF1, 0x60, 0x15, 0x84, 0xF6, 0x67,        0xA8, 0x39, 0x4B, 0xDA, 0xAF, 0x3E, 0x4C, 0xDD, 0xA6, 0x37, 0x45, 0xD4, 0xA1, 0x30, 0x42, 0xD3,     0xB4, 0x25, 0x57, 0xC6, 0xB3, 0x22, 0x50, 0xC1, 0xBA, 0x2B, 0x59, 0xC8, 0xBD, 0x2C, 0x5E, 0xCF, };
2.2 通用查表法
網上有很多種查表發計算CRC，不盡相同。於是我做了個通用版，滿足各種算法，其中用了宏定義的奇技淫巧。直接上代碼：
#define DEF_CRC_FUNC(func, width, crcTable)                                                         \uint##width func(const uint8 *pdata, int len,                                                       \uint##width initial, uint##width finalXor,                                                          \BOOL inputReflected, BOOL resultReflected)                                                          \{                                                                                                   \    uint##width crc = initial;                                                                      \    uint##width temp1 = 0, temp2 = 0, pos = 0;                                                      \    const uint##width *pTable = crcTable;                                                           \    for(int i = 0; i < len; i++)                                                                    \    {                                                                                               \        uint##width curByte = pdata[i];                                                             \        if(inputReflected)                                                                          \        {                                                                                           \          curByte = Reflect8(pdata[i]);                                                             \        }                                                                                           \                                              \        temp1 = (crc ^ (curByte << (width - 8)));                                                   \                                        \        pos = (temp1 >> (width - 8)) & 0xFF;                                                        \                                                                          \        temp2 = (temp1 << 8);                                                                       \                                 \        crc = (temp2 ^ pTable[pos]);                                                                \    }                                                                                               \    if(resultReflected)                                                                             \    {                                                                                               \        crc = Reflect##width(crc);                                                                  \    }                                                                                               \    return (crc ^ finalXor);                                                                        \}
怎麼用？
先定義，即定義對於位數算法的函數，通過預編譯生成：
DEF_CRC_FUNC(gen_crc8, 8, crc8__table);DEF_CRC_FUNC(gen_crc16_maxim, 16, crc16_maxim__table);DEF_CRC_FUNC(gen_crc16_a, 16, crc16_a__table);DEF_CRC_FUNC(gen_crc32_jamcrc, 32, crc32_jamcrc__table);
再調用，測試可以在main函數調用：
int main(void){    const uint8 buf[6] = "123456";    uint8 crc8 = gen_crc8(buf, 6, 0x00, 0x00, 0, 0);    uint16 crc16_maxim = gen_crc16_maxim(buf, 6, 0x0000, 0xFFFF, 1, 1);    uint16 crc16_a = gen_crc16_a(buf, 6, 0xC6C6, 0x0000, 1, 1);    uint32 crc32_jamcrc = gen_crc32_jamcrc(buf, 6, 0xFFFFFFFF, 0x00000000, 1, 1);    printf("crc8: %X\n", crc8);    printf("crc16_maxim: %X\n", crc16_maxim);    printf("crc16_a: %X\n", crc16_a);    printf("crc32_jamcrc: %X\n", crc32_jamcrc);}
這裡還是有個問題，就那個「翻轉」的問題，每個byte都做翻轉，很浪費CPU資源啊。作為「優秀的」嵌入式軟體開發人員，我們是追求卓越的算法，於是乎，就有了以下方式：
(1)對於InputReflected和OutputReflected都是False的，我們用正序表，以CRC8_ITU為例：
unsigned char crc8_itu(unsigned char crc, const unsigned char* buf, unsigned int len){    for(unsigned int i = 0; i < len; i++)    {        crc = crc8_itu__table[crc ^ buf[i]];    }    return crc^0x55;}
(2)對於InputReflected和OutputReflected都是True的，我們用逆序表，以CRC8_EBU為例：
/*CRC Info:Name                 Polynomial Initial    FinalXor   InputReflected ResultReflectedCRC8_EBU             0x1D       0xFF       0x00       true           true           */unsigned int crc8_ebu(unsigned int crc, const unsigned char* buf, unsigned int len){    for(unsigned int i = 0; i < len; i++)    {        crc = crc8_ebu_reversed_table[crc ^ buf[i]];    }    return crc^0x00;}
▍CRC的源碼
說了這麼多，以上都是舉例而已(其實直接將上面代碼copy過去驗證也是木有問題的，不要懷疑)，上代碼啊
Talk is cheap. Show me the code.
我將上面表格中提到的所有CRC算法，都coding了，就像下圖的這些
舉個例子，CRC32_BZIP2.h文件是的算法是這樣的：
真以為我一個一個寫的嗎，哈哈哈，不是。但我肯定不是在網上一個一個抄的，網上也找不到這麼多。
我找到了個規律，寫了個腳本生成的，多項式的正序表、逆序表是生成的，連代碼，我都是用腳本生成的。
這裡篇幅有限，就不將代碼全部貼在這了，如果你對這些算法感興趣，關注「嵌入式軟體實戰派」，聊天界面輸入並發送「CRC」獲得下載連結。後續適當的時候，我還會將這個生成源文件的腳本也分享給大家。
為了驗證其可靠性，我還做了個測試代碼(篇幅有限，下面截取的代碼已省略了部分)：
    crc_assert(0xfd ==  crc8                 (0x00, "123456", 6), "crc8"                  );        crc_assert(0x57 ==  crc8_rohc            (0xFF, "123456", 6), "crc8_rohc"             );    crc_assert(0xab ==  crc8_wcdma           (0x00, "123456", 6), "crc8_wcdma"            );
    crc_assert(0x20e4 ==  crc16_ccit_zero   (0x0000, "123456", 6), "crc16_ccit_zero"    );    crc_assert(0x29e4 ==  crc16_arc         (0x0000, "123456", 6), "crc16_arc"          );
        crc_assert(0x32e4 ==  crc16_modbus      (0xFFFF, "123456", 6), "crc16_modbus"       );    crc_assert(0xe672 ==  crc16_x_25        (0xFFFF, "123456", 6), "crc16_x_25"         );    crc_assert(0x20e4 ==  crc16_xmodem      (0x0000, "123456", 6), "crc16_xmodem"       );

    crc_assert(0x0972d361 ==  crc32         (0xFFFFFFFF, "123456", 6), "crc32"          );        crc_assert(0xf036f1c2 ==  crc32_xfer    (0x00000000, "123456", 6), "crc32_xfer"     );
如果你懷疑我「監守自盜」，你還可以在網上找個在線計算的方式來驗證算法的正確性，如：https://crccalc.com/如果你喜歡我的文章，請掃碼關注「嵌入式軟體實戰派」，我會分享更多技術乾貨。還有哦，點擊「在看」，讓更多有需要的人參與學習，我的分享毫無保留。

往期精彩內容推薦>>>
我在馬路上遇到一個死鎖問題
我硬生生地把C代碼塞進了Python和Ruby
C語言的奇技淫巧之四
SREC、Hex、Bin等燒錄文件格式完全解讀