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