程式扎記: [C++ 文章收集] CRC32 Algorithm : Cyclic Redundancy Check

標籤

2011年3月14日 星期一

[C++ 文章收集] CRC32 Algorithm : Cyclic Redundancy Check


轉載自 這裡
前言 :
CRC is a "digital fingerprint" of a file.
With CRC32 you can get a single 32-bit number that represents a string or file (of any size). If the file data changes in any way (even a single bit) the CRC32 calculation would yield a completely different value. This algorithm is used by WinZip and PKZIP (ie the same numbers are generated) so:
pkunzip.exe -vt File.zip gives the same CRC value as you get by giving the file to this code.
A single 1kB table is allocated while instances of CCRC32 exist.

使用範例 :
你可以直接將 Buffer/Content 傳進 CCRC32 From 函式運算 CRC Code :
  1. DWORD CRC=CCRC32().From(Buffer,Size);  
或透過由 CCRC32 建立的物件操作 :
  1. CCRC32 CRC32;  
  2. DWORD CRC1=CRC32.From(Buffer1,Size1);  
  3. DWORD CRC2=CRC32.From(Buffer2,Size2);  
如果來源是檔案, 你可以這麼做 :
  1. int OK;  
  2. CCRC32 CRC32;  
  3. BYTE Buffer[1024];  
  4. FILE* File=fopen("C:\\CheckMe.txt","rb");  
  5. if(File) do CRC32.From(Buffer, OK=fread(Buffer, 11024, File), true); while(OK);  
  6. fclose(File);  
  7. DWORD CRC=CRC32.GetCRC();  
事實上, 你也可以將檔案開啟, 讀取與關閉交給 CRC32 類別處理, 而直接將檔案路徑傳入 :
  1. DWORD CRC=CCRC32().From("C:\\CheckMe.txt");  
