Fast decoding: why inflate_fast is safe
Source: zlib/inffast.c. Translation: ZlibF/Zlib/inffast.c.lean.
inflate_fast decodes literals and matches without checking, on each read and write, that
input and output remain. It is safe because its callers enter it only with at least 6 input
bytes and 258 output bytes, and because one round of its loop reads at most 6 bytes and writes
at most 258. This page lists the entry conditions the theorem assumes, shows the loop invariant,
and explains the two bounds.
inflate_fast is an internal function. Its callers are inflate
(stream decoding) and inflateBack (callback decoder).
Results
| Result | Theorem |
|---|---|
Goal.fast_safe: under the entry conditions, the call returns without a fault; the postcondition FastPost says exactly what changed |
inflate_fast_safe |
One round of the loop is safe: at most 6 bytes read, at most 258 written, at least one written if the loop continues (Goal.step_safe) |
inflate_fast_body_step_safe |
| The static fixed tables have the table shape | lenfix_tableSafe, distfix_tableSafe |
The same safety statement, and: a call that does not end in mode TYPE or BAD leaves less output room than it found |
inflate_fast_safe_progress |
The same, and: a call never increases bits + 8 * avail_in, and lowers it unless it ends in TYPE or BAD |
fast_consumes |
The two goals Goal.fast_safe and Goal.step_safe are done.
inflate_fast_safe is stated for the entry conditions of inflate (Env). The last two
theorems of the table, inflate_fast_safe_progress and fast_consumes, are stated for the
entry conditions of both callers (EnvG); they are lemmas inside the proofs of the callers.
How the callers use these theorems:
inflateBack.fast_envproves the entry conditions.LEN_fast_ptakes them from it and appliesfast_consumes. This is inside the proof ofinflate_back_sequence_safety. It is what makes the call frominflateBacksafe, and it gives termination of that caller's loop.inflate, input and output in two different heap blocks.inflate_fast_raw_entryproves the entry conditions under that premise (ib ≠ ob), andinflate_fast_safe_progressis applied to them.inflate, every layout.inflate_sequence_safety_publicallows the input and the output to be two ranges of one block. For the fast call its proof usesinflate_fast_default_view_buffers_progress, a lemma of that proof. That lemma has no premise on the blocks. It is a second proof of the same translated function, stated on the caller's ranges and the decoder invariant; it does not useEnvG.fast_consumesis not used forinflate. See stream decoding.inflate, functional results.inflate_fast_entryproves the entry conditions for every layout. The functional theoremfast_call_meaninguses it; the safety results do not.
FastPost says: the stream's next_in, avail_in, next_out, avail_out and msg and the
state's mode, hold and bits were written; output bytes changed only in the range this
call wrote; bits < 8 and hold < 2^bits again; the mode is unchanged, or TYPE (end of
block), or BAD. Nothing else in the heap changed, and nothing was allocated.
Functional results about inflate_fast also exist; see Functional results.
Assumptions
The theorems assume the entry conditions below. In Lean they are the fields of the record
EnvG. Env is the case of inflate, in which the window
is never the output object; inflate_fast_safe is stated for Env. These are
internal premises: a caller proves them before it applies a theorem of this page; the lemmas
that do so are named under Results.
- Stream.
strmpoints at a writable stream record whosestateis an inflate state. - Input.
next_inpoints into a byte object of fewer than2^63bytes.avail_in ≥ 6, and theavail_inbytes lie inside the object. A byte object is a heap block or any other byte array of the model, such as an array inside a state record. - Output.
next_outpoints into a writable byte object of fewer than2^63bytes.avail_out ≥ 258, and theavail_outbytes lie inside the object.start ≥ avail_out, andstart - avail_outbytes lie beforenext_outin the same object; sobegbelow is a pointer into that object. - Separation. Input and output are different byte objects, or two ranges of one object that do not overlap.
- Bit buffer.
bits < 8,hold < 2^bits,sane ≠ 0. - Window.
wsize ≤ 32768,whave ≤ wsize,wnext ≤ wsize. Ifwhave ≠ 0,windowpoints atwsizebytes inside a heap block. Forinflatethat block is not the output object. ForinflateBackit may be the output object; thenwnext = 0and the window ends inside the output range. - Tables.
lencodeanddistcodepoint at tables of the safe shape forlenbitsanddistbits(LenTableSafe,DistTableSafe; see decode tables).
The internal contracts page also describes the entry of
inflate_fast. Where that description says more than the list above, the list is what the
safety theorems assume.
No premise names the mode. No premise says what the window bytes contain, or that
whave < wsize implies wnext = whave. Safety needs only the bounds above; the rest belongs to
the functional argument.
fast_consumes has one more premise: every literal/length leaf uses at least one bit
(LenLeavesPositive). inflate_table_len_leaves_positive proves it for a constructed table
and lenfix_leavesPositive for the fixed table.
The loop and its invariant
last = in + (strm->avail_in - 5); /* loop while in < last */
beg = out - (start - strm->avail_out); /* start of the output of the enclosing call */
end = out + (strm->avail_out - 257); /* loop while out < end */
do {
/* decode one literal, or one length and distance with its copy */
} while (in < last && out < end);
/* give back unused whole bytes; write in, out, hold, bits back */
Write in0 and out0 for the values of next_in and next_out at entry.
output block beg ........ out0 ........ out ............ end ... out0 + avail_out
| earlier output | this call | free; at least 258 bytes at loop entry
input block in0 ........ in ............ last ... in0 + avail_in
| read | unread; at least 6 bytes at loop entry
At the start of every round the following hold (LS, and the loop invariant in fast_loop_wp).
| Name | Says |
|---|---|
| I1 | in0 ≤ in, and in + 6 ≤ in0 + avail_in: six bytes can be read |
| I2 | out0 ≤ out, and out + 258 ≤ out0 + avail_out: 258 bytes can be written |
| I3 | bits ≤ 30 and hold < 2^bits |
| I4 | bits + 8 * in0 ≤ bits_entry + 8 * in: every held bit came from the entry or from a byte this call read |
| I5 | Output bytes outside [out0, out) are as they were at entry |
The first round is reached without a test, because the loop is a do loop. The entry
conditions give I1 and I2 for it directly. Later rounds get them from the loop condition.
Why each round keeps the invariant
At most six bytes are read
One round has four places that read input.
| Place | Guard and read | After it |
|---|---|---|
| R1, before the length lookup | bits < 15: read two bytes |
16 to 30 bits |
| R2, length extra bits | bits < op, with op ≤ 5: read one byte |
enough for op |
| R3, before the distance lookup | bits < 15: read two bytes |
16 to 30 bits |
| R4, distance extra bits | bits < op, with op ≤ 13: read one byte, and a second if still bits < op |
enough for op |
A code uses at most 15 bits, including a second-level lookup; that is part of the table shape.
So after R1 or R3, or when either is skipped, the code that follows is covered. The op bounds
5 and 13 are also part of the table shape. Hence every bits -= op takes away only bits that
are there, and every shift is by less than the width of its operand.
Adding up the four maxima gives seven bytes. Seven cannot happen. Suppose R1, R2, R3 and R4 read 2, 1, 2 and 2 bytes.
- After R1 at least 16 bits are held. The length code takes at most 15: at least 1 remains.
- R2 adds 8 and the length extra bits take at most 5: at least 4 remain.
- R3 adds 16 and the distance code takes at most 15: at least 5 remain.
- R4 reads its second byte only if, after the first, fewer than
op ≤ 13bits are held. Then fewer than 5 were held before R4. This contradicts step 3.
So one round reads at most six bytes, which is why last is five bytes before the end of the
input. One round writes one literal or a match of at most 258 bytes, which is why end is 257
bytes before the end of the output. The bound 258 comes from the table shape: a length base
plus its largest extra value is at most 258. inflate_fast_body_step_safe states both bounds.
Table reads
The root index is hold & ((1 << lenbits) - 1), which is below 2^lenbits; the table shape
puts 2^lenbits entries inside the array. A root entry is a leaf or a link. A link designates a
second-level table that lies inside the array and holds only leaves, so the goto dolen or
goto dodist happens at most once per code.
An invalid code sets msg and mode BAD and leaves the loop. An end-of-block code sets mode
TYPE and leaves the loop. Both go through the same exit code as a normal end.
Match copies
Let dist ≥ 1 be the decoded distance and len the length, with 3 ≤ len ≤ 258.
From the output. If dist ≤ out - beg, the source out - dist is at or after beg, in the
output block. The copy runs byte by byte, forward. Each byte it reads was written before the
round or by an earlier step of the same copy, also when dist < len and the ranges overlap.
From the window. Otherwise op = dist - (out - beg) bytes come from the window. The C
tests op > whave and, because sane ≠ 0, leaves with an error. After the test
1 ≤ op ≤ whave ≤ wsize. In particular whave ≠ 0, so the window block exists. There are
three source positions.
| Condition | First window index | Why it is inside [0, wsize) |
|---|---|---|
wnext == 0 |
wsize - op |
1 ≤ op ≤ wsize |
0 < wnext < op |
wsize + wnext - op |
op ≤ wsize and wnext < op. The copy runs to the end of the ring, then continues at index 0 for up to wnext bytes |
wnext ≥ op |
wnext - op |
op ≤ wnext ≤ wsize |
Each piece copies the smaller of what the window holds there and what the match still needs. If the match is longer, the rest comes from the output, as above.
For inflateBack the window is the output buffer itself. Then wnext = 0, only the first row
applies, and the premise that the window ends inside the output range keeps the read in the
block.
Giving bytes back and writing back
len = bits >> 3;
in -= len;
bits -= len << 3;
hold &= (1U << bits) - 1;
I4 gives bits ≤ bits_entry + 8 * (in - in0). With bits_entry < 8 this means
len ≤ in - in0: the function gives back only bytes it read itself, and in does not move
before in0. Afterwards bits < 8, so the mask shift is in range. This is where the entry
condition bits < 8 is used. Without it the function could step back over bytes that the caller
had consumed.
inflate tests bits < 8 in its own condition for taking the fast path. inflateBack does not
test it. The proof of its dispatch loop carries the fact in the loop invariant: fewer than 8 bits
are held whenever a round starts in mode TYPE, TABLE or LEN (Short). LEN_fast_p takes
bits < 8 at entry as a premise, which that invariant supplies, and proves that it holds
again after the call.
The function then computes the new avail_in and avail_out from pointer differences inside
one block each and stores them with the cursors, hold and bits
(fast_finish_wp).
Why the loops end
The measure of the main loop is the free output room, out0 + avail_out - out
(fast_loop_wp). A round that does not leave the loop writes at least one byte, so the measure
falls. It is below 2^63, far below the loop fuel of 2^64.
Inside a round, a copy loop runs op or len times and counts down, and a code needs at most
one extra lookup.
Where the hard part is
The two margins are small and they are exact. The loop is safe only because a round can never read a seventh byte, and that is not visible in any one statement: it follows from how the four refills interact with the bit counts that the tables allow. The proof follows the same case split as the argument above, on the heap, for every table of the safe shape.
The second hard point is the output block. It is read and written in the same round, the source of a match can overlap its destination, and input and output may be two ranges of one block: run under sanitizers, the real C decodes correctly in that layout, with no report. The loop invariant therefore tracks the whole output array, not a separate view of "old" and "new" bytes.
Readings of the C that no theorem states
- A window byte that a match reads was written earlier. For
inflatethis follows from the window shape W.5 of stream decoding: in a window that is not fullwnext = whave, so only the third row of the table can occur, and it reads belowwnext.EnvGdoes not carry W.5, and the safety theorem does not need it: in the model a read of a byte that was never written returns an arbitrary value and is not a fault (trusted base). not yet confirmed.
Functional results
These results say what the fast decoder computes. Each has a theorem, and none is required for the safety results.
| Result | Theorems |
|---|---|
| A round consumes exactly the bits of one format token, and the bits it consumes are the next bits of the source | actual_body_refines_token, actual_body_preserves_origin |
| A length or distance lookup returns the format's symbol | length_lookup_matches_format, distance_lookup_matches_format |
| A match copy is the LZ77 copy of the format | actual_distance_refines_lz77, actual_copy_match_refines_lz77 |
For these the invariant is larger: it relates the consumed bits to the source stream and the
window contents to the earlier output. fast_call_meaning carries the meaning through the
fast branch of LEN in inflate, for input and output in any byte objects: after the call the
decoded tokens still parse as the format says, or the mode is BAD and the input read has no
valid completion. It is a step of
the round trip of the default zlib stream. Bytes read ahead and given back play no
part in the meaning of a decoded symbol; see
stream decoding.