1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
use snarkvm_fields::PrimeField;
use snarkvm_r1cs::ConstraintSystem;
use crate::{
bits::boolean::Boolean,
errors::UnsignedIntegerError,
integers::uint::*,
traits::{
alloc::AllocGadget,
bits::EvaluateLtGadget,
eq::{EqGadget, EvaluateEqGadget},
integers::{Add, Div, Integer},
select::CondSelectGadget,
},
};
macro_rules! div_int_impl {
($($gadget:ident),*) => ($(
impl<F: PrimeField> Div<F> for $gadget {
type ErrorType = UnsignedIntegerError;
fn div<CS: ConstraintSystem<F>>(
&self,
mut cs: CS,
other: &Self,
) -> Result<Self, Self::ErrorType> {
if !other.is_constant() {
other.evaluate_equal(cs.ns(||"is_divisor_zero"), &Self::constant(0 as <$gadget as Integer>::IntegerType))?.enforce_equal(cs.ns(||"divisor_is_not_zero"), &Boolean::constant(false))?;
}
if let Some(value) = other.value {
if value == 0 as <$gadget as Integer>::IntegerType {
return Err(UnsignedIntegerError::DivisionByZero.into());
}
}
if self.is_constant() && other.is_constant() {
return Ok(Self::constant(self.value.unwrap().wrapping_div(other.value.unwrap())));
}
let one = Self::constant(1 as <$gadget as Integer>::IntegerType);
let zero = Self::constant(0 as <$gadget as Integer>::IntegerType);
let mut quotient_bits = Vec::new();
let mut remainder = zero.clone();
for (i, bit) in self.bits.iter().rev().enumerate() {
remainder = remainder.add(cs.ns(|| format!("R_double_{}", i)), &remainder)?;
let remainder_plus_one = remainder.add(cs.ns(|| format!("set_remainder_bit_{}", i)), &one)?;
remainder = Self::conditionally_select(
&mut cs.ns(|| format!("increment_or_remainder_{}", i)),
&bit,
&remainder_plus_one,
&remainder,
)?;
let r_larger_or_equal_to_d = remainder.less_than(cs.ns(|| format!("check_if_R_greater_than_D_{}", i)), &other)?.not();
let r_sub_d = {
let result = Self::alloc(cs.ns(||format!("r_sub_d_result_{}", i)), || {
let remainder_value = remainder.value.unwrap();
let divisor_value = other.value.unwrap();
if remainder_value < divisor_value {
Ok(0 as <$gadget as Integer>::IntegerType)
} else{
Ok(remainder_value - divisor_value)
}
})?;
let result_plus_d = result.add(cs.ns(|| format!("r_sub_d_add_d_{}", i)), &other)?;
let result_plus_d_sub_r = result_plus_d.sub(cs.ns(|| format!("r_sub_d_add_d_sub_r_{}", i)), &remainder)?;
let should_be_zero = Self::conditionally_select(
cs.ns(|| format!("select_result_plus_d_sub_r_or_zero_{}", i)),
&r_larger_or_equal_to_d,
&result_plus_d_sub_r,
&zero,
)?;
should_be_zero.enforce_equal(cs.ns(|| format!("should_be_zero_{}", i)), &zero)?;
result
};
remainder = Self::conditionally_select(
&mut cs.ns(|| format!("subtract_or_same_{}", i)),
&r_larger_or_equal_to_d,
&r_sub_d,
&remainder,
)?;
quotient_bits.push(r_larger_or_equal_to_d);
}
quotient_bits.reverse();
let quotient = Self::from_bits_le("ient_bits);
Ok(quotient)
}
}
)*)
}
div_int_impl!(UInt8, UInt16, UInt32, UInt64, UInt128);