json-bourne 0.2.2

//! Shortest-roundtrip `f64` → decimal-string formatter.
//!
//! Port of the teju-jagua algorithm by Cassio Neri (Apache-2.0).
//! Unlike Grisu3, teju-jagua always succeeds — no fallback path needed.
//! The algorithm decomposes an IEEE 754 double into binary fields, then
//! uses a 128-bit multiply-and-shift with precomputed tables to find the
//! shortest decimal mantissa that round-trips.
//!
//! Tables generated by `teju_gen.rs` (test-only module) and cross-validated
//! against the C reference at https://github.com/cassioneri/teju_jagua.

#![allow(
    clippy::many_single_char_names,
    clippy::unreadable_literal,
    clippy::cast_possible_truncation,
    clippy::cast_possible_wrap,
    clippy::cast_sign_loss,
    clippy::cast_lossless,
    clippy::cast_precision_loss,
    clippy::similar_names,
    clippy::module_name_repetitions,
    clippy::missing_const_for_fn,
    clippy::doc_markdown,
    clippy::redundant_pub_crate
)]

extern crate alloc;

use alloc::string::String;
use core::fmt;

// ===========================================================================
// IEEE 754 constants and decomposition.
// ===========================================================================

const MANTISSA_WIDTH: u32 = 53;
const EXPONENT_MIN: i32 = -1074;
const HIDDEN_BIT: u64 = 1u64 << (MANTISSA_WIDTH - 1);
const SIG_MASK: u64 = HIDDEN_BIT - 1;
const EXP_SHIFT: u32 = MANTISSA_WIDTH - 1; // 52

struct BinaryF64 {
    exponent: i32,
    mantissa: u64,
}

#[inline]
fn decompose(value: f64) -> BinaryF64 {
    debug_assert!(value.is_finite() && value > 0.0);
    let bits = value.to_bits();
    let mut mantissa = bits & SIG_MASK;
    let biased_exp = (bits >> EXP_SHIFT) as i32;
    let mut exponent;
    if biased_exp != 0 {
        exponent = biased_exp - 1;
        mantissa |= HIDDEN_BIT;
    } else {
        exponent = 0;
    }
    exponent += EXPONENT_MIN;
    BinaryF64 { exponent, mantissa }
}

// ===========================================================================
// Algorithm helpers.
// ===========================================================================

#[inline]
fn log10_pow2(e: i32) -> i32 {
    ((1_292_913_987i64 * i64::from(e)) >> 32) as i32
}

#[inline]
fn log10_pow2_residual(e: i32) -> u32 {
    // Matches C: (uint32_t)((int64_t)1292913987u * e) / 1292913987u
    // The cast to uint32_t truncates the 64-bit product to 32 bits
    // BEFORE the unsigned division.
    let product = 1_292_913_987i64 * i64::from(e);
    (product as u32) / 1_292_913_987u32
}

#[inline]
fn mshift(m: u64, upper: u64, lower: u64) -> u64 {
    let hi = u128::from(m) * u128::from(upper);
    let lo = u128::from(m) * u128::from(lower);
    ((hi + (lo >> 64)) >> 64) as u64
}

#[inline]
fn mshift_pow2(k: u32, upper: u64, lower: u64) -> u64 {
    let s = k as i32 - 64;
    if s <= 0 {
        upper >> (-s) as u32
    } else {
        (upper << s as u32) | (lower >> (64 - s as u32))
    }
}

#[inline]
fn is_multiple_of_pow2(e: i32, n: u64) -> bool {
    debug_assert!(e >= 0 && (e as u32) < 64);
    (n >> e as u32) << e as u32 == n
}

#[inline]
fn can_test_pow5(f: i32) -> bool {
    f >= 0 && (f as usize) < MINVERSE.len()
}

#[inline]
fn is_multiple_of_pow5(f: i32, n: u64) -> bool {
    debug_assert!(can_test_pow5(f));
    let (inv, bound) = MINVERSE[f as usize];
    n.wrapping_mul(inv) <= bound
}

#[inline]
fn div10(n: u64) -> u64 {
    n / 10
}

// ===========================================================================
// Decimal result + trailing-zero removal.
// ===========================================================================

struct DecimalF64 {
    exponent: i32,
    mantissa: u64,
}

#[inline]
fn remove_trailing_zeros(mut m: u64, mut e: i32) -> DecimalF64 {
    // m == 0 only reachable from a speculative caller (branchless
    // `to_decimal_centred` always computes this path even when it
    // ends up unused). Return immediately so the loop below doesn't
    // diverge / overflow `e`. The result is discarded by the cmov in
    // that case.
    if m == 0 {
        return DecimalF64 {
            exponent: e,
            mantissa: 0,
        };
    }
    let minv5: u64 = 0u64.wrapping_sub(u64::MAX / 5);
    let bound: u64 = u64::MAX / 10 + 1;
    loop {
        let q = m.wrapping_mul(minv5).rotate_right(1);
        if q >= bound {
            return DecimalF64 {
                exponent: e,
                mantissa: m,
            };
        }
        e += 1;
        m = q;
    }
}

// ===========================================================================
// Teju Jagua core.
// ===========================================================================

const MANTISSA_UNCENTRED: u64 = 1u64 << (MANTISSA_WIDTH - 1);

#[inline]
fn is_small_integer(e: i32, m: u64) -> bool {
    let neg_e = -e;
    neg_e >= 0 && (neg_e as u32) < MANTISSA_WIDTH && is_multiple_of_pow2(neg_e, m)
}

#[inline]
fn is_centred(e: i32, m: u64) -> bool {
    m != MANTISSA_UNCENTRED || e == EXPONENT_MIN
}

fn to_decimal_small_integer(e: i32, m: u64) -> DecimalF64 {
    debug_assert!(is_small_integer(e, m));
    remove_trailing_zeros(m >> (-e) as u32, 0)
}

