parmesan-par2 0.6.0

Fast, standalone PAR2 (Reed-Solomon) creation, verification and repair tool
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
//! GF(2^16) arithmetic and the PAR2 Reed-Solomon matrix.
//!
//! PAR2 computes recovery data over the Galois field GF(2^16) with the
//! primitive polynomial `0x1100B` (x^16 + x^12 + x^3 + x + 1) and the
//! primitive element 2. Every detail here is matched bit-for-bit with
//! `par2cmdline` so the output is repairable by standard tools.
//!
//! ## The Reed-Solomon matrix
//!
//! Each recovery block has an integer **exponent** (0, 1, 2, …). Each input
//! block `i` is assigned a **base** constant `antilog(logbase_i)`, where
//! `logbase_i` is the i-th non-negative integer coprime with 65535 — the
//! multiplicative group order. Since `65535 = 3·5·17·257`, "coprime with
//! 65535" means "not divisible by 3, 5, 17 or 257". The matrix entry for
//! input block `i` and recovery exponent `e` is `base_i` raised to `e`.

/// Primitive polynomial of the field (x^16 + x^12 + x^3 + x + 1).
const POLYNOMIAL: u32 = 0x1_100B;

/// Order of the multiplicative group: `2^16 - 1`.
pub const ORDER: u32 = 65_535;

/// Maximum number of input blocks: the count of integers coprime with 65535,
/// i.e. `φ(65535) = φ(3)·φ(5)·φ(17)·φ(257) = 2·4·16·256`.
pub const MAX_INPUT_BLOCKS: usize = 32_768;

/// Maximum number of recovery blocks par2cmdline supports.
pub const MAX_RECOVERY_BLOCKS: usize = 65_535;

/// Greatest common divisor.
fn gcd(mut a: u32, mut b: u32) -> u32 {
    while b != 0 {
        let t = b;
        b = a % b;
        a = t;
    }
    a
}

/// The `logbase` exponents assigned to the first `count` input blocks: the
/// non-negative integers coprime with 65535, in order.
///
/// # Panics
///
/// Panics if `count` exceeds [`MAX_INPUT_BLOCKS`].
pub fn input_logbases(count: usize) -> Vec<u32> {
    assert!(
        count <= MAX_INPUT_BLOCKS,
        "PAR2 supports at most {MAX_INPUT_BLOCKS} input blocks, got {count}"
    );
    let mut out = Vec::with_capacity(count);
    let mut logbase = 0u32;
    while out.len() < count {
        if gcd(ORDER, logbase) == 1 {
            out.push(logbase);
        }
        logbase += 1;
    }
    out
}

/// The GF(2^16) field: the antilog (`2^i`) and log lookup tables.
#[derive(Debug, Clone)]
pub struct Gf16 {
    /// `antilog[i] = 2^i` for `i` in `0..65535`.
    antilog: Vec<u16>,
    /// `log[v]` is the exponent `i` such that `antilog[i] == v`; `log[0]`
    /// is unused.
    log: Vec<u16>,
}

impl Gf16 {
    /// Build the field lookup tables.
    pub fn new() -> Self {
        let mut antilog = vec![0u16; ORDER as usize];
        let mut log = vec![0u16; ORDER as usize + 1];
        let mut value: u32 = 1;
        for (i, slot) in antilog.iter_mut().enumerate() {
            *slot = value as u16;
            log[value as usize] = i as u16;
            value <<= 1;
            if value & 0x1_0000 != 0 {
                value ^= POLYNOMIAL;
            }
        }
        Self { antilog, log }
    }

    /// Multiply two field elements.
    pub fn mul(&self, a: u16, b: u16) -> u16 {
        if a == 0 || b == 0 {
            return 0;
        }
        let exponent = self.log[a as usize] as u32 + self.log[b as usize] as u32;
        self.antilog[(exponent % ORDER) as usize]
    }

