//! 自定义任意精度数字 (bignum) 的实现。
//!
//! 这样做是为了避免以分配堆内存为代价来避免堆分配。
//! 最常用的 bignum 类型 `Big32x40` 受 32×40=1,280 位的限制，最多占用 160 个字节的栈内存。
//! 对于往返所有可能的有限 `f64` 值而言，这绰绰有余。
//!
//! 原则上，可以为不同的输入使用多个 bignum 类型，但是我们这样做并不是为了避免代码膨胀。
//!
//! 仍然会跟踪每个 bignum 的实际用法，因此通常没有关系。
//!

// 该模块仅用于 dec2flt 和 flt2dec，并且由于 coretests 而仅用于公共模块。
// 它永远都不会稳定下来。
#![doc(hidden)]
#![unstable(
    feature = "core_private_bignum",
    reason = "internal routines only exposed for testing",
    issue = "none"
)]
#![macro_use]

/// bignums 需要的算术运算。
pub trait FullOps: Sized {
    /// 返回 `(carry', v')`，使得 `carry'*2^W + v' = self* other + other2 + carry`，其中 `W` 是 `Self` 中的位数。
    ///
    fn full_mul_add(self, other: Self, other2: Self, carry: Self) -> (Self /* carry */, Self);

    /// 返回 `(quo, rem)`，使得 `borrow *2^W + self = quo* other + rem` 和 `0 <= rem < other`，其中 `W` 是 `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_mul_add(self, other: $ty, other2: $ty, carry: $ty) -> ($ty, $ty) {
                    // 这不会溢出；
                    // 输出在 `0` 和 `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);
                    // 这不会溢出； 输出在 `0` 和 `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);
    // 有关启用此功能的信息，请参见 RFC #521。
    // u64: add(intrinsics::u64_add_with_overflow), mul/div(u128);
}

/// 5 的幂表可用数字表示。具体来说，最大的 {u8, u16, u32} 值是 5 的幂，再加上相应的指数。
/// 在 `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) => {
        /// 栈分配的任意精度 (达到一定限制) 整数。
        ///
        /// 这由给定类型 ("digit") 的固定大小的数组支持。
        /// 尽管数组不是很大 (通常为几百个字节)，但不计后果地复制它可能会导致性能下降。
        ///
        /// 因此，这不是 `Copy`。
        ///
        /// 发生溢出时，bignums panic 可以使用所有操作。
        /// 调用者负责使用足够大的 bignum 类型。
        pub struct $name {
            /// 一加偏移量到正在使用的最大 "digit"。
            /// 这不会减少，因此请注意计算顺序。
            /// `base[size..]` 应为零。
            size: usize,
            /// Digits.
            /// `[a, b, c, ...]` 代表 `a + b*2^W + c*2^(2W) + ...`，其中 `W` 是数字类型中的位数。
            base: [$ty; $n],
        }

        impl $name {
            /// 从一位数产生一个大数。
            pub fn from_small(v: $ty) -> $name {
                let mut base = [0; $n];
                base[0] = v;
                $name { size: 1, base }
            }

            /// 从 `u64` 值得到一个大数。
            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 }
            }

            /// 返回内部数字作为切片 `[a, b, c, ...]`，以使数值为 `a + b *2^W + c* 2^(2W) + ...`，其中 `W` 是数字类型中的位数。
            ///
            ///
            pub fn digits(&self) -> &[$ty] {
                &self.base[..self.size]
            }

            /// 返回第 i 位，其中位 0 是最低有效位。
            /// 换句话说，钻头的重量为 `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
            }

            /// 如果 bignum 为零，则返回 `true`。
            pub fn is_zero(&self) -> bool {
                self.digits().iter().all(|&v| v == 0)
            }

            /// 返回表示此值所需的位数。
            /// 注意，零被认为需要 0 位。
            pub fn bit_length(&self) -> usize {
                let digitbits = <$ty>::BITS as usize;
                let digits = self.digits();
                // 找到最重要的非零数字。
                let msd = digits.iter().rposition(|&x| x != 0);
                match msd {
                    Some(msd) => msd * digitbits + digits[msd].ilog2() as usize + 1,
                    // 没有非零数字，即数字为零。
                    _ => 0,
                }
            }

            /// 向其自身添加 `other`，并返回其自己的可变引用。
            pub fn add<'a>(&'a mut self, other: &$name) -> &'a mut $name {
                use crate::cmp;
                use crate::iter;

                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 (v, c) = (*a).carrying_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 {
                let (v, mut carry) = self.base[0].carrying_add(other, false);
                self.base[0] = v;
                let mut i = 1;
                while carry {
                    let (v, c) = self.base[i].carrying_add(0, carry);
                    self.base[i] = v;
                    carry = c;
                    i += 1;
                }
                if i > self.size {
                    self.size = i;
                }
                self
            }

            /// 从自身中减去 `other`，并返回其自己的可变引用。
            pub fn sub<'a>(&'a mut self, other: &$name) -> &'a mut $name {
                use crate::cmp;
                use crate::iter;

                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 (v, c) = (*a).carrying_add(!*b, noborrow);
                    *a = v;
                    noborrow = c;
                }
                assert!(noborrow);
                self.size = sz;
                self
            }

            /// 将自身乘以数字大小的 `other` 并返回其自己的可变引用。
            ///
            pub fn mul_small(&mut self, other: $ty) -> &mut $name {
                let mut sz = self.size;
                let mut carry = 0;
                for a in &mut self.base[..sz] {
                    let (v, c) = (*a).carrying_mul(other, carry);
                    *a = v;
                    carry = c;
                }
                if carry > 0 {
                    self.base[sz] = carry;
                    sz += 1;
                }
                self.size = sz;
                self
            }

            /// 将自身乘以 `2^bits` 并返回自己的变量引用。
            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);

                // 移位 `digits * digitbits` 位
                for i in (0..self.size).rev() {
                    self.base[i + digits] = self.base[i];
                }
                for i in 0..digits {
                    self.base[i] = 0;
                }

                // 移位 `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] 为零，无需移位
                }

                self.size = sz;
                self
            }

            /// 将自身乘以 `5^e` 并返回自己的变量引用。
            pub fn mul_pow5(&mut self, mut e: usize) -> &mut $name {
                use crate::mem;
                use crate::num::bignum::SMALL_POW5;

                // 在 2 ^ n 上正好有 n 个尾随零，并且唯一相关的数字大小是 2 的连续幂，因此这非常适合该表的索引。
                //
                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;

                // 尽可能长时间乘以最大个位数的幂 ...
                while e >= small_e {
                    self.mul_small(small_power);
                    e -= small_e;
                }

                // ... 然后结束剩余的部分。
                let mut rest_power = 1;
                for _ in 0..e {
                    rest_power *= 5;
                }
                self.mul_small(rest_power);

                self
            }

            /// 将自身乘以 `other[0] + other[1]*2^W + other[2]* 2^(2W) + ...` 描述的数字 (其中 `W` 是数字类型的位数)，并返回其自己的可变引用。
            ///
            ///
            pub fn mul_digits<'a>(&'a mut self, other: &[$ty]) -> &'a mut $name {
                // 内部例程。当 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
            }

            /// 用数字大小的 `other` 除以自身，并返回其自身的变量引用 *，其余为*。
            ///
            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)
            }

            /// 用另一个大数除以 self，用商覆盖 `q`，用余数覆盖 `r`。
            ///
            pub fn div_rem(&self, d: &$name, q: &mut $name, r: &mut $name) {
                // 愚蠢的慢 base-2 长除法取自
                // https://en.wikipedia.org/wiki/Division_algorithm
                // FIXME 对于长除法使用更大的基数 ($ty)。
                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);
                        // 将 q 的位 `i` 设置为 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(())
            }
        }
    };
}

/// `Big32x40` 的数字类型。
pub type Digit32 = u32;

define_bignum!(Big32x40: type=Digit32, n=40);

// 此仅用于测试。
#[doc(hidden)]
pub mod tests {
    define_bignum!(Big8x3: type=u8, n=3);
}