xxhash.c revision 313570
1/* 2xxHash - Fast Hash algorithm 3Copyright (C) 2012-2014, Yann Collet. 4BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php) 5 6Redistribution and use in source and binary forms, with or without 7modification, are permitted provided that the following conditions are 8met: 9 10* Redistributions of source code must retain the above copyright 11notice, this list of conditions and the following disclaimer. 12* Redistributions in binary form must reproduce the above 13copyright notice, this list of conditions and the following disclaimer 14in the documentation and/or other materials provided with the 15distribution. 16 17THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 18"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 19LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 20A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 21OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 22SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 24DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 25THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 29You can contact the author at : 30- xxHash source repository : http://code.google.com/p/xxhash/ 31*/ 32#include "archive_platform.h" 33 34#include <stdlib.h> 35#include <string.h> 36 37#include "archive_xxhash.h" 38 39#ifdef HAVE_LIBLZ4 40 41/*************************************** 42** Tuning parameters 43****************************************/ 44/* Unaligned memory access is automatically enabled for "common" CPU, such as x86. 45** For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected. 46** If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance. 47** You can also enable this parameter if you know your input data will always be aligned (boundaries of 4, for U32). 48*/ 49#if defined(__ARM_FEATURE_UNALIGNED) || defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64) 50# define XXH_USE_UNALIGNED_ACCESS 1 51#endif 52 53/* XXH_ACCEPT_NULL_INPUT_POINTER : 54** If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer. 55** When this option is enabled, xxHash output for null input pointers will be the same as a null-length input. 56** This option has a very small performance cost (only measurable on small inputs). 57** By default, this option is disabled. To enable it, uncomment below define : 58** #define XXH_ACCEPT_NULL_INPUT_POINTER 1 59 60** XXH_FORCE_NATIVE_FORMAT : 61** By default, xxHash library provides endian-independent Hash values, based on little-endian convention. 62** Results are therefore identical for little-endian and big-endian CPU. 63** This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format. 64** Should endian-independence be of no importance for your application, you may set the #define below to 1. 65** It will improve speed for Big-endian CPU. 66** This option has no impact on Little_Endian CPU. 67*/ 68#define XXH_FORCE_NATIVE_FORMAT 0 69 70/*************************************** 71** Compiler Specific Options 72****************************************/ 73/* Disable some Visual warning messages */ 74#ifdef _MSC_VER /* Visual Studio */ 75# pragma warning(disable : 4127) /* disable: C4127: conditional expression is constant */ 76#endif 77 78#ifdef _MSC_VER /* Visual Studio */ 79# define FORCE_INLINE __forceinline 80#else 81# ifdef __GNUC__ 82# define FORCE_INLINE inline __attribute__((always_inline)) 83# else 84# define FORCE_INLINE inline 85# endif 86#endif 87 88/*************************************** 89** Includes & Memory related functions 90****************************************/ 91#define XXH_malloc malloc 92#define XXH_free free 93#define XXH_memcpy memcpy 94 95 96static unsigned int XXH32 (const void*, unsigned int, unsigned int); 97static void* XXH32_init (unsigned int); 98static XXH_errorcode XXH32_update (void*, const void*, unsigned int); 99static unsigned int XXH32_digest (void*); 100/*static int XXH32_sizeofState(void);*/ 101static XXH_errorcode XXH32_resetState(void*, unsigned int); 102#define XXH32_SIZEOFSTATE 48 103typedef struct { long long ll[(XXH32_SIZEOFSTATE+(sizeof(long long)-1))/sizeof(long long)]; } XXH32_stateSpace_t; 104static unsigned int XXH32_intermediateDigest (void*); 105 106/*************************************** 107** Basic Types 108****************************************/ 109#if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L /* C99 */ 110# include <stdint.h> 111 typedef uint8_t BYTE; 112 typedef uint16_t U16; 113 typedef uint32_t U32; 114 typedef int32_t S32; 115 typedef uint64_t U64; 116#else 117 typedef unsigned char BYTE; 118 typedef unsigned short U16; 119 typedef unsigned int U32; 120 typedef signed int S32; 121 typedef unsigned long long U64; 122#endif 123 124#if defined(__GNUC__) && !defined(XXH_USE_UNALIGNED_ACCESS) 125# define _PACKED __attribute__ ((packed)) 126#else 127# define _PACKED 128#endif 129 130#if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__) 131# ifdef __IBMC__ 132# pragma pack(1) 133# else 134# pragma pack(push, 1) 135# endif 136#endif 137 138typedef struct _U32_S { U32 v; } _PACKED U32_S; 139 140#if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__) 141# pragma pack(pop) 142#endif 143 144#define A32(x) (((const U32_S *)(x))->v) 145 146 147/**************************************** 148** Compiler-specific Functions and Macros 149*****************************************/ 150#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__) 151 152/* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */ 153#if defined(_MSC_VER) 154# define XXH_rotl32(x,r) _rotl(x,r) 155#else 156# define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r))) 157#endif 158 159#if defined(_MSC_VER) /* Visual Studio */ 160# define XXH_swap32 _byteswap_ulong 161#elif GCC_VERSION >= 403 162# define XXH_swap32 __builtin_bswap32 163#else 164static inline U32 XXH_swap32 (U32 x) { 165 return ((x << 24) & 0xff000000 ) | 166 ((x << 8) & 0x00ff0000 ) | 167 ((x >> 8) & 0x0000ff00 ) | 168 ((x >> 24) & 0x000000ff );} 169#endif 170 171 172/*************************************** 173** Constants 174****************************************/ 175#define PRIME32_1 2654435761U 176#define PRIME32_2 2246822519U 177#define PRIME32_3 3266489917U 178#define PRIME32_4 668265263U 179#define PRIME32_5 374761393U 180 181 182/*************************************** 183** Architecture Macros 184****************************************/ 185typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess; 186#ifndef XXH_CPU_LITTLE_ENDIAN /* It is possible to define XXH_CPU_LITTLE_ENDIAN externally, for example using a compiler switch */ 187 static const int one = 1; 188# define XXH_CPU_LITTLE_ENDIAN (*(const char*)(&one)) 189#endif 190 191 192/*************************************** 193** Macros 194****************************************/ 195#define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(!!(c)) }; } /* use only *after* variable declarations */ 196 197 198/***************************** 199** Memory reads 200******************************/ 201typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment; 202 203static 204FORCE_INLINE U32 XXH_readLE32_align(const U32* ptr, XXH_endianess endian, XXH_alignment align) 205{ 206 if (align==XXH_unaligned) 207 return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr)); 208 else 209 return endian==XXH_littleEndian ? *ptr : XXH_swap32(*ptr); 210} 211 212static 213FORCE_INLINE U32 XXH_readLE32(const U32* ptr, XXH_endianess endian) { return XXH_readLE32_align(ptr, endian, XXH_unaligned); } 214 215 216/***************************** 217** Simple Hash Functions 218******************************/ 219static 220FORCE_INLINE U32 XXH32_endian_align(const void* input, unsigned int len, U32 seed, XXH_endianess endian, XXH_alignment align) 221{ 222 const BYTE* p = (const BYTE*)input; 223 const BYTE* bEnd = p + len; 224 U32 h32; 225#define XXH_get32bits(p) XXH_readLE32_align((const U32*)p, endian, align) 226 227#ifdef XXH_ACCEPT_NULL_INPUT_POINTER 228 if (p==NULL) { len=0; bEnd=p=(const BYTE*)(size_t)16; } 229#endif 230 231 if (len>=16) 232 { 233 const BYTE* const limit = bEnd - 16; 234 U32 v1 = seed + PRIME32_1 + PRIME32_2; 235 U32 v2 = seed + PRIME32_2; 236 U32 v3 = seed + 0; 237 U32 v4 = seed - PRIME32_1; 238 239 do 240 { 241 v1 += XXH_get32bits(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4; 242 v2 += XXH_get32bits(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4; 243 v3 += XXH_get32bits(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4; 244 v4 += XXH_get32bits(p) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4; 245 } while (p<=limit); 246 247 h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18); 248 } 249 else 250 { 251 h32 = seed + PRIME32_5; 252 } 253 254 h32 += (U32) len; 255 256 while (p<=bEnd-4) 257 { 258 h32 += XXH_get32bits(p) * PRIME32_3; 259 h32 = XXH_rotl32(h32, 17) * PRIME32_4 ; 260 p+=4; 261 } 262 263 while (p<bEnd) 264 { 265 h32 += (*p) * PRIME32_5; 266 h32 = XXH_rotl32(h32, 11) * PRIME32_1 ; 267 p++; 268 } 269 270 h32 ^= h32 >> 15; 271 h32 *= PRIME32_2; 272 h32 ^= h32 >> 13; 273 h32 *= PRIME32_3; 274 h32 ^= h32 >> 16; 275 276 return h32; 277} 278 279 280U32 XXH32(const void* input, unsigned int len, U32 seed) 281{ 282#if 0 283 // Simple version, good for code maintenance, but unfortunately slow for small inputs 284 void* state = XXH32_init(seed); 285 XXH32_update(state, input, len); 286 return XXH32_digest(state); 287#else 288 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 289 290# if !defined(XXH_USE_UNALIGNED_ACCESS) 291 if ((((size_t)input) & 3) == 0) /* Input is aligned, let's leverage the speed advantage */ 292 { 293 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 294 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned); 295 else 296 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned); 297 } 298# endif 299 300 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 301 return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned); 302 else 303 return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned); 304#endif 305} 306 307/***************************** 308** Advanced Hash Functions 309******************************/ 310 311struct XXH_state32_t 312{ 313 U64 total_len; 314 U32 seed; 315 U32 v1; 316 U32 v2; 317 U32 v3; 318 U32 v4; 319 int memsize; 320 char memory[16]; 321}; 322 323#if 0 324static 325int XXH32_sizeofState(void) 326{ 327 XXH_STATIC_ASSERT(XXH32_SIZEOFSTATE >= sizeof(struct XXH_state32_t)); /* A compilation error here means XXH32_SIZEOFSTATE is not large enough */ 328 return sizeof(struct XXH_state32_t); 329} 330#endif 331 332static 333XXH_errorcode XXH32_resetState(void* state_in, U32 seed) 334{ 335 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in; 336 state->seed = seed; 337 state->v1 = seed + PRIME32_1 + PRIME32_2; 338 state->v2 = seed + PRIME32_2; 339 state->v3 = seed + 0; 340 state->v4 = seed - PRIME32_1; 341 state->total_len = 0; 342 state->memsize = 0; 343 return XXH_OK; 344} 345 346static 347void* XXH32_init (U32 seed) 348{ 349 void* state = XXH_malloc (sizeof(struct XXH_state32_t)); 350 XXH32_resetState(state, seed); 351 return state; 352} 353 354static 355FORCE_INLINE XXH_errorcode XXH32_update_endian (void* state_in, const void* input, int len, XXH_endianess endian) 356{ 357 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in; 358 const BYTE* p = (const BYTE*)input; 359 const BYTE* const bEnd = p + len; 360 361#ifdef XXH_ACCEPT_NULL_INPUT_POINTER 362 if (input==NULL) return XXH_ERROR; 363#endif 364 365 state->total_len += len; 366 367 if (state->memsize + len < 16) /* fill in tmp buffer */ 368 { 369 XXH_memcpy(state->memory + state->memsize, input, len); 370 state->memsize += len; 371 return XXH_OK; 372 } 373 374 if (state->memsize) /* some data left from previous update */ 375 { 376 XXH_memcpy(state->memory + state->memsize, input, 16-state->memsize); 377 { 378 const U32* p32 = (const U32*)state->memory; 379 state->v1 += XXH_readLE32(p32, endian) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++; 380 state->v2 += XXH_readLE32(p32, endian) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++; 381 state->v3 += XXH_readLE32(p32, endian) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++; 382 state->v4 += XXH_readLE32(p32, endian) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++; 383 } 384 p += 16-state->memsize; 385 state->memsize = 0; 386 } 387 388 if (p <= bEnd-16) 389 { 390 const BYTE* const limit = bEnd - 16; 391 U32 v1 = state->v1; 392 U32 v2 = state->v2; 393 U32 v3 = state->v3; 394 U32 v4 = state->v4; 395 396 do 397 { 398 v1 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4; 399 v2 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4; 400 v3 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4; 401 v4 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4; 402 } while (p<=limit); 403 404 state->v1 = v1; 405 state->v2 = v2; 406 state->v3 = v3; 407 state->v4 = v4; 408 } 409 410 if (p < bEnd) 411 { 412 XXH_memcpy(state->memory, p, bEnd-p); 413 state->memsize = (int)(bEnd-p); 414 } 415 416 return XXH_OK; 417} 418 419static 420XXH_errorcode XXH32_update (void* state_in, const void* input, unsigned int len) 421{ 422 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 423 424 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 425 return XXH32_update_endian(state_in, input, len, XXH_littleEndian); 426 else 427 return XXH32_update_endian(state_in, input, len, XXH_bigEndian); 428} 429 430 431 432static 433FORCE_INLINE U32 XXH32_intermediateDigest_endian (void* state_in, XXH_endianess endian) 434{ 435 struct XXH_state32_t * state = (struct XXH_state32_t *) state_in; 436 const BYTE * p = (const BYTE*)state->memory; 437 BYTE* bEnd = (BYTE*)state->memory + state->memsize; 438 U32 h32; 439 440 if (state->total_len >= 16) 441 { 442 h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18); 443 } 444 else 445 { 446 h32 = state->seed + PRIME32_5; 447 } 448 449 h32 += (U32) state->total_len; 450 451 while (p<=bEnd-4) 452 { 453 h32 += XXH_readLE32((const U32*)p, endian) * PRIME32_3; 454 h32 = XXH_rotl32(h32, 17) * PRIME32_4; 455 p+=4; 456 } 457 458 while (p<bEnd) 459 { 460 h32 += (*p) * PRIME32_5; 461 h32 = XXH_rotl32(h32, 11) * PRIME32_1; 462 p++; 463 } 464 465 h32 ^= h32 >> 15; 466 h32 *= PRIME32_2; 467 h32 ^= h32 >> 13; 468 h32 *= PRIME32_3; 469 h32 ^= h32 >> 16; 470 471 return h32; 472} 473 474static 475U32 XXH32_intermediateDigest (void* state_in) 476{ 477 XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN; 478 479 if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT) 480 return XXH32_intermediateDigest_endian(state_in, XXH_littleEndian); 481 else 482 return XXH32_intermediateDigest_endian(state_in, XXH_bigEndian); 483} 484 485static 486U32 XXH32_digest (void* state_in) 487{ 488 U32 h32 = XXH32_intermediateDigest(state_in); 489 490 XXH_free(state_in); 491 492 return h32; 493} 494 495const 496struct archive_xxhash __archive_xxhash = { 497 XXH32, 498 XXH32_init, 499 XXH32_update, 500 XXH32_digest 501}; 502#else 503 504/* 505 * Define an empty version of the struct if we aren't using the LZ4 library. 506 */ 507const 508struct archive_xxhash __archive_xxhash = { 509 NULL, 510 NULL, 511 NULL, 512 NULL 513}; 514 515#endif /* HAVE_LIBLZ4 */ 516