趁一下热度，发一个自己整理的CRC说明及C语言实现

canspider

最近这个版块CRC的帖子很多，我也来凑个热闹，从代码实现的角度来介绍一下CRC
这里会先介绍CRC的基本运算（1楼、2楼），以及反向计算输入值（3楼），介绍如何反向计算多项式（4楼），CRC计算应用举例（5楼）。
本文提到的所有代码都在这里


CRC其实很简单，以DS18B20的CRC8为例，下面这个图就是CRC计算的全部内容


这个图告诉我们，要计算CRC8，把原来的CRC寄存器中值进行右移，最低位与新来的bit做异或，把这个结果与CRC寄存器中对应的位进行异或，CRC寄存器中就是这一bit的计算结果，要计算多位数据的CRC，那就继续往里移数据。

翻译成代码就是这样的

1. static int bits = 8;
   
2. static uint32_t poly = 0x8c;
   
3. 
   
4. uint32_t crc_1bit(uint32_t init, uint32_t input) {
   
5.   uint32_t xbit = (init ^ input) & 1;
   
6.   init >>= 1;
   
7.   if (xbit) {
   
8.     init ^= poly;
   
9.   }
   
10.   return init & ((1ull << bits) - 1);
    
11. }

复制代码

0x8c = 0b10001100， 多项式正好与上图中寄存器的需要异或的位一一对应。

上面这个函数有两个参数，一个结果，说明CRC计算除了多项式之外，还需要CRC初始值init，和输入值input这两个参数。

至此CRC计算的全部内容就完成了，剩下的就是用不同的多项式，不同的位长度来计算的问题了。
如果我说这就是我整理的CRC，估计你们肯定看了想打人。

其实这个才刚刚开始，接下来才是干货。
根据上面计算1bit CRC值的函数，可以封装出计算多位的CRC函数，如下：

1. uint32_t crc_nbit(uint32_t init, uint32_t input, int n) {
   
2.   for (int i = 0; i < n; i++) {
   
3.     init = crc_1bit(init, input);
   
4.     input >>= 1;
   
5.   }
   
6.   return init;
   
7. }

复制代码

1. uint32_t crc_1byte(uint32_t init, uint8_t input) {
   
2.   for (int i = 0;  i < 8; i++) {
   
3.     init = crc_1bit(init, input);
   
4.     input >>= 1;
   
5.   }
   
6.   return init;
   
7. }

复制代码

有了上面两个函数，可以计算多个位或是一个字节的CRC值了。
估计你们会觉得这玩意会写代码的都知道这么写，不过还没完，我还有干货
计算n位数据CRC值的函数，其中n为CRC位数，如下：

1. uint32_t crc(uint32_t init, uint32_t input)
   
2. {
   
3.   for (int i = 0; i < bits; i++) {
   
4.     init = crc_1bit(init, input);
   
5.     input >>= 1;
   
6.   }
   
7.   return init;
   
8. }

复制代码

计算一串数据CRC值的函数，如下：

1. uint32_t crc_data(uint32_t init, const void* data, int len)
   
2. {
   
3.   const uint8_t* input = (const uint8_t*)data;
   
4.   for (int i = 0; i < len; i++) {
   
5.     init = crc_1byte(init, input[i]);
   
6.   }
   
7.   return init;
   
8. }

复制代码

其实这一楼没啥干货，都是些基本操作。

canspider

前面写了几个CRC计算的基本函数，非常的简单，简单到不值得开一贴来描述。这里还是厚着脸皮再写一点关于计算优化的。
第一个计算1bit数据CRC值的函数，其实站在代码的角度来看的话，就是根据输入bit和原来CRC值的最低位来决定要不要异或多项式。所以计算1 bit的代码还可以写成下面这样
crc_1bit(init, input) = crc_1bit(0, init ^ input ) ^ (init >> 1)
因为输入数据只关心最低位，可以先异或后再输入进去。初始值无论如果都会右移一位，可以在外面右移后再与结果异或。
这样写看起来更麻烦了，但是有个好处，crc_1bit函数只与一个参数有关了。
其实不光是1bit能这样计算，n bit也可以这样计算
crc_nbit(init, input, n) = crc_nbit(0, init ^ input, n) ^ (init >> n)

crc_1byte(init, input) = crc_1byte(0, init ^ input) ^ (init >> 8)
这样可以把crc_1byte函数简化成只有一个参数的，进而将计算转换成查表方式，加快速度。代码如下：

