sponsors gamedev.net search:

Calculating CRC32 With the lookup table in place now we can look at the GetCRC32 function. This function takes a single byte and the previous calculated CRC32 value (if one exists). inline void ECRC32::GetCRC32(const BYTE byte, DWORD &dwCRC32){ dwCRC32 = (( dwCRC32 ) >> 8 )^ CRC32Table[( byte )^(( dwCrc32 ) & 0x000000FF )]; } First thing you should note is that the function is inline. For those of you who do not understand this specifier, wherever your code makes a call to this function, instead of jumping to the function's location in your memory every single time (which does consume a few cycles) it will actually insert a copy of the code where the function was called. It may only be a cycle or two that is saved every time the function is called, but if you try to calculate the CRC32 value of a 4Gig file you can see why one or two cycles for every bytes being processed can really save a lot of time. Note: the use of inline should not be taken lightly. It can cause extremely large increases in code size and may in the end decrease the overall performance of your application from consuming too much memory (which leads to limited resources and page faults during application execution). In our situation the actual instances where GetCRC32 is called are very limited and thus overall application size is not a concern. You may also want to look into the __fastcall specifier. __fastcall works by passing the arguments to a function through the CPU registers (when they will fit) as opposed to the standard way of passing them through the stack. This can create a notable speed increase just as inline does here. With the present byte, and previous CRC32 value the function performs a polynomial division, with a reference to the lookup table, and updates the CRC32 signature. Calculating for Structures The two previous functions core of our CRC32 algorithm. All that is left is to read the data, and using those two functions, generate a CRC32 signature for our data. DWORD ECRC32::CRC32ByStruct( BYTE* byStruct, DWORD dwSize, DWORD &dwCRC32 ){ // MAKE SURE WE HAVE A VALID BYTE STREAM if( byStruct == NULL ){ return -1; } dwCRC32 = 0xFFFFFFFF; // LOOP TO READ THE STRUCTURE for( DWORD i = 0; i < dwSize; i++ ){ GetCRC32( *byStruct, dwCRC32 ); byStruct++; } // FINISH UP dwCRC32 = ~dwCRC32; return 0; } The function takes in a BYTE pointer to the base address of the structure, and cycles through every byte of that structure passing each byte value to GetCRC32 with the previous CRC32 value. In the situation that a previous CRC32 value has not been calculated we will simply assign the value 0xFFFFFFFF. Before filling a structure with data that is to be calculated it is very important that we initialize the entire structure to NULL, the reason for this being that structures are usually padded to 8 bytes. In other words if you have a structure that has 7 chars (7bytes) sizeof( struct ) will still return 8bytes. The last bit will be initialized to a garbage value and may not be the same if you recreate that structure later, this will change the CRC32 value, causing them not to match. There is one other option though, when passing in the structure size, if you know the exact unpadded size of the structure you may use that value instead which will cause our algorithm to ignore any extra bytes from padding. You should not mix the two methods though since this will yield different non-matching CRC32 values between two exactly the same structures. Calculating for a file Calculating the CRC signature for a file is very similar though the function to do so does seem somewhat more complex - it really is not. We do however need to add an additional function that will calculate the size of the file before processing. bool ECRC32::GetFileSize( const HANDLE hFile, DWORD &dwSize ){ // WE HAVE TO HAVE A VALID HANDLE if( hFile == INVALID_HANDLE_VALUE ){ return false; } // NOW WE CAN GET THE FILE SIZE bool bException = false; dwSize = 0; try { // SETS THE UPPER AND LOWER SIZE VALUES dwSize = GetFileSize( hFile, NULL ); if( dwSize == INVALID_FILE_SIZE ){ bException = true; dwSize = 0; } } // SOMETHING SCREWED UP catch( ... ) { bException = true; } return !bException; } This function is called internally by CRC32ByFile so we do not have to worry about it a whole lot. Ideally what happens though is that after CRC32ByFile has opened the specified file (successfully I might add) it will attempt to pass the file pointer in and a pointer to a DWORD that will return the calculated size. The function returns true if it succeeded. The next little bit actually reads the file and passes the data to our CRC32 algorithm. // OPEN THE SPECIFIED FILE if(( hFile = CreateFile( strFileName, GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL \ | FILE_FLAG_SEQUENTIAL_SCAN, NULL )) == INVALID_HANDLE_VALUE ){ // THIS MEANS THAT WE HAVE AN ERROR dwErrorCode = -1; } // CALCULATE THE CRC32 SIGNATURE else { BYTE cBuffer[ 512 ]; DWORD dwBytesInOut, dwLoop; bool bSuccess = false; bSuccess = ReadFile( hFile, cBuffer, sizeof( cBuffer ), &dwBytesInOut, NULL ); while( bSuccess && dwBytesInOut ){ for( dwLoop = 0; dwLoop < dwBytesInOut; dwLoop++ ); GetCRC32( cBuffer[ dwLoop ], dwCRC32 ); bSuccess = ReadFile( hFile, cBuffer, sizeof( cBuffer ), &dwBytesInOut, NULL ); } } This is a small code snippet from the function provided in the demo that takes a file, opens it, fills a buffer with data, processes the CRC32 value for that data and repeats until it hits the end of the file. Other uses for CRC CRC32, like it is used in gaming, is also used outside of gaming for the same reasons; those being for file integrity checking and data integrity checking when data is copied. A great extension to this use that is also commonly employed in gaming is to add a CRC32 value into the packets that you are sending over the internet, this insures that data that arrives at a destination is the same as it was before it was sent. Though the TCP and UDP protocols have CRC values in their headers they will only verify each packet as they are transmitted. Structures and data that are sent over multiple packets may become corrupt and used without a CRC check. CRC can even be used for security purposes to insure that text messages, and other types of message, are not intentionally modified. This is a system that is commonly used in PGP when signing a message so that the receiving party can verify that it was in fact you who signed it. PGP does not actually use CRC32 with the signatures since CRC32 is somewhat weak in these situations. Other common algorithms used for these purposes would be algorithms such as MD5, SHA8, SHA256, etc. These are called HASH algorithms when used for security purposes. If you need to use a signature generator that produces a larger number of values than CRC32 and has to have a greater accuracy than you can look into the three algorithms I mentioned above. And finally, if you have any comments, question, or so forth you can usually find me on the #gamedev channel as kurifu, seta, or something else.

Contents   Page 1   Page 2   Source code   Printable version   Discuss this article