//! 快速，准确地打印浮点数 [^1] 图 3 的几乎直接 (但略有优化) 的 Rust 翻译。
//!
//!
//! [^1]: Burger, R.  G. and Dybvig, R.  K. 1996.  打印浮点数
//!   快速准确。SIGPLAN 不是。31，5 (1996 年 5 月)，108-116。

use crate::cmp::Ordering;
use crate::mem::MaybeUninit;

use crate::num::bignum::Big32x40 as Big;
use crate::num::bignum::Digit32 as Digit;
use crate::num::flt2dec::estimator::estimate_scaling_factor;
use crate::num::flt2dec::{round_up, Decoded, MAX_SIG_DIGITS};

static POW10: [Digit; 10] =
    [1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000];
static TWOPOW10: [Digit; 10] =
    [2, 20, 200, 2000, 20000, 200000, 2000000, 20000000, 200000000, 2000000000];

// 为 10^(2^n) 预先计算的 `Digit` 数组
static POW10TO16: [Digit; 2] = [0x6fc10000, 0x2386f2];
static POW10TO32: [Digit; 4] = [0, 0x85acef81, 0x2d6d415b, 0x4ee];
static POW10TO64: [Digit; 7] = [0, 0, 0xbf6a1f01, 0x6e38ed64, 0xdaa797ed, 0xe93ff9f4, 0x184f03];
static POW10TO128: [Digit; 14] = [
    0, 0, 0, 0, 0x2e953e01, 0x3df9909, 0xf1538fd, 0x2374e42f, 0xd3cff5ec, 0xc404dc08, 0xbccdb0da,
    0xa6337f19, 0xe91f2603, 0x24e,
];
static POW10TO256: [Digit; 27] = [
    0, 0, 0, 0, 0, 0, 0, 0, 0x982e7c01, 0xbed3875b, 0xd8d99f72, 0x12152f87, 0x6bde50c6, 0xcf4a6e70,
    0xd595d80f, 0x26b2716e, 0xadc666b0, 0x1d153624, 0x3c42d35a, 0x63ff540e, 0xcc5573c0, 0x65f9ef17,
    0x55bc28f2, 0x80dcc7f7, 0xf46eeddc, 0x5fdcefce, 0x553f7,
];

#[doc(hidden)]
pub fn mul_pow10(x: &mut Big, n: usize) -> &mut Big {
    debug_assert!(n < 512);
    if n & 7 != 0 {
        x.mul_small(POW10[n & 7]);
    }
    if n & 8 != 0 {
        x.mul_small(POW10[8]);
    }
    if n & 16 != 0 {
        x.mul_digits(&POW10TO16);
    }
    if n & 32 != 0 {
        x.mul_digits(&POW10TO32);
    }
    if n & 64 != 0 {
        x.mul_digits(&POW10TO64);
    }
    if n & 128 != 0 {
        x.mul_digits(&POW10TO128);
    }
    if n & 256 != 0 {
        x.mul_digits(&POW10TO256);
    }
    x
}

fn div_2pow10(x: &mut Big, mut n: usize) -> &mut Big {
    let largest = POW10.len() - 1;
    while n > largest {
        x.div_rem_small(POW10[largest]);
        n -= largest;
    }
    x.div_rem_small(TWOPOW10[n]);
    x
}

// 仅在 `x < 16 * scale` 时可用； `scaleN` 应该是 `scale.mul_small(N)`
fn div_rem_upto_16<'a>(
    x: &'a mut Big,
    scale: &Big,
    scale2: &Big,
    scale4: &Big,
    scale8: &Big,
) -> (u8, &'a mut Big) {
    let mut d = 0;
    if *x >= *scale8 {
        x.sub(scale8);
        d += 8;
    }
    if *x >= *scale4 {
        x.sub(scale4);
        d += 4;
    }
    if *x >= *scale2 {
        x.sub(scale2);
        d += 2;
    }
    if *x >= *scale {
        x.sub(scale);
        d += 1;
    }
    debug_assert!(*x < *scale);
    (d, x)
}

