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 IntegerBitSize {
270    pub const fn to_u32(self) -> u32 {
271        match self {
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 From<IntegerBitSize> for u32 {
283    fn from(bit_size: IntegerBitSize) -> u32 {
284        bit_size.to_u32()
285    }
286}
287
288impl TryFrom<u32> for IntegerBitSize {
289    type Error = &'static str;
290
291    fn try_from(value: u32) -> Result<Self, Self::Error> {
292        match value {
293            1 => Ok(IntegerBitSize::U1),
294            8 => Ok(IntegerBitSize::U8),
295            16 => Ok(IntegerBitSize::U16),
296            32 => Ok(IntegerBitSize::U32),
297            64 => Ok(IntegerBitSize::U64),
298            128 => Ok(IntegerBitSize::U128),
299            _ => Err("Invalid bit size"),
300        }
301    }
302}
303
304impl std::fmt::Display for IntegerBitSize {
305    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
306        match self {
307            IntegerBitSize::U1 => write!(f, "bool"),
308            IntegerBitSize::U8 => write!(f, "u8"),
309            IntegerBitSize::U16 => write!(f, "u16"),
310            IntegerBitSize::U32 => write!(f, "u32"),
311            IntegerBitSize::U64 => write!(f, "u64"),
312            IntegerBitSize::U128 => write!(f, "u128"),
313        }
314    }
315}
316
317/// Represents the bit size of values in Brillig.
318///
319/// Values can either be field elements (whose size depends on the field being used)
320/// or fixed-size unsigned integers.
321#[derive(Debug, Clone, PartialEq, Eq, Copy, PartialOrd, Ord, Hash)]
322#[derive(Serialize, Deserialize, MsgpackTagged)]
323#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
324pub enum BitSize {
325    #[tag(0)]
326    Field,
327    #[tag(1)]
328    Integer(IntegerBitSize),
329}
330
331impl BitSize {
332    /// Convert the bit size to a u32 value.
333    ///
334    /// For field elements, returns the maximum number of bits in the field.
335    /// For integers, returns the bit size of the integer type.
336    pub fn to_u32<F: AcirField>(self) -> u32 {
337        match self {
338            BitSize::Field => F::max_num_bits(),
339            BitSize::Integer(bit_size) => bit_size.into(),
340        }
341    }
342
343    /// Try to create a `BitSize` from a u32 value.
344    ///
345    /// If the value matches the field's maximum bit count, returns `BitSize::Field`.
346    /// Otherwise, attempts to interpret it as an integer bit size.
347    pub fn try_from_u32<F: AcirField>(value: u32) -> Result<Self, &'static str> {
348        if value == F::max_num_bits() {
349            Ok(BitSize::Field)
350        } else {
351            Ok(BitSize::Integer(IntegerBitSize::try_from(value)?))
352        }
353    }
354}
355
356impl std::fmt::Display for BitSize {
357    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
358        match self {
359            BitSize::Field => write!(f, "field"),
360            BitSize::Integer(bit_size) => write!(f, "{bit_size}"),
361        }
362    }
363}
364
365/// Lays out various ways an external foreign call's input and output data may be interpreted inside Brillig.
366/// This data can either be an individual value or memory.
367///
368/// While we are usually agnostic to how memory is passed within Brillig,
369/// this needs to be encoded somehow when dealing with an external system.
370/// For simplicity, the extra type information is given right in the `ForeignCall` instructions.
371#[derive(Debug, Clone, PartialEq, Eq, Copy, Hash)]
372#[derive(Serialize, Deserialize, MsgpackTagged)]
373#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
374pub enum ValueOrArray {
375    /// A single value to be passed to or from an external call.
376    /// It is an 'immediate' value - used without dereferencing.
377    /// For a foreign call input, the value is read directly from memory.
378    /// For a foreign call output, the value is written directly to memory.
379    #[tag(0)]
380    MemoryAddress(MemoryAddress),
381    /// An array to be passed to or from an external call.
382    /// In the case of a foreign call input, the array is read from this Brillig memory location + `size` more cells.
383    /// 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.
384    #[tag(1)]
385    HeapArray(HeapArray),
386    /// A vector to be passed to or from an external call.
387    /// 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.
388    /// 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.
389    #[tag(2)]
390    HeapVector(HeapVector),
391}
392
393impl std::fmt::Display for ValueOrArray {
394    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
395        match self {
396            ValueOrArray::MemoryAddress(memory_address) => {
397                write!(f, "{memory_address}")
398            }
399            ValueOrArray::HeapArray(heap_array) => {
400                write!(f, "{heap_array}")
401            }
402            ValueOrArray::HeapVector(heap_vector) => {
403                write!(f, "{heap_vector}")
404            }
405        }
406    }
407}
408
409#[derive(Debug, Clone, PartialEq, Eq, Hash)]
410#[derive(Serialize, Deserialize, MsgpackTagged)]
411#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
412pub enum BrilligOpcode<F> {
413    /// Takes the fields in addresses `lhs` and `rhs`,
414    /// performs the specified binary operation,
415    /// and stores the value in the `destination` address.
416    #[tag(0)]
417    BinaryFieldOp {
418        #[tag(0)]
419        destination: MemoryAddress,
420        #[tag(1)]
421        op: BinaryFieldOp,
422        #[tag(2)]
423        lhs: MemoryAddress,
424        #[tag(3)]
425        rhs: MemoryAddress,
426    },
427    /// Takes the `bit_size` size integers in addresses `lhs` and `rhs`,
428    /// performs the specified binary operation,
429    /// and stores the value in the `destination` address.
430    #[tag(1)]
431    BinaryIntOp {
432        #[tag(0)]
433        destination: MemoryAddress,
434        #[tag(1)]
435        op: BinaryIntOp,
436        #[tag(2)]
437        bit_size: IntegerBitSize,
438        #[tag(3)]
439        lhs: MemoryAddress,
440        #[tag(4)]
441        rhs: MemoryAddress,
442    },
443    /// Takes the value from the `source` address, inverts it,
444    /// and stores the value in the `destination` address.
445    #[tag(2)]
446    Not {
447        #[tag(0)]
448        destination: MemoryAddress,
449        #[tag(1)]
450        source: MemoryAddress,
451        #[tag(2)]
452        bit_size: IntegerBitSize,
453    },
454    /// Takes the value from the `source` address,
455    /// casts it into the type indicated by `bit_size`,
456    /// and stores the value in the `destination` address.
457    #[tag(3)]
458    Cast {
459        #[tag(0)]
460        destination: MemoryAddress,
461        #[tag(1)]
462        source: MemoryAddress,
463        #[tag(2)]
464        bit_size: BitSize,
465    },
466    /// Sets the program counter to the value of `location`
467    /// if the value at `condition` is non-zero.
468    #[tag(4)]
469    JumpIf {
470        #[tag(0)]
471        condition: MemoryAddress,
472        #[tag(1)]
473        location: Label,
474    },
475    /// Sets the program counter to the value of `location`.
476    #[tag(5)]
477    Jump {
478        #[tag(0)]
479        location: Label,
480    },
481    /// Copies the data from `calldata` from the `offset_address` with length indicated by `size_address`
482    /// to the specified `destination_address` in the memory.
483    #[tag(6)]
484    CalldataCopy {
485        #[tag(0)]
486        destination_address: MemoryAddress,
487        #[tag(1)]
488        size_address: MemoryAddress,
489        #[tag(2)]
490        offset_address: MemoryAddress,
491    },
492    /// Pushes the current program counter to the call stack as to set a return location.
493    /// Sets the program counter to the value of `location`.
494    ///
495    /// We don't support dynamic jumps or calls;
496    /// see <https://github.com/ethereum/aleth/issues/3404> for reasoning.
497    #[tag(7)]
498    Call {
499        #[tag(0)]
500        location: Label,
501    },
502    /// Stores a constant `value` with a `bit_size` in the `destination` address.
503    #[tag(8)]
504    Const {
505        #[tag(0)]
506        destination: MemoryAddress,
507        #[tag(1)]
508        bit_size: BitSize,
509        #[tag(2)]
510        value: F,
511    },
512    /// Reads the address from `destination_pointer`, then stores a constant `value` with a `bit_size` at that address.
513    #[tag(9)]
514    IndirectConst {
515        #[tag(0)]
516        destination_pointer: MemoryAddress,
517        #[tag(1)]
518        bit_size: BitSize,
519        #[tag(2)]
520        value: F,
521    },
522    /// Pops the top element from the call stack, which represents the return location,
523    /// and sets the program counter to that value. This operation is used to return
524    /// from a function call.
525    #[tag(10)]
526    Return,
527    /// Used to get data from an outside source.
528    ///
529    /// Also referred to as an Oracle, intended for things like state tree reads;
530    /// it shouldn't be confused with e.g. blockchain price oracles.
531    #[tag(11)]
532    ForeignCall {
533        /// Interpreted by caller context, ie. this will have different meanings depending on
534        /// who the caller is.
535        #[tag(0)]
536        function: String,
537        /// Destination addresses (may be single values or memory pointers).
538        ///
539        /// Output vectors are passed as a [`ValueOrArray::MemoryAddress`]. Since their size is not known up front,
540        /// we cannot allocate space for them on the heap. Instead, the VM is expected to write their data after
541        /// the current free memory pointer, and store the heap address into the destination.
542        #[tag(1)]
543        destinations: Vec<ValueOrArray>,
544        /// Destination value types.
545        #[tag(2)]
546        destination_value_types: Vec<HeapValueType>,
547        /// Input addresses (may be single values or memory pointers).
548        #[tag(3)]
549        inputs: Vec<ValueOrArray>,
550        /// Input value types (for heap allocated structures indicates how to
551        /// retrieve the elements).
552        #[tag(4)]
553        input_value_types: Vec<HeapValueType>,
554    },
555    /// Moves the content in the `source` address to the `destination` address.
556    #[tag(12)]
557    Mov {
558        #[tag(0)]
559        destination: MemoryAddress,
560        #[tag(1)]
561        source: MemoryAddress,
562    },
563    /// If the value at `condition` is non-zero, moves the content in the `source_a`
564    /// address to the `destination` address, otherwise moves the content from the
565    /// `source_b` address instead.
566    ///
567    /// `destination = condition > 0 ? source_a : source_b`
568    #[tag(13)]
569    ConditionalMov {
570        #[tag(0)]
571        destination: MemoryAddress,
572        #[tag(1)]
573        source_a: MemoryAddress,
574        #[tag(2)]
575        source_b: MemoryAddress,
576        #[tag(3)]
577        condition: MemoryAddress,
578    },
579    /// Reads the `source_pointer` to obtain a memory address, then retrieves the data
580    /// stored at that address and writes it to the `destination` address.
581    #[tag(14)]
582    Load {
583        #[tag(0)]
584        destination: MemoryAddress,
585        #[tag(1)]
586        source_pointer: MemoryAddress,
587    },
588    /// Reads the `destination_pointer` to obtain a memory address, then stores the value
589    /// from the `source` address at that location.
590    #[tag(15)]
591    Store {
592        #[tag(0)]
593        destination_pointer: MemoryAddress,
594        #[tag(1)]
595        source: MemoryAddress,
596    },
597    /// Native functions in the VM.
598    /// These are equivalent to the black box functions in ACIR.
599    #[tag(16)]
600    BlackBox(BlackBoxOp),
601    /// Used to denote execution failure, halting the VM and returning data specified by a dynamically-sized vector.
602    #[tag(17)]
603    Trap {
604        #[tag(0)]
605        revert_data: HeapVector,
606    },
607    /// Halts execution and returns data specified by a dynamically-sized vector.
608    #[tag(18)]
609    Stop {
610        #[tag(0)]
611        return_data: HeapVector,
612    },
613}
614
615impl<F: std::fmt::Display> std::fmt::Display for BrilligOpcode<F> {
616    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
617        match self {
618            BrilligOpcode::BinaryFieldOp { destination, op, lhs, rhs } => {
619                write!(f, "{destination} = field {op} {lhs}, {rhs}")
620            }
621            BrilligOpcode::BinaryIntOp { destination, op, bit_size, lhs, rhs } => {
622                write!(f, "{destination} = {bit_size} {op} {lhs}, {rhs}")
623            }
624            BrilligOpcode::Not { destination, source, bit_size } => {
625                write!(f, "{destination} = {bit_size} not {source}")
626            }
627            BrilligOpcode::Cast { destination, source, bit_size } => {
628                write!(f, "{destination} = cast {source} to {bit_size}")
629            }
630            BrilligOpcode::JumpIf { condition, location } => {
631                write!(f, "jump if {condition} to {location}")
632            }
633            BrilligOpcode::Jump { location } => {
634                write!(f, "jump to {location}")
635            }
636            BrilligOpcode::CalldataCopy { destination_address, size_address, offset_address } => {
637                write!(
638                    f,
639                    "{destination_address} = calldata copy [{offset_address}; {size_address}]"
640                )
641            }
642            BrilligOpcode::Call { location } => {
643                write!(f, "call {location}")
644            }
645            BrilligOpcode::Const { destination, bit_size, value } => {
646                write!(f, "{destination} = const {bit_size} {value}")
647            }
648            BrilligOpcode::IndirectConst { destination_pointer, bit_size, value } => {
649                write!(f, "{destination_pointer} = indirect const {bit_size} {value}")
650            }
651            BrilligOpcode::Return => {
652                write!(f, "return")
653            }
654            BrilligOpcode::ForeignCall {
655                function,
656                destinations,
657                destination_value_types,
658                inputs,
659                input_value_types,
660            } => {
661                if !destinations.is_empty() {
662                    for (index, (destination, destination_value_type)) in
663                        destinations.iter().zip_eq(destination_value_types).enumerate()
664                    {
665                        if index > 0 {
666                            write!(f, ", ")?;
667                        }
668                        write!(f, "{destination}: {destination_value_type}")?;
669                    }
670                    write!(f, " = ")?;
671                }
672
673                write!(f, "foreign call {function}(")?;
674
675                for (index, (input, input_value_type)) in
676                    inputs.iter().zip_eq(input_value_types).enumerate()
677                {
678                    if index > 0 {
679                        write!(f, ", ")?;
680                    }
681                    write!(f, "{input}: {input_value_type}")?;
682                }
683
684                write!(f, ")")?;
685                Ok(())
686            }
687            BrilligOpcode::Mov { destination, source } => {
688                write!(f, "{destination} = {source}")
689            }
690            BrilligOpcode::ConditionalMov { destination, source_a, source_b, condition } => {
691                write!(f, "{destination} = if {condition} then {source_a} else {source_b}")
692            }
693            BrilligOpcode::Load { destination, source_pointer } => {
694                write!(f, "{destination} = load {source_pointer}")
695            }
696            BrilligOpcode::Store { destination_pointer, source } => {
697                write!(f, "store {source} at {destination_pointer}")
698            }
699            BrilligOpcode::BlackBox(black_box_op) => {
700                write!(f, "{black_box_op}")
701            }
702            BrilligOpcode::Trap { revert_data } => {
703                write!(f, "trap {revert_data}")
704            }
705            BrilligOpcode::Stop { return_data } => {
706                write!(f, "stop {return_data}")
707            }
708        }
709    }
710}
711
712/// Binary operations on field elements.
713///
714/// Most operations work with field arithmetic, but some operations like
715/// `IntegerDiv` interpret the field elements as unsigned integers for the purpose
716/// of the operation (useful when field elements are used to represent integer values).
717#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
718#[derive(Serialize, Deserialize, MsgpackTagged)]
719#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
720pub enum BinaryFieldOp {
721    #[tag(0)]
722    Add,
723    #[tag(1)]
724    Sub,
725    #[tag(2)]
726    Mul,
727    /// Field division (inverse multiplication in the field)
728    #[tag(3)]
729    Div,
730    /// Unsigned integer division (treating field elements as unsigned integers)
731    #[tag(4)]
732    IntegerDiv,
733    /// (==) Equal
734    #[tag(5)]
735    Equals,
736    /// (<) Field less than
737    #[tag(6)]
738    LessThan,
739    /// (<=) Field less or equal
740    #[tag(7)]
741    LessThanEquals,
742}
743
744impl std::fmt::Display for BinaryFieldOp {
745    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
746        match self {
747            BinaryFieldOp::Add => write!(f, "add"),
748            BinaryFieldOp::Sub => write!(f, "sub"),
749            BinaryFieldOp::Mul => write!(f, "mul"),
750            BinaryFieldOp::Div => write!(f, "field_div"),
751            BinaryFieldOp::IntegerDiv => write!(f, "int_div"),
752            BinaryFieldOp::Equals => write!(f, "eq"),
753            BinaryFieldOp::LessThan => write!(f, "lt"),
754            BinaryFieldOp::LessThanEquals => write!(f, "lt_eq"),
755        }
756    }
757}
758
759/// Binary fixed-length integer expressions
760#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
761#[derive(Serialize, Deserialize, MsgpackTagged)]
762#[cfg_attr(feature = "arb", derive(proptest_derive::Arbitrary))]
763pub enum BinaryIntOp {
764    #[tag(0)]
765    Add,
766    #[tag(1)]
767    Sub,
768    #[tag(2)]
769    Mul,
770    #[tag(3)]
771    Div,
772    /// (==) Equal
773    #[tag(4)]
774    Equals,
775    /// (<) Integer less than
776    #[tag(5)]
777    LessThan,
778    /// (<=) Integer less or equal
779    #[tag(6)]
780    LessThanEquals,
781    /// (&) Bitwise AND
782    #[tag(7)]
783    And,
784    /// (|) Bitwise OR
785    #[tag(8)]
786    Or,
787    /// (^) Bitwise XOR
788    #[tag(9)]
789    Xor,
790    /// (<<) Shift left
791    #[tag(10)]
792    Shl,
793    /// (>>) Shift right
794    #[tag(11)]
795    Shr,
796}
797
798impl std::fmt::Display for BinaryIntOp {
799    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
800        match self {
801            BinaryIntOp::Add => write!(f, "add"),
802            BinaryIntOp::Sub => write!(f, "sub"),
803            BinaryIntOp::Mul => write!(f, "mul"),
804            BinaryIntOp::Div => write!(f, "div"),
805            BinaryIntOp::Equals => write!(f, "eq"),
806            BinaryIntOp::LessThan => write!(f, "lt"),
807            BinaryIntOp::LessThanEquals => write!(f, "lt_eq"),
808            BinaryIntOp::And => write!(f, "and"),
809            BinaryIntOp::Or => write!(f, "or"),
810            BinaryIntOp::Xor => write!(f, "xor"),
811            BinaryIntOp::Shl => write!(f, "shl"),
812            BinaryIntOp::Shr => write!(f, "shr"),
813        }
814    }
815}
816
817#[cfg(test)]
818mod tests {
819    use crate::MemoryAddress;
820
821    use super::{BitSize, IntegerBitSize};
822    use acir_field::FieldElement;
823
824    /// Test that `IntegerBitSize` round trips correctly through From/TryFrom u32
825    #[test]
826    fn test_integer_bitsize_roundtrip() {
827        let integer_sizes = [
828            IntegerBitSize::U1,
829            IntegerBitSize::U8,
830            IntegerBitSize::U16,
831            IntegerBitSize::U32,
832            IntegerBitSize::U64,
833            IntegerBitSize::U128,
834        ];
835
836        for int_size in integer_sizes {
837            // Convert to u32 using From trait
838            let as_u32: u32 = int_size.into();
839            // Convert back using TryFrom trait
840            let roundtrip = IntegerBitSize::try_from(as_u32)
841                .expect("Should successfully convert back from u32");
842            assert_eq!(
843                int_size, roundtrip,
844                "IntegerBitSize::{int_size} should roundtrip through From<IntegerBitSize> for u32 and TryFrom<u32>"
845            );
846        }
847    }
848
849    #[test]
850    fn test_integer_bitsize_values() {
851        // Verify the actual u32 values returned by From trait
852        assert_eq!(u32::from(IntegerBitSize::U1), 1);
853        assert_eq!(u32::from(IntegerBitSize::U8), 8);
854        assert_eq!(u32::from(IntegerBitSize::U16), 16);
855        assert_eq!(u32::from(IntegerBitSize::U32), 32);
856        assert_eq!(u32::from(IntegerBitSize::U64), 64);
857        assert_eq!(u32::from(IntegerBitSize::U128), 128);
858    }
859
860    #[test]
861    fn test_integer_bitsize_try_from_invalid() {
862        // Test that invalid bit sizes return an error
863        assert!(IntegerBitSize::try_from(0).is_err());
864        assert!(IntegerBitSize::try_from(2).is_err());
865        assert!(IntegerBitSize::try_from(7).is_err());
866        assert!(IntegerBitSize::try_from(15).is_err());
867        assert!(IntegerBitSize::try_from(31).is_err());
868        assert!(IntegerBitSize::try_from(63).is_err());
869        assert!(IntegerBitSize::try_from(127).is_err());
870        assert!(IntegerBitSize::try_from(129).is_err());
871        assert!(IntegerBitSize::try_from(256).is_err());
872    }
873
874    /// Test that `BitSize` round-trips correctly through `to_u32/try_from_u32`
875    #[test]
876    fn test_bitsize_roundtrip() {
877        // Test all integer bit sizes
878        let integer_sizes = [
879            IntegerBitSize::U1,
880            IntegerBitSize::U8,
881            IntegerBitSize::U16,
882            IntegerBitSize::U32,
883            IntegerBitSize::U64,
884            IntegerBitSize::U128,
885        ];
886
887        for int_size in integer_sizes {
888            let bit_size = BitSize::Integer(int_size);
889            let as_u32 = bit_size.to_u32::<FieldElement>();
890            let roundtrip = BitSize::try_from_u32::<FieldElement>(as_u32)
891                .expect("Should successfully convert back from u32");
892            assert_eq!(
893                bit_size, roundtrip,
894                "BitSize::Integer({int_size}) should roundtrip through to_u32/try_from_u32"
895            );
896        }
897
898        // Test Field type
899        let field_bit_size = BitSize::Field;
900        let as_u32 = field_bit_size.to_u32::<FieldElement>();
901        let roundtrip = BitSize::try_from_u32::<FieldElement>(as_u32)
902            .expect("Should successfully convert Field back from u32");
903        assert_eq!(
904            field_bit_size, roundtrip,
905            "BitSize::Field should roundtrip through to_u32/try_from_u32"
906        );
907    }
908
909    #[test]
910    fn test_bitsize_to_u32_values_integers() {
911        // Verify the actual u32 values returned for integer types
912        assert_eq!(BitSize::Integer(IntegerBitSize::U1).to_u32::<FieldElement>(), 1);
913        assert_eq!(BitSize::Integer(IntegerBitSize::U8).to_u32::<FieldElement>(), 8);
914        assert_eq!(BitSize::Integer(IntegerBitSize::U16).to_u32::<FieldElement>(), 16);
915        assert_eq!(BitSize::Integer(IntegerBitSize::U32).to_u32::<FieldElement>(), 32);
916        assert_eq!(BitSize::Integer(IntegerBitSize::U64).to_u32::<FieldElement>(), 64);
917        assert_eq!(BitSize::Integer(IntegerBitSize::U128).to_u32::<FieldElement>(), 128);
918    }
919
920    #[test]
921    #[cfg(feature = "bn254")]
922    fn test_bitsize_to_u32_field_bn254() {
923        // Field type returns 254 bits for bn254
924        assert_eq!(BitSize::Field.to_u32::<FieldElement>(), 254);
925    }
926
927    #[test]
928    #[cfg(feature = "bls12_381")]
929    fn test_bitsize_to_u32_field_bls12_381() {
930        // Field type returns 255 bits for bls12_381
931        assert_eq!(BitSize::Field.to_u32::<FieldElement>(), 255);
932    }
933
934    #[test]
935    fn test_bitsize_try_from_u32_invalid() {
936        // Test that invalid bit sizes return an error
937        assert!(BitSize::try_from_u32::<FieldElement>(2).is_err());
938        assert!(BitSize::try_from_u32::<FieldElement>(7).is_err());
939        assert!(BitSize::try_from_u32::<FieldElement>(0).is_err());
940        assert!(BitSize::try_from_u32::<FieldElement>(256).is_err());
941    }
942
943    #[test]
944    #[should_panic = "memory offset overflow"]
945    fn memory_offset_overflow() {
946        let addr = MemoryAddress::direct(u32::MAX);
947        let _ = addr.offset(1);
948    }
949}
950
951#[cfg(feature = "arb")]
952mod prop_tests {
953    use proptest::arbitrary::Arbitrary;
954    use proptest::prelude::*;
955
956    use crate::lengths::SemanticLength;
957
958    use super::{BitSize, HeapValueType};
959
960    // Need to define recursive strategy for `HeapValueType`
961    impl Arbitrary for HeapValueType {
962        type Parameters = ();
963        type Strategy = BoxedStrategy<Self>;
964
965        fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
966            let leaf = any::<BitSize>().prop_map(HeapValueType::Simple);
967            leaf.prop_recursive(2, 3, 2, |inner| {
968                prop_oneof![
969                    (prop::collection::vec(inner.clone(), 1..3), any::<u32>()).prop_map(
970                        |(value_types, size)| {
971                            HeapValueType::Array { value_types, size: SemanticLength(size) }
972                        }
973                    ),
974                    (prop::collection::vec(inner, 1..3))
975                        .prop_map(|value_types| { HeapValueType::Vector { value_types } }),
976                ]
977            })
978            .boxed()
979        }
980    }
981}
brillig/opcodes.rs

brillig/
opcodes.rs
