From cd67ec306fda0e3d39ead0eda3de2c0b3dd696e2 Mon Sep 17 00:00:00 2001 From: Robin Kruppe Date: Sun, 20 Sep 2015 18:34:33 +0200 Subject: 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. --- src/libcore/num/bignum.rs | 497 +++++++++++++++++++++++++ src/libcore/num/dec2flt/algorithm.rs | 8 +- src/libcore/num/dec2flt/mod.rs | 3 - src/libcore/num/dec2flt/num.rs | 3 +- src/libcore/num/dec2flt/rawfp.rs | 4 +- src/libcore/num/diy_float.rs | 71 ++++ src/libcore/num/flt2dec/bignum.rs | 491 ------------------------ src/libcore/num/flt2dec/mod.rs | 1 - src/libcore/num/flt2dec/strategy/dragon.rs | 4 +- src/libcore/num/flt2dec/strategy/grisu.rs | 53 +-- src/libcore/num/mod.rs | 4 + src/libcoretest/lib.rs | 2 + src/libcoretest/num/bignum.rs | 249 +++++++++++++ src/libcoretest/num/dec2flt/rawfp.rs | 6 +- src/libcoretest/num/flt2dec/bignum.rs | 249 ------------- src/libcoretest/num/flt2dec/mod.rs | 1 - src/libcoretest/num/flt2dec/strategy/dragon.rs | 2 +- src/libcoretest/num/mod.rs | 1 + 18 files changed, 838 insertions(+), 811 deletions(-) create mode 100644 src/libcore/num/bignum.rs create mode 100644 src/libcore/num/diy_float.rs delete mode 100644 src/libcore/num/flt2dec/bignum.rs create mode 100644 src/libcoretest/num/bignum.rs delete mode 100644 src/libcoretest/num/flt2dec/bignum.rs diff --git a/src/libcore/num/bignum.rs b/src/libcore/num/bignum.rs new file mode 100644 index 00000000000..baeca6b8b49 --- /dev/null +++ b/src/libcore/num/bignum.rs @@ -0,0 +1,497 @@ +// 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 or the MIT license +// , 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. + +// This module is only for dec2flt and flt2dec, and only public because of libcoretest. +// It is not intended to ever be stabilized. +#![doc(hidden)] +#![unstable(feature = "core_private_bignum", + reason = "internal routines only exposed for testing", + issue = "0")] +#![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::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::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::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::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::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::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::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/dec2flt/algorithm.rs b/src/libcore/num/dec2flt/algorithm.rs index f166bb9b3eb..1f0f06d7461 100644 --- a/src/libcore/num/dec2flt/algorithm.rs +++ b/src/libcore/num/dec2flt/algorithm.rs @@ -10,13 +10,13 @@ //! The various algorithms from the paper. -use num::flt2dec::strategy::grisu::Fp; use prelude::v1::*; use cmp::min; use cmp::Ordering::{Less, Equal, Greater}; -use super::table; -use super::rawfp::{self, Unpacked, RawFloat, fp_to_float, next_float, prev_float}; -use super::num::{self, Big}; +use num::diy_float::Fp; +use num::dec2flt::table; +use num::dec2flt::rawfp::{self, Unpacked, RawFloat, fp_to_float, next_float, prev_float}; +use num::dec2flt::num::{self, Big}; /// Number of significand bits in Fp const P: u32 = 64; diff --git a/src/libcore/num/dec2flt/mod.rs b/src/libcore/num/dec2flt/mod.rs index 4e6b6f04e9e..55be4cd3191 100644 --- a/src/libcore/num/dec2flt/mod.rs +++ b/src/libcore/num/dec2flt/mod.rs @@ -86,9 +86,6 @@ //! "such that the exponent +/- the number of decimal digits fits into a 64 bit integer". //! Larger exponents are accepted, but we don't do arithmetic with them, they are immediately //! turned into {positive,negative} {zero,infinity}. -//! -//! FIXME: this uses several things from core::num::flt2dec, which is nonsense. Those things -//! should be moved into core::num::. #![doc(hidden)] #![unstable(feature = "dec2flt", diff --git a/src/libcore/num/dec2flt/num.rs b/src/libcore/num/dec2flt/num.rs index dcba73d7c93..81e7856633b 100644 --- a/src/libcore/num/dec2flt/num.rs +++ b/src/libcore/num/dec2flt/num.rs @@ -14,9 +14,8 @@ use prelude::v1::*; use cmp::Ordering::{self, Less, Equal, Greater}; -use num::flt2dec::bignum::Big32x40; -pub type Big = Big32x40; +pub use num::bignum::Big32x40 as Big; /// Test whether truncating all bits less significant than `ones_place` introduces /// a relative error less, equal, or greater than 0.5 ULP. diff --git a/src/libcore/num/dec2flt/rawfp.rs b/src/libcore/num/dec2flt/rawfp.rs index 830d2dad42f..be61653c379 100644 --- a/src/libcore/num/dec2flt/rawfp.rs +++ b/src/libcore/num/dec2flt/rawfp.rs @@ -33,10 +33,10 @@ use cmp::Ordering::{Less, Equal, Greater}; use ops::{Mul, Div, Neg}; use fmt::{Debug, LowerExp}; use mem::transmute; -use num::flt2dec::strategy::grisu::Fp; +use num::diy_float::Fp; use num::FpCategory::{Infinite, Zero, Subnormal, Normal, Nan}; use num::Float; -use super::num::{self, Big}; +use num::dec2flt::num::{self, Big}; #[derive(Copy, Clone, Debug)] pub struct Unpacked { diff --git a/src/libcore/num/diy_float.rs b/src/libcore/num/diy_float.rs new file mode 100644 index 00000000000..7c369ee3b3b --- /dev/null +++ b/src/libcore/num/diy_float.rs @@ -0,0 +1,71 @@ +// 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 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Extended precision "soft float", for internal use only. + +// This module is only for dec2flt and flt2dec, and only public because of libcoretest. +// It is not intended to ever be stabilized. +#![doc(hidden)] +#![unstable(feature = "core_private_diy_float", + reason = "internal routines only exposed for testing", + issue = "0")] + +/// 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 } + } +} 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 or the MIT license -// , 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; diff --git a/src/libcore/num/mod.rs b/src/libcore/num/mod.rs index 127f8d3b5a2..6507bb7bf8c 100644 --- a/src/libcore/num/mod.rs +++ b/src/libcore/num/mod.rs @@ -43,8 +43,12 @@ use slice::SliceExt; pub struct Wrapping(#[stable(feature = "rust1", since = "1.0.0")] pub T); pub mod wrapping; + +// All these modules are technically private and only exposed for libcoretest: pub mod flt2dec; pub mod dec2flt; +pub mod bignum; +pub mod diy_float; /// Types that have a "zero" value. /// diff --git a/src/libcoretest/lib.rs b/src/libcoretest/lib.rs index e87a179f58d..22b285b0343 100644 --- a/src/libcoretest/lib.rs +++ b/src/libcoretest/lib.rs @@ -15,6 +15,8 @@ #![feature(const_fn)] #![feature(core)] #![feature(core_float)] +#![feature(core_private_bignum)] +#![feature(core_private_diy_float)] #![feature(dec2flt)] #![feature(decode_utf16)] #![feature(fixed_size_array)] diff --git a/src/libcoretest/num/bignum.rs b/src/libcoretest/num/bignum.rs new file mode 100644 index 00000000000..58a9dd1b128 --- /dev/null +++ b/src/libcoretest/num/bignum.rs @@ -0,0 +1,249 @@ +// 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 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use std::prelude::v1::*; +use core::num::bignum::tests::Big8x3 as Big; + +#[test] +#[should_panic] +fn test_from_u64_overflow() { + Big::from_u64(0x1000000); +} + +#[test] +fn test_add() { + assert_eq!(*Big::from_small(3).add(&Big::from_small(4)), Big::from_small(7)); + assert_eq!(*Big::from_small(3).add(&Big::from_small(0)), Big::from_small(3)); + assert_eq!(*Big::from_small(0).add(&Big::from_small(3)), Big::from_small(3)); + assert_eq!(*Big::from_small(3).add(&Big::from_u64(0xfffe)), Big::from_u64(0x10001)); + assert_eq!(*Big::from_u64(0xfedc).add(&Big::from_u64(0x789)), Big::from_u64(0x10665)); + assert_eq!(*Big::from_u64(0x789).add(&Big::from_u64(0xfedc)), Big::from_u64(0x10665)); +} + +#[test] +#[should_panic] +fn test_add_overflow_1() { + Big::from_small(1).add(&Big::from_u64(0xffffff)); +} + +#[test] +#[should_panic] +fn test_add_overflow_2() { + Big::from_u64(0xffffff).add(&Big::from_small(1)); +} + +#[test] +fn test_add_small() { + assert_eq!(*Big::from_small(3).add_small(4), Big::from_small(7)); + assert_eq!(*Big::from_small(3).add_small(0), Big::from_small(3)); + assert_eq!(*Big::from_small(0).add_small(3), Big::from_small(3)); + assert_eq!(*Big::from_small(7).add_small(250), Big::from_u64(257)); + assert_eq!(*Big::from_u64(0x7fff).add_small(1), Big::from_u64(0x8000)); + assert_eq!(*Big::from_u64(0x2ffe).add_small(0x35), Big::from_u64(0x3033)); + assert_eq!(*Big::from_small(0xdc).add_small(0x89), Big::from_u64(0x165)); +} + +#[test] +#[should_panic] +fn test_add_small_overflow() { + Big::from_u64(0xffffff).add_small(1); +} + +#[test] +fn test_sub() { + assert_eq!(*Big::from_small(7).sub(&Big::from_small(4)), Big::from_small(3)); + assert_eq!(*Big::from_u64(0x10665).sub(&Big::from_u64(0x789)), Big::from_u64(0xfedc)); + assert_eq!(*Big::from_u64(0x10665).sub(&Big::from_u64(0xfedc)), Big::from_u64(0x789)); + assert_eq!(*Big::from_u64(0x10665).sub(&Big::from_u64(0x10664)), Big::from_small(1)); + assert_eq!(*Big::from_u64(0x10665).sub(&Big::from_u64(0x10665)), Big::from_small(0)); +} + +#[test] +#[should_panic] +fn test_sub_underflow_1() { + Big::from_u64(0x10665).sub(&Big::from_u64(0x10666)); +} + +#[test] +#[should_panic] +fn test_sub_underflow_2() { + Big::from_small(0).sub(&Big::from_u64(0x123456)); +} + +#[test] +fn test_mul_small() { + assert_eq!(*Big::from_small(7).mul_small(5), Big::from_small(35)); + assert_eq!(*Big::from_small(0xff).mul_small(0xff), Big::from_u64(0xfe01)); + assert_eq!(*Big::from_u64(0xffffff/13).mul_small(13), Big::from_u64(0xffffff)); +} + +#[test] +#[should_panic] +fn test_mul_small_overflow() { + Big::from_u64(0x800000).mul_small(2); +} + +#[test] +fn test_mul_pow2() { + assert_eq!(*Big::from_small(0x7).mul_pow2(4), Big::from_small(0x70)); + assert_eq!(*Big::from_small(0xff).mul_pow2(1), Big::from_u64(0x1fe)); + assert_eq!(*Big::from_small(0xff).mul_pow2(12), Big::from_u64(0xff000)); + assert_eq!(*Big::from_small(0x1).mul_pow2(23), Big::from_u64(0x800000)); + assert_eq!(*Big::from_u64(0x123).mul_pow2(0), Big::from_u64(0x123)); + assert_eq!(*Big::from_u64(0x123).mul_pow2(7), Big::from_u64(0x9180)); + assert_eq!(*Big::from_u64(0x123).mul_pow2(15), Big::from_u64(0x918000)); + assert_eq!(*Big::from_small(0).mul_pow2(23), Big::from_small(0)); +} + +#[test] +#[should_panic] +fn test_mul_pow2_overflow_1() { + Big::from_u64(0x1).mul_pow2(24); +} + +#[test] +#[should_panic] +fn test_mul_pow2_overflow_2() { + Big::from_u64(0x123).mul_pow2(16); +} + +#[test] +fn test_mul_pow5() { + assert_eq!(*Big::from_small(42).mul_pow5(0), Big::from_small(42)); + assert_eq!(*Big::from_small(1).mul_pow5(2), Big::from_small(25)); + assert_eq!(*Big::from_small(1).mul_pow5(4), Big::from_u64(25 * 25)); + assert_eq!(*Big::from_small(4).mul_pow5(3), Big::from_u64(500)); + assert_eq!(*Big::from_small(140).mul_pow5(2), Big::from_u64(25 * 140)); + assert_eq!(*Big::from_small(25).mul_pow5(1), Big::from_small(125)); + assert_eq!(*Big::from_small(125).mul_pow5(7), Big::from_u64(9765625)); + assert_eq!(*Big::from_small(0).mul_pow5(127), Big::from_small(0)); +} + +#[test] +#[should_panic] +fn test_mul_pow5_overflow_1() { + Big::from_small(1).mul_pow5(12); +} + +#[test] +#[should_panic] +fn test_mul_pow5_overflow_2() { + Big::from_small(230).mul_pow5(8); +} + +#[test] +fn test_mul_digits() { + assert_eq!(*Big::from_small(3).mul_digits(&[5]), Big::from_small(15)); + assert_eq!(*Big::from_small(0xff).mul_digits(&[0xff]), Big::from_u64(0xfe01)); + assert_eq!(*Big::from_u64(0x123).mul_digits(&[0x56, 0x4]), Big::from_u64(0x4edc2)); + assert_eq!(*Big::from_u64(0x12345).mul_digits(&[0x67]), Big::from_u64(0x7530c3)); + assert_eq!(*Big::from_small(0x12).mul_digits(&[0x67, 0x45, 0x3]), Big::from_u64(0x3ae13e)); + assert_eq!(*Big::from_u64(0xffffff/13).mul_digits(&[13]), Big::from_u64(0xffffff)); + assert_eq!(*Big::from_small(13).mul_digits(&[0x3b, 0xb1, 0x13]), Big::from_u64(0xffffff)); +} + +#[test] +#[should_panic] +fn test_mul_digits_overflow_1() { + Big::from_u64(0x800000).mul_digits(&[2]); +} + +#[test] +#[should_panic] +fn test_mul_digits_overflow_2() { + Big::from_u64(0x1000).mul_digits(&[0, 0x10]); +} + +#[test] +fn test_div_rem_small() { + let as_val = |(q, r): (&mut Big, u8)| (q.clone(), r); + assert_eq!(as_val(Big::from_small(0xff).div_rem_small(15)), (Big::from_small(17), 0)); + assert_eq!(as_val(Big::from_small(0xff).div_rem_small(16)), (Big::from_small(15), 15)); + assert_eq!(as_val(Big::from_small(3).div_rem_small(40)), (Big::from_small(0), 3)); + assert_eq!(as_val(Big::from_u64(0xffffff).div_rem_small(123)), + (Big::from_u64(0xffffff / 123), (0xffffffu64 % 123) as u8)); + assert_eq!(as_val(Big::from_u64(0x10000).div_rem_small(123)), + (Big::from_u64(0x10000 / 123), (0x10000u64 % 123) as u8)); +} + +#[test] +fn test_div_rem() { + fn div_rem(n: u64, d: u64) -> (Big, Big) { + let mut q = Big::from_small(42); + let mut r = Big::from_small(42); + Big::from_u64(n).div_rem(&Big::from_u64(d), &mut q, &mut r); + (q, r) + } + assert_eq!(div_rem(1, 1), (Big::from_small(1), Big::from_small(0))); + assert_eq!(div_rem(4, 3), (Big::from_small(1), Big::from_small(1))); + assert_eq!(div_rem(1, 7), (Big::from_small(0), Big::from_small(1))); + assert_eq!(div_rem(45, 9), (Big::from_small(5), Big::from_small(0))); + assert_eq!(div_rem(103, 9), (Big::from_small(11), Big::from_small(4))); + assert_eq!(div_rem(123456, 77), (Big::from_u64(1603), Big::from_small(25))); + assert_eq!(div_rem(0xffff, 1), (Big::from_u64(0xffff), Big::from_small(0))); + assert_eq!(div_rem(0xeeee, 0xffff), (Big::from_small(0), Big::from_u64(0xeeee))); + assert_eq!(div_rem(2_000_000, 2), (Big::from_u64(1_000_000), Big::from_u64(0))); +} + +#[test] +fn test_is_zero() { + assert!(Big::from_small(0).is_zero()); + assert!(!Big::from_small(3).is_zero()); + assert!(!Big::from_u64(0x123).is_zero()); + assert!(!Big::from_u64(0xffffff).sub(&Big::from_u64(0xfffffe)).is_zero()); + assert!(Big::from_u64(0xffffff).sub(&Big::from_u64(0xffffff)).is_zero()); +} + +#[test] +fn test_get_bit() { + let x = Big::from_small(0b1101); + assert_eq!(x.get_bit(0), 1); + assert_eq!(x.get_bit(1), 0); + assert_eq!(x.get_bit(2), 1); + assert_eq!(x.get_bit(3), 1); + let y = Big::from_u64(1 << 15); + assert_eq!(y.get_bit(14), 0); + assert_eq!(y.get_bit(15), 1); + assert_eq!(y.get_bit(16), 0); +} + +#[test] +#[should_panic] +fn test_get_bit_out_of_range() { + Big::from_small(42).get_bit(24); +} + +#[test] +fn test_bit_length() { + assert_eq!(Big::from_small(0).bit_length(), 0); + assert_eq!(Big::from_small(1).bit_length(), 1); + assert_eq!(Big::from_small(5).bit_length(), 3); + assert_eq!(Big::from_small(0x18).bit_length(), 5); + assert_eq!(Big::from_u64(0x4073).bit_length(), 15); + assert_eq!(Big::from_u64(0xffffff).bit_length(), 24); +} + +#[test] +fn test_ord() { + assert!(Big::from_u64(0) < Big::from_u64(0xffffff)); + assert!(Big::from_u64(0x102) < Big::from_u64(0x201)); +} + +#[test] +fn test_fmt() { + assert_eq!(format!("{:?}", Big::from_u64(0)), "0x0"); + assert_eq!(format!("{:?}", Big::from_u64(0x1)), "0x1"); + assert_eq!(format!("{:?}", Big::from_u64(0x12)), "0x12"); + assert_eq!(format!("{:?}", Big::from_u64(0x123)), "0x1_23"); + assert_eq!(format!("{:?}", Big::from_u64(0x1234)), "0x12_34"); + assert_eq!(format!("{:?}", Big::from_u64(0x12345)), "0x1_23_45"); + assert_eq!(format!("{:?}", Big::from_u64(0x123456)), "0x12_34_56"); +} + diff --git a/src/libcoretest/num/dec2flt/rawfp.rs b/src/libcoretest/num/dec2flt/rawfp.rs index a40d360f105..4c0a403e574 100644 --- a/src/libcoretest/num/dec2flt/rawfp.rs +++ b/src/libcoretest/num/dec2flt/rawfp.rs @@ -9,14 +9,14 @@ // except according to those terms. use std::f64; -use core::num::flt2dec::strategy::grisu::Fp; +use core::num::diy_float::Fp; use core::num::dec2flt::rawfp::{fp_to_float, prev_float, next_float, round_normal}; #[test] fn fp_to_float_half_to_even() { fn is_normalized(sig: u64) -> bool { - // intentionally written without {min,max}_sig() as a sanity check - sig >> 52 == 1 && sig >> 53 == 0 + // intentionally written without {min,max}_sig() as a sanity check + sig >> 52 == 1 && sig >> 53 == 0 } fn conv(sig: u64) -> u64 { diff --git a/src/libcoretest/num/flt2dec/bignum.rs b/src/libcoretest/num/flt2dec/bignum.rs deleted file mode 100644 index 31065b2898f..00000000000 --- a/src/libcoretest/num/flt2dec/bignum.rs +++ /dev/null @@ -1,249 +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 or the MIT license -// , at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -use std::prelude::v1::*; -use core::num::flt2dec::bignum::tests::Big8x3 as Big; - -#[test] -#[should_panic] -fn test_from_u64_overflow() { - Big::from_u64(0x1000000); -} - -#[test] -fn test_add() { - assert_eq!(*Big::from_small(3).add(&Big::from_small(4)), Big::from_small(7)); - assert_eq!(*Big::from_small(3).add(&Big::from_small(0)), Big::from_small(3)); - assert_eq!(*Big::from_small(0).add(&Big::from_small(3)), Big::from_small(3)); - assert_eq!(*Big::from_small(3).add(&Big::from_u64(0xfffe)), Big::from_u64(0x10001)); - assert_eq!(*Big::from_u64(0xfedc).add(&Big::from_u64(0x789)), Big::from_u64(0x10665)); - assert_eq!(*Big::from_u64(0x789).add(&Big::from_u64(0xfedc)), Big::from_u64(0x10665)); -} - -#[test] -#[should_panic] -fn test_add_overflow_1() { - Big::from_small(1).add(&Big::from_u64(0xffffff)); -} - -#[test] -#[should_panic] -fn test_add_overflow_2() { - Big::from_u64(0xffffff).add(&Big::from_small(1)); -} - -#[test] -fn test_add_small() { - assert_eq!(*Big::from_small(3).add_small(4), Big::from_small(7)); - assert_eq!(*Big::from_small(3).add_small(0), Big::from_small(3)); - assert_eq!(*Big::from_small(0).add_small(3), Big::from_small(3)); - assert_eq!(*Big::from_small(7).add_small(250), Big::from_u64(257)); - assert_eq!(*Big::from_u64(0x7fff).add_small(1), Big::from_u64(0x8000)); - assert_eq!(*Big::from_u64(0x2ffe).add_small(0x35), Big::from_u64(0x3033)); - assert_eq!(*Big::from_small(0xdc).add_small(0x89), Big::from_u64(0x165)); -} - -#[test] -#[should_panic] -fn test_add_small_overflow() { - Big::from_u64(0xffffff).add_small(1); -} - -#[test] -fn test_sub() { - assert_eq!(*Big::from_small(7).sub(&Big::from_small(4)), Big::from_small(3)); - assert_eq!(*Big::from_u64(0x10665).sub(&Big::from_u64(0x789)), Big::from_u64(0xfedc)); - assert_eq!(*Big::from_u64(0x10665).sub(&Big::from_u64(0xfedc)), Big::from_u64(0x789)); - assert_eq!(*Big::from_u64(0x10665).sub(&Big::from_u64(0x10664)), Big::from_small(1)); - assert_eq!(*Big::from_u64(0x10665).sub(&Big::from_u64(0x10665)), Big::from_small(0)); -} - -#[test] -#[should_panic] -fn test_sub_underflow_1() { - Big::from_u64(0x10665).sub(&Big::from_u64(0x10666)); -} - -#[test] -#[should_panic] -fn test_sub_underflow_2() { - Big::from_small(0).sub(&Big::from_u64(0x123456)); -} - -#[test] -fn test_mul_small() { - assert_eq!(*Big::from_small(7).mul_small(5), Big::from_small(35)); - assert_eq!(*Big::from_small(0xff).mul_small(0xff), Big::from_u64(0xfe01)); - assert_eq!(*Big::from_u64(0xffffff/13).mul_small(13), Big::from_u64(0xffffff)); -} - -#[test] -#[should_panic] -fn test_mul_small_overflow() { - Big::from_u64(0x800000).mul_small(2); -} - -#[test] -fn test_mul_pow2() { - assert_eq!(*Big::from_small(0x7).mul_pow2(4), Big::from_small(0x70)); - assert_eq!(*Big::from_small(0xff).mul_pow2(1), Big::from_u64(0x1fe)); - assert_eq!(*Big::from_small(0xff).mul_pow2(12), Big::from_u64(0xff000)); - assert_eq!(*Big::from_small(0x1).mul_pow2(23), Big::from_u64(0x800000)); - assert_eq!(*Big::from_u64(0x123).mul_pow2(0), Big::from_u64(0x123)); - assert_eq!(*Big::from_u64(0x123).mul_pow2(7), Big::from_u64(0x9180)); - assert_eq!(*Big::from_u64(0x123).mul_pow2(15), Big::from_u64(0x918000)); - assert_eq!(*Big::from_small(0).mul_pow2(23), Big::from_small(0)); -} - -#[test] -#[should_panic] -fn test_mul_pow2_overflow_1() { - Big::from_u64(0x1).mul_pow2(24); -} - -#[test] -#[should_panic] -fn test_mul_pow2_overflow_2() { - Big::from_u64(0x123).mul_pow2(16); -} - -#[test] -fn test_mul_pow5() { - assert_eq!(*Big::from_small(42).mul_pow5(0), Big::from_small(42)); - assert_eq!(*Big::from_small(1).mul_pow5(2), Big::from_small(25)); - assert_eq!(*Big::from_small(1).mul_pow5(4), Big::from_u64(25 * 25)); - assert_eq!(*Big::from_small(4).mul_pow5(3), Big::from_u64(500)); - assert_eq!(*Big::from_small(140).mul_pow5(2), Big::from_u64(25 * 140)); - assert_eq!(*Big::from_small(25).mul_pow5(1), Big::from_small(125)); - assert_eq!(*Big::from_small(125).mul_pow5(7), Big::from_u64(9765625)); - assert_eq!(*Big::from_small(0).mul_pow5(127), Big::from_small(0)); -} - -#[test] -#[should_panic] -fn test_mul_pow5_overflow_1() { - Big::from_small(1).mul_pow5(12); -} - -#[test] -#[should_panic] -fn test_mul_pow5_overflow_2() { - Big::from_small(230).mul_pow5(8); -} - -#[test] -fn test_mul_digits() { - assert_eq!(*Big::from_small(3).mul_digits(&[5]), Big::from_small(15)); - assert_eq!(*Big::from_small(0xff).mul_digits(&[0xff]), Big::from_u64(0xfe01)); - assert_eq!(*Big::from_u64(0x123).mul_digits(&[0x56, 0x4]), Big::from_u64(0x4edc2)); - assert_eq!(*Big::from_u64(0x12345).mul_digits(&[0x67]), Big::from_u64(0x7530c3)); - assert_eq!(*Big::from_small(0x12).mul_digits(&[0x67, 0x45, 0x3]), Big::from_u64(0x3ae13e)); - assert_eq!(*Big::from_u64(0xffffff/13).mul_digits(&[13]), Big::from_u64(0xffffff)); - assert_eq!(*Big::from_small(13).mul_digits(&[0x3b, 0xb1, 0x13]), Big::from_u64(0xffffff)); -} - -#[test] -#[should_panic] -fn test_mul_digits_overflow_1() { - Big::from_u64(0x800000).mul_digits(&[2]); -} - -#[test] -#[should_panic] -fn test_mul_digits_overflow_2() { - Big::from_u64(0x1000).mul_digits(&[0, 0x10]); -} - -#[test] -fn test_div_rem_small() { - let as_val = |(q, r): (&mut Big, u8)| (q.clone(), r); - assert_eq!(as_val(Big::from_small(0xff).div_rem_small(15)), (Big::from_small(17), 0)); - assert_eq!(as_val(Big::from_small(0xff).div_rem_small(16)), (Big::from_small(15), 15)); - assert_eq!(as_val(Big::from_small(3).div_rem_small(40)), (Big::from_small(0), 3)); - assert_eq!(as_val(Big::from_u64(0xffffff).div_rem_small(123)), - (Big::from_u64(0xffffff / 123), (0xffffffu64 % 123) as u8)); - assert_eq!(as_val(Big::from_u64(0x10000).div_rem_small(123)), - (Big::from_u64(0x10000 / 123), (0x10000u64 % 123) as u8)); -} - -#[test] -fn test_div_rem() { - fn div_rem(n: u64, d: u64) -> (Big, Big) { - let mut q = Big::from_small(42); - let mut r = Big::from_small(42); - Big::from_u64(n).div_rem(&Big::from_u64(d), &mut q, &mut r); - (q, r) - } - assert_eq!(div_rem(1, 1), (Big::from_small(1), Big::from_small(0))); - assert_eq!(div_rem(4, 3), (Big::from_small(1), Big::from_small(1))); - assert_eq!(div_rem(1, 7), (Big::from_small(0), Big::from_small(1))); - assert_eq!(div_rem(45, 9), (Big::from_small(5), Big::from_small(0))); - assert_eq!(div_rem(103, 9), (Big::from_small(11), Big::from_small(4))); - assert_eq!(div_rem(123456, 77), (Big::from_u64(1603), Big::from_small(25))); - assert_eq!(div_rem(0xffff, 1), (Big::from_u64(0xffff), Big::from_small(0))); - assert_eq!(div_rem(0xeeee, 0xffff), (Big::from_small(0), Big::from_u64(0xeeee))); - assert_eq!(div_rem(2_000_000, 2), (Big::from_u64(1_000_000), Big::from_u64(0))); -} - -#[test] -fn test_is_zero() { - assert!(Big::from_small(0).is_zero()); - assert!(!Big::from_small(3).is_zero()); - assert!(!Big::from_u64(0x123).is_zero()); - assert!(!Big::from_u64(0xffffff).sub(&Big::from_u64(0xfffffe)).is_zero()); - assert!(Big::from_u64(0xffffff).sub(&Big::from_u64(0xffffff)).is_zero()); -} - -#[test] -fn test_get_bit() { - let x = Big::from_small(0b1101); - assert_eq!(x.get_bit(0), 1); - assert_eq!(x.get_bit(1), 0); - assert_eq!(x.get_bit(2), 1); - assert_eq!(x.get_bit(3), 1); - let y = Big::from_u64(1 << 15); - assert_eq!(y.get_bit(14), 0); - assert_eq!(y.get_bit(15), 1); - assert_eq!(y.get_bit(16), 0); -} - -#[test] -#[should_panic] -fn test_get_bit_out_of_range() { - Big::from_small(42).get_bit(24); -} - -#[test] -fn test_bit_length() { - assert_eq!(Big::from_small(0).bit_length(), 0); - assert_eq!(Big::from_small(1).bit_length(), 1); - assert_eq!(Big::from_small(5).bit_length(), 3); - assert_eq!(Big::from_small(0x18).bit_length(), 5); - assert_eq!(Big::from_u64(0x4073).bit_length(), 15); - assert_eq!(Big::from_u64(0xffffff).bit_length(), 24); -} - -#[test] -fn test_ord() { - assert!(Big::from_u64(0) < Big::from_u64(0xffffff)); - assert!(Big::from_u64(0x102) < Big::from_u64(0x201)); -} - -#[test] -fn test_fmt() { - assert_eq!(format!("{:?}", Big::from_u64(0)), "0x0"); - assert_eq!(format!("{:?}", Big::from_u64(0x1)), "0x1"); - assert_eq!(format!("{:?}", Big::from_u64(0x12)), "0x12"); - assert_eq!(format!("{:?}", Big::from_u64(0x123)), "0x1_23"); - assert_eq!(format!("{:?}", Big::from_u64(0x1234)), "0x12_34"); - assert_eq!(format!("{:?}", Big::from_u64(0x12345)), "0x1_23_45"); - assert_eq!(format!("{:?}", Big::from_u64(0x123456)), "0x12_34_56"); -} - diff --git a/src/libcoretest/num/flt2dec/mod.rs b/src/libcoretest/num/flt2dec/mod.rs index 8ae33a44202..309bf6d8192 100644 --- a/src/libcoretest/num/flt2dec/mod.rs +++ b/src/libcoretest/num/flt2dec/mod.rs @@ -23,7 +23,6 @@ use core::num::flt2dec::{to_shortest_str, to_shortest_exp_str, pub use test::Bencher; mod estimator; -mod bignum; mod strategy { mod dragon; mod grisu; diff --git a/src/libcoretest/num/flt2dec/strategy/dragon.rs b/src/libcoretest/num/flt2dec/strategy/dragon.rs index f3ddc370d1e..79dcca7671a 100644 --- a/src/libcoretest/num/flt2dec/strategy/dragon.rs +++ b/src/libcoretest/num/flt2dec/strategy/dragon.rs @@ -12,7 +12,7 @@ use std::prelude::v1::*; use std::{i16, f64}; use super::super::*; use core::num::flt2dec::*; -use core::num::flt2dec::bignum::Big32x40 as Big; +use core::num::bignum::Big32x40 as Big; use core::num::flt2dec::strategy::dragon::*; #[test] diff --git a/src/libcoretest/num/mod.rs b/src/libcoretest/num/mod.rs index 9f9d2a4ca16..f57c54faf28 100644 --- a/src/libcoretest/num/mod.rs +++ b/src/libcoretest/num/mod.rs @@ -31,6 +31,7 @@ mod u64; mod flt2dec; mod dec2flt; +mod bignum; /// Helper function for testing numeric operations pub fn test_num(ten: T, two: T) where -- cgit 1.4.1-3-g733a5