source/libs/zlib/zlib-src/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     z_const 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 char FAR *window;  /* allocated sliding window, if needed */
 233     unsigned long hold;         /* bit buffer */
 234     unsigned bits;              /* bits in bit buffer */
 235     unsigned extra;             /* extra bits needed */
 236     unsigned long length;       /* literal or length of data to copy */
 237     unsigned long offset;       /* distance back to copy string from */
 238     unsigned long copy;         /* number of stored or match bytes to copy */
 239     unsigned char FAR *from;    /* where to copy match bytes from */
 240     code const FAR *lencode;    /* starting table for length/literal codes */
 241     code const FAR *distcode;   /* starting table for distance codes */
 242     unsigned lenbits;           /* index bits for lencode */
 243     unsigned distbits;          /* index bits for distcode */
 244     code here;                  /* current decoding table entry */
 245     code last;                  /* parent table entry */
 246     unsigned len;               /* length to copy for repeats, bits to drop */
 247     int ret;                    /* return code */
 248     static const unsigned short order[19] = /* permutation of code lengths */
 249         {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
 250 #include "inffix9.h"
 251
 252     /* Check that the strm exists and that the state was initialized */
 253     if (strm == Z_NULL || strm->state == Z_NULL)
 254         return Z_STREAM_ERROR;
 255     state = (struct inflate_state FAR *)strm->state;
 256
 257     /* Reset the state */
 258     strm->msg = Z_NULL;
 259     mode = TYPE;
 260     lastblock = 0;
 261     wrap = 0;
 262     window = state->window;
 263     next = strm->next_in;
 264     have = next != Z_NULL ? strm->avail_in : 0;
 265     hold = 0;
 266     bits = 0;
 267     put = window;
 268     left = WSIZE;
 269     lencode = Z_NULL;
 270     distcode = Z_NULL;
 271
 272     /* Inflate until end of block marked as last */
 273     for (;;)
 274         switch (mode) {
 275         case TYPE:
 276             /* determine and dispatch block type */
 277             if (lastblock) {
 278                 BYTEBITS();
 279                 mode = DONE;
 280                 break;
 281             }
 282             NEEDBITS(3);
 283             lastblock = BITS(1);
 284             DROPBITS(1);
 285             switch (BITS(2)) {
 286             case 0:                             /* stored block */
 287                 Tracev((stderr, "inflate:     stored block%s\n",
 288                         lastblock ? " (last)" : ""));
 289                 mode = STORED;
 290                 break;
 291             case 1:                             /* fixed block */
 292                 lencode = lenfix;
 293                 lenbits = 9;
 294                 distcode = distfix;
 295                 distbits = 5;
 296                 Tracev((stderr, "inflate:     fixed codes block%s\n",
 297                         lastblock ? " (last)" : ""));
 298                 mode = LEN;                     /* decode codes */
 299                 break;
 300             case 2:                             /* dynamic block */
 301                 Tracev((stderr, "inflate:     dynamic codes block%s\n",
 302                         lastblock ? " (last)" : ""));
 303                 mode = TABLE;
 304                 break;
 305             case 3:
 306                 strm->msg = (char *)"invalid block type";
 307                 mode = BAD;
 308             }
 309             DROPBITS(2);
 310             break;
 311
 312         case STORED:
 313             /* get and verify stored block length */
 314             BYTEBITS();                         /* go to byte boundary */
 315             NEEDBITS(32);
 316             if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
 317                 strm->msg = (char *)"invalid stored block lengths";
 318                 mode = BAD;
 319                 break;
 320             }
 321             length = (unsigned)hold & 0xffff;
 322             Tracev((stderr, "inflate:       stored length %lu\n",
 323                     length));
 324             INITBITS();
 325
 326             /* copy stored block from input to output */
 327             while (length != 0) {
 328                 copy = length;
 329                 PULL();
 330                 ROOM();
 331                 if (copy > have) copy = have;
 332                 if (copy > left) copy = left;
 333                 zmemcpy(put, next, copy);
 334                 have -= copy;
 335                 next += copy;
 336                 left -= copy;
 337                 put += copy;
 338                 length -= copy;
 339             }
 340             Tracev((stderr, "inflate:       stored end\n"));
 341             mode = TYPE;
 342             break;
 343
 344         case TABLE:
 345             /* get dynamic table entries descriptor */
 346             NEEDBITS(14);
 347             state->nlen = BITS(5) + 257;
 348             DROPBITS(5);
 349             state->ndist = BITS(5) + 1;
 350             DROPBITS(5);
 351             state->ncode = BITS(4) + 4;
 352             DROPBITS(4);
 353             if (state->nlen > 286) {
 354                 strm->msg = (char *)"too many length symbols";
 355                 mode = BAD;
 356                 break;
 357             }
 358             Tracev((stderr, "inflate:       table sizes ok\n"));
 359
 360             /* get code length code lengths (not a typo) */
 361             state->have = 0;
 362             while (state->have < state->ncode) {
 363                 NEEDBITS(3);
 364                 state->lens[order[state->have++]] = (unsigned short)BITS(3);
 365                 DROPBITS(3);
 366             }
 367             while (state->have < 19)
 368                 state->lens[order[state->have++]] = 0;
 369             state->next = state->codes;
 370             lencode = (code const FAR *)(state->next);
 371             lenbits = 7;
 372             ret = inflate_table9(CODES, state->lens, 19, &(state->next),
 373                                 &(lenbits), state->work);
 374             if (ret) {
 375                 strm->msg = (char *)"invalid code lengths set";
 376                 mode = BAD;
 377                 break;
 378             }
 379             Tracev((stderr, "inflate:       code lengths ok\n"));
 380
 381             /* get length and distance code code lengths */
 382             state->have = 0;
 383             while (state->have < state->nlen + state->ndist) {
 384                 for (;;) {
 385                     here = lencode[BITS(lenbits)];
 386                     if ((unsigned)(here.bits) <= bits) break;
 387                     PULLBYTE();
 388                 }
 389                 if (here.val < 16) {
 390                     NEEDBITS(here.bits);
 391                     DROPBITS(here.bits);
 392                     state->lens[state->have++] = here.val;
 393                 }
 394                 else {
 395                     if (here.val == 16) {
 396                         NEEDBITS(here.bits + 2);
 397                         DROPBITS(here.bits);
 398                         if (state->have == 0) {
 399                             strm->msg = (char *)"invalid bit length repeat";
 400                             mode = BAD;
 401                             break;
 402                         }
 403                         len = (unsigned)(state->lens[state->have - 1]);
 404                         copy = 3 + BITS(2);
 405                         DROPBITS(2);
 406                     }
 407                     else if (here.val == 17) {
 408                         NEEDBITS(here.bits + 3);
 409                         DROPBITS(here.bits);
 410                         len = 0;
 411                         copy = 3 + BITS(3);
 412                         DROPBITS(3);
 413                     }
 414                     else {
 415                         NEEDBITS(here.bits + 7);
 416                         DROPBITS(here.bits);
 417                         len = 0;
 418                         copy = 11 + BITS(7);
 419                         DROPBITS(7);
 420                     }
 421                     if (state->have + copy > state->nlen + state->ndist) {
 422                         strm->msg = (char *)"invalid bit length repeat";
 423                         mode = BAD;
 424                         break;
 425                     }
 426                     while (copy--)
 427                         state->lens[state->have++] = (unsigned short)len;
 428                 }
 429             }
 430
 431             /* handle error breaks in while */
 432             if (mode == BAD) break;
 433
 434             /* check for end-of-block code (better have one) */
 435             if (state->lens[256] == 0) {
 436                 strm->msg = (char *)"invalid code -- missing end-of-block";
 437                 mode = BAD;
 438                 break;
 439             }
 440
 441             /* build code tables -- note: do not change the lenbits or distbits
 442                values here (9 and 6) without reading the comments in inftree9.h
 443                concerning the ENOUGH constants, which depend on those values */
 444             state->next = state->codes;
 445             lencode = (code const FAR *)(state->next);
 446             lenbits = 9;
 447             ret = inflate_table9(LENS, state->lens, state->nlen,
 448                             &(state->next), &(lenbits), state->work);
 449             if (ret) {
 450                 strm->msg = (char *)"invalid literal/lengths set";
 451                 mode = BAD;
 452                 break;
 453             }
 454             distcode = (code const FAR *)(state->next);
 455             distbits = 6;
 456             ret = inflate_table9(DISTS, state->lens + state->nlen,
 457                             state->ndist, &(state->next), &(distbits),
 458                             state->work);
 459             if (ret) {
 460                 strm->msg = (char *)"invalid distances set";
 461                 mode = BAD;
 462                 break;
 463             }
 464             Tracev((stderr, "inflate:       codes ok\n"));
 465             mode = LEN;
 466
 467         case LEN:
 468             /* get a literal, length, or end-of-block code */
 469             for (;;) {
 470                 here = lencode[BITS(lenbits)];
 471                 if ((unsigned)(here.bits) <= bits) break;
 472                 PULLBYTE();
 473             }
 474             if (here.op && (here.op & 0xf0) == 0) {
 475                 last = here;
 476                 for (;;) {
 477                     here = lencode[last.val +
 478                             (BITS(last.bits + last.op) >> last.bits)];
 479                     if ((unsigned)(last.bits + here.bits) <= bits) break;
 480                     PULLBYTE();
 481                 }
 482                 DROPBITS(last.bits);
 483             }
 484             DROPBITS(here.bits);
 485             length = (unsigned)here.val;
 486
 487             /* process literal */
 488             if (here.op == 0) {
 489                 Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
 490                         "inflate:         literal '%c'\n" :
 491                         "inflate:         literal 0x%02x\n", here.val));
 492                 ROOM();
 493                 *put++ = (unsigned char)(length);
 494                 left--;
 495                 mode = LEN;
 496                 break;
 497             }
 498
 499             /* process end of block */
 500             if (here.op & 32) {
 501                 Tracevv((stderr, "inflate:         end of block\n"));
 502                 mode = TYPE;
 503                 break;
 504             }
 505
 506             /* invalid code */
 507             if (here.op & 64) {
 508                 strm->msg = (char *)"invalid literal/length code";
 509                 mode = BAD;
 510                 break;
 511             }
 512
 513             /* length code -- get extra bits, if any */
 514             extra = (unsigned)(here.op) & 31;
 515             if (extra != 0) {
 516                 NEEDBITS(extra);
 517                 length += BITS(extra);
 518                 DROPBITS(extra);
 519             }
 520             Tracevv((stderr, "inflate:         length %lu\n", length));
 521
 522             /* get distance code */
 523             for (;;) {
 524                 here = distcode[BITS(distbits)];
 525                 if ((unsigned)(here.bits) <= bits) break;
 526                 PULLBYTE();
 527             }
 528             if ((here.op & 0xf0) == 0) {
 529                 last = here;
 530                 for (;;) {
 531                     here = distcode[last.val +
 532                             (BITS(last.bits + last.op) >> last.bits)];
 533                     if ((unsigned)(last.bits + here.bits) <= bits) break;
 534                     PULLBYTE();
 535                 }
 536                 DROPBITS(last.bits);
 537             }
 538             DROPBITS(here.bits);
 539             if (here.op & 64) {
 540                 strm->msg = (char *)"invalid distance code";
 541                 mode = BAD;
 542                 break;
 543             }
 544             offset = (unsigned)here.val;
 545
 546             /* get distance extra bits, if any */
 547             extra = (unsigned)(here.op) & 15;
 548             if (extra != 0) {
 549                 NEEDBITS(extra);
 550                 offset += BITS(extra);
 551                 DROPBITS(extra);
 552             }
 553             if (offset > WSIZE - (wrap ? 0: left)) {
 554                 strm->msg = (char *)"invalid distance too far back";
 555                 mode = BAD;
 556                 break;
 557             }
 558             Tracevv((stderr, "inflate:         distance %lu\n", offset));
 559
 560             /* copy match from window to output */
 561             do {
 562                 ROOM();
 563                 copy = WSIZE - offset;
 564                 if (copy < left) {
 565                     from = put + copy;
 566                     copy = left - copy;
 567                 }
 568                 else {
 569                     from = put - offset;
 570                     copy = left;
 571                 }
 572                 if (copy > length) copy = length;
 573                 length -= copy;
 574                 left -= copy;
 575                 do {
 576                     *put++ = *from++;
 577                 } while (--copy);
 578             } while (length != 0);
 579             break;
 580
 581         case DONE:
 582             /* inflate stream terminated properly -- write leftover output */
 583             ret = Z_STREAM_END;
 584             if (left < WSIZE) {
 585                 if (out(out_desc, window, (unsigned)(WSIZE - left)))
 586                     ret = Z_BUF_ERROR;
 587             }
 588             goto inf_leave;
 589
 590         case BAD:
 591             ret = Z_DATA_ERROR;
 592             goto inf_leave;
 593
 594         default:                /* can't happen, but makes compilers happy */
 595             ret = Z_STREAM_ERROR;
 596             goto inf_leave;
 597         }
 598
 599     /* Return unused input */
 600   inf_leave:
 601     strm->next_in = next;
 602     strm->avail_in = have;
 603     return ret;
 604 }
 605
 606 int ZEXPORT inflateBack9End(strm)
 607 z_stream FAR *strm;
 608 {
 609     if (strm == Z_NULL || strm->state == Z_NULL || strm->zfree == (free_func)0)
 610         return Z_STREAM_ERROR;
 611     ZFREE(strm, strm->state);
 612     strm->state = Z_NULL;
 613     Tracev((stderr, "inflate: end\n"));
 614     return Z_OK;
 615 }