第1页 / 共31页
第2页 / 共31页
第3页 / 共31页
第4页 / 共31页
第5页 / 共31页
第6页 / 共31页
第7页 / 共31页
第8页 / 共31页
我学习CRC32、CRC16、CRC原理和算法的总结(与WINRAR结果一致.pdf
我学习 CRC32、CRC16、CRC 原理和算法的总结（与 WINRAR 结果一致）
wxleasyland(wxlwww@gmail.com)
2010 年 9 月 2 日
比较愚钝，学了 CRC 校验好几天，很痛苦的过程，现终于有眉目了，总结一下。
国外版的“轻松无痛苦学习 CRC 指南”，在
http://www.repairfaq.org/filipg/LINK/F_crc_v31.html
（为什么好的资料都是老外写的？）我的英文有限，这种专业性太强的文章，很多都看不太明白，所
以没办法翻译，靠参考国内的翻译和自己瞎琢磨的。
国内的翻译比较不全，而且有点误导，能看英文的还是看英文吧，国内版资料比较零散，可参考：
http://www.q.cc/2001/12/08/10190.html
http://www.360doc.com/content/10/0703/12/1317564_36621098.shtml
http://www.yuanma.org/data/2006/1010/article_1637.htm
我结合国内资料和英文原版进行总结，达到和 WINRAR 一样的 CRC32 计算结果。
一、 CRC 原理
可参考 http://www.luocong.com/articles/show_article.asp?Article_ID=15
计算 CRC 的过程，就是用一个特殊的“除法”，来得到余数，这个余数就是 CRC。
它不是真正的算术上的除法！过程和算术除法过程一样，只是加减运算变成了 XOR（异或）运算！
算术上的除法：
120÷9＝13 余 3，120 是被除数，9 是除数，13 是商，3 是余数。念作 120 除以 9，或者 9 除 120，或
者 9 去除 120！（除法的过程就不写了）
这个除法计算机当然会做，但是做起来很麻烦，因为减法有借位，很耗时间和指令!
所以，计算 CRC 也是除法，但是用 XOR 来代替减法，这就简单多了！
CRC 的除法：
120÷9＝14 余 6，商、余数和算术除法不一定相同！！因为除法用的是 XOR，而不是真正的减法。
以二进制模拟这个计算过程：
1110 商为 1110，即 14，商有 4 位，表示进行了 4 次 XOR
________
1001/1111000 被除数 120 是 1111000，除数 9 是 1001
1001 ^
----
1100 第一次 XOR 后得到 011，加入下一位 0。最高位的 0 可以消掉了，这样最高位是 1,所以下个商是 1
1001 ^
----
1010 第二次 XOR 后得到 0101，加入下一位 0。最高位的 0 可以消掉了，这样最高位是 1,所以下个商是 1
1001 ^
----
0110 第三次 XOR 后得到 0011，加入下一位 0。最高位的 0 可以消掉了，这样最高位是 0,所以下个商是 0
0000 ^
----
110 -> 最后一次 XOR 后得到 0110，最高位的 0 可以消掉了，得到余数为 110，即 6
注意，余数不是 0110，而是 110，因为最前面那个 0 已经被 XOR 后消掉了！
可见，除法（XOR）的目的是逐步消掉最高位的 1 或 0！
由于过程是 XOR 的，所以商是没有意义的，我们不要。我们要的是余数。
余数 110 是 1111000 的 CRC 吗？不是！
余数 110 是 1111（即十进制 15）的 CRC！！！
为什么？因为 CRC 是和数据一起传送的，所以数据后面要加上 CRC。
数据 1111 加上 CRC110 后，变成 1111110，再传送。接收机收到 1111110 后，除以除数 1001，余数为
000，正确；如果余数不为 0，则说明传送的数据有误！这样完成 CRC 校验。
即发送端要发送 1111，先在 1111 后加 000，变成 1111000，再除以 1001 得到余数 110，这个 110
就是 CRC，将 110 加到数据后面，变成 1111110，发送出去。
接收端收到 1111110，用它除以 1001，计算得余数为 000，就说明收到的数据正确。
所以原始数据后面要先扩展出 3 位 0，以容纳 CRC 值！
会发现，在上面的除法过程中，这 3 位 0，能保证所有的 4 个数据位在除法时都能够被处理到！不然做
一次除法就到结果了，那是不对的。这个概念后面要用到。
所以，实际上，数据是 1111，CRC 是 110。
对于除数 1001，我们叫它生成多项式，即生成项，或 POLY，即 g(x)。
数据 1111 根据 POLY1001，计算得到 CRC110。
如果 POLY 不是 1001，而是 1011，那得到的 CRC 也是不同的！
所以生成项不同，得到的 CRC 也不同。要预先定义好 POLY，发送端和接收端要用一样的 POLY！
二、 生成项
上面例子中，生成项是 1001，共 4 位比特，最高位的 1，实际上在除法的每次 XOR 时，都要消掉，所
以这个 1 可不做参考，后 3 位 001 才是最重要的！001 有 3 位，所以得到的余数也是 3 位，因为最后一次除
法 XOR 时，最高位消掉了。所以 CRC 就是 3 位比特的。
CRC 是 3 比特，表示它的宽度 W＝3。也就是说，原始数据后面要加上 W=3 比特的 0 进行扩展！
生成项的最低位也必须是 1，这是规定的。
生成项 1001，就等效于 g(x)=x2+1
生成项也可以倒过来写，即颠倒过来，写成 1001，这里倒过来的值是一样的。
再如 CRC32 的生成项是：
1 0000 0100 1100 0001 0001 1101 1011 0111 （33 个比特）
即 g(x)= x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1
颠倒过来，就可以写成 1110 1101 1011 1000 1000 0011 0010 0000 1
一般生成项简写时不写最高位的 1，故生成项是 0x04C11DB7，颠倒后的生成项是 0xEDB88320
CRC32 的生成项是 33 比特，最高位是消掉的，即 CRC 值是 32 比特（4 个字节），即宽度 W=32，就是说，
在计算前，原始数据后面要先扩展 W=32 个比特 0，即 4 个 0x00 字节。
注意：我看到网上 CRC32 的 POLY 有 0x04C10DB7 这个值的，它和正规的 POLY 值不同，需要注意！
颠倒过来，即是镜像，为什么要颠倒，后述。
三、 直接计算法 Straightforward CRC Implementation
“直接计算法”就是直接模拟上面的除法的过程，来得到余数即 CRC！
上面的例子中，除数是 4 位，但最高位是要一直消掉的，所以我们只需要一个 3 位的寄存器就好了。
计算过程：
待测数据后扩展 W=3 个比特 0，变成 1111000；
寄存器初始化置 0；
先在寄存器中移入数据 111；
寄存器左移一位，并且右边移入下一位数据 1。这样最高位 1 移出，由于最高位是 1，故本次的商
是 1，要用除数 1001 来进行 XOR，最高位肯定 XOR 得 0，故不管它，只要用低 3 位 001 来进行 XOR 就可
以，即 001 对寄存器进行 XOR，寄存器中得到 110，即第一次 XOR 后的结果（相当于是数据 1111 与生
成项 1001 进行了一次 XOR，并把最高位 0 消掉了）。 如果移出的最高位是 0，则用 0000 来进行 XOR（0
XOR 后，得到的还是原值）。
一直重复这个过程，就能得到最后余数了。
总共处理次数＝商的位数＝待测数据的位数－生成项位数＋1＋宽度 W＝待测数据的位数＝4 次。
我们假设待测数据是 1101 0110 11，生成项是 10011，假设有一个 4 bits 的寄存器，通过反复的移位
和进行 CRC 的除法，最终该寄存器中的值就是我们所要求的余数。
3 2 1 0 Bits
+---+---+---+---+
Pop <-- | | | | | <----- Augmented message（已加 0 扩张的原始数据）
+---+---+---+---+
1 0 0 1 1 = The Poly 生成项
依据这个模型，我们得到了一个最最简单的算法：
把 register 中的值置 0.
把原始的数据后添加 w 个 0.
While (还有剩余没有处理的数据)
Begin
把 register 中的值左移一位，读入一个新的数据并置于 register 最低位的位置。
If (如果上一步的左移操作中的移出的一位是 1)
register = register XOR Poly.
End
实际上就是模拟 XOR 除法的过程，即被测数据一位一位放到寄存器中来做除法。
比如生成项是 10011，则生成的余数是 4 位 XXXX，所以寄存器是 4 位。
待测数据是 1101 0110 11，后面加上 0000，即扩张 4 位，以容纳余数。
只要与生成项的 0011 做 XOR 就好了，最高位经过 XOR 肯定出 0，可不用最高位。
过程如下：
待测数据先移 4 位即 1101 到寄存器中，准备开始除法。
第 1 次除法：寄存器中是 1101，先从寄存器移出最高位 1，移进下一位待测数据位 0，则寄存器中是
1010，由于移出的位是 1，则需要与生成项的 0011 做 XOR，得到 1001，即做了第 1 次除法后，寄存器中是
1001，这个就是余数。
第 2 次除法：寄存器中是 1001，从寄存器移出最高位 1，移进下一位待测数据位 1，则寄存器中是 0011，
由于移出的位是 1，则需要与生成项的 0011 做 XOR，得到 0000，即做了第 2 次除法后，寄存器中是 0000，
这个就是余数。
第 3 次除法：寄存器中是 0000，从寄存器移出最高位 0，移进下一位待测数据位 1，则寄存器中是 0001，
由于移出的位是 0，则需要不做 XOR，直接下一步移位。也可以等同于：本次的商是 0,0*生成项＝0，即是
0000 与寄存器做 XOR，得到寄存器的数不变，还是 0001，即做了第 3 次除法后，寄存器中是 0001，这个就
是余数。
第 4 次除法：寄存器中是 0001，从寄存器移出最高位 0，移进下一位待测数据位 0，则寄存器中是 0010，
由于移出的位是 0，则需要不做 XOR，直接下一步移位。
第 5 次除法：移位，不用做 XOR，得到寄存器中是 0101
第 6 次除法：移位，不用做 XOR，得到寄存器中是 1011
第 7 次除法：移位，移出的位是 1，又要与生成项做 XOR 了
一直做下去。。。。。。直到最后，寄存器中的就是整个计算后的余数了。即 CRC 值。
注意：
这个算法，计算出的 CRC32 值,与 WINRAR 计算出来的不一样，为什么？算法是正确的，不用怀疑！只
是 CRC32 正式算法还涉及到数据颠倒和初始化预置值等，后述。
程序实现：
程序 1：
（注：网上下的程序是有错的，我有修改了，这里是正确的）
//网上的程序经修改
BYTE POLY=0x13; //
unsigned short data = 0x035B; // 待测数据是 35BH，12 比特，注意，数据不是 16 比特
unsigned short regi = 0x0000; // load the register with zero bits
// augment the data by appending W(4) zero bits to the end of it.
//按 CRC 计算的定义，待测数据后加入 4 个比特 0，以容纳 4 比特的 CRC；
生成项，13H＝10011，这样 CRC 是 4 比特
做最后一次 XOR
这 1 比特加载到寄存器中
//这样共有 16 比特待测数据，从第 5 比特开始做除法，就要做 16－5＋1＝12 次 XOR
data <<= 4;
// we do it bit after bit
for ( int cur_bit = 15; cur_bit >= 0; -- cur_bit ) //处理 16 次，前 4 次实际上只是加载数据
{
// test the highest bit which will be poped later.
/// in fact, the 5th bit from right is the hightest bit here
if ( ( ( regi >> 4 ) & 0x0001 ) == 0x1 ) regi = regi ^ POLY;
regi <<= 1; // shift the register
// reading the next bit of the augmented data
unsigned short tmp = ( data >> cur_bit ) & 0x0001; // 加载待测数据 1 比特到 tmp 中，tmp 只有 1 比特
regi |= tmp; //
}
if ( ( ( regi >> 4 ) & 0x0001 ) == 0x1 ) regi = regi ^ POLY; //
//这时， regi 中的值就是 CRC
程序 2：我做的通用 CRC 计算程序：
_int64 POLY = 0x104C11DB7; // 生成项，需要含有最高位的"1"，这样 CRC 是 32 比特
int crcbitnumber=32; //crc
_int64 data = 0x31323334; //
int databitnumber=32; //
_int64 regi = 0x0; // load the register with zero bits
// augment the data by appending W zero bits to the end of it.
//按 CRC 计算的定义，加入 32 个比特 0，以容纳 32 比特的 CRC；
//这样共有 64 比特待测数据，从第 33 比特开始做除法，就要做 64－33＋1＝32 次 XOR
data <<= crcbitnumber;
// we do it bit after bit
for ( int cur_bit = databitnumber+crcbitnumber-1; cur_bit >= 0; -- cur_bit ) //处理 64 次（32 比特待测数据＋32 比
特扩展 0），前 32 次是加载数据
{
// test the highest bit which will be poped later.
/// in fact, the 5th bit from right is the hightest bit here
if ( ( ( regi >> crcbitnumber ) & 0x0001 ) == 0x1 ) regi = regi ^ POLY;
regi <<= 1; // shift the register
// reading the next bit of the augmented data
unsigned short tmp = ( data >> cur_bit ) & 0x0001; // 加载待测数据 1 比特到 tmp 中，tmp 只有 1 比特
regi |= tmp; //
}
if ( ( ( regi >> crcbitnumber ) & 0x0001 ) == 0x1 ) regi = regi ^ POLY; // 做最后一次 XOR
//这时， regi 中的值就是 CRC
待测数据，为字串"1234"
是 32 比特
数据是 32 比特
这 1 比特加载到寄存器中
四、 驱动表法 Table-Driven Implementation
上面的“直接计算法”很直观，却非常的低效。为了加快它的速度，我们使它一次能处理大于 4 bit
的数据。一次能处理一个字节的数据的话，那就方便多了。
我们想要实现的 32 bit 的 CRC 校验。我们还是假设有和原来一样的一个 4 "bit"的 register，但它的
每一位是一个 8 bit 的字节。
3 2 1 0 Bytes
+----+----+----+----+
Pop! <-- | | | | | <----- Augmented message（扩展 0 后的数据）
+----+----+----+----+
1 <------32 bits------> （生成项，暗含了一个最高位的“1”）
根据同样的原理我们可以得到如下的算法：
While (还有剩余没有处理的数据)
Begin
检查 register 头字节，并取得它的值
求不同偏移处多项式的 XOR
register 左移一个字节，最右处存入新读入的一个字节
把 register 的值 和 多项式的 XOR 结果 进行 XOR 运算
End
可是为什么要这样作呢？ 同样我们还是以一个简单的例子说明问题：
为了简单起见，我们假设一次只移出 4 个比特！而不是 8 个比特。
生成多项式为： 1 0101 1100，即宽度 W=8，即 CRC8，这样寄存器为 8 位
待测数据是 1011 0100 1101
按正常的算法做：
将 1011 0100 放入寄存器中，然后开始计算 CRC。
先将高 4 位移出寄存器：
当前 register 中的值： 0100 1101
4 bit 应该被移出的值： 1011
生成多项式为： 1010 1110 0
第一步：
Top Register （top 指移出的数据）
---- --------
1011 0100 1101 待测数
1010 1110 0 + (CRC XOR) POLY
-------------
0001 1010 1101 第一次 XOR 后的值
第二步：
这时，首 4 bits 不为 0 说明没有除尽，要继续除:
0001 1010 1101
1 0101 1100 + (CRC XOR) 将 POLY 右移 3 位后，再做 XOR
-------------
0000 1111 0001 第二次 XOR 后的值
^^^^
这时，首 4 bits 全 0 说明不用继续除了，结果满足要求了。
也就是说：待测数据与 POLY 相 XOR，得到的结果再与 POLY 相 XOR，POLY 要适当移位，以消掉 1。重复
进行，直到结果满足要求。
下面，我们换一种算法，来达到相同的目的：
POLY 与 POLY 自已先进行 XOR，当然 POLY 要进行适当移位。使得得到的结果值的高 4 位与待测数据相
同。
第一步：
1010 1110 0 POLY
1 0101 1100 + 右移 3 位后的 POLY
-------------
1011 1011 1100 POLY 与 POLY 自已进行 XOR 后得到的值
第二步：
1011 1011 1100 POLY 相 XOR 后得到的值
1011 0100 1101+ 待测数据
-------------
0000 11110001 得到的结果值和上面是一样的（说明可以先把 POLY 预先 XOR 好，再与待
测数据 XOR，就能得到结果）
结论：
现在我们看到，这二种算法计算的结果是一致的！这是基于 XOR 的交换律，即(a XOR b) XOR c = a XOR
(b XOR c)。而后一种算法可以通过查表来快速完成，叫做“驱动表法”算法。
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
