芯片破解网


首页 -- 单片机破解-- IC破解-- 芯片破解-- 新闻技术 --关于我们
 
芯片破解网 >> 新闻技术 >> 当前位置

计算法简单实现crc校验

前一段时间做协议转换器的时间用到CRC-16校验,查了不少资料发现都不理想。查表法要建表太麻烦,而计算法觉得那些例子太罗嗦。最后只好自己写了,最后发现原来挺简单嘛:)

两个子程序搞定。这里用的多项式为:
CRC-16    = X16 + X12 + X5 + X0 = 2^0+2^5+2^12+2^16=0x11021

因最高位一定为“1”,故略去计算只采用0x1021即可

CRC_Byte:计算单字节的CRC值
CRC_Data:计算一帧数据的CRC值
CRC_High  CRC_Low:存放单字节CRC值
CRC16_High  CRC16_Low:存放帧数据CRC值

;<>-------------------------------------------------------------
;      Function:       CRC one byte
;      Input:             CRCByte
;      Output:           CRC_High CRC_Low
;<>-------------------------------------------------------------

CRC_Byte:
       clrf         CRC_Low
       clrf         CRC_High
       movlw           09H
       movwf           v_Loop1
       movf              CRCByte, w
       movwf           CRC_High
CRC:
       decfsz            v_Loop1                              ;8次循环,每一位相应计算
       goto        CRC10
       goto        CRCend
CRC10
       bcf                STATUS, C
       rlf                  CRC_Low
       rlf                  CRC_High
       
       btfss              STATUS, C
       goto        CRC                                          ;为0不需计算
       movlw           10H                                    ;若多项式改变,这里作相应变化
       xorwf            CRC_High, f
       movlw           21H                                    ;若多项式改变,这里作相应变化
       xorwf            CRC_Low, f
       goto        CRC
CRCend:
       nop
       nop
       return
;<>-------------------------------------------------------------
;      CRC one byte end
;<>-------------------------------------------------------------
;<>-------------------------------------------------------------
;      Function:       CRC date
;      Input:             BufStart(A,B,C)(一帧数据的起始地址) v_Count (要做CRC的字节数)
;      Output:           CRC16_High CRC16_Low(结果)
;<>-------------------------------------------------------------
CRC_Data:

       clrf         CRC16_High
       clrf         CRC16_Low

CRC_Data10

       movf              INDF, w
       xorwf            CRC16_High,w

       movwf           CRCByte
       call         CRC_Byte
       incf         FSR
       decf        v_Count                       ;需计算的字节数
       
       movf              CRC_High, w
       xorwf            CRC16_Low, w
       movwf           CRC16_High

       movf              CRC_Low, w
       movwf           CRC16_Low

       movf              v_Count, w                                          ;计算结束?
       btfss              STATUS, Z
       goto        CRC_Data10

       return

;<>-------------------------------------------------------------
;             CRC date end
;<>-------------------------------------------------------------

 

说明: CRC 的计算原理如下(一个字节的简单例子)
    11011000 00000000 00000000  <- 一个字节数据, 左移 16b
   ^10001000 00010000 1         <- CRC-CCITT 多项式, 17b
    --------------------------
     1010000 00010000 10        <- 中间余数
    ^1000100 00001000 01
     -------------------------
       10100 00011000 1100
      ^10001 00000010 0001
       -----------------------
         101 00011010 110100
        ^100 01000000 100001
         ---------------------
           1 01011010 01010100
          ^1 00010000 00100001
           -------------------
             01001010 01110101  <- 16b CRC

仿此,可推出两个字节数据计算如下:d 为数据,p 为项式,a 为余数
    dddddddd dddddddd 00000000 00000000 <- 数据 D ( D1, D0, 0, 0 )
   ^pppppppp pppppppp p                 <- 多项式 P
    -----------------------------------
    ...
             aaaaaaaa aaaaaaaa 0        <- 第一次的余数 A’ ( A’1, A’0 )
            ^pppppppp pppppppp p
             --------------------------
             ...
                      aaaaaaaa aaaaaaaa <- 结果 A ( A1, A0 )

由此与一字节的情况比较,将两个字节分开计算如下:
先算高字节:
    dddddddd 00000000 00000000 00000000 <- D1, 0, 0, 0
   ^pppppppp pppppppp p                 <- P
    -----------------------------------
    ...
             aaaaaaaa aaaaaaaa          <- 高字节部分余数 PHA1, PHA0

