binius_field/
packed_binary_field.rs

1// Copyright 2023-2025 Irreducible Inc.
2
3pub use crate::arch::{
4	packed_1::*, packed_2::*, packed_4::*, packed_8::*, packed_16::*, packed_32::*, packed_64::*,
5	packed_128::*, packed_256::*, packed_512::*, packed_aes_8::*, packed_aes_16::*,
6	packed_aes_32::*, packed_aes_64::*, packed_aes_128::*, packed_aes_256::*, packed_aes_512::*,
7};
8
9/// Common code to test different multiply, square and invert implementations
10#[cfg(test)]
11pub mod test_utils {
12	use crate::{
13		BinaryField, PackedField,
14		linear_transformation::PackedTransformationFactory,
15		underlier::{U1, U2, U4, WithUnderlier},
16	};
17
18	pub struct Unit;
19
20	impl From<U1> for Unit {
21		fn from(_: U1) -> Self {
22			Self
23		}
24	}
25
26	impl From<U2> for Unit {
27		fn from(_: U2) -> Self {
28			Self
29		}
30	}
31
32	impl From<U4> for Unit {
33		fn from(_: U4) -> Self {
34			Self
35		}
36	}
37
38	impl From<u8> for Unit {
39		fn from(_: u8) -> Self {
40			Self
41		}
42	}
43
44	impl From<u16> for Unit {
45		fn from(_: u16) -> Self {
46			Self
47		}
48	}
49
50	impl From<u32> for Unit {
51		fn from(_: u32) -> Self {
52			Self
53		}
54	}
55
56	impl From<u64> for Unit {
57		fn from(_: u64) -> Self {
58			Self
59		}
60	}
61
62	impl From<u128> for Unit {
63		fn from(_: u128) -> Self {
64			Self
65		}
66	}
67
68	impl From<[u128; 2]> for Unit {
69		fn from(_: [u128; 2]) -> Self {
70			Self
71		}
72	}
73
74	impl From<[u128; 4]> for Unit {
75		fn from(_: [u128; 4]) -> Self {
76			Self
77		}
78	}
79
80	/// We use such helper macros to run tests only for the
81	/// types that implement the `constraint` trait.
82	/// The idea is inspired by `impls` trait.
83	macro_rules! define_check_packed_mul {
84		($mult_func:path, $constraint:path) => {
85			#[allow(unused)]
86			trait TestMulTrait<T> {
87				fn test_mul(_a: T, _b: T) {}
88			}
89
90			impl<T> TestMulTrait<$crate::packed_binary_field::test_utils::Unit> for T {}
91
92			struct TestMult<T>(std::marker::PhantomData<T>);
93
94			impl<T: $constraint + PackedField + $crate::underlier::WithUnderlier> TestMult<T> {
95				#[allow(unused)]
96				fn test_mul(
97					a: <T as $crate::underlier::WithUnderlier>::Underlier,
98					b: <T as $crate::underlier::WithUnderlier>::Underlier,
99				) {
100					let a = T::from_underlier(a);
101					let b = T::from_underlier(b);
102
103					let c = $mult_func(a, b);
104					for i in 0..T::WIDTH {
105						assert_eq!(c.get(i), a.get(i) * b.get(i));
106					}
107				}
108			}
109		};
110	}
111
112	pub(crate) use define_check_packed_mul;
113
114	macro_rules! define_check_packed_square {
115		($square_func:path, $constraint:path) => {
116			#[allow(unused)]
117			trait TestSquareTrait<T> {
118				fn test_square(_a: T) {}
119			}
120
121			impl<T> TestSquareTrait<$crate::packed_binary_field::test_utils::Unit> for T {}
122
123			struct TestSquare<T>(std::marker::PhantomData<T>);
124
125			impl<T: $constraint + PackedField + $crate::underlier::WithUnderlier> TestSquare<T> {
126				#[allow(unused)]
127				fn test_square(a: <T as $crate::underlier::WithUnderlier>::Underlier) {
128					let a = T::from_underlier(a);
129
130					let c = $square_func(a);
131					for i in 0..T::WIDTH {
132						assert_eq!(c.get(i), a.get(i) * a.get(i));
133					}
134				}
135			}
136		};
137	}
138
139	pub(crate) use define_check_packed_square;
140
141	macro_rules! define_check_packed_inverse {
142		($invert_func:path, $constraint:path) => {
143			#[allow(unused)]
144			trait TestInvertTrait<T> {
145				fn test_invert(_a: T) {}
146			}
147
148			impl<T> TestInvertTrait<$crate::packed_binary_field::test_utils::Unit> for T {}
149
150			struct TestInvert<T>(std::marker::PhantomData<T>);
151
152			#[allow(unused)]
153			impl<T: $constraint + PackedField + $crate::underlier::WithUnderlier> TestInvert<T> {
154				fn test_invert(a: <T as $crate::underlier::WithUnderlier>::Underlier) {
155					use crate::Field;
156
157					let a = T::from_underlier(a);
158
159					let c = $invert_func(a);
160					for i in 0..T::WIDTH {
161						assert!(
162							(c.get(i).is_zero().into()
163								&& a.get(i).is_zero().into()
164								&& c.get(i).is_zero().into())
165								|| T::Scalar::ONE == a.get(i) * c.get(i)
166						);
167					}
168				}
169			}
170		};
171	}
172
173	pub(crate) use define_check_packed_inverse;
174
175	macro_rules! define_check_packed_transformation {
176		($constraint:path) => {
177			#[allow(unused)]
178			trait TestTransformationTrait<T> {
179				fn test_transformation(_a: T) {}
180			}
181
182			impl<T> TestTransformationTrait<$crate::packed_binary_field::test_utils::Unit> for T {}
183
184			struct TestTransformation<T>(std::marker::PhantomData<T>);
185
186			impl<T: $constraint + PackedField + $crate::underlier::WithUnderlier>
187				TestTransformation<T>
188			{
189				fn test_transformation(a: <T as $crate::underlier::WithUnderlier>::Underlier) {
190					use ::rand::prelude::*;
191					use $crate::linear_transformation::{
192						FieldLinearTransformation, Transformation,
193					};
194
195					let a = T::from_underlier(a);
196
197					// TODO: think how we can use random seed from proptests here
198					let rng = StdRng::seed_from_u64(0);
199					let field_transformation =
200						FieldLinearTransformation::<T::Scalar, _>::random(rng);
201					let packed_transformation =
202						T::make_packed_transformation(field_transformation.clone());
203
204					let c = packed_transformation.transform(&a);
205					for i in 0..T::WIDTH {
206						assert_eq!(c.get(i), field_transformation.transform(&a.get(i)));
207					}
208				}
209			}
210		};
211	}
212
213	pub(crate) use define_check_packed_transformation;
214
215	/// Test if `mult_func` operation is a valid multiply operation on the given values for
216	/// all possible packed fields defined on u128.
217	macro_rules! define_multiply_tests {
218		($mult_func:path, $constraint:path) => {
219			$crate::packed_binary_field::test_utils::define_check_packed_mul!(
220				$mult_func,
221				$constraint
222			);
223
224			proptest::proptest! {
225				#[test]
226				fn test_mul_packed_8(a_val in proptest::prelude::any::<u8>(), b_val in proptest::prelude::any::<u8>()) {
227					use $crate::arch::packed_8::*;
228					use $crate::arch::packed_aes_8::*;
229
230					TestMult::<PackedBinaryField8x1b>::test_mul(a_val.into(), b_val.into());
231					TestMult::<PackedAESBinaryField1x8b>::test_mul(a_val.into(), b_val.into());
232				}
233
234				#[test]
235				fn test_mul_packed_16(a_val in proptest::prelude::any::<u16>(), b_val in proptest::prelude::any::<u16>()) {
236					use $crate::arch::packed_16::*;
237					use $crate::arch::packed_aes_16::*;
238
239					TestMult::<PackedBinaryField16x1b>::test_mul(a_val.into(), b_val.into());
240					TestMult::<PackedAESBinaryField2x8b>::test_mul(a_val.into(), b_val.into());
241				}
242
243				#[test]
244				fn test_mul_packed_32(a_val in proptest::prelude::any::<u32>(), b_val in proptest::prelude::any::<u32>()) {
245					use $crate::arch::packed_32::*;
246					use $crate::arch::packed_aes_32::*;
247
248					TestMult::<PackedBinaryField32x1b>::test_mul(a_val.into(), b_val.into());
249					TestMult::<PackedAESBinaryField4x8b>::test_mul(a_val.into(), b_val.into());
250				}
251
252				#[test]
253				fn test_mul_packed_64(a_val in proptest::prelude::any::<u64>(), b_val in proptest::prelude::any::<u64>()) {
254					use $crate::arch::packed_64::*;
255					use $crate::arch::packed_aes_64::*;
256
257					TestMult::<PackedBinaryField64x1b>::test_mul(a_val.into(), b_val.into());
258					TestMult::<PackedAESBinaryField8x8b>::test_mul(a_val.into(), b_val.into());
259				}
260
261				#[test]
262				fn test_mul_packed_128(a_val in proptest::prelude::any::<u128>(), b_val in proptest::prelude::any::<u128>()) {
263					use $crate::arch::packed_128::*;
264					use $crate::arch::packed_aes_128::*;
265					use $crate::arch::packed_ghash_128::*;
266
267					TestMult::<PackedBinaryField128x1b>::test_mul(a_val.into(), b_val.into());
268					TestMult::<PackedAESBinaryField16x8b>::test_mul(a_val.into(), b_val.into());
269					TestMult::<PackedBinaryGhash1x128b>::test_mul(a_val.into(), b_val.into());
270				}
271
272				#[test]
273				fn test_mul_packed_256(a_val in proptest::prelude::any::<[u128; 2]>(), b_val in proptest::prelude::any::<[u128; 2]>()) {
274					use $crate::arch::packed_256::*;
275					use $crate::arch::packed_aes_256::*;
276					use $crate::arch::packed_ghash_256::*;
277
278					TestMult::<PackedBinaryField256x1b>::test_mul(a_val.into(), b_val.into());
279					TestMult::<PackedAESBinaryField32x8b>::test_mul(a_val.into(), b_val.into());
280					TestMult::<PackedBinaryGhash2x128b>::test_mul(a_val.into(), b_val.into());
281				}
282
283				#[test]
284				fn test_mul_packed_512(a_val in proptest::prelude::any::<[u128; 4]>(), b_val in proptest::prelude::any::<[u128; 4]>()) {
285					use $crate::arch::packed_512::*;
286					use $crate::arch::packed_aes_512::*;
287					use $crate::arch::packed_ghash_512::*;
288
289					TestMult::<PackedBinaryField512x1b>::test_mul(a_val.into(), b_val.into());
290					TestMult::<PackedAESBinaryField64x8b>::test_mul(a_val.into(), b_val.into());
291					TestMult::<PackedBinaryGhash4x128b>::test_mul(a_val.into(), b_val.into());
292				}
293			}
294		};
295	}
296
297	/// Test if `square_func` operation is a valid square operation on the given value for
298	/// all possible packed fields.
299	macro_rules! define_square_tests {
300		($square_func:path, $constraint:path) => {
301			$crate::packed_binary_field::test_utils::define_check_packed_square!(
302				$square_func,
303				$constraint
304			);
305
306			proptest::proptest! {
307				#[test]
308				fn test_square_packed_8(a_val in proptest::prelude::any::<u8>()) {
309					use $crate::arch::packed_8::*;
310					use $crate::arch::packed_aes_8::*;
311
312					TestSquare::<PackedBinaryField8x1b>::test_square(a_val.into());
313					TestSquare::<PackedAESBinaryField1x8b>::test_square(a_val.into());
314				}
315
316				#[test]
317				fn test_square_packed_16(a_val in proptest::prelude::any::<u16>()) {
318					use $crate::arch::packed_16::*;
319					use $crate::arch::packed_aes_16::*;
320
321					TestSquare::<PackedBinaryField16x1b>::test_square(a_val.into());
322					TestSquare::<PackedAESBinaryField2x8b>::test_square(a_val.into());
323				}
324
325				#[test]
326				fn test_square_packed_32(a_val in proptest::prelude::any::<u32>()) {
327					use $crate::arch::packed_32::*;
328					use $crate::arch::packed_aes_32::*;
329
330					TestSquare::<PackedBinaryField32x1b>::test_square(a_val.into());
331					TestSquare::<PackedAESBinaryField4x8b>::test_square(a_val.into());
332				}
333
334				#[test]
335				fn test_square_packed_64(a_val in proptest::prelude::any::<u64>()) {
336					use $crate::arch::packed_64::*;
337					use $crate::arch::packed_aes_64::*;
338
339					TestSquare::<PackedBinaryField64x1b>::test_square(a_val.into());
340					TestSquare::<PackedAESBinaryField8x8b>::test_square(a_val.into());
341				}
342
343				#[test]
344				fn test_square_packed_128(a_val in proptest::prelude::any::<u128>()) {
345					use $crate::arch::packed_128::*;
346					use $crate::arch::packed_aes_128::*;
347					use $crate::arch::packed_ghash_128::*;
348
349					TestSquare::<PackedBinaryField128x1b>::test_square(a_val.into());
350					TestSquare::<PackedAESBinaryField16x8b>::test_square(a_val.into());
351					TestSquare::<PackedBinaryGhash1x128b>::test_square(a_val.into());
352				}
353
354				#[test]
355				fn test_square_packed_256(a_val in proptest::prelude::any::<[u128; 2]>()) {
356					use $crate::arch::packed_256::*;
357					use $crate::arch::packed_aes_256::*;
358					use $crate::arch::packed_ghash_256::*;
359
360					TestSquare::<PackedBinaryField256x1b>::test_square(a_val.into());
361					TestSquare::<PackedAESBinaryField32x8b>::test_square(a_val.into());
362					TestSquare::<PackedBinaryGhash2x128b>::test_square(a_val.into());
363				}
364
365				#[test]
366				fn test_square_packed_512(a_val in proptest::prelude::any::<[u128; 4]>()) {
367					use $crate::arch::packed_512::*;
368					use $crate::arch::packed_aes_512::*;
369					use $crate::arch::packed_ghash_512::*;
370
371					TestSquare::<PackedBinaryField512x1b>::test_square(a_val.into());
372					TestSquare::<PackedAESBinaryField64x8b>::test_square(a_val.into());
373					TestSquare::<PackedBinaryGhash4x128b>::test_square(a_val.into());
374				}
375			}
376		};
377	}
378
379	/// Test if `invert_func` operation is a valid invert operation on the given value for
380	/// all possible packed fields.
381	macro_rules! define_invert_tests {
382		($invert_func:path, $constraint:path) => {
383			$crate::packed_binary_field::test_utils::define_check_packed_inverse!(
384				$invert_func,
385				$constraint
386			);
387
388			proptest::proptest! {
389				#[test]
390				fn test_invert_packed_8(a_val in proptest::prelude::any::<u8>()) {
391					use $crate::arch::packed_8::*;
392					use $crate::arch::packed_aes_8::*;
393
394					TestInvert::<PackedBinaryField8x1b>::test_invert(a_val.into());
395					TestInvert::<PackedAESBinaryField1x8b>::test_invert(a_val.into());
396				}
397
398				#[test]
399				fn test_invert_packed_16(a_val in proptest::prelude::any::<u16>()) {
400					use $crate::arch::packed_16::*;
401					use $crate::arch::packed_aes_16::*;
402
403					TestInvert::<PackedBinaryField16x1b>::test_invert(a_val.into());
404					TestInvert::<PackedAESBinaryField2x8b>::test_invert(a_val.into());
405				}
406
407				#[test]
408				fn test_invert_packed_32(a_val in proptest::prelude::any::<u32>()) {
409					use $crate::arch::packed_32::*;
410					use $crate::arch::packed_aes_32::*;
411
412					TestInvert::<PackedBinaryField32x1b>::test_invert(a_val.into());
413					TestInvert::<PackedAESBinaryField4x8b>::test_invert(a_val.into());
414				}
415
416				#[test]
417				fn test_invert_packed_64(a_val in proptest::prelude::any::<u64>()) {
418					use $crate::arch::packed_64::*;
419					use $crate::arch::packed_aes_64::*;
420
421					TestInvert::<PackedBinaryField64x1b>::test_invert(a_val.into());
422					TestInvert::<PackedAESBinaryField8x8b>::test_invert(a_val.into());
423				}
424
425				#[test]
426				fn test_invert_packed_128(a_val in proptest::prelude::any::<u128>()) {
427					use $crate::arch::packed_128::*;
428					use $crate::arch::packed_aes_128::*;
429					use $crate::arch::packed_ghash_128::*;
430
431					TestInvert::<PackedBinaryField128x1b>::test_invert(a_val.into());
432					TestInvert::<PackedAESBinaryField16x8b>::test_invert(a_val.into());
433					TestInvert::<PackedBinaryGhash1x128b>::test_invert(a_val.into());
434				}
435
436				#[test]
437				fn test_invert_packed_256(a_val in proptest::prelude::any::<[u128; 2]>()) {
438					use $crate::arch::packed_256::*;
439					use $crate::arch::packed_aes_256::*;
440					use $crate::arch::packed_ghash_256::*;
441
442					TestInvert::<PackedBinaryField256x1b>::test_invert(a_val.into());
443					TestInvert::<PackedAESBinaryField32x8b>::test_invert(a_val.into());
444					TestInvert::<PackedBinaryGhash2x128b>::test_invert(a_val.into());
445				}
446
447				#[test]
448				fn test_invert_packed_512(a_val in proptest::prelude::any::<[u128; 4]>()) {
449					use $crate::arch::packed_512::*;
450					use $crate::arch::packed_aes_512::*;
451					use $crate::arch::packed_ghash_512::*;
452
453					TestInvert::<PackedBinaryField512x1b>::test_invert(a_val.into());
454					TestInvert::<PackedAESBinaryField64x8b>::test_invert(a_val.into());
455					TestInvert::<PackedBinaryGhash4x128b>::test_invert(a_val.into());
456				}
457			}
458		};
459	}
460
461	/// Test if `$constraint::make_packed_transformation` operation creates a valid transformation
462	/// operation on the given value for all possible packed fields.
463	macro_rules! define_transformation_tests {
464		($constraint:path) => {
465			$crate::packed_binary_field::test_utils::define_check_packed_transformation!(
466				$constraint
467			);
468
469			proptest::proptest! {
470				#[test]
471				fn test_transformation_packed_1(a_val in 0..2u8) {
472					use crate::arch::packed_1::*;
473
474					TestTransformation::<PackedBinaryField1x1b>::test_transformation($crate::underlier::U1::new_unchecked(a_val).into());
475				}
476
477				#[test]
478				fn test_transformation_packed_2(a_val in 0..4u8) {
479					use crate::arch::packed_2::*;
480
481					TestTransformation::<PackedBinaryField2x1b>::test_transformation($crate::underlier::U2::new_unchecked(a_val).into());
482				}
483
484				#[test]
485				fn test_transformation_packed_4(a_val in 0..16u8) {
486					use crate::arch::packed_4::*;
487
488					TestTransformation::<PackedBinaryField4x1b>::test_transformation($crate::underlier::U4::new_unchecked(a_val).into());
489				}
490
491				#[test]
492				fn test_transformation_packed_8(a_val in proptest::prelude::any::<u8>()) {
493					use crate::arch::packed_8::*;
494					use crate::arch::packed_aes_8::*;
495
496					TestTransformation::<PackedBinaryField8x1b>::test_transformation(a_val.into());
497					TestTransformation::<PackedAESBinaryField1x8b>::test_transformation(a_val.into());
498				}
499
500				#[test]
501				fn test_transformation_packed_16(a_val in proptest::prelude::any::<u16>()) {
502					use crate::arch::packed_16::*;
503					use crate::arch::packed_aes_16::*;
504
505					TestTransformation::<PackedBinaryField16x1b>::test_transformation(a_val.into());
506					TestTransformation::<PackedAESBinaryField2x8b>::test_transformation(a_val.into());
507				}
508
509				#[test]
510				fn test_transformation_packed_32(a_val in proptest::prelude::any::<u32>()) {
511					use crate::arch::packed_32::*;
512					use crate::arch::packed_aes_32::*;
513
514					TestTransformation::<PackedBinaryField32x1b>::test_transformation(a_val.into());
515					TestTransformation::<PackedAESBinaryField4x8b>::test_transformation(a_val.into());
516				}
517
518				#[test]
519				fn test_transformation_packed_64(a_val in proptest::prelude::any::<u64>()) {
520					use $crate::arch::packed_64::*;
521					use $crate::arch::packed_aes_64::*;
522
523					TestTransformation::<PackedBinaryField64x1b>::test_transformation(a_val.into());
524					TestTransformation::<PackedAESBinaryField8x8b>::test_transformation(a_val.into());
525				}
526
527				#[test]
528				fn test_transformation_packed_128(a_val in proptest::prelude::any::<u128>()) {
529					use $crate::arch::packed_128::*;
530					use $crate::arch::packed_aes_128::*;
531					use $crate::arch::packed_ghash_128::*;
532
533					TestTransformation::<PackedBinaryField128x1b>::test_transformation(a_val.into());
534					TestTransformation::<PackedAESBinaryField16x8b>::test_transformation(a_val.into());
535					TestTransformation::<PackedBinaryGhash1x128b>::test_transformation(a_val.into());
536				}
537
538				#[test]
539				fn test_transformation_packed_256(a_val in proptest::prelude::any::<[u128; 2]>()) {
540					use $crate::arch::packed_256::*;
541					use $crate::arch::packed_aes_256::*;
542					use $crate::arch::packed_ghash_256::*;
543
544					TestTransformation::<PackedBinaryField256x1b>::test_transformation(a_val.into());
545					TestTransformation::<PackedAESBinaryField32x8b>::test_transformation(a_val.into());
546					TestTransformation::<PackedBinaryGhash2x128b>::test_transformation(a_val.into());
547				}
548
549				#[test]
550				fn test_transformation_packed_512(a_val in proptest::prelude::any::<[u128; 4]>()) {
551					use $crate::arch::packed_512::*;
552					use $crate::arch::packed_aes_512::*;
553					use $crate::arch::packed_ghash_512::*;
554
555					TestTransformation::<PackedBinaryField512x1b>::test_transformation(a_val.into());
556					TestTransformation::<PackedAESBinaryField64x8b>::test_transformation(a_val.into());
557					TestTransformation::<PackedBinaryGhash4x128b>::test_transformation(a_val.into());
558				}
559			}
560		};
561	}
562
563	pub(crate) use define_invert_tests;
564	pub(crate) use define_multiply_tests;
565	pub(crate) use define_square_tests;
566	pub(crate) use define_transformation_tests;
567
568	/// Helper function for compile-time checks
569	#[allow(unused)]
570	pub const fn implements_transformation_factory<
571		P1: PackedField<Scalar: BinaryField>,
572		P2: PackedTransformationFactory<P1>,
573	>() {
574	}
575
576	pub fn check_interleave<P: PackedField + WithUnderlier>(
577		lhs: P::Underlier,
578		rhs: P::Underlier,
579		log_block_len: usize,
580	) {
581		let lhs = P::from_underlier(lhs);
582		let rhs = P::from_underlier(rhs);
583		let (a, b) = lhs.interleave(rhs, log_block_len);
584		let block_len = 1 << log_block_len;
585		for i in (0..P::WIDTH).step_by(block_len * 2) {
586			for j in 0..block_len {
587				assert_eq!(a.get(i + j), lhs.get(i + j));
588				assert_eq!(a.get(i + j + block_len), rhs.get(i + j));
589
590				assert_eq!(b.get(i + j), lhs.get(i + j + block_len));
591				assert_eq!(b.get(i + j + block_len), rhs.get(i + j + block_len));
592			}
593		}
594	}
595
596	pub fn check_interleave_all_heights<P: PackedField + WithUnderlier>(
597		lhs: P::Underlier,
598		rhs: P::Underlier,
599	) {
600		for log_block_len in 0..P::LOG_WIDTH {
601			check_interleave::<P>(lhs, rhs, log_block_len);
602		}
603	}
604
605	pub fn check_unzip<P: PackedField + WithUnderlier>(
606		lhs: P::Underlier,
607		rhs: P::Underlier,
608		log_block_len: usize,
609	) {
610		let lhs = P::from_underlier(lhs);
611		let rhs = P::from_underlier(rhs);
612		let block_len = 1 << log_block_len;
613		let (a, b) = lhs.unzip(rhs, log_block_len);
614		for i in (0..P::WIDTH / 2).step_by(block_len) {
615			for j in 0..block_len {
616				assert_eq!(
617					a.get(i + j),
618					lhs.get(2 * i + j),
619					"i: {}, j: {}, log_block_len: {}, P: {:?}",
620					i,
621					j,
622					log_block_len,
623					P::zero()
624				);
625				assert_eq!(
626					b.get(i + j),
627					lhs.get(2 * i + j + block_len),
628					"i: {}, j: {}, log_block_len: {}, P: {:?}",
629					i,
630					j,
631					log_block_len,
632					P::zero()
633				);
634			}
635		}
636
637		for i in (0..P::WIDTH / 2).step_by(block_len) {
638			for j in 0..block_len {
639				assert_eq!(
640					a.get(i + j + P::WIDTH / 2),
641					rhs.get(2 * i + j),
642					"i: {}, j: {}, log_block_len: {}, P: {:?}",
643					i,
644					j,
645					log_block_len,
646					P::zero()
647				);
648				assert_eq!(b.get(i + j + P::WIDTH / 2), rhs.get(2 * i + j + block_len));
649			}
650		}
651	}
652
653	pub fn check_transpose_all_heights<P: PackedField + WithUnderlier>(
654		lhs: P::Underlier,
655		rhs: P::Underlier,
656	) {
657		for log_block_len in 0..P::LOG_WIDTH {
658			check_unzip::<P>(lhs, rhs, log_block_len);
659		}
660	}
661}
662
663#[cfg(test)]
664mod tests {
665	use std::{iter::repeat_with, ops::Mul};
666
667	use binius_utils::{DeserializeBytes, SerializeBytes, bytes::BytesMut};
668	use proptest::prelude::*;
669	use rand::prelude::*;
670	use test_utils::check_interleave_all_heights;
671
672	use super::{
673		test_utils::{
674			define_invert_tests, define_multiply_tests, define_square_tests,
675			define_transformation_tests,
676		},
677		*,
678	};
679	use crate::{
680		PackedBinaryGhash1x128b, PackedBinaryGhash2x128b, PackedBinaryGhash4x128b, PackedField,
681		Random,
682		linear_transformation::PackedTransformationFactory,
683		test_utils::check_transpose_all_heights,
684		underlier::{U2, U4},
685	};
686
687	fn test_add_packed<P: PackedField + From<u128>>(a_val: u128, b_val: u128) {
688		let a = P::from(a_val);
689		let b = P::from(b_val);
690		let c = a + b;
691		for i in 0..P::WIDTH {
692			assert_eq!(c.get(i), a.get(i) + b.get(i));
693		}
694	}
695
696	fn test_mul_packed<P: PackedField>(a: P, b: P) {
697		let c = a * b;
698		for i in 0..P::WIDTH {
699			assert_eq!(c.get(i), a.get(i) * b.get(i));
700		}
701	}
702
703	fn test_mul_packed_random<P: PackedField>() {
704		let mut rng = StdRng::seed_from_u64(0);
705		test_mul_packed(P::random(&mut rng), P::random(&mut rng))
706	}
707
708	fn test_set_then_get<P: PackedField>() {
709		let mut rng = StdRng::seed_from_u64(0);
710		let mut elem = P::random(&mut rng);
711
712		let scalars = repeat_with(|| P::Scalar::random(&mut rng))
713			.take(P::WIDTH)
714			.collect::<Vec<_>>();
715
716		for (i, val) in scalars.iter().enumerate() {
717			elem.set(i, *val);
718		}
719		for (i, val) in scalars.iter().enumerate() {
720			assert_eq!(elem.get(i), *val);
721		}
722	}
723
724	fn test_serialize_then_deserialize<P: PackedField + DeserializeBytes + SerializeBytes>() {
725		let mut buffer = BytesMut::new();
726		let mut rng = StdRng::seed_from_u64(0);
727		let packed = P::random(&mut rng);
728		packed.serialize(&mut buffer).unwrap();
729
730		let mut read_buffer = buffer.freeze();
731
732		assert_eq!(P::deserialize(&mut read_buffer).unwrap(), packed);
733	}
734
735	#[test]
736	fn test_set_then_get_128b() {
737		test_set_then_get::<PackedBinaryGhash1x128b>();
738		test_set_then_get::<PackedBinaryGhash2x128b>();
739		test_set_then_get::<PackedBinaryGhash4x128b>();
740	}
741
742	#[test]
743	fn test_serialize_then_deserialize_128b() {
744		test_serialize_then_deserialize::<PackedBinaryGhash1x128b>();
745		test_serialize_then_deserialize::<PackedBinaryGhash2x128b>();
746		test_serialize_then_deserialize::<PackedBinaryGhash4x128b>();
747	}
748
749	#[test]
750	fn test_serialize_deserialize_different_packing_width() {
751		let mut rng = StdRng::seed_from_u64(0);
752
753		let packed0 = PackedBinaryGhash1x128b::random(&mut rng);
754		let packed1 = PackedBinaryGhash1x128b::random(&mut rng);
755
756		let mut buffer = BytesMut::new();
757		packed0.serialize(&mut buffer).unwrap();
758		packed1.serialize(&mut buffer).unwrap();
759
760		let mut read_buffer = buffer.freeze();
761		let packed01 = PackedBinaryGhash2x128b::deserialize(&mut read_buffer).unwrap();
762
763		assert!(
764			packed01
765				.iter()
766				.zip([packed0, packed1])
767				.all(|(x, y)| x == y.get(0))
768		);
769	}
770
771	// TODO: Generate lots more proptests using macros
772	proptest! {
773		#[test]
774		fn test_add_packed_128x1b(a_val in any::<u128>(), b_val in any::<u128>()) {
775			test_add_packed::<PackedBinaryField128x1b>(a_val, b_val)
776		}
777
778		#[test]
779		fn test_add_packed_16x8b(a_val in any::<u128>(), b_val in any::<u128>()) {
780			test_add_packed::<PackedAESBinaryField16x8b>(a_val, b_val)
781		}
782
783		#[test]
784		fn test_add_packed_1x128b(a_val in any::<u128>(), b_val in any::<u128>()) {
785			test_add_packed::<PackedBinaryGhash1x128b>(a_val, b_val)
786		}
787	}
788
789	#[test]
790	fn test_mul_packed_256x1b() {
791		test_mul_packed_random::<PackedBinaryField256x1b>()
792	}
793
794	#[test]
795	fn test_mul_packed_32x8b() {
796		test_mul_packed_random::<PackedAESBinaryField32x8b>()
797	}
798
799	#[test]
800	fn test_mul_packed_2x128b() {
801		test_mul_packed_random::<PackedBinaryGhash2x128b>()
802	}
803
804	#[test]
805	fn test_iter_size_hint() {
806		assert_valid_iterator_with_exact_size_hint::<PackedBinaryField128x1b>();
807	}
808
809	fn assert_valid_iterator_with_exact_size_hint<P: PackedField>() {
810		assert_eq!(P::default().iter().size_hint(), (P::WIDTH, Some(P::WIDTH)));
811		assert_eq!(P::default().into_iter().size_hint(), (P::WIDTH, Some(P::WIDTH)));
812		assert_eq!(P::default().iter().count(), P::WIDTH);
813		assert_eq!(P::default().into_iter().count(), P::WIDTH);
814	}
815
816	define_multiply_tests!(Mul::mul, PackedField);
817
818	define_square_tests!(PackedField::square, PackedField);
819
820	define_invert_tests!(PackedField::invert_or_zero, PackedField);
821
822	#[allow(unused)]
823	trait SelfTransformationFactory: PackedTransformationFactory<Self> {}
824
825	impl<T: PackedTransformationFactory<T>> SelfTransformationFactory for T {}
826
827	define_transformation_tests!(SelfTransformationFactory);
828
829	proptest! {
830		#[test]
831		fn test_interleave_2b(a_val in 0u8..3, b_val in 0u8..3) {
832			check_interleave_all_heights::<PackedBinaryField2x1b>(U2::new(a_val), U2::new(b_val));
833		}
834
835		#[test]
836		fn test_interleave_4b(a_val in 0u8..16, b_val in 0u8..16) {
837			check_interleave_all_heights::<PackedBinaryField4x1b>(U4::new(a_val), U4::new(b_val));
838		}
839
840		#[test]
841		fn test_interleave_8b(a_val in 0u8.., b_val in 0u8..) {
842			check_interleave_all_heights::<PackedBinaryField8x1b>(a_val, b_val);
843			check_interleave_all_heights::<PackedAESBinaryField1x8b>(a_val, b_val);
844		}
845
846		#[test]
847		fn test_interleave_16b(a_val in 0u16.., b_val in 0u16..) {
848			check_interleave_all_heights::<PackedBinaryField16x1b>(a_val, b_val);
849			check_interleave_all_heights::<PackedAESBinaryField2x8b>(a_val, b_val);
850		}
851
852		#[test]
853		fn test_interleave_32b(a_val in 0u32.., b_val in 0u32..) {
854			check_interleave_all_heights::<PackedBinaryField32x1b>(a_val, b_val);
855			check_interleave_all_heights::<PackedAESBinaryField4x8b>(a_val, b_val);
856		}
857
858		#[test]
859		fn test_interleave_64b(a_val in 0u64.., b_val in 0u64..) {
860			check_interleave_all_heights::<PackedBinaryField64x1b>(a_val, b_val);
861			check_interleave_all_heights::<PackedAESBinaryField8x8b>(a_val, b_val);
862		}
863
864		#[test]
865		#[allow(clippy::useless_conversion)] // this warning depends on the target platform
866		fn test_interleave_128b(a_val in 0u128.., b_val in 0u128..) {
867			check_interleave_all_heights::<PackedBinaryField128x1b>(a_val.into(), b_val.into());
868			check_interleave_all_heights::<PackedAESBinaryField16x8b>(a_val.into(), b_val.into());
869			check_interleave_all_heights::<PackedBinaryGhash1x128b>(a_val.into(), b_val.into());
870		}
871
872		#[test]
873		fn test_interleave_256b(a_val in any::<[u128; 2]>(), b_val in any::<[u128; 2]>()) {
874			check_interleave_all_heights::<PackedBinaryField256x1b>(a_val.into(), b_val.into());
875			check_interleave_all_heights::<PackedAESBinaryField32x8b>(a_val.into(), b_val.into());
876			check_interleave_all_heights::<PackedBinaryGhash2x128b>(a_val.into(), b_val.into());
877		}
878
879		#[test]
880		fn test_interleave_512b(a_val in any::<[u128; 4]>(), b_val in any::<[u128; 4]>()) {
881			check_interleave_all_heights::<PackedBinaryField512x1b>(a_val.into(), b_val.into());
882			check_interleave_all_heights::<PackedAESBinaryField64x8b>(a_val.into(), b_val.into());
883			check_interleave_all_heights::<PackedBinaryGhash4x128b>(a_val.into(), b_val.into());
884		}
885
886		#[test]
887		fn check_transpose_2b(a_val in 0u8..3, b_val in 0u8..3) {
888			check_transpose_all_heights::<PackedBinaryField2x1b>(U2::new(a_val), U2::new(b_val));
889		}
890
891		#[test]
892		fn check_transpose_4b(a_val in 0u8..16, b_val in 0u8..16) {
893			check_transpose_all_heights::<PackedBinaryField4x1b>(U4::new(a_val), U4::new(b_val));
894		}
895
896		#[test]
897		fn check_transpose_8b(a_val in 0u8.., b_val in 0u8..) {
898			check_transpose_all_heights::<PackedBinaryField8x1b>(a_val, b_val);
899			check_transpose_all_heights::<PackedAESBinaryField1x8b>(a_val, b_val);
900		}
901
902		#[test]
903		fn check_transpose_16b(a_val in 0u16.., b_val in 0u16..) {
904			check_transpose_all_heights::<PackedBinaryField16x1b>(a_val, b_val);
905			check_transpose_all_heights::<PackedAESBinaryField2x8b>(a_val, b_val);
906		}
907
908		#[test]
909		fn check_transpose_32b(a_val in 0u32.., b_val in 0u32..) {
910			check_transpose_all_heights::<PackedBinaryField32x1b>(a_val, b_val);
911			check_transpose_all_heights::<PackedAESBinaryField4x8b>(a_val, b_val);
912		}
913
914		#[test]
915		fn check_transpose_64b(a_val in 0u64.., b_val in 0u64..) {
916			check_transpose_all_heights::<PackedBinaryField64x1b>(a_val, b_val);
917			check_transpose_all_heights::<PackedAESBinaryField8x8b>(a_val, b_val);
918		}
919
920		#[test]
921		#[allow(clippy::useless_conversion)] // this warning depends on the target platform
922		fn check_transpose_128b(a_val in 0u128.., b_val in 0u128..) {
923			check_transpose_all_heights::<PackedBinaryField128x1b>(a_val.into(), b_val.into());
924			check_transpose_all_heights::<PackedAESBinaryField16x8b>(a_val.into(), b_val.into());
925			check_transpose_all_heights::<PackedBinaryGhash1x128b>(a_val.into(), b_val.into());
926		}
927
928		#[test]
929		fn check_transpose_256b(a_val in any::<[u128; 2]>(), b_val in any::<[u128; 2]>()) {
930			check_transpose_all_heights::<PackedBinaryField256x1b>(a_val.into(), b_val.into());
931			check_transpose_all_heights::<PackedAESBinaryField32x8b>(a_val.into(), b_val.into());
932			check_transpose_all_heights::<PackedBinaryGhash2x128b>(a_val.into(), b_val.into());
933		}
934
935		#[test]
936		fn check_transpose_512b(a_val in any::<[u128; 4]>(), b_val in any::<[u128; 4]>()) {
937			check_transpose_all_heights::<PackedBinaryField512x1b>(a_val.into(), b_val.into());
938			check_transpose_all_heights::<PackedAESBinaryField64x8b>(a_val.into(), b_val.into());
939			check_transpose_all_heights::<PackedBinaryGhash4x128b>(a_val.into(), b_val.into());
940		}
941	}
942}
binius_field/packed_binary_field.rs

binius_field/
packed_binary_field.rs
