2016/md5.c

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