From patchwork Fri Apr 19 21:31:50 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andi Kleen X-Patchwork-Id: 238117 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "localhost", Issuer "www.qmailtoaster.com" (not verified)) by ozlabs.org (Postfix) with ESMTPS id 6FECC2C0223 for ; Sat, 20 Apr 2013 07:32:58 +1000 (EST) DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references; q=dns; s= default; b=Nxh9oIPU90+jYfmByp0Pbp4Req+CqPJOC+ifOE+DsxHWwpjiQgTuq uhbXBeRfOqP7Ahw52BlJx2Ehuv8Z4xGMEKPBYWfi9mYvWugVMAXbUlWBINQXMf+Y eH/so7SJ3g6cDMGrgRlHLyD/Nmg0OcpSu1L6D9V09WMocnvxSVUhIE= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender:from :to:cc:subject:date:message-id:in-reply-to:references; s= default; bh=u3AOOqUtbJ+6yzjw9B1HUvWaCEA=; b=U5HbzzLll4Z1BCs6uKZ3 Zw1XqRQG4qm0kItsJ4KtQaAue2wH6Cuk/vGtb8k/w+kSKJofkQ55jk5bNLFjql22 eK7zSat2dZwLhTbrTTVr5MqaP4vxzv96TS/nViFMhpOyCn0YCGU2Z2PkDa8ZSxAw LnYTTO9hSV7pgLFc9y1DSNs= Received: (qmail 32553 invoked by alias); 19 Apr 2013 21:32:13 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 32453 invoked by uid 89); 19 Apr 2013 21:32:13 -0000 X-Spam-SWARE-Status: No, score=-3.7 required=5.0 tests=AWL, BAYES_00, KHOP_THREADED, RP_MATCHES_RCVD autolearn=ham version=3.3.1 Received: from one.firstfloor.org (HELO one.firstfloor.org) (193.170.194.197) by sourceware.org (qpsmtpd/0.84/v0.84-167-ge50287c) with ESMTP; Fri, 19 Apr 2013 21:32:11 +0000 Received: by one.firstfloor.org (Postfix, from userid 503) id CCFC686763; Fri, 19 Apr 2013 23:32:07 +0200 (CEST) From: Andi Kleen To: gcc-patches@gcc.gnu.org Cc: hubicka@ucw.cz, Andi Kleen Subject: [PATCH 2/9] Add murmurhash3 Date: Fri, 19 Apr 2013 23:31:50 +0200 Message-Id: <1366407117-18462-3-git-send-email-andi@firstfloor.org> In-Reply-To: <1366407117-18462-1-git-send-email-andi@firstfloor.org> References: <1366407117-18462-1-git-send-email-andi@firstfloor.org> From: Andi Kleen I use Austin Appleby's Public Domain Murmur3 reference code. I don't own that code. Murmur hash is available from http://code.google.com/p/smhasher/wiki/MurmurHash gcc/: 2013-04-18 Andi Kleen * murmurhash3.h: New file. --- gcc/murmurhash3.h | 80 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 80 insertions(+) create mode 100644 gcc/murmurhash3.h diff --git a/gcc/murmurhash3.h b/gcc/murmurhash3.h new file mode 100644 index 0000000..f4e838e --- /dev/null +++ b/gcc/murmurhash3.h @@ -0,0 +1,80 @@ +#include + +//----------------------------------------------------------------------------- +// MurmurHash3 was written by Austin Appleby, and is placed in the public +// domain. The author hereby disclaims copyright to this source code. +// Minor changes for gcc by AK. + +inline uint32_t rotl32(uint32_t x, int8_t r) +{ + return (x << r) | (x >> (32 - r)); +} + +//----------------------------------------------------------------------------- +// Finalization mix - force all bits of a hash block to avalanche + +inline uint32_t mm3_fmix(uint32_t h) +{ + h ^= h >> 16; + h *= 0x85ebca6b; + h ^= h >> 13; + h *= 0xc2b2ae35; + h ^= h >> 16; + + return h; +} + +static inline uint32_t murmurhash3_32(const void *key, int len, uint32_t seed) +{ + const uint8_t * data = (const uint8_t*)key; + const int nblocks = len / 4; + + uint32_t h1 = seed; + + const uint32_t c1 = 0xcc9e2d51; + const uint32_t c2 = 0x1b873593; + + //---------- + // body + + const uint32_t *blocks = (const uint32_t *)(data + nblocks*4); + + for(int i = -nblocks; i; i++) + { + uint32_t k1 = blocks[i]; + + k1 *= c1; + k1 = rotl32(k1,15); + k1 *= c2; + + h1 ^= k1; + h1 = rotl32(h1,13); + h1 = h1*5+0xe6546b64; + } + + //---------- + // tail + + const uint8_t * tail = (const uint8_t*)(data + nblocks*4); + + uint32_t k1 = 0; + + switch(len & 3) + { + case 3: + k1 ^= tail[2] << 16; + case 2: + k1 ^= tail[1] << 8; + case 1: + k1 ^= tail[0]; + k1 *= c1; k1 = rotl32(k1,15); k1 *= c2; h1 ^= k1; + }; + + //---------- + // finalization + + h1 ^= len; + + h1 = mm3_fmix(h1); + return h1; +}