silo/third-party/lz4/xxhash.c

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