src/libcore/num/bignum.rs

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