CRC源码.docx

CRC源码.docx

《CRC源码.docx》由会员分享，可在线阅读，更多相关《CRC源码.docx（20页珍藏版）》请在冰点文库上搜索。

CRC源码

CRC-16/CRC-32程序代码

不久前写一程序时要用到CRC-16，但找来找去只在UDDF里找到一个Delphi的CRC-32程序代码，而且是用查表法，虽然说查表法速度快，但256项32位数据我怀疑可能会有输入错误，让人不是那么放心，而我又不知道这个表是怎么算出来的。

后来我又在一本两年前的笔记本里找到一段关于CRC的内容，也不知是从哪里抄来的，还好里面有一段程序代码，是CRC-16的，这段程序正是产生CRC表的，可是这区区几行的程序（基本上与下面的BuilderTable16函数相同）看得我一头雾水，直到这两天才弄明白，并据此推出CRC-32的算法，现将全部程序列在下面，并作一些说明以助于理解，不但要知其然，还要知其所以然嘛：

补充：

为了使这段程序更加实用，我将其整理为几个单元，分别用于Delphi和C++Builder。

包括对数据流TMemoryStream和字符串的处理。

可以在此下载：

3.7KB。

Aug.18-01

//注意：

因最高位一定为“1”，故略去

constunsignedshortcnCRC_16=0x8005;

//CRC-16=X16+X15+X2+X0

constunsignedshortcnCRC_CCITT=0x1021;

//CRC-CCITT=X16+X12+X5+X0，据说这个16位CRC多项式比上一个要好

constunsignedlongcnCRC_32=0x04C10DB7;

//CRC-32=X32+X26+X23+X22+X16+X11+X10+X8+X7+X5+X4+X2+X1+X0

unsignedlongTable_CRC[256];//CRC表

//构造16位CRC表

voidBuildTable16（unsignedshortaPoly）

{

unsignedshorti,j;

unsignedshortnData;

unsignedshortnAccum;

for（i=0;i<256;i++）

{

nData=（unsignedshort）（i<<8）;

nAccum=0;

for（j=0;j<8;j++）

{

if（（nData^nAccum）&0x8000）

nAccum=（nAccum<<1）^aPoly;

else

nAccum<<=1;

nData<<=1;

}

Table_CRC[i]=（unsignedlong）nAccum;

}

}

//计算16位CRC值，CRC-16或CRC-CCITT

unsignedshortCRC_16（unsignedchar*aData,unsignedlongaSize）

{

unsignedlongi;

unsignedshortnAccum=0;

BuildTable16（cnCRC_16）;//orcnCRC_CCITT

for（i=0;i<aSize;i++）

nAccum=（nAccum<<8）^（unsignedshort）Table_CRC[（nAccum>>8）^*aData++];

returnnAccum;

}

//构造32位CRC表

voidBuildTable32（unsignedlongaPoly）

{

unsignedlongi,j;

unsignedlongnData;

unsignedlongnAccum;

for（i=0;i<256;i++）

{

nData=（unsignedlong）（i<<24）;

nAccum=0;

for（j=0;j<8;j++）

{

if（（nData^nAccum）&0x80000000）

nAccum=（nAccum<<1）^aPoly;

else

nAccum<<=1;

nData<<=1;

}

Table_CRC[i]=nAccum;

}

}

//计算32位CRC-32值

unsignedlongCRC_32（unsignedchar*aData,unsignedlongaSize）

{

unsignedlongi;

unsignedlongnAccum=0;

BuildTable32（cnCRC_32）;

for（i=0;i<aSize;i++）

nAccum=（nAccum<<8）^Table_CRC[（nAccum>>24）^*aData++];

returnnAccum;

}

说明：

CRC的计算原理如下（一个字节的简单例子）

110110000000000000000000<-一个字节数据,左移16b

^10001000000100001<-CRC-CCITT多项式,17b

--------------------------

10100000001000010<-中间余数

^10001000000100001

-------------------------

10100000110001100

^10001000000100001

-----------------------

10100011010110100

^10001000000100001

---------------------

10101101001010100

^10001000000100001

-------------------

0100101001110101<-16bCRC

仿此，可推出两个字节数据计算如下：

d为数据，p为项式，a为余数

dddddddddddddddd0000000000000000<-数据D（D1,D0,0,0）

^ppppppppppppppppp<-多项式P

-----------------------------------

...

aaaaaaaaaaaaaaaa0<-第一次的余数A'（A'1,A'0）

^ppppppppppppppppp

--------------------------

...

aaaaaaaaaaaaaaaa<-结果A（A1,A0）

由此与一字节的情况比较，将两个字节分开计算如下：

先算高字节：

