摘 要： 介紹循環(huán)冗余校驗(yàn)title="CRC">CRC在TMS320C64x+系列DSP上的軟件實(shí)現(xiàn),。 給出了該實(shí)現(xiàn)方法的理論推導(dǎo)過(guò)程并提供了相應(yīng)的軟件實(shí)現(xiàn)代碼,。
    關(guān)鍵詞： CRC；DSP

 1 CRC常規(guī)實(shí)現(xiàn)方法
    CRC(Cyclic Redundancy Check)是一種廣泛應(yīng)用于各種通信系統(tǒng)的錯(cuò)誤校驗(yàn)機(jī)制,。例如,，3GPP標(biāo)準(zhǔn)定義以下16位CRC校驗(yàn)多項(xiàng)式：
    G_CRC16(X)=X¹⁶+X¹²+X⁵+1
    CRC通常由硬件實(shí)現(xiàn)，圖1說(shuō)明由硬件移位寄存器實(shí)現(xiàn)的3GPP CRC16,。

    圖1中,，表示異或(XOR)運(yùn)算, 異或運(yùn)算在移位寄存器中的位置與生成多項(xiàng)式相對(duì)應(yīng)。CRC運(yùn)算前,，移位寄存器清零,，隨后數(shù)據(jù)位被移入寄存器，當(dāng)所有位都被移入寄存器后,，寄存器的值即為CRC碼,。
    發(fā)送端將CRC碼附在原始數(shù)據(jù)后發(fā)送；接收端用同樣的方法為接收到的原始數(shù)據(jù)生成CRC碼,，并且與接收到的CRC碼比較,。如果不一致，則說(shuō)明接收到的數(shù)據(jù)出錯(cuò),。
    CRC校驗(yàn)也可由軟件實(shí)現(xiàn),，它比硬件實(shí)現(xiàn)靈活，但不如硬件實(shí)現(xiàn)效率高,。假設(shè)變量crc代表移位寄存器的值,，CRC16 軟件實(shí)現(xiàn)的偽代碼為：
    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
    }
    以上軟件實(shí)現(xiàn)效率不高，主要是因?yàn)閿?shù)據(jù)被逐個(gè)位處理,，每次循環(huán)只能處理一位,。一種常見(jiàn)的改進(jìn)的軟件實(shí)現(xiàn)方法可以每次循環(huán)處理一個(gè)字節(jié)，但它需要一個(gè)查找表,。在查找表中保存所有的8位（一個(gè)字節(jié)）數(shù)據(jù)的CRC運(yùn)算結(jié)果,，因?yàn)?位數(shù)據(jù)有256個(gè)，所以查找表的長(zhǎng)度為256,。下面是生成查找表的偽代碼：
    for(i=0,；i<256；i++)
    crc_lut[i]=crc_value_for_one_byte(i)；//generate CRC for one byte
    用查找表方法實(shí)現(xiàn)的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),；
    }
    這個(gè)處理過(guò)程可被理解為：
    (1)計(jì)算移位寄存器在8個(gè)時(shí)鐘周期中的輸入：(crc_shift_out^*data_prt++)；
    (2)查找這個(gè)輸入字節(jié)對(duì)應(yīng)的CRC碼：crc_lut[crc_shift_out^*data_prt++],；
    (3)把新輸入數(shù)據(jù)的CRC碼加到原有的CRC值上：(crc<<8)^crc_lut[crc_shift_out^*data_prt++],。
    在TMS320C64x DSP上，如果用這種方法實(shí)現(xiàn)CRC校驗(yàn),，每次循環(huán)大概需9個(gè)DSP時(shí)鐘周期,。而在TMS320C64x+DSP上新增了與CRC運(yùn)算相關(guān)的Galois域乘法運(yùn)算指令，使得每次循環(huán)僅需約1個(gè)DSP時(shí)鐘周期,。
