zlib/infback.c

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