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