CRC32

程式庫特點

檢錯能力極強，開銷小，易於用編碼器及檢測電路實現。從其檢錯能力來看，它所不能發現的錯誤的幾率僅為0.0047%以下。從性能上和開銷上考慮，均遠遠優於奇偶校驗及算術和校驗等方式。因而，在數據存儲和數據通訊領域，CRC無處不在：著名的通訊協定X.25的FCS（幀檢錯序列）採用的是CRC-CCITT，ARJ、LHA等壓縮工具軟體採用的是CRC32，磁碟驅動器的讀寫採用了CRC16，通用的圖像存儲格式GIF、TIFF等也都用CRC作為檢錯手段。

算法

CRC的本質

是模-2除法的餘數，採用的除數不同，CRC的類型也就不一樣。通常，CRC的除數用生成多項式來表示。最常用的CRC碼的生成多項式如表1所示。最常用的CRC碼及生成多項式名稱生成多項式

CRC-12

CRC-16

CRC-CCITT

CRC-32

由於CRC在通訊和數據處理軟體中經常採用，筆者在實際工作中對其算法進行了研究和比較，總結並編寫了一個具有最高效率的CRC通用程式庫。該程式採用查表法計算CRC，在速度上優於一般的直接模仿硬體的算法，可以套用於通訊和數據壓縮程式。

通常算法

通常的CRC算法在計算一個數據段的CRC值時，其CRC值是由求解每個數值的CRC值的和對CRC暫存器的值反覆更新而得到的。這樣，求解CRC的速度較慢。通過對CRC算法的研究，我們發現:一個8位數據加到16位累加器中去，只有累加器的高8位或低8位與數據相作用，其結果僅有256種可能的組合值。因而，我們可以用查表法來代替反覆的運算，這也同樣適用於CRC32的計算。本文所提供的程式庫中，函式crchware是一般的16位CRC的算法；mk-crctbl用以在記憶體中建立一個CRC數值表；crcupdate用以查表並更新CRC累加器的值；crcrevhware和crcrevupdate是反序算法的兩個函式；BuildCRCTable、CalculateBlockCRC32和UpdateCharac

terCRC32用於CRC32的計算。

/*CRC.C——CRC程式庫*/#define CRCCCITT0x1021#define CCITT-REV0x8408#define CRC160x8005#define CRC16-REV0xA001#define CRC32-POLYNOMIAL0xEDB88320L/*以上為CRC除數的定義*/#define NIL0#define crcupdate(d,a,t)   *(a)=(*(a)<<8)^(t)[(*(a)>>8)^(d)];#define crcupdate16(d,a,t) *(a)=(*(a)>>8^(t)[(*(a)^(d))&0x00ff])/*以上兩個宏可以代替函式crcupdate和crcrevupdate*/#include <stdio.h>#include <stdlib.h>#include <alloc.h>/*函式crchware是傳統的CRC算法，其返回值即CRC值*/unsigned short crchware(data,genpoly,accum)unsigned short data;/*輸入的數據*/unsigned short genpoly;/*CRC除數*/unsigned short accum;/*CRC累加器值*/{    static int i;    data<<=8;    for(i=8;i>0;i--)    {        if((data^accum)&0x8000)        accum=(accum<<1)^genpoly;        else        accum<<=1;        data<<=1;    }    return(accum);}/*函式mk-crctbl利用函式crchware建立記憶體中的CRC數值表*/unsigned short *mk-crctbl(poly,crcfn);unsigned short poly;        /*CRC除數--CRC生成多項式*/R>unsigned short(*crcfn)();  /*指向CRC函式(例如crchware)的指針*/{    /*unsignedshort*/malloc();*/    unsignedshort*crctp;    inti;    if((crctp=(unsignedshort*)malloc(256*sizeof(unsigned)))==0)    return0;    for(i=0;i<256;i++)    crctp=(*crcfn)(i,poly,0);    returncrctp;}/*函式mk-crctbl的使用範例*/if((crctblp=mk-crctbl(CRCCCITT,crchware))==NIL){    puts("insuffmemoryforCRClookuptable.n");    return1;*/    /*函式crcupdate用以用查表法計算CRC值並更新CRC累加器值*/    voidcrcupdate(data,accum,crctab)    unsignedshortdata;/*輸入的數據*/    unsignedshort*accum;/*指向CRC累加器的指針*/    unsignedshort*crctab;/*指向記憶體中CRC表的指針*/    {        staticshortcomb-val;        comb-val=(*accum>>8)^data;        *accum=(*accum<<8)^crctab[comb-val];    }    /*函式crcrevhware是傳統的CRC算法的反序算法，其返回值即CRC值*/    unsignedshortcrcrevhware(data,genpoly,accum)    unsignedshortdata;    unsignedshortgenpoly;    unsignedshortaccum;    {        staticinti;        data<<=1;        for(i=8;i>0;i--)        {            data>>=1;            if((data^accum)&0x0001)            accum=(accum>>1)^genpoly;            else            accum>>=1;        }        returnaccum;    }    /*函式crcrevupdate用以用反序查表法計算CRC值並更新CRC累加器值*/    voidcrcrevupdate(data,accum,crcrevtab)    unsignedshortdata;    unsignedshort*accum;DvNews

CRC32

基本介紹

程式庫特點

算法

說明

相關詞條

熱門詞條