//! Integer-exact LEARNED Gaussian-splat ATTRIBUTE codec — "the int_hyper of 3D".
//! A Gaussian splat is N Gaussians × 14 attributes (pos[3], scale[3], rot[4],
//! color[3], opacity), arranged as a `[14, S, S]` attribute image. A decode that runs
//! float arithmetic can round differently on different machines, and then the
//! reconstructed cloud — and its hash — differ between them. Here the synthesis is
//! integer (a `WHM1` network, 14 channels instead of RGB's 3) over a per-channel
//! factorized-rANS latent, all exact integers — so the decoded attribute tensor is
//! byte-identical on every machine: **splat-equivalence**, a portable cloud hash. The
//! synthesis decodes through the integer operator set, lowered by `whm1/1`
//! (`extensions/integer-operators.md` §13.2; [`crate::int_ops`]). The float rasterizer is
//! sink-supplied presentation; the *attributes* are the conformance contract.

use std::cmp::Ordering;

use crate::int_hyper_synth::{fnv1a, refused, IntModel, Refused, RefusalKind, MAX_AFRAC, MAX_TENSOR};
use crate::int_wire::Binary32;
use crate::rans::RansDecoder;
use crate::strict_json::{self, Json};

/// A decoded splat: the `[attr · s · s]` `u8` attribute image (channel-major), to be
/// un-normalized + un-sorted into Gaussians by the presentation layer.
pub struct DecodedSplat {
    pub attr: Vec<u8>,
    pub n_attr: usize,
    pub s: usize,
}

impl DecodedSplat {
    /// FNV-1a over the attribute bytes — the portable cloud hash (splat-equivalence).
    pub fn attr_hash(&self) -> u64 {
        fnv1a(&self.attr)
    }
}

/// A cloud's coded form, typed: what a `WIS1` payload carries
/// (`extensions/integer-payloads.md` §6), and what the tool's JSON form carries, read
/// by [`SplatJson`]. Per latent channel: a table, a symbol offset and a median.
#[derive(Debug, Clone, Copy)]
pub struct SplatStream<'a> {
    /// The fixed-point scale the stream was coded at; it must equal the model's.
    pub afrac: u32,
    pub c: usize,
    pub sh: usize,
    pub sw: usize,
    pub s: usize,
    pub n_attr: usize,
    pub cdfs: &'a [Vec<i32>],
    pub offsets: &'a [i32],
    pub median_q: &'a [i64],
    pub rans: &'a [u8],
}

/// The tool's JSON bitstream (`tools/wai_int_splat_export.py`'s `splat.json`), read
/// into the typed form, with the members only presentation reads: `n_gaussians` and
/// the per-attribute ranges `lo`, `hi`. A converter input and a debugging aid; the
/// payload is `WIS1`. Its `afrac` is read (the old JSON decoder ignored it) and must
/// be the model's.
///
/// It is read from its text ([`SplatJson::read`]) with no floating point: every count,
/// table entry, offset and median is an integer spelling read as an integer, and each
/// range is the binary32 value its spelling denotes ([`binary32_of`]), found in exact
/// integer arithmetic. So the same text reads to the same values on every machine and
/// in every build, whatever a general JSON parser would round a decimal to.
#[derive(Debug, Clone)]
pub struct SplatJson {
    pub afrac: u32,
    pub c: usize,
    pub sh: usize,
    pub sw: usize,
    pub s: usize,
    pub n_attr: usize,
    pub n_gaussians: usize,
    pub cdfs: Vec<Vec<i32>>,
    pub offsets: Vec<i32>,
    pub median_q: Vec<i64>,
    /// Per attribute, `(lo, hi)`: the binary32 values the JSON's `lo` and `hi` denote.
    pub ranges: Vec<(Binary32, Binary32)>,
    pub rans: Vec<u8>,
}

