1/*
2xxHash - Fast Hash algorithm
3Copyright (C) 2012-2014, Yann Collet.
4BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
5
6Redistribution and use in source and binary forms, with or without
7modification, are permitted provided that the following conditions are
8met:
9
10* Redistributions of source code must retain the above copyright
11notice, this list of conditions and the following disclaimer.
12* Redistributions in binary form must reproduce the above
13copyright notice, this list of conditions and the following disclaimer
14in the documentation and/or other materials provided with the
15distribution.
16
17THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29You 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
84typedef 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
110static 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//**************************************
133typedef 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//****************************
149typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
150
151static uint32_t XXH_readLE32_align(const uint32_t* ptr, XXH_endianess endian, XXH_alignment align)
152{
153    if (align==XXH_unaligned)
154        return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr));
155    else
156        return endian==XXH_littleEndian ? *ptr : XXH_swap32(*ptr);
157}
158
159static uint32_t XXH_readLE32(const uint32_t* ptr, XXH_endianess endian) { return XXH_readLE32_align(ptr, endian, XXH_unaligned); }
160
161
162//****************************
163// Simple Hash Functions
164//****************************
165static uint32_t XXH32_endian_align(const void* input, int len, uint32_t seed, XXH_endianess endian, XXH_alignment align)
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
224uint32_t XXH32(const void* input, uint32_t len, uint32_t seed)
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
256int XXH32_sizeofState(void)
257{
258    XXH_STATIC_ASSERT(XXH32_SIZEOFSTATE >= sizeof(struct XXH_state32_t));   // A compilation error here means XXH32_SIZEOFSTATE is not large enough
259    return sizeof(struct XXH_state32_t);
260}
261
262
263XXH_errorcode XXH32_resetState(void* state_in, uint32_t seed)
264{
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
277void* 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
285static XXH_errorcode XXH32_update_endian (void* state_in, const void* input, int len, XXH_endianess endian)
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++;
310            state->v2 += XXH_readLE32(p32, endian) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++;
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
349XXH_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
361static uint32_t XXH32_intermediateDigest_endian (void* state_in, XXH_endianess endian)
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
403uint32_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
414uint32_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}
422