LZ4 compression supports block dependency (argument -BD within lz4c command line)

fullbench : added bench of LZ4_compress_continue(), LZ4_compress_limitedOutput_continue(), LZ4_compressHC_continue() and LZ4_compressHC_limitedOutput_continue()


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

6 files changed, 204 insertions, 40 deletions

diff --git a/fullbench.c b/fullbench.c
index 779e1ba..abb4f92 100644
--- a/fullbench.c
+++ b/fullbench.c
@@ -255,11 +255,32 @@ static inline int local_LZ4_compress_limitedOutput(const char* in, char* out, in
     return LZ4_compress_limitedOutput(in, out, inSize, LZ4_compressBound(inSize));

 }

 

+static void* ctx;

+static inline int local_LZ4_compress_continue(const char* in, char* out, int inSize)

+{

+    return LZ4_compress_continue(ctx, in, out, inSize);

+}

+

+static inline int local_LZ4_compress_limitedOutput_continue(const char* in, char* out, int inSize)

+{

+    return LZ4_compress_limitedOutput_continue(ctx, in, out, inSize, LZ4_compressBound(inSize));

+}

+

 static inline int local_LZ4_compressHC_limitedOutput(const char* in, char* out, int inSize)

 {

     return LZ4_compressHC_limitedOutput(in, out, inSize, LZ4_compressBound(inSize));

 }

 

+static inline int local_LZ4_compressHC_continue(const char* in, char* out, int inSize)

+{

+    return LZ4_compressHC_continue(ctx, in, out, inSize);

+}

+

+static inline int local_LZ4_compressHC_limitedOutput_continue(const char* in, char* out, int inSize)

+{

+    return LZ4_compressHC_limitedOutput_continue(ctx, in, out, inSize, LZ4_compressBound(inSize));

+}

+

 static inline int local_LZ4_decompress_fast(const char* in, char* out, int inSize, int outSize)

 {

     (void)inSize;

@@ -283,15 +304,15 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles)
 {

   int fileIdx=0;

   char* orig_buff;

-# define NB_COMPRESSION_ALGORITHMS 4

+# define NB_COMPRESSION_ALGORITHMS 8

 # define MINCOMPRESSIONCHAR '0'

-# define MAXCOMPRESSIONCHAR '3'

-  static char* compressionNames[] = { "LZ4_compress", "LZ4_compress_limitedOutput", "LZ4_compressHC", "LZ4_compressHC_limitedOutput" };

+# define MAXCOMPRESSIONCHAR (MINCOMPRESSIONCHAR + NB_COMPRESSION_ALGORITHMS)

+  static char* compressionNames[] = { "LZ4_compress", "LZ4_compress_limitedOutput", "LZ4_compress_continue", "LZ4_compress_limitedOutput_continue", "LZ4_compressHC", "LZ4_compressHC_limitedOutput", "LZ4_compressHC_continue", "LZ4_compressHC_limitedOutput_continue" };

   double totalCTime[NB_COMPRESSION_ALGORITHMS] = {0};

   double totalCSize[NB_COMPRESSION_ALGORITHMS] = {0};

 # define NB_DECOMPRESSION_ALGORITHMS 5

 # define MINDECOMPRESSIONCHAR '0'

-# define MAXDECOMPRESSIONCHAR '4'

+# define MAXDECOMPRESSIONCHAR (MINDECOMPRESSIONCHAR + NB_DECOMPRESSION_ALGORITHMS)

   static char* decompressionNames[] = { "LZ4_decompress_fast", "LZ4_decompress_fast_withPrefix64k", "LZ4_decompress_safe", "LZ4_decompress_safe_withPrefix64k", "LZ4_decompress_safe_partial" };

   double totalDTime[NB_DECOMPRESSION_ALGORITHMS] = {0};

 

@@ -397,6 +418,7 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles)
         {

             char* cName = compressionNames[cAlgNb];

             int (*compressionFunction)(const char*, char*, int);

+            void* (*initFunction)(const char*) = NULL;

             double bestTime = 100000000.;

 

             if ((compressionAlgo != ALL_COMPRESSORS) && (compressionAlgo != cAlgNb)) continue;

@@ -405,8 +427,12 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles)
             {

             case 0: compressionFunction = LZ4_compress; break;

             case 1: compressionFunction = local_LZ4_compress_limitedOutput; break;

-            case 2: compressionFunction = LZ4_compressHC; break;

-            case 3: compressionFunction = local_LZ4_compressHC_limitedOutput; break;

+            case 2: compressionFunction = local_LZ4_compress_continue; initFunction = LZ4_create; break;

+            case 3: compressionFunction = local_LZ4_compress_limitedOutput_continue; initFunction = LZ4_create; break;

+            case 4: compressionFunction = LZ4_compressHC; break;

+            case 5: compressionFunction = local_LZ4_compressHC_limitedOutput; break;

+            case 6: compressionFunction = local_LZ4_compressHC_continue; initFunction = LZ4_createHC; break;

+            case 7: compressionFunction = local_LZ4_compressHC_limitedOutput_continue; initFunction = LZ4_createHC; break;

             default : DISPLAY("ERROR ! Bad algorithm Id !! \n"); free(chunkP); return 1;

             }

 

@@ -424,11 +450,13 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles)
                 milliTime = BMK_GetMilliStart();

                 while(BMK_GetMilliSpan(milliTime) < TIMELOOP)

                 {

+                    if (initFunction!=NULL) ctx = initFunction(chunkP[0].origBuffer);

                     for (chunkNb=0; chunkNb<nbChunks; chunkNb++)

                     {

                         chunkP[chunkNb].compressedSize = compressionFunction(chunkP[chunkNb].origBuffer, chunkP[chunkNb].compressedBuffer, chunkP[chunkNb].origSize);

                         if (chunkP[chunkNb].compressedSize==0) DISPLAY("ERROR ! %s() = 0 !! \n", cName), exit(1);

                     }

+                    if (initFunction!=NULL) free(ctx);

                     nb_loops++;

                 }

                 milliTime = BMK_GetMilliSpan(milliTime);

diff --git a/lz4.c b/lz4.c
index 549edad..73783ba 100644
--- a/lz4.c
+++ b/lz4.c
@@ -144,10 +144,18 @@
 

 

 //**************************************

+// Memory routines

+//**************************************

+#include <stdlib.h>   // malloc, calloc, free

+#define ALLOCATOR(n,s) calloc(n,s)

+#define FREEMEM        free

+#include <string.h>   // memset, memcpy

+#define MEM_INIT       memset

+

+

+//**************************************

 // Includes

 //**************************************

-#include <stdlib.h>   // for malloc

-#include <string.h>   // for memset

 #include "lz4.h"

 

 

@@ -203,14 +211,16 @@ typedef struct {size_t v;} _PACKED size_t_S;
 //**************************************

 // Constants

 //**************************************

+#define LZ4_HASHLOG   (MEMORY_USAGE-2)

 #define HASHTABLESIZE (1 << MEMORY_USAGE)

+#define HASHNBCELLS4  (1 << LZ4_HASHLOG)

 

 #define MINMATCH 4

 

 #define COPYLENGTH 8

 #define LASTLITERALS 5

 #define MFLIMIT (COPYLENGTH+MINMATCH)

-#define MINLENGTH (MFLIMIT+1)

+const int LZ4_minLength = (MFLIMIT+1);

 

 #define LZ4_64KLIMIT ((1<<16) + (MFLIMIT-1))

 #define SKIPSTRENGTH 6     // Increasing this value will make the compression run slower on incompressible data

@@ -223,6 +233,30 @@ typedef struct {size_t v;} _PACKED size_t_S;
 #define RUN_BITS (8-ML_BITS)

 #define RUN_MASK ((1U<<RUN_BITS)-1)

 

+#define KB *(1U<<10)

