p3_commit/
encoder.rs

1//! Linear codes applied column-wise to a matrix.
2
3use p3_dft::TwoAdicSubgroupDft;
4use p3_field::{Field, TwoAdicField};
5use p3_matrix::Matrix;
6use p3_matrix::dense::RowMajorMatrix;
7
8/// A linear code applied to every column of a matrix.
9///
10/// The blanket impl below covers every [`TwoAdicSubgroupDft`], which restricts what an
11/// implementor may write: `impl<F: Field> Encoder<F> for MyEncoder` overlaps it and is rejected
12/// (E0119), since a downstream crate could implement [`TwoAdicSubgroupDft`] for `MyEncoder`. An
13/// impl must therefore name the concrete field(s) it encodes over, as in
14/// `impl Encoder<MyField> for MyEncoder`.
15///
16/// The randomized counterpart is `p3_zk_codes::ZkEncoding`, whose codewords additionally hide the
17/// message from a bounded number of queries.
18pub trait Encoder<F: Field> {
19    /// Encodes each column of `message` into a codeword.
20    ///
21    /// `message` has height `2^k`; the result has the same width and height
22    /// `2^(k + log_inv_rate)`. Output row `i` is codeword symbol `i`.
23    ///
24    /// # Panics
25    /// Panics if the height of `message` is not a power of two, or if the codeword height
26    /// `2^(k + log_inv_rate)` overflows `usize`.
27    fn encode_batch(&self, message: RowMajorMatrix<F>, log_inv_rate: usize) -> RowMajorMatrix<F>;
28}
29
30/// Reed-Solomon over the two-adic subgroup of order `2^(k + log_inv_rate)`: each column of
31/// `message` is the low-degree coefficient vector of a polynomial, and the codeword is its
32/// evaluation vector on that subgroup.
33impl<F: TwoAdicField, D: TwoAdicSubgroupDft<F>> Encoder<F> for D {
34    fn encode_batch(
35        &self,
36        mut message: RowMajorMatrix<F>,
37        log_inv_rate: usize,
38    ) -> RowMajorMatrix<F> {
39        if log_inv_rate > 0 {
40            // Appending zero rows extends every column's coefficient vector.
41            let len = message.values.len();
42            let padded_len = u32::try_from(log_inv_rate)
43                .ok()
44                .and_then(|rate| len.checked_shl(rate))
45                // `checked_shl` only rejects a shift amount that is too wide; it does not
46                // detect the value itself overflowing, so recovering `len` from the shifted
47                // result is what actually proves no bits were lost.
48                .filter(|&padded| padded >> log_inv_rate == len)
49                .expect("codeword length overflows usize");
50            let mut values = F::zero_vec(padded_len);
51            values[..len].copy_from_slice(&message.values);
52            message.values = values;
53        }
54        self.dft_batch(message).to_row_major_matrix()
55    }
56}
57
58#[cfg(test)]
59mod tests {
60    use alloc::vec;
61
62    use p3_baby_bear::BabyBear;
63    use p3_dft::{Radix2DFTSmallBatch, Radix2DitParallel, TwoAdicSubgroupDft};
64    use p3_field::PrimeCharacteristicRing;
65    use p3_matrix::Matrix;
66    use p3_matrix::dense::RowMajorMatrix;
67    use rand::SeedableRng;
68    use rand::rngs::SmallRng;
69
70    use super::Encoder;
71
72    /// `encode_batch` must agree with zero-padding the message and calling `dft_batch`.
73    fn check_matches_padded_dft<D: TwoAdicSubgroupDft<BabyBear>>(dft: &D) {
74        let mut rng = SmallRng::seed_from_u64(1);
75        let message = RowMajorMatrix::<BabyBear>::rand(&mut rng, 8, 3);
76
77        let mut padded = message.clone();
78        padded
79            .values
80            .resize(message.values.len() * 4, BabyBear::ZERO);
81        let expected = dft.dft_batch(padded).to_row_major_matrix();
82
83        assert_eq!(dft.encode_batch(message, 2), expected);
84    }
85
86    #[test]
87    fn small_batch_encoder_matches_padded_dft() {
88        check_matches_padded_dft(&Radix2DFTSmallBatch::<BabyBear>::default());
89    }
90
91    #[test]
92    fn dit_parallel_encoder_matches_padded_dft() {
93        check_matches_padded_dft(&Radix2DitParallel::<BabyBear>::default());
94    }
95
96    #[test]
97    #[should_panic = "codeword length overflows usize"]
98    fn encode_batch_panics_when_the_codeword_length_overflows() {
99        let message = RowMajorMatrix::<BabyBear>::new(vec![BabyBear::ZERO; 2], 1);
100        let _ = Radix2DitParallel::<BabyBear>::default()
101            .encode_batch(message, usize::BITS as usize - 1);
102    }
103}
p3_commit/encoder.rs

p3_commit/
encoder.rs
