在Delphi下，如何计算字符串的16位CRC校验码？？？(100分)

在Delphi下，如何计算字符串的16位CRC校验码？？？
用查表法怎么实现？用计算法又是怎么实现呢？

我有代码, 需要的话发邮件tseug@263.net

CRC-16/CRC-32 程序代码
不久前写一程序时要用到 CRC-16 ，但找来找去只在 UDDF 里找到一个 Delphi 的 CRC-32
程序代码，而且是用查表法，虽然说查表法速度快，但 256 项 32 位数据我怀疑可能会有
输入错误， 让人不是那么放心，而我又不知道这个表是怎么算出来的。后来我又在一本两
年前的笔记本里找到一段关于 CRC 的内容， 也不知是从哪里抄来的，还好里面有一段程序
代码，是 CRC-16 的，这段程序正是产生 CRC 表的， 可是这区区几行的程序（基本上与下
面的 BuilderTable16 函数相同）看得我一头雾水，直到这两天才弄明白， 并据此推出
CRC-32 的算法，现将全部程序列在下面，并作一些说明以助于理解，不但要知其然，还要
知其所以然嘛：

补充：为了使这段程序更加实用，我将其整理为几个单元， 分别用于 Delphi 和
C++Builder 。包括对数据流 TMemoryStream 和字符串的处理。可以在本站作品中下载。
Aug.18-01

// 注意：因最高位一定为“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 ) &amp; 0x8000 )
nAccum = ( nAccum << 1 ) ^ aPoly;
else
nAccum <<= 1;
nData <<= 1;
}
Table_CRC = ( 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 ) &amp; 0x80000000 )
nAccum = ( nAccum << 1 ) ^ aPoly;
else
nAccum <<= 1;
nData <<= 1;
}
Table_CRC = 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 相似，就不多加说明，
请参考源程序。

猛禽 Aug.9-2k

我曾经帮黑龙写过DELPHI的代码，你可以在DFW里找来看看！

张大哥，DFW是哪里？

DFW就是大富翁论坛呀，
auchCRCHi : array [0..255] of byte =
( $00, $C1, $81, $40, $01, $C0, $80, $41, $01, $C0,

$80, $41, $00, $C1, $81, $40, $01, $C0, $80, $41,

$00, $C1, $81, $40, $00, $C1, $81, $40, $01, $C0,

$80, $41, $01, $C0, $80, $41, $00, $C1, $81, $40,

$00, $C1, $81, $40, $01, $C0, $80, $41, $00, $C1,

$81, $40, $01, $C0, $80, $41, $01, $C0, $80, $41,

$00, $C1, $81, $40, $01, $C0, $80, $41, $00, $C1,

$81, $40, $00, $C1, $81, $40, $01, $C0, $80, $41,

$00, $C1, $81, $40, $01, $C0, $80, $41, $01, $C0,

$80, $41, $00, $C1, $81, $40, $00, $C1, $81, $40,

$01, $C0, $80, $41, $01, $C0, $80, $41, $00, $C1,

$81, $40, $01, $C0, $80, $41, $00, $C1, $81, $40,

$00, $C1, $81, $40, $01, $C0, $80, $41, $01, $C0,

$80, $41, $00, $C1, $81, $40, $00, $C1, $81, $40,

$01, $C0, $80, $41, $00, $C1, $81, $40, $01, $C0,

$80, $41, $01, $C0, $80, $41, $00, $C1, $81, $40,

$00, $C1, $81, $40, $01, $C0, $80, $41, $01, $C0,

$80, $41, $00, $C1, $81, $40, $01, $C0, $80, $41,

$00, $C1, $81, $40, $00, $C1, $81, $40, $01, $C0,

$80, $41, $00, $C1, $81, $40, $01, $C0, $80, $41,

$01, $C0, $80, $41, $00, $C1, $81, $40, $01, $C0,

$80, $41, $00, $C1, $81, $40, $00, $C1, $81, $40,

$01, $C0, $80, $41, $01, $C0, $80, $41, $00, $C1,

$81, $40, $00, $C1, $81, $40, $01, $C0, $80, $41,

$00, $C1, $81, $40, $01, $C0, $80, $41, $01, $C0,

$80, $41, $00, $C1, $81, $40
);