+#define MB *(1U<<20)

+#define GB *(1U<<30)

+

+

+//**************************************

+// Structures and local types

+//**************************************

+

+typedef struct {

+    U32 hashTable[HASHNBCELLS4];

+    Ptr bufferStart;

+    Ptr base;

+    Ptr nextBlock;

+} LZ4_Data_Structure;

+

+typedef enum { notLimited = 0, limited = 1 } limitedOutput_directive;

+typedef enum { byPtr, byU32, byU16 } tableType_t;

+

+typedef enum { noPrefix = 0, withPrefix = 1 } prefix64k_directive;

+

+typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;

+typedef enum { full = 0, partial = 1 } earlyEnd_directive;

+

 

 //**************************************

 // Architecture-specific macros

@@ -327,10 +361,6 @@ FORCE_INLINE int LZ4_NbCommonBytes (register U32 val)
 //****************************

 // Compression functions

 //****************************

-#define LZ4_HASHLOG (MEMORY_USAGE-2)

-typedef enum { notLimited = 0, limited = 1 } limitedOutput_directive;

-typedef enum { byPtr, byU32, byU16 } tableType_t;

-

 FORCE_INLINE int LZ4_hashSequence(U32 sequence, tableType_t tableType)

 {

     if (tableType == byU16)

@@ -379,10 +409,12 @@ FORCE_INLINE int LZ4_compress_generic(
                  int maxOutputSize,

 

                  limitedOutput_directive limitedOutput,

-                 tableType_t tableType)

+                 tableType_t tableType,

+                 prefix64k_directive prefix)

 {

     Ptr ip = (Ptr) source;

-    Ptr const base = (Ptr) source;

+    Ptr const base = (prefix==withPrefix) ? ((LZ4_Data_Structure*)ctx)->base : (Ptr) source;

+    Ptr const lowLimit = ((prefix==withPrefix) ? ((LZ4_Data_Structure*)ctx)->bufferStart : (Ptr)source);

     Ptr anchor = (Ptr) source;

     Ptr const iend = ip + inputSize;

     Ptr const mflimit = iend - MFLIMIT;

@@ -396,8 +428,10 @@ FORCE_INLINE int LZ4_compress_generic(
     U32 forwardH;

 

     // Init conditions

-    if (inputSize<MINLENGTH) goto _last_literals;

-    if ((tableType == byU16) && (inputSize>=LZ4_64KLIMIT)) return 0;   // Size too large (not within 64K limit)

+    if ((prefix==withPrefix) && (ip != ((LZ4_Data_Structure*)ctx)->nextBlock)) return 0;   // must continue from end of previous block

+    if (prefix==withPrefix) ((LZ4_Data_Structure*)ctx)->nextBlock=iend;                    // do it now, due to potential early exit

+    if ((tableType == byU16) && (inputSize>=LZ4_64KLIMIT)) return 0;                       // Size too large (not within 64K limit)

+    if (inputSize<LZ4_minLength) goto _last_literals;                                      // Input too small, no compression (all literals)

 

     // First Byte

     LZ4_putPosition(ip, ctx, tableType, base);

@@ -427,7 +461,7 @@ FORCE_INLINE int LZ4_compress_generic(
         } while ((ref + MAX_DISTANCE < ip) || (A32(ref) != A32(ip)));

 

         // Catch up

-        while ((ip>anchor) && (ref>(BYTE*)source) && unlikely(ip[-1]==ref[-1])) { ip--; ref--; }

+        while ((ip>anchor) && (ref > lowLimit) && unlikely(ip[-1]==ref[-1])) { ip--; ref--; }

 

         // Encode Literal length

         length = (int)(ip - anchor);

@@ -512,54 +546,111 @@ _last_literals:
 int LZ4_compress(const char* source, char* dest, int inputSize)

 {

 #if (HEAPMODE)

-    void* ctx = calloc(1U<<(MEMORY_USAGE-2), 4);   // Aligned on 4-bytes boundaries

+    void* ctx = ALLOCATOR(HASHNBCELLS4, 4);   // Aligned on 4-bytes boundaries

 #else

     U32 ctx[1U<<(MEMORY_USAGE-2)] = {0};           // Ensure data is aligned on 4-bytes boundaries

 #endif

     int result;

 

     if (inputSize < (int)LZ4_64KLIMIT)

-        result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, byU16);

+        result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, byU16, noPrefix);

     else

-        result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr);