/// Branchless `is_multiple_of_pow5` — returns `false` if `f` is out of the
/// MINVERSE table range, without branching. Used in the branchless
/// tiebreak below where we compute both candidates speculatively and
/// select with cmov; a panicky table index would break that.
#[inline]
fn is_multiple_of_pow5_safe(f: i32, n: u64) -> bool {
    // Mask the index into a valid range; the result is gated by the
    // `in_range` boolean below so out-of-range f values can never falsely
    // claim divisibility.
    let in_range = f >= 0 && (f as usize) < MINVERSE.len();
    let idx = if in_range { f as usize } else { 0 };
    let (inv, bound) = MINVERSE[idx];
    let multiple = n.wrapping_mul(inv) <= bound;
    in_range & multiple
}

#[inline]
fn is_tie_neg_f_safe(f: i32, c_2: u64) -> bool {
    is_multiple_of_pow5_safe(-f, c_2)
}

#[inline]
fn to_decimal_centred(e: i32, m: u64) -> DecimalF64 {
    debug_assert!(is_centred(e, m));

    let f = log10_pow2(e);
    let r = log10_pow2_residual(e);
    let idx = (f - STORAGE_INDEX_OFFSET) as usize;
    let (lower, upper) = MULTIPLIERS[idx];
    let m_b = (2 * m + 1) << r;
    let m_a = (2 * m - 1) << r;
    let b = mshift(m_b, upper, lower);
    let a = mshift(m_a, upper, lower);
    let q = div10(b);
    let s = 10 * q;

    // ── Branchless tiebreak. ─────────────────────────────────────────────
    //
    // The previous version had three nested branches with data-dependent
    // outcomes (`if can_test_pow5(f)`, `if s == b ... else if s == a`,
    // `if shortest`). Under random `f64` inputs each fired ~50/50 and
    // none could be predicted; perf record on n=10000 showed the
    // aggregate teju mispredict cost dominated the cliff.
    //
    // The rewrite computes BOTH candidates (the "shortest" result with
    // `remove_trailing_zeros` and the "fallback" `m_c` mshift) and
    // selects via a single boolean comparison that LLVM compiles to
    // cmov. The fallback path was already always computed in the
    // original after early-return — the extra work here is just the
    // unconditional `remove_trailing_zeros`, which exits in iter 1 for
    // any value not divisible by 10 (the common case).
    let m_even = m & 1 == 0;
    let m_b_mult_pow5 = is_multiple_of_pow5_safe(f, m_b);
    let m_a_mult_pow5 = is_multiple_of_pow5_safe(f, m_a);
    let allows_ties = can_test_pow5(f);

    // Three sub-cases for the pow5-allowed branch, computed as booleans
    // without short-circuit: `s == b ? cond_b : s == a ? cond_a : s > a`.
    let cond_s_eq_b = !m_b_mult_pow5 || m_even;
    let cond_s_eq_a = m_a_mult_pow5 && m_even;
    let cond_else = s > a;
    let shortest_pow5 = if s == b {
        cond_s_eq_b
    } else if s == a {
        cond_s_eq_a
    } else {
        cond_else
    };
    // For non-pow5 case the test is just `s > a`.
    let shortest = if allows_ties { shortest_pow5 } else { s > a };

    // Always compute the "shortest" branch's result (a `remove_trailing_zeros`
    // call) and the "fallback" branch's result (an extra mshift + tiebreak
    // arithmetic). Both are cheap and side-effect-free; cmov selects.
    let shortest_result = remove_trailing_zeros(q, f + 1);

    let m_c = (4 * m) << r;
    let c_2 = mshift(m_c, upper, lower);
    let c = c_2 / 2;
    let pick_left = (is_tie_neg_f_safe(f, c_2) && c & 1 == 0) || c_2 & 1 == 0;
    let fallback_result = DecimalF64 {
        exponent: f,
        mantissa: c + u64::from(!pick_left),
    };

    if shortest {
        shortest_result
    } else {
        fallback_result
    }
}

/// Bundle of values shared across the uncentred-decompose helpers.
/// Extracted so the two arms (`a < b` and `a >= b`) take one struct
/// rather than seven positional arguments.
struct UncentredCtx {
    m: u64,
    f: i32,
    r: u32,
    upper: u64,
    lower: u64,
    a: u64,
    b: u64,
    m_a: u64,
    m_b: u64,
}

fn to_decimal_uncentred(e: i32) -> DecimalF64 {
    let m = MANTISSA_UNCENTRED;
    let f = log10_pow2(e);
    let r = log10_pow2_residual(e);
    let idx = (f - STORAGE_INDEX_OFFSET) as usize;
    let (lower, upper) = MULTIPLIERS[idx];
    let m_a = (4 * m - 1) << r;
    let m_b = (2 * m + 1) << r;
    let b = mshift(m_b, upper, lower);
    let a = mshift(m_a, upper, lower) / 2;
    let ctx = UncentredCtx {
        m,
        f,
        r,
        upper,
        lower,
        a,
        b,
        m_a,
        m_b,
    };

    if a < b {
        uncentred_a_less_than_b(&ctx)
    } else {
        uncentred_a_ge_b(&ctx)
    }
}

/// `a < b` arm — the common case. Handles the shortest-roundtrip
/// selection and the `m_c` fallback.
#[inline]
fn uncentred_a_less_than_b(ctx: &UncentredCtx) -> DecimalF64 {
    let UncentredCtx {
        f,
        r,
        upper,
        lower,
        a,
        b,
        m_a,
        ..
    } = *ctx;
    let q = div10(b);
    let s = 10 * q;

    if uncentred_is_shortest(ctx, s) {
        return remove_trailing_zeros(q, f + 1);
    }

    let log2_m_c = MANTISSA_WIDTH + r + 1;
    let c_2 = mshift_pow2(log2_m_c, upper, lower);
    let c = c_2 / 2;

    if c == a && !is_tie_uncentred(f, m_a) {
        return DecimalF64 {
            exponent: f,
            mantissa: c + 1,
        };
    }
    let pick_left = (is_tie_neg_f(f, c_2) && c % 2 == 0) || c_2 % 2 == 0;
    DecimalF64 {
        exponent: f,
        mantissa: c + u64::from(!pick_left),
    }
}

