CODEWITHSUNDEEP
algorithmcrc
Dennis
Dennis

Reputation: 333

How does the CRC-32 algorithm work?

After doing some research on the CRC-32 algorithm, I got to the following:

/* Usage: Recursively call this with previous crc. Start with crc = 0. */
#define POLYNOMIAL 0x04C11DB7

unsigned int crc32( unsigned int crc, char* msg, unsigned int len ) {
  for ( unsigned int byteNum = 0; byteNum < len; byteNum++ ) {
    char msgByte = msg[ byteNum ];

    for ( unsigned int bitNum = 0; bitNum < 8; bitNum++ ) {
      char msgBit = ( msgByte >> ( 7 - bitNum ) ) & 0x1;

      if ( ( crc & 0x80000000 ) != 0 )
        crc = ( ( crc << 1 ) | msgBit ) ^ POLYNOMIAL;
      else
        crc = ( crc << 1 ) | msgBit;
    }
  }
  return crc;
}

However the output of my code is totally different from those of commonly used CRC-32 functions ( Optimized with tables )

Now I hoped someone could give me example source code for the CRC-32 algorithm, which is not optimized by tables, and gives good insight in how it actually works.

Thanks,
Dennis

Upvotes: 2

Views: 5242

Answers (4)

Dennis
Dennis

Reputation: 333

I stumbled by coincidence on the following pdf: stigge.org/martin/pub/SAR-PR-2006-05.pdf
Page 18 contains my solution.

For some strange reason I shifted to the wrong side, and the polynomial should be reversed.

This is the code which gives me the correct output: 

/* Usage: Recursively call this with previous crc. Start with crc = 0. */

#define POLYNOMIAL 0xEDB88320

unsigned int crc32( unsigned int crc, char* msg, unsigned int len ) {
  crc ^= 0xFFFFFFFF;
  for ( unsigned int byteNum = 0; byteNum < len; byteNum++ ) {
    char msgByte = msg[ byteNum ];

    for ( unsigned int bitNum = 0; bitNum < 8; bitNum++ ) {
      if ( ( crc ^ msgByte ) & 1 )
        crc = ( crc >> 1 ) ^ POLYNOMIAL;
      else
        crc >>= 1;
      msgByte >>= 1;
    }
  }
  return crc ^ 0xFFFFFFFF;
}

Upvotes: 0

Shelwien
Shelwien

Reputation: 2200

The one used in archivers etc looks like this:

char msg[] = "hello, world!";
uint POLY = 0xEDB88320;

int main( void ) {
  uint i,j,l,x;
  l = sizeof(msg)-1;
  x = 0;
  for( i=0; i<l; i++ ) {
     x = x ^ msg[i];
     for( j=0; j<8; j++ ) {
       x = (x>>1) ^ 0x80000000 ^ ((~x&1)*POLY);
     }
  }
  printf( "crc32(\"%s\")=%08X\n", msg, x );
}

http://rextester.com/EHM45452

Or alternatively

x = 0;
for( i=0; i<l; i++ ) {
   x = x ^ (msg[i]^0xFF);
   for( j=0; j<8; j++ ) {
     x = (x>>1) ^ ((x&1)*POLY);
   }
   x ^= 0xFF000000;
}

Upvotes: 1

Ben Voigt
Ben Voigt

Reputation: 283614

This doesn't look right:

if ( ( crc & 0x80000000 ) != 0 )
    crc ^= POLYNOMIAL;
crc = ( crc << 1 ) | msgBit;

You need to test the crc high bit before shifting, but xor the rest of the POLYNOMIAL after shifting and inserting the message bit.

Note that the actual polynomial is 0x104C11DB7, and that the 1 in bit 32 cancels 0x80000000 << 1 (which the test proved is set)

Upvotes: 1

Henry
Henry

Reputation: 43728

The CRC-32 algorithm considers the input as a big poynomial in base 2. Each input bit is the coefficient of one power of x. For example, the last bit is the coefficient of x^0, the last but one bit is the coefficient of x^1 and so on.

This polynomial is divided by the generator polynomial, which has degree 32 (i.e. the highest power is x^32). All calculations are performed in the ring of polynomials over the field GF(2). There are different generator polynomials in use, so there is not really only one CRC-32 algorithm. They also differ in other respects (for example bit order).

The CRC-32 value is the remainder of this polynomial division, a polynomial of at most degree 31, which is again represented by the bits of its coefficients.

Upvotes: 1

Related Questions