removed code and reference to binary tree match finder

reduced size of LZ4HC state

3 files changed, 6 insertions, 132 deletions

diff --git a/lib/lz4hc.c b/lib/lz4hc.c
index a7238c7..c1f8da6 100644
--- a/lib/lz4hc.c
+++ b/lib/lz4hc.c
@@ -761,10 +761,7 @@ int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int
     }
     LZ4HC_init (ctxPtr, (const BYTE*)dictionary);
     ctxPtr->end = (const BYTE*)dictionary + dictSize;
-    if (ctxPtr->compressionLevel >= LZ4HC_CLEVEL_OPT_MIN)
-        LZ4HC_updateBinTree(ctxPtr, ctxPtr->end - MFLIMIT, ctxPtr->end - LASTLITERALS);
-    else
-        if (dictSize >= 4) LZ4HC_Insert (ctxPtr, ctxPtr->end-3);
+    if (dictSize >= 4) LZ4HC_Insert (ctxPtr, ctxPtr->end-3);
     return dictSize;
 }
 
@@ -773,10 +770,7 @@ int LZ4_loadDictHC (LZ4_streamHC_t* LZ4_streamHCPtr, const char* dictionary, int
 
 static void LZ4HC_setExternalDict(LZ4HC_CCtx_internal* ctxPtr, const BYTE* newBlock)
 {
-    if (ctxPtr->compressionLevel >= LZ4HC_CLEVEL_OPT_MIN)
-        LZ4HC_updateBinTree(ctxPtr, ctxPtr->end - MFLIMIT, ctxPtr->end - LASTLITERALS);
-    else
-        if (ctxPtr->end >= ctxPtr->base + 4) LZ4HC_Insert (ctxPtr, ctxPtr->end-3);   /* Referencing remaining dictionary content */
+    if (ctxPtr->end >= ctxPtr->base + 4) LZ4HC_Insert (ctxPtr, ctxPtr->end-3);   /* Referencing remaining dictionary content */
 
     /* Only one memory segment for extDict, so any previous extDict is lost at this stage */
     ctxPtr->lowLimit  = ctxPtr->dictLimit;
diff --git a/lib/lz4hc.h b/lib/lz4hc.h
index a9cefbb..191ab0c 100644
--- a/lib/lz4hc.h
+++ b/lib/lz4hc.h
@@ -129,7 +129,7 @@ LZ4LIB_API int LZ4_saveDictHC (LZ4_streamHC_t* streamHCPtr, char* safeBuffer, in
  * They are exposed to allow static allocation of `LZ4_streamHC_t`.
  * Using these definitions makes the code vulnerable to potential API break when upgrading LZ4
  **************************************/
-#define LZ4HC_DICTIONARY_LOGSIZE 17   /* due to btree, hc would only need 16 */
+#define LZ4HC_DICTIONARY_LOGSIZE 16
 #define LZ4HC_MAXD (1<<LZ4HC_DICTIONARY_LOGSIZE)
 #define LZ4HC_MAXD_MASK (LZ4HC_MAXD - 1)
 
@@ -175,7 +175,7 @@ typedef struct
 
 #endif
 
-#define LZ4_STREAMHCSIZE       (4*LZ4HC_HASHTABLESIZE + 2*LZ4HC_MAXD + 56) /* 393268 */
+#define LZ4_STREAMHCSIZE       (4*LZ4HC_HASHTABLESIZE + 2*LZ4HC_MAXD + 56) /* 262200 */
 #define LZ4_STREAMHCSIZE_SIZET (LZ4_STREAMHCSIZE / sizeof(size_t))
 union LZ4_streamHC_u {
     size_t table[LZ4_STREAMHCSIZE_SIZET];
diff --git a/lib/lz4opt.h b/lib/lz4opt.h
index c754865..841e00c 100644
--- a/lib/lz4opt.h
+++ b/lib/lz4opt.h
@@ -62,7 +62,7 @@ LZ4_FORCE_INLINE int LZ4HC_literalsPrice(int const litlen)
 /* requires mlen >= MINMATCH */
 LZ4_FORCE_INLINE int LZ4HC_sequencePrice(int litlen, int mlen)
 {
-    int price = 2 + 1; /* 16-bit offset + token */
+    int price = 1 + 2 ; /* token + 16-bit offset */
 
     price += LZ4HC_literalsPrice(litlen);
 
@@ -74,126 +74,8 @@ LZ4_FORCE_INLINE int LZ4HC_sequencePrice(int litlen, int mlen)
 
 
 /*-*************************************
-*  Binary Tree search
+*  Match finder
 ***************************************/
-LZ4_FORCE_INLINE int LZ4HC_BinTree_InsertAndGetAllMatches (
-    LZ4HC_CCtx_internal* ctx,
-    const BYTE* const ip,
-    const BYTE* const iHighLimit,
-    size_t best_mlen,
-    LZ4HC_match_t* matches,
-    int* matchNum)
-{
-    U16* const chainTable = ctx->chainTable;
-    U32* const HashTable = ctx->hashTable;
-    const BYTE* const base = ctx->base;
-    const U32 dictLimit = ctx->dictLimit;
-    const U32 current = (U32)(ip - base);
-    const U32 lowLimit = (ctx->lowLimit + MAX_DISTANCE > current) ? ctx->lowLimit : current - (MAX_DISTANCE - 1);
-    const BYTE* const dictBase = ctx->dictBase;
-    const BYTE* match;
-    int nbAttempts = ctx->searchNum;
-    int mnum = 0;
-    U16 *ptr0, *ptr1, delta0, delta1;
-    U32 matchIndex;
-    size_t matchLength = 0;
-    U32* HashPos;
-
-    if (ip + MINMATCH > iHighLimit) return 1;
-
-    /* HC4 match finder */
-    HashPos = &HashTable[LZ4HC_hashPtr(ip)];
-    matchIndex = *HashPos;
-    *HashPos = current;
-
-    ptr0 = &DELTANEXTMAXD(current*2+1);
-    ptr1 = &DELTANEXTMAXD(current*2);
-    delta0 = delta1 = (U16)(current - matchIndex);
-
-    while ((matchIndex < current) && (matchIndex>=lowLimit) && (nbAttempts)) {
-        nbAttempts--;
-        if (matchIndex >= dictLimit) {
-            match = base + matchIndex;
-            matchLength = LZ4_count(ip, match, iHighLimit);
-        } else {
-            const BYTE* vLimit = ip + (dictLimit - matchIndex);
-            match = dictBase + matchIndex;
-            if (vLimit > iHighLimit) vLimit = iHighLimit;
-            matchLength = LZ4_count(ip, match, vLimit);
-            if ((ip+matchLength == vLimit) && (vLimit < iHighLimit))
-                matchLength += LZ4_count(ip+matchLength, base+dictLimit, iHighLimit);
-            if (matchIndex+matchLength >= dictLimit)
-                match = base + matchIndex;   /* to prepare for next usage of match[matchLength] */
-        }
-
-        if (matchLength > best_mlen) {
-            best_mlen = matchLength;
-            if (matches) {
-                if (matchIndex >= dictLimit)
-                    matches[mnum].off = (int)(ip - match);
-                else
-                    matches[mnum].off = (int)(ip - (base + matchIndex)); /* virtual matchpos */
-                matches[mnum].len = (int)matchLength;
-                mnum++;
-            }
-            if (best_mlen > LZ4_OPT_NUM) break;
-        }
-
-        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 */
-
-        DEBUGLOG(6, "ip   :%016llX", (U64)ip);
-        DEBUGLOG(6, "match:%016llX", (U64)match);
-        if (*(ip+matchLength) < *(match+matchLength)) {
-            *ptr0 = delta0;
-            ptr0 = &DELTANEXTMAXD(matchIndex*2);
-            if (*ptr0 == (U16)-1) break;
-            delta0 = *ptr0;
-            delta1 += delta0;
-            matchIndex -= delta0;
-        } else {
-            *ptr1 = delta1;
-            ptr1 = &DELTANEXTMAXD(matchIndex*2+1);
-            if (*ptr1 == (U16)-1) break;
-            delta1 = *ptr1;
-            delta0 += delta1;
-            matchIndex -= delta1;
-        }
-    }
-
-    *ptr0 = (U16)-1;
-    *ptr1 = (U16)-1;
-    if (matchNum) *matchNum = mnum;
-  /*  if (best_mlen > 8) return best_mlen-8; */
-    if (!matchNum) return 1;
-    return 1;
-}
-
-
-LZ4_FORCE_INLINE void LZ4HC_updateBinTree(LZ4HC_CCtx_internal* ctx, const BYTE* const ip, const BYTE* const iHighLimit)
-{
-    const BYTE* const base = ctx->base;
-    const U32 target = (U32)(ip - base);
-    U32 idx = ctx->nextToUpdate;
-    while(idx < target)
-        idx += LZ4HC_BinTree_InsertAndGetAllMatches(ctx, base+idx, iHighLimit, 8, NULL, NULL);
-}
-
-
-/** Tree updater, providing best match */
-LZ4_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, const int fullUpdate)
-{
-    int mnum = 0;
-    if (ip < ctx->base + ctx->nextToUpdate) return 0;   /* skipped area */
-    if (fullUpdate) LZ4HC_updateBinTree(ctx, ip, iHighLimit);
-    best_mlen = LZ4HC_BinTree_InsertAndGetAllMatches(ctx, ip, iHighLimit, best_mlen, matches, &mnum);
-    ctx->nextToUpdate = (U32)(ip - ctx->base + best_mlen);
-    return mnum;
-}
-
 
 LZ4_FORCE_INLINE
 int LZ4HC_FindLongerMatch(LZ4HC_CCtx_internal* const ctx,   /* Index table will be updated */
@@ -257,7 +139,6 @@ static int LZ4HC_compress_optimal (
         int best_mlen, best_off;
         int cur, last_match_pos = 0;
 
-        //int const nb_matches_initial = LZ4HC_BinTree_GetAllMatches(ctx, ip, matchlimit, MINMATCH-1, matches, fullUpdate);
         int const nb_matches_initial = LZ4HC_HashChain_GetAllMatches(ctx, ip, matchlimit, MINMATCH-1, matches, fullUpdate);
         if (!nb_matches_initial) { ip++; continue; }
 
@@ -323,7 +204,6 @@ static int LZ4HC_compress_optimal (
             }
 
             DEBUGLOG(7, "search at rPos:%u", cur);
-            //nb_matches = LZ4HC_BinTree_GetAllMatches(ctx, curPtr, matchlimit, MINMATCH-1, matches, fullUpdate);
             if (fullUpdate)
                 nb_matches = LZ4HC_HashChain_GetAllMatches(ctx, curPtr, matchlimit, MINMATCH-1, matches, fullUpdate);
             else