2 xxHash - Fast Hash algorithm
3 Copyright (C) 2012-2014, Yann Collet.
4 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions are
10 * Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12 * Redistributions in binary form must reproduce the above
13 copyright notice, this list of conditions and the following disclaimer
14 in the documentation and/or other materials provided with the
17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 You can contact the author at :
30 - xxHash source repository : http://code.google.com/p/xxhash/
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 uint32_t).
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-independent 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-independence 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 // Includes & Memory related functions
64 //**************************************
70 #if defined(__GNUC__) && !defined(XXH_USE_UNALIGNED_ACCESS)
71 # define _PACKED __attribute__ ((packed))
76 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
80 # pragma pack(push, 1)
84 typedef struct _uint32_t_S { uint32_t v; } _PACKED uint32_t_S;
86 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
90 #define A32(x) (((uint32_t_S *)(x))->v)
93 //***************************************
94 // Compiler-specific Functions and Macros
95 //***************************************
96 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
98 // Note : although _rotl exists for minGW (GCC under windows), performance seems poor
100 # define XXH_rotl32(x,r) _rotl(x,r)
102 # define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
105 #if defined(_MSC_VER) // Visual Studio
106 # define XXH_swap32 _byteswap_ulong
107 #elif GCC_VERSION >= 403
108 # define XXH_swap32 __builtin_bswap32
110 static inline uint32_t XXH_swap32 (uint32_t x)
112 return ((x << 24) & 0xff000000 ) |
113 ((x << 8) & 0x00ff0000 ) |
114 ((x >> 8) & 0x0000ff00 ) |
115 ((x >> 24) & 0x000000ff );
120 //**************************************
122 //**************************************
123 #define PRIME32_1 2654435761U
124 #define PRIME32_2 2246822519U
125 #define PRIME32_3 3266489917U
126 #define PRIME32_4 668265263U
127 #define PRIME32_5 374761393U
130 //**************************************
131 // Architecture Macros
132 //**************************************
133 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess;
134 #ifndef XXH_CPU_LITTLE_ENDIAN // It is possible to define XXH_CPU_LITTLE_ENDIAN externally, for example using a compiler switch
135 static const int one = 1;
136 # define XXH_CPU_LITTLE_ENDIAN (*(char*)(&one))
140 //**************************************
142 //**************************************
143 #define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(!!(c)) }; } // use only *after* variable declarations
146 //****************************
148 //****************************
149 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
151 static uint32_t XXH_readLE32_align(const uint32_t* ptr, XXH_endianess endian, XXH_alignment align)
153 if (align==XXH_unaligned)
154 return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr));
156 return endian==XXH_littleEndian ? *ptr : XXH_swap32(*ptr);
159 static uint32_t XXH_readLE32(const uint32_t* ptr, XXH_endianess endian) { return XXH_readLE32_align(ptr, endian, XXH_unaligned); }
162 //****************************
163 // Simple Hash Functions
164 //****************************
165 static uint32_t XXH32_endian_align(const void* input, int len, uint32_t seed, XXH_endianess endian, XXH_alignment align)
167 const uint8_t *p = (const uint8_t *)input;
168 const uint8_t * const bEnd = p + len;
171 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
172 if (p==NULL) { len=0; p=(const uint8_t *)(size_t)16; }
177 const uint8_t * const limit = bEnd - 16;
178 uint32_t v1 = seed + PRIME32_1 + PRIME32_2;
179 uint32_t v2 = seed + PRIME32_2;
180 uint32_t v3 = seed + 0;
181 uint32_t v4 = seed - PRIME32_1;
185 v1 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
186 v2 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
187 v3 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
188 v4 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
191 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
195 h32 = seed + PRIME32_5;
198 h32 += (uint32_t) len;
202 h32 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_3;
203 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
209 h32 += (*p) * PRIME32_5;
210 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
224 uint32_t XXH32(const void* input, uint32_t len, uint32_t seed)
227 // Simple version, good for code maintenance, but unfortunately slow for small inputs
228 void* state = XXH32_init(seed);
229 XXH32_update(state, input, len);
230 return XXH32_digest(state);
232 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
234 # if !defined(XXH_USE_UNALIGNED_ACCESS)
235 if ((((size_t)input) & 3)) // Input is aligned, let's leverage the speed advantage
237 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
238 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
240 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
244 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
245 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
247 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
252 //****************************
253 // Advanced Hash Functions
254 //****************************
256 int XXH32_sizeofState(void)
258 XXH_STATIC_ASSERT(XXH32_SIZEOFSTATE >= sizeof(struct XXH_state32_t)); // A compilation error here means XXH32_SIZEOFSTATE is not large enough
259 return sizeof(struct XXH_state32_t);
263 XXH_errorcode XXH32_resetState(void* state_in, uint32_t seed)
265 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
267 state->v1 = seed + PRIME32_1 + PRIME32_2;
268 state->v2 = seed + PRIME32_2;
269 state->v3 = seed + 0;
270 state->v4 = seed - PRIME32_1;
271 state->total_len = 0;
277 void* XXH32_init (uint32_t seed)
279 void *state = malloc (sizeof(struct XXH_state32_t));
280 XXH32_resetState(state, seed);
285 static XXH_errorcode XXH32_update_endian (void* state_in, const void* input, int len, XXH_endianess endian)
287 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
288 const uint8_t *p = (const uint8_t *)input;
289 const uint8_t * const bEnd = p + len;
291 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
292 if (input==NULL) return XXH_ERROR;
295 state->total_len += len;
297 if (state->memsize + len < 16) // fill in tmp buffer
299 memcpy(state->memory + state->memsize, input, len);
300 state->memsize += len;
304 if (state->memsize) // some data left from previous update
306 memcpy(state->memory + state->memsize, input, 16-state->memsize);
308 const uint32_t* p32 = (const uint32_t*)state->memory;
309 state->v1 += XXH_readLE32(p32, endian) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++;
310 state->v2 += XXH_readLE32(p32, endian) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++;
311 state->v3 += XXH_readLE32(p32, endian) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++;
312 state->v4 += XXH_readLE32(p32, endian) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++;
314 p += 16-state->memsize;
320 const uint8_t * const limit = bEnd - 16;
321 uint32_t v1 = state->v1;
322 uint32_t v2 = state->v2;
323 uint32_t v3 = state->v3;
324 uint32_t v4 = state->v4;
328 v1 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
329 v2 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
330 v3 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
331 v4 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
342 memcpy(state->memory, p, bEnd-p);
343 state->memsize = (int)(bEnd-p);
349 XXH_errorcode XXH32_update (void* state_in, const void* input, int len)
351 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
353 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
354 return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
356 return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
361 static uint32_t XXH32_intermediateDigest_endian (void* state_in, XXH_endianess endian)
363 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
364 const uint8_t *p = (const uint8_t *)state->memory;
365 uint8_t * bEnd = (uint8_t *)state->memory + state->memsize;
368 if (state->total_len >= 16)
370 h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
374 h32 = state->seed + PRIME32_5;
377 h32 += (uint32_t) state->total_len;
381 h32 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_3;
382 h32 = XXH_rotl32(h32, 17) * PRIME32_4;
388 h32 += (*p) * PRIME32_5;
389 h32 = XXH_rotl32(h32, 11) * PRIME32_1;
403 uint32_t XXH32_intermediateDigest (void* state_in)
405 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
407 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
408 return XXH32_intermediateDigest_endian(state_in, XXH_littleEndian);
410 return XXH32_intermediateDigest_endian(state_in, XXH_bigEndian);
414 uint32_t XXH32_digest (void* state_in)
416 uint32_t h32 = XXH32_intermediateDigest(state_in);