Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

zlib.h, crc32_z() — the compiled crc32_z computes CRC-32

Open
ZlibCrc32.subroutineOk_crc32_z

by dbenbenn · Nov 22, 2026 · Mathlib 0df444a (Lean v4.33.1)

aarch64crcmachine-code-verificationseparation-logiczlib

Total correctness of crc32_z in the AArch64 object code of zlib 1.3.1's crc32.c (zlibCrc32Lib). For every placement of the library that the linker could produce (Placeable), every frame RRR and every entry state at the address of crc32_z with the stack pointer 16-byte aligned, whose memory satisfies the precondition separately from RRR, execution terminates. It returns to the caller (the link register) with the stack pointer and the callee-saved registers restored, RRR untouched, and the postcondition holding. It never panics, exits or runs out of memory.

The arguments follow AAPCS64: crc in x0, buf in x1, len in x2, the result in x0. In every case the caller lends the 96 bytes below the stack pointer (any contents) and the library's three tables in their initial state, and gets both back.

  • buf = Z_NULL (x1 = 0), any crc and len: the result is 000.
  • buf ≠ Z_NULL, with the bytes b0,…,bn−1b_0, \dots, b_{n-1}b0​,…,bn−1​ readable at buf and len =n= n=n: the result is a 32-bit value (upper half of x0 zero) whose polynomial is CRCu(M,v)\mathrm{CRC}_u(M, v)CRCu​(M,v). Here MMM is the message of b0…bn−1b_0 \dots b_{n-1}b0​…bn−1​ (bit iii of byte jjj is message bit 8j+i8j + i8j+i), vvv is the polynomial of the low 32 bits of crc, PPP is the CRC-32 polynomial and u=x31+⋯+x+1u = x^{31} + \dots + x + 1u=x31+⋯+x+1. The buffer is handed back unchanged.

Polynomials of 32-bit values are Kadatch–Jenkins' register convention: bit iii is the coefficient of x31−ix^{31-i}x31−i.

