yo_common/

num.rs

//! Numbers to text and back, written by hand.
//!
//! Every reply that carries a length or an integer goes through here, which is
//! every reply, so this is as hot as anything in the codec. The formatting
//! machinery in `core::fmt` would produce the same bytes and would be several
//! times slower for the two or three digits a bulk header usually needs, so it
//! is not used for integers.
//!
//! Parsing is deliberately strict and matches Redis's `string2ll` byte for
//! byte, including its refusal of leading zeros and of a leading `+`. The
//! protocol's own lengths are parsed with it, so a stricter or looser reading
//! here is a real difference in what the two servers accept.

use core::fmt::Write as _;

/// Every two digit pair, `00` through `99`, laid out end to end.
///
/// Two digits per pass rather than one halves the number of divisions, which is
/// the whole cost of this loop. Built at compile time rather than typed out,
/// because a two hundred character literal is a typo waiting to happen and the
/// compiler will do it for free.
const PAIRS: [u8; 200] = {
    let mut t = [0u8; 200];
    let mut i = 0;
    while i < 100 {
        t[i * 2] = b'0' + (i / 10) as u8;
        t[i * 2 + 1] = b'0' + (i % 10) as u8;
        i += 1;
    }
    t
};

/// The most digits a `u64` can have, which is what `18446744073709551615` needs.
const U64_DIGITS: usize = 20;

/// Appends the decimal digits of `n`.
///
/// The digits go into a fixed twenty byte buffer that is then copied whole,
/// with the length cut back afterwards to the digits that are actually there.
/// A copy of a length the compiler can see is a couple of stores it writes
/// inline; a copy of a length only known at run time is a call into the
/// platform's `memmove`, and getting into that call costs more than moving one
/// digit. It showed up as eleven percent of `SADD` on the wire, where the whole
/// reply is `:0`.
pub fn push_u64(out: &mut Vec<u8>, n: u64) {
    let len = u64_len(n);
    let mut buf = [0u8; U64_DIGITS];
    let mut i = len;
    let mut n = n;
    while n >= 100 {
        let p = ((n % 100) as usize) * 2;
        n /= 100;
        i -= 2;
        buf[i] = PAIRS[p];
        buf[i + 1] = PAIRS[p + 1];
    }
    if n >= 10 {
        let p = (n as usize) * 2;
        buf[0] = PAIRS[p];
        buf[1] = PAIRS[p + 1];
    } else {
        buf[0] = b'0' + n as u8;
    }
    let at = out.len();
    out.extend_from_slice(&buf);
    out.truncate(at + len);
}

/// Appends the decimal digits of `n`, with a minus sign if it needs one.
pub fn push_i64(out: &mut Vec<u8>, n: i64) {
    if n < 0 {
        out.push(b'-');
    }
    // `unsigned_abs` rather than `-n`, which overflows on `i64::MIN`.
    push_u64(out, n.unsigned_abs());
}

/// The number of bytes [`push_i64`] would append.
///
/// Used to presize a reply buffer before anything is written to it, which is
/// the whole point of Y18: the buffer is sized once from what is about to go
/// into it rather than grown while it is being filled.
pub const fn i64_len(n: i64) -> usize {
    (if n < 0 { 1 } else { 0 }) + u64_len(n.unsigned_abs())
}

/// How many digits `n` has.
///
/// `ilog10` and not a loop of divides, because this runs in front of every
/// integer reply to size the buffer and a divide by ten is twenty cycles the
/// hardware's leading zero count answers in one.
#[must_use]
pub const fn u64_len(n: u64) -> usize {
    match n.checked_ilog10() {
        Some(log) => log as usize + 1,
        // `ilog10` has no answer for zero, which still takes one digit to say.
        None => 1,
    }
}

/// A buffer big enough for the digits of any `i64` or `u64`, sign included.
///
/// Twenty digits for `18446744073709551615` and one more for the minus sign
/// that `-9223372036854775808` needs.
pub const DIGITS_MAX: usize = U64_DIGITS + 1;

/// The digits of `n`, written backwards into `buf`, and where they start.
///
/// One digit a pass rather than the two [`push_u64`] does, because these two
/// are not on the reply path and the pair table is only worth its branch when
/// it is.
fn fill_back(buf: &mut [u8; DIGITS_MAX], n: u64) -> usize {
    let mut at = DIGITS_MAX;
    let mut v = n;
    loop {
        at -= 1;
        buf[at] = b'0' + (v % 10) as u8;
        v /= 10;
        if v == 0 {
            return at;
        }
    }
}

/// The decimal digits of `n`, written into the back of `buf`.
///
/// The same answer [`push_i64`] gives, for a caller that has nowhere to put a
/// `Vec`. `SSCAN key 0 MATCH 1*` has to run a glob over a member that is stored
/// as a number and has no digits anywhere, and doing that through a `Vec` would
/// be an allocation per member on a thread that must not allocate.
pub fn i64_digits(buf: &mut [u8; DIGITS_MAX], n: i64) -> &[u8] {
    let mut at = fill_back(buf, n.unsigned_abs());
    if n < 0 {
        at -= 1;
        buf[at] = b'-';
    }
    &buf[at..]
}

/// The decimal digits of `n`, written into the back of `buf`.
///
/// The unsigned form, for the numbers that genuinely do not fit in an `i64`. A
/// scan cursor is one: ours packs a partition count into the top bits, so a
/// large enough collection hands the client a number with bit 63 set and
/// reporting it as a signed integer would report it as negative.
pub fn u64_digits(buf: &mut [u8; DIGITS_MAX], n: u64) -> &[u8] {
    let at = fill_back(buf, n);
    &buf[at..]
}

/// Parses a signed decimal integer the way Redis's `string2ll` does.
///
/// Returns `None` for anything it would reject, which includes an empty slice,
/// a leading `+`, a leading zero on a non zero number, any non digit anywhere,
/// and anything that does not fit in an `i64`. The protocol's array and bulk
/// lengths are parsed with this, so being looser here would mean accepting
/// frames that Redis rejects, and being stricter would mean the reverse.
pub fn parse_i64(s: &[u8]) -> Option<i64> {
    // The longest thing that can parse is `-9223372036854775808`, at twenty.
    if s.is_empty() || s.len() > 20 {
        return None;
    }
    let (negative, digits) = if s[0] == b'-' {
        (true, &s[1..])
    } else {
        (false, s)
    };
    if digits.is_empty() {
        return None;
    }
    // A leading zero is only ever a whole number zero, and only a positive one.
    // `007` is not seven here and it is not seven in Redis either, and `-0` is
    // not a number in either: `string2ll` tests its zero case against the length
    // of the whole string, so the minus sign puts `-0` past it and into the one
    // to nine gate, which it fails. That matters beyond parsing, because this is
    // also what decides whether a string is stored int encoded. Accepting `-0`
    // would store it as the integer zero, and `GET` would then hand the client
    // back `0` for a value it wrote as `-0`.
    if digits[0] == b'0' {
        return if digits.len() == 1 && !negative {
            Some(0)
        } else {
            None
        };
    }
    let mut v: u64 = 0;
    for &c in digits {
        if !c.is_ascii_digit() {
            return None;
        }
        v = v.checked_mul(10)?.checked_add(u64::from(c - b'0'))?;
    }
    if negative {
        // One more magnitude is available going negative, and `i64::MIN`
        // reached through `wrapping_neg` is the one value that cannot be
        // written as a positive `i64` first.
        if v > (i64::MAX as u64) + 1 {
            None
        } else {
            Some((v as i64).wrapping_neg())
        }
    } else if v > i64::MAX as u64 {
        None
    } else {
        Some(v as i64)
    }
}

/// The largest magnitude Redis's `double2ll` will turn into an integer.
///
/// `double2ll` refuses anything outside `LLONG_MAX / 2`, which as a double is
/// exactly two to the sixty second, and then checks that the value survives a
/// round trip through a `long long`. Everything inside that range and integral
/// is written with the integer printer rather than the digit generator, and
/// that decision is visible: at this magnitude the digit generator would switch
/// to an exponent.
const DOUBLE_INT_LIMIT: f64 = 4_611_686_018_427_387_904.0; // 2^62

/// Redis's `getLongDoubleFromObject`, as far as the difference is observable.
///
/// A float argument and a float value are parsed by the same rules, and the
/// rules are stricter than Rust's `str::parse`: no leading or trailing
/// whitespace at all, and `nan` is refused where the infinities are not. Redis
/// refuses NaN because every command that takes a float goes on to store the
/// result, and a stored NaN compares false against itself forever after.
///
/// This lives here for the same reason [`parse_i64`] does. It is not a codec
/// question, it is the same question the string type asks of a stored value,
/// and the storage layer cannot reach into the wire layer to ask it.
///
/// It also takes hexadecimal, because `strtold` does and Redis inherits every
/// bit of that. `INCRBYFLOAT` on a key holding `0x10` counts from sixteen on a
/// real server, and `INCRBYFLOAT key 0x10` adds sixteen. Nobody designed that
/// and it is unlikely anyone relies on it, but a client that sends it gets an
/// answer from Redis and an error from us, and telling a client its value is
/// not a valid float when the server next door accepts it is the kind of
/// difference that gets found in production rather than in a test.
pub fn parse_f64(s: &[u8]) -> Option<f64> {
    if s.is_empty() || s[0].is_ascii_whitespace() {
        return None;
    }
    let text = core::str::from_utf8(s).ok()?;
    if text.trim() != text {
        return None;
    }
    let v = if is_hex(text) {
        parse_hex_f64(text)?
    } else {
        text.parse().ok()?
    };
    if v.is_nan() { None } else { Some(v) }
}

/// Does this start the way a C hexadecimal float does?
///
/// Only the prefix is checked here. Whether the rest of it is a number at all
/// is [`parse_hex_f64`]'s problem, and a string that starts `0x` and continues
/// badly has to be refused rather than falling back to the decimal parser,
/// which would read `0xzz` as a plain zero.
fn is_hex(text: &str) -> bool {
    let body = text.strip_prefix(['+', '-']).unwrap_or(text).as_bytes();
    body.len() > 2 && body[0] == b'0' && (body[1] | 0x20) == b'x'
}

/// `0x1.8p1` and the rest of C's hexadecimal float syntax.
///
/// The binary exponent is optional, which it is not in a C source literal but
/// is in `strtod`, so `0x10` on its own is sixteen. The mantissa is gathered
/// into a `u64` until it is full and after that the digits only move the
/// exponent, which costs nothing anyone will see: sixteen hex digits is more
/// precision than a double has to give back.
fn parse_hex_f64(text: &str) -> Option<f64> {
    let (negative, rest) = match text.as_bytes()[0] {
        b'-' => (true, &text[1..]),
        b'+' => (false, &text[1..]),
        _ => (false, text),
    };
    let body = &rest[2..]; // `is_hex` already checked the `0x`.

    let mut mantissa: u64 = 0;
    let mut exponent: i32 = 0;
    let mut digits = 0usize;
    let mut seen_point = false;
    let mut at = 0usize;
    let bytes = body.as_bytes();

    while at < bytes.len() {
        let c = bytes[at];
        if c == b'.' {
            if seen_point {
                return None;
            }
            seen_point = true;
            at += 1;
            continue;
        }
        let Some(value) = (c as char).to_digit(16) else {
            break;
        };
        digits += 1;
        if mantissa <= u64::MAX >> 4 {
            mantissa = (mantissa << 4) | u64::from(value);
            if seen_point {
                exponent -= 4;
            }
        } else if !seen_point {
            // Past what a `u64` holds, a digit before the point is worth four
            // more binary places and nothing else.
            exponent += 4;
        }
        at += 1;
    }
    if digits == 0 {
        return None;
    }

    if at < bytes.len() {
        // A binary exponent, and it is the only thing allowed to be here.
        if (bytes[at] | 0x20) != b'p' {
            return None;
        }
        let written: i32 = rest[2 + at + 1..].parse().ok()?;
        exponent = exponent.checked_add(written)?;
    }

    let value = (mantissa as f64) * exp2(exponent);
    // An overflow to infinity is refused rather than stored. Redis refuses it
    // too, at a much higher ceiling, and that gap is in the divergence register
    // rather than pretended away here.
    if !value.is_finite() {
        return None;
    }
    Some(if negative { -value } else { value })
}

/// Two to the power of a whole number, without `std`.
///
/// `powi` is not in core, and the exponent can be far enough out that squaring
/// up from one would take a while, so this walks the bits. A power that is out
/// of range comes back as an infinity and the caller refuses it.
fn exp2(mut n: i32) -> f64 {
    let mut base = if n < 0 { 0.5 } else { 2.0 };
    n = n.abs();
    let mut out = 1.0f64;
    while n > 0 {
        if n & 1 == 1 {
            out *= base;
        }
        base *= base;
        n >>= 1;
    }
    out
}

