Commit | Line | Data |
---|---|---|
65f21d61 JA |
1 | /* |
2 | xxHash - Fast Hash algorithm | |
3 | Copyright (C) 2012-2014, Yann Collet. | |
4 | BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) | |
5 | ||
6 | Redistribution and use in source and binary forms, with or without | |
7 | modification, are permitted provided that the following conditions are | |
8 | met: | |
9 | ||
10 | * Redistributions of source code must retain the above copyright | |
11 | notice, this list of conditions and the following disclaimer. | |
12 | * Redistributions in binary form must reproduce the above | |
13 | copyright notice, this list of conditions and the following disclaimer | |
14 | in the documentation and/or other materials provided with the | |
15 | distribution. | |
16 | ||
17 | THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | |
18 | "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | |
19 | LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | |
20 | A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | |
21 | OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | |
22 | SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | |
23 | LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | |
24 | DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | |
25 | THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | |
26 | (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | |
27 | OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | |
28 | ||
29 | You can contact the author at : | |
30 | - xxHash source repository : http://code.google.com/p/xxhash/ | |
31 | */ | |
32 | ||
33 | ||
34 | //************************************** | |
35 | // Tuning parameters | |
36 | //************************************** | |
37 | // Unaligned memory access is automatically enabled for "common" CPU, such as x86. | |
38 | // For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected. | |
39 | // If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance. | |
40 | // You can also enable this parameter if you know your input data will always be aligned (boundaries of 4, for uint32_t). | |
41 | #if defined(__ARM_FEATURE_UNALIGNED) || defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64) | |
42 | # define XXH_USE_UNALIGNED_ACCESS 1 | |
43 | #endif | |
44 | ||
45 | // XXH_ACCEPT_NULL_INPUT_POINTER : | |
46 | // If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer. | |
47 | // When this option is enabled, xxHash output for null input pointers will be the same as a null-length input. | |
48 | // This option has a very small performance cost (only measurable on small inputs). | |
49 | // By default, this option is disabled. To enable it, uncomment below define : | |
50 | //#define XXH_ACCEPT_NULL_INPUT_POINTER 1 | |
51 | ||
52 | // XXH_FORCE_NATIVE_FORMAT : | |
53 | // By default, xxHash library provides endian-independant Hash values, based on little-endian convention. | |
54 | // Results are therefore identical for little-endian and big-endian CPU. | |
55 | // This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format. | |
56 | // Should endian-independance be of no importance for your application, you may set the #define below to 1. | |
57 | // It will improve speed for Big-endian CPU. | |
58 | // This option has no impact on Little_Endian CPU. | |
59 | #define XXH_FORCE_NATIVE_FORMAT 0 | |
60 | ||
61 | ||
62 | //************************************** | |
63 | // Includes & Memory related functions | |
64 | //************************************** | |
65 | #include "xxhash.h" | |
66 | #include <stdlib.h> | |
67 | #include <string.h> | |
68 | ||
69 | ||
70 | #if defined(__GNUC__) && !defined(XXH_USE_UNALIGNED_ACCESS) | |
71 | # define _PACKED __attribute__ ((packed)) | |
72 | #else | |
73 | # define _PACKED | |
74 | #endif | |
75 | ||
76 | #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__) | |
77 | # ifdef __IBMC__ | |
78 | # pragma pack(1) | |
79 | # else | |
80 | # pragma pack(push, 1) | |
81 | # endif | |
82 | #endif | |
83 | ||
84 | typedef struct _uint32_t_S { uint32_t v; } _PACKED uint32_t_S; | |
85 | ||
86 | #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__) | |
87 | # pragma pack(pop) | |
88 | #endif | |
89 | ||
90 | #define A32(x) (((uint32_t_S *)(x))->v) | |
91 | ||
92 | ||
93 | //*************************************** | |
94 | // Compiler-specific Functions and Macros | |
95 | //*************************************** | |
96 | #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) | |
97 | ||
98 | // Note : although _rotl exists for minGW (GCC under windows), performance seems poor | |
99 | #if defined(_MSC_VER) | |
100 | # define XXH_rotl32(x,r) _rotl(x,r) | |
101 | #else | |
102 | # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r))) | |
103 | #endif | |
104 | ||
105 | #if defined(_MSC_VER) // Visual Studio | |
106 | # define XXH_swap32 _byteswap_ulong | |
107 | #elif GCC_VERSION >= 403 | |
108 | # define XXH_swap32 __builtin_bswap32 | |
109 | #else | |
110 | static inline uint32_t XXH_swap32 (uint32_t x) | |
111 | { | |
112 | return ((x << 24) & 0xff000000 ) | | |
113 | ((x << 8) & 0x00ff0000 ) | | |
114 | ((x >> 8) & 0x0000ff00 ) | | |
115 | ((x >> 24) & 0x000000ff ); | |
116 | } | |
117 | #endif | |
118 | ||
119 | ||
120 | //************************************** | |
121 | // Constants | |
122 | //************************************** | |
123 | #define PRIME32_1 2654435761U | |
124 | #define PRIME32_2 2246822519U | |
125 | #define PRIME32_3 3266489917U | |
126 | #define PRIME32_4 668265263U | |
127 | #define PRIME32_5 374761393U | |
128 | ||
129 | ||
130 | //************************************** | |
131 | // Architecture Macros | |
132 | //************************************** | |
133 | typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess; | |
134 | #ifndef XXH_CPU_LITTLE_ENDIAN // It is possible to define XXH_CPU_LITTLE_ENDIAN externally, for example using a compiler switch | |
135 | static const int one = 1; | |
136 | # define XXH_CPU_LITTLE_ENDIAN (*(char*)(&one)) | |
137 | #endif | |
138 | ||
139 | ||
140 | //************************************** | |
141 | // Macros | |
142 | //************************************** | |
143 | #define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(!!(c)) }; } // use only *after* variable declarations | |
144 | ||
145 | ||
146 | //**************************** | |
147 | // Memory reads | |
148 | //**************************** | |
149 | typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment; | |
150 | ||
10aa136b | 151 | static uint32_t XXH_readLE32_align(const uint32_t* ptr, XXH_endianess endian, XXH_alignment align) |
190b8f0c | 152 | { |
65f21d61 | 153 | if (align==XXH_unaligned) |
190b8f0c | 154 | return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr)); |
65f21d61 | 155 | else |
190b8f0c | 156 | return endian==XXH_littleEndian ? *ptr : XXH_swap32(*ptr); |
65f21d61 JA |
157 | } |
158 | ||
10aa136b | 159 | static uint32_t XXH_readLE32(const uint32_t* ptr, XXH_endianess endian) { return XXH_readLE32_align(ptr, endian, XXH_unaligned); } |
65f21d61 JA |
160 | |
161 | ||
162 | //**************************** | |
163 | // Simple Hash Functions | |
164 | //**************************** | |
10aa136b | 165 | static uint32_t XXH32_endian_align(const void* input, int len, uint32_t seed, XXH_endianess endian, XXH_alignment align) |
65f21d61 JA |
166 | { |
167 | const uint8_t *p = (const uint8_t *)input; | |
168 | const uint8_t * const bEnd = p + len; | |
169 | uint32_t h32; | |
170 | ||
171 | #ifdef XXH_ACCEPT_NULL_INPUT_POINTER | |
172 | if (p==NULL) { len=0; p=(const uint8_t *)(size_t)16; } | |
173 | #endif | |
174 | ||
175 | if (len>=16) | |
176 | { | |
177 | const uint8_t * const limit = bEnd - 16; | |
178 | uint32_t v1 = seed + PRIME32_1 + PRIME32_2; | |
179 | uint32_t v2 = seed + PRIME32_2; | |
180 | uint32_t v3 = seed + 0; | |
181 | uint32_t v4 = seed - PRIME32_1; | |
182 | ||
183 | do | |
184 | { | |
185 | v1 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4; | |
186 | v2 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4; | |
187 | v3 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4; | |
188 | v4 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4; | |
189 | } while (p<=limit); | |
190 | ||
191 | h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18); | |
192 | } | |
193 | else | |
194 | { | |
195 | h32 = seed + PRIME32_5; | |
196 | } | |
197 | ||
198 | h32 += (uint32_t) len; | |
199 | ||
200 | while (p<=bEnd-4) | |
201 | { | |
202 | h32 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_3; | |
203 | h32 = XXH_rotl32(h32, 17) * PRIME32_4 ; | |
204 | p+=4; | |
205 | } | |
206 | ||
207 | while (p<bEnd) | |
208 | { | |
209 | h32 += (*p) * PRIME32_5; | |
210 | h32 = XXH_rotl32(h32, 11) * PRIME32_1 ; | |
211 | p++; | |
212 | } | |
213 | ||
214 | h32 ^= h32 >> 15; | |
215 | h32 *= PRIME32_2; | |
216 | h32 ^= h32 >> 13; | |
217 | h32 *= PRIME32_3; | |
218 | h32 ^= h32 >> 16; | |
219 | ||
220 | return h32; | |
221 | } | |
222 | ||
223 | ||
899834b5 | 224 | uint32_t XXH32(const void* input, uint32_t len, uint32_t seed) |
65f21d61 JA |
225 | { |
226 | #if 0 | |
227 | // Simple version, good for code maintenance, but unfortunately slow for small inputs | |
228 | void* state = XXH32_init(seed); | |
229 | XXH32_update(state, input, len); | |
230 | return XXH32_digest(state); | |
231 | #else | |
232 | XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; | |
233 | ||
234 | # if !defined(XXH_USE_UNALIGNED_ACCESS) | |
235 | if ((((size_t)input) & 3)) // Input is aligned, let's leverage the speed advantage | |
236 | { | |
237 | if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) | |
238 | return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); | |
239 | else | |
240 | return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); | |
241 | } | |
242 | # endif | |
243 | ||
244 | if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) | |
245 | return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned); | |
246 | else | |
247 | return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); | |
248 | #endif | |
249 | } | |
250 | ||
251 | ||
252 | //**************************** | |
253 | // Advanced Hash Functions | |
254 | //**************************** | |
255 | ||
190b8f0c | 256 | int XXH32_sizeofState(void) |
65f21d61 JA |
257 | { |
258 | XXH_STATIC_ASSERT(XXH32_SIZEOFSTATE >= sizeof(struct XXH_state32_t)); // A compilation error here means XXH32_SIZEOFSTATE is not large enough | |
190b8f0c | 259 | return sizeof(struct XXH_state32_t); |
65f21d61 JA |
260 | } |
261 | ||
262 | ||
263 | XXH_errorcode XXH32_resetState(void* state_in, uint32_t seed) | |
190b8f0c | 264 | { |
65f21d61 JA |
265 | struct XXH_state32_t * state = (struct XXH_state32_t *) state_in; |
266 | state->seed = seed; | |
267 | state->v1 = seed + PRIME32_1 + PRIME32_2; | |
268 | state->v2 = seed + PRIME32_2; | |
269 | state->v3 = seed + 0; | |
270 | state->v4 = seed - PRIME32_1; | |
271 | state->total_len = 0; | |
272 | state->memsize = 0; | |
273 | return XXH_OK; | |
274 | } | |
275 | ||
276 | ||
277 | void* XXH32_init (uint32_t seed) | |
278 | { | |
279 | void *state = malloc (sizeof(struct XXH_state32_t)); | |
280 | XXH32_resetState(state, seed); | |
281 | return state; | |
282 | } | |
283 | ||
284 | ||
10aa136b | 285 | static XXH_errorcode XXH32_update_endian (void* state_in, const void* input, int len, XXH_endianess endian) |
65f21d61 JA |
286 | { |
287 | struct XXH_state32_t * state = (struct XXH_state32_t *) state_in; | |
288 | const uint8_t *p = (const uint8_t *)input; | |
289 | const uint8_t * const bEnd = p + len; | |
290 | ||
291 | #ifdef XXH_ACCEPT_NULL_INPUT_POINTER | |
292 | if (input==NULL) return XXH_ERROR; | |
293 | #endif | |
294 | ||
295 | state->total_len += len; | |
296 | ||
297 | if (state->memsize + len < 16) // fill in tmp buffer | |
298 | { | |
299 | memcpy(state->memory + state->memsize, input, len); | |
300 | state->memsize += len; | |
301 | return XXH_OK; | |
302 | } | |
303 | ||
304 | if (state->memsize) // some data left from previous update | |
305 | { | |
306 | memcpy(state->memory + state->memsize, input, 16-state->memsize); | |
307 | { | |
308 | const uint32_t* p32 = (const uint32_t*)state->memory; | |
309 | state->v1 += XXH_readLE32(p32, endian) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++; | |
190b8f0c | 310 | state->v2 += XXH_readLE32(p32, endian) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++; |
65f21d61 JA |
311 | state->v3 += XXH_readLE32(p32, endian) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++; |
312 | state->v4 += XXH_readLE32(p32, endian) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++; | |
313 | } | |
314 | p += 16-state->memsize; | |
315 | state->memsize = 0; | |
316 | } | |
317 | ||
318 | if (p <= bEnd-16) | |
319 | { | |
320 | const uint8_t * const limit = bEnd - 16; | |
321 | uint32_t v1 = state->v1; | |
322 | uint32_t v2 = state->v2; | |
323 | uint32_t v3 = state->v3; | |
324 | uint32_t v4 = state->v4; | |
325 | ||
326 | do | |
327 | { | |
328 | v1 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4; | |
329 | v2 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4; | |
330 | v3 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4; | |
331 | v4 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4; | |
332 | } while (p<=limit); | |
333 | ||
334 | state->v1 = v1; | |
335 | state->v2 = v2; | |
336 | state->v3 = v3; | |
337 | state->v4 = v4; | |
338 | } | |
339 | ||
340 | if (p < bEnd) | |
341 | { | |
342 | memcpy(state->memory, p, bEnd-p); | |
343 | state->memsize = (int)(bEnd-p); | |
344 | } | |
345 | ||
346 | return XXH_OK; | |
347 | } | |
348 | ||
349 | XXH_errorcode XXH32_update (void* state_in, const void* input, int len) | |
350 | { | |
351 | XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; | |
352 | ||
353 | if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) | |
354 | return XXH32_update_endian(state_in, input, len, XXH_littleEndian); | |
355 | else | |
356 | return XXH32_update_endian(state_in, input, len, XXH_bigEndian); | |
357 | } | |
358 | ||
359 | ||
360 | ||
10aa136b | 361 | static uint32_t XXH32_intermediateDigest_endian (void* state_in, XXH_endianess endian) |
65f21d61 JA |
362 | { |
363 | struct XXH_state32_t * state = (struct XXH_state32_t *) state_in; | |
364 | const uint8_t *p = (const uint8_t *)state->memory; | |
365 | uint8_t * bEnd = (uint8_t *)state->memory + state->memsize; | |
366 | uint32_t h32; | |
367 | ||
368 | if (state->total_len >= 16) | |
369 | { | |
370 | h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18); | |
371 | } | |
372 | else | |
373 | { | |
374 | h32 = state->seed + PRIME32_5; | |
375 | } | |
376 | ||
377 | h32 += (uint32_t) state->total_len; | |
378 | ||
379 | while (p<=bEnd-4) | |
380 | { | |
381 | h32 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_3; | |
382 | h32 = XXH_rotl32(h32, 17) * PRIME32_4; | |
383 | p+=4; | |
384 | } | |
385 | ||
386 | while (p<bEnd) | |
387 | { | |
388 | h32 += (*p) * PRIME32_5; | |
389 | h32 = XXH_rotl32(h32, 11) * PRIME32_1; | |
390 | p++; | |
391 | } | |
392 | ||
393 | h32 ^= h32 >> 15; | |
394 | h32 *= PRIME32_2; | |
395 | h32 ^= h32 >> 13; | |
396 | h32 *= PRIME32_3; | |
397 | h32 ^= h32 >> 16; | |
398 | ||
399 | return h32; | |
400 | } | |
401 | ||
402 | ||
403 | uint32_t XXH32_intermediateDigest (void* state_in) | |
404 | { | |
405 | XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; | |
406 | ||
407 | if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) | |
408 | return XXH32_intermediateDigest_endian(state_in, XXH_littleEndian); | |
409 | else | |
410 | return XXH32_intermediateDigest_endian(state_in, XXH_bigEndian); | |
411 | } | |
412 | ||
413 | ||
414 | uint32_t XXH32_digest (void* state_in) | |
415 | { | |
416 | uint32_t h32 = XXH32_intermediateDigest(state_in); | |
417 | ||
418 | free(state_in); | |
419 | ||
420 | return h32; | |
421 | } |