CRC算法

CRC校验算法

https://www.52pojie.cn/thread-783879-1-1.html

¶0x00-CRC校验原理

CRC校验即循环冗余判断，是基于数据计算一组的校验码，用于核对数据传输过程中是否被更改或传输错误。首先看两个概念，后续会用到

• 模2除法：也叫模2运算，就是结果除2后取余数。 数据传输过程中是否被更改或传输错误。首先看两个概念，后续会用到

• 多项式与二进制：二进制可以表示成多项式的形式，比如二进制1101可以表示为：
  $$
  x^3+x2+x^0
  $$
  1011表示为：
  $$
  x^3+x1+x^0
  $$

CRC校验本质上是选取一个合适的除数，要进行校验的数据是除数，然后做模2除法，得到的余数就是CRC校验值

最终传输的数据是我们的数据加上CRC校验值，而CRC的数据存储在数据的末尾，添加的位数根据除数来判断

余数位必须比除数少一位，如果不够前面加0补齐

¶CRC生成多项式

通常我们把选出的除数称为生成多项式，对于我们来说，直接拿来使用即可

因为生成多项式的最高位肯定为1，所以在简记式中可以去掉，所以位宽等于多项式对应的二进制的位数-1，CRC8本来是9位，但是省去最高位1，得到八位，所以CRC校验值为8位

¶0x01-计算过程

¶根据CRC原理实现校验

这里我们以CRC16为例，即选取生成多项式为0x8005

1. 在数据末尾添加十六位CRC校验值0
2. 如果最高位为1，数据左移后异或生成的多项式
3. 如果数据最高位为0，直接左移
4. 这样得到的低十六位就是我们的CRC校验值

这样就完成了一个字节的校验

CRC校验有很多种类型，这上面介绍了不同的计算类型

¶代码实现

以CRC16为例

因为一个字符是8位，所以CRC16本身会左移8位，所以在开始前 需要先左移8位，这样得到的才会是十六位数据

¶0x01-CRC检验过程改进

CRC查表法

由于每一个字节都需要进行8次的判断、移位和异或操作。如果使用查表法

因为加密的是一个字符，最多就256个，也就是8位，所以使用查表法效率较高

下面是生成CRC-8表的代码

#include<stdio.h>
#include<string.h>
//每个字符传进来进行CRC8计算
unsigned char crc_high_first(unsigned char ptr)
{
    unsigned char i;
    unsigned char crc = ptr;

    for (i = 8; i > 0; --i)   /* 下面这段计算过程与计算一个字节crc一样 */
    {
        if (crc & 0x80)
            crc = (crc << 1) ^ 0x31;
        else
            crc = (crc << 1);
    }
    return (crc);
}
void  create_crc_table()
{
    unsigned short i;
    unsigned char j;
    for (i = 0; i <= 0xFF; i++)
    {
        if (0 == (i % 16))
            printf("\n");
        j = i & 0xFF;
        printf("0x%.2x, ", crc_high_first(j));  /*依次计算每个字节的crc校验值*/
    }
}
int main()
{
    create_crc_table();
	return 0;
}

CRC8查表法

#include<stdio.h>
#include<string.h>

static const unsigned char crc_table[] =
{
0x00,0x31,0x62,0x53,0xc4,0xf5,0xa6,0x97,0xb9,0x88,0xdb,0xea,0x7d,0x4c,0x1f,0x2e,0x43,0x72,0x21,0x10,0x87,0xb6,0xe5,0xd4,0xfa,0xcb,0x98,0xa9,0x3e,0x0f,0x5c,0x6d,0x86,0xb7,0xe4,0xd5,0x42,0x73,0x20,0x11,0x3f,0x0e,0x5d,0x6c,0xfb,0xca,0x99,0xa8,0xc5,0xf4,0xa7,0x96,0x01,0x30,0x63,0x52,0x7c,0x4d,0x1e,0x2f,0xb8,0x89,0xda,0xeb,0x3d,0x0c,0x5f,0x6e,0xf9,0xc8,0x9b,0xaa,0x84,0xb5,0xe6,0xd7,0x40,0x71,0x22,0x13,0x7e,0x4f,0x1c,0x2d,0xba,0x8b,0xd8,0xe9,0xc7,0xf6,0xa5,0x94,0x03,0x32,0x61,0x50,0xbb,0x8a,0xd9,0xe8,0x7f,0x4e,0x1d,0x2c,0x02,0x33,0x60,0x51,0xc6,0xf7,0xa4,0x95,0xf8,0xc9,0x9a,0xab,0x3c,0x0d,0x5e,0x6f,0x41,0x70,0x23,0x12,0x85,0xb4,0xe7,0xd6,0x7a,0x4b,0x18,0x29,0xbe,0x8f,0xdc,0xed,0xc3,0xf2,0xa1,0x90,0x07,0x36,0x65,0x54,0x39,0x08,0x5b,0x6a,0xfd,0xcc,0x9f,0xae,0x80,0xb1,0xe2,0xd3,0x44,0x75,0x26,0x17,0xfc,0xcd,0x9e,0xaf,0x38,0x09,0x5a,0x6b,0x45,0x74,0x27,0x16,0x81,0xb0,0xe3,0xd2,0xbf,0x8e,0xdd,0xec,0x7b,0x4a,0x19,0x28,0x06,0x37,0x64,0x55,0xc2,0xf3,0xa0,0x91,0x47,0x76,0x25,0x14,0x83,0xb2,0xe1,0xd0,0xfe,0xcf,0x9c,0xad,0x3a,0x0b,0x58,0x69,0x04,0x35,0x66,0x57,0xc0,0xf1,0xa2,0x93,0xbd,0x8c,0xdf,0xee,0x79,0x48,0x1b,0x2a,0xc1,0xf0,0xa3,0x92,0x05,0x34,0x67,0x56,0x78,0x49,0x1a,0x2b,0xbc,0x8d,0xde,0xef,0x82,0xb3,0xe0,0xd1,0x46,0x77,0x24,0x15,0x3b,0x0a,0x59,0x68,0xff,0xce,0x9d,0xac
};
//每个字符传进来进行CRC8计算
unsigned char crc_high_first(unsigned char ptr)
{
    unsigned char i;
    unsigned char crc = ptr;

    for (i = 8; i > 0; --i)   /* 下面这段计算过程与计算一个字节crc一样 */
    {
        if (crc & 0x80)
            crc = (crc << 1) ^ 0x31;
        else
            crc = (crc << 1);
    }
    return (crc);
}
void  create_crc_table()
{
    unsigned short i;
    unsigned char j;
    for (i = 0; i <= 0xFF; i++)
    {
        if (0 == (i % 16))
            printf("\n");
        j = i & 0xFF;
        printf("0x%.2x, ", crc_high_first(j));  /*依次计算每个字节的crc校验值*/
    }
}
void find_crc_table()
{
    unsigned char crc = 0x00;
    unsigned char key = 0x31;
    printf("0x%x\n", crc_table[crc ^ 0x31]);
}
void crc_8_encode()
{
    unsigned char crc=0x00;
    unsigned char key = 0x31;
    crc ^= key;
    for (int i = 0; i < 8; ++i)
    {
        if (crc & 0x80)
        {
            crc = (crc << 1) ^ 0x31;
        }
        else
        {
            crc <<= 1;
        }
        
    }
    printf("0x%x", crc);
    return;
}
int main()
{
    //create_crc_table();
    find_crc_table();
    crc_8_encode();
	return 0;
}

CRC16和CRC32也同理

只是初始时移动的位数改变