Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
alu.test.cpp
Go to the documentation of this file.
1#include "barretenberg/vm2/simulation/gadgets/alu.hpp"
2
3#include <cstdint>
4#include <gmock/gmock.h>
5#include <gtest/gtest.h>
6
7#include "barretenberg/numeric/uint128/uint128.hpp"
8#include "barretenberg/vm2/common/memory_types.hpp"
9#include "barretenberg/vm2/simulation/events/alu_event.hpp"
10#include "barretenberg/vm2/simulation/events/event_emitter.hpp"
11#include "barretenberg/vm2/simulation/events/memory_event.hpp"
12#include "barretenberg/vm2/simulation/gadgets/memory.hpp"
13#include "barretenberg/vm2/simulation/testing/mock_context.hpp"
14#include "barretenberg/vm2/simulation/testing/mock_field_gt.hpp"
15#include "barretenberg/vm2/simulation/testing/mock_gt.hpp"
16#include "barretenberg/vm2/simulation/testing/mock_range_check.hpp"
17
18namespace bb::avm2::simulation {
19
20using ::testing::_;
21using ::testing::ElementsAre;
22using ::testing::Return;
23using ::testing::StrictMock;
24
25namespace {
26
27TEST(AvmSimulationAluTest, Add)
28{
29 EventEmitter<AluEvent> alu_event_emitter;
30 StrictMock<MockGreaterThan> gt;
31 StrictMock<MockFieldGreaterThan> field_gt;
32 StrictMock<MockRangeCheck> range_check;
33 Alu alu(gt, field_gt, range_check, alu_event_emitter);
34
35 auto a = MemoryValue::from<uint32_t>(1);
36 auto b = MemoryValue::from<uint32_t>(2);
37
38 auto c = alu.add(a, b);
39
40 EXPECT_EQ(c, MemoryValue::from<uint32_t>(3));
41
42 auto events = alu_event_emitter.dump_events();
43 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::ADD, .a = a, .b = b, .c = c }));
44}
45
46TEST(AvmSimulationAluTest, AddOverflow)
47{
48 EventEmitter<AluEvent> alu_event_emitter;
49 StrictMock<MockGreaterThan> gt;
50 StrictMock<MockFieldGreaterThan> field_gt;
51 StrictMock<MockRangeCheck> range_check;
52 Alu alu(gt, field_gt, range_check, alu_event_emitter);
53
54 auto a = MemoryValue::from<uint32_t>(static_cast<uint32_t>(get_tag_max_value(MemoryTag::U32)));
55 auto b = MemoryValue::from<uint32_t>(2);
56
57 auto c = alu.add(a, b);
58
59 EXPECT_EQ(c, MemoryValue::from<uint32_t>(1));
60
61 auto events = alu_event_emitter.dump_events();
62 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::ADD, .a = a, .b = b, .c = c }));
63}
64
65TEST(AvmSimulationAluTest, NegativeAddTag)
66{
67 EventEmitter<AluEvent> alu_event_emitter;
68 StrictMock<MockGreaterThan> gt;
69 StrictMock<MockFieldGreaterThan> field_gt;
70 StrictMock<MockRangeCheck> range_check;
71 Alu alu(gt, field_gt, range_check, alu_event_emitter);
72
73 auto a = MemoryValue::from<uint32_t>(1);
74 auto b = MemoryValue::from<uint64_t>(2);
75
76 EXPECT_THROW(alu.add(a, b), AluException);
77
78 auto events = alu_event_emitter.dump_events();
79 EXPECT_THAT(events,
80 ElementsAre(AluEvent{ .operation = AluOperation::ADD,
81 .a = a,
82 .b = b,
83 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
84 .error = true }));
85}
86
87TEST(AvmSimulationAluTest, Sub)
88{
89 EventEmitter<AluEvent> alu_event_emitter;
90 StrictMock<MockGreaterThan> gt;
91 StrictMock<MockFieldGreaterThan> field_gt;
92 StrictMock<MockRangeCheck> range_check;
93 Alu alu(gt, field_gt, range_check, alu_event_emitter);
94
95 auto a = MemoryValue::from<uint32_t>(2);
96 auto b = MemoryValue::from<uint32_t>(1);
97
98 auto c = alu.sub(a, b);
99
100 EXPECT_EQ(c, MemoryValue::from<uint32_t>(1));
101
102 auto events = alu_event_emitter.dump_events();
103 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SUB, .a = a, .b = b, .c = c }));
104}
105
106TEST(AvmSimulationAluTest, SubUnderflow)
107{
108 EventEmitter<AluEvent> alu_event_emitter;
109 StrictMock<MockGreaterThan> gt;
110 StrictMock<MockFieldGreaterThan> field_gt;
111 StrictMock<MockRangeCheck> range_check;
112 Alu alu(gt, field_gt, range_check, alu_event_emitter);
113
114 auto a = MemoryValue::from<uint64_t>(1);
115 auto b = MemoryValue::from<uint64_t>(2);
116
117 auto c = alu.sub(a, b);
118
119 EXPECT_EQ(c, MemoryValue::from_tag(MemoryTag::U64, get_tag_max_value(MemoryTag::U64)));
120
121 auto events = alu_event_emitter.dump_events();
122 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SUB, .a = a, .b = b, .c = c }));
123}
124
125TEST(AvmSimulationAluTest, SubFFUnderflow)
126{
127 EventEmitter<AluEvent> alu_event_emitter;
128 StrictMock<MockGreaterThan> gt;
129 StrictMock<MockFieldGreaterThan> field_gt;
130 StrictMock<MockRangeCheck> range_check;
131 Alu alu(gt, field_gt, range_check, alu_event_emitter);
132
133 auto a = MemoryValue::from<FF>(1);
134 auto b = MemoryValue::from<FF>(2);
135
136 auto c = alu.sub(a, b);
137
138 EXPECT_EQ(c, MemoryValue::from_tag(MemoryTag::FF, get_tag_max_value(MemoryTag::FF)));
139
140 auto events = alu_event_emitter.dump_events();
141 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SUB, .a = a, .b = b, .c = c }));
142}
143
144TEST(AvmSimulationAluTest, NegativeSubTag)
145{
146 EventEmitter<AluEvent> alu_event_emitter;
147 StrictMock<MockGreaterThan> gt;
148 StrictMock<MockFieldGreaterThan> field_gt;
149 StrictMock<MockRangeCheck> range_check;
150 Alu alu(gt, field_gt, range_check, alu_event_emitter);
151
152 auto a = MemoryValue::from<uint32_t>(2);
153 auto b = MemoryValue::from<uint64_t>(1);
154
155 EXPECT_THROW(alu.sub(a, b), AluException);
156
157 auto events = alu_event_emitter.dump_events();
158 EXPECT_THAT(events,
159 ElementsAre(AluEvent{ .operation = AluOperation::SUB,
160 .a = a,
161 .b = b,
162 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
163 .error = true }));
164}
165
166TEST(AvmSimulationAluTest, Mul)
167{
168 EventEmitter<AluEvent> alu_event_emitter;
169 StrictMock<MockGreaterThan> gt;
170 StrictMock<MockFieldGreaterThan> field_gt;
171 StrictMock<MockRangeCheck> range_check;
172 Alu alu(gt, field_gt, range_check, alu_event_emitter);
173
174 auto a = MemoryValue::from<uint32_t>(2);
175 auto b = MemoryValue::from<uint32_t>(3);
176
177 EXPECT_CALL(range_check, assert_range(_, 64)).Times(1);
178
179 auto c = alu.mul(a, b);
180
181 EXPECT_EQ(c, MemoryValue::from<uint32_t>(6));
182
183 auto events = alu_event_emitter.dump_events();
184 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::MUL, .a = a, .b = b, .c = c }));
185}
186
187TEST(AvmSimulationAluTest, MulOverflow)
188{
189 EventEmitter<AluEvent> alu_event_emitter;
190 StrictMock<MockGreaterThan> gt;
191 StrictMock<MockFieldGreaterThan> field_gt;
192 StrictMock<MockRangeCheck> range_check;
193 Alu alu(gt, field_gt, range_check, alu_event_emitter);
194
195 auto a = MemoryValue::from<uint32_t>(static_cast<uint32_t>(get_tag_max_value(MemoryTag::U32)));
196 auto b = MemoryValue::from<uint32_t>(2);
197
198 EXPECT_CALL(range_check, assert_range(_, 64)).Times(1);
199
200 auto c = alu.mul(a, b);
201
202 EXPECT_EQ(c, MemoryValue::from<uint32_t>(static_cast<uint32_t>(get_tag_max_value(MemoryTag::U32) - 1)));
203
204 auto events = alu_event_emitter.dump_events();
205 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::MUL, .a = a, .b = b, .c = c }));
206}
207
208TEST(AvmSimulationAluTest, MulOverflowU128)
209{
210 EventEmitter<AluEvent> alu_event_emitter;
211 StrictMock<MockGreaterThan> gt;
212 StrictMock<MockFieldGreaterThan> field_gt;
213 StrictMock<MockRangeCheck> range_check;
214 Alu alu(gt, field_gt, range_check, alu_event_emitter);
215
216 uint128_t max = static_cast<uint128_t>(get_tag_max_value(MemoryTag::U128));
217
218 auto a = MemoryValue::from<uint128_t>(max);
219 auto b = MemoryValue::from<uint128_t>(max - 3);
220
221 // For u128s, we range check a_lo, a_hi, b_lo, b_hi, and c_hi:
222 EXPECT_CALL(range_check, assert_range(_, 64)).Times(5);
223
224 auto c = alu.mul(a, b);
225
226 EXPECT_EQ(c, MemoryValue::from<uint128_t>(4));
227
228 auto events = alu_event_emitter.dump_events();
229 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::MUL, .a = a, .b = b, .c = c }));
230}
231
232TEST(AvmSimulationAluTest, Div)
233{
234 EventEmitter<AluEvent> alu_event_emitter;
235 StrictMock<MockGreaterThan> gt;
236 StrictMock<MockFieldGreaterThan> field_gt;
237 StrictMock<MockRangeCheck> range_check;
238 Alu alu(gt, field_gt, range_check, alu_event_emitter);
239
240 auto a = MemoryValue::from<uint32_t>(6);
241 auto b = MemoryValue::from<uint32_t>(3);
242
243 EXPECT_CALL(gt, gt(b, MemoryValue::from<uint32_t>(0))).WillOnce(Return(true));
244 EXPECT_CALL(range_check, assert_range(0, 32)).Times(1);
245
246 auto c = alu.div(a, b);
247
248 EXPECT_EQ(c, MemoryValue::from<uint32_t>(2));
249
250 auto events = alu_event_emitter.dump_events();
251 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::DIV, .a = a, .b = b, .c = c }));
252}
253
254TEST(AvmSimulationAluTest, DivU128)
255{
256 EventEmitter<AluEvent> alu_event_emitter;
257 StrictMock<MockGreaterThan> gt;
258 StrictMock<MockFieldGreaterThan> field_gt;
259 StrictMock<MockRangeCheck> range_check;
260 Alu alu(gt, field_gt, range_check, alu_event_emitter);
261
262 uint128_t max = static_cast<uint128_t>(get_tag_max_value(MemoryTag::U128));
263
264 auto a = MemoryValue::from<uint128_t>(max);
265 auto b = MemoryValue::from<uint128_t>(2);
266
267 EXPECT_CALL(gt, gt(b, MemoryValue::from<uint128_t>(1))).WillOnce(Return(true));
268
269 // Range check the remainder (1) fits within 128 bits:
270 EXPECT_CALL(range_check, assert_range(1, 128)).Times(1);
271 // For u128s, we range check c_lo, c_hi, b_lo, b_hi:
272 EXPECT_CALL(range_check, assert_range(_, 64)).Times(4);
273
274 auto c = alu.div(a, b);
275
276 EXPECT_EQ(c, MemoryValue::from<uint128_t>(max >> 1));
277
278 auto events = alu_event_emitter.dump_events();
279 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::DIV, .a = a, .b = b, .c = c }));
280}
281
282TEST(AvmSimulationAluTest, DivByZero)
283{
284 EventEmitter<AluEvent> alu_event_emitter;
285 StrictMock<MockGreaterThan> gt;
286 StrictMock<MockFieldGreaterThan> field_gt;
287 StrictMock<MockRangeCheck> range_check;
288 Alu alu(gt, field_gt, range_check, alu_event_emitter);
289
290 auto a = MemoryValue::from<uint32_t>(6);
291 auto b = MemoryValue::from<uint32_t>(0);
292
293 EXPECT_THROW(alu.div(a, b), AluException);
294
295 auto events = alu_event_emitter.dump_events();
296 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::DIV, .a = a, .b = b, .error = true }));
297}
298
299TEST(AvmSimulationAluTest, DivFFTag)
300{
301 EventEmitter<AluEvent> alu_event_emitter;
302 StrictMock<MockGreaterThan> gt;
303 StrictMock<MockFieldGreaterThan> field_gt;
304 StrictMock<MockRangeCheck> range_check;
305 Alu alu(gt, field_gt, range_check, alu_event_emitter);
306
307 auto a = MemoryValue::from<FF>(2);
308 auto b = MemoryValue::from<FF>(2);
309
310 EXPECT_THROW(alu.div(a, b), AluException);
311
312 auto events = alu_event_emitter.dump_events();
313 EXPECT_THAT(events,
314 ElementsAre(AluEvent{ .operation = AluOperation::DIV,
315 .a = a,
316 .b = b,
317 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
318 .error = true }));
319}
320
321TEST(AvmSimulationAluTest, FDiv)
322{
323 EventEmitter<AluEvent> alu_event_emitter;
324 StrictMock<MockGreaterThan> gt;
325 StrictMock<MockFieldGreaterThan> field_gt;
326 StrictMock<MockRangeCheck> range_check;
327 Alu alu(gt, field_gt, range_check, alu_event_emitter);
328
329 auto a = MemoryValue::from<FF>(FF::modulus - 4);
330 auto b = MemoryValue::from<FF>(2);
331
332 auto c = alu.fdiv(a, b);
333
334 EXPECT_EQ(c, MemoryValue::from<FF>(FF::modulus - 2));
335
336 auto events = alu_event_emitter.dump_events();
337 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::FDIV, .a = a, .b = b, .c = c }));
338}
339
340TEST(AvmSimulationAluTest, FDivByZero)
341{
342 EventEmitter<AluEvent> alu_event_emitter;
343 StrictMock<MockGreaterThan> gt;
344 StrictMock<MockFieldGreaterThan> field_gt;
345 StrictMock<MockRangeCheck> range_check;
346 Alu alu(gt, field_gt, range_check, alu_event_emitter);
347
348 auto a = MemoryValue::from<FF>(FF::modulus - 4);
349 auto b = MemoryValue::from<FF>(0);
350
351 EXPECT_THROW(alu.fdiv(a, b), AluException);
352
353 auto events = alu_event_emitter.dump_events();
354 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::FDIV, .a = a, .b = b, .error = true }));
355}
356
357TEST(AvmSimulationAluTest, FDivNonFFTag)
358{
359 EventEmitter<AluEvent> alu_event_emitter;
360 StrictMock<MockGreaterThan> gt;
361 StrictMock<MockFieldGreaterThan> field_gt;
362 StrictMock<MockRangeCheck> range_check;
363 Alu alu(gt, field_gt, range_check, alu_event_emitter);
364
365 auto a = MemoryValue::from<uint64_t>(2);
366 auto b = MemoryValue::from<uint64_t>(2);
367
368 EXPECT_THROW(alu.fdiv(a, b), AluException);
369
370 auto events = alu_event_emitter.dump_events();
371 EXPECT_THAT(events,
372 ElementsAre(AluEvent{ .operation = AluOperation::FDIV,
373 .a = a,
374 .b = b,
375 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
376 .error = true }));
377}
378
379TEST(AvmSimulationAluTest, LT)
380{
381 EventEmitter<AluEvent> alu_event_emitter;
382 StrictMock<MockGreaterThan> gt;
383 StrictMock<MockFieldGreaterThan> field_gt;
384 StrictMock<MockRangeCheck> range_check;
385 Alu alu(gt, field_gt, range_check, alu_event_emitter);
386
387 auto a = MemoryValue::from<uint32_t>(1);
388 auto b = MemoryValue::from<uint32_t>(2);
389
390 EXPECT_CALL(gt, gt(b, a)).WillOnce(Return(true));
391
392 auto c = alu.lt(a, b);
393
394 EXPECT_EQ(c, MemoryValue::from<uint1_t>(1));
395
396 auto events = alu_event_emitter.dump_events();
397 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LT, .a = a, .b = b, .c = c }));
398}
399
400TEST(AvmSimulationAluTest, LTFF)
401{
402 EventEmitter<AluEvent> alu_event_emitter;
403 StrictMock<MockGreaterThan> gt;
404 StrictMock<MockFieldGreaterThan> field_gt;
405 StrictMock<MockRangeCheck> range_check;
406 Alu alu(gt, field_gt, range_check, alu_event_emitter);
407
408 auto a = MemoryValue::from<FF>(FF::modulus - 3);
409 auto b = MemoryValue::from<FF>(2);
410
411 EXPECT_CALL(gt, gt(b, a)).WillOnce(Return(false));
412
413 auto c = alu.lt(a, b);
414
415 EXPECT_EQ(c, MemoryValue::from<uint1_t>(0));
416
417 auto events = alu_event_emitter.dump_events();
418 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LT, .a = a, .b = b, .c = c }));
419}
420
421TEST(AvmSimulationAluTest, NegativeLTTag)
422{
423 EventEmitter<AluEvent> alu_event_emitter;
424 StrictMock<MockGreaterThan> gt;
425 StrictMock<MockFieldGreaterThan> field_gt;
426 StrictMock<MockRangeCheck> range_check;
427 Alu alu(gt, field_gt, range_check, alu_event_emitter);
428
429 auto a = MemoryValue::from<uint32_t>(1);
430 auto b = MemoryValue::from<uint64_t>(2);
431
432 EXPECT_THROW(alu.lt(a, b), AluException);
433
434 auto events = alu_event_emitter.dump_events();
435 EXPECT_THAT(events,
436 ElementsAre(AluEvent{ .operation = AluOperation::LT,
437 .a = a,
438 .b = b,
439 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
440 .error = true }));
441}
442
443TEST(AvmSimulationAluTest, LTE)
444{
445 EventEmitter<AluEvent> alu_event_emitter;
446 StrictMock<MockGreaterThan> gt;
447 StrictMock<MockFieldGreaterThan> field_gt;
448 StrictMock<MockRangeCheck> range_check;
449 Alu alu(gt, field_gt, range_check, alu_event_emitter);
450
451 auto a = MemoryValue::from<uint32_t>(1);
452 auto b = MemoryValue::from<uint32_t>(2);
453
454 EXPECT_CALL(gt, gt(a, b)).WillOnce(Return(false));
455
456 auto c = alu.lte(a, b);
457
458 EXPECT_EQ(c, MemoryValue::from<uint1_t>(1));
459
460 auto events = alu_event_emitter.dump_events();
461 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LTE, .a = a, .b = b, .c = c }));
462}
463
464TEST(AvmSimulationAluTest, LTEEq)
465{
466 EventEmitter<AluEvent> alu_event_emitter;
467 StrictMock<MockGreaterThan> gt;
468 StrictMock<MockFieldGreaterThan> field_gt;
469 StrictMock<MockRangeCheck> range_check;
470 Alu alu(gt, field_gt, range_check, alu_event_emitter);
471
472 auto a = MemoryValue::from<uint128_t>(2);
473 auto b = MemoryValue::from<uint128_t>(2);
474
475 EXPECT_CALL(gt, gt(a, b)).WillOnce(Return(false));
476
477 auto c = alu.lte(a, b);
478
479 EXPECT_EQ(c, MemoryValue::from<uint1_t>(1));
480
481 auto events = alu_event_emitter.dump_events();
482 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LTE, .a = a, .b = b, .c = c }));
483}
484
485TEST(AvmSimulationAluTest, LTEFF)
486{
487 EventEmitter<AluEvent> alu_event_emitter;
488 StrictMock<MockGreaterThan> gt;
489 StrictMock<MockFieldGreaterThan> field_gt;
490 StrictMock<MockRangeCheck> range_check;
491 Alu alu(gt, field_gt, range_check, alu_event_emitter);
492
493 auto a = MemoryValue::from<FF>(FF::modulus - 3);
494 auto b = MemoryValue::from<FF>(2);
495
496 EXPECT_CALL(gt, gt(a, b)).WillOnce(Return(true));
497
498 auto c = alu.lte(a, b);
499
500 EXPECT_EQ(c, MemoryValue::from<uint1_t>(0));
501
502 auto events = alu_event_emitter.dump_events();
503 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LTE, .a = a, .b = b, .c = c }));
504}
505
506// TODO(MW): Required? Same path as ADD tag error tests
507TEST(AvmSimulationAluTest, NegativeLTETag)
508{
509 EventEmitter<AluEvent> alu_event_emitter;
510 StrictMock<MockGreaterThan> gt;
511 StrictMock<MockFieldGreaterThan> field_gt;
512 StrictMock<MockRangeCheck> range_check;
513 Alu alu(gt, field_gt, range_check, alu_event_emitter);
514
515 auto a = MemoryValue::from<uint32_t>(1);
516 auto b = MemoryValue::from<uint64_t>(2);
517
518 EXPECT_THROW(alu.lte(a, b), AluException);
519
520 auto events = alu_event_emitter.dump_events();
521 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LTE, .a = a, .b = b, .error = true }));
522}
523
524TEST(AvmSimulationAluTest, EQEquality)
525{
526 EventEmitter<AluEvent> alu_event_emitter;
527 StrictMock<MockGreaterThan> gt;
528 StrictMock<MockFieldGreaterThan> field_gt;
529 StrictMock<MockRangeCheck> range_check;
530 Alu alu(gt, field_gt, range_check, alu_event_emitter);
531
532 auto a = MemoryValue::from<uint128_t>(123456789);
533 auto b = MemoryValue::from<uint128_t>(123456789);
534
535 auto c = alu.eq(a, b);
536
537 EXPECT_EQ(c, MemoryValue::from<uint1_t>(1));
538
539 auto events = alu_event_emitter.dump_events();
540 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::EQ, .a = a, .b = b, .c = c, .error = false }));
541}
542
543TEST(AvmSimulationAluTest, EQInequality)
544{
545 EventEmitter<AluEvent> alu_event_emitter;
546 StrictMock<MockGreaterThan> gt;
547 StrictMock<MockFieldGreaterThan> field_gt;
548 StrictMock<MockRangeCheck> range_check;
549 Alu alu(gt, field_gt, range_check, alu_event_emitter);
550
551 auto a = MemoryValue::from<FF>(123456789);
552 auto b = MemoryValue::from<FF>(123456788);
553
554 auto c = alu.eq(a, b);
555
556 EXPECT_EQ(c, MemoryValue::from<uint1_t>(0));
557
558 auto events = alu_event_emitter.dump_events();
559 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::EQ, .a = a, .b = b, .c = c, .error = false }));
560}
561
562TEST(AvmSimulationAluTest, EQTagError)
563{
564 EventEmitter<AluEvent> alu_event_emitter;
565 StrictMock<MockGreaterThan> gt;
566 StrictMock<MockFieldGreaterThan> field_gt;
567 StrictMock<MockRangeCheck> range_check;
568 Alu alu(gt, field_gt, range_check, alu_event_emitter);
569
570 auto a = MemoryValue::from<uint1_t>(1);
571 auto b = MemoryValue::from<uint8_t>(1);
572
573 EXPECT_THROW(alu.eq(a, b), AluException);
574
575 auto events = alu_event_emitter.dump_events();
576 EXPECT_THAT(events,
577 ElementsAre(AluEvent{ .operation = AluOperation::EQ,
578 .a = a,
579 .b = b,
580 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
581 .error = true }));
582}
583
584TEST(AvmSimulationAluTest, NotBasic)
585{
586 EventEmitter<AluEvent> alu_event_emitter;
587 StrictMock<MockGreaterThan> gt;
588 StrictMock<MockFieldGreaterThan> field_gt;
589 StrictMock<MockRangeCheck> range_check;
590 Alu alu(gt, field_gt, range_check, alu_event_emitter);
591
592 const auto a = MemoryValue::from<uint64_t>(98321);
593 const auto b = alu.op_not(a);
594
595 EXPECT_EQ(b, ~a);
596
597 auto events = alu_event_emitter.dump_events();
598 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::NOT, .a = a, .b = b, .error = false }));
599}
600
601TEST(AvmSimulationAluTest, NotFFTagError)
602{
603 EventEmitter<AluEvent> alu_event_emitter;
604 StrictMock<MockGreaterThan> gt;
605 StrictMock<MockFieldGreaterThan> field_gt;
606 StrictMock<MockRangeCheck> range_check;
607 Alu alu(gt, field_gt, range_check, alu_event_emitter);
608
609 auto a = MemoryValue::from<FF>(FF::modulus - 3);
610
611 EXPECT_THROW(alu.op_not(a), AluException);
612
613 auto events = alu_event_emitter.dump_events();
614 EXPECT_THAT(events,
615 ElementsAre(AluEvent{ .operation = AluOperation::NOT,
616 .a = a,
617 .b = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
618 .error = true }));
619}
620
621TEST(AvmSimulationAluTest, Shl)
622{
623 EventEmitter<AluEvent> alu_event_emitter;
624 StrictMock<MockGreaterThan> gt;
625 StrictMock<MockFieldGreaterThan> field_gt;
626 StrictMock<MockRangeCheck> range_check;
627 Alu alu(gt, field_gt, range_check, alu_event_emitter);
628
629 auto a = MemoryValue::from<uint32_t>(64);
630 auto b = MemoryValue::from<uint32_t>(2);
631
632 // a_lo and a_hi range checks:
633 EXPECT_CALL(range_check, assert_range(64, 30)).Times(1);
634 EXPECT_CALL(range_check, assert_range(0, 2)).Times(1);
635
636 auto c = alu.shl(a, b);
637
638 EXPECT_EQ(c, MemoryValue::from<uint32_t>(256));
639
640 auto events = alu_event_emitter.dump_events();
641 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SHL, .a = a, .b = b, .c = c }));
642}
643
644TEST(AvmSimulationAluTest, ShlOverflow)
645{
646 EventEmitter<AluEvent> alu_event_emitter;
647 StrictMock<MockGreaterThan> gt;
648 StrictMock<MockFieldGreaterThan> field_gt;
649 StrictMock<MockRangeCheck> range_check;
650 Alu alu(gt, field_gt, range_check, alu_event_emitter);
651
652 auto a = MemoryValue::from<uint32_t>(64);
653 auto b = MemoryValue::from<uint32_t>(100);
654
655 // a_lo and a_hi range checks:
656 EXPECT_CALL(range_check, assert_range(68, 32)).Times(1);
657 EXPECT_CALL(range_check, assert_range(0, 32)).Times(1);
658
659 auto c = alu.shl(a, b);
660
661 EXPECT_EQ(c, MemoryValue::from<uint32_t>(0));
662
663 auto events = alu_event_emitter.dump_events();
664 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SHL, .a = a, .b = b, .c = c }));
665}
666
667// Useful to test bitwise shifts larger than 128 bits.
668TEST(AvmSimulationAluTest, ShlOverflowU128)
669{
670 EventEmitter<AluEvent> alu_event_emitter;
671 StrictMock<MockGreaterThan> gt;
672 StrictMock<MockFieldGreaterThan> field_gt;
673 StrictMock<MockRangeCheck> range_check;
674 Alu alu(gt, field_gt, range_check, alu_event_emitter);
675
676 auto a = MemoryValue::from<uint128_t>(177);
677 auto b = MemoryValue::from<uint128_t>(129);
678
679 // a_lo and a_hi range checks:
680 EXPECT_CALL(range_check, assert_range(1, 128)).Times(1);
681 EXPECT_CALL(range_check, assert_range(0, 128)).Times(1);
682
683 auto c = alu.shl(a, b);
684
685 auto events = alu_event_emitter.dump_events();
686 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SHL, .a = a, .b = b, .c = c }));
687}
688
689TEST(AvmSimulationAluTest, NegativeShlTagMismatch)
690{
691 EventEmitter<AluEvent> alu_event_emitter;
692 StrictMock<MockGreaterThan> gt;
693 StrictMock<MockFieldGreaterThan> field_gt;
694 StrictMock<MockRangeCheck> range_check;
695 Alu alu(gt, field_gt, range_check, alu_event_emitter);
696
697 auto a = MemoryValue::from<uint32_t>(64);
698 auto b = MemoryValue::from<uint64_t>(2);
699
700 EXPECT_THROW(alu.shl(a, b), AluException);
701
702 auto events = alu_event_emitter.dump_events();
703 EXPECT_THAT(events,
704 ElementsAre(AluEvent{ .operation = AluOperation::SHL,
705 .a = a,
706 .b = b,
707 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
708 .error = true }));
709}
710
711TEST(AvmSimulationAluTest, Shr)
712{
713 EventEmitter<AluEvent> alu_event_emitter;
714 StrictMock<MockGreaterThan> gt;
715 StrictMock<MockFieldGreaterThan> field_gt;
716 StrictMock<MockRangeCheck> range_check;
717 Alu alu(gt, field_gt, range_check, alu_event_emitter);
718
719 auto a = MemoryValue::from<uint32_t>(64);
720 auto b = MemoryValue::from<uint32_t>(2);
721
722 // a_lo and a_hi range checks:
723 EXPECT_CALL(range_check, assert_range(0, 2)).Times(1);
724 EXPECT_CALL(range_check, assert_range(16, 30)).Times(1);
725
726 auto c = alu.shr(a, b);
727
728 EXPECT_EQ(c, MemoryValue::from<uint32_t>(16));
729
730 auto events = alu_event_emitter.dump_events();
731 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SHR, .a = a, .b = b, .c = c }));
732}
733
734// Useful to test bitwise shifts larger than 128 bits.
735TEST(AvmSimulationAluTest, ShrOverflowU128)
736{
737 EventEmitter<AluEvent> alu_event_emitter;
738 StrictMock<MockGreaterThan> gt;
739 StrictMock<MockFieldGreaterThan> field_gt;
740 StrictMock<MockRangeCheck> range_check;
741 Alu alu(gt, field_gt, range_check, alu_event_emitter);
742
743 auto a = MemoryValue::from<uint128_t>(177);
744 auto b = MemoryValue::from<uint128_t>(129);
745
746 // a_lo and a_hi range checks:
747 EXPECT_CALL(range_check, assert_range(1, 128)).Times(1);
748 EXPECT_CALL(range_check, assert_range(0, 128)).Times(1);
749
750 auto c = alu.shr(a, b);
751
752 auto events = alu_event_emitter.dump_events();
753 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SHR, .a = a, .b = b, .c = c }));
754}
755
756TEST(AvmSimulationAluTest, ShrFFTag)
757{
758 EventEmitter<AluEvent> alu_event_emitter;
759 StrictMock<MockGreaterThan> gt;
760 StrictMock<MockFieldGreaterThan> field_gt;
761 StrictMock<MockRangeCheck> range_check;
762 Alu alu(gt, field_gt, range_check, alu_event_emitter);
763
764 auto a = MemoryValue::from<FF>(64);
765 auto b = MemoryValue::from<FF>(2);
766
767 EXPECT_THROW(alu.shr(a, b), AluException);
768
769 auto events = alu_event_emitter.dump_events();
770 EXPECT_THAT(events,
771 ElementsAre(AluEvent{ .operation = AluOperation::SHR,
772 .a = a,
773 .b = b,
774 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
775 .error = true }));
776}
777
778TEST(AvmSimulationAluTest, TruncateTrivial)
779{
780 EventEmitter<AluEvent> alu_event_emitter;
781 StrictMock<MockGreaterThan> gt;
782 StrictMock<MockFieldGreaterThan> field_gt;
783 StrictMock<MockRangeCheck> range_check;
784 Alu alu(gt, field_gt, range_check, alu_event_emitter);
785
786 FF a = 8762;
787
788 auto b = alu.truncate(a, static_cast<MemoryTag>(MemoryTag::U16));
789 auto c = MemoryValue::from<uint16_t>(8762);
790 EXPECT_EQ(b, c);
791
792 auto events = alu_event_emitter.dump_events();
793 EXPECT_THAT(events,
794 ElementsAre(AluEvent{ .operation = AluOperation::TRUNCATE,
795 .a = MemoryValue::from_tag(MemoryTag::FF, a),
796 .b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(MemoryTag::U16)),
797 .c = c,
798 .error = false }));
799}
800
801TEST(AvmSimulationAluTest, TruncateLess128Bits)
802{
803 EventEmitter<AluEvent> alu_event_emitter;
804 StrictMock<MockGreaterThan> gt;
805 StrictMock<MockFieldGreaterThan> field_gt;
806 StrictMock<MockRangeCheck> range_check;
807 Alu alu(gt, field_gt, range_check, alu_event_emitter);
808
809 FF a = (1 << 16) + 12222;
810
811 EXPECT_CALL(range_check, assert_range(1, 112)).Times(1);
812
813 auto b = alu.truncate(a, static_cast<MemoryTag>(MemoryTag::U16));
814 auto c = MemoryValue::from<uint16_t>(12222);
815 EXPECT_EQ(b, c);
816
817 auto events = alu_event_emitter.dump_events();
818 EXPECT_THAT(events,
819 ElementsAre(AluEvent{ .operation = AluOperation::TRUNCATE,
820 .a = MemoryValue::from_tag(MemoryTag::FF, a),
821 .b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(MemoryTag::U16)),
822 .c = c,
823 .error = false }));
824}
825
826TEST(AvmSimulationAluTest, TruncateGreater128Bits)
827{
828 EventEmitter<AluEvent> alu_event_emitter;
829 StrictMock<MockGreaterThan> gt;
830 StrictMock<MockFieldGreaterThan> field_gt;
831 StrictMock<MockRangeCheck> range_check;
832 Alu alu(gt, field_gt, range_check, alu_event_emitter);
833
834 FF a = (static_cast<uint256_t>(176) << 175) + (static_cast<uint256_t>(234) << 32) + 123456789;
835 U256Decomposition decomposition_a = { .lo = (static_cast<uint128_t>(234) << 32) + 123456789, .hi = 176 };
836
837 EXPECT_CALL(range_check, assert_range(234, 96)).Times(1);
838 EXPECT_CALL(field_gt, canon_dec(a)).Times(1).WillOnce(Return(decomposition_a));
839
840 auto b = alu.truncate(a, static_cast<MemoryTag>(MemoryTag::U32));
841 auto c = MemoryValue::from<uint32_t>(123456789);
842
843 EXPECT_EQ(b, c);
844
845 auto events = alu_event_emitter.dump_events();
846 EXPECT_THAT(events,
847 ElementsAre(AluEvent{ .operation = AluOperation::TRUNCATE,
848 .a = MemoryValue::from_tag(MemoryTag::FF, a),
849 .b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(MemoryTag::U32)),
850 .c = c,
851 .error = false }));
852}
853
854} // namespace
855} // namespace bb::avm2::simulation
alu_event.hpp
field_gt
FieldGreaterThan field_gt
Definition bc_retrieval.test.cpp:309
range_check
RangeCheck range_check
Definition bc_retrieval.test.cpp:308
bb::avm2::TaggedValue::from_tag
static TaggedValue from_tag(ValueTag tag, FF value)
Definition tagged_value.cpp:227
bb::numeric::uint256_t
Definition uint256.hpp:32
gt
GreaterThan gt
Definition data_copy.test.cpp:56
a
FF a
Definition field_gt.test.cpp:52
b
FF b
Definition field_gt.test.cpp:53
event_emitter.hpp
memory_event.hpp
memory_types.hpp
mock_context.hpp
mock_field_gt.hpp
mock_gt.hpp
mock_range_check.hpp
bb::avm2::simulation
AVM range check gadget for witness generation.
Definition address_derivation_event.hpp:6
bb::avm2::get_tag_max_value
uint256_t get_tag_max_value(ValueTag tag)
Definition tagged_value.cpp:204
bb::TEST
TEST(BoomerangMegaCircuitBuilder, BasicCircuit)
Definition graph_description_megacircuitbuilder.test.cpp:22
uint128_t
unsigned __int128 uint128_t
Definition serialize.hpp:45
bb::field< bb::Bn254FrParams >::modulus
static constexpr uint256_t modulus
Definition field_declarations.hpp:234
EnqueuedCallMutation::Add
@ Add