Commit fc3dc8a for zlib

commit fc3dc8a7c0cba1550bfeb4b815cac87c8f6fe70a
Author: icodywu <125686483+icodywu@users.noreply.github.com>
Date:   Thu Nov 19 10:20:18 2026 -0800

    Speed up inflate with 64-bit fetches and wide match copies.

    If a 64-bit integer is available (Z_U8), run a loop to refill a
    64-bit buffer using 64-bit word loads, once per length/distance
    pair or up to three literals. Matches are copied 8 or 16 bytes at
    a time, though with overlaps for distances 2 to 7, and allowing
    overwrites of up to 15 bytes that stay within the output buffer.
    Continue as long as 16 bytes of input and 275 bytes of output
    space are available.

    This makes raw inflate from 30% to 80% faster in most cases,
    depending on the machine, the size of the deflate stream and the
    amount of input and output provided per call.

    This breaks inflateBack(), so do not cherry pick just this commit.
    On 32-bit machines this has mixed results, from 15% slower to 15%
    faster, and this is a significant loss when unaligned access is
    slow. All these issues are addressed in later commits.

diff --git a/inffast.c b/inffast.c
index d1657f3..c6988ea 100644
--- a/inffast.c
+++ b/inffast.c
@@ -12,6 +12,78 @@
 #  pragma message("Assembler code may have bugs -- use at your own risk")
 #else

+#ifdef Z_U8
+/* Fast loop: with a 64-bit type the bit buffer is refilled eight bytes at a
+   time, and matches are copied eight or sixteen bytes at a time. */
+
+#define TRACE_LITERAL(here) \
+    Tracevv((stderr, (here)->val >= 0x20 && (here)->val < 0x7f ? \
+            "inflate:         literal '%c'\n" : \
+            "inflate:         literal 0x%02x\n", (here)->val))
+
+/* The eight bytes at p, little-endian: one load on a little-endian machine,
+   the bytes one by one on big-endian, though the compiler should turn that
+   into a single load and a byte swap. */
+local Z_U8 load64(z_const unsigned char FAR *p) {
+    Z_U8 v = 1;
+
+    if (*(unsigned char *)&v) {
+        zmemcpy(&v, p, 8);
+        return v;
+    }
+    return (Z_U8)p[0] | ((Z_U8)p[1] << 8) | ((Z_U8)p[2] << 16) |
+           ((Z_U8)p[3] << 24) | ((Z_U8)p[4] << 32) | ((Z_U8)p[5] << 40) |
+           ((Z_U8)p[6] << 48) | ((Z_U8)p[7] << 56);
+}
+
+/* Copy len >= 1 bytes from dist bytes back in the output to out, and return
+   out + len. It may write up to fifteen bytes after out + len, so the caller
+   must have that room. */
+local unsigned char FAR *copy_back(unsigned char FAR *out, unsigned dist,
+                                   unsigned len) {
+    unsigned char FAR *from = out - dist;
+    unsigned char FAR *stop = out + len;
+
+    if (dist >= 16) {                   /* sixteen at a time, no overlap */
+        do {
+            zmemcpy(out, from, 16);
+            out += 16;
+            from += 16;
+        } while (out < stop);
+        return stop;
+    }
+    if (dist >= 8) {                    /* eight at a time, no overlap */
+        do {
+            zmemcpy(out, from, 8);
+            out += 8;
+            from += 8;
+        } while (out < stop);
+        return stop;
+    }
+    if (dist == 1) {                    /* a run of one byte, eight at once */
+        Z_U8 run = *from;
+        run |= run << 8;
+        run |= run << 16;
+        run |= run << 32;
+        do {
+            zmemcpy(out, &run, 8);
+            out += 8;
+        } while (out < stop);
+        return stop;
+    }
+    /* dist 2..7: eight bytes per step, of which the first dist are right;
+       the next step rewrites the rest */
+    do {
+        Z_U8 v;
+        zmemcpy(&v, from, 8);
+        zmemcpy(out, &v, 8);
+        out += dist;
+        from += dist;
+    } while (out < stop);
+    return stop;
+}
+#endif
+
 /*
    Decode literal, length, and distance codes and write out the resulting
    literal and match bytes until either not enough input or output is
@@ -73,6 +145,11 @@ void ZLIB_INTERNAL inflate_fast(z_streamp strm, unsigned start) {
     unsigned len;               /* match length, unused bytes */
     unsigned dist;              /* match distance */
     unsigned char FAR *from;    /* where to copy match from */
