libkern/zlib/inffast.c

   1 /*
   2  * Copyright (c) 2008-2016, 2020 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 /* inffast.c -- fast decoding
  29  * Copyright (C) 1995-2004 Mark Adler
  30  * For conditions of distribution and use, see copyright notice in zlib.h
  31  */
  32
  33
  34 #include "zutil.h"
  35 #include "inftrees.h"
  36 #include "inflate.h"
  37 #include "inffast.h"
  38
  39 #ifndef ASMINF
  40
  41 /*
  42    Decode literal, length, and distance codes and write out the resulting
  43    literal and match bytes until either not enough input or output is
  44    available, an end-of-block is encountered, or a data error is encountered.
  45    When large enough input and output buffers are supplied to inflate(), for
  46    example, a 16K input buffer and a 64K output buffer, more than 95% of the
  47    inflate execution time is spent in this routine.
  48
  49    Entry assumptions:
  50
  51         state->mode == LEN
  52         strm->avail_in >= 6
  53         strm->avail_out >= 258
  54         start >= strm->avail_out
  55         state->bits < 8
  56
  57    On return, state->mode is one of:
  58
  59         LEN -- ran out of enough output space or enough available input
  60         TYPE -- reached end of block code, inflate() to interpret next block
  61         BAD -- error in block data
  62
  63    Notes:
  64
  65     - The maximum input bits used by a length/distance pair is 15 bits for the
  66       length code, 5 bits for the length extra, 15 bits for the distance code,
  67       and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
  68       Therefore if strm->avail_in >= 6, then there is enough input to avoid
  69       checking for available input while decoding.
  70
  71     - The maximum bytes that a single length/distance pair can output is 258
  72       bytes, which is the maximum length that can be coded.  inflate_fast()
  73       requires strm->avail_out >= 258 for each loop to avoid checking for
  74       output space.
  75
  76       @param start inflate()'s starting value for strm->avail_out
  77  */
  78 void
  79 inflate_fast(z_streamp strm, unsigned start)
  80 {
  81     struct inflate_state FAR *state;
  82     unsigned char FAR *in;      /* local strm->next_in */
  83     unsigned char FAR *last;    /* while in < last, enough input available */
  84     unsigned char FAR *out;     /* local strm->next_out */
  85     unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
  86     unsigned char FAR *end;     /* while out < end, enough space available */
  87 #ifdef INFLATE_STRICT
  88     unsigned dmax;              /* maximum distance from zlib header */
  89 #endif
  90     unsigned wsize;             /* window size or zero if not using window */
  91     unsigned whave;             /* valid bytes in the window */
  92     unsigned write;             /* window write index */
  93     unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
  94     unsigned long hold;         /* local strm->hold */
  95     unsigned bits;              /* local strm->bits */
  96     code const FAR *lcode;      /* local strm->lencode */
  97     code const FAR *dcode;      /* local strm->distcode */
  98     unsigned lmask;             /* mask for first level of length codes */
  99     unsigned dmask;             /* mask for first level of distance codes */
 100     code this;                  /* retrieved table entry */
 101     unsigned op;                /* code bits, operation, extra bits, or */
 102                                 /*  window position, window bytes to copy */
 103     unsigned len;               /* match length, unused bytes */
 104     unsigned dist;              /* match distance */
 105     unsigned char FAR *from;    /* where to copy match from */
 106
 107     /* copy state to local variables */
 108     state = (struct inflate_state FAR *)strm->state;
 109     in = strm->next_in;
 110     last = in + (strm->avail_in - 5);
 111     out = strm->next_out;
 112     beg = out - (start - strm->avail_out);
 113     end = out + (strm->avail_out - 257);
 114 #ifdef INFLATE_STRICT
 115     dmax = state->dmax;
 116 #endif
 117     wsize = state->wsize;
 118     whave = state->whave;
 119     write = state->write;
 120     window = state->window;
 121     hold = state->hold;
 122     bits = state->bits;
 123     lcode = state->lencode;
 124     dcode = state->distcode;
 125     lmask = (1U << state->lenbits) - 1;
 126     dmask = (1U << state->distbits) - 1;
 127
 128     /* decode literals and length/distances until end-of-block or not enough
 129        input data or output space */
 130     do {
 131         if (bits < 15) {
 132             hold += (unsigned long)(*in++) << bits;
 133             bits += 8;
 134             hold += (unsigned long)(*in++) << bits;
 135             bits += 8;
 136         }
 137         this = lcode[hold & lmask];
 138       dolen:
 139         op = (unsigned)(this.bits);
 140         hold >>= op;
 141         bits -= op;
 142         op = (unsigned)(this.op);
 143         if (op == 0) {                          /* literal */
 144             Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
 145                     "inflate:         literal '%c'\n" :
 146                     "inflate:         literal 0x%02x\n", this.val));
 147             *out++ = (unsigned char)(this.val);
 148         }
 149         else if (op & 16) {                     /* length base */
 150             len = (unsigned)(this.val);
 151             op &= 15;                           /* number of extra bits */
 152             if (op) {
 153                 if (bits < op) {
 154                     hold += (unsigned long)(*in++) << bits;
 155                     bits += 8;
 156                 }
 157                 len += (unsigned)hold & ((1U << op) - 1);
 158                 hold >>= op;
 159                 bits -= op;
 160             }
 161             Tracevv((stderr, "inflate:         length %u\n", len));
 162             if (bits < 15) {
 163                 hold += (unsigned long)(*in++) << bits;
 164                 bits += 8;
 165                 hold += (unsigned long)(*in++) << bits;
 166                 bits += 8;
 167             }
 168             this = dcode[hold & dmask];
 169           dodist:
 170             op = (unsigned)(this.bits);
 171             hold >>= op;
 172             bits -= op;
 173             op = (unsigned)(this.op);
 174             if (op & 16) {                      /* distance base */
 175                 dist = (unsigned)(this.val);
 176                 op &= 15;                       /* number of extra bits */
 177                 if (bits < op) {
 178                     hold += (unsigned long)(*in++) << bits;
 179                     bits += 8;
 180                     if (bits < op) {
 181                         hold += (unsigned long)(*in++) << bits;
 182                         bits += 8;
 183                     }
 184                 }
 185                 dist += (unsigned)hold & ((1U << op) - 1);
 186 #ifdef INFLATE_STRICT
 187                 if (dist > dmax) {
 188                     strm->msg = (char *)"invalid distance too far back";
 189                     state->mode = BAD;
 190                     break;
 191                 }
 192 #endif
 193                 hold >>= op;
 194                 bits -= op;
 195                 Tracevv((stderr, "inflate:         distance %u\n", dist));
 196                 op = (unsigned)(out - beg);     /* max distance in output */
 197                 if (dist > op) {                /* see if copy from window */
 198                     op = dist - op;             /* distance back in window */
 199                     if (op > whave) {
 200                         strm->msg = (char *)"invalid distance too far back";
 201                         state->mode = BAD;
 202                         break;
 203                     }
 204                     from = window;
 205                     if (write == 0) {           /* very common case */
 206                         from += wsize - op;
 207                         if (op < len) {         /* some from window */
 208                             len -= op;
 209                             do {
 210                                 *out++ = *from++;
 211                             } while (--op);
 212                             from = out - dist;  /* rest from output */
 213                         }
 214                     }
 215                     else if (write < op) {      /* wrap around window */
 216                         from += wsize + write - op;
 217                         op -= write;
 218                         if (op < len) {         /* some from end of window */
 219                             len -= op;
 220                             do {
 221                                 *out++ = *from++;
 222                             } while (--op);
 223                             from = window;
 224                             if (write < len) {  /* some from start of window */
 225                                 op = write;
 226                                 len -= op;
 227                                 do {
 228                                     *out++ = *from++;
 229                                 } while (--op);
 230                                 from = out - dist;      /* rest from output */
 231                             }
 232                         }
 233                     }
 234                     else {                      /* contiguous in window */
 235                         from += write - op;
 236                         if (op < len) {         /* some from window */
 237                             len -= op;
 238                             do {
 239                                 *out++ = *from++;
 240                             } while (--op);
 241                             from = out - dist;  /* rest from output */
 242                         }
 243                     }
 244                     while (len > 2) {
 245                         *out++ = *from++;
 246                         *out++ = *from++;
 247                         *out++ = *from++;
 248                         len -= 3;
 249                     }
 250                     if (len) {
 251                         *out++ = *from++;
 252                         if (len > 1)
 253                             *out++ = *from++;
 254                     }
 255                 }
 256                 else {
 257                     from = out - dist;          /* copy direct from output */
 258                     do {                        /* minimum length is three */
 259                         *out++ = *from++;
 260                         *out++ = *from++;
 261                         *out++ = *from++;
 262                         len -= 3;
 263                     } while (len > 2);
 264                     if (len) {
 265                         *out++ = *from++;
 266                         if (len > 1)
 267                             *out++ = *from++;
 268                     }
 269                 }
 270             }
 271             else if ((op & 64) == 0) {          /* 2nd level distance code */
 272                 this = dcode[this.val + (hold & ((1U << op) - 1))];
 273                 goto dodist;
 274             }
 275             else {
 276                 strm->msg = (char *)"invalid distance code";
 277                 state->mode = BAD;
 278                 break;
 279             }
 280         }
 281         else if ((op & 64) == 0) {              /* 2nd level length code */
 282             this = lcode[this.val + (hold & ((1U << op) - 1))];
 283             goto dolen;
 284         }
 285         else if (op & 32) {                     /* end-of-block */
 286             Tracevv((stderr, "inflate:         end of block\n"));
 287             state->mode = TYPE;
 288             break;
 289         }
 290         else {
 291             strm->msg = (char *)"invalid literal/length code";
 292             state->mode = BAD;
 293             break;
 294         }
 295     } while (in < last && out < end);
 296
 297     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
 298     len = bits >> 3;
 299     in -= len;
 300     bits -= len << 3;
 301     hold &= (1U << bits) - 1;
 302
 303     /* update state and return */
 304     strm->next_in = in;
 305     strm->next_out = out;
 306     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
 307     strm->avail_out = (unsigned)(out < end ?
 308                                  257 + (end - out) : 257 - (out - end));
 309     state->hold = hold;
 310     state->bits = bits;
 311     return;
 312 }
 313
 314 /*
 315    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
 316    - Using bit fields for code structure
 317    - Different op definition to avoid & for extra bits (do & for table bits)
 318    - Three separate decoding do-loops for direct, window, and write == 0
 319    - Special case for distance > 1 copies to do overlapped load and store copy
 320    - Explicit branch predictions (based on measured branch probabilities)
 321    - Deferring match copy and interspersed it with decoding subsequent codes
 322    - Swapping literal/length else
 323    - Swapping window/direct else
 324    - Larger unrolled copy loops (three is about right)
 325    - Moving len -= 3 statement into middle of loop
 326  */
 327
 328 #endif /* !ASMINF */