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