• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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  
33  
34  //**************************************
35  // Tuning parameters
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
43  #endif
44  
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
51  
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
60  
61  
62  //**************************************
63  // Includes & Memory related functions
64  //**************************************
65  #include "xxhash.h"
66  #include <stdlib.h>
67  #include <string.h>
68  
69  
70  #if defined(__GNUC__)  && !defined(XXH_USE_UNALIGNED_ACCESS)
71  #  define _PACKED __attribute__ ((packed))
72  #else
73  #  define _PACKED
74  #endif
75  
76  #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
77  #  ifdef __IBMC__
78  #    pragma pack(1)
79  #  else
80  #    pragma pack(push, 1)
81  #  endif
82  #endif
83  
84  typedef struct _uint32_t_S { uint32_t v; } _PACKED uint32_t_S;
85  
86  #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
87  #  pragma pack(pop)
88  #endif
89  
90  #define A32(x) (((uint32_t_S *)(x))->v)
91  
92  
93  //***************************************
94  // Compiler-specific Functions and Macros
95  //***************************************
96  #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
97  
98  // Note : although _rotl exists for minGW (GCC under windows), performance seems poor
99  #if defined(_MSC_VER)
100  #  define XXH_rotl32(x,r) _rotl(x,r)
101  #else
102  #  define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
103  #endif
104  
105  #if defined(_MSC_VER)     // Visual Studio
106  #  define XXH_swap32 _byteswap_ulong
107  #elif GCC_VERSION >= 403
108  #  define XXH_swap32 __builtin_bswap32
109  #else
XXH_swap32(uint32_t x)110  static inline uint32_t XXH_swap32 (uint32_t x)
111  {
112      return  ((x << 24) & 0xff000000 ) |
113          ((x <<  8) & 0x00ff0000 ) |
114          ((x >>  8) & 0x0000ff00 ) |
115          ((x >> 24) & 0x000000ff );
116  }
117  #endif
118  
119  
120  //**************************************
121  // Constants
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
128  
129  
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))
137  #endif
138  
139  
140  //**************************************
141  // Macros
142  //**************************************
143  #define XXH_STATIC_ASSERT(c)   { enum { XXH_static_assert = 1/(!!(c)) }; }    // use only *after* variable declarations
144  
145  
146  //****************************
147  // Memory reads
148  //****************************
149  typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
150  
XXH_readLE32_align(const uint32_t * ptr,XXH_endianess endian,XXH_alignment align)151  static uint32_t XXH_readLE32_align(const uint32_t* ptr, XXH_endianess endian, XXH_alignment align)
152  {
153      if (align==XXH_unaligned)
154          return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr));
155      else
156          return endian==XXH_littleEndian ? *ptr : XXH_swap32(*ptr);
157  }
158  
XXH_readLE32(const uint32_t * ptr,XXH_endianess endian)159  static uint32_t XXH_readLE32(const uint32_t* ptr, XXH_endianess endian) { return XXH_readLE32_align(ptr, endian, XXH_unaligned); }
160  
161  
162  //****************************
163  // Simple Hash Functions
164  //****************************
XXH32_endian_align(const void * input,int len,uint32_t seed,XXH_endianess endian,XXH_alignment align)165  static uint32_t XXH32_endian_align(const void* input, int len, uint32_t seed, XXH_endianess endian, XXH_alignment align)
166  {
167      const uint8_t *p = (const uint8_t *)input;
168      const uint8_t * const bEnd = p + len;
169      uint32_t h32;
170  
171  #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
172      if (p==NULL) { len=0; p=(const uint8_t *)(size_t)16; }
173  #endif
174  
175      if (len>=16)
176      {
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;
182  
183          do
184          {
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;
189          } while (p<=limit);
190  
191          h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
192      }
193      else
194      {
195          h32  = seed + PRIME32_5;
196      }
197  
198      h32 += (uint32_t) len;
199  
200      while (p<=bEnd-4)
201      {
202          h32 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_3;
203          h32  = XXH_rotl32(h32, 17) * PRIME32_4 ;
204          p+=4;
205      }
206  
207      while (p<bEnd)
208      {
209          h32 += (*p) * PRIME32_5;
210          h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
211          p++;
212      }
213  
214      h32 ^= h32 >> 15;
215      h32 *= PRIME32_2;
216      h32 ^= h32 >> 13;
217      h32 *= PRIME32_3;
218      h32 ^= h32 >> 16;
219  
220      return h32;
221  }
222  
223  
XXH32(const void * input,uint32_t len,uint32_t seed)224  uint32_t XXH32(const void* input, uint32_t len, uint32_t seed)
225  {
226  #if 0
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);
231  #else
232      XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
233  
234  #  if !defined(XXH_USE_UNALIGNED_ACCESS)
235      if ((((size_t)input) & 3))   // Input is aligned, let's leverage the speed advantage
236      {
237          if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
238              return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
239          else
240              return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
241      }
242  #  endif
243  
244      if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
245          return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
246      else
247          return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
248  #endif
249  }
250  
251  
252  //****************************
253  // Advanced Hash Functions
254  //****************************
255  
XXH32_sizeofState(void)256  int XXH32_sizeofState(void)
257  {
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);
260  }
261  
262  
XXH32_resetState(void * state_in,uint32_t seed)263  XXH_errorcode XXH32_resetState(void* state_in, uint32_t seed)
264  {
265      struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
266      state->seed = seed;
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;
272      state->memsize = 0;
273      return XXH_OK;
274  }
275  
276  
XXH32_init(uint32_t seed)277  void* XXH32_init (uint32_t seed)
278  {
279      void *state = malloc (sizeof(struct XXH_state32_t));
280      XXH32_resetState(state, seed);
281      return state;
282  }
283  
284  
XXH32_update_endian(void * state_in,const void * input,int len,XXH_endianess endian)285  static XXH_errorcode XXH32_update_endian (void* state_in, const void* input, int len, XXH_endianess endian)
286  {
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;
290  
291  #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
292      if (input==NULL) return XXH_ERROR;
293  #endif
294  
295      state->total_len += len;
296  
297      if (state->memsize + len < 16)   // fill in tmp buffer
298      {
299          memcpy(state->memory + state->memsize, input, len);
300          state->memsize +=  len;
301          return XXH_OK;
302      }
303  
304      if (state->memsize)   // some data left from previous update
305      {
306          memcpy(state->memory + state->memsize, input, 16-state->memsize);
307          {
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++;
313          }
314          p += 16-state->memsize;
315          state->memsize = 0;
316      }
317  
318      if (p <= bEnd-16)
319      {
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;
325  
326          do
327          {
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;
332          } while (p<=limit);
333  
334          state->v1 = v1;
335          state->v2 = v2;
336          state->v3 = v3;
337          state->v4 = v4;
338      }
339  
340      if (p < bEnd)
341      {
342          memcpy(state->memory, p, bEnd-p);
343          state->memsize = (int)(bEnd-p);
344      }
345  
346      return XXH_OK;
347  }
348  
XXH32_update(void * state_in,const void * input,int len)349  XXH_errorcode XXH32_update (void* state_in, const void* input, int len)
350  {
351      XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
352  
353      if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
354          return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
355      else
356          return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
357  }
358  
359  
360  
XXH32_intermediateDigest_endian(void * state_in,XXH_endianess endian)361  static uint32_t XXH32_intermediateDigest_endian (void* state_in, XXH_endianess endian)
362  {
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;
366      uint32_t h32;
367  
368      if (state->total_len >= 16)
369      {
370          h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
371      }
372      else
373      {
374          h32  = state->seed + PRIME32_5;
375      }
376  
377      h32 += (uint32_t) state->total_len;
378  
379      while (p<=bEnd-4)
380      {
381          h32 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_3;
382          h32  = XXH_rotl32(h32, 17) * PRIME32_4;
383          p+=4;
384      }
385  
386      while (p<bEnd)
387      {
388          h32 += (*p) * PRIME32_5;
389          h32 = XXH_rotl32(h32, 11) * PRIME32_1;
390          p++;
391      }
392  
393      h32 ^= h32 >> 15;
394      h32 *= PRIME32_2;
395      h32 ^= h32 >> 13;
396      h32 *= PRIME32_3;
397      h32 ^= h32 >> 16;
398  
399      return h32;
400  }
401  
402  
XXH32_intermediateDigest(void * state_in)403  uint32_t XXH32_intermediateDigest (void* state_in)
404  {
405      XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
406  
407      if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
408          return XXH32_intermediateDigest_endian(state_in, XXH_littleEndian);
409      else
410          return XXH32_intermediateDigest_endian(state_in, XXH_bigEndian);
411  }
412  
413  
XXH32_digest(void * state_in)414  uint32_t XXH32_digest (void* state_in)
415  {
416      uint32_t h32 = XXH32_intermediateDigest(state_in);
417  
418      free(state_in);
419  
420      return h32;
421  }
422