1use crate::prelude::*;
  2use ark_ff::Field;
  3use ark_relations::r1cs::SynthesisError;
  4use ark_std::vec::Vec;
  5/// Generates constraints for selecting between one of two values.
  6pub trait CondSelectGadget<ConstraintF: Field>
  7where
  8    Self: Sized,
  9    Self: Clone,
 10{
 11    /// If `cond == &Boolean::TRUE`, then this returns `true_value`; else,
 12    /// returns `false_value`.
 13    ///
 14    /// # Note
 15    /// `Self::conditionally_select(cond, true_value, false_value)?` can be more
 16    /// succinctly written as `cond.select(&true_value, &false_value)?`.
 17    fn conditionally_select(
 18        cond: &Boolean<ConstraintF>,
 19        true_value: &Self,
 20        false_value: &Self,
 21    ) -> Result<Self, SynthesisError>;
 22
 23    /// Returns an element of `values` whose index in represented by `position`.
 24    /// `position` is an array of boolean that represents an unsigned integer in
 25    /// big endian order.
 26    ///
 27    /// # Example
 28    /// To get the 6th element of `values`, convert unsigned integer 6 (`0b110`)
 29    /// to `position = [True, True, False]`,
 30    /// and call `conditionally_select_power_of_two_vector(position, values)`.
 31    fn conditionally_select_power_of_two_vector(
 32        position: &[Boolean<ConstraintF>],
 33        values: &[Self],
 34    ) -> Result<Self, SynthesisError> {
 35        let m = values.len();
 36        let n = position.len();
 37
 38        // Assert m is a power of 2, and n = log(m)
 39        assert!(m.is_power_of_two());
 40        assert_eq!(1 << n, m);
 41
 42        let mut cur_mux_values = values.to_vec();
 43
 44        // Traverse the evaluation tree from bottom to top in level order traversal.
 45        // This is method 5.1 from https://github.com/mir-protocol/r1cs-workshop/blob/master/workshop.pdf
 46        // TODO: Add method 5.2/5.3
 47        for i in 0..n {
 48            // Size of current layer.
 49            let cur_size = 1 << (n - i);
 50            assert_eq!(cur_mux_values.len(), cur_size);
 51
 52            let mut next_mux_values = Vec::new();
 53            for j in (0..cur_size).step_by(2) {
 54                let cur = Self::conditionally_select(
 55                    &position[n - 1 - i],
 56                    // true case
 57                    &cur_mux_values[j + 1],
 58                    // false case
 59                    &cur_mux_values[j],
 60                )?;
 61                next_mux_values.push(cur);
 62            }
 63            cur_mux_values = next_mux_values;
 64        }
 65
 66        Ok(cur_mux_values[0].clone())
 67    }
 68}
 69
 70/// Performs a lookup in a 4-element table using two bits.
 71pub trait TwoBitLookupGadget<ConstraintF: Field>
 72where
 73    Self: Sized,
 74{
 75    /// The type of values being looked up.
 76    type TableConstant;
 77
 78    /// Interprets the slice `bits` as a two-bit integer `b = bits[0] + (bits[1]
 79    /// << 1)`, and then outputs `constants[b]`.
 80    ///
 81    /// For example, if `bits == [0, 1]`, and `constants == [0, 1, 2, 3]`, this
 82    /// method should output a variable corresponding to `2`.
 83    ///
 84    /// # Panics
 85    ///
 86    /// This method panics if `bits.len() != 2` or `constants.len() != 4`.
 87    fn two_bit_lookup(
 88        bits: &[Boolean<ConstraintF>],
 89        constants: &[Self::TableConstant],
 90    ) -> Result<Self, SynthesisError>;
 91}
 92
 93/// Uses three bits to perform a lookup into a table, where the last bit
 94/// conditionally negates the looked-up value.
 95pub trait ThreeBitCondNegLookupGadget<ConstraintF: Field>
 96where
 97    Self: Sized,
 98{
 99    /// The type of values being looked up.
100    type TableConstant;
101
102    /// Interprets the slice `bits` as a two-bit integer `b = bits[0] + (bits[1]
103    /// << 1)`, and then outputs `constants[b] * c`, where `c = if bits[2] {
104    /// -1 } else { 1 };`.
105    ///
106    /// That is, `bits[2]` conditionally negates the looked-up value.
107    ///
108    /// For example, if `bits == [1, 0, 1]`, and `constants == [0, 1, 2, 3]`,
109    /// this method should output a variable corresponding to `-1`.
110    ///
111    /// # Panics
112    ///
113    /// This method panics if `bits.len() != 3` or `constants.len() != 4`.
114    fn three_bit_cond_neg_lookup(
115        bits: &[Boolean<ConstraintF>],
116        b0b1: &Boolean<ConstraintF>,
117        constants: &[Self::TableConstant],
118    ) -> Result<Self, SynthesisError>;
119}