md5.c

00001 /* md5.c - Functions to compute MD5 message digest of files or memory blocks
00002    according to the definition of MD5 in RFC 1321 from April 1992.
00003    Copyright (C) 1995, 1996 Free Software Foundation, Inc.
00004    NOTE: The canonical source of this file is maintained with the GNU C
00005    Library.  Bugs can be reported to bug-glibc@prep.ai.mit.edu.
00006 
00007    This program is free software; you can redistribute it and/or modify it
00008    under the terms of the GNU General Public License as published by the
00009    Free Software Foundation; either version 2, or (at your option) any
00010    later version.
00011 
00012    This program is distributed in the hope that it will be useful,
00013    but WITHOUT ANY WARRANTY; without even the implied warranty of
00014    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015    GNU General Public License for more details.
00016 
00017    You should have received a copy of the GNU General Public License
00018    along with this program; if not, write to the Free Software Foundation,
00019    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
00020 
00021 /* Written by Ulrich Drepper <drepper@gnu.ai.mit.edu>, 1995.  */
00022 
00023 #ifdef HAVE_CONFIG_H
00024 # include <config.h>
00025 #endif
00026 
00027 #include <sys/types.h>
00028 
00029 #if STDC_HEADERS || defined _LIBC
00030 # include <stdlib.h>
00031 # include <string.h>
00032 #else
00033 # ifndef HAVE_MEMCPY
00034 #include <string.h>
00035 #  define memcpy(d, s, n) bcopy ((s), (d), (n))
00036 # endif
00037 #endif
00038 
00039 #include "md5.h"
00040 
00041 #ifdef _LIBC
00042 # include <endian.h>
00043 # if __BYTE_ORDER == __BIG_ENDIAN
00044 #  define WORDS_BIGENDIAN 1
00045 # endif
00046 #endif
00047 
00048 #ifdef WORDS_BIGENDIAN
00049 # define SWAP(n)                                                        \
00050     (((n) << 24) | (((n) & 0xff00) << 8) | (((n) >> 8) & 0xff00) | ((n) >> 24))
00051 #else
00052 # define SWAP(n) (n)
00053 #endif
00054 
00055 
00056 /* This array contains the bytes used to pad the buffer to the next
00057    64-byte boundary.  (RFC 1321, 3.1: Step 1)  */
00058 static const unsigned char fillbuf[64] = { 0x80, 0 /* , 0, 0, ...  */ };
00059 
00060 
00061 /* Initialize structure containing state of computation.
00062    (RFC 1321, 3.3: Step 3)  */
00063 void
00064 md5_init_ctx (ctx)
00065      struct md5_ctx *ctx;
00066 {
00067   ctx->A = 0x67452301;
00068   ctx->B = 0xefcdab89;
00069   ctx->C = 0x98badcfe;
00070   ctx->D = 0x10325476;
00071 
00072   ctx->total[0] = ctx->total[1] = 0;
00073   ctx->buflen = 0;
00074 }
00075 
00076 /* Put result from CTX in first 16 bytes following RESBUF.  The result
00077    must be in little endian byte order.
00078 
00079    IMPORTANT: On some systems it is required that RESBUF is correctly
00080    aligned for a 32 bits value.  */
00081 void *
00082 md5_read_ctx (ctx, resbuf)
00083      const struct md5_ctx *ctx;
00084      void *resbuf;
00085 {
00086   ((md5_uint32 *) resbuf)[0] = SWAP (ctx->A);
00087   ((md5_uint32 *) resbuf)[1] = SWAP (ctx->B);
00088   ((md5_uint32 *) resbuf)[2] = SWAP (ctx->C);
00089   ((md5_uint32 *) resbuf)[3] = SWAP (ctx->D);
00090 
00091   return resbuf;
00092 }
00093 
00094 /* Process the remaining bytes in the internal buffer and the usual
00095    prolog according to the standard and write the result to RESBUF.
00096 
00097    IMPORTANT: On some systems it is required that RESBUF is correctly
00098    aligned for a 32 bits value.  */
00099 void *
00100 md5_finish_ctx (ctx, resbuf)
00101      struct md5_ctx *ctx;
00102      void *resbuf;
00103 {
00104   /* Take yet unprocessed bytes into account.  */
00105   md5_uint32 bytes = ctx->buflen;
00106   size_t pad;
00107 
00108   /* Now count remaining bytes.  */
00109   ctx->total[0] += bytes;
00110   if (ctx->total[0] < bytes)
00111     ++ctx->total[1];
00112 
00113   pad = bytes >= 56 ? 64 + 56 - bytes : 56 - bytes;
00114   memcpy (&ctx->buffer[bytes], fillbuf, pad);
00115 
00116   /* Put the 64-bit file length in *bits* at the end of the buffer.  */
00117   *(md5_uint32 *) &ctx->buffer[bytes + pad] = SWAP (ctx->total[0] << 3);
00118   *(md5_uint32 *) &ctx->buffer[bytes + pad + 4] = SWAP ((ctx->total[1] << 3) |
00119                                                         (ctx->total[0] >> 29));
00120 
00121   /* Process last bytes.  */
00122   md5_process_block (ctx->buffer, bytes + pad + 8, ctx);
00123 
00124   return md5_read_ctx (ctx, resbuf);
00125 }
00126 
00127 /* Compute MD5 message digest for bytes read from STREAM.  The
00128    resulting message digest number will be written into the 16 bytes
00129    beginning at RESBLOCK.  */
00130 int
00131 md5_stream (stream, resblock)
00132      FILE *stream;
00133      void *resblock;
00134 {
00135   /* Important: BLOCKSIZE must be a multiple of 64.  */
00136 #define BLOCKSIZE 4096
00137   struct md5_ctx ctx;
00138   char buffer[BLOCKSIZE + 72];
00139   size_t sum;
00140 
00141   /* Initialize the computation context.  */
00142   md5_init_ctx (&ctx);
00143 
00144   /* Iterate over full file contents.  */
00145   while (1)
00146     {
00147       /* We read the file in blocks of BLOCKSIZE bytes.  One call of the
00148          computation function processes the whole buffer so that with the
00149          next round of the loop another block can be read.  */
00150       size_t n;
00151       sum = 0;
00152 
00153       /* Read block.  Take care for partial reads.  */
00154       do
00155         {
00156           n = fread (buffer + sum, 1, BLOCKSIZE - sum, stream);
00157 
00158           sum += n;
00159         }
00160       while (sum < BLOCKSIZE && n != 0);
00161       if (n == 0 && ferror (stream))
00162         return 1;
00163 
00164       /* If end of file is reached, end the loop.  */
00165       if (n == 0)
00166         break;
00167 
00168       /* Process buffer with BLOCKSIZE bytes.  Note that
00169                         BLOCKSIZE % 64 == 0
00170        */
00171       md5_process_block (buffer, BLOCKSIZE, &ctx);
00172     }
00173 
00174   /* Add the last bytes if necessary.  */
00175   if (sum > 0)
00176     md5_process_bytes (buffer, sum, &ctx);
00177 
00178   /* Construct result in desired memory.  */
00179   md5_finish_ctx (&ctx, resblock);
00180   return 0;
00181 }
00182 
00183 /* Compute MD5 message digest for LEN bytes beginning at BUFFER.  The
00184    result is always in little endian byte order, so that a byte-wise
00185    output yields to the wanted ASCII representation of the message
00186    digest.  */
00187 void *
00188 md5_buffer (buffer, len, resblock)
00189      const char *buffer;
00190      size_t len;
00191      void *resblock;
00192 {
00193   struct md5_ctx ctx;
00194 
00195   /* Initialize the computation context.  */
00196   md5_init_ctx (&ctx);
00197 
00198   /* Process whole buffer but last len % 64 bytes.  */
00199   md5_process_bytes (buffer, len, &ctx);
00200 
00201   /* Put result in desired memory area.  */
00202   return md5_finish_ctx (&ctx, resblock);
00203 }
00204 
00205 
00206 void
00207 md5_process_bytes (buffer, len, ctx)
00208      const void *buffer;
00209      size_t len;
00210      struct md5_ctx *ctx;
00211 {
00212 #define NUM_MD5_WORDS 1024
00213   size_t add = 0;
00214 
00215   /* When we already have some bits in our internal buffer concatenate
00216      both inputs first.  */
00217   if (ctx->buflen != 0)
00218     {
00219       size_t left_over = ctx->buflen;
00220 
00221       add = 128 - left_over > len ? len : 128 - left_over;
00222 
00223       memcpy (&ctx->buffer[left_over], buffer, add);
00224       ctx->buflen += add;
00225 
00226       if (left_over + add > 64)
00227         {
00228           md5_process_block (ctx->buffer, (left_over + add) & ~63, ctx);
00229           /* The regions in the following copy operation cannot overlap.  */
00230           memcpy (ctx->buffer, &ctx->buffer[(left_over + add) & ~63],
00231                   (left_over + add) & 63);
00232           ctx->buflen = (left_over + add) & 63;
00233         }
00234 
00235       buffer = (const char *) buffer + add;
00236       len -= add;
00237     }
00238 
00239   /* Process available complete blocks.  */
00240   if (len > 64)
00241     {
00242       if ((add & 3) == 0) /* buffer is still 32-bit aligned */
00243         {
00244           md5_process_block (buffer, len & ~63, ctx);
00245           buffer = (const char *) buffer + (len & ~63);
00246         }
00247       else                /* buffer is not 32-bit aligned */
00248         {
00249           md5_uint32 md5_buffer[NUM_MD5_WORDS];
00250           size_t num_bytes;
00251           size_t buf_bytes;
00252 
00253           num_bytes = len & ~63;
00254           while (num_bytes > 0)
00255             {
00256               buf_bytes = (num_bytes < sizeof(md5_buffer)) ?
00257                            num_bytes : sizeof(md5_buffer);
00258               memcpy (md5_buffer, buffer, buf_bytes);
00259               md5_process_block (md5_buffer, buf_bytes, ctx);
00260               num_bytes -= buf_bytes;
00261               buffer = (const char *) buffer + buf_bytes;
00262             }
00263         }
00264 
00265       len &= 63;
00266     }
00267 
00268   /* Move remaining bytes in internal buffer.  */
00269   if (len > 0)
00270     {
00271       memcpy (ctx->buffer, buffer, len);
00272       ctx->buflen = len;
00273     }
00274 }
00275 
00276 
00277 /* These are the four functions used in the four steps of the MD5 algorithm
00278    and defined in the RFC 1321.  The first function is a little bit optimized
00279    (as found in Colin Plumbs public domain implementation).  */
00280 /* #define FF(b, c, d) ((b & c) | (~b & d)) */
00281 #define FF(b, c, d) (d ^ (b & (c ^ d)))
00282 #define FG(b, c, d) FF (d, b, c)
00283 #define FH(b, c, d) (b ^ c ^ d)
00284 #define FI(b, c, d) (c ^ (b | ~d))
00285 
00286 /* Process LEN bytes of BUFFER, accumulating context into CTX.
00287    It is assumed that LEN % 64 == 0.  */
00288 
00289 void
00290 md5_process_block (buffer, len, ctx)
00291      const void *buffer;
00292      size_t len;
00293      struct md5_ctx *ctx;
00294 {
00295   md5_uint32 correct_words[16];
00296   const md5_uint32 *words = buffer;
00297   size_t nwords = len / sizeof (md5_uint32);
00298   const md5_uint32 *endp = words + nwords;
00299   md5_uint32 A = ctx->A;
00300   md5_uint32 B = ctx->B;
00301   md5_uint32 C = ctx->C;
00302   md5_uint32 D = ctx->D;
00303 
00304   /* First increment the byte count.  RFC 1321 specifies the possible
00305      length of the file up to 2^64 bits.  Here we only compute the
00306      number of bytes.  Do a double word increment.  */
00307   ctx->total[0] += len;
00308   if (ctx->total[0] < len)
00309     ++ctx->total[1];
00310 
00311   /* Process all bytes in the buffer with 64 bytes in each round of
00312      the loop.  */
00313   while (words < endp)
00314     {
00315       md5_uint32 *cwp = correct_words;
00316       md5_uint32 A_save = A;
00317       md5_uint32 B_save = B;
00318       md5_uint32 C_save = C;
00319       md5_uint32 D_save = D;
00320 
00321       /* First round: using the given function, the context and a constant
00322          the next context is computed.  Because the algorithms processing
00323          unit is a 32-bit word and it is determined to work on words in
00324          little endian byte order we perhaps have to change the byte order
00325          before the computation.  To reduce the work for the next steps
00326          we store the swapped words in the array CORRECT_WORDS.  */
00327 
00328 #define OP(a, b, c, d, s, T)                                            \
00329       do                                                                \
00330         {                                                               \
00331           a += FF (b, c, d) + (*cwp++ = SWAP (*words)) + T;             \
00332           ++words;                                                      \
00333           CYCLIC (a, s);                                                \
00334           a += b;                                                       \
00335         }                                                               \
00336       while (0)
00337 
00338       /* It is unfortunate that C does not provide an operator for
00339          cyclic rotation.  Hope the C compiler is smart enough.  */
00340 #define CYCLIC(w, s) (w = (w << s) | (w >> (32 - s)))
00341 
00342       /* Before we start, one word to the strange constants.
00343          They are defined in RFC 1321 as
00344 
00345          T[i] = (int) (4294967296.0 * fabs (sin (i))), i=1..64
00346        */
00347 
00348       /* Round 1.  */
00349       OP (A, B, C, D,  7, 0xd76aa478);
00350       OP (D, A, B, C, 12, 0xe8c7b756);
00351       OP (C, D, A, B, 17, 0x242070db);
00352       OP (B, C, D, A, 22, 0xc1bdceee);
00353       OP (A, B, C, D,  7, 0xf57c0faf);
00354       OP (D, A, B, C, 12, 0x4787c62a);
00355       OP (C, D, A, B, 17, 0xa8304613);
00356       OP (B, C, D, A, 22, 0xfd469501);
00357       OP (A, B, C, D,  7, 0x698098d8);
00358       OP (D, A, B, C, 12, 0x8b44f7af);
00359       OP (C, D, A, B, 17, 0xffff5bb1);
00360       OP (B, C, D, A, 22, 0x895cd7be);
00361       OP (A, B, C, D,  7, 0x6b901122);
00362       OP (D, A, B, C, 12, 0xfd987193);
00363       OP (C, D, A, B, 17, 0xa679438e);
00364       OP (B, C, D, A, 22, 0x49b40821);
00365 
00366       /* For the second to fourth round we have the possibly swapped words
00367          in CORRECT_WORDS.  Redefine the macro to take an additional first
00368          argument specifying the function to use.  */
00369 #undef OP
00370 #define OP(f, a, b, c, d, k, s, T)                                      \
00371       do                                                                \
00372         {                                                               \
00373           a += f (b, c, d) + correct_words[k] + T;                      \
00374           CYCLIC (a, s);                                                \
00375           a += b;                                                       \
00376         }                                                               \
00377       while (0)
00378 
00379       /* Round 2.  */
00380       OP (FG, A, B, C, D,  1,  5, 0xf61e2562);
00381       OP (FG, D, A, B, C,  6,  9, 0xc040b340);
00382       OP (FG, C, D, A, B, 11, 14, 0x265e5a51);
00383       OP (FG, B, C, D, A,  0, 20, 0xe9b6c7aa);
00384       OP (FG, A, B, C, D,  5,  5, 0xd62f105d);
00385       OP (FG, D, A, B, C, 10,  9, 0x02441453);
00386       OP (FG, C, D, A, B, 15, 14, 0xd8a1e681);
00387       OP (FG, B, C, D, A,  4, 20, 0xe7d3fbc8);
00388       OP (FG, A, B, C, D,  9,  5, 0x21e1cde6);
00389       OP (FG, D, A, B, C, 14,  9, 0xc33707d6);
00390       OP (FG, C, D, A, B,  3, 14, 0xf4d50d87);
00391       OP (FG, B, C, D, A,  8, 20, 0x455a14ed);
00392       OP (FG, A, B, C, D, 13,  5, 0xa9e3e905);
00393       OP (FG, D, A, B, C,  2,  9, 0xfcefa3f8);
00394       OP (FG, C, D, A, B,  7, 14, 0x676f02d9);
00395       OP (FG, B, C, D, A, 12, 20, 0x8d2a4c8a);
00396 
00397       /* Round 3.  */
00398       OP (FH, A, B, C, D,  5,  4, 0xfffa3942);
00399       OP (FH, D, A, B, C,  8, 11, 0x8771f681);
00400       OP (FH, C, D, A, B, 11, 16, 0x6d9d6122);
00401       OP (FH, B, C, D, A, 14, 23, 0xfde5380c);
00402       OP (FH, A, B, C, D,  1,  4, 0xa4beea44);
00403       OP (FH, D, A, B, C,  4, 11, 0x4bdecfa9);
00404       OP (FH, C, D, A, B,  7, 16, 0xf6bb4b60);
00405       OP (FH, B, C, D, A, 10, 23, 0xbebfbc70);
00406       OP (FH, A, B, C, D, 13,  4, 0x289b7ec6);
00407       OP (FH, D, A, B, C,  0, 11, 0xeaa127fa);
00408       OP (FH, C, D, A, B,  3, 16, 0xd4ef3085);
00409       OP (FH, B, C, D, A,  6, 23, 0x04881d05);
00410       OP (FH, A, B, C, D,  9,  4, 0xd9d4d039);
00411       OP (FH, D, A, B, C, 12, 11, 0xe6db99e5);
00412       OP (FH, C, D, A, B, 15, 16, 0x1fa27cf8);
00413       OP (FH, B, C, D, A,  2, 23, 0xc4ac5665);
00414 
00415       /* Round 4.  */
00416       OP (FI, A, B, C, D,  0,  6, 0xf4292244);
00417       OP (FI, D, A, B, C,  7, 10, 0x432aff97);
00418       OP (FI, C, D, A, B, 14, 15, 0xab9423a7);
00419       OP (FI, B, C, D, A,  5, 21, 0xfc93a039);
00420       OP (FI, A, B, C, D, 12,  6, 0x655b59c3);
00421       OP (FI, D, A, B, C,  3, 10, 0x8f0ccc92);
00422       OP (FI, C, D, A, B, 10, 15, 0xffeff47d);
00423       OP (FI, B, C, D, A,  1, 21, 0x85845dd1);
00424       OP (FI, A, B, C, D,  8,  6, 0x6fa87e4f);
00425       OP (FI, D, A, B, C, 15, 10, 0xfe2ce6e0);
00426       OP (FI, C, D, A, B,  6, 15, 0xa3014314);
00427       OP (FI, B, C, D, A, 13, 21, 0x4e0811a1);
00428       OP (FI, A, B, C, D,  4,  6, 0xf7537e82);
00429       OP (FI, D, A, B, C, 11, 10, 0xbd3af235);
00430       OP (FI, C, D, A, B,  2, 15, 0x2ad7d2bb);
00431       OP (FI, B, C, D, A,  9, 21, 0xeb86d391);
00432 
00433       /* Add the starting values of the context.  */
00434       A += A_save;
00435       B += B_save;
00436       C += C_save;
00437       D += D_save;
00438     }
00439 
00440   /* Put checksum in context given as argument.  */
00441   ctx->A = A;
00442   ctx->B = B;
00443   ctx->C = C;
00444   ctx->D = D;
00445 }

Generated on Fri May 12 18:00:32 2006 for QOF by  doxygen 1.4.4