LLVM API Documentation

 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
MD5.cpp
Go to the documentation of this file.
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"
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 
71 namespace 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.
75 const 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 
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.
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.
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.
232 void 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 
280 void 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 }
#define GET(n)
Definition: MD5.cpp:69
size_t size() const
size - Get the string size.
Definition: StringRef.h:113
#define STEP(f, a, b, c, d, x, t, s)
Definition: MD5.cpp:57
#define G(x, y, z)
Definition: MD5.cpp:52
format_object1< T > format(const char *Fmt, const T &Val)
Definition: Format.h:180
#define F(x, y, z)
Definition: MD5.cpp:51
const char * data() const
Definition: StringRef.h:107
void update(ArrayRef< uint8_t > Data)
Updates the hash for the byte stream provided.
Definition: MD5.cpp:187
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:109
void final(MD5Result &result)
Finishes off the hash and puts the result in result.
Definition: MD5.cpp:232
#define SET(n)
Definition: MD5.cpp:64
#define H(x, y, z)
Definition: MD5.cpp:53
void free(void *ptr);
static void stringifyResult(MD5Result &Res, SmallString< 32 > &Str)
Translates the bytes in Res to a hex string that is deposited into Str. The result will be of length ...
Definition: MD5.cpp:280
#define I(x, y, z)
Definition: MD5.cpp:54
const T * data() const
Definition: ArrayRef.h:106
MD5()
Definition: MD5.cpp:182