diff options
Diffstat (limited to 'xxhash.c')
| -rw-r--r-- | xxhash.c | 475 |
1 files changed, 257 insertions, 218 deletions
@@ -1,33 +1,33 @@ /*
- xxHash - Fast Hash algorithm
- Copyright (C) 2012-2013, Yann Collet.
- BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
-
- Redistribution and use in source and binary forms, with or without
- modification, are permitted provided that the following conditions are
- met:
-
- * Redistributions of source code must retain the above copyright
- notice, this list of conditions and the following disclaimer.
- * Redistributions in binary form must reproduce the above
- copyright notice, this list of conditions and the following disclaimer
- in the documentation and/or other materials provided with the
- distribution.
-
- THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
- "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
- LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
- A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
- OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
- SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
- LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
- DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
- THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
- (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
- OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
-
- You can contact the author at :
- - xxHash source repository : http://code.google.com/p/xxhash/
+xxHash - Fast Hash algorithm
+Copyright (C) 2012-2013, Yann Collet.
+BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+* Redistributions of source code must retain the above copyright
+notice, this list of conditions and the following disclaimer.
+* Redistributions in binary form must reproduce the above
+copyright notice, this list of conditions and the following disclaimer
+in the documentation and/or other materials provided with the
+distribution.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+You can contact the author at :
+- xxHash source repository : http://code.google.com/p/xxhash/
*/
@@ -35,14 +35,21 @@ //**************************************
// Tuning parameters
//**************************************
-// FORCE_NATIVE_FORMAT :
-// By default, xxHash library provides endian-independant Hash values.
-// Results are therefore identical for big-endian and little-endian CPU.
+// XXH_ACCEPT_NULL_INPUT_POINTER :
+// If the input pointer is a null pointer, xxHash default behavior is to crash, since it is a bad input.
+// If this option is enabled, xxHash output for null input pointers will be the same as a null-length input.
+// This option has a very small performance cost (only measurable on small inputs).
+// By default, this option is disabled. To enable it, uncomment below define :
+//#define XXH_ACCEPT_NULL_INPUT_POINTER 1
+
+// XXH_FORCE_NATIVE_FORMAT :
+// By default, xxHash library provides endian-independant Hash values, based on little-endian convention.
+// Results are therefore identical for little-endian and big-endian CPU.
// This comes at a performance cost for big-endian CPU, since some swapping is required to emulate little-endian format.
// Should endian-independance be of no importance to your application, you may uncomment the #define below
// It will improve speed for Big-endian CPU.
// This option has no impact on Little_Endian CPU.
-//#define FORCE_NATIVE_FORMAT 1
+//#define XXH_FORCE_NATIVE_FORMAT 1
@@ -60,7 +67,7 @@ //**************************************
// Little Endian or Big Endian ?
// You can overwrite the #define below if you know your architecture endianess
-#if defined(FORCE_NATIVE_FORMAT) && (FORCE_NATIVE_FORMAT==1)
+#if defined(XXH_FORCE_NATIVE_FORMAT) && (XXH_FORCE_NATIVE_FORMAT==1)
// Force native format. The result will be endian dependant.
# define XXH_BIG_ENDIAN 0
#elif defined (__GLIBC__)
@@ -71,9 +78,9 @@ #elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN))
# define XXH_BIG_ENDIAN 1
#elif defined(__sparc) || defined(__sparc__) \
- || defined(__ppc__) || defined(_POWER) || defined(__powerpc__) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) \
- || defined(__hpux) || defined(__hppa) \
- || defined(_MIPSEB) || defined(__s390__)
+ || defined(__ppc__) || defined(_POWER) || defined(__powerpc__) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) \
+ || defined(__hpux) || defined(__hppa) \
+ || defined(_MIPSEB) || defined(__s390__)
# define XXH_BIG_ENDIAN 1
#endif
@@ -83,6 +90,24 @@ #endif
+//**************************************
+// Basic Types
+//**************************************
+#if defined (__STDC_VERSION__) && __STDC_VERSION__ >= 199901L // C99
+# include <stdint.h>
+ typedef uint8_t BYTE;
+ typedef uint16_t U16;
+ typedef uint32_t U32;
+ typedef int32_t S32;
+ typedef uint64_t U64;
+#else
+ typedef unsigned char BYTE;
+ typedef unsigned short U16;
+ typedef unsigned int U32;
+ typedef signed int S32;
+ typedef unsigned long long U64;
+#endif
+
//**************************************
// Compiler-specific Options & Functions
@@ -101,16 +126,14 @@ #elif GCC_VERSION >= 403
# define XXH_swap32 __builtin_bswap32
#else
-static inline unsigned int XXH_swap32 (unsigned int x) {
- return ((x << 24) & 0xff000000 ) |
- ((x << 8) & 0x00ff0000 ) |
- ((x >> 8) & 0x0000ff00 ) |
- ((x >> 24) & 0x000000ff );
- }
+static inline U32 XXH_swap32 (U32 x) {
+ return ((x << 24) & 0xff000000 ) |
+ ((x << 8) & 0x00ff0000 ) |
+ ((x >> 8) & 0x0000ff00 ) |
+ ((x >> 24) & 0x000000ff );}
#endif
-
//**************************************
// Constants
//**************************************
@@ -121,11 +144,10 @@ static inline unsigned int XXH_swap32 (unsigned int x) { #define PRIME32_5 374761393U
-
//**************************************
// Macros
//**************************************
-#define XXH_LE32(p) (XXH_BIG_ENDIAN ? XXH_swap32(*(unsigned int*)(p)) : *(unsigned int*)(p))
+#define XXH_LE32(p) (XXH_BIG_ENDIAN ? XXH_swap32(*(U32*)(p)) : *(U32*)(p))
@@ -133,65 +155,69 @@ static inline unsigned int XXH_swap32 (unsigned int x) { // Simple Hash Functions
//****************************
-unsigned int XXH32(const void* input, int len, unsigned int seed)
+U32 XXH32(const void* input, int len, U32 seed)
{
#if 0
- // Simple version, good for code maintenance, but unfortunately slow for small inputs
- void* state = XXH32_init(seed);
- XXH32_update(state, input, len);
- return XXH32_digest(state);
+ // Simple version, good for code maintenance, but unfortunately slow for small inputs
+ void* state = XXH32_init(seed);
+ XXH32_update(state, input, len);
+ return XXH32_digest(state);
#else
- const unsigned char* p = (const unsigned char*)input;
- const unsigned char* const bEnd = p + len;
- unsigned int h32;
-
- if (len>=16)
- {
- const unsigned char* const limit = bEnd - 16;
- unsigned int v1 = seed + PRIME32_1 + PRIME32_2;
- unsigned int v2 = seed + PRIME32_2;
- unsigned int v3 = seed + 0;
- unsigned int v4 = seed - PRIME32_1;
-
- do
- {
- v1 += XXH_LE32(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
- v2 += XXH_LE32(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
- v3 += XXH_LE32(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
- v4 += XXH_LE32(p) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
- } while (p<=limit) ;
-
- h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
- }
- else
- {
- h32 = seed + PRIME32_5;
- }
-
- h32 += (unsigned int) len;
-
- while (p<=bEnd-4)
- {
- h32 += XXH_LE32(p) * PRIME32_3;
- h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
- p+=4;
- }
-
- while (p<bEnd)
- {
- h32 += (*p) * PRIME32_5;
- h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
- p++;
- }
-
- h32 ^= h32 >> 15;
- h32 *= PRIME32_2;
- h32 ^= h32 >> 13;
- h32 *= PRIME32_3;
- h32 ^= h32 >> 16;
-
- return h32;
+ const BYTE* p = (const BYTE*)input;
+ const BYTE* const bEnd = p + len;
+ U32 h32;
+
+#ifdef XXH_ACCEPT_NULL_INPUT_POINTER
+ if (p==NULL) { len=0; p=(const BYTE*)16; }
+#endif
+
+ if (len>=16)
+ {
+ const BYTE* const limit = bEnd - 16;
+ U32 v1 = seed + PRIME32_1 + PRIME32_2;
+ U32 v2 = seed + PRIME32_2;
+ U32 v3 = seed + 0;
+ U32 v4 = seed - PRIME32_1;
+
+ do
+ {
+ v1 += XXH_LE32(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
+ v2 += XXH_LE32(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
+ v3 += XXH_LE32(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
+ v4 += XXH_LE32(p) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
+ } while (p<=limit);
+
+ h32 = XXH_rotl32(v1, 1) + XXH_rotl32(v2, 7) + XXH_rotl32(v3, 12) + XXH_rotl32(v4, 18);
+ }
+ else
+ {
+ h32 = seed + PRIME32_5;
+ }
+
+ h32 += (U32) len;
+
+ while (p<=bEnd-4)
+ {
+ h32 += XXH_LE32(p) * PRIME32_3;
+ h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
+ p+=4;
+ }
+
+ while (p<bEnd)
+ {
+ h32 += (*p) * PRIME32_5;
+ h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
+ p++;
+ }
+
+ h32 ^= h32 >> 15;
+ h32 *= PRIME32_2;
+ h32 ^= h32 >> 13;
+ h32 *= PRIME32_3;
+ h32 ^= h32 >> 16;
+
+ return h32;
#endif
}
@@ -203,142 +229,155 @@ unsigned int XXH32(const void* input, int len, unsigned int seed) struct XXH_state32_t
{
- unsigned int seed;
- unsigned int v1;
- unsigned int v2;
- unsigned int v3;
- unsigned int v4;
- unsigned long long total_len;
- char memory[16];
- int memsize;
+ U32 seed;
+ U32 v1;
+ U32 v2;
+ U32 v3;
+ U32 v4;
+ U64 total_len;
+ char memory[16];
+ int memsize;
};
-void* XXH32_init (unsigned int seed)
+int XXH32_sizeofState() { return sizeof(struct XXH_state32_t); }
+
+
+XXH_errorcode XXH32_resetState(void* state_in, unsigned int seed)
+{
+ struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
+ state->seed = seed;
+ state->v1 = seed + PRIME32_1 + PRIME32_2;
+ state->v2 = seed + PRIME32_2;
+ state->v3 = seed + 0;
+ state->v4 = seed - PRIME32_1;
+ state->total_len = 0;
+ state->memsize = 0;
+ return OK;
+}
+
+
+void* XXH32_init (U32 seed)
{
- struct XXH_state32_t * state = (struct XXH_state32_t *) malloc ( sizeof(struct XXH_state32_t));
- state->seed = seed;
- state->v1 = seed + PRIME32_1 + PRIME32_2;
- state->v2 = seed + PRIME32_2;
- state->v3 = seed + 0;
- state->v4 = seed - PRIME32_1;
- state->total_len = 0;
- state->memsize = 0;
-
- return (void*)state;
+ struct XXH_state32_t * state = (struct XXH_state32_t *) malloc (sizeof(struct XXH_state32_t));
+ XXH32_resetState(state, seed);
+ return (void*)state;
}
XXH_errorcode XXH32_update (void* state_in, const void* input, int len)
{
- struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
- const unsigned char* p = (const unsigned char*)input;
- const unsigned char* const bEnd = p + len;
+ struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
+ const BYTE* p = (const BYTE*)input;
+ const BYTE* const bEnd = p + len;
+
+#ifdef XXH_ACCEPT_NULL_INPUT_POINTER
+ if (input==NULL) return XXH_ERROR;
+#endif
- if (input==NULL) return XXH_ERROR;
-
state->total_len += len;
-
- if (state->memsize + len < 16) // fill in tmp buffer
- {
- memcpy(state->memory + state->memsize, input, len);
- state->memsize += len;
- return OK;
- }
-
- if (state->memsize) // some data left from previous update
- {
- memcpy(state->memory + state->memsize, input, 16-state->memsize);
- {
- const unsigned int* p32 = (const unsigned int*)state->memory;
- state->v1 += XXH_LE32(p32) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++;
- state->v2 += XXH_LE32(p32) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++;
- state->v3 += XXH_LE32(p32) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++;
- state->v4 += XXH_LE32(p32) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++;
- }
- p += 16-state->memsize;
- state->memsize = 0;
- }
-
- {
- const unsigned char* const limit = bEnd - 16;
- unsigned int v1 = state->v1;
- unsigned int v2 = state->v2;
- unsigned int v3 = state->v3;
- unsigned int v4 = state->v4;
-
- while (p<=limit)
- {
- v1 += XXH_LE32(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
- v2 += XXH_LE32(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
- v3 += XXH_LE32(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
- v4 += XXH_LE32(p) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
- }
-
- state->v1 = v1;
- state->v2 = v2;
- state->v3 = v3;
- state->v4 = v4;
- }
-
- if (p < bEnd)
- {
- memcpy(state->memory, p, bEnd-p);
- state->memsize = (int)(bEnd-p);
- }
-
- return OK;
+
+ if (state->memsize + len < 16) // fill in tmp buffer
+ {
+ memcpy(state->memory + state->memsize, input, len);
+ state->memsize += len;
+ return OK;
+ }
+
+ if (state->memsize) // some data left from previous update
+ {
+ memcpy(state->memory + state->memsize, input, 16-state->memsize);
+ {
+ const U32* p32 = (const U32*)state->memory;
+ state->v1 += XXH_LE32(p32) * PRIME32_2; state->v1 = XXH_rotl32(state->v1, 13); state->v1 *= PRIME32_1; p32++;
+ state->v2 += XXH_LE32(p32) * PRIME32_2; state->v2 = XXH_rotl32(state->v2, 13); state->v2 *= PRIME32_1; p32++;
+ state->v3 += XXH_LE32(p32) * PRIME32_2; state->v3 = XXH_rotl32(state->v3, 13); state->v3 *= PRIME32_1; p32++;
+ state->v4 += XXH_LE32(p32) * PRIME32_2; state->v4 = XXH_rotl32(state->v4, 13); state->v4 *= PRIME32_1; p32++;
+ }
+ p += 16-state->memsize;
+ state->memsize = 0;
+ }
+
+ if (p <= bEnd-16)
+ {
+ const BYTE* const limit = bEnd - 16;
+ U32 v1 = state->v1;
+ U32 v2 = state->v2;
+ U32 v3 = state->v3;
+ U32 v4 = state->v4;
+
+ do
+ {
+ v1 += XXH_LE32(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
+ v2 += XXH_LE32(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
+ v3 += XXH_LE32(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
+ v4 += XXH_LE32(p) * PRIME32_2; v4 = XXH_rotl32(v4, 13); v4 *= PRIME32_1; p+=4;
+ } while (p<=limit);
+
+ state->v1 = v1;
+ state->v2 = v2;
+ state->v3 = v3;
+ state->v4 = v4;
+ }
+
+ if (p < bEnd)
+ {
+ memcpy(state->memory, p, bEnd-p);
+ state->memsize = (int)(bEnd-p);
+ }
+
+ return OK;
}
-unsigned int XXH32_intermediateDigest (void* state_in)
+U32 XXH32_intermediateDigest (void* state_in)
{
- struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
- unsigned char * p = (unsigned char*)state->memory;
- unsigned char* bEnd = (unsigned char*)state->memory + state->memsize;
- unsigned int h32;
-
-
- if (state->total_len >= 16)
- {
- h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
- }
- else
- {
- h32 = state->seed + PRIME32_5;
- }
-
- h32 += (unsigned int) state->total_len;
-
- while (p<=bEnd-4)
- {
- h32 += XXH_LE32(p) * PRIME32_3;
- h32 = XXH_rotl32(h32, 17) * PRIME32_4 ;
- p+=4;
- }
-
- while (p<bEnd)
- {
- h32 += (*p) * PRIME32_5;
- h32 = XXH_rotl32(h32, 11) * PRIME32_1 ;
- p++;
- }
-
- h32 ^= h32 >> 15;
- h32 *= PRIME32_2;
- h32 ^= h32 >> 13;
- h32 *= PRIME32_3;
- h32 ^= h32 >> 16;
-
- return h32;
+ struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
+ BYTE * p = (BYTE*)state->memory;
+ BYTE* bEnd = (BYTE*)state->memory + state->memsize;
+ U32 h32;
+
+
+ if (state->total_len >= 16)
+ {
+ h32 = XXH_rotl32(state->v1, 1) + XXH_rotl32(state->v2, 7) + XXH_rotl32(state->v3, 12) + XXH_rotl32(state->v4, 18);
+ }
+ else
+ {
+ h32 = state->seed + PRIME32_5;
+ }
+
+ h32 += (U32) state->total_len;
+
+ while (p<=bEnd-4)
+ {
+ h32 += XXH_LE32(p) * PRIME32_3;
+ h32 = XXH_rotl32(h32, 17) * PRIME32_4;
+ p+=4;
+ }
+
+ while (p<bEnd)
+ {
+ h32 += (*p) * PRIME32_5;
+ h32 = XXH_rotl32(h32, 11) * PRIME32_1;
+ p++;
+ }
+
+ h32 ^= h32 >> 15;
+ h32 *= PRIME32_2;
+ h32 ^= h32 >> 13;
+ h32 *= PRIME32_3;
+ h32 ^= h32 >> 16;
+
+ return h32;
}
-unsigned int XXH32_digest (void* state_in)
+U32 XXH32_digest (void* state_in)
{
- unsigned int h32 = XXH32_intermediateDigest(state_in);
+ U32 h32 = XXH32_intermediateDigest(state_in);
- free(state_in);
+ free(state_in);
- return h32;
+ return h32;
}
|