CRC32實作代碼 :
底下是 CRC32 類別實作的標頭檔 :
- CRC32.h :
  1. // CRC32.h  
  2.   
  3. #ifndef CRC32h  
  4. #define CRC32h  
  5.   
  6. #if _MSC_VER > 1000  
  7. #pragma once  
  8. #endif // _MSC_VER > 1000  
  9.   
  10. /* CRC is a "digital fingerprint" of a file. 
  11. With CRC32 you can get a single 32-bit number that represents a string or file (of any size). 
  12. If the file data changes in any way (even a single bit) the CRC32 calculation would yield a completely different value. 
  13. This algorithm is used by WinZip and PKZIP (ie the same numbers are generated) so: 
  14. pkunzip.exe -vt File.zip gives the same CRC value as you get by giving the file to this code. 
  15.  
  16. A single 1kB table is allocated while instances of CCRC32 exist. 
  17.  
  18. Usage: 
  19.   DWORD CRC=CCRC32().From(Buffer,Size); 
  20.  
  21. or use one instance for several CRCs: 
  22.   CCRC32 CRC32; 
  23.   DWORD CRC1=CRC32.From(Buffer1,Size1); 
  24.   DWORD CRC2=CRC32.From(Buffer2,Size2); 
  25.  
  26. or if reading data in blocks: 
  27.   int OK; 
  28.   CCRC32 CRC32; 
  29.   BYTE Buffer[1024]; 
  30.   FILE* File=fopen("C:\\CheckMe.txt","rb"); 
  31.   if(File) do CRC32.From(Buffer, OK=fread(Buffer, 1, 1024, File), true); while(OK); 
  32.   fclose(File); 
  33.   DWORD CRC=CRC32.GetCRC(); 
  34.  
  35. But since we want the fastest routines we should use CreateFile 
  36. and thats what the class uses internally for retrieving the CRC32 of a file: 
  37.   DWORD CRC=CCRC32().From("C:\\CheckMe.txt"); 
  38. */  
  39. class CCRC32 {  
  40.   DWORD*  Tbl; // These let us use the static variables in the constructor without having to have a .cpp file to initialise the statics  
  41.   int*    Instances;  
  42.   DWORD   LastCRC;  
  43. public:  
  44.   CCRC32() {  
  45.     static DWORD* StaticTbl=0;       // Table of CRC values for every possible BYTE  
  46.     static int    StaticInstances=0// Count of references to Tbl (Instances of CCRC32)  
  47.     Tbl=StaticTbl;  
  48.     Instances=&StaticInstances;  
  49.     if(Tbl) ++Instances;  
  50.     else {  
  51.       LastCRC=-1;  
  52.       *Instances=0;  
  53.       Tbl=new DWORD[256];  
  54.       if(!Tbl) return;  
  55.       *Instances=1;  
  56.       DWORD* ptr=Tbl;  
  57.       for(DWORD n=0; n<256; ++n){  
  58.         DWORD c=n;  
  59.         for(int k=0; k<8; ++k) c=(c&1 ? 0xEDB88320^(c>>1) : c>>1);  
  60.         *ptr++=c;  
  61.     } }  
  62.   }  
  63.   virtual ~CCRC32() {  
  64.     if(*Instances) --*Instances;  
  65.     if(*Instances) return;  
  66.     try{delete[] Tbl;}catch(...){}  
  67.     Tbl=0;  
  68.   }  
  69.   DWORD GetCRC() const {return ~LastCRC;}  
  70.   
  71.   DWORD From(const char* Path, bool Partial=false) {  
  72.     if(!Partial) Reset();  
  73.     DWORD OK;  
  74.     char Buffer[1024];  
  75.     HANDLE File=CreateFile(Path, GENERIC_READ, FILE_SHARE_READ, 0, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL, 0);  
  76.     if(File) do {  
  77.       ReadFile(File, Buffer, sizeof(Buffer), &OK, 0);  
  78.       From(Buffer, OK, true);  
  79.     }while(OK);  
  80.     CloseHandle(File);  
  81.     return GetCRC();  
  82.   }  
  83.   
  84.   void Reset() {LastCRC=-1;} // Only use this to use one CRC32 class for a whole new checksum when only using From(...) with Partial=true.  
  85.   
  86. // Since all that happens with the Buffer is an Exclusive OR operation, it doesn't matter if Buffer holds signed or unsigned chars.  
  87.   DWORD From(const char* Buffer, int   Len, bool Partial=false) {return From(Buffer, (DWORD)Len, Partial);}  
  88.   DWORD From(const char* Buffer, DWORD Len, bool Partial=false) {  
  89.     if(!Len || !Tbl || !Buffer) return 0;  
  90.     register DWORD CRC=(Partial ? LastCRC : LastCRC=-1);  
  91.     while(Len--) CRC=(CRC>>8)^Tbl[(CRC^(*Buffer++))&0xFF]; // Modern processors will NOT benefit from coded loop optimisation techniques (unrolling)!  
  92.     return ~(LastCRC=CRC);  
  93.   }  
  94. };  
  95.   
  96. #ifdef Assert // Run tests if Tester.h is included in stdafx.h  
  97. namespace { // namespace prevents multiple definitions if instantiating in the header like this:  
  98.   struct CRC32Tester : Tester, CCRC32 {  
  99.     CRC32Tester() {  
  100.       Assert(From("resume",6)==0x60C1D0A0);  
  101.       Assert(From("resum�",6)==0x84CF1FAB);  
  102.       Assert(From("foo",3)==0x8C736521);  
  103.       Assert(From("test0123456789",24)==0x97F206A3);  
  104.       Assert(From("\x80\x00",2)==0x7A5A8AB4);  
  105.       Assert(From("\x00\x08",2)==0x4F029ACD);  
  106.       Assert(From("\x00\x80",2)==0xAC6191DF);  
  107.       Assert(From("\x80",1)==0x3FBA6CAD);  
  108.       Assert(From("\x80\x00\x00\x00",4)==0xCC1D6927);  
  109.       Assert(From("\x00\x00\x00\x01",4)==0x5643EF8A);  
  110.     }  
  111.   } _CRC32Tester;  
  112. }  
  113. #endif // def Assert  
  114.   
  115. #endif // ndef CRC32h  
This message was edited 1 time. Last update was at 14/03/2011 15:21:39

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!