package/libs/zlib/patches/003-arm-specific-optimisations-for-inflate.patch

   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
   5
   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.
  10
  11 Change-Id: I59854eb25d2b1e43561c8a2afaf9175bf10cf674
  12 ---
  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
  18
  19 diff --git a/contrib/arm/chunkcopy.h b/contrib/arm/chunkcopy.h
  20 new file mode 100644
  21 index 00000000..2d6fd6f9
  22 --- /dev/null
  23 +++ b/contrib/arm/chunkcopy.h
  24 @@ -0,0 +1,279 @@
  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
  28 + */
  29 +
  30 +#ifndef CHUNKCOPY_H
  31 +#define CHUNKCOPY_H
  32 +
  33 +#include "zutil.h"
  34 +#include <arm_neon.h>
  35 +
  36 +#if __STDC_VERSION__ >= 199901L
  37 +#define Z_RESTRICT restrict
  38 +#else
  39 +#define Z_RESTRICT
  40 +#endif
  41 +
  42 +typedef uint8x16_t chunkcopy_chunk_t;
  43 +#define CHUNKCOPY_CHUNK_SIZE sizeof(chunkcopy_chunk_t)
  44 +
  45 +/*
  46 +   Ask the compiler to perform a wide, unaligned load with an machine
  47 +   instruction appropriate for the chunkcopy_chunk_t type.
  48 + */
  49 +static inline chunkcopy_chunk_t loadchunk(const unsigned char FAR *s) {
  50 +    chunkcopy_chunk_t c;
  51 +    __builtin_memcpy(&c, s, sizeof(c));
  52 +    return c;
  53 +}
  54 +
  55 +/*
  56 +   Ask the compiler to perform a wide, unaligned store with an machine
  57 +   instruction appropriate for the chunkcopy_chunk_t type.
  58 + */
  59 +static inline void storechunk(unsigned char FAR *d, chunkcopy_chunk_t c) {
  60 +    __builtin_memcpy(d, &c, sizeof(c));
  61 +}
  62 +
  63 +/*
  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.
  67 +
  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().
  71 +
  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
  75 +   reliable.
  76 + */
  77 +static inline unsigned char FAR *chunkcopy_core(unsigned char FAR *out,
  78 +                                                const unsigned char FAR *from,
  79 +                                                unsigned len) {
  80 +    int bump = (--len % CHUNKCOPY_CHUNK_SIZE) + 1;
  81 +    storechunk(out, loadchunk(from));
  82 +    out += bump;
  83 +    from += bump;
  84 +    len /= CHUNKCOPY_CHUNK_SIZE;
  85 +    while (len-- > 0) {
  86 +        storechunk(out, loadchunk(from));
  87 +        out += CHUNKCOPY_CHUNK_SIZE;
  88 +        from += CHUNKCOPY_CHUNK_SIZE;
  89 +    }
  90 +    return out;
  91 +}
  92 +
  93 +/*
  94 +   Like chunkcopy_core, but avoid writing beyond of legal output.
  95 +
  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
  99 +   exploited.
 100 + */
 101 +static inline unsigned char FAR *chunkcopy_core_safe(unsigned char FAR *out,
 102 +                                                     const unsigned char FAR * from,
 103 +                                                     unsigned len,
 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++; }
 112 +        return out;
 113 +    }
 114 +    return chunkcopy_core(out, from, len);
 115 +}
 116 +
 117 +/*
 118 +   Perform short copies until distance can be rewritten as being at least
 119 +   CHUNKCOPY_CHUNK_SIZE.
 120 +
 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).
 126 + */
 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));
 133 +        out += *dist;
 134 +        *len -= *dist;
 135 +        *dist += *dist;
 136 +    }
 137 +    return out;
 138 +}
 139 +
 140 +
 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));
 144 +#else
 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.
 147 +     */
 148 +    uint8x8_t h = vld1_u8(from);
 149 +    return vcombine_u8(h, h);
 150 +#endif
 151 +}
 152 +
 153 +/*
 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.
 158 + */
 159 +static inline unsigned char FAR *chunkset_core(unsigned char FAR *out,
 160 +                                               unsigned period,
 161 +                                               unsigned len) {
 162 +    uint8x16_t f;
 163 +    int bump = ((len - 1) % sizeof(f)) + 1;
 164 +
 165 +    switch (period) {
 166 +    case 1:
 167 +        f = vld1q_dup_u8(out - 1);
 168 +        vst1q_u8(out, f);
 169 +        out += bump;
 170 +        len -= bump;
 171 +        while (len > 0) {
 172 +            vst1q_u8(out, f);
 173 +            out += sizeof(f);
 174 +            len -= sizeof(f);
 175 +        }
 176 +        return out;
 177 +    case 2:
 178 +        f = vreinterpretq_u8_u16(vld1q_dup_u16((void *)(out - 2)));
 179 +        vst1q_u8(out, f);
 180 +        out += bump;
 181 +        len -= bump;
 182 +        if (len > 0) {
 183 +            f = vreinterpretq_u8_u16(vld1q_dup_u16((void *)(out - 2)));
 184 +            do {
 185 +                vst1q_u8(out, f);
 186 +                out += sizeof(f);
 187 +                len -= sizeof(f);
 188 +            } while (len > 0);
 189 +        }
 190 +        return out;
 191 +    case 4:
 192 +        f = vreinterpretq_u8_u32(vld1q_dup_u32((void *)(out - 4)));
 193 +        vst1q_u8(out, f);
 194 +        out += bump;
 195 +        len -= bump;
 196 +        if (len > 0) {
 197 +            f = vreinterpretq_u8_u32(vld1q_dup_u32((void *)(out - 4)));
 198 +            do {
 199 +                vst1q_u8(out, f);
 200 +                out += sizeof(f);
 201 +                len -= sizeof(f);
 202 +            } while (len > 0);
 203 +        }
 204 +        return out;
 205 +    case 8:
 206 +        f = chunkset_vld1q_dup_u8x8(out - 8);
 207 +        vst1q_u8(out, f);
 208 +        out += bump;
 209 +        len -= bump;
 210 +        if (len > 0) {
 211 +            f = chunkset_vld1q_dup_u8x8(out - 8);
 212 +            do {
 213 +                vst1q_u8(out, f);
 214 +                out += sizeof(f);
 215 +                len -= sizeof(f);
 216 +            } while (len > 0);
 217 +        }
 218 +        return out;
 219 +    }
 220 +    out = chunkunroll_relaxed(out, &period, &len);
 221 +    return chunkcopy_core(out, out - period, len);
 222 +}
 223 +
 224 +/*
 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.
 228 +
 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.
 233 + */
 234 +static inline unsigned char FAR *chunkcopy_relaxed(unsigned char FAR * Z_RESTRICT out,
 235 +                                                   const unsigned char FAR * Z_RESTRICT from,
 236 +                                                   unsigned len) {
 237 +    return chunkcopy_core(out, from, len);
 238 +}
 239 +
 240 +/*
 241 +   Like chunkcopy_relaxed, but avoid writing beyond of legal output.
 242 +
 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.
 247 +
 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
 251 +   exploited.
 252 + */
 253 +static inline unsigned char FAR *chunkcopy_safe(unsigned char FAR *out,
 254 +                                                const unsigned char FAR * Z_RESTRICT from,
 255 +                                                unsigned len,
 256 +                                                unsigned char FAR *limit) {
 257 +    Assert(out + len <= limit, "chunk copy exceeds safety limit");
 258 +    return chunkcopy_core_safe(out, from, len, limit);
 259 +}
 260 +
 261 +/*
 262 +   Perform chunky copy within the same buffer, where the source and destination
 263 +   may potentially overlap.
 264 +
 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.
 267 + */
 268 +static inline unsigned char FAR *chunkcopy_lapped_relaxed(unsigned char FAR *out,
 269 +                                                          unsigned dist,
 270 +                                                          unsigned len) {
 271 +    if (dist < len && dist < CHUNKCOPY_CHUNK_SIZE) {
 272 +        return chunkset_core(out, dist, len);
 273 +    }
 274 +    return chunkcopy_core(out, out - dist, len);
 275 +}
 276 +
 277 +/*
 278 +   Behave like chunkcopy_lapped_relaxed, but avoid writing beyond of legal output.
 279 +
 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
 283 +   exploited.
 284 + */
 285 +static inline unsigned char FAR *chunkcopy_lapped_safe(unsigned char FAR *out,
 286 +                                                       unsigned dist,
 287 +                                                       unsigned len,
 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);
 294 +            out++;
 295 +        }
 296 +        return out;
 297 +    }
 298 +    return chunkcopy_lapped_relaxed(out, dist, len);
 299 +}
 300 +
 301 +#undef Z_RESTRICT
 302 +
 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
 308 @@ -7,6 +7,7 @@
 309  #include "inftrees.h"
 310  #include "inflate.h"
 311  #include "inffast.h"
 312 +#include "chunkcopy.h"
 313
 314  #ifdef ASMINF
 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 */
 323  #endif
 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
 330      dmax = state->dmax;
 331  #endif
 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;
 337      hold = state->hold;
 338      bits = state->bits;
 339 @@ -197,70 +200,51 @@ unsigned start;         /* inflate()'s starting value for strm->avail_out */
 340  #endif
 341                      }
 342                      from = window;
 343 -                    if (wnext == 0) {           /* very common case */
 344 -                        from += wsize - op;
 345 -                        if (op < len) {         /* some from window */
 346 -                            len -= op;
 347 -                            do {
 348 -                                *out++ = *from++;
 349 -                            } while (--op);
 350 -                            from = out - dist;  /* rest from output */
 351 -                        }
 352 +                    if (wnext >= op) {          /* contiguous in window */
 353 +                        from += wnext - op;
 354                      }
 355 -                    else if (wnext < op) {      /* wrap around window */
 356 -                        from += wsize + wnext - op;
 357 +                    else {                      /* wrap around window */
 358                          op -= wnext;
 359 +                        from += wsize - op;
 360                          if (op < len) {         /* some from end of window */
 361                              len -= op;
 362 -                            do {
 363 -                                *out++ = *from++;
 364 -                            } while (--op);
 365 -                            from = window;
 366 -                            if (wnext < len) {  /* some from start of window */
 367 -                                op = wnext;
 368 -                                len -= op;
 369 -                                do {
 370 -                                    *out++ = *from++;
 371 -                                } while (--op);
 372 -                                from = out - dist;      /* rest from output */
 373 -                            }
 374 +                            out = chunkcopy_safe(out, from, op, limit);
 375 +                            from = window;      /* more from start of window */
 376 +                            op = wnext;
 377 +                            /* This (rare) case can create a situation where
 378 +                               the first chunkcopy below must be checked.
 379 +                             */
 380                          }
 381                      }
 382 -                    else {                      /* contiguous in window */
 383 -                        from += wnext - op;
 384 -                        if (op < len) {         /* some from window */
 385 -                            len -= op;
 386 -                            do {
 387 -                                *out++ = *from++;
 388 -                            } while (--op);
 389 -                            from = out - dist;  /* rest from output */
 390 -                        }
 391 -                    }
 392 -                    while (len > 2) {
 393 -                        *out++ = *from++;
 394 -                        *out++ = *from++;
 395 -                        *out++ = *from++;
 396 -                        len -= 3;
 397 -                    }
 398 -                    if (len) {
 399 -                        *out++ = *from++;
 400 -                        if (len > 1)
 401 -                            *out++ = *from++;
 402 +                    if (op < len) {             /* still need some from output */
 403 +                        out = chunkcopy_safe(out, from, op, limit);
 404 +                        len -= op;
 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.
 413 +                          */
 414 +                        out = chunkunroll_relaxed(out, &dist, &len);
 415 +                        out = chunkcopy_safe(out, out - dist, len, limit);
 416 +                    } else {
 417 +                        /* from points to window, so there is no risk of
 418 +                           overlapping pointers requiring memset-like behaviour
 419 +                         */
 420 +                        out = chunkcopy_safe(out, from, len, limit);
 421                      }
 422                  }
 423                  else {
 424 -                    from = out - dist;          /* copy direct from output */
 425 -                    do {                        /* minimum length is three */
 426 -                        *out++ = *from++;
 427 -                        *out++ = *from++;
 428 -                        *out++ = *from++;
 429 -                        len -= 3;
 430 -                    } while (len > 2);
 431 -                    if (len) {
 432 -                        *out++ = *from++;
 433 -                        if (len > 1)
 434 -                            *out++ = *from++;
 435 -                    }
 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`.
 441 +                     */
 442 +                    out = chunkcopy_lapped_relaxed(out, dist, len);
 443                  }
 444              }
 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
 450 @@ -84,6 +84,7 @@
 451  #include "inftrees.h"
 452  #include "inflate.h"
 453  #include "inffast.h"
 454 +#include "contrib/arm/chunkcopy.h"
 455
 456  #ifdef MAKEFIXED
 457  #  ifndef BUILDFIXED
 458 @@ -405,10 +406,20 @@ unsigned copy;
 459
 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.
 474 +         */
 475 +        memset(state->window + wsize, 0, CHUNKCOPY_CHUNK_SIZE);
 476 +#endif
 477      }
 478
 479      /* if window not in use yet, initialize */
 480 @@ -1175,17 +1186,16 @@ int flush;
 481                  else
 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);
 486              }
 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);
 492              }
 493 -            if (copy > left) copy = left;
 494              left -= copy;
 495              state->length -= copy;
 496 -            do {
 497 -                *put++ = *from++;
 498 -            } while (--copy);
 499              if (state->length == 0) state->mode = LEN;
 500              break;
 501          case LIT: