Browse zstd specs (31 of 44)
Proofs / zstd / Earlier, longer properties
x_any_info_extra
ZSTD_getDecompressedSize and ZSTD_getFrameHeader_advanced on any bytes, as documented.
- spec
- 55 lines of C
- status
- Proved
- 31 of 44
On this page
The spec
The spec is the C program harness/x_any_info_extra.c, 55 lines, shown whole as it is in the repository at 2e46017. Its first comment states the property in full, with every bound.
// Law any_info_extra (PROMISES.md: S1, I7, I8): the inspection functions not in any_info, on ANY bytes:
// ZSTD_getDecompressedSize (obsolete, stable API): "Both functions work the same way, but ZSTD_getDecompressedSize()
// blends "empty", "unknown" and "error" results to the same return value (0), while ZSTD_getFrameContentSize()
// gives them separate return values" (I7);
// ZSTD_getFrameHeader_advanced (experimental): "same as ZSTD_getFrameHeader(), with added capability to select a
// format (like ZSTD_f_zstd1_magicless)" (I8).
//
// Claim (QuickProof.Contract.harness_safe of this program): no execution has undefined behaviour, and every gp_assert
// holds: ZSTD_getDecompressedSize is ZSTD_getFrameContentSize with ZSTD_CONTENTSIZE_UNKNOWN and ZSTD_CONTENTSIZE_ERROR
// mapped to 0; ZSTD_getFrameHeader_advanced with ZSTD_f_zstd1 returns what ZSTD_getFrameHeader returns, and on 0 the
// same header fields; with ZSTD_f_zstd1_magicless it returns 0 (with headerSize <= srcSize), or "> 0 => srcSize is
// too small, @return value is the wanted srcSize amount" (> srcSize), or an error. Draw order n, bytes (env.c).
#include <stdlib.h>
#include "quickproof.h"
#ifndef ZSTD_STATIC_LINKING_ONLY
#define ZSTD_STATIC_LINKING_ONLY /* ZSTD_getFrameHeader_advanced */
#endif
#include "zstd.h"
#define SRC_MAX 4096
int main(void)
{
size_t n = nondet_size(), r, r2;
unsigned char *src;
unsigned long long fcs, ds;
ZSTD_FrameHeader h1, h2;
gp_assume(n <= SRC_MAX);
src = malloc(n > 0 ? n : 1);
if (src == NULL)
return 0; /* harness out of memory: end the run */
nondet_bytes(src, n);
fcs = ZSTD_getFrameContentSize(src, n);
ds = ZSTD_getDecompressedSize(src, n);
gp_assert(ds == ((fcs == ZSTD_CONTENTSIZE_UNKNOWN || fcs == ZSTD_CONTENTSIZE_ERROR) ? 0 : fcs));
r = ZSTD_getFrameHeader(&h1, src, n);
r2 = ZSTD_getFrameHeader_advanced(&h2, src, n, ZSTD_f_zstd1);
gp_assert(r2 == r);
if (r == 0) {
gp_assert(h2.frameContentSize == h1.frameContentSize);
gp_assert(h2.windowSize == h1.windowSize);
gp_assert(h2.blockSizeMax == h1.blockSizeMax);
gp_assert(h2.frameType == h1.frameType);
gp_assert(h2.headerSize == h1.headerSize);
gp_assert(h2.dictID == h1.dictID);
gp_assert(h2.checksumFlag == h1.checksumFlag);
}
r = ZSTD_getFrameHeader_advanced(&h2, src, n, ZSTD_f_zstd1_magicless);
if (r == 0)
gp_assert(h2.headerSize <= n);
else if (!ZSTD_isError(r))
gp_assert(r > n);
free(src);
return 0;
}The theorem
QuickProof generated this statement from the spec, in src/contracts/x_any_info_extra.v:
Theorem x_any_info_extra : 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_info_extra : harness_safe Zstd.contracts.x_any_info_extra.whole_prog.
Proof. exact (proj1 (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.