yo_common/

dtoa.rs

//! Redis's double printer, which is Grisu2 by way of fpconv.
//!
//! Redis 7 stopped writing doubles with `%.17g` and started calling
//! `fpconv_dtoa`, a small Grisu2 implementation it vendors under
//! `deps/fpconv`. Every double a client reads comes out of it: a sorted set
//! score, an `INCRBYFLOAT` reply, a geo distance, a RESP3 double. So the exact
//! bytes it produces are part of the protocol, and there are two reasons a
//! shortest round trip printer from somewhere else does not reproduce them.
//!
//! The first is presentation. fpconv switches to an exponent for a large or a
//! small magnitude and Rust's `Display` never does, so `1e+30` and
//! `1000000000000000000000000000000` are the same number written two ways and a
//! client comparing bytes sees two different answers. That part could have been
//! fixed by reshaping Rust's digits.
//!
//! The second is the digits themselves, and it could not. Grisu2 is not always
//! shortest. It finds the shortest representation for about nineteen values in
//! twenty and emits one extra digit for the rest, and which values fall in
//! which set is a property of the algorithm rather than of the number. Rust's
//! printer is always shortest. So no amount of reformatting closes the gap, and
//! the only way to answer what Redis answers is to run what Redis runs.
//!
//! This is that port, kept deliberately line for line with the C so that the
//! next time Redis changes it the diff is readable. The one thing that could
//! not be carried across literally is unsigned overflow: C leaves it wrapping
//! and Rust panics on it in a debug build, so every place the original relies
//! on wrapping is spelled out with a `wrapping_` call.
//!
//! ----------------------------------------------------------------------------
//!
//! Copyright (c) 2021, Redis Labs
//! Copyright (c) 2013-2019, night-shift <as.smljk at gmail dot com>
//! Copyright (c) 2009, Florian Loitsch < florian.loitsch at inria dot fr >
//! All rights reserved.
//!
//! Boost Software License - Version 1.0 - August 17th, 2003
//!
//! Permission is hereby granted, free of charge, to any person or organization
//! obtaining a copy of the software and accompanying documentation covered by
//! this license (the "Software") to use, reproduce, display, distribute,
//! execute, and transmit the Software, and to prepare derivative works of the
//! Software, and to permit third-parties to whom the Software is furnished to
//! do so, all subject to the following:
//!
//! The copyright notices in the Software and this entire statement, including
//! the above license grant, this restriction and the following disclaimer,
//! must be included in all copies of the Software, in whole or in part, and
//! all derivative works of the Software, unless such copies or derivative
//! works are solely in the form of machine-executable object code generated by
//! a source language processor.
//!
//! THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//! IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//! FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
//! SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
//! FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
//! ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
//! DEALINGS IN THE SOFTWARE.

/// Room for anything [`dtoa`] can write.
///
/// The widest output is the plain integer branch at its limit, which is
/// seventeen digits and seven zeros, and a sign in front of it. The C carries a
/// twenty four byte buffer for the same thing and relies on its caller passing
/// something larger, so this is rounded up to a power of two instead.
pub const MAX: usize = 32;

const FRACMASK: u64 = 0x000F_FFFF_FFFF_FFFF;
const EXPMASK: u64 = 0x7FF0_0000_0000_0000;
const HIDDENBIT: u64 = 0x0010_0000_0000_0000;
const SIGNMASK: u64 = 0x8000_0000_0000_0000;
const EXPBIAS: i32 = 1023 + 52;

/// The powers of ten the digit generator divides by, largest first.
const TENS: [u64; 20] = [
    10_000_000_000_000_000_000,
    1_000_000_000_000_000_000,
    100_000_000_000_000_000,
    10_000_000_000_000_000,
    1_000_000_000_000_000,
    100_000_000_000_000,
    10_000_000_000_000,
    1_000_000_000_000,
    100_000_000_000,
    10_000_000_000,
    1_000_000_000,
    100_000_000,
    10_000_000,
    1_000_000,
    100_000,
    10_000,
    1_000,
    100,
    10,
    1,
];

