Add crc32c to the list of invertible functions.

[alexey-milovidov]

crc32c instruction from SSE4.2 has latency of 3 cycles (similar to integer multiplication) and thoughput of 1 operation per cycle. It is invertible on uint32. If you change one bit of input, only one bit of output is changed and other are unchanged.

The operation itself is very bad as generic hash function (no avalanche), but it can be used in construction of hash functions. Or it can be used as a hash function in some applications where avalanche property is unneeded.

[Bulat-Ziganshin]

If you change one bit of input, only one bit of output is changed and other are unchanged.

I wonder what do you mean here? It has two operands and crc32c(base,x) == crc32c(0,x) ^ base, so the first operand indeed isn't very useful. But each bit of x value affects many bits of the result.

CRC is the remainder of polynomial division and as such, provides average quality hash - better than multiplication or a few add-rotate-xor operations, but comparable to integer remainder operation.

[alexey-milovidov]

Yes, my mistake.

Maybe this:

For every input X and state S, if you change single N-th bit of X, every bit of crc32(S, X) will either always change or always not change, regardless of value X.

Or this:

Xoring argument of crc with some constant is equivalent to xoring the result of crc with (some other) constant.

Or even this:

crc commutates with xor: crc(a ^ b) = crc(a) ^ crc(b)
or more specifically: crc(state, a ^ b) = crc(state, a) ^ crc(0, b)

[Logan007]

#13 was updated to support the CRC32c opcode, try -p crc32,mul,crc32. If I am not mistaken, this looks like a pretty low-bias class of hash functions.