此处的部分余数与前面两字节算法中的第一次余数有如下关系,即 A’1 = PHA1 ^ D0, A’0 = PHA0:
             aaaaaaaa aaaaaaaa          <- PHA1, PHA0
            ^dddddddd                   <- D0
             -----------------
             aaaaaaaa aaaaaaaa          <- A’1, A’0

低字节的计算:
             aaaaaaaa 00000000 00000000 <- A’1, 0, 0
            ^pppppppp pppppppp p        <- P
             --------------------------
             ...
                      aaaaaaaa aaaaaaaa <- 低字节部分余数 PLA1, PLA0
                     ^aaaaaaaa          <- A’0 , 即 PHA0
                      -----------------
                      aaaaaaaa aaaaaaaa <- 最后的 CRC ( A1, A0 )

总结以上内容可得规律如下:
设部分余数函数
    PA = f( d )
其中 d 为一个字节的数据(注意,除非 n = 0 ,否则就不是原始数据,见下文)
第 n 次的部分余数
    PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( d )
其中的
    d = ( PA( n - 1 ) >> 8 ) ^ D( n )
其中的 D( n ) 才是一个字节的原始数据。

公式如下:
    PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( ( PA( n - 1 ) >> 8 ) ^ D( n ) )

可以注意到函数 f( d ) 的参数 d 为一个字节,对一个确定的多项式 P, f( d ) 的返回值 是与 d 一一对应的,总数为 256 项,将这些数据预先算出保存在表里,f( d )就转换为一 个查表的过程,速度也就可以大幅提高,这也就是查表法计算 CRC 的原理。

再来看 CRC 表是如何计算出来的,即函数 f( d ) 的实现方法。分析前面一个字节数据的 计算过程可发现,d 对结果的影响只表现为对 P 的移位异或,看计算过程中的三个 8 位 的列中只低两个字节的最后结果是余数,而数据所在的高 8 位列最后都被消去了,因其 中的运算均为异或,不产生进位或借位,故每一位数据只影响本列的结果,即 d 并不直接 影响结果。再将前例变化一下重列如下:
    11011000
    --------------------------
    10001000 00010000 1        // P
   ^ 1000100 00001000 01       // P
   ^  000000 00000000 000      // 0
   ^   10001 00000010 0001     // P
   ^    0000 00000000 00000    // 0
   ^     100 01000000 100001   // P
   ^      00 00000000 0000000  // 0
   ^       1 00010000 00100001 // P
           -------------------
             01001010 01110101

现在的问题就是如何根据 d 来对 P 移位异或了,从上面的例子看,也可以理解为每步 移位,但根据 d 决定中间余数是否与 P 异或。从前面原来的例子可以看出,决定的条件是中间余数的最高位为0,因为 P 的最高位一定为1,即当中间余数与 d 相应位异或的最高位为1时,中间余数移位就要和 P 异或,否则只需移位即可。其方法如下例(上例的变形,注意其中空格的移动表现了 d 的影响如何被排除在结果之外):

    d --------a--------
    1 00000000 00000000 <- HSB = 1
      0000000 000000000 <- a <<= 1
      0001000 000100001 <-不含最高位的 1
      -----------------
    1 0001000 000100001
      001000 0001000010
      000100 0000100001
      -----------------
    0 001100 0001100011 <- HSB = 0
      01100 00011000110
      -----------------
    1 01100 00011000110 <- HSB = 1
      1100 000110001100
      0001 000000100001
      -----------------
    1 1101 000110101101 <- HSB = 0
      101 0001101011010
      -----------------
    0 101 0001101011010 <- HSB = 1
      01 00011010110100
      00 01000000100001
      -----------------
    0 01 01011010010101 <- HSB = 0
      1 010110100101010
      -----------------
    0 1 010110100101010 <- HSB = 1
       0101101001010100
       0001000000100001
      -----------------
       0100101001110101 <- CRC

结合这些,前面的程序就好理解了。 

返回顶部


2013-2015 芯片破解网 All Rights Reserved.
如有任何问题和建议请联系:498187676@qq.com

深圳市协同电子有限公司 版权所有

地址:深圳市福田区华强北路华强电子世界华强广场B座19i号 电话:0755-88820678
手机:13713820066 QQ:498187676 联系:周工


站点地图

粤ICP备12084176号-9