/// Decide whether `q` is the shortest representation when `a < b`.
/// Splitting this out of `uncentred_a_less_than_b` keeps each helper
/// below the CRAP threshold.
#[inline]
fn uncentred_is_shortest(ctx: &UncentredCtx, s: u64) -> bool {
    let UncentredCtx {
        m,
        f,
        a,
        b,
        m_a,
        m_b,
        ..
    } = *ctx;
    if !can_test_pow5(f) {
        return s > a;
    }
    if s == b {
        return !is_tie_uncentred(f, m_b) || m % 2 == 0;
    }
    if s == a {
        return is_tie_uncentred(f, m_a) && m % 2 == 0;
    }
    s > a
}

/// `a >= b` arm — rarely hit, separate fn so the high-CC tiebreak
/// math doesn't combine with the `a < b` arm's CC.
#[inline]
fn uncentred_a_ge_b(ctx: &UncentredCtx) -> DecimalF64 {
    let UncentredCtx {
        m,
        f,
        r,
        upper,
        lower,
        a,
        m_a,
        ..
    } = *ctx;
    if is_tie_uncentred(f, m_a) && m % 2 == 0 {
        return remove_trailing_zeros(a, f);
    }
    let m_c = (40 * m) << r;
    let c_2 = mshift(m_c, upper, lower);
    let c = c_2 / 2;
    let pick_left = (is_tie_neg_f(f, c_2) && c % 2 == 0) || c_2 % 2 == 0;
    DecimalF64 {
        exponent: f - 1,
        mantissa: c + u64::from(!pick_left),
    }
}

#[inline]
fn is_tie_neg_f(f: i32, c_2: u64) -> bool {
    can_test_pow5(-f) && is_multiple_of_pow5(-f, c_2)
}

#[inline]
fn is_tie_uncentred(f: i32, m: u64) -> bool {
    m % 5 == 0 && can_test_pow5(f) && is_multiple_of_pow5(f, m)
}

#[inline]
fn teju(value: f64) -> DecimalF64 {
    let b = decompose(value);
    let e = b.exponent;
    let m = b.mantissa;

    if is_small_integer(e, m) {
        return to_decimal_small_integer(e, m);
    }
    if is_centred(e, m) {
        return to_decimal_centred(e, m);
    }
    to_decimal_uncentred(e)
}

// ===========================================================================
// Decimal-to-string formatting.
//
// Output is written forward into a 32-byte stack buffer (worst case for an
// f64 in scientific or fixed form is ≤ 25 bytes). Single `extend_from_slice`
// hands the result to the caller; no `String` reallocation, no `copy_within`
// shift, no `fmt::Display` route for the exponent.
// ===========================================================================

/// Worst-case byte length for any finite `f64` printed by `format_finite_to_buf`.
/// 25 bytes covers: sign + 17 significant digits + decimal point + `e` + sign
/// + 3-digit exponent. Round up to 32 for a power-of-two stack buffer.
pub(crate) const FORMAT_BUF_LEN: usize = 32;

const DIGIT_LUT: &[u8; 200] = b"\
0001020304050607080910111213141516171819\
2021222324252627282930313233343536373839\
4041424344454647484950515253545556575859\
6061626364656667686970717273747576777879\
8081828384858687888990919293949596979899";

/// Four-digit ASCII LUT: for each `n` in `0..10_000`, `QUAD_LUT[n*4..n*4+4]`
/// holds the four ASCII digits of `n` (with leading zeros). Lets the digit
/// writer emit four characters per iteration with one 4-byte store instead
/// of two 2-byte LUT lookups + stores.
///
/// 40 KB in `.rodata`, generated at compile time. Indexed by `(u32) % 10_000`,
/// so the access pattern is bounded and cache-friendly when the same
/// magnitude is processed repeatedly (typical for float-heavy serialization).
static QUAD_LUT: [u8; 40_000] = {
    let mut buf = [0u8; 40_000];
    let mut n: u32 = 0;
    while n < 10_000 {
        let off = (n * 4) as usize;
        buf[off] = b'0' + (n / 1000) as u8;
        buf[off + 1] = b'0' + ((n / 100) % 10) as u8;
        buf[off + 2] = b'0' + ((n / 10) % 10) as u8;
        buf[off + 3] = b'0' + (n % 10) as u8;
        n += 1;
    }
    buf
};

const DIGIT_THRESHOLDS: [u64; 16] = [
    10_000_000_000_000_000, // ≥ this → 17
    1_000_000_000_000_000,  // ≥ this → 16
    100_000_000_000_000,    // ≥ this → 15
    10_000_000_000_000,     // ≥ this → 14
    1_000_000_000_000,      // ≥ this → 13
    100_000_000_000,        // ≥ this → 12
    10_000_000_000,         // ≥ this → 11
    1_000_000_000,          // ≥ this → 10
    100_000_000,            // ≥ this → 9
    10_000_000,             // ≥ this → 8
    1_000_000,              // ≥ this → 7
    100_000,                // ≥ this → 6
    10_000,                 // ≥ this → 5
    1_000,                  // ≥ this → 4
    100,                    // ≥ this → 3
    10,                     // ≥ this → 2
];

/// Digit count for any post-teju mantissa (≤ 17 digits — that's what
/// shortest-roundtrip guarantees). Table-driven to avoid a 17-branch
/// if-else chain. Ordered high-to-low so the common 15–17 digit case
/// exits early.
#[inline]
fn mantissa_digit_count(n: u64) -> usize {
    debug_assert!(n < 100_000_000_000_000_000); // < 10^17
    let mut i = 0;
    while i < DIGIT_THRESHOLDS.len() {
        if n >= DIGIT_THRESHOLDS[i] {
            return 17 - i;
        }
        i += 1;
    }
    1
}

/// Core formatter: write `value`'s shortest-roundtrip decimal into `buf`,
/// returning the byte length. `buf` must hold at least `FORMAT_BUF_LEN` (32)
/// bytes. The output is ASCII.
#[inline]
pub(crate) fn format_finite_to_buf(value: f64, buf: &mut [u8; FORMAT_BUF_LEN]) -> usize {
    #[allow(unsafe_code)]
    // SAFETY: buf is at least FORMAT_BUF_LEN = 32 bytes, the worst-case
    // length any finite f64 can produce.
    unsafe {
        format_finite_to_ptr(value, buf.as_mut_ptr())
    }
}

