Skip to content
REFERENCE / ZLIB × LEAN

deflateBound_z

Compute a size bound using the stream's current configuration and wrapper.

Full chapter and shared rules ↗
z_size_t ZEXPORT deflateBound_z(z_streamp strm, z_size_t sourceLen);

Compute a size bound using the stream's current configuration and wrapper.

This query answers how many output bytes are enough for the whole input. sourceLen is the input byte count, written n below; w is the wrapper size: header, trailer and optional fields together. floor(x) rounds down. SIZE_MAX is the largest value of the return type z_size_t; "saturates" means that a larger mathematical result returns this maximum and does not wrap to a small number.

Return values and next calls

Return type. z_size_t — Output-capacity bound (bytes)

The return is an output-capacity bound in bytes, not a zlib status code. It can saturate at SIZE_MAX.

deflateBound_z()
Returned value Meaning and conditions Caller’s next step
bound
Output byte bound
For a live stream, the formula uses the current window, memory level, compression level, strategy and full wrapper size; NULL or a safely checkable invalid stream uses the larger fixed/stored formula plus 18. All results saturate at SIZE_MAX and leave the heap unchanged. Apply the stated capacity guarantee only after init/setup and before compression, with fixed configuration/dictionary/header, standard tuning and no prime bits; buffer representability and avail_in/avail_out capacity conditions must also hold.

Calling conditions and effects

Domain Restricted domain (live stream and readable retained header); every z_size_t sourceLen is included. Effect: query.

Pre live stream and shared header conditions. For the output-capacity guarantee below, call after init and any dictionary/header setup, before compression. Keep configuration, header and dictionary fixed; use standard tuning and no inserted prime bits.

Proof goals.

  • Goal. Goal.deflateBound_z_safety (Safety/Streams.lean); required. Theorem: ZlibF.Spec.Public.StreamCallSafetyProof.deflateBound_z_safety (public-stream-call-safety.lean). The goal has two clauses: the refusal of a refused stream, and one call on a reachable stream.
  • Applies when. The refusal asks that strm is a refused stream (RefusedDeflate). The call on a reachable stream asks (StreamCallDomain):
    1. strm is a reachable stream (StreamReachable);
    2. the platform size bound holds (ByteObjectsFit);
    3. conditions 4 to 6 of deflate on the gzip header (ActiveHeader);
    4. a header record that was given to deflateSetHeader is live and readable at this call, not only while the header is being written: the record is live and is not one of the stream's own blocks, a non-NULL extra points to extra_len readable bytes outside the stream's own blocks, and a non-NULL name or comment is a NUL-terminated string (DeflateHeaderLive).
  • Covered without condition. Every sourceLen. Every reachable stream, in every phase: before the first deflate, mid-stream, while finishing, and after Z_STREAM_END. In the refusal: every refused stream and every value of the other arguments.
  • Guarantees (StreamCallSafe for the call on a reachable stream).
    • Returns. On a refused stream the call returns the value it returns for a NULL strm with the same sourceLen: the conservative bound, not an error code. On a reachable stream the call returns.
    • State. On a reachable stream, the stream keeps its invariant (StreamInvariant).
    • Writes. On a refused stream, nothing: the heap is unchanged. On a reachable stream, only the stream record and the stream's own blocks.
    • Allocations. On a reachable stream, the exact allocation account (LiveChange).
  • Not in this goal. A stream record with zalloc and zfree set whose state is a garbage pointer, points to a freed state, or points to an inflate state: no goal covers this call on such a record (deviations). The value returned: functional goal Goal.deflateBound_z (not planned; not done). That this much output room is enough: the clause DeflateCompletes of the functional goal Goal.deflate_sequence (not planned; not done).
Complete return conditions and boundaries

Post the heap is unchanged. The numerical target is the following mathematical value, saturated at SIZE_MAX, where n = sourceLen and w is the full wrapper size:

  • Window 15, memory level 8 and a strategy other than Z_FIXED: n + floor(n/4096) + floor(n/16384) + floor(n/33554432) + 7 + w.
  • Otherwise, if window bits are at most hash bits and level is nonzero: n + floor(n/8) + floor(n/256) + floor(n/512) + 4 + w.
  • Otherwise: n + floor(n/32) + floor(n/128) + floor(n/2048) + 7 + w.

