CRC32: Generating a checksum for a file

• Download source files - 17 Kb
• Download demo project - 8 Kb

Introduction

Recently I wrote a program in which I wanted to generate a CRC for a given file. I did some checking on the web for sample CRC code, but found very few algorithms to help me. So I decided to learn more about CRCs and write my own code. This article describes what a CRC is, how to generate them, what they can be used for, and lastly source code showing how it's done.

What is a CRC

CRC is an acronym for Cyclic Redundancy Checksum or Cyclic Redundancy Check (depending on who you ask). A CRC is a "digital signature" representing data. The most common CRC is CRC32, in which the "digital signature" is a 32-bit number. The "data" that is being CRC'ed can be any data of any length; from a file, to a string, or even a block of memory. As long as the data can be represented as a series of bytes, it can be CRC'ed. There is no single CRC algorithm, there can be as many algorithms as there are programmers. The ideal CRC algorithm has several characteristics about it. First, if you CRC the same data more than once, you must get the same CRC every time. Secondly, if you CRC two different pieces of data you should get two very different CRC values. If you CRC the same data twice, you get the same digital signature. But if you CRC data that differs (even by a single byte) then you should get two very different digital signatures. With a 32-bit CRC there are over 4 billion possible CRC values. To be exact that's 2³² or 4,294,967,296. With that many CRC values it's not difficult for every piece of data being CRC'ed to get a unique CRC value. However, it is possible for spurious hits to happen. In other words two completely different pieces of data can have the same CRC. This is rare, but not so rare that it won't happen.

Why use CRCs

Most of the time CRCs are used to compare data as an integrity check. Suppose there are two files that need to be compared to determine if they are identical. The first file is on Machine A and the other file is on Machine B. Each file is a rather large file (say 500 MB), and there is no network connection between the two machines. How do you compare the two files? The answer is CRC. You CRC each of the two files, which gives you two 32-bit numbers. You then compare those 32-bit numbers to see if they are identical. If the CRC values are different, then you can be 100% guaranteed that the files are not the same. If the CRC values are the same, then you can be 99% sure that the files are the same. Remember, because spurious hits can happen you cannot be positive that the two files are identical. The only way to be positive they are the same is to break down and do a comparison one byte at a time. But CRCs offer a quick way to be reasonably certain that two files are identical.

How to generate CRCs

Generating CRCs is a lot like cryptography in that involves a lot of mathematical theories. Since I don't fully understand it myself, I won't go into a lot of those details here. Instead I'll focus on how to program a CRC algorithm. Once you know how the algorithm works you should be able to write a CRC algorithm in any language on any platform. The first part of generating CRCs is the CRC lookup table. In CRC32 this is a table of 256 specific CRC numbers. These numbers are generated by a polynomial (the computation of these numbers and what polynomial to use are part of that math stuff I'm avoiding). The next part is a CRC lookup function. This function takes two things, a single byte of data to be CRC'ed and the current CRC value. It does a lookup in the CRC table according to the byte provided, and then does some math to apply that lookup value to the given CRC value resulting in a new CRC value. The last piece needed is the actual data that is to be CRC'ed. The CRC algorithm reads the first byte of data and calls the CRC lookup function which returns the CRC value for that single byte. It then calls the CRC lookup function with the next byte of data and passes the previous CRC value. After the second call, the CRC value represents the CRC of the first two bytes. You continuously call the CRC lookup function until all the bytes of the data have been processed. The resulting value is the CRC for the whole data.

Code Details

In this sample program I wanted to show that there are many different ways of generating CRCs. There are over 8 different CRC functions, all based on the above steps for generating CRCs. Each function differs slightly in it's intended use or optimization. There are four main CRC functions, each described below. There are also two separate CRC classes, but more on that later. And lastly there are a few helper functions that CRC strings.

C++ Streams: The first function represents the simplest CRC function. The file is opened using the C++ stream classes (ifstream). This function uses nothing but standard C++ calls, so this function should compile and run using any C++ compiler on any OS.

Win32 I/O: This function is more optimized in that it uses the Win32 API for file I/O; CreateFile, and ReadFile. This will speed up the processing, but by using the Win32 API the code is no longer platform independent.

Filemaps: This function uses memory mapped files to process the file. Filemaps can be used to greatly increase the speed with which files are accessed. They allow the contents of a file to be accessed as if it were in memory. No longer does the programmer need to call ReadFile and WriteFile.

