5 ms·
https://github.com/RedSpah/xxhash_cpp/blob/master/xxhash/xxhash.cpp https://github.com/RedSpah/xxhash_cpp/blob/master/xxhash/xxh... The core of the function is
by dragontamer 8y ago
https://github.com/RedSpah/xxhash_cpp/blob/master/xxhash/xxhash.cpp https://github.com/RedSpah/xxhash_cpp/blob/master/xxhash/xxh...
The core of the function is as follows:
static U64 XXH64_round(U64 acc, U64 input)
{
acc += input * PRIME64_2;
acc = XXH_rotl64(acc, 31);
acc *= PRIME64_1;
return acc;
}
Multiplication, rotation, and a 2nd multiplication. These are 64-bit multiplications, which is well known to mix bits well, but CPUs don't have many 64-bit multipliers. Four rounds execute in parallel (see XXH64_update_endian), which can hide the long latency (~5 cycles) associated with a 64-bit multiply.
My own experiments show that multiplication is a great function for hashing. Multiplication however only spreads the bits in "one direction" (towards the most-significant bit), and very poorly spreads bits towards the LSB.
Rotations, as well as a 2nd multiplication, are helpful at spreading the bits around better.
----------
The 64-bit version is somewhat interesting to me, but the 32-bit version probably has more potential for optimization. 32-bit vectorized multiplication exists in AVX2, so the 32-bit version probably can be vectorized. I'd expect the 32-bit version (if vectorized) would be faster, but the 64-bit version probably mixes the bits around better.
Overall looks like a decent design. Uses ILP with 4x state variables (state->v1, state->v2, etc. etc. to allow CPUs to process these multiplications in parallel). Multiply + rotation + multiplication is good from my personal experiments, but the numbers chosen need to be carefully chosen.
Prime numbers are probably not necessary: they just need to be odd numbers to ensure invertibility (Ex: I've achieved decent mixing by multiplying with 0xAAAAAAAA5, which probably isn't a prime number). I'm curious how the prime-constants were selected. There could be some potential for "better numbers" for mixing, depending on how PRIME64_1 and PRIME64_2 were chosen.
Overall checks all of my boxes with regards to good design. Nice! I'm just curious about some details.
----------
I'll note that in my experiments, multiplication seems to "mix" better with XOR, rather than with ADD. I haven't done any tests with this hash yet, but I'm curious how changing the "+=" into "^=" would have on the statistical strength of the hash function.
- petschge 8y agoIf I am not mistaken 0xAAAAAAAA5 is 45812984485 = 5 * 28297 * 323801. At least that is what factor $(echo -e "ibase=16\nAAAAAAAA5" | bc -l) claims.
- dragontamer 8y agoOh man, a typo. Lol. I meant 0xAAAAAAA5... sorry about that. Lemme muse on the concept: "multiplying by 0xAAAAAAA5" is that the binary is 1010,1010,1010...0101. A multiplication at its core, is equivalent to a LOT of bitshift-left and add. Multiplying by "1000" is the same as bitshift left by 4. Multiplying by "1010" is bitshift left by 4 + bitshift left by 2. This is why its important to multiply by an odd number: all those bitshifts lose the top-most bit. You only keep the topmost bit if the bottom-most bit is set. So multiply by 0xAAAAAAA5 is the same as "bitshift left 31 + bitshift left 29 + bitshift left 27 ... + bitshift left 2 + bitshift left 0", all at once. Addition itself is a great "mixing" instruction, its an XOR innately with the potential for carries. The carries make the XORs far more complicated to analyze. The 31st bit after all of those bitshifts are not only the XOR of a bunch of bits... but also the "propagated carry bit". The topmost bit of any multiplication operation is very complex, while the bottom most bit is always the original bit (bit0 is only affected by bit0 from the input). That's why a rotation + 2nd multiply is needed.
- andromeduck 8y agoAddition and multiplication also leak more information via side channels than bit shift and xor.
- dragontamer 8y agoI'd be surprised if that's true. I'm pretty sure addition is always 1-clock tick latency / 3-instructions per cycle. While Multiplication is 5-clock tick latency / 1-instruction per cycle IIRC. So if the timing of those instructions are constant, it seems difficult to side-channel / timing attack them.
- andromeduck 8y agothere's also power, 0xffffffff + 0x1 results in 32 bit flips, 0x0 + 0x1 results in 1, they don't consume the same amount of energy.
- 8y ago
- terrelln 8y agoI believe you are looking at XXH64 and XXH32, which is the old version. The new version XXH3 is located in https://github.com/Cyan4973/xxHash/blob/dev/xxh3.h https://github.com/Cyan4973/xxHash/blob/dev/xxh3.h which exposes the public prototypes `XXH3_64bits()` and `XXH3_128bits()` (and variants with seeds).
- dragontamer 8y agoThanks. This code is IMO far easier to read, despite being intrinsics. It just requires some familiarity with shuffle. Anyone who wants to follow along should use: https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=_mm256_shuffle_epi32&expand=5113 https://software.intel.com/sites/landingpage/IntrinsicsGuide... assert(((size_t)acc) & 31 == 0); { ALIGN(32) __m256i* const xacc = (__m256i *) acc; const __m256i* const xdata = (const __m256i *) data; const __m256i* const xkey = (const __m256i *) key; size_t i; for (i=0; i < STRIPE_LEN/sizeof(__m256i); i++) { __m256i const d = _mm256_loadu_si256 (xdata+i); __m256i const k = _mm256_loadu_si256 (xkey+i); __m256i const dk = _mm256_add_epi32 (d,k); /* uint32 dk[8] = {d0+k0, d1+k1, d2+k2, d3+k3, ...} */ __m256i const res = _mm256_mul_epu32 (dk, _mm256_shuffle_epi32 (dk, 0x31)); /* uint64 res[4] = {dk0*dk1, dk2*dk3, ...} */ __m256i const add = _mm256_add_epi64(d, xacc[i]); xacc[i] = _mm256_add_epi64(res, add); } } This is followed up by "ScrambleAcc": assert(((size_t)acc) & 31 == 0); { ALIGN(32) __m256i* const xacc = (__m256i*) acc; const __m256i* const xkey = (const __m256i *) key; size_t i; for (i=0; i < STRIPE_LEN/sizeof(__m256i); i++) { __m256i data = xacc[i]; __m256i const shifted = _mm256_srli_epi64(data, 47); data = _mm256_xor_si256(data, shifted); { __m256i const k = _mm256_loadu_si256 (xkey+i); __m256i const dk = _mm256_mul_epu32 (data,k); /* U32 dk[4] = {d0+k0, d1+k1, d2+k2, d3+k3} */ __m256i const d2 = _mm256_shuffle_epi32 (data,0x31); __m256i const k2 = _mm256_shuffle_epi32 (k,0x31); __m256i const dk2 = _mm256_mul_epu32 (d2,k2); /* U32 dk[4] = {d0+k0, d1+k1, d2+k2, d3+k3} */ xacc[i] = _mm256_xor_si256(dk, dk2); } } } I don't believe AVX2 rotation exists (correct me if I'm wrong though). So the author has opted for _mm256_srli_epi64 (... 47), which is a 47-bit right shift, followed up with XOR. This is how the author gets those "highly mixed" high-bits back down to the lower-bits. Vectorization has broadened to 512-bits of state (4x128) so that the vectorized steps can be ILP'd. The keys are: ALIGN(64) static const U32 kKey[KEYSET_DEFAULT_SIZE] = { 0xb8fe6c39,0x23a44bbe,0x7c01812c,0xf721ad1c, 0xded46de9,0x839097db,0x7240a4a4,0xb7b3671f, 0xcb79e64e,0xccc0e578,0x825ad07d,0xccff7221, 0xb8084674,0xf743248e,0xe03590e6,0x813a264c, 0x3c2852bb,0x91c300cb,0x88d0658b,0x1b532ea3, 0x71644897,0xa20df94e,0x3819ef46,0xa9deacd8, 0xa8fa763f,0xe39c343f,0xf9dcbbc7,0xc70b4f1d, 0x8a51e04b,0xcdb45931,0xc89f7ec9,0xd9787364, 0xeac5ac83,0x34d3ebc3,0xc581a0ff,0xfa1363eb, 0x170ddd51,0xb7f0da49,0xd3165526,0x29d4689e, 0x2b16be58,0x7d47a1fc,0x8ff8b8d1,0x7ad031ce, 0x45cb3a8f,0x95160428,0xafd7fbca,0xbb4b407e, }; Hmmm... this key is added with the data as it gets mixed in. --------- Definitely seems like cleaner code actually. Again, I'm not seeing any obvious red-flags in the code, so it looks pretty good to me. The only thing is that the 32-bit to 64-bit multiply step seems odd to me. It probably isn't losing any information, but I'm kind of mind-farting and can't see whether or not that step is potentially losing entropy or not... I'll probably have to sleep on it. Specifically this step: __m256i const res = _mm256_mul_epu32 (dk, _mm256_shuffle_epi32 (dk, 0x31)); /* uint64 res[4] = {dk0*dk1, dk2*dk3, ...} */ Those numbers aren't necessarily odd. Its a 32-bit multiply that takes two 32-bit numbers, and outputs a 64-bit number (vectorized). It doesn't seem like a "strong" hash, but maybe I need to think about it more. If this is a good hash (and with all the tests done on it... it probably is a good hash), then I'd be surprised. It reminds me of a RNG that Knuth discussed in his book: where you multiply two numbers and then take the "middle" results of the multiplication (https://en.wikipedia.org/wiki/Middle-square_method https://en.wikipedia.org/wiki/Middle-square_method). So I feel like there's potential for weakness here. I can't see it one way or the other yet, its just something I'm trying to think about...