+        result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, 0, notLimited, (sizeof(void*)==8) ? byU32 : byPtr, noPrefix);

 

 #if (HEAPMODE)

-    free(ctx);

+    FREEMEM(ctx);

 #endif

     return result;

 }

 

+int LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize)

+{

+    return LZ4_compress_generic(LZ4_Data, source, dest, inputSize, 0, notLimited, byU32, withPrefix);

+}

+

 

 int LZ4_compress_limitedOutput(const char* source, char* dest, int inputSize, int maxOutputSize)

 {

 #if (HEAPMODE)

-    void* ctx = calloc(1U<<(MEMORY_USAGE-2), 4);   // Aligned on 4-bytes boundaries

+    void* ctx = ALLOCATOR(HASHNBCELLS4, 4);   // Aligned on 4-bytes boundaries

 #else

     U32 ctx[1U<<(MEMORY_USAGE-2)] = {0};           // Ensure data is aligned on 4-bytes boundaries

 #endif

     int result;

 

     if (inputSize < (int)LZ4_64KLIMIT)

-        result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limited, byU16);

+        result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limited, byU16, noPrefix);

     else

-        result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limited, (sizeof(void*)==8) ? byU32 : byPtr);

+        result = LZ4_compress_generic((void*)ctx, source, dest, inputSize, maxOutputSize, limited, (sizeof(void*)==8) ? byU32 : byPtr, noPrefix);

 

 #if (HEAPMODE)

-    free(ctx);

+    FREEMEM(ctx);

 #endif

     return result;

 }

 

+int LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize)

+{

+    return LZ4_compress_generic(LZ4_Data, source, dest, inputSize, maxOutputSize, limited, byU32, withPrefix);

+}

 

 

 //****************************

-// Decompression functions

+// Stream functions

 //****************************

 

-typedef enum { noPrefix = 0, withPrefix = 1 } prefix64k_directive;

-typedef enum { endOnOutputSize = 0, endOnInputSize = 1 } endCondition_directive;

-typedef enum { full = 0, partial = 1 } earlyEnd_directive;

+FORCE_INLINE void LZ4_init(LZ4_Data_Structure* lz4ds, Ptr base)

+{

+    MEM_INIT(lz4ds->hashTable, 0, sizeof(lz4ds->hashTable));

+    lz4ds->bufferStart = base;

+    lz4ds->base = base;

+    lz4ds->nextBlock = base;

+}

+

+

+void* LZ4_create (const char* inputBuffer)

+{

+    void* lz4ds = ALLOCATOR(1, sizeof(LZ4_Data_Structure));

+    LZ4_init ((LZ4_Data_Structure*)lz4ds, (Ptr)inputBuffer);

+    return lz4ds;

+}

+

 

+int LZ4_free (void* LZ4_Data)

+{

+    FREEMEM(LZ4_Data);

+    return (0);

+}

+

+

+char* LZ4_slideInputBuffer (void* LZ4_Data)

+{

+    LZ4_Data_Structure* lz4ds = (LZ4_Data_Structure*)LZ4_Data;

+    size_t delta = lz4ds->nextBlock - (lz4ds->bufferStart + 64 KB);

+

+    if(lz4ds->base - delta > lz4ds->base)   // underflow control

+    {

+        size_t newBaseDelta = (lz4ds->nextBlock - 64 KB) - lz4ds->base;

+        int nH;

+

+        for (nH=0; nH < HASHNBCELLS4; nH++)

+        {

+            if (lz4ds->hashTable[nH] < (U32)newBaseDelta) lz4ds->hashTable[nH] = 0;

+            else lz4ds->hashTable[nH] -= newBaseDelta;

+        }

+        lz4ds->base += newBaseDelta;

+    }

+    memcpy((void*)(lz4ds->bufferStart), (const void*)(lz4ds->nextBlock - 64 KB), 64 KB);

+    lz4ds->nextBlock -= delta;

+    lz4ds->base -= delta;

+

+    return (char*)(lz4ds->nextBlock);

+}

+

+

+//****************************

+// Decompression functions

+//****************************

 

 // This generic decompression function cover all use cases.

 // It shall be instanciated several times, using different sets of directives

diff --git a/lz4.h b/lz4.h
index ab73fdc..8f87908 100644
--- a/lz4.h
+++ b/lz4.h
@@ -146,6 +146,47 @@ int LZ4_decompress_fast_withPrefix64k (const char* source, char* dest, int outpu
 */

 

 

+

+//****************************

+// Stream Functions

+//****************************

+

+void* LZ4_create (const char* inputBuffer);

+int   LZ4_compress_continue (void* LZ4_Data, const char* source, char* dest, int inputSize);

+int   LZ4_compress_limitedOutput_continue (void* LZ4_Data, const char* source, char* dest, int inputSize, int maxOutputSize);

+char* LZ4_slideInputBuffer (void* LZ4_Data);

+int   LZ4_free (void* LZ4_Data);

+

+/* 

+These functions allow the compression of dependent blocks, where each block benefits from prior 64 KB within preceding blocks.

+In order to achieve this, it is necessary to start creating the LZ4 Data Structure, thanks to the function :

+

+void* LZ4_create (const char* inputBuffer);

+The result of the function is the (void*) pointer on the LZ4 Data Structure.

+This pointer will be needed in all other functions.

+If the pointer returned is NULL, then the allocation has failed, and compression must be aborted.

+The only parameter 'const char* inputBuffer' must, obviously, point at the beginning of input buffer.

+The input buffer must be already allocated, and size at least 192KB.

+'inputBuffer' will also be the 'const char* source' of the first block.

+

+All blocks are expected to lay next to each other within the input buffer, starting from 'inputBuffer'.

+To compress each block, use either LZ4_compress_continue() or LZ4_compress_limitedOutput_continue().

+Their behavior are identical to LZ4_compress() or LZ4_compress_limitedOutput(), 

+but require the LZ4 Data Structure as their first argument, and check that each block starts right after the previous one.

+If next block does not begin immediately after the previous one, the compression will fail (return 0).

+

+When it's no longer possible to lay the next block after the previous one (not enough space left into input buffer), a call to : 

+char* LZ4_slideInputBuffer(void* LZ4_Data);

+must be performed. It will typically copy the latest 64KB of input at the beginning of input buffer.

+Note that, for this function to work properly, minimum size of an input buffer must be 192KB.

+==> The memory position where the next input data block must start is provided as the result of the function.

+

+Compression can then resume, using LZ4_compress_continue() or LZ4_compress_limitedOutput_continue(), as usual.

+

+When compression is completed, a call to LZ4_free() will release the memory used by the LZ4 Data Structure.

+*/

+

+

 //****************************

 // Obsolete Functions

 //****************************

diff --git a/lz4c.c b/lz4c.c
index b6fc0ee..65a7ea2 100644
--- a/lz4c.c
+++ b/lz4c.c
@@ -378,7 +378,7 @@ int compress_file_blockDependency(char* input_filename, char* output_filename, i
     char* out_buff;

     FILE* finput;

     FILE* foutput;

-    int displayLevel = (compressionlevel>0);

+    int displayLevel = ((compressionlevel>0) && (!silence)) || (verbose);

     clock_t start, end;

     unsigned int blockSize, inputBufferSize;

     size_t sizeCheck, header_size;

@@ -390,6 +390,11 @@ int compress_file_blockDependency(char* input_filename, char* output_filename, i
     switch (compressionlevel)

     {

     case 0 :

+        initFunction = LZ4_create;

+        compressionFunction = LZ4_compress_limitedOutput_continue;

+        translateFunction = LZ4_slideInputBuffer;

+        freeFunction = LZ4_free;

+        break;

     case 1 :

     default:

         initFunction = LZ4_createHC;

diff --git a/lz4hc.c b/lz4hc.c
index 79fd3f7..db6b484 100644
--- a/lz4hc.c
+++ b/lz4hc.c
@@ -332,7 +332,7 @@ FORCE_INLINE int LZ4_NbCommonBytes (register U32 val)
 #endif

 

 

-FORCE_INLINE int LZ4_InitHC (LZ4HC_Data_Structure* hc4, const BYTE* base)

+FORCE_INLINE void LZ4_initHC (LZ4HC_Data_Structure* hc4, const BYTE* base)

 {

     MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable));

     MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable));

@@ -340,14 +340,13 @@ FORCE_INLINE int LZ4_InitHC (LZ4HC_Data_Structure* hc4, const BYTE* base)
     hc4->base = base;

     hc4->inputBuffer = base;

     hc4->end = base;

-    return 1;

 }

 

 

