CRC - 32 (IEEE)

In our Data Communication Lab, we were supposed to write a CRC-32 implementation with C/C++. CRC stands for cyclic redundancy check, which is an error detection algorithm based on modulo-2 division. We used IEEE 32 bit polynomial 0x04C11DB7 to generate CRC-32 of a given string, and recheck it against the generated CRC whether an error occurred or not.

However, we looked for it in the net but could not find much information about it, probably because many languages (like php) already include functions as a built-in library to generate CRC checksum. So, I guess, people don't do these stuffs with C/C++ anymore.

The first tricky thing about generating CRC-32 is the polynomial is of 33 bits, which is an unnatural size for computers as it will need longer data type. However, after a slight observation, it becomes clear that, the 33th bit (or msb) is always 1 and thus, this is not present in the polynomial, rather, it is handled by the algorithm itself. Following the algorithm, the msb will be always 0 after we perform the XOR operation, and shifted out from the remainder. For this reason, we do not waste a bit to store that value, or add complexity to the code.

Here is my implementation goes, it is not very efficient, because, most of the implementations I have found later on in internet, use look-up tables to speed up the generation. However, this is quite simple and follow the algorithm straight:

/*
zobayer hasan
03/03/2011
*/

#include <cstdio>
#include <cstring>
using namespace std;

typedef unsigned int int32;

// key is the crc-32 ieee 802.3 standard polynomial
const int32 poly = 0x04C11DB7;
const int MAXLEN = 1024;

int32 reflect(int32 data, int bits) {
    int32 ret = 0;
    for(int i = bits-1; i>=0; i--) {
        if(data & 1) ret |= (1 << i);
        data >>= 1;
    }
    return ret;
}

int32 crc32(char* msg, int len) {
    int32 crc = 0xffffffff;
    int i, j;
    for(i = 0; i < len; i++) {
        crc ^= ((char)reflect(msg[i], 8) << 24);
        for(j = 8; j; j--) {
            crc = (crc << 1) ^ ((crc & 0x80000000) ? poly : 0x0);
        }
    }
    return reflect(crc, 32) ^ 0xffffffff;
}

int main() {
    int32 crc;
    int len;
    char msg[MAXLEN];

    gets(msg);
    len = strlen(msg);

    // generate crc32 for msg
    crc = crc32(msg, len);
    printf("CRC: 0x%08X\n", crc);
 
    return 0;
}

Here, reflect() just reverses the 'bits' number of lsb (from right) bits from 'data' passed to it.

Now, how to check consistency? It is simple, before sending message over ports, we generate the CRC and pass it with original message, in receiver end, the CRC is appended with the message and then it generates CRC again, this time, if now error has occurred, CRC will be 0.

Ahh, quite short code :)