crc/xxhash.c

   1 /*\r
   2 xxHash - Fast Hash algorithm\r
   3 Copyright (C) 2012-2014, 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 // Tuning parameters\r
  36 //**************************************\r
  37 // Unaligned memory access is automatically enabled for "common" CPU, such as x86.\r
  38 // For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected.\r
  39 // If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance.\r
  40 // You can also enable this parameter if you know your input data will always be aligned (boundaries of 4, for uint32_t).\r
  41 #if defined(__ARM_FEATURE_UNALIGNED) || defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)\r
  42 #  define XXH_USE_UNALIGNED_ACCESS 1\r
  43 #endif\r
  44 \r
  45 // XXH_ACCEPT_NULL_INPUT_POINTER :\r
  46 // If the input pointer is a null pointer, xxHash default behavior is to trigger a memory access error, since it is a bad pointer.\r
  47 // When this option is enabled, xxHash output for null input pointers will be the same as a null-length input.\r
  48 // This option has a very small performance cost (only measurable on small inputs).\r
  49 // By default, this option is disabled. To enable it, uncomment below define :\r
  50 //#define XXH_ACCEPT_NULL_INPUT_POINTER 1\r
  51 \r
  52 // XXH_FORCE_NATIVE_FORMAT :\r
  53 // By default, xxHash library provides endian-independant Hash values, based on little-endian convention.\r
  54 // Results are therefore identical for little-endian and big-endian CPU.\r
  55 // This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format.\r
  56 // Should endian-independance be of no importance for your application, you may set the #define below to 1.\r
  57 // It will improve speed for Big-endian CPU.\r
  58 // This option has no impact on Little_Endian CPU.\r
  59 #define XXH_FORCE_NATIVE_FORMAT 0\r
  60 \r
  61 \r
  62 //**************************************\r
  63 // Includes & Memory related functions\r
  64 //**************************************\r
  65 #include "xxhash.h"\r
  66 // Modify the local functions below should you wish to use some other memory related routines\r
  67 // for malloc(), free()\r
  68 #include <stdlib.h>\r
  69 void* XXH_malloc(size_t s) { return malloc(s); }\r
  70 void  XXH_free  (void* p)  { free(p); }\r
  71 // for memcpy()\r
  72 #include <string.h>\r
  73 void* XXH_memcpy(void* dest, const void* src, size_t size) { return memcpy(dest,src,size); }\r
  74 \r
  75 \r
  76 #if defined(__GNUC__)  && !defined(XXH_USE_UNALIGNED_ACCESS)\r
  77 #  define _PACKED __attribute__ ((packed))\r
  78 #else\r
  79 #  define _PACKED\r
  80 #endif\r
  81 \r
  82 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)\r
  83 #  ifdef __IBMC__\r
  84 #    pragma pack(1)\r
  85 #  else\r
  86 #    pragma pack(push, 1)\r
  87 #  endif\r
  88 #endif\r
  89 \r
  90 typedef struct _uint32_t_S { uint32_t v; } _PACKED uint32_t_S;\r
  91 \r
  92 #if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)\r
  93 #  pragma pack(pop)\r
  94 #endif\r
  95 \r
  96 #define A32(x) (((uint32_t_S *)(x))->v)\r
  97 \r
  98 \r
  99 //***************************************\r
 100 // Compiler-specific Functions and Macros\r
 101 //***************************************\r
 102 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)\r
 103 \r
 104 // Note : although _rotl exists for minGW (GCC under windows), performance seems poor\r
 105 #if defined(_MSC_VER)\r
 106 #  define XXH_rotl32(x,r) _rotl(x,r)\r
 107 #else\r
 108 #  define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))\r
 109 #endif\r
 110 \r
 111 #if defined(_MSC_VER)     // Visual Studio\r
 112 #  define XXH_swap32 _byteswap_ulong\r
 113 #elif GCC_VERSION >= 403\r
 114 #  define XXH_swap32 __builtin_bswap32\r
 115 #else\r
 116 static inline uint32_t XXH_swap32 (uint32_t x) {\r
 117     return  ((x << 24) & 0xff000000 ) |\r
 118         ((x <<  8) & 0x00ff0000 ) |\r
 119         ((x >>  8) & 0x0000ff00 ) |\r
 120         ((x >> 24) & 0x000000ff );}\r
 121 #endif\r
 122 \r
 123 \r
 124 //**************************************\r
 125 // Constants\r
 126 //**************************************\r
 127 #define PRIME32_1   2654435761U\r
 128 #define PRIME32_2   2246822519U\r
 129 #define PRIME32_3   3266489917U\r
 130 #define PRIME32_4    668265263U\r
 131 #define PRIME32_5    374761393U\r
 132 \r
 133 \r
 134 //**************************************\r
 135 // Architecture Macros\r
 136 //**************************************\r
 137 typedef enum { XXH_bigEndian=0, XXH_littleEndian=1 } XXH_endianess;\r
 138 #ifndef XXH_CPU_LITTLE_ENDIAN   // It is possible to define XXH_CPU_LITTLE_ENDIAN externally, for example using a compiler switch\r
 139     static const int one = 1;\r
 140 #   define XXH_CPU_LITTLE_ENDIAN   (*(char*)(&one))\r
 141 #endif\r
 142 \r
 143 \r
 144 //**************************************\r
 145 // Macros\r
 146 //**************************************\r
 147 #define XXH_STATIC_ASSERT(c)   { enum { XXH_static_assert = 1/(!!(c)) }; }    // use only *after* variable declarations\r
 148 \r
 149 \r
 150 //****************************\r
 151 // Memory reads\r
 152 //****************************\r
 153 typedef enum { XXH_aligned, XXH_unaligned } XXH_alignment;\r
 154 \r
 155 uint32_t XXH_readLE32_align(const uint32_t* ptr, XXH_endianess endian, XXH_alignment align)\r
 156 { \r
 157     if (align==XXH_unaligned)\r
 158         return endian==XXH_littleEndian ? A32(ptr) : XXH_swap32(A32(ptr)); \r
 159     else\r
 160         return endian==XXH_littleEndian ? *ptr : XXH_swap32(*ptr); \r
 161 }\r
 162 \r
 163 uint32_t XXH_readLE32(const uint32_t* ptr, XXH_endianess endian) { return XXH_readLE32_align(ptr, endian, XXH_unaligned); }\r
 164 \r
 165 \r
 166 //****************************\r
 167 // Simple Hash Functions\r
 168 //****************************\r
 169 uint32_t XXH32_endian_align(const void* input, int len, uint32_t seed, XXH_endianess endian, XXH_alignment align)\r
 170 {\r
 171     const uint8_t *p = (const uint8_t *)input;\r
 172     const uint8_t * const bEnd = p + len;\r
 173     uint32_t h32;\r
 174 \r
 175 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER\r
 176     if (p==NULL) { len=0; p=(const uint8_t *)(size_t)16; }\r
 177 #endif\r
 178 \r
 179     if (len>=16)\r
 180     {\r
 181         const uint8_t * const limit = bEnd - 16;\r
 182         uint32_t v1 = seed + PRIME32_1 + PRIME32_2;\r
 183         uint32_t v2 = seed + PRIME32_2;\r
 184         uint32_t v3 = seed + 0;\r
 185         uint32_t v4 = seed - PRIME32_1;\r
 186 \r
 187         do\r
 188         {\r
 189             v1 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;\r
 190             v2 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;\r
 191             v3 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;\r
 192             v4 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;\r
 193         } while (p<=limit);\r
 194 \r
 195         h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);\r
 196     }\r
 197     else\r
 198     {\r
 199         h32  = seed + PRIME32_5;\r
 200     }\r
 201 \r
 202     h32 += (uint32_t) len;\r
 203 \r
 204     while (p<=bEnd-4)\r
 205     {\r
 206         h32 += XXH_readLE32_align((const uint32_t*)p, endian, align) * PRIME32_3;\r
 207         h32  = XXH_rotl32(h32, 17) * PRIME32_4 ;\r
 208         p+=4;\r
 209     }\r
 210 \r
 211     while (p<bEnd)\r
 212     {\r
 213         h32 += (*p) * PRIME32_5;\r
 214         h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;\r
 215         p++;\r
 216     }\r
 217 \r
 218     h32 ^= h32 >> 15;\r
 219     h32 *= PRIME32_2;\r
 220     h32 ^= h32 >> 13;\r
 221     h32 *= PRIME32_3;\r
 222     h32 ^= h32 >> 16;\r
 223 \r
 224     return h32;\r
 225 }\r
 226 \r
 227 \r
 228 uint32_t XXH32(const void* input, int len, uint32_t seed)\r
 229 {\r
 230 #if 0\r
 231     // Simple version, good for code maintenance, but unfortunately slow for small inputs\r
 232     void* state = XXH32_init(seed);\r
 233     XXH32_update(state, input, len);\r
 234     return XXH32_digest(state);\r
 235 #else\r
 236     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;\r
 237 \r
 238 #  if !defined(XXH_USE_UNALIGNED_ACCESS)\r
 239     if ((((size_t)input) & 3))   // Input is aligned, let's leverage the speed advantage\r
 240     {\r
 241         if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)\r
 242             return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_aligned);\r
 243         else\r
 244             return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_aligned);\r
 245     }\r
 246 #  endif\r
 247 \r
 248     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)\r
 249         return XXH32_endian_align(input, len, seed, XXH_littleEndian, XXH_unaligned);\r
 250     else\r
 251         return XXH32_endian_align(input, len, seed, XXH_bigEndian, XXH_unaligned);\r
 252 #endif\r
 253 }\r
 254 \r
 255 \r
 256 //****************************\r
 257 // Advanced Hash Functions\r
 258 //****************************\r
 259 \r
 260 int XXH32_sizeofState() \r
 261 {\r
 262     XXH_STATIC_ASSERT(XXH32_SIZEOFSTATE >= sizeof(struct XXH_state32_t));   // A compilation error here means XXH32_SIZEOFSTATE is not large enough\r
 263     return sizeof(struct XXH_state32_t); \r
 264 }\r
 265 \r
 266 \r
 267 XXH_errorcode XXH32_resetState(void* state_in, uint32_t seed)\r
 268 { \r
 269     struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;\r
 270     state->seed = seed;\r
 271     state->v1 = seed + PRIME32_1 + PRIME32_2;\r
 272     state->v2 = seed + PRIME32_2;\r
 273     state->v3 = seed + 0;\r
 274     state->v4 = seed - PRIME32_1;\r
 275     state->total_len = 0;\r
 276     state->memsize = 0;\r
 277     return XXH_OK;\r
 278 }\r
 279 \r
 280 \r
 281 void* XXH32_init (uint32_t seed)\r
 282 {\r
 283     void* state = XXH_malloc (sizeof(struct XXH_state32_t));\r
 284     XXH32_resetState(state, seed);\r
 285     return state;\r
 286 }\r
 287 \r
 288 \r
 289 XXH_errorcode XXH32_update_endian (void* state_in, const void* input, int len, XXH_endianess endian)\r
 290 {\r
 291     struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;\r
 292     const uint8_t *p = (const uint8_t *)input;\r
 293     const uint8_t * const bEnd = p + len;\r
 294 \r
 295 #ifdef XXH_ACCEPT_NULL_INPUT_POINTER\r
 296     if (input==NULL) return XXH_ERROR;\r
 297 #endif\r
 298 \r
 299     state->total_len += len;\r
 300 \r
 301     if (state->memsize + len < 16)   // fill in tmp buffer\r
 302     {\r
 303         XXH_memcpy(state->memory + state->memsize, input, len);\r
 304         state->memsize +=  len;\r
 305         return XXH_OK;\r
 306     }\r
 307 \r
 308     if (state->memsize)   // some data left from previous update\r
 309     {\r
 310         XXH_memcpy(state->memory + state->memsize, input, 16-state->memsize);\r
 311         {\r
 312             const uint32_t* p32 = (const uint32_t*)state->memory;\r
 313             state->v1 += XXH_readLE32(p32, endian) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++;\r
 314             state->v2 += XXH_readLE32(p32, endian) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++; \r
 315             state->v3 += XXH_readLE32(p32, endian) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++;\r
 316             state->v4 += XXH_readLE32(p32, endian) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++;\r
 317         }\r
 318         p += 16-state->memsize;\r
 319         state->memsize = 0;\r
 320     }\r
 321 \r
 322     if (p <= bEnd-16)\r
 323     {\r
 324         const uint8_t * const limit = bEnd - 16;\r
 325         uint32_t v1 = state->v1;\r
 326         uint32_t v2 = state->v2;\r
 327         uint32_t v3 = state->v3;\r
 328         uint32_t v4 = state->v4;\r
 329 \r
 330         do\r
 331         {\r
 332             v1 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;\r
 333             v2 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;\r
 334             v3 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;\r
 335             v4 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;\r
 336         } while (p<=limit);\r
 337 \r
 338         state->v1 = v1;\r
 339         state->v2 = v2;\r
 340         state->v3 = v3;\r
 341         state->v4 = v4;\r
 342     }\r
 343 \r
 344     if (p < bEnd)\r
 345     {\r
 346         XXH_memcpy(state->memory, p, bEnd-p);\r
 347         state->memsize = (int)(bEnd-p);\r
 348     }\r
 349 \r
 350     return XXH_OK;\r
 351 }\r
 352 \r
 353 XXH_errorcode XXH32_update (void* state_in, const void* input, int len)\r
 354 {\r
 355     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;\r
 356 \r
 357     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)\r
 358         return XXH32_update_endian(state_in, input, len, XXH_littleEndian);\r
 359     else\r
 360         return XXH32_update_endian(state_in, input, len, XXH_bigEndian);\r
 361 }\r
 362 \r
 363 \r
 364 \r
 365 uint32_t XXH32_intermediateDigest_endian (void* state_in, XXH_endianess endian)\r
 366 {\r
 367     struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;\r
 368     const uint8_t *p = (const uint8_t *)state->memory;\r
 369     uint8_t * bEnd = (uint8_t *)state->memory + state->memsize;\r
 370     uint32_t h32;\r
 371 \r
 372     if (state->total_len >= 16)\r
 373     {\r
 374         h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);\r
 375     }\r
 376     else\r
 377     {\r
 378         h32  = state->seed + PRIME32_5;\r
 379     }\r
 380 \r
 381     h32 += (uint32_t) state->total_len;\r
 382 \r
 383     while (p<=bEnd-4)\r
 384     {\r
 385         h32 += XXH_readLE32((const uint32_t*)p, endian) * PRIME32_3;\r
 386         h32  = XXH_rotl32(h32, 17) * PRIME32_4;\r
 387         p+=4;\r
 388     }\r
 389 \r
 390     while (p<bEnd)\r
 391     {\r
 392         h32 += (*p) * PRIME32_5;\r
 393         h32 = XXH_rotl32(h32, 11) * PRIME32_1;\r
 394         p++;\r
 395     }\r
 396 \r
 397     h32 ^= h32 >> 15;\r
 398     h32 *= PRIME32_2;\r
 399     h32 ^= h32 >> 13;\r
 400     h32 *= PRIME32_3;\r
 401     h32 ^= h32 >> 16;\r
 402 \r
 403     return h32;\r
 404 }\r
 405 \r
 406 \r
 407 uint32_t XXH32_intermediateDigest (void* state_in)\r
 408 {\r
 409     XXH_endianess endian_detected = (XXH_endianess)XXH_CPU_LITTLE_ENDIAN;\r
 410 \r
 411     if ((endian_detected==XXH_littleEndian) || XXH_FORCE_NATIVE_FORMAT)\r
 412         return XXH32_intermediateDigest_endian(state_in, XXH_littleEndian);\r
 413     else\r
 414         return XXH32_intermediateDigest_endian(state_in, XXH_bigEndian);\r
 415 }\r
 416 \r
 417 \r
 418 uint32_t XXH32_digest (void* state_in)\r
 419 {\r
 420     uint32_t h32 = XXH32_intermediateDigest(state_in);\r
 421 \r
 422     XXH_free(state_in);\r
 423 \r
 424     return h32;\r
 425 }\r