1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
//! 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 coretests.
// It is not intended to ever be stabilized.
#![doc(hidden)]
#![unstable(
    feature = "core_private_bignum",
    reason = "internal routines only exposed for testing",
    issue = "none"
)]
#![macro_use]

use crate::intrinsics;

/// Arithmetic operations required by bignums.
pub trait FullOps: Sized {
    /// 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) = intrinsics::add_with_overflow(self, other);
                    let (v, carry2) = intrinsics::add_with_overflow(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)`.
                    // FIXME: will LLVM optimize this into ADC or similar?
                    let v = (self as $bigty) * (other as $bigty) + (carry as $bigty);
                    ((v >> <$ty>::BITS) 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^nbits * (2^nbits - 1)`.
                    let v = (self as $bigty) * (other as $bigty) + (other2 as $bigty) +
                            (carry as $bigty);
                    ((v >> <$ty>::BITS) as $ty, v as $ty)
                }

                fn full_div_rem(self, other: $ty, borrow: $ty) -> ($ty, $ty) {
                    debug_assert!(borrow < other);
                    // This cannot overflow; the output is between `0` and `other * (2^nbits - 1)`.
                    let lhs = ((borrow as $bigty) << <$ty>::BITS) | (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);
    // See RFC #521 for enabling this.
    // u64: add(intrinsics::u64_add_with_overflow), mul/div(u128);
}

/// 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 a 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 overflows.
        /// 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 }
            }

            /// Makes a bignum from `u64` value.
            pub fn from_u64(mut v: u64) -> $name {
                let mut base = [0; $n];
                let mut sz = 0;
                while v > 0 {
                    base[sz] = v as $ty;
                    v >>= <$ty>::BITS;
                    sz += 1;
                }
                $name { size: sz, base }
            }

            /// Returns 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]
            }

            /// Returns 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 {
                let digitbits = <$ty>::BITS as usize;
                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 {
                // 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 = <$ty>::BITS as usize;
                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 crate::cmp;
                use crate::iter;
                use crate::num::bignum::FullOps;

                let mut sz = cmp::max(self.size, other.size);
                let mut carry = false;
                for (a, b) in iter::zip(&mut self.base[..sz], &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 crate::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 crate::cmp;
                use crate::iter;
                use crate::num::bignum::FullOps;

                let sz = cmp::max(self.size, other.size);
                let mut noborrow = true;
                for (a, b) in iter::zip(&mut self.base[..sz], &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 crate::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 {
                let digitbits = <$ty>::BITS as usize;
                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 crate::mem;
                use crate::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 crate::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 crate::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) {
                // 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 = <$ty>::BITS as usize;
                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 crate::cmp::PartialEq for $name {
            fn eq(&self, other: &$name) -> bool {
                self.base[..] == other.base[..]
            }
        }

        impl crate::cmp::Eq for $name {}

        impl crate::cmp::PartialOrd for $name {
            fn partial_cmp(&self, other: &$name) -> crate::option::Option<crate::cmp::Ordering> {
                crate::option::Option::Some(self.cmp(other))
            }
        }

        impl crate::cmp::Ord for $name {
            fn cmp(&self, other: &$name) -> crate::cmp::Ordering {
                use crate::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 crate::clone::Clone for $name {
            fn clone(&self) -> Self {
                Self { size: self.size, base: self.base }
            }
        }

        impl crate::fmt::Debug for $name {
            fn fmt(&self, f: &mut crate::fmt::Formatter<'_>) -> crate::fmt::Result {
                let sz = if self.size < 1 { 1 } else { self.size };
                let digitlen = <$ty>::BITS as usize / 4;

                write!(f, "{:#x}", self.base[sz - 1])?;
                for &v in self.base[..sz - 1].iter().rev() {
                    write!(f, "_{:01$x}", v, digitlen)?;
                }
                crate::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 {
    define_bignum!(Big8x3: type=u8, n=3);
}