inffast.c

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