summaryrefslogtreecommitdiffstats
path: root/library/core/src/num/bignum.rs
diff options
context:
space:
mode:
Diffstat (limited to 'library/core/src/num/bignum.rs')
-rw-r--r--library/core/src/num/bignum.rs434
1 files changed, 434 insertions, 0 deletions
diff --git a/library/core/src/num/bignum.rs b/library/core/src/num/bignum.rs
new file mode 100644
index 000000000..de85fdd6e
--- /dev/null
+++ b/library/core/src/num/bignum.rs
@@ -0,0 +1,434 @@
+//! Custom arbitrary-precision number (bignum) implementation.
+//!
+//! This is designed to avoid the heap allocation at expense of stack memory.
+//! The most used bignum type, `Big32x40`, is limited by 32 × 40 = 1,280 bits
+//! and will take at most 160 bytes of stack memory. This is more than enough
+//! for round-tripping all possible finite `f64` values.
+//!
+//! In principle it is possible to have multiple bignum types for different
+//! inputs, but we don't do so to avoid the code bloat. Each bignum is still
+//! tracked for the actual usages, so it normally doesn't matter.
+
+// This module is only for dec2flt and flt2dec, and only public because of coretests.
+// It is not intended to ever be stabilized.
+#![doc(hidden)]
+#![unstable(
+ feature = "core_private_bignum",
+ reason = "internal routines only exposed for testing",
+ issue = "none"
+)]
+#![macro_use]
+
+/// Arithmetic operations required by bignums.
+pub trait FullOps: Sized {
+ /// Returns `(carry', v')` such that `carry' * 2^W + v' = self * other + other2 + carry`,
+ /// where `W` is the number of bits in `Self`.
+ fn full_mul_add(self, other: Self, other2: Self, carry: Self) -> (Self /* carry */, Self);
+
+ /// Returns `(quo, rem)` such that `borrow * 2^W + self = quo * other + rem`
+ /// and `0 <= rem < other`, where `W` is the number of bits in `Self`.
+ fn full_div_rem(self, other: Self, borrow: Self)
+ -> (Self /* quotient */, Self /* remainder */);
+}
+
+macro_rules! impl_full_ops {
+ ($($ty:ty: add($addfn:path), mul/div($bigty:ident);)*) => (
+ $(
+ impl FullOps for $ty {
+ fn full_mul_add(self, other: $ty, other2: $ty, carry: $ty) -> ($ty, $ty) {
+ // This cannot overflow;
+ // the output is between `0` and `2^nbits * (2^nbits - 1)`.
+ let v = (self as $bigty) * (other as $bigty) + (other2 as $bigty) +
+ (carry as $bigty);
+ ((v >> <$ty>::BITS) as $ty, v as $ty)
+ }
+
+ fn full_div_rem(self, other: $ty, borrow: $ty) -> ($ty, $ty) {
+ debug_assert!(borrow < other);
+ // This cannot overflow; the output is between `0` and `other * (2^nbits - 1)`.
+ let lhs = ((borrow as $bigty) << <$ty>::BITS) | (self as $bigty);
+ let rhs = other as $bigty;
+ ((lhs / rhs) as $ty, (lhs % rhs) as $ty)
+ }
+ }
+ )*
+ )
+}
+
+impl_full_ops! {
+ u8: add(intrinsics::u8_add_with_overflow), mul/div(u16);
+ u16: add(intrinsics::u16_add_with_overflow), mul/div(u32);
+ u32: add(intrinsics::u32_add_with_overflow), mul/div(u64);
+ // See RFC #521 for enabling this.
+ // u64: add(intrinsics::u64_add_with_overflow), mul/div(u128);
+}
+
+/// Table of powers of 5 representable in digits. Specifically, the largest {u8, u16, u32} value
+/// that's a power of five, plus the corresponding exponent. Used in `mul_pow5`.
+const SMALL_POW5: [(u64, usize); 3] = [(125, 3), (15625, 6), (1_220_703_125, 13)];
+
+macro_rules! define_bignum {
+ ($name:ident: type=$ty:ty, n=$n:expr) => {
+ /// Stack-allocated arbitrary-precision (up to certain limit) integer.
+ ///
+ /// This is backed by a fixed-size array of given type ("digit").
+ /// While the array is not very large (normally some hundred bytes),
+ /// copying it recklessly may result in the performance hit.
+ /// Thus this is intentionally not `Copy`.
+ ///
+ /// All operations available to bignums panic in the case of overflows.
+ /// The caller is responsible to use large enough bignum types.
+ pub struct $name {
+ /// One plus the offset to the maximum "digit" in use.
+ /// This does not decrease, so be aware of the computation order.
+ /// `base[size..]` should be zero.
+ size: usize,
+ /// Digits. `[a, b, c, ...]` represents `a + b*2^W + c*2^(2W) + ...`
+ /// where `W` is the number of bits in the digit type.
+ base: [$ty; $n],
+ }
+
+ impl $name {
+ /// Makes a bignum from one digit.
+ pub fn from_small(v: $ty) -> $name {
+ let mut base = [0; $n];
+ base[0] = v;
+ $name { size: 1, base }
+ }
+
+ /// Makes a bignum from `u64` value.
+ pub fn from_u64(mut v: u64) -> $name {
+ let mut base = [0; $n];
+ let mut sz = 0;
+ while v > 0 {
+ base[sz] = v as $ty;
+ v >>= <$ty>::BITS;
+ sz += 1;
+ }
+ $name { size: sz, base }
+ }
+
+ /// Returns the internal digits as a slice `[a, b, c, ...]` such that the numeric
+ /// value is `a + b * 2^W + c * 2^(2W) + ...` where `W` is the number of bits in
+ /// the digit type.
+ pub fn digits(&self) -> &[$ty] {
+ &self.base[..self.size]
+ }
+
+ /// Returns the `i`-th bit where bit 0 is the least significant one.
+ /// In other words, the bit with weight `2^i`.
+ pub fn get_bit(&self, i: usize) -> u8 {
+ let digitbits = <$ty>::BITS as usize;
+ let d = i / digitbits;
+ let b = i % digitbits;
+ ((self.base[d] >> b) & 1) as u8
+ }
+
+ /// Returns `true` if the bignum is zero.
+ pub fn is_zero(&self) -> bool {
+ self.digits().iter().all(|&v| v == 0)
+ }
+
+ /// Returns the number of bits necessary to represent this value. Note that zero
+ /// is considered to need 0 bits.
+ pub fn bit_length(&self) -> usize {
+ let digitbits = <$ty>::BITS as usize;
+ let digits = self.digits();
+ // Find the most significant non-zero digit.
+ let msd = digits.iter().rposition(|&x| x != 0);
+ match msd {
+ Some(msd) => msd * digitbits + digits[msd].log2() as usize + 1,
+ // There are no non-zero digits, i.e., the number is zero.
+ _ => 0,
+ }
+ }
+
+ /// Adds `other` to itself and returns its own mutable reference.
+ pub fn add<'a>(&'a mut self, other: &$name) -> &'a mut $name {
+ use crate::cmp;
+ use crate::iter;
+
+ let mut sz = cmp::max(self.size, other.size);
+ let mut carry = false;
+ for (a, b) in iter::zip(&mut self.base[..sz], &other.base[..sz]) {
+ let (v, c) = (*a).carrying_add(*b, carry);
+ *a = v;
+ carry = c;
+ }
+ if carry {
+ self.base[sz] = 1;
+ sz += 1;
+ }
+ self.size = sz;
+ self
+ }
+
+ pub fn add_small(&mut self, other: $ty) -> &mut $name {
+ let (v, mut carry) = self.base[0].carrying_add(other, false);
+ self.base[0] = v;
+ let mut i = 1;
+ while carry {
+ let (v, c) = self.base[i].carrying_add(0, carry);
+ self.base[i] = v;
+ carry = c;
+ i += 1;
+ }
+ if i > self.size {
+ self.size = i;
+ }
+ self
+ }
+
+ /// Subtracts `other` from itself and returns its own mutable reference.
+ pub fn sub<'a>(&'a mut self, other: &$name) -> &'a mut $name {
+ use crate::cmp;
+ use crate::iter;
+
+ let sz = cmp::max(self.size, other.size);
+ let mut noborrow = true;
+ for (a, b) in iter::zip(&mut self.base[..sz], &other.base[..sz]) {
+ let (v, c) = (*a).carrying_add(!*b, noborrow);
+ *a = v;
+ noborrow = c;
+ }
+ assert!(noborrow);
+ self.size = sz;
+ self
+ }
+
+ /// Multiplies itself by a digit-sized `other` and returns its own
+ /// mutable reference.
+ pub fn mul_small(&mut self, other: $ty) -> &mut $name {
+ let mut sz = self.size;
+ let mut carry = 0;
+ for a in &mut self.base[..sz] {
+ let (v, c) = (*a).carrying_mul(other, carry);
+ *a = v;
+ carry = c;
+ }
+ if carry > 0 {
+ self.base[sz] = carry;
+ sz += 1;
+ }
+ self.size = sz;
+ self
+ }
+
+ /// Multiplies itself by `2^bits` and returns its own mutable reference.
+ pub fn mul_pow2(&mut self, bits: usize) -> &mut $name {
+ let digitbits = <$ty>::BITS as usize;
+ let digits = bits / digitbits;
+ let bits = bits % digitbits;
+
+ assert!(digits < $n);
+ debug_assert!(self.base[$n - digits..].iter().all(|&v| v == 0));
+ debug_assert!(bits == 0 || (self.base[$n - digits - 1] >> (digitbits - bits)) == 0);
+
+ // shift by `digits * digitbits` bits
+ for i in (0..self.size).rev() {
+ self.base[i + digits] = self.base[i];
+ }
+ for i in 0..digits {
+ self.base[i] = 0;
+ }
+
+ // shift by `bits` bits
+ let mut sz = self.size + digits;
+ if bits > 0 {
+ let last = sz;
+ let overflow = self.base[last - 1] >> (digitbits - bits);
+ if overflow > 0 {
+ self.base[last] = overflow;
+ sz += 1;
+ }
+ for i in (digits + 1..last).rev() {
+ self.base[i] =
+ (self.base[i] << bits) | (self.base[i - 1] >> (digitbits - bits));
+ }
+ self.base[digits] <<= bits;
+ // self.base[..digits] is zero, no need to shift
+ }
+
+ self.size = sz;
+ self
+ }
+
+ /// Multiplies itself by `5^e` and returns its own mutable reference.
+ pub fn mul_pow5(&mut self, mut e: usize) -> &mut $name {
+ use crate::mem;
+ use crate::num::bignum::SMALL_POW5;
+
+ // There are exactly n trailing zeros on 2^n, and the only relevant digit sizes
+ // are consecutive powers of two, so this is well suited index for the table.
+ let table_index = mem::size_of::<$ty>().trailing_zeros() as usize;
+ let (small_power, small_e) = SMALL_POW5[table_index];
+ let small_power = small_power as $ty;
+
+ // Multiply with the largest single-digit power as long as possible ...
+ while e >= small_e {
+ self.mul_small(small_power);
+ e -= small_e;
+ }
+
+ // ... then finish off the remainder.
+ let mut rest_power = 1;
+ for _ in 0..e {
+ rest_power *= 5;
+ }
+ self.mul_small(rest_power);
+
+ self
+ }
+
+ /// Multiplies itself by a number described by `other[0] + other[1] * 2^W +
+ /// other[2] * 2^(2W) + ...` (where `W` is the number of bits in the digit type)
+ /// and returns its own mutable reference.
+ pub fn mul_digits<'a>(&'a mut self, other: &[$ty]) -> &'a mut $name {
+ // the internal routine. works best when aa.len() <= bb.len().
+ fn mul_inner(ret: &mut [$ty; $n], aa: &[$ty], bb: &[$ty]) -> usize {
+ use crate::num::bignum::FullOps;
+
+ let mut retsz = 0;
+ for (i, &a) in aa.iter().enumerate() {
+ if a == 0 {
+ continue;
+ }
+ let mut sz = bb.len();
+ let mut carry = 0;
+ for (j, &b) in bb.iter().enumerate() {
+ let (c, v) = a.full_mul_add(b, ret[i + j], carry);
+ ret[i + j] = v;
+ carry = c;
+ }
+ if carry > 0 {
+ ret[i + sz] = carry;
+ sz += 1;
+ }
+ if retsz < i + sz {
+ retsz = i + sz;
+ }
+ }
+ retsz
+ }
+
+ let mut ret = [0; $n];
+ let retsz = if self.size < other.len() {
+ mul_inner(&mut ret, &self.digits(), other)
+ } else {
+ mul_inner(&mut ret, other, &self.digits())
+ };
+ self.base = ret;
+ self.size = retsz;
+ self
+ }
+
+ /// Divides itself by a digit-sized `other` and returns its own
+ /// mutable reference *and* the remainder.
+ pub fn div_rem_small(&mut self, other: $ty) -> (&mut $name, $ty) {
+ use crate::num::bignum::FullOps;
+
+ assert!(other > 0);
+
+ let sz = self.size;
+ let mut borrow = 0;
+ for a in self.base[..sz].iter_mut().rev() {
+ let (q, r) = (*a).full_div_rem(other, borrow);
+ *a = q;
+ borrow = r;
+ }
+ (self, borrow)
+ }
+
+ /// Divide self by another bignum, overwriting `q` with the quotient and `r` with the
+ /// remainder.
+ pub fn div_rem(&self, d: &$name, q: &mut $name, r: &mut $name) {
+ // Stupid slow base-2 long division taken from
+ // https://en.wikipedia.org/wiki/Division_algorithm
+ // FIXME use a greater base ($ty) for the long division.
+ assert!(!d.is_zero());
+ let digitbits = <$ty>::BITS as usize;
+ for digit in &mut q.base[..] {
+ *digit = 0;
+ }
+ for digit in &mut r.base[..] {
+ *digit = 0;
+ }
+ r.size = d.size;
+ q.size = 1;
+ let mut q_is_zero = true;
+ let end = self.bit_length();
+ for i in (0..end).rev() {
+ r.mul_pow2(1);
+ r.base[0] |= self.get_bit(i) as $ty;
+ if &*r >= d {
+ r.sub(d);
+ // Set bit `i` of q to 1.
+ let digit_idx = i / digitbits;
+ let bit_idx = i % digitbits;
+ if q_is_zero {
+ q.size = digit_idx + 1;
+ q_is_zero = false;
+ }
+ q.base[digit_idx] |= 1 << bit_idx;
+ }
+ }
+ debug_assert!(q.base[q.size..].iter().all(|&d| d == 0));
+ debug_assert!(r.base[r.size..].iter().all(|&d| d == 0));
+ }
+ }
+
+ impl crate::cmp::PartialEq for $name {
+ fn eq(&self, other: &$name) -> bool {
+ self.base[..] == other.base[..]
+ }
+ }
+
+ impl crate::cmp::Eq for $name {}
+
+ impl crate::cmp::PartialOrd for $name {
+ fn partial_cmp(&self, other: &$name) -> crate::option::Option<crate::cmp::Ordering> {
+ crate::option::Option::Some(self.cmp(other))
+ }
+ }
+
+ impl crate::cmp::Ord for $name {
+ fn cmp(&self, other: &$name) -> crate::cmp::Ordering {
+ use crate::cmp::max;
+ let sz = max(self.size, other.size);
+ let lhs = self.base[..sz].iter().cloned().rev();
+ let rhs = other.base[..sz].iter().cloned().rev();
+ lhs.cmp(rhs)
+ }
+ }
+
+ impl crate::clone::Clone for $name {
+ fn clone(&self) -> Self {
+ Self { size: self.size, base: self.base }
+ }
+ }
+
+ impl crate::fmt::Debug for $name {
+ fn fmt(&self, f: &mut crate::fmt::Formatter<'_>) -> crate::fmt::Result {
+ let sz = if self.size < 1 { 1 } else { self.size };
+ let digitlen = <$ty>::BITS as usize / 4;
+
+ write!(f, "{:#x}", self.base[sz - 1])?;
+ for &v in self.base[..sz - 1].iter().rev() {
+ write!(f, "_{:01$x}", v, digitlen)?;
+ }
+ crate::result::Result::Ok(())
+ }
+ }
+ };
+}
+
+/// The digit type for `Big32x40`.
+pub type Digit32 = u32;
+
+define_bignum!(Big32x40: type=Digit32, n=40);
+
+// this one is used for testing only.
+#[doc(hidden)]
+pub mod tests {
+ define_bignum!(Big8x3: type=u8, n=3);
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-29 00:50:42 +0000