Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

zlib.h, get_crc_table() — get_crc_table returns the byte-wise CRC table

Open
ZlibCrc32.subroutineOk_get_crc_table

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

aarch64crcmachine-code-verificationseparation-logiczlib

Total correctness of get_crc_table in the AArch64 object code of zlib 1.3.1's crc32.c. "Total correctness" is read as in the goal: for every placement of the library, frame and AAPCS64 entry state, the function terminates and returns with the calling convention preserved.

The caller lends the library's tables and gets them back. The result x0 is the address of the library's crc_table under the placement, and points to 1024 readable bytes holding 256 little-endian 32-bit words. Word iii is the polynomial of byte iii times x32x^{32}x32, mod the CRC-32 polynomial PPP, which is CRC0\mathrm{CRC}_0CRC0​ of the one-byte message iii from the initial value 000 (Kadatch–Jenkins eq. (7)).

Preamble
import Mathlib
import Definitions.Def_ZlibCrc32_Spec
Formal statement
namespace ZlibCrc32

theorem subroutineOk_get_crc_table :
    zlibCrc32Lib.subroutineOk "get_crc_table" getCrcTableSpec := 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 line 1916 and crc32.c lines 546–554 (get_crc_table)
Read-back

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

Read-back: the contract of "get_crc_table" in the placed zlib CRC-32 library

The objects involved

The library. The statement is about one fixed relocatable library, named "zlibCrc32", given as literal data:

  • a text block of 282428242824 code bytes (a fixed list of byte constants), with code alignment 444, no external symbols and no weak references;
  • eight code symbols with byte offsets into the text block: "get_crc_table" at 000, "crc32_z" at 121212, "crc32" at 204420442044, "crc32_combine64" at 205220522052, "crc32_combine" at 225622562256, "crc32_combine_gen64" at 246024602460, "crc32_combine_gen" at 260426042604, "crc32_combine_op" at 274827482748;
  • seventeen code relocations, all with addend 000: "page address" relocations at offsets 0,28,10400, 28, 10400,28,1040 (symbol "crc_table [zlib_crc32]"), 456456456 (symbol "crc_braid_table [zlib_crc32]"), 2072,2276,2476,26202072, 2276, 2476, 26202072,2276,2476,2620 (symbol "x2n_table [zlib_crc32]"); "low 12 bits" relocations at the offsets 444 beyond each of those (4,32,1044,460,2076,2280,2480,26244, 32, 1044, 460, 2076, 2280, 2480, 26244,32,1044,460,2076,2280,2480,2624) for the same symbols; and one 26-bit branch relocation at offset 204820482048 to the library's own symbol "crc32_z";
  • three read-only data objects, each of alignment 444, with no data relocations and no zero tail: "crc_table [zlib_crc32]" holding a fixed list C0C_0C0​ of 102410241024 bytes, "crc_braid_table [zlib_crc32]" holding a fixed list C1C_1C1​ of 819281928192 bytes, and "x2n_table [zlib_crc32]" holding a fixed list C2C_2C2​ of 128128128 bytes;
  • an export list of eight names: "crc32_z", "crc32", "crc32_combine", "crc32_combine64", "crc32_combine_gen", "crc32_combine_gen64", "crc32_combine_op", "get_crc_table".

All machine words below are 646464-bit, and all address arithmetic is modulo 2642^{64}264.

Placements. A placement π\piπ consists of a base address b∈{0,…,264−1}b \in \{0,\dots,2^{64}-1\}b∈{0,…,264−1} for the text block, an arbitrary symbol-address map ρ\rhoρ from strings to 646464-bit addresses, and three arbitrary Boolean-valued option maps: a "relax" flag relax(o)\mathrm{relax}(o)relax(o) for each natural number ooo, a "branch-to-branch" flag for each natural number, and an "undefined weak" flag for each string.

What the statement asserts

The statement is the conjunction of two claims.

(1) The string "get_crc_table" belongs to the library's export list. (It does: it is the eighth entry.)

(2) For every placement π=(b,ρ,relax,… )\pi = (b, \rho, \mathrm{relax}, \dots)π=(b,ρ,relax,…) that is admissible (defined below), the subroutine contract (defined below) holds for the program obtained by placing the library according to π\piπ, entered at the address of "get_crc_table", which is b+0=bb + 0 = bb+0=b.

There are no other variables or hypotheses at the top level.

Admissibility of a placement

A placement π\piπ is admissible for this library when all of the following hold. Several items are facts about the fixed library only; they are listed because the definition includes them, and each of them holds for this library, so they add no restriction on π\piπ.

