1245868Sjasone/* 2245868Sjasone * The following hash function is based on MurmurHash3, placed into the public 3245868Sjasone * domain by Austin Appleby. See http://code.google.com/p/smhasher/ for 4245868Sjasone * details. 5245868Sjasone */ 6234370Sjasone/******************************************************************************/ 7234370Sjasone#ifdef JEMALLOC_H_TYPES 8234370Sjasone 9234370Sjasone#endif /* JEMALLOC_H_TYPES */ 10234370Sjasone/******************************************************************************/ 11234370Sjasone#ifdef JEMALLOC_H_STRUCTS 12234370Sjasone 13234370Sjasone#endif /* JEMALLOC_H_STRUCTS */ 14234370Sjasone/******************************************************************************/ 15234370Sjasone#ifdef JEMALLOC_H_EXTERNS 16234370Sjasone 17234370Sjasone#endif /* JEMALLOC_H_EXTERNS */ 18234370Sjasone/******************************************************************************/ 19234370Sjasone#ifdef JEMALLOC_H_INLINES 20234370Sjasone 21234370Sjasone#ifndef JEMALLOC_ENABLE_INLINE 22245868Sjasonevoid hash(const void *key, size_t len, const uint32_t seed, 23245868Sjasone size_t r_hash[2]); 24234370Sjasone#endif 25234370Sjasone 26234370Sjasone#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_HASH_C_)) 27245868Sjasone/******************************************************************************/ 28245868Sjasone/* Internal implementation. */ 29245868SjasoneJEMALLOC_INLINE uint32_t 30245868Sjasonehash_rotl_32(uint32_t x, int8_t r) 31245868Sjasone{ 32245868Sjasone 33245868Sjasone return (x << r) | (x >> (32 - r)); 34245868Sjasone} 35245868Sjasone 36234370SjasoneJEMALLOC_INLINE uint64_t 37245868Sjasonehash_rotl_64(uint64_t x, int8_t r) 38234370Sjasone{ 39245868Sjasone return (x << r) | (x >> (64 - r)); 40245868Sjasone} 41234370Sjasone 42245868SjasoneJEMALLOC_INLINE uint32_t 43245868Sjasonehash_get_block_32(const uint32_t *p, int i) 44245868Sjasone{ 45234370Sjasone 46245868Sjasone return p[i]; 47245868Sjasone} 48234370Sjasone 49245868SjasoneJEMALLOC_INLINE uint64_t 50245868Sjasonehash_get_block_64(const uint64_t *p, int i) 51245868Sjasone{ 52234370Sjasone 53245868Sjasone return p[i]; 54245868Sjasone} 55245868Sjasone 56245868SjasoneJEMALLOC_INLINE uint32_t 57245868Sjasonehash_fmix_32(uint32_t h) 58245868Sjasone{ 59245868Sjasone 60245868Sjasone h ^= h >> 16; 61245868Sjasone h *= 0x85ebca6b; 62245868Sjasone h ^= h >> 13; 63245868Sjasone h *= 0xc2b2ae35; 64245868Sjasone h ^= h >> 16; 65245868Sjasone 66245868Sjasone return h; 67245868Sjasone} 68245868Sjasone 69245868SjasoneJEMALLOC_INLINE uint64_t 70245868Sjasonehash_fmix_64(uint64_t k) 71245868Sjasone{ 72245868Sjasone 73245868Sjasone k ^= k >> 33; 74245868Sjasone k *= QU(0xff51afd7ed558ccdLLU); 75245868Sjasone k ^= k >> 33; 76245868Sjasone k *= QU(0xc4ceb9fe1a85ec53LLU); 77245868Sjasone k ^= k >> 33; 78245868Sjasone 79245868Sjasone return k; 80245868Sjasone} 81245868Sjasone 82245868SjasoneJEMALLOC_INLINE uint32_t 83245868Sjasonehash_x86_32(const void *key, int len, uint32_t seed) 84245868Sjasone{ 85245868Sjasone const uint8_t *data = (const uint8_t *) key; 86245868Sjasone const int nblocks = len / 4; 87245868Sjasone 88245868Sjasone uint32_t h1 = seed; 89245868Sjasone 90245868Sjasone const uint32_t c1 = 0xcc9e2d51; 91245868Sjasone const uint32_t c2 = 0x1b873593; 92245868Sjasone 93245868Sjasone /* body */ 94245868Sjasone { 95245868Sjasone const uint32_t *blocks = (const uint32_t *) (data + nblocks*4); 96245868Sjasone int i; 97245868Sjasone 98245868Sjasone for (i = -nblocks; i; i++) { 99245868Sjasone uint32_t k1 = hash_get_block_32(blocks, i); 100245868Sjasone 101245868Sjasone k1 *= c1; 102245868Sjasone k1 = hash_rotl_32(k1, 15); 103245868Sjasone k1 *= c2; 104245868Sjasone 105245868Sjasone h1 ^= k1; 106245868Sjasone h1 = hash_rotl_32(h1, 13); 107245868Sjasone h1 = h1*5 + 0xe6546b64; 108245868Sjasone } 109234370Sjasone } 110234370Sjasone 111245868Sjasone /* tail */ 112245868Sjasone { 113245868Sjasone const uint8_t *tail = (const uint8_t *) (data + nblocks*4); 114245868Sjasone 115245868Sjasone uint32_t k1 = 0; 116245868Sjasone 117245868Sjasone switch (len & 3) { 118245868Sjasone case 3: k1 ^= tail[2] << 16; 119245868Sjasone case 2: k1 ^= tail[1] << 8; 120245868Sjasone case 1: k1 ^= tail[0]; k1 *= c1; k1 = hash_rotl_32(k1, 15); 121245868Sjasone k1 *= c2; h1 ^= k1; 122245868Sjasone } 123234370Sjasone } 124234370Sjasone 125245868Sjasone /* finalization */ 126245868Sjasone h1 ^= len; 127234370Sjasone 128245868Sjasone h1 = hash_fmix_32(h1); 129245868Sjasone 130245868Sjasone return h1; 131234370Sjasone} 132245868Sjasone 133245868SjasoneUNUSED JEMALLOC_INLINE void 134245868Sjasonehash_x86_128(const void *key, const int len, uint32_t seed, 135245868Sjasone uint64_t r_out[2]) 136245868Sjasone{ 137245868Sjasone const uint8_t * data = (const uint8_t *) key; 138245868Sjasone const int nblocks = len / 16; 139245868Sjasone 140245868Sjasone uint32_t h1 = seed; 141245868Sjasone uint32_t h2 = seed; 142245868Sjasone uint32_t h3 = seed; 143245868Sjasone uint32_t h4 = seed; 144245868Sjasone 145245868Sjasone const uint32_t c1 = 0x239b961b; 146245868Sjasone const uint32_t c2 = 0xab0e9789; 147245868Sjasone const uint32_t c3 = 0x38b34ae5; 148245868Sjasone const uint32_t c4 = 0xa1e38b93; 149245868Sjasone 150245868Sjasone /* body */ 151245868Sjasone { 152245868Sjasone const uint32_t *blocks = (const uint32_t *) (data + nblocks*16); 153245868Sjasone int i; 154245868Sjasone 155245868Sjasone for (i = -nblocks; i; i++) { 156245868Sjasone uint32_t k1 = hash_get_block_32(blocks, i*4 + 0); 157245868Sjasone uint32_t k2 = hash_get_block_32(blocks, i*4 + 1); 158245868Sjasone uint32_t k3 = hash_get_block_32(blocks, i*4 + 2); 159245868Sjasone uint32_t k4 = hash_get_block_32(blocks, i*4 + 3); 160245868Sjasone 161245868Sjasone k1 *= c1; k1 = hash_rotl_32(k1, 15); k1 *= c2; h1 ^= k1; 162245868Sjasone 163245868Sjasone h1 = hash_rotl_32(h1, 19); h1 += h2; 164245868Sjasone h1 = h1*5 + 0x561ccd1b; 165245868Sjasone 166245868Sjasone k2 *= c2; k2 = hash_rotl_32(k2, 16); k2 *= c3; h2 ^= k2; 167245868Sjasone 168245868Sjasone h2 = hash_rotl_32(h2, 17); h2 += h3; 169245868Sjasone h2 = h2*5 + 0x0bcaa747; 170245868Sjasone 171245868Sjasone k3 *= c3; k3 = hash_rotl_32(k3, 17); k3 *= c4; h3 ^= k3; 172245868Sjasone 173245868Sjasone h3 = hash_rotl_32(h3, 15); h3 += h4; 174245868Sjasone h3 = h3*5 + 0x96cd1c35; 175245868Sjasone 176245868Sjasone k4 *= c4; k4 = hash_rotl_32(k4, 18); k4 *= c1; h4 ^= k4; 177245868Sjasone 178245868Sjasone h4 = hash_rotl_32(h4, 13); h4 += h1; 179245868Sjasone h4 = h4*5 + 0x32ac3b17; 180245868Sjasone } 181245868Sjasone } 182245868Sjasone 183245868Sjasone /* tail */ 184245868Sjasone { 185245868Sjasone const uint8_t *tail = (const uint8_t *) (data + nblocks*16); 186245868Sjasone uint32_t k1 = 0; 187245868Sjasone uint32_t k2 = 0; 188245868Sjasone uint32_t k3 = 0; 189245868Sjasone uint32_t k4 = 0; 190245868Sjasone 191245868Sjasone switch (len & 15) { 192245868Sjasone case 15: k4 ^= tail[14] << 16; 193245868Sjasone case 14: k4 ^= tail[13] << 8; 194245868Sjasone case 13: k4 ^= tail[12] << 0; 195245868Sjasone k4 *= c4; k4 = hash_rotl_32(k4, 18); k4 *= c1; h4 ^= k4; 196245868Sjasone 197245868Sjasone case 12: k3 ^= tail[11] << 24; 198245868Sjasone case 11: k3 ^= tail[10] << 16; 199245868Sjasone case 10: k3 ^= tail[ 9] << 8; 200245868Sjasone case 9: k3 ^= tail[ 8] << 0; 201245868Sjasone k3 *= c3; k3 = hash_rotl_32(k3, 17); k3 *= c4; h3 ^= k3; 202245868Sjasone 203245868Sjasone case 8: k2 ^= tail[ 7] << 24; 204245868Sjasone case 7: k2 ^= tail[ 6] << 16; 205245868Sjasone case 6: k2 ^= tail[ 5] << 8; 206245868Sjasone case 5: k2 ^= tail[ 4] << 0; 207245868Sjasone k2 *= c2; k2 = hash_rotl_32(k2, 16); k2 *= c3; h2 ^= k2; 208245868Sjasone 209245868Sjasone case 4: k1 ^= tail[ 3] << 24; 210245868Sjasone case 3: k1 ^= tail[ 2] << 16; 211245868Sjasone case 2: k1 ^= tail[ 1] << 8; 212245868Sjasone case 1: k1 ^= tail[ 0] << 0; 213245868Sjasone k1 *= c1; k1 = hash_rotl_32(k1, 15); k1 *= c2; h1 ^= k1; 214245868Sjasone } 215245868Sjasone } 216245868Sjasone 217245868Sjasone /* finalization */ 218245868Sjasone h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len; 219245868Sjasone 220245868Sjasone h1 += h2; h1 += h3; h1 += h4; 221245868Sjasone h2 += h1; h3 += h1; h4 += h1; 222245868Sjasone 223245868Sjasone h1 = hash_fmix_32(h1); 224245868Sjasone h2 = hash_fmix_32(h2); 225245868Sjasone h3 = hash_fmix_32(h3); 226245868Sjasone h4 = hash_fmix_32(h4); 227245868Sjasone 228245868Sjasone h1 += h2; h1 += h3; h1 += h4; 229245868Sjasone h2 += h1; h3 += h1; h4 += h1; 230245868Sjasone 231245868Sjasone r_out[0] = (((uint64_t) h2) << 32) | h1; 232245868Sjasone r_out[1] = (((uint64_t) h4) << 32) | h3; 233245868Sjasone} 234245868Sjasone 235245868SjasoneUNUSED JEMALLOC_INLINE void 236245868Sjasonehash_x64_128(const void *key, const int len, const uint32_t seed, 237245868Sjasone uint64_t r_out[2]) 238245868Sjasone{ 239245868Sjasone const uint8_t *data = (const uint8_t *) key; 240245868Sjasone const int nblocks = len / 16; 241245868Sjasone 242245868Sjasone uint64_t h1 = seed; 243245868Sjasone uint64_t h2 = seed; 244245868Sjasone 245245868Sjasone const uint64_t c1 = QU(0x87c37b91114253d5LLU); 246245868Sjasone const uint64_t c2 = QU(0x4cf5ad432745937fLLU); 247245868Sjasone 248245868Sjasone /* body */ 249245868Sjasone { 250245868Sjasone const uint64_t *blocks = (const uint64_t *) (data); 251245868Sjasone int i; 252245868Sjasone 253245868Sjasone for (i = 0; i < nblocks; i++) { 254245868Sjasone uint64_t k1 = hash_get_block_64(blocks, i*2 + 0); 255245868Sjasone uint64_t k2 = hash_get_block_64(blocks, i*2 + 1); 256245868Sjasone 257245868Sjasone k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1; 258245868Sjasone 259245868Sjasone h1 = hash_rotl_64(h1, 27); h1 += h2; 260245868Sjasone h1 = h1*5 + 0x52dce729; 261245868Sjasone 262245868Sjasone k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2; 263245868Sjasone 264245868Sjasone h2 = hash_rotl_64(h2, 31); h2 += h1; 265245868Sjasone h2 = h2*5 + 0x38495ab5; 266245868Sjasone } 267245868Sjasone } 268245868Sjasone 269245868Sjasone /* tail */ 270245868Sjasone { 271245868Sjasone const uint8_t *tail = (const uint8_t*)(data + nblocks*16); 272245868Sjasone uint64_t k1 = 0; 273245868Sjasone uint64_t k2 = 0; 274245868Sjasone 275245868Sjasone switch (len & 15) { 276245868Sjasone case 15: k2 ^= ((uint64_t)(tail[14])) << 48; 277245868Sjasone case 14: k2 ^= ((uint64_t)(tail[13])) << 40; 278245868Sjasone case 13: k2 ^= ((uint64_t)(tail[12])) << 32; 279245868Sjasone case 12: k2 ^= ((uint64_t)(tail[11])) << 24; 280245868Sjasone case 11: k2 ^= ((uint64_t)(tail[10])) << 16; 281245868Sjasone case 10: k2 ^= ((uint64_t)(tail[ 9])) << 8; 282245868Sjasone case 9: k2 ^= ((uint64_t)(tail[ 8])) << 0; 283245868Sjasone k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2; 284245868Sjasone 285245868Sjasone case 8: k1 ^= ((uint64_t)(tail[ 7])) << 56; 286245868Sjasone case 7: k1 ^= ((uint64_t)(tail[ 6])) << 48; 287245868Sjasone case 6: k1 ^= ((uint64_t)(tail[ 5])) << 40; 288245868Sjasone case 5: k1 ^= ((uint64_t)(tail[ 4])) << 32; 289245868Sjasone case 4: k1 ^= ((uint64_t)(tail[ 3])) << 24; 290245868Sjasone case 3: k1 ^= ((uint64_t)(tail[ 2])) << 16; 291245868Sjasone case 2: k1 ^= ((uint64_t)(tail[ 1])) << 8; 292245868Sjasone case 1: k1 ^= ((uint64_t)(tail[ 0])) << 0; 293245868Sjasone k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1; 294245868Sjasone } 295245868Sjasone } 296245868Sjasone 297245868Sjasone /* finalization */ 298245868Sjasone h1 ^= len; h2 ^= len; 299245868Sjasone 300245868Sjasone h1 += h2; 301245868Sjasone h2 += h1; 302245868Sjasone 303245868Sjasone h1 = hash_fmix_64(h1); 304245868Sjasone h2 = hash_fmix_64(h2); 305245868Sjasone 306245868Sjasone h1 += h2; 307245868Sjasone h2 += h1; 308245868Sjasone 309245868Sjasone r_out[0] = h1; 310245868Sjasone r_out[1] = h2; 311245868Sjasone} 312245868Sjasone 313245868Sjasone 314245868Sjasone/******************************************************************************/ 315245868Sjasone/* API. */ 316245868SjasoneJEMALLOC_INLINE void 317245868Sjasonehash(const void *key, size_t len, const uint32_t seed, size_t r_hash[2]) 318245868Sjasone{ 319245868Sjasone#if (LG_SIZEOF_PTR == 3) 320245868Sjasone hash_x64_128(key, len, seed, (uint64_t *)r_hash); 321245868Sjasone#else 322245868Sjasone uint64_t hashes[2]; 323245868Sjasone hash_x86_128(key, len, seed, hashes); 324245868Sjasone r_hash[0] = (size_t)hashes[0]; 325245868Sjasone r_hash[1] = (size_t)hashes[1]; 326234370Sjasone#endif 327245868Sjasone} 328245868Sjasone#endif 329234370Sjasone 330234370Sjasone#endif /* JEMALLOC_H_INLINES */ 331234370Sjasone/******************************************************************************/ 332