ck_ht_hash.h revision 332391
1309260Scognet/* 2309260Scognet * Copyright 2012-2015 Samy Al Bahra 3309260Scognet * Copyright 2011-2014 AppNexus, Inc. 4309260Scognet * 5309260Scognet * Redistribution and use in source and binary forms, with or without 6309260Scognet * modification, are permitted provided that the following conditions 7309260Scognet * are met: 8309260Scognet * 1. Redistributions of source code must retain the above copyright 9309260Scognet * notice, this list of conditions and the following disclaimer. 10309260Scognet * 2. Redistributions in binary form must reproduce the above copyright 11309260Scognet * notice, this list of conditions and the following disclaimer in the 12309260Scognet * documentation and/or other materials provided with the distribution. 13309260Scognet * 14309260Scognet * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15309260Scognet * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16309260Scognet * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17309260Scognet * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18309260Scognet * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19309260Scognet * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20309260Scognet * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21309260Scognet * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22309260Scognet * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23309260Scognet * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24309260Scognet * SUCH DAMAGE. 25309260Scognet */ 26309260Scognet 27309260Scognet#ifndef CK_HT_HASH_H 28309260Scognet#define CK_HT_HASH_H 29309260Scognet 30309260Scognet/* 31309260Scognet * This is the Murmur hash written by Austin Appleby. 32309260Scognet */ 33309260Scognet 34309260Scognet#include <ck_stdint.h> 35309260Scognet#include <ck_string.h> 36309260Scognet 37309260Scognet//----------------------------------------------------------------------------- 38309260Scognet// MurmurHash3 was written by Austin Appleby, and is placed in the public 39309260Scognet// domain. The author hereby disclaims copyright to this source code. 40309260Scognet 41309260Scognet// Note - The x86 and x64 versions do _not_ produce the same results, as the 42309260Scognet// algorithms are optimized for their respective platforms. You can still 43309260Scognet// compile and run any of them on any platform, but your performance with the 44309260Scognet// non-native version will be less than optimal. 45309260Scognet 46309260Scognet//----------------------------------------------------------------------------- 47309260Scognet// Platform-specific functions and macros 48309260Scognet 49309260Scognet// Microsoft Visual Studio 50309260Scognet 51309260Scognet#if defined(_MSC_VER) 52309260Scognet 53309260Scognet#define FORCE_INLINE __forceinline 54309260Scognet 55309260Scognet#include <stdlib.h> 56309260Scognet 57309260Scognet#define ROTL32(x,y) _rotl(x,y) 58309260Scognet#define ROTL64(x,y) _rotl64(x,y) 59309260Scognet 60309260Scognet#define BIG_CONSTANT(x) (x) 61309260Scognet 62309260Scognet// Other compilers 63309260Scognet 64309260Scognet#else // defined(_MSC_VER) 65309260Scognet 66309260Scognet#define FORCE_INLINE inline __attribute__((always_inline)) 67309260Scognet 68309260Scognetstatic inline uint32_t rotl32 ( uint32_t x, int8_t r ) 69309260Scognet{ 70309260Scognet return (x << r) | (x >> (32 - r)); 71309260Scognet} 72309260Scognet 73309260Scognetstatic inline uint64_t rotl64 ( uint64_t x, int8_t r ) 74309260Scognet{ 75309260Scognet return (x << r) | (x >> (64 - r)); 76309260Scognet} 77309260Scognet 78309260Scognet#define ROTL32(x,y) rotl32(x,y) 79309260Scognet#define ROTL64(x,y) rotl64(x,y) 80309260Scognet 81309260Scognet#define BIG_CONSTANT(x) (x##LLU) 82309260Scognet 83309260Scognet#endif // !defined(_MSC_VER) 84309260Scognet 85309260Scognet//----------------------------------------------------------------------------- 86309260Scognet// Block read - if your platform needs to do endian-swapping or can only 87309260Scognet// handle aligned reads, do the conversion here 88309260Scognet 89309260ScognetFORCE_INLINE static uint32_t getblock ( const uint32_t * p, int i ) 90309260Scognet{ 91332391Scognet#ifdef __s390x__ 92332391Scognet uint32_t res; 93332391Scognet 94332391Scognet __asm__ (" lrv %0,%1\n" 95332391Scognet : "=r" (res) : "Q" (p[i]) : "cc", "mem"); 96332391Scognet return res; 97332391Scognet#else 98309260Scognet return p[i]; 99332391Scognet#endif /* !__s390x__ */ 100309260Scognet} 101309260Scognet 102309260Scognet//----------------------------------------------------------------------------- 103309260Scognet// Finalization mix - force all bits of a hash block to avalanche 104309260Scognet 105309260ScognetFORCE_INLINE static uint32_t fmix ( uint32_t h ) 106309260Scognet{ 107309260Scognet h ^= h >> 16; 108309260Scognet h *= 0x85ebca6b; 109309260Scognet h ^= h >> 13; 110309260Scognet h *= 0xc2b2ae35; 111309260Scognet h ^= h >> 16; 112309260Scognet 113309260Scognet return h; 114309260Scognet} 115309260Scognet 116309260Scognet//----------------------------------------------------------------------------- 117309260Scognet 118309260Scognetstatic inline void MurmurHash3_x86_32 ( const void * key, int len, 119309260Scognet uint32_t seed, uint32_t * out ) 120309260Scognet{ 121309260Scognet const uint8_t * data = (const uint8_t*)key; 122309260Scognet const int nblocks = len / 4; 123309260Scognet int i; 124309260Scognet 125309260Scognet uint32_t h1 = seed; 126309260Scognet 127309260Scognet uint32_t c1 = 0xcc9e2d51; 128309260Scognet uint32_t c2 = 0x1b873593; 129309260Scognet 130309260Scognet //---------- 131309260Scognet // body 132309260Scognet 133309260Scognet const uint32_t * blocks = (const uint32_t *)(const void *)(data + nblocks*4); 134309260Scognet 135309260Scognet for(i = -nblocks; i; i++) 136309260Scognet { 137309260Scognet uint32_t k1 = getblock(blocks,i); 138309260Scognet 139309260Scognet k1 *= c1; 140309260Scognet k1 = ROTL32(k1,15); 141309260Scognet k1 *= c2; 142309260Scognet 143309260Scognet h1 ^= k1; 144309260Scognet h1 = ROTL32(h1,13); 145309260Scognet h1 = h1*5+0xe6546b64; 146309260Scognet } 147309260Scognet 148309260Scognet //---------- 149309260Scognet // tail 150309260Scognet 151309260Scognet const uint8_t * tail = (const uint8_t*)(data + nblocks*4); 152309260Scognet 153309260Scognet uint32_t k1 = 0; 154309260Scognet 155309260Scognet switch(len & 3) 156309260Scognet { 157309260Scognet case 3: k1 ^= tail[2] << 16; 158332391Scognet /* fall through */ 159309260Scognet case 2: k1 ^= tail[1] << 8; 160332391Scognet /* fall through */ 161309260Scognet case 1: k1 ^= tail[0]; 162309260Scognet k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; 163309260Scognet }; 164309260Scognet 165309260Scognet //---------- 166309260Scognet // finalization 167309260Scognet 168309260Scognet h1 ^= len; 169309260Scognet 170309260Scognet h1 = fmix(h1); 171309260Scognet 172309260Scognet *(uint32_t *)out = h1; 173309260Scognet} 174309260Scognet 175309260Scognetstatic inline uint64_t MurmurHash64A ( const void * key, int len, uint64_t seed ) 176309260Scognet{ 177309260Scognet const uint64_t m = BIG_CONSTANT(0xc6a4a7935bd1e995); 178309260Scognet const int r = 47; 179309260Scognet 180309260Scognet uint64_t h = seed ^ (len * m); 181309260Scognet 182309260Scognet const uint64_t * data = (const uint64_t *)key; 183309260Scognet const uint64_t * end = data + (len/8); 184309260Scognet 185309260Scognet while(data != end) 186309260Scognet { 187309260Scognet uint64_t k; 188309260Scognet 189309260Scognet if (!((uintptr_t)data & 0x7)) 190309260Scognet k = *data++; 191309260Scognet else { 192309260Scognet memcpy(&k, data, sizeof(k)); 193309260Scognet data++; 194309260Scognet } 195309260Scognet 196309260Scognet k *= m; 197309260Scognet k ^= k >> r; 198309260Scognet k *= m; 199309260Scognet 200309260Scognet h ^= k; 201309260Scognet h *= m; 202309260Scognet } 203309260Scognet 204309260Scognet const unsigned char * data2 = (const unsigned char*)data; 205309260Scognet 206309260Scognet switch(len & 7) 207309260Scognet { 208309260Scognet case 7: h ^= (uint64_t)(data2[6]) << 48; 209332391Scognet /* fall through */ 210309260Scognet case 6: h ^= (uint64_t)(data2[5]) << 40; 211332391Scognet /* fall through */ 212309260Scognet case 5: h ^= (uint64_t)(data2[4]) << 32; 213332391Scognet /* fall through */ 214309260Scognet case 4: h ^= (uint64_t)(data2[3]) << 24; 215332391Scognet /* fall through */ 216309260Scognet case 3: h ^= (uint64_t)(data2[2]) << 16; 217332391Scognet /* fall through */ 218309260Scognet case 2: h ^= (uint64_t)(data2[1]) << 8; 219332391Scognet /* fall through */ 220309260Scognet case 1: h ^= (uint64_t)(data2[0]); 221309260Scognet h *= m; 222309260Scognet }; 223309260Scognet 224309260Scognet h ^= h >> r; 225309260Scognet h *= m; 226309260Scognet h ^= h >> r; 227309260Scognet 228309260Scognet return h; 229309260Scognet} 230309260Scognet 231309260Scognet 232309260Scognet// 64-bit hash for 32-bit platforms 233309260Scognet 234309260Scognetstatic inline uint64_t MurmurHash64B ( const void * key, int len, uint64_t seed ) 235309260Scognet{ 236309260Scognet const uint32_t m = 0x5bd1e995; 237309260Scognet const int r = 24; 238309260Scognet 239309260Scognet uint32_t h1 = (uint32_t)(seed) ^ len; 240309260Scognet uint32_t h2 = (uint32_t)(seed >> 32); 241309260Scognet 242309260Scognet const uint32_t * data = (const uint32_t *)key; 243309260Scognet 244309260Scognet while(len >= 8) 245309260Scognet { 246309260Scognet uint32_t k1 = *data++; 247309260Scognet k1 *= m; k1 ^= k1 >> r; k1 *= m; 248309260Scognet h1 *= m; h1 ^= k1; 249309260Scognet len -= 4; 250309260Scognet 251309260Scognet uint32_t k2 = *data++; 252309260Scognet k2 *= m; k2 ^= k2 >> r; k2 *= m; 253309260Scognet h2 *= m; h2 ^= k2; 254309260Scognet len -= 4; 255309260Scognet } 256309260Scognet 257309260Scognet if(len >= 4) 258309260Scognet { 259309260Scognet uint32_t k1 = *data++; 260309260Scognet k1 *= m; k1 ^= k1 >> r; k1 *= m; 261309260Scognet h1 *= m; h1 ^= k1; 262309260Scognet len -= 4; 263309260Scognet } 264309260Scognet 265309260Scognet switch(len) 266309260Scognet { 267309260Scognet case 3: h2 ^= ((const unsigned char*)data)[2] << 16; 268332391Scognet /* fall through */ 269309260Scognet case 2: h2 ^= ((const unsigned char*)data)[1] << 8; 270332391Scognet /* fall through */ 271309260Scognet case 1: h2 ^= ((const unsigned char*)data)[0]; 272309260Scognet h2 *= m; 273309260Scognet }; 274309260Scognet 275309260Scognet h1 ^= h2 >> 18; h1 *= m; 276309260Scognet h2 ^= h1 >> 22; h2 *= m; 277309260Scognet h1 ^= h2 >> 17; h1 *= m; 278309260Scognet h2 ^= h1 >> 19; h2 *= m; 279309260Scognet 280309260Scognet uint64_t h = h1; 281309260Scognet 282309260Scognet h = (h << 32) | h2; 283309260Scognet 284309260Scognet return h; 285309260Scognet} 286309260Scognet 287309260Scognet#endif /* CK_HT_HASH_H */ 288