Fletcher's checksum
|
|
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.
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.
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:
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 =
0xffffand 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)reducesxmodulo 65535. Only doing it once is not guaranteed to be complete, but it will be less than0x1fffe. 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 (http://www.faqs.org/rfcs/rfc1146.html) TCP Alternate Checksum Options describes the Fletcher checksum algorithm.
- Performance of Checksums and CRCs over Real Data (http://www.network.com/hughes/AAL5_CRC.ps)