CRC实现之CRC通用算法（一）

看了两天的CRC，网上的资料大致可分两类，要么数学公式一大堆，最终只告诉你用先移相应位，再用短除法求余数就是对应的CRC码；要么全是代码，并且只针对一种CRC生成多项式。这两种都很难看懂哦，看的我头都大了。最后终于找到一篇理论与实践相结合的，才有了点眉目，仔细想了想，依样画葫芦，写出了对应的通用算法，我只验证了N=4和N=16的情况，其他的如果有什么问题大家可以向我说，我们一起讨论。如果你要这方面的资料，我可以把我搜集到的发给你，请留下邮箱。

好了，不说废话了，通用算法如下：

/*
*   CRC通用算法    *
*   version 1.0    *
*   by Yinpei    *
*   Wuhan University   *
*   2006年11月18日    *
*/
#define CRC_NUM_N //定义每种CRC的校验码比特数
/*
CRC_NUM_32 == 32
CRC_NUM_24 == 24
CRC_NUM_16 == 16
CRC_NUM_12 == 12
CRC_NUM_8  == 8
CRC_NUM_4  == 4
*/
#define LIMIT_MASK_N //定义每种CRC校验码的最大值
/*
LIMIT_MASK_32 == 0xFFFFFFFF
LIMIT_MASK_24 == 0xFFFFFF
LIMIT_MASK_16 == 0xFFFF
LIMIT_MASK_12 == 0xFFF
LIMIT_MASK_8  == 0xFF
LIMIT_MASK_4  == 0xF
*/
#define MSB_MASK_N //用于检测CRC校验码左移一位后是否会溢出(所占比特数超出CRC_NUM_N)
/*
MSB_MASK_32 == 0x80000000
MSB_MASK_24 == 0x800000
MSB_MASK_16 == 0x8000
MSB_MASK_12 == 0x800
MSB_MASK_8  == 0x80
MSB_MASK_4  == 0x8
*/
#define R_N //根据N次生成多项式得到的1的对应的余数多项式对应CRC(0相应的余数为0)
/*
g_24(D)=D24+D23+D6+D5+D+1  :  R_24 == 1000 0000 0000 0000 0110 0011 == 0x800063
g_16(D)=D16+D12+D5+1    :  R_16 == 1000000100001 == 0x1021
g_12(D)=D12+D11+D3+D2+D+1  :  R_12 == 100000001111 == 0x80F
g_8(D) =D8+D7+D4+D3+D+1    :  R_8  == 10011011 == 0x9B
g_4(D) =D4+D3+D2+1    :  R_4  == 1101 == 0xD 
*/
 //N表示生成多项式的最高阶数，常见如32、24、16、12、8、4
unsigned int cal_crcN(unsigned char *ptr, unsigned char len){
 unsigned int i;
 unsigned int crc=0;
 while(len--!=0)
 {
  //此处迭代变量为0x80，表示以字节为单位存储源数据，并且每个字节迭代8次，分别处理每个位
  for(i=0x80; i!=0; i/=2)
  {
   //通过MSB_MASK_N检测CRC校验码左移一位后是否会溢出
   if((crc&MSB_MASK_N)!=0)
   {
    //如果会溢出
    crc*=2;
    crc&=LIMIT_MASK_N;//取有效比特位，使其在CRC_NUM_N内
    crc^=R_N;
   } /* 余式CRC 乘以2 再求CRC */
   else crc*=2;
   if((*ptr&i)!=0) crc^=R_N; /* 再加上本位的CRC */
  }
  ptr++;
 }
 return(crc);
}

验证程序：

main()
{
 char test[ ]={0x01};
 int res_crc;
 res_crc=cal_crc16(test,8);
 printf("res_crc=%x\n",res_crc);
}

最后补充两句，这个通用算法是按位计算的，虽然代码简单，所占用的内存比较少，但其最大的缺点就是一位一位地计算会占用很多的处理器处理时间，尤其在高速通讯的场合，这个缺点更是不可容忍。今后我会给出更高效的通用算法。