精华内容
下载资源
问答
  • crc原理
    千次阅读
    2019-02-23 21:59:49

    原文地址:http://wenku.baidu.com/view/fb791c0203d8ce2f006623f5.html


    我学习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;          //生成项,13H=10011,这样CRC是4比特 
    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; 
    //这样共有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;    //这1比特加载到寄存器中 

    if ( ( ( regi >> 4 ) & 0x0001 ) == 0x1 )   regi = regi ^ POLY;    //做最后一次XOR 
    //这时, regi中的值就是CRC 
     
     
    程序2:我做的通用CRC计算程序: 
     
    _int64  POLY = 0x104C11DB7;   //生成项,需要含有最高位的"1",这样CRC是32比特 
    int crcbitnumber=32;      //crc是32比特 
     
    _int64  data = 0x31323334;      //待测数据,为字串"1234" 
    int  databitnumber=32;     //数据是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;    //这1比特加载到寄存器中 

    if ( ( ( regi >> crcbitnumber ) & 0x0001 ) == 0x1 )   regi = regi ^ POLY;   //做最后一次XOR 
    //这时, regi中的值就是CRC 
     
     
    四、  驱动表法   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)。而后一种算法可以通过查表来快速完成,叫做“驱动表法”算法。 
    也就是说,根据4 bit被移出的值1011,我们就可以知道要用POLY自身XOR后得到的 1011 1011 1100 
    来对待测数据1011 0100 1101进行XOR,这样一次就能消掉4BIT待测数据。(注意蓝色的最高4位要一样,
    这样XOR后才能得0000,就能消掉了) 
    即1011对应1011 1011 1100,实际只需要用到后8位,即1011对应1011 1100 
    用查表法来得到,即1011作为索引值,查表,得到表值1011 1100。 
    表格可以预先生成。 
     
    这里是每次移出4位,则POLY与POLY进行XOR的组合有2^4=16种,即从0000到1111。 
    注意,POLY自身与自身相XOR时,要先对齐到和寄存器一样的长度,再XOR。相当于有12位进行XOR。 
    组合后的结果有16种:(黑色的0表示对齐到和寄存器一样的长度) 
    1.  0000 0000 0000        即表示待测数据移出的4位都是0,不需要与POLY相XOR,即相当于待测
    数据移出的4位后,与0000 0000 0000相XOR 
    2.  0001 0101 1100   即表示待测数据移出的4位是0001,需要与右移过3位的POLY相XOR 
    3.  0010 1011 1000   
    4.  0010 1011 1000 与 0001 0101 1100  相XOR,XOR后前4位为0011  即表示待测数据移出的4位
    后,需要与POLY进行二次相XOR,结果才能满足要求。 
    5.  0101 0111 0000 与 0001 0101 1100相XOR,          XOR后前4位为0100 
    6.  0101 0111 0000 ,                    前4位为      0101 
    7.  0101 0111 0000 与 0010 1011 1000、0001 0101 1100 相XOR, XOR后前4位为0110 
    8.  0101 0111 0000 与 0010 1011 1000,             XOR后前4位为0111 
    9.  1010 1110 0000 与 0010 1011 1000相XOR,          XOR后前4位为1000 
    10. 1010 1110 0000 与 0010 1011 1000、0001 0101 1100相XOR, XOR后前4位为1001 
    11. 1010 1110 0000,                    前4位为      1010 
    12. 1010 1110 0000 与 0001 0101 1100相XOR,          XOR后前4位为1011 
    13. 1010 1110 0000 与 0101 0111 0000、0010 1011 1000、0001 0101 1100相XOR, XOR后前4位为
    1100 
    14. 1010 1110 0000 与 0101 0111 0000、0010 1011 1000相XOR, XOR后前4位为1101 
    15. 1010 1110 0000 与 0101 0111 0000、0001 0101 1100相XOR, XOR后前4位为1110 
    16. 1010 1110 0000 与 0101 0111 0000相XOR,          XOR后前4位为1111 
     
    以XOR后得到的结果的前4位做为索引值,以XOR后得到的结果的后8位做为表值,生成一张表,即: 
    TABLE[0]=0000 0000B; 
    TABLE[1]=0101 1100B; 
    TABLE[2]=1011 1000B; 
    TABLE[3]=[(0010 1011 1000B ^ 0001 0101 1100B) >> 4 ] & 0xff 
    .... 
    这张表我叫它为“直接查询表”。 
     
    就是说,一次移出的待测数据的4位bit,有2^4个值,即0000,0001,0010,....,1111,根据这个值
    来查表,找到相应的表值,再用表值来XOR寄存器中的待测数据。 
     
    所以,如果一次移出待测数据的8位bit,即一次进行一个字节的计算,则表格有2^8=256个表值。 
    CRC16和CRC32都是一次处理一个字节的,所以它们的查询表有256个表值。 
     
    “驱动表法”算法为: 
                  3    2    1    0   Bytes 
               +----+----+----+----+ 
        +-----<|    |    |    |    | <----- Augmented message(扩展0后的数据) 
        |      +----+----+----+----+ 
        |      MSB       ^        LSB 
        |                | 
        |               XOR 
        |                | 
        |     0+----+----+----+----+ 
    查表v      +----+----+----+----+ 
        |      +----+----+----+----+ 
        |      +----+----+----+----+ 
        |      +----+----+----+----+ 
        |      +----+----+----+----+ 
        |      +----+----+----+----+ 
        +----->+----+----+----+----+ 
               +----+----+----+----+ 
               +----+----+----+----+ 
               +----+----+----+----+ 
               +----+----+----+----+ 
            255+----+----+----+----+ 
     
    描述: 
    1:register左移一个字节,从原始数据中读入一个新的字节.  
    2:利用刚从register移出的字节作为下标定位 table 中的一个32位的值  
    3:把这个值XOR到register中。 
    4:如果还有未处理的数据则回到第一步继续执行。 
    用C可以写成这样: 
       r=0;            //r是寄存器,先初始化为0 
       while (len--)   //len是已扩展0之后的待测数据的长度 
         { 
          byte t = (r >> 24) & 0xFF; 
          r = (r << 8) | *p++;     //p是指向待测数据的指针(待测数据需已经扩展过0) 
          r^=table[t];       //table是查询表 
         } 
    这个代码可以优化为: 
      r=0;           //r是寄存器,先初始化为0 
       while (len--) //len是已扩展0之后的待测数据的字节长度 
              r = ((r << 8) | *p++) ^ t[(r >> 24) & 0xFF]; //p是指向待测数据的指针(待
    测数据需已经扩展过0),t是查询表 
     
    注意: 
    这个“驱动表法”算法和“直接计算法”是完全一样的,不仅结果完全一样,处理方式也是完全
    一样的,所以“驱动表法”可以完全替代“直接计算法”! 
    原始数据都需要先用0扩展W位;最开始的几次循环的实质都只是先将待测数据移动到寄存器中
    去而已; 
    会发现,这个算法用到的“直接查询表”的表值,和网上公开的查询表(我叫它“正规查询表”)
    的表值不一样!为什么?因为网上公开的正规查询表是用于“颠倒”算法的!后述。 
    会发现,这个算法,计算出的CRC32值,同样与WINRAR计算出来的不一样。 
     
    生成的“直接查询表”的内容是: 
    CRC16直接查询表 
    00H    0000  8005  800F  000A 
    04H    801B  001E  0014  8011 
    08H    8033  0036  003C  8039 
    0CH    0028  802D  8027  0022 
    10H    8063  0066  006C  8069 
    14H    0078  807D  8077  0072 
    18H    0050  8055  805F  005A 
    1CH    804B  004E  0044  8041 
    20H    80C3  00C6  00CC  80C9 
    24H    00D8  80DD  80D7  00D2 
    28H    00F0  80F5  80FF  00FA 
    2CH    80EB  00EE  00E4  80E1 
    30H    00A0  80A5  80AF  00AA 
    34H    80BB  00BE  00B4  80B1 
    38H    8093  0096  009C  8099 
    3CH    0088  808D  8087  0082 
    40H    8183  0186  018C  8189 
    44H    0198  819D  8197  0192 
    48H    01B0  81B5  81BF  01BA 
    4CH    81AB  01AE  01A4  81A1 
    50H    01E0  81E5  81EF  01EA 
    54H    81FB  01FE  01F4  81F1 
    58H    81D3  01D6  01DC  81D9 
    5CH    01C8  81CD  81C7  01C2 
    60H    0140  8145  814F  014A 
    64H    815B  015E  0154  8151 
    68H    8173  0176  017C  8179 
    6CH    0168  816D  8167  0162 
    70H    8123  0126  012C  8129 
    74H    0138  813D  8137  0132 
    78H    0110  8115  811F  011A 
    7CH    810B  010E  0104  8101 
    80H    8303  0306  030C  8309 
    84H    0318  831D  8317  0312 
    88H    0330  8335  833F  033A 
    8CH    832B  032E  0324  8321 
    90H    0360  8365  836F  036A 
    94H    837B  037E  0374  8371 
    98H    8353  0356  035C  8359 
    9CH    0348  834D  8347  0342 
    A0H    03C0  83C5  83CF  03CA 
    A4H    83DB  03DE  03D4  83D1 
    A8H    83F3  03F6  03FC  83F9 
    ACH    03E8  83ED  83E7  03E2 
    B0H    83A3  03A6  03AC  83A9 
    B4H    03B8  83BD  83B7  03B2 
    B8H    0390  8395  839F  039A 
    BCH    838B  038E  0384  8381 
    C0H    0280  8285  828F  028A 
    C4H    829B  029E  0294  8291 
    C8H    82B3  02B6  02BC  82B9 
    CCH    02A8  82AD  82A7  02A2 
    D0H    82E3  02E6  02EC  82E9 
    D4H    02F8  82FD  82F7  02F2 
    D8H    02D0  82D5  82DF  02DA 
    DCH    82CB  02CE  02C4  82C1 
    E0H    8243  0246  024C  8249 
    E4H    0258  825D  8257  0252 
    E8H    0270  8275  827F  027A 
    ECH    826B  026E  0264  8261 
    F0H    0220  8225  822F  022A 
    F4H    823B  023E  0234  8231 
    F8H    8213  0216  021C  8219 
    FCH    0208  820D  8207  0202 
     
     
    CRC32直接查询表 
    00H    00000000  04C11DB7  09823B6E  0D4326D9 
    04H    130476DC  17C56B6B  1A864DB2  1E475005 
    08H    2608EDB8  22C9F00F  2F8AD6D6  2B4BCB61 
    0CH    350C9B64  31CD86D3  3C8EA00A  384FBDBD 
    10H    4C11DB70  48D0C6C7  4593E01E  4152FDA9 
    14H    5F15ADAC  5BD4B01B  569796C2  52568B75 
    18H    6A1936C8  6ED82B7F  639B0DA6  675A1011 
    1CH    791D4014  7DDC5DA3  709F7B7A  745E66CD 
    20H    9823B6E0  9CE2AB57  91A18D8E  95609039 
    24H    8B27C03C  8FE6DD8B  82A5FB52  8664E6E5 
    28H    BE2B5B58  BAEA46EF  B7A96036  B3687D81 
    2CH    AD2F2D84  A9EE3033  A4AD16EA  A06C0B5D 
    30H    D4326D90  D0F37027  DDB056FE  D9714B49 
    34H    C7361B4C  C3F706FB  CEB42022  CA753D95 
    38H    F23A8028  F6FB9D9F  FBB8BB46  FF79A6F1 
    3CH    E13EF6F4  E5FFEB43  E8BCCD9A  EC7DD02D 
    40H    34867077  30476DC0  3D044B19  39C556AE 
    44H    278206AB  23431B1C  2E003DC5  2AC12072 
    48H    128E9DCF  164F8078  1B0CA6A1  1FCDBB16 
    4CH    018AEB13  054BF6A4  0808D07D  0CC9CDCA 
    50H    7897AB07  7C56B6B0  71159069  75D48DDE 
    54H    6B93DDDB  6F52C06C  6211E6B5  66D0FB02 
    58H    5E9F46BF  5A5E5B08  571D7DD1  53DC6066 
    5CH    4D9B3063  495A2DD4  44190B0D  40D816BA 
    60H    ACA5C697  A864DB20  A527FDF9  A1E6E04E 
    64H    BFA1B04B  BB60ADFC  B6238B25  B2E29692 
    68H    8AAD2B2F  8E6C3698  832F1041  87EE0DF6 
    6CH    99A95DF3  9D684044  902B669D  94EA7B2A 
    70H    E0B41DE7  E4750050  E9362689  EDF73B3E 
    74H    F3B06B3B  F771768C  FA325055  FEF34DE2 
    78H    C6BCF05F  C27DEDE8  CF3ECB31  CBFFD686 
    7CH    D5B88683  D1799B34  DC3ABDED  D8FBA05A 
    80H    690CE0EE  6DCDFD59  608EDB80  644FC637 
    84H    7A089632  7EC98B85  738AAD5C  774BB0EB 
    88H    4F040D56  4BC510E1  46863638  42472B8F 
    8CH    5C007B8A  58C1663D  558240E4  51435D53 
    90H    251D3B9E  21DC2629  2C9F00F0  285E1D47 
    94H    36194D42  32D850F5  3F9B762C  3B5A6B9B 
    98H    0315D626  07D4CB91  0A97ED48  0E56F0FF 
    9CH    1011A0FA  14D0BD4D  19939B94  1D528623 
    A0H    F12F560E  F5EE4BB9  F8AD6D60  FC6C70D7 
    A4H    E22B20D2  E6EA3D65  EBA91BBC  EF68060B 
    A8H    D727BBB6  D3E6A601  DEA580D8  DA649D6F 
    ACH    C423CD6A  C0E2D0DD  CDA1F604  C960EBB3 
    B0H    BD3E8D7E  B9FF90C9  B4BCB610  B07DABA7 
    B4H    AE3AFBA2  AAFBE615  A7B8C0CC  A379DD7B 
    B8H    9B3660C6  9FF77D71  92B45BA8  9675461F 
    BCH    8832161A  8CF30BAD  81B02D74  857130C3 
    C0H    5D8A9099  594B8D2E  5408ABF7  50C9B640 
    C4H    4E8EE645  4A4FFBF2  470CDD2B  43CDC09C 
    C8H    7B827D21  7F436096  7200464F  76C15BF8 
    CCH    68860BFD  6C47164A  61043093  65C52D24 
    D0H    119B4BE9  155A565E  18197087  1CD86D30 
    D4H    029F3D35  065E2082  0B1D065B  0FDC1BEC 
    D8H    3793A651  3352BBE6  3E119D3F  3AD08088 
    DCH    2497D08D  2056CD3A  2D15EBE3  29D4F654 
    E0H    C5A92679  C1683BCE  CC2B1D17  C8EA00A0 
    E4H    D6AD50A5  D26C4D12  DF2F6BCB  DBEE767C 
    E8H    E3A1CBC1  E760D676  EA23F0AF  EEE2ED18 
    ECH    F0A5BD1D  F464A0AA  F9278673  FDE69BC4 
    F0H    89B8FD09  8D79E0BE  803AC667  84FBDBD0 
    F4H    9ABC8BD5  9E7D9662  933EB0BB  97FFAD0C 
    F8H    AFB010B1  AB710D06  A6322BDF  A2F33668 
    FCH    BCB4666D  B8757BDA  B5365D03  B1F740B4 
     
     
     
     
    “驱动表法”的程序: 
     
    // 注意:因生成项POLY最高位一定为“1”,故略去最高位的"1", 
    unsigned short cnCRC_16 = 0x8005;    // CRC-16 = X16 + X15 + X2 + X0  
    unsigned short cnCRC_CCITT = 0x1021; // CRC-CCITT = X16 + X12 + X5 + X0,据说这个 16 位 CRC 多项式比上一个要好  
    unsigned long cnCRC_32 = 0x04C11DB7; //采用正规的CRC32的POLY 
    unsigned long Table_CRC16[256];     // CRC16 表  
    unsigned long Table_CRC32[256];     // CRC32 表  
     
     
    // 构造 16 位 CRC 表 "直接查询表" 
    unsigned short i16, j16;  
    unsigned short nData16;  
    unsigned short nAccum16;  
    for ( i16 = 0; i16 < 256; i16++ )  
    {  
      nData16 = ( unsigned short )( i16 << 8 );  
      nAccum16 = 0;  
      for ( j16 = 0; j16 < 8; j16++ )  
      {  
        if ( ( nData16 ^ nAccum16 ) & 0x8000 )  
        nAccum16 = ( nAccum16 << 1 ) ^ cnCRC_16;   //也可以用cnCRC_CCITT 
        else  
        nAccum16 <<= 1;  
        nData16 <<= 1;  
      }  
      Table_CRC16[i16] = ( unsigned long )nAccum16;  
    }  
     
    // 构造 32 位 CRC 表 "直接查询表" 
    unsigned long i32, j32;  
    unsigned long nData32;  
    unsigned long nAccum32;  
    for ( i32 = 0; i32 < 256; i32++ )  
    {  
      nData32 = ( unsigned long )( i32 << 24 );  
      nAccum32 = 0;  
      for ( j32 = 0; j32 < 8; j32++ )  
      {  
        if ( ( nData32 ^ nAccum32 ) & 0x80000000 )  
          nAccum32 = ( nAccum32 << 1 ) ^ cnCRC_32;  
        else  
          nAccum32 <<= 1;  
        nData32 <<= 1;  
      }  
      Table_CRC32[i32] = nAccum32;  
    }  
     
     
    unsigned char aData[512]={0x31,0x32,0x33,0x34};      //待测数据,为字串"1234" 
    unsigned long aSize; 
    unsigned long i;  
    unsigned char *point; 
     
    // 计算 16 位 CRC 值,CRC-16 或 CRC-CCITT  
    //Table-Driven驱动表法,需要用到“直接查询表”(不能用“正规查询表”);待测数据需扩展0 
    unsigned short CRC16_1;  
    aSize=4;       //数据长度字节(不包含扩展0) 
    CRC16_1 = 0;      //寄存器归0 
    point=aData; 
    while (aSize--)    
      CRC16_1 = ((CRC16_1 << 8) | *point++) ^ Table_CRC16[(CRC16_1 >> 8) & 0xFF];   
    for ( i = 0; i < 2; i++ )    
      CRC16_1 = ((CRC16_1 << 8) ) ^ Table_CRC16[(CRC16_1 >> 8) & 0xFF];  //加入2字节的扩展0 
    //这时, CRC16_1中的值就是CRC 
     
     
     
    // 计算 32 位 CRC-32 值  
    //Table-Driven驱动表法,需要用到“直接查询表”(不能用“正规查询表”);待测数据需扩展0 
    unsigned long CRC32_1;  
    aSize=4;       //数据长度字节(不包含扩展0) 
    CRC32_1=0x0;      //寄存器归0 
    point=aData; 
    while (aSize--)    
      CRC32_1 = ((CRC32_1 << 8) | *point++) ^ Table_CRC32[(CRC32_1 >> 24) & 0xFF];   
    for ( i = 0; i < 4; i++ )   CRC32_1 = ((CRC32_1 << 8) ) ^ Table_CRC32[(CRC32_1 >> 24) & 0xFF];//加入4字节的扩展0 
    //这时, CRC32_1中的值就是CRC 
     
     
     
    打印查询表的语句:(在TC中实现) 
    for ( i16 = 0; i16 < 256; i16++ )  
    {  
    printf("%02xh    %04x  %04x  %04x  %04x\n",i16,( unsigned short)Table_CRC16[i16],( unsigned 
    short)Table_CRC16[i16+1],( unsigned short)Table_CRC16[i16+2],( unsigned short)Table_CRC16[i16+3]); 
    i16++; 
    i16++; 
    i16++; 

     
    for ( i16 = 0; i16 < 256; i16++ )  
    {  
    printf("%02xh    %08lx  %08lx  %08lx  
    %08lx\n",i16,Table_CRC32[i16],Table_CRC32[i16+1],Table_CRC32[i16+2],Table_CRC32[i16+3]); 
    i16++; 
    i16++; 
    i16++; 

     
     
    五、  直驱表法  DIRECT TABLE ALGORITHM 
     
    对于上面的算法: 
    1.对于尾部的w/8个扩展0字节,事实上它们的作用只是确保所有的原始数据都已被送入register,
    并且被算法处理。 
    2.如果register中的初始值是0,那么开始的4次循环,作用只是把原始数据的头4个字节送入寄存
    器,而没有进行真正的除法操作。就算初始值不是0(我注:这里并没有说是“寄存器的初始值”,而是指
    算法开始时的“初始化值”),开始的4次循环也只是把原始数据的头4个字节移入到register中,然后再
    把它们和一个特定常数相XOR(我注:即这时进行初始化操作,后述)。 
    3.因为有交换律:(A xor B) xor C = A xor (B xor C) 
    这些信息意味着,上面提到的算法可以被优化,待测数据不需要先循环几次进入到寄存器中后再进行
    处理,而是数据直接就可以处理到寄存器中。 
    可以这样:数据可以先与刚从寄存器移出的字节相XOR,用得到的结果值进行查表,再用表值XOR寄存
    器。这引出了以下“直驱表法”算法: 
        +-----<Message (non augmented) 待测数据(不用扩展0) 
        | 
        v         3    2    1    0   Bytes 
        |      +----+----+----+----+ 
       XOR----<|    |    |    |    | 
        |      +----+----+----+----+ 
        |      MSB       ^        LSB 
        |                | 
        |               XOR 
        |                | 
        |     0+----+----+----+----+ 
    查表v      +----+----+----+----+ 
        |      +----+----+----+----+ 
        |      +----+----+----+----+ 
        |      +----+----+----+----+ 
        |      +----+----+----+----+ 
        |      +----+----+----+----+ 
        +----->+----+----+----+----+ 
               +----+----+----+----+ 
               +----+----+----+----+ 
               +----+----+----+----+ 
               +----+----+----+----+ 
            255+----+----+----+----+ 
     
     
    “直驱表法”算法: 
    1.  Shift the register left by one byte, reading in a new message byte.(我注:
    老外的这句话有问题,应只是Shift the register left by one byte,而不将新的信息字节
    读入register中。所以翻译为:寄存器左移一个字节) 
    2.  XOR the top byte just rotated out of the register with the next message byte 
    to yield an index into the table ([0,255]). 将刚从register移出的字节与新的信息字节
    相XOR,结果值作为定位索引,从查询表中取得相应的表值。 
    3.  XOR the table value into the register. 把表值XOR到register中 
    4.  Goto 1 iff more augmented message bytes. 如果还有未处理的数据则回到第一步
    继续执行。 
    用C可以写成这样: 
       r=0;   //r是寄存器,先初始化为0 
       while (len--)   //len是待测数据(不用扩展0)的字节长度 
              r = (r<<8) ^ t[(r >> 24) ^ *p++];  //p是指向待测数据的指针,t是查询表 
    算法相当于: 
    寄存器左移出1字节,右边补0; 
    移出的字节与待测信息字节进行XOR,根据结果值查表,得表值 
    表值与寄存器进行XOR 
     
    注意: 
    这个“直驱表法”算法的数学原理我也不明白,但它肯定是从“驱动表法”算法推导出来的,得
    到的CRC结果值是完全一样的!只是它们的处理方式是不一样的。 
    这个算法很方便,原始数据不需要先用0扩展W位; 
    这个算法很方便,第一次循环就能够处理待测数据并在寄存器中生成结果,而不单纯只是将数据
    移动到寄存器中去而已; 
    这个算法,用的是和“驱动表法”同样的“直接查询表”,而不是“正规查询表”。 
    正是由于处理方式不一样,所以如果寄存器初始化预置值不为0,那么本算法可不受影响,而“驱
    动表法”则需要将预置值再另外XOR到寄存器中。后述。 
     
     
     
     
     
    “直驱表法”的程序: 
     
    // 注意:因生成项POLY最高位一定为“1”,故略去最高位的"1", 
    unsigned short cnCRC_16 = 0x8005;    // CRC-16 = X16 + X15 + X2 + X0  
    unsigned short cnCRC_CCITT = 0x1021; // CRC-CCITT = X16 + X12 + X5 + X0,据说这个 16 位 CRC 多项式比上一个要好  
    unsigned long cnCRC_32 = 0x04C11DB7; //采用正规的CRC32的POLY 
    unsigned long Table_CRC16[256];     // CRC16 表  
    unsigned long Table_CRC32[256];     // CRC32 表  
     
     
    // 构造 16 位 CRC 表 "直接查询表" 
    unsigned short i16, j16;  
    unsigned short nData16;  
    unsigned short nAccum16;  
    for ( i16 = 0; i16 < 256; i16++ )  
    {  
      nData16 = ( unsigned short )( i16 << 8 );  
      nAccum16 = 0;  
      for ( j16 = 0; j16 < 8; j16++ )  
      {  
        if ( ( nData16 ^ nAccum16 ) & 0x8000 )  
        nAccum16 = ( nAccum16 << 1 ) ^ cnCRC_16;   //也可以用cnCRC_CCITT 
        else  
        nAccum16 <<= 1;  
        nData16 <<= 1;  
      }  
      Table_CRC16[i16] = ( unsigned long )nAccum16;  
    }  
     
    // 构造 32 位 CRC 表 "直接查询表" 
    unsigned long i32, j32;  
    unsigned long nData32;  
    unsigned long nAccum32;  
    for ( i32 = 0; i32 < 256; i32++ )  
    {  
      nData32 = ( unsigned long )( i32 << 24 );  
      nAccum32 = 0;  
      for ( j32 = 0; j32 < 8; j32++ )  
      {  
        if ( ( nData32 ^ nAccum32 ) & 0x80000000 )  
          nAccum32 = ( nAccum32 << 1 ) ^ cnCRC_32;  
        else  
          nAccum32 <<= 1;  
        nData32 <<= 1;  
      }  
      Table_CRC32[i32] = nAccum32;  
    }  
     
     
    unsigned char aData[512]={0x31,0x32,0x33,0x34};      //待测数据,为字串"1234" 
    unsigned long aSize; 
    unsigned long i;  
    unsigned char *point; 
     
    // 计算 16 位 CRC 值,CRC-16 或 CRC-CCITT  
    //DIRECT TABLE直驱表法,需要用到“直接查询表”(不能用“正规查询表”);待测数据不需要扩展0 
    unsigned short CRC16_2;  
    aSize=4;       //数据长度字节(数据不用扩展0了) 
    CRC16_2 = 0;      //寄存器中预置初始值 
    point=aData;      
    for ( i = 0; i < aSize; i++ )  
      CRC16_2 = ( CRC16_2 << 8 ) ^ ( unsigned short ) Table_CRC16[( CRC16_2 >> 8 ) ^ *point++];  
    //这时, CRC16_2中的值就是CRC 
     
     
    // 计算 32 位 CRC-32 值  
    //DIRECT TABLE直驱表法,需要用到“直接查询表”(不能用“正规查询表”);待测数据不需要扩展0 
    unsigned long CRC32_2;  
    aSize=4;       //数据长度字节(数据不用扩展0了) 
    CRC32_2 = 0x0;    //寄存器中预置初始值 
    point=aData; 
    for ( i = 0; i < aSize; i++ )  
      CRC32_2 = ( CRC32_2 << 8 ) ^ Table_CRC32[( CRC32_2 >> 24 ) ^ *point++];  
    //这时, CRC32_2中的值就是CRC 
     
     
     
    六、  CRC的参数模型 
     
    实际上,这时已经可以计算出与WINRAR相同的CRC32值了。但是会发现,算出的结果和WINRAR是不
    一样的,为什么?因为不仅仅是生成项POLY会影响到CRC值,还有很多参数会影响到最终的CRC值! 
    CRC计算,需要有CRC参数模型,比如CRC32的参数模型是: 
       Name   : "CRC-32" 
       Width  : 32 
       Poly   : 04C11DB7 
       Init   : FFFFFFFF 
       RefIn  : True 
       RefOut : True 
       XorOut : FFFFFFFF 
       Check  : CBF43926 
    解释: 
    NAME  
    名称 
    WIDTH  
    宽度,即CRC比特数 
    POLY  
    生成项的简写。以16进制表示,即是0x04C11DB7。忽略了最高位的"1",即完整的生成项是
    0x104C11DB7。 
    重要的一点是,这是“未颠倒”的生成项!前面说过,“颠倒的”生成项是0xEDB88320。 
     
    INIT  
    这是算法开始时寄存器的初始化预置值,十六进制表示。 
    这个值可以直接赋值给“直驱表法”算法中的寄存器,作为寄存器的初始值! 
    而对于“驱动表法”算法及“直接计算法”,寄存器的初始值必须是0!前面几次循环先将待测数
    据移入到寄存器中,当寄存器装满后,再用这个初始化预置值去XOR寄存器,这样寄存器就被这个
    值初始化了! 
    这点很重要!!如果在“驱动表法”算法开始时,寄存器的初始值不为0,那么寄存器中的值就会
    相当于是待测数据了,这样算出的CRC结果就不对了!我们的目的是用预置值去初始化寄存器,而
    不是将预置值作为待测数据去处理! 
    REFIN  
    这个值是真TRUE或假FALSE。 
    如果这个值是FALSE,表示待测数据的每个字节都不用“颠倒”,即BIT7仍是作为最高位,BIT0
    作为最低位。 
    如果这个值是TRUE,表示待测数据的每个字节都要先“颠倒”,即BIT7作为最低位,BIT0作为最
    高位。 
    REFOUT  
    这个值是真TRUE或假FALSE。 
    如果这个值是FALSE,表示计算结束后,寄存器中的值直接进入XOROUT处理即可。 
    如果这个值是TRUE,表示计算结束后,寄存器中的值要先“颠倒”,再进入XOROUT处理。注意,
    这是将整个寄存器的值颠倒,因为寄存器的各个字节合起来表达了一个值,如果只是对各个字节各
    自颠倒,那结果值就错误了。 
    XOROUT  
    这是W位长的16进制数值。 
    这个值与经REFOUT后的寄存器的值相XOR,得到的值就是最终正式的CRC值! 
    CHECK  
    这不是定义值的一部分,这只是字串"123456789"用这个CRC参数模型计算后得到的CRC值,作为参
    考。 
     
    我们发现,CRC32模型的Init=0xFFFFFFFF,就是说寄存器要用0xFFFFFFFF进行初始化,而不是0。 
    为什么?因为待测数据的内容和长度是随机的,如果寄存器初始值为0,那么,待测字节是1字节的
    0x00,与待测字节是N字节的0x00,计算出来的CRC32值都是0,那CRC值就没有意义了!所以寄存器用
    0xFFFFFFFF进行初始化,就可以避免这个问题了! 
     
    RefIn=True,表示输入数据的每个字节需要“颠倒”!为什么要“颠倒”,因为很多硬件在发送时是先
    发送最低位LSB的!比如UART等。 
    字节顺序不用颠倒,只是每个字节内部的比特进行颠倒。例如待测的字串是"1234",这时也是一样先
    处理"1",再处理"2",一直到处理"4"。处理字符"1"时,它是0x31,即0011 0001,需要先将它颠倒,变
    成低位在前,即1000 1100,即0x8C,再进行处理。 
    也就是说,待处理的数据是0x31 32 33 34,颠倒后就变成0x8C 4C CC 2C,再进行CRC计算。 
     
    RefOut=True,表示计算完成后,要将寄存器中的值再颠倒。注意,这是将整个寄存器的值颠倒,即如
    果寄存器中的值是0x31 32 33 34,颠倒后就变成0x2C CC 4C 8C! 
     
    XorOut=FFFFFFFF,表示还需要将结果值与0xffffffff进行XOR,这样就得到最终的CRC32值了! 
     
    我们直接用“直驱表法”,计算字串"1234"的CRC32值。 
     
    程序如下: 
    要先做一个颠倒比特的子程序: 
    unsigned long int Reflect(unsigned long int ref, char ch)  

    unsigned long int value=0;  
      // 交换bit0和bit7,bit1和bit6,类推  
    for(int i = 1; i < (ch + 1); i++)  
    {  
      if(ref & 1)  
        value |= 1 << (ch - i);  
      ref >>= 1;  
    }  
    return value;  

     
    在主程序中的程序: 
    // 注意:因生成项POLY最高位一定为“1”,故略去最高位的"1", 
    unsigned long cnCRC_32 = 0x04C11DB7; //采用正规的CRC32的POLY 
    unsigned long Table_CRC32[256];     // CRC32 表  
     
    // 构造 32 位 CRC 表 "直接查询表" 
    unsigned long i32, j32;  
    unsigned long nData32;  
    unsigned long nAccum32;  
    for ( i32 = 0; i32 < 256; i32++ )  
    {  
      nData32 = ( unsigned long )( i32 << 24 );  
      nAccum32 = 0;  
      for ( j32 = 0; j32 < 8; j32++ )  
      {  
        if ( ( nData32 ^ nAccum32 ) & 0x80000000 )  
          nAccum32 = ( nAccum32 << 1 ) ^ cnCRC_32;  
        else  
          nAccum32 <<= 1;  
        nData32 <<= 1;  
      }  
      Table_CRC32[i32] = nAccum32;  
    }  
     
    unsigned char aData[512]={0x31,0x32,0x33,0x34};      //待测数据,为字串"1234" 
    unsigned long aSize; 
    unsigned long i;  
    unsigned char *point; 
    unsigned char chtemp; 
    // 计算 32 位 CRC-32 值  
    //Table-Driven驱动表法,需要用到“直接查询表”(不能用“正规查询表”);待测数据需扩展0 
    unsigned long ii;  
    unsigned long CRC32_1;  
    aSize=4;       //数据长度字节(不包含扩展0) 
    CRC32_1=0x0;      //寄存器归0 
    point=aData; 
    ii=0; 
    while (aSize--)    

      chtemp=*point++; 
      chtemp=(unsigned char)Reflect(chtemp, 8);   //将数据字节内部的比特进行颠倒 
      CRC32_1 = ((CRC32_1 << 8) | chtemp) ^ Table_CRC32[(CRC32_1 >> 24) & 0xFF];   
      ii++; 
      if (ii==4) CRC32_1=CRC32_1^0xffffffff;//当寄存器装满4个字节后,用预置值0xffffffff去XOR寄存器,这样寄存器就
    被这个值初始化了! 

    for ( i = 0; i < 4; i++ )    

      CRC32_1 = ((CRC32_1 << 8) ) ^ Table_CRC32[(CRC32_1 >> 24) & 0xFF];  //加入4字节的扩展0 
      ii++; 
      if (ii==4) CRC32_1=CRC32_1^0xffffffff;//如果待测数据小于4字节,则只有在这里寄存器才会装满4个字节,才进行初
    始化 

    CRC32_1=Reflect(CRC32_1, 32);  //颠倒寄存器的值 
    CRC32_1=CRC32_1^0xffffffff;   //寄存器的值与0xffffffff异或 
    //这时, CRC32_1中的值就是CRC 
     
     
    //DIRECT TABLE直驱表法,需要用到“直接查询表”(不能用“正规查询表”);待测数据不需要扩展0 
    unsigned long CRC32_2;  
    aSize=4;       //数据长度字节(数据不用扩展0了) 
    CRC32_2 = 0xffffffff;      //寄存器中直接预置初始值0xffffffff即可 
    point=aData; 
    for ( i = 0; i < aSize; i++ )  

      chtemp=*point++; 
      chtemp=(unsigned char)Reflect(chtemp, 8);   //将数据字节内部的比特进行颠倒 
      CRC32_2 = ( CRC32_2 << 8 ) ^ Table_CRC32[( CRC32_2 >> 24 ) ^ chtemp]; 

     
    CRC32_2=Reflect(CRC32_2, 32);  //颠倒寄存器的值 
    CRC32_2=CRC32_2^0xffffffff;     //寄存器的值与0xffffffff异或 
    //这时, CRC32_2中的值就是CRC 
     
     
    得到的结果与WINRAR的计算结果是完全一样的!成功了! 
     
     
     
    其它的CRC参数模型: 
       Name   : "CRC-16" 
       Width  : 16 
       Poly   : 8005 
       Init   : 0000 
       RefIn  : True 
       RefOut : True 
       XorOut : 0000 
       Check  : BB3D 
     
       Name   : "CRC-16/CITT" 
       Width  : 16 
       Poly   : 1021 
       Init   : FFFF 
       RefIn  : False 
       RefOut : False 
       XorOut : 0000 
       Check  : ? 
     
       Name   : "XMODEM" 
       Width  : 16 
       Poly   : 8408 
       Init   : 0000 
       RefIn  : True 
       RefOut : True 
       XorOut : 0000 
       Check  : ? 
     
       Name   : "ARC" 
       Width  : 16 
       Poly   : 8005 
       Init   : 0000 
       RefIn  : True 
       RefOut : True 
       XorOut : 0000 
       Check  : ? 
     
     
    七、  最后的战斗-“颠倒的直驱表法”算法 "Reflected" Table-Driven Implementations 
     
    颠倒,也就是镜像! 
    CRC32要求输入的字节要颠倒,那么在程序中,在对每个字节处理前,还要先把这个字节先颠倒一下,
    再处理,那不是超级麻烦! 
    所以就把“直驱表法”算法颠倒一下(查询表颠倒),那么算法就可以直接处理不颠倒的字节了,就方
    便多了。 
    我们把算法照镜子: 
     
             “直驱表法”                    镜子               “颠倒的直驱表法” 
     
        +-----<Message (non augmented) 待测数据(要颠倒) 
        | 
        v         3    2    1    0   Bytes 
        |      +----+----+----+----+ 
       XOR----<|    |    |    |    | 
        |      +----+----+----+----+ 
        |      MSB       ^        LSB 
        |                | 
        |               XOR 
        |                | 
        |   00H +----+----+----+----+ 
    查表v  01H +----+----+----+----+ 04C11DB7H 
        |   02H +----+----+----+----+ 
        |   03H +----+----+----+----+ 
        |       +----+----+----+----+ 
        |       +----+----+----+----+ 
        |       +----+----+----+----+ 
        +-----> +----+----+----+----+ 
                +----+----+----+----+ 
            80H +----+----+----+----+ 690CE0EEH 
                +----+----+----+----+ 
                +----+----+----+----+ 
            FFH +----+----+----+----+ 
              索引值和表值都不颠倒 
     
    “颠倒的直驱表法”用的查询表,是网上可以找到的查询表,我叫它“正规查询表”,实际就是“颠倒
    的直接查询表”。对应关系是: 
    “直接查询表”                            “正规查询表”(颠倒的查询表) 
    0000 0000(00H)                         0000 0000(00H) 
    0000 0001(01H)表值04C11DB7H           1000 0000(80H)表值EDB88320H 
    0000 0010(02H)                         0100 0000(C0H) 
    0000 0011(03H)                         1100 0000(20H) 
    0000 0100(04H)                         0010 0000(A0H) 
    ... 
    1000 0000(80H)表值690CE0EEH            0000 0001(01H)表值77073096H 
    ... 
    1111 1111(FFH)                          FFFF FFFF(FFH) 
    待测数据(不颠倒)Message (non augmented) >-----+ 
                                          | 
          Bytes   3    2    1    0        v 
               +----+----+----+----+      | 
               |    |    |    |    |>----XOR 
               +----+----+----+----+      | 
               MSB       ^        LSB     | 
                         |                | 
                        XOR               | 
                         |                | 
               +----+----+----+----+ 00H  | 
     EDB88320H +----+----+----+----+ 80H  v查表 
               +----+----+----+----+ C0H  | 
               +----+----+----+----+ 20H  | 
               +----+----+----+----+ A0H  | 
               +----+----+----+----+      | 
               +----+----+----+----+      | 
               +----+----+----+----+<-----+ 
               +----+----+----+----+ 
    77073096H +----+----+----+----+ 01H 
               +----+----+----+----+ 
               +----+----+----+----+ 
               +----+----+----+----+255 
                              索引值和表值都颠倒 
     
    也就是说,将“直接查询表”的索引值和表值直接镜像就是“正规查询表”。 
    比如,直接查询表的[01H]= 04C11DB7H,因为01H镜像后是80H,04C11DB7H镜像后是EDB88320H,就
    得到正规查询表的[80H]= EDB88320H。 
     
    举例来说,假设待测的原始数据是10H,简单起见,不考虑寄存器移出的字节的影响(即假设它是00H): 
    “直驱表法”,原始数据先颠倒为01H,根据01H查表得04C11DB7H,寄存器移出的字节是向左移。 
    “颠倒的直驱表法”,    直接根据原始数据10H查表得EDB88320H,寄存器移出的字节是向右移。 
    可见,这时这二个方法本质上是一样的。 
     
    对于“直驱表法”,颠倒的数据用不颠倒的表索引值、得到不颠倒的表值寄存器进入寄存器,得到的寄
    存器结果值是不颠倒的,还要再颠倒,变成“颠倒的CRC”。 
    对于“颠倒的直驱表法”,不颠倒的数据用颠倒的表索引值、得到颠倒的表值寄存器进入寄存器,得到
    的寄存器结果值就已经是“颠倒的CRC”,不用再颠倒了。 
    可见,对于REFIN=TRUE并且REFOUT=TRUE的CRC模型来说(注意这个先决条件),就可以直接用“颠
    倒的直驱表法”来代替“直驱表法”,这样原始数据的比特不用镜像,处理起来就很简单。 
     
    那是不是说:不颠倒的数据用不颠倒的表索引值和表值,把得到的寄存器结果值颠倒一下,就能得到
    和颠倒的数据一样的计算结果?不可能的。颠倒的数据和不颠倒的数据是完全不一样的数据,得到的结果
    完全两码事。 
     
    注意: 
    先决条件是REFIN=TRUE并且REFOUT=TRUE的CRC参数模型。 
    “颠倒的直驱表法”用的是“正规查询表”。 
    寄存器的初始化预置值也要颠倒。 
    待测数据每个字节的比特不用颠倒,因为算法的其他部分都做过颠倒处理了。 
    待测数据串肯定不用颠倒,即待测的字串是"1234",这时也是一样先处理"1",再处理"2",一直
    到处理"4"。 
     
    算法如下: 
    1. 将寄存器向右移动一个字节。 
    2. 将刚移出的那个字节与待测数据中的新字节做XOR运算,得到一个指向查询表的索引值。 
    3. 将索引所指的表值与寄存器做XOR运算。 
    4. 如数据没有全部处理完,则跳到步骤1。 
     
    用C可以写成这样: 
       r=0;   //r是寄存器,先初始化为0 
    for(i=0;  i <len;  i++)   //len是待测数据(不用扩展0)的字节长度 
    {  
      r = t[( r^(*(p+i)) ) & 0xff] ^ (r >> 8);  //p是指向待测数据的指针,t是查询表 

     
     
     
    “正规查询表”的内容是: 
    CRC16正规查询表 
      00h   0000 C0C1 C181 0140 C301 03C0 0280 C241 
      08h   C601 06C0 0780 C741 0500 C5C1 C481 0440 
      10h   CC01 0CC0 0D80 CD41 0F00 CFC1 CE81 0E40 
      18h   0A00 CAC1 CB81 0B40 C901 09C0 0880 C841 
      20h   D801 18C0 1980 D941 1B00 DBC1 DA81 1A40 
      28h   1E00 DEC1 DF81 1F40 DD01 1DC0 1C80 DC41 
      30h   1400 D4C1 D581 1540 D701 17C0 1680 D641 
      38h   D201 12C0 1380 D341 1100 D1C1 D081 1040 
      40h   F001 30C0 3180 F141 3300 F3C1 F281 3240 
      48h   3600 F6C1 F781 3740 F501 35C0 3480 F441 
      50h   3C00 FCC1 FD81 3D40 FF01 3FC0 3E80 FE41 
      58h   FA01 3AC0 3B80 FB41 3900 F9C1 F881 3840 
      60h   2800 E8C1 E981 2940 EB01 2BC0 2A80 EA41 
      68h   EE01 2EC0 2F80 EF41 2D00 EDC1 EC81 2C40 
      70h   E401 24C0 2580 E541 2700 E7C1 E681 2640 
      78h   2200 E2C1 E381 2340 E101 21C0 2080 E041 
      80h   A001 60C0 6180 A141 6300 A3C1 A281 6240 
      88h   6600 A6C1 A781 6740 A501 65C0 6480 A441 
      90h   6C00 ACC1 AD81 6D40 AF01 6FC0 6E80 AE41 
      98h   AA01 6AC0 6B80 AB41 6900 A9C1 A881 6840 
      A0h   7800 B8C1 B981 7940 BB01 7BC0 7A80 BA41 
      A8h   BE01 7EC0 7F80 BF41 7D00 BDC1 BC81 7C40 
      B0h   B401 74C0 7580 B541 7700 B7C1 B681 7640 
      B8h   7200 B2C1 B381 7340 B101 71C0 7080 B041 
      C0h   5000 90C1 9181 5140 9301 53C0 5280 9241 
      C8h   9601 56C0 5780 9741 5500 95C1 9481 5440 
      D0h   9C01 5CC0 5D80 9D41 5F00 9FC1 9E81 5E40 
      D8h   5A00 9AC1 9B81 5B40 9901 59C0 5880 9841 
      E0h   8801 48C0 4980 8941 4B00 8BC1 8A81 4A40 
      E8h   4E00 8EC1 8F81 4F40 8D01 4DC0 4C80 8C41 
      F0h   4400 84C1 8581 4540 8701 47C0 4680 8641 
      F8h   8201 42C0 4380 8341 4100 81C1 8081 4040 
     
     
    CRC32正规查询表 
      00h   00000000 77073096 EE0E612C 990951BA 
      04h   076DC419 706AF48F E963A535 9E6495A3 
      08h   0EDB8832 79DCB8A4 E0D5E91E 97D2D988 
      0Ch   09B64C2B 7EB17CBD E7B82D07 90BF1D91 
      10h   1DB71064 6AB020F2 F3B97148 84BE41DE 
      14h   1ADAD47D 6DDDE4EB F4D4B551 83D385C7 
      18h   136C9856 646BA8C0 FD62F97A 8A65C9EC 
      1Ch   14015C4F 63066CD9 FA0F3D63 8D080DF5 
      20h   3B6E20C8 4C69105E D56041E4 A2677172 
      24h   3C03E4D1 4B04D447 D20D85FD A50AB56B 
      28h   35B5A8FA 42B2986C DBBBC9D6 ACBCF940 
      2Ch   32D86CE3 45DF5C75 DCD60DCF ABD13D59 
      30h   26D930AC 51DE003A C8D75180 BFD06116 
      34h   21B4F4B5 56B3C423 CFBA9599 B8BDA50F 
      38h   2802B89E 5F058808 C60CD9B2 B10BE924 
      3Ch   2F6F7C87 58684C11 C1611DAB B6662D3D 
      40h   76DC4190 01DB7106 98D220BC EFD5102A 
      44h   71B18589 06B6B51F 9FBFE4A5 E8B8D433 
      48h   7807C9A2 0F00F934 9609A88E E10E9818 
      4Ch   7F6A0DBB 086D3D2D 91646C97 E6635C01 
      50h   6B6B51F4 1C6C6162 856530D8 F262004E 
      54h   6C0695ED 1B01A57B 8208F4C1 F50FC457 
      58h   65B0D9C6 12B7E950 8BBEB8EA FCB9887C 
      5Ch   62DD1DDF 15DA2D49 8CD37CF3 FBD44C65 
      60h   4DB26158 3AB551CE A3BC0074 D4BB30E2 
      64h   4ADFA541 3DD895D7 A4D1C46D D3D6F4FB 
      68h   4369E96A 346ED9FC AD678846 DA60B8D0 
      6Ch   44042D73 33031DE5 AA0A4C5F DD0D7CC9 
      70h   5005713C 270241AA BE0B1010 C90C2086 
      74h   5768B525 206F85B3 B966D409 CE61E49F 
      78h   5EDEF90E 29D9C998 B0D09822 C7D7A8B4 
      7Ch   59B33D17 2EB40D81 B7BD5C3B C0BA6CAD 
      80h   EDB88320 9ABFB3B6 03B6E20C 74B1D29A 
      84h   EAD54739 9DD277AF 04DB2615 73DC1683 
      88h   E3630B12 94643B84 0D6D6A3E 7A6A5AA8 
      8Ch   E40ECF0B 9309FF9D 0A00AE27 7D079EB1 
      90h   F00F9344 8708A3D2 1E01F268 6906C2FE 
      94h   F762575D 806567CB 196C3671 6E6B06E7 
      98h   FED41B76 89D32BE0 10DA7A5A 67DD4ACC 
      9Ch   F9B9DF6F 8EBEEFF9 17B7BE43 60B08ED5 
      A0h   D6D6A3E8 A1D1937E 38D8C2C4 4FDFF252 
      A4h   D1BB67F1 A6BC5767 3FB506DD 48B2364B 
      A8h   D80D2BDA AF0A1B4C 36034AF6 41047A60 
      ACh   DF60EFC3 A867DF55 316E8EEF 4669BE79 
      B0h   CB61B38C BC66831A 256FD2A0 5268E236 
      B4h   CC0C7795 BB0B4703 220216B9 5505262F 
      B8h   C5BA3BBE B2BD0B28 2BB45A92 5CB36A04 
      BCh   C2D7FFA7 B5D0CF31 2CD99E8B 5BDEAE1D 
      C0h   9B64C2B0 EC63F226 756AA39C 026D930A 
      C4h   9C0906A9 EB0E363F 72076785 05005713 
      C8h   95BF4A82 E2B87A14 7BB12BAE 0CB61B38 
      CCh   92D28E9B E5D5BE0D 7CDCEFB7 0BDBDF21 
      D0h   86D3D2D4 F1D4E242 68DDB3F8 1FDA836E 
      D4h   81BE16CD F6B9265B 6FB077E1 18B74777 
      D8h   88085AE6 FF0F6A70 66063BCA 11010B5C 
      DCh   8F659EFF F862AE69 616BFFD3 166CCF45 
      E0h   A00AE278 D70DD2EE 4E048354 3903B3C2 
      E4h   A7672661 D06016F7 4969474D 3E6E77DB 
      E8h   AED16A4A D9D65ADC 40DF0B66 37D83BF0 
      ECh   A9BCAE53 DEBB9EC5 47B2CF7F 30B5FFE9 
      F0h   BDBDF21C CABAC28A 53B39330 24B4A3A6 
      F4h   BAD03605 CDD70693 54DE5729 23D967BF 
      F8h   B3667A2E C4614AB8 5D681B02 2A6F2B94 
      FCh   B40BBE37 C30C8EA1 5A05DF1B 2D02EF8D 
     
     
     
    “颠倒的直驱表法”的程序: 
     
    同样要先做一个颠倒比特的子程序: 
    unsigned long int Reflect(unsigned long int ref, char ch)  

    unsigned long int value=0;  
      // 交换bit0和bit7,bit1和bit6,类推  
    for(int i = 1; i < (ch + 1); i++)  
    {  
      if(ref & 1)  
        value |= 1 << (ch - i);  
      ref >>= 1;  
    }  
    return value;  

     
    在主程序中的程序: 
    unsigned long int crc32_table[256];  
    unsigned long int ulPolynomial = 0x04c11db7;  
    unsigned long int crc,temp;  
     
    for(int i = 0; i <= 0xFF; i++)   // 生成CRC32“正规查询表” 
    {  
      temp=Reflect(i, 8);  
      crc32_table[i]= temp<< 24;  
      for (int j = 0; j < 8; j++) 
      {  
        unsigned long int t1,t2;  
        unsigned long int flag=crc32_table[i]&0x80000000;  
        t1=(crc32_table[i] << 1);  
        if(flag==0)  
          t2=0;  
        else  
          t2=ulPolynomial;  
        crc32_table[i] =t1^t2 ;  
      }  
      crc=crc32_table[i];  
      crc32_table[i] = Reflect(crc32_table[i], 32);  
    }  
     
     
       //计算CRC32值 
    unsigned   long   CRC32; 
    BYTE  DataBuf[512]={0x31,0x32,0x33,0x34};   //待测数据,为字串"1234" 
    unsigned   long   len; 
    unsigned   long   ii;  
    unsigned   long   m_CRC = 0xFFFFFFFF;   //寄存器中预置初始值 
    BYTE   *p;  
     
    len=4;             //待测数据的字节长度 
    p = DataBuf;  
    for(ii=0;  ii <len;  ii++)  
    {  
      m_CRC = crc32_table[( m_CRC^(*(p+ii)) ) & 0xff] ^ (m_CRC >> 8);  //计算 
    }  
    CRC32= ~m_CRC;     //取反。经WINRAR对比,CRC32值正确!! 
    //这时, CRC32中的值就是CRC 
     
     
    八、  结束 
    以上程序均在VC6中测试成功,很多程序是直接抄网上的再修改。 
    CRC计算其实很简单,也就才4个算法,移来移去、优化来优化去而已。 
    但是就是这么简单的东西,国内网上好像没有文章能说得完全明白。搞得我这种笨人花了整整5天才
    整理出来。 
    书上的都是理论一大堆,这个式子那个式子的,一头雾水,我这个非专业人士更看不懂。 
    应该说,用程序实现和优化算法是容易的,创造出CRC方法的人才是真正的强人。

    更多相关内容
  • 我学习CRC32、CRC16、CRC 原理和算法的总结(与WINRAR 结果一致),里面详细描述了CRC原理,应用,及相应推导过程,是CRC讲得最全的,从入门到高阶及C语言写的例程都有!~~
  • 如何理解CRC原理

    2016-01-14 15:56:58
    一篇很容易让不懂CRC的人5分钟就理解的好总结
  • (简单易懂的CRC原理阐述) 网上大多的教材都是面向大佬的很多细节原理都没有讲清楚,对于我们这些新萌菜鸟们实在太不友好了。于是我写一篇相对轻松易懂的博客,希望能对学习CRC的朋友们有所帮助吧! 什么是...

    不要跑,CRC没这么难!(简单易懂的CRC原理阐述)


    网上大多的教材都是面向大佬的很多细节原理都没有讲清楚,对于我们这些新萌菜鸟们实在太不友好了。于是我写一篇相对轻松易懂的博客,希望能对学习CRC的朋友们有所帮助吧!

    什么是CRC???


    你说小学3年级的小明同学不知好歹喜欢村长女儿王大麻子,于是羞涩的他想到写一封情书已表心意。正所谓闺女似情人,爱女心切的村长凡是信件统统要过他之手。如果这份情书被她爸稍加“几笔”岂不悲剧了?

    奇偶验证

    如何验证情书是否被动过手脚(验证数据是否损坏),介于王大麻子数学不行,数数还行。作为数学课代表的小明同学立刻想到一个好主意:将所有的文字转化二进制,只要数一数1的数量是奇数还是偶数不就可以了吗!

    比如我要传递M这个字符那么他的ASCII的值为0100 1101(M),就是数据末尾加上一个1或0,使其整个数据的1的数量可以凑齐奇数或偶数。

    如果规定信件所有1的个数为奇数的话,那么0100 1101(M)才4个1,我们就数据的末尾加上一个1凑齐奇数(5个1):0100 1101 1;如果数据中的1刚好奇数,我们就在末尾加上一个0就可(这个方法叫做奇校验),当然相反如果规定的信件所有1的个数为偶数(偶校验),刚好处理的方法也是相反。

    虽然这个方法简单到连他没有上学的弟弟都做得起(很容易通过硬件方式实现验证),但是这个的出错率是五五开啊(刚好少/多偶数个1),且永远检查不出0的错误(就算多100个零也看不出来)。

    累加和校验

    你说奇偶不行,哪我相加总该行吧?于是乎小明同学又推出第二号方案:将每一个文字(字节)的值相加来验证。

    比如传递LOVE,我们就可以得到四个数字76(L) 79(O) 86(V) 69(E),他们相加可得310,如果这个数字嫌他太大了不好写,我们可以限制他在0~255(一个字节)这个范围之内,那么我们就得到一个验证数字55 =310 – 255(最简单的办法就是减去255的倍数)。然后将数字附加数据后面,对方接受到数据执行同样的操作对比验证数字是否一致。

    虽说这个方法要比上面的方法要可靠一些,但凡事总有列外:

    一、比如数据错误刚好等于验证数字
    我们要传输的数据:76 79 86 69 310(验证数字)
    发生错误的数据: 76 78(-1) 87(+1) 69 310(验证数字还是一样的)

    二、单个字符的出错率为1/256

    CRC验证原理

    无数日夜小明同学冥思苦想,最终还剩最后三根头发之际他学会除法,头顶一凉想到一个绝佳主意:如果我将信件上的所有文字组合成一个长数字,然后用一个我和王大麻子都知道的数字(约定的多项式)去除以,将余数作为一个验证数字的话……

    假设我要传输一个字符87(W),和王大麻子约定除数为6,那么结果很明显就是87 ÷ 6 = 14……3,那么我们可以将3作为验证数字附加原始数据的末尾发送。

    但明显我们常规的借位除法大大超出了王大麻子的数学水平,于是小明同学决定不做人了发明一个二进制除法,并取名为“模二除法”。

    所谓模二除法实际形式上和我们的平常使用的除法一样的(用于二进制运算),但是唯一不一同的是关于计算当中一切的加减法统统换成“异或”(XOR),一句话概括异或运算就是:异性相吸(返回真1),同性相斥(返回假0):1 Xor 0 = 1,0 Xor 1 = 1, 1 Xor 1 = 0, 0 Xor 0 = 0。

    那么我们用上面列子来试一下模二除法(模二除法的结果不等于普通除法)

    图片描述

    王大麻子表示:我去!算完之后我还要核对余数?!不能再简单点吗?

    于是乎小明同学又开始没日没夜苦想,最终当最后的狼牙山“三壮士”也离他而去时,他头顶一凉想到一个绝佳主意:在信件数据的末尾(即数据低位LSB)补上我和王大麻子都知道的数字的长度-1的0(生成项长度-1)然后在被同知数字相除,得到的余数再附加原始数据的末尾上。(这里说的原始数据是指没有补零的,且余数长度一定与补零的长度一致)

    口说无凭,我们来重新用这个升级计算方法试一试。

    图片描述

    我们将余数10补在原始数据1010111的末尾得到了一个新数:101011110,然后我们再用110去除,神奇的事情发生了:没有余数了。(接受端只要将已修改的数据与生成项模二相除没有余数即代表数据无误)

    这便是CRC(循环冗余校验,Cyclic Redundancy Check)是一种为了检测数据是否损坏处理办法。而当中的模二除法是无借位(不向高位借位的)的性质十分重要:意味我们计算CRC只需要简单的数据位移和Xor即可(到后面你就知道了)。

    当然理论上讲CRC还是出错的可能(不过已经比程序猿能找到女朋友的几率要低了),所以选择一个好的除数就是一个非常重要的事情,关于CRC的除数有个专业的名称:生成多项式,简称生成项。如何选择生成项这是需要一定的代数编码知识(已经不是我这种咸鱼能搞懂的问题了)。好在我们可以直接用大佬计算好的生成项,不同的生成项有不同的CRC,如:CRC8、CRC16、CRC-CCITT、CRC32……。

    从数学的角度来理解CRC(如果您只是了解如何计算CRC的话可以直接跳过本节)

    我们不妨尝试将二进制转化一种多项式:数字中多少位1代表的是x的多少次方,0乘以任何数都是0所以不用管。

    比如101010(42),可以转化为:x^5+x^3+x。(注意最低位0次方,任何数零次方都等于1)

    假设用x^3+x^2+x除去x+1,可以得到如下式子:(这一段基本上完全搬运的循環冗餘校驗Wiki,写的真的好!)

    图片描述

    很好我们在两边再乘一个x+1:

    图片描述

    这里不难看出:得到一个商×除数+余数的式子,其中的(x^2+1)就是商,-1就是余数(我也不没懂为啥余数是负数)。我们还可以对左边式子再提取一次x,可得:

    图片描述

    我们可以理解这里提取的x是对于x^2+x+1(1011)进行补一次零变成了10110,实际上这个补零还有个说法叫做左移(要注意数据的方向高位在左边)。

    如何理解补零的性质这个很简单,我们类比十进制的补零如:1要补两次零变成100,很明显补零就是乘与10的几次方。回到二进制中就是2的几次方,而多项式中的x就可以代表2。

    通过以上的式子的整理可以得出通用公式即是:

    图片描述

    M(x)就代表的是原始数据,x^n代表的是数据末补n个0,K(x)代表的是Key也就是生成项,R(x)代表的余数也是上一节提到FCS。接收者接受到M(x)*x^n+R(x)看看是能被K(x)整除不,可以即为正确数据。

    要注意的一点x^n的长度(补零长度)受限于R(x)(目的是可以直接追加在末尾,而不影响原始数据):他们长度一致,且一定比K(x)的长度少1。

    关于R(x)为什么一定比K(x)的长度少1?我个人愚见是特殊的模二除法:K(x)的最高位一定1(不然没有意义啊),而数据处理过程中需要计算数据的最高位也是1(可以对照着除法的当中与除数对应的那个被除数的那部分数据),他们进行Xor就变成0,实际计算往往是剩下的部分(K(x)长度-1)(在程序设计中反正都会变成0干脆都不计算首位,这就是为啥网上的CRC生成多项式的简记码都是默认舍弃首位1的原因)。

    CRC的原理实际上远比这些要复杂的多,涉及到群论这类我们这些吃瓜群众可望不可即的数理知识。以上也只是我对Wiki的搬运和理解瞎猜,希望大家能通过这个简单列子大概了解CRC的性质,如有不对之处有望大佬不惜赐教!

    直接计算法


    虽说上一节我们已经知道CRC是怎么计算的,但明显电脑可不会写除法公式(程序很难直接用这种方法)。且不说要对齐一个超长二进制数据进行逐位计算的困难不说,单单是像vbscript这种既没有几个位操作符又用起来蛋疼的语言基本上是很难实现(大佬:喵喵喵?)。不过可以转化一个思路:比如每次只取一部分数据来计算如何?

    仔细观察计算的过程,可以发现其实每一次Xor都是固定不动的生成项与其对应的数据首位“消1”。那我们就可以假想出一个与生成项长度一致的“盒子”,取出一部分的数据出来若首位是1时就进行一次Xor,遇到0则左移到1为止,左移造成的右端的空缺用0补充。而这里0希望理解为一种“存储”,它“存储” 生成项中未和数据进行计算的那一部分,按顺序先后附加被计算数据的后面,当先一部分的数据全部计算之后,实际上“盒子”中剩下都是未和数据计算的部分的“和”11011 xor 10110 = 11011 xor ( 10000 xor 00100 xor 00010)(这里实际上就是Xor的交换律到后面就会体会到他的强大)

    图片描述

    通过以上的结论我们可以假装设计出一个算法(这里我用的是VBScript):

    
      
    1. Const PLAY = &H1021&       '这里生成项(实际上就是CRC-CCITT),注意这里默认首位1是去掉的
    2. Const TEXT =  "123456789"   '这里就是原始数据
    3. Dim L,I,CRC
    4. DoWhile L <  Len(TEXT)
    5. '通过循环取得原始数据的每一个字符来计算
    6.     L = L +  1
    7.     CRC = CRC  Xor ( Asc( Mid(TEXT,L, 1)) * &H100&)
    8.      '实际上文中提到的“盒子”专业的说法应该叫做:寄存器。
    9.      '这里取出新的字符出来与CRC寄存器里上一次未和数据进行计算的多项式的部分进行Xor,作为新数据进行下一步处理。
    10.      '机智的你也许发现了:1021这个生成式是16位与一个字节8位不符怎么办?别忘我们还有神器——补零!乘上H100 = 256 = 2 ^ 8
    11.      For I =  0To7
    12.          '判断数据最高位是否为 1
    13.          '1 - 左移一位(去掉数据首位1),剩下的部分进行Xor
    14.          '0 - 就左移一位(去掉多余的0)
    15.          If (CRC  And &H8000&)  Then
    16.             CRC = (CRC *  2)  And &HFFFF&  '// 左移
    17.             CRC = CRC  Xor PLAY
    18.          Else
    19.             CRC = (CRC *  2)  And &HFFFF&  '// 左移
    20.          EndIf
    21.      Next
    22.     CRC = CRC  And &HFFFF&
    23.      '限制寄存器内数据大小为16位。
    24. Loop
    25. WScript.Echo  Hex(CRC)

    运行之后成功就可以得出CRC-CCITT (XModem)的标准验证值:31C3(在线计算网站:On-line CRC calculation and free library

    驱动表法


    实际上CRC就像开心消消乐一样,就是不断消除首位数据。这时你想:要是能一口气消除一个字节(8bit)以上的数据那该多好!

    一般来讲文艺青年会这么做(CRC的正常计算):

    图片描述

    但是2B青年会这么想:可不可以将生成项先Xor了?

    图片描述

    我们可以先提前计算出与数据前几位相符的生成项之和再Xor从而到达一口气消掉了多位数据的目的,Xor的乘法交换律允许我们提前计算出需要的数据A Xor B Xor C = A Xor ( B Xor C )

    既然如此干脆直接将前八位0000 0000 ~ 1111 1111(0 ~ 255,一个字节)这个范围所有的生产项的和全部计算存储成表格,等计算的时候直接取出数据的首字节出来作为索引找到对应表格的中生存项的和与去掉首位字节的数据进行Xor不就可以了吗。

    表的由来

    虽说想法很美好,但是如何实现前8位从0~255所有的生成项之和了?我们来思考一下CRC计算的本质是什么?复读没错是不断地消除首位数据,那么在Xor运算下消除方法就是:数据一样!

    那么我们将0~255这256个数字进行CRC逐位计算后剩下不就是已经消除掉前8位数据的生成项之和吗!(因为前8位数据一样所以被消除了)

    用通俗点语言就是:我们提前将一个字节的CRC验证码计算出来。(实际上这一段语文老师死得早的我构思很久,担心没有上面这段过渡部分会造成读者理解困难,希望大家能Get我的点……Orz)

    以下就是关于CRC16的正序表格计算代码:

    
      
    1. Const PLAY = &H8005&      '这里生成项(CRC16),注意这里默认首位1是去掉的
    2. ReDim Table( 255)          '这里存储表格
    3. '// 计算表格部分
    4. Dim I,J,Temp
    5. '对于0~255这256个数字进行CRC计算,并将计算好的CRC验证码按顺序存储在表格(数组)中
    6. For I =  0To255
    7.     Temp = (I * &H100&)  And &HFFFF&
    8.      For J =  0To7
    9.          If (Temp  And &H8000)  Then
    10.             Temp = (Temp *  2)  And &HFFFF&
    11.             Temp = Temp  Xor PLAY
    12.          Else
    13.             Temp = (Temp *  2)  And &HFFFF&
    14.          EndIf
    15.      Next
    16.     Table(I) = Temp  And &HFFFF&
    17. Next
    18. '// 输出CRC16表格代码(使用VbsEdit的调试)
    19. Dim y,x,u
    20. Debug.WriteLine  "Dim CRC16_Table:CRC16_Table = Array( _"
    21. For y =  1To64
    22.      For x =  1To4
    23.         Debug.Write  "&H", String( 4 -  Len( Hex(Table(u))), "0"), Hex(Table(u)), "&"
    24.          If u <>  255Then Debug.Write  ", "Else Debug.Write  " "
    25.         u = u +  1
    26.      Next
    27.     Debug.WriteLine  "_"
    28. Next
    29. Debug.WriteLine  ")"

    代码无误的话,应该会在调试框中得到如下代码(作为验证可以看看):

    
      
    1. Dim CRC16_Table:CRC16_Table =  Array( _
    2. &H0000&, &H8005&, &H800F&, &H000A&, _
    3. &H801B&, &H001E&, &H0014&, &H8011&, _
    4. &H8033&, &H0036&, &H003C&, &H8039&, _
    5. &H0028&, &H802D&, &H8027&, &H0022&, _
    6. &H8063&, &H0066&, &H006C&, &H8069&, _
    7. &H0078&, &H807D&, &H8077&, &H0072&, _
    8. &H0050&, &H8055&, &H805F&, &H005A&, _
    9. &H804B&, &H004E&, &H0044&, &H8041&, _
    10. &H80C3&, &H00C6&, &H00CC&, &H80C9&, _
    11. &H00D8&, &H80DD&, &H80D7&, &H00D2&, _
    12. &H00F0&, &H80F5&, &H80FF&, &H00FA&, _
    13. &H80EB&, &H00EE&, &H00E4&, &H80E1&, _
    14. &H00A0&, &H80A5&, &H80AF&, &H00AA&, _
    15. &H80BB&, &H00BE&, &H00B4&, &H80B1&, _
    16. &H8093&, &H0096&, &H009C&, &H8099&, _
    17. &H0088&, &H808D&, &H8087&, &H0082&, _
    18. &H8183&, &H0186&, &H018C&, &H8189&, _
    19. &H0198&, &H819D&, &H8197&, &H0192&, _
    20. &H01B0&, &H81B5&, &H81BF&, &H01BA&, _
    21. &H81AB&, &H01AE&, &H01A4&, &H81A1&, _
    22. &H01E0&, &H81E5&, &H81EF&, &H01EA&, _
    23. &H81FB&, &H01FE&, &H01F4&, &H81F1&, _
    24. &H81D3&, &H01D6&, &H01DC&, &H81D9&, _
    25. &H01C8&, &H81CD&, &H81C7&, &H01C2&, _
    26. &H0140&, &H8145&, &H814F&, &H014A&, _
    27. &H815B&, &H015E&, &H0154&, &H8151&, _
    28. &H8173&, &H0176&, &H017C&, &H8179&, _
    29. &H0168&, &H816D&, &H8167&, &H0162&, _
    30. &H8123&, &H0126&, &H012C&, &H8129&, _
    31. &H0138&, &H813D&, &H8137&, &H0132&, _
    32. &H0110&, &H8115&, &H811F&, &H011A&, _
    33. &H810B&, &H010E&, &H0104&, &H8101&, _
    34. &H8303&, &H0306&, &H030C&, &H8309&, _
    35. &H0318&, &H831D&, &H8317&, &H0312&, _
    36. &H0330&, &H8335&, &H833F&, &H033A&, _
    37. &H832B&, &H032E&, &H0324&, &H8321&, _
    38. &H0360&, &H8365&, &H836F&, &H036A&, _
    39. &H837B&, &H037E&, &H0374&, &H8371&, _
    40. &H8353&, &H0356&, &H035C&, &H8359&, _
    41. &H0348&, &H834D&, &H8347&, &H0342&, _
    42. &H03C0&, &H83C5&, &H83CF&, &H03CA&, _
    43. &H83DB&, &H03DE&, &H03D4&, &H83D1&, _
    44. &H83F3&, &H03F6&, &H03FC&, &H83F9&, _
    45. &H03E8&, &H83ED&, &H83E7&, &H03E2&, _
    46. &H83A3&, &H03A6&, &H03AC&, &H83A9&, _
    47. &H03B8&, &H83BD&, &H83B7&, &H03B2&, _
    48. &H0390&, &H8395&, &H839F&, &H039A&, _
    49. &H838B&, &H038E&, &H0384&, &H8381&, _
    50. &H0280&, &H8285&, &H828F&, &H028A&, _
    51. &H829B&, &H029E&, &H0294&, &H8291&, _
    52. &H82B3&, &H02B6&, &H02BC&, &H82B9&, _
    53. &H02A8&, &H82AD&, &H82A7&, &H02A2&, _
    54. &H82E3&, &H02E6&, &H02EC&, &H82E9&, _
    55. &H02F8&, &H82FD&, &H82F7&, &H02F2&, _
    56. &H02D0&, &H82D5&, &H82DF&, &H02DA&, _
    57. &H82CB&, &H02CE&, &H02C4&, &H82C1&, _
    58. &H8243&, &H0246&, &H024C&, &H8249&, _
    59. &H0258&, &H825D&, &H8257&, &H0252&, _
    60. &H0270&, &H8275&, &H827F&, &H027A&, _
    61. &H826B&, &H026E&, &H0264&, &H8261&, _
    62. &H0220&, &H8225&, &H822F&, &H022A&, _
    63. &H823B&, &H023E&, &H0234&, &H8231&, _
    64. &H8213&, &H0216&, &H021C&, &H8219&, _
    65. &H0208&, &H820D&, &H8207&, &H0202& _
    66. )

    我们可以以空间换取时间,直接将CRC表格计算好作为一个常数数组使用。

    得到表格之后回到驱动表法的计算:取出CRC寄存器中的首位字节,然后将CRC左移去掉首字节然后取出一字节新数据装入CRC低端空出字节中,根据取出首字节找到对应表格中的生成项之和与CRC寄存器进行Xor,然后重复这个步骤直到数据全部取完计算完。要注意的是:因为驱动表法是一个一个字节计算,所以他必须计算之前在原始数据上补零(不能像直接计算法那样通过逐位左移方式自己完成补零)。我们来看一下代码是如何实现的:

    
      
    1. Dim CRC16_Table                      '这里表格我们直接就套用上一节我们计算好的数据
    2. Const TEXT =  "123456789"             '这里就是原始数据
    3. '这里要注意驱动表法没有逐位补零,所以我们要手动在数据末尾增加两个字节的零
    4. Dim str:str = TEXT &  String( 2, Chr( 0))
    5. Dim L,I,T,CRC
    6. '初始化CRC寄存器值为0
    7. CRC =  0
    8. DoWhile L <  Len(str)
    9.     L = L +  1
    10.      '取出CRC寄存器中的首字节
    11.     T = (CRC  And &HFF00&) / &H100
    12.      '左移数据一个字节(就是去掉寄存器中的首字节),并在空出的字节放入新的数据,限制寄存器大小为两个字节。
    13.     CRC = ((CRC * &H100&)  OrAsc( Mid(str,L, 1)))  And &HFFFF&
    14.      '将已经去掉首字节的CRC寄存器与对应的表格生成项之和进行Xor
    15.     CRC = CRC  Xor CRC16_Table(T)
    16.      '当然也可以直接将上面三句缩写成一句:
    17.      'CRC = (((CRC * 256) Or Asc(Mid(str,L,1))) And &HFFFF&) Xor Table16((CRC And &HFF00&) / &H100)
    18. Loop
    19. '限制CRC大小为两个字节
    20. CRC = CRC  And &HFFFF&
    21. WScript.Echo  Hex(CRC)

    输出结果为:FEE8(注意这个值并不是标准的CRC16验证码,后面我们还会讲到如何修改它。)

    直驱动法


    这个部分的思路完全来自poiu_elab大佬的【脑冻结】CRC我就拿下了,感谢大佬的分享!

    我们不妨用大佬的列子看看(丑不要脸的偷懒):

    图片描述

    我们针对31 32 33 34进行CRC-CCITT驱动表法的计算,着重观察每次查询表格的索引(也就是黄色部分),你会发现实际上索引就是原始数据与寄存器前2位数据Xor计算的结果。

    比如第一次查询时,寄存器为0与原始数据31 Xor得到查表的索引31,查得26 72并存入寄存器内;遇到第二个原始数据32与寄存器内的26进行Xor得到14,查得52 B5由于寄存器左移一个字节于是上一次72移到高位与52进行Xor得到20,于是现在寄存器内就是20(72 Xor 52) B5;遇到第三个原始数据33与寄存器内20(72 xor 52)进行Xor,得到13……重复这个过程直到查到最后一个原始数据为止。

    通过上面的步骤我们可以整理出直驱动表法的算法:

    伪语言版:

    循环:取得字符
    寄存器 = 去掉首位字节的寄存器 Xor表格[寄存器的首字节 Xor 取出的原始数据]

    C语言版 CRC32直驱表法:

    While(len--)
    r=(r<<8)^t[(r>>24)^*p++];

    我个人的总结直驱动表法实际上就是将驱动表法再一次简化,将数据输入和表格查询有机的结合在一起,这么做好处可以不用在原始数据上补零,方便持续计算CRC(不停的加入新的数据)。

    由于vbscript对于32位数据进行四则运算(乘法补零)会溢出,所以不妨为我们尝试一下寄存器分段处理(就是将寄存器分成两个部分处理来解决数据溢出的问题),代码如下:

    
      
    1. Dim Table_M( 255)          '表格的高位
    2. Dim Table_L( 255)          '表格的低位
    3. '// CRC32正序表格计算
    4. Const PLOY_M = &H04C1&    '生成项高位,CRC32生成项:04C11DB7
    5. Const PLOY_L = &H1DB7&    '生成项低位
    6. Dim I,J,CRC_M,CRC_L
    7. For I =  0To255
    8.     CRC_M = (I * &H100&)  And &HFFFF&
    9.     CRC_L =  0
    10.      For J =  0To7
    11.          If (CRC_M  And &H8000)  Then
    12.              '// 左移
    13.             CRC_M = (CRC_M  And &H7FFF) * &H2
    14.             CRC_M = CRC_M  Xor ((CRC_L  And &H8000&) / &H8000&)  '低位寄存器中高位会移动到高位寄存器中的低位
    15.             CRC_L = (CRC_L  And &H7FFF) * &H2
    16.              '// Xor计算
    17.             CRC_M = CRC_M  Xor PLOY_M
    18.             CRC_L = CRC_L  Xor PLOY_L
    19.          Else
    20.              '// 左移
    21.             CRC_M = (CRC_M  And &H7FFF) * &H2
    22.             CRC_M = CRC_M  Xor ((CRC_L  And &H8000&) / &H8000&)
    23.             CRC_L = (CRC_L  And &H7FFF) * &H2
    24.          EndIf
    25.         Table_M(I) = CRC_M
    26.         Table_L(I) = CRC_L
    27.      Next
    28. Next
    29. '// CRC32计算部分
    30. Const TEXT =  "123456789"   '原始数据
    31. CRC_M =  0
    32. CRC_L =  0
    33. Dim T
    34. DoWhile L <  Len(TEXT)
    35.     L = L +  1
    36.      '计算出查询表格的索引
    37.     T = ((CRC_M  And &HFF00&) / &H100&)  XorAsc( Mid(TEXT,L, 1))
    38.      '分别计算出高位、低位寄存器,要注意的是低位寄存器中高位会移动到高位寄存器中的低位。
    39.     CRC_M = ((CRC_M  And &HFF&) * &H100)  Xor ((CRC_L  And &HFF00&) / &H100&)  Xor Table_M(T)
    40.     CRC_L = ((CRC_L  And &HFF&) * &H100)  Xor Table_L(T)
    41. Loop
    42. '记得输出不足CRC寄存器长度的数据时在前面补零
    43. Debug.WriteLine  String( 4 -  Len( Hex(CRC_M)), "0"), Hex(CRC_M), String( 4 -  Len( Hex(CRC_L)), "0"), Hex(CRC_L)

    输出结果为:89A1897F

    CRC参数模型


    细心的朋友可能发现我们上一节计算出的CRC32验证值是不对的,为了方便机器更好的计算CRC所以制定一些规则,称为CRC参数模型。我们一睹CRC32模型的芳容:

    图片描述

    Width:代表生成项长度
    Poly:生成项
    Init:寄存器计算前的初始值,其实初始值是为了保存数据之前零(CRC计算特性是省略开头的零)
    RefIn:输入原始数据进行二进制数据反转,因为数据输入是一个字节一个字节,所以反转也是一个字节,如图所示:
    图片描述
    RefOut:最后输出的CRC数据进行数据反转,注意是整个CRC数据进行反转(其实就是对CRC寄存器进行反转)
    XorOut:对已经RefOut的CRC数据进行Xor处理,方式和Init一样。
    Check:是对字符串“123456789”CRC计算的验证值,作为参考看看自己的程序计算是否有误。

    根据这个模型,我们对上一节的CRC32算法再次魔改:

    
      
    1. Dim Table_M:Table_M =  Array( _ ' CRC32表格高位,由于篇幅有限请自行补齐代码
    2. Dim Table_L:Table_L =  Array( _ ' CRC32表格低位,由于篇幅有限请自行补齐代码
    3. '颠倒二进制函数
    4. PublicFunction RevBin( ByVal Value, ByVal lLen)
    5.     RevBin =  0
    6.      If IsNumeric(Value)  And Value  Then
    7.         lLen = lLen -  1
    8.          Dim I,REG
    9.          For I =  0To lLen
    10.              If (( 2^I)  And Value)  Then REG = REG  Or2^(lLen - I)
    11.          Next
    12.         RevBin = REG
    13.      EndIf
    14. EndFunction
    15. '原始数据
    16. Const TEXT =  "123456789"
    17. 'Init:初始化寄存器
    18. CRC_M = &HFFFF&
    19. CRC_L = &HFFFF&
    20. '计算CRC部分
    21. Dim T
    22. DoWhile L <  Len(TEXT)
    23.     L = L +  1
    24.      'RefIn:注意这里的对一个字节(8bit)的反转(我曾经在这里被坑过)
    25.     T = ((CRC_M  And &HFF00&) / &H100)  Xor RevBin( Asc( Mid(TEXT,L, 1)), 8)
    26.     CRC_M = ((CRC_M  And &HFF) * &H100)  Xor ((CRC_L  And &HFF00&) / &H100)  Xor Table_M(T)
    27.     CRC_L = ((CRC_L  And &HFF) * &H100)  Xor Table_L(T)
    28. Loop
    29. 'RefOut:反转计算出来的CRC值
    30. Dim Temp
    31. Temp = RevBin(CRC_L, 16)
    32. CRC_L = RevBin(CRC_M, 16)
    33. CRC_M = Temp
    34. 'XorOut:最后一次Xor
    35. CRC_M = CRC_M  Xor &HFFFF&
    36. CRC_L = CRC_L  Xor &HFFFF&
    37. '输出CRC验证值
    38. Debug.WriteLine  String( 4 -  Len( Hex(CRC_M)), "0"), Hex(CRC_M), String( 4 -  Len( Hex(CRC_L)), "0"), Hex(CRC_L)

    终于得到正确的CRC32验证码:CBF43926

    进一步的优化:镜像CRC直驱表法算法


    虽然可以计算出CRC32,但是每次都要颠倒输入、输出的值这显十分浪费性能。我们可以不可以将这个算法直接镜像,从而避免对其输入、输出的逆转,只需要对表格进行逆转和相反的数据位移方向即可。

    图片描述

    那么新的问题已经出现,我们怎能停滞不前:这逆转的表格咋算啊?!

    答案就是:要用魔法(逆转)去打败魔法(逆转):将生成项:04C11DB7逆转为EDB88320,新数据插入的方向为数据低位(新数据不需要逆转只需要通过它的值计算出对应的生成项之和),数据位移方向向右(这个就是逆转的核心)。我们可以达到以下代码:

    
      
    1. Dim Table_M( 255)          '表格的高位
    2. Dim Table_L( 255)          '表格的低位
    3. '// CRC32逆序表格计算,CRC32生成项:EDB88320
    4. Const PLOY_M = &HEDB8&    '生成项高位
    5. Const PLOY_L = &H8320&    '生成项低位
    6. Dim I,J,CRC_M,CRC_L
    7. For I =  0To255
    8.     CRC_M =  0
    9.     CRC_L = I
    10.      For J =  0To7
    11.          If (CRC_L  And &H1)  Then
    12.              '// 右移
    13.             CRC_L = (CRC_L  And &HFFFE&) / &H2
    14.             CRC_L = CRC_L  Xor ((CRC_M  And &H1) * &H8000&)  '高位寄存器中低位会移动到低位寄存器中的高位
    15.             CRC_M = (CRC_M  And &HFFFE&) / &H2
    16.              '// Xor计算
    17.             CRC_M = CRC_M  Xor PLOY_M
    18.             CRC_L = CRC_L  Xor PLOY_L
    19.          Else
    20.              '// 右移
    21.             CRC_L = (CRC_L  And &HFFFE&) / &H2
    22.             CRC_L = CRC_L  Xor ((CRC_M  And &H1) * &H8000&) 
    23.             CRC_M = (CRC_M  And &HFFFE&) / &H2
    24.          EndIf
    25.      Next
    26.     Table_M(I) = CRC_M
    27.     Table_L(I) = CRC_L
    28. Next
    29. '//输出逆序表格代码
    30. PublicSub Print( ByVal Name, ByVal lTable)
    31.      Dim y,x,u
    32.     Debug.WriteLine Name &  " = Array( _"
    33.      For y =  1To32
    34.          For x =  1To8
    35.             Debug.Write  "&H", String( 4 -  Len( Hex(lTable(u))), "0"), Hex(lTable(u)), "&"
    36.              If u <>  255Then Debug.Write  ", "Else Debug.Write  " "
    37.             u = u +  1
    38.          Next
    39.         Debug.WriteLine  "_"
    40.      Next
    41.     Debug.WriteLine  ")"
    42. EndSub
    43. Call Print( "CRC32Table_MSB",Table_M)
    44. Call Print( "CRC32Table_LSB",Table_L)

    计算出表格代码根据上图的镜像算法,我们可以将新数据xor到寄存器最低位取得表格索引,然后两个寄存器左移一个字节计算索引对应的逆转的生成项之和。封装一下代码就是这样的:

    
      
    1. Class C_CRC
    2.      '初始化类载入数据
    3.      Private m_CRC32Table_MSB
    4.      Private m_CRC32Table_LSB
    5.      PrivateSubClass_Initialize()
    6.         m_CRC32Table_MSB =  Array( _
    7.         &H0000&, &H7707&, &HEE0E&, &H9909&, &H076D&, &H706A&, &HE963&, &H9E64&, _
    8.         &H0EDB&, &H79DC&, &HE0D5&, &H97D2&, &H09B6&, &H7EB1&, &HE7B8&, &H90BF&, _
    9.         &H1DB7&, &H6AB0&, &HF3B9&, &H84BE&, &H1ADA&, &H6DDD&, &HF4D4&, &H83D3&, _
    10.         &H136C&, &H646B&, &HFD62&, &H8A65&, &H1401&, &H6306&, &HFA0F&, &H8D08&, _
    11.         &H3B6E&, &H4C69&, &HD560&, &HA267&, &H3C03&, &H4B04&, &HD20D&, &HA50A&, _
    12.         &H35B5&, &H42B2&, &HDBBB&, &HACBC&, &H32D8&, &H45DF&, &HDCD6&, &HABD1&, _
    13.         &H26D9&, &H51DE&, &HC8D7&, &HBFD0&, &H21B4&, &H56B3&, &HCFBA&, &HB8BD&, _
    14.         &H2802&, &H5F05&, &HC60C&, &HB10B&, &H2F6F&, &H5868&, &HC161&, &HB666&, _
    15.         &H76DC&, &H01DB&, &H98D2&, &HEFD5&, &H71B1&, &H06B6&, &H9FBF&, &HE8B8&, _
    16.         &H7807&, &H0F00&, &H9609&, &HE10E&, &H7F6A&, &H086D&, &H9164&, &HE663&, _
    17.         &H6B6B&, &H1C6C&, &H8565&, &HF262&, &H6C06&, &H1B01&, &H8208&, &HF50F&, _
    18.         &H65B0&, &H12B7&, &H8BBE&, &HFCB9&, &H62DD&, &H15DA&, &H8CD3&, &HFBD4&, _
    19.         &H4DB2&, &H3AB5&, &HA3BC&, &HD4BB&, &H4ADF&, &H3DD8&, &HA4D1&, &HD3D6&, _
    20.         &H4369&, &H346E&, &HAD67&, &HDA60&, &H4404&, &H3303&, &HAA0A&, &HDD0D&, _
    21.         &H5005&, &H2702&, &HBE0B&, &HC90C&, &H5768&, &H206F&, &HB966&, &HCE61&, _
    22.         &H5EDE&, &H29D9&, &HB0D0&, &HC7D7&, &H59B3&, &H2EB4&, &HB7BD&, &HC0BA&, _
    23.         &HEDB8&, &H9ABF&, &H03B6&, &H74B1&, &HEAD5&, &H9DD2&, &H04DB&, &H73DC&, _
    24.         &HE363&, &H9464&, &H0D6D&, &H7A6A&, &HE40E&, &H9309&, &H0A00&, &H7D07&, _
    25.         &HF00F&, &H8708&, &H1E01&, &H6906&, &HF762&, &H8065&, &H196C&, &H6E6B&, _
    26.         &HFED4&, &H89D3&, &H10DA&, &H67DD&, &HF9B9&, &H8EBE&, &H17B7&, &H60B0&, _
    27.         &HD6D6&, &HA1D1&, &H38D8&, &H4FDF&, &HD1BB&, &HA6BC&, &H3FB5&, &H48B2&, _
    28.         &HD80D&, &HAF0A&, &H3603&, &H4104&, &HDF60&, &HA867&, &H316E&, &H4669&, _
    29.         &HCB61&, &HBC66&, &H256F&, &H5268&, &HCC0C&, &HBB0B&, &H2202&, &H5505&, _
    30.         &HC5BA&, &HB2BD&, &H2BB4&, &H5CB3&, &HC2D7&, &HB5D0&, &H2CD9&, &H5BDE&, _
    31.         &H9B64&, &HEC63&, &H756A&, &H026D&, &H9C09&, &HEB0E&, &H7207&, &H0500&, _
    32.         &H95BF&, &HE2B8&, &H7BB1&, &H0CB6&, &H92D2&, &HE5D5&, &H7CDC&, &H0BDB&, _
    33.         &H86D3&, &HF1D4&, &H68DD&, &H1FDA&, &H81BE&, &HF6B9&, &H6FB0&, &H18B7&, _
    34.         &H8808&, &HFF0F&, &H6606&, &H1101&, &H8F65&, &HF862&, &H616B&, &H166C&, _
    35.         &HA00A&, &HD70D&, &H4E04&, &H3903&, &HA767&, &HD060&, &H4969&, &H3E6E&, _
    36.         &HAED1&, &HD9D6&, &H40DF&, &H37D8&, &HA9BC&, &HDEBB&, &H47B2&, &H30B5&, _
    37.         &HBDBD&, &HCABA&, &H53B3&, &H24B4&, &HBAD0&, &HCDD7&, &H54DE&, &H23D9&, _
    38.         &HB366&, &HC461&, &H5D68&, &H2A6F&, &HB40B&, &HC30C&, &H5A05&, &H2D02& )
    39.         m_CRC32Table_LSB =  Array( _
    40.         &H0000&, &H3096&, &H612C&, &H51BA&, &HC419&, &HF48F&, &HA535&, &H95A3&, _
    41.         &H8832&, &HB8A4&, &HE91E&, &HD988&, &H4C2B&, &H7CBD&, &H2D07&, &H1D91&, _
    42.         &H1064&, &H20F2&, &H7148&, &H41DE&, &HD47D&, &HE4EB&, &HB551&, &H85C7&, _
    43.         &H9856&, &HA8C0&, &HF97A&, &HC9EC&, &H5C4F&, &H6CD9&, &H3D63&, &H0DF5&, _
    44.         &H20C8&, &H105E&, &H41E4&, &H7172&, &HE4D1&, &HD447&, &H85FD&, &HB56B&, _
    45.         &HA8FA&, &H986C&, &HC9D6&, &HF940&, &H6CE3&, &H5C75&, &H0DCF&, &H3D59&, _
    46.         &H30AC&, &H003A&, &H5180&, &H6116&, &HF4B5&, &HC423&, &H9599&, &HA50F&, _
    47.         &HB89E&, &H8808&, &HD9B2&, &HE924&, &H7C87&, &H4C11&, &H1DAB&, &H2D3D&, _
    48.         &H4190&, &H7106&, &H20BC&, &H102A&, &H8589&, &HB51F&, &HE4A5&, &HD433&, _
    49.         &HC9A2&, &HF934&, &HA88E&, &H9818&, &H0DBB&, &H3D2D&, &H6C97&, &H5C01&, _
    50.         &H51F4&, &H6162&, &H30D8&, &H004E&, &H95ED&, &HA57B&, &HF4C1&, &HC457&, _
    51.         &HD9C6&, &HE950&, &HB8EA&, &H887C&, &H1DDF&, &H2D49&, &H7CF3&, &H4C65&, _
    52.         &H6158&, &H51CE&, &H0074&, &H30E2&, &HA541&, &H95D7&, &HC46D&, &HF4FB&, _
    53.         &HE96A&, &HD9FC&, &H8846&, &HB8D0&, &H2D73&, &H1DE5&, &H4C5F&, &H7CC9&, _
    54.         &H713C&, &H41AA&, &H1010&, &H2086&, &HB525&, &H85B3&, &HD409&, &HE49F&, _
    55.         &HF90E&, &HC998&, &H9822&, &HA8B4&, &H3D17&, &H0D81&, &H5C3B&, &H6CAD&, _
    56.         &H8320&, &HB3B6&, &HE20C&, &HD29A&, &H4739&, &H77AF&, &H2615&, &H1683&, _
    57.         &H0B12&, &H3B84&, &H6A3E&, &H5AA8&, &HCF0B&, &HFF9D&, &HAE27&, &H9EB1&, _
    58.         &H9344&, &HA3D2&, &HF268&, &HC2FE&, &H575D&, &H67CB&, &H3671&, &H06E7&, _
    59.         &H1B76&, &H2BE0&, &H7A5A&, &H4ACC&, &HDF6F&, &HEFF9&, &HBE43&, &H8ED5&, _
    60.         &HA3E8&, &H937E&, &HC2C4&, &HF252&, &H67F1&, &H5767&, &H06DD&, &H364B&, _
    61.         &H2BDA&, &H1B4C&, &H4AF6&, &H7A60&, &HEFC3&, &HDF55&, &H8EEF&, &HBE79&, _
    62.         &HB38C&, &H831A&, &HD2A0&, &HE236&, &H7795&, &H4703&, &H16B9&, &H262F&, _
    63.         &H3BBE&, &H0B28&, &H5A92&, &H6A04&, &HFFA7&, &HCF31&, &H9E8B&, &HAE1D&, _
    64.         &HC2B0&, &HF226&, &HA39C&, &H930A&, &H06A9&, &H363F&, &H6785&, &H5713&, _
    65.         &H4A82&, &H7A14&, &H2BAE&, &H1B38&, &H8E9B&, &HBE0D&, &HEFB7&, &HDF21&, _
    66.         &HD2D4&, &HE242&, &HB3F8&, &H836E&, &H16CD&, &H265B&, &H77E1&, &H4777&, _
    67.         &H5AE6&, &H6A70&, &H3BCA&, &H0B5C&, &H9EFF&, &HAE69&, &HFFD3&, &HCF45&, _
    68.         &HE278&, &HD2EE&, &H8354&, &HB3C2&, &H2661&, &H16F7&, &H474D&, &H77DB&, _
    69.         &H6A4A&, &H5ADC&, &H0B66&, &H3BF0&, &HAE53&, &H9EC5&, &HCF7F&, &HFFE9&, _
    70.         &HF21C&, &HC28A&, &H9330&, &HA3A6&, &H3605&, &H0693&, &H5729&, &H67BF&, _
    71.         &H7A2E&, &H4AB8&, &H1B02&, &H2B94&, &HBE37&, &H8EA1&, &HDF1B&, &HEF8D& )
    72.      EndSub
    73.     
    74.      '// 计算CRC部分
    75.      PublicFunction CRC32( ByVal Value)
    76.          Dim CRC_MSB,CRC_LSB
    77.         CRC_MSB = &HFFFF&
    78.         CRC_LSB = &HFFFF&
    79.         
    80.          Dim StrLen:StrLen =  Len(Value)
    81.          Dim FirstByte,L
    82.          DoWhile L < StrLen
    83.             L = L +  1
    84.             FirstByte = (CRC_LSB  And &HFF&)  XorAsc( Mid(Value,L, 1))
    85.             CRC_LSB = ((CRC_LSB  And &HFF00&) / &H100)  Xor ((CRC_MSB  And &HFF&) * &H100&)  Xor m_CRC32Table_LSB(FirstByte)
    86.             CRC_MSB = ((CRC_MSB  And &HFF00&) / &H100)  Xor m_CRC32Table_MSB(FirstByte)
    87.          Loop
    88.         
    89.         CRC_MSB = CRC_MSB  Xor &HFFFF&
    90.         CRC_LSB = CRC_LSB  Xor &HFFFF&
    91.         
    92.         CRC32 =  String( 4 -  Len( Hex(CRC_MSB)), "0") &  Hex(CRC_MSB) &  String( 4 -  Len( Hex(CRC_LSB)), "0") &  Hex(CRC_LSB)
    93.      EndFunction
    94. EndClass
    95. Dim CRC: Set CRC =  New C_CRC
    96. WScript.Echo CRC.CRC32( "123456789")

    到这里教程就完全结束了,当然我这个代码完全没有效率,纯粹写出演示闹着玩(笑)。如果是想用vbs进行CRC计算的话,我推荐Demon大佬的这篇Blog:用VBS实现PHP的crc32函数。使用MSScriptControl.ScriptControl对象调用js就可以十分方便的实现数据数据左右移。可读性远比我这篇代码要高的多,推荐去读一读方便理解。

    其他博客推荐

    虽说我码这么多字,但我还是没有自信能保证各位一定能懂(强行语文老师背锅),所以我个人觉得写的不错的几篇博客(也是我学习的博客),希望能对大家有用。

    循环冗余校验(CRC)算法入门引导: https://blog.csdn.net/liyuanb...
    我学习CRC32、CRC16、CRC原理和算法的总结(与WINRAR结果一致): https://wenku.baidu.com/view/...
    【脑冻结】CRC我就拿下了: https://www.cnblogs.com/poiu-...
    CRC的基本原理详解: https://blog.csdn.net/dream_1...
    循环冗余检验 (CRC) 算法原理: http://www.cnblogs.com/esestt...
    你真的搞明白CRC的计算过程了吗?: http://blog.chinaaet.com/wuya...
    CRC检错技术原理: https://www.cnblogs.com/forge...
    CRC算法详解与c源码: https://wenku.baidu.com/view/...
    最通俗的CRC校验原理剖析: http://blog.51cto.com/winda/1...
    VB的CRC32校验代码: https://blog.csdn.net/zdingyu...
    CRC校验码原理、实例、手动计算: https://www.cnblogs.com/bugut...
    如何计算CRC32校验和?: https://codeday.me/bug/201708...
    CRC算法与实现: https://blog.csdn.net/ncdawen...

    再推荐两个在线计算网站方便验证程序:

    CRC(循环冗余校验)在线计算: http://www.ip33.com/crc.html
    On-line CRC calculation and free library: https://www.lammertbies.nl/co...

    当然如果你E文比较好的话,还是推荐Ross Williams的《A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS》 http://www.ross.net/crc/downl...

    哦,对了!故事的最后:王大麻子其实喜欢他们班的班长——小强

    展开全文
  • CRC是英文Cyclical Redundancy Check的缩写,翻译成中文通常称作循环冗余校验或简称为CRC校验。它是数据传输领域中最常用的一种差错校验方法,其特点是传输数据和CRC校验值的长度可以任意选定。在当今手机、计算机和...
  • 文章目录1 产生原理1.1 CRC可检测的错误?1.2 CRC生成过程?1.3 接收过程?2 CRC 的计算2.1 手算2.1 在线计算器3 Verilog 实现3.1 线性反馈移位寄存器(LFSR)循环码编码3.2 Verilog代码 1 产生原理 循环冗余校验码...


    1 产生原理

    循环冗余校验码Cyclic Redundancy Check(CRC)

    简介:在发送端根据要传送的K位二进制码序列,以一定的规则产生一个校验用的r位监督码(CRC码),附在信息后面组成n=k+r位的码发出去。这种编码也叫(n,k)码。对于一个给定的(n,k)码,存在一个高次幂为r的多项式G(x),根据多项式G(x)可以生成k位信息的校验码,G(x)叫做这个CRC码的生成多项式, 生成多项式的最高位和最低位必是1。

    1.1 CRC可检测的错误?

    • 突发长度小于n-k+1的突发错误;
    • 大部分突发长度等于n-k+1的突发错误,其中不可检出的占2-(n-k-1);
    • 大部分突发长度大于n-k+1的突发错误,其中不可检出的占2-(n-k);
    • 所有与许用码组 码距 小于dmin-1的错误及所有奇数个错误。

    1.2 CRC生成过程?

    生成过程:发送信息C(x)左移r位,表示为C(x)×2r,C(x)右边空出的r位就是校验码的位置。通过C(x)×2r模2除以生成多项式G(x)得到的余数就是校验码。

    1.3 接收过程?

    接收过程

    1. 计算CRC比较。
    2. 收到的二进制序列(信息码+循环码)除以多项式,如果余数为0,则说明传输过程无错误发生。

    2 CRC 的计算

    以输入数据0x5a,G(x)=x^8+x^2+x+1计算为例。

    2.1 手算

    首先了解模2运算:
    模2加:0+0=0,0+1=1,1+1=0 -> a(模2加)b = a⊕b
    模2减:0-0=0,0-1=1,1-0=1,1-1=0 -> a(模2减)b = a⊕b
    模2乘:0×0=0,0×1=0,1×1=1
    模2除:0/1=0,1/1=1

    根据生成过程:C(x)×2^r模2除以生成多项式G(x)得到的余数就是校验码。
    G(x)对应:0x107

    在这里插入图片描述

    运算过程减法为模2减,即异或运算。
    设余数为R[8:0],注意的是,当 R[7] 为1,下一商位为1,当 R[7] 为0,下一商位为0。
    其他规则与正常二进制除法一致。

    可以看到每次运算的结果:

    输入位余数
    000_0000_0000
    110_0110_1111
    000_0110_1111
    110_1011_1011
    110_0111_0001
    000_0111_0001
    110_1100_0011
    010_1000_0001

    最终的到的余数为:0x81,即我们需要的CRC码,0x5a编码之后为 0x5a|0x81。

    2.1 在线计算器

    CRC(循环冗余校验)在线计算

    在这里插入图片描述

    网页就有各参数的介绍。
    需要注意的是

    • POLY:生成项的简写,以16进制表示。忽略了最高位的"1"。
    • INIT:这是算法开始时寄存器(crc)的初始化预置值,十六进制表示。手动计算过程初始值是0x00。

    3 Verilog 实现

    3.1 线性反馈移位寄存器(LFSR)循环码编码

    以上的计算过程很多文章都有介绍,但是都没有介绍为什么是题目中的结构?
    比如为什么 Verilog实现串行CRC-8,G(D)=D8+D2+D+1,电路结构如下?

    在这里插入图片描述

    其实这是线性反馈移位寄存器(LFSR)循环码编码。

    引用《数字通信(第四版)John G.Proakis著.张力军译》8.1.3 循环码的内容:

    在这里插入图片描述

    对于CRC-8进行信源0x5a的校验,移位运算过程为:
    信源数据的逐个输入等效于把0x5a(8’b01011010)移位后的 16’b0101_1010_0000_0000 拆分为:

    1. 16’b0000_0000_0000_0000 模2除 9’b1_0000_0111 = 商0…余 R1:0000_0000

                                   0
                    ________________________
      8’b1_0000_0111|16'b0000_0000_0000_0000
                    /-   0000_0000_0 
                        ____________
                    =R1: 0000_0000_0     
      

      在这里插入图片描述

      这一步比较直观。所以在这我们就知道为什么在线计算器需要设置初始值?嘿嘿

    2. 16’b0100_0000_0000_0000 模2除 9’b1_0000_0111 ⊕ R1 = 商1…余 R2: 0000_0111

                                   01
                    ________________________
      8’b1_0000_0111|16'b0100_0000_0000_0000
                    /-    100_0001_11   
                     +R1: 0000_0000_0
                         ____________ 
                     =R2: 0000_0011_1
                          
      

      在这里插入图片描述

      这一步值得注意的是生成多项式为0的位可以想象有一个C_(i-1) ⊕ 0,只不过与结果为C_(i-1)省略了,因为加减都是等效于异或,以此实现加上上一步的余数减去因式。

    3. 16’b0000_0000_0000_0000 模2除 9’b1_0000_0111 ⊕ R2 = 商0…余 R3:0000_1110:

    4. 16’b0001_0000_0000_0000 模2除 9’b1_0000_0111 ⊕ R3 = 商1…余 R4:0001_1011:

    5. 16’b0000_1000_0000_0000 模2除 9’b1_0000_0111 ⊕ R4 = 商1…余 R5:1000_1100:

    6. 16’b0000_0000_0000_0000 模2除 9’b1_0000_0111 ⊕ R5 = 商0…余 R6:0110_0010:

    7. 16’b0000_0010_0000_0000 模2除 9’b1_0000_0111 ⊕ R6 = 商1…余 R7:1100_0001:

    8. 16’b0000_0000_0000_0000 模2除 9’b1_0000_0111 ⊕ R7 = 商1…余 R8:1000_0001:

    输入移位移位寄存器值C7~C0
    00000_0000
    000000_0000
    110000_0111
    000000_1110
    110001_1011
    111000_1100
    000110_0010
    111100_0001
    011000_0001

    可以看到,这其实就是对应我们模2除运算的过程。

    3.2 Verilog代码

    OutputLogic可以在线生成CRC代码,我们在生成的基础上改就好了。
    在这里插入图片描述

    在这里插入图片描述

    展开全文
  • CRC原理简析 1. CRC校验原理 CRC校验原理根本思想就是先在要发送的帧后面附加一个数(这个就是用来校验的校验码,但要注意,这里的数也是二进制序列的,下同),生成一个新帧发送给接收端。当然,这个附加的数不是...

    CRC原理简析

    1. CRC校验原理
    CRC校验原理根本思想就是先在要发送的帧后面附加一个数(这个就是用来校验的校验码,但要注意,这里的数也是二进制序列的,下同),生成一个新帧发送给接收端。当然,这个附加的数不是随意的,它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除(注意,这里不是直接采用二进制除法,而是采用一种称之为“模2除法”)。到达接收端后,再把接收到的新帧除以(同样采用“模2除法”)这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数,做了“去余”处理(也就已经能整除了),所以结果应该是没有余数。如果有余数,则表明该帧在传输过程中出现了差错。
    【说明】“模2除法”与“算术除法”类似,但它既不向上位借位,也不比较除数和被除数的相同位数值的大小,只要以相同位数进行相除即可。模2加法运算为:1+1=0,0+1=1,0+0=0,无进位,也无借位;模2减法运算为:1-1=0,0-1=1,1-0=1,0-0=0,也无进位,无借位。相当于二进制中的逻辑异或运算。也就是比较后,两者对应位相同则结果为“0”,不同则结果为“1”。如100101除以1110,结果得到商为11,余数为1,如图5-9左图所示。如11×11=101,如图所示。
    在这里插入图片描述

    具体来说,CRC校验原理就是以下几个步骤:
    (1)先选择(可以随机选择,也可按标准选择,具体在后面介绍)一个用于在接收端进行校验时,对接收的帧进行除法运算的除数(是二进制比较特串,通常是以多项方式表示,所以CRC又称多项式编码方法,这个多项式也称之为“生成多项式”)。
    (2)看所选定的除数二进制位数(假设为k位),然后在要发送的数据帧(假设为m位)后面加上k-1位“0”,然后以这个加了k-1个“0“的新帧(一共是m+k-1位)以“模2除法”方式除以上面这个除数,所得到的余数(也是二进制的比特串)就是该帧的CRC校验码,也称之为FCS(帧校验序列)。但要注意的是,余数的位数一定要是比除数位数只能少一位,哪怕前面位是0,甚至是全为0(附带好整除时)也都不能省略。
    (3)再把这个校验码附加在原数据帧(就是m位的帧,注意不是在后面形成的m+k-1位的帧)后面,构建一个新帧发送到接收端;最后在接收端再把这个新帧以“模2除法”方式除以前面选择的除数,如果没有余数,则表明该帧在传输过程中没出错,否则出现了差错。
    通过以上介绍,大家一定可以理解CRC校验的原理,并且不再认为很复杂吧。
    从上面可以看出,CRC校验中有两个关键点:一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串(或多项式);二是把原始帧与上面选定的除进行二进制除法运算,计算出FCS。前者可以随机选择,也可按国际上通行的标准选择,但最高位和最低位必须均为“1”,如在IBM的SDLC(同步数据链路控制)规程中使用的CRC-16(也就是这个除数一共是17位)生成多项式g(x)= x16 + x15 + x2 +1(对应二进制比特串为:11000000000000101);而在ISO HDLC(高级数据链路控制)规程、ITU的SDLC、X.25、V.34、V.41、V.42等中使用CCITT-16生成多项式g(x)= x16 + x15 + x5+1(对应二进制比特串为:11000000000100001)。
    2. CRC校验码的计算示例
    由以上分析可知,既然除数是随机,或者按标准选定的,所以CRC校验的关键是如何求出余数,也就是校验码(CRC校验码)。
    下面以一个例子来具体说明整个过程。现假设选择的CRC生成多项式为G(X) = X4 + X3 + 1,要求出二进制序列10110011的CRC校验码。下面是具体的计算过程:
    (1)首先把生成多项式转换成二进制数,由G(X) = X4 + X3 + 1可以知道(,它一共是5位(总位数等于最高位的幂次加1,即4+1=5),然后根据多项式各项的含义(多项式只列出二进制值为1的位,也就是这个二进制的第4位、第3位、第0位的二进制均为1,其它位均为0)很快就可得到它的二进制比特串为11001。
    (2)因为生成多项式的位数为5,根据前面的介绍,得知CRC校验码的位数为4(校验码的位数比生成多项式的位数少1)。因为原数据帧10110011,在它后面再加4个0,得到101100110000,然后把这个数以“模2除法”方式除以生成多项式,得到的余数(即CRC码)为0100,如图所示。注意参考前面介绍的“模2除法”运算法则。
    在这里插入图片描述

    (3)把上步计算得到的CRC校验0100替换原始帧101100110000后面的四个“0”,得到新帧101100110100。再把这个新帧发送到接收端。
    (4)当以上新帧到达接收端后,接收端会把这个新帧再用上面选定的除数11001以“模2除法”方式去除,验证余数是否为0,如果为0,则证明该帧数据在传输过程中没有出现差错,否则出现了差错。
    通过以上CRC校验原理的剖析和CRC校验码的计算示例的介绍,大家应该对这种看似很复杂的CRC校验原理和计算方法应该比较清楚了。

    3. 模2运算的硬件实现
    对于一个给定的(N,K)码,可以证明存在一个最高次幂为N-K=R的多项式G(x)可以使整个编码被除余数为0。M(x)为原始序列,r为补充的r个0。
    在这里插入图片描述
    在这里插入图片描述
    4. 总结
    CRC16: x16+….
    CRC24: x24+….
    CRC32: x32+….
    <1>原有序列后面补0(CRC多少就补多少个0)。
    <2>做模2除法,将余数补到原始序列后面。
    发送
    <3>接收端对序列做模2除法
    <4>判决余数是否为0,否则错误。
    注:硬件实现的移位寄存器数量等于24(CRC24)

    展开全文
  • 我学习CRC32、CRC16、CRC原理和算法的总结(与WINRAR结.doc
  • ADSL通信系统中CRC原理及案例分析 绪论 循环冗余校验码(CRC)因编码简单且误判概率很低在通信系统中得到了广泛的应用循环冗余校验码的英文全称为Cyclic Redundancy Check缩写为CRC CRC是ADSL通信系统中关于误码率BER...
  • 【很好】我学习CRC32、CRC16、CRC原理和算法的总结(与WINRAR结果一致).pdf
  • CRC原理简述

    千次阅读 2017-04-12 17:26:46
    以下内容摘自笔者即将出版的最新著作《深入理解计算机网络》一书。... 上节介绍的奇偶校验码(PCC)只能校验一位错误,本节所要介绍的循环冗余校验码(CRC)的检错能力更强,可以检出多位错误。 1. C
  • CRC原理

    2011-02-25 15:59:54
    CRC.......................................................................................
  • CRC原理详解(附crc16校验代码)

    千次阅读 2020-06-09 14:46:23
    CRC原理详解算法原理查表法反向算法附录1:crc16校验表及用法 算法原理 Cyclic Redundancy Check循环冗余检验,是基于数据计算一组效验码,用于核对数据传输过程中是否被更改或传输错误。 假设数据传输过程中需要...
  • 当看了这个文档后,就对CRC算法完全明白了,其实很简单,并不像网上摆的一大堆公式那么复杂!半小时搞定CRC算法!!内包含一个CRC16的C语言程序VC++或turboc可以直接打开运行...
  • crc原理及c代码实现

    2021-07-14 22:14:18
    具体crc原理可参见 https://www.cnblogs.com/esestt/archive/2007/08/09/848856.html。看来看去,关于代码实现部分网上都是互相拷贝,没有一个完整的crc实现,因此想着把所有crc8/16/32基于查表法的实现在该博客写...
  • 查表法CRC原理

    2021-03-12 18:51:34
    https://www.xuebuyuan.com/1592737.html
  • CRC原理和算法总结

    2010-11-02 12:41:10
    介绍了计算机网络中的CRC算发。并且针对学习CRC原理的一些个人总结。
  • 循环冗余检验CRC原理

    万次阅读 多人点赞 2017-05-11 16:44:59
    为什么引入CRC现实的通信链路都不会是理想的。这就是说,比特在传输的过程中可能会产生差错:1可能会变成0,0可能会变成1,这就叫做比特差错。在一段是时间内,传输错误的比特占所传输比特总数的比率成为误码率BER...
  • 这篇文是在网上搜集的,特拿来与大家共享:我学习CRC32、CRC16、CRC原理和算法的总结(与WINRAR结果一致
  • 网络纠错CRC原理

    2011-12-15 20:01:33
    网络纠错CRC原理 同步光纤网 SONET 和同步数字系列 SDH 循环冗余检验的原理
  • CRC原理详解

    千次阅读 2019-03-04 21:31:44
    参考链接: ... CyclicRedundancyCheck循环冗余检验,是基于数据计算一组效验码,用于核对数据传输过程中是否...算法原理 假设数据传输过程中需要发送15位的二进制信息g=101001110100001,这串二进制码可表示为代...
  • CRC原理和C语言实现CRC

    千次阅读 2020-08-25 15:02:16
    一、CRC原理 CRC是对传输的数据进行一个差错校验的,但是不对数据进行纠错,CRC检测不通过的时候丢弃数据 CRC冗余校验 首先先明确几个点: 多项式的被除数M,也就是信息码(数据) 多项式的除数G 得到的结果冗余校验...
  • CRC原理和实例

    2019-11-11 15:54:33
    算法原理 假设数据传输过程中需要发送15位的二进制信息g=101001110100001,这串二进制码可表示为代数多项式g(x) = x^14 + x^12 + x^9 + x^8 + x^7 + x^5 + 1,其中g中第k位的值,对应g(x)中x^k的系数。将...
  • CRC 原理 CRC计算 介绍

    2009-10-28 23:02:42
    CRC计算与普通的除法计算有所不同。普通的除法计算是借位相减的,而CRC计算则是异或运算。任何一个除法运算都需要选取一个除数,在CRC运算中我们称之为poly,而宽度W就是poly最高位的位置。比如poly 1001的W是3,而...
  • 1.做课设的时候看了很多资料,结果很多...1. CRC校验原理CRC校验原理其实是很简单的问题,其根本思想就是先在要发送的帧后面附加一个二进制数(这个数就是校验码),生成一个新帧发送给接收端。例如: 要发送 1 校验码1...
  • CRC原理及其逆向分析方法

    千次阅读 2019-07-22 23:46:30
    CRC原理及其逆向破解方法: 介绍: 这篇短文包含CRC原理介绍和其逆向分析方法,很多程序员和破解者不是很清楚了解CRC的工作原理,而且几乎没人知道如何逆向分析它的方法,事实上它是非常有用的.首先,这篇教程教你...
  • 下面是网上找到的CRC原理,不弄长的了,凑合看吧。CRC 校验的基本思想是利用线性编码理论,在发送端根据要传送的k位二进制码序列,以一定的规则产生一个校验用的监督码(既CRC 码)r 位,并附在信息后边,构成一个新的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,167
精华内容 16,466
关键字:

crc原理

友情链接: 双机UART串口通信.zip