aoc/year2016/
day05.rs

1//! # How About a Nice Game of Chess?
2//!
3//! Essentially a repeat of [`Year 2015 Day 4`]. We brute force MD5 hashes as quickly as
4//! possible in parallel in blocks of 1000 at a time.
5//!
6//! [`Year 2015 Day 4`]: crate::year2015::day04
7use crate::util::md5::*;
8use crate::util::thread::*;
9use std::sync::Mutex;
10
11struct Shared {
12    prefix: String,
13    iter: AtomicIter,
14    mutex: Mutex<Exclusive>,
15}
16
17struct Exclusive {
18    found: Vec<(u32, u32)>,
19    mask: u16,
20}
21
22pub fn parse(input: &str) -> Vec<u32> {
23    let shared = Shared {
24        prefix: input.trim().to_owned(),
25        iter: AtomicIter::new(1000, 1000),
26        mutex: Mutex::new(Exclusive { found: vec![], mask: 0 }),
27    };
28
29    // Handle the first 999 numbers specially as the number of digits varies.
30    for n in 1..1000 {
31        let (mut buffer, size) = format_string(&shared.prefix, n);
32        check_hash(&mut buffer, size, n, &shared);
33    }
34
35    // Use as many cores as possible to parallelize the remaining search.
36    spawn(|| {
37        #[cfg(not(feature = "simd"))]
38        worker(&shared);
39        #[cfg(feature = "simd")]
40        simd::worker(&shared);
41    });
42
43    let mut found = shared.mutex.into_inner().unwrap().found;
44    found.sort_unstable();
45    found.iter().map(|&(_, n)| n).collect()
46}
47
48pub fn part1(input: &[u32]) -> String {
49    let password = input.iter().take(8).fold(0, |acc, n| (acc << 4) | (n >> 8));
50    format!("{password:08x}")
51}
52
53pub fn part2(input: &[u32]) -> String {
54    let mut password = 0;
55    let mut mask = 0xffffffff;
56
57    for n in input {
58        let sixth = n >> 8;
59        if sixth < 8 {
60            let shift = 4 * (7 - sixth);
61            let seventh = (n >> 4) & 0xf;
62            password |= (seventh << shift) & mask;
63            mask &= !(0xf << shift);
64        }
65    }
66
67    format!("{password:08x}")
68}
69
70fn format_string(prefix: &str, n: u32) -> ([u8; 64], usize) {
71    let string = format!("{prefix}{n}");
72    let size = string.len();
73
74    let mut buffer = [0; 64];
75    buffer[0..size].copy_from_slice(string.as_bytes());
76
77    (buffer, size)
78}
79
80fn check_hash(buffer: &mut [u8], size: usize, n: u32, shared: &Shared) {
81    let [result, ..] = hash(buffer, size);
82
83    if result & 0xfffff000 == 0 {
84        let mut exclusive = shared.mutex.lock().unwrap();
85
86        exclusive.found.push((n, result));
87        exclusive.mask |= 1 << (result >> 8);
88
89        if exclusive.mask & 0xff == 0xff {
90            shared.iter.stop();
91        }
92    }
93}
94
95#[cfg(not(feature = "simd"))]
96fn worker(shared: &Shared) {
97    while let Some(offset) = shared.iter.next() {
98        let (mut buffer, size) = format_string(&shared.prefix, offset);
99
100        for n in 0..1000 {
101            // Format macro is very slow, so update digits directly
102            buffer[size - 3] = b'0' + (n / 100) as u8;
103            buffer[size - 2] = b'0' + ((n / 10) % 10) as u8;
104            buffer[size - 1] = b'0' + (n % 10) as u8;
105
106            check_hash(&mut buffer, size, offset + n, shared);
107        }
108    }
109}
110
111#[cfg(feature = "simd")]
112mod simd {
113    use super::*;
114    use crate::util::bitset::*;
115    use crate::util::md5::simd::hash_fixed;
116    use std::simd::cmp::SimdPartialEq as _;
117    use std::simd::*;
118
119    #[expect(clippy::needless_range_loop)]
120    fn check_hash_simd<const N: usize>(
121        buffers: &mut [[u8; 64]; N],
122        size: usize,
123        start: u32,
124        offset: u32,
125        shared: &Shared,
126    ) where
127        LaneCount<N>: SupportedLaneCount,
128    {
129        // Format macro is very slow, so update digits directly
130        for i in 0..N {
131            let n = offset + i as u32;
132            buffers[i][size - 3] = b'0' + (n / 100) as u8;
133            buffers[i][size - 2] = b'0' + ((n / 10) % 10) as u8;
134            buffers[i][size - 1] = b'0' + (n % 10) as u8;
135        }
136
137        let [result, ..] = hash_fixed(buffers, size);
138        let bitmask = (result & Simd::splat(0xfffff000)).simd_eq(Simd::splat(0)).to_bitmask();
139
140        if bitmask != 0 {
141            let mut exclusive = shared.mutex.lock().unwrap();
142
143            for i in bitmask.biterator() {
144                exclusive.found.push((start + offset + i as u32, result[i]));
145                exclusive.mask |= 1 << (result[i] >> 8);
146
147                if exclusive.mask & 0xff == 0xff {
148                    shared.iter.stop();
149                }
150            }
151        }
152    }
153
154    pub(super) fn worker(shared: &Shared) {
155        while let Some(start) = shared.iter.next() {
156            let (prefix, size) = format_string(&shared.prefix, start);
157            let buffers = &mut [prefix; 32];
158
159            for offset in (0..992).step_by(32) {
160                check_hash_simd(buffers, size, start, offset, shared);
161            }
162
163            let buffers = &mut [prefix; 8];
164            check_hash_simd(buffers, size, start, 992, shared);
165        }
166    }
167}
aoc/year2016/day05.rs

aoc/year2016/
day05.rs
