1 /*-----------------------------------------------------------------------------
2 * MurmurHash3 was written by Austin Appleby, and is placed in the public
3 * domain.
4 *
5 * This implementation was written by Shane Day, and is also public domain.
6 *
7 * This is a portable ANSI C implementation of MurmurHash3_x86_32 (Murmur3A)
8 * with support for progressive processing.
9 */
10
11 /*-----------------------------------------------------------------------------
12
13 If you want to understand the MurmurHash algorithm you would be much better
14 off reading the original source. Just point your browser at:
15 http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
16
17
18 What this version provides?
19
20 1. Progressive data feeding. Useful when the entire payload to be hashed
21 does not fit in memory or when the data is streamed through the application.
22 Also useful when hashing a number of strings with a common prefix. A partial
23 hash of a prefix string can be generated and reused for each suffix string.
24
25 2. Portability. Plain old C so that it should compile on any old compiler.
26 Both CPU endian and access-alignment neutral, but avoiding inefficient code
27 when possible depending on CPU capabilities.
28
29 3. Drop in. I personally like nice self contained public domain code, making it
30 easy to pilfer without loads of refactoring to work properly in the existing
31 application code & makefile structure and mucking around with licence files.
32 Just copy PMurHash.h and PMurHash.c and you're ready to go.
33
34
35 How does it work?
36
37 We can only process entire 32 bit chunks of input, except for the very end
38 that may be shorter. So along with the partial hash we need to give back to
39 the caller a carry containing up to 3 bytes that we were unable to process.
40 This carry also needs to record the number of bytes the carry holds. I use
41 the low 2 bits as a count (0..3) and the carry bytes are shifted into the
42 high byte in stream order.
43
44 To handle endianess I simply use a macro that reads a uint32_t and define
45 that macro to be a direct read on little endian machines, a read and swap
46 on big endian machines, or a byte-by-byte read if the endianess is unknown.
47
48 -----------------------------------------------------------------------------*/
49
50 #include "PMurHash.h"
51 #include <stdint.h>
52
53 /* I used ugly type names in the header to avoid potential conflicts with
54 * application or system typedefs & defines. Since I'm not including any more
55 * headers below here I can rename these so that the code reads like C99 */
56 #undef uint32_t
57 #define uint32_t MH_UINT32
58 #undef uint8_t
59 #define uint8_t MH_UINT8
60
61 /* MSVC warnings we choose to ignore */
62 #if defined(_MSC_VER)
63 # pragma warning(disable : 4127) /* conditional expression is constant */
64 #endif
65
66 /*-----------------------------------------------------------------------------
67 * Endianess, misalignment capabilities and util macros
68 *
69 * The following 3 macros are defined in this section. The other macros defined
70 * are only needed to help derive these 3.
71 *
72 * READ_UINT32(x) Read a little endian unsigned 32-bit int
73 * UNALIGNED_SAFE Defined if READ_UINT32 works on non-word boundaries
74 * ROTL32(x,r) Rotate x left by r bits
75 */
76
77 /* Convention is to define __BYTE_ORDER == to one of these values */
78 #if !defined(__BIG_ENDIAN)
79 # define __BIG_ENDIAN 4321
80 #endif
81 #if !defined(__LITTLE_ENDIAN)
82 # define __LITTLE_ENDIAN 1234
83 #endif
84
85 /* I386 */
86 #if defined(_M_IX86) || defined(__i386__) || defined(__i386) || defined(i386)
87 # define __BYTE_ORDER __LITTLE_ENDIAN
88 # define UNALIGNED_SAFE
89 #endif
90
91 /* gcc 'may' define __LITTLE_ENDIAN__ or __BIG_ENDIAN__ to 1 (Note the trailing __),
92 * or even _LITTLE_ENDIAN or _BIG_ENDIAN (Note the single _ prefix) */
93 #if !defined(__BYTE_ORDER)
94 # if defined(__LITTLE_ENDIAN__) && __LITTLE_ENDIAN__ == 1 || \
95 defined(_LITTLE_ENDIAN) && _LITTLE_ENDIAN == 1
96 # define __BYTE_ORDER __LITTLE_ENDIAN
97 # elif defined(__BIG_ENDIAN__) && __BIG_ENDIAN__ == 1 || defined(_BIG_ENDIAN) && _BIG_ENDIAN == 1
98 # define __BYTE_ORDER __BIG_ENDIAN
99 # endif
100 #endif
101
102 /* gcc (usually) defines xEL/EB macros for ARM and MIPS endianess */
103 #if !defined(__BYTE_ORDER)
104 # if defined(__ARMEL__) || defined(__MIPSEL__)
105 # define __BYTE_ORDER __LITTLE_ENDIAN
106 # endif
107 # if defined(__ARMEB__) || defined(__MIPSEB__)
108 # define __BYTE_ORDER __BIG_ENDIAN
109 # endif
110 #endif
111
112 /* Now find best way we can to READ_UINT32 */
113 #if __BYTE_ORDER == __LITTLE_ENDIAN
114 /* CPU endian matches murmurhash algorithm, so read 32-bit word directly */
115 # define READ_UINT32(ptr) (*((uint32_t *)(ptr)))
116 #elif __BYTE_ORDER == __BIG_ENDIAN
117 /* TODO: Add additional cases below where a compiler provided bswap32 is available */
118 # if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 3))
119 # define READ_UINT32(ptr) (__builtin_bswap32(*((uint32_t *)(ptr))))
120 # else
121 /* Without a known fast bswap32 we're just as well off doing this */
122 # define READ_UINT32(ptr) (ptr[0] | ptr[1] << 8 | ptr[2] << 16 | ptr[3] << 24)
123 # define UNALIGNED_SAFE
124 # endif
125 #else
126 /* Unknown endianess so last resort is to read individual bytes */
127 # define READ_UINT32(ptr) (ptr[0] | ptr[1] << 8 | ptr[2] << 16 | ptr[3] << 24)
128
129 /* Since we're not doing word-reads we can skip the messing about with realignment */
130 # define UNALIGNED_SAFE
131 #endif
132
133 /* Find best way to ROTL32 */
134 #if defined(_MSC_VER)
135 # include <stdlib.h> /* Microsoft put _rotl declaration in here */
136 # define ROTL32(x, r) _rotl(x, r)
137 #else
138 /* gcc recognises this code and generates a rotate instruction for CPUs with one */
139 # define ROTL32(x, r) (((uint32_t)x << r) | ((uint32_t)x >> (32 - r)))
140 #endif
141
142 /*-----------------------------------------------------------------------------
143 * Core murmurhash algorithm macros */
144
145 #define C1 (0xcc9e2d51)
146 #define C2 (0x1b873593)
147
148 /* This is the main processing body of the algorithm. It operates
149 * on each full 32-bits of input. */
150 #define DOBLOCK(h1, k1) \
151 do \
152 { \
153 k1 *= C1; \
154 k1 = ROTL32(k1, 15); \
155 k1 *= C2; \
156 \
157 h1 ^= k1; \
158 h1 = ROTL32(h1, 13); \
159 h1 = h1 * 5 + 0xe6546b64; \
160 } while (0)
161
162 /* Append unaligned bytes to carry, forcing hash churn if we have 4 bytes */
163 /* cnt=bytes to process, h1=name of h1 var, c=carry, n=bytes in c, ptr/len=payload */
164 #define DOBYTES(cnt, h1, c, n, ptr, len) \
165 do \
166 { \
167 int _i = cnt; \
168 while (_i--) \
169 { \
170 c = c >> 8 | *ptr++ << 24; \
171 n++; \
172 len--; \
173 if (n == 4) \
174 { \
175 DOBLOCK(h1, c); \
176 n = 0; \
177 } \
178 } \
179 } while (0)
180
181 /*---------------------------------------------------------------------------*/
182
183 namespace angle
184 {
185 /* Main hashing function. Initialise carry to 0 and h1 to 0 or an initial seed
186 * if wanted. Both ph1 and pcarry are required arguments. */
PMurHash32_Process(uint32_t * ph1,uint32_t * pcarry,const void * key,int len)187 void PMurHash32_Process(uint32_t *ph1, uint32_t *pcarry, const void *key, int len)
188 {
189 uint32_t h1 = *ph1;
190 uint32_t c = *pcarry;
191
192 const uint8_t *ptr = (uint8_t *)key;
193 const uint8_t *end;
194
195 /* Extract carry count from low 2 bits of c value */
196 int n = c & 3;
197
198 #if defined(UNALIGNED_SAFE)
199 /* This CPU handles unaligned word access */
200
201 /* Consume any carry bytes */
202 int i = (4 - n) & 3;
203 if (i && i <= len)
204 {
205 DOBYTES(i, h1, c, n, ptr, len);
206 }
207
208 /* Process 32-bit chunks */
209 end = ptr + len / 4 * 4;
210 for (; ptr < end; ptr += 4)
211 {
212 uint32_t k1 = READ_UINT32(ptr);
213 DOBLOCK(h1, k1);
214 }
215
216 #else /*UNALIGNED_SAFE*/
217 /* This CPU does not handle unaligned word access */
218
219 /* Consume enough so that the next data byte is word aligned */
220 int i = -(intptr_t)ptr & 3;
221 if (i && i <= len)
222 {
223 DOBYTES(i, h1, c, n, ptr, len);
224 }
225
226 /* We're now aligned. Process in aligned blocks. Specialise for each possible carry count */
227 end = ptr + len / 4 * 4;
228 switch (n)
229 { /* how many bytes in c */
230 case 0: /* c=[----] w=[3210] b=[3210]=w c'=[----] */
231 for (; ptr < end; ptr += 4)
232 {
233 uint32_t k1 = READ_UINT32(ptr);
234 DOBLOCK(h1, k1);
235 }
236 break;
237 case 1: /* c=[0---] w=[4321] b=[3210]=c>>24|w<<8 c'=[4---] */
238 for (; ptr < end; ptr += 4)
239 {
240 uint32_t k1 = c >> 24;
241 c = READ_UINT32(ptr);
242 k1 |= c << 8;
243 DOBLOCK(h1, k1);
244 }
245 break;
246 case 2: /* c=[10--] w=[5432] b=[3210]=c>>16|w<<16 c'=[54--] */
247 for (; ptr < end; ptr += 4)
248 {
249 uint32_t k1 = c >> 16;
250 c = READ_UINT32(ptr);
251 k1 |= c << 16;
252 DOBLOCK(h1, k1);
253 }
254 break;
255 case 3: /* c=[210-] w=[6543] b=[3210]=c>>8|w<<24 c'=[654-] */
256 for (; ptr < end; ptr += 4)
257 {
258 uint32_t k1 = c >> 8;
259 c = READ_UINT32(ptr);
260 k1 |= c << 24;
261 DOBLOCK(h1, k1);
262 }
263 }
264 #endif /*UNALIGNED_SAFE*/
265
266 /* Advance over whole 32-bit chunks, possibly leaving 1..3 bytes */
267 len -= len / 4 * 4;
268
269 /* Append any remaining bytes into carry */
270 DOBYTES(len, h1, c, n, ptr, len);
271
272 /* Copy out new running hash and carry */
273 *ph1 = h1;
274 *pcarry = (c & ~0xff) | n;
275 }
276
277 /*---------------------------------------------------------------------------*/
278
279 /* Finalize a hash. To match the original Murmur3A the total_length must be provided */
PMurHash32_Result(uint32_t h,uint32_t carry,uint32_t total_length)280 uint32_t PMurHash32_Result(uint32_t h, uint32_t carry, uint32_t total_length)
281 {
282 uint32_t k1;
283 int n = carry & 3;
284 if (n)
285 {
286 k1 = carry >> (4 - n) * 8;
287 k1 *= C1;
288 k1 = ROTL32(k1, 15);
289 k1 *= C2;
290 h ^= k1;
291 }
292 h ^= total_length;
293
294 /* fmix */
295 h ^= h >> 16;
296 h *= 0x85ebca6b;
297 h ^= h >> 13;
298 h *= 0xc2b2ae35;
299 h ^= h >> 16;
300
301 return h;
302 }
303
304 /*---------------------------------------------------------------------------*/
305
306 /* Murmur3A compatable all-at-once */
PMurHash32(uint32_t seed,const void * key,int len)307 uint32_t PMurHash32(uint32_t seed, const void *key, int len)
308 {
309 uint32_t h1 = seed, carry = 0;
310 PMurHash32_Process(&h1, &carry, key, len);
311 return PMurHash32_Result(h1, carry, len);
312 }
313
314 /*---------------------------------------------------------------------------*/
315
316 /* Provide an API suitable for smhasher */
PMurHash32_test(const void * key,int len,uint32_t seed,void * out)317 void PMurHash32_test(const void *key, int len, uint32_t seed, void *out)
318 {
319 uint32_t h1 = seed, carry = 0;
320 const uint8_t *ptr = (uint8_t *)key;
321 const uint8_t *end = ptr + len;
322
323 #if 0 /* Exercise the progressive processing */
324 while(ptr < end) {
325 //const uint8_t *mid = ptr + rand()%(end-ptr)+1;
326 const uint8_t *mid = ptr + (rand()&0xF);
327 mid = mid<end?mid:end;
328 PMurHash32_Process(&h1, &carry, ptr, mid-ptr);
329 ptr = mid;
330 }
331 #else
332 PMurHash32_Process(&h1, &carry, ptr, (int)(end - ptr));
333 #endif
334 h1 = PMurHash32_Result(h1, carry, len);
335 *(uint32_t *)out = h1;
336 }
337 } // namespace angle
338
339 /*---------------------------------------------------------------------------*/
340