common/dist/zlib/infback.c

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