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