miden_core/operations/mod.rs
1use core::fmt;
2
3use super::Felt;
4mod decorators;
5pub use decorators::{
6 AssemblyOp, DebugOptions, Decorator, DecoratorIterator, DecoratorList, SignatureKind,
7};
8// OPERATIONS OP CODES
9// ================================================================================================
10use opcode_constants::*;
11use winter_utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
12
13/// Opcode patterns have the following meanings:
14/// - 00xxxxx operations do not shift the stack; constraint degree can be up to 2.
15/// - 010xxxx operations shift the stack the left; constraint degree can be up to 2.
16/// - 011xxxx operations shift the stack to the right; constraint degree can be up to 2.
17/// - 100xxx-: operations consume 4 range checks; constraint degree can be up to 3. These are used
18/// to encode most u32 operations.
19/// - 101xxx-: operations where constraint degree can be up to 3. These include control flow
20/// operations and some other operations requiring high degree constraints.
21/// - 11xxx--: operations where constraint degree can be up to 5. These include control flow
22/// operations and some other operations requiring very high degree constraints.
23#[rustfmt::skip]
24pub(super) mod opcode_constants {
25 pub const OPCODE_NOOP: u8 = 0b0000_0000;
26 pub const OPCODE_EQZ: u8 = 0b0000_0001;
27 pub const OPCODE_NEG: u8 = 0b0000_0010;
28 pub const OPCODE_INV: u8 = 0b0000_0011;
29 pub const OPCODE_INCR: u8 = 0b0000_0100;
30 pub const OPCODE_NOT: u8 = 0b0000_0101;
31 pub const OPCODE_FMPADD: u8 = 0b0000_0110;
32 pub const OPCODE_MLOAD: u8 = 0b0000_0111;
33 pub const OPCODE_SWAP: u8 = 0b0000_1000;
34 pub const OPCODE_CALLER: u8 = 0b0000_1001;
35 pub const OPCODE_MOVUP2: u8 = 0b0000_1010;
36 pub const OPCODE_MOVDN2: u8 = 0b0000_1011;
37 pub const OPCODE_MOVUP3: u8 = 0b0000_1100;
38 pub const OPCODE_MOVDN3: u8 = 0b0000_1101;
39 pub const OPCODE_ADVPOPW: u8 = 0b0000_1110;
40 pub const OPCODE_EXPACC: u8 = 0b0000_1111;
41
42 pub const OPCODE_MOVUP4: u8 = 0b0001_0000;
43 pub const OPCODE_MOVDN4: u8 = 0b0001_0001;
44 pub const OPCODE_MOVUP5: u8 = 0b0001_0010;
45 pub const OPCODE_MOVDN5: u8 = 0b0001_0011;
46 pub const OPCODE_MOVUP6: u8 = 0b0001_0100;
47 pub const OPCODE_MOVDN6: u8 = 0b0001_0101;
48 pub const OPCODE_MOVUP7: u8 = 0b0001_0110;
49 pub const OPCODE_MOVDN7: u8 = 0b0001_0111;
50 pub const OPCODE_SWAPW: u8 = 0b0001_1000;
51 pub const OPCODE_EXT2MUL: u8 = 0b0001_1001;
52 pub const OPCODE_MOVUP8: u8 = 0b0001_1010;
53 pub const OPCODE_MOVDN8: u8 = 0b0001_1011;
54 pub const OPCODE_SWAPW2: u8 = 0b0001_1100;
55 pub const OPCODE_SWAPW3: u8 = 0b0001_1101;
56 pub const OPCODE_SWAPDW: u8 = 0b0001_1110;
57
58 pub const OPCODE_ASSERT: u8 = 0b0010_0000;
59 pub const OPCODE_EQ: u8 = 0b0010_0001;
60 pub const OPCODE_ADD: u8 = 0b0010_0010;
61 pub const OPCODE_MUL: u8 = 0b0010_0011;
62 pub const OPCODE_AND: u8 = 0b0010_0100;
63 pub const OPCODE_OR: u8 = 0b0010_0101;
64 pub const OPCODE_U32AND: u8 = 0b0010_0110;
65 pub const OPCODE_U32XOR: u8 = 0b0010_0111;
66 pub const OPCODE_FRIE2F4: u8 = 0b0010_1000;
67 pub const OPCODE_DROP: u8 = 0b0010_1001;
68 pub const OPCODE_CSWAP: u8 = 0b0010_1010;
69 pub const OPCODE_CSWAPW: u8 = 0b0010_1011;
70 pub const OPCODE_MLOADW: u8 = 0b0010_1100;
71 pub const OPCODE_MSTORE: u8 = 0b0010_1101;
72 pub const OPCODE_MSTOREW: u8 = 0b0010_1110;
73 pub const OPCODE_FMPUPDATE: u8 = 0b0010_1111;
74
75 pub const OPCODE_PAD: u8 = 0b0011_0000;
76 pub const OPCODE_DUP0: u8 = 0b0011_0001;
77 pub const OPCODE_DUP1: u8 = 0b0011_0010;
78 pub const OPCODE_DUP2: u8 = 0b0011_0011;
79 pub const OPCODE_DUP3: u8 = 0b0011_0100;
80 pub const OPCODE_DUP4: u8 = 0b0011_0101;
81 pub const OPCODE_DUP5: u8 = 0b0011_0110;
82 pub const OPCODE_DUP6: u8 = 0b0011_0111;
83 pub const OPCODE_DUP7: u8 = 0b0011_1000;
84 pub const OPCODE_DUP9: u8 = 0b0011_1001;
85 pub const OPCODE_DUP11: u8 = 0b0011_1010;
86 pub const OPCODE_DUP13: u8 = 0b0011_1011;
87 pub const OPCODE_DUP15: u8 = 0b0011_1100;
88 pub const OPCODE_ADVPOP: u8 = 0b0011_1101;
89 pub const OPCODE_SDEPTH: u8 = 0b0011_1110;
90 pub const OPCODE_CLK: u8 = 0b0011_1111;
91
92 pub const OPCODE_U32ADD: u8 = 0b0100_0000;
93 pub const OPCODE_U32SUB: u8 = 0b0100_0010;
94 pub const OPCODE_U32MUL: u8 = 0b0100_0100;
95 pub const OPCODE_U32DIV: u8 = 0b0100_0110;
96 pub const OPCODE_U32SPLIT: u8 = 0b0100_1000;
97 pub const OPCODE_U32ASSERT2: u8 = 0b0100_1010;
98 pub const OPCODE_U32ADD3: u8 = 0b0100_1100;
99 pub const OPCODE_U32MADD: u8 = 0b0100_1110;
100
101 pub const OPCODE_HPERM: u8 = 0b0101_0000;
102 pub const OPCODE_MPVERIFY: u8 = 0b0101_0001;
103 pub const OPCODE_PIPE: u8 = 0b0101_0010;
104 pub const OPCODE_MSTREAM: u8 = 0b0101_0011;
105 pub const OPCODE_SPLIT: u8 = 0b0101_0100;
106 pub const OPCODE_LOOP: u8 = 0b0101_0101;
107 pub const OPCODE_SPAN: u8 = 0b0101_0110;
108 pub const OPCODE_JOIN: u8 = 0b0101_0111;
109 pub const OPCODE_DYN: u8 = 0b0101_1000;
110 pub const OPCODE_RCOMBBASE: u8 = 0b0101_1001;
111 pub const OPCODE_EMIT: u8 = 0b0101_1010;
112 pub const OPCODE_PUSH: u8 = 0b0101_1011;
113 pub const OPCODE_DYNCALL: u8 = 0b0101_1100;
114
115 pub const OPCODE_MRUPDATE: u8 = 0b0110_0000;
116 /* unused: 0b0110_0100 */
117 pub const OPCODE_SYSCALL: u8 = 0b0110_1000;
118 pub const OPCODE_CALL: u8 = 0b0110_1100;
119 pub const OPCODE_END: u8 = 0b0111_0000;
120 pub const OPCODE_REPEAT: u8 = 0b0111_0100;
121 pub const OPCODE_RESPAN: u8 = 0b0111_1000;
122 pub const OPCODE_HALT: u8 = 0b0111_1100;
123}
124
125// OPERATIONS
126// ================================================================================================
127
128/// A set of native VM operations which take exactly one cycle to execute.
129#[derive(Copy, Clone, Debug, Eq, PartialEq)]
130#[repr(u8)]
131pub enum Operation {
132 // ----- system operations -------------------------------------------------------------------
133 /// Advances cycle counter, but does not change the state of user stack.
134 Noop = OPCODE_NOOP,
135
136 /// Pops the stack; if the popped value is not 1, execution fails.
137 ///
138 /// The internal value specifies an error code associated with the error in case when the
139 /// execution fails.
140 Assert(u32) = OPCODE_ASSERT,
141
142 /// Pops an element off the stack, adds the current value of the `fmp` register to it, and
143 /// pushes the result back onto the stack.
144 FmpAdd = OPCODE_FMPADD,
145
146 /// Pops an element off the stack and adds it to the current value of `fmp` register.
147 FmpUpdate = OPCODE_FMPUPDATE,
148
149 /// Pushes the current depth of the stack onto the stack.
150 SDepth = OPCODE_SDEPTH,
151
152 /// Overwrites the top four stack items with the hash of a function which initiated the current
153 /// SYSCALL. Thus, this operation can be executed only inside a SYSCALL code block.
154 Caller = OPCODE_CALLER,
155
156 /// Pushes the current value of the clock cycle onto the stack. This operation can be used to
157 /// measure the number of cycles it has taken to execute the program up to the current
158 /// instruction.
159 Clk = OPCODE_CLK,
160
161 /// Emits an event id (`u32` value) to the host.
162 ///
163 /// We interpret the event id as follows:
164 /// - 16 most significant bits identify the event source,
165 /// - 16 least significant bits identify the actual event.
166 ///
167 /// Similar to Noop, this operation does not change the state of user stack. The immediate
168 /// value affects the program MAST root computation.
169 Emit(u32) = OPCODE_EMIT,
170
171 // ----- flow control operations -------------------------------------------------------------
172 /// Marks the beginning of a join block.
173 Join = OPCODE_JOIN,
174
175 /// Marks the beginning of a split block.
176 Split = OPCODE_SPLIT,
177
178 /// Marks the beginning of a loop block.
179 Loop = OPCODE_LOOP,
180
181 /// Marks the beginning of a function call.
182 Call = OPCODE_CALL,
183
184 /// Marks the beginning of a dynamic code block, where the target is specified by the stack.
185 Dyn = OPCODE_DYN,
186
187 /// Marks the beginning of a dynamic function call, where the target is specified by the stack.
188 Dyncall = OPCODE_DYNCALL,
189
190 /// Marks the beginning of a kernel call.
191 SysCall = OPCODE_SYSCALL,
192
193 /// Marks the beginning of a span code block.
194 Span = OPCODE_SPAN,
195
196 /// Marks the end of a program block.
197 End = OPCODE_END,
198
199 /// Indicates that body of an executing loop should be executed again.
200 Repeat = OPCODE_REPEAT,
201
202 /// Starts processing a new operation batch.
203 Respan = OPCODE_RESPAN,
204
205 /// Indicates the end of the program. This is used primarily to pad the execution trace to
206 /// the required length. Once HALT operation is executed, no other operations can be executed
207 /// by the VM (HALT operation itself excepted).
208 Halt = OPCODE_HALT,
209
210 // ----- field operations --------------------------------------------------------------------
211 /// Pops two elements off the stack, adds them, and pushes the result back onto the stack.
212 Add = OPCODE_ADD,
213
214 /// Pops an element off the stack, negates it, and pushes the result back onto the stack.
215 Neg = OPCODE_NEG,
216
217 /// Pops two elements off the stack, multiplies them, and pushes the result back onto the
218 /// stack.
219 Mul = OPCODE_MUL,
220
221 /// Pops an element off the stack, computes its multiplicative inverse, and pushes the result
222 /// back onto the stack.
223 Inv = OPCODE_INV,
224
225 /// Pops an element off the stack, adds 1 to it, and pushes the result back onto the stack.
226 Incr = OPCODE_INCR,
227
228 /// Pops two elements off the stack, multiplies them, and pushes the result back onto the
229 /// stack.
230 ///
231 /// If either of the elements is greater than 1, execution fails. This operation is equivalent
232 /// to boolean AND.
233 And = OPCODE_AND,
234
235 /// Pops two elements off the stack and subtracts their product from their sum.
236 ///
237 /// If either of the elements is greater than 1, execution fails. This operation is equivalent
238 /// to boolean OR.
239 Or = OPCODE_OR,
240
241 /// Pops an element off the stack and subtracts it from 1.
242 ///
243 /// If the element is greater than one, the execution fails. This operation is equivalent to
244 /// boolean NOT.
245 Not = OPCODE_NOT,
246
247 /// Pops two elements off the stack and compares them. If the elements are equal, pushes 1
248 /// onto the stack, otherwise pushes 0 onto the stack.
249 Eq = OPCODE_EQ,
250
251 /// Pops an element off the stack and compares it to 0. If the element is 0, pushes 1 onto
252 /// the stack, otherwise pushes 0 onto the stack.
253 Eqz = OPCODE_EQZ,
254
255 /// Computes a single turn of exponent accumulation for the given inputs. This operation can be
256 /// be used to compute a single turn of power of a field element.
257 ///
258 /// The top 4 elements of the stack are expected to be arranged as follows (form the top):
259 /// - least significant bit of the exponent in the previous trace if there's an expacc call,
260 /// otherwise ZERO
261 /// - exponent of base number `a` for this turn
262 /// - accumulated power of base number `a` so far
263 /// - number which needs to be shifted to the right
264 ///
265 /// At the end of the operation, exponent is replaced with its square, current value of power
266 /// of base number `a` on exponent is incorporated into the accumulator and the number is
267 /// shifted to the right by one bit.
268 Expacc = OPCODE_EXPACC,
269
270 // ----- ext2 operations ---------------------------------------------------------------------
271 /// Computes the product of two elements in the extension field of degree 2 and pushes the
272 /// result back onto the stack as the third and fourth elements. Pushes 0 onto the stack as
273 /// the first and second elements.
274 Ext2Mul = OPCODE_EXT2MUL,
275
276 // ----- u32 operations ----------------------------------------------------------------------
277 /// Pops an element off the stack, splits it into upper and lower 32-bit values, and pushes
278 /// these values back onto the stack.
279 U32split = OPCODE_U32SPLIT,
280
281 /// Pops two elements off the stack, adds them, and splits the result into upper and lower
282 /// 32-bit values. Then pushes these values back onto the stack.
283 ///
284 /// If either of these elements is greater than or equal to 2^32, the result of this
285 /// operation is undefined.
286 U32add = OPCODE_U32ADD,
287
288 /// Pops two elements off the stack and checks if each of them represents a 32-bit value.
289 /// If both of them are, they are pushed back onto the stack, otherwise an error is returned.
290 ///
291 /// The internal value specifies an error code associated with the error in case when the
292 /// assertion fails.
293 U32assert2(u32) = OPCODE_U32ASSERT2,
294
295 /// Pops three elements off the stack, adds them together, and splits the result into upper
296 /// and lower 32-bit values. Then pushes the result back onto the stack.
297 U32add3 = OPCODE_U32ADD3,
298
299 /// Pops two elements off the stack and subtracts the first element from the second. Then,
300 /// the result, together with a flag indicating whether subtraction underflowed is pushed
301 /// onto the stack.
302 ///
303 /// If their of the values is greater than or equal to 2^32, the result of this operation is
304 /// undefined.
305 U32sub = OPCODE_U32SUB,
306
307 /// Pops two elements off the stack, multiplies them, and splits the result into upper and
308 /// lower 32-bit values. Then pushes these values back onto the stack.
309 ///
310 /// If their of the values is greater than or equal to 2^32, the result of this operation is
311 /// undefined.
312 U32mul = OPCODE_U32MUL,
313
314 /// Pops two elements off the stack and multiplies them. Then pops the third element off the
315 /// stack, and adds it to the result. Finally, splits the result into upper and lower 32-bit
316 /// values, and pushes them onto the stack.
317 ///
318 /// If any of the three values is greater than or equal to 2^32, the result of this operation
319 /// is undefined.
320 U32madd = OPCODE_U32MADD,
321
322 /// Pops two elements off the stack and divides the second element by the first. Then pushes
323 /// the integer result of the division, together with the remainder, onto the stack.
324 ///
325 /// If their of the values is greater than or equal to 2^32, the result of this operation is
326 /// undefined.
327 U32div = OPCODE_U32DIV,
328
329 /// Pops two elements off the stack, computes their binary AND, and pushes the result back
330 /// onto the stack.
331 ///
332 /// If either of the elements is greater than or equal to 2^32, execution fails.
333 U32and = OPCODE_U32AND,
334
335 /// Pops two elements off the stack, computes their binary XOR, and pushes the result back
336 /// onto the stack.
337 ///
338 /// If either of the elements is greater than or equal to 2^32, execution fails.
339 U32xor = OPCODE_U32XOR,
340
341 // ----- stack manipulation ------------------------------------------------------------------
342 /// Pushes 0 onto the stack.
343 Pad = OPCODE_PAD,
344
345 /// Removes to element from the stack.
346 Drop = OPCODE_DROP,
347
348 /// Pushes a copy of stack element 0 onto the stack.
349 Dup0 = OPCODE_DUP0,
350
351 /// Pushes a copy of stack element 1 onto the stack.
352 Dup1 = OPCODE_DUP1,
353
354 /// Pushes a copy of stack element 2 onto the stack.
355 Dup2 = OPCODE_DUP2,
356
357 /// Pushes a copy of stack element 3 onto the stack.
358 Dup3 = OPCODE_DUP3,
359
360 /// Pushes a copy of stack element 4 onto the stack.
361 Dup4 = OPCODE_DUP4,
362
363 /// Pushes a copy of stack element 5 onto the stack.
364 Dup5 = OPCODE_DUP5,
365
366 /// Pushes a copy of stack element 6 onto the stack.
367 Dup6 = OPCODE_DUP6,
368
369 /// Pushes a copy of stack element 7 onto the stack.
370 Dup7 = OPCODE_DUP7,
371
372 /// Pushes a copy of stack element 9 onto the stack.
373 Dup9 = OPCODE_DUP9,
374
375 /// Pushes a copy of stack element 11 onto the stack.
376 Dup11 = OPCODE_DUP11,
377
378 /// Pushes a copy of stack element 13 onto the stack.
379 Dup13 = OPCODE_DUP13,
380
381 /// Pushes a copy of stack element 15 onto the stack.
382 Dup15 = OPCODE_DUP15,
383
384 /// Swaps stack elements 0 and 1.
385 Swap = OPCODE_SWAP,
386
387 /// Swaps stack elements 0, 1, 2, and 3 with elements 4, 5, 6, and 7.
388 SwapW = OPCODE_SWAPW,
389
390 /// Swaps stack elements 0, 1, 2, and 3 with elements 8, 9, 10, and 11.
391 SwapW2 = OPCODE_SWAPW2,
392
393 /// Swaps stack elements 0, 1, 2, and 3, with elements 12, 13, 14, and 15.
394 SwapW3 = OPCODE_SWAPW3,
395
396 /// Swaps the top two words pair wise.
397 ///
398 /// Input: [D, C, B, A, ...]
399 /// Output: [B, A, D, C, ...]
400 SwapDW = OPCODE_SWAPDW,
401
402 /// Moves stack element 2 to the top of the stack.
403 MovUp2 = OPCODE_MOVUP2,
404
405 /// Moves stack element 3 to the top of the stack.
406 MovUp3 = OPCODE_MOVUP3,
407
408 /// Moves stack element 4 to the top of the stack.
409 MovUp4 = OPCODE_MOVUP4,
410
411 /// Moves stack element 5 to the top of the stack.
412 MovUp5 = OPCODE_MOVUP5,
413
414 /// Moves stack element 6 to the top of the stack.
415 MovUp6 = OPCODE_MOVUP6,
416
417 /// Moves stack element 7 to the top of the stack.
418 MovUp7 = OPCODE_MOVUP7,
419
420 /// Moves stack element 8 to the top of the stack.
421 MovUp8 = OPCODE_MOVUP8,
422
423 /// Moves the top stack element to position 2 on the stack.
424 MovDn2 = OPCODE_MOVDN2,
425
426 /// Moves the top stack element to position 3 on the stack.
427 MovDn3 = OPCODE_MOVDN3,
428
429 /// Moves the top stack element to position 4 on the stack.
430 MovDn4 = OPCODE_MOVDN4,
431
432 /// Moves the top stack element to position 5 on the stack.
433 MovDn5 = OPCODE_MOVDN5,
434
435 /// Moves the top stack element to position 6 on the stack.
436 MovDn6 = OPCODE_MOVDN6,
437
438 /// Moves the top stack element to position 7 on the stack.
439 MovDn7 = OPCODE_MOVDN7,
440
441 /// Moves the top stack element to position 8 on the stack.
442 MovDn8 = OPCODE_MOVDN8,
443
444 /// Pops an element off the stack, and if the element is 1, swaps the top two remaining
445 /// elements on the stack. If the popped element is 0, the stack remains unchanged.
446 ///
447 /// If the popped element is neither 0 nor 1, execution fails.
448 CSwap = OPCODE_CSWAP,
449
450 /// Pops an element off the stack, and if the element is 1, swaps the remaining elements
451 /// 0, 1, 2, and 3 with elements 4, 5, 6, and 7. If the popped element is 0, the stack
452 /// remains unchanged.
453 ///
454 /// If the popped element is neither 0 nor 1, execution fails.
455 CSwapW = OPCODE_CSWAPW,
456
457 // ----- input / output ----------------------------------------------------------------------
458 /// Pushes the immediate value onto the stack.
459 Push(Felt) = OPCODE_PUSH,
460
461 /// Removes the next element from the advice stack and pushes it onto the operand stack.
462 AdvPop = OPCODE_ADVPOP,
463
464 /// Removes a word (4 elements) from the advice stack and overwrites the top four operand
465 /// stack elements with it.
466 AdvPopW = OPCODE_ADVPOPW,
467
468 /// Pops an element off the stack, interprets it as a memory address, and replaces the
469 /// remaining 4 elements at the top of the stack with values located at the specified address.
470 MLoadW = OPCODE_MLOADW,
471
472 /// Pops an element off the stack, interprets it as a memory address, and writes the remaining
473 /// 4 elements at the top of the stack into memory at the specified address.
474 MStoreW = OPCODE_MSTOREW,
475
476 /// Pops an element off the stack, interprets it as a memory address, and pushes the first
477 /// element of the word located at the specified address to the stack.
478 MLoad = OPCODE_MLOAD,
479
480 /// Pops an element off the stack, interprets it as a memory address, and writes the remaining
481 /// element at the top of the stack into the first element of the word located at the specified
482 /// memory address. The remaining 3 elements of the word are not affected.
483 MStore = OPCODE_MSTORE,
484
485 /// Loads two words from memory, and replaces the top 8 elements of the stack with them,
486 /// element-wise, in stack order.
487 ///
488 /// The operation works as follows:
489 /// - The memory address of the first word is retrieved from 13th stack element (position 12).
490 /// - Two consecutive words, starting at this address, are loaded from memory.
491 /// - The top 8 elements of the stack are overwritten with these words (element-wise, in stack
492 /// order).
493 /// - Memory address (in position 12) is incremented by 2.
494 /// - All other stack elements remain the same.
495 MStream = OPCODE_MSTREAM,
496
497 /// Pops two words from the advice stack, writes them to memory, and replaces the top 8
498 /// elements of the stack with them, element-wise, in stack order.
499 ///
500 /// The operation works as follows:
501 /// - Two words are popped from the advice stack.
502 /// - The destination memory address for the first word is retrieved from the 13th stack
503 /// element (position 12).
504 /// - The two words are written to memory consecutively, starting at this address.
505 /// - The top 8 elements of the stack are overwritten with these words (element-wise, in stack
506 /// order).
507 /// - Memory address (in position 12) is incremented by 2.
508 /// - All other stack elements remain the same.
509 Pipe = OPCODE_PIPE,
510
511 // ----- cryptographic operations ------------------------------------------------------------
512 /// Performs a Rescue Prime Optimized permutation on the top 3 words of the operand stack,
513 /// where the top 2 words are the rate (words C and B), the deepest word is the capacity (word
514 /// A), and the digest output is the middle word E.
515 ///
516 /// Stack transition:
517 /// [C, B, A, ...] -> [F, E, D, ...]
518 HPerm = OPCODE_HPERM,
519
520 /// Verifies that a Merkle path from the specified node resolves to the specified root. This
521 /// operation can be used to prove that the prover knows a path in the specified Merkle tree
522 /// which starts with the specified node.
523 ///
524 /// The stack is expected to be arranged as follows (from the top):
525 /// - value of the node, 4 elements.
526 /// - depth of the path, 1 element.
527 /// - index of the node, 1 element.
528 /// - root of the tree, 4 elements.
529 ///
530 /// The Merkle path itself is expected to be provided by the prover non-deterministically (via
531 /// merkle sets). If the prover is not able to provide the required path, the operation fails.
532 /// The state of the stack does not change.
533 ///
534 /// The internal value specifies an error code associated with the error in case when the
535 /// assertion fails.
536 MpVerify(u32) = OPCODE_MPVERIFY,
537
538 /// Computes a new root of a Merkle tree where a node at the specified position is updated to
539 /// the specified value.
540 ///
541 /// The stack is expected to be arranged as follows (from the top):
542 /// - old value of the node, 4 element
543 /// - depth of the node, 1 element
544 /// - index of the node, 1 element
545 /// - current root of the tree, 4 elements
546 /// - new value of the node, 4 element
547 ///
548 /// The Merkle path for the node is expected to be provided by the prover non-deterministically
549 /// via the advice provider. At the end of the operation, the old node value is replaced with
550 /// the new root value, that is computed based on the provided path. Everything else on the
551 /// stack remains the same.
552 ///
553 /// The tree will always be copied into a new instance, meaning the advice provider will keep
554 /// track of both the old and new Merkle trees.
555 MrUpdate = OPCODE_MRUPDATE,
556
557 /// TODO: add docs
558 FriE2F4 = OPCODE_FRIE2F4,
559
560 /// Performs a single step of a random linear combination defining the DEEP composition
561 /// polynomial i.e., the input to the FRI protocol. More precisely, the sum in question is:
562 /// \sum_{i=0}^k{\alpha_i \cdot \left(\frac{T_i(x) - T_i(z)}{x - z} +
563 /// \frac{T_i(x) - T_i(g \cdot z)}{x - g \cdot z} \right)}
564 ///
565 /// and the following instruction computes the numerators $\alpha_i \cdot (T_i(x) - T_i(z))$
566 /// and $\alpha_i \cdot (T_i(x) - T_i(g \cdot z))$ and stores the values in two accumulators
567 /// $r$ and $p$, respectively. This instruction is specialized to main trace columns i.e.
568 /// the values $T_i(x)$ are base field elements.
569 RCombBase = OPCODE_RCOMBBASE,
570}
571
572impl Operation {
573 pub const OP_BITS: usize = 7;
574
575 /// Returns the opcode of this operation.
576 #[rustfmt::skip]
577 pub fn op_code(&self) -> u8 {
578 // SAFETY: This is safe because we have given this enum a primitive representation with
579 // #[repr(u8)], with the first field of the underlying union-of-structs the discriminant.
580 //
581 // See the section on "accessing the numeric value of the discriminant"
582 // here: https://doc.rust-lang.org/std/mem/fn.discriminant.html
583 unsafe { *<*const _>::from(self).cast::<u8>() }
584 }
585
586 /// Returns an immediate value carried by this operation.
587 pub fn imm_value(&self) -> Option<Felt> {
588 match *self {
589 Self::Push(imm) => Some(imm),
590 Self::Emit(imm) => Some(imm.into()),
591 _ => None,
592 }
593 }
594
595 /// Returns true if this operation writes any data to the decoder hasher registers.
596 ///
597 /// In other words, if so, then the user op helper registers are not available.
598 pub fn populates_decoder_hasher_registers(&self) -> bool {
599 matches!(
600 self,
601 Self::End
602 | Self::Join
603 | Self::Split
604 | Self::Loop
605 | Self::Repeat
606 | Self::Respan
607 | Self::Span
608 | Self::Halt
609 | Self::Call
610 | Self::SysCall
611 )
612 }
613}
614
615impl crate::prettier::PrettyPrint for Operation {
616 fn render(&self) -> crate::prettier::Document {
617 crate::prettier::display(self)
618 }
619}
620
621impl fmt::Display for Operation {
622 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
623 match self {
624 // ----- system operations ------------------------------------------------------------
625 Self::Noop => write!(f, "noop"),
626 Self::Assert(err_code) => write!(f, "assert({err_code})"),
627
628 Self::FmpAdd => write!(f, "fmpadd"),
629 Self::FmpUpdate => write!(f, "fmpupdate"),
630
631 Self::SDepth => write!(f, "sdepth"),
632 Self::Caller => write!(f, "caller"),
633
634 Self::Clk => write!(f, "clk"),
635
636 // ----- flow control operations ------------------------------------------------------
637 Self::Join => write!(f, "join"),
638 Self::Split => write!(f, "split"),
639 Self::Loop => write!(f, "loop"),
640 Self::Call => writeln!(f, "call"),
641 Self::Dyncall => writeln!(f, "dyncall"),
642 Self::SysCall => writeln!(f, "syscall"),
643 Self::Dyn => writeln!(f, "dyn"),
644 Self::Span => write!(f, "span"),
645 Self::End => write!(f, "end"),
646 Self::Repeat => write!(f, "repeat"),
647 Self::Respan => write!(f, "respan"),
648 Self::Halt => write!(f, "halt"),
649
650 // ----- field operations -------------------------------------------------------------
651 Self::Add => write!(f, "add"),
652 Self::Neg => write!(f, "neg"),
653 Self::Mul => write!(f, "mul"),
654 Self::Inv => write!(f, "inv"),
655 Self::Incr => write!(f, "incr"),
656
657 Self::And => write!(f, "and"),
658 Self::Or => write!(f, "or"),
659 Self::Not => write!(f, "not"),
660
661 Self::Eq => write!(f, "eq"),
662 Self::Eqz => write!(f, "eqz"),
663
664 Self::Expacc => write!(f, "expacc"),
665
666 // ----- ext2 operations --------------------------------------------------------------
667 Self::Ext2Mul => write!(f, "ext2mul"),
668
669 // ----- u32 operations ---------------------------------------------------------------
670 Self::U32assert2(err_code) => write!(f, "u32assert2({err_code})"),
671 Self::U32split => write!(f, "u32split"),
672 Self::U32add => write!(f, "u32add"),
673 Self::U32add3 => write!(f, "u32add3"),
674 Self::U32sub => write!(f, "u32sub"),
675 Self::U32mul => write!(f, "u32mul"),
676 Self::U32madd => write!(f, "u32madd"),
677 Self::U32div => write!(f, "u32div"),
678
679 Self::U32and => write!(f, "u32and"),
680 Self::U32xor => write!(f, "u32xor"),
681
682 // ----- stack manipulation -----------------------------------------------------------
683 Self::Drop => write!(f, "drop"),
684 Self::Pad => write!(f, "pad"),
685
686 Self::Dup0 => write!(f, "dup0"),
687 Self::Dup1 => write!(f, "dup1"),
688 Self::Dup2 => write!(f, "dup2"),
689 Self::Dup3 => write!(f, "dup3"),
690 Self::Dup4 => write!(f, "dup4"),
691 Self::Dup5 => write!(f, "dup5"),
692 Self::Dup6 => write!(f, "dup6"),
693 Self::Dup7 => write!(f, "dup7"),
694 Self::Dup9 => write!(f, "dup9"),
695 Self::Dup11 => write!(f, "dup11"),
696 Self::Dup13 => write!(f, "dup13"),
697 Self::Dup15 => write!(f, "dup15"),
698
699 Self::Swap => write!(f, "swap"),
700 Self::SwapW => write!(f, "swapw"),
701 Self::SwapW2 => write!(f, "swapw2"),
702 Self::SwapW3 => write!(f, "swapw3"),
703 Self::SwapDW => write!(f, "swapdw"),
704
705 Self::MovUp2 => write!(f, "movup2"),
706 Self::MovUp3 => write!(f, "movup3"),
707 Self::MovUp4 => write!(f, "movup4"),
708 Self::MovUp5 => write!(f, "movup5"),
709 Self::MovUp6 => write!(f, "movup6"),
710 Self::MovUp7 => write!(f, "movup7"),
711 Self::MovUp8 => write!(f, "movup8"),
712
713 Self::MovDn2 => write!(f, "movdn2"),
714 Self::MovDn3 => write!(f, "movdn3"),
715 Self::MovDn4 => write!(f, "movdn4"),
716 Self::MovDn5 => write!(f, "movdn5"),
717 Self::MovDn6 => write!(f, "movdn6"),
718 Self::MovDn7 => write!(f, "movdn7"),
719 Self::MovDn8 => write!(f, "movdn8"),
720
721 Self::CSwap => write!(f, "cswap"),
722 Self::CSwapW => write!(f, "cswapw"),
723
724 // ----- input / output ---------------------------------------------------------------
725 Self::Push(value) => write!(f, "push({value})"),
726
727 Self::AdvPop => write!(f, "advpop"),
728 Self::AdvPopW => write!(f, "advpopw"),
729
730 Self::MLoadW => write!(f, "mloadw"),
731 Self::MStoreW => write!(f, "mstorew"),
732
733 Self::MLoad => write!(f, "mload"),
734 Self::MStore => write!(f, "mstore"),
735
736 Self::MStream => write!(f, "mstream"),
737 Self::Pipe => write!(f, "pipe"),
738
739 Self::Emit(value) => write!(f, "emit({value})"),
740
741 // ----- cryptographic operations -----------------------------------------------------
742 Self::HPerm => write!(f, "hperm"),
743 Self::MpVerify(err_code) => write!(f, "mpverify({err_code})"),
744 Self::MrUpdate => write!(f, "mrupdate"),
745 Self::FriE2F4 => write!(f, "frie2f4"),
746 Self::RCombBase => write!(f, "rcomb1"),
747 }
748 }
749}
750
751impl Serializable for Operation {
752 fn write_into<W: ByteWriter>(&self, target: &mut W) {
753 target.write_u8(self.op_code());
754
755 // For operations that have extra data, encode it in `data`.
756 match self {
757 Operation::Assert(err_code)
758 | Operation::MpVerify(err_code)
759 | Operation::U32assert2(err_code) => {
760 err_code.write_into(target);
761 },
762 Operation::Push(value) => value.as_int().write_into(target),
763 Operation::Emit(value) => value.write_into(target),
764
765 // Note: we explicitly write out all the operations so that whenever we make a
766 // modification to the `Operation` enum, we get a compile error here. This
767 // should help us remember to properly encode/decode each operation variant.
768 Operation::Noop
769 | Operation::FmpAdd
770 | Operation::FmpUpdate
771 | Operation::SDepth
772 | Operation::Caller
773 | Operation::Clk
774 | Operation::Join
775 | Operation::Split
776 | Operation::Loop
777 | Operation::Call
778 | Operation::Dyn
779 | Operation::Dyncall
780 | Operation::SysCall
781 | Operation::Span
782 | Operation::End
783 | Operation::Repeat
784 | Operation::Respan
785 | Operation::Halt
786 | Operation::Add
787 | Operation::Neg
788 | Operation::Mul
789 | Operation::Inv
790 | Operation::Incr
791 | Operation::And
792 | Operation::Or
793 | Operation::Not
794 | Operation::Eq
795 | Operation::Eqz
796 | Operation::Expacc
797 | Operation::Ext2Mul
798 | Operation::U32split
799 | Operation::U32add
800 | Operation::U32add3
801 | Operation::U32sub
802 | Operation::U32mul
803 | Operation::U32madd
804 | Operation::U32div
805 | Operation::U32and
806 | Operation::U32xor
807 | Operation::Pad
808 | Operation::Drop
809 | Operation::Dup0
810 | Operation::Dup1
811 | Operation::Dup2
812 | Operation::Dup3
813 | Operation::Dup4
814 | Operation::Dup5
815 | Operation::Dup6
816 | Operation::Dup7
817 | Operation::Dup9
818 | Operation::Dup11
819 | Operation::Dup13
820 | Operation::Dup15
821 | Operation::Swap
822 | Operation::SwapW
823 | Operation::SwapW2
824 | Operation::SwapW3
825 | Operation::SwapDW
826 | Operation::MovUp2
827 | Operation::MovUp3
828 | Operation::MovUp4
829 | Operation::MovUp5
830 | Operation::MovUp6
831 | Operation::MovUp7
832 | Operation::MovUp8
833 | Operation::MovDn2
834 | Operation::MovDn3
835 | Operation::MovDn4
836 | Operation::MovDn5
837 | Operation::MovDn6
838 | Operation::MovDn7
839 | Operation::MovDn8
840 | Operation::CSwap
841 | Operation::CSwapW
842 | Operation::AdvPop
843 | Operation::AdvPopW
844 | Operation::MLoadW
845 | Operation::MStoreW
846 | Operation::MLoad
847 | Operation::MStore
848 | Operation::MStream
849 | Operation::Pipe
850 | Operation::HPerm
851 | Operation::MrUpdate
852 | Operation::FriE2F4
853 | Operation::RCombBase => (),
854 }
855 }
856}
857
858impl Deserializable for Operation {
859 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
860 let op_code = source.read_u8()?;
861
862 let operation = match op_code {
863 OPCODE_NOOP => Self::Noop,
864 OPCODE_EQZ => Self::Eqz,
865 OPCODE_NEG => Self::Neg,
866 OPCODE_INV => Self::Inv,
867 OPCODE_INCR => Self::Incr,
868 OPCODE_NOT => Self::Not,
869 OPCODE_FMPADD => Self::FmpAdd,
870 OPCODE_MLOAD => Self::MLoad,
871 OPCODE_SWAP => Self::Swap,
872 OPCODE_CALLER => Self::Caller,
873 OPCODE_MOVUP2 => Self::MovUp2,
874 OPCODE_MOVDN2 => Self::MovDn2,
875 OPCODE_MOVUP3 => Self::MovUp3,
876 OPCODE_MOVDN3 => Self::MovDn3,
877 OPCODE_ADVPOPW => Self::AdvPopW,
878 OPCODE_EXPACC => Self::Expacc,
879
880 OPCODE_MOVUP4 => Self::MovUp4,
881 OPCODE_MOVDN4 => Self::MovDn4,
882 OPCODE_MOVUP5 => Self::MovUp5,
883 OPCODE_MOVDN5 => Self::MovDn5,
884 OPCODE_MOVUP6 => Self::MovUp6,
885 OPCODE_MOVDN6 => Self::MovDn6,
886 OPCODE_MOVUP7 => Self::MovUp7,
887 OPCODE_MOVDN7 => Self::MovDn7,
888 OPCODE_SWAPW => Self::SwapW,
889 OPCODE_EXT2MUL => Self::Ext2Mul,
890 OPCODE_MOVUP8 => Self::MovUp8,
891 OPCODE_MOVDN8 => Self::MovDn8,
892 OPCODE_SWAPW2 => Self::SwapW2,
893 OPCODE_SWAPW3 => Self::SwapW3,
894 OPCODE_SWAPDW => Self::SwapDW,
895
896 OPCODE_ASSERT => {
897 let err_code = source.read_u32()?;
898 Self::Assert(err_code)
899 },
900 OPCODE_EQ => Self::Eq,
901 OPCODE_ADD => Self::Add,
902 OPCODE_MUL => Self::Mul,
903 OPCODE_AND => Self::And,
904 OPCODE_OR => Self::Or,
905 OPCODE_U32AND => Self::U32and,
906 OPCODE_U32XOR => Self::U32xor,
907 OPCODE_FRIE2F4 => Self::FriE2F4,
908 OPCODE_DROP => Self::Drop,
909 OPCODE_CSWAP => Self::CSwap,
910 OPCODE_CSWAPW => Self::CSwapW,
911 OPCODE_MLOADW => Self::MLoadW,
912 OPCODE_MSTORE => Self::MStore,
913 OPCODE_MSTOREW => Self::MStoreW,
914 OPCODE_FMPUPDATE => Self::FmpUpdate,
915
916 OPCODE_PAD => Self::Pad,
917 OPCODE_DUP0 => Self::Dup0,
918 OPCODE_DUP1 => Self::Dup1,
919 OPCODE_DUP2 => Self::Dup2,
920 OPCODE_DUP3 => Self::Dup3,
921 OPCODE_DUP4 => Self::Dup4,
922 OPCODE_DUP5 => Self::Dup5,
923 OPCODE_DUP6 => Self::Dup6,
924 OPCODE_DUP7 => Self::Dup7,
925 OPCODE_DUP9 => Self::Dup9,
926 OPCODE_DUP11 => Self::Dup11,
927 OPCODE_DUP13 => Self::Dup13,
928 OPCODE_DUP15 => Self::Dup15,
929 OPCODE_ADVPOP => Self::AdvPop,
930 OPCODE_SDEPTH => Self::SDepth,
931 OPCODE_CLK => Self::Clk,
932
933 OPCODE_U32ADD => Self::U32add,
934 OPCODE_U32SUB => Self::U32sub,
935 OPCODE_U32MUL => Self::U32mul,
936 OPCODE_U32DIV => Self::U32div,
937 OPCODE_U32SPLIT => Self::U32split,
938 OPCODE_U32ASSERT2 => {
939 let err_code = source.read_u32()?;
940
941 Self::U32assert2(err_code)
942 },
943 OPCODE_U32ADD3 => Self::U32add3,
944 OPCODE_U32MADD => Self::U32madd,
945
946 OPCODE_HPERM => Self::HPerm,
947 OPCODE_MPVERIFY => {
948 let err_code = source.read_u32()?;
949
950 Self::MpVerify(err_code)
951 },
952 OPCODE_PIPE => Self::Pipe,
953 OPCODE_MSTREAM => Self::MStream,
954 OPCODE_SPLIT => Self::Split,
955 OPCODE_LOOP => Self::Loop,
956 OPCODE_SPAN => Self::Span,
957 OPCODE_JOIN => Self::Join,
958 OPCODE_DYN => Self::Dyn,
959 OPCODE_DYNCALL => Self::Dyncall,
960 OPCODE_RCOMBBASE => Self::RCombBase,
961
962 OPCODE_MRUPDATE => Self::MrUpdate,
963 OPCODE_PUSH => {
964 let value_u64 = source.read_u64()?;
965 let value_felt = Felt::try_from(value_u64).map_err(|_| {
966 DeserializationError::InvalidValue(format!(
967 "Operation associated data doesn't fit in a field element: {value_u64}"
968 ))
969 })?;
970
971 Self::Push(value_felt)
972 },
973 OPCODE_EMIT => {
974 let value = source.read_u32()?;
975
976 Self::Emit(value)
977 },
978 OPCODE_SYSCALL => Self::SysCall,
979 OPCODE_CALL => Self::Call,
980 OPCODE_END => Self::End,
981 OPCODE_REPEAT => Self::Repeat,
982 OPCODE_RESPAN => Self::Respan,
983 OPCODE_HALT => Self::Halt,
984 _ => {
985 return Err(DeserializationError::InvalidValue(format!(
986 "Invalid opcode '{op_code}'"
987 )));
988 },
989 };
990
991 Ok(operation)
992 }
993}