f256 0.11.2

// ---------------------------------------------------------------------------
// Copyright:   (c) 2022 ff. Michael Amrhein (michael@adrhinum.de)
// License:     This program is part of a larger application. For license
//              details please read the file LICENSE.TXT provided together
//              with the application.
// ---------------------------------------------------------------------------
// $Source$
// $Revision$

/// Implementation of a high precision decimal number type supporting
/// high precision non-rounding shifts as decribed in
/// `Nigel Tao: ParseNumberF64 by Simple Decimal Conversion`
/// [https://nigeltao.github.io/blog/2020/parse-number-f64-simple.html],
/// adopted for `f256`.
use core::cmp::{min, Ordering};

use crate::{big_uint::imul10_add, f256, BigUInt, DivRem, U256};

/// The maximum number of digits required to unambiguously round a `f256`,
/// calculated by the formula:
/// -Eₘᵢₙ + p + ⌊(Eₘᵢₙ + 1) × log₁₀(2)⌋, where p = number of significand bits
/// (See J.-M. Muller et al., Handbook of Floating-Point Arithmetic, Chapter
/// 2).
pub(crate) const MAX_DIGITS: usize = 183467;

/// Table for left shift: indexed by shift count giving number of new digits
/// that need to be added. If the current value as digit sequence is greater or
/// equal to the cutoff given by the tables second column, the number of new
/// digits is given by the first column, otherwise that number has to be reduced
/// by 1.
/// Generated by the following Python code:
/// ```python
/// from math import ceil, log10
///
/// def int_to_digit_array(n):
///     a = [0] * 42
///     i = ceil(log10(n))
///     while i > 0:
///         i -= 1
///         a[i] = n % 10
///         n //= 10
///     return a
///
/// def print_table():
///     print(f"    ( 0, {[0] * 42}),")
///     for i in range(1, 61):
///         n = int(log10(2) * i + 1)
///         p = 5 ** i
///         print(f"    // × {2 ** i}")
///         print(f"    ({n:2d}, {int_to_digit_array(p)}),")
///
/// print_table()
/// ```
#[rustfmt::skip]
const LEFT_SHIFT_HELPER_TABLE: [(u32, [u8; 42]); 61] = [
    ( 0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 2
    ( 1, [5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 4
    ( 1, [2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 8
    ( 1, [1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 16
    ( 2, [6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 32
    ( 2, [3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 64
    ( 2, [1, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 128
    ( 3, [7, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 256
    ( 3, [3, 9, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 512
    ( 3, [1, 9, 5, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 1024
    ( 4, [9, 7, 6, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 2048
    ( 4, [4, 8, 8, 2, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 4096
    ( 4, [2, 4, 4, 1, 4, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 8192
    ( 4, [1, 2, 2, 0, 7, 0, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 16384
    ( 5, [6, 1, 0, 3, 5, 1, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 32768
    ( 5, [3, 0, 5, 1, 7, 5, 7, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 65536
    ( 5, [1, 5, 2, 5, 8, 7, 8, 9, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 131072
    ( 6, [7, 6, 2, 9, 3, 9, 4, 5, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 262144
    ( 6, [3, 8, 1, 4, 6, 9, 7, 2, 6, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 524288
    ( 6, [1, 9, 0, 7, 3, 4, 8, 6, 3, 2, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 1048576
    ( 7, [9, 5, 3, 6, 7, 4, 3, 1, 6, 4, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 2097152
    ( 7, [4, 7, 6, 8, 3, 7, 1, 5, 8, 2, 0, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 4194304
    ( 7, [2, 3, 8, 4, 1, 8, 5, 7, 9, 1, 0, 1, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 8388608
    ( 7, [1, 1, 9, 2, 0, 9, 2, 8, 9, 5, 5, 0, 7, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 16777216
    ( 8, [5, 9, 6, 0, 4, 6, 4, 4, 7, 7, 5, 3, 9, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 33554432
    ( 8, [2, 9, 8, 0, 2, 3, 2, 2, 3, 8, 7, 6, 9, 5, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 67108864
    ( 8, [1, 4, 9, 0, 1, 1, 6, 1, 1, 9, 3, 8, 4, 7, 6, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 134217728
    ( 9, [7, 4, 5, 0, 5, 8, 0, 5, 9, 6, 9, 2, 3, 8, 2, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 268435456
    ( 9, [3, 7, 2, 5, 2, 9, 0, 2, 9, 8, 4, 6, 1, 9, 1, 4, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 536870912
    ( 9, [1, 8, 6, 2, 6, 4, 5, 1, 4, 9, 2, 3, 0, 9, 5, 7, 0, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 1073741824
    (10, [9, 3, 1, 3, 2, 2, 5, 7, 4, 6, 1, 5, 4, 7, 8, 5, 1, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 2147483648
    (10, [4, 6, 5, 6, 6, 1, 2, 8, 7, 3, 0, 7, 7, 3, 9, 2, 5, 7, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 4294967296
    (10, [2, 3, 2, 8, 3, 0, 6, 4, 3, 6, 5, 3, 8, 6, 9, 6, 2, 8, 9, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 8589934592
    (10, [1, 1, 6, 4, 1, 5, 3, 2, 1, 8, 2, 6, 9, 3, 4, 8, 1, 4, 4, 5, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 17179869184
    (11, [5, 8, 2, 0, 7, 6, 6, 0, 9, 1, 3, 4, 6, 7, 4, 0, 7, 2, 2, 6, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 34359738368
    (11, [2, 9, 1, 0, 3, 8, 3, 0, 4, 5, 6, 7, 3, 3, 7, 0, 3, 6, 1, 3, 2, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 68719476736
    (11, [1, 4, 5, 5, 1, 9, 1, 5, 2, 2, 8, 3, 6, 6, 8, 5, 1, 8, 0, 6, 6, 4, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 137438953472
    (12, [7, 2, 7, 5, 9, 5, 7, 6, 1, 4, 1, 8, 3, 4, 2, 5, 9, 0, 3, 3, 2, 0, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 274877906944
    (12, [3, 6, 3, 7, 9, 7, 8, 8, 0, 7, 0, 9, 1, 7, 1, 2, 9, 5, 1, 6, 6, 0, 1, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 549755813888
    (12, [1, 8, 1, 8, 9, 8, 9, 4, 0, 3, 5, 4, 5, 8, 5, 6, 4, 7, 5, 8, 3, 0, 0, 7, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 1099511627776
    (13, [9, 0, 9, 4, 9, 4, 7, 0, 1, 7, 7, 2, 9, 2, 8, 2, 3, 7, 9, 1, 5, 0, 3, 9, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 2199023255552
    (13, [4, 5, 4, 7, 4, 7, 3, 5, 0, 8, 8, 6, 4, 6, 4, 1, 1, 8, 9, 5, 7, 5, 1, 9, 5, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 4398046511104
    (13, [2, 2, 7, 3, 7, 3, 6, 7, 5, 4, 4, 3, 2, 3, 2, 0, 5, 9, 4, 7, 8, 7, 5, 9, 7, 6, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 8796093022208
    (13, [1, 1, 3, 6, 8, 6, 8, 3, 7, 7, 2, 1, 6, 1, 6, 0, 2, 9, 7, 3, 9, 3, 7, 9, 8, 8, 2, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 17592186044416
    (14, [5, 6, 8, 4, 3, 4, 1, 8, 8, 6, 0, 8, 0, 8, 0, 1, 4, 8, 6, 9, 6, 8, 9, 9, 4, 1, 4, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 35184372088832
    (14, [2, 8, 4, 2, 1, 7, 0, 9, 4, 3, 0, 4, 0, 4, 0, 0, 7, 4, 3, 4, 8, 4, 4, 9, 7, 0, 7, 0, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 70368744177664
    (14, [1, 4, 2, 1, 0, 8, 5, 4, 7, 1, 5, 2, 0, 2, 0, 0, 3, 7, 1, 7, 4, 2, 2, 4, 8, 5, 3, 5, 1, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 140737488355328
    (15, [7, 1, 0, 5, 4, 2, 7, 3, 5, 7, 6, 0, 1, 0, 0, 1, 8, 5, 8, 7, 1, 1, 2, 4, 2, 6, 7, 5, 7, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 281474976710656
    (15, [3, 5, 5, 2, 7, 1, 3, 6, 7, 8, 8, 0, 0, 5, 0, 0, 9, 2, 9, 3, 5, 5, 6, 2, 1, 3, 3, 7, 8, 9, 0, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0]),
    // × 562949953421312
    (15, [1, 7, 7, 6, 3, 5, 6, 8, 3, 9, 4, 0, 0, 2, 5, 0, 4, 6, 4, 6, 7, 7, 8, 1, 0, 6, 6, 8, 9, 4, 5, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0]),
    // × 1125899906842624
    (16, [8, 8, 8, 1, 7, 8, 4, 1, 9, 7, 0, 0, 1, 2, 5, 2, 3, 2, 3, 3, 8, 9, 0, 5, 3, 3, 4, 4, 7, 2, 6, 5, 6, 2, 5, 0, 0, 0, 0, 0, 0, 0]),
    // × 2251799813685248
    (16, [4, 4, 4, 0, 8, 9, 2, 0, 9, 8, 5, 0, 0, 6, 2, 6, 1, 6, 1, 6, 9, 4, 5, 2, 6, 6, 7, 2, 3, 6, 3, 2, 8, 1, 2, 5, 0, 0, 0, 0, 0, 0]),
    // × 4503599627370496
    (16, [2, 2, 2, 0, 4, 4, 6, 0, 4, 9, 2, 5, 0, 3, 1, 3, 0, 8, 0, 8, 4, 7, 2, 6, 3, 3, 3, 6, 1, 8, 1, 6, 4, 0, 6, 2, 5, 0, 0, 0, 0, 0]),
    // × 9007199254740992
    (16, [1, 1, 1, 0, 2, 2, 3, 0, 2, 4, 6, 2, 5, 1, 5, 6, 5, 4, 0, 4, 2, 3, 6, 3, 1, 6, 6, 8, 0, 9, 0, 8, 2, 0, 3, 1, 2, 5, 0, 0, 0, 0]),
    // × 18014398509481984
    (17, [5, 5, 5, 1, 1, 1, 5, 1, 2, 3, 1, 2, 5, 7, 8, 2, 7, 0, 2, 1, 1, 8, 1, 5, 8, 3, 4, 0, 4, 5, 4, 1, 0, 1, 5, 6, 2, 5, 0, 0, 0, 0]),
    // × 36028797018963968
    (17, [2, 7, 7, 5, 5, 5, 7, 5, 6, 1, 5, 6, 2, 8, 9, 1, 3, 5, 1, 0, 5, 9, 0, 7, 9, 1, 7, 0, 2, 2, 7, 0, 5, 0, 7, 8, 1, 2, 5, 0, 0, 0]),
    // × 72057594037927936
    (17, [1, 3, 8, 7, 7, 7, 8, 7, 8, 0, 7, 8, 1, 4, 4, 5, 6, 7, 5, 5, 2, 9, 5, 3, 9, 5, 8, 5, 1, 1, 3, 5, 2, 5, 3, 9, 0, 6, 2, 5, 0, 0]),
    // × 144115188075855872
    (18, [6, 9, 3, 8, 8, 9, 3, 9, 0, 3, 9, 0, 7, 2, 2, 8, 3, 7, 7, 6, 4, 7, 6, 9, 7, 9, 2, 5, 5, 6, 7, 6, 2, 6, 9, 5, 3, 1, 2, 5, 0, 0]),
    // × 288230376151711744
    (18, [3, 4, 6, 9, 4, 4, 6, 9, 5, 1, 9, 5, 3, 6, 1, 4, 1, 8, 8, 8, 2, 3, 8, 4, 8, 9, 6, 2, 7, 8, 3, 8, 1, 3, 4, 7, 6, 5, 6, 2, 5, 0]),
    // × 576460752303423488
    (18, [1, 7, 3, 4, 7, 2, 3, 4, 7, 5, 9, 7, 6, 8, 0, 7, 0, 9, 4, 4, 1, 1, 9, 2, 4, 4, 8, 1, 3, 9, 1, 9, 0, 6, 7, 3, 8, 2, 8, 1, 2, 5]),
    // × 1152921504606846976
    (19, [8, 6, 7, 3, 6, 1, 7, 3, 7, 9, 8, 8, 4, 0, 3, 5, 4, 7, 2, 0, 5, 9, 6, 2, 2, 4, 0, 6, 9, 5, 9, 5, 3, 3, 6, 9, 1, 4, 0, 6, 2, 5]),
];

/// High precision decimal number.
#[derive(Clone, Debug)]
pub(crate) struct Decimal {
    /// The sign of the number: 0 if positive, 1 if negative.
    pub(crate) sign: u32,
    /// The number of digits in self.digits.
    pub(crate) n_digits: usize,
    /// The offset of the decimal point in self.digits.
    /// If positive, it's the index of the first fractional digit (if equal
    /// to n_digits => self represents an integer).
    /// If negative, it's the number of zeroes to be added before the first
    /// digit.
    pub(crate) decimal_point: i32,
    /// True, if the number of significant digits of the original number
    /// exceeds MAX_DIGITS. This flag is used to distinguish between a true
    /// half case and an above-half case when rounding half-to-even.
    pub(crate) truncated: bool,
    /// Buffer of the raw decimal digits.
    /// Parsing and shifting functions keep the digits in "canonical form",
    /// i.e. maintain the invariant
    /// `n-digits == 0 || digits[0] != 0 && digits[n-digits - 1] != 0`.
    pub(crate) digits: [u8; MAX_DIGITS],
}

impl Default for Decimal {
    fn default() -> Self {
        Self {
            sign: 0,
            n_digits: 0,
            decimal_point: 0,
            truncated: false,
            digits: [0; MAX_DIGITS],
        }
    }
}

impl PartialEq<&[u8]> for Decimal {
    fn eq(&self, other: &&[u8]) -> bool {
        if self.n_digits > other.len() {
            return false;
        } else {
            for i in 0..self.n_digits - 1 {
                if self.digits[i] != other[i] {
                    return false;
                }
            }
        }
        !other[self.n_digits..].iter().any(|d| *d != 0)
    }
}

impl PartialOrd<&[u8]> for Decimal {
    fn partial_cmp(&self, other: &&[u8]) -> Option<Ordering> {
        let n = min(self.n_digits, other.len());
        for i in 0..n {
            if self.digits[i] != other[i] {
                return self.digits[i].partial_cmp(&other[i]);
            }
        }
        match self.n_digits.cmp(&other.len()) {
            Ordering::Greater => Some(Ordering::Greater),
            Ordering::Equal => Some(Ordering::Equal),
            Ordering::Less => {
                if other[self.n_digits..].iter().any(|d| *d != 0) {
                    Some(Ordering::Less)
                } else {
                    Some(Ordering::Equal)
                }
            }
        }
    }
}

impl From<U256> for Decimal {
    /// Create new Decimal from an u256 value.
    #[allow(clippy::cast_possible_wrap)]
    #[allow(clippy::cast_possible_truncation)]
    fn from(mut value: U256) -> Self {
        const SEGMENT_BASE: u64 = 1_000_000_000_000_000_000;
        let mut res = Self::default();
        let mut segments: [u64; 5] = [0, 0, 0, 0, 0];
        let mut r = 0_u64;
        let mut idx = 0;
        while !value.is_zero() {
            (value, r) = (&value).div_rem(SEGMENT_BASE);
            segments[idx] = r;
            idx += 1;
        }
        idx -= 1;
        res.add_digits(segments[idx], false);
        while idx > 0 {
            idx -= 1;
            res.add_digits(segments[idx], true);
        }
        // n_digits <= MAX_DIGITS < i32::MAX, so cast to i32 is safe.
        res.decimal_point = res.n_digits as i32;
        res
    }
}

impl Decimal {
    // We use an u64 as accumulator in the shifting functions and need 4 bits
    // to shift a decimal digit [0..9] in and out. Thus, we shift atmost 60
    // bits in one go.
    /// Maximum number of bits for left / right shifts.
    pub(crate) const MAX_SHIFT: u32 = u64::BITS - 4;

    pub(crate) fn add_digits(&mut self, mut int: u64, full: bool) {
        let mut digits: [u8; 18] = [0; 18];
        let mut idx = 0;
        while int > 0 {
            digits[idx] = (int % 10) as u8;
            int /= 10;
            idx += 1;
        }
        if full {
            idx = digits.len();
        }
        let n_digits = idx;
        for i in self.n_digits..self.n_digits + n_digits {
            idx -= 1;
            self.digits[i] = digits[idx];
        }
        self.n_digits += n_digits;
    }

    pub(crate) const fn add_digit(&mut self, digit: u8) {
        if self.n_digits < MAX_DIGITS {
            self.digits[self.n_digits] = digit;
        } else if digit != 0 {
            self.truncated = true;
        }
        self.n_digits += 1;
    }

    #[inline]
    pub(crate) const fn trim_trailing_zeroes(&mut self) {
        while self.n_digits != 0 && self.digits[self.n_digits - 1] == 0 {
            self.n_digits -= 1;
        }
    }

    /// High precision non-rounding left shift. Computes self × 2ⁿ.
    #[allow(clippy::integer_division)]
    #[allow(clippy::cast_possible_wrap)]
    pub(crate) fn left_shift(&mut self, n: u32) {
        debug_assert!(n <= Self::MAX_SHIFT);
        if self.n_digits == 0 {
            return;
        }

        // The non-rounding shift is done by "rolling a sliding window across
        // the input and output digit streams". A 64-bit accumulator is used
        // and in each step one digt is shifted in and one digit is
        // shifted out.

        // The digits are processed from right to left. In order to avoid
        // copying to / from a second buffer, first, the number of additional
        // digits needed for the left shift is calculated and then used as an
        // offset for writing digits to the digit buffer. For details about
        // the used table see the comment above that table.
        let mut t = &LEFT_SHIFT_HELPER_TABLE[n as usize];
        let mut n_new_digits = t.0;
        let limit = &mut &t.1[..];
        if self < limit {
            n_new_digits -= 1;
        }

        let mut read_idx = self.n_digits;
        let mut write_idx = self.n_digits + n_new_digits as usize;

        // Read a digit, write a digit.
        let mut acc = 0_u64;
        while read_idx != 0 {
            read_idx -= 1;
            write_idx -= 1;
            acc += (self.digits[read_idx] as u64) << n;
            let q = acc / 10;
            let r = acc % 10;
            if write_idx < MAX_DIGITS {
                self.digits[write_idx] = r as u8;
            } else if r > 0 {
                self.truncated = true;
            }
            acc = q;
        }

        // Write extra digits.
        while acc > 0 {
            write_idx -= 1;
            let q = acc / 10;
            let r = acc % 10;
            if write_idx < MAX_DIGITS {
                self.digits[write_idx] = r as u8;
            } else if r > 0 {
                self.truncated = true;
            }
            acc = q;
        }

        self.n_digits += n_new_digits as usize;
        // n_new_digits <= 19, so can't wrap around.
        self.decimal_point += n_new_digits as i32;

        // Normalize self.
        self.n_digits = min(self.n_digits, MAX_DIGITS);
        self.trim_trailing_zeroes();
        debug_assert!(
            self.n_digits == 0
                || self.digits[0] != 0 && self.digits[self.n_digits - 1] != 0
        );
    }

    /// High precision non-rounding right shift. Computes self / 2ⁿ.
    #[allow(clippy::cast_possible_truncation)]
    #[allow(clippy::cast_possible_wrap)]
    pub(crate) fn right_shift(&mut self, n: u32) {
        debug_assert!(n <= Self::MAX_SHIFT);
        let mut read_idx = 0;
        let mut write_idx = 0;

        // The non-rounding shift is done by "rolling a sliding window across
        // the input and output digit streams". A 64-bit accumulator is used
        // and in each step one digt is shifted in and one digit is
        // shifted out.

        // Read enough digits to cover first shift.
        let mut acc = 0_u64;
        while (acc >> n) == 0 {
            if read_idx < self.n_digits {
                acc = (10 * acc) + self.digits[read_idx] as u64;
                read_idx += 1;
            } else if acc == 0 {
                return;
            } else {
                while (acc >> n) == 0 {
                    acc *= 10;
                    read_idx += 1;
                }
                break;
            }
        }

        // Adjust decimal point.
        // read_idx <= MAX_DIGITS < i32::MAX, so cast to i32 is safe.
        self.decimal_point -= read_idx as i32 - 1;

        // TODO: check if following is an otimization
        // if self.decimal_point < some lower limit {
        //     // Result will be 0.
        //     self.n_digits = 0;
        //     self.decimal_point = 0;
        //     self.truncated = false;
        //     return;
        // }

        let mask = (1_u64 << n) - 1;

        // Read a digit, write a digit.
        while read_idx < self.n_digits {
            let d = (acc >> n) as u8;
            acc = (10 * (acc & mask)) + self.digits[read_idx] as u64;
            read_idx += 1;
            self.digits[write_idx] = d;
            write_idx += 1;
        }

        // Write extra digits.
        while acc > 0 {
            let d = (acc >> n) as u8;
            acc = 10 * (acc & mask);
            if write_idx < MAX_DIGITS {
                self.digits[write_idx] = d;
                write_idx += 1;
            } else if d > 0 {
                self.truncated = true;
            }
        }

        self.n_digits = write_idx;
        self.trim_trailing_zeroes();
        debug_assert!(
            self.n_digits == 0
                || self.digits[0] != 0 && self.digits[self.n_digits - 1] != 0
        );
    }

    // Round to nearest integer (half-to-even).
    #[allow(clippy::cast_possible_wrap)]
    #[allow(clippy::cast_sign_loss)]
    pub(crate) fn round(&mut self) -> U256 {
        if self.n_digits == 0 || self.decimal_point < 0 {
            return U256::ZERO;
        } else if self.decimal_point > U256::MAX_N_DECIMAL_DIGITS as i32 {
            return U256::MAX;
        }
        let dp = self.decimal_point as usize;
        let mut n = U256::ZERO;
        for i in 0..dp {
            imul10_add(&mut n, self.digits[i]);
        }
        if self.digits[dp] > 5
            || self.digits[dp] == 5
                && (dp < self.n_digits - 1 || self.truncated)
        {
            n.incr();
        }
        n
    }

    // Multiply in-place by 10ⁿ.
    pub(crate) const fn imul_10_pow(&mut self, n: i32) {
        self.decimal_point += n;
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_add_digits() {
        let mut dec = Decimal::default();
        let digits: [u8; 25] = [
            7, 9, 3, 4, 4, 6, 4, 0, 0, 0, 0, 2, 0, 0, 8, 1, 4, 0, 3, 7, 5, 9,
            2, 2, 0,
        ];
        dec.add_digits(7934464, false);
        assert_eq!(dec.n_digits, 7);
        dec.add_digits(20081403759220, true);
        assert_eq!(dec, &digits);
        assert_eq!(dec.decimal_point, 0);
        assert!(!dec.truncated);
    }

    #[test]
    #[allow(clippy::cast_possible_truncation)]
    #[allow(clippy::cast_possible_wrap)]
    fn test_from_u256() {
        let val = U256::new(
            401609310945955079118279405485910,
            168709353958551391248113314710179390005,
        );
        let dec = Decimal::from(val);
        let digits: [u8; 72] = [
            1, 3, 6, 6, 6, 0, 5, 6, 6, 9, 0, 6, 1, 7, 6, 7, 5, 4, 1, 8, 7, 2,
            3, 7, 8, 1, 3, 3, 7, 8, 5, 7, 5, 5, 0, 0, 9, 8, 2, 4, 5, 9, 8, 9,
            6, 1, 2, 9, 5, 6, 6, 9, 1, 0, 7, 8, 3, 4, 1, 5, 0, 6, 5, 4, 8, 7,
            9, 7, 4, 9, 6, 5,
        ];
        assert_eq!(dec, &digits);
        assert_eq!(dec.decimal_point, digits.len() as i32);
        assert!(!dec.truncated);
    }

    #[test]
    fn test_shift_right() {
        let mut dec = Decimal::from(U256::new(0, 299792458));
        dec.imul_10_pow(-6);
        let digits: [u8; 42] = [
            5, 5, 8, 4, 0, 6, 9, 6, 7, 6, 6, 9, 7, 2, 5, 4, 1, 8, 0, 9, 0, 8,
            2, 0, 3, 1, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        ];
        dec.right_shift(29);
        assert_eq!(dec.n_digits, 28);
        assert_eq!(dec, &digits);
        assert_eq!(dec.decimal_point, -6);
        assert!(!dec.truncated);
    }

    #[test]
    fn test_shift_left() {
        let mut dec = Decimal::from(U256::new(0, 4768371582));
        dec.imul_10_pow(-9);
        let digits: [u8; 42] = [
            9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 3, 4, 4, 6, 4, 0, 0, 0, 0, 0, 0,
            0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        ];
        dec.left_shift(21);
        assert_eq!(dec.n_digits, 16);
        assert_eq!(dec, &digits);
        assert_eq!(dec.decimal_point, 7);
        assert!(!dec.truncated);
    }
}