Fletcher’s Checksum

November 22, 2013

We begin with a function to read up to n characters from the current input and return the base-256 number that they represent; this is similar to the undigits function from the Standard Prelude:

(define (readc n)
  (if (eof-object? (peek-char)) -1
    (let loop ((k n) (v 0))
      (if (or (eof-object? (peek-char)) (zero? k)) v
        (loop (- k 1) (+ (* v 256) (char->integer (read-char))))))))

Then we write a single function fletcher that reads the current input and returns the checksum defined by its argument; chars is the number of characters to read at each step, base is the base of the checksums, and mod is the modulus, which is one less than the base:

(define (fletcher k) ; k in {16, 32, 64}
  (let* ((chars (/ k 16))
         (base (expt 2 (/ k 2)))
         (mod (- base 1)))
    (let loop ((i 0) (c 0) (v (readc chars)))
      (if (negative? v)
          (+ (* c base) i)
          (let* ((i (modulo (+ i v) mod))
                 (c (modulo (+ c i) mod)))
            (loop i c (readc chars)))))))

Here are some examples:

> (with-input-from-string "abcde"
(lambda () (fletcher 16)))
51440
> (with-input-from-string "abcde"
(lambda () (fletcher 32)))
3948201259
> (with-input-from-string "abcde"
(lambda () (fletcher 64)))
14034561336514601929

The program is collected at http://programmingpraxis.codepad.org/ZErlGDad, but you can’t run it because codepad doesn’t provide string ports.

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 643 other followers

%d bloggers like this: