crc的全称为Cyclic Redundancy Check,循环冗余检验,用于核对数据传输过程中是否被更改或传输错误。

基础知识

假设我们要发送的15位的二进制为101001110100001,那么它可以表示成一个多项式:g(x) = x^14 + x^12 + x^9 + x^8 + x^7 + x^5 + 1,(这个和二进制一一对应,最后面的1相当于2的零次方。)

然后需要采用一个h(x),用上面不断的和g(x)进行模二除法(不借位,只进行异或操作),h(x)有很多种,例如CRC-8,CRC-3,CRC-32等等。

我们假设现在的h(x)采用CRC-8标准,那么h(x)= x^8 + x^7 + x^6 + x^4 + x^2 + 1 ,对应的二进制串为:111010101。

具体操作

上面我们大概知道了crc其实就是两个二进制的数字不断的进行模二除法,那么我们现在来计算上面中101001110100001,111010101这个例子:

计算过程比较繁琐,需要耐心看。我们从这些计算过程中可以得到一般的计算流程:

1.g需要根据h的最高位先向左移动x位。

2.如果首位(最左边的1位)是0,那么h为0,那么g直接向左移动一位得到结果;如果首位是1,那么h不为0,那么就先和h异或,再向左移动一位。

这个过程我们可以做如下简化:

background Layer 1 g 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 h g 0 1 1 0 1 0 0 0 0 0 0 1 0 0 g 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 1 0 1 0 1 h g 1 1 0 1 0 0 0 0 0 0 1 0 0 等效于 g 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 h g 0 1 1 0 0 0 1 0 1 0 0 1 0 0 等效于 g 0 h g 1 1 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0

上面我们计算中的h为111010101,我们做一个h`,h`为h去掉最高位(最左边的1位),那么h`为11010101,有了h`,在实际计算过程中,我们每次就可以先将g左移一位(无论0,还是1),然后再和h`异或。(这个操作很重要,因为实际计算就是这样来的,一定要理解透)

划分单元

现在我们将g中每4个划分成一组:

background Layer 1 g 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 B1 B2 B3 B4 B5 B6

我们现在来看一下计算完一组的情况:

background Layer 1 g 0 1 0 1 0 0 1 1 1 0 1 0 B1 B2 B3 h` 0 0 0 g 0 1 0 1 0 0 1 1 1 0 1 0 h` 0 1 0 1 0 1 0 0 g 0 1 1 0 0 1 1 0 1 1 1 0 h` 1 0 1 0 1 0 1 0 g 0 1 1 1 1 1 0 0 0 1 0 0 h` 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 1 1 1

经过4次迭代,B1完全消失了,现在我们比较关心B2和B3变成啥样了:

B2B3:0011 1010

h1: 0000 0000

h2: 0101 0111

h3: 1010 1010

h4: 1101 0101

现在的B2`B3`=B2B3^h1^h2^h3^h4。根据交换律,我们可以这样计算:B2`B3`=B2B3^(h1^h2^h3^h4),也就是先计算出h1,h2,h3,h4。而h1,h2,h3,h4的生成都和B1有关,现在我们看看如何计算h1^h2^h3^h4:

根据上面我们可以知道,如果我们有一个单元的内容和h`,我们就可以计算出h1^h2^h3^h4。上面的一个单元(4位),一共有2^4种情况,我们将可能的情况全部计算出来,使用的时候直接查询,这种方法就是查表法。下面我们看看上面的计算如何用查表法计算:

background Layer 1 g B1 B2 B3 B4 h` g B1 B2` B3` B4` F[B1h`] h` F[B2`h`] g B1 B2` B3`` B4`` h` F[B3``h`] r B1 B2` B3`` B4```

上面的F[**]就是直接通过查表法得到结果,现在看看具体的计算过程:

反向算法

上面计算的叫做正向计算,就是左边是高位,右边低位,计算的时候左对齐;然后实际中更多的是应用反向计算,即右边是高位,左边是低位,计算过程右对齐。

反向计算和正向计算有很多指标都不太一样,例如正向计算的h`和反向的h`就不一样,在CRC32中正向计算的时候h`位0x04C11DB7,反向的时候位0xEDB88320(全部是已经去掉最高位的h`,为什么是h`不是h,上面已经讲过)

反向计算的主要原理也是通过拆分单元,然后计算每个单元和h`,得到h1^h2^h3...,这里我们以CRC32为例,反向计算单元11001110和h`=》11101101 10111000 10000011 00100000(0xEDB88320):

我们可以看到和正向算法大体类似,只是对齐方式不同(高低位顺序不同)。

CRC32反向算法和之前的CRC8还有一点不同的地方,CRC32需要初始化值为0XFFFFFFFF,而CRC8的初始值为0,(这个是它算法规定的)。现在我们来看看一个手算CRC32的'12'(Ascii,也就说获取每个字符的Code码进行,'1'的Code码为49,'2'的Code码为50)

之前我们计算的时候,都是一次性在后面补充多少个0,但是在真实计算中,内容的长度不确定,都是一边剔除(剔除最右边单元),一边加入(从最左边加入)。

background Layer 1 g B4 B3 B2 B1 h` F[(B1^c1)h`] c1 g B4` B3` B2` h` F[(B2`^c2)h`] c2 B5 g B5` B4`` B3`` h` F[(B3``^c3)h`] B6 c3 .............

最后放CRC32的代码:

其中makeTable做的就是列出一个单元(8位,2^8中可能)和h`的结果,保存起来,用的时候直接获取。

CRC32负数问题

在CRC32中经常会看到很多的负数,例如,我们可以看到在crcTable中会有 -301047508, -1727442502等,那么到底咋回事呢?如何不显示负数呢?

例如-301047508,我们执行(-301047508).toString(2),得到-10001111100011001111011010100,但是这并不是它真正的二进制,因为负数在计算机中是以补码存在的,而toString(2)对负数,只是得到'-'+Math.abs(num).toString(2)。

我们现在计算-301047508的补码:

也就是说-301047508在计算机中存储为:11101110000011100110000100101100 ,至于为什么会表现为负数,可以参考这篇文章: 2147483648 | 0为什么等于-2147483648

现在如何将负数变成正数呢?其实js在存储的时候,最大可存储8个字节,我们可以用parseInt('11101110000011100110000100101100',2);得到它的正数。但是前提是要得到负数的补码,下面的代码可以得到一个负数的补码和16进制数字:

其他文章

0
我要评论

评论

返回
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

提交
还可以输入500个字