2

在对 CRC-32 算法做了一些研究之后，我得到了以下结论：

/* 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;
}

但是我的代码的输出与常用的 CRC-32 函数的输出完全不同（用表格优化）

现在我希望有人能给我 CRC-32 算法的示例源代码，该算法没有通过表格进行优化，并且可以很好地了解它的实际工作原理。

谢谢，
丹尼斯

4

4 回答 4

1

归档器等中使用的一个如下所示：

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

或者，

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;
}
于 2013-11-11T19:39:11.737 回答
1

这看起来不对：

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

您需要在移位之前测试高位，但在移位和插入消息位之后crc对 POLYNOMIAL 的其余部分进行异或。

请注意，实际多项式是0x104C11DB7，并且第 32 位中的 1 取消0x80000000 << 1（测试证明已设置）

于 2013-11-11T16:54:01.737 回答
1

CRC-32 算法将输入视为以 2 为底的大多项式。每个输入位是 x 的一次幂的系数。例如，最后一位是x^0的系数，最后一位是x^1的系数，依此类推。

该多项式除以生成多项式，生成多项式的次数为 32（即最高幂为 x^32）。所有的计算都是在多项式环中在 GF(2) 域上进行的。使用了不同的生成多项式，因此实际上并不只有一种 CRC-32 算法。它们在其他方面也不同（例如位顺序）。

CRC-32 值是该多项式除法的余数，最多为 31 次的多项式，再次由其系数的位表示。

于 2013-11-11T16:28:50.183 回答
0

我偶然发现了以下 pdf：stigge.org/martin/pub/SAR-PR-2006-05.pdf
第 18 页包含我的解决方案。

出于某种奇怪的原因，我移到了错误的一侧，多项式应该颠倒过来。

这是给我正确输出的代码： 

/* 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;
}
于 2013-11-11T20:22:30.677 回答