CRC-16/CRC-32程序代码
| 0000000 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 |
凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢! |
