CRC算法，從原理到實現(xiàn)

CRC，一種基于有限域GF(2)的多項式環(huán)的Hash算法。在GF(2)中，多項式系數(shù)只有0、1，加減運算等同于異或(XOR)運算，乘除運算與一般多項式運算一致（合并同類項時需要注意為XOR運算）

abstract.jpg

概述

在GF(2)中，多項式系數(shù)只有0、1，加減運算等同于異或(XOR)運算，乘除運算與一般多項式運算一致（合并同類項時需要注意為XOR運算）。在CRC-n算法中，有M(x)·xn=Q(x)·G(x)+R(x)，M(x)為m位的數(shù)據(jù)，G(x)為一個GF(2)的n+1項的生成多項式(Poly)，M(x)·xn 則是通過在數(shù)據(jù)M(x)后添加n個0形成的對應(yīng)的m+n位多項式，而R(x)即為M(x)·xn 除以G(x)的n位余數(shù)——即CRC校驗碼，Q(x)為商，直接丟棄。通過比較兩次計算產(chǎn)生的Signature是否一致判斷故障的發(fā)生

基本原理

假定M(x)=11100110，G(x)=x3 + x + 1，其中n=3，則M(x)·xn=11100110000，將G(x)多項式中的各項系數(shù)取出，按降冪排列所對應(yīng)的數(shù)據(jù)Poly=1011，然后對其進(jìn)行除法運算：

Fig1.png

所得n位余數(shù)即為CRC——100

根據(jù)定義可以建立一個簡單的CRC實現(xiàn)算法，模型如下圖所示：
1)建立一個長度為r的CRC Register，并初始化為0
2)在M(x)后添加r個0形成M(x)·xn
3)將CRC Register左移一位，將M(x)·xn的MSB移入CRC Register的Bit 0
4)第3步中的從CRC Register移出的數(shù)，如果是1，則計算，CRC Register=Poly XOR CRC Register
5)重復(fù)第3步，直到M(x)·xn全部移入CRC Register
6)CRC Register即為CRC校驗值

Fig2.png

算法實現(xiàn)

Table Driven Algorithm

根據(jù)定義所建立的算法模型存在明顯缺陷，按位移動處理效率低下，為此我們探索如何實現(xiàn)更大處理單元的算法。這次我們以CRC-32為例，按照前面的算法思路構(gòu)建的模型如下圖所示：

Fig3.png

設(shè)CRC Register中的Byte 3依次為：t7 t6 t5 t4 t3 t2 t1 t0，Poly中的Bit31-Bit24依次為：g7 g6 g5 g4 g3 g2 g1 g0，根據(jù)1.3.2可知，在第1次迭代中，CRC Register的MSB:t7將會決定Poly與CRC Register的異或，如果t7=1，這就會發(fā)生，反之就不會發(fā)生;在第2次迭代中，CRC Register的MSB:t6 XOR (t7*g7) 將會決定本次Poly與CRC Register的異或是否發(fā)生，即t7、t6控制第2XOR操作；同理，在第3次迭代中，CRC Register的MSB也是通過t7、t6、t5決定，即t7、t6、t5控制第3次XOR操作。故我們可以得出下述結(jié)論：k次以后的迭代的最高位的值，可以由寄存器的前k位計算得到。根據(jù)這個結(jié)論，我們可以一次性取出CRC Register的Byte 3，提前計算出8次迭代后的寄存器余式，因為高位終將會在迭代中被移出，我們只需要關(guān)心余式即可。同時XOR運算滿足結(jié)合律：A XOR B XOR C = A XOR (B XOR C)

Fig4.png

上圖即為Byte 3全部迭代移出的示意圖，根據(jù)結(jié)合律可以看出，我們可以依據(jù)Byte 3直接確定8次異或的與否及Poly的偏移量，從而提前計算出不同偏移量的Poly間XOR的值，令其為A，易知A的高8位和Byte 3一定相等，Reg向左移出btye3，從M(x)·xn讀取一個byte放在byte 0，最后將A的低32位與Reg完成XOR操作。為避免與字節(jié)邊界發(fā)生沖突，我們采用字節(jié)的整數(shù)倍——字節(jié)（1 byte）、字（2 byte）、雙字（4 byte），故一般不采用4bit作為處理單元。由于一個字節(jié)的取值是有限的——256種，我們只要提前計算一個字節(jié)全部的A值保存到表中。運行時以byte值為索引，直接從表里取出即可

