parmesan/decoder.rs
1//! Reconstructs missing PAR2 input slices from available recovery blocks.
2//!
3//! [`RecoveryDecoder`] implements the algorithm described in `ROADMAP.md`
4//! Phase 22: subtract every known input slice's contribution from a chosen
5//! set of recovery blocks (one per missing slice), invert the resulting
6//! reduced matrix, and multiply through to recover the missing data. See
7//! [`crate::matrix`] for the matrix algebra and [`crate::gf16_mac`] for the
8//! multiply-accumulate primitive both steps share.
9//!
10//! This decoder is independent of file layout: it works entirely in terms
11//! of global input-slice indices (the same indexing `RecoveryEncoder` uses)
12//! and asks its caller for bytes via a callback, so it never has to know
13//! about paths, `RecoverySet`, or on-disk formats. [`crate::repair`] is
14//! where those pieces meet.
15
16use crate::gf16::{input_logbases, Gf16};
17use crate::gf16_mac::mac;
18use crate::matrix::Gf16Matrix;
19use anyhow::{bail, Context, Result};
20use rayon::prelude::*;
21use std::collections::{BTreeMap, BTreeSet};
22
23/// Reconstructs a set of missing PAR2 input slices.
24pub struct RecoveryDecoder {
25 gf: Gf16,
26 slice_size: usize,
27 logbases: Vec<u32>,
28 total_input_slices: usize,
29 missing: Vec<usize>,
30}
31
32impl RecoveryDecoder {
33 /// Build a decoder for `total_input_slices` input slices of `slice_size`
34 /// bytes each, where the global indices listed in `missing` need
35 /// reconstruction.
36 ///
37 /// # Panics
38 ///
39 /// Panics if `missing` is empty or any index in it is
40 /// `>= total_input_slices`.
41 pub fn new(slice_size: usize, total_input_slices: usize, mut missing: Vec<usize>) -> Self {
42 assert!(
43 !missing.is_empty(),
44 "RecoveryDecoder: nothing to reconstruct"
45 );
46 missing.sort_unstable();
47 missing.dedup();
48 assert!(
49 *missing.last().unwrap() < total_input_slices,
50 "RecoveryDecoder: missing index {} is out of range for {total_input_slices} slices",
51 missing.last().unwrap()
52 );
53 Self {
54 gf: Gf16::new(),
55 slice_size,
56 logbases: input_logbases(total_input_slices),
57 total_input_slices,
58 missing,
59 }
60 }
61
62 /// Global indices this decoder will reconstruct, ascending.
63 pub fn missing(&self) -> &[usize] {
64 &self.missing
65 }
66
67 /// Reconstruct every missing slice.
68 ///
69 /// `known_slice(i)` must return the padded, slice-sized bytes of known
70 /// (non-missing) global input slice `i`. It is called exactly once per
71 /// known slice, in ascending order — a caller reading from disk pays for
72 /// one sequential pass over the surviving data, not one pass per missing
73 /// slice.
74 ///
75 /// `recovery_blocks` must hold at least `self.missing().len()` entries;
76 /// the lowest-exponent blocks available are used first (an arbitrary but
77 /// deterministic choice). Consecutive exponents always form an invertible
78 /// matrix; a non-consecutive selection, left after some recovery blocks
79 /// were lost, can be singular (see the [`crate::matrix`] module docs).
80 ///
81 /// Returns `(global_index, slice_bytes)` pairs, one per entry of
82 /// [`missing`](Self::missing), in the same order.
83 pub fn reconstruct(
84 &self,
85 mut known_slice: impl FnMut(usize) -> Result<Vec<u8>>,
86 recovery_blocks: &BTreeMap<u32, Vec<u8>>,
87 ) -> Result<Vec<(usize, Vec<u8>)>> {
88 let m = self.missing.len();
89 if recovery_blocks.len() < m {
90 bail!(
91 "not enough recovery blocks to repair {m} missing slice(s): only {} available",
92 recovery_blocks.len()
93 );
94 }
95
96 let exponents: Vec<u32> = recovery_blocks.keys().take(m).copied().collect();
97 let bases: Vec<u16> = self
98 .missing
99 .iter()
100 .map(|&i| self.gf.exp(self.logbases[i]))
101 .collect();
102
103 let mut adjusted: Vec<Vec<u8>> = Vec::with_capacity(m);
104 for e in &exponents {
105 let block = &recovery_blocks[e];
106 anyhow::ensure!(
107 block.len() == self.slice_size,
108 "recovery block (exponent {e}) has the wrong length: expected {}, got {}",
109 self.slice_size,
110 block.len()
111 );
112 adjusted.push(block.clone());
113 }
114
115 // Subtract each known slice's contribution from every selected
116 // recovery block in one pass, so the caller's `known_slice` reads
117 // each surviving slice from disk exactly once regardless of how
118 // many blocks are being reconstructed.
119 //
120 // The outer loop over `j` stays strictly sequential: `known_slice` is
121 // an `FnMut` and callers (see `crate::repair::SliceReader`) rely on
122 // ascending, one-at-a-time calls to keep a single file handle open
123 // across reads rather than reopening per slice. What *is*
124 // embarrassingly parallel is the inner loop: `m` (missing-slice
125 // count) independent `mac`s, one per row of `adjusted`, each writing
126 // to its own disjoint buffer from the one just-read `known_bytes`.
127 // On a repair with many missing slices — the case that dominates
128 // wall time, since this loop runs `total_input_slices` times — that
129 // inner width is real parallelism `par_iter_mut` can use without
130 // touching the I/O ordering at all. `Gf16` and `mac` are pure over
131 // `&self`/read-only `src`, so sharing `&self.gf` across the rayon
132 // pool here needs no synchronization.
133 let missing_set: BTreeSet<usize> = self.missing.iter().copied().collect();
134 for j in 0..self.total_input_slices {
135 if missing_set.contains(&j) {
136 continue;
137 }
138 let known_bytes =
139 known_slice(j).with_context(|| format!("reading known input slice {j}"))?;
140 anyhow::ensure!(
141 known_bytes.len() == self.slice_size,
142 "known slice {j} has the wrong length: expected {}, got {}",
143 self.slice_size,
144 known_bytes.len()
145 );
146 let base_j = self.gf.exp(self.logbases[j]);
147 adjusted
148 .par_iter_mut()
149 .zip(exponents.par_iter())
150 .for_each(|(row, &e)| {
151 let coeff = self.gf.pow(base_j, e);
152 mac(&self.gf, row, &known_bytes, coeff);
153 });
154 }
155
156 let a = Gf16Matrix::build_reduced(&self.gf, &bases, &exponents);
157 let inv = a
158 .invert(&self.gf)
159 .map_err(|e| anyhow::anyhow!("{e}"))
160 .context(
161 "the selected recovery/missing blocks produced a singular matrix \
162 (PAR2 does not guarantee an inverse when the available recovery \
163 blocks are not consecutive)",
164 )?;
165
166 // Each output slice `c` is an independent linear combination of the
167 // (shared, read-only at this point) `adjusted` rows — disjoint
168 // writes again, so this parallelizes the same way as the loop above.
169 let results: Vec<(usize, Vec<u8>)> = self
170 .missing
171 .par_iter()
172 .enumerate()
173 .map(|(c, &global_index)| {
174 let mut out = vec![0u8; self.slice_size];
175 for (r, adjusted_row) in adjusted.iter().enumerate() {
176 let coeff = inv.get(c, r);
177 if coeff != 0 {
178 mac(&self.gf, &mut out, adjusted_row, coeff);
179 }
180 }
181 (global_index, out)
182 })
183 .collect();
184
185 Ok(results)
186 }
187}
188
189#[cfg(test)]
190mod tests {
191 use super::*;
192 use crate::encoder::RecoveryEncoder;
193
194 fn make_slice(slice_size: usize, seed: u8) -> Vec<u8> {
195 (0..slice_size)
196 .map(|i| seed.wrapping_add(i as u8))
197 .collect()
198 }
199
200 fn encode(
201 slices: &[Vec<u8>],
202 slice_size: usize,
203 recovery_count: usize,
204 ) -> BTreeMap<u32, Vec<u8>> {
205 let mut enc = RecoveryEncoder::new(slice_size, slices.len(), 0, recovery_count);
206 for s in slices {
207 enc.add_slice(s.clone());
208 }
209 let (recovery_slices, _checksums) = enc.finish();
210 recovery_slices
211 .into_iter()
212 .map(|s| (s.exponent, s.data))
213 .collect()
214 }
215
216 #[test]
217 fn reconstructs_a_single_missing_slice() {
218 let slice_size = 64;
219 let n = 5;
220 let slices: Vec<Vec<u8>> = (0..n)
221 .map(|i| make_slice(slice_size, (i as u8).wrapping_mul(17).wrapping_add(3)))
222 .collect();
223 let recovery_blocks = encode(&slices, slice_size, n);
224
225 let missing_index = 2;
226 let dec = RecoveryDecoder::new(slice_size, n, vec![missing_index]);
227 let result = dec
228 .reconstruct(|j| Ok(slices[j].clone()), &recovery_blocks)
229 .unwrap();
230
231 assert_eq!(result.len(), 1);
232 assert_eq!(result[0].0, missing_index);
233 assert_eq!(result[0].1, slices[missing_index]);
234 }
235
236 #[test]
237 fn reconstructs_multiple_missing_slices_using_exactly_enough_recovery_blocks() {
238 let slice_size = 64;
239 let n = 10;
240 let slices: Vec<Vec<u8>> = (0..n)
241 .map(|i| make_slice(slice_size, (i as u8).wrapping_mul(31).wrapping_add(7)))
242 .collect();
243 let recovery_count = 4;
244 let recovery_blocks = encode(&slices, slice_size, recovery_count);
245
246 let missing = vec![1usize, 4, 7, 9];
247 let dec = RecoveryDecoder::new(slice_size, n, missing.clone());
248 let result = dec
249 .reconstruct(
250 |j| {
251 assert!(
252 !missing.contains(&j),
253 "decoder must never ask for a missing slice's bytes"
254 );
255 Ok(slices[j].clone())
256 },
257 &recovery_blocks,
258 )
259 .unwrap();
260
261 let got: BTreeMap<usize, Vec<u8>> = result.into_iter().collect();
262 for &idx in &missing {
263 assert_eq!(got[&idx], slices[idx], "slice {idx} mismatch");
264 }
265 }
266
267 #[test]
268 fn reconstructs_correctly_with_surplus_recovery_blocks() {
269 // More recovery blocks are available than are strictly needed; the
270 // decoder should still pick exactly `m` of them and succeed.
271 let slice_size = 32;
272 let n = 8;
273 let slices: Vec<Vec<u8>> = (0..n)
274 .map(|i| make_slice(slice_size, (i as u8).wrapping_mul(5).wrapping_add(1)))
275 .collect();
276 let recovery_blocks = encode(&slices, slice_size, 6); // n=8 missing=1, way more than needed
277
278 let missing_index = 3;
279 let dec = RecoveryDecoder::new(slice_size, n, vec![missing_index]);
280 let result = dec
281 .reconstruct(|j| Ok(slices[j].clone()), &recovery_blocks)
282 .unwrap();
283 assert_eq!(result[0].1, slices[missing_index]);
284 }
285
286 #[test]
287 fn errors_cleanly_when_not_enough_recovery_blocks() {
288 let slice_size = 64;
289 let n = 5;
290 let slices: Vec<Vec<u8>> = (0..n).map(|i| make_slice(slice_size, i as u8)).collect();
291 let recovery_blocks = encode(&slices, slice_size, 1);
292
293 let dec = RecoveryDecoder::new(slice_size, n, vec![0, 1]);
294 let result = dec.reconstruct(|j| Ok(slices[j].clone()), &recovery_blocks);
295 assert!(result.is_err());
296 }
297
298 #[test]
299 fn reconstructing_every_slice_at_once_still_works() {
300 let slice_size = 32;
301 let n = 6;
302 let slices: Vec<Vec<u8>> = (0..n)
303 .map(|i| make_slice(slice_size, (i as u8).wrapping_mul(41).wrapping_add(2)))
304 .collect();
305 let recovery_blocks = encode(&slices, slice_size, n);
306
307 let missing: Vec<usize> = (0..n).collect();
308 let dec = RecoveryDecoder::new(slice_size, n, missing.clone());
309 let result = dec
310 .reconstruct(
311 |_| unreachable!("no known slices exist in this test"),
312 &recovery_blocks,
313 )
314 .unwrap();
315
316 let got: BTreeMap<usize, Vec<u8>> = result.into_iter().collect();
317 for i in 0..n {
318 assert_eq!(got[&i], slices[i]);
319 }
320 }
321
322 mod props {
323 use super::*;
324 use proptest::prelude::*;
325
326 fn distinct_below(seed: u64, count: usize, bound: usize) -> Vec<usize> {
327 let mut lcg = seed | 1;
328 let mut set = std::collections::BTreeSet::new();
329 while set.len() < count {
330 lcg = lcg
331 .wrapping_mul(6364136223846793005)
332 .wrapping_add(1442695040888963407);
333 set.insert((lcg >> 32) as usize % bound);
334 }
335 set.into_iter().collect()
336 }
337
338 fn pseudo_random_bytes(seed: u64, len: usize) -> Vec<u8> {
339 let mut lcg = seed | 1;
340 (0..len)
341 .map(|_| {
342 lcg = lcg
343 .wrapping_mul(6364136223846793005)
344 .wrapping_add(1442695040888963407);
345 (lcg >> 56) as u8
346 })
347 .collect()
348 }
349
350 // Pinned regression check for the known CI-failing minimal inputs
351 // from issue #51. Across 9 observed CI failures (3 originally
352 // reported + 6 found later by scanning CI history), only these 3
353 // distinct (n, recovery_count) pairs have ever appeared, always with
354 // seed = 0 — despite the property covering n in 2..25 and
355 // recovery_count in 1..15 (360 combinations), and 9 independent
356 // proptest runs (each exploring 96 random cases) never landing on
357 // any *other* failing input. All 3 share a structural trait: `m =
358 // recovery_count.min(n) == n` (every input slice is missing — the
359 // "reconstruct everything" edge) *and* recovery_count > n (surplus
360 // recovery blocks are available, so `reconstruct` only uses the
361 // first n by exponent — see `exponents: ... .take(m)` above).
362 // recovery_count % 4 == 3 in all 3 known cases too, but that may be
363 // coincidental rather than essential — see the broader sweep below.
364 // Never reproduced locally so far — this exists to make each new
365 // investigation attempt (different core count, RAYON_NUM_THREADS,
366 // toolchain) trivially re-checkable without waiting on proptest to
367 // land on the same inputs by chance.
368 #[test]
369 fn known_ci_failing_inputs_from_issue_51() {
370 for (n, recovery_count) in [(2usize, 3usize), (5, 7), (9, 11)] {
371 let seed = 0u64;
372 let slice_size = 16;
373 let m = recovery_count.min(n);
374 let missing = distinct_below(seed, m, n);
375
376 let slices: Vec<Vec<u8>> = (0..n)
377 .map(|i| pseudo_random_bytes(seed ^ 0x9E3779B9 ^ (i as u64), slice_size))
378 .collect();
379 let recovery_blocks = encode(&slices, slice_size, recovery_count);
380
381 let dec = RecoveryDecoder::new(slice_size, n, missing.clone());
382 let result = dec
383 .reconstruct(|j| Ok(slices[j].clone()), &recovery_blocks)
384 .unwrap();
385
386 assert_eq!(
387 result.len(),
388 missing.len(),
389 "n={n} recovery_count={recovery_count}"
390 );
391 for (idx, data) in result {
392 assert_eq!(
393 data,
394 slices[idx].clone(),
395 "slice {idx} mismatch (n={n}, recovery_count={recovery_count}, missing={missing:?})"
396 );
397 }
398 }
399 }
400
401 // Exhaustively sweeps the structural condition every known CI
402 // failure shares — "reconstruct everything" (m == n) with surplus
403 // recovery blocks (recovery_count > n) — across n and surplus far
404 // beyond the 3 known points, and several seeds per point (not just
405 // 0), to check whether the trigger is that structural condition
406 // alone or something narrower (e.g. recovery_count % 4 == 3
407 // specifically, or seed == 0 specifically). Proptest's default 96
408 // cases per run, spread over the *entire* n/recovery_count/seed
409 // space, apparently doesn't sample this particular corner densely
410 // enough to hit it reliably even when it exists — this targets it
411 // directly instead of hoping general-purpose exploration finds it.
412 //
413 // Ran once (~200s, 960 real PAR2 encode/decode round trips) with
414 // zero mismatches found — the structural condition alone isn't
415 // sufficient to reproduce locally. `#[ignore]`d rather than run on
416 // every `cargo test`: too slow for routine/CI use, kept as an
417 // on-demand tool for the next investigation attempt
418 // (`cargo test -- --ignored everything_missing_with_surplus`).
419 #[test]
420 #[ignore]
421 fn everything_missing_with_surplus_recovery_blocks_sweep() {
422 let mut failures = Vec::new();
423 for n in 1usize..=20 {
424 for surplus in 1usize..=8 {
425 let recovery_count = n + surplus;
426 for seed in [0u64, 1, 2, 42, 12345, u64::MAX] {
427 let slice_size = 16;
428 let missing: Vec<usize> = (0..n).collect();
429
430 let slices: Vec<Vec<u8>> = (0..n)
431 .map(|i| {
432 pseudo_random_bytes(seed ^ 0x9E3779B9 ^ (i as u64), slice_size)
433 })
434 .collect();
435 let recovery_blocks = encode(&slices, slice_size, recovery_count);
436
437 let dec = RecoveryDecoder::new(slice_size, n, missing.clone());
438 let result = dec
439 .reconstruct(|j| Ok(slices[j].clone()), &recovery_blocks)
440 .unwrap();
441
442 for (idx, data) in result {
443 if data != slices[idx] {
444 failures.push((n, recovery_count, seed, idx));
445 }
446 }
447 }
448 }
449 }
450 assert!(
451 failures.is_empty(),
452 "{} mismatch(es) found: {:?}",
453 failures.len(),
454 &failures[..failures.len().min(20)]
455 );
456 }
457
458 proptest! {
459 #![proptest_config(ProptestConfig::with_cases(96))]
460
461 /// End-to-end: real `RecoveryEncoder` output, an arbitrary valid
462 /// subset of slices treated as missing, `RecoveryDecoder`
463 /// reconstructs every one of them bit-exact — across randomly
464 /// chosen slice counts, recovery counts, and which slices are
465 /// missing (including the "reconstruct everything" edge and
466 /// "just enough recovery blocks" edge).
467 #[test]
468 fn round_trip_reconstructs_arbitrary_missing_sets(
469 n in 2usize..25,
470 recovery_count in 1usize..15,
471 seed in any::<u64>(),
472 ) {
473 let slice_size = 16;
474 let m = recovery_count.min(n);
475 let missing = distinct_below(seed, m, n);
476
477 let slices: Vec<Vec<u8>> = (0..n)
478 .map(|i| pseudo_random_bytes(seed ^ 0x9E3779B9 ^ (i as u64), slice_size))
479 .collect();
480 let recovery_blocks = encode(&slices, slice_size, recovery_count);
481
482 let dec = RecoveryDecoder::new(slice_size, n, missing.clone());
483 let result = dec
484 .reconstruct(|j| Ok(slices[j].clone()), &recovery_blocks)
485 .unwrap();
486
487 let mismatched = result.iter().any(|(idx, data)| data != &slices[*idx]);
488 if mismatched {
489 // Diagnostic capture for issue #51: this failure has
490 // reproduced on CI 9 times and never once locally across
491 // three investigation rounds. Before failing, gather the
492 // two things the plain "minimal failing input" report
493 // never has: (1) whether it's a genuine data race (some
494 // retries of the *identical* inputs pass) or a
495 // deterministic environment-specific bug (every retry
496 // fails the same way), and (2) which SIMD tier and
497 // thread count this machine actually used, since that's
498 // exactly what differs between CI and every local
499 // attempt so far.
500 eprintln!(
501 "issue #51 diagnostic: mismatch at n={n} recovery_count={recovery_count} seed={seed}"
502 );
503 eprintln!(
504 " simd={} gfni={} nproc={}",
505 crate::detect_simd(),
506 {
507 #[cfg(target_arch = "x86_64")]
508 { std::is_x86_feature_detected!("gfni") }
509 #[cfg(not(target_arch = "x86_64"))]
510 { false }
511 },
512 std::thread::available_parallelism().map(|n| n.get()).unwrap_or(0),
513 );
514 for attempt in 1..=5 {
515 let retry = dec
516 .reconstruct(|j| Ok(slices[j].clone()), &recovery_blocks)
517 .unwrap();
518 let retry_mismatched =
519 retry.iter().any(|(idx, data)| data != &slices[*idx]);
520 eprintln!(
521 " retry {attempt} (same recovery_blocks): {}",
522 if retry_mismatched { "mismatch" } else { "MATCH (non-deterministic!)" }
523 );
524 }
525 // Encode fresh from the same slices too, in case the bug
526 // is in `encode` producing different bytes run-to-run
527 // (e.g. rayon scheduling) rather than in `reconstruct`.
528 let re_encoded = encode(&slices, slice_size, recovery_count);
529 eprintln!(
530 " re-encode produced identical recovery blocks: {}",
531 re_encoded == recovery_blocks
532 );
533 }
534
535 prop_assert_eq!(result.len(), missing.len());
536 for (idx, data) in result {
537 prop_assert_eq!(data, slices[idx].clone(), "slice {} mismatch", idx);
538 }
539 }
540 }
541 }
542}