lib/libz/0004-Backport-Unconditional-refill-for-literals-with-fast.patch
$ cat 0004-Backport-Unconditional-refill-for-literals-with-fast.patch
From bc8d6761c35275f96916238bd450296a9106528d Mon Sep 17 00:00:00 2001
From: Felix Hanau <felix@cloudflare.com>
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 @@
* jloup@gzip.org madler@alumni.caltech.edu
*
* 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