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 "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
  96 static unsigned int       XXH32 (const void*, unsigned int, unsigned int);
  97 static void*              XXH32_init   (unsigned int);
  98 static XXH_errorcode      XXH32_update (void*, const void*, unsigned int);
  99 static unsigned int       XXH32_digest (void*);
 100 /*static int              XXH32_sizeofState(void);*/
 101 static XXH_errorcode      XXH32_resetState(void*, unsigned int);
 102 #define       XXH32_SIZEOFSTATE 48
 103 typedef struct { long long ll[(XXH32_SIZEOFSTATE+(sizeof(long long)-1))/sizeof(long long)]; } XXH32_stateSpace_t;
 104 static 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
 138 typedef 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
 164 static 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 ****************************************/
 185 typedef 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 ******************************/
 201 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
 202
 203 static
 204 FORCE_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
 212 static
 213 FORCE_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 ******************************/
 219 static
 220 FORCE_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
 280 U32 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
 311 struct 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
 324 static
 325 int 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
 332 static
 333 XXH_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
 346 static
 347 void* 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
 354 static
 355 FORCE_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
 419 static
 420 XXH_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
 432 static
 433 FORCE_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
 474 static
 475 U32 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
 485 static
 486 U32 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
 495 const
 496 struct 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  */
 507 const
 508 struct archive_xxhash __archive_xxhash = {
 509         NULL,
 510         NULL,
 511         NULL,
 512         NULL
 513 };
 514
 515 #endif /* HAVE_LIBLZ4 */