Restore hash_head != 0 checks

Commit bc5915e2dec7 ("Fixed unsigned integer overflow ASAN error when
hash_head > s->strstart.") removed hash_head != 0 checks in fast,
medium and slow deflate, because it improved performance [1].

Unfortunately, the attached test started failing after that.
Apparently, as the comments suggest, the code implicitly relies on
matches with the beginning of the window being skipped. So restore the
check.

[1] https://github.com/zlib-ng/zlib-ng/pull/772#issuecomment-710760300

5 files changed, 115 insertions, 4 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 7b43268..b39f132 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -1261,6 +1261,7 @@ if(ZLIB_ENABLE_TESTS)
 
     add_simple_test_executable(deflate_quick_bi_valid)
     add_simple_test_executable(deflate_quick_block_open)
+    add_simple_test_executable(hash_head_0)
 endif()
 
 FEATURE_SUMMARY(WHAT ALL INCLUDE_QUIET_PACKAGES)
diff --git a/deflate_fast.c b/deflate_fast.c
index 14718ba..1594886 100644
--- a/deflate_fast.c
+++ b/deflate_fast.c
@@ -48,7 +48,7 @@ Z_INTERNAL block_state deflate_fast(deflate_state *s, int flush) {
              * At this point we have always match length < MIN_MATCH
              */
             
-            if (dist <= MAX_DIST(s) && dist > 0) {
+            if (dist <= MAX_DIST(s) && dist > 0 && hash_head != 0) {
                 /* To simplify the code, we prevent matches with the string
                  * of window index 0 (in particular we have to avoid a match
                  * of the string with itself at the start of the input file).
diff --git a/deflate_medium.c b/deflate_medium.c
index dad550c..59ccfa8 100644
--- a/deflate_medium.c
+++ b/deflate_medium.c
@@ -210,7 +210,7 @@ Z_INTERNAL block_state deflate_medium(deflate_state *s, int flush) {
              */
 
             dist = (int64_t)s->strstart - hash_head;
-            if (dist <= MAX_DIST(s) && dist > 0) {
+            if (dist <= MAX_DIST(s) && dist > 0 && hash_head != 0) {
                 /* To simplify the code, we prevent matches with the string
                  * of window index 0 (in particular we have to avoid a match
                  * of the string with itself at the start of the input file).
@@ -245,7 +245,7 @@ Z_INTERNAL block_state deflate_medium(deflate_state *s, int flush) {
              */
 
             dist = (int64_t)s->strstart - hash_head;
-            if (dist <= MAX_DIST(s) && dist > 0) {
+            if (dist <= MAX_DIST(s) && dist > 0 && hash_head != 0) {
                 /* To simplify the code, we prevent matches with the string
                  * of window index 0 (in particular we have to avoid a match
                  * of the string with itself at the start of the input file).
diff --git a/deflate_slow.c b/deflate_slow.c
index cac8a96..dc1c072 100644
--- a/deflate_slow.c
+++ b/deflate_slow.c
@@ -50,7 +50,7 @@ Z_INTERNAL block_state deflate_slow(deflate_state *s, int flush) {
         match_len = MIN_MATCH-1;
         dist = (int64_t)s->strstart - hash_head;
 
-        if (dist <= MAX_DIST(s) && dist > 0 && s->prev_length < s->max_lazy_match) {
+        if (dist <= MAX_DIST(s) && dist > 0 && s->prev_length < s->max_lazy_match && hash_head != 0) {
             /* To simplify the code, we prevent matches with the string
              * of window index 0 (in particular we have to avoid a match
              * of the string with itself at the start of the input file).
diff --git a/test/hash_head_0.c b/test/hash_head_0.c
new file mode 100644
index 0000000..128ae34
--- /dev/null
+++ b/test/hash_head_0.c
@@ -0,0 +1,110 @@
+/* Generated by fuzzing - test hash_head == 0 handling. */
+
+#include "zbuild.h"
+#ifdef ZLIB_COMPAT
+#  include "zlib.h"
+#else
+#  include "zlib-ng.h"
+#endif
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+int main() {
+    PREFIX3(stream) strm;
+    memset(&strm, 0, sizeof(strm));
+
+    int ret = PREFIX(deflateInit2)(&strm, 1, Z_DEFLATED, -15, 4, Z_HUFFMAN_ONLY);
+    if (ret != Z_OK) {
+        fprintf(stderr, "deflateInit2() failed with code %d\n", ret);
+        return EXIT_FAILURE;
+    }
+
+    unsigned char next_in[9698];
+    memset(next_in, 0x30, sizeof(next_in));
+    next_in[8193] = 0x00;
+    next_in[8194] = 0x00;
+    next_in[8195] = 0x00;
+    next_in[8199] = 0x8a;
+    strm.next_in = next_in;
+    unsigned char next_out[21572];
+    strm.next_out = next_out;
+
+    strm.avail_in = 0;
+    strm.avail_out = 1348;
+    ret = PREFIX(deflateParams(&strm, 3, Z_FILTERED));
+    if (ret != Z_OK) {
+        fprintf(stderr, "deflateParams() failed with code %d\n", ret);
+        return EXIT_FAILURE;
+    }
+
+    strm.avail_in = 6728;
+    strm.avail_out = 2696;
+    ret = PREFIX(deflate(&strm, Z_SYNC_FLUSH));
+    if (ret != Z_OK) {
+        fprintf(stderr, "deflate() failed with code %d\n", ret);
+        return EXIT_FAILURE;
+    }
+
+    strm.avail_in = 15;
+    strm.avail_out = 1348;
+    ret = PREFIX(deflateParams(&strm, 9, Z_FILTERED));
+    if (ret != Z_OK) {
+        fprintf(stderr, "deflateParams() failed with code %d\n", ret);
+        return EXIT_FAILURE;
+    }
+
+    strm.avail_in = 1453;
+    strm.avail_out = 1348;
+    ret = PREFIX(deflate(&strm, Z_FULL_FLUSH));
+    if (ret != Z_OK) {
+        fprintf(stderr, "deflate() failed with code %d\n", ret);
+        return EXIT_FAILURE;
+    }
+
+    strm.avail_in = next_in + sizeof(next_in) - strm.next_in;
+    strm.avail_out = next_out + sizeof(next_out) - strm.next_out;
+    ret = PREFIX(deflate)(&strm, Z_FINISH);
+    if (ret != Z_STREAM_END) {
+        fprintf(stderr, "deflate() failed with code %d\n", ret);
+        return EXIT_FAILURE;
+    }
+    uint32_t compressed_size = strm.next_out - next_out;
+
+    ret = PREFIX(deflateEnd)(&strm);
+    if (ret != Z_OK) {
+        fprintf(stderr, "deflateEnd() failed with code %d\n", ret);
+        return EXIT_FAILURE;
+    }
+
+    memset(&strm, 0, sizeof(strm));
+    ret = PREFIX(inflateInit2)(&strm, -15);
+    if (ret != Z_OK) {
+        fprintf(stderr, "inflateInit2() failed with code %d\n", ret);
+        return EXIT_FAILURE;
+    }
+
+    strm.next_in = next_out;
+    strm.avail_in = compressed_size;
+    unsigned char uncompressed[sizeof(next_in)];
+    strm.next_out = uncompressed;
+    strm.avail_out = sizeof(uncompressed);
+
+    ret = PREFIX(inflate)(&strm, Z_NO_FLUSH);
+    if (ret != Z_STREAM_END) {
+        fprintf(stderr, "inflate() failed with code %d\n", ret);
+        return EXIT_FAILURE;
+    }
+
+    ret = PREFIX(inflateEnd)(&strm);
+    if (ret != Z_OK) {
+        fprintf(stderr, "inflateEnd() failed with code %d\n", ret);
+        return EXIT_FAILURE;
+    }
+
+    if (memcmp(uncompressed, next_in, sizeof(uncompressed)) != 0) {
+        fprintf(stderr, "Uncompressed data differs from the original\n");
+        return EXIT_FAILURE;
+    }
+}