/// A number held as a fraction and a binary exponent, wider than a double.
///
/// Grisu works in this form rather than in doubles because it needs the extra
/// bits to know when it is allowed to stop emitting digits.
#[derive(Clone, Copy)]
struct Fp {
    frac: u64,
    exp: i32,
}

const NPOWERS: i32 = 87;
const STEPPOWERS: i32 = 8;
const FIRSTPOWER: i32 = -348;
const EXPMAX: i32 = -32;
const EXPMIN: i32 = -60;

/// Every eighth power of ten from `10^-348` up, each as the closest `Fp`.
///
/// Eight apart rather than one because the algorithm only needs to land inside
/// a window of binary exponents, not on an exact power, and a table of eighty
/// seven entries is small enough to stay in cache where a table of seven
/// hundred would not.
static POWERS_TEN: [Fp; 87] = [
    Fp {
        frac: 18054884314459144840,
        exp: -1220,
    },
    Fp {
        frac: 13451937075301367670,
        exp: -1193,
    },
    Fp {
        frac: 10022474136428063862,
        exp: -1166,
    },
    Fp {
        frac: 14934650266808366570,
        exp: -1140,
    },
    Fp {
        frac: 11127181549972568877,
        exp: -1113,
    },
    Fp {
        frac: 16580792590934885855,
        exp: -1087,
    },
    Fp {
        frac: 12353653155963782858,
        exp: -1060,
    },
    Fp {
        frac: 18408377700990114895,
        exp: -1034,
    },
    Fp {
        frac: 13715310171984221708,
        exp: -1007,
    },
    Fp {
        frac: 10218702384817765436,
        exp: -980,
    },
    Fp {
        frac: 15227053142812498563,
        exp: -954,
    },
    Fp {
        frac: 11345038669416679861,
        exp: -927,
    },
    Fp {
        frac: 16905424996341287883,
        exp: -901,
    },
    Fp {
        frac: 12595523146049147757,
        exp: -874,
    },
    Fp {
        frac: 9384396036005875287,
        exp: -847,
    },
    Fp {
        frac: 13983839803942852151,
        exp: -821,
    },
    Fp {
        frac: 10418772551374772303,
        exp: -794,
    },
    Fp {
        frac: 15525180923007089351,
        exp: -768,
    },
    Fp {
        frac: 11567161174868858868,
        exp: -741,
    },
    Fp {
        frac: 17236413322193710309,
        exp: -715,
    },
    Fp {
        frac: 12842128665889583758,
        exp: -688,
    },
    Fp {
        frac: 9568131466127621947,
        exp: -661,
    },
    Fp {
        frac: 14257626930069360058,
        exp: -635,
    },
    Fp {
        frac: 10622759856335341974,
        exp: -608,
    },
    Fp {
        frac: 15829145694278690180,
        exp: -582,
    },
    Fp {
        frac: 11793632577567316726,
        exp: -555,
    },
    Fp {
        frac: 17573882009934360870,
        exp: -529,
    },
    Fp {
        frac: 13093562431584567480,
        exp: -502,
    },
    Fp {
        frac: 9755464219737475723,
        exp: -475,
    },
    Fp {
        frac: 14536774485912137811,
        exp: -449,
    },
    Fp {
        frac: 10830740992659433045,
        exp: -422,
    },
    Fp {
        frac: 16139061738043178685,
        exp: -396,
    },
    Fp {
        frac: 12024538023802026127,
        exp: -369,
    },
    Fp {
        frac: 17917957937422433684,
        exp: -343,
    },
    Fp {
        frac: 13349918974505688015,
        exp: -316,
    },
    Fp {
        frac: 9946464728195732843,
        exp: -289,
    },
    Fp {
        frac: 14821387422376473014,
        exp: -263,
    },
    Fp {
        frac: 11042794154864902060,
        exp: -236,
    },
    Fp {
        frac: 16455045573212060422,
        exp: -210,
    },
    Fp {
        frac: 12259964326927110867,
        exp: -183,
    },
    Fp {
        frac: 18268770466636286478,
        exp: -157,
    },
    Fp {
        frac: 13611294676837538539,
        exp: -130,
    },
    Fp {
        frac: 10141204801825835212,
        exp: -103,
    },
    Fp {
        frac: 15111572745182864684,
        exp: -77,
    },
    Fp {
        frac: 11258999068426240000,
        exp: -50,
    },
    Fp {
        frac: 16777216000000000000,
        exp: -24,
    },
    Fp {
        frac: 12500000000000000000,
        exp: 3,
    },
    Fp {
        frac: 9313225746154785156,
        exp: 30,
    },
    Fp {
        frac: 13877787807814456755,
        exp: 56,
    },
    Fp {
        frac: 10339757656912845936,
        exp: 83,
    },
    Fp {
        frac: 15407439555097886824,
        exp: 109,
    },
    Fp {
        frac: 11479437019748901445,
        exp: 136,
    },
    Fp {
        frac: 17105694144590052135,
        exp: 162,
    },
    Fp {
        frac: 12744735289059618216,
        exp: 189,
    },
    Fp {
        frac: 9495567745759798747,
        exp: 216,
    },
    Fp {
        frac: 14149498560666738074,
        exp: 242,
    },
    Fp {
        frac: 10542197943230523224,
        exp: 269,
    },
    Fp {
        frac: 15709099088952724970,
        exp: 295,
    },
    Fp {
        frac: 11704190886730495818,
        exp: 322,
    },
    Fp {
        frac: 17440603504673385349,
        exp: 348,
    },
    Fp {
        frac: 12994262207056124023,
        exp: 375,
    },
    Fp {
        frac: 9681479787123295682,
        exp: 402,
    },
    Fp {
        frac: 14426529090290212157,
        exp: 428,
    },
    Fp {
        frac: 10748601772107342003,
        exp: 455,
    },
    Fp {
        frac: 16016664761464807395,
        exp: 481,
    },
    Fp {
        frac: 11933345169920330789,
        exp: 508,
    },
    Fp {
        frac: 17782069995880619868,
        exp: 534,
    },
    Fp {
        frac: 13248674568444952270,
        exp: 561,
    },
    Fp {
        frac: 9871031767461413346,
        exp: 588,
    },
    Fp {
        frac: 14708983551653345445,
        exp: 614,
    },
    Fp {
        frac: 10959046745042015199,
        exp: 641,
    },
    Fp {
        frac: 16330252207878254650,
        exp: 667,
    },
    Fp {
        frac: 12166986024289022870,
        exp: 694,
    },
    Fp {
        frac: 18130221999122236476,
        exp: 720,
    },
    Fp {
        frac: 13508068024458167312,
        exp: 747,
    },
    Fp {
        frac: 10064294952495520794,
        exp: 774,
    },
    Fp {
        frac: 14996968138956309548,
        exp: 800,
    },
    Fp {
        frac: 11173611982879273257,
        exp: 827,
    },
    Fp {
        frac: 16649979327439178909,
        exp: 853,
    },
    Fp {
        frac: 12405201291620119593,
        exp: 880,
    },
    Fp {
        frac: 9242595204427927429,
        exp: 907,
    },
    Fp {
        frac: 13772540099066387757,
        exp: 933,
    },
    Fp {
        frac: 10261342003245940623,
        exp: 960,
    },
    Fp {
        frac: 15290591125556738113,
        exp: 986,
    },
    Fp {
        frac: 11392378155556871081,
        exp: 1013,
    },
    Fp {
        frac: 16975966327722178521,
        exp: 1039,
    },
    Fp {
        frac: 12648080533535911531,
        exp: 1066,
    },
];

