ldeflate 0.1.3

//! **The piece-count ceiling** — the one place this crate refuses a request that
//! would exhaust memory instead of attempting it.
//!
//! Every parallel path here turns *one* size parameter into *many* independent
//! pieces: `cfg.segment` cuts an object into segments ([`crate::split`]),
//! `member` cuts a buffer into gzip members ([`crate::gzip`]). Both are
//! `len.div_ceil(piece)`, and both are **amplifying**: the caller passes two
//! small integers and the crate allocates a structure proportional to their
//! quotient. A `piece` of 1 against a multi-megabyte input asks for millions of
//! independently framed, independently compressed, independently checksummed
//! pieces.
//!
//! That is not a hypothetical. On 2026-08-03 a test crossing `len = 3_000_000`
//! with `member = 1` allocated ~497 GB on a 499 GB box, the kernel OOM killer
//! fired and took unrelated services down with it. The test was the trigger; the
//! bug was that the library said yes.
//!
//! # The measurement the ceiling is derived from
//!
//! Peak RSS of `gzip_compress_members(&[b'x'; n], &Config::default(), 1)` — i.e.
//! `n` one-byte members — on oden (32 cores, glibc malloc), release build:
//!
//! | pieces | peak RSS |
//! |---|---|
//! | 100_000 | 0.45 GB |
//! | 250_000 | 0.87 GB |
//! | 300_000 | 0.78 GB |
//! | 400_000 | **13.0 GB** |
//! | 800_000 | **21.0 GB** (address-space capped) |
//! | 3_000_000 | ~497 GB uncapped — the OOM |
//!
//! The cost is not merely linear-with-a-big-constant. Below ~3x10^5 pieces the
//! peak stays under a gigabyte; above it the allocator churn from one encoder
//! pair per unit turns the curve superlinear and, past the cap, unpredictable.
//! So the ceiling is set at the last power of two that is still measurably on
//! the flat part of that curve: [`MAX_PIECES`] = 2^18 = 262_144.
//!
//! # Why an error and not a clamp
//!
//! Clamping — quietly raising `piece` until the count fits — would be the
//! friendlier-looking fix and it is the wrong one. This crate's headline
//! guarantee is that the same `(input, Config)` produces byte-identical output
//! at any worker count, and the segment plan is what carries that guarantee. A
//! silent clamp changes the plan, therefore changes the output bytes, and does
//! it *without the caller ever learning* — turning a loud failure into a
//! reproducibility hole. An `Err` costs the caller one line and tells them
//! exactly what to pass instead.
//!
//! # What is NOT bounded here, and why
//!
//! The number of *objects* handed to [`crate::compress_objects`] is not capped.
//! That count is not amplification: the caller already holds every one of those
//! buffers in memory, so the plan is a constant factor over storage the caller
//! has already paid for. Only counts derived from a size *parameter* are
//! checked.

use crate::unit::DeflateError;

/// The largest number of independently framed pieces any one request may ask
/// for: **262_144** (2^18).
///
/// Measured headroom, so this is not an arbitrary round number:
///
/// - at the default `segment` of 1 MiB it admits a **256 GiB** object;
/// - at a 256 KiB gzip member it admits a **64 GiB** buffer;
/// - even at a deliberately small 64 KiB segment it admits **16 GiB**.
///
/// Every one of those is larger than any `&[u8]` this crate is realistically
/// handed, while the measured peak RSS at the ceiling stays under 1 GB. See the
/// module docs for the sweep.
pub const MAX_PIECES: usize = 1 << 18;

/// How many pieces of `piece` bytes an input of `total` bytes is cut into.
///
/// An empty input is one (empty) piece, not zero: a zlib stream with no blocks
/// and a gzip file with no members are both malformed, so every path here emits
/// at least one. `piece` is floored at 1 so a `0` argument cannot divide by
/// zero — but note that `piece = 0` and `piece = 1` then ask for the same
/// (rejected) `total` pieces.
#[inline]
pub fn piece_count(total: usize, piece: usize) -> usize {
    if total == 0 {
        1
    } else {
        total.div_ceil(piece.max(1))
    }
}

