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)
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions are
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
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.
29 You can contact the author at :
30 - xxHash source repository : http://code.google.com/p/xxhash/
35 #include "archive_platform.h"
36 #include "archive_xxhash.h"
40 /***************************************
42 ****************************************/
43 /* Unaligned memory access is automatically enabled for "common" CPU, such as x86.
44 ** For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected.
45 ** If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance.
46 ** You can also enable this parameter if you know your input data will always be aligned (boundaries of 4, for U32).
48 #if defined(__ARM_FEATURE_UNALIGNED) || defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
49 # define XXH_USE_UNALIGNED_ACCESS 1
52 /* XXH_ACCEPT_NULL_INPUT_POINTER :
53 ** If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer.
54 ** When this option is enabled, xxHash output for null input pointers will be the same as a null-length input.
55 ** This option has a very small performance cost (only measurable on small inputs).
56 ** By default, this option is disabled. To enable it, uncomment below define :
57 ** #define XXH_ACCEPT_NULL_INPUT_POINTER 1
59 ** XXH_FORCE_NATIVE_FORMAT :
60 ** By default, xxHash library provides endian-independant Hash values, based on little-endian convention.
61 ** Results are therefore identical for little-endian and big-endian CPU.
62 ** This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format.
63 ** Should endian-independance be of no importance for your application, you may set the #define below to 1.
64 ** It will improve speed for Big-endian CPU.
65 ** This option has no impact on Little_Endian CPU.
67 #define XXH_FORCE_NATIVE_FORMAT 0
69 /***************************************
70 ** Compiler Specific Options
71 ****************************************/
72 /* Disable some Visual warning messages */
73 #ifdef _MSC_VER /* Visual Studio */
74 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
77 #ifdef _MSC_VER /* Visual Studio */
78 # define FORCE_INLINE __forceinline
81 # define FORCE_INLINE inline __attribute__((always_inline))
83 # define FORCE_INLINE inline
87 /***************************************
88 ** Includes & Memory related functions
89 ****************************************/
90 #define XXH_malloc malloc
92 #define XXH_memcpy memcpy
95 static unsigned int XXH32 (const void*, unsigned int, unsigned int);
96 static void* XXH32_init (unsigned int);
97 static XXH_errorcode XXH32_update (void*, const void*, unsigned int);
98 static unsigned int XXH32_digest (void*);
99 /*static int XXH32_sizeofState(void);*/
100 static XXH_errorcode XXH32_resetState(void*, unsigned int);
101 #define XXH32_SIZEOFSTATE 48
102 typedef struct { long long ll[(XXH32_SIZEOFSTATE+(sizeof(long long)-1))/sizeof(long long)]; } XXH32_stateSpace_t;
103 static unsigned int XXH32_intermediateDigest (void*);
105 /***************************************
107 ****************************************/
108 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
110 typedef uint8_t BYTE;
111 typedef uint16_t U16;
112 typedef uint32_t U32;
114 typedef uint64_t U64;
116 typedef unsigned char BYTE;
117 typedef unsigned short U16;
118 typedef unsigned int U32;
119 typedef signed int S32;
120 typedef unsigned long long U64;
123 #if defined(__GNUC__) && !defined(XXH_USE_UNALIGNED_ACCESS)
124 # define _PACKED __attribute__ ((packed))
129 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
133 # pragma pack(push, 1)
137 typedef struct _U32_S { U32 v; } _PACKED U32_S;
139 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
143 #define A32(x) (((const U32_S *)(x))->v)
146 /****************************************
147 ** Compiler-specific Functions and Macros
148 *****************************************/
149 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
151 /* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */
152 #if defined(_MSC_VER)
153 # define XXH_rotl32(x,r) _rotl(x,r)
155 # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
158 #if defined(_MSC_VER) /* Visual Studio */
159 # define XXH_swap32 _byteswap_ulong
160 #elif GCC_VERSION >= 403
161 # define XXH_swap32 __builtin_bswap32
163 static inline U32 XXH_swap32 (U32 x) {
164 return ((x << 24) & 0xff000000 ) |
165 ((x << 8) & 0x00ff0000 ) |
166 ((x >> 8) & 0x0000ff00 ) |
167 ((x >> 24) & 0x000000ff );}
171 /***************************************
173 ****************************************/
174 #define PRIME32_1 2654435761U
175 #define PRIME32_2 2246822519U
176 #define PRIME32_3 3266489917U
177 #define PRIME32_4 668265263U
178 #define PRIME32_5 374761393U
181 /***************************************
182 ** Architecture Macros
183 ****************************************/
184 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess;
185 #ifndef XXH_CPU_LITTLE_ENDIAN /* It is possible to define XXH_CPU_LITTLE_ENDIAN externally, for example using a compiler switch */
186 static const int one = 1;
187 # define XXH_CPU_LITTLE_ENDIAN (*(const char*)(&one))
191 /***************************************
193 ****************************************/
194 #define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(!!(c)) }; } /* use only *after* variable declarations */
197 /*****************************
199 ******************************/
200 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
203 FORCE_INLINE U32 XXH_readLE32_align(const U32* ptr, XXH_endianess endian, XXH_alignment align)
205 if (align==XXH_unaligned)
206 return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr));
208 return endian==XXH_littleEndian ? *ptr : XXH_swap32(*ptr);
212 FORCE_INLINE U32 XXH_readLE32(const U32* ptr, XXH_endianess endian) { return XXH_readLE32_align(ptr, endian, XXH_unaligned); }
215 /*****************************
216 ** Simple Hash Functions
217 ******************************/
219 FORCE_INLINE U32 XXH32_endian_align(const void* input, unsigned int len, U32 seed, XXH_endianess endian, XXH_alignment align)
221 const BYTE* p = (const BYTE*)input;
222 const BYTE* bEnd = p + len;
224 #define XXH_get32bits(p) XXH_readLE32_align((const U32*)p, endian, align)
226 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
227 if (p==NULL) { len=0; bEnd=p=(const BYTE*)(size_t)16; }
232 const BYTE* const limit = bEnd - 16;
233 U32 v1 = seed + PRIME32_1 + PRIME32_2;
234 U32 v2 = seed + PRIME32_2;
236 U32 v4 = seed - PRIME32_1;
240 v1 += XXH_get32bits(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
241 v2 += XXH_get32bits(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
242 v3 += XXH_get32bits(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
243 v4 += XXH_get32bits(p) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
246 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
250 h32 = seed + PRIME32_5;
257 h32 += XXH_get32bits(p) * PRIME32_3;
258 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
264 h32 += (*p) * PRIME32_5;
265 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
279 U32 XXH32(const void* input, unsigned int len, U32 seed)
282 // Simple version, good for code maintenance, but unfortunately slow for small inputs
283 void* state = XXH32_init(seed);
284 XXH32_update(state, input, len);
285 return XXH32_digest(state);
287 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
289 # if !defined(XXH_USE_UNALIGNED_ACCESS)
290 if ((((size_t)input) & 3) == 0) /* Input is aligned, let's leverage the speed advantage */
292 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
293 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
295 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
299 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
300 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
302 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
306 /*****************************
307 ** Advanced Hash Functions
308 ******************************/
324 int XXH32_sizeofState(void)
326 XXH_STATIC_ASSERT(XXH32_SIZEOFSTATE >= sizeof(struct XXH_state32_t)); /* A compilation error here means XXH32_SIZEOFSTATE is not large enough */
327 return sizeof(struct XXH_state32_t);
332 XXH_errorcode XXH32_resetState(void* state_in, U32 seed)
334 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
336 state->v1 = seed + PRIME32_1 + PRIME32_2;
337 state->v2 = seed + PRIME32_2;
338 state->v3 = seed + 0;
339 state->v4 = seed - PRIME32_1;
340 state->total_len = 0;
346 void* XXH32_init (U32 seed)
348 void* state = XXH_malloc (sizeof(struct XXH_state32_t));
349 XXH32_resetState(state, seed);
354 FORCE_INLINE XXH_errorcode XXH32_update_endian (void* state_in, const void* input, int len, XXH_endianess endian)
356 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
357 const BYTE* p = (const BYTE*)input;
358 const BYTE* const bEnd = p + len;
360 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
361 if (input==NULL) return XXH_ERROR;
364 state->total_len += len;
366 if (state->memsize + len < 16) /* fill in tmp buffer */
368 XXH_memcpy(state->memory + state->memsize, input, len);
369 state->memsize += len;
373 if (state->memsize) /* some data left from previous update */
375 XXH_memcpy(state->memory + state->memsize, input, 16-state->memsize);
377 const U32* p32 = (const U32*)state->memory;
378 state->v1 += XXH_readLE32(p32, endian) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++;
379 state->v2 += XXH_readLE32(p32, endian) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++;
380 state->v3 += XXH_readLE32(p32, endian) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++;
381 state->v4 += XXH_readLE32(p32, endian) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++;
383 p += 16-state->memsize;
389 const BYTE* const limit = bEnd - 16;
397 v1 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
398 v2 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
399 v3 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
400 v4 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
411 XXH_memcpy(state->memory, p, bEnd-p);
412 state->memsize = (int)(bEnd-p);
419 XXH_errorcode XXH32_update (void* state_in, const void* input, unsigned int len)
421 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
423 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
424 return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
426 return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
432 FORCE_INLINE U32 XXH32_intermediateDigest_endian (void* state_in, XXH_endianess endian)
434 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
435 const BYTE * p = (const BYTE*)state->memory;
436 BYTE* bEnd = (BYTE*)state->memory + state->memsize;
439 if (state->total_len >= 16)
441 h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
445 h32 = state->seed + PRIME32_5;
448 h32 += (U32) state->total_len;
452 h32 += XXH_readLE32((const U32*)p, endian) * PRIME32_3;
453 h32 = XXH_rotl32(h32, 17) * PRIME32_4;
459 h32 += (*p) * PRIME32_5;
460 h32 = XXH_rotl32(h32, 11) * PRIME32_1;
474 U32 XXH32_intermediateDigest (void* state_in)
476 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
478 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
479 return XXH32_intermediateDigest_endian(state_in, XXH_littleEndian);
481 return XXH32_intermediateDigest_endian(state_in, XXH_bigEndian);
485 U32 XXH32_digest (void* state_in)
487 U32 h32 = XXH32_intermediateDigest(state_in);
495 struct archive_xxhash __archive_xxhash = {
504 * Define an empty version of the struct if we aren't using the LZ4 library.
507 struct archive_xxhash __archive_xxhash = {
514 #endif /* HAVE_LIBLZ4 */