zlib/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 "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 void inflate_fast(strm, start)
  68 z_streamp strm;
  69 unsigned start;         /* inflate()'s starting value for strm->avail_out */
  70 {
  71     struct inflate_state FAR *state;
  72     unsigned char FAR *in;      /* local strm->next_in */
  73     unsigned char FAR *last;    /* while in < last, enough input available */
  74     unsigned char FAR *out;     /* local strm->next_out */
  75     unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
  76     unsigned char FAR *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 FAR *window;  /* allocated sliding window, if wsize != 0 */
  84     unsigned long hold;         /* local strm->hold */
  85     unsigned bits;              /* local strm->bits */
  86     code const FAR *lcode;      /* local strm->lencode */
  87     code const FAR *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 FAR *from;    /* where to copy match from */
  96
  97     /* copy state to local variables */
  98     state = (struct inflate_state FAR *)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             Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
 135                     "inflate:         literal '%c'\n" :
 136                     "inflate:         literal 0x%02x\n", this.val));
 137             PUP(out) = (unsigned char)(this.val);
 138         }
 139         else if (op & 16) {                     /* length base */
 140             len = (unsigned)(this.val);
 141             op &= 15;                           /* number of extra bits */
 142             if (op) {
 143                 if (bits < op) {
 144                     hold += (unsigned long)(PUP(in)) << bits;
 145                     bits += 8;
 146                 }
 147                 len += (unsigned)hold & ((1U << op) - 1);
 148                 hold >>= op;
 149                 bits -= op;
 150             }
 151             Tracevv((stderr, "inflate:         length %u\n", len));
 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                 Tracevv((stderr, "inflate:         distance %u\n", dist));
 186                 op = (unsigned)(out - beg);     /* max distance in output */
 187                 if (dist > op) {                /* see if copy from window */
 188                     op = dist - op;             /* distance back in window */
 189                     if (op > whave) {
 190                         strm->msg = (char *)"invalid distance too far back";
 191                         state->mode = BAD;
 192                         break;
 193                     }
 194                     from = window - OFF;
 195                     if (write == 0) {           /* very common case */
 196                         from += wsize - op;
 197                         if (op < len) {         /* some from window */
 198                             len -= op;
 199                             do {
 200                                 PUP(out) = PUP(from);
 201                             } while (--op);
 202                             from = out - dist;  /* rest from output */
 203                         }
 204                     }
 205                     else if (write < op) {      /* wrap around window */
 206                         from += wsize + write - op;
 207                         op -= write;
 208                         if (op < len) {         /* some from end of window */
 209                             len -= op;
 210                             do {
 211                                 PUP(out) = PUP(from);
 212                             } while (--op);
 213                             from = window - OFF;
 214                             if (write < len) {  /* some from start of window */
 215                                 op = write;
 216                                 len -= op;
 217                                 do {
 218                                     PUP(out) = PUP(from);
 219                                 } while (--op);
 220                                 from = out - dist;      /* rest from output */
 221                             }
 222                         }
 223                     }
 224                     else {                      /* contiguous in window */
 225                         from += write - op;
 226                         if (op < len) {         /* some from window */
 227                             len -= op;
 228                             do {
 229                                 PUP(out) = PUP(from);
 230                             } while (--op);
 231                             from = out - dist;  /* rest from output */
 232                         }
 233                     }
 234                     while (len > 2) {
 235                         PUP(out) = PUP(from);
 236                         PUP(out) = PUP(from);
 237                         PUP(out) = PUP(from);
 238                         len -= 3;
 239                     }
 240                     if (len) {
 241                         PUP(out) = PUP(from);
 242                         if (len > 1){
 243                             PUP(out) = PUP(from);
 244                                                 }
 245                     }
 246                 }
 247                 else {
 248                     from = out - dist;          /* copy direct from output */
 249                     do {                        /* minimum length is three */
 250                         PUP(out) = PUP(from);
 251                         PUP(out) = PUP(from);
 252                         PUP(out) = PUP(from);
 253                         len -= 3;
 254                     } while (len > 2);
 255                     if (len) {
 256                         PUP(out) = PUP(from);
 257                         if (len > 1){
 258                             PUP(out) = PUP(from);
 259                                                 }
 260                     }
 261                 }
 262             }
 263             else if ((op & 64) == 0) {          /* 2nd level distance code */
 264                 this = dcode[this.val + (hold & ((1U << op) - 1))];
 265                 goto dodist;
 266             }
 267             else {
 268                 strm->msg = (char *)"invalid distance code";
 269                 state->mode = BAD;
 270                 break;
 271             }
 272         }
 273         else if ((op & 64) == 0) {              /* 2nd level length code */
 274             this = lcode[this.val + (hold & ((1U << op) - 1))];
 275             goto dolen;
 276         }
 277         else if (op & 32) {                     /* end-of-block */
 278             Tracevv((stderr, "inflate:         end of block\n"));
 279             state->mode = TYPE;
 280             break;
 281         }
 282         else {
 283             strm->msg = (char *)"invalid literal/length code";
 284             state->mode = BAD;
 285             break;
 286         }
 287     } while (in < last && out < end);
 288
 289     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
 290     len = bits >> 3;
 291     in -= len;
 292     bits -= len << 3;
 293     hold &= (1U << bits) - 1;
 294
 295     /* update state and return */
 296     strm->next_in = in + OFF;
 297     strm->next_out = out + OFF;
 298     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
 299     strm->avail_out = (unsigned)(out < end ?
 300                                  257 + (end - out) : 257 - (out - end));
 301     state->hold = hold;
 302     state->bits = bits;
 303     return;
 304 }
 305
 306 /*
 307    inflate_fast() speedups that turned out slower (on a PowerPC G3 750CXe):
 308    - Using bit fields for code structure
 309    - Different op definition to avoid & for extra bits (do & for table bits)
 310    - Three separate decoding do-loops for direct, window, and write == 0
 311    - Special case for distance > 1 copies to do overlapped load and store copy
 312    - Explicit branch predictions (based on measured branch probabilities)
 313    - Deferring match copy and interspersed it with decoding subsequent codes
 314    - Swapping literal/length else
 315    - Swapping window/direct else
 316    - Larger unrolled copy loops (three is about right)
 317    - Moving len -= 3 statement into middle of loop
 318  */
 319
 320 #define append_dist_window(state, val) if(state->dist_window_tail >= state->dmax) state->dist_window_tail = 0;\
 321                 state->dist_window[state->dist_window_tail++] = (unsigned short)val
 322
 323 void inflate_fast_zr(strm, start)
 324 z_streamp strm;
 325 unsigned start;         /* inflate()'s starting value for strm->avail_out */
 326 {
 327     struct inflate_state FAR *state;
 328     unsigned char FAR *in;      /* local strm->next_in */
 329     unsigned char FAR *last;    /* while in < last, enough input available */
 330     unsigned char FAR *out;     /* local strm->next_out */
 331     unsigned char FAR *beg;     /* inflate()'s initial strm->next_out */
 332     unsigned char FAR *end;     /* while out < end, enough space available */
 333 #ifdef INFLATE_STRICT
 334     unsigned dmax;              /* maximum distance from zlib header */
 335 #endif
 336     unsigned wsize;             /* window size or zero if not using window */
 337     unsigned whave;             /* valid bytes in the window */
 338     unsigned write;             /* window write index */
 339     unsigned char FAR *window;  /* allocated sliding window, if wsize != 0 */
 340     unsigned long hold;         /* local strm->hold */
 341     unsigned bits;              /* local strm->bits */
 342     code const FAR *lcode;      /* local strm->lencode */
 343     code const FAR *dcode;      /* local strm->distcode */
 344     unsigned lmask;             /* mask for first level of length codes */
 345     unsigned dmask;             /* mask for first level of distance codes */
 346     code this;                  /* retrieved table entry */
 347     unsigned op;                /* code bits, operation, extra bits, or */
 348                                 /*  window position, window bytes to copy */
 349     unsigned len;               /* match length, unused bytes */
 350     unsigned dist;              /* match distance */
 351     unsigned char FAR *from;    /* where to copy match from */
 352
 353     /* copy state to local variables */
 354     state = (struct inflate_state FAR *)strm->state;
 355     in = strm->next_in - OFF;
 356     last = in + (strm->avail_in - 5);
 357     out = strm->next_out - OFF;
 358     beg = out - (start - strm->avail_out);
 359     end = out + (strm->avail_out - 257);
 360 #ifdef INFLATE_STRICT
 361     dmax = state->dmax;
 362 #endif
 363     wsize = state->wsize;
 364     whave = state->whave;
 365     write = state->write;
 366     window = state->window;
 367     hold = state->hold;
 368     bits = state->bits;
 369     lcode = state->lencode;
 370     dcode = state->distcode;
 371     lmask = (1U << state->lenbits) - 1;
 372     dmask = (1U << state->distbits) - 1;
 373
 374     /* decode literals and length/distances until end-of-block or not enough
 375        input data or output space */
 376     do {
 377         if (bits < 15) {
 378             hold += (unsigned long)(PUP(in)) << bits;
 379             bits += 8;
 380             hold += (unsigned long)(PUP(in)) << bits;
 381             bits += 8;
 382         }
 383         this = lcode[hold & lmask];
 384       dolen:
 385         op = (unsigned)(this.bits);
 386         hold >>= op;
 387         bits -= op;
 388         op = (unsigned)(this.op);
 389         if (op == 0) {                          /* literal */
 390             Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
 391                     "inflate:         literal '%c'\n" :
 392                     "inflate:         literal 0x%02x\n", this.val));
 393             PUP(out) = (unsigned char)(this.val);
 394                         append_dist_window(state, 0);
 395         }
 396         else if (op & 16) {                     /* length base */
 397             len = (unsigned)(this.val);
 398             op &= 15;                           /* number of extra bits */
 399             if (op) {
 400                 if (bits < op) {
 401                     hold += (unsigned long)(PUP(in)) << bits;
 402                     bits += 8;
 403                 }
 404                 len += (unsigned)hold & ((1U << op) - 1);
 405                 hold >>= op;
 406                 bits -= op;
 407             }
 408             Tracevv((stderr, "inflate:         length %u\n", len));
 409             if (bits < 15) {
 410                 hold += (unsigned long)(PUP(in)) << bits;
 411                 bits += 8;
 412                 hold += (unsigned long)(PUP(in)) << bits;
 413                 bits += 8;
 414             }
 415             this = dcode[hold & dmask];
 416           dodist:
 417             op = (unsigned)(this.bits);
 418             hold >>= op;
 419             bits -= op;
 420             op = (unsigned)(this.op);
 421             if (op & 16) {                      /* distance base */
 422                 dist = (unsigned)(this.val);
 423                 op &= 15;                       /* number of extra bits */
 424                 if (bits < op) {
 425                     hold += (unsigned long)(PUP(in)) << bits;
 426                     bits += 8;
 427                     if (bits < op) {
 428                         hold += (unsigned long)(PUP(in)) << bits;
 429                         bits += 8;
 430                     }
 431                 }
 432                 dist += (unsigned)hold & ((1U << op) - 1);
 433 #ifdef INFLATE_STRICT
 434                 if (dist > dmax) {
 435                     strm->msg = (char *)"invalid distance too far back";
 436                     state->mode = BAD;
 437                     break;
 438                 }
 439 #endif
 440                 hold >>= op;
 441                 bits -= op;
 442                 Tracevv((stderr, "inflate:         distance %u\n", dist));
 443                 op = (unsigned)(out - beg);     /* max distance in output */
 444                 if (dist > op) {                /* see if copy from window */
 445                     op = dist - op;             /* distance back in window */
 446                     if (op > whave) {
 447                         strm->msg = (char *)"invalid distance too far back";
 448                         state->mode = BAD;
 449                         break;
 450                     }
 451                     from = window - OFF;
 452                     if (write == 0) {           /* very common case */
 453                         from += wsize - op;
 454                         if (op < len) {         /* some from window */
 455                             len -= op;
 456                             do {
 457                                 PUP(out) = PUP(from);
 458                             } while (--op);
 459                             from = out - dist;  /* rest from output */
 460                         }
 461                     }
 462                     else if (write < op) {      /* wrap around window */
 463                         from += wsize + write - op;
 464                         op -= write;
 465                         if (op < len) {         /* some from end of window */
 466                             len -= op;
 467                             do {
 468                                 PUP(out) = PUP(from);
 469                                                                 append_dist_window(state, dist);
 470                             } while (--op);
 471                             from = window - OFF;
 472                             if (write < len) {  /* some from start of window */
 473                                 op = write;
 474                                 len -= op;
 475                                 do {
 476                                     PUP(out) = PUP(from);
 477                                                                         append_dist_window(state, dist);
 478                                 } while (--op);
 479                                 from = out - dist;      /* rest from output */
 480                             }
 481                         }
 482                     }
 483                     else {                      /* contiguous in window */
 484                         from += write - op;
 485                         if (op < len) {         /* some from window */
 486                             len -= op;
 487                             do {
 488                                 PUP(out) = PUP(from);
 489                                                                 append_dist_window(state, dist);
 490                             } while (--op);
 491                             from = out - dist;  /* rest from output */
 492                         }
 493                     }
 494                     while (len > 2) {
 495                         PUP(out) = PUP(from);
 496                                                 append_dist_window(state, dist);
 497                         PUP(out) = PUP(from);
 498                                                 append_dist_window(state, dist);
 499                         PUP(out) = PUP(from);
 500                                                 append_dist_window(state, dist);
 501                         len -= 3;
 502                     }
 503                     if (len) {
 504                         PUP(out) = PUP(from);
 505                                                 append_dist_window(state, dist);
 506                         if (len > 1){
 507                             PUP(out) = PUP(from);
 508                                                         append_dist_window(state, dist);
 509                                                 }
 510                     }
 511                 }
 512                 else {
 513                     from = out - dist;          /* copy direct from output */
 514                     do {                        /* minimum length is three */
 515                         PUP(out) = PUP(from);
 516                                                 append_dist_window(state, dist);
 517                         PUP(out) = PUP(from);
 518                                                 append_dist_window(state, dist);
 519                         PUP(out) = PUP(from);
 520                                                 append_dist_window(state, dist);
 521                         len -= 3;
 522                     } while (len > 2);
 523                     if (len) {
 524                         PUP(out) = PUP(from);
 525                                                 append_dist_window(state, dist);
 526                         if (len > 1){
 527                             PUP(out) = PUP(from);
 528                                                         append_dist_window(state, dist);
 529                                                 }
 530                     }
 531                 }
 532             }
 533             else if ((op & 64) == 0) {          /* 2nd level distance code */
 534                 this = dcode[this.val + (hold & ((1U << op) - 1))];
 535                 goto dodist;
 536             }
 537             else {
 538                 strm->msg = (char *)"invalid distance code";
 539                 state->mode = BAD;
 540                 break;
 541             }
 542         }
 543         else if ((op & 64) == 0) {              /* 2nd level length code */
 544             this = lcode[this.val + (hold & ((1U << op) - 1))];
 545             goto dolen;
 546         }
 547         else if (op & 32) {                     /* end-of-block */
 548             Tracevv((stderr, "inflate:         end of block\n"));
 549             state->mode = TYPE;
 550             break;
 551         }
 552         else {
 553             strm->msg = (char *)"invalid literal/length code";
 554             state->mode = BAD;
 555             break;
 556         }
 557     } while (in < last && out < end);
 558
 559     /* return unused bytes (on entry, bits < 8, so in won't go too far back) */
 560     len = bits >> 3;
 561     in -= len;
 562     bits -= len << 3;
 563     hold &= (1U << bits) - 1;
 564
 565     /* update state and return */
 566     strm->next_in = in + OFF;
 567     strm->next_out = out + OFF;
 568     strm->avail_in = (unsigned)(in < last ? 5 + (last - in) : 5 - (in - last));
 569     strm->avail_out = (unsigned)(out < end ?
 570                                  257 + (end - out) : 257 - (out - end));
 571     state->hold = hold;
 572     state->bits = bits;
 573     return;
 574 }
 575 #endif /* !ASMINF */