不久前写一程序时要用到 CRC-16 ，但找来找去只在 UDDF 里找到一个 Delphi 的 CRC-32 程序代码，而且是用查表法，虽然说查表法速度快，但 256 项 32 位数据我怀疑可能会有输入错误， 让人不是那么放心，而我又不知道这个表是怎么算出来的。后来我又在一本两年前的笔记本里找到一段关于 CRC 的内容， 也不知是从哪里抄来的，还好里面有一段程序代码，是 CRC-16 的，这段程序正是产生 CRC 表的，可是这区区几行的程序（基本上与下面的 BuilderTable16 函数相同）看得我一头雾水，直到这两天才弄明白， 并据此推出 CRC-32 的算法，现将全部程序列在下面，并作一些说明以助于理解，不但要知其然，还要知其所以然嘛：
// 注意：因最高位一定为“1”，故略去
const unsigned short cnCRC_16 = 0x8005;
// CRC-16 = X16 + X15 + X2 + X0
const unsigned short cnCRC_CCITT = 0x1021;
// CRC-CCITT = X16 + X12 + X5 + X0，据说这个 16 位 CRC 多项式比上一个要好
const unsigned long cnCRC_32 = 0x04C10DB7;
// CRC-32 = X32 + X26 + X23 + X22 + X16 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + X0
unsigned long Table_CRC[256]; // CRC 表
// 构造 16 位 CRC 表
void BuildTable16( unsigned short aPoly )
{
unsigned short i, j;
unsigned short nData;
unsigned short nAccum;
for ( i = 0; i < 256; i++ )
{
nData = ( unsigned short )( i << 8 );
nAccum = 0;
for ( j = 0; j < 8; j++ )
{
if ( ( nData ^ nAccum ) & 0x8000 )
nAccum = ( nAccum << 1 ) ^ aPoly;
else
nAccum <<= 1;
nData <<= 1;
}
Table_CRC[i] = ( unsigned long )nAccum;
}
}
// 计算 16 位 CRC 值，CRC-16 或 CRC-CCITT
unsigned short CRC_16( unsigned char * aData, unsigned long aSize )
{
unsigned long i;
unsigned short nAccum = 0;
BuildTable16( cnCRC_16 ); // or cnCRC_CCITT
for ( i = 0; i < aSize; i++ )
nAccum = ( nAccum << 8 ) ^ ( unsigned short )Table_CRC[( nAccum >> 8 ) ^ *aData++];
return nAccum;
}
// 构造 32 位 CRC 表
void BuildTable32( unsigned long aPoly )
{
unsigned long i, j;
unsigned long nData;
unsigned long nAccum;
for ( i = 0; i < 256; i++ )
{
nData = ( unsigned long )( i << 24 );
nAccum = 0;
for ( j = 0; j < 8; j++ )
{
if ( ( nData ^ nAccum ) & 0x80000000 )
nAccum = ( nAccum << 1 ) ^ aPoly;
else
nAccum <<= 1;
nData <<= 1;
}
Table_CRC[i] = nAccum;
}
}
// 计算 32 位 CRC-32 值
unsigned long CRC_32( unsigned char * aData, unsigned long aSize )
{
unsigned long i;
unsigned long nAccum = 0;
BuildTable32( cnCRC_32 );
for ( i = 0; i < aSize; i++ )
nAccum = ( nAccum << 8 ) ^ Table_CRC[( nAccum >> 24 ) ^ *aData++];
return nAccum;
}
说明：CRC 的计算原理如下（一个字节的简单例子）
11011000 00000000 00000000 <- 一个字节数据, 左移 16b
^10001000 00010000 1 <- CRC-CCITT 多项式, 17b
--------------------------
1010000 00010000 10 <- 中间余数
^1000100 00001000 01
-------------------------
10100 00011000 1100
^10001 00000010 0001
-----------------------
101 00011010 110100
^100 01000000 100001
---------------------
1 01011010 01010100
^1 00010000 00100001
-------------------
01001010 01110101 <- 16b CRC
仿此，可推出两个字节数据计算如下：d 为数据，p 为项式，a 为余数
dddddddd dddddddd 0 |
