美文网首页
杂技 CRC深究

杂技 CRC深究

作者: 元指南役 | 来源:发表于2016-02-24 11:51 被阅读0次

    数学算法的描述可以坑很多程序员,我也不例外

    CRC

    CRC32

    1.CRC32算法难在网上的源码大多是驱动表计算,无法从源码中推倒实现过程
    2.CRC32 正式算法还涉及到数据颠倒和初始化预置值

    CRC32参数模型
    Name : "CRC-32"
    Width : 32
    Poly : 04C11DB7
    Init : FFFFFFFF
    RefIn : True
    RefOut : True
    XorOut : FFFFFFFF
    Check : CBF43926
    

    标准的CRC

    CRC的核心算法是 模2除法 [除法过程为XOR]

    例:

    101101 mod2 1100
    
    101101 000
    1100
     11101 000
     1100
       101 000
       110 0
        11 000
        11 00
           000   ->余数 / CRC校检值
    

    例子中的 1100 称为生成项
    1.在测试数据后面+[生成项长度-1]位0
    2.进行mod2除法
    3.余数追加到测试数据后面,形成101101 100作为我们的SIGNED数据

    CRC32的生成项长度为33
    上面演示的过程是 直接计算法

    驱动表法

    我们延用上面的例子

    首先驱动表法基于交换律

    (A XOR B) XOR C = A XOR (B XOR C)
    

    我们的位宽是3 //生成项长度-1 也称为CRC3

    原:

    101101 000
    1100
     11101 000
     1100
       101 000
       110 0
        11 000
        11 00
           000   ->余数 / CRC校检值
    

    我们一共XOR了4次来得到余数
    表:

    1100
     1100
       1100
        1100
    10110100
    
    计算表值->10110100
    
    101101000
    10110100
          000
    

    例子中实际上我们的表索引是 [101101]值是[000000]
    例子不是很明显,但是我们实际上是用的是消去法
    我们使poly XOR (ploy>>n) 直到前约定位与原数据相同[例子中是6]
    后三位只需要与ploy XOR的结果 左移6位 再XOR 再查表就可以了

    我们的poly表就可以有 111111-000000种变化

    在CRC32中,我们的位宽是32位
    CRC16 和 CRC32 都是一次处理一个字节的,我们按字节建8位表[总长度255]
    8 位表的总长度是 11111111B =255D

    我们用标准生成项0x104C11DB7
    例子

    [0000 0000]->[0x0]
    [0000 0001]->[0x04C11DB7]
    [0000 0010]->[0x09823B6E]
    [0000 0011]->[0x0D4326D9]
    [0000 0100]->[0x130476DC]
    ...
    

    这张表叫做,直接查询表

    例:

    1111 1111 1111 1000 0000 0000 0000 0000 0000 0000 0000 0
    1000 0010 0110 0000 1000 1110 1101 1011 1
     111 1101 1001 1000 1000 1110 1101 1011 10
     100 0001 0011 0000 0100 0111 0110 1101 11
      11 1100 1010 1000 1100 1001 1011 0110 010
      10 0000 1001 1000 0010 0011 1011 0110 111
       1 1100 0011 0000 1110 1010 0000 0000 1010
       1 0000 0100 1100 0001 0001 1101 1011 0111
         1100 0111 1100 1111 1011 1101 1011 1101 0000 0000 0
         1000 0010 0110 0000 1000 1110 1101 1011 1
          100 0101 1010 1111 0011 0011 0110 0110 1000 0000 0
          100 0001 0011 0000 0100 0111 0110 1101 11
               100 1001 1111 0111 0100 0000 1011 0100 0000 0
               100 0001 0011 0000 0100 0111 0110 1101 11
                   1000 1100 0111 0000 0111 1101 1001 1100 0
                   1000 0010 0110 0000 1000 1110 1101 1011 1
                    000 1110 0001 0000 1111 0011 0100 0111 1
    
    1111 1111 1111 1
              1011 0001 1111 0111 0100 0000 1011 0100   //表ff
               100 1001 1111 0111 0100 0000 1011 0100   
                    001 0001 0110 0100 1111 1000 0000 0111 1   //表09
                    000 1110 0001 0000 1111 0011 0100 0111 1
    
    

    驱动表法的实现

    定义1个32位的register,并将原始数据头放入。
    1:register 左移一个字节[剩余长度],从原始数据中读入一个新的字节[剩余长度]
    2:利用刚从 register 移出的内容作为下标定位 table 中的一个 32 位的值
    3:把这个值 XOR 到 register 中
    4:如果还有未处理的数据则回到第一步继续执行

    直驱表法

    我们算法的本质是
    原数据 XOR POLY XOR [POLY>>N]……
    驱动表法的本质是
    原数据 XOR TABLE[G(POLY)] XOR [TABLE[G(POLY)]>>8N]……

    直驱表法例:

    1111 1111 1111 1
    原数据取出1字节 -> 1111 1111
    XOR
    寄存器取出1字节 -> 0000 0000
    查表[1111 1111]
    得 0xB1F740B4 XOR进 寄存器
    
    目前寄存器 1011 0001 1111 0111 0100 0000 1011 0100
    
    
    原数据取出剩余字节 -> 1111 1
    XOR
    寄存器取出5位 1011 0
    目前寄存器 0011 1110 1110 1000 0001 0110 1000 0000
    查表[01001]
    得0x22C9F00F XOR进 寄存器
    目前寄存器 
              0010 0010 1100 1001 1111 0000 0000 1111
              XOR
              0011 1110 1110 1000 0001 0110 1000 0000
              =
              0001 1100 0010 0001 1110 0110 1000 1111
    

    直驱表法,使原数据成了因子。只用n次的poly 自xor来计算结果。

    引入模型

    我们之前的计算的确属于CRC。但是与winrar之类的软件求的值并不一样。原因是因为我们没有引入模型。

    CRC32参数模型
    Name : "CRC-32"
    Width : 32
    Poly : 04C11DB7
    Init : FFFFFFFF
    RefIn : True
    RefOut : True
    XorOut : FFFFFFFF
    Check : CBF43926
    

    Init 用于初始化直驱表的寄存器值,我们之前初始化是0
    RefIn 需要将待测数据的每个字节颠倒
    RefOut 计算结束后 需要将整个寄存器颠倒
    XorOut 输出前要用这个值XOR一次寄存器

    0011 0001  -> 字符"1"
    直驱表法
    1.寄存器 FFFFFFFF
    2.~0011 0001  -> 1000 1100
    3.1000 1100 XOR 1111 1111
    4.0111 0011
    5.查表[0111 0011] -> 0xEDF73B3E
    6.寄存器 0xFFFFFF00 XOR 0xEDF73B3E
    7.寄存器 0x1208C43E
    8.颠倒寄存器 0111 1100 0010 0011 0001 0000 0100 1000 0x7C231048
    9.寄存器 XOR 0xFFFFFFFF -> 0x83DCEFB7
    10.TRUE
    

    最后的优化

    颠倒 直接查询表 成为 正规查询表
    我们肯定不希望,每次颠倒字节的值,毕竟很损耗性能而且实现要多几行函数。[关键是容易忘啊]
    所以如果我们把表颠倒好。让我们还按照直驱表法计算。那就方便多了。

    有两个颠倒要处理
    RefIn和RefOut

    乍一想还很麻烦

    我们把整个算法几何镜像
    RefIn和RefOut就全镜像了
    同时表的poly 0x04C11DB7 | 0xEDB88320
    表的key[0000 0001] | [1000 0000]
    T2[0000 0001] = ~T1[1000 0000] = ~0x690CE0EE = 0x77073096

    //直接查询表的生成法
    void
    CRC32_INIT(){
        int i, j;
        for (i = 0 ; i < 256 ; i++){
            for (j = 0, CRC_TABLE[i] = i<<24 ; j < 8 ; j++){
                //i就是计算因子
                //mem = i<<24 对齐内存
                //mem = (mem<<1)^((mem&0x80000000)?POLYNOMIAL:0)
                //poly = 04C11DB7
                CRC_TABLE[i] = (CRC_TABLE[i]<<1)^((CRC_TABLE[i]&0x80000000)?POLYNOMIAL:0);
            }
        }
    }
    //所以正规查询表的算法
    void
    CRC32_INIT(){
        int i, j;
        for (i = 0 ; i < 256 ; i++){
            for (j = 0, CRC_TABLE[i] = i<<24 ; j < 8 ; j++){
                //i就是计算因子
                //mem = i
                //mem = (mem>>1)^((mem&0x1)?~POLYNOMIAL:0)
                //poly = ~poly = ~0x04C11DB7 = 0xEDB88320
                CRC_TABLE[i] = (CRC_TABLE[i]>>1)^((CRC_TABLE[i]&0x1)?POLYNOMIAL:0);
            }
        }
    }
    

    我们需要的CRC算法[这里我只考虑了字节对齐的情况]

    void
    CRC32_INIT(){
        int i, j;
        for (i = 0 ; i < 256 ; i++){
            for (j = 0, CRC_TABLE[i] = i ; j < 8 ; j++){
                CRC_TABLE[i] = (CRC_TABLE[i]>>1)^((CRC_TABLE[i]&1)?POLYNOMIAL:0);
            }
        }
    }
    
    unsigned int
    CRC32(char *buff, int len){
        //Init模型的处理
        unsigned int reg=0xFFFFFFFF;
        for (int i = 0; i < len; i++){
            reg = (reg >> 8) ^ CRC_TABLE[(reg ^ buff[i]) & 0xff];
        }
        //XorOut的处理
        return ~reg;
    }
    

    相关文章

      网友评论

          本文标题:杂技 CRC深究

          本文链接:https://www.haomeiwen.com/subject/hdhikttx.html