Skip to content
REFERENCE / ZLIB × LEAN

crc32_combine_op

Compute the CRC-32 of A followed by B using a previously generated operator.

Full chapter and shared rules ↗
uLong ZEXPORT crc32_combine_op(uLong crc1, uLong crc2, uLong op);

Compute the CRC-32 of A followed by B using a previously generated operator.

Return values and next calls

Return type. uLong — CRC-32 checksum or operator-rejection value

Applies a previously generated operator to two independent CRCs. A zero operator has a separate rejection result.

crc32_combine_op()
Returned value Meaning and conditions Caller’s next step
0
Zero operator rejected
op == 0; any checksum arguments are allowed. Generate a valid operator from the actual length of B.
CRC-32(A || B)
Concatenated CRC
The low 32 bits of crc1 and crc2 are the CRCs of A and B, each started at 0; op is the unchanged operator generated for the length of B. Use the result as the concatenated CRC; reuse the operator for the same B length.

Reading the result.

  • A valid CRC can also be zero; the return value alone cannot distinguish rejection from a valid result.
  • Forged operators and operators for the wrong length have no functional guarantee.

Calling conditions and effects

Domain Restricted domain. Effects: pure computation.

Pre For the concatenation result, the low 32 bits of crc1 and crc2 are the CRC-32 checksums of A and B, each started at 0. op is the unchanged result of crc32_combine_gen or crc32_combine_gen64 for the length of B. The separate rejection case permits op == 0 with any checksum arguments.

Effects Preserve all memory and ownership. Read no buffers or stream state.

With a nonzero LP64 op whose low 32 bits are zero the call does not return: uLong has 64 bits, the loop in multmodp looks for a set bit only among bits 31 to 0 of op, and it has no other exit. crc32_combine_op_diverges proves this of the translation: the run ends in the model's out-of-fuel fault (CRC-32 proof). For the C it is a reading of the source. Such an op is outside the premise of the safety goal below, which covers only operators that a generator returned: a generated operator is below 2^32, and it is zero or has a set bit.

Proof goals.

  • Goal. Goal.crc32_combine_op_safety (Safety/Checksums.lean); required. Theorem: ZlibF.Spec.Public.StatelessSafetyProof.crc32_combine_op_safety (public-stateless-safety.lean).
  • Applies when:
    1. the heap holds the library's two constant CRC tables (CrcGlobals), the condition on the model stated at the top of this page;
    2. op is a value that crc32_combine_gen or crc32_combine_gen64 returns for some len2. This is the domain zlib.h gives.
  • Covered without condition. Every crc1 and crc2, also forged checksums; every len2 the operator was generated for, also a negative one, for which the operator is 0.
  • Guarantees.
    • Returns. The call returns.
    • State, writes, allocations. None: the heap after the call is the heap before it.
  • Not in this goal. An op that no generator call returned: outside every goal (deviations, row "CRC combination operator"). The value returned: functional goal Goal.crc32_combine_op (not planned; a theorem proves it).
Complete return conditions and boundaries

Post Return the CRC-32 of A followed by B. If op == 0, return 0. An operator for an empty B leaves A's checksum unchanged.

Shared conditions and scope

Compute a checksum a buffer at a time, or combine the checksums of independently processed byte sequences without rereading them. The byte sequences A and B below are ordinary data; the contracts use the Adler-32 or CRC-32 of those sequences. For example, after processing A and then B, the checksum of A can be the starting value of the next update; if A and B were processed independently, the combination functions give the checksum of A followed by B.

In the update functions, buf points to this batch of input, len is its byte count, and the incoming adler or crc is the value to continue from. In the combination functions, len2 is the byte count of the second sequence B only, not the total length of the two.

Task Entries
Update Adler-32 Size-type length, 32-bit length
Combine Adler-32 Ordinary offset, explicit 64-bit offset
Update CRC-32 Size-type length, 32-bit length
Combine CRC-32 Ordinary offset, explicit 64-bit offset
Reuse a CRC combination operator Generate, generate with 64-bit length, apply
Inspect the byte table get_crc_table

