1/*
2 * This code is derived from (original license follows):
3 *
4 * This is an OpenSSL-compatible implementation of the RSA Data Security, Inc.
5 * MD5 Message-Digest Algorithm (RFC 1321).
6 *
7 * Homepage:
8 * http://openwall.info/wiki/people/solar/software/public-domain-source-code/md5
9 *
10 * Author:
11 * Alexander Peslyak, better known as Solar Designer <solar at openwall.com>
12 *
13 * This software was written by Alexander Peslyak in 2001.  No copyright is
14 * claimed, and the software is hereby placed in the public domain.
15 * In case this attempt to disclaim copyright and place the software in the
16 * public domain is deemed null and void, then the software is
17 * Copyright (c) 2001 Alexander Peslyak and it is hereby released to the
18 * general public under the following terms:
19 *
20 * Redistribution and use in source and binary forms, with or without
21 * modification, are permitted.
22 *
23 * There's ABSOLUTELY NO WARRANTY, express or implied.
24 *
25 * (This is a heavily cut-down "BSD license".)
26 *
27 * This differs from Colin Plumb's older public domain implementation in that
28 * no exactly 32-bit integer data type is required (any 32-bit or wider
29 * unsigned integer data type will do), there's no compile-time endianness
30 * configuration, and the function prototypes match OpenSSL's.  No code from
31 * Colin Plumb's implementation has been reused; this comment merely compares
32 * the properties of the two independent implementations.
33 *
34 * The primary goals of this implementation are portability and ease of use.
35 * It is meant to be fast, but not as fast as possible.  Some known
36 * optimizations are not included to reduce source code size and avoid
37 * compile-time configuration.
38 */
39
40#include "llvm/ADT/ArrayRef.h"
41#include "llvm/Support/Format.h"
42#include "llvm/Support/MD5.h"
43#include "llvm/Support/raw_ostream.h"
44#include <cstring>
45
46// The basic MD5 functions.
47
48// F and G are optimized compared to their RFC 1321 definitions for
49// architectures that lack an AND-NOT instruction, just like in Colin Plumb's
50// implementation.
51#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
52#define G(x, y, z) ((y) ^ ((z) & ((x) ^ (y))))
53#define H(x, y, z) ((x) ^ (y) ^ (z))
54#define I(x, y, z) ((y) ^ ((x) | ~(z)))
55
56// The MD5 transformation for all four rounds.
57#define STEP(f, a, b, c, d, x, t, s)                                           \
58  (a) += f((b), (c), (d)) + (x) + (t);                                         \
59  (a) = (((a) << (s)) | (((a) & 0xffffffff) >> (32 - (s))));                   \
60  (a) += (b);
61
62// SET reads 4 input bytes in little-endian byte order and stores them
63// in a properly aligned word in host byte order.
64#define SET(n)                                                                 \
65  (block[(n)] =                                                                \
66       (MD5_u32plus) ptr[(n) * 4] | ((MD5_u32plus) ptr[(n) * 4 + 1] << 8) |    \
67       ((MD5_u32plus) ptr[(n) * 4 + 2] << 16) |                                \
68       ((MD5_u32plus) ptr[(n) * 4 + 3] << 24))
69#define GET(n) (block[(n)])
70
71namespace llvm {
72
73/// \brief This processes one or more 64-byte data blocks, but does NOT update
74///the bit counters.  There are no alignment requirements.
75const uint8_t *MD5::body(ArrayRef<uint8_t> Data) {
76  const uint8_t *ptr;
77  MD5_u32plus a, b, c, d;
78  MD5_u32plus saved_a, saved_b, saved_c, saved_d;
79  unsigned long Size = Data.size();
80
81  ptr = Data.data();
82
83  a = this->a;
84  b = this->b;
85  c = this->c;
86  d = this->d;
87
88  do {
89    saved_a = a;
90    saved_b = b;
91    saved_c = c;
92    saved_d = d;
93
94    // Round 1
95    STEP(F, a, b, c, d, SET(0), 0xd76aa478, 7)
96    STEP(F, d, a, b, c, SET(1), 0xe8c7b756, 12)
97    STEP(F, c, d, a, b, SET(2), 0x242070db, 17)
98    STEP(F, b, c, d, a, SET(3), 0xc1bdceee, 22)
99    STEP(F, a, b, c, d, SET(4), 0xf57c0faf, 7)
100    STEP(F, d, a, b, c, SET(5), 0x4787c62a, 12)
101    STEP(F, c, d, a, b, SET(6), 0xa8304613, 17)
102    STEP(F, b, c, d, a, SET(7), 0xfd469501, 22)
103    STEP(F, a, b, c, d, SET(8), 0x698098d8, 7)
104    STEP(F, d, a, b, c, SET(9), 0x8b44f7af, 12)
105    STEP(F, c, d, a, b, SET(10), 0xffff5bb1, 17)
106    STEP(F, b, c, d, a, SET(11), 0x895cd7be, 22)
107    STEP(F, a, b, c, d, SET(12), 0x6b901122, 7)
108    STEP(F, d, a, b, c, SET(13), 0xfd987193, 12)
109    STEP(F, c, d, a, b, SET(14), 0xa679438e, 17)
110    STEP(F, b, c, d, a, SET(15), 0x49b40821, 22)
111
112    // Round 2
113    STEP(G, a, b, c, d, GET(1), 0xf61e2562, 5)
114    STEP(G, d, a, b, c, GET(6), 0xc040b340, 9)
115    STEP(G, c, d, a, b, GET(11), 0x265e5a51, 14)
116    STEP(G, b, c, d, a, GET(0), 0xe9b6c7aa, 20)
117    STEP(G, a, b, c, d, GET(5), 0xd62f105d, 5)
118    STEP(G, d, a, b, c, GET(10), 0x02441453, 9)
119    STEP(G, c, d, a, b, GET(15), 0xd8a1e681, 14)
120    STEP(G, b, c, d, a, GET(4), 0xe7d3fbc8, 20)
121    STEP(G, a, b, c, d, GET(9), 0x21e1cde6, 5)
122    STEP(G, d, a, b, c, GET(14), 0xc33707d6, 9)
123    STEP(G, c, d, a, b, GET(3), 0xf4d50d87, 14)
124    STEP(G, b, c, d, a, GET(8), 0x455a14ed, 20)
125    STEP(G, a, b, c, d, GET(13), 0xa9e3e905, 5)
126    STEP(G, d, a, b, c, GET(2), 0xfcefa3f8, 9)
127    STEP(G, c, d, a, b, GET(7), 0x676f02d9, 14)
128    STEP(G, b, c, d, a, GET(12), 0x8d2a4c8a, 20)
129
130    // Round 3
131    STEP(H, a, b, c, d, GET(5), 0xfffa3942, 4)
132    STEP(H, d, a, b, c, GET(8), 0x8771f681, 11)
133    STEP(H, c, d, a, b, GET(11), 0x6d9d6122, 16)
134    STEP(H, b, c, d, a, GET(14), 0xfde5380c, 23)
135    STEP(H, a, b, c, d, GET(1), 0xa4beea44, 4)
136    STEP(H, d, a, b, c, GET(4), 0x4bdecfa9, 11)
137    STEP(H, c, d, a, b, GET(7), 0xf6bb4b60, 16)
138    STEP(H, b, c, d, a, GET(10), 0xbebfbc70, 23)
139    STEP(H, a, b, c, d, GET(13), 0x289b7ec6, 4)
140    STEP(H, d, a, b, c, GET(0), 0xeaa127fa, 11)
141    STEP(H, c, d, a, b, GET(3), 0xd4ef3085, 16)
142    STEP(H, b, c, d, a, GET(6), 0x04881d05, 23)
143    STEP(H, a, b, c, d, GET(9), 0xd9d4d039, 4)
144    STEP(H, d, a, b, c, GET(12), 0xe6db99e5, 11)
145    STEP(H, c, d, a, b, GET(15), 0x1fa27cf8, 16)
146    STEP(H, b, c, d, a, GET(2), 0xc4ac5665, 23)
147
148    // Round 4
149    STEP(I, a, b, c, d, GET(0), 0xf4292244, 6)
150    STEP(I, d, a, b, c, GET(7), 0x432aff97, 10)
151    STEP(I, c, d, a, b, GET(14), 0xab9423a7, 15)
152    STEP(I, b, c, d, a, GET(5), 0xfc93a039, 21)
153    STEP(I, a, b, c, d, GET(12), 0x655b59c3, 6)
154    STEP(I, d, a, b, c, GET(3), 0x8f0ccc92, 10)
155    STEP(I, c, d, a, b, GET(10), 0xffeff47d, 15)
156    STEP(I, b, c, d, a, GET(1), 0x85845dd1, 21)
157    STEP(I, a, b, c, d, GET(8), 0x6fa87e4f, 6)
158    STEP(I, d, a, b, c, GET(15), 0xfe2ce6e0, 10)
159    STEP(I, c, d, a, b, GET(6), 0xa3014314, 15)
160    STEP(I, b, c, d, a, GET(13), 0x4e0811a1, 21)
161    STEP(I, a, b, c, d, GET(4), 0xf7537e82, 6)
162    STEP(I, d, a, b, c, GET(11), 0xbd3af235, 10)
163    STEP(I, c, d, a, b, GET(2), 0x2ad7d2bb, 15)
164    STEP(I, b, c, d, a, GET(9), 0xeb86d391, 21)
165
166    a += saved_a;
167    b += saved_b;
168    c += saved_c;
169    d += saved_d;
170
171    ptr += 64;
172  } while (Size -= 64);
173
174  this->a = a;
175  this->b = b;
176  this->c = c;
177  this->d = d;
178
179  return ptr;
180}
181
182MD5::MD5()
183    : a(0x67452301), b(0xefcdab89), c(0x98badcfe), d(0x10325476), hi(0), lo(0) {
184}
185
186/// Incrementally add the bytes in \p Data to the hash.
187void MD5::update(ArrayRef<uint8_t> Data) {
188  MD5_u32plus saved_lo;
189  unsigned long used, free;
190  const uint8_t *Ptr = Data.data();
191  unsigned long Size = Data.size();
192
193  saved_lo = lo;
194  if ((lo = (saved_lo + Size) & 0x1fffffff) < saved_lo)
195    hi++;
196  hi += Size >> 29;
197
198  used = saved_lo & 0x3f;
199
200  if (used) {
201    free = 64 - used;
202
203    if (Size < free) {
204      memcpy(&buffer[used], Ptr, Size);
205      return;
206    }
207
208    memcpy(&buffer[used], Ptr, free);
209    Ptr = Ptr + free;
210    Size -= free;
211    body(ArrayRef<uint8_t>(buffer, 64));
212  }
213
214  if (Size >= 64) {
215    Ptr = body(ArrayRef<uint8_t>(Ptr, Size & ~(unsigned long) 0x3f));
216    Size &= 0x3f;
217  }
218
219  memcpy(buffer, Ptr, Size);
220}
221
222/// Add the bytes in the StringRef \p Str to the hash.
223// Note that this isn't a string and so this won't include any trailing NULL
224// bytes.
225void MD5::update(StringRef Str) {
226  ArrayRef<uint8_t> SVal((const uint8_t *)Str.data(), Str.size());
227  update(SVal);
228}
229
230/// \brief Finish the hash and place the resulting hash into \p result.
231/// \param result is assumed to be a minimum of 16-bytes in size.
232void MD5::final(MD5Result &result) {
233  unsigned long used, free;
234
235  used = lo & 0x3f;
236
237  buffer[used++] = 0x80;
238
239  free = 64 - used;
240
241  if (free < 8) {
242    memset(&buffer[used], 0, free);
243    body(ArrayRef<uint8_t>(buffer, 64));
244    used = 0;
245    free = 64;
246  }
247
248  memset(&buffer[used], 0, free - 8);
249
250  lo <<= 3;
251  buffer[56] = lo;
252  buffer[57] = lo >> 8;
253  buffer[58] = lo >> 16;
254  buffer[59] = lo >> 24;
255  buffer[60] = hi;
256  buffer[61] = hi >> 8;
257  buffer[62] = hi >> 16;
258  buffer[63] = hi >> 24;
259
260  body(ArrayRef<uint8_t>(buffer, 64));
261
262  result[0] = a;
263  result[1] = a >> 8;
264  result[2] = a >> 16;
265  result[3] = a >> 24;
266  result[4] = b;
267  result[5] = b >> 8;
268  result[6] = b >> 16;
269  result[7] = b >> 24;
270  result[8] = c;
271  result[9] = c >> 8;
272  result[10] = c >> 16;
273  result[11] = c >> 24;
274  result[12] = d;
275  result[13] = d >> 8;
276  result[14] = d >> 16;
277  result[15] = d >> 24;
278}
279
280void MD5::stringifyResult(MD5Result &result, SmallString<32> &Str) {
281  raw_svector_ostream Res(Str);
282  for (int i = 0; i < 16; ++i)
283    Res << format("%.2x", result[i]);
284}
285
286}
287