4 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
by 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 agoWell, 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
- Cyan4973 8y agoFollowing your suggestion, I went ahead and modified the scrambling formula. The crux of the problem is that the secret is allowed to be absolutely anything (it's user provided). As a consequence, it's a bad idea to depend on it for the multiplier. Now, the secret key only function is to be a mask, while the multiplier is under implementation control, guaranteeing a good prime.