摘 要： 介紹循環(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指令,，用戶(hù)按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)依賴(lài)”,，即下一次循環(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)算的效率,。