CRC-16/CRC-32措施代码
副标题#e#
不久前写一措施时要用到 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;
}
#p#副标题#e#
说明：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 ) 的实现要领。阐明前面一个字节数据的
#p#分页标题#e#
计较进程可发明，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 相似，就不多加说明，请参考源措施。
