deps/infback.c

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