binius_math/
binary_subspace.rs1use binius_field::BinaryField;
4use binius_utils::{bail, iter::IterExtensions};
5
6use super::error::Error;
7
8#[derive(Debug, Clone)]
13pub struct BinarySubspace<F: BinaryField> {
14 basis: Vec<F>,
15}
16
17impl<F: BinaryField> BinarySubspace<F> {
18 pub const fn new_unchecked(basis: Vec<F>) -> Self {
22 Self { basis }
23 }
24
25 pub fn with_dim(dim: usize) -> Result<Self, Error> {
34 let basis = (0..dim)
35 .map(|i| F::basis_checked(i).map_err(|_| Error::DomainSizeTooLarge))
36 .collect::<Result<_, _>>()?;
37 Ok(Self { basis })
38 }
39
40 pub fn reduce_dim(&self, dim: usize) -> Result<Self, Error> {
48 if dim > self.dim() {
49 bail!(Error::DomainSizeTooLarge);
50 }
51 Ok(Self {
52 basis: self.basis[..dim].to_vec(),
53 })
54 }
55
56 pub fn isomorphic<FIso>(&self) -> BinarySubspace<FIso>
58 where
59 FIso: BinaryField + From<F>,
60 {
61 BinarySubspace {
62 basis: self.basis.iter().copied().map(Into::into).collect(),
63 }
64 }
65
66 pub fn dim(&self) -> usize {
68 self.basis.len()
69 }
70
71 pub fn basis(&self) -> &[F] {
73 &self.basis
74 }
75
76 pub fn get(&self, index: usize) -> F {
77 self.basis
78 .iter()
79 .take(usize::BITS as usize)
80 .enumerate()
81 .fold(F::ZERO, |acc, (i, basis_i)| {
82 if (index >> i) & 1 != 0 {
83 acc + basis_i
84 } else {
85 acc
86 }
87 })
88 }
89
90 pub fn get_checked(&self, index: usize) -> Result<F, Error> {
91 if index >= 1 << self.basis.len() {
92 bail!(Error::ArgumentRangeError {
93 arg: "index".to_string(),
94 range: 0..1 << self.basis.len(),
95 });
96 }
97 Ok(self.get(index))
98 }
99
100 pub fn iter(&self) -> impl Iterator<Item = F> + '_ {
104 let last = if self.basis.len() < usize::BITS as usize {
105 (1 << self.basis.len()) - 1
106 } else {
107 usize::MAX
108 };
109 (0..=last).map_skippable(|i| self.get(i))
110 }
111}
112
113impl<F: BinaryField> Default for BinarySubspace<F> {
114 fn default() -> Self {
115 let basis = (0..F::DEGREE).map(|i| F::basis(i)).collect();
116 Self { basis }
117 }
118}
119
120#[cfg(test)]
121mod tests {
122 use assert_matches::assert_matches;
123 use binius_field::{BinaryField128b, BinaryField8b};
124
125 use super::*;
126
127 #[test]
128 fn test_default_binary_subspace_iterates_elements() {
129 let subspace = BinarySubspace::<BinaryField8b>::default();
130 for i in 0..=255 {
131 assert_eq!(subspace.get(i), BinaryField8b::new(i as u8));
132 }
133 }
134
135 #[test]
136 fn test_binary_subspace_range_error() {
137 let subspace = BinarySubspace::<BinaryField8b>::default();
138 assert_matches!(subspace.get_checked(256), Err(Error::ArgumentRangeError { .. }));
139 }
140
141 #[test]
142 fn test_default_large_binary_subspace_iterates_elements() {
143 let subspace = BinarySubspace::<BinaryField128b>::default();
144 for i in 0..=255 {
145 assert_eq!(subspace.get(i), BinaryField128b::new(i as u128));
146 }
147 }
148
149 #[test]
150 fn test_default_binary_subspace() {
151 let subspace = BinarySubspace::<BinaryField8b>::default();
152 assert_eq!(subspace.dim(), 8);
153 assert_eq!(subspace.basis().len(), 8);
154
155 assert_eq!(
156 subspace.basis(),
157 [
158 BinaryField8b::new(0b00000001),
159 BinaryField8b::new(0b00000010),
160 BinaryField8b::new(0b00000100),
161 BinaryField8b::new(0b00001000),
162 BinaryField8b::new(0b00010000),
163 BinaryField8b::new(0b00100000),
164 BinaryField8b::new(0b01000000),
165 BinaryField8b::new(0b10000000)
166 ]
167 );
168
169 let expected_elements: [u8; 256] = (0..=255).collect::<Vec<_>>().try_into().unwrap();
170
171 for (i, &expected) in expected_elements.iter().enumerate() {
172 assert_eq!(subspace.get(i), BinaryField8b::new(expected));
173 }
174 }
175
176 #[test]
177 fn test_with_dim_valid() {
178 let subspace = BinarySubspace::<BinaryField8b>::with_dim(3).unwrap();
179 assert_eq!(subspace.dim(), 3);
180 assert_eq!(subspace.basis().len(), 3);
181
182 assert_eq!(
183 subspace.basis(),
184 [
185 BinaryField8b::new(0b001),
186 BinaryField8b::new(0b010),
187 BinaryField8b::new(0b100)
188 ]
189 );
190
191 let expected_elements: [u8; 8] = [0b000, 0b001, 0b010, 0b011, 0b100, 0b101, 0b110, 0b111];
192
193 for (i, &expected) in expected_elements.iter().enumerate() {
194 assert_eq!(subspace.get(i), BinaryField8b::new(expected));
195 }
196 }
197
198 #[test]
199 fn test_with_dim_invalid() {
200 let result = BinarySubspace::<BinaryField8b>::with_dim(10);
201 assert_matches!(result, Err(Error::DomainSizeTooLarge));
202 }
203
204 #[test]
205 fn test_reduce_dim_valid() {
206 let subspace = BinarySubspace::<BinaryField8b>::with_dim(6).unwrap();
207 let reduced = subspace.reduce_dim(4).unwrap();
208 assert_eq!(reduced.dim(), 4);
209 assert_eq!(reduced.basis().len(), 4);
210
211 assert_eq!(
212 reduced.basis(),
213 [
214 BinaryField8b::new(0b0001),
215 BinaryField8b::new(0b0010),
216 BinaryField8b::new(0b0100),
217 BinaryField8b::new(0b1000)
218 ]
219 );
220
221 let expected_elements: [u8; 16] = (0..16).collect::<Vec<_>>().try_into().unwrap();
222
223 for (i, &expected) in expected_elements.iter().enumerate() {
224 assert_eq!(reduced.get(i), BinaryField8b::new(expected));
225 }
226 }
227
228 #[test]
229 fn test_reduce_dim_invalid() {
230 let subspace = BinarySubspace::<BinaryField8b>::with_dim(4).unwrap();
231 let result = subspace.reduce_dim(6);
232 assert_matches!(result, Err(Error::DomainSizeTooLarge));
233 }
234
235 #[test]
236 fn test_isomorphic_conversion() {
237 let subspace = BinarySubspace::<BinaryField8b>::with_dim(3).unwrap();
238 let iso_subspace: BinarySubspace<BinaryField128b> = subspace.isomorphic();
239 assert_eq!(iso_subspace.dim(), 3);
240 assert_eq!(iso_subspace.basis().len(), 3);
241
242 assert_eq!(
243 iso_subspace.basis(),
244 [
245 BinaryField128b::from(BinaryField8b::new(0b001)),
246 BinaryField128b::from(BinaryField8b::new(0b010)),
247 BinaryField128b::from(BinaryField8b::new(0b100))
248 ]
249 );
250 }
251
252 #[test]
253 fn test_get_checked_valid() {
254 let subspace = BinarySubspace::<BinaryField8b>::default();
255 for i in 0..256 {
256 assert!(subspace.get_checked(i).is_ok());
257 }
258 }
259
260 #[test]
261 fn test_get_checked_invalid() {
262 let subspace = BinarySubspace::<BinaryField8b>::default();
263 assert_matches!(subspace.get_checked(256), Err(Error::ArgumentRangeError { .. }));
264 }
265
266 #[test]
267 fn test_iterate_subspace() {
268 let subspace = BinarySubspace::<BinaryField8b>::with_dim(3).unwrap();
269 let elements: Vec<_> = subspace.iter().collect();
270 assert_eq!(elements.len(), 8);
271
272 let expected_elements: [u8; 8] = [0b000, 0b001, 0b010, 0b011, 0b100, 0b101, 0b110, 0b111];
273
274 for (i, &expected) in expected_elements.iter().enumerate() {
275 assert_eq!(elements[i], BinaryField8b::new(expected));
276 }
277 }
278}