1. uint32_t crc_fast_1byte(uint8_t input) {
   
2.   static uint32_t table[256];
   
3.   static uint32_t table_poly = 0;
   
4.   if (table_poly != poly) {
   
5.     table_poly = poly;
   
6.     for (int i = 0; i < 256; i++) {
   
7.       table[i] = crc_1byte(0, i);
   
8.     }
   
9.   }
   
10.   return table_poly == poly ? table[input & 0xff] : crc_1byte(0, input);
    
11. }

复制代码

1. uint32_t crc_fast(uint32_t init, const void* data, int len)
   
2. {
   
3.   const uint8_t* input = (const uint8_t*)data;
   
4.   for (int i = 0; i < len; i++) {
   
5.     init = crc_fast_1byte(input[i]^ init) ^ (init >>8);
   
6.   }
   
7.   return init;
   
8. }

复制代码

前面有一个计算n位CRC值函数，这个函数由于计算的位数与CRC位数相同，init>>n之后为0，还可以写成这样:
result = crc(init, input) = crc(0, init ^ input)

至此CRC的基本计算就完成了，接下来介绍如何根据CRC结果计算输入数据。

canspider

如果我们只知道CRC结果，能不能反过来计算出输入数据呢？答案是肯定的。
我们先做一个反向计算一位输入数据的函数
通过观察crc_1bit函数，我们会发现，要想知道输入的数据，其实只要看CRC结果的最高位就行了
如果结果最高为1，必然做过次异或操作，输入bit与初始CRC值异或后为1，即输入bit与初始CRC值最低位不同
如果结果最高为0，没有做过次异或操作，输入bit与初始CRC值异或后为0，即输入bit与初始CRC值最低位相同
有了这个信息，反向计算一位的函数很容易实现

1. uint32_t crc_rev_1bit_input(uint32_t init, uint32_t result)
   
2. {
   
3.   uint32_t mask = 1ul << (bits - 1);
   
4.   if (result & mask) {
   
5.     return (init ^ 1) & 1;
   
6.   }
   
7.   return init & 1;
   
8. }

复制代码

然后再做一个根据输入数据，反向计算初始CRC值的函数
再观察crc_1bit函数，还是看CRC结果的最高位，如果为1，做了过异或操作，如果不为1，没有做异或操作。
与反向计算1bit不同的是，这里除了要关心最低位是否与输入值相同，还需要将结果左移后再异或上多项式，代码如下：

1. uint32_t crc_rev_1bit_init(uint32_t input, uint32_t result)
   
2. {
   
3.   uint32_t init;
   
4.   uint32_t mask = 1ul << (bits - 1);
   
5.   if (result & mask) {
   
6.     init = (result ^ poly) << 1;
   
7.     init |= (input ^ 1) & 1;
   
8.   }
   
9.   else {
   
10.     init = result << 1;
    
11.     init |= (input ^ 0) & 1;
    
12.   }
    
13.   return init & ((1ull << bits) - 1);
    
14. }

复制代码

有了这两个函数做基础，就可以反向计算任意位的CRC值了
反向计算输入值的逻辑稍微有一点绕，先计算出每一位CRC值的计算方式
然后再根据这个计算方式，把真实的初始值代入进去计算，根据每一步的结果调整输入数据，最后得到真实的输入数据，代码如下：

1. uint32_t crc_rev(uint32_t init, uint32_t result)
   
2. {
   
3.   uint32_t calc_map = 0;
   
4.   for (int i = 0; i < bits; i++) {
   
5.     calc_map <<= 1;
   
6.     calc_map |= crc_rev_1bit_input(0, result);
   
7.     result = crc_rev_1bit_init(calc_map, result);
   
8.   }
   
9.   uint32_t r = 0;
   
10.   for (int i = 0; i < bits; i++) {
    
11.     uint32_t xbit = (calc_map ^ init) & 1;
    
12.     init = crc_1bit(init, xbit);
    
13.     r <<= 1;
    
14.     r |= xbit;
    
15.     calc_map >>= 1;
    
16.   }
    
17.   return rev_bits(r, bits);
    
18. }

复制代码

代码中calc_map含义是，当前这一位的CRC必须按照这样方式来计算：0不异或，1异或。有了计算方式后，再把初始值代入进去，得到每一位输入值。

