contrib/jemalloc/include/jemalloc/internal/hash.h

   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; /* falls through */
 264                 case 14: k2 ^= ((uint64_t)(tail[13])) << 40; /* falls through */
 265                 case 13: k2 ^= ((uint64_t)(tail[12])) << 32; /* falls through */
 266                 case 12: k2 ^= ((uint64_t)(tail[11])) << 24; /* falls through */
 267                 case 11: k2 ^= ((uint64_t)(tail[10])) << 16; /* falls through */
 268                 case 10: k2 ^= ((uint64_t)(tail[ 9])) << 8;  /* falls through */
 269                 case  9: k2 ^= ((uint64_t)(tail[ 8])) << 0;
 270                         k2 *= c2; k2 = hash_rotl_64(k2, 33); k2 *= c1; h2 ^= k2;
 271                         /* falls through */
 272                 case  8: k1 ^= ((uint64_t)(tail[ 7])) << 56; /* falls through */
 273                 case  7: k1 ^= ((uint64_t)(tail[ 6])) << 48; /* falls through */
 274                 case  6: k1 ^= ((uint64_t)(tail[ 5])) << 40; /* falls through */
 275                 case  5: k1 ^= ((uint64_t)(tail[ 4])) << 32; /* falls through */
 276                 case  4: k1 ^= ((uint64_t)(tail[ 3])) << 24; /* falls through */
 277                 case  3: k1 ^= ((uint64_t)(tail[ 2])) << 16; /* falls through */
 278                 case  2: k1 ^= ((uint64_t)(tail[ 1])) << 8;  /* falls through */
 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 */