lib/libz/0002-Port-ARM-inflate-performance-improvement-patches-chu.patch
$ cat 0002-Port-ARM-inflate-performance-improvement-patches-chu.patch
From 48f533726432ff3eb9c40ff087c13488fa604f54 Mon Sep 17 00:00:00 2001
From: Janakarajan Natarajan <68447808+janaknat@users.noreply.github.com>
Date: Wed, 23 Sep 2020 12:31:13 -0500
Subject: [PATCH 2/4] Port ARM inflate performance improvement patches (chunk
SIMD, read64le) (#22)
* When windowBits is zero, the size of the sliding window comes from
the zlib header. The allowed values of the four-bit field are
0..7, but when windowBits is zero, values greater than 7 are
permitted and acted upon, resulting in large, mostly unused memory
allocations. This fix rejects such invalid zlib headers.
* Add option to not compute or check check values.
The undocumented (except in these commit comments) function
inflateValidate(strm, check) can be called after an inflateInit(),
inflateInit2(), or inflateReset2() with check equal to zero to
turn off the check value (CRC-32 or Adler-32) computation and
comparison. Calling with check not equal to zero turns checking
back on. This should only be called immediately after the init or
reset function. inflateReset() does not change the state, so a
previous inflateValidate() setting will remain in effect.
This also turns off validation of the gzip header CRC when
present.
This should only be used when a zlib or gzip stream has already
been checked, and repeated decompressions of the same stream no
longer need to be validated.
* This verifies that the state has been initialized, that it is the
expected type of state, deflate or inflate, and that at least the
first several bytes of the internal state have not been clobbered.
* Use macros to represent magic numbers
This combines two patches which help in improving the readability and
maintainability of the code by making magic numbers into #defines.
Based on Chris Blume's (cblume@chromium) patches for zlib chromium:
8888511 - "Zlib: Use defines for inffast"
b9c1566 - "Share inffast names in zlib"
These patches are needed when introducing chunk SIMD NEON enchancements.
Signed-off-by: Janakarajan Natarajan <janakan@amazon.com>
* Port inflate chunk SIMD NEON patches for cloudflare
Based on 2 patches from zlib chromium fork:
* Adenilson Cavalcanti (adenilson.cavalcanti@arm.com)
3060dcb - "zlib: inflate using wider loads and stores"
* Noel Gordon (noel@chromium.org)
64ffef0 - "Improve zlib inflate speed by using SSE2 chunk copy
The two patches combined provide around 5-25% increase in inflate
performance, based on the workload, when checked with a modified
zpipe.c and the Silesia corpus.
Signed-off-by: Janakarajan Natarajan <janakan@amazon.com>
* Increase inflate speed: read decode input into a uint64_t
Update the chunk-copy code with a wide input data reader, which consumes
input in 64-bit (8 byte) chunks. Update inflate_fast_chunk_() to use the
wide reader.
Based on Noel Gordon's (noel@chromium.org) patch for the zlib chromium fork
8a8edc1 - "Increase inflate speed: read decoder input into a uint64_t"
This patch provides 7-10% inflate performance improvement when tested with a
modified zpipe.c and the Silesia corpus.
Signed-off-by: Janakarajan Natarajan <janakan@amazon.com>
Co-authored-by: Mark Adler <madler@alumni.caltech.edu>
---
Makefile.in | 4 +
chunkcopy.h | 414 ++++++++++++++++++++++++++++++++++++++++++++++++
infback.c | 3 +-
inffast.c | 11 +-
inffast.h | 4 +
inffast_chunk.c | 379 ++++++++++++++++++++++++++++++++++++++++++++
inffast_chunk.h | 48 ++++++
inflate.c | 38 ++++-
8 files changed, 895 insertions(+), 6 deletions(-)
create mode 100644 chunkcopy.h
create mode 100644 inffast_chunk.c
create mode 100644 inffast_chunk.h
diff --git a/Makefile.in b/Makefile.in
index f661801..3647d90 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -37,6 +37,10 @@ trees.o \
uncompr.o \
zutil.o \
+ifneq ($(findstring -DINFLATE_CHUNK_SIMD_NEON,$(CFLAGS)),)
+STATIC_OBJS += inffast_chunk.o
+endif
+
# TODO: What extension to use here?
SHARED_OBJS=$(STATIC_OBJS:.o=.lo)
diff --git a/chunkcopy.h b/chunkcopy.h
new file mode 100644
index 0000000..217da52
--- /dev/null
+++ b/chunkcopy.h
@@ -0,0 +1,414 @@
+/* chunkcopy.h -- fast chunk copy and set operations
+ *
+ * (C) 1995-2013 Jean-loup Gailly and Mark Adler
+ *
+ * This software is provided 'as-is', without any express or implied
+ * warranty. In no event will the authors be held liable for any damages
+ * arising from the use of this software.
+ *
+ * Permission is granted to anyone to use this software for any purpose,
+ * including commercial applications, and to alter it and redistribute it
+ * freely, subject to the following restrictions:
+ *
+ * 1. The origin of this software must not be misrepresented; you must not
+ * claim that you wrote the original software. If you use this software
+ * in a product, an acknowledgment in the product documentation would be
+ * appreciated but is not required.
+ * 2. Altered source versions must be plainly marked as such, and must not be
+ * misrepresented as being the original software.
+ * 3. This notice may not be removed or altered from any source distribution.
+ *
+ * Jean-loup Gailly Mark Adler
+ * jloup@gzip.org madler@alumni.caltech.edu
+ *
+ * Copyright (C) 2017 ARM, Inc.
+ * Copyright 2017 The Chromium Authors. All rights reserved.
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the Chromium source repository LICENSE file.
+ */
+
+#ifndef CHUNKCOPY_H
+#define CHUNKCOPY_H
+
+#include <stdint.h>
+#include "zutil.h"
+
+#define Z_STATIC_ASSERT(name, assert) typedef char name[(assert) ? 1 : -1]
+
+#if __STDC_VERSION__ >= 199901L
+#define Z_RESTRICT restrict
+#else
+#define Z_RESTRICT
+#endif
+
+#if defined(__clang__) || defined(__GNUC__) || defined(__llvm__)
+#define Z_BUILTIN_MEMCPY __builtin_memcpy
+#else
+#define Z_BUILTIN_MEMCPY zmemcpy
+#endif
+
+#if defined(INFLATE_CHUNK_SIMD_NEON)
+#include <arm_neon.h>
+typedef uint8x16_t z_vec128i_t;
+#endif
+
+/*
+ * chunk copy type: the z_vec128i_t type size should be exactly 128-bits
+ * and equal to CHUNKCOPY_CHUNK_SIZE.
+ */
+#define CHUNKCOPY_CHUNK_SIZE sizeof(z_vec128i_t)
+
+Z_STATIC_ASSERT(vector_128_bits_wide,
+ CHUNKCOPY_CHUNK_SIZE == sizeof(int8_t) * 16);
+
+/*
+ * Ask the compiler to perform a wide, unaligned load with a machine
+ * instruction appropriate for the z_vec128i_t type.
+ */
+static inline z_vec128i_t loadchunk(
+ const unsigned char FAR* s) {
+ z_vec128i_t v;
+ Z_BUILTIN_MEMCPY(&v, s, sizeof(v));
+ return v;
+}
+
+/*
+ * Ask the compiler to perform a wide, unaligned store with a machine
+ * instruction appropriate for the z_vec128i_t type.
+ */
+static inline void storechunk(
+ unsigned char FAR* d,
+ const z_vec128i_t v) {
+ Z_BUILTIN_MEMCPY(d, &v, sizeof(v));
+}
+
+/*
+ * Perform a memcpy-like operation, assuming that length is non-zero and that
+ * it's OK to overwrite at least CHUNKCOPY_CHUNK_SIZE bytes of output even if
+ * the length is shorter than this.
+ *
+ * It also guarantees that it will properly unroll the data if the distance
+ * between `out` and `from` is at least CHUNKCOPY_CHUNK_SIZE, which we rely on
+ * in chunkcopy_relaxed().
+ *
+ * Aside from better memory bus utilisation, this means that short copies
+ * (CHUNKCOPY_CHUNK_SIZE bytes or fewer) will fall straight through the loop
+ * without iteration, which will hopefully make the branch prediction more
+ * reliable.
+ */
+static inline unsigned char FAR* chunkcopy_core(
+ unsigned char FAR* out,
+ const unsigned char FAR* from,
+ unsigned len) {
+ const int bump = (--len % CHUNKCOPY_CHUNK_SIZE) + 1;
+ storechunk(out, loadchunk(from));
+ out += bump;
+ from += bump;
+ len /= CHUNKCOPY_CHUNK_SIZE;
+ while (len-- > 0) {
+ storechunk(out, loadchunk(from));
+ out += CHUNKCOPY_CHUNK_SIZE;
+ from += CHUNKCOPY_CHUNK_SIZE;
+ }
+ return out;
+}
+
+/*
+ * Like chunkcopy_core(), but avoid writing beyond of legal output.
+ *
+ * Accepts an additional pointer to the end of safe output. A generic safe
+ * copy would use (out + len), but it's normally the case that the end of the
+ * output buffer is beyond the end of the current copy, and this can still be
+ * exploited.
+ */
+static inline unsigned char FAR* chunkcopy_core_safe(
+ unsigned char FAR* out,
+ const unsigned char FAR* from,
+ unsigned len,
+ unsigned char FAR* limit) {
+ Assert(out + len <= limit, "chunk copy exceeds safety limit");
+ if ((limit - out) < (ptrdiff_t)CHUNKCOPY_CHUNK_SIZE) {
+ const unsigned char FAR* Z_RESTRICT rfrom = from;
+ if (len & 8) {
+ Z_BUILTIN_MEMCPY(out, rfrom, 8);
+ out += 8;
+ rfrom += 8;
+ }
+ if (len & 4) {
+ Z_BUILTIN_MEMCPY(out, rfrom, 4);
+ out += 4;
+ rfrom += 4;
+ }
+ if (len & 2) {
+ Z_BUILTIN_MEMCPY(out, rfrom, 2);
+ out += 2;
+ rfrom += 2;
+ }
+ if (len & 1) {
+ *out++ = *rfrom++;
+ }
+ return out;
+ }
+ return chunkcopy_core(out, from, len);
+}
+
+/*
+ * Perform short copies until distance can be rewritten as being at least
+ * CHUNKCOPY_CHUNK_SIZE.
+ *
+ * Assumes it's OK to overwrite at least the first 2*CHUNKCOPY_CHUNK_SIZE
+ * bytes of output even if the copy is shorter than this. This assumption
+ * holds within zlib inflate_fast(), which starts every iteration with at
+ * least 258 bytes of output space available (258 being the maximum length
+ * output from a single token; see inffast.c).
+ */
+static inline unsigned char FAR* chunkunroll_relaxed(
+ unsigned char FAR* out,
+ unsigned FAR* dist,
+ unsigned FAR* len) {
+ const unsigned char FAR* from = out - *dist;
+ while (*dist < *len && *dist < CHUNKCOPY_CHUNK_SIZE) {
+ storechunk(out, loadchunk(from));
+ out += *dist;
+ *len -= *dist;
+ *dist += *dist;
+ }
+ return out;
+}
+
+#if defined(INFLATE_CHUNK_SIMD_NEON)
+/*
+ * v_load64_dup(): load *src as an unaligned 64-bit int and duplicate it in
+ * every 64-bit component of the 128-bit result (64-bit int splat).
+ */
+static inline z_vec128i_t v_load64_dup(const void* src) {
+ return vcombine_u8(vld1_u8(src), vld1_u8(src));
+}
+
+/*
+ * v_load32_dup(): load *src as an unaligned 32-bit int and duplicate it in
+ * every 32-bit component of the 128-bit result (32-bit int splat).
+ */
+static inline z_vec128i_t v_load32_dup(const void* src) {
+ int32_t i32;
+ Z_BUILTIN_MEMCPY(&i32, src, sizeof(i32));
+ return vreinterpretq_u8_s32(vdupq_n_s32(i32));
+}
+
+/*
+ * v_load16_dup(): load *src as an unaligned 16-bit int and duplicate it in
+ * every 16-bit component of the 128-bit result (16-bit int splat).
+ */
+static inline z_vec128i_t v_load16_dup(const void* src) {
+ int16_t i16;
+ Z_BUILTIN_MEMCPY(&i16, src, sizeof(i16));
+ return vreinterpretq_u8_s16(vdupq_n_s16(i16));
+}
+
+/*
+ * v_load8_dup(): load the 8-bit int *src and duplicate it in every 8-bit
+ * component of the 128-bit result (8-bit int splat).
+ */
+static inline z_vec128i_t v_load8_dup(const void* src) {
+ return vld1q_dup_u8((const uint8_t*)src);
+}
+
+/*
+ * v_store_128(): store the 128-bit vec in a memory destination (that might
+ * not be 16-byte aligned) void* out.
+ */
+static inline void v_store_128(void* out, const z_vec128i_t vec) {
+ vst1q_u8(out, vec);
+}
+#endif
+
+/*
+ * Perform an overlapping copy which behaves as a memset() operation, but
+ * supporting periods other than one, and assume that length is non-zero and
+ * that it's OK to overwrite at least CHUNKCOPY_CHUNK_SIZE*3 bytes of output
+ * even if the length is shorter than this.
+ */
+static inline unsigned char FAR* chunkset_core(
+ unsigned char FAR* out,
+ unsigned period,
+ unsigned len) {
+ z_vec128i_t v;
+ const int bump = ((len - 1) % sizeof(v)) + 1;
+
+ switch (period) {
+ case 1:
+ v = v_load8_dup(out - 1);
+ v_store_128(out, v);
+ out += bump;
+ len -= bump;
+ while (len > 0) {
+ v_store_128(out, v);
+ out += sizeof(v);
+ len -= sizeof(v);
+ }
+ return out;
+ case 2:
+ v = v_load16_dup(out - 2);
+ v_store_128(out, v);
+ out += bump;
+ len -= bump;
+ if (len > 0) {
+ v = v_load16_dup(out - 2);
+ do {
+ v_store_128(out, v);
+ out += sizeof(v);
+ len -= sizeof(v);
+ } while (len > 0);
+ }
+ return out;
+ case 4:
+ v = v_load32_dup(out - 4);
+ v_store_128(out, v);
+ out += bump;
+ len -= bump;
+ if (len > 0) {
+ v = v_load32_dup(out - 4);
+ do {
+ v_store_128(out, v);
+ out += sizeof(v);
+ len -= sizeof(v);
+ } while (len > 0);
+ }
+ return out;
+ case 8:
+ v = v_load64_dup(out - 8);
+ v_store_128(out, v);
+ out += bump;
+ len -= bump;
+ if (len > 0) {
+ v = v_load64_dup(out - 8);
+ do {
+ v_store_128(out, v);
+ out += sizeof(v);
+ len -= sizeof(v);
+ } while (len > 0);
+ }
+ return out;
+ }
+ out = chunkunroll_relaxed(out, &period, &len);
+ return chunkcopy_core(out, out - period, len);
+}
+
+/*
+ * Perform a memcpy-like operation, but assume that length is non-zero and that
+ * it's OK to overwrite at least CHUNKCOPY_CHUNK_SIZE bytes of output even if
+ * the length is shorter than this.
+ *
+ * Unlike chunkcopy_core() above, no guarantee is made regarding the behaviour
+ * of overlapping buffers, regardless of the distance between the pointers.
+ * This is reflected in the `restrict`-qualified pointers, allowing the
+ * compiler to re-order loads and stores.
+ */
+static inline unsigned char FAR* chunkcopy_relaxed(
+ unsigned char FAR* Z_RESTRICT out,
+ const unsigned char FAR* Z_RESTRICT from,
+ unsigned len) {
+ return chunkcopy_core(out, from, len);
+}
+
+/*
+ * Like chunkcopy_relaxed(), but avoid writing beyond of legal output.
+ *
+ * Unlike chunkcopy_core_safe() above, no guarantee is made regarding the
+ * behaviour of overlapping buffers, regardless of the distance between the
+ * pointers. This is reflected in the `restrict`-qualified pointers, allowing
+ * the compiler to re-order loads and stores.
+ *
+ * Accepts an additional pointer to the end of safe output. A generic safe
+ * copy would use (out + len), but it's normally the case that the end of the
+ * output buffer is beyond the end of the current copy, and this can still be
+ * exploited.
+ */
+static inline unsigned char FAR* chunkcopy_safe(
+ unsigned char FAR* out,
+ const unsigned char FAR* Z_RESTRICT from,
+ unsigned len,
+ unsigned char FAR* limit) {
+ Assert(out + len <= limit, "chunk copy exceeds safety limit");
+ return chunkcopy_core_safe(out, from, len, limit);
+}
+
+/*
+ * Perform chunky copy within the same buffer, where the source and destination
+ * may potentially overlap.
+ *
+ * Assumes that len > 0 on entry, and that it's safe to write at least
+ * CHUNKCOPY_CHUNK_SIZE*3 bytes to the output.
+ */
+static inline unsigned char FAR* chunkcopy_lapped_relaxed(
+ unsigned char FAR* out,
+ unsigned dist,
+ unsigned len) {
+ if (dist < len && dist < CHUNKCOPY_CHUNK_SIZE) {
+ return chunkset_core(out, dist, len);
+ }
+ return chunkcopy_core(out, out - dist, len);
+}
+
+/*
+ * Behave like chunkcopy_lapped_relaxed(), but avoid writing beyond of legal
+ * output.
+ *
+ * Accepts an additional pointer to the end of safe output. A generic safe
+ * copy would use (out + len), but it's normally the case that the end of the
+ * output buffer is beyond the end of the current copy, and this can still be
+ * exploited.
+ */
+static inline unsigned char FAR* chunkcopy_lapped_safe(
+ unsigned char FAR* out,
+ unsigned dist,
+ unsigned len,
+ unsigned char FAR* limit) {
+ Assert(out + len <= limit, "chunk copy exceeds safety limit");
+ if ((limit - out) < (ptrdiff_t)(3 * CHUNKCOPY_CHUNK_SIZE)) {
+ /* TODO(cavalcantii): try harder to optimise this */
+ while (len-- > 0) {
+ *out = *(out - dist);
+ out++;
+ }
+ return out;
+ }
+ return chunkcopy_lapped_relaxed(out, dist, len);
+}
+
+/*
+ * The chunk-copy code above deals with writing the decoded DEFLATE data to
+ * the output with SIMD methods to increase decode speed. Reading the input
+ * to the DEFLATE decoder with a wide, SIMD method can also increase decode
+ * speed. This option is supported on little endian machines, and reads the
+ * input data in 64-bit (8 byte) chunks.
+ */
+
+#ifdef INFLATE_CHUNK_READ_64LE
+/*
+ * Buffer the input in a uint64_t (8 bytes) in the wide input reading case.
+ */
+typedef uint64_t inflate_holder_t;
+
+/*
+ * Ask the compiler to perform a wide, unaligned load of a uint64_t using a
+ * machine instruction appropriate for the uint64_t type.
+ */
+static inline inflate_holder_t read64le(const unsigned char FAR *in) {
+ inflate_holder_t input;
+ Z_BUILTIN_MEMCPY(&input, in, sizeof(input));
+ return input;
+}
+#else
+/*
+ * Otherwise, buffer the input bits using zlib's default input buffer type.
+ */
+typedef unsigned long inflate_holder_t;
+
+#endif /* INFLATE_CHUNK_READ_64LE */
+
+#undef Z_STATIC_ASSERT
+#undef Z_RESTRICT
+#undef Z_BUILTIN_MEMCPY
+
+#endif /* CHUNKCOPY_H */
diff --git a/infback.c b/infback.c
index f0a5905..f62bb77 100644
--- a/infback.c
+++ b/infback.c
@@ -427,7 +427,8 @@ int ZEXPORT inflateBack(z_stream *strm,
case LEN:
/* use inflate_fast() if we have enough input and output */
- if (have >= 6 && left >= 258) {
+ if (have >= INFLATE_FAST_MIN_INPUT &&
+ left >= INFLATE_FAST_MIN_OUTPUT) {
RESTORE();
if (state->whave < state->wsize)
state->whave = state->wsize - left;
diff --git a/inffast.c b/inffast.c
index 5420b2c..5f196de 100644
--- a/inffast.c
+++ b/inffast.c
@@ -74,10 +74,10 @@ void ZLIB_INTERNAL inflate_fast(
/* copy state to local variables */
state = (struct inflate_state *)strm->state;
in = strm->next_in;
- last = in + (strm->avail_in - 5);
+ last = in + (strm->avail_in - (INFLATE_FAST_MIN_INPUT - 1));
out = strm->next_out;
beg = out - (start - strm->avail_out);
- end = out + (strm->avail_out - 257);
+ end = out + (strm->avail_out - (INFLATE_FAST_MIN_OUTPUT - 1));
dmax = state->dmax;
wsize = state->wsize;
whave = state->whave;
@@ -269,9 +269,12 @@ void ZLIB_INTERNAL inflate_fast(
/* update state and return */
strm->next_in = in;
strm->next_out = out;
- strm->avail_in = (unsigned int)(in < last ? 5 + (last - in) : 5 - (in - last));
+ strm->avail_in = (unsigned int)(in < last ?
+ (INFLATE_FAST_MIN_INPUT - 1) + (last - in) :
+ (INFLATE_FAST_MIN_INPUT - 1) - (in - last));
strm->avail_out = (unsigned int)(out < end ?
- 257 + (end - out) : 257 - (out - end));
+ (INFLATE_FAST_MIN_OUTPUT - 1) + (end - out) :
+ (INFLATE_FAST_MIN_OUTPUT - 1) - (out - end));
state->hold = hold;
state->bits = bits;
}
diff --git a/inffast.h b/inffast.h
index 5d2a82e..4463d20 100644
--- a/inffast.h
+++ b/inffast.h
@@ -8,4 +8,8 @@
subject to change. Applications should only use zlib.h.
*/
+/* Minimum input and output needed for a fast inflate iteration. */
+#define INFLATE_FAST_MIN_INPUT 6
+#define INFLATE_FAST_MIN_OUTPUT 258
+
void ZLIB_INTERNAL inflate_fast(z_stream *strm, unsigned int start);
diff --git a/inffast_chunk.c b/inffast_chunk.c
new file mode 100644
index 0000000..d80c9a7
--- /dev/null
+++ b/inffast_chunk.c
@@ -0,0 +1,379 @@
+/* inffast_chunk.c -- fast decoding
+ *
+ * (C) 1995-2013 Jean-loup Gailly and Mark Adler
+ *
+ * This software is provided 'as-is', without any express or implied
+ * warranty. In no event will the authors be held liable for any damages
+ * arising from the use of this software.
+ *
+ * Permission is granted to anyone to use this software for any purpose,
+ * including commercial applications, and to alter it and redistribute it
+ * freely, subject to the following restrictions:
+ *
+ * 1. The origin of this software must not be misrepresented; you must not
+ * claim that you wrote the original software. If you use this software
+ * in a product, an acknowledgment in the product documentation would be
+ * appreciated but is not required.
+ * 2. Altered source versions must be plainly marked as such, and must not be
+ * misrepresented as being the original software.
+ * 3. This notice may not be removed or altered from any source distribution.
+ *
+ * Jean-loup Gailly Mark Adler
+ * jloup@gzip.org madler@alumni.caltech.edu
+ *
+ * Copyright (C) 1995-2017 Mark Adler
+ * For conditions of distribution and use, see copyright notice in zlib.h
+ */
+
+#include "zutil.h"
+#include "inftrees.h"
+#include "inflate.h"
+#include "inffast_chunk.h"
+#include "chunkcopy.h"
+
+#ifdef ASMINF
+# pragma message("Assembler code may have bugs -- use at your own risk")
+#else
+
+/*
+ Decode literal, length, and distance codes and write out the resulting
+ literal and match bytes until either not enough input or output is
+ available, an end-of-block is encountered, or a data error is encountered.
+ When large enough input and output buffers are supplied to inflate(), for
+ example, a 16K input buffer and a 64K output buffer, more than 95% of the
+ inflate() execution time is spent in this routine.
+
+ 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)
+ start >= strm->avail_out
+ state->bits < 8
+ strm->next_out[0..strm->avail_out] does not overlap with
+ strm->next_in[0..strm->avail_in]
+ strm->state->window is allocated with an additional
+ CHUNKCOPY_CHUNK_SIZE-1 bytes of padding beyond strm->state->wsize
+
+ On return, state->mode is one of:
+
+ LEN -- ran out of enough output space or enough available input
+ TYPE -- reached end of block code, inflate() to interpret next block
+ BAD -- error in block data
+
+ Notes:
+
+ INFLATE_FAST_MIN_INPUT: 6 or 8 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,
+ and 13 bits for the distance extra. This totals 48 bits, or six bytes.
+ Therefore if strm->avail_in >= 6, then there is enough input to avoid
+ checking for available input while decoding.
+
+ - The wide input data reading option reads 64 input bits at a time. Thus,
+ if strm->avail_in >= 8, then there is enough input to avoid checking for
+ available input while decoding. Reading consumes the input with:
+
+ hold |= read64le(in) << bits;
+ in += 6;
+ bits += 48;
+
+ reporting 6 bytes of new input because |bits| is 0..15 (2 bytes rounded
+ up, worst case) and 6 bytes is enough to decode as noted above. At exit,
+ hold &= (1U << bits) - 1 drops excess input to keep the invariant:
+
+ (state->hold >> state->bits) == 0
+
+ INFLATE_FAST_MIN_OUTPUT: 258 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
+ available output space while decoding.
+ */
+void ZLIB_INTERNAL inflate_fast_chunk_(strm, start)
+z_streamp strm;
+unsigned start; /* inflate()'s starting value for strm->avail_out */
+{
+ struct inflate_state FAR *state;
+ z_const unsigned char FAR *in; /* local strm->next_in */
+ z_const unsigned char FAR *last; /* have enough input while in < last */
+ unsigned char FAR *out; /* local strm->next_out */
+ unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
+ unsigned char FAR *end; /* while out < end, enough space available */
+ unsigned char FAR *limit; /* safety limit for chunky copies */
+#ifdef INFLATE_STRICT
+ unsigned dmax; /* maximum distance from zlib header */
+#endif
+ unsigned wsize; /* window size or zero if not using window */
+ unsigned whave; /* valid bytes in the window */
+ unsigned wnext; /* window write index */
+ unsigned char FAR *window; /* allocated sliding window, if wsize != 0 */
+ inflate_holder_t hold; /* local strm->hold */
+ unsigned bits; /* local strm->bits */
+ code const FAR *lcode; /* local strm->lencode */
+ code const FAR *dcode; /* local strm->distcode */
+ unsigned lmask; /* mask for first level of length codes */
+ unsigned dmask; /* mask for first level of distance codes */
+ code here; /* retrieved table entry */
+ unsigned op; /* code bits, operation, extra bits, or */
+ /* window position, window bytes to copy */
+ unsigned len; /* match length, unused bytes */
+ unsigned dist; /* match distance */
+ unsigned char FAR *from; /* where to copy match from */
+
+ /* copy state to local variables */
+ state = (struct inflate_state FAR *)strm->state;
+ in = strm->next_in;
+ last = in + (strm->avail_in - (INFLATE_FAST_MIN_INPUT - 1));
+ out = strm->next_out;
+ beg = out - (start - strm->avail_out);
+ end = out + (strm->avail_out - (INFLATE_FAST_MIN_OUTPUT - 1));
+ limit = out + strm->avail_out;
+#ifdef INFLATE_STRICT
+ dmax = state->dmax;
+#endif
+ wsize = state->wsize;
+ whave = state->whave;
+ wnext = (state->wnext == 0 && whave >= wsize) ? wsize : state->wnext;
+ window = state->window;
+ hold = state->hold;
+ bits = state->bits;
+ lcode = state->lencode;
+ dcode = state->distcode;
+ lmask = (1U << state->lenbits) - 1;
+ dmask = (1U << state->distbits) - 1;
+
+ /* 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;
+#else
+ hold += (unsigned long)(*in++) << bits;
+ bits += 8;
+ hold += (unsigned long)(*in++) << bits;
+ bits += 8;
+#endif
+ }
+ here = lcode[hold & lmask];
+ dolen:
+ op = (unsigned)(here.bits);
+ hold >>= op;
+ bits -= op;
+ op = (unsigned)(here.op);
+ if (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);
+ }
+ else if (op & 16) { /* length base */
+ len = (unsigned)(here.val);
+ op &= 15; /* number of extra bits */
+ if (op) {
+ 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
+ }
+ len += (unsigned)hold & ((1U << op) - 1);
+ hold >>= op;
+ bits -= op;
+ }
+ Tracevv((stderr, "inflate: length %u\n", len));
+ 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
+ }
+ here = dcode[hold & dmask];
+ dodist:
+ op = (unsigned)(here.bits);
+ hold >>= op;
+ bits -= op;
+ op = (unsigned)(here.op);
+ if (op & 16) { /* distance base */
+ dist = (unsigned)(here.val);
+ op &= 15; /* number of extra bits */
+ if (bits < op) {
+#ifdef INFLATE_CHUNK_READ_64LE
+ hold |= read64le(in) << bits;
+ in += 6;
+ bits += 48;
+#else
+ hold += (unsigned long)(*in++) << bits;
+ bits += 8;
+ if (bits < op) {
+ hold += (unsigned long)(*in++) << bits;
+ bits += 8;
+ }
+#endif
+ }
+ dist += (unsigned)hold & ((1U << op) - 1);
+#ifdef INFLATE_STRICT
+ if (dist > dmax) {
+ strm->msg = (char *)"invalid distance too far back";
+ state->mode = BAD;
+ break;
+ }
+#endif
+ hold >>= 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 =
+ (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) {
+ from = out - dist;
+ do {
+ *out++ = *from++;
+ } while (--len);
+ continue;
+ }
+#endif
+ }
+ from = window;
+ if (wnext >= op) { /* contiguous in window */
+ from += wnext - op;
+ }
+ else { /* wrap around window */
+ op -= wnext;
+ from += wsize - op;
+ if (op < len) { /* some from end of window */
+ len -= op;
+ out = chunkcopy_safe(out, from, op, limit);
+ from = window; /* more from start of window */
+ op = wnext;
+ /* This (rare) case can create a situation where
+ the first chunkcopy below must be checked.
+ */
+ }
+ }
+ if (op < len) { /* still need some from output */
+ out = chunkcopy_safe(out, from, op, limit);
+ len -= op;
+ /* When dist is small the amount of data that can be
+ copied from the window is also small, and progress
+ towards the dangerous end of the output buffer is
+ also small. This means that for trivial memsets and
+ for chunkunroll_relaxed() a safety check is
+ unnecessary. However, these conditions may not be
+ entered at all, and in that case it's possible that
+ the main copy is near the end.
+ */
+ out = chunkunroll_relaxed(out, &dist, &len);
+ out = chunkcopy_safe(out, out - dist, len, limit);
+ } else {
+ /* from points to window, so there is no risk of
+ overlapping pointers requiring memset-like behaviour
+ */
+ out = chunkcopy_safe(out, from, len, limit);
+ }
+ }
+ else {
+ /* Whole reference is in range of current output. No
+ range checks are necessary because we start with room
+ for at least 258 bytes of output, so unroll and roundoff
+ operations can write beyond `out+len` so long as they
+ stay within 258 bytes of `out`.
+ */
+ out = chunkcopy_lapped_relaxed(out, dist, len);
+ }
+ }
+ else if ((op & 64) == 0) { /* 2nd level distance code */
+ here = dcode[here.val + (hold & ((1U << op) - 1))];
+ goto dodist;
+ }
+ else {
+ strm->msg = (char *)"invalid distance code";
+ state->mode = BAD;
+ break;
+ }
+ }
+ else if ((op & 64) == 0) { /* 2nd level length code */
+ here = lcode[here.val + (hold & ((1U << op) - 1))];
+ goto dolen;
+ }
+ else if (op & 32) { /* end-of-block */
+ Tracevv((stderr, "inflate: end of block\n"));
+ state->mode = TYPE;
+ break;
+ }
+ else {
+ strm->msg = (char *)"invalid literal/length code";
+ state->mode = BAD;
+ break;
+ }
+ } while (in < last && out < end);
+
+ /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
+ len = bits >> 3;
+ in -= len;
+ bits -= len << 3;
+ hold &= (1U << bits) - 1;
+
+ /* update state and return */
+ strm->next_in = in;
+ strm->next_out = out;
+ strm->avail_in = (unsigned)(in < last ?
+ (INFLATE_FAST_MIN_INPUT - 1) + (last - in) :
+ (INFLATE_FAST_MIN_INPUT - 1) - (in - last));
+ strm->avail_out = (unsigned)(out < end ?
+ (INFLATE_FAST_MIN_OUTPUT - 1) + (end - out) :
+ (INFLATE_FAST_MIN_OUTPUT - 1) - (out - end));
+ state->hold = hold;
+ state->bits = bits;
+
+ Assert((state->hold >> state->bits) == 0, "invalid input data state");
+ return;
+}
+
+/*
+ inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
+ - Using bit fields for code structure
+ - Different op definition to avoid & for extra bits (do & for table bits)
+ - Three separate decoding do-loops for direct, window, and wnext == 0
+ - Special case for distance > 1 copies to do overlapped load and store copy
+ - Explicit branch predictions (based on measured branch probabilities)
+ - Deferring match copy and interspersed it with decoding subsequent codes
+ - Swapping literal/length else
+ - Swapping window/direct else
+ - Larger unrolled copy loops (three is about right)
+ - Moving len -= 3 statement into middle of loop
+ */
+
+#endif /* !ASMINF */
diff --git a/inffast_chunk.h b/inffast_chunk.h
new file mode 100644
index 0000000..de6aa0d
--- /dev/null
+++ b/inffast_chunk.h
@@ -0,0 +1,48 @@
+/* inffast_chunk.h -- header to use inffast_chunk.c
+ *
+ * (C) 1995-2013 Jean-loup Gailly and Mark Adler
+ *
+ * This software is provided 'as-is', without any express or implied
+ * warranty. In no event will the authors be held liable for any damages
+ * arising from the use of this software.
+ *
+ * Permission is granted to anyone to use this software for any purpose,
+ * including commercial applications, and to alter it and redistribute it
+ * freely, subject to the following restrictions:
+ *
+ * 1. The origin of this software must not be misrepresented; you must not
+ * claim that you wrote the original software. If you use this software
+ * in a product, an acknowledgment in the product documentation would be
+ * appreciated but is not required.
+ * 2. Altered source versions must be plainly marked as such, and must not be
+ * misrepresented as being the original software.
+ * 3. This notice may not be removed or altered from any source distribution.
+ *
+ * Jean-loup Gailly Mark Adler
+ * jloup@gzip.org madler@alumni.caltech.edu
+ *
+ * Copyright (C) 1995-2003, 2010 Mark Adler
+ * Copyright (C) 2017 ARM, Inc.
+ * For conditions of distribution and use, see copyright notice in zlib.h
+ */
+
+/* WARNING: this file should *not* be used by applications. It is
+ part of the implementation of the compression library and is
+ subject to change. Applications should only use zlib.h.
+ */
+
+#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
+ 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).
+*/
+#ifdef INFLATE_CHUNK_READ_64LE
+#undef INFLATE_FAST_MIN_INPUT
+#define INFLATE_FAST_MIN_INPUT 8
+#endif
+
+void ZLIB_INTERNAL inflate_fast_chunk_ OF((z_streamp strm, unsigned start));
diff --git a/inflate.c b/inflate.c
index 33b66c8..626488c 100644
--- a/inflate.c
+++ b/inflate.c
@@ -83,7 +83,12 @@
#include "zutil.h"
#include "inftrees.h"
#include "inflate.h"
+#ifdef INFLATE_CHUNK_SIMD_NEON
+#include "inffast_chunk.h"
+#include "chunkcopy.h"
+#else
#include "inffast.h"
+#endif
/* function prototypes */
static void fixedtables(struct inflate_state *state);
@@ -260,9 +265,16 @@ static int updatewindow(z_stream *strm,
/* if it hasn't been done already, allocate space for the window */
if (state->window == NULL) {
+#ifdef INFLATE_CHUNK_SIMD_NEON
+ unsigned int wsize = 1U << state->wbits;
+ state->window = (unsigned char *)
+ z_stream_alloc(strm, wsize + CHUNKCOPY_CHUNK_SIZE);
+ if (state->window == NULL) return 1;
+#else
state->window = (unsigned char *)
z_stream_alloc(strm, 1U << state->wbits);
if (state->window == NULL) return 1;
+#endif
}
/* if window not in use yet, initialize */
@@ -876,9 +888,14 @@ int ZEXPORT inflate(z_stream *strm,
case LEN_:
state->mode = LEN;
case LEN:
- if (have >= 6 && left >= 258) {
+ if (have >= INFLATE_FAST_MIN_INPUT &&
+ left >= INFLATE_FAST_MIN_OUTPUT) {
RESTORE();
+#ifdef INFLATE_CHUNK_SIMD_NEON
+ inflate_fast_chunk_(strm, out);
+#else
inflate_fast(strm, out);
+#endif
LOAD();
if (state->mode == TYPE)
state->back = -1;
@@ -994,6 +1011,18 @@ int ZEXPORT inflate(z_stream *strm,
else
from = state->window + (state->wnext - copy);
if (copy > state->length) copy = state->length;
+#ifdef INFLATE_CHUNK_SIMD_NEON
+ if (copy > left) copy = left;
+ put = chunkcopy_safe(put, from, copy, put + left);
+ }
+ else { /* copy from output */
+ copy = state->length;
+ if (copy > left) copy = left;
+ put = chunkcopy_lapped_safe(put, state->offset, copy, put + left);
+ }
+ left -= copy;
+ state->length -= copy;
+#else
}
else { /* copy from output */
from = put - state->offset;
@@ -1005,6 +1034,7 @@ int ZEXPORT inflate(z_stream *strm,
do {
*put++ = *from++;
} while (--copy);
+#endif
if (state->length == 0) state->mode = LEN;
break;
case LIT:
@@ -1064,6 +1094,12 @@ int ZEXPORT inflate(z_stream *strm,
Note: a memory error from inflate() is non-recoverable.
*/
inf_leave:
+#ifdef INFLATE_CHUNK_SIMD_NEON
+ if (left >= CHUNKCOPY_CHUNK_SIZE)
+ memset(put, 0x55, CHUNKCOPY_CHUNK_SIZE);
+ else
+ memset(put, 0x55, left);
+#endif
RESTORE();
if (state->wsize || (out != strm->avail_out && state->mode < BAD &&
(state->mode < CHECK || flush != Z_FINISH)))
--
2.55.0