Linux內核中crc16_table與crc32_table的計算

CRC： Cyclic redundancy check 循環冗余校驗

內核中使用的crc16計算方法位於代碼樹/lib/crc16.c文件中

crc32的計算方法位於代碼樹/lib/crc32.c文件中

均采用了查表法

其中crc32的表由代碼樹/lib/gen_crc32table.c中的主機小程序計算而來

生成的冗余表保存在文件/lib/crc32table.h中

具體的計算方法可以參考gen_crc32table.c中的代碼

/lib/crc16.c中的crc16_table是直接定義的，沒有提供計算代碼

在學習了wiki上介紹的原理後，參考內核中crc32的計算方法，寫了個crc16的代碼

生成crc16_table表

1. /*
2. * crc16gen.c - CRC-16 table gen routine
3. *
4. * Generate the standard CRC-16 table:
5. * Width 16
6. * Poly 0x8005 (x^16 + x^15 + x^2 + 1)
7. * Init 0
8. *
9. * <kernel.digger@gmail.com>
10. *
11. * This source code is licensed under the GNU General Public License,
12. * Version 2. See the file COPYING for more details.
13. */
15. #include <stdio.h>
16. #include <string.h>
18. #define CRC_BITS 8
19. #define TABLE_SIZE (1 << CRC_BITS)
21. /* 在小端序機器上，因為低位在前，所以將多項式對應的位串反轉 */
22. #define CRC16POLY_LE 0xa001
23. #define CRC16POLY_BE 0x8005
25. #define MASK_LE 0x0001
26. #define MASK_BE 0x8000
29. unsigned short crc16_table[TABLE_SIZE];
31. /*
32. * 在小端序的機器上，低位在前
33. * 作為位串計算時，這裡的位操作向右移
34. */
35. static void
36. crc16init_le(void)
37. {
38. unsigned short i, j, crc;
40. for (i = 0; i < TABLE_SIZE; i++)
41. {
42. /* i為0-255的字符值，放在crc的低字節處 */
43. crc = i;
44. for (j = 0; j < CRC_BITS; j++)
45. {
46. /* 位串首位為1的話(最低bit為1)
47. 則右移1位的同時異或多項式
48. 否則異或0，即直接右移1位 */
49. crc = (crc >> 1) ^ ((crc & MASK_LE) ? CRC16POLY_LE : 0);
50. }
51. crc16_table[i] = crc;
52. }
53. }
55. static void
56. crc16init_be(void)
57. {
58. unsigned short i, j, crc;
60. for (i = 0; i < TABLE_SIZE; i++)
61. {
62. crc = i << 8;
63. for (j = 0; j < CRC_BITS; j++)
64. {
65. crc = (crc << 1) ^ ((crc & MASK_BE) ? CRC16POLY_BE : 0);
66. }
67. crc16_table[i] = crc;
68. }
69. }
71. static void
72. crc16_print(void)
73. {
74. int i;
75. for (i = 0; i < TABLE_SIZE; i++)
76. {
77. printf(" 0x%04x ", crc16_table[i]);
78. if ((i % 8) == 7) {
79. printf("\n");
80. }
81. }
82. }
84. void
85. main(void)
86. {
87. crc16init_le();
88. printf("--------------\nle table\n\n");
89. crc16_print();
91. crc16init_be();
92. printf("--------------\nbe table\n\n");
93. crc16_print();
94. }