impl SplatJson {
    /// Read the tool's JSON bitstream from its text: one JSON text (RFC 8259, read
    /// strictly: no member named twice, nothing after the value), whose integers are
    /// spelled as integers (an optional `-`, then digits; `-0` is zero), and whose `lo`
    /// and `hi` each hold one binary32 value per attribute ([`binary32_of`]). The error
    /// names the member that fails.
    pub fn read(text: &[u8]) -> Result<Self, &'static str> {
        let bs = strict_json::read(text).map_err(|_| "the JSON form is not one strict JSON text")?;
        let get = |k: &'static str| bs.get(k).ok_or(k);
        let uz = |k: &'static str| get(k)?.as_u64().and_then(|v| usize::try_from(v).ok()).ok_or(k);
        let (c, sh, sw, s, n_attr) = (uz("c")?, uz("sh")?, uz("sw")?, uz("s")?, uz("attr")?);
        let n_gaussians = uz("n_gaussians")?;
        let afrac = get("afrac")?.as_u64().and_then(|v| u32::try_from(v).ok()).ok_or("afrac")?;
        let i32s = |v: &Json| v.as_arr()?.iter().map(|n| n.as_i64().and_then(|v| i32::try_from(v).ok())).collect::<Option<Vec<i32>>>();
        let offsets = i32s(get("offsets")?).ok_or("offsets")?;
        let median_q = get("median_q")?.as_arr().and_then(|a| a.iter().map(Json::as_i64).collect::<Option<Vec<i64>>>()).ok_or("median_q")?;
        let cdfs = get("cdfs")?.as_arr().and_then(|a| a.iter().map(i32s).collect::<Option<Vec<_>>>()).ok_or("cdfs holds a value outside i32")?;
        let ranges = |k: &'static str| -> Result<Vec<Binary32>, &'static str> {
            let not = if k == "lo" { "lo holds a value that is not a binary32 value" } else { "hi holds a value that is not a binary32 value" };
            get(k)?.as_arr().ok_or(k)?.iter().map(|v| match v {
                Json::Num(n) => binary32_of(n).ok_or(not),
                _ => Err(k),
            }).collect()
        };
        let (lo, hi) = (ranges("lo")?, ranges("hi")?);
        if lo.len() != n_attr || hi.len() != n_attr {
            return Err("lo and hi are not one per attribute");
        }
        let rans = b64_decode(get("rans_b64")?.as_str().ok_or("rans_b64")?)?;
        Ok(SplatJson { afrac, c, sh, sw, s, n_attr, n_gaussians, cdfs, offsets, median_q, ranges: lo.into_iter().zip(hi).collect(), rans })
    }

    /// The typed form, borrowing this one's tables.
    pub fn stream(&self) -> SplatStream<'_> {
        SplatStream {
            afrac: self.afrac, c: self.c, sh: self.sh, sw: self.sw, s: self.s, n_attr: self.n_attr,
            cdfs: &self.cdfs, offsets: &self.offsets, median_q: &self.median_q, rans: &self.rans,
        }
    }
}

/// Decode a typed cloud → the integer attribute tensor, byte-exact on every machine,
/// refusing rather than panicking or overflowing on any input:
///
/// 1. the stream's `afrac` is the model's, in `1..=30`; the medians, offsets and
///    tables are one per channel and every table is well formed; `g_s` maps the
///    latent's shape to `[n_attr, s, s]` with no buffer over
///    [`crate::int_hyper_synth::MAX_TENSOR`] elements; then `g_s` is lowered by
///    `whm1/1` and loaded under `acc64` with its bounds certificate
///    (`extensions/integer-operators.md` §13.2) — all before anything is allocated
///    for the payload;
/// 2. per channel, rANS-decode the symbol and rebuild `s·2^afrac + median_q`
///    ([`crate::int_entropy::dequantize`]); a stream that runs out before its last
///    symbol is refused;
/// 3. integer synthesis `g_s` through the integer operator set ([`crate::int_ops`]),
///    whose `check` ranges refuse a latent that could take a layer outside the exact
///    integer range (`field_range`), ending with the RGB8 step: each value clamped to
///    `[0, 2^afrac]` and rounded half up to `u8`, channel-major `[attr, s, s]`.
///
/// This is [`ops::decode_typed`]. The direct decode it replaced is kept, test-only
/// (feature `legacy_int`), as `legacy::decode_typed`.
pub fn decode_typed(gs: &IntModel, st: &SplatStream<'_>) -> Result<DecodedSplat, Refused> {
    ops::decode_typed(gs, st)
}

