24#ifndef JAU_BIG_INT_OPS_HPP_
25#define JAU_BIG_INT_OPS_HPP_
45 #undef JAU_FORCE_MP_WORD_32_BITS
46 #if !defined( JAU_FORCE_MP_WORD_32_BITS )
59 #if defined(__SIZEOF_INT128__)
77 carry = c1 | (z < carry);
110 carry = c1 | (z > t0);
151 inline void mul64x64_128(
const uint64_t a,
const uint64_t b, uint64_t& lo, uint64_t& hi)
noexcept {
153 const uint128_t r =
static_cast<uint128_t
>(a) * b;
154 hi = (r >> 64) & 0xFFFFFFFFFFFFFFFFUL;
155 lo = (r ) & 0xFFFFFFFFFFFFFFFFUL;
162 constexpr const size_t HWORD_BITS = 32;
163 constexpr const uint32_t HWORD_MASK = 0xFFFFFFFFU;
165 const uint32_t a_hi = (a >> HWORD_BITS);
166 const uint32_t a_lo = (a & HWORD_MASK);
167 const uint32_t b_hi = (b >> HWORD_BITS);
168 const uint32_t b_lo = (b & HWORD_MASK);
170 uint64_t x0 =
static_cast<uint64_t
>(a_hi) * b_hi;
171 uint64_t x1 =
static_cast<uint64_t
>(a_lo) * b_hi;
172 uint64_t x2 =
static_cast<uint64_t
>(a_hi) * b_lo;
173 uint64_t x3 =
static_cast<uint64_t
>(a_lo) * b_lo;
176 x2 += x3 >> HWORD_BITS;
182 x0 +=
static_cast<uint64_t
>(
static_cast<bool>(x2 < x1)) << HWORD_BITS;
184 hi = x0 + (x2 >> HWORD_BITS);
185 lo = ((x2 & HWORD_MASK) << HWORD_BITS) + (x3 & HWORD_MASK);
285 assert(x_size >= y_size);
287 const size_t blocks = y_size - (y_size % 8);
289 for(
size_t i = 0; i != blocks; i += 8) {
292 for(
size_t i = blocks; i != y_size; ++i) {
295 for(
size_t i = y_size; i != x_size; ++i) {
308 const size_t blocks = y_size - (y_size % 8);
310 for(
size_t i = 0; i != blocks; i += 8) {
311 carry =
word8_add3(z + i, x + i, y + i, carry);
313 for(
size_t i = blocks; i != y_size; ++i) {
316 for(
size_t i = y_size; i != x_size; ++i) {
323 z[x_size > y_size ? x_size : y_size] +=
331 assert(x_size >= y_size);
333 const size_t blocks = y_size - (y_size % 8);
335 for(
size_t i = 0; i != blocks; i += 8) {
338 for(
size_t i = blocks; i != y_size; ++i) {
339 x[i] =
word_sub(x[i], y[i], borrow);
341 for(
size_t i = y_size; i != x_size; ++i) {
351 const size_t blocks = y_size - (y_size % 8);
353 for(
size_t i = 0; i != blocks; i += 8) {
356 for(
size_t i = blocks; i != y_size; ++i) {
357 x[i] =
word_sub(y[i], x[i], borrow);
366 assert(x_size >= y_size);
368 const size_t blocks = y_size - (y_size % 8);
370 for(
size_t i = 0; i != blocks; i += 8) {
371 borrow =
word8_sub3(z + i, x + i, y + i, borrow);
373 for(
size_t i = blocks; i != y_size; ++i) {
374 z[i] =
word_sub(x[i], y[i], borrow);
376 for(
size_t i = y_size; i != x_size; ++i) {
397 const int32_t relative_size =
bigint_cmp(x, x_size, y, y_size);
400 const bool need_swap = relative_size < 0;
409 y_size = std::min(x_size, y_size);
413 return relative_size;
420 const size_t blocks = x_size - (x_size % 8);
424 for(
size_t i = 0; i != blocks; i += 8) {
427 for(
size_t i = blocks; i != x_size; ++i) {
434 const size_t blocks = x_size - (x_size % 8);
438 for(
size_t i = 0; i != blocks; i += 8) {
441 for(
size_t i = blocks; i != x_size; ++i) {
447 inline void bigint_shl1(
mp_word_t x[],
size_t x_size,
size_t x_words,
size_t word_shift,
size_t bit_shift)
noexcept {
448 std::memmove(x + word_shift, x,
sizeof(
mp_word_t)*x_words);
449 std::memset(x, 0,
sizeof(
mp_word_t)*word_shift);
452 const size_t carry_shift = carry_mask.if_set_return(
mp_word_bits - bit_shift);
455 for(
size_t i = word_shift; i != x_size; ++i) {
457 x[i] = (w << bit_shift) | carry;
458 carry = carry_mask.if_set_return(w >> carry_shift);
463 const size_t top = x_size >= word_shift ? (x_size - word_shift) : 0;
466 std::memmove(x, x + word_shift,
sizeof(
mp_word_t)*top);
471 const size_t carry_shift = carry_mask.if_set_return(
mp_word_bits - bit_shift);
474 for(
size_t i = 0; i != top; ++i) {
476 x[top-i-1] = (w >> bit_shift) | carry;
477 carry = carry_mask.if_set_return(w << carry_shift);
482 std::memmove(y + word_shift, x,
sizeof(
mp_word_t)*x_size);
485 const size_t carry_shift = carry_mask.if_set_return(
mp_word_bits - bit_shift);
488 for(
size_t i = word_shift; i != x_size + word_shift + 1; ++i) {
490 y[i] = (w << bit_shift) | carry;
491 carry = carry_mask.if_set_return(w >> carry_shift);
495 const size_t new_size = x_size < word_shift ? 0 : (x_size - word_shift);
498 std::memmove(y, x + word_shift,
sizeof(
mp_word_t)*new_size);
501 const size_t carry_shift = carry_mask.if_set_return(
mp_word_bits - bit_shift);
504 for(
size_t i = new_size; i > 0; --i) {
506 y[i-1] = (w >> bit_shift) | carry;
507 carry = carry_mask.if_set_return(w << carry_shift);
516 const mp_word_t y[],
size_t y_size)
noexcept
518 assert(z_size >= x_size + y_size);
520 const size_t x_size_8 = x_size - (x_size % 8);
522 for(
size_t i=0; i<z_size; ++i) { z[i]=0; }
524 for(
size_t i = 0; i != y_size; ++i) {
529 for(
size_t j = 0; j != x_size_8; j += 8) {
532 for(
size_t j = x_size_8; j != x_size; ++j) {
533 z[i+j] =
word_madd3(x[j], y_i, z[i+j], carry);
557 if(high_top_bit || high >= d) {
583 const size_t common_elems = std::min(x_size, y_size);
586 for(
size_t i = 0; i != common_elems; i++) {
587 diff |= (x[i] ^ y[i]);
593 for(
size_t i = x_size; i != y_size; i++) {
596 }
else if(y_size < x_size) {
597 for(
size_t i = y_size; i != x_size; i++) {
612 const size_t common_elems =
jau::min(x_size, y_size);
616 for(
size_t i = 0; i != common_elems; i++)
620 is_lt = eq.select_mask(is_lt, lt);
623 if(x_size < y_size) {
625 for(
size_t i = x_size; i != y_size; i++) {
630 }
else if(y_size < x_size) {
632 for(
size_t i = y_size; i != x_size; i++) {
656 const size_t common_elems =
jau::min(x_size, y_size);
660 for(
size_t i = 0; i != common_elems; i++) {
663 result = is_eq.select(result, is_lt.select(LT, GT));
665 if(x_size < y_size) {
667 for(
size_t i = x_size; i != y_size; i++) {
672 }
else if(y_size < x_size) {
674 for(
size_t i = y_size; i != x_size; i++) {
681 return static_cast<int>(result);
A Mask type used for constant-time operations.
static Mask< T > is_equal(T x, T y) noexcept
Return a Mask<T> which is set if x == y.
static Mask< T > expand(T v) noexcept
Return a Mask<T> which is set if v is != 0.
static Mask< T > is_zero(T x) noexcept
Return a Mask<T> which is set if v is == 0 or cleared otherwise.
static Mask< T > is_lt(T x, T y) noexcept
Return a Mask<T> which is set if x < y.
math_error_t::div_by_zero, i.e.
consteval_cxx20 bool is_builtin_int128_available() noexcept
constexpr T min(const T x, const T y) noexcept
Returns the minimum of two integrals (w/ branching) in O(1)
constexpr size_t pointer_bit_size() noexcept
Returns the compile time pointer architecture size in bits.
void unpoison(const T *p, size_t n)
void conditional_swap(bool cnd, T &x, T &y) noexcept
void conditional_swap_ptr(bool cnd, T &x, T &y) noexcept
constexpr size_t best_word_byte_size()
mp_word_t word8_madd3(mp_word_t z[8], const mp_word_t x[8], mp_word_t y, mp_word_t carry) noexcept
mp_word_t word8_sub2(mp_word_t x[8], const mp_word_t y[8], mp_word_t carry) noexcept
CT::Mask< mp_word_t > bigint_ct_is_lt(const mp_word_t x[], size_t x_size, const mp_word_t y[], size_t y_size, bool lt_or_equal=false) noexcept
Compare x and y Return ~0 if x[0:x_size] < y[0:y_size] or 0 otherwise If lt_or_equal is true,...
CT::Mask< mp_word_t > bigint_ct_is_eq(const mp_word_t x[], size_t x_size, const mp_word_t y[], size_t y_size) noexcept
mp_word_t word8_sub2_rev(mp_word_t x[8], const mp_word_t y[8], mp_word_t carry) noexcept
int bigint_cmp(const mp_word_t x[], size_t x_size, const mp_word_t y[], size_t y_size) noexcept
Compare unsigned x and y mp_word_t.
mp_word_t bigint_divop(mp_word_t n1, mp_word_t n0, mp_word_t d)
Computes ((n1<<bits) + n0) / d.
int32_t bigint_sub_abs(mp_word_t z[], const mp_word_t x[], size_t x_size, const mp_word_t y[], size_t y_size) noexcept
Set z to abs(x-y), ie if x >= y, then compute z = x - y Otherwise compute z = y - x No borrow is poss...
mp_word_t bigint_add2(mp_word_t x[], size_t x_size, const mp_word_t y[], size_t y_size) noexcept
Two operand addition with carry out.
mp_word_t word8_linmul3(mp_word_t z[8], const mp_word_t x[8], mp_word_t y, mp_word_t carry) noexcept
mp_word_t word_sub(mp_word_t x, mp_word_t y, mp_word_t &carry) noexcept
mp_word_t word8_sub3(mp_word_t z[8], const mp_word_t x[8], const mp_word_t y[8], mp_word_t carry) noexcept
void bigint_shr1(mp_word_t x[], size_t x_size, size_t word_shift, size_t bit_shift) noexcept
mp_word_t bigint_linmul2(mp_word_t x[], size_t x_size, mp_word_t y) noexcept
void bigint_linmul3(mp_word_t z[], const mp_word_t x[], size_t x_size, mp_word_t y) noexcept
mp_word_t bigint_sub3(mp_word_t z[], const mp_word_t x[], size_t x_size, const mp_word_t y[], size_t y_size) noexcept
Three operand subtraction.
mp_word_t bigint_add3_nc(mp_word_t z[], const mp_word_t x[], size_t x_size, const mp_word_t y[], size_t y_size) noexcept
Three operand addition with carry out.
void bigint_shl2(mp_word_t y[], const mp_word_t x[], size_t x_size, size_t word_shift, size_t bit_shift) noexcept
void bigint_add3(mp_word_t z[], const mp_word_t x[], size_t x_size, const mp_word_t y[], size_t y_size) noexcept
Three operand addition.
mp_word_t bigint_sub2(mp_word_t x[], size_t x_size, const mp_word_t y[], size_t y_size) noexcept
Two operand subtraction.
void mul64x64_128(const uint64_t a, const uint64_t b, uint64_t &lo, uint64_t &hi) noexcept
64x64->128 bit multiplication
mp_word_t word8_linmul2(mp_word_t x[8], mp_word_t y, mp_word_t carry) noexcept
mp_word_t word8_add3(mp_word_t z[8], const mp_word_t x[8], const mp_word_t y[8], mp_word_t carry) noexcept
mp_word_t bigint_modop(mp_word_t n1, mp_word_t n0, mp_word_t d)
Compute ((n1<<bits) + n0) % d.
mp_word_t word_madd3(mp_word_t a, mp_word_t b, mp_word_t c, mp_word_t &d) noexcept
Word Multiply/Add.
mp_word_t word_madd2(mp_word_t a, mp_word_t b, mp_word_t &c) noexcept
Word Multiply/Add.
void bigint_shl1(mp_word_t x[], size_t x_size, size_t x_words, size_t word_shift, size_t bit_shift) noexcept
void basecase_mul(mp_word_t z[], size_t z_size, const mp_word_t x[], size_t x_size, const mp_word_t y[], size_t y_size) noexcept
mp_word_t word8_add2(mp_word_t x[8], const mp_word_t y[8], mp_word_t carry) noexcept
void bigint_shr2(mp_word_t y[], const mp_word_t x[], size_t x_size, size_t word_shift, size_t bit_shift) noexcept
mp_word_t word_add(const mp_word_t x, const mp_word_t y, mp_word_t &carry) noexcept
void bigint_sub2_rev(mp_word_t x[], const mp_word_t y[], size_t y_size) noexcept
Two operand subtraction, x = y - x; assumes y >= x.
big_int_t (this file) (c) 2024 Gothel Software e.K.
constexpr const bool has_mp_dword
jau::uint_bytes< impl::best_word_byte_size()>::type mp_word_t
constexpr const size_t mp_word_bits
jau::uint_bytes< impl::best_word_byte_size() *2 >::type mp_dword_t
constexpr const mp_word_t mp_word_max