/// Room for the longest thing [`write_double`] or [`write_g17`] can write.
///
/// Both of them are bounded by the same thing, a mantissa of seventeen digits
/// with a handful of zeros or a `.` and an exponent around it, and neither can
/// reach thirty two bytes. It is worth saying out loud that this used to be
/// three hundred and fifty two, because Rust's printer writes every leading
/// zero of a subnormal, and the port of Redis's own printer is what shrank it.
pub const DOUBLE_MAX: usize = 32;

const _: () = assert!(DOUBLE_MAX >= crate::dtoa::MAX);

/// Appends a double the way Redis 8 writes one.
///
/// This is `d2string`. Redis stopped using `%.17g` in 7.0 and now writes a
/// double in two cases: a value that is exactly an integer inside two to the
/// sixty second is written with the integer printer, and everything else goes
/// through the Grisu2 in [`crate::dtoa`]. Zero is checked before either of
/// them, which is the only reason negative zero comes back as `-0` rather than
/// as `0`.
///
/// The infinities and NaN are written as bare words because that is what RESP3
/// says and what RESP2 clients have always been given.
pub fn push_double(out: &mut Vec<u8>, d: f64) {
    let mut buf = [0u8; DOUBLE_MAX];
    out.extend_from_slice(write_double(&mut buf, d));
}

/// Appends a double the way `INCRBYFLOAT` and `HINCRBYFLOAT` write one, which
/// is not the way everything else does.
///
/// Those two go through `ld2string` in its human mode rather than through
/// `d2string`, and the human mode is `%.17Lf` with the trailing zeros taken off
/// and a lone `-0` turned back into `0`. Being a fixed point conversion it never
/// writes an exponent, so `INCRBYFLOAT key 1e30` answers a one and thirty zeros
/// where `ZSCORE` would answer `1e+30` for the same number.
///
/// The digits are the shortest ones rather than seventeen decimal places of the
/// `f64`, and that is the closer answer rather than the lazier one. Redis holds
/// the value in a long double, so `%.17Lf` of one tenth is `0.10000000000000000`
/// and comes back as `0.1` once the zeros are stripped. Seventeen decimal places
/// of the `f64` would be `0.10000000000000001`, which is a worse match for the
/// same reason D-11 gives: the extra width is what makes the long double print
/// cleanly, and shortest digits land on the same text without pretending to have
/// it.
pub fn push_human(out: &mut Vec<u8>, d: f64) {
    if d.is_nan() {
        out.extend_from_slice(b"nan");
        return;
    }
    if d.is_infinite() {
        out.extend_from_slice(if d > 0.0 { b"inf" } else { b"-inf" });
        return;
    }
    // Negative zero loses its sign here, which is the one thing the human mode
    // says out loud and `d2string` does the other way round.
    if d.fract() == 0.0 && d.abs() <= DOUBLE_INT_LIMIT {
        push_i64(out, d as i64);
        return;
    }
    // Writing through the sink puts the digits straight into the reply buffer.
    // `format!` would produce the same bytes and one throwaway allocation, and
    // a shard thread that allocates aborts.
    let mut sink = Utf8Sink(out);
    let _ = write!(sink, "{d}");
}

/// Appends a distance the way the geo commands write one, which is four digits
/// after the point and no exponent ever.
///
/// `GEODIST` and the `WITHDIST` half of a search go through Redis's
/// `fixedpoint_d2string` rather than through `d2string`, because "166.2742 km
/// away" reads better than "166.27415156960033 km away" and four places is
/// still a tenth of a metre when the unit is the kilometre. The trailing zeros
/// stay, so a whole number of metres comes back as `5.0000` and a distance of
/// nothing comes back as `0.0000`.
///
/// The scaled value is rounded to the nearest, ties to even, which is what
/// `llrint` does in the default rounding mode and therefore what a real server
/// answers. Ties are not reachable in practice, since the value being rounded
/// came out of a square root, but rounding the other way would still be a
/// divergence that only showed up in somebody's test suite.
///
/// A distance too large to scale into an integer writes nothing, which is what
/// Redis does too: its formatter fails and hands the reply an empty string.
/// Nothing reaches that from a real search, because the far side of the world
/// is twenty thousand kilometres away and the scaled form of that is twelve
/// digits.
pub fn push_fixed4(out: &mut Vec<u8>, d: f64) {
    let scaled = (d * 10_000.0).round_ties_even();
    if !scaled.is_finite() || scaled.abs() >= DOUBLE_INT_LIMIT {
        return;
    }
    let mut whole = scaled as i64;
    if whole < 0 {
        out.push(b'-');
        whole = -whole;
    }
    let mut buf = [0u8; DIGITS_MAX];
    let digits = u64_digits(&mut buf, whole as u64);
    // Four digits or fewer means there is no integer part, and Redis writes a
    // zero in front rather than leaving a reply that starts with a point. The
    // padding is what is left of the four places once the digits are in.
    if let Some(padding) = 4usize.checked_sub(digits.len()) {
        out.extend_from_slice(b"0.");
        out.extend_from_slice(&b"0000"[..padding]);
        out.extend_from_slice(digits);
    } else {
        let (front, back) = digits.split_at(digits.len() - 4);
        out.extend_from_slice(front);
        out.push(b'.');
        out.extend_from_slice(back);
    }
}

/// Writes a double into a fixed buffer, byte for byte what [`push_double`]
/// would append.
///
/// The two are the same code now, and this is the one that does the work,
/// because the digit generator wants somewhere to put eighteen digits before it
/// knows how many of them it is going to keep. The caller that needs it as a
/// buffer rather than as a reply is the array type, which stores a value as a
/// double only when the double prints back as the exact bytes the client sent,
/// so it formats a candidate, compares, and usually throws it away.
pub fn write_double(buf: &mut [u8; DOUBLE_MAX], d: f64) -> &[u8] {
    // Zero first, so that the sign of a negative zero survives. The integer
    // path below would lose it and Redis checks in this order for that reason.
    if d == 0.0 {
        let n = if d.is_sign_negative() {
            buf[..2].copy_from_slice(b"-0");
            2
        } else {
            buf[0] = b'0';
            1
        };
        return &buf[..n];
    }
    if d.is_nan() {
        buf[..3].copy_from_slice(b"nan");
        return &buf[..3];
    }
    if d.is_infinite() {
        let text: &[u8] = if d > 0.0 { b"inf" } else { b"-inf" };
        buf[..text.len()].copy_from_slice(text);
        return &buf[..text.len()];
    }
    if d.fract() == 0.0 && d.abs() <= DOUBLE_INT_LIMIT {
        let mut digits = [0u8; DIGITS_MAX];
        let text = i64_digits(&mut digits, d as i64);
        let n = text.len();
        buf[..n].copy_from_slice(text);
        return &buf[..n];
    }
    let n = crate::dtoa::dtoa(d, buf);
    &buf[..n]
}

