brillig/
opcodes.rs

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

brillig/
opcodes.rs
