Skip to content
REFERENCE / ZLIB × LEAN

deflate

Accept input and deliver part or all of a valid compressed stream.

Full chapter and shared rules ↗
int ZEXPORT deflate(z_streamp strm, int flush);

Accept input and deliver part or all of a valid compressed stream.

flush says how far the caller wants the call to go: an ordinary call lets the compressor choose when to emit output, a flush request establishes the chosen boundary, and Z_FINISH asks to end the whole stream. A request does not enlarge a limited output buffer: when the room is used up, take the output and continue by the protocol below.

Return values and next calls

Return type. int — zlib status code

The result separates continuation, completion of the whole compressed stream, and refusal or inability to progress. Updated pointers and counts show this call’s consumed and delivered bytes.

deflate()
Returned value Meaning and conditions Caller’s next step
Z_OK
Continuation may be needed
The call has not reported whole-stream completion. It may have consumed input or delivered header, data, flush-marker or trailer bytes; full output can leave unconsumed input or pending output. Collect output and use updated counts; replenish full output, keeping the same flush during a flush. Once finishing begins, add no input and continue only with Z_FINISH until Z_STREAM_END.
Z_STREAM_END
Complete compressed stream delivered
Only with Z_FINISH, all supplied input and all compressed output, including the wrapper trailer, have been delivered. Retain final output; call deflateEnd to release state, or deflateReset for a new stream. This result itself does not free state.
Z_BUF_ERROR
No output room
Initial checks pass but avail_out is 0; no input is consumed or output delivered, and the existing live stream is retained. Supply valid nonempty output room; keep the same flush during a flush and use only Z_FINISH during finishing.
Z_BUF_ERROR
Cannot progress now
No input or pending output is available, and no stronger flush is requested; the current non-Z_FINISH call cannot progress. Wait for input, or request a stronger legal flush when the application needs it; do not loop unchanged. The stream remains live.
Z_BUF_ERROR
Input offered after final processing
New input is supplied after final-block processing began; none of it is accepted, though old pending output may be delivered before refusal. The live stream is retained. Collect any delivered output and keep unaccepted input for another task; offer no further input to this stream, and finish with Z_FINISH or legally reset/end.
Z_STREAM_ERROR
Stream or call arguments refused
The stream check fails, flush is invalid (including Z_TREES), next_out is NULL, nonzero input has NULL next_in, or a non-Z_FINISH flush is used after finishing began. Initial refusal consumes and delivers no bytes. Establish that the stream is live and correct buffers or flush; after finishing begins use only Z_FINISH. A failed stream check does not guarantee that an arbitrary state can be retried or ended.

Reading the result.

  • A completed nonterminal flush still returns Z_OK, not stream completion; use output room and the flush protocol to determine boundary completion.

Calling conditions and effects

Domain Restricted domain. Effect: consume input, emit output and update progress.

Pre live stream with valid buffers and any active header. next_out is non-NULL and avail_out > 0; next_in may be NULL only with zero input. flush is Z_NO_FLUSH, Z_PARTIAL_FLUSH, Z_SYNC_FLUSH, Z_FULL_FLUSH, Z_FINISH or Z_BLOCK. If output fills during a flush, continue with the same flush and more room. After finishing begins, supply no new input and continue only with Z_FINISH. For ordinary format validity, begin from init/deflateReset (or a copy of that history), use legal dictionary/header setup, standard tuning and no arbitrary priming.

