143a63c18SDmitri Tikhonov/* 243a63c18SDmitri TikhonovxxHash - Fast Hash algorithm 343a63c18SDmitri TikhonovCopyright (C) 2012-2014, Yann Collet. 443a63c18SDmitri TikhonovBSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 543a63c18SDmitri Tikhonov 643a63c18SDmitri TikhonovRedistribution and use in source and binary forms, with or without 743a63c18SDmitri Tikhonovmodification, are permitted provided that the following conditions are 843a63c18SDmitri Tikhonovmet: 943a63c18SDmitri Tikhonov 1043a63c18SDmitri Tikhonov* Redistributions of source code must retain the above copyright 1143a63c18SDmitri Tikhonovnotice, this list of conditions and the following disclaimer. 1243a63c18SDmitri Tikhonov* Redistributions in binary form must reproduce the above 1343a63c18SDmitri Tikhonovcopyright notice, this list of conditions and the following disclaimer 1443a63c18SDmitri Tikhonovin the documentation and/or other materials provided with the 1543a63c18SDmitri Tikhonovdistribution. 1643a63c18SDmitri Tikhonov 1743a63c18SDmitri TikhonovTHIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1843a63c18SDmitri Tikhonov"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1943a63c18SDmitri TikhonovLIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2043a63c18SDmitri TikhonovA PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2143a63c18SDmitri TikhonovOWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2243a63c18SDmitri TikhonovSPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2343a63c18SDmitri TikhonovLIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2443a63c18SDmitri TikhonovDATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2543a63c18SDmitri TikhonovTHEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2643a63c18SDmitri Tikhonov(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2743a63c18SDmitri TikhonovOF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2843a63c18SDmitri Tikhonov 2943a63c18SDmitri TikhonovYou can contact the author at : 3043a63c18SDmitri Tikhonov- xxHash source repository : http://code.google.com/p/xxhash/ 3143a63c18SDmitri Tikhonov- public discussion board : https://groups.google.com/forum/#!forum/lz4c 3243a63c18SDmitri Tikhonov*/ 3343a63c18SDmitri Tikhonov 3443a63c18SDmitri Tikhonov 3543a63c18SDmitri Tikhonov//************************************** 3643a63c18SDmitri Tikhonov// Tuning parameters 3743a63c18SDmitri Tikhonov//************************************** 3843a63c18SDmitri Tikhonov// Unaligned memory access is automatically enabled for "common" CPU, such as x86. 3943a63c18SDmitri Tikhonov// For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected. 4043a63c18SDmitri Tikhonov// If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance. 4143a63c18SDmitri Tikhonov// You can also enable this parameter if you know your input data will always be aligned (boundaries of 4, for U32). 4243a63c18SDmitri Tikhonov#if defined(__ARM_FEATURE_UNALIGNED) || defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64) 4343a63c18SDmitri Tikhonov# define XXH_USE_UNALIGNED_ACCESS 1 4443a63c18SDmitri Tikhonov#endif 4543a63c18SDmitri Tikhonov 4643a63c18SDmitri Tikhonov// XXH_ACCEPT_NULL_INPUT_POINTER : 4743a63c18SDmitri Tikhonov// If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer. 4843a63c18SDmitri Tikhonov// When this option is enabled, xxHash output for null input pointers will be the same as a null-length input. 4943a63c18SDmitri Tikhonov// This option has a very small performance cost (only measurable on small inputs). 5043a63c18SDmitri Tikhonov// By default, this option is disabled. To enable it, uncomment below define : 5143a63c18SDmitri Tikhonov// #define XXH_ACCEPT_NULL_INPUT_POINTER 1 5243a63c18SDmitri Tikhonov 5343a63c18SDmitri Tikhonov// XXH_FORCE_NATIVE_FORMAT : 5443a63c18SDmitri Tikhonov// By default, xxHash library provides endian-independant Hash values, based on little-endian convention. 5543a63c18SDmitri Tikhonov// Results are therefore identical for little-endian and big-endian CPU. 5643a63c18SDmitri Tikhonov// This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format. 5743a63c18SDmitri Tikhonov// Should endian-independance be of no importance for your application, you may set the #define below to 1. 5843a63c18SDmitri Tikhonov// It will improve speed for Big-endian CPU. 5943a63c18SDmitri Tikhonov// This option has no impact on Little_Endian CPU. 6043a63c18SDmitri Tikhonov#define XXH_FORCE_NATIVE_FORMAT 0 6143a63c18SDmitri Tikhonov 6243a63c18SDmitri Tikhonov//************************************** 6343a63c18SDmitri Tikhonov// Compiler Specific Options 6443a63c18SDmitri Tikhonov//************************************** 6543a63c18SDmitri Tikhonov// Disable some Visual warning messages 6643a63c18SDmitri Tikhonov#ifdef _MSC_VER // Visual Studio 6743a63c18SDmitri Tikhonov# pragma warning(disable : 4127) // disable: C4127: conditional expression is constant 6843a63c18SDmitri Tikhonov#endif 6943a63c18SDmitri Tikhonov 7043a63c18SDmitri Tikhonov#ifdef _MSC_VER // Visual Studio 7143a63c18SDmitri Tikhonov# define FORCE_INLINE static __forceinline 7243a63c18SDmitri Tikhonov#else 7343a63c18SDmitri Tikhonov# ifdef __GNUC__ 7443a63c18SDmitri Tikhonov# define FORCE_INLINE static inline __attribute__((always_inline)) 7543a63c18SDmitri Tikhonov# else 7643a63c18SDmitri Tikhonov# define FORCE_INLINE static inline 7743a63c18SDmitri Tikhonov# endif 7843a63c18SDmitri Tikhonov#endif 7943a63c18SDmitri Tikhonov 8043a63c18SDmitri Tikhonov//************************************** 8143a63c18SDmitri Tikhonov// Includes & Memory related functions 8243a63c18SDmitri Tikhonov//************************************** 8343a63c18SDmitri Tikhonov#include "xxhash.h" 8443a63c18SDmitri Tikhonov// Modify the local functions below should you wish to use some other memory routines 8543a63c18SDmitri Tikhonov// for malloc(), free() 8643a63c18SDmitri Tikhonov#include <stdlib.h> 8743a63c18SDmitri Tikhonovstatic void *XXH_malloc(size_t s) { return malloc(s); } 8843a63c18SDmitri Tikhonovstatic void XXH_free(void *p) { free(p); } 8943a63c18SDmitri Tikhonov// for memcpy() 9043a63c18SDmitri Tikhonov#include <string.h> 9143a63c18SDmitri Tikhonovstatic void *XXH_memcpy(void *dest, const void *src, size_t size) 9243a63c18SDmitri Tikhonov{ 9343a63c18SDmitri Tikhonov return memcpy(dest, src, size); 9443a63c18SDmitri Tikhonov} 9543a63c18SDmitri Tikhonov 9643a63c18SDmitri Tikhonov 9743a63c18SDmitri Tikhonov//************************************** 9843a63c18SDmitri Tikhonov// Basic Types 9943a63c18SDmitri Tikhonov//************************************** 10043a63c18SDmitri Tikhonov#if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L // C99 10143a63c18SDmitri Tikhonov# include <stdint.h> 10243a63c18SDmitri Tikhonovtypedef uint8_t BYTE; 10343a63c18SDmitri Tikhonovtypedef uint16_t U16; 10443a63c18SDmitri Tikhonovtypedef uint32_t U32; 10543a63c18SDmitri Tikhonovtypedef int32_t S32; 10643a63c18SDmitri Tikhonovtypedef uint64_t U64; 10743a63c18SDmitri Tikhonov#else 10843a63c18SDmitri Tikhonovtypedef unsigned char BYTE; 10943a63c18SDmitri Tikhonovtypedef unsigned short U16; 11043a63c18SDmitri Tikhonovtypedef unsigned int U32; 11143a63c18SDmitri Tikhonovtypedef signed int S32; 11243a63c18SDmitri Tikhonovtypedef unsigned long long U64; 11343a63c18SDmitri Tikhonov#endif 11443a63c18SDmitri Tikhonov 11543a63c18SDmitri Tikhonov#if defined(__GNUC__) && !defined(XXH_USE_UNALIGNED_ACCESS) 11643a63c18SDmitri Tikhonov# define _PACKED __attribute__ ((packed)) 11743a63c18SDmitri Tikhonov#else 11843a63c18SDmitri Tikhonov# define _PACKED 11943a63c18SDmitri Tikhonov#endif 12043a63c18SDmitri Tikhonov 12143a63c18SDmitri Tikhonov#if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__) 12243a63c18SDmitri Tikhonov# ifdef __IBMC__ 12343a63c18SDmitri Tikhonov# pragma pack(1) 12443a63c18SDmitri Tikhonov# else 12543a63c18SDmitri Tikhonov# pragma pack(push, 1) 12643a63c18SDmitri Tikhonov# endif 12743a63c18SDmitri Tikhonov#endif 12843a63c18SDmitri Tikhonov 12943a63c18SDmitri Tikhonovtypedef struct _U32_S 13043a63c18SDmitri Tikhonov{ 13143a63c18SDmitri Tikhonov U32 v; 13243a63c18SDmitri Tikhonov} _PACKED U32_S; 13343a63c18SDmitri Tikhonovtypedef struct _U64_S 13443a63c18SDmitri Tikhonov{ 13543a63c18SDmitri Tikhonov U64 v; 13643a63c18SDmitri Tikhonov} _PACKED U64_S; 13743a63c18SDmitri Tikhonov 13843a63c18SDmitri Tikhonov#if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__) 13943a63c18SDmitri Tikhonov# pragma pack(pop) 14043a63c18SDmitri Tikhonov#endif 14143a63c18SDmitri Tikhonov 14243a63c18SDmitri Tikhonov#define A32(x) (((U32_S *)(x))->v) 14343a63c18SDmitri Tikhonov#define A64(x) (((U64_S *)(x))->v) 14443a63c18SDmitri Tikhonov 14543a63c18SDmitri Tikhonov 14643a63c18SDmitri Tikhonov//*************************************** 14743a63c18SDmitri Tikhonov// Compiler-specific Functions and Macros 14843a63c18SDmitri Tikhonov//*************************************** 14943a63c18SDmitri Tikhonov#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) 15043a63c18SDmitri Tikhonov 15143a63c18SDmitri Tikhonov// Note : although _rotl exists for minGW (GCC under windows), performance seems poor 15243a63c18SDmitri Tikhonov#if defined(_MSC_VER) 15343a63c18SDmitri Tikhonov# define XXH_rotl32(x,r) _rotl(x,r) 15443a63c18SDmitri Tikhonov# define XXH_rotl64(x,r) _rotl64(x,r) 15543a63c18SDmitri Tikhonov#else 15643a63c18SDmitri Tikhonov# define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r))) 15743a63c18SDmitri Tikhonov# define XXH_rotl64(x,r) ((x << r) | (x >> (64 - r))) 15843a63c18SDmitri Tikhonov#endif 15943a63c18SDmitri Tikhonov 16043a63c18SDmitri Tikhonov#if defined(_MSC_VER) // Visual Studio 16143a63c18SDmitri Tikhonov# define XXH_swap32 _byteswap_ulong 16243a63c18SDmitri Tikhonov# define XXH_swap64 _byteswap_uint64 16343a63c18SDmitri Tikhonov#elif GCC_VERSION >= 403 16443a63c18SDmitri Tikhonov# define XXH_swap32 __builtin_bswap32 16543a63c18SDmitri Tikhonov# define XXH_swap64 __builtin_bswap64 16643a63c18SDmitri Tikhonov#else 16743a63c18SDmitri Tikhonovstatic inline U32 XXH_swap32(U32 x) 16843a63c18SDmitri Tikhonov{ 16943a63c18SDmitri Tikhonov return ((x << 24) & 0xff000000) | 17043a63c18SDmitri Tikhonov ((x << 8) & 0x00ff0000) | 17143a63c18SDmitri Tikhonov ((x >> 8) & 0x0000ff00) | 17243a63c18SDmitri Tikhonov ((x >> 24) & 0x000000ff); 17343a63c18SDmitri Tikhonov} 17443a63c18SDmitri Tikhonovstatic inline U64 XXH_swap64(U64 x) 17543a63c18SDmitri Tikhonov{ 17643a63c18SDmitri Tikhonov return ((x << 56) & 0xff00000000000000ULL) | 17743a63c18SDmitri Tikhonov ((x << 40) & 0x00ff000000000000ULL) | 17843a63c18SDmitri Tikhonov ((x << 24) & 0x0000ff0000000000ULL) | 17943a63c18SDmitri Tikhonov ((x << 8) & 0x000000ff00000000ULL) | 18043a63c18SDmitri Tikhonov ((x >> 8) & 0x00000000ff000000ULL) | 18143a63c18SDmitri Tikhonov ((x >> 24) & 0x0000000000ff0000ULL) | 18243a63c18SDmitri Tikhonov ((x >> 40) & 0x000000000000ff00ULL) | 18343a63c18SDmitri Tikhonov ((x >> 56) & 0x00000000000000ffULL); 18443a63c18SDmitri Tikhonov} 18543a63c18SDmitri Tikhonov#endif 18643a63c18SDmitri Tikhonov 18743a63c18SDmitri Tikhonov 18843a63c18SDmitri Tikhonov//************************************** 18943a63c18SDmitri Tikhonov// Constants 19043a63c18SDmitri Tikhonov//************************************** 19143a63c18SDmitri Tikhonov#define PRIME32_1 2654435761U 19243a63c18SDmitri Tikhonov#define PRIME32_2 2246822519U 19343a63c18SDmitri Tikhonov#define PRIME32_3 3266489917U 19443a63c18SDmitri Tikhonov#define PRIME32_4 668265263U 19543a63c18SDmitri Tikhonov#define PRIME32_5 374761393U 19643a63c18SDmitri Tikhonov 19743a63c18SDmitri Tikhonov#define PRIME64_1 11400714785074694791ULL 19843a63c18SDmitri Tikhonov#define PRIME64_2 14029467366897019727ULL 19943a63c18SDmitri Tikhonov#define PRIME64_3 1609587929392839161ULL 20043a63c18SDmitri Tikhonov#define PRIME64_4 9650029242287828579ULL 20143a63c18SDmitri Tikhonov#define PRIME64_5 2870177450012600261ULL 20243a63c18SDmitri Tikhonov 20343a63c18SDmitri Tikhonov//************************************** 20443a63c18SDmitri Tikhonov// Architecture Macros 20543a63c18SDmitri Tikhonov//************************************** 20643a63c18SDmitri Tikhonovtypedef enum { XXH_bigEndian = 0, XXH_littleEndian = 1 } XXH_endianess; 20743a63c18SDmitri Tikhonov#ifndef XXH_CPU_LITTLE_ENDIAN // It is possible to define XXH_CPU_LITTLE_ENDIAN externally, for example using a compiler switch 20843a63c18SDmitri Tikhonovstatic const int one = 1; 20943a63c18SDmitri Tikhonov# define XXH_CPU_LITTLE_ENDIAN (*(char*)(&one)) 21043a63c18SDmitri Tikhonov#endif 21143a63c18SDmitri Tikhonov 21243a63c18SDmitri Tikhonov 21343a63c18SDmitri Tikhonov//************************************** 21443a63c18SDmitri Tikhonov// Macros 21543a63c18SDmitri Tikhonov//************************************** 21643a63c18SDmitri Tikhonov#define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(!!(c)) }; } // use only *after* variable declarations 21743a63c18SDmitri Tikhonov 21843a63c18SDmitri Tikhonov 21943a63c18SDmitri Tikhonov//**************************** 22043a63c18SDmitri Tikhonov// Memory reads 22143a63c18SDmitri Tikhonov//**************************** 22243a63c18SDmitri Tikhonovtypedef enum { XXH_aligned, XXH_unaligned } XXH_alignment; 22343a63c18SDmitri Tikhonov 22443a63c18SDmitri TikhonovFORCE_INLINE U32 XXH_readLE32_align(const void *ptr, XXH_endianess endian, 22543a63c18SDmitri Tikhonov XXH_alignment align) 22643a63c18SDmitri Tikhonov{ 22743a63c18SDmitri Tikhonov if (align == XXH_unaligned) 22843a63c18SDmitri Tikhonov return endian == XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr)); 22943a63c18SDmitri Tikhonov else 23043a63c18SDmitri Tikhonov return endian == XXH_littleEndian ? *(U32 *)ptr : XXH_swap32(*(U32 *)ptr); 23143a63c18SDmitri Tikhonov} 23243a63c18SDmitri Tikhonov 23343a63c18SDmitri TikhonovFORCE_INLINE U32 XXH_readLE32(const void *ptr, XXH_endianess endian) 23443a63c18SDmitri Tikhonov{ 23543a63c18SDmitri Tikhonov return XXH_readLE32_align(ptr, endian, XXH_unaligned); 23643a63c18SDmitri Tikhonov} 23743a63c18SDmitri Tikhonov 23843a63c18SDmitri TikhonovFORCE_INLINE U64 XXH_readLE64_align(const void *ptr, XXH_endianess endian, 23943a63c18SDmitri Tikhonov XXH_alignment align) 24043a63c18SDmitri Tikhonov{ 24143a63c18SDmitri Tikhonov if (align == XXH_unaligned) 24243a63c18SDmitri Tikhonov return endian == XXH_littleEndian ? A64(ptr) : XXH_swap64(A64(ptr)); 24343a63c18SDmitri Tikhonov else 24443a63c18SDmitri Tikhonov return endian == XXH_littleEndian ? *(U64 *)ptr : XXH_swap64(*(U64 *)ptr); 24543a63c18SDmitri Tikhonov} 24643a63c18SDmitri Tikhonov 24743a63c18SDmitri TikhonovFORCE_INLINE U64 XXH_readLE64(const void *ptr, XXH_endianess endian) 24843a63c18SDmitri Tikhonov{ 24943a63c18SDmitri Tikhonov return XXH_readLE64_align(ptr, endian, XXH_unaligned); 25043a63c18SDmitri Tikhonov} 25143a63c18SDmitri Tikhonov 25243a63c18SDmitri Tikhonov 25343a63c18SDmitri Tikhonov//**************************** 25443a63c18SDmitri Tikhonov// Simple Hash Functions 25543a63c18SDmitri Tikhonov//**************************** 25643a63c18SDmitri TikhonovFORCE_INLINE U32 XXH32_endian_align(const void *input, size_t len, 25743a63c18SDmitri Tikhonov U32 seed, XXH_endianess endian, XXH_alignment align) 25843a63c18SDmitri Tikhonov{ 25943a63c18SDmitri Tikhonov const BYTE *p = (const BYTE *)input; 26043a63c18SDmitri Tikhonov const BYTE *bEnd = p + len; 26143a63c18SDmitri Tikhonov U32 h32; 26243a63c18SDmitri Tikhonov#define XXH_get32bits(p) XXH_readLE32_align(p, endian, align) 26343a63c18SDmitri Tikhonov 26443a63c18SDmitri Tikhonov#ifdef XXH_ACCEPT_NULL_INPUT_POINTER 26543a63c18SDmitri Tikhonov if (p == NULL) 26643a63c18SDmitri Tikhonov { 26743a63c18SDmitri Tikhonov len = 0; 26843a63c18SDmitri Tikhonov bEnd = p = (const BYTE *)(size_t)16; 26943a63c18SDmitri Tikhonov } 27043a63c18SDmitri Tikhonov#endif 27143a63c18SDmitri Tikhonov 27243a63c18SDmitri Tikhonov if (len >= 16) 27343a63c18SDmitri Tikhonov { 27443a63c18SDmitri Tikhonov const BYTE *const limit = bEnd - 16; 27543a63c18SDmitri Tikhonov U32 v1 = seed + PRIME32_1 + PRIME32_2; 27643a63c18SDmitri Tikhonov U32 v2 = seed + PRIME32_2; 27743a63c18SDmitri Tikhonov U32 v3 = seed + 0; 27843a63c18SDmitri Tikhonov U32 v4 = seed - PRIME32_1; 27943a63c18SDmitri Tikhonov 28043a63c18SDmitri Tikhonov do 28143a63c18SDmitri Tikhonov { 28243a63c18SDmitri Tikhonov v1 += XXH_get32bits(p) * PRIME32_2; 28343a63c18SDmitri Tikhonov v1 = XXH_rotl32(v1, 13); 28443a63c18SDmitri Tikhonov v1 *= PRIME32_1; 28543a63c18SDmitri Tikhonov p += 4; 28643a63c18SDmitri Tikhonov v2 += XXH_get32bits(p) * PRIME32_2; 28743a63c18SDmitri Tikhonov v2 = XXH_rotl32(v2, 13); 28843a63c18SDmitri Tikhonov v2 *= PRIME32_1; 28943a63c18SDmitri Tikhonov p += 4; 29043a63c18SDmitri Tikhonov v3 += XXH_get32bits(p) * PRIME32_2; 29143a63c18SDmitri Tikhonov v3 = XXH_rotl32(v3, 13); 29243a63c18SDmitri Tikhonov v3 *= PRIME32_1; 29343a63c18SDmitri Tikhonov p += 4; 29443a63c18SDmitri Tikhonov v4 += XXH_get32bits(p) * PRIME32_2; 29543a63c18SDmitri Tikhonov v4 = XXH_rotl32(v4, 13); 29643a63c18SDmitri Tikhonov v4 *= PRIME32_1; 29743a63c18SDmitri Tikhonov p += 4; 29843a63c18SDmitri Tikhonov } 29943a63c18SDmitri Tikhonov while (p <= limit); 30043a63c18SDmitri Tikhonov 30143a63c18SDmitri Tikhonov h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 30243a63c18SDmitri Tikhonov 12) + XXH_rotl32(v4, 18); 30343a63c18SDmitri Tikhonov } 30443a63c18SDmitri Tikhonov else 30543a63c18SDmitri Tikhonov h32 = seed + PRIME32_5; 30643a63c18SDmitri Tikhonov 30743a63c18SDmitri Tikhonov h32 += (U32) len; 30843a63c18SDmitri Tikhonov 30943a63c18SDmitri Tikhonov while (p + 4 <= bEnd) 31043a63c18SDmitri Tikhonov { 31143a63c18SDmitri Tikhonov h32 += XXH_get32bits(p) * PRIME32_3; 31243a63c18SDmitri Tikhonov h32 = XXH_rotl32(h32, 17) * PRIME32_4 ; 31343a63c18SDmitri Tikhonov p += 4; 31443a63c18SDmitri Tikhonov } 31543a63c18SDmitri Tikhonov 31643a63c18SDmitri Tikhonov while (p < bEnd) 31743a63c18SDmitri Tikhonov { 31843a63c18SDmitri Tikhonov h32 += (*p) * PRIME32_5; 31943a63c18SDmitri Tikhonov h32 = XXH_rotl32(h32, 11) * PRIME32_1 ; 32043a63c18SDmitri Tikhonov p++; 32143a63c18SDmitri Tikhonov } 32243a63c18SDmitri Tikhonov 32343a63c18SDmitri Tikhonov h32 ^= h32 >> 15; 32443a63c18SDmitri Tikhonov h32 *= PRIME32_2; 32543a63c18SDmitri Tikhonov h32 ^= h32 >> 13; 32643a63c18SDmitri Tikhonov h32 *= PRIME32_3; 32743a63c18SDmitri Tikhonov h32 ^= h32 >> 16; 32843a63c18SDmitri Tikhonov 32943a63c18SDmitri Tikhonov return h32; 33043a63c18SDmitri Tikhonov} 33143a63c18SDmitri Tikhonov 33243a63c18SDmitri Tikhonov 33343a63c18SDmitri Tikhonovunsigned int XXH32(const void *input, size_t len, unsigned seed) 33443a63c18SDmitri Tikhonov{ 33543a63c18SDmitri Tikhonov#if 0 33643a63c18SDmitri Tikhonov // Simple version, good for code maintenance, but unfortunately slow for small inputs 33743a63c18SDmitri Tikhonov XXH32_state_t state; 33843a63c18SDmitri Tikhonov XXH32_reset(&state, seed); 33943a63c18SDmitri Tikhonov XXH32_update(&state, input, len); 34043a63c18SDmitri Tikhonov return XXH32_digest(&state); 34143a63c18SDmitri Tikhonov#else 34243a63c18SDmitri Tikhonov XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 34343a63c18SDmitri Tikhonov 34443a63c18SDmitri Tikhonov# if !defined(XXH_USE_UNALIGNED_ACCESS) 34543a63c18SDmitri Tikhonov if ((((size_t)input) & 3) == 34643a63c18SDmitri Tikhonov 0) // Input is aligned, let's leverage the speed advantage 34743a63c18SDmitri Tikhonov { 34843a63c18SDmitri Tikhonov if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 34943a63c18SDmitri Tikhonov return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); 35043a63c18SDmitri Tikhonov else 35143a63c18SDmitri Tikhonov return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); 35243a63c18SDmitri Tikhonov } 35343a63c18SDmitri Tikhonov# endif 35443a63c18SDmitri Tikhonov 35543a63c18SDmitri Tikhonov if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 35643a63c18SDmitri Tikhonov return XXH32_endian_align(input, len, seed, XXH_littleEndian, 35743a63c18SDmitri Tikhonov XXH_unaligned); 35843a63c18SDmitri Tikhonov else 35943a63c18SDmitri Tikhonov return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); 36043a63c18SDmitri Tikhonov#endif 36143a63c18SDmitri Tikhonov} 36243a63c18SDmitri Tikhonov 36343a63c18SDmitri TikhonovFORCE_INLINE U64 XXH64_endian_align(const void *input, size_t len, 36443a63c18SDmitri Tikhonov U64 seed, XXH_endianess endian, XXH_alignment align) 36543a63c18SDmitri Tikhonov{ 36643a63c18SDmitri Tikhonov const BYTE *p = (const BYTE *)input; 36743a63c18SDmitri Tikhonov const BYTE *bEnd = p + len; 36843a63c18SDmitri Tikhonov U64 h64; 36943a63c18SDmitri Tikhonov#define XXH_get64bits(p) XXH_readLE64_align(p, endian, align) 37043a63c18SDmitri Tikhonov 37143a63c18SDmitri Tikhonov#ifdef XXH_ACCEPT_NULL_INPUT_POINTER 37243a63c18SDmitri Tikhonov if (p == NULL) 37343a63c18SDmitri Tikhonov { 37443a63c18SDmitri Tikhonov len = 0; 37543a63c18SDmitri Tikhonov bEnd = p = (const BYTE *)(size_t)32; 37643a63c18SDmitri Tikhonov } 37743a63c18SDmitri Tikhonov#endif 37843a63c18SDmitri Tikhonov 37943a63c18SDmitri Tikhonov if (len >= 32) 38043a63c18SDmitri Tikhonov { 38143a63c18SDmitri Tikhonov const BYTE *const limit = bEnd - 32; 38243a63c18SDmitri Tikhonov U64 v1 = seed + PRIME64_1 + PRIME64_2; 38343a63c18SDmitri Tikhonov U64 v2 = seed + PRIME64_2; 38443a63c18SDmitri Tikhonov U64 v3 = seed + 0; 38543a63c18SDmitri Tikhonov U64 v4 = seed - PRIME64_1; 38643a63c18SDmitri Tikhonov 38743a63c18SDmitri Tikhonov do 38843a63c18SDmitri Tikhonov { 38943a63c18SDmitri Tikhonov v1 += XXH_get64bits(p) * PRIME64_2; 39043a63c18SDmitri Tikhonov p += 8; 39143a63c18SDmitri Tikhonov v1 = XXH_rotl64(v1, 31); 39243a63c18SDmitri Tikhonov v1 *= PRIME64_1; 39343a63c18SDmitri Tikhonov v2 += XXH_get64bits(p) * PRIME64_2; 39443a63c18SDmitri Tikhonov p += 8; 39543a63c18SDmitri Tikhonov v2 = XXH_rotl64(v2, 31); 39643a63c18SDmitri Tikhonov v2 *= PRIME64_1; 39743a63c18SDmitri Tikhonov v3 += XXH_get64bits(p) * PRIME64_2; 39843a63c18SDmitri Tikhonov p += 8; 39943a63c18SDmitri Tikhonov v3 = XXH_rotl64(v3, 31); 40043a63c18SDmitri Tikhonov v3 *= PRIME64_1; 40143a63c18SDmitri Tikhonov v4 += XXH_get64bits(p) * PRIME64_2; 40243a63c18SDmitri Tikhonov p += 8; 40343a63c18SDmitri Tikhonov v4 = XXH_rotl64(v4, 31); 40443a63c18SDmitri Tikhonov v4 *= PRIME64_1; 40543a63c18SDmitri Tikhonov } 40643a63c18SDmitri Tikhonov while (p <= limit); 40743a63c18SDmitri Tikhonov 40843a63c18SDmitri Tikhonov h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 40943a63c18SDmitri Tikhonov 12) + XXH_rotl64(v4, 18); 41043a63c18SDmitri Tikhonov 41143a63c18SDmitri Tikhonov v1 *= PRIME64_2; 41243a63c18SDmitri Tikhonov v1 = XXH_rotl64(v1, 31); 41343a63c18SDmitri Tikhonov v1 *= PRIME64_1; 41443a63c18SDmitri Tikhonov h64 ^= v1; 41543a63c18SDmitri Tikhonov h64 = h64 * PRIME64_1 + PRIME64_4; 41643a63c18SDmitri Tikhonov 41743a63c18SDmitri Tikhonov v2 *= PRIME64_2; 41843a63c18SDmitri Tikhonov v2 = XXH_rotl64(v2, 31); 41943a63c18SDmitri Tikhonov v2 *= PRIME64_1; 42043a63c18SDmitri Tikhonov h64 ^= v2; 42143a63c18SDmitri Tikhonov h64 = h64 * PRIME64_1 + PRIME64_4; 42243a63c18SDmitri Tikhonov 42343a63c18SDmitri Tikhonov v3 *= PRIME64_2; 42443a63c18SDmitri Tikhonov v3 = XXH_rotl64(v3, 31); 42543a63c18SDmitri Tikhonov v3 *= PRIME64_1; 42643a63c18SDmitri Tikhonov h64 ^= v3; 42743a63c18SDmitri Tikhonov h64 = h64 * PRIME64_1 + PRIME64_4; 42843a63c18SDmitri Tikhonov 42943a63c18SDmitri Tikhonov v4 *= PRIME64_2; 43043a63c18SDmitri Tikhonov v4 = XXH_rotl64(v4, 31); 43143a63c18SDmitri Tikhonov v4 *= PRIME64_1; 43243a63c18SDmitri Tikhonov h64 ^= v4; 43343a63c18SDmitri Tikhonov h64 = h64 * PRIME64_1 + PRIME64_4; 43443a63c18SDmitri Tikhonov } 43543a63c18SDmitri Tikhonov else 43643a63c18SDmitri Tikhonov h64 = seed + PRIME64_5; 43743a63c18SDmitri Tikhonov 43843a63c18SDmitri Tikhonov h64 += (U64) len; 43943a63c18SDmitri Tikhonov 44043a63c18SDmitri Tikhonov while (p + 8 <= bEnd) 44143a63c18SDmitri Tikhonov { 44243a63c18SDmitri Tikhonov U64 k1 = XXH_get64bits(p); 44343a63c18SDmitri Tikhonov k1 *= PRIME64_2; 44443a63c18SDmitri Tikhonov k1 = XXH_rotl64(k1, 31); 44543a63c18SDmitri Tikhonov k1 *= PRIME64_1; 44643a63c18SDmitri Tikhonov h64 ^= k1; 44743a63c18SDmitri Tikhonov h64 = XXH_rotl64(h64, 27) * PRIME64_1 + PRIME64_4; 44843a63c18SDmitri Tikhonov p += 8; 44943a63c18SDmitri Tikhonov } 45043a63c18SDmitri Tikhonov 45143a63c18SDmitri Tikhonov if (p + 4 <= bEnd) 45243a63c18SDmitri Tikhonov { 45343a63c18SDmitri Tikhonov h64 ^= (U64)(XXH_get32bits(p)) * PRIME64_1; 45443a63c18SDmitri Tikhonov h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3; 45543a63c18SDmitri Tikhonov p += 4; 45643a63c18SDmitri Tikhonov } 45743a63c18SDmitri Tikhonov 45843a63c18SDmitri Tikhonov while (p < bEnd) 45943a63c18SDmitri Tikhonov { 46043a63c18SDmitri Tikhonov h64 ^= (*p) * PRIME64_5; 46143a63c18SDmitri Tikhonov h64 = XXH_rotl64(h64, 11) * PRIME64_1; 46243a63c18SDmitri Tikhonov p++; 46343a63c18SDmitri Tikhonov } 46443a63c18SDmitri Tikhonov 46543a63c18SDmitri Tikhonov h64 ^= h64 >> 33; 46643a63c18SDmitri Tikhonov h64 *= PRIME64_2; 46743a63c18SDmitri Tikhonov h64 ^= h64 >> 29; 46843a63c18SDmitri Tikhonov h64 *= PRIME64_3; 46943a63c18SDmitri Tikhonov h64 ^= h64 >> 32; 47043a63c18SDmitri Tikhonov 47143a63c18SDmitri Tikhonov return h64; 47243a63c18SDmitri Tikhonov} 47343a63c18SDmitri Tikhonov 47443a63c18SDmitri Tikhonov 47543a63c18SDmitri Tikhonovunsigned long long XXH64(const void *input, size_t len, 47643a63c18SDmitri Tikhonov unsigned long long seed) 47743a63c18SDmitri Tikhonov{ 47843a63c18SDmitri Tikhonov#if 0 47943a63c18SDmitri Tikhonov // Simple version, good for code maintenance, but unfortunately slow for small inputs 48043a63c18SDmitri Tikhonov XXH64_state_t state; 48143a63c18SDmitri Tikhonov XXH64_reset(&state, seed); 48243a63c18SDmitri Tikhonov XXH64_update(&state, input, len); 48343a63c18SDmitri Tikhonov return XXH64_digest(&state); 48443a63c18SDmitri Tikhonov#else 48543a63c18SDmitri Tikhonov XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 48643a63c18SDmitri Tikhonov 48743a63c18SDmitri Tikhonov# if !defined(XXH_USE_UNALIGNED_ACCESS) 48843a63c18SDmitri Tikhonov if ((((size_t)input) & 7) == 48943a63c18SDmitri Tikhonov 0) // Input is aligned, let's leverage the speed advantage 49043a63c18SDmitri Tikhonov { 49143a63c18SDmitri Tikhonov if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 49243a63c18SDmitri Tikhonov return XXH64_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); 49343a63c18SDmitri Tikhonov else 49443a63c18SDmitri Tikhonov return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); 49543a63c18SDmitri Tikhonov } 49643a63c18SDmitri Tikhonov# endif 49743a63c18SDmitri Tikhonov 49843a63c18SDmitri Tikhonov if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 49943a63c18SDmitri Tikhonov return XXH64_endian_align(input, len, seed, XXH_littleEndian, 50043a63c18SDmitri Tikhonov XXH_unaligned); 50143a63c18SDmitri Tikhonov else 50243a63c18SDmitri Tikhonov return XXH64_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); 50343a63c18SDmitri Tikhonov#endif 50443a63c18SDmitri Tikhonov} 50543a63c18SDmitri Tikhonov 50643a63c18SDmitri Tikhonov/**************************************************** 50743a63c18SDmitri Tikhonov * Advanced Hash Functions 50843a63c18SDmitri Tikhonov****************************************************/ 50943a63c18SDmitri Tikhonov 51043a63c18SDmitri Tikhonov/*** Allocation ***/ 51143a63c18SDmitri Tikhonovtypedef struct 51243a63c18SDmitri Tikhonov{ 51343a63c18SDmitri Tikhonov U64 total_len; 51443a63c18SDmitri Tikhonov U32 seed; 51543a63c18SDmitri Tikhonov U32 v1; 51643a63c18SDmitri Tikhonov U32 v2; 51743a63c18SDmitri Tikhonov U32 v3; 51843a63c18SDmitri Tikhonov U32 v4; 51943a63c18SDmitri Tikhonov U32 mem32[4]; /* defined as U32 for alignment */ 52043a63c18SDmitri Tikhonov U32 memsize; 52143a63c18SDmitri Tikhonov} XXH_istate32_t; 52243a63c18SDmitri Tikhonov 52343a63c18SDmitri Tikhonovtypedef struct 52443a63c18SDmitri Tikhonov{ 52543a63c18SDmitri Tikhonov U64 total_len; 52643a63c18SDmitri Tikhonov U64 seed; 52743a63c18SDmitri Tikhonov U64 v1; 52843a63c18SDmitri Tikhonov U64 v2; 52943a63c18SDmitri Tikhonov U64 v3; 53043a63c18SDmitri Tikhonov U64 v4; 53143a63c18SDmitri Tikhonov U64 mem64[4]; /* defined as U64 for alignment */ 53243a63c18SDmitri Tikhonov U32 memsize; 53343a63c18SDmitri Tikhonov} XXH_istate64_t; 53443a63c18SDmitri Tikhonov 53543a63c18SDmitri Tikhonov 53643a63c18SDmitri TikhonovXXH32_state_t *XXH32_createState(void) 53743a63c18SDmitri Tikhonov{ 53843a63c18SDmitri Tikhonov XXH_STATIC_ASSERT(sizeof(XXH32_state_t) >= sizeof( 53943a63c18SDmitri Tikhonov XXH_istate32_t)); // A compilation error here means XXH32_state_t is not large enough 54043a63c18SDmitri Tikhonov return (XXH32_state_t *)XXH_malloc(sizeof(XXH32_state_t)); 54143a63c18SDmitri Tikhonov} 54243a63c18SDmitri TikhonovXXH_errorcode XXH32_freeState(XXH32_state_t *statePtr) 54343a63c18SDmitri Tikhonov{ 54443a63c18SDmitri Tikhonov XXH_free(statePtr); 54543a63c18SDmitri Tikhonov return XXH_OK; 54643a63c18SDmitri Tikhonov}; 54743a63c18SDmitri Tikhonov 54843a63c18SDmitri TikhonovXXH64_state_t *XXH64_createState(void) 54943a63c18SDmitri Tikhonov{ 55043a63c18SDmitri Tikhonov XXH_STATIC_ASSERT(sizeof(XXH64_state_t) >= sizeof( 55143a63c18SDmitri Tikhonov XXH_istate64_t)); // A compilation error here means XXH64_state_t is not large enough 55243a63c18SDmitri Tikhonov return (XXH64_state_t *)XXH_malloc(sizeof(XXH64_state_t)); 55343a63c18SDmitri Tikhonov} 55443a63c18SDmitri TikhonovXXH_errorcode XXH64_freeState(XXH64_state_t *statePtr) 55543a63c18SDmitri Tikhonov{ 55643a63c18SDmitri Tikhonov XXH_free(statePtr); 55743a63c18SDmitri Tikhonov return XXH_OK; 55843a63c18SDmitri Tikhonov}; 55943a63c18SDmitri Tikhonov 56043a63c18SDmitri Tikhonov 56143a63c18SDmitri Tikhonov/*** Hash feed ***/ 56243a63c18SDmitri Tikhonov 56343a63c18SDmitri TikhonovXXH_errorcode XXH32_reset(XXH32_state_t *state_in, U32 seed) 56443a63c18SDmitri Tikhonov{ 56543a63c18SDmitri Tikhonov XXH_istate32_t *state = (XXH_istate32_t *) state_in; 56643a63c18SDmitri Tikhonov state->seed = seed; 56743a63c18SDmitri Tikhonov state->v1 = seed + PRIME32_1 + PRIME32_2; 56843a63c18SDmitri Tikhonov state->v2 = seed + PRIME32_2; 56943a63c18SDmitri Tikhonov state->v3 = seed + 0; 57043a63c18SDmitri Tikhonov state->v4 = seed - PRIME32_1; 57143a63c18SDmitri Tikhonov state->total_len = 0; 57243a63c18SDmitri Tikhonov state->memsize = 0; 57343a63c18SDmitri Tikhonov return XXH_OK; 57443a63c18SDmitri Tikhonov} 57543a63c18SDmitri Tikhonov 57643a63c18SDmitri TikhonovXXH_errorcode XXH64_reset(XXH64_state_t *state_in, unsigned long long seed) 57743a63c18SDmitri Tikhonov{ 57843a63c18SDmitri Tikhonov XXH_istate64_t *state = (XXH_istate64_t *) state_in; 57943a63c18SDmitri Tikhonov state->seed = seed; 58043a63c18SDmitri Tikhonov state->v1 = seed + PRIME64_1 + PRIME64_2; 58143a63c18SDmitri Tikhonov state->v2 = seed + PRIME64_2; 58243a63c18SDmitri Tikhonov state->v3 = seed + 0; 58343a63c18SDmitri Tikhonov state->v4 = seed - PRIME64_1; 58443a63c18SDmitri Tikhonov state->total_len = 0; 58543a63c18SDmitri Tikhonov state->memsize = 0; 58643a63c18SDmitri Tikhonov return XXH_OK; 58743a63c18SDmitri Tikhonov} 58843a63c18SDmitri Tikhonov 58943a63c18SDmitri Tikhonov 59043a63c18SDmitri TikhonovFORCE_INLINE XXH_errorcode XXH32_update_endian(XXH32_state_t *state_in, 59143a63c18SDmitri Tikhonov const void *input, size_t len, XXH_endianess endian) 59243a63c18SDmitri Tikhonov{ 59343a63c18SDmitri Tikhonov XXH_istate32_t *state = (XXH_istate32_t *) state_in; 59443a63c18SDmitri Tikhonov const BYTE *p = (const BYTE *)input; 59543a63c18SDmitri Tikhonov const BYTE *const bEnd = p + len; 59643a63c18SDmitri Tikhonov 59743a63c18SDmitri Tikhonov#ifdef XXH_ACCEPT_NULL_INPUT_POINTER 59843a63c18SDmitri Tikhonov if (input == NULL) return XXH_ERROR; 59943a63c18SDmitri Tikhonov#endif 60043a63c18SDmitri Tikhonov 60143a63c18SDmitri Tikhonov state->total_len += len; 60243a63c18SDmitri Tikhonov 60343a63c18SDmitri Tikhonov if (state->memsize + len < 16) // fill in tmp buffer 60443a63c18SDmitri Tikhonov { 60543a63c18SDmitri Tikhonov XXH_memcpy((BYTE *)(state->mem32) + state->memsize, input, len); 60643a63c18SDmitri Tikhonov state->memsize += (U32)len; 60743a63c18SDmitri Tikhonov return XXH_OK; 60843a63c18SDmitri Tikhonov } 60943a63c18SDmitri Tikhonov 61043a63c18SDmitri Tikhonov if (state->memsize) // some data left from previous update 61143a63c18SDmitri Tikhonov { 61243a63c18SDmitri Tikhonov XXH_memcpy((BYTE *)(state->mem32) + state->memsize, input, 61343a63c18SDmitri Tikhonov 16 - state->memsize); 61443a63c18SDmitri Tikhonov { 61543a63c18SDmitri Tikhonov const U32 *p32 = state->mem32; 61643a63c18SDmitri Tikhonov state->v1 += XXH_readLE32(p32, endian) * PRIME32_2; 61743a63c18SDmitri Tikhonov state->v1 = XXH_rotl32(state->v1, 13); 61843a63c18SDmitri Tikhonov state->v1 *= PRIME32_1; 61943a63c18SDmitri Tikhonov p32++; 62043a63c18SDmitri Tikhonov state->v2 += XXH_readLE32(p32, endian) * PRIME32_2; 62143a63c18SDmitri Tikhonov state->v2 = XXH_rotl32(state->v2, 13); 62243a63c18SDmitri Tikhonov state->v2 *= PRIME32_1; 62343a63c18SDmitri Tikhonov p32++; 62443a63c18SDmitri Tikhonov state->v3 += XXH_readLE32(p32, endian) * PRIME32_2; 62543a63c18SDmitri Tikhonov state->v3 = XXH_rotl32(state->v3, 13); 62643a63c18SDmitri Tikhonov state->v3 *= PRIME32_1; 62743a63c18SDmitri Tikhonov p32++; 62843a63c18SDmitri Tikhonov state->v4 += XXH_readLE32(p32, endian) * PRIME32_2; 62943a63c18SDmitri Tikhonov state->v4 = XXH_rotl32(state->v4, 13); 63043a63c18SDmitri Tikhonov state->v4 *= PRIME32_1; 63143a63c18SDmitri Tikhonov p32++; 63243a63c18SDmitri Tikhonov } 63343a63c18SDmitri Tikhonov p += 16 - state->memsize; 63443a63c18SDmitri Tikhonov state->memsize = 0; 63543a63c18SDmitri Tikhonov } 63643a63c18SDmitri Tikhonov 63743a63c18SDmitri Tikhonov if (p <= bEnd - 16) 63843a63c18SDmitri Tikhonov { 63943a63c18SDmitri Tikhonov const BYTE *const limit = bEnd - 16; 64043a63c18SDmitri Tikhonov U32 v1 = state->v1; 64143a63c18SDmitri Tikhonov U32 v2 = state->v2; 64243a63c18SDmitri Tikhonov U32 v3 = state->v3; 64343a63c18SDmitri Tikhonov U32 v4 = state->v4; 64443a63c18SDmitri Tikhonov 64543a63c18SDmitri Tikhonov do 64643a63c18SDmitri Tikhonov { 64743a63c18SDmitri Tikhonov v1 += XXH_readLE32(p, endian) * PRIME32_2; 64843a63c18SDmitri Tikhonov v1 = XXH_rotl32(v1, 13); 64943a63c18SDmitri Tikhonov v1 *= PRIME32_1; 65043a63c18SDmitri Tikhonov p += 4; 65143a63c18SDmitri Tikhonov v2 += XXH_readLE32(p, endian) * PRIME32_2; 65243a63c18SDmitri Tikhonov v2 = XXH_rotl32(v2, 13); 65343a63c18SDmitri Tikhonov v2 *= PRIME32_1; 65443a63c18SDmitri Tikhonov p += 4; 65543a63c18SDmitri Tikhonov v3 += XXH_readLE32(p, endian) * PRIME32_2; 65643a63c18SDmitri Tikhonov v3 = XXH_rotl32(v3, 13); 65743a63c18SDmitri Tikhonov v3 *= PRIME32_1; 65843a63c18SDmitri Tikhonov p += 4; 65943a63c18SDmitri Tikhonov v4 += XXH_readLE32(p, endian) * PRIME32_2; 66043a63c18SDmitri Tikhonov v4 = XXH_rotl32(v4, 13); 66143a63c18SDmitri Tikhonov v4 *= PRIME32_1; 66243a63c18SDmitri Tikhonov p += 4; 66343a63c18SDmitri Tikhonov } 66443a63c18SDmitri Tikhonov while (p <= limit); 66543a63c18SDmitri Tikhonov 66643a63c18SDmitri Tikhonov state->v1 = v1; 66743a63c18SDmitri Tikhonov state->v2 = v2; 66843a63c18SDmitri Tikhonov state->v3 = v3; 66943a63c18SDmitri Tikhonov state->v4 = v4; 67043a63c18SDmitri Tikhonov } 67143a63c18SDmitri Tikhonov 67243a63c18SDmitri Tikhonov if (p < bEnd) 67343a63c18SDmitri Tikhonov { 67443a63c18SDmitri Tikhonov XXH_memcpy(state->mem32, p, bEnd - p); 67543a63c18SDmitri Tikhonov state->memsize = (int)(bEnd - p); 67643a63c18SDmitri Tikhonov } 67743a63c18SDmitri Tikhonov 67843a63c18SDmitri Tikhonov return XXH_OK; 67943a63c18SDmitri Tikhonov} 68043a63c18SDmitri Tikhonov 68143a63c18SDmitri TikhonovXXH_errorcode XXH32_update(XXH32_state_t *state_in, const void *input, 68243a63c18SDmitri Tikhonov size_t len) 68343a63c18SDmitri Tikhonov{ 68443a63c18SDmitri Tikhonov XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 68543a63c18SDmitri Tikhonov 68643a63c18SDmitri Tikhonov if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 68743a63c18SDmitri Tikhonov return XXH32_update_endian(state_in, input, len, XXH_littleEndian); 68843a63c18SDmitri Tikhonov else 68943a63c18SDmitri Tikhonov return XXH32_update_endian(state_in, input, len, XXH_bigEndian); 69043a63c18SDmitri Tikhonov} 69143a63c18SDmitri Tikhonov 69243a63c18SDmitri Tikhonov 69343a63c18SDmitri Tikhonov 69443a63c18SDmitri TikhonovFORCE_INLINE U32 XXH32_digest_endian(const XXH32_state_t *state_in, 69543a63c18SDmitri Tikhonov XXH_endianess endian) 69643a63c18SDmitri Tikhonov{ 69743a63c18SDmitri Tikhonov XXH_istate32_t *state = (XXH_istate32_t *) state_in; 69843a63c18SDmitri Tikhonov const BYTE *p = (const BYTE *)state->mem32; 69943a63c18SDmitri Tikhonov BYTE *bEnd = (BYTE *)(state->mem32) + state->memsize; 70043a63c18SDmitri Tikhonov U32 h32; 70143a63c18SDmitri Tikhonov 70243a63c18SDmitri Tikhonov if (state->total_len >= 16) 70343a63c18SDmitri Tikhonov h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 70443a63c18SDmitri Tikhonov 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18); 70543a63c18SDmitri Tikhonov else 70643a63c18SDmitri Tikhonov h32 = state->seed + PRIME32_5; 70743a63c18SDmitri Tikhonov 70843a63c18SDmitri Tikhonov h32 += (U32) state->total_len; 70943a63c18SDmitri Tikhonov 71043a63c18SDmitri Tikhonov while (p + 4 <= bEnd) 71143a63c18SDmitri Tikhonov { 71243a63c18SDmitri Tikhonov h32 += XXH_readLE32(p, endian) * PRIME32_3; 71343a63c18SDmitri Tikhonov h32 = XXH_rotl32(h32, 17) * PRIME32_4; 71443a63c18SDmitri Tikhonov p += 4; 71543a63c18SDmitri Tikhonov } 71643a63c18SDmitri Tikhonov 71743a63c18SDmitri Tikhonov while (p < bEnd) 71843a63c18SDmitri Tikhonov { 71943a63c18SDmitri Tikhonov h32 += (*p) * PRIME32_5; 72043a63c18SDmitri Tikhonov h32 = XXH_rotl32(h32, 11) * PRIME32_1; 72143a63c18SDmitri Tikhonov p++; 72243a63c18SDmitri Tikhonov } 72343a63c18SDmitri Tikhonov 72443a63c18SDmitri Tikhonov h32 ^= h32 >> 15; 72543a63c18SDmitri Tikhonov h32 *= PRIME32_2; 72643a63c18SDmitri Tikhonov h32 ^= h32 >> 13; 72743a63c18SDmitri Tikhonov h32 *= PRIME32_3; 72843a63c18SDmitri Tikhonov h32 ^= h32 >> 16; 72943a63c18SDmitri Tikhonov 73043a63c18SDmitri Tikhonov return h32; 73143a63c18SDmitri Tikhonov} 73243a63c18SDmitri Tikhonov 73343a63c18SDmitri Tikhonov 73443a63c18SDmitri TikhonovU32 XXH32_digest(const XXH32_state_t *state_in) 73543a63c18SDmitri Tikhonov{ 73643a63c18SDmitri Tikhonov XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 73743a63c18SDmitri Tikhonov 73843a63c18SDmitri Tikhonov if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 73943a63c18SDmitri Tikhonov return XXH32_digest_endian(state_in, XXH_littleEndian); 74043a63c18SDmitri Tikhonov else 74143a63c18SDmitri Tikhonov return XXH32_digest_endian(state_in, XXH_bigEndian); 74243a63c18SDmitri Tikhonov} 74343a63c18SDmitri Tikhonov 74443a63c18SDmitri Tikhonov 74543a63c18SDmitri TikhonovFORCE_INLINE XXH_errorcode XXH64_update_endian(XXH64_state_t *state_in, 74643a63c18SDmitri Tikhonov const void *input, size_t len, XXH_endianess endian) 74743a63c18SDmitri Tikhonov{ 74843a63c18SDmitri Tikhonov XXH_istate64_t *state = (XXH_istate64_t *) state_in; 74943a63c18SDmitri Tikhonov const BYTE *p = (const BYTE *)input; 75043a63c18SDmitri Tikhonov const BYTE *const bEnd = p + len; 75143a63c18SDmitri Tikhonov 75243a63c18SDmitri Tikhonov#ifdef XXH_ACCEPT_NULL_INPUT_POINTER 75343a63c18SDmitri Tikhonov if (input == NULL) return XXH_ERROR; 75443a63c18SDmitri Tikhonov#endif 75543a63c18SDmitri Tikhonov 75643a63c18SDmitri Tikhonov state->total_len += len; 75743a63c18SDmitri Tikhonov 75843a63c18SDmitri Tikhonov if (state->memsize + len < 32) // fill in tmp buffer 75943a63c18SDmitri Tikhonov { 76043a63c18SDmitri Tikhonov XXH_memcpy(((BYTE *)state->mem64) + state->memsize, input, len); 76143a63c18SDmitri Tikhonov state->memsize += (U32)len; 76243a63c18SDmitri Tikhonov return XXH_OK; 76343a63c18SDmitri Tikhonov } 76443a63c18SDmitri Tikhonov 76543a63c18SDmitri Tikhonov if (state->memsize) // some data left from previous update 76643a63c18SDmitri Tikhonov { 76743a63c18SDmitri Tikhonov XXH_memcpy(((BYTE *)state->mem64) + state->memsize, input, 76843a63c18SDmitri Tikhonov 32 - state->memsize); 76943a63c18SDmitri Tikhonov { 77043a63c18SDmitri Tikhonov const U64 *p64 = state->mem64; 77143a63c18SDmitri Tikhonov state->v1 += XXH_readLE64(p64, endian) * PRIME64_2; 77243a63c18SDmitri Tikhonov state->v1 = XXH_rotl64(state->v1, 31); 77343a63c18SDmitri Tikhonov state->v1 *= PRIME64_1; 77443a63c18SDmitri Tikhonov p64++; 77543a63c18SDmitri Tikhonov state->v2 += XXH_readLE64(p64, endian) * PRIME64_2; 77643a63c18SDmitri Tikhonov state->v2 = XXH_rotl64(state->v2, 31); 77743a63c18SDmitri Tikhonov state->v2 *= PRIME64_1; 77843a63c18SDmitri Tikhonov p64++; 77943a63c18SDmitri Tikhonov state->v3 += XXH_readLE64(p64, endian) * PRIME64_2; 78043a63c18SDmitri Tikhonov state->v3 = XXH_rotl64(state->v3, 31); 78143a63c18SDmitri Tikhonov state->v3 *= PRIME64_1; 78243a63c18SDmitri Tikhonov p64++; 78343a63c18SDmitri Tikhonov state->v4 += XXH_readLE64(p64, endian) * PRIME64_2; 78443a63c18SDmitri Tikhonov state->v4 = XXH_rotl64(state->v4, 31); 78543a63c18SDmitri Tikhonov state->v4 *= PRIME64_1; 78643a63c18SDmitri Tikhonov p64++; 78743a63c18SDmitri Tikhonov } 78843a63c18SDmitri Tikhonov p += 32 - state->memsize; 78943a63c18SDmitri Tikhonov state->memsize = 0; 79043a63c18SDmitri Tikhonov } 79143a63c18SDmitri Tikhonov 79243a63c18SDmitri Tikhonov if (p + 32 <= bEnd) 79343a63c18SDmitri Tikhonov { 79443a63c18SDmitri Tikhonov const BYTE *const limit = bEnd - 32; 79543a63c18SDmitri Tikhonov U64 v1 = state->v1; 79643a63c18SDmitri Tikhonov U64 v2 = state->v2; 79743a63c18SDmitri Tikhonov U64 v3 = state->v3; 79843a63c18SDmitri Tikhonov U64 v4 = state->v4; 79943a63c18SDmitri Tikhonov 80043a63c18SDmitri Tikhonov do 80143a63c18SDmitri Tikhonov { 80243a63c18SDmitri Tikhonov v1 += XXH_readLE64(p, endian) * PRIME64_2; 80343a63c18SDmitri Tikhonov v1 = XXH_rotl64(v1, 31); 80443a63c18SDmitri Tikhonov v1 *= PRIME64_1; 80543a63c18SDmitri Tikhonov p += 8; 80643a63c18SDmitri Tikhonov v2 += XXH_readLE64(p, endian) * PRIME64_2; 80743a63c18SDmitri Tikhonov v2 = XXH_rotl64(v2, 31); 80843a63c18SDmitri Tikhonov v2 *= PRIME64_1; 80943a63c18SDmitri Tikhonov p += 8; 81043a63c18SDmitri Tikhonov v3 += XXH_readLE64(p, endian) * PRIME64_2; 81143a63c18SDmitri Tikhonov v3 = XXH_rotl64(v3, 31); 81243a63c18SDmitri Tikhonov v3 *= PRIME64_1; 81343a63c18SDmitri Tikhonov p += 8; 81443a63c18SDmitri Tikhonov v4 += XXH_readLE64(p, endian) * PRIME64_2; 81543a63c18SDmitri Tikhonov v4 = XXH_rotl64(v4, 31); 81643a63c18SDmitri Tikhonov v4 *= PRIME64_1; 81743a63c18SDmitri Tikhonov p += 8; 81843a63c18SDmitri Tikhonov } 81943a63c18SDmitri Tikhonov while (p <= limit); 82043a63c18SDmitri Tikhonov 82143a63c18SDmitri Tikhonov state->v1 = v1; 82243a63c18SDmitri Tikhonov state->v2 = v2; 82343a63c18SDmitri Tikhonov state->v3 = v3; 82443a63c18SDmitri Tikhonov state->v4 = v4; 82543a63c18SDmitri Tikhonov } 82643a63c18SDmitri Tikhonov 82743a63c18SDmitri Tikhonov if (p < bEnd) 82843a63c18SDmitri Tikhonov { 82943a63c18SDmitri Tikhonov XXH_memcpy(state->mem64, p, bEnd - p); 83043a63c18SDmitri Tikhonov state->memsize = (int)(bEnd - p); 83143a63c18SDmitri Tikhonov } 83243a63c18SDmitri Tikhonov 83343a63c18SDmitri Tikhonov return XXH_OK; 83443a63c18SDmitri Tikhonov} 83543a63c18SDmitri Tikhonov 83643a63c18SDmitri TikhonovXXH_errorcode XXH64_update(XXH64_state_t *state_in, const void *input, 83743a63c18SDmitri Tikhonov size_t len) 83843a63c18SDmitri Tikhonov{ 83943a63c18SDmitri Tikhonov XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 84043a63c18SDmitri Tikhonov 84143a63c18SDmitri Tikhonov if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 84243a63c18SDmitri Tikhonov return XXH64_update_endian(state_in, input, len, XXH_littleEndian); 84343a63c18SDmitri Tikhonov else 84443a63c18SDmitri Tikhonov return XXH64_update_endian(state_in, input, len, XXH_bigEndian); 84543a63c18SDmitri Tikhonov} 84643a63c18SDmitri Tikhonov 84743a63c18SDmitri Tikhonov 84843a63c18SDmitri Tikhonov 84943a63c18SDmitri TikhonovFORCE_INLINE U64 XXH64_digest_endian(const XXH64_state_t *state_in, 85043a63c18SDmitri Tikhonov XXH_endianess endian) 85143a63c18SDmitri Tikhonov{ 85243a63c18SDmitri Tikhonov XXH_istate64_t *state = (XXH_istate64_t *) state_in; 85343a63c18SDmitri Tikhonov const BYTE *p = (const BYTE *)state->mem64; 85443a63c18SDmitri Tikhonov BYTE *bEnd = (BYTE *)state->mem64 + state->memsize; 85543a63c18SDmitri Tikhonov U64 h64; 85643a63c18SDmitri Tikhonov 85743a63c18SDmitri Tikhonov if (state->total_len >= 32) 85843a63c18SDmitri Tikhonov { 85943a63c18SDmitri Tikhonov U64 v1 = state->v1; 86043a63c18SDmitri Tikhonov U64 v2 = state->v2; 86143a63c18SDmitri Tikhonov U64 v3 = state->v3; 86243a63c18SDmitri Tikhonov U64 v4 = state->v4; 86343a63c18SDmitri Tikhonov 86443a63c18SDmitri Tikhonov h64 = XXH_rotl64(v1, 1) + XXH_rotl64(v2, 7) + XXH_rotl64(v3, 86543a63c18SDmitri Tikhonov 12) + XXH_rotl64(v4, 18); 86643a63c18SDmitri Tikhonov 86743a63c18SDmitri Tikhonov v1 *= PRIME64_2; 86843a63c18SDmitri Tikhonov v1 = XXH_rotl64(v1, 31); 86943a63c18SDmitri Tikhonov v1 *= PRIME64_1; 87043a63c18SDmitri Tikhonov h64 ^= v1; 87143a63c18SDmitri Tikhonov h64 = h64 * PRIME64_1 + PRIME64_4; 87243a63c18SDmitri Tikhonov 87343a63c18SDmitri Tikhonov v2 *= PRIME64_2; 87443a63c18SDmitri Tikhonov v2 = XXH_rotl64(v2, 31); 87543a63c18SDmitri Tikhonov v2 *= PRIME64_1; 87643a63c18SDmitri Tikhonov h64 ^= v2; 87743a63c18SDmitri Tikhonov h64 = h64 * PRIME64_1 + PRIME64_4; 87843a63c18SDmitri Tikhonov 87943a63c18SDmitri Tikhonov v3 *= PRIME64_2; 88043a63c18SDmitri Tikhonov v3 = XXH_rotl64(v3, 31); 88143a63c18SDmitri Tikhonov v3 *= PRIME64_1; 88243a63c18SDmitri Tikhonov h64 ^= v3; 88343a63c18SDmitri Tikhonov h64 = h64 * PRIME64_1 + PRIME64_4; 88443a63c18SDmitri Tikhonov 88543a63c18SDmitri Tikhonov v4 *= PRIME64_2; 88643a63c18SDmitri Tikhonov v4 = XXH_rotl64(v4, 31); 88743a63c18SDmitri Tikhonov v4 *= PRIME64_1; 88843a63c18SDmitri Tikhonov h64 ^= v4; 88943a63c18SDmitri Tikhonov h64 = h64 * PRIME64_1 + PRIME64_4; 89043a63c18SDmitri Tikhonov } 89143a63c18SDmitri Tikhonov else 89243a63c18SDmitri Tikhonov h64 = state->seed + PRIME64_5; 89343a63c18SDmitri Tikhonov 89443a63c18SDmitri Tikhonov h64 += (U64) state->total_len; 89543a63c18SDmitri Tikhonov 89643a63c18SDmitri Tikhonov while (p + 8 <= bEnd) 89743a63c18SDmitri Tikhonov { 89843a63c18SDmitri Tikhonov U64 k1 = XXH_readLE64(p, endian); 89943a63c18SDmitri Tikhonov k1 *= PRIME64_2; 90043a63c18SDmitri Tikhonov k1 = XXH_rotl64(k1, 31); 90143a63c18SDmitri Tikhonov k1 *= PRIME64_1; 90243a63c18SDmitri Tikhonov h64 ^= k1; 90343a63c18SDmitri Tikhonov h64 = XXH_rotl64(h64, 27) * PRIME64_1 + PRIME64_4; 90443a63c18SDmitri Tikhonov p += 8; 90543a63c18SDmitri Tikhonov } 90643a63c18SDmitri Tikhonov 90743a63c18SDmitri Tikhonov if (p + 4 <= bEnd) 90843a63c18SDmitri Tikhonov { 90943a63c18SDmitri Tikhonov h64 ^= (U64)(XXH_readLE32(p, endian)) * PRIME64_1; 91043a63c18SDmitri Tikhonov h64 = XXH_rotl64(h64, 23) * PRIME64_2 + PRIME64_3; 91143a63c18SDmitri Tikhonov p += 4; 91243a63c18SDmitri Tikhonov } 91343a63c18SDmitri Tikhonov 91443a63c18SDmitri Tikhonov while (p < bEnd) 91543a63c18SDmitri Tikhonov { 91643a63c18SDmitri Tikhonov h64 ^= (*p) * PRIME64_5; 91743a63c18SDmitri Tikhonov h64 = XXH_rotl64(h64, 11) * PRIME64_1; 91843a63c18SDmitri Tikhonov p++; 91943a63c18SDmitri Tikhonov } 92043a63c18SDmitri Tikhonov 92143a63c18SDmitri Tikhonov h64 ^= h64 >> 33; 92243a63c18SDmitri Tikhonov h64 *= PRIME64_2; 92343a63c18SDmitri Tikhonov h64 ^= h64 >> 29; 92443a63c18SDmitri Tikhonov h64 *= PRIME64_3; 92543a63c18SDmitri Tikhonov h64 ^= h64 >> 32; 92643a63c18SDmitri Tikhonov 92743a63c18SDmitri Tikhonov return h64; 92843a63c18SDmitri Tikhonov} 92943a63c18SDmitri Tikhonov 93043a63c18SDmitri Tikhonov 93143a63c18SDmitri Tikhonovunsigned long long XXH64_digest(const XXH64_state_t *state_in) 93243a63c18SDmitri Tikhonov{ 93343a63c18SDmitri Tikhonov XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 93443a63c18SDmitri Tikhonov 93543a63c18SDmitri Tikhonov if ((endian_detected == XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 93643a63c18SDmitri Tikhonov return XXH64_digest_endian(state_in, XXH_littleEndian); 93743a63c18SDmitri Tikhonov else 93843a63c18SDmitri Tikhonov return XXH64_digest_endian(state_in, XXH_bigEndian); 93943a63c18SDmitri Tikhonov} 94043a63c18SDmitri Tikhonov 94143a63c18SDmitri Tikhonov 942