$ cat 0004-Backport-Unconditional-refill-for-literals-with-fast.patch

From bc8d6761c35275f96916238bd450296a9106528d Mon Sep 17 00:00:00 2001
From: Felix Hanau <[email protected]>
Date: Fri, 8 Sep 2023 17:58:50 -0400
Subject: [PATCH 4/4] Backport "Unconditional refill for literals with
 fastpath"

This PR avoids branching before a potential bit buffer refill during
decompression as the buffer is filled once in every iteration, allowing
up to two literals to be decoded. See https://chromium-review.googlesource.com/c/chromium/src/+/4247146
for base commit, rationale and performance metrics. Patch based on
Dougall Johnson's inflate improvements.

Also drops superfluous return statement.
---
 inffast_chunk.c | 69 +++++++++++++++++++++++++++++++------------------
 inffast_chunk.h | 17 ++++++++----
 2 files changed, 56 insertions(+), 30 deletions(-)

diff --git a/inffast_chunk.c b/inffast_chunk.c
index 39eff71..7a158d7 100644
--- a/inffast_chunk.c
+++ b/inffast_chunk.c
@@ -22,6 +22,7 @@
  * [email protected]          [email protected]
  *
  * Copyright (C) 1995-2017 Mark Adler
+ * Copyright 2023 The Chromium Authors
  * For conditions of distribution and use, see copyright notice in zlib.h
  */
 
@@ -46,8 +47,8 @@
    Entry assumptions:
 
         state->mode == LEN
-        strm->avail_in >= INFLATE_FAST_MIN_INPUT (6 or 8 bytes)
-        strm->avail_out >= INFLATE_FAST_MIN_OUTPUT (258 bytes)
+        strm->avail_in >= INFLATE_FAST_MIN_INPUT (6 or 8 bytes + 7 bytes)
+        strm->avail_out >= INFLATE_FAST_MIN_OUTPUT (258 bytes + 2 bytes)
         start >= strm->avail_out
         state->bits < 8
         strm->next_out[0..strm->avail_out] does not overlap with
@@ -63,7 +64,7 @@
 
    Notes:
 
-    INFLATE_FAST_MIN_INPUT: 6 or 8 bytes
+    INFLATE_FAST_MIN_INPUT: 6 or 8 bytes + 7 bytes
 
     - The maximum input bits used by a length/distance pair is 15 bits for the
       length code, 5 bits for the length extra, 15 bits for the distance code,
@@ -85,10 +86,10 @@
 
           (state->hold >> state->bits) == 0
 
-    INFLATE_FAST_MIN_OUTPUT: 258 bytes
+    INFLATE_FAST_MIN_OUTPUT: 258 bytes + 2 bytes for literals = 260 bytes
     - The maximum bytes that a single length/distance pair can output is 258
       bytes, which is the maximum length that can be coded.  inflate_fast()
-      requires strm->avail_out >= 258 for each loop to avoid checking for
+      requires strm->avail_out >= 260 for each loop to avoid checking for
       available output space while decoding.
  */
 void ZLIB_INTERNAL inflate_fast_chunk_(strm, start)
@@ -144,22 +145,50 @@ unsigned start;         /* inflate()'s starting value for strm->avail_out */
     lmask = (1U << state->lenbits) - 1;
     dmask = (1U << state->distbits) - 1;
 
+#ifdef INFLATE_CHUNK_READ_64LE
+#define REFILL() do { \
+        Assert(bits < 64, "too many bits in inflate_fast_chunk_"); \
+        hold |= read64le(in) << bits; \
+        in += 7; \
+        in -= bits >> 3; \
+        bits |= 56; \
+    } while (0)
+#endif
+
     /* decode literals and length/distances until end-of-block or not enough
        input data or output space */
     do {
-        if (bits < 15) {
 #ifdef INFLATE_CHUNK_READ_64LE
-            hold |= read64le(in) << bits;
-            in += 6;
-            bits += 48;
+        REFILL();
 #else
+        if (bits < 15) {
             hold += (unsigned long)(*in++) << bits;
             bits += 8;
             hold += (unsigned long)(*in++) << bits;
             bits += 8;
-#endif
         }
+#endif
         here = lcode[hold & lmask];
+#ifdef INFLATE_CHUNK_READ_64LE
+        if (here.op == 0) {                     /* literal */
+            Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
+                    "inflate:         literal '%c'\n" :
+                    "inflate:         literal 0x%02x\n", here.val));
+            *out++ = (unsigned char)(here.val);
+            hold >>= here.bits;
+            bits -= here.bits;
+            here = lcode[hold & lmask];
+            if (here.op == 0) {                 /* literal */
+                Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
+                        "inflate:    2nd  literal '%c'\n" :
+                        "inflate:    2nd  literal 0x%02x\n", here.val));
+                *out++ = (unsigned char)(here.val);
+                hold >>= here.bits;
+                bits -= here.bits;
+                here = lcode[hold & lmask];
+            }
+        }
+#endif
       dolen:
         op = (unsigned)(here.bits);
         hold >>= op;
