library/core/src/num/bignum.rs

   1 //! Custom arbitrary-precision number (bignum) implementation.
   2 //!
   3 //! This is designed to avoid the heap allocation at expense of stack memory.
   4 //! The most used bignum type, `Big32x40`, is limited by 32 × 40 = 1,280 bits
   5 //! and will take at most 160 bytes of stack memory. This is more than enough
   6 //! for round-tripping all possible finite `f64` values.
   7 //!
   8 //! In principle it is possible to have multiple bignum types for different
   9 //! inputs, but we don't do so to avoid the code bloat. Each bignum is still
  10 //! tracked for the actual usages, so it normally doesn't matter.
  11
  12 // This module is only for dec2flt and flt2dec, and only public because of coretests.
  13 // It is not intended to ever be stabilized.
  14 #![doc(hidden)]
  15 #![unstable(
  16     feature = "core_private_bignum",
  17     reason = "internal routines only exposed for testing",
  18     issue = "none"
  19 )]
  20 #![macro_use]
  21
  22 use crate::intrinsics;
  23
  24 /// Arithmetic operations required by bignums.
  25 pub trait FullOps: Sized {
  26     /// Returns `(carry', v')` such that `carry' * 2^W + v' = self + other + carry`,
  27     /// where `W` is the number of bits in `Self`.
  28     fn full_add(self, other: Self, carry: bool) -> (bool /* carry */, Self);
  29
  30     /// Returns `(carry', v')` such that `carry' * 2^W + v' = self * other + carry`,
  31     /// where `W` is the number of bits in `Self`.
  32     fn full_mul(self, other: Self, carry: Self) -> (Self /* carry */, Self);
  33
  34     /// Returns `(carry', v')` such that `carry' * 2^W + v' = self * other + other2 + carry`,
  35     /// where `W` is the number of bits in `Self`.
  36     fn full_mul_add(self, other: Self, other2: Self, carry: Self) -> (Self /* carry */, Self);
  37
  38     /// Returns `(quo, rem)` such that `borrow * 2^W + self = quo * other + rem`
  39     /// and `0 <= rem < other`, where `W` is the number of bits in `Self`.
  40     fn full_div_rem(self, other: Self, borrow: Self)
  41     -> (Self /* quotient */, Self /* remainder */);
  42 }
  43
  44 macro_rules! impl_full_ops {
  45     ($($ty:ty: add($addfn:path), mul/div($bigty:ident);)*) => (
  46         $(
  47             impl FullOps for $ty {
  48                 fn full_add(self, other: $ty, carry: bool) -> (bool, $ty) {
  49                     // This cannot overflow; the output is between `0` and `2 * 2^nbits - 1`.
  50                     // FIXME: will LLVM optimize this into ADC or similar?
  51                     let (v, carry1) = intrinsics::add_with_overflow(self, other);
  52                     let (v, carry2) = intrinsics::add_with_overflow(v, if carry {1} else {0});
  53                     (carry1 || carry2, v)
  54                 }
  55
  56                 fn full_mul(self, other: $ty, carry: $ty) -> ($ty, $ty) {
  57                     // This cannot overflow;
  58                     // the output is between `0` and `2^nbits * (2^nbits - 1)`.
  59                     // FIXME: will LLVM optimize this into ADC or similar?
  60                     let v = (self as $bigty) * (other as $bigty) + (carry as $bigty);
  61                     ((v >> <$ty>::BITS) as $ty, v as $ty)
  62                 }
  63
  64                 fn full_mul_add(self, other: $ty, other2: $ty, carry: $ty) -> ($ty, $ty) {
  65                     // This cannot overflow;
  66                     // the output is between `0` and `2^nbits * (2^nbits - 1)`.
  67                     let v = (self as $bigty) * (other as $bigty) + (other2 as $bigty) +
  68                             (carry as $bigty);
  69                     ((v >> <$ty>::BITS) as $ty, v as $ty)
  70                 }
  71
  72                 fn full_div_rem(self, other: $ty, borrow: $ty) -> ($ty, $ty) {
  73                     debug_assert!(borrow < other);
  74                     // This cannot overflow; the output is between `0` and `other * (2^nbits - 1)`.
  75                     let lhs = ((borrow as $bigty) << <$ty>::BITS) | (self as $bigty);
  76                     let rhs = other as $bigty;
  77                     ((lhs / rhs) as $ty, (lhs % rhs) as $ty)
  78                 }
  79             }
  80         )*
  81     )
  82 }
  83
  84 impl_full_ops! {
  85     u8:  add(intrinsics::u8_add_with_overflow),  mul/div(u16);
  86     u16: add(intrinsics::u16_add_with_overflow), mul/div(u32);
  87     u32: add(intrinsics::u32_add_with_overflow), mul/div(u64);
  88     // See RFC #521 for enabling this.
  89     // u64: add(intrinsics::u64_add_with_overflow), mul/div(u128);
  90 }
  91
  92 /// Table of powers of 5 representable in digits. Specifically, the largest {u8, u16, u32} value
  93 /// that's a power of five, plus the corresponding exponent. Used in `mul_pow5`.
  94 const SMALL_POW5: [(u64, usize); 3] = [(125, 3), (15625, 6), (1_220_703_125, 13)];
  95
  96 macro_rules! define_bignum {
  97     ($name:ident: type=$ty:ty, n=$n:expr) => {
  98         /// Stack-allocated arbitrary-precision (up to certain limit) integer.
  99         ///
 100         /// This is backed by a fixed-size array of given type ("digit").
 101         /// While the array is not very large (normally some hundred bytes),
 102         /// copying it recklessly may result in the performance hit.
 103         /// Thus this is intentionally not `Copy`.
 104         ///
 105         /// All operations available to bignums panic in the case of overflows.
 106         /// The caller is responsible to use large enough bignum types.
 107         pub struct $name {
 108             /// One plus the offset to the maximum "digit" in use.
 109             /// This does not decrease, so be aware of the computation order.
 110             /// `base[size..]` should be zero.
 111             size: usize,
 112             /// Digits. `[a, b, c, ...]` represents `a + b*2^W + c*2^(2W) + ...`
 113             /// where `W` is the number of bits in the digit type.
 114             base: [$ty; $n],
 115         }
 116
 117         impl $name {
 118             /// Makes a bignum from one digit.
 119             pub fn from_small(v: $ty) -> $name {
 120                 let mut base = [0; $n];
 121                 base[0] = v;
 122                 $name { size: 1, base: base }
 123             }
 124
 125             /// Makes a bignum from `u64` value.
 126             pub fn from_u64(mut v: u64) -> $name {
 127                 let mut base = [0; $n];
 128                 let mut sz = 0;
 129                 while v > 0 {
 130                     base[sz] = v as $ty;
 131                     v >>= <$ty>::BITS;
 132                     sz += 1;
 133                 }
 134                 $name { size: sz, base: base }
 135             }
 136
 137             /// Returns the internal digits as a slice `[a, b, c, ...]` such that the numeric
 138             /// value is `a + b * 2^W + c * 2^(2W) + ...` where `W` is the number of bits in
 139             /// the digit type.
 140             pub fn digits(&self) -> &[$ty] {
 141                 &self.base[..self.size]
 142             }
 143
 144             /// Returns the `i`-th bit where bit 0 is the least significant one.
 145             /// In other words, the bit with weight `2^i`.
 146             pub fn get_bit(&self, i: usize) -> u8 {
 147                 let digitbits = <$ty>::BITS as usize;
 148                 let d = i / digitbits;
 149                 let b = i % digitbits;
 150                 ((self.base[d] >> b) & 1) as u8
 151             }
 152
 153             /// Returns `true` if the bignum is zero.
 154             pub fn is_zero(&self) -> bool {
 155                 self.digits().iter().all(|&v| v == 0)
 156             }
 157
 158             /// Returns the number of bits necessary to represent this value. Note that zero
 159             /// is considered to need 0 bits.
 160             pub fn bit_length(&self) -> usize {
 161                 // Skip over the most significant digits which are zero.
 162                 let digits = self.digits();
 163                 let zeros = digits.iter().rev().take_while(|&&x| x == 0).count();
 164                 let end = digits.len() - zeros;
 165                 let nonzero = &digits[..end];
 166
 167                 if nonzero.is_empty() {
 168                     // There are no non-zero digits, i.e., the number is zero.
 169                     return 0;
 170                 }
 171                 // This could be optimized with leading_zeros() and bit shifts, but that's
 172                 // probably not worth the hassle.
 173                 let digitbits = <$ty>::BITS as usize;
 174                 let mut i = nonzero.len() * digitbits - 1;
 175                 while self.get_bit(i) == 0 {
 176                     i -= 1;
 177                 }
 178                 i + 1
 179             }
 180
 181             /// Adds `other` to itself and returns its own mutable reference.
 182             pub fn add<'a>(&'a mut self, other: &$name) -> &'a mut $name {
 183                 use crate::cmp;
 184                 use crate::num::bignum::FullOps;
 185
 186                 let mut sz = cmp::max(self.size, other.size);
 187                 let mut carry = false;
 188                 for (a, b) in self.base[..sz].iter_mut().zip(&other.base[..sz]) {
 189                     let (c, v) = (*a).full_add(*b, carry);
 190                     *a = v;
 191                     carry = c;
 192                 }
 193                 if carry {
 194                     self.base[sz] = 1;
 195                     sz += 1;
 196                 }
 197                 self.size = sz;
 198                 self
 199             }
 200
 201             pub fn add_small(&mut self, other: $ty) -> &mut $name {
 202                 use crate::num::bignum::FullOps;
 203
 204                 let (mut carry, v) = self.base[0].full_add(other, false);
 205                 self.base[0] = v;
 206                 let mut i = 1;
 207                 while carry {
 208                     let (c, v) = self.base[i].full_add(0, carry);
 209                     self.base[i] = v;
 210                     carry = c;
 211                     i += 1;
 212                 }
 213                 if i > self.size {
 214                     self.size = i;
 215                 }
 216                 self
 217             }
 218
 219             /// Subtracts `other` from itself and returns its own mutable reference.
 220             pub fn sub<'a>(&'a mut self, other: &$name) -> &'a mut $name {
 221                 use crate::cmp;
 222                 use crate::num::bignum::FullOps;
 223
 224                 let sz = cmp::max(self.size, other.size);
 225                 let mut noborrow = true;
 226                 for (a, b) in self.base[..sz].iter_mut().zip(&other.base[..sz]) {
 227                     let (c, v) = (*a).full_add(!*b, noborrow);
 228                     *a = v;
 229                     noborrow = c;
 230                 }
 231                 assert!(noborrow);
 232                 self.size = sz;
 233                 self
 234             }
 235
 236             /// Multiplies itself by a digit-sized `other` and returns its own
 237             /// mutable reference.
 238             pub fn mul_small(&mut self, other: $ty) -> &mut $name {
 239                 use crate::num::bignum::FullOps;
 240
 241                 let mut sz = self.size;
 242                 let mut carry = 0;
 243                 for a in &mut self.base[..sz] {
 244                     let (c, v) = (*a).full_mul(other, carry);
 245                     *a = v;
 246                     carry = c;
 247                 }
 248                 if carry > 0 {
 249                     self.base[sz] = carry;
 250                     sz += 1;
 251                 }
 252                 self.size = sz;
 253                 self
 254             }
 255
 256             /// Multiplies itself by `2^bits` and returns its own mutable reference.
 257             pub fn mul_pow2(&mut self, bits: usize) -> &mut $name {
 258                 let digitbits = <$ty>::BITS as usize;
 259                 let digits = bits / digitbits;
 260                 let bits = bits % digitbits;
 261
 262                 assert!(digits < $n);
 263                 debug_assert!(self.base[$n - digits..].iter().all(|&v| v == 0));
 264                 debug_assert!(bits == 0 || (self.base[$n - digits - 1] >> (digitbits - bits)) == 0);
 265
 266                 // shift by `digits * digitbits` bits
 267                 for i in (0..self.size).rev() {
 268                     self.base[i + digits] = self.base[i];
 269                 }
 270                 for i in 0..digits {
 271                     self.base[i] = 0;
 272                 }
 273
 274                 // shift by `bits` bits
 275                 let mut sz = self.size + digits;
 276                 if bits > 0 {
 277                     let last = sz;
 278                     let overflow = self.base[last - 1] >> (digitbits - bits);
 279                     if overflow > 0 {
 280                         self.base[last] = overflow;
 281                         sz += 1;
 282                     }
 283                     for i in (digits + 1..last).rev() {
 284                         self.base[i] =
 285                             (self.base[i] << bits) | (self.base[i - 1] >> (digitbits - bits));
 286                     }
 287                     self.base[digits] <<= bits;
 288                     // self.base[..digits] is zero, no need to shift
 289                 }
 290
 291                 self.size = sz;
 292                 self
 293             }
 294
 295             /// Multiplies itself by `5^e` and returns its own mutable reference.
 296             pub fn mul_pow5(&mut self, mut e: usize) -> &mut $name {
 297                 use crate::mem;
 298                 use crate::num::bignum::SMALL_POW5;
 299
 300                 // There are exactly n trailing zeros on 2^n, and the only relevant digit sizes
 301                 // are consecutive powers of two, so this is well suited index for the table.
 302                 let table_index = mem::size_of::<$ty>().trailing_zeros() as usize;
 303                 let (small_power, small_e) = SMALL_POW5[table_index];
 304                 let small_power = small_power as $ty;
 305
 306                 // Multiply with the largest single-digit power as long as possible ...
 307                 while e >= small_e {
 308                     self.mul_small(small_power);
 309                     e -= small_e;
 310                 }
 311
 312                 // ... then finish off the remainder.
 313                 let mut rest_power = 1;
 314                 for _ in 0..e {
 315                     rest_power *= 5;
 316                 }
 317                 self.mul_small(rest_power);
 318
 319                 self
 320             }
 321
 322             /// Multiplies itself by a number described by `other[0] + other[1] * 2^W +
 323             /// other[2] * 2^(2W) + ...` (where `W` is the number of bits in the digit type)
 324             /// and returns its own mutable reference.
 325             pub fn mul_digits<'a>(&'a mut self, other: &[$ty]) -> &'a mut $name {
 326                 // the internal routine. works best when aa.len() <= bb.len().
 327                 fn mul_inner(ret: &mut [$ty; $n], aa: &[$ty], bb: &[$ty]) -> usize {
 328                     use crate::num::bignum::FullOps;
 329
 330                     let mut retsz = 0;
 331                     for (i, &a) in aa.iter().enumerate() {
 332                         if a == 0 {
 333                             continue;
 334                         }
 335                         let mut sz = bb.len();
 336                         let mut carry = 0;
 337                         for (j, &b) in bb.iter().enumerate() {
 338                             let (c, v) = a.full_mul_add(b, ret[i + j], carry);
 339                             ret[i + j] = v;
 340                             carry = c;
 341                         }
 342                         if carry > 0 {
 343                             ret[i + sz] = carry;
 344                             sz += 1;
 345                         }
 346                         if retsz < i + sz {
 347                             retsz = i + sz;
 348                         }
 349                     }
 350                     retsz
 351                 }
 352
 353                 let mut ret = [0; $n];
 354                 let retsz = if self.size < other.len() {
 355                     mul_inner(&mut ret, &self.digits(), other)
 356                 } else {
 357                     mul_inner(&mut ret, other, &self.digits())
 358                 };
 359                 self.base = ret;
 360                 self.size = retsz;
 361                 self
 362             }
 363
 364             /// Divides itself by a digit-sized `other` and returns its own
 365             /// mutable reference *and* the remainder.
 366             pub fn div_rem_small(&mut self, other: $ty) -> (&mut $name, $ty) {
 367                 use crate::num::bignum::FullOps;
 368
 369                 assert!(other > 0);
 370
 371                 let sz = self.size;
 372                 let mut borrow = 0;
 373                 for a in self.base[..sz].iter_mut().rev() {
 374                     let (q, r) = (*a).full_div_rem(other, borrow);
 375                     *a = q;
 376                     borrow = r;
 377                 }
 378                 (self, borrow)
 379             }
 380
 381             /// Divide self by another bignum, overwriting `q` with the quotient and `r` with the
 382             /// remainder.
 383             pub fn div_rem(&self, d: &$name, q: &mut $name, r: &mut $name) {
 384                 // Stupid slow base-2 long division taken from
 385                 // https://en.wikipedia.org/wiki/Division_algorithm
 386                 // FIXME use a greater base ($ty) for the long division.
 387                 assert!(!d.is_zero());
 388                 let digitbits = <$ty>::BITS as usize;
 389                 for digit in &mut q.base[..] {
 390                     *digit = 0;
 391                 }
 392                 for digit in &mut r.base[..] {
 393                     *digit = 0;
 394                 }
 395                 r.size = d.size;
 396                 q.size = 1;
 397                 let mut q_is_zero = true;
 398                 let end = self.bit_length();
 399                 for i in (0..end).rev() {
 400                     r.mul_pow2(1);
 401                     r.base[0] |= self.get_bit(i) as $ty;
 402                     if &*r >= d {
 403                         r.sub(d);
 404                         // Set bit `i` of q to 1.
 405                         let digit_idx = i / digitbits;
 406                         let bit_idx = i % digitbits;
 407                         if q_is_zero {
 408                             q.size = digit_idx + 1;
 409                             q_is_zero = false;
 410                         }
 411                         q.base[digit_idx] |= 1 << bit_idx;
 412                     }
 413                 }
 414                 debug_assert!(q.base[q.size..].iter().all(|&d| d == 0));
 415                 debug_assert!(r.base[r.size..].iter().all(|&d| d == 0));
 416             }
 417         }
 418
 419         impl crate::cmp::PartialEq for $name {
 420             fn eq(&self, other: &$name) -> bool {
 421                 self.base[..] == other.base[..]
 422             }
 423         }
 424
 425         impl crate::cmp::Eq for $name {}
 426
 427         impl crate::cmp::PartialOrd for $name {
 428             fn partial_cmp(&self, other: &$name) -> crate::option::Option<crate::cmp::Ordering> {
 429                 crate::option::Option::Some(self.cmp(other))
 430             }
 431         }
 432
 433         impl crate::cmp::Ord for $name {
 434             fn cmp(&self, other: &$name) -> crate::cmp::Ordering {
 435                 use crate::cmp::max;
 436                 let sz = max(self.size, other.size);
 437                 let lhs = self.base[..sz].iter().cloned().rev();
 438                 let rhs = other.base[..sz].iter().cloned().rev();
 439                 lhs.cmp(rhs)
 440             }
 441         }
 442
 443         impl crate::clone::Clone for $name {
 444             fn clone(&self) -> Self {
 445                 Self { size: self.size, base: self.base }
 446             }
 447         }
 448
 449         impl crate::fmt::Debug for $name {
 450             fn fmt(&self, f: &mut crate::fmt::Formatter<'_>) -> crate::fmt::Result {
 451                 let sz = if self.size < 1 { 1 } else { self.size };
 452                 let digitlen = <$ty>::BITS as usize / 4;
 453
 454                 write!(f, "{:#x}", self.base[sz - 1])?;
 455                 for &v in self.base[..sz - 1].iter().rev() {
 456                     write!(f, "_{:01$x}", v, digitlen)?;
 457                 }
 458                 crate::result::Result::Ok(())
 459             }
 460         }
 461     };
 462 }
 463
 464 /// The digit type for `Big32x40`.
 465 pub type Digit32 = u32;
 466
 467 define_bignum!(Big32x40: type=Digit32, n=40);
 468
 469 // this one is used for testing only.
 470 #[doc(hidden)]
 471 pub mod tests {
 472     define_bignum!(Big8x3: type=u8, n=3);
 473 }