1 From 247147654fe5cd11cf15d8dff91440405ea57040 Mon Sep 17 00:00:00 2001
2 From: Simon Hosie <simon.hosie@arm.com>
3 Date: Wed, 12 Apr 2017 15:44:21 -0700
4 Subject: [PATCH 2/2] Inflate using wider loads and stores
6 In inflate_fast() the output pointer always has plenty of room to write. This
7 means that so long as the target is capable, wide un-aligned loads and stores
8 can be used to transfer several bytes at once. When the reference distance is
9 too short simply unroll the data a little to increase the distance.
11 Change-Id: I59854eb25d2b1e43561c8a2afaf9175bf10cf674
13 contrib/arm/chunkcopy.h | 279 ++++++++++++++++++++++++++++++++++++++++++++++++
14 contrib/arm/inffast.c | 96 +++++++----------
15 contrib/arm/inflate.c | 22 ++--
16 3 files changed, 335 insertions(+), 62 deletions(-)
17 create mode 100644 contrib/arm/chunkcopy.h
19 diff --git a/contrib/arm/chunkcopy.h b/contrib/arm/chunkcopy.h
21 index 00000000..2d6fd6f9
23 +++ b/contrib/arm/chunkcopy.h
25 +/* chunkcopy.h -- fast copies and sets
26 + * Copyright (C) 2017 ARM, Inc.
27 + * For conditions of distribution and use, see copyright notice in zlib.h
34 +#include <arm_neon.h>
36 +#if __STDC_VERSION__ >= 199901L
37 +#define Z_RESTRICT restrict
42 +typedef uint8x16_t chunkcopy_chunk_t;
43 +#define CHUNKCOPY_CHUNK_SIZE sizeof(chunkcopy_chunk_t)
46 + Ask the compiler to perform a wide, unaligned load with an machine
47 + instruction appropriate for the chunkcopy_chunk_t type.
49 +static inline chunkcopy_chunk_t loadchunk(const unsigned char FAR *s) {
50 + chunkcopy_chunk_t c;
51 + __builtin_memcpy(&c, s, sizeof(c));
56 + Ask the compiler to perform a wide, unaligned store with an machine
57 + instruction appropriate for the chunkcopy_chunk_t type.
59 +static inline void storechunk(unsigned char FAR *d, chunkcopy_chunk_t c) {
60 + __builtin_memcpy(d, &c, sizeof(c));
64 + Perform a memcpy-like operation, but assume that length is non-zero and that
65 + it's OK to overwrite at least CHUNKCOPY_CHUNK_SIZE bytes of output even if
66 + the length is shorter than this.
68 + It also guarantees that it will properly unroll the data if the distance
69 + between `out` and `from` is at least CHUNKCOPY_CHUNK_SIZE, which we rely on
70 + in chunkcopy_relaxed().
72 + Aside from better memory bus utilisation, this means that short copies
73 + (CHUNKCOPY_CHUNK_SIZE bytes or fewer) will fall straight through the loop
74 + without iteration, which will hopefully make the branch prediction more
77 +static inline unsigned char FAR *chunkcopy_core(unsigned char FAR *out,
78 + const unsigned char FAR *from,
80 + int bump = (--len % CHUNKCOPY_CHUNK_SIZE) + 1;
81 + storechunk(out, loadchunk(from));
84 + len /= CHUNKCOPY_CHUNK_SIZE;
86 + storechunk(out, loadchunk(from));
87 + out += CHUNKCOPY_CHUNK_SIZE;
88 + from += CHUNKCOPY_CHUNK_SIZE;
94 + Like chunkcopy_core, but avoid writing beyond of legal output.
96 + Accepts an additional pointer to the end of safe output. A generic safe
97 + copy would use (out + len), but it's normally the case that the end of the
98 + output buffer is beyond the end of the current copy, and this can still be
101 +static inline unsigned char FAR *chunkcopy_core_safe(unsigned char FAR *out,
102 + const unsigned char FAR * from,
104 + unsigned char FAR *limit) {
105 + Assert(out + len <= limit, "chunk copy exceeds safety limit");
106 + if (limit - out < CHUNKCOPY_CHUNK_SIZE) {
107 + const unsigned char FAR * Z_RESTRICT rfrom = from;
108 + if (len & 8) { __builtin_memcpy(out, rfrom, 8); out += 8; rfrom += 8; }
109 + if (len & 4) { __builtin_memcpy(out, rfrom, 4); out += 4; rfrom += 4; }
110 + if (len & 2) { __builtin_memcpy(out, rfrom, 2); out += 2; rfrom += 2; }
111 + if (len & 1) { *out++ = *rfrom++; }
114 + return chunkcopy_core(out, from, len);
118 + Perform short copies until distance can be rewritten as being at least
119 + CHUNKCOPY_CHUNK_SIZE.
121 + This assumes that it's OK to overwrite at least the first
122 + 2*CHUNKCOPY_CHUNK_SIZE bytes of output even if the copy is shorter than
123 + this. This assumption holds within inflate_fast() which starts every
124 + iteration with at least 258 bytes of output space available (258 being the
125 + maximum length output from a single token; see inffast.c).
127 +static inline unsigned char FAR *chunkunroll_relaxed(unsigned char FAR *out,
128 + unsigned FAR *dist,
129 + unsigned FAR *len) {
130 + const unsigned char FAR *from = out - *dist;
131 + while (*dist < *len && *dist < CHUNKCOPY_CHUNK_SIZE) {
132 + storechunk(out, loadchunk(from));
141 +static inline uint8x16_t chunkset_vld1q_dup_u8x8(const unsigned char FAR * Z_RESTRICT from) {
142 +#if defined(__clang__) || defined(__aarch64__)
143 + return vreinterpretq_u8_u64(vld1q_dup_u64((void *)from));
145 + /* 32-bit GCC uses an alignment hint for vld1q_dup_u64, even when given a
146 + * void pointer, so here's an alternate implementation.
148 + uint8x8_t h = vld1_u8(from);
149 + return vcombine_u8(h, h);
154 + Perform an overlapping copy which behaves as a memset() operation, but
155 + supporting periods other than one, and assume that length is non-zero and
156 + that it's OK to overwrite at least CHUNKCOPY_CHUNK_SIZE*3 bytes of output
157 + even if the length is shorter than this.
159 +static inline unsigned char FAR *chunkset_core(unsigned char FAR *out,
163 + int bump = ((len - 1) % sizeof(f)) + 1;
167 + f = vld1q_dup_u8(out - 1);
178 + f = vreinterpretq_u8_u16(vld1q_dup_u16((void *)(out - 2)));
183 + f = vreinterpretq_u8_u16(vld1q_dup_u16((void *)(out - 2)));
192 + f = vreinterpretq_u8_u32(vld1q_dup_u32((void *)(out - 4)));
197 + f = vreinterpretq_u8_u32(vld1q_dup_u32((void *)(out - 4)));
206 + f = chunkset_vld1q_dup_u8x8(out - 8);
211 + f = chunkset_vld1q_dup_u8x8(out - 8);
220 + out = chunkunroll_relaxed(out, &period, &len);
221 + return chunkcopy_core(out, out - period, len);
225 + Perform a memcpy-like operation, but assume that length is non-zero and that
226 + it's OK to overwrite at least CHUNKCOPY_CHUNK_SIZE bytes of output even if
227 + the length is shorter than this.
229 + Unlike chunkcopy_core() above, no guarantee is made regarding the behaviour
230 + of overlapping buffers, regardless of the distance between the pointers.
231 + This is reflected in the `restrict`-qualified pointers, allowing the
232 + compiler to reorder loads and stores.
234 +static inline unsigned char FAR *chunkcopy_relaxed(unsigned char FAR * Z_RESTRICT out,
235 + const unsigned char FAR * Z_RESTRICT from,
237 + return chunkcopy_core(out, from, len);
241 + Like chunkcopy_relaxed, but avoid writing beyond of legal output.
243 + Unlike chunkcopy_core_safe() above, no guarantee is made regarding the
244 + behaviour of overlapping buffers, regardless of the distance between the
245 + pointers. This is reflected in the `restrict`-qualified pointers, allowing
246 + the compiler to reorder loads and stores.
248 + Accepts an additional pointer to the end of safe output. A generic safe
249 + copy would use (out + len), but it's normally the case that the end of the
250 + output buffer is beyond the end of the current copy, and this can still be
253 +static inline unsigned char FAR *chunkcopy_safe(unsigned char FAR *out,
254 + const unsigned char FAR * Z_RESTRICT from,
256 + unsigned char FAR *limit) {
257 + Assert(out + len <= limit, "chunk copy exceeds safety limit");
258 + return chunkcopy_core_safe(out, from, len, limit);
262 + Perform chunky copy within the same buffer, where the source and destination
263 + may potentially overlap.
265 + Assumes that len > 0 on entry, and that it's safe to write at least
266 + CHUNKCOPY_CHUNK_SIZE*3 bytes to the output.
268 +static inline unsigned char FAR *chunkcopy_lapped_relaxed(unsigned char FAR *out,
271 + if (dist < len && dist < CHUNKCOPY_CHUNK_SIZE) {
272 + return chunkset_core(out, dist, len);
274 + return chunkcopy_core(out, out - dist, len);
278 + Behave like chunkcopy_lapped_relaxed, but avoid writing beyond of legal output.
280 + Accepts an additional pointer to the end of safe output. A generic safe
281 + copy would use (out + len), but it's normally the case that the end of the
282 + output buffer is beyond the end of the current copy, and this can still be
285 +static inline unsigned char FAR *chunkcopy_lapped_safe(unsigned char FAR *out,
288 + unsigned char FAR *limit) {
289 + Assert(out + len <= limit, "chunk copy exceeds safety limit");
290 + if (limit - out < CHUNKCOPY_CHUNK_SIZE * 3) {
291 + /* TODO: try harder to optimise this */
292 + while (len-- > 0) {
293 + *out = *(out - dist);
298 + return chunkcopy_lapped_relaxed(out, dist, len);
303 +#endif /* CHUNKCOPY_H */
304 diff --git a/contrib/arm/inffast.c b/contrib/arm/inffast.c
305 index 0dbd1dbc..f7f50071 100644
306 --- a/contrib/arm/inffast.c
307 +++ b/contrib/arm/inffast.c
309 #include "inftrees.h"
312 +#include "chunkcopy.h"
315 # pragma message("Assembler code may have bugs -- use at your own risk")
316 @@ -57,6 +58,7 @@ unsigned start; /* inflate()'s starting value for strm->avail_out */
317 unsigned char FAR *out; /* local strm->next_out */
318 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
319 unsigned char FAR *end; /* while out < end, enough space available */
320 + unsigned char FAR *limit; /* safety limit for chunky copies */
321 #ifdef INFLATE_STRICT
322 unsigned dmax; /* maximum distance from zlib header */
324 @@ -84,12 +86,13 @@ unsigned start; /* inflate()'s starting value for strm->avail_out */
325 out = strm->next_out;
326 beg = out - (start - strm->avail_out);
327 end = out + (strm->avail_out - 257);
328 + limit = out + strm->avail_out;
329 #ifdef INFLATE_STRICT
332 wsize = state->wsize;
333 whave = state->whave;
334 - wnext = state->wnext;
335 + wnext = (state->wnext == 0 && whave >= wsize) ? wsize : state->wnext;
336 window = state->window;
339 @@ -197,70 +200,51 @@ unsigned start; /* inflate()'s starting value for strm->avail_out */
343 - if (wnext == 0) { /* very common case */
344 - from += wsize - op;
345 - if (op < len) { /* some from window */
350 - from = out - dist; /* rest from output */
352 + if (wnext >= op) { /* contiguous in window */
353 + from += wnext - op;
355 - else if (wnext < op) { /* wrap around window */
356 - from += wsize + wnext - op;
357 + else { /* wrap around window */
359 + from += wsize - op;
360 if (op < len) { /* some from end of window */
366 - if (wnext < len) { /* some from start of window */
372 - from = out - dist; /* rest from output */
374 + out = chunkcopy_safe(out, from, op, limit);
375 + from = window; /* more from start of window */
377 + /* This (rare) case can create a situation where
378 + the first chunkcopy below must be checked.
382 - else { /* contiguous in window */
383 - from += wnext - op;
384 - if (op < len) { /* some from window */
389 - from = out - dist; /* rest from output */
402 + if (op < len) { /* still need some from output */
403 + out = chunkcopy_safe(out, from, op, limit);
405 + /* When dist is small the amount of data that can be
406 + copied from the window is also small, and progress
407 + towards the dangerous end of the output buffer is
408 + also small. This means that for trivial memsets and
409 + for chunkunroll_relaxed() a safety check is
410 + unnecessary. However, these conditions may not be
411 + entered at all, and in that case it's possible that
412 + the main copy is near the end.
414 + out = chunkunroll_relaxed(out, &dist, &len);
415 + out = chunkcopy_safe(out, out - dist, len, limit);
417 + /* from points to window, so there is no risk of
418 + overlapping pointers requiring memset-like behaviour
420 + out = chunkcopy_safe(out, from, len, limit);
424 - from = out - dist; /* copy direct from output */
425 - do { /* minimum length is three */
436 + /* Whole reference is in range of current output. No
437 + range checks are necessary because we start with room
438 + for at least 258 bytes of output, so unroll and roundoff
439 + operations can write beyond `out+len` so long as they
440 + stay within 258 bytes of `out`.
442 + out = chunkcopy_lapped_relaxed(out, dist, len);
445 else if ((op & 64) == 0) { /* 2nd level distance code */
446 diff --git a/contrib/arm/inflate.c b/contrib/arm/inflate.c
447 index ac333e8c..e40322c3 100644
448 --- a/contrib/arm/inflate.c
449 +++ b/contrib/arm/inflate.c
451 #include "inftrees.h"
454 +#include "contrib/arm/chunkcopy.h"
458 @@ -405,10 +406,20 @@ unsigned copy;
460 /* if it hasn't been done already, allocate space for the window */
461 if (state->window == Z_NULL) {
462 + unsigned wsize = 1U << state->wbits;
463 state->window = (unsigned char FAR *)
464 - ZALLOC(strm, 1U << state->wbits,
465 + ZALLOC(strm, wsize + CHUNKCOPY_CHUNK_SIZE,
466 sizeof(unsigned char));
467 if (state->window == Z_NULL) return 1;
468 +#ifdef INFLATE_CLEAR_UNUSED_UNDEFINED
469 + /* Copies from the overflow portion of this buffer are undefined and
470 + may cause analysis tools to raise a warning if we don't initialize
471 + it. However, this undefined data overwrites other undefined data
472 + and is subsequently either overwritten or left deliberately
473 + undefined at the end of decode; so there's really no point.
475 + memset(state->window + wsize, 0, CHUNKCOPY_CHUNK_SIZE);
479 /* if window not in use yet, initialize */
480 @@ -1175,17 +1186,16 @@ int flush;
482 from = state->window + (state->wnext - copy);
483 if (copy > state->length) copy = state->length;
484 + if (copy > left) copy = left;
485 + put = chunkcopy_safe(put, from, copy, put + left);
487 else { /* copy from output */
488 - from = put - state->offset;
489 copy = state->length;
490 + if (copy > left) copy = left;
491 + put = chunkcopy_lapped_safe(put, state->offset, copy, put + left);
493 - if (copy > left) copy = left;
495 state->length -= copy;
499 if (state->length == 0) state->mode = LEN;