Back to index

lightning-sunbird  0.9+nobinonly
inffast.c
Go to the documentation of this file.
00001 /* inffast.c -- fast decoding
00002  * Copyright (C) 1995-2004 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 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 write;             /* 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 this;                  /* 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     write = state->write;
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         this = lcode[hold & lmask];
00128       dolen:
00129         op = (unsigned)(this.bits);
00130         hold >>= op;
00131         bits -= op;
00132         op = (unsigned)(this.op);
00133         if (op == 0) {                          /* literal */
00134             Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
00135                     "inflate:         literal '%c'\n" :
00136                     "inflate:         literal 0x%02x\n", this.val));
00137             PUP(out) = (unsigned char)(this.val);
00138         }
00139         else if (op & 16) {                     /* length base */
00140             len = (unsigned)(this.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             this = dcode[hold & dmask];
00159           dodist:
00160             op = (unsigned)(this.bits);
00161             hold >>= op;
00162             bits -= op;
00163             op = (unsigned)(this.op);
00164             if (op & 16) {                      /* distance base */
00165                 dist = (unsigned)(this.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                         strm->msg = (char *)"invalid distance too far back";
00191                         state->mode = BAD;
00192                         break;
00193                     }
00194                     from = window - OFF;
00195                     if (write == 0) {           /* very common case */
00196                         from += wsize - op;
00197                         if (op < len) {         /* some from window */
00198                             len -= op;
00199                             do {
00200                                 PUP(out) = PUP(from);
00201                             } while (--op);
00202                             from = out - dist;  /* rest from output */
00203                         }
00204                     }
00205                     else if (write < op) {      /* wrap around window */
00206                         from += wsize + write - op;
00207                         op -= write;
00208                         if (op < len) {         /* some from end of window */
00209                             len -= op;
00210                             do {
00211                                 PUP(out) = PUP(from);
00212                             } while (--op);
00213                             from = window - OFF;
00214                             if (write < len) {  /* some from start of window */
00215                                 op = write;
00216                                 len -= op;
00217                                 do {
00218                                     PUP(out) = PUP(from);
00219                                 } while (--op);
00220                                 from = out - dist;      /* rest from output */
00221                             }
00222                         }
00223                     }
00224                     else {                      /* contiguous in window */
00225                         from += write - op;
00226                         if (op < len) {         /* some from window */
00227                             len -= op;
00228                             do {
00229                                 PUP(out) = PUP(from);
00230                             } while (--op);
00231                             from = out - dist;  /* rest from output */
00232                         }
00233                     }
00234                     while (len > 2) {
00235                         PUP(out) = PUP(from);
00236                         PUP(out) = PUP(from);
00237                         PUP(out) = PUP(from);
00238                         len -= 3;
00239                     }
00240                     if (len) {
00241                         PUP(out) = PUP(from);
00242                         if (len > 1)
00243                             PUP(out) = PUP(from);
00244                     }
00245                 }
00246                 else {
00247                     from = out - dist;          /* copy direct from output */
00248                     do {                        /* minimum length is three */
00249                         PUP(out) = PUP(from);
00250                         PUP(out) = PUP(from);
00251                         PUP(out) = PUP(from);
00252                         len -= 3;
00253                     } while (len > 2);
00254                     if (len) {
00255                         PUP(out) = PUP(from);
00256                         if (len > 1)
00257                             PUP(out) = PUP(from);
00258                     }
00259                 }
00260             }
00261             else if ((op & 64) == 0) {          /* 2nd level distance code */
00262                 this = dcode[this.val + (hold & ((1U << op) - 1))];
00263                 goto dodist;
00264             }
00265             else {
00266                 strm->msg = (char *)"invalid distance code";
00267                 state->mode = BAD;
00268                 break;
00269             }
00270         }
00271         else if ((op & 64) == 0) {              /* 2nd level length code */
00272             this = lcode[this.val + (hold & ((1U << op) - 1))];
00273             goto dolen;
00274         }
00275         else if (op & 32) {                     /* end-of-block */
00276             Tracevv((stderr, "inflate:         end of block\n"));
00277             state->mode = TYPE;
00278             break;
00279         }
00280         else {
00281             strm->msg = (char *)"invalid literal/length code";
00282             state->mode = BAD;
00283             break;
00284         }
00285     } while (in < last && out < end);
00286 
00287     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
00288     len = bits >> 3;
00289     in -= len;
00290     bits -= len << 3;
00291     hold &= (1U << bits) - 1;
00292 
00293     /* update state and return */
00294     strm->next_in = in + OFF;
00295     strm->next_out = out + OFF;
00296     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
00297     strm->avail_out = (unsigned)(out < end ?
00298                                  257 + (end - out) : 257 - (out - end));
00299     state->hold = hold;
00300     state->bits = bits;
00301     return;
00302 }
00303 
00304 /*
00305    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
00306    - Using bit fields for code structure
00307    - Different op definition to avoid & for extra bits (do & for table bits)
00308    - Three separate decoding do-loops for direct, window, and write == 0
00309    - Special case for distance > 1 copies to do overlapped load and store copy
00310    - Explicit branch predictions (based on measured branch probabilities)
00311    - Deferring match copy and interspersed it with decoding subsequent codes
00312    - Swapping literal/length else
00313    - Swapping window/direct else
00314    - Larger unrolled copy loops (three is about right)
00315    - Moving len -= 3 statement into middle of loop
00316  */
00317 
00318 #endif /* !ASMINF */