0

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".

Community
  • 1
  • 1
Sorayuki
  • 256
  • 2
  • 7
  • (Spelling note: it's "remainder" (what remains), not "reminder" (what reminds you of... what?).) – gx_ Jun 25 '13 at 09:02
  • @gx_ I'm sorry. I'm not a native English speaker. I'll edit to fix it. – Sorayuki Jun 25 '13 at 09:04
  • Don't be sorry :) but djf cancelled your fix when fixing "grammer"... Edit: and fixed it back afterwards ^^ Ok now back to CRC! – gx_ Jun 25 '13 at 09:10
  • 1
    Read [this](http://www.ross.net/crc/download/crc_v3.txt). (Also [here](http://www.repairfaq.org/filipg/LINK/F_crc_v3.html), [here](http://zlib.net/crc_v3.txt), and [here](http://www.intel-assembler.it/portale/5/A-Painless-Guide-To-Crc-Error-Detection-Algorithms/A-Guide-To-Crc-Error-Detection-Algorithms.asp) for those who would complain about link rot.) – Mark Adler Jun 25 '13 at 14:39

0 Answers0