/// Writes a double the way C's `%.17g` writes one, which is what `AROP`
/// replies with.
///
/// Redis formats an aggregate through `ld2string` in its automatic mode, and
/// that mode is a plain `%.17Lg`, so this is the one reply in the whole server
/// that is not a shortest round trip printer. The difference is visible: three
/// tenths comes back as `0.29999999999999999` here and as `0.3` from `ZSCORE`,
/// because seventeen significant digits of the nearest double to three tenths
/// really are those.
///
/// `%g` picks between the two forms the way C says: the exponent form when the
/// decimal exponent is below minus four or at least the precision, the plain
/// form otherwise, and trailing zeros come off either way.
pub fn write_g17(buf: &mut [u8; DOUBLE_MAX], d: f64) -> &[u8] {
    /// Seventeen significant digits is sixteen after the point.
    const AFTER: usize = 16;
    if d.is_nan() {
        buf[..3].copy_from_slice(b"nan");
        return &buf[..3];
    }
    if d.is_infinite() {
        let word: &[u8] = if d > 0.0 { b"inf" } else { b"-inf" };
        buf[..word.len()].copy_from_slice(word);
        return &buf[..word.len()];
    }
    // The exponent C would use is the one the value has after it has been
    // rounded to seventeen digits, so it has to come from the rounding and not
    // from a logarithm: 9.9999999999999999e-5 rounds up into the next decade.
    let mut scratch = [0u8; DOUBLE_MAX];
    let mut sink = SliceSink {
        buf: &mut scratch,
        at: 0,
    };
    let _ = write!(sink, "{d:.AFTER$e}");
    let end = sink.at;
    let split = scratch[..end]
        .iter()
        .position(|&c| c == b'e')
        .expect("the exponent form always has one");
    let exp = parse_i64(&scratch[split + 1..end]).expect("a written exponent parses") as i32;

    if !(-4..17).contains(&exp) {
        // The exponent form, and C writes at least two exponent digits where
        // Rust writes as few as one.
        let mantissa = trim_zeros(&scratch[..split]);
        let n = mantissa.len();
        buf[..n].copy_from_slice(mantissa);
        let mut sink = SliceSink { buf, at: n };
        let sign = if exp < 0 { '-' } else { '+' };
        let _ = write!(sink, "e{sign}{:02}", exp.unsigned_abs());
        let at = sink.at;
        return &buf[..at];
    }
    // The plain form, whose precision is what is left of the seventeen digits
    // once the integer part has had its share.
    let places = usize::try_from(AFTER as i32 - exp).unwrap_or(0);
    let mut sink = SliceSink { buf, at: 0 };
    let _ = write!(sink, "{d:.places$}");
    let at = sink.at;
    let n = trim_zeros(&buf[..at]).len();
    &buf[..n]
}

/// The same digits [`write_g17`] would write, appended.
pub fn push_g17(out: &mut Vec<u8>, d: f64) {
    let mut buf = [0u8; DOUBLE_MAX];
    out.extend_from_slice(write_g17(&mut buf, d));
}

/// Writes a double the way the time series module writes a sample value on
/// RESP2, which is neither of the two printers above.
///
/// The module hands the value to a vendored Dragonbox and replies with the
/// characters that come back, so a sample reads as `1.5` but a tenth reads as
/// `1E-1` and ten million reads as `10000000`. Deciding which of the two forms
/// a value takes is the whole problem, because Dragonbox makes that decision
/// on a decimal it has not finished shortening, and the caller never sees that
/// intermediate. Its printer takes the plain form when the exponent of that
/// unshortened decimal is in `-16 ..= 0` and the value has an integer part,
/// and the exponent form otherwise.
///
/// The unshortened exponent can be recovered from the shortest one. Dragonbox
/// returns one of two adjacent exponents, `floor(e2 * log10(2))` and one above
/// it, where `e2` is the binary exponent of the significand read as an
/// integer, so the exponent it used is the shortest value's own exponent
/// capped at the upper of that pair. A value whose significand bits are all
/// zero sits on a shorter rounding interval and its pair starts at
/// `floor(e2 * log10(2) - log10(4 / 3))` instead. Both logarithms are the
/// usual integer approximations, exact for every binary exponent a double has.
///
/// Verified against the module's own Dragonbox over seven and a half million
/// doubles, random bit patterns, every awkward decade and boundary, and every
/// one of the 2045 powers of two, with no difference.
pub fn write_dragonbox(buf: &mut [u8; DOUBLE_MAX], d: f64) -> &[u8] {
    fn word<'a>(buf: &'a mut [u8; DOUBLE_MAX], text: &[u8]) -> &'a [u8] {
        buf[..text.len()].copy_from_slice(text);
        &buf[..text.len()]
    }
    if d.is_nan() {
        return word(buf, b"NaN");
    }
    if d.is_infinite() {
        return word(buf, if d > 0.0 { b"Infinity" } else { b"-Infinity" });
    }
    if d == 0.0 {
        return word(buf, if d.is_sign_negative() { b"-0" } else { b"0" });
    }
    // The shortest round trip decimal, as a digit count and the exponent its
    // first digit carries. A one digit shortest form can round up across a
    // power of ten, so a magnitude that reads as a `1` is asked again at a
    // width no rounding can carry.
    let mut scratch = [0u8; DOUBLE_MAX];
    let (mut exp, count) = exponent_and_digits(&mut scratch, d.abs(), None);
    let mut magnitude = exp;
    if count == 1 {
        magnitude = exponent_and_digits(&mut scratch, d.abs(), Some(17)).0;
    }

    // Where Dragonbox would have stopped, which is the shortest value's own
    // exponent unless the pair it chooses from stops it earlier.
    let bits = d.abs().to_bits();
    let raised = (bits >> 52) as i32;
    let fraction = bits & ((1 << 52) - 1);
    let e2 = if raised == 0 { -1074 } else { raised - 1075 };
    let shorter = fraction == 0 && raised > 1;
    let base = if shorter {
        ((i64::from(e2) * 631_305 - 261_663) >> 21) as i32
    } else {
        ((i64::from(e2) * 315_653) >> 20) as i32
    };
    let unshortened = (exp - count as i32 + 1).min(base + 1);

    // The digits Dragonbox prints are the value rounded at that exponent,
    // which is not the same as the shortest digits. The two differ when the
    // value sits exactly between two decimals of that width, where Dragonbox
    // rounds to even and a shortest printer rounds away, and they differ by
    // the zeros that padding a short value out to that width leaves behind.
    // Rounding can carry into another digit, which moves the exponent.
    let places = usize::try_from(magnitude - unshortened)
        .unwrap_or(0)
        .min(17);
    let (carried, mut count) = if shorter {
        round_shorter(&mut scratch, d.abs(), places, e2)
    } else {
        exponent_and_digits(&mut scratch, d.abs(), Some(places))
    };
    exp = carried;
    while count > 1 && scratch[count - 1] == b'0' {
        count -= 1;
    }
    let digits = &scratch[..count];

    let mut sink = SliceSink { buf, at: 0 };
    if d.is_sign_negative() {
        let _ = sink.write_str("-");
    }
    if exp >= 0 && (-16..=0).contains(&unshortened) {
        // The plain form. An exponent at least the digit count means the point
        // would fall past the end, so the tail is zeros and there is no point.
        let whole = (exp + 1) as usize;
        let _ = sink.write_str(str::from_utf8(&digits[..whole.min(count)]).expect("digits"));
        for _ in count..whole {
            let _ = sink.write_str("0");
        }
        if whole < count {
            let _ = sink.write_str(".");
            let _ = sink.write_str(str::from_utf8(&digits[whole..]).expect("digits"));
        }
    } else {
        let _ = sink.write_str(str::from_utf8(&digits[..1]).expect("digits"));
        if count > 1 {
            let _ = sink.write_str(".");
            let _ = sink.write_str(str::from_utf8(&digits[1..]).expect("digits"));
        }
        let _ = write!(sink, "E{exp}");
    }
    let at = sink.at;
    &buf[..at]
}

