Fletcher's checksum is one of several types of checksum algorithms, which are relatively simple processes used by computers to check the integrity of data. A checksum is a form of redundancy check, a very simple measure for protecting the integrity of data by detecting errors in data that is sent through space (telecommunications) or time (storage). ...

The implementation is best described on the page for Adler-32 (a very similar algorithm). Replacing the modulo-65521 operation on large numbers with modulo-65535 gives you the Fletcher algorithm instead of Adler. Adler-32 is a checksum algorithm which was invented by Mark Adler. ...

It is designed to overcome some of the inadequacies of simply summing all the bytes as in the original checksum. Fletcher's checksum, unlike the original checksum, can detect the inserting/deleting of zero value bytes, the reordering of bytes, and incrementing and decrement of the bytes in opposite directions.

Fletcher's checksum is described in RFC 1146. You can also find information about generating (as well as verifying) such a checksum in Annex B of RFC 905.

An optimized implementation in the C programming language operates as follows: The C Programming Language, Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language is a standardized imperative computer programming language developed in the early 1970s by Ken Thompson and Dennis Ritchie for use on the...

 uint16_t *data; /* Pointer to the data to be summed */ size_t len; /* Length in 16-bit words */ uint32_t sum1 = 0xffff, sum2 = 0xffff; while (len) { unsigned tlen = len > 360 ? 360 : len; len -= tlen; do { sum1 += *data++; sum2 += sum1; } while (--tlen); sum1 = (sum1 & 0xffff) + (sum1 >> 16); sum2 = (sum2 & 0xffff) + (sum2 >> 16); } /* Second reduction step to reduce sums to 16 bits */ sum1 = (sum1 & 0xffff) + (sum1 >> 16); sum2 = (sum2 & 0xffff) + (sum2 >> 16); return sum2 << 16 | sum1; 

A few tricks, well-known to implementors of the IP checksum, are used here for efficiency:

• This reduces to the range 1..65535 rather than 0..65534. Modulo 65535, the values 65535 = 0xffff and 0 are equivalent, but it is easier to detect overflow if the former convention is used. This also provides the guarantee that the resultant checksum will never be zero, so that value is available for a special flag, such as "checksum not yet computed".
• 65536 ≡ 1 mod 65535, so the expression (x & 0xffff) + (x >> 16) reduces x modulo 65535. Only doing it once is not guaranteed to be complete, but it will be less than 0x1fffe. A second repetition guarantees a fully reduced sum in the range of 1..65535.
• This uses a 32-bit accumulator to perform a number of sums before doing any modular reduction. The magic value 360 is the largest number of sums that can be performed without numeric overflow. Any smaller value is also permissible; 256 may be convenient in many cases.

External links

• RFC 1146 TCP Alternate Checksum Options describes the Fletcher checksum algorithm.
• Performance of Checksums and CRCs over Real Data