> 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