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