changed strategy : opt[] path is complete after each match

previous strategy would leave a few "bad choices"
on the ground they would be fixed later,
but that requires passing through each position to make the fix
and cannot give the end position of the last useful match.

2 files changed, 71 insertions, 40 deletions

diff --git a/lib/lz4hc.c b/lib/lz4hc.c
index 4532ba3..eb31a9c 100644
--- a/lib/lz4hc.c
+++ b/lib/lz4hc.c
@@ -342,10 +342,6 @@ typedef enum {
     limitedDestSize = 2,
 } limitedOutput_directive;
 
-#ifndef LZ4HC_DEBUG
-#  define LZ4HC_DEBUG 0
-#endif
-
 /* LZ4HC_encodeSequence() :
  * @return : 0 if ok,
  *           1 if buffer issue detected */
@@ -361,9 +357,19 @@ LZ4_FORCE_INLINE int LZ4HC_encodeSequence (
     size_t length;
     BYTE* const token = (*op)++;
 
-#if LZ4HC_DEBUG
-    printf("literal : %u  --  match : %u  --  offset : %u\n",
-           (U32)(*ip - *anchor), (U32)matchLength, (U32)(*ip-match));
+#if defined(LZ4_DEBUG) && (LZ4_DEBUG >= 2)
+    static const BYTE* start = NULL;
+    static U32 totalCost = 0;
+    U32 const ll = (U32)(*ip - *anchor);
+    U32 const llAdd = (ll>=15) ? ((ll-15) / 255) + 1 : 0;
+    U32 const mlAdd = (matchLength>=19) ? ((matchLength-19) / 255) + 1 : 0;
+    U32 const cost = 1 + llAdd + ll + 2 + mlAdd;
+    if (start==NULL) start = *anchor;  /* only works for single segment */
+    totalCost += cost;
+    DEBUGLOG(2, "pos:%7u -- literals:%3u, match:%4i, offset:%5u, cost:%3u/%7u",
+                (U32)(*anchor - start),
+                (U32)(*ip - *anchor), matchLength, (U32)(*ip-match),
+                cost, totalCost);
 #endif
 
     /* Encode Literal length */
@@ -386,6 +392,7 @@ LZ4_FORCE_INLINE int LZ4HC_encodeSequence (
     LZ4_writeLE16(*op, (U16)(*ip-match)); *op += 2;
 
     /* Encode MatchLength */
+    assert(matchLength >= MINMATCH);
     length = (size_t)(matchLength - MINMATCH);
     if ((limit) && (*op + (length >> 8) + (1 + LASTLITERALS) > oend)) return 1;   /* Check output limit */
     if (length >= ML_MASK) {
diff --git a/lib/lz4opt.h b/lib/lz4opt.h
index 40592df..8a223ec 100644
--- a/lib/lz4opt.h
+++ b/lib/lz4opt.h
@@ -233,14 +233,14 @@ static int LZ4HC_compress_optimal (
     const int fullUpdate
     )
 {
-    LZ4HC_optimal_t opt[LZ4_OPT_NUM + 1];   /* this uses a bit too much stack memory to my taste ... */
+    LZ4HC_optimal_t opt[LZ4_OPT_NUM + 3];   /* this uses a bit too much stack memory to my taste ... */
     LZ4HC_match_t matches[LZ4_OPT_NUM + 1];
 
     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);
+    const BYTE* const matchlimit = iend - LASTLITERALS;
     BYTE* op = (BYTE*) dst;
     BYTE* const oend = op + dstCapacity;
 
@@ -278,8 +278,8 @@ static int LZ4HC_compress_optimal (
                 opt[rPos].off = 0;
                 opt[rPos].litlen = llen + rPos;
                 opt[rPos].price = cost;
-                DEBUGLOG(7, "rPos:%3u => cost:%3i (litlen=%i)",
-                            (U32)rPos, cost, opt[rPos].litlen);
+                DEBUGLOG(7, "rPos:%3i => price:%3i (litlen=%i) -- initial setup",
+                            rPos, cost, opt[rPos].litlen);
         }   }
         /* set prices using matches found for rPos = 0 */
         {   int matchNb;
@@ -294,36 +294,26 @@ static int LZ4HC_compress_optimal (
                     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 = matches[nb_matches_initial-1].len;
+        {   int addLit;
+            for (addLit = 1; addLit <= 2; 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++) {
+        for (cur = 1; cur < last_match_pos; cur++) {
             const BYTE* const curPtr = ip + cur;
             int nb_matches;
 
-            /* establish baseline price for cur as a literal.
-             * fixes unused positions (between 2 matches)
-             * and inefficient match stack */
-            {   int price;
-                int litlen;
-                if (opt[cur-1].mlen == 1) {
-                    /* no match at previous position */
-                    litlen = opt[cur-1].litlen + 1;
-                    price = opt[cur-1].price - LZ4HC_literalsPrice(litlen-1) + LZ4HC_literalsPrice(litlen);
-                } else {
-                    litlen = 1;
-                    price = opt[cur - 1].price + LZ4HC_literalsPrice(1);
-                }
-                if (price < opt[cur].price) {
-                    opt[cur].mlen = 1;
-                    opt[cur].off = 0;
-                    opt[cur].litlen = litlen;
-                    opt[cur].price = price;
-                }
-            }
-
-            if (cur == last_match_pos || curPtr >= mflimit) break;
+            if (curPtr >= mflimit) break;
 
             //nb_matches = LZ4HC_BinTree_GetAllMatches(ctx, curPtr, matchlimit, MINMATCH-1, matches, fullUpdate);
             nb_matches = LZ4HC_HashChain_GetAllMatches(ctx, curPtr, matchlimit, MINMATCH-1, matches, fullUpdate);
@@ -339,11 +329,26 @@ static int LZ4HC_compress_optimal (
                 goto encode;
             }
 
+            /* before first 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 matches at position = cur */
             {   int matchNb;
+                assert(cur + matches[nb_matches-1].len < LZ4_OPT_NUM);
                 for (matchNb = 0; matchNb < nb_matches; matchNb++) {
-                    int const matchML = (cur + matches[matchNb].len < LZ4_OPT_NUM) ?
-                                matches[matchNb].len : (int)(LZ4_OPT_NUM - cur);
+                    int const matchML = matches[matchNb].len;
                     int ml = (matchNb>0) ? matches[matchNb-1].len+1 : MINMATCH;
 
                     for ( ; ml <= matchML ; ml++) {
@@ -351,23 +356,39 @@ static int LZ4HC_compress_optimal (
                         int const offset = matches[matchNb].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);
+                            price = ((cur > ll) ? opt[cur - ll].price : 0)
+                                  + LZ4HC_sequencePrice(ll, ml);
                         } else {
                             ll = 0;
                             price = opt[cur].price + LZ4HC_sequencePrice(0, ml);
                         }
 
-                        if (pos > last_match_pos || price < opt[pos].price) {
+                        if (pos > last_match_pos+2 || price <= opt[pos].price) {
+                            DEBUGLOG(7, "rPos:%3i => price:%3i (matchlen=%i)",
+                                        pos, price, ml);
                             assert(pos < LZ4_OPT_NUM);
-                            while (last_match_pos < pos) opt[++last_match_pos].price = 1<<30;
+                            if ( (matchNb == nb_matches-1)  /* last match */
+                              && (ml == matchML)  /* last post 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 <= 2; 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++) */
 
         best_mlen = opt[last_match_pos].mlen;
@@ -377,12 +398,15 @@ static int LZ4HC_compress_optimal (
 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")
+        DEBUGLOG(6, "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(6, "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;