From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:4830:134:3::10]:51869) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1b2ihv-00056n-6c for qemu-devel@nongnu.org; Tue, 17 May 2016 13:23:00 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1b2ihr-0006KP-OV for qemu-devel@nongnu.org; Tue, 17 May 2016 13:22:58 -0400 Received: from mail-lb0-x244.google.com ([2a00:1450:4010:c04::244]:33980) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1b2ihr-0006KD-C5 for qemu-devel@nongnu.org; Tue, 17 May 2016 13:22:55 -0400 Received: by mail-lb0-x244.google.com with SMTP id bg8so1392731lbc.1 for ; Tue, 17 May 2016 10:22:55 -0700 (PDT) References: <1463196873-17737-1-git-send-email-cota@braap.org> <1463196873-17737-9-git-send-email-cota@braap.org> From: Sergey Fedorov Message-ID: <573B536C.90804@gmail.com> Date: Tue, 17 May 2016 20:22:52 +0300 MIME-Version: 1.0 In-Reply-To: <1463196873-17737-9-git-send-email-cota@braap.org> Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: 7bit Subject: Re: [Qemu-devel] [PATCH v5 08/18] exec: add tb_hash_func5, derived from xxhash List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , To: "Emilio G. Cota" , QEMU Developers , MTTCG Devel Cc: =?UTF-8?Q?Alex_Benn=c3=a9e?= , Paolo Bonzini , Peter Crosthwaite , Richard Henderson On 14/05/16 06:34, Emilio G. Cota wrote: > This will be used by upcoming changes for hashing the tb hash. > > Add this into a separate file to include the copyright notice from > xxhash. > > Reviewed-by: Richard Henderson > Signed-off-by: Emilio G. Cota > --- > include/exec/tb-hash-xx.h | 94 +++++++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 94 insertions(+) > create mode 100644 include/exec/tb-hash-xx.h > > diff --git a/include/exec/tb-hash-xx.h b/include/exec/tb-hash-xx.h > new file mode 100644 > index 0000000..67f4e6f > --- /dev/null > +++ b/include/exec/tb-hash-xx.h > @@ -0,0 +1,94 @@ > +/* > + * xxHash - Fast Hash algorithm > + * Copyright (C) 2012-2016, Yann Collet > + * > + * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) > + * > + * Redistribution and use in source and binary forms, with or without > + * modification, are permitted provided that the following conditions are > + * met: > + * > + * + Redistributions of source code must retain the above copyright > + * notice, this list of conditions and the following disclaimer. > + * + Redistributions in binary form must reproduce the above > + * copyright notice, this list of conditions and the following disclaimer > + * in the documentation and/or other materials provided with the > + * distribution. > + * > + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS > + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT > + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR > + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT > + * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, > + * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT > + * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, > + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY > + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT > + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE > + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. > + * > + * You can contact the author at : > + * - xxHash source repository : https://github.com/Cyan4973/xxHash > + */ > +#ifndef EXEC_TB_HASH_XX > +#define EXEC_TB_HASH_XX > + > +#include > + > +#define PRIME32_1 2654435761U > +#define PRIME32_2 2246822519U > +#define PRIME32_3 3266489917U > +#define PRIME32_4 668265263U > +#define PRIME32_5 374761393U > + > +#define TB_HASH_XX_SEED 1 > + > +/* > + * xxhash32, customized for input variables that are not guaranteed to be > + * contiguous in memory. > + */ > +static inline > +uint32_t tb_hash_func5(uint64_t a0, uint64_t b0, uint32_t e) > +{ > + uint32_t v1 = TB_HASH_XX_SEED + PRIME32_1 + PRIME32_2; > + uint32_t v2 = TB_HASH_XX_SEED + PRIME32_2; > + uint32_t v3 = TB_HASH_XX_SEED + 0; > + uint32_t v4 = TB_HASH_XX_SEED - PRIME32_1; > + uint32_t a = a0 >> 31 >> 1; I'm wondering if there's something special forcing us to make ">> 31 >>1" instead of just ">> 32" on uint64_t? Kind regards, Sergey > + uint32_t b = a0; > + uint32_t c = b0 >> 31 >> 1; > + uint32_t d = b0; > + uint32_t h32; > + > + v1 += a * PRIME32_2; > + v1 = rol32(v1, 13); > + v1 *= PRIME32_1; > + > + v2 += b * PRIME32_2; > + v2 = rol32(v2, 13); > + v2 *= PRIME32_1; > + > + v3 += c * PRIME32_2; > + v3 = rol32(v3, 13); > + v3 *= PRIME32_1; > + > + v4 += d * PRIME32_2; > + v4 = rol32(v4, 13); > + v4 *= PRIME32_1; > + > + h32 = rol32(v1, 1) + rol32(v2, 7) + rol32(v3, 12) + rol32(v4, 18); > + h32 += 20; > + > + h32 += e * PRIME32_3; > + h32 = rol32(h32, 17) * PRIME32_4; > + > + h32 ^= h32 >> 15; > + h32 *= PRIME32_2; > + h32 ^= h32 >> 13; > + h32 *= PRIME32_3; > + h32 ^= h32 >> 16; > + > + return h32; > +} > + > +#endif /* EXEC_TB_HASH_XX */