crc32.c, the CRC tables — crc_table, crc_braid_table and x2n_table hold their CRC values
OpenZlibCrc32.crc_tables_eqThe three data objects of the compiled library, read as little-endian 32-bit words, hold the following values. is the CRC-32 polynomial, and the polynomial of a word is read by the register convention: bit is the coefficient of .
crc_tableis 1024 bytes. Its word () is of the one-byte message from , that is . Here is the polynomial of byte : bit of is the coefficient of .crc_braid_tableis 8192 bytes. Its word (, ) is .x2n_tableis 128 bytes. Its word () is (Kadatch–Jenkins eq. (6)).
import Mathlib import Definitions.Def_ZlibCrc32_Spec open Polynomial KadatchJenkins
namespace ZlibCrc32
theorem crc_tables_eq :
(zlibCrc32PlacedData0.length = 1024 ∧ ∀ i < 256,
regPoly (word32 zlibCrc32PlacedData0 i) = crc0 crc32P (Message.ofBytes [BitVec.ofNat 8 i]) 0) ∧
(zlibCrc32PlacedData1.length = 8192 ∧ ∀ k < 8, ∀ i < 256,
regPoly (word32 zlibCrc32PlacedData1 (256 * k + i)) =
(Message.ofBytes [BitVec.ofNat 8 i]).poly * X ^ (8 * (5 * 8 + 3 - k)) % crc32P) ∧
(zlibCrc32PlacedData2.length = 128 ∧ ∀ k < 32,
regPoly (word32 zlibCrc32PlacedData2 k) = pow2k crc32P k) := by
sorry
end ZlibCrc32Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
What the statement asserts
The statement is a single closed proposition: it has no variables, parameters or hypotheses of its own. It is a conjunction of three claims, one about each of three fixed, explicitly listed tables of bytes. All quantified variables inside it range over natural numbers.
The objects involved
The three tables. , , are three concrete finite lists of bytes (8-bit values), written out literally, byte by byte, in hexadecimal in the published definitions. There they are the contents of three read-only data sections of a placed object library, attached to the symbols "crc_table [zlib_crc32]", "crc_braid_table [zlib_crc32]" and "x2n_table [zlib_crc32]" respectively. The statement uses only their contents as lists. Entries are indexed from .
Bits. For a fixed-width bit string , write for its bit , where bit is the least significant bit, i.e. is the -th binary digit of the natural number that represents.
Reading a 32-bit word out of a table. For a byte list and a natural number , is the 32-bit word whose four bytes, from least significant to most significant, are , , , (little-endian). That is, bit of is bit of , for , . If one of these positions lies beyond the end of , the zero byte is used in its place. (Given the lengths asserted below, every position the statement reads lies within its table, so this default is never reached when the length claims hold.)
Polynomials. All polynomials have coefficients in the two-element field , in the indeterminate . The fixed polynomial is
which is monic of degree . "" denotes the ordinary remainder of on division by , a polynomial of degree less than (or zero).
The polynomial of a 32-bit word (reflected reading). For a 32-bit word ,
So the least significant bit gives the coefficient of and the most significant bit gives the constant term. In terms of the table bytes, bit of is the coefficient of in .
The polynomial of a byte (same reflected reading). For a natural number , let be the byte with value (no truncation occurs since ), and
This arises as follows: the byte is turned into the length-8 sequence of its bits, least significant first, ; a sequence is turned into the polynomial (first entry carries the highest power). So is the coefficient of and the constant term. For example and .
Claim 1 (table )
has exactly entries, and for every natural number with ,
The left middle form is the literal shape: it is a "CRC with zero initial register" of the 8-bit message consisting of the bits of (least significant first), namely (initial value message polynomial ) mod , with initial value , message length and . The case asserts that is the zero word.
Claim 2 (table )
has exactly entries, and for every natural number with and every natural number with ,
The exponent is written in the source as , i.e. ; since the subtraction never goes below zero, and the exponent ranges over as runs over . The word index runs over , so the claim covers words through , which occupy all bytes. The remainder is taken of the whole product (the product is formed first, then reduced mod ). For the claim says the corresponding word is zero.
Claim 3 (table )
has exactly entries, and for every natural number with ,
For example, asserts , i.e. has only bit set. The claim covers words through , which occupy all bytes.
Remarks on scope
The three claims are joined by "and"; each consists of the exact length of the table together with a value formula for every word of the table. Nothing is asserted about any program, machine state, memory placement or address: only the three byte lists themselves are constrained.