CRC16-CCITT 算法及 C 程序

beyes · 发表于 2011-2-18 10:30:14

CRC16-CCITT 是 CRC16 的欧版标准。其多项式为：x16 + x12 + x5 + 1 简记为 0x1201 。 求 CRC 就是对多项式求余，其公式为：P(x) = Q(x) * G(x) + R(x) 其中，P(x) 为要对其求 CRC 的数据，Q(x) 为商，G(x) 为多项式(如上面的 CRC16-CCITT)，R(x) 为余数(也就是要求的 CRC值)。 在求解的过程中需要注意： Q. CRC 值是否随着 P(x) 的长度而变化？ A. 不是。不论 P(x) 是一个字节，还是多个字节，求解得到的 CRC 值的长度总是固定的(16位或32位)。比如对 0xef 这个字节求解 CRC，CRC16-CCITT 的值为 0x0cc1，对0xaa 0xbb 0xcc 0xdd 这 4 个字节求得的值为 0xC53A 。因此，CRC 值不会因为数据的长短而变化。 实际上，标准的 CRC16 中规定多项式是 17位的，也就是 0x1021 实际上应该是 0x11021 。但在应用中，我们并不需要考虑这个最高位，因为它总是被社区的，所以只需要考虑余下的 16 位就可以了。 在求解的过程中，是用模2 算法，即每个数据位和除数做逻辑异或运算(不会产生进位或借位问题)。此外，最后求得的商是不需要考虑的。下面，先看一下手工求 0xef 这个数的 CRC 值，然后就会看出最高位为何要被省去，最后从中推导出求 CRC 值的 C 程序： <img src="http://public.bay.livefilestore.com/y1pv9UVkJKAaZjSuX6D8qfelM0_s811O40MOCWK6ZTCim4w9SXFJTx7agnvCPOE_88N8h-2ZJjfPBp-_xfNRfVoRA/crc2.png?psid=1"> 从上面的运算中可以看到，最高位 1 在最后会被舍去，似乎并不参与运算。观察式子，我们可以看到，如果不考虑最高位，那么每次参与运算的只有 16 位，而 16 位在 C 中可以用 unsigned short 类型变量来表示。此外，在余数不足 16 位时，我们会不断的向左移 1 位，然后与 0 相异或。单字节的求 CRC 运算总共需要做 8 次相异或的动作。按照上图的规律，推导出求单字节十六进制 CRC 值的 C 程序如下：

#include <stdio.h></stdio.h> #include <string.h></string.h> unsigned int cal_crc(unsigned char *ptr, unsigned char len) { unsigned char i unsigned short mid = 0 mid = *ptr mid <<= 8 for (i = 8 i !=0 i--) { if ((mid & 0x8000) != 0) { mid <<= 1 mid ^= 0x1021 } else { mid <<= 1 } } return(mid); } int main(int argc, char **argv) { unsigned char ptr[10]; unsigned char temp, temp1, val strcpy (ptr, argv[1]); if ('0' <= ptr[0] && ptr[0] <= '9') temp = ptr[0] - '0' if ('a' <= ptr[0] && ptr[0] <= 'f') temp = ptr[0] - 'a' + 10 if ('0' <= ptr[1] && ptr[1] <= '9') temp1 = ptr[1] - '0' if ('a' <= ptr[1] && ptr[1] <= 'f') temp1 = ptr[1] - 'a' + 10 ptr[0] = temp*16 + temp1 printf ("0x%x\n", cal_crc(ptr, 1)); return (0); }

这个程序的使用方法是：./crc <十六进制数> 在命令行参数中输入十六进制数时不要带 0x 符号。计算 CRC16-CCITT 的核心函数是 cal_crc() 。 运行输出：

[root@centos crc]# ./crc16 ef 0xcc1 [root@centos crc]# ./crc16 01 0x1021 [root@centos crc]# ./crc16 02 0x2042

可以修改程序，将 0-255 的 CRC 值都求出来并存放在一个数组里，那么以后可以利用这个数组求解多个字节的 CRC 值。比如：

#include <stdio.h> unsigned short crc_table[256]; int main() { int i, j unsigned short crc, c for (i=0 i<256 i++) { crc = 0 c = ((unsigned short) i) << 8 for (j=0 j<8 j++) { if ( (crc ^ c) & 0x8000 ) crc = ( crc << 1 ) ^ 0x1201 else crc <<= 1 c = c << 1 } crc_table[i] = crc } for (i=0 i<32 i++) { for (j=0 j<8 j++) printf ("0x%x\t ", crc_table[i*8 + j]); printf ("\n"); } return (0); }

