8#include <botan/internal/divide.h>
10#include <botan/internal/bit_ops.h>
11#include <botan/internal/ct_utils.h>
12#include <botan/internal/mp_core.h>
21void 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()) {
30inline bool division_check(word q, word y2, word y1, word x3, word x2, word x1) {
40 const word x[3] = {x1, x2, x3};
41 const word y[3] = {y1, y2, y3};
56 const size_t x_bits = x.
bits();
62 for(
size_t i = 0; i != x_bits; ++i) {
63 const size_t b = x_bits - 1 - i;
75 sign_fixup(x, y, q, r);
85 const size_t x_bits = k + 1;
86 const size_t y_bits = y.
bits();
101 for(
size_t i = y_bits - 1; i != x_bits; ++i) {
102 const size_t b = x_bits - 1 - i;
126 const size_t x_bits = x.
bits();
131 for(
size_t i = 0; i != x_bits; ++i) {
132 const size_t b = x_bits - 1 - i;
142 r = r_gte_y.select(r - y, r);
161 const size_t x_bits = x.
bits();
165 for(
size_t i = 0; i != x_bits; ++i) {
166 const size_t b = x_bits - 1 - i;
175 r = r_gte_y.select(r - y, r);
188 const size_t x_bits = x.
bits();
193 for(
size_t i = 0; i != x_bits; ++i) {
194 const size_t b = x_bits - 1 - i;
224 const size_t y_words = y_arg.
sig_words();
244 const size_t t = y_words - 1;
245 const size_t n = std::max(y_words, r.
sig_words()) - 1;
258 const word y_t0 = y.
word_at(t);
259 const word y_t1 = y.
word_at(t - 1);
262 for(
size_t j = n; j != t; --j) {
263 const word x_j0 = r.
word_at(j);
264 const word x_j1 = r.
word_at(j - 1);
265 const word x_j2 = r.
word_at(j - 2);
272 qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
273 qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
280 r -= qjt * shifted_y;
282 r +=
static_cast<word
>(r.
is_negative()) * shifted_y;
284 q_words[j - t - 1] = qjt;
289 sign_fixup(x, y_arg, q, r);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_DEBUG_ASSERT(expr)
#define BOTAN_ARG_CHECK(expr, msg)
void conditionally_set_bit(size_t n, bool set_it)
void grow_to(size_t n) const
size_t top_bits_free() const
word word_at(size_t n) const
const word * _data() 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 constexpr Mask< T > is_gte(T x, T y)
static constexpr Mask< T > expand_top_bit(T v)
static constexpr Mask< T > is_equal(T x, T y)
#define BOTAN_MP_WORD_BITS
constexpr void bigint_cnd_swap(W cnd, W x[], W y[], size_t size)
void vartime_divide(const BigInt &x, const BigInt &y_arg, BigInt &q_out, BigInt &r_out)
word ct_mod_word(const BigInt &x, word y)
constexpr auto word_madd2(W a, W b, W *c) -> W
constexpr auto bigint_sub3(W z[], const W x[], size_t x_size, const W y[], size_t y_size) -> W
constexpr void bigint_shl1(W x[], size_t x_size, size_t x_words, size_t shift)
BigInt ct_modulo(const BigInt &x, const BigInt &y)
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)
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
constexpr auto bigint_ct_is_lt(const W x[], size_t x_size, const W y[], size_t y_size, bool lt_or_equal=false) -> CT::Mask< W >
std::vector< T, secure_allocator< T > > secure_vector
constexpr auto bigint_divop_vartime(W n1, W n0, W d) -> W