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-32？

---

循环冗余校验（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作为检错手段。

 

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

---

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

 

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

---

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

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

最常用的多项式长度为：

• 9位（CRC-8）
• 17位（CRC-16）
• 33位（CRC-32）
• 65位（CRC-64）

 

CRC32源代码

---

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

/* crc32.cCopyright (C) 2009-2020 Free Software Foundation, Inc.This file is part of the libiberty library.This file is free software; you can redistribute it and/or modifyit under the terms of the GNU General Public License as published bythe Free Software Foundation; either version 2 of the License, or(at your option) any later version.In addition to the permissions in the GNU General Public License, theFree Software Foundation gives you unlimited permission to link thecompiled version of this file into combinations with other programs,and to distribute those combinations without any restriction comingfrom the use of this file.  (The General Public License restrictionsdo apply in other respects; for example, they cover modification ofthe file, and distribution when not linked into a combinedexecutable.)This program is distributed in the hope that it will be useful,but WITHOUT ANY WARRANTY; without even the implied warranty ofMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See theGNU General Public License for more details.You should have received a copy of the GNU General Public Licensealong with this program; if not, write to the Free SoftwareFoundation, Inc., 51 Franklin Street - Fifth Floor, Boston, MA 02110-1301, USA.
*/#ifdef HAVE_CONFIG_H
#include "config.h"
#endif#include "libiberty.h"/* This table was generated by the following program.#include <stdio.h>intmain (){unsigned int i, j;unsigned int c;int table[256];for (i = 0; i < 256; i++){for (c = i << 24, j = 8; j > 0; --j)c = c & 0x80000000 ? (c << 1) ^ 0x04c11db7 : (c << 1);table[i] = c;}printf ("static const unsigned int crc32_table[] =\n{\n");for (i = 0; i < 256; i += 4){printf ("  0x%08x, 0x%08x, 0x%08x, 0x%08x",table[i + 0], table[i + 1], table[i + 2], table[i + 3]);if (i + 4 < 256)putchar (',');putchar ('\n');}printf ("};\n");return 0;}For more information on CRC, see, e.g.,http://www.ross.net/crc/download/crc_v3.txt.  */static const unsigned int crc32_table[] =
{0x00000000, 0x04c11db7, 0x09823b6e, 0x0d4326d9,0x130476dc, 0x17c56b6b, 0x1a864db2, 0x1e475005,0x2608edb8, 0x22c9f00f, 0x2f8ad6d6, 0x2b4bcb61,0x350c9b64, 0x31cd86d3, 0x3c8ea00a, 0x384fbdbd,0x4c11db70, 0x48d0c6c7, 0x4593e01e, 0x4152fda9,0x5f15adac, 0x5bd4b01b, 0x569796c2, 0x52568b75,0x6a1936c8, 0x6ed82b7f, 0x639b0da6, 0x675a1011,0x791d4014, 0x7ddc5da3, 0x709f7b7a, 0x745e66cd,0x9823b6e0, 0x9ce2ab57, 0x91a18d8e, 0x95609039,0x8b27c03c, 0x8fe6dd8b, 0x82a5fb52, 0x8664e6e5,0xbe2b5b58, 0xbaea46ef, 0xb7a96036, 0xb3687d81,0xad2f2d84, 0xa9ee3033, 0xa4ad16ea, 0xa06c0b5d,0xd4326d90, 0xd0f37027, 0xddb056fe, 0xd9714b49,0xc7361b4c, 0xc3f706fb, 0xceb42022, 0xca753d95,0xf23a8028, 0xf6fb9d9f, 0xfbb8bb46, 0xff79a6f1,0xe13ef6f4, 0xe5ffeb43, 0xe8bccd9a, 0xec7dd02d,0x34867077, 0x30476dc0, 0x3d044b19, 0x39c556ae,0x278206ab, 0x23431b1c, 0x2e003dc5, 0x2ac12072,0x128e9dcf, 0x164f8078, 0x1b0ca6a1, 0x1fcdbb16,0x018aeb13, 0x054bf6a4, 0x0808d07d, 0x0cc9cdca,0x7897ab07, 0x7c56b6b0, 0x71159069, 0x75d48dde,0x6b93dddb, 0x6f52c06c, 0x6211e6b5, 0x66d0fb02,0x5e9f46bf, 0x5a5e5b08, 0x571d7dd1, 0x53dc6066,0x4d9b3063, 0x495a2dd4, 0x44190b0d, 0x40d816ba,0xaca5c697, 0xa864db20, 0xa527fdf9, 0xa1e6e04e,0xbfa1b04b, 0xbb60adfc, 0xb6238b25, 0xb2e29692,0x8aad2b2f, 0x8e6c3698, 0x832f1041, 0x87ee0df6,0x99a95df3, 0x9d684044, 0x902b669d, 0x94ea7b2a,0xe0b41de7, 0xe4750050, 0xe9362689, 0xedf73b3e,0xf3b06b3b, 0xf771768c, 0xfa325055, 0xfef34de2,0xc6bcf05f, 0xc27dede8, 0xcf3ecb31, 0xcbffd686,0xd5b88683, 0xd1799b34, 0xdc3abded, 0xd8fba05a,0x690ce0ee, 0x6dcdfd59, 0x608edb80, 0x644fc637,0x7a089632, 0x7ec98b85, 0x738aad5c, 0x774bb0eb,0x4f040d56, 0x4bc510e1, 0x46863638, 0x42472b8f,0x5c007b8a, 0x58c1663d, 0x558240e4, 0x51435d53,0x251d3b9e, 0x21dc2629, 0x2c9f00f0, 0x285e1d47,0x36194d42, 0x32d850f5, 0x3f9b762c, 0x3b5a6b9b,0x0315d626, 0x07d4cb91, 0x0a97ed48, 0x0e56f0ff,0x1011a0fa, 0x14d0bd4d, 0x19939b94, 0x1d528623,0xf12f560e, 0xf5ee4bb9, 0xf8ad6d60, 0xfc6c70d7,0xe22b20d2, 0xe6ea3d65, 0xeba91bbc, 0xef68060b,0xd727bbb6, 0xd3e6a601, 0xdea580d8, 0xda649d6f,0xc423cd6a, 0xc0e2d0dd, 0xcda1f604, 0xc960ebb3,0xbd3e8d7e, 0xb9ff90c9, 0xb4bcb610, 0xb07daba7,0xae3afba2, 0xaafbe615, 0xa7b8c0cc, 0xa379dd7b,0x9b3660c6, 0x9ff77d71, 0x92b45ba8, 0x9675461f,0x8832161a, 0x8cf30bad, 0x81b02d74, 0x857130c3,0x5d8a9099, 0x594b8d2e, 0x5408abf7, 0x50c9b640,0x4e8ee645, 0x4a4ffbf2, 0x470cdd2b, 0x43cdc09c,0x7b827d21, 0x7f436096, 0x7200464f, 0x76c15bf8,0x68860bfd, 0x6c47164a, 0x61043093, 0x65c52d24,0x119b4be9, 0x155a565e, 0x18197087, 0x1cd86d30,0x029f3d35, 0x065e2082, 0x0b1d065b, 0x0fdc1bec,0x3793a651, 0x3352bbe6, 0x3e119d3f, 0x3ad08088,0x2497d08d, 0x2056cd3a, 0x2d15ebe3, 0x29d4f654,0xc5a92679, 0xc1683bce, 0xcc2b1d17, 0xc8ea00a0,0xd6ad50a5, 0xd26c4d12, 0xdf2f6bcb, 0xdbee767c,0xe3a1cbc1, 0xe760d676, 0xea23f0af, 0xeee2ed18,0xf0a5bd1d, 0xf464a0aa, 0xf9278673, 0xfde69bc4,0x89b8fd09, 0x8d79e0be, 0x803ac667, 0x84fbdbd0,0x9abc8bd5, 0x9e7d9662, 0x933eb0bb, 0x97ffad0c,0xafb010b1, 0xab710d06, 0xa6322bdf, 0xa2f33668,0xbcb4666d, 0xb8757bda, 0xb5365d03, 0xb1f740b4
};/*
@deftypefn Extension {unsigned int} crc32 (const unsigned char *@var{buf}, @int @var{len}, unsigned int @var{init})
Compute the 32-bit CRC of @var{buf} which has length @var{len}.  The
starting value is @var{init}; this may be used to compute the CRC of
data split across multiple buffers by passing the return value of each
call as the @var{init} parameter of the next.
This is used by the @command{gdb} remote protocol for the @samp{qCRC}
command.  In order to get the same results as gdb for a block of data,
you must pass the first CRC parameter as @code{0xffffffff}.
This CRC can be specified as:Width  : 32Poly   : 0x04c11db7Init   : parameter, typically 0xffffffffRefIn  : falseRefOut : falseXorOut : 0
This differs from the "standard" CRC-32 algorithm in that the values
are not reflected, and there is no final XOR value.  These differences
make it easy to compose the values of multiple blocks.
@end deftypefn
*/unsigned int
xcrc32 (const unsigned char *buf, int len, unsigned int init)
{unsigned int crc = init;while (len--){crc = (crc << 8) ^ crc32_table[((crc >> 24) ^ *buf) & 255];buf++;}return crc;
}

 

CRC32算法详细推导

https://blog.csdn.net/sparkliang/article/details/5671510

---

CRC 算法的数学基础

CRC 算法的数学基础就不再多啰嗦了，到处都是，简单提一下。它是以 GF(2) 多项式算术为数学基础的， GF(2) 多项式中只有一个变量 x ，其系数也只有 0 和 1 ，比如：

1 *x^6 + 0*x^5 + 1*x^4 + 0*x^3 + 0*x^2 +1*x^1 + 1*x^0= x^6 + x^4 + x + 1

加减运算不考虑进位和退位。说白了就是下面的运算规则：

0 + 0 = 0    0 - 0 = 0
0 + 1 = 1    0 - 1 = 1
1 + 0 = 1    1 - 0 = 1
1 + 1 = 0    1 - 1 = 0

看看这个规则，其实就是一个异或运算。

每个生成多项式的系数只能是 0 或 1 ，因此我们可以把它转化为二进制形式表示， 比如 g(x)=x^4 + x + 1 ，那么 g(x) 对应的二进制形式就是 10011 ， 于是我们就把 GF(2) 多项式的除法转换成了二进制形式，和普通除法没有区别，只是加减运算没有进位和退位。

比如基于上述规则计算 11010/1001 ，那么商是 11 ，余数就是 101 ，简单吧。

 