2 C64x+DSP的Galois域乘法指令
    C64x+DSP系列是TI最新的高性能DSP系列,，它有8個(gè)并行的運(yùn)算單元，速度高達(dá)到1GHz,。C64x+ DSP 提供了新的與CRC運(yùn)算相關(guān)的Galois域乘法指令和寄存器,，可在兩個(gè)乘法單元M1、M2中并行執(zhí)行,。
    (1)GMPY：Galois域(32bit)(9bit),，寄存器GPLYA存放用于M1運(yùn)算單元的多項(xiàng)式，寄存器GPLYB存放用于M2運(yùn)算單元的多項(xiàng)式,；
    (2)XORMPY：多項(xiàng)式為0的Galois域(32bit)(9bit),；
    (3)GMPY4：同時(shí)執(zhí)行4個(gè)Galois域(8bit)(8bit)，M1和M2運(yùn)算單元共用存放多項(xiàng)式的GFPGFR寄存器,。
    注：表示Galois域乘法,。
    M1和M2可以并行執(zhí)行，所以,，C64x+每個(gè)時(shí)鐘周期可執(zhí)行2個(gè)(32bit)(9bit)的GMPY或XORGMPY指令,，或執(zhí)行8個(gè)(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.
    }
    請(qǐng)注意,，這里的GMPY指令所用的多項(xiàng)式是GF(2³²)原多項(xiàng)式的低32位。例如：
    G(X)_CRC32=X³²+X²⁶+X²³+X²²+X¹⁶+X¹²+X¹¹+X¹⁰+X⁸+X⁷+X⁵+X⁴+X²+X¹+1
    用二進(jìn)制數(shù)表示為：1 0000 0100 1100 0001 0001 1101 1011 0111=0x1 04c1 1db7,，則GMPY多項(xiàng)式寄存器的值應(yīng)該是0x04c11db7,，沒(méi)有必要包含最高位，因?yàn)樗冀K為1,。GMPY所用的多項(xiàng)式必須是GF(2³²)域多項(xiàng)式,，對(duì)于非GF(2³²)域的多項(xiàng)式，必須被左移得到32階的多項(xiàng)式,，并左移操作數(shù)src1,，使它也是32階，然后用GMPY指令運(yùn)算,，結(jié)果需右移同樣的位數(shù),，從而得到最終結(jié)果。
    例如：Galois域G(X)=X⁸+X⁶+X⁵+X³+1(01101001)上的二進(jìn)制數(shù)(01000001)(100)可以用以下方法計(jì)算：
    GMPY((01000001)<<24,，(100),，(01101001)<<24)>>24
3 CRC在C64x+DSP上的高效實(shí)現(xiàn)
    比較CRC的軟件實(shí)現(xiàn)代碼和GMPY指令的等效C語(yǔ)言代碼可以看出，一個(gè)字節(jié)的CRC碼可以用GMPY指令計(jì)算為GMPY(polynomial, data_byte, polynomial),。
    用GMPY實(shí)現(xiàn)的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語(yǔ)言函數(shù)調(diào)用的方式使用它，但DSP編譯器會(huì)把它編譯成一條GMPY指令,，而不是一個(gè)函數(shù)調(diào)用,。所有的C6000系列DSP指令都可以在C語(yǔ)音中按這種方式使用。
    以上代碼在C64x+上執(zhí)行,，每次循環(huán)需要大約6個(gè)時(shí)鐘周期,，它比查找表方法效率高,，而且不需要查找表,，這對(duì)于存儲(chǔ)器受限的應(yīng)用來(lái)說(shuō)非常合適。上述代碼每個(gè)循環(huán)需要6個(gè)時(shí)鐘周期的瓶頸因素是“循環(huán)依賴”,，即下一次循環(huán)運(yùn)算要基于前一次運(yùn)算的結(jié)果,，這使得C64x+指令流水線不能充分的流水式執(zhí)行。一種改進(jìn)的查找表方法可以解決這一問(wèn)題,，從而大大提高CRC計(jì)算的效率,。該方法使用的查找表可以由以下代碼生成：
    crc_lut[0]=polynomial；
    for(k=1,；k         crc_lut[k]=_gmpy(crc_lut[k-1]，0x100)),；//polynomialx8
    這種CRC的計(jì)算方法可用以下偽代碼表示：
    Index=length_of_byte-1,；
    for(k=0；k         crc=crc^_gmpy(crc_lut[Index--],，data_byte[k]))；
    為了更充分地利用C64x+ DSP并行流水式處理的能力,，并減少查找表的長(zhǎng)度,，可以進(jìn)一步對(duì)以上計(jì)算進(jìn)行優(yōu)化，每次循環(huán)處理32bit,。相應(yīng)的查找表長(zhǎng)度減少為原來(lái)的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計(jì)算可用以下偽代碼表示：
    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優(yōu)化實(shí)現(xiàn),，每次循環(huán)約需4個(gè)時(shí)鐘周期,，而一次循環(huán)處理4字節(jié)，所以每個(gè)字節(jié)的處理僅需約一個(gè)時(shí)鐘周期,。
    CRC是常用的檢錯(cuò)機(jī)制,，表1總結(jié)了幾種CRC的軟件實(shí)現(xiàn)方法在C64x+DSP上執(zhí)行的效率。

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