Reorganize core::num internals

Move private bignum module to core::num, because it is not only used in flt2dec.
Extract private 80-bit soft-float into new core::num module for the same reason.

4 files changed, 3 insertions, 546 deletions

diff --git a/src/libcore/num/flt2dec/bignum.rs b/src/libcore/num/flt2dec/bignum.rs
deleted file mode 100644
index 091e9c889da..00000000000
--- a/src/libcore/num/flt2dec/bignum.rs
+++ /dev/null
@@ -1,491 +0,0 @@
-// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
-// file at the top-level directory of this distribution and at
-// http://rust-lang.org/COPYRIGHT.
-//
-// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
-// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
-// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
-// option. This file may not be copied, modified, or distributed
-// except according to those terms.
-
-//! 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.
-
-#![macro_use]
-
-use prelude::v1::*;
-
-use mem;
-use intrinsics;
-
-/// Arithmetic operations required by bignums.
-pub trait FullOps {
-    /// Returns `(carry', v')` such that `carry' * 2^W + v' = self + other + carry`,
-    /// where `W` is the number of bits in `Self`.
-    fn full_add(self, other: Self, carry: bool) -> (bool /*carry*/, Self);
-
-    /// Returns `(carry', v')` such that `carry' * 2^W + v' = self * other + carry`,
-    /// where `W` is the number of bits in `Self`.
-    fn full_mul(self, other: Self, carry: Self) -> (Self /*carry*/, Self);
-
-    /// 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_add(self, other: $ty, carry: bool) -> (bool, $ty) {
-                    // this cannot overflow, the output is between 0 and 2*2^nbits - 1
-                    // FIXME will LLVM optimize this into ADC or similar???
-                    let (v, carry1) = unsafe { $addfn(self, other) };
-                    let (v, carry2) = unsafe { $addfn(v, if carry {1} else {0}) };
-                    (carry1 || carry2, v)
-                }
-
-                fn full_mul(self, other: $ty, carry: $ty) -> ($ty, $ty) {
-                    // this cannot overflow, the output is between 0 and 2^nbits * (2^nbits - 1)
-                    let nbits = mem::size_of::<$ty>() * 8;
-                    let v = (self as $bigty) * (other as $bigty) + (carry as $bigty);
-                    ((v >> nbits) as $ty, v as $ty)
-                }
-
-                fn full_mul_add(self, other: $ty, other2: $ty, carry: $ty) -> ($ty, $ty) {
-                    // this cannot overflow, the output is between 0 and 2^(2*nbits) - 1
-                    let nbits = mem::size_of::<$ty>() * 8;
-                    let v = (self as $bigty) * (other as $bigty) + (other2 as $bigty) +
-                            (carry as $bigty);
-                    ((v >> nbits) as $ty, v as $ty)
-                }
-
-                fn full_div_rem(self, other: $ty, borrow: $ty) -> ($ty, $ty) {
-                    debug_assert!(borrow < other);
-                    // this cannot overflow, the dividend is between 0 and other * 2^nbits - 1
-                    let nbits = mem::size_of::<$ty>() * 8;
-                    let lhs = ((borrow as $bigty) << nbits) | (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);
-//  u64: add(intrinsics::u64_add_with_overflow), mul/div(u128); // see RFC #521 for enabling this.
-}
-
-/// 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 an 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 over/underflows.
-        /// 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: base }
-            }
-
-            /// Makes a bignum from `u64` value.
-            pub fn from_u64(mut v: u64) -> $name {
-                use mem;
-
-                let mut base = [0; $n];
-                let mut sz = 0;
-                while v > 0 {
-                    base[sz] = v as $ty;
-                    v >>= mem::size_of::<$ty>() * 8;
-                    sz += 1;
-                }
-                $name { size: sz, base: base }
-            }
-
-            /// Return 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]
-            }
-
-            /// Return 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 {
-                use mem;
-
-                let digitbits = mem::size_of::<$ty>() * 8;
-                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 {
-                use mem;
-
-                // Skip over the most significant digits which are zero.
-                let digits = self.digits();
-                let zeros = digits.iter().rev().take_while(|&&x| x == 0).count();
-                let end = digits.len() - zeros;
-                let nonzero = &digits[..end];
-
-                if nonzero.is_empty() {
-                    // There are no non-zero digits, i.e. the number is zero.
-                    return 0;
-                }
-                // This could be optimized with leading_zeros() and bit shifts, but that's
-                // probably not worth the hassle.
-                let digitbits = mem::size_of::<$ty>()* 8;
-                let mut i = nonzero.len() * digitbits - 1;
-                while self.get_bit(i) == 0 {
-                    i -= 1;
-                }
-                i + 1
-            }
-
-            /// Adds `other` to itself and returns its own mutable reference.
-            pub fn add<'a>(&'a mut self, other: &$name) -> &'a mut $name {
-                use cmp;
-                use num::flt2dec::bignum::FullOps;
-
-                let mut sz = cmp::max(self.size, other.size);
-                let mut carry = false;
-                for (a, b) in self.base[..sz].iter_mut().zip(&other.base[..sz]) {
-                    let (c, v) = (*a).full_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 {
-                use num::flt2dec::bignum::FullOps;
-
-                let (mut carry, v) = self.base[0].full_add(other, false);
-                self.base[0] = v;
-                let mut i = 1;
-                while carry {
-                    let (c, v) = self.base[i].full_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 cmp;
-                use num::flt2dec::bignum::FullOps;
-
-                let sz = cmp::max(self.size, other.size);
-                let mut noborrow = true;
-                for (a, b) in self.base[..sz].iter_mut().zip(&other.base[..sz]) {
-                    let (c, v) = (*a).full_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 {
-                use num::flt2dec::bignum::FullOps;
-
-                let mut sz = self.size;
-                let mut carry = 0;
-                for a in &mut self.base[..sz] {
-                    let (c, v) = (*a).full_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 {
-                use mem;
-
-                let digitbits = mem::size_of::<$ty>() * 8;
-                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 mem;
-                use num::flt2dec::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 num::flt2dec::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 num::flt2dec::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) {
-                use mem;
-
-                // 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 = mem::size_of::<$ty>() * 8;
-                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 ::cmp::PartialEq for $name {
-            fn eq(&self, other: &$name) -> bool { self.base[..] == other.base[..] }
-        }
-
-        impl ::cmp::Eq for $name {
-        }
-
-        impl ::cmp::PartialOrd for $name {
-            fn partial_cmp(&self, other: &$name) -> ::option::Option<::cmp::Ordering> {
-                ::option::Option::Some(self.cmp(other))
-            }
-        }
-
-        impl ::cmp::Ord for $name {
-            fn cmp(&self, other: &$name) -> ::cmp::Ordering {
-                use 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 ::clone::Clone for $name {
-            fn clone(&self) -> $name {
-                $name { size: self.size, base: self.base }
-            }
-        }
-
-        impl ::fmt::Debug for $name {
-            fn fmt(&self, f: &mut ::fmt::Formatter) -> ::fmt::Result {
-                use mem;
-
-                let sz = if self.size < 1 {1} else {self.size};
-                let digitlen = mem::size_of::<$ty>() * 2;
-
-                try!(write!(f, "{:#x}", self.base[sz-1]));
-                for &v in self.base[..sz-1].iter().rev() {
-                    try!(write!(f, "_{:01$x}", v, digitlen));
-                }
-                ::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 {
-    use prelude::v1::*;
-    define_bignum!(Big8x3: type=u8, n=3);
-}
diff --git a/src/libcore/num/flt2dec/mod.rs b/src/libcore/num/flt2dec/mod.rs
index 700523e49a2..7f7c61938cb 100644
--- a/src/libcore/num/flt2dec/mod.rs
+++ b/src/libcore/num/flt2dec/mod.rs
@@ -136,7 +136,6 @@ use slice::bytes;
 pub use self::decoder::{decode, DecodableFloat, FullDecoded, Decoded};
 
 pub mod estimator;
-pub mod bignum;
 pub mod decoder;
 
 /// Digit-generation algorithms.
diff --git a/src/libcore/num/flt2dec/strategy/dragon.rs b/src/libcore/num/flt2dec/strategy/dragon.rs
index 40aa2a527db..2d68c3a6d02 100644
--- a/src/libcore/num/flt2dec/strategy/dragon.rs
+++ b/src/libcore/num/flt2dec/strategy/dragon.rs
@@ -21,8 +21,8 @@ use cmp::Ordering;
 
 use num::flt2dec::{Decoded, MAX_SIG_DIGITS, round_up};
 use num::flt2dec::estimator::estimate_scaling_factor;
-use num::flt2dec::bignum::Digit32 as Digit;
-use num::flt2dec::bignum::Big32x40 as Big;
+use num::bignum::Digit32 as Digit;
+use num::bignum::Big32x40 as Big;
 
 static POW10: [Digit; 10] = [1, 10, 100, 1000, 10000, 100000,
                              1000000, 10000000, 100000000, 1000000000];
diff --git a/src/libcore/num/flt2dec/strategy/grisu.rs b/src/libcore/num/flt2dec/strategy/grisu.rs
index b0822ca76c7..5b4b2e46478 100644
--- a/src/libcore/num/flt2dec/strategy/grisu.rs
+++ b/src/libcore/num/flt2dec/strategy/grisu.rs
@@ -18,60 +18,9 @@ Rust adaptation of Grisu3 algorithm described in [1]. It uses about
 
 use prelude::v1::*;
 
+use num::diy_float::Fp;
 use num::flt2dec::{Decoded, MAX_SIG_DIGITS, round_up};
 
-/// A custom 64-bit floating point type, representing `f * 2^e`.
-#[derive(Copy, Clone, Debug)]
-#[doc(hidden)]
-pub struct Fp {
-    /// The integer mantissa.
-    pub f: u64,
-    /// The exponent in base 2.
-    pub e: i16,
-}
-
-impl Fp {
-    /// Returns a correctly rounded product of itself and `other`.
-    pub fn mul(&self, other: &Fp) -> Fp {
-        const MASK: u64 = 0xffffffff;
-        let a = self.f >> 32;
-        let b = self.f & MASK;
-        let c = other.f >> 32;
-        let d = other.f & MASK;
-        let ac = a * c;
-        let bc = b * c;
-        let ad = a * d;
-        let bd = b * d;
-        let tmp = (bd >> 32) + (ad & MASK) + (bc & MASK) + (1 << 31) /* round */;
-        let f = ac + (ad >> 32) + (bc >> 32) + (tmp >> 32);
-        let e = self.e + other.e + 64;
-        Fp { f: f, e: e }
-    }
-
-    /// Normalizes itself so that the resulting mantissa is at least `2^63`.
-    pub fn normalize(&self) -> Fp {
-        let mut f = self.f;
-        let mut e = self.e;
-        if f >> (64 - 32) == 0 { f <<= 32; e -= 32; }
-        if f >> (64 - 16) == 0 { f <<= 16; e -= 16; }
-        if f >> (64 -  8) == 0 { f <<=  8; e -=  8; }
-        if f >> (64 -  4) == 0 { f <<=  4; e -=  4; }
-        if f >> (64 -  2) == 0 { f <<=  2; e -=  2; }
-        if f >> (64 -  1) == 0 { f <<=  1; e -=  1; }
-        debug_assert!(f >= (1 >> 63));
-        Fp { f: f, e: e }
-    }
-
-    /// Normalizes itself to have the shared exponent.
-    /// It can only decrease the exponent (and thus increase the mantissa).
-    pub fn normalize_to(&self, e: i16) -> Fp {
-        let edelta = self.e - e;
-        assert!(edelta >= 0);
-        let edelta = edelta as usize;
-        assert_eq!(self.f << edelta >> edelta, self.f);
-        Fp { f: self.f << edelta, e: e }
-    }
-}
 
 // see the comments in `format_shortest_opt` for the rationale.
 #[doc(hidden)] pub const ALPHA: i16 = -60;