CRC校验原理探究与算法实现

1. 源起

前面我曾经写过一篇用mathjax输入竖式除法的文章,里面提到我当时正在写一个关于CRC校验原理的实验报告并且后期打算发出来,后面也再想像CRC校验这种相对底层的功能大家应该都是直接调用库函数了吧,应该是用不到的,但是后来又想到了解一下底层原理终究不是一件坏事情,所以还是发出来啦。

2. 内容概括

毕竟是为了了解原理而不是写出一个能用的CRC校验的程序,因此这篇文章主要是介绍原理,代码实现后面会给出但是不会详细说明(不过有了原理配合代码应该还是比较容易看懂的2333)。整篇文章大概分为如下的几部分:

  1. 模二运算
  2. 基本原理
  3. 算例演示
  4. 改进、加速与完善。

3. 模二运算

模二运算是整个CRC校验过程种的最基础的运算, 其核心思想是不考虑进位和借位, 只在本位上进行运算, 这中运算方式极大的简化了算法的实现过程, 并提高了计算效率. 其具体法则如下

  1. 模二加减运算

    模二加减运算得到的结果相同, 不考虑借位和进位, 其运算规则如下

  2. 模二乘运算

    模二乘法即按照模二加法求部分积之和, 不考虑进位.

  3. 模二除运算

    模二除法即按照模二减法求部分余数, 不考虑借位. 其余所有运算规则和二进制除法相同.

4. CRC校验的基本原理

CRC码由有效信息位和校验位组成, 其编码方式如下所述

  1. 先将位有效信息表达为多项式

    上式种或者.

  2. 左移位, 可以表示成. 右边的位用来放置校验位. 其中的取值应满足.

事实上这个的关系只是为了保证检错能力而设置的, 在某些情况下(尤其是在文件校验的时候)并不会考虑这个关系.

  1. 选择一个生成多项式, 其最高次幂等于校验位的位数, 最低次幂等于, 即必须是位.

  2. 用多项式除以生成多项式所得的余数作为校验码.

基于上面的描述, 我们来看一下CRC校验进行检错的原理. 假设有效信息为, 则其左移位即为, 如果我们假设的商为, 余数为, 则有

最后把余数追加在后面相当于直接加上. 这样最后加上余数后的CRC码的值为

考虑到执行的加法是模二加法, 从而有

从而进一步有

从而如果信息传输无误, 则一定可以被除尽. 如果除不尽, 则说明信息传输有误.

5. 算例

语言来描述怎么去计算CRC还是太容易让人云里雾里, 不如直接看一个例子2333

求有效信息1100的码, 选择生成多项式.

生成多项式为四位, 则需要在原信息后补三个0, 然后执行模二除法如下

最后得到余数010, 从而该信息的CRC码为1100010.

6. 改进、加速与完善

理论上讲, 前面的介绍已经足以让我们写出程序来计算CRC的值, 但是实际实现起来会发现还是有一些问题的。 首先 第一个面临的大问题就是CRC计算总全部都是位运算, 操作要精确到每一个bit,而且这个bit通常还不一定是8bit为一组的那种bit,这就是一个比较麻烦的事情, 尽管我们可以利用像x = x | 0x0800之类的办法来进行某一位的修改但是这种方法显然是严重降低效率的,所有首先我们需要解决的第一个问题就是怎么高效的实现成组的位操作。

6. 1 改进位操作问题

如果你学过计算机组成原理这门课程的话这个改进应该完全不是问题, 因为在计算机组成原理课程中是学习过计算机计算乘法、除法(非阵列形式)的办法,而这里的模二除法不过是计算机组成原理课程中除法的一个弱化版本, 实现起来更为简单。当然如果你没学过这门课也没啥关系,这里我还是多啰嗦一下,把整个计算过程详细说出来。

我们还是以前面的那个算例为例来介绍如何进行计算, 具体计算方法如下:

  1. 首先初始化一个CRC寄存器, 其长度要不小于信息长度和生成多项式长度(实际上生成多项式中因为第一位一定是1所以按照惯例一般省略第一位而且计算长度的时候也不包括第一位, 本例中(也就是前面那个算例)生成多项式为,实际上计算中用的是去掉首位的1,为011,而其长度也视为3 )中最大的那一个. 本例中初始化为1100.

  2. 后续的除法操作可以按照下面的方式进行: 如果CRC寄存器中的第一位为1, 则将其左移一位(最后一位补0)后与生成多项式左端对齐后进行异或.(模二加法实际上就是异或运算). 在本例中CRC寄存器第一位是1, 则左移一位后变为1000, 然后与生成多项式011先左端对齐然后异或, 即

    从而得到更新后的CRC寄存器的值1110.

  3. 重复2过程, 重复次数正好为信息长度. 本例中重复四次

本例中完整的计算过程如下:

因为余数为3位, 因此直接从CRC寄存器中提取前三位即可得到最终结果010, 与前面的计算相符

实际上从计算过程中也可以看出这种算法实际上和前面提到的竖式的模二除法本质上是完全相同的.

看到这里有读者可能会问现在仍然不是完整的8bit啊,在实际计算过程中仍然不能方便计算啊。但是这里可以注意到,在CRC寄存器中添加若干位的0其实是完全不影响计算结果的, 因此可以随随便便在后面补0. 另外生成多项式因为在计算中都是易或操作,在他的后面补0也不会影响计算结果, 所以可以直接补0补到8bit整数倍就可以了。现在再来看前面的操作中只会用到位移和易或,而且已经是8bit的完整运算了,这样CRC校验就可以相对比较高效的完成了。

但是前面的计算过程还是有局限性的,首先最大的一个问题就是信息实际上往往都比较长(在计算机网络中对1500byte的数据进行校验是非常正常的),如果要对这么长的数据执行左移还是一件比较麻烦并且占用资源相对较多的事情。而且CRC还曾经被用于文件校验(包括现在你下载一个7zip依然可以看到其附带的CRC32文件校验的功能),而如果你面临的是一个数十GB的文件你甚至不能把这个文件载入到内存,而对其执行位移操作更是天方夜谭。其次信息的长度通常来说并不固定, 那么我们去编程实现的时候还得把这个CRC寄存器的长度变成不固定的, 也带来了编程上的不方便,而如果能对信息进行分段计算, 前面的问题貌似就都可以解决了,这也就是下面的改进:分段计算

6.2 分段计算

在CRC校验中有一个很好的性质就是可以分段进行处理, 我们假设一条信息可以被拆分为两段, 其中. 那么这一整条信息可以按照如下的方式分段进行:

  1. 首先计算的CRC码, 得到余数值.

  2. 将余数左移位(其中是前面提到的, 是生成多项式不计算第一位1的时候的宽度), 然后加到上的得到.

  3. 计算CRC码, 得到余数.

注意到前面第二步实际上是有可能小于的。当时问题不大, 按照前面说的计算即可。 当时也就是信息长度小于生成多项式长度的情况,这时候就需要把信息左移一位然后加上余数得到再进行第三步的运算, 而且第三步里面除的次数仍然等于原来的位数(或者说按照传统算法在信息后面补零的时候少补一个), 这个过程如果仔细考虑一下实际上是和信息右移一位然后不截掉多余位是一致的

  1. 余数即为的余数, 也就是原信息待求的余数.

在看严格证明之前其实可以找一个算例看一下这个算法实际上是在干什么, 实际上这个算法仅仅只是把竖式除法拆成了两部分来计算而已,并没有什么骚操作2333

下面我们将看到这种分段方式为何是可行的. 首先对于第一步, 对计算CRC码, 设其商为, 从而有

第二步种我们对左移位并加到上得到, 我们实际上得到了

第三步中我们对计算CRC码, 我们实际上得到了

我们假设直接对计算CRC码得到的商为, 余数为. 为了看到实际上就等于, 把前面的带入的表达式中, 我们得到

从而显然的余数就是.

为了更直观的展示计算方法, 我们再来用一个例子来展示。(信息: 1101, 多项式 1011)

首先是不分段的传统的计算方法:

分两段进行计算, 第一段信息为, 第二段为。 第一段的计算结果如下所示:

这里是的情况, 01左移一位变成010, 加上前面的余数101得到111, 然后除两次进行计算,如下所示(这里用的是少补一个0的计算方法):

从而得出余数为001, 和前面的计算结果是一致的。不过其实仔细看一下这个式子, 第二个式子的内容和前面标准算法的后半部分是一模一样的,这也印证了前面那句分段计算就是简单地把一个竖式拆成两个来算而已的说法。

至此,前面提到的问题完美解决。但是, 既然能分段计算, 那么是不是这个算法还有改进的空间呢?假定按照字节分段, 这样每次面临的信息实际上只有256种不同的情况, 因而如果能把这些情况对应的计算结果直接储存起来(这个代价实际上是很低的),我们就可以避免在计算CRC的过程中不断地进行完位移等操作, 只需要查表就可以了。但是实际上从前面的分段计算可以看出来计算结果和上一阶段的余数(也就是CRC寄存器中的值)还是有关系的,而CRC寄存器通常位宽是比较大的,所以并不能直接简单的查表。不过经过一定的计算我们可以发现查表法仍然是可行的, 不过方法需要稍微动一下。这也就是下面的改进:查表法。

6.3 查表法加速

为了使介绍更加直观, 我们以CRC32的计算过程来说明如何规避初始值的问题来进行查表计算. 假设生成多项式长度为33bit, 则CRC寄存器长度为32bit, 数据长度为8bit, 假设上一次的余数为, 这一次输入的数据为, 则在本轮计算中, 实际计算的内容为

的长度也就是CRC寄存器的长度, 记为32bit, 我们把分为两段, 第一段为前8bit, 记为, 第二段为后面的24bit, 记为, 这样就可以表示为

带入前面的的表达式中, 我们有

这个结果是我们非常希望看到的, 因为前面一半()是我们已经在表格中储存的内容, 而后面的一部分, 我们已经知道是24bit的, 则即为32bit的, 而为33bit的, 也就是说这个求余之后就是. 这样最后我们把这个余数和前面查表得到的余数模二加法(也就是异或)就可以解决问题了.

6.4 改进

前面我们一直在讨论的是经典的CRC校验计算, 不过这个计算实际上还是有些问题的. 比如显然在数据前面添加若干个0并不会影响计算结果, 而这是我们不希望看到的. 另外就是输出的时候为了适应具体环境还有一些配置项。因此成熟的CRC算法一般都有四个选项: 输入按字节反转、输出按位反转 初始值和结果异或值。其中输入按字节翻转就是对输入的数据按照字节为单位进行分段,字节顺序不变, 只是对每一个字节内部的位的顺序进行翻转,如1100 1010 0001 0100 翻转为0101 0011 0010 1000, 输出按位翻转就是整体输出的内容按照位翻转,,如1100 1010 0001 0100 翻转为 0010 1000 0101 0011. 初始值主要是为了分段计算的方便,结果异或值就是对结果与这个给定的值进行异或。

7. 代码

前面说了这么多其实特别容易让人糊涂, 还有就是细节也没办法详细的说明,talk is cheap, I’ll show you the code. 结合代码来看就明朗很多了2333

template<typename PolyType>
class CRC
{
public:
CRC(void)
{
init();
}
CRC(PolyType& initial, PolyType& polynomial, PolyType& xorout, int refin, int refout, size_t _width = sizeof(PolyType)<<3)
{
init();
create(initial, polynomial, xorout, refin, refout, _width);
}
public:
template<typename DataType>
void calculate(DataType& data)
{
BYTE* DataPointer = reinterpret_cast<BYTE*>(&data);
size_t DataSize = sizeof(DataType);
BYTE actualData = 0x00;
for(size_t i = 0; i < DataSize; i++)
{
if(RefIn)
{
actualData = reverseTable[DataPointer[i]];
}
else
{
actualData = DataPointer[i];
}
BYTE index = (CRCreg>>((sizeof(PolyType) - 1)<<3))^actualData;
CRCreg <<= 8;
CRCreg ^= crcTable[index];
}
}
void create(PolyType& initial, PolyType& polynomial, PolyType& xorout, int refin, int refout, size_t _width = sizeof(PolyType)<<3)
{
CRCreg = initial<<((sizeof(PolyType)<<3) - _width);
CRCpoly = polynomial<<((sizeof(PolyType)<<3) - _width);
XORout = xorout<<((sizeof(PolyType)<<3) - _width);
RefIn = refin;
RefOut = refout;
width = _width;
ByteWidth = (width + 7)>>3;
makeTable();
}
void SetCRCreg(PolyType& initial)
{
CRCreg = initial;
}
PolyType GetCRCreg(void)
{
PolyType ret = 0x00;
if(RefOut)
{
BYTE* regPointer = (BYTE*) &CRCreg;
BYTE* retPointer = (BYTE*) &ret;
for(size_t i = 0; i < sizeof(PolyType); i++)
{
retPointer[sizeof(PolyType) - 1 - i] = reverseTable[regPointer[i]];
}
ret <<= sizeof(PolyType) * 8 - width;
}
else
{
ret = CRCreg;
}
ret ^= XORout;
return ret;
}
void reset(void)
{
init();
}
private:
void init(void)
{
RefIn = 0;
RefOut = 0;
width = 0;
ByteWidth = 0;
PolyType one;
one = 0x01;
mask = one<<((sizeof(PolyType)<<3) - 1);
}
void makeTable(void)
{
for(size_t i = 0; i < 256; i++)
{
BYTE cur = (BYTE) i;
PolyType reg = cur;
reg <<= ((sizeof(PolyType) - 1)<<3);
for(size_t j = 0; j < 8; j++)
{
if(reg&mask)
{
reg <<= 1;
reg ^= CRCpoly;
}
else
{
reg <<= 1;
}
}
crcTable[i] = reg;
}
static BYTE BitMask[8] = {0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80};
for(size_t i = 0; i < 256; i++)
{
BYTE cur = (BYTE) i;
BYTE write = 0x00;
for(size_t j = 0; j < 8; j++)
{
if((cur & BitMask[j]))
{
write |= BitMask[7 - j];
}
}
reverseTable[i] = write;
}
}
private:
PolyType CRCreg;
PolyType CRCpoly;
PolyType XORout;
PolyType mask;
int RefIn;
int RefOut;
size_t width;
size_t ByteWidth;
PolyType crcTable[256];
BYTE reverseTable[256];
};

这是一部分代码我直接贴在这里了, 我这个人不怎么喜欢在代码上写注释所以就将就看吧…不过基本变量名都能自己解释自己的含义, 配合前面的说明应该还行。这段代码就是个class, 然后为了不失一般性CRCreg的数据类型用了个模板这样你就可以自己实例化出各种宽度的CRC寄存器。完整的代码我会在文末的附件中给出下载链接, 这里就不给出来了。

8. 附件

给懒人准备个福利,本文对应的完整代码可以在这里查看:

CRC示例代码:https://static.zmyme.com/code/crc/crcexample.cpp

在这份代码里面是前面的CRC类以及几个二进制打印的函数, 然后在main函数里面利用前面的那个类做了个CRC32的文件校验, 校验结果和7zip是一致的。整个就是一个单文件, 直接编译即可。

9. 参考资料

CRC在线计算网站:CRC(循环冗余校验)在线计算: http://www.ip33.com/crc.html

评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注