]> git.proxmox.com Git - ceph.git/blob - ceph/src/xxHash/xxhash.c
projects / ceph.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
add subtree-ish sources for 12.0.3
[ceph.git] / ceph / src / xxHash / xxhash.c
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 source repository : https://github.com/Cyan4973/xxHash
32 */
33
34
35 /* *************************************
36 * Tuning parameters
37 ***************************************/
38 /*!XXH_FORCE_MEMORY_ACCESS
39 * By default, access to unaligned memory is controlled by `memcpy()`, which is safe and portable.
40 * Unfortunately, on some target/compiler combinations, the generated assembly is sub-optimal.
41 * The below switch allow to select different access method for improved performance.
42 * Method 0 (default) : use `memcpy()`. Safe and portable.
43 * Method 1 : `__packed` statement. It depends on compiler extension (ie, not portable).
44 * This method is safe if your compiler supports it, and *generally* as fast or faster than `memcpy`.
45 * Method 2 : direct access. This method doesn't depend on compiler but violate C standard.
46 * It can generate buggy code on targets which do not support unaligned memory accesses.
47 * But in some circumstances, it's the only known way to get the most performance (ie GCC + ARMv6)
48 * See http://stackoverflow.com/a/32095106/646947 for details.
49 * Prefer these methods in priority order (0 > 1 > 2)
50 */
51 #ifndef XXH_FORCE_MEMORY_ACCESS /* can be defined externally, on command line for example */
52 # 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__) )
53 # define XXH_FORCE_MEMORY_ACCESS 2
54 # elif defined(__INTEL_COMPILER) || \
55 (defined(__GNUC__) && ( defined(__ARM_ARCH_7__) || defined(__ARM_ARCH_7A__) || defined(__ARM_ARCH_7R__) || defined(__ARM_ARCH_7M__) || defined(__ARM_ARCH_7S__) ))
56 # define XXH_FORCE_MEMORY_ACCESS 1
57 # endif
58 #endif
59
60 /*!XXH_ACCEPT_NULL_INPUT_POINTER :
61 * If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer.
62 * When this option is enabled, xxHash output for null input pointers will be the same as a null-length input.
63 * By default, this option is disabled. To enable it, uncomment below define :
64 */
65 /* #define XXH_ACCEPT_NULL_INPUT_POINTER 1 */
66
67 /*!XXH_FORCE_NATIVE_FORMAT :
68 * By default, xxHash library provides endian-independant Hash values, based on little-endian convention.
69 * Results are therefore identical for little-endian and big-endian CPU.
70 * This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format.
71 * Should endian-independance be of no importance for your application, you may set the #define below to 1,
72 * to improve speed for Big-endian CPU.
73 * This option has no impact on Little_Endian CPU.
74 */
75 #define XXH_FORCE_NATIVE_FORMAT 0
76
77 /*!XXH_USELESS_ALIGN_BRANCH :
78 * This is a minor performance trick, only useful with lots of very small keys.
79 * It means : don't check for aligned/unaligned input, because performance will be the same.
80 * It saves one initial branch per hash.
81 */
82 #if defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
83 # define XXH_USELESS_ALIGN_BRANCH 1
84 #endif
85
86
87 /* *************************************
88 * Compiler Specific Options
89 ***************************************/
90 #ifdef _MSC_VER /* Visual Studio */
91 # pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */
92 # define FORCE_INLINE static __forceinline
93 #else
94 # if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
95 # ifdef __GNUC__
96 # define FORCE_INLINE static inline __attribute__((always_inline))
97 # else
98 # define FORCE_INLINE static inline
99 # endif
100 # else
101 # define FORCE_INLINE static
102 # endif /* __STDC_VERSION__ */
103 #endif
104
105
106 /* *************************************
107 * Includes & Memory related functions
108 ***************************************/
109 /* Modify the local functions below should you wish to use some other memory routines */
110 /* for malloc(), free() */
111 #include <stdlib.h>
112 static void* XXH_malloc(size_t s) { return malloc(s); }
113 static void XXH_free (void* p) { free(p); }
114 /* for memcpy() */
115 #include <string.h>
116 static void* XXH_memcpy(void* dest, const void* src, size_t size) { return memcpy(dest,src,size); }
117
118 #include "xxhash.h"
119
120
121 /* *************************************
122 * Basic Types
123 ***************************************/
124 #ifndef MEM_MODULE
125 # define MEM_MODULE
126 # if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */
127 # include <stdint.h>
128 typedef uint8_t BYTE;
129 typedef uint16_t U16;
130 typedef uint32_t U32;
131 typedef int32_t S32;
132 typedef uint64_t U64;
133 # else
134 typedef unsigned char BYTE;
135 typedef unsigned short U16;
136 typedef unsigned int U32;
137 typedef signed int S32;
138 typedef unsigned long long U64;
139 # endif
140 #endif
141
142
143 #if (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==2))
144
145 /* Force direct memory access. Only works on CPU which support unaligned memory access in hardware */
146 static U32 XXH_read32(const void* memPtr) { return *(const U32*) memPtr; }
147 static U64 XXH_read64(const void* memPtr) { return *(const U64*) memPtr; }
148
149 #elif (defined(XXH_FORCE_MEMORY_ACCESS) && (XXH_FORCE_MEMORY_ACCESS==1))
150
151 /* __pack instructions are safer, but compiler specific, hence potentially problematic for some compilers */
152 /* currently only defined for gcc and icc */
153 typedef union { U32 u32; U64 u64; } __attribute__((packed)) unalign;
154
155 static U32 XXH_read32(const void* ptr) { return ((const unalign*)ptr)->u32; }
156 static U64 XXH_read64(const void* ptr) { return ((const unalign*)ptr)->u64; }
157
158 #else
159
160 /* portable and safe solution. Generally efficient.
161 * see : http://stackoverflow.com/a/32095106/646947
162 */
163
164 static U32 XXH_read32(const void* memPtr)
165 {
166 U32 val;
167 memcpy(&val, memPtr, sizeof(val));
168 return val;
169 }
170
171 static U64 XXH_read64(const void* memPtr)
172 {
173 U64 val;
174 memcpy(&val, memPtr, sizeof(val));
175 return val;
176 }
177
178 #endif /* XXH_FORCE_DIRECT_MEMORY_ACCESS */
179
180
181 /* ****************************************
182 * Compiler-specific Functions and Macros
183 ******************************************/
184 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
185
186 /* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */
187 #if defined(_MSC_VER)
188 # define XXH_rotl32(x,r) _rotl(x,r)
189 # define XXH_rotl64(x,r) _rotl64(x,r)
190 #else
191 # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
192 # define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r)))
193 #endif
194
195 #if defined(_MSC_VER) /* Visual Studio */
196 # define XXH_swap32 _byteswap_ulong
197 # define XXH_swap64 _byteswap_uint64
198 #elif GCC_VERSION >= 403
199 # define XXH_swap32 __builtin_bswap32
200 # define XXH_swap64 __builtin_bswap64
201 #else
202 static U32 XXH_swap32 (U32 x)
203 {
204 return ((x << 24) & 0xff000000 ) |
205 ((x << 8) & 0x00ff0000 ) |
206 ((x >> 8) & 0x0000ff00 ) |
207 ((x >> 24) & 0x000000ff );
208 }
209 static U64 XXH_swap64 (U64 x)
210 {
211 return ((x << 56) & 0xff00000000000000ULL) |
212 ((x << 40) & 0x00ff000000000000ULL) |
213 ((x << 24) & 0x0000ff0000000000ULL) |
214 ((x << 8) & 0x000000ff00000000ULL) |
215 ((x >> 8) & 0x00000000ff000000ULL) |
216 ((x >> 24) & 0x0000000000ff0000ULL) |
217 ((x >> 40) & 0x000000000000ff00ULL) |
218 ((x >> 56) & 0x00000000000000ffULL);
219 }
220 #endif
221
222
223 /* *************************************
224 * Architecture Macros
225 ***************************************/
226 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess;
227
228 /* XXH_CPU_LITTLE_ENDIAN can be defined externally, for example on the compiler command line */
229 #ifndef XXH_CPU_LITTLE_ENDIAN
230 static const int g_one = 1;
231 # define XXH_CPU_LITTLE_ENDIAN (*(const char*)(&g_one))
232 #endif
233
234
235 /* ***************************
236 * Memory reads
237 *****************************/
238 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
239
240 FORCE_INLINE U32 XXH_readLE32_align(const void* ptr, XXH_endianess endian, XXH_alignment align)
241 {
242 if (align==XXH_unaligned)
243 return endian==XXH_littleEndian ? XXH_read32(ptr) : XXH_swap32(XXH_read32(ptr));
244 else
245 return endian==XXH_littleEndian ? *(const U32*)ptr : XXH_swap32(*(const U32*)ptr);
246 }
247
248 FORCE_INLINE U32 XXH_readLE32(const void* ptr, XXH_endianess endian)
249 {
250 return XXH_readLE32_align(ptr, endian, XXH_unaligned);
251 }
252
253 static U32 XXH_readBE32(const void* ptr)
254 {
255 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap32(XXH_read32(ptr)) : XXH_read32(ptr);
256 }
257
258 FORCE_INLINE U64 XXH_readLE64_align(const void* ptr, XXH_endianess endian, XXH_alignment align)
259 {
260 if (align==XXH_unaligned)
261 return endian==XXH_littleEndian ? XXH_read64(ptr) : XXH_swap64(XXH_read64(ptr));
262 else
263 return endian==XXH_littleEndian ? *(const U64*)ptr : XXH_swap64(*(const U64*)ptr);
264 }
265
266 FORCE_INLINE U64 XXH_readLE64(const void* ptr, XXH_endianess endian)
267 {
268 return XXH_readLE64_align(ptr, endian, XXH_unaligned);
269 }
270
271 static U64 XXH_readBE64(const void* ptr)
272 {
273 return XXH_CPU_LITTLE_ENDIAN ? XXH_swap64(XXH_read64(ptr)) : XXH_read64(ptr);
274 }
275
276
277 /* *************************************
278 * Macros
279 ***************************************/
280 #define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(int)(!!(c)) }; } /* use only *after* variable declarations */
281
282
283 /* *************************************
284 * Constants
285 ***************************************/
286 #define PRIME32_1 2654435761U
287 #define PRIME32_2 2246822519U
288 #define PRIME32_3 3266489917U
289 #define PRIME32_4 668265263U
290 #define PRIME32_5 374761393U
291
292 #define PRIME64_1 11400714785074694791ULL
293 #define PRIME64_2 14029467366897019727ULL
294 #define PRIME64_3 1609587929392839161ULL
295 #define PRIME64_4 9650029242287828579ULL
296 #define PRIME64_5 2870177450012600261ULL
297
298 XXH_PUBLIC_API unsigned XXH_versionNumber (void) { return XXH_VERSION_NUMBER; }
299
300
301 /* ***************************
302 * Simple Hash Functions
303 *****************************/
304 FORCE_INLINE U32 XXH32_endian_align(const void* input, size_t len, U32 seed, XXH_endianess endian, XXH_alignment align)
305 {
306 const BYTE* p = (const BYTE*)input;
307 const BYTE* bEnd = p + len;
308 U32 h32;
309 #define XXH_get32bits(p) XXH_readLE32_align(p, endian, align)
310
311 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
312 if (p==NULL)
313 {
314 len=0;
315 bEnd=p=(const BYTE*)(size_t)16;
316 }
317 #endif
318
319 if (len>=16)
320 {
321 const BYTE* const limit = bEnd - 16;
322 U32 v1 = seed + PRIME32_1 + PRIME32_2;
323 U32 v2 = seed + PRIME32_2;
324 U32 v3 = seed + 0;
325 U32 v4 = seed - PRIME32_1;
326
327 do
328 {
329 v1 += XXH_get32bits(p) * PRIME32_2;
330 v1 = XXH_rotl32(v1, 13);
331 v1 *= PRIME32_1;
332 p+=4;
333 v2 += XXH_get32bits(p) * PRIME32_2;
334 v2 = XXH_rotl32(v2, 13);
335 v2 *= PRIME32_1;
336 p+=4;
337 v3 += XXH_get32bits(p) * PRIME32_2;
338 v3 = XXH_rotl32(v3, 13);
339 v3 *= PRIME32_1;
340 p+=4;
341 v4 += XXH_get32bits(p) * PRIME32_2;
342 v4 = XXH_rotl32(v4, 13);
343 v4 *= PRIME32_1;
344 p+=4;
345 }
346 while (p<=limit);
347
348 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
349 }
350 else
351 {
352 h32 = seed + PRIME32_5;
353 }
354
355 h32 += (U32) len;
356
357 while (p+4<=bEnd)
358 {
359 h32 += XXH_get32bits(p) * PRIME32_3;
360 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
361 p+=4;
362 }
363
364 while (p<bEnd)
365 {
366 h32 += (*p) * PRIME32_5;
367 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
368 p++;
369 }
370
371 h32 ^= h32 >> 15;
372 h32 *= PRIME32_2;
373 h32 ^= h32 >> 13;
374 h32 *= PRIME32_3;
375 h32 ^= h32 >> 16;
376
377 return h32;
378 }
379
380
381 XXH_PUBLIC_API unsigned int XXH32 (const void* input, size_t len, unsigned int seed)
382 {
383 #if 0
384 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
385 XXH32_CREATESTATE_STATIC(state);
386 XXH32_reset(state, seed);
387 XXH32_update(state, input, len);
388 return XXH32_digest(state);
389 #else
390 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
391
392 # if !defined(XXH_USELESS_ALIGN_BRANCH)
393 if ((((size_t)input) & 3) == 0) /* Input is 4-bytes aligned, leverage the speed benefit */
394 {
395 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
396 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
397 else
398 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
399 }
400 # endif
401
402 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
403 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
404 else
405 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
406 #endif
407 }
408
409 FORCE_INLINE U64 XXH64_endian_align(const void* input, size_t len, U64 seed, XXH_endianess endian, XXH_alignment align)
410 {
411 const BYTE* p = (const BYTE*)input;
412 const BYTE* bEnd = p + len;
413 U64 h64;
414 #define XXH_get64bits(p) XXH_readLE64_align(p, endian, align)
415
416 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
417 if (p==NULL)
418 {
419 len=0;
420 bEnd=p=(const BYTE*)(size_t)32;
421 }
422 #endif
423
424 if (len>=32)
425 {
426 const BYTE* const limit = bEnd - 32;
427 U64 v1 = seed + PRIME64_1 + PRIME64_2;
428 U64 v2 = seed + PRIME64_2;
429 U64 v3 = seed + 0;
430 U64 v4 = seed - PRIME64_1;
431
432 do
433 {
434 v1 += XXH_get64bits(p) * PRIME64_2;
435 p+=8;
436 v1 = XXH_rotl64(v1, 31);
437 v1 *= PRIME64_1;
438 v2 += XXH_get64bits(p) * PRIME64_2;
439 p+=8;
440 v2 = XXH_rotl64(v2, 31);
441 v2 *= PRIME64_1;
442 v3 += XXH_get64bits(p) * PRIME64_2;
443 p+=8;
444 v3 = XXH_rotl64(v3, 31);
445 v3 *= PRIME64_1;
446 v4 += XXH_get64bits(p) * PRIME64_2;
447 p+=8;
448 v4 = XXH_rotl64(v4, 31);
449 v4 *= PRIME64_1;
450 }
451 while (p<=limit);
452
453 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
454
455 v1 *= PRIME64_2;
456 v1 = XXH_rotl64(v1, 31);
457 v1 *= PRIME64_1;
458 h64 ^= v1;
459 h64 = h64 * PRIME64_1 + PRIME64_4;
460
461 v2 *= PRIME64_2;
462 v2 = XXH_rotl64(v2, 31);
463 v2 *= PRIME64_1;
464 h64 ^= v2;
465 h64 = h64 * PRIME64_1 + PRIME64_4;
466
467 v3 *= PRIME64_2;
468 v3 = XXH_rotl64(v3, 31);
469 v3 *= PRIME64_1;
470 h64 ^= v3;
471 h64 = h64 * PRIME64_1 + PRIME64_4;
472
473 v4 *= PRIME64_2;
474 v4 = XXH_rotl64(v4, 31);
475 v4 *= PRIME64_1;
476 h64 ^= v4;
477 h64 = h64 * PRIME64_1 + PRIME64_4;
478 }
479 else
480 {
481 h64 = seed + PRIME64_5;
482 }
483
484 h64 += (U64) len;
485
486 while (p+8<=bEnd)
487 {
488 U64 k1 = XXH_get64bits(p);
489 k1 *= PRIME64_2;
490 k1 = XXH_rotl64(k1,31);
491 k1 *= PRIME64_1;
492 h64 ^= k1;
493 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
494 p+=8;
495 }
496
497 if (p+4<=bEnd)
498 {
499 h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1;
500 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
501 p+=4;
502 }
503
504 while (p<bEnd)
505 {
506 h64 ^= (*p) * PRIME64_5;
507 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
508 p++;
509 }
510
511 h64 ^= h64 >> 33;
512 h64 *= PRIME64_2;
513 h64 ^= h64 >> 29;
514 h64 *= PRIME64_3;
515 h64 ^= h64 >> 32;
516
517 return h64;
518 }
519
520
521 XXH_PUBLIC_API unsigned long long XXH64 (const void* input, size_t len, unsigned long long seed)
522 {
523 #if 0
524 /* Simple version, good for code maintenance, but unfortunately slow for small inputs */
525 XXH64_CREATESTATE_STATIC(state);
526 XXH64_reset(state, seed);
527 XXH64_update(state, input, len);
528 return XXH64_digest(state);
529 #else
530 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
531
532 # if !defined(XXH_USELESS_ALIGN_BRANCH)
533 if ((((size_t)input) & 7)==0) /* Input is aligned, let's leverage the speed advantage */
534 {
535 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
536 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
537 else
538 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
539 }
540 # endif
541
542 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
543 return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
544 else
545 return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
546 #endif
547 }
548
549 /* **************************************************
550 * Advanced Hash Functions
551 ****************************************************/
552
553 /*** Allocation ***/
554 struct XXH32_state_s
555 {
556 U64 total_len;
557 U32 seed;
558 U32 v1;
559 U32 v2;
560 U32 v3;
561 U32 v4;
562 U32 mem32[4]; /* defined as U32 for alignment */
563 U32 memsize;
564 }; /* typedef'd to XXH32_state_t within xxhash.h */
565
566 struct XXH64_state_s
567 {
568 U64 total_len;
569 U64 seed;
570 U64 v1;
571 U64 v2;
572 U64 v3;
573 U64 v4;
574 U64 mem64[4]; /* defined as U64 for alignment */
575 U32 memsize;
576 }; /* typedef'd to XXH64_state_t within xxhash.h */
577
578
579 XXH_PUBLIC_API XXH32_state_t* XXH32_createState(void)
580 {
581 XXH_STATIC_ASSERT(sizeof(XXH32_stateBody_t) >= sizeof(XXH32_state_t)); /* A compilation error here means XXH32_state_t is not large enough */
582 return (XXH32_state_t*)XXH_malloc(sizeof(XXH32_state_t));
583 }
584 XXH_PUBLIC_API XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr)
585 {
586 XXH_free(statePtr);
587 return XXH_OK;
588 }
589
590 XXH_PUBLIC_API XXH64_state_t* XXH64_createState(void)
591 {
592 XXH_STATIC_ASSERT(sizeof(XXH64_stateBody_t) >= sizeof(XXH64_state_t)); /* A compilation error here means XXH64_state_t is not large enough */
593 return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t));
594 }
595 XXH_PUBLIC_API XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr)
596 {
597 XXH_free(statePtr);
598 return XXH_OK;
599 }
600
601
602 /*** Hash feed ***/
603
604 XXH_PUBLIC_API XXH_errorcode XXH32_reset(XXH32_state_t* statePtr, unsigned int seed)
605 {
606 XXH32_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */
607 memset(&state, 0, sizeof(state));
608 state.seed = seed;
609 state.v1 = seed + PRIME32_1 + PRIME32_2;
610 state.v2 = seed + PRIME32_2;
611 state.v3 = seed + 0;
612 state.v4 = seed - PRIME32_1;
613 memcpy(statePtr, &state, sizeof(state));
614 return XXH_OK;
615 }
616
617
618 XXH_PUBLIC_API XXH_errorcode XXH64_reset(XXH64_state_t* statePtr, unsigned long long seed)
619 {
620 XXH64_state_t state; /* using a local state to memcpy() in order to avoid strict-aliasing warnings */
621 memset(&state, 0, sizeof(state));
622 state.seed = seed;
623 state.v1 = seed + PRIME64_1 + PRIME64_2;
624 state.v2 = seed + PRIME64_2;
625 state.v3 = seed + 0;
626 state.v4 = seed - PRIME64_1;
627 memcpy(statePtr, &state, sizeof(state));
628 return XXH_OK;
629 }
630
631
632 FORCE_INLINE XXH_errorcode XXH32_update_endian (XXH32_state_t* state, const void* input, size_t len, XXH_endianess endian)
633 {
634 const BYTE* p = (const BYTE*)input;
635 const BYTE* const bEnd = p + len;
636
637 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
638 if (input==NULL) return XXH_ERROR;
639 #endif
640
641 state->total_len += len;
642
643 if (state->memsize + len < 16) /* fill in tmp buffer */
644 {
645 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, len);
646 state->memsize += (U32)len;
647 return XXH_OK;
648 }
649
650 if (state->memsize) /* some data left from previous update */
651 {
652 XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, 16-state->memsize);
653 {
654 const U32* p32 = state->mem32;
655 state->v1 += XXH_readLE32(p32, endian) * PRIME32_2;
656 state->v1 = XXH_rotl32(state->v1, 13);
657 state->v1 *= PRIME32_1;
658 p32++;
659 state->v2 += XXH_readLE32(p32, endian) * PRIME32_2;
660 state->v2 = XXH_rotl32(state->v2, 13);
661 state->v2 *= PRIME32_1;
662 p32++;
663 state->v3 += XXH_readLE32(p32, endian) * PRIME32_2;
664 state->v3 = XXH_rotl32(state->v3, 13);
665 state->v3 *= PRIME32_1;
666 p32++;
667 state->v4 += XXH_readLE32(p32, endian) * PRIME32_2;
668 state->v4 = XXH_rotl32(state->v4, 13);
669 state->v4 *= PRIME32_1;
670 p32++;
671 }
672 p += 16-state->memsize;
673 state->memsize = 0;
674 }
675
676 if (p <= bEnd-16)
677 {
678 const BYTE* const limit = bEnd - 16;
679 U32 v1 = state->v1;
680 U32 v2 = state->v2;
681 U32 v3 = state->v3;
682 U32 v4 = state->v4;
683
684 do
685 {
686 v1 += XXH_readLE32(p, endian) * PRIME32_2;
687 v1 = XXH_rotl32(v1, 13);
688 v1 *= PRIME32_1;
689 p+=4;
690 v2 += XXH_readLE32(p, endian) * PRIME32_2;
691 v2 = XXH_rotl32(v2, 13);
692 v2 *= PRIME32_1;
693 p+=4;
694 v3 += XXH_readLE32(p, endian) * PRIME32_2;
695 v3 = XXH_rotl32(v3, 13);
696 v3 *= PRIME32_1;
697 p+=4;
698 v4 += XXH_readLE32(p, endian) * PRIME32_2;
699 v4 = XXH_rotl32(v4, 13);
700 v4 *= PRIME32_1;
701 p+=4;
702 }
703 while (p<=limit);
704
705 state->v1 = v1;
706 state->v2 = v2;
707 state->v3 = v3;
708 state->v4 = v4;
709 }
710
711 if (p < bEnd)
712 {
713 XXH_memcpy(state->mem32, p, bEnd-p);
714 state->memsize = (int)(bEnd-p);
715 }
716
717 return XXH_OK;
718 }
719
720 XXH_PUBLIC_API XXH_errorcode XXH32_update (XXH32_state_t* state_in, const void* input, size_t len)
721 {
722 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
723
724 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
725 return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
726 else
727 return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
728 }
729
730
731
732 FORCE_INLINE U32 XXH32_digest_endian (const XXH32_state_t* state, XXH_endianess endian)
733 {
734 const BYTE * p = (const BYTE*)state->mem32;
735 const BYTE* bEnd = (const BYTE*)(state->mem32) + state->memsize;
736 U32 h32;
737
738 if (state->total_len >= 16)
739 {
740 h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
741 }
742 else
743 {
744 h32 = state->seed + PRIME32_5;
745 }
746
747 h32 += (U32) state->total_len;
748
749 while (p+4<=bEnd)
750 {
751 h32 += XXH_readLE32(p, endian) * PRIME32_3;
752 h32 = XXH_rotl32(h32, 17) * PRIME32_4;
753 p+=4;
754 }
755
756 while (p<bEnd)
757 {
758 h32 += (*p) * PRIME32_5;
759 h32 = XXH_rotl32(h32, 11) * PRIME32_1;
760 p++;
761 }
762
763 h32 ^= h32 >> 15;
764 h32 *= PRIME32_2;
765 h32 ^= h32 >> 13;
766 h32 *= PRIME32_3;
767 h32 ^= h32 >> 16;
768
769 return h32;
770 }
771
772
773 XXH_PUBLIC_API unsigned int XXH32_digest (const XXH32_state_t* state_in)
774 {
775 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
776
777 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
778 return XXH32_digest_endian(state_in, XXH_littleEndian);
779 else
780 return XXH32_digest_endian(state_in, XXH_bigEndian);
781 }
782
783
784
785 /* **** XXH64 **** */
786
787 FORCE_INLINE XXH_errorcode XXH64_update_endian (XXH64_state_t* state, const void* input, size_t len, XXH_endianess endian)
788 {
789 const BYTE* p = (const BYTE*)input;
790 const BYTE* const bEnd = p + len;
791
792 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
793 if (input==NULL) return XXH_ERROR;
794 #endif
795
796 state->total_len += len;
797
798 if (state->memsize + len < 32) /* fill in tmp buffer */
799 {
800 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, len);
801 state->memsize += (U32)len;
802 return XXH_OK;
803 }
804
805 if (state->memsize) /* some data left from previous update */
806 {
807 XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, 32-state->memsize);
808 {
809 const U64* p64 = state->mem64;
810 state->v1 += XXH_readLE64(p64, endian) * PRIME64_2;
811 state->v1 = XXH_rotl64(state->v1, 31);
812 state->v1 *= PRIME64_1;
813 p64++;
814 state->v2 += XXH_readLE64(p64, endian) * PRIME64_2;
815 state->v2 = XXH_rotl64(state->v2, 31);
816 state->v2 *= PRIME64_1;
817 p64++;
818 state->v3 += XXH_readLE64(p64, endian) * PRIME64_2;
819 state->v3 = XXH_rotl64(state->v3, 31);
820 state->v3 *= PRIME64_1;
821 p64++;
822 state->v4 += XXH_readLE64(p64, endian) * PRIME64_2;
823 state->v4 = XXH_rotl64(state->v4, 31);
824 state->v4 *= PRIME64_1;
825 p64++;
826 }
827 p += 32-state->memsize;
828 state->memsize = 0;
829 }
830
831 if (p+32 <= bEnd)
832 {
833 const BYTE* const limit = bEnd - 32;
834 U64 v1 = state->v1;
835 U64 v2 = state->v2;
836 U64 v3 = state->v3;
837 U64 v4 = state->v4;
838
839 do
840 {
841 v1 += XXH_readLE64(p, endian) * PRIME64_2;
842 v1 = XXH_rotl64(v1, 31);
843 v1 *= PRIME64_1;
844 p+=8;
845 v2 += XXH_readLE64(p, endian) * PRIME64_2;
846 v2 = XXH_rotl64(v2, 31);
847 v2 *= PRIME64_1;
848 p+=8;
849 v3 += XXH_readLE64(p, endian) * PRIME64_2;
850 v3 = XXH_rotl64(v3, 31);
851 v3 *= PRIME64_1;
852 p+=8;
853 v4 += XXH_readLE64(p, endian) * PRIME64_2;
854 v4 = XXH_rotl64(v4, 31);
855 v4 *= PRIME64_1;
856 p+=8;
857 }
858 while (p<=limit);
859
860 state->v1 = v1;
861 state->v2 = v2;
862 state->v3 = v3;
863 state->v4 = v4;
864 }
865
866 if (p < bEnd)
867 {
868 XXH_memcpy(state->mem64, p, bEnd-p);
869 state->memsize = (int)(bEnd-p);
870 }
871
872 return XXH_OK;
873 }
874
875 XXH_PUBLIC_API XXH_errorcode XXH64_update (XXH64_state_t* state_in, const void* input, size_t len)
876 {
877 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
878
879 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
880 return XXH64_update_endian(state_in, input, len, XXH_littleEndian);
881 else
882 return XXH64_update_endian(state_in, input, len, XXH_bigEndian);
883 }
884
885
886
887 FORCE_INLINE U64 XXH64_digest_endian (const XXH64_state_t* state, XXH_endianess endian)
888 {
889 const BYTE * p = (const BYTE*)state->mem64;
890 const BYTE* bEnd = (const BYTE*)state->mem64 + state->memsize;
891 U64 h64;
892
893 if (state->total_len >= 32)
894 {
895 U64 v1 = state->v1;
896 U64 v2 = state->v2;
897 U64 v3 = state->v3;
898 U64 v4 = state->v4;
899
900 h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
901
902 v1 *= PRIME64_2;
903 v1 = XXH_rotl64(v1, 31);
904 v1 *= PRIME64_1;
905 h64 ^= v1;
906 h64 = h64*PRIME64_1 + PRIME64_4;
907
908 v2 *= PRIME64_2;
909 v2 = XXH_rotl64(v2, 31);
910 v2 *= PRIME64_1;
911 h64 ^= v2;
912 h64 = h64*PRIME64_1 + PRIME64_4;
913
914 v3 *= PRIME64_2;
915 v3 = XXH_rotl64(v3, 31);
916 v3 *= PRIME64_1;
917 h64 ^= v3;
918 h64 = h64*PRIME64_1 + PRIME64_4;
919
920 v4 *= PRIME64_2;
921 v4 = XXH_rotl64(v4, 31);
922 v4 *= PRIME64_1;
923 h64 ^= v4;
924 h64 = h64*PRIME64_1 + PRIME64_4;
925 }
926 else
927 {
928 h64 = state->seed + PRIME64_5;
929 }
930
931 h64 += (U64) state->total_len;
932
933 while (p+8<=bEnd)
934 {
935 U64 k1 = XXH_readLE64(p, endian);
936 k1 *= PRIME64_2;
937 k1 = XXH_rotl64(k1,31);
938 k1 *= PRIME64_1;
939 h64 ^= k1;
940 h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
941 p+=8;
942 }
943
944 if (p+4<=bEnd)
945 {
946 h64 ^= (U64)(XXH_readLE32(p, endian)) * PRIME64_1;
947 h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
948 p+=4;
949 }
950
951 while (p<bEnd)
952 {
953 h64 ^= (*p) * PRIME64_5;
954 h64 = XXH_rotl64(h64, 11) * PRIME64_1;
955 p++;
956 }
957
958 h64 ^= h64 >> 33;
959 h64 *= PRIME64_2;
960 h64 ^= h64 >> 29;
961 h64 *= PRIME64_3;
962 h64 ^= h64 >> 32;
963
964 return h64;
965 }
966
967
968 XXH_PUBLIC_API unsigned long long XXH64_digest (const XXH64_state_t* state_in)
969 {
970 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
971
972 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
973 return XXH64_digest_endian(state_in, XXH_littleEndian);
974 else
975 return XXH64_digest_endian(state_in, XXH_bigEndian);
976 }
977
978
979 /* **************************
980 * Canonical representation
981 ****************************/
982
983 /*! Default XXH result types are basic unsigned 32 and 64 bits.
984 * The canonical representation follows human-readable write convention, aka big-endian (large digits first).
985 * These functions allow transformation of hash result into and from its canonical format.
986 * This way, hash values can be written into a file or buffer, and remain comparable across different systems and programs.
987 */
988
989 XXH_PUBLIC_API void XXH32_canonicalFromHash(XXH32_canonical_t* dst, XXH32_hash_t hash)
990 {
991 XXH_STATIC_ASSERT(sizeof(XXH32_canonical_t) == sizeof(XXH32_hash_t));
992 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap32(hash);
993 memcpy(dst, &hash, sizeof(*dst));
994 }
995
996 XXH_PUBLIC_API void XXH64_canonicalFromHash(XXH64_canonical_t* dst, XXH64_hash_t hash)
997 {
998 XXH_STATIC_ASSERT(sizeof(XXH64_canonical_t) == sizeof(XXH64_hash_t));
999 if (XXH_CPU_LITTLE_ENDIAN) hash = XXH_swap64(hash);
1000 memcpy(dst, &hash, sizeof(*dst));
1001 }
1002
1003 XXH_PUBLIC_API XXH32_hash_t XXH32_hashFromCanonical(const XXH32_canonical_t* src)
1004 {
1005 return XXH_readBE32(src);
1006 }
1007
1008 XXH_PUBLIC_API XXH64_hash_t XXH64_hashFromCanonical(const XXH64_canonical_t* src)
1009 {
1010 return XXH_readBE64(src);
1011 }
1012
Ceph