-void* LZ4_createHC (const char* slidingInputBuffer)

+void* LZ4_createHC (const char* inputBuffer)

 {

     void* hc4 = ALLOCATOR(sizeof(LZ4HC_Data_Structure));

-    LZ4_InitHC ((LZ4HC_Data_Structure*)hc4, (const BYTE*)slidingInputBuffer);

+    LZ4_initHC ((LZ4HC_Data_Structure*)hc4, (const BYTE*)inputBuffer);

     return hc4;

 }

 

diff --git a/lz4hc.h b/lz4hc.h
index 7db2160..107fd0f 100644
--- a/lz4hc.h
+++ b/lz4hc.h
@@ -70,7 +70,7 @@ Decompression functions are provided within LZ4 source code (see "lz4.h") (BSD l
 

 /* Advanced Functions */

 

-void* LZ4_createHC (const char* slidingInputBuffer);

+void* LZ4_createHC (const char* inputBuffer);

 int   LZ4_compressHC_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize);

 int   LZ4_compressHC_limitedOutput_continue (void* LZ4HC_Data, const char* source, char* dest, int inputSize, int maxOutputSize);

 char* LZ4_slideInputBufferHC (void* LZ4HC_Data);

@@ -80,15 +80,15 @@ int   LZ4_freeHC (void* LZ4HC_Data);
 These functions allow the compression of dependent blocks, where each block benefits from prior 64 KB within preceding blocks.

 In order to achieve this, it is necessary to start creating the LZ4HC Data Structure, thanks to the function :

 

-void* LZ4_createHC (const char* slidingInputBuffer);

+void* LZ4_createHC (const char* inputBuffer);

 The result of the function is the (void*) pointer on the LZ4HC Data Structure.

 This pointer will be needed in all other functions.

 If the pointer returned is NULL, then the allocation has failed, and compression must be aborted.

-The only parameter 'const char* slidingInputBuffer' must, obviously, point at the beginning of input buffer.

+The only parameter 'const char* inputBuffer' must, obviously, point at the beginning of input buffer.

 The input buffer must be already allocated, and size at least 192KB.

-'slidingInputBuffer' will also be the 'const char* source' of the first block.

+'inputBuffer' will also be the 'const char* source' of the first block.

 

-All blocks are expected to lay next to each other within the input buffer, starting from 'slidingInputBuffer'.

+All blocks are expected to lay next to each other within the input buffer, starting from 'inputBuffer'.

 To compress each block, use either LZ4_compressHC_continue() or LZ4_compressHC_limitedOutput_continue().

 Their behavior are identical to LZ4_compressHC() or LZ4_compressHC_limitedOutput(), 

 but require the LZ4HC Data Structure as their first argument, and check that each block starts right after the previous one.