摘 要： 介紹循環冗余校驗title="CRC">CRC在TMS320C64x+系列DSP上的軟件實現。 給出了該實現方法的理論推導過程并提供了相應的軟件實現代碼。
    關鍵詞： CRC；DSP

 1 CRC常規實現方法
    CRC(Cyclic Redundancy Check)是一種廣泛應用于各種通信系統的錯誤校驗機制。例如，3GPP標準定義以下16位CRC校驗多項式：
    G_CRC16(X)=X¹⁶+X¹²+X⁵+1
    CRC通常由硬件實現，圖1說明由硬件移位寄存器實現的3GPP CRC16。

    圖1中，表示異或(XOR)運算, 異或運算在移位寄存器中的位置與生成多項式相對應。CRC運算前，移位寄存器清零，隨后數據位被移入寄存器，當所有位都被移入寄存器后，寄存器的值即為CRC碼。
    發送端將CRC碼附在原始數據后發送；接收端用同樣的方法為接收到的原始數據生成CRC碼，并且與接收到的CRC碼比較。如果不一致，則說明接收到的數據出錯。
    CRC校驗也可由軟件實現，它比硬件實現靈活，但不如硬件實現效率高。假設變量crc代表移位寄存器的值，CRC16 軟件實現的偽代碼為：
    while(data_len--)
    {
      crc=(crc<<1)
      if (((input bit)(bit shifted out))==1)
         crc=crc0x1021           //0x1021 represents X¹²+X⁵+1
      else if (((input bit)(bit shifted out))==0)
      crc=crc0//this can be removed since it is meaningless
    }
    以上軟件實現效率不高，主要是因為數據被逐個位處理，每次循環只能處理一位。一種常見的改進的軟件實現方法可以每次循環處理一個字節，但它需要一個查找表。在查找表中保存所有的8位（一個字節）數據的CRC運算結果，因為8位數據有256個，所以查找表的長度為256。下面是生成查找表的偽代碼：
    for(i=0；i<256；i++)
    crc_lut[i]=crc_value_for_one_byte(i)；//generate CRC for one byte
    用查找表方法實現的CRC16的代碼如下：
    Uint16 crc16_lut(Uint8*data_prt，Int32 data_len，Uint16*crc_lut)
    {
      Uint8 crc_shift_out；
      Uint16 crc=0；
      while(data_len--)
      {
         crc_shift_out=(Uint8) (crc>>8)；//higher 8 bit of previous crc are shifted out
         crc=(crc<<8)^crc_lut[crc_shift_out^(*data_prt++)]；
      }
      return(crc)；
    }
    這個處理過程可被理解為：
    (1)計算移位寄存器在8個時鐘周期中的輸入：(crc_shift_out^*data_prt++)；
    (2)查找這個輸入字節對應的CRC碼：crc_lut[crc_shift_out^*data_prt++]；
    (3)把新輸入數據的CRC碼加到原有的CRC值上：(crc<<8)^crc_lut[crc_shift_out^*data_prt++]。
    在TMS320C64x DSP上，如果用這種方法實現CRC校驗，每次循環大概需9個DSP時鐘周期。而在TMS320C64x+DSP上新增了與CRC運算相關的Galois域乘法運算指令，使得每次循環僅需約1個DSP時鐘周期。
2 C64x+DSP的Galois域乘法指令
    C64x+DSP系列是TI最新的高性能DSP系列，它有8個并行的運算單元，速度高達到1GHz。C64x+ DSP 提供了新的與CRC運算相關的Galois域乘法指令和寄存器，可在兩個乘法單元M1、M2中并行執行。
    (1)GMPY：Galois域(32bit)(9bit)，寄存器GPLYA存放用于M1運算單元的多項式，寄存器GPLYB存放用于M2運算單元的多項式；
    (2)XORMPY：多項式為0的Galois域(32bit)(9bit)；
    (3)GMPY4：同時執行4個Galois域(8bit)(8bit)，M1和M2運算單元共用存放多項式的GFPGFR寄存器。
    注：表示Galois域乘法。
    M1和M2可以并行執行，所以，C64x+每個時鐘周期可執行2個(32bit)(9bit)的GMPY或XORGMPY指令，或執行8個(8bit)(8bit)的GMPY指令。
    下面是C64x+GMPY指令的等效C代碼：
    //32bits src1 multiply 9bit src2 with 32bit polynomial
    uint GMPY(uint src1，uint src2，uint polynomial)
    {
      uint pp；
      uint mask，tpp；
      uint i；
      pp=0；
      mask=0x00000100；//multiply by computing partial products.
      for (i=0；i<8；i++){
          if (src2 & mask) pp^=src1；
          mask>>=1；
          tpp=pp<<1；
          if(pp & 0x80000000) pp=polynomial^tpp；
          else pp=tpp；
      }
      if (src2 & 0x1) pp^=src1；
      return(pp)；//leave it asserted left.
    }
    請注意，這里的GMPY指令所用的多項式是GF(2³²)原多項式的低32位。例如：
    G(X)_CRC32=X³²+X²⁶+X²³+X²²+X¹⁶+X¹²+X¹¹+X¹⁰+X⁸+X⁷+X⁵+X⁴+X²+X¹+1
    用二進制數表示為：1 0000 0100 1100 0001 0001 1101 1011 0111=0x1 04c1 1db7，則GMPY多項式寄存器的值應該是0x04c11db7，沒有必要包含最高位，因為它始終為1。GMPY所用的多項式必須是GF(2³²)域多項式，對于非GF(2³²)域的多項式，必須被左移得到32階的多項式，并左移操作數src1，使它也是32階，然后用GMPY指令運算，結果需右移同樣的位數，從而得到最終結果。
    例如：Galois域G(X)=X⁸+X⁶+X⁵+X³+1(01101001)上的二進制數(01000001)(100)可以用以下方法計算：
    GMPY((01000001)<<24，(100)，(01101001)<<24)>>24
