嵌入式算法之CRC校验算法

数据传输过程中差错不可避免，接收方在收到数据后，先对数据的准确性进行校验，异常数据特殊处理。校验的方式有很多，常见的有CRC循环冗余校验。CRC算法检错能力强，效率高，是信息通信领域最为普遍的校验方式。CRC校验算法应用广，且实现算法简单，但其背后的涉及的纠错码的代数理论，不是一般人可以理解的。所以，在不理解循环校验原理的基础上，贸然分析算法流程是不明智的，根据源码倒推实现流程，也不会明白为什么要这样执行?一般关注CRC以应用为主，以及为什么都是CRC16算法，得出的结果却不同。本文的意图只是这个。

1、CRC定义

假设要发送996这个数字，将其除以7余数为2，发送时将996-2合并后发出，接收方按同样运算判断数据包是否正确。同样的源数据，因为除数不同而余数不同。CRC算法也是因为类似原理。

CRC算法中参数解释如下：

除法定为模2除法

除数定为多项式，如x^16+x^12+x^5+1(0x1021) 2^16+2^12+2^5+2^0=65536+4096+32+1= 69665=0x11021 。依据不可描述的标准，多项式最高位和最低位必须为1，所以一般简化为0x1021，忽略最高位，记为Poly。

因为多项式长度不同，一般分为CRC8、CRC16和CRC32，因为模2除法简化为异或和移位操作，其初始值为Init。

还有三个参数

RefIn：待测数据的每个字节是否按位反转，TRUE或FALSE。

RefOut：在计算后之后，异或输出之前，整个数据是否按位反转，TRUE或FALSE。

XorOut：计算结果与此参数异或后得到最终的CRC值。但是任何数与0异或还是它本身，所以该值为0时可以忽略。

因为多项式Poly，初始值等差异，CRC有不同的版本。理论上是多项式是可以随意定义的，但是通用的标准多项式是经过数学推导的，尽可能的保证不同的数据求出的CRC值不相同。

参考https://crccalc.com/ 的定义，不同场景使用不同的多项式。

2、CRC算法与模板

通用版的CRC算法如下：

CRC8

//以CRC-8/ITU为参考 
unsigned char CRC8(unsigned char *data, unsigned int len) 
{ 
    unsigned char i; 
    unsigned char poly = 0x07;//与表中的Poly列对应 
    unsigned char init = 0x00;//与表中的Init列对应 
 
    unsigned char wChar = 0; 
 
    while (len--) 
    { 
        wChar = *(data++); 
 
        //RefIn为TRUE时执行，FALSE时删除 
        //InvertUint8(&wChar,&wChar); 
 
        init ^= wChar; 
        for( i = 0;i < 8;i++) 
        { 
            if(init & 0x80) 
            { 
                init = (init << 1) ^ poly; 
            } 
            else 
            { 
                init = init << 1; 
            } 
        } 
    } 
 
    //RefOut为TRUE时执行，FALSE时删除 
    //InvertUint8(&init,&init); 
 
    //与XorOut进行异或，若为0时执行或不执行没有区别 
    init=init^0x55; 
 
    return (init); 
 
} 

CRC16

//以CRC-16/X-25为参考 
unsigned short CRC16(unsigned char *data, unsigned int len) 
{ 
    unsigned char i; 
    unsigned short poly = 0x1021;//与表中的Poly列对应 
    unsigned short init = 0xFFFF;//与表中的Init列对应 
    unsigned char wChar = 0; 
 
    while (len--) 
    { 
        wChar = *(data++); 
 
        //RefIn为TRUE时执行，FALSE时删除 
        InvertUint8(&wChar,&wChar); 
 
        init ^= (wChar << 8); 
        for( i = 0;i < 8;i++) 
        { 
            if(init & 0x8000) 
            { 
                init = (init << 1) ^ poly; 
            } 
            else 
            { 
                init = init << 1; 
            } 
        } 
    } 
 
    //RefOut为TRUE时执行，FALSE时删除 
    InvertUint16(&init,&init); 
 
    //与XorOut进行异或，若为0时执行或不执行没有区别 
    init=init^0xFFFF; 
 
    return (init); 
} 

CRC8和CRC16，根据不同版本的参数差异，查表，将模板里的参数改为对应值，即可得出对应版本的CRC值。其中涉及到数据反转的代码如下：

void InvertUint8(unsigned char *DesBuf, unsigned char *SrcBuf) 
{ 
    int i; 
    unsigned char temp = 0; 
 
    for(i = 0; i < 8; i++) 
    { 
        if(SrcBuf[0] & (1 << i)) 
        { 
            temp |= 1 << (7 - i); 
        } 
    } 
    *DesBuf = temp; 
} 
 
