4 ms·
Fletcher's Checksum
- MarkSweep 8y agoFor some context, the Fletcher checksum algorithm is used by bother ZFS and APFS (the new Apple filesystem for iOS and macOS). So it is a fairly wildly used checksum algorithm.
- Annatar 8y agoThat was my first thought: "ZFS, Jeff Bonwick!"
- pvtmert 8y agoi have used this on couple projects most notably: - wireless network packet checksum - filesystem checksum good thing is that comes in variations, 16, 32 and 64 bits wide
- acqq 8y agoRelated: Modulus without Division, a tutorial http://homepage.divms.uiowa.edu/~jones/bcd/mod.shtml http://homepage.divms.uiowa.edu/~jones/bcd/mod.shtml
- Iwan-Zotow 8y agohttps://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-...
- senderista 8y agoThat is an alternative to using the modulo function for hashing, not an alternative implementation of the modulo function.
- epx 8y agoNot quite my tempo.
- wazoox 8y agorelated, the Mojette transform used by ROzoFS (an HPC filesystem): https://en.wikipedia.org/wiki/Mojette_Transform https://en.wikipedia.org/wiki/Mojette_Transform
- acranox 8y ago'The Fletcher checksum cannot distinguish between blocks of all 0 bits and blocks of all 1 bits.' For some reason, I find it fascinating to read about such a fundamental limitation. But I understand it doesn't apply much in the real world.
- maffydub 8y agoPresumably it depends on the modulus used? I think the article is assuming a modulus of 2^n-1. As the article says, Adler-32 is a specialization of Fletcher-32 that specifies a modulus of 65521 - that would seem to avoid this limitation.
- Isamu 8y agoThe original paper "An Arithmetic Checksum for Serial Transmissions" is worthwhile reading. Fletcher's background as a physicist shows through and the analysis is interesting as it contrasts to many other papers I have read on codes. Also: note the section in the Wikipedia page on the Adler checksum, which was an attempt to improve Fletcher's checksum by substituting a prime modulus. This stands to reason as a prime modulus is usually important in codes. This change was probably not backed up by analysis and through direct simulation has shown to actually weaken the checksum. Just pointing this out as an example of what I have observed personally: people tinkering with codes (nothing wrong with that) to improve them, without bothering to understand the analysis they would have to do to prove that they hadn't made things actually worse. [yet another edit:] If you find error-detecting and -correcting codes interesting or mysterious, read the original papers! So many fun and interesting things to see there, and it is a chance to motivate a look into areas of math you might be unfamiliar with. 'Nuff said.
- deleted 8y ago[deleted]