Assembly: The final CRC function is one that is optimized using Intel Assembly. By hand writing the assembly code the algorithm can be optimized for speed, although at the sacrifice of being easy to read and understand.

Those are the four main CRC functions. But there are actually two versions of each function. There are two classes, CCrc32Dynamic and CCrc32Static, each of which have the above four functions for a total of eight. The only difference between the static and dynamic classes is the CRC table. With the static class the CRC table and all the functions in the class are static. The trade off is simple. The static class is simpler to use, but the dynamic class uses memory more efficiently because the CRC table (1K in size) is only allocated when needed.

// Using the static class is as easy as one line of code

dwErrorCode = CCrc32Static::FileCrc32Assembly(m_strFilename, dwCrc32);

// Whereas there is more involved when using the dynamic class

CCrc32Dynamic *pobCrc32Dynamic = new CCrc32Dynamic;
pobCrc32Dynamic->Init();
dwErrorCode = pobCrc32Dynamic->FileCrc32Assembly(m_strFilename, dwCrc32);
pobCrc32Dynamic->Free();
delete pobCrc32Dynamic;

Whenever you calculate a CRC you need to take into account the speed of the algorithm. Generating CRCs for files is both a CPU and a disk intensive task. Here is a table showing the time it took to CRC three different files. The columns are the different file sizes, the rows are the different CRC functions, and the table entries are in seconds. The system these numbers were captured on is a dual Pentium III at 1 GHz with a 10,000 RPM SCSI Ultra160 hard drive.

	44 Kb	34 Mb	5 Gb
C++ Streams	0.0013	0.80	125
Win32 I/O	0.0009	0.60	85
Filemaps	0.0010	0.60	87
Assembly	0.0006	0.35	49

As expected the C++ streams is the slowest function followed by the Win32 I/O. However, I was very surprised to see the filemaps were not faster than the Win32 I/O, in fact they are slower. After I thought about it some, I realized memory mapped files are designed to provide fast random access to files. But when you CRC you access the file sequentially. Thus filemaps are not faster, and the extra overhead of creating the "views" of the file are why it's slower. Filemaps do have one advantage that none of the other functions have. Memory mapped files are guaranteed to be able to access files up to the maximum file size in NT which is 2⁶⁴ or 18 exabytes. Although the Win32 I/O may handle files of this size, none of the documentation confirms this. [Note: The largest file I have CRC'ed is 40 GB, which all eight functions successfully CRC'ed, but took over 10 minutes each.]

If anyone who reads this article knows a way to improve the speed even more, please post the code or email me. Especially if you know of a speed improvement for the assembly code. I will bet there are further optimizations that can be made to the assembly code. After all I don't know Intel Assembly very well, therefore I'm sure there are optimizations I don't know about.

You must Sign In to use this message board.

FAQ    Noise Tolerance Very HighHighMediumLowVery Low   Layout Expand Posts & RepliesThread ViewNo JavascriptNo JS + Preview   Per page 102550

Msgs 1 to 25 of 84 (Total in Forum: 84) (Refresh) FirstPrevNext