/// Step 2 of the decode, after its plan: per channel, the factorized rANS decode of the
/// latent, each symbol rebuilt as `s·2^afrac + median_q`. The latent grows a symbol at a
/// time, and the first symbol that runs the stream out refuses the payload before its
/// value is used; the stream must then end canonically.
fn latent(st: &SplatStream<'_>, afrac: u32) -> Result<Vec<i64>, Refused> {
    use crate::int_entropy::dequantize;
    use RefusalKind::*;
    let (c, plane) = (st.c, st.sh * st.sw);
    let mut y = Vec::new();
    let mut dec = RansDecoder::new(st.rans).map_err(|_| refused(FieldRange, "the latent stream is not a rANS stream"))?;
    for ch in 0..c {
        for _ in 0..plane {
            let sym = dec.decode(&st.cdfs[ch], st.cdfs[ch].len(), st.offsets[ch]);
            if dec.is_exhausted() {
                return Err(refused(StreamExhausted, "the latent stream ended before its last symbol"));
            }
            crate::int_hyper_synth::push_capped(&mut y, dequantize(sym, afrac, st.median_q[ch]).ok_or(refused(FieldRange, "a latent value leaves i64"))?, c * plane);
        }
    }
    if !dec.is_canonical_end() {
        return Err(refused(StreamNoncanonical, "the latent stream does not end canonically after its last symbol"));
    }
    Ok(y)
}

/// The direct decode, as the decoder ran before it decoded through the integer operator
/// set: the synthesis `g_s` run layer by layer by
/// [`crate::int_hyper_synth::legacy::run_net_checked`], which checks each layer's arithmetic on
/// the values it is given before it runs, then the attribute bytes formed here.
/// Test-only (`legacy_int`): the differential tests decode both ways, and the two differ
/// only on the planned breaks of `extensions/integer-operators.md` §15.3.
#[cfg(any(test, feature = "legacy_int"))]
pub mod legacy {
    use super::*;
    use crate::int_hyper_synth::legacy::run_net_checked;

    /// The direct decode of [`super::decode_typed`]'s arguments.
    pub fn decode_typed(gs: &IntModel, st: &SplatStream<'_>) -> Result<DecodedSplat, Refused> {
        use RefusalKind::*;
        splat_plan(gs, st)?;
        let (afrac, c, sh, sw, s, n_attr) = (gs.afrac, st.c, st.sh, st.sw, st.s, st.n_attr);
        let y = latent(st, afrac)?;
        // Integer synthesis → attribute tensor at 2^afrac.
        let (x, ..) = run_net_checked(gs, &y, c, sh, sw).map_err(|r| {
            if r.out_of_range {
                refused(FieldRange, "a decoded latent could take a layer outside the exact integer range")
            } else {
                refused(ModelMismatch, "g_s's parameters do not fit the running shapes")
            }
        })?;
        drop(y);
        // Round-half-up → u8 (channel-major [attr, s, s]).
        let (one, half) = (1i64 << afrac, 1i64 << (afrac - 1));
        let attr = x.iter().map(|&v| ((v.clamp(0, one) * 255 + half) >> afrac).clamp(0, 255) as u8).collect();
        Ok(DecodedSplat { attr, n_attr, s })
    }
}

/// The decode through the integer operator set (`extensions/integer-operators.md`):
/// `g_s` lowered by `whm1/1` with the RGB8 step (§13.2, §13.0), loaded under `acc64` with
/// its bounds certificate, and run by the operator set's interpreter
/// ([`crate::int_ops`]), whose `check` ranges carry the exactness checks of
/// integer-payloads §7. The driver keeps integer-payloads §7's order: the plan of
/// [`splat_plan`], then the set lowered and loaded, then the stream, then the graph.
pub mod ops {
    use super::*;
    use wai_ops::{Code, Loaded, Refusal, Tensor};

    /// A refusal of the operator set as the splat decode reports it
    /// (`extensions/integer-payloads.md` §8): a value outside a `check` range is
    /// `field_range`; the other codes are the payload extension's of the same name.
    fn kind(r: Refusal, what: &'static str) -> Refused {
        let k = match r.code {
            Code::FieldRange => RefusalKind::FieldRange,
            Code::TooLarge => RefusalKind::TooLarge,
            Code::GeometryMismatch => RefusalKind::GeometryMismatch,
            Code::StreamExhausted => RefusalKind::StreamExhausted,
            Code::StreamNoncanonical => RefusalKind::StreamNoncanonical,
            Code::ModelMismatch => RefusalKind::ModelMismatch,
        };
        refused(k, what)
    }

