Broken CRC32 Combine

Question

I have a problem with a certain CRC method when trying to combine CRC's.

I have been using the combine CRC method and even adapted it a while ago to work with CRC16, etc. and I (hope?) understand how the filling of 0's work according to the answer here https://stackoverflow.com/a/23126768/5495036 with zlib's code

Thing is, I've been rapping my brain on how to get an operator that I can use as I am also working with a non standard CRC calculation. The original CRC calculation is based on the CRC32 0xEDB88320 polynomial for the lookup table but the calculation itself was broken, so instead of 256 byte lookup table looking like 0x00000000,0x77073096,0xee0e612c,0x990951ba,0x076dc419,0x706af48f,0xe963a535,... it now looks like this 0x00000000,0x96000000,0x30960000,0x07309600,0x77073096,0x2c770730,0x612c7707,... and the combine CRC uses the operator to be able to zero out the rest of the bits.

I can't change the calculation unfortunately so that idea is out :P Any ideas?

EDIT:

The calculation is standard, it just uses a table that has been built using the standard polynomial of 0xEDB88320 but building it incorrectly. Table is still 256 ints. Starting CRC of 0xFFFFFFFF

Complete class code

public static byte[] ByteLookupTable =
        {
        0x00,0x00,0x00,0x00,0x96,0x30,0x07,0x77,0x2C,0x61,0x0E,0xEE,0xBA,0x51,
        0x09,0x99,0x19,0xC4,0x6D,0x07,0x8F,0xF4,0x6A,0x70,0x35,0xA5,0x63,
        0xE9,0xA3,0x95,0x64,0x9E,0x32,0x88,0xDB,0x0E,0xA4,0xB8,0xDC,0x79,0x1E,
        0xE9,0xD5,0xE0,0x88,0xD9,0xD2,0x97,0x2B,0x4C,0xB6,0x09,0xBD,0x7C,
        0xB1,0x7E,0x07,0x2D,0xB8,0xE7,0x91,0x1D,0xBF,0x90,0x64,0x10,0xB7,0x1D,
        0xF2,0x20,0xB0,0x6A,0x48,0x71,0xB9,0xF3,0xDE,0x41,0xBE,0x84,0x7D,
        0xD4,0xDA,0x1A,0xEB,0xE4,0xDD,0x6D,0x51,0xB5,0xD4,0xF4,0xC7,0x85,0xD3,
        0x83,0x56,0x98,0x6C,0x13,0xC0,0xA8,0x6B,0x64,0x7A,0xF9,0x62,0xFD,
        0xEC,0xC9,0x65,0x8A,0x4F,0x5C,0x01,0x14,0xD9,0x6C,0x06,0x63,0x63,0x3D,
        0x0F,0xFA,0xF5,0x0D,0x08,0x8D,0xC8,0x20,0x6E,0x3B,0x5E,0x10,0x69,
        0x4C,0xE4,0x41,0x60,0xD5,0x72,0x71,0x67,0xA2,0xD1,0xE4,0x03,0x3C,0x47,
        0xD4,0x04,0x4B,0xFD,0x85,0x0D,0xD2,0x6B,0xB5,0x0A,0xA5,0xFA,0xA8,
        0xB5,0x35,0x6C,0x98,0xB2,0x42,0xD6,0xC9,0xBB,0xDB,0x40,0xF9,0xBC,0xAC,
        0xE3,0x6C,0xD8,0x32,0x75,0x5C,0xDF,0x45,0xCF,0x0D,0xD6,0xDC,0x59,
        0x3D,0xD1,0xAB,0xAC,0x30,0xD9,0x26,0x3A,0x00,0xDE,0x51,0x80,0x51,0xD7,
        0xC8,0x16,0x61,0xD0,0xBF,0xB5,0xF4,0xB4,0x21,0x23,0xC4,0xB3,0x56,
        0x99,0x95,0xBA,0xCF,0x0F,0xA5,0xBD,0xB8,0x9E,0xB8,0x02,0x28,0x08,0x88,
        0x05,0x5F,0xB2,0xD9,0x0C,0xC6,0x24,0xE9,0x0B,0xB1,0x87,0x7C,0x6F,
        0x2F,0x11,0x4C,0x68,0x58,0xAB,0x1D,0x61,0xC1,0x3D,0x2D,0x66,0xB6,0x90,
        0x41,0xDC,0x76,0x06,0x71,0xDB,0x01,0xBC,0x20,0xD2,0x98,0x2A,0x10,
        0xD5,0xEF,0x89,0x85,0xB1,0x71,0x1F,0xB5,0xB6,0x06,0xA5,0xE4,0xBF,0x9F,
        0x33,0xD4,0xB8,0xE8,0xA2,0xC9,0x07,0x78,0x34,0xF9,0x00,0x0F,0x8E,
        0xA8,0x09,0x96,0x18,0x98,0x0E,0xE1,0xBB,0x0D,0x6A,0x7F,0x2D,0x3D,0x6D,
        0x08,0x97,0x6C,0x64,0x91,0x01,0x5C,0x63,0xE6,0xF4,0x51,0x6B,0x6B,
        0x62,0x61,0x6C,0x1C,0xD8,0x30,0x65,0x85,0x4E,0x00,0x62,0xF2,0xED,0x95,
        0x06,0x6C,0x7B,0xA5,0x01,0x1B,0xC1,0xF4,0x08,0x82,0x57,0xC4,0x0F,
        0xF5,0xC6,0xD9,0xB0,0x65,0x50,0xE9,0xB7,0x12,0xEA,0xB8,0xBE,0x8B,0x7C,
        0x88,0xB9,0xFC,0xDF,0x1D,0xDD,0x62,0x49,0x2D,0xDA,0x15,0xF3,0x7C,
        0xD3,0x8C,0x65,0x4C,0xD4,0xFB,0x58,0x61,0xB2,0x4D,0xCE,0x51,0xB5,0x3A,
        0x74,0x00,0xBC,0xA3,0xE2,0x30,0xBB,0xD4,0x41,0xA5,0xDF,0x4A,0xD7,
        0x95,0xD8,0x3D,0x6D,0xC4,0xD1,0xA4,0xFB,0xF4,0xD6,0xD3,0x6A,0xE9,0x69,
        0x43,0xFC,0xD9,0x6E,0x34,0x46,0x88,0x67,0xAD,0xD0,0xB8,0x60,0xDA,
        0x73,0x2D,0x04,0x44,0xE5,0x1D,0x03,0x33,0x5F,0x4C,0x0A,0xAA,0xC9,0x7C,
        0x0D,0xDD,0x3C,0x71,0x05,0x50,0xAA,0x41,0x02,0x27,0x10,0x10,0x0B,
        0xBE,0x86,0x20,0x0C,0xC9,0x25,0xB5,0x68,0x57,0xB3,0x85,0x6F,0x20,0x09,
        0xD4,0x66,0xB9,0x9F,0xE4,0x61,0xCE,0x0E,0xF9,0xDE,0x5E,0x98,0xC9,
        0xD9,0x29,0x22,0x98,0xD0,0xB0,0xB4,0xA8,0xD7,0xC7,0x17,0x3D,0xB3,0x59,
        0x81,0x0D,0xB4,0x2E,0x3B,0x5C,0xBD,0xB7,0xAD,0x6C,0xBA,0xC0,0x20,
        0x83,0xB8,0xED,0xB6,0xB3,0xBF,0x9A,0x0C,0xE2,0xB6,0x03,0x9A,0xD2,0xB1,
        0x74,0x39,0x47,0xD5,0xEA,0xAF,0x77,0xD2,0x9D,0x15,0x26,0xDB,0x04,
        0x83,0x16,0xDC,0x73,0x12,0x0B,0x63,0xE3,0x84,0x3B,0x64,0x94,0x3E,0x6A,
        0x6D,0x0D,0xA8,0x5A,0x6A,0x7A,0x0B,0xCF,0x0E,0xE4,0x9D,0xFF,0x09,
        0x93,0x27,0xAE,0x00,0x0A,0xB1,0x9E,0x07,0x7D,0x44,0x93,0x0F,0xF0,0xD2,
        0xA3,0x08,0x87,0x68,0xF2,0x01,0x1E,0xFE,0xC2,0x06,0x69,0x5D,0x57,
        0x62,0xF7,0xCB,0x67,0x65,0x80,0x71,0x36,0x6C,0x19,0xE7,0x06,0x6B,0x6E,
        0x76,0x1B,0xD4,0xFE,0xE0,0x2B,0xD3,0x89,0x5A,0x7A,0xDA,0x10,0xCC,
        0x4A,0xDD,0x67,0x6F,0xDF,0xB9,0xF9,0xF9,0xEF,0xBE,0x8E,0x43,0xBE,0xB7,
        0x17,0xD5,0x8E,0xB0,0x60,0xE8,0xA3,0xD6,0xD6,0x7E,0x93,0xD1,0xA1,
        0xC4,0xC2,0xD8,0x38,0x52,0xF2,0xDF,0x4F,0xF1,0x67,0xBB,0xD1,0x67,0x57,
        0xBC,0xA6,0xDD,0x06,0xB5,0x3F,0x4B,0x36,0xB2,0x48,0xDA,0x2B,0x0D,
        0xD8,0x4C,0x1B,0x0A,0xAF,0xF6,0x4A,0x03,0x36,0x60,0x7A,0x04,0x41,0xC3,
        0xEF,0x60,0xDF,0x55,0xDF,0x67,0xA8,0xEF,0x8E,0x6E,0x31,0x79,0xBE,
        0x69,0x46,0x8C,0xB3,0x61,0xCB,0x1A,0x83,0x66,0xBC,0xA0,0xD2,0x6F,0x25,
        0x36,0xE2,0x68,0x52,0x95,0x77,0x0C,0xCC,0x03,0x47,0x0B,0xBB,0xB9,
        0x16,0x02,0x22,0x2F,0x26,0x05,0x55,0xBE,0x3B,0xBA,0xC5,0x28,0x0B,0xBD,
        0xB2,0x92,0x5A,0xB4,0x2B,0x04,0x6A,0xB3,0x5C,0xA7,0xFF,0xD7,0xC2,
        0x31,0xCF,0xD0,0xB5,0x8B,0x9E,0xD9,0x2C,0x1D,0xAE,0xDE,0x5B,0xB0,0xC2,
        0x64,0x9B,0x26,0xF2,0x63,0xEC,0x9C,0xA3,0x6A,0x75,0x0A,0x93,0x6D,
        0x02,0xA9,0x06,0x09,0x9C,0x3F,0x36,0x0E,0xEB,0x85,0x67,0x07,0x72,0x13,
        0x57,0x00,0x05,0x82,0x4A,0xBF,0x95,0x14,0x7A,0xB8,0xE2,0xAE,0x2B,
        0xB1,0x7B,0x38,0x1B,0xB6,0x0C,0x9B,0x8E,0xD2,0x92,0x0D,0xBE,0xD5,0xE5,
        0xB7,0xEF,0xDC,0x7C,0x21,0xDF,0xDB,0x0B,0xD4,0xD2,0xD3,0x86,0x42,
        0xE2,0xD4,0xF1,0xF8,0xB3,0xDD,0x68,0x6E,0x83,0xDA,0x1F,0xCD,0x16,0xBE,
        0x81,0x5B,0x26,0xB9,0xF6,0xE1,0x77,0xB0,0x6F,0x77,0x47,0xB7,0x18,
        0xE6,0x5A,0x08,0x88,0x70,0x6A,0x0F,0xFF,0xCA,0x3B,0x06,0x66,0x5C,0x0B,
        0x01,0x11,0xFF,0x9E,0x65,0x8F,0x69,0xAE,0x62,0xF8,0xD3,0xFF,0x6B,
        0x61,0x45,0xCF,0x6C,0x16,0x78,0xE2,0x0A,0xA0,0xEE,0xD2,0x0D,0xD7,0x54,
        0x83,0x04,0x4E,0xC2,0xB3,0x03,0x39,0x61,0x26,0x67,0xA7,0xF7,0x16,
        0x60,0xD0,0x4D,0x47,0x69,0x49,0xDB,0x77,0x6E,0x3E,0x4A,0x6A,0xD1,0xAE,
        0xDC,0x5A,0xD6,0xD9,0x66,0x0B,0xDF,0x40,0xF0,0x3B,0xD8,0x37,0x53,
        0xAE,0xBC,0xA9,0xC5,0x9E,0xBB,0xDE,0x7F,0xCF,0xB2,0x47,0xE9,0xFF,0xB5,
        0x30,0x1C,0xF2,0xBD,0xBD,0x8A,0xC2,0xBA,0xCA,0x30,0x93,0xB3,0x53,
        0xA6,0xA3,0xB4,0x24,0x05,0x36,0xD0,0xBA,0x93,0x06,0xD7,0xCD,0x29,0x57,
        0xDE,0x54,0xBF,0x67,0xD9,0x23,0x2E,0x7A,0x66,0xB3,0xB8,0x4A,0x61,
        0xC4,0x02,0x1B,0x68,0x5D,0x94,0x2B,0x6F,0x2A,0x37,0xBE,0x0B,0xB4,0xA1,
        0x8E,0x0C,0xC3,0x1B,0xDF,0x05,0x5A,0x8D,0xEF,0x02,0x2D,0xC3,0x8D,0x40,0x00
        };

    protected void BuildLookupTable()
    {
        if (LookupTable == null)
        {
            LookupTable = new uint[256];
            for (int i = 0; i < LookupTable.Length; i++)
            {
                LookupTable[i] = BitConverter.ToUInt32(ByteLookupTable, i);
            }
        }
    }

    protected override uint CalculateBuffer(byte[] buffer, uint crc, int startPos, int endPos)
    {
        for (int i = 0; i < endPos; i++)
        {
            crc = LookupTable[(crc ^ buffer[i]) & 0xff] ^ (crc >> 8);
        }
        return crc;
    }

