Why is CRC16 calculation so slow?

Question

I have the following CRC function:

public static ushort ComputeCRC16(byte[] data)
{
    ushort i, j, crc = 0;
    int size = data.Length;

    for (i = 0; i < size - 2; i++)
    {
        crc ^= (ushort)(data[i] << 8);

        for (j = 0; j < 8; j++)
        {
            if ((crc & 0x8000) != 0) /* Test for bit 15 */
            {
                crc = (ushort)((crc << 1) ^ 0x1234); /* POLYNOMIAL */
            }
            else
            {
                crc <<= 1;
            }
        }
    }

    return crc;
}

I have been trying to use it to calculate a CRC16 from a file that is around 800 Kb, but it takes forever, I mean after five minutes, the value of i was still at around 2 000, and it should go up to 800 000.

Can someone give me an explanation on why it is so slow and what I can do to solve this issue ?

I'm working with Visual Studio 2015 on a i7 processor and the computer is not old nor broken.

I thing the compiler overcomplicates the optimization, the code looks solid enough; try adding [MethodImpl(MethodImplOptions.AggressiveInlining)] to the function, it might help — zedling
I don't see there any problem, that should cause such a slow speed. In standard implementation a pre-build table is used and whole bytes are processed at once (not per bit, as it is here). The current implementation should be slow, but IMHO not this slow. — Julo
@TheGeneral Kb, sorry french speaker here (o is for octet, which means byte) — Martin Verjans

xanatos xanatos · Accepted Answer · 2018-05-15T09:22:26

Replace the first lines with:

int i, j;
ushort crc = 0;

You were using a ushort for the for counter, but if size > 65535, the for cycle won't ever end.

The reason for this is that C# by default does not throw an Exception if an overflow occurs but just "silently" ignores it. Checkout the following code for a demonstration:

ushort i = ushort.MaxValue; //65535  
i++; //0

Why is CRC16 calculation so slow?

1 Answers