程序设计

算了一天终于把CRC32算对了，也理解了boost库的做法

留下评论

满满的一种“被坑了”的感觉。

CRC32不是有什么多项式、初始值、调换bit顺序、结果xor值、调换结果位序之类的参数吗，常用的这个

多项式：0x104C11DB7
初始值：0xFFFFFFFF
结果异或值：0xFFFFFFFF
调换输入字节位序：是
调换结果字节位序：是

CRC的理论也不难，我就一个比特一个比特处理，写了这样的代码

void CRC32::ProcessBit(bool bit)
{
/*   top                                bit
    x xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx b : x curVal
    1 yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy y : y polynomial
*/
    bool topBit = _remainder & 0x80000000 ? 1 : 0;

    _remainder <<= 1;
    _remainder |= bit ? 1 : 0;
    if (topBit)
        _remainder ^= polynomial;
}

看着没问题是不是，我也觉得看着没问题。

但是它就是算不出正确结果（……

最后只能找了本科时的某室友帮忙看。结果人家找来一篇文章

http://wenku.baidu.com/view/fb791c0203d8ce2f006623f5.html

中间赫然写着

INIT

这是算法开始时寄存器的初始化预置值，十六进制表示。  这个值可以直接赋值给“直驱表法”算法中的寄存器，作为寄存器的初始值！  而对于“驱动表法”算法及“直接计算法”，寄存器的初始值必须是0！前面几次循环先将待测数据移入到寄存器中，当寄存器装满后，再用这个初始化预置值去XOR寄存器，这样寄存器就被这个值初始化了！  这点很重要！！如果在“驱动表法”算法开始时，寄存器的初始值不为0，那么寄存器中的值就会相当于是待测数据了，这样算出的CRC结果就不对了！我们的目的是用预置值去初始化寄存器，而不是将预置值作为待测数据去处理！

“而对于‘驱动表法’算法及‘直接计算法’，寄存器的初始值必须是0！”

必须是0………………
必须是0…………
必须是0……

然后我的代码赫然把_remainder在初始化的时候给置0xFFFFFFFF了。

改成寄存器填满以后xor一下0xFFFFFFFF，初始值0，数据最后加送32个bit的0，然后它就算对了。

对于Boost的实现，它初始值0xFFFFFFFF，最后也不用送32个bit的0，每个bit是这样处理的

void CRC32::ProcessBit(bool bit) {
    bool topBit = (_remainder & 0x80000000) ? true : false;
    _remainder <<= 1;
    if (topBit != bit) {
        _remainder ^= polynomial;
    }
}

看不懂，但能算对。到底是什么原理呢……

补充：花了好多时间研究，终于懂得它怎么做的了。

boost的算法，为什么是“首先比较最高位和新进来的位，然后余数左移。如果不相等则余数异或多项式”

如果每次送入的数据都事先后面加上32个0，那么在最后就不需要送入32个0也可以得到正确的结果了。
举个例子，数据是1010010，多项式长度5，那么送入的分别是1,0,1,0,0,1,0,0,0,0,0。但是如果看作送入的是10000,0,10000,0,0,10000,0，根据除法性质，结果应该是一样的。

为什么是一样的呢？拿平时的除法举例。比如142÷8，现在要补充一个0变成1420÷8，计算过程：
1÷8 = 0……1，1左移一位变成10
（10 + 4）÷8 = 1……6，6左移变成60
（60 + 2）÷8 = 7……6
（60 + 0）÷8 = 7……4
所以商177余数4

v这里的“左移一位”，是因为余数的位权每次都要左移，
竖式除法的时候，每次从除数拿一位下来加在余数的末尾对吧
这就说明每次余数最右数字的位权都要比除数拿下来那一位大一个等级

好了，boost是什么意思呢？
10÷8 = 1……2，2左移一位变20 ←注意，左移还是要的，因为位权问题
（20 + 40）÷8 = 7……4
（40 + 20）÷8 = 7……4
商177余4。结果是一样的。

就是说加的最后一个0，变成每个送进来除的数字都加0，然后最后就不用送那个0了。
十进制可以，但是现在减法不是正常的减法是不退位减法，加法不是加法是不退位加法，还能适用的原因……我不知道了，大概和离散数学里面那些什么理论有关系？群啊域啊什么什么的。

于是计算过程中，左移余数以后，都先对送入的bit把0加好（对于CRC32，加32个0），于是送入的比特如果是1，那么就把余数左移后加上0x100000000；如果是0就把余数左移后加上0x000000000，然后进行下一位的除法运算。因为二进制无进位加法中，加是等同于异或，于是变成余数首位和送进来的bit异或。

比如余数是0x12345678，送进来的比特是1，这里送进来的数就按照0x100000000算。余数左移一位然后加上送进来的比特，0x2468acf0 + 0x100000000 = 0x12468acf0，然后看看够不够多项式除。

因为多项式的首位一定是1，而且只要比较这一位就够了。所以如果余数的高位是1，送进来的比特也是1，那么相加后造成溢出，首位变0，不够多项式除，于是商0；如果相加后首位是1，够多项式除，那么商1，然后余数就减去多项式乘以1（因为“多项式”是除数。二进制无借位减法相当于异或）。和最基本理论上的那种把新的数据放在余数最末端的相比，它余数最末端都是补的0，所以不会出现相加溢出的情况，也就是送进什么数据直接粘在余数末尾就好了。这个需要好好理解。

综合一下，变成：

比较送进来的位和余数的最高位
    相等：余数左移一位，然后和多项式进行异或
    不等：余数左移一位

这是boost的做法。

按照这样说，它最开始的余数是0xFFFFFFFF，为什么之前的理论算法最后变成填满数据以后再和initial进行异或呢？仔细想想看，boost的做法每次送进来的是一个33位的数（首位1或0，其他都是0）。平时计算除法的时候呢，是不是一开始先从被除数中找出和除数相同长度的部分来试商？这个0xFFFFFFFF被看作“上一轮的余数”，是加到试商这部分去的。好了，“加”，二进制无进位加法相当于异或。

那个initial value如果当作最初的余数，然后一个比特一个比特从右边送进来，会错误的原因是initial value的位权和送进来的比特的位权不同……本来initial value的最左bit位权应该和数据的第一个bit位权相等的，简单说就是initial value的最高位应该和送进来的第一个bit竖式运算的时候对齐的

发表评论