/// Dragon 的最短模式实现。
pub fn format_shortest<'a>(
    d: &Decoded,
    buf: &'a mut [MaybeUninit<u8>],
) -> (/*digits*/ &'a [u8], /*exp*/ i16) {
    // 已知要格式化的数字 `v` 为：
    // - 等于 `mant * 2^exp`；
    // - 原始类型前面带有 `(mant - 2 *minus)* 2^exp`； and
    // - 后面是原始类型的 `(mant + 2 *plus)* 2^exp`。
    //
    // 显然，`minus` 和 `plus` 不能为零。(对于无穷大，我们使用越界的值。) 我们还假定至少生成一个数字，即 `mant` 也不能为零。
    //
    // 这也意味着 `low = (mant - minus)*2^exp` 和 `high = (mant + plus)* 2^exp` 之间的任何数字都将 map 转换为该精确的浮点数，并包括原始尾数为偶数 (即 `!mant_was_odd`) 时的范围。
    //
    //
    //

    assert!(d.mant > 0);
    assert!(d.minus > 0);
    assert!(d.plus > 0);
    assert!(d.mant.checked_add(d.plus).is_some());
    assert!(d.mant.checked_sub(d.minus).is_some());
    assert!(buf.len() >= MAX_SIG_DIGITS);

    // `a.cmp(&b) < rounding` 是 `if d.inclusive {a <= b} else {a < b}`
    let rounding = if d.inclusive { Ordering::Greater } else { Ordering::Equal };

    // 从满足 `10^(k_0-1) < high <= 10^(k_0+1)` 的原始输入中估算 `k_0`。
    // 满足 `10^(k-1) < high <= 10^k` 的紧定 `k` 稍后计算。
    let mut k = estimate_scaling_factor(d.mant + d.plus, d.exp);

    // 将 `{mant, plus, minus} * 2^exp` 转换为小数形式，以便：
    // - `v = mant / scale`
    // - `low = (mant - minus) / scale`
    // - `high = (mant + plus) / scale`
    let mut mant = Big::from_u64(d.mant);
    let mut minus = Big::from_u64(d.minus);
    let mut plus = Big::from_u64(d.plus);
    let mut scale = Big::from_small(1);
    if d.exp < 0 {
        scale.mul_pow2(-d.exp as usize);
    } else {
        mant.mul_pow2(d.exp as usize);
        minus.mul_pow2(d.exp as usize);
        plus.mul_pow2(d.exp as usize);
    }

    // 将 `mant` 除以 `10^k`。现在是 `scale / 10 < mant + plus <= scale * 10`。
    if k >= 0 {
        mul_pow10(&mut scale, k as usize);
    } else {
        mul_pow10(&mut mant, -k as usize);
        mul_pow10(&mut minus, -k as usize);
        mul_pow10(&mut plus, -k as usize);
    }

    // `mant + plus > scale` (或 `>=`) 时修正。
    // 我们实际上并没有修改 `scale`，因为我们可以跳过初始乘法。
    // 现在 `scale < mant + plus <= scale * 10`，我们准备生成数字。
    //
    // 请注意，当 `scale - plus < mant < scale` 时，`d[0]`*可以* 为零。
    // 在这种情况下，将立即触发舍入条件 (下面的 `up`)。
    if scale.cmp(mant.clone().add(&plus)) < rounding {
        // 相当于将 `scale` 缩放 10
        k += 1;
    } else {
        mant.mul_small(10);
        minus.mul_small(10);
        plus.mul_small(10);
    }

    // 缓存 `(2, 4, 8) * scale` 用于数字生成。
    let mut scale2 = scale.clone();
    scale2.mul_pow2(1);
    let mut scale4 = scale.clone();
    scale4.mul_pow2(2);
    let mut scale8 = scale.clone();
    scale8.mul_pow2(3);

    let mut down;
    let mut up;
    let mut i = 0;
    loop {
        // 不变量，其中 `d[0..n-1]` 是迄今为止生成的数字：
        // - `v = mant / scale * 10^(k-n-1) + d[0..n-1] * 10^(k-n)`
        // - `v - low = minus / scale * 10^(k-n-1)`
        // - `high - v = plus / scale * 10^(k-n-1)`
        // - `(mant + plus) / scale <= 10` (因此是 `mant / scale < 10`)，其中 `d[i..j]` 是 `d [i] * 10^(ji) 的简写 + ...
        // + d[j-1] * 10 + d[j]`.

        // 生成一位数字: `d[n] = floor(mant / scale) < 10`。
        let (d, _) = div_rem_upto_16(&mut mant, &scale, &scale2, &scale4, &scale8);
        debug_assert!(d < 10);
        buf[i] = MaybeUninit::new(b'0' + d);
        i += 1;

        // 这是对修改后的 Dragon 算法的简化描述。
        // 为了方便起见，省略了许多中间派生和完整性参数。
        //
        // 从修改的不变量开始，因为我们已经更新了 `n`：
        // - `v = mant / scale * 10^(k-n) + d[0..n-1] * 10^(k-n)`
        // - `v - low = minus / scale * 10^(k-n)`
        // - `high - v = plus / scale * 10^(k-n)`
        //
        // 假定 `d[0..n-1]` 是 `low` 和 `high` 之间的最短表示形式，即 `d[0..n-1]` 满足以下两个条件，但 `d[0..n-2]` 不满足：
        //
        // - `low < d[0..n-1] * 10^(k-n) < high` (双射性：数字四舍五入到 `v`) ； and
        // - `abs(v / 10^(k-n) - d[0..n-1]) <= 1/2` (最后一位是正确的)。
        //
        // 第二个条件简化为 `2 * mant <= scale`。
        // 根据 `mant`、`low` 和 `high` 求解不变量会产生第一个条件的更简单版本: `-plus < mant < minus`。
        // 自 `-plus < 0 <= mant` 以来，我们拥有正确的最短表示形式 `mant < minus` 和 `2 * mant <= scale`。
        // (当原始尾数为偶数时，前者变为 `mant <= minus`。)
        //
        // 当第二个不保存 (`2 * mant > scale`) 时，我们需要增加最后一位。
        // 这足以恢复该条件：我们已经知道数字生成可以保证 `0 <= v / 10^(k-n) - d[0..n-1] < 1`。
        // 在这种情况下，第一个条件变为 `-plus < mant - scale < minus`。
        // 自从 `mant < scale` 产生以来，我们有了 `scale < mant + plus`。
        // (同样，当原始尾数为偶数时，它变为 `scale <= mant + plus`。)
        //
        // 简而言之：
        // - `mant < minus` (或 `<=`) 时，停止并四舍五入 `down` (保持数字不变)。
        // - `scale < mant + plus` (或 `<=`) 时，停止并四舍五入 `up` (增加最后一位)。
        // - 否则继续生成。
        //
        //
        //
        down = mant.cmp(&minus) < rounding;
        up = scale.cmp(mant.clone().add(&plus)) < rounding;
        if down || up {
            break;
        } // 我们具有最短的表示，请继续进行四舍五入

        // 恢复不变量。
        // 这使得算法总是终止: `minus` 和 `plus` 总是增加，但是 `mant` 被裁剪为 `scale` 模，并且 `scale` 是固定的。
        //
        mant.mul_small(10);
        minus.mul_small(10);
        plus.mul_small(10);
    }

    // 当 i) 仅触发了舍入条件，或者 ii) 两个条件都被触发并且平局打破更倾向于舍入时，发生舍入。
    //
    //
    if up && (!down || *mant.mul_pow2(1) >= scale) {
        // 如果四舍五入改变了长度，则指数也应改变。
        // 似乎很难满足这个条件 (可能是不可能的)，但是我们在这里只是安全和一致的。
        //
        // SAFETY: 我们在上面初始化了该内存。
        if let Some(c) = round_up(unsafe { MaybeUninit::slice_assume_init_mut(&mut buf[..i]) }) {
            buf[i] = MaybeUninit::new(c);
            i += 1;
            k += 1;
        }
    }

    // SAFETY: 我们在上面初始化了该内存。
    (unsafe { MaybeUninit::slice_assume_init_ref(&buf[..i]) }, k)
}

