Skip to main content

utils/md5/
mod.rs

1//! Implementation of the MD5 hash function.
2//!
3//! **WARNING: Don't use MD5 for anything remotely security-sensitive!**
4//! This implementation is meant to be used for Advent of Code puzzles only.
5//!
6//! The vectorized versions hash multiple inputs of the same length at once, which provides a
7//! significant performance increase for the brute force puzzle solutions.
8use 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
21/// Fastest supported implementation, for dynamic dispatch.
22///
23/// Determined using a small microbenchmark at runtime, see [`multiversion!`](crate::multiversion!).
24pub static FASTEST: LazyLock<Version> = multiversion! { fastest(microbenchmark()) };
25
26/// Returns the MD5 hash of the input slice.
27///
28/// Wrapper around the [`scalar`] implementation.
29///
30/// # Examples
31///
32/// ```
33/// # use utils::md5::hash;
34/// assert_eq!(hash(b"").as_slice(), &[0xd41d8cd9, 0x8f00b204, 0xe9800998, 0xecf8427e]);
35/// assert_eq!(hash(b"Hello World").as_slice(), &[0xb10a8db1, 0x64e07541, 0x05b7a99b, 0xe72e3fe5]);
36/// ```
37#[must_use]
38pub fn hash(buf: &[u8]) -> [u32; 4] {
39    scalar::hash(buf)[0]
40}
41
42multiversion! {
43    use {crate::simd::*};
44
45    // The length of 1/2/3/4 bytes for each lane
46    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    /// [`multiversion!`] MD5 hash implementation.
52    ///
53    /// The bytes for each lane must be interweaved, and each lane must be the same length.
54    ///
55    /// # Examples
56    ///
57    /// For [`array128`](crate::simd::array128) with four lanes:
58    /// ```
59    /// # use utils::md5::{self, array128};
60    /// assert_eq!(
61    ///     array128::hash(b"hwafeobglrchlldiodej"),
62    ///     [
63    ///         md5::hash(b"hello"),
64    ///         md5::hash(b"world"),
65    ///         md5::hash(b"abcde"),
66    ///         md5::hash(b"fghij"),
67    ///     ],
68    /// );
69    #[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                    // 0x80 end marker after final byte
90                    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        // `state.map(|x| x.into());` doesn't always get vectorised
152        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    /// [`multiversion!`] MD5 key stretching implementation.
165    ///
166    /// For example, passing 2 will return `hash(to_hex(hash(to_hex(hash))))` for each lane.
167    ///
168    /// # Examples
169    ///
170    /// For [`array128`](crate::simd::array128) with four lanes:
171    /// ```
172    /// # use utils::md5::{self, array128};
173    /// let hashes = array128::hash(b"hwafeobglrchlldiodej");
174    /// assert_eq!(
175    ///     array128::stretch(hashes, 2),
176    ///     hashes.map(|hash| md5::hash(&md5::to_hex(md5::hash(&md5::to_hex(hash))))),
177    /// );
178    /// ```
179    #[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        // Reverse the to_hashes call at the end of hash
188        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            // Using a separate copy of this function for stretch is ~15% faster for 2016 day 14.
225            // The copy is optimized out, and the end marker and bit count become constants.
226            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/// Convert an MD5 hash to ASCII hex.
355///
356/// Implemented using bitwise operations on each [`u32`] to spread each nibble into separate bytes,
357/// followed by adding either '0' or 'a' to each byte using a bitmask.
358///
359/// # Examples
360///
361/// ```
362/// # use utils::md5::to_hex;
363/// assert_eq!(
364///     to_hex([0xd41d8cd9, 0x8f00b204, 0xe9800998, 0xecf8427e]),
365///     *b"d41d8cd98f00b204e9800998ecf8427e",
366/// );
367/// ```
368#[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 = 0x0000_0000_1234_ABCD
385
386    n = ((n & 0x0000_0000_FFFF_0000) << 16) | (n & 0x0000_0000_0000_FFFF);
387    // n = 0x0000_1234_0000_ABCD
388
389    n = ((n & 0x0000_FF00_0000_FF00) << 8) | (n & 0x0000_00FF_0000_00FF);
390    // n = 0x0012_0034_00AB_00CD
391
392    n = ((n & 0x00F0_00F0_00F0_00F0) << 4) | (n & 0x000F_000F_000F_000F);
393    // n = 0x0102_0304_0A0B_0C0D
394
395    let letter_positions = (n + ((128 - 10) * SPLAT)) & (128 * SPLAT);
396    // letter_positions = 0x0000_0000_8080_8080
397
398    let letter_mask = letter_positions - (letter_positions >> 7);
399    // letter_mask = 0x0000_0000_7F7F_7F7F
400
401    let hex = (n + u64::from(b'0') * SPLAT) + (letter_mask & (u64::from(b'a' - b'0' - 10) * SPLAT));
402    // hex = 0x3132_3334_6162_6364
403
404    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 = 0x0000_12AB
413
414    n = ((n & 0x0000_FF00) << 8) | (n & 0x0000_00FF);
415    // n = 0x0012_00AB
416
417    n = ((n & 0x000F_000F) << 8) | ((n & 0x00F0_00F0) >> 4);
418    // n = 0x0201_0B0A
419
420    let letter_positions = (n + ((128 - 10) * SPLAT)) & (128 * SPLAT);
421    // letter_positions = 0x0000_8080
422
423    let letter_mask = letter_positions - (letter_positions >> 7);
424    // letter_mask = 0x0000_7F7F
425
426    // 0x3231_6261
427    (n + u32::from(b'0') * SPLAT) + (letter_mask & (u32::from(b'a' - b'0' - 10) * SPLAT))
428}