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/vm2/common/memory_types.hpp"
9#include "barretenberg/vm2/constraining/flavor_settings.hpp"
10#include "barretenberg/vm2/constraining/full_row.hpp"
11#include "barretenberg/vm2/generated/columns.hpp"
12#include "barretenberg/vm2/simulation/events/alu_event.hpp"
13#include "barretenberg/vm2/simulation/events/field_gt_event.hpp"
14#include "barretenberg/vm2/simulation/events/range_check_event.hpp"
15#include "barretenberg/vm2/simulation/gadgets/alu.hpp"
16#include "barretenberg/vm2/simulation/gadgets/field_gt.hpp"
17#include "barretenberg/vm2/simulation/gadgets/gt.hpp"
18#include "barretenberg/vm2/simulation/gadgets/range_check.hpp"
19#include "barretenberg/vm2/simulation/testing/mock_field_gt.hpp"
20#include "barretenberg/vm2/simulation/testing/mock_gt.hpp"
21#include "barretenberg/vm2/simulation/testing/mock_range_check.hpp"
22#include "barretenberg/vm2/testing/macros.hpp"
23#include "barretenberg/vm2/tracegen/alu_trace.hpp"
24#include "barretenberg/vm2/tracegen/lib/instruction_spec.hpp"
25#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
26
27namespace bb::avm2::tracegen {
28namespace {
29
30using simulation::AluError;
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, 0), // We don't set/check is_ff for ADD
173 ROW_FIELD_EQ(alu_sel_tag_err, 0),
174 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
175}
176
177TEST_F(AluTraceGenerationTest, TraceGenerationAddTagError)
178{
179 builder.process(
180 {
181 { .operation = AluOperation::ADD,
182 .a = MemoryValue::from<uint128_t>(1),
183 .b = MemoryValue::from<uint64_t>(2),
184 .c = MemoryValue::from<uint128_t>(3),
185 .error = AluError::TAG_ERROR },
186 { .operation = AluOperation::ADD,
187 .a = MemoryValue::from<uint128_t>(1),
188 .b = MemoryValue::from<uint128_t>(2),
189 .c = MemoryValue::from<uint64_t>(3) },
190 },
191 trace);
192
193 EXPECT_THAT(
194 trace.as_rows(),
195 ElementsAre(
196 AllOf(ROW_FIELD_EQ(alu_sel_op_add, 1),
197 ROW_FIELD_EQ(alu_sel, 1),
198 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_ADD),
199 ROW_FIELD_EQ(alu_ia, 1),
200 ROW_FIELD_EQ(alu_ib, 2),
201 ROW_FIELD_EQ(alu_ic, 3),
202 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
203 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U64)),
204 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
205 ROW_FIELD_EQ(alu_cf, 0),
206 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
207 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U128)),
208 ROW_FIELD_EQ(alu_sel_is_ff, 0),
209 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
210 ROW_FIELD_EQ(alu_sel_tag_err, 1),
211 ROW_FIELD_EQ(alu_sel_err, 1),
212 ROW_FIELD_EQ(
213 alu_ab_tags_diff_inv,
214 (FF(static_cast<uint8_t>(MemoryTag::U128)) - FF(static_cast<uint8_t>(MemoryTag::U64))).invert())),
215 AllOf(ROW_FIELD_EQ(alu_sel_op_add, 1),
216 ROW_FIELD_EQ(alu_sel, 1),
217 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_ADD),
218 ROW_FIELD_EQ(alu_ia, 1),
219 ROW_FIELD_EQ(alu_ib, 2),
220 ROW_FIELD_EQ(alu_ic, 3),
221 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
222 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
223 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U64)),
224 ROW_FIELD_EQ(alu_cf, 0),
225 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
226 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U128)),
227 ROW_FIELD_EQ(alu_sel_is_ff, 0),
228 ROW_FIELD_EQ(alu_sel_tag_err,
229 0)) // Incorrect c tag does not create a tag error (see C_TAG_CHECK)
230 ));
231}
232
233// SUB TESTS
234
235const std::vector<MemoryValue> TEST_VALUES_SUB_OUT = {
236 MemoryValue::from_tag(MemoryTag::U1, 1),
237 MemoryValue::from_tag(MemoryTag::U1, 0),
238 MemoryValue::from_tag(MemoryTag::U8, 150),
239 MemoryValue::from_tag(MemoryTag::U8, 201),
240 MemoryValue::from_tag(MemoryTag::U16, 66),
241 MemoryValue::from_tag(MemoryTag::U16, 1),
242 MemoryValue::from_tag(MemoryTag::U32, (uint256_t(1) << 32) - 15),
243 MemoryValue::from_tag(MemoryTag::U32, (uint256_t(1) << 32) - 5),
244 MemoryValue::from_tag(MemoryTag::U64, (uint256_t(1) << 64) - 15),
245 MemoryValue::from_tag(MemoryTag::U64, (uint256_t(1) << 64) - 5),
246 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 15),
247 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 5),
248 MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 6),
249};
250
251const std::vector<ThreeOperandTestParams> TEST_VALUES_SUB = zip_helper(TEST_VALUES_SUB_OUT);
252
253class AluSubTraceGenerationTest : public AluTraceGenerationTest,
254 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
255
256INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluSubTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_SUB));
257
258TEST_P(AluSubTraceGenerationTest, TraceGenerationSub)
259{
260 auto [a, b, c] = GetParam();
261 auto tag = a.get_tag();
262 builder.process(
263 {
264 { .operation = AluOperation::SUB, .a = a, .b = b, .c = c },
265 },
266 trace);
267
268 EXPECT_THAT(trace.as_rows(),
269 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_sub, 1),
270 ROW_FIELD_EQ(alu_sel, 1),
271 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SUB),
272 ROW_FIELD_EQ(alu_ia, a),
273 ROW_FIELD_EQ(alu_ib, b),
274 ROW_FIELD_EQ(alu_ic, c),
275 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
276 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
277 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
278 ROW_FIELD_EQ(alu_cf, a.as_ff() - b.as_ff() != c.as_ff() ? 1 : 0),
279 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
280 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
281 ROW_FIELD_EQ(alu_sel_tag_err, 0),
282 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
283}
284
285// MUL TESTS
286
287const std::vector<MemoryValue> TEST_VALUES_MUL_OUT = {
288 MemoryValue::from_tag(MemoryTag::U1, 0),
289 MemoryValue::from_tag(MemoryTag::U1, 1),
290 MemoryValue::from_tag(MemoryTag::U8, 16),
291 MemoryValue::from_tag(MemoryTag::U8, 8),
292 MemoryValue::from_tag(MemoryTag::U16, 64456),
293 MemoryValue::from_tag(MemoryTag::U16, 1260),
294 MemoryValue::from_tag(MemoryTag::U32, (uint256_t(1) << 32) - 50),
295 MemoryValue::from_tag(MemoryTag::U32, 50),
296 MemoryValue::from_tag(MemoryTag::U64, (uint256_t(1) << 64) - 50),
297 MemoryValue::from_tag(MemoryTag::U64, 50),
298 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 50),
299 MemoryValue::from_tag(MemoryTag::U128, 50),
300 MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 8),
301};
302
303const std::vector<ThreeOperandTestParams> TEST_VALUES_MUL = zip_helper(TEST_VALUES_MUL_OUT);
304
305class AluMulTraceGenerationTest : public AluTraceGenerationTest,
306 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
307
308INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluMulTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_MUL));
309
310TEST_P(AluMulTraceGenerationTest, TraceGenerationMul)
311{
312 auto [a, b, c] = GetParam();
313 auto tag = a.get_tag();
314 uint256_t a_int = static_cast<uint256_t>(a.as_ff());
315 uint256_t b_int = static_cast<uint256_t>(b.as_ff());
316 auto c_hi = tag == MemoryTag::FF ? 0 : (a_int * b_int) >> get_tag_bits(tag);
317 bool is_u128 = tag == MemoryTag::U128;
318 bool cf = false;
319 if (is_u128) {
320 // For u128s, we decompose a and b into 64 bit chunks:
321 auto a_hi = simulation::decompose(static_cast<uint128_t>(a.as_ff())).hi;
322 auto b_hi = simulation::decompose(static_cast<uint128_t>(b.as_ff())).hi;
323 // c_hi = old_c_hi - a_hi * b_hi % 2^64
324 auto hi_operand = static_cast<uint256_t>(a_hi) * static_cast<uint256_t>(b_hi);
325 cf = hi_operand != 0;
326 c_hi = (c_hi - hi_operand) % (uint256_t(1) << 64);
327 }
328 builder.process(
329 {
330 { .operation = AluOperation::MUL, .a = a, .b = b, .c = c },
331 },
332 trace);
333
334 EXPECT_THAT(
335 trace.as_rows(),
336 ElementsAre(AllOf(
337 ROW_FIELD_EQ(alu_sel_op_mul, 1),
338 ROW_FIELD_EQ(alu_sel, 1),
339 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_MUL),
340 ROW_FIELD_EQ(alu_ia, a),
341 ROW_FIELD_EQ(alu_ib, b),
342 ROW_FIELD_EQ(alu_ic, c),
343 ROW_FIELD_EQ(alu_c_hi, c_hi),
344 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
345 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
346 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
347 ROW_FIELD_EQ(alu_cf, cf),
348 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
349 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
350 ROW_FIELD_EQ(alu_constant_64, 64),
351 ROW_FIELD_EQ(alu_sel_is_u128, is_u128 ? 1 : 0),
352 ROW_FIELD_EQ(
353 alu_tag_u128_diff_inv,
354 is_u128 ? 0 : (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::U128))).invert()),
355 ROW_FIELD_EQ(alu_sel_mul_div_u128, is_u128 ? 1 : 0),
356 ROW_FIELD_EQ(alu_sel_mul_u128, is_u128 ? 1 : 0),
357 ROW_FIELD_EQ(alu_sel_tag_err, 0),
358 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
359}
360
361TEST_F(AluTraceGenerationTest, TraceGenerationMulU128)
362{
363 uint128_t u128_max = static_cast<uint128_t>(get_tag_max_value(MemoryTag::U128));
364 builder.process(
365 {
366 { .operation = AluOperation::MUL,
367 .a = MemoryValue::from<uint128_t>(2),
368 .b = MemoryValue::from<uint128_t>(3),
369 .c = MemoryValue::from<uint128_t>(6) },
370 { .operation = AluOperation::MUL,
371 .a = MemoryValue::from<uint128_t>(u128_max),
372 .b = MemoryValue::from<uint128_t>(u128_max - 2),
373 .c = MemoryValue::from<uint128_t>(3) },
374 },
375 trace);
376
377 EXPECT_THAT(trace.as_rows(),
378 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_mul, 1),
379 ROW_FIELD_EQ(alu_sel, 1),
380 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_MUL),
381 ROW_FIELD_EQ(alu_ia, 2),
382 ROW_FIELD_EQ(alu_a_hi, 0),
383 ROW_FIELD_EQ(alu_a_hi_bits, 64),
384 ROW_FIELD_EQ(alu_a_lo, 2),
385 ROW_FIELD_EQ(alu_a_lo_bits, 64),
386 ROW_FIELD_EQ(alu_ib, 3),
387 ROW_FIELD_EQ(alu_b_hi, 0),
388 ROW_FIELD_EQ(alu_b_lo, 3),
389 ROW_FIELD_EQ(alu_ic, 6),
390 ROW_FIELD_EQ(alu_c_hi, 0),
391 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
392 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
393 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
394 ROW_FIELD_EQ(alu_cf, 0),
395 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
396 ROW_FIELD_EQ(alu_max_value, u128_max),
397 ROW_FIELD_EQ(alu_constant_64, 64),
398 ROW_FIELD_EQ(alu_sel_is_u128, 1),
399 ROW_FIELD_EQ(alu_tag_u128_diff_inv, 0),
400 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
401 ROW_FIELD_EQ(alu_sel_mul_u128, 1),
402 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
403 ROW_FIELD_EQ(alu_sel_tag_err, 0),
404 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
405 AllOf(ROW_FIELD_EQ(alu_sel_op_mul, 1),
406 ROW_FIELD_EQ(alu_sel, 1),
407 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_MUL),
408 ROW_FIELD_EQ(alu_ia, u128_max),
409 ROW_FIELD_EQ(alu_a_hi, (uint256_t(1) << 64) - 1),
410 ROW_FIELD_EQ(alu_a_hi_bits, 64),
411 ROW_FIELD_EQ(alu_a_lo, (uint256_t(1) << 64) - 1),
412 ROW_FIELD_EQ(alu_a_lo_bits, 64),
413 ROW_FIELD_EQ(alu_ib, u128_max - 2),
414 ROW_FIELD_EQ(alu_b_hi, (uint256_t(1) << 64) - 1),
415 ROW_FIELD_EQ(alu_b_lo, (uint256_t(1) << 64) - 3),
416 ROW_FIELD_EQ(alu_ic, 3),
417 ROW_FIELD_EQ(alu_c_hi, (uint256_t(1) << 64) - 5),
418 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
419 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
420 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
421 ROW_FIELD_EQ(alu_cf, 1),
422 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
423 ROW_FIELD_EQ(alu_max_value, u128_max),
424 ROW_FIELD_EQ(alu_sel_is_u128, 1),
425 ROW_FIELD_EQ(alu_tag_u128_diff_inv, 0),
426 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
427 ROW_FIELD_EQ(alu_sel_mul_u128, 1),
428 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
429 ROW_FIELD_EQ(alu_sel_tag_err, 0),
430 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
431}
432
433// DIV TESTS
434
435const std::vector<MemoryValue> TEST_VALUES_DIV_OUT = {
436 MemoryValue::from_tag(MemoryTag::U1, 0), // Dividing by zero, so expecting an error
437 MemoryValue::from_tag(MemoryTag::U1, 1),
438 MemoryValue::from_tag(MemoryTag::U8, 4),
439 MemoryValue::from_tag(MemoryTag::U8, 0),
440 MemoryValue::from_tag(MemoryTag::U16, 0),
441 MemoryValue::from_tag(MemoryTag::U16, 1),
442 MemoryValue::from_tag(MemoryTag::U32, 0x33333331),
443 MemoryValue::from_tag(MemoryTag::U32, 1),
444 MemoryValue::from_tag(MemoryTag::U64, 0x3333333333333331ULL),
445 MemoryValue::from_tag(MemoryTag::U64, 1),
446 MemoryValue::from_tag(MemoryTag::U128, (((uint256_t(1) << 128) - 11) / 5)), // 0x3333333333333333333333333333331
447 MemoryValue::from_tag(MemoryTag::U128, 1),
448};
449
450const std::vector<ThreeOperandTestParams> TEST_VALUES_DIV = zip_helper(TEST_VALUES_DIV_OUT);
451
452class AluDivTraceGenerationTest : public AluTraceGenerationTest,
453 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
454
455INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluDivTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_DIV));
456
457TEST_P(AluDivTraceGenerationTest, TraceGenerationDiv)
458{
459 auto [a, b, c] = GetParam();
460 auto tag = a.get_tag();
461 bool div_0_error = b.as_ff() == FF(0);
462 bool is_u128 = tag == MemoryTag::U128;
463 builder.process(
464 {
465 { .operation = AluOperation::DIV,
466 .a = a,
467 .b = b,
468 .c = c,
469 .error = div_0_error ? std::make_optional(simulation::AluError::DIV_0_ERROR) : std::nullopt },
470 },
471 trace);
472
473 EXPECT_THAT(
474 trace.as_rows(),
475 ElementsAre(AllOf(
476 ROW_FIELD_EQ(alu_sel_op_div, 1),
477 ROW_FIELD_EQ(alu_sel, 1),
478 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
479 ROW_FIELD_EQ(alu_ia, a),
480 ROW_FIELD_EQ(alu_ib, b),
481 ROW_FIELD_EQ(alu_ic, c),
482 ROW_FIELD_EQ(alu_helper1, div_0_error ? 0 : (a - b * c).as_ff()),
483 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
484 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
485 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
486 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
487 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
488 ROW_FIELD_EQ(alu_constant_64, 64),
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_0_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_tag_u128_diff_inv, 0),
542 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
543 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
544 ROW_FIELD_EQ(alu_sel_div_no_0_err, 1),
545 ROW_FIELD_EQ(alu_sel_tag_err, 0),
546 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
547 AllOf(ROW_FIELD_EQ(alu_sel_op_div, 1),
548 ROW_FIELD_EQ(alu_sel, 1),
549 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
550 ROW_FIELD_EQ(alu_ia, u128_max),
551 ROW_FIELD_EQ(alu_a_hi, 0),
552 ROW_FIELD_EQ(alu_a_hi_bits, 64),
553 ROW_FIELD_EQ(alu_a_lo, 1),
554 ROW_FIELD_EQ(alu_a_lo_bits, 64),
555 ROW_FIELD_EQ(alu_ib, u128_max - 2),
556 ROW_FIELD_EQ(alu_b_hi, (uint256_t(1) << 64) - 1),
557 ROW_FIELD_EQ(alu_b_lo, (uint256_t(1) << 64) - 3),
558 ROW_FIELD_EQ(alu_ic, 1),
559 ROW_FIELD_EQ(alu_helper1, 2),
560 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
561 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
562 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
563 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
564 ROW_FIELD_EQ(alu_max_value, u128_max),
565 ROW_FIELD_EQ(alu_sel_is_u128, 1),
566 ROW_FIELD_EQ(alu_tag_u128_diff_inv, 0),
567 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
568 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
569 ROW_FIELD_EQ(alu_sel_div_no_0_err, 1),
570 ROW_FIELD_EQ(alu_sel_tag_err, 0),
571 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
572}
573
574TEST_F(AluTraceGenerationTest, TraceGenerationDivTagError)
575{
576 // Tests two cases:
577 // a. inputs are both FF => should have a tag error (FF_TAG_ERR)
578 // b. input a is FF, b is not => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
579 builder.process(
580 {
581 { .operation = AluOperation::DIV,
582 .a = MemoryValue::from<FF>(6),
583 .b = MemoryValue::from<FF>(3),
584 .c = MemoryValue::from<FF>(2),
585 .error = AluError::TAG_ERROR },
586 { .operation = AluOperation::DIV,
587 .a = MemoryValue::from<FF>(6),
588 .b = MemoryValue::from<uint128_t>(3),
589 .c = MemoryValue::from<FF>(2),
590 .error = AluError::TAG_ERROR },
591 },
592 trace);
593
594 EXPECT_THAT(
595 trace.as_rows(),
596 ElementsAre(
597 AllOf(ROW_FIELD_EQ(alu_sel_op_div, 1),
598 ROW_FIELD_EQ(alu_sel, 1),
599 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
600 ROW_FIELD_EQ(alu_ia, 6),
601 ROW_FIELD_EQ(alu_ib, 3),
602 ROW_FIELD_EQ(alu_ic, 2),
603 ROW_FIELD_EQ(alu_helper1, 0),
604 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
605 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
606 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
607 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
608 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
609 ROW_FIELD_EQ(alu_constant_64, 64),
610 ROW_FIELD_EQ(alu_sel_is_u128, 0),
611 ROW_FIELD_EQ(
612 alu_tag_u128_diff_inv,
613 (FF(static_cast<uint8_t>(MemoryTag::FF)) - FF(static_cast<uint8_t>(MemoryTag::U128))).invert()),
614 ROW_FIELD_EQ(alu_sel_is_ff, 1),
615 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
616 ROW_FIELD_EQ(alu_sel_div_no_0_err, 1),
617 ROW_FIELD_EQ(alu_sel_tag_err, 1),
618 ROW_FIELD_EQ(alu_sel_err, 1),
619 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
620 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
621 AllOf(
622 ROW_FIELD_EQ(alu_sel_op_div, 1),
623 ROW_FIELD_EQ(alu_sel, 1),
624 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
625 ROW_FIELD_EQ(alu_ia, 6),
626 ROW_FIELD_EQ(alu_ib, 3),
627 ROW_FIELD_EQ(alu_ic, 2),
628 ROW_FIELD_EQ(alu_helper1, 0),
629 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
630 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
631 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
632 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
633 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
634 ROW_FIELD_EQ(alu_constant_64, 64),
635 ROW_FIELD_EQ(alu_sel_is_u128, 0),
636 ROW_FIELD_EQ(
637 alu_tag_u128_diff_inv,
638 (FF(static_cast<uint8_t>(MemoryTag::FF)) - FF(static_cast<uint8_t>(MemoryTag::U128))).invert()),
639 ROW_FIELD_EQ(alu_sel_is_ff, 1),
640 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
641 ROW_FIELD_EQ(alu_sel_div_no_0_err, 1),
642 ROW_FIELD_EQ(alu_sel_tag_err, 1),
643 ROW_FIELD_EQ(alu_sel_err, 1),
644 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
645 ROW_FIELD_EQ(
646 alu_ab_tags_diff_inv,
647 (FF(static_cast<uint8_t>(MemoryTag::FF)) - FF(static_cast<uint8_t>(MemoryTag::U128))).invert()))));
648}
649
650TEST_F(AluTraceGenerationTest, TraceGenerationDivByZeroError)
651{
652 builder.process(
653 {
654 { .operation = AluOperation::DIV,
655 .a = MemoryValue::from<uint64_t>(6),
656 .b = MemoryValue::from<uint64_t>(0), // c is optional
657 .error = AluError::DIV_0_ERROR },
658 },
659 trace);
660
661 auto tag = static_cast<uint8_t>(MemoryTag::U64);
662
663 EXPECT_THAT(
664 trace.as_rows(),
665 ElementsAre(AllOf(
666 ROW_FIELD_EQ(alu_sel_op_div, 1),
667 ROW_FIELD_EQ(alu_sel, 1),
668 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
669 ROW_FIELD_EQ(alu_ia, 6),
670 ROW_FIELD_EQ(alu_ib, 0),
671 ROW_FIELD_EQ(alu_helper1, 0),
672 ROW_FIELD_EQ(alu_ia_tag, tag),
673 ROW_FIELD_EQ(alu_ib_tag, tag),
674 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U64)),
675 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U64)),
676 ROW_FIELD_EQ(alu_constant_64, 64),
677 ROW_FIELD_EQ(alu_sel_is_u128, 0),
678 ROW_FIELD_EQ(
679 alu_tag_u128_diff_inv,
680 (FF(static_cast<uint8_t>(MemoryTag::U64)) - FF(static_cast<uint8_t>(MemoryTag::U128))).invert()),
681 ROW_FIELD_EQ(alu_sel_is_ff, 0),
682 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
683 (FF(static_cast<uint8_t>(MemoryTag::U64)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
684 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
685 ROW_FIELD_EQ(alu_sel_div_no_0_err, 0),
686 ROW_FIELD_EQ(alu_sel_div_0_err, 1),
687 ROW_FIELD_EQ(alu_sel_tag_err, 0),
688 ROW_FIELD_EQ(alu_sel_err, 1),
689 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
690}
691
692// FDIV TESTS
693
694// Note: The test framework below converts all inputs to FF values to allow for many happy path tests without adding
695// new vectors. Non-FF values are tested separately.
696const std::vector<MemoryValue> TEST_VALUES_FDIV_OUT = {
697 MemoryValue::from_tag(MemoryTag::FF, 0), // Dividing by zero, so expecting an error
698 MemoryValue::from_tag(MemoryTag::FF, 1),
699 MemoryValue::from_tag(MemoryTag::FF, 4),
700 MemoryValue::from_tag(MemoryTag::FF, FF("0x01e5d0e15e2a1a5bfd30530c2d3c49bd60f2fa0ce1a2e146f39a6e05cd2d2d2e")),
701 MemoryValue::from_tag(MemoryTag::FF, FF("0x1e980ebbc51694827ee20074ac28b250a037a43eb44b38e6aa367c57a05e6d48")),
702 MemoryValue::from_tag(MemoryTag::FF, FF("0x2147f0860ba1d62029c594e3f5aceb850f136498cea0446888431f547aadd073")),
703 MemoryValue::from_tag(MemoryTag::FF, FF("0x135b52945a13d9aa49b9b57c33cd568ba9ae5ce9ca4a2d06e7f3fbd4f9999998")),
704 MemoryValue::from_tag(MemoryTag::FF, FF("0x24cf2a710b7edf4a26671a904a58c669b3f0209955b8ae8fc6ebbaffdc413535")),
705 MemoryValue::from_tag(MemoryTag::FF, FF("0x135b52945a13d9aa49b9b57c33cd568ba9ae5ce9ca4a2d071b272f07f9999998")),
706 MemoryValue::from_tag(MemoryTag::FF, FF("0x0b4aa7141dd9de9dbb71b5c665b57fb2d51dbb57c3a94d1d4a4d490bf23d5d0d")),
707 MemoryValue::from_tag(MemoryTag::FF, FF("0x135b52945a13d9aa49b9b57c33cd568bdce1901cfd7d603a1b272f07f9999998")),
708 MemoryValue::from_tag(MemoryTag::FF, FF("0x27065734afd7f6d659d8a21b1823b65a575334117d9b1cb58b0a1af021960640")),
709 MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 2),
710};
711
712const std::vector<ThreeOperandTestParams> TEST_VALUES_FDIV = zip_helper(TEST_VALUES_FDIV_OUT);
713
714class AluFDivTraceGenerationTest : public AluTraceGenerationTest,
715 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
716
717INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluFDivTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_FDIV));
718
719TEST_P(AluFDivTraceGenerationTest, TraceGenerationFDiv)
720{
721 auto [a, b, c] = GetParam();
722 a = MemoryValue::from_tag(MemoryTag::FF, a);
723 b = MemoryValue::from_tag(MemoryTag::FF, b);
724 c = MemoryValue::from_tag(MemoryTag::FF, c);
725 auto tag = a.get_tag();
726
727 bool div_0_error = b.as_ff() == FF(0);
728
729 builder.process(
730 {
731 { .operation = AluOperation::FDIV,
732 .a = a,
733 .b = b,
734 .c = c,
735 .error = div_0_error ? std::make_optional(simulation::AluError::DIV_0_ERROR) : std::nullopt },
736 },
737 trace);
738
739 EXPECT_THAT(trace.as_rows(),
740 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
741 ROW_FIELD_EQ(alu_sel, 1),
742 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
743 ROW_FIELD_EQ(alu_ia, a),
744 ROW_FIELD_EQ(alu_ib, b),
745 ROW_FIELD_EQ(alu_ic, c),
746 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
747 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
748 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
749 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
750 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
751 ROW_FIELD_EQ(alu_sel_is_u128, 0),
752 ROW_FIELD_EQ(alu_sel_is_ff, 1),
753 ROW_FIELD_EQ(alu_tag_ff_diff_inv, 0),
754 ROW_FIELD_EQ(alu_sel_div_0_err, div_0_error ? 1 : 0),
755 ROW_FIELD_EQ(alu_sel_tag_err, 0),
756 ROW_FIELD_EQ(alu_sel_err, div_0_error ? 1 : 0),
757 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
758}
759
760TEST_F(AluTraceGenerationTest, TraceGenerationFDivTagError)
761{
762 // Tests two cases unique to FDIV:
763 // a. inputs are both matching non-FF => should have a tag error (FF_TAG_ERR)
764 // b. input a is non-FF, b is FF => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
765 builder.process(
766 {
767 { .operation = AluOperation::FDIV,
768 .a = MemoryValue::from<uint128_t>(6),
769 .b = MemoryValue::from<uint128_t>(3),
770 .c = MemoryValue::from<uint128_t>(2),
771 .error = AluError::TAG_ERROR },
772 { .operation = AluOperation::FDIV,
773 .a = MemoryValue::from<uint64_t>(6),
774 .b = MemoryValue::from<FF>(3),
775 .c = MemoryValue::from<uint64_t>(2),
776 .error = AluError::TAG_ERROR },
777 },
778 trace);
779
780 auto u128_tag = static_cast<uint8_t>(MemoryTag::U128);
781 auto u64_tag = static_cast<uint8_t>(MemoryTag::U64);
782
783 EXPECT_THAT(
784 trace.as_rows(),
785 ElementsAre(
786 AllOf(ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
787 ROW_FIELD_EQ(alu_sel, 1),
788 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
789 ROW_FIELD_EQ(alu_ia, 6),
790 ROW_FIELD_EQ(alu_ib, 3),
791 ROW_FIELD_EQ(alu_ic, 2),
792 ROW_FIELD_EQ(alu_ia_tag, u128_tag),
793 ROW_FIELD_EQ(alu_ib_tag, u128_tag),
794 ROW_FIELD_EQ(alu_ic_tag, u128_tag),
795 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
796 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U128)),
797 ROW_FIELD_EQ(alu_sel_is_ff, 0),
798 ROW_FIELD_EQ(alu_tag_ff_diff_inv, (FF(u128_tag) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
799 ROW_FIELD_EQ(alu_sel_div_0_err, 0),
800 ROW_FIELD_EQ(alu_sel_tag_err, 1),
801 ROW_FIELD_EQ(alu_sel_err, 1),
802 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
803 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
804 AllOf(
805 ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
806 ROW_FIELD_EQ(alu_sel, 1),
807 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
808 ROW_FIELD_EQ(alu_ia, 6),
809 ROW_FIELD_EQ(alu_ib, 3),
810 ROW_FIELD_EQ(alu_ic, 2),
811 ROW_FIELD_EQ(alu_helper1, 0),
812 ROW_FIELD_EQ(alu_ia_tag, u64_tag),
813 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
814 ROW_FIELD_EQ(alu_ic_tag, u64_tag),
815 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U64)),
816 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U64)),
817 ROW_FIELD_EQ(alu_sel_is_ff, 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 { .operation = AluOperation::FDIV,
831 .a = MemoryValue::from<FF>(6),
832 .b = MemoryValue::from<FF>(0), // c is optional
833 .error = AluError::DIV_0_ERROR },
834 },
835 trace);
836
837 auto tag = static_cast<uint8_t>(MemoryTag::FF);
838
839 EXPECT_THAT(trace.as_rows(),
840 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
841 ROW_FIELD_EQ(alu_sel, 1),
842 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
843 ROW_FIELD_EQ(alu_ia, 6),
844 ROW_FIELD_EQ(alu_ib, 0),
845 ROW_FIELD_EQ(alu_ia_tag, tag),
846 ROW_FIELD_EQ(alu_ib_tag, tag),
847 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
848 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
849 ROW_FIELD_EQ(alu_sel_is_u128, 0),
850 ROW_FIELD_EQ(alu_sel_is_ff, 1),
851 ROW_FIELD_EQ(alu_tag_ff_diff_inv, 0),
852 ROW_FIELD_EQ(alu_sel_div_0_err, 1),
853 ROW_FIELD_EQ(alu_sel_tag_err, 0),
854 ROW_FIELD_EQ(alu_sel_err, 1),
855 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
856}
857
858// EQ TESTS
859
860const std::vector<MemoryValue> TEST_VALUES_EQ_OUT = {
861 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
862 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
863 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
864 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
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),
868};
869
870const std::vector<ThreeOperandTestParams> TEST_VALUES_EQ = zip_helper(TEST_VALUES_EQ_OUT);
871
872class AluEQTraceGenerationTest : public AluTraceGenerationTest,
873 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
874
875INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluEQTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_EQ));
876
877TEST_P(AluEQTraceGenerationTest, TraceGenerationEQ)
878{
879 auto [a, _b, _c] = GetParam();
880 auto tag = a.get_tag();
881
882 builder.process(
883 {
884 {
885 .operation = AluOperation::EQ,
886 .a = a,
887 .b = a,
888 .c = MemoryValue::from_tag(MemoryTag::U1, 1),
889 },
890 },
891 trace);
892
893 EXPECT_THAT(trace.as_rows(),
894 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_eq, 1),
895 ROW_FIELD_EQ(alu_sel, 1),
896 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_EQ),
897 ROW_FIELD_EQ(alu_ia, a),
898 ROW_FIELD_EQ(alu_ib, a),
899 ROW_FIELD_EQ(alu_ic, 1),
900 ROW_FIELD_EQ(alu_helper1, 0),
901 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
902 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
903 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
904 ROW_FIELD_EQ(alu_sel_tag_err, 0),
905 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
906}
907
908TEST_P(AluEQTraceGenerationTest, TraceGenerationInEQ)
909{
910 auto [a, b, c] = GetParam();
911 auto tag = a.get_tag();
912
913 builder.process(
914 {
915 {
916 .operation = AluOperation::EQ,
917 .a = a,
918 .b = b,
919 .c = c,
920 },
921 },
922 trace);
923
924 EXPECT_THAT(trace.as_rows(),
925 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_eq, 1),
926 ROW_FIELD_EQ(alu_sel, 1),
927 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_EQ),
928 ROW_FIELD_EQ(alu_ia, a),
929 ROW_FIELD_EQ(alu_ib, b),
930 ROW_FIELD_EQ(alu_ic, c),
931 ROW_FIELD_EQ(alu_ab_diff_inv, c.as_ff() == 1 ? 0 : (a.as_ff() - b.as_ff()).invert()),
932 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
933 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
934 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
935 ROW_FIELD_EQ(alu_sel_tag_err, 0),
936 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
937}
938
939// LT TESTS
940
941const std::vector<MemoryValue> TEST_VALUES_LT_OUT = {
942 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
943 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
944 MemoryValue::from_tag(MemoryTag::U1, 1), MemoryValue::from_tag(MemoryTag::U1, 0),
945 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
946 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
947 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
948 MemoryValue::from_tag(MemoryTag::U1, 0),
949};
950
951const std::vector<ThreeOperandTestParams> TEST_VALUES_LT = zip_helper(TEST_VALUES_LT_OUT);
952
953class AluLTTraceGenerationTest : public AluTraceGenerationTest,
954 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
955
956INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluLTTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_LT));
957
958TEST_P(AluLTTraceGenerationTest, TraceGenerationLT)
959{
960 auto [a, b, c] = GetParam();
961 auto tag = a.get_tag();
962 bool is_ff = tag == MemoryTag::FF;
963 builder.process(
964 {
965 { .operation = AluOperation::LT, .a = a, .b = b, .c = c },
966 },
967 trace);
968
969 EXPECT_THAT(trace.as_rows(),
970 ElementsAre(AllOf(
971 ROW_FIELD_EQ(alu_sel_op_lt, 1),
972 ROW_FIELD_EQ(alu_sel_lt_ops, 1),
973 ROW_FIELD_EQ(alu_sel, 1),
974 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_LT),
975 ROW_FIELD_EQ(alu_ia, a),
976 ROW_FIELD_EQ(alu_ib, b),
977 ROW_FIELD_EQ(alu_ic, c),
978 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
979 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
980 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
981 ROW_FIELD_EQ(alu_cf, 0),
982 ROW_FIELD_EQ(alu_lt_ops_input_a, b),
983 ROW_FIELD_EQ(alu_lt_ops_input_b, a),
984 ROW_FIELD_EQ(alu_lt_ops_result_c, c),
985 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
986 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
987 ROW_FIELD_EQ(alu_sel_is_ff, is_ff ? 1 : 0),
988 ROW_FIELD_EQ(alu_sel_ff_lt_ops, is_ff ? 1 : 0),
989 ROW_FIELD_EQ(alu_sel_int_lt_ops, is_ff ? 0 : 1),
990 ROW_FIELD_EQ(
991 alu_tag_ff_diff_inv,
992 is_ff ? 0 : (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
993 ROW_FIELD_EQ(alu_sel_tag_err, 0),
994 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
995}
996
997// LTE TESTS
998
999const std::vector<MemoryValue> TEST_VALUES_LTE_OUT = {
1000 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
1001 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
1002 MemoryValue::from_tag(MemoryTag::U1, 1), MemoryValue::from_tag(MemoryTag::U1, 0),
1003 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
1004 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
1005 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
1006 MemoryValue::from_tag(MemoryTag::U1, 0),
1007};
1008
1009const std::vector<ThreeOperandTestParams> TEST_VALUES_LTE = zip_helper(TEST_VALUES_LTE_OUT);
1010
1011class AluLTETraceGenerationTest : public AluTraceGenerationTest,
1012 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
1013
1014INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluLTETraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_LTE));
1015
1016TEST_P(AluLTETraceGenerationTest, TraceGenerationLTE)
1017{
1018 auto [a, b, c] = GetParam();
1019 auto tag = a.get_tag();
1020 bool is_ff = tag == MemoryTag::FF;
1021 builder.process(
1022 {
1023 { .operation = AluOperation::LTE, .a = a, .b = b, .c = c },
1024 },
1025 trace);
1026
1027 EXPECT_THAT(trace.as_rows(),
1028 ElementsAre(AllOf(
1029 ROW_FIELD_EQ(alu_sel_op_lte, 1),
1030 ROW_FIELD_EQ(alu_sel_lt_ops, 1),
1031 ROW_FIELD_EQ(alu_sel, 1),
1032 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_LTE),
1033 ROW_FIELD_EQ(alu_ia, a),
1034 ROW_FIELD_EQ(alu_ib, b),
1035 ROW_FIELD_EQ(alu_ic, c),
1036 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1037 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1038 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
1039 ROW_FIELD_EQ(alu_cf, 0),
1040 ROW_FIELD_EQ(alu_lt_ops_input_a, a),
1041 ROW_FIELD_EQ(alu_lt_ops_input_b, b),
1042 ROW_FIELD_EQ(alu_lt_ops_result_c, c.as_ff() == 1 ? 0 : 1),
1043 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
1044 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1045 ROW_FIELD_EQ(alu_sel_is_ff, is_ff ? 1 : 0),
1046 ROW_FIELD_EQ(alu_sel_ff_lt_ops, is_ff ? 1 : 0),
1047 ROW_FIELD_EQ(alu_sel_int_lt_ops, is_ff ? 0 : 1),
1048 ROW_FIELD_EQ(
1049 alu_tag_ff_diff_inv,
1050 is_ff ? 0 : (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
1051 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1052 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
1053}
1054
1055// NOT Opcode TESTS
1056
1057const std::vector<MemoryValue> TEST_VALUES_NOT = split_helper(TEST_VALUES_IN);
1058
1059class AluNOTTraceGenerationTest : public AluTraceGenerationTest, public ::testing::WithParamInterface<MemoryValue> {};
1060
1061INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluNOTTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_NOT));
1062
1063TEST_P(AluNOTTraceGenerationTest, TraceGenerationNOT)
1064{
1065 auto a = GetParam();
1066 auto tag = a.get_tag();
1067 bool is_ff = tag == MemoryTag::FF;
1068 auto b = is_ff ? MemoryValue::from_tag(MemoryTag::FF, 0) : ~a;
1069
1070 builder.process(
1071 {
1072 { .operation = AluOperation::NOT,
1073 .a = a,
1074 .b = b,
1075 .error = is_ff ? std::make_optional(simulation::AluError::TAG_ERROR) : std::nullopt },
1076 },
1077 trace);
1078
1079 EXPECT_THAT(trace.as_rows(),
1080 ElementsAre(AllOf(
1081 ROW_FIELD_EQ(alu_sel_op_not, 1),
1082 ROW_FIELD_EQ(alu_sel, 1),
1083 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_NOT),
1084 ROW_FIELD_EQ(alu_ia, a),
1085 ROW_FIELD_EQ(alu_ib, b),
1086 ROW_FIELD_EQ(alu_ic, 0),
1087 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1088 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1089 ROW_FIELD_EQ(alu_ic_tag, 0),
1090 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1091 ROW_FIELD_EQ(alu_sel_is_ff, is_ff ? 1 : 0),
1092 ROW_FIELD_EQ(
1093 alu_tag_ff_diff_inv,
1094 is_ff ? 0 : (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
1095 ROW_FIELD_EQ(alu_sel_tag_err, is_ff ? 1 : 0),
1096 ROW_FIELD_EQ(alu_sel_err, is_ff ? 1 : 0))));
1097}
1098
1099// SHL TESTS
1100
1101const std::vector<MemoryValue> TEST_VALUES_SHL_OUT = {
1102 MemoryValue::from_tag(MemoryTag::U1, 1),
1103 MemoryValue::from_tag(MemoryTag::U1, 0),
1104 MemoryValue::from_tag(MemoryTag::U8, 0),
1105 MemoryValue::from_tag(MemoryTag::U8, 0),
1106 MemoryValue::from_tag(MemoryTag::U16, 0),
1107 MemoryValue::from_tag(MemoryTag::U16, 0),
1108 MemoryValue::from_tag(MemoryTag::U32, 0xfffffec0),
1109 MemoryValue::from_tag(MemoryTag::U32, 0xb0000000),
1110 MemoryValue::from_tag(MemoryTag::U64, 0xfffffffffffffec0ULL),
1111 MemoryValue::from_tag(MemoryTag::U64, 0xb000000000000000ULL),
1112 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 320), // 0xfffffffffffffffffffffffffffffec0
1113 MemoryValue::from_tag(MemoryTag::U128, 0),
1114};
1115
1116const std::vector<ThreeOperandTestParams> TEST_VALUES_SHL = zip_helper(TEST_VALUES_SHL_OUT);
1117
1118class AluShlTraceGenerationTest : public AluTraceGenerationTest,
1119 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
1120
1121INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluShlTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_SHL));
1122
1123TEST_P(AluShlTraceGenerationTest, TraceGenerationShl)
1124{
1125 auto [a, b, c] = GetParam();
1126 auto tag = a.get_tag();
1127 auto tag_bits = get_tag_bits(tag);
1128 auto b_num = static_cast<uint128_t>(b.as_ff());
1129
1130 auto overflow = b_num > tag_bits;
1131 uint128_t shift_lo_bits = overflow ? tag_bits : tag_bits - b_num;
1132 uint128_t shift_hi_bits = overflow ? tag_bits : b_num;
1133 auto two_pow_shift_lo_bits = static_cast<uint128_t>(1) << shift_lo_bits;
1134 auto a_lo = overflow ? b_num - tag_bits : static_cast<uint128_t>(a.as_ff()) % two_pow_shift_lo_bits;
1135 auto a_hi = static_cast<uint128_t>(a.as_ff()) >> shift_lo_bits;
1136
1137 builder.process({ {
1138 .operation = AluOperation::SHL,
1139 .a = a,
1140 .b = b,
1141 .c = c,
1142 } },
1143 trace);
1144
1145 EXPECT_THAT(trace.as_rows(),
1146 ElementsAre(AllOf(
1147 ROW_FIELD_EQ(alu_sel_op_shl, 1),
1148 ROW_FIELD_EQ(alu_sel, 1),
1149 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHL),
1150 ROW_FIELD_EQ(alu_ia, a),
1151 ROW_FIELD_EQ(alu_a_hi, a_hi),
1152 ROW_FIELD_EQ(alu_a_hi_bits, shift_hi_bits),
1153 ROW_FIELD_EQ(alu_a_lo, a_lo),
1154 ROW_FIELD_EQ(alu_a_lo_bits, shift_lo_bits),
1155 ROW_FIELD_EQ(alu_ib, b),
1156 ROW_FIELD_EQ(alu_ic, c),
1157 ROW_FIELD_EQ(alu_helper1, static_cast<uint128_t>(1) << b_num),
1158 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1159 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1160 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
1161 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
1162 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1163 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
1164 ROW_FIELD_EQ(alu_sel_is_ff, 0),
1165 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
1166 (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
1167 ROW_FIELD_EQ(alu_sel_shift_ops, 1),
1168 ROW_FIELD_EQ(alu_sel_shift_ops_no_overflow, overflow ? 0 : 1),
1169 ROW_FIELD_EQ(alu_shift_lo_bits, shift_lo_bits),
1170 ROW_FIELD_EQ(alu_two_pow_shift_lo_bits, two_pow_shift_lo_bits),
1171 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1172 ROW_FIELD_EQ(alu_sel_err, 0),
1173 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
1174}
1175
1176TEST_F(AluShlTraceGenerationTest, TraceGenerationShlTagError)
1177{
1178 // Tests two cases:
1179 // a. inputs are both FF => should have a tag error (FF_TAG_ERR)
1180 // b. input a is FF, b is not => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
1181 builder.process(
1182 {
1183 { .operation = AluOperation::SHL,
1184 .a = MemoryValue::from<FF>(6),
1185 .b = MemoryValue::from<FF>(3),
1186 .c = MemoryValue::from<FF>(48),
1187 .error = AluError::TAG_ERROR },
1188 { .operation = AluOperation::SHL,
1189 .a = MemoryValue::from<FF>(6),
1190 .b = MemoryValue::from<uint128_t>(3),
1191 .c = MemoryValue::from<FF>(48),
1192 .error = AluError::TAG_ERROR },
1193 },
1194 trace);
1195
1196 EXPECT_THAT(trace.as_rows(),
1197 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_shl, 1),
1198 ROW_FIELD_EQ(alu_sel, 1),
1199 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHL),
1200 ROW_FIELD_EQ(alu_ia, 6),
1201 ROW_FIELD_EQ(alu_ib, 3),
1202 ROW_FIELD_EQ(alu_ic, 48),
1203 ROW_FIELD_EQ(alu_helper1, 8),
1204 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1205 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
1206 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1207 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1208 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1209 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1210 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1211 ROW_FIELD_EQ(alu_sel_err, 1),
1212 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
1213 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
1214 AllOf(ROW_FIELD_EQ(alu_sel_op_shl, 1),
1215 ROW_FIELD_EQ(alu_sel, 1),
1216 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHL),
1217 ROW_FIELD_EQ(alu_ia, 6),
1218 ROW_FIELD_EQ(alu_ib, 3),
1219 ROW_FIELD_EQ(alu_ic, 48),
1220 ROW_FIELD_EQ(alu_helper1, 8),
1221 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1222 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
1223 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1224 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1225 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1226 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1227 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
1228 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1229 ROW_FIELD_EQ(alu_sel_err, 1),
1230 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
1231 ROW_FIELD_EQ(alu_ab_tags_diff_inv,
1232 (FF(static_cast<uint8_t>(MemoryTag::FF)) -
1233 FF(static_cast<uint8_t>(MemoryTag::U128)))
1234 .invert()))));
1235}
1236
1237// SHR TESTS
1238
1239const std::vector<MemoryValue> TEST_VALUES_SHR_OUT = {
1240 MemoryValue::from_tag(MemoryTag::U1, 1),
1241 MemoryValue::from_tag(MemoryTag::U1, 0),
1242 MemoryValue::from_tag(MemoryTag::U8, 0),
1243 MemoryValue::from_tag(MemoryTag::U8, 0),
1244 MemoryValue::from_tag(MemoryTag::U16, 0),
1245 MemoryValue::from_tag(MemoryTag::U16, 0),
1246 MemoryValue::from_tag(MemoryTag::U32, 0x7ffffff),
1247 MemoryValue::from_tag(MemoryTag::U32, 0x0000001f),
1248 MemoryValue::from_tag(MemoryTag::U64, 0x7ffffffffffffffULL),
1249 MemoryValue::from_tag(MemoryTag::U64, 0x000000000000001fULL),
1250 MemoryValue::from_tag(MemoryTag::U128,
1251 (uint256_t(1) << 128) - 1 - (uint256_t(248) << 120)), // 0x7ffffffffffffffffffffffffffffff
1252 MemoryValue::from_tag(MemoryTag::U128, 0x000000000000001fULL),
1253};
1254
1255const std::vector<ThreeOperandTestParams> TEST_VALUES_SHR = zip_helper(TEST_VALUES_SHR_OUT);
1256
1257class AluShrTraceGenerationTest : public AluTraceGenerationTest,
1258 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
1259
1260INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluShrTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_SHR));
1261
1262TEST_P(AluShrTraceGenerationTest, TraceGenerationShr)
1263{
1264 auto [a, b, c] = GetParam();
1265 auto tag = a.get_tag();
1266 auto tag_bits = get_tag_bits(tag);
1267 auto b_num = static_cast<uint128_t>(b.as_ff());
1268
1269 auto overflow = b_num > tag_bits;
1270 uint128_t shift_lo_bits = overflow ? tag_bits : b_num;
1271 uint128_t shift_hi_bits = overflow ? tag_bits : tag_bits - b_num;
1272 auto two_pow_shift_lo_bits = static_cast<uint128_t>(1) << shift_lo_bits;
1273 auto a_lo = overflow ? b_num - tag_bits : static_cast<uint128_t>(a.as_ff()) % two_pow_shift_lo_bits;
1274 auto a_hi = static_cast<uint128_t>(a.as_ff()) >> shift_lo_bits;
1275
1276 builder.process({ {
1277 .operation = AluOperation::SHR,
1278 .a = a,
1279 .b = b,
1280 .c = c,
1281 } },
1282 trace);
1283
1284 EXPECT_THAT(trace.as_rows(),
1285 ElementsAre(AllOf(
1286 ROW_FIELD_EQ(alu_sel_op_shr, 1),
1287 ROW_FIELD_EQ(alu_sel, 1),
1288 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHR),
1289 ROW_FIELD_EQ(alu_ia, a),
1290 ROW_FIELD_EQ(alu_a_hi, a_hi),
1291 ROW_FIELD_EQ(alu_a_hi_bits, shift_hi_bits),
1292 ROW_FIELD_EQ(alu_a_lo, a_lo),
1293 ROW_FIELD_EQ(alu_a_lo_bits, shift_lo_bits),
1294 ROW_FIELD_EQ(alu_ib, b),
1295 ROW_FIELD_EQ(alu_ic, c),
1296 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1297 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1298 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
1299 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
1300 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1301 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
1302 ROW_FIELD_EQ(alu_sel_is_ff, 0),
1303 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
1304 (FF(static_cast<uint8_t>(tag)) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
1305 ROW_FIELD_EQ(alu_sel_shift_ops, 1),
1306 ROW_FIELD_EQ(alu_sel_shift_ops_no_overflow, overflow ? 0 : 1),
1307 ROW_FIELD_EQ(alu_shift_lo_bits, shift_lo_bits),
1308 ROW_FIELD_EQ(alu_two_pow_shift_lo_bits, two_pow_shift_lo_bits),
1309 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1310 ROW_FIELD_EQ(alu_sel_err, 0),
1311 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
1312}
1313
1314TEST_F(AluShrTraceGenerationTest, TraceGenerationShrTagError)
1315{
1316 // Tests two cases:
1317 // a. inputs are both FF => should have a tag error (FF_TAG_ERR)
1318 // b. input a is FF, b is not => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
1319 builder.process(
1320 {
1321 { .operation = AluOperation::SHR,
1322 .a = MemoryValue::from<FF>(6),
1323 .b = MemoryValue::from<FF>(3),
1324 .c = MemoryValue::from<FF>(0),
1325 .error = AluError::TAG_ERROR },
1326 { .operation = AluOperation::SHR,
1327 .a = MemoryValue::from<FF>(6),
1328 .b = MemoryValue::from<uint128_t>(3),
1329 .c = MemoryValue::from<FF>(0),
1330 .error = AluError::TAG_ERROR },
1331 },
1332 trace);
1333
1334 EXPECT_THAT(trace.as_rows(),
1335 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_shr, 1),
1336 ROW_FIELD_EQ(alu_sel, 1),
1337 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHR),
1338 ROW_FIELD_EQ(alu_ia, 6),
1339 ROW_FIELD_EQ(alu_ib, 3),
1340 ROW_FIELD_EQ(alu_ic, 0),
1341 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1342 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
1343 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1344 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1345 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1346 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1347 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1348 ROW_FIELD_EQ(alu_sel_err, 1),
1349 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
1350 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
1351 AllOf(ROW_FIELD_EQ(alu_sel_op_shr, 1),
1352 ROW_FIELD_EQ(alu_sel, 1),
1353 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHR),
1354 ROW_FIELD_EQ(alu_ia, 6),
1355 ROW_FIELD_EQ(alu_ib, 3),
1356 ROW_FIELD_EQ(alu_ic, 0),
1357 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1358 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
1359 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1360 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1361 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1362 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1363 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
1364 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1365 ROW_FIELD_EQ(alu_sel_err, 1),
1366 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
1367 ROW_FIELD_EQ(alu_ab_tags_diff_inv,
1368 (FF(static_cast<uint8_t>(MemoryTag::FF)) -
1369 FF(static_cast<uint8_t>(MemoryTag::U128)))
1370 .invert()))));
1371}
1372
1373// TRUNCATE operation (SET/CAST opcodes)
1374
1375// Truncation is a special case as we always have FF TaggedValue inputs:
1376struct TruncateTrivialTestParams {
1377 MemoryValue a;
1378 MemoryTag dst_tag;
1379 FF expected_result;
1380};
1381
1382const std::vector<TruncateTrivialTestParams> TRUNCATE_TRIVIAL_TEST_PARAMS = {
1383 {
1384 .a = MemoryValue::from_tag(MemoryTag::FF, 1),
1385 .dst_tag = MemoryTag::U1,
1386 .expected_result = 1,
1387 },
1388 {
1389 .a = MemoryValue::from_tag(MemoryTag::FF, 7),
1390 .dst_tag = MemoryTag::U8,
1391 .expected_result = 7,
1392 },
1393 {
1394 .a = MemoryValue::from_tag(MemoryTag::U32, 123456789),
1395 .dst_tag = MemoryTag::U32,
1396 .expected_result = 123456789,
1397 },
1398 {
1399 .a = MemoryValue::from_tag(MemoryTag::U128, 1234567890123456789ULL),
1400 .dst_tag = MemoryTag::U64,
1401 .expected_result = 1234567890123456789ULL,
1402 },
1403 {
1404 .a = MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 127) + 982739482),
1405 .dst_tag = MemoryTag::U128,
1406 .expected_result = (uint256_t(1) << 127) + 982739482,
1407 },
1408 {
1409 .a = MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 1),
1410 .dst_tag = MemoryTag::FF,
1411 .expected_result = FF::modulus - 1,
1412 },
1413};
1414
1415class AluTruncateTrivialTraceGenerationTest : public AluTraceGenerationTest,
1416 public ::testing::WithParamInterface<TruncateTrivialTestParams> {};
1417
1418INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest,
1419 AluTruncateTrivialTraceGenerationTest,
1420 ::testing::ValuesIn(TRUNCATE_TRIVIAL_TEST_PARAMS));
1421
1422TEST_P(AluTruncateTrivialTraceGenerationTest, TraceGenerationTruncateTrivial)
1423{
1424 auto [a, dst_tag, expected_result] = GetParam();
1425 auto b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(dst_tag));
1426 auto c = MemoryValue::from_tag(dst_tag, expected_result);
1427
1428 builder.process(
1429 {
1430 { .operation = AluOperation::TRUNCATE, .a = a, .b = b, .c = c },
1431 },
1432 trace);
1433
1434 EXPECT_THAT(trace.as_rows(),
1435 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_truncate, 1),
1436 ROW_FIELD_EQ(alu_sel_trunc_trivial, 1),
1437 ROW_FIELD_EQ(alu_sel_trunc_lt_128, 0),
1438 ROW_FIELD_EQ(alu_sel_trunc_gte_128, 0),
1439 ROW_FIELD_EQ(alu_sel_trunc_non_trivial, 0),
1440 ROW_FIELD_EQ(alu_sel, 1),
1441 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_TRUNCATE),
1442 ROW_FIELD_EQ(alu_ia, a),
1443 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(dst_tag)),
1444 ROW_FIELD_EQ(alu_ic, expected_result),
1445 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(dst_tag)),
1446 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(dst_tag)),
1447 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1448 ROW_FIELD_EQ(alu_a_lo, 0),
1449 ROW_FIELD_EQ(alu_a_hi, 0),
1450 ROW_FIELD_EQ(alu_mid, 0),
1451 ROW_FIELD_EQ(alu_mid_bits, 0))));
1452}
1453
1454struct TruncateNonTrivialTestParams {
1455 MemoryValue a;
1456 MemoryTag dst_tag;
1457 FF expected_result;
1458 FF expected_lo_128;
1459 FF expected_hi_128;
1460 FF expected_mid;
1461};
1462
1463const std::vector<TruncateNonTrivialTestParams> TRUNCATE_LESS_THAN_128_TEST_PARAMS = {
1464 {
1465 .a = MemoryValue::from_tag(MemoryTag::U128, (uint256_t(98263) << 64) + 123456789987654321ULL),
1466 .dst_tag = MemoryTag::U64,
1467 .expected_result = 123456789987654321ULL,
1468 .expected_lo_128 = (uint256_t(98263) << 64) + 123456789987654321ULL,
1469 .expected_hi_128 = 0,
1470 .expected_mid = 98263,
1471 },
1472 {
1473 .a = MemoryValue::from_tag(MemoryTag::U64, (uint256_t(98263) << 32) + 1234567ULL),
1474 .dst_tag = MemoryTag::U32,
1475 .expected_result = 1234567,
1476 .expected_lo_128 = (98263ULL << 32) + 1234567ULL,
1477 .expected_hi_128 = 0,
1478 .expected_mid = 98263,
1479 },
1480 {
1481 .a = MemoryValue::from_tag(MemoryTag::U64, (uint256_t(98263) << 32) + 1234ULL),
1482 .dst_tag = MemoryTag::U16,
1483 .expected_result = 1234,
1484 .expected_lo_128 = (98263ULL << 32) + 1234ULL,
1485 .expected_hi_128 = 0,
1486 .expected_mid = 98263ULL << 16,
1487 },
1488 {
1489 .a = MemoryValue::from_tag(MemoryTag::FF, 263),
1490 .dst_tag = MemoryTag::U8,
1491 .expected_result = 7,
1492 .expected_lo_128 = 263,
1493 .expected_hi_128 = 0,
1494 .expected_mid = 1,
1495 },
1496 {
1497 .a = MemoryValue::from_tag(MemoryTag::U64, 999),
1498 .dst_tag = MemoryTag::U1,
1499 .expected_result = 1,
1500 .expected_lo_128 = 999,
1501 .expected_hi_128 = 0,
1502 .expected_mid = 499,
1503 }
1504};
1505
1506class AluTruncateNonTrivialLT128TraceGenerationTest
1507 : public AluTraceGenerationTest,
1508 public ::testing::WithParamInterface<TruncateNonTrivialTestParams> {};
1509
1510INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest,
1511 AluTruncateNonTrivialLT128TraceGenerationTest,
1512 ::testing::ValuesIn(TRUNCATE_LESS_THAN_128_TEST_PARAMS));
1513
1514TEST_P(AluTruncateNonTrivialLT128TraceGenerationTest, TraceGenerationTruncateNonTrivialLT128)
1515{
1516 auto [a, dst_tag, expected_result, expected_lo_128, expected_hi_128, expected_mid] = GetParam();
1517 auto b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(dst_tag));
1518 auto c = MemoryValue::from_tag(dst_tag, expected_result);
1519
1520 builder.process(
1521 {
1522 { .operation = AluOperation::TRUNCATE, .a = a, .b = b, .c = c },
1523 },
1524 trace);
1525
1526 EXPECT_THAT(trace.as_rows(),
1527 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_truncate, 1),
1528 ROW_FIELD_EQ(alu_sel_trunc_trivial, 0),
1529 ROW_FIELD_EQ(alu_sel_trunc_lt_128, 1),
1530 ROW_FIELD_EQ(alu_sel_trunc_gte_128, 0),
1531 ROW_FIELD_EQ(alu_sel_trunc_non_trivial, 1),
1532 ROW_FIELD_EQ(alu_sel, 1),
1533 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_TRUNCATE),
1534 ROW_FIELD_EQ(alu_ia, a),
1535 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(dst_tag)),
1536 ROW_FIELD_EQ(alu_ic, expected_result),
1537 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(dst_tag)),
1538 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(dst_tag)),
1539 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1540 ROW_FIELD_EQ(alu_a_lo, expected_lo_128),
1541 ROW_FIELD_EQ(alu_a_hi, expected_hi_128),
1542 ROW_FIELD_EQ(alu_mid, expected_mid),
1543 ROW_FIELD_EQ(alu_mid_bits, 128 - get_tag_bits(dst_tag)))));
1544}
1545
1546const std::vector<TruncateNonTrivialTestParams> TRUNCATE_GREATER_THAN_128_TEST_PARAMS = {
1547 {
1548 .a = MemoryValue::from<FF>((uint256_t(98263) << 128) + (uint256_t(1111) << 64) + 123456789987654321ULL),
1549 .dst_tag = MemoryTag::U64,
1550 .expected_result = 123456789987654321ULL,
1551 .expected_lo_128 = (uint256_t(1111) << 64) + 123456789987654321ULL,
1552 .expected_hi_128 = 98263,
1553 .expected_mid = 1111,
1554 },
1555 {
1556 .a = MemoryValue::from<FF>((uint256_t(98263) << 128) + (uint256_t(1111) << 64) + 123456789),
1557 .dst_tag = MemoryTag::U32,
1558 .expected_result = 123456789,
1559 .expected_lo_128 = (uint256_t(1111) << 64) + 123456789,
1560 .expected_hi_128 = 98263,
1561 .expected_mid = 1111ULL << 32,
1562 },
1563 {
1564 .a = MemoryValue::from<FF>((uint256_t(98263) << 128) + (uint256_t(1111) << 64) + 1234),
1565 .dst_tag = MemoryTag::U16,
1566 .expected_result = 1234,
1567 .expected_lo_128 = (uint256_t(1111) << 64) + 1234,
1568 .expected_hi_128 = 98263,
1569 .expected_mid = 1111ULL << 48,
1570 },
1571 {
1572 .a = MemoryValue::from<FF>((uint256_t(98263) << 150) + (uint256_t(123456789987654321ULL) << 8) + 234),
1573 .dst_tag = MemoryTag::U8,
1574 .expected_result = 234,
1575 .expected_lo_128 = (uint256_t(123456789987654321ULL) << 8) + 234,
1576 .expected_hi_128 = 98263ULL << 22,
1577 .expected_mid = 123456789987654321ULL,
1578 }
1579};
1580
1581class AluTruncateNonTrivialGT128TraceGenerationTest
1582 : public AluTraceGenerationTest,
1583 public ::testing::WithParamInterface<TruncateNonTrivialTestParams> {};
1584
1585INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest,
1586 AluTruncateNonTrivialGT128TraceGenerationTest,
1587 ::testing::ValuesIn(TRUNCATE_GREATER_THAN_128_TEST_PARAMS));
1588
1589TEST_P(AluTruncateNonTrivialGT128TraceGenerationTest, TraceGenerationTruncateNonTrivialGT128)
1590{
1591 auto [a, dst_tag, expected_result, expected_lo_128, expected_hi_128, expected_mid] = GetParam();
1592 auto b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(dst_tag));
1593 auto c = MemoryValue::from_tag(dst_tag, expected_result);
1594
1595 builder.process(
1596 {
1597 { .operation = AluOperation::TRUNCATE, .a = a, .b = b, .c = c },
1598 },
1599 trace);
1600
1601 EXPECT_THAT(trace.as_rows(),
1602 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_truncate, 1),
1603 ROW_FIELD_EQ(alu_sel_trunc_trivial, 0),
1604 ROW_FIELD_EQ(alu_sel_trunc_lt_128, 0),
1605 ROW_FIELD_EQ(alu_sel_trunc_gte_128, 1),
1606 ROW_FIELD_EQ(alu_sel_trunc_non_trivial, 1),
1607 ROW_FIELD_EQ(alu_sel, 1),
1608 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_TRUNCATE),
1609 ROW_FIELD_EQ(alu_ia, a),
1610 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(dst_tag)),
1611 ROW_FIELD_EQ(alu_ic, expected_result),
1612 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(dst_tag)),
1613 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(dst_tag)),
1614 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1615 ROW_FIELD_EQ(alu_a_lo, expected_lo_128),
1616 ROW_FIELD_EQ(alu_a_hi, expected_hi_128),
1617 ROW_FIELD_EQ(alu_mid, expected_mid),
1618 ROW_FIELD_EQ(alu_mid_bits, 128 - get_tag_bits(dst_tag)))));
1619}
1620
1621} // namespace
1622} // 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:108
alu_event.hpp
alu_trace.hpp
dst_tag
MemoryTag dst_tag
Definition alu_trace.test.cpp:1378
expected_lo_128
FF expected_lo_128
Definition alu_trace.test.cpp:1458
expected_hi_128
FF expected_hi_128
Definition alu_trace.test.cpp:1459
expected_mid
FF expected_mid
Definition alu_trace.test.cpp:1460
AVM_EXEC_OP_ID_ALU_TRUNCATE
#define AVM_EXEC_OP_ID_ALU_TRUNCATE
Definition aztec_constants.hpp:103
AVM_EXEC_OP_ID_ALU_LTE
#define AVM_EXEC_OP_ID_ALU_LTE
Definition aztec_constants.hpp:99
AVM_EXEC_OP_ID_ALU_DIV
#define AVM_EXEC_OP_ID_ALU_DIV
Definition aztec_constants.hpp:95
AVM_EXEC_OP_ID_ALU_ADD
#define AVM_EXEC_OP_ID_ALU_ADD
Definition aztec_constants.hpp:92
AVM_EXEC_OP_ID_ALU_SHL
#define AVM_EXEC_OP_ID_ALU_SHL
Definition aztec_constants.hpp:101
AVM_EXEC_OP_ID_ALU_EQ
#define AVM_EXEC_OP_ID_ALU_EQ
Definition aztec_constants.hpp:97
AVM_EXEC_OP_ID_ALU_SUB
#define AVM_EXEC_OP_ID_ALU_SUB
Definition aztec_constants.hpp:93
AVM_EXEC_OP_ID_ALU_NOT
#define AVM_EXEC_OP_ID_ALU_NOT
Definition aztec_constants.hpp:100
AVM_EXEC_OP_ID_ALU_MUL
#define AVM_EXEC_OP_ID_ALU_MUL
Definition aztec_constants.hpp:94
AVM_EXEC_OP_ID_ALU_FDIV
#define AVM_EXEC_OP_ID_ALU_FDIV
Definition aztec_constants.hpp:96
AVM_EXEC_OP_ID_ALU_SHR
#define AVM_EXEC_OP_ID_ALU_SHR
Definition aztec_constants.hpp:102
AVM_EXEC_OP_ID_ALU_LT
#define AVM_EXEC_OP_ID_ALU_LT
Definition aztec_constants.hpp:98
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)
Definition alu_trace.cpp:308
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:123
trace
TestTraceContainer trace
Definition data_copy.test.cpp:62
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
U256Decomposition decompose(const uint256_t &x)
Definition uint_decomposition.cpp:9
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::MemoryTag
ValueTag MemoryTag
Definition memory_types.hpp:9
bb::avm2::FF
AvmFlavorSettings::FF FF
Definition field.hpp:10
bb::TEST_F
TEST_F(IPATest, ChallengesAreZero)
Definition ipa.test.cpp:188
std
STL namespace.
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
tuplet::tag
std::integral_constant< size_t, I > tag
Definition tuplet.hpp:258
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< Bn254FrParams >::modulus
static constexpr uint256_t modulus
Definition field_declarations.hpp:197
test_trace_container.hpp
instruction_spec.hpp