Skip to content
REFERENCE / ZLIB × LEAN

Proof details

Start with an engine’s full argument, then follow lookup, copying, coding, and memory components in detail. Each route connects to concrete function contracts and definitions.

inflate.c

Decompression engine

Window contents, actual modes, supporting bits, lookup, exits, and call sequences.

Full proof details →Public contract and exact target →
deflate.c

Compression engine

Windows, hash chains, matching, strategy loops, symbol ledgers, block output, and the default wrapper.

Full proof details →Public contract and exact target →

Statements of the goals for call sequences, refusals, satisfiable premises and the round trip →

Reading the actual proofs

Follow key lemmas in implementation order. Read the problem and premises for each step, then open its derivation. Whole-interface proofs connect these steps.

inflate

  1. Initialization domain

    What state does initialization actually create? Expands the actual inflateInit2_ call to establish InflateInitContract at every accepted window parameter. Version/size refusals, a null stream, allocation success, and allocation failure are included.

    Fresh means future allocation identities are unused; Uniq means existing object identities do not conflict. Explicitly requires Api.inflWbits to accept the parameter. Invalid window arguments are excluded, so this is not the unrestricted Goal.inflateInit2_. The contract retains its version-value, caller-storage, Fresh/Uniq, and default-or-null allocator conditions.inflate_init2_valid_public
  2. Fixed-table installation

    After reading a fixed-block header, the decoder must install the format’s actual tables. The actual fixed-block TYPEDO tail enters LEN_ and establishes DataTableInvariant on the returned heap. Fixed pointers are connected to the actual static arrays.

    Env describes the execution environment and LibraryGlobals its static library data. Requires Env, LibraryGlobals, low hold bits selecting a fixed block, and flush different from Z_TREES. This covers that installation branch; dynamic installation, preservation through all histories, and the whole public inflate call do not follow from it alone.typedoTail_fixed_tableInvariant
  3. Dynamic-table contents

    The dynamic-block lengths must become entries the decoder can actually read. Actual inflate_table execution yields both the original safety/return classification and TableConstruction. Successful runs retain canonical leaves, links, and returned extents; empty tables, singleton tables, and constructor error returns are included.

    CallPre describes the internal call’s readable length input, writable table capacities, separation, and other internal call conditions. It does not relate the constructed contents to the predicates the decoder uses or to the actual call state; it is not whole-stream decoding correctness.inflate_table_construction
  4. Mode loop and termination

    The main loop changes between bit reading, table lookup, and copying. Shows that the actual endless-condition dispatch loop exits without a runtime fault while preserving DefaultStateJ, the remaining input view, and exact input/output cursors and counts. Its rank reads the actual heap mode and fits the real fuel bound.

    DefaultStateJ relates actual fields to a usable decoding state; DispatchBuffers describes this internal call’s buffers. Requires Env, DefaultStateJ, DispatchBuffers, the local-header condition HeaderLocal, and at most 39 incoming buffered bits. The theorem does not include the complete public entry domain, leave path, or ownership postcondition.inflate_default_view_loop
  5. Preserving fixed stream fields

    Processing changes cursors, but should retain stream identity and allocation configuration. Establishes preservation of fixed stream fields through entry normalization, LOAD, and the complete mode loop: the state root, allocator/free functions, opaque argument, and reserved field are preserved. Callee preservation results concern their actual translated bodies.

    Requires context.strm to identify the stream. StreamFrameX is conditional on an already successful execution equation and states fixed-field preservation only. By itself it does not establish execution existence, termination, fault freedom, or correct output.streamFrameX_inflate_run
  6. State and window release

    End must release the stream’s state and history without changing unrelated caller objects. The actual end execution for Goal.inflateEnd returns Z_OK, clears the stream's state pointer, removes live blocks exactly according to InflateOwned, and supplies the unrelated-object Frame and unchanged allocation counters.

    Good is the state-validity condition used by this entry. Goal.inflateEnd explicitly requires Good and the default zcfree. This theorem uses that state condition; it does not independently establish Good for every public call history.inflate_end_public
  7. Rebuffering and history

    Replacing a buffer should continue the same decoding task. The public Rebuffer relation permits caller-buffer replacement while retaining the exact decoder state and DefaultDecodeJ, including its table, pending-work, and window clauses. It does not assume equal old and new caller-buffer contents.

    Rebuffer describes the permitted caller-buffer replacement; DefaultDecodeJ records the retained decoding state. Requires an existing DefaultDecodeJ, a legal Rebuffer, and explicit ByteObjectsFit platform scope for the new heap. It covers this history operation only; initialization, other auxiliary operations, and the complete call sequence are outside this theorem.rebuffer_default_J

