lz4/xxhash.c
Go to the documentation of this file.
1 /*
2 * xxHash - Fast Hash algorithm
3 * Copyright (C) 2012-2016, Yann Collet
4 *
5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
9 * met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following disclaimer
15 * in the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 * You can contact the author at :
31 * - xxHash homepage: http://www.xxhash.com
32 * - xxHash source repository : https://github.com/Cyan4973/xxHash
33 */
34 
35 
36 /* *************************************
37 * Tuning parameters
38 ***************************************/
52 #ifndef XXH_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
53 # if defined(__GNUC__) && ( defined(__ARM_ARCH_6__) || defined(__ARM_ARCH_6J__) || defined(__ARM_ARCH_6K__) || defined(__ARM_ARCH_6Z__) || defined(__ARM_ARCH_6ZK__) || defined(__ARM_ARCH_6T2__) )
54 # define XXH_FORCE_MEMORY_ACCESS 2
55 # elif defined(__INTEL_COMPILER) || \
56  (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
57 # define XXH_FORCE_MEMORY_ACCESS 1
58 # endif
59 #endif
60 
66 /* #define XXH_ACCEPT_NULL_INPUT_POINTER 1 */
67 
76 #ifndef XXH_FORCE_NATIVE_FORMAT /* can be defined externally */
77 # define XXH_FORCE_NATIVE_FORMAT 0
78 #endif
79 
86 #ifndef XXH_FORCE_ALIGN_CHECK /* can be defined externally */
87 # if defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
88 # define XXH_FORCE_ALIGN_CHECK 0
89 # else
90 # define XXH_FORCE_ALIGN_CHECK 1
91 # endif
92 #endif
93 
94 
95 /* *************************************
96 * Includes & Memory related functions
97 ***************************************/
100 #include <stdlib.h>
101 static void* XXH_malloc(size_t s) { return malloc(s); }
102 static void XXH_free (void* p) { free(p); }
104 #include <string.h>
105 static void* XXH_memcpy(void* dest, const void* src, size_t size) { return memcpy(dest,src,size); }
106 
107 #define XXH_STATIC_LINKING_ONLY
108 #include "xxhash.h"
109 
110 
111 /* *************************************
112 * Compiler Specific Options
113 ***************************************/
114 #ifdef _MSC_VER /* Visual Studio */
115 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
116 # define FORCE_INLINE static __forceinline
117 #else
118 # if defined (__cplusplus) || defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
119 # ifdef __GNUC__
120 # define FORCE_INLINE static inline __attribute__((always_inline))
121 # else
122 # define FORCE_INLINE static inline
123 # endif
124 # else
125 # define FORCE_INLINE static
126 # endif /* __STDC_VERSION__ */
127 #endif
128 
129 
130 /* *************************************
131 * Basic Types
132 ***************************************/
133 #ifndef MEM_MODULE
134 # if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
135 # include <stdint.h>
136  typedef uint8_t BYTE;
137  typedef uint16_t U16;
138  typedef uint32_t U32;
139  typedef int32_t S32;
140 # else
141  typedef unsigned char BYTE;
142  typedef unsigned short U16;
143  typedef unsigned int U32;
144  typedef signed int S32;
145 # endif
146 #endif
147 
148 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
149 
150 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
151 static U32 XXH_read32(const void* memPtr) { return *(const U32*) memPtr; }
152 
153 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
154 
155 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
156 /* currently only defined for gcc and icc */
157 typedef union { U32 u32; } __attribute__((packed)) unalign;
158 static U32 XXH_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
159 
160 #else
161 
162 /* portable and safe solution. Generally efficient.
163  * see : http://stackoverflow.com/a/32095106/646947
164  */
165 static U32 XXH_read32(const void* memPtr)
166 {
167  U32 val;
168  memcpy(&val, memPtr, sizeof(val));
169  return val;
170 }
171 
172 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
173 
174 
175 /* ****************************************
176 * Compiler-specific Functions and Macros
177 ******************************************/
178 #define XXH_GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
179 
180 /* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */
181 #if defined(_MSC_VER)
182 # define XXH_rotl32(x,r) _rotl(x,r)
183 # define XXH_rotl64(x,r) _rotl64(x,r)
184 #else
185 # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
186 # define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r)))
187 #endif
188 
189 #if defined(_MSC_VER) /* Visual Studio */
190 # define XXH_swap32 _byteswap_ulong
191 #elif XXH_GCC_VERSION >= 403
192 # define XXH_swap32 __builtin_bswap32
193 #else
194 static U32 XXH_swap32 (U32 x)
195 {
196  return ((x << 24) & 0xff000000 ) |
197  ((x << 8) & 0x00ff0000 ) |
198  ((x >> 8) & 0x0000ff00 ) |
199  ((x >> 24) & 0x000000ff );
200 }
201 #endif
202 
203 
204 /* *************************************
205 * Architecture Macros
206 ***************************************/
208 
209 /* XXH_CPU_LITTLE_ENDIAN can be defined externally, for example on the compiler command line */
210 #ifndef XXH_CPU_LITTLE_ENDIAN
211  static const int g_one = 1;
212 # define XXH_CPU_LITTLE_ENDIAN (*(const char*)(&g_one))
213 #endif
214 
215 
216 /* ***************************
217 * Memory reads
218 *****************************/
220 
222 {
223  if (align==XXH_unaligned)
224  return endian==XXH_littleEndian ? XXH_read32(ptr) : XXH_swap32(XXH_read32(ptr));
225  else
226  return endian==XXH_littleEndian ? *(const U32*)ptr : XXH_swap32(*(const U32*)ptr);
227 }
228 
229 FORCE_INLINE U32 XXH_readLE32(const void* ptr, XXH_endianess endian)
230 {
231  return XXH_readLE32_align(ptr, endian, XXH_unaligned);
232 }
233 
234 static U32 XXH_readBE32(const void* ptr)
235 {
237 }
238 
239 
240 /* *************************************
241 * Macros
242 ***************************************/
243 #define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
245 
246 
247 /* *******************************************************************
248 * 32-bits hash functions
249 *********************************************************************/
250 static const U32 PRIME32_1 = 2654435761U;
251 static const U32 PRIME32_2 = 2246822519U;
252 static const U32 PRIME32_3 = 3266489917U;
253 static const U32 PRIME32_4 = 668265263U;
254 static const U32 PRIME32_5 = 374761393U;
255 
256 static U32 XXH32_round(U32 seed, U32 input)
257 {
258  seed += input * PRIME32_2;
259  seed = XXH_rotl32(seed, 13);
260  seed *= PRIME32_1;
261  return seed;
262 }
263 
265 {
266  const BYTE* p = (const BYTE*)input;
267  const BYTE* bEnd = p + len;
268  U32 h32;
269 #define XXH_get32bits(p) XXH_readLE32_align(p, endian, align)
270 
271 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
272  if (p==NULL) {
273  len=0;
274  bEnd=p=(const BYTE*)(size_t)16;
275  }
276 #endif
277 
278  if (len>=16) {
279  const BYTE* const limit = bEnd - 16;
280  U32 v1 = seed + PRIME32_1 + PRIME32_2;
281  U32 v2 = seed + PRIME32_2;
282  U32 v3 = seed + 0;
283  U32 v4 = seed - PRIME32_1;
284 
285  do {
286  v1 = XXH32_round(v1, XXH_get32bits(p)); p+=4;
287  v2 = XXH32_round(v2, XXH_get32bits(p)); p+=4;
288  v3 = XXH32_round(v3, XXH_get32bits(p)); p+=4;
289  v4 = XXH32_round(v4, XXH_get32bits(p)); p+=4;
290  } while (p<=limit);
291 
292  h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
293  } else {
294  h32 = seed + PRIME32_5;
295  }
296 
297  h32 += (U32) len;
298 
299  while (p+4<=bEnd) {
300  h32 += XXH_get32bits(p) * PRIME32_3;
301  h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
302  p+=4;
303  }
304 
305  while (p<bEnd) {
306  h32 += (*p) * PRIME32_5;
307  h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
308  p++;
309  }
310 
311  h32 ^= h32 >> 15;
312  h32 *= PRIME32_2;
313  h32 ^= h32 >> 13;
314  h32 *= PRIME32_3;
315  h32 ^= h32 >> 16;
316 
317  return h32;
318 }
319 
320 
321 XXH_PUBLIC_API unsigned int XXH32 (const void* input, size_t len, unsigned int seed)
322 {
323 #if 0
324  /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
326  XXH32_reset(&state, seed);
327  XXH32_update(&state, input, len);
328  return XXH32_digest(&state);
329 #else
331 
332  if (XXH_FORCE_ALIGN_CHECK) {
333  if ((((size_t)input) & 3) == 0) { /* Input is 4-bytes aligned, leverage the speed benefit */
334  if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
335  return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
336  else
337  return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
338  } }
339 
340  if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
341  return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
342  else
343  return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
344 #endif
345 }
346 
347 
348 
349 /*====== Hash streaming ======*/
350 
352 {
353  return (XXH32_state_t*)XXH_malloc(sizeof(XXH32_state_t));
354 }
356 {
357  XXH_free(statePtr);
358  return XXH_OK;
359 }
360 
362 {
363  memcpy(dstState, srcState, sizeof(*dstState));
364 }
365 
367 {
368  XXH32_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */
369  memset(&state, 0, sizeof(state)-4); /* do not write into reserved, for future removal */
370  state.v1 = seed + PRIME32_1 + PRIME32_2;
371  state.v2 = seed + PRIME32_2;
372  state.v3 = seed + 0;
373  state.v4 = seed - PRIME32_1;
374  memcpy(statePtr, &state, sizeof(state));
375  return XXH_OK;
376 }
377 
378 
380 {
381  const BYTE* p = (const BYTE*)input;
382  const BYTE* const bEnd = p + len;
383 
384 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
385  if (input==NULL) return XXH_ERROR;
386 #endif
387 
388  state->total_len_32 += (unsigned)len;
389  state->large_len |= (len>=16) | (state->total_len_32>=16);
390 
391  if (state->memsize + len < 16) { /* fill in tmp buffer */
392  XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, len);
393  state->memsize += (unsigned)len;
394  return XXH_OK;
395  }
396 
397  if (state->memsize) { /* some data left from previous update */
398  XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, 16-state->memsize);
399  { const U32* p32 = state->mem32;
400  state->v1 = XXH32_round(state->v1, XXH_readLE32(p32, endian)); p32++;
401  state->v2 = XXH32_round(state->v2, XXH_readLE32(p32, endian)); p32++;
402  state->v3 = XXH32_round(state->v3, XXH_readLE32(p32, endian)); p32++;
403  state->v4 = XXH32_round(state->v4, XXH_readLE32(p32, endian)); p32++;
404  }
405  p += 16-state->memsize;
406  state->memsize = 0;
407  }
408 
409  if (p <= bEnd-16) {
410  const BYTE* const limit = bEnd - 16;
411  U32 v1 = state->v1;
412  U32 v2 = state->v2;
413  U32 v3 = state->v3;
414  U32 v4 = state->v4;
415 
416  do {
417  v1 = XXH32_round(v1, XXH_readLE32(p, endian)); p+=4;
418  v2 = XXH32_round(v2, XXH_readLE32(p, endian)); p+=4;
419  v3 = XXH32_round(v3, XXH_readLE32(p, endian)); p+=4;
420  v4 = XXH32_round(v4, XXH_readLE32(p, endian)); p+=4;
421  } while (p<=limit);
422 
423  state->v1 = v1;
424  state->v2 = v2;
425  state->v3 = v3;
426  state->v4 = v4;
427  }
428 
429  if (p < bEnd) {
430  XXH_memcpy(state->mem32, p, (size_t)(bEnd-p));
431  state->memsize = (unsigned)(bEnd-p);
432  }
433 
434  return XXH_OK;
435 }
436 
438 {
440 
441  if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
442  return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
443  else
444  return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
445 }
446 
447 
448 
450 {
451  const BYTE * p = (const BYTE*)state->mem32;
452  const BYTE* const bEnd = (const BYTE*)(state->mem32) + state->memsize;
453  U32 h32;
454 
455  if (state->large_len) {
456  h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
457  } else {
458  h32 = state->v3 /* == seed */ + PRIME32_5;
459  }
460 
461  h32 += state->total_len_32;
462 
463  while (p+4<=bEnd) {
464  h32 += XXH_readLE32(p, endian) * PRIME32_3;
465  h32 = XXH_rotl32(h32, 17) * PRIME32_4;
466  p+=4;
467  }
468 
469  while (p<bEnd) {
470  h32 += (*p) * PRIME32_5;
471  h32 = XXH_rotl32(h32, 11) * PRIME32_1;
472  p++;
473  }
474 
475  h32 ^= h32 >> 15;
476  h32 *= PRIME32_2;
477  h32 ^= h32 >> 13;
478  h32 *= PRIME32_3;
479  h32 ^= h32 >> 16;
480 
481  return h32;
482 }
483 
484 
485 XXH_PUBLIC_API unsigned int XXH32_digest (const XXH32_state_t* state_in)
486 {
488 
489  if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
490  return XXH32_digest_endian(state_in, XXH_littleEndian);
491  else
492  return XXH32_digest_endian(state_in, XXH_bigEndian);
493 }
494 
495 
496 /*====== Canonical representation ======*/
497 
505 {
507  if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap32(hash);
508  memcpy(dst, &hash, sizeof(*dst));
509 }
510 
512 {
513  return XXH_readBE32(src);
514 }
515 
516 
517 #ifndef XXH_NO_LONG_LONG
518 
519 /* *******************************************************************
520 * 64-bits hash functions
521 *********************************************************************/
522 
523 /*====== Memory access ======*/
524 
525 #ifndef MEM_MODULE
526 # define MEM_MODULE
527 # if !defined (__VMS) && (defined (__cplusplus) || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
528 # include <stdint.h>
529  typedef uint64_t U64;
530 # else
531  typedef unsigned long long U64; /* if your compiler doesn't support unsigned long long, replace by another 64-bit type here. Note that xxhash.h will also need to be updated. */
532 # endif
533 #endif
534 
535 
536 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
537 
538 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
539 static U64 XXH_read64(const void* memPtr) { return *(const U64*) memPtr; }
540 
541 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
542 
543 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
544 /* currently only defined for gcc and icc */
545 typedef union { U32 u32; U64 u64; } __attribute__((packed)) unalign64;
546 static U64 XXH_read64(const void* ptr) { return ((const unalign64*)ptr)->u64; }
547 
548 #else
549 
550 /* portable and safe solution. Generally efficient.
551  * see : http://stackoverflow.com/a/32095106/646947
552  */
553 
554 static U64 XXH_read64(const void* memPtr)
555 {
556  U64 val;
557  memcpy(&val, memPtr, sizeof(val));
558  return val;
559 }
560 
561 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
562 
563 #if defined(_MSC_VER) /* Visual Studio */
564 # define XXH_swap64 _byteswap_uint64
565 #elif XXH_GCC_VERSION >= 403
566 # define XXH_swap64 __builtin_bswap64
567 #else
568 static U64 XXH_swap64 (U64 x)
569 {
570  return ((x << 56) & 0xff00000000000000ULL) |
571  ((x << 40) & 0x00ff000000000000ULL) |
572  ((x << 24) & 0x0000ff0000000000ULL) |
573  ((x << 8) & 0x000000ff00000000ULL) |
574  ((x >> 8) & 0x00000000ff000000ULL) |
575  ((x >> 24) & 0x0000000000ff0000ULL) |
576  ((x >> 40) & 0x000000000000ff00ULL) |
577  ((x >> 56) & 0x00000000000000ffULL);
578 }
579 #endif
580 
582 {
583  if (align==XXH_unaligned)
584  return endian==XXH_littleEndian ? XXH_read64(ptr) : XXH_swap64(XXH_read64(ptr));
585  else
586  return endian==XXH_littleEndian ? *(const U64*)ptr : XXH_swap64(*(const U64*)ptr);
587 }
588 
589 FORCE_INLINE U64 XXH_readLE64(const void* ptr, XXH_endianess endian)
590 {
591  return XXH_readLE64_align(ptr, endian, XXH_unaligned);
592 }
593 
594 static U64 XXH_readBE64(const void* ptr)
595 {
597 }
598 
599 
600 /*====== xxh64 ======*/
601 
602 static const U64 PRIME64_1 = 11400714785074694791ULL;
603 static const U64 PRIME64_2 = 14029467366897019727ULL;
604 static const U64 PRIME64_3 = 1609587929392839161ULL;
605 static const U64 PRIME64_4 = 9650029242287828579ULL;
606 static const U64 PRIME64_5 = 2870177450012600261ULL;
607 
609 {
610  acc += input * PRIME64_2;
611  acc = XXH_rotl64(acc, 31);
612  acc *= PRIME64_1;
613  return acc;
614 }
615 
617 {
618  val = XXH64_round(0, val);
619  acc ^= val;
620  acc = acc * PRIME64_1 + PRIME64_4;
621  return acc;
622 }
623 
625 {
626  const BYTE* p = (const BYTE*)input;
627  const BYTE* const bEnd = p + len;
628  U64 h64;
629 #define XXH_get64bits(p) XXH_readLE64_align(p, endian, align)
630 
631 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
632  if (p==NULL) {
633  len=0;
634  bEnd=p=(const BYTE*)(size_t)32;
635  }
636 #endif
637 
638  if (len>=32) {
639  const BYTE* const limit = bEnd - 32;
640  U64 v1 = seed + PRIME64_1 + PRIME64_2;
641  U64 v2 = seed + PRIME64_2;
642  U64 v3 = seed + 0;
643  U64 v4 = seed - PRIME64_1;
644 
645  do {
646  v1 = XXH64_round(v1, XXH_get64bits(p)); p+=8;
647  v2 = XXH64_round(v2, XXH_get64bits(p)); p+=8;
648  v3 = XXH64_round(v3, XXH_get64bits(p)); p+=8;
649  v4 = XXH64_round(v4, XXH_get64bits(p)); p+=8;
650  } while (p<=limit);
651 
652  h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
653  h64 = XXH64_mergeRound(h64, v1);
654  h64 = XXH64_mergeRound(h64, v2);
655  h64 = XXH64_mergeRound(h64, v3);
656  h64 = XXH64_mergeRound(h64, v4);
657 
658  } else {
659  h64 = seed + PRIME64_5;
660  }
661 
662  h64 += (U64) len;
663 
664  while (p+8<=bEnd) {
665  U64 const k1 = XXH64_round(0, XXH_get64bits(p));
666  h64 ^= k1;
667  h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
668  p+=8;
669  }
670 
671  if (p+4<=bEnd) {
672  h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1;
673  h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
674  p+=4;
675  }
676 
677  while (p<bEnd) {
678  h64 ^= (*p) * PRIME64_5;
679  h64 = XXH_rotl64(h64, 11) * PRIME64_1;
680  p++;
681  }
682 
683  h64 ^= h64 >> 33;
684  h64 *= PRIME64_2;
685  h64 ^= h64 >> 29;
686  h64 *= PRIME64_3;
687  h64 ^= h64 >> 32;
688 
689  return h64;
690 }
691 
692 
693 XXH_PUBLIC_API unsigned long long XXH64 (const void* input, size_t len, unsigned long long seed)
694 {
695 #if 0
696  /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
698  XXH64_reset(&state, seed);
699  XXH64_update(&state, input, len);
700  return XXH64_digest(&state);
701 #else
703 
704  if (XXH_FORCE_ALIGN_CHECK) {
705  if ((((size_t)input) & 7)==0) { /* Input is aligned, let's leverage the speed advantage */
706  if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
707  return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
708  else
709  return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
710  } }
711 
712  if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
713  return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
714  else
715  return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
716 #endif
717 }
718 
719 /*====== Hash Streaming ======*/
720 
722 {
723  return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t));
724 }
726 {
727  XXH_free(statePtr);
728  return XXH_OK;
729 }
730 
732 {
733  memcpy(dstState, srcState, sizeof(*dstState));
734 }
735 
736 XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t* statePtr, unsigned long long seed)
737 {
738  XXH64_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */
739  memset(&state, 0, sizeof(state)-8); /* do not write into reserved, for future removal */
740  state.v1 = seed + PRIME64_1 + PRIME64_2;
741  state.v2 = seed + PRIME64_2;
742  state.v3 = seed + 0;
743  state.v4 = seed - PRIME64_1;
744  memcpy(statePtr, &state, sizeof(state));
745  return XXH_OK;
746 }
747 
749 {
750  const BYTE* p = (const BYTE*)input;
751  const BYTE* const bEnd = p + len;
752 
753 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
754  if (input==NULL) return XXH_ERROR;
755 #endif
756 
757  state->total_len += len;
758 
759  if (state->memsize + len < 32) { /* fill in tmp buffer */
760  XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, len);
761  state->memsize += (U32)len;
762  return XXH_OK;
763  }
764 
765  if (state->memsize) { /* tmp buffer is full */
766  XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, 32-state->memsize);
767  state->v1 = XXH64_round(state->v1, XXH_readLE64(state->mem64+0, endian));
768  state->v2 = XXH64_round(state->v2, XXH_readLE64(state->mem64+1, endian));
769  state->v3 = XXH64_round(state->v3, XXH_readLE64(state->mem64+2, endian));
770  state->v4 = XXH64_round(state->v4, XXH_readLE64(state->mem64+3, endian));
771  p += 32-state->memsize;
772  state->memsize = 0;
773  }
774 
775  if (p+32 <= bEnd) {
776  const BYTE* const limit = bEnd - 32;
777  U64 v1 = state->v1;
778  U64 v2 = state->v2;
779  U64 v3 = state->v3;
780  U64 v4 = state->v4;
781 
782  do {
783  v1 = XXH64_round(v1, XXH_readLE64(p, endian)); p+=8;
784  v2 = XXH64_round(v2, XXH_readLE64(p, endian)); p+=8;
785  v3 = XXH64_round(v3, XXH_readLE64(p, endian)); p+=8;
786  v4 = XXH64_round(v4, XXH_readLE64(p, endian)); p+=8;
787  } while (p<=limit);
788 
789  state->v1 = v1;
790  state->v2 = v2;
791  state->v3 = v3;
792  state->v4 = v4;
793  }
794 
795  if (p < bEnd) {
796  XXH_memcpy(state->mem64, p, (size_t)(bEnd-p));
797  state->memsize = (unsigned)(bEnd-p);
798  }
799 
800  return XXH_OK;
801 }
802 
804 {
806 
807  if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
808  return XXH64_update_endian(state_in, input, len, XXH_littleEndian);
809  else
810  return XXH64_update_endian(state_in, input, len, XXH_bigEndian);
811 }
812 
814 {
815  const BYTE * p = (const BYTE*)state->mem64;
816  const BYTE* const bEnd = (const BYTE*)state->mem64 + state->memsize;
817  U64 h64;
818 
819  if (state->total_len >= 32) {
820  U64 const v1 = state->v1;
821  U64 const v2 = state->v2;
822  U64 const v3 = state->v3;
823  U64 const v4 = state->v4;
824 
825  h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
826  h64 = XXH64_mergeRound(h64, v1);
827  h64 = XXH64_mergeRound(h64, v2);
828  h64 = XXH64_mergeRound(h64, v3);
829  h64 = XXH64_mergeRound(h64, v4);
830  } else {
831  h64 = state->v3 + PRIME64_5;
832  }
833 
834  h64 += (U64) state->total_len;
835 
836  while (p+8<=bEnd) {
837  U64 const k1 = XXH64_round(0, XXH_readLE64(p, endian));
838  h64 ^= k1;
839  h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
840  p+=8;
841  }
842 
843  if (p+4<=bEnd) {
844  h64 ^= (U64)(XXH_readLE32(p, endian)) * PRIME64_1;
845  h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
846  p+=4;
847  }
848 
849  while (p<bEnd) {
850  h64 ^= (*p) * PRIME64_5;
851  h64 = XXH_rotl64(h64, 11) * PRIME64_1;
852  p++;
853  }
854 
855  h64 ^= h64 >> 33;
856  h64 *= PRIME64_2;
857  h64 ^= h64 >> 29;
858  h64 *= PRIME64_3;
859  h64 ^= h64 >> 32;
860 
861  return h64;
862 }
863 
864 XXH_PUBLIC_API unsigned long long XXH64_digest (const XXH64_state_t* state_in)
865 {
867 
868  if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
869  return XXH64_digest_endian(state_in, XXH_littleEndian);
870  else
871  return XXH64_digest_endian(state_in, XXH_bigEndian);
872 }
873 
874 
875 /*====== Canonical representation ======*/
876 
878 {
880  if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap64(hash);
881  memcpy(dst, &hash, sizeof(*dst));
882 }
883 
885 {
886  return XXH_readBE64(src);
887 }
888 
889 #endif /* XXH_NO_LONG_LONG */
static void XXH_free(void *p)
Definition: lz4/xxhash.c:102
XXH_PUBLIC_API XXH_errorcode XXH64_update(XXH64_state_t *state_in, const void *input, size_t len)
Definition: lz4/xxhash.c:803
unsigned short U16
Definition: lz4/xxhash.c:142
#define XXH_CPU_LITTLE_ENDIAN
Definition: lz4/xxhash.c:212
sqlite_uint64 u64
Definition: sqlite3.c:11446
FORCE_INLINE U64 XXH64_digest_endian(const XXH64_state_t *state, XXH_endianess endian)
Definition: lz4/xxhash.c:813
unsigned int U32
Definition: lz4.c:147
GLuint GLenum GLsizei GLsizei GLint GLint GLboolean packed
Definition: glext.h:9770
GLdouble s
GLfloat GLfloat p
Definition: glext.h:12687
static const U64 PRIME64_5
Definition: lz4/xxhash.c:606
static const U32 PRIME32_5
Definition: lz4/xxhash.c:254
#define XXH_rotl32(x, r)
Definition: lz4/xxhash.c:185
XXH_PUBLIC_API unsigned XXH_versionNumber(void)
Definition: lz4/xxhash.c:244
XXH_PUBLIC_API unsigned long long XXH64_digest(const XXH64_state_t *state_in)
Definition: lz4/xxhash.c:864
GLenum GLenum dst
Definition: glext.h:1751
XXH_PUBLIC_API XXH_errorcode XXH32_reset(XXH32_state_t *statePtr, unsigned int seed)
Definition: lz4/xxhash.c:366
unsigned short uint16_t
Definition: stdint.h:79
signed int S32
Definition: lz4/xxhash.c:144
static const U32 PRIME32_2
Definition: lz4/xxhash.c:251
XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t *src)
Definition: lz4/xxhash.c:884
GLenum src
Definition: glext.h:1751
unsigned long long U64
Definition: lz4.c:149
XXH_PUBLIC_API unsigned int XXH32_digest(const XXH32_state_t *state_in)
Definition: lz4/xxhash.c:485
#define XXH_VERSION_NUMBER
Definition: lz4/xxhash.h:153
GLint limit
Definition: glext.h:9964
unsigned char uint8_t
Definition: stdint.h:78
XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t *src)
Definition: lz4/xxhash.c:511
#define XXH_get32bits(p)
static U32 XXH_read32(const void *memPtr)
Definition: lz4/xxhash.c:165
static U64 XXH_read64(const void *memPtr)
Definition: lz4/xxhash.c:554
XXH_endianess
Definition: lz4/xxhash.c:207
GLenum GLsizei len
Definition: glext.h:3285
GLuint GLfloat * val
XXH_errorcode
Definition: lz4/xxhash.h:79
XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t *statePtr, unsigned long long seed)
Definition: lz4/xxhash.c:736
XXH_alignment
Definition: lz4/xxhash.c:219
unsigned char BYTE
Definition: lz4.c:145
struct XXH32_state_s XXH32_state_t
Definition: lz4/xxhash.h:170
static U32 XXH_swap32(U32 x)
Definition: lz4/xxhash.c:194
#define XXH_FORCE_ALIGN_CHECK
Definition: lz4/xxhash.c:90
#define XXH_FORCE_NATIVE_FORMAT
Definition: lz4/xxhash.c:77
GLsizeiptr size
#define XXH_STATIC_ASSERT(c)
Definition: lz4/xxhash.c:243
FORCE_INLINE U64 XXH_readLE64_align(const void *ptr, XXH_endianess endian, XXH_alignment align)
Definition: lz4/xxhash.c:581
FORCE_INLINE U32 XXH32_endian_align(const void *input, size_t len, U32 seed, XXH_endianess endian, XXH_alignment align)
Definition: lz4/xxhash.c:264
UINT32_TYPE u32
Definition: sqlite3.c:11447
GLdouble x
unsigned int uint32_t
Definition: stdint.h:80
FORCE_INLINE XXH_errorcode XXH32_update_endian(XXH32_state_t *state, const void *input, size_t len, XXH_endianess endian)
Definition: lz4/xxhash.c:379
FORCE_INLINE U64 XXH_readLE64(const void *ptr, XXH_endianess endian)
Definition: lz4/xxhash.c:589
static const U64 PRIME64_1
Definition: lz4/xxhash.c:602
XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t *statePtr)
Definition: lz4/xxhash.c:355
XXH_PUBLIC_API void XXH32_copyState(XXH32_state_t *dstState, const XXH32_state_t *srcState)
Definition: lz4/xxhash.c:361
static void * XXH_memcpy(void *dest, const void *src, size_t size)
Definition: lz4/xxhash.c:105
struct XXH64_state_s XXH64_state_t
Definition: lz4/xxhash.h:228
XXH_PUBLIC_API XXH64_state_t * XXH64_createState(void)
Definition: lz4/xxhash.c:721
unsigned __int64 uint64_t
Definition: stdint.h:90
GLfloat GLfloat GLfloat GLfloat v3
static const U64 PRIME64_2
Definition: lz4/xxhash.c:603
XXH_PUBLIC_API unsigned long long XXH64(const void *input, size_t len, unsigned long long seed)
Definition: lz4/xxhash.c:693
XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t *statePtr)
Definition: lz4/xxhash.c:725
unsigned long long XXH64_hash_t
Definition: lz4/xxhash.h:218
#define XXH_rotl64(x, r)
Definition: lz4/xxhash.c:186
static U64 XXH64_mergeRound(U64 acc, U64 val)
Definition: lz4/xxhash.c:616
XXH_PUBLIC_API void XXH64_copyState(XXH64_state_t *dstState, const XXH64_state_t *srcState)
Definition: lz4/xxhash.c:731
static const U32 PRIME32_1
Definition: lz4/xxhash.c:250
#define XXH_PUBLIC_API
Definition: lz4/xxhash.h:108
#define FORCE_INLINE
Definition: lz4/xxhash.c:125
unsigned char BYTE
Definition: lz4/xxhash.c:141
XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t *dst, XXH64_hash_t hash)
Definition: lz4/xxhash.c:877
FORCE_INLINE U32 XXH_readLE32(const void *ptr, XXH_endianess endian)
Definition: lz4/xxhash.c:229
FORCE_INLINE U32 XXH_readLE32_align(const void *ptr, XXH_endianess endian, XXH_alignment align)
Definition: lz4/xxhash.c:221
#define XXH_get64bits(p)
GLdouble GLdouble GLint GLint GLdouble v1
static const U64 PRIME64_3
Definition: lz4/xxhash.c:604
static void * XXH_malloc(size_t s)
Definition: lz4/xxhash.c:101
static const int g_one
Definition: lz4/xxhash.c:211
FORCE_INLINE U32 XXH32_digest_endian(const XXH32_state_t *state, XXH_endianess endian)
Definition: lz4/xxhash.c:449
GLenum GLenum GLenum input
Definition: glext.h:10805
static const U32 PRIME32_4
Definition: lz4/xxhash.c:253
unsigned int XXH32_hash_t
Definition: lz4/xxhash.h:160
static U32 XXH_readBE32(const void *ptr)
Definition: lz4/xxhash.c:234
FORCE_INLINE U64 XXH64_endian_align(const void *input, size_t len, U64 seed, XXH_endianess endian, XXH_alignment align)
Definition: lz4/xxhash.c:624
XXH_PUBLIC_API XXH32_state_t * XXH32_createState(void)
Definition: lz4/xxhash.c:351
LZ4LIB_API char * dest
Definition: lz4.h:438
static U64 XXH64_round(U64 acc, U64 input)
Definition: lz4/xxhash.c:608
XXH_PUBLIC_API XXH_errorcode XXH32_update(XXH32_state_t *state_in, const void *input, size_t len)
Definition: lz4/xxhash.c:437
static U64 XXH_readBE64(const void *ptr)
Definition: lz4/xxhash.c:594
XXH_PUBLIC_API unsigned int XXH32(const void *input, size_t len, unsigned int seed)
Definition: lz4/xxhash.c:321
#define NULL
Definition: tinycthread.c:47
const GLdouble * v2
signed int int32_t
Definition: stdint.h:77
unsigned long long U64
Definition: lz4/xxhash.c:531
FORCE_INLINE XXH_errorcode XXH64_update_endian(XXH64_state_t *state, const void *input, size_t len, XXH_endianess endian)
Definition: lz4/xxhash.c:748
static const U64 PRIME64_4
Definition: lz4/xxhash.c:605
unsigned int U32
Definition: lz4/xxhash.c:143
static U32 XXH32_round(U32 seed, U32 input)
Definition: lz4/xxhash.c:256
static U64 XXH_swap64(U64 x)
Definition: lz4/xxhash.c:568
XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t *dst, XXH32_hash_t hash)
Definition: lz4/xxhash.c:504
static const U32 PRIME32_3
Definition: lz4/xxhash.c:252


librealsense2
Author(s): Sergey Dorodnicov , Doron Hirshberg , Mark Horn , Reagan Lopez , Itay Carpis
autogenerated on Mon May 3 2021 02:50:23