added ZSTD_btopt2 strategy
diff --git a/lib/compress/zstd_compress.c b/lib/compress/zstd_compress.c
index 21a1ffb..f444a7e 100644
--- a/lib/compress/zstd_compress.c
+++ b/lib/compress/zstd_compress.c
@@ -137,7 +137,7 @@
U32 const searchLengthMax = (cParams.strategy == ZSTD_fast) ? ZSTD_SEARCHLENGTH_MAX : ZSTD_SEARCHLENGTH_MAX-1;
CLAMPCHECK(cParams.searchLength, searchLengthMin, searchLengthMax); }
CLAMPCHECK(cParams.targetLength, ZSTD_TARGETLENGTH_MIN, ZSTD_TARGETLENGTH_MAX);
- if ((U32)(cParams.strategy) > (U32)ZSTD_btopt) return ERROR(compressionParameter_unsupported);
+ if ((U32)(cParams.strategy) > (U32)ZSTD_btopt2) return ERROR(compressionParameter_unsupported);
return 0;
}
@@ -160,7 +160,7 @@
if (cPar.windowLog > srcLog) cPar.windowLog = srcLog;
} }
if (cPar.hashLog > cPar.windowLog) cPar.hashLog = cPar.windowLog;
- { U32 const btPlus = (cPar.strategy == ZSTD_btlazy2) | (cPar.strategy == ZSTD_btopt);
+ { U32 const btPlus = (cPar.strategy == ZSTD_btlazy2) | (cPar.strategy == ZSTD_btopt) | (cPar.strategy == ZSTD_btopt2);
U32 const maxChainLog = cPar.windowLog+btPlus;
if (cPar.chainLog > maxChainLog) cPar.chainLog = maxChainLog; } /* <= ZSTD_CHAINLOG_MAX */
@@ -186,7 +186,7 @@
size_t const optSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits))*sizeof(U32)
+ (ZSTD_OPT_NUM+1)*(sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t));
size_t const neededSpace = tableSpace + (256*sizeof(U32)) /* huffTable */ + tokenSpace
- + ((cParams.strategy == ZSTD_btopt) ? optSpace : 0);
+ + (((cParams.strategy == ZSTD_btopt) || (cParams.strategy == ZSTD_btopt2)) ? optSpace : 0);
return sizeof(ZSTD_CCtx) + neededSpace;
}
@@ -246,7 +246,7 @@
{ size_t const optSpace = ((MaxML+1) + (MaxLL+1) + (MaxOff+1) + (1<<Litbits))*sizeof(U32)
+ (ZSTD_OPT_NUM+1)*(sizeof(ZSTD_match_t) + sizeof(ZSTD_optimal_t));
size_t const neededSpace = tableSpace + (256*sizeof(U32)) /* huffTable */ + tokenSpace
- + ((params.cParams.strategy == ZSTD_btopt) ? optSpace : 0);
+ + (((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) ? optSpace : 0);
if (zc->workSpaceSize < neededSpace) {
ZSTD_free(zc->workSpace, zc->customMem);
zc->workSpace = ZSTD_malloc(neededSpace, zc->customMem);
@@ -276,7 +276,7 @@
zc->frameContentSize = frameContentSize;
{ int i; for (i=0; i<ZSTD_REP_NUM; i++) zc->rep[i] = repStartValue[i]; }
- if (params.cParams.strategy == ZSTD_btopt) {
+ if ((params.cParams.strategy == ZSTD_btopt) || (params.cParams.strategy == ZSTD_btopt2)) {
zc->seqStore.litFreq = (U32*)ptr;
zc->seqStore.litLengthFreq = zc->seqStore.litFreq + (1<<Litbits);
zc->seqStore.matchLengthFreq = zc->seqStore.litLengthFreq + (MaxLL+1);
@@ -2170,7 +2170,17 @@
static void ZSTD_compressBlock_btopt(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
{
#ifdef ZSTD_OPT_H_91842398743
- ZSTD_compressBlock_opt_generic(ctx, src, srcSize);
+ ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 0);
+#else
+ (void)ctx; (void)src; (void)srcSize;
+ return;
+#endif
+}
+
+static void ZSTD_compressBlock_btopt2(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
+{
+#ifdef ZSTD_OPT_H_91842398743
+ ZSTD_compressBlock_opt_generic(ctx, src, srcSize, 1);
#else
(void)ctx; (void)src; (void)srcSize;
return;
@@ -2180,7 +2190,17 @@
static void ZSTD_compressBlock_btopt_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
{
#ifdef ZSTD_OPT_H_91842398743
- ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize);
+ ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 0);
+#else
+ (void)ctx; (void)src; (void)srcSize;
+ return;
+#endif
+}
+
+static void ZSTD_compressBlock_btopt2_extDict(ZSTD_CCtx* ctx, const void* src, size_t srcSize)
+{
+#ifdef ZSTD_OPT_H_91842398743
+ ZSTD_compressBlock_opt_extDict_generic(ctx, src, srcSize, 1);
#else
(void)ctx; (void)src; (void)srcSize;
return;
@@ -2192,9 +2212,9 @@
static ZSTD_blockCompressor ZSTD_selectBlockCompressor(ZSTD_strategy strat, int extDict)
{
- static const ZSTD_blockCompressor blockCompressor[2][7] = {
- { ZSTD_compressBlock_fast, ZSTD_compressBlock_doubleFast, ZSTD_compressBlock_greedy, ZSTD_compressBlock_lazy, ZSTD_compressBlock_lazy2, ZSTD_compressBlock_btlazy2, ZSTD_compressBlock_btopt },
- { ZSTD_compressBlock_fast_extDict, ZSTD_compressBlock_doubleFast_extDict, ZSTD_compressBlock_greedy_extDict, ZSTD_compressBlock_lazy_extDict,ZSTD_compressBlock_lazy2_extDict, ZSTD_compressBlock_btlazy2_extDict, ZSTD_compressBlock_btopt_extDict }
+ static const ZSTD_blockCompressor blockCompressor[2][8] = {
+ { ZSTD_compressBlock_fast, ZSTD_compressBlock_doubleFast, ZSTD_compressBlock_greedy, ZSTD_compressBlock_lazy, ZSTD_compressBlock_lazy2, ZSTD_compressBlock_btlazy2, ZSTD_compressBlock_btopt, ZSTD_compressBlock_btopt2 },
+ { ZSTD_compressBlock_fast_extDict, ZSTD_compressBlock_doubleFast_extDict, ZSTD_compressBlock_greedy_extDict, ZSTD_compressBlock_lazy_extDict,ZSTD_compressBlock_lazy2_extDict, ZSTD_compressBlock_btlazy2_extDict, ZSTD_compressBlock_btopt_extDict, ZSTD_compressBlock_btopt2_extDict }
};
return blockCompressor[extDict][(U32)strat];
@@ -2247,7 +2267,7 @@
/* preemptive overflow correction */
if (cctx->lowLimit > (1<<30)) {
- U32 const btplus = (cctx->params.cParams.strategy == ZSTD_btlazy2) | (cctx->params.cParams.strategy == ZSTD_btopt);
+ U32 const btplus = (cctx->params.cParams.strategy == ZSTD_btlazy2) | (cctx->params.cParams.strategy == ZSTD_btopt) | (cctx->params.cParams.strategy == ZSTD_btopt2);
U32 const chainMask = (1 << (cctx->params.cParams.chainLog - btplus)) - 1;
U32 const supLog = MAX(cctx->params.cParams.chainLog, 17 /* blockSize */);
U32 const newLowLimit = (cctx->lowLimit & chainMask) + (1 << supLog); /* preserve position % chainSize, ensure current-repcode doesn't underflow */
@@ -2436,6 +2456,7 @@
case ZSTD_btlazy2:
case ZSTD_btopt:
+ case ZSTD_btopt2:
ZSTD_updateTree(zc, iend-HASH_READ_SIZE, iend, 1 << zc->params.cParams.searchLog, zc->params.cParams.searchLength);
break;
@@ -3066,9 +3087,9 @@
{ 23, 21, 22, 4, 5, 24, ZSTD_btopt }, /* level 17 */
{ 23, 23, 22, 6, 5, 32, ZSTD_btopt }, /* level 18 */
{ 23, 23, 22, 6, 3, 48, ZSTD_btopt }, /* level 19 */
- { 25, 25, 23, 7, 3, 64, ZSTD_btopt }, /* level 20 */
- { 26, 26, 23, 7, 3,256, ZSTD_btopt }, /* level 21 */
- { 27, 27, 25, 9, 3,512, ZSTD_btopt }, /* level 22 */
+ { 25, 25, 23, 7, 3, 64, ZSTD_btopt2 }, /* level 20 */
+ { 26, 26, 23, 7, 3,256, ZSTD_btopt2 }, /* level 21 */
+ { 27, 27, 25, 9, 3,512, ZSTD_btopt2 }, /* level 22 */
},
{ /* for srcSize <= 256 KB */
/* W, C, H, S, L, T, strat */
@@ -3092,9 +3113,9 @@
{ 18, 19, 18, 8, 3, 64, ZSTD_btopt }, /* level 17.*/
{ 18, 19, 18, 9, 3,128, ZSTD_btopt }, /* level 18.*/
{ 18, 19, 18, 10, 3,256, ZSTD_btopt }, /* level 19.*/
- { 18, 19, 18, 11, 3,512, ZSTD_btopt }, /* level 20.*/
- { 18, 19, 18, 12, 3,512, ZSTD_btopt }, /* level 21.*/
- { 18, 19, 18, 13, 3,512, ZSTD_btopt }, /* level 22.*/
+ { 18, 19, 18, 11, 3,512, ZSTD_btopt2 }, /* level 20.*/
+ { 18, 19, 18, 12, 3,512, ZSTD_btopt2 }, /* level 21.*/
+ { 18, 19, 18, 13, 3,512, ZSTD_btopt2 }, /* level 22.*/
},
{ /* for srcSize <= 128 KB */
/* W, C, H, S, L, T, strat */
@@ -3118,9 +3139,9 @@
{ 17, 18, 17, 7, 3, 64, ZSTD_btopt }, /* level 17.*/
{ 17, 18, 17, 7, 3,256, ZSTD_btopt }, /* level 18.*/
{ 17, 18, 17, 8, 3,256, ZSTD_btopt }, /* level 19.*/
- { 17, 18, 17, 9, 3,256, ZSTD_btopt }, /* level 20.*/
- { 17, 18, 17, 10, 3,256, ZSTD_btopt }, /* level 21.*/
- { 17, 18, 17, 11, 3,512, ZSTD_btopt }, /* level 22.*/
+ { 17, 18, 17, 9, 3,256, ZSTD_btopt2 }, /* level 20.*/
+ { 17, 18, 17, 10, 3,256, ZSTD_btopt2 }, /* level 21.*/
+ { 17, 18, 17, 11, 3,512, ZSTD_btopt2 }, /* level 22.*/
},
{ /* for srcSize <= 16 KB */
/* W, C, H, S, L, T, strat */
@@ -3144,9 +3165,9 @@
{ 14, 15, 15, 6, 3,128, ZSTD_btopt }, /* level 17.*/
{ 14, 15, 15, 6, 3,256, ZSTD_btopt }, /* level 18.*/
{ 14, 15, 15, 7, 3,256, ZSTD_btopt }, /* level 19.*/
- { 14, 15, 15, 8, 3,256, ZSTD_btopt }, /* level 20.*/
- { 14, 15, 15, 9, 3,256, ZSTD_btopt }, /* level 21.*/
- { 14, 15, 15, 10, 3,256, ZSTD_btopt }, /* level 22.*/
+ { 14, 15, 15, 8, 3,256, ZSTD_btopt2 }, /* level 20.*/
+ { 14, 15, 15, 9, 3,256, ZSTD_btopt2 }, /* level 21.*/
+ { 14, 15, 15, 10, 3,256, ZSTD_btopt2 }, /* level 22.*/
},
};
diff --git a/lib/compress/zstd_opt.h b/lib/compress/zstd_opt.h
index 5e4cb7c..90d511c 100644
--- a/lib/compress/zstd_opt.h
+++ b/lib/compress/zstd_opt.h
@@ -121,12 +121,14 @@
}
-FORCE_INLINE U32 ZSTD_getPrice(seqStore_t* seqStorePtr, U32 litLength, const BYTE* literals, U32 offset, U32 matchLength)
+FORCE_INLINE U32 ZSTD_getPrice(seqStore_t* seqStorePtr, U32 litLength, const BYTE* literals, U32 offset, U32 matchLength, const int ultra)
{
/* offset */
BYTE const offCode = (BYTE)ZSTD_highbit32(offset+1);
U32 price = offCode + seqStorePtr->log2offCodeSum - ZSTD_highbit32(seqStorePtr->offCodeFreq[offCode]+1);
+ if (!ultra && offCode >= 20) price += (offCode-19)*2;
+
/* match Length */
{ const BYTE ML_deltaCode = 36;
const BYTE mlCode = (matchLength>127) ? (BYTE)ZSTD_highbit32(matchLength) + ML_deltaCode : ML_Code[matchLength];
@@ -376,7 +378,7 @@
*********************************/
FORCE_INLINE
void ZSTD_compressBlock_opt_generic(ZSTD_CCtx* ctx,
- const void* src, size_t srcSize)
+ const void* src, size_t srcSize, const int ultra)
{
seqStore_t* seqStorePtr = &(ctx->seqStore);
const BYTE* const istart = (const BYTE*)src;
@@ -424,7 +426,7 @@
}
best_off = i - (ip == anchor);
do {
- price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH);
+ price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
if (mlen > last_pos || price < opt[mlen].price)
SET_PRICE(mlen, mlen, i, litlen, price); /* note : macro modifies last_pos */
mlen--;
@@ -449,7 +451,7 @@
mlen = (u>0) ? matches[u-1].len+1 : best_mlen;
best_mlen = matches[u].len;
while (mlen <= best_mlen) {
- price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH);
+ price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);
if (mlen > last_pos || price < opt[mlen].price)
SET_PRICE(mlen, mlen, matches[u].off, litlen, price); /* note : macro modifies last_pos */
mlen++;
@@ -516,12 +518,12 @@
if (opt[cur].mlen == 1) {
litlen = opt[cur].litlen;
if (cur > litlen) {
- price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr-litlen, best_off, mlen - MINMATCH);
+ price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr-litlen, best_off, mlen - MINMATCH, ultra);
} else
- price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH);
+ price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
} else {
litlen = 0;
- price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH);
+ price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH, ultra);
}
if (cur + mlen > last_pos || price <= opt[cur + mlen].price)
@@ -548,12 +550,12 @@
if (opt[cur].mlen == 1) {
litlen = opt[cur].litlen;
if (cur > litlen)
- price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip+cur-litlen, matches[u].off-1, mlen - MINMATCH);
+ price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip+cur-litlen, matches[u].off-1, mlen - MINMATCH, ultra);
else
- price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH);
+ price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);
} else {
litlen = 0;
- price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off-1, mlen - MINMATCH);
+ price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off-1, mlen - MINMATCH, ultra);
}
if (cur + mlen > last_pos || (price < opt[cur + mlen].price))
@@ -625,7 +627,7 @@
FORCE_INLINE
void ZSTD_compressBlock_opt_extDict_generic(ZSTD_CCtx* ctx,
- const void* src, size_t srcSize)
+ const void* src, size_t srcSize, const int ultra)
{
seqStore_t* seqStorePtr = &(ctx->seqStore);
const BYTE* const istart = (const BYTE*)src;
@@ -688,7 +690,7 @@
best_off = i - (ip==anchor);
litlen = opt[0].litlen;
do {
- price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH);
+ price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
if (mlen > last_pos || price < opt[mlen].price)
SET_PRICE(mlen, mlen, i, litlen, price); /* note : macro modifies last_pos */
mlen--;
@@ -718,7 +720,7 @@
best_mlen = matches[u].len;
litlen = opt[0].litlen;
while (mlen <= best_mlen) {
- price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH);
+ price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);
if (mlen > last_pos || price < opt[mlen].price)
SET_PRICE(mlen, mlen, matches[u].off, litlen, price);
mlen++;
@@ -788,12 +790,12 @@
if (opt[cur].mlen == 1) {
litlen = opt[cur].litlen;
if (cur > litlen) {
- price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr-litlen, best_off, mlen - MINMATCH);
+ price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, inr-litlen, best_off, mlen - MINMATCH, ultra);
} else
- price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH);
+ price = ZSTD_getPrice(seqStorePtr, litlen, anchor, best_off, mlen - MINMATCH, ultra);
} else {
litlen = 0;
- price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH);
+ price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, best_off, mlen - MINMATCH, ultra);
}
if (cur + mlen > last_pos || price <= opt[cur + mlen].price)
@@ -820,12 +822,12 @@
if (opt[cur].mlen == 1) {
litlen = opt[cur].litlen;
if (cur > litlen)
- price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip+cur-litlen, matches[u].off-1, mlen - MINMATCH);
+ price = opt[cur - litlen].price + ZSTD_getPrice(seqStorePtr, litlen, ip+cur-litlen, matches[u].off-1, mlen - MINMATCH, ultra);
else
- price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH);
+ price = ZSTD_getPrice(seqStorePtr, litlen, anchor, matches[u].off-1, mlen - MINMATCH, ultra);
} else {
litlen = 0;
- price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off-1, mlen - MINMATCH);
+ price = opt[cur].price + ZSTD_getPrice(seqStorePtr, 0, NULL, matches[u].off-1, mlen - MINMATCH, ultra);
}
if (cur + mlen > last_pos || (price < opt[cur + mlen].price))
diff --git a/lib/zstd.h b/lib/zstd.h
index 1b6665c..471cd74 100644
--- a/lib/zstd.h
+++ b/lib/zstd.h
@@ -340,7 +340,7 @@
/*--- Advanced types ---*/
-typedef enum { ZSTD_fast, ZSTD_dfast, ZSTD_greedy, ZSTD_lazy, ZSTD_lazy2, ZSTD_btlazy2, ZSTD_btopt } ZSTD_strategy; /* from faster to stronger */
+typedef enum { ZSTD_fast, ZSTD_dfast, ZSTD_greedy, ZSTD_lazy, ZSTD_lazy2, ZSTD_btlazy2, ZSTD_btopt, ZSTD_btopt2 } ZSTD_strategy; /* from faster to stronger */
typedef struct {
unsigned windowLog; /**< largest match distance : larger == more compression, more memory needed during decompression */
diff --git a/tests/paramgrill.c b/tests/paramgrill.c
index f253fa3..5eabcba 100644
--- a/tests/paramgrill.c
+++ b/tests/paramgrill.c
@@ -302,7 +302,8 @@
"ZSTD_lazy ",
"ZSTD_lazy2 ",
"ZSTD_btlazy2",
- "ZSTD_btopt " };
+ "ZSTD_btopt ",
+ "ZSTD_btopt2 "};
static void BMK_printWinner(FILE* f, U32 cLevel, BMK_result_t result, ZSTD_compressionParameters params, size_t srcSize)
{
@@ -442,7 +443,7 @@
g_params.chainLog = 0, g_params.searchLog = 0;
if (params.strategy == ZSTD_dfast)
g_params.searchLog = 0;
- if (params.strategy != ZSTD_btopt )
+ if (params.strategy != ZSTD_btopt && params.strategy != ZSTD_btopt2)
g_params.targetLength = 0;
return &g_params;
}
@@ -548,7 +549,7 @@
p.windowLog = FUZ_rand(&g_rand) % (ZSTD_WINDOWLOG_MAX+1 - ZSTD_WINDOWLOG_MIN) + ZSTD_WINDOWLOG_MIN;
p.searchLength=FUZ_rand(&g_rand) % (ZSTD_SEARCHLENGTH_MAX+1 - ZSTD_SEARCHLENGTH_MIN) + ZSTD_SEARCHLENGTH_MIN;
p.targetLength=FUZ_rand(&g_rand) % (ZSTD_TARGETLENGTH_MAX+1 - ZSTD_TARGETLENGTH_MIN) + ZSTD_TARGETLENGTH_MIN;
- p.strategy = (ZSTD_strategy) (FUZ_rand(&g_rand) % (ZSTD_btopt +1));
+ p.strategy = (ZSTD_strategy) (FUZ_rand(&g_rand) % (ZSTD_btopt2 +1));
validated = !ZSTD_isError(ZSTD_checkCParams(p));
}
return p;