[PATCH] erofs-utils: lib: reset hc to avoid 32-bit overflow of kite-deflate

[Gao Xiang]

Yifan reported a "segmentation fault (core dumped)" error days ago
with a large dataset (enwik9 x 5).   Let's fix it.

Reported-by: Yifan Zhao <zhaoyifan at sjtu.edu.cn>
Fixes: 861037f4fc15 ("erofs-utils: add a built-in DEFLATE compressor")
Signed-off-by: Gao Xiang <hsiangkao at linux.alibaba.com>
---
 include/erofs/defs.h |  3 +++
 lib/kite_deflate.c   | 12 ++++++++++++
 2 files changed, 15 insertions(+)

diff --git a/include/erofs/defs.h b/include/erofs/defs.h
index e7384a1..4ea9a55 100644
--- a/include/erofs/defs.h
+++ b/include/erofs/defs.h
@@ -343,6 +343,9 @@ unsigned long __roundup_pow_of_two(unsigned long n)
 #define ST_MTIM_NSEC(stbuf) 0
 #endif
 
+#define likely(x)      __builtin_expect(!!(x), 1)
+#define unlikely(x)    __builtin_expect(!!(x), 0)
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/lib/kite_deflate.c b/lib/kite_deflate.c
index 8667954..cb81626 100644
--- a/lib/kite_deflate.c
+++ b/lib/kite_deflate.c
@@ -859,6 +859,18 @@ static void kite_mf_reset(struct kite_matchfinder *mf,
 	 */
 	mf->base += mf->offset + kHistorySize32 + 1;
 
+	/*
+	 * Unlike other LZ encoders like liblzma [1], we simply reset the hash
+	 * chain instead of normalization.  This avoids extra complexity, as we
+	 * don't consider extreme large input buffers in one go.
+	 *
+	 * [1] https://github.com/tukaani-project/xz/blob/v5.4.0/src/liblzma/lz/lz_encoder_mf.c#L94
+	 */
+	if (unlikely(mf->base > ((typeof(mf->base))-1) >> 1)) {
+		mf->base = kHistorySize32 + 1;
+		memset(mf->hash, 0, 0x10000 * sizeof(mf->hash[0]));
+		memset(mf->chain, 0, sizeof(mf->chain[0]) * mf->wsiz);
+	}
 	mf->offset = 0;
 	mf->cyclic_pos = 0;
 
-- 
2.39.3