lib/zlib/inflate.c

   1 /* inflate.c -- zlib decompression
   2  * Copyright (C) 1995-2005 Mark Adler
   3  * For conditions of distribution and use, see copyright notice in zlib.h
   4  */
   5 local void fixedtables OF((struct inflate_state FAR *state));
   6 local int updatewindow OF((z_streamp strm, unsigned out));
   7
   8 int ZEXPORT inflateReset(z_streamp strm)
   9 {
  10     struct inflate_state FAR *state;
  11
  12     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  13     state = (struct inflate_state FAR *)strm->state;
  14     strm->total_in = strm->total_out = state->total = 0;
  15     strm->msg = Z_NULL;
  16     strm->adler = 1;        /* to support ill-conceived Java test suite */
  17     state->mode = HEAD;
  18     state->last = 0;
  19     state->havedict = 0;
  20     state->dmax = 32768U;
  21     state->head = Z_NULL;
  22     state->wsize = 0;
  23     state->whave = 0;
  24     state->write = 0;
  25     state->hold = 0;
  26     state->bits = 0;
  27     state->lencode = state->distcode = state->next = state->codes;
  28     WATCHDOG_RESET();
  29     Tracev((stderr, "inflate: reset\n"));
  30     return Z_OK;
  31 }
  32
  33 int ZEXPORT inflateInit2_(z_streamp strm, int windowBits, const char *version,
  34                           int stream_size)
  35 {
  36     struct inflate_state FAR *state;
  37
  38     if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
  39         stream_size != (int)(sizeof(z_stream)))
  40         return Z_VERSION_ERROR;
  41     if (strm == Z_NULL) return Z_STREAM_ERROR;
  42     strm->msg = Z_NULL;                 /* in case we return an error */
  43     if (strm->zalloc == (alloc_func)0) {
  44         strm->zalloc = zcalloc;
  45         strm->opaque = (voidpf)0;
  46     }
  47     if (strm->zfree == (free_func)0) strm->zfree = zcfree;
  48     state = (struct inflate_state FAR *)
  49             ZALLOC(strm, 1, sizeof(struct inflate_state));
  50     if (state == Z_NULL) return Z_MEM_ERROR;
  51     Tracev((stderr, "inflate: allocated\n"));
  52     strm->state = (struct internal_state FAR *)state;
  53     if (windowBits < 0) {
  54         state->wrap = 0;
  55         windowBits = -windowBits;
  56     }
  57     else {
  58         state->wrap = (windowBits >> 4) + 1;
  59 #ifdef GUNZIP
  60         if (windowBits < 48) windowBits &= 15;
  61 #endif
  62     }
  63     if (windowBits < 8 || windowBits > 15) {
  64         ZFREE(strm, state);
  65         strm->state = Z_NULL;
  66         return Z_STREAM_ERROR;
  67     }
  68     state->wbits = (unsigned)windowBits;
  69     state->window = Z_NULL;
  70     return inflateReset(strm);
  71 }
  72
  73 int ZEXPORT inflateInit_(z_streamp strm, const char *version, int stream_size)
  74 {
  75     return inflateInit2_(strm, DEF_WBITS, version, stream_size);
  76 }
  77
  78 local void fixedtables(struct inflate_state FAR *state)
  79 {
  80     state->lencode = lenfix;
  81     state->lenbits = 9;
  82     state->distcode = distfix;
  83     state->distbits = 5;
  84 }
  85
  86 /*
  87    Update the window with the last wsize (normally 32K) bytes written before
  88    returning.  If window does not exist yet, create it.  This is only called
  89    when a window is already in use, or when output has been written during this
  90    inflate call, but the end of the deflate stream has not been reached yet.
  91    It is also called to create a window for dictionary data when a dictionary
  92    is loaded.
  93
  94    Providing output buffers larger than 32K to inflate() should provide a speed
  95    advantage, since only the last 32K of output is copied to the sliding window
  96    upon return from inflate(), and since all distances after the first 32K of
  97    output will fall in the output data, making match copies simpler and faster.
  98    The advantage may be dependent on the size of the processor's data caches.
  99  */
 100 local int updatewindow(z_streamp strm, unsigned out)
 101 {
 102     struct inflate_state FAR *state;
 103     unsigned copy, dist;
 104
 105     state = (struct inflate_state FAR *)strm->state;
 106
 107     /* if it hasn't been done already, allocate space for the window */
 108     if (state->window == Z_NULL) {
 109         state->window = (unsigned char FAR *)
 110                         ZALLOC(strm, 1U << state->wbits,
 111                                sizeof(unsigned char));
 112         if (state->window == Z_NULL) return 1;
 113     }
 114
 115     /* if window not in use yet, initialize */
 116     if (state->wsize == 0) {
 117         state->wsize = 1U << state->wbits;
 118         state->write = 0;
 119         state->whave = 0;
 120     }
 121
 122     /* copy state->wsize or less output bytes into the circular window */
 123     copy = out - strm->avail_out;
 124     if (copy >= state->wsize) {
 125         zmemcpy(state->window, strm->next_out - state->wsize, state->wsize);
 126         state->write = 0;
 127         state->whave = state->wsize;
 128     }
 129     else {
 130         dist = state->wsize - state->write;
 131         if (dist > copy) dist = copy;
 132         zmemcpy(state->window + state->write, strm->next_out - copy, dist);
 133         copy -= dist;
 134         if (copy) {
 135             zmemcpy(state->window, strm->next_out - copy, copy);
 136             state->write = copy;
 137             state->whave = state->wsize;
 138         }
 139         else {
 140             state->write += dist;
 141             if (state->write == state->wsize) state->write = 0;
 142             if (state->whave < state->wsize) state->whave += dist;
 143         }
 144     }
 145     return 0;
 146 }
 147
 148 /* Macros for inflate(): */
 149
 150 /* check function to use adler32() for zlib or crc32() for gzip */
 151 #ifdef GUNZIP
 152 #  define UPDATE(check, buf, len) \
 153     (state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
 154 #else
 155 #  define UPDATE(check, buf, len) adler32(check, buf, len)
 156 #endif
 157
 158 /* check macros for header crc */
 159 #ifdef GUNZIP
 160 #  define CRC2(check, word) \
 161     do { \
 162         hbuf[0] = (unsigned char)(word); \
 163         hbuf[1] = (unsigned char)((word) >> 8); \
 164         check = crc32(check, hbuf, 2); \
 165     } while (0)
 166
 167 #  define CRC4(check, word) \
 168     do { \
 169         hbuf[0] = (unsigned char)(word); \
 170         hbuf[1] = (unsigned char)((word) >> 8); \
 171         hbuf[2] = (unsigned char)((word) >> 16); \
 172         hbuf[3] = (unsigned char)((word) >> 24); \
 173         check = crc32(check, hbuf, 4); \
 174     } while (0)
 175 #endif
 176
 177 /* Load registers with state in inflate() for speed */
 178 #define LOAD() \
 179     do { \
 180         put = strm->next_out; \
 181         left = strm->avail_out; \
 182         next = strm->next_in; \
 183         have = strm->avail_in; \
 184         hold = state->hold; \
 185         bits = state->bits; \
 186     } while (0)
 187
 188 /* Restore state from registers in inflate() */
 189 #define RESTORE() \
 190     do { \
 191         strm->next_out = put; \
 192         strm->avail_out = left; \
 193         strm->next_in = next; \
 194         strm->avail_in = have; \
 195         state->hold = hold; \
 196         state->bits = bits; \
 197     } while (0)
 198
 199 /* Clear the input bit accumulator */
 200 #define INITBITS() \
 201     do { \
 202         hold = 0; \
 203         bits = 0; \
 204     } while (0)
 205
 206 /* Get a byte of input into the bit accumulator, or return from inflate()
 207    if there is no input available. */
 208 #define PULLBYTE() \
 209     do { \
 210         if (have == 0) goto inf_leave; \
 211         have--; \
 212         hold += (unsigned long)(*next++) << bits; \
 213         bits += 8; \
 214     } while (0)
 215
 216 /* Assure that there are at least n bits in the bit accumulator.  If there is
 217    not enough available input to do that, then return from inflate(). */
 218 #define NEEDBITS(n) \
 219     do { \
 220         while (bits < (unsigned)(n)) \
 221             PULLBYTE(); \
 222     } while (0)
 223
 224 /* Return the low n bits of the bit accumulator (n < 16) */
 225 #define BITS(n) \
 226     ((unsigned)hold & ((1U << (n)) - 1))
 227
 228 /* Remove n bits from the bit accumulator */
 229 #define DROPBITS(n) \
 230     do { \
 231         hold >>= (n); \
 232         bits -= (unsigned)(n); \
 233     } while (0)
 234
 235 /* Remove zero to seven bits as needed to go to a byte boundary */
 236 #define BYTEBITS() \
 237     do { \
 238         hold >>= bits & 7; \
 239         bits -= bits & 7; \
 240     } while (0)
 241
 242 /* Reverse the bytes in a 32-bit value */
 243 #define REVERSE(q) \
 244     ((((q) >> 24) & 0xff) + (((q) >> 8) & 0xff00) + \
 245      (((q) & 0xff00) << 8) + (((q) & 0xff) << 24))
 246
 247 /*
 248    inflate() uses a state machine to process as much input data and generate as
 249    much output data as possible before returning.  The state machine is
 250    structured roughly as follows:
 251
 252     for (;;) switch (state) {
 253     ...
 254     case STATEn:
 255         if (not enough input data or output space to make progress)
 256             return;
 257         ... make progress ...
 258         state = STATEm;
 259         break;
 260     ...
 261     }
 262
 263    so when inflate() is called again, the same case is attempted again, and
 264    if the appropriate resources are provided, the machine proceeds to the
 265    next state.  The NEEDBITS() macro is usually the way the state evaluates
 266    whether it can proceed or should return.  NEEDBITS() does the return if
 267    the requested bits are not available.  The typical use of the BITS macros
 268    is:
 269
 270         NEEDBITS(n);
 271         ... do something with BITS(n) ...
 272         DROPBITS(n);
 273
 274    where NEEDBITS(n) either returns from inflate() if there isn't enough
 275    input left to load n bits into the accumulator, or it continues.  BITS(n)
 276    gives the low n bits in the accumulator.  When done, DROPBITS(n) drops
 277    the low n bits off the accumulator.  INITBITS() clears the accumulator
 278    and sets the number of available bits to zero.  BYTEBITS() discards just
 279    enough bits to put the accumulator on a byte boundary.  After BYTEBITS()
 280    and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
 281
 282    NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
 283    if there is no input available.  The decoding of variable length codes uses
 284    PULLBYTE() directly in order to pull just enough bytes to decode the next
 285    code, and no more.
 286
 287    Some states loop until they get enough input, making sure that enough
 288    state information is maintained to continue the loop where it left off
 289    if NEEDBITS() returns in the loop.  For example, want, need, and keep
 290    would all have to actually be part of the saved state in case NEEDBITS()
 291    returns:
 292
 293     case STATEw:
 294         while (want < need) {
 295             NEEDBITS(n);
 296             keep[want++] = BITS(n);
 297             DROPBITS(n);
 298         }
 299         state = STATEx;
 300     case STATEx:
 301
 302    As shown above, if the next state is also the next case, then the break
 303    is omitted.
 304
 305    A state may also return if there is not enough output space available to
 306    complete that state.  Those states are copying stored data, writing a
 307    literal byte, and copying a matching string.
 308
 309    When returning, a "goto inf_leave" is used to update the total counters,
 310    update the check value, and determine whether any progress has been made
 311    during that inflate() call in order to return the proper return code.
 312    Progress is defined as a change in either strm->avail_in or strm->avail_out.
 313    When there is a window, goto inf_leave will update the window with the last
 314    output written.  If a goto inf_leave occurs in the middle of decompression
 315    and there is no window currently, goto inf_leave will create one and copy
 316    output to the window for the next call of inflate().
 317
 318    In this implementation, the flush parameter of inflate() only affects the
 319    return code (per zlib.h).  inflate() always writes as much as possible to
 320    strm->next_out, given the space available and the provided input--the effect
 321    documented in zlib.h of Z_SYNC_FLUSH.  Furthermore, inflate() always defers
 322    the allocation of and copying into a sliding window until necessary, which
 323    provides the effect documented in zlib.h for Z_FINISH when the entire input
 324    stream available.  So the only thing the flush parameter actually does is:
 325    when flush is set to Z_FINISH, inflate() cannot return Z_OK.  Instead it
 326    will return Z_BUF_ERROR if it has not reached the end of the stream.
 327  */
 328 int ZEXPORT inflate(z_streamp strm, int flush)
 329 {
 330     struct inflate_state FAR *state;
 331     unsigned char FAR *next;    /* next input */
 332     unsigned char FAR *put;     /* next output */
 333     unsigned have, left;        /* available input and output */
 334     unsigned long hold;         /* bit buffer */
 335     unsigned bits;              /* bits in bit buffer */
 336     unsigned in, out;           /* save starting available input and output */
 337     unsigned copy;              /* number of stored or match bytes to copy */
 338     unsigned char FAR *from;    /* where to copy match bytes from */
 339     code this;                  /* current decoding table entry */
 340     code last;                  /* parent table entry */
 341     unsigned len;               /* length to copy for repeats, bits to drop */
 342     int ret;                    /* return code */
 343 #ifdef GUNZIP
 344     unsigned char hbuf[4];      /* buffer for gzip header crc calculation */
 345 #endif
 346     static const unsigned short order[19] = /* permutation of code lengths */
 347         {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
 348
 349     if (strm == Z_NULL || strm->state == Z_NULL ||
 350         (strm->next_in == Z_NULL && strm->avail_in != 0))
 351         return Z_STREAM_ERROR;
 352
 353     state = (struct inflate_state FAR *)strm->state;
 354     if (state->mode == TYPE) state->mode = TYPEDO;      /* skip check */
 355     LOAD();
 356     in = have;
 357     out = left;
 358     ret = Z_OK;
 359     for (;;)
 360         switch (state->mode) {
 361         case HEAD:
 362             if (state->wrap == 0) {
 363                 state->mode = TYPEDO;
 364                 break;
 365             }
 366             NEEDBITS(16);
 367 #ifdef GUNZIP
 368             if ((state->wrap & 2) && hold == 0x8b1f) {  /* gzip header */
 369                 state->check = crc32(0L, Z_NULL, 0);
 370                 CRC2(state->check, hold);
 371                 INITBITS();
 372                 state->mode = FLAGS;
 373                 break;
 374             }
 375             state->flags = 0;           /* expect zlib header */
 376             if (state->head != Z_NULL)
 377                 state->head->done = -1;
 378             if (!(state->wrap & 1) ||   /* check if zlib header allowed */
 379 #else
 380             if (
 381 #endif
 382                 ((BITS(8) << 8) + (hold >> 8)) % 31) {
 383                 strm->msg = (char *)"incorrect header check";
 384                 state->mode = BAD;
 385                 break;
 386             }
 387             if (BITS(4) != Z_DEFLATED) {
 388                 strm->msg = (char *)"unknown compression method";
 389                 state->mode = BAD;
 390                 break;
 391             }
 392             DROPBITS(4);
 393             len = BITS(4) + 8;
 394             if (len > state->wbits) {
 395                 strm->msg = (char *)"invalid window size";
 396                 state->mode = BAD;
 397                 break;
 398             }
 399             state->dmax = 1U << len;
 400             Tracev((stderr, "inflate:   zlib header ok\n"));
 401             strm->adler = state->check = adler32(0L, Z_NULL, 0);
 402             state->mode = hold & 0x200 ? DICTID : TYPE;
 403             INITBITS();
 404             break;
 405 #ifdef GUNZIP
 406         case FLAGS:
 407             NEEDBITS(16);
 408             state->flags = (int)(hold);
 409             if ((state->flags & 0xff) != Z_DEFLATED) {
 410                 strm->msg = (char *)"unknown compression method";
 411                 state->mode = BAD;
 412                 break;
 413             }
 414             if (state->flags & 0xe000) {
 415                 strm->msg = (char *)"unknown header flags set";
 416                 state->mode = BAD;
 417                 break;
 418             }
 419             if (state->head != Z_NULL)
 420                 state->head->text = (int)((hold >> 8) & 1);
 421             if (state->flags & 0x0200) CRC2(state->check, hold);
 422             INITBITS();
 423             state->mode = TIME;
 424         case TIME:
 425             NEEDBITS(32);
 426             if (state->head != Z_NULL)
 427                 state->head->time = hold;
 428             if (state->flags & 0x0200) CRC4(state->check, hold);
 429             INITBITS();
 430             state->mode = OS;
 431         case OS:
 432             NEEDBITS(16);
 433             if (state->head != Z_NULL) {
 434                 state->head->xflags = (int)(hold & 0xff);
 435                 state->head->os = (int)(hold >> 8);
 436             }
 437             if (state->flags & 0x0200) CRC2(state->check, hold);
 438             INITBITS();
 439             state->mode = EXLEN;
 440         case EXLEN:
 441             if (state->flags & 0x0400) {
 442                 NEEDBITS(16);
 443                 state->length = (unsigned)(hold);
 444                 if (state->head != Z_NULL)
 445                     state->head->extra_len = (unsigned)hold;
 446                 if (state->flags & 0x0200) CRC2(state->check, hold);
 447                 INITBITS();
 448             }
 449             else if (state->head != Z_NULL)
 450                 state->head->extra = Z_NULL;
 451             state->mode = EXTRA;
 452         case EXTRA:
 453             if (state->flags & 0x0400) {
 454                 copy = state->length;
 455                 if (copy > have) copy = have;
 456                 if (copy) {
 457                     if (state->head != Z_NULL &&
 458                         state->head->extra != Z_NULL) {
 459                         len = state->head->extra_len - state->length;
 460                         zmemcpy(state->head->extra + len, next,
 461                                 len + copy > state->head->extra_max ?
 462                                 state->head->extra_max - len : copy);
 463                     }
 464                     if (state->flags & 0x0200)
 465                         state->check = crc32(state->check, next, copy);
 466                     have -= copy;
 467                     next += copy;
 468                     state->length -= copy;
 469                 }
 470                 if (state->length) goto inf_leave;
 471             }
 472             state->length = 0;
 473             state->mode = NAME;
 474         case NAME:
 475             if (state->flags & 0x0800) {
 476                 if (have == 0) goto inf_leave;
 477                 copy = 0;
 478                 do {
 479                     len = (unsigned)(next[copy++]);
 480                     if (state->head != Z_NULL &&
 481                             state->head->name != Z_NULL &&
 482                             state->length < state->head->name_max)
 483                         state->head->name[state->length++] = len;
 484                 } while (len && copy < have);
 485                 if (state->flags & 0x0200)
 486                     state->check = crc32(state->check, next, copy);
 487                 have -= copy;
 488                 next += copy;
 489                 if (len) goto inf_leave;
 490             }
 491             else if (state->head != Z_NULL)
 492                 state->head->name = Z_NULL;
 493             state->length = 0;
 494             state->mode = COMMENT;
 495         case COMMENT:
 496             if (state->flags & 0x1000) {
 497                 if (have == 0) goto inf_leave;
 498                 copy = 0;
 499                 do {
 500                     len = (unsigned)(next[copy++]);
 501                     if (state->head != Z_NULL &&
 502                             state->head->comment != Z_NULL &&
 503                             state->length < state->head->comm_max)
 504                         state->head->comment[state->length++] = len;
 505                 } while (len && copy < have);
 506                 if (state->flags & 0x0200)
 507                     state->check = crc32(state->check, next, copy);
 508                 have -= copy;
 509                 next += copy;
 510                 if (len) goto inf_leave;
 511             }
 512             else if (state->head != Z_NULL)
 513                 state->head->comment = Z_NULL;
 514             state->mode = HCRC;
 515         case HCRC:
 516             if (state->flags & 0x0200) {
 517                 NEEDBITS(16);
 518                 if (hold != (state->check & 0xffff)) {
 519                     strm->msg = (char *)"header crc mismatch";
 520                     state->mode = BAD;
 521                     break;
 522                 }
 523                 INITBITS();
 524             }
 525             if (state->head != Z_NULL) {
 526                 state->head->hcrc = (int)((state->flags >> 9) & 1);
 527                 state->head->done = 1;
 528             }
 529             strm->adler = state->check = crc32(0L, Z_NULL, 0);
 530             state->mode = TYPE;
 531             break;
 532 #endif
 533         case DICTID:
 534             NEEDBITS(32);
 535             strm->adler = state->check = REVERSE(hold);
 536             INITBITS();
 537             state->mode = DICT;
 538         case DICT:
 539             if (state->havedict == 0) {
 540                 RESTORE();
 541                 return Z_NEED_DICT;
 542             }
 543             strm->adler = state->check = adler32(0L, Z_NULL, 0);
 544             state->mode = TYPE;
 545         case TYPE:
 546             WATCHDOG_RESET();
 547             if (flush == Z_BLOCK) goto inf_leave;
 548         case TYPEDO:
 549             if (state->last) {
 550                 BYTEBITS();
 551                 state->mode = CHECK;
 552                 break;
 553             }
 554             NEEDBITS(3);
 555             state->last = BITS(1);
 556             DROPBITS(1);
 557             switch (BITS(2)) {
 558             case 0:                             /* stored block */
 559                 Tracev((stderr, "inflate:     stored block%s\n",
 560                         state->last ? " (last)" : ""));
 561                 state->mode = STORED;
 562                 break;
 563             case 1:                             /* fixed block */
 564                 fixedtables(state);
 565                 Tracev((stderr, "inflate:     fixed codes block%s\n",
 566                         state->last ? " (last)" : ""));
 567                 state->mode = LEN;              /* decode codes */
 568                 break;
 569             case 2:                             /* dynamic block */
 570                 Tracev((stderr, "inflate:     dynamic codes block%s\n",
 571                         state->last ? " (last)" : ""));
 572                 state->mode = TABLE;
 573                 break;
 574             case 3:
 575                 strm->msg = (char *)"invalid block type";
 576                 state->mode = BAD;
 577             }
 578             DROPBITS(2);
 579             break;
 580         case STORED:
 581             BYTEBITS();                         /* go to byte boundary */
 582             NEEDBITS(32);
 583             if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
 584                 strm->msg = (char *)"invalid stored block lengths";
 585                 state->mode = BAD;
 586                 break;
 587             }
 588             state->length = (unsigned)hold & 0xffff;
 589             Tracev((stderr, "inflate:       stored length %u\n",
 590                     state->length));
 591             INITBITS();
 592             state->mode = COPY;
 593         case COPY:
 594             copy = state->length;
 595             if (copy) {
 596                 if (copy > have) copy = have;
 597                 if (copy > left) copy = left;
 598                 if (copy == 0) goto inf_leave;
 599                 zmemcpy(put, next, copy);
 600                 have -= copy;
 601                 next += copy;
 602                 left -= copy;
 603                 put += copy;
 604                 state->length -= copy;
 605                 break;
 606             }
 607             Tracev((stderr, "inflate:       stored end\n"));
 608             state->mode = TYPE;
 609             break;
 610         case TABLE:
 611             NEEDBITS(14);
 612             state->nlen = BITS(5) + 257;
 613             DROPBITS(5);
 614             state->ndist = BITS(5) + 1;
 615             DROPBITS(5);
 616             state->ncode = BITS(4) + 4;
 617             DROPBITS(4);
 618 #ifndef PKZIP_BUG_WORKAROUND
 619             if (state->nlen > 286 || state->ndist > 30) {
 620                 strm->msg = (char *)"too many length or distance symbols";
 621                 state->mode = BAD;
 622                 break;
 623             }
 624 #endif
 625             Tracev((stderr, "inflate:       table sizes ok\n"));
 626             state->have = 0;
 627             state->mode = LENLENS;
 628         case LENLENS:
 629             while (state->have < state->ncode) {
 630                 NEEDBITS(3);
 631                 state->lens[order[state->have++]] = (unsigned short)BITS(3);
 632                 DROPBITS(3);
 633             }
 634             while (state->have < 19)
 635                 state->lens[order[state->have++]] = 0;
 636             state->next = state->codes;
 637             state->lencode = (code const FAR *)(state->next);
 638             state->lenbits = 7;
 639             ret = inflate_table(CODES, state->lens, 19, &(state->next),
 640                                 &(state->lenbits), state->work);
 641             if (ret) {
 642                 strm->msg = (char *)"invalid code lengths set";
 643                 state->mode = BAD;
 644                 break;
 645             }
 646             Tracev((stderr, "inflate:       code lengths ok\n"));
 647             state->have = 0;
 648             state->mode = CODELENS;
 649         case CODELENS:
 650             while (state->have < state->nlen + state->ndist) {
 651                 for (;;) {
 652                     this = state->lencode[BITS(state->lenbits)];
 653                     if ((unsigned)(this.bits) <= bits) break;
 654                     PULLBYTE();
 655                 }
 656                 if (this.val < 16) {
 657                     NEEDBITS(this.bits);
 658                     DROPBITS(this.bits);
 659                     state->lens[state->have++] = this.val;
 660                 }
 661                 else {
 662                     if (this.val == 16) {
 663                         NEEDBITS(this.bits + 2);
 664                         DROPBITS(this.bits);
 665                         if (state->have == 0) {
 666                             strm->msg = (char *)"invalid bit length repeat";
 667                             state->mode = BAD;
 668                             break;
 669                         }
 670                         len = state->lens[state->have - 1];
 671                         copy = 3 + BITS(2);
 672                         DROPBITS(2);
 673                     }
 674                     else if (this.val == 17) {
 675                         NEEDBITS(this.bits + 3);
 676                         DROPBITS(this.bits);
 677                         len = 0;
 678                         copy = 3 + BITS(3);
 679                         DROPBITS(3);
 680                     }
 681                     else {
 682                         NEEDBITS(this.bits + 7);
 683                         DROPBITS(this.bits);
 684                         len = 0;
 685                         copy = 11 + BITS(7);
 686                         DROPBITS(7);
 687                     }
 688                     if (state->have + copy > state->nlen + state->ndist) {
 689                         strm->msg = (char *)"invalid bit length repeat";
 690                         state->mode = BAD;
 691                         break;
 692                     }
 693                     while (copy--)
 694                         state->lens[state->have++] = (unsigned short)len;
 695                 }
 696             }
 697
 698             /* handle error breaks in while */
 699             if (state->mode == BAD) break;
 700
 701             /* build code tables */
 702             state->next = state->codes;
 703             state->lencode = (code const FAR *)(state->next);
 704             state->lenbits = 9;
 705             ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
 706                                 &(state->lenbits), state->work);
 707             if (ret) {
 708                 strm->msg = (char *)"invalid literal/lengths set";
 709                 state->mode = BAD;
 710                 break;
 711             }
 712             state->distcode = (code const FAR *)(state->next);
 713             state->distbits = 6;
 714             ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
 715                             &(state->next), &(state->distbits), state->work);
 716             if (ret) {
 717                 strm->msg = (char *)"invalid distances set";
 718                 state->mode = BAD;
 719                 break;
 720             }
 721             Tracev((stderr, "inflate:       codes ok\n"));
 722             state->mode = LEN;
 723         case LEN:
 724             WATCHDOG_RESET();
 725             if (have >= 6 && left >= 258) {
 726                 RESTORE();
 727                 inflate_fast(strm, out);
 728                 LOAD();
 729                 break;
 730             }
 731             for (;;) {
 732                 this = state->lencode[BITS(state->lenbits)];
 733                 if ((unsigned)(this.bits) <= bits) break;
 734                 PULLBYTE();
 735             }
 736             if (this.op && (this.op & 0xf0) == 0) {
 737                 last = this;
 738                 for (;;) {
 739                     this = state->lencode[last.val +
 740                             (BITS(last.bits + last.op) >> last.bits)];
 741                     if ((unsigned)(last.bits + this.bits) <= bits) break;
 742                     PULLBYTE();
 743                 }
 744                 DROPBITS(last.bits);
 745             }
 746             DROPBITS(this.bits);
 747             state->length = (unsigned)this.val;
 748             if ((int)(this.op) == 0) {
 749                 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
 750                         "inflate:         literal '%c'\n" :
 751                         "inflate:         literal 0x%02x\n", this.val));
 752                 state->mode = LIT;
 753                 break;
 754             }
 755             if (this.op & 32) {
 756                 Tracevv((stderr, "inflate:         end of block\n"));
 757                 state->mode = TYPE;
 758                 break;
 759             }
 760             if (this.op & 64) {
 761                 strm->msg = (char *)"invalid literal/length code";
 762                 state->mode = BAD;
 763                 break;
 764             }
 765             state->extra = (unsigned)(this.op) & 15;
 766             state->mode = LENEXT;
 767         case LENEXT:
 768             if (state->extra) {
 769                 NEEDBITS(state->extra);
 770                 state->length += BITS(state->extra);
 771                 DROPBITS(state->extra);
 772             }
 773             Tracevv((stderr, "inflate:         length %u\n", state->length));
 774             state->mode = DIST;
 775         case DIST:
 776             for (;;) {
 777                 this = state->distcode[BITS(state->distbits)];
 778                 if ((unsigned)(this.bits) <= bits) break;
 779                 PULLBYTE();
 780             }
 781             if ((this.op & 0xf0) == 0) {
 782                 last = this;
 783                 for (;;) {
 784                     this = state->distcode[last.val +
 785                             (BITS(last.bits + last.op) >> last.bits)];
 786                     if ((unsigned)(last.bits + this.bits) <= bits) break;
 787                     PULLBYTE();
 788                 }
 789                 DROPBITS(last.bits);
 790             }
 791             DROPBITS(this.bits);
 792             if (this.op & 64) {
 793                 strm->msg = (char *)"invalid distance code";
 794                 state->mode = BAD;
 795                 break;
 796             }
 797             state->offset = (unsigned)this.val;
 798             state->extra = (unsigned)(this.op) & 15;
 799             state->mode = DISTEXT;
 800         case DISTEXT:
 801             if (state->extra) {
 802                 NEEDBITS(state->extra);
 803                 state->offset += BITS(state->extra);
 804                 DROPBITS(state->extra);
 805             }
 806 #ifdef INFLATE_STRICT
 807             if (state->offset > state->dmax) {
 808                 strm->msg = (char *)"invalid distance too far back";
 809                 state->mode = BAD;
 810                 break;
 811             }
 812 #endif
 813             if (state->offset > state->whave + out - left) {
 814                 strm->msg = (char *)"invalid distance too far back";
 815                 state->mode = BAD;
 816                 break;
 817             }
 818             Tracevv((stderr, "inflate:         distance %u\n", state->offset));
 819             state->mode = MATCH;
 820         case MATCH:
 821             if (left == 0) goto inf_leave;
 822             copy = out - left;
 823             if (state->offset > copy) {         /* copy from window */
 824                 copy = state->offset - copy;
 825                 if (copy > state->write) {
 826                     copy -= state->write;
 827                     from = state->window + (state->wsize - copy);
 828                 }
 829                 else
 830                     from = state->window + (state->write - copy);
 831                 if (copy > state->length) copy = state->length;
 832             }
 833             else {                              /* copy from output */
 834                 from = put - state->offset;
 835                 copy = state->length;
 836             }
 837             if (copy > left) copy = left;
 838             left -= copy;
 839             state->length -= copy;
 840             do {
 841                 *put++ = *from++;
 842             } while (--copy);
 843             if (state->length == 0) state->mode = LEN;
 844             break;
 845         case LIT:
 846             if (left == 0) goto inf_leave;
 847             *put++ = (unsigned char)(state->length);
 848             left--;
 849             state->mode = LEN;
 850             break;
 851         case CHECK:
 852             if (state->wrap) {
 853                 NEEDBITS(32);
 854                 out -= left;
 855                 strm->total_out += out;
 856                 state->total += out;
 857                 if (out)
 858                     strm->adler = state->check =
 859                         UPDATE(state->check, put - out, out);
 860                 out = left;
 861                 if ((
 862 #ifdef GUNZIP
 863                      state->flags ? hold :
 864 #endif
 865                      REVERSE(hold)) != state->check) {
 866                     strm->msg = (char *)"incorrect data check";
 867                     state->mode = BAD;
 868                     break;
 869                 }
 870                 INITBITS();
 871                 Tracev((stderr, "inflate:   check matches trailer\n"));
 872             }
 873 #ifdef GUNZIP
 874             state->mode = LENGTH;
 875         case LENGTH:
 876             if (state->wrap && state->flags) {
 877                 NEEDBITS(32);
 878                 if (hold != (state->total & 0xffffffffUL)) {
 879                     strm->msg = (char *)"incorrect length check";
 880                     state->mode = BAD;
 881                     break;
 882                 }
 883                 INITBITS();
 884                 Tracev((stderr, "inflate:   length matches trailer\n"));
 885             }
 886 #endif
 887             state->mode = DONE;
 888         case DONE:
 889             ret = Z_STREAM_END;
 890             goto inf_leave;
 891         case BAD:
 892             ret = Z_DATA_ERROR;
 893             goto inf_leave;
 894         case MEM:
 895             return Z_MEM_ERROR;
 896         case SYNC:
 897         default:
 898             return Z_STREAM_ERROR;
 899         }
 900
 901     /*
 902        Return from inflate(), updating the total counts and the check value.
 903        If there was no progress during the inflate() call, return a buffer
 904        error.  Call updatewindow() to create and/or update the window state.
 905        Note: a memory error from inflate() is non-recoverable.
 906      */
 907   inf_leave:
 908     RESTORE();
 909     if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
 910         if (updatewindow(strm, out)) {
 911             state->mode = MEM;
 912             return Z_MEM_ERROR;
 913         }
 914     in -= strm->avail_in;
 915     out -= strm->avail_out;
 916     strm->total_in += in;
 917     strm->total_out += out;
 918     state->total += out;
 919     if (state->wrap && out)
 920         strm->adler = state->check =
 921             UPDATE(state->check, strm->next_out - out, out);
 922     strm->data_type = state->bits + (state->last ? 64 : 0) +
 923                       (state->mode == TYPE ? 128 : 0);
 924     if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
 925         ret = Z_BUF_ERROR;
 926     return ret;
 927 }
 928
 929 int ZEXPORT inflateEnd(z_streamp strm)
 930 {
 931     struct inflate_state FAR *state;
 932     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
 933         return Z_STREAM_ERROR;
 934     state = (struct inflate_state FAR *)strm->state;
 935     if (state->window != Z_NULL) {
 936         WATCHDOG_RESET();
 937         ZFREE(strm, state->window);
 938     }
 939     ZFREE(strm, strm->state);
 940     strm->state = Z_NULL;
 941     Tracev((stderr, "inflate: end\n"));
 942     return Z_OK;
 943 }