最简单的CRC32源码-逐BYTE法

从按BIT计算转到按BYTE计算,要利用异或的一个性质,具体见前面的文章《再探CRC 》。

其实方法跟逐BIT法是一样的,我们只是利用异或的性质,把数据分成一BYTE一BYTE来计算,一BYTE数据会有256种值,每一种值与POLY(生成多项式)进行模二除法的余数都是唯一的,所以我们可以先把这256个余数先计算出来,放到一个表里,这样对每一BYTE进行模二除求余的计算都节省了。

如果不用查表的方法,逐BYTE法对比逐BIT法没什么区别,因为计算量是一样的,逐BYTE法还会多好多跳转步骤。

使用查表方法,计算一个32位数据只需要异或4次+查表4次,是不是快得多了

以0x035b035b为例

令Reg=0x035b035b

1 .从Reg中取头一个BYTE即0x03扩展成0x03000000与POLY逐BIT模二除求余,得一个u32的TempReg,然后用其与剩下的Reg(0x5b035b00)异或得到更新的Reg

2.再从Reg中取头一个BYTE进行1的步骤,直到最后一Byte计算完毕,因为一个32数据有4个BYTE,所以总共需要计算4次

其实这跟逐BIT计算没什么区别,用《再探CRC 》里的算例里的两种方法实际手算一下,就能体会。

如果我们有之前说的表,那步骤1可以变成:

1 .从Reg中取头一个BYTE即0x03,查表直接得到0x03与POLY逐BIT模二除的余数,得一个u32的TempReg,然后用其与剩下的Reg(0x5b035b00)异或得到更新的Reg

下面就是用逐BYTE法来进行CRC校验的函数:

/*CRC校验程序*/
//输入32位
//多项式,省略最高位1 0x4C11DB7 CCITT-32:   0x04C11DB7  =  x32 + x26 +  x23 + x22 + x16 + x12 +
//                              x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
//数据不revert 结果不revert
//初值0x00000000或0xFFFFFFFF,其实所谓的初值就是原始数据要不要跟0xFFFFFFFF先异或先放到Reg中计算,用0xFFFFFFFF只是为了让别人不
//会一下就看出生成多项式是多少
//结果不异或
//验证网址:http://www.zorc.breitbandkatze.de/crc.html
//算法中数据向左移动,相对手工计算等效于生成多项式向右移动,所以不需要在后面加一大堆0
u32 CRC_Check_Software(u8 *ucpData,u8 Length)
{
    u32 poly=0x4C11DB7; //生成多项式
    u32 Reg=0x00000000; //初值
    u32 tempbyte=;
    u8 i;
    u8 count;
    u8 j=;
    u8 u32DataLen=((Length/)>)?((Length/)+):(Length/);
    u32 uipData[]={};
    //把byte组合成32位一组的数据放入uipData
    ;i<Length;i++)
    {
        uipData[i/]|=((u32)(*(ucpData+i)))<<(*(j-));
        j--;
        )
        {
            j=;
        }
    }
    //以下是算法开始

    //逐BYTE法
    ;count<u32DataLen;count++)
    {
        Reg=uipData[count];
        //Reg^=0xffffffff;//如果初值为0x00000000就把这行注释掉,否则不要注释
        ;i<;i++)
        {
            tempbyte= (( Reg >>  ) & ;//取一个byte
            ;j<;j++)
            {
                if(tempbyte&0x80000000)
                {
                    tempbyte=tempbyte<<;//要异或时Reg的最高位是1,CRC多项式最高位一直就是1,异或后必为0,所以一开始就偷懒把CRC多项式去掉最高位变成
                                       //0x4C11DB7 ,所以相应的这时候要把Reg左移一位,只要异或后边的32位
                    tempbyte^=poly;
                }
                else
                {
                    tempbyte=tempbyte<<;
                }
            }
            Reg=Reg<<; //丢掉计算过的头一个BYTE
            Reg^=tempbyte; //与前一个BYTE的计算结果异或 

        }
    }

    /*位计算算法
    for(i=0;i<u32DataLen;i++)
    {
        Reg=uipData[i];
        Reg^=0xffffffff;//如果初值为0x00000000就把这行注释掉,否则不要注释
        for(j=0;j<32;j++)
        {
            if(Reg&0x80000000)
            {
                Reg=Reg<<1;//要异或时Reg的最高位是1,CRC多项式最高位一直就是1,异或后必为0,所以一开始就偷懒把CRC多项式去掉最高位变成
                                //0x4C11DB7 ,所以相应的这时候要把Reg左移一位,只要异或后边的32位
                Reg^=poly;
            }
            else
            {
                Reg=Reg<<1;
            }

        }
    }
    */

    return Reg;
}

这一部分就是对每一个BYTE模二求余:

;j<;j++)
{
    if(tempbyte&0x80000000)
    {
        tempbyte=tempbyte<<;    // 要异或时Reg的最高位是1,CRC多项式最高位一直就是1,异或后必为0,所以一开始就偷懒把CRC多项式去掉最高位变成
                                // 0x4C11DB7 ,所以相应的这时候要把Reg左移一位,只要异或后边的32位
        tempbyte^=poly;
    }
    else
    {
        tempbyte=tempbyte<<;
    }
} 

是不是就是前一篇文章里的逐BIT法?

上一篇:在Mac OS环境下安装MySQL服务


下一篇:android 5.1 WIFI图标上的感叹号及其解决办法