/src/botan/src/lib/math/bigint/divide.cpp
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * Division Algorithm |
3 | | * (C) 1999-2007,2012,2018 Jack Lloyd |
4 | | * |
5 | | * Botan is released under the Simplified BSD License (see license.txt) |
6 | | */ |
7 | | |
8 | | #include <botan/divide.h> |
9 | | #include <botan/internal/mp_core.h> |
10 | | #include <botan/internal/mp_madd.h> |
11 | | #include <botan/internal/ct_utils.h> |
12 | | #include <botan/internal/bit_ops.h> |
13 | | |
14 | | namespace Botan { |
15 | | |
16 | | namespace { |
17 | | |
18 | | /* |
19 | | * Handle signed operands, if necessary |
20 | | */ |
21 | | void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r) |
22 | 2.55M | { |
23 | 2.55M | q.cond_flip_sign(x.sign() != y.sign()); |
24 | 2.55M | |
25 | 2.55M | if(x.is_negative() && r.is_nonzero()) |
26 | 1.21k | { |
27 | 1.21k | q -= 1; |
28 | 1.21k | r = y.abs() - r; |
29 | 1.21k | } |
30 | 2.55M | } |
31 | | |
32 | | inline bool division_check(word q, word y2, word y1, |
33 | | word x3, word x2, word x1) |
34 | 5.70M | { |
35 | 5.70M | /* |
36 | 5.70M | Compute (y3,y2,y1) = (y2,y1) * q |
37 | 5.70M | and return true if (y3,y2,y1) > (x3,x2,x1) |
38 | 5.70M | */ |
39 | 5.70M | |
40 | 5.70M | word y3 = 0; |
41 | 5.70M | y1 = word_madd2(q, y1, &y3); |
42 | 5.70M | y2 = word_madd2(q, y2, &y3); |
43 | 5.70M | |
44 | 5.70M | const word x[3] = { x1, x2, x3 }; |
45 | 5.70M | const word y[3] = { y1, y2, y3 }; |
46 | 5.70M | |
47 | 5.70M | return bigint_ct_is_lt(x, 3, y, 3).is_set(); |
48 | 5.70M | } |
49 | | |
50 | | } |
51 | | |
52 | | void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) |
53 | 98.5k | { |
54 | 98.5k | const size_t x_words = x.sig_words(); |
55 | 98.5k | const size_t y_words = y.sig_words(); |
56 | 98.5k | |
57 | 98.5k | const size_t x_bits = x.bits(); |
58 | 98.5k | |
59 | 98.5k | BigInt q(BigInt::Positive, x_words); |
60 | 98.5k | BigInt r(BigInt::Positive, y_words); |
61 | 98.5k | BigInt t(BigInt::Positive, y_words); // a temporary |
62 | 98.5k | |
63 | 148M | for(size_t i = 0; i != x_bits; ++i) |
64 | 148M | { |
65 | 148M | const size_t b = x_bits - 1 - i; |
66 | 148M | const bool x_b = x.get_bit(b); |
67 | 148M | |
68 | 148M | r *= 2; |
69 | 148M | r.conditionally_set_bit(0, x_b); |
70 | 148M | |
71 | 148M | const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0; |
72 | 148M | |
73 | 148M | q.conditionally_set_bit(b, r_gte_y); |
74 | 148M | r.ct_cond_swap(r_gte_y, t); |
75 | 148M | } |
76 | 98.5k | |
77 | 98.5k | sign_fixup(x, y, q, r); |
78 | 98.5k | r_out = r; |
79 | 98.5k | q_out = q; |
80 | 98.5k | } |
81 | | |
82 | | void ct_divide_u8(const BigInt& x, uint8_t y, BigInt& q_out, uint8_t& r_out) |
83 | 750 | { |
84 | 750 | const size_t x_words = x.sig_words(); |
85 | 750 | const size_t x_bits = x.bits(); |
86 | 750 | |
87 | 750 | BigInt q(BigInt::Positive, x_words); |
88 | 750 | uint32_t r = 0; |
89 | 750 | |
90 | 645k | for(size_t i = 0; i != x_bits; ++i) |
91 | 645k | { |
92 | 645k | const size_t b = x_bits - 1 - i; |
93 | 645k | const bool x_b = x.get_bit(b); |
94 | 645k | |
95 | 645k | r *= 2; |
96 | 645k | r += x_b; |
97 | 645k | |
98 | 645k | const auto r_gte_y = CT::Mask<uint32_t>::is_gte(r, y); |
99 | 645k | |
100 | 645k | q.conditionally_set_bit(b, r_gte_y.is_set()); |
101 | 645k | r = r_gte_y.select(r - y, r); |
102 | 645k | } |
103 | 750 | |
104 | 750 | if(x.is_negative()) |
105 | 0 | { |
106 | 0 | q.flip_sign(); |
107 | 0 | if(r != 0) |
108 | 0 | { |
109 | 0 | --q; |
110 | 0 | r = y - r; |
111 | 0 | } |
112 | 0 | } |
113 | 750 | |
114 | 750 | r_out = static_cast<uint8_t>(r); |
115 | 750 | q_out = q; |
116 | 750 | } |
117 | | |
118 | | BigInt ct_modulo(const BigInt& x, const BigInt& y) |
119 | 1.86k | { |
120 | 1.86k | if(y.is_negative() || y.is_zero()) |
121 | 0 | throw Invalid_Argument("ct_modulo requires y > 0"); |
122 | 1.86k | |
123 | 1.86k | const size_t y_words = y.sig_words(); |
124 | 1.86k | |
125 | 1.86k | const size_t x_bits = x.bits(); |
126 | 1.86k | |
127 | 1.86k | BigInt r(BigInt::Positive, y_words); |
128 | 1.86k | BigInt t(BigInt::Positive, y_words); |
129 | 1.86k | |
130 | 2.02M | for(size_t i = 0; i != x_bits; ++i) |
131 | 2.02M | { |
132 | 2.02M | const size_t b = x_bits - 1 - i; |
133 | 2.02M | const bool x_b = x.get_bit(b); |
134 | 2.02M | |
135 | 2.02M | r *= 2; |
136 | 2.02M | r.conditionally_set_bit(0, x_b); |
137 | 2.02M | |
138 | 2.02M | const bool r_gte_y = bigint_sub3(t.mutable_data(), r.data(), r.size(), y.data(), y_words) == 0; |
139 | 2.02M | |
140 | 2.02M | r.ct_cond_swap(r_gte_y, t); |
141 | 2.02M | } |
142 | 1.86k | |
143 | 1.86k | if(x.is_negative()) |
144 | 412 | { |
145 | 412 | if(r.is_nonzero()) |
146 | 299 | { |
147 | 299 | r = y - r; |
148 | 299 | } |
149 | 412 | } |
150 | 1.86k | |
151 | 1.86k | return r; |
152 | 1.86k | } |
153 | | |
154 | | /* |
155 | | * Solve x = q * y + r |
156 | | * |
157 | | * See Handbook of Applied Cryptography section 14.2.5 |
158 | | */ |
159 | | void divide(const BigInt& x, const BigInt& y_arg, BigInt& q_out, BigInt& r_out) |
160 | 2.45M | { |
161 | 2.45M | if(y_arg.is_zero()) |
162 | 0 | throw BigInt::DivideByZero(); |
163 | 2.45M | |
164 | 2.45M | const size_t y_words = y_arg.sig_words(); |
165 | 2.45M | |
166 | 2.45M | BOTAN_ASSERT_NOMSG(y_words > 0); |
167 | 2.45M | |
168 | 2.45M | BigInt y = y_arg; |
169 | 2.45M | |
170 | 2.45M | BigInt r = x; |
171 | 2.45M | BigInt q = 0; |
172 | 2.45M | secure_vector<word> ws; |
173 | 2.45M | |
174 | 2.45M | r.set_sign(BigInt::Positive); |
175 | 2.45M | y.set_sign(BigInt::Positive); |
176 | 2.45M | |
177 | 2.45M | // Calculate shifts needed to normalize y with high bit set |
178 | 2.45M | const size_t shifts = y.top_bits_free(); |
179 | 2.45M | |
180 | 2.45M | y <<= shifts; |
181 | 2.45M | r <<= shifts; |
182 | 2.45M | |
183 | 2.45M | // we know y has not changed size, since we only shifted up to set high bit |
184 | 2.45M | const size_t t = y_words - 1; |
185 | 2.45M | const size_t n = std::max(y_words, r.sig_words()) - 1; // r may have changed size however |
186 | 2.45M | |
187 | 2.45M | BOTAN_ASSERT_NOMSG(n >= t); |
188 | 2.45M | |
189 | 2.45M | q.grow_to(n - t + 1); |
190 | 2.45M | |
191 | 2.45M | word* q_words = q.mutable_data(); |
192 | 2.45M | |
193 | 2.45M | BigInt shifted_y = y << (BOTAN_MP_WORD_BITS * (n-t)); |
194 | 2.45M | |
195 | 2.45M | // Set q_{n-t} to number of times r > shifted_y |
196 | 2.45M | q_words[n-t] = r.reduce_below(shifted_y, ws); |
197 | 2.45M | |
198 | 2.45M | const word y_t0 = y.word_at(t); |
199 | 2.45M | const word y_t1 = y.word_at(t-1); |
200 | 2.45M | BOTAN_DEBUG_ASSERT((y_t0 >> (BOTAN_MP_WORD_BITS-1)) == 1); |
201 | 2.45M | |
202 | 5.30M | for(size_t j = n; j != t; --j) |
203 | 2.85M | { |
204 | 2.85M | const word x_j0 = r.word_at(j); |
205 | 2.85M | const word x_j1 = r.word_at(j-1); |
206 | 2.85M | const word x_j2 = r.word_at(j-2); |
207 | 2.85M | |
208 | 2.85M | word qjt = bigint_divop(x_j0, x_j1, y_t0); |
209 | 2.85M | |
210 | 2.85M | qjt = CT::Mask<word>::is_equal(x_j0, y_t0).select(MP_WORD_MAX, qjt); |
211 | 2.85M | |
212 | 2.85M | // Per HAC 14.23, this operation is required at most twice |
213 | 2.85M | qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2); |
214 | 2.85M | qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2); |
215 | 2.85M | BOTAN_DEBUG_ASSERT(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) == false); |
216 | 2.85M | |
217 | 2.85M | shifted_y >>= BOTAN_MP_WORD_BITS; |
218 | 2.85M | // Now shifted_y == y << (BOTAN_MP_WORD_BITS * (j-t-1)) |
219 | 2.85M | |
220 | 2.85M | // TODO this sequence could be better |
221 | 2.85M | r -= qjt * shifted_y; |
222 | 2.85M | qjt -= r.is_negative(); |
223 | 2.85M | r += static_cast<word>(r.is_negative()) * shifted_y; |
224 | 2.85M | |
225 | 2.85M | q_words[j-t-1] = qjt; |
226 | 2.85M | } |
227 | 2.45M | |
228 | 2.45M | r >>= shifts; |
229 | 2.45M | |
230 | 2.45M | sign_fixup(x, y_arg, q, r); |
231 | 2.45M | |
232 | 2.45M | r_out = r; |
233 | 2.45M | q_out = q; |
234 | 2.45M | } |
235 | | |
236 | | } |