zlib.h, lines 1732–1736 and 1751: “Update a running CRC-32 with the bytes buf[0..len-1] and return the updated CRC-32. A CRC-32 value is in the range of a 32-bit unsigned integer. If buf is Z_NULL, this function returns the required initial value for the crc. Pre- and post-conditioning (one's complement) is performed within this function so it shouldn't be done by the application.” (of crc32), and of crc32_z: “Same as crc32(), but with a size_t length.”

Preamble
import Mathlib
import Definitions.Def_ZlibCrc32_Spec
Formal statement
namespace ZlibCrc32

theorem subroutineOk_crc32_z : zlibCrc32Lib.subroutineOk "crc32_z" crc32zSpec := by
  sorry

end ZlibCrc32
Source
zlib 1.3.1 (J.-l. Gailly and M. Adler, January 22, 2024; https://zlib.net/fossils/zlib-1.3.1.tar.gz, SHA-256 9a93b2b7dfdac77ceba5a558a580e74667dd6fede4585b91eefb60f03b72df23), zlib.h lines 1730–1752 (crc32, crc32_z)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

What the statement asserts

The statement is a correctness contract for the routine named "crc32_z" in a fixed AArch64 machine-code library (the library called "zlibCrc32" below), proved against a formal model of AArch64 execution. It is the conjunction of two claims.

Claim 1. The name "crc32_z" is in the library's export list. (That list is "crc32_z", "crc32", "crc32_combine", "crc32_combine64", "crc32_combine_gen", "crc32_combine_gen64", "crc32_combine_op", "get_crc_table".)

Claim 2. For every placement π\piπ of the library that is admissible (defined below), the program obtained by loading the library at π\piπ satisfies the subroutine contract described below, with entry point π.base+12\pi.\mathrm{base} + 12π.base+12.

The library

The library has one code block, a fixed list of 2824 bytes (706 four-byte instruction words, read little-endian), with symbols at byte offsets "get_crc_table" 0, "crc32_z" 12, "crc32" 2044, "crc32_combine64" 2052, "crc32_combine" 2256, "crc32_combine_gen64" 2460, "crc32_combine_gen" 2604, "crc32_combine_op" 2748. It has no external symbols and no weak references. It has 17 relocation entries, all with addend 0: page-address/low-12-bit pairs (an "adrp" fix-up at offset ooo and an "add" fix-up at o+4o+4o+4) at o=0,28,1040o = 0, 28, 1040o=0,28,1040 referring to the data symbol "crc_table [zlib_crc32]", at o=456o = 456o=456 referring to "crc_braid_table [zlib_crc32]", at o=2072,2276,2476,2620o = 2072, 2276, 2476, 2620o=2072,2276,2476,2620 referring to "x2n_table [zlib_crc32]"; and one 26-bit branch fix-up at offset 2048 whose target is the library's own symbol "crc32_z".

It has three read-only data objects, each with alignment 4, no relocations and no zero padding: "crc_table [zlib_crc32]" (a fixed list of 1024 bytes, call it T0T_0T0​), "crc_braid_table [zlib_crc32]" (8192 bytes, T1T_1T1​), "x2n_table [zlib_crc32]" (128 bytes, T2T_2T2​).

Placements

A placement π\piπ consists of: a 64-bit code base address π.base\pi.\mathrm{base}π.base; a function ρ\rhoρ from symbol names to 64-bit addresses (used here for the three data objects); a relaxation flag relax(o)∈{true,false}\mathrm{relax}(o) \in \{\text{true},\text{false}\}relax(o)∈{true,false} for each code offset ooo; a "branch-to-branch" flag for each offset; and an "undefined weak symbol" flag for each name. All address arithmetic is modulo 2642^{64}264.

Loaded code. The program's code bytes are the library's code with every relocated word patched for π\piπ:

  • A word with no relocation entry is unchanged.
  • For each adrp/add pair at offsets o,o+4o, o+4o,o+4 (all eight pairs in this library meet the structural pattern for relaxation): if relax(o)\mathrm{relax}(o)relax(o) is true, the word at ooo becomes a no-op and the word at o+4o+4o+4 becomes a PC-relative "adr" into the same destination register, encoding the 21-bit offset from address π.base+o+4\pi.\mathrm{base}+o+4π.base+o+4 to the target; otherwise the word at ooo gets the 21-bit page difference between the target's 4 KiB page and the page of π.base+o\pi.\mathrm{base}+oπ.base+o, and the word at o+4o+4o+4 gets the low 12 bits of the target. The target is ρ\rhoρ of the data symbol named.
  • The branch at offset 2048 gets the low 26 bits of (target−place)/4(\text{target} - \text{place})/4(target−place)/4, where the target is π.base+12\pi.\mathrm{base} + 12π.base+12 (the symbol "crc32_z" resolves inside the library) and the place is π.base+2048\pi.\mathrm{base}+2048π.base+2048. The branch-to-branch and weak-symbol flags have no effect on this library.

The program has base π.base\pi.\mathrm{base}π.base, these patched bytes as code, the library's symbol table, no external-call stubs, no external hooks and no override hooks, and the model's standard system-call handler.

Admissible placement. π\piπ is admissible iff all of the following hold (with ∣C∣=2824|C| = 2824∣C∣=2824 the code length):

  • π.base≡0(mod4)\pi.\mathrm{base} \equiv 0 \pmod 4π.base≡0(mod4), and π.base+2824≤264\pi.\mathrm{base} + 2824 \le 2^{64}π.base+2824≤264 (as natural numbers; the code does not wrap around);
  • for each adrp relocation at offset ooo (with target t=ρ(its symbol)t = \rho(\text{its symbol})t=ρ(its symbol), place p=π.base+op = \pi.\mathrm{base}+op=π.base+o), whatever the value of relax(o)\mathrm{relax}(o)relax(o): the page difference page(t)−page(p)\mathrm{page}(t) - \mathrm{page}(p)page(t)−page(p) (where page(x)\mathrm{page}(x)page(x) clears the low 12 bits; difference taken mod 2642^{64}264 and read in two's complement) lies in [−232,232)[-2^{32}, 2^{32})[−232,232). The "add" relocations impose no condition;
  • for the branch at 2048: (π.base+12)−(π.base+2048)(\pi.\mathrm{base}+12) - (\pi.\mathrm{base}+2048)(π.base+12)−(π.base+2048), read as a signed 64-bit number, is divisible by 4 and lies in [−227,227)[-2^{27}, 2^{27})[−227,227) (this holds automatically);
  • for each pair whose relax(o)\mathrm{relax}(o)relax(o) is true: the signed difference t−(π.base+o+4)t - (\pi.\mathrm{base} + o + 4)t−(π.base+o+4) lies in [−220,220)[-2^{20}, 2^{20})[−220,220);
  • the relocation offsets are distinct, multiples of 4, and at most 282028202820; symbol offsets are multiples of 4 and at most 2824; code length is a multiple of 4 (all automatic for this library);
  • the three data symbol names are distinct and none is a code symbol (automatic), and for each data object ddd of length ndn_dnd​: ρ(d)≡0(mod4)\rho(d) \equiv 0 \pmod 4ρ(d)≡0(mod4) and ρ(d)+nd≤264\rho(d) + n_d \le 2^{64}ρ(d)+nd​≤264.

Nothing in admissibility requires the code region, the three tables and one another to be disjoint.

Memory assertions used

The contract is stated in a separation logic over a "heap" that records ownership of individual byte addresses. A memory mmm satisfies an assertion PPP if some heap hhh satisfies PPP and hhh is consistent with mmm: every byte owned read-write in hhh holds the recorded value in mmm with permission exactly read-write and not marked lazily-freed; every byte owned read-only in hhh holds the recorded value in mmm, is readable, and is not lazily-freed (plus bookkeeping conditions on auxiliary ghost and mapping components of the heap, which none of the assertions named here use but RRR may). P∗QP * QP∗Q holds of a heap that splits into two compatible parts satisfying PPP and QQQ; two parts are compatible only if no address is in both, except that an address may be owned read-only by both with the same byte value. ⌈φ⌉\lceil\varphi\rceil⌈φ⌉ holds of the empty heap when the proposition φ\varphiφ is true.

  • a↦ro[b0,…,bn−1]a \mapsto_{\mathrm{ro}} [b_0,\dots,b_{n-1}]a↦ro​[b0​,…,bn−1​]: the addresses a,a+1,…,a+n−1a, a+1, \dots, a+n-1a,a+1,…,a+n−1 (mod 2642^{64}264) are owned read-only and hold b0,…,bn−1b_0,\dots,b_{n-1}b0​,…,bn−1​ (for n=0n=0n=0, the empty heap).
  • Frame(s)\mathrm{Frame}(s)Frame(s), the 96-byte stack frame of state sss: the 96 addresses sp(s)−96,…,sp(s)−1\mathrm{sp}(s) - 96, \dots, \mathrm{sp}(s)-1sp(s)−96,…,sp(s)−1 (mod 2642^{64}264) are owned read-write, with arbitrary contents.
  • Tables(π)=(ρ("crc_table [zlib_crc32]")↦roT0)∗(ρ("crc_braid_table [zlib_crc32]")↦roT1)∗(ρ("x2n_table [zlib_crc32]")↦roT2)\mathrm{Tables}(\pi) = (\rho(\text{"crc\_table [zlib\_crc32]"}) \mapsto_{\mathrm{ro}} T_0) * (\rho(\text{"crc\_braid\_table [zlib\_crc32]"}) \mapsto_{\mathrm{ro}} T_1) * (\rho(\text{"x2n\_table [zlib\_crc32]"}) \mapsto_{\mathrm{ro}} T_2)Tables(π)=(ρ("crc_table [zlib_crc32]")↦ro​T0​)∗(ρ("crc_braid_table [zlib_crc32]")↦ro​T1​)∗(ρ("x2n_table [zlib_crc32]")↦ro​T2​).

The CRC value

Polynomials are over F2\mathbb F_2F2​. Let

P(X)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1,P(X) = X^{32} + X^{26} + X^{23} + X^{22} + X^{16} + X^{12} + X^{11} + X^{10} + X^8 + X^7 + X^5 + X^4 + X^2 + X + 1,P(X)=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1, U(X)=∑k=031Xk.U(X) = \sum_{k=0}^{31} X^k .U(X)=k=0∑31​Xk.

For a 32-bit value ccc with bits c0c_0c0​ (least significant) to c31c_{31}c31​, let reg(c)=∑i=031ciX31−i\mathrm{reg}(c) = \sum_{i=0}^{31} c_i X^{31-i}reg(c)=∑i=031​ci​X31−i (the least significant bit is the coefficient of X31X^{31}X31). For a byte list B=[b0,…,bn−1]B = [b_0,\dots,b_{n-1}]B=[b0​,…,bn−1​] let MBM_BMB​ be the bit string of length 8n8n8n listing the bits of b0b_0b0​ from least to most significant, then those of b1b_1b1​, and so on; and MB(X)=∑k=08n−1(MB)kX8n−1−kM_B(X) = \sum_{k=0}^{8n-1} (M_B)_k X^{8n-1-k}MB​(X)=∑k=08n−1​(MB​)k​X8n−1−k (the first bit gets the highest power). Define

CRC(c,B)=((reg(c)−U) X8n+MB(X) X32+U) mod P,\mathrm{CRC}(c, B) = \big( (\mathrm{reg}(c) - U)\,X^{8n} + M_B(X)\,X^{32} + U \big) \bmod P,CRC(c,B)=((reg(c)−U)X8n+MB​(X)X32+U)modP,

the remainder on division by PPP (which is monic of degree 32). For BBB empty, CRC(c,[])=reg(c) mod P=reg(c)\mathrm{CRC}(c,[]) = \mathrm{reg}(c) \bmod P = \mathrm{reg}(c)CRC(c,[])=reg(c)modP=reg(c).

A 64-bit value rrr holds a polynomial qqq if r<232r < 2^{32}r<232 as an unsigned number and reg(r mod 232)=q\mathrm{reg}(r \bmod 2^{32}) = qreg(rmod232)=q.

The subroutine contract

Write x0,x1,x2x_0, x_1, x_2x0​,x1​,x2​ for the 64-bit general registers 0, 1, 2 of a state, lr\mathrm{lr}lr for register 30, fp\mathrm{fp}fp for register 29, and sp\mathrm{sp}sp for the stack pointer. The contract has a ghost parameter ggg that is either "none" or a byte list BBB.

Precondition Pre(g,s0)\mathrm{Pre}(g, s_0)Pre(g,s0​):

  • g=g = g= none: ⌈x1(s0)=0⌉∗Frame(s0)∗Tables(π)\lceil x_1(s_0) = 0\rceil * \mathrm{Frame}(s_0) * \mathrm{Tables}(\pi)⌈x1​(s0​)=0⌉∗Frame(s0​)∗Tables(π).
  • g=Bg = Bg=B: ⌈x1(s0)≠0 and x2(s0)=∣B∣ (as unsigned 64-bit)⌉∗(x1(s0)↦roB)∗Frame(s0)∗Tables(π)\lceil x_1(s_0) \ne 0 \text{ and } x_2(s_0) = |B| \text{ (as unsigned 64-bit)}\rceil * (x_1(s_0) \mapsto_{\mathrm{ro}} B) * \mathrm{Frame}(s_0) * \mathrm{Tables}(\pi)⌈x1​(s0​)=0 and x2​(s0​)=∣B∣ (as unsigned 64-bit)⌉∗(x1​(s0​)↦ro​B)∗Frame(s0​)∗Tables(π).

Postcondition Post(g,s0,sf)\mathrm{Post}(g, s_0, s_f)Post(g,s0​,sf​):

  • g=g = g= none: ⌈x0(sf)=0 (all 64 bits)⌉∗Frame(s0)∗Tables(π)\lceil x_0(s_f) = 0 \text{ (all 64 bits)}\rceil * \mathrm{Frame}(s_0) * \mathrm{Tables}(\pi)⌈x0​(sf​)=0 (all 64 bits)⌉∗Frame(s0​)∗Tables(π).
  • g=Bg = Bg=B: ⌈x0(sf) holds CRC(x0(s0) mod 232, B)⌉∗(x1(s0)↦roB)∗Frame(s0)∗Tables(π)\lceil x_0(s_f) \text{ holds } \mathrm{CRC}(x_0(s_0) \bmod 2^{32},\, B)\rceil * (x_1(s_0) \mapsto_{\mathrm{ro}} B) * \mathrm{Frame}(s_0) * \mathrm{Tables}(\pi)⌈x0​(sf​) holds CRC(x0​(s0​)mod232,B)⌉∗(x1​(s0​)↦ro​B)∗Frame(s0​)∗Tables(π).

(Note the frame in the postcondition is the 96 bytes below the initial stack pointer.) In the none case, x2x_2x2​ is unconstrained and no buffer is owned.

The contract, for the loaded program and entry address e=π.base+12e = \pi.\mathrm{base}+12e=π.base+12, says: for every ghost ggg, every separation-logic assertion RRR (the "rest of memory"), and every machine state s0s_0s0​ such that

  1. the program counter of s0s_0s0​ is eee,
  2. s0s_0s0​ is in the running status,
  3. the memory of s0s_0s0​ satisfies Pre(g,s0)∗R\mathrm{Pre}(g, s_0) * RPre(g,s0​)∗R,
  4. sp(s0)≡0(mod16)\mathrm{sp}(s_0) \equiv 0 \pmod{16}sp(s0​)≡0(mod16),
  5. the program's code is loaded in the memory of s0s_0s0​: π.base≡0(mod4)\pi.\mathrm{base} \equiv 0 \pmod 4π.base≡0(mod4), π.base+2824≤264\pi.\mathrm{base} + 2824 \le 2^{64}π.base+2824≤264, and for each i<2824i < 2824i<2824 the byte at π.base+i\pi.\mathrm{base}+iπ.base+i equals the iii-th patched code byte, has permission exactly read+execute, and is not lazily-freed,

there exists a state sfs_fsf​ reachable from s0s_0s0​ in zero or more machine steps such that at least one of the following holds:

  • (normal return) the program counter of sfs_fsf​ equals lr(s0)\mathrm{lr}(s_0)lr(s0​); sp(sf)=sp(s0)\mathrm{sp}(s_f) = \mathrm{sp}(s_0)sp(sf​)=sp(s0​); sfs_fsf​ is running; registers 19–28 and fp\mathrm{fp}fp have the same 64-bit values in sfs_fsf​ as in s0s_0s0​, as do the low 64 bits of vector registers 8–15; and the memory of sfs_fsf​ satisfies Post(g,s0,sf)∗R\mathrm{Post}(g, s_0, s_f) * RPost(g,s0​,sf​)∗R, with the same RRR;
  • sfs_fsf​ has panicked, exited with some code, or run out of memory, and its memory satisfies ⌈False⌉∗R\lceil \text{False}\rceil * R⌈False⌉∗R — which is impossible, so in effect only the normal-return alternative can occur.

A machine step from a running state either executes the instruction decoded from the 4 bytes of current memory at the program counter (if the address is 4-aligned and executable), or halts (status "halted") if no instruction can be fetched there. Since the program has no hooks, the hook-related step rules never apply. System-call instructions are handled by the model's standard system-call handler, which cannot modify memory marked frozen.

Edge cases and remarks

  • The quantification over π\piπ includes every admissible placement, including all choices of the relaxation flags.
  • Reaching sfs_fsf​ in zero steps is allowed: sfs_fsf​ may be s0s_0s0​ itself (this matters only if lr(s0)=e\mathrm{lr}(s_0) = elr(s0​)=e and the postcondition already holds). sfs_fsf​ need not be the first state at which the program counter equals lr(s0)\mathrm{lr}(s_0)lr(s0​).
  • The input buffer, when BBB is empty, owns no bytes; then x1(s0)≠0x_1(s_0) \ne 0x1​(s0​)=0 and x2(s0)=0x_2(s_0) = 0x2​(s0​)=0 are the only constraints.
  • Because read-only ownership can be shared when byte values agree, the buffer x1(s0)↦roBx_1(s_0) \mapsto_{\mathrm{ro}} Bx1​(s0​)↦ro​B may overlap the tables where the bytes agree; read-only buffer or table bytes may also coincide with code bytes (which are readable) since loaded code is not part of the heap. The read-write stack frame cannot overlap any owned byte, and cannot overlap the code (whose permission is read+execute, not read-write).
  • x2(s0)=∣B∣x_2(s_0) = |B|x2​(s0​)=∣B∣ is the full 64-bit unsigned value; the initial CRC value is the low 32 bits of x0(s0)x_0(s_0)x0​(s0​), the upper 32 bits being ignored; the result must have its upper 32 bits zero.
  • Hypotheses 1–5 are jointly satisfiable only if memory is laid out as described; nothing in the statement itself makes any hypothesis contradictory.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me