1 /*
2  * $Id: md5.i,v 1.1 2005-09-18 22:06:16 dhmunro Exp $
3  * routines to compute MD5 checksums
4  * entirely in interpreted code, so they are slow,
5  *   on the order of a few seconds per megabyte
6  * original C source from L. Peter Deutsch ghost@aladdin.com
7  *   adapted by David H. Munro
8  */
9 /* Copyright (c) 2005, The Regents of the University of California.
10  * All rights reserved.
11  * This file is part of yorick (http://yorick.sourceforge.net).
12  * Read the accompanying LICENSE file for details.
13  */
14 
15 func md5sum(file, hex=)
16 /* DOCUMENT digest = md5sum(filename)
17  *          digest = md5sum(filename, hex=1)
18  *   compute MD5 digest of a file, an array of 16 char
19  *   with the hex=1 keyword, returned digest is a string (in hex)
20  *
21  * SEE ALSO: md5
22  */
23 {
24   if (!is_stream(file)) file = open(file, "rb");
25   nbyte = sizeof(file);
26   if (!nbyte) return md5(md5());
27   nchunk = 1000000;  /* process file in megabyte chunks */
28   buf = array(char, min(nbyte,nchunk));
29   for (state=[],n=0 ; n<nbyte ; n+=nchunk) {
30     if (n+nchunk > nbyte) {
31       nchunk = nbyte - n;
32       if (sizeof(buf) > nchunk) buf = array(char, nchunk);
33     }
34     if (_read(file,n,buf) < nchunk)
35       error, "i/o error reading file";
36     state = md5(buf, state);
37   }
38   return md5(state, hex=hex);
39 }
40 
41 func md5(data, state, hex=)
42 /* DOCUMENT state = md5(data)
43  *          state = md5(data, state)
44  *          digest = md5(state)
45  *          digest = md5(state, hex=1)
46  *   compute MD5 digest of data, an array of 16 char
47  *   with the hex=1 keyword, returned digest is a string (in hex)
48  *
49  * SEE ALSO: md5sum
50  */
51 {
52   local count, digest;
53   type = structof(data);
54   if (is_void(state)) {
55     if (type == pointer) {
56       /* no more data, return MD5 digest */
57       count = *data(1);                /* makes a copy of count */
58       _md5_increment, count, sizeof(*data(3));  /* add pending */
59       /* number of additional bytes to reach 56 mod 64 */
60       nbyte = ((55-(count(1)>>3))&63) + 1;
61       pad = grow(array(char, nbyte), _md5_number(count));
62       pad(1) = '\x80';
63       state = md5(pad, data);
64       return _md5_hex(_md5_number(*state(2)), hex=hex);
65     }
66 
67     /* create a new state, this is first call for this digest */
68     state = [&[0, 0],
69              &[0x67452301, ~0x10325476, ~0x67452301, 0x10325476],
70              &[]];
71     if (is_void(data)) return state;
72   }
73 
74   if (type != char) error, "md5 requires char input data";
75 
76   data = grow(*state(3), data(*));   /* prepend any leftover data */
77   nbyte = sizeof(data);
78   next = nbyte & 63;
79   state(3) = next? &data(1-next:0) : &[];
80   nbyte -= next;
81 
82   if (nbyte) {
83     eq_nocopy, count, *state(1);
84     _md5_increment, count, nbyte;
85 
86     nword = nbyte>>6;
87     tmp = array(char, 4, 16, nword);
88     tmp(*) = data(1:-next);
89     tmp = long(tmp);
90     data = tmp(1,,) | (tmp(2,,)<<8) | (tmp(3,,)<<16) | (tmp(4,,)<<24);
91     tmp = [];
92 
93     eq_nocopy, digest, *state(2);
94     a0 = digest(1);
95     b0 = digest(2);
96     c0 = digest(3);
97     d0 = digest(4);
98 
99     for (i=1 ; i<=nword ; ++i) {
100       x = data(_md5_order,i) + _md5_t;
101       a = a0;
102       b = b0;
103       c = c0;
104       d = d0;
105       /* round 1 */
106       a = a + ((b & c) | ((~b) & d)) + x(1);
107       a = ((a << 7) | ((a >> 25)&0x0000007f)) + b;
108       d = d + ((a & b) | ((~a) & c)) + x(2);
109       d = ((d << 12) | ((d >> 20)&0x00000fff)) + a;
110       c = c + ((d & a) | ((~d) & b)) + x(3);
111       c = ((c << 17) | ((c >> 15)&0x0001ffff)) + d;
112       b = b + ((c & d) | ((~c) & a)) + x(4);
113       b = ((b << 22) | ((b >> 10)&0x003fffff)) + c;
114       a = a + ((b & c) | ((~b) & d)) + x(5);
115       a = ((a << 7) | ((a >> 25)&0x0000007f)) + b;
116       d = d + ((a & b) | ((~a) & c)) + x(6);
117       d = ((d << 12) | ((d >> 20)&0x00000fff)) + a;
118       c = c + ((d & a) | ((~d) & b)) + x(7);
119       c = ((c << 17) | ((c >> 15)&0x0001ffff)) + d;
120       b = b + ((c & d) | ((~c) & a)) + x(8);
121       b = ((b << 22) | ((b >> 10)&0x003fffff)) + c;
122       a = a + ((b & c) | ((~b) & d)) + x(9);
123       a = ((a << 7) | ((a >> 25)&0x0000007f)) + b;
124       d = d + ((a & b) | ((~a) & c)) + x(10);
125       d = ((d << 12) | ((d >> 20)&0x00000fff)) + a;
126       c = c + ((d & a) | ((~d) & b)) + x(11);
127       c = ((c << 17) | ((c >> 15)&0x0001ffff)) + d;
128       b = b + ((c & d) | ((~c) & a)) + x(12);
129       b = ((b << 22) | ((b >> 10)&0x003fffff)) + c;
130       a = a + ((b & c) | ((~b) & d)) + x(13);
131       a = ((a << 7) | ((a >> 25)&0x0000007f)) + b;
132       d = d + ((a & b) | ((~a) & c)) + x(14);
133       d = ((d << 12) | ((d >> 20)&0x00000fff)) + a;
134       c = c + ((d & a) | ((~d) & b)) + x(15);
135       c = ((c << 17) | ((c >> 15)&0x0001ffff)) + d;
136       b = b + ((c & d) | ((~c) & a)) + x(16);
137       b = ((b << 22) | ((b >> 10)&0x003fffff)) + c;
138       /* round 2 */
139       a = a + ((b & d) | ((~d) & c)) + x(17);
140       a = ((a << 5) | ((a >> 27)&0x0000001f)) + b;
141       d = d + ((a & c) | ((~c) & b)) + x(18);
142       d = ((d << 9) | ((d >> 23)&0x000001ff)) + a;
143       c = c + ((d & b) | ((~b) & a)) + x(19);
144       c = ((c << 14) | ((c >> 18)&0x00003fff)) + d;
145       b = b + ((c & a) | ((~a) & d)) + x(20);
146       b = ((b << 20) | ((b >> 12)&0x000fffff)) + c;
147       a = a + ((b & d) | ((~d) & c)) + x(21);
148       a = ((a << 5) | ((a >> 27)&0x0000001f)) + b;
149       d = d + ((a & c) | ((~c) & b)) + x(22);
150       d = ((d << 9) | ((d >> 23)&0x000001ff)) + a;
151       c = c + ((d & b) | ((~b) & a)) + x(23);
152       c = ((c << 14) | ((c >> 18)&0x00003fff)) + d;
153       b = b + ((c & a) | ((~a) & d)) + x(24);
154       b = ((b << 20) | ((b >> 12)&0x000fffff)) + c;
155       a = a + ((b & d) | ((~d) & c)) + x(25);
156       a = ((a << 5) | ((a >> 27)&0x0000001f)) + b;
157       d = d + ((a & c) | ((~c) & b)) + x(26);
158       d = ((d << 9) | ((d >> 23)&0x000001ff)) + a;
159       c = c + ((d & b) | ((~b) & a)) + x(27);
160       c = ((c << 14) | ((c >> 18)&0x00003fff)) + d;
161       b = b + ((c & a) | ((~a) & d)) + x(28);
162       b = ((b << 20) | ((b >> 12)&0x000fffff)) + c;
163       a = a + ((b & d) | ((~d) & c)) + x(29);
164       a = ((a << 5) | ((a >> 27)&0x0000001f)) + b;
165       d = d + ((a & c) | ((~c) & b)) + x(30);
166       d = ((d << 9) | ((d >> 23)&0x000001ff)) + a;
167       c = c + ((d & b) | ((~b) & a)) + x(31);
168       c = ((c << 14) | ((c >> 18)&0x00003fff)) + d;
169       b = b + ((c & a) | ((~a) & d)) + x(32);
170       b = ((b << 20) | ((b >> 12)&0x000fffff)) + c;
171       /* round 3 */
172       a = a + (b ~ c ~ d) + x(33);
173       a = ((a << 4) | ((a >> 28)&0x0000000f)) + b;
174       d = d + (a ~ b ~ c) + x(34);
175       d = ((d << 11) | ((d >> 21)&0x000007ff)) + a;
176       c = c + (d ~ a ~ b) + x(35);
177       c = ((c << 16) | ((c >> 16)&0x0000ffff)) + d;
178       b = b + (c ~ d ~ a) + x(36);
179       b = ((b << 23) | ((b >> 9)&0x007fffff)) + c;
180       a = a + (b ~ c ~ d) + x(37);
181       a = ((a << 4) | ((a >> 28)&0x0000000f)) + b;
182       d = d + (a ~ b ~ c) + x(38);
183       d = ((d << 11) | ((d >> 21)&0x000007ff)) + a;
184       c = c + (d ~ a ~ b) + x(39);
185       c = ((c << 16) | ((c >> 16)&0x0000ffff)) + d;
186       b = b + (c ~ d ~ a) + x(40);
187       b = ((b << 23) | ((b >> 9)&0x007fffff)) + c;
188       a = a + (b ~ c ~ d) + x(41);
189       a = ((a << 4) | ((a >> 28)&0x0000000f)) + b;
190       d = d + (a ~ b ~ c) + x(42);
191       d = ((d << 11) | ((d >> 21)&0x000007ff)) + a;
192       c = c + (d ~ a ~ b) + x(43);
193       c = ((c << 16) | ((c >> 16)&0x0000ffff)) + d;
194       b = b + (c ~ d ~ a) + x(44);
195       b = ((b << 23) | ((b >> 9)&0x007fffff)) + c;
196       a = a + (b ~ c ~ d) + x(45);
197       a = ((a << 4) | ((a >> 28)&0x0000000f)) + b;
198       d = d + (a ~ b ~ c) + x(46);
199       d = ((d << 11) | ((d >> 21)&0x000007ff)) + a;
200       c = c + (d ~ a ~ b) + x(47);
201       c = ((c << 16) | ((c >> 16)&0x0000ffff)) + d;
202       b = b + (c ~ d ~ a) + x(48);
203       b = ((b << 23) | ((b >> 9)&0x007fffff)) + c;
204       /* round 4 */
205       a = a + (c ~ ((~d) | b)) + x(49);
206       a = ((a << 6) | ((a >> 26)&0x0000003f)) + b;
207       d = d + (b ~ ((~c) | a)) + x(50);
208       d = ((d << 10) | ((d >> 22)&0x000003ff)) + a;
209       c = c + (a ~ ((~b) | d)) + x(51);
210       c = ((c << 15) | ((c >> 17)&0x00007fff)) + d;
211       b = b + (d ~ ((~a) | c)) + x(52);
212       b = ((b << 21) | ((b >> 11)&0x001fffff)) + c;
213       a = a + (c ~ ((~d) | b)) + x(53);
214       a = ((a << 6) | ((a >> 26)&0x0000003f)) + b;
215       d = d + (b ~ ((~c) | a)) + x(54);
216       d = ((d << 10) | ((d >> 22)&0x000003ff)) + a;
217       c = c + (a ~ ((~b) | d)) + x(55);
218       c = ((c << 15) | ((c >> 17)&0x00007fff)) + d;
219       b = b + (d ~ ((~a) | c)) + x(56);
220       b = ((b << 21) | ((b >> 11)&0x001fffff)) + c;
221       a = a + (c ~ ((~d) | b)) + x(57);
222       a = ((a << 6) | ((a >> 26)&0x0000003f)) + b;
223       d = d + (b ~ ((~c) | a)) + x(58);
224       d = ((d << 10) | ((d >> 22)&0x000003ff)) + a;
225       c = c + (a ~ ((~b) | d)) + x(59);
226       c = ((c << 15) | ((c >> 17)&0x00007fff)) + d;
227       b = b + (d ~ ((~a) | c)) + x(60);
228       b = ((b << 21) | ((b >> 11)&0x001fffff)) + c;
229       a = a + (c ~ ((~d) | b)) + x(61);
230       a = ((a << 6) | ((a >> 26)&0x0000003f)) + b;
231       d = d + (b ~ ((~c) | a)) + x(62);
232       d = ((d << 10) | ((d >> 22)&0x000003ff)) + a;
233       c = c + (a ~ ((~b) | d)) + x(63);
234       c = ((c << 15) | ((c >> 17)&0x00007fff)) + d;
235       b = b + (d ~ ((~a) | c)) + x(64);
236       b = ((b << 21) | ((b >> 11)&0x001fffff)) + c;
237       a0 += a;
238       b0 += b;
239       c0 += c;
240       d0 += d;
241     }
242 
243     digest(1) = a0;
244     digest(2) = b0;
245     digest(3) = c0;
246     digest(4) = d0;
247   }
248 
249   return state;
250 }
251 
_md5_increment(count,nbyte)252 func _md5_increment(count, nbyte)
253 {
254   /* add number of bits to count, with carry if overflows 32 bits */
255   count(2) += nbyte >> 29;
256   old = count(1);
257   nlo = (nbyte << 3) & 0xffffffff;
258   count(1) = new = (old + nlo) & 0xffffffff;
259   if ((new&0x80000000)? (old & nlo & 0x80000000) : ((old | nlo)&0x80000000))
260     count(1) += 1;
261 }
262 
_md5_number(w)263 func _md5_number(w)
264 {
265   return char( w(-,) >> [0,8,16,24] )(*);
266 }
267 
268 _md5_order = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,
269               2,7,12,1,6,11,16,5,10,15,4,9,14,3,8,13,
270               6,9,12,15,2,5,8,11,14,1,4,7,10,13,16,3,
271               1,8,15,6,13,4,11,2,9,16,7,14,5,12,3,10];
272 
273 _md5_t = [~0x28955b87, ~0x173848a9, 0x242070db, ~0x3e423111, ~0x0a83f050,
274           0x4787c62a, ~0x57cfb9ec, ~0x02b96afe, 0x698098d8, ~0x74bb0850,
275           ~0x0000a44e, ~0x76a32841, 0x6b901122, ~0x02678e6c, ~0x5986bc71,
276           0x49b40821, ~0x09e1da9d, ~0x3fbf4cbf, 0x265e5a51, ~0x16493855,
277           ~0x29d0efa2, 0x02441453, ~0x275e197e, ~0x182c0437, 0x21e1cde6,
278           ~0x3cc8f829, ~0x0b2af278, 0x455a14ed, ~0x561c16fa, ~0x03105c07,
279           0x676f02d9, ~0x72d5b375, ~0x0005c6bd, ~0x788e097e, 0x6d9d6122,
280           ~0x021ac7f3, ~0x5b4115bb, 0x4bdecfa9, ~0x0944b49f, ~0x4140438f,
281           0x289b7ec6, ~0x155ed805, ~0x2b10cf7a, 0x04881d05, ~0x262b2fc6,
282           ~0x1924661a, 0x1fa27cf8, ~0x3b53a99a, ~0x0bd6ddbb, 0x432aff97,
283           ~0x546bdc58, ~0x036c5fc6, 0x655b59c3, ~0x70f3336d, ~0x00100b82,
284           ~0x7a7ba22e, 0x6fa87e4f, ~0x01d3191f, ~0x5cfebceb, 0x4e0811a1,
285           ~0x08ac817d, ~0x42c50dca, 0x2ad7d2bb, ~0x14792c6e];
286 
287 func md5_test
288 {
289   test = ["", "a", "abc", "message digest", "abcdefghijklmnopqrstuvwxyz",
290           "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
291           "12345678901234567890123456789012345678901234567890123456789"+
292           "012345678901234567890"];
293   answ = ["d41d8cd98f00b204e9800998ecf8427e",
294           "0cc175b9c0f1b6a831c399e269772661",
295           "900150983cd24fb0d6963f7d28e17f72",
296           "f96b697d7cb7938d525a2f31aaf161d0",
297           "c3fcd3d76192e4007dfb496cca67e13b",
298           "d174ab98d277d9f5a5611c2c9f419d9f",
299           "57edf4a22be3c955ac49da2e2107b67a"];
300   correct = [[0xd4,0x1d,0x8c,0xd9,0x8f,0x00,0xb2,0x04,
301               0xe9,0x80,0x09,0x98,0xec,0xf8,0x42,0x7e],
302              [0x0c,0xc1,0x75,0xb9,0xc0,0xf1,0xb6,0xa8,
303               0x31,0xc3,0x99,0xe2,0x69,0x77,0x26,0x61],
304              [0x90,0x01,0x50,0x98,0x3c,0xd2,0x4f,0xb0,
305               0xd6,0x96,0x3f,0x7d,0x28,0xe1,0x7f,0x72],
306              [0xf9,0x6b,0x69,0x7d,0x7c,0xb7,0x93,0x8d,
307               0x52,0x5a,0x2f,0x31,0xaa,0xf1,0x61,0xd0],
308              [0xc3,0xfc,0xd3,0xd7,0x61,0x92,0xe4,0x00,
309               0x7d,0xfb,0x49,0x6c,0xca,0x67,0xe1,0x3b],
310              [0xd1,0x74,0xab,0x98,0xd2,0x77,0xd9,0xf5,
311               0xa5,0x61,0x1c,0x2c,0x9f,0x41,0x9d,0x9f],
312              [0x57,0xed,0xf4,0xa2,0x2b,0xe3,0xc9,0x55,
313               0xac,0x49,0xda,0x2e,0x21,0x07,0xb6,0x7a]];
314   actual = array(char, 16, numberof(answ));
315   for (i=1 ; i<=numberof(answ) ; ++i) {
316     data = *pointer(test(i));
317     actual(,i) = md5(md5(((numberof(data)>1)?data(1:-1):[])));
318   }
319   if (anyof(actual!=correct)) error, "md5 function flunked test";
320 }
321 
322 func _md5_hex(digest, hex=)
323 {
324   if (!hex) return digest;
325   s = swrite(format="%02x",digest);
326   s = s(1:16:2) + s(2:16:2);
327   s = s(1:8:2) + s(2:8:2);
328   s = s(1:4:2) + s(2:4:2);
329   return s(1) + s(2);
330 }
331