1 #ifndef JEMALLOC_INTERNAL_HASH_H 2 #define JEMALLOC_INTERNAL_HASH_H 3 4 #include "jemalloc/internal/assert.h" 5 6 /* 7 * The following hash function is based on MurmurHash3, placed into the public 8 * domain by Austin Appleby. See https://github.com/aappleby/smhasher for 9 * details. 10 */ 11 12 /******************************************************************************/ 13 /* Internal implementation. */ 14 static inline uint32_t 15 hash_rotl_32(uint32_t x, int8_t r) { 16 return ((x << r) | (x >> (32 - r))); 17 } 18 19 static inline uint64_t 20 hash_rotl_64(uint64_t x, int8_t r) { 21 return ((x << r) | (x >> (64 - r))); 22 } 23 24 static inline uint32_t 25 hash_get_block_32(const uint32_t *p, int i) { 26 /* Handle unaligned read. */ 27 if (unlikely((uintptr_t)p & (sizeof(uint32_t)-1)) != 0) { 28 uint32_t ret; 29 30 memcpy(&ret, (const uint8_t *)(p + i), sizeof(uint32_t)); 31 return ret; 32 } 33 34 return p[i]; 35 } 36 37 static inline uint64_t 38 hash_get_block_64(const uint64_t *p, int i) { 39 /* Handle unaligned read. */ 40 if (unlikely((uintptr_t)p & (sizeof(uint64_t)-1)) != 0) { 41 uint64_t ret; 42 43 memcpy(&ret, (const uint8_t *)(p + i), sizeof(uint64_t)); 44 return ret; 45 } 46 47 return p[i]; 48 } 49 50 static inline uint32_t 51 hash_fmix_32(uint32_t h) { 52 h ^= h >> 16; 53 h *= 0x85ebca6b; 54 h ^= h >> 13; 55 h *= 0xc2b2ae35; 56 h ^= h >> 16; 57 58 return h; 59 } 60 61 static inline uint64_t 62 hash_fmix_64(uint64_t k) { 63 k ^= k >> 33; 64 k *= KQU(0xff51afd7ed558ccd); 65 k ^= k >> 33; 66 k *= KQU(0xc4ceb9fe1a85ec53); 67 k ^= k >> 33; 68 69 return k; 70 } 71 72 static inline uint32_t 73 hash_x86_32(const void *key, int len, uint32_t seed) { 74 const uint8_t *data = (const uint8_t *) key; 75 const int nblocks = len / 4; 76 77 uint32_t h1 = seed; 78 79 const uint32_t c1 = 0xcc9e2d51; 80 const uint32_t c2 = 0x1b873593; 81 82 /* body */ 83 { 84 const uint32_t *blocks = (const uint32_t *) (data + nblocks*4); 85 int i; 86 87 for (i = -nblocks; i; i++) { 88 uint32_t k1 = hash_get_block_32(blocks, i); 89 90 k1 *= c1; 91 k1 = hash_rotl_32(k1, 15); 92 k1 *= c2; 93 94 h1 ^= k1; 95 h1 = hash_rotl_32(h1, 13); 96 h1 = h1*5 + 0xe6546b64; 97 } 98 } 99 100 /* tail */ 101 { 102 const uint8_t *tail = (const uint8_t *) (data + nblocks*4); 103 104 uint32_t k1 = 0; 105 106 switch (len & 3) { 107 case 3: k1 ^= tail[2] << 16; 108 case 2: k1 ^= tail[1] << 8; 109 case 1: k1 ^= tail[0]; k1 *= c1; k1 = hash_rotl_32(k1, 15); 110 k1 *= c2; h1 ^= k1; 111 } 112 } 113 114 /* finalization */ 115 h1 ^= len; 116 117 h1 = hash_fmix_32(h1); 118 119 return h1; 120 } 121 122 UNUSED static inline void 123 hash_x86_128(const void *key, const int len, uint32_t seed, 124 uint64_t r_out[2]) { 125 const uint8_t * data = (const uint8_t *) key; 126 const int nblocks = len / 16; 127 128 uint32_t h1 = seed; 129 uint32_t h2 = seed; 130 uint32_t h3 = seed; 131 uint32_t h4 = seed; 132 133 const uint32_t c1 = 0x239b961b; 134 const uint32_t c2 = 0xab0e9789; 135 const uint32_t c3 = 0x38b34ae5; 136 const uint32_t c4 = 0xa1e38b93; 137 138 /* body */ 139 { 140 const uint32_t *blocks = (const uint32_t *) (data + nblocks*16); 141 int i; 142 143 for (i = -nblocks; i; i++) { 144 uint32_t k1 = hash_get_block_32(blocks, i*4 + 0); 145 uint32_t k2 = hash_get_block_32(blocks, i*4 + 1); 146 uint32_t k3 = hash_get_block_32(blocks, i*4 + 2); 147 uint32_t k4 = hash_get_block_32(blocks, i*4 + 3); 148 149 k1 *= c1; k1 = hash_rotl_32(k1, 15); k1 *= c2; h1 ^= k1; 150 151 h1 = hash_rotl_32(h1, 19); h1 += h2; 152 h1 = h1*5 + 0x561ccd1b; 153 154 k2 *= c2; k2 = hash_rotl_32(k2, 16); k2 *= c3; h2 ^= k2; 155 156 h2 = hash_rotl_32(h2, 17); h2 += h3; 157 h2 = h2*5 + 0x0bcaa747; 158 159 k3 *= c3; k3 = hash_rotl_32(k3, 17); k3 *= c4; h3 ^= k3; 160 161 h3 = hash_rotl_32(h3, 15); h3 += h4; 162 h3 = h3*5 + 0x96cd1c35; 163 164 k4 *= c4; k4 = hash_rotl_32(k4, 18); k4 *= c1; h4 ^= k4; 165 166 h4 = hash_rotl_32(h4, 13); h4 += h1; 167 h4 = h4*5 + 0x32ac3b17; 168 } 169 } 170 171 /* tail */ 172 { 173 const uint8_t *tail = (const uint8_t *) (data + nblocks*16); 174 uint32_t k1 = 0; 175 uint32_t k2 = 0; 176 uint32_t k3 = 0; 177 uint32_t k4 = 0; 178 179 switch (len & 15) { 180 case 15: k4 ^= tail[14] << 16; /*FALLTHROUGH*/ 181 case 14: k4 ^= tail[13] << 8; /*FALLTHROUGH*/ 182 case 13: k4 ^= tail[12] << 0; 183 k4 *= c4; k4 = hash_rotl_32(k4, 18); k4 *= c1; h4 ^= k4; 184 /*FALLTHROUGH*/ 185 186 case 12: k3 ^= (uint32_t)tail[11] << 24; /*FALLTHROUGH*/ 187 case 11: k3 ^= tail[10] << 16; /*FALLTHROUGH*/ 188 case 10: k3 ^= tail[ 9] << 8; /*FALLTHROUGH*/ 189 case 9: k3 ^= tail[ 8] << 0; 190 k3 *= c3; k3 = hash_rotl_32(k3, 17); k3 *= c4; h3 ^= k3; 191 /*FALLTHROUGH*/ 192 193 case 8: k2 ^= (uint32_t)tail[ 7] << 24; /*FALLTHROUGH*/ 194 case 7: k2 ^= tail[ 6] << 16; /*FALLTHROUGH*/ 195 case 6: k2 ^= tail[ 5] << 8; /*FALLTHROUGH*/ 196 case 5: k2 ^= tail[ 4] << 0; 197 k2 *= c2; k2 = hash_rotl_32(k2, 16); k2 *= c3; h2 ^= k2; 198 /*FALLTHROUGH*/ 199 200 case 4: k1 ^= (uint32_t)tail[ 3] << 24; /*FALLTHROUGH*/ 201 case 3: k1 ^= tail[ 2] << 16; /*FALLTHROUGH*/ 202 case 2: k1 ^= tail[ 1] << 8; /*FALLTHROUGH*/ 203 case 1: k1 ^= tail[ 0] << 0; 204 k1 *= c1; k1 = hash_rotl_32(k1, 15); k1 *= c2; h1 ^= k1; 205 } 206 } 207 208 /* finalization */ 209 h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len; 210 211 h1 += h2; h1 += h3; h1 += h4; 212 h2 += h1; h3 += h1; h4 += h1; 213 214 h1 = hash_fmix_32(h1); 215 h2 = hash_fmix_32(h2); 216 h3 = hash_fmix_32(h3); 217 h4 = hash_fmix_32(h4); 218 219 h1 += h2; h1 += h3; h1 += h4; 220 h2 += h1; h3 += h1; h4 += h1; 221 222 r_out[0] = (((uint64_t) h2) << 32) | h1; 223 r_out[1] = (((uint64_t) h4) << 32) | h3; 224 } 225 226 UNUSED static inline void 227 hash_x64_128(const void *key, const int len, const uint32_t seed, 228 uint64_t r_out[2]) { 229 const uint8_t *data = (const uint8_t *) key; 230 const int nblocks = len / 16; 231 232 uint64_t h1 = seed; 233 uint64_t h2 = seed; 234 235 const uint64_t c1 = KQU(0x87c37b91114253d5); 236 const uint64_t c2 = KQU(0x4cf5ad432745937f); 237 238 /* body */ 239 { 240 const uint64_t *blocks = (const uint64_t *) (data); 241 int i; 242 243 for (i = 0; i < nblocks; i++) { 244 uint64_t k1 = hash_get_block_64(blocks, i*2 + 0); 245 uint64_t k2 = hash_get_block_64(blocks, i*2 + 1); 246 247 k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1; 248 249 h1 = hash_rotl_64(h1, 27); h1 += h2; 250 h1 = h1*5 + 0x52dce729; 251 252 k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2; 253 254 h2 = hash_rotl_64(h2, 31); h2 += h1; 255 h2 = h2*5 + 0x38495ab5; 256 } 257 } 258 259 /* tail */ 260 { 261 const uint8_t *tail = (const uint8_t*)(data + nblocks*16); 262 uint64_t k1 = 0; 263 uint64_t k2 = 0; 264 265 switch (len & 15) { 266 case 15: k2 ^= ((uint64_t)(tail[14])) << 48; /* falls through */ 267 case 14: k2 ^= ((uint64_t)(tail[13])) << 40; /* falls through */ 268 case 13: k2 ^= ((uint64_t)(tail[12])) << 32; /* falls through */ 269 case 12: k2 ^= ((uint64_t)(tail[11])) << 24; /* falls through */ 270 case 11: k2 ^= ((uint64_t)(tail[10])) << 16; /* falls through */ 271 case 10: k2 ^= ((uint64_t)(tail[ 9])) << 8; /* falls through */ 272 case 9: k2 ^= ((uint64_t)(tail[ 8])) << 0; 273 k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2; 274 /* falls through */ 275 case 8: k1 ^= ((uint64_t)(tail[ 7])) << 56; /* falls through */ 276 case 7: k1 ^= ((uint64_t)(tail[ 6])) << 48; /* falls through */ 277 case 6: k1 ^= ((uint64_t)(tail[ 5])) << 40; /* falls through */ 278 case 5: k1 ^= ((uint64_t)(tail[ 4])) << 32; /* falls through */ 279 case 4: k1 ^= ((uint64_t)(tail[ 3])) << 24; /* falls through */ 280 case 3: k1 ^= ((uint64_t)(tail[ 2])) << 16; /* falls through */ 281 case 2: k1 ^= ((uint64_t)(tail[ 1])) << 8; /* falls through */ 282 case 1: k1 ^= ((uint64_t)(tail[ 0])) << 0; 283 k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1; 284 } 285 } 286 287 /* finalization */ 288 h1 ^= len; h2 ^= len; 289 290 h1 += h2; 291 h2 += h1; 292 293 h1 = hash_fmix_64(h1); 294 h2 = hash_fmix_64(h2); 295 296 h1 += h2; 297 h2 += h1; 298 299 r_out[0] = h1; 300 r_out[1] = h2; 301 } 302 303 /******************************************************************************/ 304 /* API. */ 305 static inline void 306 hash(const void *key, size_t len, const uint32_t seed, size_t r_hash[2]) { 307 assert(len <= INT_MAX); /* Unfortunate implementation limitation. */ 308 309 #if (LG_SIZEOF_PTR == 3 && !defined(JEMALLOC_BIG_ENDIAN)) 310 hash_x64_128(key, (int)len, seed, (uint64_t *)r_hash); 311 #else 312 { 313 uint64_t hashes[2]; 314 hash_x86_128(key, (int)len, seed, hashes); 315 r_hash[0] = (size_t)hashes[0]; 316 r_hash[1] = (size_t)hashes[1]; 317 } 318 #endif 319 } 320 321 #endif /* JEMALLOC_INTERNAL_HASH_H */ 322