input = crc_rev(init, result)
前面我们提到
result = crc(init, input) = crc(0, init ^ input)
所以
init_xor_input = crc_rev(0, result)
input = init_xor_input ^ init = crc_rev(0, result) ^ init
init = init_xor_input ^ input = crc_rev(0, result) ^ input

有了crc和crc_rev这两个函数，可以根据init, input, result这三个条件中的任意两个，求出第三个，这就是CRC反向计算。

canspider

既然输入结果可以反向计算得到，如果初始值init，输入值input以及结果result都有了，能不能计算出CRC多项式呢？
答案是可以，不过CRC多项式的计算方法需要用到CRC计算的数学原理，不能单靠代码实现来反推出多项式计算公式。
CRC计算用数学的话说叫做求余数
比如求8位CRC，8位CRC的多项式是9位的，代码实现一般忽略掉最高位的1。然后在待校验数据的后面补充8个0，然后用这个补了0数据除以多项式，余数就是CRC结果。
而CRC的初始值可以看作是上次计算的余数，加到当前数据上一起进行计算就行了。
result = crc(init, input) 写成数学公式就是
result = ( (input + init ) << n ) % poly
在GF(2)这个域中，加减都是不进位的异或计算，这也是为什么前面 result = crc(init, input) 也可以写成 crc(0, init ^ input)

前面这个公式中result, input, init都是已知，要求poly，相当于已知一个被除数 x，其余数是r，求除数p。
其中 x = ( (input + init ) << n )，r = result, p = poly
先不管CRC的特殊计算，放在普通数学计算中，这个其实也比较麻烦。
相当于 x % p = r，已知x，r求p。
这里我们可以知道 x - r可以被p整除，如果将x-r进行因式分解，那么p一定是某些分解出来因子的乘积。
由于CRC多项式一定是奇数，所以只用考虑分解来出的奇数因子，将这些因子乘起来，如果结果位数与多项式位数相同，那么它就可能是多项式的一个解。
求多项式的算法就是这样的：
先计算出x，即 ((init + input) << n) + result，在GF(2)中加减都是异或操作，x = ((init ^ input) << n) ^ result
然后将x进行因式分解，只要奇数因子，不要2和1。
将这些因子乘起来，满足多项式位数的就是最终结果。
主要代码如下，完整代码在1楼的附件中：

1. int crc_rev_poly(uint32_t init, uint32_t input, uint32_t result, uint32_t* poly_buffer, int poly_buffer_len)
   
2. {
   
3.   if (bits > 16)return 0;
   
4.   uint32_t data = (rev_bits(init ^ input, bits) << bits) | rev_bits(result, bits);
   
5. 
   
6.   uint32_t factor[FACTOR_MAX_CNT];
   
7.   int count = get_odd_factor(data, factor, FACTOR_MAX_CNT);
   
8. 
   
9.   if (count > FACTOR_MAX_CNT || count < 1) {
   
10.     printf("Factor overflow or underflow, %d\n", count);
    
11.     count = FACTOR_MAX_CNT;
    
12.     return 0;
    
13.   }
    
14. 
    
15.   count = guess_result(factor, count, poly_buffer, poly_buffer_len);
    
16.   for (int i = 0; i < count; i++) {
    
17.     poly_buffer[i] = rev_bits(poly_buffer[i], bits) & ((1ul << bits) - 1);
    
18.   }
    
19.   return count;
    
20. }

复制代码

其中比较复杂是的因式分解，需要先计算出GF(2)上的素数，再用这些素数去分解x
这样计算出的结果可能会有多个，一般多取几组数据就可以确定最终结果
之前的CRC计算都是右移方式计算，这里为了方便进行因式分解，采用了左移方式计算，因此数据在输入和输出的时候进行了位反转操作。

canspider

本文中的CRC计算都是右移计算的，实际上有左移也有右移，这些计算都可以通过右移来实现。完整的CRC计算代码如下：

1. uint32_t crc_calc(const void* data, int len, uint32_t init, uint32_t xor_out, uint32_t polynomial, int bit_count, uint32_t shift_right)
   
2. {
   
3.   const uint8_t* pdata = (const uint8_t*)data;
   
4.   bits = bit_count;
   
5.   poly = rev_bits(polynomial, bit_count);
   
6.   init = rev_bits(init, bit_count);
   
7.   if (shift_right) {
   
8.     init = crc_fast(init, data, len);
   
9.   }
   
10.   else {
    
11.     for (int i = 0; i < len; i++) {
    
12.       init = crc_1byte(init, rev_bits(pdata[i], 8) & 0xfful);
    
13.     }
    
14.     init = rev_bits(init, bit_count);
    
15.   }
    
16.   init ^= xor_out;
    
17.   init &= (uint32_t)((1ull << bit_count) - 1);
    
18.   return init;
    
19. }