    /// `g_s` lowered by `whm1/1` with the RGB8 step and loaded under `acc64`: the set as
    /// the decode holds it, beside the parsed model.
    pub fn load(gs: &IntModel) -> Result<Loaded, Refused> {
        const WHAT: &str = "g_s does not lower to an integer-operator graph that loads under acc64";
        let net = crate::int_ops::whm1_net(gs).map_err(|r| kind(r, WHAT))?;
        wai_ops::lower::whm1_net_loaded(net, true, crate::int_ops::PROFILE).map_err(|r| kind(r, WHAT))
    }

    /// Everything the decode checks before it decodes a symbol: [`splat_plan`], then `g_s`
    /// lowered and loaded. Returns the loaded graph, and [`splat_plan`]'s working bytes and
    /// multiply-accumulates.
    pub(crate) fn plan(gs: &IntModel, st: &SplatStream<'_>) -> Result<(Loaded, u64, u128), Refused> {
        plan_with(gs, st, load)
    }

    /// [`plan`], with `g_s` lowered and loaded by `load`, after every check before it: a
    /// sink that keeps loaded sets (`crate::int_set_cache`) answers that one step from
    /// its store.
    pub(crate) fn plan_with<L>(
        gs: &IntModel, st: &SplatStream<'_>, load: impl FnOnce(&IntModel) -> Result<L, Refused>,
    ) -> Result<(L, u64, u128), Refused> {
        let (working, macs) = splat_plan(gs, st)?;
        Ok((load(gs)?, working, macs))
    }

    /// [`super::decode_typed`] through the integer operator set: the same attribute bytes,
    /// and the same refusals, except where integer-operators §15.3 lists a change.
    pub fn decode_typed(gs: &IntModel, st: &SplatStream<'_>) -> Result<DecodedSplat, Refused> {
        let (g, ..) = plan(gs, st)?;
        decode_loaded(&g, gs.afrac, st)
    }

    /// The decode after its plan: the stream at `afrac`, then `g`, the set's loaded
    /// lowering ([`load`]), then the bytes. `st` must be a cloud the plan admitted
    /// against that set. What it holds beyond the set is what the payload declares
    /// (integer-payloads §7, *Memory and work*).
    pub fn decode_loaded(g: &Loaded, afrac: u32, st: &SplatStream<'_>) -> Result<DecodedSplat, Refused> {
        let (c, sh, sw, s, n_attr) = (st.c, st.sh, st.sw, st.s, st.n_attr);
        let y = latent(st, afrac)?;
        // The plan admitted every size, so each fits u32.
        let x = Tensor::new(c as u32, sh as u32, sw as u32, y);
        let out = crate::int_ops::run1(g, x, &[]).map_err(|r| kind(r, "a decoded latent is outside a check range of g_s"))?;
        if (out.c as usize, out.h as usize, out.w as usize) != (n_attr, s, s) {
            return Err(refused(RefusalKind::GeometryMismatch, "g_s does not give the attribute shape the payload declares"));
        }
        // The RGB8 step ends the graph, so every value is a byte.
        let attr = out.data.iter().map(|&v| v as u8).collect();
        Ok(DecodedSplat { attr, n_attr, s })
    }
}

/// What [`decode_typed`] checks before it decodes a symbol, short of lowering `g_s`
/// ([`ops::plan`] adds that), and the most bytes the decode then holds at once on the
/// reference kernels beyond the payload and the set as it holds it (the parsed model,
/// and its loaded lowering): the latent (`i64`) with `g_s`'s buffers while it runs (a
/// layer's input, its output and a transposed convolution's uncropped plane), then
/// `g_s`'s output (`i64`) with the attribute tensor (`u8`); and `g_s`'s
/// multiply-accumulates ([`crate::int_hyper_synth::NetPlan`]).
pub(crate) fn splat_plan(gs: &IntModel, st: &SplatStream<'_>) -> Result<(u64, u128), Refused> {
    use RefusalKind::*;
    let afrac = gs.afrac;
    if !(1..=MAX_AFRAC).contains(&afrac) {
        return Err(refused(ModelMismatch, "the model's fixed-point scale is outside 1..=30"));
    }
    if st.afrac != afrac {
        return Err(refused(ModelMismatch, "the stream's afrac is not the model's"));
    }
    let (c, sh, sw, s, n_attr) = (st.c, st.sh, st.sw, st.s, st.n_attr);
    if [c, sh, sw, s, n_attr].contains(&0) || st.median_q.len() != c || st.offsets.len() != c || st.cdfs.len() != c {
        return Err(refused(FieldRange, "a dimension is zero, or the medians, offsets or tables are not one per channel"));
    }
    if st.median_q.iter().any(|m| m.unsigned_abs() > 1 << 47) {
        return Err(refused(FieldRange, "a median's magnitude exceeds 2^47"));
    }
    let ok = |t: &Vec<i32>| (3..=4097).contains(&t.len()) && t[0] == 0 && t[t.len() - 1] == 1 << 16 && t.windows(2).all(|p| p[0] < p[1]);
    if !st.cdfs.iter().all(ok) {
        return Err(refused(CdfMalformed, "a table is not a CDF from 0 to 65536, strictly increasing"));
    }
    let size = |d: &[usize]| d.iter().try_fold(1usize, |a, &x| a.checked_mul(x)).filter(|&n| n <= MAX_TENSOR);
    let (Some(latent), Some(out)) = (size(&[c, sh, sw]), size(&[n_attr, s, s])) else {
        return Err(refused(TooLarge, "the latent or the attribute tensor exceeds 2^26 elements"));
    };
    let p = crate::int_hyper_synth::plan_net(gs, c, sh, sw)?;
    if p.out != (n_attr, s, s) {
        return Err(refused(GeometryMismatch, "g_s does not give the attribute shape the payload declares"));
    }
    let (latent, out) = (latent as u64, out as u64);
    Ok(((8 * (latent + p.live)).max(8 * out + out), p.macs))
}