/// Core formatter: write `value`'s shortest-roundtrip decimal through `dst`,
/// returning the byte length. The output is ASCII.
///
/// # Safety
///
/// `dst` must point to at least `FORMAT_BUF_LEN` (32) writable bytes — the
/// worst case for any finite f64.
///
/// All writes go through `ptr::write` and `ptr::copy_nonoverlapping` (no
/// bounds checks); the slice-and-debug-assert version is `format_finite_to_buf`.
#[allow(unsafe_code)]
pub(crate) unsafe fn format_finite_to_ptr(value: f64, dst: *mut u8) -> usize {
    if value == 0.0 {
        let (src, len) = if value.is_sign_negative() {
            (b"-0.0".as_ptr(), 4)
        } else {
            (b"0.0".as_ptr(), 3)
        };
        // SAFETY: caller guarantees at least 32 writable bytes.
        unsafe { core::ptr::copy_nonoverlapping(src, dst, len) };
        return len;
    }

    let negative = value.is_sign_negative();
    let d = teju(value.abs());
    let digits_count = mantissa_digit_count(d.mantissa);
    // Always write '-' at dst[0]; the cursor advances past it only when
    // negative. For positive values the next field's write at offset 0
    // overwrites the '-'. This removes the sign branch (which was the
    // largest remaining mispredictor: 4% of all branch-misses at random
    // input, since `is_sign_negative` is 50/50 by construction).
    // SAFETY: caller guarantees ≥ 32 writable bytes; offset 0 is in bounds.
    unsafe { dst.write(b'-') };
    let pos = usize::from(negative);

    let point = digits_count as i32 + d.exponent;

    if (-6..=21).contains(&point) {
        // Fixed-point form.
        if point <= 0 {
            // "0." + (−point) zeros + digits
            let zeros = (-point) as usize;
            // SAFETY: pos + 2 + zeros + digits_count ≤ 1 + 2 + 6 + 17 = 26 ≤ 32.
            unsafe {
                dst.add(pos).write(b'0');
                dst.add(pos + 1).write(b'.');
                ptr_fill(dst.add(pos + 2), b'0', zeros);
                write_digits_at_ptr(d.mantissa, dst.add(pos + 2 + zeros), digits_count);
            }
            pos + 2 + zeros + digits_count
        } else if (point as usize) >= digits_count {
            // digits + (point − digits_count) zeros + ".0"
            let trail_zeros = point as usize - digits_count;
            // SAFETY: pos + digits_count + trail_zeros + 2 ≤ 1 + 21 + 2 = 24 ≤ 32.
            unsafe {
                write_digits_at_ptr(d.mantissa, dst.add(pos), digits_count);
                ptr_fill(dst.add(pos + digits_count), b'0', trail_zeros);
                let tail = dst.add(pos + digits_count + trail_zeros);
                tail.write(b'.');
                tail.add(1).write(b'0');
            }
            pos + digits_count + trail_zeros + 2
        } else {
            // digits[..p] + '.' + digits[p..]
            // Render digits into [pos+1 .. pos+1+digits_count] then shift the
            // leading p digits down by one to free the slot for '.'.
            let p = point as usize;
            // SAFETY: pos + 1 + digits_count ≤ 1 + 1 + 17 = 19 ≤ 32.
            unsafe {
                write_digits_at_ptr(d.mantissa, dst.add(pos + 1), digits_count);
                // Shift leading p digits left by 1. Overlapping copy ⇒ ptr::copy.
                core::ptr::copy(dst.add(pos + 1), dst.add(pos), p);
                dst.add(pos + p).write(b'.');
            }
            pos + digits_count + 1
        }
    } else {
        // Scientific form: "d.dddde±N".
        // Render digits into [pos+1 .. pos+1+digits_count], then drop the
        // first digit down to pos and overwrite pos+1 with '.' (when there
        // are ≥ 2 digits).
        // SAFETY: pos + 1 + digits_count + 5 ≤ 1 + 1 + 17 + 5 = 24 ≤ 32.
        unsafe {
            write_digits_at_ptr(d.mantissa, dst.add(pos + 1), digits_count);
            let lead = dst.add(pos + 1).read();
            dst.add(pos).write(lead);
            let after_mantissa = if digits_count > 1 {
                dst.add(pos + 1).write(b'.');
                pos + 1 + digits_count
            } else {
                pos + 1
            };
            dst.add(after_mantissa).write(b'e');
            let exp = point - 1;
            let exp_len = write_exponent_ptr(dst.add(after_mantissa + 1), exp);
            after_mantissa + 1 + exp_len
        }
    }
}

/// Fill `n` bytes at `dst` with `byte`. Used for zero-padding in the fixed
/// form. `n` is bounded by 22 here (point ∈ [−6, 21]).
///
/// # Safety
/// `dst` must point to ≥ `n` writable bytes.
#[inline]
#[allow(unsafe_code)]
unsafe fn ptr_fill(dst: *mut u8, byte: u8, n: usize) {
    // SAFETY: forwarded to caller.
    unsafe { core::ptr::write_bytes(dst, byte, n) };
}

