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 #include "archive_platform.h"
33
34 #include <stdlib.h>
35 #include <string.h>
36
37 #include "archive_xxhash.h"
38
39 #ifdef HAVE_LIBLZ4
40
41 /***************************************
42 ** Tuning parameters
43 ****************************************/
44 /* Unaligned memory access is automatically enabled for "common" CPU, such as x86.
45 ** For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected.
46 ** If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance.
47 ** You can also enable this parameter if you know your input data will always be aligned (boundaries of 4, for U32).
48 */
49 #if defined(__ARM_FEATURE_UNALIGNED) || defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
50 # define XXH_USE_UNALIGNED_ACCESS 1
51 #endif
52
53 /* XXH_ACCEPT_NULL_INPUT_POINTER :
54 ** If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer.
55 ** When this option is enabled, xxHash output for null input pointers will be the same as a null-length input.
56 ** This option has a very small performance cost (only measurable on small inputs).
57 ** By default, this option is disabled. To enable it, uncomment below define :
58 ** #define XXH_ACCEPT_NULL_INPUT_POINTER 1
59
60 ** XXH_FORCE_NATIVE_FORMAT :
61 ** By default, xxHash library provides endian-independent Hash values, based on little-endian convention.
62 ** Results are therefore identical for little-endian and big-endian CPU.
63 ** This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format.
64 ** Should endian-independence be of no importance for your application, you may set the #define below to 1.
65 ** It will improve speed for Big-endian CPU.
66 ** This option has no impact on Little_Endian CPU.
67 */
68 #define XXH_FORCE_NATIVE_FORMAT 0
69
70 /***************************************
71 ** Compiler Specific Options
72 ****************************************/
73 /* Disable some Visual warning messages */
74 #ifdef _MSC_VER /* Visual Studio */
75 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
76 #endif
77
78 #ifdef _MSC_VER /* Visual Studio */
79 # define FORCE_INLINE __forceinline
80 #else
81 # ifdef __GNUC__
82 # define FORCE_INLINE inline __attribute__((always_inline))
83 # else
84 # define FORCE_INLINE inline
85 # endif
86 #endif
87
88 /***************************************
89 ** Includes & Memory related functions
90 ****************************************/
91 #define XXH_malloc malloc
92 #define XXH_free free
93 #define XXH_memcpy memcpy
94
95
96 static unsigned int XXH32 (const void*, unsigned int, unsigned int);
97 static void* XXH32_init (unsigned int);
98 static XXH_errorcode XXH32_update (void*, const void*, unsigned int);
99 static unsigned int XXH32_digest (void*);
100 /*static int XXH32_sizeofState(void);*/
101 static XXH_errorcode XXH32_resetState(void*, unsigned int);
102 #define XXH32_SIZEOFSTATE 48
103 typedef struct { long long ll[(XXH32_SIZEOFSTATE+(sizeof(long long)-1))/sizeof(long long)]; } XXH32_stateSpace_t;
104 static unsigned int XXH32_intermediateDigest (void*);
105
106 /***************************************
107 ** Basic Types
108 ****************************************/
109 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
110 # include <stdint.h>
111 typedef uint8_t BYTE;
112 typedef uint16_t U16;
113 typedef uint32_t U32;
114 typedef int32_t S32;
115 typedef uint64_t U64;
116 #else
117 typedef unsigned char BYTE;
118 typedef unsigned short U16;
119 typedef unsigned int U32;
120 typedef signed int S32;
121 typedef unsigned long long U64;
122 #endif
123
124 #if defined(__GNUC__) && !defined(XXH_USE_UNALIGNED_ACCESS)
125 # define _PACKED __attribute__ ((packed))
126 #else
127 # define _PACKED
128 #endif
129
130 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
131 # ifdef __IBMC__
132 # pragma pack(1)
133 # else
134 # pragma pack(push, 1)
135 # endif
136 #endif
137
138 typedef struct _U32_S { U32 v; } _PACKED U32_S;
139
140 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
141 # pragma pack(pop)
142 #endif
143
144
145 /****************************************
146 ** Compiler-specific Functions and Macros
147 *****************************************/
148 #define GCC_VERSION ((__GNUC__-0) * 100 + (__GNUC_MINOR__ - 0))
149
150 #if GCC_VERSION >= 409
151 __attribute__((__no_sanitize_undefined__))
152 #endif
A32(const void * x)153 static inline U32 A32(const void * x)
154 {
155 return (((const U32_S *)(x))->v);
156 }
157
158 /* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */
159 #if defined(_MSC_VER)
160 # define XXH_rotl32(x,r) _rotl(x,r)
161 #else
162 # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
163 #endif
164
165 #if defined(_MSC_VER) /* Visual Studio */
166 # define XXH_swap32 _byteswap_ulong
167 #elif GCC_VERSION >= 403
168 # define XXH_swap32 __builtin_bswap32
169 #else
XXH_swap32(U32 x)170 static inline U32 XXH_swap32 (U32 x) {
171 return ((x << 24) & 0xff000000 ) |
172 ((x << 8) & 0x00ff0000 ) |
173 ((x >> 8) & 0x0000ff00 ) |
174 ((x >> 24) & 0x000000ff );}
175 #endif
176
177
178 /***************************************
179 ** Constants
180 ****************************************/
181 #define PRIME32_1 2654435761U
182 #define PRIME32_2 2246822519U
183 #define PRIME32_3 3266489917U
184 #define PRIME32_4 668265263U
185 #define PRIME32_5 374761393U
186
187
188 /***************************************
189 ** Architecture Macros
190 ****************************************/
191 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess;
192 #ifndef XXH_CPU_LITTLE_ENDIAN /* It is possible to define XXH_CPU_LITTLE_ENDIAN externally, for example using a compiler switch */
193 static const int one = 1;
194 # define XXH_CPU_LITTLE_ENDIAN (*(const char*)(&one))
195 #endif
196
197
198 /***************************************
199 ** Macros
200 ****************************************/
201 #define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(!!(c)) }; } /* use only *after* variable declarations */
202
203
204 /*****************************
205 ** Memory reads
206 ******************************/
207 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
208
209 static
XXH_readLE32_align(const U32 * ptr,XXH_endianess endian,XXH_alignment align)210 FORCE_INLINE U32 XXH_readLE32_align(const U32* ptr, XXH_endianess endian, XXH_alignment align)
211 {
212 if (align==XXH_unaligned)
213 return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr));
214 else
215 return endian==XXH_littleEndian ? *ptr : XXH_swap32(*ptr);
216 }
217
218 static
XXH_readLE32(const U32 * ptr,XXH_endianess endian)219 FORCE_INLINE U32 XXH_readLE32(const U32* ptr, XXH_endianess endian) { return XXH_readLE32_align(ptr, endian, XXH_unaligned); }
220
221
222 /*****************************
223 ** Simple Hash Functions
224 ******************************/
225 static
XXH32_endian_align(const void * input,unsigned int len,U32 seed,XXH_endianess endian,XXH_alignment align)226 FORCE_INLINE U32 XXH32_endian_align(const void* input, unsigned int len, U32 seed, XXH_endianess endian, XXH_alignment align)
227 {
228 const BYTE* p = (const BYTE*)input;
229 const BYTE* bEnd = p + len;
230 U32 h32;
231 #define XXH_get32bits(p) XXH_readLE32_align((const U32*)p, endian, align)
232
233 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
234 if (p==NULL) { len=0; bEnd=p=(const BYTE*)(size_t)16; }
235 #endif
236
237 if (len>=16)
238 {
239 const BYTE* const limit = bEnd - 16;
240 U32 v1 = seed + PRIME32_1 + PRIME32_2;
241 U32 v2 = seed + PRIME32_2;
242 U32 v3 = seed + 0;
243 U32 v4 = seed - PRIME32_1;
244
245 do
246 {
247 v1 += XXH_get32bits(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
248 v2 += XXH_get32bits(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
249 v3 += XXH_get32bits(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
250 v4 += XXH_get32bits(p) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
251 } while (p<=limit);
252
253 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
254 }
255 else
256 {
257 h32 = seed + PRIME32_5;
258 }
259
260 h32 += (U32) len;
261
262 while (p<=bEnd-4)
263 {
264 h32 += XXH_get32bits(p) * PRIME32_3;
265 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
266 p+=4;
267 }
268
269 while (p<bEnd)
270 {
271 h32 += (*p) * PRIME32_5;
272 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
273 p++;
274 }
275
276 h32 ^= h32 >> 15;
277 h32 *= PRIME32_2;
278 h32 ^= h32 >> 13;
279 h32 *= PRIME32_3;
280 h32 ^= h32 >> 16;
281
282 return h32;
283 }
284
285
XXH32(const void * input,unsigned int len,U32 seed)286 U32 XXH32(const void* input, unsigned int len, U32 seed)
287 {
288 #if 0
289 // Simple version, good for code maintenance, but unfortunately slow for small inputs
290 void* state = XXH32_init(seed);
291 XXH32_update(state, input, len);
292 return XXH32_digest(state);
293 #else
294 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
295
296 # if !defined(XXH_USE_UNALIGNED_ACCESS)
297 if ((((size_t)input) & 3) == 0) /* Input is aligned, let's leverage the speed advantage */
298 {
299 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
300 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
301 else
302 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
303 }
304 # endif
305
306 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
307 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
308 else
309 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
310 #endif
311 }
312
313 /*****************************
314 ** Advanced Hash Functions
315 ******************************/
316
317 struct XXH_state32_t
318 {
319 U64 total_len;
320 U32 seed;
321 U32 v1;
322 U32 v2;
323 U32 v3;
324 U32 v4;
325 int memsize;
326 char memory[16];
327 };
328
329 #if 0
330 static
331 int XXH32_sizeofState(void)
332 {
333 XXH_STATIC_ASSERT(XXH32_SIZEOFSTATE >= sizeof(struct XXH_state32_t)); /* A compilation error here means XXH32_SIZEOFSTATE is not large enough */
334 return sizeof(struct XXH_state32_t);
335 }
336 #endif
337
338 static
XXH32_resetState(void * state_in,U32 seed)339 XXH_errorcode XXH32_resetState(void* state_in, U32 seed)
340 {
341 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
342 state->seed = seed;
343 state->v1 = seed + PRIME32_1 + PRIME32_2;
344 state->v2 = seed + PRIME32_2;
345 state->v3 = seed + 0;
346 state->v4 = seed - PRIME32_1;
347 state->total_len = 0;
348 state->memsize = 0;
349 return XXH_OK;
350 }
351
352 static
XXH32_init(U32 seed)353 void* XXH32_init (U32 seed)
354 {
355 void* state = XXH_malloc (sizeof(struct XXH_state32_t));
356 XXH32_resetState(state, seed);
357 return state;
358 }
359
360 static
XXH32_update_endian(void * state_in,const void * input,int len,XXH_endianess endian)361 FORCE_INLINE XXH_errorcode XXH32_update_endian (void* state_in, const void* input, int len, XXH_endianess endian)
362 {
363 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
364 const BYTE* p = (const BYTE*)input;
365 const BYTE* const bEnd = p + len;
366
367 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
368 if (input==NULL) return XXH_ERROR;
369 #endif
370
371 state->total_len += len;
372
373 if (state->memsize + len < 16) /* fill in tmp buffer */
374 {
375 XXH_memcpy(state->memory + state->memsize, input, len);
376 state->memsize += len;
377 return XXH_OK;
378 }
379
380 if (state->memsize) /* some data left from previous update */
381 {
382 XXH_memcpy(state->memory + state->memsize, input, 16-state->memsize);
383 {
384 const U32* p32 = (const U32*)state->memory;
385 state->v1 += XXH_readLE32(p32, endian) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++;
386 state->v2 += XXH_readLE32(p32, endian) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++;
387 state->v3 += XXH_readLE32(p32, endian) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++;
388 state->v4 += XXH_readLE32(p32, endian) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++;
389 }
390 p += 16-state->memsize;
391 state->memsize = 0;
392 }
393
394 if (p <= bEnd-16)
395 {
396 const BYTE* const limit = bEnd - 16;
397 U32 v1 = state->v1;
398 U32 v2 = state->v2;
399 U32 v3 = state->v3;
400 U32 v4 = state->v4;
401
402 do
403 {
404 v1 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
405 v2 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
406 v3 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
407 v4 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
408 } while (p<=limit);
409
410 state->v1 = v1;
411 state->v2 = v2;
412 state->v3 = v3;
413 state->v4 = v4;
414 }
415
416 if (p < bEnd)
417 {
418 XXH_memcpy(state->memory, p, bEnd-p);
419 state->memsize = (int)(bEnd-p);
420 }
421
422 return XXH_OK;
423 }
424
425 static
XXH32_update(void * state_in,const void * input,unsigned int len)426 XXH_errorcode XXH32_update (void* state_in, const void* input, unsigned int len)
427 {
428 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
429
430 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
431 return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
432 else
433 return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
434 }
435
436
437
438 static
XXH32_intermediateDigest_endian(void * state_in,XXH_endianess endian)439 FORCE_INLINE U32 XXH32_intermediateDigest_endian (void* state_in, XXH_endianess endian)
440 {
441 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
442 const BYTE * p = (const BYTE*)state->memory;
443 BYTE* bEnd = (BYTE*)state->memory + state->memsize;
444 U32 h32;
445
446 if (state->total_len >= 16)
447 {
448 h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
449 }
450 else
451 {
452 h32 = state->seed + PRIME32_5;
453 }
454
455 h32 += (U32) state->total_len;
456
457 while (p<=bEnd-4)
458 {
459 h32 += XXH_readLE32((const U32*)p, endian) * PRIME32_3;
460 h32 = XXH_rotl32(h32, 17) * PRIME32_4;
461 p+=4;
462 }
463
464 while (p<bEnd)
465 {
466 h32 += (*p) * PRIME32_5;
467 h32 = XXH_rotl32(h32, 11) * PRIME32_1;
468 p++;
469 }
470
471 h32 ^= h32 >> 15;
472 h32 *= PRIME32_2;
473 h32 ^= h32 >> 13;
474 h32 *= PRIME32_3;
475 h32 ^= h32 >> 16;
476
477 return h32;
478 }
479
480 static
XXH32_intermediateDigest(void * state_in)481 U32 XXH32_intermediateDigest (void* state_in)
482 {
483 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
484
485 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
486 return XXH32_intermediateDigest_endian(state_in, XXH_littleEndian);
487 else
488 return XXH32_intermediateDigest_endian(state_in, XXH_bigEndian);
489 }
490
491 static
XXH32_digest(void * state_in)492 U32 XXH32_digest (void* state_in)
493 {
494 U32 h32 = XXH32_intermediateDigest(state_in);
495
496 XXH_free(state_in);
497
498 return h32;
499 }
500
501 const
502 struct archive_xxhash __archive_xxhash = {
503 XXH32,
504 XXH32_init,
505 XXH32_update,
506 XXH32_digest
507 };
508 #else
509
510 /*
511 * Define an empty version of the struct if we aren't using the LZ4 library.
512 */
513 const
514 struct archive_xxhash __archive_xxhash = {
515 NULL,
516 NULL,
517 NULL,
518 NULL
519 };
520
521 #endif /* HAVE_LIBLZ4 */
522