2 xxHash - Fast Hash algorithm
3 Copyright (C) 2012-2013, 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/
34 //**************************************
36 //**************************************
37 // Unaligned memory access is automatically enabled for "common" CPU, such as x86.
38 // For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected.
39 // If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance.
40 // You can also enable this parameter if you know your input data will always be aligned (boundaries of 4, for U32).
41 #if defined(__ARM_FEATURE_UNALIGNED) || defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
42 # define XXH_USE_UNALIGNED_ACCESS 1
45 // XXH_ACCEPT_NULL_INPUT_POINTER :
46 // If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer.
47 // When this option is enabled, xxHash output for null input pointers will be the same as a null-length input.
48 // This option has a very small performance cost (only measurable on small inputs).
49 // By default, this option is disabled. To enable it, uncomment below define :
50 //#define XXH_ACCEPT_NULL_INPUT_POINTER 1
52 // XXH_FORCE_NATIVE_FORMAT :
53 // By default, xxHash library provides endian-independant Hash values, based on little-endian convention.
54 // Results are therefore identical for little-endian and big-endian CPU.
55 // This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format.
56 // Should endian-independance be of no importance for your application, you may set the #define below to 1.
57 // It will improve speed for Big-endian CPU.
58 // This option has no impact on Little_Endian CPU.
59 #define XXH_FORCE_NATIVE_FORMAT 0
62 //**************************************
63 // Compiler Specific Options
64 //**************************************
65 // Disable some Visual warning messages
66 #ifdef _MSC_VER // Visual Studio
67 # pragma warning(disable : 4127) // disable: C4127: conditional expression is constant
70 #ifdef _MSC_VER // Visual Studio
71 # define forceinline static __forceinline
74 # define forceinline static inline __attribute__((always_inline))
76 # define forceinline static inline
81 //**************************************
82 // Includes & Memory related functions
83 //**************************************
85 // Modify the local functions below should you wish to use some other memory related routines
86 // for malloc(), free()
88 forceinline void* XXH_malloc(size_t s) { return malloc(s); }
89 forceinline void XXH_free (void* p) { free(p); }
92 forceinline void* XXH_memcpy(void* dest, const void* src, size_t size) { return memcpy(dest,src,size); }
95 //**************************************
97 //**************************************
98 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L // C99
100 typedef uint8_t BYTE;
101 typedef uint16_t U16;
102 typedef uint32_t U32;
104 typedef uint64_t U64;
106 typedef unsigned char BYTE;
107 typedef unsigned short U16;
108 typedef unsigned int U32;
109 typedef signed int S32;
110 typedef unsigned long long U64;
113 #if defined(__GNUC__) && !defined(XXH_USE_UNALIGNED_ACCESS)
114 # define _PACKED __attribute__ ((packed))
119 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
123 # pragma pack(push, 1)
127 typedef struct _U32_S { U32 v; } _PACKED U32_S;
129 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
133 #define A32(x) (((U32_S *)(x))->v)
136 //***************************************
137 // Compiler-specific Functions and Macros
138 //***************************************
139 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
141 // Note : although _rotl exists for minGW (GCC under windows), performance seems poor
142 #if defined(_MSC_VER)
143 # define XXH_rotl32(x,r) _rotl(x,r)
145 # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
148 #if defined(_MSC_VER) // Visual Studio
149 # define XXH_swap32 _byteswap_ulong
150 #elif GCC_VERSION >= 403
151 # define XXH_swap32 __builtin_bswap32
153 static inline U32 XXH_swap32 (U32 x) {
154 return ((x << 24) & 0xff000000 ) |
155 ((x << 8) & 0x00ff0000 ) |
156 ((x >> 8) & 0x0000ff00 ) |
157 ((x >> 24) & 0x000000ff );}
161 //**************************************
163 //**************************************
164 #define PRIME32_1 2654435761U
165 #define PRIME32_2 2246822519U
166 #define PRIME32_3 3266489917U
167 #define PRIME32_4 668265263U
168 #define PRIME32_5 374761393U
171 //**************************************
172 // Architecture Macros
173 //**************************************
174 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess;
175 #ifndef XXH_CPU_LITTLE_ENDIAN // It is possible to define XXH_CPU_LITTLE_ENDIAN externally, for example using a compiler switch
176 static const int one = 1;
177 # define XXH_CPU_LITTLE_ENDIAN (*(char*)(&one))
181 //**************************************
183 //**************************************
184 #define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(!!(c)) }; } // use only *after* variable declarations
187 //****************************
189 //****************************
190 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
192 forceinline U32 XXH_readLE32_align(const U32* ptr, XXH_endianess endian, XXH_alignment align)
194 if (align==XXH_unaligned)
195 return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr));
197 return endian==XXH_littleEndian ? *ptr : XXH_swap32(*ptr);
200 forceinline U32 XXH_readLE32(const U32* ptr, XXH_endianess endian) { return XXH_readLE32_align(ptr, endian, XXH_unaligned); }
203 //****************************
204 // Simple Hash Functions
205 //****************************
206 forceinline U32 XXH32_endian_align(const void* input, int len, U32 seed, XXH_endianess endian, XXH_alignment align)
208 const BYTE* p = (const BYTE*)input;
209 const BYTE* const bEnd = p + len;
212 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
213 if (p==NULL) { len=0; p=(const BYTE*)(size_t)16; }
218 const BYTE* const limit = bEnd - 16;
219 U32 v1 = seed + PRIME32_1 + PRIME32_2;
220 U32 v2 = seed + PRIME32_2;
222 U32 v4 = seed - PRIME32_1;
226 v1 += XXH_readLE32_align((const U32*)p, endian, align) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
227 v2 += XXH_readLE32_align((const U32*)p, endian, align) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
228 v3 += XXH_readLE32_align((const U32*)p, endian, align) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
229 v4 += XXH_readLE32_align((const U32*)p, endian, align) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
232 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
236 h32 = seed + PRIME32_5;
243 h32 += XXH_readLE32_align((const U32*)p, endian, align) * PRIME32_3;
244 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
250 h32 += (*p) * PRIME32_5;
251 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
265 U32 XXH32(const void* input, int len, U32 seed)
268 // Simple version, good for code maintenance, but unfortunately slow for small inputs
269 void* state = XXH32_init(seed);
270 XXH32_update(state, input, len);
271 return XXH32_digest(state);
273 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
275 # if !defined(XXH_USE_UNALIGNED_ACCESS)
276 if (!(((size_t)input) & 3)) // Input is aligned, let's leverage the speed advantage
278 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
279 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
281 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
285 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
286 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
288 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
293 //****************************
294 // Advanced Hash Functions
295 //****************************
310 int XXH32_sizeofState(void)
312 XXH_STATIC_ASSERT(XXH32_SIZEOFSTATE >= sizeof(struct XXH_state32_t)); // A compilation error here means XXH32_SIZEOFSTATE is not large enough
313 return sizeof(struct XXH_state32_t);
317 XXH_errorcode XXH32_resetState(void* state_in, U32 seed)
319 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
321 state->v1 = seed + PRIME32_1 + PRIME32_2;
322 state->v2 = seed + PRIME32_2;
323 state->v3 = seed + 0;
324 state->v4 = seed - PRIME32_1;
325 state->total_len = 0;
331 void* XXH32_init (U32 seed)
333 void* state = XXH_malloc (sizeof(struct XXH_state32_t));
334 XXH32_resetState(state, seed);
339 forceinline XXH_errorcode XXH32_update_endian (void* state_in, const void* input, int len, XXH_endianess endian)
341 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
342 const BYTE* p = (const BYTE*)input;
343 const BYTE* const bEnd = p + len;
345 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
346 if (input==NULL) return XXH_ERROR;
349 state->total_len += len;
351 if (state->memsize + len < 16) // fill in tmp buffer
353 XXH_memcpy(state->memory + state->memsize, input, len);
354 state->memsize += len;
358 if (state->memsize) // some data left from previous update
360 XXH_memcpy(state->memory + state->memsize, input, 16-state->memsize);
362 const U32* p32 = (const U32*)state->memory;
363 state->v1 += XXH_readLE32(p32, endian) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++;
364 state->v2 += XXH_readLE32(p32, endian) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++;
365 state->v3 += XXH_readLE32(p32, endian) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++;
366 state->v4 += XXH_readLE32(p32, endian) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++;
368 p += 16-state->memsize;
374 const BYTE* const limit = bEnd - 16;
382 v1 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
383 v2 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
384 v3 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
385 v4 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
396 XXH_memcpy(state->memory, p, bEnd-p);
397 state->memsize = (int)(bEnd-p);
403 XXH_errorcode XXH32_update (void* state_in, const void* input, int len)
405 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
407 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
408 return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
410 return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
415 forceinline U32 XXH32_intermediateDigest_endian (void* state_in, XXH_endianess endian)
417 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
418 const BYTE * p = (const BYTE*)state->memory;
419 BYTE* bEnd = (BYTE*)state->memory + state->memsize;
422 if (state->total_len >= 16)
424 h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
428 h32 = state->seed + PRIME32_5;
431 h32 += (U32) state->total_len;
435 h32 += XXH_readLE32((const U32*)p, endian) * PRIME32_3;
436 h32 = XXH_rotl32(h32, 17) * PRIME32_4;
442 h32 += (*p) * PRIME32_5;
443 h32 = XXH_rotl32(h32, 11) * PRIME32_1;
457 U32 XXH32_intermediateDigest (void* state_in)
459 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
461 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
462 return XXH32_intermediateDigest_endian(state_in, XXH_littleEndian);
464 return XXH32_intermediateDigest_endian(state_in, XXH_bigEndian);
468 U32 XXH32_digest (void* state_in)
470 U32 h32 = XXH32_intermediateDigest(state_in);