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