+#ifdef Z_U8
+    Z_U8 hold8;                 /* 64-bit bit buffer of the fast loop */
+    z_const unsigned char FAR *last8;   /* two refills fit after in */
+    unsigned char FAR *end8;    /* room for two literals, a match, 15 more */
+#endif

     /* copy state to local variables */
     state = (struct inflate_state FAR *)strm->state;
@@ -95,6 +172,173 @@ void ZLIB_INTERNAL inflate_fast(z_streamp strm, unsigned start) {
     lmask = (1U << state->lenbits) - 1;
     dmask = (1U << state->distbits) - 1;

+#ifdef Z_U8
+    /* Fast loop, while sixteen bytes are available at in (two refills of eight
+       bytes, the first advancing in by up to seven) and the output has room
+       for the longest match plus 17 bytes (one iteration can write two
+       literals and then a match, and copy_back() may write 15 bytes past the
+       match). Each length/literal code starts with at least 56 bits in hold8,
+       enough for a length/distance pair (at most 48 bits). */
+    if (strm->avail_in >= 16 && strm->avail_out >= 2 + 258 + 15) {
+        last8 = in + (strm->avail_in - 16);
+        end8 = out + (strm->avail_out - (2 + 258 + 15));
+        hold8 = hold;
+        do {
+            hold8 |= load64(in) << bits;
+            in += (63 - bits) >> 3;
+            bits |= 56;
+            here = lcode + (hold8 & lmask);
+            if (here->op == 0) {        /* up to three literals a refill */
+                hold8 >>= here->bits;
+                bits -= here->bits;
+                TRACE_LITERAL(here);
+                *out++ = (unsigned char)(here->val);
+                here = lcode + (hold8 & lmask);
+                if (here->op == 0) {
+                    hold8 >>= here->bits;
+                    bits -= here->bits;
+                    TRACE_LITERAL(here);
+                    *out++ = (unsigned char)(here->val);
+                    here = lcode + (hold8 & lmask);
+                    if (here->op == 0) {
+                        hold8 >>= here->bits;
+                        bits -= here->bits;
+                        TRACE_LITERAL(here);
+                        *out++ = (unsigned char)(here->val);
+                        continue;
+                    }
+                }
+                hold8 |= load64(in) << bits;    /* 56 bits for a pair */
+                in += (63 - bits) >> 3;
+                bits |= 56;
+            }
+          dolen8:
+            op = (unsigned)(here->bits);
+            hold8 >>= op;
+            bits -= op;
+            op = (unsigned)(here->op);
+            if (op == 0) {                      /* literal */
+                TRACE_LITERAL(here);
+                *out++ = (unsigned char)(here->val);
+            }
+            else if (op & 16) {                 /* length base */
+                len = (unsigned)(here->val);
+                op &= 15;                       /* number of extra bits */
+                len += (unsigned)hold8 & ((1U << op) - 1);
+                hold8 >>= op;
+                bits -= op;
+                Tracevv((stderr, "inflate:         length %u\n", len));
+                here = dcode + (hold8 & dmask);
+              dodist8:
+                op = (unsigned)(here->bits);
+                hold8 >>= op;
+                bits -= op;
+                op = (unsigned)(here->op);
+                if (op & 16) {                  /* distance base */
+                    dist = (unsigned)(here->val);
+                    op &= 15;                   /* number of extra bits */
+                    dist += (unsigned)hold8 & ((1U << op) - 1);
+#ifdef INFLATE_STRICT
+                    if (dist > dmax) {
+                        strm->msg = (z_const char *)
+                            "invalid distance too far back";
+                        state->mode = BAD;
+                        break;
+                    }
+#endif
+                    hold8 >>= op;
+                    bits -= op;
+                    Tracevv((stderr, "inflate:         distance %u\n", dist));
+                    op = (unsigned)(out - beg); /* max distance in output */
+                    if (dist > op) {            /* see if copy from window */
+                        op = dist - op;         /* distance back in window */
+                        if (op > whave) {
+                            if (state->sane) {
+                                strm->msg = (z_const char *)
+                                    "invalid distance too far back";
+                                state->mode = BAD;
+                                break;
+                            }
+#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
+                            if (len <= op - whave) {
+                                do {
+                                    *out++ = 0;
+                                } while (--len);
+                                continue;
+                            }
+                            len -= op - whave;
+                            do {
+                                *out++ = 0;
+                            } while (--op > whave);
+                            if (op == 0) {
+                                out = copy_back(out, dist, len);
+                                continue;
+                            }
+#endif
+                        }
+                        from = window;
+                        if (wnext == 0)         /* very common case */
+                            from += wsize - op;
+                        else if (wnext < op) {  /* wrap around window */
+                            from += wsize + wnext - op;
+                            op -= wnext;
+                            if (op < len) {     /* end of window, then start */
+                                zmemcpy(out, from, op);
+                                out += op;
+                                len -= op;
+                                from = window;
+                                op = wnext;
+                            }
+                        }
+                        else                    /* contiguous in window */
+                            from += wnext - op;
+                        if (op > len)
+                            op = len;
+                        zmemcpy(out, from, op); /* from the window */
+                        out += op;
+                        len -= op;
+                        if (len)                /* rest from output */
+                            out = copy_back(out, dist, len);
+                    }
+                    else
+                        out = copy_back(out, dist, len);
+                }
+                else if ((op & 64) == 0) {      /* 2nd level distance code */
+                    here = dcode + here->val + (hold8 & ((1U << op) - 1));
+                    goto dodist8;
+                }
+                else {
+                    strm->msg = (z_const char *)"invalid distance code";
+                    state->mode = BAD;
+                    break;
+                }
+            }
+            else if ((op & 64) == 0) {          /* 2nd level length code */
+                here = lcode + here->val + (hold8 & ((1U << op) - 1));
+                goto dolen8;
+            }
+            else if (op & 32) {                 /* end-of-block */
+                Tracevv((stderr, "inflate:         end of block\n"));
+                state->mode = TYPE;
+                break;
+            }
+            else {
+                strm->msg = (z_const char *)"invalid literal/length code";
+                state->mode = BAD;
+                break;
+            }
+        } while (in <= last8 && out <= end8);
+
+        /* return the whole bytes not used, leaving fewer than eight bits */
+        len = bits >> 3;
+        in -= len;
+        bits -= len << 3;
+        hold = (unsigned long)(hold8 & ((1U << bits) - 1));
+        if (state->mode != LEN || in >= last || out >= end)
+            goto leave;
+    }
+#endif
+
     /* decode literals and length/distances until end-of-block or not enough
        input data or output space */
     do {
@@ -287,6 +531,9 @@ void ZLIB_INTERNAL inflate_fast(z_streamp strm, unsigned start) {
         }
     } while (in < last && out < end);

+#ifdef Z_U8
+  leave:
+#endif
     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
     len = bits >> 3;
     in -= len;
diff --git a/test/infcover.c b/test/infcover.c
index 6a928a6..3254dbd 100644
--- a/test/infcover.c
+++ b/test/infcover.c
@@ -662,6 +662,54 @@ local void cover_fast(void)
         Z_STREAM_END);
 }

