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的代码:

    1. function makeTable() {//列出单元可能的情况2^8和h`的结果
    2.     var c, table = [];
    3.     for(var n =0; n < 256; n++){
    4.         c = n;
    5.         for(var k =0; k < 8; k++){
    6.             c = ((c&1) ? (0xEDB88320 ^ (>>> 1)) : (>>> 1));
    7.         }
    8.         table[n] = c;
    9.     }
    10.     return table;
    11. }
    12. var crcTable = makeTable();
    13. function crc32str(crc, str, len, pos) {
    14.     var t = crcTable, end = pos + len;
    15.     crc = crc ^ (-1);
    16.     for (var i = pos; i < end; i++ ) {
    17.         crc = (crc >>> 8) ^ t[(crc ^ str.charCodeAt(i)) & 0xFF];
    18.     }
    19.     return (crc ^ (-1)); // >>> 0;
    20. }

    其中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进制数字:

    1. function getRealCode(num, showHex) {
    2.     if(num < 0) {
    3.         let n = -num;
    4.         n--;
    5.         let str = '11111111111111111111111111111111'.concat(n.toString(2).split('').map(=> i & 1 ? 0 : 1).join('')).slice(-32);
    6.         if(showHex) {
    7.             return '0x'+parseInt(str, 2).toString(16);
    8.         } else {
    9.             return str;
    10.         }
    11.     } else { //
    12.         if(showHex) {
    13.             return '0x'+num.toString(16);
    14.         } else {
    15.             return num.toString(2);
    16.         }
    17.     }
    18. }
    19. /*例:getRealCode(-301047508,true)得到0xee0e612c*/
    回到顶部
    我要评论

    所有评论

      相关文章