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
 145 /****************************************
 146 ** Compiler-specific Functions and Macros
 147 *****************************************/
 148 #define GCC_VERSION ((__GNUC__-0) * 100 + (__GNUC_MINOR__ - 0))
 149
 150 #if GCC_VERSION >= 409
 151 __attribute__((__no_sanitize_undefined__))
 152 #endif
 153 static inline U32 A32(const void * x)
 154 {
 155     return (((const U32_S *)(x))->v);
 156 }
 157
 158 /* Note : although _rotl exists for minGW (GCC under windows), performance seems poor */
 159 #if defined(_MSC_VER)
 160 #  define XXH_rotl32(x,r) _rotl(x,r)
 161 #else
 162 #  define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
 163 #endif
 164
 165 #if defined(_MSC_VER)     /* Visual Studio */
 166 #  define XXH_swap32 _byteswap_ulong
 167 #elif GCC_VERSION >= 403
 168 #  define XXH_swap32 __builtin_bswap32
 169 #else
 170 static inline U32 XXH_swap32 (U32 x) {
 171     return  ((x << 24) & 0xff000000 ) |
 172                         ((x <<  8) & 0x00ff0000 ) |
 173                         ((x >>  8) & 0x0000ff00 ) |
 174                         ((x >> 24) & 0x000000ff );}
 175 #endif
 176
 177
 178 /***************************************
 179 ** Constants
 180 ****************************************/
 181 #define PRIME32_1   2654435761U
 182 #define PRIME32_2   2246822519U
 183 #define PRIME32_3   3266489917U
 184 #define PRIME32_4    668265263U
 185 #define PRIME32_5    374761393U
 186
 187
 188 /***************************************
 189 ** Architecture Macros
 190 ****************************************/
 191 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess;
 192 #ifndef XXH_CPU_LITTLE_ENDIAN   /* It is possible to define XXH_CPU_LITTLE_ENDIAN externally, for example using a compiler switch */
 193     static const int one = 1;
 194 #   define XXH_CPU_LITTLE_ENDIAN   (*(const char*)(&one))
 195 #endif
 196
 197
 198 /***************************************
 199 ** Macros
 200 ****************************************/
 201 #define XXH_STATIC_ASSERT(c)   { enum { XXH_static_assert = 1/(!!(c)) }; }    /* use only *after* variable declarations */
 202
 203
 204 /*****************************
 205 ** Memory reads
 206 ******************************/
 207 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;
 208
 209 static
 210 FORCE_INLINE U32 XXH_readLE32_align(const U32* ptr, XXH_endianess endian, XXH_alignment align)
 211 {
 212     if (align==XXH_unaligned)
 213         return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr));
 214     else
 215         return endian==XXH_littleEndian ? *ptr : XXH_swap32(*ptr);
 216 }
 217
 218 static
 219 FORCE_INLINE U32 XXH_readLE32(const U32* ptr, XXH_endianess endian) { return XXH_readLE32_align(ptr, endian, XXH_unaligned); }
 220
 221
 222 /*****************************
 223 ** Simple Hash Functions
 224 ******************************/
 225 static
 226 FORCE_INLINE U32 XXH32_endian_align(const void* input, unsigned int len, U32 seed, XXH_endianess endian, XXH_alignment align)
 227 {
 228     const BYTE* p = (const BYTE*)input;
 229     const BYTE* bEnd = p + len;
 230     U32 h32;
 231 #define XXH_get32bits(p) XXH_readLE32_align((const U32*)p, endian, align)
 232
 233 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
 234     if (p==NULL) { len=0; bEnd=p=(const BYTE*)(size_t)16; }
 235 #endif
 236
 237     if (len>=16)
 238     {
 239         const BYTE* const limit = bEnd - 16;
 240         U32 v1 = seed + PRIME32_1 + PRIME32_2;
 241         U32 v2 = seed + PRIME32_2;
 242         U32 v3 = seed + 0;
 243         U32 v4 = seed - PRIME32_1;
 244
 245         do
 246         {
 247             v1 += XXH_get32bits(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
 248             v2 += XXH_get32bits(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
 249             v3 += XXH_get32bits(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
 250             v4 += XXH_get32bits(p) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
 251         } while (p<=limit);
 252
 253         h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
 254     }
 255     else
 256     {
 257         h32  = seed + PRIME32_5;
 258     }
 259
 260     h32 += (U32) len;
 261
 262     while (p<=bEnd-4)
 263     {
 264         h32 += XXH_get32bits(p) * PRIME32_3;
 265         h32  = XXH_rotl32(h32, 17) * PRIME32_4 ;
 266         p+=4;
 267     }
 268
 269     while (p<bEnd)
 270     {
 271         h32 += (*p) * PRIME32_5;
 272         h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
 273         p++;
 274     }
 275
 276     h32 ^= h32 >> 15;
 277     h32 *= PRIME32_2;
 278     h32 ^= h32 >> 13;
 279     h32 *= PRIME32_3;
 280     h32 ^= h32 >> 16;
 281
 282     return h32;
 283 }
 284
 285
 286 U32 XXH32(const void* input, unsigned int len, U32 seed)
 287 {
 288 #if 0
 289     // Simple version, good for code maintenance, but unfortunately slow for small inputs
 290     void* state = XXH32_init(seed);
 291     XXH32_update(state, input, len);
 292     return XXH32_digest(state);
 293 #else
 294     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
 295
 296 #  if !defined(XXH_USE_UNALIGNED_ACCESS)
 297     if ((((size_t)input) & 3) == 0)   /* Input is aligned, let's leverage the speed advantage */
 298     {
 299         if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 300             return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);
 301         else
 302             return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);
 303     }
 304 #  endif
 305
 306     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 307         return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);
 308     else
 309         return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);
 310 #endif
 311 }
 312
 313 /*****************************
 314 ** Advanced Hash Functions
 315 ******************************/
 316
 317 struct XXH_state32_t
 318 {
 319     U64 total_len;
 320     U32 seed;
 321     U32 v1;
 322     U32 v2;
 323     U32 v3;
 324     U32 v4;
 325     int memsize;
 326     char memory[16];
 327 };
 328
 329 #if 0
 330 static
 331 int XXH32_sizeofState(void)
 332 {
 333     XXH_STATIC_ASSERT(XXH32_SIZEOFSTATE >= sizeof(struct XXH_state32_t));   /* A compilation error here means XXH32_SIZEOFSTATE is not large enough */
 334     return sizeof(struct XXH_state32_t);
 335 }
 336 #endif
 337
 338 static
 339 XXH_errorcode XXH32_resetState(void* state_in, U32 seed)
 340 {
 341     struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
 342     state->seed = seed;
 343     state->v1 = seed + PRIME32_1 + PRIME32_2;
 344     state->v2 = seed + PRIME32_2;
 345     state->v3 = seed + 0;
 346     state->v4 = seed - PRIME32_1;
 347     state->total_len = 0;
 348     state->memsize = 0;
 349     return XXH_OK;
 350 }
 351
 352 static
 353 void* XXH32_init (U32 seed)
 354 {
 355     void* state = XXH_malloc (sizeof(struct XXH_state32_t));
 356     XXH32_resetState(state, seed);
 357     return state;
 358 }
 359
 360 static
 361 FORCE_INLINE XXH_errorcode XXH32_update_endian (void* state_in, const void* input, int len, XXH_endianess endian)
 362 {
 363     struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
 364     const BYTE* p = (const BYTE*)input;
 365     const BYTE* const bEnd = p + len;
 366
 367 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER
 368     if (input==NULL) return XXH_ERROR;
 369 #endif
 370
 371     state->total_len += len;
 372
 373     if (state->memsize + len < 16)   /* fill in tmp buffer */
 374     {
 375         XXH_memcpy(state->memory + state->memsize, input, len);
 376         state->memsize +=  len;
 377         return XXH_OK;
 378     }
 379
 380     if (state->memsize)   /* some data left from previous update */
 381     {
 382         XXH_memcpy(state->memory + state->memsize, input, 16-state->memsize);
 383         {
 384             const U32* p32 = (const U32*)state->memory;
 385             state->v1 += XXH_readLE32(p32, endian) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++;
 386             state->v2 += XXH_readLE32(p32, endian) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++;
 387             state->v3 += XXH_readLE32(p32, endian) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++;
 388             state->v4 += XXH_readLE32(p32, endian) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++;
 389         }
 390         p += 16-state->memsize;
 391         state->memsize = 0;
 392     }
 393
 394     if (p <= bEnd-16)
 395     {
 396         const BYTE* const limit = bEnd - 16;
 397         U32 v1 = state->v1;
 398         U32 v2 = state->v2;
 399         U32 v3 = state->v3;
 400         U32 v4 = state->v4;
 401
 402         do
 403         {
 404             v1 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
 405             v2 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
 406             v3 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
 407             v4 += XXH_readLE32((const U32*)p, endian) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
 408         } while (p<=limit);
 409
 410         state->v1 = v1;
 411         state->v2 = v2;
 412         state->v3 = v3;
 413         state->v4 = v4;
 414     }
 415
 416     if (p < bEnd)
 417     {
 418         XXH_memcpy(state->memory, p, bEnd-p);
 419         state->memsize = (int)(bEnd-p);
 420     }
 421
 422     return XXH_OK;
 423 }
 424
 425 static
 426 XXH_errorcode XXH32_update (void* state_in, const void* input, unsigned int len)
 427 {
 428     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
 429
 430     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 431         return XXH32_update_endian(state_in, input, len, XXH_littleEndian);
 432     else
 433         return XXH32_update_endian(state_in, input, len, XXH_bigEndian);
 434 }
 435
 436
 437
 438 static
 439 FORCE_INLINE U32 XXH32_intermediateDigest_endian (void* state_in, XXH_endianess endian)
 440 {
 441     struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
 442     const BYTE * p = (const BYTE*)state->memory;
 443     BYTE* bEnd = (BYTE*)state->memory + state->memsize;
 444     U32 h32;
 445
 446     if (state->total_len >= 16)
 447     {
 448         h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
 449     }
 450     else
 451     {
 452         h32  = state->seed + PRIME32_5;
 453     }
 454
 455     h32 += (U32) state->total_len;
 456
 457     while (p<=bEnd-4)
 458     {
 459         h32 += XXH_readLE32((const U32*)p, endian) * PRIME32_3;
 460         h32  = XXH_rotl32(h32, 17) * PRIME32_4;
 461         p+=4;
 462     }
 463
 464     while (p<bEnd)
 465     {
 466         h32 += (*p) * PRIME32_5;
 467         h32 = XXH_rotl32(h32, 11) * PRIME32_1;
 468         p++;
 469     }
 470
 471     h32 ^= h32 >> 15;
 472     h32 *= PRIME32_2;
 473     h32 ^= h32 >> 13;
 474     h32 *= PRIME32_3;
 475     h32 ^= h32 >> 16;
 476
 477     return h32;
 478 }
 479
 480 static
 481 U32 XXH32_intermediateDigest (void* state_in)
 482 {
 483     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;
 484
 485     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)
 486         return XXH32_intermediateDigest_endian(state_in, XXH_littleEndian);
 487     else
 488         return XXH32_intermediateDigest_endian(state_in, XXH_bigEndian);
 489 }
 490
 491 static
 492 U32 XXH32_digest (void* state_in)
 493 {
 494     U32 h32 = XXH32_intermediateDigest(state_in);
 495
 496     XXH_free(state_in);
 497
 498     return h32;
 499 }
 500
 501 const
 502 struct archive_xxhash __archive_xxhash = {
 503         XXH32,
 504         XXH32_init,
 505         XXH32_update,
 506         XXH32_digest
 507 };
 508 #else
 509
 510 /*
 511  * Define an empty version of the struct if we aren't using the LZ4 library.
 512  */
 513 const
 514 struct archive_xxhash __archive_xxhash = {
 515         NULL,
 516         NULL,
 517         NULL,
 518         NULL
 519 };
 520
 521 #endif /* HAVE_LIBLZ4 */