/// Pointer-flavored `write_digits_at`. Writes `digits` decimal digits of `n`
/// to `dst[0..digits]`. Same algorithm as the slice version but unchecked.
///
/// # Safety
/// `dst` must point to ≥ `digits` writable bytes, and
/// `digits == mantissa_digit_count(n)`.
#[inline]
#[allow(unsafe_code, clippy::cast_possible_truncation)]
unsafe fn write_digits_at_ptr(n: u64, dst: *mut u8, digits: usize) {
    debug_assert_eq!(mantissa_digit_count(n), digits);

    // `pos` is the offset of the next byte to write (counts down).
    let mut pos = digits;
    let lut2 = DIGIT_LUT.as_ptr();
    let lut4 = QUAD_LUT.as_ptr();

    // Split a >32-bit value into (upper, lower 8 digits) with one
    // expensive 64-bit divide. Both halves then fit in u32.
    let mut output32 = if n >> 32 == 0 {
        n as u32
    } else {
        let low = (n - 100_000_000 * (n / 100_000_000)) as u32;
        let upper = (n / 100_000_000) as u32;

        // Write the bottom 8 digits as two 4-digit chunks via two 4-byte copies.
        let lo4 = (low % 10_000) as usize;
        let hi4 = (low / 10_000) as usize;
        // SAFETY: pos starts at digits ≥ 9 (we are in the >32-bit branch),
        // and decreases by 8 across the two 4-byte copies below; both
        // 4-byte LUT slots are inside the 40_000-byte table.
        unsafe {
            pos -= 4;
            core::ptr::copy_nonoverlapping(lut4.add(lo4 * 4), dst.add(pos), 4);
            pos -= 4;
            core::ptr::copy_nonoverlapping(lut4.add(hi4 * 4), dst.add(pos), 4);
        }
        upper
    };

    // 32-bit tail. Process 4 digits per iteration via one 4-byte copy.
    while output32 >= 10_000 {
        let c = (output32 - 10_000 * (output32 / 10_000)) as usize;
        output32 /= 10_000;
        // SAFETY: digit count was precomputed; pos decreases by 4 here
        // and the LUT slot is inside the 40_000-byte table.
        unsafe {
            pos -= 4;
            core::ptr::copy_nonoverlapping(lut4.add(c * 4), dst.add(pos), 4);
        }
    }
    // Tail: 1..=3 leading digits. The 2-digit LUT (200 bytes) handles
    // 2-digit chunks; we keep the single-byte fallback for a lone digit.
    if output32 >= 100 {
        let c = ((output32 % 100) * 2) as usize;
        output32 /= 100;
        // SAFETY: see loop above.
        unsafe {
            pos -= 2;
            core::ptr::copy_nonoverlapping(lut2.add(c), dst.add(pos), 2);
        }
    }
    if output32 >= 10 {
        let c = (output32 * 2) as usize;
        // SAFETY: see loop above.
        unsafe {
            pos -= 2;
            core::ptr::copy_nonoverlapping(lut2.add(c), dst.add(pos), 2);
        }
    } else {
        // SAFETY: see loop above.
        unsafe {
            pos -= 1;
            dst.add(pos).write(b'0' + output32 as u8);
        }
    }
    debug_assert_eq!(pos, 0);
}

/// Pointer-flavored `write_exponent`. Writes the exponent to `dst[0..]` and
/// returns the byte length (1–4 bytes including optional `-`).
///
/// # Safety
/// `dst` must point to ≥ 4 writable bytes.
#[inline]
#[allow(unsafe_code, clippy::cast_possible_truncation, clippy::cast_sign_loss)]
unsafe fn write_exponent_ptr(dst: *mut u8, exp: i32) -> usize {
    let (mag, sign_bytes) = if exp < 0 {
        // SAFETY: caller guarantees ≥ 4 bytes.
        unsafe { dst.write(b'-') };
        ((-exp) as u32, 1)
    } else {
        (exp as u32, 0)
    };
    let lut = DIGIT_LUT.as_ptr();
    // SAFETY: mag < 1000 in all cases (f64 exponent ≤ 308 in magnitude),
    // so we write at most 3 bytes after the optional sign.
    unsafe {
        if mag >= 100 {
            let hundreds = mag / 100;
            let rem = ((mag % 100) * 2) as usize;
            dst.add(sign_bytes).write(b'0' + hundreds as u8);
            core::ptr::copy_nonoverlapping(lut.add(rem), dst.add(sign_bytes + 1), 2);
            sign_bytes + 3
        } else if mag >= 10 {
            let r = (mag * 2) as usize;
            core::ptr::copy_nonoverlapping(lut.add(r), dst.add(sign_bytes), 2);
            sign_bytes + 2
        } else {
            dst.add(sign_bytes).write(b'0' + mag as u8);
            sign_bytes + 1
        }
    }
}

// ===========================================================================
// Public API — unchanged signatures from the Grisu3 era.
// ===========================================================================

// `expect`s below are unreachable: `format_finite_to_buf` only writes ASCII
// (digits, '.', 'e', '-', '+'). They guard a formatter-internal bug, not
// user input. ASCII validation of ≤32 bytes is one SIMD compare.

pub(crate) fn format_finite(f: f64, out: &mut String) {
    let mut buf = [0u8; FORMAT_BUF_LEN];
    let len = format_finite_to_buf(f, &mut buf);
    let s = core::str::from_utf8(&buf[..len]).expect("teju emits ASCII");
    out.push_str(s);
}

pub(crate) fn format_finite_fmt<W: fmt::Write + ?Sized>(f: f64, out: &mut W) -> fmt::Result {
    let mut buf = [0u8; FORMAT_BUF_LEN];
    let len = format_finite_to_buf(f, &mut buf);
    let s = core::str::from_utf8(&buf[..len]).expect("teju emits ASCII");
    out.write_str(s)
}

/// `Vec<u8>` path used by `ByteSink::write_float_f64`. Renders to a 32-byte
/// stack buffer, then `extend_from_slice`s into the output Vec.
///
/// Why the scratch buffer (vs writing the bytes straight into `out`'s tail):
/// `format_finite_to_ptr` emits scattered byte writes (the integer prefix,
/// the `'.'` byte, the trailing digits) at different offsets within the
/// output. Routing them through `dst.add(...).write(b)` on the output Vec's
/// tail interleaves stores into pages that may be cold (large outputs
/// exceed L1). The same stores into a 32-byte stack buffer hit a single
/// cache line every iteration, then a single `extend_from_slice` lets the
/// optimized memcpy stream the result into the output Vec contiguously.
/// This is exactly what `zmij` (serde_json's float formatter) does, and
/// it's what keeps its per-element cost flat as output grows past L1.
///
/// Returns `true` for finite `f` (writing its decimal form), `false` for
/// non-finite inputs (writing nothing). Folding the finiteness check in
/// here keeps `f` live in `xmm0` across the call.
#[cfg(feature = "alloc")]
#[allow(unsafe_code)]
#[inline]
pub(crate) fn format_finite_to_vec(f: f64, out: &mut alloc::vec::Vec<u8>) -> bool {
    // Cheap bit-pattern finiteness test: the exponent field is all-ones only
    // for ±inf and NaN.
    const EXP_MASK: u64 = 0x7ff0_0000_0000_0000;
    if f.to_bits() & EXP_MASK == EXP_MASK {
        return false;
    }
    let mut buf = [0u8; FORMAT_BUF_LEN];
    // SAFETY: `buf` is FORMAT_BUF_LEN = 32 bytes, the documented worst case.
    let len = unsafe { format_finite_to_ptr(f, buf.as_mut_ptr()) };
    out.extend_from_slice(&buf[..len]);
    true
}