复制代码

指定初始值，输出是否需要异或，多项式，位数以及右移计算还是左移计算。
一般多项式的最高位在左边，因此右移计算时需要先将多项式和初始值反向。如果是右移计算，直接调用快速计算函数。
如果是左移计算，按字节反转后再进行计算，并在计算完成后将结果反转。
最后根据需要将输出值进行异或。
此计算方式与网站　https://crccalc.com/ 上的计算结果一致。网站上默认为左移，所以RefIn为true的时候表示反向，是右移。
如果采用标准CRC，能在这里面找到结果。
一些计算标准CRC值的例子

1.   printf("============== CRC8 results ============\n");
   
2.   printf("CRC8               = 0x%02X\n", crc_calc(data, len, 0x00, 0x00, 0x07, 8, LEFT));
   
3.   printf("CRC8/CDMA200       = 0x%02X\n", crc_calc(data, len, 0xff, 0x00, 0x9b, 8, LEFT));
   
4.   printf("CRC8/DARC          = 0x%02X\n", crc_calc(data, len, 0x00, 0x00, 0x39, 8, RIGHT));
   
5.   printf("CRC8/DVB-S2        = 0x%02X\n", crc_calc(data, len, 0x00, 0x00, 0xd5, 8, LEFT));
   
6.   printf("CRC8/EBU           = 0x%02X\n", crc_calc(data, len, 0xff, 0x00, 0x1d, 8, RIGHT));
   
7.   printf("CRC8/I-CODE        = 0x%02X\n", crc_calc(data, len, 0xfd, 0x00, 0x1d, 8, LEFT));
   
8.   printf("CRC8/ITU           = 0x%02X\n", crc_calc(data, len, 0x00, 0x55, 0x07, 8, LEFT));
   
9.   printf("CRC8/MAXIM         = 0x%02X\n", crc_calc(data, len, 0x00, 0x00, 0x31, 8, RIGHT));
   
10.   printf("CRC8/ROHC          = 0x%02X\n", crc_calc(data, len, 0xff, 0x00, 0x07, 8, RIGHT));
    
11.   printf("CRC8/WCDA          = 0x%02X\n", crc_calc(data, len, 0x00, 0x00, 0x9b, 8, RIGHT));

复制代码

1.   printf("============== CRC32 results ===========\n");
   
2.   printf("CRC-32             = 0x%08X\n", crc_calc(data, len, 0xFFFFFFFF, 0xFFFFFFFF, 0x04C11DB7, 32, RIGHT));
   
3.   printf("CRC-32/BZIP2       = 0x%08X\n", crc_calc(data, len, 0xFFFFFFFF, 0xFFFFFFFF, 0x04C11DB7, 32, LEFT));
   
4.   printf("CRC-32C            = 0x%08X\n", crc_calc(data, len, 0xFFFFFFFF, 0xFFFFFFFF, 0x1EDC6F41, 32, RIGHT));
   
5.   printf("CRC-32D            = 0x%08X\n", crc_calc(data, len, 0xFFFFFFFF, 0xFFFFFFFF, 0xA833982B, 32, RIGHT));
   
6.   printf("CRC-32/MPEG-2      = 0x%08X\n", crc_calc(data, len, 0xFFFFFFFF, 0x00000000, 0x04C11DB7, 32, LEFT));
   
7.   printf("CRC-32/POSIX       = 0x%08X\n", crc_calc(data, len, 0x00000000, 0xFFFFFFFF, 0x04C11DB7, 32, LEFT));
   
8.   printf("CRC-32Q            = 0x%08X\n", crc_calc(data, len, 0x00000000, 0x00000000, 0x814141AB, 32, LEFT));
   
9.   printf("CRC-32/JAMCRC      = 0x%08X\n", crc_calc(data, len, 0xFFFFFFFF, 0x00000000, 0x04C11DB7, 32, RIGHT));
   
10.   printf("CRC-32/XFER        = 0x%08X\n", crc_calc(data, len, 0x00000000, 0x00000000, 0x000000AF, 32, LEFT));

复制代码

