crc/xxhash.c

   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
 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
 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
 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 //****************************
 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
 224 uint32_t XXH32(const void* input, int 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
 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
 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
 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
 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
 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
 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
 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
 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 }