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