/// The table entry whose binary exponent brings `exp` into the working window.
///
/// The first guess comes from a logarithm and is then walked one entry at a
/// time, which sounds slack and is not: the guess is within one of the answer
/// for every input, so the loop runs once or twice and never searches.
fn find_cachedpow10(exp: i32, k: &mut i32) -> Fp {
    const ONE_LOG_TEN: f64 = 0.30102999566398114;

    let approx = (-((exp + NPOWERS) as f64) * ONE_LOG_TEN) as i32;
    let mut idx = (approx - FIRSTPOWER) / STEPPOWERS;

    loop {
        let current = exp + POWERS_TEN[idx as usize].exp + 64;
        if current < EXPMIN {
            idx += 1;
            continue;
        }
        if current > EXPMAX {
            idx -= 1;
            continue;
        }
        *k = FIRSTPOWER + idx * STEPPOWERS;
        return POWERS_TEN[idx as usize];
    }
}

/// A double taken apart into its stored fraction and exponent.
fn build_fp(d: f64) -> Fp {
    let bits = d.to_bits();
    let mut fp = Fp {
        frac: bits & FRACMASK,
        exp: ((bits & EXPMASK) >> 52) as i32,
    };
    if fp.exp != 0 {
        fp.frac += HIDDENBIT;
        fp.exp -= EXPBIAS;
    } else {
        fp.exp = -EXPBIAS + 1;
    }
    fp
}

/// Shifts the fraction up until its top bit is set, which is where the
/// multiply below is accurate.
fn normalize(fp: &mut Fp) {
    while fp.frac & HIDDENBIT == 0 {
        fp.frac <<= 1;
        fp.exp -= 1;
    }
    let shift = 64 - 52 - 1;
    fp.frac <<= shift;
    fp.exp -= shift;
}

/// The half way points either side of `fp`, which are the edges of the set of
/// decimals that read back as this exact double.
fn get_normalized_boundaries(fp: &Fp, lower: &mut Fp, upper: &mut Fp) {
    upper.frac = (fp.frac << 1) + 1;
    upper.exp = fp.exp - 1;

    while upper.frac & (HIDDENBIT << 1) == 0 {
        upper.frac <<= 1;
        upper.exp -= 1;
    }

    let u_shift = 64 - 52 - 2;
    upper.frac <<= u_shift;
    upper.exp -= u_shift;

    // A power of two has a closer neighbour below it than above it, so its
    // lower boundary is half a step away rather than a whole one.
    let l_shift = if fp.frac == HIDDENBIT { 2 } else { 1 };

    lower.frac = (fp.frac << l_shift) - 1;
    lower.exp = fp.exp - l_shift;

    lower.frac <<= lower.exp - upper.exp;
    lower.exp = upper.exp;
}

/// The high sixty four bits of the product, rounded.
fn multiply(a: &Fp, b: &Fp) -> Fp {
    const LOMASK: u64 = 0x0000_0000_FFFF_FFFF;

    let ah_bl = (a.frac >> 32).wrapping_mul(b.frac & LOMASK);
    let al_bh = (a.frac & LOMASK).wrapping_mul(b.frac >> 32);
    let al_bl = (a.frac & LOMASK).wrapping_mul(b.frac & LOMASK);
    let ah_bh = (a.frac >> 32).wrapping_mul(b.frac >> 32);

    let mut tmp = (ah_bl & LOMASK)
        .wrapping_add(al_bh & LOMASK)
        .wrapping_add(al_bl >> 32);
    // Round up rather than truncate.
    tmp = tmp.wrapping_add(1u64 << 31);

    Fp {
        frac: ah_bh
            .wrapping_add(ah_bl >> 32)
            .wrapping_add(al_bh >> 32)
            .wrapping_add(tmp >> 32),
        exp: a.exp + b.exp + 64,
    }
}

