From patchwork Fri Jun 10 14:26:44 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Richard Henderson X-Patchwork-Id: 9169925 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 712D56048C for ; Fri, 10 Jun 2016 14:27:45 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 60A042833F for ; Fri, 10 Jun 2016 14:27:45 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 5595728363; Fri, 10 Jun 2016 14:27:45 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 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.wl.linuxfoundation.org (Postfix) with ESMTPS id 586B928342 for ; Fri, 10 Jun 2016 14:27:43 +0000 (UTC) Received: from localhost ([::1]:41408 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bBNPS-0003ir-EQ for patchwork-qemu-devel@patchwork.kernel.org; Fri, 10 Jun 2016 10:27:42 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:46320) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bBNOq-0003el-PL for qemu-devel@nongnu.org; Fri, 10 Jun 2016 10:27:06 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1bBNOl-0005gv-Td for qemu-devel@nongnu.org; Fri, 10 Jun 2016 10:27:03 -0400 Received: from mail-pf0-x243.google.com ([2607:f8b0:400e:c00::243]:36013) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1bBNOl-0005gm-Jn for qemu-devel@nongnu.org; Fri, 10 Jun 2016 10:26:59 -0400 Received: by mail-pf0-x243.google.com with SMTP id 62so5248058pfd.3 for ; Fri, 10 Jun 2016 07:26:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=sender:from:to:cc:subject:date:message-id:in-reply-to:references; bh=Xk8exyNSktO908Du0RSl4J5pOe1bwgA+fG3QokqUYxQ=; b=zTcgb0+HdVQqauNmPvNHfUsdF0p1AzZOUhb20sKynL5P5KxaZtvXj0TE6B26DV+qh4 rSVggJd3FcBO56/ZDmyV52hHYx1oUFtGnN247bhfgPh3Me+MkJoS58LwVBfNjbrLG7Ca HiNUYow3lf5Vn9vXr0ImKjcfR1dmsrnMt9nqchrMJCZ5hs3RPMnvipHfD8SX5xEisii9 C62IpQL++Z4GDceHjlv5avb9c+hl2rLzmi0AHEWj4pG/Qxt1pttdlUBeCx5WSJh9Wq3w 2ybDKF/B4dr8yvxGpDkH4pXc60B1RSwZCJxD8wErrf0WZk53dtlwgtzycNX8fRusTNgH 1m8Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:sender:from:to:cc:subject:date:message-id :in-reply-to:references; bh=Xk8exyNSktO908Du0RSl4J5pOe1bwgA+fG3QokqUYxQ=; b=SXRi2ntHZ/h5FgtxVsPyag2njFyzdPpxpK2xp2Hmh8YZJG8dhYMIFOjq2c9TKXW3JW 9mGv2Dl22WbtgHXlySK+d4gU93QpNWlIsbDaKrQfa0Rifi8N3Vcsl3mO0i+wkqkhT2qX N2qNd42rqMRYufKYWYRCB1PJldFykSD+WRLP5E8Yp5fnHcbrYNs3mt4zQNYW8i780gKf r5PFpqi+3B9sp7l02GLaY381LFK0t+Rln/2Lx6VloU7oRquSLfBYtQfFDzzhdg+rfLnb FwAPf6uKt5Jew9+kbw5iBmv2he19LOq+CVH9J4axI/WlOFhMyrTNGQbp6/qsIC7jgfWH ozCA== X-Gm-Message-State: ALyK8tJmoipQMbNd/TPlIj4XyRugBfiS21J+t06lW0X3Rf6f/Iq5or3MGigGblQNGwCRfA== X-Received: by 10.98.72.150 with SMTP id q22mr2633201pfi.122.1465568818787; Fri, 10 Jun 2016 07:26:58 -0700 (PDT) Received: from anchor.twiddle.net (71-37-54-227.tukw.qwest.net. [71.37.54.227]) by smtp.gmail.com with ESMTPSA id vy8sm18227219pab.22.2016.06.10.07.26.58 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 10 Jun 2016 07:26:58 -0700 (PDT) From: Richard Henderson To: qemu-devel@nongnu.org Date: Fri, 10 Jun 2016 07:26:44 -0700 Message-Id: <1465568813-19771-7-git-send-email-rth@twiddle.net> X-Mailer: git-send-email 2.5.5 In-Reply-To: <1465568813-19771-1-git-send-email-rth@twiddle.net> References: <1465568813-19771-1-git-send-email-rth@twiddle.net> X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 2607:f8b0:400e:c00::243 Subject: [Qemu-devel] [PULL 06/15] exec: add tb_hash_func5, derived from xxhash X-BeenThere: qemu-devel@nongnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: peter.maydell@linaro.org, "Emilio G. Cota" Errors-To: qemu-devel-bounces+patchwork-qemu-devel=patchwork.kernel.org@nongnu.org Sender: "Qemu-devel" X-Virus-Scanned: ClamAV using ClamSMTP From: "Emilio G. Cota" 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: Sergey Fedorov Reviewed-by: Richard Henderson Signed-off-by: Emilio G. Cota Message-Id: <1465412133-3029-7-git-send-email-cota@braap.org> Signed-off-by: Richard Henderson --- 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..9f3fc05 --- /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 >> 32; + uint32_t b = a0; + uint32_t c = b0 >> 32; + 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 */