1ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans/* 2ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans * The following hash function is based on MurmurHash3, placed into the public 3a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans * domain by Austin Appleby. See https://github.com/aappleby/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 38e12eaf93dca308a426c182956197b0eeb5f2cff3Jason 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{ 44e12eaf93dca308a426c182956197b0eeb5f2cff3Jason Evans 45e12eaf93dca308a426c182956197b0eeb5f2cff3Jason Evans return ((x << r) | (x >> (64 - r))); 46ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 47ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 48ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE uint32_t 49ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_get_block_32(const uint32_t *p, int i) 50ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 51ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 52a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans /* Handle unaligned read. */ 53a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans if (unlikely((uintptr_t)p & (sizeof(uint32_t)-1)) != 0) { 54a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans uint32_t ret; 55a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans 56b40253a93ec4eb79c536403491f326bb56f72c02Rajeev Misra memcpy(&ret, (uint8_t *)(p + i), sizeof(uint32_t)); 57a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans return (ret); 58a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans } 59a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans 600f4f1efd94d33a4bbf766d3d4e7e349fa7c0d3b9Jason Evans return (p[i]); 61ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 62ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 636109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE uint64_t 64ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_get_block_64(const uint64_t *p, int i) 656109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 66b27805b36309681da1936eb33044584547552340Jason Evans 67a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans /* Handle unaligned read. */ 68a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans if (unlikely((uintptr_t)p & (sizeof(uint64_t)-1)) != 0) { 69a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans uint64_t ret; 70a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans 71b40253a93ec4eb79c536403491f326bb56f72c02Rajeev Misra memcpy(&ret, (uint8_t *)(p + i), sizeof(uint64_t)); 72a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans return (ret); 73a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans } 74a0aaad1afa8c1c4b30bf15c6b8744084ffc32055Jason Evans 750f4f1efd94d33a4bbf766d3d4e7e349fa7c0d3b9Jason Evans return (p[i]); 76ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 77ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 78ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE uint32_t 79ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_fmix_32(uint32_t h) 80ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 816109fe07a14b7a619365977d9523db9f8b333792Jason Evans 82ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h ^= h >> 16; 83ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h *= 0x85ebca6b; 84ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h ^= h >> 13; 85ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h *= 0xc2b2ae35; 86ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h ^= h >> 16; 876109fe07a14b7a619365977d9523db9f8b333792Jason Evans 880f4f1efd94d33a4bbf766d3d4e7e349fa7c0d3b9Jason Evans return (h); 89ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 906109fe07a14b7a619365977d9523db9f8b333792Jason Evans 91ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE uint64_t 92ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_fmix_64(uint64_t k) 93ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 94ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 95ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k ^= k >> 33; 961f6d77e1f687c3c4fa4ae6768b689a7936923f07Jason Evans k *= KQU(0xff51afd7ed558ccd); 97ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k ^= k >> 33; 981f6d77e1f687c3c4fa4ae6768b689a7936923f07Jason Evans k *= KQU(0xc4ceb9fe1a85ec53); 99ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k ^= k >> 33; 100ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 1010f4f1efd94d33a4bbf766d3d4e7e349fa7c0d3b9Jason Evans return (k); 102ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 103ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 104ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE uint32_t 105ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_x86_32(const void *key, int len, uint32_t seed) 106ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 107ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t *data = (const uint8_t *) key; 108ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const int nblocks = len / 4; 109ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 110ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t h1 = seed; 111ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 112ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c1 = 0xcc9e2d51; 113ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c2 = 0x1b873593; 114ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 115ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* body */ 116ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 117ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t *blocks = (const uint32_t *) (data + nblocks*4); 118ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans int i; 119ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 120ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans for (i = -nblocks; i; i++) { 121ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k1 = hash_get_block_32(blocks, i); 122ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 123ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c1; 124ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 = hash_rotl_32(k1, 15); 125ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c2; 126ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 127ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 ^= k1; 128ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_rotl_32(h1, 13); 129ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = h1*5 + 0xe6546b64; 130ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 1316109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1326109fe07a14b7a619365977d9523db9f8b333792Jason Evans 133ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* tail */ 134ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 135ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t *tail = (const uint8_t *) (data + nblocks*4); 136ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 137ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k1 = 0; 138ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 139ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans switch (len & 3) { 140ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 3: k1 ^= tail[2] << 16; 141ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 2: k1 ^= tail[1] << 8; 142ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 1: k1 ^= tail[0]; k1 *= c1; k1 = hash_rotl_32(k1, 15); 143ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c2; h1 ^= k1; 144ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 1456109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1466109fe07a14b7a619365977d9523db9f8b333792Jason Evans 147ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* finalization */ 148ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 ^= len; 149ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 150ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_fmix_32(h1); 151ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 1520f4f1efd94d33a4bbf766d3d4e7e349fa7c0d3b9Jason Evans return (h1); 153ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 154ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 155ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansUNUSED JEMALLOC_INLINE void 156ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_x86_128(const void *key, const int len, uint32_t seed, 1571b75b4e6d11814f470e797be4a610a2e3ae323d5Jason Evans uint64_t r_out[2]) 158ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 159ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t * data = (const uint8_t *) key; 160ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const int nblocks = len / 16; 161ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 162ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t h1 = seed; 163ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t h2 = seed; 164ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t h3 = seed; 165ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t h4 = seed; 166ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 167ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c1 = 0x239b961b; 168ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c2 = 0xab0e9789; 169ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c3 = 0x38b34ae5; 170ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t c4 = 0xa1e38b93; 171ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 172ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* body */ 173ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 174ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint32_t *blocks = (const uint32_t *) (data + nblocks*16); 175ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans int i; 176ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 177ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans for (i = -nblocks; i; i++) { 178ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k1 = hash_get_block_32(blocks, i*4 + 0); 179ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k2 = hash_get_block_32(blocks, i*4 + 1); 180ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k3 = hash_get_block_32(blocks, i*4 + 2); 181ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k4 = hash_get_block_32(blocks, i*4 + 3); 1826109fe07a14b7a619365977d9523db9f8b333792Jason Evans 183ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c1; k1 = hash_rotl_32(k1, 15); k1 *= c2; h1 ^= k1; 184ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 185ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_rotl_32(h1, 19); h1 += h2; 186ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = h1*5 + 0x561ccd1b; 187ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 188ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k2 *= c2; k2 = hash_rotl_32(k2, 16); k2 *= c3; h2 ^= k2; 189ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 190ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = hash_rotl_32(h2, 17); h2 += h3; 191ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = h2*5 + 0x0bcaa747; 192ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 193ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k3 *= c3; k3 = hash_rotl_32(k3, 17); k3 *= c4; h3 ^= k3; 194ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 195ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h3 = hash_rotl_32(h3, 15); h3 += h4; 196ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h3 = h3*5 + 0x96cd1c35; 197ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 198ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k4 *= c4; k4 = hash_rotl_32(k4, 18); k4 *= c1; h4 ^= k4; 199ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 200ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h4 = hash_rotl_32(h4, 13); h4 += h1; 201ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h4 = h4*5 + 0x32ac3b17; 202ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 203ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 204ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 205ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* tail */ 206ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 207ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t *tail = (const uint8_t *) (data + nblocks*16); 208ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k1 = 0; 209ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k2 = 0; 210ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k3 = 0; 211ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint32_t k4 = 0; 212ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 213ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans switch (len & 15) { 214ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 15: k4 ^= tail[14] << 16; 215ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 14: k4 ^= tail[13] << 8; 216ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 13: k4 ^= tail[12] << 0; 217ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k4 *= c4; k4 = hash_rotl_32(k4, 18); k4 *= c1; h4 ^= k4; 218ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 219ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 12: k3 ^= tail[11] << 24; 220ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 11: k3 ^= tail[10] << 16; 221ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 10: k3 ^= tail[ 9] << 8; 222ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 9: k3 ^= tail[ 8] << 0; 223ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k3 *= c3; k3 = hash_rotl_32(k3, 17); k3 *= c4; h3 ^= k3; 224ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 225ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 8: k2 ^= tail[ 7] << 24; 226ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 7: k2 ^= tail[ 6] << 16; 227ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 6: k2 ^= tail[ 5] << 8; 228ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 5: k2 ^= tail[ 4] << 0; 229ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k2 *= c2; k2 = hash_rotl_32(k2, 16); k2 *= c3; h2 ^= k2; 230ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 231ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 4: k1 ^= tail[ 3] << 24; 232ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 3: k1 ^= tail[ 2] << 16; 233ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 2: k1 ^= tail[ 1] << 8; 234ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 1: k1 ^= tail[ 0] << 0; 235ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c1; k1 = hash_rotl_32(k1, 15); k1 *= c2; h1 ^= k1; 236ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 237ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 238ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 239ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* finalization */ 240ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len; 241ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 242ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 += h2; h1 += h3; h1 += h4; 243ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 += h1; h3 += h1; h4 += h1; 244ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 245ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_fmix_32(h1); 246ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = hash_fmix_32(h2); 247ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h3 = hash_fmix_32(h3); 248ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h4 = hash_fmix_32(h4); 249ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 250ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 += h2; h1 += h3; h1 += h4; 251ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 += h1; h3 += h1; h4 += h1; 252ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 253ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans r_out[0] = (((uint64_t) h2) << 32) | h1; 254ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans r_out[1] = (((uint64_t) h4) << 32) | h3; 255ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 256ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 257ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansUNUSED JEMALLOC_INLINE void 258ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash_x64_128(const void *key, const int len, const uint32_t seed, 2591b75b4e6d11814f470e797be4a610a2e3ae323d5Jason Evans uint64_t r_out[2]) 260ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 261ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t *data = (const uint8_t *) key; 262ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const int nblocks = len / 16; 263ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 264ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t h1 = seed; 265ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t h2 = seed; 266ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 2671f6d77e1f687c3c4fa4ae6768b689a7936923f07Jason Evans const uint64_t c1 = KQU(0x87c37b91114253d5); 2681f6d77e1f687c3c4fa4ae6768b689a7936923f07Jason Evans const uint64_t c2 = KQU(0x4cf5ad432745937f); 269ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 270ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* body */ 271ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 272ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint64_t *blocks = (const uint64_t *) (data); 273ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans int i; 274ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 275ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans for (i = 0; i < nblocks; i++) { 276ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t k1 = hash_get_block_64(blocks, i*2 + 0); 277ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t k2 = hash_get_block_64(blocks, i*2 + 1); 278ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 279ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1; 280ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 281ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_rotl_64(h1, 27); h1 += h2; 282ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = h1*5 + 0x52dce729; 283ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 284ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2; 285ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 286ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = hash_rotl_64(h2, 31); h2 += h1; 287ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = h2*5 + 0x38495ab5; 288ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 289ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 290ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 291ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* tail */ 292ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans { 293ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans const uint8_t *tail = (const uint8_t*)(data + nblocks*16); 294ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t k1 = 0; 295ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans uint64_t k2 = 0; 296ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 297ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans switch (len & 15) { 298ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 15: k2 ^= ((uint64_t)(tail[14])) << 48; 299ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 14: k2 ^= ((uint64_t)(tail[13])) << 40; 300ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 13: k2 ^= ((uint64_t)(tail[12])) << 32; 301ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 12: k2 ^= ((uint64_t)(tail[11])) << 24; 302ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 11: k2 ^= ((uint64_t)(tail[10])) << 16; 303ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 10: k2 ^= ((uint64_t)(tail[ 9])) << 8; 304ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 9: k2 ^= ((uint64_t)(tail[ 8])) << 0; 305ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2; 306ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 307ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 8: k1 ^= ((uint64_t)(tail[ 7])) << 56; 308ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 7: k1 ^= ((uint64_t)(tail[ 6])) << 48; 309ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 6: k1 ^= ((uint64_t)(tail[ 5])) << 40; 310ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 5: k1 ^= ((uint64_t)(tail[ 4])) << 32; 311ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 4: k1 ^= ((uint64_t)(tail[ 3])) << 24; 312ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 3: k1 ^= ((uint64_t)(tail[ 2])) << 16; 313ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 2: k1 ^= ((uint64_t)(tail[ 1])) << 8; 314ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans case 1: k1 ^= ((uint64_t)(tail[ 0])) << 0; 315ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1; 316ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 317ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans } 318ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 319ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans /* finalization */ 320ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 ^= len; h2 ^= len; 321ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 322ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 += h2; 323ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 += h1; 324ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 325ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 = hash_fmix_64(h1); 326ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 = hash_fmix_64(h2); 327ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 328ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h1 += h2; 329ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans h2 += h1; 330ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 331ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans r_out[0] = h1; 332ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans r_out[1] = h2; 333ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans} 334ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans 335ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans/******************************************************************************/ 336ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans/* API. */ 337ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason EvansJEMALLOC_INLINE void 338ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evanshash(const void *key, size_t len, const uint32_t seed, size_t r_hash[2]) 339ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans{ 3409e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans 3419e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans assert(len <= INT_MAX); /* Unfortunate implementation limitation. */ 3429e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans 343df3f27024f193b7baeedcd9f3799b4774dd20bbfJason Evans#if (LG_SIZEOF_PTR == 3 && !defined(JEMALLOC_BIG_ENDIAN)) 3449e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans hash_x64_128(key, (int)len, seed, (uint64_t *)r_hash); 345ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans#else 3469e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans { 3479e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans uint64_t hashes[2]; 3489e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans hash_x86_128(key, (int)len, seed, hashes); 3499e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans r_hash[0] = (size_t)hashes[0]; 3509e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans r_hash[1] = (size_t)hashes[1]; 3519e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans } 352ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans#endif 3536109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 3546109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 3556109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3566109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif /* JEMALLOC_H_INLINES */ 3576109fe07a14b7a619365977d9523db9f8b333792Jason Evans/******************************************************************************/ 358