/// Walks the last digit back while a smaller one is still closer to the value.
fn round_digit(digits: &mut [u8; 18], ndigits: usize, delta: u64, rem: u64, kappa: u64, frac: u64) {
    let mut rem = rem;
    while rem < frac
        && delta.wrapping_sub(rem) >= kappa
        && (rem.wrapping_add(kappa) < frac
            || frac.wrapping_sub(rem) > rem.wrapping_add(kappa).wrapping_sub(frac))
    {
        digits[ndigits - 1] -= 1;
        rem = rem.wrapping_add(kappa);
    }
}

/// Emits digits from the top down and stops as soon as the number read back
/// would land inside the boundaries.
///
/// The first loop takes the integral part apart with the table of powers, and
/// the second one multiplies the fractional part by ten a digit at a time. It
/// is the early return out of either that makes the output short.
fn generate_digits(fp: &Fp, upper: &Fp, lower: &Fp, digits: &mut [u8; 18], k: &mut i32) -> usize {
    let wfrac = upper.frac.wrapping_sub(fp.frac);
    let mut delta = upper.frac.wrapping_sub(lower.frac);

    let shift = (-upper.exp) as u32;
    let one_frac = 1u64 << shift;

    let mut part1 = upper.frac >> shift;
    let mut part2 = upper.frac & (one_frac - 1);

    let mut idx = 0usize;
    let mut kappa: i32 = 10;

    // Starting at 10^9, the largest power the integral part can hold.
    let mut divp = 10usize;
    while kappa > 0 {
        let div = TENS[divp];
        let digit = part1 / div;

        if digit != 0 || idx != 0 {
            digits[idx] = b'0' + digit as u8;
            idx += 1;
        }

        part1 -= digit * div;
        kappa -= 1;

        let tmp = (part1.wrapping_shl(shift)).wrapping_add(part2);
        if tmp <= delta {
            *k += kappa;
            round_digit(digits, idx, delta, tmp, div.wrapping_shl(shift), wfrac);
            return idx;
        }
        divp += 1;
    }

    let mut unit = 18usize;
    loop {
        part2 = part2.wrapping_mul(10);
        delta = delta.wrapping_mul(10);
        kappa -= 1;

        let digit = part2 >> shift;
        if digit != 0 || idx != 0 {
            digits[idx] = b'0' + digit as u8;
            idx += 1;
        }

        part2 &= one_frac - 1;
        if part2 < delta {
            *k += kappa;
            round_digit(
                digits,
                idx,
                delta,
                part2,
                one_frac,
                wfrac.wrapping_mul(TENS[unit]),
            );
            return idx;
        }
        unit -= 1;
    }
}

/// The shortest-ish digits of `d` and the power of ten they sit at.
fn grisu2(d: f64, digits: &mut [u8; 18], k: &mut i32) -> usize {
    let mut w = build_fp(d);

    let mut lower = Fp { frac: 0, exp: 0 };
    let mut upper = Fp { frac: 0, exp: 0 };
    get_normalized_boundaries(&w, &mut lower, &mut upper);

    normalize(&mut w);

    let mut cached_k = 0;
    let cp = find_cachedpow10(upper.exp, &mut cached_k);

    w = multiply(&w, &cp);
    upper = multiply(&upper, &cp);
    lower = multiply(&lower, &cp);

    // Pull the boundaries in by one so a value sitting exactly on one of them
    // is not claimed by this double.
    lower.frac = lower.frac.wrapping_add(1);
    upper.frac = upper.frac.wrapping_sub(1);

    *k = -cached_k;

    generate_digits(&w, &upper, &lower, digits, k)
}