Proof goals.

  • Goal. Goal.deflate_safety (Safety/Streams.lean); required. Theorem: ZlibF.Spec.Public.StreamCallSafetyProof.deflate_safety (public-stream-call-safety.lean). The goal has two clauses: the refusal of a refused stream, and one call on a reachable stream. Goal.deflate_refusal (Safety/Refusals.lean), also required, states the same refusal.
  • 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. next_in is NULL or points to avail_in readable bytes, and next_out is NULL or points to avail_out writable bytes; neither range lies in the stream's own blocks, and the two ranges do not overlap (StreamBuffers);
    4. while the gzip header is being written (stream status GZIP_STATE to HCRC_STATE) and a header record was given to deflateSetHeader: 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; a non-NULL name or comment is a NUL-terminated string (HeaderMemory);
    5. the caller has kept what is already written: the field being written (extra, name or comment) still covers the part already written, and was not set to NULL after part of it was written (DeflateHeaderProgress);
    6. while the header is being written: the input range, the output range, extra (extra_len mod 2^16 bytes), name and comment (each through its NUL) do not overlap one another, and extra, name and comment lie outside the stream's own blocks (DeflateHeaderApart). Conditions 4 to 6 together are ActiveHeader.
  • Covered without condition. Every flush value, also one that is not a flush code; every sequence of input bytes. Every reachable stream, in every phase: before the first deflate, mid-stream, while finishing, and after Z_STREAM_END. The goal is wider than Pre: next_out may be NULL, avail_out may be zero, next_in may be NULL with a nonzero avail_in, and flush may be any int. The C refuses or reports these cases (return table above). 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 Z_STREAM_ERROR. 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, the stream's own blocks and the avail_out bytes at next_out.
    • 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). Which code is returned and which bytes are written: functional goal Goal.deflate (not planned; a theorem proves it).
Complete return conditions and boundaries

Post used is the number of input bytes this call consumes and made the number of output bytes it delivers; old avail_in and old avail_out are the input count and the output room given before the call. Then used <= old avail_in and made <= old avail_out. Pointers advance by those amounts, available counts fall by them, and totals increase by them with unsigned wrapping. Input stays unchanged; output outside the delivered prefix stays unchanged. Some input can remain when output fills. No allocation or free occurs.

Across calls, delivered bytes form a prefix of a valid encoding of accepted input, using the chosen wrapper, settings and preset dictionary. Completed output decodes to that input. This specifies valid output, not one unique compressed byte sequence. Once the header has been written, adler tracks the accepted input, with Adler-32 for zlib and CRC-32 for gzip; raw has no input checksum.

Z_OK means continuation may be needed. Z_STREAM_END occurs only with Z_FINISH, after all supplied input and all compressed output, including trailer, have been delivered. The live state remains owned until deflateEnd or reusable via deflateReset.

When a requested flush is fully delivered, Z_BLOCK completes a block without byte padding; Z_PARTIAL_FLUSH adds an empty fixed block; Z_SYNC_FLUSH makes all preceding input available to a decoder and ends with an aligned empty stored block. Z_FULL_FLUSH also resets match history: later blocks do not refer before that completed flush. Restarting a raw decoder there requires retaining the exact boundary and delivering the entire flush marker first. Z_FINISH closes the final block and writes the wrapper trailer.

Errors Z_BUF_ERROR covers zero output room, no possible progress with no input and no stronger flush, or input offered after final-block processing began. It preserves a live stream; provide room/input as appropriate. Z_STREAM_ERROR covers the stream check, invalid flush (including Z_TREES), invalid NULL I/O combinations, or non-finish flush after finishing began. Initial argument refusals consume no input or output. A later Z_BUF_ERROR for new input after finishing may first deliver old pending output; no new input is accepted. msg and remembered flush can change. The safety goal and the functional goal both include all signed flush values and these refusals.

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.deflate_safety

State: done · Status of the results

/-- `int deflate(z_streamp strm, int flush)`.
**Safety of `deflate`**: a `NULL` or inconsistent stream (`RefusedDeflate`) is refused with
`Z_STREAM_ERROR` and nothing changed; and on every reachable deflate stream, with the caller's
arguments as `zlib.h` asks, the call is safe (`StreamCallSafe`). -/
def Goal.deflate_safety : Prop :=
  (∀ h p flush, RefusedDeflate h p →
    C.run (Zlib.Deflate.deflate p flush) h = .ok (Z_STREAM_ERROR, h)) ∧
  (∀ h r flush,
     StreamCallDomain .deflate h r (.deflate (some r) flush) →
     StreamCallSafe .deflate h r (.deflate (some r) flush))
Related definitions and source ↗

Functional contract (beyond safety)

ZlibF.Spec.Public.Goal.deflate

State: done · Status of the results

