CRC校验算法
CRC(Cyclic Redundancy Check)循环冗余校验是常用的数据校验方法，讲CRC算法的文章很多，之所以还要写这篇，是想换一个方法介绍CRC算法，希望能让大家更容易理解CRC 算法。
先说说什么是数据校验。数据在传输过程（比如通过网线在两台计算机间传文件）中，由于传输信道的原因，可能会有误码现象（比如说发送数字5但接收方收到的却是6），如何发现误码呢？方法是发送额外的数据让接收方校验是否正确，这就是数据校验。最容易想到的校验方法是和校验，就是将传送的数据(按字节方式)加起来计算出数据的总和，并将总和传给接收方，接收方收到数据后也计算总和，并与收到的总和比较看是否相同。如果传输中出现误码，那么总和一般不会相同，从而知道有误码产生，可以让发送方再发送一遍数据。
CRC校验也是添加额外数据做为校验码，这就是CRC校验码，那么CRC校验码是如何得到的呢？
非常简单，CRC校验码就是将数据除以某个固定的数（比如ANSI-CRC16中，这个数是0x18005），所得到的余数就是CRC校验码。
那这里就有一个问题，我们传送的是一串字节数据，而不是一个数据，怎么将一串数字变成一个数据呢？这也很简单，比如说2个字节B1，B2,那么对应的数就是(B1<<8)+B2；如果是3个字节B1，B2，B3，那么对应的数就是((B1<<16)+(B2<<8)+B3),比如数字是0x01,0x02, 0x03，那么对应的数字就是0x10203；依次类推。如果字节数很多，那么对应的数就非常非常大，不过幸好CRC只需要得到余数，而不需要得到商。
从上面介绍的原理我们可以大致知道CRC校验的准确率，在CRC8中出现了误码但没发现的概率是1/256，CRC16的概率是1/65536，而CRC32的概率则是1/2^32，那已经是非常小了，所以一般在数据不多的情况下用CRC16校验就可以了，而在整个文件的校验中一般用CRC32校验。
这里还有个问题，如果被除数比除数小，那么余数就是被除数本身，比如说只要传一个字节，那么它的CRC就是它自己，为避免这种情况，在做除法之前先将它移位，使它大于除数，那么移多少位呢？这就与所选的固定除数有关了，左移位数比除数的位数少1，下面是常用标准中的除数：
CRC8：多项式是X8+X5+X4+1，对应的数字是0x131，左移8位
CRC12：多项式是X12+X11+X3+X2+1，对应的数字是0x180D，左移12位
CCITT CRC16：多项式是X16+X12+X5+1，对应的数字是0x11021，左移16位
ANSI CRC16：多项式是X16+X15+X2+1，对应的数字是0x18005，左移16位
CRC32：多项式是X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1，对应数字是0x104C11DB7，左移32
因此，在得到字节串对应的数字后，再将数字左移M位（比如ANSI-CRC16是左移16位），就得到了被除数。
好了，现在被除数和除数都有了，那么就要开始做除法求CRC校验码了。CRC除法的计算过程与我们笔算除法类似，首先是被除数与除数高位对齐后，被除数减去除数，得到了差，除数再与差的最高位对齐，进行减法，然后再对齐再减，直到差比除数小,这个差就是余数。不过和普通减法有差别的是，CRC的加(减)法是不进(借)位的，比如10减01，它的结果是11，而不是借位减法得到的01，因此，实际上CRC的加法和减法所得的结果是一样的，比如10加0 1的结果是11，10减01的结果也是11，这其实就是异或操作。虽然说了这么多也不一定能说清楚,我们还是看一段CRC除法求余程序吧:
/* 这段程序是求数据0x880000除以0x11021的余数 */
/* 这段程序其实也就是求字节0x88的CRC16校验码，因为0x88左移16位是0x880000 */ unsigned short crc16_div()
{
unsigned long data = 0x880000;
unsigned long ccitt16 = 0x11021;
/* 这是比较值,被除数与它比较看是否需要减去除数
注意,这里只需要与0x10000比较就可以了,而不需要与除数0x18005比较,这样可以少很多计算
而且余数的范围就在0-0xFFFF之间,而不是0-0x18004之间了 */
unsigned long cmp_value = 0x10000;
int i;
ccitt16 <<= 7; /* 左移7位,与被除数最高位对齐 */
cmp_value <<= 7; /* 左移7位,与被除数最高位对齐 */
while (cmp_value >= 0x10000) /* 循环直到差数比cmp_value小 */
{
if ((data & cmp_value) != 0) /* 最高位为1,则减去除数 */
{
data ^= ccitt16; /* 做CRC的减法,就是异或操作 */
}
else /* 最高位为0,不够减 */
{
/* 不作任何操作，只执行后面的移位操作 */
}
/* 得到了差,右移一位,与被除数下一位对齐 */
ccitt16 >>= 1;
cmp_value >>= 1;
}
/* 现在data的最低两个字节就是余数,也就是CRC校验码 */
return (data & 0xFFFF);
}
好了，现在我们已经会计算0x88的CRC校验码了，它只是对0x880000做除法运算求余数而已，不过这只是求单字节的CRC校验码，那如果有十多个字节怎么办？我们的计算机也存不下那么大的数呀，看来我们还要对程序进行些改进，使它能对大数求除法了。
unsigned short crc16_div_2()
{
/* 这段程序也是求数据0x88的CRC校验码，与上一个程序crc16_div所得结果相同*/
/* 这里只需要直接传数据就可以，而不需要再事先移位 */
unsigned short data = 0x88;
/* 这里只需要2个字节0x1021，而不是0x11021，为什么不再需要最高位的1，看看代码就清楚了 */
unsigned short ccitt16 = 0x1021;
int i;
data <<= 8;
for (i=0; i<8; i++)
{
if (data & 0x8000) /* 最高位为1,减去除数 */
{
data <<= 1; /* 将最高位的1移出,剩下的数与0x1021(而不是0x11021)异或,这是因为最高位的1与0x11021的最高位1异或后为0 */
data ^= ccitt16;
}
else /* 最高位为0,不需要减去除数 */
{
data <<= 1; /* 直接移位 */
}
}
return data;
}
现在对单字节0x88求CRC16，我们只需要两字节short型的整数就行了，而不需要象以前必须用long型0x880000，其实不管多少字节，只用short型就能够计算它的CRC16。下面说说怎么求多字节的样验码：
当我们求得一个字节（比如0x88）的CRC校验码后，如果这时又有一个字节(比如0x23)加入，需要求校验码，该怎么办呢？以前得到的是0x880000除以0x11021的余数，但现在需要得到的是0x88230000除以0x11021的余数，以前求得的校验码是不是白费了？不是的，因为当我们得到0x880000除以0x11021的余数（这里余数是0x1080）后，需要求0x88230000除以0x11021的余数，只要将原来的余数0x1080左移8位除以0x11021就得到了0x98000000除以0x11021的余数<0x108000除以0x11021的余数>（想一想为什么），再加上0x230000除以0x11021的余数。这其实就是求0x108000+0x230000除以0x11021的余数.。因此根据这个方法，我们就可以写出求多个字节的CRC算法：
/* 这段代码是求ccitt-crc16的算法
参数：
data:字节数据
crc:原来数据求得的crc校验码
返回值：
数据的ccitt-crc16校验码
*/
unsigned short crc16_ccitt(unsigned char data, unsigned short crc)
{
unsigned short ccitt16 = 0x1021;
int i;
crc ^= (data<<8); /* 新的数据与将原来的余数（就是crc）相加（加法就是异或操作） */
/* 求数据的CRC校验码 */
for (i=0; i<8; i++)
{
if (crc & 0x8000) /* 最高位为1,减去除数 */
{
crc <<= 1;
crc ^= ccitt16;
}
else /* 最高位为0,不需要减去除数 */
{
crc <<= 1; /* 直接移位 */
}
}
return crc;
}
/* 这是个主程序，表示如何计算5个字节的CRC */
void main()
{
int i;
unsigned short crc;
char data[5] = { 0x71, 0x88, 0x93, 0xa5, 0x13 }; /* 计算这5个数据的CRC校验码 */
crc = 0;
for (i=0; i<5; i++)
{
crc = crc16_ccitt(data[i], crc);
}
printf("crc is %x", crc);
}
好了，讲到这里CRC算法已经全部介绍完了。什么，讲完了？不对呀，我怎么记得C RC程序都有个数组叫CRC表什么的，你这里怎么没有？
呵呵，其实使用CRC表是为了节省一些运算时间，事先将算好的CRC保存在数组里，省得临时再计算，它保存的是0到0xff的CRC码，下面我们来自己生成一个CRC表：unsigned short CRC16_CCITT_TABLE[256];
void init_crc16_ccitt_table()
{
int i;
for (i=0; i<256; i++)
{
CRC16_CCITT_TABLE[i] = crc16_ccitt(i, 0);
}
}
上面只是一个字节的CRC表，那多个字节的CRC如何计算呢？与前面求多字节的CRC 方法差不多，它的代码如下：
/* 这段代码是查表求ccitt-crc16的算法，它与前面的程序crc16_ccitt所得到的结果一样参数：
data:字节数据
crc:原来数据求得的crc校验码
返回值：
数据的ccitt-crc16校验码
unsigned short crc16_ccitt_2(unsigned char data, unsigned short crc)
{
unsigned char c;
c = crc >> 8; /* c的值为crc的高8位 */
crc <<= 8; /* crc现在的值变为低8位左移8位 */
crc ^= CRC16_CCITT_TABLE[data ^ c];
return crc;
}
最后要说的是CRC的正序和反转问题，比如前面ccitt-crc16的正序是0x1021，如果是反转就是0x8408（就是将0x1021倒过来低位变高位）为什么要反转？这是因为数据传输可能是先传低位再传高位（比如串口就是低位在前高位在后）。反转的CRC算法与正序类似，只是需要注意移位的方向相反。
/* 这段代码是求ccitt-crc16的反转算法
参数：
data:字节数据
crc:原来数据求得的crc反转校验码
返回值：
数据的ccitt-crc16反转校验码
*/
unsigned short crc16_ccitt_r(unsigned char data, unsigned short crc)
{
unsigned short ccitt16 = 0x8408;
int i;
crc ^= data; /* 新的数据与将原来的余数（就是crc）相加（加法就是异或操作）
for (i=0; i<8; i++)
{
if (crc & 1) /* 最低位为1,减去除数 */
{
crc >>= 1;
crc ^= ccitt16;
}
else /* 最低位为0,不需要减去除数 */
{
crc >>= 1; /* 直接移位 */
}
}
return crc;
}
/* 这段代码是查表求反转ccitt-crc16的算法，它与前面的程序crc16_ccitt_r所得到的结果一样
参数：
data:字节数据
crc:原来数据求得的crc校验码
返回值：
数据的ccitt-crc16校验码
*/
unsigned short crc16_ccitt_r2(unsigned char data, unsigned short crc)
{
unsigned char c;
c = crc & 0xff;
crc >>= 8;
crc ^= CRC16_CCITT_R_TABLE[data ^ c];
return crc;
}
CRC算法及原理
CRC校验码的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。
在数据存储和数据通讯领域，CRC无处不在:著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC. CCITT，ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为
检错手段。
CRC的本质是模-2除法的余数，采用的除数不同，CRC的类型也就不一样。通常，CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式有
CRC16,CRC32.
以CRC16为例,16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以2^16）后，再除以一个多项式，最后所得到的余数既是CRC码，如下式所示，其中K(X)表示n位的二进制序列数，G(X)为多项式，Q(X)为整数，
R(X)是余数（既CRC码）。
K(X)>>16=G(x)Q(x)+R(x)
求CRC码所采用模2加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。生成CRC码的多项式如下，其中CRC-16和CRC-CCITT产生16位的CRC码，而CRC-32则产生的是32位的CRC
码
接收方将接收到的二进制序列数（包括信息码和CRC码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误，关于其原理这里不再多述。用软件计算CRC码时，接收方可以将接收到的信息码求CRC码，比较结果和接收
到的CRC码是否相同。
CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中，使用CCITT-16即CRC16,其生成多项式为G(x)=x16+x12+x5+1, CRC-32的生成多项式为G(x)=x32+x26+x23+x22+x16+x11+x10+x16+x8+x7+x5+x4+x2+x+1
CRC算法原理及C语言实现
CRC原理介绍:
CRC的英文全称为Cyclic Redundancy Check（Code），中文名称为循环冗余校验（码）。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。
CRC计算与普通的除法计算有所不同。普通的除法计算是借位相减的，而CRC 计算则是异或运算。任何一个除法运算都需要选取一个除数，在CRC运算中我们称之为poly，而宽度W就是poly最高位的位置。比如poly 1001的W是3，而不是4。注意最高位总是1，当你选定一个宽度，那么你只需要选择低W各位的值。假如我们想计算一个位串的CRC码，并要保证每一位都要被处理，因此我们需要在目标位串后面加上W个0。下面举例说明CRC算法的过程。
在此例中，我们假设位串为110101101。
Poly= 10011（宽度W = 4）
Bitstring + W zeros = 110101101 0000
10011/1101011010000/110000101 （我们不关心此运算的商）
10011||||||||
-----||||||||
10011|||||||
10011|||||||
-----|||||||
00001||||||
00000||||||
-----||||||
00010|||||
00000|||||
-----|||||
00101||||
00000||||
-----||||
01010|||
00000|||
-----|||
10100||
10011||
-----||
01110|
00000|
-----|
11100
10011
-----
1111 -> 余数 -> CRC！
计算过程总结如下：
1. 只有当位串的最高位为1，我们才将它与poly做XOR运算，否则我们只是将位
串左移一位。
2. 异或运算的结果实质上是被操作位串与poly的低W位进行运算的结果，因为最高位总为0。
CRC原理及其逆向破解方法：
介绍：
这篇短文包含CRC原理介绍和其逆向分析方法,很多程序员和破解者不是很清楚了解
CRC的工作原理,而且几乎没人知道如何逆向分析它的方法,事实上它是非常有用的. 首先,这篇教程教你一般如何计算CRC,你可以将它用在数据代码保护中.第二,主要是
介绍如何逆向分析CRC-32,你可以以此来分析程序中的CRC保护（象反病毒编码）.当然
有很多有效的工具用来对付CRC,但我怀疑它是否会说明原理.
我要告诉你,这篇短文里中应用了很多数学知识,这不会影响一些人,而且会被一般的
程序员与逆向分析者很好理解.为什么？那么如果你不知道数学是如何被应用在CR C中,
我建议你可以停止继续学习了.所以我假定你们（读者）都是具备二进制算术知识的. 第一部分：CRC 介绍,CRC是什么和计算CRC的方法.
循环冗余码CRC
我们都知道CRC.甚至你没有印象,但当你想到那些来自诸如RAR,ZIP等压缩软件发给你
由于错误连接和其他一些意外原因导致的文件错误的恼人的消息时,你就会知道.CR C是块
数据的计算值,比如对每一个文件进行压缩.在一个解压缩过程中,程序会从新计算解
压文件
的CRC值,并且将之与从文件中读取的CRC值进行比对,如果值相同,那么正确.在C RC-32中,
会有1/2^32的可能性发生对确认数据更改的校验错误.
很多人认为CRC就是循环冗余校验,假如CRC真的就是循环冗余校验,那么很多人都错用了
这个术语.你不能说"这个程序的CRC是12345678".人们也常说某一个程序有CRC 校验,而不
说是"循环冗余校验" 校验.结论：CRC 代表循环冗余码,而不是循环冗余校验.
计算是如何完成的呢？好,主要的想法就是将一个文件看成一个被一些数字分割的很长的
位字串,这里会有一个余数---CRC！你总会有一个余数(可以是0),它至多比除数小一. (9/3=3 余数=0 ; (9+2)/3=3 余数=2)
(或者它本身就包含一个除数在其中).
在这里CRC计算方法与除法有一点点区别,除法就是将被减数重复的减去除数X 次,然后留下
余数.如果你希望得到原值,那么你就要把除数乘上X次,然后加上余数.
CRC计算使用特殊的减法与加法完成的.也就是一种新的"算法".计算中每一位计算的进位值
被"遗忘"了.
看如下两个例子,1是普通减法,2和3是特殊的.
-+
(1) 1101 (2) 1010 1010 (3) 0+0=0 0-0=0
1010- 1111+ 1111- 0+1=1 *0-1=1
---- ---- ---- 1+0=1 1-0=1
0011 0101 0101 *1+1=0 1-1=0
在(1)中,右数第二列可以看成是0-1=-1,因此要从高位借1,就变成(10+0)-1=1.(这就象普通
的'by-paper'十进制减法).特例(2,3)中,1+1会有正常的结果10,'1'是计算后的进位.这个值
被忽略了.特殊情况0-1应该有正常结果'-1'就要退到下一位.这个值也被忽略了.假如你对编程
有一定了解,这就象,XOR 操作或者更好.
现在来看一个除法的例子:
在普通算法中:
1001/1111000\1101 13 9/120\13
1001 - 09 -|
---- -- |
1100 30 |
1001 - 27 -
---- --
0110 3 -> 余数
0000 -
----
1100
1001 -
----
011 -> 3, 余数
在CRC算法中:
1001/1111000\1110 9/120\14 余数为6
1001 -
----
1100
1001 -
----
1010
1001 -
----
0110
0000 -
----
110 -> 余数
(例3)
这个除法的商并不重要,也没必要去记住,因为他们仅仅是一组无关紧要的位串.真正
重要的是余数!它就是这个值,可以说比原文件还重要的值,他就是基本的CRC.
过度到真正的CRC码计算.
进行一个CRC计算我们需要选则一个除数,从现在起我们称之为"poly".宽度W就是最高位
的位置,所以这个poly 1001的W 是3,而不是4.注意最高位总是1,当你选定一个宽
度,那么你只
需要选择低W各位的值.
假如我们想计算一个位串的CRC码,我们想确定每一个位都被处理过,因此,我们要在目标
位串后面加上W个0位.在此例中,我们假设位串为1111.请仔细分析下面一个例子: Poly = 10011, 宽度W=4
位串Bitstring
Bitstring + W zeros = 110101101 + 0000
10011/1101011010000\110000101 (我们不关心此运算的商)
10011|||||||| -
-----||||||||
10011|||||||
10011||||||| -
-----|||||||
00001||||||
00000|||||| -
-----||||||
00010|||||
00000||||| -
-----|||||
00101||||
00000|||| -
-----||||
01010|||
00000||| -
-----|||
10100||
10011|| -
-----||
01110|
00000| -
-----|
11100
10011 -
-----
1111 -> 余数-> the CRC!
(例4)
重要两点声明如下:
1.只有当Bitstring的最高位为1,我们才将它与poly做XOR运算,否则我们只是将Bitstring左移一位.
2.XOR运算的结果就是被操作位串bitstring与低W位进行XOR运算,因为最高位总为0.
算法设计:
你们都应知道基于位运算的算法是非常慢的而且效率低下.但如果将计算放在每一字节上
进行,那么效率将大大提高.不过我们只能接受poly的宽度是8的倍数(一个字节;).
可以形
象的看成这样一个宽度为32的poly(W=32):
3 2 1 0 byte
+---+---+---+---+
Pop! <--| | | | |<-- bitstring with W zero bits added, in this case 32 +---+---+---+---+
1<--- 32 bits ---> this is the poly, 4*8 bits
(figure 1)
这是一个你用来存放暂时CRC结果的记存器,现在我称它为CRC记存器或者记存器.你从右
至左移动位串,当从左边移出的位是1,则整个记存器被与poly的低W位进行XOR 运算.(此例
中为32).事实上,我们精确的完成了上面除法所做的事情.
移动前记存器值为:10110100
当从右边移入4位时,左边的高4位将被移出,此例中1011将被移出,而1101被移入. 情况如下:
当前8位CRC记存器: 01001101
刚刚被移出的高4位: 1011
我们用此poly : 101011100, 宽度W=8
现在我们用如前介绍的方法来计算记存器的新值.
顶部记存器