計(jì)算法簡(jiǎn)單實(shí)現(xiàn)crc校驗(yàn)
[導(dǎo)讀]前一段時(shí)間做協(xié)議轉(zhuǎn)換器的時(shí)間用到CRC-16校驗(yàn)，查了不少資料發(fā)現(xiàn)都不理想。查表法要建表太麻煩，而計(jì)算法覺得那些例子太羅嗦。最后只好自己寫了，最后發(fā)現(xiàn)原來挺簡(jiǎn)單嘛：）
前一段時(shí)間做協(xié)議轉(zhuǎn)換器的時(shí)間用到CRC-16校驗(yàn)，查了不少資料發(fā)現(xiàn)都不理想。查表法要建表太麻煩，而計(jì)算法覺得那些例子太羅嗦。最后只好自己寫了，最后發(fā)現(xiàn)原來挺簡(jiǎn)單嘛：）
兩個(gè)子程序搞定。這里用的多項(xiàng)式為：
CRC-16 = X16 + X12 + X5 + X0 = 2^0+2^5+2^12+2^16=0x11021
因最高位一定為“1”，故略去計(jì)算只采用0x1021即可
CRC_Byte：計(jì)算單字節(jié)的CRC值
CRC_Data：計(jì)算一幀數(shù)據(jù)的CRC值
CRC_High CRC_Low：存放單字節(jié)CRC值
CRC16_High CRC16_Low：存放幀數(shù)據(jù)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次循環(huán)，每一位相應(yīng)計(jì)算
goto CRC10
goto CRCend
CRC10
bcf STATUS, C
rlf CRC_Low
rlf CRC_High
btfss STATUS, C
goto CRC ；為0不需計(jì)算
movlw 10H ;若多項(xiàng)式改變，這里作相應(yīng)變化
xorwf CRC_High, f
movlw 21H ;若多項(xiàng)式改變，這里作相應(yīng)變化
xorwf CRC_Low, f
goto CRC
CRCend:
nop
nop
return
;<>-------------------------------------------------------------
; CRC one byte end
;<>-------------------------------------------------------------
;<>-------------------------------------------------------------
; Function: CRC date
; Input: BufStart(A,B,C)（一幀數(shù)據(jù)的起始地址） v_Count （要做CRC的字節(jié)數(shù)）
; Output: CRC16_High CRC16_Low（結(jié)果）
;<>-------------------------------------------------------------
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 ;需計(jì)算的字節(jié)數(shù)
movf CRC_High, w
xorwf CRC16_Low, w
movwf CRC16_High
movf CRC_Low, w
movwf CRC16_Low
movf v_Count, w ；計(jì)算結(jié)束？
btfss STATUS, Z
goto CRC_Data10
return
;<>-------------------------------------------------------------
; CRC date end
;<>-------------------------------------------------------------
說明： CRC 的計(jì)算原理如下（一個(gè)字節(jié)的簡(jiǎn)單例子）
11011000 00000000 00000000 <- 一個(gè)字節(jié)數(shù)據(jù), 左移 16b
^10001000 00010000 1 <- CRC-CCITT 多項(xiàng)式, 17b
--------------------------
1010000 00010000 10 <- 中間余數(shù)
^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
仿此，可推出兩個(gè)字節(jié)數(shù)據(jù)計(jì)算如下：d 為數(shù)據(jù)，p 為項(xiàng)式，a 為余數(shù)
dddddddd dddddddd 00000000 00000000 <- 數(shù)據(jù) D ( D1, D0, 0, 0 )
^pppppppp pppppppp p <- 多項(xiàng)式 P
-----------------------------------
...
aaaaaaaa aaaaaaaa 0 <- 第一次的余數(shù) A’ ( A’1, A’0 )
^pppppppp pppppppp p
--------------------------
...
aaaaaaaa aaaaaaaa <- 結(jié)果 A ( A1, A0 )
由此與一字節(jié)的情況比較，將兩個(gè)字節(jié)分開計(jì)算如下：
先算高字節(jié)：
dddddddd 00000000 00000000 00000000 <- D1, 0, 0, 0
^pppppppp pppppppp p <- P
-----------------------------------
...
aaaaaaaa aaaaaaaa <- 高字節(jié)部分余數(shù) PHA1, PHA0
此處的部分余數(shù)與前面兩字節(jié)算法中的第一次余數(shù)有如下關(guān)系，即 A’1 = PHA1 ^ D0, A’0 = PHA0：
aaaaaaaa aaaaaaaa <- PHA1, PHA0
^dddddddd <- D0
-----------------
aaaaaaaa aaaaaaaa <- A’1, A’0
低字節(jié)的計(jì)算：
aaaaaaaa 00000000 00000000 <- A’1, 0, 0
^pppppppp pppppppp p <- P
--------------------------
...
aaaaaaaa aaaaaaaa <- 低字節(jié)部分余數(shù) PLA1, PLA0
^aaaaaaaa <- A’0 ， 即 PHA0
-----------------
aaaaaaaa aaaaaaaa <- 最后的 CRC ( A1, A0 )
總結(jié)以上內(nèi)容可得規(guī)律如下：
設(shè)部分余數(shù)函數(shù)
PA = f( d )
其中 d 為一個(gè)字節(jié)的數(shù)據(jù)（注意，除非 n = 0 ，否則就不是原始數(shù)據(jù)，見下文）
第 n 次的部分余數(shù)
PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( d )
其中的
d = ( PA( n - 1 ) >> 8 ) ^ D( n )
其中的 D( n ) 才是一個(gè)字節(jié)的原始數(shù)據(jù)。
公式如下：
PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( ( PA( n - 1 ) >> 8 ) ^ D( n ) )
可以注意到函數(shù) f( d ) 的參數(shù) d 為一個(gè)字節(jié)，對(duì)一個(gè)確定的多項(xiàng)式 P， f( d ) 的返回值 是與 d 一一對(duì)應(yīng)的，總數(shù)為 256 項(xiàng)，將這些數(shù)據(jù)預(yù)先算出保存在表里，f( d )就轉(zhuǎn)換為一 個(gè)查表的過程，速度也就可以大幅提高，這也就是查表法計(jì)算 CRC 的原理。
再來看 CRC 表是如何計(jì)算出來的，即函數(shù) f( d ) 的實(shí)現(xiàn)方法。分析前面一個(gè)字節(jié)數(shù)據(jù)的 計(jì)算過程可發(fā)現(xiàn)，d 對(duì)結(jié)果的影響只表現(xiàn)為對(duì) P 的移位異或，看計(jì)算過程中的三個(gè) 8 位 的列中只低兩個(gè)字節(jié)的最后結(jié)果是余數(shù)，而數(shù)據(jù)所在的高 8 位列最后都被消去了，因其 中的運(yùn)算均為異或，不產(chǎn)生進(jìn)位或借位，故每一位數(shù)據(jù)只影響本列的結(jié)果，即 d 并不直接 影響結(jié)果。再將前例變化一下重列如下：
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
現(xiàn)在的問題就是如何根據(jù) d 來對(duì) P 移位異或了，從上面的例子看，也可以理解為每步 移位，但根據(jù) d 決定中間余數(shù)是否與 P 異或。從前面原來的例子可以看出，決定的條件是中間余數(shù)的最高位為0，因?yàn)?nbsp;P 的最高位一定為1，即當(dāng)中間余數(shù)與 d 相應(yīng)位異或的最高位為1時(shí)，中間余數(shù)移位就要和 P 異或，否則只需移位即可。其方法如下例（上例的變形，注意其中空格的移動(dòng)表現(xiàn)了 d 的影響如何被排除在結(jié)果之外）：
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
結(jié)合這些，前面的程序就好理解了。
兩個(gè)子程序搞定。這里用的多項(xiàng)式為：
CRC-16 = X16 + X12 + X5 + X0 = 2^0+2^5+2^12+2^16=0x11021
因最高位一定為“1”，故略去計(jì)算只采用0x1021即可
CRC_Byte：計(jì)算單字節(jié)的CRC值
CRC_Data：計(jì)算一幀數(shù)據(jù)的CRC值
CRC_High CRC_Low：存放單字節(jié)CRC值
CRC16_High CRC16_Low：存放幀數(shù)據(jù)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次循環(huán)，每一位相應(yīng)計(jì)算
goto CRC10
goto CRCend
CRC10
bcf STATUS, C
rlf CRC_Low
rlf CRC_High
btfss STATUS, C
goto CRC ；為0不需計(jì)算
movlw 10H ;若多項(xiàng)式改變，這里作相應(yīng)變化
xorwf CRC_High, f
movlw 21H ;若多項(xiàng)式改變，這里作相應(yīng)變化
xorwf CRC_Low, f
goto CRC
CRCend:
nop
nop
return
;<>-------------------------------------------------------------
; CRC one byte end
;<>-------------------------------------------------------------
;<>-------------------------------------------------------------
; Function: CRC date
; Input: BufStart(A,B,C)（一幀數(shù)據(jù)的起始地址） v_Count （要做CRC的字節(jié)數(shù)）
; Output: CRC16_High CRC16_Low（結(jié)果）
;<>-------------------------------------------------------------
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 ;需計(jì)算的字節(jié)數(shù)
movf CRC_High, w
xorwf CRC16_Low, w
movwf CRC16_High
movf CRC_Low, w
movwf CRC16_Low
movf v_Count, w ；計(jì)算結(jié)束？
btfss STATUS, Z
goto CRC_Data10
return
;<>-------------------------------------------------------------
; CRC date end
;<>-------------------------------------------------------------
說明： CRC 的計(jì)算原理如下（一個(gè)字節(jié)的簡(jiǎn)單例子）
11011000 00000000 00000000 <- 一個(gè)字節(jié)數(shù)據(jù), 左移 16b
^10001000 00010000 1 <- CRC-CCITT 多項(xiàng)式, 17b
--------------------------
1010000 00010000 10 <- 中間余數(shù)
^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
仿此，可推出兩個(gè)字節(jié)數(shù)據(jù)計(jì)算如下：d 為數(shù)據(jù)，p 為項(xiàng)式，a 為余數(shù)
dddddddd dddddddd 00000000 00000000 <- 數(shù)據(jù) D ( D1, D0, 0, 0 )
^pppppppp pppppppp p <- 多項(xiàng)式 P
-----------------------------------
...
aaaaaaaa aaaaaaaa 0 <- 第一次的余數(shù) A’ ( A’1, A’0 )
^pppppppp pppppppp p
--------------------------
...
aaaaaaaa aaaaaaaa <- 結(jié)果 A ( A1, A0 )
由此與一字節(jié)的情況比較，將兩個(gè)字節(jié)分開計(jì)算如下：
先算高字節(jié)：
dddddddd 00000000 00000000 00000000 <- D1, 0, 0, 0
^pppppppp pppppppp p <- P
-----------------------------------
...
aaaaaaaa aaaaaaaa <- 高字節(jié)部分余數(shù) PHA1, PHA0
此處的部分余數(shù)與前面兩字節(jié)算法中的第一次余數(shù)有如下關(guān)系，即 A’1 = PHA1 ^ D0, A’0 = PHA0：
aaaaaaaa aaaaaaaa <- PHA1, PHA0
^dddddddd <- D0
-----------------
aaaaaaaa aaaaaaaa <- A’1, A’0
低字節(jié)的計(jì)算：
aaaaaaaa 00000000 00000000 <- A’1, 0, 0
^pppppppp pppppppp p <- P
--------------------------
...
aaaaaaaa aaaaaaaa <- 低字節(jié)部分余數(shù) PLA1, PLA0
^aaaaaaaa <- A’0 ， 即 PHA0
-----------------
aaaaaaaa aaaaaaaa <- 最后的 CRC ( A1, A0 )
總結(jié)以上內(nèi)容可得規(guī)律如下：
設(shè)部分余數(shù)函數(shù)
PA = f( d )
其中 d 為一個(gè)字節(jié)的數(shù)據(jù)（注意，除非 n = 0 ，否則就不是原始數(shù)據(jù)，見下文）
第 n 次的部分余數(shù)
PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( d )
其中的
d = ( PA( n - 1 ) >> 8 ) ^ D( n )
其中的 D( n ) 才是一個(gè)字節(jié)的原始數(shù)據(jù)。
公式如下：
PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( ( PA( n - 1 ) >> 8 ) ^ D( n ) )
可以注意到函數(shù) f( d ) 的參數(shù) d 為一個(gè)字節(jié)，對(duì)一個(gè)確定的多項(xiàng)式 P， f( d ) 的返回值 是與 d 一一對(duì)應(yīng)的，總數(shù)為 256 項(xiàng)，將這些數(shù)據(jù)預(yù)先算出保存在表里，f( d )就轉(zhuǎn)換為一 個(gè)查表的過程，速度也就可以大幅提高，這也就是查表法計(jì)算 CRC 的原理。
再來看 CRC 表是如何計(jì)算出來的，即函數(shù) f( d ) 的實(shí)現(xiàn)方法。分析前面一個(gè)字節(jié)數(shù)據(jù)的 計(jì)算過程可發(fā)現(xiàn)，d 對(duì)結(jié)果的影響只表現(xiàn)為對(duì) P 的移位異或，看計(jì)算過程中的三個(gè) 8 位 的列中只低兩個(gè)字節(jié)的最后結(jié)果是余數(shù)，而數(shù)據(jù)所在的高 8 位列最后都被消去了，因其 中的運(yùn)算均為異或，不產(chǎn)生進(jìn)位或借位，故每一位數(shù)據(jù)只影響本列的結(jié)果，即 d 并不直接 影響結(jié)果。再將前例變化一下重列如下：
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
現(xiàn)在的問題就是如何根據(jù) d 來對(duì) P 移位異或了，從上面的例子看，也可以理解為每步 移位，但根據(jù) d 決定中間余數(shù)是否與 P 異或。從前面原來的例子可以看出，決定的條件是中間余數(shù)的最高位為0，因?yàn)?nbsp;P 的最高位一定為1，即當(dāng)中間余數(shù)與 d 相應(yīng)位異或的最高位為1時(shí)，中間余數(shù)移位就要和 P 異或，否則只需移位即可。其方法如下例（上例的變形，注意其中空格的移動(dòng)表現(xiàn)了 d 的影響如何被排除在結(jié)果之外）：
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
結(jié)合這些，前面的程序就好理解了。
下載文檔
