Add various methods to Bignum:

- Exposing digits and individual bits
- Counting the number of bits
- Add small (digit-sized) values
- Multiplication by power of 5
- Division with remainder

All are necessary for decimal to floating point conversions.
All but the most trivial ones come with tests.

1 files changed, 141 insertions, 5 deletions

diff --git a/src/libcore/num/flt2dec/bignum.rs b/src/libcore/num/flt2dec/bignum.rs
index 33c5a3ded98..15980f925fa 100644
--- a/src/libcore/num/flt2dec/bignum.rs
+++ b/src/libcore/num/flt2dec/bignum.rs
@@ -13,7 +13,7 @@
 //! 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 formatting and parsing all possible finite `f64` values.
+//! 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
@@ -92,6 +92,14 @@ impl_full_ops! {
 //  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.
@@ -135,9 +143,53 @@ macro_rules! define_bignum {
                 $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.base[..self.size].iter().all(|&v| v == 0)
+                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;
+
+                let digitbits = mem::size_of::<$ty>()* 8;
+                // Skip over the most significant digits which are zero.
+                let nonzero = match self.digits().iter().rposition(|&x| x != 0) {
+                    Some(n) => {
+                        let end = self.size - n;
+                        &self.digits()[..end]
+                    }
+                    None => {
+                        // 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 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.
@@ -160,6 +212,24 @@ macro_rules! define_bignum {
                 self
             }
 
+            pub fn add_small<'a>(&'a mut self, other: $ty) -> &'a 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;
@@ -238,6 +308,34 @@ macro_rules! define_bignum {
                 self
             }
 
+            /// Multiplies itself by `5^e` and returns its own mutable reference.
+            pub fn mul_pow5<'a>(&'a mut self, mut e: usize) -> &'a 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.
@@ -269,9 +367,9 @@ macro_rules! define_bignum {
 
                 let mut ret = [0; $n];
                 let retsz = if self.size < other.len() {
-                    mul_inner(&mut ret, &self.base[..self.size], other)
+                    mul_inner(&mut ret, &self.digits(), other)
                 } else {
-                    mul_inner(&mut ret, other, &self.base[..self.size])
+                    mul_inner(&mut ret, other, &self.digits())
                 };
                 self.base = ret;
                 self.size = retsz;
@@ -294,6 +392,45 @@ macro_rules! define_bignum {
                 }
                 (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 {
@@ -355,4 +492,3 @@ pub mod tests {
     use prelude::v1::*;
     define_bignum!(Big8x3: type=u8, n=3);
 }
-