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