CRC-32算法是如何工作的？
CRC-32算法是如何工作的？
提问于 2013-11-12 00:21:41
在对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
Stack Overflow用户
发布于 2013-11-12 00:28:50
CRC-32算法将输入视为以2为基数的大多项式，每个输入比特都是x的一次幂的系数，例如，最后一比特是x^0的系数，倒数第二比特是x^1的系数，依此类推。
这个多项式除以生成多项式，生成多项式的次数是32 (即最高幂是x^32)。所有的计算都是在域GF(2)上的多项式环中进行的。在使用中有不同的生成器多项式，因此实际上并不只有一种CRC-32算法。它们在其他方面也不同(例如，位顺序)。
CRC-32值是该多项式除法的余数，即最高次数为31的多项式，同样由其系数的比特表示。
Stack Overflow用户
发布于 2013-11-12 00:54:02
这看起来不太对劲：
if ( ( crc & 0x80000000 ) != 0 )
crc ^= POLYNOMIAL;
crc = ( crc << 1 ) | msgBit;您需要在移位前测试crc高位，但在移位和插入消息位之后对多项式的其余部分进行异或运算。
请注意，实际的多项式是0x104C11DB7，位32中的1取消了0x80000000 << 1 (测试证明已设置)
Stack Overflow用户
发布于 2013-11-12 03:39:12
在archivers等文件中使用的代码看起来像这样：
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;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/19911060
复制相关文章
相似问题
腾讯云开发者