/// Fills `digits` with the decimal digits of `d`, no point among them, and
/// answers the exponent the first of them carries and how many there are.
///
/// With no `places` the digits are the shortest ones that read back as `d`,
/// and with some they are `d` rounded to that many places after the first,
/// which is a rounding to even. Rounding can carry, `9.99` at one place is
/// `1.0e1`, so the exponent that comes back is the rounded value's own.
fn exponent_and_digits(digits: &mut [u8], d: f64, places: Option<usize>) -> (i32, usize) {
    let mut text = [0u8; WIDE_MAX];
    let mut sink = SliceSink {
        buf: &mut text,
        at: 0,
    };
    let _ = match places {
        Some(places) => write!(sink, "{d:.places$e}"),
        None => write!(sink, "{d:e}"),
    };
    let end = sink.at;
    let split = text[..end]
        .iter()
        .position(|&c| c == b'e')
        .expect("the exponent form always has one");
    let exp = parse_i64(&text[split + 1..end]).expect("a written exponent parses") as i32;
    let mut count = 0;
    for &c in &text[..split] {
        if c != b'.' {
            digits[count] = c;
            count += 1;
        }
    }
    (exp, count)
}

/// Room for the widest thing [`exponent_and_digits`] is asked to write.
const WIDE_MAX: usize = 48;

/// How many digits past the ones it answers [`round_shorter`] looks at.
///
/// The two comparisons it makes are decided by six figures at worst, measured
/// over every value that reaches it, so eight is enough with room to spare and
/// keeps the whole thing inside a `u64` of digits.
const EXTRA: usize = 8;

/// Ten to the [`EXTRA`], as the divisor that turns those digits into a fraction.
const EXTRA_SCALE: f64 = 100_000_000.0;

/// The one binary exponent where Dragonbox breaks a tie to even.
///
/// Its shorter interval case rounds a half away from zero everywhere else, and
/// only inside a band of binary exponents does it fall back to the tie rule the
/// caller asked for. For a double that band is a single exponent, and the only
/// two values that land on an exact half are this one and the one above it, so
/// the whole of the rule is: `2^-25` rounds to even and `2^-24` rounds up.
const TIE_TO_EVEN: i32 = -77;

/// Fills `digits` the way [`exponent_and_digits`] does, for a value whose
/// significand bits are all zero.
///
/// A power of two sits on a rounding interval that is not centred on it,
/// because the gap below is half the gap above, and Dragonbox answers the
/// nearest decimal inside that interval rather than the nearest decimal full
/// stop. The two differ when rounding down would land below the interval, which
/// is a quarter of a gap under the value, so the digits go up whenever what is
/// left over is more than a fifty four bit relative step. That is the whole
/// difference from the ordinary case, along with a half rounding away from zero
/// rather than to even.
///
/// Verified against the module's own Dragonbox over all 2045 values that reach
/// here, which is every power of two a double has.
fn round_shorter(digits: &mut [u8], d: f64, places: usize, e2: i32) -> (i32, usize) {
    let mut wide = [0u8; WIDE_MAX];
    let (mut exp, count) = exponent_and_digits(&mut wide, d, Some(places + EXTRA));
    let keep = count - EXTRA;
    let mut whole = 0.0;
    for &c in &wide[..keep] {
        whole = whole * 10.0 + f64::from(c - b'0');
    }
    let mut left = 0.0;
    for &c in &wide[keep..count] {
        left = left * 10.0 + f64::from(c - b'0');
    }
    left /= EXTRA_SCALE;

    // A half is a half whichever way it was reached, and nothing else this
    // rounding ever sees comes within a thousandth of one.
    let up = if (left - 0.5).abs() < 1e-6 {
        e2 != TIE_TO_EVEN || wide[keep - 1] % 2 == 1
    } else {
        // Either past the halfway point, or short of it but still under the
        // bottom of the interval, which sits a fifty four bit step below.
        left > 0.5 || left > whole / 18_014_398_509_481_984.0
    };

    digits[..keep].copy_from_slice(&wide[..keep]);
    if up {
        let mut at = keep;
        while at > 0 {
            at -= 1;
            if digits[at] == b'9' {
                digits[at] = b'0';
            } else {
                digits[at] += 1;
                break;
            }
        }
        // Every digit was a nine, so the answer is a one and a row of zeros
        // that is one digit wider, which at a fixed width is a larger exponent.
        if digits[0] == b'0' {
            digits[0] = b'1';
            exp += 1;
        }
    }
    (exp, keep)
}

