1ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans/* 2ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans * The following hash function is based on MurmurHash3, placed into the public 3ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans * domain by Austin Appleby. See http://code.google.com/p/smhasher/ for 4ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans * details. 5ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans */ 66109fe07a14b7a619365977d9523db9f8b333792Jason Evans/******************************************************************************/ 76109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef JEMALLOC_H_TYPES 86109fe07a14b7a619365977d9523db9f8b333792Jason Evans 96109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif /* JEMALLOC_H_TYPES */ 106109fe07a14b7a619365977d9523db9f8b333792Jason Evans/******************************************************************************/ 116109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef JEMALLOC_H_STRUCTS 126109fe07a14b7a619365977d9523db9f8b333792Jason Evans 136109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif /* JEMALLOC_H_STRUCTS */ 146109fe07a14b7a619365977d9523db9f8b333792Jason Evans/******************************************************************************/ 156109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef JEMALLOC_H_EXTERNS 166109fe07a14b7a619365977d9523db9f8b333792Jason Evans 176109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif /* JEMALLOC_H_EXTERNS */ 186109fe07a14b7a619365977d9523db9f8b333792Jason Evans/******************************************************************************/ 196109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef JEMALLOC_H_INLINES 206109fe07a14b7a619365977d9523db9f8b333792Jason Evans 216109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifndef JEMALLOC_ENABLE_INLINE 221b75b4e6d11814f470e797be4a610a2e3ae323d5Jason Evansuint32_t hash_x86_32(const void *key, int len, uint32_t seed); 231b75b4e6d11814f470e797be4a610a2e3ae323d5Jason Evansvoid hash_x86_128(const void *key, const int len, uint32_t seed, 241b75b4e6d11814f470e797be4a610a2e3ae323d5Jason Evans uint64_t r_out[2]); 251b75b4e6d11814f470e797be4a610a2e3ae323d5Jason Evansvoid hash_x64_128(const void *key, const int len, const uint32_t seed, 261b75b4e6d11814f470e797be4a610a2e3ae323d5Jason Evans uint64_t r_out[2]); 27ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evansvoid hash(const void *key, size_t len, const uint32_t seed, 28ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans size_t r_hash[2]); 296109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 306109fe07a14b7a619365977d9523db9f8b333792Jason Evans 310657f12acd43eb2082a71230341449eca648bc9bJason Evans#if (defined(JEMALLOC_ENABLE_INLINE) || defined(JEMALLOC_HASH_C_)) 32ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans/******************************************************************************/ 33ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans/* Internal implementation. */ 34ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE uint32_t 35ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_rotl_32(uint32_t x, int8_t r) 36ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 37ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 38ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans return (x << r) | (x >> (32 - r)); 39ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 40ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 41ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE uint64_t 42ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_rotl_64(uint64_t x, int8_t r) 43ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 44ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans return (x << r) | (x >> (64 - r)); 45ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 46ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 47ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE uint32_t 48ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_get_block_32(const uint32_t *p, int i) 49ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 50ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 510f4f1efd94d33a4bbf766d3d4e7e349fa7c0d3b9Jason Evans return (p[i]); 52ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 53ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 546109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE uint64_t 55ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_get_block_64(const uint64_t *p, int i) 566109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 57b27805b36309681da1936eb33044584547552340Jason Evans 580f4f1efd94d33a4bbf766d3d4e7e349fa7c0d3b9Jason Evans return (p[i]); 59ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 60ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 61ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE uint32_t 62ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_fmix_32(uint32_t h) 63ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 646109fe07a14b7a619365977d9523db9f8b333792Jason Evans 65ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h ^= h >> 16; 66ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h *= 0x85ebca6b; 67ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h ^= h >> 13; 68ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h *= 0xc2b2ae35; 69ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h ^= h >> 16; 706109fe07a14b7a619365977d9523db9f8b333792Jason Evans 710f4f1efd94d33a4bbf766d3d4e7e349fa7c0d3b9Jason Evans return (h); 72ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 736109fe07a14b7a619365977d9523db9f8b333792Jason Evans 74ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE uint64_t 75ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_fmix_64(uint64_t k) 76ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 77ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 78ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k ^= k >> 33; 79da74e77beefbc6ea0f9d7dbf663bc5df48fbd887Jason Evans k *= KQU(0xff51afd7ed558ccd); 80ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k ^= k >> 33; 81da74e77beefbc6ea0f9d7dbf663bc5df48fbd887Jason Evans k *= KQU(0xc4ceb9fe1a85ec53); 82ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k ^= k >> 33; 83ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 840f4f1efd94d33a4bbf766d3d4e7e349fa7c0d3b9Jason Evans return (k); 85ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 86ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 87ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE uint32_t 88ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_x86_32(const void *key, int len, uint32_t seed) 89ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 90ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t *data = (const uint8_t *) key; 91ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const int nblocks = len / 4; 92ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 93ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t h1 = seed; 94ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 95ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c1 = 0xcc9e2d51; 96ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c2 = 0x1b873593; 97ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 98ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* body */ 99ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 100ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t *blocks = (const uint32_t *) (data + nblocks*4); 101ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans int i; 102ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 103ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans for (i = -nblocks; i; i++) { 104ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k1 = hash_get_block_32(blocks, i); 105ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 106ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c1; 107ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 = hash_rotl_32(k1, 15); 108ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c2; 109ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 110ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 ^= k1; 111ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_rotl_32(h1, 13); 112ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = h1*5 + 0xe6546b64; 113ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 1146109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1156109fe07a14b7a619365977d9523db9f8b333792Jason Evans 116ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* tail */ 117ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 118ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t *tail = (const uint8_t *) (data + nblocks*4); 119ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 120ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k1 = 0; 121ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 122ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans switch (len & 3) { 123ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 3: k1 ^= tail[2] << 16; 124ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 2: k1 ^= tail[1] << 8; 125ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 1: k1 ^= tail[0]; k1 *= c1; k1 = hash_rotl_32(k1, 15); 126ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c2; h1 ^= k1; 127ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 1286109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1296109fe07a14b7a619365977d9523db9f8b333792Jason Evans 130ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* finalization */ 131ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 ^= len; 132ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 133ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_fmix_32(h1); 134ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 1350f4f1efd94d33a4bbf766d3d4e7e349fa7c0d3b9Jason Evans return (h1); 136ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 137ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 138ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansUNUSED JEMALLOC_INLINE void 139ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_x86_128(const void *key, const int len, uint32_t seed, 1401b75b4e6d11814f470e797be4a610a2e3ae323d5Jason Evans uint64_t r_out[2]) 141ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 142ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t * data = (const uint8_t *) key; 143ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const int nblocks = len / 16; 144ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 145ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t h1 = seed; 146ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t h2 = seed; 147ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t h3 = seed; 148ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t h4 = seed; 149ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 150ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c1 = 0x239b961b; 151ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c2 = 0xab0e9789; 152ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c3 = 0x38b34ae5; 153ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c4 = 0xa1e38b93; 154ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 155ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* body */ 156ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 157ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t *blocks = (const uint32_t *) (data + nblocks*16); 158ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans int i; 159ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 160ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans for (i = -nblocks; i; i++) { 161ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k1 = hash_get_block_32(blocks, i*4 + 0); 162ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k2 = hash_get_block_32(blocks, i*4 + 1); 163ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k3 = hash_get_block_32(blocks, i*4 + 2); 164ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k4 = hash_get_block_32(blocks, i*4 + 3); 1656109fe07a14b7a619365977d9523db9f8b333792Jason Evans 166ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c1; k1 = hash_rotl_32(k1, 15); k1 *= c2; h1 ^= k1; 167ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 168ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_rotl_32(h1, 19); h1 += h2; 169ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = h1*5 + 0x561ccd1b; 170ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 171ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k2 *= c2; k2 = hash_rotl_32(k2, 16); k2 *= c3; h2 ^= k2; 172ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 173ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = hash_rotl_32(h2, 17); h2 += h3; 174ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = h2*5 + 0x0bcaa747; 175ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 176ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k3 *= c3; k3 = hash_rotl_32(k3, 17); k3 *= c4; h3 ^= k3; 177ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 178ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h3 = hash_rotl_32(h3, 15); h3 += h4; 179ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h3 = h3*5 + 0x96cd1c35; 180ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 181ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k4 *= c4; k4 = hash_rotl_32(k4, 18); k4 *= c1; h4 ^= k4; 182ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 183ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h4 = hash_rotl_32(h4, 13); h4 += h1; 184ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h4 = h4*5 + 0x32ac3b17; 185ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 186ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 187ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 188ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* tail */ 189ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 190ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t *tail = (const uint8_t *) (data + nblocks*16); 191ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k1 = 0; 192ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k2 = 0; 193ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k3 = 0; 194ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k4 = 0; 195ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 196ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans switch (len & 15) { 197ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 15: k4 ^= tail[14] << 16; 198ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 14: k4 ^= tail[13] << 8; 199ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 13: k4 ^= tail[12] << 0; 200ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k4 *= c4; k4 = hash_rotl_32(k4, 18); k4 *= c1; h4 ^= k4; 201ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 202ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 12: k3 ^= tail[11] << 24; 203ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 11: k3 ^= tail[10] << 16; 204ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 10: k3 ^= tail[ 9] << 8; 205ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 9: k3 ^= tail[ 8] << 0; 206ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k3 *= c3; k3 = hash_rotl_32(k3, 17); k3 *= c4; h3 ^= k3; 207ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 208ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 8: k2 ^= tail[ 7] << 24; 209ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 7: k2 ^= tail[ 6] << 16; 210ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 6: k2 ^= tail[ 5] << 8; 211ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 5: k2 ^= tail[ 4] << 0; 212ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k2 *= c2; k2 = hash_rotl_32(k2, 16); k2 *= c3; h2 ^= k2; 213ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 214ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 4: k1 ^= tail[ 3] << 24; 215ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 3: k1 ^= tail[ 2] << 16; 216ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 2: k1 ^= tail[ 1] << 8; 217ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 1: k1 ^= tail[ 0] << 0; 218ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c1; k1 = hash_rotl_32(k1, 15); k1 *= c2; h1 ^= k1; 219ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 220ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 221ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 222ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* finalization */ 223ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len; 224ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 225ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 += h2; h1 += h3; h1 += h4; 226ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 += h1; h3 += h1; h4 += h1; 227ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 228ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_fmix_32(h1); 229ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = hash_fmix_32(h2); 230ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h3 = hash_fmix_32(h3); 231ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h4 = hash_fmix_32(h4); 232ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 233ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 += h2; h1 += h3; h1 += h4; 234ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 += h1; h3 += h1; h4 += h1; 235ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 236ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans r_out[0] = (((uint64_t) h2) << 32) | h1; 237ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans r_out[1] = (((uint64_t) h4) << 32) | h3; 238ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 239ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 240ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansUNUSED JEMALLOC_INLINE void 241ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_x64_128(const void *key, const int len, const uint32_t seed, 2421b75b4e6d11814f470e797be4a610a2e3ae323d5Jason Evans uint64_t r_out[2]) 243ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 244ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t *data = (const uint8_t *) key; 245ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const int nblocks = len / 16; 246ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 247ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t h1 = seed; 248ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t h2 = seed; 249ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 250da74e77beefbc6ea0f9d7dbf663bc5df48fbd887Jason Evans const uint64_t c1 = KQU(0x87c37b91114253d5); 251da74e77beefbc6ea0f9d7dbf663bc5df48fbd887Jason Evans const uint64_t c2 = KQU(0x4cf5ad432745937f); 252ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 253ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* body */ 254ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 255ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint64_t *blocks = (const uint64_t *) (data); 256ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans int i; 257ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 258ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans for (i = 0; i < nblocks; i++) { 259ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t k1 = hash_get_block_64(blocks, i*2 + 0); 260ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t k2 = hash_get_block_64(blocks, i*2 + 1); 261ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 262ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1; 263ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 264ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_rotl_64(h1, 27); h1 += h2; 265ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = h1*5 + 0x52dce729; 266ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 267ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2; 268ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 269ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = hash_rotl_64(h2, 31); h2 += h1; 270ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = h2*5 + 0x38495ab5; 271ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 272ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 273ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 274ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* tail */ 275ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 276ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t *tail = (const uint8_t*)(data + nblocks*16); 277ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t k1 = 0; 278ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t k2 = 0; 279ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 280ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans switch (len & 15) { 281ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 15: k2 ^= ((uint64_t)(tail[14])) << 48; 282ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 14: k2 ^= ((uint64_t)(tail[13])) << 40; 283ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 13: k2 ^= ((uint64_t)(tail[12])) << 32; 284ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 12: k2 ^= ((uint64_t)(tail[11])) << 24; 285ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 11: k2 ^= ((uint64_t)(tail[10])) << 16; 286ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 10: k2 ^= ((uint64_t)(tail[ 9])) << 8; 287ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 9: k2 ^= ((uint64_t)(tail[ 8])) << 0; 288ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2; 289ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 290ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 8: k1 ^= ((uint64_t)(tail[ 7])) << 56; 291ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 7: k1 ^= ((uint64_t)(tail[ 6])) << 48; 292ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 6: k1 ^= ((uint64_t)(tail[ 5])) << 40; 293ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 5: k1 ^= ((uint64_t)(tail[ 4])) << 32; 294ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 4: k1 ^= ((uint64_t)(tail[ 3])) << 24; 295ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 3: k1 ^= ((uint64_t)(tail[ 2])) << 16; 296ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 2: k1 ^= ((uint64_t)(tail[ 1])) << 8; 297ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 1: k1 ^= ((uint64_t)(tail[ 0])) << 0; 298ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1; 299ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 300ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 301ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 302ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* finalization */ 303ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 ^= len; h2 ^= len; 304ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 305ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 += h2; 306ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 += h1; 307ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 308ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_fmix_64(h1); 309ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = hash_fmix_64(h2); 310ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 311ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 += h2; 312ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 += h1; 313ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 314ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans r_out[0] = h1; 315ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans r_out[1] = h2; 316ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 317ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 318ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans/******************************************************************************/ 319ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans/* API. */ 320ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE void 321ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash(const void *key, size_t len, const uint32_t seed, size_t r_hash[2]) 322ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 323df3f27024f193b7baeedcd9f3799b4774dd20bbfJason Evans#if (LG_SIZEOF_PTR == 3 && !defined(JEMALLOC_BIG_ENDIAN)) 324ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans hash_x64_128(key, len, seed, (uint64_t *)r_hash); 325ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans#else 326ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t hashes[2]; 327ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans hash_x86_128(key, len, seed, hashes); 328ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans r_hash[0] = (size_t)hashes[0]; 329ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans r_hash[1] = (size_t)hashes[1]; 330ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans#endif 3316109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 3326109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 3336109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3346109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif /* JEMALLOC_H_INLINES */ 3356109fe07a14b7a619365977d9523db9f8b333792Jason Evans/******************************************************************************/ 336