From 1c80b9af4edf94f93582d40bae0856d13eacbf11 Mon Sep 17 00:00:00 2001 From: Przemyslaw Skibinski Date: Wed, 28 Dec 2016 15:18:19 +0100 Subject: LZ4HC_getSearchNum --- lib/lz4hc.c | 16 ++++++++++++++-- lib/lz4opt.h | 18 +++++++++++------- tests/fuzzer.c | 2 +- 3 files changed, 26 insertions(+), 10 deletions(-) diff --git a/lib/lz4hc.c b/lib/lz4hc.c index 3097df2..8ca5442 100644 --- a/lib/lz4hc.c +++ b/lib/lz4hc.c @@ -486,6 +486,14 @@ _Search3: return (int) (((char*)op)-dest); } +static int LZ4HC_getSearchNum(int compressionLevel) +{ + switch (compressionLevel) { + default: return 0; /* unused */ + case 11: return 128; + case 12: return 1<<10; + } +} static int LZ4HC_compress_generic ( LZ4HC_CCtx_internal* const ctx, @@ -497,13 +505,14 @@ static int LZ4HC_compress_generic ( limitedOutput_directive limit ) { + // printf("LZ4HC_compress_generic inputSize=%d compressionLevel=%d\n", inputSize, compressionLevel); if (compressionLevel < 1) compressionLevel = LZ4HC_CLEVEL_DEFAULT; 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); + case 11: ctx->searchNum = LZ4HC_getSearchNum(compressionLevel); 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); + case 12: ctx->searchNum = LZ4HC_getSearchNum(compressionLevel); 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); @@ -554,11 +563,13 @@ void LZ4_resetStreamHC (LZ4_streamHC_t* LZ4_streamHCPtr, int compressionLevel) LZ4_STATIC_ASSERT(sizeof(LZ4HC_CCtx_internal) <= sizeof(size_t) * LZ4_STREAMHCSIZE_SIZET); /* if compilation fails here, LZ4_STREAMHCSIZE must be increased */ LZ4_streamHCPtr->internal_donotuse.base = NULL; LZ4_streamHCPtr->internal_donotuse.compressionLevel = (unsigned)compressionLevel; + LZ4_streamHCPtr->internal_donotuse.searchNum = LZ4HC_getSearchNum(compressionLevel); } int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int dictSize) { LZ4HC_CCtx_internal* ctxPtr = &LZ4_streamHCPtr->internal_donotuse; + // printf("LZ4_loadDictHC dictSize=%d\n", (int)dictSize); if (dictSize > 64 KB) { dictionary += dictSize - 64 KB; dictSize = 64 KB; @@ -577,6 +588,7 @@ int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal* ctxPtr, const BYTE* newBlock) { + // printf("LZ4HC_setExternalDict\n"); if (ctxPtr->compressionLevel >= LZ4HC_CLEVEL_OPT_MIN) LZ4HC_updateBinTree(ctxPtr, ctxPtr->end - MFLIMIT, ctxPtr->end - LASTLITERALS); else diff --git a/lib/lz4opt.h b/lib/lz4opt.h index 1633453..041df52 100644 --- a/lib/lz4opt.h +++ b/lib/lz4opt.h @@ -37,6 +37,7 @@ #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_LOG_TREE(fmt, ...) //printf(fmt, __VA_ARGS__) #define LZ4_OPT_NUM (1<<12) @@ -106,6 +107,8 @@ FORCE_INLINE int LZ4HC_BinTree_InsertAndGetAllMatches ( size_t matchLength = 0; U32* HashPos; + LZ4_LOG_TREE("LZ4HC_BinTree_InsertAndGetAllMatches nbAttempts=%d\n", nbAttempts); + if (ip + MINMATCH > iHighLimit) return 1; /* HC4 match finder */ @@ -117,6 +120,7 @@ FORCE_INLINE int LZ4HC_BinTree_InsertAndGetAllMatches ( ptr1 = &DELTANEXTMAXD(current*2); delta0 = delta1 = (U16)(current - matchIndex); + LZ4_LOG_TREE("matchIndex[%u] current[%u] lowLimit[%u]\n", matchIndex, current, lowLimit); while ((matchIndex < current) && (matchIndex>=lowLimit) && (nbAttempts)) { nbAttempts--; if (matchIndex >= dictLimit) { @@ -141,29 +145,30 @@ FORCE_INLINE int LZ4HC_BinTree_InsertAndGetAllMatches ( matches[mnum].len = (int)matchLength; mnum++; } - if (best_mlen > LZ4_OPT_NUM) break; + if (best_mlen > LZ4_OPT_NUM) { LZ4_LOG_TREE("best_mlen > LZ4_OPT_NUM\n"); 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 */ + { LZ4_LOG_TREE("ip+matchLength > iHighLimit\n"); 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; + if (*ptr0 == (U16)-1) { LZ4_LOG_TREE("*ptr0 == (U16)-1"); break; } delta0 = *ptr0; delta1 += delta0; matchIndex -= delta0; } else { *ptr1 = delta1; ptr1 = &DELTANEXTMAXD(matchIndex*2+1); - if (*ptr1 == (U16)-1) break; + if (*ptr1 == (U16)-1) { LZ4_LOG_TREE("*ptr1 == (U16)-1\n"); break; } delta1 = *ptr1; delta0 += delta1; matchIndex -= delta1; } } + LZ4_LOG_TREE("nbAttempts=%d mnum=%d\n", nbAttempts, mnum); *ptr0 = (U16)-1; *ptr1 = (U16)-1; if (matchNum) *matchNum = mnum; @@ -178,7 +183,7 @@ FORCE_INLINE void LZ4HC_updateBinTree(LZ4HC_CCtx_internal* ctx, const BYTE* cons const BYTE* const base = ctx->base; const U32 target = (U32)(ip - base); U32 idx = ctx->nextToUpdateBT; - + LZ4_LOG_TREE("LZ4HC_updateBinTree %d->%d nbAttempts=%d\n", idx, target, ctx->searchNum); while(idx < target) idx += LZ4HC_BinTree_InsertAndGetAllMatches(ctx, base+idx, iHighLimit, 8, NULL, NULL); } @@ -206,7 +211,7 @@ FORCE_INLINE int LZ4HC_BinTree_GetAllMatches ( 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-(const BYTE*)source), (int)(pos), (int)last_pos, opt[pos].price, opt[pos].litlen, opt[pos].mlen, opt[pos].off); \ + LZ4_LOG_PARSER("%u: SET price[%d/%d]=%d litlen=%d len=%d off=%d\n", (int)(inr-(const BYTE*)source), (int)(pos), (int)last_pos, opt[pos].price, opt[pos].litlen, opt[pos].mlen, opt[pos].off); \ } @@ -330,7 +335,6 @@ static int LZ4HC_compress_optimal ( price = opt[cur2].price + LZ4HC_sequencePrice(litlen, mlen); } - LZ4_LOG_PARSER("%d: Found2 mlen=%d best_mlen=%d off=%d price=%d litlen=%d price[%d]=%d\n", (int)(inr-(const BYTE*)source), (int)mlen, (int)best_mlen, matches[i].off, (int)price, (int)litlen, (int)(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); } diff --git a/tests/fuzzer.c b/tests/fuzzer.c index dbc15ec..fb918b4 100644 --- a/tests/fuzzer.c +++ b/tests/fuzzer.c @@ -601,7 +601,7 @@ static int FUZ_test(U32 seed, U32 nbCycles, const U32 startCycle, const double c FUZ_DISPLAYTEST; LZ4_loadDictHC(&LZ4dictHC, dict, dictSize); ret = LZ4_compress_HC_continue(&LZ4dictHC, block, compressedBuffer, blockSize, blockContinueCompressedSize-1); - FUZ_CHECKTEST(ret>0, "LZ4_compressHC_limitedOutput_continue using ExtDict should fail : one missing byte for output buffer"); + FUZ_CHECKTEST(ret>0, "LZ4_compressHC_limitedOutput_continue using ExtDict should fail : one missing byte for output buffer (%i != %i)", ret, blockContinueCompressedSize); FUZ_DISPLAYTEST; LZ4_loadDictHC(&LZ4dictHC, dict, dictSize); -- cgit v0.12