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
20 +++ b/contrib/arm/chunkcopy.h
22 +/* chunkcopy.h -- fast copies and sets
23 + * Copyright (C) 2017 ARM, Inc.
24 + * For conditions of distribution and use, see copyright notice in zlib.h
31 +#include <arm_neon.h>
33 +#if __STDC_VERSION__ >= 199901L
34 +#define Z_RESTRICT restrict
39 +typedef uint8x16_t chunkcopy_chunk_t;
40 +#define CHUNKCOPY_CHUNK_SIZE sizeof(chunkcopy_chunk_t)
43 + Ask the compiler to perform a wide, unaligned load with an machine
44 + instruction appropriate for the chunkcopy_chunk_t type.
46 +static inline chunkcopy_chunk_t loadchunk(const unsigned char FAR *s) {
47 + chunkcopy_chunk_t c;
48 + __builtin_memcpy(&c, s, sizeof(c));
53 + Ask the compiler to perform a wide, unaligned store with an machine
54 + instruction appropriate for the chunkcopy_chunk_t type.
56 +static inline void storechunk(unsigned char FAR *d, chunkcopy_chunk_t c) {
57 + __builtin_memcpy(d, &c, sizeof(c));
61 + Perform a memcpy-like operation, but assume that length is non-zero and that
62 + it's OK to overwrite at least CHUNKCOPY_CHUNK_SIZE bytes of output even if
63 + the length is shorter than this.
65 + It also guarantees that it will properly unroll the data if the distance
66 + between `out` and `from` is at least CHUNKCOPY_CHUNK_SIZE, which we rely on
67 + in chunkcopy_relaxed().
69 + Aside from better memory bus utilisation, this means that short copies
70 + (CHUNKCOPY_CHUNK_SIZE bytes or fewer) will fall straight through the loop
71 + without iteration, which will hopefully make the branch prediction more
74 +static inline unsigned char FAR *chunkcopy_core(unsigned char FAR *out,
75 + const unsigned char FAR *from,
77 + int bump = (--len % CHUNKCOPY_CHUNK_SIZE) + 1;
78 + storechunk(out, loadchunk(from));
81 + len /= CHUNKCOPY_CHUNK_SIZE;
83 + storechunk(out, loadchunk(from));
84 + out += CHUNKCOPY_CHUNK_SIZE;
85 + from += CHUNKCOPY_CHUNK_SIZE;
91 + Like chunkcopy_core, but avoid writing beyond of legal output.
93 + Accepts an additional pointer to the end of safe output. A generic safe
94 + copy would use (out + len), but it's normally the case that the end of the
95 + output buffer is beyond the end of the current copy, and this can still be
98 +static inline unsigned char FAR *chunkcopy_core_safe(unsigned char FAR *out,
99 + const unsigned char FAR * from,
101 + unsigned char FAR *limit) {
102 + Assert(out + len <= limit, "chunk copy exceeds safety limit");
103 + if (limit - out < CHUNKCOPY_CHUNK_SIZE) {
104 + const unsigned char FAR * Z_RESTRICT rfrom = from;
105 + if (len & 8) { __builtin_memcpy(out, rfrom, 8); out += 8; rfrom += 8; }
106 + if (len & 4) { __builtin_memcpy(out, rfrom, 4); out += 4; rfrom += 4; }
107 + if (len & 2) { __builtin_memcpy(out, rfrom, 2); out += 2; rfrom += 2; }
108 + if (len & 1) { *out++ = *rfrom++; }
111 + return chunkcopy_core(out, from, len);
115 + Perform short copies until distance can be rewritten as being at least
116 + CHUNKCOPY_CHUNK_SIZE.
118 + This assumes that it's OK to overwrite at least the first
119 + 2*CHUNKCOPY_CHUNK_SIZE bytes of output even if the copy is shorter than
120 + this. This assumption holds within inflate_fast() which starts every
121 + iteration with at least 258 bytes of output space available (258 being the
122 + maximum length output from a single token; see inffast.c).
124 +static inline unsigned char FAR *chunkunroll_relaxed(unsigned char FAR *out,
125 + unsigned FAR *dist,
126 + unsigned FAR *len) {
127 + const unsigned char FAR *from = out - *dist;
128 + while (*dist < *len && *dist < CHUNKCOPY_CHUNK_SIZE) {
129 + storechunk(out, loadchunk(from));
138 +static inline uint8x16_t chunkset_vld1q_dup_u8x8(const unsigned char FAR * Z_RESTRICT from) {
139 +#if defined(__clang__) || defined(__aarch64__)
140 + return vreinterpretq_u8_u64(vld1q_dup_u64((void *)from));
142 + /* 32-bit GCC uses an alignment hint for vld1q_dup_u64, even when given a
143 + * void pointer, so here's an alternate implementation.
145 + uint8x8_t h = vld1_u8(from);
146 + return vcombine_u8(h, h);
151 + Perform an overlapping copy which behaves as a memset() operation, but
152 + supporting periods other than one, and assume that length is non-zero and
153 + that it's OK to overwrite at least CHUNKCOPY_CHUNK_SIZE*3 bytes of output
154 + even if the length is shorter than this.
156 +static inline unsigned char FAR *chunkset_core(unsigned char FAR *out,
160 + int bump = ((len - 1) % sizeof(f)) + 1;
164 + f = vld1q_dup_u8(out - 1);
175 + f = vreinterpretq_u8_u16(vld1q_dup_u16((void *)(out - 2)));
180 + f = vreinterpretq_u8_u16(vld1q_dup_u16((void *)(out - 2)));
189 + f = vreinterpretq_u8_u32(vld1q_dup_u32((void *)(out - 4)));
194 + f = vreinterpretq_u8_u32(vld1q_dup_u32((void *)(out - 4)));
203 + f = chunkset_vld1q_dup_u8x8(out - 8);
208 + f = chunkset_vld1q_dup_u8x8(out - 8);
217 + out = chunkunroll_relaxed(out, &period, &len);
218 + return chunkcopy_core(out, out - period, len);
222 + Perform a memcpy-like operation, but assume that length is non-zero and that
223 + it's OK to overwrite at least CHUNKCOPY_CHUNK_SIZE bytes of output even if
224 + the length is shorter than this.
226 + Unlike chunkcopy_core() above, no guarantee is made regarding the behaviour
227 + of overlapping buffers, regardless of the distance between the pointers.
228 + This is reflected in the `restrict`-qualified pointers, allowing the
229 + compiler to reorder loads and stores.
231 +static inline unsigned char FAR *chunkcopy_relaxed(unsigned char FAR * Z_RESTRICT out,
232 + const unsigned char FAR * Z_RESTRICT from,
234 + return chunkcopy_core(out, from, len);
238 + Like chunkcopy_relaxed, but avoid writing beyond of legal output.
240 + Unlike chunkcopy_core_safe() above, no guarantee is made regarding the
241 + behaviour of overlapping buffers, regardless of the distance between the
242 + pointers. This is reflected in the `restrict`-qualified pointers, allowing
243 + the compiler to reorder loads and stores.
245 + Accepts an additional pointer to the end of safe output. A generic safe
246 + copy would use (out + len), but it's normally the case that the end of the
247 + output buffer is beyond the end of the current copy, and this can still be
250 +static inline unsigned char FAR *chunkcopy_safe(unsigned char FAR *out,
251 + const unsigned char FAR * Z_RESTRICT from,
253 + unsigned char FAR *limit) {
254 + Assert(out + len <= limit, "chunk copy exceeds safety limit");
255 + return chunkcopy_core_safe(out, from, len, limit);
259 + Perform chunky copy within the same buffer, where the source and destination
260 + may potentially overlap.
262 + Assumes that len > 0 on entry, and that it's safe to write at least
263 + CHUNKCOPY_CHUNK_SIZE*3 bytes to the output.
265 +static inline unsigned char FAR *chunkcopy_lapped_relaxed(unsigned char FAR *out,
268 + if (dist < len && dist < CHUNKCOPY_CHUNK_SIZE) {
269 + return chunkset_core(out, dist, len);
271 + return chunkcopy_core(out, out - dist, len);
275 + Behave like chunkcopy_lapped_relaxed, but avoid writing beyond of legal output.
277 + Accepts an additional pointer to the end of safe output. A generic safe
278 + copy would use (out + len), but it's normally the case that the end of the
279 + output buffer is beyond the end of the current copy, and this can still be
282 +static inline unsigned char FAR *chunkcopy_lapped_safe(unsigned char FAR *out,
285 + unsigned char FAR *limit) {
286 + Assert(out + len <= limit, "chunk copy exceeds safety limit");
287 + if (limit - out < CHUNKCOPY_CHUNK_SIZE * 3) {
288 + /* TODO: try harder to optimise this */
289 + while (len-- > 0) {
290 + *out = *(out - dist);
295 + return chunkcopy_lapped_relaxed(out, dist, len);
300 +#endif /* CHUNKCOPY_H */
301 --- a/contrib/arm/inffast.c
302 +++ b/contrib/arm/inffast.c
304 #include "inftrees.h"
307 +#include "chunkcopy.h"
310 # pragma message("Assembler code may have bugs -- use at your own risk")
311 @@ -57,6 +58,7 @@ unsigned start; /* inflate()'s s
312 unsigned char FAR *out; /* local strm->next_out */
313 unsigned char FAR *beg; /* inflate()'s initial strm->next_out */
314 unsigned char FAR *end; /* while out < end, enough space available */
315 + unsigned char FAR *limit; /* safety limit for chunky copies */
316 #ifdef INFLATE_STRICT
317 unsigned dmax; /* maximum distance from zlib header */
319 @@ -84,12 +86,13 @@ unsigned start; /* inflate()'s s
320 out = strm->next_out;
321 beg = out - (start - strm->avail_out);
322 end = out + (strm->avail_out - 257);
323 + limit = out + strm->avail_out;
324 #ifdef INFLATE_STRICT
327 wsize = state->wsize;
328 whave = state->whave;
329 - wnext = state->wnext;
330 + wnext = (state->wnext == 0 && whave >= wsize) ? wsize : state->wnext;
331 window = state->window;
334 @@ -197,70 +200,51 @@ unsigned start; /* inflate()'s s
338 - if (wnext == 0) { /* very common case */
339 - from += wsize - op;
340 - if (op < len) { /* some from window */
345 - from = out - dist; /* rest from output */
347 + if (wnext >= op) { /* contiguous in window */
348 + from += wnext - op;
350 - else if (wnext < op) { /* wrap around window */
351 - from += wsize + wnext - op;
352 + else { /* wrap around window */
354 + from += wsize - op;
355 if (op < len) { /* some from end of window */
361 - if (wnext < len) { /* some from start of window */
367 - from = out - dist; /* rest from output */
371 - else { /* contiguous in window */
372 - from += wnext - op;
373 - if (op < len) { /* some from window */
378 - from = out - dist; /* rest from output */
391 + out = chunkcopy_safe(out, from, op, limit);
392 + from = window; /* more from start of window */
394 + /* This (rare) case can create a situation where
395 + the first chunkcopy below must be checked.
399 + if (op < len) { /* still need some from output */
400 + out = chunkcopy_safe(out, from, op, limit);
402 + /* When dist is small the amount of data that can be
403 + copied from the window is also small, and progress
404 + towards the dangerous end of the output buffer is
405 + also small. This means that for trivial memsets and
406 + for chunkunroll_relaxed() a safety check is
407 + unnecessary. However, these conditions may not be
408 + entered at all, and in that case it's possible that
409 + the main copy is near the end.
411 + out = chunkunroll_relaxed(out, &dist, &len);
412 + out = chunkcopy_safe(out, out - dist, len, limit);
414 + /* from points to window, so there is no risk of
415 + overlapping pointers requiring memset-like behaviour
417 + out = chunkcopy_safe(out, from, len, limit);
421 - from = out - dist; /* copy direct from output */
422 - do { /* minimum length is three */
433 + /* Whole reference is in range of current output. No
434 + range checks are necessary because we start with room
435 + for at least 258 bytes of output, so unroll and roundoff
436 + operations can write beyond `out+len` so long as they
437 + stay within 258 bytes of `out`.
439 + out = chunkcopy_lapped_relaxed(out, dist, len);
442 else if ((op & 64) == 0) { /* 2nd level distance code */
443 --- a/contrib/arm/inflate.c
444 +++ b/contrib/arm/inflate.c
446 #include "inftrees.h"
449 +#include "contrib/arm/chunkcopy.h"
453 @@ -405,10 +406,20 @@ unsigned copy;
455 /* if it hasn't been done already, allocate space for the window */
456 if (state->window == Z_NULL) {
457 + unsigned wsize = 1U << state->wbits;
458 state->window = (unsigned char FAR *)
459 - ZALLOC(strm, 1U << state->wbits,
460 + ZALLOC(strm, wsize + CHUNKCOPY_CHUNK_SIZE,
461 sizeof(unsigned char));
462 if (state->window == Z_NULL) return 1;
463 +#ifdef INFLATE_CLEAR_UNUSED_UNDEFINED
464 + /* Copies from the overflow portion of this buffer are undefined and
465 + may cause analysis tools to raise a warning if we don't initialize
466 + it. However, this undefined data overwrites other undefined data
467 + and is subsequently either overwritten or left deliberately
468 + undefined at the end of decode; so there's really no point.
470 + memset(state->window + wsize, 0, CHUNKCOPY_CHUNK_SIZE);
474 /* if window not in use yet, initialize */
475 @@ -1175,17 +1186,16 @@ int flush;
477 from = state->window + (state->wnext - copy);
478 if (copy > state->length) copy = state->length;
479 + if (copy > left) copy = left;
480 + put = chunkcopy_safe(put, from, copy, put + left);
482 else { /* copy from output */
483 - from = put - state->offset;
484 copy = state->length;
485 + if (copy > left) copy = left;
486 + put = chunkcopy_lapped_safe(put, state->offset, copy, put + left);
488 - if (copy > left) copy = left;
490 state->length -= copy;
494 if (state->length == 0) state->mode = LEN;