/// Dragon 的确切和固定模式实现。
pub fn format_exact<'a>(
    d: &Decoded,
    buf: &'a mut [MaybeUninit<u8>],
    limit: i16,
) -> (/*digits*/ &'a [u8], /*exp*/ i16) {
    assert!(d.mant > 0);
    assert!(d.minus > 0);
    assert!(d.plus > 0);
    assert!(d.mant.checked_add(d.plus).is_some());
    assert!(d.mant.checked_sub(d.minus).is_some());

    // 从满足 `10^(k_0-1) < v <= 10^(k_0+1)` 的原始输入中估算 `k_0`。
    let mut k = estimate_scaling_factor(d.mant, d.exp);

    // `v = mant / scale`.
    let mut mant = Big::from_u64(d.mant);
    let mut scale = Big::from_small(1);
    if d.exp < 0 {
        scale.mul_pow2(-d.exp as usize);
    } else {
        mant.mul_pow2(d.exp as usize);
    }

    // 将 `mant` 除以 `10^k`。现在 `scale / 10 < mant <= scale * 10`。
    if k >= 0 {
        mul_pow10(&mut scale, k as usize);
    } else {
        mul_pow10(&mut mant, -k as usize);
    }

    // `mant + plus >= scale` 时的修正，`plus / scale = 10^-buf.len() / 2` 时的修正。
    // 为了保留固定大小的 bignum，我们实际上使用 `mant + floor(plus) >= scale`。
    // 我们实际上并没有修改 `scale`，因为我们可以跳过初始乘法。
    // 再次使用最短算法，`d[0]` 可以为零，但最终会四舍五入。
    if *div_2pow10(&mut scale.clone(), buf.len()).add(&mant) >= scale {
        // 相当于将 `scale` 缩放 10
        k += 1;
    } else {
        mant.mul_small(10);
    }

    // 如果使用的是最后一位数字的限制，则需要在实际渲染之前缩短缓冲区，以避免双舍入。
    //
    // 请注意，在进行舍入操作时，我们必须再次扩大缓冲区！
    let mut len = if k < limit {
        // 糟糕，我们甚至无法产生 *一位* 数字。
        // 例如，当我们有类似 9.5 的值并将其四舍五入时，这是可能的。
        // 我们返回一个空缓冲区，但以后的向上舍入情况除外，后者发生在 `k == limit` 且必须产生一位数字的情况下。
        //
        0
    } else if ((k as i32 - limit as i32) as usize) < buf.len() {
        (k - limit) as usize
    } else {
        buf.len()
    };

    if len > 0 {
        // 缓存 `(2, 4, 8) * scale` 用于数字生成。
        // (这可能很昂贵，因此在缓冲区为空时不要计算它们。)
        let mut scale2 = scale.clone();
        scale2.mul_pow2(1);
        let mut scale4 = scale.clone();
        scale4.mul_pow2(2);
        let mut scale8 = scale.clone();
        scale8.mul_pow2(3);

        for i in 0..len {
            if mant.is_zero() {
                // 以下数字全为零，我们在这里停止 *不要* 尝试进行舍入！ 而是填写剩余的数字。
                //
                for c in &mut buf[i..len] {
                    *c = MaybeUninit::new(b'0');
                }
                // SAFETY: 我们在上面初始化了该内存。
                return (unsafe { MaybeUninit::slice_assume_init_ref(&buf[..len]) }, k);
            }

            let mut d = 0;
            if mant >= scale8 {
                mant.sub(&scale8);
                d += 8;
            }
            if mant >= scale4 {
                mant.sub(&scale4);
                d += 4;
            }
            if mant >= scale2 {
                mant.sub(&scale2);
                d += 2;
            }
            if mant >= scale {
                mant.sub(&scale);
                d += 1;
            }
            debug_assert!(mant < scale);
            debug_assert!(d < 10);
            buf[i] = MaybeUninit::new(b'0' + d);
            mant.mul_small(10);
        }
    }

    // 如果以下几位恰好是 5000，则四舍五入，如果我们停在数字的中间，请检查前一位并尝试四舍五入为偶数 (即，避免在前一位为偶数时四舍五入)。
    //
    //
    let order = mant.cmp(scale.mul_small(5));
    if order == Ordering::Greater
        || (order == Ordering::Equal
            // SAFETY: `buf[len-1]` 被初始化。
            && len > 0 && unsafe { buf[len - 1].assume_init() } & 1 == 1)
    {
        // 如果四舍五入改变了长度，则指数也应改变。
        // 但是我们被要求固定位数，所以不要改变缓冲区...
        // SAFETY: 我们在上面初始化了该内存。
        if let Some(c) = round_up(unsafe { MaybeUninit::slice_assume_init_mut(&mut buf[..len]) }) {
            // ...除非我们被要求改为固定精度。
            // 我们还需要检查一下，如果原始缓冲区为空，则只能在 `k == limit` (edge 情况) 下添加附加数字。
            //
            k += 1;
            if k > limit && len < buf.len() {
                buf[len] = MaybeUninit::new(c);
                len += 1;
            }
        }
    }

    // SAFETY: 我们在上面初始化了该内存。
    (unsafe { MaybeUninit::slice_assume_init_ref(&buf[..len]) }, k)
}