binius_field/arch/portable/
pairwise_table_arithmetic.rs

1// Copyright 2024-2025 Irreducible Inc.
2
3use super::packed::PackedPrimitiveType;
4use crate::{
5	AESTowerField8b,
6	arch::PairwiseTableStrategy,
7	arithmetic_traits::{TaggedInvertOrZero, TaggedMul, TaggedMulAlpha, TaggedSquare},
8	packed::PackedField,
9	underlier::UnderlierType,
10};
11
12impl<U: UnderlierType> TaggedMul<PairwiseTableStrategy> for PackedPrimitiveType<U, AESTowerField8b>
13where
14	Self: PackedField<Scalar = AESTowerField8b>,
15{
16	#[inline]
17	fn mul(self, rhs: Self) -> Self {
18		#[rustfmt::skip]
19		const AES_EXP_TABLE: [u8; 256] = [
20			0x01, 0x03, 0x05, 0x0f, 0x11, 0x33, 0x55, 0xff, 0x1a, 0x2e, 0x72, 0x96, 0xa1, 0xf8, 0x13, 0x35,
21			0x5f, 0xe1, 0x38, 0x48, 0xd8, 0x73, 0x95, 0xa4, 0xf7, 0x02, 0x06, 0x0a, 0x1e, 0x22, 0x66, 0xaa,
22			0xe5, 0x34, 0x5c, 0xe4, 0x37, 0x59, 0xeb, 0x26, 0x6a, 0xbe, 0xd9, 0x70, 0x90, 0xab, 0xe6, 0x31,
23			0x53, 0xf5, 0x04, 0x0c, 0x14, 0x3c, 0x44, 0xcc, 0x4f, 0xd1, 0x68, 0xb8, 0xd3, 0x6e, 0xb2, 0xcd,
24			0x4c, 0xd4, 0x67, 0xa9, 0xe0, 0x3b, 0x4d, 0xd7, 0x62, 0xa6, 0xf1, 0x08, 0x18, 0x28, 0x78, 0x88,
25			0x83, 0x9e, 0xb9, 0xd0, 0x6b, 0xbd, 0xdc, 0x7f, 0x81, 0x98, 0xb3, 0xce, 0x49, 0xdb, 0x76, 0x9a,
26			0xb5, 0xc4, 0x57, 0xf9, 0x10, 0x30, 0x50, 0xf0, 0x0b, 0x1d, 0x27, 0x69, 0xbb, 0xd6, 0x61, 0xa3,
27			0xfe, 0x19, 0x2b, 0x7d, 0x87, 0x92, 0xad, 0xec, 0x2f, 0x71, 0x93, 0xae, 0xe9, 0x20, 0x60, 0xa0,
28			0xfb, 0x16, 0x3a, 0x4e, 0xd2, 0x6d, 0xb7, 0xc2, 0x5d, 0xe7, 0x32, 0x56, 0xfa, 0x15, 0x3f, 0x41,
29			0xc3, 0x5e, 0xe2, 0x3d, 0x47, 0xc9, 0x40, 0xc0, 0x5b, 0xed, 0x2c, 0x74, 0x9c, 0xbf, 0xda, 0x75,
30			0x9f, 0xba, 0xd5, 0x64, 0xac, 0xef, 0x2a, 0x7e, 0x82, 0x9d, 0xbc, 0xdf, 0x7a, 0x8e, 0x89, 0x80,
31			0x9b, 0xb6, 0xc1, 0x58, 0xe8, 0x23, 0x65, 0xaf, 0xea, 0x25, 0x6f, 0xb1, 0xc8, 0x43, 0xc5, 0x54,
32			0xfc, 0x1f, 0x21, 0x63, 0xa5, 0xf4, 0x07, 0x09, 0x1b, 0x2d, 0x77, 0x99, 0xb0, 0xcb, 0x46, 0xca,
33			0x45, 0xcf, 0x4a, 0xde, 0x79, 0x8b, 0x86, 0x91, 0xa8, 0xe3, 0x3e, 0x42, 0xc6, 0x51, 0xf3, 0x0e,
34			0x12, 0x36, 0x5a, 0xee, 0x29, 0x7b, 0x8d, 0x8c, 0x8f, 0x8a, 0x85, 0x94, 0xa7, 0xf2, 0x0d, 0x17,
35			0x39, 0x4b, 0xdd, 0x7c, 0x84, 0x97, 0xa2, 0xfd, 0x1c, 0x24, 0x6c, 0xb4, 0xc7, 0x52, 0xf6, 0x0
36		];
37
38		#[rustfmt::skip]
39		const AES_LOG_TABLE: [u8; 256] = [
40			0x00, 0x00, 0x19, 0x01, 0x32, 0x02, 0x1a, 0xc6, 0x4b, 0xc7, 0x1b, 0x68, 0x33, 0xee, 0xdf, 0x03,
41			0x64, 0x04, 0xe0, 0x0e, 0x34, 0x8d, 0x81, 0xef, 0x4c, 0x71, 0x08, 0xc8, 0xf8, 0x69, 0x1c, 0xc1,
42			0x7d, 0xc2, 0x1d, 0xb5, 0xf9, 0xb9, 0x27, 0x6a, 0x4d, 0xe4, 0xa6, 0x72, 0x9a, 0xc9, 0x09, 0x78,
43			0x65, 0x2f, 0x8a, 0x05, 0x21, 0x0f, 0xe1, 0x24, 0x12, 0xf0, 0x82, 0x45, 0x35, 0x93, 0xda, 0x8e,
44			0x96, 0x8f, 0xdb, 0xbd, 0x36, 0xd0, 0xce, 0x94, 0x13, 0x5c, 0xd2, 0xf1, 0x40, 0x46, 0x83, 0x38,
45			0x66, 0xdd, 0xfd, 0x30, 0xbf, 0x06, 0x8b, 0x62, 0xb3, 0x25, 0xe2, 0x98, 0x22, 0x88, 0x91, 0x10,
46			0x7e, 0x6e, 0x48, 0xc3, 0xa3, 0xb6, 0x1e, 0x42, 0x3a, 0x6b, 0x28, 0x54, 0xfa, 0x85, 0x3d, 0xba,
47			0x2b, 0x79, 0x0a, 0x15, 0x9b, 0x9f, 0x5e, 0xca, 0x4e, 0xd4, 0xac, 0xe5, 0xf3, 0x73, 0xa7, 0x57,
48			0xaf, 0x58, 0xa8, 0x50, 0xf4, 0xea, 0xd6, 0x74, 0x4f, 0xae, 0xe9, 0xd5, 0xe7, 0xe6, 0xad, 0xe8,
49			0x2c, 0xd7, 0x75, 0x7a, 0xeb, 0x16, 0x0b, 0xf5, 0x59, 0xcb, 0x5f, 0xb0, 0x9c, 0xa9, 0x51, 0xa0,
50			0x7f, 0x0c, 0xf6, 0x6f, 0x17, 0xc4, 0x49, 0xec, 0xd8, 0x43, 0x1f, 0x2d, 0xa4, 0x76, 0x7b, 0xb7,
51			0xcc, 0xbb, 0x3e, 0x5a, 0xfb, 0x60, 0xb1, 0x86, 0x3b, 0x52, 0xa1, 0x6c, 0xaa, 0x55, 0x29, 0x9d,
52			0x97, 0xb2, 0x87, 0x90, 0x61, 0xbe, 0xdc, 0xfc, 0xbc, 0x95, 0xcf, 0xcd, 0x37, 0x3f, 0x5b, 0xd1,
53			0x53, 0x39, 0x84, 0x3c, 0x41, 0xa2, 0x6d, 0x47, 0x14, 0x2a, 0x9e, 0x5d, 0x56, 0xf2, 0xd3, 0xab,
54			0x44, 0x11, 0x92, 0xd9, 0x23, 0x20, 0x2e, 0x89, 0xb4, 0x7c, 0xb8, 0x26, 0x77, 0x99, 0xe3, 0xa5,
55			0x67, 0x4a, 0xed, 0xde, 0xc5, 0x31, 0xfe, 0x18, 0x0d, 0x63, 0x8c, 0x80, 0xc0, 0xf7, 0x70, 0x07,
56		];
57
58		Self::from_fn(|i| {
59			multiply_8b_using_log_table(
60				self.get(i).val(),
61				rhs.get(i).val(),
62				&AES_LOG_TABLE,
63				&AES_EXP_TABLE,
64			)
65			.into()
66		})
67	}
68}
69
70#[inline]
71fn multiply_8b_using_log_table(
72	lhs: u8,
73	rhs: u8,
74	log_table: &[u8; 256],
75	exp_table: &[u8; 256],
76) -> u8 {
77	if lhs != 0 && rhs != 0 {
78		let log_table_index = log_table[lhs as usize] as usize + log_table[rhs as usize] as usize;
79		let log_table_index = if log_table_index > 254 {
80			log_table_index - 255
81		} else {
82			log_table_index
83		};
84
85		unsafe {
86			// Safety: `log_table_index` is smaller than 255 because:
87			// - all values in `LOG_TABLE` do not exceed 254
88			// - sum of two values do not exceed 254*2
89			// - the previous line reduces `log_table_index` by 255 if it is
90			// bigger than 254
91			*exp_table.get_unchecked(log_table_index)
92		}
93	} else {
94		0
95	}
96}
97
98/// Return the result of the operation by a table search for each scalar value
99#[inline(always)]
100fn unary_op_with_table<PT>(val: PT, table: &[u8; 256]) -> PT
101where
102	PT: PackedField,
103	PT::Scalar: From<u8>,
104	u8: From<PT::Scalar>,
105{
106	PT::from_fn(|i| table[u8::from(val.get(i)) as usize].into())
107}
108
109/// Implement unary operation with a table search
110macro_rules! impl_unary_ops {
111	($tagged_op_type:ident, $method_name:ident, $table:ident, $field:ty) => {
112		impl<U: UnderlierType> $tagged_op_type<PairwiseTableStrategy>
113			for PackedPrimitiveType<U, $field>
114		where
115			Self: PackedField<Scalar = $field>,
116		{
117			#[inline(always)]
118			fn $method_name(self) -> Self {
119				unary_op_with_table(self, &$table)
120			}
121		}
122	};
123}
124
125#[rustfmt::skip]
126const AES_TOWER_8B_SQUARE_MAP: [u8; 256] = [
127    0x00, 0x01, 0x04, 0x05, 0x10, 0x11, 0x14, 0x15, 0x40, 0x41, 0x44, 0x45, 0x50, 0x51, 0x54, 0x55,
128    0x1b, 0x1a, 0x1f, 0x1e, 0x0b, 0x0a, 0x0f, 0x0e, 0x5b, 0x5a, 0x5f, 0x5e, 0x4b, 0x4a, 0x4f, 0x4e,
129    0x6c, 0x6d, 0x68, 0x69, 0x7c, 0x7d, 0x78, 0x79, 0x2c, 0x2d, 0x28, 0x29, 0x3c, 0x3d, 0x38, 0x39,
130    0x77, 0x76, 0x73, 0x72, 0x67, 0x66, 0x63, 0x62, 0x37, 0x36, 0x33, 0x32, 0x27, 0x26, 0x23, 0x22,
131    0xab, 0xaa, 0xaf, 0xae, 0xbb, 0xba, 0xbf, 0xbe, 0xeb, 0xea, 0xef, 0xee, 0xfb, 0xfa, 0xff, 0xfe,
132    0xb0, 0xb1, 0xb4, 0xb5, 0xa0, 0xa1, 0xa4, 0xa5, 0xf0, 0xf1, 0xf4, 0xf5, 0xe0, 0xe1, 0xe4, 0xe5,
133    0xc7, 0xc6, 0xc3, 0xc2, 0xd7, 0xd6, 0xd3, 0xd2, 0x87, 0x86, 0x83, 0x82, 0x97, 0x96, 0x93, 0x92,
134    0xdc, 0xdd, 0xd8, 0xd9, 0xcc, 0xcd, 0xc8, 0xc9, 0x9c, 0x9d, 0x98, 0x99, 0x8c, 0x8d, 0x88, 0x89,
135    0x9a, 0x9b, 0x9e, 0x9f, 0x8a, 0x8b, 0x8e, 0x8f, 0xda, 0xdb, 0xde, 0xdf, 0xca, 0xcb, 0xce, 0xcf,
136    0x81, 0x80, 0x85, 0x84, 0x91, 0x90, 0x95, 0x94, 0xc1, 0xc0, 0xc5, 0xc4, 0xd1, 0xd0, 0xd5, 0xd4,
137    0xf6, 0xf7, 0xf2, 0xf3, 0xe6, 0xe7, 0xe2, 0xe3, 0xb6, 0xb7, 0xb2, 0xb3, 0xa6, 0xa7, 0xa2, 0xa3,
138    0xed, 0xec, 0xe9, 0xe8, 0xfd, 0xfc, 0xf9, 0xf8, 0xad, 0xac, 0xa9, 0xa8, 0xbd, 0xbc, 0xb9, 0xb8,
139    0x31, 0x30, 0x35, 0x34, 0x21, 0x20, 0x25, 0x24, 0x71, 0x70, 0x75, 0x74, 0x61, 0x60, 0x65, 0x64,
140    0x2a, 0x2b, 0x2e, 0x2f, 0x3a, 0x3b, 0x3e, 0x3f, 0x6a, 0x6b, 0x6e, 0x6f, 0x7a, 0x7b, 0x7e, 0x7f,
141    0x5d, 0x5c, 0x59, 0x58, 0x4d, 0x4c, 0x49, 0x48, 0x1d, 0x1c, 0x19, 0x18, 0x0d, 0x0c, 0x09, 0x08,
142    0x46, 0x47, 0x42, 0x43, 0x56, 0x57, 0x52, 0x53, 0x06, 0x07, 0x02, 0x03, 0x16, 0x17, 0x12, 0x13,
143];
144
145impl_unary_ops!(TaggedSquare, square, AES_TOWER_8B_SQUARE_MAP, AESTowerField8b);
146
147#[rustfmt::skip]
148const AES_TOWER_8B_MUL_ALPHA_MAP: [u8; 256] = [
149    0x00, 0xd3, 0xbd, 0x6e, 0x61, 0xb2, 0xdc, 0x0f, 0xc2, 0x11, 0x7f, 0xac, 0xa3, 0x70, 0x1e, 0xcd,
150    0x9f, 0x4c, 0x22, 0xf1, 0xfe, 0x2d, 0x43, 0x90, 0x5d, 0x8e, 0xe0, 0x33, 0x3c, 0xef, 0x81, 0x52,
151    0x25, 0xf6, 0x98, 0x4b, 0x44, 0x97, 0xf9, 0x2a, 0xe7, 0x34, 0x5a, 0x89, 0x86, 0x55, 0x3b, 0xe8,
152    0xba, 0x69, 0x07, 0xd4, 0xdb, 0x08, 0x66, 0xb5, 0x78, 0xab, 0xc5, 0x16, 0x19, 0xca, 0xa4, 0x77,
153    0x4a, 0x99, 0xf7, 0x24, 0x2b, 0xf8, 0x96, 0x45, 0x88, 0x5b, 0x35, 0xe6, 0xe9, 0x3a, 0x54, 0x87,
154    0xd5, 0x06, 0x68, 0xbb, 0xb4, 0x67, 0x09, 0xda, 0x17, 0xc4, 0xaa, 0x79, 0x76, 0xa5, 0xcb, 0x18,
155    0x6f, 0xbc, 0xd2, 0x01, 0x0e, 0xdd, 0xb3, 0x60, 0xad, 0x7e, 0x10, 0xc3, 0xcc, 0x1f, 0x71, 0xa2,
156    0xf0, 0x23, 0x4d, 0x9e, 0x91, 0x42, 0x2c, 0xff, 0x32, 0xe1, 0x8f, 0x5c, 0x53, 0x80, 0xee, 0x3d,
157    0x94, 0x47, 0x29, 0xfa, 0xf5, 0x26, 0x48, 0x9b, 0x56, 0x85, 0xeb, 0x38, 0x37, 0xe4, 0x8a, 0x59,
158    0x0b, 0xd8, 0xb6, 0x65, 0x6a, 0xb9, 0xd7, 0x04, 0xc9, 0x1a, 0x74, 0xa7, 0xa8, 0x7b, 0x15, 0xc6,
159    0xb1, 0x62, 0x0c, 0xdf, 0xd0, 0x03, 0x6d, 0xbe, 0x73, 0xa0, 0xce, 0x1d, 0x12, 0xc1, 0xaf, 0x7c,
160    0x2e, 0xfd, 0x93, 0x40, 0x4f, 0x9c, 0xf2, 0x21, 0xec, 0x3f, 0x51, 0x82, 0x8d, 0x5e, 0x30, 0xe3,
161    0xde, 0x0d, 0x63, 0xb0, 0xbf, 0x6c, 0x02, 0xd1, 0x1c, 0xcf, 0xa1, 0x72, 0x7d, 0xae, 0xc0, 0x13,
162    0x41, 0x92, 0xfc, 0x2f, 0x20, 0xf3, 0x9d, 0x4e, 0x83, 0x50, 0x3e, 0xed, 0xe2, 0x31, 0x5f, 0x8c,
163    0xfb, 0x28, 0x46, 0x95, 0x9a, 0x49, 0x27, 0xf4, 0x39, 0xea, 0x84, 0x57, 0x58, 0x8b, 0xe5, 0x36,
164    0x64, 0xb7, 0xd9, 0x0a, 0x05, 0xd6, 0xb8, 0x6b, 0xa6, 0x75, 0x1b, 0xc8, 0xc7, 0x14, 0x7a, 0xa9,
165];
166
167impl_unary_ops!(TaggedMulAlpha, mul_alpha, AES_TOWER_8B_MUL_ALPHA_MAP, AESTowerField8b);
168
169#[rustfmt::skip]
170const AES_TOWER_8B_INVERT_MAP: [u8; 256] = [
171    0x00, 0x01, 0x8d, 0xf6, 0xcb, 0x52, 0x7b, 0xd1, 0xe8, 0x4f, 0x29, 0xc0, 0xb0, 0xe1, 0xe5, 0xc7,
172    0x74, 0xb4, 0xaa, 0x4b, 0x99, 0x2b, 0x60, 0x5f, 0x58, 0x3f, 0xfd, 0xcc, 0xff, 0x40, 0xee, 0xb2,
173    0x3a, 0x6e, 0x5a, 0xf1, 0x55, 0x4d, 0xa8, 0xc9, 0xc1, 0x0a, 0x98, 0x15, 0x30, 0x44, 0xa2, 0xc2,
174    0x2c, 0x45, 0x92, 0x6c, 0xf3, 0x39, 0x66, 0x42, 0xf2, 0x35, 0x20, 0x6f, 0x77, 0xbb, 0x59, 0x19,
175    0x1d, 0xfe, 0x37, 0x67, 0x2d, 0x31, 0xf5, 0x69, 0xa7, 0x64, 0xab, 0x13, 0x54, 0x25, 0xe9, 0x09,
176    0xed, 0x5c, 0x05, 0xca, 0x4c, 0x24, 0x87, 0xbf, 0x18, 0x3e, 0x22, 0xf0, 0x51, 0xec, 0x61, 0x17,
177    0x16, 0x5e, 0xaf, 0xd3, 0x49, 0xa6, 0x36, 0x43, 0xf4, 0x47, 0x91, 0xdf, 0x33, 0x93, 0x21, 0x3b,
178    0x79, 0xb7, 0x97, 0x85, 0x10, 0xb5, 0xba, 0x3c, 0xb6, 0x70, 0xd0, 0x06, 0xa1, 0xfa, 0x81, 0x82,
179    0x83, 0x7e, 0x7f, 0x80, 0x96, 0x73, 0xbe, 0x56, 0x9b, 0x9e, 0x95, 0xd9, 0xf7, 0x02, 0xb9, 0xa4,
180    0xde, 0x6a, 0x32, 0x6d, 0xd8, 0x8a, 0x84, 0x72, 0x2a, 0x14, 0x9f, 0x88, 0xf9, 0xdc, 0x89, 0x9a,
181    0xfb, 0x7c, 0x2e, 0xc3, 0x8f, 0xb8, 0x65, 0x48, 0x26, 0xc8, 0x12, 0x4a, 0xce, 0xe7, 0xd2, 0x62,
182    0x0c, 0xe0, 0x1f, 0xef, 0x11, 0x75, 0x78, 0x71, 0xa5, 0x8e, 0x76, 0x3d, 0xbd, 0xbc, 0x86, 0x57,
183    0x0b, 0x28, 0x2f, 0xa3, 0xda, 0xd4, 0xe4, 0x0f, 0xa9, 0x27, 0x53, 0x04, 0x1b, 0xfc, 0xac, 0xe6,
184    0x7a, 0x07, 0xae, 0x63, 0xc5, 0xdb, 0xe2, 0xea, 0x94, 0x8b, 0xc4, 0xd5, 0x9d, 0xf8, 0x90, 0x6b,
185    0xb1, 0x0d, 0xd6, 0xeb, 0xc6, 0x0e, 0xcf, 0xad, 0x08, 0x4e, 0xd7, 0xe3, 0x5d, 0x50, 0x1e, 0xb3,
186    0x5b, 0x23, 0x38, 0x34, 0x68, 0x46, 0x03, 0x8c, 0xdd, 0x9c, 0x7d, 0xa0, 0xcd, 0x1a, 0x41, 0x1c,
187];
188
189impl_unary_ops!(TaggedInvertOrZero, invert_or_zero, AES_TOWER_8B_INVERT_MAP, AESTowerField8b);
190
191#[cfg(test)]
192mod tests {
193	use super::*;
194	use crate::test_utils::{define_invert_tests, define_multiply_tests, define_square_tests};
195
196	define_multiply_tests!(TaggedMul<PairwiseTableStrategy>::mul, TaggedMul<PairwiseTableStrategy>);
197
198	define_square_tests!(
199		TaggedSquare<PairwiseTableStrategy>::square,
200		TaggedSquare<PairwiseTableStrategy>
201	);
202
203	define_invert_tests!(
204		TaggedInvertOrZero<PairwiseTableStrategy>::invert_or_zero,
205		TaggedInvertOrZero<PairwiseTableStrategy>
206	);
207}
binius_field/arch/portable/pairwise_table_arithmetic.rs

binius_field/arch/portable/
pairwise_table_arithmetic.rs