至此我們完成基于1 byte為處理單元的Table Driven，算法模型如下圖所示：
1)建立一個長度為r的CRC Register，并初始化為0
2)在M(x)后添加r個0形成M(x)·xn
3)將CRC Register左移一個byte，從M(x)·xn讀入一個byte至CRC Register的byte 0中
4)以第3步中的從CRC Register移出的byte為index，從表中取出對應(yīng)的n位寬的值，將該值與CRC Register進(jìn)行XOR
5)重復(fù)第3步，直到M(x)·xn全部移入CRC Register6) CRC Register即為CRC校驗值

Fig5.png

Direct Table Algorithm

在上述的兩種算法中，我們每次都需要在M(x)后添加n個0，其并不參與運算，目的只是為了將M(x)的全部推入CRC Register而已，并且在有些情境下在M(x)后添0操作并不總是能夠?qū)崿F(xiàn)的，故通過改進(jìn)計算步驟有了直接表法，避免了對原始數(shù)據(jù)的添0操作
算法流程，算法模型如下圖所示：
1)建立一個長度為r的CRC Register，按照Init值對其初始化
2)將CRC Register左移一個byte，從M(x)左移一個byte，兩者進(jìn)行XOR
3)第2步中XOR后的值作為index，從表中取出對應(yīng)的n位寬的值，將該值與CRC Register進(jìn)行XOR
4)重復(fù)第2步，直到M(x)全部取出
5)CRC Register即為CRC校驗值

Fig6.png

Reflected Direct Table Algorithm

在Direct Table算法中，當(dāng)RefIn、RefOut為True，每次都需要對數(shù)據(jù)做顛倒操作，很麻煩。為此產(chǎn)生了Reflected Direct Table算法，該算法改變了CRC Register的移動方向，而不需要對M(x)做任何處理，按字節(jié)順序讀取即可，算法模型如下圖所示

算法流程如下：
1)建立一個長度為r的CRC Register，按照Init值對其初始化
2)將CRC Register右移一個byte，從M(x)左移一個byte，兩者進(jìn)行XOR
3)第2步中XOR后的值作為index，從表中取出對應(yīng)的n位寬的值，將該值與CRC Register進(jìn)行XOR
4)重復(fù)第2步，直到M(x)全部取出
5)CRC Register即為CRC校驗值

Fig7.png

CRC模型

Name: CRC標(biāo)準(zhǔn)

Width: 生成的CRC的位寬

Poly: 生成多項式，一般采用十六進(jìn)制簡記，長度為width+1，由于其最高位恒為1，故記法中不體現(xiàn)出來（例如：x16+x12+x5+1記為0x1021）

Init: 初始值，如果數(shù)據(jù)前添加了若干個前導(dǎo)零，在前述算法中，一般是檢測不到的，故通過改變CRC Register中的預(yù)設(shè)值，以實現(xiàn)對該類型錯誤的檢測。在Direct Table算法中用Init初始化CRC Register即可，在Table Driven算法中，不可以直接用Init初始化CRC Register，因為其等同于在原始數(shù)據(jù)前插入了Init，必須要先把CRC Register設(shè)為0，等M(x)·xn移動n/8次后，即CRC Register的預(yù)設(shè)值0全部移出時，再將Init值異或進(jìn)CRC Register。完成Init操作

Xorout: 結(jié)果異或值，所有計算完成后將CRC Register與Xorout進(jìn)行異或作，作為最后的校驗值

RefIn: 輸入反轉(zhuǎn)，這是一個布爾值，如果為False，則每個字節(jié)內(nèi)的位順序保持不變，即Bit 7為MSB，Bit0為LSB。如果為True，則將需要每個字節(jié)內(nèi)的位順序顛倒，即Bit 7為LSB，Bit0為MSB。這個約定在硬件CRC中是合理的，因為在串口通訊中硬件一般默認(rèn)先發(fā)送字節(jié)的Bit 0，最后發(fā)送Bit 7

