CRC原理和实现

原文：http://blog.sina.com.cn/s/blog_ad0672d60101j93l.html

一、CRC介绍
RCR为Cyclical Redundancy Check，循环冗余码校验.它是利用除法及余数的原理来作错误侦测（Error Detecting）的。
CRC数值简单地说就是通过让你需要做处理的数据“除以”一个常数而得到的余数。
实际应用时，发送装置计算出CRC值并随数据一同发送给接收装置，接收装置对收到的数据重新计算CRC并与收到的CRC相比较，若两个CRC值不同，则说明数据通讯出现错误。

二、生成多项式
生成多项式是，求CRC数值时所用的一个常数。生成多项式是CRC中的除数。
一般在计算机的除法中，都使用的是减运算，但在CRC多项式除法运算中使用的是异或运算。

三、CRC检验原理(CRC16)
CRC-16码由两个字节构成，在开始时CRC寄存器的每一位都预置为1
然后把CRC寄存器与8-bit的数据进行异或(异或：二进制运算 相同为0，不同为1；0^0=0;0^1=1;1^0=1;1^1=0)
之后对CRC寄存器从高到低进行移位，在最高位（MSB）的位置补零，而最低位（LSB，移位后已经被移出CRC寄存器）如果为1，则把寄存器与预定义的生成多项式进行异或，否则如果LSB为零，则无需进行异或。
重复上述的由高至低的移位8次，第一个8-bit数据处理完毕，用此时CRC寄存器的值与下一个8-bit数据异或并进行如前一个数据值的8次移位。
所有的字符处理完成后CRC寄存器内的值即为最终的CRC值。
 
计算过程：
1．设置CRC寄存器，并给其赋值FFFF(hex)。
2．将数据的第一个8-bit字符与16位CRC寄存器的低8位进行异或，并把结果存入CRC寄存器。
3．CRC寄存器向右移一位，MSB补零，移出并检查LSB。
4．如果LSB为0，重复第三步；若LSB为1，CRC寄存器与生成多项式相异或。
5．重复第3与第4步直到8次移位全部完成。此时一个8-bit数据处理完毕。
6. 把(本次CRC值)与(上次CRC值右移8位的值)相异或，然后取反
6．重复第2至第6步直到所有数据全部处理完成。
7．最终CRC寄存器的内容即为CRC值。

查表方法
通过对CRC算法的研究，我们发现:一个8位数据加到16位累加器中去，只有累加器的高8位或低8位与数据相作用，其结果仅有256种可能(2^8)的组合值。因而，我们可以用查表法来代替反复的运算，这也同样适用于CRC32的计算。

四、CRC32算法实现
//crc32.h
#ifndef _CRC32_H
#define _CRC32_H

uint crc32( uchar *buf, int len);

#endif

crc32的源文件
#include
#include "crc32.h"

static uint   CRC32[256];
static char   init = 0;

//初始化表
//对应算法的2、3、4、5步骤
static void init_table()
{
    int   i,j;
    uint   crc;
    for(i = 0;i < 256;i++)
    {
        crc = i;
        for(j = 0;j < 8;j++)
        {
            if(crc & 1)
            {
                 crc = (crc >> 1) ^ 0xEDB88320;
            }
            else
            {
                 crc = crc >> 1;
            }
        }
         CRC32[i] = crc;
    }
}

//crc32实现函数
uint crc32(uint ret, uchar *buf, int len)
{
    uint ret = ~ret;
    int   i;
    if( !init )
    {
         init_table();
         init = 1;
    }
    for(i = 0; i < len;i++)
    {
         ret = CRC32[(ret & 0xFF) ^ buf[i]] ^ (ret >> 8);
    }
    return ~ret;
}

//使用
const char *s = "The quick brown fox jumps over the lazy dog";
printf("%lX\n", crc32(0, (const void*)s, strlen(s)));

五、CRC常用生成多项式
CRC(16IBM) = X^16+X^15+X^2+1
CRC(CCITT) = X^16+X^12+X^5+1
CRC(32以太网帧) = X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X+1,由于32位bit达不到X^32,因此X^32舍去

以CRC(16IBM)多项式为例，其对应校验二进制位列为(1) 1000 0000 0000 0101=0x8005
以CRC(32以太网帧)多项式为例，其对应校验二进制位列为(1) 0000 0100 1100 0001 0001 1101 1011 0111=0x4C11DB7,从高到低
                                                       1110 1101 1011 1000 1000 0011 0010 0000 (1)=EDB88320,从低到高


其他CRC相关文章：
STM32 CRC32 全接触（原理＋源码） 
CRC原理及C语言实现： 
结果正确的CRC32算法  
最简单的CRC32源码－查表法  
CRC问题  
CRC逆向算法： http://blog.csdn.net/crazyleen/article/details/7334081
CRC32算法及CRC原理： 
STM32学习1：基本 存储器、CRC、电源 http://blog.sina.com.cn/s/blog_aa3e5f4e0102v1z0.html