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(
559            StructType::id(),
560            &[
561                GenericArg::UserType(UserTypeId::from_string("Tuple")),
562                GenericArg::Type(u96_guarantee_ty.clone()),
563                GenericArg::Type(u96_guarantee_ty.clone()),
564                GenericArg::Type(u96_guarantee_ty.clone()),
565                GenericArg::Type(u96_guarantee_ty),
566            ],
567        )?;
568        Ok(LibfuncSignature {
569            param_signatures: vec![
570                ParamSignature::new(circuit_input_accumulator_ty.clone()),
571                ParamSignature::new(val_ty),
572            ],
573            branch_signatures: vec![
574                // All inputs were added.
575                BranchSignature {
576                    vars: vec![OutputVarInfo {
577                        ty: circuit_data_ty,
578                        ref_info: OutputVarReferenceInfo::SimpleDerefs,
579                    }],
580                    ap_change: SierraApChange::Known { new_vars_only: false },
581                },
582                // More inputs to add.
583                BranchSignature {
584                    vars: vec![OutputVarInfo {
585                        ty: circuit_input_accumulator_ty,
586                        ref_info: OutputVarReferenceInfo::SimpleDerefs,
587                    }],
588                    ap_change: SierraApChange::Known { new_vars_only: false },
589                },
590            ],
591            fallthrough: Some(0),
592        })
593    }
594}
595
596pub type AddCircuitInputLibFunc = WrapSignatureAndTypeGenericLibfunc<AddCircuitInputLibFuncWrapped>;
597
598/// A zero-input function that returns an handle to the offsets of a circuit.
599#[derive(Default)]
600pub struct GetCircuitDescriptorLibFuncWrapped {}
601impl SignatureAndTypeGenericLibfunc for GetCircuitDescriptorLibFuncWrapped {
602    const STR_ID: &'static str = "get_circuit_descriptor";
603
604    fn specialize_signature(
605        &self,
606        context: &dyn SignatureSpecializationContext,
607        ty: ConcreteTypeId,
608    ) -> Result<LibfuncSignature, SpecializationError> {
609        let circuit_descriptor_ty =
610            context.get_concrete_type(CircuitDescriptor::id(), &[GenericArg::Type(ty.clone())])?;
611
612        Ok(LibfuncSignature::new_non_branch(
613            vec![],
614            vec![OutputVarInfo {
615                ty: circuit_descriptor_ty,
616                ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
617            }],
618            SierraApChange::Known { new_vars_only: false },
619        ))
620    }
621}
622
623/// Helper for u96 type def.
624fn get_u96_type(
625    context: &dyn SignatureSpecializationContext,
626) -> Result<ConcreteTypeId, SpecializationError> {
627    bounded_int_ty(context, BigInt::zero(), BigInt::one().shl(96) - 1)
628}
629
630/// Helper for u384 type def.
631fn get_u384_type(
632    context: &dyn SignatureSpecializationContext,
633) -> Result<ConcreteTypeId, SpecializationError> {
634    let u96_ty = get_u96_type(context)?;
635    context.get_concrete_type(
636        StructType::id(),
637        &[
638            GenericArg::UserType(UserTypeId::from_string("core::circuit::u384")),
639            GenericArg::Type(u96_ty.clone()),
640            GenericArg::Type(u96_ty.clone()),
641            GenericArg::Type(u96_ty.clone()),
642            GenericArg::Type(u96_ty),
643        ],
644    )
645}
646
647pub type GetCircuitDescriptorLibFunc =
648    WrapSignatureAndTypeGenericLibfunc<GetCircuitDescriptorLibFuncWrapped>;
649
650/// A zero-input function that returns an handle to the offsets of a circuit.
651#[derive(Default)]
652pub struct EvalCircuitLibFuncWrapped {}
653impl SignatureAndTypeGenericLibfunc for EvalCircuitLibFuncWrapped {
654    const STR_ID: &'static str = "eval_circuit";
655
656    fn specialize_signature(
657        &self,
658        context: &dyn SignatureSpecializationContext,
659        ty: ConcreteTypeId,
660    ) -> Result<LibfuncSignature, SpecializationError> {
661        let add_mod_builtin_ty = context.get_concrete_type(AddModType::id(), &[])?;
662        let mul_mod_builtin_ty = context.get_concrete_type(MulModType::id(), &[])?;
663
664        let circuit_descriptor_ty =
665            context.get_concrete_type(CircuitDescriptor::id(), &[GenericArg::Type(ty.clone())])?;
666        let circuit_data_ty =
667            context.get_concrete_type(CircuitData::id(), &[GenericArg::Type(ty.clone())])?;
668
669        let zero = bounded_int_ty(context, BigInt::zero(), BigInt::zero())?;
670        let one = bounded_int_ty(context, BigInt::one(), BigInt::one())?;
671
672        Ok(LibfuncSignature {
673            param_signatures: [
674                add_mod_builtin_ty.clone(),
675                mul_mod_builtin_ty.clone(),
676                circuit_descriptor_ty,
677                circuit_data_ty,
678                context.get_concrete_type(CircuitModulus::id(), &[])?,
679                zero,
680                one,
681            ]
682            .into_iter()
683            .map(|ty| ParamSignature::new(ty.clone()))
684            .collect(),
685            branch_signatures: vec![
686                // Success.
687                BranchSignature {
688                    vars: vec![
689                        OutputVarInfo::new_builtin(add_mod_builtin_ty.clone(), 0),
690                        OutputVarInfo {
691                            ty: mul_mod_builtin_ty.clone(),
692                            ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
693                        },
694                        OutputVarInfo {
695                            ty: context.get_concrete_type(
696                                CircuitOutputs::id(),
697                                &[GenericArg::Type(ty.clone())],
698                            )?,
699                            ref_info: OutputVarReferenceInfo::SimpleDerefs,
700                        },
701                    ],
702
703                    ap_change: SierraApChange::Known { new_vars_only: false },
704                },
705                // Failure (inverse of non-invertible).
706                BranchSignature {
707                    vars: vec![
708                        OutputVarInfo::new_builtin(add_mod_builtin_ty, 0),
709                        OutputVarInfo {
710                            ty: mul_mod_builtin_ty,
711                            ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
712                        },
713                        OutputVarInfo {
714                            ty: context.get_concrete_type(
715                                CircuitPartialOutputs::id(),
716                                &[GenericArg::Type(ty)],
717                            )?,
718                            ref_info: OutputVarReferenceInfo::SimpleDerefs,
719                        },
720                        OutputVarInfo {
721                            ty: context.get_concrete_type(CircuitFailureGuarantee::id(), &[])?,
722                            ref_info: OutputVarReferenceInfo::SimpleDerefs,
723                        },
724                    ],
725
726                    ap_change: SierraApChange::Known { new_vars_only: false },
727                },
728            ],
729            fallthrough: Some(0),
730        })
731    }
732}
733
734pub type EvalCircuitLibFunc = WrapSignatureAndTypeGenericLibfunc<EvalCircuitLibFuncWrapped>;
735
736/// Converts 'T' into a 'U96Guarantee'.
737/// 'T' must be a value that fits inside a u96, for example: u8, u96 or BoundedInt<0, 12>.
738#[derive(Default)]
739pub struct IntoU96GuaranteeLibFuncWrapped {}
740impl SignatureAndTypeGenericLibfunc for IntoU96GuaranteeLibFuncWrapped {
741    const STR_ID: &'static str = "into_u96_guarantee";
742
743    fn specialize_signature(
744        &self,
745        context: &dyn SignatureSpecializationContext,
746        ty: ConcreteTypeId,
747    ) -> Result<LibfuncSignature, SpecializationError> {
748        let range = Range::from_type(context, ty.clone())?;
749        require(!range.lower.is_negative() && range.upper <= BigInt::one().shl(96))
750            .ok_or(SpecializationError::UnsupportedGenericArg)?;
751
752        let guarantee_ty = context.get_concrete_type(U96Guarantee::id(), &[])?;
753        Ok(reinterpret_cast_signature(ty, guarantee_ty))
754    }
755}
756
757pub type IntoU96GuaranteeLibFunc =
758    WrapSignatureAndTypeGenericLibfunc<IntoU96GuaranteeLibFuncWrapped>;
759
760/// Libfunc for verifying and dropping a `U96Guarantee`.
761#[derive(Default)]
762pub struct U96GuaranteeVerifyLibFunc {}
763impl NoGenericArgsGenericLibfunc for U96GuaranteeVerifyLibFunc {
764    const STR_ID: &'static str = "u96_guarantee_verify";
765
766    fn specialize_signature(
767        &self,
768        context: &dyn SignatureSpecializationContext,
769    ) -> Result<LibfuncSignature, SpecializationError> {
770        let range_check96_type = context.get_concrete_type(RangeCheck96Type::id(), &[])?;
771        let guarantee_ty = context.get_concrete_type(U96Guarantee::id(), &[])?;
772        Ok(LibfuncSignature::new_non_branch_ex(
773            vec![
774                ParamSignature::new(range_check96_type.clone()).with_allow_add_const(),
775                ParamSignature::new(guarantee_ty),
776            ],
777            vec![OutputVarInfo::new_builtin(range_check96_type, 0)],
778            SierraApChange::Known { new_vars_only: true },
779        ))
780    }
781}
782
783/// Libfunc for getting an output of a circuit.
784#[derive(Default)]
785pub struct GetOutputLibFunc {}
786impl NamedLibfunc for GetOutputLibFunc {
787    const STR_ID: &'static str = "get_circuit_output";
788
789    type Concrete = ConcreteGetOutputLibFunc;
790
791    fn specialize_signature(
792        &self,
793        context: &dyn SignatureSpecializationContext,
794        args: &[GenericArg],
795    ) -> Result<LibfuncSignature, SpecializationError> {
796        let (circ_ty, output_ty) = args_as_two_types(args)?;
797        if !CIRCUIT_COMPONENTS.contains(&context.get_type_info(output_ty)?.long_id.generic_id) {
798            return Err(SpecializationError::UnsupportedGenericArg);
799        }
800
801        let outputs_ty =
802            context.get_concrete_type(CircuitOutputs::id(), &[GenericArg::Type(circ_ty)])?;
803
804        let u384_ty = get_u384_type(context)?;
805        let guarantee_ty = u384_less_than_guarantee_ty(context)?;
806        Ok(LibfuncSignature::new_non_branch(
807            vec![outputs_ty],
808            vec![
809                OutputVarInfo { ty: u384_ty, ref_info: OutputVarReferenceInfo::SimpleDerefs },
810                OutputVarInfo { ty: guarantee_ty, ref_info: OutputVarReferenceInfo::SimpleDerefs },
811            ],
812            SierraApChange::Known { new_vars_only: false },
813        ))
814    }
815
816    fn specialize(
817        &self,
818        context: &dyn SpecializationContext,
819        args: &[GenericArg],
820    ) -> Result<Self::Concrete, SpecializationError> {
821        let (circuit_ty, output_ty) = args_as_two_types(args)?;
822
823        // TODO(ilya): Fail if `circuit_ty` does not contain output_ty.
824        Ok(ConcreteGetOutputLibFunc {
825            signature: self.specialize_signature(context.upcast(), args)?,
826            circuit_ty,
827            output_ty,
828        })
829    }
830}
831
832/// Struct the data for a multi pop action.
833pub struct ConcreteGetOutputLibFunc {
834    pub signature: LibfuncSignature,
835    pub circuit_ty: ConcreteTypeId,
836    pub output_ty: ConcreteTypeId,
837}
838impl SignatureBasedConcreteLibfunc for ConcreteGetOutputLibFunc {
839    fn signature(&self) -> &LibfuncSignature {
840        &self.signature
841    }
842}
843
844/// Verifies the circuit evaluation has failed.
845#[derive(Default)]
846pub struct CircuitFailureGuaranteeVerifyLibFunc {}
847impl NoGenericArgsGenericLibfunc for CircuitFailureGuaranteeVerifyLibFunc {
848    const STR_ID: &'static str = "circuit_failure_guarantee_verify";
849
850    fn specialize_signature(
851        &self,
852        context: &dyn SignatureSpecializationContext,
853    ) -> Result<LibfuncSignature, SpecializationError> {
854        let range_check96_type = context.get_concrete_type(RangeCheck96Type::id(), &[])?;
855        let mul_mod_builtin_ty = context.get_concrete_type(MulModType::id(), &[])?;
856        let guarantee_ty = context.get_concrete_type(CircuitFailureGuarantee::id(), &[])?;
857
858        let zero = bounded_int_ty(context, BigInt::zero(), BigInt::zero())?;
859        let one = bounded_int_ty(context, BigInt::one(), BigInt::one())?;
860
861        Ok(LibfuncSignature::new_non_branch(
862            vec![range_check96_type.clone(), mul_mod_builtin_ty.clone(), guarantee_ty, zero, one],
863            vec![
864                OutputVarInfo::new_builtin(range_check96_type, 0),
865                OutputVarInfo::new_builtin(mul_mod_builtin_ty, 1),
866                OutputVarInfo {
867                    ty: u384_less_than_guarantee_ty(context)?,
868                    ref_info: OutputVarReferenceInfo::SimpleDerefs,
869                },
870            ],
871            SierraApChange::Known { new_vars_only: false },
872        ))
873    }
874}
875
876/// Verifies that numbers with u96 limbs are one larger than the other.
877#[derive(Default)]
878pub struct U96LimbsLessThanGuaranteeVerifyLibfunc {}
879impl NamedLibfunc for U96LimbsLessThanGuaranteeVerifyLibfunc {
880    const STR_ID: &'static str = "u96_limbs_less_than_guarantee_verify";
881
882    fn specialize_signature(
883        &self,
884        context: &dyn SignatureSpecializationContext,
885        args: &[GenericArg],
886    ) -> Result<LibfuncSignature, SpecializationError> {
887        let limb_count = args_as_single_value(args)?
888            .to_usize()
889            .ok_or(SpecializationError::UnsupportedGenericArg)?;
890        require(limb_count > 1).ok_or(SpecializationError::UnsupportedGenericArg)?;
891        let in_guarantee_ty = u96_limbs_less_than_guarantee_ty(context, limb_count)?;
892        let u96_lt_guarantee_ty = context.get_concrete_type(U96Guarantee::id(), &[])?;
893        let eq_guarantee_ty = u96_limbs_less_than_guarantee_ty(context, limb_count - 1)?;
894        Ok(LibfuncSignature {
895            param_signatures: vec![ParamSignature::new(in_guarantee_ty)],
896            branch_signatures: vec![
897                // Most significant limbs are equal - move to the next smaller guarantee.
898                BranchSignature {
899                    vars: vec![OutputVarInfo {
900                        ty: eq_guarantee_ty,
901                        ref_info: OutputVarReferenceInfo::PartialParam { param_idx: 0 },
902                    }],
903                    ap_change: SierraApChange::Known { new_vars_only: false },
904                },
905                // Most significant limbs are different - checking the diff is in u96 range.
906                BranchSignature {
907                    vars: vec![OutputVarInfo {
908                        ty: u96_lt_guarantee_ty,
909                        ref_info: OutputVarReferenceInfo::NewTempVar { idx: 0 },
910                    }],
911                    ap_change: SierraApChange::Known { new_vars_only: true },
912                },
913            ],
914            fallthrough: Some(0),
915        })
916    }
917
918    type Concrete = ConcreteU96LimbsLessThanGuaranteeVerifyLibfunc;
919
920    fn specialize(
921        &self,
922        context: &dyn SpecializationContext,
923        args: &[GenericArg],
924    ) -> Result<Self::Concrete, SpecializationError> {
925        let limb_count = args_as_single_value(args)?
926            .to_usize()
927            .ok_or(SpecializationError::UnsupportedGenericArg)?;
928        Ok(Self::Concrete {
929            signature: self.specialize_signature(context.upcast(), args)?,
930            limb_count,
931        })
932    }
933}
934pub struct ConcreteU96LimbsLessThanGuaranteeVerifyLibfunc {
935    signature: LibfuncSignature,
936    pub limb_count: usize,
937}
938impl SignatureBasedConcreteLibfunc for ConcreteU96LimbsLessThanGuaranteeVerifyLibfunc {
939    fn signature(&self) -> &LibfuncSignature {
940        &self.signature
941    }
942}
943
944/// Verifies that numbers with a single u96 limb are one larger than the other.
945#[derive(Default)]
946pub struct U96SingleLimbLessThanGuaranteeVerifyLibfunc {}
947impl NoGenericArgsGenericLibfunc for U96SingleLimbLessThanGuaranteeVerifyLibfunc {
948    const STR_ID: &'static str = "u96_single_limb_less_than_guarantee_verify";
949
950    fn specialize_signature(
951        &self,
952        context: &dyn SignatureSpecializationContext,
953    ) -> Result<LibfuncSignature, SpecializationError> {
954        let in_guarantee_ty = u96_limbs_less_than_guarantee_ty(context, 1)?;
955        let u96_lt_guarantee_ty = context.get_concrete_type(U96Guarantee::id(), &[])?;
956        Ok(LibfuncSignature::new_non_branch(
957            vec![in_guarantee_ty],
958            vec![OutputVarInfo {
959                ty: u96_lt_guarantee_ty,
960                ref_info: OutputVarReferenceInfo::Deferred(DeferredOutputKind::Generic),
961            }],
962            SierraApChange::Known { new_vars_only: true },
963        ))
964    }
965}
966
967/// Type for add mod builtin.
968#[derive(Default)]
969pub struct AddModType {}
970impl NoGenericArgsGenericType for AddModType {
971    const ID: GenericTypeId = GenericTypeId::new_inline("AddMod");
972    const STORABLE: bool = true;
973    const DUPLICATABLE: bool = false;
974    const DROPPABLE: bool = false;
975    const ZERO_SIZED: bool = false;
976}
977
978/// Type for mul mod builtin.
979#[derive(Default)]
980pub struct MulModType {}
981impl NoGenericArgsGenericType for MulModType {
982    const ID: GenericTypeId = GenericTypeId::new_inline("MulMod");
983    const STORABLE: bool = true;
984    const DUPLICATABLE: bool = false;
985    const DROPPABLE: bool = false;
986    const ZERO_SIZED: bool = false;
987}
988
989/// Libfunc for checking whether the given `u384` (given as 4 limbs of `u96`) is zero.
990#[derive(Default)]
991pub struct TryIntoCircuitModulusLibFunc {}
992impl NoGenericArgsGenericLibfunc for TryIntoCircuitModulusLibFunc {
993    const STR_ID: &'static str = "try_into_circuit_modulus";
994
995    fn specialize_signature(
996        &self,
997        context: &dyn SignatureSpecializationContext,
998    ) -> Result<LibfuncSignature, SpecializationError> {
999        let u96_ty = get_u96_type(context)?;
1000        let value_type = context.get_concrete_type(
1001            StructType::id(),
1002            &[
1003                GenericArg::UserType(UserTypeId::from_string("Tuple")),
1004                GenericArg::Type(u96_ty.clone()),
1005                GenericArg::Type(u96_ty.clone()),
1006                GenericArg::Type(u96_ty.clone()),
1007                GenericArg::Type(u96_ty),
1008            ],
1009        )?;
1010
1011        Ok(LibfuncSignature {
1012            param_signatures: vec![ParamSignature::new(value_type)],
1013            branch_signatures: vec![
1014                // Success (value >= 2).
1015                BranchSignature {
1016                    vars: vec![OutputVarInfo {
1017                        ty: context.get_concrete_type(CircuitModulus::id(), &[])?,
1018                        ref_info: OutputVarReferenceInfo::SameAsParam { param_idx: 0 },
1019                    }],
1020                    ap_change: SierraApChange::Known { new_vars_only: false },
1021                },
1022                // Failure (value is zero or one).
1023                BranchSignature {
1024                    vars: vec![],
1025                    ap_change: SierraApChange::Known { new_vars_only: false },
1026                },
1027            ],
1028            fallthrough: Some(0),
1029        })
1030    }
1031}
1032
1033/// Gets a concrete type, if it is a const type returns a vector of the values to be stored in
1034/// the const segment.
1035fn get_circuit_info(
1036    context: &dyn TypeSpecializationContext,
1037    outputs_tuple_ty: &ConcreteTypeId,
1038) -> Result<CircuitInfo, SpecializationError> {
1039    let struct_generic_args = extract_type_generic_args::<StructType>(context, outputs_tuple_ty)?;
1040    let mut generic_args = struct_generic_args.iter();
1041    if !matches!(
1042        generic_args.next(),
1043        Some(GenericArg::UserType(ut))
1044        if (*ut == UserTypeId::from_string("Tuple"))
1045    ) {
1046        return Err(SpecializationError::UnsupportedGenericArg);
1047    }
1048
1049    let circ_outputs = generic_args;
1050
1051    validate_args_are_circuit_components(context, circ_outputs.clone())?;
1052
1053    let ParsedInputs { reduced_inputs: mut values, mut mul_offsets } =
1054        parse_circuit_inputs(context, circ_outputs.clone())?;
1055    let n_inputs = values.len();
1056    require(n_inputs >= 1).ok_or(SpecializationError::UnsupportedGenericArg)?;
1057
1058    let mut add_offsets = vec![];
1059
1060    // We visit each gate in the circuit twice.
1061    // In the first visit of a gate, push all its inputs to the stack.
1062    // In the second visit of a gate, we assume that all the inputs were already visited (twice)
1063    // and we can allocate a value for the output and update `add_offsets` or `mul_offsets`.
1064    //
1065    // The stack contains pairs of (type, first_visit).
1066    let mut stack: Vec<(ConcreteTypeId, bool)> = circ_outputs
1067        .map(|generic_arg| (extract_matches!(generic_arg, GenericArg::Type).clone(), true))
1068        .collect();
1069
1070    while let Some((ty, first_visit)) = stack.pop() {
1071        let long_id = context.get_type_info(ty.clone())?.long_id;
1072        let generic_id = long_id.generic_id;
1073
1074        if values.contains_key(&ty) {
1075            // The value was already processed.
1076            continue;
1077        }
1078
1079        let gate_inputs = long_id
1080            .generic_args
1081            .iter()
1082            .map(|generic_arg| extract_matches!(generic_arg, GenericArg::Type));
1083
1084        if first_visit {
1085            stack.push((ty, false));
1086            stack.extend(gate_inputs.map(|ty| (ty.clone(), true)))
1087        } else {
1088            let output_offset = 1 + n_inputs + values.len();
1089            let mut input_offsets = gate_inputs.map(|ty| values[ty]);
1090
1091            if generic_id == AddModGate::ID {
1092                add_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 == SubModGate::ID {
1098                // output = sub_lhs - sub_rhs => output + sub_rhs = sub_lhs.
1099                let sub_lhs = input_offsets.next().unwrap();
1100                let sub_rhs = input_offsets.next().unwrap();
1101                add_offsets.push(GateOffsets { lhs: output_offset, rhs: sub_rhs, output: sub_lhs });
1102            } else if generic_id == MulModGate::ID {
1103                mul_offsets.push(GateOffsets {
1104                    lhs: input_offsets.next().unwrap(),
1105                    rhs: input_offsets.next().unwrap(),
1106                    output: output_offset,
1107                });
1108            } else if generic_id == InverseGate::ID {
1109                // output = 1 / input => 1 = output * input.
1110                // Note that the gate will fail if the input is not invertible.
1111                // Evaluating this gate successfully implies that input is invertible.
1112                mul_offsets.push(GateOffsets {
1113                    lhs: output_offset,
1114                    rhs: input_offsets.next().unwrap(),
1115                    output: ONE_OFFSET,
1116                });
1117            } else {
1118                return Err(SpecializationError::UnsupportedGenericArg);
1119            };
1120
1121            // Make sure all the gate inputs were consumed.
1122            assert!(input_offsets.next().is_none());
1123            values.insert(ty.clone(), output_offset);
1124        }
1125    }
1126
1127    Ok(CircuitInfo { n_inputs, values, add_offsets, mul_offsets })
1128}
1129
1130/// Parses the circuit inputs and returns `ParsedInputs`.
1131fn parse_circuit_inputs<'a>(
1132    context: &dyn TypeSpecializationContext,
1133    circuit_outputs: impl Iterator<Item = &'a GenericArg>,
1134) -> Result<ParsedInputs, SpecializationError> {
1135    let mut stack: Vec<ConcreteTypeId> = circuit_outputs
1136        .map(|generic_arg| extract_matches!(generic_arg, GenericArg::Type).clone())
1137        .collect();
1138
1139    let mut inputs: UnorderedHashMap<usize, ConcreteTypeId> = Default::default();
1140
1141    let mut visited = UnorderedHashSet::<_>::default();
1142
1143    while let Some(ty) = stack.pop() {
1144        if !visited.insert(ty.clone()) {
1145            // Already visited.
1146            continue;
1147        }
1148
1149        let long_id = context.get_type_info(ty.clone())?.long_id;
1150        let generic_id = long_id.generic_id;
1151        if generic_id == CircuitInput::ID {
1152            let idx = args_as_single_value(&long_id.generic_args)?
1153                .to_usize()
1154                .ok_or(SpecializationError::UnsupportedGenericArg)?;
1155            assert!(inputs.insert(idx, ty).is_none());
1156        } else {
1157            // generic_id must be a gate. This was validated in `validate_output_tuple`.
1158            stack.extend(
1159                long_id
1160                    .generic_args
1161                    .iter()
1162                    .map(|generic_arg| extract_matches!(generic_arg, GenericArg::Type).clone()),
1163            );
1164        }
1165    }
1166
1167    let mut reduced_inputs: UnorderedHashMap<ConcreteTypeId, usize> = Default::default();
1168    let n_inputs = inputs.len();
1169
1170    // The reduced_inputs start at `1 + n_inputs` since we need to reserve slot 0 for the constant
1171    // value `1`.
1172    let reduced_input_start = 1 + n_inputs;
1173    let mut mul_offsets = vec![];
1174
1175    for (idx, (input_idx, ty)) in inputs.iter_sorted().enumerate() {
1176        // Validate that the input indices are `[0, 1, ..., n_inputs - 1]`.
1177        require(idx == *input_idx).ok_or(SpecializationError::UnsupportedGenericArg)?;
1178        assert!(reduced_inputs.insert(ty.clone(), reduced_input_start + idx).is_none());
1179        // Add the gate `1 * input = result` to reduce the input module the modulus.
1180        mul_offsets.push(GateOffsets {
1181            lhs: ONE_OFFSET,
1182            rhs: 1 + idx,
1183            output: reduced_input_start + idx,
1184        });
1185    }
1186
1187    Ok(ParsedInputs { reduced_inputs, mul_offsets })
1188}
1189
1190/// Describes the offset that define a gate in a circuit.
1191#[derive(Debug, Eq, PartialEq, Clone)]
1192pub struct GateOffsets {
1193    pub lhs: usize,
1194    pub rhs: usize,
1195    pub output: usize,
1196}
1197
1198/// Describes a circuit in the program.
1199#[derive(Clone, Debug, Eq, PartialEq)]
1200pub struct CircuitInfo {
1201    /// The number of circuit inputs.
1202    pub n_inputs: usize,
1203
1204    /// Maps a concrete type to its offset (measured in number of elements) in the values array.
1205    /// The values mapping does not include the constant input `1` which is stored at offset `0`.
1206    pub values: UnorderedHashMap<ConcreteTypeId, usize>,
1207    /// The offsets for the add gates. This includes AddModGate and SubModGate.
1208    pub add_offsets: Vec<GateOffsets>,
1209    /// The offsets for the mul gates. This includes MulModGate, InverseGate, and input reductions.
1210    pub mul_offsets: Vec<GateOffsets>,
1211}
1212
1213impl CircuitInfo {
1214    /// Returns the number of 96-bit range checks used by the circuit.
1215    ///
1216    /// We use:
1217    /// * 1 slot for the const 1,
1218    /// * `n_inputs` slots for the original unreduced inputs,
1219    /// * `self.values.len()` for all the intermediate values and outputs (including the reduced
1220    ///   inputs).
1221    pub fn rc96_usage(&self) -> usize {
1222        (1 + self.n_inputs + self.values.len()) * VALUE_SIZE
1223    }
1224}
1225
1226struct ParsedInputs {
1227    /// Maps a concrete input type to its offset in the values array.
1228    reduced_inputs: UnorderedHashMap<ConcreteTypeId, usize>,
1229    /// The offsets for the mul gates that are used to reduce the inputs.
1230    mul_offsets: Vec<GateOffsets>,
1231}
1232
1233/// Returns the guarantee type for u384 values comparison.
1234fn u384_less_than_guarantee_ty(
1235    context: &dyn SignatureSpecializationContext,
1236) -> Result<ConcreteTypeId, SpecializationError> {
1237    u96_limbs_less_than_guarantee_ty(context, 4)
1238}
1239
1240/// Returns the guarantee type for a number with u96 limbs values comparison.
1241fn u96_limbs_less_than_guarantee_ty(
1242    context: &dyn SignatureSpecializationContext,
1243    limb_count: usize,
1244) -> Result<ConcreteTypeId, SpecializationError> {
1245    context
1246        .get_concrete_type(U96LimbsLessThanGuarantee::id(), &[GenericArg::Value(limb_count.into())])
1247}
1248
1249/// Returns the type info of the circuit component.
1250fn circuit_component_type_info(generic_id: GenericTypeId, args: &[GenericArg]) -> TypeInfo {
1251    TypeInfo {
1252        long_id: ConcreteTypeLongId { generic_id, generic_args: args.to_vec() },
1253        duplicatable: false,
1254        droppable: false,
1255        storable: false,
1256        zero_sized: true,
1257    }
1258}
cairo_lang_sierra/extensions/modules/circuit.rs

cairo_lang_sierra/extensions/modules/
circuit.rs
