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
51 #include "PMurHash.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 || defined(_LITTLE_ENDIAN) && _LITTLE_ENDIAN==1
95 #define __BYTE_ORDER __LITTLE_ENDIAN
96 #elif defined(__BIG_ENDIAN__) && __BIG_ENDIAN__==1 || defined(_BIG_ENDIAN) && _BIG_ENDIAN==1
97 #define __BYTE_ORDER __BIG_ENDIAN
98 #endif
99 #endif
100
101 /* gcc (usually) defines xEL/EB macros for ARM and MIPS endianess */
102 #if !defined(__BYTE_ORDER)
103 #if defined(__ARMEL__) || defined(__MIPSEL__)
104 #define __BYTE_ORDER __LITTLE_ENDIAN
105 #endif
106 #if defined(__ARMEB__) || defined(__MIPSEB__)
107 #define __BYTE_ORDER __BIG_ENDIAN
108 #endif
109 #endif
110
111 /* Now find best way we can to READ_UINT32 */
112 #if __BYTE_ORDER==__LITTLE_ENDIAN
113 /* CPU endian matches murmurhash algorithm, so read 32-bit word directly */
114 #define READ_UINT32(ptr) (*((uint32_t*)(ptr)))
115 #elif __BYTE_ORDER==__BIG_ENDIAN
116 /* TODO: Add additional cases below where a compiler provided bswap32 is available */
117 #if defined(__GNUC__) && (__GNUC__>4 || (__GNUC__==4 && __GNUC_MINOR__>=3))
118 #define READ_UINT32(ptr) (__builtin_bswap32(*((uint32_t*)(ptr))))
119 #else
120 /* Without a known fast bswap32 we're just as well off doing this */
121 #define READ_UINT32(ptr) (ptr[0]|ptr[1]<<8|ptr[2]<<16|ptr[3]<<24)
122 #define UNALIGNED_SAFE
123 #endif
124 #else
125 /* Unknown endianess so last resort is to read individual bytes */
126 #define READ_UINT32(ptr) (ptr[0]|ptr[1]<<8|ptr[2]<<16|ptr[3]<<24)
127
128 /* Since we're not doing word-reads we can skip the messing about with realignment */
129 #define UNALIGNED_SAFE
130 #endif
131
132 /* Find best way to ROTL32 */
133 #if defined(_MSC_VER)
134 #include <stdlib.h> /* Microsoft put _rotl declaration in here */
135 #define ROTL32(x,r) _rotl(x,r)
136 #else
137 /* gcc recognises this code and generates a rotate instruction for CPUs with one */
138 #define ROTL32(x,r) (((uint32_t)x << r) | ((uint32_t)x >> (32 - r)))
139 #endif
140
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) do{ \
151 k1 *= C1; \
152 k1 = ROTL32(k1,15); \
153 k1 *= C2; \
154 \
155 h1 ^= k1; \
156 h1 = ROTL32(h1,13); \
157 h1 = h1*5+0xe6546b64; \
158 }while(0)
159
160
161 /* Append unaligned bytes to carry, forcing hash churn if we have 4 bytes */
162 /* cnt=bytes to process, h1=name of h1 var, c=carry, n=bytes in c, ptr/len=payload */
163 #define DOBYTES(cnt, h1, c, n, ptr, len) do{ \
164 int _i = cnt; \
165 while(_i--) { \
166 c = c>>8 | *ptr++<<24; \
167 n++; len--; \
168 if(n==4) { \
169 DOBLOCK(h1, c); \
170 n = 0; \
171 } \
172 } }while(0)
173
174 /*---------------------------------------------------------------------------*/
175
176 /* Main hashing function. Initialise carry to 0 and h1 to 0 or an initial seed
177 * if wanted. Both ph1 and pcarry are required arguments. */
PMurHash32_Process(uint32_t * ph1,uint32_t * pcarry,const void * key,int len)178 void PMurHash32_Process(uint32_t *ph1, uint32_t *pcarry, const void *key, int len)
179 {
180 uint32_t h1 = *ph1;
181 uint32_t c = *pcarry;
182
183 const uint8_t *ptr = (uint8_t*)key;
184 const uint8_t *end;
185
186 /* Extract carry count from low 2 bits of c value */
187 int n = c & 3;
188
189 #if defined(UNALIGNED_SAFE)
190 /* This CPU handles unaligned word access */
191
192 /* Consume any carry bytes */
193 int i = (4-n) & 3;
194 if(i && i <= len) {
195 DOBYTES(i, h1, c, n, ptr, len);
196 }
197
198 /* Process 32-bit chunks */
199 end = ptr + len/4*4;
200 for( ; ptr < end ; ptr+=4) {
201 uint32_t k1 = READ_UINT32(ptr);
202 DOBLOCK(h1, k1);
203 }
204
205 #else /*UNALIGNED_SAFE*/
206 /* This CPU does not handle unaligned word access */
207
208 /* Consume enough so that the next data byte is word aligned */
209 int i = -(long)ptr & 3;
210 if(i && i <= len) {
211 DOBYTES(i, h1, c, n, ptr, len);
212 }
213
214 /* We're now aligned. Process in aligned blocks. Specialise for each possible carry count */
215 end = ptr + len/4*4;
216 switch(n) { /* how many bytes in c */
217 case 0: /* c=[----] w=[3210] b=[3210]=w c'=[----] */
218 for( ; ptr < end ; ptr+=4) {
219 uint32_t k1 = READ_UINT32(ptr);
220 DOBLOCK(h1, k1);
221 }
222 break;
223 case 1: /* c=[0---] w=[4321] b=[3210]=c>>24|w<<8 c'=[4---] */
224 for( ; ptr < end ; ptr+=4) {
225 uint32_t k1 = c>>24;
226 c = READ_UINT32(ptr);
227 k1 |= c<<8;
228 DOBLOCK(h1, k1);
229 }
230 break;
231 case 2: /* c=[10--] w=[5432] b=[3210]=c>>16|w<<16 c'=[54--] */
232 for( ; ptr < end ; ptr+=4) {
233 uint32_t k1 = c>>16;
234 c = READ_UINT32(ptr);
235 k1 |= c<<16;
236 DOBLOCK(h1, k1);
237 }
238 break;
239 case 3: /* c=[210-] w=[6543] b=[3210]=c>>8|w<<24 c'=[654-] */
240 for( ; ptr < end ; ptr+=4) {
241 uint32_t k1 = c>>8;
242 c = READ_UINT32(ptr);
243 k1 |= c<<24;
244 DOBLOCK(h1, k1);
245 }
246 }
247 #endif /*UNALIGNED_SAFE*/
248
249 /* Advance over whole 32-bit chunks, possibly leaving 1..3 bytes */
250 len -= len/4*4;
251
252 /* Append any remaining bytes into carry */
253 DOBYTES(len, h1, c, n, ptr, len);
254
255 /* Copy out new running hash and carry */
256 *ph1 = h1;
257 *pcarry = (c & ~0xff) | n;
258 }
259
260 /*---------------------------------------------------------------------------*/
261
262 /* 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)263 uint32_t PMurHash32_Result(uint32_t h, uint32_t carry, uint32_t total_length)
264 {
265 uint32_t k1;
266 int n = carry & 3;
267 if(n) {
268 k1 = carry >> (4-n)*8;
269 k1 *= C1; k1 = ROTL32(k1,15); k1 *= C2; h ^= k1;
270 }
271 h ^= total_length;
272
273 /* fmix */
274 h ^= h >> 16;
275 h *= 0x85ebca6b;
276 h ^= h >> 13;
277 h *= 0xc2b2ae35;
278 h ^= h >> 16;
279
280 return h;
281 }
282
283 /*---------------------------------------------------------------------------*/
284
285 /* Murmur3A compatable all-at-once */
PMurHash32(uint32_t seed,const void * key,int len)286 uint32_t PMurHash32(uint32_t seed, const void *key, int len)
287 {
288 uint32_t h1=seed, carry=0;
289 PMurHash32_Process(&h1, &carry, key, len);
290 return PMurHash32_Result(h1, carry, len);
291 }
292
293 /*---------------------------------------------------------------------------*/
294
295 /* Provide an API suitable for smhasher */
PMurHash32_test(const void * key,int len,uint32_t seed,void * out)296 void PMurHash32_test(const void *key, int len, uint32_t seed, void *out)
297 {
298 uint32_t h1=seed, carry=0;
299 const uint8_t *ptr = (uint8_t*)key;
300 const uint8_t *end = ptr + len;
301
302 #if 0 /* Exercise the progressive processing */
303 while(ptr < end) {
304 //const uint8_t *mid = ptr + rand()%(end-ptr)+1;
305 const uint8_t *mid = ptr + (rand()&0xF);
306 mid = mid<end?mid:end;
307 PMurHash32_Process(&h1, &carry, ptr, mid-ptr);
308 ptr = mid;
309 }
310 #else
311 PMurHash32_Process(&h1, &carry, ptr, (int)(end-ptr));
312 #endif
313 h1 = PMurHash32_Result(h1, carry, len);
314 *(uint32_t*)out = h1;
315 }
316
317 /*---------------------------------------------------------------------------*/
318