算法之CRC
循环冗余校验（英语：Cyclic redundancy check，通称“CRC”）是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化1。
校验码
为了防止在数据传输过程中出现不可预知的错误，达到通信的稳定性，在远距离通信时一般要引入一种校验方式来去除干扰。一般来说是在数据包的后面增加校验码。比较简单的校验码有:
- 奇偶校验
- 累加和校验
奇偶校验
奇偶校验需要增加一位校验位。分为 2 种实现:
- 奇校验（odd parity）：让传输的数据（包含校验位）中1的个数为奇数。
- 偶校验（even parity）：让传输的数据（包含校验位）中1的个数为偶数。
以消息10101010为例，如果是奇校验，因为消息中存在 4 个 1，所以需要在消息后面增加一个校验码1。如果是偶校验，那么就是增加一个校验码0。
累计和校验
累计和校验的实现方式有很多，最简单的就是, 每次通信数据包最后都加一个字节的校验数据，这个校验字节里的数据是通信数据包里所有数据的不进位累加和。CRC 也是一种校验和算法。
多项式运算
对任意的二进制数都可以构造与其对应的一个二进制系数多项式。例如10011B，其对应的二进制系数多项式为:
$$ P(x)=x^{4}+x+1 $$
下面先介绍下多项式运算(与四则运算不同的是多项式运算不考虑进位和借位):
- 多项式加法运算为：1+1=0，0+1=1，0+0=0，无进位，无借位；
- 多项式减法运算为：1-1=0，0-1=1，1-0=1，0-0=0，无进位，无借位。
多项式加减法相当于二进制中的逻辑异或运算。 多项式乘除法与普通乘除法一样演算，唯一的区别是，多项式乘法在部分积相加时按多项式加，多项式除法部分余数相减时按多项式减。来看几个例子:
- 多项式乘法
11*11:
11
x 11
-----
11
11 <--- 模二加法
-----
101
- 多项式除法
10011/111:
11 <--- 商
=====
10011
111 <--- 模二减法
-----
1111
111
-----
1 <--- 余数
CRC 算法
CRC 算法的基本思想就是将消息视为一串长的二进制数，然后用另一个固定的二进制数除以它，除法的余数作为校验和。CRC算法中的除法不是简单除法，是模二除法。
实际应用时，发送方和接收方按以下方式通信：
- 发送方和接收方在通信前，约定好一个预设整数作为除数。
- 发送方在发送前根据原始数据和约定好的除数进行模二除法运算生成余数（即CRC码），然后将其附加到原始数据后面一起发送给接收方。
- 接收方收到后将其模二除以约定好的除数，当且仅当余数为0时接收方认为没有差错。
假设传入的数据是字节0xC2=11000010B。事先约定的除数是100011101B。
- 由于除数有9位（因此这是CRC-8多项式），因此将8个零位附加到输入。
- 然后进行多项式除法计算，得到实际CRC值为0x0F。
11001011
================
1100001000000000
100011101
---------
100110010000000
100011101
----------
101111000000
100011101
---------
1100101000
100011101
---------
100010010
100011101
---------
1111 = 0x0F
因此发送方实际发送的是1100001000001111B。接收方在接收后需要将其除以10011B来进行CRC校验。
证明
设原始数据为 $D(x)$ ,约定好的除数为 $P(x)$ , $P(x)$ 最高次数为 $r$ ，多项式除法运算的余数为 $R(x)$ ，即 $R(x)=[2^{r}D(x)] \space \text{mod} \space P(x)$ , CRC码为 $F(x)$ ，实际发送的数据为 $T(x)$ 。显然，$T(x)=2^{r}D(x)+F(x)T(x)$ 。
所以CRC算法问题变为：求解 $F(x)$ 使 $T(x) \space \text{mod} \space P(x)=0$ 。(这里不考虑正负，所以取模和取余等效)
$$ T(x) \space \text{mod} \space P(x)\newline =[2^{r}D(x)+F(x)]\space \text{mod} \space P(x) \newline ={[2^{r}D(x) \space \text{mod} \space P(x)+ F(x) \space \text{mod} \space P(x)]} \space \text{mod} \space P(x) \newline = { R(x)+ F(x) \space \text{mod} \space P(x) } \space \text{mod} \space P(x) $$
令 $F(x) = R(x)$ 可得:
$$ { R(x)+ R(x) \space \text{mod} \space P(x) } \space \text{mod} \space P(x) \newline = [R(x) + R(x)] \space \text{mod} \space P(x) = 0 \space \text{mod} \space P(x) = 0 $$
所以 $F(x) = R(x) = [2^{r}D(x)] \space \text{mod} \space P(x)$
算法实现
要实现CRC算法，我们所要做的就是实现CRC除法。不能简单地使用机器上的除法指令有两个原因:
- 必须在CRC算法中做除法。
- 由于被除数可能有10兆字节长，而今天的处理器没有那么大的寄存器。
因此我们使用移位寄存器来实现 CRC 算法。移位寄存器具有固定的宽度，可以将其内容移位一位，移除右侧或左侧边界的位，并在释放位置移入新位。CRC使用左移位寄存器：当移位时，最高有效位从寄存器中弹出，位置MSB-1的位向左移动一个位置到位置MSB，位置MSB-2的位到MSB-1，以此类推。最低有效位的位是空的，输入流的下一个位被移进来。
MSB LSB
--- --- --- -- -- ---
<-- | | | |... ... | | <-- (shift in input message bits)
--- --- --- -- -- ---
MSB（Most Significant Bit） 是二进制数中的最高有效位，代表数值的最高权重或最高位值。 LSB（Least Significant Bit） 是二进制数中的最低有效位，代表数值的最低权重或最低位值。
使用移位寄存器计算CRC的过程如下：
- 用0初始化寄存器。
- 在输入流中逐位移位。如果弹出的MSB是
1，则将寄存器值与生成器多项式进行异或。 - 如果所有输入位都被处理，CRC移位寄存器包含CRC值。
下面举个例子:
1. 用 0 初始化 CRC-8
--- --- --- --- --- --- --- ---
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | <-- b1100001000000000
--- --- --- --- --- --- --- ---
2. 左移一位. 因为MSB = 0, 继续移位
--- --- --- --- --- --- --- ---
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | <-- b100001000000000
--- --- --- --- --- --- --- ---
3. 重复上面的步骤，直到 MSB=1, 寄存器状态如下:
--- --- --- --- --- --- --- ---
| 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | <-- b00000000
--- --- --- --- --- --- --- ---
4. 左移寄存器. MSB 弹出 1:
--- --- --- --- --- --- --- ---
1 <- | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | <-- b0000000
--- --- --- --- --- --- --- ---
对CRC 寄存器(包含弹出的MSB) b110000100 和多项式 b100011101 进行异或计算得到b010011001 = 0x99. 将寄存器值更新为 b010011001(注意忽略了 MSB):
--- --- --- --- --- --- --- ---
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | <-- b0000000
--- --- --- --- --- --- --- ---
5. 左移寄存器. MSB 弹出 1 : b100110010 ^ b100011101 = b000101111 = 0x2F:
--- --- --- --- --- --- --- ---
| 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | <-- b000000
--- --- --- --- --- --- --- ---
6. 左移寄存器直到 1 出现在 MSB 位置:
--- --- --- --- --- --- --- ---
| 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | <-- b0000
--- --- --- --- --- --- --- ---
7. 左移寄存器. MSB 弹出 1: b101111000 ^ b100011101 = b001100101 = 0x65:
--- --- --- --- --- --- --- ---
| 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | <-- b000
--- --- --- --- --- --- --- ---
8. 左移寄存器直到 1 出现在 MSB 位置:
--- --- --- --- --- --- --- ---
| 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | <-- b00
--- --- --- --- --- --- --- ---
9. 左移寄存器.MSB 弹出 1: b110010100 ^ b100011101 = b010001001 = 0x89:
--- --- --- --- --- --- --- ---
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | <-- b0
--- --- --- --- --- --- --- ---
10. 左移寄存器.MSB 弹出 1: b10001001 ^ b100011101 = b000001111 = 0x0F:
--- --- --- --- --- --- --- ---
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | <-- <empty>
--- --- --- --- --- --- --- ---
所有的 bits 都被处理, 算法终止。这时候左移寄存器中的值就是 CRC 计算结果 0x0F.
CRC-8 算法实现
根据上面的算法，可以写出如下实现:
public static final byte generator_8 = 0x1D;
public static byte crc8BitShiftReg(byte[] byteVal)
{
byte crc = 0; /* init crc register */
byte[] data = new byte[byteVal.length+1];
System.arraycopy(byteVal, 0, data, 0, byteVal.length);
data[byteVal.length+1] = 0x00;
for(byte b : data)
{
for (int i = 7; i >= 0; i--)
{
/* 检查 MSB ==1 ? */
if ((crc & 0x80) != 0)
{
crc = (byte)(crc << 1);
/* 读入 1 位
* 如果是 1 , 设置 LSB 为 1.
* 如果是 0 , 设置 LSB 为 0.
*/
crc = ((byte)(b & (1 << i)) != 0) ? (byte)(crc | 0x01) : (byte)(crc & 0xFE);
// 异或计算
crc = (byte)(crc ^ generator_8);
}
else
{
// crc 左移 1 位
crc = (byte)(crc << 1);
crc = ((byte)(b & (1 << i)) != 0) ? (byte)(crc | 0x01) : (byte)(crc & 0xFE);
}
}
}
return crc;
}改进
先考虑单 Byte 信息的场景:
- 把CRC的值给成信息的值 那么就不用一上来就移位了
- 由于移位的时候信息后面会自动不零 所以也不用在后面补零了
public static final byte generator_8 = 0x1D;
public static byte crcByte(byte byteVal)
{
// 省去了一开始的 8 次 移位
byte crc = byteVal;
for (int i = 0; i < 8; i++) {
if ((crc & 0x80) != 0) {
// 每一次MSB都是会异或得0,其实是把信息的最高位和多项式的多高位一起去掉了。
// 所以每一次信息都是先移位在异或。
crc = (byte) ((crc << 1) ^ generator_8);
}
else {
// 左移
crc <<= 1;
}
}
return crc;
}多个字节怎么处理？先来看个例子(消息是[0x01, 0x02]):
// 先看第一个 Byte 的 CRC 结果
000000010000000000000000
100011101
---------
000011101
000000010000001000000000
100011101
---------
0000111110000 ->000011111 = 000011101 ^ 00000010
100011101
---------
0111011010
100011101
---------
0110001110
100011101
---------
0100100110
100011101
---------
0001110110 = 0x76
多字节时，实际上是当前 CRC结果 异或 下一个字节，然后再进行 CRC 除法计算。
public static final byte generator_8 = 0x1D;
public static byte crc8ByteShift(byte[] bytes)
{
byte crc = 0;
for (byte currByte : bytes) {
/* XOR-in the next input byte */
crc ^= currByte;
for (int i = 0; i < 8; i++) {
if ((crc & 0x80) != 0) {
crc = (byte) ((crc << 1) ^ generator_8);
}
else {
crc <<= 1;
}
}
}
return crc;
}查表法加速
到目前为止，算法是相当低效的，因为它是按 bit工作的。对于较大的输入数据，这可能相当慢。由于一个字节只能有256个不同的值且多项式除数是固定的。因此可以提前计算出每个 byte 和 generator 异或的结果。
public static final byte generator_8 = 0x1D;
public static final byte[] crcTable_8 = calCrc8Table();
public static byte[] calCrc8Table()
{
byte[] crcTable = new byte[256];
for (int dividend = 0; dividend < 256; dividend++)
{
byte currByte = (byte)dividend;
for (byte bit = 0; bit < 8; bit++)
{
if ((currByte & 0x80) != 0)
{
currByte <<= 1;
currByte ^= generator_8;
}
else
{
currByte <<= 1;
}
}
crcTable[dividend] = currByte;
}
return crcTable;
}
public static byte crc8ByteByTable(byte[] bytes)
{
byte crc = 0;
for (byte b : bytes) {
byte data = (byte)(b ^ crc);
crc = (byte)(crcTable_8[data]);
}
return crc;
}速度的提高是以预先计算表的处理时间和256字节元素的更高内存消耗为代价的，但这是值得的。
CRC 拓展
CRC值的位数越多，发生冲突的概率就越小：对于CRC-8，只有256个不同的CRC值。这意味着如果数据在发送方和接收方之间受到干扰或修改，则修改后的数据流与原始数据流具有相同的CRC值的概率为1/256。
CRC-16
如果我们想将其从CRC-8扩展到CRC-16，对实现有什么影响？
- CRC-16使用具有17项的16次多项式，但与CRC-8类似，最高有效位隐含为1。因此生成器多项式和需要16位长度。
- 下一个输入字节（8bit）与生成器多项式和如何异或。
先来看个例子(generator=0x1021,值是{0x01, 0x02}):
00000001000000100000000000000000
10001000000100001
-----------------
00001001000100001 = 0x1221 (第一个 Byte 的 CRC 值)
10001000000100001
-----------------
00011001000110001
10001000000100001
-----------------
01000000110101001
10001000000100001
-----------------
00001001101110011 = 0x1373 (最终的 CRC 值)
00000001000000000000000000000000
10001000000100001
-----------------
00001000000100001
// 可以发现结果是将输入和中间 CRC 的高 8 位进行计算得到
00001000000100001 ^ (00000010 <<8) = 00001001000100001
CRC-16 算法实现如下:
// 简单计算
public static short crc16ByteShift(byte[] bytes)
{
short crc = 0;
for (byte b : bytes) {
crc ^= (short) (b << 8);
for (int i = 0; i < 8; i++) {
if ((crc & 0x8000) != 0) {
crc = (short) ((crc << 1) ^ generator_16);
}
else {
crc <<= 1;
}
}
}
return crc;
}
// 查表法
public static short[] calCrc16Table()
{
short[] crcTable = new short[256];
for (int dividend = 0; dividend < 256; dividend++) {
short curByte = (short) (dividend << 8);
for (byte bit = 0; bit < 8; bit++) {
if ((curByte & 0x8000) != 0) {
curByte <<= 1;
curByte ^= generator_16;
}
else {
curByte <<= 1;
}
}
crcTable[dividend] = curByte;
}
return crcTable;
}
public static short crc16ByteByTable(byte[] bytes)
{
short crc = 0;
for (byte b : bytes) {
/* equal: ((crc ^ (b << 8)) >> 8), MSB是查找表的索引*/
byte pos = (byte) ((crc >> 8) ^ b);
crc = (short) ((crc << 8) ^ (crcTable_16[pos]));
}
return crc;
}性能
目前常用的 CRC 算法是 CRC32，它可以把一个字符串哈希成 32 位的值。CRC32 的碰撞率要比 MurMurHash3（32位）低，可惜它的运算速度跟 MD5 差不多。一个 32 位的哈希值，再怎么样，碰撞的概率还是比 128 位的多得多。更何况选用非加密哈希算法，运算速度往往是首先考虑的。看样子 CRC32 要出局了。
好在 CRC 系列一向有硬件加持。只要 CPU 支持 sse4.2 特性，就能使用 mm_crc32* 这一类硬件原语。（参见 Intel 的 文档，更详细的用法可以在网上搜到）硬件加持之后，CRC32 的计算速度可以达到十数倍以上的提升。换个说法，就是有硬件加持的 CRC32，比 MurMurHash3 要快。
不过要注意的是，有 sse4.2 加持的是 CRC32c，它是 CRC32 的一个变种。CRC32c 跟我们通常用的 CRC32 并不兼容。所以如果你要编写的程序会持久化 CRC32 哈希值，在使用硬件加速之前先关注这一点。
参考
相关内容
如果你觉得这篇文章对你有所帮助，请我一杯咖啡吧~
微信支付
支付宝