err.no Git - linux-2.6/blob - lib/zlib_inflate/inffast.c

   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 <linux/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     - @start:   inflate()'s starting value for strm->avail_out
  68  */
  69 void inflate_fast(z_streamp strm, unsigned start)
  70 {
  71     struct inflate_state *state;
  72     const unsigned char *in;    /* local strm->next_in */
  73     const unsigned char *last;  /* while in < last, enough input available */
  74     unsigned char *out;         /* local strm->next_out */
  75     unsigned char *beg;         /* inflate()'s initial strm->next_out */
  76     unsigned char *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 *window;      /* allocated sliding window, if wsize != 0 */
  84     unsigned long hold;         /* local strm->hold */
  85     unsigned bits;              /* local strm->bits */
  86     code const *lcode;          /* local strm->lencode */
  87     code const *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 *from;        /* where to copy match from */
  96
  97     /* copy state to local variables */
  98     state = (struct inflate_state *)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             PUP(out) = (unsigned char)(this.val);
 135         }
 136         else if (op & 16) {                     /* length base */
 137             len = (unsigned)(this.val);
 138             op &= 15;                           /* number of extra bits */
 139             if (op) {
 140                 if (bits < op) {
 141                     hold += (unsigned long)(PUP(in)) << bits;
 142                     bits += 8;
 143                 }
 144                 len += (unsigned)hold & ((1U << op) - 1);
 145                 hold >>= op;
 146                 bits -= op;
 147             }
 148             if (bits < 15) {
 149                 hold += (unsigned long)(PUP(in)) << bits;
 150                 bits += 8;
 151                 hold += (unsigned long)(PUP(in)) << bits;
 152                 bits += 8;
 153             }
 154             this = dcode[hold & dmask];
 155           dodist:
 156             op = (unsigned)(this.bits);
 157             hold >>= op;
 158             bits -= op;
 159             op = (unsigned)(this.op);
 160             if (op & 16) {                      /* distance base */
 161                 dist = (unsigned)(this.val);
 162                 op &= 15;                       /* number of extra bits */
 163                 if (bits < op) {
 164                     hold += (unsigned long)(PUP(in)) << bits;
 165                     bits += 8;
 166                     if (bits < op) {
 167                         hold += (unsigned long)(PUP(in)) << bits;
 168                         bits += 8;
 169                     }
 170                 }
 171                 dist += (unsigned)hold & ((1U << op) - 1);
 172 #ifdef INFLATE_STRICT
 173                 if (dist > dmax) {
 174                     strm->msg = (char *)"invalid distance too far back";
 175                     state->mode = BAD;
 176                     break;
 177                 }
 178 #endif
 179                 hold >>= op;
 180                 bits -= op;
 181                 op = (unsigned)(out - beg);     /* max distance in output */
 182                 if (dist > op) {                /* see if copy from window */
 183                     op = dist - op;             /* distance back in window */
 184                     if (op > whave) {
 185                         strm->msg = (char *)"invalid distance too far back";
 186                         state->mode = BAD;
 187                         break;
 188                     }
 189                     from = window - OFF;
 190                     if (write == 0) {           /* very common case */
 191                         from += wsize - op;
 192                         if (op < len) {         /* some from window */
 193                             len -= op;
 194                             do {
 195                                 PUP(out) = PUP(from);
 196                             } while (--op);
 197                             from = out - dist;  /* rest from output */
 198                         }
 199                     }
 200                     else if (write < op) {      /* wrap around window */
 201                         from += wsize + write - op;
 202                         op -= write;
 203                         if (op < len) {         /* some from end of window */
 204                             len -= op;
 205                             do {
 206                                 PUP(out) = PUP(from);
 207                             } while (--op);
 208                             from = window - OFF;
 209                             if (write < len) {  /* some from start of window */
 210                                 op = write;
 211                                 len -= op;
 212                                 do {
 213                                     PUP(out) = PUP(from);
 214                                 } while (--op);
 215                                 from = out - dist;      /* rest from output */
 216                             }
 217                         }
 218                     }
 219                     else {                      /* contiguous in window */
 220                         from += write - op;
 221                         if (op < len) {         /* some from window */
 222                             len -= op;
 223                             do {
 224                                 PUP(out) = PUP(from);
 225                             } while (--op);
 226                             from = out - dist;  /* rest from output */
 227                         }
 228                     }
 229                     while (len > 2) {
 230                         PUP(out) = PUP(from);
 231                         PUP(out) = PUP(from);
 232                         PUP(out) = PUP(from);
 233                         len -= 3;
 234                     }
 235                     if (len) {
 236                         PUP(out) = PUP(from);
 237                         if (len > 1)
 238                             PUP(out) = PUP(from);
 239                     }
 240                 }
 241                 else {
 242                     from = out - dist;          /* copy direct from output */
 243                     do {                        /* minimum length is three */
 244                         PUP(out) = PUP(from);
 245                         PUP(out) = PUP(from);
 246                         PUP(out) = PUP(from);
 247                         len -= 3;
 248                     } while (len > 2);
 249                     if (len) {
 250                         PUP(out) = PUP(from);
 251                         if (len > 1)
 252                             PUP(out) = PUP(from);
 253                     }
 254                 }
 255             }
 256             else if ((op & 64) == 0) {          /* 2nd level distance code */
 257                 this = dcode[this.val + (hold & ((1U << op) - 1))];
 258                 goto dodist;
 259             }
 260             else {
 261                 strm->msg = (char *)"invalid distance code";
 262                 state->mode = BAD;
 263                 break;
 264             }
 265         }
 266         else if ((op & 64) == 0) {              /* 2nd level length code */
 267             this = lcode[this.val + (hold & ((1U << op) - 1))];
 268             goto dolen;
 269         }
 270         else if (op & 32) {                     /* end-of-block */
 271             state->mode = TYPE;
 272             break;
 273         }
 274         else {
 275             strm->msg = (char *)"invalid literal/length code";
 276             state->mode = BAD;
 277             break;
 278         }
 279     } while (in < last && out < end);
 280
 281     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
 282     len = bits >> 3;
 283     in -= len;
 284     bits -= len << 3;
 285     hold &= (1U << bits) - 1;
 286
 287     /* update state and return */
 288     strm->next_in = in + OFF;
 289     strm->next_out = out + OFF;
 290     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
 291     strm->avail_out = (unsigned)(out < end ?
 292                                  257 + (end - out) : 257 - (out - end));
 293     state->hold = hold;
 294     state->bits = bits;
 295     return;
 296 }
 297
 298 /*
 299    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
 300    - Using bit fields for code structure
 301    - Different op definition to avoid & for extra bits (do & for table bits)
 302    - Three separate decoding do-loops for direct, window, and write == 0
 303    - Special case for distance > 1 copies to do overlapped load and store copy
 304    - Explicit branch predictions (based on measured branch probabilities)
 305    - Deferring match copy and interspersed it with decoding subsequent codes
 306    - Swapping literal/length else
 307    - Swapping window/direct else
 308    - Larger unrolled copy loops (three is about right)
 309    - Moving len -= 3 statement into middle of loop
 310  */
 311
 312 #endif /* !ASMINF */