inffast.c

00001 /* inffast.c -- fast decoding
00002  * Copyright (C) 1995-2008, 2010 Mark Adler
00003  * For conditions of distribution and use, see copyright notice in zlib.h
00004  */
00005 
00006 #include "zutil.h"
00007 #include "inftrees.h"
00008 #include "inflate.h"
00009 #include "inffast.h"
00010 
00011 #ifndef ASMINF
00012 
00013 /* Allow machine dependent optimization for post-increment or pre-increment.
00014    Based on testing to date,
00015    Pre-increment preferred for:
00016    - PowerPC G3 (Adler)
00017    - MIPS R5000 (Randers-Pehrson)
00018    Post-increment preferred for:
00019    - none
00020    No measurable difference:
00021    - Pentium III (Anderson)
00022    - M68060 (Nikl)
00023  */
00024 #ifdef POSTINC
00025 #  define OFF 0
00026 #  define PUP(a) *(a)++
00027 #else
00028 #  define OFF 1
00029 #  define PUP(a) *++(a)
00030 #endif
00031 
00032 /*
00033    Decode literal, length, and distance codes and write out the resulting
00034    literal and match bytes until either not enough input or output is
00035    available, an end-of-block is encountered, or a data error is encountered.
00036    When large enough input and output buffers are supplied to inflate(), for
00037    example, a 16K input buffer and a 64K output buffer, more than 95% of the
00038    inflate execution time is spent in this routine.
00039 
00040    Entry assumptions:
00041 
00042         state->mode == LEN
00043         strm->avail_in >= 6
00044         strm->avail_out >= 258
00045         start >= strm->avail_out
00046         state->bits < 8
00047 
00048    On return, state->mode is one of:
00049 
00050         LEN -- ran out of enough output space or enough available input
00051         TYPE -- reached end of block code, inflate() to interpret next block
00052         BAD -- error in block data
00053 
00054    Notes:
00055 
00056     - The maximum input bits used by a length/distance pair is 15 bits for the
00057       length code, 5 bits for the length extra, 15 bits for the distance code,
00058       and 13 bits for the distance extra.  This totals 48 bits, or six bytes.
00059       Therefore if strm->avail_in >= 6, then there is enough input to avoid
00060       checking for available input while decoding.
00061 
00062     - The maximum bytes that a single length/distance pair can output is 258
00063       bytes, which is the maximum length that can be coded.  inflate_fast()
00064       requires strm->avail_out >= 258 for each loop to avoid checking for
00065       output space.
00066  */
00067 void ZLIB_INTERNAL inflate_fast(strm, start)
00068 z_streamp strm;
00069 unsigned start;         /* inflate()'s starting value for strm->avail_out */
00070 {
00071     struct inflate_state FAR *state;
00072     unsigned char FAR *in;      /* local strm->next_in */
00073     unsigned char FAR *last;    /* while in < last, enough input available */
00074     unsigned char FAR *out;     /* local strm->next_out */
00075     unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
00076     unsigned char FAR *end;     /* while out < end, enough space available */
00077 #ifdef INFLATE_STRICT
00078     unsigned dmax;              /* maximum distance from zlib header */
00079 #endif
00080     unsigned wsize;             /* window size or zero if not using window */
00081     unsigned whave;             /* valid bytes in the window */
00082     unsigned wnext;             /* window write index */
00083     unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
00084     unsigned long hold;         /* local strm->hold */
00085     unsigned bits;              /* local strm->bits */
00086     code const FAR *lcode;      /* local strm->lencode */
00087     code const FAR *dcode;      /* local strm->distcode */
00088     unsigned lmask;             /* mask for first level of length codes */
00089     unsigned dmask;             /* mask for first level of distance codes */
00090     code here;                  /* retrieved table entry */
00091     unsigned op;                /* code bits, operation, extra bits, or */
00092                                 /*  window position, window bytes to copy */
00093     unsigned len;               /* match length, unused bytes */
00094     unsigned dist;              /* match distance */
00095     unsigned char FAR *from;    /* where to copy match from */
00096 
00097     /* copy state to local variables */
00098     state = (struct inflate_state FAR *)strm->state;
00099     in = strm->next_in - OFF;
00100     last = in + (strm->avail_in - 5);
00101     out = strm->next_out - OFF;
00102     beg = out - (start - strm->avail_out);
00103     end = out + (strm->avail_out - 257);
00104 #ifdef INFLATE_STRICT
00105     dmax = state->dmax;
00106 #endif
00107     wsize = state->wsize;
00108     whave = state->whave;
00109     wnext = state->wnext;
00110     window = state->window;
00111     hold = state->hold;
00112     bits = state->bits;
00113     lcode = state->lencode;
00114     dcode = state->distcode;
00115     lmask = (1U << state->lenbits) - 1;
00116     dmask = (1U << state->distbits) - 1;
00117 
00118     /* decode literals and length/distances until end-of-block or not enough
00119        input data or output space */
00120     do {
00121         if (bits < 15) {
00122             hold += (unsigned long)(PUP(in)) << bits;
00123             bits += 8;
00124             hold += (unsigned long)(PUP(in)) << bits;
00125             bits += 8;
00126         }
00127         here = lcode[hold & lmask];
00128       dolen:
00129         op = (unsigned)(here.bits);
00130         hold >>= op;
00131         bits -= op;
00132         op = (unsigned)(here.op);
00133         if (op == 0) {                          /* literal */
00134             Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
00135                     "inflate:         literal '%c'\n" :
00136                     "inflate:         literal 0x%02x\n", here.val));
00137             PUP(out) = (unsigned char)(here.val);
00138         }
00139         else if (op & 16) {                     /* length base */
00140             len = (unsigned)(here.val);
00141             op &= 15;                           /* number of extra bits */
00142             if (op) {
00143                 if (bits < op) {
00144                     hold += (unsigned long)(PUP(in)) << bits;
00145                     bits += 8;
00146                 }
00147                 len += (unsigned)hold & ((1U << op) - 1);
00148                 hold >>= op;
00149                 bits -= op;
00150             }
00151             Tracevv((stderr, "inflate:         length %u\n", len));
00152             if (bits < 15) {
00153                 hold += (unsigned long)(PUP(in)) << bits;
00154                 bits += 8;
00155                 hold += (unsigned long)(PUP(in)) << bits;
00156                 bits += 8;
00157             }
00158             here = dcode[hold & dmask];
00159           dodist:
00160             op = (unsigned)(here.bits);
00161             hold >>= op;
00162             bits -= op;
00163             op = (unsigned)(here.op);
00164             if (op & 16) {                      /* distance base */
00165                 dist = (unsigned)(here.val);
00166                 op &= 15;                       /* number of extra bits */
00167                 if (bits < op) {
00168                     hold += (unsigned long)(PUP(in)) << bits;
00169                     bits += 8;
00170                     if (bits < op) {
00171                         hold += (unsigned long)(PUP(in)) << bits;
00172                         bits += 8;
00173                     }
00174                 }
00175                 dist += (unsigned)hold & ((1U << op) - 1);
00176 #ifdef INFLATE_STRICT
00177                 if (dist > dmax) {
00178                     strm->msg = (char *)"invalid distance too far back";
00179                     state->mode = BAD;
00180                     break;
00181                 }
00182 #endif
00183                 hold >>= op;
00184                 bits -= op;
00185                 Tracevv((stderr, "inflate:         distance %u\n", dist));
00186                 op = (unsigned)(out - beg);     /* max distance in output */
00187                 if (dist > op) {                /* see if copy from window */
00188                     op = dist - op;             /* distance back in window */
00189                     if (op > whave) {
00190                         if (state->sane) {
00191                             strm->msg =
00192                                 (char *)"invalid distance too far back";
00193                             state->mode = BAD;
00194                             break;
00195                         }
00196 #ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
00197                         if (len <= op - whave) {
00198                             do {
00199                                 PUP(out) = 0;
00200                             } while (--len);
00201                             continue;
00202                         }
00203                         len -= op - whave;
00204                         do {
00205                             PUP(out) = 0;
00206                         } while (--op > whave);
00207                         if (op == 0) {
00208                             from = out - dist;
00209                             do {
00210                                 PUP(out) = PUP(from);
00211                             } while (--len);
00212                             continue;
00213                         }
00214 #endif
00215                     }
00216                     from = window - OFF;
00217                     if (wnext == 0) {           /* very common case */
00218                         from += wsize - op;
00219                         if (op < len) {         /* some from window */
00220                             len -= op;
00221                             do {
00222                                 PUP(out) = PUP(from);
00223                             } while (--op);
00224                             from = out - dist;  /* rest from output */
00225                         }
00226                     }
00227                     else if (wnext < op) {      /* wrap around window */
00228                         from += wsize + wnext - op;
00229                         op -= wnext;
00230                         if (op < len) {         /* some from end of window */
00231                             len -= op;
00232                             do {
00233                                 PUP(out) = PUP(from);
00234                             } while (--op);
00235                             from = window - OFF;
00236                             if (wnext < len) {  /* some from start of window */
00237                                 op = wnext;
00238                                 len -= op;
00239                                 do {
00240                                     PUP(out) = PUP(from);
00241                                 } while (--op);
00242                                 from = out - dist;      /* rest from output */
00243                             }
00244                         }
00245                     }
00246                     else {                      /* contiguous in window */
00247                         from += wnext - op;
00248                         if (op < len) {         /* some from window */
00249                             len -= op;
00250                             do {
00251                                 PUP(out) = PUP(from);
00252                             } while (--op);
00253                             from = out - dist;  /* rest from output */
00254                         }
00255                     }
00256                     while (len > 2) {
00257                         PUP(out) = PUP(from);
00258                         PUP(out) = PUP(from);
00259                         PUP(out) = PUP(from);
00260                         len -= 3;
00261                     }
00262                     if (len) {
00263                         PUP(out) = PUP(from);
00264                         if (len > 1)
00265                             PUP(out) = PUP(from);
00266                     }
00267                 }
00268                 else {
00269                     from = out - dist;          /* copy direct from output */
00270                     do {                        /* minimum length is three */
00271                         PUP(out) = PUP(from);
00272                         PUP(out) = PUP(from);
00273                         PUP(out) = PUP(from);
00274                         len -= 3;
00275                     } while (len > 2);
00276                     if (len) {
00277                         PUP(out) = PUP(from);
00278                         if (len > 1)
00279                             PUP(out) = PUP(from);
00280                     }
00281                 }
00282             }
00283             else if ((op & 64) == 0) {          /* 2nd level distance code */
00284                 here = dcode[here.val + (hold & ((1U << op) - 1))];
00285                 goto dodist;
00286             }
00287             else {
00288                 strm->msg = (char *)"invalid distance code";
00289                 state->mode = BAD;
00290                 break;
00291             }
00292         }
00293         else if ((op & 64) == 0) {              /* 2nd level length code */
00294             here = lcode[here.val + (hold & ((1U << op) - 1))];
00295             goto dolen;
00296         }
00297         else if (op & 32) {                     /* end-of-block */
00298             Tracevv((stderr, "inflate:         end of block\n"));
00299             state->mode = TYPE;
00300             break;
00301         }
00302         else {
00303             strm->msg = (char *)"invalid literal/length code";
00304             state->mode = BAD;
00305             break;
00306         }
00307     } while (in < last && out < end);
00308 
00309     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
00310     len = bits >> 3;
00311     in -= len;
00312     bits -= len << 3;
00313     hold &= (1U << bits) - 1;
00314 
00315     /* update state and return */
00316     strm->next_in = in + OFF;
00317     strm->next_out = out + OFF;
00318     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
00319     strm->avail_out = (unsigned)(out < end ?
00320                                  257 + (end - out) : 257 - (out - end));
00321     state->hold = hold;
00322     state->bits = bits;
00323     return;
00324 }
00325 
00326 /*
00327    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
00328    - Using bit fields for code structure
00329    - Different op definition to avoid & for extra bits (do & for table bits)
00330    - Three separate decoding do-loops for direct, window, and wnext == 0
00331    - Special case for distance > 1 copies to do overlapped load and store copy
00332    - Explicit branch predictions (based on measured branch probabilities)
00333    - Deferring match copy and interspersed it with decoding subsequent codes
00334    - Swapping literal/length else
00335    - Swapping window/direct else
00336    - Larger unrolled copy loops (three is about right)
00337    - Moving len -= 3 statement into middle of loop
00338  */
00339 
00340 #endif /* !ASMINF */