zlib/contrib/infback9/infback9.c

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