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这个例子:

计算101001110100001和111010101

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

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

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

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

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

划分单元

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

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

经过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:

计算h1^h2^h3^h4

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

上面的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,但是在真实计算中,内容的长度不确定,都是一边剔除(剔除最右边单元),一边加入(从最左边加入)。

最后放CRC32的代码:

function makeTable() {//列出单元可能的情况2^8和h`的结果
    var c, table = [];
    for(var n =0; n < 256; n++){
        c = n;
        for(var k =0; k < 8; k++){
            c = ((c&1) ? (0xEDB88320 ^ (c >>> 1)) : (c >>> 1));
        }
        table[n] = c;
    }
    return table;
}
var crcTable = makeTable();
function crc32str(crc, str, len, pos) {
    var t = crcTable, end = pos + len;
    crc = crc ^ (-1);
    for (var i = pos; i < end; i++ ) {
        crc = (crc >>> 8) ^ t[(crc ^ str.charCodeAt(i)) & 0xFF];
    }
    return (crc ^ (-1)); // >>> 0;
}

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

CRC32负数问题

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

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

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

-301047508补码

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

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

function getRealCode(num, showHex) {
    if(num < 0) {
        let n = -num;
        n--;
        let str = '11111111111111111111111111111111'.concat(n.toString(2).split('').map(i => i & 1 ? 0 : 1).join('')).slice(-32);
        if(showHex) {
            return '0x'+parseInt(str, 2).toString(16);
        } else {
            return str;
        }
    } else { //
        if(showHex) {
            return '0x'+num.toString(16);
        } else {
            return num.toString(2);
        }
    }
}
/*例:getRealCode(-301047508,true)得到0xee0e612c*/
回到顶部
我要评论

所有评论

返回
邮箱:
绑定
取消
×

我要评论

回复:

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

图片:

邮箱:
绑定邮箱后,若有回复,会邮件通知。
提交
还可以输入500个字