/-- `int deflate(z_streamp strm, int flush)`.
Preserve the live stream and its five allocations. Account for exactly the bytes accepted
and delivered, including progress on a full output buffer and clean parameter refusals.
`Z_BUF_ERROR` is characterized exactly (`zlib.h`: no progress was possible): no output space;
or no input, nothing pending and a flush that repeats or weakens the previous one, other than
`Z_FINISH`; or new input after the first `Z_FINISH`. Only in the last case can the call still
deliver pending output before it refuses. A `Z_FINISH` call with output space, no new input
after the first `Z_FINISH`, and no refusal, ends the stream or makes progress. Success keeps
`msg`; an error sets it to the error's text. `data_type` changes only from `Z_UNKNOWN` to a guess.
The sequence target states valid encoding, flush points and completion. -/
def Goal.deflate : Prop :=
  ∀ h r i z s flush,
    StreamReachable .deflate h r → Zlib.Deflate.Spec.DGood h r i z s →
    StreamBuffers h r → ActiveHeader h r →
    ∃ rc after z' s' used out,
      C.run (Zlib.Deflate.deflate (some r) flush) h = .ok (rc, after) ∧
      Zlib.Deflate.Spec.DGood after r i z' s' ∧ StreamAccounting z z' used out.length ∧
      Bytes after z.next_out out.length out ∧
      z'.total_in = z.total_in + UInt64.ofNat used ∧
      z'.total_out = z.total_out + UInt64.ofNat out.length ∧
      (rc = Z_OK ∨ rc = Z_STREAM_END ∨ rc = Z_STREAM_ERROR ∨ rc = Z_BUF_ERROR) ∧
      (rc = Z_STREAM_ERROR ↔ DeflateRefuses z s flush) ∧
      (flush.toInt < 0 ∨ 5 < flush.toInt → rc = Z_STREAM_ERROR ∧ after = h) ∧
      (rc = Z_STREAM_END → flush = Z_FINISH ∧ s'.status = FINISH_STATE ∧
        z'.avail_in = 0 ∧ s'.pending = 0 ∧ s'.bi_valid = 0) ∧
      (rc = Z_BUF_ERROR → used = 0 ∧
        (out = [] ∨ (s.status = FINISH_STATE ∧ z.avail_in ≠ 0))) ∧
      (¬ DeflateRefuses z s flush → z.avail_out = 0 → rc = Z_BUF_ERROR) ∧
      (¬ DeflateRefuses z s flush → z.avail_out ≠ 0 →
        ¬ (s.status = FINISH_STATE ∧ z.avail_in ≠ 0) →
        (rc = Z_BUF_ERROR ↔ z.avail_in = 0 ∧ s.pending = 0 ∧ flush ≠ Z_FINISH ∧
          deflateRank flush ≤ deflateRank s.last_flush)) ∧
      (flush = Z_FINISH → ¬ DeflateRefuses z s flush → z.avail_out ≠ 0 →
        ¬ (s.status = FINISH_STATE ∧ z.avail_in ≠ 0) →
        rc = Z_STREAM_END ∨ used ≠ 0 ∨ out ≠ []) ∧
      (rc = Z_OK ∨ rc = Z_STREAM_END → z'.msg = z.msg) ∧
      (rc = Z_BUF_ERROR → StaticString after z'.msg (errorText Z_BUF_ERROR.toInt)) ∧
      (rc = Z_STREAM_ERROR → 0 ≤ flush.toInt → flush.toInt ≤ 5 →
        StaticString after z'.msg (errorText Z_STREAM_ERROR.toInt)) ∧
      (z'.data_type = z.data_type ∨
        (z.data_type = Z_UNKNOWN ∧ (z'.data_type = Z_BINARY ∨ z'.data_type = Z_TEXT))) ∧
      BufferFrame h after (fun b => StreamRoot r b ∨ DeflateOwned i s b) [⟨z.next_out, out.length⟩] ∧
      LiveChange h after (fun _ => False) (fun _ => False) ∧ after.nalloc = h.nalloc
Related definitions and source ↗
ZLIB × LEAN

Contents

READING NOWdeflate