contrib/libucl/src/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 - public discussion board : https://groups.google.com/forum/#!forum/lz4c
  32 */
  33
  34
  35 //**************************************
  36 // Tuning parameters
  37 //**************************************
  38 // Unaligned memory access is automatically enabled for "common" CPU, such as x86.
  39 // For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected.
  40 // If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance.
  41 // You can also enable this parameter if you know your input data will always be aligned (boundaries of 4, for U32).
  42 #if defined(__ARM_FEATURE_UNALIGNED) || defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
  43 #  define XXH_USE_UNALIGNED_ACCESS 1
  44 #endif
  45
  46 // XXH_ACCEPT_NULL_INPUT_POINTER :
  47 // If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer.
  48 // When this option is enabled, xxHash output for null input pointers will be the same as a null-length input.
  49 // This option has a very small performance cost (only measurable on small inputs).
  50 // By default, this option is disabled. To enable it, uncomment below define :
  51 // #define XXH_ACCEPT_NULL_INPUT_POINTER 1
  52
  53 // XXH_FORCE_NATIVE_FORMAT :
  54 // By default, xxHash library provides endian-independant Hash values, based on little-endian convention.
  55 // Results are therefore identical for little-endian and big-endian CPU.
  56 // This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format.
  57 // Should endian-independance be of no importance for your application, you may set the #define below to 1.
  58 // It will improve speed for Big-endian CPU.
  59 // This option has no impact on Little_Endian CPU.
  60 #define XXH_FORCE_NATIVE_FORMAT 0
  61
  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
  68 #endif
  69
  70 #ifdef _MSC_VER    // Visual Studio
  71 #  define FORCE_INLINE static __forceinline
  72 #else
  73 #  ifdef __GNUC__
  74 #    define FORCE_INLINE static inline __attribute__((always_inline))
  75 #  else
  76 #    define FORCE_INLINE static inline
  77 #  endif
  78 #endif
  79
  80 //**************************************
  81 // Includes & Memory related functions
  82 //**************************************
  83 #include "xxhash.h"
  84 // Modify the local functions below should you wish to use some other memory routines
  85 // for malloc(), free()
  86 #include <stdlib.h>
  87 static void* XXH_malloc(size_t s) { return malloc(s); }
  88 static void  XXH_free  (void* p)  { free(p); }
  89 // for memcpy()
  90 #include <string.h>
  91 static void* XXH_memcpy(void* dest, const void* src, size_t size)
  92 {
  93     return memcpy(dest,src,size);
  94 }
  95
  96
  97 //**************************************
  98 // Basic Types
  99 //**************************************
 100 #if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L   // C99
 101 # include <stdint.h>
 102 typedef uint8_t  BYTE;
 103 typedef uint16_t U16;
 104 typedef uint32_t U32;
 105 typedef  int32_t S32;
 106 typedef uint64_t U64;
 107 #else
 108 typedef unsigned char      BYTE;
 109 typedef unsigned short     U16;
 110 typedef unsigned int       U32;
 111 typedef   signed int       S32;
 112 typedef uint64_t U64;
 113 #endif
 114
 115 #if defined(__GNUC__)  && !defined(XXH_USE_UNALIGNED_ACCESS)
 116 #  define _PACKED __attribute__ ((packed))
 117 #else
 118 #  define _PACKED
 119 #endif
 120
 121 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
 122 #  ifdef __IBMC__
 123 #    pragma pack(1)
 124 #  else
 125 #    pragma pack(push, 1)
 126 #  endif
 127 #endif
 128
 129 typedef struct _U32_S
 130 {
 131     U32 v;
 132 } _PACKED U32_S;
 133 typedef struct _U64_S
 134 {
 135     U64 v;
 136 } _PACKED U64_S;
 137
 138 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
 139 #  pragma pack(pop)
 140 #endif
 141
 142 #define A32(x) (((U32_S *)(x))->v)
 143 #define A64(x) (((U64_S *)(x))->v)
 144
 145
 146 //***************************************
 147 // Compiler-specific Functions and Macros
 148 //***************************************
 149 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
 150
 151 // Note : although _rotl exists for minGW (GCC under windows), performance seems poor
 152 #if defined(_MSC_VER)
 153 #  define XXH_rotl32(x,r) _rotl(x,r)
 154 #  define XXH_rotl64(x,r) _rotl64(x,r)
 155 #else
 156 #  define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
 157 #  define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r)))
 158 #endif
 159
 160 #if defined(_MSC_VER)     // Visual Studio
 161 #  define XXH_swap32 _byteswap_ulong
 162 #  define XXH_swap64 _byteswap_uint64
 163 #elif GCC_VERSION >= 403 || defined(__clang__)
 164 #  define XXH_swap32 __builtin_bswap32
 165 #  define XXH_swap64 __builtin_bswap64
 166 #else
 167 static inline U32 XXH_swap32 (U32 x)
 168 {
 169     return  ((x << 24) & 0xff000000 ) |
 170             ((x <<  8) & 0x00ff0000 ) |
 171             ((x >>  8) & 0x0000ff00 ) |
 172             ((x >> 24) & 0x000000ff );
 173 }
 174 static inline U64 XXH_swap64 (U64 x)
 175 {
 176     return  ((x << 56) & 0xff00000000000000ULL) |
 177             ((x << 40) & 0x00ff000000000000ULL) |
 178             ((x << 24) & 0x0000ff0000000000ULL) |
 179             ((x << 8)  & 0x000000ff00000000ULL) |
 180             ((x >> 8)  & 0x00000000ff000000ULL) |
 181             ((x >> 24) & 0x0000000000ff0000ULL) |
 182             ((x >> 40) & 0x000000000000ff00ULL) |
 183             ((x >> 56) & 0x00000000000000ffULL);
 184 }
 185 #endif
 186
 187
 188 //**************************************
 189 // Constants
 190 //**************************************
 191 #define PRIME32_1   2654435761U
 192 #define PRIME32_2   2246822519U
 193 #define PRIME32_3   3266489917U
 194 #define PRIME32_4    668265263U
 195 #define PRIME32_5    374761393U
 196
 197 #define PRIME64_1 11400714785074694791ULL
 198 #define PRIME64_2 14029467366897019727ULL
 199 #define PRIME64_3  1609587929392839161ULL
 200 #define PRIME64_4  9650029242287828579ULL
 201 #define PRIME64_5  2870177450012600261ULL
 202
 203 //**************************************
 204 // Architecture Macros
 205 //**************************************
 206 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess;
 207 #ifndef XXH_CPU_LITTLE_ENDIAN   // It is possible to define XXH_CPU_LITTLE_ENDIAN externally, for example using a compiler switch
 208 static const int one = 1;
 209 #   define XXH_CPU_LITTLE_ENDIAN   (*(char*)(&one))
 210 #endif
 211
 212
 213 //**************************************
 214 // Macros
 215 //**************************************
 216 #define XXH_STATIC_ASSERT(c)   { enum { XXH_static_assert = 1/(!!(c)) }; }    // use only *after* variable declarations
 217
 218
 219 //****************************
 220 // Memory reads
 221 //****************************
 222 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
 223
 224 FORCE_INLINE U32 XXH_readLE32_align(const void* ptr, XXH_endianess endian, XXH_alignment align)
 225 {
 226     if (align==XXH_unaligned)
 227         return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr));
 228     else
 229         return endian==XXH_littleEndian ? *(U32*)ptr : XXH_swap32(*(U32*)ptr);
 230 }
 231
 232 FORCE_INLINE U32 XXH_readLE32(const void* ptr, XXH_endianess endian)
 233 {
 234     return XXH_readLE32_align(ptr, endian, XXH_unaligned);
 235 }
 236
 237 FORCE_INLINE U64 XXH_readLE64_align(const void* ptr, XXH_endianess endian, XXH_alignment align)
 238 {
 239     if (align==XXH_unaligned)
 240         return endian==XXH_littleEndian ? A64(ptr) : XXH_swap64(A64(ptr));
 241     else
 242         return endian==XXH_littleEndian ? *(U64*)ptr : XXH_swap64(*(U64*)ptr);
 243 }
 244
 245 FORCE_INLINE U64 XXH_readLE64(const void* ptr, XXH_endianess endian)
 246 {
 247     return XXH_readLE64_align(ptr, endian, XXH_unaligned);
 248 }
 249
 250
 251 //****************************
 252 // Simple Hash Functions
 253 //****************************
 254 FORCE_INLINE U32 XXH32_endian_align(const void* input, size_t len, U32 seed, XXH_endianess endian, XXH_alignment align)
 255 {
 256     const BYTE* p = (const BYTE*)input;
 257     const BYTE* bEnd = p + len;
 258     U32 h32;
 259 #define XXH_get32bits(p) XXH_readLE32_align(p, endian, align)
 260
 261 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
 262     if (p==NULL)
 263     {
 264         len=0;
 265         bEnd=p=(const BYTE*)(size_t)16;
 266     }
 267 #endif
 268
 269     if (len>=16)
 270     {
 271         const BYTE* const limit = bEnd - 16;
 272         U32 v1 = seed + PRIME32_1 + PRIME32_2;
 273         U32 v2 = seed + PRIME32_2;
 274         U32 v3 = seed + 0;
 275         U32 v4 = seed - PRIME32_1;
 276
 277         do
 278         {
 279             v1 += XXH_get32bits(p) * PRIME32_2;
 280             v1 = XXH_rotl32(v1, 13);
 281             v1 *= PRIME32_1;
 282             p+=4;
 283             v2 += XXH_get32bits(p) * PRIME32_2;
 284             v2 = XXH_rotl32(v2, 13);
 285             v2 *= PRIME32_1;
 286             p+=4;
 287             v3 += XXH_get32bits(p) * PRIME32_2;
 288             v3 = XXH_rotl32(v3, 13);
 289             v3 *= PRIME32_1;
 290             p+=4;
 291             v4 += XXH_get32bits(p) * PRIME32_2;
 292             v4 = XXH_rotl32(v4, 13);
 293             v4 *= PRIME32_1;
 294             p+=4;
 295         }
 296         while (p<=limit);
 297
 298         h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
 299     }
 300     else
 301     {
 302         h32  = seed + PRIME32_5;
 303     }
 304
 305     h32 += (U32) len;
 306
 307     while (p+4<=bEnd)
 308     {
 309         h32 += XXH_get32bits(p) * PRIME32_3;
 310         h32  = XXH_rotl32(h32, 17) * PRIME32_4 ;
 311         p+=4;
 312     }
 313
 314     while (p<bEnd)
 315     {
 316         h32 += (*p) * PRIME32_5;
 317         h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
 318         p++;
 319     }
 320
 321     h32 ^= h32 >> 15;
 322     h32 *= PRIME32_2;
 323     h32 ^= h32 >> 13;
 324     h32 *= PRIME32_3;
 325     h32 ^= h32 >> 16;
 326
 327     return h32;
 328 }
 329
 330
 331 unsigned int XXH32 (const void* input, size_t len, unsigned seed)
 332 {
 333 #if 0
 334     // Simple version, good for code maintenance, but unfortunately slow for small inputs
 335     XXH32_state_t state;
 336     XXH32_reset(&state, seed);
 337     XXH32_update(&state, input, len);
 338     return XXH32_digest(&state);
 339 #else
 340     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
 341
 342 #  if !defined(XXH_USE_UNALIGNED_ACCESS)
 343     if ((((size_t)input) & 3) == 0)   // Input is aligned, let's leverage the speed advantage
 344     {
 345         if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 346             return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
 347         else
 348             return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
 349     }
 350 #  endif
 351
 352     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 353         return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
 354     else
 355         return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
 356 #endif
 357 }
 358
 359 FORCE_INLINE U64 XXH64_endian_align(const void* input, size_t len, U64 seed, XXH_endianess endian, XXH_alignment align)
 360 {
 361     const BYTE* p = (const BYTE*)input;
 362     const BYTE* bEnd = p + len;
 363     U64 h64;
 364 #define XXH_get64bits(p) XXH_readLE64_align(p, endian, align)
 365
 366 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
 367     if (p==NULL)
 368     {
 369         len=0;
 370         bEnd=p=(const BYTE*)(size_t)32;
 371     }
 372 #endif
 373
 374     if (len>=32)
 375     {
 376         const BYTE* const limit = bEnd - 32;
 377         U64 v1 = seed + PRIME64_1 + PRIME64_2;
 378         U64 v2 = seed + PRIME64_2;
 379         U64 v3 = seed + 0;
 380         U64 v4 = seed - PRIME64_1;
 381
 382         do
 383         {
 384             v1 += XXH_get64bits(p) * PRIME64_2;
 385             p+=8;
 386             v1 = XXH_rotl64(v1, 31);
 387             v1 *= PRIME64_1;
 388             v2 += XXH_get64bits(p) * PRIME64_2;
 389             p+=8;
 390             v2 = XXH_rotl64(v2, 31);
 391             v2 *= PRIME64_1;
 392             v3 += XXH_get64bits(p) * PRIME64_2;
 393             p+=8;
 394             v3 = XXH_rotl64(v3, 31);
 395             v3 *= PRIME64_1;
 396             v4 += XXH_get64bits(p) * PRIME64_2;
 397             p+=8;
 398             v4 = XXH_rotl64(v4, 31);
 399             v4 *= PRIME64_1;
 400         }
 401         while (p<=limit);
 402
 403         h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
 404
 405         v1 *= PRIME64_2;
 406         v1 = XXH_rotl64(v1, 31);
 407         v1 *= PRIME64_1;
 408         h64 ^= v1;
 409         h64 = h64 * PRIME64_1 + PRIME64_4;
 410
 411         v2 *= PRIME64_2;
 412         v2 = XXH_rotl64(v2, 31);
 413         v2 *= PRIME64_1;
 414         h64 ^= v2;
 415         h64 = h64 * PRIME64_1 + PRIME64_4;
 416
 417         v3 *= PRIME64_2;
 418         v3 = XXH_rotl64(v3, 31);
 419         v3 *= PRIME64_1;
 420         h64 ^= v3;
 421         h64 = h64 * PRIME64_1 + PRIME64_4;
 422
 423         v4 *= PRIME64_2;
 424         v4 = XXH_rotl64(v4, 31);
 425         v4 *= PRIME64_1;
 426         h64 ^= v4;
 427         h64 = h64 * PRIME64_1 + PRIME64_4;
 428     }
 429     else
 430     {
 431         h64  = seed + PRIME64_5;
 432     }
 433
 434     h64 += (U64) len;
 435
 436     while (p+8<=bEnd)
 437     {
 438         U64 k1 = XXH_get64bits(p);
 439         k1 *= PRIME64_2;
 440         k1 = XXH_rotl64(k1,31);
 441         k1 *= PRIME64_1;
 442         h64 ^= k1;
 443         h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
 444         p+=8;
 445     }
 446
 447     if (p+4<=bEnd)
 448     {
 449         h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1;
 450         h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
 451         p+=4;
 452     }
 453
 454     while (p<bEnd)
 455     {
 456         h64 ^= (*p) * PRIME64_5;
 457         h64 = XXH_rotl64(h64, 11) * PRIME64_1;
 458         p++;
 459     }
 460
 461     h64 ^= h64 >> 33;
 462     h64 *= PRIME64_2;
 463     h64 ^= h64 >> 29;
 464     h64 *= PRIME64_3;
 465     h64 ^= h64 >> 32;
 466
 467     return h64;
 468 }
 469
 470
 471 uint64_t XXH64 (const void* input, size_t len, uint64_t seed)
 472 {
 473 #if 0
 474     // Simple version, good for code maintenance, but unfortunately slow for small inputs
 475     XXH64_state_t state;
 476     XXH64_reset(&state, seed);
 477     XXH64_update(&state, input, len);
 478     return XXH64_digest(&state);
 479 #else
 480     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
 481
 482 #  if !defined(XXH_USE_UNALIGNED_ACCESS)
 483     if ((((size_t)input) & 7)==0)   // Input is aligned, let's leverage the speed advantage
 484     {
 485         if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 486             return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
 487         else
 488             return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
 489     }
 490 #  endif
 491
 492     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 493         return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
 494     else
 495         return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
 496 #endif
 497 }
 498
 499 /****************************************************
 500  *  Advanced Hash Functions
 501 ****************************************************/
 502
 503 /*** Allocation ***/
 504 typedef struct
 505 {
 506     U64 total_len;
 507     U32 seed;
 508     U32 v1;
 509     U32 v2;
 510     U32 v3;
 511     U32 v4;
 512     U32 mem32[4];   /* defined as U32 for alignment */
 513     U32 memsize;
 514 } XXH_istate32_t;
 515
 516 typedef struct
 517 {
 518     U64 total_len;
 519     U64 seed;
 520     U64 v1;
 521     U64 v2;
 522     U64 v3;
 523     U64 v4;
 524     U64 mem64[4];   /* defined as U64 for alignment */
 525     U32 memsize;
 526 } XXH_istate64_t;
 527
 528
 529 XXH32_state_t* XXH32_createState(void)
 530 {
 531     XXH_STATIC_ASSERT(sizeof(XXH32_state_t) >= sizeof(XXH_istate32_t));   // A compilation error here means XXH32_state_t is not large enough
 532     return (XXH32_state_t*)XXH_malloc(sizeof(XXH32_state_t));
 533 }
 534
 535 void* XXH32_init (unsigned seed)
 536 {
 537         XXH32_state_t *st = XXH32_createState();
 538         XXH32_reset(st, seed);
 539
 540         return st;
 541 }
 542
 543 XXH_errorcode XXH32_freeState(XXH32_state_t* statePtr)
 544 {
 545     XXH_free(statePtr);
 546     return XXH_OK;
 547 };
 548
 549 XXH64_state_t* XXH64_createState(void)
 550 {
 551     XXH_STATIC_ASSERT(sizeof(XXH64_state_t) >= sizeof(XXH_istate64_t));   // A compilation error here means XXH64_state_t is not large enough
 552     return (XXH64_state_t*)XXH_malloc(sizeof(XXH64_state_t));
 553 }
 554 XXH_errorcode XXH64_freeState(XXH64_state_t* statePtr)
 555 {
 556     XXH_free(statePtr);
 557     return XXH_OK;
 558 };
 559
 560
 561 /*** Hash feed ***/
 562
 563 XXH_errorcode XXH32_reset(XXH32_state_t* state_in, U32 seed)
 564 {
 565     XXH_istate32_t* state = (XXH_istate32_t*) state_in;
 566     state->seed = seed;
 567     state->v1 = seed + PRIME32_1 + PRIME32_2;
 568     state->v2 = seed + PRIME32_2;
 569     state->v3 = seed + 0;
 570     state->v4 = seed - PRIME32_1;
 571     state->total_len = 0;
 572     state->memsize = 0;
 573     return XXH_OK;
 574 }
 575
 576 XXH_errorcode XXH64_reset(XXH64_state_t* state_in, uint64_t seed)
 577 {
 578     XXH_istate64_t* state = (XXH_istate64_t*) state_in;
 579     state->seed = seed;
 580     state->v1 = seed + PRIME64_1 + PRIME64_2;
 581     state->v2 = seed + PRIME64_2;
 582     state->v3 = seed + 0;
 583     state->v4 = seed - PRIME64_1;
 584     state->total_len = 0;
 585     state->memsize = 0;
 586     return XXH_OK;
 587 }
 588
 589
 590 FORCE_INLINE XXH_errorcode XXH32_update_endian (XXH32_state_t* state_in, const void* input, size_t len, XXH_endianess endian)
 591 {
 592     XXH_istate32_t* state = (XXH_istate32_t *) state_in;
 593     const BYTE* p = (const BYTE*)input;
 594     const BYTE* const bEnd = p + len;
 595
 596 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
 597     if (input==NULL) return XXH_ERROR;
 598 #endif
 599
 600     state->total_len += len;
 601
 602     if (state->memsize + len < 16)   // fill in tmp buffer
 603     {
 604         XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, len);
 605         state->memsize += (U32)len;
 606         return XXH_OK;
 607     }
 608
 609     if (state->memsize)   // some data left from previous update
 610     {
 611         XXH_memcpy((BYTE*)(state->mem32) + state->memsize, input, 16-state->memsize);
 612         {
 613             const U32* p32 = state->mem32;
 614             state->v1 += XXH_readLE32(p32, endian) * PRIME32_2;
 615             state->v1 = XXH_rotl32(state->v1, 13);
 616             state->v1 *= PRIME32_1;
 617             p32++;
 618             state->v2 += XXH_readLE32(p32, endian) * PRIME32_2;
 619             state->v2 = XXH_rotl32(state->v2, 13);
 620             state->v2 *= PRIME32_1;
 621             p32++;
 622             state->v3 += XXH_readLE32(p32, endian) * PRIME32_2;
 623             state->v3 = XXH_rotl32(state->v3, 13);
 624             state->v3 *= PRIME32_1;
 625             p32++;
 626             state->v4 += XXH_readLE32(p32, endian) * PRIME32_2;
 627             state->v4 = XXH_rotl32(state->v4, 13);
 628             state->v4 *= PRIME32_1;
 629             p32++;
 630         }
 631         p += 16-state->memsize;
 632         state->memsize = 0;
 633     }
 634
 635     if (p <= bEnd-16)
 636     {
 637         const BYTE* const limit = bEnd - 16;
 638         U32 v1 = state->v1;
 639         U32 v2 = state->v2;
 640         U32 v3 = state->v3;
 641         U32 v4 = state->v4;
 642
 643         do
 644         {
 645             v1 += XXH_readLE32(p, endian) * PRIME32_2;
 646             v1 = XXH_rotl32(v1, 13);
 647             v1 *= PRIME32_1;
 648             p+=4;
 649             v2 += XXH_readLE32(p, endian) * PRIME32_2;
 650             v2 = XXH_rotl32(v2, 13);
 651             v2 *= PRIME32_1;
 652             p+=4;
 653             v3 += XXH_readLE32(p, endian) * PRIME32_2;
 654             v3 = XXH_rotl32(v3, 13);
 655             v3 *= PRIME32_1;
 656             p+=4;
 657             v4 += XXH_readLE32(p, endian) * PRIME32_2;
 658             v4 = XXH_rotl32(v4, 13);
 659             v4 *= PRIME32_1;
 660             p+=4;
 661         }
 662         while (p<=limit);
 663
 664         state->v1 = v1;
 665         state->v2 = v2;
 666         state->v3 = v3;
 667         state->v4 = v4;
 668     }
 669
 670     if (p < bEnd)
 671     {
 672         XXH_memcpy(state->mem32, p, bEnd-p);
 673         state->memsize = (int)(bEnd-p);
 674     }
 675
 676     return XXH_OK;
 677 }
 678
 679 XXH_errorcode XXH32_update (XXH32_state_t* state_in, const void* input, size_t len)
 680 {
 681     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
 682
 683     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 684         return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
 685     else
 686         return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
 687 }
 688
 689
 690
 691 FORCE_INLINE U32 XXH32_digest_endian (const XXH32_state_t* state_in, XXH_endianess endian)
 692 {
 693     XXH_istate32_t* state = (XXH_istate32_t*) state_in;
 694     const BYTE * p = (const BYTE*)state->mem32;
 695     BYTE* bEnd = (BYTE*)(state->mem32) + state->memsize;
 696     U32 h32;
 697
 698     if (state->total_len >= 16)
 699     {
 700         h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
 701     }
 702     else
 703     {
 704         h32  = state->seed + PRIME32_5;
 705     }
 706
 707     h32 += (U32) state->total_len;
 708
 709     while (p+4<=bEnd)
 710     {
 711         h32 += XXH_readLE32(p, endian) * PRIME32_3;
 712         h32  = XXH_rotl32(h32, 17) * PRIME32_4;
 713         p+=4;
 714     }
 715
 716     while (p<bEnd)
 717     {
 718         h32 += (*p) * PRIME32_5;
 719         h32 = XXH_rotl32(h32, 11) * PRIME32_1;
 720         p++;
 721     }
 722
 723     h32 ^= h32 >> 15;
 724     h32 *= PRIME32_2;
 725     h32 ^= h32 >> 13;
 726     h32 *= PRIME32_3;
 727     h32 ^= h32 >> 16;
 728 #if 0
 729     XXH32_freeState((XXH32_state_t *)state_in);
 730 #endif
 731     return h32;
 732 }
 733
 734
 735 U32 XXH32_digest (const XXH32_state_t* state_in)
 736 {
 737     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
 738
 739     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 740         return XXH32_digest_endian(state_in, XXH_littleEndian);
 741     else
 742         return XXH32_digest_endian(state_in, XXH_bigEndian);
 743 }
 744
 745
 746 FORCE_INLINE XXH_errorcode XXH64_update_endian (XXH64_state_t* state_in, const void* input, size_t len, XXH_endianess endian)
 747 {
 748     XXH_istate64_t * state = (XXH_istate64_t *) state_in;
 749     const BYTE* p = (const BYTE*)input;
 750     const BYTE* const bEnd = p + len;
 751
 752 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
 753     if (input==NULL) return XXH_ERROR;
 754 #endif
 755
 756     state->total_len += len;
 757
 758     if (state->memsize + len < 32)   // fill in tmp buffer
 759     {
 760         XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, len);
 761         state->memsize += (U32)len;
 762         return XXH_OK;
 763     }
 764
 765     if (state->memsize)   // some data left from previous update
 766     {
 767         XXH_memcpy(((BYTE*)state->mem64) + state->memsize, input, 32-state->memsize);
 768         {
 769             const U64* p64 = state->mem64;
 770             state->v1 += XXH_readLE64(p64, endian) * PRIME64_2;
 771             state->v1 = XXH_rotl64(state->v1, 31);
 772             state->v1 *= PRIME64_1;
 773             p64++;
 774             state->v2 += XXH_readLE64(p64, endian) * PRIME64_2;
 775             state->v2 = XXH_rotl64(state->v2, 31);
 776             state->v2 *= PRIME64_1;
 777             p64++;
 778             state->v3 += XXH_readLE64(p64, endian) * PRIME64_2;
 779             state->v3 = XXH_rotl64(state->v3, 31);
 780             state->v3 *= PRIME64_1;
 781             p64++;
 782             state->v4 += XXH_readLE64(p64, endian) * PRIME64_2;
 783             state->v4 = XXH_rotl64(state->v4, 31);
 784             state->v4 *= PRIME64_1;
 785             p64++;
 786         }
 787         p += 32-state->memsize;
 788         state->memsize = 0;
 789     }
 790
 791     if (p+32 <= bEnd)
 792     {
 793         const BYTE* const limit = bEnd - 32;
 794         U64 v1 = state->v1;
 795         U64 v2 = state->v2;
 796         U64 v3 = state->v3;
 797         U64 v4 = state->v4;
 798
 799         do
 800         {
 801             v1 += XXH_readLE64(p, endian) * PRIME64_2;
 802             v1 = XXH_rotl64(v1, 31);
 803             v1 *= PRIME64_1;
 804             p+=8;
 805             v2 += XXH_readLE64(p, endian) * PRIME64_2;
 806             v2 = XXH_rotl64(v2, 31);
 807             v2 *= PRIME64_1;
 808             p+=8;
 809             v3 += XXH_readLE64(p, endian) * PRIME64_2;
 810             v3 = XXH_rotl64(v3, 31);
 811             v3 *= PRIME64_1;
 812             p+=8;
 813             v4 += XXH_readLE64(p, endian) * PRIME64_2;
 814             v4 = XXH_rotl64(v4, 31);
 815             v4 *= PRIME64_1;
 816             p+=8;
 817         }
 818         while (p<=limit);
 819
 820         state->v1 = v1;
 821         state->v2 = v2;
 822         state->v3 = v3;
 823         state->v4 = v4;
 824     }
 825
 826     if (p < bEnd)
 827     {
 828         XXH_memcpy(state->mem64, p, bEnd-p);
 829         state->memsize = (int)(bEnd-p);
 830     }
 831
 832     return XXH_OK;
 833 }
 834
 835 XXH_errorcode XXH64_update (XXH64_state_t* state_in, const void* input, size_t len)
 836 {
 837     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
 838
 839     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 840         return XXH64_update_endian(state_in, input, len, XXH_littleEndian);
 841     else
 842         return XXH64_update_endian(state_in, input, len, XXH_bigEndian);
 843 }
 844
 845
 846
 847 FORCE_INLINE U64 XXH64_digest_endian (const XXH64_state_t* state_in, XXH_endianess endian)
 848 {
 849     XXH_istate64_t * state = (XXH_istate64_t *) state_in;
 850     const BYTE * p = (const BYTE*)state->mem64;
 851     BYTE* bEnd = (BYTE*)state->mem64 + state->memsize;
 852     U64 h64;
 853
 854     if (state->total_len >= 32)
 855     {
 856         U64 v1 = state->v1;
 857         U64 v2 = state->v2;
 858         U64 v3 = state->v3;
 859         U64 v4 = state->v4;
 860
 861         h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 12) + XXH_rotl64(v4, 18);
 862
 863         v1 *= PRIME64_2;
 864         v1 = XXH_rotl64(v1, 31);
 865         v1 *= PRIME64_1;
 866         h64 ^= v1;
 867         h64 = h64*PRIME64_1 + PRIME64_4;
 868
 869         v2 *= PRIME64_2;
 870         v2 = XXH_rotl64(v2, 31);
 871         v2 *= PRIME64_1;
 872         h64 ^= v2;
 873         h64 = h64*PRIME64_1 + PRIME64_4;
 874
 875         v3 *= PRIME64_2;
 876         v3 = XXH_rotl64(v3, 31);
 877         v3 *= PRIME64_1;
 878         h64 ^= v3;
 879         h64 = h64*PRIME64_1 + PRIME64_4;
 880
 881         v4 *= PRIME64_2;
 882         v4 = XXH_rotl64(v4, 31);
 883         v4 *= PRIME64_1;
 884         h64 ^= v4;
 885         h64 = h64*PRIME64_1 + PRIME64_4;
 886     }
 887     else
 888     {
 889         h64  = state->seed + PRIME64_5;
 890     }
 891
 892     h64 += (U64) state->total_len;
 893
 894     while (p+8<=bEnd)
 895     {
 896         U64 k1 = XXH_readLE64(p, endian);
 897         k1 *= PRIME64_2;
 898         k1 = XXH_rotl64(k1,31);
 899         k1 *= PRIME64_1;
 900         h64 ^= k1;
 901         h64 = XXH_rotl64(h64,27) * PRIME64_1 + PRIME64_4;
 902         p+=8;
 903     }
 904
 905     if (p+4<=bEnd)
 906     {
 907         h64 ^= (U64)(XXH_readLE32(p, endian)) * PRIME64_1;
 908         h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
 909         p+=4;
 910     }
 911
 912     while (p<bEnd)
 913     {
 914         h64 ^= (*p) * PRIME64_5;
 915         h64 = XXH_rotl64(h64, 11) * PRIME64_1;
 916         p++;
 917     }
 918
 919     h64 ^= h64 >> 33;
 920     h64 *= PRIME64_2;
 921     h64 ^= h64 >> 29;
 922     h64 *= PRIME64_3;
 923     h64 ^= h64 >> 32;
 924 #if 0
 925     XXH64_freeState((XXH64_state_t *)state_in);
 926 #endif
 927     return h64;
 928 }
 929
 930
 931 uint64_t XXH64_digest (const XXH64_state_t* state_in)
 932 {
 933     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
 934
 935     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 936         return XXH64_digest_endian(state_in, XXH_littleEndian);
 937     else
 938         return XXH64_digest_endian(state_in, XXH_bigEndian);
 939 }
 940
 941