1use super::NonNativeFieldConfig;
 2
 3/// Obtain the parameters from a `ConstraintSystem`'s cache or generate a new one
 4#[must_use]
 5pub const fn get_params(
 6    target_field_size: usize,
 7    base_field_size: usize,
 8    optimization_type: OptimizationType,
 9) -> NonNativeFieldConfig {
10    let (num_of_limbs, limb_size) =
11        find_parameters(base_field_size, target_field_size, optimization_type);
12    NonNativeFieldConfig {
13        num_limbs: num_of_limbs,
14        bits_per_limb: limb_size,
15    }
16}
17
18#[derive(Clone, Copy, Debug, PartialEq, Eq)]
19/// The type of optimization target for the parameters searching
20pub enum OptimizationType {
21    /// Optimized for constraints
22    Constraints,
23    /// Optimized for weight
24    Weight,
25}
26
27/// A function to search for parameters for nonnative field gadgets
28pub const fn find_parameters(
29    base_field_prime_length: usize,
30    target_field_prime_bit_length: usize,
31    optimization_type: OptimizationType,
32) -> (usize, usize) {
33    let mut found = false;
34    let mut min_cost = 0usize;
35    let mut min_cost_limb_size = 0usize;
36    let mut min_cost_num_of_limbs = 0usize;
37
38    let surfeit = 10;
39    let mut max_limb_size = (base_field_prime_length - 1 - surfeit - 1) / 2 - 1;
40    if max_limb_size > target_field_prime_bit_length {
41        max_limb_size = target_field_prime_bit_length;
42    }
43    let mut limb_size = 1;
44
45    while limb_size <= max_limb_size {
46        let num_of_limbs = (target_field_prime_bit_length + limb_size - 1) / limb_size;
47
48        let group_size =
49            (base_field_prime_length - 1 - surfeit - 1 - 1 - limb_size + limb_size - 1) / limb_size;
50        let num_of_groups = (2 * num_of_limbs - 1 + group_size - 1) / group_size;
51
52        let mut this_cost = 0;
53
54        match optimization_type {
55            OptimizationType::Constraints => {
56                this_cost += 2 * num_of_limbs - 1;
57            },
58            OptimizationType::Weight => {
59                this_cost += 6 * num_of_limbs * num_of_limbs;
60            },
61        };
62
63        match optimization_type {
64            OptimizationType::Constraints => {
65                this_cost += target_field_prime_bit_length; // allocation of k
66                this_cost += target_field_prime_bit_length + num_of_limbs; // allocation of r
67                                                                           //this_cost += 2 * num_of_limbs - 1; // compute kp
68                this_cost += num_of_groups + (num_of_groups - 1) * (limb_size * 2 + surfeit) + 1;
69                // equality check
70            },
71            OptimizationType::Weight => {
72                this_cost += target_field_prime_bit_length * 3 + target_field_prime_bit_length; // allocation of k
73                this_cost += target_field_prime_bit_length * 3
74                    + target_field_prime_bit_length
75                    + num_of_limbs; // allocation of r
76                this_cost += num_of_limbs * num_of_limbs + 2 * (2 * num_of_limbs - 1); // compute kp
77                this_cost += num_of_limbs
78                    + num_of_groups
79                    + 6 * num_of_groups
80                    + (num_of_groups - 1) * (2 * limb_size + surfeit) * 4
81                    + 2; // equality check
82            },
83        };
84
85        if !found || this_cost < min_cost {
86            found = true;
87            min_cost = this_cost;
88            min_cost_limb_size = limb_size;
89            min_cost_num_of_limbs = num_of_limbs;
90        }
91
92        limb_size += 1;
93    }
94
95    (min_cost_num_of_limbs, min_cost_limb_size)
96}