diff options
author | Yann Collet <Cyan4973@users.noreply.github.com> | 2016-12-11 02:40:53 (GMT) |
---|---|---|
committer | GitHub <noreply@github.com> | 2016-12-11 02:40:53 (GMT) |
commit | fec57e49eaee4bf2926c9c2a4071d8f109e3ba71 (patch) | |
tree | 01d092019595311b4aa54f5a7a63dae0cb40a0ab | |
parent | 626552671a69a13cd467e27ed149dac4b35fd484 (diff) | |
parent | 4f050b68d817776e3c1fac6c449b5f2b2adfbcb9 (diff) | |
download | lz4-fec57e49eaee4bf2926c9c2a4071d8f109e3ba71.zip lz4-fec57e49eaee4bf2926c9c2a4071d8f109e3ba71.tar.gz lz4-fec57e49eaee4bf2926c9c2a4071d8f109e3ba71.tar.bz2 |
Merge pull request #287 from inikep/dev
opt parser
-rw-r--r-- | lib/README.md | 2 | ||||
-rw-r--r-- | lib/dll/example/README.md | 2 | ||||
-rw-r--r-- | lib/lz4hc.c | 45 | ||||
-rw-r--r-- | lib/lz4hc.h | 15 | ||||
-rw-r--r-- | lib/lz4opt.h | 395 | ||||
-rw-r--r-- | programs/lz4io.c | 11 |
6 files changed, 449 insertions, 21 deletions
diff --git a/lib/README.md b/lib/README.md index 18793d4..b40442c 100644 --- a/lib/README.md +++ b/lib/README.md @@ -47,7 +47,7 @@ The header files `lz4.h`, `lz4hc.h`, `lz4frame.h` and the dynamic library `dll\liblz4.dll` are required to compile a project using gcc/MinGW. The dynamic library has to be added to linking options. It means that if a project that uses LZ4 consists of a single `test-dll.c` -file it should be compiled with "liblz4.lib". For example: +file it should be linked with `dll\liblz4.dll`. For example: ``` gcc $(CFLAGS) -Iinclude/ test-dll.c -o test-dll dll\liblz4.dll ``` diff --git a/lib/dll/example/README.md b/lib/dll/example/README.md index 4908663..223e473 100644 --- a/lib/dll/example/README.md +++ b/lib/dll/example/README.md @@ -39,7 +39,7 @@ The header files from `include\` and the dynamic library `dll\liblz4.dll` are required to compile a project using gcc/MinGW. The dynamic library has to be added to linking options. It means that if a project that uses LZ4 consists of a single `test-dll.c` -file it should be compiled with "liblz4.dll". For example: +file it should be linked with `dll\liblz4.dll`. For example: ``` gcc $(CFLAGS) -Iinclude\ test-dll.c -o test-dll dll\liblz4.dll ``` diff --git a/lib/lz4hc.c b/lib/lz4hc.c index 298550c..44a1340 100644 --- a/lib/lz4hc.c +++ b/lib/lz4hc.c @@ -84,7 +84,7 @@ * Local Macros **************************************/ #define HASH_FUNCTION(i) (((i) * 2654435761U) >> ((MINMATCH*8)-LZ4HC_HASH_LOG)) -/* #define DELTANEXTU16(p) chainTable[(p) & LZ4HC_MAXD_MASK] */ /* flexible, LZ4HC_MAXD dependent */ +#define DELTANEXTMAXD(p) chainTable[(p) & LZ4HC_MAXD_MASK] /* flexible, LZ4HC_MAXD dependent */ #define DELTANEXTU16(p) chainTable[(U16)(p)] /* faster */ static U32 LZ4HC_hashPtr(const void* ptr) { return HASH_FUNCTION(LZ4_read32(ptr)); } @@ -98,7 +98,7 @@ static void LZ4HC_init (LZ4HC_CCtx_internal* hc4, const BYTE* start) { MEM_INIT((void*)hc4->hashTable, 0, sizeof(hc4->hashTable)); MEM_INIT(hc4->chainTable, 0xFF, sizeof(hc4->chainTable)); - hc4->nextToUpdate = 64 KB; + hc4->nextToUpdate = hc4->nextToUpdateBT = 64 KB; hc4->base = start - 64 KB; hc4->end = start; hc4->dictBase = start - 64 KB; @@ -305,14 +305,15 @@ FORCE_INLINE int LZ4HC_encodeSequence ( return 0; } +#include "lz4opt.h" -static int LZ4HC_compress_generic ( +static int LZ4HC_compress_hashChain ( LZ4HC_CCtx_internal* const ctx, const char* const source, char* const dest, int const inputSize, int const maxOutputSize, - int compressionLevel, + unsigned maxNbAttempts, limitedOutput_directive limit ) { @@ -325,7 +326,6 @@ static int LZ4HC_compress_generic ( BYTE* op = (BYTE*) dest; BYTE* const oend = op + maxOutputSize; - unsigned maxNbAttempts; int ml, ml2, ml3, ml0; const BYTE* ref = NULL; const BYTE* start2 = NULL; @@ -336,9 +336,6 @@ static int LZ4HC_compress_generic ( const BYTE* ref0; /* init */ - if (compressionLevel > LZ4HC_MAX_CLEVEL) compressionLevel = LZ4HC_MAX_CLEVEL; - if (compressionLevel < 1) compressionLevel = LZ4HC_DEFAULT_CLEVEL; - maxNbAttempts = 1 << (compressionLevel-1); ctx->end += inputSize; ip++; @@ -490,6 +487,29 @@ _Search3: } +static int LZ4HC_compress_generic ( + LZ4HC_CCtx_internal* const ctx, + const char* const source, + char* const dest, + int const inputSize, + int const maxOutputSize, + int compressionLevel, + limitedOutput_directive limit + ) +{ + if (compressionLevel < 1) compressionLevel = LZ4HC_DEFAULT_CLEVEL; + if (compressionLevel > 9) { + switch (compressionLevel) { + case 10: return LZ4HC_compress_hashChain(ctx, source, dest, inputSize, maxOutputSize, 1 << (16-1), limit); + case 11: ctx->searchNum = 128; return LZ4HC_compress_optimal(ctx, source, dest, inputSize, maxOutputSize, limit, 128, 0); + default: + case 12: ctx->searchNum = 1<<10; return LZ4HC_compress_optimal(ctx, source, dest, inputSize, maxOutputSize, limit, LZ4_OPT_NUM, 1); + } + } + return LZ4HC_compress_hashChain(ctx, source, dest, inputSize, maxOutputSize, 1 << (compressionLevel-1), limit); +} + + int LZ4_sizeofStateHC(void) { return sizeof(LZ4_streamHC_t); } int LZ4_compress_HC_extStateHC (void* state, const char* src, char* dst, int srcSize, int maxDstSize, int compressionLevel) @@ -554,14 +574,18 @@ int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal* ctxPtr, const BYTE* newBlock) { - if (ctxPtr->end >= ctxPtr->base + 4) LZ4HC_Insert (ctxPtr, ctxPtr->end-3); /* Referencing remaining dictionary content */ + if (ctxPtr->compressionLevel >= LZ4HC_MIN_CLEVEL_OPT) + LZ4HC_updateBinTree(ctxPtr, ctxPtr->end - MFLIMIT, ctxPtr->end - LASTLITERALS); + else + if (ctxPtr->end >= ctxPtr->base + 4) LZ4HC_Insert (ctxPtr, ctxPtr->end-3); /* Referencing remaining dictionary content */ + /* Only one memory segment for extDict, so any previous extDict is lost at this stage */ ctxPtr->lowLimit = ctxPtr->dictLimit; ctxPtr->dictLimit = (U32)(ctxPtr->end - ctxPtr->base); ctxPtr->dictBase = ctxPtr->base; ctxPtr->base = newBlock - ctxPtr->dictLimit; ctxPtr->end = newBlock; - ctxPtr->nextToUpdate = ctxPtr->dictLimit; /* match referencing will resume from there */ + ctxPtr->nextToUpdate = ctxPtr->nextToUpdateBT = ctxPtr->dictLimit; /* match referencing will resume from there */ } static int LZ4_compressHC_continue_generic (LZ4_streamHC_t* LZ4_streamHCPtr, @@ -621,6 +645,7 @@ int LZ4_saveDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, char* safeBuffer, int dictS streamPtr->dictLimit = endIndex - dictSize; streamPtr->lowLimit = endIndex - dictSize; if (streamPtr->nextToUpdate < streamPtr->dictLimit) streamPtr->nextToUpdate = streamPtr->dictLimit; + if (streamPtr->nextToUpdateBT < streamPtr->dictLimit) streamPtr->nextToUpdateBT = streamPtr->dictLimit; } return dictSize; } diff --git a/lib/lz4hc.h b/lib/lz4hc.h index d8ac3c0..7ce5958 100644 --- a/lib/lz4hc.h +++ b/lib/lz4hc.h @@ -46,7 +46,8 @@ extern "C" { /* --- Useful constants --- */ #define LZ4HC_MIN_CLEVEL 3 #define LZ4HC_DEFAULT_CLEVEL 9 -#define LZ4HC_MAX_CLEVEL 16 +#define LZ4HC_MIN_CLEVEL_OPT 11 +#define LZ4HC_MAX_CLEVEL 12 /*-************************************ @@ -58,7 +59,7 @@ extern "C" { * Compression is guaranteed to succeed if `dstCapacity >= LZ4_compressBound(srcSize)` (see "lz4.h") * Max supported `srcSize` value is LZ4_MAX_INPUT_SIZE (see "lz4.h") * `compressionLevel` : Recommended values are between 4 and 9, although any value between 1 and LZ4HC_MAX_CLEVEL will work. - * Values >LZ4HC_MAX_CLEVEL behave the same as 16. + * Values >LZ4HC_MAX_CLEVEL behave the same as LZ4HC_MAX_CLEVEL. * @return : the number of bytes written into 'dst' * or 0 if compression fails. */ @@ -130,11 +131,11 @@ LZ4LIB_API int LZ4_saveDictHC (LZ4_streamHC_t* streamHCPtr, char* safeBuffer, in * They are exposed to allow static allocation of `LZ4_streamHC_t`. * Using these definitions makes the code vulnerable to potential API break when upgrading LZ4 **************************************/ -#define LZ4HC_DICTIONARY_LOGSIZE 16 +#define LZ4HC_DICTIONARY_LOGSIZE 17 #define LZ4HC_MAXD (1<<LZ4HC_DICTIONARY_LOGSIZE) #define LZ4HC_MAXD_MASK (LZ4HC_MAXD - 1) -#define LZ4HC_HASH_LOG (LZ4HC_DICTIONARY_LOGSIZE-1) +#define LZ4HC_HASH_LOG 15 #define LZ4HC_HASHTABLESIZE (1 << LZ4HC_HASH_LOG) #define LZ4HC_HASH_MASK (LZ4HC_HASHTABLESIZE - 1) @@ -153,6 +154,8 @@ typedef struct uint32_t dictLimit; /* below that point, need extDict */ uint32_t lowLimit; /* below that point, no more dict */ uint32_t nextToUpdate; /* index from which to continue dictionary update */ + uint32_t nextToUpdateBT; /* index from which to continue binary tree update */ + uint32_t searchNum; /* only for optimal parser */ uint32_t compressionLevel; } LZ4HC_CCtx_internal; @@ -169,12 +172,14 @@ typedef struct unsigned int dictLimit; /* below that point, need extDict */ unsigned int lowLimit; /* below that point, no more dict */ unsigned int nextToUpdate; /* index from which to continue dictionary update */ + unsigned int nextToUpdateBT; /* index from which to continue binary tree update */ + unsigned int searchNum; /* only for optimal parser */ unsigned int compressionLevel; } LZ4HC_CCtx_internal; #endif -#define LZ4_STREAMHCSIZE 262192 +#define LZ4_STREAMHCSIZE (4*LZ4HC_HASHTABLESIZE + 2*LZ4HC_MAXD + 56) /* 393268 */ #define LZ4_STREAMHCSIZE_SIZET (LZ4_STREAMHCSIZE / sizeof(size_t)) union LZ4_streamHC_u { size_t table[LZ4_STREAMHCSIZE_SIZET]; diff --git a/lib/lz4opt.h b/lib/lz4opt.h new file mode 100644 index 0000000..f487edf --- /dev/null +++ b/lib/lz4opt.h @@ -0,0 +1,395 @@ +/* + lz4opt.h - Optimal Mode of LZ4 + Copyright (C) 2015-2016, 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_LOG_PARSER(fmt, ...) //printf(fmt, __VA_ARGS__) +#define LZ4_LOG_PRICE(fmt, ...) //printf(fmt, __VA_ARGS__) +#define LZ4_LOG_ENCODE(fmt, ...) //printf(fmt, __VA_ARGS__) + + +#define LZ4_OPT_NUM (1<<12) + + +typedef struct +{ + int off; + int len; +} LZ4HC_match_t; + +typedef struct +{ + int price; + int off; + int mlen; + int litlen; +} LZ4HC_optimal_t; + + +FORCE_INLINE size_t LZ4HC_GetLiteralsPrice(size_t litlen) +{ + size_t price = 8*litlen; + if (litlen >= (int)RUN_MASK) price+=8*(1+(litlen-RUN_MASK)/255); + return price; +} + + +FORCE_INLINE size_t LZ4HC_get_price(size_t litlen, size_t mlen) +{ + size_t price = 16 + 8; /* 16-bit offset + token */ + + price += 8*litlen; + if (litlen >= (int)RUN_MASK) price+=8*(1+(litlen-RUN_MASK)/255); + + mlen -= MINMATCH; + if (mlen >= (int)ML_MASK) price+=8*(1+(mlen-ML_MASK)/255); + + return price; +} + + +/*-************************************* +* Binary Tree search +***************************************/ +FORCE_INLINE int LZ4HC_BinTree_InsertAndGetAllMatches ( + LZ4HC_CCtx_internal* ctx, + const BYTE* const ip, + const BYTE* const iHighLimit, + size_t best_mlen, + LZ4HC_match_t* matches, + int* matchNum) +{ + U16* const chainTable = ctx->chainTable; + U32* const HashTable = ctx->hashTable; + const BYTE* const base = ctx->base; + const U32 dictLimit = ctx->dictLimit; + const U32 current = (U32)(ip - base); + const U32 lowLimit = (ctx->lowLimit + MAX_DISTANCE > current) ? ctx->lowLimit : current - (MAX_DISTANCE - 1); + const BYTE* const dictBase = ctx->dictBase; + const BYTE* match; + int nbAttempts = ctx->searchNum; + int mnum = 0; + U16 *ptr0, *ptr1, delta0, delta1; + U32 matchIndex; + size_t matchLength = 0; + U32* HashPos; + + if (ip + MINMATCH > iHighLimit) return 1; + + /* HC4 match finder */ + HashPos = &HashTable[LZ4HC_hashPtr(ip)]; + matchIndex = *HashPos; + *HashPos = current; + + ptr0 = &DELTANEXTMAXD(current*2+1); + ptr1 = &DELTANEXTMAXD(current*2); + delta0 = delta1 = (U16)(current - matchIndex); + + while ((matchIndex < current) && (matchIndex>=lowLimit) && (nbAttempts)) { + nbAttempts--; + if (matchIndex >= dictLimit) { + match = base + matchIndex; + matchLength = LZ4_count(ip, match, iHighLimit); + } else { + const BYTE* vLimit = ip + (dictLimit - matchIndex); + match = dictBase + matchIndex; + if (vLimit > iHighLimit) vLimit = iHighLimit; + matchLength = LZ4_count(ip, match, vLimit); + if ((ip+matchLength == vLimit) && (vLimit < iHighLimit)) + matchLength += LZ4_count(ip+matchLength, base+dictLimit, iHighLimit); + } + + if (matchLength > best_mlen) { + best_mlen = matchLength; + if (matches) { + matches[mnum].off = (int)(ip - match); + matches[mnum].len = (int)matchLength; + mnum++; + } + if (best_mlen > LZ4_OPT_NUM) break; + } + + if (ip+matchLength >= iHighLimit) /* equal : no way to know if inf or sup */ + break; /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */ + + if (*(ip+matchLength) < *(match+matchLength)) { + *ptr0 = delta0; + ptr0 = &DELTANEXTMAXD(matchIndex*2); + if (*ptr0 == (U16)-1) break; + delta0 = *ptr0; + delta1 += delta0; + matchIndex -= delta0; + } else { + *ptr1 = delta1; + ptr1 = &DELTANEXTMAXD(matchIndex*2+1); + if (*ptr1 == (U16)-1) break; + delta1 = *ptr1; + delta0 += delta1; + matchIndex -= delta1; + } + } + + *ptr0 = (U16)-1; + *ptr1 = (U16)-1; + if (matchNum) *matchNum = mnum; + /* if (best_mlen > 8) return best_mlen-8; */ + if (!matchNum) return 1; + return 1; +} + + +FORCE_INLINE void LZ4HC_updateBinTree(LZ4HC_CCtx_internal* ctx, const BYTE* const ip, const BYTE* const iHighLimit) +{ + const BYTE* const base = ctx->base; + const U32 target = (U32)(ip - base); + U32 idx = ctx->nextToUpdateBT; + + while(idx < target) + idx += LZ4HC_BinTree_InsertAndGetAllMatches(ctx, base+idx, iHighLimit, 8, NULL, NULL); +} + + +/** Tree updater, providing best match */ +FORCE_INLINE int LZ4HC_BinTree_GetAllMatches ( + LZ4HC_CCtx_internal* ctx, + const BYTE* const ip, const BYTE* const iHighLimit, + size_t best_mlen, LZ4HC_match_t* matches, const int fullUpdate) +{ + int mnum = 0; + if (ip < ctx->base + ctx->nextToUpdateBT) return 0; /* skipped area */ + if (fullUpdate) LZ4HC_updateBinTree(ctx, ip, iHighLimit); + best_mlen = LZ4HC_BinTree_InsertAndGetAllMatches(ctx, ip, iHighLimit, best_mlen, matches, &mnum); + ctx->nextToUpdateBT = (U32)(ip - ctx->base + best_mlen); + return mnum; +} + + +#define SET_PRICE(pos, mlen, offset, litlen, price) \ +{ \ + while (last_pos < pos) { opt[last_pos+1].price = 1<<30; last_pos++; } \ + opt[pos].mlen = (int)mlen; \ + opt[pos].off = (int)offset; \ + opt[pos].litlen = (int)litlen; \ + opt[pos].price = (int)price; \ + LZ4_LOG_PARSER("%d: SET price[%d/%d]=%d litlen=%d len=%d off=%d\n", (int)(inr-source), pos, last_pos, opt[pos].price, opt[pos].litlen, opt[pos].mlen, opt[pos].off); \ +} + + +static int LZ4HC_compress_optimal ( + LZ4HC_CCtx_internal* ctx, + const char* const source, + char* dest, + int inputSize, + int maxOutputSize, + limitedOutput_directive limit, + const size_t sufficient_len, + const int fullUpdate + ) +{ + LZ4HC_optimal_t opt[LZ4_OPT_NUM + 1]; + LZ4HC_match_t matches[LZ4_OPT_NUM + 1]; + const BYTE *inr; + size_t res, cur, cur2; + size_t i, llen, litlen, mlen, best_mlen, price, offset, best_off, match_num, last_pos; + + const BYTE* ip = (const BYTE*) source; + const BYTE* anchor = ip; + const BYTE* const iend = ip + inputSize; + const BYTE* const mflimit = iend - MFLIMIT; + const BYTE* const matchlimit = (iend - LASTLITERALS); + BYTE* op = (BYTE*) dest; + BYTE* const oend = op + maxOutputSize; + + /* init */ + ctx->end += inputSize; + ip++; + + /* Main Loop */ + while (ip < mflimit) { + memset(opt, 0, sizeof(LZ4HC_optimal_t)); + last_pos = 0; + llen = ip - anchor; + match_num = LZ4HC_BinTree_GetAllMatches(ctx, ip, matchlimit, MINMATCH-1, matches, fullUpdate); + if (!match_num) { ip++; continue; } + LZ4_LOG_PARSER("%d: match_num=%d last_pos=%d\n", (int)(ip-source), match_num, last_pos); + + if ((size_t)matches[match_num-1].len > sufficient_len) { + best_mlen = matches[match_num-1].len; + best_off = matches[match_num-1].off; + cur = 0; + last_pos = 1; + goto encode; + } + + /* set prices using matches at position = 0 */ + for (i = 0; i < match_num; i++) { + mlen = (i>0) ? (size_t)matches[i-1].len+1 : MINMATCH; + best_mlen = (matches[i].len < LZ4_OPT_NUM) ? matches[i].len : LZ4_OPT_NUM; + LZ4_LOG_PARSER("%d: start Found mlen=%d off=%d best_mlen=%d last_pos=%d\n", (int)(ip-source), matches[i].len, matches[i].off, best_mlen, last_pos); + while (mlen <= best_mlen) { + litlen = 0; + price = LZ4HC_get_price(llen + litlen, mlen) - LZ4HC_GetLiteralsPrice(llen); + SET_PRICE(mlen, mlen, matches[i].off, litlen, price); + mlen++; + } + } + + if (last_pos < MINMATCH) { ip++; continue; } + + /* check further positions */ + opt[0].mlen = opt[1].mlen = 1; + for (cur = 1; cur <= last_pos; cur++) { + inr = ip + cur; + + if (opt[cur-1].mlen == 1) { + litlen = opt[cur-1].litlen + 1; + if (cur != litlen) { + price = opt[cur - litlen].price + LZ4HC_GetLiteralsPrice(litlen); + LZ4_LOG_PRICE("%d: TRY1 opt[%d].price=%d price=%d cur=%d litlen=%d\n", (int)(inr-source), cur - litlen, opt[cur - litlen].price, price, cur, litlen); + } else { + price = LZ4HC_GetLiteralsPrice(llen + litlen) - LZ4HC_GetLiteralsPrice(llen); + LZ4_LOG_PRICE("%d: TRY2 price=%d cur=%d litlen=%d llen=%d\n", (int)(inr-source), price, cur, litlen, llen); + } + } else { + litlen = 1; + price = opt[cur - 1].price + LZ4HC_GetLiteralsPrice(litlen); + LZ4_LOG_PRICE("%d: TRY3 price=%d cur=%d litlen=%d litonly=%d\n", (int)(inr-source), price, cur, litlen, LZ4HC_GetLiteralsPrice(litlen)); + } + + mlen = 1; + best_mlen = 0; + LZ4_LOG_PARSER("%d: TRY price=%d opt[%d].price=%d\n", (int)(inr-source), price, cur, opt[cur].price); + if (cur > last_pos || price < (size_t)opt[cur].price) + SET_PRICE(cur, mlen, best_mlen, litlen, price); + + if (cur == last_pos || inr >= mflimit) break; + LZ4_LOG_PARSER("%d: CURRENT price[%d/%d]=%d off=%d mlen=%d litlen=%d\n", (int)(inr-source), cur, last_pos, opt[cur].price, opt[cur].off, opt[cur].mlen, opt[cur].litlen); + + match_num = LZ4HC_BinTree_GetAllMatches(ctx, inr, matchlimit, MINMATCH-1, matches, fullUpdate); + LZ4_LOG_PARSER("%d: LZ4HC_BinTree_GetAllMatches match_num=%d\n", (int)(inr-source), match_num); + + if (match_num > 0 && (size_t)matches[match_num-1].len > sufficient_len) { + best_mlen = matches[match_num-1].len; + best_off = matches[match_num-1].off; + last_pos = cur + 1; + goto encode; + } + + /* set prices using matches at position = cur */ + for (i = 0; i < match_num; i++) { + mlen = (i>0) ? (size_t)matches[i-1].len+1 : MINMATCH; + cur2 = cur; + best_mlen = (cur2 + matches[i].len < LZ4_OPT_NUM) ? (size_t)matches[i].len : LZ4_OPT_NUM - cur2; + LZ4_LOG_PARSER("%d: Found1 cur=%d cur2=%d mlen=%d off=%d best_mlen=%d last_pos=%d\n", (int)(inr-source), cur, cur2, matches[i].len, matches[i].off, best_mlen, last_pos); + + while (mlen <= best_mlen) { + if (opt[cur2].mlen == 1) { + litlen = opt[cur2].litlen; + + if (cur2 != litlen) + price = opt[cur2 - litlen].price + LZ4HC_get_price(litlen, mlen); + else + price = LZ4HC_get_price(llen + litlen, mlen) - LZ4HC_GetLiteralsPrice(llen); + } else { + litlen = 0; + price = opt[cur2].price + LZ4HC_get_price(litlen, mlen); + } + + LZ4_LOG_PARSER("%d: Found2 mlen=%d best_mlen=%d off=%d price=%d litlen=%d price[%d]=%d\n", (int)(inr-source), mlen, best_mlen, matches[i].off, price, litlen, cur - litlen, opt[cur - litlen].price); + if (cur2 + mlen > last_pos || price < (size_t)opt[cur2 + mlen].price) { // || (((int)price == opt[cur2 + mlen].price) && (opt[cur2 + mlen-1].mlen == 1))) { + SET_PRICE(cur2 + mlen, mlen, matches[i].off, litlen, price); + } + mlen++; + } + } + } /* for (cur = 1; cur <= last_pos; cur++) */ + + best_mlen = opt[last_pos].mlen; + best_off = opt[last_pos].off; + cur = last_pos - best_mlen; + +encode: /* cur, last_pos, best_mlen, best_off have to be set */ + for (i = 1; i <= last_pos; i++) { + LZ4_LOG_PARSER("%d: price[%d/%d]=%d off=%d mlen=%d litlen=%d\n", (int)(ip-source+i), i, last_pos, opt[i].price, opt[i].off, opt[i].mlen, opt[i].litlen); + } + + LZ4_LOG_PARSER("%d: cur=%d/%d best_mlen=%d best_off=%d\n", (int)(ip-source+cur), cur, last_pos, best_mlen, best_off); + + opt[0].mlen = 1; + while (1) { + mlen = opt[cur].mlen; + offset = opt[cur].off; + opt[cur].mlen = (int)best_mlen; + opt[cur].off = (int)best_off; + best_mlen = mlen; + best_off = offset; + if (mlen > cur) break; + cur -= mlen; + } + + for (i = 0; i <= last_pos;) { + LZ4_LOG_PARSER("%d: price2[%d/%d]=%d off=%d mlen=%d litlen=%d\n", (int)(ip-source+i), i, last_pos, opt[i].price, opt[i].off, opt[i].mlen, opt[i].litlen); + i += opt[i].mlen; + } + + cur = 0; + while (cur < last_pos) { + LZ4_LOG_PARSER("%d: price3[%d/%d]=%d off=%d mlen=%d litlen=%d\n", (int)(ip-source+cur), cur, last_pos, opt[cur].price, opt[cur].off, opt[cur].mlen, opt[cur].litlen); + mlen = opt[cur].mlen; + if (mlen == 1) { ip++; cur++; continue; } + offset = opt[cur].off; + cur += mlen; + + LZ4_LOG_ENCODE("%d: ENCODE literals=%d off=%d mlen=%d ", (int)(ip-(const BYTE*)source), (int)(ip-anchor), (int)(offset), (int)mlen); + res = LZ4HC_encodeSequence(&ip, &op, &anchor, (int)mlen, ip - offset, limit, oend); + LZ4_LOG_ENCODE("out=%d\n", (int)((char*)op - dest)); + + if (res) return 0; + + LZ4_LOG_PARSER("%d: offset=%d\n", (int)(ip-source), offset); + } + } + + /* Encode Last Literals */ + { int lastRun = (int)(iend - anchor); + if ((limit) && (((char*)op - dest) + lastRun + 1 + ((lastRun+255-RUN_MASK)/255) > (U32)maxOutputSize)) return 0; /* Check output limit */ + if (lastRun>=(int)RUN_MASK) { *op++=(RUN_MASK<<ML_BITS); lastRun-=RUN_MASK; for(; lastRun > 254 ; lastRun-=255) *op++ = 255; *op++ = (BYTE) lastRun; } + else *op++ = (BYTE)(lastRun<<ML_BITS); + LZ4_LOG_ENCODE("%d: ENCODE_LAST literals=%d out=%d\n", (int)(ip-(const BYTE*)source), (int)(iend-anchor), (int)((char*)op-dest)); + memcpy(op, anchor, iend - anchor); + op += iend-anchor; + } + + /* End */ + return (int) ((char*)op-dest); +} diff --git a/programs/lz4io.c b/programs/lz4io.c index bc2ba95..46daaf7 100644 --- a/programs/lz4io.c +++ b/programs/lz4io.c @@ -591,12 +591,15 @@ int LZ4IO_compressMultipleFilenames(const char** inFileNamesTable, int ifntSize, char* dstFileName = (char*)malloc(FNSPACE); size_t ofnSize = FNSPACE; const size_t suffixSize = strlen(suffix); - cRess_t const ress = LZ4IO_createCResources(); + cRess_t ress; + + if (dstFileName == NULL) return ifntSize; /* not enough memory */ + ress = LZ4IO_createCResources(); /* loop on each file */ for (i=0; i<ifntSize; i++) { size_t const ifnSize = strlen(inFileNamesTable[i]); - if (ofnSize <= ifnSize+suffixSize+1) { free(dstFileName); ofnSize = ifnSize + 20; dstFileName = (char*)malloc(ofnSize); } + if (ofnSize <= ifnSize+suffixSize+1) { free(dstFileName); ofnSize = ifnSize + 20; dstFileName = (char*)malloc(ofnSize); if (dstFileName==NULL) { LZ4IO_freeCResources(ress); return ifntSize; } } strcpy(dstFileName, inFileNamesTable[i]); strcat(dstFileName, suffix); @@ -1022,7 +1025,7 @@ int LZ4IO_decompressMultipleFilenames(const char** inFileNamesTable, int ifntSiz size_t const suffixSize = strlen(suffix); dRess_t ress = LZ4IO_createDResources(); - if (outFileName==NULL) exit(1); /* not enough memory */ + if (outFileName==NULL) return ifntSize; /* not enough memory */ ress.dstFile = LZ4IO_openDstFile(stdoutmark); for (i=0; i<ifntSize; i++) { @@ -1032,7 +1035,7 @@ int LZ4IO_decompressMultipleFilenames(const char** inFileNamesTable, int ifntSiz missingFiles += LZ4IO_decompressSrcFile(ress, inFileNamesTable[i], stdoutmark); continue; } - if (ofnSize <= ifnSize-suffixSize+1) { free(outFileName); ofnSize = ifnSize + 20; outFileName = (char*)malloc(ofnSize); if (outFileName==NULL) exit(1); } + if (ofnSize <= ifnSize-suffixSize+1) { free(outFileName); ofnSize = ifnSize + 20; outFileName = (char*)malloc(ofnSize); if (outFileName==NULL) return ifntSize; } if (ifnSize <= suffixSize || strcmp(suffixPtr, suffix) != 0) { DISPLAYLEVEL(1, "File extension doesn't match expected LZ4_EXTENSION (%4s); will not process file: %s\n", suffix, inFileNamesTable[i]); skippedFiles++; |