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 --- /dev/null
  20 +++ b/contrib/arm/chunkcopy.h
  21 @@ -0,0 +1,279 @@
  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
  25 + */
  26 +
  27 +#ifndef CHUNKCOPY_H
  28 +#define CHUNKCOPY_H
  29 +
  30 +#include "zutil.h"
  31 +#include <arm_neon.h>
  32 +
  33 +#if __STDC_VERSION__ >= 199901L
  34 +#define Z_RESTRICT restrict
  35 +#else
  36 +#define Z_RESTRICT
  37 +#endif
  38 +
  39 +typedef uint8x16_t chunkcopy_chunk_t;
  40 +#define CHUNKCOPY_CHUNK_SIZE sizeof(chunkcopy_chunk_t)
  41 +
  42 +/*
  43 +   Ask the compiler to perform a wide, unaligned load with an machine
  44 +   instruction appropriate for the chunkcopy_chunk_t type.
  45 + */
  46 +static inline chunkcopy_chunk_t loadchunk(const unsigned char FAR *s) {
  47 +    chunkcopy_chunk_t c;
  48 +    __builtin_memcpy(&c, s, sizeof(c));
  49 +    return c;
  50 +}
  51 +
  52 +/*
  53 +   Ask the compiler to perform a wide, unaligned store with an machine
  54 +   instruction appropriate for the chunkcopy_chunk_t type.
  55 + */
  56 +static inline void storechunk(unsigned char FAR *d, chunkcopy_chunk_t c) {
  57 +    __builtin_memcpy(d, &c, sizeof(c));
  58 +}
  59 +
  60 +/*
  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.
  64 +
  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().
  68 +
  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
  72 +   reliable.
  73 + */
  74 +static inline unsigned char FAR *chunkcopy_core(unsigned char FAR *out,
  75 +                                                const unsigned char FAR *from,
  76 +                                                unsigned len) {
  77 +    int bump = (--len % CHUNKCOPY_CHUNK_SIZE) + 1;
  78 +    storechunk(out, loadchunk(from));
  79 +    out += bump;
  80 +    from += bump;
  81 +    len /= CHUNKCOPY_CHUNK_SIZE;
  82 +    while (len-- > 0) {
  83 +        storechunk(out, loadchunk(from));
  84 +        out += CHUNKCOPY_CHUNK_SIZE;
  85 +        from += CHUNKCOPY_CHUNK_SIZE;
  86 +    }
  87 +    return out;
  88 +}
  89 +
  90 +/*
  91 +   Like chunkcopy_core, but avoid writing beyond of legal output.
  92 +
  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
  96 +   exploited.
  97 + */
  98 +static inline unsigned char FAR *chunkcopy_core_safe(unsigned char FAR *out,
  99 +                                                     const unsigned char FAR * from,
 100 +                                                     unsigned len,
 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++; }
 109 +        return out;
 110 +    }
 111 +    return chunkcopy_core(out, from, len);
 112 +}
 113 +
 114 +/*
 115 +   Perform short copies until distance can be rewritten as being at least
 116 +   CHUNKCOPY_CHUNK_SIZE.
 117 +
 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).
 123 + */
 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));
 130 +        out += *dist;
 131 +        *len -= *dist;
 132 +        *dist += *dist;
 133 +    }
 134 +    return out;
 135 +}
 136 +
 137 +
 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));
 141 +#else
 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.
 144 +     */
 145 +    uint8x8_t h = vld1_u8(from);
 146 +    return vcombine_u8(h, h);
 147 +#endif
 148 +}
 149 +
 150 +/*
 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.
 155 + */
 156 +static inline unsigned char FAR *chunkset_core(unsigned char FAR *out,
 157 +                                               unsigned period,
 158 +                                               unsigned len) {
 159 +    uint8x16_t f;
 160 +    int bump = ((len - 1) % sizeof(f)) + 1;
 161 +
 162 +    switch (period) {
 163 +    case 1:
 164 +        f = vld1q_dup_u8(out - 1);
 165 +        vst1q_u8(out, f);
 166 +        out += bump;
 167 +        len -= bump;
 168 +        while (len > 0) {
 169 +            vst1q_u8(out, f);
 170 +            out += sizeof(f);
 171 +            len -= sizeof(f);
 172 +        }
 173 +        return out;
 174 +    case 2:
 175 +        f = vreinterpretq_u8_u16(vld1q_dup_u16((void *)(out - 2)));
 176 +        vst1q_u8(out, f);
 177 +        out += bump;
 178 +        len -= bump;
 179 +        if (len > 0) {
 180 +            f = vreinterpretq_u8_u16(vld1q_dup_u16((void *)(out - 2)));
 181 +            do {
 182 +                vst1q_u8(out, f);
 183 +                out += sizeof(f);
 184 +                len -= sizeof(f);
 185 +            } while (len > 0);
 186 +        }
 187 +        return out;
 188 +    case 4:
 189 +        f = vreinterpretq_u8_u32(vld1q_dup_u32((void *)(out - 4)));
 190 +        vst1q_u8(out, f);
 191 +        out += bump;
 192 +        len -= bump;
 193 +        if (len > 0) {
 194 +            f = vreinterpretq_u8_u32(vld1q_dup_u32((void *)(out - 4)));
 195 +            do {
 196 +                vst1q_u8(out, f);
 197 +                out += sizeof(f);
 198 +                len -= sizeof(f);
 199 +            } while (len > 0);
 200 +        }
 201 +        return out;
 202 +    case 8:
 203 +        f = chunkset_vld1q_dup_u8x8(out - 8);
 204 +        vst1q_u8(out, f);
 205 +        out += bump;
 206 +        len -= bump;
 207 +        if (len > 0) {
 208 +            f = chunkset_vld1q_dup_u8x8(out - 8);
 209 +            do {
 210 +                vst1q_u8(out, f);
 211 +                out += sizeof(f);
 212 +                len -= sizeof(f);
 213 +            } while (len > 0);
 214 +        }
 215 +        return out;
 216 +    }
 217 +    out = chunkunroll_relaxed(out, &period, &len);
 218 +    return chunkcopy_core(out, out - period, len);
 219 +}
 220 +
 221 +/*
 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.
 225 +
 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.
 230 + */
 231 +static inline unsigned char FAR *chunkcopy_relaxed(unsigned char FAR * Z_RESTRICT out,
 232 +                                                   const unsigned char FAR * Z_RESTRICT from,
 233 +                                                   unsigned len) {
 234 +    return chunkcopy_core(out, from, len);
 235 +}
 236 +
 237 +/*
 238 +   Like chunkcopy_relaxed, but avoid writing beyond of legal output.
 239 +
 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.
 244 +
 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
 248 +   exploited.
 249 + */
 250 +static inline unsigned char FAR *chunkcopy_safe(unsigned char FAR *out,
 251 +                                                const unsigned char FAR * Z_RESTRICT from,
 252 +                                                unsigned len,
 253 +                                                unsigned char FAR *limit) {
 254 +    Assert(out + len <= limit, "chunk copy exceeds safety limit");
 255 +    return chunkcopy_core_safe(out, from, len, limit);
 256 +}
 257 +
 258 +/*
 259 +   Perform chunky copy within the same buffer, where the source and destination
 260 +   may potentially overlap.
 261 +
 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.
 264 + */
 265 +static inline unsigned char FAR *chunkcopy_lapped_relaxed(unsigned char FAR *out,
 266 +                                                          unsigned dist,
 267 +                                                          unsigned len) {
 268 +    if (dist < len && dist < CHUNKCOPY_CHUNK_SIZE) {
 269 +        return chunkset_core(out, dist, len);
 270 +    }
 271 +    return chunkcopy_core(out, out - dist, len);
 272 +}
 273 +
 274 +/*
 275 +   Behave like chunkcopy_lapped_relaxed, but avoid writing beyond of legal output.
 276 +
 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
 280 +   exploited.
 281 + */
 282 +static inline unsigned char FAR *chunkcopy_lapped_safe(unsigned char FAR *out,
 283 +                                                       unsigned dist,
 284 +                                                       unsigned len,
 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);
 291 +            out++;
 292 +        }
 293 +        return out;
 294 +    }
 295 +    return chunkcopy_lapped_relaxed(out, dist, len);
 296 +}
 297 +
 298 +#undef Z_RESTRICT
 299 +
 300 +#endif /* CHUNKCOPY_H */
 301 --- a/contrib/arm/inffast.c
 302 +++ b/contrib/arm/inffast.c
 303 @@ -7,6 +7,7 @@
 304  #include "inftrees.h"
 305  #include "inflate.h"
 306  #include "inffast.h"
 307 +#include "chunkcopy.h"
 308
 309  #ifdef ASMINF
 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 */
 318  #endif
 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
 325      dmax = state->dmax;
 326  #endif
 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;
 332      hold = state->hold;
 333      bits = state->bits;
 334 @@ -197,70 +200,51 @@ unsigned start;         /* inflate()'s s
 335  #endif
 336                      }
 337                      from = window;
 338 -                    if (wnext == 0) {           /* very common case */
 339 -                        from += wsize - op;
 340 -                        if (op < len) {         /* some from window */
 341 -                            len -= op;
 342 -                            do {
 343 -                                *out++ = *from++;
 344 -                            } while (--op);
 345 -                            from = out - dist;  /* rest from output */
 346 -                        }
 347 +                    if (wnext >= op) {          /* contiguous in window */
 348 +                        from += wnext - op;
 349                      }
 350 -                    else if (wnext < op) {      /* wrap around window */
 351 -                        from += wsize + wnext - op;
 352 +                    else {                      /* wrap around window */
 353                          op -= wnext;
 354 +                        from += wsize - op;
 355                          if (op < len) {         /* some from end of window */
 356                              len -= op;
 357 -                            do {
 358 -                                *out++ = *from++;
 359 -                            } while (--op);
 360 -                            from = window;
 361 -                            if (wnext < len) {  /* some from start of window */
 362 -                                op = wnext;
 363 -                                len -= op;
 364 -                                do {
 365 -                                    *out++ = *from++;
 366 -                                } while (--op);
 367 -                                from = out - dist;      /* rest from output */
 368 -                            }
 369 -                        }
 370 -                    }
 371 -                    else {                      /* contiguous in window */
 372 -                        from += wnext - op;
 373 -                        if (op < len) {         /* some from window */
 374 -                            len -= op;
 375 -                            do {
 376 -                                *out++ = *from++;
 377 -                            } while (--op);
 378 -                            from = out - dist;  /* rest from output */
 379 -                        }
 380 -                    }
 381 -                    while (len > 2) {
 382 -                        *out++ = *from++;
 383 -                        *out++ = *from++;
 384 -                        *out++ = *from++;
 385 -                        len -= 3;
 386 -                    }
 387 -                    if (len) {
 388 -                        *out++ = *from++;
 389 -                        if (len > 1)
 390 -                            *out++ = *from++;
 391 +                            out = chunkcopy_safe(out, from, op, limit);
 392 +                            from = window;      /* more from start of window */
 393 +                            op = wnext;
 394 +                            /* This (rare) case can create a situation where
 395 +                               the first chunkcopy below must be checked.
 396 +                             */
 397 +                        }
 398 +                    }
 399 +                    if (op < len) {             /* still need some from output */
 400 +                        out = chunkcopy_safe(out, from, op, limit);
 401 +                        len -= op;
 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.
 410 +                          */
 411 +                        out = chunkunroll_relaxed(out, &dist, &len);
 412 +                        out = chunkcopy_safe(out, out - dist, len, limit);
 413 +                    } else {
 414 +                        /* from points to window, so there is no risk of
 415 +                           overlapping pointers requiring memset-like behaviour
 416 +                         */
 417 +                        out = chunkcopy_safe(out, from, len, limit);
 418                      }
 419                  }
 420                  else {
 421 -                    from = out - dist;          /* copy direct from output */
 422 -                    do {                        /* minimum length is three */
 423 -                        *out++ = *from++;
 424 -                        *out++ = *from++;
 425 -                        *out++ = *from++;
 426 -                        len -= 3;
 427 -                    } while (len > 2);
 428 -                    if (len) {
 429 -                        *out++ = *from++;
 430 -                        if (len > 1)
 431 -                            *out++ = *from++;
 432 -                    }
 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`.
 438 +                     */
 439 +                    out = chunkcopy_lapped_relaxed(out, dist, len);
 440                  }
 441              }
 442              else if ((op & 64) == 0) {          /* 2nd level distance code */
 443 --- a/contrib/arm/inflate.c
 444 +++ b/contrib/arm/inflate.c
 445 @@ -84,6 +84,7 @@
 446  #include "inftrees.h"
 447  #include "inflate.h"
 448  #include "inffast.h"
 449 +#include "contrib/arm/chunkcopy.h"
 450
 451  #ifdef MAKEFIXED
 452  #  ifndef BUILDFIXED
 453 @@ -405,10 +406,20 @@ unsigned copy;
 454
 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.
 469 +         */
 470 +        memset(state->window + wsize, 0, CHUNKCOPY_CHUNK_SIZE);
 471 +#endif
 472      }
 473
 474      /* if window not in use yet, initialize */
 475 @@ -1175,17 +1186,16 @@ int flush;
 476                  else
 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);
 481              }
 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);
 487              }
 488 -            if (copy > left) copy = left;
 489              left -= copy;
 490              state->length -= copy;
 491 -            do {
 492 -                *put++ = *from++;
 493 -            } while (--copy);
 494              if (state->length == 0) state->mode = LEN;
 495              break;
 496          case LIT: