Trees and block output: why a block flush is safe
Source: zlib/trees.c, with the symbol layout in zlib/deflate.h.
Translation: ZlibF/Zlib/trees.c.lean.
When deflate closes a block it calls _tr_flush_block. That function builds two Huffman
trees from the recorded symbols, picks the cheapest of three block forms, and writes the block.
It writes into the same buffer from which it is still reading the symbols. This page explains
why every array access of tree construction is in range, and why the output never overwrites a
symbol that has not been read yet. The second fact, F9, is the hardest step of the whole
deflate proof.
trees.c has no public function. Its theorems serve the safety of deflate
(stream compression). The internal contracts of
this file are I-bt-*, I-gb-*, I-gc-*, I-cb-* and I-tf-* in
internal contracts. Two more groups there concern the block
output. I-pb-room is the room that the bit writers need: put_short and send_bits of this
file, and the macro put_byte of deflate.h. I-fp-* are the contracts of flush_pending,
a function of deflate.c that FLUSH_BLOCK_ONLY calls after _tr_flush_block.
Results
The theorems of the table serve the proof of
Zlib.Deflate.Universal.deflate_sequence_safety, the sequence theorem of deflate.
| Result | Theorem |
|---|---|
FLUSH_BLOCK_ONLY is safe for every block form and every memLevel, given the overlay room of the dynamic form |
flush_block_only_safe, from tr_flush_block_safe |
| The three block forms | stored_block_safe, fixed_block_safe, dynamic_block_safe |
Overlay room F9, B ≥ 2048 (memLevel ≥ 5) |
dynamic_overlay_large |
Overlay room F9, B = 512 and 1024 (memLevel 3 and 4) |
dynamic_overlay_mid |
Overlay room F9, B = 256 and 128 (memLevel 2 and 1) |
tinyOverlayAt_256, tinyOverlayAt_128, tinyOverlay |
gen_bitlen never shortens a code of a tree whose weight is below 1597 |
ws_gen_bitlen_fib_plus |
The heap operations, gen_bitlen, the bit output and the tally |
pqdownheap_safe, pqremove_safe, gen_bitlen_safe, kraft_clamped, send_bits_spec, bi_flush_spec, bi_windup_spec, bi_reverse_safe, init_block_spec, tr_init_spec, tr_tally_spec |
B is lit_bufsize = 2^(memLevel + 6). Because F9 is proved for all nine values of
memLevel, the sequence theorem of deflate has no premise about it.
Functional theorems also exist (gen_bitlen_correct, pqdownheap_correct,
bi_reverse_correct and others: the lengths form a complete prefix code, the bits written are
the ones intended). They are proved, and they are not required for the safety results. No
theorem for every configuration says that the emitted block decodes to the recorded symbols.
For the stream that deflateInit makes at the default level, a completed stream is proved to
be a valid zlib stream for its input; see the round trip.
Assumptions
flush_block_only_safe is a theorem about an internal step of deflate, not about a public
function. Its premises are facts about the compressor state, and the strategies prove them at
every flush from the invariant DInv (stream compression). The
list has every premise of the Lean statement.
- The state is well formed (
DGood,TreesInvAt): array sizes, tree descriptors, the block that holdspending_bufandsym_buf. - The window pointer is the start of a live byte block.
- The level is positive. Level 0 does not build trees.
- H0, the entry accounting.
pending = 0,pending_out = pending_buf, andbi_valid ≤ 7. - The recorded symbols are described by a list (
SymbolLedger):sym_next = 3n, the bytes insym_bufare thensymbols, each has a length byte below 256 and a distance of at most 32768, and the frequencies indyn_ltreeanddyn_dtreecount exactly these symbols. - The cost fields
opt_lenandstatic_lenand the bit-length frequencies are zero (BlockClear). -2^62 ≤ block_start ≤ strstart ≤ window_size. The first bound keeps the block lengthstrstart - block_startinsidelong;block_startcan be negative after a window slide.StreamBuffersholds, andnext_outpoints into a byte block of the heap or into thedeptharray of a deflate state record. These are the two kinds of writable byte storage in the model; the strategies get the premise fromStreamBuffersand anext_outthat is notNULL(output_reference).- The overlay room of the dynamic form (
DynamicOverlay). This premise is a hypothesis, not a fact about sizes. It has these conditions: the trees are built on this state, and building them changes only the tree fields and the two costs; the description of the trees has at most 2283 bits; the bits by which the symbol costs exceed 24 bits a symbol, summed over thenrecorded symbols, satisfy1000 * bitExcess ≤ 6257 * (n + 3); and the costs select the dynamic form. Under them the prepared state has the roomDynamicRoomof fact F9. The three overlay theorems of the Results table prove it for everyB.FlushSafeAt Lis the statement offlush_block_only_safewithout this hypothesis, for the states whoselit_bufsizeisL; it is what the strategies use, each for its own buffer size.
The theorem holds for both values of the argument last.
H0 holds at every flush. bi_valid ≤ 7 is the clause biValid of the invariant: every path
that sends bits ends with bi_flush or bi_windup. pending = 0 is part of the loop state of
each strategy (BlockReady): deflate
calls a strategy only with an empty pending buffer, and after a flush that leaves bytes pending
the strategy returns instead of going on.
What a flush does
flowchart TD
Tally["symbols recorded in sym_buf, frequencies counted"] --> Flush["_tr_flush_block"]
Flush --> Trees["build_tree: literal/length tree, distance tree"]
Trees --> Lengths["gen_bitlen: code lengths, limited to 15"]
Lengths --> Codes["gen_codes: canonical codes"]
Codes --> BitTree["build_bl_tree: code for the code lengths"]
BitTree --> Choose{"cheapest form"}
Choose --> Stored["stored: copy the input bytes"]
Choose --> Fixed["fixed: compress_block with the static trees"]
Choose --> Dynamic["dynamic: send_all_trees, then compress_block"]
Fixed --> Bits["send_bits into pending_buf"]
Dynamic --> Bits
Stored --> Bits
The buffer that send_bits writes is the one compress_block reads:
pending_buf 0 .......... pending ......... B ......... B + 3k ......... B + 3n ...... 4B
| output written | free | symbols read | symbols unread | free |
--> grows --> moves
The "invariant" of this page is the picture: while a block is written, pending stays below
B + 3k, the start of the next unread symbol. Everything else is ordinary array bounds.
Why each step is safe
Building a tree: F7
Let elems be 286, 30 or 19 for the literal/length, distance or bit-length tree.
HEAP_SIZE = 573. The arrays heap, depth and dyn_ltree have 573 entries, dyn_dtree has
61 and bl_tree has 39.
build_tree first puts every symbol with a nonzero frequency on the heap. If fewer than two
are found, it adds symbols with frequency 1 until there are two. So the heap holds N leaves
with 2 ≤ N ≤ elems, at heap[1..N].
pqdownheap(k) reads the left child heap[2k] only when 2k ≤ heap_len and the right child
heap[2k+1] only when 2k < heap_len. Each round moves k to a child, so the loop runs at
most as many times as the heap is deep.
The merge loop takes the two smallest nodes off the heap, stores them at the top of heap, and
puts a new parent node on the heap. After t merges
heap_len = N - t
heap_max = HEAP_SIZE - 2t
A merge happens only while t ≤ N - 2. It writes heap[HEAP_SIZE - 2t - 1] and
heap[HEAP_SIZE - 2t - 2]. These indices are positive and above the active heap:
HEAP_SIZE - 2t - 2 > N - t because N ≤ 286 and t ≤ N - 2
The new node has number at most elems + N - 2 ≤ 2 * elems - 2: 570, 58 or 36. That fits the
tree array (573, 61, 39). The last root write goes to heap[HEAP_SIZE - 2N + 1], an index of
at least 2. These bounds are fact F7 of
the method. pqdownheap_safe and
pqremove_safe cover the heap operations, and ws_build_tree_complete the whole function.
depth is an unsigned char and its increment can wrap. That is defined behaviour and has no
effect on any index. Frequencies of parent nodes are sums of leaf frequencies; a block has
fewer than B ≤ 32768 symbols, so the sums fit in 16 bits.
Limiting the code lengths: F8
gen_bitlen walks the nodes that build_tree stored in heap[heap_max..HEAP_SIZE). A parent
is stored at a smaller index than its children, so the walk meets every parent first. Let L
be the length limit: 15 for the two data trees, 7 for the bit-length tree.
First pass. Each node gets Len = min(Len(parent) + 1, L). overflow counts the nodes,
leaves and inner nodes, whose true depth is greater than L. bl_count[l] counts the leaves
of length l.
The Kraft sum after clamping. In a full binary tree the leaves satisfy Σ 2^-depth = 1.
Take an inner node v at true depth L, with m_v leaves below it. Before clamping those
leaves weigh 2^-L together. After clamping each weighs 2^-L, so together m_v * 2^-L. The
subtree has 2 m_v - 2 nodes below v, all deeper than L. Every node deeper than L lies
under exactly one such v. Summing over all v:
overflow = Σ_v (2 m_v - 2)
Σ_leaves 2^-Len = 1 + (overflow / 2) * 2^-L
So overflow is even (kraft_clamped).
Repair. While overflow > 0 the C does
bits = max_length - 1;
while (s->bl_count[bits] == 0) bits--;
s->bl_count[bits]--; /* one leaf of length bits becomes an inner node ... */
s->bl_count[bits + 1] += 2; /* ... with two leaves below it */
s->bl_count[max_length]--; /* one of them is a leaf moved up from the last level */
overflow -= 2;
One round lowers the Kraft sum by 2^-L and overflow by 2, and keeps the number of leaves
(round_kraft). Two things have to be true for it not to fault.
- F8(i): the downward scan stops at a positive index. Suppose every leaf had length
Lwhileoverflow > 0. The identity would given * 2^-L > 1, son > 2^L. Butn ≤ 286 < 2^15for the data trees andn ≤ 19 < 2^7for the bit-length tree. So some class belowLis not empty (exists_short). - F8(ii):
bl_count[max_length]does not go below zero. At the start it is at leastoverflow / 2 + 1: the leaves under the nodesvnumberΣ m_v = overflow / 2 + (number of such v), and there is at least onev. Each round takes one from it and one fromoverflow / 2. So it is at least 2 at every round.
overflow goes down through even values to 0, and then the Kraft sum is 1.
Second pass. The C hands out the lengths again: bl_count[bits] leaves get length bits,
taken from heap[--h] and skipping inner nodes. There are n leaves among the stored nodes
and Σ bl_count = n, so h does not go below heap_max.
gen_bitlen_safe is the whole function.
Codes and the tree description
gen_codes computes the first code of each length from bl_count and gives each symbol with a
nonzero length the next code of its length, bit-reversed by bi_reverse. The local array
next_code[16] is written at indices 1 to 15 before it is read. bi_reverse is called with a
length between 1 and 15 and loops that many times (bi_reverse_safe).
| Function | Why its accesses are in range |
|---|---|
scan_tree |
It runs on the two data trees. It writes a guard value 0xffff at tree[max_code + 1]; that index is at most 286 or 30, inside the arrays of 573 and 61 entries. Real lengths are 0 to 15 and index bl_tree at 0 to 18; the guard is compared, never used as an index. ws_scan_tree proves that the function returns. It assumes lengths of at most 15 up to max_code and nothing about the entry at max_code + 1. Its conclusion also says that afterwards the tree is the array scGuard: the old array with only the length at max_code + 1 changed, to 0xffff. scGuard_lengths is a lemma about the lengths of that array, not about the function |
build_bl_tree |
It scans bl_order[max_blindex] down from 18 and stops at 3 at the latest |
send_all_trees |
It sends lcodes - 257, dcodes - 1 and blcodes - 4 in 5, 5 and 4 bits, then blcodes ≤ 19 three-bit lengths |
send_tree |
It repeats the scan of scan_tree and reads the same entries, the guard included. send_tree_emit proves that it returns, for lengths of at most 15 up to max_code and any 16-bit value at max_code + 1, given fitted codes for the bit-length symbols that occur and room in pending_buf for the bits |
Bits and pending bytes
send_bits(s, value, length) adds length bits to the 16-bit buffer bi_buf. When the buffer
would overflow it writes two bytes to pending_buf and keeps the rest. It does not check the
room in pending_buf. send_bits_spec assumes 0 ≤ length ≤ 15, a value below 2^length,
and room for the bits; every call in trees.c sends at most 15 bits. With bi_valid ≤ 16 and
length ≤ 15 all shifts are by at most 16 on 32-bit operands.
If S bits were sent from a state with v bits held, then
pending ≤ base + 2 * floor((S + v) / 16)
Equality need not hold at a multiple of 16: the C keeps a full bit buffer until the next write.
With v ≤ 7 this gives pending ≤ base + S / 8 + 1.
compress_block reads the three bytes of symbol k and then sends its code. For a match the
length byte lc ≤ 255 indexes _length_code, and the distance minus one, at most 32767,
indexes _dist_code through
d_code(x) = x < 256 ? _dist_code[x] : _dist_code[256 + (x >> 7)], at most index 511 of 512.
These bounds hold only if the bytes read are the ones recorded. If output had overwritten an
unread symbol, the distance could be any 16-bit value and d_code could index 767. So F9
protects a read of a static table as well as the writes.
The overlay lemma F9
Write B = lit_bufsize. The buffer has 4B bytes. Symbols start at offset B, take three
bytes each, and number n ≤ B - 1. Symbol k is at [B + 3k, B + 3k + 3).
F9. While a block is written, after the header and after each of the first k symbols,
8 * pending + bi_valid + 15 ≤ 8 * (B + 3k) (prefix room)
and when the block is complete, with its end code and the final alignment, it fits in 4B
bytes (block room). The 15 bits of slack cover the bits held in bi_buf and the two-byte step
of send_bits. In Lean this is DynamicRoom for the dynamic form; it is written with the
entry state and the bit costs of the header and of each symbol.
A symbol frees 24 bits of buffer when it is read. So the question is how much more than 24 bits a symbol's code can take, and how many bits the block header takes before the first symbol.
Stored and fixed blocks
A stored block is chosen only when its length plus 4 is at most the cost of the other forms.
Once it is chosen the symbols are not read again, so the copy may overwrite them
(stored_block_safe).
With the fixed codes a literal costs at most 9 bits and a match at most 8 + 5 + 5 + 13 = 31.
The header has 3 bits. From H0, after q symbols
pending ≤ (7 + 3 + 31 q) / 8 + 1
For the smallest buffer, B = 128 with q = 127: pending ≤ 494, and the next symbol starts
at 128 + 3 * 127 = 509. In general the bound is below B + 3q whenever B > 11
(fixed_block_safe).
Dynamic blocks
A dynamic block sends its tree description first, and its codes can be 15 bits long. Comparing the total size with a fixed block is not enough: long codes may come early and short ones late. The proof bounds the whole block instead. Let
header = bits of the tree description
excess = Σ over the symbols of max(0, cost - 24)
Any prefix of k symbols costs at most 24k + excess. With H0 (7 held bits), 3 block-type
bits and the 15 bits of slack, prefix room follows from the budget
header + excess + 25 ≤ 8B
The budget is proved in three ranges of B.
B |
8B |
Proved bound on header + excess |
With the 25 |
|---|---|---|---|
| 2048 and above | 16384 and above | 2283 + 6.257 (B + 2), which is 15110 at B = 2048 |
15135 at B = 2048 |
| 1024 | 8192 | 2283 + 3678 = 5961 |
5986 |
| 512 | 4096 | 2283 + 1777 = 4060 |
4085 |
| 256 | 2048 | 2023 | 2048 |
| 128 | 1024 | 999 | 1024 |
The header bound 2283. The description has 14 count bits, at most 19 three-bit lengths, and
one code of at most 7 bits for each of at most 286 + 30 code lengths:
14 + 57 + 7 * 316 = 2283 (build_bl_tree_header_budget).
B ≥ 2048. In a Huffman tree a frequent symbol has a short code: a leaf of frequency f
at depth l forces the total weight to be at least about f times the Fibonacci number
F(l + 1). Summing the worst case over both alphabets, with their extra bits and with the
effect of the length repair, gives an excess of at most 6.257 bits per symbol, counted over
n + 3 (source_trees_symbol_excess_engine, from symbol_excess_from_fib). The 3 are the end-of-block
symbol and the up to two symbols that build_tree adds. With n ≤ B - 1 the budget holds from
B = 1332 up. At B = 1024 it fails: 2283 + 6.257 * 1026 + 25 = 8728 > 8192.
B = 512 and 1024. The trees weigh at most B + 2 ≤ 1026. A tree lighter than
F(17) = 1597 has no node deeper than 15: such a node has a parent at depth 15 or more, and a
node that deep forces a total weight of at least F(16) + F(15) = 1597. So gen_bitlen repairs
nothing in the two data trees
(ws_gen_bitlen_fib_plus), every length is the true depth, and each symbol satisfies
f * F(l + 1) + F(l) ≤ W. Under that constraint the excess is at most 1777 bits for a weight
of at most 514 and at most 3678 bits for a weight of at most 1026 (prepared_excess_small,
from symbol_excess_from_fib_plus).
B = 256 and 128. The general header bound is too large here: 2283 > 2048. The proof
bounds the header of the block at hand. It is 14 + 3 (max_blindex + 1) bits, at most 71, plus
the cost of the code-length symbols. At B = 256 every data code is at most 11 bits long, so
the code-length symbols 12 to 15 do not occur; at B = 128 every code is at most 9 bits long.
The cost of the remaining symbols is bounded against a fixed complete code
(header_ref_bound_256, header_ref_bound_128w). One more inequality is used: the dynamic form was
chosen, so its rounded cost is below the cost of the fixed form. Adding the header bound and a
multiple of that choice inequality cancels the symbol-length sums; Kraft and the Fibonacci depth
bound then give header + excess ≤ 1899 and ≤ 983
(header_excess_256c, header_excess_128_w).
Why the loops end
pqdownheap:kat least doubles each round and stays at mostheap_len ≤ 573.- The merge loop of
build_tree:heap_lenfalls by one per round, fromNto 1. gen_bitlen: the first and second pass run over the stored nodes; the repair loop lowersoverflowby 2 per round; the downward scan stops by F8(i).gen_codes,scan_tree,send_tree: fixed ranges up tomax_code.compress_block: one round per recorded symbol,sym_next / 3rounds.bi_reverse:lenrounds, with1 ≤ len ≤ 15.
The largest bound is that of compress_block: a block has at most B - 1 ≤ 32767 symbols.
The bounds of the other loops are a few hundred rounds at most. All are far below the loop
fuel of 2^64. The safety theorems named above include termination.
Where the hard part is
F9 for a dynamic block, at small memLevel. Array bounds do not give it, and neither does the
comparison of block costs. It needs a fact about the code lengths of the tree that was actually
built: no cheap sequence of symbols can have codes long enough to catch up with the read
position. For B ≥ 2048 a general bound per symbol is enough. For the two smallest buffers
the proved bound has no slack, and the proof has to use the exact header of the block and the
fact that the dynamic form was chosen.
Readings of the C that no theorem states
- Every
depthvalue that the tie-break ofpqdownheapreads was written during the samebuild_treecall. No theorem states it. In the model a read of an integer that was never written returns an arbitrary value and is not a fault, and the theorems hold for every such value (trusted base). not yet confirmed.