1use ark_ff::PrimeField;
  2use ark_relations::r1cs::SynthesisError;
  3use ark_std::{ops::BitOr, ops::BitOrAssign};
  4
  5use crate::{
  6    eq::EqGadget,
  7    fields::{fp::FpVar, FieldVar},
  8};
  9
 10use super::Boolean;
 11
 12impl<F: PrimeField> Boolean<F> {
 13    fn _or(&self, other: &Self) -> Result<Self, SynthesisError> {
 14        use Boolean::*;
 15        match (self, other) {
 16            (&Constant(false), x) | (x, &Constant(false)) => Ok(x.clone()),
 17            (&Constant(true), _) | (_, &Constant(true)) => Ok(Constant(true)),
 18            (Var(ref x), Var(ref y)) => Ok(Var(x.or(y)?)),
 19        }
 20    }
 21
 22    /// Outputs `bits[0] | bits[1] | ... | bits.last().unwrap()`.
 23    ///
 24    /// ```
 25    /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
 26    /// // We'll use the BLS12-381 scalar field for our constraints.
 27    /// use ark_test_curves::bls12_381::Fr;
 28    /// use ark_relations::r1cs::*;
 29    /// use ark_r1cs_std::prelude::*;
 30    ///
 31    /// let cs = ConstraintSystem::<Fr>::new_ref();
 32    ///
 33    /// let a = Boolean::new_witness(cs.clone(), || Ok(true))?;
 34    /// let b = Boolean::new_witness(cs.clone(), || Ok(false))?;
 35    /// let c = Boolean::new_witness(cs.clone(), || Ok(false))?;
 36    ///
 37    /// Boolean::kary_or(&[a.clone(), b.clone(), c.clone()])?.enforce_equal(&Boolean::TRUE)?;
 38    /// Boolean::kary_or(&[a.clone(), c.clone()])?.enforce_equal(&Boolean::TRUE)?;
 39    /// Boolean::kary_or(&[b.clone(), c.clone()])?.enforce_equal(&Boolean::FALSE)?;
 40    ///
 41    /// assert!(cs.is_satisfied().unwrap());
 42    /// # Ok(())
 43    /// # }
 44    /// ```
 45    #[tracing::instrument(target = "r1cs")]
 46    pub fn kary_or(bits: &[Self]) -> Result<Self, SynthesisError> {
 47        assert!(!bits.is_empty());
 48        if bits.len() <= 3 {
 49            let mut cur: Option<Self> = None;
 50            for next in bits {
 51                cur = if let Some(b) = cur {
 52                    Some(b | next)
 53                } else {
 54                    Some(next.clone())
 55                };
 56            }
 57
 58            Ok(cur.expect("should not be 0"))
 59        } else {
 60            // b0 | b1 | ... | bN == 1 if and only if not all of b0, b1, ..., bN are 0.
 61            // We can enforce this by requiring that the sum of b0, b1, ..., bN is not 0.
 62            let sum_bits: FpVar<_> = bits.iter().map(|b| FpVar::from(b.clone())).sum();
 63            sum_bits.is_neq(&FpVar::zero())
 64        }
 65    }
 66}
 67
 68impl<'a, F: PrimeField> BitOr<Self> for &'a Boolean<F> {
 69    type Output = Boolean<F>;
 70
 71    /// Outputs `self | other`.
 72    ///
 73    /// If at least one of `self` and `other` are constants, then this method
 74    /// *does not* create any constraints or variables.
 75    ///
 76    /// ```
 77    /// # fn main() -> Result<(), ark_relations::r1cs::SynthesisError> {
 78    /// // We'll use the BLS12-381 scalar field for our constraints.
 79    /// use ark_test_curves::bls12_381::Fr;
 80    /// use ark_relations::r1cs::*;
 81    /// use ark_r1cs_std::prelude::*;
 82    ///
 83    /// let cs = ConstraintSystem::<Fr>::new_ref();
 84    ///
 85    /// let a = Boolean::new_witness(cs.clone(), || Ok(true))?;
 86    /// let b = Boolean::new_witness(cs.clone(), || Ok(false))?;
 87    ///
 88    /// (&a | &b).enforce_equal(&Boolean::TRUE)?;
 89    /// (&b | &a).enforce_equal(&Boolean::TRUE)?;
 90    ///
 91    /// (&a | &a).enforce_equal(&Boolean::TRUE)?;
 92    /// (&b | &b).enforce_equal(&Boolean::FALSE)?;
 93    ///
 94    /// assert!(cs.is_satisfied().unwrap());
 95    /// # Ok(())
 96    /// # }
 97    /// ```
 98    #[tracing::instrument(target = "r1cs", skip(self, other))]
 99    fn bitor(self, other: Self) -> Self::Output {
100        self._or(other).unwrap()
101    }
102}
103
104impl<'a, F: PrimeField> BitOr<&'a Self> for Boolean<F> {
105    type Output = Boolean<F>;
106
107    #[tracing::instrument(target = "r1cs", skip(self, other))]
108    fn bitor(self, other: &Self) -> Self::Output {
109        self._or(&other).unwrap()
110    }
111}
112
113impl<'a, F: PrimeField> BitOr<Boolean<F>> for &'a Boolean<F> {
114    type Output = Boolean<F>;
115
116    #[tracing::instrument(target = "r1cs", skip(self, other))]
117    fn bitor(self, other: Boolean<F>) -> Self::Output {
118        self._or(&other).unwrap()
119    }
120}
121
122impl<F: PrimeField> BitOr<Self> for Boolean<F> {
123    type Output = Self;
124
125    #[tracing::instrument(target = "r1cs", skip(self, other))]
126    fn bitor(self, other: Self) -> Self::Output {
127        self._or(&other).unwrap()
128    }
129}
130
131impl<F: PrimeField> BitOrAssign<Self> for Boolean<F> {
132    /// Sets `self = self | other`.
133    #[tracing::instrument(target = "r1cs", skip(self, other))]
134    fn bitor_assign(&mut self, other: Self) {
135        let result = self._or(&other).unwrap();
136        *self = result;
137    }
138}
139
140impl<'a, F: PrimeField> BitOrAssign<&'a Self> for Boolean<F> {
141    /// Sets `self = self | other`.
142    #[tracing::instrument(target = "r1cs", skip(self, other))]
143    fn bitor_assign(&mut self, other: &'a Self) {
144        let result = self._or(other).unwrap();
145        *self = result;
146    }
147}
148
149#[cfg(test)]
150mod tests {
151    use super::*;
152    use crate::{
153        alloc::{AllocVar, AllocationMode},
154        boolean::test_utils::run_binary_exhaustive,
155        prelude::EqGadget,
156        R1CSVar,
157    };
158    use ark_test_curves::bls12_381::Fr;
159
160    #[test]
161    fn or() {
162        run_binary_exhaustive::<Fr>(|a, b| {
163            let cs = a.cs().or(b.cs());
164            let both_constant = a.is_constant() && b.is_constant();
165            let computed = &a | &b;
166            let expected_mode = if both_constant {
167                AllocationMode::Constant
168            } else {
169                AllocationMode::Witness
170            };
171            let expected =
172                Boolean::new_variable(cs.clone(), || Ok(a.value()? | b.value()?), expected_mode)?;
173            assert_eq!(expected.value(), computed.value());
174            expected.enforce_equal(&computed)?;
175            if !both_constant {
176                assert!(cs.is_satisfied().unwrap());
177            }
178            Ok(())
179        })
180        .unwrap()
181    }
182}