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