3

I was trying to implement my own CRC32 function in C#. I saw an elegant solution in JS here JavaScript CRC32 So I came up with this:

internal static class Crc32
    {
        internal static long CalculateCrc32(string str)
        {
            long[] crcTable = Crc32.MakeCrcTable();
            long crc = 0 ^ (-1);

            for (int i = 0; i < str.Length; i++)
            {
                char c = str[i];
                crc = (crc >> 8) ^ crcTable[(crc ^ c) & 0xFF];
            }

            return ~crc; //(crc ^ (-1)) >> 0;
        }

        internal static long[] MakeCrcTable()
        {
            long c;
            long[] crcTable = new long[256];
            for (int n = 0; n < 256; n++)
            {
                c = n;
                for (int k = 0; k < 8; k++)
                {
                    var res = c & 1;
                    c = (res == 1) ? (0xEDB88320 ^ (c >> 1)) : (c >> 1);
                }
                crcTable[n] = c;
            }

            return crcTable;
        }
    }

The problem is that my solution does not return the same result. Console.WriteLine(Crc32.CalculateCrc32("l")); results in 1762050814 while the JS function produces 2517025534. The JS result is also the correct one. What am I doing wrong?

Community
  • 1
  • 1
Cyan
  • 1,068
  • 1
  • 12
  • 31
  • Are you sure you linked the right question? The one you linked is about a char code, not a JS CRC... – Ron Beyer Jun 26 '15 at 15:29
  • Can you not debug this to find the problem? Dump the CRC table and see if it matches. Dump the CRC after each calculation and see when they diverge, etc. We don't even have your reference implementation to compare against... Also google shows up many c# implementations that you could probably compare yours against to find the problem. – Chris Jun 26 '15 at 15:31
  • 1
    One thing that immediately makes me wonder is whether it is correct you are using Int64 to calcuate a CRC32? The name suggests 32 bit as does the implementation here: http://sanity-free.org/12/crc32_implementation_in_csharp.html – Chris Jun 26 '15 at 15:35
  • yes, it was the type. changed to uint and it works. – Cyan Jun 26 '15 at 15:41

1 Answers1

3

The problem here is that you are using the wrong datatype. I'm not familiar with the CRC32 algorithm so I googled to find http://sanity-free.org/12/crc32_implementation_in_csharp.html as a reference implementation.

the first thing I noticed is that they are using uint instead of long. This makes sense as I'd assume the 32 in CRC32 means that it would return a 32 bit number. long is a 64 bit signed int.

If you change all the long for uint then we nearly get a working program. The only line that won't work is c=n because it can't implicitly convert an int (n) to a uint (c). However since we know n is always going to be a positive integer we can just change n to be of type uint as well.

This leaves me with:

internal static uint CalculateCrc32(string str)
{
    uint[] crcTable = Crc32.MakeCrcTable();
    uint crc = 0xffffffff;
    for (int i = 0; i < str.Length; i++)
    {
        char c = str[i];
        crc = (crc >> 8) ^ crcTable[(crc ^ c) & 0xFF];
    }

    return ~crc; //(crc ^ (-1)) >> 0;
}

internal static uint[] MakeCrcTable()
{
    uint c;
    uint[] crcTable = new uint[256];
    for (uint n = 0; n < 256; n++)
    {
        c = n;
        for (int k = 0; k < 8; k++)
        {
            var res = c & 1;
            c = (res == 1) ? (0xEDB88320 ^ (c >> 1)) : (c >> 1);
        }
        crcTable[n] = c;
    }

    return crcTable;
}

With this code Console.WriteLine(Crc32.CalculateCrc32("l")); displays 2517025534 as expected.

Chris
  • 27,210
  • 6
  • 71
  • 92