zlib/contrib/infback9/infback9.c

   1 /* infback9.c -- inflate deflate64 data using a call-back interface
   2  * Copyright (C) 1995-2008 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 here;                  /* 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                     here = lencode[BITS(lenbits)];
 388                     if ((unsigned)(here.bits) <= bits) break;
 389                     PULLBYTE();
 390                 }
 391                 if (here.val < 16) {
 392                     NEEDBITS(here.bits);
 393                     DROPBITS(here.bits);
 394                     state->lens[state->have++] = here.val;
 395                 }
 396                 else {
 397                     if (here.val == 16) {
 398                         NEEDBITS(here.bits + 2);
 399                         DROPBITS(here.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 (here.val == 17) {
 410                         NEEDBITS(here.bits + 3);
 411                         DROPBITS(here.bits);
 412                         len = 0;
 413                         copy = 3 + BITS(3);
 414                         DROPBITS(3);
 415                     }
 416                     else {
 417                         NEEDBITS(here.bits + 7);
 418                         DROPBITS(here.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             /* check for end-of-block code (better have one) */
 437             if (state->lens[256] == 0) {
 438                 strm->msg = (char *)"invalid code -- missing end-of-block";
 439                 mode = BAD;
 440                 break;
 441             }
 442
 443             /* build code tables -- note: do not change the lenbits or distbits
 444                values here (9 and 6) without reading the comments in inftree9.h
 445                concerning the ENOUGH constants, which depend on those values */
 446             state->next = state->codes;
 447             lencode = (code const FAR *)(state->next);
 448             lenbits = 9;
 449             ret = inflate_table9(LENS, state->lens, state->nlen,
 450                             &(state->next), &(lenbits), state->work);
 451             if (ret) {
 452                 strm->msg = (char *)"invalid literal/lengths set";
 453                 mode = BAD;
 454                 break;
 455             }
 456             distcode = (code const FAR *)(state->next);
 457             distbits = 6;
 458             ret = inflate_table9(DISTS, state->lens + state->nlen,
 459                             state->ndist, &(state->next), &(distbits),
 460                             state->work);
 461             if (ret) {
 462                 strm->msg = (char *)"invalid distances set";
 463                 mode = BAD;
 464                 break;
 465             }
 466             Tracev((stderr, "inflate:       codes ok\n"));
 467             mode = LEN;
 468
 469         case LEN:
 470             /* get a literal, length, or end-of-block code */
 471             for (;;) {
 472                 here = lencode[BITS(lenbits)];
 473                 if ((unsigned)(here.bits) <= bits) break;
 474                 PULLBYTE();
 475             }
 476             if (here.op && (here.op & 0xf0) == 0) {
 477                 last = here;
 478                 for (;;) {
 479                     here = lencode[last.val +
 480                             (BITS(last.bits + last.op) >> last.bits)];
 481                     if ((unsigned)(last.bits + here.bits) <= bits) break;
 482                     PULLBYTE();
 483                 }
 484                 DROPBITS(last.bits);
 485             }
 486             DROPBITS(here.bits);
 487             length = (unsigned)here.val;
 488
 489             /* process literal */
 490             if (here.op == 0) {
 491                 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
 492                         "inflate:         literal '%c'\n" :
 493                         "inflate:         literal 0x%02x\n", here.val));
 494                 ROOM();
 495                 *put++ = (unsigned char)(length);
 496                 left--;
 497                 mode = LEN;
 498                 break;
 499             }
 500
 501             /* process end of block */
 502             if (here.op & 32) {
 503                 Tracevv((stderr, "inflate:         end of block\n"));
 504                 mode = TYPE;
 505                 break;
 506             }
 507
 508             /* invalid code */
 509             if (here.op & 64) {
 510                 strm->msg = (char *)"invalid literal/length code";
 511                 mode = BAD;
 512                 break;
 513             }
 514
 515             /* length code -- get extra bits, if any */
 516             extra = (unsigned)(here.op) & 31;
 517             if (extra != 0) {
 518                 NEEDBITS(extra);
 519                 length += BITS(extra);
 520                 DROPBITS(extra);
 521             }
 522             Tracevv((stderr, "inflate:         length %lu\n", length));
 523
 524             /* get distance code */
 525             for (;;) {
 526                 here = distcode[BITS(distbits)];
 527                 if ((unsigned)(here.bits) <= bits) break;
 528                 PULLBYTE();
 529             }
 530             if ((here.op & 0xf0) == 0) {
 531                 last = here;
 532                 for (;;) {
 533                     here = distcode[last.val +
 534                             (BITS(last.bits + last.op) >> last.bits)];
 535                     if ((unsigned)(last.bits + here.bits) <= bits) break;
 536                     PULLBYTE();
 537                 }
 538                 DROPBITS(last.bits);
 539             }
 540             DROPBITS(here.bits);
 541             if (here.op & 64) {
 542                 strm->msg = (char *)"invalid distance code";
 543                 mode = BAD;
 544                 break;
 545             }
 546             offset = (unsigned)here.val;
 547
 548             /* get distance extra bits, if any */
 549             extra = (unsigned)(here.op) & 15;
 550             if (extra != 0) {
 551                 NEEDBITS(extra);
 552                 offset += BITS(extra);
 553                 DROPBITS(extra);
 554             }
 555             if (offset > WSIZE - (wrap ? 0: left)) {
 556                 strm->msg = (char *)"invalid distance too far back";
 557                 mode = BAD;
 558                 break;
 559             }
 560             Tracevv((stderr, "inflate:         distance %lu\n", offset));
 561
 562             /* copy match from window to output */
 563             do {
 564                 ROOM();
 565                 copy = WSIZE - offset;
 566                 if (copy < left) {
 567                     from = put + copy;
 568                     copy = left - copy;
 569                 }
 570                 else {
 571                     from = put - offset;
 572                     copy = left;
 573                 }
 574                 if (copy > length) copy = length;
 575                 length -= copy;
 576                 left -= copy;
 577                 do {
 578                     *put++ = *from++;
 579                 } while (--copy);
 580             } while (length != 0);
 581             break;
 582
 583         case DONE:
 584             /* inflate stream terminated properly -- write leftover output */
 585             ret = Z_STREAM_END;
 586             if (left < WSIZE) {
 587                 if (out(out_desc, window, (unsigned)(WSIZE - left)))
 588                     ret = Z_BUF_ERROR;
 589             }
 590             goto inf_leave;
 591
 592         case BAD:
 593             ret = Z_DATA_ERROR;
 594             goto inf_leave;
 595
 596         default:                /* can't happen, but makes compilers happy */
 597             ret = Z_STREAM_ERROR;
 598             goto inf_leave;
 599         }
 600
 601     /* Return unused input */
 602   inf_leave:
 603     strm->next_in = next;
 604     strm->avail_in = have;
 605     return ret;
 606 }
 607
 608 int ZEXPORT inflateBack9End(strm)
 609 z_stream FAR *strm;
 610 {
 611     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
 612         return Z_STREAM_ERROR;
 613     ZFREE(strm, strm->state);
 614     strm->state = Z_NULL;
 615     Tracev((stderr, "inflate: end\n"));
 616     return Z_OK;
 617 }