Thank you very much! yulin11 23:59 1 Oct '08   Hi,I want to say that I am looking for a crc source code like this. I found a lot of them, but this one I think is the best. So, thank you very much for offering such good source code. codeuu,source code Sign In·View Thread·PermaLink How many errors.. Rikard Astrof 0:01 25 Feb '08   How many bit errors can a 32-bit CRC detect before it can't properly detect anymore? is it 32? Sign In·View Thread·PermaLink Re: How many errors.. supercat9 9:40 14 Apr '08   With an 'n' bit CRC, any change that is confined to a single n-bit region of a file will be detected. Most common CRCs will also detect any combination of errors that flip an odd number of bits, and any two-bit error where the bits are not separated by a multiple of 2^(n-1) bits. Although CRC's are excellent for detecting bit errors that fit the above patterns, inputs with an even number of bit errors >= 4, where the errors are not confined to an 'n' bit region may often go undetected. Sign In·View Thread·PermaLink Licensing allen_ellison 17:33 15 Jan '08   Is this code public domain? Sign In·View Thread·PermaLink Computing File CRC in VBScript Milind Mehendale 20:06 25 Nov '07   Hello, Can I compute file CRC using VBScript? If yes, how?? Regards, Milind Sign In·View Thread·PermaLink 2.00/5 (1 vote) How to compile? maxsubzero 14:51 30 Oct '06   Hi, I'm new in this forum and I'm interesting in crc, I would like to learn about it?, I have done a little code (just C) for small files (<1mb)... I want to compile (and execute) the code but I don't know how I can do this.. may you help me? I use Mingw32 (gcc) , but if i need another compiler i can get it, just say it. thanks Sign In·View Thread·PermaLink 2.00/5 (2 votes) Re: How to compile? VEMS 10:36 9 Jan '07   You can get VS 2005 Express for free at http://msdn.microsoft.com/vstudio/express/[^] Sign In·View Thread·PermaLink Re: How to compile? maxsubzero 12:05 20 Jan '07   Thanks!! I'll get it now. Sign In·View Thread·PermaLink Re: How to compile? chris_liush 20:33 22 Oct '07   Error 2 fatal error C1083: Cannot open include file: 'fstream.h': No such file or directory c:\documents and settings\chris.liu\桌面\crc_file\crc32_src\crc32\crc32dynamic.cpp 3 can not open fstream.h my IDE is vs2005 Sign In·View Thread·PermaLink Re: How to compile? ispeedonthe405 14:50 16 Nov '07   Under the current version you'll have to make some code changes to get it to compile. 1) Change fstream.h to fstream 2) You'll need to specify the std namespace, either with a using namespace std; in the file or prefixing with std:: 3) ios::nocreate no longer exists. You can change it to ios::_Nocreate but I don't believe that's portable (vendor-specific). If you're only building on Windows then that's fine. 4) Get rid of the filebuf::sh_read parameter in the open() calls. Assuming #3 above, it should now look like this: file.open(szFilename, ios::in | ios::_Nocreate | ios::binary); Sign In·View Thread·PermaLink 3.25/5 (3 votes) Re: How to compile? tianjianii 0:29 27 Jun '08   ios::in will not create and ios::in|ios:ut will not create anyway, so just remove ios::nocreate. Sign In·View Thread·PermaLink Re: How to compile? Tim Stubbs 4:33 6 Aug '09   thanks for taking the time Tim Stubbs Sign In·View Thread·PermaLink link error JakeFront 7:31 19 Sep '06   Hi I have used some of your code in my project, namely the CCrc32Static. I only want this function, the others i have commented out as i will not need them. I have hard coded a test file in the main but when i build i get the following error. Crc error LNK2019: unresolved external symbol "public: static void __cdecl CCrc32Static::CalcCrc32(unsigned char,unsigned long &)" (?CalcCrc32@CCrc32Static@@SAXEAAK@Z) referenced in function _main I have seen the ASSERT thread below but i don't fully understand where to put that in my code. I have the code below. // Crc.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "crc32Static.h" #include #include #include #include using namespace std; int main () { DWORD dwCrc32, dwErrorCode = NO_ERROR; (m_strFilename, dwCrc32); ifstream fin; string string1 = "", string2, string3; fin.open("C:\\test\\xml files\\2605",ios::in); if (fin.is_open()) { fin >> string1; while (string1 != "") { fin >> string1; } char buffer[MAX_BUFFER_SIZE]; int nLoop, nCount; nCount = fin.read(buffer, sizeof(buffer)).gcount(); while(nCount) { for(nLoop = 0; nLoop < nCount; nLoop++) //CalcCrc32(buffer[nLoop], dwCrc32); CCrc32Static::CalcCrc32(buffer[nLoop], dwCrc32); nCount = fin.read(buffer, sizeof(buffer)).gcount(); } } } with the helper class as follows DWORD CCrc32Static::s_arrdwCrc32Table[256] = { //static table }; //*********************************************** CCrc32Static::CCrc32Static() { } //*********************************************** CCrc32Static::~CCrc32Static() { } //*********************************************** inline void CCrc32Static::CalcCrc32(const BYTE byte, DWORD &dwCrc32) { dwCrc32 = ((dwCrc32) >> 8) ^ s_arrdwCrc32Table[(byte) ^ ((dwCrc32) & 0x000000FF)]; } I have included the common file. Thanks for your help in Advance. Rick Sign In·View Thread·PermaLink 2.00/5 (1 vote) Re: link error Brian Friesen 13:44 19 Sep '06   I'm not sure. What changes, if any, did you make to Crc32Static.h? Sign In·View Thread·PermaLink 2.00/5 (1 vote) Re: link error JakeFront 22:58 19 Sep '06   Yes i made the following changes in Crc32staic.h file #ifndef _CRC32STATIC_H_ #define _CRC32STATIC_H_ #include "Common.h" class CCrc32Static { public: CCrc32Static(); virtual ~CCrc32Static(); static inline void CalcCrc32(const BYTE byte, DWORD &dwCrc32); static DWORD s_arrdwCrc32Table[256]; protected: }; #endif and i am using VS2003 Rick Sign In·View Thread·PermaLink 2.00/5 (1 vote) Re: link error aldasp 5:15 28 Nov '06   You must delete from function definition inline directive --- Aldas Sign In·View Thread·PermaLink Re: link error JakeFront 6:02 28 Nov '06   Thanks for your help I found the solution to be to re order the header files in the stdafx files and the link error disappears #include #include // MFC core and standard components #include // MFC extensions #include // MFC support for Internet Explorer 4 Common Controls #ifndef _AFX_NO_AFXCMN_SUPPORT #include // MFC support for Windows Common Controls #endif // _AFX_NO_AFXCMN_SUPPORT #include Rick Sign In·View Thread·PermaLink Should I Change CRC Table? OffLineR 22:26 31 Jan '06   Dear Brian, Should I change the values in the CRC Table. I am planning to use CRC for security reasons and I would like to have my unique results when I use CRC algorithm. Thanks a lot. Cheers Koray Sign In·View Thread·PermaLink 1.00/5 (1 vote) Re: Should I Change CRC Table? aldasp 21:58 28 Nov '06   For security traditionally used md5 algorithm it gives longer result, but it is no easy way to make falsification -- Aldas Sign In·View Thread·PermaLink 4.33/5 (2 votes) Thanks OffLineR 22:20 31 Jan '06   Thanks a lot for this article. It will be very helpful. Cheers. Koray Sign In·View Thread·PermaLink Different CRC Sniper167 11:56 22 Jan '06   I have another program that detects CRC's too but when I open the same file with both your program and the other one it picks up two different CRC's. Why? Sniper167 Sign In·View Thread·PermaLink 5.00/5 (1 vote) Re: Different CRC Brian Friesen 13:09 22 Jan '06   There are many different CRC algorithms, just as there are many different compression algorithms. The algorithm my program uses is the same that PKWare and Ethernet use. It sounds like this other CRC program you're using generates CRCs using a different algorithm, hence the different result. Sign In·View Thread·PermaLink 3.00/5 (2 votes) Re: Different CRC VEMS 10:49 9 Jan '07   You shouldn't. If you are, pretty useless across networks and file transfer. CRC32 in control by RFC 3309 (RFC3309) Sign In·View Thread·PermaLink Re: Different CRC awneil 4:30 14 Jul '08   Brian Friesen wrote: There are many different CRC algorithms, just as there are many different compression algorithms. This is, of course, very true - which makes it a bit naughty of you not to have mentioned anywhere in the article or the source which particular algoritm you were implementing! Sign In·View Thread·PermaLink 1.50/5 (2 votes) this is not the way to use CRC jt_roxas 15:30 10 Dec '05   Firstly I commend you for your efforts in posting your code here.. I think you missunderstood the usage of CRC. CRC is not supposed to be used as checksum for large files. the reason for this is that you are representing say a 40GB file(based from your sample) with only only a 32bit value which only has 2^32 combinations as opposed to a a file with 2^(40GB*8bits) combination.. this will mean that there will be ( 2^(40GB*8bits) divided by 2^32bits )2^319999999968 files of the same 40GB size having the same CRC value at the most. Ofcors you can modify 1byte or a char at a tyme and it will generate a diferent CRC but try doing it at several hundred location and Iterate you will see that there will be many(billions) times that your code generates no error even when files are completely different.... You see CRC where created mostly with transmission protocols which sends data in packets that are only a few BYTES in length i.e. like in ISDN which has a default packet size of 2048bytes (including the CRC16 value whatever your modem use). the modem calculates the CRC for this 2048bytes and sent it with the packet so the receiving end can check for data corruption to resent the packet. In Ethernet the packet size are much larger so instead of using a 16bit CRC value they use a larger number CRC32(32bit) to represent a larger packet size so the probability of cathing an error is not reduced compared to a modem with a smaller packetsize.. when a file is sent through a modem the protocol or a hardware in the modem segments the file into packets and compute the CRC for each packet and not for the whole file. I hope this Clears up things.... thanks, Sign In·View Thread·PermaLink 4.25/5 (8 votes)

Last Visit: 0:29 9 Nov '09     Last Update: 0:29 9 Nov '09 1234 Next »