Fletcher’s Checksum

November 22, 2013

We have seen the SYSV and BSD checksum algorithms in previous exercises. In today’s exercise we look at another checksum algorithm developed by John Fletcher at Lawrence Livermore Labs in the late 1970s.

Fletcher’s original algorithm reads a file one byte at a time and computes a 16-bit checksum. Each byte is added to an accumulating sum, mod 255; to detect transposition errors, each accumulating sum is itself added to a second accumulating sum, mod 255. When the input is exhausted, the second sum is multiplied by 256 and added to the first sum, giving the checksum. Variants of Fletcher’s algorithm read a file two bytes at a time and compute a 32-bit checksum (the modulus is 65535), or read a file four bytes at a time and compute a 64-bit checksum (the modulus is 4294967295).

Your task is to write the three checksum programs described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

4 Responses to “Fletcher’s Checksum”

1. Paul said

In python.

```def readn(fin, n):
s = 0
for ti in fin.read(n):
s = s * 256 + ord(ti)
return s

def fletcher(fin, k):
if  k not in (16, 32, 64):
raise ValueError("Valid choices of k are 16, 32 and 64")
nbytes = k // 16
mod = 2 ** (8 * nbytes) - 1
s = s2 = 0
t = readn(fin, nbytes)
while t:
s += t
s2 += s
t = readn(fin, nbytes)
return s % mod + (mod + 1) * (s2 % mod)
```
2. r. clayton said

In guile scheme.

3. […] I implemented Fletcher’s checksum as an exercise from Programming Praxis. […]