compression/zlib/inffast.c

0001 /* inffast.c -- fast decoding
0002  * Copyright (C) 1995-2017 Mark Adler
0003  * For conditions of distribution and use, see copyright notice in zlib.h
0004  */
0005
0006 #include "zutil.h"
0007 #include "inftrees.h"
0008 #include "inflate.h"
0009 #include "inffast.h"
0010
0011 #ifdef ASMINF
0012 #  pragma message("Assembler code may have bugs -- use at your own risk")
0013 #else
0014
0015 /*
0016    Decode literal, length, and distance codes and write out the resulting
0017    literal and match bytes until either not enough input or output is
0018    available, an end-of-block is encountered, or a data error is encountered.
0019    When large enough input and output buffers are supplied to inflate(), for
0020    example, a 16K input buffer and a 64K output buffer, more than 95% of the
0021    inflate execution time is spent in this routine.
0022
0023    Entry assumptions:
0024
0025         state->mode == LEN
0026         strm->avail_in >= 6
0027         strm->avail_out >= 258
0028         start >= strm->avail_out
0029         state->bits < 8
0030
0031    On return, state->mode is one of:
0032
0033         LEN -- ran out of enough output space or enough available input
0034         TYPE -- reached end of block code, inflate() to interpret next block
0035         BAD -- error in block data
0036
0037    Notes:
0038
0039     - The maximum input bits used by a length/distance pair is 15 bits for the
0040       length code, 5 bits for the length extra, 15 bits for the distance code,
0041       and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
0042       Therefore if strm->avail_in >= 6, then there is enough input to avoid
0043       checking for available input while decoding.
0044
0045     - The maximum bytes that a single length/distance pair can output is 258
0046       bytes, which is the maximum length that can be coded.  inflate_fast()
0047       requires strm->avail_out >= 258 for each loop to avoid checking for
0048       output space.
0049  */
0050 void ZLIB_INTERNAL inflate_fast(strm, start)
0051 z_streamp strm;
0052 unsigned start;         /* inflate()'s starting value for strm->avail_out */
0053 {
0054     struct inflate_state FAR *state;
0055     z_const unsigned char FAR *in;      /* local strm->next_in */
0056     z_const unsigned char FAR *last;    /* have enough input while in < last */
0057     unsigned char FAR *out;     /* local strm->next_out */
0058     unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
0059     unsigned char FAR *end;     /* while out < end, enough space available */
0060 #ifdef INFLATE_STRICT
0061     unsigned dmax;              /* maximum distance from zlib header */
0062 #endif
0063     unsigned wsize;             /* window size or zero if not using window */
0064     unsigned whave;             /* valid bytes in the window */
0065     unsigned wnext;             /* window write index */
0066     unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
0067     unsigned long hold;         /* local strm->hold */
0068     unsigned bits;              /* local strm->bits */
0069     code const FAR *lcode;      /* local strm->lencode */
0070     code const FAR *dcode;      /* local strm->distcode */
0071     unsigned lmask;             /* mask for first level of length codes */
0072     unsigned dmask;             /* mask for first level of distance codes */
0073     code const *here;           /* retrieved table entry */
0074     unsigned op;                /* code bits, operation, extra bits, or */
0075                                 /*  window position, window bytes to copy */
0076     unsigned len;               /* match length, unused bytes */
0077     unsigned dist;              /* match distance */
0078     unsigned char FAR *from;    /* where to copy match from */
0079
0080     /* copy state to local variables */
0081     state = (struct inflate_state FAR *)strm->state;
0082     in = strm->next_in;
0083     last = in + (strm->avail_in - 5);
0084     out = strm->next_out;
0085     beg = out - (start - strm->avail_out);
0086     end = out + (strm->avail_out - 257);
0087 #ifdef INFLATE_STRICT
0088     dmax = state->dmax;
0089 #endif
0090     wsize = state->wsize;
0091     whave = state->whave;
0092     wnext = state->wnext;
0093     window = state->window;
0094     hold = state->hold;
0095     bits = state->bits;
0096     lcode = state->lencode;
0097     dcode = state->distcode;
0098     lmask = (1U << state->lenbits) - 1;
0099     dmask = (1U << state->distbits) - 1;
0100
0101     /* decode literals and length/distances until end-of-block or not enough
0102        input data or output space */
0103     do {
0104         if (bits < 15) {
0105             hold += (unsigned long)(*in++) << bits;
0106             bits += 8;
0107             hold += (unsigned long)(*in++) << bits;
0108             bits += 8;
0109         }
0110         here = lcode + (hold & lmask);
0111       dolen:
0112         op = (unsigned)(here->bits);
0113         hold >>= op;
0114         bits -= op;
0115         op = (unsigned)(here->op);
0116         if (op == 0) {                          /* literal */
0117             Tracevv((stderr, here->val >= 0x20 && here->val < 0x7f ?
0118                     "inflate:         literal '%c'\n" :
0119                     "inflate:         literal 0x%02x\n", here->val));
0120             *out++ = (unsigned char)(here->val);
0121         }
0122         else if (op & 16) {                     /* length base */
0123             len = (unsigned)(here->val);
0124             op &= 15;                           /* number of extra bits */
0125             if (op) {
0126                 if (bits < op) {
0127                     hold += (unsigned long)(*in++) << bits;
0128                     bits += 8;
0129                 }
0130                 len += (unsigned)hold & ((1U << op) - 1);
0131                 hold >>= op;
0132                 bits -= op;
0133             }
0134             Tracevv((stderr, "inflate:         length %u\n", len));
0135             if (bits < 15) {
0136                 hold += (unsigned long)(*in++) << bits;
0137                 bits += 8;
0138                 hold += (unsigned long)(*in++) << bits;
0139                 bits += 8;
0140             }
0141             here = dcode + (hold & dmask);
0142           dodist:
0143             op = (unsigned)(here->bits);
0144             hold >>= op;
0145             bits -= op;
0146             op = (unsigned)(here->op);
0147             if (op & 16) {                      /* distance base */
0148                 dist = (unsigned)(here->val);
0149                 op &= 15;                       /* number of extra bits */
0150                 if (bits < op) {
0151                     hold += (unsigned long)(*in++) << bits;
0152                     bits += 8;
0153                     if (bits < op) {
0154                         hold += (unsigned long)(*in++) << bits;
0155                         bits += 8;
0156                     }
0157                 }
0158                 dist += (unsigned)hold & ((1U << op) - 1);
0159 #ifdef INFLATE_STRICT
0160                 if (dist > dmax) {
0161                     strm->msg = (char *)"invalid distance too far back";
0162                     state->mode = BAD;
0163                     break;
0164                 }
0165 #endif
0166                 hold >>= op;
0167                 bits -= op;
0168                 Tracevv((stderr, "inflate:         distance %u\n", dist));
0169                 op = (unsigned)(out - beg);     /* max distance in output */
0170                 if (dist > op) {                /* see if copy from window */
0171                     op = dist - op;             /* distance back in window */
0172                     if (op > whave) {
0173                         if (state->sane) {
0174                             strm->msg =
0175                                 (char *)"invalid distance too far back";
0176                             state->mode = BAD;
0177                             break;
0178                         }
0179 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
0180                         if (len <= op - whave) {
0181                             do {
0182                                 *out++ = 0;
0183                             } while (--len);
0184                             continue;
0185                         }
0186                         len -= op - whave;
0187                         do {
0188                             *out++ = 0;
0189                         } while (--op > whave);
0190                         if (op == 0) {
0191                             from = out - dist;
0192                             do {
0193                                 *out++ = *from++;
0194                             } while (--len);
0195                             continue;
0196                         }
0197 #endif
0198                     }
0199                     from = window;
0200                     if (wnext == 0) {           /* very common case */
0201                         from += wsize - op;
0202                         if (op < len) {         /* some from window */
0203                             len -= op;
0204                             do {
0205                                 *out++ = *from++;
0206                             } while (--op);
0207                             from = out - dist;  /* rest from output */
0208                         }
0209                     }
0210                     else if (wnext < op) {      /* wrap around window */
0211                         from += wsize + wnext - op;
0212                         op -= wnext;
0213                         if (op < len) {         /* some from end of window */
0214                             len -= op;
0215                             do {
0216                                 *out++ = *from++;
0217                             } while (--op);
0218                             from = window;
0219                             if (wnext < len) {  /* some from start of window */
0220                                 op = wnext;
0221                                 len -= op;
0222                                 do {
0223                                     *out++ = *from++;
0224                                 } while (--op);
0225                                 from = out - dist;      /* rest from output */
0226                             }
0227                         }
0228                     }
0229                     else {                      /* contiguous in window */
0230                         from += wnext - op;
0231                         if (op < len) {         /* some from window */
0232                             len -= op;
0233                             do {
0234                                 *out++ = *from++;
0235                             } while (--op);
0236                             from = out - dist;  /* rest from output */
0237                         }
0238                     }
0239                     while (len > 2) {
0240                         *out++ = *from++;
0241                         *out++ = *from++;
0242                         *out++ = *from++;
0243                         len -= 3;
0244                     }
0245                     if (len) {
0246                         *out++ = *from++;
0247                         if (len > 1)
0248                             *out++ = *from++;
0249                     }
0250                 }
0251                 else {
0252                     from = out - dist;          /* copy direct from output */
0253                     do {                        /* minimum length is three */
0254                         *out++ = *from++;
0255                         *out++ = *from++;
0256                         *out++ = *from++;
0257                         len -= 3;
0258                     } while (len > 2);
0259                     if (len) {
0260                         *out++ = *from++;
0261                         if (len > 1)
0262                             *out++ = *from++;
0263                     }
0264                 }
0265             }
0266             else if ((op & 64) == 0) {          /* 2nd level distance code */
0267                 here = dcode + here->val + (hold & ((1U << op) - 1));
0268                 goto dodist;
0269             }
0270             else {
0271                 strm->msg = (char *)"invalid distance code";
0272                 state->mode = BAD;
0273                 break;
0274             }
0275         }
0276         else if ((op & 64) == 0) {              /* 2nd level length code */
0277             here = lcode + here->val + (hold & ((1U << op) - 1));
0278             goto dolen;
0279         }
0280         else if (op & 32) {                     /* end-of-block */
0281             Tracevv((stderr, "inflate:         end of block\n"));
0282             state->mode = TYPE;
0283             break;
0284         }
0285         else {
0286             strm->msg = (char *)"invalid literal/length code";
0287             state->mode = BAD;
0288             break;
0289         }
0290     } while (in < last && out < end);
0291
0292     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
0293     len = bits >> 3;
0294     in -= len;
0295     bits -= len << 3;
0296     hold &= (1U << bits) - 1;
0297
0298     /* update state and return */
0299     strm->next_in = in;
0300     strm->next_out = out;
0301     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
0302     strm->avail_out = (unsigned)(out < end ?
0303                                  257 + (end - out) : 257 - (out - end));
0304     state->hold = hold;
0305     state->bits = bits;
0306     return;
0307 }
0308
0309 /*
0310    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
0311    - Using bit fields for code structure
0312    - Different op definition to avoid & for extra bits (do & for table bits)
0313    - Three separate decoding do-loops for direct, window, and wnext == 0
0314    - Special case for distance > 1 copies to do overlapped load and store copy
0315    - Explicit branch predictions (based on measured branch probabilities)
0316    - Deferring match copy and interspersed it with decoding subsequent codes
0317    - Swapping literal/length else
0318    - Swapping window/direct else
0319    - Larger unrolled copy loops (three is about right)
0320    - Moving len -= 3 statement into middle of loop
0321  */
0322
0323 #endif /* !ASMINF */