    /// Raise a field element to an integer power.
    pub fn pow(&self, base: u16, exponent: u32) -> u16 {
        if base == 0 {
            return u16::from(exponent == 0);
        }
        let log = self.log[base as usize] as u64;
        self.antilog[((log * exponent as u64) % ORDER as u64) as usize]
    }

    /// `2^exponent` in the field, with the exponent reduced modulo the group
    /// order. Note `discrete_log(exp(e)) == e % ORDER`.
    pub fn exp(&self, exponent: u32) -> u16 {
        self.antilog[(exponent % ORDER) as usize]
    }

    /// Discrete logarithm: the exponent `e` such that `exp(e) == value`.
    ///
    /// # Panics
    ///
    /// Panics if `value` is zero.
    pub fn discrete_log(&self, value: u16) -> u16 {
        assert!(value != 0, "zero has no discrete logarithm");
        self.log[value as usize]
    }

    /// Multiplicative inverse: the value `v⁻¹` such that `mul(v, v⁻¹) == 1`.
    ///
    /// Every non-zero element of the multiplicative group has order dividing
    /// [`ORDER`], so `v⁻¹ == 2^(ORDER - log(v))`.
    ///
    /// # Panics
    ///
    /// Panics if `value` is zero (zero has no multiplicative inverse).
    pub fn inverse(&self, value: u16) -> u16 {
        let log = self.discrete_log(value) as u32;
        self.exp(ORDER - log)
    }

    /// The base constants assigned to the first `count` input blocks.
    pub fn input_bases(&self, count: usize) -> Vec<u16> {
        input_logbases(count)
            .into_iter()
            .map(|logbase| self.antilog[logbase as usize])
            .collect()
    }

    /// The Reed-Solomon coefficient applied to input block `input_index` when
    /// forming the recovery block with the given `exponent`.
    pub fn recovery_coefficient(&self, input_index: usize, exponent: u32) -> u16 {
        let logbase = input_logbases(input_index + 1)[input_index] as u64;
        self.antilog[((logbase * exponent as u64) % ORDER as u64) as usize]
    }
}

/// XOR bit-dependency matrix for multiplying by a constant in GF(2¹⁶).
///
/// Returns `deps` where `deps[k]` is a 16-bit mask: bit `j` is set when input
/// bit `j` contributes (via XOR) to output bit `k` of the product `input × coeff`.
///
/// Applying the matrix to a single word `x`:
/// ```ignore
/// let mut result = 0u16;
/// for k in 0..16 {
///     let bits = x & deps[k];
///     result |= (bits.count_ones() as u16 & 1) << k;
/// }
/// ```
///
/// For `coeff == 0` all entries are zero (product is always 0).
/// For `coeff == 1` the matrix is the identity.
///
/// The algorithm follows the "XOR Bit Dependencies" method from ParPar's
/// `fast-gf-multiplication.md`: simulate the shift-and-XOR multiplication in
/// GF(2¹⁶) symbolically, tracking which input bits reach each output bit.
pub fn xor_dep_matrix(coeff: u16) -> [u16; 16] {
    if coeff == 0 {
        return [0u16; 16];
    }

    // deps[k] = bitmask of input bits that XOR into output bit k.
    let mut deps = [0u16; 16];

    for b in (0..16).rev() {
        if (coeff >> b) & 1 == 1 {
            // This power of 2 is present in `coeff`; add its contribution
            // (the identity shifted into the current position).
            for (k, d) in deps.iter_mut().enumerate() {
                *d ^= 1 << k;
            }
        }

        if b > 0 {
            // Multiply the accumulated dependencies by 2 in GF(2¹⁶):
            // shift left by one bit position and XOR in the polynomial
            // for any term that overflowed bit 15.
            let high = deps[15];
            deps.copy_within(0..15, 1);
            deps[0] = 0;
            // POLYNOMIAL = 0x1_100B = x^16 + x^12 + x^3 + x + 1.
            // The bit positions of the lower 16 bits of the polynomial
            // are 0 (x^0), 1 (x^1), 3 (x^3), 12 (x^12).
            for k in [0usize, 1, 3, 12] {
                deps[k] ^= high;
            }
        }
    }

    deps
}

