前一段時間做協(xié)議轉換器的時間用到CRC-16校驗，查了不少資料發(fā)現(xiàn)都不理想。查表法要建表太麻煩，而計算法覺得那些例子太羅嗦。最后只好自己寫了，最后發(fā)現(xiàn)原來挺簡單嘛：）

　　兩個子程序搞定。這里用的多項式為：

　　CRC-16    = X16 + X12 + X5 + X0 = 2^0+2^5+2^12+2^16=0x11021

　　因最高位一定為“1”，故略去計算只采用0x1021即可

CRC_Byte：計算單字節(jié)的CRC值
CRC_Data：計算一幀數(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)，每一位相應計算
       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)（一幀數(shù)據(jù)的起始地址） v_Count （要做CRC的字節(jié)數(shù)）
;      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                       ;需計算的字節(jié)數(shù)
       
       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 的計算原理如下（一個字節(jié)的簡單例子）
    11011000 00000000 00000000  <- 一個字節(jié)數(shù)據(jù), 左移 16b
   ^10001000 00010000 1         <- CRC-CCITT 多項式, 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

仿此，可推出兩個字節(jié)數(shù)據(jù)計算如下：d 為數(shù)據(jù)，p 為項式，a 為余數(shù)
    dddddddd dddddddd 00000000 00000000 <- 數(shù)據(jù) D ( D1, D0, 0, 0 )
   ^pppppppp pppppppp p                 <- 多項式 P
    -----------------------------------
    ...
             aaaaaaaa aaaaaaaa 0        <- 第一次的余數(shù) A’ ( A’1, A’0 )
            ^pppppppp pppppppp p
             --------------------------
             ...
                      aaaaaaaa aaaaaaaa <- 結果 A ( A1, A0 )

由此與一字節(jié)的情況比較，將兩個字節(jié)分開計算如下：
先算高字節(jié)：
    dddddddd 00000000 00000000 00000000 <- D1, 0, 0, 0
   ^pppppppp pppppppp p                 <- P
    -----------------------------------
    ...
             aaaaaaaa aaaaaaaa          <- 高字節(jié)部分余數(shù) PHA1, PHA0

此處的部分余數(shù)與前面兩字節(jié)算法中的第一次余數(shù)有如下關系，即 A’1 = PHA1 ^ D0, A’0 = PHA0：
             aaaaaaaa aaaaaaaa          <- PHA1, PHA0
            ^dddddddd                   <- D0
             -----------------
             aaaaaaaa aaaaaaaa          <- A’1, A’0 {{分頁}}

低字節(jié)的計算：
             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 )

總結以上內容可得規(guī)律如下：
設部分余數(shù)函數(shù)
    PA = f( d )
其中 d 為一個字節(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 ) 才是一個字節(jié)的原始數(shù)據(jù)。

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

　　可以注意到函數(shù) f( d ) 的參數(shù) d 為一個字節(jié)，對一個確定的多項式 P， f( d ) 的返回值 是與 d 一一對應的，總數(shù)為 256 項，將這些數(shù)據(jù)預先算出保存在表里，f( d )就轉換為一 個查表的過程，速度也就可以大幅提高，這也就是查表法計算 CRC 的原理。

　　再來看 CRC 表是如何計算出來的，即函數(shù) f( d ) 的實現(xiàn)方法。分析前面一個字節(jié)數(shù)據(jù)的 計算過程可發(fā)現(xiàn)，d 對結果的影響只表現(xiàn)為對 P 的移位異或，看計算過程中的三個 8 位 的列中只低兩個字節(jié)的最后結果是余數(shù)，而數(shù)據(jù)所在的高 8 位列最后都被消去了，因其 中的運算均為異或，不產(chǎn)生進位或借位，故每一位數(shù)據(jù)只影響本列的結果，即 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

　　現(xiàn)在的問題就是如何根據(jù) d 來對 P 移位異或了，從上面的例子看，也可以理解為每步 移位，但根據(jù) d 決定中間余數(shù)是否與 P 異或。從前面原來的例子可以看出，決定的條件是中間余數(shù)的最高位為0，因為 P 的最高位一定為1，即當中間余數(shù)與 d 相應位異或的最高位為1時，中間余數(shù)移位就要和 P 異或，否則只需移位即可。其方法如下例（上例的變形，注意其中空格的移動表現(xiàn)了 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

　　結合這些，前面的程序就好理解了。