Fletcher's checksum

From Wikipedia, the free encyclopedia

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 of the Fletcher-32 is very similar to the Adler-32 algorithm but several differences should be noted. Fletcher wraps around at modulo 65535 while Adler wraps at the prime 65521. Fletcher adds upper bits (16-31) into its sum while Adler drops these bits. Fletcher-32 works on 16 bit data while Adler works on 8 bit data.

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 the incrementing and decrementing of 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:

uint32_t fletcher( uint16_t *data, size_t len )
{
        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.
  • For 8 bit checksums (with 16 bit accumulators) the maximum number of sums that can be performed before doing the modular reduction is 21.


An efficient 8 bit implementation in the C programming language is as follows:

void fletcher( uint8_t *checkA, uint8_t *checkB, uint8_t *data, size_t len )
{
        uint16_t sum1 = 0xff, sum2 = 0xff;
 
        while (len) {
                size_t tlen = len > 21 ? 21 : len;
                len -= tlen;
                do {
                        sum1 += *data++;
                        sum2 += sum1;
                } while (--tlen);
                sum1 = (sum1 & 0xff) + (sum1 >> 8);
                sum2 = (sum2 & 0xff) + (sum2 >> 8);
        }
        /* Second reduction step to reduce sums to 8 bits */
        sum1 = (sum1 & 0xff) + (sum1 >> 8);
        sum2 = (sum2 & 0xff) + (sum2 >> 8);
        *checkA = (uint8_t)sum1;
        *checkB = (uint8_t)sum2;
        return;
}


[edit] References

  • Fletcher, J. G., “An Arithmetic Checksum for Serial Transmissions”, IEEE Trans. on Comm., Vol. COM-30, No. 1, January 1982, pp 247-252.

[edit] External links

Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.