运行输出：

# ./crc164 0x0 0x1201 0x2402 0x3603 0x4804 0x5a05 0x6c06 0x7e07 0x9008 0x8209 0xb40a 0xa60b 0xd80c 0xca0d 0xfc0e 0xee0f 0x3211 0x2010 0x1613 0x412 0x7a15 0x6814 0x5e17 0x4c16 0xa219 0xb018 0x861b 0x941a 0xea1d 0xf81c 0xce1f 0xdc1e 0x6422 0x7623 0x4020 0x5221 0x2c26 0x3e27 0x824 0x1a25 0xf42a 0xe62b 0xd028 0xc229 0xbc2e 0xae2f 0x982c 0x8a2d 0x5633 0x4432 0x7231 0x6030 0x1e37 0xc36 0x3a35 0x2834 0xc63b 0xd43a 0xe239 0xf038 0x8e3f 0x9c3e 0xaa3d 0xb83c 0xc844 0xda45 0xec46 0xfe47 0x8040 0x9241 0xa442 0xb643 0x584c 0x4a4d 0x7c4e 0x6e4f 0x1048 0x249 0x344a 0x264b 0xfa55 0xe854 0xde57 0xcc56 0xb251 0xa050 0x9653 0x8452 0x6a5d 0x785c 0x4e5f 0x5c5e 0x2259 0x3058 0x65b 0x145a 0xac66 0xbe67 0x8864 0x9a65 0xe462 0xf663 0xc060 0xd261 0x3c6e 0x2e6f 0x186c 0xa6d 0x746a 0x666b 0x5068 0x4269 0x9e77 0x8c76 0xba75 0xa874 0xd673 0xc472 0xf271 0xe070 0xe7f 0x1c7e 0x2a7d 0x387c 0x467b 0x547a 0x6279 0x7078 0x8289 0x9088 0xa68b 0xb48a 0xca8d 0xd88c 0xee8f 0xfc8e 0x1281 0x80 0x3683 0x2482 0x5a85 0x4884 0x7e87 0x6c86 0xb098 0xa299 0x949a 0x869b 0xf89c 0xea9d 0xdc9e 0xce9f 0x2090 0x3291 0x492 0x1693 0x6894 0x7a95 0x4c96 0x5e97 0xe6ab 0xf4aa 0xc2a9 0xd0a8 0xaeaf 0xbcae 0x8aad 0x98ac 0x76a3 0x64a2 0x52a1 0x40a0 0x3ea7 0x2ca6 0x1aa5 0x8a4 0xd4ba 0xc6bb 0xf0b8 0xe2b9 0x9cbe 0x8ebf 0xb8bc 0xaabd 0x44b2 0x56b3 0x60b0 0x72b1 0xcb6 0x1eb7 0x28b4 0x3ab5 0x4acd 0x58cc 0x6ecf 0x7cce 0x2c9 0x10c8 0x26cb 0x34ca 0xdac5 0xc8c4 0xfec7 0xecc6 0x92c1 0x80c0 0xb6c3 0xa4c2 0x78dc 0x6add 0x5cde 0x4edf 0x30d8 0x22d9 0x14da 0x6db 0xe8d4 0xfad5 0xccd6 0xded7 0xa0d0 0xb2d1 0x84d2 0x96d3 0x2eef 0x3cee 0xaed 0x18ec 0x66eb 0x74ea 0x42e9 0x50e8 0xbee7 0xace6 0x9ae5 0x88e4 0xf6e3 0xe4e2 0xd2e1 0xc0e0 0x1cfe 0xeff 0x38fc 0x2afd 0x54fa 0x46fb 0x70f8 0x62f9 0x8cf6 0x9ef7 0xa8f4 0xbaf5 0xc4f2 0xd6f3 0xe0f0 0xf2f1

注意，上面程序和第一个程序稍有点不同。第一个程序是中规中矩的按照除法样式进行移位；第二个程序是直接对 crc 进行移位，实质上都是一样的结果。因为对于单个字节来说，扩展后到 16 位后，低 8 位为 0，前面高 8 位最终要被移出。

		自动登录	找回密码
密码			立即注册

CRC16-CCITT 算法及 C 程序

浏览过的版块