1/* vi: set sw=4 ts=4: */
2/*
3 *  md5.c - Compute MD5 checksum of strings according to the
4 *          definition of MD5 in RFC 1321 from April 1992.
5 *
6 *  Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.
7 *
8 *  Copyright (C) 1995-1999 Free Software Foundation, Inc.
9 *  Copyright (C) 2001 Manuel Novoa III
10 *  Copyright (C) 2003 Glenn L. McGrath
11 *  Copyright (C) 2003 Erik Andersen
12 *
13 *  Licensed under the GPL v2 or later, see the file LICENSE in this tarball.
14 */
15
16#include "libbb.h"
17
18/* 0: fastest, 3: smallest */
19#if CONFIG_MD5_SIZE_VS_SPEED < 0
20# define MD5_SIZE_VS_SPEED 0
21#elif CONFIG_MD5_SIZE_VS_SPEED > 3
22# define MD5_SIZE_VS_SPEED 3
23#else
24# define MD5_SIZE_VS_SPEED CONFIG_MD5_SIZE_VS_SPEED
25#endif
26
27/* Initialize structure containing state of computation.
28 * (RFC 1321, 3.3: Step 3)
29 */
30void FAST_FUNC md5_begin(md5_ctx_t *ctx)
31{
32	ctx->A = 0x67452301;
33	ctx->B = 0xefcdab89;
34	ctx->C = 0x98badcfe;
35	ctx->D = 0x10325476;
36	ctx->total = 0;
37	ctx->buflen = 0;
38}
39
40/* These are the four functions used in the four steps of the MD5 algorithm
41 * and defined in the RFC 1321.  The first function is a little bit optimized
42 * (as found in Colin Plumbs public domain implementation).
43 * #define FF(b, c, d) ((b & c) | (~b & d))
44 */
45#define FF(b, c, d) (d ^ (b & (c ^ d)))
46#define FG(b, c, d) FF(d, b, c)
47#define FH(b, c, d) (b ^ c ^ d)
48#define FI(b, c, d) (c ^ (b | ~d))
49
50#define rotl32(w, s) (((w) << (s)) | ((w) >> (32 - (s))))
51
52/* Hash a single block, 64 bytes long and 4-byte aligned. */
53static void md5_hash_block(const void *buffer, md5_ctx_t *ctx)
54{
55	uint32_t correct_words[16];
56	const uint32_t *words = buffer;
57
58#if MD5_SIZE_VS_SPEED > 0
59	static const uint32_t C_array[] = {
60		/* round 1 */
61		0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee,
62		0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
63		0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
64		0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
65		/* round 2 */
66		0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa,
67		0xd62f105d, 0x2441453, 0xd8a1e681, 0xe7d3fbc8,
68		0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed,
69		0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
70		/* round 3 */
71		0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
72		0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
73		0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05,
74		0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
75		/* round 4 */
76		0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039,
77		0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
78		0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
79		0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391
80	};
81	static const char P_array[] ALIGN1 = {
82# if MD5_SIZE_VS_SPEED > 1
83		0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,	/* 1 */
84# endif
85		1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12,	/* 2 */
86		5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2,	/* 3 */
87		0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9	/* 4 */
88	};
89# if MD5_SIZE_VS_SPEED > 1
90	static const char S_array[] ALIGN1 = {
91		7, 12, 17, 22,
92		5, 9, 14, 20,
93		4, 11, 16, 23,
94		6, 10, 15, 21
95	};
96# endif	/* MD5_SIZE_VS_SPEED > 1 */
97#endif
98	uint32_t A = ctx->A;
99	uint32_t B = ctx->B;
100	uint32_t C = ctx->C;
101	uint32_t D = ctx->D;
102
103	/* Process all bytes in the buffer with 64 bytes in each round of
104	   the loop.  */
105	uint32_t *cwp = correct_words;
106	uint32_t A_save = A;
107	uint32_t B_save = B;
108	uint32_t C_save = C;
109	uint32_t D_save = D;
110
111#if MD5_SIZE_VS_SPEED > 1
112	const uint32_t *pc;
113	const char *pp;
114	const char *ps;
115	int i;
116	uint32_t temp;
117
118	for (i = 0; i < 16; i++)
119		cwp[i] = SWAP_LE32(words[i]);
120	words += 16;
121
122# if MD5_SIZE_VS_SPEED > 2
123	pc = C_array;
124	pp = P_array;
125	ps = S_array - 4;
126
127	for (i = 0; i < 64; i++) {
128		if ((i & 0x0f) == 0)
129			ps += 4;
130		temp = A;
131		switch (i >> 4) {
132		case 0:
133			temp += FF(B, C, D);
134			break;
135		case 1:
136			temp += FG(B, C, D);
137			break;
138		case 2:
139			temp += FH(B, C, D);
140			break;
141		case 3:
142			temp += FI(B, C, D);
143		}
144		temp += cwp[(int) (*pp++)] + *pc++;
145		temp = rotl32(temp, ps[i & 3]);
146		temp += B;
147		A = D;
148		D = C;
149		C = B;
150		B = temp;
151	}
152# else
153	pc = C_array;
154	pp = P_array;
155	ps = S_array;
156
157	for (i = 0; i < 16; i++) {
158		temp = A + FF(B, C, D) + cwp[(int) (*pp++)] + *pc++;
159		temp = rotl32(temp, ps[i & 3]);
160		temp += B;
161		A = D;
162		D = C;
163		C = B;
164		B = temp;
165	}
166	ps += 4;
167	for (i = 0; i < 16; i++) {
168		temp = A + FG(B, C, D) + cwp[(int) (*pp++)] + *pc++;
169		temp = rotl32(temp, ps[i & 3]);
170		temp += B;
171		A = D;
172		D = C;
173		C = B;
174		B = temp;
175	}
176	ps += 4;
177	for (i = 0; i < 16; i++) {
178		temp = A + FH(B, C, D) + cwp[(int) (*pp++)] + *pc++;
179		temp = rotl32(temp, ps[i & 3]);
180		temp += B;
181		A = D;
182		D = C;
183		C = B;
184		B = temp;
185	}
186	ps += 4;
187	for (i = 0; i < 16; i++) {
188		temp = A + FI(B, C, D) + cwp[(int) (*pp++)] + *pc++;
189		temp = rotl32(temp, ps[i & 3]);
190		temp += B;
191		A = D;
192		D = C;
193		C = B;
194		B = temp;
195	}
196
197# endif /* MD5_SIZE_VS_SPEED > 2 */
198#else
199	/* First round: using the given function, the context and a constant
200	   the next context is computed.  Because the algorithms processing
201	   unit is a 32-bit word and it is determined to work on words in
202	   little endian byte order we perhaps have to change the byte order
203	   before the computation.  To reduce the work for the next steps
204	   we store the swapped words in the array CORRECT_WORDS.  */
205# define OP(a, b, c, d, s, T) \
206	do { \
207		a += FF(b, c, d) + (*cwp++ = SWAP_LE32(*words)) + T; \
208		++words; \
209		a = rotl32(a, s); \
210		a += b; \
211	} while (0)
212
213	/* Before we start, one word to the strange constants.
214	   They are defined in RFC 1321 as
215	   T[i] = (int)(4294967296.0 * fabs(sin(i))), i=1..64
216	 */
217
218# if MD5_SIZE_VS_SPEED == 1
219	const uint32_t *pc;
220	const char *pp;
221	int i;
222# endif	/* MD5_SIZE_VS_SPEED */
223
224	/* Round 1.  */
225# if MD5_SIZE_VS_SPEED == 1
226	pc = C_array;
227	for (i = 0; i < 4; i++) {
228		OP(A, B, C, D, 7, *pc++);
229		OP(D, A, B, C, 12, *pc++);
230		OP(C, D, A, B, 17, *pc++);
231		OP(B, C, D, A, 22, *pc++);
232	}
233# else
234	OP(A, B, C, D, 7, 0xd76aa478);
235	OP(D, A, B, C, 12, 0xe8c7b756);
236	OP(C, D, A, B, 17, 0x242070db);
237	OP(B, C, D, A, 22, 0xc1bdceee);
238	OP(A, B, C, D, 7, 0xf57c0faf);
239	OP(D, A, B, C, 12, 0x4787c62a);
240	OP(C, D, A, B, 17, 0xa8304613);
241	OP(B, C, D, A, 22, 0xfd469501);
242	OP(A, B, C, D, 7, 0x698098d8);
243	OP(D, A, B, C, 12, 0x8b44f7af);
244	OP(C, D, A, B, 17, 0xffff5bb1);
245	OP(B, C, D, A, 22, 0x895cd7be);
246	OP(A, B, C, D, 7, 0x6b901122);
247	OP(D, A, B, C, 12, 0xfd987193);
248	OP(C, D, A, B, 17, 0xa679438e);
249	OP(B, C, D, A, 22, 0x49b40821);
250# endif /* MD5_SIZE_VS_SPEED == 1 */
251
252	/* For the second to fourth round we have the possibly swapped words
253	   in CORRECT_WORDS.  Redefine the macro to take an additional first
254	   argument specifying the function to use.  */
255# undef OP
256# define OP(f, a, b, c, d, k, s, T) \
257	do { \
258		a += f(b, c, d) + correct_words[k] + T; \
259		a = rotl32(a, s); \
260		a += b; \
261	} while (0)
262
263	/* Round 2.  */
264# if MD5_SIZE_VS_SPEED == 1
265	pp = P_array;
266	for (i = 0; i < 4; i++) {
267		OP(FG, A, B, C, D, (int) (*pp++), 5, *pc++);
268		OP(FG, D, A, B, C, (int) (*pp++), 9, *pc++);
269		OP(FG, C, D, A, B, (int) (*pp++), 14, *pc++);
270		OP(FG, B, C, D, A, (int) (*pp++), 20, *pc++);
271	}
272# else
273	OP(FG, A, B, C, D, 1, 5, 0xf61e2562);
274	OP(FG, D, A, B, C, 6, 9, 0xc040b340);
275	OP(FG, C, D, A, B, 11, 14, 0x265e5a51);
276	OP(FG, B, C, D, A, 0, 20, 0xe9b6c7aa);
277	OP(FG, A, B, C, D, 5, 5, 0xd62f105d);
278	OP(FG, D, A, B, C, 10, 9, 0x02441453);
279	OP(FG, C, D, A, B, 15, 14, 0xd8a1e681);
280	OP(FG, B, C, D, A, 4, 20, 0xe7d3fbc8);
281	OP(FG, A, B, C, D, 9, 5, 0x21e1cde6);
282	OP(FG, D, A, B, C, 14, 9, 0xc33707d6);
283	OP(FG, C, D, A, B, 3, 14, 0xf4d50d87);
284	OP(FG, B, C, D, A, 8, 20, 0x455a14ed);
285	OP(FG, A, B, C, D, 13, 5, 0xa9e3e905);
286	OP(FG, D, A, B, C, 2, 9, 0xfcefa3f8);
287	OP(FG, C, D, A, B, 7, 14, 0x676f02d9);
288	OP(FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
289# endif /* MD5_SIZE_VS_SPEED == 1 */
290
291	/* Round 3.  */
292# if MD5_SIZE_VS_SPEED == 1
293	for (i = 0; i < 4; i++) {
294		OP(FH, A, B, C, D, (int) (*pp++), 4, *pc++);
295		OP(FH, D, A, B, C, (int) (*pp++), 11, *pc++);
296		OP(FH, C, D, A, B, (int) (*pp++), 16, *pc++);
297		OP(FH, B, C, D, A, (int) (*pp++), 23, *pc++);
298	}
299# else
300	OP(FH, A, B, C, D, 5, 4, 0xfffa3942);
301	OP(FH, D, A, B, C, 8, 11, 0x8771f681);
302	OP(FH, C, D, A, B, 11, 16, 0x6d9d6122);
303	OP(FH, B, C, D, A, 14, 23, 0xfde5380c);
304	OP(FH, A, B, C, D, 1, 4, 0xa4beea44);
305	OP(FH, D, A, B, C, 4, 11, 0x4bdecfa9);
306	OP(FH, C, D, A, B, 7, 16, 0xf6bb4b60);
307	OP(FH, B, C, D, A, 10, 23, 0xbebfbc70);
308	OP(FH, A, B, C, D, 13, 4, 0x289b7ec6);
309	OP(FH, D, A, B, C, 0, 11, 0xeaa127fa);
310	OP(FH, C, D, A, B, 3, 16, 0xd4ef3085);
311	OP(FH, B, C, D, A, 6, 23, 0x04881d05);
312	OP(FH, A, B, C, D, 9, 4, 0xd9d4d039);
313	OP(FH, D, A, B, C, 12, 11, 0xe6db99e5);
314	OP(FH, C, D, A, B, 15, 16, 0x1fa27cf8);
315	OP(FH, B, C, D, A, 2, 23, 0xc4ac5665);
316# endif /* MD5_SIZE_VS_SPEED == 1 */
317
318	/* Round 4.  */
319# if MD5_SIZE_VS_SPEED == 1
320	for (i = 0; i < 4; i++) {
321		OP(FI, A, B, C, D, (int) (*pp++), 6, *pc++);
322		OP(FI, D, A, B, C, (int) (*pp++), 10, *pc++);
323		OP(FI, C, D, A, B, (int) (*pp++), 15, *pc++);
324		OP(FI, B, C, D, A, (int) (*pp++), 21, *pc++);
325	}
326# else
327	OP(FI, A, B, C, D, 0, 6, 0xf4292244);
328	OP(FI, D, A, B, C, 7, 10, 0x432aff97);
329	OP(FI, C, D, A, B, 14, 15, 0xab9423a7);
330	OP(FI, B, C, D, A, 5, 21, 0xfc93a039);
331	OP(FI, A, B, C, D, 12, 6, 0x655b59c3);
332	OP(FI, D, A, B, C, 3, 10, 0x8f0ccc92);
333	OP(FI, C, D, A, B, 10, 15, 0xffeff47d);
334	OP(FI, B, C, D, A, 1, 21, 0x85845dd1);
335	OP(FI, A, B, C, D, 8, 6, 0x6fa87e4f);
336	OP(FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
337	OP(FI, C, D, A, B, 6, 15, 0xa3014314);
338	OP(FI, B, C, D, A, 13, 21, 0x4e0811a1);
339	OP(FI, A, B, C, D, 4, 6, 0xf7537e82);
340	OP(FI, D, A, B, C, 11, 10, 0xbd3af235);
341	OP(FI, C, D, A, B, 2, 15, 0x2ad7d2bb);
342	OP(FI, B, C, D, A, 9, 21, 0xeb86d391);
343# endif	/* MD5_SIZE_VS_SPEED == 1 */
344#endif	/* MD5_SIZE_VS_SPEED > 1 */
345
346	/* Add the starting values of the context.  */
347	A += A_save;
348	B += B_save;
349	C += C_save;
350	D += D_save;
351
352	/* Put checksum in context given as argument.  */
353	ctx->A = A;
354	ctx->B = B;
355	ctx->C = C;
356	ctx->D = D;
357}
358
359/* Feed data through a temporary buffer to call md5_hash_aligned_block()
360 * with chunks of data that are 4-byte aligned and a multiple of 64 bytes.
361 * This function's internal buffer remembers previous data until it has 64
362 * bytes worth to pass on.  Call md5_end() to flush this buffer. */
363void FAST_FUNC md5_hash(const void *buffer, size_t len, md5_ctx_t *ctx)
364{
365	char *buf = (char *)buffer;
366
367	/* RFC 1321 specifies the possible length of the file up to 2^64 bits,
368	 * Here we only track the number of bytes.  */
369	ctx->total += len;
370
371	/* Process all input. */
372	while (len) {
373		unsigned i = 64 - ctx->buflen;
374
375		/* Copy data into aligned buffer. */
376		if (i > len)
377			i = len;
378		memcpy(ctx->buffer + ctx->buflen, buf, i);
379		len -= i;
380		ctx->buflen += i;
381		buf += i;
382
383		/* When buffer fills up, process it. */
384		if (ctx->buflen == 64) {
385			md5_hash_block(ctx->buffer, ctx);
386			ctx->buflen = 0;
387		}
388	}
389}
390
391/* Process the remaining bytes in the buffer and put result from CTX
392 * in first 16 bytes following RESBUF.  The result is always in little
393 * endian byte order, so that a byte-wise output yields to the wanted
394 * ASCII representation of the message digest.
395 */
396void FAST_FUNC md5_end(void *resbuf, md5_ctx_t *ctx)
397{
398	char *buf = ctx->buffer;
399	int i;
400
401	/* Pad data to block size.  */
402	buf[ctx->buflen++] = 0x80;
403	memset(buf + ctx->buflen, 0, 128 - ctx->buflen);
404
405	/* Put the 64-bit file length in *bits* at the end of the buffer.  */
406	ctx->total <<= 3;
407	if (ctx->buflen > 56)
408		buf += 64;
409	for (i = 0; i < 8; i++)
410		buf[56 + i] = ctx->total >> (i*8);
411
412	/* Process last bytes.  */
413	if (buf != ctx->buffer)
414		md5_hash_block(ctx->buffer, ctx);
415	md5_hash_block(buf, ctx);
416
417	/* The MD5 result is in little endian byte order.
418	 * We (ab)use the fact that A-D are consecutive in memory.
419	 */
420#if BB_BIG_ENDIAN
421	ctx->A = SWAP_LE32(ctx->A);
422	ctx->B = SWAP_LE32(ctx->B);
423	ctx->C = SWAP_LE32(ctx->C);
424	ctx->D = SWAP_LE32(ctx->D);
425#endif
426	memcpy(resbuf, &ctx->A, sizeof(ctx->A) * 4);
427}
428