dddddddd000000000000000000000000<-D1,0,0,0

^ppppppppppppppppp<-P

-----------------------------------

...

aaaaaaaaaaaaaaaa<-高字节部分余数PHA1,PHA0

此处的部分余数与前面两字节算法中的第一次余数有如下关系，即A'1=PHA1^D0,A'0=PHA0：

aaaaaaaaaaaaaaaa<-PHA1,PHA0

^dddddddd<-D0

-----------------

aaaaaaaaaaaaaaaa<-A'1,A'0

低字节的计算：

aaaaaaaa0000000000000000<-A'1,0,0

^ppppppppppppppppp<-P

--------------------------

...

aaaaaaaaaaaaaaaa<-低字节部分余数PLA1,PLA0

^aaaaaaaa<-A'0，即PHA0

-----------------

aaaaaaaaaaaaaaaa<-最后的CRC（A1,A0）

总结以上内容可得规律如下：

设部分余数函数

PA=f（d）

其中d为一个字节的数据（注意，除非n=0，否则就不是原始数据，见下文）

第n次的部分余数

PA（n）=（PA（n-1）<<8）^f（d）

其中的

d=（PA（n-1）>>8）^D（n）

其中的D（n）才是一个字节的原始数据。

公式如下：

PA（n）=（PA（n-1）<<8）^f（（PA（n-1）>>8）^D（n））

可以注意到函数f（d）的参数d为一个字节，对一个确定的多项式P，f（d）的返回值

是与d一一对应的，总数为256项，将这些数据预先算出保存在表里，f（d）就转换为一

个查表的过程，速度也就可以大幅提高，这也就是查表法计算CRC的原理，在CRC_16和

CRC_32两个函数的循环中的语句便是上面那个公式。

再来看CRC表是如何计算出来的，即函数f（d）的实现方法。

分析前面一个字节数据的

计算过程可发现，d对结果的影响只表现为对P的移位异或，看计算过程中的三个8位

的列中只有低两个字节的最后结果是余数，而数据所在的高8位列最后都被消去了，因其

中的运算均为异或，不产生进位或借位，故每一位数据只影响本列的结果，即d并不直接

影响结果。

再将前例变化一下重列如下：

11011000

--------------------------

10001000000100001//P

^10001000000100001//P

^00000000000000000//0

^10001000000100001//P

^00000000000000000//0

^10001000000100001//P

^00000000000000000//0

^10001000000100001//P

-------------------

0100101001110101

现在的问题就是如何根据d来对P移位异或了，从上面的例子看，也可以理解为每步

移位，但根据d决定中间余数是否与P异或。

从前面原来的例子可以看出，决定的条

件是中间余数的最高位为0，因为P的最高位一定为1，即当中间余数与d相应位异或

的最高位为1时，中间余数移位就要和P异或，否则只需移位即可。

具体做法见程序中

的BuildTable16和BuildTable32两个函数，其方法如下例（上例的变形，注意其中

空格的移动表现了d的影响如何被排除在结果之外）：

d--------a--------

10000000000000000<-HSB=1

0000000000000000<-a<<=1

0001000000100001<-P,CRC-CCITT不含最高位的1

-----------------

10001000000100001

0010000001000010

0001000000100001

-----------------

00011000001100011<-HSB=0

0110000011000110

-----------------

10110000011000110<-HSB=1

1100000110001100

0001000000100001

-----------------

11101000110101101<-HSB=0

1010001101011010

-----------------

01010001101011010<-HSB=1

0100011010110100

010*********

-----------------

00101011010010101<-HSB=0

010*********

-----------------

01010110100101010<-HSB=1

010*********

0001000000100001

-----------------

0100101001110101<-CRC

结合这些，前面的程序就好理解了。

至于32位CRC的计算与16相似，就不多加说明，请参考源程序。

CRC算法原理及C语言实现 －来自（我爱单片机）

       摘要 

       本文从理论上推导出CRC算法实现原理，给出三种分别适应不同计算机或微控制器硬件环境的C语言程序。

读者更能根据本算法原理，用不同的语言编写出独特风格更加实用的CRC计算程序。

       关键词  CRC  算法  C语言

       1 引言

       循环冗余码CRC检验技术广泛应用于测控及通信领域。

CRC计算可以靠专用的硬件来实现，但是对于低成本的微控制器系统，在没有硬件支持下实现CRC检验，关键的问题就是如何通过软件来完成CRC计算，也就是CRC算法的问题。

       这里将提供三种算法，它们稍有不同，一种适用于程序空间十分苛刻但CRC计算速度要求不高的微控制器系统，另一种适用于程序空间较大且CRC计算速度要求较高的计算机或微控制器系统，最后一种是适用于程序空间不太大，且CRC计算速度又不可以太慢的微控制器系统。

       2 CRC简介

       CRC校验的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共（k+r）位，最后发送出去。

