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

aoc/year2016/
day05.rs
