From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:39974) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1anloJ-0006tQ-9w for qemu-devel@nongnu.org; Wed, 06 Apr 2016 07:39:48 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1anloF-0007zF-4D for qemu-devel@nongnu.org; Wed, 06 Apr 2016 07:39:47 -0400 Received: from mail-wm0-x232.google.com ([2a00:1450:400c:c09::232]:32960) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1anloE-0007yw-Ci for qemu-devel@nongnu.org; Wed, 06 Apr 2016 07:39:43 -0400 Received: by mail-wm0-x232.google.com with SMTP id f198so69419436wme.0 for ; Wed, 06 Apr 2016 04:39:41 -0700 (PDT) References: <1459834253-8291-1-git-send-email-cota@braap.org> <1459834253-8291-7-git-send-email-cota@braap.org> From: Alex =?utf-8?Q?Benn=C3=A9e?= In-reply-to: <1459834253-8291-7-git-send-email-cota@braap.org> Date: Wed, 06 Apr 2016 12:39:42 +0100 Message-ID: <87lh4rarup.fsf@linaro.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit Subject: Re: [Qemu-devel] [PATCH 06/10] include: add xxhash.h List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: "Emilio G. Cota" Cc: MTTCG Devel , Peter Maydell , Peter Crosthwaite , QEMU Developers , Sergey Fedorov , Paolo Bonzini , Richard Henderson Emilio G. Cota writes: > xxhash is a fast, high-quality hashing function. The appended > brings in the 32-bit version of it, with the small modification that > it assumes the data to be hashed is made of 32-bit chunks; this increases > speed slightly for the use-case we care about, i.e. tb-hash. > > The original algorithm, as well as a 64-bit implementation, can be found at: > https://github.com/Cyan4973/xxHash > > Signed-off-by: Emilio G. Cota > --- > include/qemu/xxhash.h | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 106 insertions(+) > create mode 100644 include/qemu/xxhash.h > > diff --git a/include/qemu/xxhash.h b/include/qemu/xxhash.h > new file mode 100644 > index 0000000..a13a665 > --- /dev/null > +++ b/include/qemu/xxhash.h > @@ -0,0 +1,106 @@ > + > +/* u32 hash of @n contiguous chunks of u32's */ > +static inline uint32_t qemu_xxh32(const uint32_t *p, size_t n, uint32_t seed) > +{ What is the point of seed here? I looked on the original site to see if there was any guidance on tuning seed but couldn't find anything. I appreciate the compiler can inline the constant away but perhaps we should #define it and drop the parameter if we are not intending to modify it? Also it might be helpful to wrap the call to avoid getting the boilerplate sizing wrong: #define qemu_xxh32(s) qemu_xxh32_impl((const uint32_t *)s, sizeof(*s)/sizeof(uint32_t), 1) Then calls become a little simpler for the user: return qemu_xxh32(&k); Do we need to include a compile time check for structures that don't neatly divide into uint32_t chunks? > + const uint32_t *end = p + n; > + uint32_t h32; > + > + if (n >= 4) { > + const uint32_t * const limit = end - 4; > + uint32_t v1 = seed + PRIME32_1 + PRIME32_2; > + uint32_t v2 = seed + PRIME32_2; > + uint32_t v3 = seed + 0; > + uint32_t v4 = seed - PRIME32_1; > + > + do { > + v1 += *p * PRIME32_2; > + v1 = XXH_rotl32(v1, 13); > + v1 *= PRIME32_1; > + p++; > + v2 += *p * PRIME32_2; > + v2 = XXH_rotl32(v2, 13); > + v2 *= PRIME32_1; > + p++; > + v3 += *p * PRIME32_2; > + v3 = XXH_rotl32(v3, 13); > + v3 *= PRIME32_1; > + p++; > + v4 += *p * PRIME32_2; > + v4 = XXH_rotl32(v4, 13); > + v4 *= PRIME32_1; > + p++; > + } while (p <= limit); > + h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + > + XXH_rotl32(v4, 18); > + } else { > + h32 = seed + PRIME32_5; > + } I don't plead any particular knowledge of hashing codes but I note the test cases we add only exercise the n == 1 path but in actual usage we exercise n = 5 (at least for arm32, I guess aarch64 would be more). > + > + h32 += n * sizeof(uint32_t); > + > + while (p < end) { > + h32 += *p * PRIME32_3; > + h32 = XXH_rotl32(h32, 17) * PRIME32_4 ; > + p++; > + } > + > + h32 ^= h32 >> 15; > + h32 *= PRIME32_2; > + h32 ^= h32 >> 13; > + h32 *= PRIME32_3; > + h32 ^= h32 >> 16; > + > + return h32; > +} > + > +#endif /* QEMU_XXHASH_H */ -- Alex Bennée