/// `Vec<u8>` path used by `ByteSink::write_float_f64` when the caller has
/// pre-reserved enough capacity. Skips `Vec::extend_from_slice`'s
/// per-call capacity check + grow path (the second-biggest mispredict
/// source after the comma `Vec::push`). Writes through a raw pointer
/// straight into the reserved tail, then bumps `set_len`.
///
/// Returns `true` for finite `f`, `false` otherwise (no bytes written
/// in that case — `out`'s length is untouched).
///
/// # Safety
/// `out.capacity() - out.len()` must be ≥ `FORMAT_BUF_LEN` (32) bytes.
/// The array-write path in `ser.rs` ensures this via `reserve_hint`.
#[cfg(feature = "alloc")]
#[allow(unsafe_code)]
#[inline]
pub(crate) unsafe fn format_finite_to_vec_unchecked(f: f64, out: &mut alloc::vec::Vec<u8>) -> bool {
    const EXP_MASK: u64 = 0x7ff0_0000_0000_0000;
    if f.to_bits() & EXP_MASK == EXP_MASK {
        return false;
    }
    // SAFETY:
    //   - caller guarantees `cap - len >= FORMAT_BUF_LEN`, so writing up
    //     to 32 bytes at `out.as_mut_ptr().add(out.len())` is in-bounds;
    //   - `format_finite_to_ptr` returns the actual byte count
    //     (`≤ FORMAT_BUF_LEN`), which we use for `set_len`;
    //   - the written bytes are ASCII (digits, '.', 'e', '-'), keeping
    //     `Vec<u8>` validity intact.
    unsafe {
        let len = out.len();
        let dst = out.as_mut_ptr().add(len);
        let written = format_finite_to_ptr(f, dst);
        out.set_len(len + written);
    }
    true
}

/// `Vec<u8>` path that branchlessly tolerates non-finite input. Always
/// writes 24-byte-bounded output; for non-finite values, the bytes are
/// garbage (but valid ASCII) and the caller is expected to discard the
/// `Vec` via the returned taint bit.
///
/// Returns a `u64` that is non-zero iff `f` was non-finite. The caller
/// accumulates these bits across a slice's worth of writes and checks
/// once at the end — no per-element branch.
///
/// Why: `pre_validate_slice` adds an entire scan pass over the input,
/// which `perf record -c cycles` showed costing ~20% of total cycles
/// at n=10000 (the SIMD-vectorised pand/pcmpeqd loop). Folding the
/// finiteness check into the per-element work eliminates that pass.
///
/// # Safety
/// `out.capacity() - out.len()` must be ≥ `FORMAT_BUF_LEN` (32) bytes.
#[cfg(feature = "alloc")]
#[allow(unsafe_code)]
#[inline]
pub(crate) unsafe fn format_finite_to_vec_taint(f: f64, out: &mut alloc::vec::Vec<u8>) -> u64 {
    const EXP_MASK: u64 = 0x7ff0_0000_0000_0000;
    let bits = f.to_bits();
    let is_nonfinite = (bits & EXP_MASK) == EXP_MASK;
    // Branchless substitute: if non-finite, replace `f` with `1.0` so
    // the teju math never indexes out of MULTIPLIERS. The substitute
    // value's ASCII output goes into `out` but is junk; the caller's
    // taint check rejects the whole call, so the bytes are never
    // observed.
    let safe = if is_nonfinite { 1.0_f64 } else { f };
    // SAFETY: caller-reserved ≥ 32 bytes; `safe` is finite by
    // construction so `format_finite_to_ptr` does not OOB-read
    // `MULTIPLIERS`.
    unsafe {
        let len = out.len();
        let dst = out.as_mut_ptr().add(len);
        let written = format_finite_to_ptr(safe, dst);
        out.set_len(len + written);
    }
    u64::from(is_nonfinite)
}

/// Like [`format_finite_to_vec_unchecked`] but the caller PROMISES `f`
/// is finite — no per-call finiteness branch. The slice path
/// `[f64]::write_json` calls this after a one-shot pre-scan of the
/// whole slice for non-finite inputs.
///
/// The finiteness branch was the single dominant remaining mispredict
/// in the bench's per-element loop (`perf record -e branch-misses`
/// showed 13.43% of all mispredicts attributed to it). Eliminating it
/// removes the structural data-dependent cliff at large N.
///
/// # Safety
///   - `out.capacity() - out.len()` must be ≥ `FORMAT_BUF_LEN` (32).
///   - `f` must be finite (`is_finite() == true`). Passing inf or NaN
///     is undefined behaviour: `teju` uses the IEEE exponent bits to
///     index `MULTIPLIERS`, and non-finite exponents fall outside the
///     valid index range.
#[cfg(feature = "alloc")]
#[allow(unsafe_code)]
#[inline]
pub(crate) unsafe fn format_finite_to_vec_unchecked_finite(f: f64, out: &mut alloc::vec::Vec<u8>) {
    debug_assert!(f.is_finite(), "caller violated finite-input precondition");
    // SAFETY: see `format_finite_to_vec_unchecked`. Additionally, the
    // caller's finiteness precondition makes `format_finite_to_ptr`'s
    // teju-table indexing well-defined.
    unsafe {
        let len = out.len();
        let dst = out.as_mut_ptr().add(len);
        let written = format_finite_to_ptr(f, dst);
        out.set_len(len + written);
    }
}

// ===========================================================================
// Tables — generated by teju_gen.rs, cross-validated against C reference.
// ===========================================================================

const STORAGE_INDEX_OFFSET: i32 = -324;

include!("teju_tables.txt");

// ===========================================================================
// Tests.
// ===========================================================================

#[cfg(all(test, feature = "alloc"))]
mod tests {
    use super::*;
    use alloc::format;
    use alloc::string::String;

    #[test]
    fn teju_output_roundtrips() {
        let mut state: u64 = 0xCAFE_BABE_DEAD_BEEF;
        for (count, _) in (0..10_000).enumerate() {
            state = state
                .wrapping_mul(6_364_136_223_846_793_005)
                .wrapping_add(1_442_695_040_888_963_407);
            let mantissa = (state >> 11) as f64 / (1u64 << 53) as f64;
            let signed = mantissa.mul_add(2.0, -1.0);
            let v = match count % 10 {
                0 => signed * 1e-6,
                1 => signed * 1e6,
                _ => signed * 100.0,
            };
            if !v.is_finite() || v == 0.0 {
                continue;
            }
            let mut out = String::new();
            format_finite(v, &mut out);
            let parsed: f64 = out.parse().expect("our output parses");
            // Bit-pattern equality: format→parse must round-trip to the
            // identical IEEE 754 encoding.
            assert_eq!(
                parsed.to_bits(),
                v.to_bits(),
                "roundtrip failed: formatted={out:?} for v={v:e} (bits=0x{:016x})",
                v.to_bits()
            );
        }
    }

    #[test]
    fn teju_matches_libstd_display() {
        let cases = [
            1.0_f64,
            1.5,
            0.1,
            0.2,
            0.3,
            100.0,
            12.5,
            1.5e10,
            -2.7e-5,
            1234.5678,
            1e100,
            1e-100,
            1.7976931348623157e308,
            5e-324,
        ];
        for &v in &cases {
            if v == 0.0 || !v.is_finite() {
                continue;
            }
            let mut ours = String::new();
            format_finite(v, &mut ours);
            let libstd = format!("{v}");
            let ours_parsed: f64 = ours.parse().expect("ours parses");
            let libstd_parsed: f64 = libstd.parse().expect("libstd parses");
            // Bit-pattern equality — both strings must parse to the same f64
            // encoding, even though their textual forms may differ in
            // grouping (e.g. "1e10" vs "10000000000").
            assert_eq!(
                ours_parsed.to_bits(),
                libstd_parsed.to_bits(),
                "ours={ours:?} libstd={libstd:?} for v={v:e}",
            );
        }
    }

    #[test]
    fn teju_edge_cases() {
        let cases: &[(f64, &str)] = &[
            (1.0, "1.0"),
            (2.0, "2.0"),
            (0.5, "0.5"),
            (10.0, "10.0"),
            (100.0, "100.0"),
            (1e20, "100000000000000000000.0"),
            (1.5, "1.5"),
        ];
        for &(v, expected) in cases {
            let mut out = String::new();
            format_finite(v, &mut out);
            assert_eq!(out, expected, "for {v}");
        }
    }

    #[test]
    fn teju_zero_handling() {
        let mut pos = String::new();
        format_finite(0.0, &mut pos);
        assert_eq!(pos, "0.0");

        let mut neg = String::new();
        format_finite(-0.0, &mut neg);
        assert_eq!(neg, "-0.0");
    }

    #[test]
    fn teju_small_integers() {
        // Verify via string round-trip rather than `mantissa as f64 * 10^exp`:
        // `f64::powi` is libm-backed and miri's host libm may differ from the
        // production host (we observed `10f64.powi(1)` returning a 1 ULP off
        // value under miri), which is unrelated to whether teju's decomposition
        // is correct. The string is the contract we actually ship.
        for i in 1u32..=1000 {
            let v = f64::from(i);
            let mut s = String::new();
            format_finite(v, &mut s);
            let parsed: f64 = s.parse().expect("our output parses");
            // Bit-pattern equality: small integers round-trip exactly.
            assert_eq!(
                parsed.to_bits(),
                v.to_bits(),
                "small integer {i}: round-tripped through {s:?}"
            );
        }
    }

    /// Exhaustively format every uncentred f64 (powers of two from
    /// 2^-1022 through 2^1023). These hit `to_decimal_uncentred`,
    /// covering both its `a < b` (the common case) and `a >= b` arms.
    /// Round-tripping via string parse guards against silent corruption.
    #[test]
    fn teju_every_uncentred_value_round_trips() {
        let mantissa_uncentred = 1u64 << 52;
        for biased_exp in 1u64..=0x7FE {
            let bits = (biased_exp << 52) | (mantissa_uncentred & ((1 << 52) - 1));
            let v = f64::from_bits(bits);
            assert!(v.is_finite(), "biased_exp={biased_exp}");
            let mut s = String::new();
            format_finite(v, &mut s);
            let parsed: f64 = s.parse().expect("our output parses");
            // Bit-pattern equality: exact round-trip is the contract.
            assert_eq!(
                parsed.to_bits(),
                v.to_bits(),
                "uncentred f64 with biased_exp={biased_exp} round-trip failed: {s:?}"
            );
        }
    }

    // ---------------------------------------------------------------------
    // Unsafe-boundary tests — these specifically exercise the caller-side
    // capacity contract of the `_unchecked` Vec-tail writers under miri,
    // including the exact-fit case `cap == len + FORMAT_BUF_LEN`.
    //
    // The full ser path always pre-reserves plenty of headroom via
    // `reserve_hint`, so these are the only places that hit the boundary
    // precisely. A regression that miscomputed `cap - len` would slip past
    // the round-trip tests but blow up here under miri's strict pointer
    // tracking.
    // ---------------------------------------------------------------------