What does "the calculation was broken" mean? Is it even a CRC? You would need to show the code for this broken CRC to even have a dim hope of getting an answer. — Mark Adler, Jul 15 '20 at 07:31
CRC calculation is standard, just the lookup table is broken. I'll add the code — VenoMpie, Jul 15 '20 at 07:39
If the lookup table is broken, it's probably not generating a proper CRC. How well it detects errors is unknown without seeing the broken table and how it was generated. Why are you not able to use a corrected CRC table? — rcgldr, Jul 15 '20 at 20:31
I don't have the original data, only CRC's. Legacy systems ;) And this CRC is so broken, constantly get conflicts with this algorithm but it is what it is — VenoMpie, Jul 15 '20 at 21:21
@VenoMpie - "only CRC's"? So you have data + CRC stored somewhere using the bad table? To check it, you'll need to use the bad table again, and it may not be that good for error detection due to the table being bad. You could do a one time pass reading the old data with bad CRC, generating a correct CRC and writing the now corrected data to new files. — rcgldr, Jul 16 '20 at 03:20
I fully understand that I can do that ... but it's a bit more complicated than that. Old CRC's are in SFV's and the data compared against it changes all the time, once a set of CRC's are found, they are removed and onto the next set. So it's not a case of doing a one time pass to correct it as I only need to find the correct data then I won't use that set again — VenoMpie, Jul 16 '20 at 06:42

