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