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
245 auto c = alu.div(a, b);
246
247 EXPECT_EQ(c, MemoryValue::from<uint32_t>(2));
248
249 auto events = alu_event_emitter.dump_events();
250 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::DIV, .a = a, .b = b, .c = c }));
251}
252
253TEST(AvmSimulationAluTest, DivU128)
254{
255 EventEmitter<AluEvent> alu_event_emitter;
256 StrictMock<MockGreaterThan> gt;
257 StrictMock<MockFieldGreaterThan> field_gt;
258 StrictMock<MockRangeCheck> range_check;
259 Alu alu(gt, field_gt, range_check, alu_event_emitter);
260
261 uint128_t max = static_cast<uint128_t>(get_tag_max_value(MemoryTag::U128));
262
263 auto a = MemoryValue::from<uint128_t>(max);
264 auto b = MemoryValue::from<uint128_t>(2);
265
266 EXPECT_CALL(gt, gt(b, MemoryValue::from<uint128_t>(1))).WillOnce(Return(true));
267
268 // For u128s, we range check c_lo, c_hi, b_lo, b_hi:
269 EXPECT_CALL(range_check, assert_range(_, 64)).Times(4);
270
271 auto c = alu.div(a, b);
272
273 EXPECT_EQ(c, MemoryValue::from<uint128_t>(max >> 1));
274
275 auto events = alu_event_emitter.dump_events();
276 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::DIV, .a = a, .b = b, .c = c }));
277}
278
279TEST(AvmSimulationAluTest, DivByZero)
280{
281 EventEmitter<AluEvent> alu_event_emitter;
282 StrictMock<MockGreaterThan> gt;
283 StrictMock<MockFieldGreaterThan> field_gt;
284 StrictMock<MockRangeCheck> range_check;
285 Alu alu(gt, field_gt, range_check, alu_event_emitter);
286
287 auto a = MemoryValue::from<uint32_t>(6);
288 auto b = MemoryValue::from<uint32_t>(0);
289
290 EXPECT_THROW(alu.div(a, b), AluException);
291
292 auto events = alu_event_emitter.dump_events();
293 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::DIV, .a = a, .b = b, .error = true }));
294}
295
296TEST(AvmSimulationAluTest, DivFFTag)
297{
298 EventEmitter<AluEvent> alu_event_emitter;
299 StrictMock<MockGreaterThan> gt;
300 StrictMock<MockFieldGreaterThan> field_gt;
301 StrictMock<MockRangeCheck> range_check;
302 Alu alu(gt, field_gt, range_check, alu_event_emitter);
303
304 auto a = MemoryValue::from<FF>(2);
305 auto b = MemoryValue::from<FF>(2);
306
307 EXPECT_THROW(alu.div(a, b), AluException);
308
309 auto events = alu_event_emitter.dump_events();
310 EXPECT_THAT(events,
311 ElementsAre(AluEvent{ .operation = AluOperation::DIV,
312 .a = a,
313 .b = b,
314 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
315 .error = true }));
316}
317
318TEST(AvmSimulationAluTest, FDiv)
319{
320 EventEmitter<AluEvent> alu_event_emitter;
321 StrictMock<MockGreaterThan> gt;
322 StrictMock<MockFieldGreaterThan> field_gt;
323 StrictMock<MockRangeCheck> range_check;
324 Alu alu(gt, field_gt, range_check, alu_event_emitter);
325
326 auto a = MemoryValue::from<FF>(FF::modulus - 4);
327 auto b = MemoryValue::from<FF>(2);
328
329 auto c = alu.fdiv(a, b);
330
331 EXPECT_EQ(c, MemoryValue::from<FF>(FF::modulus - 2));
332
333 auto events = alu_event_emitter.dump_events();
334 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::FDIV, .a = a, .b = b, .c = c }));
335}
336
337TEST(AvmSimulationAluTest, FDivByZero)
338{
339 EventEmitter<AluEvent> alu_event_emitter;
340 StrictMock<MockGreaterThan> gt;
341 StrictMock<MockFieldGreaterThan> field_gt;
342 StrictMock<MockRangeCheck> range_check;
343 Alu alu(gt, field_gt, range_check, alu_event_emitter);
344
345 auto a = MemoryValue::from<FF>(FF::modulus - 4);
346 auto b = MemoryValue::from<FF>(0);
347
348 EXPECT_THROW(alu.fdiv(a, b), AluException);
349
350 auto events = alu_event_emitter.dump_events();
351 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::FDIV, .a = a, .b = b, .error = true }));
352}
353
354TEST(AvmSimulationAluTest, FDivNonFFTag)
355{
356 EventEmitter<AluEvent> alu_event_emitter;
357 StrictMock<MockGreaterThan> gt;
358 StrictMock<MockFieldGreaterThan> field_gt;
359 StrictMock<MockRangeCheck> range_check;
360 Alu alu(gt, field_gt, range_check, alu_event_emitter);
361
362 auto a = MemoryValue::from<uint64_t>(2);
363 auto b = MemoryValue::from<uint64_t>(2);
364
365 EXPECT_THROW(alu.fdiv(a, b), AluException);
366
367 auto events = alu_event_emitter.dump_events();
368 EXPECT_THAT(events,
369 ElementsAre(AluEvent{ .operation = AluOperation::FDIV,
370 .a = a,
371 .b = b,
372 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
373 .error = true }));
374}
375
376TEST(AvmSimulationAluTest, LT)
377{
378 EventEmitter<AluEvent> alu_event_emitter;
379 StrictMock<MockGreaterThan> gt;
380 StrictMock<MockFieldGreaterThan> field_gt;
381 StrictMock<MockRangeCheck> range_check;
382 Alu alu(gt, field_gt, range_check, alu_event_emitter);
383
384 auto a = MemoryValue::from<uint32_t>(1);
385 auto b = MemoryValue::from<uint32_t>(2);
386
387 EXPECT_CALL(gt, gt(b, a)).WillOnce(Return(true));
388
389 auto c = alu.lt(a, b);
390
391 EXPECT_EQ(c, MemoryValue::from<uint1_t>(1));
392
393 auto events = alu_event_emitter.dump_events();
394 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LT, .a = a, .b = b, .c = c }));
395}
396
397TEST(AvmSimulationAluTest, LTFF)
398{
399 EventEmitter<AluEvent> alu_event_emitter;
400 StrictMock<MockGreaterThan> gt;
401 StrictMock<MockFieldGreaterThan> field_gt;
402 StrictMock<MockRangeCheck> range_check;
403 Alu alu(gt, field_gt, range_check, alu_event_emitter);
404
405 auto a = MemoryValue::from<FF>(FF::modulus - 3);
406 auto b = MemoryValue::from<FF>(2);
407
408 EXPECT_CALL(gt, gt(b, a)).WillOnce(Return(false));
409
410 auto c = alu.lt(a, b);
411
412 EXPECT_EQ(c, MemoryValue::from<uint1_t>(0));
413
414 auto events = alu_event_emitter.dump_events();
415 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LT, .a = a, .b = b, .c = c }));
416}
417
418TEST(AvmSimulationAluTest, NegativeLTTag)
419{
420 EventEmitter<AluEvent> alu_event_emitter;
421 StrictMock<MockGreaterThan> gt;
422 StrictMock<MockFieldGreaterThan> field_gt;
423 StrictMock<MockRangeCheck> range_check;
424 Alu alu(gt, field_gt, range_check, alu_event_emitter);
425
426 auto a = MemoryValue::from<uint32_t>(1);
427 auto b = MemoryValue::from<uint64_t>(2);
428
429 EXPECT_THROW(alu.lt(a, b), AluException);
430
431 auto events = alu_event_emitter.dump_events();
432 EXPECT_THAT(events,
433 ElementsAre(AluEvent{ .operation = AluOperation::LT,
434 .a = a,
435 .b = b,
436 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
437 .error = true }));
438}
439
440TEST(AvmSimulationAluTest, LTE)
441{
442 EventEmitter<AluEvent> alu_event_emitter;
443 StrictMock<MockGreaterThan> gt;
444 StrictMock<MockFieldGreaterThan> field_gt;
445 StrictMock<MockRangeCheck> range_check;
446 Alu alu(gt, field_gt, range_check, alu_event_emitter);
447
448 auto a = MemoryValue::from<uint32_t>(1);
449 auto b = MemoryValue::from<uint32_t>(2);
450
451 EXPECT_CALL(gt, gt(a, b)).WillOnce(Return(false));
452
453 auto c = alu.lte(a, b);
454
455 EXPECT_EQ(c, MemoryValue::from<uint1_t>(1));
456
457 auto events = alu_event_emitter.dump_events();
458 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LTE, .a = a, .b = b, .c = c }));
459}
460
461TEST(AvmSimulationAluTest, LTEEq)
462{
463 EventEmitter<AluEvent> alu_event_emitter;
464 StrictMock<MockGreaterThan> gt;
465 StrictMock<MockFieldGreaterThan> field_gt;
466 StrictMock<MockRangeCheck> range_check;
467 Alu alu(gt, field_gt, range_check, alu_event_emitter);
468
469 auto a = MemoryValue::from<uint128_t>(2);
470 auto b = MemoryValue::from<uint128_t>(2);
471
472 EXPECT_CALL(gt, gt(a, b)).WillOnce(Return(false));
473
474 auto c = alu.lte(a, b);
475
476 EXPECT_EQ(c, MemoryValue::from<uint1_t>(1));
477
478 auto events = alu_event_emitter.dump_events();
479 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LTE, .a = a, .b = b, .c = c }));
480}
481
482TEST(AvmSimulationAluTest, LTEFF)
483{
484 EventEmitter<AluEvent> alu_event_emitter;
485 StrictMock<MockGreaterThan> gt;
486 StrictMock<MockFieldGreaterThan> field_gt;
487 StrictMock<MockRangeCheck> range_check;
488 Alu alu(gt, field_gt, range_check, alu_event_emitter);
489
490 auto a = MemoryValue::from<FF>(FF::modulus - 3);
491 auto b = MemoryValue::from<FF>(2);
492
493 EXPECT_CALL(gt, gt(a, b)).WillOnce(Return(true));
494
495 auto c = alu.lte(a, b);
496
497 EXPECT_EQ(c, MemoryValue::from<uint1_t>(0));
498
499 auto events = alu_event_emitter.dump_events();
500 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LTE, .a = a, .b = b, .c = c }));
501}
502
503// TODO(MW): Required? Same path as ADD tag error tests
504TEST(AvmSimulationAluTest, NegativeLTETag)
505{
506 EventEmitter<AluEvent> alu_event_emitter;
507 StrictMock<MockGreaterThan> gt;
508 StrictMock<MockFieldGreaterThan> field_gt;
509 StrictMock<MockRangeCheck> range_check;
510 Alu alu(gt, field_gt, range_check, alu_event_emitter);
511
512 auto a = MemoryValue::from<uint32_t>(1);
513 auto b = MemoryValue::from<uint64_t>(2);
514
515 EXPECT_THROW(alu.lte(a, b), AluException);
516
517 auto events = alu_event_emitter.dump_events();
518 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::LTE, .a = a, .b = b, .error = true }));
519}
520
521TEST(AvmSimulationAluTest, EQEquality)
522{
523 EventEmitter<AluEvent> alu_event_emitter;
524 StrictMock<MockGreaterThan> gt;
525 StrictMock<MockFieldGreaterThan> field_gt;
526 StrictMock<MockRangeCheck> range_check;
527 Alu alu(gt, field_gt, range_check, alu_event_emitter);
528
529 auto a = MemoryValue::from<uint128_t>(123456789);
530 auto b = MemoryValue::from<uint128_t>(123456789);
531
532 auto c = alu.eq(a, b);
533
534 EXPECT_EQ(c, MemoryValue::from<uint1_t>(1));
535
536 auto events = alu_event_emitter.dump_events();
537 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::EQ, .a = a, .b = b, .c = c, .error = false }));
538}
539
540TEST(AvmSimulationAluTest, EQInequality)
541{
542 EventEmitter<AluEvent> alu_event_emitter;
543 StrictMock<MockGreaterThan> gt;
544 StrictMock<MockFieldGreaterThan> field_gt;
545 StrictMock<MockRangeCheck> range_check;
546 Alu alu(gt, field_gt, range_check, alu_event_emitter);
547
548 auto a = MemoryValue::from<FF>(123456789);
549 auto b = MemoryValue::from<FF>(123456788);
550
551 auto c = alu.eq(a, b);
552
553 EXPECT_EQ(c, MemoryValue::from<uint1_t>(0));
554
555 auto events = alu_event_emitter.dump_events();
556 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::EQ, .a = a, .b = b, .c = c, .error = false }));
557}
558
559TEST(AvmSimulationAluTest, EQTagError)
560{
561 EventEmitter<AluEvent> alu_event_emitter;
562 StrictMock<MockGreaterThan> gt;
563 StrictMock<MockFieldGreaterThan> field_gt;
564 StrictMock<MockRangeCheck> range_check;
565 Alu alu(gt, field_gt, range_check, alu_event_emitter);
566
567 auto a = MemoryValue::from<uint1_t>(1);
568 auto b = MemoryValue::from<uint8_t>(1);
569
570 EXPECT_THROW(alu.eq(a, b), AluException);
571
572 auto events = alu_event_emitter.dump_events();
573 EXPECT_THAT(events,
574 ElementsAre(AluEvent{ .operation = AluOperation::EQ,
575 .a = a,
576 .b = b,
577 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
578 .error = true }));
579}
580
581TEST(AvmSimulationAluTest, NotBasic)
582{
583 EventEmitter<AluEvent> alu_event_emitter;
584 StrictMock<MockGreaterThan> gt;
585 StrictMock<MockFieldGreaterThan> field_gt;
586 StrictMock<MockRangeCheck> range_check;
587 Alu alu(gt, field_gt, range_check, alu_event_emitter);
588
589 const auto a = MemoryValue::from<uint64_t>(98321);
590 const auto b = alu.op_not(a);
591
592 EXPECT_EQ(b, ~a);
593
594 auto events = alu_event_emitter.dump_events();
595 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::NOT, .a = a, .b = b, .error = false }));
596}
597
598TEST(AvmSimulationAluTest, NotFFTagError)
599{
600 EventEmitter<AluEvent> alu_event_emitter;
601 StrictMock<MockGreaterThan> gt;
602 StrictMock<MockFieldGreaterThan> field_gt;
603 StrictMock<MockRangeCheck> range_check;
604 Alu alu(gt, field_gt, range_check, alu_event_emitter);
605
606 auto a = MemoryValue::from<FF>(FF::modulus - 3);
607
608 EXPECT_THROW(alu.op_not(a), AluException);
609
610 auto events = alu_event_emitter.dump_events();
611 EXPECT_THAT(events,
612 ElementsAre(AluEvent{ .operation = AluOperation::NOT,
613 .a = a,
614 .b = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
615 .error = true }));
616}
617
618TEST(AvmSimulationAluTest, Shl)
619{
620 EventEmitter<AluEvent> alu_event_emitter;
621 StrictMock<MockGreaterThan> gt;
622 StrictMock<MockFieldGreaterThan> field_gt;
623 StrictMock<MockRangeCheck> range_check;
624 Alu alu(gt, field_gt, range_check, alu_event_emitter);
625
626 auto a = MemoryValue::from<uint32_t>(64);
627 auto b = MemoryValue::from<uint32_t>(2);
628
629 // a_lo and a_hi range checks:
630 EXPECT_CALL(range_check, assert_range(64, 30)).Times(1);
631 EXPECT_CALL(range_check, assert_range(0, 2)).Times(1);
632
633 auto c = alu.shl(a, b);
634
635 EXPECT_EQ(c, MemoryValue::from<uint32_t>(256));
636
637 auto events = alu_event_emitter.dump_events();
638 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SHL, .a = a, .b = b, .c = c }));
639}
640
641TEST(AvmSimulationAluTest, ShlOverflow)
642{
643 EventEmitter<AluEvent> alu_event_emitter;
644 StrictMock<MockGreaterThan> gt;
645 StrictMock<MockFieldGreaterThan> field_gt;
646 StrictMock<MockRangeCheck> range_check;
647 Alu alu(gt, field_gt, range_check, alu_event_emitter);
648
649 auto a = MemoryValue::from<uint32_t>(64);
650 auto b = MemoryValue::from<uint32_t>(100);
651
652 // a_lo and a_hi range checks:
653 EXPECT_CALL(range_check, assert_range(68, 32)).Times(1);
654 EXPECT_CALL(range_check, assert_range(0, 32)).Times(1);
655
656 auto c = alu.shl(a, b);
657
658 EXPECT_EQ(c, MemoryValue::from<uint32_t>(0));
659
660 auto events = alu_event_emitter.dump_events();
661 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SHL, .a = a, .b = b, .c = c }));
662}
663
664// Useful to test bitwise shifts larger than 128 bits.
665TEST(AvmSimulationAluTest, ShlOverflowU128)
666{
667 EventEmitter<AluEvent> alu_event_emitter;
668 StrictMock<MockGreaterThan> gt;
669 StrictMock<MockFieldGreaterThan> field_gt;
670 StrictMock<MockRangeCheck> range_check;
671 Alu alu(gt, field_gt, range_check, alu_event_emitter);
672
673 auto a = MemoryValue::from<uint128_t>(177);
674 auto b = MemoryValue::from<uint128_t>(129);
675
676 // a_lo and a_hi range checks:
677 EXPECT_CALL(range_check, assert_range(1, 128)).Times(1);
678 EXPECT_CALL(range_check, assert_range(0, 128)).Times(1);
679
680 auto c = alu.shl(a, b);
681
682 auto events = alu_event_emitter.dump_events();
683 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SHL, .a = a, .b = b, .c = c }));
684}
685
686TEST(AvmSimulationAluTest, NegativeShlTagMismatch)
687{
688 EventEmitter<AluEvent> alu_event_emitter;
689 StrictMock<MockGreaterThan> gt;
690 StrictMock<MockFieldGreaterThan> field_gt;
691 StrictMock<MockRangeCheck> range_check;
692 Alu alu(gt, field_gt, range_check, alu_event_emitter);
693
694 auto a = MemoryValue::from<uint32_t>(64);
695 auto b = MemoryValue::from<uint64_t>(2);
696
697 EXPECT_THROW(alu.shl(a, b), AluException);
698
699 auto events = alu_event_emitter.dump_events();
700 EXPECT_THAT(events,
701 ElementsAre(AluEvent{ .operation = AluOperation::SHL,
702 .a = a,
703 .b = b,
704 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
705 .error = true }));
706}
707
708TEST(AvmSimulationAluTest, Shr)
709{
710 EventEmitter<AluEvent> alu_event_emitter;
711 StrictMock<MockGreaterThan> gt;
712 StrictMock<MockFieldGreaterThan> field_gt;
713 StrictMock<MockRangeCheck> range_check;
714 Alu alu(gt, field_gt, range_check, alu_event_emitter);
715
716 auto a = MemoryValue::from<uint32_t>(64);
717 auto b = MemoryValue::from<uint32_t>(2);
718
719 // a_lo and a_hi range checks:
720 EXPECT_CALL(range_check, assert_range(0, 2)).Times(1);
721 EXPECT_CALL(range_check, assert_range(16, 30)).Times(1);
722
723 auto c = alu.shr(a, b);
724
725 EXPECT_EQ(c, MemoryValue::from<uint32_t>(16));
726
727 auto events = alu_event_emitter.dump_events();
728 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SHR, .a = a, .b = b, .c = c }));
729}
730
731// Useful to test bitwise shifts larger than 128 bits.
732TEST(AvmSimulationAluTest, ShrOverflowU128)
733{
734 EventEmitter<AluEvent> alu_event_emitter;
735 StrictMock<MockGreaterThan> gt;
736 StrictMock<MockFieldGreaterThan> field_gt;
737 StrictMock<MockRangeCheck> range_check;
738 Alu alu(gt, field_gt, range_check, alu_event_emitter);
739
740 auto a = MemoryValue::from<uint128_t>(177);
741 auto b = MemoryValue::from<uint128_t>(129);
742
743 // a_lo and a_hi range checks:
744 EXPECT_CALL(range_check, assert_range(1, 128)).Times(1);
745 EXPECT_CALL(range_check, assert_range(0, 128)).Times(1);
746
747 auto c = alu.shr(a, b);
748
749 auto events = alu_event_emitter.dump_events();
750 EXPECT_THAT(events, ElementsAre(AluEvent{ .operation = AluOperation::SHR, .a = a, .b = b, .c = c }));
751}
752
753TEST(AvmSimulationAluTest, ShrFFTag)
754{
755 EventEmitter<AluEvent> alu_event_emitter;
756 StrictMock<MockGreaterThan> gt;
757 StrictMock<MockFieldGreaterThan> field_gt;
758 StrictMock<MockRangeCheck> range_check;
759 Alu alu(gt, field_gt, range_check, alu_event_emitter);
760
761 auto a = MemoryValue::from<FF>(64);
762 auto b = MemoryValue::from<FF>(2);
763
764 EXPECT_THROW(alu.shr(a, b), AluException);
765
766 auto events = alu_event_emitter.dump_events();
767 EXPECT_THAT(events,
768 ElementsAre(AluEvent{ .operation = AluOperation::SHR,
769 .a = a,
770 .b = b,
771 .c = MemoryValue::from_tag(static_cast<MemoryTag>(0), 0),
772 .error = true }));
773}
774
775TEST(AvmSimulationAluTest, TruncateTrivial)
776{
777 EventEmitter<AluEvent> alu_event_emitter;
778 StrictMock<MockGreaterThan> gt;
779 StrictMock<MockFieldGreaterThan> field_gt;
780 StrictMock<MockRangeCheck> range_check;
781 Alu alu(gt, field_gt, range_check, alu_event_emitter);
782
783 FF a = 8762;
784
785 auto b = alu.truncate(a, static_cast<MemoryTag>(MemoryTag::U16));
786 auto c = MemoryValue::from<uint16_t>(8762);
787 EXPECT_EQ(b, c);
788
789 auto events = alu_event_emitter.dump_events();
790 EXPECT_THAT(events,
791 ElementsAre(AluEvent{ .operation = AluOperation::TRUNCATE,
792 .a = MemoryValue::from_tag(MemoryTag::FF, a),
793 .b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(MemoryTag::U16)),
794 .c = c,
795 .error = false }));
796}
797
798TEST(AvmSimulationAluTest, TruncateLess128Bits)
799{
800 EventEmitter<AluEvent> alu_event_emitter;
801 StrictMock<MockGreaterThan> gt;
802 StrictMock<MockFieldGreaterThan> field_gt;
803 StrictMock<MockRangeCheck> range_check;
804 Alu alu(gt, field_gt, range_check, alu_event_emitter);
805
806 FF a = (1 << 16) + 12222;
807
808 EXPECT_CALL(range_check, assert_range(1, 112)).Times(1);
809
810 auto b = alu.truncate(a, static_cast<MemoryTag>(MemoryTag::U16));
811 auto c = MemoryValue::from<uint16_t>(12222);
812 EXPECT_EQ(b, c);
813
814 auto events = alu_event_emitter.dump_events();
815 EXPECT_THAT(events,
816 ElementsAre(AluEvent{ .operation = AluOperation::TRUNCATE,
817 .a = MemoryValue::from_tag(MemoryTag::FF, a),
818 .b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(MemoryTag::U16)),
819 .c = c,
820 .error = false }));
821}
822
823TEST(AvmSimulationAluTest, TruncateGreater128Bits)
824{
825 EventEmitter<AluEvent> alu_event_emitter;
826 StrictMock<MockGreaterThan> gt;
827 StrictMock<MockFieldGreaterThan> field_gt;
828 StrictMock<MockRangeCheck> range_check;
829 Alu alu(gt, field_gt, range_check, alu_event_emitter);
830
831 FF a = (static_cast<uint256_t>(176) << 175) + (static_cast<uint256_t>(234) << 32) + 123456789;
832 U256Decomposition decomposition_a = { .lo = (static_cast<uint128_t>(234) << 32) + 123456789, .hi = 176 };
833
834 EXPECT_CALL(range_check, assert_range(234, 96)).Times(1);
835 EXPECT_CALL(field_gt, canon_dec(a)).Times(1).WillOnce(Return(decomposition_a));
836
837 auto b = alu.truncate(a, static_cast<MemoryTag>(MemoryTag::U32));
838 auto c = MemoryValue::from<uint32_t>(123456789);
839
840 EXPECT_EQ(b, c);
841
842 auto events = alu_event_emitter.dump_events();
843 EXPECT_THAT(events,
844 ElementsAre(AluEvent{ .operation = AluOperation::TRUNCATE,
845 .a = MemoryValue::from_tag(MemoryTag::FF, a),
846 .b = MemoryValue::from_tag(MemoryTag::FF, static_cast<uint8_t>(MemoryTag::U32)),
847 .c = c,
848 .error = false }));
849}
850
851} // namespace
852} // namespace bb::avm2::simulation
alu_event.hpp
field_gt
FieldGreaterThan field_gt
Definition alu_integration.test.cpp:64
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
range_check
RangeCheck range_check
Definition data_copy.test.cpp:53
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::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:44
bb::field< bb::Bn254FrParams >::modulus
static constexpr uint256_t modulus
Definition field_declarations.hpp:197