CRC 校验的基本过程

---

采用 CRC 校验时，发送方和接收方用同一个生成多项式 g(x) ， g(x) 是一个 GF(2) 多项式，并且 g(x) 的首位和最后一位的系数必须为 1 。

CRC 的处理方法是：发送方用发送数据的二进制多项式 t(x) 除以 g(x) ，得到余数 y(x) 作为 CRC 校验码。校验时，以计算的校正结果是否为 0 为据，判断数据帧是否出错。设生成多项式是 r 阶的（最高位是 x^r ）具体步骤如下面的描述。

发送方：

• 1 ）在发送的 m 位数据的二进制多项式 t(x) 后添加 r 个 0 ，扩张到 m+ r 位，以容纳 r 位的校验码，追加 0 后的二进制多项式为  T(x) ；
• 2 ）用 T(x) 除以生成多项式 g(x) ，得到 r 位的余数 y(x) ，它就是 CRC 校验码；
• 3 ）把 y(x) 追加到 t(x) 后面，此时的数据 s(x) 就是包含了 CRC 校验码的待发送字符串；由于 s(x) = t(x) y(x) ，因此 s(x) 肯定能被 g(x) 除尽。

接收方：

• 1 ）接收数据 n(x) ，这个 n(x) 就是包含了 CRC 校验码的 m+r 位数据；
• 2 ）计算 n(x) 除以 g(x) ，如果余数为 0 则表示传输过程没有错误，否则表示有错误。从 n(x) 去掉尾部的 r 位数据，得到的就是原始数据。

生成多项式可不是随意选择的，数学上的东西就免了，以下是一些标准的 CRC 算法的生成多项式：

原始的 CRC 校验算法

---

根据多项式除法，我们就可以得到原始的 CRC 校验算法。假设生成多项式 g(x) 是 r 阶的，原始数据存放在 data 中，长度为 len 个 bit ， reg 是 r+1 位的变量。 以 CRC-4 为例，生成多项式 g(x)=x^4 + x + 1 ，对应了一个 5bits 的二进制数字 10011 ，那么 reg 就是 5 bits 。

reg[1] 表明 reg 的最低位， reg[r+1] 是 reg 的最高位。

通过反复的移位和进行除法，那么最终该寄存器中的值去掉最高一位就是我们所要求的余数。所以可以将上述步骤用下面的流程描述：

