Checksum
Fletcher’s checksum
Proposed by John G. Fletcher (Lawrence Livermore, 1982). Two running sums (one of the data, one of the first sum’s history) combined into a single output. Catches all single-bit, all double-bit, and all burst errors of short length , while running far faster than CRC. Widely deployed in network protocols where speed matters.
The three sizes
| Variant | Output | Modulus |
|---|---|---|
| Fletcher-16 | 16 bits | 255 |
| Fletcher-32 | 32 bits | 65535 |
| Fletcher-64 | 64 bits | 4294967295 |
How it works
Maintain two accumulators a, b initialized to 0 (or to a non-zero starting state per the variant). For each input word w: a = (a + w) mod M; b = (b + a) mod M. Output (b << bits) | a where bits is half the output width. Compared with Adler-32, the modulus is the Mersenne-like 2k−1 rather than a prime , making the modular reduction cheaper at the cost of slightly weaker distribution.
Where it shows up
- OSPF , Fletcher-16 over the routing-protocol packet header (RFC 1008 / 2328).
- ISO TP4 / X.224 , Fletcher-16 as the transport-layer checksum.
- SCTP (legacy) , Fletcher-32 in early drafts before the switch to CRC-32C (RFC 4960).
- UBIFS (Linux) , metadata integrity.
- ZFS (older versions) , one option for block-level checksums.
Limitations
Like every checksum on this list, Fletcher is non-cryptographic. Adversaries can construct collisions trivially. It also has a well-known limitation: a block of all-zero bytes followed by a single non-zero byte at the right position can mask error patterns.
References
- J. G. Fletcher, “An arithmetic checksum for serial transmissions,” IEEE Transactions on Communications, 1982.
- RFC 1008 , Implementation guide for the ISO Transport Protocol
- Adler-32 · Internet checksum