/// Return the piece count for `(total, piece)`, or refuse it.
///
/// `what` names the caller's axis ("gzip members", "split segments") so the
/// message is actionable without a backtrace. The error carries the request as
/// asked *and* the smallest `piece` that would have been accepted.
#[inline]
pub fn check_pieces(what: &'static str, total: usize, piece: usize) -> Result<usize, DeflateError> {
    let pieces = piece_count(total, piece);
    if pieces > MAX_PIECES {
        return Err(DeflateError::TooManyPieces {
            what,
            total,
            piece,
            pieces,
            max: MAX_PIECES,
        });
    }
    Ok(pieces)
}

/// The smallest piece size that keeps `total` bytes under [`MAX_PIECES`]. What
/// the error tells the caller to pass instead.
#[inline]
pub fn min_piece_for(total: usize) -> usize {
    total.div_ceil(MAX_PIECES).max(1)
}

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

    /// The counting rule itself: empty is one piece, exact multiples do not
    /// gain a spurious tail, `piece = 0` cannot panic.
    #[test]
    fn piece_count_is_the_ceiling_division_it_claims_to_be() {
        assert_eq!(piece_count(0, 1), 1, "an empty input is still one piece");
        assert_eq!(piece_count(0, 0), 1);
        assert_eq!(piece_count(1, 1), 1);
        assert_eq!(piece_count(1000, 1000), 1);
        assert_eq!(piece_count(1001, 1000), 2);
        assert_eq!(piece_count(999, 1000), 1);
        assert_eq!(
            piece_count(7, 0),
            7,
            "piece 0 is treated as 1, not a divide by zero"
        );
    }

    /// The boundary, from both sides. A ceiling that only ever says no is as
    /// useless as one that only ever says yes, so assert BOTH answers at the
    /// exact edge.
    #[test]
    fn the_ceiling_accepts_at_max_and_refuses_at_max_plus_one() {
        assert_eq!(check_pieces("t", MAX_PIECES, 1).unwrap(), MAX_PIECES);
        let e = check_pieces("t", MAX_PIECES + 1, 1).unwrap_err();
        assert!(
            matches!(e, DeflateError::TooManyPieces { pieces, max, .. }
                     if pieces == MAX_PIECES + 1 && max == MAX_PIECES),
            "wrong error for a one-over request: {e}"
        );
    }

    /// The message has to be actionable: it must name the count asked for, the
    /// ceiling, and a piece size that would work. A caller reading it should
    /// not have to guess or read this source.
    #[test]
    fn the_error_names_the_request_the_ceiling_and_the_fix() {
        let e = check_pieces("gzip members", 3_000_000, 1).unwrap_err();
        let m = e.to_string();
        for needle in ["gzip members", "3000000", "3000000 pieces", "262144"] {
            assert!(
                m.contains(needle),
                "message {m:?} does not mention {needle:?}"
            );
        }
        // And the suggested piece size must actually be accepted.
        let fix = min_piece_for(3_000_000);
        assert!(
            m.contains(&fix.to_string()),
            "message {m:?} does not suggest a piece size"
        );
        assert!(
            check_pieces("gzip members", 3_000_000, fix).is_ok(),
            "the suggested fix is refused"
        );
    }

    /// The headroom claim in the docs is a claim, so assert it. If a future
    /// tightening of MAX_PIECES broke a legitimate planet-sized request this
    /// must fail rather than be discovered in production.
    #[test]
    fn the_ceiling_still_admits_every_realistic_request() {
        assert!(
            check_pieces("segments", 256 << 30, 1 << 20).is_ok(),
            "256 GiB at 1 MiB segments"
        );
        assert!(
            check_pieces("members", 64 << 30, 256 << 10).is_ok(),
            "64 GiB at 256 KiB members"
        );
        assert!(
            check_pieces("segments", 16 << 30, 64 << 10).is_ok(),
            "16 GiB at 64 KiB segments"
        );
    }
}