From patchwork Tue Apr 5 05:30:49 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Emilio Cota X-Patchwork-Id: 8747721 Return-Path: X-Original-To: patchwork-qemu-devel@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id 7676AC0553 for ; Tue, 5 Apr 2016 05:34:35 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 5DDAD20225 for ; Tue, 5 Apr 2016 05:34:34 +0000 (UTC) Received: from lists.gnu.org (lists.gnu.org [208.118.235.17]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id 3898E201ED for ; Tue, 5 Apr 2016 05:34:33 +0000 (UTC) Received: from localhost ([::1]:34498 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1anJdI-0008DH-Ka for patchwork-qemu-devel@patchwork.kernel.org; Tue, 05 Apr 2016 01:34:32 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:51942) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1anJa2-0001el-QO for qemu-devel@nongnu.org; Tue, 05 Apr 2016 01:31:12 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1anJZy-0005TW-6P for qemu-devel@nongnu.org; Tue, 05 Apr 2016 01:31:10 -0400 Received: from out5-smtp.messagingengine.com ([66.111.4.29]:50232) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1anJZy-0005T5-3O for qemu-devel@nongnu.org; Tue, 05 Apr 2016 01:31:06 -0400 Received: from compute2.internal (compute2.nyi.internal [10.202.2.42]) by mailout.nyi.internal (Postfix) with ESMTP id 497D820DB9 for ; Tue, 5 Apr 2016 01:31:05 -0400 (EDT) Received: from frontend1 ([10.202.2.160]) by compute2.internal (MEProxy); Tue, 05 Apr 2016 01:31:05 -0400 DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=braap.org; h=cc :date:from:in-reply-to:message-id:references:subject:to :x-sasl-enc:x-sasl-enc; s=mesmtp; bh=/6XEzSSDc4poIX/8hBh4KGSxmr0 =; b=nQ0g0TYyrZ7hPMx35xj+vmnzUnrR1T0KS0bkJ9qAMMFu5MgSRVUax2N779O JzCD6bhbtzm3NIxfi8+praSyCG9JCw7YL5O5Lyqa7TbzuSAaS+pynWl0zsGnxdFo YZMyI/XKI+qXSTJ2I5x4cbqr9IntzVu0WW6cEtJS0+h+IOVU= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d= messagingengine.com; h=cc:date:from:in-reply-to:message-id :references:subject:to:x-sasl-enc:x-sasl-enc; s=smtpout; bh=/6XE zSSDc4poIX/8hBh4KGSxmr0=; b=Sk8Y9kGhfhp4bIUn1++3mSsdrZuZY8bR42Pj 39T9ev/6V4ysfjRMA4UDytNnwBD/JcKCyV8Wo9HTZFrYwubMvCGCMGtfVkjI9taV SswGCmVaQHeo1n7RJ9n/AqkXI7iC0cJBEKZm/MjMQ96pfDRxRKC5rTnJ5CyrOsQ5 GmoZDzQ= X-Sasl-enc: b9x4GcImptbt5TehZECzbUZE47q+Az7R/66QPoG4767w 1459834265 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 050C7C00018; Tue, 5 Apr 2016 01:31:05 -0400 (EDT) From: "Emilio G. Cota" To: QEMU Developers , MTTCG Devel Date: Tue, 5 Apr 2016 01:30:49 -0400 Message-Id: <1459834253-8291-7-git-send-email-cota@braap.org> X-Mailer: git-send-email 2.5.0 In-Reply-To: <1459834253-8291-1-git-send-email-cota@braap.org> References: <1459834253-8291-1-git-send-email-cota@braap.org> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 66.111.4.29 Cc: Peter Maydell , Peter Crosthwaite , Sergey Fedorov , Paolo Bonzini , =?UTF-8?q?Alex=20Benn=C3=A9e?= , Richard Henderson Subject: [Qemu-devel] [PATCH 06/10] include: add xxhash.h X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org X-Spam-Status: No, score=-6.8 required=5.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI, T_DKIM_INVALID, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP 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 @@ +/* + * 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 QEMU_XXHASH_H +#define QEMU_XXHASH_H + +#define PRIME32_1 2654435761U +#define PRIME32_2 2246822519U +#define PRIME32_3 3266489917U +#define PRIME32_4 668265263U +#define PRIME32_5 374761393U + +/* + * Note : although _rotl exists for minGW (GCC under windows), performance + * seems poor. + */ +#if defined(_MSC_VER) +# define XXH_rotl32(x, r) _rotl(x, r) +#else +# define XXH_rotl32(x, r) ((x << r) | (x >> (32 - r))) +#endif + +/* 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) +{ + 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; + } + + 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 */