Basic CRC32 Wikipedia implementation differs from standard CRC32 seen online

12
votes

I have a basic CRC32 implementation following Wikipedia's Code Fragment:1 sample. I think I have done it right, with the modification of using an n-bit register for the remainderPolynomial instead of n+1 bit usage as per the example.

The result I get differs from the online CRC32 implementation results. What do I have to change here in my implementation?

Please ignore Console.Writeline statements for the logic.

    const UInt32 poly = 0x04C11DB7;

    public static UInt32 GenerateCRC_32(byte[] message)
    {
        byte[] augmentedMsg = new byte[message.Length + 4];
        message.CopyTo(augmentedMsg, 0);

        UInt32 remainder = Convert.ToUInt32(augmentedMsg[0]) << 24 |
                           Convert.ToUInt32(augmentedMsg[1]) << 16 |
                           Convert.ToUInt32(augmentedMsg[2]) <<  8 |
                           Convert.ToUInt32(augmentedMsg[3]);

        for (Int32 i = 4; i < augmentedMsg.Length; i++)
        {
            for (int bit = 0; bit < 8; bit++)
            {
                UInt32 nextBit = ((UInt32)augmentedMsg[i] >> (7 - bit)) & 0x01;
                if ((remainder & 0x80000000) > 0)
                {
                    Console.WriteLine("---------------DO XOR --------------------");
                    Console.WriteLine(Convert.ToString(((remainder << 1) | nextBit), 2).PadLeft(32, '0'));
                    Console.WriteLine(Convert.ToString(poly, 2).PadLeft(32, '0'));
                    Console.WriteLine("------------------------------------------");

                    remainder = ((remainder << 1) | nextBit) ^ poly;

                    Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0'));
                    Console.WriteLine("------------------------------------------");
                }
                else
                {
                    remainder = (remainder << 1) | nextBit;

                    Console.WriteLine("--------------NO---------------------");
                    Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0'));
                    Console.WriteLine("------------------------------------------");
                }
            }
        }

        Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0'));
        Console.WriteLine(remainder.ToString("X"));

        return remainder;
    }

I am not looking for the best way to optimize the logic, since I am just trying to follow Wikipedia sample using C#.

Input Message : 'A' (hex : 0x41) Output : 0x30476DC0 As per this website : Output should be : 0xD3D99E8B

I think I am missing either the reversal/Initialization of the CRC, but I am not sure how to change this basic implementation to get the result equivalent to the website's result.

Output on running my program:

--------------NO---------------------
10000010000000000000000000000000
------------------------------------------
---------------DO XOR --------------------
00000100000000000000000000000000
00000100110000010001110110110111
------------------------------------------
00000000110000010001110110110111
------------------------------------------
--------------NO---------------------
00000001100000100011101101101110
------------------------------------------
--------------NO---------------------
00000011000001000111011011011100
------------------------------------------
--------------NO---------------------
00000110000010001110110110111000
------------------------------------------
--------------NO---------------------
00001100000100011101101101110000
------------------------------------------
--------------NO---------------------
00011000001000111011011011100000
------------------------------------------
--------------NO---------------------
00110000010001110110110111000000
------------------------------------------
00110000010001110110110111000000

The last line into hex: 0x30476DC0

Follow-up to @Mark Adler Comments:**

I modified the above as follows, following are the modifications (comments are added inline to the code):

  1. Initialized to 0xFFFFFFFF
  2. Reversed the input message byte

  3. XOR to the final value, reverse of the XORed value

    public static UInt32 GenerateCRC_32(byte[] message) { byte[] augmentedMsg = new byte[message.Length + 8]; message.CopyTo(augmentedMsg, 4); // Modified to create space for initialization

    UInt32 remainder = Convert.ToUInt32(augmentedMsg[0]) << 24 |
                   Convert.ToUInt32(augmentedMsg[1]) << 16 |
                   Convert.ToUInt32(augmentedMsg[2]) <<  8 |
                   Convert.ToUInt32(augmentedMsg[3]);

remainder = ~remainder; // Overwrite the above and initialized the register to 0xFFFFFFFF

for (Int32 i = 4; i < augmentedMsg.Length; i++)
{
    byte reversedMessage = Reverse(augmentedMsg[i]); // Reversed the augmented message byte
    for (int bit = 0; bit < 8; bit++)
    {
        UInt32 nextBit = Convert.ToUInt32(reversedMessage >> (7 - bit)) & 0x1; // Use the reversed message byte
        if ((remainder & 0x80000000) > 0)
        {
            Console.WriteLine("---------------DO XOR --------------------");
            Console.WriteLine(Convert.ToString(((remainder << 1) | nextBit), 2).PadLeft(32, '0'));
            Console.WriteLine(Convert.ToString(poly32, 2).PadLeft(32, '0'));
            Console.WriteLine("------------------------------------------");

            remainder = Convert.ToUInt32((UInt32)((UInt32)(remainder << 1) | nextBit) ^ poly32);

            Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0'));
            Console.WriteLine("------------------------------------------");
        }
        else
        {
            remainder = (UInt32)((UInt32)(remainder << 1) | nextBit);

            Console.WriteLine("--------------NO---------------------");
            Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0'));
            Console.WriteLine("------------------------------------------");
        }
    }
}

Console.WriteLine(Convert.ToString(remainder, 2).PadLeft(32, '0') + "(" + remainder.ToString("X") + ")");

remainder = (~remainder);

Console.WriteLine("XOR ^ 0xFFFFFFFF : " + Convert.ToString(remainder, 2).PadLeft(32, '0') + "(" + remainder.ToString("X") + ")");

remainder = Reverse(remainder);

Console.WriteLine("Reversed the Abv : " + Convert.ToString(remainder, 2).PadLeft(32, '0') + "(" + remainder.ToString("X") + ")");
return remainder;

    }