+/* cover the fast loop of inffast.c, which needs sixteen bytes of input and
+   room for 265 bytes of output: second-level codes with 10- and 8-bit root
+   tables, literal runs, copies at distances 1, 2..7 and 8 or more, window
+   copies (wrapped, contiguous, and with the write index at zero), and its
+   errors */
+local void cover_fast64(void)
+{
+    char *longcodes =
+        "ed ef d1 92 24 49 92 24 cb 7e 2b 5e 16 35 8f ec ff ff 0 2a 80 79 d9 "
+        "87 f3 9 f7 22 1d 96 55 1b 8f ce 5b fe 7f bb f7 fd fe fe fd ef bf ff "
+        "df ff fd 7f ff cf ff f7 ff e1 ff f9 7f fc 7f fc 1f fe ff ff bf ff ff "
+        "ff c0 ff fc ff e0 bf ff 80 0";
+    char *win12 =
+        "4b 4c 4a 4e 49 4d 4b cf c8 cc ca ce c9 cd cb 2f 28 2c 2a 2e 29 2d 2b "
+        "af a8 ac 1a 95 19 d 9b d1 b0 1a d ab d1 b0 1a d ab d1 b0 1a 75 c3 68 "
+        "58 8d 86 d5 68 cc 8f 86 d5 68 58 8d 86 d5 68 58 8d 86 d5 68 58 8d 86 "
+        "db 68 58 8d c6 d5 68 58 8d 96 d3 a3 61 35 1a 56 a3 ad ae d1 b0 1a f5 "
+        "e9 68 58 8d 86 ee 68 58 8d 86 d5 68 df 7d 34 ac 46 d3 e1 68 58 8d ba "
+        "6d 34 ac 46 c3 6a 34 45 8c 86 d5 68 6b 66 34 ac 46 5b e6 a3 61 35 1a "
+        "56 a3 e1 39 1a 56 a3 71 38 1a 56 a3 f1 3b 1a 56 a3 61 35 5a 5a 8f 86 "
+        "d5 68 8 8c 86 55 6a 5e a 0";
+    char *win9 =
+        "4b 4c 4a 4e 49 4d 4b cf c8 cc ca ce c9 cd cb 2f 28 2c 2a 2e 29 2d 2b "
+        "af a8 ac 1a 95 19 5 a3 61 35 1a e7 a3 76 8c a2 d1 f8 1f d 83 51 38 "
+        "1a 1f a3 8a 46 63 70 94 1e d cc d4 bc 14 0";
+
+    inf(longcodes, "fast long codes", 0, -15, 1000, Z_STREAM_END);
+    inf("4a 4c 4a 6 2c 25 35 2d 3d 23 33 2b 3b 27 37 2f bf a0 b0 a8 b8 a4 b4 "
+        "ac bc a2 b2 2a 31 29 39 25 35 2d 3d 23 33 2b 3b 27 37 2f bf 0 0",
+        "fast end of block", 0, -15, 300, Z_STREAM_END);
+    inf(longcodes, "long codes in small pieces", 3, -15, 100, Z_OK);
+    try(longcodes, "long codes", 0);
+    inf(win12, "fast window copies", 0, -12, 600, Z_OK);
+    inf(win9, "fast window write index zero", 0, -9, 600, Z_OK);
+    inf("4b 4c 4a 4e 49 4d 4b cf c8 cc ca ce c9 cd cb 2f 40 d8 91 98 94 9c 92 "
+        "9a 96 9e 91 99 95 9d 93 9b 97 5f 50 58 54 5c 52 5a 56 5e 51 59 95 98 "
+        "94 9c 92 9a 6 0",
+        "fast too far back", 0, -15, 300, Z_DATA_ERROR);
+    inf("4b 4c 4a 4e 49 4d 4b cf c8 cc ca ce c9 cd cb 2f 18 4b 4c 4a 4e 49 4d "
+        "4b cf c8 cc ca ce c9 cd cb 2f 28 2c 2a 2e 29 2d 2b af a8 ac 4a 4c 4a "
+        "4e 49 4d 3 0",
+        "fast invalid literal/length code", 0, -15, 300, Z_DATA_ERROR);
+    inf("4b 4c 4a 4e 49 4d 4b cf c8 cc ca ce c9 cd cb 2f 0 be c4 a4 e4 94 d4 "
+        "b4 f4 8c cc ac ec 9c dc bc fc 82 c2 a2 e2 92 d2 b2 f2 8a ca aa c4 a4 "
+        "e4 94 d4 34 0",
+        "fast invalid distance code", 0, -15, 300, Z_DATA_ERROR);
+}
+
 int main(void)
 {
     fprintf(stderr, "%s\n", zlibVersion());
@@ -671,5 +719,6 @@ int main(void)
     cover_inflate();
     cover_trees();
     cover_fast();
+    cover_fast64();
     return 0;
 }