diff options
Diffstat (limited to 'xxhash.c')
-rw-r--r-- | xxhash.c | 160 |
1 files changed, 127 insertions, 33 deletions
@@ -35,6 +35,14 @@ You can contact the author at : //**************************************
// Tuning parameters
//**************************************
+// Unaligned memory access is automatically enabled for "common" CPU, such as x86.
+// For others CPU, the compiler will be more cautious, and insert extra code to ensure aligned access is respected.
+// If you know your target CPU supports unaligned memory access, you want to force this option manually to improve performance.
+// You can also enable this parameter if you know your input data will always be aligned (boundaries of 4, for U32).
+#if defined(__ARM_FEATURE_UNALIGNED) || defined(__i386) || defined(_M_IX86) || defined(__x86_64__) || defined(_M_X64)
+# define XXH_USE_UNALIGNED_ACCESS 1
+#endif
+
// 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.
@@ -45,21 +53,33 @@ You can contact the author at : // 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
+// 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 for 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 XXH_FORCE_NATIVE_FORMAT 1
+//**************************************
+// Compiler Options
+//**************************************
+#if defined(_MSC_VER) && !defined(__cplusplus) // Visual Studio
+# define inline __inline // Visual C is not C99, but supports some kind of inline
+#endif
+
//**************************************
-// Includes
+// Includes & Memory related functions
//**************************************
-#include <stdlib.h> // for malloc(), free()
-#include <string.h> // for memcpy()
#include "xxhash.h"
-
+// Modify the local functions below should you wish to use some other memory related routines
+// for malloc(), free()
+#include <stdlib.h>
+static inline void* XXH_malloc(size_t s) { return malloc(s); }
+static inline void XXH_free (void* p) { free(p); }
+// for memcpy()
+#include <string.h>
+static inline void* XXH_memcpy(void* dest, const void* src, size_t size) { return memcpy(dest,src,size); }
//**************************************
@@ -77,8 +97,8 @@ You can contact the author at : # endif
#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) \
+#elif defined(__sparc) || defined(__sparc__) \
+ || defined(__powerpc__) || defined(__ppc__) || defined(__PPC__) \
|| defined(__hpux) || defined(__hppa) \
|| defined(_MIPSEB) || defined(__s390__)
# define XXH_BIG_ENDIAN 1
@@ -101,21 +121,39 @@ You can contact the author at : 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;
+ typedef unsigned char BYTE;
+ typedef unsigned short U16;
+ typedef unsigned int U32;
+ typedef signed int S32;
+ typedef unsigned long long U64;
#endif
+#if defined(__GNUC__) && !defined(XXH_USE_UNALIGNED_ACCESS)
+# define _PACKED __attribute__ ((packed))
+#else
+# define _PACKED
+#endif
-//**************************************
-// Compiler-specific Options & Functions
-//**************************************
+#if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
+# pragma pack(push, 1)
+#endif
+
+typedef struct _U32_S { U32 v; } _PACKED U32_S;
+
+#if !defined(XXH_USE_UNALIGNED_ACCESS) && !defined(__GNUC__)
+# pragma pack(pop)
+#endif
+
+#define A32(x) (((U32_S *)(x))->v)
+
+
+//***************************************
+// Compiler-specific Functions and Macros
+//***************************************
#define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
-// Note : under GCC, it may sometimes be faster to enable the (2nd) macro definition, instead of using win32 intrinsic
-#if defined(_WIN32)
+// Note : although _rotl exists for minGW (GCC under windows), performance seems poor
+#if defined(_MSC_VER)
# define XXH_rotl32(x,r) _rotl(x,r)
#else
# define XXH_rotl32(x,r) ((x << r) | (x >> (32 - r)))
@@ -147,7 +185,9 @@ static inline U32 XXH_swap32 (U32 x) { //**************************************
// Macros
//**************************************
-#define XXH_LE32(p) (XXH_BIG_ENDIAN ? XXH_swap32(*(U32*)(p)) : *(U32*)(p))
+#define XXH_STATIC_ASSERT(c) { enum { XXH_static_assert = 1/(!!(c)) }; } // use only *after* variable declarations
+#define XXH_LE32(p) (XXH_BIG_ENDIAN ? XXH_swap32(A32(p)) : A32(p))
+#define XXH_alignedLE32(p) (XXH_BIG_ENDIAN ? XXH_swap32(*(U32*)(p)) : *(U32*)(p))
@@ -155,6 +195,53 @@ static inline U32 XXH_swap32 (U32 x) { // Simple Hash Functions
//****************************
+#if !defined(XXH_USE_UNALIGNED_ACCESS)
+// Specific version, for aligned 32-bits input. Useless for CPU supporting unaligned access.
+static U32 XXH32_alignedInput(const void* input, int len, U32 seed)
+{
+ const BYTE* p = (const BYTE*)input;
+ const BYTE* const bEnd = p + len;
+ U32 h32;
+
+ 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_alignedLE32(p) * PRIME32_2; v1 = XXH_rotl32(v1, 13); v1 *= PRIME32_1; p+=4;
+ v2 += XXH_alignedLE32(p) * PRIME32_2; v2 = XXH_rotl32(v2, 13); v2 *= PRIME32_1; p+=4;
+ v3 += XXH_alignedLE32(p) * PRIME32_2; v3 = XXH_rotl32(v3, 13); v3 *= PRIME32_1; p+=4;
+ v4 += XXH_alignedLE32(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_alignedLE32(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
+
U32 XXH32(const void* input, int len, U32 seed)
{
#if 0
@@ -172,6 +259,10 @@ U32 XXH32(const void* input, int len, U32 seed) if (p==NULL) { len=0; p=(const BYTE*)16; }
#endif
+#if !defined(XXH_USE_UNALIGNED_ACCESS)
+ if ((((U32)p) & 3) == 0) return XXH32_alignedInput(input, len, seed); // Input is aligned, let's leverage the speed advantage
+#endif
+
if (len>=16)
{
const BYTE* const limit = bEnd - 16;
@@ -229,21 +320,25 @@ U32 XXH32(const void* input, int len, U32 seed) struct XXH_state32_t
{
+ U64 total_len;
U32 seed;
U32 v1;
U32 v2;
U32 v3;
U32 v4;
- U64 total_len;
- char memory[16];
int memsize;
+ char memory[16];
};
-int XXH32_sizeofState() { return sizeof(struct XXH_state32_t); }
+int XXH32_sizeofState()
+{
+ XXH_STATIC_ASSERT(XXH32_SIZEOFSTATE >= sizeof(struct XXH_state32_t)); // A compilation error here means XXH32_SIZEOFSTATE is not large enough
+ return sizeof(struct XXH_state32_t);
+}
-XXH_errorcode XXH32_resetState(void* state_in, unsigned int seed)
+XXH_errorcode XXH32_resetState(void* state_in, U32 seed)
{
struct XXH_state32_t * state = (struct XXH_state32_t *) state_in;
state->seed = seed;
@@ -253,15 +348,15 @@ XXH_errorcode XXH32_resetState(void* state_in, unsigned int seed) state->v4 = seed - PRIME32_1;
state->total_len = 0;
state->memsize = 0;
- return OK;
+ return XXH_OK;
}
void* XXH32_init (U32 seed)
{
- struct XXH_state32_t * state = (struct XXH_state32_t *) malloc (sizeof(struct XXH_state32_t));
+ void* state = XXH_malloc (sizeof(struct XXH_state32_t));
XXH32_resetState(state, seed);
- return (void*)state;
+ return state;
}
@@ -279,14 +374,14 @@ XXH_errorcode XXH32_update (void* state_in, const void* input, int len) if (state->memsize + len < 16) // fill in tmp buffer
{
- memcpy(state->memory + state->memsize, input, len);
+ XXH_memcpy(state->memory + state->memsize, input, len);
state->memsize += len;
- return OK;
+ return XXH_OK;
}
if (state->memsize) // some data left from previous update
{
- memcpy(state->memory + state->memsize, input, 16-state->memsize);
+ XXH_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++;
@@ -322,11 +417,11 @@ XXH_errorcode XXH32_update (void* state_in, const void* input, int len) if (p < bEnd)
{
- memcpy(state->memory, p, bEnd-p);
+ XXH_memcpy(state->memory, p, bEnd-p);
state->memsize = (int)(bEnd-p);
}
- return OK;
+ return XXH_OK;
}
@@ -337,7 +432,6 @@ U32 XXH32_intermediateDigest (void* state_in) 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);
@@ -377,7 +471,7 @@ U32 XXH32_digest (void* state_in) {
U32 h32 = XXH32_intermediateDigest(state_in);
- free(state_in);
+ XXH_free(state_in);
return h32;
}
|