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