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