Debian Codegraph @

closure-library/closure/goog/crypt/md5.js

raw
1 // Copyright 2011 The Closure Library Authors. All Rights Reserved.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS-IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 /**
16 * @fileoverview MD5 cryptographic hash.
17 * Implementation of http://tools.ietf.org/html/rfc1321 with common
18 * optimizations and tweaks (see http://en.wikipedia.org/wiki/MD5).
19 *
20 * Usage:
21 * var md5 = new goog.crypt.Md5();
22 * md5.update(bytes);
23 * var hash = md5.digest();
24 *
25 * Performance:
26 * Chrome 23 ~680 Mbit/s
27 * Chrome 13 (in a VM) ~250 Mbit/s
28 * Firefox 6.0 (in a VM) ~100 Mbit/s
29 * IE9 (in a VM) ~27 Mbit/s
30 * Firefox 3.6 ~15 Mbit/s
31 * IE8 (in a VM) ~13 Mbit/s
32 *
33 */
34
35 goog.provide('goog.crypt.Md5');
36
37 goog.require('goog.crypt.Hash');
38
39
40
41 /**
42 * MD5 cryptographic hash constructor.
43 * @constructor
44 * @extends {goog.crypt.Hash}
45 * @final
46 * @struct
47 */
48 goog.crypt.Md5 = function() {
49 goog.crypt.Md5.base(this, 'constructor');
50
51 this.blockSize = 512 / 8;
52
53 /**
54 * Holds the current values of accumulated A-D variables (MD buffer).
55 * @type {!Array<number>}
56 * @private
57 */
58 this.chain_ = new Array(4);
59
60 /**
61 * A buffer holding the data until the whole block can be processed.
62 * @type {!Array<number>}
63 * @private
64 */
65 this.block_ = new Array(this.blockSize);
66
67 /**
68 * The length of yet-unprocessed data as collected in the block.
69 * @type {number}
70 * @private
71 */
72 this.blockLength_ = 0;
73
74 /**
75 * The total length of the message so far.
76 * @type {number}
77 * @private
78 */
79 this.totalLength_ = 0;
80
81 this.reset();
82 };
83 goog.inherits(goog.crypt.Md5, goog.crypt.Hash);
84
85
86 /**
87 * Integer rotation constants used by the abbreviated implementation.
88 * They are hardcoded in the unrolled implementation, so it is left
89 * here commented out.
90 * @type {Array<number>}
91 * @private
92 *
93 goog.crypt.Md5.S_ = [
94 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
95 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
96 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
97 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21
98 ];
99 */
100
101 /**
102 * Sine function constants used by the abbreviated implementation.
103 * They are hardcoded in the unrolled implementation, so it is left
104 * here commented out.
105 * @type {Array<number>}
106 * @private
107 *
108 goog.crypt.Md5.T_ = [
109 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
110 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
111 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
112 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
113 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
114 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
115 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
116 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
117 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
118 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
119 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05,
120 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
121 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
122 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
123 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
124 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
125 ];
126 */
127
128
129 /** @override */
130 goog.crypt.Md5.prototype.reset = function() {
131 this.chain_[0] = 0x67452301;
132 this.chain_[1] = 0xefcdab89;
133 this.chain_[2] = 0x98badcfe;
134 this.chain_[3] = 0x10325476;
135
136 this.blockLength_ = 0;
137 this.totalLength_ = 0;
138 };
139
140
141 /**
142 * Internal compress helper function. It takes a block of data (64 bytes)
143 * and updates the accumulator.
144 * @param {Array<number>|Uint8Array|string} buf The block to compress.
145 * @param {number=} opt_offset Offset of the block in the buffer.
146 * @private
147 */
148 goog.crypt.Md5.prototype.compress_ = function(buf, opt_offset) {
149 if (!opt_offset) {
150 opt_offset = 0;
151 }
152
153 // We allocate the array every time, but it's cheap in practice.
154 var X = new Array(16);
155
156 // Get 16 little endian words. It is not worth unrolling this for Chrome 11.
157 if (goog.isString(buf)) {
158 for (var i = 0; i < 16; ++i) {
159 X[i] = (buf.charCodeAt(opt_offset++)) |
160 (buf.charCodeAt(opt_offset++) << 8) |
161 (buf.charCodeAt(opt_offset++) << 16) |
162 (buf.charCodeAt(opt_offset++) << 24);
163 }
164 } else {
165 for (var i = 0; i < 16; ++i) {
166 X[i] = (buf[opt_offset++]) | (buf[opt_offset++] << 8) |
167 (buf[opt_offset++] << 16) | (buf[opt_offset++] << 24);
168 }
169 }
170
171 var A = this.chain_[0];
172 var B = this.chain_[1];
173 var C = this.chain_[2];
174 var D = this.chain_[3];
175 var sum = 0;
176
177 /*
178 * This is an abbreviated implementation, it is left here commented out for
179 * reference purposes. See below for an unrolled version in use.
180 *
181 var f, n, tmp;
182 for (var i = 0; i < 64; ++i) {
183
184 if (i < 16) {
185 f = (D ^ (B & (C ^ D)));
186 n = i;
187 } else if (i < 32) {
188 f = (C ^ (D & (B ^ C)));
189 n = (5 * i + 1) % 16;
190 } else if (i < 48) {
191 f = (B ^ C ^ D);
192 n = (3 * i + 5) % 16;
193 } else {
194 f = (C ^ (B | (~D)));
195 n = (7 * i) % 16;
196 }
197
198 tmp = D;
199 D = C;
200 C = B;
201 sum = (A + f + goog.crypt.Md5.T_[i] + X[n]) & 0xffffffff;
202 B += ((sum << goog.crypt.Md5.S_[i]) & 0xffffffff) |
203 (sum >>> (32 - goog.crypt.Md5.S_[i]));
204 A = tmp;
205 }
206 */
207
208 /*
209 * This is an unrolled MD5 implementation, which gives ~30% speedup compared
210 * to the abbreviated implementation above, as measured on Chrome 11. It is
211 * important to keep 32-bit croppings to minimum and inline the integer
212 * rotation.
213 */
214 sum = (A + (D ^ (B & (C ^ D))) + X[0] + 0xd76aa478) & 0xffffffff;
215 A = B + (((sum << 7) & 0xffffffff) | (sum >>> 25));
216 sum = (D + (C ^ (A & (B ^ C))) + X[1] + 0xe8c7b756) & 0xffffffff;
217 D = A + (((sum << 12) & 0xffffffff) | (sum >>> 20));
218 sum = (C + (B ^ (D & (A ^ B))) + X[2] + 0x242070db) & 0xffffffff;
219 C = D + (((sum << 17) & 0xffffffff) | (sum >>> 15));
220 sum = (B + (A ^ (C & (D ^ A))) + X[3] + 0xc1bdceee) & 0xffffffff;
221 B = C + (((sum << 22) & 0xffffffff) | (sum >>> 10));
222 sum = (A + (D ^ (B & (C ^ D))) + X[4] + 0xf57c0faf) & 0xffffffff;
223 A = B + (((sum << 7) & 0xffffffff) | (sum >>> 25));
224 sum = (D + (C ^ (A & (B ^ C))) + X[5] + 0x4787c62a) & 0xffffffff;
225 D = A + (((sum << 12) & 0xffffffff) | (sum >>> 20));
226 sum = (C + (B ^ (D & (A ^ B))) + X[6] + 0xa8304613) & 0xffffffff;
227 C = D + (((sum << 17) & 0xffffffff) | (sum >>> 15));
228 sum = (B + (A ^ (C & (D ^ A))) + X[7] + 0xfd469501) & 0xffffffff;
229 B = C + (((sum << 22) & 0xffffffff) | (sum >>> 10));
230 sum = (A + (D ^ (B & (C ^ D))) + X[8] + 0x698098d8) & 0xffffffff;
231 A = B + (((sum << 7) & 0xffffffff) | (sum >>> 25));
232 sum = (D + (C ^ (A & (B ^ C))) + X[9] + 0x8b44f7af) & 0xffffffff;
233 D = A + (((sum << 12) & 0xffffffff) | (sum >>> 20));
234 sum = (C + (B ^ (D & (A ^ B))) + X[10] + 0xffff5bb1) & 0xffffffff;
235 C = D + (((sum << 17) & 0xffffffff) | (sum >>> 15));
236 sum = (B + (A ^ (C & (D ^ A))) + X[11] + 0x895cd7be) & 0xffffffff;
237 B = C + (((sum << 22) & 0xffffffff) | (sum >>> 10));
238 sum = (A + (D ^ (B & (C ^ D))) + X[12] + 0x6b901122) & 0xffffffff;
239 A = B + (((sum << 7) & 0xffffffff) | (sum >>> 25));
240 sum = (D + (C ^ (A & (B ^ C))) + X[13] + 0xfd987193) & 0xffffffff;
241 D = A + (((sum << 12) & 0xffffffff) | (sum >>> 20));
242 sum = (C + (B ^ (D & (A ^ B))) + X[14] + 0xa679438e) & 0xffffffff;
243 C = D + (((sum << 17) & 0xffffffff) | (sum >>> 15));
244 sum = (B + (A ^ (C & (D ^ A))) + X[15] + 0x49b40821) & 0xffffffff;
245 B = C + (((sum << 22) & 0xffffffff) | (sum >>> 10));
246 sum = (A + (C ^ (D & (B ^ C))) + X[1] + 0xf61e2562) & 0xffffffff;
247 A = B + (((sum << 5) & 0xffffffff) | (sum >>> 27));
248 sum = (D + (B ^ (C & (A ^ B))) + X[6] + 0xc040b340) & 0xffffffff;
249 D = A + (((sum << 9) & 0xffffffff) | (sum >>> 23));
250 sum = (C + (A ^ (B & (D ^ A))) + X[11] + 0x265e5a51) & 0xffffffff;
251 C = D + (((sum << 14) & 0xffffffff) | (sum >>> 18));
252 sum = (B + (D ^ (A & (C ^ D))) + X[0] + 0xe9b6c7aa) & 0xffffffff;
253 B = C + (((sum << 20) & 0xffffffff) | (sum >>> 12));
254 sum = (A + (C ^ (D & (B ^ C))) + X[5] + 0xd62f105d) & 0xffffffff;
255 A = B + (((sum << 5) & 0xffffffff) | (sum >>> 27));
256 sum = (D + (B ^ (C & (A ^ B))) + X[10] + 0x02441453) & 0xffffffff;
257 D = A + (((sum << 9) & 0xffffffff) | (sum >>> 23));
258 sum = (C + (A ^ (B & (D ^ A))) + X[15] + 0xd8a1e681) & 0xffffffff;
259 C = D + (((sum << 14) & 0xffffffff) | (sum >>> 18));
260 sum = (B + (D ^ (A & (C ^ D))) + X[4] + 0xe7d3fbc8) & 0xffffffff;
261 B = C + (((sum << 20) & 0xffffffff) | (sum >>> 12));
262 sum = (A + (C ^ (D & (B ^ C))) + X[9] + 0x21e1cde6) & 0xffffffff;
263 A = B + (((sum << 5) & 0xffffffff) | (sum >>> 27));
264 sum = (D + (B ^ (C & (A ^ B))) + X[14] + 0xc33707d6) & 0xffffffff;
265 D = A + (((sum << 9) & 0xffffffff) | (sum >>> 23));
266 sum = (C + (A ^ (B & (D ^ A))) + X[3] + 0xf4d50d87) & 0xffffffff;
267 C = D + (((sum << 14) & 0xffffffff) | (sum >>> 18));
268 sum = (B + (D ^ (A & (C ^ D))) + X[8] + 0x455a14ed) & 0xffffffff;
269 B = C + (((sum << 20) & 0xffffffff) | (sum >>> 12));
270 sum = (A + (C ^ (D & (B ^ C))) + X[13] + 0xa9e3e905) & 0xffffffff;
271 A = B + (((sum << 5) & 0xffffffff) | (sum >>> 27));
272 sum = (D + (B ^ (C & (A ^ B))) + X[2] + 0xfcefa3f8) & 0xffffffff;
273 D = A + (((sum << 9) & 0xffffffff) | (sum >>> 23));
274 sum = (C + (A ^ (B & (D ^ A))) + X[7] + 0x676f02d9) & 0xffffffff;
275 C = D + (((sum << 14) & 0xffffffff) | (sum >>> 18));
276 sum = (B + (D ^ (A & (C ^ D))) + X[12] + 0x8d2a4c8a) & 0xffffffff;
277 B = C + (((sum << 20) & 0xffffffff) | (sum >>> 12));
278 sum = (A + (B ^ C ^ D) + X[5] + 0xfffa3942) & 0xffffffff;
279 A = B + (((sum << 4) & 0xffffffff) | (sum >>> 28));
280 sum = (D + (A ^ B ^ C) + X[8] + 0x8771f681) & 0xffffffff;
281 D = A + (((sum << 11) & 0xffffffff) | (sum >>> 21));
282 sum = (C + (D ^ A ^ B) + X[11] + 0x6d9d6122) & 0xffffffff;
283 C = D + (((sum << 16) & 0xffffffff) | (sum >>> 16));
284 sum = (B + (C ^ D ^ A) + X[14] + 0xfde5380c) & 0xffffffff;
285 B = C + (((sum << 23) & 0xffffffff) | (sum >>> 9));
286 sum = (A + (B ^ C ^ D) + X[1] + 0xa4beea44) & 0xffffffff;
287 A = B + (((sum << 4) & 0xffffffff) | (sum >>> 28));
288 sum = (D + (A ^ B ^ C) + X[4] + 0x4bdecfa9) & 0xffffffff;
289 D = A + (((sum << 11) & 0xffffffff) | (sum >>> 21));
290 sum = (C + (D ^ A ^ B) + X[7] + 0xf6bb4b60) & 0xffffffff;
291 C = D + (((sum << 16) & 0xffffffff) | (sum >>> 16));
292 sum = (B + (C ^ D ^ A) + X[10] + 0xbebfbc70) & 0xffffffff;
293 B = C + (((sum << 23) & 0xffffffff) | (sum >>> 9));
294 sum = (A + (B ^ C ^ D) + X[13] + 0x289b7ec6) & 0xffffffff;
295 A = B + (((sum << 4) & 0xffffffff) | (sum >>> 28));
296 sum = (D + (A ^ B ^ C) + X[0] + 0xeaa127fa) & 0xffffffff;
297 D = A + (((sum << 11) & 0xffffffff) | (sum >>> 21));
298 sum = (C + (D ^ A ^ B) + X[3] + 0xd4ef3085) & 0xffffffff;
299 C = D + (((sum << 16) & 0xffffffff) | (sum >>> 16));
300 sum = (B + (C ^ D ^ A) + X[6] + 0x04881d05) & 0xffffffff;
301 B = C + (((sum << 23) & 0xffffffff) | (sum >>> 9));
302 sum = (A + (B ^ C ^ D) + X[9] + 0xd9d4d039) & 0xffffffff;
303 A = B + (((sum << 4) & 0xffffffff) | (sum >>> 28));
304 sum = (D + (A ^ B ^ C) + X[12] + 0xe6db99e5) & 0xffffffff;
305 D = A + (((sum << 11) & 0xffffffff) | (sum >>> 21));
306 sum = (C + (D ^ A ^ B) + X[15] + 0x1fa27cf8) & 0xffffffff;
307 C = D + (((sum << 16) & 0xffffffff) | (sum >>> 16));
308 sum = (B + (C ^ D ^ A) + X[2] + 0xc4ac5665) & 0xffffffff;
309 B = C + (((sum << 23) & 0xffffffff) | (sum >>> 9));
310 sum = (A + (C ^ (B | (~D))) + X[0] + 0xf4292244) & 0xffffffff;
311 A = B + (((sum << 6) & 0xffffffff) | (sum >>> 26));
312 sum = (D + (B ^ (A | (~C))) + X[7] + 0x432aff97) & 0xffffffff;
313 D = A + (((sum << 10) & 0xffffffff) | (sum >>> 22));
314 sum = (C + (A ^ (D | (~B))) + X[14] + 0xab9423a7) & 0xffffffff;
315 C = D + (((sum << 15) & 0xffffffff) | (sum >>> 17));
316 sum = (B + (D ^ (C | (~A))) + X[5] + 0xfc93a039) & 0xffffffff;
317 B = C + (((sum << 21) & 0xffffffff) | (sum >>> 11));
318 sum = (A + (C ^ (B | (~D))) + X[12] + 0x655b59c3) & 0xffffffff;
319 A = B + (((sum << 6) & 0xffffffff) | (sum >>> 26));
320 sum = (D + (B ^ (A | (~C))) + X[3] + 0x8f0ccc92) & 0xffffffff;
321 D = A + (((sum << 10) & 0xffffffff) | (sum >>> 22));
322 sum = (C + (A ^ (D | (~B))) + X[10] + 0xffeff47d) & 0xffffffff;
323 C = D + (((sum << 15) & 0xffffffff) | (sum >>> 17));
324 sum = (B + (D ^ (C | (~A))) + X[1] + 0x85845dd1) & 0xffffffff;
325 B = C + (((sum << 21) & 0xffffffff) | (sum >>> 11));
326 sum = (A + (C ^ (B | (~D))) + X[8] + 0x6fa87e4f) & 0xffffffff;
327 A = B + (((sum << 6) & 0xffffffff) | (sum >>> 26));
328 sum = (D + (B ^ (A | (~C))) + X[15] + 0xfe2ce6e0) & 0xffffffff;
329 D = A + (((sum << 10) & 0xffffffff) | (sum >>> 22));
330 sum = (C + (A ^ (D | (~B))) + X[6] + 0xa3014314) & 0xffffffff;
331 C = D + (((sum << 15) & 0xffffffff) | (sum >>> 17));
332 sum = (B + (D ^ (C | (~A))) + X[13] + 0x4e0811a1) & 0xffffffff;
333 B = C + (((sum << 21) & 0xffffffff) | (sum >>> 11));
334 sum = (A + (C ^ (B | (~D))) + X[4] + 0xf7537e82) & 0xffffffff;
335 A = B + (((sum << 6) & 0xffffffff) | (sum >>> 26));
336 sum = (D + (B ^ (A | (~C))) + X[11] + 0xbd3af235) & 0xffffffff;
337 D = A + (((sum << 10) & 0xffffffff) | (sum >>> 22));
338 sum = (C + (A ^ (D | (~B))) + X[2] + 0x2ad7d2bb) & 0xffffffff;
339 C = D + (((sum << 15) & 0xffffffff) | (sum >>> 17));
340 sum = (B + (D ^ (C | (~A))) + X[9] + 0xeb86d391) & 0xffffffff;
341 B = C + (((sum << 21) & 0xffffffff) | (sum >>> 11));
342
343 this.chain_[0] = (this.chain_[0] + A) & 0xffffffff;
344 this.chain_[1] = (this.chain_[1] + B) & 0xffffffff;
345 this.chain_[2] = (this.chain_[2] + C) & 0xffffffff;
346 this.chain_[3] = (this.chain_[3] + D) & 0xffffffff;
347 };
348
349
350 /** @override */
351 goog.crypt.Md5.prototype.update = function(bytes, opt_length) {
352 if (!goog.isDef(opt_length)) {
353 opt_length = bytes.length;
354 }
355 var lengthMinusBlock = opt_length - this.blockSize;
356
357 // Copy some object properties to local variables in order to save on access
358 // time from inside the loop (~10% speedup was observed on Chrome 11).
359 var block = this.block_;
360 var blockLength = this.blockLength_;
361 var i = 0;
362
363 // The outer while loop should execute at most twice.
364 while (i < opt_length) {
365 // When we have no data in the block to top up, we can directly process the
366 // input buffer (assuming it contains sufficient data). This gives ~30%
367 // speedup on Chrome 14 and ~70% speedup on Firefox 6.0, but requires that
368 // the data is provided in large chunks (or in multiples of 64 bytes).
369 if (blockLength == 0) {
370 while (i <= lengthMinusBlock) {
371 this.compress_(bytes, i);
372 i += this.blockSize;
373 }
374 }
375
376 if (goog.isString(bytes)) {
377 while (i < opt_length) {
378 block[blockLength++] = bytes.charCodeAt(i++);
379 if (blockLength == this.blockSize) {
380 this.compress_(block);
381 blockLength = 0;
382 // Jump to the outer loop so we use the full-block optimization.
383 break;
384 }
385 }
386 } else {
387 while (i < opt_length) {
388 block[blockLength++] = bytes[i++];
389 if (blockLength == this.blockSize) {
390 this.compress_(block);
391 blockLength = 0;
392 // Jump to the outer loop so we use the full-block optimization.
393 break;
394 }
395 }
396 }
397 }
398
399 this.blockLength_ = blockLength;
400 this.totalLength_ += opt_length;
401 };
402
403
404 /** @override */
405 goog.crypt.Md5.prototype.digest = function() {
406 // This must accommodate at least 1 padding byte (0x80), 8 bytes of
407 // total bitlength, and must end at a 64-byte boundary.
408 var pad = new Array(
409 (this.blockLength_ < 56 ? this.blockSize : this.blockSize * 2) -
410 this.blockLength_);
411
412 // Add padding: 0x80 0x00*
413 pad[0] = 0x80;
414 for (var i = 1; i < pad.length - 8; ++i) {
415 pad[i] = 0;
416 }
417 // Add the total number of bits, little endian 64-bit integer.
418 var totalBits = this.totalLength_ * 8;
419 for (var i = pad.length - 8; i < pad.length; ++i) {
420 pad[i] = totalBits & 0xff;
421 totalBits /= 0x100; // Don't use bit-shifting here!
422 }
423 this.update(pad);
424
425 var digest = new Array(16);
426 var n = 0;
427 for (var i = 0; i < 4; ++i) {
428 for (var j = 0; j < 32; j += 8) {
429 digest[n++] = (this.chain_[i] >>> j) & 0xff;
430 }
431 }
432 return digest;
433 };