Very cool, Mark -- thanks for posting this! I was discussing this general issue with Jonathan Adams this afternoon. He's currently coding and measuring the performance and effectiveness of a number of fletcher2 variants, which I'll let him describe in exquisite detail.
Something we observed along the way: all orders of fletcher linear combinations of the data words, so it shouldn't matter what initial data block you use when checking for two-bit error detection. Also, note that the fletcher checksum of an all-zero block is zero. Therefore, you can find two-bit vulnerabilities by setting all possible pairs of bits in an otherwise all-zero block, and checking whether any of the resulting fletcher checksums are zero. Jeff On Tue, Mar 31, 2009 at 12:36:48AM -0700, Mark Butler wrote: > 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 > _______________________________________________ > zfs-code mailing list > zfs-code at opensolaris.org > http://mail.opensolaris.org/mailman/listinfo/zfs-code
