Debian Codegraph @

tests/inputs/md5.rkt

raw
1 #lang racket/base
2
3 (provide md5)
4
5 ;;; Copyright (c) 2005-2014, PLT Design Inc.
6 ;;; Copyright (c) 2002, Jens Axel Soegaard
7 ;;;
8 ;;; Distributed under the same terms as Racket, by permission.
9 ;;;
10 ;;; md5.scm -- Jens Axel Soegaard, 16 oct 2002
11
12 ;;; Summary
13 ;; This is an implementation of the md5 message-digest algorithm in R5RS
14 ;; Scheme. The algorithm takes an arbitrary byte-string or an input port, and
15 ;; returns a 128-bit "fingerprint" byte string. The algorithm was invented by
16 ;; Ron Rivest, RSA Security, INC. Reference: RFC 1321,
17 ;; <http://www.faqs.org/rfcs/rfc1321.html>
18
19 ;;; History
20 ;; 2002-10-14 /jas
21 ;; - Bored. Initial attempt. Done. Well, except for faulty output.
22 ;; 2002-10-15 /jas
23 ;; - It works at last
24 ;; 2002-10-16 /jas
25 ;; - Added R5RS support
26 ;; 2003-02-16 / lth
27 ;; - Removed let-values implementation because Larceny has it already
28 ;; - Implemented Larceny versions of many bit primitives (note, 0.52 or later
29 ;; required due to bignum bug)
30 ;; - Removed most 'personal idiosyncrasies' to give the compiler a fair chance
31 ;; to inline primitives and improve performance some. Performance in the
32 ;; interpreter is still really quite awful.
33 ;; - Wrapped entire procedure in a big LET to protect the namespace
34 ;; - Some cleanup of repeated computations
35 ;; - Moved test code to separate file
36 ;; 2003-02-17 / lth
37 ;; - Removed some of the indirection, for a 30% speedup in Larceny's
38 ;; interpreter. Running in the interpreter on my Dell Inspiron 4000 I get a
39 ;; fingerprint of "Lib/Common/bignums-be.sch" in about 63ms, which is slow
40 ;; but adequate. (The compiled version is not much faster -- most time is
41 ;; spent in bignum manipulation, which is compiled in either case. To do
42 ;; this well we must either operate on the bignum representation or redo the
43 ;; algorithm to use fixnums only.)
44 ;; 2003-12-01 / lth
45 ;; - Reimplemented word arithmetic to use two 16-bit fixnums boxed in a cons
46 ;; cell. In Petit Larceny's interpreter this gives a speedup of a factor of
47 ;; almost eight, and in addition this change translates well to other Scheme
48 ;; systems that support bit operations on fixnums. Only 17-bit (signed)
49 ;; fixnums are required.
50 ;; 2003-12-23 / jas
51 ;; - Trivial port to PLT. Rewrote the word macro to syntax-rules. Larceny
52 ;; primitives written as syntax-rules macros exanding to their PLT name.
53 ;; 2005-05-05 / Greg Pettyjohn
54 ;; - It was failing for strings of length 56 bytes i.e. when the length in bits
55 ;; was congruent 448 modulo 512. Changed step 1 to fix this. According to
56 ;; RFC 1321, the message should still be padded in this case.
57 ;; 2005-12-23 / Jepri
58 ;; - Mucked around with the insides to get it to read from a port
59 ;; - Now it accepts a port or a string as input
60 ;; - Doesn't explode when handed large strings anymore
61 ;; - Now much slower
62 ;; 2006-10-02 / Matthew
63 ;; - Cleaned up a little
64 ;; - Despite comment above, it seems consistently faster
65 ;; 2006-05-11 / Eli
66 ;; - Cleaned up a lot, removed Larceny-isms
67 ;; - Heavy optimization: not consing anything throughout the loop
68 ;; 2007-09-17 / Eli
69 ;; - making raw output possible
70 ;; 2009-12-20 / Eli
71 ;; - `mzscheme' -> `scheme/base'
72 ;; - moved from mzlib/md5 to file/md5
73 ;; - made it work on strings again
74
75 (require (for-syntax racket/base))
76
77 ;;; Word arithmetic (32 bit)
78 ;; Terminology
79 ;; word: 32 bit unsigned integer
80 ;; byte: 8 bit unsigned integer
81
82 ;; Words are represented as a cons where the car holds the high 16 bits and the
83 ;; cdr holds the low 16 bits. Most good Scheme systems will have fixnums that
84 ;; hold at least 16 bits as well as fast allocation, so this has a fair chance
85 ;; at beating bignums for performance.
86
87 ;; (word c) turns into a quoted pair '(hi . lo) if c is a literal number. can
88 ;; create a new word, compute one at compile-time etc
89 (define-syntax (word stx)
90 (syntax-case stx ()
91 ;; normal version (checks, allocates)
92 [(word #:new c)
93 #'(let ([n c])
94 (if (<= 0 n 4294967296)
95 (mcons (quotient n 65536) (remainder n 65536))
96 (error 'word "out of range: ~e" n)))]
97 ;; use when the number is known to be in range (allocates, no check)
98 [(word #:new+safe c)
99 #'(let ([n c]) (mcons (quotient n 65536) (remainder n 65536)))]
100 ;; default form: compute at compile-time if possible
101 [(word c)
102 (let ([n (syntax-e #'c)])
103 (if (integer? n)
104 (if (<= 0 n 4294967295)
105 (syntax-local-lift-expression
106 #`(mcons #,(quotient n 65536) #,(remainder n 65536)))
107 (raise-syntax-error #f "constant number out of range" stx))
108 #'(word #:new c)))]))
109
110 ;; destructive operations to save on consing
111
112 ;; destructive cons
113 (define (cons! p x y)
114 (set-mcar! p x)
115 (set-mcdr! p y))
116
117 ;; a := b
118 (define (word=! a b)
119 (cons! a (mcar b) (mcdr b)))
120
121 ;; a := a + b
122 (define (word+=! a b)
123 (let ([t1 (+ (mcar a) (mcar b))]
124 [t2 (+ (mcdr a) (mcdr b))])
125 (cons! a
126 (bitwise-and (+ t1 (arithmetic-shift t2 -16)) 65535)
127 (bitwise-and t2 65535))))
128
129 (define word<<<!
130 (let* ([masks '#(#x0 #x1 #x3 #x7 #xF #x1F #x3F #x7F #xFF #x1FF #x3FF #x7FF
131 #xFFF #x1FFF #x3FFF #x7FFF #xFFFF)])
132 (lambda (a s)
133 (let-values ([(hi lo s)
134 (cond [(< s 16) (values (mcar a) (mcdr a) s)]
135 [(< s 32) (values (mcdr a) (mcar a) (- s 16))]
136 [else (error 'word<<< "shift out of range: ~e" s)])])
137 (cons!
138 a
139 (bitwise-ior
140 (arithmetic-shift (bitwise-and hi (vector-ref masks (- 16 s))) s)
141 (bitwise-and (arithmetic-shift lo (- s 16))
142 (vector-ref masks s)))
143 (bitwise-ior
144 (arithmetic-shift (bitwise-and lo (vector-ref masks (- 16 s))) s)
145 (bitwise-and (arithmetic-shift hi (- s 16))
146 (vector-ref masks s))))))))
147
148 ;; Bytes and words
149 ;; The least significant byte of a word is the first
150
151 ;; Converts a byte string to words, writes the result into `result'
152 ;; bytes->word-vector! : vector byte-string -> void
153 (define (bytes->word-vector! result l-raw)
154 ;; assumption: always getting a byte-string with 64 places
155 ;; (unless (eq? 64 (bytes-length l-raw))
156 ;; (error 'bytes->word-vector! "something bad happened"))
157 (let loop ([n 15])
158 (when (<= 0 n)
159 (let ([m (arithmetic-shift n 2)])
160 (cons! (vector-ref result n)
161 (+ (bytes-ref l-raw (+ 2 m))
162 (arithmetic-shift (bytes-ref l-raw (+ 3 m)) 8))
163 (+ (bytes-ref l-raw m)
164 (arithmetic-shift (bytes-ref l-raw (+ 1 m)) 8))))
165 (loop (sub1 n)))))
166
167 (define empty-port (open-input-bytes #""))
168
169 ;; List Helper
170 ;; read-block! : a-port done-n (vector word) -> (values vector a-port done-n)
171 ;; reads 512 bytes from the port, writes them into the `result' vector of 16
172 ;; 32-bit words when the port is exhausted it returns #f for the port and the
173 ;; last few bytes padded
174 (define (read-block! a-port done result)
175 (define-syntax write-words!
176 (syntax-rules ()
177 [(_ done buf) (bytes->word-vector! result (step2 (* 8 done) buf))]))
178 (let ([l-raw (read-bytes 512/8 a-port)])
179 (cond
180 ;; File size was a multiple of 512 bits, or we're doing one more round to
181 ;; add the correct padding from the short case
182 [(eof-object? l-raw)
183 (write-words! done
184 (if (zero? (modulo done 512/8))
185 ;; The file is a multiple of 512 or was 0, so there hasn't been a
186 ;; chance to add the 1-bit pad, so we need to do a full pad
187 (step1 #"")
188 ;; We only enter this block when the previous block didn't have
189 ;; enough room to fit the 64-bit file length, so we just add 448
190 ;; bits of zeros and then the 64-bit file length (step2)
191 (make-bytes 448/8 0)))
192 (values #f done)]
193 ;; We read exactly 512 bits, the algorithm proceeds as usual
194 [(eq? (bytes-length l-raw) 512/8)
195 (bytes->word-vector! result l-raw)
196 (values a-port (+ done (bytes-length l-raw)))]
197 ;; We read less than 512 bits, so the file has ended.
198 [else
199 (let ([done (+ done (bytes-length l-raw))])
200 (write-words! done (step1 l-raw))
201 (values
202 (if (> (* 8 (bytes-length l-raw)) 446)
203 ;; However, we don't have enough room to add the correct trailer,
204 ;; so we add what we can, then go for one more round which will
205 ;; automatically fall into the (eof-object? case)
206 empty-port
207 ;; Returning a longer vector than we should, luckily it doesn't
208 ;; matter. We read less than 512 bits and there is enough room for
209 ;; the correct trailer. Add trailer and bail
210 #f)
211 done))])))
212
213 ;; MD5
214 ;; The algorithm consists of four steps an encoding the result. All we need to
215 ;; do, is to call them in order.
216 ;; md5 : string/bytes/port [bool] -> string
217 (define md5
218 (case-lambda
219 [(a-thing) (md5 a-thing #t)]
220 [(a-thing hex-encode?)
221 (let ([a-port
222 (cond [(bytes? a-thing) (open-input-bytes a-thing)]
223 [(string? a-thing) (open-input-string a-thing)]
224 [(input-port? a-thing) a-thing]
225 [else (raise-type-error 'md5 "input-port, bytes, or string"
226 a-thing)])])
227 (encode (step4 a-port) hex-encode?))]))
228
229 ;; Step 1 - Append Padding Bits
230 ;; The message is padded so the length (in bits) becomes 448 modulo 512. We
231 ;; allways append a 1 bit and then append the proper numbber of 0's. NB: 448
232 ;; bits is 14 words and 512 bits is 16 words
233 ;; step1 : bytes -> bytes
234 (define (step1 message)
235 (let* ([nbytes (modulo (- 448/8 (bytes-length message)) 512/8)]
236 [nbytes (if (zero? nbytes) 512/8 nbytes)])
237 (bytes-append message
238 #"\x80" ; the 1 bit byte => one less 0 bytes to append
239 (make-bytes (sub1 nbytes) 0))))
240
241 ;; Step 2 - Append Length
242 ;; A 64 bit representation of the bit length b of the message before the
243 ;; padding of step 1 is appended. Lower word first.
244 ;; step2 : number bytes -> bytes
245 ;; org-len is the length of the original message in number of bits
246 (define (step2 len padded-message)
247 (bytes-append padded-message (integer->integer-bytes len 8 #f #f)))
248
249 ;; Step 3 - Initialize MD Buffer
250 ;; These magic constants are used to initialize the loop in step 4.
251 ;;
252 ;; word A: 01 23 45 67
253 ;; word B: 89 ab cd ef
254 ;; word C: fe dc ba 98
255 ;; word D: 76 54 32 10
256
257 ;; Step 4 - Process Message in 16-Word Blocks
258 ;; For each 16 word block, go through a round one to four.
259 ;; step4 : input-port -> (list word word word word)
260
261 ;; Step 3 :-) (magic constants)
262 (define (step4 a-port)
263 ;; X is always a vector of 16 words (it changes in read-block!)
264 (define X
265 (vector
266 (mcons 0 0) (mcons 0 0) (mcons 0 0) (mcons 0 0) (mcons 0 0) (mcons 0 0)
267 (mcons 0 0) (mcons 0 0) (mcons 0 0) (mcons 0 0) (mcons 0 0) (mcons 0 0)
268 (mcons 0 0) (mcons 0 0) (mcons 0 0) (mcons 0 0)))
269 (define A (word #:new+safe #x67452301))
270 (define B (word #:new+safe #xefcdab89))
271 (define C (word #:new+safe #x98badcfe))
272 (define D (word #:new+safe #x10325476))
273 (define AA (mcons 0 0))
274 (define BB (mcons 0 0))
275 (define CC (mcons 0 0))
276 (define DD (mcons 0 0))
277 (define tmp (mcons 0 0))
278 (let loop ([a-port a-port] [done 0])
279 (if (not a-port)
280 (list A B C D)
281 (let-values ([(b-port done) (read-block! a-port done X)])
282 (define-syntax step
283 (syntax-rules ()
284 [(_ a b c d e f g h)
285 #| This is the `no GC version' (aka C-in-Scheme) of this:
286 (set! a (word+ b (word<<< (word+ (word+ a (e b c d))
287 (word+ (vector-ref X f)
288 (word h)))
289 g)))
290 |#
291 (begin (e tmp b c d)
292 (word+=! a tmp)
293 (word+=! a (vector-ref X f))
294 (word+=! a (word h))
295 (word<<<! a g)
296 (word+=! a b))]))
297 ;;---
298 (word=! AA A) (word=! BB B) (word=! CC C) (word=! DD D)
299 ;;---
300 ;; the last column is generated with
301 ;; (lambda (i) (inexact->exact (floor (* 4294967296 (abs (sin i))))))
302 ;; for i from 1 to 64
303 (step A B C D F 0 7 3614090360)
304 (step D A B C F 1 12 3905402710)
305 (step C D A B F 2 17 606105819)
306 (step B C D A F 3 22 3250441966)
307 (step A B C D F 4 7 4118548399)
308 (step D A B C F 5 12 1200080426)
309 (step C D A B F 6 17 2821735955)
310 (step B C D A F 7 22 4249261313)
311 (step A B C D F 8 7 1770035416)
312 (step D A B C F 9 12 2336552879)
313 (step C D A B F 10 17 4294925233)
314 (step B C D A F 11 22 2304563134)
315 (step A B C D F 12 7 1804603682)
316 (step D A B C F 13 12 4254626195)
317 (step C D A B F 14 17 2792965006)
318 (step B C D A F 15 22 1236535329)
319 ;;---
320 (step A B C D G 1 5 4129170786)
321 (step D A B C G 6 9 3225465664)
322 (step C D A B G 11 14 643717713)
323 (step B C D A G 0 20 3921069994)
324 (step A B C D G 5 5 3593408605)
325 (step D A B C G 10 9 38016083)
326 (step C D A B G 15 14 3634488961)
327 (step B C D A G 4 20 3889429448)
328 (step A B C D G 9 5 568446438)
329 (step D A B C G 14 9 3275163606)
330 (step C D A B G 3 14 4107603335)
331 (step B C D A G 8 20 1163531501)
332 (step A B C D G 13 5 2850285829)
333 (step D A B C G 2 9 4243563512)
334 (step C D A B G 7 14 1735328473)
335 (step B C D A G 12 20 2368359562)
336 ;;---
337 (step A B C D H 5 4 4294588738)
338 (step D A B C H 8 11 2272392833)
339 (step C D A B H 11 16 1839030562)
340 (step B C D A H 14 23 4259657740)
341 (step A B C D H 1 4 2763975236)
342 (step D A B C H 4 11 1272893353)
343 (step C D A B H 7 16 4139469664)
344 (step B C D A H 10 23 3200236656)
345 (step A B C D H 13 4 681279174)
346 (step D A B C H 0 11 3936430074)
347 (step C D A B H 3 16 3572445317)
348 (step B C D A H 6 23 76029189)
349 (step A B C D H 9 4 3654602809)
350 (step D A B C H 12 11 3873151461)
351 (step C D A B H 15 16 530742520)
352 (step B C D A H 2 23 3299628645)
353 ;;---
354 (step A B C D II 0 6 4096336452)
355 (step D A B C II 7 10 1126891415)
356 (step C D A B II 14 15 2878612391)
357 (step B C D A II 5 21 4237533241)
358 (step A B C D II 12 6 1700485571)
359 (step D A B C II 3 10 2399980690)
360 (step C D A B II 10 15 4293915773)
361 (step B C D A II 1 21 2240044497)
362 (step A B C D II 8 6 1873313359)
363 (step D A B C II 15 10 4264355552)
364 (step C D A B II 6 15 2734768916)
365 (step B C D A II 13 21 1309151649)
366 (step A B C D II 4 6 4149444226)
367 (step D A B C II 11 10 3174756917)
368 (step C D A B II 2 15 718787259)
369 (step B C D A II 9 21 3951481745)
370 ;;---
371 (word+=! A AA) (word+=! B BB) (word+=! C CC) (word+=! D DD)
372 ;;---
373 (loop b-port done)))))
374
375 ;; Each round consists of the application of the following basic functions.
376 ;; They functions on a word bitwise, as follows.
377 ;; F(X,Y,Z) = XY v not(X) Z (NB: or can be replaced with + in F)
378 ;; G(X,Y,Z) = XZ v Y not(Z)
379 ;; H(X,Y,Z) = X xor Y xor Z
380 ;; I(X,Y,Z) = Y xor (X v not(Z))
381
382 #| These functions used to be simple, for example:
383 (define (F x y z)
384 (word-or (word-and x y) (word-and (word-not x) z)))
385 but we don't want to allocate stuff for each operation, so we add an output
386 pair for each of these functions (the `t' argument). However, this means
387 that if we want to avoid consing, we need either a few such pre-allocated
388 `register' values... The solution is to use a macro that will perform an
389 operation on the cars, cdrs, and set the result into the target pair. Works
390 only because these operations are symmetrical in their use of the two
391 halves.
392 |#
393
394 (define-syntax cons-op!
395 (syntax-rules ()
396 [(cons-op! t (x ...) body)
397 (cons! t (let ([x (mcar x)] ...) body) (let ([x (mcdr x)] ...) body))]))
398
399 (define (F t x y z)
400 (cons-op! t (x y z)
401 (bitwise-and (bitwise-ior (bitwise-and x y)
402 (bitwise-and (bitwise-not x) z))
403 65535)))
404
405 (define (G t x y z)
406 (cons-op! t (x y z)
407 (bitwise-and (bitwise-ior (bitwise-and x z)
408 (bitwise-and y (bitwise-not z)))
409 65535)))
410
411 (define (H t x y z)
412 (cons-op! t (x y z) (bitwise-xor x y z)))
413
414 (define (II t x y z)
415 (cons-op! t (x y z)
416 (bitwise-and (bitwise-xor y (bitwise-ior x (bitwise-not z)))
417 65535)))
418
419 ;; Step 5 - Encoding
420 ;; To finish up, we convert the word to hexadecimal string - and make sure they
421 ;; end up in order.
422 ;; encode : (list word word word word) bool -> byte-string
423
424 (define hex-digits #(48 49 50 51 52 53 54 55 56 57 97 98 99 100 101 102))
425 ;; word->digits : word -> bytes-string,
426 ;; returns a little endian result, but each byte is hi half and then lo half
427 (define (word->digits w)
428 (let ([digit (lambda (n b)
429 (vector-ref hex-digits
430 (bitwise-and (arithmetic-shift n (- b)) 15)))]
431 [lo (mcdr w)] [hi (mcar w)])
432 (bytes (digit lo 4) (digit lo 0) (digit lo 12) (digit lo 8)
433 (digit hi 4) (digit hi 0) (digit hi 12) (digit hi 8))))
434 (define (word->bytes w)
435 (bytes-append (integer->integer-bytes (mcdr w) 2 #f #f)
436 (integer->integer-bytes (mcar w) 2 #f #f)))
437 (define (encode l hex-encode?)
438 (apply bytes-append (map (if hex-encode? word->digits word->bytes) l)))