分享
 
 
 

CRC-16/CRC-32程序代码

王朝other·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

不久前写一程序时要用到 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 相似,就不多加说明,请参考源程序。

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有