zlib/infback.c

   1 /* infback.c -- inflate using a call-back interface
   2  * Copyright (C) 1995-2003 Mark Adler
   3  * For conditions of distribution and use, see copyright notice in zlib.h
   4  */
   5
   6 /*
   7    This code is largely copied from inflate.c.  Normally either infback.o or
   8    inflate.o would be linked into an application--not both.  The interface
   9    with inffast.c is retained so that optimized assembler-coded versions of
  10    inflate_fast() can be used with either inflate.c or infback.c.
  11  */
  12
  13 #include "zutil.h"
  14 #include "inftrees.h"
  15 #include "inflate.h"
  16 #include "inffast.h"
  17
  18 /* function prototypes */
  19 local void fixedtables OF((struct inflate_state FAR *state));
  20
  21 /*
  22    strm provides memory allocation functions in zalloc and zfree, or
  23    Z_NULL to use the library memory allocation functions.
  24
  25    windowBits is in the range 8..15, and window is a user-supplied
  26    window and output buffer that is 2**windowBits bytes.
  27  */
  28 int ZEXPORT inflateBackInit_(strm, windowBits, window, version, stream_size)
  29 z_stream FAR *strm;
  30 int windowBits;
  31 unsigned char FAR *window;
  32 const char *version;
  33 int stream_size;
  34 {
  35     struct inflate_state FAR *state;
  36
  37     if (version == Z_NULL || version[0] != ZLIB_VERSION[0] ||
  38         stream_size != (int)(sizeof(z_stream)))
  39         return Z_VERSION_ERROR;
  40     if (strm == Z_NULL || window == Z_NULL ||
  41         windowBits < 8 || windowBits > 15)
  42         return Z_STREAM_ERROR;
  43     strm->msg = Z_NULL;                 /* in case we return an error */
  44     if (strm->zalloc == (alloc_func)0) {
  45         strm->zalloc = zcalloc;
  46         strm->opaque = (voidpf)0;
  47     }
  48     if (strm->zfree == (free_func)0) strm->zfree = zcfree;
  49     state = (struct inflate_state FAR *)ZALLOC(strm, 1,
  50                                                sizeof(struct inflate_state));
  51     if (state == Z_NULL) return Z_MEM_ERROR;
  52     Tracev((stderr, "inflate: allocated\n"));
  53     strm->state = (voidpf)state;
  54     state->wbits = windowBits;
  55     state->wsize = 1U << windowBits;
  56     state->window = window;
  57     state->write = 0;
  58     state->whave = 0;
  59     return Z_OK;
  60 }
  61
  62 /*
  63    Return state with length and distance decoding tables and index sizes set to
  64    fixed code decoding.  Normally this returns fixed tables from inffixed.h.
  65    If BUILDFIXED is defined, then instead this routine builds the tables the
  66    first time it's called, and returns those tables the first time and
  67    thereafter.  This reduces the size of the code by about 2K bytes, in
  68    exchange for a little execution time.  However, BUILDFIXED should not be
  69    used for threaded applications, since the rewriting of the tables and virgin
  70    may not be thread-safe.
  71  */
  72 local void fixedtables(state)
  73 struct inflate_state FAR *state;
  74 {
  75 #ifdef BUILDFIXED
  76     static int virgin = 1;
  77     static code *lenfix, *distfix;
  78     static code fixed[544];
  79
  80     /* build fixed huffman tables if first call (may not be thread safe) */
  81     if (virgin) {
  82         unsigned sym, bits;
  83         static code *next;
  84
  85         /* literal/length table */
  86         sym = 0;
  87         while (sym < 144) state->lens[sym++] = 8;
  88         while (sym < 256) state->lens[sym++] = 9;
  89         while (sym < 280) state->lens[sym++] = 7;
  90         while (sym < 288) state->lens[sym++] = 8;
  91         next = fixed;
  92         lenfix = next;
  93         bits = 9;
  94         inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
  95
  96         /* distance table */
  97         sym = 0;
  98         while (sym < 32) state->lens[sym++] = 5;
  99         distfix = next;
 100         bits = 5;
 101         inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
 102
 103         /* do this just once */
 104         virgin = 0;
 105     }
 106 #else /* !BUILDFIXED */
 107 #   include "inffixed.h"
 108 #endif /* BUILDFIXED */
 109     state->lencode = lenfix;
 110     state->lenbits = 9;
 111     state->distcode = distfix;
 112     state->distbits = 5;
 113 }
 114
 115 /* Macros for inflateBack(): */
 116
 117 /* Load returned state from inflate_fast() */
 118 #define LOAD() \
 119     do { \
 120         put = strm->next_out; \
 121         left = strm->avail_out; \
 122         next = strm->next_in; \
 123         have = strm->avail_in; \
 124         hold = state->hold; \
 125         bits = state->bits; \
 126     } while (0)
 127
 128 /* Set state from registers for inflate_fast() */
 129 #define RESTORE() \
 130     do { \
 131         strm->next_out = put; \
 132         strm->avail_out = left; \
 133         strm->next_in = next; \
 134         strm->avail_in = have; \
 135         state->hold = hold; \
 136         state->bits = bits; \
 137     } while (0)
 138
 139 /* Clear the input bit accumulator */
 140 #define INITBITS() \
 141     do { \
 142         hold = 0; \
 143         bits = 0; \
 144     } while (0)
 145
 146 /* Assure that some input is available.  If input is requested, but denied,
 147    then return a Z_BUF_ERROR from inflateBack(). */
 148 #define PULL() \
 149     do { \
 150         if (have == 0) { \
 151             have = in(in_desc, &next); \
 152             if (have == 0) { \
 153                 next = Z_NULL; \
 154                 ret = Z_BUF_ERROR; \
 155                 goto inf_leave; \
 156             } \
 157         } \
 158     } while (0)
 159
 160 /* Get a byte of input into the bit accumulator, or return from inflateBack()
 161    with an error if there is no input available. */
 162 #define PULLBYTE() \
 163     do { \
 164         PULL(); \
 165         have--; \
 166         hold += (unsigned long)(*next++) << bits; \
 167         bits += 8; \
 168     } while (0)
 169
 170 /* Assure that there are at least n bits in the bit accumulator.  If there is
 171    not enough available input to do that, then return from inflateBack() with
 172    an error. */
 173 #define NEEDBITS(n) \
 174     do { \
 175         while (bits < (unsigned)(n)) \
 176             PULLBYTE(); \
 177     } while (0)
 178
 179 /* Return the low n bits of the bit accumulator (n < 16) */
 180 #define BITS(n) \
 181     ((unsigned)hold & ((1U << (n)) - 1))
 182
 183 /* Remove n bits from the bit accumulator */
 184 #define DROPBITS(n) \
 185     do { \
 186         hold >>= (n); \
 187         bits -= (unsigned)(n); \
 188     } while (0)
 189
 190 /* Remove zero to seven bits as needed to go to a byte boundary */
 191 #define BYTEBITS() \
 192     do { \
 193         hold >>= bits & 7; \
 194         bits -= bits & 7; \
 195     } while (0)
 196
 197 /* Assure that some output space is available, by writing out the window
 198    if it's full.  If the write fails, return from inflateBack() with a
 199    Z_BUF_ERROR. */
 200 #define ROOM() \
 201     do { \
 202         if (left == 0) { \
 203             put = state->window; \
 204             left = state->wsize; \
 205             state->whave = left; \
 206             if (out(out_desc, put, left)) { \
 207                 ret = Z_BUF_ERROR; \
 208                 goto inf_leave; \
 209             } \
 210         } \
 211     } while (0)
 212
 213 /*
 214    strm provides the memory allocation functions and window buffer on input,
 215    and provides information on the unused input on return.  For Z_DATA_ERROR
 216    returns, strm will also provide an error message.
 217
 218    in() and out() are the call-back input and output functions.  When
 219    inflateBack() needs more input, it calls in().  When inflateBack() has
 220    filled the window with output, or when it completes with data in the
 221    window, it calls out() to write out the data.  The application must not
 222    change the provided input until in() is called again or inflateBack()
 223    returns.  The application must not change the window/output buffer until
 224    inflateBack() returns.
 225
 226    in() and out() are called with a descriptor parameter provided in the
 227    inflateBack() call.  This parameter can be a structure that provides the
 228    information required to do the read or write, as well as accumulated
 229    information on the input and output such as totals and check values.
 230
 231    in() should return zero on failure.  out() should return non-zero on
 232    failure.  If either in() or out() fails, than inflateBack() returns a
 233    Z_BUF_ERROR.  strm->next_in can be checked for Z_NULL to see whether it
 234    was in() or out() that caused in the error.  Otherwise,  inflateBack()
 235    returns Z_STREAM_END on success, Z_DATA_ERROR for an deflate format
 236    error, or Z_MEM_ERROR if it could not allocate memory for the state.
 237    inflateBack() can also return Z_STREAM_ERROR if the input parameters
 238    are not correct, i.e. strm is Z_NULL or the state was not initialized.
 239  */
 240 int ZEXPORT inflateBack(strm, in, in_desc, out, out_desc)
 241 z_stream FAR *strm;
 242 in_func in;
 243 void FAR *in_desc;
 244 out_func out;
 245 void FAR *out_desc;
 246 {
 247     struct inflate_state FAR *state;
 248     unsigned char FAR *next;    /* next input */
 249     unsigned char FAR *put;     /* next output */
 250     unsigned have, left;        /* available input and output */
 251     unsigned long hold;         /* bit buffer */
 252     unsigned bits;              /* bits in bit buffer */
 253     unsigned copy;              /* number of stored or match bytes to copy */
 254     unsigned char FAR *from;    /* where to copy match bytes from */
 255     code this;                  /* current decoding table entry */
 256     code last;                  /* parent table entry */
 257     unsigned len;               /* length to copy for repeats, bits to drop */
 258     int ret;                    /* return code */
 259     static const unsigned short order[19] = /* permutation of code lengths */
 260         {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
 261
 262     /* Check that the strm exists and that the state was initialized */
 263     if (strm == Z_NULL || strm->state == Z_NULL)
 264         return Z_STREAM_ERROR;
 265     state = (struct inflate_state FAR *)strm->state;
 266
 267     /* Reset the state */
 268     strm->msg = Z_NULL;
 269     state->mode = TYPE;
 270     state->last = 0;
 271     state->whave = 0;
 272     next = strm->next_in;
 273     have = next != Z_NULL ? strm->avail_in : 0;
 274     hold = 0;
 275     bits = 0;
 276     put = state->window;
 277     left = state->wsize;
 278
 279     /* Inflate until end of block marked as last */
 280     for (;;)
 281         switch (state->mode) {
 282         case TYPE:
 283             /* determine and dispatch block type */
 284             if (state->last) {
 285                 BYTEBITS();
 286                 state->mode = DONE;
 287                 break;
 288             }
 289             NEEDBITS(3);
 290             state->last = BITS(1);
 291             DROPBITS(1);
 292             switch (BITS(2)) {
 293             case 0:                             /* stored block */
 294                 Tracev((stderr, "inflate:     stored block%s\n",
 295                         state->last ? " (last)" : ""));
 296                 state->mode = STORED;
 297                 break;
 298             case 1:                             /* fixed block */
 299                 fixedtables(state);
 300                 Tracev((stderr, "inflate:     fixed codes block%s\n",
 301                         state->last ? " (last)" : ""));
 302                 state->mode = LEN;              /* decode codes */
 303                 break;
 304             case 2:                             /* dynamic block */
 305                 Tracev((stderr, "inflate:     dynamic codes block%s\n",
 306                         state->last ? " (last)" : ""));
 307                 state->mode = TABLE;
 308                 break;
 309             case 3:
 310                 strm->msg = (char *)"invalid block type";
 311                 state->mode = BAD;
 312             }
 313             DROPBITS(2);
 314             break;
 315
 316         case STORED:
 317             /* get and verify stored block length */
 318             BYTEBITS();                         /* go to byte boundary */
 319             NEEDBITS(32);
 320             if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
 321                 strm->msg = (char *)"invalid stored block lengths";
 322                 state->mode = BAD;
 323                 break;
 324             }
 325             state->length = (unsigned)hold & 0xffff;
 326             Tracev((stderr, "inflate:       stored length %u\n",
 327                     state->length));
 328             INITBITS();
 329
 330             /* copy stored block from input to output */
 331             while (state->length != 0) {
 332                 copy = state->length;
 333                 PULL();
 334                 ROOM();
 335                 if (copy > have) copy = have;
 336                 if (copy > left) copy = left;
 337                 zmemcpy(put, next, copy);
 338                 have -= copy;
 339                 next += copy;
 340                 left -= copy;
 341                 put += copy;
 342                 state->length -= copy;
 343             }
 344             Tracev((stderr, "inflate:       stored end\n"));
 345             state->mode = TYPE;
 346             break;
 347
 348         case TABLE:
 349             /* get dynamic table entries descriptor */
 350             NEEDBITS(14);
 351             state->nlen = BITS(5) + 257;
 352             DROPBITS(5);
 353             state->ndist = BITS(5) + 1;
 354             DROPBITS(5);
 355             state->ncode = BITS(4) + 4;
 356             DROPBITS(4);
 357 #ifndef PKZIP_BUG_WORKAROUND
 358             if (state->nlen > 286 || state->ndist > 30) {
 359                 strm->msg = (char *)"too many length or distance symbols";
 360                 state->mode = BAD;
 361                 break;
 362             }
 363 #endif
 364             Tracev((stderr, "inflate:       table sizes ok\n"));
 365
 366             /* get code length code lengths (not a typo) */
 367             state->have = 0;
 368             while (state->have < state->ncode) {
 369                 NEEDBITS(3);
 370                 state->lens[order[state->have++]] = (unsigned short)BITS(3);
 371                 DROPBITS(3);
 372             }
 373             while (state->have < 19)
 374                 state->lens[order[state->have++]] = 0;
 375             state->next = state->codes;
 376             state->lencode = (code const FAR *)(state->next);
 377             state->lenbits = 7;
 378             ret = inflate_table(CODES, state->lens, 19, &(state->next),
 379                                 &(state->lenbits), state->work);
 380             if (ret) {
 381                 strm->msg = (char *)"invalid code lengths set";
 382                 state->mode = BAD;
 383                 break;
 384             }
 385             Tracev((stderr, "inflate:       code lengths ok\n"));
 386
 387             /* get length and distance code code lengths */
 388             state->have = 0;
 389             while (state->have < state->nlen + state->ndist) {
 390                 for (;;) {
 391                     this = state->lencode[BITS(state->lenbits)];
 392                     if ((unsigned)(this.bits) <= bits) break;
 393                     PULLBYTE();
 394                 }
 395                 if (this.val < 16) {
 396                     NEEDBITS(this.bits);
 397                     DROPBITS(this.bits);
 398                     state->lens[state->have++] = this.val;
 399                 }
 400                 else {
 401                     if (this.val == 16) {
 402                         NEEDBITS(this.bits + 2);
 403                         DROPBITS(this.bits);
 404                         if (state->have == 0) {
 405                             strm->msg = (char *)"invalid bit length repeat";
 406                             state->mode = BAD;
 407                             break;
 408                         }
 409                         len = (unsigned)(state->lens[state->have - 1]);
 410                         copy = 3 + BITS(2);
 411                         DROPBITS(2);
 412                     }
 413                     else if (this.val == 17) {
 414                         NEEDBITS(this.bits + 3);
 415                         DROPBITS(this.bits);
 416                         len = 0;
 417                         copy = 3 + BITS(3);
 418                         DROPBITS(3);
 419                     }
 420                     else {
 421                         NEEDBITS(this.bits + 7);
 422                         DROPBITS(this.bits);
 423                         len = 0;
 424                         copy = 11 + BITS(7);
 425                         DROPBITS(7);
 426                     }
 427                     if (state->have + copy > state->nlen + state->ndist) {
 428                         strm->msg = (char *)"invalid bit length repeat";
 429                         state->mode = BAD;
 430                         break;
 431                     }
 432                     while (copy--)
 433                         state->lens[state->have++] = (unsigned short)len;
 434                 }
 435             }
 436
 437             /* build code tables */
 438             state->next = state->codes;
 439             state->lencode = (code const FAR *)(state->next);
 440             state->lenbits = 9;
 441             ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
 442                                 &(state->lenbits), state->work);
 443             if (ret) {
 444                 strm->msg = (char *)"invalid literal/lengths set";
 445                 state->mode = BAD;
 446                 break;
 447             }
 448             state->distcode = (code const FAR *)(state->next);
 449             state->distbits = 6;
 450             ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
 451                             &(state->next), &(state->distbits), state->work);
 452             if (ret) {
 453                 strm->msg = (char *)"invalid distances set";
 454                 state->mode = BAD;
 455                 break;
 456             }
 457             Tracev((stderr, "inflate:       codes ok\n"));
 458             state->mode = LEN;
 459
 460         case LEN:
 461             /* use inflate_fast() if we have enough input and output */
 462             if (have >= 6 && left >= 258) {
 463                 RESTORE();
 464                 if (state->whave < state->wsize)
 465                     state->whave = state->wsize - left;
 466                 inflate_fast(strm, state->wsize);
 467                 LOAD();
 468                 break;
 469             }
 470
 471             /* get a literal, length, or end-of-block code */
 472             for (;;) {
 473                 this = state->lencode[BITS(state->lenbits)];
 474                 if ((unsigned)(this.bits) <= bits) break;
 475                 PULLBYTE();
 476             }
 477             if (this.op && (this.op & 0xf0) == 0) {
 478                 last = this;
 479                 for (;;) {
 480                     this = state->lencode[last.val +
 481                             (BITS(last.bits + last.op) >> last.bits)];
 482                     if ((unsigned)(last.bits + this.bits) <= bits) break;
 483                     PULLBYTE();
 484                 }
 485                 DROPBITS(last.bits);
 486             }
 487             DROPBITS(this.bits);
 488             state->length = (unsigned)this.val;
 489
 490             /* process literal */
 491             if (this.op == 0) {
 492                 Tracevv((stderr, this.val >= 0x20 && this.val < 0x7f ?
 493                         "inflate:         literal '%c'\n" :
 494                         "inflate:         literal 0x%02x\n", this.val));
 495                 ROOM();
 496                 *put++ = (unsigned char)(state->length);
 497                 left--;
 498                 state->mode = LEN;
 499                 break;
 500             }
 501
 502             /* process end of block */
 503             if (this.op & 32) {
 504                 Tracevv((stderr, "inflate:         end of block\n"));
 505                 state->mode = TYPE;
 506                 break;
 507             }
 508
 509             /* invalid code */
 510             if (this.op & 64) {
 511                 strm->msg = (char *)"invalid literal/length code";
 512                 state->mode = BAD;
 513                 break;
 514             }
 515
 516             /* length code -- get extra bits, if any */
 517             state->extra = (unsigned)(this.op) & 15;
 518             if (state->extra != 0) {
 519                 NEEDBITS(state->extra);
 520                 state->length += BITS(state->extra);
 521                 DROPBITS(state->extra);
 522             }
 523             Tracevv((stderr, "inflate:         length %u\n", state->length));
 524
 525             /* get distance code */
 526             for (;;) {
 527                 this = state->distcode[BITS(state->distbits)];
 528                 if ((unsigned)(this.bits) <= bits) break;
 529                 PULLBYTE();
 530             }
 531             if ((this.op & 0xf0) == 0) {
 532                 last = this;
 533                 for (;;) {
 534                     this = state->distcode[last.val +
 535                             (BITS(last.bits + last.op) >> last.bits)];
 536                     if ((unsigned)(last.bits + this.bits) <= bits) break;
 537                     PULLBYTE();
 538                 }
 539                 DROPBITS(last.bits);
 540             }
 541             DROPBITS(this.bits);
 542             if (this.op & 64) {
 543                 strm->msg = (char *)"invalid distance code";
 544                 state->mode = BAD;
 545                 break;
 546             }
 547             state->offset = (unsigned)this.val;
 548
 549             /* get distance extra bits, if any */
 550             state->extra = (unsigned)(this.op) & 15;
 551             if (state->extra != 0) {
 552                 NEEDBITS(state->extra);
 553                 state->offset += BITS(state->extra);
 554                 DROPBITS(state->extra);
 555             }
 556             if (state->offset > state->wsize - (state->whave < state->wsize ?
 557                                                 left : 0)) {
 558                 strm->msg = (char *)"invalid distance too far back";
 559                 state->mode = BAD;
 560                 break;
 561             }
 562             Tracevv((stderr, "inflate:         distance %u\n", state->offset));
 563
 564             /* copy match from window to output */
 565             do {
 566                 ROOM();
 567                 copy = state->wsize - state->offset;
 568                 if (copy < left) {
 569                     from = put + copy;
 570                     copy = left - copy;
 571                 }
 572                 else {
 573                     from = put - state->offset;
 574                     copy = left;
 575                 }
 576                 if (copy > state->length) copy = state->length;
 577                 state->length -= copy;
 578                 left -= copy;
 579                 do {
 580                     *put++ = *from++;
 581                 } while (--copy);
 582             } while (state->length != 0);
 583             break;
 584
 585         case DONE:
 586             /* inflate stream terminated properly -- write leftover output */
 587             ret = Z_STREAM_END;
 588             if (left < state->wsize) {
 589                 if (out(out_desc, state->window, state->wsize - left))
 590                     ret = Z_BUF_ERROR;
 591             }
 592             goto inf_leave;
 593
 594         case BAD:
 595             ret = Z_DATA_ERROR;
 596             goto inf_leave;
 597
 598         default:                /* can't happen, but makes compilers happy */
 599             ret = Z_STREAM_ERROR;
 600             goto inf_leave;
 601         }
 602
 603     /* Return unused input */
 604   inf_leave:
 605     strm->next_in = next;
 606     strm->avail_in = have;
 607     return ret;
 608 }
 609
 610 int ZEXPORT inflateBackEnd(strm)
 611 z_stream FAR *strm;
 612 {
 613     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
 614         return Z_STREAM_ERROR;
 615     ZFREE(strm, strm->state);
 616     strm->state = Z_NULL;
 617     Tracev((stderr, "inflate: end\n"));
 618     return Z_OK;
 619 }