Back to index

tetex-bin  3.0
inffast.c
Go to the documentation of this file.
00001 /* inffast.c -- fast decoding
00002  * Copyright (C) 1995-2003 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    - 68060 (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 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     unsigned wsize;             /* window size or zero if not using window */
00078     unsigned whave;             /* valid bytes in the window */
00079     unsigned write;             /* window write index */
00080     unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
00081     unsigned long hold;         /* local strm->hold */
00082     unsigned bits;              /* local strm->bits */
00083     code const FAR *lcode;      /* local strm->lencode */
00084     code const FAR *dcode;      /* local strm->distcode */
00085     unsigned lmask;             /* mask for first level of length codes */
00086     unsigned dmask;             /* mask for first level of distance codes */
00087     code this;                  /* retrieved table entry */
00088     unsigned op;                /* code bits, operation, extra bits, or */
00089                                 /*  window position, window bytes to copy */
00090     unsigned len;               /* match length, unused bytes */
00091     unsigned dist;              /* match distance */
00092     unsigned char FAR *from;    /* where to copy match from */
00093 
00094     /* copy state to local variables */
00095     state = (struct inflate_state FAR *)strm->state;
00096     in = strm->next_in - OFF;
00097     last = in + (strm->avail_in - 5);
00098     out = strm->next_out - OFF;
00099     beg = out - (start - strm->avail_out);
00100     end = out + (strm->avail_out - 257);
00101     wsize = state->wsize;
00102     whave = state->whave;
00103     write = state->write;
00104     window = state->window;
00105     hold = state->hold;
00106     bits = state->bits;
00107     lcode = state->lencode;
00108     dcode = state->distcode;
00109     lmask = (1U << state->lenbits) - 1;
00110     dmask = (1U << state->distbits) - 1;
00111 
00112     /* decode literals and length/distances until end-of-block or not enough
00113        input data or output space */
00114     do {
00115         if (bits < 15) {
00116             hold += (unsigned long)(PUP(in)) << bits;
00117             bits += 8;
00118             hold += (unsigned long)(PUP(in)) << bits;
00119             bits += 8;
00120         }
00121         this = lcode[hold & lmask];
00122       dolen:
00123         op = (unsigned)(this.bits);
00124         hold >>= op;
00125         bits -= op;
00126         op = (unsigned)(this.op);
00127         if (op == 0) {                          /* literal */
00128             Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
00129                     "inflate:         literal '%c'\n" :
00130                     "inflate:         literal 0x%02x\n", this.val));
00131             PUP(out) = (unsigned char)(this.val);
00132         }
00133         else if (op & 16) {                     /* length base */
00134             len = (unsigned)(this.val);
00135             op &= 15;                           /* number of extra bits */
00136             if (op) {
00137                 if (bits < op) {
00138                     hold += (unsigned long)(PUP(in)) << bits;
00139                     bits += 8;
00140                 }
00141                 len += (unsigned)hold & ((1U << op) - 1);
00142                 hold >>= op;
00143                 bits -= op;
00144             }
00145             Tracevv((stderr, "inflate:         length %u\n", len));
00146             if (bits < 15) {
00147                 hold += (unsigned long)(PUP(in)) << bits;
00148                 bits += 8;
00149                 hold += (unsigned long)(PUP(in)) << bits;
00150                 bits += 8;
00151             }
00152             this = dcode[hold & dmask];
00153           dodist:
00154             op = (unsigned)(this.bits);
00155             hold >>= op;
00156             bits -= op;
00157             op = (unsigned)(this.op);
00158             if (op & 16) {                      /* distance base */
00159                 dist = (unsigned)(this.val);
00160                 op &= 15;                       /* number of extra bits */
00161                 if (bits < op) {
00162                     hold += (unsigned long)(PUP(in)) << bits;
00163                     bits += 8;
00164                     if (bits < op) {
00165                         hold += (unsigned long)(PUP(in)) << bits;
00166                         bits += 8;
00167                     }
00168                 }
00169                 dist += (unsigned)hold & ((1U << op) - 1);
00170                 hold >>= op;
00171                 bits -= op;
00172                 Tracevv((stderr, "inflate:         distance %u\n", dist));
00173                 op = (unsigned)(out - beg);     /* max distance in output */
00174                 if (dist > op) {                /* see if copy from window */
00175                     op = dist - op;             /* distance back in window */
00176                     if (op > whave) {
00177                         strm->msg = (char *)"invalid distance too far back";
00178                         state->mode = BAD;
00179                         break;
00180                     }
00181                     from = window - OFF;
00182                     if (write == 0) {           /* very common case */
00183                         from += wsize - op;
00184                         if (op < len) {         /* some from window */
00185                             len -= op;
00186                             do {
00187                                 PUP(out) = PUP(from);
00188                             } while (--op);
00189                             from = out - dist;  /* rest from output */
00190                         }
00191                     }
00192                     else if (write < op) {      /* wrap around window */
00193                         from += wsize + write - op;
00194                         op -= write;
00195                         if (op < len) {         /* some from end of window */
00196                             len -= op;
00197                             do {
00198                                 PUP(out) = PUP(from);
00199                             } while (--op);
00200                             from = window - OFF;
00201                             if (write < len) {  /* some from start of window */
00202                                 op = write;
00203                                 len -= op;
00204                                 do {
00205                                     PUP(out) = PUP(from);
00206                                 } while (--op);
00207                                 from = out - dist;      /* rest from output */
00208                             }
00209                         }
00210                     }
00211                     else {                      /* contiguous in window */
00212                         from += write - op;
00213                         if (op < len) {         /* some from window */
00214                             len -= op;
00215                             do {
00216                                 PUP(out) = PUP(from);
00217                             } while (--op);
00218                             from = out - dist;  /* rest from output */
00219                         }
00220                     }
00221                     while (len > 2) {
00222                         PUP(out) = PUP(from);
00223                         PUP(out) = PUP(from);
00224                         PUP(out) = PUP(from);
00225                         len -= 3;
00226                     }
00227                     if (len) {
00228                         PUP(out) = PUP(from);
00229                         if (len > 1)
00230                             PUP(out) = PUP(from);
00231                     }
00232                 }
00233                 else {
00234                     from = out - dist;          /* copy direct from output */
00235                     do {                        /* minimum length is three */
00236                         PUP(out) = PUP(from);
00237                         PUP(out) = PUP(from);
00238                         PUP(out) = PUP(from);
00239                         len -= 3;
00240                     } while (len > 2);
00241                     if (len) {
00242                         PUP(out) = PUP(from);
00243                         if (len > 1)
00244                             PUP(out) = PUP(from);
00245                     }
00246                 }
00247             }
00248             else if ((op & 64) == 0) {          /* 2nd level distance code */
00249                 this = dcode[this.val + (hold & ((1U << op) - 1))];
00250                 goto dodist;
00251             }
00252             else {
00253                 strm->msg = (char *)"invalid distance code";
00254                 state->mode = BAD;
00255                 break;
00256             }
00257         }
00258         else if ((op & 64) == 0) {              /* 2nd level length code */
00259             this = lcode[this.val + (hold & ((1U << op) - 1))];
00260             goto dolen;
00261         }
00262         else if (op & 32) {                     /* end-of-block */
00263             Tracevv((stderr, "inflate:         end of block\n"));
00264             state->mode = TYPE;
00265             break;
00266         }
00267         else {
00268             strm->msg = (char *)"invalid literal/length code";
00269             state->mode = BAD;
00270             break;
00271         }
00272     } while (in < last && out < end);
00273 
00274     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
00275     len = bits >> 3;
00276     in -= len;
00277     bits -= len << 3;
00278     hold &= (1U << bits) - 1;
00279 
00280     /* update state and return */
00281     strm->next_in = in + OFF;
00282     strm->next_out = out + OFF;
00283     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
00284     strm->avail_out = (unsigned)(out < end ?
00285                                  257 + (end - out) : 257 - (out - end));
00286     state->hold = hold;
00287     state->bits = bits;
00288     return;
00289 }
00290 
00291 /*
00292    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
00293    - Using bit fields for code structure
00294    - Different op definition to avoid & for extra bits (do & for table bits)
00295    - Three separate decoding do-loops for direct, window, and write == 0
00296    - Special case for distance > 1 copies to do overlapped load and store copy
00297    - Explicit branch predictions (based on measured branch probabilities)
00298    - Deferring match copy and interspersed it with decoding subsequent codes
00299    - Swapping literal/length else
00300    - Swapping window/direct else
00301    - Larger unrolled copy loops (three is about right)
00302    - Moving len -= 3 statement into middle of loop
00303  */
00304 
00305 #endif /* !ASMINF */