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 */ 19int ZEXPORT inflateBack9Init_(strm, window, version, stream_size) 20z_stream FAR *strm; 21unsigned char FAR *window; 22const char *version; 23int 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 54void 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 */ 217int ZEXPORT inflateBack9(strm, in, in_desc, out, out_desc) 218z_stream FAR *strm; 219in_func in; 220void FAR *in_desc; 221out_func out; 222void 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 608int ZEXPORT inflateBack9End(strm) 609z_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} 618