tree c64bf7783cb0de34e38ec9942ecfbb830af7a4d9
parent 16b4b7554baadc57513a852542e0f4ad9910ea1c
author Nigel Tao <nigeltao@golang.org> 1616026779 +1100
committer Nigel Tao <nigeltao@golang.org> 1616026911 +1100

Replace SIMD CRC-32 k6' magic constant with Px'

This is just a change of name (and a change of comment), not a change of
value.

From my colleague, Eric Biggers:

The number is not k6' = (x^32 mod P(x) << 32)' << 1 = 0x1DB710640, but
rather P(x)' = 0x1DB710641. This value represents the generator
polynomial of CRC-32 as a 33-bit value, using the CRC-32 bit ordering
convention (lowest order bit = coefficient of highest order polynomial
term). The lowest order bit is the coefficient of x^32, which by
definition is 1 for CRC-32. P(x) is used as a multiplicand in Barrett
reduction, which is the step which reduces a 64-bit value to the final
32-bit remainder. See "Algorithm 1" in the Gopal paper.

The reason that last bit doesn't actually matter is because the output
of the Barrett reduction is supposed to be fully reduced mod P(x), so
only 32 bits (the bits that represent the coefficients of x^0..x^31) are
supposed to be able to be nonzero. Therefore, in practice
implementations will just truncate the result to 32 bits. Incorrectly
using 0x1DB710640 rather than P(x) = 0x1DB710641 only causes the result
to be wrong by a factor of x^32, so it doesn't affect those 32 bits.