/// Lays the digits out, choosing between the plain and the exponent form.
///
/// This is the part a client sees. The plain integer form is used when the
/// value needs at most seven trailing zeros, the plain decimal form when it
/// needs at most six leading zeros or is close enough to one, and the exponent
/// form otherwise. Note that the exponent is written with a sign and with no
/// padding, so it is `1e+30` and `1e-7`, which is neither what `%g` writes nor
/// what Rust writes.
fn emit_digits(digits: &[u8; 18], ndigits: usize, dest: &mut [u8], k: i32, neg: bool) -> usize {
    let mut ndigits = ndigits;
    let mut exp = (k + ndigits as i32 - 1).abs();

    // Plain integer.
    if k >= 0 && exp < ndigits as i32 + 7 {
        let zeros = k as usize;
        dest[..ndigits].copy_from_slice(&digits[..ndigits]);
        dest[ndigits..ndigits + zeros].fill(b'0');
        return ndigits + zeros;
    }

    // Plain decimal.
    if k < 0 && (k > -7 || exp < 4) {
        let offset = ndigits as i32 - k.abs();
        if offset <= 0 {
            let lead = (-offset) as usize;
            dest[0] = b'0';
            dest[1] = b'.';
            dest[2..2 + lead].fill(b'0');
            dest[lead + 2..lead + 2 + ndigits].copy_from_slice(&digits[..ndigits]);
            return ndigits + 2 + lead;
        }
        let offset = offset as usize;
        dest[..offset].copy_from_slice(&digits[..offset]);
        dest[offset] = b'.';
        dest[offset + 1..ndigits + 1].copy_from_slice(&digits[offset..ndigits]);
        return ndigits + 1;
    }

    // Exponent form. The cap never bites, because the shortest digits of a
    // double are at most seventeen and this allows seventeen or eighteen, but
    // it is here because the original has it.
    ndigits = ndigits.min(18 - usize::from(neg));

    let mut idx = 0usize;
    dest[idx] = digits[0];
    idx += 1;

    if ndigits > 1 {
        dest[idx] = b'.';
        idx += 1;
        dest[idx..idx + ndigits - 1].copy_from_slice(&digits[1..ndigits]);
        idx += ndigits - 1;
    }

    dest[idx] = b'e';
    idx += 1;
    dest[idx] = if k + ndigits as i32 - 1 < 0 {
        b'-'
    } else {
        b'+'
    };
    idx += 1;

    let mut cent = 0;
    if exp > 99 {
        cent = exp / 100;
        dest[idx] = b'0' + cent as u8;
        idx += 1;
        exp -= cent * 100;
    }
    if exp > 9 {
        let dec = exp / 10;
        dest[idx] = b'0' + dec as u8;
        idx += 1;
        exp -= dec * 10;
    } else if cent != 0 {
        dest[idx] = b'0';
        idx += 1;
    }
    dest[idx] = b'0' + (exp % 10) as u8;
    idx + 1
}

