不久前写一程序时要用到 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 00000000 00000000 - 数据 D ( D1, D0, 0, 0 )
　　^pppppppp pppppppp p - 多项式 P
　　-----------------------------------
　　...
　　aaaaaaaa aaaaaaaa 0 - 第一次的余数 A'' ( A''1, A''0 )
　　^pppppppp pppppppp p
　　--------------------------
　　...
　　aaaaaaaa aaaaaaaa - 结果 A ( A1, A0 )
　　
　　由此与一字节的情况比较，将两个字节分开计算如下：
　　先算高字节：
　　dddddddd 00000000 00000000 00000000 - D1, 0, 0, 0
　　^pppppppp pppppppp p - P
　　-----------------------------------
　　...
　　aaaaaaaa aaaaaaaa - 高字节部分余数 PHA1, PHA0
　　
　　此处的部分余数与前面两字节算法中的第一次余数有如下关系，即 A''1 = PHA1 ^ D0, A''0 = PHA0：
　　aaaaaaaa aaaaaaaa - PHA1, PHA0
　　^dddddddd - D0
　　-----------------
　　aaaaaaaa aaaaaaaa - A''1, A''0
　　
　　低字节的计算：
　　aaaaaaaa 00000000 00000000 - A''1, 0, 0
　　^pppppppp pppppppp p - P
　　--------------------------
　　...
　　aaaaaaaa aaaaaaaa - 低字节部分余数 PLA1, PLA0
　　^aaaaaaaa - A''0 ， 即 PHA0
　　-----------------
　　aaaaaaaa aaaaaaaa - 最后的 CRC ( A1, A0 )
　　
　　总结以上内容可得规律如下：
　　设部分余数函数
　　PA = f( d )
　　其中 d 为一个字节的数据（注重，除非 n = 0 ，否则就不是原始数据，见下文）
　　第 n 次的部分余数
　　PA( n ) = ( PA( n - 1 ) 8 ) ^ f( d )
　　其中的
　　d = ( PA( n - 1 ) 8 ) ^ D( n )
　　其中的 D( n ) 才是一个字节的原始数据。
　　
　　公式如下：
　　PA( n ) = ( PA( n - 1 ) 8 ) ^ f( ( PA( n - 1 ) 8 ) ^ D( n ) )
　　
　　可以注重到函数 f( d ) 的参数 d 为一个字节，对一个确定的多项式 P， f( d ) 的返回值
　　是与 d 一一对应的，总数为 256 项，将这些数据预先算出保存在表里，f( d )就转换为一
　　个查表的过程，速度也就可以大幅提高，这也就是查表法计算 CRC 的原理，在 CRC_16 和
　　CRC_32 两个函数的循环中的语句便是上面那个公式。
　　
　　再来看 CRC 表是如何计算出来的，即函数 f( d ) 的实现方法。分析前面一个字节数据的
　　计算过程可发现，d 对结果的影响只表现为对 P 的移位异或，看计算过程中的三个 8 位
　　的列中只有低两个字节的最后结果是余数，而数据所在的高 8 位列最后都被消去了，因其
　　中的运算均为异或，不产生进位或借位，故每一位数据只影响本列的结果，即 d 并不直接
　　影响结果。再将前例变化一下重列如下：
　　11011000
　　--------------------------
　　10001000 00010000 1 // P
　　^ 1000100 00001000 01 // P
　　^ 000000 00000000 000 // 0
　　^ 10001 00000010 0001 // P
　　^ 0000 00000000 00000 // 0
　　^ 100 01000000 100001 // P
　　^ 00 00000000 0000000 // 0
　　^ 1 00010000 00100001 // P
　　-------------------
　　01001010 01110101
　　
　　现在的问题就是如何根据 d 来对 P 移位异或了，从上面的例子看，也可以理解为每步
　　移位，但根据 d 决定中间余数是否与 P 异或。从前面原来的例子可以看出，决定的条
　　件是中间余数的最高位为0，因为 P 的最高位一定为1，即当中间余数与 d 相应位异或
　　的最高位为1时，中间余数移位就要和 P 异或，否则只需移位即可。具体做法见程序中
　　的 BuildTable16 和 BuildTable32 两个函数，其方法如下例（上例的变形，注重其中
　　空格的移动表现了 d 的影响如何被排除在结果之外）：
　　
　　d --------a--------
　　1 00000000 00000000 - HSB = 1
　　0000000 000000000 - a = 1
　　0001000 000100001 - P, CRC-CCITT 不含最高位的 1
　　-----------------
　　1 0001000 000100001
　　001000 0001000010
　　000100 0000100001
　　-----------------
　　0 001100 0001100011 - HSB = 0
　　01100 00011000110
　　-----------------
　　1 01100 00011000110 - HSB = 1
　　1100 000110001100
　　0001 000000100001
　　-----------------
　　1 1101 000110101101 - HSB = 0
　　101 0001101011010
　　-----------------
　　0 101 0001101011010 - HSB = 1
　　01 00011010110100
　　00 01000000100001
　　-----------------
　　0 01 01011010010101 - HSB = 0
　　1 010110100101010
　　-----------------
　　0 1 010110100101010 - HSB = 1
　　0101101001010100
　　0001000000100001
　　-----------------
　　0100101001110101 - CRC
　　
　　结合这些，前面的程序就好理解了。至于 32 位 CRC 的计算与 16 相似，就不多加说明，请参考源程序。