Skip to main content

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}