deps/zlib/inffast.c

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