本文首发于“嵌入式软件实战派”。

循环冗余校验（英语：Cyclic redundancy check，通称“CRC”）是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。

Wikipedia

一句话：CRC是将数据计算出散列的方式，一般用于校验数据的完整性。它具有简单、执行效率高等特点。当然，你可以类比于Checksum，但比Checksum复杂些，防碰撞性更好些。

▍CRC的原理

CRC是基于除法的。实际的输入数据会被解释为一个长二进制位流（除数），再将其除以另一个固定二进制数（除数，即多项式）。该除法的其余部分就是校验值。

但是，现实要复杂一些。二进制数（除数和除数）不被视为普通整数值，而是被视为二进制多项式，其中实际位用作系数。

输入数据，看做一串二进制流，用多项式的方式表示为g(x)，而除数是国际标准上的多项式，用h(x)表示。通过g(x)和h(x)做除法，即两者的异或运算，得出的结果，就是我们所说的CRC运算检验结果。

那么，这里有两个疑问:

问题1：多项式和二进制是什么关系？

例如，1x3 + 0x2 + 1x + 1可以表示为1011b，或者1011b表示为1x3 + 0x2 + 1x + 1，其中是0的位，即以0为系数乘以该项。

问题2：除法怎么做？ 本质就是在做异或运算

我们来看看一个数据串11010011101100除以x3 + x + 1是怎样进行的？

注意，根据CRC长度，需要将这个数据串补0

整个运算过程是这样的：

实际上就是逐个bit移位做异或。

详见：https://en.wikipedia.org/wiki/Cyclic_redundancy_check

▍CRC的概念

实际上，人们根据不同的需要，做了很多种计算方式，主要差别在于CRC长度、多项式、初始值、结果是否需要异或、是否需要翻转等等。

首先，来看看几个概念:

Length: CRC的长度(按bit算，如8,16,32)

Name: CRC的名字，让人一看就知道这是哪种CRC

Polinomial: 多项式，通过该多项式来计算CRC

InitialValue: CRC的初始值

FinalXorValue: CRC结果做异或运算的值

InputReflected: 指示输出是否需要翻转

OutputReflected: 指示输出是否需要翻转

我将网上搜到的所有的CRC标准分类做了个汇总：

从上面的CRC名称可以看出，不同的算法是有不同用途的，这是国际常规的用法定义，其实如果是用户自己用也没特别要求，可以自由点。

▍CRC的实现

1. 根据多项式二进制数，逐位做异或

按照前面章节的“CRC原理”来做C语言实现，就通过数据移位和异或算得。以CRC8为例，代码如下