zlib/infback.c

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