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.  */  
14.   
15. #include <stdio.h>  
16. #include <string.h>  
17.   
18. #define CRC_BITS 8  
19. #define TABLE_SIZE (1 << CRC_BITS)  
20.   
21. /* 在小端序機器上，因為低位在前，所以將多項式對應的位串反轉 */  
22. #define CRC16POLY_LE 0xa001  
23. #define CRC16POLY_BE 0x8005  
24.   
25. #define MASK_LE 0x0001  
26. #define MASK_BE 0x8000  
27.   
28.   
29. unsigned short crc16_table[TABLE_SIZE];  
30.   
31. /*  
32.  * 在小端序的機器上，低位在前  
33.  * 作為位串計算時，這裡的位操作向右移  
34.  */  
35. static void  
36. crc16init_le(void)  
37. {  
38.     unsigned short i, j, crc;  
39.   
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. }  
54.   
55. static void  
56. crc16init_be(void)  
57. {  
58.     unsigned short i, j, crc;  
59.   
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. }  
70.   
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. }  
83.   
84. void  
85. main(void)  
86. {  
87.     crc16init_le();  
88.     printf("--------------\nle table\n\n");  
89.     crc16_print();  
90.   
91.     crc16init_be();  
92.     printf("--------------\nbe table\n\n");  
93.     crc16_print();  
94. }