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/alu.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/field_gt.hpp"
17#include "barretenberg/vm2/simulation/gt.hpp"
18#include "barretenberg/vm2/simulation/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) - 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(alu_tag_u128_diff_inv,
353 is_u128 ? 0 : FF(static_cast<uint8_t>(tag) - static_cast<uint8_t>(MemoryTag::U128)).invert()),
354 ROW_FIELD_EQ(alu_sel_mul_div_u128, is_u128 ? 1 : 0),
355 ROW_FIELD_EQ(alu_sel_mul_u128, is_u128 ? 1 : 0),
356 ROW_FIELD_EQ(alu_sel_tag_err, 0),
357 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
358}
359
360TEST_F(AluTraceGenerationTest, TraceGenerationMulU128)
361{
362 uint128_t u128_max = static_cast<uint128_t>(get_tag_max_value(MemoryTag::U128));
363 builder.process(
364 {
365 { .operation = AluOperation::MUL,
366 .a = MemoryValue::from<uint128_t>(2),
367 .b = MemoryValue::from<uint128_t>(3),
368 .c = MemoryValue::from<uint128_t>(6) },
369 { .operation = AluOperation::MUL,
370 .a = MemoryValue::from<uint128_t>(u128_max),
371 .b = MemoryValue::from<uint128_t>(u128_max - 2),
372 .c = MemoryValue::from<uint128_t>(3) },
373 },
374 trace);
375
376 EXPECT_THAT(trace.as_rows(),
377 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_mul, 1),
378 ROW_FIELD_EQ(alu_sel, 1),
379 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_MUL),
380 ROW_FIELD_EQ(alu_ia, 2),
381 ROW_FIELD_EQ(alu_a_hi, 0),
382 ROW_FIELD_EQ(alu_a_hi_bits, 64),
383 ROW_FIELD_EQ(alu_a_lo, 2),
384 ROW_FIELD_EQ(alu_a_lo_bits, 64),
385 ROW_FIELD_EQ(alu_ib, 3),
386 ROW_FIELD_EQ(alu_b_hi, 0),
387 ROW_FIELD_EQ(alu_b_lo, 3),
388 ROW_FIELD_EQ(alu_ic, 6),
389 ROW_FIELD_EQ(alu_c_hi, 0),
390 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
391 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
392 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
393 ROW_FIELD_EQ(alu_cf, 0),
394 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
395 ROW_FIELD_EQ(alu_max_value, u128_max),
396 ROW_FIELD_EQ(alu_constant_64, 64),
397 ROW_FIELD_EQ(alu_sel_is_u128, 1),
398 ROW_FIELD_EQ(alu_tag_u128_diff_inv, 0),
399 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
400 ROW_FIELD_EQ(alu_sel_mul_u128, 1),
401 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
402 ROW_FIELD_EQ(alu_sel_tag_err, 0),
403 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
404 AllOf(ROW_FIELD_EQ(alu_sel_op_mul, 1),
405 ROW_FIELD_EQ(alu_sel, 1),
406 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_MUL),
407 ROW_FIELD_EQ(alu_ia, u128_max),
408 ROW_FIELD_EQ(alu_a_hi, (uint256_t(1) << 64) - 1),
409 ROW_FIELD_EQ(alu_a_hi_bits, 64),
410 ROW_FIELD_EQ(alu_a_lo, (uint256_t(1) << 64) - 1),
411 ROW_FIELD_EQ(alu_a_lo_bits, 64),
412 ROW_FIELD_EQ(alu_ib, u128_max - 2),
413 ROW_FIELD_EQ(alu_b_hi, (uint256_t(1) << 64) - 1),
414 ROW_FIELD_EQ(alu_b_lo, (uint256_t(1) << 64) - 3),
415 ROW_FIELD_EQ(alu_ic, 3),
416 ROW_FIELD_EQ(alu_c_hi, (uint256_t(1) << 64) - 5),
417 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
418 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
419 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
420 ROW_FIELD_EQ(alu_cf, 1),
421 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
422 ROW_FIELD_EQ(alu_max_value, u128_max),
423 ROW_FIELD_EQ(alu_sel_is_u128, 1),
424 ROW_FIELD_EQ(alu_tag_u128_diff_inv, 0),
425 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
426 ROW_FIELD_EQ(alu_sel_mul_u128, 1),
427 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
428 ROW_FIELD_EQ(alu_sel_tag_err, 0),
429 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
430}
431
432// DIV TESTS
433
434const std::vector<MemoryValue> TEST_VALUES_DIV_OUT = {
435 MemoryValue::from_tag(MemoryTag::U1, 0), // Dividing by zero, so expecting an error
436 MemoryValue::from_tag(MemoryTag::U1, 1),
437 MemoryValue::from_tag(MemoryTag::U8, 4),
438 MemoryValue::from_tag(MemoryTag::U8, 0),
439 MemoryValue::from_tag(MemoryTag::U16, 0),
440 MemoryValue::from_tag(MemoryTag::U16, 1),
441 MemoryValue::from_tag(MemoryTag::U32, 0x33333331),
442 MemoryValue::from_tag(MemoryTag::U32, 1),
443 MemoryValue::from_tag(MemoryTag::U64, 0x3333333333333331ULL),
444 MemoryValue::from_tag(MemoryTag::U64, 1),
445 MemoryValue::from_tag(MemoryTag::U128, (((uint256_t(1) << 128) - 11) / 5)), // 0x3333333333333333333333333333331
446 MemoryValue::from_tag(MemoryTag::U128, 1),
447};
448
449const std::vector<ThreeOperandTestParams> TEST_VALUES_DIV = zip_helper(TEST_VALUES_DIV_OUT);
450
451class AluDivTraceGenerationTest : public AluTraceGenerationTest,
452 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
453
454INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluDivTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_DIV));
455
456TEST_P(AluDivTraceGenerationTest, TraceGenerationDiv)
457{
458 auto [a, b, c] = GetParam();
459 auto tag = a.get_tag();
460 bool div_0_error = b.as_ff() == FF(0);
461 bool is_u128 = tag == MemoryTag::U128;
462 builder.process(
463 {
464 { .operation = AluOperation::DIV,
465 .a = a,
466 .b = b,
467 .c = c,
468 .error = div_0_error ? std::make_optional(simulation::AluError::DIV_0_ERROR) : std::nullopt },
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_u128, is_u128 ? 1 : 0),
489 ROW_FIELD_EQ(alu_tag_u128_diff_inv,
490 is_u128 ? 0 : FF(static_cast<uint8_t>(tag) - static_cast<uint8_t>(MemoryTag::U128)).invert()),
491 ROW_FIELD_EQ(alu_sel_is_ff, 0),
492 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
493 FF(static_cast<uint8_t>(tag) - static_cast<uint8_t>(MemoryTag::FF)).invert()),
494 ROW_FIELD_EQ(alu_sel_mul_div_u128, is_u128 ? 1 : 0),
495 ROW_FIELD_EQ(alu_sel_div_no_0_err, div_0_error ? 0 : 1),
496 ROW_FIELD_EQ(alu_sel_div_0_err, div_0_error ? 1 : 0),
497 ROW_FIELD_EQ(alu_sel_tag_err, 0),
498 ROW_FIELD_EQ(alu_sel_err, div_0_error ? 1 : 0),
499 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
500}
501
502TEST_F(AluTraceGenerationTest, TraceGenerationDivU128)
503{
504 uint128_t u128_max = static_cast<uint128_t>(get_tag_max_value(MemoryTag::U128));
505 builder.process(
506 {
507 { .operation = AluOperation::DIV,
508 .a = MemoryValue::from<uint128_t>(6),
509 .b = MemoryValue::from<uint128_t>(3),
510 .c = MemoryValue::from<uint128_t>(2) },
511 { .operation = AluOperation::DIV,
512 .a = MemoryValue::from<uint128_t>(u128_max),
513 .b = MemoryValue::from<uint128_t>(u128_max - 2),
514 .c = MemoryValue::from<uint128_t>(1) },
515 },
516 trace);
517
518 EXPECT_THAT(trace.as_rows(),
519 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_div, 1),
520 ROW_FIELD_EQ(alu_sel, 1),
521 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
522 ROW_FIELD_EQ(alu_ia, 6),
523 ROW_FIELD_EQ(alu_a_hi, 0),
524 ROW_FIELD_EQ(alu_a_hi_bits, 64),
525 ROW_FIELD_EQ(alu_a_lo, 2),
526 ROW_FIELD_EQ(alu_a_lo_bits, 64),
527 ROW_FIELD_EQ(alu_ib, 3),
528 ROW_FIELD_EQ(alu_b_hi, 0),
529 ROW_FIELD_EQ(alu_b_lo, 3),
530 ROW_FIELD_EQ(alu_ic, 2),
531 ROW_FIELD_EQ(alu_helper1, 0),
532 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
533 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
534 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
535 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
536 ROW_FIELD_EQ(alu_max_value, u128_max),
537 ROW_FIELD_EQ(alu_constant_64, 64),
538 ROW_FIELD_EQ(alu_sel_is_u128, 1),
539 ROW_FIELD_EQ(alu_tag_u128_diff_inv, 0),
540 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
541 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
542 ROW_FIELD_EQ(alu_sel_div_no_0_err, 1),
543 ROW_FIELD_EQ(alu_sel_tag_err, 0),
544 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
545 AllOf(ROW_FIELD_EQ(alu_sel_op_div, 1),
546 ROW_FIELD_EQ(alu_sel, 1),
547 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
548 ROW_FIELD_EQ(alu_ia, u128_max),
549 ROW_FIELD_EQ(alu_a_hi, 0),
550 ROW_FIELD_EQ(alu_a_hi_bits, 64),
551 ROW_FIELD_EQ(alu_a_lo, 1),
552 ROW_FIELD_EQ(alu_a_lo_bits, 64),
553 ROW_FIELD_EQ(alu_ib, u128_max - 2),
554 ROW_FIELD_EQ(alu_b_hi, (uint256_t(1) << 64) - 1),
555 ROW_FIELD_EQ(alu_b_lo, (uint256_t(1) << 64) - 3),
556 ROW_FIELD_EQ(alu_ic, 1),
557 ROW_FIELD_EQ(alu_helper1, 2),
558 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::U128)),
559 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
560 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U128)),
561 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
562 ROW_FIELD_EQ(alu_max_value, u128_max),
563 ROW_FIELD_EQ(alu_sel_is_u128, 1),
564 ROW_FIELD_EQ(alu_tag_u128_diff_inv, 0),
565 ROW_FIELD_EQ(alu_sel_mul_div_u128, 1),
566 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
567 ROW_FIELD_EQ(alu_sel_div_no_0_err, 1),
568 ROW_FIELD_EQ(alu_sel_tag_err, 0),
569 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
570}
571
572TEST_F(AluTraceGenerationTest, TraceGenerationDivTagError)
573{
574 // Tests two cases:
575 // a. inputs are both FF => should have a tag error (FF_TAG_ERR)
576 // b. input a is FF, b is not => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
577 builder.process(
578 {
579 { .operation = AluOperation::DIV,
580 .a = MemoryValue::from<FF>(6),
581 .b = MemoryValue::from<FF>(3),
582 .c = MemoryValue::from<FF>(2),
583 .error = AluError::TAG_ERROR },
584 { .operation = AluOperation::DIV,
585 .a = MemoryValue::from<FF>(6),
586 .b = MemoryValue::from<uint128_t>(3),
587 .c = MemoryValue::from<FF>(2),
588 .error = AluError::TAG_ERROR },
589 },
590 trace);
591
592 EXPECT_THAT(
593 trace.as_rows(),
594 ElementsAre(
595 AllOf(
596 ROW_FIELD_EQ(alu_sel_op_div, 1),
597 ROW_FIELD_EQ(alu_sel, 1),
598 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
599 ROW_FIELD_EQ(alu_ia, 6),
600 ROW_FIELD_EQ(alu_ib, 3),
601 ROW_FIELD_EQ(alu_ic, 2),
602 ROW_FIELD_EQ(alu_helper1, 0),
603 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
604 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
605 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
606 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
607 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
608 ROW_FIELD_EQ(alu_constant_64, 64),
609 ROW_FIELD_EQ(alu_sel_is_u128, 0),
610 ROW_FIELD_EQ(alu_tag_u128_diff_inv,
611 FF(static_cast<uint8_t>(MemoryTag::FF) - static_cast<uint8_t>(MemoryTag::U128)).invert()),
612 ROW_FIELD_EQ(alu_sel_is_ff, 1),
613 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
614 ROW_FIELD_EQ(alu_sel_div_no_0_err, 1),
615 ROW_FIELD_EQ(alu_sel_tag_err, 1),
616 ROW_FIELD_EQ(alu_sel_err, 1),
617 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
618 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
619 AllOf(
620 ROW_FIELD_EQ(alu_sel_op_div, 1),
621 ROW_FIELD_EQ(alu_sel, 1),
622 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
623 ROW_FIELD_EQ(alu_ia, 6),
624 ROW_FIELD_EQ(alu_ib, 3),
625 ROW_FIELD_EQ(alu_ic, 2),
626 ROW_FIELD_EQ(alu_helper1, 0),
627 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
628 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
629 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
630 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
631 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
632 ROW_FIELD_EQ(alu_constant_64, 64),
633 ROW_FIELD_EQ(alu_sel_is_u128, 0),
634 ROW_FIELD_EQ(alu_tag_u128_diff_inv,
635 FF(static_cast<uint8_t>(MemoryTag::FF) - static_cast<uint8_t>(MemoryTag::U128)).invert()),
636 ROW_FIELD_EQ(alu_sel_is_ff, 1),
637 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
638 ROW_FIELD_EQ(alu_sel_div_no_0_err, 1),
639 ROW_FIELD_EQ(alu_sel_tag_err, 1),
640 ROW_FIELD_EQ(alu_sel_err, 1),
641 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
642 ROW_FIELD_EQ(
643 alu_ab_tags_diff_inv,
644 FF(static_cast<uint8_t>(MemoryTag::FF) - static_cast<uint8_t>(MemoryTag::U128)).invert()))));
645}
646
647TEST_F(AluTraceGenerationTest, TraceGenerationDivByZeroError)
648{
649 builder.process(
650 {
651 { .operation = AluOperation::DIV,
652 .a = MemoryValue::from<uint64_t>(6),
653 .b = MemoryValue::from<uint64_t>(0), // c is optional
654 .error = AluError::DIV_0_ERROR },
655 },
656 trace);
657
658 auto tag = static_cast<uint8_t>(MemoryTag::U64);
659
660 EXPECT_THAT(
661 trace.as_rows(),
662 ElementsAre(AllOf(
663 ROW_FIELD_EQ(alu_sel_op_div, 1),
664 ROW_FIELD_EQ(alu_sel, 1),
665 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_DIV),
666 ROW_FIELD_EQ(alu_ia, 6),
667 ROW_FIELD_EQ(alu_ib, 0),
668 ROW_FIELD_EQ(alu_helper1, 0),
669 ROW_FIELD_EQ(alu_ia_tag, tag),
670 ROW_FIELD_EQ(alu_ib_tag, tag),
671 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U64)),
672 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U64)),
673 ROW_FIELD_EQ(alu_constant_64, 64),
674 ROW_FIELD_EQ(alu_sel_is_u128, 0),
675 ROW_FIELD_EQ(alu_tag_u128_diff_inv,
676 FF(static_cast<uint8_t>(MemoryTag::U64) - static_cast<uint8_t>(MemoryTag::U128)).invert()),
677 ROW_FIELD_EQ(alu_sel_is_ff, 0),
678 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
679 FF(static_cast<uint8_t>(MemoryTag::U64) - static_cast<uint8_t>(MemoryTag::FF)).invert()),
680 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
681 ROW_FIELD_EQ(alu_sel_div_no_0_err, 0),
682 ROW_FIELD_EQ(alu_sel_div_0_err, 1),
683 ROW_FIELD_EQ(alu_sel_tag_err, 0),
684 ROW_FIELD_EQ(alu_sel_err, 1),
685 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
686}
687
688// FDIV TESTS
689
690// Note: The test framework below converts all inputs to FF values to allow for many happy path tests without adding
691// new vectors. Non-FF values are tested separately.
692const std::vector<MemoryValue> TEST_VALUES_FDIV_OUT = {
693 MemoryValue::from_tag(MemoryTag::FF, 0), // Dividing by zero, so expecting an error
694 MemoryValue::from_tag(MemoryTag::FF, 1),
695 MemoryValue::from_tag(MemoryTag::FF, 4),
696 MemoryValue::from_tag(MemoryTag::FF, FF("0x01e5d0e15e2a1a5bfd30530c2d3c49bd60f2fa0ce1a2e146f39a6e05cd2d2d2e")),
697 MemoryValue::from_tag(MemoryTag::FF, FF("0x1e980ebbc51694827ee20074ac28b250a037a43eb44b38e6aa367c57a05e6d48")),
698 MemoryValue::from_tag(MemoryTag::FF, FF("0x2147f0860ba1d62029c594e3f5aceb850f136498cea0446888431f547aadd073")),
699 MemoryValue::from_tag(MemoryTag::FF, FF("0x135b52945a13d9aa49b9b57c33cd568ba9ae5ce9ca4a2d06e7f3fbd4f9999998")),
700 MemoryValue::from_tag(MemoryTag::FF, FF("0x24cf2a710b7edf4a26671a904a58c669b3f0209955b8ae8fc6ebbaffdc413535")),
701 MemoryValue::from_tag(MemoryTag::FF, FF("0x135b52945a13d9aa49b9b57c33cd568ba9ae5ce9ca4a2d071b272f07f9999998")),
702 MemoryValue::from_tag(MemoryTag::FF, FF("0x0b4aa7141dd9de9dbb71b5c665b57fb2d51dbb57c3a94d1d4a4d490bf23d5d0d")),
703 MemoryValue::from_tag(MemoryTag::FF, FF("0x135b52945a13d9aa49b9b57c33cd568bdce1901cfd7d603a1b272f07f9999998")),
704 MemoryValue::from_tag(MemoryTag::FF, FF("0x27065734afd7f6d659d8a21b1823b65a575334117d9b1cb58b0a1af021960640")),
705 MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 2),
706};
707
708const std::vector<ThreeOperandTestParams> TEST_VALUES_FDIV = zip_helper(TEST_VALUES_FDIV_OUT);
709
710class AluFDivTraceGenerationTest : public AluTraceGenerationTest,
711 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
712
713INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluFDivTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_FDIV));
714
715TEST_P(AluFDivTraceGenerationTest, TraceGenerationFDiv)
716{
717 auto [a, b, c] = GetParam();
718 a = MemoryValue::from_tag(MemoryTag::FF, a);
719 b = MemoryValue::from_tag(MemoryTag::FF, b);
720 c = MemoryValue::from_tag(MemoryTag::FF, c);
721 auto tag = a.get_tag();
722
723 bool div_0_error = b.as_ff() == FF(0);
724
725 builder.process(
726 {
727 { .operation = AluOperation::FDIV,
728 .a = a,
729 .b = b,
730 .c = c,
731 .error = div_0_error ? std::make_optional(simulation::AluError::DIV_0_ERROR) : std::nullopt },
732 },
733 trace);
734
735 EXPECT_THAT(trace.as_rows(),
736 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
737 ROW_FIELD_EQ(alu_sel, 1),
738 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
739 ROW_FIELD_EQ(alu_ia, a),
740 ROW_FIELD_EQ(alu_ib, b),
741 ROW_FIELD_EQ(alu_ic, c),
742 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
743 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
744 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
745 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
746 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
747 ROW_FIELD_EQ(alu_sel_is_u128, 0),
748 ROW_FIELD_EQ(alu_sel_is_ff, 1),
749 ROW_FIELD_EQ(alu_tag_ff_diff_inv, 0),
750 ROW_FIELD_EQ(alu_sel_div_0_err, div_0_error ? 1 : 0),
751 ROW_FIELD_EQ(alu_sel_tag_err, 0),
752 ROW_FIELD_EQ(alu_sel_err, div_0_error ? 1 : 0),
753 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
754}
755
756TEST_F(AluTraceGenerationTest, TraceGenerationFDivTagError)
757{
758 // Tests two cases unique to FDIV:
759 // a. inputs are both matching non-FF => should have a tag error (FF_TAG_ERR)
760 // b. input a is non-FF, b is FF => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
761 builder.process(
762 {
763 { .operation = AluOperation::FDIV,
764 .a = MemoryValue::from<uint128_t>(6),
765 .b = MemoryValue::from<uint128_t>(3),
766 .c = MemoryValue::from<uint128_t>(2),
767 .error = AluError::TAG_ERROR },
768 { .operation = AluOperation::FDIV,
769 .a = MemoryValue::from<uint64_t>(6),
770 .b = MemoryValue::from<FF>(3),
771 .c = MemoryValue::from<uint64_t>(2),
772 .error = AluError::TAG_ERROR },
773 },
774 trace);
775
776 auto u128_tag = static_cast<uint8_t>(MemoryTag::U128);
777 auto u64_tag = static_cast<uint8_t>(MemoryTag::U64);
778
779 EXPECT_THAT(trace.as_rows(),
780 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
781 ROW_FIELD_EQ(alu_sel, 1),
782 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
783 ROW_FIELD_EQ(alu_ia, 6),
784 ROW_FIELD_EQ(alu_ib, 3),
785 ROW_FIELD_EQ(alu_ic, 2),
786 ROW_FIELD_EQ(alu_ia_tag, u128_tag),
787 ROW_FIELD_EQ(alu_ib_tag, u128_tag),
788 ROW_FIELD_EQ(alu_ic_tag, u128_tag),
789 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U128)),
790 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U128)),
791 ROW_FIELD_EQ(alu_sel_is_ff, 0),
792 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
793 FF(FF(u128_tag) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
794 ROW_FIELD_EQ(alu_sel_div_0_err, 0),
795 ROW_FIELD_EQ(alu_sel_tag_err, 1),
796 ROW_FIELD_EQ(alu_sel_err, 1),
797 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
798 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
799 AllOf(ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
800 ROW_FIELD_EQ(alu_sel, 1),
801 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
802 ROW_FIELD_EQ(alu_ia, 6),
803 ROW_FIELD_EQ(alu_ib, 3),
804 ROW_FIELD_EQ(alu_ic, 2),
805 ROW_FIELD_EQ(alu_helper1, 0),
806 ROW_FIELD_EQ(alu_ia_tag, u64_tag),
807 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
808 ROW_FIELD_EQ(alu_ic_tag, u64_tag),
809 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::U64)),
810 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::U64)),
811 ROW_FIELD_EQ(alu_sel_is_ff, 0),
812 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
813 FF(FF(u64_tag) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()),
814 ROW_FIELD_EQ(alu_sel_div_0_err, 0),
815 ROW_FIELD_EQ(alu_sel_tag_err, 1),
816 ROW_FIELD_EQ(alu_sel_err, 1),
817 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
818 ROW_FIELD_EQ(alu_ab_tags_diff_inv,
819 FF(FF(u64_tag) - FF(static_cast<uint8_t>(MemoryTag::FF))).invert()))));
820}
821
822TEST_F(AluTraceGenerationTest, TraceGenerationFDivByZeroError)
823{
824 builder.process(
825 {
826 { .operation = AluOperation::FDIV,
827 .a = MemoryValue::from<FF>(6),
828 .b = MemoryValue::from<FF>(0), // c is optional
829 .error = AluError::DIV_0_ERROR },
830 },
831 trace);
832
833 auto tag = static_cast<uint8_t>(MemoryTag::FF);
834
835 EXPECT_THAT(trace.as_rows(),
836 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_fdiv, 1),
837 ROW_FIELD_EQ(alu_sel, 1),
838 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_FDIV),
839 ROW_FIELD_EQ(alu_ia, 6),
840 ROW_FIELD_EQ(alu_ib, 0),
841 ROW_FIELD_EQ(alu_ia_tag, tag),
842 ROW_FIELD_EQ(alu_ib_tag, tag),
843 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
844 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
845 ROW_FIELD_EQ(alu_sel_is_u128, 0),
846 ROW_FIELD_EQ(alu_sel_is_ff, 1),
847 ROW_FIELD_EQ(alu_tag_ff_diff_inv, 0),
848 ROW_FIELD_EQ(alu_sel_div_0_err, 1),
849 ROW_FIELD_EQ(alu_sel_tag_err, 0),
850 ROW_FIELD_EQ(alu_sel_err, 1),
851 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
852}
853
854// EQ TESTS
855
856const std::vector<MemoryValue> TEST_VALUES_EQ_OUT = {
857 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
858 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
859 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
860 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
861 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
862 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
863 MemoryValue::from_tag(MemoryTag::U1, 0),
864};
865
866const std::vector<ThreeOperandTestParams> TEST_VALUES_EQ = zip_helper(TEST_VALUES_EQ_OUT);
867
868class AluEQTraceGenerationTest : public AluTraceGenerationTest,
869 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
870
871INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluEQTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_EQ));
872
873TEST_P(AluEQTraceGenerationTest, TraceGenerationEQ)
874{
875 auto [a, _b, _c] = GetParam();
876 auto tag = a.get_tag();
877
878 builder.process(
879 {
880 {
881 .operation = AluOperation::EQ,
882 .a = a,
883 .b = a,
884 .c = MemoryValue::from_tag(MemoryTag::U1, 1),
885 },
886 },
887 trace);
888
889 EXPECT_THAT(trace.as_rows(),
890 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_eq, 1),
891 ROW_FIELD_EQ(alu_sel, 1),
892 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_EQ),
893 ROW_FIELD_EQ(alu_ia, a),
894 ROW_FIELD_EQ(alu_ib, a),
895 ROW_FIELD_EQ(alu_ic, 1),
896 ROW_FIELD_EQ(alu_helper1, 0),
897 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
898 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
899 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
900 ROW_FIELD_EQ(alu_sel_tag_err, 0),
901 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
902}
903
904TEST_P(AluEQTraceGenerationTest, TraceGenerationInEQ)
905{
906 auto [a, b, c] = GetParam();
907 auto tag = a.get_tag();
908
909 builder.process(
910 {
911 {
912 .operation = AluOperation::EQ,
913 .a = a,
914 .b = b,
915 .c = c,
916 },
917 },
918 trace);
919
920 EXPECT_THAT(trace.as_rows(),
921 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_eq, 1),
922 ROW_FIELD_EQ(alu_sel, 1),
923 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_EQ),
924 ROW_FIELD_EQ(alu_ia, a),
925 ROW_FIELD_EQ(alu_ib, b),
926 ROW_FIELD_EQ(alu_ic, c),
927 ROW_FIELD_EQ(alu_helper1, c.as_ff() == 1 ? 0 : FF(a.as_ff() - b.as_ff()).invert()),
928 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
929 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
930 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
931 ROW_FIELD_EQ(alu_sel_tag_err, 0),
932 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
933}
934
935// LT TESTS
936
937const std::vector<MemoryValue> TEST_VALUES_LT_OUT = {
938 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 0),
939 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
940 MemoryValue::from_tag(MemoryTag::U1, 1), MemoryValue::from_tag(MemoryTag::U1, 0),
941 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
942 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
943 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
944 MemoryValue::from_tag(MemoryTag::U1, 0),
945};
946
947const std::vector<ThreeOperandTestParams> TEST_VALUES_LT = zip_helper(TEST_VALUES_LT_OUT);
948
949class AluLTTraceGenerationTest : public AluTraceGenerationTest,
950 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
951
952INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluLTTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_LT));
953
954TEST_P(AluLTTraceGenerationTest, TraceGenerationLT)
955{
956 auto [a, b, c] = GetParam();
957 auto tag = a.get_tag();
958 bool is_ff = tag == MemoryTag::FF;
959 builder.process(
960 {
961 { .operation = AluOperation::LT, .a = a, .b = b, .c = c },
962 },
963 trace);
964
965 EXPECT_THAT(
966 trace.as_rows(),
967 ElementsAre(AllOf(
968 ROW_FIELD_EQ(alu_sel_op_lt, 1),
969 ROW_FIELD_EQ(alu_sel_lt_ops, 1),
970 ROW_FIELD_EQ(alu_sel, 1),
971 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_LT),
972 ROW_FIELD_EQ(alu_ia, a),
973 ROW_FIELD_EQ(alu_ib, b),
974 ROW_FIELD_EQ(alu_ic, c),
975 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
976 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
977 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
978 ROW_FIELD_EQ(alu_cf, 0),
979 ROW_FIELD_EQ(alu_lt_ops_input_a, b),
980 ROW_FIELD_EQ(alu_lt_ops_input_b, a),
981 ROW_FIELD_EQ(alu_lt_ops_result_c, c),
982 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
983 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
984 ROW_FIELD_EQ(alu_sel_is_ff, is_ff ? 1 : 0),
985 ROW_FIELD_EQ(alu_sel_ff_lt_ops, is_ff ? 1 : 0),
986 ROW_FIELD_EQ(alu_sel_int_lt_ops, is_ff ? 0 : 1),
987 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
988 is_ff ? 0 : FF(static_cast<uint8_t>(tag) - static_cast<uint8_t>(MemoryTag::FF)).invert()),
989 ROW_FIELD_EQ(alu_sel_tag_err, 0),
990 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
991}
992
993// LTE TESTS
994
995const std::vector<MemoryValue> TEST_VALUES_LTE_OUT = {
996 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
997 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
998 MemoryValue::from_tag(MemoryTag::U1, 1), MemoryValue::from_tag(MemoryTag::U1, 0),
999 MemoryValue::from_tag(MemoryTag::U1, 0), MemoryValue::from_tag(MemoryTag::U1, 1),
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, 0),
1003};
1004
1005const std::vector<ThreeOperandTestParams> TEST_VALUES_LTE = zip_helper(TEST_VALUES_LTE_OUT);
1006
1007class AluLTETraceGenerationTest : public AluTraceGenerationTest,
1008 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
1009
1010INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluLTETraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_LTE));
1011
1012TEST_P(AluLTETraceGenerationTest, TraceGenerationLTE)
1013{
1014 auto [a, b, c] = GetParam();
1015 auto tag = a.get_tag();
1016 bool is_ff = tag == MemoryTag::FF;
1017 builder.process(
1018 {
1019 { .operation = AluOperation::LTE, .a = a, .b = b, .c = c },
1020 },
1021 trace);
1022
1023 EXPECT_THAT(
1024 trace.as_rows(),
1025 ElementsAre(AllOf(
1026 ROW_FIELD_EQ(alu_sel_op_lte, 1),
1027 ROW_FIELD_EQ(alu_sel_lt_ops, 1),
1028 ROW_FIELD_EQ(alu_sel, 1),
1029 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_LTE),
1030 ROW_FIELD_EQ(alu_ia, a),
1031 ROW_FIELD_EQ(alu_ib, b),
1032 ROW_FIELD_EQ(alu_ic, c),
1033 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1034 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1035 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::U1)),
1036 ROW_FIELD_EQ(alu_cf, 0),
1037 ROW_FIELD_EQ(alu_lt_ops_input_a, a),
1038 ROW_FIELD_EQ(alu_lt_ops_input_b, b),
1039 ROW_FIELD_EQ(alu_lt_ops_result_c, c.as_ff() == 1 ? 0 : 1),
1040 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
1041 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1042 ROW_FIELD_EQ(alu_sel_is_ff, is_ff ? 1 : 0),
1043 ROW_FIELD_EQ(alu_sel_ff_lt_ops, is_ff ? 1 : 0),
1044 ROW_FIELD_EQ(alu_sel_int_lt_ops, is_ff ? 0 : 1),
1045 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
1046 is_ff ? 0 : FF(static_cast<uint8_t>(tag) - static_cast<uint8_t>(MemoryTag::FF)).invert()),
1047 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1048 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
1049}
1050
1051// NOT Opcode TESTS
1052
1053const std::vector<MemoryValue> TEST_VALUES_NOT = split_helper(TEST_VALUES_IN);
1054
1055class AluNOTTraceGenerationTest : public AluTraceGenerationTest, public ::testing::WithParamInterface<MemoryValue> {};
1056
1057INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluNOTTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_NOT));
1058
1059TEST_P(AluNOTTraceGenerationTest, TraceGenerationNOT)
1060{
1061 auto a = GetParam();
1062 auto tag = a.get_tag();
1063 bool is_ff = tag == MemoryTag::FF;
1064 auto b = is_ff ? MemoryValue::from_tag(MemoryTag::FF, 0) : ~a;
1065
1066 builder.process(
1067 {
1068 { .operation = AluOperation::NOT,
1069 .a = a,
1070 .b = b,
1071 .error = is_ff ? std::make_optional(simulation::AluError::TAG_ERROR) : std::nullopt },
1072 },
1073 trace);
1074
1075 EXPECT_THAT(
1076 trace.as_rows(),
1077 ElementsAre(AllOf(
1078 ROW_FIELD_EQ(alu_sel_op_not, 1),
1079 ROW_FIELD_EQ(alu_sel, 1),
1080 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_NOT),
1081 ROW_FIELD_EQ(alu_ia, a),
1082 ROW_FIELD_EQ(alu_ib, b),
1083 ROW_FIELD_EQ(alu_ic, 0),
1084 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1085 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1086 ROW_FIELD_EQ(alu_ic_tag, 0),
1087 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1088 ROW_FIELD_EQ(alu_sel_is_ff, is_ff ? 1 : 0),
1089 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
1090 is_ff ? 0 : FF(static_cast<uint8_t>(tag) - static_cast<uint8_t>(MemoryTag::FF)).invert()),
1091 ROW_FIELD_EQ(alu_sel_tag_err, is_ff ? 1 : 0),
1092 ROW_FIELD_EQ(alu_sel_err, is_ff ? 1 : 0))));
1093}
1094
1095// SHL TESTS
1096
1097const std::vector<MemoryValue> TEST_VALUES_SHL_OUT = {
1098 MemoryValue::from_tag(MemoryTag::U1, 1),
1099 MemoryValue::from_tag(MemoryTag::U1, 0),
1100 MemoryValue::from_tag(MemoryTag::U8, 0),
1101 MemoryValue::from_tag(MemoryTag::U8, 0),
1102 MemoryValue::from_tag(MemoryTag::U16, 0),
1103 MemoryValue::from_tag(MemoryTag::U16, 0),
1104 MemoryValue::from_tag(MemoryTag::U32, 0xfffffec0),
1105 MemoryValue::from_tag(MemoryTag::U32, 0xb0000000),
1106 MemoryValue::from_tag(MemoryTag::U64, 0xfffffffffffffec0ULL),
1107 MemoryValue::from_tag(MemoryTag::U64, 0xb000000000000000ULL),
1108 MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 128) - 320), // 0xfffffffffffffffffffffffffffffec0
1109 MemoryValue::from_tag(MemoryTag::U128, 0),
1110};
1111
1112const std::vector<ThreeOperandTestParams> TEST_VALUES_SHL = zip_helper(TEST_VALUES_SHL_OUT);
1113
1114class AluShlTraceGenerationTest : public AluTraceGenerationTest,
1115 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
1116
1117INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluShlTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_SHL));
1118
1119TEST_P(AluShlTraceGenerationTest, TraceGenerationShl)
1120{
1121 auto [a, b, c] = GetParam();
1122 auto tag = a.get_tag();
1123 auto tag_bits = get_tag_bits(tag);
1124 auto b_num = static_cast<uint128_t>(b.as_ff());
1125
1126 auto overflow = b_num > tag_bits;
1127 uint128_t shift_lo_bits = overflow ? tag_bits : tag_bits - b_num;
1128 uint128_t shift_hi_bits = overflow ? tag_bits : b_num;
1129 auto two_pow_shift_lo_bits = static_cast<uint128_t>(1) << shift_lo_bits;
1130 auto a_lo = overflow ? b_num - tag_bits : static_cast<uint128_t>(a.as_ff()) % two_pow_shift_lo_bits;
1131 auto a_hi = static_cast<uint128_t>(a.as_ff()) >> shift_lo_bits;
1132
1133 builder.process({ {
1134 .operation = AluOperation::SHL,
1135 .a = a,
1136 .b = b,
1137 .c = c,
1138 } },
1139 trace);
1140
1141 EXPECT_THAT(
1142 trace.as_rows(),
1143 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_shl, 1),
1144 ROW_FIELD_EQ(alu_sel, 1),
1145 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHL),
1146 ROW_FIELD_EQ(alu_ia, a),
1147 ROW_FIELD_EQ(alu_a_hi, a_hi),
1148 ROW_FIELD_EQ(alu_a_hi_bits, shift_hi_bits),
1149 ROW_FIELD_EQ(alu_a_lo, a_lo),
1150 ROW_FIELD_EQ(alu_a_lo_bits, shift_lo_bits),
1151 ROW_FIELD_EQ(alu_ib, b),
1152 ROW_FIELD_EQ(alu_ic, c),
1153 ROW_FIELD_EQ(alu_helper1, static_cast<uint128_t>(1) << b_num),
1154 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1155 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1156 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
1157 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
1158 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1159 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
1160 ROW_FIELD_EQ(alu_sel_is_ff, 0),
1161 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
1162 FF(static_cast<uint8_t>(tag) - static_cast<uint8_t>(MemoryTag::FF)).invert()),
1163 ROW_FIELD_EQ(alu_sel_shift_ops, 1),
1164 ROW_FIELD_EQ(alu_sel_shift_ops_no_overflow, overflow ? 0 : 1),
1165 ROW_FIELD_EQ(alu_shift_lo_bits, shift_lo_bits),
1166 ROW_FIELD_EQ(alu_two_pow_shift_lo_bits, two_pow_shift_lo_bits),
1167 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1168 ROW_FIELD_EQ(alu_sel_err, 0),
1169 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
1170}
1171
1172TEST_F(AluShlTraceGenerationTest, TraceGenerationShlTagError)
1173{
1174 // Tests two cases:
1175 // a. inputs are both FF => should have a tag error (FF_TAG_ERR)
1176 // b. input a is FF, b is not => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
1177 builder.process(
1178 {
1179 { .operation = AluOperation::SHL,
1180 .a = MemoryValue::from<FF>(6),
1181 .b = MemoryValue::from<FF>(3),
1182 .c = MemoryValue::from<FF>(48),
1183 .error = AluError::TAG_ERROR },
1184 { .operation = AluOperation::SHL,
1185 .a = MemoryValue::from<FF>(6),
1186 .b = MemoryValue::from<uint128_t>(3),
1187 .c = MemoryValue::from<FF>(48),
1188 .error = AluError::TAG_ERROR },
1189 },
1190 trace);
1191
1192 EXPECT_THAT(
1193 trace.as_rows(),
1194 ElementsAre(
1195 AllOf(ROW_FIELD_EQ(alu_sel_op_shl, 1),
1196 ROW_FIELD_EQ(alu_sel, 1),
1197 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHL),
1198 ROW_FIELD_EQ(alu_ia, 6),
1199 ROW_FIELD_EQ(alu_ib, 3),
1200 ROW_FIELD_EQ(alu_ic, 48),
1201 ROW_FIELD_EQ(alu_helper1, 8),
1202 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1203 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
1204 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1205 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1206 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1207 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1208 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1209 ROW_FIELD_EQ(alu_sel_err, 1),
1210 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
1211 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
1212 AllOf(ROW_FIELD_EQ(alu_sel_op_shl, 1),
1213 ROW_FIELD_EQ(alu_sel, 1),
1214 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHL),
1215 ROW_FIELD_EQ(alu_ia, 6),
1216 ROW_FIELD_EQ(alu_ib, 3),
1217 ROW_FIELD_EQ(alu_ic, 48),
1218 ROW_FIELD_EQ(alu_helper1, 8),
1219 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1220 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
1221 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1222 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1223 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1224 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1225 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
1226 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1227 ROW_FIELD_EQ(alu_sel_err, 1),
1228 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
1229 ROW_FIELD_EQ(
1230 alu_ab_tags_diff_inv,
1231 FF(static_cast<uint8_t>(MemoryTag::FF) - static_cast<uint8_t>(MemoryTag::U128)).invert()))));
1232}
1233
1234// SHR TESTS
1235
1236const std::vector<MemoryValue> TEST_VALUES_SHR_OUT = {
1237 MemoryValue::from_tag(MemoryTag::U1, 1),
1238 MemoryValue::from_tag(MemoryTag::U1, 0),
1239 MemoryValue::from_tag(MemoryTag::U8, 0),
1240 MemoryValue::from_tag(MemoryTag::U8, 0),
1241 MemoryValue::from_tag(MemoryTag::U16, 0),
1242 MemoryValue::from_tag(MemoryTag::U16, 0),
1243 MemoryValue::from_tag(MemoryTag::U32, 0x7ffffff),
1244 MemoryValue::from_tag(MemoryTag::U32, 0x0000001f),
1245 MemoryValue::from_tag(MemoryTag::U64, 0x7ffffffffffffffULL),
1246 MemoryValue::from_tag(MemoryTag::U64, 0x000000000000001fULL),
1247 MemoryValue::from_tag(MemoryTag::U128,
1248 (uint256_t(1) << 128) - 1 - (uint256_t(248) << 120)), // 0x7ffffffffffffffffffffffffffffff
1249 MemoryValue::from_tag(MemoryTag::U128, 0x000000000000001fULL),
1250};
1251
1252const std::vector<ThreeOperandTestParams> TEST_VALUES_SHR = zip_helper(TEST_VALUES_SHR_OUT);
1253
1254class AluShrTraceGenerationTest : public AluTraceGenerationTest,
1255 public ::testing::WithParamInterface<ThreeOperandTestParams> {};
1256
1257INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest, AluShrTraceGenerationTest, ::testing::ValuesIn(TEST_VALUES_SHR));
1258
1259TEST_P(AluShrTraceGenerationTest, TraceGenerationShr)
1260{
1261 auto [a, b, c] = GetParam();
1262 auto tag = a.get_tag();
1263 auto tag_bits = get_tag_bits(tag);
1264 auto b_num = static_cast<uint128_t>(b.as_ff());
1265
1266 auto overflow = b_num > tag_bits;
1267 uint128_t shift_lo_bits = overflow ? tag_bits : b_num;
1268 uint128_t shift_hi_bits = overflow ? tag_bits : tag_bits - b_num;
1269 auto two_pow_shift_lo_bits = static_cast<uint128_t>(1) << shift_lo_bits;
1270 auto a_lo = overflow ? b_num - tag_bits : static_cast<uint128_t>(a.as_ff()) % two_pow_shift_lo_bits;
1271 auto a_hi = static_cast<uint128_t>(a.as_ff()) >> shift_lo_bits;
1272
1273 builder.process({ {
1274 .operation = AluOperation::SHR,
1275 .a = a,
1276 .b = b,
1277 .c = c,
1278 } },
1279 trace);
1280
1281 EXPECT_THAT(
1282 trace.as_rows(),
1283 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_shr, 1),
1284 ROW_FIELD_EQ(alu_sel, 1),
1285 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHR),
1286 ROW_FIELD_EQ(alu_ia, a),
1287 ROW_FIELD_EQ(alu_a_hi, a_hi),
1288 ROW_FIELD_EQ(alu_a_hi_bits, shift_hi_bits),
1289 ROW_FIELD_EQ(alu_a_lo, a_lo),
1290 ROW_FIELD_EQ(alu_a_lo_bits, shift_lo_bits),
1291 ROW_FIELD_EQ(alu_ib, b),
1292 ROW_FIELD_EQ(alu_ic, c),
1293 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(tag)),
1294 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(tag)),
1295 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(tag)),
1296 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(tag)),
1297 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(tag)),
1298 ROW_FIELD_EQ(alu_sel_decompose_a, 1),
1299 ROW_FIELD_EQ(alu_sel_is_ff, 0),
1300 ROW_FIELD_EQ(alu_tag_ff_diff_inv,
1301 FF(static_cast<uint8_t>(tag) - static_cast<uint8_t>(MemoryTag::FF)).invert()),
1302 ROW_FIELD_EQ(alu_sel_shift_ops, 1),
1303 ROW_FIELD_EQ(alu_sel_shift_ops_no_overflow, overflow ? 0 : 1),
1304 ROW_FIELD_EQ(alu_shift_lo_bits, shift_lo_bits),
1305 ROW_FIELD_EQ(alu_two_pow_shift_lo_bits, two_pow_shift_lo_bits),
1306 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1307 ROW_FIELD_EQ(alu_sel_err, 0),
1308 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0))));
1309}
1310
1311TEST_F(AluShrTraceGenerationTest, TraceGenerationShrTagError)
1312{
1313 // Tests two cases:
1314 // a. inputs are both FF => should have a tag error (FF_TAG_ERR)
1315 // b. input a is FF, b is not => should have a tag error with BOTH FF_TAG_ERR and ab_tag_mismatch
1316 builder.process(
1317 {
1318 { .operation = AluOperation::SHR,
1319 .a = MemoryValue::from<FF>(6),
1320 .b = MemoryValue::from<FF>(3),
1321 .c = MemoryValue::from<FF>(0),
1322 .error = AluError::TAG_ERROR },
1323 { .operation = AluOperation::SHR,
1324 .a = MemoryValue::from<FF>(6),
1325 .b = MemoryValue::from<uint128_t>(3),
1326 .c = MemoryValue::from<FF>(0),
1327 .error = AluError::TAG_ERROR },
1328 },
1329 trace);
1330
1331 EXPECT_THAT(
1332 trace.as_rows(),
1333 ElementsAre(
1334 AllOf(ROW_FIELD_EQ(alu_sel_op_shr, 1),
1335 ROW_FIELD_EQ(alu_sel, 1),
1336 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHR),
1337 ROW_FIELD_EQ(alu_ia, 6),
1338 ROW_FIELD_EQ(alu_ib, 3),
1339 ROW_FIELD_EQ(alu_ic, 0),
1340 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1341 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::FF)),
1342 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1343 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1344 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1345 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1346 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1347 ROW_FIELD_EQ(alu_sel_err, 1),
1348 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 0),
1349 ROW_FIELD_EQ(alu_ab_tags_diff_inv, 0)),
1350 AllOf(ROW_FIELD_EQ(alu_sel_op_shr, 1),
1351 ROW_FIELD_EQ(alu_sel, 1),
1352 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_SHR),
1353 ROW_FIELD_EQ(alu_ia, 6),
1354 ROW_FIELD_EQ(alu_ib, 3),
1355 ROW_FIELD_EQ(alu_ic, 0),
1356 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(MemoryTag::FF)),
1357 ROW_FIELD_EQ(alu_ib_tag, static_cast<uint8_t>(MemoryTag::U128)),
1358 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(MemoryTag::FF)),
1359 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(MemoryTag::FF)),
1360 ROW_FIELD_EQ(alu_max_value, get_tag_max_value(MemoryTag::FF)),
1361 ROW_FIELD_EQ(alu_sel_is_ff, 1),
1362 ROW_FIELD_EQ(alu_sel_mul_div_u128, 0),
1363 ROW_FIELD_EQ(alu_sel_tag_err, 1),
1364 ROW_FIELD_EQ(alu_sel_err, 1),
1365 ROW_FIELD_EQ(alu_sel_ab_tag_mismatch, 1),
1366 ROW_FIELD_EQ(
1367 alu_ab_tags_diff_inv,
1368 FF(static_cast<uint8_t>(MemoryTag::FF) - static_cast<uint8_t>(MemoryTag::U128)).invert()))));
1369}
1370
1371// TRUNCATE operation (SET/CAST opcodes)
1372
1373// Truncation is a special case as we always have FF TaggedValue inputs:
1374struct TruncateTrivialTestParams {
1375 MemoryValue a;
1376 MemoryTag dst_tag;
1377 FF expected_result;
1378};
1379
1380const std::vector<TruncateTrivialTestParams> TRUNCATE_TRIVIAL_TEST_PARAMS = {
1381 {
1382 .a = MemoryValue::from_tag(MemoryTag::FF, 1),
1383 .dst_tag = MemoryTag::U1,
1384 .expected_result = 1,
1385 },
1386 {
1387 .a = MemoryValue::from_tag(MemoryTag::FF, 7),
1388 .dst_tag = MemoryTag::U8,
1389 .expected_result = 7,
1390 },
1391 {
1392 .a = MemoryValue::from_tag(MemoryTag::U32, 123456789),
1393 .dst_tag = MemoryTag::U32,
1394 .expected_result = 123456789,
1395 },
1396 {
1397 .a = MemoryValue::from_tag(MemoryTag::U128, 1234567890123456789ULL),
1398 .dst_tag = MemoryTag::U64,
1399 .expected_result = 1234567890123456789ULL,
1400 },
1401 {
1402 .a = MemoryValue::from_tag(MemoryTag::U128, (uint256_t(1) << 127) + 982739482),
1403 .dst_tag = MemoryTag::U128,
1404 .expected_result = (uint256_t(1) << 127) + 982739482,
1405 },
1406 {
1407 .a = MemoryValue::from_tag(MemoryTag::FF, FF::modulus - 1),
1408 .dst_tag = MemoryTag::FF,
1409 .expected_result = FF::modulus - 1,
1410 },
1411};
1412
1413class AluTruncateTrivialTraceGenerationTest : public AluTraceGenerationTest,
1414 public ::testing::WithParamInterface<TruncateTrivialTestParams> {};
1415
1416INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest,
1417 AluTruncateTrivialTraceGenerationTest,
1418 ::testing::ValuesIn(TRUNCATE_TRIVIAL_TEST_PARAMS));
1419
1420TEST_P(AluTruncateTrivialTraceGenerationTest, TraceGenerationTruncateTrivial)
1421{
1422 auto [a, dst_tag, expected_result] = GetParam();
1423 auto b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(dst_tag));
1424 auto c = MemoryValue::from_tag(dst_tag, expected_result);
1425
1426 builder.process(
1427 {
1428 { .operation = AluOperation::TRUNCATE, .a = a, .b = b, .c = c },
1429 },
1430 trace);
1431
1432 EXPECT_THAT(trace.as_rows(),
1433 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_truncate, 1),
1434 ROW_FIELD_EQ(alu_sel_trunc_trivial, 1),
1435 ROW_FIELD_EQ(alu_sel_trunc_lt_128, 0),
1436 ROW_FIELD_EQ(alu_sel_trunc_gte_128, 0),
1437 ROW_FIELD_EQ(alu_sel_trunc_non_trivial, 0),
1438 ROW_FIELD_EQ(alu_sel, 1),
1439 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_TRUNCATE),
1440 ROW_FIELD_EQ(alu_ia, a),
1441 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(dst_tag)),
1442 ROW_FIELD_EQ(alu_ic, expected_result),
1443 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(dst_tag)),
1444 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(dst_tag)),
1445 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1446 ROW_FIELD_EQ(alu_a_lo, 0),
1447 ROW_FIELD_EQ(alu_a_hi, 0),
1448 ROW_FIELD_EQ(alu_mid, 0),
1449 ROW_FIELD_EQ(alu_mid_bits, 0))));
1450}
1451
1452struct TruncateNonTrivialTestParams {
1453 MemoryValue a;
1454 MemoryTag dst_tag;
1455 FF expected_result;
1456 FF expected_lo_128;
1457 FF expected_hi_128;
1458 FF expected_mid;
1459};
1460
1461const std::vector<TruncateNonTrivialTestParams> TRUNCATE_LESS_THAN_128_TEST_PARAMS = {
1462 {
1463 .a = MemoryValue::from_tag(MemoryTag::U128, (uint256_t(98263) << 64) + 123456789987654321ULL),
1464 .dst_tag = MemoryTag::U64,
1465 .expected_result = 123456789987654321ULL,
1466 .expected_lo_128 = (uint256_t(98263) << 64) + 123456789987654321ULL,
1467 .expected_hi_128 = 0,
1468 .expected_mid = 98263,
1469 },
1470 {
1471 .a = MemoryValue::from_tag(MemoryTag::U64, (uint256_t(98263) << 32) + 1234567ULL),
1472 .dst_tag = MemoryTag::U32,
1473 .expected_result = 1234567,
1474 .expected_lo_128 = (98263ULL << 32) + 1234567ULL,
1475 .expected_hi_128 = 0,
1476 .expected_mid = 98263,
1477 },
1478 {
1479 .a = MemoryValue::from_tag(MemoryTag::U64, (uint256_t(98263) << 32) + 1234ULL),
1480 .dst_tag = MemoryTag::U16,
1481 .expected_result = 1234,
1482 .expected_lo_128 = (98263ULL << 32) + 1234ULL,
1483 .expected_hi_128 = 0,
1484 .expected_mid = 98263ULL << 16,
1485 },
1486 {
1487 .a = MemoryValue::from_tag(MemoryTag::FF, 263),
1488 .dst_tag = MemoryTag::U8,
1489 .expected_result = 7,
1490 .expected_lo_128 = 263,
1491 .expected_hi_128 = 0,
1492 .expected_mid = 1,
1493 },
1494 {
1495 .a = MemoryValue::from_tag(MemoryTag::U64, 999),
1496 .dst_tag = MemoryTag::U1,
1497 .expected_result = 1,
1498 .expected_lo_128 = 999,
1499 .expected_hi_128 = 0,
1500 .expected_mid = 499,
1501 }
1502};
1503
1504class AluTruncateNonTrivialLT128TraceGenerationTest
1505 : public AluTraceGenerationTest,
1506 public ::testing::WithParamInterface<TruncateNonTrivialTestParams> {};
1507
1508INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest,
1509 AluTruncateNonTrivialLT128TraceGenerationTest,
1510 ::testing::ValuesIn(TRUNCATE_LESS_THAN_128_TEST_PARAMS));
1511
1512TEST_P(AluTruncateNonTrivialLT128TraceGenerationTest, TraceGenerationTruncateNonTrivialLT128)
1513{
1514 auto [a, dst_tag, expected_result, expected_lo_128, expected_hi_128, expected_mid] = GetParam();
1515 auto b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(dst_tag));
1516 auto c = MemoryValue::from_tag(dst_tag, expected_result);
1517
1518 builder.process(
1519 {
1520 { .operation = AluOperation::TRUNCATE, .a = a, .b = b, .c = c },
1521 },
1522 trace);
1523
1524 EXPECT_THAT(trace.as_rows(),
1525 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_truncate, 1),
1526 ROW_FIELD_EQ(alu_sel_trunc_trivial, 0),
1527 ROW_FIELD_EQ(alu_sel_trunc_lt_128, 1),
1528 ROW_FIELD_EQ(alu_sel_trunc_gte_128, 0),
1529 ROW_FIELD_EQ(alu_sel_trunc_non_trivial, 1),
1530 ROW_FIELD_EQ(alu_sel, 1),
1531 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_TRUNCATE),
1532 ROW_FIELD_EQ(alu_ia, a),
1533 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(dst_tag)),
1534 ROW_FIELD_EQ(alu_ic, expected_result),
1535 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(dst_tag)),
1536 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(dst_tag)),
1537 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1538 ROW_FIELD_EQ(alu_a_lo, expected_lo_128),
1539 ROW_FIELD_EQ(alu_a_hi, expected_hi_128),
1540 ROW_FIELD_EQ(alu_mid, expected_mid),
1541 ROW_FIELD_EQ(alu_mid_bits, 128 - get_tag_bits(dst_tag)))));
1542}
1543
1544const std::vector<TruncateNonTrivialTestParams> TRUNCATE_GREATER_THAN_128_TEST_PARAMS = {
1545 {
1546 .a = MemoryValue::from<FF>((uint256_t(98263) << 128) + (uint256_t(1111) << 64) + 123456789987654321ULL),
1547 .dst_tag = MemoryTag::U64,
1548 .expected_result = 123456789987654321ULL,
1549 .expected_lo_128 = (uint256_t(1111) << 64) + 123456789987654321ULL,
1550 .expected_hi_128 = 98263,
1551 .expected_mid = 1111,
1552 },
1553 {
1554 .a = MemoryValue::from<FF>((uint256_t(98263) << 128) + (uint256_t(1111) << 64) + 123456789),
1555 .dst_tag = MemoryTag::U32,
1556 .expected_result = 123456789,
1557 .expected_lo_128 = (uint256_t(1111) << 64) + 123456789,
1558 .expected_hi_128 = 98263,
1559 .expected_mid = 1111ULL << 32,
1560 },
1561 {
1562 .a = MemoryValue::from<FF>((uint256_t(98263) << 128) + (uint256_t(1111) << 64) + 1234),
1563 .dst_tag = MemoryTag::U16,
1564 .expected_result = 1234,
1565 .expected_lo_128 = (uint256_t(1111) << 64) + 1234,
1566 .expected_hi_128 = 98263,
1567 .expected_mid = 1111ULL << 48,
1568 },
1569 {
1570 .a = MemoryValue::from<FF>((uint256_t(98263) << 150) + (uint256_t(123456789987654321ULL) << 8) + 234),
1571 .dst_tag = MemoryTag::U8,
1572 .expected_result = 234,
1573 .expected_lo_128 = (uint256_t(123456789987654321ULL) << 8) + 234,
1574 .expected_hi_128 = 98263ULL << 22,
1575 .expected_mid = 123456789987654321ULL,
1576 }
1577};
1578
1579class AluTruncateNonTrivialGT128TraceGenerationTest
1580 : public AluTraceGenerationTest,
1581 public ::testing::WithParamInterface<TruncateNonTrivialTestParams> {};
1582
1583INSTANTIATE_TEST_SUITE_P(AluTraceGenerationTest,
1584 AluTruncateNonTrivialGT128TraceGenerationTest,
1585 ::testing::ValuesIn(TRUNCATE_GREATER_THAN_128_TEST_PARAMS));
1586
1587TEST_P(AluTruncateNonTrivialGT128TraceGenerationTest, TraceGenerationTruncateNonTrivialGT128)
1588{
1589 auto [a, dst_tag, expected_result, expected_lo_128, expected_hi_128, expected_mid] = GetParam();
1590 auto b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(dst_tag));
1591 auto c = MemoryValue::from_tag(dst_tag, expected_result);
1592
1593 builder.process(
1594 {
1595 { .operation = AluOperation::TRUNCATE, .a = a, .b = b, .c = c },
1596 },
1597 trace);
1598
1599 EXPECT_THAT(trace.as_rows(),
1600 ElementsAre(AllOf(ROW_FIELD_EQ(alu_sel_op_truncate, 1),
1601 ROW_FIELD_EQ(alu_sel_trunc_trivial, 0),
1602 ROW_FIELD_EQ(alu_sel_trunc_lt_128, 0),
1603 ROW_FIELD_EQ(alu_sel_trunc_gte_128, 1),
1604 ROW_FIELD_EQ(alu_sel_trunc_non_trivial, 1),
1605 ROW_FIELD_EQ(alu_sel, 1),
1606 ROW_FIELD_EQ(alu_op_id, AVM_EXEC_OP_ID_ALU_TRUNCATE),
1607 ROW_FIELD_EQ(alu_ia, a),
1608 ROW_FIELD_EQ(alu_ia_tag, static_cast<uint8_t>(dst_tag)),
1609 ROW_FIELD_EQ(alu_ic, expected_result),
1610 ROW_FIELD_EQ(alu_ic_tag, static_cast<uint8_t>(dst_tag)),
1611 ROW_FIELD_EQ(alu_max_bits, get_tag_bits(dst_tag)),
1612 ROW_FIELD_EQ(alu_sel_tag_err, 0),
1613 ROW_FIELD_EQ(alu_a_lo, expected_lo_128),
1614 ROW_FIELD_EQ(alu_a_hi, expected_hi_128),
1615 ROW_FIELD_EQ(alu_mid, expected_mid),
1616 ROW_FIELD_EQ(alu_mid_bits, 128 - get_tag_bits(dst_tag)))));
1617}
1618
1619} // namespace
1620} // 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:123
alu_event.hpp
alu_trace.hpp
dst_tag
MemoryTag dst_tag
Definition alu_trace.test.cpp:1376
expected_lo_128
FF expected_lo_128
Definition alu_trace.test.cpp:1456
expected_hi_128
FF expected_hi_128
Definition alu_trace.test.cpp:1457
expected_mid
FF expected_mid
Definition alu_trace.test.cpp:1458
AVM_EXEC_OP_ID_ALU_TRUNCATE
#define AVM_EXEC_OP_ID_ALU_TRUNCATE
Definition aztec_constants.hpp:99
AVM_EXEC_OP_ID_ALU_LTE
#define AVM_EXEC_OP_ID_ALU_LTE
Definition aztec_constants.hpp:95
AVM_EXEC_OP_ID_ALU_DIV
#define AVM_EXEC_OP_ID_ALU_DIV
Definition aztec_constants.hpp:91
AVM_EXEC_OP_ID_ALU_ADD
#define AVM_EXEC_OP_ID_ALU_ADD
Definition aztec_constants.hpp:88
AVM_EXEC_OP_ID_ALU_SHL
#define AVM_EXEC_OP_ID_ALU_SHL
Definition aztec_constants.hpp:97
AVM_EXEC_OP_ID_ALU_EQ
#define AVM_EXEC_OP_ID_ALU_EQ
Definition aztec_constants.hpp:93
AVM_EXEC_OP_ID_ALU_SUB
#define AVM_EXEC_OP_ID_ALU_SUB
Definition aztec_constants.hpp:89
AVM_EXEC_OP_ID_ALU_NOT
#define AVM_EXEC_OP_ID_ALU_NOT
Definition aztec_constants.hpp:96
AVM_EXEC_OP_ID_ALU_MUL
#define AVM_EXEC_OP_ID_ALU_MUL
Definition aztec_constants.hpp:90
AVM_EXEC_OP_ID_ALU_FDIV
#define AVM_EXEC_OP_ID_ALU_FDIV
Definition aztec_constants.hpp:92
AVM_EXEC_OP_ID_ALU_SHR
#define AVM_EXEC_OP_ID_ALU_SHR
Definition aztec_constants.hpp:98
AVM_EXEC_OP_ID_ALU_LT
#define AVM_EXEC_OP_ID_ALU_LT
Definition aztec_constants.hpp:94
bb::avm2::TaggedValue::from_tag
static TaggedValue from_tag(ValueTag tag, FF value)
Definition tagged_value.cpp:216
bb::avm2::tracegen::AluTraceBuilder::process
void process(const simulation::EventEmitterInterface< simulation::AluEvent >::Container &events, TraceContainer &trace)
Definition alu_trace.cpp:312
bb::avm2::tracegen::TestTraceContainer::as_rows
std::vector< AvmFullRowConstRef > as_rows() const
Definition test_trace_container.cpp:41
bb::numeric::uint256_t
Definition uint256.hpp:32
builder
AluTraceBuilder builder
Definition alu.test.cpp:123
trace
TestTraceContainer trace
Definition data_copy.test.cpp:59
a
FF a
Definition field_gt.test.cpp:51
b
FF b
Definition field_gt.test.cpp:52
expected_result
bool expected_result
Definition field_gt.test.cpp:53
field_gt.hpp
field_gt_event.hpp
flavor_settings.hpp
full_row.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:151
bb::avm2::get_tag_max_value
uint256_t get_tag_max_value(ValueTag tag)
Definition tagged_value.cpp:193
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:123
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