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表：

/* 
*  crc16gen.c - CRC-16 table gen routine 
* 
* Generate the standard CRC-16 table: 
*   Width 16 
*   Poly  0x8005 (x^16 + x^15 + x^2 + 1) 
*   Init  0 
* 
* <kernel.digger@gmail.com> 
* 
* This source code is licensed under the GNU General Public License, 
* Version 2. See the file COPYING for more details. 
*/ 
 
#include <stdio.h> 
#include <string.h> 
 
#define CRC_BITS 8 
#define TABLE_SIZE (1 << CRC_BITS) 
 
/* 在小端序机器上，因为低位在前，所以将多项式对应的位串反转 */ 
#define CRC16POLY_LE 0xa001 
#define CRC16POLY_BE 0x8005 
 
#define MASK_LE 0x0001 
#define MASK_BE 0x8000 
 
 
unsigned short crc16_table[TABLE_SIZE]; 
 
/* 
 * 在小端序的机器上，低位在前 
 * 作为位串计算时，这里的位操作向右移 
 */ 
static void 
crc16init_le(void) 
{ 
unsigned short i, j, crc; 
 
for (i = 0; i < TABLE_SIZE; i++) 
{ 
/* i为0-255的字符值，放在crc的低字节处 */ 
crc = i; 
for (j = 0; j < CRC_BITS; j++) 
{ 
/* 位串首位为1的话(最低bit为1) 
则右移1位的同时异或多项式 
否则异或0，即直接右移1位 */ 
crc = (crc >> 1) ^ ((crc & MASK_LE) ? CRC16POLY_LE : 0); 
} 
crc16_table[i] = crc; 
} 
} 
 
static void 
crc16init_be(void) 
{ 
unsigned short i, j, crc; 
 
for (i = 0; i < TABLE_SIZE; i++) 
{ 
crc = i << 8; 
for (j = 0; j < CRC_BITS; j++) 
{ 
crc = (crc << 1) ^ ((crc & MASK_BE) ? CRC16POLY_BE : 0); 
} 
crc16_table[i] = crc; 
} 
} 
 
static void 
crc16_print(void) 
{ 
int i; 
for (i = 0; i < TABLE_SIZE; i++) 
{ 
printf("0x%04x ", crc16_table[i]); 
if ((i % 8) == 7) { 
printf("\n"); 
} 
} 
} 
 
void 
main(void) 
{ 
crc16init_le(); 
printf("--------------\nle table\n\n"); 
crc16_print(); 
 
crc16init_be(); 
printf("--------------\nbe table\n\n"); 
crc16_print(); 
}