aoc/year2016/
day14.rs

1//! # One-Time Pad
2//!
3//! Brute force slog through all possible keys, parallelized as much as possible. An optimization
4//! for part two is a quick method to convert `u32` to 8 ASCII digits.
5use crate::util::md5::*;
6use crate::util::thread::*;
7use std::collections::{BTreeMap, BTreeSet};
8use std::sync::Mutex;
9use std::sync::atomic::{AtomicBool, AtomicI32, Ordering};
10
11/// Atomics can be safely shared between threads.
12struct Shared<'a> {
13    input: &'a str,
14    part_two: bool,
15    done: AtomicBool,
16    counter: AtomicI32,
17    mutex: Mutex<Exclusive>,
18}
19
20/// Regular data structures need to be protected by a mutex.
21struct Exclusive {
22    threes: BTreeMap<i32, u32>,
23    fives: BTreeMap<i32, u32>,
24    found: BTreeSet<i32>,
25}
26
27pub fn parse(input: &str) -> &str {
28    input.trim()
29}
30
31/// Hash each key once.
32pub fn part1(input: &str) -> i32 {
33    generate_pad(input, false)
34}
35
36/// Hash each key an additional 2016 times.
37pub fn part2(input: &str) -> i32 {
38    generate_pad(input, true)
39}
40
41/// Find the first 64 keys that sastify the rules.
42fn generate_pad(input: &str, part_two: bool) -> i32 {
43    let exclusive =
44        Exclusive { threes: BTreeMap::new(), fives: BTreeMap::new(), found: BTreeSet::new() };
45    let shared = Shared {
46        input,
47        part_two,
48        done: AtomicBool::new(false),
49        counter: AtomicI32::new(0),
50        mutex: Mutex::new(exclusive),
51    };
52
53    // Use as many cores as possible to parallelize the search.
54    spawn(|| worker(&shared));
55
56    let exclusive = shared.mutex.into_inner().unwrap();
57    *exclusive.found.iter().nth(63).unwrap()
58}
59
60#[cfg(not(feature = "simd"))]
61fn worker(shared: &Shared<'_>) {
62    while !shared.done.load(Ordering::Relaxed) {
63        // Get the next key to check.
64        let n = shared.counter.fetch_add(1, Ordering::Relaxed);
65
66        // Calculate the hash.
67        let (mut buffer, size) = format_string(shared.input, n);
68        let mut result = hash(&mut buffer, size);
69
70        if shared.part_two {
71            for _ in 0..2016 {
72                buffer[0..8].copy_from_slice(&to_ascii(result.0));
73                buffer[8..16].copy_from_slice(&to_ascii(result.1));
74                buffer[16..24].copy_from_slice(&to_ascii(result.2));
75                buffer[24..32].copy_from_slice(&to_ascii(result.3));
76                result = hash(&mut buffer, 32);
77            }
78        }
79
80        check(shared, n, result);
81    }
82}
83
84/// Use SIMD to compute hashes in parallel in blocks of 32.
85#[cfg(feature = "simd")]
86#[expect(clippy::needless_range_loop)]
87fn worker(shared: &Shared<'_>) {
88    let mut result = ([0; 32], [0; 32], [0; 32], [0; 32]);
89    let mut buffers = [[0; 64]; 32];
90
91    while !shared.done.load(Ordering::Relaxed) {
92        // Get the next key to check.
93        let start = shared.counter.fetch_add(32, Ordering::Relaxed);
94
95        // Calculate the hash.
96        for i in 0..32 {
97            let (mut buffer, size) = format_string(shared.input, start + i as i32);
98            let (a, b, c, d) = hash(&mut buffer, size);
99
100            result.0[i] = a;
101            result.1[i] = b;
102            result.2[i] = c;
103            result.3[i] = d;
104        }
105
106        if shared.part_two {
107            for _ in 0..2016 {
108                for i in 0..32 {
109                    buffers[i][0..8].copy_from_slice(&to_ascii(result.0[i]));
110                    buffers[i][8..16].copy_from_slice(&to_ascii(result.1[i]));
111                    buffers[i][16..24].copy_from_slice(&to_ascii(result.2[i]));
112                    buffers[i][24..32].copy_from_slice(&to_ascii(result.3[i]));
113                }
114                result = simd::hash::<32>(&mut buffers, 32);
115            }
116        }
117
118        for i in 0..32 {
119            let hash = (result.0[i], result.1[i], result.2[i], result.3[i]);
120            check(shared, start + i as i32, hash);
121        }
122    }
123}
124
125/// Check for sequences of 3 or 5 consecutive matching digits.
126fn check(shared: &Shared<'_>, n: i32, hash: (u32, u32, u32, u32)) {
127    let (a, b, c, d) = hash;
128
129    let mut prev = u32::MAX;
130    let mut same = 1;
131    let mut three = 0;
132    let mut five = 0;
133
134    for mut word in [d, c, b, a] {
135        for _ in 0..8 {
136            let next = word & 0xf;
137
138            if next == prev {
139                same += 1;
140            } else {
141                same = 1;
142            }
143
144            if same == 3 {
145                three = 1 << next;
146            }
147            if same == 5 {
148                five |= 1 << next;
149            }
150
151            word >>= 4;
152            prev = next;
153        }
154    }
155
156    if three != 0 || five != 0 {
157        let mut exclusive = shared.mutex.lock().unwrap();
158        let mut candidates = Vec::new();
159
160        // Compare against all 5 digit sequences.
161        if three != 0 {
162            exclusive.threes.insert(n, three);
163
164            for (_, mask) in exclusive.fives.range(n + 1..n + 1001) {
165                if three & mask != 0 {
166                    candidates.push(n);
167                }
168            }
169        }
170
171        // Compare against all 3 digit sequences.
172        if five != 0 {
173            exclusive.fives.insert(n, five);
174
175            for (&index, &mask) in exclusive.threes.range(n - 1000..n) {
176                if five & mask != 0 {
177                    candidates.push(index);
178                }
179            }
180        }
181
182        // Add any matching keys found, finishing once we have at least 64 keys.
183        exclusive.found.extend(candidates);
184
185        if exclusive.found.len() >= 64 {
186            shared.done.store(true, Ordering::Relaxed);
187        }
188    }
189}
190
191/// Write the salt and integer index as ASCII characters.
192fn format_string(prefix: &str, n: i32) -> ([u8; 64], usize) {
193    let string = format!("{prefix}{n}");
194    let size = string.len();
195
196    let mut buffer = [0; 64];
197    buffer[0..size].copy_from_slice(string.as_bytes());
198
199    (buffer, size)
200}
201
202/// Quickly convert a `u32` to an array of 8 ASCII values.
203fn to_ascii(n: u32) -> [u8; 8] {
204    // Spread each nibble into its own byte, for example `1234abcd` becomes `010203040a0b0c0d`.
205    let mut n = n as u64;
206    n = ((n << 16) & 0x0000ffff00000000) | (n & 0x000000000000ffff);
207    n = ((n << 8) & 0x00ff000000ff0000) | (n & 0x000000ff000000ff);
208    n = ((n << 4) & 0x0f000f000f000f00) | (n & 0x000f000f000f000f);
209
210    // If a digit is 0 to 9 then we need to add `0x30` to convert to an ASCII digit.
211    // For digits from 10 to 15 we need to further add `0x27` to convert to lowercase ASCII.
212    // Steps:
213    // * Add 6 to each digit
214    // * If digit is 10 or higher then the highest bit in each nibble will be set
215    // * Shift this bit to create a mask
216    // * Multiply mask by 0x27 to get ASCII conversion offset
217    // For example mask of `010203040a0b0c0d` is `0000000001010101`.
218
219    let mask = ((n + 0x0606060606060606) >> 4) & 0x0101010101010101;
220    n = n + 0x3030303030303030 + 0x27 * mask;
221    n.to_be_bytes()
222}
aoc/year2016/day14.rs

aoc/year2016/
day14.rs
