I have attempted many times to write my own CRC32 implementation according to the theory, but I never got the expected results.
Today I have made another try, referring not only the theory but also the Boosts's implementation. Although I finally got it working correctly, I don't understand why it works like this.
I understand why boost reverses the byte and reverses the result, I know why it's initial remainder is 0xffffffff and the result should be XOR'ed with 0xffffffff. It's the standard.
But when it gets to the function ProcessBit
, I get stuck.
In the answer to How is a CRC32 checksum calculated?, I found a full example. So I think the implementation of ProcessBit
looks like this:
void CRC32::ProcessBit(bool b)
{
/*
x xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxb : x curVal, b coming bit
1 yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy : y polynomial
*/
if (_remainder & 0x80000000) {
_remainder <<= 1;
_remainder |= b;
_remainder ^= polynomial;
} else {
_remainder <<= 1;
_remainder |= b;
}
}
since the first bit of the polynomial is 1, if the remainder begins with bit 1 I shall XOR it. But this implementation generates a wrong result. I traced the code in Boost to see how it works, and write my own one:
void CRC32::ProcessBit(bool b)
{
bool high = (_remainder & 0x80000000) ? true : false;
_remainder <<= 1;
if (high != b) {
_remainder ^= polynomial;
}
}
This implementation works well. but I don't understand why. What confuses me is that the condition to determined whether the remainder should be XOR'ed with the polynomial is:
"the first bit of remainder equals the coming bit".
Whereas in the "full example" another condition is used, namely:
"the first bit of remainder is 1".
Another question is; why the coming bit will not be appended at the end of remainder in Boost's implementation.
Edit: I have solved the problem. The reason why it generated a wrong result is that I misunderstand the meaning of "initial value".