RefOut: 輸出反轉(zhuǎn)，這是一個布爾值，如果為False，則在計算結(jié)束后，直接進(jìn)入Xorout環(huán)節(jié)，如果為True，則在計算結(jié)束后，將CRC Register進(jìn)行顛倒后，再進(jìn)入Xorout環(huán)節(jié)。注意，和RefIn顛倒字節(jié)內(nèi)的位順序不同的是，這個是將CRC Register的值作為一個整體顛倒，即Bit n到Bit0進(jìn)行顛倒

實現(xiàn)

針對常見常用的下述CRC給出了實現(xiàn)方法，以供參考

#include <stdio.h>

typedef unsigned char   uint8_t;
typedef signed char     int8_t;
typedef unsigned short int  uint16_t;
typedef signed short int    int16_t;
typedef unsigned int    uint32_t;
typedef signed int      int32_t;
typedef unsigned long long int  uint64_t;
typedef signed long long int    int64_t;

uint16_t Table16[256];
uint32_t Table32[256];
uint32_t Table32Ref[256];

/********************      CRC-16/CITI False Model      ********************/
/*
Name   : "CRC-16/CITT FALSE"
Width  : 16
Poly   : 1021
Init   : FFFF
RefIn  : False
RefOut : False
XorOut : 0000
*/
/***************************************************************************/       
uint16_t CRC16_CITIFalse(uint8_t *ptr, uint32_t len);
uint8_t GenerateT16(void);


/********************      CRC-32 Model      *******************************/
/*
Name   : "CRC-32"
Width  : 32
Poly   : 04C11DB7
Init   : FFFFFFFF
RefIn  : True
RefOut : True
XorOut : FFFFFFFF
*/
/***************************************************************************/
uint32_t CRC32(const uint8_t* ptr, uint32_t len);
uint8_t GenerateT32(void);   
uint32_t CRC32Ref(const uint8_t* ptr, uint32_t len);
uint8_t GenerateT32Ref(void);
uint32_t ExchBitOrder(uint32_t data, uint8_t bitnum);

uint8_t main(void)
{
    uint8_t Table16Flag = 0;
    uint8_t Table32Flag = 0;
    uint8_t Table32RefFlag = 0;

    if (0 == Table16Flag)
    {
        printf("Calc Table16 Start...\r\n");
        GenerateT16();
        printf("Calc Table16 Over!\r\n");
        Table16Flag = 1;
    }
    if (0 == Table32Flag)
    {
        printf("\r\nCalc Table32 Start...\r\n");
        GenerateT32();
        printf("Calc Table32 Over!\r\n");
        Table32Flag = 1;
    }
    if (0 == Table32RefFlag)
    {
        printf("\r\nCalc Table32Ref Start...\r\n");
        GenerateT32Ref();
        printf("Calc Table32Ref Over!\r\n");
        Table32Flag = 1;
    }

    uint8_t test1[4] = { 0,0,0,0};
    uint8_t test2[3] = { 0xF2,0x01,0x83};
    uint8_t test3[9] = { 0x33,0x22,0x55,0xAA,0xBB,0xCC,0xDD,0xEE,0xFF};
    uint8_t test4[4] = { 0xFF,0xFF,0xFF,0xFF};
    uint8_t test5[4] = { 0x31,0x32,0x33,0x34 };

    printf("\r\n       CRC-16/CITT-FALSE Test\r\n");
    printf("____________________________________________________\r\n");
    printf(" TestData               Expecte     Actual\r\n");
    printf("____________________________________________________\r\n");
    printf("0x00000000              0x84C0      0x%X\r\n", CRC16_CITIFalse(test1,4));     
    printf("0xF20183                0xD374      0x%X\r\n", CRC16_CITIFalse(test2,3));
    printf("0x332255AABBCCDDEEFF    0xF53F      0x%X\r\n", CRC16_CITIFalse(test3,9));
    printf("0xFFFFFFFF              0x1D0F      0x%X\r\n", CRC16_CITIFalse(test4,4));
    printf("0x31323334              0x5349      0x%X\r\n", CRC16_CITIFalse(test5,4));
    printf("____________________________________________________\r\n");


    printf("\r\n       CRC-32 Test\r\n");
    printf("Algorithm : Direct Table\r\n");
    printf("__________________________________________________________\r\n");
    printf(" TestData                Expecte             Actual\r\n");
    printf("__________________________________________________________\r\n");
    printf("0x00000000              0x2144DF1C          0x%X\r\n", CRC32(test1, 4));
    printf("0xF20183                0x24AB9D77          0x%X\r\n", CRC32(test2, 3));
    printf("0x332255AABBCCDDEEFF    0xB0AE863D          0x%X\r\n", CRC32(test3, 9));
    printf("0xFFFFFFFF              0xFFFFFFFF          0x%X\r\n", CRC32(test4, 4));
    printf("0x31323334              0x9BE3E0A3          0x%X\r\n", CRC32(test5, 4));
    printf("__________________________________________________________\r\n");
    
    printf("\r\n       CRC-32 Test\r\n");
    printf("Algorithm : Reflected Direct Table\r\n");
    printf("__________________________________________________________\r\n");
    printf(" TestData        Expecte       Actual\r\n");
    printf("__________________________________________________________\r\n");
    printf("0x00000000              0x2144DF1C          0x%X\r\n", CRC32Ref(test1, 4));
    printf("0xF20183                0x24AB9D77          0x%X\r\n", CRC32Ref(test2, 3));
    printf("0x332255AABBCCDDEEFF    0xB0AE863D          0x%X\r\n", CRC32Ref(test3, 9));
    printf("0xFFFFFFFF              0xFFFFFFFF          0x%X\r\n", CRC32Ref(test4, 4));
    printf("0x31323334              0x9BE3E0A3          0x%X\r\n", CRC32Ref(test5, 4));
    printf("__________________________________________________________\r\n");

    return 0;
}

