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, (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, (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; 181 case 14: k4 ^= tail[13] << 8; 182 case 13: k4 ^= tail[12] << 0; 183 k4 *= c4; k4 = hash_rotl_32(k4, 18); k4 *= c1; h4 ^= k4; 184 185 case 12: k3 ^= tail[11] << 24; 186 case 11: k3 ^= tail[10] << 16; 187 case 10: k3 ^= tail[ 9] << 8; 188 case 9: k3 ^= tail[ 8] << 0; 189 k3 *= c3; k3 = hash_rotl_32(k3, 17); k3 *= c4; h3 ^= k3; 190 191 case 8: k2 ^= tail[ 7] << 24; 192 case 7: k2 ^= tail[ 6] << 16; 193 case 6: k2 ^= tail[ 5] << 8; 194 case 5: k2 ^= tail[ 4] << 0; 195 k2 *= c2; k2 = hash_rotl_32(k2, 16); k2 *= c3; h2 ^= k2; 196 197 case 4: k1 ^= tail[ 3] << 24; 198 case 3: k1 ^= tail[ 2] << 16; 199 case 2: k1 ^= tail[ 1] << 8; 200 case 1: k1 ^= tail[ 0] << 0; 201 k1 *= c1; k1 = hash_rotl_32(k1, 15); k1 *= c2; h1 ^= k1; 202 } 203 } 204 205 /* finalization */ 206 h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len; 207 208 h1 += h2; h1 += h3; h1 += h4; 209 h2 += h1; h3 += h1; h4 += h1; 210 211 h1 = hash_fmix_32(h1); 212 h2 = hash_fmix_32(h2); 213 h3 = hash_fmix_32(h3); 214 h4 = hash_fmix_32(h4); 215 216 h1 += h2; h1 += h3; h1 += h4; 217 h2 += h1; h3 += h1; h4 += h1; 218 219 r_out[0] = (((uint64_t) h2) << 32) | h1; 220 r_out[1] = (((uint64_t) h4) << 32) | h3; 221 } 222 223 UNUSED static inline void 224 hash_x64_128(const void *key, const int len, const uint32_t seed, 225 uint64_t r_out[2]) { 226 const uint8_t *data = (const uint8_t *) key; 227 const int nblocks = len / 16; 228 229 uint64_t h1 = seed; 230 uint64_t h2 = seed; 231 232 const uint64_t c1 = KQU(0x87c37b91114253d5); 233 const uint64_t c2 = KQU(0x4cf5ad432745937f); 234 235 /* body */ 236 { 237 const uint64_t *blocks = (const uint64_t *) (data); 238 int i; 239 240 for (i = 0; i < nblocks; i++) { 241 uint64_t k1 = hash_get_block_64(blocks, i*2 + 0); 242 uint64_t k2 = hash_get_block_64(blocks, i*2 + 1); 243 244 k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1; 245 246 h1 = hash_rotl_64(h1, 27); h1 += h2; 247 h1 = h1*5 + 0x52dce729; 248 249 k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2; 250 251 h2 = hash_rotl_64(h2, 31); h2 += h1; 252 h2 = h2*5 + 0x38495ab5; 253 } 254 } 255 256 /* tail */ 257 { 258 const uint8_t *tail = (const uint8_t*)(data + nblocks*16); 259 uint64_t k1 = 0; 260 uint64_t k2 = 0; 261 262 switch (len & 15) { 263 case 15: k2 ^= ((uint64_t)(tail[14])) << 48; 264 case 14: k2 ^= ((uint64_t)(tail[13])) << 40; 265 case 13: k2 ^= ((uint64_t)(tail[12])) << 32; 266 case 12: k2 ^= ((uint64_t)(tail[11])) << 24; 267 case 11: k2 ^= ((uint64_t)(tail[10])) << 16; 268 case 10: k2 ^= ((uint64_t)(tail[ 9])) << 8; 269 case 9: k2 ^= ((uint64_t)(tail[ 8])) << 0; 270 k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2; 271 272 case 8: k1 ^= ((uint64_t)(tail[ 7])) << 56; 273 case 7: k1 ^= ((uint64_t)(tail[ 6])) << 48; 274 case 6: k1 ^= ((uint64_t)(tail[ 5])) << 40; 275 case 5: k1 ^= ((uint64_t)(tail[ 4])) << 32; 276 case 4: k1 ^= ((uint64_t)(tail[ 3])) << 24; 277 case 3: k1 ^= ((uint64_t)(tail[ 2])) << 16; 278 case 2: k1 ^= ((uint64_t)(tail[ 1])) << 8; 279 case 1: k1 ^= ((uint64_t)(tail[ 0])) << 0; 280 k1 *= c1; k1 = hash_rotl_64(k1, 31); k1 *= c2; h1 ^= k1; 281 } 282 } 283 284 /* finalization */ 285 h1 ^= len; h2 ^= len; 286 287 h1 += h2; 288 h2 += h1; 289 290 h1 = hash_fmix_64(h1); 291 h2 = hash_fmix_64(h2); 292 293 h1 += h2; 294 h2 += h1; 295 296 r_out[0] = h1; 297 r_out[1] = h2; 298 } 299 300 /******************************************************************************/ 301 /* API. */ 302 static inline void 303 hash(const void *key, size_t len, const uint32_t seed, size_t r_hash[2]) { 304 assert(len <= INT_MAX); /* Unfortunate implementation limitation. */ 305 306 #if (LG_SIZEOF_PTR == 3 && !defined(JEMALLOC_BIG_ENDIAN)) 307 hash_x64_128(key, (int)len, seed, (uint64_t *)r_hash); 308 #else 309 { 310 uint64_t hashes[2]; 311 hash_x86_128(key, (int)len, seed, hashes); 312 r_hash[0] = (size_t)hashes[0]; 313 r_hash[1] = (size_t)hashes[1]; 314 } 315 #endif 316 } 317 318 #endif /* JEMALLOC_INTERNAL_HASH_H */ 319