On CRCs and CRC Reverse Engineering

Last week I ran into this interesting CRC Reverse Engineering challenge at Stackoverflow. I immediately felt this is something I should be able to figure out using our Docklight Scripting tool, and indeed I managed to find the correct CRC within two hours.

(Update 2016 - the Docklight CRC Finder also found the answer for this second CRC puzzle.)

Now here are my personal sentiments about CRC:

The fact that the most frequently cited reference is called A Painless Guide to CRC Error Detection Algorithms only proves - it's painful. It really is.

So if you are with CRC aches, too, here is my personal list of painkillers on the subject:

• Sven Reifegerte's great Online CRC Calculator and his related C sample implementations.
• A somewhat comforting article about CRC Implementation Code in C. This article was originally called "Easier said than done (Michael Barr) - A guide to CRC calculation", and I much respect the honesty. 
• The Boost CRC Library documenation and code, which seems to be based on Michael Barr's expertise. 
• And, in fact, our nice Docklight CRC calculator, where we tried to include all common CRC8/CRC16/CRC32 flavors as a preset. The CRC calculation algorithm is basically according to Sven's C example and looks as listed below.
• BTW - this Python CRC solver looks really interesting, but I haven't found time yet to test it myself.

Here's our Docklight CRC calculation code:

// Generic, not table-based CRC calculation 
// Based on and credits to the following:
// CRC tester v1.3 written on 4th of February 2003 by Sven Reifegerste (zorc/reflex)

unsigned long reflect (unsigned long crc, int bitnum) {

    // reflects the lower 'bitnum' bits of 'crc'
    unsigned long i, j=1, crcout=0;
    for (i=(unsigned long)1<<(bitnum-1); i; i>>=1) {
        if (crc & i) crcout|=j;
        j<<= 1;
    }
    return (crcout);
}    

calcCRC(
    const int width, const unsigned long polynominal, const unsigned long initialRemainder, 
    const unsigned long finalXOR, const int reflectedInput, const int reflectedOutput, 
    const unsigned char message[], const long startIndex, const long endIndex) 
{ 
    // Ensure the width is in range: 1-32 bits
    assert(width >= 1 && width <= 32);  
    // some constant parameters used
    const bool b_refInput = (reflectedInput > 0); 
    const bool b_refOutput = (reflectedOutput > 0); 
    const unsigned long crcmask = ((((unsigned long)1<<(width-1))-1)<<1)|1;
    const unsigned long crchighbit = (unsigned long)1<<(width-1);

    unsigned long j, c, bit;
    unsigned long crc = initialRemainder;

    for (long msgIndex = startIndex; msgIndex <= endIndex; ++msgIndex) {
        c = (unsigned long)message[msgIndex];
        if (b_refInput) c = reflect(c, 8);
        for (j=0x80; j; j>>=1) {
            bit = crc & crchighbit;
            crc<<= 1;
            if (c & j) bit^= crchighbit;
            if (bit) crc^= polynominal;
        }
    }   
    if (b_refOutput) crc=reflect(crc, width);
    crc^= finalXOR;
    crc&= crcmask;
    return(crc);
}