ark-r1cs-std/src/uint/cmp.rs
src/uint/cmp.rsRaw
1use crate::cmp::CmpGadget;
2
3use super::*;
4
5impl<const N: usize, T: PrimUInt, F: PrimeField + From<T>> CmpGadget<F> for UInt<N, T, F> {
6 fn is_ge(&self, other: &Self) -> Result<Boolean<F>, SynthesisError> {
7 if N + 1 < ((F::MODULUS_BIT_SIZE - 1) as usize) {
8 let a = self.to_fp()?;
9 let b = other.to_fp()?;
10 let (bits, _) = (a - b + F::from(T::max_value()) + F::one())
11 .to_bits_le_with_top_bits_zero(N + 1)?;
12 Ok(bits.last().unwrap().clone())
13 } else {
14 unimplemented!("bit sizes larger than modulus size not yet supported")
15 }
16 }
17}
18
19#[cfg(test)]
20mod tests {
21 use super::*;
22 use crate::{
23 alloc::{AllocVar, AllocationMode},
24 prelude::EqGadget,
25 uint::test_utils::{run_binary_exhaustive, run_binary_random},
26 R1CSVar,
27 };
28 use ark_ff::PrimeField;
29 use ark_test_curves::bls12_381::Fr;
30
31 fn uint_gt<T: PrimUInt, const N: usize, F: PrimeField + From<T>>(
32 a: UInt<N, T, F>,
33 b: UInt<N, T, F>,
34 ) -> Result<(), SynthesisError> {
35 let cs = a.cs().or(b.cs());
36 let both_constant = a.is_constant() && b.is_constant();
37 let expected_mode = if both_constant {
38 AllocationMode::Constant
39 } else {
40 AllocationMode::Witness
41 };
42 let computed = a.is_gt(&b)?;
43 let expected =
44 Boolean::new_variable(cs.clone(), || Ok(a.value()? > b.value()?), expected_mode)?;
45 assert_eq!(expected.value(), computed.value());
46 expected.enforce_equal(&computed)?;
47 if !both_constant {
48 assert!(cs.is_satisfied().unwrap());
49 }
50 Ok(())
51 }
52
53 fn uint_lt<T: PrimUInt, const N: usize, F: PrimeField + From<T>>(
54 a: UInt<N, T, F>,
55 b: UInt<N, T, F>,
56 ) -> Result<(), SynthesisError> {
57 let cs = a.cs().or(b.cs());
58 let both_constant = a.is_constant() && b.is_constant();
59 let expected_mode = if both_constant {
60 AllocationMode::Constant
61 } else {
62 AllocationMode::Witness
63 };
64 let computed = a.is_lt(&b)?;
65 let expected =
66 Boolean::new_variable(cs.clone(), || Ok(a.value()? < b.value()?), expected_mode)?;
67 assert_eq!(expected.value(), computed.value());
68 expected.enforce_equal(&computed)?;
69 if !both_constant {
70 assert!(cs.is_satisfied().unwrap());
71 }
72 Ok(())
73 }
74
75 fn uint_ge<T: PrimUInt, const N: usize, F: PrimeField + From<T>>(
76 a: UInt<N, T, F>,
77 b: UInt<N, T, F>,
78 ) -> Result<(), SynthesisError> {
79 let cs = a.cs().or(b.cs());
80 let both_constant = a.is_constant() && b.is_constant();
81 let expected_mode = if both_constant {
82 AllocationMode::Constant
83 } else {
84 AllocationMode::Witness
85 };
86 let computed = a.is_ge(&b)?;
87 let expected =
88 Boolean::new_variable(cs.clone(), || Ok(a.value()? >= b.value()?), expected_mode)?;
89 assert_eq!(expected.value(), computed.value());
90 expected.enforce_equal(&computed)?;
91 if !both_constant {
92 assert!(cs.is_satisfied().unwrap());
93 }
94 Ok(())
95 }
96
97 fn uint_le<T: PrimUInt, const N: usize, F: PrimeField + From<T>>(
98 a: UInt<N, T, F>,
99 b: UInt<N, T, F>,
100 ) -> Result<(), SynthesisError> {
101 let cs = a.cs().or(b.cs());
102 let both_constant = a.is_constant() && b.is_constant();
103 let expected_mode = if both_constant {
104 AllocationMode::Constant
105 } else {
106 AllocationMode::Witness
107 };
108 let computed = a.is_le(&b)?;
109 let expected =
110 Boolean::new_variable(cs.clone(), || Ok(a.value()? <= b.value()?), expected_mode)?;
111 assert_eq!(expected.value(), computed.value());
112 expected.enforce_equal(&computed)?;
113 if !both_constant {
114 assert!(cs.is_satisfied().unwrap());
115 }
116 Ok(())
117 }
118
119 #[test]
120 fn u8_gt() {
121 run_binary_exhaustive(uint_gt::<u8, 8, Fr>).unwrap()
122 }
123
124 #[test]
125 fn u16_gt() {
126 run_binary_random::<1000, 16, _, _>(uint_gt::<u16, 16, Fr>).unwrap()
127 }
128
129 #[test]
130 fn u32_gt() {
131 run_binary_random::<1000, 32, _, _>(uint_gt::<u32, 32, Fr>).unwrap()
132 }
133
134 #[test]
135 fn u64_gt() {
136 run_binary_random::<1000, 64, _, _>(uint_gt::<u64, 64, Fr>).unwrap()
137 }
138
139 #[test]
140 fn u128_gt() {
141 run_binary_random::<1000, 128, _, _>(uint_gt::<u128, 128, Fr>).unwrap()
142 }
143
144 #[test]
145 fn u8_lt() {
146 run_binary_exhaustive(uint_lt::<u8, 8, Fr>).unwrap()
147 }
148
149 #[test]
150 fn u16_lt() {
151 run_binary_random::<1000, 16, _, _>(uint_lt::<u16, 16, Fr>).unwrap()
152 }
153
154 #[test]
155 fn u32_lt() {
156 run_binary_random::<1000, 32, _, _>(uint_lt::<u32, 32, Fr>).unwrap()
157 }
158
159 #[test]
160 fn u64_lt() {
161 run_binary_random::<1000, 64, _, _>(uint_lt::<u64, 64, Fr>).unwrap()
162 }
163
164 #[test]
165 fn u128_lt() {
166 run_binary_random::<1000, 128, _, _>(uint_lt::<u128, 128, Fr>).unwrap()
167 }
168
169 #[test]
170 fn u8_le() {
171 run_binary_exhaustive(uint_le::<u8, 8, Fr>).unwrap()
172 }
173
174 #[test]
175 fn u16_le() {
176 run_binary_random::<1000, 16, _, _>(uint_le::<u16, 16, Fr>).unwrap()
177 }
178
179 #[test]
180 fn u32_le() {
181 run_binary_random::<1000, 32, _, _>(uint_le::<u32, 32, Fr>).unwrap()
182 }
183
184 #[test]
185 fn u64_le() {
186 run_binary_random::<1000, 64, _, _>(uint_le::<u64, 64, Fr>).unwrap()
187 }
188
189 #[test]
190 fn u128_le() {
191 run_binary_random::<1000, 128, _, _>(uint_le::<u128, 128, Fr>).unwrap()
192 }
193
194 #[test]
195 fn u8_ge() {
196 run_binary_exhaustive(uint_ge::<u8, 8, Fr>).unwrap()
197 }
198
199 #[test]
200 fn u16_ge() {
201 run_binary_random::<1000, 16, _, _>(uint_ge::<u16, 16, Fr>).unwrap()
202 }
203
204 #[test]
205 fn u32_ge() {
206 run_binary_random::<1000, 32, _, _>(uint_ge::<u32, 32, Fr>).unwrap()
207 }
208
209 #[test]
210 fn u64_ge() {
211 run_binary_random::<1000, 64, _, _>(uint_ge::<u64, 64, Fr>).unwrap()
212 }
213
214 #[test]
215 fn u128_ge() {
216 run_binary_random::<1000, 128, _, _>(uint_ge::<u128, 128, Fr>).unwrap()
217 }
218}