/// Writes `d` into `dest` exactly as Redis's `fpconv_dtoa` would, and answers
/// how many bytes it wrote.
///
/// `dest` must be at least [`MAX`] long.
pub fn dtoa(d: f64, dest: &mut [u8]) -> usize {
    debug_assert!(dest.len() >= MAX);

    let mut len = 0usize;
    let neg = d.to_bits() & SIGNMASK != 0;
    if neg {
        dest[0] = b'-';
        len = 1;
    }

    // Zero, the infinities and NaN never reach the digit generator. The sign
    // has already been written, which is where `-0` and `-inf` come from.
    if d == 0.0 {
        dest[len] = b'0';
        return len + 1;
    }
    if d.is_nan() {
        dest[len..len + 3].copy_from_slice(b"nan");
        return len + 3;
    }
    if d.is_infinite() {
        dest[len..len + 3].copy_from_slice(b"inf");
        return len + 3;
    }

    let mut digits = [0u8; 18];
    let mut k = 0i32;
    let ndigits = grisu2(d, &mut digits, &mut k);

    len + emit_digits(&digits, ndigits, &mut dest[len..], k, neg)
}

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

    fn text(d: f64) -> String {
        let mut buf = [0u8; MAX];
        let n = dtoa(d, &mut buf);
        String::from_utf8(buf[..n].to_vec()).expect("digits are ascii")
    }

    #[test]
    fn the_two_plain_forms_cover_the_ordinary_range() {
        // The forms Redis uses for anything a client is likely to send.
        for (d, want) in [
            (0.0, "0"),
            (-0.0, "-0"),
            (1.0, "1"),
            (-1.0, "-1"),
            (0.5, "0.5"),
            (0.3, "0.3"),
            (-0.3, "-0.3"),
            (3.0e3, "3000"),
            (1.5, "1.5"),
            (1234.5678, "1234.5678"),
            (0.001234, "0.001234"),
            (core::f64::consts::PI, "3.141592653589793"),
            (0.0001, "0.0001"),
        ] {
            assert_eq!(text(d), want, "{d}");
        }
    }

    #[test]
    fn a_large_or_small_magnitude_switches_to_an_exponent() {
        // The whole reason this port exists: Rust writes every one of these
        // with all its zeros and Redis does not.
        for (d, want) in [
            // Note that this is the printer on its own. A whole number this
            // size never reaches it from `push_double`, because Redis takes the
            // integer path for anything up to two to the sixty second first.
            (1.0e15, "1e+15"),
            (1.0e30, "1e+30"),
            (-1.0e30, "-1e+30"),
            (1.0e-7, "1e-7"),
            (1.0e19, "1e+19"),
            (1.0e100, "1e+100"),
            (1.0e-100, "1e-100"),
            (5.0e-324, "5e-324"),
            (f64::MAX, "1.7976931348623157e+308"),
            (f64::MIN_POSITIVE, "2.2250738585072014e-308"),
            (1.2345678e-5, "1.2345678e-5"),
        ] {
            assert_eq!(text(d), want, "{d}");
        }
    }

    #[test]
    fn the_special_values_are_written_as_words() {
        assert_eq!(text(f64::INFINITY), "inf");
        assert_eq!(text(f64::NEG_INFINITY), "-inf");
        assert_eq!(text(f64::NAN), "nan");
        assert_eq!(text(-f64::NAN), "-nan");
    }

    #[test]
    fn everything_written_reads_back_as_the_same_double() {
        // Grisu2 is not always shortest, but it is always exact: whatever it
        // writes has to parse back to the bits it was handed. That is the
        // property worth checking over a lot of values, because a port that
        // dropped a digit somewhere would still look right on a hand table.
        let mut state = 0x2545_F491_4F6C_DD1Du64;
        let mut checked = 0u32;
        for _ in 0..200_000 {
            state ^= state << 13;
            state ^= state >> 7;
            state ^= state << 17;
            let d = f64::from_bits(state);
            if !d.is_finite() {
                continue;
            }
            let s = text(d);
            let back: f64 = s.parse().expect("what was written parses");
            assert_eq!(back.to_bits(), d.to_bits(), "{s}");
            checked += 1;
        }
        assert!(checked > 190_000, "only {checked} finite values");
    }

    #[test]
    fn nothing_written_needs_more_room_than_the_buffer() {
        let mut widest = 0usize;
        let mut state = 0x9E37_79B9_7F4A_7C15u64;
        for _ in 0..200_000 {
            state ^= state << 13;
            state ^= state >> 7;
            state ^= state << 17;
            let d = f64::from_bits(state);
            if !d.is_finite() {
                continue;
            }
            let mut buf = [0u8; MAX];
            widest = widest.max(dtoa(d, &mut buf));
        }
        // Both edges of the plain integer branch, which is the widest form.
        for d in [9.999999999999999e23, -9.999999999999999e23] {
            let mut buf = [0u8; MAX];
            widest = widest.max(dtoa(d, &mut buf));
        }
        assert!(widest <= MAX, "{widest} bytes needs more than {MAX}");
    }
}