Cksum

October 25, 2011

Here’s our version:

(define cksum
  (let* ((two32 4294967296)
         (crctab (vector #x00000000
           #x04c11db7 #x09823b6e #x0d4326d9 #x130476dc #x17c56b6b
           #x1a864db2 #x1e475005 #x2608edb8 #x22c9f00f #x2f8ad6d6
           #x2b4bcb61 #x350c9b64 #x31cd86d3 #x3c8ea00a #x384fbdbd
           #x4c11db70 #x48d0c6c7 #x4593e01e #x4152fda9 #x5f15adac
           #x5bd4b01b #x569796c2 #x52568b75 #x6a1936c8 #x6ed82b7f
           #x639b0da6 #x675a1011 #x791d4014 #x7ddc5da3 #x709f7b7a
           #x745e66cd #x9823b6e0 #x9ce2ab57 #x91a18d8e #x95609039
           #x8b27c03c #x8fe6dd8b #x82a5fb52 #x8664e6e5 #xbe2b5b58
           #xbaea46ef #xb7a96036 #xb3687d81 #xad2f2d84 #xa9ee3033
           #xa4ad16ea #xa06c0b5d #xd4326d90 #xd0f37027 #xddb056fe
           #xd9714b49 #xc7361b4c #xc3f706fb #xceb42022 #xca753d95
           #xf23a8028 #xf6fb9d9f #xfbb8bb46 #xff79a6f1 #xe13ef6f4
           #xe5ffeb43 #xe8bccd9a #xec7dd02d #x34867077 #x30476dc0
           #x3d044b19 #x39c556ae #x278206ab #x23431b1c #x2e003dc5
           #x2ac12072 #x128e9dcf #x164f8078 #x1b0ca6a1 #x1fcdbb16
           #x018aeb13 #x054bf6a4 #x0808d07d #x0cc9cdca #x7897ab07
           #x7c56b6b0 #x71159069 #x75d48dde #x6b93dddb #x6f52c06c
           #x6211e6b5 #x66d0fb02 #x5e9f46bf #x5a5e5b08 #x571d7dd1
           #x53dc6066 #x4d9b3063 #x495a2dd4 #x44190b0d #x40d816ba
           #xaca5c697 #xa864db20 #xa527fdf9 #xa1e6e04e #xbfa1b04b
           #xbb60adfc #xb6238b25 #xb2e29692 #x8aad2b2f #x8e6c3698
           #x832f1041 #x87ee0df6 #x99a95df3 #x9d684044 #x902b669d
           #x94ea7b2a #xe0b41de7 #xe4750050 #xe9362689 #xedf73b3e
           #xf3b06b3b #xf771768c #xfa325055 #xfef34de2 #xc6bcf05f
           #xc27dede8 #xcf3ecb31 #xcbffd686 #xd5b88683 #xd1799b34
           #xdc3abded #xd8fba05a #x690ce0ee #x6dcdfd59 #x608edb80
           #x644fc637 #x7a089632 #x7ec98b85 #x738aad5c #x774bb0eb
           #x4f040d56 #x4bc510e1 #x46863638 #x42472b8f #x5c007b8a
           #x58c1663d #x558240e4 #x51435d53 #x251d3b9e #x21dc2629
           #x2c9f00f0 #x285e1d47 #x36194d42 #x32d850f5 #x3f9b762c
           #x3b5a6b9b #x0315d626 #x07d4cb91 #x0a97ed48 #x0e56f0ff
           #x1011a0fa #x14d0bd4d #x19939b94 #x1d528623 #xf12f560e
           #xf5ee4bb9 #xf8ad6d60 #xfc6c70d7 #xe22b20d2 #xe6ea3d65
           #xeba91bbc #xef68060b #xd727bbb6 #xd3e6a601 #xdea580d8
           #xda649d6f #xc423cd6a #xc0e2d0dd #xcda1f604 #xc960ebb3
           #xbd3e8d7e #xb9ff90c9 #xb4bcb610 #xb07daba7 #xae3afba2
           #xaafbe615 #xa7b8c0cc #xa379dd7b #x9b3660c6 #x9ff77d71
           #x92b45ba8 #x9675461f #x8832161a #x8cf30bad #x81b02d74
           #x857130c3 #x5d8a9099 #x594b8d2e #x5408abf7 #x50c9b640
           #x4e8ee645 #x4a4ffbf2 #x470cdd2b #x43cdc09c #x7b827d21
           #x7f436096 #x7200464f #x76c15bf8 #x68860bfd #x6c47164a
           #x61043093 #x65c52d24 #x119b4be9 #x155a565e #x18197087
           #x1cd86d30 #x029f3d35 #x065e2082 #x0b1d065b #x0fdc1bec
           #x3793a651 #x3352bbe6 #x3e119d3f #x3ad08088 #x2497d08d
           #x2056cd3a #x2d15ebe3 #x29d4f654 #xc5a92679 #xc1683bce
           #xcc2b1d17 #xc8ea00a0 #xd6ad50a5 #xd26c4d12 #xdf2f6bcb
           #xdbee767c #xe3a1cbc1 #xe760d676 #xea23f0af #xeee2ed18
           #xf0a5bd1d #xf464a0aa #xf9278673 #xfde69bc4 #x89b8fd09
           #x8d79e0be #x803ac667 #x84fbdbd0 #x9abc8bd5 #x9e7d9662
           #x933eb0bb #x97ffad0c #xafb010b1 #xab710d06 #xa6322bdf
           #xa2f33668 #xbcb4666d #xb8757bda #xb5365d03 #xb1f740b4))
         (f (lambda (s c)
              (logxor (modulo (ash s 8) two32)
                      (vector-ref crctab (logxor (ash s -24) c))))))
    (lambda ()
      (let loop ((c (read-char)) (b 0) (s 0))
        (if (not (eof-object? c))
            (loop (read-char) (+ b 1) (f s (char->integer c)))
            (let loop ((n b) (s s))
              (if (positive? n)
                  (loop (ash n -8) (f s (logand n 255)))
                  (values (modulo (lognot s) two32) b))))))))

We use several idioms of Scheme. The crctab vector is outside the function closure, so that space for the vector is allocated only once, at compile time, instead of being re-allocated every time the function is called. The bit operations are non-standard, but common, with names derived from old-style LISP (even before the days of Common Lisp); versions of Scheme starting from R6RS are required to provide the bit operators, though with different names, and our Standard Prelude provides portable versions of the bit operators if you need them. The worst problem is that most Scheme systems use 30-bit integers, reserving 2 bits for type tagging. That means that logical operators don’t truncate at 32-bits like their C counterparts. There are two places in the code where we had to specify (modulo ... two32), which correspond to the places where the logical operators can overflow a 32-bit integer.

The cksum function normally lives within a shell script that loops on command-line filename arguments, but since we showed that shell script in the two previous exercises, we don’t bother to repeat it here. You can see the program, complete with the Chez-specific shell wrapper, at http://programmingpraxis.codepad.org/6FlmcgGC.

About these ads

Pages: 1 2 3

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

%d bloggers like this: