cairo_lang_sierra/extensions/modules/
circuit.rs

1use std::ops::Shl;
2use std::sync::LazyLock;
3
4use cairo_lang_utils::unordered_hash_map::UnorderedHashMap;
5use cairo_lang_utils::unordered_hash_set::UnorderedHashSet;
6use cairo_lang_utils::{extract_matches, require};
7use num_bigint::BigInt;
8use num_traits::{One, Signed, ToPrimitive, Zero};
9
10use super::range_check::RangeCheck96Type;
11use super::structure::StructType;
12use super::utils::{Range, reinterpret_cast_signature};
13use crate::extensions::bounded_int::bounded_int_ty;
14use crate::extensions::lib_func::{
15    BranchSignature, DeferredOutputKind, LibfuncSignature, OutputVarInfo, ParamSignature,
16    SierraApChange, SignatureAndTypeGenericLibfunc, SignatureSpecializationContext,
17    SpecializationContext, WrapSignatureAndTypeGenericLibfunc,
18};
19use crate::extensions::type_specialization_context::TypeSpecializationContext;
20use crate::extensions::types::{InfoOnlyConcreteType, TypeInfo};
21use crate::extensions::{
22    ConcreteType, NamedLibfunc, NamedType, NoGenericArgsGenericLibfunc, NoGenericArgsGenericType,
23    OutputVarReferenceInfo, SignatureBasedConcreteLibfunc, SpecializationError,
24    args_as_single_type, args_as_single_value, args_as_two_types, extract_type_generic_args,
25};
26use crate::ids::{ConcreteTypeId, GenericTypeId, UserTypeId};
27use crate::program::{ConcreteTypeLongId, GenericArg};
28use crate::{define_libfunc_hierarchy, define_type_hierarchy};
29
30/// The set of types that are considered circuit components.
31/// A circuit it defined as Circuit<(Output0, Output1, ...)> where all the outputs are
32/// circuit components (recursively).
33static CIRCUIT_COMPONENTS: LazyLock<UnorderedHashSet<GenericTypeId>> = LazyLock::new(|| {
34    UnorderedHashSet::from_iter([
35        CircuitInput::ID,
36        AddModGate::ID,
37        InverseGate::ID,
38        MulModGate::ID,
39        SubModGate::ID,
40    ])
41});
42
43/// The number of limbs used to represent a single value in the circuit.
44pub const VALUE_SIZE: usize = 4;
45/// The size of the AddMod and MulMod builtin instances.
46pub const MOD_BUILTIN_INSTANCE_SIZE: usize = 7;
47/// A gate is defined by 3 offsets, the first two are the inputs and the third is the output.
48pub const OFFSETS_PER_GATE: usize = 3;
49/// The offset of the values in the values array.
50pub const ONE_OFFSET: usize = 0;
51
52define_type_hierarchy! {
53    pub enum CircuitType {
54        AddMod(AddModType),
55        MulMod(MulModType),
56        AddModGate(AddModGate),
57        Circuit(Circuit),
58        CircuitData(CircuitData),
59        CircuitOutputs(CircuitOutputs),
60        CircuitPartialOutputs(CircuitPartialOutputs),
61        CircuitDescriptor(CircuitDescriptor),
62        CircuitFailureGuarantee(CircuitFailureGuarantee),
63        CircuitInput(CircuitInput),
64        CircuitInputAccumulator(CircuitInputAccumulator),
65        CircuitModulus(CircuitModulus),
66        InverseGate(InverseGate),
67        MulModGate(MulModGate),
68        SubModGate(SubModGate),
69        U96Guarantee(U96Guarantee),
70        U96LimbsLessThanGuarantee(U96LimbsLessThanGuarantee),
71    }, CircuitTypeConcrete
72}
73
74define_libfunc_hierarchy! {
75    pub enum CircuitLibFunc {
76        AddInput(AddCircuitInputLibFunc),
77        Eval(EvalCircuitLibFunc),
78        GetDescriptor(GetCircuitDescriptorLibFunc),
79        InitCircuitData(InitCircuitDataLibFunc),
80        GetOutput(GetOutputLibFunc),
81        TryIntoCircuitModulus(TryIntoCircuitModulusLibFunc),
82        FailureGuaranteeVerify(CircuitFailureGuaranteeVerifyLibFunc),
83        IntoU96Guarantee(IntoU96GuaranteeLibFunc),
84        U96GuaranteeVerify(U96GuaranteeVerifyLibFunc),
85        U96LimbsLessThanGuaranteeVerify(U96LimbsLessThanGuaranteeVerifyLibfunc),
86        U96SingleLimbLessThanGuaranteeVerify(U96SingleLimbLessThanGuaranteeVerifyLibfunc),
87    }, CircuitConcreteLibfunc
88}
89
90/// Returns true if `generic_arg` is a type that is considered a circuit component.
91fn is_circuit_component(
92    context: &dyn TypeSpecializationContext,
93    generic_arg: &GenericArg,
94) -> Result<bool, SpecializationError> {
95    let GenericArg::Type(ty) = generic_arg else {
96        return Err(SpecializationError::UnsupportedGenericArg);
97    };
98
99    let long_id = context.get_type_info(ty.clone())?.long_id;
100    Ok(CIRCUIT_COMPONENTS.contains(&long_id.generic_id))
101}
102
103/// Circuit input type.
104#[derive(Default)]
105pub struct CircuitInput {}
106impl NamedType for CircuitInput {
107    type Concrete = ConcreteCircuitInput;
108    const ID: GenericTypeId = GenericTypeId::new_inline("CircuitInput");
109
110    fn specialize(
111        &self,
112        _context: &dyn TypeSpecializationContext,
113        args: &[GenericArg],
114    ) -> Result<Self::Concrete, SpecializationError> {
115        let idx = args_as_single_value(args)?
116            .to_usize()
117            .ok_or(SpecializationError::UnsupportedGenericArg)?;
118        Ok(Self::Concrete { info: circuit_component_type_info(Self::ID, args), idx })
119    }
120}
121
122/// Defines an input for a circuit.
123pub struct ConcreteCircuitInput {
124    // The type info of the concrete type.
125    pub info: TypeInfo,
126    // The index of the circuit input.
127    pub idx: usize,
128}
129
130impl ConcreteType for ConcreteCircuitInput {
131    fn info(&self) -> &TypeInfo {
132        &self.info
133    }
134}
135
136/// Validate gate generic arguments.
137fn validate_gate_generic_args(
138    context: &dyn TypeSpecializationContext,
139    args: &[GenericArg],
140) -> Result<(), SpecializationError> {
141    if args.len() != 2 {
142        return Err(SpecializationError::WrongNumberOfGenericArgs);
143    }
144    validate_args_are_circuit_components(context, args.iter())
145}
146
147/// Represents the action of adding two fields elements in the circuits builtin.
148#[derive(Default)]
149pub struct AddModGate {}
150impl NamedType for AddModGate {
151    type Concrete = InfoOnlyConcreteType;
152    const ID: GenericTypeId = GenericTypeId::new_inline("AddModGate");
153
154    fn specialize(
155        &self,
156        context: &dyn TypeSpecializationContext,
157        args: &[GenericArg],
158    ) -> Result<Self::Concrete, SpecializationError> {
159        validate_gate_generic_args(context, args)?;
160        Ok(Self::Concrete { info: circuit_component_type_info(Self::ID, args) })
161    }
162}
163
164// Represents the action of adding two fields elements in the circuits builtin.
165#[derive(Default)]
166pub struct SubModGate {}
167impl NamedType for SubModGate {
168    type Concrete = InfoOnlyConcreteType;
169    const ID: GenericTypeId = GenericTypeId::new_inline("SubModGate");
170
171    fn specialize(
172        &self,
173        context: &dyn TypeSpecializationContext,
174        args: &[GenericArg],
175    ) -> Result<Self::Concrete, SpecializationError> {
176        validate_gate_generic_args(context, args)?;
177        Ok(Self::Concrete { info: circuit_component_type_info(Self::ID, args) })
178    }
179}
180
181/// Represents the action of multiplying two fields elements in the circuits builtin.
182#[derive(Default)]
183pub struct MulModGate {}
184impl NamedType for MulModGate {
185    type Concrete = InfoOnlyConcreteType;
186    const ID: GenericTypeId = GenericTypeId::new_inline("MulModGate");
187
188    fn specialize(
189        &self,
190        context: &dyn TypeSpecializationContext,
191        args: &[GenericArg],
192    ) -> Result<Self::Concrete, SpecializationError> {
193        validate_gate_generic_args(context, args)?;
194        Ok(Self::Concrete { info: circuit_component_type_info(Self::ID, args) })
195    }
196}
197
198/// Represents the action of computing the inverse of a fields element in the circuits builtin.
199#[derive(Default)]
200pub struct InverseGate {}
201impl NamedType for InverseGate {
202    type Concrete = InfoOnlyConcreteType;
203    const ID: GenericTypeId = GenericTypeId::new_inline("InverseGate");
204
205    fn specialize(
206        &self,
207        context: &dyn TypeSpecializationContext,
208        args: &[GenericArg],
209    ) -> Result<Self::Concrete, SpecializationError> {
210        if args.len() != 1 {
211            return Err(SpecializationError::WrongNumberOfGenericArgs);
212        }
213        validate_args_are_circuit_components(context, args.iter())?;
214        Ok(Self::Concrete { info: circuit_component_type_info(Self::ID, args) })
215    }
216}
217
218/// Type for accumulating inputs into the circuit instance's data.
219#[derive(Default)]
220pub struct CircuitInputAccumulator {}
221impl NamedType for CircuitInputAccumulator {
222    type Concrete = InfoOnlyConcreteType;
223    const ID: GenericTypeId = GenericTypeId::new_inline("CircuitInputAccumulator");
224
225    fn specialize(
226        &self,
227        context: &dyn TypeSpecializationContext,
228        args: &[GenericArg],
229    ) -> Result<Self::Concrete, SpecializationError> {
230        let circ_ty = args_as_single_type(args)?;
231        validate_is_circuit(context, circ_ty)?;
232        Ok(Self::Concrete {
233            info: TypeInfo {
234                long_id: ConcreteTypeLongId { generic_id: Self::ID, generic_args: args.to_vec() },
235                duplicatable: false,
236                droppable: true,
237                storable: true,
238                zero_sized: false,
239            },
240        })
241    }
242}
243
244/// A type that can be used as a circuit modulus (a u384 that is not zero or one)
245#[derive(Default)]
246pub struct CircuitModulus {}
247impl NoGenericArgsGenericType for CircuitModulus {
248    const ID: GenericTypeId = GenericTypeId::new_inline("CircuitModulus");
249    const STORABLE: bool = true;
250    const DUPLICATABLE: bool = true;
251    const DROPPABLE: bool = true;
252    const ZERO_SIZED: bool = false;
253}
254
255/// A type representing a circuit instance data with all the inputs added.
256#[derive(Default)]
257pub struct CircuitData {}
258impl NamedType for CircuitData {
259    type Concrete = InfoOnlyConcreteType;
260    const ID: GenericTypeId = GenericTypeId::new_inline("CircuitData");
261
262    fn specialize(
263        &self,
264        context: &dyn TypeSpecializationContext,
265        args: &[GenericArg],
266    ) -> Result<Self::Concrete, SpecializationError> {
267        let circ_ty = args_as_single_type(args)?;
268        validate_is_circuit(context, circ_ty)?;
269        Ok(Self::Concrete {
270            info: TypeInfo {
271                long_id: ConcreteTypeLongId { generic_id: Self::ID, generic_args: args.to_vec() },
272                duplicatable: false,
273                droppable: true,
274                storable: true,
275                zero_sized: false,
276            },
277        })
278    }
279}
280
281/// A type representing a circuit instance where the outputs is filled.
282#[derive(Default)]
283pub struct CircuitOutputs {}
284impl NamedType for CircuitOutputs {
285    type Concrete = InfoOnlyConcreteType;
286    const ID: GenericTypeId = GenericTypeId::new_inline("CircuitOutputs");
287
288    fn specialize(
289        &self,
290        context: &dyn TypeSpecializationContext,
291        args: &[GenericArg],
292    ) -> Result<Self::Concrete, SpecializationError> {
293        let circ_ty = args_as_single_type(args)?;
294        validate_is_circuit(context, circ_ty)?;
295        Ok(Self::Concrete {
296            info: TypeInfo {
297                long_id: ConcreteTypeLongId { generic_id: Self::ID, generic_args: args.to_vec() },
298                duplicatable: true,
299                droppable: true,
300                storable: true,
301                zero_sized: false,
302            },
303        })
304    }
305}
306
307/// A type representing a circuit instance where the outputs are partially filled as
308/// the evaluation of one of the inverse gates failed.
309#[derive(Default)]
310pub struct CircuitPartialOutputs {}
311impl NamedType for CircuitPartialOutputs {
312    type Concrete = InfoOnlyConcreteType;
313    const ID: GenericTypeId = GenericTypeId::new_inline("CircuitPartialOutputs");
314
315    fn specialize(
316        &self,
317        context: &dyn TypeSpecializationContext,
318        args: &[GenericArg],
319    ) -> Result<Self::Concrete, SpecializationError> {
320        let circ_ty = args_as_single_type(args)?;
321        validate_is_circuit(context, circ_ty)?;
322        Ok(Self::Concrete {
323            info: TypeInfo {
324                long_id: ConcreteTypeLongId { generic_id: Self::ID, generic_args: args.to_vec() },
325                duplicatable: false,
326                droppable: true,
327                storable: true,
328                zero_sized: false,
329            },
330        })
331    }
332}
333
334/// A type whose destruction guarantees that the circuit instance invocation failed.
335#[derive(Default)]
336pub struct CircuitFailureGuarantee {}
337impl NoGenericArgsGenericType for CircuitFailureGuarantee {
338    const ID: GenericTypeId = GenericTypeId::new_inline("CircuitFailureGuarantee");
339    const STORABLE: bool = true;
340    const DUPLICATABLE: bool = false;
341    const DROPPABLE: bool = false;
342    const ZERO_SIZED: bool = false;
343}
344
345/// A type whose destruction guarantees that u96-limbs based value is smaller than another.
346#[derive(Default)]
347pub struct U96LimbsLessThanGuarantee {}
348impl NamedType for U96LimbsLessThanGuarantee {
349    type Concrete = ConcreteU96LimbsLessThanGuarantee;
350    // Shortened name to fit in the 23 bytes limit.
351    const ID: GenericTypeId = GenericTypeId::new_inline("U96LimbsLtGuarantee");
352
353    fn specialize(
354        &self,
355        _context: &dyn TypeSpecializationContext,
356        args: &[GenericArg],
357    ) -> Result<Self::Concrete, SpecializationError> {
358        let limb_count = args_as_single_value(args)?
359            .to_usize()
360            .ok_or(SpecializationError::UnsupportedGenericArg)?;
361        require(limb_count >= 1).ok_or(SpecializationError::UnsupportedGenericArg)?;
362        Ok(Self::Concrete {
363            info: TypeInfo {
364                long_id: ConcreteTypeLongId {
365                    generic_id: <Self as NamedType>::ID,
366                    generic_args: args.to_vec(),
367                },
368                duplicatable: false,
369                droppable: false,
370                storable: true,
371                zero_sized: false,
372            },
373            limb_count,
374        })
375    }
376}
377
378pub struct ConcreteU96LimbsLessThanGuarantee {
379    pub info: TypeInfo,
380    pub limb_count: usize,
381}
382
383impl ConcreteType for ConcreteU96LimbsLessThanGuarantee {
384    fn info(&self) -> &TypeInfo {
385        &self.info
386    }
387}
388
389/// A value that is guaranteed to fit in a u96.
390/// This value can only be dropped by being written to a 96bit range check.
391#[derive(Default)]
392pub struct U96Guarantee {}
393impl NoGenericArgsGenericType for U96Guarantee {
394    const ID: GenericTypeId = GenericTypeId::new_inline("U96Guarantee");
395    const STORABLE: bool = true;
396    const DUPLICATABLE: bool = false;
397    const DROPPABLE: bool = false;
398    const ZERO_SIZED: bool = false;
399}
400
401/// A type representing the circuit add and mul tables.
402#[derive(Default)]
403pub struct CircuitDescriptor {}
404impl NamedType for CircuitDescriptor {
405    type Concrete = InfoOnlyConcreteType;
406    const ID: GenericTypeId = GenericTypeId::new_inline("CircuitDescriptor");
407
408    fn specialize(
409        &self,
410        context: &dyn TypeSpecializationContext,
411        args: &[GenericArg],
412    ) -> Result<Self::Concrete, SpecializationError> {
413        let circ_ty = args_as_single_type(args)?;
414        validate_is_circuit(context, circ_ty.clone())?;
415        Ok(Self::Concrete {
416            info: TypeInfo {
417                long_id: ConcreteTypeLongId { generic_id: Self::ID, generic_args: args.to_vec() },
418                duplicatable: true,
419                droppable: true,
420                storable: true,
421                zero_sized: false,
422            },
423        })
424    }
425}
426
427/// A type that creates a circuit from a tuple of outputs.
428#[derive(Default)]
429pub struct Circuit {}
430impl NamedType for Circuit {
431    type Concrete = ConcreteCircuit;
432    const ID: GenericTypeId = GenericTypeId::new_inline("Circuit");
433
434    fn specialize(
435        &self,
436        context: &dyn TypeSpecializationContext,
437        args: &[GenericArg],
438    ) -> Result<Self::Concrete, SpecializationError> {
439        Self::Concrete::new(context, args)
440    }
441}
442
443pub struct ConcreteCircuit {
444    pub info: TypeInfo,
445    pub circuit_info: CircuitInfo,
446}
447
448impl ConcreteCircuit {
449    fn new(
450        context: &dyn TypeSpecializationContext,
451        args: &[GenericArg],
452    ) -> Result<Self, SpecializationError> {
453        let output_tuple = args_as_single_type(args)?;
454
455        let circuit_info = get_circuit_info(context, &output_tuple)?;
456        Ok(Self {
457            info: TypeInfo {
458                long_id: ConcreteTypeLongId {
459                    generic_id: "Circuit".into(),
460                    generic_args: args.to_vec(),
461                },
462                duplicatable: false,
463                droppable: false,
464                storable: false,
465                zero_sized: true,
466            },
467            circuit_info,
468        })
469    }
470}
471
472impl ConcreteType for ConcreteCircuit {
473    fn info(&self) -> &TypeInfo {
474        &self.info
475    }
476}
477
478/// Validate that `circ_ty` is a circuit type.
479fn validate_is_circuit(
480    context: &dyn TypeSpecializationContext,
481    circ_ty: ConcreteTypeId,
482) -> Result<(), SpecializationError> {
483    if context.get_type_info(circ_ty.clone())?.long_id.generic_id != Circuit::ID {
484        return Err(SpecializationError::UnsupportedGenericArg);
485    }
486    Ok(())
487}
488
489/// Validate that all the generic arguments are circuit components.
490fn validate_args_are_circuit_components<'a>(
491    context: &dyn TypeSpecializationContext,
492    generic_args: impl Iterator<Item = &'a GenericArg>,
493) -> Result<(), SpecializationError> {
494    for generic_arg in generic_args {
495        // Note that its enough to check the topmost types as they validate their children.
496        if !is_circuit_component(context, generic_arg)? {
497            return Err(SpecializationError::UnsupportedGenericArg);
498        }
499    }
500
501    Ok(())
502}
503
504/// Libfunc for initializing the input data for running an instance of the circuit.
505#[derive(Default)]
506pub struct InitCircuitDataLibFuncWrapped {}
507impl SignatureAndTypeGenericLibfunc for InitCircuitDataLibFuncWrapped {
508    const STR_ID: &'static str = "init_circuit_data";
509
510    fn specialize_signature(
511        &self,
512        context: &dyn SignatureSpecializationContext,
513        ty: ConcreteTypeId,
514    ) -> Result<LibfuncSignature, SpecializationError> {
515        let range_check96_type = context.get_concrete_type(RangeCheck96Type::id(), &[])?;
516        let circuit_input_accumulator_ty =
517            context.get_concrete_type(CircuitInputAccumulator::id(), &[GenericArg::Type(ty)])?;
518        Ok(LibfuncSignature::new_non_branch_ex(
519            vec![ParamSignature::new(range_check96_type.clone()).with_allow_add_const()],
520            vec![
521                OutputVarInfo {
522                    ty: range_check96_type.clone(),
523                    ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::AddConst {
524                        param_idx: 0,
525                    }),
526                },
527                OutputVarInfo {
528                    ty: circuit_input_accumulator_ty.clone(),
529                    ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
530                },
531            ],
532            SierraApChange::Known { new_vars_only: true },
533        ))
534    }
535}
536
537pub type InitCircuitDataLibFunc = WrapSignatureAndTypeGenericLibfunc<InitCircuitDataLibFuncWrapped>;
538
539/// libfunc for adding an input in the circuit instance's data.
540#[derive(Default)]
541pub struct AddCircuitInputLibFuncWrapped {}
542impl SignatureAndTypeGenericLibfunc for AddCircuitInputLibFuncWrapped {
543    const STR_ID: &'static str = "add_circuit_input";
544
545    fn specialize_signature(
546        &self,
547        context: &dyn SignatureSpecializationContext,
548        ty: ConcreteTypeId,
549    ) -> Result<LibfuncSignature, SpecializationError> {
550        let circuit_input_accumulator_ty = context
551            .get_concrete_type(CircuitInputAccumulator::id(), &[GenericArg::Type(ty.clone())])?;
552
553        let circuit_data_ty =
554            context.get_concrete_type(CircuitData::id(), &[GenericArg::Type(ty)])?;
555
556        let u96_guarantee_ty = context.get_concrete_type(U96Guarantee::id(), &[])?;
557
558        let val_ty = context.get_concrete_type(StructType::id(), &[
559            GenericArg::UserType(UserTypeId::from_string("Tuple")),
560            GenericArg::Type(u96_guarantee_ty.clone()),
561            GenericArg::Type(u96_guarantee_ty.clone()),
562            GenericArg::Type(u96_guarantee_ty.clone()),
563            GenericArg::Type(u96_guarantee_ty),
564        ])?;
565        Ok(LibfuncSignature {
566            param_signatures: vec![
567                ParamSignature::new(circuit_input_accumulator_ty.clone()),
568                ParamSignature::new(val_ty),
569            ],
570            branch_signatures: vec![
571                // All inputs were added.
572                BranchSignature {
573                    vars: vec![OutputVarInfo {
574                        ty: circuit_data_ty,
575                        ref_info: OutputVarReferenceInfo::SimpleDerefs,
576                    }],
577                    ap_change: SierraApChange::Known { new_vars_only: false },
578                },
579                // More inputs to add.
580                BranchSignature {
581                    vars: vec![OutputVarInfo {
582                        ty: circuit_input_accumulator_ty,
583                        ref_info: OutputVarReferenceInfo::SimpleDerefs,
584                    }],
585                    ap_change: SierraApChange::Known { new_vars_only: false },
586                },
587            ],
588            fallthrough: Some(0),
589        })
590    }
591}
592
593pub type AddCircuitInputLibFunc = WrapSignatureAndTypeGenericLibfunc<AddCircuitInputLibFuncWrapped>;
594
595/// A zero-input function that returns an handle to the offsets of a circuit.
596#[derive(Default)]
597pub struct GetCircuitDescriptorLibFuncWrapped {}
598impl SignatureAndTypeGenericLibfunc for GetCircuitDescriptorLibFuncWrapped {
599    const STR_ID: &'static str = "get_circuit_descriptor";
600
601    fn specialize_signature(
602        &self,
603        context: &dyn SignatureSpecializationContext,
604        ty: ConcreteTypeId,
605    ) -> Result<LibfuncSignature, SpecializationError> {
606        let circuit_descriptor_ty =
607            context.get_concrete_type(CircuitDescriptor::id(), &[GenericArg::Type(ty.clone())])?;
608
609        Ok(LibfuncSignature::new_non_branch(
610            vec![],
611            vec![OutputVarInfo {
612                ty: circuit_descriptor_ty,
613                ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
614            }],
615            SierraApChange::Known { new_vars_only: false },
616        ))
617    }
618}
619
620/// Helper for u96 type def.
621fn get_u96_type(
622    context: &dyn SignatureSpecializationContext,
623) -> Result<ConcreteTypeId, SpecializationError> {
624    bounded_int_ty(context, BigInt::zero(), BigInt::one().shl(96) - 1)
625}
626
627/// Helper for u384 type def.
628fn get_u384_type(
629    context: &dyn SignatureSpecializationContext,
630) -> Result<ConcreteTypeId, SpecializationError> {
631    let u96_ty = get_u96_type(context)?;
632    context.get_concrete_type(StructType::id(), &[
633        GenericArg::UserType(UserTypeId::from_string("core::circuit::u384")),
634        GenericArg::Type(u96_ty.clone()),
635        GenericArg::Type(u96_ty.clone()),
636        GenericArg::Type(u96_ty.clone()),
637        GenericArg::Type(u96_ty),
638    ])
639}
640
641pub type GetCircuitDescriptorLibFunc =
642    WrapSignatureAndTypeGenericLibfunc<GetCircuitDescriptorLibFuncWrapped>;
643
644/// A zero-input function that returns an handle to the offsets of a circuit.
645#[derive(Default)]
646pub struct EvalCircuitLibFuncWrapped {}
647impl SignatureAndTypeGenericLibfunc for EvalCircuitLibFuncWrapped {
648    const STR_ID: &'static str = "eval_circuit";
649
650    fn specialize_signature(
651        &self,
652        context: &dyn SignatureSpecializationContext,
653        ty: ConcreteTypeId,
654    ) -> Result<LibfuncSignature, SpecializationError> {
655        let add_mod_builtin_ty = context.get_concrete_type(AddModType::id(), &[])?;
656        let mul_mod_builtin_ty = context.get_concrete_type(MulModType::id(), &[])?;
657
658        let circuit_descriptor_ty =
659            context.get_concrete_type(CircuitDescriptor::id(), &[GenericArg::Type(ty.clone())])?;
660        let circuit_data_ty =
661            context.get_concrete_type(CircuitData::id(), &[GenericArg::Type(ty.clone())])?;
662
663        let zero = bounded_int_ty(context, BigInt::zero(), BigInt::zero())?;
664        let one = bounded_int_ty(context, BigInt::one(), BigInt::one())?;
665
666        Ok(LibfuncSignature {
667            param_signatures: [
668                add_mod_builtin_ty.clone(),
669                mul_mod_builtin_ty.clone(),
670                circuit_descriptor_ty,
671                circuit_data_ty,
672                context.get_concrete_type(CircuitModulus::id(), &[])?,
673                zero,
674                one,
675            ]
676            .into_iter()
677            .map(|ty| ParamSignature::new(ty.clone()))
678            .collect(),
679            branch_signatures: vec![
680                // Success.
681                BranchSignature {
682                    vars: vec![
683                        OutputVarInfo::new_builtin(add_mod_builtin_ty.clone(), 0),
684                        OutputVarInfo {
685                            ty: mul_mod_builtin_ty.clone(),
686                            ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
687                        },
688                        OutputVarInfo {
689                            ty: context.get_concrete_type(CircuitOutputs::id(), &[
690                                GenericArg::Type(ty.clone()),
691                            ])?,
692                            ref_info: OutputVarReferenceInfo::SimpleDerefs,
693                        },
694                    ],
695
696                    ap_change: SierraApChange::Known { new_vars_only: false },
697                },
698                // Failure (inverse of non-invertible).
699                BranchSignature {
700                    vars: vec![
701                        OutputVarInfo::new_builtin(add_mod_builtin_ty, 0),
702                        OutputVarInfo {
703                            ty: mul_mod_builtin_ty,
704                            ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
705                        },
706                        OutputVarInfo {
707                            ty: context.get_concrete_type(CircuitPartialOutputs::id(), &[
708                                GenericArg::Type(ty),
709                            ])?,
710                            ref_info: OutputVarReferenceInfo::SimpleDerefs,
711                        },
712                        OutputVarInfo {
713                            ty: context.get_concrete_type(CircuitFailureGuarantee::id(), &[])?,
714                            ref_info: OutputVarReferenceInfo::SimpleDerefs,
715                        },
716                    ],
717
718                    ap_change: SierraApChange::Known { new_vars_only: false },
719                },
720            ],
721            fallthrough: Some(0),
722        })
723    }
724}
725
726pub type EvalCircuitLibFunc = WrapSignatureAndTypeGenericLibfunc<EvalCircuitLibFuncWrapped>;
727
728/// Converts 'T' into a 'U96Guarantee'.
729/// 'T' must be a value that fits inside a u96, for example: u8, u96 or BoundedInt<0, 12>.
730#[derive(Default)]
731pub struct IntoU96GuaranteeLibFuncWrapped {}
732impl SignatureAndTypeGenericLibfunc for IntoU96GuaranteeLibFuncWrapped {
733    const STR_ID: &'static str = "into_u96_guarantee";
734
735    fn specialize_signature(
736        &self,
737        context: &dyn SignatureSpecializationContext,
738        ty: ConcreteTypeId,
739    ) -> Result<LibfuncSignature, SpecializationError> {
740        let range = Range::from_type(context, ty.clone())?;
741        require(!range.lower.is_negative() && range.upper <= BigInt::one().shl(96))
742            .ok_or(SpecializationError::UnsupportedGenericArg)?;
743
744        let guarantee_ty = context.get_concrete_type(U96Guarantee::id(), &[])?;
745        Ok(reinterpret_cast_signature(ty, guarantee_ty))
746    }
747}
748
749pub type IntoU96GuaranteeLibFunc =
750    WrapSignatureAndTypeGenericLibfunc<IntoU96GuaranteeLibFuncWrapped>;
751
752/// Libfunc for verifying and dropping a `U96Guarantee`.
753#[derive(Default)]
754pub struct U96GuaranteeVerifyLibFunc {}
755impl NoGenericArgsGenericLibfunc for U96GuaranteeVerifyLibFunc {
756    const STR_ID: &'static str = "u96_guarantee_verify";
757
758    fn specialize_signature(
759        &self,
760        context: &dyn SignatureSpecializationContext,
761    ) -> Result<LibfuncSignature, SpecializationError> {
762        let range_check96_type = context.get_concrete_type(RangeCheck96Type::id(), &[])?;
763        let guarantee_ty = context.get_concrete_type(U96Guarantee::id(), &[])?;
764        Ok(LibfuncSignature::new_non_branch_ex(
765            vec![
766                ParamSignature::new(range_check96_type.clone()).with_allow_add_const(),
767                ParamSignature::new(guarantee_ty),
768            ],
769            vec![OutputVarInfo::new_builtin(range_check96_type, 0)],
770            SierraApChange::Known { new_vars_only: true },
771        ))
772    }
773}
774
775/// Libfunc for getting an output of a circuit.
776#[derive(Default)]
777pub struct GetOutputLibFunc {}
778impl NamedLibfunc for GetOutputLibFunc {
779    const STR_ID: &'static str = "get_circuit_output";
780
781    type Concrete = ConcreteGetOutputLibFunc;
782
783    fn specialize_signature(
784        &self,
785        context: &dyn SignatureSpecializationContext,
786        args: &[GenericArg],
787    ) -> Result<LibfuncSignature, SpecializationError> {
788        let (circ_ty, output_ty) = args_as_two_types(args)?;
789        if !CIRCUIT_COMPONENTS.contains(&context.get_type_info(output_ty)?.long_id.generic_id) {
790            return Err(SpecializationError::UnsupportedGenericArg);
791        }
792
793        let outputs_ty =
794            context.get_concrete_type(CircuitOutputs::id(), &[GenericArg::Type(circ_ty)])?;
795
796        let u384_ty = get_u384_type(context)?;
797        let guarantee_ty = u384_less_than_guarantee_ty(context)?;
798        Ok(LibfuncSignature::new_non_branch(
799            vec![outputs_ty],
800            vec![
801                OutputVarInfo { ty: u384_ty, ref_info: OutputVarReferenceInfo::SimpleDerefs },
802                OutputVarInfo { ty: guarantee_ty, ref_info: OutputVarReferenceInfo::SimpleDerefs },
803            ],
804            SierraApChange::Known { new_vars_only: false },
805        ))
806    }
807
808    fn specialize(
809        &self,
810        context: &dyn SpecializationContext,
811        args: &[GenericArg],
812    ) -> Result<Self::Concrete, SpecializationError> {
813        let (circuit_ty, output_ty) = args_as_two_types(args)?;
814
815        // TODO(ilya): Fail if `circuit_ty` does not contain output_ty.
816        Ok(ConcreteGetOutputLibFunc {
817            signature: self.specialize_signature(context.upcast(), args)?,
818            circuit_ty,
819            output_ty,
820        })
821    }
822}
823
824/// Struct the data for a multi pop action.
825pub struct ConcreteGetOutputLibFunc {
826    pub signature: LibfuncSignature,
827    pub circuit_ty: ConcreteTypeId,
828    pub output_ty: ConcreteTypeId,
829}
830impl SignatureBasedConcreteLibfunc for ConcreteGetOutputLibFunc {
831    fn signature(&self) -> &LibfuncSignature {
832        &self.signature
833    }
834}
835
836/// Verifies the circuit evaluation has failed.
837#[derive(Default)]
838pub struct CircuitFailureGuaranteeVerifyLibFunc {}
839impl NoGenericArgsGenericLibfunc for CircuitFailureGuaranteeVerifyLibFunc {
840    const STR_ID: &'static str = "circuit_failure_guarantee_verify";
841
842    fn specialize_signature(
843        &self,
844        context: &dyn SignatureSpecializationContext,
845    ) -> Result<LibfuncSignature, SpecializationError> {
846        let range_check96_type = context.get_concrete_type(RangeCheck96Type::id(), &[])?;
847        let mul_mod_builtin_ty = context.get_concrete_type(MulModType::id(), &[])?;
848        let guarantee_ty = context.get_concrete_type(CircuitFailureGuarantee::id(), &[])?;
849
850        let zero = bounded_int_ty(context, BigInt::zero(), BigInt::zero())?;
851        let one = bounded_int_ty(context, BigInt::one(), BigInt::one())?;
852
853        Ok(LibfuncSignature::new_non_branch(
854            vec![range_check96_type.clone(), mul_mod_builtin_ty.clone(), guarantee_ty, zero, one],
855            vec![
856                OutputVarInfo::new_builtin(range_check96_type, 0),
857                OutputVarInfo::new_builtin(mul_mod_builtin_ty, 1),
858                OutputVarInfo {
859                    ty: u384_less_than_guarantee_ty(context)?,
860                    ref_info: OutputVarReferenceInfo::SimpleDerefs,
861                },
862            ],
863            SierraApChange::Known { new_vars_only: false },
864        ))
865    }
866}
867
868/// Verifies that numbers with u96 limbs are one larger than the other.
869#[derive(Default)]
870pub struct U96LimbsLessThanGuaranteeVerifyLibfunc {}
871impl NamedLibfunc for U96LimbsLessThanGuaranteeVerifyLibfunc {
872    const STR_ID: &'static str = "u96_limbs_less_than_guarantee_verify";
873
874    fn specialize_signature(
875        &self,
876        context: &dyn SignatureSpecializationContext,
877        args: &[GenericArg],
878    ) -> Result<LibfuncSignature, SpecializationError> {
879        let limb_count = args_as_single_value(args)?
880            .to_usize()
881            .ok_or(SpecializationError::UnsupportedGenericArg)?;
882        require(limb_count > 1).ok_or(SpecializationError::UnsupportedGenericArg)?;
883        let in_guarantee_ty = u96_limbs_less_than_guarantee_ty(context, limb_count)?;
884        let u96_lt_guarantee_ty = context.get_concrete_type(U96Guarantee::id(), &[])?;
885        let eq_guarantee_ty = u96_limbs_less_than_guarantee_ty(context, limb_count - 1)?;
886        Ok(LibfuncSignature {
887            param_signatures: vec![ParamSignature::new(in_guarantee_ty)],
888            branch_signatures: vec![
889                // Most significant limbs are equal - move to the next smaller guarantee.
890                BranchSignature {
891                    vars: vec![OutputVarInfo {
892                        ty: eq_guarantee_ty,
893                        ref_info: OutputVarReferenceInfo::PartialParam { param_idx: 0 },
894                    }],
895                    ap_change: SierraApChange::Known { new_vars_only: false },
896                },
897                // Most significant limbs are different - checking the diff is in u96 range.
898                BranchSignature {
899                    vars: vec![OutputVarInfo {
900                        ty: u96_lt_guarantee_ty,
901                        ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
902                    }],
903                    ap_change: SierraApChange::Known { new_vars_only: true },
904                },
905            ],
906            fallthrough: Some(0),
907        })
908    }
909
910    type Concrete = ConcreteU96LimbsLessThanGuaranteeVerifyLibfunc;
911
912    fn specialize(
913        &self,
914        context: &dyn SpecializationContext,
915        args: &[GenericArg],
916    ) -> Result<Self::Concrete, SpecializationError> {
917        let limb_count = args_as_single_value(args)?
918            .to_usize()
919            .ok_or(SpecializationError::UnsupportedGenericArg)?;
920        Ok(Self::Concrete {
921            signature: self.specialize_signature(context.upcast(), args)?,
922            limb_count,
923        })
924    }
925}
926pub struct ConcreteU96LimbsLessThanGuaranteeVerifyLibfunc {
927    signature: LibfuncSignature,
928    pub limb_count: usize,
929}
930impl SignatureBasedConcreteLibfunc for ConcreteU96LimbsLessThanGuaranteeVerifyLibfunc {
931    fn signature(&self) -> &LibfuncSignature {
932        &self.signature
933    }
934}
935
936/// Verifies that numbers with a single u96 limb are one larger than the other.
937#[derive(Default)]
938pub struct U96SingleLimbLessThanGuaranteeVerifyLibfunc {}
939impl NoGenericArgsGenericLibfunc for U96SingleLimbLessThanGuaranteeVerifyLibfunc {
940    const STR_ID: &'static str = "u96_single_limb_less_than_guarantee_verify";
941
942    fn specialize_signature(
943        &self,
944        context: &dyn SignatureSpecializationContext,
945    ) -> Result<LibfuncSignature, SpecializationError> {
946        let in_guarantee_ty = u96_limbs_less_than_guarantee_ty(context, 1)?;
947        let u96_lt_guarantee_ty = context.get_concrete_type(U96Guarantee::id(), &[])?;
948        Ok(LibfuncSignature::new_non_branch(
949            vec![in_guarantee_ty],
950            vec![OutputVarInfo {
951                ty: u96_lt_guarantee_ty,
952                ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
953            }],
954            SierraApChange::Known { new_vars_only: true },
955        ))
956    }
957}
958
959/// Type for add mod builtin.
960#[derive(Default)]
961pub struct AddModType {}
962impl NoGenericArgsGenericType for AddModType {
963    const ID: GenericTypeId = GenericTypeId::new_inline("AddMod");
964    const STORABLE: bool = true;
965    const DUPLICATABLE: bool = false;
966    const DROPPABLE: bool = false;
967    const ZERO_SIZED: bool = false;
968}
969
970/// Type for mul mod builtin.
971#[derive(Default)]
972pub struct MulModType {}
973impl NoGenericArgsGenericType for MulModType {
974    const ID: GenericTypeId = GenericTypeId::new_inline("MulMod");
975    const STORABLE: bool = true;
976    const DUPLICATABLE: bool = false;
977    const DROPPABLE: bool = false;
978    const ZERO_SIZED: bool = false;
979}
980
981/// Libfunc for checking whether the given `u384` (given as 4 limbs of `u96`) is zero.
982#[derive(Default)]
983pub struct TryIntoCircuitModulusLibFunc {}
984impl NoGenericArgsGenericLibfunc for TryIntoCircuitModulusLibFunc {
985    const STR_ID: &'static str = "try_into_circuit_modulus";
986
987    fn specialize_signature(
988        &self,
989        context: &dyn SignatureSpecializationContext,
990    ) -> Result<LibfuncSignature, SpecializationError> {
991        let u96_ty = get_u96_type(context)?;
992        let value_type = context.get_concrete_type(StructType::id(), &[
993            GenericArg::UserType(UserTypeId::from_string("Tuple")),
994            GenericArg::Type(u96_ty.clone()),
995            GenericArg::Type(u96_ty.clone()),
996            GenericArg::Type(u96_ty.clone()),
997            GenericArg::Type(u96_ty),
998        ])?;
999
1000        Ok(LibfuncSignature {
1001            param_signatures: vec![ParamSignature::new(value_type)],
1002            branch_signatures: vec![
1003                // Success (value >= 2).
1004                BranchSignature {
1005                    vars: vec![OutputVarInfo {
1006                        ty: context.get_concrete_type(CircuitModulus::id(), &[])?,
1007                        ref_info: OutputVarReferenceInfo::SameAsParam { param_idx: 0 },
1008                    }],
1009                    ap_change: SierraApChange::Known { new_vars_only: false },
1010                },
1011                // Failure (value is zero or one).
1012                BranchSignature {
1013                    vars: vec![],
1014                    ap_change: SierraApChange::Known { new_vars_only: false },
1015                },
1016            ],
1017            fallthrough: Some(0),
1018        })
1019    }
1020}
1021
1022/// Gets a concrete type, if it is a const type returns a vector of the values to be stored in
1023/// the const segment.
1024fn get_circuit_info(
1025    context: &dyn TypeSpecializationContext,
1026    outputs_tuple_ty: &ConcreteTypeId,
1027) -> Result<CircuitInfo, SpecializationError> {
1028    let struct_generic_args = extract_type_generic_args::<StructType>(context, outputs_tuple_ty)?;
1029    let mut generic_args = struct_generic_args.iter();
1030    if !matches!(
1031        generic_args.next(),
1032        Some(GenericArg::UserType(ut))
1033        if (*ut == UserTypeId::from_string("Tuple"))
1034    ) {
1035        return Err(SpecializationError::UnsupportedGenericArg);
1036    }
1037
1038    let circ_outputs = generic_args;
1039
1040    validate_args_are_circuit_components(context, circ_outputs.clone())?;
1041
1042    let ParsedInputs { reduced_inputs: mut values, mut mul_offsets } =
1043        parse_circuit_inputs(context, circ_outputs.clone())?;
1044    let n_inputs = values.len();
1045    require(n_inputs >= 1).ok_or(SpecializationError::UnsupportedGenericArg)?;
1046
1047    let mut add_offsets = vec![];
1048
1049    // We visit each gate in the circuit twice.
1050    // In the first visit of a gate, push all its inputs to the stack.
1051    // In the second visit of a gate, we assume that all the inputs were already visited (twice)
1052    // and we can allocate a value for the output and update `add_offsets` or `mul_offsets`.
1053    //
1054    // The stack contains pairs of (type, first_visit).
1055    let mut stack: Vec<(ConcreteTypeId, bool)> = circ_outputs
1056        .map(|generic_arg| (extract_matches!(generic_arg, GenericArg::Type).clone(), true))
1057        .collect();
1058
1059    while let Some((ty, first_visit)) = stack.pop() {
1060        let long_id = context.get_type_info(ty.clone())?.long_id;
1061        let generic_id = long_id.generic_id;
1062
1063        if values.contains_key(&ty) {
1064            // The value was already processed.
1065            continue;
1066        }
1067
1068        let gate_inputs = long_id
1069            .generic_args
1070            .iter()
1071            .map(|generic_arg| extract_matches!(generic_arg, GenericArg::Type));
1072
1073        if first_visit {
1074            stack.push((ty, false));
1075            stack.extend(gate_inputs.map(|ty| (ty.clone(), true)))
1076        } else {
1077            let output_offset = 1 + n_inputs + values.len();
1078            let mut input_offsets = gate_inputs.map(|ty| values[ty]);
1079
1080            if generic_id == AddModGate::ID {
1081                add_offsets.push(GateOffsets {
1082                    lhs: input_offsets.next().unwrap(),
1083                    rhs: input_offsets.next().unwrap(),
1084                    output: output_offset,
1085                });
1086            } else if generic_id == SubModGate::ID {
1087                // output = sub_lhs - sub_rhs => output + sub_rhs = sub_lhs.
1088                let sub_lhs = input_offsets.next().unwrap();
1089                let sub_rhs = input_offsets.next().unwrap();
1090                add_offsets.push(GateOffsets { lhs: output_offset, rhs: sub_rhs, output: sub_lhs });
1091            } else if generic_id == MulModGate::ID {
1092                mul_offsets.push(GateOffsets {
1093                    lhs: input_offsets.next().unwrap(),
1094                    rhs: input_offsets.next().unwrap(),
1095                    output: output_offset,
1096                });
1097            } else if generic_id == InverseGate::ID {
1098                // output = 1 / input => 1 = output * input.
1099                // Note that the gate will fail if the input is not invertible.
1100                // Evaluating this gate successfully implies that input is invertible.
1101                mul_offsets.push(GateOffsets {
1102                    lhs: output_offset,
1103                    rhs: input_offsets.next().unwrap(),
1104                    output: ONE_OFFSET,
1105                });
1106            } else {
1107                return Err(SpecializationError::UnsupportedGenericArg);
1108            };
1109
1110            // Make sure all the gate inputs were consumed.
1111            assert!(input_offsets.next().is_none());
1112            values.insert(ty.clone(), output_offset);
1113        }
1114    }
1115
1116    Ok(CircuitInfo { n_inputs, values, add_offsets, mul_offsets })
1117}
1118
1119/// Parses the circuit inputs and returns `ParsedInputs`.
1120fn parse_circuit_inputs<'a>(
1121    context: &dyn TypeSpecializationContext,
1122    circuit_outputs: impl Iterator<Item = &'a GenericArg>,
1123) -> Result<ParsedInputs, SpecializationError> {
1124    let mut stack: Vec<ConcreteTypeId> = circuit_outputs
1125        .map(|generic_arg| extract_matches!(generic_arg, GenericArg::Type).clone())
1126        .collect();
1127
1128    let mut inputs: UnorderedHashMap<usize, ConcreteTypeId> = Default::default();
1129
1130    let mut visited = UnorderedHashSet::<_>::default();
1131
1132    while let Some(ty) = stack.pop() {
1133        if !visited.insert(ty.clone()) {
1134            // Already visited.
1135            continue;
1136        }
1137
1138        let long_id = context.get_type_info(ty.clone())?.long_id;
1139        let generic_id = long_id.generic_id;
1140        if generic_id == CircuitInput::ID {
1141            let idx = args_as_single_value(&long_id.generic_args)?
1142                .to_usize()
1143                .ok_or(SpecializationError::UnsupportedGenericArg)?;
1144            assert!(inputs.insert(idx, ty).is_none());
1145        } else {
1146            // generic_id must be a gate. This was validated in `validate_output_tuple`.
1147            stack.extend(
1148                long_id
1149                    .generic_args
1150                    .iter()
1151                    .map(|generic_arg| extract_matches!(generic_arg, GenericArg::Type).clone()),
1152            );
1153        }
1154    }
1155
1156    let mut reduced_inputs: UnorderedHashMap<ConcreteTypeId, usize> = Default::default();
1157    let n_inputs = inputs.len();
1158
1159    // The reduced_inputs start at `1 + n_inputs` since we need to reserve slot 0 for the constant
1160    // value `1`.
1161    let reduced_input_start = 1 + n_inputs;
1162    let mut mul_offsets = vec![];
1163
1164    for (idx, (input_idx, ty)) in inputs.iter_sorted().enumerate() {
1165        // Validate that the input indices are `[0, 1, ..., n_inputs - 1]`.
1166        require(idx == *input_idx).ok_or(SpecializationError::UnsupportedGenericArg)?;
1167        assert!(reduced_inputs.insert(ty.clone(), reduced_input_start + idx).is_none());
1168        // Add the gate `1 * input = result` to reduce the input module the modulus.
1169        mul_offsets.push(GateOffsets {
1170            lhs: ONE_OFFSET,
1171            rhs: 1 + idx,
1172            output: reduced_input_start + idx,
1173        });
1174    }
1175
1176    Ok(ParsedInputs { reduced_inputs, mul_offsets })
1177}
1178
1179/// Describes the offset that define a gate in a circuit.
1180#[derive(Debug, Eq, PartialEq, Clone)]
1181pub struct GateOffsets {
1182    pub lhs: usize,
1183    pub rhs: usize,
1184    pub output: usize,
1185}
1186
1187/// Describes a circuit in the program.
1188#[derive(Clone, Debug, Eq, PartialEq)]
1189pub struct CircuitInfo {
1190    /// The number of circuit inputs.
1191    pub n_inputs: usize,
1192
1193    /// Maps a concrete type to its offset (measured in number of elements) in the values array.
1194    /// The values mapping does not include the constant input `1` which is stored at offset `0`.
1195    pub values: UnorderedHashMap<ConcreteTypeId, usize>,
1196    /// The offsets for the add gates. This includes AddModGate and SubModGate.
1197    pub add_offsets: Vec<GateOffsets>,
1198    /// The offsets for the mul gates. This includes MulModGate, InverseGate, and input reductions.
1199    pub mul_offsets: Vec<GateOffsets>,
1200}
1201
1202impl CircuitInfo {
1203    /// Returns the number of 96-bit range checks used by the circuit.
1204    ///
1205    /// We use:
1206    /// * 1 slot for the const 1,
1207    /// * `n_inputs` slots for the original unreduced inputs,
1208    /// * `self.values.len()` for all the intermediate values and outputs (including the reduced
1209    ///   inputs).
1210    pub fn rc96_usage(&self) -> usize {
1211        (1 + self.n_inputs + self.values.len()) * VALUE_SIZE
1212    }
1213}
1214
1215struct ParsedInputs {
1216    /// Maps a concrete input type to its offset in the values array.
1217    reduced_inputs: UnorderedHashMap<ConcreteTypeId, usize>,
1218    /// The offsets for the mul gates that are used to reduce the inputs.
1219    mul_offsets: Vec<GateOffsets>,
1220}
1221
1222/// Returns the guarantee type for u384 values comparison.
1223fn u384_less_than_guarantee_ty(
1224    context: &dyn SignatureSpecializationContext,
1225) -> Result<ConcreteTypeId, SpecializationError> {
1226    u96_limbs_less_than_guarantee_ty(context, 4)
1227}
1228
1229/// Returns the guarantee type for a number with u96 limbs values comparison.
1230fn u96_limbs_less_than_guarantee_ty(
1231    context: &dyn SignatureSpecializationContext,
1232    limb_count: usize,
1233) -> Result<ConcreteTypeId, SpecializationError> {
1234    context
1235        .get_concrete_type(U96LimbsLessThanGuarantee::id(), &[GenericArg::Value(limb_count.into())])
1236}
1237
1238/// Returns the type info of the circuit component.
1239fn circuit_component_type_info(generic_id: GenericTypeId, args: &[GenericArg]) -> TypeInfo {
1240    TypeInfo {
1241        long_id: ConcreteTypeLongId { generic_id, generic_args: args.to_vec() },
1242        duplicatable: false,
1243        droppable: false,
1244        storable: false,
1245        zero_sized: true,
1246    }
1247}
cairo_lang_sierra/extensions/modules/circuit.rs

cairo_lang_sierra/extensions/modules/
circuit.rs
