From e4f5a34d1613b3cce97124539c3a8b6b2ed42310 Mon Sep 17 00:00:00 2001
From: Yann Collet <cyan@fb.com>
Date: Fri, 28 Jan 2022 16:51:28 -0800
Subject: fixed bug in optimal parser

discovered by @yoniko.
---
 lib/lz4hc.c    | 36 +++++++++++++++++-------------------
 tests/Makefile |  1 +
 2 files changed, 18 insertions(+), 19 deletions(-)

diff --git a/lib/lz4hc.c b/lib/lz4hc.c
index e71ce94..ee6fc41 100644
--- a/lib/lz4hc.c
+++ b/lib/lz4hc.c
@@ -193,8 +193,7 @@ LZ4HC_countPattern(const BYTE* ip, const BYTE* const iEnd, U32 const pattern32)
             BYTE const byte = (BYTE)(pattern >> bitOffset);
             if (*ip != byte) break;
             ip ++; bitOffset -= 8;
-        }
-    }
+    }   }
 
     return (unsigned)(ip - iStart);
 }
@@ -234,18 +233,16 @@ typedef enum { favorCompressionRatio=0, favorDecompressionSpeed } HCfavor_e;
 
 LZ4_FORCE_INLINE int
 LZ4HC_InsertAndGetWiderMatch (
-    LZ4HC_CCtx_internal* hc4,
-    const BYTE* const ip,
-    const BYTE* const iLowLimit,
-    const BYTE* const iHighLimit,
-    int longest,
-    const BYTE** matchpos,
-    const BYTE** startpos,
-    const int maxNbAttempts,
-    const int patternAnalysis,
-    const int chainSwap,
-    const dictCtx_directive dict,
-    const HCfavor_e favorDecSpeed)
+        LZ4HC_CCtx_internal* const hc4,
+        const BYTE* const ip,
+        const BYTE* const iLowLimit, const BYTE* const iHighLimit,
+        int longest,
+        const BYTE** matchpos,
+        const BYTE** startpos,
+        const int maxNbAttempts,
+        const int patternAnalysis, const int chainSwap,
+        const dictCtx_directive dict,
+        const HCfavor_e favorDecSpeed)
 {
     U16* const chainTable = hc4->chainTable;
     U32* const HashTable = hc4->hashTable;
@@ -254,7 +251,8 @@ LZ4HC_InsertAndGetWiderMatch (
     const U32 dictLimit = hc4->dictLimit;
     const BYTE* const lowPrefixPtr = base + dictLimit;
     const U32 ipIndex = (U32)(ip - base);
-    const U32 lowestMatchIndex = (hc4->lowLimit + (LZ4_DISTANCE_MAX + 1) > ipIndex) ? hc4->lowLimit : ipIndex - LZ4_DISTANCE_MAX;
+    const int withinStartDistance = (hc4->lowLimit + (LZ4_DISTANCE_MAX + 1) > ipIndex);
+    const U32 lowestMatchIndex = (withinStartDistance) ? hc4->lowLimit : ipIndex - LZ4_DISTANCE_MAX;
     const BYTE* const dictBase = hc4->dictBase;
     int const lookBackLength = (int)(ip-iLowLimit);
     int nbAttempts = maxNbAttempts;
@@ -294,7 +292,8 @@ LZ4HC_InsertAndGetWiderMatch (
             }   }   }
         } else {   /* lowestMatchIndex <= matchIndex < dictLimit */
             const BYTE* const matchPtr = dictBase + matchIndex;
-            if (LZ4_read32(matchPtr) == pattern) {
+            if ( likely(matchIndex <= dictLimit - 4)
+              && (LZ4_read32(matchPtr) == pattern) ) {
                 const BYTE* const dictStart = dictBase + hc4->lowLimit;
                 int back = 0;
                 const BYTE* vLimit = ip + (dictLimit - matchIndex);
@@ -310,7 +309,7 @@ LZ4HC_InsertAndGetWiderMatch (
                     *startpos = ip + back;
         }   }   }
 
-        if (chainSwap && matchLength==longest) {    /* better match => select a better chain */
+        if (chainSwap && matchLength==longest) {   /* better match => select a better chain */
             assert(lookBackLength==0);   /* search forward only */
             if (matchIndex + (U32)longest <= ipIndex) {
                 int const kTrigger = 4;
@@ -326,8 +325,7 @@ LZ4HC_InsertAndGetWiderMatch (
                         distanceToNextMatch = candidateDist;
                         matchChainPos = (U32)pos;
                         accel = 1 << kTrigger;
-                    }
-                }
+                }   }
                 if (distanceToNextMatch > 1) {
                     if (distanceToNextMatch > matchIndex) break;   /* avoid overflow */
                     matchIndex -= distanceToNextMatch;
diff --git a/tests/Makefile b/tests/Makefile
index 00f6f3b..b7490b8 100644
--- a/tests/Makefile
+++ b/tests/Makefile
@@ -448,6 +448,7 @@ test-lz4-opt-parser: lz4 datagen
 	$(DATAGEN) -g256K      | $(LZ4) -12B4D   | $(LZ4) -t
 	$(DATAGEN) -g512K -P25 | $(LZ4) -12BD    | $(LZ4) -t
 	$(DATAGEN) -g1M        | $(LZ4) -12B5    | $(LZ4) -t
+	$(DATAGEN) -g1M -s2    | $(LZ4) -12B4D   | $(LZ4) -t
 	$(DATAGEN) -g2M -P99   | $(LZ4) -11B4D   | $(LZ4) -t
 	$(DATAGEN) -g4M        | $(LZ4) -11vq    | $(LZ4) -qt
 	$(DATAGEN) -g8M        | $(LZ4) -11B4    | $(LZ4) -t
-- 
cgit v0.12