1use crate::multiversion;
9use crate::multiversion::Version;
10use std::array;
11use std::sync::LazyLock;
12
13mod bruteforce;
14pub use bruteforce::find_hash_with_appended_count;
15
16#[cfg(test)]
17mod tests;
18
19const INITIAL_STATE: [u32; 4] = [0x6745_2301, 0xefcd_ab89, 0x98ba_dcfe, 0x1032_5476];
20
21pub static FASTEST: LazyLock<Version> = multiversion! { fastest(microbenchmark()) };
25
26#[must_use]
38pub fn hash(buf: &[u8]) -> [u32; 4] {
39 scalar::hash(buf)[0]
40}
41
42multiversion! {
43 use {crate::simd::*};
44
45 const ONE_BYTE: usize = U32Vector::LANES;
47 const TWO_BYTES: usize = 2 * U32Vector::LANES;
48 const THREE_BYTES: usize = 3 * U32Vector::LANES;
49 const FOUR_BYTES: usize = 4 * U32Vector::LANES;
50
51 #[must_use]
70 pub fn hash(mut buf: &[u8]) -> [[u32; 4]; U32Vector::LANES] {
71 assert_eq!(buf.len() % U32Vector::LANES, 0);
72 let bytes = buf.len() / U32Vector::LANES;
73
74 let mut state = array::from_fn(|i| U32Vector::splat(INITIAL_STATE[i]));
75
76 let mut end_marker_written = false;
77 let mut bit_count_written = false;
78 while !bit_count_written {
79 let mut words = [U32Vector::splat(0); 16];
80
81 let remaining = (buf.len() / FOUR_BYTES).min(16);
82 for (w, chunk) in words.iter_mut().zip(buf.as_chunks::<FOUR_BYTES>().0) {
83 *w = gather(chunk);
84 }
85 buf = &buf[remaining * FOUR_BYTES..];
86
87 if remaining < 16 {
88 if !end_marker_written {
89 words[remaining] = gather_remaining(buf);
91 buf = &[];
92 end_marker_written = true;
93 }
94
95 if !bit_count_written && remaining <= 13 {
96 let bits = bytes as u64 * 8;
97 words[14] = U32Vector::splat((bits & 0xFFFF_FFFF) as u32);
98 words[15] = U32Vector::splat((bits >> 32) as u32);
99 bit_count_written = true;
100 }
101 }
102
103 state = md5_block(state, &words);
104 }
105
106 to_hashes(state)
107 }
108
109 #[inline]
110 fn gather(buf: &[u8; FOUR_BYTES]) -> U32Vector {
111 let mut values = [0u32; U32Vector::LANES];
112 for (i, v) in values.iter_mut().enumerate() {
113 *v = u32::from_le_bytes([
114 buf[i], buf[ONE_BYTE + i], buf[TWO_BYTES + i], buf[THREE_BYTES + i]
115 ]);
116 }
117 values.into()
118 }
119
120 #[inline]
121 fn gather_remaining(buf: &[u8]) -> U32Vector {
122 match buf.len() {
123 THREE_BYTES => {
124 let mut values = [0u32; U32Vector::LANES];
125 for (i, v) in values.iter_mut().enumerate() {
126 *v = u32::from_le_bytes([buf[i], buf[ONE_BYTE + i], buf[TWO_BYTES + i], 0x80]);
127 }
128 values.into()
129 }
130 TWO_BYTES => {
131 let mut values = [0u32; U32Vector::LANES];
132 for (i, v) in values.iter_mut().enumerate() {
133 *v = u32::from_le_bytes([buf[i], buf[ONE_BYTE + i], 0x80, 0]);
134 }
135 values.into()
136 }
137 ONE_BYTE => {
138 let mut values = [0u32; U32Vector::LANES];
139 for (i, v) in values.iter_mut().enumerate() {
140 *v = u32::from_le_bytes([buf[i], 0x80, 0, 0]);
141 }
142 values.into()
143 }
144 0 => U32Vector::splat(0x80),
145 _ => unreachable!("less than 4 bytes left"),
146 }
147 }
148
149 #[inline]
150 fn to_hashes(state: [U32Vector; 4]) -> [[u32; 4]; U32Vector::LANES] {
151 let state: [[u32; U32Vector::LANES]; 4] = array::from_fn(|i| state[i].into());
153
154 array::from_fn(|i| {
155 [
156 state[0][i].swap_bytes(),
157 state[1][i].swap_bytes(),
158 state[2][i].swap_bytes(),
159 state[3][i].swap_bytes(),
160 ]
161 })
162 }
163
164 #[must_use]
180 #[expect(clippy::cast_possible_truncation)]
181 pub fn stretch(
182 hashes: [[u32; 4]; U32Vector::LANES],
183 additional_hashes: u32,
184 ) -> [[u32; 4]; U32Vector::LANES] {
185 let initial = array::from_fn(|i| U32Vector::splat(INITIAL_STATE[i]));
186
187 let mut state: [U32Vector; 4] = array::from_fn(|i| {
189 let mut values = [0u32; U32Vector::LANES];
190 for (v, hash) in values.iter_mut().zip(hashes) {
191 *v = hash[i].swap_bytes();
192 }
193 values.into()
194 });
195
196 let mut words = [U32Vector::splat(0); 8];
197 for _ in 0..additional_hashes {
198 for i in 0..4 {
199 let values: [u32; U32Vector::LANES] = state[i].into();
200 let mut lo = [0u32; U32Vector::LANES];
201 let mut hi = [0u32; U32Vector::LANES];
202 for (j, &v) in values.iter().enumerate() {
203 lo[j] = u16_to_hex(v as u16);
204 hi[j] = u16_to_hex((v >> 16) as u16);
205 }
206 words[2 * i] = lo.into();
207 words[2 * i + 1] = hi.into();
208 }
209 state = md5_block(initial, &words);
210 }
211
212 to_hashes(state)
213 }
214
215 #[expect(clippy::cast_possible_truncation, clippy::many_single_char_names)]
216 fn md5_block<const N: usize>(
217 [a0, b0, c0, d0]: [U32Vector; 4],
218 words: &[U32Vector; N],
219 ) -> [U32Vector; 4] {
220 let mut block = [U32Vector::splat(0); 16];
221 let m: &[U32Vector; 16] = if let Ok(m) = words.as_slice().try_into() {
222 m
223 } else {
224 block[..N].copy_from_slice(words);
227 block[N] = U32Vector::splat(0x80);
228 block[14] = U32Vector::splat(32 * N as u32);
229 &block
230 };
231
232 let (mut a, mut b, mut c, mut d) = (a0, b0, c0, d0);
233
234 a = md5_round(md5_f(b, c, d), a, b, m[0], 7, 0xd76a_a478);
235 d = md5_round(md5_f(a, b, c), d, a, m[1], 12, 0xe8c7_b756);
236 c = md5_round(md5_f(d, a, b), c, d, m[2], 17, 0x2420_70db);
237 b = md5_round(md5_f(c, d, a), b, c, m[3], 22, 0xc1bd_ceee);
238 a = md5_round(md5_f(b, c, d), a, b, m[4], 7, 0xf57c_0faf);
239 d = md5_round(md5_f(a, b, c), d, a, m[5], 12, 0x4787_c62a);
240 c = md5_round(md5_f(d, a, b), c, d, m[6], 17, 0xa830_4613);
241 b = md5_round(md5_f(c, d, a), b, c, m[7], 22, 0xfd46_9501);
242 a = md5_round(md5_f(b, c, d), a, b, m[8], 7, 0x6980_98d8);
243 d = md5_round(md5_f(a, b, c), d, a, m[9], 12, 0x8b44_f7af);
244 c = md5_round(md5_f(d, a, b), c, d, m[10], 17, 0xffff_5bb1);
245 b = md5_round(md5_f(c, d, a), b, c, m[11], 22, 0x895c_d7be);
246 a = md5_round(md5_f(b, c, d), a, b, m[12], 7, 0x6b90_1122);
247 d = md5_round(md5_f(a, b, c), d, a, m[13], 12, 0xfd98_7193);
248 c = md5_round(md5_f(d, a, b), c, d, m[14], 17, 0xa679_438e);
249 b = md5_round(md5_f(c, d, a), b, c, m[15], 22, 0x49b4_0821);
250
251 a = md5_round(md5_g(b, c, d), a, b, m[1], 5, 0xf61e_2562);
252 d = md5_round(md5_g(a, b, c), d, a, m[6], 9, 0xc040_b340);
253 c = md5_round(md5_g(d, a, b), c, d, m[11], 14, 0x265e_5a51);
254 b = md5_round(md5_g(c, d, a), b, c, m[0], 20, 0xe9b6_c7aa);
255 a = md5_round(md5_g(b, c, d), a, b, m[5], 5, 0xd62f_105d);
256 d = md5_round(md5_g(a, b, c), d, a, m[10], 9, 0x0244_1453);
257 c = md5_round(md5_g(d, a, b), c, d, m[15], 14, 0xd8a1_e681);
258 b = md5_round(md5_g(c, d, a), b, c, m[4], 20, 0xe7d3_fbc8);
259 a = md5_round(md5_g(b, c, d), a, b, m[9], 5, 0x21e1_cde6);
260 d = md5_round(md5_g(a, b, c), d, a, m[14], 9, 0xc337_07d6);
261 c = md5_round(md5_g(d, a, b), c, d, m[3], 14, 0xf4d5_0d87);
262 b = md5_round(md5_g(c, d, a), b, c, m[8], 20, 0x455a_14ed);
263 a = md5_round(md5_g(b, c, d), a, b, m[13], 5, 0xa9e3_e905);
264 d = md5_round(md5_g(a, b, c), d, a, m[2], 9, 0xfcef_a3f8);
265 c = md5_round(md5_g(d, a, b), c, d, m[7], 14, 0x676f_02d9);
266 b = md5_round(md5_g(c, d, a), b, c, m[12], 20, 0x8d2a_4c8a);
267
268 a = md5_round(md5_h(b, c, d), a, b, m[5], 4, 0xfffa_3942);
269 d = md5_round(md5_h(a, b, c), d, a, m[8], 11, 0x8771_f681);
270 c = md5_round(md5_h(d, a, b), c, d, m[11], 16, 0x6d9d_6122);
271 b = md5_round(md5_h(c, d, a), b, c, m[14], 23, 0xfde5_380c);
272 a = md5_round(md5_h(b, c, d), a, b, m[1], 4, 0xa4be_ea44);
273 d = md5_round(md5_h(a, b, c), d, a, m[4], 11, 0x4bde_cfa9);
274 c = md5_round(md5_h(d, a, b), c, d, m[7], 16, 0xf6bb_4b60);
275 b = md5_round(md5_h(c, d, a), b, c, m[10], 23, 0xbebf_bc70);
276 a = md5_round(md5_h(b, c, d), a, b, m[13], 4, 0x289b_7ec6);
277 d = md5_round(md5_h(a, b, c), d, a, m[0], 11, 0xeaa1_27fa);
278 c = md5_round(md5_h(d, a, b), c, d, m[3], 16, 0xd4ef_3085);
279 b = md5_round(md5_h(c, d, a), b, c, m[6], 23, 0x0488_1d05);
280 a = md5_round(md5_h(b, c, d), a, b, m[9], 4, 0xd9d4_d039);
281 d = md5_round(md5_h(a, b, c), d, a, m[12], 11, 0xe6db_99e5);
282 c = md5_round(md5_h(d, a, b), c, d, m[15], 16, 0x1fa2_7cf8);
283 b = md5_round(md5_h(c, d, a), b, c, m[2], 23, 0xc4ac_5665);
284
285 a = md5_round(md5_i(b, c, d), a, b, m[0], 6, 0xf429_2244);
286 d = md5_round(md5_i(a, b, c), d, a, m[7], 10, 0x432a_ff97);
287 c = md5_round(md5_i(d, a, b), c, d, m[14], 15, 0xab94_23a7);
288 b = md5_round(md5_i(c, d, a), b, c, m[5], 21, 0xfc93_a039);
289 a = md5_round(md5_i(b, c, d), a, b, m[12], 6, 0x655b_59c3);
290 d = md5_round(md5_i(a, b, c), d, a, m[3], 10, 0x8f0c_cc92);
291 c = md5_round(md5_i(d, a, b), c, d, m[10], 15, 0xffef_f47d);
292 b = md5_round(md5_i(c, d, a), b, c, m[1], 21, 0x8584_5dd1);
293 a = md5_round(md5_i(b, c, d), a, b, m[8], 6, 0x6fa8_7e4f);
294 d = md5_round(md5_i(a, b, c), d, a, m[15], 10, 0xfe2c_e6e0);
295 c = md5_round(md5_i(d, a, b), c, d, m[6], 15, 0xa301_4314);
296 b = md5_round(md5_i(c, d, a), b, c, m[13], 21, 0x4e08_11a1);
297 a = md5_round(md5_i(b, c, d), a, b, m[4], 6, 0xf753_7e82);
298 d = md5_round(md5_i(a, b, c), d, a, m[11], 10, 0xbd3a_f235);
299 c = md5_round(md5_i(d, a, b), c, d, m[2], 15, 0x2ad7_d2bb);
300 b = md5_round(md5_i(c, d, a), b, c, m[9], 21, 0xeb86_d391);
301
302 [a0 + a, b0 + b, c0 + c, d0 + d]
303 }
304
305 #[inline]
306 #[expect(clippy::many_single_char_names)]
307 fn md5_round(f: U32Vector, a: U32Vector, b: U32Vector, m: U32Vector, s: u32, k: u32) -> U32Vector {
308 (f + a + m + U32Vector::splat(k)).rotate_left(s) + b
309 }
310
311 #[inline]
312 fn md5_f(b: U32Vector, c: U32Vector, d: U32Vector) -> U32Vector {
313 (b & c) | (d & !b)
314 }
315
316 #[inline]
317 fn md5_g(b: U32Vector, c: U32Vector, d: U32Vector) -> U32Vector {
318 (d & b) | (c & !d)
319 }
320
321 #[inline]
322 fn md5_h(b: U32Vector, c: U32Vector, d: U32Vector) -> U32Vector {
323 b ^ c ^ d
324 }
325
326 #[inline]
327 fn md5_i(b: U32Vector, c: U32Vector, d: U32Vector) -> U32Vector {
328 c ^ (b | !d)
329 }
330
331 pub(super) fn microbenchmark() {
332 let bench_string = BENCH_STRING.as_flattened();
333 for chunk in bench_string.chunks(32 * U32Vector::LANES) {
334 for len in 1..=32 {
335 std::hint::black_box(hash(&chunk[..len * U32Vector::LANES]));
336 }
337 }
338 }
339}
340
341static BENCH_STRING: [[u8; 32]; 128] = {
342 let mut out = [*b"abcdefghijklmnopqrstuvwxyz012345"; 128];
343 let mut i = 0;
344
345 #[expect(clippy::cast_possible_truncation)]
346 while i < out.len() {
347 out[i][i % 32] = i as u8;
348 i += 1;
349 }
350
351 out
352};
353
354#[inline]
369#[must_use]
370pub fn to_hex([a, b, c, d]: [u32; 4]) -> [u8; 32] {
371 let mut result = [0u8; 32];
372 result[0..8].copy_from_slice(&u32_to_hex(a));
373 result[8..16].copy_from_slice(&u32_to_hex(b));
374 result[16..24].copy_from_slice(&u32_to_hex(c));
375 result[24..32].copy_from_slice(&u32_to_hex(d));
376 result
377}
378
379#[inline]
380fn u32_to_hex(n: u32) -> [u8; 8] {
381 const SPLAT: u64 = 0x0101_0101_0101_0101;
382
383 let mut n = u64::from(n);
384 n = ((n & 0x0000_0000_FFFF_0000) << 16) | (n & 0x0000_0000_0000_FFFF);
387 n = ((n & 0x0000_FF00_0000_FF00) << 8) | (n & 0x0000_00FF_0000_00FF);
390 n = ((n & 0x00F0_00F0_00F0_00F0) << 4) | (n & 0x000F_000F_000F_000F);
393 let letter_positions = (n + ((128 - 10) * SPLAT)) & (128 * SPLAT);
396 let letter_mask = letter_positions - (letter_positions >> 7);
399 let hex = (n + u64::from(b'0') * SPLAT) + (letter_mask & (u64::from(b'a' - b'0' - 10) * SPLAT));
402 hex.to_be_bytes()
405}
406
407#[inline]
408fn u16_to_hex(n: u16) -> u32 {
409 const SPLAT: u32 = 0x0101_0101;
410
411 let mut n = u32::from(n);
412 n = ((n & 0x0000_FF00) << 8) | (n & 0x0000_00FF);
415 n = ((n & 0x000F_000F) << 8) | ((n & 0x00F0_00F0) >> 4);
418 let letter_positions = (n + ((128 - 10) * SPLAT)) & (128 * SPLAT);
421 let letter_mask = letter_positions - (letter_positions >> 7);
424 (n + u32::from(b'0') * SPLAT) + (letter_mask & (u32::from(b'a' - b'0' - 10) * SPLAT))
428}