/// The same characters [`write_dragonbox`] would write, appended.
pub fn push_dragonbox(out: &mut Vec<u8>, d: f64) {
    let mut buf = [0u8; DOUBLE_MAX];
    out.extend_from_slice(write_dragonbox(&mut buf, d));
}

/// Takes the trailing zeros off a fixed point number, and the point with them
/// when nothing is left after it.
///
/// A number with no point in it is left alone, because the zeros in `1700` are
/// not trailing anything.
fn trim_zeros(text: &[u8]) -> &[u8] {
    if !text.contains(&b'.') {
        return text;
    }
    let end = text.iter().rposition(|&c| c != b'0').unwrap_or(0);
    if text[end] == b'.' {
        &text[..end]
    } else {
        &text[..=end]
    }
}

/// A `core::fmt::Write` that fills a fixed buffer and stops when it is full.
///
/// Running out of room cannot happen here, because [`DOUBLE_MAX`] is sized for
/// the widest double there is, and it is handled rather than asserted so that a
/// mistake in that reasoning truncates a number instead of killing a shard.
struct SliceSink<'a> {
    buf: &'a mut [u8],
    at: usize,
}

impl core::fmt::Write for SliceSink<'_> {
    fn write_str(&mut self, s: &str) -> core::fmt::Result {
        let n = s.len().min(self.buf.len() - self.at);
        self.buf[self.at..self.at + n].copy_from_slice(&s.as_bytes()[..n]);
        self.at += n;
        Ok(())
    }
}

/// A `core::fmt::Write` that appends UTF-8 to a byte buffer.
///
/// The float printer only speaks `fmt::Write` and the reply buffer is bytes.
/// This is the whole adapter, and it exists so that no reply path anywhere ever
/// builds a `String` it immediately throws away.
struct Utf8Sink<'a>(&'a mut Vec<u8>);

