md5.lisp

   1 ;;;; This file implements The MD5 Message-Digest Algorithm, as defined in
   2 ;;;; RFC 1321 by R. Rivest, published April 1992.
   3 ;;;;
   4 ;;;; It was written by Pierre R. Mai, with copious input from the
   5 ;;;; cmucl-help mailing-list hosted at cons.org, in November 2001 and
   6 ;;;; has been placed into the public domain.
   7 ;;;;
   8 ;;;; $Id: md5.lisp,v 1.4 2003/05/06 04:57:43 kevin Exp $
   9 ;;;;
  10 ;;;; While the implementation should work on all conforming Common
  11 ;;;; Lisp implementations, it has only been optimized for CMU CL,
  12 ;;;; where it achieved comparable performance to the standard md5sum
  13 ;;;; utility (within a factor of 1.5 or less on iA32 and UltraSparc
  14 ;;;; hardware).
  15 ;;;;
  16 ;;;; Since the implementation makes heavy use of arithmetic on
  17 ;;;; (unsigned-byte 32) numbers, acceptable performance is likely only
  18 ;;;; on CL implementations that support unboxed arithmetic on such
  19 ;;;; numbers in some form.  For other CL implementations a 16bit
  20 ;;;; implementation of MD5 is probably more suitable.
  21 ;;;;
  22 ;;;; The code implements correct operation for files of unbounded size
  23 ;;;; as is, at the cost of having to do a single generic integer
  24 ;;;; addition for each call to update-md5-state.  If you call
  25 ;;;; update-md5-state frequently with little data, this can pose a
  26 ;;;; performance problem.  If you can live with a size restriction of
  27 ;;;; 512 MB, then you can enable fast fixnum arithmetic by putting
  28 ;;;; :md5-small-length onto *features* prior to compiling this file.
  29 ;;;;
  30 ;;;; Testing code can be compiled by including :md5-testing on
  31 ;;;; *features* prior to compilation.  In that case evaluating
  32 ;;;; (md5::test-rfc1321) will run all the test-cases present in
  33 ;;;; Appendix A.5 of RFC 1321 and report on the results.
  34 ;;;; Evaluating (md5::test-other) will run further test-cases
  35 ;;;; gathered by the author to cover regressions, etc.
  36 ;;;;
  37 ;;;; This software is "as is", and has no warranty of any kind.  The
  38 ;;;; authors assume no responsibility for the consequences of any use
  39 ;;;; of this software.
  40
  41 (defpackage #:md5 (:use #:cl)
  42   (:export
  43    ;; Low-Level types and functions
  44    #:md5-regs #:initial-md5-regs #:md5regs-digest
  45    #:update-md5-block #:fill-block #:fill-block-ub8 #:fill-block-char
  46    ;; Mid-Level types and functions
  47    #:md5-state #:md5-state-p #:make-md5-state
  48    #:update-md5-state #:finalize-md5-state
  49    ;; High-Level functions on sequences, streams and files
  50    #:md5sum-sequence #:md5sum-stream #:md5sum-file))
  51
  52 (in-package #:md5)
  53
  54 #+cmu
  55 (eval-when (:compile-toplevel)
  56   (defparameter *old-expansion-limit* ext:*inline-expansion-limit*)
  57   (setq ext:*inline-expansion-limit* (max ext:*inline-expansion-limit* 1000)))
  58
  59 #+cmu
  60 (eval-when (:compile-toplevel :execute)
  61   (defparameter *old-features* *features*)
  62   (pushnew (c:backend-byte-order c:*target-backend*) *features*))
  63
  64 ;;; Section 2:  Basic Datatypes
  65
  66 (eval-when (:compile-toplevel :load-toplevel :execute)
  67   (deftype ub32 ()
  68     "Corresponds to the 32bit quantity word of the MD5 Spec"
  69     `(unsigned-byte 32)))
  70
  71 (defmacro assemble-ub32 (a b c d)
  72   "Assemble an ub32 value from the given (unsigned-byte 8) values,
  73 where a is the intended low-order byte and d the high-order byte."
  74   `(the ub32 (logior (ash ,d 24) (ash ,c 16) (ash ,b 8) ,a)))
  75
  76 ;;; Section 3.4:  Auxilliary functions
  77
  78 (declaim (inline f g h i)
  79          (ftype (function (ub32 ub32 ub32) ub32) f g h i))
  80
  81 (defun f (x y z)
  82   (declare (type ub32 x y z)
  83            (optimize (speed 3) (safety 0) (space 0) (debug 0)))
  84   #+cmu
  85   (kernel:32bit-logical-or (kernel:32bit-logical-and x y)
  86                            (kernel:32bit-logical-andc1 x z))
  87   #-cmu
  88   (logior (logand x y) (logandc1 x z)))
  89
  90 (defun g (x y z)
  91   (declare (type ub32 x y z)
  92            (optimize (speed 3) (safety 0) (space 0) (debug 0)))
  93   #+cmu
  94   (kernel:32bit-logical-or (kernel:32bit-logical-and x z)
  95                            (kernel:32bit-logical-andc2 y z))
  96   #-cmu
  97   (logior (logand x z) (logandc2 y z)))
  98
  99 (defun h (x y z)
 100   (declare (type ub32 x y z)
 101            (optimize (speed 3) (safety 0) (space 0) (debug 0)))
 102   #+cmu
 103   (kernel:32bit-logical-xor x (kernel:32bit-logical-xor y z))
 104   #-cmu
 105   (logxor x y z))
 106
 107 (defun i (x y z)
 108   (declare (type ub32 x y z)
 109            (optimize (speed 3) (safety 0) (space 0) (debug 0)))
 110   #+cmu
 111   (kernel:32bit-logical-xor y (kernel:32bit-logical-orc2 x z))
 112   #-cmu
 113   (logxor y (logorc2 x z)))
 114
 115 (declaim (inline mod32+)
 116          (ftype (function (ub32 ub32) ub32) mod32+))
 117 (defun mod32+ (a b)
 118   (declare (type ub32 a b) (optimize (speed 3) (safety 0) (space 0) (debug 0)))
 119   (ldb (byte 32 0) (+ a b)))
 120
 121 #+cmu
 122 (define-compiler-macro mod32+ (a b)
 123   `(ext:truly-the ub32 (+ ,a ,b)))
 124
 125 (declaim (inline rol32)
 126          (ftype (function (ub32 (unsigned-byte 5)) ub32) rol32))
 127 (defun rol32 (a s)
 128   (declare (type ub32 a) (type (unsigned-byte 5) s)
 129            (optimize (speed 3) (safety 0) (space 0) (debug 0)))
 130   #+cmu
 131   (kernel:32bit-logical-or #+little-endian (kernel:shift-towards-end a s)
 132                            #+big-endian (kernel:shift-towards-start a s)
 133                            (ash a (- s 32)))
 134   #-cmu
 135   (logior (ldb (byte 32 0) (ash a s)) (ash a (- s 32))))
 136
 137 ;;; Section 3.4:  Table T
 138
 139 (eval-when (:compile-toplevel :load-toplevel :execute)
 140   (defparameter *t* (make-array 64 :element-type 'ub32
 141                                 :initial-contents
 142                                 (loop for i from 1 to 64
 143                                       collect
 144                                       (truncate
 145                                        (* 4294967296
 146                                           (abs (sin (float i 0.0d0)))))))))
 147
 148 ;;; Section 3.4:  Helper Macro for single round definitions
 149
 150 (defmacro with-md5-round ((op block) &rest clauses)
 151   (loop for (a b c d k s i) in clauses
 152         collect
 153         `(setq ,a (mod32+ ,b (rol32 (mod32+ (mod32+ ,a (,op ,b ,c ,d))
 154                                             (mod32+ (aref ,block ,k)
 155                                                     ,(aref *t* (1- i))))
 156                                     ,s)))
 157         into result
 158         finally
 159         (return `(progn ,@result))))
 160
 161 ;;; Section 3.3:  (Initial) MD5 Working Set
 162
 163 (deftype md5-regs ()
 164   "The working state of the MD5 algorithm, which contains the 4 32-bit
 165 registers A, B, C and D."
 166   `(simple-array (unsigned-byte 32) (4)))
 167
 168 (defmacro md5-regs-a (regs)
 169   `(aref ,regs 0))
 170
 171 (defmacro md5-regs-b (regs)
 172   `(aref ,regs 1))
 173
 174 (defmacro md5-regs-c (regs)
 175   `(aref ,regs 2))
 176
 177 (defmacro md5-regs-d (regs)
 178   `(aref ,regs 3))
 179
 180 (defconstant +md5-magic-a+ (assemble-ub32 #x01 #x23 #x45 #x67)
 181   "Initial value of Register A of the MD5 working state.")
 182 (defconstant +md5-magic-b+ (assemble-ub32 #x89 #xab #xcd #xef)
 183   "Initial value of Register B of the MD5 working state.")
 184 (defconstant +md5-magic-c+ (assemble-ub32 #xfe #xdc #xba #x98)
 185   "Initial value of Register C of the MD5 working state.")
 186 (defconstant +md5-magic-d+ (assemble-ub32 #x76 #x54 #x32 #x10)
 187   "Initial value of Register D of the MD5 working state.")
 188
 189 (declaim (inline initial-md5-regs))
 190 (defun initial-md5-regs ()
 191   "Create the initial working state of an MD5 run."
 192   (declare (optimize (speed 3) (safety 0) (space 0) (debug 0)))
 193   (let ((regs (make-array 4 :element-type '(unsigned-byte 32))))
 194     (declare (type md5-regs regs))
 195     (setf (md5-regs-a regs) +md5-magic-a+
 196           (md5-regs-b regs) +md5-magic-b+
 197           (md5-regs-c regs) +md5-magic-c+
 198           (md5-regs-d regs) +md5-magic-d+)
 199     regs))
 200
 201 ;;; Section 3.4:  Operation on 16-Word Blocks
 202
 203 (defun update-md5-block (regs block)
 204   "This is the core part of the MD5 algorithm.  It takes a complete 16
 205 word block of input, and updates the working state in A, B, C, and D
 206 accordingly."
 207   (declare (type md5-regs regs)
 208            (type (simple-array ub32 (16)) block)
 209            (optimize (speed 3) (safety 0) (space 0) (debug 0)))
 210   (let ((a (md5-regs-a regs)) (b (md5-regs-b regs))
 211         (c (md5-regs-c regs)) (d (md5-regs-d regs)))
 212     (declare (type ub32 a b c d))
 213     ;; Round 1
 214     (with-md5-round (f block)
 215       (A B C D  0  7  1)(D A B C  1 12  2)(C D A B  2 17  3)(B C D A  3 22  4)
 216       (A B C D  4  7  5)(D A B C  5 12  6)(C D A B  6 17  7)(B C D A  7 22  8)
 217       (A B C D  8  7  9)(D A B C  9 12 10)(C D A B 10 17 11)(B C D A 11 22 12)
 218       (A B C D 12  7 13)(D A B C 13 12 14)(C D A B 14 17 15)(B C D A 15 22 16))
 219     ;; Round 2
 220     (with-md5-round (g block)
 221       (A B C D  1  5 17)(D A B C  6  9 18)(C D A B 11 14 19)(B C D A  0 20 20)
 222       (A B C D  5  5 21)(D A B C 10  9 22)(C D A B 15 14 23)(B C D A  4 20 24)
 223       (A B C D  9  5 25)(D A B C 14  9 26)(C D A B  3 14 27)(B C D A  8 20 28)
 224       (A B C D 13  5 29)(D A B C  2  9 30)(C D A B  7 14 31)(B C D A 12 20 32))
 225     ;; Round 3
 226     (with-md5-round (h block)
 227       (A B C D  5  4 33)(D A B C  8 11 34)(C D A B 11 16 35)(B C D A 14 23 36)
 228       (A B C D  1  4 37)(D A B C  4 11 38)(C D A B  7 16 39)(B C D A 10 23 40)
 229       (A B C D 13  4 41)(D A B C  0 11 42)(C D A B  3 16 43)(B C D A  6 23 44)
 230       (A B C D  9  4 45)(D A B C 12 11 46)(C D A B 15 16 47)(B C D A  2 23 48))
 231     ;; Round 4
 232     (with-md5-round (i block)
 233       (A B C D  0  6 49)(D A B C  7 10 50)(C D A B 14 15 51)(B C D A  5 21 52)
 234       (A B C D 12  6 53)(D A B C  3 10 54)(C D A B 10 15 55)(B C D A  1 21 56)
 235       (A B C D  8  6 57)(D A B C 15 10 58)(C D A B  6 15 59)(B C D A 13 21 60)
 236       (A B C D  4  6 61)(D A B C 11 10 62)(C D A B  2 15 63)(B C D A  9 21 64))
 237     ;; Update and return
 238     (setf (md5-regs-a regs) (mod32+ (md5-regs-a regs) a)
 239           (md5-regs-b regs) (mod32+ (md5-regs-b regs) b)
 240           (md5-regs-c regs) (mod32+ (md5-regs-c regs) c)
 241           (md5-regs-d regs) (mod32+ (md5-regs-d regs) d))
 242     regs))
 243
 244 ;;; Section 3.4:  Converting 8bit-vectors into 16-Word Blocks
 245
 246 (declaim (inline fill-block fill-block-ub8 fill-block-char))
 247 (defun fill-block (block buffer offset)
 248   "Convert a complete 64 byte input vector segment into the given 16
 249 word MD5 block.  This currently works on (unsigned-byte 8) and
 250 character simple-arrays, via the functions `fill-block-ub8' and
 251 `fill-block-char' respectively."
 252   (declare (type (integer 0 #.(- most-positive-fixnum 64)) offset)
 253            (type (simple-array ub32 (16)) block)
 254            (type (simple-array * (*)) buffer)
 255            (optimize (speed 3) (safety 0) (space 0) (debug 0)))
 256   (etypecase buffer
 257     ((simple-array (unsigned-byte 8) (*))
 258      (fill-block-ub8 block buffer offset))
 259     (simple-string
 260      (fill-block-char block buffer offset))))
 261
 262 (defun fill-block-ub8 (block buffer offset)
 263   "Convert a complete 64 (unsigned-byte 8) input vector segment
 264 starting from offset into the given 16 word MD5 block."
 265   (declare (type (integer 0 #.(- most-positive-fixnum 64)) offset)
 266            (type (simple-array ub32 (16)) block)
 267            (type (simple-array (unsigned-byte 8) (*)) buffer)
 268            (optimize (speed 3) (safety 0) (space 0) (debug 0)))
 269   #+(and :cmu :little-endian)
 270   (kernel:bit-bash-copy
 271    buffer (+ (* vm:vector-data-offset vm:word-bits) (* offset vm:byte-bits))
 272    block (* vm:vector-data-offset vm:word-bits)
 273    (* 64 vm:byte-bits))
 274   #-(and :cmu :little-endian)
 275   (loop for i of-type (integer 0 16) from 0
 276         for j of-type (integer 0 #.most-positive-fixnum)
 277         from offset to (+ offset 63) by 4
 278         do
 279         (setf (aref block i)
 280               (assemble-ub32 (aref buffer j)
 281                              (aref buffer (+ j 1))
 282                              (aref buffer (+ j 2))
 283                              (aref buffer (+ j 3))))))
 284
 285 (defun fill-block-char (block buffer offset)
 286   "Convert a complete 64 character input string segment starting from
 287 offset into the given 16 word MD5 block."
 288   (declare (type (integer 0 #.(- most-positive-fixnum 64)) offset)
 289            (type (simple-array ub32 (16)) block)
 290            (type simple-string buffer)
 291            (optimize (speed 3) (safety 0) (space 0) (debug 0)))
 292   #+(and :cmu :little-endian)
 293   (kernel:bit-bash-copy
 294    buffer (+ (* vm:vector-data-offset vm:word-bits) (* offset vm:byte-bits))
 295    block (* vm:vector-data-offset vm:word-bits)
 296    (* 64 vm:byte-bits))
 297   #-(and :cmu :little-endian)
 298   (loop for i of-type (integer 0 16) from 0
 299         for j of-type (integer 0 #.most-positive-fixnum)
 300         from offset to (+ offset 63) by 4
 301         do
 302         (setf (aref block i)
 303               (assemble-ub32 (char-code (schar buffer j))
 304                              (char-code (schar buffer (+ j 1)))
 305                              (char-code (schar buffer (+ j 2)))
 306                              (char-code (schar buffer (+ j 3)))))))
 307
 308 ;;; Section 3.5:  Message Digest Output
 309
 310 (declaim (inline md5regs-digest))
 311 (defun md5regs-digest (regs)
 312   "Create the final 16 byte message-digest from the MD5 working state
 313 in regs.  Returns a (simple-array (unsigned-byte 8) (16))."
 314   (declare (optimize (speed 3) (safety 0) (space 0) (debug 0))
 315            (type md5-regs regs))
 316   (let ((result (make-array 16 :element-type '(unsigned-byte 8))))
 317     (declare (type (simple-array (unsigned-byte 8) (16)) result))
 318     (macrolet ((frob (reg offset)
 319                  (let ((var (gensym)))
 320                    `(let ((,var ,reg))
 321                       (declare (type ub32 ,var))
 322                       (setf
 323                        (aref result ,offset) (ldb (byte 8 0) ,var)
 324                        (aref result ,(+ offset 1)) (ldb (byte 8 8) ,var)
 325                        (aref result ,(+ offset 2)) (ldb (byte 8 16) ,var)
 326                        (aref result ,(+ offset 3)) (ldb (byte 8 24) ,var))))))
 327       (frob (md5-regs-a regs) 0)
 328       (frob (md5-regs-b regs) 4)
 329       (frob (md5-regs-c regs) 8)
 330       (frob (md5-regs-d regs) 12))
 331     result))
 332
 333 ;;; Mid-Level Drivers
 334
 335 (defstruct (md5-state
 336              (:constructor make-md5-state ())
 337              (:copier))
 338   (regs (initial-md5-regs) :type md5-regs :read-only t)
 339   (amount 0 :type
 340           #-md5-small-length (integer 0 *)
 341           #+md5-small-length (unsigned-byte 29))
 342   (block (make-array 16 :element-type '(unsigned-byte 32)) :read-only t
 343          :type (simple-array (unsigned-byte 32) (16)))
 344   (buffer (make-array 64 :element-type '(unsigned-byte 8)) :read-only t
 345          :type (simple-array (unsigned-byte 8) (64)))
 346   (buffer-index 0 :type (integer 0 63))
 347   (finalized-p nil))
 348
 349 (declaim (inline copy-to-buffer))
 350 (defun copy-to-buffer (from from-offset count buffer buffer-offset)
 351   "Copy a partial segment from input vector from starting at
 352 from-offset and copying count elements into the 64 byte buffer
 353 starting at buffer-offset."
 354   (declare (optimize (speed 3) (safety 0) (space 0) (debug 0))
 355            (type (unsigned-byte 29) from-offset)
 356            (type (integer 0 63) count buffer-offset)
 357            (type (simple-array * (*)) from)
 358            (type (simple-array (unsigned-byte 8) (64)) buffer))
 359   #+cmu
 360   (kernel:bit-bash-copy
 361    from (+ (* vm:vector-data-offset vm:word-bits) (* from-offset vm:byte-bits))
 362    buffer (+ (* vm:vector-data-offset vm:word-bits)
 363              (* buffer-offset vm:byte-bits))
 364    (* count vm:byte-bits))
 365   #-cmu
 366   (etypecase from
 367     (simple-string
 368      (loop for buffer-index of-type (integer 0 64) from buffer-offset
 369            for from-index of-type fixnum from from-offset
 370            below (+ from-offset count)
 371            do
 372            (setf (aref buffer buffer-index)
 373                  (char-code (schar (the simple-string from) from-index)))))
 374     ((simple-array (unsigned-byte 8) (*))
 375      (loop for buffer-index of-type (integer 0 64) from buffer-offset
 376            for from-index of-type fixnum from from-offset
 377            below (+ from-offset count)
 378            do
 379            (setf (aref buffer buffer-index)
 380                  (aref (the (simple-array (unsigned-byte 8) (*)) from)
 381                        from-index))))))
 382
 383 (defun update-md5-state (state sequence &key (start 0) (end (length sequence)))
 384   "Update the given md5-state from sequence, which is either a
 385 simple-string or a simple-array with element-type (unsigned-byte 8),
 386 bounded by start and end, which must be numeric bounding-indices."
 387   (declare (type md5-state state)
 388            (type (simple-array * (*)) sequence)
 389            (type fixnum start end)
 390            (optimize (speed 3) #+cmu (safety 0) (space 0) (debug 0))
 391            #+cmu
 392            (ext:optimize-interface (safety 1) (debug 1)))
 393   (let ((regs (md5-state-regs state))
 394         (block (md5-state-block state))
 395         (buffer (md5-state-buffer state))
 396         (buffer-index (md5-state-buffer-index state))
 397         (length (- end start)))
 398     (declare (type md5-regs regs) (type fixnum length)
 399              (type (integer 0 63) buffer-index)
 400              (type (simple-array (unsigned-byte 32) (16)) block)
 401              (type (simple-array (unsigned-byte 8) (64)) buffer))
 402     ;; Handle old rest
 403     (unless (zerop buffer-index)
 404       (let ((amount (min (- 64 buffer-index) length)))
 405         (declare (type (integer 0 63) amount))
 406         (copy-to-buffer sequence start amount buffer buffer-index)
 407         (setq start (the fixnum (+ start amount)))
 408         (when (>= start end)
 409           (setf (md5-state-buffer-index state) (+ buffer-index amount))
 410           (return-from update-md5-state state)))
 411       (fill-block-ub8 block buffer 0)
 412       (update-md5-block regs block))
 413     ;; Handle main-part and new-rest
 414     (etypecase sequence
 415       ((simple-array (unsigned-byte 8) (*))
 416        (locally
 417            (declare (type (simple-array (unsigned-byte 8) (*)) sequence))
 418          (loop for offset of-type (unsigned-byte 29) from start below end by 64
 419                until (< (- end offset) 64)
 420                do
 421                (fill-block-ub8 block sequence offset)
 422                (update-md5-block regs block)
 423                finally
 424                (let ((amount (- end offset)))
 425                  (unless (zerop amount)
 426                    (copy-to-buffer sequence offset amount buffer 0))
 427                  (setf (md5-state-buffer-index state) amount)))))
 428       (simple-string
 429        (locally
 430            (declare (type simple-string sequence))
 431          (loop for offset of-type (unsigned-byte 29) from start below end by 64
 432                until (< (- end offset) 64)
 433                do
 434                (fill-block-char block sequence offset)
 435                (update-md5-block regs block)
 436                finally
 437                (let ((amount (- end offset)))
 438                  (unless (zerop amount)
 439                    (copy-to-buffer sequence offset amount buffer 0))
 440                  (setf (md5-state-buffer-index state) amount))))))
 441     (setf (md5-state-amount state)
 442           #-md5-small-length (+ (md5-state-amount state) length)
 443           #+md5-small-length (the (unsigned-byte 29)
 444                                (+ (md5-state-amount state) length)))
 445     state))
 446
 447 (defun finalize-md5-state (state)
 448   "If the given md5-state has not already been finalized, finalize it,
 449 by processing any remaining input in its buffer, with suitable padding
 450 and appended bit-length, as specified by the MD5 standard.
 451
 452 The resulting MD5 message-digest is returned as an array of sixteen
 453 (unsigned-byte 8) values.  Calling `update-md5-state' after a call to
 454 `finalize-md5-state' results in unspecified behaviour."
 455   (declare (type md5-state state)
 456            (optimize (speed 3) #+cmu (safety 0) (space 0) (debug 0))
 457            #+cmu
 458            (ext:optimize-interface (safety 1) (debug 1)))
 459   (or (md5-state-finalized-p state)
 460       (let ((regs (md5-state-regs state))
 461             (block (md5-state-block state))
 462             (buffer (md5-state-buffer state))
 463             (buffer-index (md5-state-buffer-index state))
 464             (total-length (* 8 (md5-state-amount state))))
 465         (declare (type md5-regs regs)
 466                  (type (integer 0 63) buffer-index)
 467                  (type (simple-array ub32 (16)) block)
 468                  (type (simple-array (unsigned-byte 8) (*)) buffer))
 469         ;; Add mandatory bit 1 padding
 470         (setf (aref buffer buffer-index) #x80)
 471         ;; Fill with 0 bit padding
 472         (loop for index of-type (integer 0 64)
 473               from (1+ buffer-index) below 64
 474               do (setf (aref buffer index) #x00))
 475         (fill-block-ub8 block buffer 0)
 476         ;; Flush block first if length wouldn't fit
 477         (when (>= buffer-index 56)
 478           (update-md5-block regs block)
 479           ;; Create new fully 0 padded block
 480           (loop for index of-type (integer 0 16) from 0 below 16
 481                 do (setf (aref block index) #x00000000)))
 482         ;; Add 64bit message bit length
 483         (setf (aref block 14) (ldb (byte 32 0) total-length))
 484         #-md5-small-length
 485         (setf (aref block 15) (ldb (byte 32 32) total-length))
 486         ;; Flush last block
 487         (update-md5-block regs block)
 488         ;; Done, remember digest for later calls
 489         (setf (md5-state-finalized-p state)
 490               (md5regs-digest regs)))))
 491
 492 ;;; High-Level Drivers
 493
 494 (defun md5sum-sequence (sequence &key (start 0) end)
 495   "Calculate the MD5 message-digest of data in sequence.  On CMU CL
 496 this works for all sequences whose element-type is supported by the
 497 underlying MD5 routines, on other implementations it only works for 1d
 498 simple-arrays with such element types."
 499   (declare (optimize (speed 3) (space 0) (debug 0))
 500            (type vector sequence) (type fixnum start))
 501   (let ((state (make-md5-state)))
 502     (declare (type md5-state state))
 503     #+cmu
 504     (lisp::with-array-data ((data sequence) (real-start start) (real-end end))
 505       (update-md5-state state data :start real-start :end real-end))
 506     #-cmu
 507     (let ((real-end (or end (length sequence))))
 508       (declare (type fixnum real-end))
 509       (update-md5-state state sequence :start start :end real-end))
 510     (finalize-md5-state state)))
 511
 512 (defconstant +buffer-size+ (* 128 1024)
 513   "Size of internal buffer to use for md5sum-stream and md5sum-file
 514 operations.  This should be a multiple of 64, the MD5 block size.")
 515
 516 (deftype buffer-index () `(integer 0 ,+buffer-size+))
 517
 518 (defun md5sum-stream (stream)
 519   "Calculate an MD5 message-digest of the contents of stream.  Its
 520 element-type has to be either (unsigned-byte 8) or character."
 521   (declare (optimize (speed 3) (space 0) (debug 0)))
 522   (let ((state (make-md5-state)))
 523     (declare (type md5-state state))
 524     (cond
 525       ((equal (stream-element-type stream) '(unsigned-byte 8))
 526        (let ((buffer (make-array +buffer-size+
 527                                  :element-type '(unsigned-byte 8))))
 528          (declare (type (simple-array (unsigned-byte 8) (#.+buffer-size+))
 529                         buffer))
 530          (loop for bytes of-type buffer-index = (read-sequence buffer stream)
 531                do (update-md5-state state buffer :end bytes)
 532                until (< bytes +buffer-size+)
 533                finally
 534                (return (finalize-md5-state state)))))
 535       ((equal (stream-element-type stream) 'character)
 536        (let ((buffer (make-string +buffer-size+)))
 537          (declare (type (simple-string #.+buffer-size+) buffer))
 538          (loop for bytes of-type buffer-index = (read-sequence buffer stream)
 539                do (update-md5-state state buffer :end bytes)
 540                until (< bytes +buffer-size+)
 541                finally
 542                (return (finalize-md5-state state)))))
 543       (t
 544        (error "Unsupported stream element-type ~S for stream ~S."
 545               (stream-element-type stream) stream)))))
 546
 547 (defun md5sum-file (pathname)
 548   "Calculate the MD5 message-digest of the file specified by pathname."
 549   (declare (optimize (speed 3) (space 0) (debug 0)))
 550   (with-open-file (stream pathname :element-type '(unsigned-byte 8))
 551     (md5sum-stream stream)))
 552
 553 #+md5-testing
 554 (defconstant +rfc1321-testsuite+
 555   '(("" . "d41d8cd98f00b204e9800998ecf8427e")
 556     ("a" ."0cc175b9c0f1b6a831c399e269772661")
 557     ("abc" . "900150983cd24fb0d6963f7d28e17f72")
 558     ("message digest" . "f96b697d7cb7938d525a2f31aaf161d0")
 559     ("abcdefghijklmnopqrstuvwxyz" . "c3fcd3d76192e4007dfb496cca67e13b")
 560     ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" .
 561      "d174ab98d277d9f5a5611c2c9f419d9f")
 562     ("12345678901234567890123456789012345678901234567890123456789012345678901234567890" .
 563      "57edf4a22be3c955ac49da2e2107b67a"))
 564   "AList of test input strings and stringified message-digests
 565 according to the test suite in Appendix A.5 of RFC 1321")
 566
 567 #+md5-testing
 568 (defconstant +other-testsuite+
 569   '(;; From padding bug report by Edi Weitz
 570     ("1631901HERR BUCHHEISTERCITROEN NORD1043360796beckenbauer" .
 571      "d734945e5930bb28859ccd13c830358b")
 572     ;; Test padding for strings from 0 to 69*8 bits in size.
 573     ("" . "d41d8cd98f00b204e9800998ecf8427e")
 574     ("a" . "0cc175b9c0f1b6a831c399e269772661")
 575     ("aa" . "4124bc0a9335c27f086f24ba207a4912")
 576     ("aaa" . "47bce5c74f589f4867dbd57e9ca9f808")
 577     ("aaaa" . "74b87337454200d4d33f80c4663dc5e5")
 578     ("aaaaa" . "594f803b380a41396ed63dca39503542")
 579     ("aaaaaa" . "0b4e7a0e5fe84ad35fb5f95b9ceeac79")
 580     ("aaaaaaa" . "5d793fc5b00a2348c3fb9ab59e5ca98a")
 581     ("aaaaaaaa" . "3dbe00a167653a1aaee01d93e77e730e")
 582     ("aaaaaaaaa" . "552e6a97297c53e592208cf97fbb3b60")
 583     ("aaaaaaaaaa" . "e09c80c42fda55f9d992e59ca6b3307d")
 584     ("aaaaaaaaaaa" . "d57f21e6a273781dbf8b7657940f3b03")
 585     ("aaaaaaaaaaaa" . "45e4812014d83dde5666ebdf5a8ed1ed")
 586     ("aaaaaaaaaaaaa" . "c162de19c4c3731ca3428769d0cd593d")
 587     ("aaaaaaaaaaaaaa" . "451599a5f9afa91a0f2097040a796f3d")
 588     ("aaaaaaaaaaaaaaa" . "12f9cf6998d52dbe773b06f848bb3608")
 589     ("aaaaaaaaaaaaaaaa" . "23ca472302f49b3ea5592b146a312da0")
 590     ("aaaaaaaaaaaaaaaaa" . "88e42e96cc71151b6e1938a1699b0a27")
 591     ("aaaaaaaaaaaaaaaaaa" . "2c60c24e7087e18e45055a33f9a5be91")
 592     ("aaaaaaaaaaaaaaaaaaa" . "639d76897485360b3147e66e0a8a3d6c")
 593     ("aaaaaaaaaaaaaaaaaaaa" . "22d42eb002cefa81e9ad604ea57bc01d")
 594     ("aaaaaaaaaaaaaaaaaaaaa" . "bd049f221af82804c5a2826809337c9b")
 595     ("aaaaaaaaaaaaaaaaaaaaaa" . "ff49cfac3968dbce26ebe7d4823e58bd")
 596     ("aaaaaaaaaaaaaaaaaaaaaaa" . "d95dbfee231e34cccb8c04444412ed7d")
 597     ("aaaaaaaaaaaaaaaaaaaaaaaa" . "40edae4bad0e5bf6d6c2dc5615a86afb")
 598     ("aaaaaaaaaaaaaaaaaaaaaaaaa" . "a5a8bfa3962f49330227955e24a2e67c")
 599     ("aaaaaaaaaaaaaaaaaaaaaaaaaa" . "ae791f19bdf77357ff10bb6b0e97e121")
 600     ("aaaaaaaaaaaaaaaaaaaaaaaaaaa" . "aaab9c59a88bf0bdfcb170546c5459d6")
 601     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaa" . "b0f0545856af1a340acdedce23c54b97")
 602     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaa" . "f7ce3d7d44f3342107d884bfa90c966a")
 603     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" . "59e794d45697b360e18ba972bada0123")
 604     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" . "3b0845db57c200be6052466f87b2198a")
 605     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" . "5eca9bd3eb07c006cd43ae48dfde7fd3")
 606     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" . "b4f13cb081e412f44e99742cb128a1a5")
 607     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" . "4c660346451b8cf91ef50f4634458d41")
 608     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 609      "11db24dc3f6c2145701db08625dd6d76")
 610     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 611      "80dad3aad8584778352c68ab06250327")
 612     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 613      "1227fe415e79db47285cb2689c93963f")
 614     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 615      "8e084f489f1bdf08c39f98ff6447ce6d")
 616     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 617      "08b2f2b0864bac1ba1585043362cbec9")
 618     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 619      "4697843037d962f62a5a429e611e0f5f")
 620     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 621      "10c4da18575c092b486f8ab96c01c02f")
 622     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 623      "af205d729450b663f48b11d839a1c8df")
 624     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 625      "0d3f91798fac6ee279ec2485b25f1124")
 626     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 627      "4c3c7c067634daec9716a80ea886d123")
 628     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 629      "d1e358e6e3b707282cdd06e919f7e08c")
 630     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 631      "8c6ded4f0af86e0a7e301f8a716c4363")
 632     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 633      "4c2d8bcb02d982d7cb77f649c0a2dea8")
 634     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 635      "bdb662f765cd310f2a547cab1cfecef6")
 636     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 637      "08ff5f7301d30200ab89169f6afdb7af")
 638     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 639      "6eb6a030bcce166534b95bc2ab45d9cf")
 640     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 641      "1bb77918e5695c944be02c16ae29b25e")
 642     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 643      "b6fe77c19f0f0f4946c761d62585bfea")
 644     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 645      "e9e7e260dce84ffa6e0e7eb5fd9d37fc")
 646     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 647      "eced9e0b81ef2bba605cbc5e2e76a1d0")
 648     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 649      "ef1772b6dff9a122358552954ad0df65")
 650     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 651      "3b0c8ac703f828b04c6c197006d17218")
 652     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 653      "652b906d60af96844ebd21b674f35e93")
 654     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 655      "dc2f2f2462a0d72358b2f99389458606")
 656     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 657      "762fc2665994b217c52c3c2eb7d9f406")
 658     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 659      "cc7ed669cf88f201c3297c6a91e1d18d")
 660     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 661      "cced11f7bbbffea2f718903216643648")
 662     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 663      "24612f0ce2c9d2cf2b022ef1e027a54f")
 664     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 665      "b06521f39153d618550606be297466d5")
 666     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 667      "014842d480b571495a4a0363793f7367")
 668     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 669      "c743a45e0d2e6a95cb859adae0248435")
 670     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 671      "def5d97e01e1219fb2fc8da6c4d6ba2f")
 672     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 673      "92cb737f8687ccb93022fdb411a77cca")
 674     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 675      "a0d1395c7fb36247bfe2d49376d9d133")
 676     ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" .
 677      "ab75504250558b788f99d1ebd219abf2"))
 678   "AList of test input strings and stringified message-digests
 679 according to my additional test suite")
 680
 681 #+md5-testing
 682 (defun test-with-testsuite (testsuite)
 683   (loop for count from 1
 684         for (source . md5-string) in testsuite
 685         for md5-digest = (md5sum-sequence source)
 686         for md5-result-string = (format nil "~(~{~2,'0X~}~)"
 687                                         (map 'list #'identity md5-digest))
 688         do
 689         (format
 690          *trace-output*
 691          "~2&Test-Case ~D:~%  Input: ~S~%  Required: ~A~%  Returned: ~A~%"
 692          count source md5-string md5-result-string)
 693         when (string= md5-string md5-result-string)
 694         do (format *trace-output* "  OK~%")
 695         else
 696         count 1 into failed
 697         and do (format *trace-output* "  FAILED~%")
 698         finally
 699         (format *trace-output*
 700                 "~2&~[All ~D test cases succeeded~:;~:*~D of ~D test cases failed~].~%"
 701                 failed (1- count))
 702         (return (zerop failed))))
 703
 704 #+md5-testing
 705 (defun test-rfc1321 ()
 706   (test-with-testsuite +rfc1321-testsuite+))
 707
 708 #+md5-testing
 709 (defun test-other ()
 710   (test-with-testsuite +other-testsuite+))
 711
 712 #+cmu
 713 (eval-when (:compile-toplevel :execute)
 714   (setq *features* *old-features*))
 715
 716 #+cmu
 717 (eval-when (:compile-toplevel)
 718   (setq ext:*inline-expansion-limit* *old-expansion-limit*))