diff options
author | Yann Collet <Cyan4973@users.noreply.github.com> | 2019-05-31 19:59:38 (GMT) |
---|---|---|
committer | GitHub <noreply@github.com> | 2019-05-31 19:59:38 (GMT) |
commit | 280fc0856dbc279613669a86e0f81fe0b30d6edf (patch) | |
tree | 7f9b916874a0598c631ff356b2c8ba3afc77dde7 /lib | |
parent | 8008fdf396ae0a2d12a18bfd3fc2b033e3648fa6 (diff) | |
parent | 5997e139f53169fa3a1c1b4418d2452a90b01602 (diff) | |
download | lz4-280fc0856dbc279613669a86e0f81fe0b30d6edf.zip lz4-280fc0856dbc279613669a86e0f81fe0b30d6edf.tar.gz lz4-280fc0856dbc279613669a86e0f81fe0b30d6edf.tar.bz2 |
Merge pull request #717 from lz4/inplace
Added documentation and macro to support in-place compression and decompression
Diffstat (limited to 'lib')
-rw-r--r-- | lib/lz4.c | 36 | ||||
-rw-r--r-- | lib/lz4.h | 83 | ||||
-rw-r--r-- | lib/lz4hc.h | 3 |
3 files changed, 99 insertions, 23 deletions
@@ -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 */ @@ -119,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 @@ -412,10 +414,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 @@ -465,7 +463,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, @@ -483,7 +481,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, @@ -499,7 +497,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. @@ -516,7 +514,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; } @@ -710,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. */ @@ -736,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) { @@ -1853,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)) { @@ -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. */ /*^*************************************************************** @@ -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(). @@ -462,8 +467,75 @@ 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 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 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, + * 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 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, + * 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. + * 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, + * 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 >= (maxCompressedSize) + * with maxCompressedSize == LZ4_COMPRESSBOUND(srcSize) for guaranteed compression success. + * 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(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) /* 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 */ + + + +#ifndef LZ4_H_98237428734687 +#define LZ4_H_98237428734687 /*-************************************************************ * PRIVATE DEFINITIONS @@ -567,6 +639,7 @@ union LZ4_streamDecode_u { } ; /* previously typedef'd to LZ4_streamDecode_t */ + /*-************************************ * Obsolete Functions **************************************/ @@ -674,7 +747,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 |