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.

C
// 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:

Rocq
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:

Rocq
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.c
  • quickproof/libc/libc.c
  • quickproof/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.