Hash bits are memory level plus 7. The words "and a strategy other than Z_FIXED" in the first case are the change of patch 0006: the unpatched C uses the first formula for every strategy. With Z_FIXED, window 15 and memory level 8, the patched function uses the second formula at levels 1 to 9 and the third at level 0. The first formula is too small for Z_FIXED at levels 1 to 3: on the unpatched C, one deflate(Z_FINISH) call with that much output room can return Z_OK (finding, reproduced with the real C).

w is 0 for raw, 6 for zlib plus 4 when preset history is present, or 18 for gzip plus its optional extra field (two length bytes and the low 16 bits of extra_len, the length the header writer emits), terminated name/comment and header CRC. Taking the low 16 bits is the change of patch 0007: the unpatched C adds 2 + extra_len in 32-bit unsigned arithmetic, which wraps for extra_len 2^32 - 2 and 2^32 - 1 and gives a bound about 64 KiB too small (finding, reproduced with the real C).

Output capacity: separately from the numerical formula, for a representable adequate buffer, when the input and output sizes fit avail_in and avail_out, supplying all n bytes to one deflate(Z_FINISH) with at least the bound of output room must return Z_STREAM_END. A clean schedule using only Z_NO_FLUSH before Z_FINISH has the total-output bound. Other flush schedules can exceed it. A saturated result is not a promise that an addressable buffer of that size exists.

Outside focused scope: NULL or a safely checkable invalid stream receives the larger of the fixed/stored formulas above, plus 18, with saturation. There is no error code. The functional goal covers every readable gzip header length, including an extra_len above 65535, which the contracts on this page leave out.

Shared conditions and scope

Use a z_stream compressor when input arrives in pieces, output space is limited, or you need a chosen wrapper, dictionary or flush boundary. A wrapper is the header, trailer and integrity information added around the DEFLATE data; raw DEFLATE has none. Initialize once, call deflate with successive buffers, and end the stream even if compression is abandoned. For a single buffer, see compress and compress2.

Task Entries
Start or reuse Init, configured init, reset, reset retaining history
Supply metadata or history Dictionary, read history, gzip header
Compress and size output Deflate, bound, pending output, last flush bits
Adjust or branch Parameters, tuning, priming, copy
Release storage End

The contracts follow zlib.h and deflate.c of the pinned zlib with the patches applied, in the default LP64 Linux build. Of the seven patches only patches 0006 and 0007 touch deflate.c. Both change deflateBound_z, and with it the result of deflateBound, which calls deflateBound_z: 0006 one condition, 0007 the length of the gzip extra field in the wrapper size. The entry deflateBound_z states both changes. The patches change no other function. These are focused contracts: Pre describes ordinary correct use and is deliberately narrower than what the function accepts. Cases outside Pre that the C still handles appear under Errors or Outside focused scope. A call outside Pre is not thereby undefined, and it need not return an error code. See how to read a contract for the domain and effect labels.

What is proved. Safety only: each call returns without undefined behaviour or a memory error, writes only what its goal names, and leaks nothing (safety). Each entry gives its goal under Proof goals, in the five items and with the fixed phrases that Reading a Proof goals paragraph defines: the goal and its theorem; the conditions under which it applies, in the order of the Lean statement; what it covers for every value; what it guarantees (returns, state, writes, allocations); and what it leaves to another goal. The proof assumes the conditions listed there, not the documentary Pre. Post, the return tables and the notes describe functional behaviour. They are read from the C, are to confirm where no theorem states them, and are not required for the safety results. Progress says which goals are done.

Shared conventions

Under each stated Pre, the documented behaviour is that the call terminates without a runtime fault and that Post holds. A call that leaves the stream live preserves its representation invariant. The part of this that is proved is the safety goal of the entry.

