Obligations at internal calls
This page describes, in words, what the main internal helpers of the default build need from
the function that calls them and what they deliver. A helper is a function that zlib.h does
not declare, such as inflate_table or longest_match. The page is a reading aid for the
proofs of the public functions. It is not a list of theorems, and no proof assumes a row.
What is proved. Each row is a reading of the C, not yet confirmed unless the proof guide of its
section names a theorem for it. What is proved about the helpers follows from the public
goals: the safety goals of inflate, deflate and the other public functions are done
(progress), and each is about the whole translated body, helper calls
included. So every helper call that a public call makes returns without a fault. A row's own
wording, for example an exact postcondition, is not thereby a theorem. The
proof guides list the theorems about each helper.
What a row is needed for. The required result is safety. A row matters as far as the
safety proof of a public caller uses it: bounds, termination, frames, and the facts those rest
on. A Post that only describes content, such as I-it-canonical or I-uw-content, is a
functional fact. It is in scope only where a safety proof depends on it.
No hidden restriction on callers. The precondition of a helper can be stronger than the precondition of the public function that reaches it. The proof of the public function derives it from the invariant that init established and from the state at the call. It is never passed on to the application. In particular the public proofs cover small memory levels, arbitrary contents of fresh integer memory, and the documented error cases.
How to read the entries
Each identifier I-* names one obligation, so that the proof guides can cite it.
| Label | Meaning |
|---|---|
Pre |
What holds when the helper is called. |
Post |
What holds when it returns. |
Effects |
What it may read or write. |
Intermediate |
A fact that holds at a named point inside the helper, before the C reuses the same fields for another purpose. |
Every entry also includes the common memory facts: the storage it uses is live, represented
as the entry says and in bounds; writes go to writable storage; memcpy ranges do not
overlap; a pointer field was written before it is read. For each helper the proof of its
caller shows termination, no fault, and that storage outside Effects is unchanged.
In the diagram an arrow from A to B means that B uses data that A builds or maintains. It is not a complete C call graph.
flowchart TD
IT["inflate_table: construct bounded tables"] --> IF["inflate_fast: consume tables and history"]
UW["updatewindow: maintain history ring"] --> IF
HC["hash updates: maintain reachable chains"] --> LM["longest_match: bounded search"]
HC --> FW["fill_window: slide and refill"]
FW --> LM
BT["build_tree → gen_bitlen → gen_codes"] --> CB["compress_block: emit symbols"]
CB --> PB["pending bytes and buffered bits"]
PB --> FP["flush_pending: copy to caller"]
Construct decode tables: inflate_table
Purpose: turn the code length of each symbol into a table that decodes a symbol by lookup.
type selects one of three alphabets: code lengths (CODES), literal/length (LENS) or
distance (DISTS). codes is the number of symbols, and lens holds their code lengths in
bits. bits is the number of bits one lookup in the root table examines. table is where
entries are written, and work is a temporary array used for sorting. Array capacities here
count entries, not bytes.
Call: inflate_table(type, lens, codes, &table, &bits, work); base is the value of *table
at entry. Proof guide: inftrees.
| Part / ID | Contract |
|---|---|
Pre I-it-pre-lens |
lens[0..codes) is readable, with lengths in 0..15. For CODES, lengths are at most 7 and the requested *bits is at least 7. |
Pre I-it-pre-codes |
type is CODES, LENS or DISTS; codes is at most 19, 288 or 32, respectively. |
Pre I-it-pre-work |
work[0..codes) is writable scratch, disjoint from other arguments. |
Pre I-it-pre-table |
table/bits are writable cells; base holds 128/852/592 entries for CODES/LENS/DISTS, disjoint from other arguments. |
Post I-it-ret |
Returns 0 on success, -1 for invalid lengths, or 1 for a LENS/DISTS capacity refusal. Empty codes succeed with invalid entries. |
Effects I-it-writes |
Changes only scratch, pointer/width cells and in-capacity table entries. Success constructs [base, base + used); errors may leave partial writes. |
Post I-it-advance |
On success, *table = base + used and *bits is the actual root width. |
Post I-it-complete |
Success writes every constructed entry, including an invalid entry for a permitted one-symbol code, or two invalid entries for an empty code. |
Post I-it-links |
Every successful root link and its entire sub-table lie in [base, base + used). |
Post I-it-canonical |
Success decodes the canonical assignment, with invalid markers for reserved symbols. |
Post I-it-term |
The call ends under the stated domain. |
Decode with margins: inflate_fast
Purpose: decode many symbols at once while the caller has left enough input and output, until
room is low, a block ends or the data is invalid. avail_in and avail_out count the
remaining input and output bytes; start is the output room the outer inflate call began
with. hold holds the bits that were read and not yet used, and bits counts them. The
window that keeps the history has wsize bytes, of which whave are valid; wnext is the
index of the next write.
Proof guide: inffast.
| Part / ID | Contract |
|---|---|
Pre I-if-pre-room |
Mode is LEN; avail_in ≥ 6, avail_out ≥ 258, start ≥ avail_out. next_out - (start - avail_out) begins readable earlier output of the outer inflate call, in the same object. Input/output are disjoint. |
Pre I-if-pre-bits |
bits < 8; hold contains exactly those buffered low bits and no other set bits. |
Pre I-if-pre-tables |
lencode/distcode and root widths satisfy successful-table entry/link rules, including fixed tables. |
Pre I-if-pre-window |
whave ≤ wsize; wsize = 0 implies whave = wnext = 0; otherwise wnext < wsize and window holds wsize bytes. Its valid history has whave bytes; sane is set. |
Effects I-if-reads |
Byte reads use entry input, prior outer-call output or valid window history; table reads stay in the decoding tables. |
Effects I-if-writes |
Writes only entry output, stream cursors/counts/msg and state hold/bits/mode; no allocation. |
Post I-if-post |
Cursors/counts record consumed input/output. Whole unused input bytes are returned; bits < 8. Mode is LEN, TYPE or BAD; BAD may consume a partial invalid symbol. |
Post I-if-dist |
A distance beyond the bytes produced by the outer inflate call plus whave sets BAD before copying that match. |
Preserve decoder history: updatewindow
Purpose: append newly produced output, or dictionary bytes, to the history, so that later
back-references can be copied. end points to the end of the segment and copy is its
length, so the segment is [end - copy, end). The configured exponent wbits gives a window
of 2^wbits bytes; whave is the length of the valid history, and wnext marks where the
last write into the ring ended.
Proof guide: inflate.
| Part / ID | Contract |
|---|---|
Pre I-uw-pre |
All four hold: 1. [end - copy, end) is readable and disjoint from the destination window.2. wbits is in the configured inflate range.3. An existing window has 2^wbits writable bytes.4. The ring is unused ( wsize = 0), or it has wsize = 2^wbits, whave ≤ wsize, wnext < wsize, and whave < wsize → wnext = whave. |
Effects I-uw-alloc |
Allocates only an absent window. Returns 1 on allocation failure, else 0. Writes only window storage/fields and allocator state; failure preserves existing history. |
Post I-uw-inv |
On return 0, wsize = 2^wbits, whave ≤ wsize, wnext < wsize, and whave < wsize → wnext = whave. |
Post I-uw-content |
Success keeps the suffix, at most wsize bytes, of old history concatenated with input; whave counts it and ring order ends at wnext. |
Refill and slide: fill_window, slide_hash, read_buf
Purpose: refill the input not yet processed, and keep its position relative to the processed
history. w_size is the configured window size; the byte array has window_size bytes,
normally twice that. strstart is the array index of the next byte to process, and
lookahead is the number of bytes read from there on and not yet processed. MIN_LOOKAHEAD
is the 262 bytes the compressor normally wants ready. insert counts the positions that
still need a hash entry. A slide changes these array indices, not the input bytes they refer
to.
Proof guide: deflate.
| Part / ID | Contract |
|---|---|
Pre I-fw-pre |
fill_window has lookahead < MIN_LOOKAHEAD, window_size = 2*w_size, strstart + lookahead ≤ window_size, and insert ≤ strstart. Window, hash sizes/masks, high-water mark, search settings and position ranges satisfy the configured deflate state, including I-hc-inv. Input has a readable avail_in view. |
Post I-fw-post-room |
fill_window leaves strstart ≤ window_size - MIN_LOOKAHEAD. |
Post I-fw-post-lookahead |
It leaves lookahead ≥ MIN_LOOKAHEAD or avail_in = 0. Newly read bytes extend the current lookahead in order. |
Effects I-fw-slide |
Sliding moves live upper-window bytes down by w_size, adjusts positions/insert with C arithmetic and calls slide_hash. Other writes are input/checksum accounting, hashes and high-water padding. |
Pre / Post I-sh-total |
slide_hash requires positive hash_size and w_size, and writable head[0..hash_size)/prev[0..w_size). Each entry becomes m - w_size if m ≥ w_size, else NIL; it sets slid = 1. Unreachable prev values need not be initialised. |
Pre / Post I-rb-copy |
read_buf needs a writable destination for n = min(avail_in, size) bytes, disjoint from input. It returns n, copies that prefix, advances next_in, reduces avail_in, adds to total_in, and updates Adler-32/CRC-32 for the active wrapper. For n = 0, it changes nothing. |
Search valid hash chains: longest_match
Purpose: follow the chain of candidates in one hash bucket of three-byte strings to find a
repetition, with a bound on the comparison work. cur_match is the array index of the
current candidate; strstart is the current input position, and their difference is the
match distance. MAX_DIST = w_size - 262 is the farthest distance this implementation
searches, and MAX_MATCH = 258 is the most bytes one match copies. prev_length is the
length a candidate has to improve on. head holds the start of each bucket's chain, prev
links a candidate to an earlier position, and NIL ends a chain.
Proof guide: deflate.
| Part / ID | Contract |
|---|---|
Pre / Post I-hc-inv |
INSERT_STRING, slide_hash, CLEAR_HASH, fill_window and deflateSetDictionary maintain heads naming inserted positions and reachable prev[p mod w_size] slots written with NIL or smaller same-hash positions. Positions agree with current window/lookahead. |
Pre I-lm-pre |
cur_match is a nonzero head for the current string's hash, cur_match < strstart, and distance is at most MAX_DIST. I-hc-inv holds; strstart ≤ window_size - MIN_LOOKAHEAD, and 1 ≤ prev_length ≤ MAX_MATCH. There is no premise on the chain budget: deflateTune accepts max_chain_length = 0. |
Effects I-lm-reads |
Reads window through strstart + MAX_MATCH inclusive, possibly past lookahead, and written reachable prev slots. Only match_start changes. The padding bytes past the lookahead never make a match valid. |
Post I-lm-ret |
Returns at most min(MAX_MATCH, lookahead). Improvement sets a valid match_start; otherwise it may retain prev_length, capped by lookahead, without a new match_start guarantee. |
Post I-lm-term |
Ends because the traversed positions strictly decrease: the proof of the loop (lm_loop_ok, deflate.c.engine.lmmain.lean) uses cur_match as its measure, for any chain budget. The budget can end the walk earlier, but termination does not rest on it: with a budget of 0, --chain_length wraps to a large value. No global maximum is promised. |
Construct and emit Huffman trees: trees.c
Purpose: build Huffman codes within the length limit from the symbol frequencies, then write
the symbols as a compressed block. A descriptor selects the literal/length tree, the distance
tree or the code-length tree. bl_count[l] is the number of symbols whose code has l bits,
and max_length is the longest code that kind of tree allows. In the output phase sym_next
counts bytes, at three bytes per recorded symbol, and pending counts the compressed bytes
produced and not yet handed over.
Proof guide: trees.
| Part / ID | Contract |
|---|---|
Pre I-bt-pre |
build_tree receives a descriptor for 286/30/19 literal-length/distance/bit-length leaves, set frequencies and room for internal nodes/heap/depth. Frequency sums after forced-leaf repair fit their fields. |
Effects I-bt-heap |
Heap indices stay below 573; nodes stay in their tree. Writes: descriptor maximum, nodes, heap/depth, bit counts and costs. |
Intermediate I-bt-forest |
Before lengths/codes overwrite parent/frequency fields, nodes form a full binary tree over positive-frequency symbols, with forced leaves to reach two. Parent frequencies sum child frequencies. |
Pre / Post I-gb-len |
Given that tree, ordered heap and descriptor, gen_bitlen writes active leaf lengths in 1..max_length (15 or 7), Kraft sum 1, counts and costs. |
Post I-gb-count |
bl_count[l] counts active leaves of length l; bl_count[0] = 0. |
Pre / Post I-gc-code |
gen_codes needs lengths in 0..15 through max_code and matching complete-code counts. It writes only positive-length code fields: bit-reversed canonical words in symbol order. |
Pre / Effects I-cb-reads |
compress_block requires complete three-byte symbols in sym_buf[0..sym_next), valid literal/match ranges, matching trees with usable codes, and pending/bit-buffer room. It reads symbols in order and emits their codes/extra bits followed by END_BLOCK. |
Post I-cb-pending |
After symbol k (from 0), pending < lit_bufsize + 3*(k+1). Emission also leaves every unread symbol intact. Callers do not supply this bound; it is a property of compress_block itself. |
Pre I-tf-choice |
_tr_flush_block requires valid block symbols/frequencies, last in 0..1 and pending capacity. For a block that will be stored it also requires stored_len ≤ 65535 and readable buf[0..stored_len). |
Post I-tf-choice (the choice) |
It chooses stored if buf != NULL and stored_len + 4 ≤ opt_lenb; otherwise fixed if static_lenb = opt_lenb; otherwise dynamic. opt_lenb is the smaller of the two compressed sizes, each rounded up to bytes, except that the Z_FIXED strategy selects the fixed size first. At level 0 no trees are built and opt_lenb = static_lenb = stored_len + 5, which forces a stored block. |
Effects I-tf-choice |
It resets the block accounting, and aligns the bit buffer to a byte if last. |
The symbol buffer sym_buf shares its storage with the pending output buffer pending_buf:
this is the overlay. I-cb-pending is the bound that keeps output from overwriting symbols
not yet read. The trees guide lists the theorems that give it for every
memory level a caller may pass, so it does not restrict callers.
Drain pending output: flush_pending and bit writers
Purpose: first turn the buffered bits that make whole bytes into bytes, then hand the pending
bytes to the caller. bi_buf is the bit register that holds code words, and bi_valid is the
number of valid bits in it. pending_buf is the internal byte array, pending_out points to
the next bytes to hand over, and pending is their count. avail_out is the room the caller
still offers in this call; it is a different count.
| Part / ID | Contract |
|---|---|
Pre / Post I-fp-inv |
pending_out lies in the pending allocation and pending_out + pending ≤ pending_buf + pending_buf_size. This interval condition alone does not give the writers room: each writer needs room at the offset it writes to. |
Pre / Post I-fp-copy |
flush_pending requires writable avail_out output disjoint from pending storage and valid bit-buffer state with room for _tr_flush_bits. It first flushes whole buffered bytes, then copies n = min(pending, avail_out), advances both cursors, adds to total_out, and subtracts from both counts. After a nonzero copy empties pending, pending_out = pending_buf. Only pending/bit fields, stream output fields and the copied output bytes change. |
Pre / Post I-pb-room |
put_byte and put_short require one/two writable bytes at their pending offsets. send_bits requires 1 ≤ length ≤ 16, a value fitting that length, valid bi_valid/bi_buf, and room for a possible short write. They append bytes/bits without checking capacity, so room is a fact their callers hold; in the overlay, I-cb-pending gives it. |
The translation rules explain the operations these obligations refer to. The API model explains how byte histories differ from concrete heap effects.