From fc879fe170d1644f8fd93017d53e44bc2b3cde04 Mon Sep 17 00:00:00 2001
From: Yann Collet <cyan@fb.com>
Date: Fri, 20 Oct 2017 11:32:15 -0700
Subject: lz4opt: refactor sequence reverse traversal

---
 lib/lz4opt.h | 30 ++++++++++++++++++++----------
 1 file changed, 20 insertions(+), 10 deletions(-)

diff --git a/lib/lz4opt.h b/lib/lz4opt.h
index c7c95a8..7d487a7 100644
--- a/lib/lz4opt.h
+++ b/lib/lz4opt.h
@@ -334,17 +334,25 @@ static int LZ4HC_compress_optimal (
         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 */
         opt[0].mlen = 1;
-        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 = ml;
-            best_off = offset;
-            if (ml > cur) break;   /* can this happen ? */
-            cur -= ml;
-        }
+        DEBUGLOG(6, "sequence reverse traversal");
+        {   int candidate_pos = (int)cur;
+            int selected_matchLength = (int)best_mlen;
+            int selected_offset = (int)best_off;
+            while (1) {  /* from end to beginning */
+                int const next_matchLength = opt[candidate_pos].mlen;
+                int const next_offset = opt[candidate_pos].off;
+                assert(next_matchLength > 0); /* note : can be 1, means literal */
+                opt[candidate_pos].mlen = selected_matchLength;
+                opt[candidate_pos].off = selected_offset;
+                DEBUGLOG(6, "rPos:%3i, matchLength:%3i", candidate_pos, selected_matchLength);
+                selected_matchLength = next_matchLength;
+                selected_offset = next_offset;
+                if (next_matchLength > candidate_pos) break; /* last match elected, first match to encode */
+                candidate_pos -= next_matchLength;
+        }   }
 
         /* encode all recorded sequences */
         cur = 0;
@@ -352,7 +360,9 @@ encode: /* cur, last_match_pos, best_mlen, best_off must be set */
             int const ml = opt[cur].mlen;
             int const offset = opt[cur].off;
             if (ml == 1) { ip++; cur++; continue; }
+            assert(ml >= MINMATCH);
             cur += ml;
+            assert((offset >= 1) && (offset <=65535));
             if ( LZ4HC_encodeSequence(&ip, &op, &anchor, ml, ip - offset, limit, oend) ) return 0;
         }
     }  /* while (ip < mflimit) */
-- 
cgit v0.12