3 CRC在C64x+DSP上的高效實現
    比較CRC的軟件實現代碼和GMPY指令的等效C語言代碼可以看出，一個字節的CRC碼可以用GMPY指令計算為GMPY(polynomial, data_byte, polynomial)。
    用GMPY實現的CRC代碼為：
      Uint32 crc_gmpy(Uint8*data_ptr，Int32 data_len_of_byte，Uint32 polynomial)
    //data_ptr is data pointer，data_len_of_byte is the data length in bytes
    {
      Int32 i；
      Uint32 crc32=0；
      GPLYA=polynomial；
      GPLYB=polynomial；
      for(i=0；i      {
              crc32=_gmpy(crc32，0x100)^_gmpy(polynomial，(*data_ptr++))；
      }
      return(crc32)；
    }
    以上代碼中的“_gmpy”代表GMPY指令，用戶按C語言函數調用的方式使用它，但DSP編譯器會把它編譯成一條GMPY指令，而不是一個函數調用。所有的C6000系列DSP指令都可以在C語音中按這種方式使用。
    以上代碼在C64x+上執行，每次循環需要大約6個時鐘周期，它比查找表方法效率高，而且不需要查找表，這對于存儲器受限的應用來說非常合適。上述代碼每個循環需要6個時鐘周期的瓶頸因素是“循環依賴”，即下一次循環運算要基于前一次運算的結果，這使得C64x+指令流水線不能充分的流水式執行。一種改進的查找表方法可以解決這一問題，從而大大提高CRC計算的效率。該方法使用的查找表可以由以下代碼生成：
    crc_lut[0]=polynomial；
    for(k=1；k         crc_lut[k]=_gmpy(crc_lut[k-1]，0x100))；//polynomialx8
    這種CRC的計算方法可用以下偽代碼表示：
    Index=length_of_byte-1；
    for(k=0；k         crc=crc^_gmpy(crc_lut[Index--]，data_byte[k]))；
    為了更充分地利用C64x+ DSP并行流水式處理的能力，并減少查找表的長度，可以進一步對以上計算進行優化，每次循環處理32bit。相應的查找表長度減少為原來的1/4。查找表的生成代碼如下：
    crc_lut[0]=polynomial；
    for(k=1；k        crc_lut[k]=_gmpy(_gmpy(_gmpy(_gmpy(crc_lut[k-1]，0x100)，0x100)，0x100)，0x100)；//polynomialx³²
    該方法的CRC計算可用以下偽代碼表示：
    Index=length_of_word-1；
    for(j=0；j    {
        LutXn=crc_lut[Index--]；
        crc0=crc0^_gmpy(LutXn，data_byte[4*j])；
        crc1=crc1^_gmpy(LutXn，data_byte[4*j+1])；
        crc2=crc2^_gmpy(LutXn，data_byte[4*j+2])；
        crc3=crc3^_gmpy(LutXn，data_byte[4*j+3])；
    }
    //crc0x24
    crc0=_gmpy(crc0，0x100)；
    crc0=_gmpy(crc0，0x100)；
    crc0=_gmpy(crc0，0x100)；
    //crc1x16
    crc1= _gmpy(crc1, 0x100);
    crc1= _gmpy(crc1, 0x100);
    //crc2x8
    crc2=_gmpy(crc2，0x100)；
    crc=crc0^crc1^crc2^crc3；
    上述基于GMPY和查找表的CRC優化實現，每次循環約需4個時鐘周期，而一次循環處理4字節，所以每個字節的處理僅需約一個時鐘周期。
    CRC是常用的檢錯機制，表1總結了幾種CRC的軟件實現方法在C64x+DSP上執行的效率。

    通過表1可以看出，在C64x+DSP上利用Galois域乘法指令極大地提高了CRC運算的效率。