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

aoc/year2016/
day05.rs
