1
$\begingroup$

I'm currently trying to understand an implementation of CRC32 about which I have a question.

On this page at section 6, there is the following code:

public uint Compute_CRC32_Simple(byte[] bytes)
{
    const uint polynomial = 0x04C11DB7; /* divisor is 32bit */
    uint crc = 0; /* CRC value is 32bit */

    foreach (byte b in bytes)
    {
        crc ^= (uint)(b << 24); /* move byte into MSB of 32bit CRC */

        for (int i = 0; i < 8; i++)
        {
            if ((crc & 0x80000000) != 0) /* test for MSB = bit 31 */
            {
                crc = (uint)((crc << 1) ^ polynomial);
            }
            else
            {
                crc <<= 1;
            }
        }
    }

    return crc;
}

I'm particularly interested in understanding this line: crc ^= (uint)(b << 24); /* move byte into MSB of 32bit CRC */

What are the mathematics that make this line possible, both the shifting of the current byte (turned into an int) by 24 and the following XOR with the current crc? Unfortunately, the author doesn't go into detail regarding this. What I want to know is why dividing the current byte and then xoring the remainder with the next byte is the same as a manual division bit by bit

EDIT: made question clearer

$\endgroup$

1 Answer 1

1
$\begingroup$

Perhaps what you are imagining is something like this at the top of the inner loop, where the bits of b are fed one-by-one into the high bit of the CRC:

        if (b & 0x80)
            crc ^= 0x80000000;
        b <<= 1;

That is equivalent to this:

        crc ^= (uint)(b & 0x80) << 24;
        b <<= 1;

Now you can see where the 24 comes from. Note that each time, both crc and b are shifted up by one. It only makes decisions based on the high bit of crc, and the order that you do exclusive-or's in doesn't matter, so you can simply exclusive-or all eight of the bits of b into the high byte of crc outside of the inner loop, to get the same effect:

    crc ^= (uint)b << 24;
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.