1/* 2 * This file is derived from various .h and .c files from the zlib-0.95 3 * distribution by Jean-loup Gailly and Mark Adler, with some additions 4 * by Paul Mackerras to aid in implementing Deflate compression and 5 * decompression for PPP packets. See zlib.h for conditions of 6 * distribution and use. 7 * 8 * Changes that have been made include: 9 * - changed functions not used outside this file to "local" 10 * - added minCompression parameter to deflateInit2 11 * - added Z_PACKET_FLUSH (see zlib.h for details) 12 * - added inflateIncomp 13 * 14 Copyright (C) 1995 Jean-loup Gailly and Mark Adler 15 16 This software is provided 'as-is', without any express or implied 17 warranty. In no event will the authors be held liable for any damages 18 arising from the use of this software. 19 20 Permission is granted to anyone to use this software for any purpose, 21 including commercial applications, and to alter it and redistribute it 22 freely, subject to the following restrictions: 23 24 1. The origin of this software must not be misrepresented; you must not 25 claim that you wrote the original software. If you use this software 26 in a product, an acknowledgment in the product documentation would be 27 appreciated but is not required. 28 2. Altered source versions must be plainly marked as such, and must not be 29 misrepresented as being the original software. 30 3. This notice may not be removed or altered from any source distribution. 31 32 Jean-loup Gailly Mark Adler 33 gzip@prep.ai.mit.edu madler@alumni.caltech.edu 34 35 * 36 * 37 */ 38 39/*+++++*/ 40/* zutil.h -- internal interface and configuration of the compression library 41 * Copyright (C) 1995 Jean-loup Gailly. 42 * For conditions of distribution and use, see copyright notice in zlib.h 43 */ 44 45/* WARNING: this file should *not* be used by applications. It is 46 part of the implementation of the compression library and is 47 subject to change. Applications should only use zlib.h. 48 */ 49 50/* From: zutil.h,v 1.9 1995/05/03 17:27:12 jloup Exp */ 51 52#define _Z_UTIL_H 53 54#include "zlib.h" 55 56#ifndef local 57# define local static 58#endif 59/* compile with -Dlocal if your debugger can't find static symbols */ 60 61#define FAR 62 63typedef unsigned char uch; 64typedef uch FAR uchf; 65typedef unsigned short ush; 66typedef ush FAR ushf; 67typedef unsigned long ulg; 68 69extern char *z_errmsg[]; /* indexed by 1-zlib_error */ 70 71#define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err) 72/* To be used only when the state is known to be valid */ 73 74#ifndef NULL 75#define NULL ((void *) 0) 76#endif 77 78 /* common constants */ 79 80#define DEFLATED 8 81 82#ifndef DEF_WBITS 83# define DEF_WBITS MAX_WBITS 84#endif 85/* default windowBits for decompression. MAX_WBITS is for compression only */ 86 87#if MAX_MEM_LEVEL >= 8 88# define DEF_MEM_LEVEL 8 89#else 90# define DEF_MEM_LEVEL MAX_MEM_LEVEL 91#endif 92/* default memLevel */ 93 94#define STORED_BLOCK 0 95#define STATIC_TREES 1 96#define DYN_TREES 2 97/* The three kinds of block type */ 98 99#define MIN_MATCH 3 100#define MAX_MATCH 258 101/* The minimum and maximum match lengths */ 102 103 /* functions */ 104 105#include <linux/string.h> 106#define zmemcpy memcpy 107#define zmemzero(dest, len) memset(dest, 0, len) 108 109/* Diagnostic functions */ 110#ifdef DEBUG_ZLIB 111# include <stdio.h> 112# ifndef verbose 113# define verbose 0 114# endif 115# define Assert(cond,msg) {if(!(cond)) z_error(msg);} 116# define Trace(x) fprintf x 117# define Tracev(x) {if (verbose) fprintf x ;} 118# define Tracevv(x) {if (verbose>1) fprintf x ;} 119# define Tracec(c,x) {if (verbose && (c)) fprintf x ;} 120# define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;} 121#else 122# define Assert(cond,msg) 123# define Trace(x) 124# define Tracev(x) 125# define Tracevv(x) 126# define Tracec(c,x) 127# define Tracecv(c,x) 128#endif 129 130 131typedef uLong (*check_func) OF((uLong check, Bytef *buf, uInt len)); 132 133/* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */ 134/* void zcfree OF((voidpf opaque, voidpf ptr)); */ 135 136#define ZALLOC(strm, items, size) \ 137 (*((strm)->zalloc))((strm)->opaque, (items), (size)) 138#define ZFREE(strm, addr, size) \ 139 (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), (size)) 140#define TRY_FREE(s, p, n) {if (p) ZFREE(s, p, n);} 141 142/* deflate.h -- internal compression state 143 * Copyright (C) 1995 Jean-loup Gailly 144 * For conditions of distribution and use, see copyright notice in zlib.h 145 */ 146 147/* WARNING: this file should *not* be used by applications. It is 148 part of the implementation of the compression library and is 149 subject to change. Applications should only use zlib.h. 150 */ 151 152/*+++++*/ 153/* infblock.h -- header to use infblock.c 154 * Copyright (C) 1995 Mark Adler 155 * For conditions of distribution and use, see copyright notice in zlib.h 156 */ 157 158/* WARNING: this file should *not* be used by applications. It is 159 part of the implementation of the compression library and is 160 subject to change. Applications should only use zlib.h. 161 */ 162 163struct inflate_blocks_state; 164typedef struct inflate_blocks_state FAR inflate_blocks_statef; 165 166local inflate_blocks_statef * inflate_blocks_new OF(( 167 z_stream *z, 168 check_func c, /* check function */ 169 uInt w)); /* window size */ 170 171local int inflate_blocks OF(( 172 inflate_blocks_statef *, 173 z_stream *, 174 int)); /* initial return code */ 175 176local void inflate_blocks_reset OF(( 177 inflate_blocks_statef *, 178 z_stream *, 179 uLongf *)); /* check value on output */ 180 181local int inflate_blocks_free OF(( 182 inflate_blocks_statef *, 183 z_stream *, 184 uLongf *)); /* check value on output */ 185 186local int inflate_addhistory OF(( 187 inflate_blocks_statef *, 188 z_stream *)); 189 190local int inflate_packet_flush OF(( 191 inflate_blocks_statef *)); 192 193/*+++++*/ 194/* inftrees.h -- header to use inftrees.c 195 * Copyright (C) 1995 Mark Adler 196 * For conditions of distribution and use, see copyright notice in zlib.h 197 */ 198 199/* WARNING: this file should *not* be used by applications. It is 200 part of the implementation of the compression library and is 201 subject to change. Applications should only use zlib.h. 202 */ 203 204/* Huffman code lookup table entry--this entry is four bytes for machines 205 that have 16-bit pointers (e.g. PC's in the small or medium model). */ 206 207typedef struct inflate_huft_s FAR inflate_huft; 208 209struct inflate_huft_s { 210 union { 211 struct { 212 Byte Exop; /* number of extra bits or operation */ 213 Byte Bits; /* number of bits in this code or subcode */ 214 } what; 215 uInt Nalloc; /* number of these allocated here */ 216 Bytef *pad; /* pad structure to a power of 2 (4 bytes for */ 217 } word; /* 16-bit, 8 bytes for 32-bit machines) */ 218 union { 219 uInt Base; /* literal, length base, or distance base */ 220 inflate_huft *Next; /* pointer to next level of table */ 221 } more; 222}; 223 224#ifdef DEBUG_ZLIB 225 local uInt inflate_hufts; 226#endif 227 228local int inflate_trees_bits OF(( 229 uIntf *, /* 19 code lengths */ 230 uIntf *, /* bits tree desired/actual depth */ 231 inflate_huft * FAR *, /* bits tree result */ 232 z_stream *)); /* for zalloc, zfree functions */ 233 234local int inflate_trees_dynamic OF(( 235 uInt, /* number of literal/length codes */ 236 uInt, /* number of distance codes */ 237 uIntf *, /* that many (total) code lengths */ 238 uIntf *, /* literal desired/actual bit depth */ 239 uIntf *, /* distance desired/actual bit depth */ 240 inflate_huft * FAR *, /* literal/length tree result */ 241 inflate_huft * FAR *, /* distance tree result */ 242 z_stream *)); /* for zalloc, zfree functions */ 243 244local int inflate_trees_fixed OF(( 245 uIntf *, /* literal desired/actual bit depth */ 246 uIntf *, /* distance desired/actual bit depth */ 247 inflate_huft * FAR *, /* literal/length tree result */ 248 inflate_huft * FAR *)); /* distance tree result */ 249 250local int inflate_trees_free OF(( 251 inflate_huft *, /* tables to free */ 252 z_stream *)); /* for zfree function */ 253 254 255/*+++++*/ 256/* infcodes.h -- header to use infcodes.c 257 * Copyright (C) 1995 Mark Adler 258 * For conditions of distribution and use, see copyright notice in zlib.h 259 */ 260 261/* WARNING: this file should *not* be used by applications. It is 262 part of the implementation of the compression library and is 263 subject to change. Applications should only use zlib.h. 264 */ 265 266struct inflate_codes_state; 267typedef struct inflate_codes_state FAR inflate_codes_statef; 268 269local inflate_codes_statef *inflate_codes_new OF(( 270 uInt, uInt, 271 inflate_huft *, inflate_huft *, 272 z_stream *)); 273 274local int inflate_codes OF(( 275 inflate_blocks_statef *, 276 z_stream *, 277 int)); 278 279local void inflate_codes_free OF(( 280 inflate_codes_statef *, 281 z_stream *)); 282 283 284/*+++++*/ 285/* inflate.c -- zlib interface to inflate modules 286 * Copyright (C) 1995 Mark Adler 287 * For conditions of distribution and use, see copyright notice in zlib.h 288 */ 289 290/* inflate private state */ 291struct internal_state { 292 293 /* mode */ 294 enum { 295 METHOD, /* waiting for method byte */ 296 FLAG, /* waiting for flag byte */ 297 BLOCKS, /* decompressing blocks */ 298 CHECK4, /* four check bytes to go */ 299 CHECK3, /* three check bytes to go */ 300 CHECK2, /* two check bytes to go */ 301 CHECK1, /* one check byte to go */ 302 DONE, /* finished check, done */ 303 BAD} /* got an error--stay here */ 304 mode; /* current inflate mode */ 305 306 /* mode dependent information */ 307 union { 308 uInt method; /* if FLAGS, method byte */ 309 struct { 310 uLong was; /* computed check value */ 311 uLong need; /* stream check value */ 312 } check; /* if CHECK, check values to compare */ 313 uInt marker; /* if BAD, inflateSync's marker bytes count */ 314 } sub; /* submode */ 315 316 /* mode independent information */ 317 int nowrap; /* flag for no wrapper */ 318 uInt wbits; /* log2(window size) (8..15, defaults to 15) */ 319 inflate_blocks_statef 320 *blocks; /* current inflate_blocks state */ 321 322}; 323 324 325int inflateReset(z) 326z_stream *z; 327{ 328 uLong c; 329 330 if (z == Z_NULL || z->state == Z_NULL) 331 return Z_STREAM_ERROR; 332 z->total_in = z->total_out = 0; 333 z->msg = Z_NULL; 334 z->state->mode = z->state->nowrap ? BLOCKS : METHOD; 335 inflate_blocks_reset(z->state->blocks, z, &c); 336 Trace((stderr, "inflate: reset\n")); 337 return Z_OK; 338} 339 340 341int inflateEnd(z) 342z_stream *z; 343{ 344 uLong c; 345 346 if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL) 347 return Z_STREAM_ERROR; 348 if (z->state->blocks != Z_NULL) 349 inflate_blocks_free(z->state->blocks, z, &c); 350 ZFREE(z, z->state, sizeof(struct internal_state)); 351 z->state = Z_NULL; 352 Trace((stderr, "inflate: end\n")); 353 return Z_OK; 354} 355 356 357int inflateInit2(z, w) 358z_stream *z; 359int w; 360{ 361 /* initialize state */ 362 if (z == Z_NULL) 363 return Z_STREAM_ERROR; 364/* if (z->zalloc == Z_NULL) z->zalloc = zcalloc; */ 365/* if (z->zfree == Z_NULL) z->zfree = zcfree; */ 366 if ((z->state = (struct internal_state FAR *) 367 ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL) 368 return Z_MEM_ERROR; 369 z->state->blocks = Z_NULL; 370 371 /* handle undocumented nowrap option (no zlib header or check) */ 372 z->state->nowrap = 0; 373 if (w < 0) 374 { 375 w = - w; 376 z->state->nowrap = 1; 377 } 378 379 /* set window size */ 380 if (w < 8 || w > 15) 381 { 382 inflateEnd(z); 383 return Z_STREAM_ERROR; 384 } 385 z->state->wbits = (uInt)w; 386 387 /* create inflate_blocks state */ 388 if ((z->state->blocks = 389 inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, 1 << w)) 390 == Z_NULL) 391 { 392 inflateEnd(z); 393 return Z_MEM_ERROR; 394 } 395 Trace((stderr, "inflate: allocated\n")); 396 397 /* reset state */ 398 inflateReset(z); 399 return Z_OK; 400} 401 402 403int inflateInit(z) 404z_stream *z; 405{ 406 return inflateInit2(z, DEF_WBITS); 407} 408 409 410#define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;} 411#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++) 412 413int inflate(z, f) 414z_stream *z; 415int f; 416{ 417 int r; 418 uInt b; 419 420 if (z == Z_NULL || z->next_in == Z_NULL) 421 return Z_STREAM_ERROR; 422 r = Z_BUF_ERROR; 423 while (1) switch (z->state->mode) 424 { 425 case METHOD: 426 NEEDBYTE 427 if (((z->state->sub.method = NEXTBYTE) & 0xf) != DEFLATED) 428 { 429 z->state->mode = BAD; 430 z->msg = "unknown compression method"; 431 z->state->sub.marker = 5; /* can't try inflateSync */ 432 break; 433 } 434 if ((z->state->sub.method >> 4) + 8 > z->state->wbits) 435 { 436 z->state->mode = BAD; 437 z->msg = "invalid window size"; 438 z->state->sub.marker = 5; /* can't try inflateSync */ 439 break; 440 } 441 z->state->mode = FLAG; 442 case FLAG: 443 NEEDBYTE 444 if ((b = NEXTBYTE) & 0x20) 445 { 446 z->state->mode = BAD; 447 z->msg = "invalid reserved bit"; 448 z->state->sub.marker = 5; /* can't try inflateSync */ 449 break; 450 } 451 if (((z->state->sub.method << 8) + b) % 31) 452 { 453 z->state->mode = BAD; 454 z->msg = "incorrect header check"; 455 z->state->sub.marker = 5; /* can't try inflateSync */ 456 break; 457 } 458 Trace((stderr, "inflate: zlib header ok\n")); 459 z->state->mode = BLOCKS; 460 case BLOCKS: 461 r = inflate_blocks(z->state->blocks, z, r); 462 if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0) 463 r = inflate_packet_flush(z->state->blocks); 464 if (r == Z_DATA_ERROR) 465 { 466 z->state->mode = BAD; 467 z->state->sub.marker = 0; /* can try inflateSync */ 468 break; 469 } 470 if (r != Z_STREAM_END) 471 return r; 472 r = Z_OK; 473 inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was); 474 if (z->state->nowrap) 475 { 476 z->state->mode = DONE; 477 break; 478 } 479 z->state->mode = CHECK4; 480 case CHECK4: 481 NEEDBYTE 482 z->state->sub.check.need = (uLong)NEXTBYTE << 24; 483 z->state->mode = CHECK3; 484 case CHECK3: 485 NEEDBYTE 486 z->state->sub.check.need += (uLong)NEXTBYTE << 16; 487 z->state->mode = CHECK2; 488 case CHECK2: 489 NEEDBYTE 490 z->state->sub.check.need += (uLong)NEXTBYTE << 8; 491 z->state->mode = CHECK1; 492 case CHECK1: 493 NEEDBYTE 494 z->state->sub.check.need += (uLong)NEXTBYTE; 495 496 if (z->state->sub.check.was != z->state->sub.check.need) 497 { 498 z->state->mode = BAD; 499 z->msg = "incorrect data check"; 500 z->state->sub.marker = 5; /* can't try inflateSync */ 501 break; 502 } 503 Trace((stderr, "inflate: zlib check ok\n")); 504 z->state->mode = DONE; 505 case DONE: 506 return Z_STREAM_END; 507 case BAD: 508 return Z_DATA_ERROR; 509 default: 510 return Z_STREAM_ERROR; 511 } 512 513 empty: 514 if (f != Z_PACKET_FLUSH) 515 return r; 516 z->state->mode = BAD; 517 z->state->sub.marker = 0; /* can try inflateSync */ 518 return Z_DATA_ERROR; 519} 520 521/* 522 * This subroutine adds the data at next_in/avail_in to the output history 523 * without performing any output. The output buffer must be "caught up"; 524 * i.e. no pending output (hence s->read equals s->write), and the state must 525 * be BLOCKS (i.e. we should be willing to see the start of a series of 526 * BLOCKS). On exit, the output will also be caught up, and the checksum 527 * will have been updated if need be. 528 */ 529 530int inflateIncomp(z) 531z_stream *z; 532{ 533 if (z->state->mode != BLOCKS) 534 return Z_DATA_ERROR; 535 return inflate_addhistory(z->state->blocks, z); 536} 537 538 539int inflateSync(z) 540z_stream *z; 541{ 542 uInt n; /* number of bytes to look at */ 543 Bytef *p; /* pointer to bytes */ 544 uInt m; /* number of marker bytes found in a row */ 545 uLong r, w; /* temporaries to save total_in and total_out */ 546 547 /* set up */ 548 if (z == Z_NULL || z->state == Z_NULL) 549 return Z_STREAM_ERROR; 550 if (z->state->mode != BAD) 551 { 552 z->state->mode = BAD; 553 z->state->sub.marker = 0; 554 } 555 if ((n = z->avail_in) == 0) 556 return Z_BUF_ERROR; 557 p = z->next_in; 558 m = z->state->sub.marker; 559 560 /* search */ 561 while (n && m < 4) 562 { 563 if (*p == (Byte)(m < 2 ? 0 : 0xff)) 564 m++; 565 else if (*p) 566 m = 0; 567 else 568 m = 4 - m; 569 p++, n--; 570 } 571 572 /* restore */ 573 z->total_in += p - z->next_in; 574 z->next_in = p; 575 z->avail_in = n; 576 z->state->sub.marker = m; 577 578 /* return no joy or set up to restart on a new block */ 579 if (m != 4) 580 return Z_DATA_ERROR; 581 r = z->total_in; w = z->total_out; 582 inflateReset(z); 583 z->total_in = r; z->total_out = w; 584 z->state->mode = BLOCKS; 585 return Z_OK; 586} 587 588#undef NEEDBYTE 589#undef NEXTBYTE 590 591/*+++++*/ 592/* infutil.h -- types and macros common to blocks and codes 593 * Copyright (C) 1995 Mark Adler 594 * For conditions of distribution and use, see copyright notice in zlib.h 595 */ 596 597/* WARNING: this file should *not* be used by applications. It is 598 part of the implementation of the compression library and is 599 subject to change. Applications should only use zlib.h. 600 */ 601 602/* inflate blocks semi-private state */ 603struct inflate_blocks_state { 604 605 /* mode */ 606 enum { 607 TYPE, /* get type bits (3, including end bit) */ 608 LENS, /* get lengths for stored */ 609 STORED, /* processing stored block */ 610 TABLE, /* get table lengths */ 611 BTREE, /* get bit lengths tree for a dynamic block */ 612 DTREE, /* get length, distance trees for a dynamic block */ 613 CODES, /* processing fixed or dynamic block */ 614 DRY, /* output remaining window bytes */ 615 DONEB, /* finished last block, done */ 616 BADB} /* got a data error--stuck here */ 617 mode; /* current inflate_block mode */ 618 619 /* mode dependent information */ 620 union { 621 uInt left; /* if STORED, bytes left to copy */ 622 struct { 623 uInt table; /* table lengths (14 bits) */ 624 uInt index; /* index into blens (or border) */ 625 uIntf *blens; /* bit lengths of codes */ 626 uInt bb; /* bit length tree depth */ 627 inflate_huft *tb; /* bit length decoding tree */ 628 int nblens; /* # elements allocated at blens */ 629 } trees; /* if DTREE, decoding info for trees */ 630 struct { 631 inflate_huft *tl, *td; /* trees to free */ 632 inflate_codes_statef 633 *codes; 634 } decode; /* if CODES, current state */ 635 } sub; /* submode */ 636 uInt last; /* true if this block is the last block */ 637 638 /* mode independent information */ 639 uInt bitk; /* bits in bit buffer */ 640 uLong bitb; /* bit buffer */ 641 Bytef *window; /* sliding window */ 642 Bytef *end; /* one byte after sliding window */ 643 Bytef *read; /* window read pointer */ 644 Bytef *write; /* window write pointer */ 645 check_func checkfn; /* check function */ 646 uLong check; /* check on output */ 647 648}; 649 650 651/* defines for inflate input/output */ 652/* update pointers and return */ 653#define UPDBITS {s->bitb=b;s->bitk=k;} 654#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;} 655#define UPDOUT {s->write=q;} 656#define UPDATE {UPDBITS UPDIN UPDOUT} 657#define LEAVE {UPDATE return inflate_flush(s,z,r);} 658/* get bytes and bits */ 659#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;} 660#define NEEDBYTE {if(n)r=Z_OK;else LEAVE} 661#define NEXTBYTE (n--,*p++) 662#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}} 663#define DUMPBITS(j) {b>>=(j);k-=(j);} 664/* output bytes */ 665#define WAVAIL (q<s->read?s->read-q-1:s->end-q) 666#define LOADOUT {q=s->write;m=WAVAIL;} 667#define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}} 668#define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT} 669#define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;} 670#define OUTBYTE(a) {*q++=(Byte)(a);m--;} 671/* load local pointers */ 672#define LOAD {LOADIN LOADOUT} 673 674/* And'ing with mask[n] masks the lower n bits */ 675local uInt inflate_mask[] = { 676 0x0000, 677 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 678 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 679}; 680 681/* copy as much as possible from the sliding window to the output area */ 682local int inflate_flush OF(( 683 inflate_blocks_statef *, 684 z_stream *, 685 int)); 686 687/*+++++*/ 688/* inffast.h -- header to use inffast.c 689 * Copyright (C) 1995 Mark Adler 690 * For conditions of distribution and use, see copyright notice in zlib.h 691 */ 692 693/* WARNING: this file should *not* be used by applications. It is 694 part of the implementation of the compression library and is 695 subject to change. Applications should only use zlib.h. 696 */ 697 698local int inflate_fast OF(( 699 uInt, 700 uInt, 701 inflate_huft *, 702 inflate_huft *, 703 inflate_blocks_statef *, 704 z_stream *)); 705 706 707/*+++++*/ 708/* infblock.c -- interpret and process block types to last block 709 * Copyright (C) 1995 Mark Adler 710 * For conditions of distribution and use, see copyright notice in zlib.h 711 */ 712 713/* Table for deflate from PKZIP's appnote.txt. */ 714local uInt border[] = { /* Order of the bit length code lengths */ 715 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 716 717/* 718 Notes beyond the 1.93a appnote.txt: 719 720 1. Distance pointers never point before the beginning of the output 721 stream. 722 2. Distance pointers can point back across blocks, up to 32k away. 723 3. There is an implied maximum of 7 bits for the bit length table and 724 15 bits for the actual data. 725 4. If only one code exists, then it is encoded using one bit. (Zero 726 would be more efficient, but perhaps a little confusing.) If two 727 codes exist, they are coded using one bit each (0 and 1). 728 5. There is no way of sending zero distance codes--a dummy must be 729 sent if there are none. (History: a pre 2.0 version of PKZIP would 730 store blocks with no distance codes, but this was discovered to be 731 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 732 zero distance codes, which is sent as one code of zero bits in 733 length. 734 6. There are up to 286 literal/length codes. Code 256 represents the 735 end-of-block. Note however that the static length tree defines 736 288 codes just to fill out the Huffman codes. Codes 286 and 287 737 cannot be used though, since there is no length base or extra bits 738 defined for them. Similarily, there are up to 30 distance codes. 739 However, static trees define 32 codes (all 5 bits) to fill out the 740 Huffman codes, but the last two had better not show up in the data. 741 7. Unzip can check dynamic Huffman blocks for complete code sets. 742 The exception is that a single code would not be complete (see #4). 743 8. The five bits following the block type is really the number of 744 literal codes sent minus 257. 745 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 746 (1+6+6). Therefore, to output three times the length, you output 747 three codes (1+1+1), whereas to output four times the same length, 748 you only need two codes (1+3). Hmm. 749 10. In the tree reconstruction algorithm, Code = Code + Increment 750 only if BitLength(i) is not zero. (Pretty obvious.) 751 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 752 12. Note: length code 284 can represent 227-258, but length code 285 753 really is 258. The last length deserves its own, short code 754 since it gets used a lot in very redundant files. The length 755 258 is special since 258 - 3 (the min match length) is 255. 756 13. The literal/length and distance code bit lengths are read as a 757 single stream of lengths. It is possible (and advantageous) for 758 a repeat code (16, 17, or 18) to go across the boundary between 759 the two sets of lengths. 760 */ 761 762 763local void inflate_blocks_reset(s, z, c) 764inflate_blocks_statef *s; 765z_stream *z; 766uLongf *c; 767{ 768 if (s->checkfn != Z_NULL) 769 *c = s->check; 770 if (s->mode == BTREE || s->mode == DTREE) 771 ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt)); 772 if (s->mode == CODES) 773 { 774 inflate_codes_free(s->sub.decode.codes, z); 775 inflate_trees_free(s->sub.decode.td, z); 776 inflate_trees_free(s->sub.decode.tl, z); 777 } 778 s->mode = TYPE; 779 s->bitk = 0; 780 s->bitb = 0; 781 s->read = s->write = s->window; 782 if (s->checkfn != Z_NULL) 783 s->check = (*s->checkfn)(0L, Z_NULL, 0); 784 Trace((stderr, "inflate: blocks reset\n")); 785} 786 787 788local inflate_blocks_statef *inflate_blocks_new(z, c, w) 789z_stream *z; 790check_func c; 791uInt w; 792{ 793 inflate_blocks_statef *s; 794 795 if ((s = (inflate_blocks_statef *)ZALLOC 796 (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) 797 return s; 798 if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) 799 { 800 ZFREE(z, s, sizeof(struct inflate_blocks_state)); 801 return Z_NULL; 802 } 803 s->end = s->window + w; 804 s->checkfn = c; 805 s->mode = TYPE; 806 Trace((stderr, "inflate: blocks allocated\n")); 807 inflate_blocks_reset(s, z, &s->check); 808 return s; 809} 810 811 812local int inflate_blocks(s, z, r) 813inflate_blocks_statef *s; 814z_stream *z; 815int r; 816{ 817 uInt t; /* temporary storage */ 818 uLong b; /* bit buffer */ 819 uInt k; /* bits in bit buffer */ 820 Bytef *p; /* input data pointer */ 821 uInt n; /* bytes available there */ 822 Bytef *q; /* output window write pointer */ 823 uInt m; /* bytes to end of window or read pointer */ 824 825 /* copy input/output information to locals (UPDATE macro restores) */ 826 LOAD 827 828 /* process input based on current state */ 829 while (1) switch (s->mode) 830 { 831 case TYPE: 832 NEEDBITS(3) 833 t = (uInt)b & 7; 834 s->last = t & 1; 835 switch (t >> 1) 836 { 837 case 0: /* stored */ 838 Trace((stderr, "inflate: stored block%s\n", 839 s->last ? " (last)" : "")); 840 DUMPBITS(3) 841 t = k & 7; /* go to byte boundary */ 842 DUMPBITS(t) 843 s->mode = LENS; /* get length of stored block */ 844 break; 845 case 1: /* fixed */ 846 Trace((stderr, "inflate: fixed codes block%s\n", 847 s->last ? " (last)" : "")); 848 { 849 uInt bl, bd; 850 inflate_huft *tl, *td; 851 852 inflate_trees_fixed(&bl, &bd, &tl, &td); 853 s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); 854 if (s->sub.decode.codes == Z_NULL) 855 { 856 r = Z_MEM_ERROR; 857 LEAVE 858 } 859 s->sub.decode.tl = Z_NULL; /* don't try to free these */ 860 s->sub.decode.td = Z_NULL; 861 } 862 DUMPBITS(3) 863 s->mode = CODES; 864 break; 865 case 2: /* dynamic */ 866 Trace((stderr, "inflate: dynamic codes block%s\n", 867 s->last ? " (last)" : "")); 868 DUMPBITS(3) 869 s->mode = TABLE; 870 break; 871 case 3: /* illegal */ 872 DUMPBITS(3) 873 s->mode = BADB; 874 z->msg = "invalid block type"; 875 r = Z_DATA_ERROR; 876 LEAVE 877 } 878 break; 879 case LENS: 880 NEEDBITS(32) 881 if (((~b) >> 16) != (b & 0xffff)) 882 { 883 s->mode = BADB; 884 z->msg = "invalid stored block lengths"; 885 r = Z_DATA_ERROR; 886 LEAVE 887 } 888 s->sub.left = (uInt)b & 0xffff; 889 b = k = 0; /* dump bits */ 890 Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); 891 s->mode = s->sub.left ? STORED : TYPE; 892 break; 893 case STORED: 894 if (n == 0) 895 LEAVE 896 NEEDOUT 897 t = s->sub.left; 898 if (t > n) t = n; 899 if (t > m) t = m; 900 zmemcpy(q, p, t); 901 p += t; n -= t; 902 q += t; m -= t; 903 if ((s->sub.left -= t) != 0) 904 break; 905 Tracev((stderr, "inflate: stored end, %lu total out\n", 906 z->total_out + (q >= s->read ? q - s->read : 907 (s->end - s->read) + (q - s->window)))); 908 s->mode = s->last ? DRY : TYPE; 909 break; 910 case TABLE: 911 NEEDBITS(14) 912 s->sub.trees.table = t = (uInt)b & 0x3fff; 913#ifndef PKZIP_BUG_WORKAROUND 914 if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) 915 { 916 s->mode = BADB; 917 z->msg = "too many length or distance symbols"; 918 r = Z_DATA_ERROR; 919 LEAVE 920 } 921#endif 922 t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); 923 if (t < 19) 924 t = 19; 925 if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) 926 { 927 r = Z_MEM_ERROR; 928 LEAVE 929 } 930 s->sub.trees.nblens = t; 931 DUMPBITS(14) 932 s->sub.trees.index = 0; 933 Tracev((stderr, "inflate: table sizes ok\n")); 934 s->mode = BTREE; 935 case BTREE: 936 while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) 937 { 938 NEEDBITS(3) 939 s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; 940 DUMPBITS(3) 941 } 942 while (s->sub.trees.index < 19) 943 s->sub.trees.blens[border[s->sub.trees.index++]] = 0; 944 s->sub.trees.bb = 7; 945 t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, 946 &s->sub.trees.tb, z); 947 if (t != Z_OK) 948 { 949 r = t; 950 if (r == Z_DATA_ERROR) 951 s->mode = BADB; 952 LEAVE 953 } 954 s->sub.trees.index = 0; 955 Tracev((stderr, "inflate: bits tree ok\n")); 956 s->mode = DTREE; 957 case DTREE: 958 while (t = s->sub.trees.table, 959 s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) 960 { 961 inflate_huft *h; 962 uInt i, j, c; 963 964 t = s->sub.trees.bb; 965 NEEDBITS(t) 966 h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); 967 t = h->word.what.Bits; 968 c = h->more.Base; 969 if (c < 16) 970 { 971 DUMPBITS(t) 972 s->sub.trees.blens[s->sub.trees.index++] = c; 973 } 974 else /* c == 16..18 */ 975 { 976 i = c == 18 ? 7 : c - 14; 977 j = c == 18 ? 11 : 3; 978 NEEDBITS(t + i) 979 DUMPBITS(t) 980 j += (uInt)b & inflate_mask[i]; 981 DUMPBITS(i) 982 i = s->sub.trees.index; 983 t = s->sub.trees.table; 984 if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || 985 (c == 16 && i < 1)) 986 { 987 s->mode = BADB; 988 z->msg = "invalid bit length repeat"; 989 r = Z_DATA_ERROR; 990 LEAVE 991 } 992 c = c == 16 ? s->sub.trees.blens[i - 1] : 0; 993 do { 994 s->sub.trees.blens[i++] = c; 995 } while (--j); 996 s->sub.trees.index = i; 997 } 998 } 999 inflate_trees_free(s->sub.trees.tb, z); 1000 s->sub.trees.tb = Z_NULL; 1001 { 1002 uInt bl, bd; 1003 inflate_huft *tl, *td; 1004 inflate_codes_statef *c; 1005 1006 bl = 9; /* must be <= 9 for lookahead assumptions */ 1007 bd = 6; /* must be <= 9 for lookahead assumptions */ 1008 t = s->sub.trees.table; 1009 t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), 1010 s->sub.trees.blens, &bl, &bd, &tl, &td, z); 1011 if (t != Z_OK) 1012 { 1013 if (t == (uInt)Z_DATA_ERROR) 1014 s->mode = BADB; 1015 r = t; 1016 LEAVE 1017 } 1018 Tracev((stderr, "inflate: trees ok\n")); 1019 if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) 1020 { 1021 inflate_trees_free(td, z); 1022 inflate_trees_free(tl, z); 1023 r = Z_MEM_ERROR; 1024 LEAVE 1025 } 1026 ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt)); 1027 s->sub.decode.codes = c; 1028 s->sub.decode.tl = tl; 1029 s->sub.decode.td = td; 1030 } 1031 s->mode = CODES; 1032 case CODES: 1033 UPDATE 1034 if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) 1035 return inflate_flush(s, z, r); 1036 r = Z_OK; 1037 inflate_codes_free(s->sub.decode.codes, z); 1038 inflate_trees_free(s->sub.decode.td, z); 1039 inflate_trees_free(s->sub.decode.tl, z); 1040 LOAD 1041 Tracev((stderr, "inflate: codes end, %lu total out\n", 1042 z->total_out + (q >= s->read ? q - s->read : 1043 (s->end - s->read) + (q - s->window)))); 1044 if (!s->last) 1045 { 1046 s->mode = TYPE; 1047 break; 1048 } 1049 if (k > 7) /* return unused byte, if any */ 1050 { 1051 Assert(k < 16, "inflate_codes grabbed too many bytes") 1052 k -= 8; 1053 n++; 1054 p--; /* can always return one */ 1055 } 1056 s->mode = DRY; 1057 case DRY: 1058 FLUSH 1059 if (s->read != s->write) 1060 LEAVE 1061 s->mode = DONEB; 1062 case DONEB: 1063 r = Z_STREAM_END; 1064 LEAVE 1065 case BADB: 1066 r = Z_DATA_ERROR; 1067 LEAVE 1068 default: 1069 r = Z_STREAM_ERROR; 1070 LEAVE 1071 } 1072} 1073 1074 1075local int inflate_blocks_free(s, z, c) 1076inflate_blocks_statef *s; 1077z_stream *z; 1078uLongf *c; 1079{ 1080 inflate_blocks_reset(s, z, c); 1081 ZFREE(z, s->window, s->end - s->window); 1082 ZFREE(z, s, sizeof(struct inflate_blocks_state)); 1083 Trace((stderr, "inflate: blocks freed\n")); 1084 return Z_OK; 1085} 1086 1087/* 1088 * This subroutine adds the data at next_in/avail_in to the output history 1089 * without performing any output. The output buffer must be "caught up"; 1090 * i.e. no pending output (hence s->read equals s->write), and the state must 1091 * be BLOCKS (i.e. we should be willing to see the start of a series of 1092 * BLOCKS). On exit, the output will also be caught up, and the checksum 1093 * will have been updated if need be. 1094 */ 1095local int inflate_addhistory(s, z) 1096inflate_blocks_statef *s; 1097z_stream *z; 1098{ 1099 uLong b; /* bit buffer */ /* NOT USED HERE */ 1100 uInt k; /* bits in bit buffer */ /* NOT USED HERE */ 1101 uInt t; /* temporary storage */ 1102 Bytef *p; /* input data pointer */ 1103 uInt n; /* bytes available there */ 1104 Bytef *q; /* output window write pointer */ 1105 uInt m; /* bytes to end of window or read pointer */ 1106 1107 if (s->read != s->write) 1108 return Z_STREAM_ERROR; 1109 if (s->mode != TYPE) 1110 return Z_DATA_ERROR; 1111 1112 /* we're ready to rock */ 1113 LOAD 1114 /* while there is input ready, copy to output buffer, moving 1115 * pointers as needed. 1116 */ 1117 while (n) { 1118 t = n; /* how many to do */ 1119 /* is there room until end of buffer? */ 1120 if (t > m) t = m; 1121 /* update check information */ 1122 if (s->checkfn != Z_NULL) 1123 s->check = (*s->checkfn)(s->check, q, t); 1124 zmemcpy(q, p, t); 1125 q += t; 1126 p += t; 1127 n -= t; 1128 z->total_out += t; 1129 s->read = q; /* drag read pointer forward */ 1130/* WRAP */ /* expand WRAP macro by hand to handle s->read */ 1131 if (q == s->end) { 1132 s->read = q = s->window; 1133 m = WAVAIL; 1134 } 1135 } 1136 UPDATE 1137 return Z_OK; 1138} 1139 1140 1141/* 1142 * At the end of a Deflate-compressed PPP packet, we expect to have seen 1143 * a `stored' block type value but not the (zero) length bytes. 1144 */ 1145local int inflate_packet_flush(s) 1146 inflate_blocks_statef *s; 1147{ 1148 if (s->mode != LENS) 1149 return Z_DATA_ERROR; 1150 s->mode = TYPE; 1151 return Z_OK; 1152} 1153 1154 1155/*+++++*/ 1156/* inftrees.c -- generate Huffman trees for efficient decoding 1157 * Copyright (C) 1995 Mark Adler 1158 * For conditions of distribution and use, see copyright notice in zlib.h 1159 */ 1160 1161/* simplify the use of the inflate_huft type with some defines */ 1162#define base more.Base 1163#define next more.Next 1164#define exop word.what.Exop 1165#define bits word.what.Bits 1166 1167 1168local int huft_build OF(( 1169 uIntf *, /* code lengths in bits */ 1170 uInt, /* number of codes */ 1171 uInt, /* number of "simple" codes */ 1172 uIntf *, /* list of base values for non-simple codes */ 1173 uIntf *, /* list of extra bits for non-simple codes */ 1174 inflate_huft * FAR*,/* result: starting table */ 1175 uIntf *, /* maximum lookup bits (returns actual) */ 1176 z_stream *)); /* for zalloc function */ 1177 1178local voidpf falloc OF(( 1179 voidpf, /* opaque pointer (not used) */ 1180 uInt, /* number of items */ 1181 uInt)); /* size of item */ 1182 1183local void ffree OF(( 1184 voidpf q, /* opaque pointer (not used) */ 1185 voidpf p, /* what to free (not used) */ 1186 uInt n)); /* number of bytes (not used) */ 1187 1188/* Tables for deflate from PKZIP's appnote.txt. */ 1189local uInt cplens[] = { /* Copy lengths for literal codes 257..285 */ 1190 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 1191 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 1192 /* actually lengths - 2; also see note #13 above about 258 */ 1193local uInt cplext[] = { /* Extra bits for literal codes 257..285 */ 1194 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 1195 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 192, 192}; /* 192==invalid */ 1196local uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */ 1197 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 1198 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 1199 8193, 12289, 16385, 24577}; 1200local uInt cpdext[] = { /* Extra bits for distance codes */ 1201 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 1202 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 1203 12, 12, 13, 13}; 1204 1205/* 1206 Huffman code decoding is performed using a multi-level table lookup. 1207 The fastest way to decode is to simply build a lookup table whose 1208 size is determined by the longest code. However, the time it takes 1209 to build this table can also be a factor if the data being decoded 1210 is not very long. The most common codes are necessarily the 1211 shortest codes, so those codes dominate the decoding time, and hence 1212 the speed. The idea is you can have a shorter table that decodes the 1213 shorter, more probable codes, and then point to subsidiary tables for 1214 the longer codes. The time it costs to decode the longer codes is 1215 then traded against the time it takes to make longer tables. 1216 1217 This results of this trade are in the variables lbits and dbits 1218 below. lbits is the number of bits the first level table for literal/ 1219 length codes can decode in one step, and dbits is the same thing for 1220 the distance codes. Subsequent tables are also less than or equal to 1221 those sizes. These values may be adjusted either when all of the 1222 codes are shorter than that, in which case the longest code length in 1223 bits is used, or when the shortest code is *longer* than the requested 1224 table size, in which case the length of the shortest code in bits is 1225 used. 1226 1227 There are two different values for the two tables, since they code a 1228 different number of possibilities each. The literal/length table 1229 codes 286 possible values, or in a flat code, a little over eight 1230 bits. The distance table codes 30 possible values, or a little less 1231 than five bits, flat. The optimum values for speed end up being 1232 about one bit more than those, so lbits is 8+1 and dbits is 5+1. 1233 The optimum values may differ though from machine to machine, and 1234 possibly even between compilers. Your mileage may vary. 1235 */ 1236 1237 1238/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ 1239#define BMAX 15 /* maximum bit length of any code */ 1240#define N_MAX 288 /* maximum number of codes in any set */ 1241 1242#ifdef DEBUG_ZLIB 1243 uInt inflate_hufts; 1244#endif 1245 1246local int huft_build(b, n, s, d, e, t, m, zs) 1247uIntf *b; /* code lengths in bits (all assumed <= BMAX) */ 1248uInt n; /* number of codes (assumed <= N_MAX) */ 1249uInt s; /* number of simple-valued codes (0..s-1) */ 1250uIntf *d; /* list of base values for non-simple codes */ 1251uIntf *e; /* list of extra bits for non-simple codes */ 1252inflate_huft * FAR *t; /* result: starting table */ 1253uIntf *m; /* maximum lookup bits, returns actual */ 1254z_stream *zs; /* for zalloc function */ 1255/* Given a list of code lengths and a maximum table size, make a set of 1256 tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR 1257 if the given code set is incomplete (the tables are still built in this 1258 case), Z_DATA_ERROR if the input is invalid (all zero length codes or an 1259 over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */ 1260{ 1261 1262 uInt a; /* counter for codes of length k */ 1263 uInt c[BMAX+1]; /* bit length count table */ 1264 uInt f; /* i repeats in table every f entries */ 1265 int g; /* maximum code length */ 1266 int h; /* table level */ 1267 register uInt i; /* counter, current code */ 1268 register uInt j; /* counter */ 1269 register int k; /* number of bits in current code */ 1270 int l; /* bits per table (returned in m) */ 1271 register uIntf *p; /* pointer into c[], b[], or v[] */ 1272 inflate_huft *q; /* points to current table */ 1273 struct inflate_huft_s r; /* table entry for structure assignment */ 1274 inflate_huft *u[BMAX]; /* table stack */ 1275 uInt v[N_MAX]; /* values in order of bit length */ 1276 register int w; /* bits before this table == (l * h) */ 1277 uInt x[BMAX+1]; /* bit offsets, then code stack */ 1278 uIntf *xp; /* pointer into x */ 1279 int y; /* number of dummy codes added */ 1280 uInt z; /* number of entries in current table */ 1281 1282 1283 /* Generate counts for each bit length */ 1284 p = c; 1285#define C0 *p++ = 0; 1286#define C2 C0 C0 C0 C0 1287#define C4 C2 C2 C2 C2 1288 C4 /* clear c[]--assume BMAX+1 is 16 */ 1289 p = b; i = n; 1290 do { 1291 c[*p++]++; /* assume all entries <= BMAX */ 1292 } while (--i); 1293 if (c[0] == n) /* null input--all zero length codes */ 1294 { 1295 *t = (inflate_huft *)Z_NULL; 1296 *m = 0; 1297 return Z_OK; 1298 } 1299 1300 1301 /* Find minimum and maximum length, bound *m by those */ 1302 l = *m; 1303 for (j = 1; j <= BMAX; j++) 1304 if (c[j]) 1305 break; 1306 k = j; /* minimum code length */ 1307 if ((uInt)l < j) 1308 l = j; 1309 for (i = BMAX; i; i--) 1310 if (c[i]) 1311 break; 1312 g = i; /* maximum code length */ 1313 if ((uInt)l > i) 1314 l = i; 1315 *m = l; 1316 1317 1318 /* Adjust last length count to fill out codes, if needed */ 1319 for (y = 1 << j; j < i; j++, y <<= 1) 1320 if ((y -= c[j]) < 0) 1321 return Z_DATA_ERROR; 1322 if ((y -= c[i]) < 0) 1323 return Z_DATA_ERROR; 1324 c[i] += y; 1325 1326 1327 /* Generate starting offsets into the value table for each length */ 1328 x[1] = j = 0; 1329 p = c + 1; xp = x + 2; 1330 while (--i) { /* note that i == g from above */ 1331 *xp++ = (j += *p++); 1332 } 1333 1334 1335 /* Make a table of values in order of bit lengths */ 1336 p = b; i = 0; 1337 do { 1338 if ((j = *p++) != 0) 1339 v[x[j]++] = i; 1340 } while (++i < n); 1341 1342 1343 /* Generate the Huffman codes and for each, make the table entries */ 1344 x[0] = i = 0; /* first Huffman code is zero */ 1345 p = v; /* grab values in bit order */ 1346 h = -1; /* no tables yet--level -1 */ 1347 w = -l; /* bits decoded == (l * h) */ 1348 u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ 1349 q = (inflate_huft *)Z_NULL; /* ditto */ 1350 z = 0; /* ditto */ 1351 1352 /* go through the bit lengths (k already is bits in shortest code) */ 1353 for (; k <= g; k++) 1354 { 1355 a = c[k]; 1356 while (a--) 1357 { 1358 /* here i is the Huffman code of length k bits for value *p */ 1359 /* make tables up to required level */ 1360 while (k > w + l) 1361 { 1362 h++; 1363 w += l; /* previous table always l bits */ 1364 1365 /* compute minimum size table less than or equal to l bits */ 1366 z = (z = g - w) > (uInt)l ? l : z; /* table size upper limit */ 1367 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 1368 { /* too few codes for k-w bit table */ 1369 f -= a + 1; /* deduct codes from patterns left */ 1370 xp = c + k; 1371 if (j < z) 1372 while (++j < z) /* try smaller tables up to z bits */ 1373 { 1374 if ((f <<= 1) <= *++xp) 1375 break; /* enough codes to use up j bits */ 1376 f -= *xp; /* else deduct codes from patterns */ 1377 } 1378 } 1379 z = 1 << j; /* table entries for j-bit table */ 1380 1381 /* allocate and link in new table */ 1382 if ((q = (inflate_huft *)ZALLOC 1383 (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) 1384 { 1385 if (h) 1386 inflate_trees_free(u[0], zs); 1387 return Z_MEM_ERROR; /* not enough memory */ 1388 } 1389 q->word.Nalloc = z + 1; 1390#ifdef DEBUG_ZLIB 1391 inflate_hufts += z + 1; 1392#endif 1393 *t = q + 1; /* link to list for huft_free() */ 1394 *(t = &(q->next)) = Z_NULL; 1395 u[h] = ++q; /* table starts after link */ 1396 1397 /* connect to last table, if there is one */ 1398 if (h) 1399 { 1400 x[h] = i; /* save pattern for backing up */ 1401 r.bits = (Byte)l; /* bits to dump before this table */ 1402 r.exop = (Byte)j; /* bits in this table */ 1403 r.next = q; /* pointer to this table */ 1404 j = i >> (w - l); /* (get around Turbo C bug) */ 1405 u[h-1][j] = r; /* connect to last table */ 1406 } 1407 } 1408 1409 /* set up table entry in r */ 1410 r.bits = (Byte)(k - w); 1411 if (p >= v + n) 1412 r.exop = 128 + 64; /* out of values--invalid code */ 1413 else if (*p < s) 1414 { 1415 r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ 1416 r.base = *p++; /* simple code is just the value */ 1417 } 1418 else 1419 { 1420 r.exop = (Byte)e[*p - s] + 16 + 64; /* non-simple--look up in lists */ 1421 r.base = d[*p++ - s]; 1422 } 1423 1424 /* fill code-like entries with r */ 1425 f = 1 << (k - w); 1426 for (j = i >> w; j < z; j += f) 1427 q[j] = r; 1428 1429 /* backwards increment the k-bit code i */ 1430 for (j = 1 << (k - 1); i & j; j >>= 1) 1431 i ^= j; 1432 i ^= j; 1433 1434 /* backup over finished tables */ 1435 while ((i & ((1 << w) - 1)) != x[h]) 1436 { 1437 h--; /* don't need to update q */ 1438 w -= l; 1439 } 1440 } 1441 } 1442 1443 1444 /* Return Z_BUF_ERROR if we were given an incomplete table */ 1445 return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; 1446} 1447 1448 1449local int inflate_trees_bits(c, bb, tb, z) 1450uIntf *c; /* 19 code lengths */ 1451uIntf *bb; /* bits tree desired/actual depth */ 1452inflate_huft * FAR *tb; /* bits tree result */ 1453z_stream *z; /* for zfree function */ 1454{ 1455 int r; 1456 1457 r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z); 1458 if (r == Z_DATA_ERROR) 1459 z->msg = "oversubscribed dynamic bit lengths tree"; 1460 else if (r == Z_BUF_ERROR) 1461 { 1462 inflate_trees_free(*tb, z); 1463 z->msg = "incomplete dynamic bit lengths tree"; 1464 r = Z_DATA_ERROR; 1465 } 1466 return r; 1467} 1468 1469 1470local int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z) 1471uInt nl; /* number of literal/length codes */ 1472uInt nd; /* number of distance codes */ 1473uIntf *c; /* that many (total) code lengths */ 1474uIntf *bl; /* literal desired/actual bit depth */ 1475uIntf *bd; /* distance desired/actual bit depth */ 1476inflate_huft * FAR *tl; /* literal/length tree result */ 1477inflate_huft * FAR *td; /* distance tree result */ 1478z_stream *z; /* for zfree function */ 1479{ 1480 int r; 1481 1482 /* build literal/length tree */ 1483 if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK) 1484 { 1485 if (r == Z_DATA_ERROR) 1486 z->msg = "oversubscribed literal/length tree"; 1487 else if (r == Z_BUF_ERROR) 1488 { 1489 inflate_trees_free(*tl, z); 1490 z->msg = "incomplete literal/length tree"; 1491 r = Z_DATA_ERROR; 1492 } 1493 return r; 1494 } 1495 1496 /* build distance tree */ 1497 if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK) 1498 { 1499 if (r == Z_DATA_ERROR) 1500 z->msg = "oversubscribed literal/length tree"; 1501 else if (r == Z_BUF_ERROR) { 1502#ifdef PKZIP_BUG_WORKAROUND 1503 r = Z_OK; 1504 } 1505#else 1506 inflate_trees_free(*td, z); 1507 z->msg = "incomplete literal/length tree"; 1508 r = Z_DATA_ERROR; 1509 } 1510 inflate_trees_free(*tl, z); 1511 return r; 1512#endif 1513 } 1514 1515 /* done */ 1516 return Z_OK; 1517} 1518 1519 1520/* build fixed tables only once--keep them here */ 1521local int fixed_lock = 0; 1522local int fixed_built = 0; 1523#define FIXEDH 530 /* number of hufts used by fixed tables */ 1524local uInt fixed_left = FIXEDH; 1525local inflate_huft fixed_mem[FIXEDH]; 1526local uInt fixed_bl; 1527local uInt fixed_bd; 1528local inflate_huft *fixed_tl; 1529local inflate_huft *fixed_td; 1530 1531 1532local voidpf falloc(q, n, s) 1533voidpf q; /* opaque pointer (not used) */ 1534uInt n; /* number of items */ 1535uInt s; /* size of item */ 1536{ 1537 Assert(s == sizeof(inflate_huft) && n <= fixed_left, 1538 "inflate_trees falloc overflow"); 1539 if (q) s++; /* to make some compilers happy */ 1540 fixed_left -= n; 1541 return (voidpf)(fixed_mem + fixed_left); 1542} 1543 1544 1545local void ffree(q, p, n) 1546voidpf q; 1547voidpf p; 1548uInt n; 1549{ 1550 Assert(0, "inflate_trees ffree called!"); 1551 if (q) q = p; /* to make some compilers happy */ 1552} 1553 1554 1555local int inflate_trees_fixed(bl, bd, tl, td) 1556uIntf *bl; /* literal desired/actual bit depth */ 1557uIntf *bd; /* distance desired/actual bit depth */ 1558inflate_huft * FAR *tl; /* literal/length tree result */ 1559inflate_huft * FAR *td; /* distance tree result */ 1560{ 1561 /* build fixed tables if not built already--lock out other instances */ 1562 while (++fixed_lock > 1) 1563 fixed_lock--; 1564 if (!fixed_built) 1565 { 1566 int k; /* temporary variable */ 1567 unsigned c[288]; /* length list for huft_build */ 1568 z_stream z; /* for falloc function */ 1569 1570 /* set up fake z_stream for memory routines */ 1571 z.zalloc = falloc; 1572 z.zfree = ffree; 1573 z.opaque = Z_NULL; 1574 1575 /* literal table */ 1576 for (k = 0; k < 144; k++) 1577 c[k] = 8; 1578 for (; k < 256; k++) 1579 c[k] = 9; 1580 for (; k < 280; k++) 1581 c[k] = 7; 1582 for (; k < 288; k++) 1583 c[k] = 8; 1584 fixed_bl = 7; 1585 huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z); 1586 1587 /* distance table */ 1588 for (k = 0; k < 30; k++) 1589 c[k] = 5; 1590 fixed_bd = 5; 1591 huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z); 1592 1593 /* done */ 1594 fixed_built = 1; 1595 } 1596 fixed_lock--; 1597 *bl = fixed_bl; 1598 *bd = fixed_bd; 1599 *tl = fixed_tl; 1600 *td = fixed_td; 1601 return Z_OK; 1602} 1603 1604 1605local int inflate_trees_free(t, z) 1606inflate_huft *t; /* table to free */ 1607z_stream *z; /* for zfree function */ 1608/* Free the malloc'ed tables built by huft_build(), which makes a linked 1609 list of the tables it made, with the links in a dummy first entry of 1610 each table. */ 1611{ 1612 register inflate_huft *p, *q; 1613 1614 /* Go through linked list, freeing from the malloced (t[-1]) address. */ 1615 p = t; 1616 while (p != Z_NULL) 1617 { 1618 q = (--p)->next; 1619 ZFREE(z, p, p->word.Nalloc * sizeof(inflate_huft)); 1620 p = q; 1621 } 1622 return Z_OK; 1623} 1624 1625/*+++++*/ 1626/* infcodes.c -- process literals and length/distance pairs 1627 * Copyright (C) 1995 Mark Adler 1628 * For conditions of distribution and use, see copyright notice in zlib.h 1629 */ 1630 1631/* simplify the use of the inflate_huft type with some defines */ 1632#define base more.Base 1633#define next more.Next 1634#define exop word.what.Exop 1635#define bits word.what.Bits 1636 1637/* inflate codes private state */ 1638struct inflate_codes_state { 1639 1640 /* mode */ 1641 enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 1642 START, /* x: set up for LEN */ 1643 LEN, /* i: get length/literal/eob next */ 1644 LENEXT, /* i: getting length extra (have base) */ 1645 DIST, /* i: get distance next */ 1646 DISTEXT, /* i: getting distance extra */ 1647 COPY, /* o: copying bytes in window, waiting for space */ 1648 LIT, /* o: got literal, waiting for output space */ 1649 WASH, /* o: got eob, possibly still output waiting */ 1650 END, /* x: got eob and all data flushed */ 1651 BADCODE} /* x: got error */ 1652 mode; /* current inflate_codes mode */ 1653 1654 /* mode dependent information */ 1655 uInt len; 1656 union { 1657 struct { 1658 inflate_huft *tree; /* pointer into tree */ 1659 uInt need; /* bits needed */ 1660 } code; /* if LEN or DIST, where in tree */ 1661 uInt lit; /* if LIT, literal */ 1662 struct { 1663 uInt get; /* bits to get for extra */ 1664 uInt dist; /* distance back to copy from */ 1665 } copy; /* if EXT or COPY, where and how much */ 1666 } sub; /* submode */ 1667 1668 /* mode independent information */ 1669 Byte lbits; /* ltree bits decoded per branch */ 1670 Byte dbits; /* dtree bits decoder per branch */ 1671 inflate_huft *ltree; /* literal/length/eob tree */ 1672 inflate_huft *dtree; /* distance tree */ 1673 1674}; 1675 1676 1677local inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z) 1678uInt bl, bd; 1679inflate_huft *tl, *td; 1680z_stream *z; 1681{ 1682 inflate_codes_statef *c; 1683 1684 if ((c = (inflate_codes_statef *) 1685 ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL) 1686 { 1687 c->mode = START; 1688 c->lbits = (Byte)bl; 1689 c->dbits = (Byte)bd; 1690 c->ltree = tl; 1691 c->dtree = td; 1692 Tracev((stderr, "inflate: codes new\n")); 1693 } 1694 return c; 1695} 1696 1697 1698local int inflate_codes(s, z, r) 1699inflate_blocks_statef *s; 1700z_stream *z; 1701int r; 1702{ 1703 uInt j; /* temporary storage */ 1704 inflate_huft *t; /* temporary pointer */ 1705 uInt e; /* extra bits or operation */ 1706 uLong b; /* bit buffer */ 1707 uInt k; /* bits in bit buffer */ 1708 Bytef *p; /* input data pointer */ 1709 uInt n; /* bytes available there */ 1710 Bytef *q; /* output window write pointer */ 1711 uInt m; /* bytes to end of window or read pointer */ 1712 Bytef *f; /* pointer to copy strings from */ 1713 inflate_codes_statef *c = s->sub.decode.codes; /* codes state */ 1714 1715 /* copy input/output information to locals (UPDATE macro restores) */ 1716 LOAD 1717 1718 /* process input and output based on current state */ 1719 while (1) switch (c->mode) 1720 { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 1721 case START: /* x: set up for LEN */ 1722#ifndef SLOW 1723 if (m >= 258 && n >= 10) 1724 { 1725 UPDATE 1726 r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); 1727 LOAD 1728 if (r != Z_OK) 1729 { 1730 c->mode = r == Z_STREAM_END ? WASH : BADCODE; 1731 break; 1732 } 1733 } 1734#endif /* !SLOW */ 1735 c->sub.code.need = c->lbits; 1736 c->sub.code.tree = c->ltree; 1737 c->mode = LEN; 1738 case LEN: /* i: get length/literal/eob next */ 1739 j = c->sub.code.need; 1740 NEEDBITS(j) 1741 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 1742 DUMPBITS(t->bits) 1743 e = (uInt)(t->exop); 1744 if (e == 0) /* literal */ 1745 { 1746 c->sub.lit = t->base; 1747 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 1748 "inflate: literal '%c'\n" : 1749 "inflate: literal 0x%02x\n", t->base)); 1750 c->mode = LIT; 1751 break; 1752 } 1753 if (e & 16) /* length */ 1754 { 1755 c->sub.copy.get = e & 15; 1756 c->len = t->base; 1757 c->mode = LENEXT; 1758 break; 1759 } 1760 if ((e & 64) == 0) /* next table */ 1761 { 1762 c->sub.code.need = e; 1763 c->sub.code.tree = t->next; 1764 break; 1765 } 1766 if (e & 32) /* end of block */ 1767 { 1768 Tracevv((stderr, "inflate: end of block\n")); 1769 c->mode = WASH; 1770 break; 1771 } 1772 c->mode = BADCODE; /* invalid code */ 1773 z->msg = "invalid literal/length code"; 1774 r = Z_DATA_ERROR; 1775 LEAVE 1776 case LENEXT: /* i: getting length extra (have base) */ 1777 j = c->sub.copy.get; 1778 NEEDBITS(j) 1779 c->len += (uInt)b & inflate_mask[j]; 1780 DUMPBITS(j) 1781 c->sub.code.need = c->dbits; 1782 c->sub.code.tree = c->dtree; 1783 Tracevv((stderr, "inflate: length %u\n", c->len)); 1784 c->mode = DIST; 1785 case DIST: /* i: get distance next */ 1786 j = c->sub.code.need; 1787 NEEDBITS(j) 1788 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 1789 DUMPBITS(t->bits) 1790 e = (uInt)(t->exop); 1791 if (e & 16) /* distance */ 1792 { 1793 c->sub.copy.get = e & 15; 1794 c->sub.copy.dist = t->base; 1795 c->mode = DISTEXT; 1796 break; 1797 } 1798 if ((e & 64) == 0) /* next table */ 1799 { 1800 c->sub.code.need = e; 1801 c->sub.code.tree = t->next; 1802 break; 1803 } 1804 c->mode = BADCODE; /* invalid code */ 1805 z->msg = "invalid distance code"; 1806 r = Z_DATA_ERROR; 1807 LEAVE 1808 case DISTEXT: /* i: getting distance extra */ 1809 j = c->sub.copy.get; 1810 NEEDBITS(j) 1811 c->sub.copy.dist += (uInt)b & inflate_mask[j]; 1812 DUMPBITS(j) 1813 Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist)); 1814 c->mode = COPY; 1815 case COPY: /* o: copying bytes in window, waiting for space */ 1816#ifndef __TURBOC__ /* Turbo C bug for following expression */ 1817 f = (uInt)(q - s->window) < c->sub.copy.dist ? 1818 s->end - (c->sub.copy.dist - (q - s->window)) : 1819 q - c->sub.copy.dist; 1820#else 1821 f = q - c->sub.copy.dist; 1822 if ((uInt)(q - s->window) < c->sub.copy.dist) 1823 f = s->end - (c->sub.copy.dist - (q - s->window)); 1824#endif 1825 while (c->len) 1826 { 1827 NEEDOUT 1828 OUTBYTE(*f++) 1829 if (f == s->end) 1830 f = s->window; 1831 c->len--; 1832 } 1833 c->mode = START; 1834 break; 1835 case LIT: /* o: got literal, waiting for output space */ 1836 NEEDOUT 1837 OUTBYTE(c->sub.lit) 1838 c->mode = START; 1839 break; 1840 case WASH: /* o: got eob, possibly more output */ 1841 FLUSH 1842 if (s->read != s->write) 1843 LEAVE 1844 c->mode = END; 1845 case END: 1846 r = Z_STREAM_END; 1847 LEAVE 1848 case BADCODE: /* x: got error */ 1849 r = Z_DATA_ERROR; 1850 LEAVE 1851 default: 1852 r = Z_STREAM_ERROR; 1853 LEAVE 1854 } 1855} 1856 1857 1858local void inflate_codes_free(c, z) 1859inflate_codes_statef *c; 1860z_stream *z; 1861{ 1862 ZFREE(z, c, sizeof(struct inflate_codes_state)); 1863 Tracev((stderr, "inflate: codes free\n")); 1864} 1865 1866/*+++++*/ 1867/* inflate_util.c -- data and routines common to blocks and codes 1868 * Copyright (C) 1995 Mark Adler 1869 * For conditions of distribution and use, see copyright notice in zlib.h 1870 */ 1871 1872/* copy as much as possible from the sliding window to the output area */ 1873local int inflate_flush(s, z, r) 1874inflate_blocks_statef *s; 1875z_stream *z; 1876int r; 1877{ 1878 uInt n; 1879 Bytef *p, *q; 1880 1881 /* local copies of source and destination pointers */ 1882 p = z->next_out; 1883 q = s->read; 1884 1885 /* compute number of bytes to copy as far as end of window */ 1886 n = (uInt)((q <= s->write ? s->write : s->end) - q); 1887 if (n > z->avail_out) n = z->avail_out; 1888 if (n && r == Z_BUF_ERROR) r = Z_OK; 1889 1890 /* update counters */ 1891 z->avail_out -= n; 1892 z->total_out += n; 1893 1894 /* update check information */ 1895 if (s->checkfn != Z_NULL) 1896 s->check = (*s->checkfn)(s->check, q, n); 1897 1898 /* copy as far as end of window */ 1899 zmemcpy(p, q, n); 1900 p += n; 1901 q += n; 1902 1903 /* see if more to copy at beginning of window */ 1904 if (q == s->end) 1905 { 1906 /* wrap pointers */ 1907 q = s->window; 1908 if (s->write == s->end) 1909 s->write = s->window; 1910 1911 /* compute bytes to copy */ 1912 n = (uInt)(s->write - q); 1913 if (n > z->avail_out) n = z->avail_out; 1914 if (n && r == Z_BUF_ERROR) r = Z_OK; 1915 1916 /* update counters */ 1917 z->avail_out -= n; 1918 z->total_out += n; 1919 1920 /* update check information */ 1921 if (s->checkfn != Z_NULL) 1922 s->check = (*s->checkfn)(s->check, q, n); 1923 1924 /* copy */ 1925 zmemcpy(p, q, n); 1926 p += n; 1927 q += n; 1928 } 1929 1930 /* update pointers */ 1931 z->next_out = p; 1932 s->read = q; 1933 1934 /* done */ 1935 return r; 1936} 1937 1938 1939/*+++++*/ 1940/* inffast.c -- process literals and length/distance pairs fast 1941 * Copyright (C) 1995 Mark Adler 1942 * For conditions of distribution and use, see copyright notice in zlib.h 1943 */ 1944 1945/* simplify the use of the inflate_huft type with some defines */ 1946#define base more.Base 1947#define next more.Next 1948#define exop word.what.Exop 1949#define bits word.what.Bits 1950 1951/* macros for bit input with no checking and for returning unused bytes */ 1952#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} 1953#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;} 1954 1955/* Called with number of bytes left to write in window at least 258 1956 (the maximum string length) and number of input bytes available 1957 at least ten. The ten bytes are six bytes for the longest length/ 1958 distance pair plus four bytes for overloading the bit buffer. */ 1959 1960local int inflate_fast(bl, bd, tl, td, s, z) 1961uInt bl, bd; 1962inflate_huft *tl, *td; 1963inflate_blocks_statef *s; 1964z_stream *z; 1965{ 1966 inflate_huft *t; /* temporary pointer */ 1967 uInt e; /* extra bits or operation */ 1968 uLong b; /* bit buffer */ 1969 uInt k; /* bits in bit buffer */ 1970 Bytef *p; /* input data pointer */ 1971 uInt n; /* bytes available there */ 1972 Bytef *q; /* output window write pointer */ 1973 uInt m; /* bytes to end of window or read pointer */ 1974 uInt ml; /* mask for literal/length tree */ 1975 uInt md; /* mask for distance tree */ 1976 uInt c; /* bytes to copy */ 1977 uInt d; /* distance back to copy from */ 1978 Bytef *r; /* copy source pointer */ 1979 1980 /* load input, output, bit values */ 1981 LOAD 1982 1983 /* initialize masks */ 1984 ml = inflate_mask[bl]; 1985 md = inflate_mask[bd]; 1986 1987 /* do until not enough input or output space for fast loop */ 1988 do { /* assume called with m >= 258 && n >= 10 */ 1989 /* get literal/length code */ 1990 GRABBITS(20) /* max bits for literal/length code */ 1991 if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) 1992 { 1993 DUMPBITS(t->bits) 1994 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 1995 "inflate: * literal '%c'\n" : 1996 "inflate: * literal 0x%02x\n", t->base)); 1997 *q++ = (Byte)t->base; 1998 m--; 1999 continue; 2000 } 2001 do { 2002 DUMPBITS(t->bits) 2003 if (e & 16) 2004 { 2005 /* get extra bits for length */ 2006 e &= 15; 2007 c = t->base + ((uInt)b & inflate_mask[e]); 2008 DUMPBITS(e) 2009 Tracevv((stderr, "inflate: * length %u\n", c)); 2010 2011 /* decode distance base of block to copy */ 2012 GRABBITS(15); /* max bits for distance code */ 2013 e = (t = td + ((uInt)b & md))->exop; 2014 do { 2015 DUMPBITS(t->bits) 2016 if (e & 16) 2017 { 2018 /* get extra bits to add to distance base */ 2019 e &= 15; 2020 GRABBITS(e) /* get extra bits (up to 13) */ 2021 d = t->base + ((uInt)b & inflate_mask[e]); 2022 DUMPBITS(e) 2023 Tracevv((stderr, "inflate: * distance %u\n", d)); 2024 2025 /* do the copy */ 2026 m -= c; 2027 if ((uInt)(q - s->window) >= d) /* offset before dest */ 2028 { /* just copy */ 2029 r = q - d; 2030 *q++ = *r++; c--; /* minimum count is three, */ 2031 *q++ = *r++; c--; /* so unroll loop a little */ 2032 } 2033 else /* else offset after destination */ 2034 { 2035 e = d - (q - s->window); /* bytes from offset to end */ 2036 r = s->end - e; /* pointer to offset */ 2037 if (c > e) /* if source crosses, */ 2038 { 2039 c -= e; /* copy to end of window */ 2040 do { 2041 *q++ = *r++; 2042 } while (--e); 2043 r = s->window; /* copy rest from start of window */ 2044 } 2045 } 2046 do { /* copy all or what's left */ 2047 *q++ = *r++; 2048 } while (--c); 2049 break; 2050 } 2051 else if ((e & 64) == 0) 2052 e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop; 2053 else 2054 { 2055 z->msg = "invalid distance code"; 2056 UNGRAB 2057 UPDATE 2058 return Z_DATA_ERROR; 2059 } 2060 } while (1); 2061 break; 2062 } 2063 if ((e & 64) == 0) 2064 { 2065 if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0) 2066 { 2067 DUMPBITS(t->bits) 2068 Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 2069 "inflate: * literal '%c'\n" : 2070 "inflate: * literal 0x%02x\n", t->base)); 2071 *q++ = (Byte)t->base; 2072 m--; 2073 break; 2074 } 2075 } 2076 else if (e & 32) 2077 { 2078 Tracevv((stderr, "inflate: * end of block\n")); 2079 UNGRAB 2080 UPDATE 2081 return Z_STREAM_END; 2082 } 2083 else 2084 { 2085 z->msg = "invalid literal/length code"; 2086 UNGRAB 2087 UPDATE 2088 return Z_DATA_ERROR; 2089 } 2090 } while (1); 2091 } while (m >= 258 && n >= 10); 2092 2093 /* not enough input or output--restore pointers and return */ 2094 UNGRAB 2095 UPDATE 2096 return Z_OK; 2097} 2098 2099 2100/*+++++*/ 2101/* zutil.c -- target dependent utility functions for the compression library 2102 * Copyright (C) 1995 Jean-loup Gailly. 2103 * For conditions of distribution and use, see copyright notice in zlib.h 2104 */ 2105 2106/* From: zutil.c,v 1.8 1995/05/03 17:27:12 jloup Exp */ 2107 2108char *zlib_version = ZLIB_VERSION; 2109 2110char *z_errmsg[] = { 2111"stream end", /* Z_STREAM_END 1 */ 2112"", /* Z_OK 0 */ 2113"file error", /* Z_ERRNO (-1) */ 2114"stream error", /* Z_STREAM_ERROR (-2) */ 2115"data error", /* Z_DATA_ERROR (-3) */ 2116"insufficient memory", /* Z_MEM_ERROR (-4) */ 2117"buffer error", /* Z_BUF_ERROR (-5) */ 2118""}; 2119 2120 2121/*+++++*/ 2122/* adler32.c -- compute the Adler-32 checksum of a data stream 2123 * Copyright (C) 1995 Mark Adler 2124 * For conditions of distribution and use, see copyright notice in zlib.h 2125 */ 2126 2127/* From: adler32.c,v 1.6 1995/05/03 17:27:08 jloup Exp */ 2128 2129#define BASE 65521L /* largest prime smaller than 65536 */ 2130#define NMAX 5552 2131/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 2132 2133#define DO1(buf) {s1 += *buf++; s2 += s1;} 2134#define DO2(buf) DO1(buf); DO1(buf); 2135#define DO4(buf) DO2(buf); DO2(buf); 2136#define DO8(buf) DO4(buf); DO4(buf); 2137#define DO16(buf) DO8(buf); DO8(buf); 2138 2139/* ========================================================================= */ 2140uLong adler32(adler, buf, len) 2141 uLong adler; 2142 Bytef *buf; 2143 uInt len; 2144{ 2145 unsigned long s1 = adler & 0xffff; 2146 unsigned long s2 = (adler >> 16) & 0xffff; 2147 int k; 2148 2149 if (buf == Z_NULL) return 1L; 2150 2151 while (len > 0) { 2152 k = len < NMAX ? len : NMAX; 2153 len -= k; 2154 while (k >= 16) { 2155 DO16(buf); 2156 k -= 16; 2157 } 2158 if (k != 0) do { 2159 DO1(buf); 2160 } while (--k); 2161 s1 %= BASE; 2162 s2 %= BASE; 2163 } 2164 return (s2 << 16) | s1; 2165} 2166