Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
biggroup_tables.hpp
Go to the documentation of this file.
1// === AUDIT STATUS ===
2// internal: { status: not started, auditors: [], date: YYYY-MM-DD }
3// external_1: { status: not started, auditors: [], date: YYYY-MM-DD }
4// external_2: { status: not started, auditors: [], date: YYYY-MM-DD }
5// =====================
6
7#pragma once
8#include "barretenberg/stdlib/primitives/biggroup/biggroup.hpp"
9#include "barretenberg/stdlib/primitives/memory/twin_rom_table.hpp"
10#include "barretenberg/stdlib_circuit_builders/plookup_tables/types.hpp"
11namespace bb::stdlib::element_default {
12
13using plookup::MultiTableId;
14
31template <typename C, class Fq, class Fr, class G>
32template <size_t num_elements>
33std::array<twin_rom_table<C>, 5> element<C, Fq, Fr, G>::create_group_element_rom_tables(
34 const std::array<element, num_elements>& rom_data, std::array<uint256_t, 8>& limb_max)
35{
36 std::vector<std::array<field_t<C>, 2>> x_lo_limbs;
37 std::vector<std::array<field_t<C>, 2>> x_hi_limbs;
38 std::vector<std::array<field_t<C>, 2>> y_lo_limbs;
39 std::vector<std::array<field_t<C>, 2>> y_hi_limbs;
40 std::vector<std::array<field_t<C>, 2>> prime_limbs;
41
42 for (size_t i = 0; i < num_elements; ++i) {
43 limb_max[0] = std::max(limb_max[0], rom_data[i].x.binary_basis_limbs[0].maximum_value);
44 limb_max[1] = std::max(limb_max[1], rom_data[i].x.binary_basis_limbs[1].maximum_value);
45 limb_max[2] = std::max(limb_max[2], rom_data[i].x.binary_basis_limbs[2].maximum_value);
46 limb_max[3] = std::max(limb_max[3], rom_data[i].x.binary_basis_limbs[3].maximum_value);
47 limb_max[4] = std::max(limb_max[4], rom_data[i].y.binary_basis_limbs[0].maximum_value);
48 limb_max[5] = std::max(limb_max[5], rom_data[i].y.binary_basis_limbs[1].maximum_value);
49 limb_max[6] = std::max(limb_max[6], rom_data[i].y.binary_basis_limbs[2].maximum_value);
50 limb_max[7] = std::max(limb_max[7], rom_data[i].y.binary_basis_limbs[3].maximum_value);
51
52 x_lo_limbs.emplace_back(std::array<field_t<C>, 2>{ rom_data[i].x.binary_basis_limbs[0].element,
53 rom_data[i].x.binary_basis_limbs[1].element });
54 x_hi_limbs.emplace_back(std::array<field_t<C>, 2>{ rom_data[i].x.binary_basis_limbs[2].element,
55 rom_data[i].x.binary_basis_limbs[3].element });
56 y_lo_limbs.emplace_back(std::array<field_t<C>, 2>{ rom_data[i].y.binary_basis_limbs[0].element,
57 rom_data[i].y.binary_basis_limbs[1].element });
58 y_hi_limbs.emplace_back(std::array<field_t<C>, 2>{ rom_data[i].y.binary_basis_limbs[2].element,
59 rom_data[i].y.binary_basis_limbs[3].element });
60 prime_limbs.emplace_back(
61 std::array<field_t<C>, 2>{ rom_data[i].x.prime_basis_limb, rom_data[i].y.prime_basis_limb });
62 }
63 std::array<twin_rom_table<C>, 5> output_tables;
64 output_tables[0] = twin_rom_table<C>(x_lo_limbs);
65 output_tables[1] = twin_rom_table<C>(x_hi_limbs);
66 output_tables[2] = twin_rom_table<C>(y_lo_limbs);
67 output_tables[3] = twin_rom_table<C>(y_hi_limbs);
68 output_tables[4] = twin_rom_table<C>(prime_limbs);
69 return output_tables;
70}
71
72template <typename C, class Fq, class Fr, class G>
73template <size_t>
74element<C, Fq, Fr, G> element<C, Fq, Fr, G>::read_group_element_rom_tables(
75 const std::array<twin_rom_table<C>, 5>& tables, const field_t<C>& index, const std::array<uint256_t, 8>& limb_max)
76{
77 const auto xlo = tables[0][index];
78 const auto xhi = tables[1][index];
79 const auto ylo = tables[2][index];
80 const auto yhi = tables[3][index];
81 const auto xyprime = tables[4][index];
82
83 // We assign maximum_value of each limb here, so we can use the unsafe API from element construction
84 Fq x_fq = Fq::unsafe_construct_from_limbs(xlo[0], xlo[1], xhi[0], xhi[1], xyprime[0]);
85 Fq y_fq = Fq::unsafe_construct_from_limbs(ylo[0], ylo[1], yhi[0], yhi[1], xyprime[1]);
86 x_fq.binary_basis_limbs[0].maximum_value = limb_max[0];
87 x_fq.binary_basis_limbs[1].maximum_value = limb_max[1];
88 x_fq.binary_basis_limbs[2].maximum_value = limb_max[2];
89 x_fq.binary_basis_limbs[3].maximum_value = limb_max[3];
90 y_fq.binary_basis_limbs[0].maximum_value = limb_max[4];
91 y_fq.binary_basis_limbs[1].maximum_value = limb_max[5];
92 y_fq.binary_basis_limbs[2].maximum_value = limb_max[6];
93 y_fq.binary_basis_limbs[3].maximum_value = limb_max[7];
94
95 const auto output = element(x_fq, y_fq);
96 return output;
97}
98
99template <typename C, class Fq, class Fr, class G>
100element<C, Fq, Fr, G>::four_bit_table_plookup::four_bit_table_plookup(const element& input)
101{
102 element d2 = input.dbl();
103
104 element_table[8] = input;
105 for (size_t i = 9; i < 16; ++i) {
106 element_table[i] = element_table[i - 1] + d2;
107 }
108 for (size_t i = 0; i < 8; ++i) {
109 element_table[i] = (-element_table[15 - i]);
110 }
111
112 coordinates = create_group_element_rom_tables<16>(element_table, limb_max);
113}
114
115template <typename C, class Fq, class Fr, class G>
116element<C, Fq, Fr, G> element<C, Fq, Fr, G>::four_bit_table_plookup::operator[](const field_t<C>& index) const
117{
118 return read_group_element_rom_tables<16>(coordinates, index, limb_max);
119}
120
121template <class C, class Fq, class Fr, class G>
122element<C, Fq, Fr, G> element<C, Fq, Fr, G>::eight_bit_fixed_base_table::operator[](const field_t<C>& index) const
123{
124 const auto get_plookup_tags = [this]() {
125 switch (curve_type) {
126 case CurveType::SECP256K1: {
127 return std::array<MultiTableId, 5>{
128 use_endomorphism ? MultiTableId::SECP256K1_XLO_ENDO : MultiTableId::SECP256K1_XLO,
129 use_endomorphism ? MultiTableId::SECP256K1_XHI_ENDO : MultiTableId::SECP256K1_XHI,
130 MultiTableId::SECP256K1_YLO,
131 MultiTableId::SECP256K1_YHI,
132 use_endomorphism ? MultiTableId::SECP256K1_XYPRIME_ENDO : MultiTableId::SECP256K1_XYPRIME,
133 };
134 }
135 case CurveType::BN254: {
136 return std::array<MultiTableId, 5>{
137 use_endomorphism ? MultiTableId::BN254_XLO_ENDO : MultiTableId::BN254_XLO,
138 use_endomorphism ? MultiTableId::BN254_XHI_ENDO : MultiTableId::BN254_XHI,
139 MultiTableId::BN254_YLO,
140 MultiTableId::BN254_YHI,
141 use_endomorphism ? MultiTableId::BN254_XYPRIME_ENDO : MultiTableId::BN254_XYPRIME,
142 };
143 }
144 default: {
145 return std::array<MultiTableId, 5>{
146 use_endomorphism ? MultiTableId::BN254_XLO_ENDO : MultiTableId::BN254_XLO,
147 use_endomorphism ? MultiTableId::BN254_XHI_ENDO : MultiTableId::BN254_XHI,
148 MultiTableId::BN254_YLO,
149 MultiTableId::BN254_YHI,
150 use_endomorphism ? MultiTableId::BN254_XYPRIME_ENDO : MultiTableId::BN254_XYPRIME,
151 };
152 }
153 }
154 };
155
156 const auto tags = get_plookup_tags();
157
158 const auto xlo = plookup_read<C>::read_pair_from_table(tags[0], index);
159 const auto xhi = plookup_read<C>::read_pair_from_table(tags[1], index);
160 const auto ylo = plookup_read<C>::read_pair_from_table(tags[2], index);
161 const auto yhi = plookup_read<C>::read_pair_from_table(tags[3], index);
162 const auto xyprime = plookup_read<C>::read_pair_from_table(tags[4], index);
163
164 // All the elements are precomputed constants so they are completely reduced, so the default maximum limb values are
165 // appropriate
166 Fq x = Fq::unsafe_construct_from_limbs(xlo.first, xlo.second, xhi.first, xhi.second, xyprime.first);
167 Fq y = Fq::unsafe_construct_from_limbs(ylo.first, ylo.second, yhi.first, yhi.second, xyprime.second);
168
169 if (use_endomorphism) {
170 y = -y;
171 }
172
173 return element(x, y);
174}
175
176template <typename C, class Fq, class Fr, class G>
181
185template <typename C, class Fq, class Fr, class G>
186template <size_t length>
187element<C, Fq, Fr, G>::lookup_table_plookup<length>::lookup_table_plookup(const std::array<element, length>& inputs)
188{
189 if constexpr (length == 2) {
190 auto [A0, A1] = inputs[1].checked_unconditional_add_sub(inputs[0]);
191 element_table[0] = A0;
192 element_table[1] = A1;
193 } else if constexpr (length == 3) {
194 auto [R0, R1] = inputs[1].checked_unconditional_add_sub(inputs[0]); // B ± A
195
196 auto [T0, T1] = inputs[2].checked_unconditional_add_sub(R0); // C ± (B + A)
197 auto [T2, T3] = inputs[2].checked_unconditional_add_sub(R1); // C ± (B - A)
198
199 element_table[0] = T0;
200 element_table[1] = T2;
201 element_table[2] = T3;
202 element_table[3] = T1;
203 } else if constexpr (length == 4) {
204 auto [T0, T1] = inputs[1].checked_unconditional_add_sub(inputs[0]); // B ± A
205 auto [T2, T3] = inputs[3].checked_unconditional_add_sub(inputs[2]); // D ± C
206
207 auto [F0, F3] = T2.checked_unconditional_add_sub(T0); // (D + C) ± (B + A)
208 auto [F1, F2] = T2.checked_unconditional_add_sub(T1); // (D + C) ± (B - A)
209 auto [F4, F7] = T3.checked_unconditional_add_sub(T0); // (D - C) ± (B + A)
210 auto [F5, F6] = T3.checked_unconditional_add_sub(T1); // (D - C) ± (B - A)
211
212 element_table[0] = F0;
213 element_table[1] = F1;
214 element_table[2] = F2;
215 element_table[3] = F3;
216 element_table[4] = F4;
217 element_table[5] = F5;
218 element_table[6] = F6;
219 element_table[7] = F7;
220 } else if constexpr (length == 5) {
221 auto [A0, A1] = inputs[1].checked_unconditional_add_sub(inputs[0]); // B ± A
222 auto [T2, T3] = inputs[3].checked_unconditional_add_sub(inputs[2]); // D ± C
223
224 auto [E0, E3] = inputs[4].checked_unconditional_add_sub(T2); // E ± (D + C)
225 auto [E1, E2] = inputs[4].checked_unconditional_add_sub(T3); // E ± (D - C)
226
227 auto [F0, F3] = E0.checked_unconditional_add_sub(A0);
228 auto [F1, F2] = E0.checked_unconditional_add_sub(A1);
229 auto [F4, F7] = E1.checked_unconditional_add_sub(A0);
230 auto [F5, F6] = E1.checked_unconditional_add_sub(A1);
231 auto [F8, F11] = E2.checked_unconditional_add_sub(A0);
232 auto [F9, F10] = E2.checked_unconditional_add_sub(A1);
233 auto [F12, F15] = E3.checked_unconditional_add_sub(A0);
234 auto [F13, F14] = E3.checked_unconditional_add_sub(A1);
235
236 element_table[0] = F0;
237 element_table[1] = F1;
238 element_table[2] = F2;
239 element_table[3] = F3;
240 element_table[4] = F4;
241 element_table[5] = F5;
242 element_table[6] = F6;
243 element_table[7] = F7;
244 element_table[8] = F8;
245 element_table[9] = F9;
246 element_table[10] = F10;
247 element_table[11] = F11;
248 element_table[12] = F12;
249 element_table[13] = F13;
250 element_table[14] = F14;
251 element_table[15] = F15;
252 } else if constexpr (length == 6) {
253 // 44 adds! Only use this if it saves us adding another table to a multi-scalar-multiplication
254
255 auto [A0, A1] = inputs[1].checked_unconditional_add_sub(inputs[0]);
256 auto [E0, E1] = inputs[4].checked_unconditional_add_sub(inputs[3]);
257 auto [C0, C3] = inputs[2].checked_unconditional_add_sub(A0);
258 auto [C1, C2] = inputs[2].checked_unconditional_add_sub(A1);
259
260 auto [F0, F3] = inputs[5].checked_unconditional_add_sub(E0);
261 auto [F1, F2] = inputs[5].checked_unconditional_add_sub(E1);
262
263 auto [R0, R7] = F0.checked_unconditional_add_sub(C0);
264 auto [R1, R6] = F0.checked_unconditional_add_sub(C1);
265 auto [R2, R5] = F0.checked_unconditional_add_sub(C2);
266 auto [R3, R4] = F0.checked_unconditional_add_sub(C3);
267
268 auto [S0, S7] = F1.checked_unconditional_add_sub(C0);
269 auto [S1, S6] = F1.checked_unconditional_add_sub(C1);
270 auto [S2, S5] = F1.checked_unconditional_add_sub(C2);
271 auto [S3, S4] = F1.checked_unconditional_add_sub(C3);
272
273 auto [U0, U7] = F2.checked_unconditional_add_sub(C0);
274 auto [U1, U6] = F2.checked_unconditional_add_sub(C1);
275 auto [U2, U5] = F2.checked_unconditional_add_sub(C2);
276 auto [U3, U4] = F2.checked_unconditional_add_sub(C3);
277
278 auto [W0, W7] = F3.checked_unconditional_add_sub(C0);
279 auto [W1, W6] = F3.checked_unconditional_add_sub(C1);
280 auto [W2, W5] = F3.checked_unconditional_add_sub(C2);
281 auto [W3, W4] = F3.checked_unconditional_add_sub(C3);
282
283 element_table[0] = R0;
284 element_table[1] = R1;
285 element_table[2] = R2;
286 element_table[3] = R3;
287 element_table[4] = R4;
288 element_table[5] = R5;
289 element_table[6] = R6;
290 element_table[7] = R7;
291
292 element_table[8] = S0;
293 element_table[9] = S1;
294 element_table[10] = S2;
295 element_table[11] = S3;
296 element_table[12] = S4;
297 element_table[13] = S5;
298 element_table[14] = S6;
299 element_table[15] = S7;
300
301 element_table[16] = U0;
302 element_table[17] = U1;
303 element_table[18] = U2;
304 element_table[19] = U3;
305 element_table[20] = U4;
306 element_table[21] = U5;
307 element_table[22] = U6;
308 element_table[23] = U7;
309
310 element_table[24] = W0;
311 element_table[25] = W1;
312 element_table[26] = W2;
313 element_table[27] = W3;
314 element_table[28] = W4;
315 element_table[29] = W5;
316 element_table[30] = W6;
317 element_table[31] = W7;
318 } else if constexpr (length == 7) {
319 // 82 adds! This one is not worth using...
320
321 element A0 = inputs[1] + inputs[0]; // B + A
322 element A1 = inputs[1] - inputs[0]; // B - A
323
324 element D0 = inputs[3] + inputs[2]; // D + C
325 element D1 = inputs[3] - inputs[2]; // D - C
326
327 element E0 = D0 + A0; // D + C + B + A
328 element E1 = D0 + A1; // D + C + B - A
329 element E2 = D0 - A1; // D + C - B + A
330 element E3 = D0 - A0; // D + C - B - A
331 element E4 = D1 + A0; // D - C + B + A
332 element E5 = D1 + A1; // D - C + B - A
333 element E6 = D1 - A1; // D - C - B + A
334 element E7 = D1 - A0; // D - C - B - A
335
336 element F0 = inputs[5] + inputs[4]; // F + E
337 element F1 = inputs[5] - inputs[4]; // F - E
338
339 element G0 = inputs[6] + F0; // G + F + E
340 element G1 = inputs[6] + F1; // G + F - E
341 element G2 = inputs[6] - F1; // G - F + E
342 element G3 = inputs[6] - F0; // G - F - E
343
344 element_table[0] = G0 + E0;
345 element_table[1] = G0 + E1;
346 element_table[2] = G0 + E2;
347 element_table[3] = G0 + E3;
348 element_table[4] = G0 + E4;
349 element_table[5] = G0 + E5;
350 element_table[6] = G0 + E6;
351 element_table[7] = G0 + E7;
352 element_table[8] = G0 - E7;
353 element_table[9] = G0 - E6;
354 element_table[10] = G0 - E5;
355 element_table[11] = G0 - E4;
356 element_table[12] = G0 - E3;
357 element_table[13] = G0 - E2;
358 element_table[14] = G0 - E1;
359 element_table[15] = G0 - E0;
360 element_table[16] = G1 + E0;
361 element_table[17] = G1 + E1;
362 element_table[18] = G1 + E2;
363 element_table[19] = G1 + E3;
364 element_table[20] = G1 + E4;
365 element_table[21] = G1 + E5;
366 element_table[22] = G1 + E6;
367 element_table[23] = G1 + E7;
368 element_table[24] = G1 - E7;
369 element_table[25] = G1 - E6;
370 element_table[26] = G1 - E5;
371 element_table[27] = G1 - E4;
372 element_table[28] = G1 - E3;
373 element_table[29] = G1 - E2;
374 element_table[30] = G1 - E1;
375 element_table[31] = G1 - E0;
376 element_table[32] = G2 + E0;
377 element_table[33] = G2 + E1;
378 element_table[34] = G2 + E2;
379 element_table[35] = G2 + E3;
380 element_table[36] = G2 + E4;
381 element_table[37] = G2 + E5;
382 element_table[38] = G2 + E6;
383 element_table[39] = G2 + E7;
384 element_table[40] = G2 - E7;
385 element_table[41] = G2 - E6;
386 element_table[42] = G2 - E5;
387 element_table[43] = G2 - E4;
388 element_table[44] = G2 - E3;
389 element_table[45] = G2 - E2;
390 element_table[46] = G2 - E1;
391 element_table[47] = G2 - E0;
392 element_table[48] = G3 + E0;
393 element_table[49] = G3 + E1;
394 element_table[50] = G3 + E2;
395 element_table[51] = G3 + E3;
396 element_table[52] = G3 + E4;
397 element_table[53] = G3 + E5;
398 element_table[54] = G3 + E6;
399 element_table[55] = G3 + E7;
400 element_table[56] = G3 - E7;
401 element_table[57] = G3 - E6;
402 element_table[58] = G3 - E5;
403 element_table[59] = G3 - E4;
404 element_table[60] = G3 - E3;
405 element_table[61] = G3 - E2;
406 element_table[62] = G3 - E1;
407 element_table[63] = G3 - E0;
408 }
409 for (size_t i = 0; i < table_size / 2; ++i) {
410 element_table[i + table_size / 2] = (-element_table[table_size / 2 - 1 - i]);
411 }
412 coordinates = create_group_element_rom_tables<table_size>(element_table, limb_max);
413}
414
415template <typename C, class Fq, class Fr, class G>
416template <size_t length>
417element<C, Fq, Fr, G> element<C, Fq, Fr, G>::lookup_table_plookup<length>::get(
418 const std::array<bool_ct, length>& bits) const
419{
420 std::vector<field_t<C>> accumulators;
421 for (size_t i = 0; i < length; ++i) {
422 accumulators.emplace_back(field_t<C>(bits[i]) * (1ULL << i));
423 }
424 field_t<C> index = field_t<C>::accumulate(accumulators);
425 return read_group_element_rom_tables<table_size>(coordinates, index, limb_max);
426}
427
431template <typename C, class Fq, class Fr, class G>
432template <size_t length>
433element<C, Fq, Fr, G>::lookup_table_base<length>::lookup_table_base(const std::array<element, length>& inputs)
434{
435 static_assert(length <= 4 && length >= 2);
436 if constexpr (length == 2) {
437 twin0 = inputs[1] + inputs[0];
438 twin1 = inputs[1] - inputs[0];
439 element_table[0] = twin0;
440 element_table[1] = twin1;
441 } else if constexpr (length == 3) {
442 element T0 = inputs[1] + inputs[0];
443 element T1 = inputs[1] - inputs[0];
444 element_table[0] = inputs[2] + T0; // C + B + A
445 element_table[1] = inputs[2] + T1; // C + B - A
446 element_table[2] = inputs[2] - T1; // C - B + A
447 element_table[3] = inputs[2] - T0; // C - B - A
448
449 x_b0_table = field_t<C>::preprocess_two_bit_table(element_table[0].x.binary_basis_limbs[0].element,
450 element_table[1].x.binary_basis_limbs[0].element,
451 element_table[2].x.binary_basis_limbs[0].element,
452 element_table[3].x.binary_basis_limbs[0].element);
453 x_b1_table = field_t<C>::preprocess_two_bit_table(element_table[0].x.binary_basis_limbs[1].element,
454 element_table[1].x.binary_basis_limbs[1].element,
455 element_table[2].x.binary_basis_limbs[1].element,
456 element_table[3].x.binary_basis_limbs[1].element);
457 x_b2_table = field_t<C>::preprocess_two_bit_table(element_table[0].x.binary_basis_limbs[2].element,
458 element_table[1].x.binary_basis_limbs[2].element,
459 element_table[2].x.binary_basis_limbs[2].element,
460 element_table[3].x.binary_basis_limbs[2].element);
461 x_b3_table = field_t<C>::preprocess_two_bit_table(element_table[0].x.binary_basis_limbs[3].element,
462 element_table[1].x.binary_basis_limbs[3].element,
463 element_table[2].x.binary_basis_limbs[3].element,
464 element_table[3].x.binary_basis_limbs[3].element);
465
466 y_b0_table = field_t<C>::preprocess_two_bit_table(element_table[0].y.binary_basis_limbs[0].element,
467 element_table[1].y.binary_basis_limbs[0].element,
468 element_table[2].y.binary_basis_limbs[0].element,
469 element_table[3].y.binary_basis_limbs[0].element);
470 y_b1_table = field_t<C>::preprocess_two_bit_table(element_table[0].y.binary_basis_limbs[1].element,
471 element_table[1].y.binary_basis_limbs[1].element,
472 element_table[2].y.binary_basis_limbs[1].element,
473 element_table[3].y.binary_basis_limbs[1].element);
474 y_b2_table = field_t<C>::preprocess_two_bit_table(element_table[0].y.binary_basis_limbs[2].element,
475 element_table[1].y.binary_basis_limbs[2].element,
476 element_table[2].y.binary_basis_limbs[2].element,
477 element_table[3].y.binary_basis_limbs[2].element);
478 y_b3_table = field_t<C>::preprocess_two_bit_table(element_table[0].y.binary_basis_limbs[3].element,
479 element_table[1].y.binary_basis_limbs[3].element,
480 element_table[2].y.binary_basis_limbs[3].element,
481 element_table[3].y.binary_basis_limbs[3].element);
482 } else if constexpr (length == 4) {
483 element T0 = inputs[1] + inputs[0];
484 element T1 = inputs[1] - inputs[0];
485 element T2 = inputs[3] + inputs[2];
486 element T3 = inputs[3] - inputs[2];
487
488 element_table[0] = T2 + T0; // D + C + B + A
489 element_table[1] = T2 + T1; // D + C + B - A
490 element_table[2] = T2 - T1; // D + C - B + A
491 element_table[3] = T2 - T0; // D + C - B - A
492 element_table[4] = T3 + T0; // D - C + B + A
493 element_table[5] = T3 + T1; // D - C + B - A
494 element_table[6] = T3 - T1; // D - C - B + A
495 element_table[7] = T3 - T0; // D - C - B - A
496
497 x_b0_table = field_t<C>::preprocess_three_bit_table(element_table[0].x.binary_basis_limbs[0].element,
498 element_table[1].x.binary_basis_limbs[0].element,
499 element_table[2].x.binary_basis_limbs[0].element,
500 element_table[3].x.binary_basis_limbs[0].element,
501 element_table[4].x.binary_basis_limbs[0].element,
502 element_table[5].x.binary_basis_limbs[0].element,
503 element_table[6].x.binary_basis_limbs[0].element,
504 element_table[7].x.binary_basis_limbs[0].element);
505 x_b1_table = field_t<C>::preprocess_three_bit_table(element_table[0].x.binary_basis_limbs[1].element,
506 element_table[1].x.binary_basis_limbs[1].element,
507 element_table[2].x.binary_basis_limbs[1].element,
508 element_table[3].x.binary_basis_limbs[1].element,
509 element_table[4].x.binary_basis_limbs[1].element,
510 element_table[5].x.binary_basis_limbs[1].element,
511 element_table[6].x.binary_basis_limbs[1].element,
512 element_table[7].x.binary_basis_limbs[1].element);
513 x_b2_table = field_t<C>::preprocess_three_bit_table(element_table[0].x.binary_basis_limbs[2].element,
514 element_table[1].x.binary_basis_limbs[2].element,
515 element_table[2].x.binary_basis_limbs[2].element,
516 element_table[3].x.binary_basis_limbs[2].element,
517 element_table[4].x.binary_basis_limbs[2].element,
518 element_table[5].x.binary_basis_limbs[2].element,
519 element_table[6].x.binary_basis_limbs[2].element,
520 element_table[7].x.binary_basis_limbs[2].element);
521 x_b3_table = field_t<C>::preprocess_three_bit_table(element_table[0].x.binary_basis_limbs[3].element,
522 element_table[1].x.binary_basis_limbs[3].element,
523 element_table[2].x.binary_basis_limbs[3].element,
524 element_table[3].x.binary_basis_limbs[3].element,
525 element_table[4].x.binary_basis_limbs[3].element,
526 element_table[5].x.binary_basis_limbs[3].element,
527 element_table[6].x.binary_basis_limbs[3].element,
528 element_table[7].x.binary_basis_limbs[3].element);
529
530 y_b0_table = field_t<C>::preprocess_three_bit_table(element_table[0].y.binary_basis_limbs[0].element,
531 element_table[1].y.binary_basis_limbs[0].element,
532 element_table[2].y.binary_basis_limbs[0].element,
533 element_table[3].y.binary_basis_limbs[0].element,
534 element_table[4].y.binary_basis_limbs[0].element,
535 element_table[5].y.binary_basis_limbs[0].element,
536 element_table[6].y.binary_basis_limbs[0].element,
537 element_table[7].y.binary_basis_limbs[0].element);
538 y_b1_table = field_t<C>::preprocess_three_bit_table(element_table[0].y.binary_basis_limbs[1].element,
539 element_table[1].y.binary_basis_limbs[1].element,
540 element_table[2].y.binary_basis_limbs[1].element,
541 element_table[3].y.binary_basis_limbs[1].element,
542 element_table[4].y.binary_basis_limbs[1].element,
543 element_table[5].y.binary_basis_limbs[1].element,
544 element_table[6].y.binary_basis_limbs[1].element,
545 element_table[7].y.binary_basis_limbs[1].element);
546 y_b2_table = field_t<C>::preprocess_three_bit_table(element_table[0].y.binary_basis_limbs[2].element,
547 element_table[1].y.binary_basis_limbs[2].element,
548 element_table[2].y.binary_basis_limbs[2].element,
549 element_table[3].y.binary_basis_limbs[2].element,
550 element_table[4].y.binary_basis_limbs[2].element,
551 element_table[5].y.binary_basis_limbs[2].element,
552 element_table[6].y.binary_basis_limbs[2].element,
553 element_table[7].y.binary_basis_limbs[2].element);
554 y_b3_table = field_t<C>::preprocess_three_bit_table(element_table[0].y.binary_basis_limbs[3].element,
555 element_table[1].y.binary_basis_limbs[3].element,
556 element_table[2].y.binary_basis_limbs[3].element,
557 element_table[3].y.binary_basis_limbs[3].element,
558 element_table[4].y.binary_basis_limbs[3].element,
559 element_table[5].y.binary_basis_limbs[3].element,
560 element_table[6].y.binary_basis_limbs[3].element,
561 element_table[7].y.binary_basis_limbs[3].element);
562 }
563}
564
565template <typename C, class Fq, class Fr, class G>
566template <size_t length>
567element<C, Fq, Fr, G> element<C, Fq, Fr, G>::lookup_table_base<length>::get(
568 const std::array<bool_ct, length>& bits) const
569{
570 static_assert(length <= 4 && length >= 2);
571
572 if constexpr (length == 2) {
573 bool_ct table_selector = bits[0] ^ bits[1];
574 bool_ct sign_selector = bits[1];
575 Fq to_add_x = twin0.x.conditional_select(twin1.x, table_selector);
576 Fq to_add_y = twin0.y.conditional_select(twin1.y, table_selector);
577 element to_add(to_add_x, to_add_y.conditional_negate(sign_selector));
578 return to_add;
579 } else if constexpr (length == 3) {
580 bool_ct t0 = bits[2] ^ bits[0];
581 bool_ct t1 = bits[2] ^ bits[1];
582
583 field_t<C> x_b0 = field_t<C>::select_from_two_bit_table(x_b0_table, t1, t0);
584 field_t<C> x_b1 = field_t<C>::select_from_two_bit_table(x_b1_table, t1, t0);
585 field_t<C> x_b2 = field_t<C>::select_from_two_bit_table(x_b2_table, t1, t0);
586 field_t<C> x_b3 = field_t<C>::select_from_two_bit_table(x_b3_table, t1, t0);
587
588 field_t<C> y_b0 = field_t<C>::select_from_two_bit_table(y_b0_table, t1, t0);
589 field_t<C> y_b1 = field_t<C>::select_from_two_bit_table(y_b1_table, t1, t0);
590 field_t<C> y_b2 = field_t<C>::select_from_two_bit_table(y_b2_table, t1, t0);
591 field_t<C> y_b3 = field_t<C>::select_from_two_bit_table(y_b3_table, t1, t0);
592
593 Fq to_add_x;
594 Fq to_add_y;
595 to_add_x.binary_basis_limbs[0] = typename Fq::Limb(x_b0, Fq::DEFAULT_MAXIMUM_LIMB);
596 to_add_x.binary_basis_limbs[1] = typename Fq::Limb(x_b1, Fq::DEFAULT_MAXIMUM_LIMB);
597 to_add_x.binary_basis_limbs[2] = typename Fq::Limb(x_b2, Fq::DEFAULT_MAXIMUM_LIMB);
598 to_add_x.binary_basis_limbs[3] = typename Fq::Limb(x_b3, Fq::DEFAULT_MAXIMUM_MOST_SIGNIFICANT_LIMB);
599 to_add_x.prime_basis_limb = to_add_x.binary_basis_limbs[0].element.add_two(
600 to_add_x.binary_basis_limbs[1].element * Fq::shift_1, to_add_x.binary_basis_limbs[2].element * Fq::shift_2);
601 to_add_x.prime_basis_limb += to_add_x.binary_basis_limbs[3].element * Fq::shift_3;
602
603 to_add_y.binary_basis_limbs[0] = typename Fq::Limb(y_b0, Fq::DEFAULT_MAXIMUM_LIMB);
604 to_add_y.binary_basis_limbs[1] = typename Fq::Limb(y_b1, Fq::DEFAULT_MAXIMUM_LIMB);
605 to_add_y.binary_basis_limbs[2] = typename Fq::Limb(y_b2, Fq::DEFAULT_MAXIMUM_LIMB);
606 to_add_y.binary_basis_limbs[3] = typename Fq::Limb(y_b3, Fq::DEFAULT_MAXIMUM_MOST_SIGNIFICANT_LIMB);
607 to_add_y.prime_basis_limb = to_add_y.binary_basis_limbs[0].element.add_two(
608 to_add_y.binary_basis_limbs[1].element * Fq::shift_1, to_add_y.binary_basis_limbs[2].element * Fq::shift_2);
609 to_add_y.prime_basis_limb += to_add_y.binary_basis_limbs[3].element * Fq::shift_3;
610 element to_add(to_add_x, to_add_y.conditional_negate(bits[2]));
611
612 return to_add;
613 } else if constexpr (length == 4) {
614 bool_ct t0 = bits[3] ^ bits[0];
615 bool_ct t1 = bits[3] ^ bits[1];
616 bool_ct t2 = bits[3] ^ bits[2];
617
618 field_t<C> x_b0 = field_t<C>::select_from_three_bit_table(x_b0_table, t2, t1, t0);
619 field_t<C> x_b1 = field_t<C>::select_from_three_bit_table(x_b1_table, t2, t1, t0);
620 field_t<C> x_b2 = field_t<C>::select_from_three_bit_table(x_b2_table, t2, t1, t0);
621 field_t<C> x_b3 = field_t<C>::select_from_three_bit_table(x_b3_table, t2, t1, t0);
622
623 field_t<C> y_b0 = field_t<C>::select_from_three_bit_table(y_b0_table, t2, t1, t0);
624 field_t<C> y_b1 = field_t<C>::select_from_three_bit_table(y_b1_table, t2, t1, t0);
625 field_t<C> y_b2 = field_t<C>::select_from_three_bit_table(y_b2_table, t2, t1, t0);
626 field_t<C> y_b3 = field_t<C>::select_from_three_bit_table(y_b3_table, t2, t1, t0);
627
628 Fq to_add_x;
629 Fq to_add_y;
630 to_add_x.binary_basis_limbs[0] = typename Fq::Limb(x_b0, Fq::DEFAULT_MAXIMUM_LIMB);
631 to_add_x.binary_basis_limbs[1] = typename Fq::Limb(x_b1, Fq::DEFAULT_MAXIMUM_LIMB);
632 to_add_x.binary_basis_limbs[2] = typename Fq::Limb(x_b2, Fq::DEFAULT_MAXIMUM_LIMB);
633 to_add_x.binary_basis_limbs[3] = typename Fq::Limb(x_b3, Fq::DEFAULT_MAXIMUM_MOST_SIGNIFICANT_LIMB);
634 to_add_x.prime_basis_limb = to_add_x.binary_basis_limbs[0].element.add_two(
635 to_add_x.binary_basis_limbs[1].element * Fq::shift_1, to_add_x.binary_basis_limbs[2].element * Fq::shift_2);
636 to_add_x.prime_basis_limb += to_add_x.binary_basis_limbs[3].element * Fq::shift_3;
637
638 to_add_y.binary_basis_limbs[0] = typename Fq::Limb(y_b0, Fq::DEFAULT_MAXIMUM_LIMB);
639 to_add_y.binary_basis_limbs[1] = typename Fq::Limb(y_b1, Fq::DEFAULT_MAXIMUM_LIMB);
640 to_add_y.binary_basis_limbs[2] = typename Fq::Limb(y_b2, Fq::DEFAULT_MAXIMUM_LIMB);
641 to_add_y.binary_basis_limbs[3] = typename Fq::Limb(y_b3, Fq::DEFAULT_MAXIMUM_MOST_SIGNIFICANT_LIMB);
642 to_add_y.prime_basis_limb = to_add_y.binary_basis_limbs[0].element.add_two(
643 to_add_y.binary_basis_limbs[1].element * Fq::shift_1, to_add_y.binary_basis_limbs[2].element * Fq::shift_2);
644 to_add_y.prime_basis_limb += to_add_y.binary_basis_limbs[3].element * Fq::shift_3;
645
646 element to_add(to_add_x, to_add_y.conditional_negate(bits[3]));
647
648 return to_add;
649 }
650 return element::one(bits[0].get_context());
651}
652} // namespace bb::stdlib::element_default
bb::stdlib::bool_t
Implements boolean logic in-circuit.
Definition bool.hpp:59
bb::stdlib::element_default::element
Definition biggroup.hpp:24
bb::stdlib::element_default::element::checked_unconditional_add_sub
std::array< element, 2 > checked_unconditional_add_sub(const element &) const
Compute (*this) + other AND (*this) - other as a size-2 array.
Definition biggroup_impl.hpp:254
bb::stdlib::element_default::element::dbl
element dbl() const
Definition biggroup_impl.hpp:274
bb::stdlib::field_t
Definition field.hpp:45
bb::stdlib::field_t< Builder >::select_from_three_bit_table
static field_t select_from_three_bit_table(const std::array< field_t, 8 > &table, const bool_t< Builder > &t2, const bool_t< Builder > &t1, const bool_t< Builder > &t0)
Given a multilinear polynomial in 3 variables, which is represented by a table of monomial coefficien...
Definition field.cpp:1058
bb::stdlib::field_t< Builder >::accumulate
static field_t accumulate(const std::vector< field_t > &input)
Efficiently compute the sum of vector entries. Using big_add_gate we reduce the number of gates neede...
Definition field.cpp:1147
bb::stdlib::field_t< Builder >::preprocess_three_bit_table
static std::array< field_t, 8 > preprocess_three_bit_table(const field_t &T0, const field_t &T1, const field_t &T2, const field_t &T3, const field_t &T4, const field_t &T5, const field_t &T6, const field_t &T7)
Given a table T of size 8, outputs the monomial coefficients of the multilinear polynomial in t0,...
Definition field.cpp:1010
bb::stdlib::field_t< Builder >::select_from_two_bit_table
static field_t select_from_two_bit_table(const std::array< field_t, 4 > &table, const bool_t< Builder > &t1, const bool_t< Builder > &t0)
Given a multilinear polynomial in 2 variables, which is represented by a table of monomial coefficien...
Definition field.cpp:1036
bb::stdlib::field_t< Builder >::preprocess_two_bit_table
static std::array< field_t, 4 > preprocess_two_bit_table(const field_t &T0, const field_t &T1, const field_t &T2, const field_t &T3)
Given a table T of size 4, outputs the monomial coefficients of the multilinear polynomial in t0,...
Definition field.cpp:992
bb::stdlib::plookup_read::read_pair_from_table
static std::pair< field_pt, field_pt > read_pair_from_table(const plookup::MultiTableId id, const field_pt &key)
Definition plookup.cpp:70
bb::stdlib::twin_rom_table
Definition twin_rom_table.hpp:17
length
uint8_t const size_t length
Definition data_store.hpp:9
operator[]
FF const & operator[](size_t idx) const
Retruns the element in beta_products at place #idx.
Definition gate_separator.hpp:90
bb::stdlib::element_default
Definition biggroup.hpp:21
bb::stdlib::element
std::conditional_t< IsGoblinBigGroup< C, Fq, Fr, G >, element_goblin::goblin_element< C, goblin_field< C >, Fr, G >, element_default::element< C, Fq, Fr, G > > element
element wraps either element_default::element or element_goblin::goblin_element depending on parametr...
Definition biggroup.hpp:1055
bb::SECP256K1
@ SECP256K1
Definition types.hpp:10
bb::BN254
@ BN254
Definition types.hpp:10
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
G1
Curve::AffineElement G1
Definition pippenger.bench.cpp:29
types.hpp
twin_rom_table.hpp