err.no 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     const 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     /* Do not check for strm->next_out == NULL here as ppc zImage
 351        inflates to strm->next_out = 0 */
 352
 353     if (strm == NULL || strm->state == NULL ||
 354         (strm->next_in == NULL && strm->avail_in != 0))
 355         return Z_STREAM_ERROR;
 356
 357     state = (struct inflate_state *)strm->state;
 358
 359     if (state->mode == TYPE) state->mode = TYPEDO;      /* skip check */
 360     LOAD();
 361     in = have;
 362     out = left;
 363     ret = Z_OK;
 364     for (;;)
 365         switch (state->mode) {
 366         case HEAD:
 367             if (state->wrap == 0) {
 368                 state->mode = TYPEDO;
 369                 break;
 370             }
 371             NEEDBITS(16);
 372             if (
 373                 ((BITS(8) << 8) + (hold >> 8)) % 31) {
 374                 strm->msg = (char *)"incorrect header check";
 375                 state->mode = BAD;
 376                 break;
 377             }
 378             if (BITS(4) != Z_DEFLATED) {
 379                 strm->msg = (char *)"unknown compression method";
 380                 state->mode = BAD;
 381                 break;
 382             }
 383             DROPBITS(4);
 384             len = BITS(4) + 8;
 385             if (len > state->wbits) {
 386                 strm->msg = (char *)"invalid window size";
 387                 state->mode = BAD;
 388                 break;
 389             }
 390             state->dmax = 1U << len;
 391             strm->adler = state->check = zlib_adler32(0L, NULL, 0);
 392             state->mode = hold & 0x200 ? DICTID : TYPE;
 393             INITBITS();
 394             break;
 395         case DICTID:
 396             NEEDBITS(32);
 397             strm->adler = state->check = REVERSE(hold);
 398             INITBITS();
 399             state->mode = DICT;
 400         case DICT:
 401             if (state->havedict == 0) {
 402                 RESTORE();
 403                 return Z_NEED_DICT;
 404             }
 405             strm->adler = state->check = zlib_adler32(0L, NULL, 0);
 406             state->mode = TYPE;
 407         case TYPE:
 408             if (flush == Z_BLOCK) goto inf_leave;
 409         case TYPEDO:
 410             if (state->last) {
 411                 BYTEBITS();
 412                 state->mode = CHECK;
 413                 break;
 414             }
 415             NEEDBITS(3);
 416             state->last = BITS(1);
 417             DROPBITS(1);
 418             switch (BITS(2)) {
 419             case 0:                             /* stored block */
 420                 state->mode = STORED;
 421                 break;
 422             case 1:                             /* fixed block */
 423                 zlib_fixedtables(state);
 424                 state->mode = LEN;              /* decode codes */
 425                 break;
 426             case 2:                             /* dynamic block */
 427                 state->mode = TABLE;
 428                 break;
 429             case 3:
 430                 strm->msg = (char *)"invalid block type";
 431                 state->mode = BAD;
 432             }
 433             DROPBITS(2);
 434             break;
 435         case STORED:
 436             BYTEBITS();                         /* go to byte boundary */
 437             NEEDBITS(32);
 438             if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
 439                 strm->msg = (char *)"invalid stored block lengths";
 440                 state->mode = BAD;
 441                 break;
 442             }
 443             state->length = (unsigned)hold & 0xffff;
 444             INITBITS();
 445             state->mode = COPY;
 446         case COPY:
 447             copy = state->length;
 448             if (copy) {
 449                 if (copy > have) copy = have;
 450                 if (copy > left) copy = left;
 451                 if (copy == 0) goto inf_leave;
 452                 memcpy(put, next, copy);
 453                 have -= copy;
 454                 next += copy;
 455                 left -= copy;
 456                 put += copy;
 457                 state->length -= copy;
 458                 break;
 459             }
 460             state->mode = TYPE;
 461             break;
 462         case TABLE:
 463             NEEDBITS(14);
 464             state->nlen = BITS(5) + 257;
 465             DROPBITS(5);
 466             state->ndist = BITS(5) + 1;
 467             DROPBITS(5);
 468             state->ncode = BITS(4) + 4;
 469             DROPBITS(4);
 470 #ifndef PKZIP_BUG_WORKAROUND
 471             if (state->nlen > 286 || state->ndist > 30) {
 472                 strm->msg = (char *)"too many length or distance symbols";
 473                 state->mode = BAD;
 474                 break;
 475             }
 476 #endif
 477             state->have = 0;
 478             state->mode = LENLENS;
 479         case LENLENS:
 480             while (state->have < state->ncode) {
 481                 NEEDBITS(3);
 482                 state->lens[order[state->have++]] = (unsigned short)BITS(3);
 483                 DROPBITS(3);
 484             }
 485             while (state->have < 19)
 486                 state->lens[order[state->have++]] = 0;
 487             state->next = state->codes;
 488             state->lencode = (code const *)(state->next);
 489             state->lenbits = 7;
 490             ret = zlib_inflate_table(CODES, state->lens, 19, &(state->next),
 491                                 &(state->lenbits), state->work);
 492             if (ret) {
 493                 strm->msg = (char *)"invalid code lengths set";
 494                 state->mode = BAD;
 495                 break;
 496             }
 497             state->have = 0;
 498             state->mode = CODELENS;
 499         case CODELENS:
 500             while (state->have < state->nlen + state->ndist) {
 501                 for (;;) {
 502                     this = state->lencode[BITS(state->lenbits)];
 503                     if ((unsigned)(this.bits) <= bits) break;
 504                     PULLBYTE();
 505                 }
 506                 if (this.val < 16) {
 507                     NEEDBITS(this.bits);
 508                     DROPBITS(this.bits);
 509                     state->lens[state->have++] = this.val;
 510                 }
 511                 else {
 512                     if (this.val == 16) {
 513                         NEEDBITS(this.bits + 2);
 514                         DROPBITS(this.bits);
 515                         if (state->have == 0) {
 516                             strm->msg = (char *)"invalid bit length repeat";
 517                             state->mode = BAD;
 518                             break;
 519                         }
 520                         len = state->lens[state->have - 1];
 521                         copy = 3 + BITS(2);
 522                         DROPBITS(2);
 523                     }
 524                     else if (this.val == 17) {
 525                         NEEDBITS(this.bits + 3);
 526                         DROPBITS(this.bits);
 527                         len = 0;
 528                         copy = 3 + BITS(3);
 529                         DROPBITS(3);
 530                     }
 531                     else {
 532                         NEEDBITS(this.bits + 7);
 533                         DROPBITS(this.bits);
 534                         len = 0;
 535                         copy = 11 + BITS(7);
 536                         DROPBITS(7);
 537                     }
 538                     if (state->have + copy > state->nlen + state->ndist) {
 539                         strm->msg = (char *)"invalid bit length repeat";
 540                         state->mode = BAD;
 541                         break;
 542                     }
 543                     while (copy--)
 544                         state->lens[state->have++] = (unsigned short)len;
 545                 }
 546             }
 547
 548             /* handle error breaks in while */
 549             if (state->mode == BAD) break;
 550
 551             /* build code tables */
 552             state->next = state->codes;
 553             state->lencode = (code const *)(state->next);
 554             state->lenbits = 9;
 555             ret = zlib_inflate_table(LENS, state->lens, state->nlen, &(state->next),
 556                                 &(state->lenbits), state->work);
 557             if (ret) {
 558                 strm->msg = (char *)"invalid literal/lengths set";
 559                 state->mode = BAD;
 560                 break;
 561             }
 562             state->distcode = (code const *)(state->next);
 563             state->distbits = 6;
 564             ret = zlib_inflate_table(DISTS, state->lens + state->nlen, state->ndist,
 565                             &(state->next), &(state->distbits), state->work);
 566             if (ret) {
 567                 strm->msg = (char *)"invalid distances set";
 568                 state->mode = BAD;
 569                 break;
 570             }
 571             state->mode = LEN;
 572         case LEN:
 573             if (have >= 6 && left >= 258) {
 574                 RESTORE();
 575                 inflate_fast(strm, out);
 576                 LOAD();
 577                 break;
 578             }
 579             for (;;) {
 580                 this = state->lencode[BITS(state->lenbits)];
 581                 if ((unsigned)(this.bits) <= bits) break;
 582                 PULLBYTE();
 583             }
 584             if (this.op && (this.op & 0xf0) == 0) {
 585                 last = this;
 586                 for (;;) {
 587                     this = state->lencode[last.val +
 588                             (BITS(last.bits + last.op) >> last.bits)];
 589                     if ((unsigned)(last.bits + this.bits) <= bits) break;
 590                     PULLBYTE();
 591                 }
 592                 DROPBITS(last.bits);
 593             }
 594             DROPBITS(this.bits);
 595             state->length = (unsigned)this.val;
 596             if ((int)(this.op) == 0) {
 597                 state->mode = LIT;
 598                 break;
 599             }
 600             if (this.op & 32) {
 601                 state->mode = TYPE;
 602                 break;
 603             }
 604             if (this.op & 64) {
 605                 strm->msg = (char *)"invalid literal/length code";
 606                 state->mode = BAD;
 607                 break;
 608             }
 609             state->extra = (unsigned)(this.op) & 15;
 610             state->mode = LENEXT;
 611         case LENEXT:
 612             if (state->extra) {
 613                 NEEDBITS(state->extra);
 614                 state->length += BITS(state->extra);
 615                 DROPBITS(state->extra);
 616             }
 617             state->mode = DIST;
 618         case DIST:
 619             for (;;) {
 620                 this = state->distcode[BITS(state->distbits)];
 621                 if ((unsigned)(this.bits) <= bits) break;
 622                 PULLBYTE();
 623             }
 624             if ((this.op & 0xf0) == 0) {
 625                 last = this;
 626                 for (;;) {
 627                     this = state->distcode[last.val +
 628                             (BITS(last.bits + last.op) >> last.bits)];
 629                     if ((unsigned)(last.bits + this.bits) <= bits) break;
 630                     PULLBYTE();
 631                 }
 632                 DROPBITS(last.bits);
 633             }
 634             DROPBITS(this.bits);
 635             if (this.op & 64) {
 636                 strm->msg = (char *)"invalid distance code";
 637                 state->mode = BAD;
 638                 break;
 639             }
 640             state->offset = (unsigned)this.val;
 641             state->extra = (unsigned)(this.op) & 15;
 642             state->mode = DISTEXT;
 643         case DISTEXT:
 644             if (state->extra) {
 645                 NEEDBITS(state->extra);
 646                 state->offset += BITS(state->extra);
 647                 DROPBITS(state->extra);
 648             }
 649 #ifdef INFLATE_STRICT
 650             if (state->offset > state->dmax) {
 651                 strm->msg = (char *)"invalid distance too far back";
 652                 state->mode = BAD;
 653                 break;
 654             }
 655 #endif
 656             if (state->offset > state->whave + out - left) {
 657                 strm->msg = (char *)"invalid distance too far back";
 658                 state->mode = BAD;
 659                 break;
 660             }
 661             state->mode = MATCH;
 662         case MATCH:
 663             if (left == 0) goto inf_leave;
 664             copy = out - left;
 665             if (state->offset > copy) {         /* copy from window */
 666                 copy = state->offset - copy;
 667                 if (copy > state->write) {
 668                     copy -= state->write;
 669                     from = state->window + (state->wsize - copy);
 670                 }
 671                 else
 672                     from = state->window + (state->write - copy);
 673                 if (copy > state->length) copy = state->length;
 674             }
 675             else {                              /* copy from output */
 676                 from = put - state->offset;
 677                 copy = state->length;
 678             }
 679             if (copy > left) copy = left;
 680             left -= copy;
 681             state->length -= copy;
 682             do {
 683                 *put++ = *from++;
 684             } while (--copy);
 685             if (state->length == 0) state->mode = LEN;
 686             break;
 687         case LIT:
 688             if (left == 0) goto inf_leave;
 689             *put++ = (unsigned char)(state->length);
 690             left--;
 691             state->mode = LEN;
 692             break;
 693         case CHECK:
 694             if (state->wrap) {
 695                 NEEDBITS(32);
 696                 out -= left;
 697                 strm->total_out += out;
 698                 state->total += out;
 699                 if (out)
 700                     strm->adler = state->check =
 701                         UPDATE(state->check, put - out, out);
 702                 out = left;
 703                 if ((
 704                      REVERSE(hold)) != state->check) {
 705                     strm->msg = (char *)"incorrect data check";
 706                     state->mode = BAD;
 707                     break;
 708                 }
 709                 INITBITS();
 710             }
 711             state->mode = DONE;
 712         case DONE:
 713             ret = Z_STREAM_END;
 714             goto inf_leave;
 715         case BAD:
 716             ret = Z_DATA_ERROR;
 717             goto inf_leave;
 718         case MEM:
 719             return Z_MEM_ERROR;
 720         case SYNC:
 721         default:
 722             return Z_STREAM_ERROR;
 723         }
 724
 725     /*
 726        Return from inflate(), updating the total counts and the check value.
 727        If there was no progress during the inflate() call, return a buffer
 728        error.  Call zlib_updatewindow() to create and/or update the window state.
 729      */
 730   inf_leave:
 731     RESTORE();
 732     if (state->wsize || (state->mode < CHECK && out != strm->avail_out))
 733         zlib_updatewindow(strm, out);
 734
 735     in -= strm->avail_in;
 736     out -= strm->avail_out;
 737     strm->total_in += in;
 738     strm->total_out += out;
 739     state->total += out;
 740     if (state->wrap && out)
 741         strm->adler = state->check =
 742             UPDATE(state->check, strm->next_out - out, out);
 743
 744     strm->data_type = state->bits + (state->last ? 64 : 0) +
 745                       (state->mode == TYPE ? 128 : 0);
 746
 747     if (flush == Z_PACKET_FLUSH && ret == Z_OK &&
 748             strm->avail_out != 0 && strm->avail_in == 0)
 749                 return zlib_inflateSyncPacket(strm);
 750
 751     if (((in == 0 && out == 0) || flush == Z_FINISH) && ret == Z_OK)
 752         ret = Z_BUF_ERROR;
 753
 754     return ret;
 755 }
 756
 757 int zlib_inflateEnd(z_streamp strm)
 758 {
 759     if (strm == NULL || strm->state == NULL)
 760         return Z_STREAM_ERROR;
 761     return Z_OK;
 762 }
 763
 764 #if 0
 765 int zlib_inflateSetDictionary(z_streamp strm, const Byte *dictionary,
 766         uInt dictLength)
 767 {
 768     struct inflate_state *state;
 769     unsigned long id;
 770
 771     /* check state */
 772     if (strm == NULL || strm->state == NULL) return Z_STREAM_ERROR;
 773     state = (struct inflate_state *)strm->state;
 774     if (state->wrap != 0 && state->mode != DICT)
 775         return Z_STREAM_ERROR;
 776
 777     /* check for correct dictionary id */
 778     if (state->mode == DICT) {
 779         id = zlib_adler32(0L, NULL, 0);
 780         id = zlib_adler32(id, dictionary, dictLength);
 781         if (id != state->check)
 782             return Z_DATA_ERROR;
 783     }
 784
 785     /* copy dictionary to window */
 786     zlib_updatewindow(strm, strm->avail_out);
 787
 788     if (dictLength > state->wsize) {
 789         memcpy(state->window, dictionary + dictLength - state->wsize,
 790                 state->wsize);
 791         state->whave = state->wsize;
 792     }
 793     else {
 794         memcpy(state->window + state->wsize - dictLength, dictionary,
 795                 dictLength);
 796         state->whave = dictLength;
 797     }
 798     state->havedict = 1;
 799     return Z_OK;
 800 }
 801 #endif
 802
 803 #if 0
 804 /*
 805    Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff.  Return when found
 806    or when out of input.  When called, *have is the number of pattern bytes
 807    found in order so far, in 0..3.  On return *have is updated to the new
 808    state.  If on return *have equals four, then the pattern was found and the
 809    return value is how many bytes were read including the last byte of the
 810    pattern.  If *have is less than four, then the pattern has not been found
 811    yet and the return value is len.  In the latter case, zlib_syncsearch() can be
 812    called again with more data and the *have state.  *have is initialized to
 813    zero for the first call.
 814  */
 815 static unsigned zlib_syncsearch(unsigned *have, unsigned char *buf,
 816         unsigned len)
 817 {
 818     unsigned got;
 819     unsigned next;
 820
 821     got = *have;
 822     next = 0;
 823     while (next < len && got < 4) {
 824         if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
 825             got++;
 826         else if (buf[next])
 827             got = 0;
 828         else
 829             got = 4 - got;
 830         next++;
 831     }
 832     *have = got;
 833     return next;
 834 }
 835 #endif
 836
 837 #if 0
 838 int zlib_inflateSync(z_streamp strm)
 839 {
 840     unsigned len;               /* number of bytes to look at or looked at */
 841     unsigned long in, out;      /* temporary to save total_in and total_out */
 842     unsigned char buf[4];       /* to restore bit buffer to byte string */
 843     struct inflate_state *state;
 844
 845     /* check parameters */
 846     if (strm == NULL || strm->state == NULL) return Z_STREAM_ERROR;
 847     state = (struct inflate_state *)strm->state;
 848     if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
 849
 850     /* if first time, start search in bit buffer */
 851     if (state->mode != SYNC) {
 852         state->mode = SYNC;
 853         state->hold <<= state->bits & 7;
 854         state->bits -= state->bits & 7;
 855         len = 0;
 856         while (state->bits >= 8) {
 857             buf[len++] = (unsigned char)(state->hold);
 858             state->hold >>= 8;
 859             state->bits -= 8;
 860         }
 861         state->have = 0;
 862         zlib_syncsearch(&(state->have), buf, len);
 863     }
 864
 865     /* search available input */
 866     len = zlib_syncsearch(&(state->have), strm->next_in, strm->avail_in);
 867     strm->avail_in -= len;
 868     strm->next_in += len;
 869     strm->total_in += len;
 870
 871     /* return no joy or set up to restart inflate() on a new block */
 872     if (state->have != 4) return Z_DATA_ERROR;
 873     in = strm->total_in;  out = strm->total_out;
 874     zlib_inflateReset(strm);
 875     strm->total_in = in;  strm->total_out = out;
 876     state->mode = TYPE;
 877     return Z_OK;
 878 }
 879 #endif
 880
 881 /*
 882  * This subroutine adds the data at next_in/avail_in to the output history
 883  * without performing any output.  The output buffer must be "caught up";
 884  * i.e. no pending output but this should always be the case. The state must
 885  * be waiting on the start of a block (i.e. mode == TYPE or HEAD).  On exit,
 886  * the output will also be caught up, and the checksum will have been updated
 887  * if need be.
 888  */
 889 int zlib_inflateIncomp(z_stream *z)
 890 {
 891     struct inflate_state *state = (struct inflate_state *)z->state;
 892     Byte *saved_no = z->next_out;
 893     uInt saved_ao = z->avail_out;
 894
 895     if (state->mode != TYPE && state->mode != HEAD)
 896         return Z_DATA_ERROR;
 897
 898     /* Setup some variables to allow misuse of updateWindow */
 899     z->avail_out = 0;
 900     z->next_out = (unsigned char*)z->next_in + z->avail_in;
 901
 902     zlib_updatewindow(z, z->avail_in);
 903
 904     /* Restore saved variables */
 905     z->avail_out = saved_ao;
 906     z->next_out = saved_no;
 907
 908     z->adler = state->check =
 909         UPDATE(state->check, z->next_in, z->avail_in);
 910
 911     z->total_out += z->avail_in;
 912     z->total_in += z->avail_in;
 913     z->next_in += z->avail_in;
 914     state->total += z->avail_in;
 915     z->avail_in = 0;
 916
 917     return Z_OK;
 918 }