REFERENCE / ZLIB × LEAN
Status of the results
This page says, for each result and for each public function of zlib, whether it is done. It is
the only page that states a status. Its main point: the three safety results are done, for all
99 goals that make them up, and so is the round trip of the default zlib stream, with its 14
goals.
A result, a goal or a function has one of two states.
- Done: a Lean theorem whose statement is exactly the goal exists and passes every check of
the project. What a done result rests on says what that amounts to.
- Not done: there is no such theorem. "Not planned" is added when no theorem is intended.
For what the results mean, read the overview. For the theorem of each function
and the calls it covers, read coverage by function and
deviations.
Results
Safety means no undefined behaviour, no memory error, no leak, and termination. The results are
about the default x86_64 Linux build of zlib 1.4 with the seven patches. Each holds under the
premises of its goals; the overview gives them in short, and
deviations by function. A call sequence is the history of one stream, one gzip
file handle or one callback decoder.
| # |
Result |
Goals |
State |
| 1 |
inflate is safe on every input and every split of the buffers, also over its call sequences. |
Goal.inflate_safety, Goal.inflate_sequence_safety |
done |
| 2 |
deflate is safe on every input and every split of the buffers, also over its call sequences. |
Goal.deflate_safety, Goal.deflate_sequence_safety |
done |
| 3 |
Every other documented public function is safe: compress* and uncompress*, the other stream functions, the checksums, the gzip file interface and the callback decoder inflateBack. |
every other goal of the tables below |
done |
| 4 |
The round trip of the default zlib stream: uncompress(compress(x)) = x when compress has compressBound room; and compressing with deflateInit at the default level and deflate calls with any flush value, finished by deflate(Z_FINISH) calls, and then decompressing with inflateInit gives back the input, for every split of the buffers. |
Goal.compress_uncompress_roundtrip, Goal.compress_uncompress_roundtrip_witness, Goal.compress_completes, Goal.compress_z_completes, Goal.uncompress_completes, Goal.stream_roundtrip_total, Goal.deflate_finish_ends, Goal.inflate_chain_ends, Goal.stream_roundtrip, Goal.deflate_completes_default, Goal.deflate_bound_default, Goal.inflate_completes_default, Goal.default_inflate_progress, Goal.default_inflate_completes |
done |
Result 4 is a functional result. It is about the stream that deflateInit makes at the default
level and inflateInit reads, with no preset dictionary, where every allocation succeeds. Its
encoder histories are deflateInit, then deflate calls and changes of the buffer fields; a
history with deflateParams, a reset or another level is not part of it. The calls that finish
the stream and the inflate calls have output room.
The round trip states each goal with its premises, and
its table below says what each goal is.
Every public function
Each documented function of the default build has its own safety goal. The page of each function
in the API reference shows the statement of its goal.
Decompression streams
| Function |
Goal |
State |
inflate |
Goal.inflate_safety |
done |
inflateCopy |
Goal.inflateCopy_safety |
done |
inflateEnd |
Goal.inflateEnd_safety |
done |
inflateGetDictionary |
Goal.inflateGetDictionary_safety |
done |
inflateGetHeader |
Goal.inflateGetHeader_safety |
done |
inflateInit2_ |
Goal.inflateInit2__safety |
done |
inflateInit_ |
Goal.inflateInit__safety |
done |
inflateMark |
Goal.inflateMark_safety |
done |
inflatePrime |
Goal.inflatePrime_safety |
done |
inflateReset |
Goal.inflateReset_safety |
done |
inflateReset2 |
Goal.inflateReset2_safety |
done |
inflateSetDictionary |
Goal.inflateSetDictionary_safety |
done |
inflateSync |
Goal.inflateSync_safety |
done |
Compression streams
| Function |
Goal |
State |
deflate |
Goal.deflate_safety |
done |
deflateBound |
Goal.deflateBound_safety |
done |
deflateBound_z |
Goal.deflateBound_z_safety |
done |
deflateCopy |
Goal.deflateCopy_safety |
done |
deflateEnd |
Goal.deflateEnd_safety |
done |
deflateGetDictionary |
Goal.deflateGetDictionary_safety |
done |
deflateInit2_ |
Goal.deflateInit2__safety |
done |
deflateInit_ |
Goal.deflateInit__safety |
done |
deflateParams |
Goal.deflateParams_safety |
done |
deflatePending |
Goal.deflatePending_safety |
done |
deflatePrime |
Goal.deflatePrime_safety |
done |
deflateReset |
Goal.deflateReset_safety |
done |
deflateSetDictionary |
Goal.deflateSetDictionary_safety |
done |
deflateSetHeader |
Goal.deflateSetHeader_safety |
done |
deflateTune |
Goal.deflateTune_safety |
done |
deflateUsed |
Goal.deflateUsed_safety |
done |
Whole buffers and library information
| Function |
Goal |
State |
compress |
Goal.compress_safety |
done |
compress2 |
Goal.compress2_safety |
done |
compress2_z |
Goal.compress2_z_safety |
done |
compressBound |
Goal.compressBound |
done |
compressBound_z |
Goal.compressBound_z |
done |
compress_z |
Goal.compress_z_safety |
done |
uncompress |
Goal.uncompress_safe |
done |
uncompress2 |
Goal.uncompress2_safe |
done |
uncompress2_z |
Goal.uncompress2_z_safe |
done |
uncompress_z |
Goal.uncompress_z_safe |
done |
zlibCompileFlags |
Goal.zlibCompileFlags_safety |
done |
zlibVersion |
Goal.zlibVersion_safety |
done |
Checksums
| Function |
Goal |
State |
adler32 |
Goal.adler32_safety |
done |
adler32_combine |
Goal.adler32_combine_safety |
done |
adler32_combine64 |
Goal.adler32_combine64_safety |
done |
adler32_z |
Goal.adler32_z_safety |
done |
crc32 |
Goal.crc32_safety |
done |
crc32_combine |
Goal.crc32_combine_safety |
done |
crc32_combine64 |
Goal.crc32_combine64_safety |
done |
crc32_combine_gen |
Goal.crc32_combine_gen_safety |
done |
crc32_combine_gen64 |
Goal.crc32_combine_gen64_safety |
done |
crc32_combine_op |
Goal.crc32_combine_op_safety |
done |
crc32_z |
Goal.crc32_z_safety |
done |
Callback decoding
| Function |
Goal |
State |
inflateBack |
Goal.inflateBack_safety |
done |
inflateBackEnd |
Goal.inflateBackEnd_safety |
done |
inflateBackInit_ |
Goal.inflateBackInit__safety |
done |
Gzip files
| Function |
Goal |
State |
gzbuffer |
Goal.gzbuffer_safety |
done |
gzclearerr |
Goal.gzclearerr_safety |
done |
gzclose |
Goal.gzclose_safety |
done |
gzclose_r |
Goal.gzclose_r_safety |
done |
gzclose_w |
Goal.gzclose_w_safety |
done |
gzdirect |
Goal.gzdirect_safety |
done |
gzdopen |
Goal.gzdopen_safety |
done |
gzeof |
Goal.gzeof_safety |
done |
gzerror |
Goal.gzerror_safety |
done |
gzflush |
Goal.gzflush_safety |
done |
gzfread |
Goal.gzfread_safety |
done |
gzfwrite |
Goal.gzfwrite_safety |
done |
gzgetc |
Goal.gzgetc_safety |
done |
gzgetc_ |
Goal.gzgetc__safety |
done |
gzgets |
Goal.gzgets_safety |
done |
gzoffset |
Goal.gzoffset_safety |
done |
gzoffset64 |
Goal.gzoffset64_safety |
done |
gzopen |
Goal.gzopen_safety |
done |
gzopen64 |
Goal.gzopen64_safety |
done |
gzprintf |
Goal.gzprintf_safety |
done |
gzputc |
Goal.gzputc_safety |
done |
gzputs |
Goal.gzputs_safety |
done |
gzread |
Goal.gzread_safety |
done |
gzrewind |
Goal.gzrewind_safety |
done |
gzseek |
Goal.gzseek_safety |
done |
gzseek64 |
Goal.gzseek64_safety |
done |
gzsetparams |
Goal.gzsetparams_safety |
done |
gztell |
Goal.gztell_safety |
done |
gztell64 |
Goal.gztell64_safety |
done |
gzungetc |
Goal.gzungetc_safety |
done |
gzvprintf |
Goal.gzvprintf_safety |
done |
gzwrite |
Goal.gzwrite_safety |
done |
gzvprintf is undocumented in zlib.h. It has a safety goal because gzprintf goes through it.
Goal.compressBound and Goal.compressBound_z are the full contracts of two pure functions with
no heap and no fault; they stand for the safety goals of these two functions.
Goals about more than one function
| Statement |
Goal |
State |
| Every call sequence of an inflate stream is safe. |
Goal.inflate_sequence_safety |
done |
| Every call sequence of a deflate stream is safe. |
Goal.deflate_sequence_safety |
done |
| Every call sequence of the callback decoder is safe, for every caller protocol. |
Goal.inflate_back_sequence_safety |
done |
| Every history of a gzip file handle is safe, for every file-system world. |
Goal.gz_sequence_safety |
done |
The inflate functions refuse a NULL or inconsistent stream without a fault. |
Goal.inflate_refusal |
done |
The deflate functions refuse a NULL or inconsistent stream without a fault. |
Goal.deflate_refusal |
done |
The gzip file functions refuse a NULL handle without a fault and change nothing. |
Goal.gz_refusal |
done |
| The premises of the inflate goals can be met: initialisation succeeds on a concrete heap. |
Goal.inflate_initialisation_domain |
done |
| The premises of the deflate goals can be met: initialisation succeeds on a concrete heap. |
Goal.deflate_initialisation_domain |
done |
| The premises of the callback-decoder goals can be met: initialisation succeeds on a concrete heap. |
Goal.inflate_back_initialisation_domain |
done |
The premises of an inflateBack call can be met together, with concrete callbacks and a concrete caller protocol. |
Goal.inflateBack_call_domain |
done |
| The premises of the gzip file goals can be met: two concrete histories of a handle exist, one reading and one writing. |
Goal.gz_sequence_nonvacuity |
done |
The round trip of the default zlib stream
| Statement |
Goal |
State |
uncompress(compress(x)) = x: compress with compressBound room returns Z_OK, and uncompress of the bytes it wrote, with room for the source, returns Z_OK and gives back the source and its length. |
Goal.compress_uncompress_roundtrip |
done |
The premises of Goal.compress_uncompress_roundtrip can be met, on concrete heaps with a non-empty source. |
Goal.compress_uncompress_roundtrip_witness |
done |
compress with compressBound room returns Z_OK, and what it wrote is a zlib stream that decodes to the source and asks for no preset dictionary. |
Goal.compress_completes |
done |
The same for compress_z. |
Goal.compress_z_completes |
done |
uncompress of a zlib stream that asks for no preset dictionary, with room for its decoding, returns Z_OK, writes the decoding and stores its length. |
Goal.uncompress_completes |
done |
The stream round trip with the completion of both sides: Goal.deflate_finish_ends and Goal.inflate_chain_ends together. |
Goal.stream_roundtrip_total |
done |
After any deflate calls on a default stream, every continuation by deflate(Z_FINISH) calls with output room ends after a bounded number of calls, with all input consumed and an output that decodes to the input. |
Goal.deflate_finish_ends |
done |
A default decoder given a complete default stream, in any chunks and with output room, ends after a bounded number of inflate calls, having written exactly the input of the encoder. |
Goal.inflate_chain_ends |
done |
When a deflate call sequence and an inflate call sequence on default streams both reach Z_STREAM_END, and the decoder read a prefix of what the encoder wrote, the decoder wrote exactly the input of the encoder. |
Goal.stream_roundtrip |
done |
After deflate calls with Z_NO_FLUSH or Z_FINISH only, one deflate(Z_FINISH) call given all the remaining input and more room than the bound of the whole input leaves returns Z_STREAM_END, and the whole output decodes to the whole input. |
Goal.deflate_completes_default |
done |
On a new default stream, one deflate(Z_FINISH) call given all the input and at least deflateBound bytes of room returns Z_STREAM_END and writes a stream that decodes to the input. |
Goal.deflate_bound_default |
done |
A default decoder that has read part of a complete default stream, given the rest of it and room for the rest of the decoding, returns Z_STREAM_END and writes the rest of the input of the encoder. |
Goal.inflate_completes_default |
done |
A default decoder on any zlib stream the format accepts: each inflate call given more of the stream and output room ends the stream with exactly its decoding, or consumes input or writes output; a stream that asks for a preset dictionary gives Z_NEED_DICT. |
Goal.default_inflate_progress |
done |
A default decoder given the whole rest of a zlib stream the format accepts and room for the rest of its decoding ends the stream in one call, or returns Z_NEED_DICT for a stream that asks for a preset dictionary. |
Goal.default_inflate_completes |
done |
Not planned
No theorem is intended for these.
| Group |
What it covers |
Reason |
| Functional correctness, except result 4 |
What a function computes beyond safety: the round trip, and that inflate reads a stream the format accepts to its end, in other configurations (other levels, strategies, window sizes and wrappers, preset dictionaries), through the gzip file interface or through inflateBack; what inflate does with a stream the format rejects; the bytes the gzip file functions read or write; what inflateBack delivers; the full contracts of the four kinds of call sequence (Goal.inflate_sequence, Goal.deflate_sequence, Goal.inflate_back_sequence, Goal.gz_sequence); statements about the abstract models only. |
The safety results do not need it. The statements about the gzip file interface would also rest on a hand-made model of the file system and of descriptors, and on formatted output that the model takes from the C contract of vsnprintf without computing it. A functional fact that a safety proof depends on is proved as part of that proof. |
| Other build configurations |
Every configuration except the default x86_64 Linux build. |
Each one repeats the whole proof for a different platform model. |
| Undocumented functions |
zError, inflateSyncPoint, get_crc_table, inflateUndermine, inflateValidate, inflateCodesUsed, inflateResetKeep, deflateResetKeep, gzopen_w: nine of the ten functions that zlib.h declares under "undocumented functions (not part of the zlib API)". The tenth is gzvprintf, above. |
They are not part of the zlib API. No safety goal is stated for them: not done, not planned. |
Many functions have a theorem for their functional contract all the same, among them eight of
the nine undocumented functions (all but gzopen_w, which is not in the default build). The
page of each function in the API reference says whether its functional
contract is done. A functional contract that is not done is not planned: the only functional
result is result 4, and it is not the contract of one function.