Cyclic redundancy check 32 checksum
From CodeCodex
A cyclic redundancy check (CRC) is a type of hash function used to produce a checksum - which is a small, fixed number of bits - against a block of data, such as a packet of network traffic or a block of a computer file. The checksum is used to detect errors after transmission or storage. A CRC is computed and appended before transmission or storage, and verified afterwards by recipient to confirm that no changes occurred on transit. CRCs are popular because they are simple to implement in binary hardware, are easy to analyze mathematically, and are particularly good at detecting common errors caused by noise in transmission channels.
Implementations[edit]
Pseudocode[edit]
Since a CRC is fundamentally bit-oriented, the order that you assign to bits in bytes matters. You can do it big-endian:
function crc(bit array bitString[1..len], int polynomial) { shiftRegister := initial value // commonly all 0 bits or all 1 bits for i from 1 to len { if most significant bit of shiftRegister xor bitString[i] = 1 { shiftRegister := (shiftRegister left shift 1) xor polynomial } else { shiftRegister := (shiftRegister left shift 1) } } return shiftRegister }
Or you can do it little-endian. This turns out to be more convenient in practice, and matches the order of bits sent over RS-232 (so the CRC burst error detection property holds):
function crc(bit array bitString[1..len], int polynomial) { shiftRegister := initial value // commonly all 0 bits or all 1 bits for i from 1 to len { if (least significant bit of shiftRegister) xor bitString[i] = 1 { shiftRegister := (shiftRegister right shift 1) xor polynomial } else { shiftRegister := (shiftRegister right shift 1) } } return shiftRegister }
There are two convenient optimizations:
- The bit bitString[i] can be simply XORed into the shiftRegister before the test. It gets shifted away in the next step anyway.
- The above can be thought of as looking up entry (shiftRegister & 1) in a two-entry table whose entries are 0 and polynomial You can do multiple bits at the same time with a larger table.
C[edit]
#include <stdio.h> static unsigned long *get_crc_table( unsigned long *crc_table ) { // First call to this function? Or after freeing the memory? if ( !crc_table ) { // Allocate memory crc_table = malloc(sizeof(unsigned long) * 256); // Was the allocation successful? if ( crc_table ) { // Generate the crc table unsigned long crc ; int i, j ; for(i = 0; i < 256; i++) { crc = i; for (j = 8; j > 0; j--) { if (crc & 1) crc = (crc >> 1) ^ 0xEDB88320UL; else crc >>= 1; } crc_table[i] = crc; } } } // Return the new pointer return crc_table ; } unsigned long get_crc32(const char *file) { static unsigned long *crc_table = NULL; unsigned long crc = 0; // Called with '0'? if (!file) { // If we have a crc table, delete it from memory free(crc_table); // Set it to a null pointer, the have it (re)created on next calls to this // function crc_table = NULL; } else { // Get the crc table, on first call, generate, otherwise do nothing crc_table = get_crc_table( crc_table ) ; // Do we have a crc table? if ( crc_table ) { // Open the file for reading FILE *fp = fopen(file, "r"); // Was the file open successful? if (fp) { // Calculate the checksum int ch; crc = 0xFFFFFFFFUL; while ((ch = getc(fp)) != EOF) { crc = (crc>>8) ^ crc_table[ (crc^ch) & 0xFF ]; } crc ^= 0xFFFFFFFFUL ; // Close the file fclose(fp); } } } // Return the checksum result return crc ; }