计算法简单实现crc校验
时间：2004-12-21 02:08:00
手机看文章
扫描二维码
随时随地手机看文章
[导读]前一段时间做协议转换器的时间用到CRC-16校验，查了不少资料发现都不理想。查表法要建表太麻烦，而计算法觉得那些例子太罗嗦。最后只好自己写了，最后发现原来挺简单嘛：）
前一段时间做协议转换器的时间用到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
结合这些，前面的程序就好理解了。
两个子程序搞定。这里用的多项式为：
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
结合这些，前面的程序就好理解了。
下载文档