Text block:

  • the alignment 444 is positive and divisible by 444 (fixed fact);
  • b≡0(mod4)b \equiv 0 \pmod 4b≡0(mod4);
  • b+2824≤264b + 2824 \le 2^{64}b+2824≤264 (as natural numbers: the code does not wrap around the address space);
  • 2824≡0(mod4)2824 \equiv 0 \pmod 42824≡0(mod4) (fixed fact);
  • the seventeen relocation offsets are pairwise distinct (fixed fact);
  • for each relocation at offset ooo: o≡0(mod4)o \equiv 0 \pmod 4o≡0(mod4) and o+4≤2824o + 4 \le 2824o+4≤2824 (fixed facts), and a range condition on the place p=b+op = b + op=b+o and the target ttt of the relocation. Here the target of a relocation to a data symbol sss is ρ(s)\rho(s)ρ(s), and the target of the branch to "crc32_z" is b+12b + 12b+12. The range conditions are:
    • for each "page address" relocation: writing page(x)\mathrm{page}(x)page(x) for xxx with its low 121212 bits cleared, the difference page(t)−page(p)\mathrm{page}(t) - \mathrm{page}(p)page(t)−page(p) (computed modulo 2642^{64}264, then read as a signed two's-complement 646464-bit integer) lies in [−232,232)[-2^{32}, 2^{32})[−232,232). This applies to p=b+0,b+28,b+1040p = b+0, b+28, b+1040p=b+0,b+28,b+1040 with t=ρ("crc_table [zlib_crc32]")t = \rho(\text{"crc\_table [zlib\_crc32]"})t=ρ("crc_table [zlib_crc32]"), to p=b+456p = b + 456p=b+456 with t=ρ("crc_braid_table [zlib_crc32]")t = \rho(\text{"crc\_braid\_table [zlib\_crc32]"})t=ρ("crc_braid_table [zlib_crc32]"), and to p=b+2072,b+2276,b+2476,b+2620p = b+2072, b+2276, b+2476, b+2620p=b+2072,b+2276,b+2476,b+2620 with t=ρ("x2n_table [zlib_crc32]")t = \rho(\text{"x2n\_table [zlib\_crc32]"})t=ρ("x2n_table [zlib_crc32]");
    • for each "low 12 bits" relocation: no condition;
    • for the branch at offset 204820482048: t−p=(b+12)−(b+2048)t - p = (b+12) - (b+2048)t−p=(b+12)−(b+2048), read as a signed integer, is a multiple of 444 and lies in [−227,227)[-2^{27}, 2^{27})[−227,227) (it equals −2036-2036−2036, so this always holds);
  • for every offset ooo at which relaxation is in effect (meaning: relax(o)\mathrm{relax}(o)relax(o) is true and ooo is one of the eight offsets 0,28,456,1040,2072,2276,2476,26200, 28, 456, 1040, 2072, 2276, 2476, 26200,28,456,1040,2072,2276,2476,2620, which are exactly the offsets where the library has a page-address/low-12-bits pair on matching registers), the signed difference between that pair's target ttt and the place b+o+4b + o + 4b+o+4 lies in [−220,220)[-2^{20}, 2^{20})[−220,220). For any other ooo the relax flag has no effect and imposes nothing;
  • every code symbol offset is divisible by 444 and at most 282428242824 (fixed fact);
  • there are no external symbols, so no condition on them.

Data objects:

  • the three data symbol names are pairwise distinct, and none of them is a code symbol (fixed facts);
  • for each data object sss of length LsL_sLs​ (102410241024, 819281928192, 128128128 respectively): ρ(s)≡0(mod4)\rho(s) \equiv 0 \pmod 4ρ(s)≡0(mod4) and ρ(s)+Ls≤264\rho(s) + L_s \le 2^{64}ρ(s)+Ls​≤264 as natural numbers;
  • there are no data relocations, so no condition on them.

Admissibility does not require the three data objects to be disjoint from each other or from the code, does not require any page alignment of bbb, and places no condition on ρ\rhoρ at strings other than the three data symbol names. Such placements exist (for example, b=0b = 0b=0 and the three data symbols at small, separated multiples of 409640964096), so the quantifier over placements is not vacuous.

The placed program

For a placement π\piπ, the program has base address bbb, the library's code symbols, no external stubs, no external hooks, no overriding hooks, and the standard system-call model of the machine semantics. Its code is the text block with each 444-byte little-endian word at offset 4j4j4j (0≤j<7060 \le j < 7060≤j<706) replaced by its patched version:

  • a word with no relocation is unchanged;
  • at a page-address relocation that is not relaxed, the instruction's page-offset field is filled with the 212121-bit page count of page(t)−page(p)\mathrm{page}(t) - \mathrm{page}(p)page(t)−page(p);
  • at a low-12-bits relocation that is not part of a relaxed pair, bits 101010 to 212121 receive the low 121212 bits of ttt;
  • at the branch relocation, the low 262626 bits receive (t−p)/4(t - p)/4(t−p)/4 (low 262626 bits of the shifted difference);
  • if relaxation is in effect at offset ooo (as above), the word at ooo becomes the no-operation word 0xd503201f\mathrm{0xd503201f}0xd503201f and the word at o+4o+4o+4 becomes an address-of-label instruction on the same destination register, encoding the difference t−(b+o+4)t - (b + o + 4)t−(b+o+4).

The "branch-to-branch" and "undefined weak" options of the placement have no effect on this library (there is no branch relocation at the branch target, and there are no weak references). For "get_crc_table" itself, the unpatched words at offsets 000, 444, 888 are 0x90000000\mathrm{0x90000000}0x90000000, 0x91000000\mathrm{0x91000000}0x91000000, 0xd65f03c0\mathrm{0xd65f03c0}0xd65f03c0, with the relocation pair at offsets 000 and 444 targeting ρ("crc_table [zlib_crc32]")\rho(\text{"crc\_table [zlib\_crc32]"})ρ("crc_table [zlib_crc32]").

Memory assertions (the separation logic used)

Assertions are predicates on abstract heaps. An abstract heap assigns to some addresses a cell (a read-write byte, a read-only byte, an inaccessible byte, or a lazily-allocated cell) and carries ghost bookkeeping. A memory mmm satisfies an assertion AAA when some heap hhh satisfies AAA and hhh matches mmm: every read-write cell at aaa has mmm's byte at aaa equal to it, permission exactly read-write, and not lazily freed; every read-only cell at aaa has mmm's byte at aaa equal to it, a readable permission, and not lazily freed (similarly for the other cell kinds); the ghost part is finitely supported; and addresses marked as mapped are mapped anonymous memory in mmm. Addresses not in hhh are unconstrained.

  • ⌈φ⌉\lceil \varphi \rceil⌈φ⌉ holds of exactly the empty heap, and only when the proposition φ\varphiφ is true.
  • A∗BA \ast BA∗B (separating conjunction, associating to the right) holds of hhh when hhh is the union of two heaps h1,h2h_1, h_2h1​,h2​ with AAA true of h1h_1h1​, BBB true of h2h_2h2​, and h1,h2h_1, h_2h1​,h2​ compatible: at every address at most one of them has a cell, except that both may hold a read-only cell at the same address provided the bytes agree; their ghost parts are compatible, and they do not both mark an address as mapped.
  • ∃∗x. A(x)\exists^{\ast} x.\, A(x)∃∗x.A(x) holds of hhh when A(x)A(x)A(x) holds of hhh for some xxx.
  • a↦ro[v0,…,vn−1]a \mapsto_{\mathrm{ro}} [v_0, \dots, v_{n-1}]a↦ro​[v0​,…,vn−1​] is the separating conjunction of read-only single-byte cells vkv_kvk​ at addresses a+ka + ka+k (modulo 2642^{64}264); for the empty list it is the empty heap.

The data assertion DπD_\piDπ​ is

Dπ  =  ρ("crc_table [zlib_crc32]")↦roC0  ∗  ρ("crc_braid_table [zlib_crc32]")↦roC1  ∗  ρ("x2n_table [zlib_crc32]")↦roC2,D_\pi \;=\; \rho(\text{"crc\_table [zlib\_crc32]"}) \mapsto_{\mathrm{ro}} C_0 \;\ast\; \rho(\text{"crc\_braid\_table [zlib\_crc32]"}) \mapsto_{\mathrm{ro}} C_1 \;\ast\; \rho(\text{"x2n\_table [zlib\_crc32]"}) \mapsto_{\mathrm{ro}} C_2,Dπ​=ρ("crc_table [zlib_crc32]")↦ro​C0​∗ρ("crc_braid_table [zlib_crc32]")↦ro​C1​∗ρ("x2n_table [zlib_crc32]")↦ro​C2​,

that is, the three published constant tables lie, read-only, at the addresses the placement assigns them.

The subroutine contract

For the placed program with entry address bbb, the contract says: for every initial machine state s0s_0s0​ and every assertion RRR (an arbitrary "frame", any predicate on heaps whatsoever), if

  • the program counter of s0s_0s0​ is bbb,
  • the execution status of s0s_0s0​ is "running",
  • the memory of s0s_0s0​ satisfies Dπ∗RD_\pi \ast RDπ​∗R, and
  • the stack pointer of s0s_0s0​ is divisible by 161616,

then, if the code is loaded in the memory of s0s_0s0​ (meaning: b≡0(mod4)b \equiv 0 \pmod 4b≡0(mod4), b+2824≤264b + 2824 \le 2^{64}b+2824≤264, and for every k<2824k < 2824k<2824 the byte of memory at b+kb + kb+k equals the kkk-th patched code byte, has read-execute permission, and is not lazily freed), there exists a state sfs_fsf​ reachable from s0s_0s0​ by finitely many machine steps of the program (possibly zero) such that one of four outcomes holds:

  1. Normal return: the program counter of sfs_fsf​ equals the value held in register x30x_{30}x30​ (the link register) in s0s_0s0​; the stack pointer of sfs_fsf​ equals that of s0s_0s0​; the status of sfs_fsf​ is "running"; registers x19,…,x28x_{19}, \dots, x_{28}x19​,…,x28​ and x29x_{29}x29​ hold the same values in sfs_fsf​ as in s0s_0s0​, and the low 646464 bits of vector registers v8,…,v15v_8, \dots, v_{15}v8​,…,v15​ are the same in sfs_fsf​ as in s0s_0s0​; and the memory of sfs_fsf​ satisfies Qπ(sf)∗RQ_\pi(s_f) \ast RQπ​(sf​)∗R, with QπQ_\piQπ​ the postcondition below.
  2. Panic with memory satisfying ⌈False⌉∗R\lceil \mathrm{False} \rceil \ast R⌈False⌉∗R;
  3. Exit with some code, with memory satisfying ⌈False⌉∗R\lceil \mathrm{False} \rceil \ast R⌈False⌉∗R;
  4. Out of memory, with memory satisfying ⌈False⌉∗R\lceil \mathrm{False} \rceil \ast R⌈False⌉∗R.

Since ⌈False⌉\lceil \mathrm{False}\rceil⌈False⌉ holds of no heap, outcomes 2 to 4 can never be witnessed; the contract therefore requires a reachable normal return.

The precondition is just DπD_\piDπ​: nothing is assumed about any argument register, and no stack memory is provided. The input-side quantity attached to the contract is a single trivial value (the one-element type), so it adds nothing.

The postcondition

With sfs_fsf​ the final state and x0x_0x0​ the value of register x0x_0x0​ in sfs_fsf​:

Qπ(sf)  =  ⌈x0=ρ("crc_table [zlib_crc32]")⌉  ∗  (∃∗ T.  ⌈∣T∣=1024  ∧  ∀i<256,  Φ(T,i)⌉∗  x0↦roT)  ∗  Dπ.Q_\pi(s_f) \;=\; \big\lceil x_0 = \rho(\text{"crc\_table [zlib\_crc32]"}) \big\rceil \;\ast\; \Big( \exists^{\ast}\, T.\; \big\lceil \lvert T\rvert = 1024 \;\wedge\; \forall i < 256,\; \Phi(T, i) \big\rceil \ast\; x_0 \mapsto_{\mathrm{ro}} T \Big) \;\ast\; D_\pi .Qπ​(sf​)=⌈x0​=ρ("crc_table [zlib_crc32]")⌉∗(∃∗T.⌈∣T∣=1024∧∀i<256,Φ(T,i)⌉∗x0​↦ro​T)∗Dπ​.

Here T=[t0,…,t1023]T = [t_0, \dots, t_{1023}]T=[t0​,…,t1023​] is a list of bytes, iii ranges over natural numbers, and Φ(T,i)\Phi(T,i)Φ(T,i) is the polynomial identity in F2[X]\mathbb{F}_2[X]F2​[X]

∑j=031wj(T,i) X31−j  =  (X32∑k=07ik X7−k) mod P,\sum_{j=0}^{31} w_j(T,i)\, X^{31-j} \;=\; \Big( X^{32} \sum_{k=0}^{7} i_k\, X^{7-k} \Big) \bmod P,j=0∑31​wj​(T,i)X31−j=(X32k=0∑7​ik​X7−k)modP,

where:

  • w(T,i)w(T,i)w(T,i) is the 323232-bit word assembled little-endian from bytes t4i,t4i+1,t4i+2,t4i+3t_{4i}, t_{4i+1}, t_{4i+2}, t_{4i+3}t4i​,t4i+1​,t4i+2​,t4i+3​, i.e. the number t4i+28t4i+1+216t4i+2+224t4i+3t_{4i} + 2^8 t_{4i+1} + 2^{16} t_{4i+2} + 2^{24} t_{4i+3}t4i​+28t4i+1​+216t4i+2​+224t4i+3​, and wj(T,i)∈{0,1}w_j(T,i) \in \{0,1\}wj​(T,i)∈{0,1} is its bit jjj (j=0j = 0j=0 least significant). So bit jjj of the word is the coefficient of X31−jX^{31-j}X31−j: the word is read bit-reflected. (Since ∣T∣=1024\lvert T\rvert = 1024∣T∣=1024 and i<256i < 256i<256, all four byte indices are in range.)
  • ik∈{0,1}i_k \in \{0,1\}ik​∈{0,1} is bit kkk of iii (k=0k = 0k=0 least significant), and ∑kikX7−k\sum_{k} i_k X^{7-k}∑k​ik​X7−k is the message polynomial of the single byte iii with its least significant bit as the leading (X7X^7X7) coefficient, also bit-reflected. The byte is iii itself (no truncation, since i<256i < 256i<256).
  • P=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1P = 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 + 1P=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X+1, of degree 323232.
  •  mod \bmodmod is the remainder of polynomial division by PPP in F2[X]\mathbb{F}_2[X]F2​[X].

The right-hand side is the "zero-initial-register" CRC of the one-byte message iii: the message polynomial, multiplied by Xdeg⁡P=X32X^{\deg P} = X^{32}XdegP=X32, reduced modulo PPP, with the initial register value 000 contributing 0⋅X80 \cdot X^{8}0⋅X8. There is no pre- or post-inversion (no all-ones term) in this formula.

In words: on return, register x0x_0x0​ holds the address the placement gives to "crc_table [zlib_crc32]"; at that address there is (read-only) a 102410241024-byte table whose 256256256 little-endian 323232-bit words, read bit-reflected, are the zero-initialised CRC values of the 256256256 single bytes for the polynomial PPP; the three data tables are still present read-only exactly as in the precondition; and the frame RRR still holds, separately.

Consequences of the definitions worth stating

  • The table is the published constant. The read-only claim x0↦roTx_0 \mapsto_{\mathrm{ro}} Tx0​↦ro​T and the conjunct DπD_\piDπ​ both cover the 102410241024 addresses starting at ρ("crc_table [zlib_crc32]")\rho(\text{"crc\_table [zlib\_crc32]"})ρ("crc_table [zlib_crc32]") (these addresses are distinct, by the no-wraparound condition). Two separated read-only claims on the same address are compatible only when their bytes agree, so the witness TTT must equal C0C_0C0​. The identity Φ(T,i)\Phi(T,i)Φ(T,i) for all i<256i<256i<256 is therefore, in effect, a condition on the fixed constant C0C_0C0​, independent of the placement and of the machine run; what the run contributes is that x0x_0x0​ ends equal to ρ("crc_table [zlib_crc32]")\rho(\text{"crc\_table [zlib\_crc32]"})ρ("crc_table [zlib_crc32]") and that Dπ∗RD_\pi \ast RDπ​∗R survives.
  • The case i=0i = 0i=0 requires w(T,0)=0w(T,0) = 0w(T,0)=0, i.e. t0=t1=t2=t3=0t_0 = t_1 = t_2 = t_3 = 0t0​=t1​=t2​=t3​=0.
  • The frame RRR is arbitrary, including assertions on read-write memory, which must still hold of the final memory; and it may share read-only cells with DπD_\piDπ​ or with the table claim when bytes agree.
  • Read-only claims require only a readable permission in memory, so the data tables could, as far as the assertion is concerned, sit in readable-and-executable or readable-and-writable memory; the assertion does not require the tables to be write-protected.
  • Code-loaded is a premise, not a conclusion: for an initial state whose memory does not contain the patched code at bbb with read-execute permission, the contract asks nothing.
  • The conclusion is existential in the run: some finite sequence of machine steps from s0s_0s0​ reaches a normal-return state with the stated properties. It does not separately assert that every run behaves this way, nor anything about how many steps are taken.
  • The quantifier over placements includes the relax options: the claim must hold both for the code as written (page-address plus low-12-bits pairs) and for every combination of relaxed pairs (no-operation plus address-of-label), subject to the corresponding range conditions in admissibility.

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