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