uint16_t CRC16_CITIFalse(const uint8_t *ptr,uint32_t len)       //   Algorithm:Direct Table
{
    uint16_t CrcReg = 0xFFFF;   
    uint8_t TopByte = 0;
    uint8_t index = 0;
    while (0!=len)
    {
        TopByte = (uint8_t)((CrcReg & 0xFF00) >> 8);
        CrcReg = (uint16_t)((uint32_t)CrcReg << 8);
        index = (uint8_t)(*ptr) ^ TopByte;
        CrcReg = CrcReg^Table16[index];
        ptr++;
        len--;
    }                       
    return CrcReg;
}                             

uint8_t GenerateT16(void)
{
    uint16_t i=0;
    uint16_t pxp = 0;
    for (i = 0; i < 256; i++)
    {
        pxp = 0;
        for (int8_t nbit = 7; nbit > -1; nbit--)
        {
            if (((i >> nbit) ^ (pxp >> 15)) & 0x0001)     
            {
                //待測數(shù)據(jù)位和pxp高位相異，poly進(jìn)行XOR
                pxp = (uint16_t)((uint32_t)pxp << 1) ^ 0X1021;
            }
            else                                          
            {
                //待測數(shù)據(jù)位和pxp高位相同，poly不進(jìn)行XOR
                pxp = (uint16_t)((uint32_t)pxp << 1);
            }
        }
        Table16[i] = pxp;
    }
    return 0;
}   

uint32_t CRC32(const uint8_t* ptr,uint32_t len)     //  Algorithm : Direct Table    
{
    uint32_t CrcReg = 0xFFFFFFFF;   
    uint8_t TopByte = 0;
    uint8_t index = 0;
    uint8_t tmp = 0;
    while (0!=len)
    {
        tmp = ExchBitOrder((uint8_t)(*ptr),8);                  //  RefIn  : True
        TopByte = (uint8_t)((CrcReg & 0xFF000000) >> 24);
        CrcReg = (uint32_t)(CrcReg << 8);
        index = (uint8_t)tmp ^ TopByte;
        CrcReg = CrcReg^Table32[index];
        ptr++;
        len--;
    }           
    CrcReg = ExchBitOrder(CrcReg,32);               //  RefOut : True
    CrcReg = CrcReg ^ 0xFFFFFFFF;                   //  XorOut : FFFFFFFF   
    return CrcReg;
}

