From a22e71d4a9f4bfd0fe12acc00a7fa286faad2da6 Mon Sep 17 00:00:00 2001
From: Przemyslaw Skibinski <inikep@gmail.com>
Date: Fri, 9 Dec 2016 12:37:17 +0100
Subject: full binary tree update

---
 lib/lz4hc.c  |  6 ------
 lib/lz4opt.h | 56 ++++++++++++++++++++++++++++++++++++++++++++------------
 2 files changed, 44 insertions(+), 18 deletions(-)

diff --git a/lib/lz4hc.c b/lib/lz4hc.c
index de7a55c..d3578b9 100644
--- a/lib/lz4hc.c
+++ b/lib/lz4hc.c
@@ -497,12 +497,6 @@ static int LZ4HC_compress_generic (
     limitedOutput_directive limit
     )
 {
-/*
- 9#silesia_tar       : 211947520 ->  77891907 (2.721),  24.3 MB/s ,2142.1 MB/s
-10#silesia_tar       : 211947520 ->  77841782 (2.723),  11.4 MB/s ,2185.3 MB/s
-11#silesia_tar       : 211947520 ->  77408334 (2.738),   6.1 MB/s ,2288.9 MB/s
-12#silesia_tar       : 211947520 ->  77319973 (2.741),   3.3 MB/s ,2361.0 MB/s
-*/
     if (compressionLevel < 1) compressionLevel = LZ4HC_DEFAULT_CLEVEL;
     if (compressionLevel > 9) {
         switch (compressionLevel) {
diff --git a/lib/lz4opt.h b/lib/lz4opt.h
index dc778c9..7e8150f 100644
--- a/lib/lz4opt.h
+++ b/lib/lz4opt.h
@@ -37,7 +37,6 @@
 #define LZ4_LOG_PRICE(fmt, ...) //printf(fmt, __VA_ARGS__) 
 #define LZ4_LOG_ENCODE(fmt, ...) //printf(fmt, __VA_ARGS__) 
 
-
 #define LZ4_OPT_NUM   (1<<12)
 
 
@@ -78,7 +77,10 @@ FORCE_INLINE size_t LZ4HC_get_price(size_t litlen, size_t mlen)
 }
 
 
-FORCE_INLINE int LZ4HC_BinTree_GetAllMatches (
+/*-*************************************
+*  Binary Tree search
+***************************************/
+FORCE_INLINE int LZ4HC_BinTree_InsertAndGetAllMatches (
     LZ4HC_CCtx_internal* ctx,
     const BYTE* const ip,
     const BYTE* const iHighLimit,
@@ -97,7 +99,7 @@ FORCE_INLINE int LZ4HC_BinTree_GetAllMatches (
     int mnum = 0;
     U16 *ptr0, *ptr1, delta0, delta1;
     U32 matchIndex;
-    size_t mlt = 0;
+    size_t matchLength = 0;
     U32* HashPos;
     
     if (ip + MINMATCH > iHighLimit) return 0;
@@ -106,7 +108,6 @@ FORCE_INLINE int LZ4HC_BinTree_GetAllMatches (
     HashPos = &HashTable[LZ4HC_hashPtr(ip)];
     matchIndex = *HashPos;
     *HashPos = current;
-    ctx->nextToUpdate++;
 
     ptr0 = &DELTANEXTMAXD(current*2+1);
     ptr1 = &DELTANEXTMAXD(current*2);
@@ -116,25 +117,28 @@ FORCE_INLINE int LZ4HC_BinTree_GetAllMatches (
         nbAttempts--;
         if (matchIndex >= dictLimit) {
             match = base + matchIndex;
-            mlt = LZ4_count(ip, match, iHighLimit);
+            matchLength = LZ4_count(ip, match, iHighLimit);
         } else {
             const BYTE* vLimit = ip + (dictLimit - matchIndex);
             match = dictBase + matchIndex;
             if (vLimit > iHighLimit) vLimit = iHighLimit;
-            mlt = LZ4_count(ip, match, vLimit);
-            if ((ip+mlt == vLimit) && (vLimit < iHighLimit))
-                mlt += LZ4_count(ip+mlt, base+dictLimit, iHighLimit);
+            matchLength = LZ4_count(ip, match, vLimit);
+            if ((ip+matchLength == vLimit) && (vLimit < iHighLimit))
+                matchLength += LZ4_count(ip+matchLength, base+dictLimit, iHighLimit);
         }
 
-        if (mlt > best_mlen) {
-            best_mlen = mlt;
+        if (matches && matchLength > best_mlen) {
+            best_mlen = matchLength;
             matches[mnum].off = (int)(ip - match);
-            matches[mnum].len = (int)mlt;
+            matches[mnum].len = (int)matchLength;
             mnum++;
             if (best_mlen > LZ4_OPT_NUM) break;
         }
 
-        if (*(ip+mlt) < *(match+mlt)) {
+        if (ip+matchLength >= iHighLimit)   /* equal : no way to know if inf or sup */
+            break;   /* drop , to guarantee consistency ; miss a bit of compression, but other solutions can corrupt the tree */
+
+        if (*(ip+matchLength) < *(match+matchLength)) {
             *ptr0 = delta0;
             ptr0 = &DELTANEXTMAXD(matchIndex*2);
             if (*ptr0 == (U16)-1) break;
@@ -157,6 +161,34 @@ FORCE_INLINE int LZ4HC_BinTree_GetAllMatches (
 }
 
 
+FORCE_INLINE void LZ4HC_updateBinTree(LZ4HC_CCtx_internal* ctx, const BYTE* const ip, const BYTE* const iHighLimit, size_t best_mlen)
+{
+    const BYTE* const base = ctx->base;
+    const U32 target = (U32)(ip - base);
+    U32 idx = ctx->nextToUpdate;
+
+    while(idx < target) {
+        LZ4HC_BinTree_InsertAndGetAllMatches(ctx, base+idx, iHighLimit, best_mlen, NULL);
+        idx++;
+    }
+} 
+
+
+/** Tree updater, providing best match */
+FORCE_INLINE int LZ4HC_BinTree_GetAllMatches (
+                        LZ4HC_CCtx_internal* ctx,
+                        const BYTE* const ip, const BYTE* const iHighLimit,
+                        size_t best_mlen, LZ4HC_match_t* matches)
+{
+    int mnum;
+    if (ip < ctx->base + ctx->nextToUpdate) return 0;   /* skipped area */
+    LZ4HC_updateBinTree(ctx, ip, iHighLimit, best_mlen);
+    mnum = LZ4HC_BinTree_InsertAndGetAllMatches(ctx, ip, iHighLimit, best_mlen, matches);
+    ctx->nextToUpdate = (U32)(ip - ctx->base)+1;
+    return mnum;
+}
+
+
 #define SET_PRICE(pos, mlen, offset, litlen, price)    \
 {                                                      \
     while (last_pos < pos)  { opt[last_pos+1].price = 1<<30; last_pos++; } \
-- 
cgit v0.12