Re: Checksum (noob)

Bill Atkins wrote:
Does the following code do what you want:

(defun checksum (list)
(mod (reduce #'+ list) 256))

If you're going to use this code to find checksums of larger files by
adding them up byte by byte modulo 256, that could be disastrous. You
would add up all the bytes and *then* pass the gigantic bignum result
to MOD.

Here's a function which avoids the problem in your (clearer) code:

(defun checksum (list)
(reduce #'(lambda (a b) (mod (+ a b) 256)) list))

And if you want to make it orders of magnitude faster by limiting it to
byte-sized integers:

(defun checksum (list) ; Just for fun
(declare (optimize (speed 3) (safety 0) (debug 1)))
(let ((accum 0))
(declare (type (integer 0 255) accum))
(loop for x of-type (integer 0 255) in list
do (setf accum (mod (+ accum x) 256)))
accum))

This loop-and-accumulator approach doesn't look nearly as pretty, but
it's probably closer to what you'd use in actual applications for doing
large checksums on files. If you want to find a checksum of a 300 MB
file, you don't want to read the whole thing into memory in the form of
a linked list and pass it to a checksum function; you want to read it
in a few kilobytes at a time in buffers and update your checksum for
every new chunk of the file that you read in. Again, just for fun,
here's the fastest code I could make to compute the checksum of a file:

(defun checksum-file (pathname)
(declare (optimize (speed 3) (safety 0) (debug 1)))
(with-open-file (file pathname :element-type '(unsigned-byte 8))
(let ((buffer (make-array '(2048) :element-type '(unsigned-byte
8)))
(accum 0))
(declare (type (simple-array (unsigned-byte 8) (2048)) buffer)
(type (unsigned-byte 8) accum))
(loop for bytes-read = (read-sequence buffer file)
while (< 0 bytes-read)
do (loop for i below bytes-read
do (setf accum (mod (+ accum (aref buffer i)) 256))))
accum)))

This runs several orders of magnitude faster than the naive code would.

-Peter

.

Relevant Pages

  • How the Automatic Proofreader Works
    ... Automatic Proofreader", which was used as a checksum program for BASIC ... Gazette disk images to create the listings without having to go through ... This multiplication is done via successive addition in a loop. ...
    (comp.sys.cbm)
  • Re: How the Automatic Proofreader Works
    ... Automatic Proofreader", which was used as a checksum program for BASIC ... Gazette disk images to create the listings without having to go through ... This multiplication is done via successive addition in a loop. ...
    (comp.sys.cbm)