From 4fc6b485500ac85cd6abca04bf0fdd687ade8213 Mon Sep 17 00:00:00 2001
From: Yann Collet
Version
@@ -357,6 +357,40 @@ int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream);
+ It's possible to have input and output sharing the same buffer, + for highly contrained memory environments. + In both cases, it requires input to lay at the end of the buffer, + and buffer must have some margin, hence be larger than final size. + + This technique is more useful for decompression, + since decompressed size is typically larger, + and margin is mostly required to avoid stripe overflow, so it's short. + + For compression though, margin must be able to cope with both + history preservation, requiring input data to remain unmodified up to LZ4_DISTANCE_MAX, + and data expansion, which can happen when input is not compressible. + As a consequence, buffer size requirements are much higher than average compressed size, + hence memory savings are limited. + + There are ways to limit this cost for compression : + - Reduce history size, by modifying LZ4_DISTANCE_MAX. + Lower values will also reduce compression ratio, except when input_size < LZ4_DISTANCE_MAX, + so it's a reasonable trick when inputs are known to be small. + - Require the compressor to deliver a "maximum compressed size". + When this size is < LZ4_COMPRESSBOUND(inputSize), then compression can fail, + in which case, the return code will be 0 (zero). + The caller must be ready for these cases to happen, + and typically design a backup scheme to send data uncompressed. + The combination of both techniques can significantly reduce + the amount of margin required for in-place compression. + +
#define LZ4_DECOMPRESS_INPLACE_BUFFER_SIZE(decompressedSize) ( (decompressedSize) + LZ4_DECOMPRESS_INPLACE_MARGIN) /**< note: presumes that compressedSize < decompressedSize */ +
#define LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCompressedSize) ( (maxCompressedSize) + LZ4_COMPRESS_INPLACE_MARGIN) /**< maxCompressedSize is generally LZ4_COMPRESSBOUND(inputSize), but can be set to any lower value, with the risk that compression can fail (return code 0(zero)) */ +
Do not use these definitions directly. They are only exposed to allow static allocation of `LZ4_stream_t` and `LZ4_streamDecode_t`. diff --git a/lib/lz4.c b/lib/lz4.c index 070dd7e..19070c2 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -412,10 +412,6 @@ static const int LZ4_minLength = (MFLIMIT+1); #define MB *(1 <<20) #define GB *(1U<<30) -#ifndef LZ4_DISTANCE_MAX /* can be user - defined at compile time */ -# define LZ4_DISTANCE_MAX 65535 -#endif - #if (LZ4_DISTANCE_MAX > 65535) /* max supported by LZ4 format */ # error "LZ4_DISTANCE_MAX is too big : must be <= 65535" #endif diff --git a/lib/lz4.h b/lib/lz4.h index 6064967..ae7f52c 100644 --- a/lib/lz4.h +++ b/lib/lz4.h @@ -65,9 +65,9 @@ extern "C" { Blocks are different from Frames (doc/lz4_Frame_format.md). Frames bundle both blocks and metadata in a specified manner. - This are required for compressed data to be self-contained and portable. + Embedding metadata is required for compressed data to be self-contained and portable. Frame format is delivered through a companion API, declared in lz4frame.h. - Note that the `lz4` CLI can only manage frames. + The `lz4` CLI can only manage frames. */ /*^*************************************************************** @@ -462,8 +462,51 @@ LZ4LIB_STATIC_API int LZ4_compress_fast_extState_fastReset (void* state, const c */ LZ4LIB_STATIC_API void LZ4_attach_dictionary(LZ4_stream_t* workingStream, const LZ4_stream_t* dictionaryStream); + +/*! In-place compression and decompression + * + * It's possible to have input and output sharing the same buffer, + * for highly contrained memory environments. + * In both cases, it requires input to lay at the end of the buffer, + * and buffer must have some margin, hence be larger than final size. + * + * This technique is more useful for decompression, + * since decompressed size is typically larger, + * and margin is mostly required to avoid stripe overflow, so it's short. + * + * For compression though, margin must be able to cope with both + * history preservation, requiring input data to remain unmodified up to LZ4_DISTANCE_MAX, + * and data expansion, which can happen when input is not compressible. + * As a consequence, buffer size requirements are much higher than average compressed size, + * hence memory savings are limited. + * + * There are ways to limit this cost for compression : + * - Reduce history size, by modifying LZ4_DISTANCE_MAX. + * Lower values will also reduce compression ratio, except when input_size < LZ4_DISTANCE_MAX, + * so it's a reasonable trick when inputs are known to be small. + * - Require the compressor to deliver a "maximum compressed size". + * When this size is < LZ4_COMPRESSBOUND(inputSize), then compression can fail, + * in which case, the return code will be 0 (zero). + * The caller must be ready for these cases to happen, + * and typically design a backup scheme to send data uncompressed. + * The combination of both techniques can significantly reduce + * the amount of margin required for in-place compression. + */ + +#define LZ4_DECOMPRESS_INPLACE_MARGIN 32 +#define LZ4_DECOMPRESS_INPLACE_BUFFER_SIZE(decompressedSize) ( (decompressedSize) + LZ4_DECOMPRESS_INPLACE_MARGIN) /**< note: presumes that compressedSize < decompressedSize */ + +#ifndef LZ4_DISTANCE_MAX /* history window size; can be user-defined at compile time */ +# define LZ4_DISTANCE_MAX 65535 /* set to maximum value by default */ #endif +#define LZ4_COMPRESS_INPLACE_MARGIN (LZ4_DISTANCE_MAX + 32) +#define LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCompressedSize) ( (maxCompressedSize) + LZ4_COMPRESS_INPLACE_MARGIN) /**< maxCompressedSize is generally LZ4_COMPRESSBOUND(inputSize), but can be set to any lower value, with the risk that compression can fail (return code 0(zero)) */ + + +#endif /* LZ4_STATIC_LINKING_ONLY */ + + /*-************************************************************ * PRIVATE DEFINITIONS @@ -567,6 +610,7 @@ union LZ4_streamDecode_u { } ; /* previously typedef'd to LZ4_streamDecode_t */ + /*-************************************ * Obsolete Functions **************************************/ diff --git a/tests/fuzzer.c b/tests/fuzzer.c index 26e25eb..e04caa5 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -1017,8 +1017,7 @@ static void FUZ_unitTests(int compressionLevel) DISPLAYLEVEL(3, "in-place compression using LZ4_compress_default() :"); { size_t const sampleSize = 65 KB; size_t const maxCSize = LZ4_COMPRESSBOUND(sampleSize); - size_t const margin = 64 KB; - size_t const outSize = maxCSize + margin; + size_t const outSize = LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCSize); size_t const startIndex = outSize - sampleSize; char* const startInput = testCompressed + startIndex; XXH32_hash_t const crcOrig = XXH32(testInput, sampleSize, 0); -- cgit v0.12 From 444550defad26bcbe2e62209badbba76e803e521 Mon Sep 17 00:00:00 2001 From: Yann ColletDate: Wed, 29 May 2019 12:21:14 -0700 Subject: ensure lz4.h can be included with or without LZ4_STATIC_LINKING_ONLY in any order ensure correct propagation of LZ4_DISTANCE_MAX --- lib/lz4.c | 1 + lib/lz4.h | 16 ++++++++++++---- lib/lz4hc.h | 3 +++ 3 files changed, 16 insertions(+), 4 deletions(-) diff --git a/lib/lz4.c b/lib/lz4.c index 19070c2..a198a03 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -106,6 +106,7 @@ #define LZ4_DISABLE_DEPRECATE_WARNINGS /* due to LZ4_decompress_safe_withPrefix64k */ #endif +#define LZ4_STATIC_LINKING_ONLY /* LZ4_DISTANCE_MAX */ #include "lz4.h" /* see also "memory routines" below */ diff --git a/lib/lz4.h b/lib/lz4.h index ae7f52c..1e24ce9 100644 --- a/lib/lz4.h +++ b/lib/lz4.h @@ -388,6 +388,8 @@ LZ4LIB_API int LZ4_decompress_safe_continue (LZ4_streamDecode_t* LZ4_streamDecod */ LZ4LIB_API int LZ4_decompress_safe_usingDict (const char* src, char* dst, int srcSize, int dstCapcity, const char* dictStart, int dictSize); +#endif /* LZ4_H_2983827168210 */ + /*^************************************* * !!!!!! STATIC LINKING ONLY !!!!!! @@ -413,14 +415,17 @@ LZ4LIB_API int LZ4_decompress_safe_usingDict (const char* src, char* dst, int sr * define LZ4_PUBLISH_STATIC_FUNCTIONS when building the LZ4 library. ******************************************************************************/ +#ifdef LZ4_STATIC_LINKING_ONLY + +#ifndef LZ4_STATIC_3504398509 +#define LZ4_STATIC_3504398509 + #ifdef LZ4_PUBLISH_STATIC_FUNCTIONS #define LZ4LIB_STATIC_API LZ4LIB_API #else #define LZ4LIB_STATIC_API #endif -#ifdef LZ4_STATIC_LINKING_ONLY - /*! LZ4_compress_fast_extState_fastReset() : * A variant of LZ4_compress_fast_extState(). @@ -503,11 +508,14 @@ LZ4LIB_STATIC_API void LZ4_attach_dictionary(LZ4_stream_t* workingStream, const #define LZ4_COMPRESS_INPLACE_MARGIN (LZ4_DISTANCE_MAX + 32) #define LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCompressedSize) ( (maxCompressedSize) + LZ4_COMPRESS_INPLACE_MARGIN) /**< maxCompressedSize is generally LZ4_COMPRESSBOUND(inputSize), but can be set to any lower value, with the risk that compression can fail (return code 0(zero)) */ - +#endif /* LZ4_STATIC_3504398509 */ #endif /* LZ4_STATIC_LINKING_ONLY */ +#ifndef LZ4_H_98237428734687 +#define LZ4_H_98237428734687 + /*-************************************************************ * PRIVATE DEFINITIONS ************************************************************** @@ -718,7 +726,7 @@ LZ4LIB_API int LZ4_decompress_fast_usingDict (const char* src, char* dst, int or LZ4LIB_API void LZ4_resetStream (LZ4_stream_t* streamPtr); -#endif /* LZ4_H_2983827168210 */ +#endif /* LZ4_H_98237428734687 */ #if defined (__cplusplus) diff --git a/lib/lz4hc.h b/lib/lz4hc.h index cdc6d89..44e35bb 100644 --- a/lib/lz4hc.h +++ b/lib/lz4hc.h @@ -336,6 +336,9 @@ LZ4LIB_API void LZ4_resetStreamHC (LZ4_streamHC_t* streamHCPtr, int compressionL #ifndef LZ4_HC_SLO_098092834 #define LZ4_HC_SLO_098092834 +#define LZ4_STATIC_LINKING_ONLY /* LZ4LIB_STATIC_API */ +#include "lz4.h" + #if defined (__cplusplus) extern "C" { #endif -- cgit v0.12 From c5bcb4d68b44bd276523cd354424b89efe511b76 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Wed, 29 May 2019 12:56:27 -0700 Subject: fixed minor conversion warning --- tests/fuzzer.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/tests/fuzzer.c b/tests/fuzzer.c index e04caa5..8107cb8 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -1031,7 +1031,7 @@ static void FUZ_unitTests(int compressionLevel) assert(cSize <= (int)maxCSize); /* decompress and verify */ { int const dSize = LZ4_decompress_safe(testCompressed, testVerify, cSize, testInputSize); - assert(dSize == sampleSize); /* correct size */ + assert(dSize == (int)sampleSize); /* correct size */ { XXH32_hash_t const crcCheck = XXH32(testVerify, (size_t)dSize, 0); assert(crcCheck == crcOrig); } } } -- cgit v0.12 From 76116495bfd2096f06c923ebe865c59e42f32b07 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Wed, 29 May 2019 13:14:52 -0700 Subject: some more minor conversion warnings fixes --- Makefile | 2 +- lib/lz4.c | 8 ++++---- tests/fuzzer.c | 10 +++++----- 3 files changed, 10 insertions(+), 10 deletions(-) diff --git a/Makefile b/Makefile index e24cec5..3e55046 100644 --- a/Makefile +++ b/Makefile @@ -49,7 +49,7 @@ allmost: lib lz4 .PHONY: lib lib-release liblz4.a lib: liblz4.a lib lib-release liblz4.a: - @$(MAKE) -C $(LZ4DIR) $@ + @CFLAGS="$(CFLAGS)" $(MAKE) -C $(LZ4DIR) $@ .PHONY: lz4 lz4-release lz4 : liblz4.a diff --git a/lib/lz4.c b/lib/lz4.c index a198a03..4451bfc 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -462,7 +462,7 @@ static unsigned LZ4_NbCommonBytes (reg_t val) _BitScanForward64( &r, (U64)val ); return (int)(r>>3); # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_ctzll((U64)val) >> 3); + return (unsigned)__builtin_ctzll((U64)val) >> 3; # else static const int DeBruijnBytePos[64] = { 0, 0, 0, 0, 0, 1, 1, 2, 0, 3, 1, 3, 1, 4, 2, 7, @@ -480,7 +480,7 @@ static unsigned LZ4_NbCommonBytes (reg_t val) _BitScanForward( &r, (U32)val ); return (int)(r>>3); # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_ctz((U32)val) >> 3); + return (unsigned)__builtin_ctz((U32)val) >> 3; # else static const int DeBruijnBytePos[32] = { 0, 0, 3, 0, 3, 1, 3, 0, 3, 2, 2, 1, 3, 2, 0, 1, @@ -496,7 +496,7 @@ static unsigned LZ4_NbCommonBytes (reg_t val) _BitScanReverse64( &r, val ); return (unsigned)(r>>3); # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_clzll((U64)val) >> 3); + return (unsigned)__builtin_clzll((U64)val) >> 3; # else static const U32 by32 = sizeof(val)*4; /* 32 on 64 bits (goal), 16 on 32 bits. Just to avoid some static analyzer complaining about shift by 32 on 32-bits target. @@ -513,7 +513,7 @@ static unsigned LZ4_NbCommonBytes (reg_t val) _BitScanReverse( &r, (unsigned long)val ); return (unsigned)(r>>3); # elif (defined(__clang__) || (defined(__GNUC__) && (__GNUC__>=3))) && !defined(LZ4_FORCE_SW_BITCOUNT) - return (__builtin_clz((U32)val) >> 3); + return (unsigned)__builtin_clz((U32)val) >> 3; # else unsigned r; if (!(val>>16)) { r=2; val>>=8; } else { r=0; val>>=24; } diff --git a/tests/fuzzer.c b/tests/fuzzer.c index 8107cb8..9225e5b 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -1015,10 +1015,10 @@ static void FUZ_unitTests(int compressionLevel) /* in-place compression test */ DISPLAYLEVEL(3, "in-place compression using LZ4_compress_default() :"); - { size_t const sampleSize = 65 KB; - size_t const maxCSize = LZ4_COMPRESSBOUND(sampleSize); - size_t const outSize = LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCSize); - size_t const startIndex = outSize - sampleSize; + { int const sampleSize = 65 KB; + int const maxCSize = LZ4_COMPRESSBOUND(sampleSize); + int const outSize = LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCSize); + int const startIndex = outSize - sampleSize; char* const startInput = testCompressed + startIndex; XXH32_hash_t const crcOrig = XXH32(testInput, sampleSize, 0); int cSize; @@ -1028,7 +1028,7 @@ static void FUZ_unitTests(int compressionLevel) cSize = LZ4_compress_default(startInput, testCompressed, sampleSize, maxCSize); assert(cSize != 0); /* ensure compression is successful */ assert(maxCSize < INT_MAX); - assert(cSize <= (int)maxCSize); + assert(cSize <= maxCSize); /* decompress and verify */ { int const dSize = LZ4_decompress_safe(testCompressed, testVerify, cSize, testInputSize); assert(dSize == (int)sampleSize); /* correct size */ -- cgit v0.12 From 45eba5b0303c7a960b46fa07c3f578f5051826d8 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Wed, 29 May 2019 13:17:45 -0700 Subject: one more conversion warning --- tests/fuzzer.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/tests/fuzzer.c b/tests/fuzzer.c index 9225e5b..0cd651d 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -1022,7 +1022,7 @@ static void FUZ_unitTests(int compressionLevel) char* const startInput = testCompressed + startIndex; XXH32_hash_t const crcOrig = XXH32(testInput, sampleSize, 0); int cSize; - assert(outSize < testCompressedSize); + assert(outSize < (int)testCompressedSize); memcpy(startInput, testInput, sampleSize); /* copy at end of buffer */ /* compress in-place */ cSize = LZ4_compress_default(startInput, testCompressed, sampleSize, maxCSize); -- cgit v0.12 From b2ba857a4f295af79f94207cab1b9febec14a380 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Wed, 29 May 2019 13:33:55 -0700 Subject: fuzzer: changed internal buffer size to ensure no overflow during unit tests --- tests/fuzzer.c | 19 ++++++++++--------- 1 file changed, 10 insertions(+), 9 deletions(-) diff --git a/tests/fuzzer.c b/tests/fuzzer.c index 0cd651d..ba995e7 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -965,7 +965,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c } -#define testInputSize (192 KB) +#define testInputSize (196 KB) #define testCompressedSize (130 KB) #define ringBufferSize (8 KB) @@ -1175,12 +1175,12 @@ static void FUZ_unitTests(int compressionLevel) { U64 const crc64 = XXH64(testInput + 64 KB, testCompressedSize, 0); LZ4_resetStreamHC_fast(&sHC, compressionLevel); LZ4_loadDictHC(&sHC, testInput, 64 KB); - result = LZ4_compress_HC_continue(&sHC, testInput + 64 KB, testCompressed, testCompressedSize, testCompressedSize-1); - FUZ_CHECKTEST(result==0, "LZ4_compressHC_limitedOutput_continue() dictionary compression failed : result = %i", result); - FUZ_CHECKTEST(sHC.internal_donotuse.dirty, "Context should be clean"); - - result = LZ4_decompress_safe_usingDict(testCompressed, testVerify, result, testCompressedSize, testInput, 64 KB); - FUZ_CHECKTEST(result!=(int)testCompressedSize, "LZ4_decompress_safe() simple dictionary decompression test failed"); + { int const cSize = LZ4_compress_HC_continue(&sHC, testInput + 64 KB, testCompressed, testCompressedSize, testCompressedSize-1); + FUZ_CHECKTEST(cSize==0, "LZ4_compressHC_limitedOutput_continue() dictionary compression failed : @return = %i", cSize); + FUZ_CHECKTEST(sHC.internal_donotuse.dirty, "Context should be clean"); + { int const dSize = LZ4_decompress_safe_usingDict(testCompressed, testVerify, cSize, testCompressedSize, testInput, 64 KB); + FUZ_CHECKTEST(dSize!=(int)testCompressedSize, "LZ4_decompress_safe() simple dictionary decompression test failed"); + } } { U64 const crcNew = XXH64(testVerify, testCompressedSize, 0); FUZ_CHECKTEST(crc64!=crcNew, "LZ4_decompress_safe() simple dictionary decompression test : corruption"); } } @@ -1189,7 +1189,8 @@ static void FUZ_unitTests(int compressionLevel) /* multiple HC compression test with dictionary */ { int result1, result2; int segSize = testCompressedSize / 2; - U64 const crc64 = XXH64(testInput + segSize, testCompressedSize, 0); + XXH64_hash_t const crc64 = ( (void)assert((unsigned)segSize + testCompressedSize < testInputSize) , + XXH64(testInput + segSize, testCompressedSize, 0) ); LZ4_resetStreamHC_fast(&sHC, compressionLevel); LZ4_loadDictHC(&sHC, testInput, segSize); result1 = LZ4_compress_HC_continue(&sHC, testInput + segSize, testCompressed, segSize, segSize -1); @@ -1203,7 +1204,7 @@ static void FUZ_unitTests(int compressionLevel) FUZ_CHECKTEST(result!=segSize, "LZ4_decompress_safe() dictionary decompression part 1 failed"); result = LZ4_decompress_safe_usingDict(testCompressed+result1, testVerify+segSize, result2, segSize, testInput, 2*segSize); FUZ_CHECKTEST(result!=segSize, "LZ4_decompress_safe() dictionary decompression part 2 failed"); - { U64 const crcNew = XXH64(testVerify, testCompressedSize, 0); + { XXH64_hash_t const crcNew = XXH64(testVerify, testCompressedSize, 0); FUZ_CHECKTEST(crc64!=crcNew, "LZ4_decompress_safe() dictionary decompression corruption"); } } -- cgit v0.12 From 22adbb176afa46ebe1b799f7758381da8461bfe4 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Thu, 30 May 2019 09:45:21 -0700 Subject: add more doc on in-place (de)compression --- doc/lz4_manual.html | 30 +++++++++++++++++++++++++----- lib/lz4.h | 30 +++++++++++++++++++++++++----- 2 files changed, 50 insertions(+), 10 deletions(-) diff --git a/doc/lz4_manual.html b/doc/lz4_manual.html index 0530966..091f537 100644 --- a/doc/lz4_manual.html +++ b/doc/lz4_manual.html @@ -361,21 +361,35 @@ int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream); It's possible to have input and output sharing the same buffer, for highly contrained memory environments. In both cases, it requires input to lay at the end of the buffer, - and buffer must have some margin, hence be larger than final size. + and decompression to start at beginning of the buffer. + Buffer size must feature some margin, hence be larger than final size. + + |<------------------------buffer----------------------------------->| + |<------------compressed data---------->| + |<-----------decompressed size------------------>| + |<-----margin----->| This technique is more useful for decompression, since decompressed size is typically larger, and margin is mostly required to avoid stripe overflow, so it's short. - For compression though, margin must be able to cope with both + In-place decompression will work inside any buffer + which size is >= LZ4_DECOMPRESS_INPLACE_BUFFER_SIZE(decompressedSize). + This presumes that decompressedSize > compressedSize. + Otherwise, it means compression actually expanded data, + which can happen when data is not compressible (already compressed, or encrypted), + and it would be more efficient to store such data with a flag indicating it's not compressed. + + For compression, margin is larger, as it must be able to cope with both history preservation, requiring input data to remain unmodified up to LZ4_DISTANCE_MAX, and data expansion, which can happen when input is not compressible. - As a consequence, buffer size requirements are much higher than average compressed size, - hence memory savings are limited. + As a consequence, buffer size requirements are much higher, + and memory savings offered by in-place compression are more limited. There are ways to limit this cost for compression : - Reduce history size, by modifying LZ4_DISTANCE_MAX. - Lower values will also reduce compression ratio, except when input_size < LZ4_DISTANCE_MAX, + Note that it is a compile-time constant, so all future compression will apply this parameter. + Lower values will reduce compression ratio, except when input_size < LZ4_DISTANCE_MAX, so it's a reasonable trick when inputs are known to be small. - Require the compressor to deliver a "maximum compressed size". When this size is < LZ4_COMPRESSBOUND(inputSize), then compression can fail, @@ -384,6 +398,12 @@ int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream); and typically design a backup scheme to send data uncompressed. The combination of both techniques can significantly reduce the amount of margin required for in-place compression. + + In-place compression can work in any buffer + which size is >= LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCompressedSize) + with maxCompressedSize == LZ4_COMPRESSBOUND(srcSize) for guaranteed compression success. + This macro depends on both maxCompressedSize and LZ4_DISTANCE_MAX, + so there are ways to reduce memory requirements by playing with them.
#define LZ4_DECOMPRESS_INPLACE_BUFFER_SIZE(decompressedSize) ( (decompressedSize) + LZ4_DECOMPRESS_INPLACE_MARGIN) /**< note: presumes that compressedSize < decompressedSize */ +#define LZ4_DECOMPRESS_INPLACE_BUFFER_SIZE(decompressedSize) ( (decompressedSize) + LZ4_DECOMPRESS_INPLACE_MARGIN(decompressedSize)) /**< note: presumes that compressedSize < decompressedSize */
#define LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCompressedSize) ( (maxCompressedSize) + LZ4_COMPRESS_INPLACE_MARGIN) /**< maxCompressedSize is generally LZ4_COMPRESSBOUND(inputSize), but can be set to any lower value, with the risk that compression can fail (return code 0(zero)) */
-- cgit v0.12 From 4eec64e4d80140400ad138b18b7286439329cb08 Mon Sep 17 00:00:00 2001 From: Yann ColletDate: Fri, 31 May 2019 11:31:48 -0700 Subject: Makefile removed CFLAGS modifier which was removing `-O3` as a side effect --- Makefile | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/Makefile b/Makefile index 3e55046..e24cec5 100644 --- a/Makefile +++ b/Makefile @@ -49,7 +49,7 @@ allmost: lib lz4 .PHONY: lib lib-release liblz4.a lib: liblz4.a lib lib-release liblz4.a: - @CFLAGS="$(CFLAGS)" $(MAKE) -C $(LZ4DIR) $@ + @$(MAKE) -C $(LZ4DIR) $@ .PHONY: lz4 lz4-release lz4 : liblz4.a -- cgit v0.12 From 33cb8518ac385835cc17be9a770b27b40cd0e15b Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Fri, 31 May 2019 11:44:37 -0700 Subject: decompress: changed final memcpy() into memmove() for compatibility with in-place decompression scenarios. --- lib/lz4.c | 23 +++++++++++++---------- 1 file changed, 13 insertions(+), 10 deletions(-) diff --git a/lib/lz4.c b/lib/lz4.c index 4451bfc..a1d1860 100644 --- a/lib/lz4.c +++ b/lib/lz4.c @@ -120,6 +120,7 @@ # pragma warning(disable : 4293) /* disable: C4293: too large shift (32-bits) */ #endif /* _MSC_VER */ +#define LZ4_FORCE_INLINE static #ifndef LZ4_FORCE_INLINE # ifdef _MSC_VER /* Visual Studio */ # define LZ4_FORCE_INLINE static __forceinline @@ -707,18 +708,19 @@ static const BYTE* LZ4_getPositionOnHash(U32 h, const void* tableBase, tableType { const U16* const hashTable = (const U16*) tableBase; return hashTable[h] + srcBase; } /* default, to ensure a return */ } -LZ4_FORCE_INLINE const BYTE* LZ4_getPosition(const BYTE* p, - const void* tableBase, tableType_t tableType, - const BYTE* srcBase) +LZ4_FORCE_INLINE const BYTE* +LZ4_getPosition(const BYTE* p, + const void* tableBase, tableType_t tableType, + const BYTE* srcBase) { U32 const h = LZ4_hashPosition(p, tableType); return LZ4_getPositionOnHash(h, tableBase, tableType, srcBase); } -LZ4_FORCE_INLINE void LZ4_prepareTable( - LZ4_stream_t_internal* const cctx, - const int inputSize, - const tableType_t tableType) { +LZ4_FORCE_INLINE void +LZ4_prepareTable(LZ4_stream_t_internal* const cctx, + const int inputSize, + const tableType_t tableType) { /* If compression failed during the previous step, then the context * is marked as dirty, therefore, it has to be fully reset. */ @@ -733,9 +735,10 @@ LZ4_FORCE_INLINE void LZ4_prepareTable( * out if it's safe to leave as is or whether it needs to be reset. */ if (cctx->tableType != clearedTable) { + assert(inputSize >= 0); if (cctx->tableType != tableType - || (tableType == byU16 && cctx->currentOffset + inputSize >= 0xFFFFU) - || (tableType == byU32 && cctx->currentOffset > 1 GB) + || ((tableType == byU16) && cctx->currentOffset + (unsigned)inputSize >= 0xFFFFU) + || ((tableType == byU32) && cctx->currentOffset > 1 GB) || tableType == byPtr || inputSize >= 4 KB) { @@ -1850,7 +1853,7 @@ LZ4_decompress_generic( if ((!endOnInput) && (cpy != oend)) { goto _output_error; } /* Error : block decoding must stop exactly there */ if ((endOnInput) && ((ip+length != iend) || (cpy > oend))) { goto _output_error; } /* Error : input must be consumed */ } - memcpy(op, ip, length); + memmove(op, ip, length); /* supports overlapping memory regions, which only matters for in-place decompression scenarios */ ip += length; op += length; if (!partialDecoding || (cpy == oend)) { -- cgit v0.12 From 5997e139f53169fa3a1c1b4418d2452a90b01602 Mon Sep 17 00:00:00 2001 From: Yann Collet Date: Fri, 31 May 2019 11:56:59 -0700 Subject: added more details for in-place documentation --- doc/lz4_manual.html | 25 +++++++++++++------------ lib/lz4.h | 29 +++++++++++++++-------------- 2 files changed, 28 insertions(+), 26 deletions(-) diff --git a/doc/lz4_manual.html b/doc/lz4_manual.html index 083211d..1480089 100644 --- a/doc/lz4_manual.html +++ b/doc/lz4_manual.html @@ -364,23 +364,23 @@ int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream); and decompression to start at beginning of the buffer. Buffer size must feature some margin, hence be larger than final size. - |<------------------------buffer----------------------------------->| - |<------------compressed data---------->| + |<------------------------buffer--------------------------------->| + |<-----------compressed data--------->| |<-----------decompressed size------------------>| - |<-----margin----->| + |<----margin---->| This technique is more useful for decompression, since decompressed size is typically larger, - and margin is mostly required to avoid stripe overflow, so it's short. + and margin is short. In-place decompression will work inside any buffer which size is >= LZ4_DECOMPRESS_INPLACE_BUFFER_SIZE(decompressedSize). This presumes that decompressedSize > compressedSize. Otherwise, it means compression actually expanded data, - which can happen when data is not compressible (already compressed, or encrypted), and it would be more efficient to store such data with a flag indicating it's not compressed. + This can happen when data is not compressible (already compressed, or encrypted). - For compression, margin is larger, as it must be able to cope with both + For in-place compression, margin is larger, as it must be able to cope with both history preservation, requiring input data to remain unmodified up to LZ4_DISTANCE_MAX, and data expansion, which can happen when input is not compressible. As a consequence, buffer size requirements are much higher, @@ -388,10 +388,11 @@ int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream); There are ways to limit this cost for compression : - Reduce history size, by modifying LZ4_DISTANCE_MAX. - Note that it is a compile-time constant, so all future compression will apply this parameter. + Note that it is a compile-time constant, so all compressions will apply this limit. Lower values will reduce compression ratio, except when input_size < LZ4_DISTANCE_MAX, so it's a reasonable trick when inputs are known to be small. - Require the compressor to deliver a "maximum compressed size". + This is the `dstCapacity` parameter in `LZ4_compress*()`. When this size is < LZ4_COMPRESSBOUND(inputSize), then compression can fail, in which case, the return code will be 0 (zero). The caller must be ready for these cases to happen, @@ -400,16 +401,16 @@ int LZ4_freeStreamDecode (LZ4_streamDecode_t* LZ4_stream); the amount of margin required for in-place compression. In-place compression can work in any buffer - which size is >= LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCompressedSize) + which size is >= (maxCompressedSize) with maxCompressedSize == LZ4_COMPRESSBOUND(srcSize) for guaranteed compression success. - This macro depends on both maxCompressedSize and LZ4_DISTANCE_MAX, - so there are ways to reduce memory requirements by playing with them. + LZ4_COMPRESS_INPLACE_BUFFER_SIZE() depends on both maxCompressedSize and LZ4_DISTANCE_MAX, + so it's possible to reduce memory requirements by playing with them.
#define LZ4_DECOMPRESS_INPLACE_BUFFER_SIZE(decompressedSize) ( (decompressedSize) + LZ4_DECOMPRESS_INPLACE_MARGIN(decompressedSize)) /**< note: presumes that compressedSize < decompressedSize */ +#define LZ4_DECOMPRESS_INPLACE_BUFFER_SIZE(decompressedSize) ((decompressedSize) + LZ4_DECOMPRESS_INPLACE_MARGIN(decompressedSize)) /**< note: presumes that compressedSize < decompressedSize. note2: margin is overestimated a bit, since it could use compressedSize instead */
-#define LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCompressedSize) ( (maxCompressedSize) + LZ4_COMPRESS_INPLACE_MARGIN) /**< maxCompressedSize is generally LZ4_COMPRESSBOUND(inputSize), but can be set to any lower value, with the risk that compression can fail (return code 0(zero)) */ +#define LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCompressedSize) ((maxCompressedSize) + LZ4_COMPRESS_INPLACE_MARGIN) /**< maxCompressedSize is generally LZ4_COMPRESSBOUND(inputSize), but can be set to any lower value, with the risk that compression can fail (return code 0(zero)) */
PRIVATE DEFINITIONS
Do not use these definitions directly. diff --git a/lib/lz4.h b/lib/lz4.h index 383c2db..0dfa637 100644 --- a/lib/lz4.h +++ b/lib/lz4.h @@ -476,23 +476,23 @@ LZ4LIB_STATIC_API void LZ4_attach_dictionary(LZ4_stream_t* workingStream, const * and decompression to start at beginning of the buffer. * Buffer size must feature some margin, hence be larger than final size. * - * |<------------------------buffer----------------------------------->| - * |<------------compressed data---------->| + * |<------------------------buffer--------------------------------->| + * |<-----------compressed data--------->| * |<-----------decompressed size------------------>| - * |<-----margin----->| + * |<----margin---->| * * This technique is more useful for decompression, * since decompressed size is typically larger, - * and margin is mostly required to avoid stripe overflow, so it's short. + * and margin is short. * * In-place decompression will work inside any buffer * which size is >= LZ4_DECOMPRESS_INPLACE_BUFFER_SIZE(decompressedSize). * This presumes that decompressedSize > compressedSize. * Otherwise, it means compression actually expanded data, - * which can happen when data is not compressible (already compressed, or encrypted), * and it would be more efficient to store such data with a flag indicating it's not compressed. + * This can happen when data is not compressible (already compressed, or encrypted). * - * For compression, margin is larger, as it must be able to cope with both + * For in-place compression, margin is larger, as it must be able to cope with both * history preservation, requiring input data to remain unmodified up to LZ4_DISTANCE_MAX, * and data expansion, which can happen when input is not compressible. * As a consequence, buffer size requirements are much higher, @@ -500,10 +500,11 @@ LZ4LIB_STATIC_API void LZ4_attach_dictionary(LZ4_stream_t* workingStream, const * * There are ways to limit this cost for compression : * - Reduce history size, by modifying LZ4_DISTANCE_MAX. - * Note that it is a compile-time constant, so all future compression will apply this parameter. + * Note that it is a compile-time constant, so all compressions will apply this limit. * Lower values will reduce compression ratio, except when input_size < LZ4_DISTANCE_MAX, * so it's a reasonable trick when inputs are known to be small. * - Require the compressor to deliver a "maximum compressed size". + * This is the `dstCapacity` parameter in `LZ4_compress*()`. * When this size is < LZ4_COMPRESSBOUND(inputSize), then compression can fail, * in which case, the return code will be 0 (zero). * The caller must be ready for these cases to happen, @@ -512,21 +513,21 @@ LZ4LIB_STATIC_API void LZ4_attach_dictionary(LZ4_stream_t* workingStream, const * the amount of margin required for in-place compression. * * In-place compression can work in any buffer - * which size is >= LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCompressedSize) + * which size is >= (maxCompressedSize) * with maxCompressedSize == LZ4_COMPRESSBOUND(srcSize) for guaranteed compression success. - * This macro depends on both maxCompressedSize and LZ4_DISTANCE_MAX, - * so there are ways to reduce memory requirements by playing with them. + * LZ4_COMPRESS_INPLACE_BUFFER_SIZE() depends on both maxCompressedSize and LZ4_DISTANCE_MAX, + * so it's possible to reduce memory requirements by playing with them. */ -#define LZ4_DECOMPRESS_INPLACE_MARGIN(decompressedSize) (((decompressedSize) >> 8) + 32) -#define LZ4_DECOMPRESS_INPLACE_BUFFER_SIZE(decompressedSize) ( (decompressedSize) + LZ4_DECOMPRESS_INPLACE_MARGIN(decompressedSize)) /**< note: presumes that compressedSize < decompressedSize */ +#define LZ4_DECOMPRESS_INPLACE_MARGIN(compressedSize) (((compressedSize) >> 8) + 32) +#define LZ4_DECOMPRESS_INPLACE_BUFFER_SIZE(decompressedSize) ((decompressedSize) + LZ4_DECOMPRESS_INPLACE_MARGIN(decompressedSize)) /**< note: presumes that compressedSize < decompressedSize. note2: margin is overestimated a bit, since it could use compressedSize instead */ #ifndef LZ4_DISTANCE_MAX /* history window size; can be user-defined at compile time */ # define LZ4_DISTANCE_MAX 65535 /* set to maximum value by default */ #endif -#define LZ4_COMPRESS_INPLACE_MARGIN (LZ4_DISTANCE_MAX + 32) -#define LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCompressedSize) ( (maxCompressedSize) + LZ4_COMPRESS_INPLACE_MARGIN) /**< maxCompressedSize is generally LZ4_COMPRESSBOUND(inputSize), but can be set to any lower value, with the risk that compression can fail (return code 0(zero)) */ +#define LZ4_COMPRESS_INPLACE_MARGIN (LZ4_DISTANCE_MAX + 32) /* LZ4_DISTANCE_MAX can be safely replaced by srcSize when it's smaller */ +#define LZ4_COMPRESS_INPLACE_BUFFER_SIZE(maxCompressedSize) ((maxCompressedSize) + LZ4_COMPRESS_INPLACE_MARGIN) /**< maxCompressedSize is generally LZ4_COMPRESSBOUND(inputSize), but can be set to any lower value, with the risk that compression can fail (return code 0(zero)) */ #endif /* LZ4_STATIC_3504398509 */ #endif /* LZ4_STATIC_LINKING_ONLY */ -- cgit v0.12