Output:

---------------DO XOR --------------------
11111111111111111111111111111111
00000100110000010001110110110111
------------------------------------------
11111011001111101110001001001000
------------------------------------------
---------------DO XOR --------------------
11110110011111011100010010010000
00000100110000010001110110110111
------------------------------------------
11110010101111001101100100100111
------------------------------------------
---------------DO XOR --------------------
11100101011110011011001001001110
00000100110000010001110110110111
------------------------------------------
11100001101110001010111111111001
------------------------------------------
---------------DO XOR --------------------
11000011011100010101111111110010
00000100110000010001110110110111
------------------------------------------
11000111101100000100001001000101
------------------------------------------
---------------DO XOR --------------------
10001111011000001000010010001010
00000100110000010001110110110111
------------------------------------------
10001011101000011001100100111101
------------------------------------------
---------------DO XOR --------------------
00010111010000110011001001111010
00000100110000010001110110110111
------------------------------------------
00010011100000100010111111001101
------------------------------------------
--------------NO---------------------
00100111000001000101111110011011
------------------------------------------
--------------NO---------------------
01001110000010001011111100110110
------------------------------------------
--------------NO---------------------
10011100000100010111111001101100
------------------------------------------
---------------DO XOR --------------------
00111000001000101111110011011000
00000100110000010001110110110111
------------------------------------------
00111100111000111110000101101111
------------------------------------------
--------------NO---------------------
01111001110001111100001011011110
------------------------------------------
--------------NO---------------------
11110011100011111000010110111100
------------------------------------------
---------------DO XOR --------------------
11100111000111110000101101111000
00000100110000010001110110110111
------------------------------------------
11100011110111100001011011001111
------------------------------------------
---------------DO XOR --------------------
11000111101111000010110110011110
00000100110000010001110110110111
------------------------------------------
11000011011111010011000000101001
------------------------------------------
---------------DO XOR --------------------
10000110111110100110000001010010
00000100110000010001110110110111
------------------------------------------
10000010001110110111110111100101
------------------------------------------
---------------DO XOR --------------------
00000100011101101111101111001010
00000100110000010001110110110111
------------------------------------------
00000000101101111110011001111101
------------------------------------------
--------------NO---------------------
00000001011011111100110011111010
------------------------------------------
--------------NO---------------------
00000010110111111001100111110100
------------------------------------------
--------------NO---------------------
00000101101111110011001111101000
------------------------------------------
--------------NO---------------------
00001011011111100110011111010000
------------------------------------------
--------------NO---------------------
00010110111111001100111110100000
------------------------------------------
--------------NO---------------------
00101101111110011001111101000000
------------------------------------------
--------------NO---------------------
01011011111100110011111010000000
------------------------------------------
--------------NO---------------------
10110111111001100111110100000000
------------------------------------------
---------------DO XOR --------------------
01101111110011001111101000000000
00000100110000010001110110110111
------------------------------------------
01101011000011011110011110110111
------------------------------------------
--------------NO---------------------
11010110000110111100111101101110
------------------------------------------
---------------DO XOR --------------------
10101100001101111001111011011100
00000100110000010001110110110111
------------------------------------------
10101000111101101000001101101011
------------------------------------------
---------------DO XOR --------------------
01010001111011010000011011010110
00000100110000010001110110110111
------------------------------------------
01010101001011000001101101100001
------------------------------------------
--------------NO---------------------
10101010010110000011011011000010
------------------------------------------
---------------DO XOR --------------------
01010100101100000110110110000100
00000100110000010001110110110111
------------------------------------------
01010000011100010111000000110011
------------------------------------------
--------------NO---------------------
10100000111000101110000001100110
------------------------------------------
---------------DO XOR --------------------
01000001110001011100000011001100
00000100110000010001110110110111
------------------------------------------
01000101000001001101110101111011
------------------------------------------
--------------NO---------------------
10001010000010011011101011110110
------------------------------------------
---------------DO XOR --------------------
00010100000100110111010111101100
00000100110000010001110110110111
------------------------------------------
00010000110100100110100001011011
------------------------------------------
--------------NO---------------------
00100001101001001101000010110110
------------------------------------------
--------------NO---------------------
01000011010010011010000101101100
------------------------------------------
--------------NO---------------------
10000110100100110100001011011000
------------------------------------------
---------------DO XOR --------------------
00001101001001101000010110110000
00000100110000010001110110110111
------------------------------------------
00001001111001111001100000000111
------------------------------------------
--------------NO---------------------
00010011110011110011000000001110
------------------------------------------
--------------NO---------------------
00100111100111100110000000011100
------------------------------------------
00100111100111100110000000011100(279E601C)
XOR ^ 0xFFFFFFFF : 11011000011000011001111111100011(D8619FE3)
Reversed the Abv : 11000111111110011000011000011011(C7F9861B)