根据CRC结果凑数据
当我们需要得到指定的CRC结果时，可以用反向计算的方式来凑出需要的数据。
具体做法是，先给出CRC计算方式、一串数据和一个结果，指定在数据中插入调整数据的位置，调整数据的长度与CRC位数一致。
先从头开始计算直到调整数据前CRC值，再从后向先前算出经过调整数据之后的CRC值，根据一前一后的CRC值得到调整数据。代码如下：

1. uint32_t crc_patch(const void* pre_data, int pre_len, const void* post_data, int post_len, uint32_t init, uint32_t result)
   
2. {
   
3.   uint32_t pre_result = crc_data(init, pre_data, pre_len);
   
4.   uint32_t post_result = result;
   
5.   int data_len = bits / 8;
   
6.   while (post_len >= data_len) {
   
7.     uint32_t data = 0;
   
8.     memcpy(&data, (char*)post_data + post_len - data_len, data_len);
   
9.     post_result = crc_rev(0, post_result) ^ data;
   
10.     post_len -= data_len;
    
11.   }
    
12.   while (post_len > 0) {
    
13.     uint32_t data = 0;
    
14.     memcpy(&data, (char*)post_data + post_len - 1, 1);
    
15.     data = rev_bits(data, 8);
    
16.     for (int i = 0; i < 8; i++) {
    
17.       post_result = crc_rev_1bit_init(data, post_result);
    
18.       data >>= 1;
    
19.     }
    
20.     post_len--;
    
21.   }
    
22.   return crc_rev(pre_result, post_result);
    
23. }

复制代码

wajlh

顶一下        

KongQuan

顶一下。

jianbo513

不错，多谢分享

McuPlayer

写得挺好，已收藏，有大块时间的时候仔细看

ldj7501

顶一下！

kinoko

听老师讲课

我是一个大白菜

感谢分享，再巩固一下

huangqi412

支持 写的很好

yanyanyan168

多谢分享！收藏之

qinglong

写的不错，收藏

823032003

感谢分享。

一号纵队

收藏，学习下。

贰梓

收藏学习

1785345205

谢谢分享，解释清晰

brother_yan

这个靠谱

jiaowoxiaolu

干货！感谢分享

xmm

感谢分享

wahaha

写的不错，感谢分享

Jmhh247

干，真的是干货，通俗易懂，接地气！

lyg407

谢谢分享。

amxx

没想到楼主对CRC研究得这么深入。佩服！

liufabing

感谢,先收藏

小柿子

谢谢分享，解释清晰 ,收藏学习了

zaldy30

收藏，谢谢分享。

zyqcome

谢谢分享

newlife2lyf

干,真干货,这才是我们需要的真正干货.

WillFeng

重量级的帖子，学习了。

596142041

感谢分享,一直在用CRC,也一直没明白实现的原理

kakashi007

顶一下。

dory_m

写得挺好，已收藏，学习！！！

mculjf

感谢分享，收藏学习！！！

chen849928055

收藏，一直用，没仔细研究过

zhongsandaoren

CRC 学习了

shiyuzuxia1111

知其然知了所以然，谢谢楼主分享

sml009

学习                              

hotpower

canspider 发表于 2019-9-20 23:33
本文中的CRC计算都是右移计算的，实际上有左移也有右移，这些计算都可以通过右移来实现。完整的CRC计算代码 ...

www.hotcrc.com

很不错~~~但是看不清规律（可逆性）

hotpower

菜农正准备直播：超级CRC计算器HotCRC之CRC算法演示

CRC算法自动生成演示讲义
1.CRC表格的来龙去脉
以CRC8为例
表格分大表256个字节，小表16个系字节
前者是对数据0x00-0xFF的连续CRC运算的结果
后者分为左移算法为数据0x00-0x0F的连续CRC运算结果。右移算法为数据左移*0x10，即
0x00，0x10，0x20，……，0xE0，0xF0。
双表从CRC16开始，特别适合低位数的MCU运算高位数的CRC。
例如CRC16，本身是16位，但却运行的是8位。
2.CRC表格和算法
www.hotcrc.com对外公开的算法为5种，其中前四种为查表算法，最后为移位算法。
查表算法是以空间换取时间，而移位算法时间换取空间。
查表分为四种组合：
大表-单表，大表-双表。(每表256)
小表-单表，小表-双表。(每表16个)
移位算法就一种：移位

hotpower

http://bbs.hotfsp.com/index.php?topic=138.0

unnormal

谢谢分享

liufabing

感谢分享，收藏学习

四叶草35

不错支持一下