Browse zstd specs (26 of 44)
Proofs / zstd / Earlier, longer properties
x_any_oneshot
One-shot decompression of any bytes into any capacity: an error or at most the capacity; ZSTD_freeDCtx accepts NULL.
- spec
- 52 lines of C
- status
- Proved
- 26 of 44
On this page
The spec
The spec is the C program harness/x_any_oneshot.c, 52 lines, shown whole as it is in the repository at 2e46017. Its first comment states the property in full, with every bound.
// Law any_oneshot (PROMISES.md: S1, S3, S6, V7): one-shot decompression of ANY bytes into ANY capacity.
//
// Claim (QuickProof.Contract.harness_safe of this program): no execution has undefined behaviour, and every gp_assert
// holds: ZSTD_decompress, and ZSTD_decompressDCtx on a context used before (also after an error: "reset is implied
// for operations starting some new decompression job"), return an error or "the number of bytes decompressed into
// `dst` (<= `dstCapacity`)"; ZSTD_freeDCtx accepts NULL. Buffers have exactly the size of their contents; src and
// dst are separate objects. Draw order n, bytes, cap, twice (env.c hands out real frames this way).
#include <stdlib.h>
#include "quickproof.h"
#include "zstd.h"
#define SRC_MAX 4096
#define DST_MAX 65536
int main(void)
{
unsigned char *src[2], *dst[2];
size_t n[2], cap[2], r;
unsigned i;
ZSTD_DCtx *dctx;
for (i = 0; i < 2; i++) {
n[i] = nondet_size();
gp_assume(n[i] <= SRC_MAX);
src[i] = malloc(n[i]);
if (src[i] == NULL)
return 0; /* harness out of memory: end the run */
nondet_bytes(src[i], n[i]);
cap[i] = nondet_size();
gp_assume(cap[i] <= DST_MAX);
dst[i] = malloc(cap[i]);
if (dst[i] == NULL)
return 0;
}
r = ZSTD_decompress(dst[0], cap[0], src[0], n[0]);
if (!ZSTD_isError(r))
gp_assert(r <= cap[0]);
dctx = ZSTD_createDCtx();
if (dctx != NULL) {
for (i = 0; i < 2; i++) {
r = ZSTD_decompressDCtx(dctx, dst[i], cap[i], src[i], n[i]);
if (!ZSTD_isError(r))
gp_assert(r <= cap[i]);
}
}
ZSTD_freeDCtx(dctx);
ZSTD_freeDCtx(NULL);
for (i = 0; i < 2; i++) {
free(src[i]);
free(dst[i]);
}
return 0;
}The theorem
QuickProof generated this statement from the spec, in src/contracts/x_any_oneshot.v:
Theorem x_any_oneshot : harness_safe whole_prog.src/contracts/laws.v states it on the spec's own program, whole_prog (the spec linked with the code under test), with its proof:
Theorem x_any_oneshot : harness_safe Zstd.contracts.x_any_oneshot.whole_prog.
Proof. exact (proj1 (proj2 (proj2 (proj2 (proj2 (proj2 Zstd.contracts.suite.suite_x)))))). Qed.Read as a statement about runs, it says that no run of the program has undefined behaviour or a failing check, for every value the spec can draw. That reading rests on VST's adequacy theorem, which is not yet instantiated in Rocq (formerly Coq) for QuickProof's environment.
The C files (units) its program links
patch/decoder.cquickproof/libc/libc.cquickproof/libc/malloc_unit.c
What it leaves out
- What the first comment of the spec excludes, and its bounds.
- Like every spec of this proof: termination (a run that never returns is not a counterexample), one thread, and binaries built by a compiler (the theorem is about the code as CompCert defines C for x86_64, LP64).
- Other configurations of zstd (flags, legacy formats, assembly) and the compressor.
- The edits to zstd's code, listed in the repository, are checked against the original by testing, not proved.
The summary page says what the proof as a whole covers.
How it was proved
AI agents wrote the proof, and Rocq checks it. qp verify passes on this repository: this statement is the one generated from the spec at the contract commit, and its proof uses only Rocq's standard axioms and VST's abstract malloc library.