void InvertUint16(unsigned short *DesBuf, unsigned short *SrcBuf) 
{ 
    int i; 
    unsigned short temp = 0; 
 
    for(i = 0; i < 16; i++) 
    { 
        if(SrcBuf[0] & (1 << i)) 
        { 
            temp |= 1 << (15 - i); 
        } 
    } 
    *DesBuf = temp; 
} 

3、查表

针对上面的代码，求解CRC移位异或运算的循环体，对时间要求较高的场景，可以提前计算生成数值表，以空间换时间。

//以CRC-8/ITU为例，生成数组查表 
void creatTable(void) 
{ 
    unsigned char i,init; 
    unsigned short j; 
    for(j=0;j<=255;j++) 
    { 
        if(j%16==0) 
        { 
            printf("\r\n"); 
        } 
 
        init=j; 
        for( i = 0;i < 8;i++) 
        { 
            if(init & 0x80) 
            { 
                init = (init << 1) ^ 0x07;//以实际poly为准; 
            } 
            else 
            { 
                init = init << 1; 
            } 
        } 
        printf("0x%02X,", init); 
    } 
} 

确定poly后，假设init为0-255，求出256个参数，转为一维数组。如上，以CRC-8/ITU为例，生成数组如下：

unsigned char crcTable[]={  
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,  
0xE0,0xE7,0xEE,0xE9,0xFC,0xFB,0xF2,0xF5,0xD8,0xDF,0xD6,0xD1,0xC4,0xC3,0xCA,0xCD,  
0x90,0x97,0x9E,0x99,0x8C,0x8B,0x82,0x85,0xA8,0xAF,0xA6,0xA1,0xB4,0xB3,0xBA,0xBD,  
0xC7,0xC0,0xC9,0xCE,0xDB,0xDC,0xD5,0xD2,0xFF,0xF8,0xF1,0xF6,0xE3,0xE4,0xED,0xEA,  
0xB7,0xB0,0xB9,0xBE,0xAB,0xAC,0xA5,0xA2,0x8F,0x88,0x81,0x86,0x93,0x94,0x9D,0x9A,  
0x27,0x20,0x29,0x2E,0x3B,0x3C,0x35,0x32,0x1F,0x18,0x11,0x16,0x03,0x04,0x0D,0x0A,  
0x57,0x50,0x59,0x5E,0x4B,0x4C,0x45,0x42,0x6F,0x68,0x61,0x66,0x73,0x74,0x7D,0x7A,  
0x89,0x8E,0x87,0x80,0x95,0x92,0x9B,0x9C,0xB1,0xB6,0xBF,0xB8,0xAD,0xAA,0xA3,0xA4,  
0xF9,0xFE,0xF7,0xF0,0xE5,0xE2,0xEB,0xEC,0xC1,0xC6,0xCF,0xC8,0xDD,0xDA,0xD3,0xD4,  
0x69,0x6E,0x67,0x60,0x75,0x72,0x7B,0x7C,0x51,0x56,0x5F,0x58,0x4D,0x4A,0x43,0x44,  
0x19,0x1E,0x17,0x10,0x05,0x02,0x0B,0x0C,0x21,0x26,0x2F,0x28,0x3D,0x3A,0x33,0x34,  
0x4E,0x49,0x40,0x47,0x52,0x55,0x5C,0x5B,0x76,0x71,0x78,0x7F,0x6A,0x6D,0x64,0x63,  
0x3E,0x39,0x30,0x37,0x22,0x25,0x2C,0x2B,0x06,0x01,0x08,0x0F,0x1A,0x1D,0x14,0x13,  
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, }; 

原来的直接计算改为查表，如下：

//以CRC-8/ITU为参考 
unsigned char CRC8(unsigned char *data, unsigned int len) 
{ 
    unsigned char i; 
    unsigned char poly = 0x07;//与表中的Poly列对应 
    unsigned char init = 0x00;//与表中的Init列对应 
 
    unsigned char wChar = 0; 
 
    while (len--) 
    { 
        wChar = *(data++); 
 
        //RefIn为TRUE时执行，FALSE时删除 
        //InvertUint8(&wChar,&wChar); 
 
        init ^= wChar; 
 
 
#if 1 
 
        init=crcTable[init];//查表，空间换时间 
#else 
        for( i = 0;i < 8;i++) 
        { 
            if(init & 0x80) 
            { 
                init = (init << 1) ^ poly; 
            } 
            else 
            { 
                init = init << 1; 
            } 
        } 
#endif 
 
    } 
 
    //RefOut为TRUE时执行，FALSE时删除 
    //InvertUint8(&init,&init); 
 
    //与XorOut进行异或，若为0时执行或不执行没有区别 
    init=init^0x55; 
 
    return (init); 
} 

对于CRC16也可以使用查表法。

本文转载自微信公众号「嵌入式系统」，可以通过以下二维码关注。转载本文请联系嵌入式系统公众号。