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