8#include <botan/internal/divide.h>
9#include <botan/internal/mp_core.h>
10#include <botan/internal/ct_utils.h>
11#include <botan/internal/bit_ops.h>
20void sign_fixup(
const BigInt& x,
const BigInt&
y, BigInt& q, BigInt& r)
22 q.cond_flip_sign(x.sign() !=
y.sign());
24 if(x.is_negative() && r.is_nonzero())
31inline bool division_check(word q, word y2, word y1,
32 word x3, word x2, word x1)
43 const word x[3] = { x1, x2, x3 };
44 const word
y[3] = { y1, y2, y3 };
57 const size_t y_words =
y.sig_words();
59 const size_t x_bits = x.
bits();
65 for(
size_t i = 0; i != x_bits; ++i)
67 const size_t b = x_bits - 1 - i;
79 sign_fixup(x,
y, q, r);
90 const size_t x_bits = x.
bits();
95 for(
size_t i = 0; i != x_bits; ++i)
97 const size_t b = x_bits - 1 - i;
107 r = r_gte_y.select(r -
y, r);
126 if(
y.is_negative() ||
y.is_zero())
129 const size_t y_words =
y.sig_words();
131 const size_t x_bits = x.
bits();
136 for(
size_t i = 0; i != x_bits; ++i)
138 const size_t b = x_bits - 1 - i;
170 const size_t y_words = y_arg.
sig_words();
184 const size_t shifts =
y.top_bits_free();
190 const size_t t = y_words - 1;
191 const size_t n = std::max(y_words, r.
sig_words()) - 1;
204 const word y_t0 =
y.word_at(t);
205 const word y_t1 =
y.word_at(t-1);
208 for(
size_t j = n; j != t; --j)
210 const word x_j0 = r.
word_at(j);
211 const word x_j1 = r.
word_at(j-1);
212 const word x_j2 = r.
word_at(j-2);
219 qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
220 qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
227 r -= qjt * shifted_y;
229 r +=
static_cast<word
>(r.
is_negative()) * shifted_y;
231 q_words[j-t-1] = qjt;
236 sign_fixup(x, y_arg, q, r);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
void conditionally_set_bit(size_t n, bool set_it)
void grow_to(size_t n) const
const word * data() const
word word_at(size_t n) const
void ct_cond_swap(bool predicate, BigInt &other)
size_t reduce_below(const BigInt &mod, secure_vector< word > &ws)
bool get_bit(size_t n) const
static BigInt with_capacity(size_t n)
static Mask< T > is_equal(T x, T y)
static Mask< T > expand(T v)
static Mask< T > is_gte(T x, T y)
#define BOTAN_MP_WORD_BITS
word bigint_divop(word n1, word n0, word d)
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
BigInt ct_modulo(const BigInt &x, const BigInt &y)
CT::Mask< word > bigint_ct_is_lt(const word x[], size_t x_size, const word y[], size_t y_size, bool lt_or_equal=false)
void ct_divide(const BigInt &x, const BigInt &y, BigInt &q_out, BigInt &r_out)
void ct_divide_word(const BigInt &x, word y, BigInt &q_out, word &r_out)
word word_madd2(word a, word b, word *c)
std::vector< T, secure_allocator< T > > secure_vector
word bigint_sub3(word z[], const word x[], size_t x_size, const word y[], size_t y_size)