Happy new year!
[xonotic/gmqcc.git] / 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
26 #if defined(_MSC_VER)
27 #   define HASH_ROTL32(X, Y) _rotl((X), (Y))
28 #elif defined (__GNUC__) && (defined(__i386__) || defined(__amd64__))
29     static GMQCC_FORCEINLINE uint32_t hash_rotl32(volatile uint32_t x, int8_t r) {
30         __asm__ __volatile__ ("roll %1,%0" : "+r"(x) : "c"(r));
31         return x;
32     }
33 #   define HASH_ROTL32(X, Y) hash_rotl32((volatile uint32_t)(X), (Y))
34 #else
35 #   define HASH_ROTL32(X, Y) (((X) << (Y)) | ((X) >> (32 - (Y))))
36 #endif
37
38 /*
39  * This is a version of the Murmur3 hashing function optimized for various
40  * compilers/architectures. It uses the traditional Murmur2 mix staging
41  * but fixes the mix staging inner loops.
42  *
43  * Murmur 2 contains an inner loop such as:
44  * while (l >= 4) {
45  *      u32 k = *(u32*)d;
46  *      k *= m;
47  *      k ^= k >> r;
48  *      k *= m;
49  *
50  *      h *= m;
51  *      h ^= k;
52  *      d += 4;
53  *      l -= 4;
54  * }
55  *
56  * The two u32s that form the key are the same value for x
57  * this premix stage will perform the same results for both values. Unrolled
58  * this produces just:
59  *  x *= m;
60  *  x ^= x >> r;
61  *  x *= m;
62  *
63  *  h *= m;
64  *  h ^= x;
65  *  h *= m;
66  *  h ^= x;
67  *
68  * This appears to be fine, except what happens when m == 1? well x
69  * cancels out entierly, leaving just:
70  *  x ^= x >> r;
71  *  h ^= x;
72  *  h ^= x;
73  *
74  * So all keys hash to the same value, but how often does m == 1?
75  * well, it turns out testing x for all possible values yeilds only
76  * 172,013,942 unique results instead of 2^32. So nearly ~4.6 bits
77  * are cancelled out on average!
78  *
79  * This means we have a 14.5% higher chance of collision. This is where
80  * Murmur3 comes in to save the day.
81  */
82 static GMQCC_FORCEINLINE uint32_t hash_murmur_mix32(uint32_t hash) {
83     hash ^= hash >> 16;
84     hash *= 0x85EBCA6B;
85     hash ^= hash >> 13;
86     hash *= 0xC2B2AE35;
87     hash ^= hash >> 16;
88     return hash;
89 }
90
91 /*
92  * These constants were calculated with SMHasher to determine the best
93  * case senario for Murmur3:
94  *  http://code.google.com/p/smhasher/
95  */
96 #define HASH_MURMUR_MASK1 0xCC9E2D51
97 #define HASH_MURMUR_MASK2 0x1B873593
98 #define HASH_MURMUR_SEED  0x9747B28C
99
100 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
101 #   define HASH_MURMUR_SAFEREAD(PTR) (*((uint32_t*)(PTR)))
102 #elif PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_BIG
103 #   if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR >= 3))
104 #       define HASH_MURMUR_SAFEREAD(PTR) (__builtin_bswap32(*((uint32_t*)(PTR))))
105 #   endif
106 #endif
107 /* Process individual bytes at this point since the endianess isn't known. */
108 #ifndef HASH_MURMUR_SAFEREAD
109 #   define HASH_MURMUR_SAFEREAD(PTR) ((PTR)[0] | (PTR)[1] << 8 | (PTR)[2] << 16 | (PTR)[3] << 24)
110 #endif
111
112 #define HASH_MURMUR_BLOCK(H, K)                        \
113     do {                                               \
114         K *= HASH_MURMUR_MASK1;                        \
115         K  = HASH_ROTL32(K, 15);                       \
116         K *= HASH_MURMUR_MASK2;                        \
117         H ^= K;                                        \
118         H  = HASH_ROTL32(H, 13);                       \
119         H  = H * 5 + 0xE6546B64;                       \
120     } while (0)
121 #define HASH_MURMUR_BYTES(COUNT, H, C, N, PTR, LENGTH) \
122     do {                                               \
123         int i = COUNT;                                 \
124         while (i--) {                                  \
125             C = C >> 8 | *PTR++ << 24;                 \
126             N++;                                       \
127             LENGTH--;                                  \
128             if (N == 4) {                              \
129                 HASH_MURMUR_BLOCK(H, C);               \
130                 N = 0;                                 \
131             }                                          \
132         }                                              \
133     } while (0)
134 #define HASH_MURMUR_TAIL(P, Z, H, C, N, PTR, LEN)      \
135     do {                                               \
136         LEN -= LEN/4*4;                                \
137         HASH_MURMUR_BYTES(LEN, H, C, N, PTR, LEN);     \
138         *P = H;                                        \
139         *Z = ((C) & ~0xFF) | (N);                      \
140     } while (0)
141
142 #if PLATFORM_BYTE_ORDER == GMQCC_BYTE_ORDER_LITTLE
143 static GMQCC_FORCEINLINE void hash_murmur_process(uint32_t *ph1, uint32_t *carry, const void *key, int length) {
144     uint32_t h1 = *ph1;
145     uint32_t c  = *carry;
146
147     const uint8_t *ptr = (uint8_t*)key;
148     const uint8_t *end;
149
150     int n  = c & 3;
151     int it = (4 - n) & 3;
152     if (it && it <= length)
153         HASH_MURMUR_BYTES(it, h1, c, n, ptr, length);
154
155     end = ptr + length/4*4;
156     for (; ptr < end; ptr += 4) {
157         uint32_t k1 = HASH_MURMUR_SAFEREAD(ptr);
158         HASH_MURMUR_BLOCK(h1, k1);
159     }
160     HASH_MURMUR_TAIL(ph1, carry, h1, c, n, ptr, length);
161 }
162 #else
163 static GMQCC_FORCEINLINE void hash_murmur_process(uint32_t *ph1, uint32_t *carry, const void *key, int length) {
164     uint32_t k1;
165     uint32_t h1 = *ph1;
166     uint32_t c  = *carry;
167
168     const uint8_t *ptr = (uint8_t*)key;
169     const uint8_t *end;
170
171     int n  = c & 3;
172     int it = -(long)ptr & 3;
173     if (it && it <= length)
174         HASH_MURMUR_BYTES(it, h1, c, n, ptr, length);
175
176     end = ptr + length / 4 * 4;
177     switch (n) {
178         case 0:
179             for (; ptr < end; ptr += 4) {
180                 k1 = HASH_MURMUR_SAFEREAD(ptr);
181                 HASH_MURMUR_BLOCK(h1, k1);
182             }
183             break;
184
185 #       define NEXT(N, RIGHT, LEFT)                  \
186             case N:                                  \
187                 for (; ptr < end; ptr += 4) {        \
188                     k1  = c >> RIGHT;                \
189                     c   = HASH_MURMUR_SAFEREAD(ptr); \
190                     k1 |= c << LEFT;                 \
191                     HASH_MURMUR_BLOCK(h1, k1);       \
192                 }                                    \
193                 break
194         NEXT(1, 24, 8);
195         NEXT(2, 16, 16);
196         NEXT(3, 8,  24);
197         #undef NEXT
198     }
199     HASH_MURMUR_TAIL(ph1, carry, h1, c, n, ptr, length);
200 }
201 #endif
202
203 static GMQCC_FORCEINLINE uint32_t hash_murmur_result(uint32_t hash, uint32_t carry, size_t length) {
204     uint32_t k1;
205     int n = carry & 3;
206     if (GMQCC_LIKELY(n)) {
207         k1    = carry >> (4 - n) * 8;
208         k1   *= HASH_MURMUR_MASK1;
209         k1    = HASH_ROTL32(k1, 15);
210         k1   *= HASH_MURMUR_MASK2;
211         hash ^= k1;
212     }
213     hash ^= length;
214     hash  = hash_murmur_mix32(hash);
215
216     return hash;
217 }
218
219 static GMQCC_FORCEINLINE uint32_t hash_murmur(const void *GMQCC_RESTRICT key, size_t length) {
220     uint32_t hash  = HASH_MURMUR_SEED;
221     uint32_t carry = 0;
222     hash_murmur_process(&hash, &carry, key, length);
223     return hash_murmur_result(hash, carry, length);
224 }
225
226 size_t hash(const char *key) {
227     const char   *s = key;
228     const char   *a = s;
229     const size_t *w;
230
231     for (; (uintptr_t)s % sizeof(size_t); s++)
232         if (!*s)
233             return hash_murmur((const void *)key, s-a);
234
235     for (w = (const size_t*)s; !((*w-(size_t)-1/UCHAR_MAX) & ~*w & ((size_t)-1/UCHAR_MAX) * (UCHAR_MAX / 2 + 1)); w++);
236     for (s = (const char *)w; *s; s++);
237
238     return hash_murmur((const void *)key, s-a);
239 }
240
241 #undef HASH_ROTL32
242 #undef HASH_MURMUR_MASK1
243 #undef HASH_MURMUR_MASK2
244 #undef HASH_MURMUR_SEED
245 #undef HASH_MURMUR_SAFEREAD
246 #undef HASH_MURMUR_BLOCK
247 #undef HASH_MURMUR_BYTES
248 #undef HASH_MURMUR_TAIL