I ran tests of every dual bit error case on an 8KB block containing the first 8K of a typical ELF executable with six checksum algorithms. I included two trivial checksums for comparison purposes. The undetected error counts are as follows, out of a total of 214783648 cases:
xor128: 16744448 (~3 x 10^-3 false negative rate) add64: 15763070 (~3 x 10^-3 false negative rate) fletcher2: 187606 (~4 x 10^-5 false negative rate) fletcher4: 0 crc32c: 0 "fletcher8": 0 The comparative single threaded bandwidth for these six checksums on a recent 32 bit x86 and gcc 4.1.2 w/ -O2 is as follows: add64: 8096 MB/s xor128: 5178 MB/s fletcher2: 4137 MB/s "fletcher8": 2038 MB/ crc32c: 1228 MB/s fletcher4: 612 MB/s Notes: 1. xor128 is a 128 bit exclusive or sum. 2. Add64 is a 64 bit two?s complement sum 3. The crc32c implementation was software implementation using an 8KB lookup table - no special instructions. 4. The processor was an Intel Q6600 running at 2.4 Ghz in 32 bit mode. 5. 130560 of those fletcher2 false negatives appear to be data independent error cases that occur due to the flipped parity of two 64 bit MSBs. You get exactly that many on a block consisting of all ones or all zeroes. 6. Despite its flaws, fletcher2 is two orders of magnitude better than weaker checksums of comparable speed. -- This message posted from opensolaris.org
