8#include <botan/internal/divide.h>
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>
23 q.cond_flip_sign(x.sign() != y.sign());
25 if(x.signum() < 0 && r.signum() != 0) {
50 return gt3 | (eq3 & (gt2 | (eq2 & gt1)));
69 const size_t x_words = x.sig_words();
70 const size_t y_words = y.sig_words();
73 if(x_words < y_words) {
80 const size_t r_words = x_words + 1;
81 const size_t q_words = x_words - y_words + 1;
86 const word s_comp = s_mask.if_set_return(
static_cast<word>(WB) - s);
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);
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);
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]);
125 const word yn1 = yn[y_words - 1];
126 const word yn2 = yn[y_words - 2];
128 for(
size_t i = q_words; i > 0; --i) {
129 const size_t j = i - 1;
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];
142 const word q_est = div_by_yn.divmod_2to1_ct(u2, u1).first;
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);
152 rw[j + y_words] =
word_sub(u2, bw, &borrow);
157 rw[j + y_words] += cb;
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);
174 r_out = std::move(r);
175 q_out = std::move(q);
187 ct_divide_impl(q, r, x, y);
189 sign_fixup(x, y, q, r);
190 r_out = std::move(r);
191 q_out = std::move(q);
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]);
236 q_out = std::move(q);
255 for(
size_t i = x.
sig_words(); i > 0; --i) {
256 r = div_y.mod_2to1(r, x.
_data()[i - 1]);
269 ct_divide_impl(q, r, x, y);
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_ARG_CHECK(expr, msg)
static BigInt _from_words(secure_vector< word > &words)
static BigInt power_of_2(size_t n)
const word * _data() const
static constexpr Mask< T > expand(T v)
static constexpr Mask< T > is_equal(T x, T y)
static constexpr Mask< T > is_gt(T x, T y)
static constexpr divide_precomp setup_vartime(W divisor)
static constexpr divide_precomp setup(W divisor)
constexpr T value_barrier(T x)
word ct_mod_word(const BigInt &x, word y)
constexpr auto word_sub(W x, W y, W *carry) -> W
constexpr auto bigint_submul(W z[], const W y[], size_t N, W q) -> W
constexpr auto word_madd2(W a, W b, W *c) -> W
BigInt ct_modulo(const BigInt &x, const BigInt &y)
constexpr W bigint_cnd_add(W cnd, W x[], const W y[], size_t size)
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)
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
BigInt ct_divide_pow2k(size_t k, const BigInt &y)
std::vector< T, secure_allocator< T > > secure_vector
std::conditional_t< HasNative64BitRegisters, std::uint64_t, uint32_t > word
The native machine word, used as the limb type for multiprecision integers.