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