impl Default for Gf16 {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn table_sizes_and_first_powers_of_two() {
        let gf = Gf16::new();
        assert_eq!(gf.antilog.len(), 65_535);
        assert_eq!(gf.log.len(), 65_536);
        assert_eq!(gf.antilog[0], 1);
        assert_eq!(gf.antilog[1], 2);
        assert_eq!(gf.antilog[2], 4);
        // 2^16 wraps via the polynomial: 0x10000 ^ 0x1100B == 0x100B.
        assert_eq!(gf.antilog[16], 0x100B);
    }

    #[test]
    fn log_and_antilog_are_inverses() {
        let gf = Gf16::new();
        for exponent in 0..65_535u32 {
            let value = gf.antilog[exponent as usize];
            assert_eq!(gf.log[value as usize] as u32, exponent);
        }
        for value in 1..=65_535u32 {
            let exponent = gf.log[value as usize];
            assert_eq!(gf.antilog[exponent as usize] as u32, value);
        }
    }

    #[test]
    fn multiplication_basics_and_log_homomorphism() {
        let gf = Gf16::new();
        assert_eq!(gf.mul(0, 1234), 0);
        assert_eq!(gf.mul(1, 1234), 1234);
        assert_eq!(gf.mul(2, 2), 4);
        // mul(2^i, 2^j) == 2^((i + j) mod 65535)
        for &(i, j) in &[(3u32, 5u32), (100, 200), (60_000, 60_000)] {
            let product = gf.mul(gf.antilog[i as usize], gf.antilog[j as usize]);
            assert_eq!(product, gf.antilog[((i + j) % 65_535) as usize]);
        }
    }

    #[test]
    fn pow_matches_repeated_multiplication() {
        let gf = Gf16::new();
        assert_eq!(gf.pow(7, 0), 1);
        assert_eq!(gf.pow(7, 1), 7);
        for base in [2u16, 7, 12_345, 60_000] {
            let mut acc = 1u16;
            for exponent in 0..20u32 {
                assert_eq!(gf.pow(base, exponent), acc);
                acc = gf.mul(acc, base);
            }
        }
    }

    #[test]
    fn input_logbases_skip_factors_of_65535() {
        // 65535 = 3 * 5 * 17 * 257.
        let logbases = input_logbases(64);
        assert_eq!(&logbases[..4], &[1, 2, 4, 7]);
        for &logbase in &logbases {
            assert_ne!(logbase % 3, 0);
            assert_ne!(logbase % 5, 0);
            assert_ne!(logbase % 17, 0);
            assert_ne!(logbase % 257, 0);
        }
        // The sequence is strictly increasing.
        assert!(logbases.windows(2).all(|w| w[0] < w[1]));
    }

    #[test]
    fn input_bases_are_antilogs_of_the_logbases() {
        let gf = Gf16::new();
        // logbases 1, 2, 4, 7 -> antilog 2, 4, 16, 128.
        assert_eq!(gf.input_bases(4), vec![2, 4, 16, 128]);
    }

    #[test]
    fn recovery_coefficient_exponent_zero_is_one() {
        let gf = Gf16::new();
        for input_index in [0usize, 1, 5, 100] {
            assert_eq!(gf.recovery_coefficient(input_index, 0), 1);
        }
        // Exponent 1 yields the input block's own base constant.
        assert_eq!(gf.recovery_coefficient(0, 1), 2);
        assert_eq!(gf.recovery_coefficient(1, 1), 4);
        // base_0 = 2, so exponent 2 gives 2^2 = 4.
        assert_eq!(gf.recovery_coefficient(0, 2), 4);
    }