The contracts follow the pinned adler32.c, crc32.c and zlib.h in the default LP64 Linux static build. No patch touches these two C files (patches). Dynamic table generation, hardware CRC hooks and generated table executables are not covered (build and platform). No checksum entry writes state, allocates, frees or performs I/O. Exceptional numeric results are ordinary values, rather than error codes. Domain and effects remain independent as explained in contract conventions. These are focused contracts: Pre describes ordinary correct use and is deliberately narrower than what the function accepts. A call outside Pre is not thereby undefined, and it need not return an error code.

What is proved. Safety only (safety): each safety goal (Safety/Checksums.lean) says that the call returns and that the heap after the call is the heap before it. It says nothing about the value. Each entry gives its goal under Proof goals, in the five items and with the fixed phrases that Reading a Proof goals paragraph defines. The proof assumes the conditions listed there, not the documentary Pre. Post, the return tables and the notes describe functional behaviour. They are read from the C, are to confirm where no theorem states them, and are not required for the safety results. Progress says which goals are done.

The CRC goals have a premise on the model's heap: its two constant CRC tables, crc_table and x2n_table, equal the tables of the translated crc32.h (CrcGlobals). The premise is assumed of the heap the call starts on; no theorem derives it for an arbitrary heap. It is a condition on the model, not a duty of the caller (model limits). Two facts are proved about it. A library heap, which is what the stream goals start from, meets it (crc_globals_of_library). Each checksum goal returns the heap unchanged, so the premise still holds after the call.

The practical checksum contracts use actual byte sequences A and B. Each checksum is computed independently, starting at 1 for Adler-32 or 0 for CRC-32. These contracts deliberately omit functional promises for forged checksums. The functional goals in Functional/Checksums.lean also describe arbitrary seeds and exact scalar results. Both the Adler entries and their Lean goals, safety and functional, require zero length for NULL initialization queries (AdlerBufferBytes in Common/Checksums.lean). See deviations.

In this build, uLong and z_size_t are unsigned 64-bit types; uInt is unsigned 32-bit. z_off_t and z_off64_t are signed 64-bit. Input checksum bits above bit 31 are ignored; returned checksums fit in 32 bits. The explicit *64 declarations depend on the header's large-file feature macros.

Safety goal

ZlibF.Spec.Public.Goal.crc32_combine_op_safety

State: done · Status of the results

/-- `uLong crc32_combine_op(uLong crc1, uLong crc2, uLong op)`.
**Safety of `crc32_combine_op`**: for an operator `op` that `crc32_combine_gen` or
`crc32_combine_gen64` returned (zlib.h's domain), the call returns and the heap is unchanged. -/
def Goal.crc32_combine_op_safety : Prop :=
  ∀ (h : Heap) (first second : UInt64) (length : Int64) (op : UInt64), CrcGlobals h →
    (C.run (Zlib.Crc32.crc32_combine_gen length) h = .ok (op, h) ∨
     C.run (Zlib.Crc32.crc32_combine_gen64 length) h = .ok (op, h)) →
    ∃ value, C.run (Zlib.Crc32.crc32_combine_op first second op) h = .ok (value, h)
Related definitions and source ↗

Functional contract (beyond safety)

ZlibF.Spec.Public.Goal.crc32_combine_op

State: done · Status of the results

/-- `uLong crc32_combine_op(uLong crc1, uLong crc2, uLong op)`.
`zlib.h` requires an operator generated from a length by `crc32_combine_gen`. The domain here
is exactly those mathematical operators, including its zero rejection result. Arbitrary forged
operators are not promised termination. Every permitted call has the polynomial result and
preserves the whole heap. -/
def Goal.crc32_combine_op : Prop :=
  ∀ (h : Heap) (first second : UInt64) (length : Int64), CrcGlobals h →
    C.run (Zlib.Crc32.crc32_combine_op first second (crcOperator length)) h =
      .ok (crcCombined first second length, h)
Related definitions and source ↗
ZLIB × LEAN

Contents

READING NOWcrc32_combine_op