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

// Copyright 2023 Ulvetanna Inc.

//! Linear error-correcting code traits.

use binius_field::{ExtensionField, PackedField, RepackedExtension};

/// An encodable [linear error-correcting code](https://en.wikipedia.org/wiki/Linear_code) intended
/// for use in a Brakedown-style polynomial commitment scheme.
///
/// This trait represents linear codes with a dimension that is a power of 2, as that property is
/// required for the Brakedown polynomial commitment scheme.
///
/// Requirements:
/// - `len()` is a multiple of `dim()`
/// - `dim()` is a power of 2
/// - `dim()` is a multiple of `P::WIDTH`
#[allow(clippy::len_without_is_empty)]
pub trait LinearCode {
	type P: PackedField;
	type EncodeError: std::error::Error + Send + Sync + 'static;

	/// The block length.
	fn len(&self) -> usize {
		self.dim() * self.inv_rate()
	}

	/// The base-2 log of the dimension.
	fn dim_bits(&self) -> usize;

	/// The dimension.
	fn dim(&self) -> usize {
		1 << self.dim_bits()
	}

	/// The minimum distance between codewords.
	fn min_dist(&self) -> usize;

	/// The reciprocal of the rate, ie. `self.len() / self.dim()`.
	fn inv_rate(&self) -> usize;

	/// Encode a message in-place in a provided buffer.
	///
	/// Returns an error if the `code` buffer does not have capacity for `len()` field elements.
	fn encode_inplace(&self, code: &mut [Self::P]) -> Result<(), Self::EncodeError> {
		self.encode_batch_inplace(code, 0)
	}

	/// Encode a message in-place in a provided buffer.
	///
	/// Returns an error if the `code` buffer does not have capacity for `len()` field elements.
	fn encode_batch_inplace(
		&self,
		code: &mut [Self::P],
		log_batch_size: usize,
	) -> Result<(), Self::EncodeError>;

	/// Encode a message provided as a vector of packed field elements.
	fn encode(&self, mut msg: Vec<Self::P>) -> Result<Vec<Self::P>, Self::EncodeError> {
		msg.resize(msg.len() * self.inv_rate(), Self::P::default());
		self.encode_inplace(&mut msg)?;
		Ok(msg)
	}
}

/// A linear code the with additional ability to encode packed extension field elements.
///
/// A linear code can be naturally extended to a code over extension fields by encoding each
/// dimension of the extension as a vector-space separately. However, a naive encoding procedure
/// would not be able to access elements in the most memory-efficient manner, hence the separate
/// trait.
pub trait LinearCodeWithExtensionEncoding: LinearCode {
	/// Encode a message of extension field elements in-place in a provided buffer.
	///
	/// Returns an error if the `code` buffer does not have capacity for `len()` field elements.
	fn encode_extension_inplace<PE>(&self, code: &mut [PE]) -> Result<(), Self::EncodeError>
	where
		PE: RepackedExtension<Self::P>,
		PE::Scalar: ExtensionField<<Self::P as PackedField>::Scalar>;

	/// Encode a message of extension field elements provided as a vector of packed field elements.
	fn encode_extension<PE>(&self, mut msg: Vec<PE>) -> Result<Vec<PE>, Self::EncodeError>
	where
		PE: RepackedExtension<Self::P>,
		PE::Scalar: ExtensionField<<Self::P as PackedField>::Scalar>,
	{
		msg.resize(msg.len() * self.inv_rate(), PE::default());
		self.encode_extension_inplace(&mut msg)?;
		Ok(msg)
	}
}