1/* Functions to compute MD5 message digest of files or memory blocks.
2   according to the definition of MD5 in RFC 1321 from April 1992.
3   Copyright (C) 1995,1996,1997,1999,2000,2001,2005,2006,2008
4	Free Software Foundation, Inc.
5   This file is part of the GNU C Library.
6
7   This program is free software; you can redistribute it and/or modify it
8   under the terms of the GNU General Public License as published by the
9   Free Software Foundation; either version 3, or (at your option) any
10   later version.
11
12   This program is distributed in the hope that it will be useful,
13   but WITHOUT ANY WARRANTY; without even the implied warranty of
14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15   GNU General Public License for more details.
16
17   You should have received a copy of the GNU General Public License
18   along with this program; if not, write to the Free Software Foundation,
19   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
20
21/* Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.  */
22
23#include <config.h>
24
25#include "md5.h"
26
27#include <stddef.h>
28#include <stdlib.h>
29#include <string.h>
30#include <sys/types.h>
31
32#if USE_UNLOCKED_IO
33# include "unlocked-io.h"
34#endif
35
36#ifdef _LIBC
37# include <endian.h>
38# if __BYTE_ORDER == __BIG_ENDIAN
39#  define WORDS_BIGENDIAN 1
40# endif
41/* We need to keep the namespace clean so define the MD5 function
42   protected using leading __ .  */
43# define md5_init_ctx __md5_init_ctx
44# define md5_process_block __md5_process_block
45# define md5_process_bytes __md5_process_bytes
46# define md5_finish_ctx __md5_finish_ctx
47# define md5_read_ctx __md5_read_ctx
48# define md5_stream __md5_stream
49# define md5_buffer __md5_buffer
50#endif
51
52#ifdef WORDS_BIGENDIAN
53# define SWAP(n)							\
54    (((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24))
55#else
56# define SWAP(n) (n)
57#endif
58
59#define BLOCKSIZE 4096
60#if BLOCKSIZE % 64 != 0
61# error "invalid BLOCKSIZE"
62#endif
63
64/* This array contains the bytes used to pad the buffer to the next
65   64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
66static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
67
68
69/* Initialize structure containing state of computation.
70   (RFC 1321, 3.3: Step 3)  */
71void
72md5_init_ctx (struct md5_ctx *ctx)
73{
74  ctx->A = 0x67452301;
75  ctx->B = 0xefcdab89;
76  ctx->C = 0x98badcfe;
77  ctx->D = 0x10325476;
78
79  ctx->total[0] = ctx->total[1] = 0;
80  ctx->buflen = 0;
81}
82
83/* Copy the 4 byte value from v into the memory location pointed to by *cp,
84   If your architecture allows unaligned access this is equivalent to
85   * (uint32_t *) cp = v  */
86static inline void
87set_uint32 (char *cp, uint32_t v)
88{
89  memcpy (cp, &v, sizeof v);
90}
91
92/* Put result from CTX in first 16 bytes following RESBUF.  The result
93   must be in little endian byte order.  */
94void *
95md5_read_ctx (const struct md5_ctx *ctx, void *resbuf)
96{
97  char *r = resbuf;
98  set_uint32 (r + 0 * sizeof ctx->A, SWAP (ctx->A));
99  set_uint32 (r + 1 * sizeof ctx->B, SWAP (ctx->B));
100  set_uint32 (r + 2 * sizeof ctx->C, SWAP (ctx->C));
101  set_uint32 (r + 3 * sizeof ctx->D, SWAP (ctx->D));
102
103  return resbuf;
104}
105
106/* Process the remaining bytes in the internal buffer and the usual
107   prolog according to the standard and write the result to RESBUF.  */
108void *
109md5_finish_ctx (struct md5_ctx *ctx, void *resbuf)
110{
111  /* Take yet unprocessed bytes into account.  */
112  uint32_t bytes = ctx->buflen;
113  size_t size = (bytes < 56) ? 64 / 4 : 64 * 2 / 4;
114
115  /* Now count remaining bytes.  */
116  ctx->total[0] += bytes;
117  if (ctx->total[0] < bytes)
118    ++ctx->total[1];
119
120  /* Put the 64-bit file length in *bits* at the end of the buffer.  */
121  ctx->buffer[size - 2] = SWAP (ctx->total[0] << 3);
122  ctx->buffer[size - 1] = SWAP ((ctx->total[1] << 3) | (ctx->total[0] >> 29));
123
124  memcpy (&((char *) ctx->buffer)[bytes], fillbuf, (size - 2) * 4 - bytes);
125
126  /* Process last bytes.  */
127  md5_process_block (ctx->buffer, size * 4, ctx);
128
129  return md5_read_ctx (ctx, resbuf);
130}
131
132/* Compute MD5 message digest for bytes read from STREAM.  The
133   resulting message digest number will be written into the 16 bytes
134   beginning at RESBLOCK.  */
135int
136md5_stream (FILE *stream, void *resblock)
137{
138  struct md5_ctx ctx;
139  char buffer[BLOCKSIZE + 72];
140  size_t sum;
141
142  /* Initialize the computation context.  */
143  md5_init_ctx (&ctx);
144
145  /* Iterate over full file contents.  */
146  while (1)
147    {
148      /* We read the file in blocks of BLOCKSIZE bytes.  One call of the
149         computation function processes the whole buffer so that with the
150         next round of the loop another block can be read.  */
151      size_t n;
152      sum = 0;
153
154      /* Read block.  Take care for partial reads.  */
155      while (1)
156	{
157	  n = fread (buffer + sum, 1, BLOCKSIZE - sum, stream);
158
159	  sum += n;
160
161	  if (sum == BLOCKSIZE)
162	    break;
163
164	  if (n == 0)
165	    {
166	      /* Check for the error flag IFF N == 0, so that we don't
167	         exit the loop after a partial read due to e.g., EAGAIN
168	         or EWOULDBLOCK.  */
169	      if (ferror (stream))
170		return 1;
171	      goto process_partial_block;
172	    }
173
174	  /* We've read at least one byte, so ignore errors.  But always
175	     check for EOF, since feof may be true even though N > 0.
176	     Otherwise, we could end up calling fread after EOF.  */
177	  if (feof (stream))
178	    goto process_partial_block;
179	}
180
181      /* Process buffer with BLOCKSIZE bytes.  Note that
182         BLOCKSIZE % 64 == 0
183       */
184      md5_process_block (buffer, BLOCKSIZE, &ctx);
185    }
186
187process_partial_block:
188
189  /* Process any remaining bytes.  */
190  if (sum > 0)
191    md5_process_bytes (buffer, sum, &ctx);
192
193  /* Construct result in desired memory.  */
194  md5_finish_ctx (&ctx, resblock);
195  return 0;
196}
197
198/* Compute MD5 message digest for LEN bytes beginning at BUFFER.  The
199   result is always in little endian byte order, so that a byte-wise
200   output yields to the wanted ASCII representation of the message
201   digest.  */
202void *
203md5_buffer (const char *buffer, size_t len, void *resblock)
204{
205  struct md5_ctx ctx;
206
207  /* Initialize the computation context.  */
208  md5_init_ctx (&ctx);
209
210  /* Process whole buffer but last len % 64 bytes.  */
211  md5_process_bytes (buffer, len, &ctx);
212
213  /* Put result in desired memory area.  */
214  return md5_finish_ctx (&ctx, resblock);
215}
216
217
218void
219md5_process_bytes (const void *buffer, size_t len, struct md5_ctx *ctx)
220{
221  /* When we already have some bits in our internal buffer concatenate
222     both inputs first.  */
223  if (ctx->buflen != 0)
224    {
225      size_t left_over = ctx->buflen;
226      size_t add = 128 - left_over > len ? len : 128 - left_over;
227
228      memcpy (&((char *) ctx->buffer)[left_over], buffer, add);
229      ctx->buflen += add;
230
231      if (ctx->buflen > 64)
232	{
233	  md5_process_block (ctx->buffer, ctx->buflen & ~63, ctx);
234
235	  ctx->buflen &= 63;
236	  /* The regions in the following copy operation cannot overlap.  */
237	  memcpy (ctx->buffer,
238		  &((char *) ctx->buffer)[(left_over + add) & ~63],
239		  ctx->buflen);
240	}
241
242      buffer = (const char *) buffer + add;
243      len -= add;
244    }
245
246  /* Process available complete blocks.  */
247  if (len >= 64)
248    {
249#if !_STRING_ARCH_unaligned
250# define alignof(type) offsetof (struct { char c; type x; }, x)
251# define UNALIGNED_P(p) (((size_t) p) % alignof (uint32_t) != 0)
252      if (UNALIGNED_P (buffer))
253	while (len > 64)
254	  {
255	    md5_process_block (memcpy (ctx->buffer, buffer, 64), 64, ctx);
256	    buffer = (const char *) buffer + 64;
257	    len -= 64;
258	  }
259      else
260#endif
261	{
262	  md5_process_block (buffer, len & ~63, ctx);
263	  buffer = (const char *) buffer + (len & ~63);
264	  len &= 63;
265	}
266    }
267
268  /* Move remaining bytes in internal buffer.  */
269  if (len > 0)
270    {
271      size_t left_over = ctx->buflen;
272
273      memcpy (&((char *) ctx->buffer)[left_over], buffer, len);
274      left_over += len;
275      if (left_over >= 64)
276	{
277	  md5_process_block (ctx->buffer, 64, ctx);
278	  left_over -= 64;
279	  memcpy (ctx->buffer, &ctx->buffer[16], left_over);
280	}
281      ctx->buflen = left_over;
282    }
283}
284
285
286/* These are the four functions used in the four steps of the MD5 algorithm
287   and defined in the RFC 1321.  The first function is a little bit optimized
288   (as found in Colin Plumbs public domain implementation).  */
289/* #define FF(b, c, d) ((b & c) | (~b & d)) */
290#define FF(b, c, d) (d ^ (b & (c ^ d)))
291#define FG(b, c, d) FF (d, b, c)
292#define FH(b, c, d) (b ^ c ^ d)
293#define FI(b, c, d) (c ^ (b | ~d))
294
295/* Process LEN bytes of BUFFER, accumulating context into CTX.
296   It is assumed that LEN % 64 == 0.  */
297
298void
299md5_process_block (const void *buffer, size_t len, struct md5_ctx *ctx)
300{
301  uint32_t correct_words[16];
302  const uint32_t *words = buffer;
303  size_t nwords = len / sizeof (uint32_t);
304  const uint32_t *endp = words + nwords;
305  uint32_t A = ctx->A;
306  uint32_t B = ctx->B;
307  uint32_t C = ctx->C;
308  uint32_t D = ctx->D;
309
310  /* First increment the byte count.  RFC 1321 specifies the possible
311     length of the file up to 2^64 bits.  Here we only compute the
312     number of bytes.  Do a double word increment.  */
313  ctx->total[0] += len;
314  if (ctx->total[0] < len)
315    ++ctx->total[1];
316
317  /* Process all bytes in the buffer with 64 bytes in each round of
318     the loop.  */
319  while (words < endp)
320    {
321      uint32_t *cwp = correct_words;
322      uint32_t A_save = A;
323      uint32_t B_save = B;
324      uint32_t C_save = C;
325      uint32_t D_save = D;
326
327      /* First round: using the given function, the context and a constant
328         the next context is computed.  Because the algorithms processing
329         unit is a 32-bit word and it is determined to work on words in
330         little endian byte order we perhaps have to change the byte order
331         before the computation.  To reduce the work for the next steps
332         we store the swapped words in the array CORRECT_WORDS.  */
333
334#define OP(a, b, c, d, s, T)						\
335      do								\
336        {								\
337	  a += FF (b, c, d) + (*cwp++ = SWAP (*words)) + T;		\
338	  ++words;							\
339	  CYCLIC (a, s);						\
340	  a += b;							\
341        }								\
342      while (0)
343
344      /* It is unfortunate that C does not provide an operator for
345         cyclic rotation.  Hope the C compiler is smart enough.  */
346#define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
347
348      /* Before we start, one word to the strange constants.
349         They are defined in RFC 1321 as
350
351         T[i] = (int) (4294967296.0 * fabs (sin (i))), i=1..64
352
353         Here is an equivalent invocation using Perl:
354
355         perl -e 'foreach(1..64){printf "0x%08x\n", int (4294967296 * abs (sin $_))}'
356       */
357
358      /* Round 1.  */
359      OP (A, B, C, D, 7, 0xd76aa478);
360      OP (D, A, B, C, 12, 0xe8c7b756);
361      OP (C, D, A, B, 17, 0x242070db);
362      OP (B, C, D, A, 22, 0xc1bdceee);
363      OP (A, B, C, D, 7, 0xf57c0faf);
364      OP (D, A, B, C, 12, 0x4787c62a);
365      OP (C, D, A, B, 17, 0xa8304613);
366      OP (B, C, D, A, 22, 0xfd469501);
367      OP (A, B, C, D, 7, 0x698098d8);
368      OP (D, A, B, C, 12, 0x8b44f7af);
369      OP (C, D, A, B, 17, 0xffff5bb1);
370      OP (B, C, D, A, 22, 0x895cd7be);
371      OP (A, B, C, D, 7, 0x6b901122);
372      OP (D, A, B, C, 12, 0xfd987193);
373      OP (C, D, A, B, 17, 0xa679438e);
374      OP (B, C, D, A, 22, 0x49b40821);
375
376      /* For the second to fourth round we have the possibly swapped words
377         in CORRECT_WORDS.  Redefine the macro to take an additional first
378         argument specifying the function to use.  */
379#undef OP
380#define OP(f, a, b, c, d, k, s, T)					\
381      do								\
382	{								\
383	  a += f (b, c, d) + correct_words[k] + T;			\
384	  CYCLIC (a, s);						\
385	  a += b;							\
386	}								\
387      while (0)
388
389      /* Round 2.  */
390      OP (FG, A, B, C, D, 1, 5, 0xf61e2562);
391      OP (FG, D, A, B, C, 6, 9, 0xc040b340);
392      OP (FG, C, D, A, B, 11, 14, 0x265e5a51);
393      OP (FG, B, C, D, A, 0, 20, 0xe9b6c7aa);
394      OP (FG, A, B, C, D, 5, 5, 0xd62f105d);
395      OP (FG, D, A, B, C, 10, 9, 0x02441453);
396      OP (FG, C, D, A, B, 15, 14, 0xd8a1e681);
397      OP (FG, B, C, D, A, 4, 20, 0xe7d3fbc8);
398      OP (FG, A, B, C, D, 9, 5, 0x21e1cde6);
399      OP (FG, D, A, B, C, 14, 9, 0xc33707d6);
400      OP (FG, C, D, A, B, 3, 14, 0xf4d50d87);
401      OP (FG, B, C, D, A, 8, 20, 0x455a14ed);
402      OP (FG, A, B, C, D, 13, 5, 0xa9e3e905);
403      OP (FG, D, A, B, C, 2, 9, 0xfcefa3f8);
404      OP (FG, C, D, A, B, 7, 14, 0x676f02d9);
405      OP (FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
406
407      /* Round 3.  */
408      OP (FH, A, B, C, D, 5, 4, 0xfffa3942);
409      OP (FH, D, A, B, C, 8, 11, 0x8771f681);
410      OP (FH, C, D, A, B, 11, 16, 0x6d9d6122);
411      OP (FH, B, C, D, A, 14, 23, 0xfde5380c);
412      OP (FH, A, B, C, D, 1, 4, 0xa4beea44);
413      OP (FH, D, A, B, C, 4, 11, 0x4bdecfa9);
414      OP (FH, C, D, A, B, 7, 16, 0xf6bb4b60);
415      OP (FH, B, C, D, A, 10, 23, 0xbebfbc70);
416      OP (FH, A, B, C, D, 13, 4, 0x289b7ec6);
417      OP (FH, D, A, B, C, 0, 11, 0xeaa127fa);
418      OP (FH, C, D, A, B, 3, 16, 0xd4ef3085);
419      OP (FH, B, C, D, A, 6, 23, 0x04881d05);
420      OP (FH, A, B, C, D, 9, 4, 0xd9d4d039);
421      OP (FH, D, A, B, C, 12, 11, 0xe6db99e5);
422      OP (FH, C, D, A, B, 15, 16, 0x1fa27cf8);
423      OP (FH, B, C, D, A, 2, 23, 0xc4ac5665);
424
425      /* Round 4.  */
426      OP (FI, A, B, C, D, 0, 6, 0xf4292244);
427      OP (FI, D, A, B, C, 7, 10, 0x432aff97);
428      OP (FI, C, D, A, B, 14, 15, 0xab9423a7);
429      OP (FI, B, C, D, A, 5, 21, 0xfc93a039);
430      OP (FI, A, B, C, D, 12, 6, 0x655b59c3);
431      OP (FI, D, A, B, C, 3, 10, 0x8f0ccc92);
432      OP (FI, C, D, A, B, 10, 15, 0xffeff47d);
433      OP (FI, B, C, D, A, 1, 21, 0x85845dd1);
434      OP (FI, A, B, C, D, 8, 6, 0x6fa87e4f);
435      OP (FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
436      OP (FI, C, D, A, B, 6, 15, 0xa3014314);
437      OP (FI, B, C, D, A, 13, 21, 0x4e0811a1);
438      OP (FI, A, B, C, D, 4, 6, 0xf7537e82);
439      OP (FI, D, A, B, C, 11, 10, 0xbd3af235);
440      OP (FI, C, D, A, B, 2, 15, 0x2ad7d2bb);
441      OP (FI, B, C, D, A, 9, 21, 0xeb86d391);
442
443      /* Add the starting values of the context.  */
444      A += A_save;
445      B += B_save;
446      C += C_save;
447      D += D_save;
448    }
449
450  /* Put checksum in context given as argument.  */
451  ctx->A = A;
452  ctx->B = B;
453  ctx->C = C;
454  ctx->D = D;
455}
456