binius_field/arch/portable/
pairwise_table_arithmetic.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use super::packed::PackedPrimitiveType;
4use crate::{
5	arch::PairwiseTableStrategy,
6	arithmetic_traits::{TaggedInvertOrZero, TaggedMul, TaggedMulAlpha, TaggedSquare},
7	packed::PackedField,
8	underlier::UnderlierType,
9	AESTowerField8b, BinaryField2b, BinaryField4b, BinaryField8b,
10};
11
12impl<U: UnderlierType> TaggedMul<PairwiseTableStrategy> for PackedPrimitiveType<U, BinaryField2b>
13where
14	Self: PackedField<Scalar = BinaryField2b>,
15{
16	#[inline]
17	fn mul(self, rhs: Self) -> Self {
18		Self::from_fn(|i| mul_binary_tower_4b(self.get(i).into(), rhs.get(i).into()).into())
19	}
20}
21
22impl<U: UnderlierType> TaggedMul<PairwiseTableStrategy> for PackedPrimitiveType<U, BinaryField4b>
23where
24	Self: PackedField<Scalar = BinaryField4b>,
25{
26	#[inline]
27	fn mul(self, rhs: Self) -> Self {
28		Self::from_fn(|i| mul_binary_tower_4b(self.get(i).into(), rhs.get(i).into()).into())
29	}
30}
31
32const fn mul_binary_tower_4b(a: u8, b: u8) -> u8 {
33	#[rustfmt::skip]
34	const MUL_4B_LOOKUP: [u8; 128] = [
35		0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
36		0x10, 0x32, 0x54, 0x76, 0x98, 0xba, 0xdc, 0xfe,
37		0x20, 0x13, 0xa8, 0x9b, 0xec, 0xdf, 0x64, 0x57,
38		0x30, 0x21, 0xfc, 0xed, 0x74, 0x65, 0xb8, 0xa9,
39		0x40, 0xc8, 0xd9, 0x51, 0xae, 0x26, 0x37, 0xbf,
40		0x50, 0xfa, 0x8d, 0x27, 0x36, 0x9c, 0xeb, 0x41,
41		0x60, 0xdb, 0x71, 0xca, 0x42, 0xf9, 0x53, 0xe8,
42		0x70, 0xe9, 0x25, 0xbc, 0xda, 0x43, 0x8f, 0x16,
43		0x80, 0x4c, 0x6e, 0xa2, 0xf7, 0x3b, 0x19, 0xd5,
44		0x90, 0x7e, 0x3a, 0xd4, 0x6f, 0x81, 0xc5, 0x2b,
45		0xa0, 0x5f, 0xc6, 0x39, 0x1b, 0xe4, 0x7d, 0x82,
46		0xb0, 0x6d, 0x92, 0x4f, 0x83, 0x5e, 0xa1, 0x7c,
47		0xc0, 0x84, 0xb7, 0xf3, 0x59, 0x1d, 0x2e, 0x6a,
48		0xd0, 0xb6, 0xe3, 0x85, 0xc1, 0xa7, 0xf2, 0x94,
49		0xe0, 0x97, 0x1f, 0x68, 0xb5, 0xc2, 0x4a, 0x3d,
50		0xf0, 0xa5, 0x4b, 0x1e, 0x2d, 0x78, 0x96, 0xc3,
51	];
52	let idx = a << 4 | b;
53	(MUL_4B_LOOKUP[idx as usize >> 1] >> ((idx & 1) * 4)) & 0x0f
54}
55
56impl<U: UnderlierType> TaggedMul<PairwiseTableStrategy> for PackedPrimitiveType<U, BinaryField8b>
57where
58	Self: PackedField<Scalar = BinaryField8b>,
59{
60	#[inline]
61	fn mul(self, rhs: Self) -> Self {
62		#[rustfmt::skip]
63        const EXP_TABLE: [u8; 256] = [
64            0x1,  0x13, 0x43, 0x66, 0xab, 0x8c, 0x60, 0xc6, 0x91, 0xca, 0x59, 0xb2, 0x6a, 0x63, 0xf4, 0x53,
65            0x17, 0x0f, 0xfa, 0xba, 0xee, 0x87, 0xd6, 0xe0, 0x6e, 0x2f, 0x68, 0x42, 0x75, 0xe8, 0xea, 0xcb,
66            0x4a, 0xf1, 0x0c, 0xc8, 0x78, 0x33, 0xd1, 0x9e, 0x30, 0xe3, 0x5c, 0xed, 0xb5, 0x14, 0x3d, 0x38,
67            0x67, 0xb8, 0xcf, 0x06, 0x6d, 0x1d, 0xaa, 0x9f, 0x23, 0xa0, 0x3a, 0x46, 0x39, 0x74, 0xfb, 0xa9,
68            0xad, 0xe1, 0x7d, 0x6c, 0x0e, 0xe9, 0xf9, 0x88, 0x2c, 0x5a, 0x80, 0xa8, 0xbe, 0xa2, 0x1b, 0xc7,
69            0x82, 0x89, 0x3f, 0x19, 0xe6, 0x03, 0x32, 0xc2, 0xdd, 0x56, 0x48, 0xd0, 0x8d, 0x73, 0x85, 0xf7,
70            0x61, 0xd5, 0xd2, 0xac, 0xf2, 0x3e, 0x0a, 0xa5, 0x65, 0x99, 0x4e, 0xbd, 0x90, 0xd9, 0x1a, 0xd4,
71            0xc1, 0xef, 0x94, 0x95, 0x86, 0xc5, 0xa3, 0x08, 0x84, 0xe4, 0x22, 0xb3, 0x79, 0x20, 0x92, 0xf8,
72            0x9b, 0x6f, 0x3c, 0x2b, 0x24, 0xde, 0x64, 0x8a, 0xd,  0xdb, 0x3b, 0x55, 0x7a, 0x12, 0x50, 0x25,
73            0xcd, 0x27, 0xec, 0xa6, 0x57, 0x5b, 0x93, 0xeb, 0xd8, 0x09, 0x97, 0xa7, 0x44, 0x18, 0xf5, 0x40,
74            0x54, 0x69, 0x51, 0x36, 0x8e, 0x41, 0x47, 0x2a, 0x37, 0x9d, 0x02, 0x21, 0x81, 0xbb, 0xfd, 0xc4,
75            0xb0, 0x4b, 0xe2, 0x4f, 0xae, 0xd3, 0xbf, 0xb1, 0x58, 0xa1, 0x29, 0x05, 0x5f, 0xdf, 0x77, 0xc9,
76            0x6b, 0x70, 0xb7, 0x35, 0xbc, 0x83, 0x9a, 0x7c, 0x7f, 0x4d, 0x8f, 0x52, 0x04, 0x4c, 0x9c, 0x11,
77            0x62, 0xe7, 0x10, 0x71, 0xa4, 0x76, 0xda, 0x28, 0x16, 0x1c, 0xb9, 0xdc, 0x45, 0x0b, 0xb6, 0x26,
78            0xff, 0xe5, 0x31, 0xf0, 0x1f, 0x8b, 0x1e, 0x98, 0x5d, 0xfe, 0xf6, 0x72, 0x96, 0xb4, 0x07, 0x7e,
79            0x5e, 0xcc, 0x34, 0xaf, 0xc0, 0xfc, 0xd7, 0xf3, 0x2d, 0x49, 0xc3, 0xce, 0x15, 0x2e, 0x7b, 0x00,
80        ];
81		#[rustfmt::skip]
82        const LOG_TABLE: [u8; 256] = [
83            0x00, 0x00, 0xaa, 0x55, 0xcc, 0xbb, 0x33, 0xee, 0x77, 0x99, 0x66, 0xdd, 0x22, 0x88, 0x44, 0x11,
84            0xd2, 0xcf, 0x8d, 0x01, 0x2d, 0xfc, 0xd8, 0x10, 0x9d, 0x53, 0x6e, 0x4e, 0xd9, 0x35, 0xe6, 0xe4,
85            0x7d, 0xab, 0x7a, 0x38, 0x84, 0x8f, 0xdf, 0x91, 0xd7, 0xba, 0xa7, 0x83, 0x48, 0xf8, 0xfd, 0x19,
86            0x28, 0xe2, 0x56, 0x25, 0xf2, 0xc3, 0xa3, 0xa8, 0x2f, 0x3c, 0x3a, 0x8a, 0x82, 0x2e, 0x65, 0x52,
87            0x9f, 0xa5, 0x1b, 0x02, 0x9c, 0xdc, 0x3b, 0xa6, 0x5a, 0xf9, 0x20, 0xb1, 0xcd, 0xc9, 0x6a, 0xb3,
88            0x8e, 0xa2, 0xcb, 0x0f, 0xa0, 0x8b, 0x59, 0x94, 0xb8, 0x0a, 0x49, 0x95, 0x2a, 0xe8, 0xf0, 0xbc,
89            0x06, 0x60, 0xd0, 0x0d, 0x86, 0x68, 0x03, 0x30, 0x1a, 0xa1, 0x0c, 0xc0, 0x43, 0x34, 0x18, 0x81,
90            0xc1, 0xd3, 0xeb, 0x5d, 0x3d, 0x1c, 0xd5, 0xbe, 0x24, 0x7c, 0x8c, 0xfe, 0xc7, 0x42, 0xef, 0xc8,
91            0x4a, 0xac, 0x50, 0xc5, 0x78, 0x5e, 0x74, 0x15, 0x47, 0x51, 0x87, 0xe5, 0x05, 0x5c, 0xa4, 0xca,
92            0x6c, 0x08, 0x7e, 0x96, 0x72, 0x73, 0xec, 0x9a, 0xe7, 0x69, 0xc6, 0x80, 0xce, 0xa9, 0x27, 0x37,
93            0x39, 0xb9, 0x4d, 0x76, 0xd4, 0x67, 0x93, 0x9b, 0x4b, 0x3f, 0x36, 0x04, 0x63, 0x40, 0xb4, 0xf3,
94            0xb0, 0xb7, 0x0b, 0x7b, 0xed, 0x2c, 0xde, 0xc2, 0x31, 0xda, 0x13, 0xad, 0xc4, 0x6b, 0x4c, 0xb6,
95            0xf4, 0x70, 0x57, 0xfa, 0xaf, 0x75, 0x07, 0x4f, 0x23, 0xbf, 0x09, 0x1f, 0xf1, 0x90, 0xfb, 0x32,
96            0x5b, 0x26, 0x62, 0xb5, 0x6f, 0x61, 0x16, 0xf6, 0x98, 0x6d, 0xd6, 0x89, 0xdb, 0x58, 0x85, 0xbd,
97            0x17, 0x41, 0xb2, 0x29, 0x79, 0xe1, 0x54, 0xd1, 0x1d, 0x45, 0x1e, 0x97, 0x92, 0x2b, 0x14, 0x71,
98            0xe3, 0x21, 0x64, 0xf7, 0x0e, 0x9e, 0xea, 0x5f, 0x7f, 0x46, 0x12, 0x3e, 0xf5, 0xae, 0xe9, 0xe0,
99        ];
100
101		Self::from_fn(|i| {
102			multiply_8b_using_log_table(self.get(i).val(), rhs.get(i).val(), &LOG_TABLE, &EXP_TABLE)
103				.into()
104		})
105	}
106}
107
108impl<U: UnderlierType> TaggedMul<PairwiseTableStrategy> for PackedPrimitiveType<U, AESTowerField8b>
109where
110	Self: PackedField<Scalar = AESTowerField8b>,
111{
112	#[inline]
113	fn mul(self, rhs: Self) -> Self {
114		#[rustfmt::skip]
115		const AES_EXP_TABLE: [u8; 256] = [
116			0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35,
117			0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa,
118			0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31,
119			0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd,
120			0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88,
121			0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a,
122			0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3,
123			0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0,
124			0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41,
125			0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75,
126			0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80,
127			0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54,
128			0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca,
129			0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e,
130			0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17,
131			0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x0
132		];
133
134		#[rustfmt::skip]
135		const AES_LOG_TABLE: [u8; 256] = [
136			0x00, 0x00, 0x19, 0x01, 0x32, 0x02, 0x1a, 0xc6, 0x4b, 0xc7, 0x1b, 0x68, 0x33, 0xee, 0xdf, 0x03,
137			0x64, 0x04, 0xe0, 0x0e, 0x34, 0x8d, 0x81, 0xef, 0x4c, 0x71, 0x08, 0xc8, 0xf8, 0x69, 0x1c, 0xc1,
138			0x7d, 0xc2, 0x1d, 0xb5, 0xf9, 0xb9, 0x27, 0x6a, 0x4d, 0xe4, 0xa6, 0x72, 0x9a, 0xc9, 0x09, 0x78,
139			0x65, 0x2f, 0x8a, 0x05, 0x21, 0x0f, 0xe1, 0x24, 0x12, 0xf0, 0x82, 0x45, 0x35, 0x93, 0xda, 0x8e,
140			0x96, 0x8f, 0xdb, 0xbd, 0x36, 0xd0, 0xce, 0x94, 0x13, 0x5c, 0xd2, 0xf1, 0x40, 0x46, 0x83, 0x38,
141			0x66, 0xdd, 0xfd, 0x30, 0xbf, 0x06, 0x8b, 0x62, 0xb3, 0x25, 0xe2, 0x98, 0x22, 0x88, 0x91, 0x10,
142			0x7e, 0x6e, 0x48, 0xc3, 0xa3, 0xb6, 0x1e, 0x42, 0x3a, 0x6b, 0x28, 0x54, 0xfa, 0x85, 0x3d, 0xba,
143			0x2b, 0x79, 0x0a, 0x15, 0x9b, 0x9f, 0x5e, 0xca, 0x4e, 0xd4, 0xac, 0xe5, 0xf3, 0x73, 0xa7, 0x57,
144			0xaf, 0x58, 0xa8, 0x50, 0xf4, 0xea, 0xd6, 0x74, 0x4f, 0xae, 0xe9, 0xd5, 0xe7, 0xe6, 0xad, 0xe8,
145			0x2c, 0xd7, 0x75, 0x7a, 0xeb, 0x16, 0x0b, 0xf5, 0x59, 0xcb, 0x5f, 0xb0, 0x9c, 0xa9, 0x51, 0xa0,
146			0x7f, 0x0c, 0xf6, 0x6f, 0x17, 0xc4, 0x49, 0xec, 0xd8, 0x43, 0x1f, 0x2d, 0xa4, 0x76, 0x7b, 0xb7,
147			0xcc, 0xbb, 0x3e, 0x5a, 0xfb, 0x60, 0xb1, 0x86, 0x3b, 0x52, 0xa1, 0x6c, 0xaa, 0x55, 0x29, 0x9d,
148			0x97, 0xb2, 0x87, 0x90, 0x61, 0xbe, 0xdc, 0xfc, 0xbc, 0x95, 0xcf, 0xcd, 0x37, 0x3f, 0x5b, 0xd1,
149			0x53, 0x39, 0x84, 0x3c, 0x41, 0xa2, 0x6d, 0x47, 0x14, 0x2a, 0x9e, 0x5d, 0x56, 0xf2, 0xd3, 0xab,
150			0x44, 0x11, 0x92, 0xd9, 0x23, 0x20, 0x2e, 0x89, 0xb4, 0x7c, 0xb8, 0x26, 0x77, 0x99, 0xe3, 0xa5,
151			0x67, 0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18, 0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07,
152		];
153
154		Self::from_fn(|i| {
155			multiply_8b_using_log_table(
156				self.get(i).val(),
157				rhs.get(i).val(),
158				&AES_LOG_TABLE,
159				&AES_EXP_TABLE,
160			)
161			.into()
162		})
163	}
164}
165
166#[inline]
167fn multiply_8b_using_log_table(
168	lhs: u8,
169	rhs: u8,
170	log_table: &[u8; 256],
171	exp_table: &[u8; 256],
172) -> u8 {
173	let result = if lhs != 0 && rhs != 0 {
174		let log_table_index = log_table[lhs as usize] as usize + log_table[rhs as usize] as usize;
175		let log_table_index = if log_table_index > 254 {
176			log_table_index - 255
177		} else {
178			log_table_index
179		};
180
181		unsafe {
182			// Safety: `log_table_index` is smaller than 255 because:
183			// - all values in `LOG_TABLE` do not exceed 254
184			// - sum of two values do not exceed 254*2
185			// - the previous line reduces `log_table_index` by 255 if it is
186			// bigger than 254
187			*exp_table.get_unchecked(log_table_index)
188		}
189	} else {
190		0
191	};
192
193	result
194}
195
196/// Return the result of the operation by a table search for each scalar value
197#[inline(always)]
198fn unary_op_with_table<PT>(val: PT, table: &[u8; 256]) -> PT
199where
200	PT: PackedField,
201	PT::Scalar: From<u8>,
202	u8: From<PT::Scalar>,
203{
204	PT::from_fn(|i| table[u8::from(val.get(i)) as usize].into())
205}
206
207/// Implement unary operation with a table search
208macro_rules! impl_unary_ops {
209	($tagged_op_type:ident, $method_name:ident, $table:ident, $field:ty) => {
210		impl<U: UnderlierType> $tagged_op_type<PairwiseTableStrategy>
211			for PackedPrimitiveType<U, $field>
212		where
213			Self: PackedField<Scalar = $field>,
214		{
215			#[inline(always)]
216			fn $method_name(self) -> Self {
217				unary_op_with_table(self, &$table)
218			}
219		}
220	};
221}
222
223#[rustfmt::skip]
224static BINARY_TOWER_8B_SQUARE_MAP: [u8; 256] = [
225    0x00, 0x01, 0x03, 0x02, 0x09, 0x08, 0x0a, 0x0b, 0x07, 0x06, 0x04, 0x05, 0x0e, 0x0f, 0x0d, 0x0c,
226    0x41, 0x40, 0x42, 0x43, 0x48, 0x49, 0x4b, 0x4a, 0x46, 0x47, 0x45, 0x44, 0x4f, 0x4e, 0x4c, 0x4d,
227    0xc3, 0xc2, 0xc0, 0xc1, 0xca, 0xcb, 0xc9, 0xc8, 0xc4, 0xc5, 0xc7, 0xc6, 0xcd, 0xcc, 0xce, 0xcf,
228    0x82, 0x83, 0x81, 0x80, 0x8b, 0x8a, 0x88, 0x89, 0x85, 0x84, 0x86, 0x87, 0x8c, 0x8d, 0x8f, 0x8e,
229    0xa9, 0xa8, 0xaa, 0xab, 0xa0, 0xa1, 0xa3, 0xa2, 0xae, 0xaf, 0xad, 0xac, 0xa7, 0xa6, 0xa4, 0xa5,
230    0xe8, 0xe9, 0xeb, 0xea, 0xe1, 0xe0, 0xe2, 0xe3, 0xef, 0xee, 0xec, 0xed, 0xe6, 0xe7, 0xe5, 0xe4,
231    0x6a, 0x6b, 0x69, 0x68, 0x63, 0x62, 0x60, 0x61, 0x6d, 0x6c, 0x6e, 0x6f, 0x64, 0x65, 0x67, 0x66,
232    0x2b, 0x2a, 0x28, 0x29, 0x22, 0x23, 0x21, 0x20, 0x2c, 0x2d, 0x2f, 0x2e, 0x25, 0x24, 0x26, 0x27,
233    0x57, 0x56, 0x54, 0x55, 0x5e, 0x5f, 0x5d, 0x5c, 0x50, 0x51, 0x53, 0x52, 0x59, 0x58, 0x5a, 0x5b,
234    0x16, 0x17, 0x15, 0x14, 0x1f, 0x1e, 0x1c, 0x1d, 0x11, 0x10, 0x12, 0x13, 0x18, 0x19, 0x1b, 0x1a,
235    0x94, 0x95, 0x97, 0x96, 0x9d, 0x9c, 0x9e, 0x9f, 0x93, 0x92, 0x90, 0x91, 0x9a, 0x9b, 0x99, 0x98,
236    0xd5, 0xd4, 0xd6, 0xd7, 0xdc, 0xdd, 0xdf, 0xde, 0xd2, 0xd3, 0xd1, 0xd0, 0xdb, 0xda, 0xd8, 0xd9,
237    0xfe, 0xff, 0xfd, 0xfc, 0xf7, 0xf6, 0xf4, 0xf5, 0xf9, 0xf8, 0xfa, 0xfb, 0xf0, 0xf1, 0xf3, 0xf2,
238    0xbf, 0xbe, 0xbc, 0xbd, 0xb6, 0xb7, 0xb5, 0xb4, 0xb8, 0xb9, 0xbb, 0xba, 0xb1, 0xb0, 0xb2, 0xb3,
239    0x3d, 0x3c, 0x3e, 0x3f, 0x34, 0x35, 0x37, 0x36, 0x3a, 0x3b, 0x39, 0x38, 0x33, 0x32, 0x30, 0x31,
240    0x7c, 0x7d, 0x7f, 0x7e, 0x75, 0x74, 0x76, 0x77, 0x7b, 0x7a, 0x78, 0x79, 0x72, 0x73, 0x71, 0x70,
241];
242
243impl_unary_ops!(TaggedSquare, square, BINARY_TOWER_8B_SQUARE_MAP, BinaryField8b);
244
245#[rustfmt::skip]
246const AES_TOWER_8B_SQUARE_MAP: [u8; 256] = [
247    0x00, 0x01, 0x04, 0x05, 0x10, 0x11, 0x14, 0x15, 0x40, 0x41, 0x44, 0x45, 0x50, 0x51, 0x54, 0x55,
248    0x1b, 0x1a, 0x1f, 0x1e, 0x0b, 0x0a, 0x0f, 0x0e, 0x5b, 0x5a, 0x5f, 0x5e, 0x4b, 0x4a, 0x4f, 0x4e,
249    0x6c, 0x6d, 0x68, 0x69, 0x7c, 0x7d, 0x78, 0x79, 0x2c, 0x2d, 0x28, 0x29, 0x3c, 0x3d, 0x38, 0x39,
250    0x77, 0x76, 0x73, 0x72, 0x67, 0x66, 0x63, 0x62, 0x37, 0x36, 0x33, 0x32, 0x27, 0x26, 0x23, 0x22,
251    0xab, 0xaa, 0xaf, 0xae, 0xbb, 0xba, 0xbf, 0xbe, 0xeb, 0xea, 0xef, 0xee, 0xfb, 0xfa, 0xff, 0xfe,
252    0xb0, 0xb1, 0xb4, 0xb5, 0xa0, 0xa1, 0xa4, 0xa5, 0xf0, 0xf1, 0xf4, 0xf5, 0xe0, 0xe1, 0xe4, 0xe5,
253    0xc7, 0xc6, 0xc3, 0xc2, 0xd7, 0xd6, 0xd3, 0xd2, 0x87, 0x86, 0x83, 0x82, 0x97, 0x96, 0x93, 0x92,
254    0xdc, 0xdd, 0xd8, 0xd9, 0xcc, 0xcd, 0xc8, 0xc9, 0x9c, 0x9d, 0x98, 0x99, 0x8c, 0x8d, 0x88, 0x89,
255    0x9a, 0x9b, 0x9e, 0x9f, 0x8a, 0x8b, 0x8e, 0x8f, 0xda, 0xdb, 0xde, 0xdf, 0xca, 0xcb, 0xce, 0xcf,
256    0x81, 0x80, 0x85, 0x84, 0x91, 0x90, 0x95, 0x94, 0xc1, 0xc0, 0xc5, 0xc4, 0xd1, 0xd0, 0xd5, 0xd4,
257    0xf6, 0xf7, 0xf2, 0xf3, 0xe6, 0xe7, 0xe2, 0xe3, 0xb6, 0xb7, 0xb2, 0xb3, 0xa6, 0xa7, 0xa2, 0xa3,
258    0xed, 0xec, 0xe9, 0xe8, 0xfd, 0xfc, 0xf9, 0xf8, 0xad, 0xac, 0xa9, 0xa8, 0xbd, 0xbc, 0xb9, 0xb8,
259    0x31, 0x30, 0x35, 0x34, 0x21, 0x20, 0x25, 0x24, 0x71, 0x70, 0x75, 0x74, 0x61, 0x60, 0x65, 0x64,
260    0x2a, 0x2b, 0x2e, 0x2f, 0x3a, 0x3b, 0x3e, 0x3f, 0x6a, 0x6b, 0x6e, 0x6f, 0x7a, 0x7b, 0x7e, 0x7f,
261    0x5d, 0x5c, 0x59, 0x58, 0x4d, 0x4c, 0x49, 0x48, 0x1d, 0x1c, 0x19, 0x18, 0x0d, 0x0c, 0x09, 0x08,
262    0x46, 0x47, 0x42, 0x43, 0x56, 0x57, 0x52, 0x53, 0x06, 0x07, 0x02, 0x03, 0x16, 0x17, 0x12, 0x13,
263];
264
265impl_unary_ops!(TaggedSquare, square, AES_TOWER_8B_SQUARE_MAP, AESTowerField8b);
266
267#[rustfmt::skip]
268const BINARY_TOWER_8B_MUL_ALPHA_MAP: [u8; 256] = [
269    0x00, 0x10, 0x20, 0x30, 0x40, 0x50, 0x60, 0x70, 0x80, 0x90, 0xa0, 0xb0, 0xc0, 0xd0, 0xe0, 0xf0,
270    0x41, 0x51, 0x61, 0x71, 0x01, 0x11, 0x21, 0x31, 0xc1, 0xd1, 0xe1, 0xf1, 0x81, 0x91, 0xa1, 0xb1,
271    0x82, 0x92, 0xa2, 0xb2, 0xc2, 0xd2, 0xe2, 0xf2, 0x02, 0x12, 0x22, 0x32, 0x42, 0x52, 0x62, 0x72,
272    0xc3, 0xd3, 0xe3, 0xf3, 0x83, 0x93, 0xa3, 0xb3, 0x43, 0x53, 0x63, 0x73, 0x03, 0x13, 0x23, 0x33,
273    0x94, 0x84, 0xb4, 0xa4, 0xd4, 0xc4, 0xf4, 0xe4, 0x14, 0x04, 0x34, 0x24, 0x54, 0x44, 0x74, 0x64,
274    0xd5, 0xc5, 0xf5, 0xe5, 0x95, 0x85, 0xb5, 0xa5, 0x55, 0x45, 0x75, 0x65, 0x15, 0x05, 0x35, 0x25,
275    0x16, 0x06, 0x36, 0x26, 0x56, 0x46, 0x76, 0x66, 0x96, 0x86, 0xb6, 0xa6, 0xd6, 0xc6, 0xf6, 0xe6,
276    0x57, 0x47, 0x77, 0x67, 0x17, 0x07, 0x37, 0x27, 0xd7, 0xc7, 0xf7, 0xe7, 0x97, 0x87, 0xb7, 0xa7,
277    0xe8, 0xf8, 0xc8, 0xd8, 0xa8, 0xb8, 0x88, 0x98, 0x68, 0x78, 0x48, 0x58, 0x28, 0x38, 0x08, 0x18,
278    0xa9, 0xb9, 0x89, 0x99, 0xe9, 0xf9, 0xc9, 0xd9, 0x29, 0x39, 0x09, 0x19, 0x69, 0x79, 0x49, 0x59,
279    0x6a, 0x7a, 0x4a, 0x5a, 0x2a, 0x3a, 0x0a, 0x1a, 0xea, 0xfa, 0xca, 0xda, 0xaa, 0xba, 0x8a, 0x9a,
280    0x2b, 0x3b, 0x0b, 0x1b, 0x6b, 0x7b, 0x4b, 0x5b, 0xab, 0xbb, 0x8b, 0x9b, 0xeb, 0xfb, 0xcb, 0xdb,
281    0x7c, 0x6c, 0x5c, 0x4c, 0x3c, 0x2c, 0x1c, 0x0c, 0xfc, 0xec, 0xdc, 0xcc, 0xbc, 0xac, 0x9c, 0x8c,
282    0x3d, 0x2d, 0x1d, 0x0d, 0x7d, 0x6d, 0x5d, 0x4d, 0xbd, 0xad, 0x9d, 0x8d, 0xfd, 0xed, 0xdd, 0xcd,
283    0xfe, 0xee, 0xde, 0xce, 0xbe, 0xae, 0x9e, 0x8e, 0x7e, 0x6e, 0x5e, 0x4e, 0x3e, 0x2e, 0x1e, 0x0e,
284    0xbf, 0xaf, 0x9f, 0x8f, 0xff, 0xef, 0xdf, 0xcf, 0x3f, 0x2f, 0x1f, 0x0f, 0x7f, 0x6f, 0x5f, 0x4f,
285];
286
287impl_unary_ops!(TaggedMulAlpha, mul_alpha, BINARY_TOWER_8B_MUL_ALPHA_MAP, BinaryField8b);
288
289#[rustfmt::skip]
290const AES_TOWER_8B_MUL_ALPHA_MAP: [u8; 256] = [
291    0x00, 0xd3, 0xbd, 0x6e, 0x61, 0xb2, 0xdc, 0x0f, 0xc2, 0x11, 0x7f, 0xac, 0xa3, 0x70, 0x1e, 0xcd,
292    0x9f, 0x4c, 0x22, 0xf1, 0xfe, 0x2d, 0x43, 0x90, 0x5d, 0x8e, 0xe0, 0x33, 0x3c, 0xef, 0x81, 0x52,
293    0x25, 0xf6, 0x98, 0x4b, 0x44, 0x97, 0xf9, 0x2a, 0xe7, 0x34, 0x5a, 0x89, 0x86, 0x55, 0x3b, 0xe8,
294    0xba, 0x69, 0x07, 0xd4, 0xdb, 0x08, 0x66, 0xb5, 0x78, 0xab, 0xc5, 0x16, 0x19, 0xca, 0xa4, 0x77,
295    0x4a, 0x99, 0xf7, 0x24, 0x2b, 0xf8, 0x96, 0x45, 0x88, 0x5b, 0x35, 0xe6, 0xe9, 0x3a, 0x54, 0x87,
296    0xd5, 0x06, 0x68, 0xbb, 0xb4, 0x67, 0x09, 0xda, 0x17, 0xc4, 0xaa, 0x79, 0x76, 0xa5, 0xcb, 0x18,
297    0x6f, 0xbc, 0xd2, 0x01, 0x0e, 0xdd, 0xb3, 0x60, 0xad, 0x7e, 0x10, 0xc3, 0xcc, 0x1f, 0x71, 0xa2,
298    0xf0, 0x23, 0x4d, 0x9e, 0x91, 0x42, 0x2c, 0xff, 0x32, 0xe1, 0x8f, 0x5c, 0x53, 0x80, 0xee, 0x3d,
299    0x94, 0x47, 0x29, 0xfa, 0xf5, 0x26, 0x48, 0x9b, 0x56, 0x85, 0xeb, 0x38, 0x37, 0xe4, 0x8a, 0x59,
300    0x0b, 0xd8, 0xb6, 0x65, 0x6a, 0xb9, 0xd7, 0x04, 0xc9, 0x1a, 0x74, 0xa7, 0xa8, 0x7b, 0x15, 0xc6,
301    0xb1, 0x62, 0x0c, 0xdf, 0xd0, 0x03, 0x6d, 0xbe, 0x73, 0xa0, 0xce, 0x1d, 0x12, 0xc1, 0xaf, 0x7c,
302    0x2e, 0xfd, 0x93, 0x40, 0x4f, 0x9c, 0xf2, 0x21, 0xec, 0x3f, 0x51, 0x82, 0x8d, 0x5e, 0x30, 0xe3,
303    0xde, 0x0d, 0x63, 0xb0, 0xbf, 0x6c, 0x02, 0xd1, 0x1c, 0xcf, 0xa1, 0x72, 0x7d, 0xae, 0xc0, 0x13,
304    0x41, 0x92, 0xfc, 0x2f, 0x20, 0xf3, 0x9d, 0x4e, 0x83, 0x50, 0x3e, 0xed, 0xe2, 0x31, 0x5f, 0x8c,
305    0xfb, 0x28, 0x46, 0x95, 0x9a, 0x49, 0x27, 0xf4, 0x39, 0xea, 0x84, 0x57, 0x58, 0x8b, 0xe5, 0x36,
306    0x64, 0xb7, 0xd9, 0x0a, 0x05, 0xd6, 0xb8, 0x6b, 0xa6, 0x75, 0x1b, 0xc8, 0xc7, 0x14, 0x7a, 0xa9,
307];
308
309impl_unary_ops!(TaggedMulAlpha, mul_alpha, AES_TOWER_8B_MUL_ALPHA_MAP, AESTowerField8b);
310
311#[rustfmt::skip]
312const BINARY_TOWER_8B_INVERT_MAP : [u8; 256] = [
313	0x00, 0x01, 0x03, 0x02, 0x06, 0x0e, 0x04, 0x0f, 0x0d, 0x0a, 0x09, 0x0c, 0x0b, 0x08, 0x05, 0x07,
314	0x14, 0x67, 0x94, 0x7b, 0x10, 0x66, 0x9e, 0x7e, 0xd2, 0x81, 0x27, 0x4b, 0xd1, 0x8f, 0x2f, 0x42,
315	0x3c, 0xe6, 0xde, 0x7c, 0xb3, 0xc1, 0x4a, 0x1a, 0x30, 0xe9, 0xdd, 0x79, 0xb1, 0xc6, 0x43, 0x1e,
316	0x28, 0xe8, 0x9d, 0xb9, 0x63, 0x39, 0x8d, 0xc2, 0x62, 0x35, 0x83, 0xc5, 0x20, 0xe7, 0x97, 0xbb,
317	0x61, 0x48, 0x1f, 0x2e, 0xac, 0xc8, 0xbc, 0x56, 0x41, 0x60, 0x26, 0x1b, 0xcf, 0xaa, 0x5b, 0xbe,
318	0xef, 0x73, 0x6d, 0x5e, 0xf7, 0x86, 0x47, 0xbd, 0x88, 0xfc, 0xbf, 0x4e, 0x76, 0xe0, 0x53, 0x6c,
319	0x49, 0x40, 0x38, 0x34, 0xe4, 0xeb, 0x15, 0x11, 0x8b, 0x85, 0xaf, 0xa9, 0x5f, 0x52, 0x98, 0x92,
320	0xfb, 0xb5, 0xee, 0x51, 0xb7, 0xf0, 0x5c, 0xe1, 0xdc, 0x2b, 0x95, 0x13, 0x23, 0xdf, 0x17, 0x9f,
321	0xd3, 0x19, 0xc4, 0x3a, 0x8a, 0x69, 0x55, 0xf6, 0x58, 0xfd, 0x84, 0x68, 0xc3, 0x36, 0xd0, 0x1d,
322	0xa6, 0xf3, 0x6f, 0x99, 0x12, 0x7a, 0xba, 0x3e, 0x6e, 0x93, 0xa0, 0xf8, 0xb8, 0x32, 0x16, 0x7f,
323	0x9a, 0xf9, 0xe2, 0xdb, 0xed, 0xd8, 0x90, 0xf2, 0xae, 0x6b, 0x4d, 0xce, 0x44, 0xc9, 0xa8, 0x6a,
324	0xc7, 0x2c, 0xc0, 0x24, 0xfa, 0x71, 0xf1, 0x74, 0x9c, 0x33, 0x96, 0x3f, 0x46, 0x57, 0x4f, 0x5a,
325	0xb2, 0x25, 0x37, 0x8c, 0x82, 0x3b, 0x2d, 0xb0, 0x45, 0xad, 0xd7, 0xff, 0xf4, 0xd4, 0xab, 0x4c,
326	0x8e, 0x1c, 0x18, 0x80, 0xcd, 0xf5, 0xfe, 0xca, 0xa5, 0xec, 0xe3, 0xa3, 0x78, 0x2a, 0x22, 0x7d,
327	0x5d, 0x77, 0xa2, 0xda, 0x64, 0xea, 0x21, 0x3d, 0x31, 0x29, 0xe5, 0x65, 0xd9, 0xa4, 0x72, 0x50,
328	0x75, 0xb6, 0xa7, 0x91, 0xcc, 0xd5, 0x87, 0x54, 0x9b, 0xa1, 0xb4, 0x70, 0x59, 0x89, 0xd6, 0xcb,
329];
330
331impl_unary_ops!(TaggedInvertOrZero, invert_or_zero, BINARY_TOWER_8B_INVERT_MAP, BinaryField8b);
332impl_unary_ops!(TaggedInvertOrZero, invert_or_zero, BINARY_TOWER_8B_INVERT_MAP, BinaryField4b);
333impl_unary_ops!(TaggedInvertOrZero, invert_or_zero, BINARY_TOWER_8B_INVERT_MAP, BinaryField2b);
334
335#[rustfmt::skip]
336const AES_TOWER_8B_INVERT_MAP: [u8; 256] = [
337    0x00, 0x01, 0x8d, 0xf6, 0xcb, 0x52, 0x7b, 0xd1, 0xe8, 0x4f, 0x29, 0xc0, 0xb0, 0xe1, 0xe5, 0xc7,
338    0x74, 0xb4, 0xaa, 0x4b, 0x99, 0x2b, 0x60, 0x5f, 0x58, 0x3f, 0xfd, 0xcc, 0xff, 0x40, 0xee, 0xb2,
339    0x3a, 0x6e, 0x5a, 0xf1, 0x55, 0x4d, 0xa8, 0xc9, 0xc1, 0x0a, 0x98, 0x15, 0x30, 0x44, 0xa2, 0xc2,
340    0x2c, 0x45, 0x92, 0x6c, 0xf3, 0x39, 0x66, 0x42, 0xf2, 0x35, 0x20, 0x6f, 0x77, 0xbb, 0x59, 0x19,
341    0x1d, 0xfe, 0x37, 0x67, 0x2d, 0x31, 0xf5, 0x69, 0xa7, 0x64, 0xab, 0x13, 0x54, 0x25, 0xe9, 0x09,
342    0xed, 0x5c, 0x05, 0xca, 0x4c, 0x24, 0x87, 0xbf, 0x18, 0x3e, 0x22, 0xf0, 0x51, 0xec, 0x61, 0x17,
343    0x16, 0x5e, 0xaf, 0xd3, 0x49, 0xa6, 0x36, 0x43, 0xf4, 0x47, 0x91, 0xdf, 0x33, 0x93, 0x21, 0x3b,
344    0x79, 0xb7, 0x97, 0x85, 0x10, 0xb5, 0xba, 0x3c, 0xb6, 0x70, 0xd0, 0x06, 0xa1, 0xfa, 0x81, 0x82,
345    0x83, 0x7e, 0x7f, 0x80, 0x96, 0x73, 0xbe, 0x56, 0x9b, 0x9e, 0x95, 0xd9, 0xf7, 0x02, 0xb9, 0xa4,
346    0xde, 0x6a, 0x32, 0x6d, 0xd8, 0x8a, 0x84, 0x72, 0x2a, 0x14, 0x9f, 0x88, 0xf9, 0xdc, 0x89, 0x9a,
347    0xfb, 0x7c, 0x2e, 0xc3, 0x8f, 0xb8, 0x65, 0x48, 0x26, 0xc8, 0x12, 0x4a, 0xce, 0xe7, 0xd2, 0x62,
348    0x0c, 0xe0, 0x1f, 0xef, 0x11, 0x75, 0x78, 0x71, 0xa5, 0x8e, 0x76, 0x3d, 0xbd, 0xbc, 0x86, 0x57,
349    0x0b, 0x28, 0x2f, 0xa3, 0xda, 0xd4, 0xe4, 0x0f, 0xa9, 0x27, 0x53, 0x04, 0x1b, 0xfc, 0xac, 0xe6,
350    0x7a, 0x07, 0xae, 0x63, 0xc5, 0xdb, 0xe2, 0xea, 0x94, 0x8b, 0xc4, 0xd5, 0x9d, 0xf8, 0x90, 0x6b,
351    0xb1, 0x0d, 0xd6, 0xeb, 0xc6, 0x0e, 0xcf, 0xad, 0x08, 0x4e, 0xd7, 0xe3, 0x5d, 0x50, 0x1e, 0xb3,
352    0x5b, 0x23, 0x38, 0x34, 0x68, 0x46, 0x03, 0x8c, 0xdd, 0x9c, 0x7d, 0xa0, 0xcd, 0x1a, 0x41, 0x1c,
353];
354
355impl_unary_ops!(TaggedInvertOrZero, invert_or_zero, AES_TOWER_8B_INVERT_MAP, AESTowerField8b);
356
357#[cfg(test)]
358mod tests {
359	use super::*;
360	use crate::test_utils::{
361		define_invert_tests, define_mul_alpha_tests, define_multiply_tests, define_square_tests,
362	};
363
364	define_multiply_tests!(TaggedMul<PairwiseTableStrategy>::mul, TaggedMul<PairwiseTableStrategy>);
365
366	define_square_tests!(
367		TaggedSquare<PairwiseTableStrategy>::square,
368		TaggedSquare<PairwiseTableStrategy>
369	);
370
371	define_invert_tests!(
372		TaggedInvertOrZero<PairwiseTableStrategy>::invert_or_zero,
373		TaggedInvertOrZero<PairwiseTableStrategy>
374	);
375
376	define_mul_alpha_tests!(
377		TaggedMulAlpha<PairwiseTableStrategy>::mul_alpha,
378		TaggedMulAlpha<PairwiseTableStrategy>
379	);
380}
binius_field/arch/portable/pairwise_table_arithmetic.rs

binius_field/arch/portable/
pairwise_table_arithmetic.rs
