Crc32 Class

The implementation uses the CRC32 instructions of Arm64 processors and the carry-less multiplication of x64 processors when they are available; it computes the same value as the byte-at-a-time method of the PNG specification, Annex D.

Crc32.UpdateTables processes 8 bytes per step with eight derived tables ("slicing by 8"): table k gives the contribution of a byte followed by k zero bytes, T[k][i] = (T[k - 1][i] >> 8) ^ T[0][T[k - 1][i] & 0xFF], which is the byte-at-a-time recurrence applied k more times. The result is the CRC of the reference loop (Crc32.UpdateScalar); about 5 times faster on the chunk sizes of PNG files.

Arm64 processors have instructions for this very polynomial (the CRC32 extension): Crc32.Update uses them when they are available, 8 bytes per instruction, which is several times faster again and gives the same value.

x64 processors have a carry-less multiplication (PCLMULQDQ), which Crc32.UpdateCarrylessMultiply uses to fold the data 64 bytes at a time. The CRC is linear: the CRC of a message equals the CRC of any shorter message whose polynomial is congruent modulo the generator P once aligned. A 128-bit block A = A_hi x^64 + A_lo followed by D bits contributes like A_hi (x^(D+64) mod P) + A_lo (x^D mod P), which has fewer than 96 bits and is added to the block D bits further. The running CRC is added to the first 4 bytes, the blocks are folded onto the last 16 bytes of the whole blocks, and the CRC of these 16 bytes and of the remaining bytes, from zero, is the result. In the reflected bit order of this CRC, a block loaded as a little-endian 128-bit value has the coefficient of x^(127 - i) at bit i; a constant c = x (x^(n-1) mod P), of degree 1 to 32, is stored with the coefficient of x^(64 - j) at bit j, so that the carry-less product of a half and a constant has the same layout as a block, without a shift. The constants are computed from P when the type is initialized.