Buffer utilities: source decisions
This page lists the places in compress.c, uncompr.c and the bound functions of deflate.c
where the C does something that the model has to represent with care. For each it says what the
C does, what the model does, and whether a theorem covers it. The safety proofs of these
functions are on two other pages; this page is their source-reading companion.
The API contracts give the caller obligations. Terms: glossary.
Where the results are
| Functions | Safety theorems (required) | Page |
|---|---|---|
compress, compress_z, compress2, compress2_z |
compress_safety, compress_z_safety, compress2_safety, compress2_z_safety |
Safety of compress* |
uncompress, uncompress_z, uncompress2, uncompress2_z |
uncompress_safe, uncompress_z_safe, uncompress2_safe, uncompress2_z_safe |
Safety of uncompress* |
deflateBound, deflateBound_z |
deflateBound_safety, deflateBound_z_safety |
Stream compression |
compressBound, compressBound_z |
compressBound, compressBound_z: the exact value of the formula. The functions read no memory, so these full contracts are also their safety goals |
Safety of compress* |
The functional contracts of these functions, such as the bytes that uncompress writes or that
every compressor output fits the bound, are not required for the safety results.
A reading of the C that no theorem states is marked not yet confirmed.
The decisions
The local stream is automatic storage
- C.
compress2_zanduncompress2_zdeclarez_stream stream;as a local. Creating it cannot fail and is not a call of the allocator. - Model. The local stream is a fresh record made by
allocLocalZ. It does not consume a call of the allocation-failure oracle and does not shift the index of the library's own allocations. It is released before every return. Scalar locals whose address is taken are treated the same way. - Coverage. Covered: the safety theorems run the translation with this local and prove that nothing stays allocated.
The wrappers read their length cells before the _z call
- C.
compress2executesz_size_t got = *destLen;before it callscompress2_z.uncompress2reads*destLenand*sourceLenin the same way. TheNULLtests inside the_zfunctions come too late to protect these reads: aNULLcell is undefined behaviour in the wrapper. - Model. A
NULLcell incompress2,compress,uncompress2oruncompressisFault.ub. - Coverage. The safety goals of these four functions take a non-
NULLcell; the_zforms admitNULLand refuse it withZ_STREAM_ERROR.zlib.hdoes not offerNULLcells for the wrappers.
The length cell of compress* is a value, not memory
- C.
destLenpoints to a caller cell.compress2_zwrites it twice. After the argument checks it reads the capacity and stores 0 at once (left = *destLen; *destLen = 0;). After the loop it stores the output length. So a return after a faileddeflateInitleaves 0 in the cell, and a refused call does not write the cell.compress2copies the cell into a local, passes the local tocompress2_z, and copies it back on every return. - Model. The translation takes the value of
*destLen(noneforNULL) and returns the value the cell holds at the return as a second result: the value passed in for a refused call, 0 after a faileddeflateInit, and the output length otherwise (translation). The cell is not memory. - Coverage. This limits the safety goals: a length cell that overlaps the source or the destination cannot be expressed, so such a call is outside the theorems. The row "Whole-buffer compression" of deviations records it.
The length cells of uncompress* are memory
- C.
uncompress2_zreads*sourceLenand*destLenafter the argument checks and writes them once, after the loop (*sourceLen -= len; *destLen -= left;). A refused call and a return after a failedinflateInitdo not write them.uncompress2copies both cells into locals and copies them back on every return. - Model. Each cell is an eight-byte block that holds the value in little-endian order.
- Coverage. Covered by the safety theorems. That the cells are separate from the buffers and from each other is an explicit premise of the goals (row "Counted decompression" of deviations).
A NULL destination with zero capacity in compress2_z
- C.
dest == NULLwith*destLen == 0passes the argument checks. At the end the function computesstream.next_out - dest, with both pointersNULL. - Model. The pointer difference
Ptr.diffreturns 0 forNULL - NULL. It faults when only one of the two pointers isNULL. - Coverage. The safety theorems are proved with this rule of the model.
not yet confirmed: that the selected build defines
NULL - NULL; the C standard (C17, C23) leaves it undefined. It is a trusted-base item (safety, null pointers).
The dummy output pointer of uncompress2_z
- C. For
dest == NULLwith*destLen == 0the function setsdest = (Bytef *)&stream.reserved, becausenext_outmay not beNULL. The pointer is only ever passed asnext_outwithavail_out == 0. - Model. The dummy is a separate local eight-byte block, released before every return. The model does not represent that it is part of the stream record.
- Coverage.
uncompress2_z_safecovers this case for the translation. not yet confirmed: withavail_out == 0the decoder writes nothing throughnext_out, so the difference between a field of the record and a separate block cannot be observed.
The loops refill 32-bit counts from 64-bit lengths
- C.
avail_inandavail_outareunsigned; the remaining lengths arez_size_t. Each loop trip refills an empty count with at most(uInt)-1bytes. The loop continues only onZ_OK.deflateEndorinflateEndruns after a successful init, and the return code is mapped at the end. - Model. The translation keeps these statements one by one.
- Coverage. Covered by the safety theorems; their termination measures are on the two safety
pages. A late memory failure of the decoder can follow output that is already written: the
safety goal of
uncompress*allowsZ_MEM_ERRORwith a nonempty output.
compressBound_z: wrapped additions and saturation
- C. The formula uses wrapping
z_size_tadditions and returns the maximum value when the sum wrapped. - Model. A pure function on
UInt64. - Coverage.
compressBoundandcompressBound_zprove the exact value for every input.
deflateBound_z: the gzip extra length
- C.
deflateBound_zreads the wrapper state and the optional gzip header strings; each string scan includes the terminating NUL. For the extra field the patched C adds 2 and the low 16 bits ofextra_lenas az_size_t, the length the header writer emits (patch 0007). Upstream zlib adds2 + extra_lenevaluated as 32-bitunsigned, which wraps forextra_len >= 0xfffffffe. - Model. The translation follows the patched C.
-
Coverage. Safety is covered (
deflateBound_safety,deflateBound_z_safety). The value of the bound has two defects in upstream zlib.- For
extra_lenof2^32 - 2and2^32 - 1the bound is too small, as a run of the C shows (finding). Patch 0007 takes the low 16 bits of the length (thedeflate.cpart of upstream PR 1360, open). No goal states the value of the bound for a gzip header. - With
windowBits15,memLevel8,Z_FIXEDand level 1 to 3 the output can exceed the bound, as a run of the C shows (finding). Patch 0006 givesZ_FIXEDthe conservative bound (upstream PR 1394, open).
not yet confirmed: that the output fits the bound on the rest of the source and header domain.
- For