6 ms·

I 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 ht

I 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 ago
Thanks. 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...
- Cyan4973 8y ago
  According to the UMAC paper, the 32x32=>64 multiplication only contains 32-bit of entropy, even though it uses 64-bit space. That's understandable : most of the entropy will be in the middle of the register. That's enough for XXH3. Since it maintains a 512-bit internal state, that means it transports 256-bit of entropy.
  - dragontamer 8y ago
    But there's 64-bits of input (32-bit A x 32-bit B). So if you have 64-bits of input, but only result in 32-bits of output entropy, then you've lost information. I realize you have to compress data down in a Hash function somehow, but ideally you want to minimize the loss of entropy / information from the input bits. The ideal mixing function would have 512-bits of internal state, with 512-bits of entropy starting off... and ending with 512-bits of entropy once all the mixing were done. If your factoid is correct, then we're starting with 512-bits of entropy, but only 256-bits of entropy after the multiply. > That's enough for XXH3. Since it maintains a 512-bit internal state, that means it transports 256-bit of entropy. Why not optimize the function, and aim for only 256-bits of internal state (with 256-bits of entropy) ?? See: you can cut down on state and possibly improve performance. Maybe not on Intel Skylake, but probably on ARM Neon / AMD Zen (which have 128-bit SIMD registers internally). Hmmmm... 512-bit (aka 2x AVX2 registers) is probably needed to get good ILP on Intel processors. So there probably wouldn't be much improvement for Intel. ----------- Again though: I'm not sure if its losing information yet. Its just something I'm thinking about... (32-bit XOR would be 32-bit + 32-bit input, with only 32-bits of entropy output. But unlike multiply, you only have 32-bits of state) 32-bit multiplication with a constant, keeping only the bottom 32-bits, keeps all 32-bits of entropy without being forced to expand to 64-bits. I definitely like the bit-mixing properties of multiply, its just difficult to find configurations of multiplication that saves every bit of entropy.
    - Cyan4973 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. 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

Thanks. 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...

Cyan4973 8y ago
According to the UMAC paper, the 32x32=>64 multiplication only contains 32-bit of entropy, even though it uses 64-bit space. That's understandable : most of the entropy will be in the middle of the register. That's enough for XXH3. Since it maintains a 512-bit internal state, that means it transports 256-bit of entropy.
- dragontamer 8y ago
  But there's 64-bits of input (32-bit A x 32-bit B). So if you have 64-bits of input, but only result in 32-bits of output entropy, then you've lost information. I realize you have to compress data down in a Hash function somehow, but ideally you want to minimize the loss of entropy / information from the input bits. The ideal mixing function would have 512-bits of internal state, with 512-bits of entropy starting off... and ending with 512-bits of entropy once all the mixing were done. If your factoid is correct, then we're starting with 512-bits of entropy, but only 256-bits of entropy after the multiply. > That's enough for XXH3. Since it maintains a 512-bit internal state, that means it transports 256-bit of entropy. Why not optimize the function, and aim for only 256-bits of internal state (with 256-bits of entropy) ?? See: you can cut down on state and possibly improve performance. Maybe not on Intel Skylake, but probably on ARM Neon / AMD Zen (which have 128-bit SIMD registers internally). Hmmmm... 512-bit (aka 2x AVX2 registers) is probably needed to get good ILP on Intel processors. So there probably wouldn't be much improvement for Intel. ----------- Again though: I'm not sure if its losing information yet. Its just something I'm thinking about... (32-bit XOR would be 32-bit + 32-bit input, with only 32-bits of entropy output. But unlike multiply, you only have 32-bits of state) 32-bit multiplication with a constant, keeping only the bottom 32-bits, keeps all 32-bits of entropy without being forced to expand to 64-bits. I definitely like the bit-mixing properties of multiply, its just difficult to find configurations of multiplication that saves every bit of entropy.
  - Cyan4973 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. 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.