lbzip2/src/limits.rs
//! **The output ceiling** — the one place this crate refuses to keep growing a
//! buffer that a few kilobytes of input claimed the right to fill.
//!
//! bzip2 has no `ldeflate`-style piece count and no `linflate`-style honest
//! expansion ratio to bound it against. Its amplification is the largest of any
//! decoder in this workspace, and — unlike DEFLATE's 1032:1 — it is not usefully
//! bounded by the input length. Measured on oden, 2026-08-03, `bzip2 -9`:
//!
//! | input (zeros) | .bz2 size | ratio |
//! |---|---|---|
//! | 1 MiB | 45 B | 23_302:1 |
//! | 8 MiB | 48 B | 174_763:1 |
//! | 64 MiB | 79 B | 849_479:1 |
//! | 256 MiB | 208 B | 1_290_555:1 |
//! | 1 GiB | 785 B | **1_367_824:1** |
//!
//! The ratio is still climbing at 1 GiB: it is asymptotic, not capped. One bzip2
//! block holds at most 900_000 post-RLE1 bytes, and RLE1-reverse expands a 5-byte
//! run marker to up to 259 output bytes (~51.8×), so a single block can emit
//! ~46 MB from the ~30 compressed bytes its header and Huffman tables occupy.
//! Bounding "output ≤ input × ratio" the way [`linflate::limits`] does would
//! therefore admit ~1.4 million bytes per input byte — a ceiling that permits
//! everything and refuses nothing. For bzip2 the only bound with teeth is an
//! absolute one.
//!
//! # What is capped, and what is deliberately not
//!
//! Only the two entry points that materialise **the whole stream as one
//! `Vec<u8>`** — [`crate::stream::decompress`] and
//! [`crate::parallel::decompress_parallel`]. Both were unbounded: a 50 KB file of
//! concatenated all-zero streams asked each of them for tens of gigabytes and got
//! it, and `decompress_parallel` asked twice (every segment resident, then a full
//! copy into the assembled output).
//!
//! The streaming readers ([`crate::reader`]) are *not* capped and must not be:
//! their whole purpose is decoding an output larger than memory, and their
//! in-flight bytes are already bounded by one batch. The planet-sized OSM-XML
//! decode this crate exists for goes through them.
//!
//! # Why the default is ON
//!
//! `decompress_capped` already existed and nothing called it. A limit that a
//! caller must opt into is not a limit — it is documentation. So the plain names
//! are the capped ones, and a caller who genuinely wants an unbounded whole-stream
//! decode asks for it by name: [`crate::stream::decompress_uncapped`],
//! [`crate::parallel::decompress_parallel_uncapped`]. That is a behaviour change
//! for anyone decoding more than [`DEFAULT_MAX_OUTPUT`] into a single `Vec`, and
//! it is meant to be: they get a named error telling them exactly which call to
//! make instead.
use std::sync::atomic::{AtomicUsize, Ordering};
use crate::block::BlockError;
/// Sentinel message for "decompressed output exceeded the cap".
///
/// Lives here now so the sequential and parallel paths cannot drift apart;
/// [`crate::stream::OUTPUT_TOO_LARGE`] re-exports it for the callers that already
/// match on it.
pub const OUTPUT_TOO_LARGE: &str = "decompressed output exceeds max_out cap";
/// The largest expansion ratio actually observed from `bzip2 -9`, measured on
/// oden on 2026-08-03: **1_367_824:1** (1 GiB of zeros → 785 bytes).
///
/// Recorded for the module docs' argument, not used as a bound — see above for
/// why a ratio bound is worthless for bzip2. At this ratio
/// [`DEFAULT_MAX_OUTPUT`] is reached by an input of **823 bytes**.
pub const MEASURED_MAX_RATIO: usize = 1_367_824;
/// Default ceiling on a whole-stream in-memory decode: **1 GiB**.
///
/// Sized against what the capped calls are *for* — handing the caller the entire
/// decompressed stream in one `Vec<u8>`, which it must then hold resident. An
/// output past a gigabyte is not a thing to hand back by value; it is a thing to
/// stream ([`crate::reader`]) or to ask for explicitly with a number the caller
/// chose (`decompress_capped`).
pub const DEFAULT_MAX_OUTPUT: usize = 1 << 30;
/// A decode budget shared across the parallel workers.
///
/// The parallel path cannot cap per segment: segments are uneven, so any
/// per-segment share either rejects legitimate streams or bounds nothing. One
/// atomic counter drained by every worker is the only division-free bound. It is
/// charged **once per decoded block** — roughly once per 46 MB of output at the
/// worst case — so it is free next to the inverse-BWT chase it guards.
pub struct OutputBudget {
remaining: AtomicUsize,
}
impl OutputBudget {
/// A budget of `max` output bytes.
pub fn new(max: usize) -> Self {
Self {
remaining: AtomicUsize::new(max),
}
}
/// A budget nothing can exhaust — what the explicitly-uncapped entry points
/// pass, and the only way to get the pre-cap behaviour.
pub fn unlimited() -> Self {
Self {
remaining: AtomicUsize::new(usize::MAX),
}
}
/// Charge `n` output bytes, or refuse.
///
/// Saturating on the way down so a concurrent overshoot cannot wrap the
/// counter back up to a huge remaining budget — which would turn the ceiling
/// into a floor exactly when several workers are over it at once.
pub fn take(&self, n: usize) -> Result<(), BlockError> {
let prev = self
.remaining
.fetch_update(Ordering::Relaxed, Ordering::Relaxed, |r| {
Some(r.saturating_sub(n))
});
// `fetch_update` with an infallible closure cannot return Err.
let prev = prev.unwrap_or(0);
if prev < n {
return Err(BlockError(OUTPUT_TOO_LARGE));
}
Ok(())
}
/// Output bytes still allowed.
pub fn remaining(&self) -> usize {
self.remaining.load(Ordering::Relaxed)
}
}
#[cfg(test)]
mod tests {
use super::*;
/// The counter itself, from both sides of its edge. A budget that only ever
/// says yes and one that only ever says no are equally useless, so assert the
/// exact boundary in both directions.
#[test]
fn the_budget_admits_exactly_its_ceiling_and_refuses_one_past_it() {
let b = OutputBudget::new(1000);
assert!(b.take(600).is_ok());
assert_eq!(b.remaining(), 400);
assert!(
b.take(400).is_ok(),
"the last byte of the budget must be spendable"
);
assert_eq!(b.remaining(), 0);
let e = b.take(1).unwrap_err();
assert_eq!(e.0, OUTPUT_TOO_LARGE, "wrong error past the ceiling");
}
/// A single charge larger than the whole budget must be refused outright,
/// not clamped into a partial spend.
#[test]
fn one_oversized_charge_is_refused_whole() {
let b = OutputBudget::new(100);
assert!(b.take(101).is_err());
assert_eq!(
b.remaining(),
0,
"an over-budget charge saturates, it does not wrap"
);
}
/// The saturating subtract is the load-bearing part: an unsigned wrap would
/// hand the next worker a budget of ~2^64 at exactly the moment the stream is
/// over the limit. Drive it past zero from several threads and assert the
/// counter never comes back up.
#[test]
fn concurrent_overshoot_cannot_wrap_the_counter_back_up() {
let b = std::sync::Arc::new(OutputBudget::new(64));
let mut hs = Vec::new();
for _ in 0..16 {
let b = std::sync::Arc::clone(&b);
hs.push(std::thread::spawn(move || {
for _ in 0..64 {
let _ = b.take(1024);
}
}));
}
for h in hs {
h.join().unwrap();
}
assert_eq!(b.remaining(), 0, "the budget wrapped instead of saturating");
assert!(
b.take(1).is_err(),
"an exhausted budget must stay exhausted"
);
}
/// `unlimited()` must actually be unlimited — including for a charge that
/// would overflow any finite budget.
#[test]
fn the_unlimited_budget_admits_a_charge_no_finite_one_could() {
let b = OutputBudget::unlimited();
assert!(b.take(usize::MAX / 2).is_ok());
assert!(b.take(1 << 40).is_ok());
}
/// The default is a number this crate has to stand behind, so tie it to the
/// measurement it is argued from: it must be reachable by an input small
/// enough that "the input was tiny" is the whole point.
#[test]
fn the_default_ceiling_is_reachable_from_a_kilobyte_of_input() {
let bytes_needed = DEFAULT_MAX_OUTPUT.div_ceil(MEASURED_MAX_RATIO);
assert!(
bytes_needed < 1024,
"{DEFAULT_MAX_OUTPUT} bytes needs {bytes_needed} input bytes at the measured \
{MEASURED_MAX_RATIO}:1 — the ceiling is no longer the interesting number"
);
}
}