diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/lz4hc.c | 4 | ||||
| -rw-r--r-- | lib/lz4opt.h | 163 |
2 files changed, 85 insertions, 82 deletions
diff --git a/lib/lz4hc.c b/lib/lz4hc.c index f3c9946..03a0301 100644 --- a/lib/lz4hc.c +++ b/lib/lz4hc.c @@ -243,6 +243,10 @@ typedef enum { static unsigned debug = 0; #endif + +/* LZ4HC_encodeSequence() : + * @return : 0 if ok, + * 1 if buffer issue detected */ FORCE_INLINE int LZ4HC_encodeSequence ( const BYTE** ip, BYTE** op, diff --git a/lib/lz4opt.h b/lib/lz4opt.h index 7e2e0f6..416241a 100644 --- a/lib/lz4opt.h +++ b/lib/lz4opt.h @@ -53,7 +53,7 @@ typedef struct { FORCE_INLINE size_t LZ4HC_literalsPrice(size_t litlen) { size_t price = litlen; - if (litlen >= (size_t)RUN_MASK) price += 1+(litlen-RUN_MASK)/255; + if (litlen >= (size_t)RUN_MASK) price += 1 + (litlen-RUN_MASK)/255; return price; } @@ -65,8 +65,8 @@ FORCE_INLINE size_t LZ4HC_sequencePrice(size_t litlen, size_t mlen) price += LZ4HC_literalsPrice(litlen); - mlen -= MINMATCH; - if (mlen >= (size_t)ML_MASK) price+= 1+(mlen-ML_MASK)/255; + if (mlen >= (size_t)(ML_MASK+MINMATCH)) + price+= 1+(mlen-(ML_MASK+MINMATCH))/255; return price; } @@ -190,13 +190,13 @@ FORCE_INLINE int LZ4HC_BinTree_GetAllMatches ( } -#define SET_PRICE(pos, mlen, offset, litlen, price) \ +#define SET_PRICE(pos, ml, offset, ll, cost) \ { \ while (last_pos < pos) { opt[last_pos+1].price = 1<<30; last_pos++; } \ - opt[pos].mlen = (int)mlen; \ + opt[pos].mlen = (int)ml; \ opt[pos].off = (int)offset; \ - opt[pos].litlen = (int)litlen; \ - opt[pos].price = (int)price; \ + opt[pos].litlen = (int)ll; \ + opt[pos].price = (int)cost; \ } @@ -207,15 +207,12 @@ static int LZ4HC_compress_optimal ( int inputSize, int maxOutputSize, limitedOutput_directive limit, - const size_t sufficient_len, + size_t sufficient_len, const int fullUpdate ) { - LZ4HC_optimal_t opt[LZ4_OPT_NUM + 1]; + LZ4HC_optimal_t opt[LZ4_OPT_NUM + 1]; /* this uses a bit too much stack memory to my taste ... */ LZ4HC_match_t matches[LZ4_OPT_NUM + 1]; - const BYTE *inr = NULL; - 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; @@ -226,18 +223,22 @@ static int LZ4HC_compress_optimal ( BYTE* const oend = op + maxOutputSize; /* init */ + if (sufficient_len >= LZ4_OPT_NUM) sufficient_len = LZ4_OPT_NUM-1; ctx->end += inputSize; ip++; /* Main Loop */ while (ip < mflimit) { + size_t const llen = ip - anchor; + size_t last_pos = 0; + size_t match_num, cur, best_mlen, best_off; 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; } if ((size_t)matches[match_num-1].len > sufficient_len) { + /* good enough solution : immediate encoding */ best_mlen = matches[match_num-1].len; best_off = matches[match_num-1].off; cur = 0; @@ -246,45 +247,46 @@ static int LZ4HC_compress_optimal ( } /* 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; - while (mlen <= best_mlen) { - litlen = 0; - price = LZ4HC_sequencePrice(llen + litlen, mlen) - LZ4HC_literalsPrice(llen); - SET_PRICE(mlen, mlen, matches[i].off, litlen, price); - mlen++; - } - } + { size_t matchNb; + for (matchNb = 0; matchNb < match_num; matchNb++) { + size_t mlen = (matchNb>0) ? (size_t)matches[matchNb-1].len+1 : MINMATCH; + best_mlen = matches[matchNb].len; /* necessarily < sufficient_len < LZ4_OPT_NUM */ + for ( ; mlen <= best_mlen ; mlen++) { + size_t const cost = LZ4HC_sequencePrice(llen, mlen) - LZ4HC_literalsPrice(llen); + SET_PRICE(mlen, mlen, matches[matchNb].off, 0, cost); /* updates last_pos and opt[pos] */ + } } } - if (last_pos < MINMATCH) { ip++; continue; } + if (last_pos < MINMATCH) { ip++; continue; } /* note : on clang at least, this test improves performance */ /* 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_literalsPrice(litlen); + const BYTE* const curPtr = ip + cur; + + /* establish baseline price if cur is literal */ + { size_t price, litlen; + if (opt[cur-1].mlen == 1) { + /* no match at previous position */ + litlen = opt[cur-1].litlen + 1; + if (cur > litlen) { + price = opt[cur - litlen].price + LZ4HC_literalsPrice(litlen); + } else { + price = LZ4HC_literalsPrice(llen + litlen) - LZ4HC_literalsPrice(llen); + } } else { - price = LZ4HC_literalsPrice(llen + litlen) - LZ4HC_literalsPrice(llen); + litlen = 1; + price = opt[cur - 1].price + LZ4HC_literalsPrice(1); } - } else { - litlen = 1; - price = opt[cur - 1].price + LZ4HC_literalsPrice(litlen); - } - mlen = 1; - best_mlen = 0; - if (cur > last_pos || price < (size_t)opt[cur].price) - SET_PRICE(cur, mlen, best_mlen, litlen, price); + if (price < (size_t)opt[cur].price) + SET_PRICE(cur, 1, 0, litlen, price); /* note : increases last_pos */ + } - if (cur == last_pos || inr >= mflimit) break; + if (cur == last_pos || curPtr >= mflimit) break; - match_num = LZ4HC_BinTree_GetAllMatches(ctx, inr, matchlimit, MINMATCH-1, matches, fullUpdate); - if (match_num > 0 && (size_t)matches[match_num-1].len > sufficient_len) { + match_num = LZ4HC_BinTree_GetAllMatches(ctx, curPtr, matchlimit, MINMATCH-1, matches, fullUpdate); + if ((match_num > 0) && (size_t)matches[match_num-1].len > sufficient_len) { + /* immediate encoding */ best_mlen = matches[match_num-1].len; best_off = matches[match_num-1].off; last_pos = cur + 1; @@ -292,60 +294,57 @@ static int LZ4HC_compress_optimal ( } /* 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; - - while (mlen <= best_mlen) { - if (opt[cur2].mlen == 1) { - litlen = opt[cur2].litlen; - - if (cur2 != litlen) - price = opt[cur2 - litlen].price + LZ4HC_sequencePrice(litlen, mlen); - else - price = LZ4HC_sequencePrice(llen + litlen, mlen) - LZ4HC_literalsPrice(llen); - } else { - litlen = 0; - price = opt[cur2].price + LZ4HC_sequencePrice(litlen, mlen); - } - - 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++; - } - } + { size_t matchNb; + for (matchNb = 0; matchNb < match_num; matchNb++) { + size_t ml = (matchNb>0) ? (size_t)matches[matchNb-1].len+1 : MINMATCH; + best_mlen = (cur + matches[matchNb].len < LZ4_OPT_NUM) ? + (size_t)matches[matchNb].len : LZ4_OPT_NUM - cur; + + for ( ; ml <= best_mlen ; ml++) { + size_t ll, price; + if (opt[cur].mlen == 1) { + ll = opt[cur].litlen; + if (cur > ll) + price = opt[cur - ll].price + LZ4HC_sequencePrice(ll, ml); + else + price = LZ4HC_sequencePrice(llen + ll, ml) - LZ4HC_literalsPrice(llen); + } else { + ll = 0; + price = opt[cur].price + LZ4HC_sequencePrice(0, ml); + } + + if (cur + ml > last_pos || price < (size_t)opt[cur + ml].price) { + SET_PRICE(cur + ml, ml, matches[matchNb].off, ll, price); + } } } } } /* 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 */ +encode: /* cur, last_pos, best_mlen, best_off must be set */ opt[0].mlen = 1; - while (1) { - mlen = opt[cur].mlen; - offset = opt[cur].off; + while (1) { /* from end to beginning */ + size_t const ml = opt[cur].mlen; + int const offset = opt[cur].off; opt[cur].mlen = (int)best_mlen; opt[cur].off = (int)best_off; - best_mlen = mlen; + best_mlen = ml; best_off = offset; - if (mlen > cur) break; - cur -= mlen; + if (ml > cur) break; + cur -= ml; } + /* encode all recorded sequences */ cur = 0; while (cur < last_pos) { - mlen = opt[cur].mlen; - if (mlen == 1) { ip++; cur++; continue; } - offset = opt[cur].off; - cur += mlen; - - res = LZ4HC_encodeSequence(&ip, &op, &anchor, (int)mlen, ip - offset, limit, oend); - if (res) return 0; + int const ml = opt[cur].mlen; + int const offset = opt[cur].off; + if (ml == 1) { ip++; cur++; continue; } + cur += ml; + if ( LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ip - offset, limit, oend) ) return 0; } - } + } /* while (ip < mflimit) */ /* Encode Last Literals */ { int lastRun = (int)(iend - anchor); |