/// Decode the tool's JSON bitstream (`splat.json`, its text) → the integer attribute
/// tensor: [`SplatJson::read`] then [`decode_typed`]. A debugging and converter path; the
/// payload is `WIS1`. `gs` is the WHM1 model (`splat_gs.bin`). Byte-identical on every
/// machine.
pub fn decode(gs: &IntModel, json: &[u8]) -> Result<DecodedSplat, &'static str> {
    decode_typed(gs, &SplatJson::read(json)?.stream()).map_err(|r| r.detail)
}

/// Dependency-free base64 decode (standard alphabet) — the rANS bytes ride in JSON as
/// base64, same as `int_audio` / `int_video`.
fn b64_decode(s: &str) -> Result<Vec<u8>, &'static str> {
    fn val(c: u8) -> Result<u8, &'static str> {
        Ok(match c {
            b'A'..=b'Z' => c - b'A',
            b'a'..=b'z' => c - b'a' + 26,
            b'0'..=b'9' => c - b'0' + 52,
            b'+' => 62,
            b'/' => 63,
            _ => return Err("bad base64 char"),
        })
    }
    let s: Vec<u8> = s.bytes().filter(|&c| c != b'=' && !c.is_ascii_whitespace()).collect();
    let mut out = Vec::with_capacity(s.len() * 3 / 4);
    for chunk in s.chunks(4) {
        let mut acc = 0u32;
        let mut bits = 0;
        for &c in chunk {
            acc = (acc << 6) | val(c)? as u32;
            bits += 6;
        }
        for k in 0..bits / 8 {
            out.push((acc >> (bits - 8 * (k + 1))) as u8);
        }
    }
    Ok(out)
}

/// The most significant digits of a decimal [`binary32_of`] keeps. Every bound it
/// compares a decimal with is a multiple of `2^-1075`, so of `10^-1075`; a decimal below
/// `10^39` cut to this many digits has its last kept digit at `10^-1161` or below, so the
/// digits dropped (a nonzero tail, which it notes) cannot change any comparison.
const KEPT_DIGITS: usize = 1200;