First, how data changes hands in one call. next_in points to the start of the input not yet read, and avail_in is the number of bytes readable from there. next_out points to the next writable position, and avail_out is the output room that remains, also in bytes. One call may consume only part of the input and deliver only part of the output. Read the updated pointers and counts, take the bytes delivered, then give the same stream more input or more output room.

  • Live stream: a writable z_stream with a compressor state established by successful init or copy, preserved by legal calls, and not ended. The caller does not alter its internal state or allocator fields. Calls on one stream are sequential.
  • Buffers: input covers avail_in readable bytes; output covers avail_out writable bytes. They do not overlap each other, the stream or its owned state. A non-NULL scalar result points to a writable cell separate from other results and stream memory. These separation conditions are assumptions of the contracts. Where a safety goal assumes one too, its Proof goals says so and deviations has a row.
  • Allocator: the default allocator/free pair is used, or both fields are NULL before init. Allocation may fail on any attempt. Custom allocator callbacks are outside this page's scope.
  • Frame and ownership: calls change only their stream, its owned state and stated output regions. Caller input is read-only. Caller buffers and header records remain caller-owned. Only init and copy allocate; only their failure cleanup and deflateEnd free memory. Other calls preserve the stream's allocation set.
  • Header lifetime: a retained gzip header and its optional fields remain readable and unchanged while used. Non-NULL name and comment have a terminating zero; extra covers its stated length. The contracts on this page take extra_len <= 65535.
  • Checked refusals: except for init and bounds, a failed stream check returns Z_STREAM_ERROR before normal operation, without writes. deflateCopy additionally clears a non-NULL destination state. Query output cells are untouched on this refusal.
  • Restricted domain means these explicit memory, lifetime and call-order conditions, plus the entry's Pre. It does not mean every representable pointer or integer is accepted. Error summaries cover stream records and states that the checks can read, not arbitrary invalid addresses.
  • Reachable stream: the proof goals speak of a reachable stream where the contracts say live stream (how to read a contract). A call that a goal covers extends the stream's history: when it returns, with any code, the stream is reachable again and the goal of the next call applies. deflateEnd ends the history.
  • Result cells as values: deflateGetDictionary, deflatePending and deflateUsed report results through pointers (uInt *dictLength, unsigned *pending, int *bits). The translation does not model these cells as memory: each function takes only the fact that a pointer is NULL or not, and returns the values. So the goals say nothing about the address of a result cell, and a cell that overlaps another object cannot be expressed.

Safety goal

ZlibF.Spec.Public.Goal.deflateBound_z_safety

State: done · Status of the results

/-- `z_size_t deflateBound_z(z_streamp strm, z_size_t sourceLen)`.
**Safety of `deflateBound_z`**: a `NULL` or inconsistent stream (`RefusedDeflate`) gets the
conservative bound of a `NULL` stream (not an error, as in the C) and nothing changes; and on every
reachable deflate stream, with the caller's arguments as `zlib.h` asks, the call is safe
(`StreamCallSafe`). -/
def Goal.deflateBound_z_safety : Prop :=
  (∀ h p n, RefusedDeflate h p → ∃ v, C.run (Zlib.Deflate.deflateBound_z p n) h = .ok (v, h) ∧
    C.run (Zlib.Deflate.deflateBound_z none n) h = .ok (v, h)) ∧
  (∀ h r sourceLen,
     StreamCallDomain .deflate h r (.deflateBound_z (some r) sourceLen) →
     StreamCallSafe .deflate h r (.deflateBound_z (some r) sourceLen))
Related definitions and source ↗

Functional contract (beyond safety)

ZlibF.Spec.Public.Goal.deflateBound_z

State: not done, not planned · Status of the results

/-- `z_size_t deflateBound_z(z_streamp strm, z_size_t sourceLen)`.
The mathematical bound includes the entire gzip header, with saturation instead of overflow.
The known extra-length arithmetic issue remains an implementation proof blocker. -/
def Goal.deflateBound_z : Prop := DeflateBoundContract Zlib.Deflate.deflateBound_z
Related definitions and source ↗
ZLIB × LEAN

Contents

READING NOWdeflateBound_z