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
4#include "barretenberg/vm2/generated/columns.hpp"
5#include "barretenberg/vm2/generated/relations/lookups_memory.hpp"
6#include "barretenberg/vm2/simulation/events/memory_event.hpp"
7#include "barretenberg/vm2/testing/macros.hpp"
8#include "barretenberg/vm2/tracegen/memory_trace.hpp"
9#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
10
11namespace bb::avm2::tracegen {
12namespace {
13
14using R = TestTraceContainer::Row;
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.
24 std::vector<MemoryEvent> events = {
25 {
26 .execution_clk = UINT32_MAX,
27 .mode = simulation::MemoryMode::WRITE,
28 .addr = 20,
29 .value = MemoryValue::from_tag(MemoryTag::U8, 6),
30 .space_id = 1001,
31 },
32 {
33 .execution_clk = 20,
34 .mode = simulation::MemoryMode::WRITE,
35 .addr = 5,
36 .value = MemoryValue::from_tag(MemoryTag::U8, 3),
37 .space_id = 1000,
38 },
39 {
40 .execution_clk = UINT32_MAX,
41 .mode = simulation::MemoryMode::READ,
42 .addr = 20,
43 .value = MemoryValue::from_tag(MemoryTag::U8, 5),
44 .space_id = 1001,
45 },
46 {
47 .execution_clk = 10,
48 .mode = simulation::MemoryMode::WRITE,
49 .addr = 6,
50 .value = MemoryValue::from_tag(MemoryTag::U8, 4),
51 .space_id = 1000,
52 },
53 {
54 .execution_clk = 20,
55 .mode = simulation::MemoryMode::READ,
56 .addr = 5,
57 .value = MemoryValue::from_tag(MemoryTag::U8, 2),
58 .space_id = 1000,
59 },
60 {
61 .execution_clk = 15,
62 .mode = simulation::MemoryMode::WRITE,
63 .addr = 5,
64 .value = MemoryValue::from_tag(MemoryTag::U8, 1),
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
99 std::vector<MemoryEvent> events = {
100 {
101 // 1) WRITE: space_id = 1, addr = 10, clk = 1000, value = 1, tag = U1
102 .execution_clk = 1000,
103 .mode = simulation::MemoryMode::WRITE,
104 .addr = 10,
105 .value = MemoryValue::from_tag(MemoryTag::U1, 1),
106 .space_id = 1,
107 },
108 {
109 // 2) WRITE: space_id = 1, addr = 10, clk = 1001, value = 0, tag = U1
110 .execution_clk = 1001,
111 .mode = simulation::MemoryMode::WRITE,
112 .addr = 10,
113 .value = MemoryValue::from_tag(MemoryTag::U1, 0),
114 .space_id = 1,
115 },
116 {
117 // 3) READ: space_id = 1, addr = 11, clk = 1002, value = 0, tag = FF
118 .execution_clk = 1002,
119 .mode = simulation::MemoryMode::READ,
120 .addr = 11,
121 .value = MemoryValue::from_tag(MemoryTag::FF, 0),
122 .space_id = 1,
123 },
124 {
125 // 4) WRITE: space_id = 1, addr = 11, clk = 1002, value = 5, tag = U128
126 .execution_clk = 1002,
127 .mode = simulation::MemoryMode::WRITE,
128 .addr = 11,
129 .value = MemoryValue::from_tag(MemoryTag::U128, 5),
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,
135 .mode = simulation::MemoryMode::WRITE,
136 .addr = 11,
137 .value = MemoryValue::from_tag(MemoryTag::U64, 7),
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,
143 .mode = simulation::MemoryMode::WRITE,
144 .addr = 11,
145 .value = MemoryValue::from_tag(MemoryTag::U8, 8),
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,
151 .mode = simulation::MemoryMode::WRITE,
152 .addr = 12,
153 .value = MemoryValue::from_tag(MemoryTag::U16, 9),
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,
159 .mode = simulation::MemoryMode::WRITE,
160 .addr = 12,
161 .value = MemoryValue::from_tag(MemoryTag::U32, 10),
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,
167 .mode = simulation::MemoryMode::READ,
168 .addr = 12,
169 .value = MemoryValue::from_tag(MemoryTag::U32, 10),
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,
175 .mode = simulation::MemoryMode::READ,
176 .addr = 12,
177 .value = MemoryValue::from_tag(MemoryTag::U32, 10),
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_diff, 1), // (next timestamp - current timestamp - 1 (two writes)) 2003 - 2001 - 1
202 ROW_FIELD_EQ(memory_limb_0_, 1),
203 ROW_FIELD_EQ(memory_limb_1_, 0),
204 ROW_FIELD_EQ(memory_limb_2_, 0),
205 ROW_FIELD_EQ(memory_max_bits, 1)));
206
207 // 2) WRITE: space_id = 1, addr = 10, clk = 1001, value = 0, tag = U1
208 EXPECT_THAT(rows.at(2),
209 AllOf(ROW_FIELD_EQ(memory_sel, 1),
210 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
211 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
212 ROW_FIELD_EQ(memory_sel_rng_write, 1),
213 ROW_FIELD_EQ(memory_last_access, 1),
214 ROW_FIELD_EQ(memory_space_id, 1),
215 ROW_FIELD_EQ(memory_address, 10),
216 ROW_FIELD_EQ(memory_clk, 1001),
217 ROW_FIELD_EQ(memory_rw, 1),
218 ROW_FIELD_EQ(memory_value, 0),
219 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U1)),
220 ROW_FIELD_EQ(memory_diff, 1), // next address - current address (11 - 10)
221 ROW_FIELD_EQ(memory_limb_0_, 1),
222 ROW_FIELD_EQ(memory_limb_1_, 0),
223 ROW_FIELD_EQ(memory_limb_2_, 0),
224 ROW_FIELD_EQ(memory_max_bits, 1)));
225
226 // 3) READ: space_id = 1, addr = 11, clk = 1002, value = 0, tag = FF
227 EXPECT_THAT(rows.at(3),
228 AllOf(ROW_FIELD_EQ(memory_sel, 1),
229 ROW_FIELD_EQ(memory_sel_tag_is_ff, 1),
230 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
231 ROW_FIELD_EQ(memory_sel_rng_write, 0),
232 ROW_FIELD_EQ(memory_last_access, 0),
233 ROW_FIELD_EQ(memory_space_id, 1),
234 ROW_FIELD_EQ(memory_address, 11),
235 ROW_FIELD_EQ(memory_clk, 1002),
236 ROW_FIELD_EQ(memory_rw, 0),
237 ROW_FIELD_EQ(memory_value, 0),
238 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::FF)),
239 ROW_FIELD_EQ(memory_diff, 1), // next timestamp - current timestamp = 2005 - 2004 = 1
240 ROW_FIELD_EQ(memory_limb_0_, 1),
241 ROW_FIELD_EQ(memory_limb_1_, 0),
242 ROW_FIELD_EQ(memory_limb_2_, 0),
243 ROW_FIELD_EQ(memory_max_bits, 0)));
244
245 // 4) WRITE: space_id = 1, addr = 11, clk = 1002, value = 5, tag = U128
246 EXPECT_THAT(rows.at(4),
247 AllOf(ROW_FIELD_EQ(memory_sel, 1),
248 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
249 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
250 ROW_FIELD_EQ(memory_sel_rng_write, 1),
251 ROW_FIELD_EQ(memory_last_access, 1),
252 ROW_FIELD_EQ(memory_space_id, 1),
253 ROW_FIELD_EQ(memory_address, 11),
254 ROW_FIELD_EQ(memory_clk, 1002),
255 ROW_FIELD_EQ(memory_rw, 1),
256 ROW_FIELD_EQ(memory_value, 5),
257 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U128)),
258 ROW_FIELD_EQ(memory_diff, 0xFFFELLU << 32), // next address - current address = 2^32 *(2^16 - 2
259 ROW_FIELD_EQ(memory_limb_0_, 0),
260 ROW_FIELD_EQ(memory_limb_1_, 0),
261 ROW_FIELD_EQ(memory_limb_2_, 0xFFFELLU),
262 ROW_FIELD_EQ(memory_max_bits, 128)));
263
264 // 5) WRITE: space_id = 2^16-1, addr = 11, clk = 1, value = 7, tag = U64
265 EXPECT_THAT(rows.at(5),
266 AllOf(ROW_FIELD_EQ(memory_sel, 1),
267 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
268 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
269 ROW_FIELD_EQ(memory_sel_rng_write, 1),
270 ROW_FIELD_EQ(memory_last_access, 0),
271 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
272 ROW_FIELD_EQ(memory_address, 11),
273 ROW_FIELD_EQ(memory_clk, 1),
274 ROW_FIELD_EQ(memory_rw, 1),
275 ROW_FIELD_EQ(memory_value, 7),
276 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U64)),
277 ROW_FIELD_EQ(memory_diff, 1), // next timestamp - current timestamp = 5 - 3 - 1 (two writes)
278 ROW_FIELD_EQ(memory_limb_0_, 1),
279 ROW_FIELD_EQ(memory_limb_1_, 0),
280 ROW_FIELD_EQ(memory_limb_2_, 0),
281 ROW_FIELD_EQ(memory_max_bits, 64)));
282
283 // 6) WRITE: space_id = 2^16-1, addr = 11, clk = 2, value = 8, tag = U8
284 EXPECT_THAT(rows.at(6),
285 AllOf(ROW_FIELD_EQ(memory_sel, 1),
286 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
287 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
288 ROW_FIELD_EQ(memory_sel_rng_write, 1),
289 ROW_FIELD_EQ(memory_last_access, 1),
290 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
291 ROW_FIELD_EQ(memory_address, 11),
292 ROW_FIELD_EQ(memory_clk, 2),
293 ROW_FIELD_EQ(memory_rw, 1),
294 ROW_FIELD_EQ(memory_value, 8),
295 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U8)),
296 ROW_FIELD_EQ(memory_diff, 1), // next address - current address
297 ROW_FIELD_EQ(memory_limb_0_, 1),
298 ROW_FIELD_EQ(memory_limb_1_, 0),
299 ROW_FIELD_EQ(memory_limb_2_, 0),
300 ROW_FIELD_EQ(memory_max_bits, 8)));
301
302 // 7) WRITE: space_id = 2^16-1, addr = 12, clk = 3, value = 9, tag = U16
303 EXPECT_THAT(rows.at(7),
304 AllOf(ROW_FIELD_EQ(memory_sel, 1),
305 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
306 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
307 ROW_FIELD_EQ(memory_sel_rng_write, 1),
308 ROW_FIELD_EQ(memory_last_access, 0),
309 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
310 ROW_FIELD_EQ(memory_address, 12),
311 ROW_FIELD_EQ(memory_clk, 3),
312 ROW_FIELD_EQ(memory_rw, 1),
313 ROW_FIELD_EQ(memory_value, 9),
314 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U16)),
315 ROW_FIELD_EQ(memory_diff, 1), // next timestamp - current timestamp = 9 - 7 - 1
316 ROW_FIELD_EQ(memory_limb_0_, 1),
317 ROW_FIELD_EQ(memory_limb_1_, 0),
318 ROW_FIELD_EQ(memory_limb_2_, 0),
319 ROW_FIELD_EQ(memory_max_bits, 16)));
320
321 // 8) WRITE: space_id = 2^16-1, addr = 12, clk = 4, value = 10, tag = U32
322 EXPECT_THAT(rows.at(8),
323 AllOf(ROW_FIELD_EQ(memory_sel, 1),
324 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
325 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
326 ROW_FIELD_EQ(memory_sel_rng_write, 1),
327 ROW_FIELD_EQ(memory_last_access, 0),
328 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
329 ROW_FIELD_EQ(memory_address, 12),
330 ROW_FIELD_EQ(memory_clk, 4),
331 ROW_FIELD_EQ(memory_rw, 1),
332 ROW_FIELD_EQ(memory_value, 10),
333 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U32)),
334 ROW_FIELD_EQ(memory_diff, 9), // next timestamp - current timestamp = 18 - 9
335 ROW_FIELD_EQ(memory_limb_0_, 9),
336 ROW_FIELD_EQ(memory_limb_1_, 0),
337 ROW_FIELD_EQ(memory_limb_2_, 0),
338 ROW_FIELD_EQ(memory_max_bits, 32)));
339
340 // 9) READ: space_id = 2^16-1, addr = 12, clk = 9, value = 10, tag = U32
341 EXPECT_THAT(rows.at(9),
342 AllOf(ROW_FIELD_EQ(memory_sel, 1),
343 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
344 ROW_FIELD_EQ(memory_sel_rng_chk, 1),
345 ROW_FIELD_EQ(memory_sel_rng_write, 0),
346 ROW_FIELD_EQ(memory_last_access, 0),
347 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
348 ROW_FIELD_EQ(memory_address, 12),
349 ROW_FIELD_EQ(memory_clk, 9),
350 ROW_FIELD_EQ(memory_rw, 0),
351 ROW_FIELD_EQ(memory_value, 10),
352 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U32)),
353 ROW_FIELD_EQ(memory_diff, 0), // next timestamp - current timestamp = 18 - 18
354 ROW_FIELD_EQ(memory_limb_0_, 0),
355 ROW_FIELD_EQ(memory_limb_1_, 0),
356 ROW_FIELD_EQ(memory_limb_2_, 0),
357 ROW_FIELD_EQ(memory_max_bits, 32)));
358
359 // 10) READ: space_id = 2^16-1, addr = 12, clk = 9, value = 10, tag = U32
360 EXPECT_THAT(rows.at(10),
361 AllOf(ROW_FIELD_EQ(memory_sel, 1),
362 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
363 ROW_FIELD_EQ(memory_sel_rng_chk, 0),
364 ROW_FIELD_EQ(memory_sel_rng_write, 0),
365 ROW_FIELD_EQ(memory_last_access, 1),
366 ROW_FIELD_EQ(memory_space_id, 0xFFFF),
367 ROW_FIELD_EQ(memory_address, 12),
368 ROW_FIELD_EQ(memory_clk, 9),
369 ROW_FIELD_EQ(memory_rw, 0),
370 ROW_FIELD_EQ(memory_value, 10),
371 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U32)),
372 ROW_FIELD_EQ(memory_diff, 0), // next timestamp - current timestamp = 18 - 0
373 ROW_FIELD_EQ(memory_limb_0_, 0),
374 ROW_FIELD_EQ(memory_limb_1_, 0),
375 ROW_FIELD_EQ(memory_limb_2_, 0),
376 ROW_FIELD_EQ(memory_max_bits, 32)));
377}
378
379// Single memory entry
380TEST(MemoryTraceGenTest, SingleEntry)
381{
382 TestTraceContainer trace;
383
384 MemoryTraceBuilder memory_trace_builder;
385
386 std::vector<MemoryEvent> events = {
387 {
388 .execution_clk = 137,
389 .mode = simulation::MemoryMode::WRITE,
390 .addr = 10,
391 .value = MemoryValue::from_tag(MemoryTag::U16, 12345),
392 .space_id = 17,
393 },
394 };
395
396 memory_trace_builder.process(events, trace);
397
398 const auto& rows = trace.as_rows();
399 ASSERT_EQ(rows.size(), 2);
400
401 // 1) WRITE: space_id = 17, addr = 10, clk = 137, value = 12345, tag = U16
402 EXPECT_THAT(rows.at(1),
403 AllOf(ROW_FIELD_EQ(memory_sel, 1),
404 ROW_FIELD_EQ(memory_sel_tag_is_ff, 0),
405 ROW_FIELD_EQ(memory_sel_rng_chk, 0),
406 ROW_FIELD_EQ(memory_sel_rng_write, 1),
407 ROW_FIELD_EQ(memory_last_access, 1),
408 ROW_FIELD_EQ(memory_space_id, 17),
409 ROW_FIELD_EQ(memory_address, 10),
410 ROW_FIELD_EQ(memory_clk, 137),
411 ROW_FIELD_EQ(memory_rw, 1),
412 ROW_FIELD_EQ(memory_value, 12345),
413 ROW_FIELD_EQ(memory_tag, static_cast<uint8_t>(MemoryTag::U16)),
414 ROW_FIELD_EQ(memory_diff, 0),
415 ROW_FIELD_EQ(memory_limb_0_, 0),
416 ROW_FIELD_EQ(memory_limb_1_, 0),
417 ROW_FIELD_EQ(memory_limb_2_, 0),
418 ROW_FIELD_EQ(memory_max_bits, 16)));
419}
420
421} // namespace
422} // namespace bb::avm2::tracegen
bb::avm2::TaggedValue::from_tag
static TaggedValue from_tag(ValueTag tag, FF value)
Definition tagged_value.cpp:227
bb::avm2::tracegen::TestTraceContainer::as_rows
std::vector< AvmFullRowConstRef > as_rows() const
Definition test_trace_container.cpp:28
trace
TestTraceContainer trace
Definition data_copy.test.cpp:63
lookups_memory.hpp
ROW_FIELD_EQ
#define ROW_FIELD_EQ(field_name, expression)
Definition macros.hpp:7
memory_event.hpp
memory_trace.hpp
bb::TEST
TEST(BoomerangMegaCircuitBuilder, BasicCircuit)
Definition graph_description_megacircuitbuilder.test.cpp:22
std::get
constexpr decltype(auto) get(::tuplet::tuple< T... > &&t) noexcept
Definition tuple.hpp:13
test_trace_container.hpp