zlib.h, crc32_z() — the compiled crc32_z computes CRC-32
OpenZlibCrc32.subroutineOk_crc32_zTotal 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 and every entry state at the address of crc32_z with the stack pointer 16-byte aligned, whose memory satisfies the precondition separately from , execution terminates. It returns to the caller (the link register) with the stack pointer and the callee-saved registers restored, 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), anycrcandlen: the result is .buf ≠ Z_NULL, with the bytes readable atbufandlen: the result is a 32-bit value (upper half ofx0zero) whose polynomial is . Here is the message of (bit of byte is message bit ), is the polynomial of the low 32 bits ofcrc, is the CRC-32 polynomial and . The buffer is handed back unchanged.
Polynomials of 32-bit values are Kadatch–Jenkins' register convention: bit is the coefficient of .
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.”
import Mathlib import Definitions.Def_ZlibCrc32_Spec
namespace ZlibCrc32 theorem subroutineOk_crc32_z : zlibCrc32Lib.subroutineOk "crc32_z" crc32zSpec := by sorry end ZlibCrc32
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 of the library that is admissible (defined below), the program obtained by loading the library at satisfies the subroutine contract described below, with entry point .
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 and an "add" fix-up at ) at referring to the data symbol "crc_table [zlib_crc32]", at referring to "crc_braid_table [zlib_crc32]", at 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 ), "crc_braid_table [zlib_crc32]" (8192 bytes, ), "x2n_table [zlib_crc32]" (128 bytes, ).
Placements
A placement consists of: a 64-bit code base address ; a function from symbol names to 64-bit addresses (used here for the three data objects); a relaxation flag for each code offset ; a "branch-to-branch" flag for each offset; and an "undefined weak symbol" flag for each name. All address arithmetic is modulo .
Loaded code. The program's code bytes are the library's code with every relocated word patched for :
- A word with no relocation entry is unchanged.
- For each adrp/add pair at offsets (all eight pairs in this library meet the structural pattern for relaxation): if is true, the word at becomes a no-op and the word at becomes a PC-relative "adr" into the same destination register, encoding the 21-bit offset from address to the target; otherwise the word at gets the 21-bit page difference between the target's 4 KiB page and the page of , and the word at gets the low 12 bits of the target. The target is of the data symbol named.
- The branch at offset 2048 gets the low 26 bits of , where the target is (the symbol "crc32_z" resolves inside the library) and the place is . The branch-to-branch and weak-symbol flags have no effect on this library.
The program has 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. is admissible iff all of the following hold (with the code length):
- , and (as natural numbers; the code does not wrap around);
- for each adrp relocation at offset (with target , place ), whatever the value of : the page difference (where clears the low 12 bits; difference taken mod and read in two's complement) lies in . The "add" relocations impose no condition;
- for the branch at 2048: , read as a signed 64-bit number, is divisible by 4 and lies in (this holds automatically);
- for each pair whose is true: the signed difference lies in ;
- the relocation offsets are distinct, multiples of 4, and at most ; 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 of length : and .
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 satisfies an assertion if some heap satisfies and is consistent with : every byte owned read-write in holds the recorded value in with permission exactly read-write and not marked lazily-freed; every byte owned read-only in holds the recorded value in , 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 may). holds of a heap that splits into two compatible parts satisfying and ; 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. holds of the empty heap when the proposition is true.
- : the addresses (mod ) are owned read-only and hold (for , the empty heap).
- , the 96-byte stack frame of state : the 96 addresses (mod ) are owned read-write, with arbitrary contents.
- .
The CRC value
Polynomials are over . Let
For a 32-bit value with bits (least significant) to , let (the least significant bit is the coefficient of ). For a byte list let be the bit string of length listing the bits of from least to most significant, then those of , and so on; and (the first bit gets the highest power). Define
the remainder on division by (which is monic of degree 32). For empty, .
A 64-bit value holds a polynomial if as an unsigned number and .
The subroutine contract
Write for the 64-bit general registers 0, 1, 2 of a state, for register 30, for register 29, and for the stack pointer. The contract has a ghost parameter that is either "none" or a byte list .
Precondition :
- none: .
- : .
Postcondition :
- none: .
- : .
(Note the frame in the postcondition is the 96 bytes below the initial stack pointer.) In the none case, is unconstrained and no buffer is owned.
The contract, for the loaded program and entry address , says: for every ghost , every separation-logic assertion (the "rest of memory"), and every machine state such that
- the program counter of is ,
- is in the running status,
- the memory of satisfies ,
- ,
- the program's code is loaded in the memory of : , , and for each the byte at equals the -th patched code byte, has permission exactly read+execute, and is not lazily-freed,
there exists a state reachable from in zero or more machine steps such that at least one of the following holds:
- (normal return) the program counter of equals ; ; is running; registers 19–28 and have the same 64-bit values in as in , as do the low 64 bits of vector registers 8–15; and the memory of satisfies , with the same ;
- has panicked, exited with some code, or run out of memory, and its memory satisfies — 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 includes every admissible placement, including all choices of the relaxation flags.
- Reaching in zero steps is allowed: may be itself (this matters only if and the postcondition already holds). need not be the first state at which the program counter equals .
- The input buffer, when is empty, owns no bytes; then and are the only constraints.
- Because read-only ownership can be shared when byte values agree, the buffer 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).
- is the full 64-bit unsigned value; the initial CRC value is the low 32 bits of , 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.