    /// `format_finite_to_vec_unchecked` at exact `cap == len + 32`. Covers
    /// every output form (zero, fixed, scientific) so each branch's worst-
    /// case write lands at the boundary.
    #[test]
    fn vec_unchecked_at_exact_capacity() {
        // (input, output form name)
        let cases: &[f64] = &[
            0.0,
            -0.0,
            1.0,
            -1.0,
            1.5,
            0.1,
            123_456_789.0,
            -1.5e10,
            -2.7e-5,
            1.7976931348623157e308,
            5e-324,
        ];
        for &v in cases {
            let mut out = alloc::vec::Vec::with_capacity(FORMAT_BUF_LEN);
            // SAFETY: capacity is exactly FORMAT_BUF_LEN, contract met.
            #[allow(unsafe_code)]
            let ok = unsafe { format_finite_to_vec_unchecked(v, &mut out) };
            assert!(ok, "finite input rejected: {v}");
            assert!(
                out.len() <= FORMAT_BUF_LEN,
                "len={} > 32 for {v}",
                out.len()
            );
            assert!(!out.is_empty(), "empty output for {v}");
            // Output must be valid ASCII.
            for &b in &out {
                assert!(b.is_ascii(), "non-ASCII byte {b:#x} in output for {v}");
            }
        }
    }

    /// `format_finite_to_vec_unchecked` returns `false` for non-finite,
    /// writing zero bytes. Exercises the early-return arm where `out.len`
    /// is left untouched.
    #[test]
    fn vec_unchecked_rejects_nonfinite_without_touching_buf() {
        for v in [f64::INFINITY, f64::NEG_INFINITY, f64::NAN] {
            let mut out = alloc::vec::Vec::with_capacity(FORMAT_BUF_LEN);
            #[allow(unsafe_code)]
            let ok = unsafe { format_finite_to_vec_unchecked(v, &mut out) };
            assert!(!ok, "non-finite accepted: {v}");
            assert!(out.is_empty(), "buffer touched for non-finite {v}: {out:?}");
        }
    }

    /// `format_finite_to_vec_taint` at exact capacity. The taint path
    /// always writes — even for non-finite, where it substitutes 1.0 and
    /// flags via the returned bit. Verify the substitute path under miri.
    #[test]
    fn vec_taint_at_exact_capacity() {
        // Finite case: returns 0, writes real ASCII.
        let mut out = alloc::vec::Vec::with_capacity(FORMAT_BUF_LEN);
        #[allow(unsafe_code)]
        let taint = unsafe { format_finite_to_vec_taint(1.5_f64, &mut out) };
        assert_eq!(taint, 0);
        assert_eq!(&out[..], b"1.5");

        // Non-finite: returns non-zero, writes the substitute's ASCII.
        for v in [f64::INFINITY, f64::NEG_INFINITY, f64::NAN] {
            let mut out = alloc::vec::Vec::with_capacity(FORMAT_BUF_LEN);
            #[allow(unsafe_code)]
            let taint = unsafe { format_finite_to_vec_taint(v, &mut out) };
            assert_ne!(taint, 0, "taint not set for {v}");
            assert!(!out.is_empty(), "substitute did not write for {v}");
            assert!(out.len() <= FORMAT_BUF_LEN);
        }
    }

    /// `format_finite_to_vec_unchecked_finite` — caller-promised finite,
    /// no per-call check. Hit every digit-count branch in
    /// `mantissa_digit_count` so `write_digits_at_ptr` exercises both its
    /// >32-bit and 32-bit-tail paths.
    #[test]
    fn vec_unchecked_finite_covers_digit_counts() {
        // Values picked to hit different digit counts (1..=17) and both
        // fixed-point and scientific output forms.
        let cases: &[f64] = &[
            1.0,
            12.0,
            123.0,
            1234.0,
            12345.0,
            123_456.0,
            1_234_567.0,
            12_345_678.0, // 8-digit (boundary for >32-bit split)
            123_456_789.0,
            1_234_567_890.0,
            12_345_678_901.0,
            123_456_789_012.0,
            1_234_567_890_123.0,
            12_345_678_901_234.0,
            123_456_789_012_345.0,
            1_234_567_890_123_456.0,  // 16-digit
            12_345_678_901_234_567.0, // 17-digit boundary
            1e-300,                   // far-negative exponent, scientific
            1e300,                    // far-positive exponent, scientific
        ];
        for &v in cases {
            assert!(v.is_finite(), "test bug: non-finite case {v}");
            let mut out = alloc::vec::Vec::with_capacity(FORMAT_BUF_LEN);
            #[allow(unsafe_code)]
            unsafe {
                format_finite_to_vec_unchecked_finite(v, &mut out);
            }
            assert!(!out.is_empty(), "no output for {v}");
            assert!(out.len() <= FORMAT_BUF_LEN);
            for &b in &out {
                assert!(b.is_ascii(), "non-ASCII for {v}: {out:?}");
            }
        }
    }

    /// All three Vec-tail writers, called repeatedly on the same Vec so
    /// the ASCII bytes accumulate. Catches off-by-one in `len + written`.
    #[test]
    fn vec_unchecked_repeated_writes_accumulate() {
        // u32 because we widen losslessly to f64 below; the loop bound also
        // makes it fit u8, but u32 keeps the conversion site obvious.
        let n: u32 = 50;
        let cap = 2 + (n as usize) * (FORMAT_BUF_LEN + 1);
        let mut out: alloc::vec::Vec<u8> = alloc::vec::Vec::with_capacity(cap);
        for i in 0..n {
            let v = f64::from(i) + 0.5;
            #[allow(unsafe_code)]
            unsafe {
                format_finite_to_vec_unchecked_finite(v, &mut out);
                if i + 1 < n {
                    // Comma between elements — same unchecked-write pattern
                    // the slice writer uses.
                    let len = out.len();
                    let dst = out.as_mut_ptr().add(len);
                    core::ptr::write(dst, b',');
                    out.set_len(len + 1);
                }
            }
        }
        // Parse it back as a CSV of floats.
        let s = core::str::from_utf8(&out).expect("ASCII");
        let parts: alloc::vec::Vec<f64> = s
            .split(',')
            .map(|x| x.parse::<f64>().expect("our output parses"))
            .collect();
        assert_eq!(parts.len(), n as usize);
        for (i, &v) in parts.iter().enumerate() {
            let expected = f64::from(u32::try_from(i).expect("n=50 fits u32")) + 0.5;
            // Bit-pattern equality: format→parse round-trip is exact for these
            // tiny half-integer values.
            assert_eq!(v.to_bits(), expected.to_bits(), "round-trip {i}");
        }
    }
}