@@ -175,33 +204,25 @@ unsigned start;         /* inflate()'s starting value for strm->avail_out */
             len = (unsigned)(here.val);
             op &= 15;                           /* number of extra bits */
             if (op) {
+#ifndef INFLATE_CHUNK_READ_64LE
                 if (bits < op) {
-#ifdef INFLATE_CHUNK_READ_64LE
-                    hold |= read64le(in) << bits;
-                    in += 6;
-                    bits += 48;
-#else
                     hold += (unsigned long)(*in++) << bits;
                     bits += 8;
-#endif
                 }
+#endif
                 len += (unsigned)hold & ((1U << op) - 1);
                 hold >>= op;
                 bits -= op;
             }
             Tracevv((stderr, "inflate:         length %u\n", len));
+#ifndef INFLATE_CHUNK_READ_64LE
             if (bits < 15) {
-#ifdef INFLATE_CHUNK_READ_64LE
-                hold |= read64le(in) << bits;
-                in += 6;
-                bits += 48;
-#else
                 hold += (unsigned long)(*in++) << bits;
                 bits += 8;
                 hold += (unsigned long)(*in++) << bits;
                 bits += 8;
-#endif
             }
+#endif
             here = dcode[hold & dmask];
           dodist:
             op = (unsigned)(here.bits);
@@ -213,9 +234,7 @@ unsigned start;         /* inflate()'s starting value for strm->avail_out */
                 op &= 15;                       /* number of extra bits */
                 if (bits < op) {
 #ifdef INFLATE_CHUNK_READ_64LE
-                    hold |= read64le(in) << bits;
-                    in += 6;
-                    bits += 48;
+                    REFILL();
 #else
                     hold += (unsigned long)(*in++) << bits;
                     bits += 8;
diff --git a/inffast_chunk.h b/inffast_chunk.h
index 5d6025a..aadfd70 100644
--- a/inffast_chunk.h
+++ b/inffast_chunk.h
@@ -33,16 +33,23 @@
 
 #include "inffast.h"
 
-/* INFLATE_FAST_MIN_INPUT: the minimum number of input bytes needed so that
-   we can safely call inflate_fast() with only one up-front bounds check. One
+/* INFLATE_FAST_MIN_INPUT:
+   The minimum number of input bytes needed so that we can safely call
+   inflate_fast() with only one up-front bounds check. One
    length/distance code pair (15 bits for the length code, 5 bits for length
    extra, 15 bits for the distance code, 13 bits for distance extra) requires
-   reading up to 48 input bits (6 bytes). The wide input data reading option
-   requires a little endian machine, and reads 64 input bits (8 bytes).
+   reading up to 48 input bits. Additionally, in the same iteration, we may
+   decode two literals from the root table (requiring 258 + 2 output bytes).
+
+   The wide refill reads eight bytes and advances the input pointer by up to
+   seven bytes, maintaining at least 56 bits in the bit buffer. In the worst
+   case it refills twice in one iteration, requiring 8 + 7 input bytes.
 */
 #ifdef INFLATE_CHUNK_READ_64LE
 #undef INFLATE_FAST_MIN_INPUT
-#define INFLATE_FAST_MIN_INPUT 8
+#define INFLATE_FAST_MIN_INPUT 15
+#undef INFLATE_FAST_MIN_OUTPUT
+#define INFLATE_FAST_MIN_OUTPUT 260
 #endif
 
 void ZLIB_INTERNAL inflate_fast_chunk_(z_streamp strm, unsigned start);
-- 
2.55.0