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 #include "base/numerics/safe_conversions.h"
15
16 namespace base {
17 namespace internal {
18
19 // The implementation here is based on the pseudocode provided by Wikipedia:
20 // https://en.wikipedia.org/wiki/MD5#Pseudocode
21 struct MD5CE {
22 //////////////////////////////////////////////////////////////////////////////
23 // DATA STRUCTURES
24
25 // The data representation at each round is a 4-tuple of uint32_t.
26 struct IntermediateData {
27 uint32_t a;
28 uint32_t b;
29 uint32_t c;
30 uint32_t d;
31 };
32
33 // The input data for a single round consists of 16 uint32_t (64 bytes).
34 using RoundData = std::array<uint32_t, 16>;
35
36 //////////////////////////////////////////////////////////////////////////////
37 // CONSTANTS
38
39 static constexpr std::array<uint32_t, 64> kConstants = {
40 {0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a,
41 0xa8304613, 0xfd469501, 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be,
42 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821, 0xf61e2562, 0xc040b340,
43 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8,
44 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8,
45 0x676f02d9, 0x8d2a4c8a, 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c,
46 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70, 0x289b7ec6, 0xeaa127fa,
47 0xd4ef3085, 0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
48 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92,
49 0xffeff47d, 0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1,
50 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391}};
51
52 static constexpr std::array<uint32_t, 16> kShifts = {
53 {7, 12, 17, 22, 5, 9, 14, 20, 4, 11, 16, 23, 6, 10, 15, 21}};
54
55 // The initial intermediate data.
56 static constexpr IntermediateData kInitialIntermediateData{
57 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476};
58
59 //////////////////////////////////////////////////////////////////////////////
60 // PADDED MESSAGE GENERATION / EXTRACTION
61
62 // Given the message length, calculates the padded message length. There has
63 // to be room for the 1-byte end-of-message marker, plus 8 bytes for the
64 // uint64_t encoded message length, all rounded up to a multiple of 64 bytes.
GetPaddedMessageLengthMD5CE65 static constexpr uint32_t GetPaddedMessageLength(const uint32_t n) {
66 return (((n + 1 + 8) + 63) / 64) * 64;
67 }
68
69 // Extracts the |i|th byte of a uint64_t, where |i == 0| extracts the least
70 // significant byte. It is expected that 0 <= i < 8.
ExtractByteMD5CE71 static constexpr uint8_t ExtractByte(const uint64_t value, const uint32_t i) {
72 DCHECK_LT(i, 8u);
73 return static_cast<uint8_t>((value >> (i * 8)) & 0xff);
74 }
75
76 // Extracts the |i|th byte of a message of length |n|.
GetPaddedMessageByteMD5CE77 static constexpr uint8_t GetPaddedMessageByte(std::string_view data,
78 const uint32_t m,
79 const uint32_t i) {
80 DCHECK_LT(i, m);
81 DCHECK_LT(data.size(), m);
82 DCHECK_EQ(m % 64, 0u);
83 if (i < data.size()) {
84 // Emit the message itself...
85 return static_cast<uint8_t>(data[i]);
86 } else if (i == data.size()) {
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(data.size() * 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|. The bytes are treated in little
100 // endian order.
GetPaddedMessageWordMD5CE101 static constexpr uint32_t GetPaddedMessageWord(std::string_view data,
102 const uint32_t m,
103 const uint32_t i) {
104 DCHECK_EQ(i % 4, 0u);
105 DCHECK_LT(i, m);
106 DCHECK_LT(data.size(), m);
107 DCHECK_EQ(m % 64, 0u);
108 return static_cast<uint32_t>(GetPaddedMessageByte(data, m, i)) |
109 static_cast<uint32_t>((GetPaddedMessageByte(data, m, i + 1)) << 8) |
110 static_cast<uint32_t>((GetPaddedMessageByte(data, m, i + 2)) << 16) |
111 static_cast<uint32_t>((GetPaddedMessageByte(data, m, i + 3)) << 24);
112 }
113
114 // Given an input buffer |data|, extracts one round worth of data starting at
115 // offset |i|.
GetRoundDataMD5CE116 static constexpr RoundData GetRoundData(std::string_view data,
117 const uint32_t m,
118 const uint32_t i) {
119 DCHECK_EQ(i % 64, 0u);
120 DCHECK_LT(i, m);
121 DCHECK_LT(data.size(), m);
122 DCHECK_EQ(m % 64, 0u);
123 return RoundData{{GetPaddedMessageWord(data, m, i),
124 GetPaddedMessageWord(data, m, i + 4),
125 GetPaddedMessageWord(data, m, i + 8),
126 GetPaddedMessageWord(data, m, i + 12),
127 GetPaddedMessageWord(data, m, i + 16),
128 GetPaddedMessageWord(data, m, i + 20),
129 GetPaddedMessageWord(data, m, i + 24),
130 GetPaddedMessageWord(data, m, i + 28),
131 GetPaddedMessageWord(data, m, i + 32),
132 GetPaddedMessageWord(data, m, i + 36),
133 GetPaddedMessageWord(data, m, i + 40),
134 GetPaddedMessageWord(data, m, i + 44),
135 GetPaddedMessageWord(data, m, i + 48),
136 GetPaddedMessageWord(data, m, i + 52),
137 GetPaddedMessageWord(data, m, i + 56),
138 GetPaddedMessageWord(data, m, i + 60)}};
139 }
140
141 //////////////////////////////////////////////////////////////////////////////
142 // HASH IMPLEMENTATION
143
144 // Mixes elements |b|, |c| and |d| at round |i| of the calculation.
CalcFMD5CE145 static constexpr uint32_t CalcF(const uint32_t i,
146 const uint32_t b,
147 const uint32_t c,
148 const uint32_t d) {
149 DCHECK_LT(i, 64u);
150 if (i < 16) {
151 return d ^ (b & (c ^ d));
152 } else if (i < 32) {
153 return c ^ (d & (b ^ c));
154 } else if (i < 48) {
155 return b ^ c ^ d;
156 } else {
157 return c ^ (b | (~d));
158 }
159 }
CalcFMD5CE160 static constexpr uint32_t CalcF(const uint32_t i,
161 const IntermediateData& intermediate) {
162 return CalcF(i, intermediate.b, intermediate.c, intermediate.d);
163 }
164
165 // Calculates the indexing function at round |i|.
CalcGMD5CE166 static constexpr uint32_t CalcG(const uint32_t i) {
167 DCHECK_LT(i, 64u);
168 if (i < 16) {
169 return i;
170 } else if (i < 32) {
171 return (5 * i + 1) % 16;
172 } else if (i < 48) {
173 return (3 * i + 5) % 16;
174 } else {
175 return (7 * i) % 16;
176 }
177 }
178
179 // Calculates the rotation to be applied at round |i|.
GetShiftMD5CE180 static constexpr uint32_t GetShift(const uint32_t i) {
181 DCHECK_LT(i, 64u);
182 return kShifts[(i / 16) * 4 + (i % 4)];
183 }
184
185 // Rotates to the left the given |value| by the given |bits|.
LeftRotateMD5CE186 static constexpr uint32_t LeftRotate(const uint32_t value,
187 const uint32_t bits) {
188 DCHECK_LT(bits, 32u);
189 return (value << bits) | (value >> (32 - bits));
190 }
191
192 // Applies the ith step of mixing.
ApplyStepMD5CE193 static constexpr IntermediateData ApplyStep(
194 const uint32_t i,
195 const RoundData& data,
196 const IntermediateData& intermediate) {
197 DCHECK_LT(i, 64u);
198 const uint32_t g = CalcG(i);
199 DCHECK_LT(g, 16u);
200 const uint32_t f =
201 CalcF(i, intermediate) + intermediate.a + kConstants[i] + data[g];
202 const uint32_t s = GetShift(i);
203 return IntermediateData{/* a */ intermediate.d,
204 /* b */ intermediate.b + LeftRotate(f, s),
205 /* c */ intermediate.b,
206 /* d */ intermediate.c};
207 }
208
209 // Adds two IntermediateData together.
AddMD5CE210 static constexpr IntermediateData Add(const IntermediateData& intermediate1,
211 const IntermediateData& intermediate2) {
212 return IntermediateData{
213 intermediate1.a + intermediate2.a, intermediate1.b + intermediate2.b,
214 intermediate1.c + intermediate2.c, intermediate1.d + intermediate2.d};
215 }
216
217 // Processes an entire message.
ProcessMessageMD5CE218 static constexpr IntermediateData ProcessMessage(std::string_view message) {
219 const uint32_t m =
220 GetPaddedMessageLength(checked_cast<uint32_t>(message.size()));
221 IntermediateData intermediate0 = kInitialIntermediateData;
222 for (uint32_t offset = 0; offset < m; offset += 64) {
223 RoundData data = GetRoundData(message, m, offset);
224 IntermediateData intermediate1 = intermediate0;
225 for (uint32_t i = 0; i < 64; ++i)
226 intermediate1 = ApplyStep(i, data, intermediate1);
227 intermediate0 = Add(intermediate0, intermediate1);
228 }
229 return intermediate0;
230 }
231
232 //////////////////////////////////////////////////////////////////////////////
233 // HELPER FUNCTIONS
234
SwapEndianMD5CE235 static constexpr uint32_t SwapEndian(uint32_t a) {
236 return ((a & 0xff) << 24) | (((a >> 8) & 0xff) << 16) |
237 (((a >> 16) & 0xff) << 8) | ((a >> 24) & 0xff);
238 }
239
240 //////////////////////////////////////////////////////////////////////////////
241 // WRAPPER FUNCTIONS
242
Hash64MD5CE243 static constexpr uint64_t Hash64(std::string_view data) {
244 IntermediateData intermediate = ProcessMessage(data);
245 return (static_cast<uint64_t>(SwapEndian(intermediate.a)) << 32) |
246 static_cast<uint64_t>(SwapEndian(intermediate.b));
247 }
248
Hash32MD5CE249 static constexpr uint32_t Hash32(std::string_view data) {
250 IntermediateData intermediate = ProcessMessage(data);
251 return SwapEndian(intermediate.a);
252 }
253 };
254
255 } // namespace internal
256
257 // Implementations of the functions exposed in the public header.
258
MD5Hash64Constexpr(std::string_view string)259 constexpr uint64_t MD5Hash64Constexpr(std::string_view string) {
260 return internal::MD5CE::Hash64(string);
261 }
262
MD5Hash32Constexpr(std::string_view string)263 constexpr uint32_t MD5Hash32Constexpr(std::string_view string) {
264 return internal::MD5CE::Hash32(string);
265 }
266
267 } // namespace base
268
269 #endif // BASE_HASH_MD5_CONSTEXPR_INTERNAL_H_
270