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