impl core::fmt::Write for Utf8Sink<'_> {
    fn write_str(&mut self, s: &str) -> core::fmt::Result {
        self.0.extend_from_slice(s.as_bytes());
        Ok(())
    }
}

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

    fn text(n: i64) -> String {
        let mut v = Vec::new();
        push_i64(&mut v, n);
        String::from_utf8(v).unwrap()
    }

    #[test]
    fn integers_round_trip_through_text() {
        for n in [
            0,
            1,
            9,
            10,
            99,
            100,
            -1,
            -9,
            -10,
            12345,
            -12345,
            i64::MAX,
            i64::MIN,
        ] {
            assert_eq!(text(n), n.to_string(), "writing {n}");
            assert_eq!(parse_i64(text(n).as_bytes()), Some(n), "reading {n}");
        }
    }

    #[test]
    fn the_length_is_known_before_the_digits_are_written() {
        for n in [0, 5, 42, -42, 999, 1000, i64::MAX, i64::MIN] {
            assert_eq!(i64_len(n), text(n).len(), "length of {n}");
        }
    }

    /// Every boundary of the two digit loop, since an off by one there is a
    /// wrong length header rather than a crash and would be found by a client.
    #[test]
    fn every_length_of_number_is_written_correctly() {
        let mut n: u64 = 0;
        for _ in 0..20 {
            for probe in [n, n + 1, n.saturating_sub(1)] {
                let mut v = Vec::new();
                push_u64(&mut v, probe);
                assert_eq!(v, probe.to_string().as_bytes(), "writing {probe}");
            }
            n = n.saturating_mul(10).max(9);
            if n == u64::MAX {
                break;
            }
        }
    }

    #[test]
    fn the_stack_form_writes_what_the_vec_form_writes() {
        // Two implementations of the same digits is the shape of bug that only
        // shows at one boundary, so this checks them against each other rather
        // than against a literal.
        let mut buf = [0u8; DIGITS_MAX];
        let mut n: i64 = 0;
        for _ in 0..19 {
            for probe in [n, -n, n + 1, n - 1] {
                assert_eq!(i64_digits(&mut buf, probe), text(probe).as_bytes());
            }
            n = n.saturating_mul(10).max(9);
        }
        assert_eq!(i64_digits(&mut buf, i64::MIN), text(i64::MIN).as_bytes());
        assert_eq!(i64_digits(&mut buf, i64::MAX), text(i64::MAX).as_bytes());
        assert_eq!(i64_digits(&mut buf, 0), b"0", "and zero is one digit");

        // And the unsigned form past where the signed one stops, which is the
        // whole reason it is there.
        for probe in [0, 1, u64::MAX, 1 << 63, i64::MAX as u64 + 1] {
            let mut v = Vec::new();
            push_u64(&mut v, probe);
            assert_eq!(u64_digits(&mut buf, probe), v.as_slice(), "{probe}");
        }
    }

    #[test]
    fn the_parser_refuses_what_redis_refuses() {
        for bad in [
            &b""[..],
            b"-",
            b"+1",
            b"01",
            b"-01",
            b" 1",
            b"1 ",
            b"1a",
            b"a",
            b"1.0",
            b"-0",
            b"-00",
            b"9223372036854775808",
            b"-9223372036854775809",
            b"99999999999999999999999",
        ] {
            assert_eq!(parse_i64(bad), None, "{:?} should not parse", bad);
        }
        // The one leading zero that is a number, and the one negative that only
        // exists going downwards.
        assert_eq!(parse_i64(b"0"), Some(0));
        assert_eq!(parse_i64(b"-9223372036854775808"), Some(i64::MIN));
    }

    #[test]
    fn the_float_parser_refuses_what_redis_refuses() {
        assert_eq!(parse_f64(b"3.5"), Some(3.5));
        assert_eq!(parse_f64(b"-0"), Some(-0.0));
        assert_eq!(parse_f64(b"3.0e3"), Some(3000.0));
        assert_eq!(parse_f64(b"inf"), Some(f64::INFINITY));
        assert_eq!(parse_f64(b"-inf"), Some(f64::NEG_INFINITY));
        // No whitespace anywhere, nothing trailing, and no NaN, because a
        // stored NaN compares false against itself for the rest of time.
        assert_eq!(parse_f64(b" 3.5"), None);
        assert_eq!(parse_f64(b"3.5 "), None);
        assert_eq!(parse_f64(b"3.5x"), None);
        assert_eq!(parse_f64(b""), None);
        assert_eq!(parse_f64(b"nan"), None);
    }

    #[test]
    fn the_float_parser_takes_hexadecimal_because_strtold_does() {
        // Every one of these was read off a real 8.10.1 before it was written
        // down here.
        assert_eq!(parse_f64(b"0x10"), Some(16.0));
        assert_eq!(parse_f64(b"0X10"), Some(16.0));
        assert_eq!(parse_f64(b"0X1p4"), Some(16.0));
        assert_eq!(parse_f64(b"0x1.8p1"), Some(3.0));
        assert_eq!(parse_f64(b"-0x1.8p1"), Some(-3.0));
        assert_eq!(parse_f64(b"+0x10"), Some(16.0));
        assert_eq!(parse_f64(b"0x1p-1"), Some(0.5));
        assert_eq!(parse_f64(b"0xff"), Some(255.0));

        // A string that starts like a hexadecimal number and then stops being
        // one is refused rather than falling through to the decimal parser,
        // which would read the leading zero and call it a day.
        assert_eq!(parse_f64(b"0x"), None);
        assert_eq!(parse_f64(b"0xzz"), None);
        assert_eq!(parse_f64(b"0x1p"), None);
        assert_eq!(parse_f64(b"0x1.2.3"), None);
        assert_eq!(parse_f64(b"0x10x"), None);
        assert_eq!(parse_f64(b"0x1p99999"), None);
    }

    #[test]
    fn a_mantissa_longer_than_a_double_still_lands_in_the_right_place() {
        // Seventeen hex digits, one more than a u64 holds. The digits past the
        // end are worth four binary places each and nothing else, which is all
        // a double can use them for anyway.
        assert_eq!(
            parse_f64(b"0x10000000000000000"),
            Some(18446744073709551616.0)
        );
        assert_eq!(parse_f64(b"0x1p1024"), None);
    }

    #[test]
    fn doubles_are_written_the_way_redis_writes_them() {
        let cases: &[(f64, &str)] = &[
            (0.0, "0"),
            // Redis checks for zero before it checks for an integer, so this
            // keeps its sign where the integer printer would have dropped it.
            (-0.0, "-0"),
            (3.0, "3"),
            (-3.0, "-3"),
            (3.5, "3.5"),
            (0.1, "0.1"),
            // The integer printer reaches two to the sixty second, and past it
            // the digit generator takes over and switches to an exponent.
            (4.611686018427388e18, "4611686018427387904"),
            (1e19, "1e+19"),
            (1e30, "1e+30"),
            (1e-7, "1e-7"),
            (1e-6, "0.000001"),
            (5e-324, "5e-324"),
            (f64::INFINITY, "inf"),
            (f64::NEG_INFINITY, "-inf"),
            (f64::NAN, "nan"),
        ];
        for &(d, want) in cases {
            let mut v = Vec::new();
            push_double(&mut v, d);
            assert_eq!(String::from_utf8(v).unwrap(), want, "writing {d}");
        }
    }

    /// The human printer is the other one, and the difference is the exponent.
    ///
    /// `INCRBYFLOAT` and `HINCRBYFLOAT` are the only two commands that use it,
    /// and the reason it exists as a separate thing is the last four rows: a
    /// fixed point conversion has no exponent form to switch to, so a magnitude
    /// that comes back as `1e+30` from a score comes back written out in full
    /// from an increment.
    #[test]
    fn the_increment_printer_never_writes_an_exponent() {
        let cases: &[(f64, &str)] = &[
            (0.0, "0"),
            // The human mode says so explicitly, where `d2string` keeps it.
            (-0.0, "0"),
            (3.0, "3"),
            (3.5, "3.5"),
            (0.1, "0.1"),
            (10.5, "10.5"),
            (0.30000000000000004, "0.30000000000000004"),
            (1e30, "1000000000000000000000000000000"),
            (1e19, "10000000000000000000"),
            (1e-7, "0.0000001"),
            (f64::INFINITY, "inf"),
            (f64::NEG_INFINITY, "-inf"),
            (f64::NAN, "nan"),
        ];
        for &(d, want) in cases {
            let mut v = Vec::new();
            push_human(&mut v, d);
            assert_eq!(String::from_utf8(v).unwrap(), want, "writing {d}");
        }
        // The smallest subnormal, which is where the lack of an exponent form
        // costs the most: `0.` and then three hundred and twenty four places.
        let mut v = Vec::new();
        push_human(&mut v, 5e-324);
        assert_eq!(v.len(), 326);
        assert!(v.starts_with(b"0.0") && v.ends_with(b"5"));
    }

    #[test]
    fn a_distance_always_has_four_places_after_the_point() {
        let cases: &[(f64, &str)] = &[
            // Every one of these came off a running 8.10.1, through GEODIST and
            // through WITHDIST, in all four units.
            (0.0, "0.0000"),
            (-0.0, "0.0000"),
            (166_274.151_561_39, "166274.1516"),
            (166.274_151_561_39, "166.2742"),
            (103.318_154_263_49, "103.3182"),
            (545_518.869_950_1, "545518.8700"),
            (5.0, "5.0000"),
            // Under one, where the integer part is a zero that is written rather
            // than counted, and under a ten thousandth, where every digit of the
            // answer is a leading zero.
            (0.5, "0.5000"),
            (0.05, "0.0500"),
            (0.005, "0.0050"),
            (0.0005, "0.0005"),
            (0.000_04, "0.0000"),
            // The tie goes to the even digit, which is what llrint does.
            (0.000_25, "0.0002"),
            (0.000_35, "0.0004"),
            (-1.5, "-1.5000"),
        ];
        for &(d, want) in cases {
            let mut v = Vec::new();
            push_fixed4(&mut v, d);
            assert_eq!(String::from_utf8(v).unwrap(), want, "writing {d}");
        }
        // Nothing at all for the values a real server's formatter refuses,
        // which no search can produce and a client can still ask for.
        for d in [f64::INFINITY, f64::NAN, 1e30] {
            let mut v = Vec::new();
            push_fixed4(&mut v, d);
            assert!(v.is_empty(), "writing {d}");
        }
    }

    /// The two double writers have to agree, because one is used to predict the
    /// other.
    ///
    /// The array type decides whether a value can be stored as a double by
    /// formatting it with `write_double` and checking the bytes against what the
    /// client sent, and then the reply comes out of `push_double`. If they ever
    /// disagreed, a value would go in as a number and come back out as
    /// different text.
    #[test]
    fn the_two_double_writers_agree() {
        let mut cases = vec![
            0.0,
            -0.0,
            1.0,
            -1.0,
            3.5,
            0.1,
            -0.1,
            1e-320,
            f64::MIN_POSITIVE,
            f64::MAX,
            f64::MIN,
            DOUBLE_INT_LIMIT,
            -DOUBLE_INT_LIMIT,
            DOUBLE_INT_LIMIT + 2.0,
            f64::INFINITY,
            f64::NEG_INFINITY,
            f64::NAN,
        ];
        // A spread of ordinary values, so the agreement is not only about the
        // corners that were thought of in advance.
        for i in -400..400 {
            cases.push(f64::from(i) / 7.0);
            cases.push(f64::from(i) * 1e12);
        }
        for d in cases {
            let mut v = Vec::new();
            push_double(&mut v, d);
            let mut buf = [0u8; DOUBLE_MAX];
            assert_eq!(write_double(&mut buf, d), &v[..], "writing {d}");
        }
    }

    /// The fixed buffer is big enough for the widest double there is.
    ///
    /// `write_double` truncates rather than panicking if it is not, so a bad
    /// constant would show up as a wrong answer somewhere far away instead of
    /// here.
    #[test]
    fn the_fixed_buffer_holds_the_widest_double() {
        let mut widest = 0;
        for d in [f64::MIN, f64::MAX, f64::from_bits(1), -f64::from_bits(1)] {
            let mut v = Vec::new();
            push_double(&mut v, d);
            widest = widest.max(v.len());
        }
        assert!(widest <= DOUBLE_MAX, "{widest} bytes needs more than room");
    }

    /// Seventeen significant digits, the two forms, and the trailing zeros off
    /// both of them.
    ///
    /// The expected bytes here are what C's `%.17g` prints, which is what Redis
    /// replies to `AROP` with, and it is not what the rest of the server writes
    /// for a double: three tenths is `0.29999999999999999` in this printer and
    /// `0.3` in the other one.
    #[test]
    fn the_aggregate_printer_writes_seventeen_significant_digits() {
        let cases: &[(f64, &str)] = &[
            (0.0, "0"),
            (-0.0, "-0"),
            (1.0, "1"),
            (-1.0, "-1"),
            (0.5, "0.5"),
            (0.1, "0.10000000000000001"),
            (0.3, "0.29999999999999999"),
            (0.1 + 0.2, "0.30000000000000004"),
            (1.0 / 3.0, "0.33333333333333331"),
            (0.0001, "0.0001"),
            // Below a ten thousandth is where the exponent form starts, and C
            // writes two exponent digits where Rust would write one.
            (1.5e-5, "1.5e-05"),
            (1e-5, "1.0000000000000001e-05"),
            (1e16, "10000000000000000"),
            // And it starts again once the digits run out at seventeen.
            (1e17, "1e+17"),
            (1e30, "1e+30"),
            (-1e30, "-1e+30"),
            (1e100, "1e+100"),
            (f64::MAX, "1.7976931348623157e+308"),
            (f64::from_bits(1), "4.9406564584124654e-324"),
            (12345678901234567.0, "12345678901234568"),
            (f64::INFINITY, "inf"),
            (f64::NEG_INFINITY, "-inf"),
            (f64::NAN, "nan"),
        ];
        for &(d, want) in cases {
            let mut buf = [0u8; DOUBLE_MAX];
            assert_eq!(
                core::str::from_utf8(write_g17(&mut buf, d)).unwrap(),
                want,
                "writing {d}"
            );
            let mut v = Vec::new();
            push_g17(&mut v, d);
            assert_eq!(String::from_utf8(v).unwrap(), want, "appending {d}");
        }
    }

    #[test]
    fn dragonbox_writes_what_the_module_writes() {
        // Every one of these was read off the module's own Dragonbox rather
        // than reasoned about, including the four at the end, which are the
        // cases where the shorter rounding interval of a power of two decides
        // the last digit.
        let cases: &[(f64, &str)] = &[
            (0.0, "0"),
            (-0.0, "-0"),
            (1.0, "1"),
            (-1.0, "-1"),
            (0.5, "5E-1"),
            (0.1, "1E-1"),
            (0.3, "3E-1"),
            (1.5, "1.5"),
            (123.456, "123.456"),
            (0.1 + 0.2, "3.0000000000000004E-1"),
            (core::f64::consts::PI, "3.141592653589793"),
            (-2.5e-8, "-2.5E-8"),
            // The plain form runs from a ten thousandth up to the last width
            // that has no exponent left over, and nowhere else.
            (0.0001, "1E-4"),
            (1e7, "10000000"),
            (1e16, "1E16"),
            (1e17, "1E17"),
            (1e-16, "1E-16"),
            (1e-17, "1E-17"),
            (1e23, "1E23"),
            (9_007_199_254_740_993.0, "9007199254740992"),
            (f64::MAX, "1.7976931348623157E308"),
            (f64::MIN_POSITIVE, "2.2250738585072014E-308"),
            (f64::from_bits(1), "5E-324"),
            (f64::INFINITY, "Infinity"),
            (f64::NEG_INFINITY, "-Infinity"),
            (f64::NAN, "NaN"),
            (18_014_398_509_481_984.0, "18014398509481984"),
            (5.960_464_477_539_063e-8, "5.960464477539063E-8"),
            (2.980_232_238_769_531_2e-8, "2.9802322387695312E-8"),
            (6.189_700_196_426_902e26, "6.189700196426902E26"),
        ];
        for &(d, want) in cases {
            let mut buf = [0u8; DOUBLE_MAX];
            assert_eq!(
                core::str::from_utf8(write_dragonbox(&mut buf, d)).unwrap(),
                want,
                "writing {d}"
            );
            let mut v = Vec::new();
            push_dragonbox(&mut v, d);
            assert_eq!(String::from_utf8(v).unwrap(), want, "appending {d}");
        }
    }
}