Botan 3.14.1
Crypto and TLS for C&
divide.cpp
Go to the documentation of this file.
1/*
2* Division Algorithms
3* (C) 1999-2007,2012,2018,2021,2026 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#include <botan/internal/divide.h>
9
10#include <botan/exceptn.h>
11#include <botan/internal/bit_ops.h>
12#include <botan/internal/ct_utils.h>
13#include <botan/internal/mp_core.h>
14
15namespace Botan {
16
17namespace {
18
19/*
20* Handle signed operands, if necessary
21*/
22void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r) {
23 q.cond_flip_sign(x.sign() != y.sign());
24
25 if(x.signum() < 0 && r.signum() != 0) {
26 if(y.signum() > 0) {
27 q -= 1;
28 } else {
29 q += 1;
30 }
31 r = y.abs() - r;
32 }
33}
34
35/*
36* Computes (y3,y2,y1) = (y2,y1) * q and returns a mask which is set
37* if (y3,y2,y1) > (x3,x2,x1)
38*/
39inline CT::Mask<word> division_check_ct(word q, word y2, word y1, word x3, word x2, word x1) {
40 word y3 = 0;
41 y1 = word_madd2(q, y1, &y3);
42 y2 = word_madd2(q, y2, &y3);
43
44 const auto gt3 = CT::Mask<word>::is_gt(y3, x3);
45 const auto eq3 = CT::Mask<word>::is_equal(y3, x3);
46 const auto gt2 = CT::Mask<word>::is_gt(y2, x2);
47 const auto eq2 = CT::Mask<word>::is_equal(y2, x2);
48 const auto gt1 = CT::Mask<word>::is_gt(y1, x1);
49
50 return gt3 | (eq3 & (gt2 | (eq2 & gt1)));
51}
52
53/*
54* Word-serial constant time unsigned division
55*
56* Sets q = |x| / |y| and r = |x| % |y|, using schoolbook long division
57* (HAC Algorithm 14.20) with a quotient digit estimate from a
58* precomputed reciprocal of the normalized divisor, and with the digit
59* selection, corrections, and add-back all computed as masked updates.
60*
61* All control flow and memory indexing depends only on the word lengths
62* of x and y, which are treated as public. The normalization shift
63* depends on the bit length of y's top word, but is used only as a
64* shift count or mask input, never for control flow or indexing.
65*/
66void ct_divide_impl(BigInt& q_out, BigInt& r_out, const BigInt& x, const BigInt& y) {
67 constexpr size_t WB = WordInfo<word>::bits;
68
69 const size_t x_words = x.sig_words();
70 const size_t y_words = y.sig_words();
71 BOTAN_ASSERT_NOMSG(y_words > 0);
72
73 if(x_words < y_words) {
74 // Here |x| < |y| so q = 0 and r = |x|
75 r_out = x.abs();
76 q_out = BigInt::zero();
77 return;
78 }
79
80 const size_t r_words = x_words + 1;
81 const size_t q_words = x_words - y_words + 1;
82
83 // The number of leading zero bits of y, in [0,WB)
84 const word s = static_cast<word>(WB) - static_cast<word>(high_bit(CT::value_barrier(y._data()[y_words - 1])));
85 const auto s_mask = CT::Mask<word>::expand(s);
86 const word s_comp = s_mask.if_set_return(static_cast<word>(WB) - s);
87
88 secure_vector<word> yn(y_words);
89 secure_vector<word> rw(r_words);
90 secure_vector<word> qw(q_words);
91
92 // Normalize: yn = |y| << s (which sets the top bit of yn) and rw = |x| << s;
93 // shifting y stays within y_words words, shifting x adds at most one word
94 word carry = 0;
95 for(size_t i = 0; i != y_words; ++i) {
96 const word w = y._data()[i];
97 yn[i] = (w << s) | carry;
98 carry = s_mask.if_set_return(w >> s_comp);
99 }
100
101 carry = 0;
102 for(size_t i = 0; i != x_words; ++i) {
103 const word w = x._data()[i];
104 rw[i] = (w << s) | carry;
105 carry = s_mask.if_set_return(w >> s_comp);
106 }
107 rw[x_words] = carry;
108
109 const auto div_by_yn = divide_precomp<word>::setup(CT::value_barrier(yn[y_words - 1]));
110
111 if(y_words == 1) {
112 /*
113 * 2/1 word-serial division. The initial remainder is the shift-out
114 * carry, which is less than 2^s and so less than the divisor.
115 */
116 word r = rw[x_words];
117 for(size_t i = x_words; i > 0; --i) {
118 const auto [qi, ri] = div_by_yn.divmod_2to1_ct(r, rw[i - 1]);
119 qw[i - 1] = qi;
120 r = ri;
121 }
122
123 rw[0] = r >> s;
124 } else {
125 const word yn1 = yn[y_words - 1];
126 const word yn2 = yn[y_words - 2];
127
128 for(size_t i = q_words; i > 0; --i) {
129 const size_t j = i - 1; // current window is rw[j ... j + y_words]
130
131 const word u2 = rw[j + y_words];
132 const word u1 = rw[j + y_words - 1];
133 const word u0 = rw[j + y_words - 2];
134
135 /*
136 * Estimate the quotient digit from the top two words of the window.
137 * The window invariant gives u2 <= yn1; if u2 == yn1 the 2/1
138 * division precondition does not hold, and instead the digit
139 * estimate is the maximum word value.
140 */
141 const auto top_eq = CT::Mask<word>::is_equal(u2, yn1);
142 const word q_est = div_by_yn.divmod_2to1_ct(u2, u1).first;
143 word qhat = top_eq.select(WordInfo<word>::max, q_est);
144
145 // Per HAC 14.23, this correction is required at most twice
146 qhat -= division_check_ct(qhat, yn1, yn2, u2, u1, u0).if_set_return(1);
147 qhat -= division_check_ct(qhat, yn1, yn2, u2, u1, u0).if_set_return(1);
148
149 // Subtract qhat * yn from the window
150 const word bw = bigint_submul(&rw[j], yn.data(), y_words, qhat);
151 word borrow = 0;
152 rw[j + y_words] = word_sub(u2, bw, &borrow);
153
154 // If the digit was still one too large, the subtraction
155 // underflowed; add back and decrement the digit
156 const word cb = bigint_cnd_add(borrow, &rw[j], yn.data(), y_words);
157 rw[j + y_words] += cb;
158 qhat -= borrow;
159
160 qw[j] = qhat;
161 }
162
163 // The remainder is in rw[0:y_words], still shifted left by s, and
164 // rw[y_words] is zero
165 for(size_t i = 0; i != y_words; ++i) {
166 rw[i] = (rw[i] >> s) | s_mask.if_set_return(CT::value_barrier(rw[i + 1]) << s_comp);
167 }
168 }
169
171 rw.resize(y_words);
173
174 r_out = std::move(r);
175 q_out = std::move(q);
176}
177
178} // namespace
179
180void ct_divide(const BigInt& x, const BigInt& y, BigInt& q_out, BigInt& r_out) {
181 if(y.is_zero()) {
182 throw Invalid_Argument("ct_divide: cannot divide by zero");
183 }
184
185 BigInt q;
186 BigInt r;
187 ct_divide_impl(q, r, x, y);
188
189 sign_fixup(x, y, q, r);
190 r_out = std::move(r);
191 q_out = std::move(q);
192}
193
194BigInt ct_divide_pow2k(size_t k, const BigInt& y) {
195 BOTAN_ARG_CHECK(y.signum() != 0, "Cannot divide by zero");
196 BOTAN_ARG_CHECK(y.signum() >= 0, "Negative divisor not supported");
197 BOTAN_ARG_CHECK(k > 1, "Invalid k");
198
199 BigInt q;
200 BigInt r;
201 ct_divide_impl(q, r, BigInt::power_of_2(k), y);
202 return q;
203}
204
205void ct_divide_word(const BigInt& x, word y, BigInt& q_out, word& r_out) {
206 if(y == 0) {
207 throw Invalid_Argument("ct_divide_word: cannot divide by zero");
208 }
209
210 const size_t x_words = x.sig_words();
211
212 // The divisor is public here; setup is variable time in it
213 const auto div_y = divide_precomp<word>::setup_vartime(y);
214
215 secure_vector<word> qw(x_words);
216 word r = 0;
217
218 // Each step depends on r < y, which holds since r is a remainder mod y
219 for(size_t i = x_words; i > 0; --i) {
220 const auto [qi, ri] = div_y.divmod_2to1_vartime(r, x._data()[i - 1]);
221 qw[i - 1] = qi;
222 r = ri;
223 }
224
226
227 if(x.signum() < 0) {
228 q.flip_sign();
229 if(r != 0) {
230 --q;
231 r = y - r;
232 }
233 }
234
235 r_out = r;
236 q_out = std::move(q);
237}
238
240 BigInt q;
241 word r = 0;
242 ct_divide_word(x, y, q, r);
243 BOTAN_UNUSED(r);
244 return q;
245}
246
248 BOTAN_ARG_CHECK(x.signum() >= 0, "The argument x must be non-negative");
249 BOTAN_ARG_CHECK(y != 0, "Cannot divide by zero");
250
251 // The divisor is public here; setup is variable time in it
252 const auto div_y = divide_precomp<word>::setup_vartime(y);
253
254 word r = 0;
255 for(size_t i = x.sig_words(); i > 0; --i) {
256 r = div_y.mod_2to1(r, x._data()[i - 1]);
257 }
258
259 return r;
260}
261
262BigInt ct_modulo(const BigInt& x, const BigInt& y) {
263 if(y.signum() <= 0) {
264 throw Invalid_Argument("ct_modulo requires y > 0");
265 }
266
267 BigInt q;
268 BigInt r;
269 ct_divide_impl(q, r, x, y);
270
271 if(x.signum() < 0) {
272 if(r.signum() != 0) {
273 r = y - r;
274 }
275 }
276
277 return r;
278}
279
280} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:151
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
static BigInt zero()
Definition bigint.h:50
size_t sig_words() const
Definition bigint.h:687
static BigInt _from_words(secure_vector< word > &words)
Definition bigint.h:1052
void flip_sign()
Definition bigint.h:657
int signum() const
Definition bigint.h:493
static BigInt power_of_2(size_t n)
Definition bigint.h:906
const word * _data() const
Definition bigint.h:1033
bool is_zero() const
Definition bigint.h:510
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
static constexpr Mask< T > is_equal(T x, T y)
Definition ct_utils.h:447
static constexpr Mask< T > is_gt(T x, T y)
Definition ct_utils.h:463
static constexpr divide_precomp setup_vartime(W divisor)
Definition mp_core.h:687
static constexpr divide_precomp setup(W divisor)
Definition mp_core.h:695
constexpr T value_barrier(T x)
word ct_mod_word(const BigInt &x, word y)
Definition divide.cpp:247
constexpr auto word_sub(W x, W y, W *carry) -> W
Definition mp_asmi.h:355
constexpr auto bigint_submul(W z[], const W y[], size_t N, W q) -> W
Definition mp_core.h:443
constexpr auto word_madd2(W a, W b, W *c) -> W
Definition mp_asmi.h:111
BigInt ct_modulo(const BigInt &x, const BigInt &y)
Definition divide.cpp:262
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
Definition mp_core.h:49
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
Definition divide.cpp:180
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
Definition divide.cpp:205
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
Definition bit_ops.h:73
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
Definition divide.cpp:194
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.
Definition types.h:131