zlib.h, get_crc_table() — get_crc_table returns the byte-wise CRC table
OpenZlibCrc32.subroutineOk_get_crc_tableTotal 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 is the polynomial of byte times , mod the CRC-32 polynomial , which is of the one-byte message from the initial value (Kadatch–Jenkins eq. (7)).
import Mathlib import Definitions.Def_ZlibCrc32_Spec
namespace ZlibCrc32
theorem subroutineOk_get_crc_table :
zlibCrc32Lib.subroutineOk "get_crc_table" getCrcTableSpec := by
sorry
end ZlibCrc32Read-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 code bytes (a fixed list of byte constants), with code alignment , no external symbols and no weak references;
- eight code symbols with byte offsets into the text block: "get_crc_table" at , "crc32_z" at , "crc32" at , "crc32_combine64" at , "crc32_combine" at , "crc32_combine_gen64" at , "crc32_combine_gen" at , "crc32_combine_op" at ;
- seventeen code relocations, all with addend : "page address" relocations at offsets (symbol "crc_table [zlib_crc32]"), (symbol "crc_braid_table [zlib_crc32]"), (symbol "x2n_table [zlib_crc32]"); "low 12 bits" relocations at the offsets beyond each of those () for the same symbols; and one 26-bit branch relocation at offset to the library's own symbol "crc32_z";
- three read-only data objects, each of alignment , with no data relocations and no zero tail: "crc_table [zlib_crc32]" holding a fixed list of bytes, "crc_braid_table [zlib_crc32]" holding a fixed list of bytes, and "x2n_table [zlib_crc32]" holding a fixed list of 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 -bit, and all address arithmetic is modulo .
Placements. A placement consists of a base address for the text block, an arbitrary symbol-address map from strings to -bit addresses, and three arbitrary Boolean-valued option maps: a "relax" flag for each natural number , 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 that is admissible (defined below), the subroutine contract (defined below) holds for the program obtained by placing the library according to , entered at the address of "get_crc_table", which is .
There are no other variables or hypotheses at the top level.
Admissibility of a placement
A placement 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 .
Text block:
- the alignment is positive and divisible by (fixed fact);
- ;
- (as natural numbers: the code does not wrap around the address space);
- (fixed fact);
- the seventeen relocation offsets are pairwise distinct (fixed fact);
- for each relocation at offset : and (fixed facts), and a range condition on the place and the target of the relocation. Here the target of a relocation to a data symbol is , and the target of the branch to "crc32_z" is . The range conditions are:
- for each "page address" relocation: writing for with its low bits cleared, the difference (computed modulo , then read as a signed two's-complement -bit integer) lies in . This applies to with , to with , and to with ;
- for each "low 12 bits" relocation: no condition;
- for the branch at offset : , read as a signed integer, is a multiple of and lies in (it equals , so this always holds);
- for every offset at which relaxation is in effect (meaning: is true and is one of the eight offsets , 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 and the place lies in . For any other the relax flag has no effect and imposes nothing;
- every code symbol offset is divisible by and at most (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 of length (, , respectively): and 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 , and places no condition on at strings other than the three data symbol names. Such placements exist (for example, and the three data symbols at small, separated multiples of ), so the quantifier over placements is not vacuous.
The placed program
For a placement , the program has base address , 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 -byte little-endian word at offset () 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 -bit page count of ;
- at a low-12-bits relocation that is not part of a relaxed pair, bits to receive the low bits of ;
- at the branch relocation, the low bits receive (low bits of the shifted difference);
- if relaxation is in effect at offset (as above), the word at becomes the no-operation word and the word at becomes an address-of-label instruction on the same destination register, encoding the difference .
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 , , are , , , with the relocation pair at offsets and targeting .
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 satisfies an assertion when some heap satisfies and matches : every read-write cell at has 's byte at equal to it, permission exactly read-write, and not lazily freed; every read-only cell at has 's byte at 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 . Addresses not in are unconstrained.
- holds of exactly the empty heap, and only when the proposition is true.
- (separating conjunction, associating to the right) holds of when is the union of two heaps with true of , true of , and 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.
- holds of when holds of for some .
- is the separating conjunction of read-only single-byte cells at addresses (modulo ); for the empty list it is the empty heap.
The data assertion is
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 , the contract says: for every initial machine state and every assertion (an arbitrary "frame", any predicate on heaps whatsoever), if
- the program counter of is ,
- the execution status of is "running",
- the memory of satisfies , and
- the stack pointer of is divisible by ,
then, if the code is loaded in the memory of (meaning: , , and for every the byte of memory at equals the -th patched code byte, has read-execute permission, and is not lazily freed), there exists a state reachable from by finitely many machine steps of the program (possibly zero) such that one of four outcomes holds:
- Normal return: the program counter of equals the value held in register (the link register) in ; the stack pointer of equals that of ; the status of is "running"; registers and hold the same values in as in , and the low bits of vector registers are the same in as in ; and the memory of satisfies , with the postcondition below.
- Panic with memory satisfying ;
- Exit with some code, with memory satisfying ;
- Out of memory, with memory satisfying .
Since holds of no heap, outcomes 2 to 4 can never be witnessed; the contract therefore requires a reachable normal return.
The precondition is just : 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 the final state and the value of register in :
Here is a list of bytes, ranges over natural numbers, and is the polynomial identity in
where:
- is the -bit word assembled little-endian from bytes , i.e. the number , and is its bit ( least significant). So bit of the word is the coefficient of : the word is read bit-reflected. (Since and , all four byte indices are in range.)
- is bit of ( least significant), and is the message polynomial of the single byte with its least significant bit as the leading () coefficient, also bit-reflected. The byte is itself (no truncation, since ).
- , of degree .
- is the remainder of polynomial division by in .
The right-hand side is the "zero-initial-register" CRC of the one-byte message : the message polynomial, multiplied by , reduced modulo , with the initial register value contributing . There is no pre- or post-inversion (no all-ones term) in this formula.
In words: on return, register holds the address the placement gives to "crc_table [zlib_crc32]"; at that address there is (read-only) a -byte table whose little-endian -bit words, read bit-reflected, are the zero-initialised CRC values of the single bytes for the polynomial ; the three data tables are still present read-only exactly as in the precondition; and the frame still holds, separately.
Consequences of the definitions worth stating
- The table is the published constant. The read-only claim and the conjunct both cover the addresses starting at (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 must equal . The identity for all is therefore, in effect, a condition on the fixed constant , independent of the placement and of the machine run; what the run contributes is that ends equal to and that survives.
- The case requires , i.e. .
- The frame is arbitrary, including assertions on read-write memory, which must still hold of the final memory; and it may share read-only cells with 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 with read-execute permission, the contract asks nothing.
- The conclusion is existential in the run: some finite sequence of machine steps from 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.