uint8_t GenerateT32(void)
{
    uint16_t i = 0;
    uint32_t pxp = 0;
    for (i = 0; i < 256; i++)
    {
        pxp = 0;
        for (int8_t nbit = 7; nbit > -1; nbit--)
        {
            if (((i >> nbit) ^ (pxp >> 31)) & 0x00000001)     
            {
                pxp = (pxp << 1) ^ 0x04C11DB7;  //待測數(shù)據(jù)位和pxp高位相異，poly進(jìn)行XOR
            }
            else                                          
            {
                pxp = pxp << 1;  //待測數(shù)據(jù)位和pxp高位相同，poly不進(jìn)行XOR
            }
        }
        Table32[i] = pxp;
    }
    return 0;
}

//  Algorithm : Reflected Direct Table  
uint32_t CRC32Ref(const uint8_t* ptr, uint32_t len)     
{
    uint32_t CrcReg = 0xFFFFFFFF;
    uint8_t TopByte = 0;
    uint8_t index = 0;
    uint8_t tmp = 0;
    while (0 != len)
    {
        tmp = *ptr;                 //  RefIn  : True    X
        TopByte = (uint8_t)(CrcReg & 0x000000FF);
        CrcReg = (uint32_t)(CrcReg >> 8);
        index = (uint8_t)tmp ^ TopByte;
        CrcReg = CrcReg^Table32Ref[index];
        ptr++;
        len--;
    }
//  CrcReg = ExchBitOrder(CrcReg, 32);              //  RefOut : True    X
    CrcReg = CrcReg ^ 0xFFFFFFFF;                   //  XorOut : FFFFFFFF   
    return CrcReg;
}

uint8_t GenerateT32Ref(void)
{
    uint16_t i = 0;
    uint32_t pxp = 0;
    uint8_t iRef = 0;
    for (i = 0; i < 256; i++)
    {
        pxp = 0;
        for (int8_t nbit = 7; nbit > -1; nbit--)
        {
            if (((i >> nbit) ^ (pxp >> 31)) & 0x0001)
            {
                pxp = (pxp << 1) ^ 0x04C11DB7;  //待測數(shù)據(jù)位和pxp高位相異，poly進(jìn)行XOR
            }
            else   
            {
                pxp = pxp << 1;  //待測數(shù)據(jù)位和pxp高位相同，poly不進(jìn)行XOR
            }
        }
        iRef = (uint8_t)ExchBitOrder(i, 8);
        pxp = ExchBitOrder(pxp, 32);
        Table32Ref[iRef] = pxp;
    }
    return 0;
}

uint32_t ExchBitOrder(uint32_t data, uint8_t bitnum)
{
    uint32_t bar = 0;
    for (uint8_t j = 0; j < bitnum; j++)
    {
        if ((data >> j) & 0x01)
        {
            bar = (1 << (bitnum - 1 - j)) | bar;
        }
    }
    return bar;
}
Fig8.png
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。
禁止轉(zhuǎn)載，如需轉(zhuǎn)載請通過簡信或評論聯(lián)系作者。

相關(guān)閱讀更多精彩內(nèi)容

  • 1. 基本概念 1.1 模2運算 ??模2運算是一種二進(jìn)制算法，CRC校驗技術(shù)中的核心部分，因此，我們在分析CRC...
    starmier閱讀 972評論 0贊 1
  • 本文本文主要說兩件事，一是對于網(wǎng)上一些Demo的解釋，借用網(wǎng)友思路的Demo，如有雷同純屬巧合。二是關(guān)于數(shù)據(jù)反轉(zhuǎn)的...
    漠漠彡閱讀 9,677評論 0贊 4
  • 最近剛好有時間，整理了一下關(guān)于CRC的資料，詳細(xì)對比了下程序的實現(xiàn)過程和原理，當(dāng)然，高手都是不在意的。 本文主要介...
    漠漠彡閱讀 26,915評論 1贊 10
  • 姓名：李文杰 (四爺) 公司：中國太平人壽 日期:2018.03.30 【知～學(xué)習(xí)】 《六項精進(jìn)》大綱10遍，累計...
    紋_閱讀 116評論 0贊 0
  • 當(dāng)我沉浸在這個假期過后，孩子能有個質(zhì)的飛躍的暗喜之時，腳下突然一滑，身體在前傾之時，我下意識的往后坐下，伴...
    人生比你想象的要精彩閱讀 218評論 0贊 1

友情鏈接更多精彩內(nèi)容