REFERENCE / ZLIB × LEAN
Statements of the goals
These goals are about more than one function: whole call sequences, the refusal of an invalid stream or handle, that the premises of the goals can be met, and the round trip of the default zlib stream. The goal of each function is on the page of that function. Which are done is on the status page; the state of each full sequence contract, which is a functional goal, is shown with it below.
Safety of call sequences
inflate_sequence_safety
/-- **Safety of every permitted inflate call sequence** (the safety half of
`Goal.inflate_sequence`): every reachable stream satisfies the stream invariant, and one more
permitted call returns without a fault, keeps the invariant, writes only the stream's own blocks,
the stream record, the gzip header record and the declared caller regions, and changes the live
blocks exactly as the allocation ledger says (no leak); `inflateEnd` frees every block the stream
owns. The functional clauses of `Goal.inflate_sequence` are not planned (`docs/en/progress.md`,
"Not planned"). -/
def Goal.inflate_sequence_safety : Prop := StreamSequenceSafety .inflateComplete context ↗deflate_sequence_safety
/-- **Safety of every permitted deflate call sequence** (the safety half of
`Goal.deflate_sequence`): every reachable stream satisfies the stream invariant, and one more
permitted call returns without a fault, keeps the invariant, writes only the stream's own blocks,
the stream record and the declared caller regions, and changes the live blocks exactly as the
allocation ledger says (no leak). The functional clauses of `Goal.deflate_sequence` are not planned. -/
def Goal.deflate_sequence_safety : Prop := StreamSequenceSafety .deflateComplete context ↗inflate_back_sequence_safety
/-- **Safety of every permitted callback-decoder sequence** (the safety half of
`Goal.inflate_back_sequence`). A null stream is refused. Every reachable history leaves a valid
state over the caller's window. One more `inflateBack` call, for every caller protocol whose total
input is below `2^48` bytes (the runtime bounds every loop by `2^64` iterations; `docs/en/deviations.md`),
returns without a fault with one of its three results, keeps the state valid over the same window,
changes only the stream record, the state record, the callback's own blocks and the window slice,
and leaves the live blocks outside the callback's own unchanged (no leak). `inflateBackEnd` frees the
state. The histories are those of `BackSafeReachable`: the window is a slice of a heap byte block,
every byte object has fewer than `2^63` bytes on the heap of each call and after each call-back
step (`BackPlatform`), and every input chunk lies in a heap byte block (`BackFirstChunk`,
`BackPlatform`); `docs/en/deviations.md` lists these premises. The decoding clauses of
`Goal.inflateBack` (what reaches `out`, `Decodes`) are not planned (`docs/en/progress.md`, "Not planned"). -/
def Goal.inflate_back_sequence_safety : Prop :=
(∀ h input inDesc output outDesc,
C.run (Zlib.Infback.inflateBack none input inDesc output outDesc) h = .ok (Z_STREAM_ERROR, h)) ∧
(∀ h r i window n, BackSafeReachable h r i window n →
∃ z s, BackValid h r i z s ∧ s.window = window ∧ s.wsize.toNat = n) ∧
(∀ h r i window n z s input inDesc output outDesc
(protocol : CallbackProtocol r i window n input inDesc output outDesc) first,
BackSafeReachable h r i window n → BackValid h r i z s →
(if z.next_in = .null then first = [] else Bytes h z.next_in z.avail_in.toNat first) →
Separate z.next_in first.length window n →
protocol.invariant h { supplied := first, chunks := [], active := z.next_in, held := first } →
protocol.inputBound < 2 ^ 48 →
ZlibF.PlatformMemory.ByteObjectsFit h → BackPlatform protocol → BackFirstChunk z first →
∃ rc after z' s' log,
C.run (Zlib.Infback.inflateBack (some r) input inDesc output outDesc) h = .ok (rc, after) ∧
BackValid after r i z' s' ∧ s'.window = window ∧ s'.wsize = s.wsize ∧
protocol.invariant after log ∧
(rc = Z_STREAM_END ∨ rc = Z_DATA_ERROR ∨ rc = Z_BUF_ERROR) ∧
CallbackFrame protocol.own h after r i window n ∧
(∀ b, ¬ protocol.own b → (after.live b ↔ h.live b))) ∧
(∀ h r i window n, BackSafeReachable h r i window n →
∃ after z, C.run (Zlib.Infback.inflateBackEnd (some r)) h = .ok (Z_OK, after) ∧
r.get after = some z ∧ z.state = none ∧
Frame h after (fun b => StreamRoot r b ∨ b = i) ∧
LiveChange h after (fun _ => False) (fun b => b = i))Complete context ↗gz_sequence_safety
/-- **Goal: safety of every gz file history.** Every history keeps the world well formed and the
handle in `GzInv`; `GzHistory` has no budget premise. For every next public call and every world (every
oracle): the run's result is not a fault, it is `.ok` or the out-of-fuel outcome, never `Fault.ub` or a memory
error (no premise); with `ReadsFinite` (a read budget below `2^61` bytes, only for the reading calls of `NeedsReadBound`) the result is `.ok`. `NeedsReadBound` goes by call name:
`gzread`, `gzfread`, `gzgetc`, `gzgetc_`, `gzgets` and `gzungetc`. For these the termination claim needs `ReadsFinite`, also
where the C returns at once (a call on a writer, a request of length 0); every other call terminates in every world. The
first half is partial correctness up to `2^64` iterations of each loop, which no real execution reaches. A call
that returns keeps the open descriptors, keeps
`GzInv`, writes only the handle's blocks and the declared caller regions, and changes the live blocks exactly
by the handle's ledger. The `gzgetc()` macro has the post of the function, which writes no caller region, and the
termination split of a reading call: with buffered output (`x.have ≠ 0`, the inline path) it returns with no premise;
with `x.have = 0` it calls the function `gzgetc`, and returns under `ReadsFinite`. The pointer `gzerror` returns is a readable NUL-terminated string in the heap after the
call: a literal or the handle's message. Every close returns and either refuses on the wrong mode or frees every owned block and
releases the descriptor. Every open returns; a failed open leaves no block and no open descriptor behind. -/
def Goal.gz_sequence_safety : Prop :=
(∀ h fs i, GzHistory h fs i → FileSystem fs ∧ ∃ s, GzInv h i s) ∧
(∀ h fs i s call, GzHistory h fs i → h.gzstates i = some s → GzOperation i call → GzArguments h i s call →
(∀ e, call.execute fs h = .error e → e = .outOfFuel) ∧
((NeedsReadBound call → ReadsFinite fs s.fd) →
∃ value fs' after, call.execute fs h = .ok ((value, fs'), after)) ∧
(∀ value fs' after, call.execute fs h = .ok ((value, fs'), after) →
FdsKept fs fs' ∧ GzStepPost h i s call fs' after)) ∧
(∀ h fs i s, GzHistory h fs i → h.gzstates i = some s →
(∀ e, Zlib.ZlibH.gzgetc (some (.in_gzstate_x i)) fs h = .error e → e = .outOfFuel) ∧
((s.x.have = 0 → NeedsReadBound (.gzgetc (some (.in_gzstate_x i))) → ReadsFinite fs s.fd) →
∃ value fs' after, Zlib.ZlibH.gzgetc (some (.in_gzstate_x i)) fs h = .ok ((value, fs'), after)) ∧
(∀ value fs' after, Zlib.ZlibH.gzgetc (some (.in_gzstate_x i)) fs h = .ok ((value, fs'), after) →
FdsKept fs fs' ∧ GzStepPost h i s (.gzgetc (some (.in_gzstate_x i))) fs' after)) ∧
(∀ h fs i s errnum, GzHistory h fs i → h.gzstates i = some s →
GzArguments h i s (.gzerror (some (.in_gzstate_x i)) errnum) →
∀ (value : BPtr) fs' after,
(Call.gzerror (some (.in_gzstate_x i)) errnum).execute fs h = .ok ((value, fs'), after) →
∃ t, CString after value t) ∧
(∀ h fs i s call, GzHistory h fs i → h.gzstates i = some s → GzCloseCall i call →
∃ value fs' after, call.execute fs h = .ok ((value, fs'), after) ∧
((CloseRefuses s call ∧ after = h ∧ fs' = fs) ∨ (¬ CloseRefuses s call ∧ GzReleased h after fs fs' i s))) ∧
GzOpenSafe Zlib.Gzlib.gzopen ∧ GzOpenSafe Zlib.Gzlib.gzopen64 ∧ GzDopenSafeComplete context ↗Refusals
inflate_refusal
/-- **Inflate stream refusals.** `inflate` makes and frees its local four-byte array, so its
refusal is stated with a frame and an unchanged ledger; the other functions leave the heap
exactly as it was. `inflateCopy` from a refused source clears the destination state. -/
def Goal.inflate_refusal : Prop :=
(∀ h p flush, Fresh h → RefusedInflate h p →
∃ after, C.run (Zlib.Inflate.inflate p flush) h = .ok (Z_STREAM_ERROR, after) ∧
Frame h after (fun _ => False) ∧ LiveChange h after (fun _ => False) (fun _ => False)) ∧
(∀ h p, RefusedInflate h p → C.run (Zlib.Inflate.inflateEnd p) h = .ok (Z_STREAM_ERROR, h)) ∧
(∀ h p, RefusedInflate h p → C.run (Zlib.Inflate.inflateReset p) h = .ok (Z_STREAM_ERROR, h)) ∧
(∀ h p windowBits, RefusedInflate h p →
C.run (Zlib.Inflate.inflateReset2 p windowBits) h = .ok (Z_STREAM_ERROR, h)) ∧
(∀ h p dictionary dictLength, RefusedInflate h p →
C.run (Zlib.Inflate.inflateGetDictionary p dictionary dictLength) h =
.ok ((Z_STREAM_ERROR, dictLength), h)) ∧
(∀ h p dictionary dictLength, RefusedInflate h p →
C.run (Zlib.Inflate.inflateSetDictionary p dictionary dictLength) h = .ok (Z_STREAM_ERROR, h)) ∧
(∀ h dest oldDest source, dest.get h = some oldDest → RefusedInflate h source →
C.run (Zlib.Inflate.inflateCopy (some dest) source) h =
.ok (Z_STREAM_ERROR, dest.put h { oldDest with state := none }))Complete context ↗deflate_refusal
/-- **Deflate stream refusals.** Each function refuses a refused stream and leaves the heap
exactly as it was. `deflateCopy` from a refused source clears the destination state; this
includes a source whose live state the check refuses (a wrong back pointer or status). -/
def Goal.deflate_refusal : Prop :=
(∀ h p flush, RefusedDeflate h p → C.run (Zlib.Deflate.deflate p flush) h = .ok (Z_STREAM_ERROR, h)) ∧
(∀ h p dictionary dictLength, RefusedDeflate h p →
C.run (Zlib.Deflate.deflateSetDictionary p dictionary dictLength) h = .ok (Z_STREAM_ERROR, h)) ∧
(∀ h p level strategy, RefusedDeflate h p →
C.run (Zlib.Deflate.deflateParams p level strategy) h = .ok (Z_STREAM_ERROR, h)) ∧
(∀ h p dictionary hasDictLength, RefusedDeflate h p →
C.run (Zlib.Deflate.deflateGetDictionary p dictionary hasDictLength) h = .ok ((Z_STREAM_ERROR, none), h)) ∧
(∀ h dest oldDest source, dest.get h = some oldDest → RefusedDeflate h source →
C.run (Zlib.Deflate.deflateCopy (some dest) source) h =
.ok (Z_STREAM_ERROR, dest.put h { oldDest with state := none }))Complete context ↗gz_refusal
/-- **Refusal of a `NULL` handle** by every gz function of the public interface: the documented
value, the heap and the file-system world unchanged, for every heap, world and other argument.
No precondition. `gzprintf` and `gzvprintf` quantify over the argument list.
`gzgetc` is the function `(gzgetc)(file)`. The `gzgetc` macro of `zlib.h` reads `(g)->have` first,
so the macro on `NULL` is undefined behaviour in C; the translation `Zlib.Gzread.gzgetc` is the
function, and that is what is stated here. -/
def Goal.gz_refusal : Prop :=
(∀ (fs : Fs) (h : Heap) buf len, Zlib.Gzread.gzread none buf len fs h = .ok ((-1, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) buf size nitems,
Zlib.Gzread.gzfread buf size nitems none fs h = .ok ((0, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) buf len, Zlib.Gzwrite.gzwrite none buf len fs h = .ok ((0, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) buf size nitems,
Zlib.Gzwrite.gzfwrite buf size nitems none fs h = .ok ((0, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) c, Zlib.Gzwrite.gzputc none c fs h = .ok ((-1, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) str, Zlib.Gzwrite.gzputs none str fs h = .ok ((-1, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) format (va : List VaArg),
Zlib.Gzwrite.gzprintf none format va fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) format (va : List VaArg),
Zlib.Gzwrite.gzvprintf none format va fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) flush,
Zlib.Gzwrite.gzflush none flush fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) level strategy,
Zlib.Gzwrite.gzsetparams none level strategy fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
(∀ (fs : Fs) (h : Heap), Zlib.Gzread.gzgetc none fs h = .ok ((-1, fs), h)) ∧
(∀ (fs : Fs) (h : Heap), Zlib.Gzread.gzgetc_ none fs h = .ok ((-1, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) c, Zlib.Gzread.gzungetc c none fs h = .ok ((-1, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) buf len, Zlib.Gzread.gzgets none buf len fs h = .ok ((.null, fs), h)) ∧
(∀ (fs : Fs) (h : Heap), Zlib.Gzread.gzdirect none fs h = .ok ((0, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) offset whence,
Zlib.Gzlib.gzseek none offset whence fs h = .ok ((-1, fs), h)) ∧
(∀ (fs : Fs) (h : Heap) offset whence,
Zlib.Gzlib.gzseek64 none offset whence fs h = .ok ((-1, fs), h)) ∧
(∀ h : Heap, Zlib.Gzlib.gztell none h = .ok (-1, h)) ∧
(∀ h : Heap, Zlib.Gzlib.gztell64 none h = .ok (-1, h)) ∧
(∀ (fs : Fs) (h : Heap), Zlib.Gzlib.gzoffset none fs h = .ok ((-1, fs), h)) ∧
(∀ (fs : Fs) (h : Heap), Zlib.Gzlib.gzoffset64 none fs h = .ok ((-1, fs), h)) ∧
(∀ (fs : Fs) (h : Heap), Zlib.Gzlib.gzrewind none fs h = .ok ((-1, fs), h)) ∧
(∀ h : Heap, Zlib.Gzlib.gzeof none h = .ok (0, h)) ∧
(∀ (h : Heap) errnum, Zlib.Gzlib.gzerror none errnum h = .ok (.null, h)) ∧
(∀ h : Heap, Zlib.Gzlib.gzclearerr none h = .ok ((), h)) ∧
(∀ (h : Heap) size, Zlib.Gzlib.gzbuffer none size h = .ok (-1, h)) ∧
(∀ (fs : Fs) (h : Heap), Zlib.Gzclose.gzclose none fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
(∀ (fs : Fs) (h : Heap), Zlib.Gzread.gzclose_r none fs h = .ok ((Z_STREAM_ERROR, fs), h)) ∧
(∀ (fs : Fs) (h : Heap), Zlib.Gzwrite.gzclose_w none fs h = .ok ((Z_STREAM_ERROR, fs), h))Complete context ↗The premises can be met
inflate_initialisation_domain
/-- Every accepted signed window parameter has a non-failing init on every permitted heap.
The fixed witness additionally rules out an empty caller domain. -/
def Goal.inflate_initialisation_domain : Prop :=
(∀ h r version wb wrap bits,
InitDomain h r version → Api.inflWbits wb.toInt = some (wrap, bits) →
h.allocOk h.nalloc = true →
∃ after, C.run (Zlib.Inflate.inflateInit2_ (some r) wb version 112) h = .ok (Z_OK, after) ∧
InflateInitial h after r wrap bits ∧ StreamReachable .inflate after r) ∧
InitDomain witnessHeap (.tab 0) (.ref (.blk 1) 0) ∧
(∀ wb wrap bits, Api.inflWbits wb.toInt = some (wrap, bits) →
∃ after, C.run (Zlib.Inflate.inflateInit2_ (some (.tab 0)) wb (.ref (.blk 1) 0) 112)
witnessHeap = .ok (Z_OK, after) ∧ InflateInitial witnessHeap after (.tab 0) wrap bits)Complete context ↗deflate_initialisation_domain
/-- Full level, method, window, memory-level and strategy coverage, including normalisation.
No assumption that the post-init invariant already holds is permitted. -/
def Goal.deflate_initialisation_domain : Prop :=
(∀ h r version level method wb mem strategy p,
InitDomain h r version →
Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
(∀ j, j < 5 → h.allocOk (h.nalloc + j) = true) →
∃ after, C.run (Zlib.Deflate.deflateInit2_ (some r) level method wb mem strategy version 112) h =
.ok (Z_OK, after) ∧ DeflateInitial h after r p ∧ StreamReachable .deflate after r) ∧
InitDomain witnessHeap (.tab 0) (.ref (.blk 1) 0) ∧
(∀ level method wb mem strategy p,
Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
∃ after, C.run (Zlib.Deflate.deflateInit2_ (some (.tab 0)) level method wb mem strategy
(.ref (.blk 1) 0) 112) witnessHeap = .ok (Z_OK, after) ∧
DeflateInitial witnessHeap after (.tab 0) p)Complete context ↗inflate_back_initialisation_domain
/-- All eight documented callback-window sizes, with an arbitrary valid caller window.
Init establishes the back-decoder invariant and retains ownership of the window. -/
def Goal.inflate_back_initialisation_domain : Prop :=
(∀ h r version wb window,
InitDomain h r version → 8 ≤ wb.toInt → wb.toInt ≤ 15 →
window ≠ .null → Writable h window (2 ^ wb.toInt.toNat) → h.allocOk h.nalloc = true →
∃ after z s, C.run (Zlib.Infback.inflateBackInit_ (some r) wb window version 112) h =
.ok (Z_OK, after) ∧ BackValid after r h.nextBlk z s ∧ s.window = window ∧
s.wbits = wb.toUInt32 ∧ Frame h after (StreamRoot r) ∧
LiveChange h after (fun b => b = h.nextBlk) (fun _ => False)) ∧
InitDomain witnessHeap (.tab 0) (.ref (.blk 1) 0) ∧
(∀ wb : Int32, 8 ≤ wb.toInt → wb.toInt ≤ 15 →
∃ after z s, C.run (Zlib.Infback.inflateBackInit_ (some (.tab 0)) wb (.ref (.blk 2) 0)
(.ref (.blk 1) 0) 112) witnessHeap = .ok (Z_OK, after) ∧
BackValid after (.tab 0) witnessHeap.nextBlk z s ∧ s.window = .ref (.blk 2) 0)Complete context ↗inflateBack_call_domain
/-- The premises of the call clause of `Goal.inflateBack_safety` hold together on a concrete
history, with a concrete pair of callbacks, a concrete `CallbackProtocol` and a non-empty first
chunk of input in a heap byte block. So that clause is not vacuous: its conclusion holds for this
call of `inflateBack`. A protocol is a structure of obligations, and a set of obligations that no
callback meets would make every statement over "every protocol" true. -/
def Goal.inflateBack_call_domain : Prop :=
∃ (h : Heap) (r : ZStreamRef) (i : Nat) (window : BPtr) (n : Nat) (z : ZStream) (s : InflateState)
(input : Zlib.Infback.InCb) (inDesc : BPtr) (output : Zlib.Infback.OutCb) (outDesc : BPtr)
(protocol : CallbackProtocol r i window n input inDesc output outDesc) (first : List UInt8),
first ≠ [] ∧ z.next_in ≠ .null ∧
BackSafeReachable h r i window n ∧ BackValid h r i z s ∧
Bytes h z.next_in z.avail_in.toNat first ∧
Separate z.next_in first.length window n ∧
protocol.invariant h { supplied := first, chunks := [], active := z.next_in, held := first } ∧
protocol.inputBound < 2 ^ 48 ∧
ZlibF.PlatformMemory.ByteObjectsFit h ∧ BackPlatform protocol ∧ BackFirstChunk z firstComplete context ↗gz_sequence_nonvacuity
/-- **Goal: the premises of `gz_sequence_safety` are satisfiable** (non-vacuity). Two concrete histories, one per
entry point and mode, each from a caller heap and a world that satisfy every premise of the opening constructor of
`GzHistory`, with no allocation failure:
1. `gzopen` gives a reading handle in `GzInv` whose descriptor has a finite read budget (`ReadsFinite`, the premise
of the termination half), and a one-byte `gzread` into a caller buffer satisfies `GzArguments`;
2. `gzdopen` on an open descriptor gives a writing handle in `GzInv` that keeps the descriptor, and a one-byte
`gzwrite` from a caller buffer satisfies `GzArguments`.
So the call clause of `gz_sequence_safety`, and its termination half for a reading call, apply to a real call with a
nonzero length. -/
def Goal.gz_sequence_nonvacuity : Prop :=
(∃ (h : Heap) (fs : Fs) (path mode : BPtr) (name flags : List UInt8) (after : Heap) (fs' : Fs) (i : Nat)
(s : GzState) (buf : BPtr),
Fresh h ∧ Zlib.Gzlib.Spec.Uniq h ∧ LibraryGlobals h ∧ ZlibF.PlatformMemory.ByteObjectsFit h ∧
NoAllocationFailure h ∧ FileSystem fs ∧ CString h path name ∧ CString h mode flags ∧
Zlib.Gzlib.gzopen path mode fs h = .ok ((some (.in_gzstate_x i), fs'), after) ∧
GzHistory after fs' i ∧ after.gzstates i = some s ∧ s.mode = GZ_READ ∧ GzInv after i s ∧
ReadsFinite fs' s.fd ∧
GzOperation i (.gzread (some (.in_gzstate_x i)) buf 1) ∧
NeedsReadBound (.gzread (some (.in_gzstate_x i)) buf 1) ∧
GzArguments after i s (.gzread (some (.in_gzstate_x i)) buf 1)) ∧
(∃ (h : Heap) (fs : Fs) (fd : Int32) (mode : BPtr) (flags : List UInt8) (after : Heap) (fs' : Fs) (i : Nat)
(s : GzState) (buf : BPtr),
Fresh h ∧ Zlib.Gzlib.Spec.Uniq h ∧ LibraryGlobals h ∧ ZlibF.PlatformMemory.ByteObjectsFit h ∧
NoAllocationFailure h ∧ FileSystem fs ∧ 0 ≤ fd.toInt ∧ GzOracle.FdOpen fs fd.toInt.toNat ∧
CString h mode flags ∧
Zlib.Gzlib.gzdopen fd mode fs h = .ok ((some (.in_gzstate_x i), fs'), after) ∧
GzHistory after fs' i ∧ after.gzstates i = some s ∧ s.mode = GZ_WRITE ∧ s.fd = fd ∧ GzInv after i s ∧
GzOperation i (.gzwrite (some (.in_gzstate_x i)) buf 1) ∧
GzArguments after i s (.gzwrite (some (.in_gzstate_x i)) buf 1))Complete context ↗The round trip of the default zlib stream
compress_uncompress_roundtrip
/-- **`uncompress(compress(x)) = x`.** When every allocation succeeds, `compress` with
`compressBound` room returns `Z_OK` and stores the length `m` it wrote; the `m` bytes it wrote,
given to `uncompress` on any heap where every allocation succeeds, with room for the source, give
back the source and its length, with `Z_OK`. -/
def Goal.compress_uncompress_roundtrip : Prop :=
∀ h dest c source n xs,
Fresh h → Zlib.Deflate.Spec.Uniq h → LibraryGlobals h → ZlibF.PlatformMemory.ByteObjectsFit h →
NoAllocationFailure h →
Bytes h source n.toNat xs → Writable h dest c.toNat → Separate source n.toNat dest c.toNat →
¬ compressRejected dest (some c) source n →
Api.compressBound n.toNat ≤ c.toNat →
∃ stored after out, C.run (Zlib.Compress.compress dest (some c) source n) h = .ok ((Z_OK, stored), after) ∧
out.length = stored.toNat ∧ Bytes after dest stored.toNat out ∧
∀ h₂ dest₂ destLen₂ source₂ capacity₂,
Fresh h₂ → Zlib.Inflate.Spec.Uniq h₂ → LibraryGlobals h₂ →
ZlibF.PlatformMemory.ByteObjectsFit h₂ → NoAllocationFailure h₂ →
LengthCell h₂ destLen₂ capacity₂ → destLen₂ ≠ .null → source₂ ≠ .null → dest₂ ≠ .null →
Bytes h₂ source₂ stored.toNat out → Writable h₂ dest₂ capacity₂.toNat →
Separate source₂ stored.toNat dest₂ capacity₂.toNat →
Separate destLen₂ 8 dest₂ capacity₂.toNat → Separate destLen₂ 8 source₂ stored.toNat →
n.toNat ≤ capacity₂.toNat →
∃ after₂, C.run (Zlib.Uncompr.uncompress dest₂ destLen₂ source₂ stored) h₂ = .ok (Z_OK, after₂) ∧
Bytes after₂ dest₂ n.toNat xs ∧ LengthCell after₂ destLen₂ nComplete context ↗compress_uncompress_roundtrip_witness
/-- **Non-vacuity of `Goal.compress_uncompress_roundtrip`.** There is a heap, a destination and a
non-empty source on which every premise of the `compress` half holds; and for every output `out`
that `compress` can produce there (`stored` bytes, at most `compressBound n`), a second heap,
destination, length cell and source holding `out` on which every premise of the `uncompress` half
holds. -/
def Goal.compress_uncompress_roundtrip_witness : Prop :=
∃ h dest c source n xs,
Fresh h ∧ Zlib.Deflate.Spec.Uniq h ∧ LibraryGlobals h ∧ ZlibF.PlatformMemory.ByteObjectsFit h ∧
NoAllocationFailure h ∧
xs ≠ [] ∧
Bytes h source n.toNat xs ∧ Writable h dest c.toNat ∧ Separate source n.toNat dest c.toNat ∧
¬ compressRejected dest (some c) source n ∧ Api.compressBound n.toNat ≤ c.toNat ∧
∀ (stored : UInt64) (out : List UInt8), stored.toNat ≤ Api.compressBound n.toNat →
out.length = stored.toNat →
∃ h₂ dest₂ destLen₂ source₂ capacity₂,
Fresh h₂ ∧ Zlib.Inflate.Spec.Uniq h₂ ∧ LibraryGlobals h₂ ∧
ZlibF.PlatformMemory.ByteObjectsFit h₂ ∧ NoAllocationFailure h₂ ∧
LengthCell h₂ destLen₂ capacity₂ ∧ destLen₂ ≠ .null ∧ source₂ ≠ .null ∧ dest₂ ≠ .null ∧
Bytes h₂ source₂ stored.toNat out ∧ Writable h₂ dest₂ capacity₂.toNat ∧
Separate source₂ stored.toNat dest₂ capacity₂.toNat ∧
Separate destLen₂ 8 dest₂ capacity₂.toNat ∧ Separate destLen₂ 8 source₂ stored.toNat ∧
n.toNat ≤ capacity₂.toNatComplete context ↗compress_completes
/-- `compress` (the default level) completes with `compressBound` room. -/
def Goal.compress_completes : Prop :=
CompressCompletes (fun d c s n => do
let (rc, size) ← Zlib.Compress.compress d c s n
pure (rc, some size))Complete context ↗compress_z_completes
/-- `compress_z` (the default level) completes with `compressBound` room. -/
def Goal.compress_z_completes : Prop :=
CompressCompletes Zlib.Compress.compress_zComplete context ↗uncompress_completes
/-- **`uncompress` completes on a complete stream.** The `n` source bytes are a zlib stream that
does not ask for a preset dictionary and decodes to `xs`, and the destination holds at least
`xs.length` bytes:
when every allocation succeeds, `uncompress` returns `Z_OK`, writes `xs` and stores its length. -/
def Goal.uncompress_completes : Prop :=
∀ h dest destLen source capacity n stream xs,
Fresh h → Zlib.Inflate.Spec.Uniq h → LibraryGlobals h → ZlibF.PlatformMemory.ByteObjectsFit h →
NoAllocationFailure h →
LengthCell h destLen capacity → destLen ≠ .null → source ≠ .null → dest ≠ .null →
Bytes h source n.toNat stream → Writable h dest capacity.toNat →
Separate source n.toNat dest capacity.toNat →
Separate destLen 8 dest capacity.toNat → Separate destLen 8 source n.toNat →
Zlib.Decodes [] stream xs → ¬ AsksDictionary stream → xs.length ≤ capacity.toNat →
∃ after, C.run (Zlib.Uncompr.uncompress dest destLen source n) h = .ok (Z_OK, after) ∧
Bytes after dest xs.length xs ∧ LengthCell after destLen (UInt64.ofNat xs.length)Complete context ↗stream_roundtrip_total
/-- **The stream round trip, unconditional form.** The default encoder ends under every finishing
schedule, with an output that decodes to its input (`Goal.deflate_finish_ends`); and the default
decoder, given that output under every chunking, ends with exactly the encoder's input
(`Goal.inflate_chain_ends`). -/
def Goal.stream_roundtrip_total : Prop :=
Goal.deflate_finish_ends ∧ Goal.inflate_chain_endsComplete context ↗deflate_finish_ends
/-- **The default encoder ends under every finishing schedule.** After any default history (any
flush values, any chunking) that has not ended, with the remaining input `input` at the input
pointer: there is a number `N` such that every continuation by `Z_FINISH` calls with positive
room that offers the rest of `input` has, while unfinished, made at most `N` calls; and once it
ends it has accepted all of `input` and its whole output decodes to its whole input. No bound on
the room is needed. -/
def Goal.deflate_finish_ends : Prop :=
∀ r h log z input,
DefaultDeflateHistory r h log → log.finished = false →
r.get h = some z → StreamBuffers h r → Bytes h z.next_in z.avail_in.toNat input →
(∀ ds d, z.state = some (.deflate ds) → h.dstates ds = some d →
d.status = FINISH_STATE → input = []) →
∃ N, ∀ k after final, DefaultFinishChain r log.input input k h log after final →
(final.finished = false → k ≤ N) ∧
(final.finished = true → final.input = log.input ++ input ∧
Zlib.Decodes [] final.output final.input)Complete context ↗inflate_chain_ends
/-- **The default decoder ends under every chunking.** `encoded` is a complete default stream. From
a default decoder that has read a prefix of it and has not ended, there is a number `N` such that
every continuation of `inflate` calls on the rest of the stream (`DefaultInflateChain`) has, while
unfinished, made at most `N` calls; and once it ends it has consumed the whole stream and written
exactly the encoder's input. -/
def Goal.inflate_chain_ends : Prop :=
∀ rd hd encoded ri hi decoded,
DefaultDeflateHistory rd hd encoded → encoded.result = Z_STREAM_END →
DefaultInflateTrace ri hi decoded → decoded.finished = false →
decoded.input <+: encoded.output →
∃ N, ∀ k after final,
DefaultInflateChain ri encoded.output encoded.input k hi decoded after final →
(final.finished = false → k ≤ N) ∧
(final.finished = true → final.input = encoded.output ∧ final.output = encoded.input)Complete context ↗stream_roundtrip
/-- **The stream round trip, conditional form.** A default zlib stream written by `deflate`
under any flush values and any chunking, and read by `inflate` under any chunking: when both
histories reach `Z_STREAM_END` and the decoder read a prefix of the encoder's output, the
decoder's output is the encoder's input. The two histories run on separate heaps. -/
def Goal.stream_roundtrip : Prop :=
∀ (rd ri : ZStreamRef) (hd hi : Heap) (encoded decoded : DataLog),
DefaultDeflateHistory rd hd encoded → DefaultInflateHistory ri hi decoded →
encoded.result = Z_STREAM_END → decoded.result = Z_STREAM_END →
(∃ trailing, encoded.output = decoded.input ++ trailing) →
decoded.output = encoded.inputComplete context ↗deflate_completes_default
/-- **Completion of the default stream from the bound.** After a clean default history that has
not ended, a `deflate(Z_FINISH)` call offered all the remaining input `input`, with output room
more than what the bound of the whole input leaves after the output so far, returns
`Z_STREAM_END`: it accepts all of `input`, and the whole output decodes to the whole input. The
stream can be exactly as long as the bound, and a call that first delivers pending output and is
left with no room returns `Z_OK` (`deflate.c`), so room equal to the rest is not enough after an
earlier call; one call from a fresh stream needs only the bound (`Goal.deflate_bound_default`). The room is measured against `unsaturatedBound` of the whole input, which is
`compressBound` of the whole input below the saturation point. `zlib.h` promises nothing once
`compressBound` saturates at `2^64 - 1`, and a history may accept more input than that. At these
parameters `deflateBound` is `compressBound` (`Goal.deflate_bound_default`). Before
`Z_STREAM_END`, a `Z_FINISH` already given keeps the caller from offering new input. -/
def Goal.deflate_completes_default : Prop :=
∀ r h log z input,
DefaultCleanHistory r h log → log.finished = false →
r.get h = some z → StreamBuffers h r → z.next_out ≠ .null →
Bytes h z.next_in z.avail_in.toNat input →
(∀ ds d, z.state = some (.deflate ds) → h.dstates ds = some d →
d.status = FINISH_STATE → input = []) →
0 < z.avail_out.toNat →
unsaturatedBound (log.input.length + input.length) < log.output.length + z.avail_out.toNat →
∃ after output, DataStep .deflate h after r Z_FINISH Z_STREAM_END input output input.length ∧
Zlib.Decodes [] (log.output ++ output) (log.input ++ input)Complete context ↗deflate_bound_default
/-- **The promise of `deflateBound`, default stream** (`zlib.h`): after `deflateInit` and caller
edits only, `deflateBound(strm, n)` returns `b`; then one `deflate(Z_FINISH)` offered all `n`
input bytes with at least `b` bytes of room returns `Z_STREAM_END`, accepts all input, and writes
a stream that decodes to the input. -/
def Goal.deflate_bound_default : Prop :=
∀ r h log z input n b,
DefaultCleanHistory r h log → log.input = [] → log.output = [] → log.finished = false →
C.run (Zlib.Deflate.deflateBound (some r) n) h = .ok (b, h) →
r.get h = some z → StreamBuffers h r → z.next_out ≠ .null →
Bytes h z.next_in z.avail_in.toNat input → input.length = n.toNat →
b.toNat ≤ z.avail_out.toNat →
∃ after output, DataStep .deflate h after r Z_FINISH Z_STREAM_END input output input.length ∧
Zlib.Decodes [] output inputComplete context ↗inflate_completes_default
/-- **Completion of `inflate` on a default stream.** `encoded` is a complete default stream: the
output of a default deflate history that ended. A default decoder (`DefaultInflateTrace`) that has
read a prefix of it and has not ended, offered exactly the rest of the stream with room for the
rest of the input, on a heap where every allocation succeeds, returns `Z_STREAM_END` and writes
exactly the rest of the input. -/
def Goal.inflate_completes_default : Prop :=
∀ rd hd encoded ri hi decoded z flush,
DefaultDeflateHistory rd hd encoded → encoded.result = Z_STREAM_END →
DefaultInflateTrace ri hi decoded → decoded.finished = false →
decoded.input <+: encoded.output →
ri.get hi = some z → StreamBuffers hi ri → z.next_out ≠ .null →
ZlibF.PlatformMemory.ByteObjectsFit hi → NoAllocationFailure hi →
Bytes hi z.next_in z.avail_in.toNat (encoded.output.drop decoded.input.length) →
encoded.input.length ≤ decoded.output.length + z.avail_out.toNat → OrdinaryFlush flush →
∃ after, C.run (Zlib.Inflate.inflate (some ri) flush) hi = .ok (Z_STREAM_END, after) ∧
Bytes after z.next_out (encoded.input.length - decoded.output.length)
(encoded.input.drop decoded.output.length)Complete context ↗default_inflate_progress
/-- Progress of the default decoder on a valid stream, under any chunking. -/
def Goal.default_inflate_progress : Prop :=
∀ (r : ZStreamRef) (h : Heap) (log : DataLog) (S D input : List UInt8) (z : ZStream) (flush : Int32),
DefaultInflateTrace r h log → log.finished = false →
Zlib.Decodes [] S D → log.input <+: S →
ZlibF.PlatformMemory.ByteObjectsFit h → NoAllocationFailure h → StreamBuffers h r →
r.get h = some z → z.next_out ≠ .null → (z.avail_out ≠ 0 ∨ log.output = D) →
Bytes h z.next_in z.avail_in.toNat input → log.input ++ input <+: S →
(input ≠ [] ∨ log.input = S) → OrdinaryFlush flush →
∃ rc after output used, DataStep .inflate h after r flush rc input output used ∧
((rc = Z_STREAM_END ∧ log.input ++ input.take used = S ∧ log.output ++ output = D) ∨
((rc = Z_OK ∨ (rc = Z_BUF_ERROR ∧ flush = Z_FINISH)) ∧ (used ≠ 0 ∨ output ≠ []) ∧
log.input ++ input.take used <+: S ∧ log.output ++ output <+: D) ∨
(rc = Z_NEED_DICT ∧ AsksDictionary S ∧ log.output ++ output = []))Complete context ↗default_inflate_completes
/-- Completion of the default decoder in one call: the whole rest of a valid stream and room for
the rest of its decoding. -/
def Goal.default_inflate_completes : Prop :=
∀ (r : ZStreamRef) (h : Heap) (log : DataLog) (S D : List UInt8) (z : ZStream) (flush : Int32),
DefaultInflateTrace r h log → log.finished = false →
Zlib.Decodes [] S D → log.input <+: S →
ZlibF.PlatformMemory.ByteObjectsFit h → NoAllocationFailure h → StreamBuffers h r →
r.get h = some z → z.next_out ≠ .null →
Bytes h z.next_in z.avail_in.toNat (S.drop log.input.length) →
D.length ≤ log.output.length + z.avail_out.toNat → OrdinaryFlush flush →
∃ rc after output used, DataStep .inflate h after r flush rc (S.drop log.input.length) output used ∧
((rc = Z_STREAM_END ∧ used = S.length - log.input.length ∧ log.output ++ output = D) ∨
(rc = Z_NEED_DICT ∧ AsksDictionary S ∧ log.output ++ output = []))Complete context ↗Full sequence contracts (beyond safety)
inflate_sequence
State: not done, not planned
/-- All legal public histories are safe and retain cleanup. For ordinary data epochs every
input/output split is covered, including allocation failures and dictionary handshakes.
The functional clauses use protocol-admitted histories, with one successful wrapped
dictionary installation per NEED_DICT request. Successful acceptance uses the configured
dictionary window; valid-input prefix and completion use the unchanged RFC byte format. -/
def Goal.inflate_sequence : Prop :=
StreamSequenceSafety .inflate ∧
(∀ wb wrap bits r h log, Api.inflWbits wb.toInt = some (wrap, bits) →
AllowedInflateProtocol wb r h log →
(log.singleDictionary = true → log.result = Z_STREAM_END →
Api.Layer.InflateAccepted wrap bits log.dictionary log.input log.output) ∧
(∀ source decoded, Api.Layer.Decodes wrap bits log.dictionary source decoded →
log.singleDictionary = true → Api.FullWindow wrap bits source → log.input <+: source →
log.output <+: decoded ∧ log.result ≠ Z_DATA_ERROR ∧
(log.result = Z_STREAM_END → log.input = source ∧ log.output = decoded))) ∧
InflateCompletesComplete context ↗deflate_sequence
State: not done, not planned
/-- All legal public histories are safe and retain cleanup. A finished ordinary data epoch
encodes exactly its accepted input, for every accepted parameter set and flush schedule.
A completed `Z_SYNC_FLUSH` or `Z_FULL_FLUSH` (`Z_OK` with output space left, `zlib.h`) has
consumed all offered input, and the output so far ends at a flush point that produces exactly
the input so far. After a completed `Z_FULL_FLUSH`, the rest of a finished stream decodes
without the earlier data. A successful call leaves the Adler-32 (zlib) or CRC-32 (gzip) of
the accepted input in `adler`. Before any output, `deflateBound` returns the bound that
`DeflateCompletes` uses. -/
def Goal.deflate_sequence : Prop :=
StreamSequenceSafety .deflate ∧
(∀ level method wb mem strategy p r h log,
Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
DeflateDataTrace level method wb mem strategy r h log →
log.result = Z_STREAM_END → DecodesFor p log.dictionary log.output log.input) ∧
(∀ level method wb mem strategy p r h log after flush rc input output used z',
Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
DeflateDataTrace level method wb mem strategy r h log →
DataStep .deflate h after r flush rc input output used →
(flush = Z_SYNC_FLUSH ∨ flush = Z_FULL_FLUSH) → rc = Z_OK →
r.get after = some z' → z'.avail_out ≠ 0 →
let log₁ := deflateLogStep log flush rc input output used
z'.avail_in = 0 ∧ FlushedFor p log₁.dictionary log₁.output log₁.input ∧
(flush = Z_FULL_FLUSH → ∀ h₂ log₂, DeflateDataRun r after log₁ h₂ log₂ →
log₂.result = Z_STREAM_END →
∃ tail, Deflate.Prefix [] (log₂.output.drop log₁.output.length) tail
(log₂.input.drop log₁.input.length))) ∧
(∀ level method wb mem strategy p r h log after flush rc input output used z',
Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
DeflateDataTrace level method wb mem strategy r h log →
DataStep .deflate h after r flush rc input output used →
(rc = Z_OK ∨ rc = Z_STREAM_END) → r.get after = some z' →
let accepted := log.input ++ input.take used
(p.wrap = .zlib → z'.adler.toNat = (ZlibF.Spec.adler32 accepted).toNat) ∧
(p.wrap = .gzip → z'.adler.toNat = (ZlibF.Spec.crc32 accepted).toNat)) ∧
(∀ level method wb mem strategy p r h log n,
Api.deflInit? level.toInt method.toInt wb.toInt mem.toInt strategy.toInt = some p →
DeflateDataTrace level method wb mem strategy r h log → log.output = [] →
let bound := UInt64.ofNat (min (({ Api.DeflState.fresh p with dict := some log.dictionary }).bound
n.toNat) (2 ^ 64 - 1))
C.run (Zlib.Deflate.deflateBound_z (some r) n) h = .ok (bound, h) ∧
C.run (Zlib.Deflate.deflateBound (some r) n) h = .ok (bound, h)) ∧
DeflateCompletesComplete context ↗inflate_back_sequence
State: not done, not planned
/-- Includes actual callback execution and raw-format delivery, re-use of the window, and
complete end cleanup. Callback memory and returning/finite-input obligations remain explicit. -/
def Goal.inflate_back_sequence : Prop :=
Goal.inflateBack ∧
(∀ h r i window n, BackReachable h r i window n →
(∃ z s, BackValid h r i z s ∧ s.window = window ∧ s.wsize.toNat = n) ∧
∃ after z, C.run (Zlib.Infback.inflateBackEnd (some r)) h = .ok (Z_OK, after) ∧
r.get after = some z ∧ z.state = none ∧
Frame h after (fun b => StreamRoot r b ∨ b = i) ∧
LiveChange h after (fun _ => False) (fun b => b = i))Complete context ↗gz_sequence
State: not done, not planned
/-- The gz lifecycle includes every admitted operation, external file growth and final close.
The per-entry read contracts express transparent/concatenated-member decoding and the
per-entry write contracts account for accepted bytes and seek zeros. -/
def Goal.gz_sequence : Prop :=
(∀ h fs i, GzReachable h fs i → FileSystem fs ∧ ∃ s, GzValid h i s) ∧
(∀ h fs i s call, GzReachable h fs i → h.gzstates i = some s →
GzOperation i call → GzArguments h i s call → RegularOs fs →
∃ value fs' after s', call.execute fs h = .ok ((value, fs'), after) ∧
GzValid after i s' ∧ FileSystem fs' ∧
LiveChange h after
(fun b => GzOwned after i s' b ∧ ¬ h.live b)
(fun b => GzOwned h i s b ∧ ¬ GzOwned after i s' b)) ∧
(∀ h fs i s, GzReachable h fs i → h.gzstates i = some s →
∃ rc fs' after, Zlib.Gzclose.gzclose (some (.in_gzstate_x i)) fs h = .ok ((rc, fs'), after) ∧
CloseEffects h after fs fs' i s) ∧
Goal.gzread ∧ Goal.gzfread ∧ Goal.gzgetc ∧ Goal.gzgets ∧
Goal.gzwrite ∧ Goal.gzfwrite ∧ Goal.gzflush ∧ Goal.gzclose ∧ GzWriterFormatComplete context ↗