contrib/libarchive/libarchive/xxhash.c

   1 /*
   2 xxHash - Fast Hash algorithm
   3 Copyright (C) 2012-2014, Yann Collet.
   4 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
   5
   6 Redistribution and use in source and binary forms, with or without
   7 modification, are permitted provided that the following conditions are
   8 met:
   9
  10 * Redistributions of source code must retain the above copyright
  11 notice, this list of conditions and the following disclaimer.
  12 * Redistributions in binary form must reproduce the above
  13 copyright notice, this list of conditions and the following disclaimer
  14 in the documentation and/or other materials provided with the
  15 distribution.
  16
  17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  18 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  19 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  20 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  21 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  22 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  27 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28
  29 You can contact the author at :
  30 - xxHash source repository : http://code.google.com/p/xxhash/
  31 */
  32 #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
  95 static unsigned int       XXH32 (const void*, unsigned int, unsigned int);
  96 static void*              XXH32_init   (unsigned int);
  97 static XXH_errorcode      XXH32_update (void*, const void*, unsigned int);
  98 static unsigned int       XXH32_digest (void*);
  99 /*static int              XXH32_sizeofState(void);*/
 100 static XXH_errorcode      XXH32_resetState(void*, unsigned int);
 101 #define       XXH32_SIZEOFSTATE 48
 102 typedef struct { long long ll[(XXH32_SIZEOFSTATE+(sizeof(long long)-1))/sizeof(long long)]; } XXH32_stateSpace_t;
 103 static 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
 137 typedef 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
 163 static 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 ****************************************/
 184 typedef 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 ******************************/
 200 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
 201
 202 static
 203 FORCE_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
 211 static
 212 FORCE_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 ******************************/
 218 static
 219 FORCE_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
 279 U32 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
 310 struct 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
 323 static
 324 int 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
 331 static
 332 XXH_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
 345 static
 346 void* 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
 353 static
 354 FORCE_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
 418 static
 419 XXH_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
 431 static
 432 FORCE_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
 473 static
 474 U32 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
 484 static
 485 U32 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
 494 const
 495 struct 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  */
 506 const
 507 struct archive_xxhash __archive_xxhash = {
 508         NULL,
 509         NULL,
 510         NULL,
 511         NULL
 512 };
 513
 514 #endif /* HAVE_LIBLZ4 */