-
CRC32
鎖定
CRC32程序庫特點
檢錯能力極強，開銷小，易於用編碼器及檢測電路實現。從其檢錯能力來看，它所不能發現的錯誤的幾率僅為0.0047%以下。從性能上和開銷上考慮，均遠遠優於奇偶校驗及算術和校驗等方式。因而，在數據存儲和數據通訊領域，CRC無處不在：著名的通訊協議X.25的FCS（幀檢錯序列）採用的是CRC-CCITT，ARJ、LHA等壓縮工具軟件採用的是CRC32，磁盤驅動器的讀寫採用了CRC16，通用的圖像存儲格式GIF、TIFF等也都用CRC作為檢錯手段。
CRC32算法
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
2.
crc32 — 計算一個字符串的 crc32 多項式
CRC32説明
int crc32
( string$str )
生成str的 32 位循環冗餘校驗碼多項式。這通常用於檢查傳輸的數據是否完整。
示例中演示瞭如何使用printf()函數轉換校驗碼：
校驗碼
Example #1 顯示兩個字符串 crc32 值相同的校驗碼：
<?php
$a = crc32("c294f5b1");
$b = crc32("fc26498f");
printf("%u\n",$a);
printf("%u\n",$b);
?>
