binius_core/reed_solomon/
reed_solomon.rs

1// Copyright 2023-2025 Irreducible Inc.
2
3//! [Reed–Solomon] codes over binary fields.
4//!
5//! See [`ReedSolomonCode`] for details.
6
7use binius_field::{BinaryField, ExtensionField, PackedExtension, PackedField};
8use binius_math::BinarySubspace;
9use binius_ntt::{AdditiveNTT, NTTShape};
10use binius_utils::bail;
11use getset::{CopyGetters, Getters};
12
13use super::error::Error;
14
15/// [Reed–Solomon] codes over binary fields.
16///
17/// The Reed–Solomon code admits an efficient encoding algorithm over binary fields due to [LCH14].
18/// The additive NTT encoding algorithm encodes messages interpreted as the coefficients of a
19/// polynomial in a non-standard, novel polynomial basis and the codewords are the polynomial
20/// evaluations over a linear subspace of the field. See the [binius_ntt] crate for more details.
21///
22/// [Reed–Solomon]: <https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction>
23/// [LCH14]: <https://arxiv.org/abs/1404.3458>
24#[derive(Debug, Getters, CopyGetters)]
25pub struct ReedSolomonCode<F: BinaryField> {
26	#[get = "pub"]
27	subspace: BinarySubspace<F>,
28	log_dimension: usize,
29	#[get_copy = "pub"]
30	log_inv_rate: usize,
31}
32
33impl<F: BinaryField> ReedSolomonCode<F> {
34	pub fn new(log_dimension: usize, log_inv_rate: usize) -> Result<Self, Error> {
35		Self::with_subspace(
36			BinarySubspace::with_dim(log_dimension + log_inv_rate)?,
37			log_dimension,
38			log_inv_rate,
39		)
40	}
41
42	pub fn with_subspace(
43		subspace: BinarySubspace<F>,
44		log_dimension: usize,
45		log_inv_rate: usize,
46	) -> Result<Self, Error> {
47		if subspace.dim() != log_dimension + log_inv_rate {
48			return Err(Error::SubspaceDimensionMismatch);
49		}
50		Ok(Self {
51			subspace,
52			log_dimension,
53			log_inv_rate,
54		})
55	}
56
57	/// The dimension.
58	pub const fn dim(&self) -> usize {
59		1 << self.dim_bits()
60	}
61
62	pub const fn log_dim(&self) -> usize {
63		self.log_dimension
64	}
65
66	pub const fn log_len(&self) -> usize {
67		self.log_dimension + self.log_inv_rate
68	}
69
70	/// The block length.
71	#[allow(clippy::len_without_is_empty)]
72	pub const fn len(&self) -> usize {
73		1 << (self.log_dimension + self.log_inv_rate)
74	}
75
76	/// The base-2 log of the dimension.
77	const fn dim_bits(&self) -> usize {
78		self.log_dimension
79	}
80
81	/// The reciprocal of the rate, ie. `self.len() / self.dim()`.
82	pub const fn inv_rate(&self) -> usize {
83		1 << self.log_inv_rate
84	}
85
86	/// Encode a batch of interleaved messages in-place in a provided buffer.
87	///
88	/// The message symbols are interleaved in the buffer, which improves the cache-efficiency of
89	/// the encoding procedure. The interleaved codeword is stored in the buffer when the method
90	/// completes.
91	///
92	/// ## Throws
93	///
94	/// * If the `code` buffer does not have capacity for `len() << log_batch_size` field
95	///   elements.
96	fn encode_batch_inplace<P: PackedField<Scalar = F>, NTT: AdditiveNTT<F> + Sync>(
97		&self,
98		ntt: &NTT,
99		code: &mut [P],
100		log_batch_size: usize,
101	) -> Result<(), Error> {
102		if ntt.subspace(ntt.log_domain_size() - self.log_len()) != self.subspace {
103			bail!(Error::EncoderSubspaceMismatch);
104		}
105		let expected_buffer_len =
106			1 << (self.log_len() + log_batch_size).saturating_sub(P::LOG_WIDTH);
107		if code.len() != expected_buffer_len {
108			bail!(Error::IncorrectBufferLength {
109				expected: expected_buffer_len,
110				actual: code.len(),
111			});
112		}
113
114		let _scope = tracing::trace_span!(
115			"Reed–Solomon encode",
116			log_len = self.log_len(),
117			log_batch_size = log_batch_size,
118			symbol_bits = F::N_BITS,
119		)
120		.entered();
121
122		// Repeat the message to fill the entire buffer.
123
124		// First, if the message is less than the packing width, we need to repeat it to fill one
125		// packed element.
126		if self.dim() + log_batch_size < P::LOG_WIDTH {
127			let repeated_values = code[0]
128				.into_iter()
129				.take(1 << (self.log_dim() + log_batch_size))
130				.cycle();
131			code[0] = P::from_scalars(repeated_values);
132		}
133
134		// Repeat the packed message to fill the entire buffer.
135		let mut chunks =
136			code.chunks_mut(1 << (self.log_dim() + log_batch_size).saturating_sub(P::LOG_WIDTH));
137		let first_chunk = chunks.next().expect("code is not empty; checked above");
138		for chunk in chunks {
139			chunk.copy_from_slice(first_chunk);
140		}
141
142		let shape = NTTShape {
143			log_x: log_batch_size,
144			log_y: self.log_len(),
145			..Default::default()
146		};
147		ntt.forward_transform(code, shape, 0, self.log_inv_rate)?;
148		Ok(())
149	}
150
151	/// Encode a batch of interleaved messages of extension field elements in-place in a provided
152	/// buffer.
153	///
154	/// A linear code can be naturally extended to a code over extension fields by encoding each
155	/// dimension of the extension as a vector-space separately.
156	///
157	/// ## Preconditions
158	///
159	/// * `PE::Scalar::DEGREE` must be a power of two.
160	///
161	/// ## Throws
162	///
163	/// * If the `code` buffer does not have capacity for `len() << log_batch_size` field elements.
164	pub fn encode_ext_batch_inplace<PE: PackedExtension<F>, NTT: AdditiveNTT<F> + Sync>(
165		&self,
166		ntt: &NTT,
167		code: &mut [PE],
168		log_batch_size: usize,
169	) -> Result<(), Error> {
170		self.encode_batch_inplace(
171			ntt,
172			PE::cast_bases_mut(code),
173			log_batch_size + PE::Scalar::LOG_DEGREE,
174		)
175	}
176}
binius_core/reed_solomon/reed_solomon.rs

binius_core/reed_solomon/
reed_solomon.rs
