lz4.c no longer depends on lz4_decoder.h (removed)

Decompression speed improved under GCC
Improved speed of LZ4_decompress_safe_partial()
Added new utility : fullbench 
Modified x64 detection macro, as suggested by David Karner
Improved Fuzzer tool
Updated xxHash to r30

git-svn-id: https://lz4.googlecode.com/svn/trunk@97 650e7d94-2a16-8b24-b05c-7c0b3f6821cd

1 files changed, 127 insertions, 33 deletions

diff --git a/xxhash.c b/xxhash.c
index 3c5f560..6dacdcb 100644
--- a/xxhash.c
+++ b/xxhash.c
@@ -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;

 }