/// The binary32 value the JSON number spelled `n` denotes, read as the export tool and
/// the independent converter (`int-payload-conformance/int_payload_verify.py`) read it,
/// or `None` when it denotes none:
///
/// - an integer spelling (an optional `-`, then digits: no fraction and no exponent) is
///   that integer, which must be a binary32 value exactly: `2^60` is, `2^60 + 1` is not
///   (a binary64 would round it to `2^60`); `-0` is the integer zero, so `+0`;
/// - any other spelling denotes the binary64 value nearest it (ties to even; a magnitude
///   that rounds to zero is a zero of the spelling's sign, and one past the binary64
///   range is no value), and that must be a binary32 value: the export writes each range
///   as the shortest decimal of a binary32 value widened to binary64.
///
/// Integer arithmetic throughout, so no machine and no build reads a spelling to another
/// value. The decimal `m·10^e` is compared exactly with binary values `a·2^b`: the largest
/// binary32 value not above its magnitude is found by bisection over the bit patterns
/// (ordered as their values are), and the decimal is that value, or the next, where it
/// lies in the closed interval of reals that round to it in binary64.
pub fn binary32_of(n: &str) -> Option<Binary32> {
    let (neg, rest) = match n.strip_prefix('-') {
        Some(r) => (true, r),
        None => (false, n),
    };
    let (mant, exp) = match rest.find(['e', 'E']) {
        Some(i) => (&rest[..i], Some(&rest[i + 1..])),
        None => (rest, None),
    };
    let (int, frac) = match mant.find('.') {
        Some(i) => (&mant[..i], Some(&mant[i + 1..])),
        None => (mant, None),
    };
    let integer = exp.is_none() && frac.is_none();
    let frac = frac.unwrap_or("");
    let digit = |b: u8| b.is_ascii_digit();
    if int.is_empty() || !int.bytes().all(digit) || !frac.bytes().all(digit) {
        return None;
    }
    // The exponent, saturated far past any magnitude that can matter.
    let mut e: i64 = 0;
    if let Some(x) = exp {
        let (eneg, ed) = match x.as_bytes().first() {
            Some(b'-') => (true, &x[1..]),
            Some(b'+') => (false, &x[1..]),
            _ => (false, x),
        };
        if ed.is_empty() || !ed.bytes().all(digit) {
            return None;
        }
        for b in ed.bytes() {
            e = (e * 10 + (b - b'0') as i64).min(1 << 40);
        }
        if eneg {
            e = -e;
        }
    }
    let sign = if neg { 0x8000_0000 } else { 0 };
    let digits: Vec<u8> = int.bytes().chain(frac.bytes()).map(|b| b - b'0').collect();
    let Some(first) = digits.iter().position(|&d| d != 0) else {
        // Zero. The integer zero has no sign; a decimal zero keeps its spelling's.
        return Some(Binary32(if integer { 0 } else { sign }));
    };
    let last = digits.iter().rposition(|&d| d != 0).expect("a nonzero digit");
    let sig = &digits[first..=last];
    // |value| = sig · 10^e10, and 10^(q − 1) ≤ |value| < 10^q.
    let e10 = e - frac.len() as i64 + (digits.len() - 1 - last) as i64;
    let q = e10 + sig.len() as i64;
    if q >= 40 {
        // At least 10^39: past the greatest binary32 value's interval (or the integer is
        // past it).
        return None;
    }
    if q <= -324 {
        // Below 10^-324, so below 2^-1075: a decimal (never an integer) that rounds to
        // zero in binary64.
        return Some(Binary32(sign));
    }
    let kept = &sig[..sig.len().min(KEPT_DIGITS)];
    let d = Decimal::new(kept, e10 + (sig.len() - kept.len()) as i64, kept.len() < sig.len());
    // A positive binary32 bit pattern's value, `a·2^b`.
    let value = |bits: u32| -> (u64, i32) {
        let (x, f) = (bits >> 23, (bits & 0x7f_ffff) as u64);
        if x == 0 { (f, -149) } else { (f | 1 << 23, x as i32 - 150) }
    };
    // The largest pattern whose value is not above |d|, below the infinity's pattern: lo.
    let (mut lo, mut hi) = (0u32, 0x7f80_0000u32);
    while hi - lo > 1 {
        let mid = lo + (hi - lo) / 2;
        let (a, b) = value(mid);
        if d.order(a, b) == Ordering::Less {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    if integer {
        // The integer itself must be the value.
        let (a, b) = value(lo);
        return (lo != 0 && d.order(a, b) == Ordering::Equal).then_some(Binary32(sign | lo));
    }
    // The closed interval of reals binary64 rounds to the nonzero binary32 value `bits`
    // (ties go to it: its binary64 significand ends in 29 zero bits, so is even, and its
    // neighbours' are odd). It is normal in binary64, `m·2^31 · 2^(x − 31)` with `m` in
    // `[2^23, 2^24)`, whose half unit above is `2·2^(x − 31)`, and below the same, or half
    // that at a power of two.
    let bounds = |bits: u32| -> ((u64, i32), (u64, i32)) {
        let (mut m, mut x) = value(bits);
        while m < 1 << 23 {
            m <<= 1;
            x -= 1;
        }
        let below = if m == 1 << 23 { 1 } else { 2 };
        (((m << 31) - below, x - 31), ((m << 31) + 2, x - 31))
    };
    if lo == 0 {
        // Below the least subnormal: zero where binary64 rounds the decimal to zero, at
        // most 2^-1075 (the tie goes to zero, whose significand is even).
        if d.order(1, -1075) != Ordering::Greater {
            return Some(Binary32(sign));
        }
    } else {
        let (_, (a, b)) = bounds(lo);
        if d.order(a, b) != Ordering::Greater {
            return Some(Binary32(sign | lo));
        }
    }
    if hi < 0x7f80_0000 {
        let ((a, b), _) = bounds(hi);
        if d.order(a, b) != Ordering::Less {
            return Some(Binary32(sign | hi));
        }
    }
    None
}

/// A positive decimal `m·10^e`, held as `m·10^max(e, 0)` over `10^max(−e, 0)`, and
/// whether digits past `m` were dropped (then it lies above `m·10^e`, by less than one
/// unit of `m`'s last digit).
struct Decimal {
    num: Nat,
    den: Nat,
    sticky: bool,
}

impl Decimal {
    fn new(digits: &[u8], e: i64, sticky: bool) -> Decimal {
        let mut num = Nat(Vec::new());
        for chunk in digits.chunks(9) {
            let v = chunk.iter().fold(0u32, |a, &d| a * 10 + d as u32);
            num.mul_add_small(10u32.pow(chunk.len() as u32), v);
        }
        let mut den = Nat(vec![1]);
        if e >= 0 { num.mul_pow10(e as u64) } else { den.mul_pow10(e.unsigned_abs()) }
        Decimal { num, den, sticky }
    }

    /// The decimal's order against `a·2^b`. Exact: `a·2^b` with `b ≥ -1075` is a multiple
    /// of the last kept digit's unit (see [`KEPT_DIGITS`]), so a dropped tail decides
    /// only a tie.
    fn order(&self, a: u64, b: i32) -> Ordering {
        let (mut l, mut r) = (self.num.clone(), self.den.mul_u64(a));
        if b >= 0 { r.shl(b as u64) } else { l.shl(b.unsigned_abs() as u64) }
        match l.order(&r) {
            Ordering::Equal if self.sticky => Ordering::Greater,
            o => o,
        }
    }
}

/// A non-negative integer, as little-endian base-2^32 limbs with no zero limb on top: the
/// exact arithmetic [`binary32_of`] compares in.
#[derive(Clone)]
struct Nat(Vec<u32>);

impl Nat {
    /// `self·k + add`.
    fn mul_add_small(&mut self, k: u32, add: u32) {
        let mut carry = add as u64;
        for l in &mut self.0 {
            let v = *l as u64 * k as u64 + carry;
            *l = v as u32;
            carry = v >> 32;
        }
        if carry != 0 {
            self.0.push(carry as u32);
        }
    }

    fn mul_pow10(&mut self, mut k: u64) {
        while k > 0 {
            let s = k.min(9);
            self.mul_add_small(10u32.pow(s as u32), 0);
            k -= s;
        }
    }

    fn mul_u64(&self, a: u64) -> Nat {
        let mut out = vec![0u32; self.0.len() + 2];
        for (j, w) in [a as u32, (a >> 32) as u32].into_iter().enumerate() {
            let mut carry = 0u64;
            for (i, &l) in self.0.iter().enumerate() {
                let v = l as u64 * w as u64 + out[i + j] as u64 + carry;
                out[i + j] = v as u32;
                carry = v >> 32;
            }
            let mut k = self.0.len() + j;
            while carry != 0 {
                let v = out[k] as u64 + carry;
                out[k] = v as u32;
                carry = v >> 32;
                k += 1;
            }
        }
        while out.last() == Some(&0) {
            out.pop();
        }
        Nat(out)
    }

    fn shl(&mut self, bits: u64) {
        if self.0.is_empty() {
            return;
        }
        let b = (bits % 32) as u32;
        if b > 0 {
            let mut carry = 0u32;
            for l in &mut self.0 {
                let v = ((*l as u64) << b) | carry as u64;
                *l = v as u32;
                carry = (v >> 32) as u32;
            }
            if carry != 0 {
                self.0.push(carry);
            }
        }
        self.0.splice(0..0, std::iter::repeat_n(0, (bits / 32) as usize));
    }

    fn order(&self, o: &Nat) -> Ordering {
        self.0.len().cmp(&o.0.len()).then_with(|| self.0.iter().rev().cmp(o.0.iter().rev()))
    }
}
