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 } 422
