in cdk/extra/lz4/lib/lz4hc.c [1330:1631]
static int LZ4HC_compress_optimal ( LZ4HC_CCtx_internal* ctx,
const char* const source,
char* dst,
int* srcSizePtr,
int dstCapacity,
int const nbSearches,
size_t sufficient_len,
const limitedOutput_directive limit,
int const fullUpdate,
const dictCtx_directive dict,
const HCfavor_e favorDecSpeed)
{
int retval = 0;
#define TRAILING_LITERALS 3
#if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
LZ4HC_optimal_t* const opt = (LZ4HC_optimal_t*)ALLOC(sizeof(LZ4HC_optimal_t) * (LZ4_OPT_NUM + TRAILING_LITERALS));
#else
LZ4HC_optimal_t opt[LZ4_OPT_NUM + TRAILING_LITERALS]; /* ~64 KB, which is a bit large for stack... */
#endif
const BYTE* ip = (const BYTE*) source;
const BYTE* anchor = ip;
const BYTE* const iend = ip + *srcSizePtr;
const BYTE* const mflimit = iend - MFLIMIT;
const BYTE* const matchlimit = iend - LASTLITERALS;
BYTE* op = (BYTE*) dst;
BYTE* opSaved = (BYTE*) dst;
BYTE* oend = op + dstCapacity;
int ovml = MINMATCH; /* overflow - last sequence */
const BYTE* ovref = NULL;
/* init */
#if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
if (opt == NULL) goto _return_label;
#endif
DEBUGLOG(5, "LZ4HC_compress_optimal(dst=%p, dstCapa=%u)", dst, (unsigned)dstCapacity);
*srcSizePtr = 0;
if (limit == fillOutput) oend -= LASTLITERALS; /* Hack for support LZ4 format restriction */
if (sufficient_len >= LZ4_OPT_NUM) sufficient_len = LZ4_OPT_NUM-1;
/* Main Loop */
while (ip <= mflimit) {
int const llen = (int)(ip - anchor);
int best_mlen, best_off;
int cur, last_match_pos = 0;
LZ4HC_match_t const firstMatch = LZ4HC_FindLongerMatch(ctx, ip, matchlimit, MINMATCH-1, nbSearches, dict, favorDecSpeed);
if (firstMatch.len==0) { ip++; continue; }
if ((size_t)firstMatch.len > sufficient_len) {
/* good enough solution : immediate encoding */
int const firstML = firstMatch.len;
const BYTE* const matchPos = ip - firstMatch.off;
opSaved = op;
if ( LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), firstML, matchPos, limit, oend) ) { /* updates ip, op and anchor */
ovml = firstML;
ovref = matchPos;
goto _dest_overflow;
}
continue;
}
/* set prices for first positions (literals) */
{ int rPos;
for (rPos = 0 ; rPos < MINMATCH ; rPos++) {
int const cost = LZ4HC_literalsPrice(llen + rPos);
opt[rPos].mlen = 1;
opt[rPos].off = 0;
opt[rPos].litlen = llen + rPos;
opt[rPos].price = cost;
DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i) -- initial setup",
rPos, cost, opt[rPos].litlen);
} }
/* set prices using initial match */
{ int mlen = MINMATCH;
int const matchML = firstMatch.len; /* necessarily < sufficient_len < LZ4_OPT_NUM */
int const offset = firstMatch.off;
assert(matchML < LZ4_OPT_NUM);
for ( ; mlen <= matchML ; mlen++) {
int const cost = LZ4HC_sequencePrice(llen, mlen);
opt[mlen].mlen = mlen;
opt[mlen].off = offset;
opt[mlen].litlen = llen;
opt[mlen].price = cost;
DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i) -- initial setup",
mlen, cost, mlen);
} }
last_match_pos = firstMatch.len;
{ int addLit;
for (addLit = 1; addLit <= TRAILING_LITERALS; addLit ++) {
opt[last_match_pos+addLit].mlen = 1; /* literal */
opt[last_match_pos+addLit].off = 0;
opt[last_match_pos+addLit].litlen = addLit;
opt[last_match_pos+addLit].price = opt[last_match_pos].price + LZ4HC_literalsPrice(addLit);
DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i) -- initial setup",
last_match_pos+addLit, opt[last_match_pos+addLit].price, addLit);
} }
/* check further positions */
for (cur = 1; cur < last_match_pos; cur++) {
const BYTE* const curPtr = ip + cur;
LZ4HC_match_t newMatch;
if (curPtr > mflimit) break;
DEBUGLOG(7, "rPos:%u[%u] vs [%u]%u",
cur, opt[cur].price, opt[cur+1].price, cur+1);
if (fullUpdate) {
/* not useful to search here if next position has same (or lower) cost */
if ( (opt[cur+1].price <= opt[cur].price)
/* in some cases, next position has same cost, but cost rises sharply after, so a small match would still be beneficial */
&& (opt[cur+MINMATCH].price < opt[cur].price + 3/*min seq price*/) )
continue;
} else {
/* not useful to search here if next position has same (or lower) cost */
if (opt[cur+1].price <= opt[cur].price) continue;
}
DEBUGLOG(7, "search at rPos:%u", cur);
if (fullUpdate)
newMatch = LZ4HC_FindLongerMatch(ctx, curPtr, matchlimit, MINMATCH-1, nbSearches, dict, favorDecSpeed);
else
/* only test matches of minimum length; slightly faster, but misses a few bytes */
newMatch = LZ4HC_FindLongerMatch(ctx, curPtr, matchlimit, last_match_pos - cur, nbSearches, dict, favorDecSpeed);
if (!newMatch.len) continue;
if ( ((size_t)newMatch.len > sufficient_len)
|| (newMatch.len + cur >= LZ4_OPT_NUM) ) {
/* immediate encoding */
best_mlen = newMatch.len;
best_off = newMatch.off;
last_match_pos = cur + 1;
goto encode;
}
/* before match : set price with literals at beginning */
{ int const baseLitlen = opt[cur].litlen;
int litlen;
for (litlen = 1; litlen < MINMATCH; litlen++) {
int const price = opt[cur].price - LZ4HC_literalsPrice(baseLitlen) + LZ4HC_literalsPrice(baseLitlen+litlen);
int const pos = cur + litlen;
if (price < opt[pos].price) {
opt[pos].mlen = 1; /* literal */
opt[pos].off = 0;
opt[pos].litlen = baseLitlen+litlen;
opt[pos].price = price;
DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i)",
pos, price, opt[pos].litlen);
} } }
/* set prices using match at position = cur */
{ int const matchML = newMatch.len;
int ml = MINMATCH;
assert(cur + newMatch.len < LZ4_OPT_NUM);
for ( ; ml <= matchML ; ml++) {
int const pos = cur + ml;
int const offset = newMatch.off;
int price;
int ll;
DEBUGLOG(7, "testing price rPos %i (last_match_pos=%i)",
pos, last_match_pos);
if (opt[cur].mlen == 1) {
ll = opt[cur].litlen;
price = ((cur > ll) ? opt[cur - ll].price : 0)
+ LZ4HC_sequencePrice(ll, ml);
} else {
ll = 0;
price = opt[cur].price + LZ4HC_sequencePrice(0, ml);
}
assert((U32)favorDecSpeed <= 1);
if (pos > last_match_pos+TRAILING_LITERALS
|| price <= opt[pos].price - (int)favorDecSpeed) {
DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i)",
pos, price, ml);
assert(pos < LZ4_OPT_NUM);
if ( (ml == matchML) /* last pos of last match */
&& (last_match_pos < pos) )
last_match_pos = pos;
opt[pos].mlen = ml;
opt[pos].off = offset;
opt[pos].litlen = ll;
opt[pos].price = price;
} } }
/* complete following positions with literals */
{ int addLit;
for (addLit = 1; addLit <= TRAILING_LITERALS; addLit ++) {
opt[last_match_pos+addLit].mlen = 1; /* literal */
opt[last_match_pos+addLit].off = 0;
opt[last_match_pos+addLit].litlen = addLit;
opt[last_match_pos+addLit].price = opt[last_match_pos].price + LZ4HC_literalsPrice(addLit);
DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i)", last_match_pos+addLit, opt[last_match_pos+addLit].price, addLit);
} }
} /* for (cur = 1; cur <= last_match_pos; cur++) */
assert(last_match_pos < LZ4_OPT_NUM + TRAILING_LITERALS);
best_mlen = opt[last_match_pos].mlen;
best_off = opt[last_match_pos].off;
cur = last_match_pos - best_mlen;
encode: /* cur, last_match_pos, best_mlen, best_off must be set */
assert(cur < LZ4_OPT_NUM);
assert(last_match_pos >= 1); /* == 1 when only one candidate */
DEBUGLOG(6, "reverse traversal, looking for shortest path (last_match_pos=%i)", last_match_pos);
{ int candidate_pos = cur;
int selected_matchLength = best_mlen;
int selected_offset = best_off;
while (1) { /* from end to beginning */
int const next_matchLength = opt[candidate_pos].mlen; /* can be 1, means literal */
int const next_offset = opt[candidate_pos].off;
DEBUGLOG(7, "pos %i: sequence length %i", candidate_pos, selected_matchLength);
opt[candidate_pos].mlen = selected_matchLength;
opt[candidate_pos].off = selected_offset;
selected_matchLength = next_matchLength;
selected_offset = next_offset;
if (next_matchLength > candidate_pos) break; /* last match elected, first match to encode */
assert(next_matchLength > 0); /* can be 1, means literal */
candidate_pos -= next_matchLength;
} }
/* encode all recorded sequences in order */
{ int rPos = 0; /* relative position (to ip) */
while (rPos < last_match_pos) {
int const ml = opt[rPos].mlen;
int const offset = opt[rPos].off;
if (ml == 1) { ip++; rPos++; continue; } /* literal; note: can end up with several literals, in which case, skip them */
rPos += ml;
assert(ml >= MINMATCH);
assert((offset >= 1) && (offset <= LZ4_DISTANCE_MAX));
opSaved = op;
if ( LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), ml, ip - offset, limit, oend) ) { /* updates ip, op and anchor */
ovml = ml;
ovref = ip - offset;
goto _dest_overflow;
} } }
} /* while (ip <= mflimit) */
_last_literals:
/* Encode Last Literals */
{ size_t lastRunSize = (size_t)(iend - anchor); /* literals */
size_t llAdd = (lastRunSize + 255 - RUN_MASK) / 255;
size_t const totalSize = 1 + llAdd + lastRunSize;
if (limit == fillOutput) oend += LASTLITERALS; /* restore correct value */
if (limit && (op + totalSize > oend)) {
if (limit == limitedOutput) { /* Check output limit */
retval = 0;
goto _return_label;
}
/* adapt lastRunSize to fill 'dst' */
lastRunSize = (size_t)(oend - op) - 1 /*token*/;
llAdd = (lastRunSize + 256 - RUN_MASK) / 256;
lastRunSize -= llAdd;
}
DEBUGLOG(6, "Final literal run : %i literals", (int)lastRunSize);
ip = anchor + lastRunSize; /* can be != iend if limit==fillOutput */
if (lastRunSize >= RUN_MASK) {
size_t accumulator = lastRunSize - RUN_MASK;
*op++ = (RUN_MASK << ML_BITS);
for(; accumulator >= 255 ; accumulator -= 255) *op++ = 255;
*op++ = (BYTE) accumulator;
} else {
*op++ = (BYTE)(lastRunSize << ML_BITS);
}
LZ4_memcpy(op, anchor, lastRunSize);
op += lastRunSize;
}
/* End */
*srcSizePtr = (int) (((const char*)ip) - source);
retval = (int) ((char*)op-dst);
goto _return_label;
_dest_overflow:
if (limit == fillOutput) {
/* Assumption : ip, anchor, ovml and ovref must be set correctly */
size_t const ll = (size_t)(ip - anchor);
size_t const ll_addbytes = (ll + 240) / 255;
size_t const ll_totalCost = 1 + ll_addbytes + ll;
BYTE* const maxLitPos = oend - 3; /* 2 for offset, 1 for token */
DEBUGLOG(6, "Last sequence overflowing (only %i bytes remaining)", (int)(oend-1-opSaved));
op = opSaved; /* restore correct out pointer */
if (op + ll_totalCost <= maxLitPos) {
/* ll validated; now adjust match length */
size_t const bytesLeftForMl = (size_t)(maxLitPos - (op+ll_totalCost));
size_t const maxMlSize = MINMATCH + (ML_MASK-1) + (bytesLeftForMl * 255);
assert(maxMlSize < INT_MAX); assert(ovml >= 0);
if ((size_t)ovml > maxMlSize) ovml = (int)maxMlSize;
if ((oend + LASTLITERALS) - (op + ll_totalCost + 2) - 1 + ovml >= MFLIMIT) {
DEBUGLOG(6, "Space to end : %i + ml (%i)", (int)((oend + LASTLITERALS) - (op + ll_totalCost + 2) - 1), ovml);
DEBUGLOG(6, "Before : ip = %p, anchor = %p", ip, anchor);
LZ4HC_encodeSequence(UPDATABLE(ip, op, anchor), ovml, ovref, notLimited, oend);
DEBUGLOG(6, "After : ip = %p, anchor = %p", ip, anchor);
} }
goto _last_literals;
}
_return_label:
#if defined(LZ4HC_HEAPMODE) && LZ4HC_HEAPMODE==1
FREEMEM(opt);
#endif
return retval;
}