在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。

       16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以

       ）后，再除以一个多项式，最后所得到的余数既是CRC码，如式（2-1）式所示，其中B（X）表示n位的二进制序列数，G（X）为多项式，Q（X）为整数，R（X）是余数（既CRC码）。

                               （2-1）

       求CRC码所采用模2加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。

生成CRC码的多项式如下，其中CRC-16和CRC-CCITT产生16位的CRC码，而CRC-32则产生的是32位的CRC码。

本文不讨论32位的CRC算法，有兴趣的朋友可以根据本文的思路自己去推导计算方法。

       CRC-16：

（美国二进制同步系统中采用）  

       CRC-CCITT：

（由欧洲CCITT推荐）       

       CRC-32：

       接收方将接收到的二进制序列数（包括信息码和CRC码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误，关于其原理这里不再多述。

用软件计算CRC码时，接收方可以将接收到的信息码求CRC码，比较结果和接收到的CRC码是否相同。

       3 按位计算CRC

       对于一个二进制序列数可以表示为式（3-1）:

                                   （3-1）

       求此二进制序列数的CRC码时，先乘以后（既左移16位），再除以多项式G（X），所得的余数既是所要求的CRC码。

如式（3-2）所示：

                 （3-2）

       可以设：

                                               （3-3）

       其中为整数，为16位二进制余数。

将式（3-3）代入式（3-2）得：

             （3-4）

       再设：

                                  （3-5）

       其中为整数，为16位二进制余数，将式（3-5）代入式（3-4），如上类推，最后得到：

          （3-6）

       根据CRC的定义，很显然，十六位二进制数既是我们要求的CRC码。

       式（3-5）是编程计算CRC的关键，它说明计算本位后的CRC码等于上一位CRC码乘以2后除以多项式，所得的余数再加上本位值除以多项式所得的余数。

由此不难理解下面求CRC码的C语言程序。

*ptr指向发送缓冲区的首字节，len是要发送的总字节数，0x1021与多项式有关。

       unsignedintcal_crc（unsignedchar*ptr,unsignedcharlen）{

         unsignedchari;

         unsignedintcrc=0;

         while（len--!

=0）{

           for（i=0x80;i!

=0;i/=2）{

             if（（crc&0x8000）!

=0）{crc*=2;crc^=0x1021;}  /*余式CRC乘以2再求CRC */

               elsecrc*=2;

       if（（*ptr&i）!

=0）crc^=0x1021;               /*再加上本位的CRC*/

           }

           ptr++;

         }

         return（crc）;

       }

       按位计算CRC虽然代码简单，所占用的内存比较少，但其最大的缺点就是一位一位地计算会占用很多的处理器处理时间，尤其在高速通讯的场合，这个缺点更是不可容忍。

因此下面再介绍一种按字节查表快速计算CRC的方法。

       4 按字节计算CRC

       不难理解，对于一个二进制序列数可以按字节表示为式（4-1），其中为一个字节（共8位）。

                      （4-1）

       求此二进制序列数的CRC码时，先乘以后（既左移16位），再除以多项式G（X），所得的余数既是所要求的CRC码。

如式（4-2）所示：

                     （4-2）

       可以设：

                                           （4-3）

       其中为整数，为16位二进制余数。

将式（4-3）代入式（4-2）得：

                           （4-4）

       因为：

                                                           （4-5）

       其中是的高八位，是的低八位。

将式（4-5）代入式（4-4），经整理后得：

             （4-6）

       再设：

                （4-7）

       其中为整数，为16位二进制余数。

将式（4-7）代入式（4-6），如上类推，最后得：

                       （4-8）

       很显然，十六位二进制数既是我们要求的CRC码。

       式（4-7）是编写按字节计算CRC程序的关键，它说明计算本字节后的CRC码等于上一字节余式CRC码的低8位左移8位后，再加上上一字节CRC右移8位（也既取高8位）和本字节之和后所求得的CRC码，如果我们把8位二进制序列数的CRC全部计算出来，放如一个表里，采用查表法，可以大大提高计算速度。

由此不难理解下面按字节求CRC码的C语言程序。

*ptr指向发送缓冲区的首字节，len是要发送的总字节数，CRC余式表是按0x11021多项式求出的。

       unsignedintcal_crc（unsignedchar*ptr, unsignedcharlen）{

         unsignedintcrc;

         unsignedcharda;

         unsignedintcrc_ta[256]={              /*CRC余式表*/

           0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,

       0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,

           0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6,

           0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de,

           0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485,

           0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d,

           0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x