diff options
author | Yann Collet <Cyan4973@users.noreply.github.com> | 2018-03-09 21:10:40 (GMT) |
---|---|---|
committer | GitHub <noreply@github.com> | 2018-03-09 21:10:40 (GMT) |
commit | 9dc249ee3cb3482a28762912132021094feb55a1 (patch) | |
tree | aa5719976b565ab2c3184419c735e33d1c6465bc | |
parent | 9f338ae204f4c04bb5b720f7bb804e764e4c820e (diff) | |
parent | 6c23f03b93608a444f8747940bca26708a58fa78 (diff) | |
download | lz4-9dc249ee3cb3482a28762912132021094feb55a1.zip lz4-9dc249ee3cb3482a28762912132021094feb55a1.tar.gz lz4-9dc249ee3cb3482a28762912132021094feb55a1.tar.bz2 |
Merge pull request #483 from lz4/dev
update to dev
-rw-r--r-- | Makefile | 11 | ||||
-rw-r--r-- | NEWS | 5 | ||||
-rw-r--r-- | contrib/gen_manual/Makefile | 8 | ||||
-rw-r--r-- | doc/lz4_manual.html | 27 | ||||
-rw-r--r-- | doc/lz4frame_manual.html | 13 | ||||
-rw-r--r-- | examples/Makefile | 2 | ||||
-rw-r--r-- | lib/README.md | 2 | ||||
-rw-r--r-- | lib/lz4.c | 7 | ||||
-rw-r--r-- | lib/lz4.h | 27 | ||||
-rw-r--r-- | lib/lz4frame.h | 9 | ||||
-rw-r--r-- | lib/lz4hc.c | 380 | ||||
-rw-r--r-- | lib/lz4opt.h | 356 | ||||
-rw-r--r-- | programs/bench.c | 67 | ||||
-rw-r--r-- | programs/util.h | 8 | ||||
-rw-r--r-- | tests/Makefile | 29 |
15 files changed, 476 insertions, 475 deletions
@@ -1,10 +1,8 @@ # ################################################################ # LZ4 - Makefile -# Copyright (C) Yann Collet 2011-2016 +# Copyright (C) Yann Collet 2011-present # All rights reserved. # -# This Makefile is validated for Linux, macOS, *BSD, Hurd, Solaris, MSYS2 targets -# # BSD license # Redistribution and use in source and binary forms, with or without modification, # are permitted provided that the following conditions are met: @@ -58,6 +56,7 @@ all: allmost manuals allmost: lib lz4 examples .PHONY: lib lib-release liblz4.a +lib: liblz4.a lib lib-release liblz4.a: @$(MAKE) -C $(LZ4DIR) $@ @@ -69,7 +68,7 @@ lz4 lz4-release : @cp $(PRGDIR)/lz4$(EXT) . .PHONY: examples -examples: +examples: liblz4.a $(MAKE) -C $(EXDIR) all .PHONY: manuals @@ -122,6 +121,10 @@ ifneq (,$(filter $(HOST_OS),MSYS POSIX)) list: @$(MAKE) -pRrq -f $(lastword $(MAKEFILE_LIST)) : 2>/dev/null | awk -v RS= -F: '/^# File/,/^# Finished Make data base/ {if ($$1 !~ "^[#.]") {print $$1}}' | sort | egrep -v -e '^[^[:alnum:]]' -e '^$@$$' | xargs +.PHONY: check +check: + $(MAKE) -C $(TESTDIR) test-lz4-essentials + .PHONY: test test: $(MAKE) -C $(TESTDIR) $@ @@ -1,3 +1,8 @@ +v1.8.2 +perf: slightly faster HC compression and decompression speed +perf: very small compression ratio improvement +cli : benchmark mode more accurate for small inputs + v1.8.1 perf : faster and stronger ultra modes (levels 10+) perf : slightly faster compression and decompression speed diff --git a/contrib/gen_manual/Makefile b/contrib/gen_manual/Makefile index 9fbe858..95abe2e 100644 --- a/contrib/gen_manual/Makefile +++ b/contrib/gen_manual/Makefile @@ -30,10 +30,10 @@ # ################################################################ -CFLAGS ?= -O3 -CFLAGS += -Wall -Wextra -Wcast-qual -Wcast-align -Wshadow -Wstrict-aliasing=1 -Wswitch-enum -Wno-comment -CFLAGS += $(MOREFLAGS) -FLAGS = $(CPPFLAGS) $(CFLAGS) $(LDFLAGS) +CXXFLAGS ?= -O3 +CXXFLAGS += -Wall -Wextra -Wcast-qual -Wcast-align -Wshadow -Wstrict-aliasing=1 -Wswitch-enum -Wno-comment +CXXFLAGS += $(MOREFLAGS) +FLAGS = $(CPPFLAGS) $(CXXFLAGS) $(LDFLAGS) LZ4API = ../../lib/lz4.h LZ4MANUAL = ../../doc/lz4_manual.html diff --git a/doc/lz4_manual.html b/doc/lz4_manual.html index ef715f8..d14467f 100644 --- a/doc/lz4_manual.html +++ b/doc/lz4_manual.html @@ -1,10 +1,10 @@ <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> -<title>1.8.1 Manual</title> +<title>1.8.2 Manual</title> </head> <body> -<h1>1.8.1 Manual</h1> +<h1>1.8.2 Manual</h1> <hr> <a name="Contents"></a><h2>Contents</h2> <ol> @@ -172,26 +172,29 @@ int LZ4_freeStream (LZ4_stream_t* streamPtr); </p></pre><BR> <pre><b>int LZ4_compress_fast_continue (LZ4_stream_t* streamPtr, const char* src, char* dst, int srcSize, int dstCapacity, int acceleration); -</b><p> Compress content into 'src' using data from previously compressed blocks, improving compression ratio. +</b><p> Compress 'src' content using data from previously compressed blocks, for better compression ratio. 'dst' buffer must be already allocated. If dstCapacity >= LZ4_compressBound(srcSize), compression is guaranteed to succeed, and runs faster. - Important : The previous 64KB of compressed data is assumed to remain preset and unmodified in memory! - If less than 64KB has been compressed all the data must be present. - Special 1 : If input buffer is a double-buffer, it can have any size, including < 64 KB. + Important : The previous 64KB of compressed data is assumed to remain present and unmodified in memory! + + Special 1 : When input is a double-buffer, they can have any size, including < 64 KB. + Make sure that buffers are separated by at least one byte. + This way, each block only depends on previous block. Special 2 : If input buffer is a ring-buffer, it can have any size, including < 64 KB. @return : size of compressed block - or 0 if there is an error (typically, compressed data cannot fit into 'dst') + or 0 if there is an error (typically, cannot fit into 'dst'). After an error, the stream status is invalid, it can only be reset or freed. </p></pre><BR> -<pre><b>int LZ4_saveDict (LZ4_stream_t* streamPtr, char* safeBuffer, int dictSize); -</b><p> If previously compressed data block is not guaranteed to remain available at its current memory location, +<pre><b>int LZ4_saveDict (LZ4_stream_t* streamPtr, char* safeBuffer, int maxDictSize); +</b><p> If last 64KB data cannot be guaranteed to remain available at its current memory location, save it into a safer place (char* safeBuffer). - Note : it's not necessary to call LZ4_loadDict() after LZ4_saveDict(), dictionary is immediately usable. - @return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error. + This is schematically equivalent to a memcpy() followed by LZ4_loadDict(), + but is much faster, because LZ4_saveDict() doesn't need to rebuild tables. + @return : saved dictionary size in bytes (necessarily <= maxDictSize), or 0 if error. </p></pre><BR> @@ -207,7 +210,7 @@ int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream); <pre><b>int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize); </b><p> An LZ4_streamDecode_t structure can be allocated once and re-used multiple times. Use this function to start decompression of a new stream of blocks. - A dictionary can optionnally be set. Use NULL or size 0 for a simple reset order. + A dictionary can optionnally be set. Use NULL or size 0 for a reset order. @return : 1 if OK, 0 if error </p></pre><BR> diff --git a/doc/lz4frame_manual.html b/doc/lz4frame_manual.html index 1ddf6d8..f0f7f5a 100644 --- a/doc/lz4frame_manual.html +++ b/doc/lz4frame_manual.html @@ -1,10 +1,10 @@ <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"> -<title>1.8.1 Manual</title> +<title>1.8.2 Manual</title> </head> <body> -<h1>1.8.1 Manual</h1> +<h1>1.8.2 Manual</h1> <hr> <a name="Contents"></a><h2>Contents</h2> <ol> @@ -153,10 +153,13 @@ LZ4F_errorCode_t LZ4F_freeCompressionContext(LZ4F_cctx* cctx); </p></pre><BR> <pre><b>size_t LZ4F_compressBound(size_t srcSize, const LZ4F_preferences_t* prefsPtr); -</b><p> Provides minimum dstCapacity for a given srcSize to guarantee operation success in worst case scenarios. - Estimation includes frame footer, which would be generated by LZ4F_compressEnd(). - Estimation doesn't include frame header, already generated by LZ4F_compressBegin(). +</b><p> Provides minimum dstCapacity required to guarantee compression success + given a srcSize and preferences, covering worst case scenario. prefsPtr is optional : when NULL is provided, preferences will be set to cover worst case scenario. + Estimation is valid for either LZ4F_compressUpdate(), LZ4F_flush() or LZ4F_compressEnd(), + Estimation includes the possibility that internal buffer might already be filled by up to (blockSize-1) bytes. + It also includes frame footer (ending + checksum), which would have to be generated by LZ4F_compressEnd(). + Estimation doesn't include frame header, as it was already generated by LZ4F_compressBegin(). Result is always the same for a srcSize and prefsPtr, so it can be trusted to size reusable buffers. When srcSize==0, LZ4F_compressBound() provides an upper bound for LZ4F_flush() and LZ4F_compressEnd() operations. diff --git a/examples/Makefile b/examples/Makefile index f9e9e7a..103e7ec 100644 --- a/examples/Makefile +++ b/examples/Makefile @@ -52,7 +52,7 @@ default: all all: printVersion doubleBuffer dictionaryRandomAccess ringBuffer ringBufferHC \ lineCompress frameCompress simpleBuffer -$(LZ4DIR)/liblz4.a: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c $(LZ4DIR)/lz4opt.h $(LZ4DIR)/lz4frame.c $(LZ4DIR)/lz4.h $(LZ4DIR)/lz4hc.h $(LZ4DIR)/lz4frame.h $(LZ4DIR)/lz4frame_static.h +$(LZ4DIR)/liblz4.a: $(LZ4DIR)/lz4.c $(LZ4DIR)/lz4hc.c $(LZ4DIR)/lz4frame.c $(LZ4DIR)/lz4.h $(LZ4DIR)/lz4hc.h $(LZ4DIR)/lz4frame.h $(LZ4DIR)/lz4frame_static.h $(MAKE) -C $(LZ4DIR) liblz4.a printVersion: printVersion.c $(LZ4DIR)/liblz4.a diff --git a/lib/README.md b/lib/README.md index fc5d4e9..7082fe3 100644 --- a/lib/README.md +++ b/lib/README.md @@ -15,7 +15,7 @@ They generate and decode data using [LZ4 block format]. For more compression ratio at the cost of compression speed, the High Compression variant called **lz4hc** is available. -Add files **`lz4hc.c`**, **`lz4hc.h`** and **`lz4opt.h`**. +Add files **`lz4hc.c`** and **`lz4hc.h`**. The variant still depends on regular `lib/lz4.*` source files. @@ -545,7 +545,7 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( const ptrdiff_t dictDelta = dictEnd - (const BYTE*)source; const BYTE* anchor = (const BYTE*) source; const BYTE* const iend = ip + inputSize; - const BYTE* const mflimit = iend - MFLIMIT; + const BYTE* const mflimitPlusOne = iend - MFLIMIT + 1; const BYTE* const matchlimit = iend - LASTLITERALS; BYTE* op = (BYTE*) dest; @@ -594,7 +594,8 @@ LZ4_FORCE_INLINE int LZ4_compress_generic( forwardIp += step; step = (searchMatchNb++ >> LZ4_skipTrigger); - if (unlikely(forwardIp > mflimit)) goto _last_literals; + if (unlikely(forwardIp > mflimitPlusOne)) goto _last_literals; + assert(ip < mflimitPlusOne); match = LZ4_getPositionOnHash(h, cctx->hashTable, tableType, base); if (dict==usingExtDict) { @@ -680,7 +681,7 @@ _next_match: anchor = ip; /* Test end of chunk */ - if (ip > mflimit) break; + if (ip >= mflimitPlusOne) break; /* Fill table */ LZ4_putPosition(ip-2, cctx->hashTable, tableType, base); @@ -93,7 +93,7 @@ extern "C" { /*------ Version ------*/ #define LZ4_VERSION_MAJOR 1 /* for breaking interface changes */ #define LZ4_VERSION_MINOR 8 /* for new (non-breaking) interface capabilities */ -#define LZ4_VERSION_RELEASE 1 /* for tweaks, bug-fixes, or development */ +#define LZ4_VERSION_RELEASE 2 /* for tweaks, bug-fixes, or development */ #define LZ4_VERSION_NUMBER (LZ4_VERSION_MAJOR *100*100 + LZ4_VERSION_MINOR *100 + LZ4_VERSION_RELEASE) @@ -236,7 +236,7 @@ LZ4LIB_API int LZ4_decompress_safe_partial (const char* src, char* dst, int srcS /*-********************************************* * Streaming Compression Functions ***********************************************/ -typedef union LZ4_stream_u LZ4_stream_t; /* incomplete type (defined later) */ +typedef union LZ4_stream_u LZ4_stream_t; /* incomplete type (defined later) */ /*! LZ4_createStream() and LZ4_freeStream() : * LZ4_createStream() will allocate and initialize an `LZ4_stream_t` structure. @@ -260,28 +260,31 @@ LZ4LIB_API void LZ4_resetStream (LZ4_stream_t* streamPtr); LZ4LIB_API int LZ4_loadDict (LZ4_stream_t* streamPtr, const char* dictionary, int dictSize); /*! LZ4_compress_fast_continue() : - * Compress content into 'src' using data from previously compressed blocks, improving compression ratio. + * Compress 'src' content using data from previously compressed blocks, for better compression ratio. * 'dst' buffer must be already allocated. * If dstCapacity >= LZ4_compressBound(srcSize), compression is guaranteed to succeed, and runs faster. * - * Important : The previous 64KB of compressed data is assumed to remain preset and unmodified in memory! - * If less than 64KB has been compressed all the data must be present. - * Special 1 : If input buffer is a double-buffer, it can have any size, including < 64 KB. + * Important : The previous 64KB of compressed data is assumed to remain present and unmodified in memory! + * + * Special 1 : When input is a double-buffer, they can have any size, including < 64 KB. + * Make sure that buffers are separated by at least one byte. + * This way, each block only depends on previous block. * Special 2 : If input buffer is a ring-buffer, it can have any size, including < 64 KB. * * @return : size of compressed block - * or 0 if there is an error (typically, compressed data cannot fit into 'dst') + * or 0 if there is an error (typically, cannot fit into 'dst'). * After an error, the stream status is invalid, it can only be reset or freed. */ LZ4LIB_API int LZ4_compress_fast_continue (LZ4_stream_t* streamPtr, const char* src, char* dst, int srcSize, int dstCapacity, int acceleration); /*! LZ4_saveDict() : - * If previously compressed data block is not guaranteed to remain available at its current memory location, + * If last 64KB data cannot be guaranteed to remain available at its current memory location, * save it into a safer place (char* safeBuffer). - * Note : it's not necessary to call LZ4_loadDict() after LZ4_saveDict(), dictionary is immediately usable. - * @return : saved dictionary size in bytes (necessarily <= dictSize), or 0 if error. + * This is schematically equivalent to a memcpy() followed by LZ4_loadDict(), + * but is much faster, because LZ4_saveDict() doesn't need to rebuild tables. + * @return : saved dictionary size in bytes (necessarily <= maxDictSize), or 0 if error. */ -LZ4LIB_API int LZ4_saveDict (LZ4_stream_t* streamPtr, char* safeBuffer, int dictSize); +LZ4LIB_API int LZ4_saveDict (LZ4_stream_t* streamPtr, char* safeBuffer, int maxDictSize); /*-********************************************** @@ -299,7 +302,7 @@ LZ4LIB_API int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_str /*! LZ4_setStreamDecode() : * An LZ4_streamDecode_t structure can be allocated once and re-used multiple times. * Use this function to start decompression of a new stream of blocks. - * A dictionary can optionnally be set. Use NULL or size 0 for a simple reset order. + * A dictionary can optionnally be set. Use NULL or size 0 for a reset order. * @return : 1 if OK, 0 if error */ LZ4LIB_API int LZ4_setStreamDecode (LZ4_streamDecode_t* LZ4_streamDecode, const char* dictionary, int dictSize); diff --git a/lib/lz4frame.h b/lib/lz4frame.h index 15484d7..9efaca0 100644 --- a/lib/lz4frame.h +++ b/lib/lz4frame.h @@ -250,10 +250,13 @@ LZ4FLIB_API size_t LZ4F_compressBegin(LZ4F_cctx* cctx, const LZ4F_preferences_t* prefsPtr); /*! LZ4F_compressBound() : - * Provides minimum dstCapacity for a given srcSize to guarantee operation success in worst case scenarios. - * Estimation includes frame footer, which would be generated by LZ4F_compressEnd(). - * Estimation doesn't include frame header, already generated by LZ4F_compressBegin(). + * Provides minimum dstCapacity required to guarantee compression success + * given a srcSize and preferences, covering worst case scenario. * prefsPtr is optional : when NULL is provided, preferences will be set to cover worst case scenario. + * Estimation is valid for either LZ4F_compressUpdate(), LZ4F_flush() or LZ4F_compressEnd(), + * Estimation includes the possibility that internal buffer might already be filled by up to (blockSize-1) bytes. + * It also includes frame footer (ending + checksum), which would have to be generated by LZ4F_compressEnd(). + * Estimation doesn't include frame header, as it was already generated by LZ4F_compressBegin(). * Result is always the same for a srcSize and prefsPtr, so it can be trusted to size reusable buffers. * When srcSize==0, LZ4F_compressBound() provides an upper bound for LZ4F_flush() and LZ4F_compressEnd() operations. */ diff --git a/lib/lz4hc.c b/lib/lz4hc.c index cface81..2a6e080 100644 --- a/lib/lz4hc.c +++ b/lib/lz4hc.c @@ -67,6 +67,7 @@ /*=== Constants ===*/ #define OPTIMAL_ML (int)((ML_MASK-1)+MINMATCH) +#define LZ4_OPT_NUM (1<<12) /*=== Macros ===*/ @@ -123,17 +124,20 @@ LZ4_FORCE_INLINE int LZ4HC_countBack(const BYTE* const ip, const BYTE* const match, const BYTE* const iMin, const BYTE* const mMin) { - int back=0; - while ( (ip+back > iMin) - && (match+back > mMin) - && (ip[back-1] == match[back-1])) + int back = 0; + int const min = (int)MAX(iMin - ip, mMin - match); + assert(ip >= iMin); assert((size_t)(ip-iMin) < (1U<<31)); + assert(match >= mMin); assert((size_t)(match - mMin) < (1U<<31)); + while ( (back > min) + && (ip[back-1] == match[back-1]) ) back--; return back; } /* LZ4HC_countPattern() : * pattern32 must be a sample of repetitive pattern of length 1, 2 or 4 (but not 3!) */ -static unsigned LZ4HC_countPattern(const BYTE* ip, const BYTE* const iEnd, U32 const pattern32) +static unsigned +LZ4HC_countPattern(const BYTE* ip, const BYTE* const iEnd, U32 const pattern32) { const BYTE* const iStart = ip; reg_t const pattern = (sizeof(pattern)==8) ? (reg_t)pattern32 + (((reg_t)pattern32) << 32) : pattern32; @@ -165,7 +169,8 @@ static unsigned LZ4HC_countPattern(const BYTE* ip, const BYTE* const iEnd, U32 c /* LZ4HC_reverseCountPattern() : * pattern must be a sample of repetitive pattern of length 1, 2 or 4 (but not 3!) * read using natural platform endianess */ -static unsigned LZ4HC_reverseCountPattern(const BYTE* ip, const BYTE* const iLow, U32 pattern) +static unsigned +LZ4HC_reverseCountPattern(const BYTE* ip, const BYTE* const iLow, U32 pattern) { const BYTE* const iStart = ip; @@ -183,7 +188,8 @@ static unsigned LZ4HC_reverseCountPattern(const BYTE* ip, const BYTE* const iLow typedef enum { rep_untested, rep_not, rep_confirmed } repeat_state_e; -LZ4_FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch ( +LZ4_FORCE_INLINE int +LZ4HC_InsertAndGetWiderMatch ( LZ4HC_CCtx_internal* hc4, const BYTE* const ip, const BYTE* const iLowLimit, @@ -220,20 +226,11 @@ LZ4_FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch ( nbAttempts--; if (matchIndex >= dictLimit) { const BYTE* const matchPtr = base + matchIndex; - if (*(iLowLimit + longest) == *(matchPtr - delta + longest)) { + assert(longest >= 1); + if (LZ4_read16(iLowLimit + longest - 1) == LZ4_read16(matchPtr - delta + longest - 1)) { if (LZ4_read32(matchPtr) == pattern) { int mlt = MINMATCH + LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, iHighLimit); - #if 0 - /* more generic but unfortunately slower on clang */ - int const back = LZ4HC_countBack(ip, matchPtr, iLowLimit, lowPrefixPtr); - #else - int back = 0; - while ( (ip+back > iLowLimit) - && (matchPtr+back > lowPrefixPtr) - && (ip[back-1] == matchPtr[back-1])) { - back--; - } - #endif + int const back = delta ? LZ4HC_countBack(ip, matchPtr, iLowLimit, lowPrefixPtr) : 0; mlt -= back; if (mlt > longest) { @@ -252,10 +249,7 @@ LZ4_FORCE_INLINE int LZ4HC_InsertAndGetWiderMatch ( mlt = LZ4_count(ip+MINMATCH, matchPtr+MINMATCH, vLimit) + MINMATCH; if ((ip+mlt == vLimit) && (vLimit < iHighLimit)) mlt += LZ4_count(ip+mlt, base+dictLimit, iHighLimit); - while ( (ip+back > iLowLimit) - && (matchIndex+back > lowLimit) - && (ip[back-1] == matchPtr[back-1])) - back--; + back = delta ? LZ4HC_countBack(ip, matchPtr, iLowLimit, dictBase+lowLimit) : 0; mlt -= back; if (mlt > longest) { longest = mlt; @@ -333,7 +327,7 @@ LZ4_FORCE_INLINE int LZ4HC_encodeSequence ( size_t length; BYTE* const token = (*op)++; -#if defined(LZ4_DEBUG) && (LZ4_DEBUG >= 2) +#if defined(LZ4_DEBUG) && (LZ4_DEBUG >= 6) static const BYTE* start = NULL; static U32 totalCost = 0; U32 const pos = (start==NULL) ? 0 : (U32)(*anchor - start); @@ -343,7 +337,7 @@ LZ4_FORCE_INLINE int LZ4HC_encodeSequence ( U32 const cost = 1 + llAdd + ll + 2 + mlAdd; if (start==NULL) start = *anchor; /* only works for single segment */ //g_debuglog_enable = (pos >= 2228) & (pos <= 2262); - DEBUGLOG(2, "pos:%7u -- literals:%3u, match:%4i, offset:%5u, cost:%3u + %u", + DEBUGLOG(6, "pos:%7u -- literals:%3u, match:%4i, offset:%5u, cost:%3u + %u", pos, (U32)(*ip - *anchor), matchLength, (U32)(*ip-match), cost, totalCost); @@ -390,10 +384,6 @@ LZ4_FORCE_INLINE int LZ4HC_encodeSequence ( return 0; } -/* btopt */ -#include "lz4opt.h" - - static int LZ4HC_compress_hashChain ( LZ4HC_CCtx_internal* const ctx, const char* const source, @@ -432,7 +422,7 @@ static int LZ4HC_compress_hashChain ( if (inputSize < LZ4_minLength) goto _last_literals; /* Input too small, no compression (all literals) */ /* Main Loop */ - while (ip < mflimit) { + while (ip <= mflimit) { ml = LZ4HC_InsertAndFindBestMatch (ctx, ip, matchlimit, &ref, maxNbAttempts, patternAnalysis); if (ml<MINMATCH) { ip++; continue; } @@ -442,7 +432,7 @@ static int LZ4HC_compress_hashChain ( ml0 = ml; _Search2: - if (ip+ml < mflimit) + if (ip+ml <= mflimit) ml2 = LZ4HC_InsertAndGetWiderMatch(ctx, ip + ml - 2, ip + 0, matchlimit, ml, &ref2, &start2, maxNbAttempts, patternAnalysis); @@ -489,7 +479,7 @@ _Search3: } /* Now, we have start2 = ip+new_ml, with new_ml = min(ml, OPTIMAL_ML=18) */ - if (start2 + ml2 < mflimit) + if (start2 + ml2 <= mflimit) ml3 = LZ4HC_InsertAndGetWiderMatch(ctx, start2 + ml2 - 3, start2, matchlimit, ml2, &ref3, &start3, maxNbAttempts, patternAnalysis); @@ -612,6 +602,12 @@ _dest_overflow: return 0; } +static int LZ4HC_compress_optimal( LZ4HC_CCtx_internal* ctx, + const char* const source, char* dst, + int* srcSizePtr, int dstCapacity, + int const nbSearches, size_t sufficient_len, + limitedOutput_directive limit, int const fullUpdate); + static int LZ4HC_compress_generic ( LZ4HC_CCtx_internal* const ctx, @@ -891,3 +887,323 @@ char* LZ4_slideInputBufferHC(void* LZ4HC_Data) int const dictSize = LZ4_saveDictHC((LZ4_streamHC_t*)LZ4HC_Data, (char*)(hc4->inputBuffer), 64 KB); return (char*)(hc4->inputBuffer + dictSize); } + + +/* ================================================ + * LZ4 Optimal parser (levels 10-12) + * ===============================================*/ +typedef struct { + int price; + int off; + int mlen; + int litlen; +} LZ4HC_optimal_t; + +/* price in bytes */ +LZ4_FORCE_INLINE int LZ4HC_literalsPrice(int const litlen) +{ + int price = litlen; + if (litlen >= (int)RUN_MASK) + price += 1 + (litlen-RUN_MASK)/255; + return price; +} + + +/* requires mlen >= MINMATCH */ +LZ4_FORCE_INLINE int LZ4HC_sequencePrice(int litlen, int mlen) +{ + int price = 1 + 2 ; /* token + 16-bit offset */ + + price += LZ4HC_literalsPrice(litlen); + + if (mlen >= (int)(ML_MASK+MINMATCH)) + price += 1 + (mlen-(ML_MASK+MINMATCH))/255; + + return price; +} + + +typedef struct { + int off; + int len; +} LZ4HC_match_t; + +LZ4_FORCE_INLINE LZ4HC_match_t +LZ4HC_FindLongerMatch(LZ4HC_CCtx_internal* const ctx, + const BYTE* ip, const BYTE* const iHighLimit, + int minLen, int nbSearches) +{ + LZ4HC_match_t match = { 0 , 0 }; + const BYTE* matchPtr = NULL; + /* note : LZ4HC_InsertAndGetWiderMatch() is able to modify the starting position of a match (*startpos), + * but this won't be the case here, as we define iLowLimit==ip, + * so LZ4HC_InsertAndGetWiderMatch() won't be allowed to search past ip */ + int const matchLength = LZ4HC_InsertAndGetWiderMatch(ctx, + ip, ip, iHighLimit, minLen, &matchPtr, &ip, + nbSearches, 1 /* patternAnalysis */); + if (matchLength <= minLen) return match; + match.len = matchLength; + match.off = (int)(ip-matchPtr); + return match; +} + + +static int LZ4HC_compress_optimal ( + LZ4HC_CCtx_internal* ctx, + const char* const source, + char* dst, + int* srcSizePtr, + int dstCapacity, + int const nbSearches, + size_t sufficient_len, + limitedOutput_directive limit, + int const fullUpdate + ) +{ +#define TRAILING_LITERALS 3 + LZ4HC_optimal_t opt[LZ4_OPT_NUM + TRAILING_LITERALS]; /* ~64 KB, which is a bit large for stack... */ + + const BYTE* ip = (const BYTE*) source; + const BYTE* anchor = ip; + const BYTE* const iend = ip + *srcSizePtr; + const BYTE* const mflimit = iend - MFLIMIT; + const BYTE* const matchlimit = iend - LASTLITERALS; + BYTE* op = (BYTE*) dst; + BYTE* opSaved = (BYTE*) dst; + BYTE* oend = op + dstCapacity; + + /* init */ + DEBUGLOG(5, "LZ4HC_compress_optimal"); + *srcSizePtr = 0; + if (limit == limitedDestSize) oend -= LASTLITERALS; /* Hack for support LZ4 format restriction */ + if (sufficient_len >= LZ4_OPT_NUM) sufficient_len = LZ4_OPT_NUM-1; + + /* Main Loop */ + assert(ip - anchor < LZ4_MAX_INPUT_SIZE); + while (ip <= mflimit) { + int const llen = (int)(ip - anchor); + int best_mlen, best_off; + int cur, last_match_pos = 0; + + LZ4HC_match_t const firstMatch = LZ4HC_FindLongerMatch(ctx, ip, matchlimit, MINMATCH-1, nbSearches); + if (firstMatch.len==0) { ip++; continue; } + + if ((size_t)firstMatch.len > sufficient_len) { + /* good enough solution : immediate encoding */ + int const firstML = firstMatch.len; + const BYTE* const matchPos = ip - firstMatch.off; + opSaved = op; + if ( LZ4HC_encodeSequence(&ip, &op, &anchor, firstML, matchPos, limit, oend) ) /* updates ip, op and anchor */ + goto _dest_overflow; + continue; + } + + /* set prices for first positions (literals) */ + { int rPos; + for (rPos = 0 ; rPos < MINMATCH ; rPos++) { + int const cost = LZ4HC_literalsPrice(llen + rPos); + opt[rPos].mlen = 1; + opt[rPos].off = 0; + opt[rPos].litlen = llen + rPos; + opt[rPos].price = cost; + DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i) -- initial setup", + rPos, cost, opt[rPos].litlen); + } } + /* set prices using initial match */ + { int mlen = MINMATCH; + int const matchML = firstMatch.len; /* necessarily < sufficient_len < LZ4_OPT_NUM */ + int const offset = firstMatch.off; + assert(matchML < LZ4_OPT_NUM); + for ( ; mlen <= matchML ; mlen++) { + int const cost = LZ4HC_sequencePrice(llen, mlen); + opt[mlen].mlen = mlen; + opt[mlen].off = offset; + opt[mlen].litlen = llen; + opt[mlen].price = cost; + DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i) -- initial setup", + mlen, cost, mlen); + } } + last_match_pos = firstMatch.len; + { int addLit; + for (addLit = 1; addLit <= TRAILING_LITERALS; addLit ++) { + opt[last_match_pos+addLit].mlen = 1; /* literal */ + opt[last_match_pos+addLit].off = 0; + opt[last_match_pos+addLit].litlen = addLit; + opt[last_match_pos+addLit].price = opt[last_match_pos].price + LZ4HC_literalsPrice(addLit); + DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i) -- initial setup", + last_match_pos+addLit, opt[last_match_pos+addLit].price, addLit); + } } + + /* check further positions */ + for (cur = 1; cur < last_match_pos; cur++) { + const BYTE* const curPtr = ip + cur; + LZ4HC_match_t newMatch; + + if (curPtr > mflimit) break; + DEBUGLOG(7, "rPos:%u[%u] vs [%u]%u", + cur, opt[cur].price, opt[cur+1].price, cur+1); + if (fullUpdate) { + /* not useful to search here if next position has same (or lower) cost */ + if ( (opt[cur+1].price <= opt[cur].price) + /* in some cases, next position has same cost, but cost rises sharply after, so a small match would still be beneficial */ + && (opt[cur+MINMATCH].price < opt[cur].price + 3/*min seq price*/) ) + continue; + } else { + /* not useful to search here if next position has same (or lower) cost */ + if (opt[cur+1].price <= opt[cur].price) continue; + } + + DEBUGLOG(7, "search at rPos:%u", cur); + if (fullUpdate) + newMatch = LZ4HC_FindLongerMatch(ctx, curPtr, matchlimit, MINMATCH-1, nbSearches); + else + /* only test matches of minimum length; slightly faster, but misses a few bytes */ + newMatch = LZ4HC_FindLongerMatch(ctx, curPtr, matchlimit, last_match_pos - cur, nbSearches); + if (!newMatch.len) continue; + + if ( ((size_t)newMatch.len > sufficient_len) + || (newMatch.len + cur >= LZ4_OPT_NUM) ) { + /* immediate encoding */ + best_mlen = newMatch.len; + best_off = newMatch.off; + last_match_pos = cur + 1; + goto encode; + } + + /* before match : set price with literals at beginning */ + { int const baseLitlen = opt[cur].litlen; + int litlen; + for (litlen = 1; litlen < MINMATCH; litlen++) { + int const price = opt[cur].price - LZ4HC_literalsPrice(baseLitlen) + LZ4HC_literalsPrice(baseLitlen+litlen); + int const pos = cur + litlen; + if (price < opt[pos].price) { + opt[pos].mlen = 1; /* literal */ + opt[pos].off = 0; + opt[pos].litlen = baseLitlen+litlen; + opt[pos].price = price; + DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i)", + pos, price, opt[pos].litlen); + } } } + + /* set prices using match at position = cur */ + { int const matchML = newMatch.len; + int ml = MINMATCH; + + assert(cur + newMatch.len < LZ4_OPT_NUM); + for ( ; ml <= matchML ; ml++) { + int const pos = cur + ml; + int const offset = newMatch.off; + int price; + int ll; + DEBUGLOG(7, "testing price rPos %i (last_match_pos=%i)", + pos, last_match_pos); + if (opt[cur].mlen == 1) { + ll = opt[cur].litlen; + price = ((cur > ll) ? opt[cur - ll].price : 0) + + LZ4HC_sequencePrice(ll, ml); + } else { + ll = 0; + price = opt[cur].price + LZ4HC_sequencePrice(0, ml); + } + + if (pos > last_match_pos+TRAILING_LITERALS || price <= opt[pos].price) { + DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i)", + pos, price, ml); + assert(pos < LZ4_OPT_NUM); + if ( (ml == matchML) /* last pos of last match */ + && (last_match_pos < pos) ) + last_match_pos = pos; + opt[pos].mlen = ml; + opt[pos].off = offset; + opt[pos].litlen = ll; + opt[pos].price = price; + } } } + /* complete following positions with literals */ + { int addLit; + for (addLit = 1; addLit <= TRAILING_LITERALS; addLit ++) { + opt[last_match_pos+addLit].mlen = 1; /* literal */ + opt[last_match_pos+addLit].off = 0; + opt[last_match_pos+addLit].litlen = addLit; + opt[last_match_pos+addLit].price = opt[last_match_pos].price + LZ4HC_literalsPrice(addLit); + DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i)", last_match_pos+addLit, opt[last_match_pos+addLit].price, addLit); + } } + } /* for (cur = 1; cur <= last_match_pos; cur++) */ + + best_mlen = opt[last_match_pos].mlen; + best_off = opt[last_match_pos].off; + cur = last_match_pos - best_mlen; + + encode: /* cur, last_match_pos, best_mlen, best_off must be set */ + assert(cur < LZ4_OPT_NUM); + assert(last_match_pos >= 1); /* == 1 when only one candidate */ + DEBUGLOG(6, "reverse traversal, looking for shortest path") + DEBUGLOG(6, "last_match_pos = %i", last_match_pos); + { int candidate_pos = cur; + int selected_matchLength = best_mlen; + int selected_offset = best_off; + while (1) { /* from end to beginning */ + int const next_matchLength = opt[candidate_pos].mlen; /* can be 1, means literal */ + int const next_offset = opt[candidate_pos].off; + DEBUGLOG(6, "pos %i: sequence length %i", candidate_pos, selected_matchLength); + opt[candidate_pos].mlen = selected_matchLength; + opt[candidate_pos].off = selected_offset; + selected_matchLength = next_matchLength; + selected_offset = next_offset; + if (next_matchLength > candidate_pos) break; /* last match elected, first match to encode */ + assert(next_matchLength > 0); /* can be 1, means literal */ + candidate_pos -= next_matchLength; + } } + + /* encode all recorded sequences in order */ + { int rPos = 0; /* relative position (to ip) */ + while (rPos < last_match_pos) { + int const ml = opt[rPos].mlen; + int const offset = opt[rPos].off; + if (ml == 1) { ip++; rPos++; continue; } /* literal; note: can end up with several literals, in which case, skip them */ + rPos += ml; + assert(ml >= MINMATCH); + assert((offset >= 1) && (offset <= MAX_DISTANCE)); + opSaved = op; + if ( LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ip - offset, limit, oend) ) /* updates ip, op and anchor */ + goto _dest_overflow; + } } + } /* while (ip <= mflimit) */ + + _last_literals: + /* Encode Last Literals */ + { size_t lastRunSize = (size_t)(iend - anchor); /* literals */ + size_t litLength = (lastRunSize + 255 - RUN_MASK) / 255; + size_t const totalSize = 1 + litLength + lastRunSize; + if (limit == limitedDestSize) oend += LASTLITERALS; /* restore correct value */ + if (limit && (op + totalSize > oend)) { + if (limit == limitedOutput) return 0; /* Check output limit */ + /* adapt lastRunSize to fill 'dst' */ + lastRunSize = (size_t)(oend - op) - 1; + litLength = (lastRunSize + 255 - RUN_MASK) / 255; + lastRunSize -= litLength; + } + ip = anchor + lastRunSize; + + if (lastRunSize >= RUN_MASK) { + size_t accumulator = lastRunSize - RUN_MASK; + *op++ = (RUN_MASK << ML_BITS); + for(; accumulator >= 255 ; accumulator -= 255) *op++ = 255; + *op++ = (BYTE) accumulator; + } else { + *op++ = (BYTE)(lastRunSize << ML_BITS); + } + memcpy(op, anchor, lastRunSize); + op += lastRunSize; + } + + /* End */ + *srcSizePtr = (int) (((const char*)ip) - source); + return (int) ((char*)op-dst); + + _dest_overflow: + if (limit == limitedDestSize) { + op = opSaved; /* restore correct out pointer */ + goto _last_literals; + } + return 0; + } diff --git a/lib/lz4opt.h b/lib/lz4opt.h deleted file mode 100644 index 5a8438c..0000000 --- a/lib/lz4opt.h +++ /dev/null @@ -1,356 +0,0 @@ -/* - lz4opt.h - Optimal Mode of LZ4 - Copyright (C) 2015-2017, Przemyslaw Skibinski <inikep@gmail.com> - Note : this file is intended to be included within lz4hc.c - - 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 : - - LZ4 source repository : https://github.com/lz4/lz4 - - LZ4 public forum : https://groups.google.com/forum/#!forum/lz4c -*/ - -#define LZ4_OPT_NUM (1<<12) - -typedef struct { - int price; - int off; - int mlen; - int litlen; -} LZ4HC_optimal_t; - - -/* price in bytes */ -LZ4_FORCE_INLINE int LZ4HC_literalsPrice(int const litlen) -{ - int price = litlen; - if (litlen >= (int)RUN_MASK) - price += 1 + (litlen-RUN_MASK)/255; - return price; -} - - -/* requires mlen >= MINMATCH */ -LZ4_FORCE_INLINE int LZ4HC_sequencePrice(int litlen, int mlen) -{ - int price = 1 + 2 ; /* token + 16-bit offset */ - - price += LZ4HC_literalsPrice(litlen); - - if (mlen >= (int)(ML_MASK+MINMATCH)) - price += 1 + (mlen-(ML_MASK+MINMATCH))/255; - - return price; -} - - -/*-************************************* -* Match finder -***************************************/ -typedef struct { - int off; - int len; -} LZ4HC_match_t; - -LZ4_FORCE_INLINE -LZ4HC_match_t LZ4HC_FindLongerMatch(LZ4HC_CCtx_internal* const ctx, - const BYTE* ip, const BYTE* const iHighLimit, - int minLen, int nbSearches) -{ - LZ4HC_match_t match = { 0 , 0 }; - const BYTE* matchPtr = NULL; - /* note : LZ4HC_InsertAndGetWiderMatch() is able to modify the starting position of a match (*startpos), - * but this won't be the case here, as we define iLowLimit==ip, - * so LZ4HC_InsertAndGetWiderMatch() won't be allowed to search past ip */ - int const matchLength = LZ4HC_InsertAndGetWiderMatch(ctx, - ip, ip, iHighLimit, minLen, &matchPtr, &ip, - nbSearches, 1 /* patternAnalysis */); - if (matchLength <= minLen) return match; - match.len = matchLength; - match.off = (int)(ip-matchPtr); - return match; -} - - -static int LZ4HC_compress_optimal ( - LZ4HC_CCtx_internal* ctx, - const char* const source, - char* dst, - int* srcSizePtr, - int dstCapacity, - int const nbSearches, - size_t sufficient_len, - limitedOutput_directive limit, - int const fullUpdate - ) -{ -#define TRAILING_LITERALS 3 - LZ4HC_optimal_t opt[LZ4_OPT_NUM + TRAILING_LITERALS]; /* this uses a bit too much stack memory to my taste ... */ - - const BYTE* ip = (const BYTE*) source; - const BYTE* anchor = ip; - const BYTE* const iend = ip + *srcSizePtr; - const BYTE* const mflimit = iend - MFLIMIT; - const BYTE* const matchlimit = iend - LASTLITERALS; - BYTE* op = (BYTE*) dst; - BYTE* opSaved = (BYTE*) dst; - BYTE* oend = op + dstCapacity; - - /* init */ - DEBUGLOG(5, "LZ4HC_compress_optimal"); - *srcSizePtr = 0; - if (limit == limitedDestSize) oend -= LASTLITERALS; /* Hack for support LZ4 format restriction */ - if (sufficient_len >= LZ4_OPT_NUM) sufficient_len = LZ4_OPT_NUM-1; - - /* Main Loop */ - assert(ip - anchor < LZ4_MAX_INPUT_SIZE); - while (ip < mflimit) { - int const llen = (int)(ip - anchor); - int best_mlen, best_off; - int cur, last_match_pos = 0; - - LZ4HC_match_t const firstMatch = LZ4HC_FindLongerMatch(ctx, ip, matchlimit, MINMATCH-1, nbSearches); - if (firstMatch.len==0) { ip++; continue; } - - if ((size_t)firstMatch.len > sufficient_len) { - /* good enough solution : immediate encoding */ - int const firstML = firstMatch.len; - const BYTE* const matchPos = ip - firstMatch.off; - opSaved = op; - if ( LZ4HC_encodeSequence(&ip, &op, &anchor, firstML, matchPos, limit, oend) ) /* updates ip, op and anchor */ - goto _dest_overflow; - continue; - } - - /* set prices for first positions (literals) */ - { int rPos; - for (rPos = 0 ; rPos < MINMATCH ; rPos++) { - int const cost = LZ4HC_literalsPrice(llen + rPos); - opt[rPos].mlen = 1; - opt[rPos].off = 0; - opt[rPos].litlen = llen + rPos; - opt[rPos].price = cost; - DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i) -- initial setup", - rPos, cost, opt[rPos].litlen); - } } - /* set prices using initial match */ - { int mlen = MINMATCH; - int const matchML = firstMatch.len; /* necessarily < sufficient_len < LZ4_OPT_NUM */ - int const offset = firstMatch.off; - assert(matchML < LZ4_OPT_NUM); - for ( ; mlen <= matchML ; mlen++) { - int const cost = LZ4HC_sequencePrice(llen, mlen); - opt[mlen].mlen = mlen; - opt[mlen].off = offset; - opt[mlen].litlen = llen; - opt[mlen].price = cost; - DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i) -- initial setup", - mlen, cost, mlen); - } } - last_match_pos = firstMatch.len; - { int addLit; - for (addLit = 1; addLit <= TRAILING_LITERALS; addLit ++) { - opt[last_match_pos+addLit].mlen = 1; /* literal */ - opt[last_match_pos+addLit].off = 0; - opt[last_match_pos+addLit].litlen = addLit; - opt[last_match_pos+addLit].price = opt[last_match_pos].price + LZ4HC_literalsPrice(addLit); - DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i) -- initial setup", - last_match_pos+addLit, opt[last_match_pos+addLit].price, addLit); - } } - - /* check further positions */ - for (cur = 1; cur < last_match_pos; cur++) { - const BYTE* const curPtr = ip + cur; - LZ4HC_match_t newMatch; - - if (curPtr >= mflimit) break; - DEBUGLOG(7, "rPos:%u[%u] vs [%u]%u", - cur, opt[cur].price, opt[cur+1].price, cur+1); - if (fullUpdate) { - /* not useful to search here if next position has same (or lower) cost */ - if ( (opt[cur+1].price <= opt[cur].price) - /* in some cases, next position has same cost, but cost rises sharply after, so a small match would still be beneficial */ - && (opt[cur+MINMATCH].price < opt[cur].price + 3/*min seq price*/) ) - continue; - } else { - /* not useful to search here if next position has same (or lower) cost */ - if (opt[cur+1].price <= opt[cur].price) continue; - } - - DEBUGLOG(7, "search at rPos:%u", cur); - if (fullUpdate) - newMatch = LZ4HC_FindLongerMatch(ctx, curPtr, matchlimit, MINMATCH-1, nbSearches); - else - /* only test matches of minimum length; slightly faster, but misses a few bytes */ - newMatch = LZ4HC_FindLongerMatch(ctx, curPtr, matchlimit, last_match_pos - cur, nbSearches); - if (!newMatch.len) continue; - - if ( ((size_t)newMatch.len > sufficient_len) - || (newMatch.len + cur >= LZ4_OPT_NUM) ) { - /* immediate encoding */ - best_mlen = newMatch.len; - best_off = newMatch.off; - last_match_pos = cur + 1; - goto encode; - } - - /* before match : set price with literals at beginning */ - { int const baseLitlen = opt[cur].litlen; - int litlen; - for (litlen = 1; litlen < MINMATCH; litlen++) { - int const price = opt[cur].price - LZ4HC_literalsPrice(baseLitlen) + LZ4HC_literalsPrice(baseLitlen+litlen); - int const pos = cur + litlen; - if (price < opt[pos].price) { - opt[pos].mlen = 1; /* literal */ - opt[pos].off = 0; - opt[pos].litlen = baseLitlen+litlen; - opt[pos].price = price; - DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i)", - pos, price, opt[pos].litlen); - } } } - - /* set prices using match at position = cur */ - { int const matchML = newMatch.len; - int ml = MINMATCH; - - assert(cur + newMatch.len < LZ4_OPT_NUM); - for ( ; ml <= matchML ; ml++) { - int const pos = cur + ml; - int const offset = newMatch.off; - int price; - int ll; - DEBUGLOG(7, "testing price rPos %i (last_match_pos=%i)", - pos, last_match_pos); - if (opt[cur].mlen == 1) { - ll = opt[cur].litlen; - price = ((cur > ll) ? opt[cur - ll].price : 0) - + LZ4HC_sequencePrice(ll, ml); - } else { - ll = 0; - price = opt[cur].price + LZ4HC_sequencePrice(0, ml); - } - - if (pos > last_match_pos+TRAILING_LITERALS || price <= opt[pos].price) { - DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i)", - pos, price, ml); - assert(pos < LZ4_OPT_NUM); - if ( (ml == matchML) /* last pos of last match */ - && (last_match_pos < pos) ) - last_match_pos = pos; - opt[pos].mlen = ml; - opt[pos].off = offset; - opt[pos].litlen = ll; - opt[pos].price = price; - } } } - /* complete following positions with literals */ - { int addLit; - for (addLit = 1; addLit <= TRAILING_LITERALS; addLit ++) { - opt[last_match_pos+addLit].mlen = 1; /* literal */ - opt[last_match_pos+addLit].off = 0; - opt[last_match_pos+addLit].litlen = addLit; - opt[last_match_pos+addLit].price = opt[last_match_pos].price + LZ4HC_literalsPrice(addLit); - DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i)", last_match_pos+addLit, opt[last_match_pos+addLit].price, addLit); - } } - } /* for (cur = 1; cur <= last_match_pos; cur++) */ - - best_mlen = opt[last_match_pos].mlen; - best_off = opt[last_match_pos].off; - cur = last_match_pos - best_mlen; - -encode: /* cur, last_match_pos, best_mlen, best_off must be set */ - assert(cur < LZ4_OPT_NUM); - assert(last_match_pos >= 1); /* == 1 when only one candidate */ - DEBUGLOG(6, "reverse traversal, looking for shortest path") - DEBUGLOG(6, "last_match_pos = %i", last_match_pos); - { int candidate_pos = cur; - int selected_matchLength = best_mlen; - int selected_offset = best_off; - while (1) { /* from end to beginning */ - int const next_matchLength = opt[candidate_pos].mlen; /* can be 1, means literal */ - int const next_offset = opt[candidate_pos].off; - DEBUGLOG(6, "pos %i: sequence length %i", candidate_pos, selected_matchLength); - opt[candidate_pos].mlen = selected_matchLength; - opt[candidate_pos].off = selected_offset; - selected_matchLength = next_matchLength; - selected_offset = next_offset; - if (next_matchLength > candidate_pos) break; /* last match elected, first match to encode */ - assert(next_matchLength > 0); /* can be 1, means literal */ - candidate_pos -= next_matchLength; - } } - - /* encode all recorded sequences in order */ - { int rPos = 0; /* relative position (to ip) */ - while (rPos < last_match_pos) { - int const ml = opt[rPos].mlen; - int const offset = opt[rPos].off; - if (ml == 1) { ip++; rPos++; continue; } /* literal; note: can end up with several literals, in which case, skip them */ - rPos += ml; - assert(ml >= MINMATCH); - assert((offset >= 1) && (offset <= MAX_DISTANCE)); - opSaved = op; - if ( LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ip - offset, limit, oend) ) /* updates ip, op and anchor */ - goto _dest_overflow; - } } - } /* while (ip < mflimit) */ - -_last_literals: - /* Encode Last Literals */ - { size_t lastRunSize = (size_t)(iend - anchor); /* literals */ - size_t litLength = (lastRunSize + 255 - RUN_MASK) / 255; - size_t const totalSize = 1 + litLength + lastRunSize; - if (limit == limitedDestSize) oend += LASTLITERALS; /* restore correct value */ - if (limit && (op + totalSize > oend)) { - if (limit == limitedOutput) return 0; /* Check output limit */ - /* adapt lastRunSize to fill 'dst' */ - lastRunSize = (size_t)(oend - op) - 1; - litLength = (lastRunSize + 255 - RUN_MASK) / 255; - lastRunSize -= litLength; - } - ip = anchor + lastRunSize; - - if (lastRunSize >= RUN_MASK) { - size_t accumulator = lastRunSize - RUN_MASK; - *op++ = (RUN_MASK << ML_BITS); - for(; accumulator >= 255 ; accumulator -= 255) *op++ = 255; - *op++ = (BYTE) accumulator; - } else { - *op++ = (BYTE)(lastRunSize << ML_BITS); - } - memcpy(op, anchor, lastRunSize); - op += lastRunSize; - } - - /* End */ - *srcSizePtr = (int) (((const char*)ip) - source); - return (int) ((char*)op-dst); - -_dest_overflow: - if (limit == limitedDestSize) { - op = opSaved; /* restore correct out pointer */ - goto _last_literals; - } - return 0; -} diff --git a/programs/bench.c b/programs/bench.c index fac2a87..002eac9 100644 --- a/programs/bench.c +++ b/programs/bench.c @@ -41,6 +41,7 @@ #include <string.h> /* memset */ #include <stdio.h> /* fprintf, fopen, ftello */ #include <time.h> /* clock_t, clock, CLOCKS_PER_SEC */ +#include <assert.h> /* assert */ #include "datagen.h" /* RDG_genBuffer */ #include "xxhash.h" @@ -66,6 +67,7 @@ static int LZ4_compress_local(const char* src, char* dst, int srcSize, int dstSi #define NBSECONDS 3 #define TIMELOOP_MICROSEC 1*1000000ULL /* 1 second */ +#define TIMELOOP_NANOSEC 1*1000000000ULL /* 1 second */ #define ACTIVEPERIOD_MICROSEC 70*1000000ULL /* 70 seconds */ #define COOLPERIOD_SEC 10 #define DECOMP_MULT 1 /* test decompression DECOMP_MULT times longer than compression */ @@ -218,7 +220,9 @@ static int BMK_benchMem(const void* srcBuffer, size_t srcSize, { U64 fastestC = (U64)(-1LL), fastestD = (U64)(-1LL); U64 const crcOrig = XXH64(srcBuffer, srcSize, 0); UTIL_time_t coolTime; - U64 const maxTime = (g_nbSeconds * TIMELOOP_MICROSEC) + 100; + U64 const maxTime = (g_nbSeconds * TIMELOOP_NANOSEC) + 100; + U32 nbCompressionLoops = (U32)((5 MB) / (srcSize+1)) + 1; /* conservative initial compression speed estimate */ + U32 nbDecodeLoops = (U32)((200 MB) / (srcSize+1)) + 1; /* conservative initial decode speed estimate */ U64 totalCTime=0, totalDTime=0; U32 cCompleted=0, dCompleted=0; # define NB_MARKS 4 @@ -230,9 +234,6 @@ static int BMK_benchMem(const void* srcBuffer, size_t srcSize, coolTime = UTIL_getTime(); DISPLAYLEVEL(2, "\r%79s\r", ""); while (!cCompleted || !dCompleted) { - UTIL_time_t clockStart; - U64 clockLoop = g_nbSeconds ? TIMELOOP_MICROSEC : 1; - /* overheat protection */ if (UTIL_clockSpanMicro(coolTime) > ACTIVEPERIOD_MICROSEC) { DISPLAYLEVEL(2, "\rcooling down ... \r"); @@ -246,21 +247,27 @@ static int BMK_benchMem(const void* srcBuffer, size_t srcSize, UTIL_sleepMilli(1); /* give processor time to other processes */ UTIL_waitForNextTick(); - clockStart = UTIL_getTime(); if (!cCompleted) { /* still some time to do compression tests */ - U32 nbLoops = 0; - do { + UTIL_time_t const clockStart = UTIL_getTime(); + U32 nbLoops; + for (nbLoops=0; nbLoops < nbCompressionLoops; nbLoops++) { U32 blockNb; for (blockNb=0; blockNb<nbBlocks; blockNb++) { size_t const rSize = compP.compressionFunction(blockTable[blockNb].srcPtr, blockTable[blockNb].cPtr, (int)blockTable[blockNb].srcSize, (int)blockTable[blockNb].cRoom, cLevel); if (LZ4_isError(rSize)) EXM_THROW(1, "LZ4_compress() failed"); blockTable[blockNb].cSize = rSize; + } } + { U64 const clockSpan = UTIL_clockSpanNano(clockStart); + if (clockSpan > 0) { + if (clockSpan < fastestC * nbCompressionLoops) + fastestC = clockSpan / nbCompressionLoops; + assert(fastestC > 0); + nbCompressionLoops = (U32)(TIMELOOP_NANOSEC / fastestC) + 1; /* aim for ~1sec */ + } else { + assert(nbCompressionLoops < 40000000); /* avoid overflow */ + nbCompressionLoops *= 100; } - nbLoops++; - } while (UTIL_clockSpanMicro(clockStart) < clockLoop); - { U64 const clockSpan = UTIL_clockSpanMicro(clockStart); - if (clockSpan < fastestC*nbLoops) fastestC = clockSpan / nbLoops; totalCTime += clockSpan; cCompleted = totalCTime>maxTime; } } @@ -272,44 +279,48 @@ static int BMK_benchMem(const void* srcBuffer, size_t srcSize, markNb = (markNb+1) % NB_MARKS; DISPLAYLEVEL(2, "%2s-%-17.17s :%10u ->%10u (%5.3f),%6.1f MB/s\r", marks[markNb], displayName, (U32)srcSize, (U32)cSize, ratio, - (double)srcSize / fastestC ); + ((double)srcSize / fastestC) * 1000 ); (void)fastestD; (void)crcOrig; /* unused when decompression disabled */ #if 1 /* Decompression */ if (!dCompleted) memset(resultBuffer, 0xD6, srcSize); /* warm result buffer */ - UTIL_sleepMilli(1); /* give processor time to other processes */ + UTIL_sleepMilli(5); /* give processor time to other processes */ UTIL_waitForNextTick(); - clockStart = UTIL_getTime(); if (!dCompleted) { - U32 nbLoops = 0; - do { + UTIL_time_t const clockStart = UTIL_getTime(); + U32 nbLoops; + for (nbLoops=0; nbLoops < nbDecodeLoops; nbLoops++) { U32 blockNb; for (blockNb=0; blockNb<nbBlocks; blockNb++) { size_t const regenSize = LZ4_decompress_safe(blockTable[blockNb].cPtr, blockTable[blockNb].resPtr, (int)blockTable[blockNb].cSize, (int)blockTable[blockNb].srcSize); if (LZ4_isError(regenSize)) { - DISPLAY("LZ4_decompress_safe() failed on block %u \n", blockNb); - clockLoop = 0; /* force immediate test end */ + DISPLAY("LZ4_decompress_safe() failed on block %u \n", blockNb); break; } - blockTable[blockNb].resSize = regenSize; + } } + { U64 const clockSpan = UTIL_clockSpanNano(clockStart); + if (clockSpan > 0) { + if (clockSpan < fastestD * nbDecodeLoops) + fastestD = clockSpan / nbDecodeLoops; + assert(fastestD > 0); + nbDecodeLoops = (U32)(TIMELOOP_NANOSEC / fastestD) + 1; /* aim for ~1sec */ + } else { + assert(nbDecodeLoops < 40000000); /* avoid overflow */ + nbDecodeLoops *= 100; } - nbLoops++; - } while (UTIL_clockSpanMicro(clockStart) < DECOMP_MULT*clockLoop); - { U64 const clockSpan = UTIL_clockSpanMicro(clockStart); - if (clockSpan < fastestD*nbLoops) fastestD = clockSpan / nbLoops; totalDTime += clockSpan; - dCompleted = totalDTime>(DECOMP_MULT*maxTime); + dCompleted = totalDTime > (DECOMP_MULT*maxTime); } } markNb = (markNb+1) % NB_MARKS; DISPLAYLEVEL(2, "%2s-%-17.17s :%10u ->%10u (%5.3f),%6.1f MB/s ,%6.1f MB/s\r", marks[markNb], displayName, (U32)srcSize, (U32)cSize, ratio, - (double)srcSize / fastestC, - (double)srcSize / fastestD ); + ((double)srcSize / fastestC) * 1000, + ((double)srcSize / fastestD) * 1000); /* CRC Checking */ { U64 const crcCheck = XXH64(resultBuffer, srcSize, 0); @@ -339,8 +350,8 @@ static int BMK_benchMem(const void* srcBuffer, size_t srcSize, } /* for (testNb = 1; testNb <= (g_nbSeconds + !g_nbSeconds); testNb++) */ if (g_displayLevel == 1) { - double cSpeed = (double)srcSize / fastestC; - double dSpeed = (double)srcSize / fastestD; + double const cSpeed = ((double)srcSize / fastestC) * 1000; + double const dSpeed = ((double)srcSize / fastestD) * 1000; if (g_additionalParam) DISPLAY("-%-3i%11i (%5.3f) %6.2f MB/s %6.1f MB/s %s (param=%d)\n", cLevel, (int)cSize, ratio, cSpeed, dSpeed, displayName, g_additionalParam); else diff --git a/programs/util.h b/programs/util.h index a3576d7..ff25106 100644 --- a/programs/util.h +++ b/programs/util.h @@ -180,7 +180,7 @@ extern "C" { mach_timebase_info(&rate); init = 1; } - return (((clockEnd - clockStart) * (U64)rate.numer) / ((U64)rate.denom))/1000ULL; + return (((clockEnd - clockStart) * (U64)rate.numer) / ((U64)rate.denom)) / 1000ULL; } UTIL_STATIC U64 UTIL_getSpanTimeNano(UTIL_time_t clockStart, UTIL_time_t clockEnd) { @@ -249,6 +249,12 @@ UTIL_STATIC U64 UTIL_clockSpanMicro(UTIL_time_t clockStart) return UTIL_getSpanTimeMicro(clockStart, clockEnd); } +/* returns time span in nanoseconds */ +UTIL_STATIC U64 UTIL_clockSpanNano(UTIL_time_t clockStart) +{ + UTIL_time_t const clockEnd = UTIL_getTime(); + return UTIL_getSpanTimeNano(clockStart, clockEnd); +} UTIL_STATIC void UTIL_waitForNextTick(void) { diff --git a/tests/Makefile b/tests/Makefile index ddc0d2e..5954370 100644 --- a/tests/Makefile +++ b/tests/Makefile @@ -1,8 +1,6 @@ # ########################################################################## # LZ4 programs - Makefile -# Copyright (C) Yann Collet 2011-2017 -# -# This Makefile is validated for Linux, macOS, *BSD, Hurd, Solaris, MSYS2 targets +# Copyright (C) Yann Collet 2011-present # # GPL v2 License # @@ -53,7 +51,7 @@ else EXT = VOID = /dev/null endif -LZ4 := $(PRGDIR)/lz4$(EXT) +LZ4 := $(PRGDIR)/lz4$(EXT) # Default test parameters @@ -184,12 +182,6 @@ test-lz4-contentSize: lz4 datagen $(LZ4) -v tmplc1 | $(LZ4) -t $(LZ4) -v --content-size tmplc1 | $(LZ4) -d > tmplc2 $(DIFF) -s tmplc1 tmplc2 - # test large size [2-4] GB - @./datagen -g3G -P100 | $(LZ4) -vv | $(LZ4) --decompress --force --sparse - tmplc1 - @ls -ls tmplc1 - @./datagen -g3G -P100 | $(LZ4) --quiet --content-size | $(LZ4) --verbose --decompress --force --sparse - tmplc2 - @ls -ls tmplc2 - $(DIFF) -s tmplc1 tmplc2 @$(RM) tmplc* test-lz4-frame-concatenation: lz4 datagen @@ -293,6 +285,13 @@ test-lz4-hugefile: lz4 datagen @echo "\n ---- test huge files compression/decompression ----" ./datagen -g6GB | $(LZ4) -vB5D | $(LZ4) -qt ./datagen -g6GB | $(LZ4) -v5BD | $(LZ4) -qt + # test large file size [2-4] GB + @./datagen -g3G -P100 | $(LZ4) -vv | $(LZ4) --decompress --force --sparse - tmphf1 + @ls -ls tmphf1 + @./datagen -g3G -P100 | $(LZ4) --quiet --content-size | $(LZ4) --verbose --decompress --force --sparse - tmphf2 + @ls -ls tmphf2 + $(DIFF) -s tmphf1 tmphf2 + @$(RM) tmphf* test-lz4-testmode: lz4 datagen @echo "\n ---- bench mode ----" @@ -326,9 +325,13 @@ test-lz4-opt-parser: lz4 datagen ./datagen -g16M -P90 | $(LZ4) -11B5 | $(LZ4) -t ./datagen -g32M -P10 | $(LZ4) -11B5D | $(LZ4) -t -test-lz4: lz4 datagen test-lz4-basic test-lz4-opt-parser test-lz4-multiple \ - test-lz4-sparse test-lz4-frame-concatenation test-lz4-testmode \ - test-lz4-contentSize test-lz4-hugefile test-lz4-dict +test-lz4-essentials : lz4 datagen test-lz4-basic test-lz4-multiple \ + test-lz4-frame-concatenation test-lz4-testmode \ + test-lz4-contentSize + @$(RM) tmp* + +test-lz4: lz4 datagen test-lz4-essentials test-lz4-opt-parser \ + test-lz4-sparse test-lz4-hugefile test-lz4-dict @$(RM) tmp* test-lz4c: lz4c datagen |