Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
memory_trace.test.cpp
Go to the documentation of this file.
1#include <gmock/gmock.h>
2#include <gtest/gtest.h>
3
10
11namespace bb::avm2::tracegen {
12namespace {
13
15using C = Column;
16using simulation::MemoryEvent;
17
18TEST(MemoryTraceGenTest, Sorting)
19{
20 TestTraceContainer trace;
21
22 // We use .value field to check that the events are sorted correctly. The values
23 // are set to be in increasing order once the events are sorted.
25 {
26 .execution_clk = UINT32_MAX,
28 .addr = 20,
30 .space_id = 1001,
31 },
32 {
33 .execution_clk = 20,
35 .addr = 5,
37 .space_id = 1000,
38 },
39 {
40 .execution_clk = UINT32_MAX,
42 .addr = 20,
44 .space_id = 1001,
45 },
46 {
47 .execution_clk = 10,
49 .addr = 6,
51 .space_id = 1000,
52 },
53 {
54 .execution_clk = 20,
56 .addr = 5,
58 .space_id = 1000,
59 },
60 {
61 .execution_clk = 15,
63 .addr = 5,
65 .space_id = 1000,
66 },
67 };
68
69 MemoryTraceBuilder memory_trace_builder;
70 memory_trace_builder.process(events, trace);
71
72 const auto& rows = trace.as_rows();
73
74 // Add an empty row at the beginning.
75 ASSERT_EQ(rows.size(), 7);
76
77 for (uint32_t i = 0; i < trace.as_rows().size(); i++) {
78 EXPECT_THAT(rows.at(i), ROW_FIELD_EQ(memory_value, i));
79 }
80}
81
82TEST(MemoryTraceGenTest, MultipleEntries)
83{
84 TestTraceContainer trace;
85
86 MemoryTraceBuilder memory_trace_builder;
87
88 // The events are already sorted.
89 // 1) WRITE: space_id = 1, addr = 10, clk = 1000, value = 1, tag = U1
90 // 2) WRITE: space_id = 1, addr = 10, clk = 1001, value = 0, tag = U1
91 // 3) READ: space_id = 1, addr = 11, clk = 1002, value = 0, tag = FF
92 // 4) WRITE: space_id = 1, addr = 11, clk = 1002, value = 5, tag = U128
93 // 5) WRITE: space_id = 2^16-1, addr = 11, clk = 1, value = 7, tag = U64
94 // 6) WRITE: space_id = 2^16-1, addr = 11, clk = 2, value = 8, tag = U8
95 // 7) WRITE: space_id = 2^16-1, addr = 12, clk = 3, value = 9, tag = U16
96 // 8) WRITE: space_id = 2^16-1, addr = 12, clk = 4, value = 10, tag = U32
97 // 9) READ: space_id = 2^16-1, addr = 12, clk = 4, value = 10, tag = U32
98 // 10) READ: space_id = 2^16-1, addr = 12, clk = 4, value = 10, tag = U32
100 {
101 // 1) WRITE: space_id = 1, addr = 10, clk = 1000, value = 1, tag = U1
102 .execution_clk = 1000,
104 .addr = 10,
106 .space_id = 1,
107 },
108 {
109 // 2) WRITE: space_id = 1, addr = 10, clk = 1001, value = 0, tag = U1
110 .execution_clk = 1001,
112 .addr = 10,
114 .space_id = 1,
115 },
116 {
117 // 3) READ: space_id = 1, addr = 11, clk = 1002, value = 0, tag = FF
118 .execution_clk = 1002,
120 .addr = 11,
122 .space_id = 1,
123 },
124 {
125 // 4) WRITE: space_id = 1, addr = 11, clk = 1002, value = 5, tag = U128
126 .execution_clk = 1002,
128 .addr = 11,
130 .space_id = 1,
131 },
132 {
133 // 5) WRITE: space_id = 2^16-1, addr = 11, clk = 1, value = 7, tag = U64
134 .execution_clk = 1,
136 .addr = 11,
138 .space_id = 0xFFFF,
139 },
140 {
141 // 6) WRITE: space_id = 2^16-1, addr = 11, clk = 2, value = 8, tag = U8
142 .execution_clk = 2,
144 .addr = 11,
146 .space_id = 0xFFFF,
147 },
148 {
149 // 7) WRITE: space_id = 2^16-1, addr = 12, clk = 3, value = 9, tag = U16
150 .execution_clk = 3,
152 .addr = 12,
154 .space_id = 0xFFFF,
155 },
156 {
157 // 8) WRITE: space_id = 2^16-1, addr = 12, clk = 4, value = 10, tag = U32
158 .execution_clk = 4,
160 .addr = 12,
162 .space_id = 0xFFFF,
163 },
164 {
165 // 9) READ: space_id = 2^16-1, addr = 12, clk = 9, value = 10, tag = U32
166 .execution_clk = 9,
168 .addr = 12,
170 .space_id = 0xFFFF,
171 },
172 {
173 // 10) READ: space_id = 2^16-1, addr = 12, clk = 9, value = 10, tag = U32
174 .execution_clk = 9,
176 .addr = 12,
178 .space_id = 0xFFFF,
179 },
180 };
181
182 memory_trace_builder.process(events, trace);
183
184 const auto& rows = trace.as_rows();
185 ASSERT_EQ(rows.size(), 11);
186
187 // 1) WRITE: space_id = 1, addr = 10, clk = 1000, value = 1, tag = U1
188 EXPECT_THAT(
189 rows.at(1),
190 AllOf(ROW_FIELD_EQ(memory_sel, 1),
191 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
192 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
193 ROW_FIELD_EQ(memory_sel_rng_write, 1),
194 ROW_FIELD_EQ(memory_last_access, 0),
195 ROW_FIELD_EQ(memory_space_id, 1),
196 ROW_FIELD_EQ(memory_address, 10),
197 ROW_FIELD_EQ(memory_clk, 1000),
198 ROW_FIELD_EQ(memory_rw, 1),
199 ROW_FIELD_EQ(memory_value, 1),
200 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U1)),
201 ROW_FIELD_EQ(memory_global_addr, (1ULL << 32) + 10),
202 ROW_FIELD_EQ(memory_timestamp, 2001),
203 ROW_FIELD_EQ(memory_diff, 1), // (next timestamp - current timestamp - 1 (two writes)) 2003 - 2001 - 1
204 ROW_FIELD_EQ(memory_limb_0_, 1),
205 ROW_FIELD_EQ(memory_limb_1_, 0),
206 ROW_FIELD_EQ(memory_limb_2_, 0),
207 ROW_FIELD_EQ(memory_max_bits, 1)));
208
209 // 2) WRITE: space_id = 1, addr = 10, clk = 1001, value = 0, tag = U1
210 EXPECT_THAT(rows.at(2),
211 AllOf(ROW_FIELD_EQ(memory_sel, 1),
212 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
213 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
214 ROW_FIELD_EQ(memory_sel_rng_write, 1),
215 ROW_FIELD_EQ(memory_last_access, 1),
216 ROW_FIELD_EQ(memory_space_id, 1),
217 ROW_FIELD_EQ(memory_address, 10),
218 ROW_FIELD_EQ(memory_clk, 1001),
219 ROW_FIELD_EQ(memory_rw, 1),
220 ROW_FIELD_EQ(memory_value, 0),
221 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U1)),
222 ROW_FIELD_EQ(memory_global_addr, (1ULL << 32) + 10),
223 ROW_FIELD_EQ(memory_timestamp, 2003),
224 ROW_FIELD_EQ(memory_diff, 1), // next address - current address (11 - 10)
225 ROW_FIELD_EQ(memory_limb_0_, 1),
226 ROW_FIELD_EQ(memory_limb_1_, 0),
227 ROW_FIELD_EQ(memory_limb_2_, 0),
228 ROW_FIELD_EQ(memory_max_bits, 1)));
229
230 // 3) READ: space_id = 1, addr = 11, clk = 1002, value = 0, tag = FF
231 EXPECT_THAT(rows.at(3),
232 AllOf(ROW_FIELD_EQ(memory_sel, 1),
233 ROW_FIELD_EQ(memory_sel_tag_is_ff, 1),
234 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
235 ROW_FIELD_EQ(memory_sel_rng_write, 0),
236 ROW_FIELD_EQ(memory_last_access, 0),
237 ROW_FIELD_EQ(memory_space_id, 1),
238 ROW_FIELD_EQ(memory_address, 11),
239 ROW_FIELD_EQ(memory_clk, 1002),
240 ROW_FIELD_EQ(memory_rw, 0),
241 ROW_FIELD_EQ(memory_value, 0),
242 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::FF)),
243 ROW_FIELD_EQ(memory_global_addr, (1ULL << 32) + 11),
244 ROW_FIELD_EQ(memory_timestamp, 2004),
245 ROW_FIELD_EQ(memory_diff, 1), // next timestamp - current timestamp = 2005 - 2004 = 1
246 ROW_FIELD_EQ(memory_limb_0_, 1),
247 ROW_FIELD_EQ(memory_limb_1_, 0),
248 ROW_FIELD_EQ(memory_limb_2_, 0),
249 ROW_FIELD_EQ(memory_max_bits, 0)));
250
251 // 4) WRITE: space_id = 1, addr = 11, clk = 1002, value = 5, tag = U128
252 EXPECT_THAT(rows.at(4),
253 AllOf(ROW_FIELD_EQ(memory_sel, 1),
254 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
255 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
256 ROW_FIELD_EQ(memory_sel_rng_write, 1),
257 ROW_FIELD_EQ(memory_last_access, 1),
258 ROW_FIELD_EQ(memory_space_id, 1),
259 ROW_FIELD_EQ(memory_address, 11),
260 ROW_FIELD_EQ(memory_clk, 1002),
261 ROW_FIELD_EQ(memory_rw, 1),
262 ROW_FIELD_EQ(memory_value, 5),
263 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U128)),
264 ROW_FIELD_EQ(memory_global_addr, (1ULL << 32) + 11),
265 ROW_FIELD_EQ(memory_timestamp, 2005),
266 ROW_FIELD_EQ(memory_diff, 0xFFFELLU << 32), // next address - current address = 2^32 *(2^16 - 2
267 ROW_FIELD_EQ(memory_limb_0_, 0),
268 ROW_FIELD_EQ(memory_limb_1_, 0),
269 ROW_FIELD_EQ(memory_limb_2_, 0xFFFELLU),
270 ROW_FIELD_EQ(memory_max_bits, 128)));
271
272 // 5) WRITE: space_id = 2^16-1, addr = 11, clk = 1, value = 7, tag = U64
273 EXPECT_THAT(rows.at(5),
274 AllOf(ROW_FIELD_EQ(memory_sel, 1),
275 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
276 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
277 ROW_FIELD_EQ(memory_sel_rng_write, 1),
278 ROW_FIELD_EQ(memory_last_access, 0),
279 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
280 ROW_FIELD_EQ(memory_address, 11),
281 ROW_FIELD_EQ(memory_clk, 1),
282 ROW_FIELD_EQ(memory_rw, 1),
283 ROW_FIELD_EQ(memory_value, 7),
284 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U64)),
285 ROW_FIELD_EQ(memory_global_addr, (0xFFFFULL << 32) + 11),
286 ROW_FIELD_EQ(memory_timestamp, 3),
287 ROW_FIELD_EQ(memory_diff, 1), // next timestamp - current timestamp = 5 - 3 - 1 (two writes)
288 ROW_FIELD_EQ(memory_limb_0_, 1),
289 ROW_FIELD_EQ(memory_limb_1_, 0),
290 ROW_FIELD_EQ(memory_limb_2_, 0),
291 ROW_FIELD_EQ(memory_max_bits, 64)));
292
293 // 6) WRITE: space_id = 2^16-1, addr = 11, clk = 2, value = 8, tag = U8
294 EXPECT_THAT(rows.at(6),
295 AllOf(ROW_FIELD_EQ(memory_sel, 1),
296 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
297 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
298 ROW_FIELD_EQ(memory_sel_rng_write, 1),
299 ROW_FIELD_EQ(memory_last_access, 1),
300 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
301 ROW_FIELD_EQ(memory_address, 11),
302 ROW_FIELD_EQ(memory_clk, 2),
303 ROW_FIELD_EQ(memory_rw, 1),
304 ROW_FIELD_EQ(memory_value, 8),
305 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U8)),
306 ROW_FIELD_EQ(memory_global_addr, (0xFFFFULL << 32) + 11),
307 ROW_FIELD_EQ(memory_timestamp, 5),
308 ROW_FIELD_EQ(memory_diff, 1), // next address - current address
309 ROW_FIELD_EQ(memory_limb_0_, 1),
310 ROW_FIELD_EQ(memory_limb_1_, 0),
311 ROW_FIELD_EQ(memory_limb_2_, 0),
312 ROW_FIELD_EQ(memory_max_bits, 8)));
313
314 // 7) WRITE: space_id = 2^16-1, addr = 12, clk = 3, value = 9, tag = U16
315 EXPECT_THAT(rows.at(7),
316 AllOf(ROW_FIELD_EQ(memory_sel, 1),
317 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
318 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
319 ROW_FIELD_EQ(memory_sel_rng_write, 1),
320 ROW_FIELD_EQ(memory_last_access, 0),
321 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
322 ROW_FIELD_EQ(memory_address, 12),
323 ROW_FIELD_EQ(memory_clk, 3),
324 ROW_FIELD_EQ(memory_rw, 1),
325 ROW_FIELD_EQ(memory_value, 9),
326 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U16)),
327 ROW_FIELD_EQ(memory_global_addr, (0xFFFFULL << 32) + 12),
328 ROW_FIELD_EQ(memory_timestamp, 7),
329 ROW_FIELD_EQ(memory_diff, 1), // next timestamp - current timestamp = 9 - 7 - 1
330 ROW_FIELD_EQ(memory_limb_0_, 1),
331 ROW_FIELD_EQ(memory_limb_1_, 0),
332 ROW_FIELD_EQ(memory_limb_2_, 0),
333 ROW_FIELD_EQ(memory_max_bits, 16)));
334
335 // 8) WRITE: space_id = 2^16-1, addr = 12, clk = 4, value = 10, tag = U32
336 EXPECT_THAT(rows.at(8),
337 AllOf(ROW_FIELD_EQ(memory_sel, 1),
338 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
339 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
340 ROW_FIELD_EQ(memory_sel_rng_write, 1),
341 ROW_FIELD_EQ(memory_last_access, 0),
342 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
343 ROW_FIELD_EQ(memory_address, 12),
344 ROW_FIELD_EQ(memory_clk, 4),
345 ROW_FIELD_EQ(memory_rw, 1),
346 ROW_FIELD_EQ(memory_value, 10),
347 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U32)),
348 ROW_FIELD_EQ(memory_global_addr, (0xFFFFULL << 32) + 12),
349 ROW_FIELD_EQ(memory_timestamp, 9),
350 ROW_FIELD_EQ(memory_diff, 9), // next timestamp - current timestamp = 18 - 9
351 ROW_FIELD_EQ(memory_limb_0_, 9),
352 ROW_FIELD_EQ(memory_limb_1_, 0),
353 ROW_FIELD_EQ(memory_limb_2_, 0),
354 ROW_FIELD_EQ(memory_max_bits, 32)));
355
356 // 9) READ: space_id = 2^16-1, addr = 12, clk = 9, value = 10, tag = U32
357 EXPECT_THAT(rows.at(9),
358 AllOf(ROW_FIELD_EQ(memory_sel, 1),
359 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
360 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
361 ROW_FIELD_EQ(memory_sel_rng_write, 0),
362 ROW_FIELD_EQ(memory_last_access, 0),
363 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
364 ROW_FIELD_EQ(memory_address, 12),
365 ROW_FIELD_EQ(memory_clk, 9),
366 ROW_FIELD_EQ(memory_rw, 0),
367 ROW_FIELD_EQ(memory_value, 10),
368 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U32)),
369 ROW_FIELD_EQ(memory_global_addr, (0xFFFFULL << 32) + 12),
370 ROW_FIELD_EQ(memory_timestamp, 18),
371 ROW_FIELD_EQ(memory_diff, 0), // next timestamp - current timestamp = 18 - 18
372 ROW_FIELD_EQ(memory_limb_0_, 0),
373 ROW_FIELD_EQ(memory_limb_1_, 0),
374 ROW_FIELD_EQ(memory_limb_2_, 0),
375 ROW_FIELD_EQ(memory_max_bits, 32)));
376
377 // 10) READ: space_id = 2^16-1, addr = 12, clk = 9, value = 10, tag = U32
378 EXPECT_THAT(rows.at(10),
379 AllOf(ROW_FIELD_EQ(memory_sel, 1),
380 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
381 ROW_FIELD_EQ(memory_sel_rng_chk, 0),
382 ROW_FIELD_EQ(memory_sel_rng_write, 0),
383 ROW_FIELD_EQ(memory_last_access, 1),
384 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
385 ROW_FIELD_EQ(memory_address, 12),
386 ROW_FIELD_EQ(memory_clk, 9),
387 ROW_FIELD_EQ(memory_rw, 0),
388 ROW_FIELD_EQ(memory_value, 10),
389 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U32)),
390 ROW_FIELD_EQ(memory_global_addr, (0xFFFFULL << 32) + 12),
391 ROW_FIELD_EQ(memory_timestamp, 18),
392 ROW_FIELD_EQ(memory_diff, 0), // next timestamp - current timestamp = 18 - 0
393 ROW_FIELD_EQ(memory_limb_0_, 0),
394 ROW_FIELD_EQ(memory_limb_1_, 0),
395 ROW_FIELD_EQ(memory_limb_2_, 0),
396 ROW_FIELD_EQ(memory_max_bits, 32)));
397}
398
399// Single memory entry
400TEST(MemoryTraceGenTest, SingleEntry)
401{
402 TestTraceContainer trace;
403
404 MemoryTraceBuilder memory_trace_builder;
405
406 std::vector<MemoryEvent> events = {
407 {
408 .execution_clk = 137,
410 .addr = 10,
411 .value = MemoryValue::from_tag(MemoryTag::U16, 12345),
412 .space_id = 17,
413 },
414 };
415
416 memory_trace_builder.process(events, trace);
417
418 const auto& rows = trace.as_rows();
419 ASSERT_EQ(rows.size(), 2);
420
421 // 1) WRITE: space_id = 17, addr = 10, clk = 137, value = 12345, tag = U16
422 EXPECT_THAT(rows.at(1),
423 AllOf(ROW_FIELD_EQ(memory_sel, 1),
424 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
425 ROW_FIELD_EQ(memory_sel_rng_chk, 0),
426 ROW_FIELD_EQ(memory_sel_rng_write, 1),
427 ROW_FIELD_EQ(memory_last_access, 1),
428 ROW_FIELD_EQ(memory_space_id, 17),
429 ROW_FIELD_EQ(memory_address, 10),
430 ROW_FIELD_EQ(memory_clk, 137),
431 ROW_FIELD_EQ(memory_rw, 1),
432 ROW_FIELD_EQ(memory_value, 12345),
433 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U16)),
434 ROW_FIELD_EQ(memory_global_addr, (17ULL << 32) + 10),
435 ROW_FIELD_EQ(memory_timestamp, 275),
436 ROW_FIELD_EQ(memory_diff, 0),
437 ROW_FIELD_EQ(memory_limb_0_, 0),
438 ROW_FIELD_EQ(memory_limb_1_, 0),
439 ROW_FIELD_EQ(memory_limb_2_, 0),
440 ROW_FIELD_EQ(memory_max_bits, 16)));
441}
442
443} // namespace
444} // namespace bb::avm2::tracegen
static TaggedValue from_tag(ValueTag tag, FF value)
std::vector< AvmFullRowConstRef > as_rows() const
TestTraceContainer trace
#define ROW_FIELD_EQ(field_name, expression)
Definition macros.hpp:15
TEST(EmitUnencryptedLogTest, Basic)
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13