deflate

  1. Default initialization and allocation failure

    Initialization must create a usable compressor or clean up a failed allocation attempt. Expands the fixed-parameter deflateInit_ call to establish Goal.deflateInit_: arbitrary level arguments, version and parameter refusals, five allocation outcomes, failure cleanup, ownership, and the initialized invariant are included.

    Fresh and Uniq protect allocation identities and existing object representations. The public contract retains Fresh, Uniq, library globals, caller storage, version, and default-or-null allocator premises. Window 15, memory level 8, and strategy 0 are fixed; the general Goal.deflateInit2_ is neither assumed nor established.deflateInit_proof
  2. Initial engine invariant

    Zero-initialized fields must suffice for the first engine step. Successful default initialization establishes EngineStart on a reachable heap, including initial chains over the actual window/hash arrays, zero counters and cursor state, while preserving caller input/output bindings. DGood and the chain invariant are not supplied by the caller.

    EngineStart is the initial engine relation. Requires legal default parameters, caller storage, Fresh/Uniq/LibraryGlobals, default-or-null allocators, and success of all five allocation requests. This is the first engine entry; later nonempty chains, nonzero counters, and other histories are outside this theorem.default_initialization_engine_bindings
  3. Window refill and hash priming

    Refill changes the window bytes and the index used to search them. Gives the exact returned heap of a resumed fill_window call, preserving DGood and HeapChains while establishing the high-water initialized range and, when enough lookahead exists, the rolling-hash content relation.

    DGood is compressor-state validity and HeapChains relates the hash links to retained bytes. Covers the no-slide branch with zero insert, zlib wrap 1, lookahead below 262, and nonempty input. Actual window/input views, bounds, and copy separation are required; sliding and pending-string insertion are not covered by this single theorem.fill_window_resume_complete
  4. Match search and decisions

    A search decision must leave a valid boundary for the next strategy step. Actual search and its subsequent decisions restore StrategyBoundary, advance strstart, decrease lookahead, and retain the endpoint, caller buffers, and exact output accounting. Stored/fixed/dynamic output paths on a full symbol buffer are included.

    StrategyBoundary records that boundary, EndFrontier the input endpoint, and StreamBuffers the caller buffers. Requires StrategyBoundary, EndFrontier, StreamBuffers, a positive compression level, nonempty lookahead, and match-comparison room. lit_bufsize is fixed at 16384, output is a raw array, and PublishReady is already available. This is the post-refill suffix, not refill execution.slow_search_decision_ready_boundary
  5. Partial output and retained bits

    After partial delivery, written bytes and retained bits must still join to the original sequence. The actual low-bit flush_pending path publishes min(pending, avail_out) bytes while preserving DGood, exact accounting, and storage relations. Written-byte bits followed by remaining PendingBits equal the writer's original bit sequence.

    TreesInvAt is the tree-state relation; pending counts complete bytes awaiting delivery. Requires TreesInvAt, fewer than eight buffered bits, the base pending cursor, a valid writable output range, and distinct raw output/pending objects. Capacity may be zero. This low-bit branch does not replace general bit flushing or the broader public buffer domain.flush_pending_low_raw_bits_storage
ZLIB × LEAN

Contents

READING NOWProof details