22#ifndef JAU_BIG_INT_HPP_
23#define JAU_BIG_INT_HPP_
82 bn.set_word_at(1,
static_cast<mp_word_t>(n >> 32));
83 bn.set_word_at(0,
static_cast<mp_word_t>(n));
137 m_data.set_word_at(0, n);
139 m_data.set_word_at(1,
static_cast<mp_word_t>(n >> 32));
140 m_data.set_word_at(0,
static_cast<mp_word_t>(n));
155 if(str.length() > 0 && str[0] ==
'-')
161 if(str.length() > markers + 2 && str[markers ] ==
'0' &&
162 str[markers + 1] ==
'x')
185 binary_decode(buf, byte_len, byte_order);
188 BigInt(std::vector<mp_word_t>&& other_reg)
noexcept {
189 this->swap_reg(other_reg);
210 m_data.swap(other.m_data);
211 std::swap(m_signedness, other.m_signedness);
215 void swap_reg(std::vector<mp_word_t>& reg)
noexcept {
239 return m_data.get_word_at(n);
304 size_t size() const noexcept {
return m_data.size(); }
310 size_t sig_words() const noexcept {
return m_data.sig_words(); }
323 return full_words + top_bits;
397 m_data.set_word_at(which,
word_at(which) | mask);
425 return add(y.data(), y.sig_words(), y.sign());
433 return add2(*
this, y.data(), y.sig_words(), y.sign());
437 return add2(*
this, y.data(), y.sig_words(), y.reverse_sign());
445 const size_t bits_free = top_bits_free();
447 const size_t new_size =
size + shift_words + (bits_free < shift_bits);
449 m_data.grow_to(new_size);
460 ops::bigint_shr1(m_data.mutable_data(), m_data.size(), shift_words, shift_bits);
484 if(shift_words >= x_sw) {
501 std::vector<mp_word_t> ws;
502 return this->mul(y, ws);
508 const size_t y_sw = y.sig_words();
511 z.resize(
size() + y.size());
513 if(x_sw == 1 && y_sw) {
515 }
else if(y_sw == 1 && x_sw) {
517 }
else if(x_sw && y_sw) {
520 z.cond_flip_sign(x_sw > 0 && y_sw > 0 &&
sign() != y.sign());
526 (*this) >>= (y.
bits() - 1);
528 (*this) = (*this) / y;
538 vartime_divide(*
this, y, q, r);
546 return (*
this = (*
this) % mod);
563 vartime_divide(*
this, mod, q, r);
689 mp_word_t conversion_radix, radix_digits;
691 conversion_radix = 10000000000000000000U;
694 conversion_radix = 1000000000U;
699 const size_t digit_estimate =
static_cast<size_t>(1 + (
static_cast<double>(this->
bits()) / 3.32));
702 const size_t digit_blocks = (digit_estimate + radix_digits - 1) / radix_digits;
708 std::vector<mp_word_t> digit_groups(digit_blocks);
710 for(
size_t i = 0; i != digit_blocks; ++i) {
712 ct_divide_word(
value, conversion_radix,
value, remainder);
713 digit_groups[i] = remainder;
715 assert(
value.is_zero());
718 std::vector<uint8_t> digits(digit_blocks * radix_digits);
720 for(
size_t i = 0; i != digit_blocks; ++i) {
722 for(
size_t j = 0; j != radix_digits; ++j)
727 digits[radix_digits*i + j] =
static_cast<uint8_t
>(digit);
732 while(!digits.empty() && digits.back() == 0) {
736 assert(digit_estimate >= digits.size());
740 s.reserve(1 + digits.size());
747 for(uint8_t d : digits) {
748 s.push_back(
static_cast<char>(d +
'0'));
761 std::vector<uint8_t>
bits;
768 data_len =
bits.size();
770 data =
reinterpret_cast<const uint8_t*
>(m_data.const_data());
791 : m_reg(), m_sig_words(sig_words_npos) {}
793 data_t(
const data_t& o)
noexcept =
default;
795 data_t(data_t&& o)
noexcept {
798 data_t(std::vector<mp_word_t>&& reg)
noexcept {
802 ~data_t() noexcept = default;
804 data_t& operator=(const data_t& r) noexcept = default;
806 data_t& operator=(data_t&& other) noexcept {
812 data_t& operator=(std::vector<mp_word_t>&& other_reg)
noexcept {
813 if(&m_reg != &other_reg) {
814 this->swap(other_reg);
820 invalidate_sig_words();
824 const mp_word_t* const_data() const noexcept {
828 std::vector<mp_word_t>& mutable_vector() noexcept {
829 invalidate_sig_words();
833 const std::vector<mp_word_t>& const_vector() const noexcept {
837 mp_word_t get_word_at(
size_t n)
const noexcept {
838 if(n < m_reg.size()) {
844 void set_word_at(
size_t i,
mp_word_t w) {
845 invalidate_sig_words();
846 if(i >= m_reg.size()) {
855 void set_words(
const mp_word_t w[],
size_t len) {
856 invalidate_sig_words();
857 m_reg.assign(w, w + len);
861 m_reg.resize(m_reg.capacity());
862 clear_mem(m_reg.data(), m_reg.size());
866 void set_size(
size_t s) {
867 invalidate_sig_words();
868 clear_mem(m_reg.data(), m_reg.size());
869 m_reg.resize(s + (8 - (s % 8)));
872 void mask_bits(
size_t n)
noexcept {
873 if(n == 0) {
return set_to_zero(); }
878 if(top_word < size())
881 const size_t len = size() - (top_word + 1);
884 clear_mem(&m_reg[top_word+1], len);
886 m_reg[top_word] &= mask;
887 invalidate_sig_words();
891 void grow_to(
size_t n)
const {
893 if(n <= m_reg.capacity()) {
896 m_reg.resize(n + (8 - (n % 8)));
901 size_t size() const noexcept {
return m_reg.size(); }
903 void shrink_to_fit(
size_t min_size = 0) {
904 const size_t words = std::max(min_size, sig_words());
908 void resize(
size_t s) {
912 void swap(data_t& other)
noexcept {
913 m_reg.swap(other.m_reg);
914 std::swap(m_sig_words, other.m_sig_words);
917 void swap(std::vector<mp_word_t>& reg)
noexcept {
919 invalidate_sig_words();
922 void invalidate_sig_words() const noexcept {
923 m_sig_words = sig_words_npos;
926 size_t sig_words() const noexcept {
927 if(m_sig_words == sig_words_npos) {
928 m_sig_words = calc_sig_words();
930 assert(m_sig_words == calc_sig_words());
935 static const size_t sig_words_npos =
static_cast<size_t>(-1);
937 size_t calc_sig_words() const noexcept {
938 const size_t sz = m_reg.size();
943 for(
size_t i = 0; i != sz; ++i)
959 mutable std::vector<mp_word_t> m_reg;
960 mutable size_t m_sig_words = sig_words_npos;
971 template<
typename T>
static constexpr uint8_t get_byte_var_be(
size_t byte_num, T input)
noexcept {
972 return static_cast<uint8_t
>( input >> (((~byte_num)&(
sizeof(T)-1)) << 3) );
980 template<
typename T>
static constexpr uint8_t get_byte_var_le(
size_t byte_num, T input)
noexcept {
981 return static_cast<uint8_t
>( input >> ( byte_num << 3 ) );
992 static constexpr void clear_bytes(
void* ptr,
size_t bytes)
noexcept {
994 std::memset(ptr, 0,
bytes);
1008 template<
typename T>
static constexpr void clear_mem(T* ptr,
size_t n)
noexcept {
1009 clear_bytes(ptr,
sizeof(T)*n);
1016 void grow_to(
size_t n)
const { m_data.grow_to(n); }
1018 void resize(
size_t s) { m_data.resize(s); }
1020 void set_word_at(
size_t i,
mp_word_t w) {
1021 m_data.set_word_at(i, w);
1024 void set_words(
const mp_word_t w[],
size_t len) {
1025 m_data.set_words(w, len);
1031 mp_word_t* mutable_data() {
return m_data.mutable_data(); }
1039 void binary_decode(
const uint8_t buf[],
size_t byte_len,
const lb_endian_t byte_order) {
1040 const size_t full_words = byte_len /
sizeof(
mp_word_t);
1041 const size_t extra_bytes = byte_len %
sizeof(
mp_word_t);
1045 m_data.set_size(
jau::round_up(full_words + (extra_bytes > 0 ? 1U : 0U), 8U) );
1047 mp_word_t* sink = m_data.mutable_data();
1050 for(
size_t i = 0; i < full_words; ++i) {
1055 for(
size_t i = 0; i < full_words; ++i) {
1061 for(
size_t i = 0; i < extra_bytes; ++i) {
1065 for(
size_t i = 0; i < extra_bytes; ++i) {
1066 le_w = (le_w << 8) |
mp_word_t( buf[i] );
1078 static BigInt hex_decode(
const uint8_t buf[],
size_t str_len,
const lb_endian_t byte_order) {
1081 std::vector<uint8_t> bin_out;
1082 const size_t exp_blen = str_len / 2 + str_len % 2;
1084 if( exp_blen != blen ) {
1085 throw jau::math::MathDomainError(
"invalid hexadecimal char @ "+std::to_string(blen)+
"/"+std::to_string(exp_blen)+
" of '"+
1092 static BigInt dec_decode(
const uint8_t buf[],
size_t str_len) {
1096 for(
size_t i = 0; i < str_len; ++i) {
1097 const char c =
static_cast<char>(buf[i]);
1099 if(c <
'0' || c >
'9') {
1100 throw jau::math::MathDomainError(
"invalid decimal char",
E_FILE_LINE);
1102 const uint8_t x = c -
'0';
1126 const size_t full_words = byte_len /
sizeof(
mp_word_t);
1127 const size_t extra_bytes = byte_len %
sizeof(
mp_word_t);
1131 for(
size_t i = 0; i < full_words; ++i) {
1136 for(
size_t i = 0; i < full_words; ++i) {
1140 if(extra_bytes > 0) {
1143 for(
size_t i = 0; i < extra_bytes; ++i) {
1144 output[full_words*
sizeof(
mp_word_t) + i] = get_byte_var_le(i, le_w);
1147 for(
size_t i = 0; i < extra_bytes; ++i) {
1148 output[extra_bytes-1-i] = get_byte_var_le(i, le_w);
1152 return extra_bytes + full_words *
sizeof(
mp_word_t);
1156 size_t top_bits_free() const noexcept {
1172 int cmp(
const BigInt& other,
bool check_signs =
true) const noexcept {
1174 if(other.is_positive() && this->is_negative()) {
1177 if(other.is_negative() && this->is_positive()) {
1180 if(other.is_negative() && this->is_negative()) {
1182 other.data(), other.size()));
1186 other.data(), other.size());
1189 bool is_equal(
const BigInt& other)
const noexcept {
1190 if(this->
sign() != other.sign()) {
1194 other.data(), other.sig_words()).is_set();
1197 bool is_less_than(
const BigInt& other)
const noexcept {
1204 if(other.is_negative() && this->is_negative()) {
1206 this->data(), this->sig_words()).is_set();
1209 other.data(), other.sig_words()).is_set();
1214 grow_to(std::max(x_sw, y_words) + 1);
1216 if(
sign() == y_sign)
1222 if(relative_size >= 0)
1231 if(relative_size < 0) {
1233 }
else if(relative_size == 0) {
1248 const size_t x_sw = x.sig_words();
1252 if(x.sign() == y_sign) {
1254 z.set_sign(x.sign());
1256 const int32_t relative_size =
ops::bigint_sub_abs(
z.mutable_data(), x.data(), x_sw, y, y_words);
1259 if(relative_size < 0) {
1261 }
else if(relative_size == 0) {
1264 z.set_sign(x.sign());
1270 BigInt& mul(
const BigInt& y, std::vector<mp_word_t>& ws)
noexcept {
1272 const size_t y_sw = y.sig_words();
1275 if(x_sw == 0 || y_sw == 0)
1280 else if(x_sw == 1 && y_sw)
1285 else if(y_sw == 1 && x_sw)
1288 set_word_at(x_sw, carry);
1292 const size_t new_size = x_sw + y_sw + 1;
1295 std::vector<mp_word_t> z_reg(new_size);
1299 this->swap_reg(z_reg);
1316 void cond_flip_sign(
bool predicate)
noexcept {
1319 const uint8_t current_sign =
static_cast<uint8_t
>(
sign());
1320 const uint8_t new_sign = mask.select(current_sign ^ 1, current_sign);
1331 inline size_t reduce_below(
const BigInt& p, std::vector<mp_word_t>& ws) {
1332 if(p.is_negative() || this->is_negative()) {
1334 if( p.is_negative() ) {
1335 msg.append(
"p < 0");
1338 if( msg.length() > 0 ) {
1339 msg.append(
" and ");
1341 msg.append(
"*this < 0");
1343 throw jau::math::MathDomainError(msg,
E_FILE_LINE);
1345 const size_t p_words = p.sig_words();
1347 if(
size() < p_words + 1) {
1348 grow_to(p_words + 1);
1350 if(ws.size() < p_words + 1) {
1351 ws.resize(p_words + 1);
1353 clear_mem(ws.data(), ws.size());
1355 size_t reductions = 0;
1370 q.cond_flip_sign(x.sign() != y.sign());
1372 if(x.is_negative() && r.is_nonzero())
1402 if( y_arg.is_zero() ) {
1403 throw jau::math::MathDivByZeroError(
"y_arg == 0",
E_FILE_LINE);
1405 const size_t y_words = y_arg.sig_words();
1407 assert(y_words > 0);
1413 std::vector<mp_word_t> ws;
1419 const size_t shifts = y.top_bits_free();
1425 const size_t t = y_words - 1;
1426 const size_t n = std::max(y_words, r.sig_words()) - 1;
1429 q.grow_to(n - t + 1);
1436 q_words[n-
t] = r.reduce_below(shifted_y, ws);
1442 for(
size_t j = n;
j !=
t; --
j) {
1452 qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
1453 qjt -= division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2);
1454 assert(division_check(qjt, y_t0, y_t1, x_j0, x_j1, x_j2) ==
false);
1460 r -= shifted_y * qjt;
1461 qjt -= r.is_negative();
1462 r += shifted_y *
static_cast<mp_word_t>(r.is_negative());
1464 q_words[
j-
t-1] = qjt;
1469 sign_fixup(x, y_arg, q, r);
1477 throw jau::math::MathDivByZeroError(
"y == 0",
E_FILE_LINE);
1481 ct_divide_word(*
this, y, q, r);
1487 throw jau::math::MathDivByZeroError(
"y == 0",
E_FILE_LINE);
1489 const size_t x_words = x.sig_words();
1490 const size_t x_bits = x.bits();
1495 for(
size_t i = 0; i != x_bits; ++i)
1497 const size_t b = x_bits - 1 - i;
1498 const bool x_b = x.get_bit(b);
1506 q.conditionally_set_bit(b, r_gte_y.is_set());
1507 r = r_gte_y.select(r - y, r);
1510 if(x.is_negative()) {
1524 throw jau::math::MathDivByZeroError(
"mod == 0",
E_FILE_LINE);
1532 remainder = (
word_at(0) & (mod - 1));
1535 for(
size_t i = sw; i > 0; --i) {
1540 return mod - remainder;
1545 void append_detail(std::string& s)
const noexcept {
1546 s.append(
", bits ").append(std::to_string(
bits())).append(
", ").append(std::to_string(
sig_words())).append(
" word(s): ");
1569 return x < y ? x : y;
1572 return x > y ? x : y;
1575 return min(
max(x, min_val), max_val);
1579 return x < y ? x : y;
1582 return x > y ? x : y;
1585 return min(
max(x, min_val), max_val);
static Mask< T > is_gte(T x, T y) noexcept
Return a Mask<T> which is set if x >= y.
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.
math_error_t::div_by_zero, i.e.
Arbitrary precision integer type.
BigInt & set_sign(sign_t sign) noexcept
Set sign of the integer.
BigInt(uint64_t n)
Create big_int_t from an unsigned 64 bit integer.
bool is_even() const noexcept
Test if the integer has an even value.
size_t bits() const noexcept
Returns bit length of this integer.
std::string to_dec_string(bool add_details=false) const
bool operator==(const BigInt &b) const noexcept
bool is_odd() const noexcept
Test if the integer has an odd value.
bool get_bit(size_t n) const noexcept
Return bit value at specified position.
BigInt & operator-=(const BigInt &y) noexcept
BigInt abs() const noexcept
Returns absolute (positive) value of this instance.
BigInt & operator++() noexcept
std::strong_ordering operator<=>(const BigInt& b) const noexcept { const int r = cmp(b); return 0 == ...
BigInt operator-() const noexcept
Unary negation operator, returns new negative instance of this.
BigInt & mod_add(const BigInt &y, const BigInt &mod, std::vector< mp_word_t > &ws)
Set *this to (*this + y) % mod This function assumes *this is >= 0 && < mod.
BigInt pow(BigInt e)
Returns (*this)^e, or pow(*this, e)
BigInt & operator--() noexcept
size_t bytes() const
Returns byte length of this integer.
BigInt & operator<<=(size_t shift) noexcept
BigInt(const uint8_t buf[], size_t byte_len, const lb_endian_t byte_order)
Create a big_int_t from an integer in a byte array with given byte_len, considering the given byte_or...
BigInt & operator=(const BigInt &r)=default
BigInt operator>>(size_t shift) const
std::string to_hex_string(bool add_details=false) const noexcept
BigInt operator--(int) noexcept
sign_t reverse_sign() const noexcept
bool operator<=(const BigInt &b) const noexcept
BigInt operator+(const BigInt &y) const noexcept
sign_t
Sign symbol definitions for positive and negative numbers.
BigInt operator%(const BigInt &mod)
bool operator>(const BigInt &b) const noexcept
const mp_word_t * data() const
Return a const pointer to the register.
bool is_nonzero() const noexcept
Test if the integer is not zero.
size_t size() const noexcept
Give size of internal register.
static BigInt one()
Create a 1-value big_int.
sign_t sign() const noexcept
Return the sign of the integer.
bool is_negative() const noexcept
Tests if the sign of the integer is negative.
BigInt & operator>>=(size_t shift) noexcept
BigInt & rev_sub(const BigInt &y, std::vector< mp_word_t > &ws)
Set *this to y - *this.
BigInt & operator=(BigInt &&other) noexcept
static BigInt zero()
Create a 0-value big_int.
void conditionally_set_bit(size_t n, bool set_it) noexcept
Conditionally set bit at specified position.
size_t sig_words() const noexcept
Return how many words we need to hold this value.
void clear()
Zeroize the big_int.
BigInt(std::vector< mp_word_t > &&other_reg) noexcept
BigInt() noexcept=default
BigInt & operator%=(const BigInt &mod)
Modulo operator.
bool operator!() const noexcept
!
BigInt & mod_sub(const BigInt &y, const BigInt &mod, std::vector< mp_word_t > &ws)
Set *this to (*this - y) % mod This function assumes *this is >= 0 && < mod.
bool is_positive() const noexcept
Tests if the sign of the integer is positive.
bool operator<(const BigInt &b) const noexcept
bool operator!=(const BigInt &b) const noexcept
bool operator>=(const BigInt &b) const noexcept
size_t binary_encode(uint8_t output[], size_t byte_len, const lb_endian_t byte_order) const noexcept
Stores this number to the value in buf with given byte_len, considering the given byte_order.
void swap(BigInt &other) noexcept
Swap this value with another.
int compare(const BigInt &b) const noexcept
Compares this instance against other considering both sign() value Returns.
static BigInt from_s32(int32_t n)
Create big_int from a signed 32 bit integer.
BigInt & square(std::vector< mp_word_t > &ws)
Square value of *this.
BigInt & operator/=(const BigInt &y)
static BigInt from_word(mp_word_t n)
Create big_int from a mp_word_t (limb)
static BigInt with_capacity(size_t n)
Create big_int of specified size, all zeros.
bool is_zero() const noexcept
Test if the integer is zero.
mp_word_t word_at(size_t n) const noexcept
Return the mp_word_t at a specified position of the internal register.
BigInt operator/(const BigInt &y) const
BigInt operator-(const BigInt &y) const noexcept
BigInt & operator*=(const BigInt &y) noexcept
BigInt & mod_mul(uint8_t y, const BigInt &mod, std::vector< mp_word_t > &ws)
Set *this to (*this * y) % mod This function assumes *this is >= 0 && < mod y should be small,...
uint8_t byte_at(size_t n) const noexcept
BigInt mod_pow(BigInt e, const BigInt &m)
Returns (*this)^e % m, or pow(*this, e) % m.
BigInt & flip_sign() noexcept
Flip the sign of this big_int.
BigInt & operator+=(const BigInt &y) noexcept
void set_bit(size_t n) noexcept
Set bit at specified position.
BigInt operator*(const BigInt &y) noexcept
BigInt operator<<(size_t shift) const
BigInt(const std::string &str)
Construct a big_int_t from a string encoded as hexadecimal or decimal.
static BigInt from_u64(uint64_t n)
Create big_int from an unsigned 64 bit integer.
BigInt operator++(int) noexcept
BigInt(BigInt &&other) noexcept
static BigInt power_of_2(size_t n)
Create a power of two.
constexpr bool is_little_endian() noexcept
Evaluates true if platform is running in little endian mode, i.e.
constexpr std::enable_if_t< std::is_standard_layout_v< T >, T > get_value(uint8_t const *buffer) noexcept
Returns a T value from the given byte address using packed_t to resolve a potential memory alignment ...
char * cast_uint8_ptr_to_char(uint8_t *b) noexcept
constexpr uint16_t le_to_cpu(uint16_t const l) noexcept
lb_endian_t
Simplified reduced endian type only covering little- and big-endian.
constexpr std::enable_if_t< std::is_standard_layout_v< T >, void > put_value(uint8_t *buffer, const T &v) noexcept
Put the given T value into the given byte address using packed_t to resolve a potential memory alignm...
constexpr uint16_t cpu_to_le(uint16_t const h) noexcept
const uint8_t * cast_char_ptr_to_uint8(const char *s) noexcept
@ little
Identifier for little endian, equivalent to endian::little.
@ big
Identifier for big endian, equivalent to endian::big.
constexpr T ct_is_zero(T x)
Returns ~0 (2-complement) if arg is zero, otherwise 0 (w/o branching) in O(1) and constant time (CT).
constexpr bool value(const Bool rhs) noexcept
void swap(cow_darray< Value_type, Size_type, Alloc_type > &rhs, cow_darray< Value_type, Size_type, Alloc_type > &lhs) noexcept
constexpr T clamp(const T x, const T min_val, const T max_val) noexcept
Returns constrained integral value to lie between given min- and maximum value (w/ branching) in O(1)...
constexpr T round_up(const T n, const U align_to)
Round up w/ branching in O(1)
constexpr nsize_t high_bit(T x)
Return the index of the highest set bit w/ branching (loop) in O(n), actually O(n/2).
constexpr T min(const T x, const T y) noexcept
Returns the minimum of two integrals (w/ branching) in O(1)
constexpr T gcd(T a, T b) noexcept
Returns the greatest common divisor (GCD) of the two given integer values following Euclid's algorith...
constexpr T max(const T x, const T y) noexcept
Returns the maximum of two integrals (w/ branching) in O(1)
mp::BigInt pow(mp::BigInt b, const mp::BigInt &e)
constexpr T abs(const T x) noexcept
Returns the absolute value of an arithmetic number (w/ branching) in O(1)
constexpr bool is_power_of_2(const T x) noexcept
Power of 2 test (w/o branching ?) in O(1)
std::string bytesHexString(const void *data, const nsize_t length, const bool lsbFirst, const bool lowerCase=true, const bool skipLeading0x=false) noexcept
Produce a hexadecimal string representation of the given byte values.
size_t hexStringBytes(std::vector< uint8_t > &out, const std::string &hexstr, const bool lsbFirst, const bool checkLeading0x) noexcept
Converts a given hexadecimal string representation into a byte vector.
void unpoison(const T *p, size_t n)
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
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.
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.
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.
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_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
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
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.
jau::uint_bytes< impl::best_word_byte_size()>::type mp_word_t
constexpr const size_t mp_word_bits
constexpr const mp_word_t mp_word_max
__pack(...): Produces MSVC, clang and gcc compatible lead-in and -out macros.
std::ostream & operator<<(std::ostream &os, const jau::fraction_timespec &v) noexcept
Output stream operator for jau::fraction_timespec.