7 ms·

It's not exactly "losing information". We are not trying to regenerate original data, just make sure that all source bits can fairly influence the result. It's

It's not exactly "losing information". We are not trying to regenerate original data, just make sure that all source bits can fairly influence the result. It's more a question of bit contribution. In the resulting 64-bit register, bit-0 can only be contributed by the first bit-0 of each 32-bit input. So it's only representative of these 2 bits. Same at the other end, bit-63 mostly depending on bit-31 of each 32-bit input, and also on carry over from previous bits (making things more complex). In the middle, many more bits participate, so that's where they are "well mixed". This question of bit distribution becomes critical if the 64-bit accumulator was used "as is" to produce a hash, but fortunately it's not. Accumulators will get mixed before that stage. When the mixing function is done correctly, every bit will get redistributed to the point of saturation. After which point, it does not matter that initially one accumulator's bit had less contributions than another : all source bits contributes fully. This can be easily verified with SMHasher's Avalanche test. Finally, XXH3 does not follow UMAC too closely, and adds an operation which ensures that all bits are necessarily present at least once in the accumulator. This compensate from the risk of multiplying by zero, which _is_ dangerous for checksumming, as it would nullify a contribution.

dragontamer 8y ago
> It's not exactly "losing information". We are not trying to regenerate original data, just make sure that all source bits can fairly influence the result. It's more a question of bit contribution. I agree. But entropy is a great concept that helps allow us to calculate whether or not "input bits" can affect "output bits". Lets look at XXH3_scrambleAcc: __m256i const k = _mm256_loadu_si256 (xkey+i); __m256i const dk = _mm256_mul_epu32 (data,k); __m256i const d2 = _mm256_shuffle_epi32 (data,0x31); __m256i const k2 = _mm256_shuffle_epi32 (k,0x31); __m256i const dk2 = _mm256_mul_epu32 (d2,k2); xacc[i] = _mm256_xor_si256(dk, dk2); Assume you start with 512-bits of input entropy (that is: assume that all 512-bits of state are uniformly random). Will you have 512-bits of uniformly random output after the above operations? Or to put it in your words: are you 100% sure that the above steps allow every input bit to affect every output bit? It appears not. My counter-example (not that I've debugged your code... but based on my reading) is as follows: key[2] is 0x7c01812c, and key[3] is 0xf721ad1c. This means that key[2] AND key[3] are even numbers. Which means dk.int64[1] bit0 will always be zero. And dk2.int64[1] bit0 will ALSO always be zero (on iteration 0, i=0) I bet you, at least... if I did my math correctly... that xacc[0].int64[1].bit0 will ALWAYS be zero, no matter what state you start with (bit#64 of xacc[0] == 0) This is because xacc[0].int64[1].bit0 = dk.int64[1].bit0 XOR dk2.int64[1].bit0 And both of those component parts seem to always be zero. Which means you're at LEAST wasting the 64th bit of state each time you perform XXH3_scrambleAcc. It certainly seems like a weakness of the XXH3_scrambleAcc function to me. That's a lot of operations you do, to literally throw away half your bits. There's probably an optimization you can do here to get better mixing.
- Cyan4973 8y ago
  Well, if you believe a better scrambling operation is possible, you are certainly welcomed to suggest one. Considering feedbacks on the algorithm is one of the objectives of the test phase. If the issue is about the default keys, it's also possible to change them, though one will also have to consider what happens with custom keys and if it implies ensuring some conditions (custom keys is a long-term objective of XXH3). At the end, XXH3 is only generating 64 and 128 bit hashes, and maybe 256 in the future, so compression necessarily happens somewhere. I believe the issue would be more pressing if the intention was to generate a 512-bit hash, but that has never been an objective.
  - dragontamer 8y ago
    > Well, if you believe a better scrambling operation is possible, you are certainly welcomed to suggest one. Oh, criticism of the algorithm is the easy part, especially when I'm being vague and can't think of solid proof of my suppositions. Coming up with a better scrambling operation is the hard part. :-) As I stated earlier, there are no obvious "red flags" in your algorithm. Its just this obscure part of the function that makes me think that optimization potential exists. Since you only have 256-bits of entropy in your 512-bit accumulator, my goal if I were to go through your code is to cut the state down to 256-bits, while keeping 256-bits of entropy. 1. All multiplication keys should be odd (bottom bit set to 1). This ensures that all multiplication steps that only keep the 32-bottom bits will keep all of their entropy. 2. Precisely throw away the top 32-bits of your multiplications, and only keep the bottom 32-bits. This will be slower, but it ensures full entropy when combined with odd numbers for the key. 3. Now that we have full entropy on the multiplication steps, cut down the 512-bit accumulator down to 256-bits, which should improve performance on AMD Zen / ARM NEON. It may help Intel Skylake, but Skylake is so wide that its hard to get ILP. -------------------- Without testing the code, here's an idea. __m256i const k = _mm256_loadu_si256 (xkey+i); __m256i const dk = _mm256_mul_epu32 (data,k); __m256i const d2 = _mm256_shuffle_epi32 (data,0x31); __m256i const k2 = _mm256_shuffle_epi32 (k,0x31); // <---- This line can be precomputed by the way... __m256i const dk2 = _mm256_mul_epu32 (d2,k2); // Above this line is the same code as before dk2= _mm256_shuffle_epi32 (dk2,0xc4); xacc[i] = _mm256_blend_epi32(dk, dk2, 0xaa); As long as the keys were all odd (bottom bit set to 1), the above should mix the bits without losing any entropy. So you can now have a 256-bit state. ---------- The accumulate portion would be simply: __m256i const add = _mm256_xor_epi64(d, xacc); xacc = _mm256_xor_epi64(res, add); XOR (or add) captures all the entropy from the input. In my experiments, XOR works better with multiply (I don't know why, but its just something I've noticed). But otherwise, its conceptually similar to your original "add" code. ---------- I mean, I'm just shooting from the hip here. I don't know how well the above code mixes things around. But those are kind of the steps that I would take to move forward. ---------- Although, if you want me to be 100% honest, anything I'd do "for real" would revolve around _mm_aesenc_si128. That'd be xacc[0] = _mm_aesenc_si128(xacc[0], data[0]); xacc[1] = _mm_aesdec_si128(xacc[1], data[1]); // Finalization: __m128i finalizationA = _mm_aesenc_si128(xacc[0], const1); finalizationA = _mm_aesenc_si128(finalizationA , const2); finalizationA = _mm_aesenc_si128(finalizationA , const3); finalizationA = _mm_aesenc_si128(finalizationA , const4); __m128i finalizationB = _mm_aesdec_si128(xacc[1], const1); finalizationB = _mm_aesdec_si128(finalizationB , const2); finalizationB = _mm_aesdec_si128(finalizationB , const3); finalizationB = _mm_aesdec_si128(finalizationB , const4); __m128i finalHash = _mm128_xor_epi64(finalizationA, finalizationB); // Return bottom 32, 64, or 128-bits of finalHash // 4 rounds of finalization should be enough. // Testing required to find the minimum for an avalanche condition. It will be more than 2, but probably less than 4... And... the end. That's it. Its only uses the 128-bit functionality of the execution units, but still gets ILP off of two parallel instances. So 256-bits of state. Its probably a fast function, but I can't be bothered to test it right now. I'm curious if the simpler functionality above would outspeed the 256-bit execution units on Skylake, but I don't have a Skylake box to test on (just AMD Zen). With AVX512, _mm512_aesenc_epi128 is possible to do this over 512-bits (4x 128-bit parallel instances of AES encryption). But I don't have a Skylake-X machine to test this idea with. See here for my experiment on AES functionality: https://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand

dragontamer 8y ago

> It's not exactly "losing information". We are not trying to regenerate original data, just make sure that all source bits can fairly influence the result. It's more a question of bit contribution. I agree. But entropy is a great concept that helps allow us to calculate whether or not "input bits" can affect "output bits". Lets look at XXH3_scrambleAcc: __m256i const k = _mm256_loadu_si256 (xkey+i); __m256i const dk = _mm256_mul_epu32 (data,k); __m256i const d2 = _mm256_shuffle_epi32 (data,0x31); __m256i const k2 = _mm256_shuffle_epi32 (k,0x31); __m256i const dk2 = _mm256_mul_epu32 (d2,k2); xacc[i] = _mm256_xor_si256(dk, dk2); Assume you start with 512-bits of input entropy (that is: assume that all 512-bits of state are uniformly random). Will you have 512-bits of uniformly random output after the above operations? Or to put it in your words: are you 100% sure that the above steps allow every input bit to affect every output bit? It appears not. My counter-example (not that I've debugged your code... but based on my reading) is as follows: key[2] is 0x7c01812c, and key[3] is 0xf721ad1c. This means that key[2] AND key[3] are even numbers. Which means dk.int64[1] bit0 will always be zero. And dk2.int64[1] bit0 will ALSO always be zero (on iteration 0, i=0) I bet you, at least... if I did my math correctly... that xacc[0].int64[1].bit0 will ALWAYS be zero, no matter what state you start with (bit#64 of xacc[0] == 0) This is because xacc[0].int64[1].bit0 = dk.int64[1].bit0 XOR dk2.int64[1].bit0 And both of those component parts seem to always be zero. Which means you're at LEAST wasting the 64th bit of state each time you perform XXH3_scrambleAcc. It certainly seems like a weakness of the XXH3_scrambleAcc function to me. That's a lot of operations you do, to literally throw away half your bits. There's probably an optimization you can do here to get better mixing.

Cyan4973 8y ago
Well, if you believe a better scrambling operation is possible, you are certainly welcomed to suggest one. Considering feedbacks on the algorithm is one of the objectives of the test phase. If the issue is about the default keys, it's also possible to change them, though one will also have to consider what happens with custom keys and if it implies ensuring some conditions (custom keys is a long-term objective of XXH3). At the end, XXH3 is only generating 64 and 128 bit hashes, and maybe 256 in the future, so compression necessarily happens somewhere. I believe the issue would be more pressing if the intention was to generate a 512-bit hash, but that has never been an objective.
- dragontamer 8y ago
  > Well, if you believe a better scrambling operation is possible, you are certainly welcomed to suggest one. Oh, criticism of the algorithm is the easy part, especially when I'm being vague and can't think of solid proof of my suppositions. Coming up with a better scrambling operation is the hard part. :-) As I stated earlier, there are no obvious "red flags" in your algorithm. Its just this obscure part of the function that makes me think that optimization potential exists. Since you only have 256-bits of entropy in your 512-bit accumulator, my goal if I were to go through your code is to cut the state down to 256-bits, while keeping 256-bits of entropy. 1. All multiplication keys should be odd (bottom bit set to 1). This ensures that all multiplication steps that only keep the 32-bottom bits will keep all of their entropy. 2. Precisely throw away the top 32-bits of your multiplications, and only keep the bottom 32-bits. This will be slower, but it ensures full entropy when combined with odd numbers for the key. 3. Now that we have full entropy on the multiplication steps, cut down the 512-bit accumulator down to 256-bits, which should improve performance on AMD Zen / ARM NEON. It may help Intel Skylake, but Skylake is so wide that its hard to get ILP. -------------------- Without testing the code, here's an idea. __m256i const k = _mm256_loadu_si256 (xkey+i); __m256i const dk = _mm256_mul_epu32 (data,k); __m256i const d2 = _mm256_shuffle_epi32 (data,0x31); __m256i const k2 = _mm256_shuffle_epi32 (k,0x31); // <---- This line can be precomputed by the way... __m256i const dk2 = _mm256_mul_epu32 (d2,k2); // Above this line is the same code as before dk2= _mm256_shuffle_epi32 (dk2,0xc4); xacc[i] = _mm256_blend_epi32(dk, dk2, 0xaa); As long as the keys were all odd (bottom bit set to 1), the above should mix the bits without losing any entropy. So you can now have a 256-bit state. ---------- The accumulate portion would be simply: __m256i const add = _mm256_xor_epi64(d, xacc); xacc = _mm256_xor_epi64(res, add); XOR (or add) captures all the entropy from the input. In my experiments, XOR works better with multiply (I don't know why, but its just something I've noticed). But otherwise, its conceptually similar to your original "add" code. ---------- I mean, I'm just shooting from the hip here. I don't know how well the above code mixes things around. But those are kind of the steps that I would take to move forward. ---------- Although, if you want me to be 100% honest, anything I'd do "for real" would revolve around _mm_aesenc_si128. That'd be xacc[0] = _mm_aesenc_si128(xacc[0], data[0]); xacc[1] = _mm_aesdec_si128(xacc[1], data[1]); // Finalization: __m128i finalizationA = _mm_aesenc_si128(xacc[0], const1); finalizationA = _mm_aesenc_si128(finalizationA , const2); finalizationA = _mm_aesenc_si128(finalizationA , const3); finalizationA = _mm_aesenc_si128(finalizationA , const4); __m128i finalizationB = _mm_aesdec_si128(xacc[1], const1); finalizationB = _mm_aesdec_si128(finalizationB , const2); finalizationB = _mm_aesdec_si128(finalizationB , const3); finalizationB = _mm_aesdec_si128(finalizationB , const4); __m128i finalHash = _mm128_xor_epi64(finalizationA, finalizationB); // Return bottom 32, 64, or 128-bits of finalHash // 4 rounds of finalization should be enough. // Testing required to find the minimum for an avalanche condition. It will be more than 2, but probably less than 4... And... the end. That's it. Its only uses the 128-bit functionality of the execution units, but still gets ILP off of two parallel instances. So 256-bits of state. Its probably a fast function, but I can't be bothered to test it right now. I'm curious if the simpler functionality above would outspeed the 256-bit execution units on Skylake, but I don't have a Skylake box to test on (just AMD Zen). With AVX512, _mm512_aesenc_epi128 is possible to do this over 512-bits (4x 128-bit parallel instances of AES encryption). But I don't have a Skylake-X machine to test this idea with. See here for my experiment on AES functionality: https://github.com/dragontamer/AESRand https://github.com/dragontamer/AESRand