From 61289dea1d94510a4d6386bc44c08d3d15083123 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Sun, 2 Nov 2014 22:32:12 +0100 Subject: [PATCH] Optimized LZ4_saveDictHC() --- lz4.c | 6 ++--- lz4.h | 2 +- lz4hc.c | 51 ++++++++++++++++++++++++++--------------- lz4hc.h | 2 +- programs/fullbench.c | 65 +++++++++++++++++++++++++++++++++------------------- 5 files changed, 79 insertions(+), 47 deletions(-) diff --git a/lz4.c b/lz4.c index e8693ae..9345e74 100644 --- a/lz4.c +++ b/lz4.c @@ -701,6 +701,7 @@ void LZ4_resetStream (LZ4_stream_t* LZ4_stream) LZ4_stream_t* LZ4_createStream(void) { LZ4_stream_t* lz4s = (LZ4_stream_t*)ALLOCATOR(4, LZ4_STREAMSIZE_U32); + LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal)); /* A compilation error here means LZ4_STREAMSIZE is not large enough */ LZ4_resetStream(lz4s); return lz4s; } @@ -719,14 +720,13 @@ int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize) const BYTE* const dictEnd = p + dictSize; const BYTE* base; - LZ4_STATIC_ASSERT(LZ4_STREAMSIZE >= sizeof(LZ4_stream_t_internal)); /* A compilation error here means LZ4_STREAMSIZE is not large enough */ if (dict->initCheck) LZ4_resetStream(LZ4_dict); /* Uninitialized structure detected */ if (dictSize < MINMATCH) { dict->dictionary = NULL; dict->dictSize = 0; - return 1; + return 0; } if (p <= dictEnd - 64 KB) p = dictEnd - 64 KB; @@ -741,7 +741,7 @@ int LZ4_loadDict (LZ4_stream_t* LZ4_dict, const char* dictionary, int dictSize) p+=3; } - return 1; + return dict->dictSize; } diff --git a/lz4.h b/lz4.h index 0a8a772..3c35c6e 100644 --- a/lz4.h +++ b/lz4.h @@ -200,7 +200,7 @@ int LZ4_freeStream (LZ4_stream_t* LZ4_streamPtr); * Use this function to load a static dictionary into LZ4_stream. * Any previous data will be forgotten, only 'dictionary' will remain in memory. * Loading a size of 0 is allowed. - * Return : 1 if OK, 0 if error + * Return : dictionary size, in bytes (necessarily <= 64 KB) */ int LZ4_loadDict (LZ4_stream_t* LZ4_streamPtr, const char* dictionary, int dictSize); diff --git a/lz4hc.c b/lz4hc.c index 1422a7c..8f6f25b 100644 --- a/lz4hc.c +++ b/lz4hc.c @@ -250,14 +250,14 @@ typedef struct { U32 hashTable[HASHTABLESIZE]; U16 chainTable[MAXD]; - const BYTE* inputBuffer; - const BYTE* base; - const BYTE* end; - const BYTE* dictBase; - U32 dictLimit; + const BYTE* end; /* next block here to keep current prefix as prefix */ + const BYTE* base; /* All index relative to this position */ + const BYTE* dictBase; /* alternate base for extDict */ + U32 dictLimit; /* below that point, need extDict */ + U32 lowLimit; /* below that point, no more dict */ U32 nextToUpdate; U32 compressionLevel; - U32 lowLimit; + const BYTE* inputBuffer; /* deprecated */ } LZ4HC_Data_Structure; @@ -342,7 +342,7 @@ FORCE_INLINE int LZ4_NbCommonBytes (register U32 val) #endif -FORCE_INLINE void LZ4HC_init (LZ4HC_Data_Structure* hc4, const BYTE* base) +static void LZ4HC_init (LZ4HC_Data_Structure* hc4, const BYTE* base) { MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable)); MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable)); @@ -857,10 +857,16 @@ void LZ4_resetStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel) int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int dictSize) { - LZ4HC_init ((LZ4HC_Data_Structure*) LZ4_streamHCPtr, (const BYTE*) dictionary); - if (dictSize >= 4) LZ4HC_Insert ((LZ4HC_Data_Structure*) LZ4_streamHCPtr, (const BYTE*)dictionary +(dictSize-3)); - ((LZ4HC_Data_Structure*) LZ4_streamHCPtr)->end = (const BYTE*)dictionary + dictSize; - return 1; + LZ4HC_Data_Structure* streamPtr = (LZ4HC_Data_Structure*) LZ4_streamHCPtr; + if (dictSize > 64 KB) + { + dictionary += dictSize - 64 KB; + dictSize = 64 KB; + } + LZ4HC_init (streamPtr, (const BYTE*)dictionary); + if (dictSize >= 4) LZ4HC_Insert (streamPtr, (const BYTE*)dictionary +(dictSize-3)); + streamPtr->end = (const BYTE*)dictionary + dictSize; + return dictSize; } @@ -917,20 +923,27 @@ int LZ4_compressHC_limitedOutput_continue (LZ4_streamHC_t* LZ4_streamHCPtr, cons int LZ4_saveDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, char* safeBuffer, int dictSize) { - LZ4HC_Data_Structure* sp = (LZ4HC_Data_Structure*)LZ4_streamHCPtr; + LZ4HC_Data_Structure* streamPtr = (LZ4HC_Data_Structure*)LZ4_streamHCPtr; + int prefixSize = (int)(streamPtr->end - (streamPtr->base + streamPtr->dictLimit)); if (dictSize > 64 KB) dictSize = 64 KB; - if (dictSize < 0) dictSize = 0; - if (dictSize > (sp->end - (sp->base + sp->lowLimit))) dictSize = (int)(sp->end - (sp->base + sp->lowLimit)); - memcpy(safeBuffer, sp->end - dictSize, dictSize); - LZ4_loadDictHC(LZ4_streamHCPtr, safeBuffer, dictSize); + if (dictSize < 4) dictSize = 0; + if (dictSize > prefixSize) dictSize = prefixSize; + memcpy(safeBuffer, streamPtr->end - dictSize, dictSize); + //LZ4_loadDictHC(LZ4_streamHCPtr, safeBuffer, dictSize); + { + U32 endIndex = (U32)(streamPtr->end - streamPtr->base); + streamPtr->end = (const BYTE*)safeBuffer + dictSize; + streamPtr->base = streamPtr->end - endIndex; + streamPtr->dictLimit = endIndex - dictSize; + streamPtr->lowLimit = endIndex - dictSize; + } return dictSize; } - /*********************************** -Deprecated Streaming functions -***********************************/ + * Deprecated Functions + ***********************************/ int LZ4_sizeofStreamStateHC(void) { return LZ4_STREAMHCSIZE; } int LZ4_resetStreamStateHC(void* state, const char* inputBuffer) diff --git a/lz4hc.h b/lz4hc.h index 5fbf398..23ad7c1 100644 --- a/lz4hc.h +++ b/lz4hc.h @@ -145,7 +145,7 @@ They work like usual LZ4_compressHC() or LZ4_compressHC_limitedOutput(), but use Previous memory blocks (including initial dictionary when present) must remain accessible and unmodified during compression. If, for any reason, previous data block can't be preserved in memory during next compression block, -you can save it to a safer memory space, +you must save it to a safer memory space, using LZ4_saveDictHC(). */ diff --git a/programs/fullbench.c b/programs/fullbench.c index 4caea16..3592223 100644 --- a/programs/fullbench.c +++ b/programs/fullbench.c @@ -326,6 +326,20 @@ static int local_LZ4F_compressFrame(const char* in, char* out, int inSize) return (int)LZ4F_compressFrame(out, 2*inSize + 16, in, inSize, NULL); } +static int local_LZ4_saveDict(const char* in, char* out, int inSize) +{ + (void)in; + return LZ4_saveDict(&LZ4_dict, out, inSize); +} + +LZ4_streamHC_t LZ4_dictHC; +static int local_LZ4_saveDictHC(const char* in, char* out, int inSize) +{ + (void)in; + return LZ4_saveDictHC(&LZ4_dictHC, out, inSize); +} + + static int local_LZ4_decompress_fast(const char* in, char* out, int inSize, int outSize) { (void)inSize; @@ -386,7 +400,7 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) { int fileIdx=0; char* orig_buff; -# define NB_COMPRESSION_ALGORITHMS 14 +# define NB_COMPRESSION_ALGORITHMS 16 double totalCTime[NB_COMPRESSION_ALGORITHMS+1] = {0}; double totalCSize[NB_COMPRESSION_ALGORITHMS+1] = {0}; # define NB_DECOMPRESSION_ALGORITHMS 9 @@ -416,8 +430,8 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) // Init - stateLZ4 = malloc(LZ4_sizeofState()); - stateLZ4HC = malloc(LZ4_sizeofStateHC()); + stateLZ4 = LZ4_createStream(); + stateLZ4HC = LZ4_createStreamHC(); // Check file existence inFileName = fileNamesTable[fileIdx++]; @@ -483,23 +497,6 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) DISPLAY("\r%79s\r", ""); DISPLAY(" %s : \n", inFileName); - // Init chunks data - { - int i; - size_t remaining = benchedSize; - char* in = orig_buff; - char* out = compressed_buff; - nbChunks = (int) ((int)benchedSize / chunkSize) + 1; - for (i=0; i chunkSize) { chunkP[i].origSize = chunkSize; remaining -= chunkSize; } else { chunkP[i].origSize = (int)remaining; remaining = 0; } - chunkP[i].compressedBuffer = out; out += maxCompressedChunkSize; - chunkP[i].compressedSize = 0; - } - } - // Compression Algorithms for (cAlgNb=1; (cAlgNb <= NB_COMPRESSION_ALGORITHMS) && (compressionTest); cAlgNb++) { @@ -508,6 +505,23 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) void* (*initFunction)(const char*) = NULL; double bestTime = 100000000.; + // Init data chunks + { + int i; + size_t remaining = benchedSize; + char* in = orig_buff; + char* out = compressed_buff; + nbChunks = (int) ((int)benchedSize / chunkSize) + 1; + for (i=0; i chunkSize) { chunkP[i].origSize = chunkSize; remaining -= chunkSize; } else { chunkP[i].origSize = (int)remaining; remaining = 0; } + chunkP[i].compressedBuffer = out; out += maxCompressedChunkSize; + chunkP[i].compressedSize = 0; + } + } + if ((compressionAlgo != ALL_COMPRESSORS) && (compressionAlgo != cAlgNb)) continue; switch(cAlgNb) @@ -528,6 +542,12 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) case 14: compressionFunction = local_LZ4F_compressFrame; compressorName = "LZ4F_compressFrame"; chunkP[0].origSize = (int)benchedSize; nbChunks=1; break; + case 15: compressionFunction = local_LZ4_saveDict; compressorName = "LZ4_saveDict"; + LZ4_loadDict(&LZ4_dict, chunkP[0].origBuffer, chunkP[0].origSize); + break; + case 16: compressionFunction = local_LZ4_saveDictHC; compressorName = "LZ4_saveDictHC"; + LZ4_loadDictHC(&LZ4_dictHC, chunkP[0].origBuffer, chunkP[0].origSize); + break; default : DISPLAY("ERROR ! Bad algorithm Id !! \n"); free(chunkP); return 1; } @@ -537,7 +557,7 @@ int fullSpeedBench(char** fileNamesTable, int nbFiles) int milliTime; PROGRESS("%1i-%-26.26s : %9i ->\r", loopNb, compressorName, (int)benchedSize); - { size_t i; for (i=0; i