reg = 0;
data = data追加r个;
pos = 1;
while(pos <= len)
{if(reg[r+1] == 1) // 表明reg可以除以g(x){// 只关心余数，根据上面的算法规则可知就是XOR运算reg = reg XOR g(x);}// 移出最高位，移入新数据reg = (reg<<1) | (data[pos]);pos++;
}
return reg; // reg中的后r位存储的就是余数

 

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

---

由于最后只需要 r 位的余数，所以我们可以尝试构造一个 r 位的 reg ，初值为 0 ，数据 data 依次移入 reg[1] ，同时把 reg[r] 移出  reg 。

根据上面的算法可以知道，只有当移出的数据为 1 时， reg 才和 g(x) 进行 XOR 运算；于是可以使用下面的算法：

reg = 0;
data = data追加r个;
pos = 1;
while(pos < len)
{hi-bit = reg[r];// 移出最高位，移入新数据reg = (reg<<1) | (data[pos]);if(hi-bit == 1) // 表明reg可以除以g(x){reg = reg XOR g(x);}pos++;
}
return reg; // reg中存储的就是余数

这种算法简单，容易实现，对任意长度生成多项式的 G （ x ）都适用，对应的 CRC-32 的实现就是：

// 以4 byte数据为例
#define POLY 0x04C11DB7L // CRC32生成多项式
unsigned int CRC32_1(unsigned int data)
{unsigned char p[8];memset(p, 0, sizeof(p));memcpy(p, &data, 4);unsigned int reg = 0, idx = 0;for(int i = 0; i < 64; i++){idx = i/8;int hi = (reg>>31)&0x01; // 取得reg的最高位// 把reg左移1bit，并移入新数据到reg0reg = (reg<<1)| (p[idx]>>7);if(hi) reg = reg^POLY; // hi=1就用reg除以g(x)p[idx]<<=1;}return reg;
}

从 bit 扩张到 byte 的桥梁

---

但是如果发送的数据块很长的话，这种方法就不太适合了。它一次只能处理一个 bit 的数据，效率太低。考虑能不能每次处理一个 byte 的数据呢？事实上这也是当前的 CRC-32 实现采用的方法。

这一步骤是通往基于校验表方法的桥梁，让我们一步一步来分析上面逐 bit 的运算方式，我们把 reg 和 g(x) 都采用 bit 的方式表示如下：   

考虑把上面逐 bit 的算法执行 8 次，如果某次移出的不是 1 ，那么 reg 不会和 g(x) 执行 XOR 运算，事实上这相当于将 reg 和 0 执行了 XOR 运算。执行过程如下所示，根据 hi-bit 的值，这里的 G 可能是 g(x) 也可能是 0 。

从上面的执行过程清楚的看到，执行 8 次后， old-reg 的高 8bit 被完全移出， new-reg 就是 old-reg 的低 24bit 和数据 data 新移入的 8bit 和 G 一次次执行 XOR 运算所得到的。

       XOR 运算满足结合律，那就是： A XOR B XOR C = A XOR (B XOR C) ，于是我们可以考虑把上面的运算分成两步进行：

1 ）先执行 R 高 8bit 与 G 之间的 XOR 运算，将计算结果存入 X 中，如下面的过程所示。

2 ）将 R 左移 8bit ，并移入 8bit 的数据，得到的值就是  ，然后再与 X 做 XOR 运算。

根据 XOR 运算的结合率，最后的结果就等于上面逐 bit 的算法执行 8 次后的结果，根据这个分解，我们可以修改逐 bit 的方式，写出下面的算法。

// 以4 byte数据为例
#define POLY 0x04C11DB7L // CRC32生成多项式
unsigned int CRC32_2(unsigned int data)
{unsigned char p[8];memset(p, 0, sizeof(p));memcpy(p, &data, 4);unsigned int reg = 0, sum_poly = 0;for(int i = 0; i < 8; i++){// 计算步骤1sum_poly = reg&0xFF000000;for(int j = 0; j < 8; j++){int hi = sum_poly&0x80000000; // 测试reg最高位sum_poly <<= 1;if(hi) sum_poly = sum_poly^POLY;}// 计算步骤2reg = (reg<<8)|p[i];reg = reg ^ sum_poly;}return reg;
}

 

CRC32示例

---

1    83dcefb7
2    1ad5be0d
3    6dd28e9b123    884863d21234567890    261daee5