Robust and fast checksum algorithm?

Question

Which checksum algorithm can you recommend in the following use case?

I want to generate checksums of small JPEG files (~8 kB each) to check if the content changed. Using the filesystem's date modified is unfortunately not an option.
The checksum need not be cryptographically strong but it should robustly indicate changes of any size.

The second criterion is speed since it should be possible to process at least hundreds of images per second (on a modern CPU).

The calculation will be done on a server with several clients. The clients send the images over Gigabit TCP to the server. So there's no disk I/O as bottleneck.

Answer 1

If you have many small files, your bottleneck is going to be file I/O and probably not a checksum algorithm.

A list of hash functions (which can be thought of as a checksum) can be found here.

Is there any reason you can't use the filesystem's date modified to determine if a file has changed? That would probably be faster.

Answer 2

CRC

Answer 3

• CRC-32 comes into mind mainly because it's cheap to calculate

• Any kind of I/O comes into mind mainly because this will be the limiting factor for such an undertaking ;)

• The problem is not calculating the checksums, the problem is to get the images into memory to calculate the checksum.

• I would suggest "stagged" monitoring:

  • stage 1: check for changes of file timestamps and if you detect a change there hand over to...
    
    (not needed in your case as described in the edited version)

  • stage 2: get the image into memory and calculate the checksum

• For sure important as well: multi-threading: setting up a pipeline which enables processing of several images in parallel if several CPU cores are available.

Answer 4

There are lots of fast CRC algorithms that should do the trick: http://www.google.com/search?hl=en&q=fast+crc&aq=f&oq=

Edit: Why the hate? CRC is totally appropriate, as evidenced by the other answers. A Google search was also appropriate, since no language was specified. This is an old, old problem which has been solved so many times that there isn't likely to be a definitive answer.

Answer 5

alder32, available in the zlib headers, is advertised as being significantly faster than crc32, while being only slightly less accurate.

Answer 6

CRC32 is probably good enough, although there's a small chance you might get a collision, such that a file that has been modified might look like it hasn't been because the two versions generate the same checksum. To avoid this possibility I'd therefore suggest using MD5, which will easily be fast enough, and the chances of a collision occurring is reduced to the point where it's almost infinitessimal.

As others have said, with lots of small files your real performance bottleneck is going to be I/O so the issue is dealing with that. If you post up a few more details somebody will probably suggest a way of sorting that out as well.

Answer 7

Your most important requirement is "to check if the content changed".

If it most important that ANY change in the file be detected, MD-5, SHA-1 or even SHA-256 should be your choice.

Given that you indicated that the checksum NOT be cryptographically good, I would recommend CRC-32 for three reasons. CRC-32 gives good hamming distances over an 8K file. CRC-32 will be at least an order of magnitude faster than MD-5 to calculate (your second requirement). Sometimes as important, CRC-32 only requires 32 bits to store the value to be compared. MD-5 requires 4 times the storage and SHA-1 requires 5 times the storage.

BTW, any technique will be strengthened by prepending the length of the file when calculating the hash.

Answer 8

According to the Wiki page pointed to by Luke, MD5 is actually faster than CRC32!

I have tried this myself by using Python 2.6 on Windows Vista, and got the same result.

Here are some results:

crc32: 162.481544276 MBps md5: 224.489791549 MBps

crc32: 168.332996575 MBps md5: 226.089336532 MBps

crc32: 155.851515828 MBps md5: 194.943289532 MBps

I am thinking about the same question as well, and I'm tempted to use the Rsync's variation of Adler-32 for detecting file differences.

Answer 9

Just a postscript to the above; jpegs use lossy compression and the extent of the compression may depend upon the program used to create the jpeg, the colour pallette and/or bit-depth on the system, display gamma, graphics card and user-set compression levels/colour settings. Therefore, comparing jpegs built on different computers/platforms or using different software will be very difficult at the byte level.