From patchwork Wed May 25 01:13:13 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Emilio Cota X-Patchwork-Id: 625980 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from lists.gnu.org (lists.gnu.org [IPv6:2001:4830:134:3::11]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3rDvVD3WsVz9t3Z for ; Wed, 25 May 2016 11:15:48 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=braap.org header.i=@braap.org header.b=WWw4KEVb; dkim=fail reason="signature verification failed" (1024-bit key; unprotected) header.d=messagingengine.com header.i=@messagingengine.com header.b=kiuBCsnf; dkim-atps=neutral Received: from localhost ([::1]:56493 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1b5NQI-00038M-6E for incoming@patchwork.ozlabs.org; Tue, 24 May 2016 21:15:46 -0400 Received: from eggs.gnu.org ([2001:4830:134:3::10]:49785) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1b5NOm-0001l6-G2 for qemu-devel@nongnu.org; Tue, 24 May 2016 21:14:23 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1b5NOH-0007fu-VO for qemu-devel@nongnu.org; Tue, 24 May 2016 21:14:12 -0400 Received: from out2-smtp.messagingengine.com ([66.111.4.26]:47019) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1b5NOF-0007cK-FK for qemu-devel@nongnu.org; Tue, 24 May 2016 21:13:41 -0400 Received: from compute3.internal (compute3.nyi.internal [10.202.2.43]) by mailout.nyi.internal (Postfix) with ESMTP id E015920CA6; Tue, 24 May 2016 21:13:25 -0400 (EDT) Received: from frontend2 ([10.202.2.161]) by compute3.internal (MEProxy); Tue, 24 May 2016 21:13:26 -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=OgJq4TGrnjc/FXxYNecgK0lOA8M =; b=WWw4KEVb/NPeXVojQVzRfbBsupKEg5FVevn0XwPgCb+pb66qR4r3vPqHk5l 0MCtsl96LufGi8KHP7zpRPsdPxssv7BKDhJraVgeUEn5qV6wXygHfueKI46rUgdw ggyBixZvAVaRNIfN3h4pWi+bbqodKGZdS1r0SuvNVJbITPPU= 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=OgJq 4TGrnjc/FXxYNecgK0lOA8M=; b=kiuBCsnfLm4MsohA08fSCzl24RfmA74lJrN+ bzL8aQsEO0XTPJjOHhyEkZUy1gTPh2NGHasvb2Tr40NDY6wSGimQIonjACyyED3Z 0tY9WUiBQGCF4B5bToA5ei/+KESCXt//MeOR3SY4795kwWOOSTna/Z3OUWSkhx+P wHqb6Gg= X-Sasl-enc: y2uAc+67En7bzQ/8Zz9yzAYZQ/MBTq6PdJFCxYzh9uMI 1464138805 Received: from localhost (flamenco.cs.columbia.edu [128.59.20.216]) by mail.messagingengine.com (Postfix) with ESMTPA id 887BACCD3A; Tue, 24 May 2016 21:13:25 -0400 (EDT) From: "Emilio G. Cota" To: QEMU Developers , MTTCG Devel Date: Tue, 24 May 2016 21:13:13 -0400 Message-Id: <1464138802-23503-7-git-send-email-cota@braap.org> X-Mailer: git-send-email 2.5.0 In-Reply-To: <1464138802-23503-1-git-send-email-cota@braap.org> References: <1464138802-23503-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.26 Subject: [Qemu-devel] [PATCH v6 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: Paolo Bonzini , Sergey Fedorov , =?UTF-8?q?Alex=20Benn=C3=A9e?= , Richard Henderson Errors-To: qemu-devel-bounces+incoming=patchwork.ozlabs.org@nongnu.org Sender: "Qemu-devel" 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 Reviewed-by: Sergey Fedorov --- 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 */