common/dist/zlib/contrib/infback9/infback9.c

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