Table of Contents

什么是循环冗余校验和CRC-32？

CRC-32输出的长度是多少？

CRC-8，CRC-16，CRC-32和CRC-64有什么区别？

CRC32源代码

CRC32算法详细推导

CRC 算法的数学基础

CRC 校验的基本过程

原始的 CRC 校验算法

改进一小步——从 r+1 到 r

从 bit 扩张到 byte 的桥梁

CRC32示例

循环冗余校验（CRC）是用于检测数据损坏的错误检测码。发送数据时，会根据数据内容生成简短的校验和，并将其与数据一起发送。接收数据时，将再次生成校验和并将其与发送的校验和进行比较。如果两者相等，则没有数据损坏。所述CRC-32算法本身转换可变长度字符串转换成8个字符的字符串。

CRC（Cyclic Redundancy Check）校验实用程序库在数据存储和数据通讯领域，为了保证数据的正确，就不得不采用检错的手段。在诸多检错手段中，CRC是最著名的一种。CRC的全称是循环冗余校验。

检错能力极强，开销小，易于用编码器及检测电路实现。从其检错能力来看，它所不能发现的错误的几率仅为0.0047%以下。从性能上和开销上考虑，均远远优于奇偶校验及算术和校验等方式。因而，在数据存储和数据通讯领域，CRC无处不在：著名的通讯协议X.25的FCS（帧检错序列）采用的是CRC-CCITT，ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为检错手段。

校验值的长度固定为8个字符，因此，生成该值的函数有时会用作哈希函数。

生成多项式的选择是实现CRC算法的最重要部分。必须选择多项式以最大化错误检测能力，同时使总体碰撞概率最小。

多项式的最重要属性是其长度（多项式中任何一项的最大次数（指数）+1），因为它直接影响所计算校验值的长度。

最常用的多项式长度为：

https://github.com/gcc-mirror/gcc/blob/master/libiberty/crc32.c