1 // Copyright 2019 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #ifndef BASE_HASH_MD5_CONSTEXPR_INTERNAL_H_
6 #define BASE_HASH_MD5_CONSTEXPR_INTERNAL_H_
7
8 #include <stdint.h>
9
10 #include <array>
11
12 #include "base/check.h"
13 #include "base/check_op.h"
14
15 namespace base {
16 namespace internal {
17
18 // The implementation here is based on the pseudocode provided by Wikipedia:
19 // https://en.wikipedia.org/wiki/MD5#Pseudocode
20 struct MD5CE {
21 //////////////////////////////////////////////////////////////////////////////
22 // DATA STRUCTURES
23
24 // The data representation at each round is a 4-tuple of uint32_t.
25 struct IntermediateData {
26 uint32_t a;
27 uint32_t b;
28 uint32_t c;
29 uint32_t d;
30 };
31
32 // The input data for a single round consists of 16 uint32_t (64 bytes).
33 using RoundData = std::array<uint32_t, 16>;
34
35 //////////////////////////////////////////////////////////////////////////////
36 // CONSTANTS
37
38 static constexpr std::array<uint32_t, 64> kConstants = {
39 {0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a,
40 0xa8304613, 0xfd469501, 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
41 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821, 0xf61e2562, 0xc040b340,
42 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
43 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8,
44 0x676f02d9, 0x8d2a4c8a, 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
45 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70, 0x289b7ec6, 0xeaa127fa,
46 0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
47 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92,
48 0xffeff47d, 0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
49 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391}};
50
51 static constexpr std::array<uint32_t, 16> kShifts = {
52 {7, 12, 17, 22, 5, 9, 14, 20, 4, 11, 16, 23, 6, 10, 15, 21}};
53
54 // The initial intermediate data.
55 static constexpr IntermediateData kInitialIntermediateData{
56 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476};
57
58 //////////////////////////////////////////////////////////////////////////////
59 // PADDED MESSAGE GENERATION / EXTRACTION
60
61 // Given the message length, calculates the padded message length. There has
62 // to be room for the 1-byte end-of-message marker, plus 8 bytes for the
63 // uint64_t encoded message length, all rounded up to a multiple of 64 bytes.
GetPaddedMessageLengthMD5CE64 static constexpr uint32_t GetPaddedMessageLength(const uint32_t n) {
65 return (((n + 1 + 8) + 63) / 64) * 64;
66 }
67
68 // Extracts the |i|th byte of a uint64_t, where |i == 0| extracts the least
69 // significant byte. It is expected that 0 <= i < 8.
ExtractByteMD5CE70 static constexpr uint8_t ExtractByte(const uint64_t value, const uint32_t i) {
71 DCHECK_LT(i, 8u);
72 return static_cast<uint8_t>((value >> (i * 8)) & 0xff);
73 }
74
75 // Extracts the |i|th byte of a message of length |n|.
GetPaddedMessageByteMD5CE76 static constexpr uint8_t GetPaddedMessageByte(const char* data,
77 const uint32_t n,
78 const uint32_t m,
79 const uint32_t i) {
80 DCHECK_LT(i, m);
81 DCHECK_LT(n, m);
82 DCHECK_EQ(m % 64, 0u);
83 if (i < n) {
84 // Emit the message itself...
85 return static_cast<uint8_t>(data[i]);
86 } else if (i == n) {
87 // ...followed by the end of message marker.
88 return 0x80;
89 } else if (i >= m - 8) {
90 // The last 8 bytes encode the original message length times 8.
91 return ExtractByte(n * 8, i - (m - 8));
92 } else {
93 // And everything else is just empyt padding.
94 return 0;
95 }
96 }
97
98 // Extracts the uint32_t starting at position |i| from the padded message
99 // generate by the provided input |data| of length |n|. The bytes are treated
100 // in little endian order.
GetPaddedMessageWordMD5CE101 static constexpr uint32_t GetPaddedMessageWord(const char* data,
102 const uint32_t n,
103 const uint32_t m,
104 const uint32_t i) {
105 DCHECK_EQ(i % 4, 0u);
106 DCHECK_LT(i, m);
107 DCHECK_LT(n, m);
108 DCHECK_EQ(m % 64, 0u);
109 return static_cast<uint32_t>(GetPaddedMessageByte(data, n, m, i)) |
110 static_cast<uint32_t>((GetPaddedMessageByte(data, n, m, i + 1))
111 << 8) |
112 static_cast<uint32_t>((GetPaddedMessageByte(data, n, m, i + 2))
113 << 16) |
114 static_cast<uint32_t>((GetPaddedMessageByte(data, n, m, i + 3))
115 << 24);
116 }
117
118 // Given an input buffer of length |n| bytes, extracts one round worth of data
119 // starting at offset |i|.
GetRoundDataMD5CE120 static constexpr RoundData GetRoundData(const char* data,
121 const uint32_t n,
122 const uint32_t m,
123 const uint32_t i) {
124 DCHECK_EQ(i % 64, 0u);
125 DCHECK_LT(i, m);
126 DCHECK_LT(n, m);
127 DCHECK_EQ(m % 64, 0u);
128 return RoundData{{GetPaddedMessageWord(data, n, m, i),
129 GetPaddedMessageWord(data, n, m, i + 4),
130 GetPaddedMessageWord(data, n, m, i + 8),
131 GetPaddedMessageWord(data, n, m, i + 12),
132 GetPaddedMessageWord(data, n, m, i + 16),
133 GetPaddedMessageWord(data, n, m, i + 20),
134 GetPaddedMessageWord(data, n, m, i + 24),
135 GetPaddedMessageWord(data, n, m, i + 28),
136 GetPaddedMessageWord(data, n, m, i + 32),
137 GetPaddedMessageWord(data, n, m, i + 36),
138 GetPaddedMessageWord(data, n, m, i + 40),
139 GetPaddedMessageWord(data, n, m, i + 44),
140 GetPaddedMessageWord(data, n, m, i + 48),
141 GetPaddedMessageWord(data, n, m, i + 52),
142 GetPaddedMessageWord(data, n, m, i + 56),
143 GetPaddedMessageWord(data, n, m, i + 60)}};
144 }
145
146 //////////////////////////////////////////////////////////////////////////////
147 // HASH IMPLEMENTATION
148
149 // Mixes elements |b|, |c| and |d| at round |i| of the calculation.
CalcFMD5CE150 static constexpr uint32_t CalcF(const uint32_t i,
151 const uint32_t b,
152 const uint32_t c,
153 const uint32_t d) {
154 DCHECK_LT(i, 64u);
155 if (i < 16) {
156 return d ^ (b & (c ^ d));
157 } else if (i < 32) {
158 return c ^ (d & (b ^ c));
159 } else if (i < 48) {
160 return b ^ c ^ d;
161 } else {
162 return c ^ (b | (~d));
163 }
164 }
CalcFMD5CE165 static constexpr uint32_t CalcF(const uint32_t i,
166 const IntermediateData& intermediate) {
167 return CalcF(i, intermediate.b, intermediate.c, intermediate.d);
168 }
169
170 // Calculates the indexing function at round |i|.
CalcGMD5CE171 static constexpr uint32_t CalcG(const uint32_t i) {
172 DCHECK_LT(i, 64u);
173 if (i < 16) {
174 return i;
175 } else if (i < 32) {
176 return (5 * i + 1) % 16;
177 } else if (i < 48) {
178 return (3 * i + 5) % 16;
179 } else {
180 return (7 * i) % 16;
181 }
182 }
183
184 // Calculates the rotation to be applied at round |i|.
GetShiftMD5CE185 static constexpr uint32_t GetShift(const uint32_t i) {
186 DCHECK_LT(i, 64u);
187 return kShifts[(i / 16) * 4 + (i % 4)];
188 }
189
190 // Rotates to the left the given |value| by the given |bits|.
LeftRotateMD5CE191 static constexpr uint32_t LeftRotate(const uint32_t value,
192 const uint32_t bits) {
193 DCHECK_LT(bits, 32u);
194 return (value << bits) | (value >> (32 - bits));
195 }
196
197 // Applies the ith step of mixing.
ApplyStepMD5CE198 static constexpr IntermediateData ApplyStep(
199 const uint32_t i,
200 const RoundData& data,
201 const IntermediateData& intermediate) {
202 DCHECK_LT(i, 64u);
203 const uint32_t g = CalcG(i);
204 DCHECK_LT(g, 16u);
205 const uint32_t f =
206 CalcF(i, intermediate) + intermediate.a + kConstants[i] + data[g];
207 const uint32_t s = GetShift(i);
208 return IntermediateData{/* a */ intermediate.d,
209 /* b */ intermediate.b + LeftRotate(f, s),
210 /* c */ intermediate.b,
211 /* d */ intermediate.c};
212 }
213
214 // Adds two IntermediateData together.
AddMD5CE215 static constexpr IntermediateData Add(const IntermediateData& intermediate1,
216 const IntermediateData& intermediate2) {
217 return IntermediateData{
218 intermediate1.a + intermediate2.a, intermediate1.b + intermediate2.b,
219 intermediate1.c + intermediate2.c, intermediate1.d + intermediate2.d};
220 }
221
222 // Processes an entire message.
ProcessMessageMD5CE223 static constexpr IntermediateData ProcessMessage(const char* message,
224 const uint32_t n) {
225 const uint32_t m = GetPaddedMessageLength(n);
226 IntermediateData intermediate0 = kInitialIntermediateData;
227 for (uint32_t offset = 0; offset < m; offset += 64) {
228 RoundData data = GetRoundData(message, n, m, offset);
229 IntermediateData intermediate1 = intermediate0;
230 for (uint32_t i = 0; i < 64; ++i)
231 intermediate1 = ApplyStep(i, data, intermediate1);
232 intermediate0 = Add(intermediate0, intermediate1);
233 }
234 return intermediate0;
235 }
236
237 //////////////////////////////////////////////////////////////////////////////
238 // HELPER FUNCTIONS
239
StringLengthMD5CE240 static constexpr uint32_t StringLength(const char* string) {
241 const char* end = string;
242 while (*end != 0)
243 ++end;
244 // Double check that the precision losing conversion is safe.
245 DCHECK(end >= string);
246 DCHECK(static_cast<std::ptrdiff_t>(static_cast<uint32_t>(end - string)) ==
247 (end - string));
248 return static_cast<uint32_t>(end - string);
249 }
250
SwapEndianMD5CE251 static constexpr uint32_t SwapEndian(uint32_t a) {
252 return ((a & 0xff) << 24) | (((a >> 8) & 0xff) << 16) |
253 (((a >> 16) & 0xff) << 8) | ((a >> 24) & 0xff);
254 }
255
256 //////////////////////////////////////////////////////////////////////////////
257 // WRAPPER FUNCTIONS
258
Hash64MD5CE259 static constexpr uint64_t Hash64(const char* data, uint32_t n) {
260 IntermediateData intermediate = ProcessMessage(data, n);
261 return (static_cast<uint64_t>(SwapEndian(intermediate.a)) << 32) |
262 static_cast<uint64_t>(SwapEndian(intermediate.b));
263 }
264
Hash32MD5CE265 static constexpr uint32_t Hash32(const char* data, uint32_t n) {
266 IntermediateData intermediate = ProcessMessage(data, n);
267 return SwapEndian(intermediate.a);
268 }
269 };
270
271 } // namespace internal
272
273 // Implementations of the functions exposed in the public header.
274
MD5Hash64Constexpr(const char * string)275 constexpr uint64_t MD5Hash64Constexpr(const char* string) {
276 return internal::MD5CE::Hash64(string, internal::MD5CE::StringLength(string));
277 }
278
MD5Hash64Constexpr(const char * string,uint32_t length)279 constexpr uint64_t MD5Hash64Constexpr(const char* string, uint32_t length) {
280 return internal::MD5CE::Hash64(string, length);
281 }
282
MD5Hash32Constexpr(const char * string)283 constexpr uint32_t MD5Hash32Constexpr(const char* string) {
284 return internal::MD5CE::Hash32(string, internal::MD5CE::StringLength(string));
285 }
286
MD5Hash32Constexpr(const char * string,uint32_t length)287 constexpr uint32_t MD5Hash32Constexpr(const char* string, uint32_t length) {
288 return internal::MD5CE::Hash32(string, length);
289 }
290
291 } // namespace base
292
293 #endif // BASE_HASH_MD5_CONSTEXPR_INTERNAL_H_
294