Mark Adler · Answer 1 · 2020-07-15T23:48:22.043

1

The lookup table constants are correct for that polynomial, but apparently the conversion done by BuildLookupTable() is totally messed up. It would have been easy to rewrite the table to avoid needing BuildLookupTable().

What follows is from the original answer, which assumed that the table was converted correctly. Which it isn't.

As it is, this isn't a CRC, so the combination approach for a CRC does not apply here.

The one thing missing from your definition is what the initial value for the CRC is, and possibly if there is an exclusive-or done on the final CRC. That polynomial is the same as used by zlib, PKZIP, etc., where the initial CRC value is 0xffffffff and the final exclusive-or is with 0xffffffff. That CRC is referred to as CRC-32/ISO-HDLC.

Whatever your initial and the final exclusive-or values are, if they are equal, then you can use the crc32_combine() function from zlib as is. If they are not, you can still use crc32_combine(), but you need to exclusive-or the input and output CRC values of that function with the exclusive-or of the initial and final exclusive-or values.

edited Jul 15 '20 at 23:48

answered Jul 15 '20 at 18:53

Mark Adler

101,978
13
118
158

Thanks :). The initial CRC is `0xffffffff` and the final CRC is xor'ed. I might not understand you properly or I didn't explain properly. If you look quickly at the table bytes then yes, all those bytes are part of the correct CRC-32/ISO-HDLC table but when this lookup table is built then it completely discards all the bytes after 259 as it takes 3 bytes + 1 the whole time instead of 4 bytes++ – VenoMpie Jul 15 '20 at 20:53
e.g. with a calculation for a single byte value of `0xfe` Correct Calculation `LookupTable[0x00000001] ^ 0x00ffffff = 0x77073096 ^ 0x00ffffff = 0x77f8cf69 XOR = 0x88073096` Incorrect Calculation `LookupTable[0x00000001] ^ 0x00ffffff = 0x96000000 ^ 0x00ffffff = 0x96ffffff XOR = 0x69000000` – VenoMpie Jul 15 '20 at 20:55
Ah. I was assuming that the table conversion was being done correctly. I did not bother to look up what `BitConverter.ToUInt32` does. – Mark Adler Jul 15 '20 at 20:55
Are you using a correct table? If not, then it isn't a CRC to begin with. – Mark Adler Jul 15 '20 at 20:56
Correct table. I know it's not proper CRC because of that but this is unfortunately the table that I have to use otherwise the CRC's don't match that's why I am struggling as I have to calculate 20+mb across constantly even though only about 100 bytes in the beginning changes. I only have CRC's to work with unfortunately, otherwise it would have been easy just to recalculate the original data with the correct method and match against that ;) – VenoMpie Jul 15 '20 at 21:20

Broken CRC32 Combine

1 Answers1