This is not the expected output. I implemented the same using the below table lookup code, the result is exactly same as above (0xC7F9861B), which is wrong

public static UInt32 GenerateCRC_32_from_Table(byte[] message)
    {
        byte[] augmentedMsg = new byte[message.Length + 4];
        message.CopyTo(augmentedMsg, 0);

        UInt32 remainder = 0xFFFFFFFF;

        foreach (byte msgByte in augmentedMsg)
        {
            byte reversedMsgByte = Reverse(msgByte);
            remainder = ((remainder << 8) | Convert.ToUInt32(reversedMsgByte)) ^ crc32_table[((remainder >> 24)) & 0xFF];
        }

        remainder = Reverse(~remainder);
        return remainder;
    }

Whereas if I use the code below (which avoids message augmentation) yielded right result.

public static UInt32 GenerateCRC_32_from_Table(byte[] message)
    {
        UInt32 remainder = 0xFFFFFFFF;

        foreach (byte msgByte in message)
        {
            byte reversedMsgByte = Reverse(msgByte);
            remainder = (remainder << 8) ^ crc32_table[((remainder >> 24) ^ Convert.ToUInt32(reversedMsgByte)) & 0xFF];
        }

        remainder = Reverse(~remainder);
        return remainder;
    }

Reverse() and poly32 as mentioned in comments:**

    const UInt32 poly32 = 0x04C11DB7;

    public static UInt32 Reverse(UInt32 message)
    {
        UInt32 msgReversed = 0;
        for (int i = 0; i < 32; i++)
        {
            msgReversed = ((message & 0x80000000) >> (31 - i)) | msgReversed;
            message = message << 1;
        }
        return msgReversed;
    }

    public static byte Reverse(byte message)
    {
        byte msgReversed = 0;
        for (int i = 0; i < 8; i++)
        {
            msgReversed = (byte)(((byte)((byte)(message) & 0x80) >> (7 - i)) | msgReversed);
            message = (byte)(message << 1);
        }
        return msgReversed;
    }
1
c#crccrc32
What does Reverse do? I don't see any code for that. – Mark Adler
Also you didn't define poly32. – Mark Adler
Thank you for your reply. Sorry i don't have the code now, since i am in a different place, will paste the code which i used for reverse in couple of days. The Reverse() just reflects the binary data, you can see an example usage of Reverse in my output. XOR ^ 0xFFFFFFFF : 11011000011000011001111111100011(D8619FE3) Reversed the Abv : 11000111111110011000011000011011(C7F9861B). Also sorry for not defining 'poly32', i renamed 'poly' in my first example into 'poly32' so 'const UInt32 poly32 = 0x04C11DB7;' is the definition. Thanks! – Titus
@Mark Adler I have updated the question with details. Thanks! – Titus

1 Answers

5
votes

The standard CRC you are referring to is reflected, i.e. the bits are reversed, and it is initialized with 0xfffffff and the final CRC is exclusive-or'ed with 0xffffffff.

You are generating the CRC with the bits not reversed, with the initial CRC being zero, and with no exclusive-or at the end.

Generally to implement a bit-reversed CRC, you leave the input bytes as is, but reflect the polynomial and shift in the other direction. The input bytes are fed into the bottom of the CRC instead of the top. This also reduces the total number of bytes to be processed by four over an augmented message approach.

Update for updated question:

The code in the question attempts to "augment" the message, but then does not even use the augmentation. Instead it uses the data starting at offset 4, which is equivalent to using the original message from offset 0.

What should be done instead is to not even try to augment the message, and exclusive-or the message into the top of the CRC instead of trying to feed the message into the bottom of the CRC.

Furthermore, reversing the CRC, applying the message reversed, and then reversing the CRC again is equivalent to doing none of that, and instead to reverse the polynomial and shift in the other direction. The polynomial is a constant, so the reversal is done when writing the code, as noted in my original answer. 0x04c11db7 reversed is 0xedb88320.

So the code ends up looking like this (in C):

#include <stddef.h>
#include <stdint.h>

/* CRC-32 (Ethernet, ZIP, etc.) polynomial in reversed bit order. */
#define POLY 0xedb88320

/* Compute CRC of buf[0..len-1] with initial CRC crc.  This permits the
   computation of a CRC by feeding this routine a chunk of the input data at a
   time.  The value of crc for the first chunk should be zero. */
uint32_t crc32(uint32_t crc, const unsigned char *buf, size_t len)
{
    int k;

    crc = ~crc;
    while (len--) {
        crc ^= *buf++;
        for (k = 0; k < 8; k++)
            crc = crc & 1 ? (crc >> 1) ^ POLY : crc >> 1;
    }
    return ~crc;
}