舟山网站设计公司,网站顶部展出的大幅广告,怎么申请企业邮箱,官方发布小程序开发小程序From: http://blog.csdn.net/sparkliang/article/details/5671977 CRC算法详解#xff08;2#xff09;
初见 Table-Driven 变换到上面的方法后#xff0c;我们离 table-driven 的方法只有一步之遥了#xff0c;我们知道一个字节能表示的正整数范围是 0~255#xff0c;步…From: http://blog.csdn.net/sparkliang/article/details/5671977 CRC算法详解2
初见 Table-Driven 变换到上面的方法后我们离 table-driven 的方法只有一步之遥了我们知道一个字节能表示的正整数范围是 0~255步骤 1 中的计算就是针对 reg 的高 Byte 位进行的于是可以被提取出来预先计算并存储到一个有 256 项的表中于是下面的算法就出炉了这个和上面的算法本质上并没有什么区别。 [cpp] view plaincopy #define POLY 0x04C11DB7L // CRC32生成多项式 static unsigned int crc_table[256]; unsigned int get_sum_poly(unsigned char data) { unsigned int sum_poly data; sum_poly 24; for(int j 0; j 8; j) { int hi sum_poly0x80000000; // 取得reg的最高位 sum_poly 1; if(hi) sum_poly sum_poly^POLY; } return sum_poly; } void create_crc_table() { for(int i 0; i 256; i) { crc_table[i] get_sum_poly(i0xFF); } } // 以byte数据为例 unsigned int CRC32_3(unsigned int data) { unsigned char p[8]; memset(p, 0, sizeof(p)); memcpy(p, data, 4); unsigned int reg 0, sum_poly 0; for(int i 0; i 8; i) { // 计算步骤1 sum_poly crc_table[(reg24)0xFF]; // 计算步骤2 reg (reg8)|p[i]; reg reg ^ sum_poly; } return reg; } 更进一步 上面的这个算法已经是一个Table-Driven的CRC-32算法了但是实际上我们看到的CRC校验代码都是如下的形式divdivdiv stylecolor:silver;strong[cpp]/strong a target_blank hrefhttp://blog.csdn.net/sparkliang/article/details/5671977# titleview plain stylecolor:rgb(160, 160, 160);view plain/aa target_blank hrefhttp://blog.csdn.net/sparkliang/article/details/5671977# titlecopy stylecolor:rgb(160, 160, 160);copy/a/div/divol start1 stylecolor:rgb(92, 92, 92);li stylecolor:inherit;span stylecolor:black;r0; /span/lilispan stylecolor:black;span stylecolor:rgb(0, 102, 153);while/span(len--) /span/lili stylecolor:inherit;span stylecolor:black; r (r8) ^ t[(r 24) ^ *p]; /span/li/ol/div
下面我们将看看是做了什么转化而做到这一点的。 首先上述 CRC 算法中我们需要为原始数据追加 r/8Byte 个 0 CRC-32 就是 4Byte 。或者我们可以再计算原始数据之后把 0 放在后面单独计算像这样 [cpp] view plaincopy // 先计算原始数据 for(int i 0; i len; i) { sum_poly crc_table[(reg24)0xFF]; reg (reg8)|p[i]; reg reg ^ sum_poly; } // 再计算追加的4Byte 0 for(int i 0; i 4; i) { reg (reg8) ^ crc_table[(reg24)0xFF]; } 这看起来已经足够好了而事实上我们可以继续向下进行以免去为了附加的 0 而进行计算。在上面算法中最后的 4 次循环是为了将输入数据的最后 r/8 位都移出 reg 因为 0 对 reg 的值并没有丝毫影响。
对于 CRC-32 对于任何输入数据 Dn...D8…D5D4…D1 第一个 for 循环将 Dn…D8…D5 都依次移入执行XOR 运算再移出 reg 并将 D4…D1 都移入了 reg 但是并未移出因此最后的 4 次循环是为了将 D4…D1 都移出 reg 。
Di 与 Ri 执行 XOR 运算后值将会更新设更新后的值表示为 Di’ 不论执行了多少次 XOR 运算。
如果 reg 初始值是 0 那么第一个 for 循环中开始的 4 次循环干的事情就是把 Dn…Dn-3 移入到 reg 中与0 做 XOR 结果不变执行 4 次后 reg 的值就是 Dn.Dn-1.Dn-2.Dn-3
第 5 次循环的结果就是 reg crc_table[Dn] ^ Dn-1.Dn-2.Dn-3.Dn-4
第 6 次循环的结果就是 reg crc_table[Dn-1’] ^ Dn-2’.Dn-3’.Dn-4 Dn 移出 reg 。
因此上面的计算可以分为 3 个阶段
1 前 4 次循环将 Dn.Dn-1.Dn-2.Dn-3 装入 reg
2 中间的 n-4 次循环依次将 Di 移入 reg 在随后的 4 次循环中依次计算 Di4 Di3 Di2 和 Di1对 Di 的影响最后移出 reg
3 最后的 4 次循环实际上是为了计算 D4 D3 D2 和 D1 都能执行第 2 步的过程
具体考察 Di
1 Di 移入到 reg 中 R1Di 接着与 crc_table[R4] 执行 XOR 运算
2 循环 4 次后 Di 成为 reg 的最高位 R4 并且因为受到了 Dn…Di1 的影响而更新为 Di’
上面的运算步骤如下面所示其中 F 是对应得 crc_table[R] 的值。 可以清晰的看到最后 reg 的高 Byte 是 Di 和 F 之间一次次 XOR 运算的结果。依然根据 XOR 运算的结合律我们可以分两步走
1 先执行 F 之间的 XOR 运算设结果为 FF 它就是 reg 的首字节
2 然后再直接将 Di 和 FF 进行 XOR 运算并根据结果查 CRC 表
3 计算出 XOR 运算后 Di…Di-3 已经移入 reg 因此再将查表结果和 (reg8) 执行 XOR 运算即可
这就是方法 2 于是我们的 table-driven 的 CRC-32 校验算法就可以写成如下的方式了 [cpp] view plaincopy reg 0; for(int i 0; i len; i) { reg (reg8) ^ crc_table[(reg24)0xFF ^ p[i]]; }
