原创 【转】CRC32详解

第一次深入接触CRC，是在做802.11的MAC的设计实现的时候，802.11的MAC层采用的是CRC-32校验来确保传输数据包的完整性的。802.11标准附录的流程图中关于CRC-32校验只是做了算法级别的说明，但是没有具体的分析和阐述。在查了关于CRC计算的资料之后，结合具体的代码，我基本弄清了802.11的MAC中的CRC-32校验的主要原理，现在做一下简单的介绍，纯属个人理解。

       1、先从CRC校验讲起。

       所谓的CRC校验，就是循环冗余校验，Cyclic Redundancy Check，是数据通信领域中最常用的一种差错校验码，其特征是信息字段和校验字段的长度可以任意选定，也就是说，不管信息字段（我比较习惯称之为明文，plaintext或者message）有多长，只要选定某一种CRC校验，最后得到的校验字段（也可以称为校验和）的长度是一定的。

       通常使用的CRC校验有CRC-12，CRC-16，CRC-32，后面的数字就表示校验之后校验字段的长度（以bit为单位）。

       2、CRC校验的基本思路：

       所有的CRC校验都是基于以下这个等式：

       M是信息字段（Message）多项式，R是校验字段（Remainder）多项式，r是校验字段多项式的最高次幂（也就是校验字段的长度，CRC-32对应的r=32，依次类推）。G是生成(Generator)多项式。发送端M和G（对某一种确定的CRC校验，其G是固定的）是已知的，CRC计算就是为了求出校验字段R；接收端M，R，G都是已知的，主要的操作都是为了验证等式是否成立，方法有很多种。

       3、发送端和接收端的具体处理方法（翻译自《CYCLIC REDUNDANCY CHECK》）

       下表展示了用于被用于一些常用的CRC标准的生成多项式，Hex列表示生成多项式对应的十六进制，MSB（most significant bit，可以理解为最左边的一位）省略，因为该位总是为1：

       不同CRC标准的差异之处在于其对生成多项式的选择。绝大多数的CRC校验采用由某个非零比特串预处理信息，另外的则不采用这样的初始化。绝大多数校验的传输采用逐比特的LSB优先原则，另外的则采用MSB优先。绝大多数校验采用LSB优先原则附加校验和，另外的则采用MSB优先。有些（校验）会对校验和取反。

        CRC-12被用于传输6比特的字符数据流，其他的CRC校验则用于传输8比特的字符数据，或者是8比特为1字节的任意的数据。CRC-16被用于IBM的BISYNCH通信标准。CRC-CCITT多项式，或者说是ITU-TSS，被用于诸如XMODEM，X.25，IBM’s SDLC和ISO’s HDLC [Tanen]等。CRC-32也被称为AUTODIN-II和ITU-TSS（ITU-TSS定义了16比特和32比特的多项式）。被用于PKZip, Ethernet, AAL5 (ATM自适应层5)，FDDI（分布式光线数据接口），IEEE-802 LAN/MAN 标准和一些DOD应用。以下是一些软件算法。

        表中前三个多项式都有x+1作为因子，而最后一个（CRC-32）则没有。

        为了检测错误插入的错误或者是检测前导0的出现，一些协议把一个或者多个非零比特串预添加到待传的消息中去。实际上，这些比特串并不参与传输，它们只是简单的被用于初始化用于进行CRC运算的key寄存器。r比特个全1的值经常被采用，接收端也是以相同的方式初始化该寄存器。

        拖尾0的问题有一点小复杂。接收端接收到明文和校验和，计算出明文的余式，并与校验和做比较，就能检测出错误，这没有问题。更简单的做法是，接收端对接收到的所有数据求余式（包括明文和校验和），所得的余式一定为0。但是，余式为0并不一定能够说明明文没有改变，如果明文有尾部的0增加或者删除的情况出现，是无法被检测出来的。

       那么接收端如何才能识别无差错的传输呢？我们知道：

        用/R表示R对1取反，我们得到：

        因此，由接收端计算出的无差错的传输的校验和应该是：

       对于给定的生成多项式G，上式是一个常数，对CRC-32而言，该值成为剩余值，是：

      或以十六进制表示：C704DD7B。

      4、MAC中的CRC-32的流程

        MAC层中有三个功能模块用到了CRC校验子模块，一个是负责分片和加密的MPDU_Generation模块（模块2），实际上是加密进程中包含了CRC校验（ICV是明文的CRC校验），一个是负责发送的发送模块（模块4），要给整个MPDU加上FCS；还有一个是接收模块（模块5），用CRC校验模块来验证MPDU的完整性。

        这三个模块在标准中被称为Operator CRC32（参见IEEE 1999 P302），如3中提到的：为了检测错误插入的错误或者是检测前导0的出现，该协议设定了全为1的32位初始值存于key寄存器：其输入是32位的crcin（标准中规定crcin的初始值是0xFFFF），8位的val（信息字段，明文），输出是32位的result。无论待校验的数据多长，都是先将先收到的8位数据输入，再将输出的result作为下一个CRC32的crcin，另一输入是下个8位数据，依次类推。

        在发送端，包括模块2和模块4。也是如3中提到的：为了检测明文尾部0的插入或者删除的情况，对获得的R取反后再附加到明文后面。遵循LSB优先原则，明文按低字节开始输入（crcin取crcinital=0xFFFF），待校验明文都处理完毕之后将所得到的FCS取反、逆序，发送的顺序是：首先是明文按低字节逐字节发送，然后将取反逆序的FCS（暂且称为FCS’）按照低字节逐字节发送。

        在发送端，我们按照先发先收的原则，将先收到字节输入，类似于发送端的过程，不同的是将FCS也作为输入数据，求出最后的CRC值，与剩余值作比较，如果等于剩余值说明消息完整。

        以下是示意图：

 5、内部的运算

为实现求出满足

的R，并取反，MAC中的CRC32的具体算法如下图所示：

其中feedback = 0x04C11DB7。

用C代码可以这样表示：

 
unsigned int crc32(unsigned char *message) {
   int i, j;
   unsigned int byte, crc;
   i = 0;
   crc = 0xFFFFFFFF;
   while (message != 0) {
      byte = message;            // Get next byte.
      byte = reverse(byte);         // 32-bit reversal.
      for (j = 0; j <= 7; j++) {    // Do eight times.
         if ((int)(crc ^ byte) < 0)
              crc = (crc << 1) ^ 0x04C11DB7;
         else crc = crc << 1;
         byte = byte << 1;          // Ready next msg bit.
      }
      i = i + 1;
   }
   return reverse(~crc);
}