    #[test]
    fn inverse_is_the_multiplicative_inverse() {
        let gf = Gf16::new();
        assert_eq!(gf.inverse(1), 1);
        for value in [2u16, 3, 7, 12_345, 60_000, 65_535] {
            let inv = gf.inverse(value);
            assert_eq!(gf.mul(value, inv), 1, "value={value:#06x}");
        }
    }

    #[test]
    fn inverse_covers_every_nonzero_element() {
        let gf = Gf16::new();
        // Every non-zero element must have a valid inverse; spot-check a
        // representative spread rather than all 65535 for test speed.
        for exponent in (0..65_535u32).step_by(997) {
            let value = gf.exp(exponent);
            assert_eq!(gf.mul(value, gf.inverse(value)), 1);
        }
    }

    #[test]
    fn full_multiplicative_group_is_covered() {
        // Every non-zero value appears exactly once in the antilog table.
        let gf = Gf16::new();
        let mut seen = vec![false; 65_536];
        for &value in &gf.antilog {
            assert!(!seen[value as usize], "duplicate value {value}");
            assert_ne!(value, 0);
            seen[value as usize] = true;
        }
    }

    /// Apply a dependency matrix to a single u16 word.
    fn apply_dep_matrix(deps: &[u16; 16], x: u16) -> u16 {
        let mut result = 0u16;
        for (k, &mask) in deps.iter().enumerate() {
            let bits = x & mask;
            result |= (bits.count_ones() as u16 & 1) << k;
        }
        result
    }

    #[test]
    fn xor_dep_matrix_special_cases() {
        // coeff = 0: all-zero matrix, product always 0.
        let deps0 = xor_dep_matrix(0);
        assert_eq!(deps0, [0u16; 16]);
        for x in [0u16, 1, 0xFF, 0x1234, 0xFFFF] {
            assert_eq!(apply_dep_matrix(&deps0, x), 0);
        }

        // coeff = 1: identity matrix, product equals input.
        let deps1 = xor_dep_matrix(1);
        for k in 0..16u16 {
            assert_eq!(deps1[k as usize], 1 << k, "identity bit {k}");
        }
        for x in [0u16, 1, 0xFF, 0x1234, 0xFFFF] {
            assert_eq!(apply_dep_matrix(&deps1, x), x);
        }
    }

    #[test]
    fn xor_dep_matrix_matches_gf_mul_exhaustive() {
        // For a representative set of coefficients, verify that applying the
        // dependency matrix to every 16-bit input matches gf.mul(input, coeff).
        let gf = Gf16::new();
        let test_coeffs: &[u16] = &[
            2, 3, 4, 7, 16, 128, 256, 1000, 0x1234, 0x8000, 0xABCD, 0xFFFE, 65534,
        ];
        for &coeff in test_coeffs {
            let deps = xor_dep_matrix(coeff);
            for x in 0u32..=65535 {
                let x = x as u16;
                let expected = gf.mul(x, coeff);
                let got = apply_dep_matrix(&deps, x);
                assert_eq!(
                    got, expected,
                    "coeff={coeff:#06x} x={x:#06x}: expected {expected:#06x}, got {got:#06x}"
                );
            }
        }
    }

    #[test]
    fn xor_dep_matrix_matches_gf_mul_all_coefficients() {
        // Spot-check all 65535 non-zero coefficients against a random input.
        // Using a fixed seed (the input value 0xA5C3) keeps the test deterministic.
        let gf = Gf16::new();
        let x: u16 = 0xA5C3;
        for coeff in 1u16..=65535 {
            let deps = xor_dep_matrix(coeff);
            let expected = gf.mul(x, coeff);
            let got = apply_dep_matrix(&deps, x);
            assert_eq!(
                got, expected,
                "coeff={coeff:#06x}: expected {expected:#06x}, got {got:#06x}"
            );
        }
    }
}