计算法简单实现crc校验
发布时间:2010-11-1 21:43
发布者:eetech
前一段时间做协议转换器的时间用到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 > 8 ) ^ D( n ) 其中的 D( n ) 才是一个字节的原始数据。 公式如下: PA( n ) = ( 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 结合这些,前面的程序就好理解了。 |
网友评论