#![allow(clippy::needless_range_loop)]
use super::BigInt;
use crate::error::{Error, OVERFLOW_ERROR, Result, VALUE_ERROR, ZERO_DIVISION_ERROR};
use std::mem::MaybeUninit;
const BASE: u64 = 1 << 32;
const INLINE_WORDS: usize = 32;
struct WordsBuf {
inline: MaybeUninit<[i64; INLINE_WORDS]>,
heap: Vec<i64>,
}
impl WordsBuf {
#[inline(always)]
fn new() -> Self {
Self {
inline: MaybeUninit::uninit(),
heap: Vec::new(),
}
}
#[inline]
fn zeroed(&mut self, len: usize) -> &mut [i64] {
if len <= INLINE_WORDS {
return self.inline_zeroed(len);
}
self.heap.resize(len, 0);
&mut self.heap
}
#[inline]
fn inline_zeroed(&mut self, len: usize) -> &mut [i64] {
debug_assert!(len <= INLINE_WORDS);
let words = self.inline.as_mut_ptr().cast::<i64>();
unsafe {
std::ptr::write_bytes(words, 0, len);
std::slice::from_raw_parts_mut(words, len)
}
}
}
pub(super) fn zero_division() -> Error {
Error::new(ZERO_DIVISION_ERROR, "Division by zero")
}
fn negative_shift() -> Error {
Error::new(VALUE_ERROR, "Negative BigInt shift count")
}
fn overflow(message: &str) -> Error {
Error::new(OVERFLOW_ERROR, message)
}
#[inline]
pub(super) fn is_negative(x: &[i64]) -> bool {
x[x.len() - 1] < 0
}
#[inline]
pub(super) fn extension(x: &[i64]) -> u64 {
if is_negative(x) { u64::MAX } else { 0 }
}
#[inline]
pub(super) fn word_at(x: &[i64], i: usize, extension: u64) -> u64 {
x.get(i).map_or(extension, |&w| w as u64)
}
pub(super) fn normalized_len(words: &[i64]) -> usize {
let mut size = words.len();
while size > 1 && words[size - 1] == (if words[size - 2] < 0 { -1 } else { 0 }) {
size -= 1;
}
size
}
#[inline]
pub(super) fn trunc_div_i64(a: i64, b: i64) -> Result<Option<i64>> {
if b == 0 {
return Err(zero_division());
}
Ok(a.checked_div(b))
}
#[inline]
pub(super) fn trunc_mod_i64(a: i64, b: i64) -> Result<Option<i64>> {
if b == 0 {
return Err(zero_division());
}
Ok(Some(a.wrapping_rem(b)))
}
#[inline]
pub(super) fn floor_div_i64(a: i64, b: i64) -> Result<Option<i64>> {
if b == 0 {
return Err(zero_division());
}
Ok(a.checked_div(b).map(|q| {
if a.wrapping_rem(b) != 0 && ((a < 0) != (b < 0)) {
q - 1
} else {
q
}
}))
}
#[inline]
pub(super) fn floor_mod_i64(a: i64, b: i64) -> Result<Option<i64>> {
if b == 0 {
return Err(zero_division());
}
let r = a.wrapping_rem(b);
Ok(Some(if r != 0 && ((a < 0) != (b < 0)) {
r + b
} else {
r
}))
}
#[inline]
pub(super) fn shl_i64(a: i64, b: i64) -> Result<Option<i64>> {
if b < 0 {
return Err(negative_shift());
}
if b == 0 || a == 0 {
return Ok(Some(a));
}
if b >= 64 || a > (i64::MAX >> b) || a < -(1i64 << (63 - b)) {
return Ok(None);
}
Ok(Some(a << b))
}
#[inline]
pub(super) fn shr_i64(a: i64, b: i64) -> Result<i64> {
if b < 0 {
return Err(negative_shift());
}
Ok(if b >= 64 {
if a < 0 { -1 } else { 0 }
} else {
a >> b
})
}
pub(super) fn add(a: &[i64], b: &[i64]) -> BigInt {
let size = a.len().max(b.len()) + 1;
let (ext_a, ext_b) = (extension(a), extension(b));
let mut carry = 0u64;
BigInt::build(size, |i| {
let (sum, c1) = word_at(a, i, ext_a).overflowing_add(word_at(b, i, ext_b));
let (result, c2) = sum.overflowing_add(carry);
carry = u64::from(c1 | c2);
result as i64
})
}
pub(super) fn sub(a: &[i64], b: &[i64]) -> BigInt {
let size = a.len().max(b.len()) + 1;
let (ext_a, ext_b) = (extension(a), extension(b));
let mut carry = 1u64;
BigInt::build(size, |i| {
let (sum, c1) = word_at(a, i, ext_a).overflowing_add(!word_at(b, i, ext_b));
let (result, c2) = sum.overflowing_add(carry);
carry = u64::from(c1 | c2);
result as i64
})
}
pub(super) fn negate(x: &[i64]) -> BigInt {
let size = x.len() + 1;
let ext = extension(x);
let mut carry = 1u64;
BigInt::build(size, |i| {
let word = !word_at(x, i, ext);
let (result, overflow) = word.overflowing_add(carry);
carry = u64::from(overflow);
result as i64
})
}
pub(super) fn negate_in_place(words: &mut [i64]) {
let mut carry = true;
for word in words.iter_mut() {
let (sum, overflow) = (!(*word as u64)).overflowing_add(u64::from(carry));
*word = sum as i64;
carry = overflow;
}
}
pub(super) fn mul(a: &[i64], b: &[i64]) -> BigInt {
let (na, nb) = (a.len(), b.len());
let mut buf = WordsBuf::new();
let data = buf.zeroed(na + nb);
for i in 0..na {
let x = u128::from(a[i] as u64);
let mut carry = 0u128;
for j in 0..nb {
let product = x * u128::from(b[j] as u64) + u128::from(data[i + j] as u64) + carry;
data[i + j] = product as u64 as i64;
carry = product >> 64;
}
data[i + nb] = carry as u64 as i64;
}
let subtract_shifted = |data: &mut [i64], x: &[i64], shift: usize| {
let mut borrow = 0u64;
for i in 0..x.len() {
let word = x[i] as u64;
let (rhs, o1) = word.overflowing_add(borrow);
let (result, o2) = (data[shift + i] as u64).overflowing_sub(rhs);
data[shift + i] = result as i64;
borrow = u64::from(o1 | o2);
}
};
if is_negative(a) {
subtract_shifted(data, b, na);
}
if is_negative(b) {
subtract_shifted(data, a, nb);
}
BigInt::from_words(data)
}
fn bitwise(a: &[i64], b: &[i64], op: impl Fn(u64, u64) -> u64) -> BigInt {
let size = a.len().max(b.len());
let (ext_a, ext_b) = (extension(a), extension(b));
BigInt::build(size, |i| {
op(word_at(a, i, ext_a), word_at(b, i, ext_b)) as i64
})
}
pub(super) fn and(a: &[i64], b: &[i64]) -> BigInt {
bitwise(a, b, |x, y| x & y)
}
pub(super) fn or(a: &[i64], b: &[i64]) -> BigInt {
bitwise(a, b, |x, y| x | y)
}
pub(super) fn xor(a: &[i64], b: &[i64]) -> BigInt {
bitwise(a, b, |x, y| x ^ y)
}
pub(super) fn not(x: &[i64]) -> BigInt {
BigInt::build(x.len(), |i| !x[i])
}
fn shift_count(count: &[i64]) -> Result<Option<usize>> {
if is_negative(count) {
return Err(negative_shift());
}
if count[1..].iter().any(|&w| w != 0) {
return Ok(None);
}
Ok(usize::try_from(count[0] as u64).ok())
}
#[inline]
pub(super) fn shl(x: &[i64], count: &[i64]) -> Result<BigInt> {
let shift = shift_count(count)?;
if x.len() == 1 && x[0] == 0 {
return Ok(BigInt::from_i64(0));
}
let too_large = || overflow("BigInt shift count is too large");
let shift = shift.ok_or_else(too_large)?;
let whole = shift / 64;
let part = (shift % 64) as u32;
let size = x
.len()
.checked_add(whole)
.and_then(|size| size.checked_add(1))
.ok_or_else(too_large)?;
let ext = extension(x);
BigInt::try_build(size, |i| {
if i < whole {
return 0;
}
let j = i - whole;
let mut word = word_at(x, j, ext) << part;
if part != 0 && j != 0 {
word |= (x[j - 1] as u64) >> (64 - part);
}
word as i64
})
.ok_or_else(|| overflow("BigInt allocation is too large"))
}
pub(super) fn shr(x: &[i64], count: &[i64]) -> Result<BigInt> {
let shift = match shift_count(count)? {
Some(shift) if shift / 64 < x.len() => shift,
_ => return Ok(BigInt::from_i64(if is_negative(x) { -1 } else { 0 })),
};
let whole = shift / 64;
let size = x.len() - whole;
let part = (shift % 64) as u32;
let ext = extension(x);
let result = BigInt::build(size, |i| {
let mut word = (x[i + whole] as u64) >> part;
if part != 0 {
word |= word_at(x, i + whole + 1, ext) << (64 - part);
}
word as i64
});
Ok(result)
}
fn first_nonzero(x: &[i64]) -> usize {
x.iter().position(|&w| w != 0).unwrap_or(x.len())
}
#[inline]
fn abs_word(x: &[i64], first_nonzero: usize, i: usize) -> i64 {
if i >= x.len() {
return 0;
}
let word = x[i];
if !is_negative(x) {
return word;
}
if i < first_nonzero {
0
} else if i == first_nonzero {
word.wrapping_neg()
} else {
!word
}
}
pub(super) fn div_rem_single(a: &[i64], b: i64) -> Result<(BigInt, BigInt)> {
if b == 0 {
return Err(zero_division());
}
let divisor = b.unsigned_abs();
let first_a = first_nonzero(a);
let nq = a.len() + 1;
let mut quotient = WordsBuf::new();
let q = quotient.zeroed(nq);
let mut remainder = 0u64;
let mut shift = 0u32;
let mut normalized = divisor;
if divisor > u64::from(u32::MAX) {
while normalized >> 63 == 0 {
normalized <<= 1;
shift += 1;
}
}
let divisor_high = normalized >> 32;
let divisor_low = normalized as u32 as u64;
for i in (0..a.len()).rev() {
let word = abs_word(a, first_a, i) as u64;
let quotient_word = if divisor <= u64::from(u32::MAX) {
let high = (remainder << 32) | (word >> 32);
let quotient_high = high / divisor;
remainder = high % divisor;
let low = (remainder << 32) | (word as u32 as u64);
let quotient_low = low / divisor;
remainder = low % divisor;
(quotient_high << 32) | quotient_low
} else {
let high = if shift != 0 {
(remainder << shift) | (word >> (64 - shift))
} else {
remainder
};
let low = word << shift;
let digit = |upper: u64, next: u64| -> (u64, u64) {
let mut estimate = upper / divisor_high;
let mut residual = upper % divisor_high;
while estimate >= BASE || estimate * divisor_low > (residual << 32) + next {
estimate -= 1;
residual += divisor_high;
if residual >= BASE {
break;
}
}
let rest = (upper << 32)
.wrapping_add(next)
.wrapping_sub(estimate.wrapping_mul(normalized));
(estimate, rest)
};
let upper = digit(high, low >> 32);
let lower = digit(upper.1, low as u32 as u64);
remainder = lower.1 >> shift;
(upper.0 << 32) | lower.0
};
q[i] = quotient_word as i64;
}
if is_negative(a) != (b < 0) {
negate_in_place(&mut q[..nq]);
}
let mut signed_remainder = remainder as i64;
if is_negative(a) {
signed_remainder = -signed_remainder;
}
Ok((BigInt::from_words(q), BigInt::from_i64(signed_remainder)))
}
pub(super) fn div_rem(a: &[i64], b: &[i64]) -> Result<(BigInt, BigInt)> {
if b.len() == 1 {
return div_rem_single(a, b[0]);
}
let first_a = first_nonzero(a);
let first_b = first_nonzero(b);
let digit_count = |x: &[i64], first: usize| -> usize {
let mut words = x.len();
while words > 0 && abs_word(x, first, words - 1) == 0 {
words -= 1;
}
if words == 0 {
return 0;
}
let top = abs_word(x, first, words - 1) as u64;
2 * words - usize::from(top >> 32 == 0)
};
let m = digit_count(a, first_a);
let n = digit_count(b, first_b);
if m < n {
return Ok((BigInt::from_i64(0), BigInt::from_words(a)));
}
let top_word = abs_word(b, first_b, (n - 1) / 2) as u64;
let mut top_digit = (top_word >> (((n - 1) % 2) * 32)) as u32;
let mut shift = 0u32;
while top_digit < (1u32 << 31) {
top_digit <<= 1;
shift += 1;
}
let nq = (m - n) / 2 + 2;
let nr = n.div_ceil(2) + 1;
let capacity = nq
.checked_add(m + 1)
.and_then(|words| words.checked_add(n))
.ok_or_else(|| overflow("BigInt division workspace is too large"))?;
let mut quotient = WordsBuf::new();
let mut remainder = WordsBuf::new();
let (q, scratch) = quotient.zeroed(capacity).split_at_mut(nq);
let (u, v) = scratch.split_at_mut(m + 1);
let r = remainder.zeroed(nr);
let normalize = |x: &[i64], first: usize, digits: usize, out: &mut [i64]| -> u32 {
let mut carry = 0u64;
for i in 0..digits {
let word = abs_word(x, first, i / 2) as u64;
let part = (word >> ((i % 2) * 32)) as u32 as u64;
let value = (part << shift) | carry;
out[i] = (value as u32) as i64;
carry = value >> 32;
}
carry as u32
};
u[m] = i64::from(normalize(a, first_a, m, &mut u[..m]));
normalize(b, first_b, n, &mut v[..n]);
let mut quotient_word = 0u64;
for j in (0..=(m - n)).rev() {
let (mut estimate, mut residual) = if u[j + n] == v[n - 1] {
(BASE - 1, u[j + n - 1] as u64 + v[n - 1] as u64)
} else {
let numerator = ((u[j + n] as u64) << 32) | u[j + n - 1] as u64;
(numerator / v[n - 1] as u64, numerator % v[n - 1] as u64)
};
while residual < BASE && estimate * v[n - 2] as u64 > (residual << 32) + u[j + n - 2] as u64
{
estimate -= 1;
residual += v[n - 1] as u64;
}
let mut borrow = 0u64;
for i in 0..n {
let product = estimate * v[i] as u64 + borrow;
let low = product as u32;
let old = u[j + i] as u32;
u[j + i] = i64::from(old.wrapping_sub(low));
borrow = (product >> 32) + u64::from(old < low);
}
let old = u[j + n] as u64;
let negative = old < borrow;
u[j + n] = i64::from(old.wrapping_sub(borrow) as u32);
if negative {
estimate -= 1;
let mut carry = 0u64;
for i in 0..n {
let sum = u[j + i] as u64 + v[i] as u64 + carry;
u[j + i] = i64::from(sum as u32);
carry = sum >> 32;
}
u[j + n] = i64::from((u[j + n] as u64 + carry) as u32);
}
if j % 2 == 1 {
quotient_word = estimate << 32;
} else {
q[j / 2] = (quotient_word | estimate) as i64;
}
}
for i in 0..nr - 1 {
let digit = 2 * i;
let mut word = u[digit] as u64;
if digit + 1 < n {
word |= (u[digit + 1] as u64) << 32;
}
word >>= shift;
if shift != 0 && digit + 2 < n {
word |= (u[digit + 2] as u64) << (64 - shift);
}
r[i] = word as i64;
}
if is_negative(a) != is_negative(b) {
negate_in_place(q);
}
if is_negative(a) {
negate_in_place(r);
}
Ok((BigInt::from_words(q), BigInt::from_words(r)))
}
pub(super) fn trunc_div(a: &[i64], b: &[i64]) -> Result<BigInt> {
Ok(div_rem(a, b)?.0)
}
pub(super) fn trunc_mod(a: &[i64], b: &[i64]) -> Result<BigInt> {
if b.len() == 1 {
if b[0] == 0 {
return Err(zero_division());
}
let divisor = b[0].unsigned_abs();
if divisor <= u64::from(u32::MAX) {
let first = first_nonzero(a);
let mut remainder = 0u64;
for i in (0..a.len()).rev() {
let word = abs_word(a, first, i) as u64;
remainder = ((remainder << 32) | (word >> 32)) % divisor;
remainder = ((remainder << 32) | (word as u32 as u64)) % divisor;
}
let result = remainder as i64;
return Ok(BigInt::from_i64(if is_negative(a) {
-result
} else {
result
}));
}
}
Ok(div_rem(a, b)?.1)
}
pub(super) fn floor_div(a: &[i64], b: &[i64]) -> Result<BigInt> {
let (quotient, remainder) = div_rem(a, b)?;
if !remainder.is_zero() && is_negative(a) != is_negative(b) {
return Ok(sub(quotient.words(), &[1]));
}
Ok(quotient)
}
pub(super) fn floor_mod(a: &[i64], b: &[i64]) -> Result<BigInt> {
let remainder = trunc_mod(a, b)?;
if !remainder.is_zero() && is_negative(a) != is_negative(b) {
if let ([divisor], Some(r)) = (b, remainder.to_i64()) {
return Ok(BigInt::from_i64(r + divisor));
}
return Ok(add(remainder.words(), b));
}
Ok(remainder)
}
pub(super) fn to_f64(x: &[i64]) -> Result<f64> {
let first = first_nonzero(x);
let mut size = x.len();
while size > 0 && abs_word(x, first, size - 1) == 0 {
size -= 1;
}
if size == 0 {
return Ok(0.0);
}
let does_not_fit = || overflow("BigInt does not fit finite double");
if size > 16 {
return Err(does_not_fit());
}
let high = abs_word(x, first, size - 1) as u64;
let bits = (size - 1) * 64 + (64 - high.leading_zeros() as usize);
let shift = bits.saturating_sub(53);
let bit = |i: usize| ((abs_word(x, first, i / 64) as u64) >> (i % 64)) & 1;
let mut significand = 0u64;
for i in (shift..bits).rev() {
significand = (significand << 1) | bit(i);
}
if shift > 0 {
let sticky = (0..shift - 1).any(|i| bit(i) != 0);
if bit(shift - 1) == 1 && (sticky || significand & 1 == 1) {
significand += 1;
}
}
if bits == 1024 && significand == 1 << 53 {
return Err(does_not_fit());
}
let result = significand as f64 * 2f64.powi(shift as i32);
Ok(if is_negative(x) { -result } else { result })
}
pub(super) fn mul_add_small(magnitude: &mut Vec<u64>, factor: u64, addend: u64) {
let mut carry = u128::from(addend);
for word in magnitude.iter_mut() {
let product = u128::from(*word) * u128::from(factor) + carry;
*word = product as u64;
carry = product >> 64;
}
if carry != 0 {
magnitude.push(carry as u64);
}
}