auchCRCLo:array[1..255]of byte=
(
$00, $C0, $C1, $01, $C3, $03, $02, $C2, $C6, $06,

$07, $C7, $05, $C5, $C4, $04, $CC, $0C, $0D, $CD,

$0F, $CF, $CE, $0E, $0A, $CA, $CB, $0B, $C9, $09,

$08, $C8, $D8, $18, $19, $D9, $1B, $DB, $DA, $1A,

$1E, $DE, $DF, $1F, $DD, $1D, $1C, $DC, $14, $D4,

$D5, $15, $D7, $17, $16, $D6, $D2, $12, $13, $D3,

$11, $D1, $D0, $10, $F0, $30, $31, $F1, $33, $F3,

$F2, $32, $36, $F6, $F7, $37, $F5, $35, $34, $F4,

$3C, $FC, $FD, $3D, $FF, $3F, $3E, $FE, $FA, $3A,

$3B, $FB, $39, $F9, $F8, $38, $28, $E8, $E9, $29,

$EB, $2B, $2A, $EA, $EE, $2E, $2F, $EF, $2D, $ED,

$EC, $2C, $E4, $24, $25, $E5, $27, $E7, $E6, $26,

$22, $E2, $E3, $23, $E1, $21, $20, $E0, $A0, $60,

$61, $A1, $63, $A3, $A2, $62, $66, $A6, $A7, $67,

$A5, $65, $64, $A4, $6C, $AC, $AD, $6D, $AF, $6F,

$6E, $AE, $AA, $6A, $6B, $AB, $69, $A9, $A8, $68,

$78, $B8, $B9, $79, $BB, $7B, $7A, $BA, $BE, $7E,

$7F, $BF, $7D, $BD, $BC, $7C, $B4, $74, $75, $B5,

$77, $B7, $B6, $76, $72, $B2, $B3, $73, $B1, $71,

$70, $B0, $50, $90, $91, $51, $93, $53, $52, $92,

$96, $56, $57, $97, $55, $95, $94, $54, $9C, $5C,

$5D, $9D, $5F, $9F, $9E, $5E, $5A, $9A, $9B, $5B,

$99, $59, $58, $98, $88, $48, $49, $89, $4B, $8B,

$8A, $4A, $4E, $8E, $8F, $4F, $8D, $4D, $4C, $8C,

$44, $84, $85, $45, $87, $47, $46, $86, $82, $42,

$43, $83, $41, $81, $80, $40
);

function LRC(auchMsgByte;usDataLen:Word):byte;
var
uchLRC:byte;
begin
uchLRC:=0;
while usDataLen>0 do
begin
inc(uchLRC,auchMsg^);
auchMsg++;
dec(usDataLen);
end;
Result:=-uchLRC; //可能有点问题，你的没有写清楚
end;

function CRC16(puchMsgByte, usDataLen:Word):byte;
var
uchCRCHi:byte;
uchCRCLo:byte;
uIndex:Word;
begin
uchCRCHi:=$FF;
uchCRCLo:=$FF;
while usDataLen>0 then
begin
uIndex:=uchCRCHi xor puchMsg^;
uchCRCHi:=uchCRCLo xor auchCRCHi[uIndex]
inc(puchMsg);
uchCRCLo:=auchCRCLo[uIndex];
dec(usDataLen);
end;
Result:= uchCRCHi shl 8 or uchCRCLo;
end;

张兄，上面代码中有问题:
auchMsg++;
Result:=-uchLRC; //可能有点问题，你的没有写清楚

auchMsg++是c的嘛，就是 inc(auchMsg)

请问张兄，上面的函数LRC是干什么用的呢？起了个什么作用？请赐教。

张兄，上面的程序好像有点问题
Result:= uchCRCHi shl 8 or uchCRCLo;
uchCRCRHi左移8位之后变成0了，最后结果是一个8位的校验码

我是根据黑龙给我的C++代码改的

多人接受答案了。