hash.c

   1 /*
   2  * Copyright (C) 2012, 2013, 2014
   3  *     Dale Weiler
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   6  * this software and associated documentation files (the "Software"), to deal in
   7  * the Software without restriction, including without limitation the rights to
   8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
   9  * of the Software, and to permit persons to whom the Software is furnished to do
  10  * so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in all
  13  * copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21  * SOFTWARE.
  22  */
  23 #include "gmqcc.h"
  24 #include <limits.h>
  25 #include <string.h>
  26
  27 #if defined(_MSC_VER)
  28 #   define HASH_ROTL32(X, Y) _rotl((X), (Y))
  29 #elif defined (__GNUC__) && (defined(__i386__) || defined(__amd64__))
  30     static GMQCC_FORCEINLINE uint32_t hash_rotl32(volatile uint32_t x, int8_t r) {
  31         __asm__ __volatile__ ("roll %1,%0" : "+r"(x) : "c"(r));
  32         return x;
  33     }
  34 #   define HASH_ROTL32(X, Y) hash_rotl32((volatile uint32_t)(X), (Y))
  35 #else
  36 #   define HASH_ROTL32(X, Y) (((X) << (Y)) | ((X) >> (32 - (Y))))
  37 #endif
  38
  39 /*
  40  * This is a version of the Murmur3 hashing function optimized for various
  41  * compilers/architectures. It uses the traditional Murmur2 mix staging
  42  * but fixes the mix staging inner loops.
  43  *
  44  * Murmur 2 contains an inner loop such as:
  45  * while (l >= 4) {
  46  *      u32 k = *(u32*)d;
  47  *      k *= m;
  48  *      k ^= k >> r;
  49  *      k *= m;
  50  *
  51  *      h *= m;
  52  *      h ^= k;
  53  *      d += 4;
  54  *      l -= 4;
  55  * }
  56  *
  57  * The two u32s that form the key are the same value for x
  58  * this premix stage will perform the same results for both values. Unrolled
  59  * this produces just:
  60  *  x *= m;
  61  *  x ^= x >> r;
  62  *  x *= m;
  63  *
  64  *  h *= m;
  65  *  h ^= x;
  66  *  h *= m;
  67  *  h ^= x;
  68  *
  69  * This appears to be fine, except what happens when m == 1? well x
  70  * cancels out entierly, leaving just:
  71  *  x ^= x >> r;
  72  *  h ^= x;
  73  *  h ^= x;
  74  *
  75  * So all keys hash to the same value, but how often does m == 1?
  76  * well, it turns out testing x for all possible values yeilds only
  77  * 172,013,942 unique results instead of 2^32. So nearly ~4.6 bits
  78  * are cancelled out on average!
  79  *
  80  * This means we have a 14.5% higher chance of collision. This is where
  81  * Murmur3 comes in to save the day.
  82  */
  83 static GMQCC_FORCEINLINE uint32_t hash_murmur_mix32(uint32_t hash) {
  84     hash ^= hash >> 16;
  85     hash *= 0x85EBCA6B;
  86     hash ^= hash >> 13;
  87     hash *= 0xC2B2AE35;
  88     hash ^= hash >> 16;
  89     return hash;
  90 }
  91
  92 /*
  93  * These constants were calculated with SMHasher to determine the best
  94  * case senario for Murmur3:
  95  *  http://code.google.com/p/smhasher/
  96  */
  97 #define HASH_MURMUR_MASK1 0xCC9E2D51
  98 #define HASH_MURMUR_MASK2 0x1B873593
  99 #define HASH_MURMUR_SEED  0x9747B28C
 100
 101 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
 102 #   define HASH_MURMUR_SAFEREAD(PTR) (*((uint32_t*)(PTR)))
 103 #elif PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
 104 #   if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR >= 3))
 105 #       define HASH_MURMUR_SAFEREAD(PTR) (__builtin_bswap32(*((uint32_t*)(PTR))))
 106 #   endif
 107 #endif
 108 /* Process individual bytes at this point since the endianess isn't known. */
 109 #ifndef HASH_MURMUR_SAFEREAD
 110 #   define HASH_MURMUR_SAFEREAD(PTR) ((PTR)[0] | (PTR)[1] << 8 | (PTR)[2] << 16 | (PTR)[3] << 24)
 111 #endif
 112
 113 #define HASH_MURMUR_BLOCK(H, K)                        \
 114     do {                                               \
 115         K *= HASH_MURMUR_MASK1;                        \
 116         K  = HASH_ROTL32(K, 15);                       \
 117         K *= HASH_MURMUR_MASK2;                        \
 118         H ^= K;                                        \
 119         H  = HASH_ROTL32(H, 13);                       \
 120         H  = H * 5 + 0xE6546B64;                       \
 121     } while (0)
 122 #define HASH_MURMUR_BYTES(COUNT, H, C, N, PTR, LENGTH) \
 123     do {                                               \
 124         int i = COUNT;                                 \
 125         while (i--) {                                  \
 126             C = C >> 8 | *PTR++ << 24;                 \
 127             N++;                                       \
 128             LENGTH--;                                  \
 129             if (N == 4) {                              \
 130                 HASH_MURMUR_BLOCK(H, C);               \
 131                 N = 0;                                 \
 132             }                                          \
 133         }                                              \
 134     } while (0)
 135 #define HASH_MURMUR_TAIL(P, Z, H, C, N, PTR, LEN)      \
 136     do {                                               \
 137         LEN -= LEN/4*4;                                \
 138         HASH_MURMUR_BYTES(LEN, H, C, N, PTR, LEN);     \
 139         *P = H;                                        \
 140         *Z = ((C) & ~0xFF) | (N);                      \
 141     } while (0)
 142
 143 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
 144 static GMQCC_FORCEINLINE void hash_murmur_process(uint32_t *ph1, uint32_t *carry, const void *key, int length) {
 145     uint32_t h1 = *ph1;
 146     uint32_t c  = *carry;
 147
 148     const uint8_t *ptr = (uint8_t*)key;
 149     const uint8_t *end;
 150
 151     int n  = c & 3;
 152     int it = (4 - n) & 3;
 153     if (it && it <= length)
 154         HASH_MURMUR_BYTES(it, h1, c, n, ptr, length);
 155
 156     end = ptr + length/4*4;
 157     for (; ptr < end; ptr += 4) {
 158         uint32_t k1 = HASH_MURMUR_SAFEREAD(ptr);
 159         HASH_MURMUR_BLOCK(h1, k1);
 160     }
 161     HASH_MURMUR_TAIL(ph1, carry, h1, c, n, ptr, length);
 162 }
 163 #else
 164 static GMQCC_FORCEINLINE void hash_murmur_process(uint32_t *ph1, uint32_t *carry, const void *key, int length) {
 165     uint32_t k1;
 166     uint32_t h1 = *ph1;
 167     uint32_t c  = *carry;
 168
 169     const uint8_t *ptr = (uint8_t*)key;
 170     const uint8_t *end;
 171
 172     int n  = c & 3;
 173     int it = -(long)ptr & 3;
 174     if (it && it <= length)
 175         HASH_MURMUR_BYTES(it, h1, c, n, ptr, length);
 176
 177     end = ptr + length / 4 * 4;
 178     switch (n) {
 179         case 0:
 180             for (; ptr < end; ptr += 4) {
 181                 k1 = HASH_MURMUR_SAFEREAD(ptr);
 182                 HASH_MURMUR_BLOCK(h1, k1);
 183             }
 184             break;
 185
 186 #       define NEXT(N, RIGHT, LEFT)                  \
 187             case N:                                  \
 188                 for (; ptr < end; ptr += 4) {        \
 189                     k1  = c >> RIGHT;                \
 190                     c   = HASH_MURMUR_SAFEREAD(ptr); \
 191                     k1 |= c << LEFT;                 \
 192                     HASH_MURMUR_BLOCK(h1, k1);       \
 193                 }                                    \
 194                 break
 195         NEXT(1, 24, 8);
 196         NEXT(2, 16, 16);
 197         NEXT(3, 8,  24);
 198         #undef NEXT
 199     }
 200     HASH_MURMUR_TAIL(ph1, carry, h1, c, n, ptr, length);
 201 }
 202 #endif
 203
 204 static GMQCC_FORCEINLINE uint32_t hash_murmur_result(uint32_t hash, uint32_t carry, size_t length) {
 205     uint32_t k1;
 206     int n = carry & 3;
 207     if (GMQCC_LIKELY(n)) {
 208         k1    = carry >> (4 - n) * 8;
 209         k1   *= HASH_MURMUR_MASK1;
 210         k1    = HASH_ROTL32(k1, 15);
 211         k1   *= HASH_MURMUR_MASK2;
 212         hash ^= k1;
 213     }
 214     hash ^= length;
 215     hash  = hash_murmur_mix32(hash);
 216
 217     return hash;
 218 }
 219
 220 static GMQCC_FORCEINLINE uint32_t hash_murmur(const void *GMQCC_RESTRICT key, size_t length) {
 221     uint32_t hash  = HASH_MURMUR_SEED;
 222     uint32_t carry = 0;
 223     hash_murmur_process(&hash, &carry, key, length);
 224     return hash_murmur_result(hash, carry, length);
 225 }
 226
 227 size_t hash(const char *key) {
 228 #if 0
 229     const char   *s = key;
 230     const char   *a = s;
 231     const size_t *w;
 232
 233     for (; (uintptr_t)s % sizeof(size_t); s++)
 234         if (!*s)
 235             return hash_murmur((const void *)key, s-a);
 236
 237     for (w = (const size_t*)s; !((*w-(size_t)-1/UCHAR_MAX) & ~*w & ((size_t)-1/UCHAR_MAX) * (UCHAR_MAX / 2 + 1)); w++);
 238     for (s = (const char *)w; *s; s++);
 239
 240     return hash_murmur((const void *)key, s-a);
 241 #else
 242     return hash_murmur((const void *)key, strlen(key));
 243 #endif
 244 }
 245
 246 #undef HASH_ROTL32
 247 #undef HASH_MURMUR_MASK1
 248 #undef HASH_MURMUR_MASK2
 249 #undef HASH_MURMUR_SEED
 250 #undef HASH_MURMUR_SAFEREAD
 251 #undef HASH_MURMUR_BLOCK
 252 #undef HASH_MURMUR_BYTES
 253 #undef HASH_MURMUR_TAIL