checksum calculation

Question

To calculate CRC I found a piece of code but I am not understanding the concept. Here is the code:

count =128 and ptr=some value;

calcrc(unsigned char *ptr, int count)
{
    unsigned short  crc;
    unsigned char i;

    crc = 0;

    while (--count >= 0)
    {
        crc = crc ^ (unsigned short)*ptr++ << 8;
        i = 8;
        do
        {
            if (crc & 0x8000)
                crc = crc << 1 ^ 0x1021;
            else
                crc = crc << 1;
        } while(--i);
    }
    return (crc);
}

Please any body explain and tell me the logic.

Answer 1

This looks like a CRC (specifically it looks like CRC-16-CCITT, used by things like 802.15.4, X.25, V.41, CDMA, Bluetooth, XMODEM, HDLC, PPP and IrDA). You might want to read up on the CRC theory on the linked-to Wikipedia page, to gain some more insight. Or you can view this as a "black box" that just solves the problem of computing a checksum.

Answer 2

You will probably need to know that in C, the ^ operator is a bitwise XOR operator and the << operator is the left shift operator (equivalent to multiplication by 2 to the power of the number on the right of the operator). Also the crc & 0x8000 expression is testing for the most significant bit set of the variable crc. This will help you to work out a low level explanation of what is occurring when this runs, for a high level explanation of what a CRC is and why you might need it, read the Wikipedia page or How Stuff Works.

Answer 3

One famous text on CRCs is "A Painless Guide to CRC Error Detection Algorithms" by Ross Williams. It takes some time to absorb but it's pretty thorough.

Answer 4

Take a look at my answer to http://stackoverflow.com/questions/149617/how-could-i-guess-a-checksum-algorithm/158693#158693