Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
alu_trace.test.cpp
Go to the documentation of this file.
1#include <gmock/gmock.h>
2#include <gtest/gtest.h>
3
4#include <cstdint>
5#include <tuple>
6
7#include "barretenberg/numeric/uint128/uint128.hpp"
8#include "barretenberg/numeric/uint256/uint256.hpp"
9#include "barretenberg/vm2/common/memory_types.hpp"
10#include "barretenberg/vm2/constraining/flavor_settings.hpp"
11#include "barretenberg/vm2/constraining/full_row.hpp"
12#include "barretenberg/vm2/generated/columns.hpp"
13#include "barretenberg/vm2/simulation/events/alu_event.hpp"
14#include "barretenberg/vm2/simulation/events/field_gt_event.hpp"
15#include "barretenberg/vm2/simulation/events/range_check_event.hpp"
16#include "barretenberg/vm2/simulation/gadgets/alu.hpp"
17#include "barretenberg/vm2/simulation/gadgets/field_gt.hpp"
18#include "barretenberg/vm2/simulation/gadgets/gt.hpp"
19#include "barretenberg/vm2/simulation/gadgets/range_check.hpp"
20#include "barretenberg/vm2/simulation/testing/mock_field_gt.hpp"
21#include "barretenberg/vm2/simulation/testing/mock_gt.hpp"
22#include "barretenberg/vm2/simulation/testing/mock_range_check.hpp"
23#include "barretenberg/vm2/testing/macros.hpp"
24#include "barretenberg/vm2/tracegen/alu_trace.hpp"
25#include "barretenberg/vm2/tracegen/lib/instruction_spec.hpp"
26#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
27
28namespace bb::avm2::tracegen {
29namespace {
30
31using simulation::AluOperation;
32using testing::ElementsAre;
33
34using R = TestTraceContainer::Row;
35
36// Generic structure for three-operand opcodes
37using ThreeOperandTestParams = std::tuple<MemoryValue, MemoryValue, MemoryValue>;
38
39const std::vector<std::tuple<MemoryValue, MemoryValue>> TEST_VALUES_IN = {
40 {
41 MemoryValue::from_tag(MemoryTag::U1, 1),
42 MemoryValue::from_tag(MemoryTag::U1, 0),
43 },
44 {
45 MemoryValue::from_tag(MemoryTag::U1, 1),
46 MemoryValue::from_tag(MemoryTag::U1, 1),
47 },
48 {
49 MemoryValue::from_tag(MemoryTag::U8, 200),
50 MemoryValue::from_tag(MemoryTag::U8, 50),
51 },
52 {
53 MemoryValue::from_tag(MemoryTag::U8, 200),
54 MemoryValue::from_tag(MemoryTag::U8, 255),
55 },
56 {
57 MemoryValue::from_tag(MemoryTag::U16, 30),
58 MemoryValue::from_tag(MemoryTag::U16, 65500),
59 },
60 {
61 MemoryValue::from_tag(MemoryTag::U16, 65501),
62 MemoryValue::from_tag(MemoryTag::U16, 65500),
63 },
64 {
65 MemoryValue::from_tag(MemoryTag::U32, (uint256_t(1) << 32) - 10),
66 MemoryValue::from_tag(MemoryTag::U32, 5),
67 },
68 {
69 MemoryValue::from_tag(MemoryTag::U32, (uint256_t(1) << 32) - 10),
70 MemoryValue::from_tag(MemoryTag::U32, (uint256_t(1) << 32) - 5),
71 },
72 {
73 MemoryValue::from_tag(MemoryTag::U64, (uint256_t(1) << 64) - 10),
74 MemoryValue::from_tag(MemoryTag::U64, 5),
75 },
76 {
77 MemoryValue::from_tag(MemoryTag::U64, (uint256_t(1) << 64) - 10),
78 MemoryValue::from_tag(MemoryTag::U64, (uint256_t(1) << 64) - 5),
79 },
80 {
81 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 10),
82 MemoryValue::from_tag(MemoryTag::U128, 5),
83 },
84 {
85 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 10),
86 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 5),
87 },
88 {
89 MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 4),
90 MemoryValue::from_tag(MemoryTag::FF, 2),
91 },
92};
93
94std::vector<ThreeOperandTestParams> zip_helper(const std::vector<MemoryValue>& out)
95{
96 std::vector<ThreeOperandTestParams> res;
97 uint32_t i = 0;
98 for (const auto c : out) {
99 ThreeOperandTestParams params = tuple_cat(TEST_VALUES_IN.at(i), std::make_tuple(c));
100 res.push_back(params);
101 i++;
102 }
103 return res;
104}
105
106std::vector<MemoryValue> split_helper(const std::vector<std::tuple<MemoryValue, MemoryValue>>& in)
107{
108 std::vector<MemoryValue> res;
109 res.reserve(in.size());
110 for (const auto& c : in) {
111 res.push_back(std::get<0>(c));
112 }
113 return res;
114}
115
116class AluTraceGenerationTest : public ::testing::Test {
117 public:
118 TestTraceContainer trace;
119 AluTraceBuilder builder;
120};
121
122// ADD TESTS
123
124const std::vector<MemoryValue> TEST_VALUES_ADD_OUT = {
125 MemoryValue::from_tag(MemoryTag::U1, 1),
126 MemoryValue::from_tag(MemoryTag::U1, 0),
127 MemoryValue::from_tag(MemoryTag::U8, 250),
128 MemoryValue::from_tag(MemoryTag::U8, 199),
129 MemoryValue::from_tag(MemoryTag::U16, 65530),
130 MemoryValue::from_tag(MemoryTag::U16, 65465),
131 MemoryValue::from_tag(MemoryTag::U32, (uint256_t(1) << 32) - 5),
132 MemoryValue::from_tag(MemoryTag::U32, (uint256_t(1) << 32) - 15),
133 MemoryValue::from_tag(MemoryTag::U64, (uint256_t(1) << 64) - 5),
134 MemoryValue::from_tag(MemoryTag::U64, (uint256_t(1) << 64) - 15),
135 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 5),
136 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 15),
137 MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 2),
138};
139
140const std::vector<ThreeOperandTestParams> TEST_VALUES_ADD = zip_helper(TEST_VALUES_ADD_OUT);
141
142class AluAddTraceGenerationTest : public AluTraceGenerationTest,
143 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
144
145INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluAddTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_ADD));
146
147TEST_P(AluAddTraceGenerationTest, TraceGenerationAdd)
148{
149 auto [a, b, c] = GetParam();
150 auto tag = a.get_tag();
151 builder.process(
152 {
153 { .operation = AluOperation::ADD, .a = a, .b = b, .c = c },
154 },
155 trace);
156
157 EXPECT_THAT(trace.as_rows(),
158 ElementsAre(
159 // Only one row.
160 AllOf(ROW_FIELD_EQ(alu_sel_op_add, 1),
161 ROW_FIELD_EQ(alu_sel, 1),
162 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_ADD),
163 ROW_FIELD_EQ(alu_ia, a),
164 ROW_FIELD_EQ(alu_ib, b),
165 ROW_FIELD_EQ(alu_ic, c),
166 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
167 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
168 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
169 ROW_FIELD_EQ(alu_cf, a.as_ff() + b.as_ff() != c.as_ff() ? 1 : 0),
170 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
171 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
172 ROW_FIELD_EQ(alu_sel_is_ff, tag == MemoryTag::FF ? 1 : 0),
173 ROW_FIELD_EQ(alu_sel_is_u128, tag == MemoryTag::U128 ? 1 : 0),
174 ROW_FIELD_EQ(alu_sel_tag_err, 0),
175 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
176}
177
178TEST_F(AluTraceGenerationTest, TraceGenerationAddTagError)
179{
180 builder.process(
181 {
182 { .operation = AluOperation::ADD,
183 .a = MemoryValue::from<uint128_t>(1),
184 .b = MemoryValue::from<uint64_t>(2),
185 .c = MemoryValue::from<uint128_t>(3),
186 .error = true },
187 { .operation = AluOperation::ADD,
188 .a = MemoryValue::from<uint128_t>(1),
189 .b = MemoryValue::from<uint128_t>(2),
190 .c = MemoryValue::from<uint64_t>(3) },
191 },
192 trace);
193
194 EXPECT_THAT(
195 trace.as_rows(),
196 ElementsAre(
197 AllOf(ROW_FIELD_EQ(alu_sel_op_add, 1),
198 ROW_FIELD_EQ(alu_sel, 1),
199 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_ADD),
200 ROW_FIELD_EQ(alu_ia, 1),
201 ROW_FIELD_EQ(alu_ib, 2),
202 ROW_FIELD_EQ(alu_ic, 3),
203 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
204 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U64)),
205 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
206 ROW_FIELD_EQ(alu_cf, 0),
207 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
208 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U128)),
209 ROW_FIELD_EQ(alu_sel_is_ff, 0),
210 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
211 ROW_FIELD_EQ(alu_sel_tag_err, 1),
212 ROW_FIELD_EQ(alu_sel_err, 1),
213 ROW_FIELD_EQ(
214 alu_ab_tags_diff_inv,
215 (FF(static_cast<uint8_t>(MemoryTag::U128)) - FF(static_cast<uint8_t>(MemoryTag::U64))).invert())),
216 AllOf(ROW_FIELD_EQ(alu_sel_op_add, 1),
217 ROW_FIELD_EQ(alu_sel, 1),
218 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_ADD),
219 ROW_FIELD_EQ(alu_ia, 1),
220 ROW_FIELD_EQ(alu_ib, 2),
221 ROW_FIELD_EQ(alu_ic, 3),
222 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
223 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
224 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U64)),
225 ROW_FIELD_EQ(alu_cf, 0),
226 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
227 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U128)),
228 ROW_FIELD_EQ(alu_sel_is_ff, 0),
229 ROW_FIELD_EQ(alu_sel_tag_err,
230 0)) // Incorrect c tag does not create a tag error (see C_TAG_CHECK)
231 ));
232}
233
234// SUB TESTS
235
236const std::vector<MemoryValue> TEST_VALUES_SUB_OUT = {
237 MemoryValue::from_tag(MemoryTag::U1, 1),
238 MemoryValue::from_tag(MemoryTag::U1, 0),
239 MemoryValue::from_tag(MemoryTag::U8, 150),
240 MemoryValue::from_tag(MemoryTag::U8, 201),
241 MemoryValue::from_tag(MemoryTag::U16, 66),
242 MemoryValue::from_tag(MemoryTag::U16, 1),
243 MemoryValue::from_tag(MemoryTag::U32, (uint256_t(1) << 32) - 15),
244 MemoryValue::from_tag(MemoryTag::U32, (uint256_t(1) << 32) - 5),
245 MemoryValue::from_tag(MemoryTag::U64, (uint256_t(1) << 64) - 15),
246 MemoryValue::from_tag(MemoryTag::U64, (uint256_t(1) << 64) - 5),
247 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 15),
248 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 5),
249 MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 6),
250};
251
252const std::vector<ThreeOperandTestParams> TEST_VALUES_SUB = zip_helper(TEST_VALUES_SUB_OUT);
253
254class AluSubTraceGenerationTest : public AluTraceGenerationTest,
255 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
256
257INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluSubTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_SUB));
258
259TEST_P(AluSubTraceGenerationTest, TraceGenerationSub)
260{
261 auto [a, b, c] = GetParam();
262 auto tag = a.get_tag();
263 builder.process(
264 {
265 { .operation = AluOperation::SUB, .a = a, .b = b, .c = c },
266 },
267 trace);
268
269 EXPECT_THAT(trace.as_rows(),
270 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_sub, 1),
271 ROW_FIELD_EQ(alu_sel, 1),
272 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SUB),
273 ROW_FIELD_EQ(alu_ia, a),
274 ROW_FIELD_EQ(alu_ib, b),
275 ROW_FIELD_EQ(alu_ic, c),
276 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
277 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
278 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
279 ROW_FIELD_EQ(alu_cf, a.as_ff() - b.as_ff() != c.as_ff() ? 1 : 0),
280 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
281 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
282 ROW_FIELD_EQ(alu_sel_is_ff, tag == MemoryTag::FF ? 1 : 0),
283 ROW_FIELD_EQ(alu_sel_is_u128, tag == MemoryTag::U128 ? 1 : 0),
284 ROW_FIELD_EQ(alu_sel_tag_err, 0),
285 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
286}
287
288// MUL TESTS
289
290const std::vector<MemoryValue> TEST_VALUES_MUL_OUT = {
291 MemoryValue::from_tag(MemoryTag::U1, 0),
292 MemoryValue::from_tag(MemoryTag::U1, 1),
293 MemoryValue::from_tag(MemoryTag::U8, 16),
294 MemoryValue::from_tag(MemoryTag::U8, 8),
295 MemoryValue::from_tag(MemoryTag::U16, 64456),
296 MemoryValue::from_tag(MemoryTag::U16, 1260),
297 MemoryValue::from_tag(MemoryTag::U32, (uint256_t(1) << 32) - 50),
298 MemoryValue::from_tag(MemoryTag::U32, 50),
299 MemoryValue::from_tag(MemoryTag::U64, (uint256_t(1) << 64) - 50),
300 MemoryValue::from_tag(MemoryTag::U64, 50),
301 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 50),
302 MemoryValue::from_tag(MemoryTag::U128, 50),
303 MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 8),
304};
305
306const std::vector<ThreeOperandTestParams> TEST_VALUES_MUL = zip_helper(TEST_VALUES_MUL_OUT);
307
308class AluMulTraceGenerationTest : public AluTraceGenerationTest,
309 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
310
311INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluMulTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_MUL));
312
313TEST_P(AluMulTraceGenerationTest, TraceGenerationMul)
314{
315 auto [a, b, c] = GetParam();
316 auto tag = a.get_tag();
317 uint256_t a_int = static_cast<uint256_t>(a.as_ff());
318 uint256_t b_int = static_cast<uint256_t>(b.as_ff());
319 auto c_hi = tag == MemoryTag::FF ? 0 : (a_int * b_int) >> get_tag_bits(tag);
320 bool is_u128 = tag == MemoryTag::U128;
321 bool cf = false;
322 if (is_u128) {
323 // For u128s, we decompose a and b into 64 bit chunks:
324 auto a_hi = simulation::decompose_128(static_cast<uint128_t>(a.as_ff())).hi;
325 auto b_hi = simulation::decompose_128(static_cast<uint128_t>(b.as_ff())).hi;
326 // c_hi = old_c_hi - a_hi * b_hi % 2^64
327 auto hi_operand = static_cast<uint256_t>(a_hi) * static_cast<uint256_t>(b_hi);
328 cf = hi_operand != 0;
329 c_hi = (c_hi - hi_operand) % (uint256_t(1) << 64);
330 }
331 builder.process(
332 {
333 { .operation = AluOperation::MUL, .a = a, .b = b, .c = c },
334 },
335 trace);
336
337 EXPECT_THAT(
338 trace.as_rows(),
339 ElementsAre(AllOf(
340 ROW_FIELD_EQ(alu_sel_op_mul, 1),
341 ROW_FIELD_EQ(alu_sel, 1),
342 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_MUL),
343 ROW_FIELD_EQ(alu_ia, a),
344 ROW_FIELD_EQ(alu_ib, b),
345 ROW_FIELD_EQ(alu_ic, c),
346 ROW_FIELD_EQ(alu_c_hi, c_hi),
347 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
348 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
349 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
350 ROW_FIELD_EQ(alu_cf, cf),
351 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
352 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
353 ROW_FIELD_EQ(alu_constant_64, 64),
354 ROW_FIELD_EQ(alu_sel_is_u128, is_u128 ? 1 : 0),
355 ROW_FIELD_EQ(alu_sel_is_ff, tag == MemoryTag::FF ? 1 : 0),
356 ROW_FIELD_EQ(
357 alu_tag_u128_diff_inv,
358 is_u128 ? 0 : (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::U128))).invert()),
359 ROW_FIELD_EQ(alu_sel_mul_div_u128, is_u128 ? 1 : 0),
360 ROW_FIELD_EQ(alu_sel_tag_err, 0),
361 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
362}
363
364TEST_F(AluTraceGenerationTest, TraceGenerationMulU128)
365{
366 uint128_t u128_max = static_cast<uint128_t>(get_tag_max_value(MemoryTag::U128));
367 builder.process(
368 {
369 { .operation = AluOperation::MUL,
370 .a = MemoryValue::from<uint128_t>(2),
371 .b = MemoryValue::from<uint128_t>(3),
372 .c = MemoryValue::from<uint128_t>(6) },
373 { .operation = AluOperation::MUL,
374 .a = MemoryValue::from<uint128_t>(u128_max),
375 .b = MemoryValue::from<uint128_t>(u128_max - 2),
376 .c = MemoryValue::from<uint128_t>(3) },
377 },
378 trace);
379
380 EXPECT_THAT(trace.as_rows(),
381 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_mul, 1),
382 ROW_FIELD_EQ(alu_sel, 1),
383 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_MUL),
384 ROW_FIELD_EQ(alu_ia, 2),
385 ROW_FIELD_EQ(alu_a_hi, 0),
386 ROW_FIELD_EQ(alu_a_hi_bits, 64),
387 ROW_FIELD_EQ(alu_a_lo, 2),
388 ROW_FIELD_EQ(alu_a_lo_bits, 64),
389 ROW_FIELD_EQ(alu_ib, 3),
390 ROW_FIELD_EQ(alu_b_hi, 0),
391 ROW_FIELD_EQ(alu_b_lo, 3),
392 ROW_FIELD_EQ(alu_ic, 6),
393 ROW_FIELD_EQ(alu_c_hi, 0),
394 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
395 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
396 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
397 ROW_FIELD_EQ(alu_cf, 0),
398 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
399 ROW_FIELD_EQ(alu_max_value, u128_max),
400 ROW_FIELD_EQ(alu_constant_64, 64),
401 ROW_FIELD_EQ(alu_sel_is_u128, 1),
402 ROW_FIELD_EQ(alu_sel_is_ff, 0),
403 ROW_FIELD_EQ(alu_tag_u128_diff_inv, 0),
404 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
405 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
406 ROW_FIELD_EQ(alu_sel_tag_err, 0),
407 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
408 AllOf(ROW_FIELD_EQ(alu_sel_op_mul, 1),
409 ROW_FIELD_EQ(alu_sel, 1),
410 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_MUL),
411 ROW_FIELD_EQ(alu_ia, u128_max),
412 ROW_FIELD_EQ(alu_a_hi, (uint256_t(1) << 64) - 1),
413 ROW_FIELD_EQ(alu_a_hi_bits, 64),
414 ROW_FIELD_EQ(alu_a_lo, (uint256_t(1) << 64) - 1),
415 ROW_FIELD_EQ(alu_a_lo_bits, 64),
416 ROW_FIELD_EQ(alu_ib, u128_max - 2),
417 ROW_FIELD_EQ(alu_b_hi, (uint256_t(1) << 64) - 1),
418 ROW_FIELD_EQ(alu_b_lo, (uint256_t(1) << 64) - 3),
419 ROW_FIELD_EQ(alu_ic, 3),
420 ROW_FIELD_EQ(alu_c_hi, (uint256_t(1) << 64) - 5),
421 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
422 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
423 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
424 ROW_FIELD_EQ(alu_cf, 1),
425 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
426 ROW_FIELD_EQ(alu_max_value, u128_max),
427 ROW_FIELD_EQ(alu_sel_is_u128, 1),
428 ROW_FIELD_EQ(alu_sel_is_ff, 0),
429 ROW_FIELD_EQ(alu_tag_u128_diff_inv, 0),
430 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
431 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
432 ROW_FIELD_EQ(alu_sel_tag_err, 0),
433 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
434}
435
436// DIV TESTS
437
438const std::vector<MemoryValue> TEST_VALUES_DIV_OUT = {
439 MemoryValue::from_tag(MemoryTag::U1, 0), // Dividing by zero, so expecting an error
440 MemoryValue::from_tag(MemoryTag::U1, 1),
441 MemoryValue::from_tag(MemoryTag::U8, 4),
442 MemoryValue::from_tag(MemoryTag::U8, 0),
443 MemoryValue::from_tag(MemoryTag::U16, 0),
444 MemoryValue::from_tag(MemoryTag::U16, 1),
445 MemoryValue::from_tag(MemoryTag::U32, 0x33333331),
446 MemoryValue::from_tag(MemoryTag::U32, 1),
447 MemoryValue::from_tag(MemoryTag::U64, 0x3333333333333331ULL),
448 MemoryValue::from_tag(MemoryTag::U64, 1),
449 MemoryValue::from_tag(MemoryTag::U128, (((uint256_t(1) << 128) - 11) / 5)), // 0x3333333333333333333333333333331
450 MemoryValue::from_tag(MemoryTag::U128, 1),
451};
452
453const std::vector<ThreeOperandTestParams> TEST_VALUES_DIV = zip_helper(TEST_VALUES_DIV_OUT);
454
455class AluDivTraceGenerationTest : public AluTraceGenerationTest,
456 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
457
458INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluDivTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_DIV));
459
460TEST_P(AluDivTraceGenerationTest, TraceGenerationDiv)
461{
462 auto [a, b, c] = GetParam();
463 auto tag = a.get_tag();
464 bool div_0_error = b.as_ff() == FF(0);
465 bool is_u128 = tag == MemoryTag::U128;
466 builder.process(
467 {
468 { .operation = AluOperation::DIV, .a = a, .b = b, .c = c, .error = div_0_error },
469 },
470 trace);
471
472 EXPECT_THAT(
473 trace.as_rows(),
474 ElementsAre(AllOf(
475 ROW_FIELD_EQ(alu_sel_op_div, 1),
476 ROW_FIELD_EQ(alu_sel, 1),
477 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
478 ROW_FIELD_EQ(alu_ia, a),
479 ROW_FIELD_EQ(alu_ib, b),
480 ROW_FIELD_EQ(alu_ic, c),
481 ROW_FIELD_EQ(alu_helper1, div_0_error ? 0 : (a - b * c).as_ff()),
482 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
483 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
484 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
485 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
486 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
487 ROW_FIELD_EQ(alu_constant_64, 64),
488 ROW_FIELD_EQ(alu_sel_is_ff, tag == MemoryTag::FF ? 1 : 0),
489 ROW_FIELD_EQ(alu_sel_is_u128, is_u128 ? 1 : 0),
490 ROW_FIELD_EQ(
491 alu_tag_u128_diff_inv,
492 is_u128 ? 0 : (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::U128))).invert()),
493 ROW_FIELD_EQ(alu_sel_is_ff, 0),
494 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
495 (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
496 ROW_FIELD_EQ(alu_sel_mul_div_u128, is_u128 ? 1 : 0),
497 ROW_FIELD_EQ(alu_sel_div_no_err, div_0_error ? 0 : 1),
498 ROW_FIELD_EQ(alu_sel_div_0_err, div_0_error ? 1 : 0),
499 ROW_FIELD_EQ(alu_sel_tag_err, 0),
500 ROW_FIELD_EQ(alu_sel_err, div_0_error ? 1 : 0),
501 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
502}
503
504TEST_F(AluTraceGenerationTest, TraceGenerationDivU128)
505{
506 uint128_t u128_max = static_cast<uint128_t>(get_tag_max_value(MemoryTag::U128));
507 builder.process(
508 {
509 { .operation = AluOperation::DIV,
510 .a = MemoryValue::from<uint128_t>(6),
511 .b = MemoryValue::from<uint128_t>(3),
512 .c = MemoryValue::from<uint128_t>(2) },
513 { .operation = AluOperation::DIV,
514 .a = MemoryValue::from<uint128_t>(u128_max),
515 .b = MemoryValue::from<uint128_t>(u128_max - 2),
516 .c = MemoryValue::from<uint128_t>(1) },
517 },
518 trace);
519
520 EXPECT_THAT(trace.as_rows(),
521 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_div, 1),
522 ROW_FIELD_EQ(alu_sel, 1),
523 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
524 ROW_FIELD_EQ(alu_ia, 6),
525 ROW_FIELD_EQ(alu_a_hi, 0),
526 ROW_FIELD_EQ(alu_a_hi_bits, 64),
527 ROW_FIELD_EQ(alu_a_lo, 2),
528 ROW_FIELD_EQ(alu_a_lo_bits, 64),
529 ROW_FIELD_EQ(alu_ib, 3),
530 ROW_FIELD_EQ(alu_b_hi, 0),
531 ROW_FIELD_EQ(alu_b_lo, 3),
532 ROW_FIELD_EQ(alu_ic, 2),
533 ROW_FIELD_EQ(alu_helper1, 0),
534 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
535 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
536 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
537 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
538 ROW_FIELD_EQ(alu_max_value, u128_max),
539 ROW_FIELD_EQ(alu_constant_64, 64),
540 ROW_FIELD_EQ(alu_sel_is_u128, 1),
541 ROW_FIELD_EQ(alu_sel_is_ff, 0),
542 ROW_FIELD_EQ(alu_tag_u128_diff_inv, 0),
543 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
544 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
545 ROW_FIELD_EQ(alu_sel_div_no_err, 1),
546 ROW_FIELD_EQ(alu_sel_tag_err, 0),
547 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
548 AllOf(ROW_FIELD_EQ(alu_sel_op_div, 1),
549 ROW_FIELD_EQ(alu_sel, 1),
550 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
551 ROW_FIELD_EQ(alu_ia, u128_max),
552 ROW_FIELD_EQ(alu_a_hi, 0),
553 ROW_FIELD_EQ(alu_a_hi_bits, 64),
554 ROW_FIELD_EQ(alu_a_lo, 1),
555 ROW_FIELD_EQ(alu_a_lo_bits, 64),
556 ROW_FIELD_EQ(alu_ib, u128_max - 2),
557 ROW_FIELD_EQ(alu_b_hi, (uint256_t(1) << 64) - 1),
558 ROW_FIELD_EQ(alu_b_lo, (uint256_t(1) << 64) - 3),
559 ROW_FIELD_EQ(alu_ic, 1),
560 ROW_FIELD_EQ(alu_helper1, 2),
561 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
562 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
563 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
564 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
565 ROW_FIELD_EQ(alu_max_value, u128_max),
566 ROW_FIELD_EQ(alu_sel_is_u128, 1),
567 ROW_FIELD_EQ(alu_sel_is_ff, 0),
568 ROW_FIELD_EQ(alu_tag_u128_diff_inv, 0),
569 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
570 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
571 ROW_FIELD_EQ(alu_sel_div_no_err, 1),
572 ROW_FIELD_EQ(alu_sel_tag_err, 0),
573 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
574}
575
576TEST_F(AluTraceGenerationTest, TraceGenerationDivTagError)
577{
578 // Tests two cases:
579 // a. inputs are both FF => should have a tag error (FF_TAG_ERR)
580 // b. input a is FF, b is not => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
581 builder.process(
582 {
583 { .operation = AluOperation::DIV,
584 .a = MemoryValue::from<FF>(6),
585 .b = MemoryValue::from<FF>(3),
586 .c = MemoryValue::from<FF>(2),
587 .error = true },
588 { .operation = AluOperation::DIV,
589 .a = MemoryValue::from<FF>(6),
590 .b = MemoryValue::from<uint128_t>(3),
591 .c = MemoryValue::from<FF>(2),
592 .error = true },
593 },
594 trace);
595
596 EXPECT_THAT(
597 trace.as_rows(),
598 ElementsAre(
599 AllOf(ROW_FIELD_EQ(alu_sel_op_div, 1),
600 ROW_FIELD_EQ(alu_sel, 1),
601 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
602 ROW_FIELD_EQ(alu_ia, 6),
603 ROW_FIELD_EQ(alu_ib, 3),
604 ROW_FIELD_EQ(alu_ic, 2),
605 ROW_FIELD_EQ(alu_helper1, 0),
606 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
607 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
608 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
609 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
610 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
611 ROW_FIELD_EQ(alu_constant_64, 64),
612 ROW_FIELD_EQ(alu_sel_is_u128, 0),
613 ROW_FIELD_EQ(
614 alu_tag_u128_diff_inv,
615 (FF(static_cast<uint8_t>(MemoryTag::FF)) - FF(static_cast<uint8_t>(MemoryTag::U128))).invert()),
616 ROW_FIELD_EQ(alu_sel_is_ff, 1),
617 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
618 ROW_FIELD_EQ(alu_sel_div_no_err, 0),
619 ROW_FIELD_EQ(alu_sel_tag_err, 1),
620 ROW_FIELD_EQ(alu_sel_err, 1),
621 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
622 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
623 AllOf(
624 ROW_FIELD_EQ(alu_sel_op_div, 1),
625 ROW_FIELD_EQ(alu_sel, 1),
626 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
627 ROW_FIELD_EQ(alu_ia, 6),
628 ROW_FIELD_EQ(alu_ib, 3),
629 ROW_FIELD_EQ(alu_ic, 2),
630 ROW_FIELD_EQ(alu_helper1, 0),
631 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
632 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
633 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
634 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
635 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
636 ROW_FIELD_EQ(alu_constant_64, 64),
637 ROW_FIELD_EQ(alu_sel_is_u128, 0),
638 ROW_FIELD_EQ(
639 alu_tag_u128_diff_inv,
640 (FF(static_cast<uint8_t>(MemoryTag::FF)) - FF(static_cast<uint8_t>(MemoryTag::U128))).invert()),
641 ROW_FIELD_EQ(alu_sel_is_ff, 1),
642 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
643 ROW_FIELD_EQ(alu_sel_div_no_err, 0),
644 ROW_FIELD_EQ(alu_sel_tag_err, 1),
645 ROW_FIELD_EQ(alu_sel_err, 1),
646 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
647 ROW_FIELD_EQ(
648 alu_ab_tags_diff_inv,
649 (FF(static_cast<uint8_t>(MemoryTag::FF)) - FF(static_cast<uint8_t>(MemoryTag::U128))).invert()))));
650}
651
652TEST_F(AluTraceGenerationTest, TraceGenerationDivByZeroError)
653{
654 builder.process(
655 {
656 { .operation = AluOperation::DIV,
657 .a = MemoryValue::from<uint64_t>(6),
658 .b = MemoryValue::from<uint64_t>(0), // c is optional
659 .error = true },
660 },
661 trace);
662
663 auto tag = static_cast<uint8_t>(MemoryTag::U64);
664
665 EXPECT_THAT(
666 trace.as_rows(),
667 ElementsAre(AllOf(
668 ROW_FIELD_EQ(alu_sel_op_div, 1),
669 ROW_FIELD_EQ(alu_sel, 1),
670 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
671 ROW_FIELD_EQ(alu_ia, 6),
672 ROW_FIELD_EQ(alu_ib, 0),
673 ROW_FIELD_EQ(alu_helper1, 0),
674 ROW_FIELD_EQ(alu_ia_tag, tag),
675 ROW_FIELD_EQ(alu_ib_tag, tag),
676 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U64)),
677 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U64)),
678 ROW_FIELD_EQ(alu_constant_64, 64),
679 ROW_FIELD_EQ(alu_sel_is_u128, 0),
680 ROW_FIELD_EQ(
681 alu_tag_u128_diff_inv,
682 (FF(static_cast<uint8_t>(MemoryTag::U64)) - FF(static_cast<uint8_t>(MemoryTag::U128))).invert()),
683 ROW_FIELD_EQ(alu_sel_is_ff, 0),
684 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
685 (FF(static_cast<uint8_t>(MemoryTag::U64)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
686 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
687 ROW_FIELD_EQ(alu_sel_div_no_err, 0),
688 ROW_FIELD_EQ(alu_sel_div_0_err, 1),
689 ROW_FIELD_EQ(alu_sel_tag_err, 0),
690 ROW_FIELD_EQ(alu_sel_err, 1),
691 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
692}
693
694// FDIV TESTS
695
696// Note: The test framework below converts all inputs to FF values to allow for many happy path tests without adding
697// new vectors. Non-FF values are tested separately.
698const std::vector<MemoryValue> TEST_VALUES_FDIV_OUT = {
699 MemoryValue::from_tag(MemoryTag::FF, 0), // Dividing by zero, so expecting an error
700 MemoryValue::from_tag(MemoryTag::FF, 1),
701 MemoryValue::from_tag(MemoryTag::FF, 4),
702 MemoryValue::from_tag(MemoryTag::FF, FF("0x01e5d0e15e2a1a5bfd30530c2d3c49bd60f2fa0ce1a2e146f39a6e05cd2d2d2e")),
703 MemoryValue::from_tag(MemoryTag::FF, FF("0x1e980ebbc51694827ee20074ac28b250a037a43eb44b38e6aa367c57a05e6d48")),
704 MemoryValue::from_tag(MemoryTag::FF, FF("0x2147f0860ba1d62029c594e3f5aceb850f136498cea0446888431f547aadd073")),
705 MemoryValue::from_tag(MemoryTag::FF, FF("0x135b52945a13d9aa49b9b57c33cd568ba9ae5ce9ca4a2d06e7f3fbd4f9999998")),
706 MemoryValue::from_tag(MemoryTag::FF, FF("0x24cf2a710b7edf4a26671a904a58c669b3f0209955b8ae8fc6ebbaffdc413535")),
707 MemoryValue::from_tag(MemoryTag::FF, FF("0x135b52945a13d9aa49b9b57c33cd568ba9ae5ce9ca4a2d071b272f07f9999998")),
708 MemoryValue::from_tag(MemoryTag::FF, FF("0x0b4aa7141dd9de9dbb71b5c665b57fb2d51dbb57c3a94d1d4a4d490bf23d5d0d")),
709 MemoryValue::from_tag(MemoryTag::FF, FF("0x135b52945a13d9aa49b9b57c33cd568bdce1901cfd7d603a1b272f07f9999998")),
710 MemoryValue::from_tag(MemoryTag::FF, FF("0x27065734afd7f6d659d8a21b1823b65a575334117d9b1cb58b0a1af021960640")),
711 MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 2),
712};
713
714const std::vector<ThreeOperandTestParams> TEST_VALUES_FDIV = zip_helper(TEST_VALUES_FDIV_OUT);
715
716class AluFDivTraceGenerationTest : public AluTraceGenerationTest,
717 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
718
719INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluFDivTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_FDIV));
720
721TEST_P(AluFDivTraceGenerationTest, TraceGenerationFDiv)
722{
723 auto [a, b, c] = GetParam();
724 a = MemoryValue::from_tag(MemoryTag::FF, a);
725 b = MemoryValue::from_tag(MemoryTag::FF, b);
726 c = MemoryValue::from_tag(MemoryTag::FF, c);
727 auto tag = a.get_tag();
728
729 bool div_0_error = b.as_ff() == FF(0);
730
731 builder.process(
732 {
733 { .operation = AluOperation::FDIV, .a = a, .b = b, .c = c, .error = div_0_error },
734 },
735 trace);
736
737 EXPECT_THAT(trace.as_rows(),
738 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
739 ROW_FIELD_EQ(alu_sel, 1),
740 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
741 ROW_FIELD_EQ(alu_ia, a),
742 ROW_FIELD_EQ(alu_ib, b),
743 ROW_FIELD_EQ(alu_ic, c),
744 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
745 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
746 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
747 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
748 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
749 ROW_FIELD_EQ(alu_sel_is_u128, 0),
750 ROW_FIELD_EQ(alu_sel_is_ff, 1),
751 ROW_FIELD_EQ(alu_tag_ff_diff_inv, 0),
752 ROW_FIELD_EQ(alu_sel_div_0_err, div_0_error ? 1 : 0),
753 ROW_FIELD_EQ(alu_sel_tag_err, 0),
754 ROW_FIELD_EQ(alu_sel_err, div_0_error ? 1 : 0),
755 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
756}
757
758TEST_F(AluTraceGenerationTest, TraceGenerationFDivTagError)
759{
760 // Tests two cases unique to FDIV:
761 // a. inputs are both matching non-FF => should have a tag error (FF_TAG_ERR)
762 // b. input a is non-FF, b is FF => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
763 builder.process(
764 {
765 { .operation = AluOperation::FDIV,
766 .a = MemoryValue::from<uint128_t>(6),
767 .b = MemoryValue::from<uint128_t>(3),
768 .c = MemoryValue::from<uint128_t>(2),
769 .error = true },
770 { .operation = AluOperation::FDIV,
771 .a = MemoryValue::from<uint64_t>(6),
772 .b = MemoryValue::from<FF>(3),
773 .c = MemoryValue::from<uint64_t>(2),
774 .error = true },
775 },
776 trace);
777
778 auto u128_tag = static_cast<uint8_t>(MemoryTag::U128);
779 auto u64_tag = static_cast<uint8_t>(MemoryTag::U64);
780
781 EXPECT_THAT(
782 trace.as_rows(),
783 ElementsAre(
784 AllOf(ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
785 ROW_FIELD_EQ(alu_sel, 1),
786 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
787 ROW_FIELD_EQ(alu_ia, 6),
788 ROW_FIELD_EQ(alu_ib, 3),
789 ROW_FIELD_EQ(alu_ic, 2),
790 ROW_FIELD_EQ(alu_ia_tag, u128_tag),
791 ROW_FIELD_EQ(alu_ib_tag, u128_tag),
792 ROW_FIELD_EQ(alu_ic_tag, u128_tag),
793 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
794 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U128)),
795 ROW_FIELD_EQ(alu_sel_is_ff, 0),
796 ROW_FIELD_EQ(alu_sel_is_u128, 1),
797 ROW_FIELD_EQ(alu_tag_ff_diff_inv, (FF(u128_tag) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
798 ROW_FIELD_EQ(alu_sel_div_0_err, 0),
799 ROW_FIELD_EQ(alu_sel_tag_err, 1),
800 ROW_FIELD_EQ(alu_sel_err, 1),
801 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
802 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
803 AllOf(
804 ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
805 ROW_FIELD_EQ(alu_sel, 1),
806 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
807 ROW_FIELD_EQ(alu_ia, 6),
808 ROW_FIELD_EQ(alu_ib, 3),
809 ROW_FIELD_EQ(alu_ic, 2),
810 ROW_FIELD_EQ(alu_helper1, 0),
811 ROW_FIELD_EQ(alu_ia_tag, u64_tag),
812 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
813 ROW_FIELD_EQ(alu_ic_tag, u64_tag),
814 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U64)),
815 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U64)),
816 ROW_FIELD_EQ(alu_sel_is_ff, 0),
817 ROW_FIELD_EQ(alu_sel_is_u128, 0),
818 ROW_FIELD_EQ(alu_tag_ff_diff_inv, (FF(u64_tag) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
819 ROW_FIELD_EQ(alu_sel_div_0_err, 0),
820 ROW_FIELD_EQ(alu_sel_tag_err, 1),
821 ROW_FIELD_EQ(alu_sel_err, 1),
822 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
823 ROW_FIELD_EQ(alu_ab_tags_diff_inv, (FF(u64_tag) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()))));
824}
825
826TEST_F(AluTraceGenerationTest, TraceGenerationFDivByZeroError)
827{
828 builder.process(
829 {
830 {
831 .operation = AluOperation::FDIV,
832 .a = MemoryValue::from<FF>(6),
833 .b = MemoryValue::from<FF>(0), // c is optional
834 .error = true,
835 },
836 },
837 trace);
838
839 auto tag = static_cast<uint8_t>(MemoryTag::FF);
840
841 EXPECT_THAT(trace.as_rows(),
842 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
843 ROW_FIELD_EQ(alu_sel, 1),
844 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
845 ROW_FIELD_EQ(alu_ia, 6),
846 ROW_FIELD_EQ(alu_ib, 0),
847 ROW_FIELD_EQ(alu_ia_tag, tag),
848 ROW_FIELD_EQ(alu_ib_tag, tag),
849 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
850 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
851 ROW_FIELD_EQ(alu_sel_is_u128, 0),
852 ROW_FIELD_EQ(alu_sel_is_ff, 1),
853 ROW_FIELD_EQ(alu_sel_is_u128, 0),
854 ROW_FIELD_EQ(alu_tag_ff_diff_inv, 0),
855 ROW_FIELD_EQ(alu_sel_div_0_err, 1),
856 ROW_FIELD_EQ(alu_sel_tag_err, 0),
857 ROW_FIELD_EQ(alu_sel_err, 1),
858 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
859}
860
861// EQ TESTS
862
863const std::vector<MemoryValue> TEST_VALUES_EQ_OUT = {
864 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
865 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
866 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
867 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
868 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
869 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
870 MemoryValue::from_tag(MemoryTag::U1, 0),
871};
872
873const std::vector<ThreeOperandTestParams> TEST_VALUES_EQ = zip_helper(TEST_VALUES_EQ_OUT);
874
875class AluEQTraceGenerationTest : public AluTraceGenerationTest,
876 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
877
878INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluEQTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_EQ));
879
880TEST_P(AluEQTraceGenerationTest, TraceGenerationEQ)
881{
882 auto [a, _b, _c] = GetParam();
883 auto tag = a.get_tag();
884
885 builder.process(
886 {
887 {
888 .operation = AluOperation::EQ,
889 .a = a,
890 .b = a,
891 .c = MemoryValue::from_tag(MemoryTag::U1, 1),
892 },
893 },
894 trace);
895
896 EXPECT_THAT(trace.as_rows(),
897 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_eq, 1),
898 ROW_FIELD_EQ(alu_sel, 1),
899 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_EQ),
900 ROW_FIELD_EQ(alu_ia, a),
901 ROW_FIELD_EQ(alu_ib, a),
902 ROW_FIELD_EQ(alu_ic, 1),
903 ROW_FIELD_EQ(alu_helper1, 0),
904 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
905 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
906 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
907 ROW_FIELD_EQ(alu_sel_is_ff, tag == MemoryTag::FF ? 1 : 0),
908 ROW_FIELD_EQ(alu_sel_is_u128, tag == MemoryTag::U128 ? 1 : 0),
909 ROW_FIELD_EQ(alu_sel_tag_err, 0),
910 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
911}
912
913TEST_P(AluEQTraceGenerationTest, TraceGenerationInEQ)
914{
915 auto [a, b, c] = GetParam();
916 auto tag = a.get_tag();
917
918 builder.process(
919 {
920 {
921 .operation = AluOperation::EQ,
922 .a = a,
923 .b = b,
924 .c = c,
925 },
926 },
927 trace);
928
929 EXPECT_THAT(trace.as_rows(),
930 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_eq, 1),
931 ROW_FIELD_EQ(alu_sel, 1),
932 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_EQ),
933 ROW_FIELD_EQ(alu_ia, a),
934 ROW_FIELD_EQ(alu_ib, b),
935 ROW_FIELD_EQ(alu_ic, c),
936 ROW_FIELD_EQ(alu_ab_diff_inv, c.as_ff() == 1 ? 0 : (a.as_ff() - b.as_ff()).invert()),
937 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
938 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
939 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
940 ROW_FIELD_EQ(alu_sel_is_ff, tag == MemoryTag::FF ? 1 : 0),
941 ROW_FIELD_EQ(alu_sel_is_u128, tag == MemoryTag::U128 ? 1 : 0),
942 ROW_FIELD_EQ(alu_sel_tag_err, 0),
943 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
944}
945
946// LT TESTS
947
948const std::vector<MemoryValue> TEST_VALUES_LT_OUT = {
949 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
950 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
951 MemoryValue::from_tag(MemoryTag::U1, 1), MemoryValue::from_tag(MemoryTag::U1, 0),
952 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
953 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
954 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
955 MemoryValue::from_tag(MemoryTag::U1, 0),
956};
957
958const std::vector<ThreeOperandTestParams> TEST_VALUES_LT = zip_helper(TEST_VALUES_LT_OUT);
959
960class AluLTTraceGenerationTest : public AluTraceGenerationTest,
961 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
962
963INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluLTTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_LT));
964
965TEST_P(AluLTTraceGenerationTest, TraceGenerationLT)
966{
967 auto [a, b, c] = GetParam();
968 auto tag = a.get_tag();
969 bool is_ff = tag == MemoryTag::FF;
970 builder.process(
971 {
972 { .operation = AluOperation::LT, .a = a, .b = b, .c = c },
973 },
974 trace);
975
976 EXPECT_THAT(trace.as_rows(),
977 ElementsAre(AllOf(
978 ROW_FIELD_EQ(alu_sel_op_lt, 1),
979 ROW_FIELD_EQ(alu_sel, 1),
980 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_LT),
981 ROW_FIELD_EQ(alu_ia, a),
982 ROW_FIELD_EQ(alu_ib, b),
983 ROW_FIELD_EQ(alu_ic, c),
984 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
985 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
986 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
987 ROW_FIELD_EQ(alu_cf, 0),
988 ROW_FIELD_EQ(alu_gt_input_a, b),
989 ROW_FIELD_EQ(alu_gt_input_b, a),
990 ROW_FIELD_EQ(alu_gt_result_c, c),
991 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
992 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
993 ROW_FIELD_EQ(alu_sel_is_ff, is_ff ? 1 : 0),
994 ROW_FIELD_EQ(alu_sel_is_u128, tag == MemoryTag::U128 ? 1 : 0),
995 ROW_FIELD_EQ(alu_sel_ff_gt, is_ff ? 1 : 0),
996 ROW_FIELD_EQ(alu_sel_int_gt, is_ff ? 0 : 1),
997 ROW_FIELD_EQ(
998 alu_tag_ff_diff_inv,
999 is_ff ? 0 : (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
1000 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1001 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
1002}
1003
1004// LTE TESTS
1005
1006const std::vector<MemoryValue> TEST_VALUES_LTE_OUT = {
1007 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
1008 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
1009 MemoryValue::from_tag(MemoryTag::U1, 1), MemoryValue::from_tag(MemoryTag::U1, 0),
1010 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
1011 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
1012 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
1013 MemoryValue::from_tag(MemoryTag::U1, 0),
1014};
1015
1016const std::vector<ThreeOperandTestParams> TEST_VALUES_LTE = zip_helper(TEST_VALUES_LTE_OUT);
1017
1018class AluLTETraceGenerationTest : public AluTraceGenerationTest,
1019 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
1020
1021INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluLTETraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_LTE));
1022
1023TEST_P(AluLTETraceGenerationTest, TraceGenerationLTE)
1024{
1025 auto [a, b, c] = GetParam();
1026 auto tag = a.get_tag();
1027 bool is_ff = tag == MemoryTag::FF;
1028 builder.process(
1029 {
1030 { .operation = AluOperation::LTE, .a = a, .b = b, .c = c },
1031 },
1032 trace);
1033
1034 EXPECT_THAT(trace.as_rows(),
1035 ElementsAre(AllOf(
1036 ROW_FIELD_EQ(alu_sel_op_lte, 1),
1037 ROW_FIELD_EQ(alu_sel, 1),
1038 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_LTE),
1039 ROW_FIELD_EQ(alu_ia, a),
1040 ROW_FIELD_EQ(alu_ib, b),
1041 ROW_FIELD_EQ(alu_ic, c),
1042 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1043 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1044 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
1045 ROW_FIELD_EQ(alu_cf, 0),
1046 ROW_FIELD_EQ(alu_gt_input_a, a),
1047 ROW_FIELD_EQ(alu_gt_input_b, b),
1048 ROW_FIELD_EQ(alu_gt_result_c, c.as_ff() == 1 ? 0 : 1),
1049 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
1050 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1051 ROW_FIELD_EQ(alu_sel_is_u128, tag == MemoryTag::U128 ? 1 : 0),
1052 ROW_FIELD_EQ(alu_sel_is_ff, is_ff ? 1 : 0),
1053 ROW_FIELD_EQ(alu_sel_ff_gt, is_ff ? 1 : 0),
1054 ROW_FIELD_EQ(alu_sel_int_gt, is_ff ? 0 : 1),
1055 ROW_FIELD_EQ(
1056 alu_tag_ff_diff_inv,
1057 is_ff ? 0 : (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
1058 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1059 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
1060}
1061
1062// NOT Opcode TESTS
1063
1064const std::vector<MemoryValue> TEST_VALUES_NOT = split_helper(TEST_VALUES_IN);
1065
1066class AluNOTTraceGenerationTest : public AluTraceGenerationTest, public ::testing::WithParamInterface<MemoryValue> {};
1067
1068INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluNOTTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_NOT));
1069
1070TEST_P(AluNOTTraceGenerationTest, TraceGenerationNOT)
1071{
1072 auto a = GetParam();
1073 auto tag = a.get_tag();
1074 bool is_ff = tag == MemoryTag::FF;
1075 auto b = is_ff ? MemoryValue::from_tag(MemoryTag::FF, 0) : ~a;
1076
1077 builder.process(
1078 {
1079 { .operation = AluOperation::NOT, .a = a, .b = b, .error = is_ff },
1080 },
1081 trace);
1082
1083 EXPECT_THAT(trace.as_rows(),
1084 ElementsAre(AllOf(
1085 ROW_FIELD_EQ(alu_sel_op_not, 1),
1086 ROW_FIELD_EQ(alu_sel, 1),
1087 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_NOT),
1088 ROW_FIELD_EQ(alu_ia, a),
1089 ROW_FIELD_EQ(alu_ib, b),
1090 ROW_FIELD_EQ(alu_ic, 0),
1091 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1092 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1093 ROW_FIELD_EQ(alu_ic_tag, 0),
1094 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1095 ROW_FIELD_EQ(alu_sel_is_ff, is_ff ? 1 : 0),
1096 ROW_FIELD_EQ(alu_sel_is_u128, tag == MemoryTag::U128 ? 1 : 0),
1097 ROW_FIELD_EQ(
1098 alu_tag_ff_diff_inv,
1099 is_ff ? 0 : (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
1100 ROW_FIELD_EQ(alu_sel_tag_err, is_ff ? 1 : 0),
1101 ROW_FIELD_EQ(alu_sel_err, is_ff ? 1 : 0))));
1102}
1103
1104// SHL TESTS
1105
1106const std::vector<MemoryValue> TEST_VALUES_SHL_OUT = {
1107 MemoryValue::from_tag(MemoryTag::U1, 1),
1108 MemoryValue::from_tag(MemoryTag::U1, 0),
1109 MemoryValue::from_tag(MemoryTag::U8, 0),
1110 MemoryValue::from_tag(MemoryTag::U8, 0),
1111 MemoryValue::from_tag(MemoryTag::U16, 0),
1112 MemoryValue::from_tag(MemoryTag::U16, 0),
1113 MemoryValue::from_tag(MemoryTag::U32, 0xfffffec0),
1114 MemoryValue::from_tag(MemoryTag::U32, 0xb0000000),
1115 MemoryValue::from_tag(MemoryTag::U64, 0xfffffffffffffec0ULL),
1116 MemoryValue::from_tag(MemoryTag::U64, 0xb000000000000000ULL),
1117 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 320), // 0xfffffffffffffffffffffffffffffec0
1118 MemoryValue::from_tag(MemoryTag::U128, 0),
1119};
1120
1121const std::vector<ThreeOperandTestParams> TEST_VALUES_SHL = zip_helper(TEST_VALUES_SHL_OUT);
1122
1123class AluShlTraceGenerationTest : public AluTraceGenerationTest,
1124 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
1125
1126INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluShlTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_SHL));
1127
1128TEST_P(AluShlTraceGenerationTest, TraceGenerationShl)
1129{
1130 auto [a, b, c] = GetParam();
1131 auto tag = a.get_tag();
1132 uint256_t tag_bits = get_tag_bits(tag);
1133 uint256_t b_num = static_cast<uint256_t>(b.as_ff());
1134
1135 bool overflow = b_num > tag_bits;
1136 uint256_t shift_lo_bits = overflow ? tag_bits : static_cast<uint256_t>(tag_bits) - b_num;
1137 uint256_t shift_hi_bits = overflow ? static_cast<uint256_t>(tag_bits) : b_num;
1138 uint256_t two_pow_shift_lo_bits = overflow ? 0 : static_cast<uint256_t>(1) << shift_lo_bits;
1139 uint256_t a_lo = overflow ? b_num - tag_bits : static_cast<uint256_t>(a.as_ff()) % two_pow_shift_lo_bits;
1140 uint256_t a_hi = static_cast<uint256_t>(a.as_ff()) >> shift_lo_bits;
1141
1142 builder.process({ {
1143 .operation = AluOperation::SHL,
1144 .a = a,
1145 .b = b,
1146 .c = c,
1147 } },
1148 trace);
1149
1150 EXPECT_THAT(trace.as_rows(),
1151 ElementsAre(AllOf(
1152 ROW_FIELD_EQ(alu_sel_op_shl, 1),
1153 ROW_FIELD_EQ(alu_sel, 1),
1154 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHL),
1155 ROW_FIELD_EQ(alu_ia, a),
1156 ROW_FIELD_EQ(alu_a_hi, a_hi),
1157 ROW_FIELD_EQ(alu_a_hi_bits, shift_hi_bits),
1158 ROW_FIELD_EQ(alu_a_lo, a_lo),
1159 ROW_FIELD_EQ(alu_a_lo_bits, shift_lo_bits),
1160 ROW_FIELD_EQ(alu_ib, b),
1161 ROW_FIELD_EQ(alu_ic, c),
1162 ROW_FIELD_EQ(alu_helper1, overflow ? 0 : static_cast<uint256_t>(1) << b_num),
1163 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1164 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1165 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
1166 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
1167 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1168 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
1169 ROW_FIELD_EQ(alu_sel_is_u128, tag == MemoryTag::U128 ? 1 : 0),
1170 ROW_FIELD_EQ(alu_sel_is_ff, 0),
1171 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
1172 (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
1173 ROW_FIELD_EQ(alu_sel_shift_ops_no_overflow, overflow ? 0 : 1),
1174 ROW_FIELD_EQ(alu_shift_lo_bits, shift_lo_bits),
1175 ROW_FIELD_EQ(alu_two_pow_shift_lo_bits, two_pow_shift_lo_bits),
1176 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1177 ROW_FIELD_EQ(alu_sel_err, 0),
1178 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
1179}
1180
1181TEST_F(AluShlTraceGenerationTest, TraceGenerationShlTagError)
1182{
1183 // Tests two cases:
1184 // a. inputs are both FF => should have a tag error (FF_TAG_ERR)
1185 // b. input a is FF, b is not => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
1186 builder.process(
1187 {
1188 { .operation = AluOperation::SHL,
1189 .a = MemoryValue::from<FF>(6),
1190 .b = MemoryValue::from<FF>(3),
1191 .c = MemoryValue::from<FF>(48),
1192 .error = true },
1193 { .operation = AluOperation::SHL,
1194 .a = MemoryValue::from<FF>(6),
1195 .b = MemoryValue::from<uint128_t>(3),
1196 .c = MemoryValue::from<FF>(48),
1197 .error = true },
1198 },
1199 trace);
1200
1201 EXPECT_THAT(trace.as_rows(),
1202 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_shl, 1),
1203 ROW_FIELD_EQ(alu_sel, 1),
1204 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHL),
1205 ROW_FIELD_EQ(alu_ia, 6),
1206 ROW_FIELD_EQ(alu_ib, 3),
1207 ROW_FIELD_EQ(alu_ic, 48),
1208 ROW_FIELD_EQ(alu_helper1, 0),
1209 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1210 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
1211 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1212 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1213 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1214 ROW_FIELD_EQ(alu_sel_is_u128, 0),
1215 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1216 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1217 ROW_FIELD_EQ(alu_sel_err, 1),
1218 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
1219 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
1220 AllOf(ROW_FIELD_EQ(alu_sel_op_shl, 1),
1221 ROW_FIELD_EQ(alu_sel, 1),
1222 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHL),
1223 ROW_FIELD_EQ(alu_ia, 6),
1224 ROW_FIELD_EQ(alu_ib, 3),
1225 ROW_FIELD_EQ(alu_ic, 48),
1226 ROW_FIELD_EQ(alu_helper1, 0),
1227 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1228 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
1229 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1230 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1231 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1232 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1233 ROW_FIELD_EQ(alu_sel_is_u128, 0),
1234 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
1235 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1236 ROW_FIELD_EQ(alu_sel_err, 1),
1237 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
1238 ROW_FIELD_EQ(alu_ab_tags_diff_inv,
1239 (FF(static_cast<uint8_t>(MemoryTag::FF)) -
1240 FF(static_cast<uint8_t>(MemoryTag::U128)))
1241 .invert()))));
1242}
1243
1244// SHR TESTS
1245
1246const std::vector<MemoryValue> TEST_VALUES_SHR_OUT = {
1247 MemoryValue::from_tag(MemoryTag::U1, 1),
1248 MemoryValue::from_tag(MemoryTag::U1, 0),
1249 MemoryValue::from_tag(MemoryTag::U8, 0),
1250 MemoryValue::from_tag(MemoryTag::U8, 0),
1251 MemoryValue::from_tag(MemoryTag::U16, 0),
1252 MemoryValue::from_tag(MemoryTag::U16, 0),
1253 MemoryValue::from_tag(MemoryTag::U32, 0x7ffffff),
1254 MemoryValue::from_tag(MemoryTag::U32, 0x0000001f),
1255 MemoryValue::from_tag(MemoryTag::U64, 0x7ffffffffffffffULL),
1256 MemoryValue::from_tag(MemoryTag::U64, 0x000000000000001fULL),
1257 MemoryValue::from_tag(MemoryTag::U128,
1258 (uint256_t(1) << 128) - 1 - (uint256_t(248) << 120)), // 0x7ffffffffffffffffffffffffffffff
1259 MemoryValue::from_tag(MemoryTag::U128, 0x000000000000001fULL),
1260};
1261
1262const std::vector<ThreeOperandTestParams> TEST_VALUES_SHR = zip_helper(TEST_VALUES_SHR_OUT);
1263
1264class AluShrTraceGenerationTest : public AluTraceGenerationTest,
1265 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
1266
1267INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluShrTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_SHR));
1268
1269TEST_P(AluShrTraceGenerationTest, TraceGenerationShr)
1270{
1271 auto [a, b, c] = GetParam();
1272 auto tag = a.get_tag();
1273 uint256_t tag_bits = get_tag_bits(tag);
1274 uint256_t b_num = static_cast<uint256_t>(b.as_ff());
1275
1276 auto overflow = b_num > tag_bits;
1277 uint256_t shift_lo_bits = overflow ? tag_bits : b_num;
1278 uint256_t shift_hi_bits = overflow ? tag_bits : tag_bits - b_num;
1279 uint256_t two_pow_shift_lo_bits = overflow ? 0 : static_cast<uint256_t>(1) << shift_lo_bits;
1280 uint256_t a_lo = overflow ? b_num - tag_bits : static_cast<uint256_t>(a.as_ff()) % two_pow_shift_lo_bits;
1281 uint256_t a_hi = static_cast<uint256_t>(a.as_ff()) >> shift_lo_bits;
1282
1283 builder.process({ {
1284 .operation = AluOperation::SHR,
1285 .a = a,
1286 .b = b,
1287 .c = c,
1288 } },
1289 trace);
1290
1291 EXPECT_THAT(trace.as_rows(),
1292 ElementsAre(AllOf(
1293 ROW_FIELD_EQ(alu_sel_op_shr, 1),
1294 ROW_FIELD_EQ(alu_sel, 1),
1295 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHR),
1296 ROW_FIELD_EQ(alu_ia, a),
1297 ROW_FIELD_EQ(alu_a_hi, a_hi),
1298 ROW_FIELD_EQ(alu_a_hi_bits, shift_hi_bits),
1299 ROW_FIELD_EQ(alu_a_lo, a_lo),
1300 ROW_FIELD_EQ(alu_a_lo_bits, shift_lo_bits),
1301 ROW_FIELD_EQ(alu_ib, b),
1302 ROW_FIELD_EQ(alu_ic, c),
1303 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1304 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1305 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
1306 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
1307 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1308 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
1309 ROW_FIELD_EQ(alu_sel_is_u128, tag == MemoryTag::U128 ? 1 : 0),
1310 ROW_FIELD_EQ(alu_sel_is_ff, 0),
1311 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
1312 (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
1313 ROW_FIELD_EQ(alu_sel_shift_ops_no_overflow, overflow ? 0 : 1),
1314 ROW_FIELD_EQ(alu_shift_lo_bits, shift_lo_bits),
1315 ROW_FIELD_EQ(alu_two_pow_shift_lo_bits, two_pow_shift_lo_bits),
1316 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1317 ROW_FIELD_EQ(alu_sel_err, 0),
1318 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
1319}
1320
1321TEST_F(AluShrTraceGenerationTest, TraceGenerationShrTagError)
1322{
1323 // Tests two cases:
1324 // a. inputs are both FF => should have a tag error (FF_TAG_ERR)
1325 // b. input a is FF, b is not => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
1326 builder.process(
1327 {
1328 { .operation = AluOperation::SHR,
1329 .a = MemoryValue::from<FF>(6),
1330 .b = MemoryValue::from<FF>(3),
1331 .c = MemoryValue::from<FF>(0),
1332 .error = true },
1333 { .operation = AluOperation::SHR,
1334 .a = MemoryValue::from<FF>(6),
1335 .b = MemoryValue::from<uint128_t>(3),
1336 .c = MemoryValue::from<FF>(0),
1337 .error = true },
1338 },
1339 trace);
1340
1341 EXPECT_THAT(trace.as_rows(),
1342 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_shr, 1),
1343 ROW_FIELD_EQ(alu_sel, 1),
1344 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHR),
1345 ROW_FIELD_EQ(alu_ia, 6),
1346 ROW_FIELD_EQ(alu_ib, 3),
1347 ROW_FIELD_EQ(alu_ic, 0),
1348 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1349 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
1350 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1351 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1352 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1353 ROW_FIELD_EQ(alu_sel_is_u128, 0),
1354 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1355 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1356 ROW_FIELD_EQ(alu_sel_err, 1),
1357 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
1358 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
1359 AllOf(ROW_FIELD_EQ(alu_sel_op_shr, 1),
1360 ROW_FIELD_EQ(alu_sel, 1),
1361 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHR),
1362 ROW_FIELD_EQ(alu_ia, 6),
1363 ROW_FIELD_EQ(alu_ib, 3),
1364 ROW_FIELD_EQ(alu_ic, 0),
1365 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1366 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
1367 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1368 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1369 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1370 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1371 ROW_FIELD_EQ(alu_sel_is_u128, 0),
1372 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
1373 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1374 ROW_FIELD_EQ(alu_sel_err, 1),
1375 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
1376 ROW_FIELD_EQ(alu_ab_tags_diff_inv,
1377 (FF(static_cast<uint8_t>(MemoryTag::FF)) -
1378 FF(static_cast<uint8_t>(MemoryTag::U128)))
1379 .invert()))));
1380}
1381
1382// TRUNCATE operation (SET/CAST opcodes)
1383
1384// Truncation is a special case as we always have FF MemoryValue inputs:
1385struct TruncateTrivialTestParams {
1386 MemoryValue a;
1387 MemoryTag dst_tag;
1388 FF expected_result;
1389};
1390
1391const std::vector<TruncateTrivialTestParams> TRUNCATE_TRIVIAL_TEST_PARAMS = {
1392 {
1393 .a = MemoryValue::from_tag(MemoryTag::FF, 1),
1394 .dst_tag = MemoryTag::U1,
1395 .expected_result = 1,
1396 },
1397 {
1398 .a = MemoryValue::from_tag(MemoryTag::FF, 7),
1399 .dst_tag = MemoryTag::U8,
1400 .expected_result = 7,
1401 },
1402 {
1403 .a = MemoryValue::from_tag(MemoryTag::U32, 123456789),
1404 .dst_tag = MemoryTag::U32,
1405 .expected_result = 123456789,
1406 },
1407 {
1408 .a = MemoryValue::from_tag(MemoryTag::U128, 1234567890123456789ULL),
1409 .dst_tag = MemoryTag::U64,
1410 .expected_result = 1234567890123456789ULL,
1411 },
1412 {
1413 .a = MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 127) + 982739482),
1414 .dst_tag = MemoryTag::U128,
1415 .expected_result = (uint256_t(1) << 127) + 982739482,
1416 },
1417 {
1418 .a = MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 1),
1419 .dst_tag = MemoryTag::FF,
1420 .expected_result = FF::modulus - 1,
1421 },
1422};
1423
1424class AluTruncateTrivialTraceGenerationTest : public AluTraceGenerationTest,
1425 public ::testing::WithParamInterface<TruncateTrivialTestParams> {};
1426
1427INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest,
1428 AluTruncateTrivialTraceGenerationTest,
1429 ::testing::ValuesIn(TRUNCATE_TRIVIAL_TEST_PARAMS));
1430
1431TEST_P(AluTruncateTrivialTraceGenerationTest, TraceGenerationTruncateTrivial)
1432{
1433 auto [a, dst_tag, expected_result] = GetParam();
1434 auto b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(dst_tag));
1435 auto c = MemoryValue::from_tag(dst_tag, expected_result);
1436
1437 builder.process(
1438 {
1439 { .operation = AluOperation::TRUNCATE, .a = a, .b = b, .c = c },
1440 },
1441 trace);
1442
1443 EXPECT_THAT(trace.as_rows(),
1444 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_truncate, 1),
1445 ROW_FIELD_EQ(alu_sel_trunc_trivial, 1),
1446 ROW_FIELD_EQ(alu_sel_trunc_lt_128, 0),
1447 ROW_FIELD_EQ(alu_sel_trunc_gte_128, 0),
1448 ROW_FIELD_EQ(alu_sel_trunc_non_trivial, 0),
1449 ROW_FIELD_EQ(alu_sel, 1),
1450 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_TRUNCATE),
1451 ROW_FIELD_EQ(alu_ia, a),
1452 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(dst_tag)),
1453 ROW_FIELD_EQ(alu_ic, expected_result),
1454 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(dst_tag)),
1455 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(dst_tag)),
1456 ROW_FIELD_EQ(alu_sel_is_ff, dst_tag == MemoryTag::FF ? 1 : 0),
1457 ROW_FIELD_EQ(alu_sel_is_u128, dst_tag == MemoryTag::U128 ? 1 : 0),
1458 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1459 ROW_FIELD_EQ(alu_a_lo, 0),
1460 ROW_FIELD_EQ(alu_a_hi, 0),
1461 ROW_FIELD_EQ(alu_mid, 0),
1462 ROW_FIELD_EQ(alu_mid_bits, 0))));
1463}
1464
1465struct TruncateNonTrivialTestParams {
1466 MemoryValue a;
1467 MemoryTag dst_tag;
1468 FF expected_result;
1469 FF expected_lo_128;
1470 FF expected_mid;
1471};
1472
1473const std::vector<TruncateNonTrivialTestParams> TRUNCATE_LESS_THAN_128_TEST_PARAMS = {
1474 {
1475 .a = MemoryValue::from_tag(MemoryTag::U128, (uint256_t(98263) << 64) + 123456789987654321ULL),
1476 .dst_tag = MemoryTag::U64,
1477 .expected_result = 123456789987654321ULL,
1478 .expected_lo_128 = (uint256_t(98263) << 64) + 123456789987654321ULL,
1479 .expected_mid = 98263,
1480 },
1481 {
1482 .a = MemoryValue::from_tag(MemoryTag::U64, (uint256_t(98263) << 32) + 1234567ULL),
1483 .dst_tag = MemoryTag::U32,
1484 .expected_result = 1234567,
1485 .expected_lo_128 = (98263ULL << 32) + 1234567ULL,
1486 .expected_mid = 98263,
1487 },
1488 {
1489 .a = MemoryValue::from_tag(MemoryTag::U64, (uint256_t(98263) << 32) + 1234ULL),
1490 .dst_tag = MemoryTag::U16,
1491 .expected_result = 1234,
1492 .expected_lo_128 = (98263ULL << 32) + 1234ULL,
1493 .expected_mid = 98263ULL << 16,
1494 },
1495 {
1496 .a = MemoryValue::from_tag(MemoryTag::FF, 263),
1497 .dst_tag = MemoryTag::U8,
1498 .expected_result = 7,
1499 .expected_lo_128 = 263,
1500 .expected_mid = 1,
1501 },
1502 {
1503 .a = MemoryValue::from_tag(MemoryTag::U64, 999),
1504 .dst_tag = MemoryTag::U1,
1505 .expected_result = 1,
1506 .expected_lo_128 = 999,
1507 .expected_mid = 499,
1508 }
1509};
1510
1511class AluTruncateNonTrivialLT128TraceGenerationTest
1512 : public AluTraceGenerationTest,
1513 public ::testing::WithParamInterface<TruncateNonTrivialTestParams> {};
1514
1515INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest,
1516 AluTruncateNonTrivialLT128TraceGenerationTest,
1517 ::testing::ValuesIn(TRUNCATE_LESS_THAN_128_TEST_PARAMS));
1518
1519TEST_P(AluTruncateNonTrivialLT128TraceGenerationTest, TraceGenerationTruncateNonTrivialLT128)
1520{
1521 auto [a, dst_tag, expected_result, expected_lo_128, expected_mid] = GetParam();
1522 auto b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(dst_tag));
1523 auto c = MemoryValue::from_tag(dst_tag, expected_result);
1524
1525 builder.process(
1526 {
1527 { .operation = AluOperation::TRUNCATE, .a = a, .b = b, .c = c },
1528 },
1529 trace);
1530
1531 EXPECT_THAT(trace.as_rows(),
1532 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_truncate, 1),
1533 ROW_FIELD_EQ(alu_sel_trunc_trivial, 0),
1534 ROW_FIELD_EQ(alu_sel_trunc_lt_128, 1),
1535 ROW_FIELD_EQ(alu_sel_trunc_gte_128, 0),
1536 ROW_FIELD_EQ(alu_sel_trunc_non_trivial, 1),
1537 ROW_FIELD_EQ(alu_sel, 1),
1538 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_TRUNCATE),
1539 ROW_FIELD_EQ(alu_ia, a),
1540 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(dst_tag)),
1541 ROW_FIELD_EQ(alu_ic, expected_result),
1542 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(dst_tag)),
1543 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(dst_tag)),
1544 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1545 ROW_FIELD_EQ(alu_sel_is_ff, dst_tag == MemoryTag::FF ? 1 : 0),
1546 ROW_FIELD_EQ(alu_sel_is_u128, dst_tag == MemoryTag::U128 ? 1 : 0),
1547 ROW_FIELD_EQ(alu_a_lo, expected_lo_128),
1548 ROW_FIELD_EQ(alu_mid, expected_mid),
1549 ROW_FIELD_EQ(alu_mid_bits, 128 - get_tag_bits(dst_tag)))));
1550}
1551
1552const std::vector<TruncateNonTrivialTestParams> TRUNCATE_GREATER_THAN_128_TEST_PARAMS = {
1553 {
1554 .a = MemoryValue::from<FF>((uint256_t(98263) << 128) + (uint256_t(1111) << 64) + 123456789987654321ULL),
1555 .dst_tag = MemoryTag::U64,
1556 .expected_result = 123456789987654321ULL,
1557 .expected_lo_128 = (uint256_t(1111) << 64) + 123456789987654321ULL,
1558 .expected_mid = 1111,
1559 },
1560 {
1561 .a = MemoryValue::from<FF>((uint256_t(98263) << 128) + (uint256_t(1111) << 64) + 123456789),
1562 .dst_tag = MemoryTag::U32,
1563 .expected_result = 123456789,
1564 .expected_lo_128 = (uint256_t(1111) << 64) + 123456789,
1565 .expected_mid = 1111ULL << 32,
1566 },
1567 {
1568 .a = MemoryValue::from<FF>((uint256_t(98263) << 128) + (uint256_t(1111) << 64) + 1234),
1569 .dst_tag = MemoryTag::U16,
1570 .expected_result = 1234,
1571 .expected_lo_128 = (uint256_t(1111) << 64) + 1234,
1572 .expected_mid = 1111ULL << 48,
1573 },
1574 {
1575 .a = MemoryValue::from<FF>((uint256_t(98263) << 150) + (uint256_t(123456789987654321ULL) << 8) + 234),
1576 .dst_tag = MemoryTag::U8,
1577 .expected_result = 234,
1578 .expected_lo_128 = (uint256_t(123456789987654321ULL) << 8) + 234,
1579 .expected_mid = 123456789987654321ULL,
1580 }
1581};
1582
1583class AluTruncateNonTrivialGT128TraceGenerationTest
1584 : public AluTraceGenerationTest,
1585 public ::testing::WithParamInterface<TruncateNonTrivialTestParams> {};
1586
1587INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest,
1588 AluTruncateNonTrivialGT128TraceGenerationTest,
1589 ::testing::ValuesIn(TRUNCATE_GREATER_THAN_128_TEST_PARAMS));
1590
1591TEST_P(AluTruncateNonTrivialGT128TraceGenerationTest, TraceGenerationTruncateNonTrivialGT128)
1592{
1593 auto [a, dst_tag, expected_result, expected_lo_128, expected_mid] = GetParam();
1594 auto b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(dst_tag));
1595 auto c = MemoryValue::from_tag(dst_tag, expected_result);
1596
1597 builder.process(
1598 {
1599 { .operation = AluOperation::TRUNCATE, .a = a, .b = b, .c = c },
1600 },
1601 trace);
1602
1603 EXPECT_THAT(trace.as_rows(),
1604 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_truncate, 1),
1605 ROW_FIELD_EQ(alu_sel_trunc_trivial, 0),
1606 ROW_FIELD_EQ(alu_sel_trunc_lt_128, 0),
1607 ROW_FIELD_EQ(alu_sel_trunc_gte_128, 1),
1608 ROW_FIELD_EQ(alu_sel_trunc_non_trivial, 1),
1609 ROW_FIELD_EQ(alu_sel, 1),
1610 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_TRUNCATE),
1611 ROW_FIELD_EQ(alu_ia, a),
1612 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(dst_tag)),
1613 ROW_FIELD_EQ(alu_ic, expected_result),
1614 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(dst_tag)),
1615 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(dst_tag)),
1616 ROW_FIELD_EQ(alu_sel_is_ff, dst_tag == MemoryTag::FF ? 1 : 0),
1617 ROW_FIELD_EQ(alu_sel_is_u128, dst_tag == MemoryTag::U128 ? 1 : 0),
1618 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1619 ROW_FIELD_EQ(alu_a_lo, expected_lo_128),
1620 ROW_FIELD_EQ(alu_mid, expected_mid),
1621 ROW_FIELD_EQ(alu_mid_bits, 128 - get_tag_bits(dst_tag)))));
1622}
1623
1624} // namespace
1625} // namespace bb::avm2::tracegen
INSTANTIATE_TEST_SUITE_P
INSTANTIATE_TEST_SUITE_P(AcirTests, AcirIntegrationSingleTest, testing::Values("a_1327_concrete_in_generic", "a_1_mul", "a_2_div", "a_3_add", "a_4_sub", "a_5_over", "a_6", "a_6_array", "a_7", "a_7_function", "aes128_encrypt", "arithmetic_binary_operations", "array_dynamic", "array_dynamic_blackbox_input", "array_dynamic_main_output", "array_dynamic_nested_blackbox_input", "array_eq", "array_if_cond_simple", "array_len", "array_neq", "array_sort", "array_to_slice", "array_to_slice_constant_length", "assert", "assert_statement", "assign_ex", "bigint", "bit_and", "bit_not", "bit_shifts_comptime", "bit_shifts_runtime", "blake3", "bool_not", "bool_or", "break_and_continue", "brillig_acir_as_brillig", "brillig_array_eq", "brillig_array_to_slice", "brillig_arrays", "brillig_assert", "brillig_bit_shifts_runtime", "brillig_blake2s", "brillig_blake3", "brillig_calls", "brillig_calls_array", "brillig_calls_conditionals", "brillig_conditional", "brillig_cow", "brillig_cow_assign", "brillig_cow_regression", "brillig_ecdsa_secp256k1", "brillig_ecdsa_secp256r1", "brillig_embedded_curve", "brillig_fns_as_values", "brillig_hash_to_field", "brillig_identity_function", "brillig_keccak", "brillig_loop", "brillig_nested_arrays", "brillig_not", "brillig_oracle", "brillig_pedersen", "brillig_recursion", "brillig_references", "brillig_schnorr", "brillig_sha256", "brillig_signed_cmp", "brillig_signed_div", "brillig_slices", "brillig_to_be_bytes", "brillig_to_bits", "brillig_to_bytes_integration", "brillig_to_le_bytes", "brillig_top_level", "brillig_uninitialized_arrays", "brillig_wrapping", "cast_bool", "closures_mut_ref", "conditional_1", "conditional_2", "conditional_regression_421", "conditional_regression_547", "conditional_regression_661", "conditional_regression_short_circuit", "conditional_regression_underflow", "custom_entry", "databus", "debug_logs", "diamond_deps_0", "double_verify_nested_proof", "double_verify_proof", "ecdsa_secp256k1", "ecdsa_secp256r1", "ecdsa_secp256r1_3x", "eddsa", "embedded_curve_ops", "field_attribute", "generics", "global_consts", "hash_to_field", "hashmap", "higher_order_functions", "if_else_chain", "import", "inline_never_basic", "integer_array_indexing", "keccak256", "main_bool_arg", "main_return", "merkle_insert", "missing_closure_env", "modules", "modules_more", "modulus", "nested_array_dynamic", "nested_array_dynamic_simple", "nested_array_in_slice", "nested_arrays_from_brillig", "no_predicates_basic", "no_predicates_brillig", "no_predicates_numeric_generic_poseidon", "operator_overloading", "pedersen_check", "pedersen_commitment", "pedersen_hash", "poseidon_bn254_hash", "poseidonsponge_x5_254", "pred_eq", "prelude", "references", "regression", "regression_2660", "regression_3051", "regression_3394", "regression_3607", "regression_3889", "regression_4088", "regression_4124", "regression_4202", "regression_4449", "regression_4709", "regression_5045", "regression_capacity_tracker", "regression_mem_op_predicate", "regression_method_cannot_be_found", "regression_struct_array_conditional", "schnorr", "sha256", "sha2_byte", "side_effects_constrain_array", "signed_arithmetic", "signed_comparison", "signed_division", "simple_2d_array", "simple_add_and_ret_arr", "simple_array_param", "simple_bitwise", "simple_comparison", "simple_mut", "simple_not", "simple_print", "simple_program_addition", "simple_radix", "simple_shield", "simple_shift_left_right", "slice_coercion", "slice_dynamic_index", "slice_loop", "slices", "strings", "struct", "struct_array_inputs", "struct_fields_ordering", "struct_inputs", "submodules", "to_be_bytes", "to_bytes_consistent", "to_bytes_integration", "to_le_bytes", "trait_as_return_type", "trait_impl_base_type", "traits_in_crates_1", "traits_in_crates_2", "tuple_inputs", "tuples", "type_aliases", "u128", "u16_support", "unconstrained_empty", "unit_value", "unsafe_range_constraint", "witness_compression", "xor"))
TEST_P
TEST_P(AcirIntegrationSingleTest, DISABLED_ProveAndVerifyProgram)
Definition acir_integration.test.cpp:100
alu_event.hpp
alu_trace.hpp
dst_tag
MemoryTag dst_tag
Definition alu_trace.test.cpp:1387
expected_lo_128
FF expected_lo_128
Definition alu_trace.test.cpp:1469
expected_mid
FF expected_mid
Definition alu_trace.test.cpp:1470
AVM_EXEC_OP_ID_ALU_TRUNCATE
#define AVM_EXEC_OP_ID_ALU_TRUNCATE
Definition aztec_constants.hpp:108
AVM_EXEC_OP_ID_ALU_LTE
#define AVM_EXEC_OP_ID_ALU_LTE
Definition aztec_constants.hpp:104
AVM_EXEC_OP_ID_ALU_DIV
#define AVM_EXEC_OP_ID_ALU_DIV
Definition aztec_constants.hpp:100
AVM_EXEC_OP_ID_ALU_ADD
#define AVM_EXEC_OP_ID_ALU_ADD
Definition aztec_constants.hpp:97
AVM_EXEC_OP_ID_ALU_SHL
#define AVM_EXEC_OP_ID_ALU_SHL
Definition aztec_constants.hpp:106
AVM_EXEC_OP_ID_ALU_EQ
#define AVM_EXEC_OP_ID_ALU_EQ
Definition aztec_constants.hpp:102
AVM_EXEC_OP_ID_ALU_SUB
#define AVM_EXEC_OP_ID_ALU_SUB
Definition aztec_constants.hpp:98
AVM_EXEC_OP_ID_ALU_NOT
#define AVM_EXEC_OP_ID_ALU_NOT
Definition aztec_constants.hpp:105
AVM_EXEC_OP_ID_ALU_MUL
#define AVM_EXEC_OP_ID_ALU_MUL
Definition aztec_constants.hpp:99
AVM_EXEC_OP_ID_ALU_FDIV
#define AVM_EXEC_OP_ID_ALU_FDIV
Definition aztec_constants.hpp:101
AVM_EXEC_OP_ID_ALU_SHR
#define AVM_EXEC_OP_ID_ALU_SHR
Definition aztec_constants.hpp:107
AVM_EXEC_OP_ID_ALU_LT
#define AVM_EXEC_OP_ID_ALU_LT
Definition aztec_constants.hpp:103
bb::avm2::TaggedValue::from_tag
static TaggedValue from_tag(ValueTag tag, FF value)
Definition tagged_value.cpp:227
bb::avm2::tracegen::AluTraceBuilder::process
void process(const simulation::EventEmitterInterface< simulation::AluEvent >::Container &events, TraceContainer &trace)
Process the ALU events and populate the ALU relevant columns in the trace.
Definition alu_trace.cpp:410
bb::avm2::tracegen::TestTraceContainer::as_rows
std::vector< AvmFullRowConstRef > as_rows() const
Definition test_trace_container.cpp:28
bb::numeric::uint256_t
Definition uint256.hpp:32
builder
AluTraceBuilder builder
Definition alu.test.cpp:124
trace
TestTraceContainer trace
Definition data_copy.test.cpp:63
a
FF a
Definition field_gt.test.cpp:52
b
FF b
Definition field_gt.test.cpp:53
expected_result
bool expected_result
Definition field_gt.test.cpp:54
field_gt_event.hpp
flavor_settings.hpp
full_row.hpp
field_gt.hpp
ROW_FIELD_EQ
#define ROW_FIELD_EQ(field_name, expression)
Definition macros.hpp:15
memory_types.hpp
mock_field_gt.hpp
mock_gt.hpp
mock_range_check.hpp
bb::avm2::simulation::decompose_128
U128Decomposition decompose_128(const uint128_t &x)
Definition uint_decomposition.cpp:13
bb::avm2::MemoryValue
TaggedValue MemoryValue
Definition memory_types.hpp:10
bb::avm2::get_tag_bits
uint8_t get_tag_bits(ValueTag tag)
Definition tagged_value.cpp:162
bb::avm2::get_tag_max_value
uint256_t get_tag_max_value(ValueTag tag)
Definition tagged_value.cpp:204
bb::avm2::FF
AvmFlavorSettings::FF FF
Definition field.hpp:10
bb::TEST_F
TEST_F(IPATest, ChallengesAreZero)
Definition ipa.test.cpp:185
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
tuplet::tuple_cat
constexpr auto tuple_cat(T &&... ts)
Definition tuplet.hpp:1101
range_check_event.hpp
uint128_t
unsigned __int128 uint128_t
Definition serialize.hpp:44
range_check.hpp
bb::field< bb::Bn254FrParams >::modulus
static constexpr uint256_t modulus
Definition field_declarations.hpp:197
test_trace_container.hpp
instruction_spec.hpp