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. […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 613 other followers

%d bloggers like this: