libiberty/md5.c

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