brillig/
opcodes.rs

1use crate::{
2    black_box::BlackBoxOp,
3    lengths::{ElementsFlattenedLength, FlattenedLength, SemanticLength, SemiFlattenedLength},
4};
5use acir_field::AcirField;
6use itertools::Itertools;
7use msgpack_tagged::MsgpackTagged;
8use serde::{Deserialize, Serialize};
9
10/// Represents a program location (instruction index) used as a jump target.
11pub type Label = usize;
12
13/// Represents an address in the VM's memory.
14/// Supports both direct and relative addressing.
15#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
16#[derive(Serialize, Deserialize, MsgpackTagged)]
17#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
18pub enum MemoryAddress {
19    /// Specifies an exact index in the VM's memory.
20    #[tag(0)]
21    Direct(u32),
22    /// Specifies an index relative to the stack pointer.
23    ///
24    /// It is resolved as the current stack pointer plus the offset stored here.
25    ///
26    /// The stack pointer is stored in memory slot 0, so this address is resolved
27    /// by reading that slot and adding the offset to get the final memory address.
28    #[tag(1)]
29    Relative(u32),
30}
31
32impl MemoryAddress {
33    /// Create a `Direct` address.
34    pub fn direct(address: u32) -> Self {
35        MemoryAddress::Direct(address)
36    }
37
38    /// Create a `Relative` address.
39    pub fn relative(offset: u32) -> Self {
40        MemoryAddress::Relative(offset)
41    }
42
43    /// Return the index in a `Direct` address.
44    ///
45    /// Panics if it's `Relative`.
46    pub fn unwrap_direct(self) -> u32 {
47        match self {
48            MemoryAddress::Direct(address) => address,
49            MemoryAddress::Relative(_) => panic!("Expected direct memory address"),
50        }
51    }
52
53    /// Return the index in a `Relative` address.
54    ///
55    /// Panics if it's `Direct`.
56    pub fn unwrap_relative(self) -> u32 {
57        match self {
58            MemoryAddress::Direct(_) => panic!("Expected relative memory address"),
59            MemoryAddress::Relative(offset) => offset,
60        }
61    }
62
63    /// Return the index in the address.
64    pub fn to_u32(self) -> u32 {
65        match self {
66            MemoryAddress::Direct(address) => address,
67            MemoryAddress::Relative(offset) => offset,
68        }
69    }
70
71    pub fn is_relative(&self) -> bool {
72        match self {
73            MemoryAddress::Relative(_) => true,
74            MemoryAddress::Direct(_) => false,
75        }
76    }
77
78    pub fn is_direct(&self) -> bool {
79        !self.is_relative()
80    }
81
82    /// Offset a `Direct` address by `amount`.
83    ///
84    /// Panics if called on a `Relative` address.
85    pub fn offset(&self, amount: u32) -> Self {
86        // We disallow offsetting relatively addresses as this is not expected to be meaningful.
87        let address = self.unwrap_direct();
88        MemoryAddress::direct(address.checked_add(amount).expect("memory offset overflow"))
89    }
90}
91
92impl std::fmt::Display for MemoryAddress {
93    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
94        match self {
95            MemoryAddress::Direct(address) => write!(f, "@{address}"),
96            MemoryAddress::Relative(offset) => write!(f, "sp[{offset}]"),
97        }
98    }
99}
100
101/// Describes the memory layout for an array/vector element
102#[derive(Debug, Clone, Eq, PartialEq, Hash)]
103#[derive(Serialize, Deserialize, MsgpackTagged)]
104pub enum HeapValueType {
105    /// A single field element is enough to represent the value with a given bit size.
106    #[tag(0)]
107    Simple(BitSize),
108    /// The value read should be interpreted as a pointer to a [HeapArray], which
109    /// consists of a pointer to a slice of memory of size elements, and a
110    /// reference count, to avoid cloning arrays that are not shared.
111    #[tag(1)]
112    Array {
113        #[tag(0)]
114        value_types: Vec<HeapValueType>,
115        #[tag(1)]
116        size: SemanticLength,
117    },
118    /// The value read should be interpreted as a pointer to a [HeapVector], which
119    /// consists of a pointer to a slice of memory, a number of elements in that
120    /// vector, and a reference count.
121    #[tag(2)]
122    Vector {
123        #[tag(0)]
124        value_types: Vec<HeapValueType>,
125    },
126}
127
128impl HeapValueType {
129    /// Check that all types are `Simple`.
130    pub fn all_simple(types: &[HeapValueType]) -> bool {
131        types.iter().all(|typ| matches!(typ, HeapValueType::Simple(_)))
132    }
133
134    /// Create a `Simple` type to represent a `Field`.
135    pub fn field() -> HeapValueType {
136        HeapValueType::Simple(BitSize::Field)
137    }
138
139    /// Returns the total number of field elements required to represent this type in memory.
140    ///
141    /// Returns `None` for `Vector`, as their size is not statically known.
142    pub fn flattened_size(&self) -> Option<FlattenedLength> {
143        match self {
144            HeapValueType::Simple(_) => Some(FlattenedLength(1)),
145            HeapValueType::Array { value_types, size } => {
146                // This is the flattened length of a single entry in the array (all of `value_types`)
147                let elements_flattened_size =
148                    value_types.iter().map(|t| t.flattened_size()).sum::<Option<FlattenedLength>>();
149                // Next we multiply it by the size of the array
150                elements_flattened_size.map(|elements_flattened_size| {
151                    ElementsFlattenedLength::from(elements_flattened_size) * *size
152                })
153            }
154            HeapValueType::Vector { .. } => {
155                // Vectors are dynamic, so we cannot determine their size statically.
156                None
157            }
158        }
159    }
160}
161
162impl std::fmt::Display for HeapValueType {
163    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
164        let write_types =
165            |f: &mut std::fmt::Formatter<'_>, value_types: &[HeapValueType]| -> std::fmt::Result {
166                if value_types.len() == 1 {
167                    write!(f, "{}", value_types[0])?;
168                } else {
169                    write!(f, "(")?;
170                    for (index, value_type) in value_types.iter().enumerate() {
171                        if index > 0 {
172                            write!(f, ", ")?;
173                        }
174                        write!(f, "{value_type}")?;
175                    }
176                    write!(f, ")")?;
177                }
178                Ok(())
179            };
180
181        match self {
182            HeapValueType::Simple(bit_size) => {
183                write!(f, "{bit_size}")
184            }
185            HeapValueType::Array { value_types, size } => {
186                write!(f, "[")?;
187                write_types(f, value_types)?;
188                write!(f, "; {size}")?;
189                write!(f, "]")
190            }
191            HeapValueType::Vector { value_types } => {
192                write!(f, "@[")?;
193                write_types(f, value_types)?;
194                write!(f, "]")
195            }
196        }
197    }
198}
199
200/// A fixed-sized array starting from a Brillig memory location.
201#[derive(Debug, Clone, PartialEq, Eq, Copy, Hash)]
202#[derive(Serialize, Deserialize, MsgpackTagged)]
203#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
204pub struct HeapArray {
205    /// Pointer to a memory address which hold the address to the start of the items in the array.
206    ///
207    /// That is to say, the address retrieved from the pointer doesn't need any more offsetting.
208    #[tag(0)]
209    pub pointer: MemoryAddress,
210    /// Statically known size of the array.
211    #[tag(1)]
212    pub size: SemiFlattenedLength,
213}
214
215impl Default for HeapArray {
216    fn default() -> Self {
217        Self { pointer: MemoryAddress::direct(0), size: SemiFlattenedLength(0) }
218    }
219}
220
221impl std::fmt::Display for HeapArray {
222    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
223        write!(f, "[{}; {}]", self.pointer, self.size)
224    }
225}
226
227/// A memory-sized vector passed starting from a Brillig memory location and with a memory-held size.
228#[derive(Debug, Clone, PartialEq, Eq, Copy, Hash)]
229#[derive(Serialize, Deserialize, MsgpackTagged)]
230#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
231pub struct HeapVector {
232    /// Pointer to a memory address which hold the address to the start of the items in the vector.
233    ///
234    /// That is to say, the address retrieved from the pointer doesn't need any more offsetting.
235    #[tag(0)]
236    pub pointer: MemoryAddress,
237    /// Address to a memory slot holding the semantic length of the vector.
238    #[tag(1)]
239    pub size: MemoryAddress,
240}
241
242impl std::fmt::Display for HeapVector {
243    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
244        write!(f, "@[{}; {}]", self.pointer, self.size)
245    }
246}
247
248/// Represents the bit size of unsigned integer types in Brillig.
249///
250/// These correspond to the standard unsigned integer types, with U1 representing a boolean.
251#[derive(Debug, Clone, PartialEq, Eq, Copy, PartialOrd, Ord, Hash)]
252#[derive(Serialize, Deserialize, MsgpackTagged)]
253#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
254pub enum IntegerBitSize {
255    #[tag(0)]
256    U1,
257    #[tag(1)]
258    U8,
259    #[tag(2)]
260    U16,
261    #[tag(3)]
262    U32,
263    #[tag(4)]
264    U64,
265    #[tag(5)]
266    U128,
267}
268
269impl From<IntegerBitSize> for u32 {
270    fn from(bit_size: IntegerBitSize) -> u32 {
271        match bit_size {
272            IntegerBitSize::U1 => 1,
273            IntegerBitSize::U8 => 8,
274            IntegerBitSize::U16 => 16,
275            IntegerBitSize::U32 => 32,
276            IntegerBitSize::U64 => 64,
277            IntegerBitSize::U128 => 128,
278        }
279    }
280}
281
282impl TryFrom<u32> for IntegerBitSize {
283    type Error = &'static str;
284
285    fn try_from(value: u32) -> Result<Self, Self::Error> {
286        match value {
287            1 => Ok(IntegerBitSize::U1),
288            8 => Ok(IntegerBitSize::U8),
289            16 => Ok(IntegerBitSize::U16),
290            32 => Ok(IntegerBitSize::U32),
291            64 => Ok(IntegerBitSize::U64),
292            128 => Ok(IntegerBitSize::U128),
293            _ => Err("Invalid bit size"),
294        }
295    }
296}
297
298impl std::fmt::Display for IntegerBitSize {
299    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
300        match self {
301            IntegerBitSize::U1 => write!(f, "bool"),
302            IntegerBitSize::U8 => write!(f, "u8"),
303            IntegerBitSize::U16 => write!(f, "u16"),
304            IntegerBitSize::U32 => write!(f, "u32"),
305            IntegerBitSize::U64 => write!(f, "u64"),
306            IntegerBitSize::U128 => write!(f, "u128"),
307        }
308    }
309}
310
311/// Represents the bit size of values in Brillig.
312///
313/// Values can either be field elements (whose size depends on the field being used)
314/// or fixed-size unsigned integers.
315#[derive(Debug, Clone, PartialEq, Eq, Copy, PartialOrd, Ord, Hash)]
316#[derive(Serialize, Deserialize, MsgpackTagged)]
317#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
318pub enum BitSize {
319    #[tag(0)]
320    Field,
321    #[tag(1)]
322    Integer(IntegerBitSize),
323}
324
325impl BitSize {
326    /// Convert the bit size to a u32 value.
327    ///
328    /// For field elements, returns the maximum number of bits in the field.
329    /// For integers, returns the bit size of the integer type.
330    pub fn to_u32<F: AcirField>(self) -> u32 {
331        match self {
332            BitSize::Field => F::max_num_bits(),
333            BitSize::Integer(bit_size) => bit_size.into(),
334        }
335    }
336
337    /// Try to create a BitSize from a u32 value.
338    ///
339    /// If the value matches the field's maximum bit count, returns `BitSize::Field`.
340    /// Otherwise, attempts to interpret it as an integer bit size.
341    pub fn try_from_u32<F: AcirField>(value: u32) -> Result<Self, &'static str> {
342        if value == F::max_num_bits() {
343            Ok(BitSize::Field)
344        } else {
345            Ok(BitSize::Integer(IntegerBitSize::try_from(value)?))
346        }
347    }
348}
349
350impl std::fmt::Display for BitSize {
351    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
352        match self {
353            BitSize::Field => write!(f, "field"),
354            BitSize::Integer(bit_size) => write!(f, "{bit_size}"),
355        }
356    }
357}
358
359/// Lays out various ways an external foreign call's input and output data may be interpreted inside Brillig.
360/// This data can either be an individual value or memory.
361///
362/// While we are usually agnostic to how memory is passed within Brillig,
363/// this needs to be encoded somehow when dealing with an external system.
364/// For simplicity, the extra type information is given right in the `ForeignCall` instructions.
365#[derive(Debug, Clone, PartialEq, Eq, Copy, Hash)]
366#[derive(Serialize, Deserialize, MsgpackTagged)]
367#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
368pub enum ValueOrArray {
369    /// A single value to be passed to or from an external call.
370    /// It is an 'immediate' value - used without dereferencing.
371    /// For a foreign call input, the value is read directly from memory.
372    /// For a foreign call output, the value is written directly to memory.
373    #[tag(0)]
374    MemoryAddress(MemoryAddress),
375    /// An array to be passed to or from an external call.
376    /// In the case of a foreign call input, the array is read from this Brillig memory location + `size` more cells.
377    /// In the case of a foreign call output, the array is written to this Brillig memory location with the `size` being here just as a sanity check for the write size.
378    #[tag(1)]
379    HeapArray(HeapArray),
380    /// A vector to be passed to or from an external call.
381    /// In the case of a foreign call input, the vector is read from this Brillig memory location + as many cells as the second address indicates.
382    /// In the case of a foreign call output, the vector is written to this Brillig memory location as 'size' cells, with size being stored in the second address.
383    #[tag(2)]
384    HeapVector(HeapVector),
385}
386
387impl std::fmt::Display for ValueOrArray {
388    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
389        match self {
390            ValueOrArray::MemoryAddress(memory_address) => {
391                write!(f, "{memory_address}")
392            }
393            ValueOrArray::HeapArray(heap_array) => {
394                write!(f, "{heap_array}")
395            }
396            ValueOrArray::HeapVector(heap_vector) => {
397                write!(f, "{heap_vector}")
398            }
399        }
400    }
401}
402
403#[derive(Debug, Clone, PartialEq, Eq, Hash)]
404#[derive(Serialize, Deserialize, MsgpackTagged)]
405#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
406pub enum BrilligOpcode<F> {
407    /// Takes the fields in addresses `lhs` and `rhs`,
408    /// performs the specified binary operation,
409    /// and stores the value in the `destination` address.
410    #[tag(0)]
411    BinaryFieldOp {
412        #[tag(0)]
413        destination: MemoryAddress,
414        #[tag(1)]
415        op: BinaryFieldOp,
416        #[tag(2)]
417        lhs: MemoryAddress,
418        #[tag(3)]
419        rhs: MemoryAddress,
420    },
421    /// Takes the `bit_size` size integers in addresses `lhs` and `rhs`,
422    /// performs the specified binary operation,
423    /// and stores the value in the `destination` address.
424    #[tag(1)]
425    BinaryIntOp {
426        #[tag(0)]
427        destination: MemoryAddress,
428        #[tag(1)]
429        op: BinaryIntOp,
430        #[tag(2)]
431        bit_size: IntegerBitSize,
432        #[tag(3)]
433        lhs: MemoryAddress,
434        #[tag(4)]
435        rhs: MemoryAddress,
436    },
437    /// Takes the value from the `source` address, inverts it,
438    /// and stores the value in the `destination` address.
439    #[tag(2)]
440    Not {
441        #[tag(0)]
442        destination: MemoryAddress,
443        #[tag(1)]
444        source: MemoryAddress,
445        #[tag(2)]
446        bit_size: IntegerBitSize,
447    },
448    /// Takes the value from the `source` address,
449    /// casts it into the type indicated by `bit_size`,
450    /// and stores the value in the `destination` address.
451    #[tag(3)]
452    Cast {
453        #[tag(0)]
454        destination: MemoryAddress,
455        #[tag(1)]
456        source: MemoryAddress,
457        #[tag(2)]
458        bit_size: BitSize,
459    },
460    /// Sets the program counter to the value of `location`
461    /// if the value at `condition` is non-zero.
462    #[tag(4)]
463    JumpIf {
464        #[tag(0)]
465        condition: MemoryAddress,
466        #[tag(1)]
467        location: Label,
468    },
469    /// Sets the program counter to the value of `location`.
470    #[tag(5)]
471    Jump {
472        #[tag(0)]
473        location: Label,
474    },
475    /// Copies the data from `calldata` from the `offset_address` with length indicated by `size_address`
476    /// to the specified `destination_address` in the memory.
477    #[tag(6)]
478    CalldataCopy {
479        #[tag(0)]
480        destination_address: MemoryAddress,
481        #[tag(1)]
482        size_address: MemoryAddress,
483        #[tag(2)]
484        offset_address: MemoryAddress,
485    },
486    /// Pushes the current program counter to the call stack as to set a return location.
487    /// Sets the program counter to the value of `location`.
488    ///
489    /// We don't support dynamic jumps or calls;
490    /// see <https://github.com/ethereum/aleth/issues/3404> for reasoning.
491    #[tag(7)]
492    Call {
493        #[tag(0)]
494        location: Label,
495    },
496    /// Stores a constant `value` with a `bit_size` in the `destination` address.
497    #[tag(8)]
498    Const {
499        #[tag(0)]
500        destination: MemoryAddress,
501        #[tag(1)]
502        bit_size: BitSize,
503        #[tag(2)]
504        value: F,
505    },
506    /// Reads the address from `destination_pointer`, then stores a constant `value` with a `bit_size` at that address.
507    #[tag(9)]
508    IndirectConst {
509        #[tag(0)]
510        destination_pointer: MemoryAddress,
511        #[tag(1)]
512        bit_size: BitSize,
513        #[tag(2)]
514        value: F,
515    },
516    /// Pops the top element from the call stack, which represents the return location,
517    /// and sets the program counter to that value. This operation is used to return
518    /// from a function call.
519    #[tag(10)]
520    Return,
521    /// Used to get data from an outside source.
522    ///
523    /// Also referred to as an Oracle, intended for things like state tree reads;
524    /// it shouldn't be confused with e.g. blockchain price oracles.
525    #[tag(11)]
526    ForeignCall {
527        /// Interpreted by caller context, ie. this will have different meanings depending on
528        /// who the caller is.
529        #[tag(0)]
530        function: String,
531        /// Destination addresses (may be single values or memory pointers).
532        ///
533        /// Output vectors are passed as a [ValueOrArray::MemoryAddress]. Since their size is not known up front,
534        /// we cannot allocate space for them on the heap. Instead, the VM is expected to write their data after
535        /// the current free memory pointer, and store the heap address into the destination.
536        #[tag(1)]
537        destinations: Vec<ValueOrArray>,
538        /// Destination value types.
539        #[tag(2)]
540        destination_value_types: Vec<HeapValueType>,
541        /// Input addresses (may be single values or memory pointers).
542        #[tag(3)]
543        inputs: Vec<ValueOrArray>,
544        /// Input value types (for heap allocated structures indicates how to
545        /// retrieve the elements).
546        #[tag(4)]
547        input_value_types: Vec<HeapValueType>,
548    },
549    /// Moves the content in the `source` address to the `destination` address.
550    #[tag(12)]
551    Mov {
552        #[tag(0)]
553        destination: MemoryAddress,
554        #[tag(1)]
555        source: MemoryAddress,
556    },
557    /// If the value at `condition` is non-zero, moves the content in the `source_a`
558    /// address to the `destination` address, otherwise moves the content from the
559    /// `source_b` address instead.
560    ///
561    /// `destination = condition > 0 ? source_a : source_b`
562    #[tag(13)]
563    ConditionalMov {
564        #[tag(0)]
565        destination: MemoryAddress,
566        #[tag(1)]
567        source_a: MemoryAddress,
568        #[tag(2)]
569        source_b: MemoryAddress,
570        #[tag(3)]
571        condition: MemoryAddress,
572    },
573    /// Reads the `source_pointer` to obtain a memory address, then retrieves the data
574    /// stored at that address and writes it to the `destination` address.
575    #[tag(14)]
576    Load {
577        #[tag(0)]
578        destination: MemoryAddress,
579        #[tag(1)]
580        source_pointer: MemoryAddress,
581    },
582    /// Reads the `destination_pointer` to obtain a memory address, then stores the value
583    /// from the `source` address at that location.
584    #[tag(15)]
585    Store {
586        #[tag(0)]
587        destination_pointer: MemoryAddress,
588        #[tag(1)]
589        source: MemoryAddress,
590    },
591    /// Native functions in the VM.
592    /// These are equivalent to the black box functions in ACIR.
593    #[tag(16)]
594    BlackBox(BlackBoxOp),
595    /// Used to denote execution failure, halting the VM and returning data specified by a dynamically-sized vector.
596    #[tag(17)]
597    Trap {
598        #[tag(0)]
599        revert_data: HeapVector,
600    },
601    /// Halts execution and returns data specified by a dynamically-sized vector.
602    #[tag(18)]
603    Stop {
604        #[tag(0)]
605        return_data: HeapVector,
606    },
607}
608
609impl<F: std::fmt::Display> std::fmt::Display for BrilligOpcode<F> {
610    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
611        match self {
612            BrilligOpcode::BinaryFieldOp { destination, op, lhs, rhs } => {
613                write!(f, "{destination} = field {op} {lhs}, {rhs}")
614            }
615            BrilligOpcode::BinaryIntOp { destination, op, bit_size, lhs, rhs } => {
616                write!(f, "{destination} = {bit_size} {op} {lhs}, {rhs}")
617            }
618            BrilligOpcode::Not { destination, source, bit_size } => {
619                write!(f, "{destination} = {bit_size} not {source}")
620            }
621            BrilligOpcode::Cast { destination, source, bit_size } => {
622                write!(f, "{destination} = cast {source} to {bit_size}")
623            }
624            BrilligOpcode::JumpIf { condition, location } => {
625                write!(f, "jump if {condition} to {location}")
626            }
627            BrilligOpcode::Jump { location } => {
628                write!(f, "jump to {location}")
629            }
630            BrilligOpcode::CalldataCopy { destination_address, size_address, offset_address } => {
631                write!(
632                    f,
633                    "{destination_address} = calldata copy [{offset_address}; {size_address}]"
634                )
635            }
636            BrilligOpcode::Call { location } => {
637                write!(f, "call {location}")
638            }
639            BrilligOpcode::Const { destination, bit_size, value } => {
640                write!(f, "{destination} = const {bit_size} {value}")
641            }
642            BrilligOpcode::IndirectConst { destination_pointer, bit_size, value } => {
643                write!(f, "{destination_pointer} = indirect const {bit_size} {value}")
644            }
645            BrilligOpcode::Return => {
646                write!(f, "return")
647            }
648            BrilligOpcode::ForeignCall {
649                function,
650                destinations,
651                destination_value_types,
652                inputs,
653                input_value_types,
654            } => {
655                if !destinations.is_empty() {
656                    for (index, (destination, destination_value_type)) in
657                        destinations.iter().zip_eq(destination_value_types).enumerate()
658                    {
659                        if index > 0 {
660                            write!(f, ", ")?;
661                        }
662                        write!(f, "{destination}: {destination_value_type}")?;
663                    }
664                    write!(f, " = ")?;
665                }
666
667                write!(f, "foreign call {function}(")?;
668
669                for (index, (input, input_value_type)) in
670                    inputs.iter().zip_eq(input_value_types).enumerate()
671                {
672                    if index > 0 {
673                        write!(f, ", ")?;
674                    }
675                    write!(f, "{input}: {input_value_type}")?;
676                }
677
678                write!(f, ")")?;
679                Ok(())
680            }
681            BrilligOpcode::Mov { destination, source } => {
682                write!(f, "{destination} = {source}")
683            }
684            BrilligOpcode::ConditionalMov { destination, source_a, source_b, condition } => {
685                write!(f, "{destination} = if {condition} then {source_a} else {source_b}")
686            }
687            BrilligOpcode::Load { destination, source_pointer } => {
688                write!(f, "{destination} = load {source_pointer}")
689            }
690            BrilligOpcode::Store { destination_pointer, source } => {
691                write!(f, "store {source} at {destination_pointer}")
692            }
693            BrilligOpcode::BlackBox(black_box_op) => {
694                write!(f, "{black_box_op}")
695            }
696            BrilligOpcode::Trap { revert_data } => {
697                write!(f, "trap {revert_data}")
698            }
699            BrilligOpcode::Stop { return_data } => {
700                write!(f, "stop {return_data}")
701            }
702        }
703    }
704}
705
706/// Binary operations on field elements.
707///
708/// Most operations work with field arithmetic, but some operations like
709/// `IntegerDiv` interpret the field elements as unsigned integers for the purpose
710/// of the operation (useful when field elements are used to represent integer values).
711#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
712#[derive(Serialize, Deserialize, MsgpackTagged)]
713#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
714pub enum BinaryFieldOp {
715    #[tag(0)]
716    Add,
717    #[tag(1)]
718    Sub,
719    #[tag(2)]
720    Mul,
721    /// Field division (inverse multiplication in the field)
722    #[tag(3)]
723    Div,
724    /// Unsigned integer division (treating field elements as unsigned integers)
725    #[tag(4)]
726    IntegerDiv,
727    /// (==) Equal
728    #[tag(5)]
729    Equals,
730    /// (<) Field less than
731    #[tag(6)]
732    LessThan,
733    /// (<=) Field less or equal
734    #[tag(7)]
735    LessThanEquals,
736}
737
738impl std::fmt::Display for BinaryFieldOp {
739    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
740        match self {
741            BinaryFieldOp::Add => write!(f, "add"),
742            BinaryFieldOp::Sub => write!(f, "sub"),
743            BinaryFieldOp::Mul => write!(f, "mul"),
744            BinaryFieldOp::Div => write!(f, "field_div"),
745            BinaryFieldOp::IntegerDiv => write!(f, "int_div"),
746            BinaryFieldOp::Equals => write!(f, "eq"),
747            BinaryFieldOp::LessThan => write!(f, "lt"),
748            BinaryFieldOp::LessThanEquals => write!(f, "lt_eq"),
749        }
750    }
751}
752
753/// Binary fixed-length integer expressions
754#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
755#[derive(Serialize, Deserialize, MsgpackTagged)]
756#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
757pub enum BinaryIntOp {
758    #[tag(0)]
759    Add,
760    #[tag(1)]
761    Sub,
762    #[tag(2)]
763    Mul,
764    #[tag(3)]
765    Div,
766    /// (==) Equal
767    #[tag(4)]
768    Equals,
769    /// (<) Integer less than
770    #[tag(5)]
771    LessThan,
772    /// (<=) Integer less or equal
773    #[tag(6)]
774    LessThanEquals,
775    /// (&) Bitwise AND
776    #[tag(7)]
777    And,
778    /// (|) Bitwise OR
779    #[tag(8)]
780    Or,
781    /// (^) Bitwise XOR
782    #[tag(9)]
783    Xor,
784    /// (<<) Shift left
785    #[tag(10)]
786    Shl,
787    /// (>>) Shift right
788    #[tag(11)]
789    Shr,
790}
791
792impl std::fmt::Display for BinaryIntOp {
793    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
794        match self {
795            BinaryIntOp::Add => write!(f, "add"),
796            BinaryIntOp::Sub => write!(f, "sub"),
797            BinaryIntOp::Mul => write!(f, "mul"),
798            BinaryIntOp::Div => write!(f, "div"),
799            BinaryIntOp::Equals => write!(f, "eq"),
800            BinaryIntOp::LessThan => write!(f, "lt"),
801            BinaryIntOp::LessThanEquals => write!(f, "lt_eq"),
802            BinaryIntOp::And => write!(f, "and"),
803            BinaryIntOp::Or => write!(f, "or"),
804            BinaryIntOp::Xor => write!(f, "xor"),
805            BinaryIntOp::Shl => write!(f, "shl"),
806            BinaryIntOp::Shr => write!(f, "shr"),
807        }
808    }
809}
810
811#[cfg(test)]
812mod tests {
813    use crate::MemoryAddress;
814
815    use super::{BitSize, IntegerBitSize};
816    use acir_field::FieldElement;
817
818    /// Test that IntegerBitSize round trips correctly through From/TryFrom u32
819    #[test]
820    fn test_integer_bitsize_roundtrip() {
821        let integer_sizes = [
822            IntegerBitSize::U1,
823            IntegerBitSize::U8,
824            IntegerBitSize::U16,
825            IntegerBitSize::U32,
826            IntegerBitSize::U64,
827            IntegerBitSize::U128,
828        ];
829
830        for int_size in integer_sizes {
831            // Convert to u32 using From trait
832            let as_u32: u32 = int_size.into();
833            // Convert back using TryFrom trait
834            let roundtrip = IntegerBitSize::try_from(as_u32)
835                .expect("Should successfully convert back from u32");
836            assert_eq!(
837                int_size, roundtrip,
838                "IntegerBitSize::{int_size} should roundtrip through From<IntegerBitSize> for u32 and TryFrom<u32>"
839            );
840        }
841    }
842
843    #[test]
844    fn test_integer_bitsize_values() {
845        // Verify the actual u32 values returned by From trait
846        assert_eq!(u32::from(IntegerBitSize::U1), 1);
847        assert_eq!(u32::from(IntegerBitSize::U8), 8);
848        assert_eq!(u32::from(IntegerBitSize::U16), 16);
849        assert_eq!(u32::from(IntegerBitSize::U32), 32);
850        assert_eq!(u32::from(IntegerBitSize::U64), 64);
851        assert_eq!(u32::from(IntegerBitSize::U128), 128);
852    }
853
854    #[test]
855    fn test_integer_bitsize_try_from_invalid() {
856        // Test that invalid bit sizes return an error
857        assert!(IntegerBitSize::try_from(0).is_err());
858        assert!(IntegerBitSize::try_from(2).is_err());
859        assert!(IntegerBitSize::try_from(7).is_err());
860        assert!(IntegerBitSize::try_from(15).is_err());
861        assert!(IntegerBitSize::try_from(31).is_err());
862        assert!(IntegerBitSize::try_from(63).is_err());
863        assert!(IntegerBitSize::try_from(127).is_err());
864        assert!(IntegerBitSize::try_from(129).is_err());
865        assert!(IntegerBitSize::try_from(256).is_err());
866    }
867
868    /// Test that BitSize round-trips correctly through to_u32/try_from_u32
869    #[test]
870    fn test_bitsize_roundtrip() {
871        // Test all integer bit sizes
872        let integer_sizes = [
873            IntegerBitSize::U1,
874            IntegerBitSize::U8,
875            IntegerBitSize::U16,
876            IntegerBitSize::U32,
877            IntegerBitSize::U64,
878            IntegerBitSize::U128,
879        ];
880
881        for int_size in integer_sizes {
882            let bit_size = BitSize::Integer(int_size);
883            let as_u32 = bit_size.to_u32::<FieldElement>();
884            let roundtrip = BitSize::try_from_u32::<FieldElement>(as_u32)
885                .expect("Should successfully convert back from u32");
886            assert_eq!(
887                bit_size, roundtrip,
888                "BitSize::Integer({int_size}) should roundtrip through to_u32/try_from_u32"
889            );
890        }
891
892        // Test Field type
893        let field_bit_size = BitSize::Field;
894        let as_u32 = field_bit_size.to_u32::<FieldElement>();
895        let roundtrip = BitSize::try_from_u32::<FieldElement>(as_u32)
896            .expect("Should successfully convert Field back from u32");
897        assert_eq!(
898            field_bit_size, roundtrip,
899            "BitSize::Field should roundtrip through to_u32/try_from_u32"
900        );
901    }
902
903    #[test]
904    fn test_bitsize_to_u32_values_integers() {
905        // Verify the actual u32 values returned for integer types
906        assert_eq!(BitSize::Integer(IntegerBitSize::U1).to_u32::<FieldElement>(), 1);
907        assert_eq!(BitSize::Integer(IntegerBitSize::U8).to_u32::<FieldElement>(), 8);
908        assert_eq!(BitSize::Integer(IntegerBitSize::U16).to_u32::<FieldElement>(), 16);
909        assert_eq!(BitSize::Integer(IntegerBitSize::U32).to_u32::<FieldElement>(), 32);
910        assert_eq!(BitSize::Integer(IntegerBitSize::U64).to_u32::<FieldElement>(), 64);
911        assert_eq!(BitSize::Integer(IntegerBitSize::U128).to_u32::<FieldElement>(), 128);
912    }
913
914    #[test]
915    #[cfg(feature = "bn254")]
916    fn test_bitsize_to_u32_field_bn254() {
917        // Field type returns 254 bits for bn254
918        assert_eq!(BitSize::Field.to_u32::<FieldElement>(), 254);
919    }
920
921    #[test]
922    #[cfg(feature = "bls12_381")]
923    fn test_bitsize_to_u32_field_bls12_381() {
924        // Field type returns 255 bits for bls12_381
925        assert_eq!(BitSize::Field.to_u32::<FieldElement>(), 255);
926    }
927
928    #[test]
929    fn test_bitsize_try_from_u32_invalid() {
930        // Test that invalid bit sizes return an error
931        assert!(BitSize::try_from_u32::<FieldElement>(2).is_err());
932        assert!(BitSize::try_from_u32::<FieldElement>(7).is_err());
933        assert!(BitSize::try_from_u32::<FieldElement>(0).is_err());
934        assert!(BitSize::try_from_u32::<FieldElement>(256).is_err());
935    }
936
937    #[test]
938    #[should_panic = "memory offset overflow"]
939    fn memory_offset_overflow() {
940        let addr = MemoryAddress::direct(u32::MAX);
941        let _ = addr.offset(1);
942    }
943}
944
945#[cfg(feature = "arb")]
946mod prop_tests {
947    use proptest::arbitrary::Arbitrary;
948    use proptest::prelude::*;
949
950    use crate::lengths::SemanticLength;
951
952    use super::{BitSize, HeapValueType};
953
954    // Need to define recursive strategy for `HeapValueType`
955    impl Arbitrary for HeapValueType {
956        type Parameters = ();
957        type Strategy = BoxedStrategy<Self>;
958
959        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
960            let leaf = any::<BitSize>().prop_map(HeapValueType::Simple);
961            leaf.prop_recursive(2, 3, 2, |inner| {
962                prop_oneof![
963                    (prop::collection::vec(inner.clone(), 1..3), any::<u32>()).prop_map(
964                        |(value_types, size)| {
965                            HeapValueType::Array { value_types, size: SemanticLength(size) }
966                        }
967                    ),
968                    (prop::collection::vec(inner, 1..3))
969                        .prop_map(|value_types| { HeapValueType::Vector { value_types } }),
970                ]
971            })
972            .boxed()
973        }
974    }
975}
brillig/opcodes.rs

brillig/
opcodes.rs
