zlib/inffast.c

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