r1cs/
bitwise_operations.rs

1//! This module extends GadgetBuilder with bitwise operations such as rotations, bitwise AND, and
2//! so forth.
3
4use crate::expression::{BinaryExpression, BooleanExpression};
5use crate::field::Field;
6use crate::gadget_builder::GadgetBuilder;
7
8impl<F: Field> GadgetBuilder<F> {
9    /// The bitwise negation of a binary expression `x`, a.k.a. `~x`.
10    pub fn bitwise_not(&mut self, x: &BinaryExpression<F>) -> BinaryExpression<F> {
11        let bits = x.bits.iter()
12            .map(|w| self.not(w))
13            .collect();
14        BinaryExpression { bits }
15    }
16
17    /// The bitwise conjunction of two binary expressions `x` and `y`, a.k.a. `x & y`.
18    pub fn bitwise_and(
19        &mut self, x: &BinaryExpression<F>, y: &BinaryExpression<F>,
20    ) -> BinaryExpression<F> {
21        assert_eq!(x.len(), y.len());
22        let l = x.len();
23        let bits = (0..l).map(|i|
24            self.and(&x.bits[i], &y.bits[i])
25        ).collect();
26        BinaryExpression { bits }
27    }
28
29    /// The bitwise disjunction of two binary expressions `x` and `y`, a.k.a. `x | y`.
30    pub fn bitwise_or(
31        &mut self, x: &BinaryExpression<F>, y: &BinaryExpression<F>,
32    ) -> BinaryExpression<F> {
33        assert_eq!(x.len(), y.len());
34        let l = x.len();
35        let bits = (0..l).map(|i|
36            self.or(&x.bits[i], &y.bits[i])
37        ).collect();
38        BinaryExpression { bits }
39    }
40
41    /// The bitwise exclusive disjunction of two binary expressions `x` and `y`, a.k.a. `x ^ y`.
42    pub fn bitwise_xor<BE1, BE2>(
43        &mut self, x: &BinaryExpression<F>, y: &BinaryExpression<F>,
44    ) -> BinaryExpression<F> {
45        assert_eq!(x.len(), y.len());
46        let l = x.len();
47        let bits = (0..l).map(|i|
48            self.xor(&x.bits[i], &y.bits[i])
49        ).collect();
50        BinaryExpression { bits }
51    }
52
53    /// Rotate bits in the direction of increasing significance. This is equivalent to "left rotate"
54    /// in most programming languages.
55    pub fn bitwise_rotate_inc_significance(
56        &mut self, x: &BinaryExpression<F>, n: usize,
57    ) -> BinaryExpression<F> {
58        let l = x.len();
59        let bits = (0..l).map(|i| {
60            // This is equivalent to (i - n) mod l.
61            let from_idx = (l + i - n % l) % l;
62            x.bits[from_idx].clone()
63        }).collect();
64        BinaryExpression { bits }
65    }
66
67    /// Rotate bits in the direction of increasing significance. This is equivalent to "right
68    /// rotate" in most programming languages.
69    pub fn bitwise_rotate_dec_significance(
70        &mut self, x: &BinaryExpression<F>, n: usize,
71    ) -> BinaryExpression<F> {
72        let l = x.len();
73        let bits = (0..l).map(|i| {
74            let from_idx = (i + n) % l;
75            x.bits[from_idx].clone()
76        }).collect();
77        BinaryExpression { bits }
78    }
79
80    /// Shift bits in the direction of increasing significance, discarding bits on the most
81    /// significant end and inserting zeros on the least significant end. This is equivalent to
82    /// "left shift" in most programming languages.
83    pub fn bitwise_shift_inc_significance(
84        &mut self, x: &BinaryExpression<F>, n: usize,
85    ) -> BinaryExpression<F> {
86        let bits = (0..x.len()).map(|i| {
87            if i < n {
88                BooleanExpression::_false()
89            } else {
90                let from_idx = i - n;
91                x.bits[from_idx].clone()
92            }
93        }).collect();
94        BinaryExpression { bits }
95    }
96
97    /// Shift bits in the direction of decreasing significance, discarding bits on the least
98    /// significant end and inserting zeros on the most significant end. This is equivalent to
99    /// "right shift" in most programming languages.
100    pub fn bitwise_shift_dec_significance(
101        &mut self, x: &BinaryExpression<F>, n: usize,
102    ) -> BinaryExpression<F> {
103        let l = x.len();
104        let bits = (0..l).map(|i| {
105            if i < l - n {
106                let from_idx = i + n;
107                x.bits[from_idx].clone()
108            } else {
109                BooleanExpression::_false()
110            }
111        }).collect();
112        BinaryExpression { bits }
113    }
114}
115
116#[cfg(test)]
117mod tests {
118    use num::BigUint;
119
120    use crate::expression::BinaryExpression;
121    use crate::gadget_builder::GadgetBuilder;
122    use crate::test_util::F257;
123
124    #[test]
125    fn bitwise_not() {
126        let mut builder = GadgetBuilder::<F257>::new();
127        let x = builder.binary_wire(8);
128        let not_x = builder.bitwise_not(&BinaryExpression::from(&x));
129        let gadget = builder.build();
130
131        // ~00010011 = 11101100.
132        let mut values = binary_unsigned_values!(&x => &BigUint::from(0b00010011u32));
133        assert!(gadget.execute(&mut values));
134        assert_eq!(BigUint::from(0b11101100u32), not_x.evaluate(&values));
135    }
136
137    #[test]
138    fn bitwise_and() {
139        let mut builder = GadgetBuilder::<F257>::new();
140        let x = builder.binary_wire(8);
141        let y = builder.binary_wire(8);
142        let x_and_y = builder.bitwise_and(&BinaryExpression::from(&x), &BinaryExpression::from(&y));
143        let gadget = builder.build();
144
145        // 0 & 0 = 0.
146        let mut values_0_0 = binary_unsigned_values!(
147            &x => &BigUint::from(0u32),
148            &y => &BigUint::from(0u32));
149        assert!(gadget.execute(&mut values_0_0));
150        assert_eq!(BigUint::from(0u32), x_and_y.evaluate(&values_0_0));
151
152        // 255 & 0 = 0.
153        let mut values_255_0 = binary_unsigned_values!(
154            &x => &BigUint::from(0b11111111u32),
155            &y => &BigUint::from(0u32));
156        assert!(gadget.execute(&mut values_255_0));
157        assert_eq!(BigUint::from(0u32), x_and_y.evaluate(&values_255_0));
158
159        // 255 & 255 = 255.
160        let mut values_255_255 = binary_unsigned_values!(
161            &x => &BigUint::from(0b11111111u32),
162            &y => &BigUint::from(0b11111111u32));
163        assert!(gadget.execute(&mut values_255_255));
164        assert_eq!(BigUint::from(0b11111111u32), x_and_y.evaluate(&values_255_255));
165
166        // 11111100 & 00111111 = 00111100.
167        let mut values_11111100_00111111 = binary_unsigned_values!(
168            &x => &BigUint::from(0b11111100u32),
169            &y => &BigUint::from(0b00111111u32));
170        assert!(gadget.execute(&mut values_11111100_00111111));
171        assert_eq!(BigUint::from(0b00111100u32), x_and_y.evaluate(&values_11111100_00111111));
172    }
173
174    #[test]
175    fn bitwise_rotate_dec_significance() {
176        let mut builder = GadgetBuilder::<F257>::new();
177        let x = builder.binary_wire(8);
178        let x_rot = builder.bitwise_rotate_dec_significance(&BinaryExpression::from(&x), 3);
179        let gadget = builder.build();
180
181        // 00000000 >> 3 = 00000000.
182        let mut values_zero = binary_unsigned_values!(&x => &BigUint::from(0u32));
183        assert!(gadget.execute(&mut values_zero));
184        assert_eq!(BigUint::from(0u32), x_rot.evaluate(&values_zero));
185
186        // 00010011 >> 3 = 01100010.
187        let mut values_nonzero = binary_unsigned_values!(&x => &BigUint::from(0b00010011u32));
188        assert!(gadget.execute(&mut values_nonzero));
189        assert_eq!(BigUint::from(0b01100010u32), x_rot.evaluate(&values_nonzero));
190    }
191
192    #[test]
193    fn bitwise_rotate_dec_significance_multiple_wraps() {
194        let mut builder = GadgetBuilder::<F257>::new();
195        let x = builder.binary_wire(8);
196        let x_rot = builder.bitwise_rotate_dec_significance(&BinaryExpression::from(&x), 19);
197        let gadget = builder.build();
198
199        // 00010011 >> 19 = 00010011 >> 3 = 01100010.
200        let mut values = binary_unsigned_values!(&x => &BigUint::from(0b00010011u32));
201        assert!(gadget.execute(&mut values));
202        assert_eq!(BigUint::from(0b01100010u32), x_rot.evaluate(&values));
203    }
204
205    // TODO: Tests for shift methods
206}
r1cs/bitwise_operations.rs

r1cs/
bitwise_operations.rs
