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. }  

相关内容