Annotation of sys/net/zlib.c, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: zlib.c,v 1.12 2003/12/10 07:22:42 itojun Exp $ */
! 2: /* $NetBSD: zlib.c,v 1.2 1996/03/16 23:55:40 christos Exp $ */
! 3:
! 4: /*
! 5: * This file is derived from various .h and .c files from the zlib-0.95
! 6: * distribution by Jean-loup Gailly and Mark Adler, with some additions
! 7: * by Paul Mackerras to aid in implementing Deflate compression and
! 8: * decompression for PPP packets. See zlib.h for conditions of
! 9: * distribution and use.
! 10: *
! 11: * Changes that have been made include:
! 12: * - changed functions not used outside this file to "local"
! 13: * - added minCompression parameter to deflateInit2
! 14: * - added Z_PACKET_FLUSH (see zlib.h for details)
! 15: * - added inflateIncomp
! 16: */
! 17:
! 18:
! 19: /*+++++*/
! 20: /* zutil.h -- internal interface and configuration of the compression library
! 21: * Copyright (C) 1995 Jean-loup Gailly.
! 22: * For conditions of distribution and use, see copyright notice in zlib.h
! 23: */
! 24:
! 25: /* WARNING: this file should *not* be used by applications. It is
! 26: part of the implementation of the compression library and is
! 27: subject to change. Applications should only use zlib.h.
! 28: */
! 29:
! 30: /* From: zutil.h,v 1.9 1995/05/03 17:27:12 jloup Exp */
! 31:
! 32: #define _Z_UTIL_H
! 33:
! 34: #include "zlib.h"
! 35:
! 36: #include <sys/param.h>
! 37: #include <sys/types.h>
! 38: #ifdef _STANDALONE
! 39: #include <stand.h>
! 40: #else
! 41: #include <sys/systm.h>
! 42: #endif
! 43:
! 44: #ifndef local
! 45: # define local static
! 46: #endif
! 47: /* compile with -Dlocal if your debugger can't find static symbols */
! 48:
! 49: #define FAR
! 50:
! 51: typedef unsigned char uch;
! 52: typedef uch FAR uchf;
! 53: typedef unsigned short ush;
! 54: typedef ush FAR ushf;
! 55: typedef unsigned long ulg;
! 56:
! 57: extern char *z_errmsg[]; /* indexed by 1-zlib_error */
! 58:
! 59: #define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err)
! 60: /* To be used only when the state is known to be valid */
! 61:
! 62: #ifndef NULL
! 63: #define NULL ((void *) 0)
! 64: #endif
! 65:
! 66: /* common constants */
! 67:
! 68: #define DEFLATED 8
! 69:
! 70: #ifndef DEF_WBITS
! 71: # define DEF_WBITS MAX_WBITS
! 72: #endif
! 73: /* default windowBits for decompression. MAX_WBITS is for compression only */
! 74:
! 75: #if MAX_MEM_LEVEL >= 8
! 76: # define DEF_MEM_LEVEL 8
! 77: #else
! 78: # define DEF_MEM_LEVEL MAX_MEM_LEVEL
! 79: #endif
! 80: /* default memLevel */
! 81:
! 82: #define STORED_BLOCK 0
! 83: #define STATIC_TREES 1
! 84: #define DYN_TREES 2
! 85: /* The three kinds of block type */
! 86:
! 87: #define MIN_MATCH 3
! 88: #define MAX_MATCH 258
! 89: /* The minimum and maximum match lengths */
! 90:
! 91: /* functions */
! 92:
! 93: #if defined(KERNEL) || defined(_KERNEL)
! 94: # define zmemcpy(d, s, n) bcopy((s), (d), (n))
! 95: # define zmemzero bzero
! 96: #else
! 97: #if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY)
! 98: # define HAVE_MEMCPY
! 99: #endif
! 100: #ifdef HAVE_MEMCPY
! 101: # define zmemcpy memcpy
! 102: # define zmemzero(dest, len) memset(dest, 0, len)
! 103: #else
! 104: extern void zmemcpy OF((Bytef* dest, Bytef* source, uInt len));
! 105: extern void zmemzero OF((Bytef* dest, uInt len));
! 106: #endif
! 107: #endif
! 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:
! 131: typedef 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: #ifndef NO_DEFLATE
! 143:
! 144: /* deflate.h -- internal compression state
! 145: * Copyright (C) 1995 Jean-loup Gailly
! 146: * For conditions of distribution and use, see copyright notice in zlib.h
! 147: */
! 148:
! 149: /* WARNING: this file should *not* be used by applications. It is
! 150: part of the implementation of the compression library and is
! 151: subject to change. Applications should only use zlib.h.
! 152: */
! 153:
! 154:
! 155: /*+++++*/
! 156: /* From: deflate.h,v 1.5 1995/05/03 17:27:09 jloup Exp */
! 157:
! 158: /* ===========================================================================
! 159: * Internal compression state.
! 160: */
! 161:
! 162: /* Data type */
! 163: #define BINARY 0
! 164: #define ASCII 1
! 165: #define UNKNOWN 2
! 166:
! 167: #define LENGTH_CODES 29
! 168: /* number of length codes, not counting the special END_BLOCK code */
! 169:
! 170: #define LITERALS 256
! 171: /* number of literal bytes 0..255 */
! 172:
! 173: #define L_CODES (LITERALS+1+LENGTH_CODES)
! 174: /* number of Literal or Length codes, including the END_BLOCK code */
! 175:
! 176: #define D_CODES 30
! 177: /* number of distance codes */
! 178:
! 179: #define BL_CODES 19
! 180: /* number of codes used to transfer the bit lengths */
! 181:
! 182: #define HEAP_SIZE (2*L_CODES+1)
! 183: /* maximum heap size */
! 184:
! 185: #define MAX_BITS 15
! 186: /* All codes must not exceed MAX_BITS bits */
! 187:
! 188: #define INIT_STATE 42
! 189: #define BUSY_STATE 113
! 190: #define FLUSH_STATE 124
! 191: #define FINISH_STATE 666
! 192: /* Stream status */
! 193:
! 194:
! 195: /* Data structure describing a single value and its code string. */
! 196: typedef struct ct_data_s {
! 197: union {
! 198: ush freq; /* frequency count */
! 199: ush code; /* bit string */
! 200: } fc;
! 201: union {
! 202: ush dad; /* father node in Huffman tree */
! 203: ush len; /* length of bit string */
! 204: } dl;
! 205: } FAR ct_data;
! 206:
! 207: #define Freq fc.freq
! 208: #define Code fc.code
! 209: #define Dad dl.dad
! 210: #define Len dl.len
! 211:
! 212: typedef struct static_tree_desc_s static_tree_desc;
! 213:
! 214: typedef struct tree_desc_s {
! 215: ct_data *dyn_tree; /* the dynamic tree */
! 216: int max_code; /* largest code with non zero frequency */
! 217: const static_tree_desc *stat_desc; /* the corresponding static tree */
! 218: } FAR tree_desc;
! 219:
! 220: typedef ush Pos;
! 221: typedef Pos FAR Posf;
! 222: typedef unsigned IPos;
! 223:
! 224: /* A Pos is an index in the character window. We use short instead of int to
! 225: * save space in the various tables. IPos is used only for parameter passing.
! 226: */
! 227:
! 228: typedef struct deflate_state {
! 229: z_stream *strm; /* pointer back to this zlib stream */
! 230: int status; /* as the name implies */
! 231: Bytef *pending_buf; /* output still pending */
! 232: Bytef *pending_out; /* next pending byte to output to the stream */
! 233: int pending; /* nb of bytes in the pending buffer */
! 234: uLong adler; /* adler32 of uncompressed data */
! 235: int noheader; /* suppress zlib header and adler32 */
! 236: Byte data_type; /* UNKNOWN, BINARY or ASCII */
! 237: Byte method; /* STORED (for zip only) or DEFLATED */
! 238: int minCompr; /* min size decrease for Z_FLUSH_NOSTORE */
! 239:
! 240: /* used by deflate.c: */
! 241:
! 242: uInt w_size; /* LZ77 window size (32K by default) */
! 243: uInt w_bits; /* log2(w_size) (8..16) */
! 244: uInt w_mask; /* w_size - 1 */
! 245:
! 246: Bytef *window;
! 247: /* Sliding window. Input bytes are read into the second half of the window,
! 248: * and move to the first half later to keep a dictionary of at least wSize
! 249: * bytes. With this organization, matches are limited to a distance of
! 250: * wSize-MAX_MATCH bytes, but this ensures that IO is always
! 251: * performed with a length multiple of the block size. Also, it limits
! 252: * the window size to 64K, which is quite useful on MSDOS.
! 253: * To do: use the user input buffer as sliding window.
! 254: */
! 255:
! 256: ulg window_size;
! 257: /* Actual size of window: 2*wSize, except when the user input buffer
! 258: * is directly used as sliding window.
! 259: */
! 260:
! 261: Posf *prev;
! 262: /* Link to older string with same hash index. To limit the size of this
! 263: * array to 64K, this link is maintained only for the last 32K strings.
! 264: * An index in this array is thus a window index modulo 32K.
! 265: */
! 266:
! 267: Posf *head; /* Heads of the hash chains or NIL. */
! 268:
! 269: uInt ins_h; /* hash index of string to be inserted */
! 270: uInt hash_size; /* number of elements in hash table */
! 271: uInt hash_bits; /* log2(hash_size) */
! 272: uInt hash_mask; /* hash_size-1 */
! 273:
! 274: uInt hash_shift;
! 275: /* Number of bits by which ins_h must be shifted at each input
! 276: * step. It must be such that after MIN_MATCH steps, the oldest
! 277: * byte no longer takes part in the hash key, that is:
! 278: * hash_shift * MIN_MATCH >= hash_bits
! 279: */
! 280:
! 281: long block_start;
! 282: /* Window position at the beginning of the current output block. Gets
! 283: * negative when the window is moved backwards.
! 284: */
! 285:
! 286: uInt match_length; /* length of best match */
! 287: IPos prev_match; /* previous match */
! 288: int match_available; /* set if previous match exists */
! 289: uInt strstart; /* start of string to insert */
! 290: uInt match_start; /* start of matching string */
! 291: uInt lookahead; /* number of valid bytes ahead in window */
! 292:
! 293: uInt prev_length;
! 294: /* Length of the best match at previous step. Matches not greater than this
! 295: * are discarded. This is used in the lazy match evaluation.
! 296: */
! 297:
! 298: uInt max_chain_length;
! 299: /* To speed up deflation, hash chains are never searched beyond this
! 300: * length. A higher limit improves compression ratio but degrades the
! 301: * speed.
! 302: */
! 303:
! 304: uInt max_lazy_match;
! 305: /* Attempt to find a better match only when the current match is strictly
! 306: * smaller than this value. This mechanism is used only for compression
! 307: * levels >= 4.
! 308: */
! 309: # define max_insert_length max_lazy_match
! 310: /* Insert new strings in the hash table only if the match length is not
! 311: * greater than this length. This saves time but degrades compression.
! 312: * max_insert_length is used only for compression levels <= 3.
! 313: */
! 314:
! 315: int level; /* compression level (1..9) */
! 316: int strategy; /* favor or force Huffman coding*/
! 317:
! 318: uInt good_match;
! 319: /* Use a faster search when the previous match is longer than this */
! 320:
! 321: int nice_match; /* Stop searching when current match exceeds this */
! 322:
! 323: /* used by trees.c: */
! 324: /* Didn't use ct_data typedef below to supress compiler warning */
! 325: struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */
! 326: struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
! 327: struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */
! 328:
! 329: struct tree_desc_s l_desc; /* desc. for literal tree */
! 330: struct tree_desc_s d_desc; /* desc. for distance tree */
! 331: struct tree_desc_s bl_desc; /* desc. for bit length tree */
! 332:
! 333: ush bl_count[MAX_BITS+1];
! 334: /* number of codes at each bit length for an optimal tree */
! 335:
! 336: int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
! 337: int heap_len; /* number of elements in the heap */
! 338: int heap_max; /* element of largest frequency */
! 339: /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
! 340: * The same heap array is used to build all trees.
! 341: */
! 342:
! 343: uch depth[2*L_CODES+1];
! 344: /* Depth of each subtree used as tie breaker for trees of equal frequency
! 345: */
! 346:
! 347: uchf *l_buf; /* buffer for literals or lengths */
! 348:
! 349: uInt lit_bufsize;
! 350: /* Size of match buffer for literals/lengths. There are 4 reasons for
! 351: * limiting lit_bufsize to 64K:
! 352: * - frequencies can be kept in 16 bit counters
! 353: * - if compression is not successful for the first block, all input
! 354: * data is still in the window so we can still emit a stored block even
! 355: * when input comes from standard input. (This can also be done for
! 356: * all blocks if lit_bufsize is not greater than 32K.)
! 357: * - if compression is not successful for a file smaller than 64K, we can
! 358: * even emit a stored file instead of a stored block (saving 5 bytes).
! 359: * This is applicable only for zip (not gzip or zlib).
! 360: * - creating new Huffman trees less frequently may not provide fast
! 361: * adaptation to changes in the input data statistics. (Take for
! 362: * example a binary file with poorly compressible code followed by
! 363: * a highly compressible string table.) Smaller buffer sizes give
! 364: * fast adaptation but have of course the overhead of transmitting
! 365: * trees more frequently.
! 366: * - I can't count above 4
! 367: */
! 368:
! 369: uInt last_lit; /* running index in l_buf */
! 370:
! 371: ushf *d_buf;
! 372: /* Buffer for distances. To simplify the code, d_buf and l_buf have
! 373: * the same number of elements. To use different lengths, an extra flag
! 374: * array would be necessary.
! 375: */
! 376:
! 377: ulg opt_len; /* bit length of current block with optimal trees */
! 378: ulg static_len; /* bit length of current block with static trees */
! 379: ulg compressed_len; /* total bit length of compressed file */
! 380: uInt matches; /* number of string matches in current block */
! 381: int last_eob_len; /* bit length of EOB code for last block */
! 382:
! 383: #ifdef DEBUG_ZLIB
! 384: ulg bits_sent; /* bit length of the compressed data */
! 385: #endif
! 386:
! 387: ush bi_buf;
! 388: /* Output buffer. bits are inserted starting at the bottom (least
! 389: * significant bits).
! 390: */
! 391: int bi_valid;
! 392: /* Number of valid bits in bi_buf. All bits above the last valid bit
! 393: * are always zero.
! 394: */
! 395:
! 396: uInt blocks_in_packet;
! 397: /* Number of blocks produced since the last time Z_PACKET_FLUSH
! 398: * was used.
! 399: */
! 400:
! 401: } FAR deflate_state;
! 402:
! 403: /* Output a byte on the stream.
! 404: * IN assertion: there is enough room in pending_buf.
! 405: */
! 406: #define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
! 407:
! 408:
! 409: #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
! 410: /* Minimum amount of lookahead, except at the end of the input file.
! 411: * See deflate.c for comments about the MIN_MATCH+1.
! 412: */
! 413:
! 414: #define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)
! 415: /* In order to simplify the code, particularly on 16 bit machines, match
! 416: * distances are limited to MAX_DIST instead of WSIZE.
! 417: */
! 418:
! 419: /* in trees.c */
! 420: local void ct_init OF((deflate_state *s));
! 421: local int ct_tally OF((deflate_state *s, int dist, int lc));
! 422: local ulg ct_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
! 423: int flush));
! 424: local void ct_align OF((deflate_state *s));
! 425: local void ct_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
! 426: int eof));
! 427: local void ct_stored_type_only OF((deflate_state *s));
! 428:
! 429: /*+++++*/
! 430: /* deflate.c -- compress data using the deflation algorithm
! 431: * Copyright (C) 1995 Jean-loup Gailly.
! 432: * For conditions of distribution and use, see copyright notice in zlib.h
! 433: */
! 434:
! 435: /*
! 436: * ALGORITHM
! 437: *
! 438: * The "deflation" process depends on being able to identify portions
! 439: * of the input text which are identical to earlier input (within a
! 440: * sliding window trailing behind the input currently being processed).
! 441: *
! 442: * The most straightforward technique turns out to be the fastest for
! 443: * most input files: try all possible matches and select the longest.
! 444: * The key feature of this algorithm is that insertions into the string
! 445: * dictionary are very simple and thus fast, and deletions are avoided
! 446: * completely. Insertions are performed at each input character, whereas
! 447: * string matches are performed only when the previous match ends. So it
! 448: * is preferable to spend more time in matches to allow very fast string
! 449: * insertions and avoid deletions. The matching algorithm for small
! 450: * strings is inspired from that of Rabin & Karp. A brute force approach
! 451: * is used to find longer strings when a small match has been found.
! 452: * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
! 453: * (by Leonid Broukhis).
! 454: * A previous version of this file used a more sophisticated algorithm
! 455: * (by Fiala and Greene) which is guaranteed to run in linear amortized
! 456: * time, but has a larger average cost, uses more memory and is patented.
! 457: * However the F&G algorithm may be faster for some highly redundant
! 458: * files if the parameter max_chain_length (described below) is too large.
! 459: *
! 460: * ACKNOWLEDGEMENTS
! 461: *
! 462: * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
! 463: * I found it in 'freeze' written by Leonid Broukhis.
! 464: * Thanks to many people for bug reports and testing.
! 465: *
! 466: * REFERENCES
! 467: *
! 468: * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
! 469: * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
! 470: *
! 471: * A description of the Rabin and Karp algorithm is given in the book
! 472: * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
! 473: *
! 474: * Fiala,E.R., and Greene,D.H.
! 475: * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
! 476: *
! 477: */
! 478:
! 479: /* From: deflate.c,v 1.8 1995/05/03 17:27:08 jloup Exp */
! 480:
! 481: #if 0
! 482: local char zlib_copyright[] = " deflate Copyright 1995 Jean-loup Gailly ";
! 483: #endif
! 484: /*
! 485: If you use the zlib library in a product, an acknowledgment is welcome
! 486: in the documentation of your product. If for some reason you cannot
! 487: include such an acknowledgment, I would appreciate that you keep this
! 488: copyright string in the executable of your product.
! 489: */
! 490:
! 491: #define NIL 0
! 492: /* Tail of hash chains */
! 493:
! 494: #ifndef TOO_FAR
! 495: # define TOO_FAR 4096
! 496: #endif
! 497: /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
! 498:
! 499: #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
! 500: /* Minimum amount of lookahead, except at the end of the input file.
! 501: * See deflate.c for comments about the MIN_MATCH+1.
! 502: */
! 503:
! 504: /* Values for max_lazy_match, good_match and max_chain_length, depending on
! 505: * the desired pack level (0..9). The values given below have been tuned to
! 506: * exclude worst case performance for pathological files. Better values may be
! 507: * found for specific files.
! 508: */
! 509:
! 510: typedef struct config_s {
! 511: ush good_length; /* reduce lazy search above this match length */
! 512: ush max_lazy; /* do not perform lazy search above this match length */
! 513: ush nice_length; /* quit search above this match length */
! 514: ush max_chain;
! 515: } config;
! 516:
! 517: local config configuration_table[10] = {
! 518: /* good lazy nice chain */
! 519: /* 0 */ {0, 0, 0, 0}, /* store only */
! 520: /* 1 */ {4, 4, 8, 4}, /* maximum speed, no lazy matches */
! 521: /* 2 */ {4, 5, 16, 8},
! 522: /* 3 */ {4, 6, 32, 32},
! 523:
! 524: /* 4 */ {4, 4, 16, 16}, /* lazy matches */
! 525: /* 5 */ {8, 16, 32, 32},
! 526: /* 6 */ {8, 16, 128, 128},
! 527: /* 7 */ {8, 32, 128, 256},
! 528: /* 8 */ {32, 128, 258, 1024},
! 529: /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
! 530:
! 531: /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
! 532: * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
! 533: * meaning.
! 534: */
! 535:
! 536: #define EQUAL 0
! 537: /* result of memcmp for equal strings */
! 538:
! 539: /* ===========================================================================
! 540: * Prototypes for local functions.
! 541: */
! 542:
! 543: local void fill_window OF((deflate_state *s));
! 544: local int deflate_fast OF((deflate_state *s, int flush));
! 545: local int deflate_slow OF((deflate_state *s, int flush));
! 546: local void lm_init OF((deflate_state *s));
! 547: local int longest_match OF((deflate_state *s, IPos cur_match));
! 548: local void putShortMSB OF((deflate_state *s, uInt b));
! 549: local void flush_pending OF((z_stream *strm));
! 550: local int read_buf OF((z_stream *strm, charf *buf, unsigned size));
! 551: #ifdef ASMV
! 552: void match_init OF((void)); /* asm code initialization */
! 553: #endif
! 554:
! 555: #ifdef DEBUG_ZLIB
! 556: local void check_match OF((deflate_state *s, IPos start, IPos match,
! 557: int length));
! 558: #endif
! 559:
! 560:
! 561: /* ===========================================================================
! 562: * Update a hash value with the given input byte
! 563: * IN assertion: all calls to to UPDATE_HASH are made with consecutive
! 564: * input characters, so that a running hash key can be computed from the
! 565: * previous key instead of complete recalculation each time.
! 566: */
! 567: #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
! 568:
! 569:
! 570: /* ===========================================================================
! 571: * Insert string str in the dictionary and set match_head to the previous head
! 572: * of the hash chain (the most recent string with same hash key). Return
! 573: * the previous length of the hash chain.
! 574: * IN assertion: all calls to to INSERT_STRING are made with consecutive
! 575: * input characters and the first MIN_MATCH bytes of str are valid
! 576: * (except for the last MIN_MATCH-1 bytes of the input file).
! 577: */
! 578: #define INSERT_STRING(s, str, match_head) \
! 579: (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
! 580: s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
! 581: s->head[s->ins_h] = (str))
! 582:
! 583: /* ===========================================================================
! 584: * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
! 585: * prev[] will be initialized on the fly.
! 586: */
! 587: #define CLEAR_HASH(s) \
! 588: s->head[s->hash_size-1] = NIL; \
! 589: zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
! 590:
! 591: /* ========================================================================= */
! 592: int deflateInit (strm, level)
! 593: z_stream *strm;
! 594: int level;
! 595: {
! 596: return deflateInit2 (strm, level, DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
! 597: 0, 0);
! 598: /* To do: ignore strm->next_in if we use it as window */
! 599: }
! 600:
! 601: /* ========================================================================= */
! 602: int deflateInit2 (strm, level, method, windowBits, memLevel,
! 603: strategy, minCompression)
! 604: z_stream *strm;
! 605: int level;
! 606: int method;
! 607: int windowBits;
! 608: int memLevel;
! 609: int strategy;
! 610: int minCompression;
! 611: {
! 612: deflate_state *s;
! 613: int noheader = 0;
! 614:
! 615: if (strm == Z_NULL) return Z_STREAM_ERROR;
! 616:
! 617: strm->msg = Z_NULL;
! 618: /* if (strm->zalloc == Z_NULL) strm->zalloc = zcalloc; */
! 619: /* if (strm->zfree == Z_NULL) strm->zfree = zcfree; */
! 620:
! 621: if (level == Z_DEFAULT_COMPRESSION) level = 6;
! 622:
! 623: if (windowBits < 0) { /* undocumented feature: suppress zlib header */
! 624: noheader = 1;
! 625: windowBits = -windowBits;
! 626: }
! 627: if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != DEFLATED ||
! 628: windowBits < 8 || windowBits > 15 || level < 1 || level > 9) {
! 629: return Z_STREAM_ERROR;
! 630: }
! 631: s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
! 632: if (s == Z_NULL) return Z_MEM_ERROR;
! 633: strm->state = (struct internal_state FAR *)s;
! 634: s->strm = strm;
! 635:
! 636: s->noheader = noheader;
! 637: s->w_bits = windowBits;
! 638: s->w_size = 1 << s->w_bits;
! 639: s->w_mask = s->w_size - 1;
! 640:
! 641: s->hash_bits = memLevel + 7;
! 642: s->hash_size = 1 << s->hash_bits;
! 643: s->hash_mask = s->hash_size - 1;
! 644: s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
! 645:
! 646: s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
! 647: s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
! 648: s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
! 649:
! 650: s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
! 651:
! 652: s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 2*sizeof(ush));
! 653:
! 654: if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
! 655: s->pending_buf == Z_NULL) {
! 656: strm->msg = z_errmsg[1-Z_MEM_ERROR];
! 657: deflateEnd (strm);
! 658: return Z_MEM_ERROR;
! 659: }
! 660: s->d_buf = (ushf *) &(s->pending_buf[s->lit_bufsize]);
! 661: s->l_buf = (uchf *) &(s->pending_buf[3*s->lit_bufsize]);
! 662: /* We overlay pending_buf and d_buf+l_buf. This works since the average
! 663: * output size for (length,distance) codes is <= 32 bits (worst case
! 664: * is 15+15+13=33).
! 665: */
! 666:
! 667: s->level = level;
! 668: s->strategy = strategy;
! 669: s->method = (Byte)method;
! 670: s->minCompr = minCompression;
! 671: s->blocks_in_packet = 0;
! 672:
! 673: return deflateReset(strm);
! 674: }
! 675:
! 676: /* ========================================================================= */
! 677: int deflateReset (strm)
! 678: z_stream *strm;
! 679: {
! 680: deflate_state *s;
! 681:
! 682: if (strm == Z_NULL || strm->state == Z_NULL ||
! 683: strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR;
! 684:
! 685: strm->total_in = strm->total_out = 0;
! 686: strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
! 687: strm->data_type = Z_UNKNOWN;
! 688:
! 689: s = (deflate_state *)strm->state;
! 690: s->pending = 0;
! 691: s->pending_out = s->pending_buf;
! 692:
! 693: if (s->noheader < 0) {
! 694: s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
! 695: }
! 696: s->status = s->noheader ? BUSY_STATE : INIT_STATE;
! 697: s->adler = 1;
! 698:
! 699: ct_init(s);
! 700: lm_init(s);
! 701:
! 702: return Z_OK;
! 703: }
! 704:
! 705: /* =========================================================================
! 706: * Put a short in the pending buffer. The 16-bit value is put in MSB order.
! 707: * IN assertion: the stream state is correct and there is enough room in
! 708: * pending_buf.
! 709: */
! 710: local void putShortMSB (s, b)
! 711: deflate_state *s;
! 712: uInt b;
! 713: {
! 714: put_byte(s, (Byte)(b >> 8));
! 715: put_byte(s, (Byte)(b & 0xff));
! 716: }
! 717:
! 718: /* =========================================================================
! 719: * Flush as much pending output as possible.
! 720: */
! 721: local void flush_pending(strm)
! 722: z_stream *strm;
! 723: {
! 724: deflate_state *state = (deflate_state *) strm->state;
! 725: unsigned len = state->pending;
! 726:
! 727: if (len > strm->avail_out) len = strm->avail_out;
! 728: if (len == 0) return;
! 729:
! 730: if (strm->next_out != NULL) {
! 731: zmemcpy(strm->next_out, state->pending_out, len);
! 732: strm->next_out += len;
! 733: }
! 734: state->pending_out += len;
! 735: strm->total_out += len;
! 736: strm->avail_out -= len;
! 737: state->pending -= len;
! 738: if (state->pending == 0) {
! 739: state->pending_out = state->pending_buf;
! 740: }
! 741: }
! 742:
! 743: /* ========================================================================= */
! 744: int deflate (strm, flush)
! 745: z_stream *strm;
! 746: int flush;
! 747: {
! 748: deflate_state *state = (deflate_state *) strm->state;
! 749:
! 750: if (strm == Z_NULL || state == Z_NULL) return Z_STREAM_ERROR;
! 751:
! 752: if (strm->next_in == Z_NULL && strm->avail_in != 0) {
! 753: ERR_RETURN(strm, Z_STREAM_ERROR);
! 754: }
! 755: if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
! 756:
! 757: state->strm = strm; /* just in case */
! 758:
! 759: /* Write the zlib header */
! 760: if (state->status == INIT_STATE) {
! 761:
! 762: uInt header = (DEFLATED + ((state->w_bits-8)<<4)) << 8;
! 763: uInt level_flags = (state->level-1) >> 1;
! 764:
! 765: if (level_flags > 3) level_flags = 3;
! 766: header |= (level_flags << 6);
! 767: header += 31 - (header % 31);
! 768:
! 769: state->status = BUSY_STATE;
! 770: putShortMSB(state, header);
! 771: }
! 772:
! 773: /* Flush as much pending output as possible */
! 774: if (state->pending != 0) {
! 775: flush_pending(strm);
! 776: if (strm->avail_out == 0) return Z_OK;
! 777: }
! 778:
! 779: /* If we came back in here to get the last output from
! 780: * a previous flush, we're done for now.
! 781: */
! 782: if (state->status == FLUSH_STATE) {
! 783: state->status = BUSY_STATE;
! 784: if (flush != Z_NO_FLUSH && flush != Z_FINISH)
! 785: return Z_OK;
! 786: }
! 787:
! 788: /* User must not provide more input after the first FINISH: */
! 789: if (state->status == FINISH_STATE && strm->avail_in != 0) {
! 790: ERR_RETURN(strm, Z_BUF_ERROR);
! 791: }
! 792:
! 793: /* Start a new block or continue the current one.
! 794: */
! 795: if (strm->avail_in != 0 || state->lookahead != 0 ||
! 796: (flush == Z_FINISH && state->status != FINISH_STATE)) {
! 797: int quit;
! 798:
! 799: if (flush == Z_FINISH) {
! 800: state->status = FINISH_STATE;
! 801: }
! 802: if (state->level <= 3) {
! 803: quit = deflate_fast(state, flush);
! 804: } else {
! 805: quit = deflate_slow(state, flush);
! 806: }
! 807: if (quit || strm->avail_out == 0)
! 808: return Z_OK;
! 809: /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
! 810: * of deflate should use the same flush parameter to make sure
! 811: * that the flush is complete. So we don't have to output an
! 812: * empty block here, this will be done at next call. This also
! 813: * ensures that for a very small output buffer, we emit at most
! 814: * one empty block.
! 815: */
! 816: }
! 817:
! 818: /* If a flush was requested, we have a little more to output now. */
! 819: if (flush != Z_NO_FLUSH && flush != Z_FINISH
! 820: && state->status != FINISH_STATE) {
! 821: switch (flush) {
! 822: case Z_PARTIAL_FLUSH:
! 823: ct_align(state);
! 824: break;
! 825: case Z_PACKET_FLUSH:
! 826: /* Output just the 3-bit `stored' block type value,
! 827: but not a zero length. */
! 828: ct_stored_type_only(state);
! 829: break;
! 830: default:
! 831: ct_stored_block(state, (char*)0, 0L, 0);
! 832: /* For a full flush, this empty block will be recognized
! 833: * as a special marker by inflate_sync().
! 834: */
! 835: if (flush == Z_FULL_FLUSH) {
! 836: CLEAR_HASH(state); /* forget history */
! 837: }
! 838: }
! 839: flush_pending(strm);
! 840: if (strm->avail_out == 0) {
! 841: /* We'll have to come back to get the rest of the output;
! 842: * this ensures we don't output a second zero-length stored
! 843: * block (or whatever).
! 844: */
! 845: state->status = FLUSH_STATE;
! 846: return Z_OK;
! 847: }
! 848: }
! 849:
! 850: Assert(strm->avail_out > 0, "bug2");
! 851:
! 852: if (flush != Z_FINISH) return Z_OK;
! 853: if (state->noheader) return Z_STREAM_END;
! 854:
! 855: /* Write the zlib trailer (adler32) */
! 856: putShortMSB(state, (uInt)(state->adler >> 16));
! 857: putShortMSB(state, (uInt)(state->adler & 0xffff));
! 858: flush_pending(strm);
! 859: /* If avail_out is zero, the application will call deflate again
! 860: * to flush the rest.
! 861: */
! 862: state->noheader = -1; /* write the trailer only once! */
! 863: return state->pending != 0 ? Z_OK : Z_STREAM_END;
! 864: }
! 865:
! 866: /* ========================================================================= */
! 867: int deflateEnd (strm)
! 868: z_stream *strm;
! 869: {
! 870: deflate_state *state = (deflate_state *) strm->state;
! 871:
! 872: if (strm == Z_NULL || state == Z_NULL) return Z_STREAM_ERROR;
! 873:
! 874: TRY_FREE(strm, state->window, state->w_size * 2 * sizeof(Byte));
! 875: TRY_FREE(strm, state->prev, state->w_size * sizeof(Pos));
! 876: TRY_FREE(strm, state->head, state->hash_size * sizeof(Pos));
! 877: TRY_FREE(strm, state->pending_buf, state->lit_bufsize * 2 * sizeof(ush));
! 878:
! 879: ZFREE(strm, state, sizeof(deflate_state));
! 880: strm->state = Z_NULL;
! 881:
! 882: return Z_OK;
! 883: }
! 884:
! 885: /* ===========================================================================
! 886: * Read a new buffer from the current input stream, update the adler32
! 887: * and total number of bytes read.
! 888: */
! 889: local int read_buf(strm, buf, size)
! 890: z_stream *strm;
! 891: charf *buf;
! 892: unsigned size;
! 893: {
! 894: unsigned len = strm->avail_in;
! 895: deflate_state *state = (deflate_state *) strm->state;
! 896:
! 897: if (len > size) len = size;
! 898: if (len == 0) return 0;
! 899:
! 900: strm->avail_in -= len;
! 901:
! 902: if (!state->noheader) {
! 903: state->adler = adler32(state->adler, strm->next_in, len);
! 904: }
! 905: zmemcpy(buf, strm->next_in, len);
! 906: strm->next_in += len;
! 907: strm->total_in += len;
! 908:
! 909: return (int)len;
! 910: }
! 911:
! 912: /* ===========================================================================
! 913: * Initialize the "longest match" routines for a new zlib stream
! 914: */
! 915: local void lm_init (s)
! 916: deflate_state *s;
! 917: {
! 918: s->window_size = (ulg)2L*s->w_size;
! 919:
! 920: CLEAR_HASH(s);
! 921:
! 922: /* Set the default configuration parameters:
! 923: */
! 924: s->max_lazy_match = configuration_table[s->level].max_lazy;
! 925: s->good_match = configuration_table[s->level].good_length;
! 926: s->nice_match = configuration_table[s->level].nice_length;
! 927: s->max_chain_length = configuration_table[s->level].max_chain;
! 928:
! 929: s->strstart = 0;
! 930: s->block_start = 0L;
! 931: s->lookahead = 0;
! 932: s->match_length = MIN_MATCH-1;
! 933: s->match_available = 0;
! 934: s->ins_h = 0;
! 935: #ifdef ASMV
! 936: match_init(); /* initialize the asm code */
! 937: #endif
! 938: }
! 939:
! 940: /* ===========================================================================
! 941: * Set match_start to the longest match starting at the given string and
! 942: * return its length. Matches shorter or equal to prev_length are discarded,
! 943: * in which case the result is equal to prev_length and match_start is
! 944: * garbage.
! 945: * IN assertions: cur_match is the head of the hash chain for the current
! 946: * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
! 947: */
! 948: #ifndef ASMV
! 949: /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
! 950: * match.S. The code will be functionally equivalent.
! 951: */
! 952: local int longest_match(s, cur_match)
! 953: deflate_state *s;
! 954: IPos cur_match; /* current match */
! 955: {
! 956: unsigned chain_length = s->max_chain_length;/* max hash chain length */
! 957: Bytef *scan = s->window + s->strstart; /* current string */
! 958: Bytef *match; /* matched string */
! 959: int len; /* length of current match */
! 960: int best_len = s->prev_length; /* best match length so far */
! 961: IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
! 962: s->strstart - (IPos)MAX_DIST(s) : NIL;
! 963: /* Stop when cur_match becomes <= limit. To simplify the code,
! 964: * we prevent matches with the string of window index 0.
! 965: */
! 966: Posf *prev = s->prev;
! 967: uInt wmask = s->w_mask;
! 968:
! 969: #ifdef UNALIGNED_OK
! 970: /* Compare two bytes at a time. Note: this is not always beneficial.
! 971: * Try with and without -DUNALIGNED_OK to check.
! 972: */
! 973: Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
! 974: ush scan_start = *(ushf*)scan;
! 975: ush scan_end = *(ushf*)(scan+best_len-1);
! 976: #else
! 977: Bytef *strend = s->window + s->strstart + MAX_MATCH;
! 978: Byte scan_end1 = scan[best_len-1];
! 979: Byte scan_end = scan[best_len];
! 980: #endif
! 981:
! 982: /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
! 983: * It is easy to get rid of this optimization if necessary.
! 984: */
! 985: Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
! 986:
! 987: /* Do not waste too much time if we already have a good match: */
! 988: if (s->prev_length >= s->good_match) {
! 989: chain_length >>= 2;
! 990: }
! 991: Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
! 992:
! 993: do {
! 994: Assert(cur_match < s->strstart, "no future");
! 995: match = s->window + cur_match;
! 996:
! 997: /* Skip to next match if the match length cannot increase
! 998: * or if the match length is less than 2:
! 999: */
! 1000: #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
! 1001: /* This code assumes sizeof(unsigned short) == 2. Do not use
! 1002: * UNALIGNED_OK if your compiler uses a different size.
! 1003: */
! 1004: if (*(ushf*)(match+best_len-1) != scan_end ||
! 1005: *(ushf*)match != scan_start) continue;
! 1006:
! 1007: /* It is not necessary to compare scan[2] and match[2] since they are
! 1008: * always equal when the other bytes match, given that the hash keys
! 1009: * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
! 1010: * strstart+3, +5, ... up to strstart+257. We check for insufficient
! 1011: * lookahead only every 4th comparison; the 128th check will be made
! 1012: * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
! 1013: * necessary to put more guard bytes at the end of the window, or
! 1014: * to check more often for insufficient lookahead.
! 1015: */
! 1016: Assert(scan[2] == match[2], "scan[2]?");
! 1017: scan++, match++;
! 1018: do {
! 1019: } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
! 1020: *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
! 1021: *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
! 1022: *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
! 1023: scan < strend);
! 1024: /* The funny "do {}" generates better code on most compilers */
! 1025:
! 1026: /* Here, scan <= window+strstart+257 */
! 1027: Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
! 1028: if (*scan == *match) scan++;
! 1029:
! 1030: len = (MAX_MATCH - 1) - (int)(strend-scan);
! 1031: scan = strend - (MAX_MATCH-1);
! 1032:
! 1033: #else /* UNALIGNED_OK */
! 1034:
! 1035: if (match[best_len] != scan_end ||
! 1036: match[best_len-1] != scan_end1 ||
! 1037: *match != *scan ||
! 1038: *++match != scan[1]) continue;
! 1039:
! 1040: /* The check at best_len-1 can be removed because it will be made
! 1041: * again later. (This heuristic is not always a win.)
! 1042: * It is not necessary to compare scan[2] and match[2] since they
! 1043: * are always equal when the other bytes match, given that
! 1044: * the hash keys are equal and that HASH_BITS >= 8.
! 1045: */
! 1046: scan += 2, match++;
! 1047: Assert(*scan == *match, "match[2]?");
! 1048:
! 1049: /* We check for insufficient lookahead only every 8th comparison;
! 1050: * the 256th check will be made at strstart+258.
! 1051: */
! 1052: do {
! 1053: } while (*++scan == *++match && *++scan == *++match &&
! 1054: *++scan == *++match && *++scan == *++match &&
! 1055: *++scan == *++match && *++scan == *++match &&
! 1056: *++scan == *++match && *++scan == *++match &&
! 1057: scan < strend);
! 1058:
! 1059: Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
! 1060:
! 1061: len = MAX_MATCH - (int)(strend - scan);
! 1062: scan = strend - MAX_MATCH;
! 1063:
! 1064: #endif /* UNALIGNED_OK */
! 1065:
! 1066: if (len > best_len) {
! 1067: s->match_start = cur_match;
! 1068: best_len = len;
! 1069: if (len >= s->nice_match) break;
! 1070: #ifdef UNALIGNED_OK
! 1071: scan_end = *(ushf*)(scan+best_len-1);
! 1072: #else
! 1073: scan_end1 = scan[best_len-1];
! 1074: scan_end = scan[best_len];
! 1075: #endif
! 1076: }
! 1077: } while ((cur_match = prev[cur_match & wmask]) > limit
! 1078: && --chain_length != 0);
! 1079:
! 1080: return best_len;
! 1081: }
! 1082: #endif /* ASMV */
! 1083:
! 1084: #ifdef DEBUG_ZLIB
! 1085: /* ===========================================================================
! 1086: * Check that the match at match_start is indeed a match.
! 1087: */
! 1088: local void check_match(s, start, match, length)
! 1089: deflate_state *s;
! 1090: IPos start, match;
! 1091: int length;
! 1092: {
! 1093: /* check that the match is indeed a match */
! 1094: if (memcmp((charf *)s->window + match,
! 1095: (charf *)s->window + start, length) != EQUAL) {
! 1096: fprintf(stderr,
! 1097: " start %u, match %u, length %d\n",
! 1098: start, match, length);
! 1099: do { fprintf(stderr, "%c%c", s->window[match++],
! 1100: s->window[start++]); } while (--length != 0);
! 1101: z_error("invalid match");
! 1102: }
! 1103: if (verbose > 1) {
! 1104: fprintf(stderr,"\\[%d,%d]", start-match, length);
! 1105: do { putc(s->window[start++], stderr); } while (--length != 0);
! 1106: }
! 1107: }
! 1108: #else
! 1109: # define check_match(s, start, match, length)
! 1110: #endif
! 1111:
! 1112: /* ===========================================================================
! 1113: * Fill the window when the lookahead becomes insufficient.
! 1114: * Updates strstart and lookahead.
! 1115: *
! 1116: * IN assertion: lookahead < MIN_LOOKAHEAD
! 1117: * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
! 1118: * At least one byte has been read, or avail_in == 0; reads are
! 1119: * performed for at least two bytes (required for the zip translate_eol
! 1120: * option -- not supported here).
! 1121: */
! 1122: local void fill_window(s)
! 1123: deflate_state *s;
! 1124: {
! 1125: unsigned n, m;
! 1126: Posf *p;
! 1127: unsigned more; /* Amount of free space at the end of the window. */
! 1128: uInt wsize = s->w_size;
! 1129:
! 1130: do {
! 1131: more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
! 1132:
! 1133: /* Deal with !@#$% 64K limit: */
! 1134: if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
! 1135: more = wsize;
! 1136: } else if (more == (unsigned)(-1)) {
! 1137: /* Very unlikely, but possible on 16 bit machine if strstart == 0
! 1138: * and lookahead == 1 (input done one byte at time)
! 1139: */
! 1140: more--;
! 1141:
! 1142: /* If the window is almost full and there is insufficient lookahead,
! 1143: * move the upper half to the lower one to make room in the upper half.
! 1144: */
! 1145: } else if (s->strstart >= wsize+MAX_DIST(s)) {
! 1146:
! 1147: /* By the IN assertion, the window is not empty so we can't confuse
! 1148: * more == 0 with more == 64K on a 16 bit machine.
! 1149: */
! 1150: zmemcpy((charf *)s->window, (charf *)s->window+wsize,
! 1151: (unsigned)wsize);
! 1152: s->match_start -= wsize;
! 1153: s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
! 1154:
! 1155: s->block_start -= (long) wsize;
! 1156:
! 1157: /* Slide the hash table (could be avoided with 32 bit values
! 1158: at the expense of memory usage):
! 1159: */
! 1160: n = s->hash_size;
! 1161: p = &s->head[n];
! 1162: do {
! 1163: m = *--p;
! 1164: *p = (Pos)(m >= wsize ? m-wsize : NIL);
! 1165: } while (--n);
! 1166:
! 1167: n = wsize;
! 1168: p = &s->prev[n];
! 1169: do {
! 1170: m = *--p;
! 1171: *p = (Pos)(m >= wsize ? m-wsize : NIL);
! 1172: /* If n is not on any hash chain, prev[n] is garbage but
! 1173: * its value will never be used.
! 1174: */
! 1175: } while (--n);
! 1176:
! 1177: more += wsize;
! 1178: }
! 1179: if (s->strm->avail_in == 0) return;
! 1180:
! 1181: /* If there was no sliding:
! 1182: * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
! 1183: * more == window_size - lookahead - strstart
! 1184: * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
! 1185: * => more >= window_size - 2*WSIZE + 2
! 1186: * In the BIG_MEM or MMAP case (not yet supported),
! 1187: * window_size == input_size + MIN_LOOKAHEAD &&
! 1188: * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
! 1189: * Otherwise, window_size == 2*WSIZE so more >= 2.
! 1190: * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
! 1191: */
! 1192: Assert(more >= 2, "more < 2");
! 1193:
! 1194: n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead,
! 1195: more);
! 1196: s->lookahead += n;
! 1197:
! 1198: /* Initialize the hash value now that we have some input: */
! 1199: if (s->lookahead >= MIN_MATCH) {
! 1200: s->ins_h = s->window[s->strstart];
! 1201: UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
! 1202: #if MIN_MATCH != 3
! 1203: Call UPDATE_HASH() MIN_MATCH-3 more times
! 1204: #endif
! 1205: }
! 1206: /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
! 1207: * but this is not important since only literal bytes will be emitted.
! 1208: */
! 1209:
! 1210: } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
! 1211: }
! 1212:
! 1213: /* ===========================================================================
! 1214: * Flush the current block, with given end-of-file flag.
! 1215: * IN assertion: strstart is set to the end of the current match.
! 1216: */
! 1217: #define FLUSH_BLOCK_ONLY(s, flush) { \
! 1218: ct_flush_block(s, (s->block_start >= 0L ? \
! 1219: (charf *)&s->window[(unsigned)s->block_start] : \
! 1220: (charf *)Z_NULL), (long)s->strstart - s->block_start, (flush)); \
! 1221: s->block_start = s->strstart; \
! 1222: flush_pending(s->strm); \
! 1223: Tracev((stderr,"[FLUSH]")); \
! 1224: }
! 1225:
! 1226: /* Same but force premature exit if necessary. */
! 1227: #define FLUSH_BLOCK(s, flush) { \
! 1228: FLUSH_BLOCK_ONLY(s, flush); \
! 1229: if (s->strm->avail_out == 0) return 1; \
! 1230: }
! 1231:
! 1232: /* ===========================================================================
! 1233: * Compress as much as possible from the input stream, return true if
! 1234: * processing was terminated prematurely (no more input or output space).
! 1235: * This function does not perform lazy evaluationof matches and inserts
! 1236: * new strings in the dictionary only for unmatched strings or for short
! 1237: * matches. It is used only for the fast compression options.
! 1238: */
! 1239: local int deflate_fast(s, flush)
! 1240: deflate_state *s;
! 1241: int flush;
! 1242: {
! 1243: IPos hash_head = NIL; /* head of the hash chain */
! 1244: int bflush; /* set if current block must be flushed */
! 1245:
! 1246: s->prev_length = MIN_MATCH-1;
! 1247:
! 1248: for (;;) {
! 1249: /* Make sure that we always have enough lookahead, except
! 1250: * at the end of the input file. We need MAX_MATCH bytes
! 1251: * for the next match, plus MIN_MATCH bytes to insert the
! 1252: * string following the next match.
! 1253: */
! 1254: if (s->lookahead < MIN_LOOKAHEAD) {
! 1255: fill_window(s);
! 1256: if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
! 1257:
! 1258: if (s->lookahead == 0) break; /* flush the current block */
! 1259: }
! 1260:
! 1261: /* Insert the string window[strstart .. strstart+2] in the
! 1262: * dictionary, and set hash_head to the head of the hash chain:
! 1263: */
! 1264: if (s->lookahead >= MIN_MATCH) {
! 1265: INSERT_STRING(s, s->strstart, hash_head);
! 1266: }
! 1267:
! 1268: /* Find the longest match, discarding those <= prev_length.
! 1269: * At this point we have always match_length < MIN_MATCH
! 1270: */
! 1271: if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
! 1272: /* To simplify the code, we prevent matches with the string
! 1273: * of window index 0 (in particular we have to avoid a match
! 1274: * of the string with itself at the start of the input file).
! 1275: */
! 1276: if (s->strategy != Z_HUFFMAN_ONLY) {
! 1277: s->match_length = longest_match (s, hash_head);
! 1278: }
! 1279: /* longest_match() sets match_start */
! 1280:
! 1281: if (s->match_length > s->lookahead) s->match_length = s->lookahead;
! 1282: }
! 1283: if (s->match_length >= MIN_MATCH) {
! 1284: check_match(s, s->strstart, s->match_start, s->match_length);
! 1285:
! 1286: bflush = ct_tally(s, s->strstart - s->match_start,
! 1287: s->match_length - MIN_MATCH);
! 1288:
! 1289: s->lookahead -= s->match_length;
! 1290:
! 1291: /* Insert new strings in the hash table only if the match length
! 1292: * is not too large. This saves time but degrades compression.
! 1293: */
! 1294: if (s->match_length <= s->max_insert_length &&
! 1295: s->lookahead >= MIN_MATCH) {
! 1296: s->match_length--; /* string at strstart already in hash table */
! 1297: do {
! 1298: s->strstart++;
! 1299: INSERT_STRING(s, s->strstart, hash_head);
! 1300: /* strstart never exceeds WSIZE-MAX_MATCH, so there are
! 1301: * always MIN_MATCH bytes ahead.
! 1302: */
! 1303: } while (--s->match_length != 0);
! 1304: s->strstart++;
! 1305: } else {
! 1306: s->strstart += s->match_length;
! 1307: s->match_length = 0;
! 1308: s->ins_h = s->window[s->strstart];
! 1309: UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
! 1310: #if MIN_MATCH != 3
! 1311: Call UPDATE_HASH() MIN_MATCH-3 more times
! 1312: #endif
! 1313: /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
! 1314: * matter since it will be recomputed at next deflate call.
! 1315: */
! 1316: }
! 1317: } else {
! 1318: /* No match, output a literal byte */
! 1319: Tracevv((stderr,"%c", s->window[s->strstart]));
! 1320: bflush = ct_tally (s, 0, s->window[s->strstart]);
! 1321: s->lookahead--;
! 1322: s->strstart++;
! 1323: }
! 1324: if (bflush) FLUSH_BLOCK(s, Z_NO_FLUSH);
! 1325: }
! 1326: FLUSH_BLOCK(s, flush);
! 1327: return 0; /* normal exit */
! 1328: }
! 1329:
! 1330: /* ===========================================================================
! 1331: * Same as above, but achieves better compression. We use a lazy
! 1332: * evaluation for matches: a match is finally adopted only if there is
! 1333: * no better match at the next window position.
! 1334: */
! 1335: local int deflate_slow(s, flush)
! 1336: deflate_state *s;
! 1337: int flush;
! 1338: {
! 1339: IPos hash_head = NIL; /* head of hash chain */
! 1340: int bflush; /* set if current block must be flushed */
! 1341:
! 1342: /* Process the input block. */
! 1343: for (;;) {
! 1344: /* Make sure that we always have enough lookahead, except
! 1345: * at the end of the input file. We need MAX_MATCH bytes
! 1346: * for the next match, plus MIN_MATCH bytes to insert the
! 1347: * string following the next match.
! 1348: */
! 1349: if (s->lookahead < MIN_LOOKAHEAD) {
! 1350: fill_window(s);
! 1351: if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
! 1352:
! 1353: if (s->lookahead == 0) break; /* flush the current block */
! 1354: }
! 1355:
! 1356: /* Insert the string window[strstart .. strstart+2] in the
! 1357: * dictionary, and set hash_head to the head of the hash chain:
! 1358: */
! 1359: if (s->lookahead >= MIN_MATCH) {
! 1360: INSERT_STRING(s, s->strstart, hash_head);
! 1361: }
! 1362:
! 1363: /* Find the longest match, discarding those <= prev_length.
! 1364: */
! 1365: s->prev_length = s->match_length, s->prev_match = s->match_start;
! 1366: s->match_length = MIN_MATCH-1;
! 1367:
! 1368: if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
! 1369: s->strstart - hash_head <= MAX_DIST(s)) {
! 1370: /* To simplify the code, we prevent matches with the string
! 1371: * of window index 0 (in particular we have to avoid a match
! 1372: * of the string with itself at the start of the input file).
! 1373: */
! 1374: if (s->strategy != Z_HUFFMAN_ONLY) {
! 1375: s->match_length = longest_match (s, hash_head);
! 1376: }
! 1377: /* longest_match() sets match_start */
! 1378: if (s->match_length > s->lookahead) s->match_length = s->lookahead;
! 1379:
! 1380: if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
! 1381: (s->match_length == MIN_MATCH &&
! 1382: s->strstart - s->match_start > TOO_FAR))) {
! 1383:
! 1384: /* If prev_match is also MIN_MATCH, match_start is garbage
! 1385: * but we will ignore the current match anyway.
! 1386: */
! 1387: s->match_length = MIN_MATCH-1;
! 1388: }
! 1389: }
! 1390: /* If there was a match at the previous step and the current
! 1391: * match is not better, output the previous match:
! 1392: */
! 1393: if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
! 1394: uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
! 1395: /* Do not insert strings in hash table beyond this. */
! 1396:
! 1397: check_match(s, s->strstart-1, s->prev_match, s->prev_length);
! 1398:
! 1399: bflush = ct_tally(s, s->strstart -1 - s->prev_match,
! 1400: s->prev_length - MIN_MATCH);
! 1401:
! 1402: /* Insert in hash table all strings up to the end of the match.
! 1403: * strstart-1 and strstart are already inserted. If there is not
! 1404: * enough lookahead, the last two strings are not inserted in
! 1405: * the hash table.
! 1406: */
! 1407: s->lookahead -= s->prev_length-1;
! 1408: s->prev_length -= 2;
! 1409: do {
! 1410: if (++s->strstart <= max_insert) {
! 1411: INSERT_STRING(s, s->strstart, hash_head);
! 1412: }
! 1413: } while (--s->prev_length != 0);
! 1414: s->match_available = 0;
! 1415: s->match_length = MIN_MATCH-1;
! 1416: s->strstart++;
! 1417:
! 1418: if (bflush) FLUSH_BLOCK(s, Z_NO_FLUSH);
! 1419:
! 1420: } else if (s->match_available) {
! 1421: /* If there was no match at the previous position, output a
! 1422: * single literal. If there was a match but the current match
! 1423: * is longer, truncate the previous match to a single literal.
! 1424: */
! 1425: Tracevv((stderr,"%c", s->window[s->strstart-1]));
! 1426: if (ct_tally (s, 0, s->window[s->strstart-1])) {
! 1427: FLUSH_BLOCK_ONLY(s, Z_NO_FLUSH);
! 1428: }
! 1429: s->strstart++;
! 1430: s->lookahead--;
! 1431: if (s->strm->avail_out == 0) return 1;
! 1432: } else {
! 1433: /* There is no previous match to compare with, wait for
! 1434: * the next step to decide.
! 1435: */
! 1436: s->match_available = 1;
! 1437: s->strstart++;
! 1438: s->lookahead--;
! 1439: }
! 1440: }
! 1441: Assert (flush != Z_NO_FLUSH, "no flush?");
! 1442: if (s->match_available) {
! 1443: Tracevv((stderr,"%c", s->window[s->strstart-1]));
! 1444: ct_tally (s, 0, s->window[s->strstart-1]);
! 1445: s->match_available = 0;
! 1446: }
! 1447: FLUSH_BLOCK(s, flush);
! 1448: return 0;
! 1449: }
! 1450:
! 1451:
! 1452: /*+++++*/
! 1453: /* trees.c -- output deflated data using Huffman coding
! 1454: * Copyright (C) 1995 Jean-loup Gailly
! 1455: * For conditions of distribution and use, see copyright notice in zlib.h
! 1456: */
! 1457:
! 1458: /*
! 1459: * ALGORITHM
! 1460: *
! 1461: * The "deflation" process uses several Huffman trees. The more
! 1462: * common source values are represented by shorter bit sequences.
! 1463: *
! 1464: * Each code tree is stored in a compressed form which is itself
! 1465: * a Huffman encoding of the lengths of all the code strings (in
! 1466: * ascending order by source values). The actual code strings are
! 1467: * reconstructed from the lengths in the inflate process, as described
! 1468: * in the deflate specification.
! 1469: *
! 1470: * REFERENCES
! 1471: *
! 1472: * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
! 1473: * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
! 1474: *
! 1475: * Storer, James A.
! 1476: * Data Compression: Methods and Theory, pp. 49-50.
! 1477: * Computer Science Press, 1988. ISBN 0-7167-8156-5.
! 1478: *
! 1479: * Sedgewick, R.
! 1480: * Algorithms, p290.
! 1481: * Addison-Wesley, 1983. ISBN 0-201-06672-6.
! 1482: */
! 1483:
! 1484: /* From: trees.c,v 1.5 1995/05/03 17:27:12 jloup Exp */
! 1485:
! 1486: #ifdef DEBUG_ZLIB
! 1487: # include <ctype.h>
! 1488: #endif
! 1489:
! 1490: /* ===========================================================================
! 1491: * Constants
! 1492: */
! 1493:
! 1494: #define MAX_BL_BITS 7
! 1495: /* Bit length codes must not exceed MAX_BL_BITS bits */
! 1496:
! 1497: #define END_BLOCK 256
! 1498: /* end of block literal code */
! 1499:
! 1500: #define REP_3_6 16
! 1501: /* repeat previous bit length 3-6 times (2 bits of repeat count) */
! 1502:
! 1503: #define REPZ_3_10 17
! 1504: /* repeat a zero length 3-10 times (3 bits of repeat count) */
! 1505:
! 1506: #define REPZ_11_138 18
! 1507: /* repeat a zero length 11-138 times (7 bits of repeat count) */
! 1508:
! 1509: local const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
! 1510: = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
! 1511:
! 1512: local const int extra_dbits[D_CODES] /* extra bits for each distance code */
! 1513: = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
! 1514:
! 1515: local const int extra_blbits[BL_CODES]/* extra bits for each bit length code */
! 1516: = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
! 1517:
! 1518: local const uch bl_order[BL_CODES]
! 1519: = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
! 1520: /* The lengths of the bit length codes are sent in order of decreasing
! 1521: * probability, to avoid transmitting the lengths for unused bit length codes.
! 1522: */
! 1523:
! 1524: #define Buf_size (8 * 2*sizeof(char))
! 1525: /* Number of bits used within bi_buf. (bi_buf might be implemented on
! 1526: * more than 16 bits on some systems.)
! 1527: */
! 1528:
! 1529: /* ===========================================================================
! 1530: * Local data. These are initialized only once.
! 1531: * To do: initialize at compile time to be completely reentrant. ???
! 1532: */
! 1533:
! 1534: local ct_data static_ltree[L_CODES+2];
! 1535: /* The static literal tree. Since the bit lengths are imposed, there is no
! 1536: * need for the L_CODES extra codes used during heap construction. However
! 1537: * The codes 286 and 287 are needed to build a canonical tree (see ct_init
! 1538: * below).
! 1539: */
! 1540:
! 1541: local ct_data static_dtree[D_CODES];
! 1542: /* The static distance tree. (Actually a trivial tree since all codes use
! 1543: * 5 bits.)
! 1544: */
! 1545:
! 1546: local uch dist_code[512];
! 1547: /* distance codes. The first 256 values correspond to the distances
! 1548: * 3 .. 258, the last 256 values correspond to the top 8 bits of
! 1549: * the 15 bit distances.
! 1550: */
! 1551:
! 1552: local uch length_code[MAX_MATCH-MIN_MATCH+1];
! 1553: /* length code for each normalized match length (0 == MIN_MATCH) */
! 1554:
! 1555: local int base_length[LENGTH_CODES];
! 1556: /* First normalized length for each code (0 = MIN_MATCH) */
! 1557:
! 1558: local int base_dist[D_CODES];
! 1559: /* First normalized distance for each code (0 = distance of 1) */
! 1560:
! 1561: struct static_tree_desc_s {
! 1562: ct_data *static_tree; /* static tree or NULL */
! 1563: const intf *extra_bits; /* extra bits for each code or NULL */
! 1564: int extra_base; /* base index for extra_bits */
! 1565: int elems; /* max number of elements in the tree */
! 1566: int max_length; /* max bit length for the codes */
! 1567: };
! 1568:
! 1569: local const static_tree_desc static_l_desc =
! 1570: {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
! 1571:
! 1572: local const static_tree_desc static_d_desc =
! 1573: {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
! 1574:
! 1575: local const static_tree_desc static_bl_desc =
! 1576: {(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
! 1577:
! 1578: /* ===========================================================================
! 1579: * Local (static) routines in this file.
! 1580: */
! 1581:
! 1582: local void ct_static_init OF((void));
! 1583: local void init_block OF((deflate_state *s));
! 1584: local void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
! 1585: local void gen_bitlen OF((deflate_state *s, tree_desc *desc));
! 1586: local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count));
! 1587: local void build_tree OF((deflate_state *s, tree_desc *desc));
! 1588: local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
! 1589: local void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
! 1590: local int build_bl_tree OF((deflate_state *s));
! 1591: local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
! 1592: int blcodes));
! 1593: local void compress_block OF((deflate_state *s, ct_data *ltree,
! 1594: ct_data *dtree));
! 1595: local void set_data_type OF((deflate_state *s));
! 1596: local unsigned bi_reverse OF((unsigned value, int length));
! 1597: local void bi_windup OF((deflate_state *s));
! 1598: local void bi_flush OF((deflate_state *s));
! 1599: local void copy_block OF((deflate_state *s, charf *buf, unsigned len,
! 1600: int header));
! 1601:
! 1602: #ifndef DEBUG_ZLIB
! 1603: # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
! 1604: /* Send a code of the given tree. c and tree must not have side effects */
! 1605:
! 1606: #else /* DEBUG_ZLIB */
! 1607: # define send_code(s, c, tree) \
! 1608: { if (verbose>1) fprintf(stderr,"\ncd %3d ",(c)); \
! 1609: send_bits(s, tree[c].Code, tree[c].Len); }
! 1610: #endif
! 1611:
! 1612: #define d_code(dist) \
! 1613: ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
! 1614: /* Mapping from a distance to a distance code. dist is the distance - 1 and
! 1615: * must not have side effects. dist_code[256] and dist_code[257] are never
! 1616: * used.
! 1617: */
! 1618:
! 1619: /* ===========================================================================
! 1620: * Output a short LSB first on the stream.
! 1621: * IN assertion: there is enough room in pendingBuf.
! 1622: */
! 1623: #define put_short(s, w) { \
! 1624: put_byte(s, (uch)((w) & 0xff)); \
! 1625: put_byte(s, (uch)((ush)(w) >> 8)); \
! 1626: }
! 1627:
! 1628: /* ===========================================================================
! 1629: * Send a value on a given number of bits.
! 1630: * IN assertion: length <= 16 and value fits in length bits.
! 1631: */
! 1632: #ifdef DEBUG_ZLIB
! 1633: local void send_bits OF((deflate_state *s, int value, int length));
! 1634:
! 1635: local void send_bits(s, value, length)
! 1636: deflate_state *s;
! 1637: int value; /* value to send */
! 1638: int length; /* number of bits */
! 1639: {
! 1640: Tracev((stderr," l %2d v %4x ", length, value));
! 1641: Assert(length > 0 && length <= 15, "invalid length");
! 1642: s->bits_sent += (ulg)length;
! 1643:
! 1644: /* If not enough room in bi_buf, use (valid) bits from bi_buf and
! 1645: * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
! 1646: * unused bits in value.
! 1647: */
! 1648: if (s->bi_valid > (int)Buf_size - length) {
! 1649: s->bi_buf |= (value << s->bi_valid);
! 1650: put_short(s, s->bi_buf);
! 1651: s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
! 1652: s->bi_valid += length - Buf_size;
! 1653: } else {
! 1654: s->bi_buf |= value << s->bi_valid;
! 1655: s->bi_valid += length;
! 1656: }
! 1657: }
! 1658: #else /* !DEBUG_ZLIB */
! 1659:
! 1660: #define send_bits(s, value, length) \
! 1661: { int len = length;\
! 1662: if (s->bi_valid > (int)Buf_size - len) {\
! 1663: int val = value;\
! 1664: s->bi_buf |= (val << s->bi_valid);\
! 1665: put_short(s, s->bi_buf);\
! 1666: s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
! 1667: s->bi_valid += len - Buf_size;\
! 1668: } else {\
! 1669: s->bi_buf |= (value) << s->bi_valid;\
! 1670: s->bi_valid += len;\
! 1671: }\
! 1672: }
! 1673: #endif /* DEBUG_ZLIB */
! 1674:
! 1675:
! 1676: /* the arguments must not have side effects */
! 1677:
! 1678: /* ===========================================================================
! 1679: * Initialize the various 'constant' tables.
! 1680: * To do: do this at compile time.
! 1681: */
! 1682: local void ct_static_init()
! 1683: {
! 1684: int n; /* iterates over tree elements */
! 1685: int bits; /* bit counter */
! 1686: int length; /* length value */
! 1687: int code; /* code value */
! 1688: int dist; /* distance index */
! 1689: ush bl_count[MAX_BITS+1];
! 1690: /* number of codes at each bit length for an optimal tree */
! 1691:
! 1692: /* Initialize the mapping length (0..255) -> length code (0..28) */
! 1693: length = 0;
! 1694: for (code = 0; code < LENGTH_CODES-1; code++) {
! 1695: base_length[code] = length;
! 1696: for (n = 0; n < (1<<extra_lbits[code]); n++) {
! 1697: length_code[length++] = (uch)code;
! 1698: }
! 1699: }
! 1700: Assert (length == 256, "ct_static_init: length != 256");
! 1701: /* Note that the length 255 (match length 258) can be represented
! 1702: * in two different ways: code 284 + 5 bits or code 285, so we
! 1703: * overwrite length_code[255] to use the best encoding:
! 1704: */
! 1705: length_code[length-1] = (uch)code;
! 1706:
! 1707: /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
! 1708: dist = 0;
! 1709: for (code = 0 ; code < 16; code++) {
! 1710: base_dist[code] = dist;
! 1711: for (n = 0; n < (1<<extra_dbits[code]); n++) {
! 1712: dist_code[dist++] = (uch)code;
! 1713: }
! 1714: }
! 1715: Assert (dist == 256, "ct_static_init: dist != 256");
! 1716: dist >>= 7; /* from now on, all distances are divided by 128 */
! 1717: for ( ; code < D_CODES; code++) {
! 1718: base_dist[code] = dist << 7;
! 1719: for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
! 1720: dist_code[256 + dist++] = (uch)code;
! 1721: }
! 1722: }
! 1723: Assert (dist == 256, "ct_static_init: 256+dist != 512");
! 1724:
! 1725: /* Construct the codes of the static literal tree */
! 1726: for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
! 1727: n = 0;
! 1728: while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
! 1729: while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
! 1730: while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
! 1731: while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
! 1732: /* Codes 286 and 287 do not exist, but we must include them in the
! 1733: * tree construction to get a canonical Huffman tree (longest code
! 1734: * all ones)
! 1735: */
! 1736: gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
! 1737:
! 1738: /* The static distance tree is trivial: */
! 1739: for (n = 0; n < D_CODES; n++) {
! 1740: static_dtree[n].Len = 5;
! 1741: static_dtree[n].Code = bi_reverse(n, 5);
! 1742: }
! 1743: }
! 1744:
! 1745: /* ===========================================================================
! 1746: * Initialize the tree data structures for a new zlib stream.
! 1747: */
! 1748: local void ct_init(s)
! 1749: deflate_state *s;
! 1750: {
! 1751: if (static_dtree[0].Len == 0) {
! 1752: ct_static_init(); /* To do: at compile time */
! 1753: }
! 1754:
! 1755: s->compressed_len = 0L;
! 1756:
! 1757: s->l_desc.dyn_tree = s->dyn_ltree;
! 1758: s->l_desc.stat_desc = &static_l_desc;
! 1759:
! 1760: s->d_desc.dyn_tree = s->dyn_dtree;
! 1761: s->d_desc.stat_desc = &static_d_desc;
! 1762:
! 1763: s->bl_desc.dyn_tree = s->bl_tree;
! 1764: s->bl_desc.stat_desc = &static_bl_desc;
! 1765:
! 1766: s->bi_buf = 0;
! 1767: s->bi_valid = 0;
! 1768: s->last_eob_len = 8; /* enough lookahead for inflate */
! 1769: #ifdef DEBUG_ZLIB
! 1770: s->bits_sent = 0L;
! 1771: #endif
! 1772: s->blocks_in_packet = 0;
! 1773:
! 1774: /* Initialize the first block of the first file: */
! 1775: init_block(s);
! 1776: }
! 1777:
! 1778: /* ===========================================================================
! 1779: * Initialize a new block.
! 1780: */
! 1781: local void init_block(s)
! 1782: deflate_state *s;
! 1783: {
! 1784: int n; /* iterates over tree elements */
! 1785:
! 1786: /* Initialize the trees. */
! 1787: for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
! 1788: for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
! 1789: for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
! 1790:
! 1791: s->dyn_ltree[END_BLOCK].Freq = 1;
! 1792: s->opt_len = s->static_len = 0L;
! 1793: s->last_lit = s->matches = 0;
! 1794: }
! 1795:
! 1796: #define SMALLEST 1
! 1797: /* Index within the heap array of least frequent node in the Huffman tree */
! 1798:
! 1799:
! 1800: /* ===========================================================================
! 1801: * Remove the smallest element from the heap and recreate the heap with
! 1802: * one less element. Updates heap and heap_len.
! 1803: */
! 1804: #define pqremove(s, tree, top) \
! 1805: {\
! 1806: top = s->heap[SMALLEST]; \
! 1807: s->heap[SMALLEST] = s->heap[s->heap_len--]; \
! 1808: pqdownheap(s, tree, SMALLEST); \
! 1809: }
! 1810:
! 1811: /* ===========================================================================
! 1812: * Compares to subtrees, using the tree depth as tie breaker when
! 1813: * the subtrees have equal frequency. This minimizes the worst case length.
! 1814: */
! 1815: #define smaller(tree, n, m, depth) \
! 1816: (tree[n].Freq < tree[m].Freq || \
! 1817: (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
! 1818:
! 1819: /* ===========================================================================
! 1820: * Restore the heap property by moving down the tree starting at node k,
! 1821: * exchanging a node with the smallest of its two sons if necessary, stopping
! 1822: * when the heap property is re-established (each father smaller than its
! 1823: * two sons).
! 1824: */
! 1825: local void pqdownheap(s, tree, k)
! 1826: deflate_state *s;
! 1827: ct_data *tree; /* the tree to restore */
! 1828: int k; /* node to move down */
! 1829: {
! 1830: int v = s->heap[k];
! 1831: int j = k << 1; /* left son of k */
! 1832: while (j <= s->heap_len) {
! 1833: /* Set j to the smallest of the two sons: */
! 1834: if (j < s->heap_len &&
! 1835: smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
! 1836: j++;
! 1837: }
! 1838: /* Exit if v is smaller than both sons */
! 1839: if (smaller(tree, v, s->heap[j], s->depth)) break;
! 1840:
! 1841: /* Exchange v with the smallest son */
! 1842: s->heap[k] = s->heap[j]; k = j;
! 1843:
! 1844: /* And continue down the tree, setting j to the left son of k */
! 1845: j <<= 1;
! 1846: }
! 1847: s->heap[k] = v;
! 1848: }
! 1849:
! 1850: /* ===========================================================================
! 1851: * Compute the optimal bit lengths for a tree and update the total bit length
! 1852: * for the current block.
! 1853: * IN assertion: the fields freq and dad are set, heap[heap_max] and
! 1854: * above are the tree nodes sorted by increasing frequency.
! 1855: * OUT assertions: the field len is set to the optimal bit length, the
! 1856: * array bl_count contains the frequencies for each bit length.
! 1857: * The length opt_len is updated; static_len is also updated if stree is
! 1858: * not null.
! 1859: */
! 1860: local void gen_bitlen(s, desc)
! 1861: deflate_state *s;
! 1862: tree_desc *desc; /* the tree descriptor */
! 1863: {
! 1864: ct_data *tree = desc->dyn_tree;
! 1865: int max_code = desc->max_code;
! 1866: ct_data *stree = desc->stat_desc->static_tree;
! 1867: const intf *extra = desc->stat_desc->extra_bits;
! 1868: int base = desc->stat_desc->extra_base;
! 1869: int max_length = desc->stat_desc->max_length;
! 1870: int h; /* heap index */
! 1871: int n, m; /* iterate over the tree elements */
! 1872: int bits; /* bit length */
! 1873: int xbits; /* extra bits */
! 1874: ush f; /* frequency */
! 1875: int overflow = 0; /* number of elements with bit length too large */
! 1876:
! 1877: for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
! 1878:
! 1879: /* In a first pass, compute the optimal bit lengths (which may
! 1880: * overflow in the case of the bit length tree).
! 1881: */
! 1882: tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
! 1883:
! 1884: for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
! 1885: n = s->heap[h];
! 1886: bits = tree[tree[n].Dad].Len + 1;
! 1887: if (bits > max_length) bits = max_length, overflow++;
! 1888: tree[n].Len = (ush)bits;
! 1889: /* We overwrite tree[n].Dad which is no longer needed */
! 1890:
! 1891: if (n > max_code) continue; /* not a leaf node */
! 1892:
! 1893: s->bl_count[bits]++;
! 1894: xbits = 0;
! 1895: if (n >= base) xbits = extra[n-base];
! 1896: f = tree[n].Freq;
! 1897: s->opt_len += (ulg)f * (bits + xbits);
! 1898: if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
! 1899: }
! 1900: if (overflow == 0) return;
! 1901:
! 1902: Trace((stderr,"\nbit length overflow\n"));
! 1903: /* This happens for example on obj2 and pic of the Calgary corpus */
! 1904:
! 1905: /* Find the first bit length which could increase: */
! 1906: do {
! 1907: bits = max_length-1;
! 1908: while (s->bl_count[bits] == 0) bits--;
! 1909: s->bl_count[bits]--; /* move one leaf down the tree */
! 1910: s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
! 1911: s->bl_count[max_length]--;
! 1912: /* The brother of the overflow item also moves one step up,
! 1913: * but this does not affect bl_count[max_length]
! 1914: */
! 1915: overflow -= 2;
! 1916: } while (overflow > 0);
! 1917:
! 1918: /* Now recompute all bit lengths, scanning in increasing frequency.
! 1919: * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
! 1920: * lengths instead of fixing only the wrong ones. This idea is taken
! 1921: * from 'ar' written by Haruhiko Okumura.)
! 1922: */
! 1923: for (bits = max_length; bits != 0; bits--) {
! 1924: n = s->bl_count[bits];
! 1925: while (n != 0) {
! 1926: m = s->heap[--h];
! 1927: if (m > max_code) continue;
! 1928: if (tree[m].Len != (unsigned) bits) {
! 1929: Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
! 1930: s->opt_len += ((long)bits - (long)tree[m].Len)
! 1931: *(long)tree[m].Freq;
! 1932: tree[m].Len = (ush)bits;
! 1933: }
! 1934: n--;
! 1935: }
! 1936: }
! 1937: }
! 1938:
! 1939: /* ===========================================================================
! 1940: * Generate the codes for a given tree and bit counts (which need not be
! 1941: * optimal).
! 1942: * IN assertion: the array bl_count contains the bit length statistics for
! 1943: * the given tree and the field len is set for all tree elements.
! 1944: * OUT assertion: the field code is set for all tree elements of non
! 1945: * zero code length.
! 1946: */
! 1947: local void gen_codes (tree, max_code, bl_count)
! 1948: ct_data *tree; /* the tree to decorate */
! 1949: int max_code; /* largest code with non zero frequency */
! 1950: ushf *bl_count; /* number of codes at each bit length */
! 1951: {
! 1952: ush next_code[MAX_BITS+1]; /* next code value for each bit length */
! 1953: ush code = 0; /* running code value */
! 1954: int bits; /* bit index */
! 1955: int n; /* code index */
! 1956:
! 1957: /* The distribution counts are first used to generate the code values
! 1958: * without bit reversal.
! 1959: */
! 1960: for (bits = 1; bits <= MAX_BITS; bits++) {
! 1961: next_code[bits] = code = (code + bl_count[bits-1]) << 1;
! 1962: }
! 1963: /* Check that the bit counts in bl_count are consistent. The last code
! 1964: * must be all ones.
! 1965: */
! 1966: Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
! 1967: "inconsistent bit counts");
! 1968: Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
! 1969:
! 1970: for (n = 0; n <= max_code; n++) {
! 1971: int len = tree[n].Len;
! 1972: if (len == 0) continue;
! 1973: /* Now reverse the bits */
! 1974: tree[n].Code = bi_reverse(next_code[len]++, len);
! 1975:
! 1976: Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
! 1977: n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
! 1978: }
! 1979: }
! 1980:
! 1981: /* ===========================================================================
! 1982: * Construct one Huffman tree and assigns the code bit strings and lengths.
! 1983: * Update the total bit length for the current block.
! 1984: * IN assertion: the field freq is set for all tree elements.
! 1985: * OUT assertions: the fields len and code are set to the optimal bit length
! 1986: * and corresponding code. The length opt_len is updated; static_len is
! 1987: * also updated if stree is not null. The field max_code is set.
! 1988: */
! 1989: local void build_tree(s, desc)
! 1990: deflate_state *s;
! 1991: tree_desc *desc; /* the tree descriptor */
! 1992: {
! 1993: ct_data *tree = desc->dyn_tree;
! 1994: ct_data *stree = desc->stat_desc->static_tree;
! 1995: int elems = desc->stat_desc->elems;
! 1996: int n, m; /* iterate over heap elements */
! 1997: int max_code = -1; /* largest code with non zero frequency */
! 1998: int node; /* new node being created */
! 1999:
! 2000: /* Construct the initial heap, with least frequent element in
! 2001: * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
! 2002: * heap[0] is not used.
! 2003: */
! 2004: s->heap_len = 0, s->heap_max = HEAP_SIZE;
! 2005:
! 2006: for (n = 0; n < elems; n++) {
! 2007: if (tree[n].Freq != 0) {
! 2008: s->heap[++(s->heap_len)] = max_code = n;
! 2009: s->depth[n] = 0;
! 2010: } else {
! 2011: tree[n].Len = 0;
! 2012: }
! 2013: }
! 2014:
! 2015: /* The pkzip format requires that at least one distance code exists,
! 2016: * and that at least one bit should be sent even if there is only one
! 2017: * possible code. So to avoid special checks later on we force at least
! 2018: * two codes of non zero frequency.
! 2019: */
! 2020: while (s->heap_len < 2) {
! 2021: node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
! 2022: tree[node].Freq = 1;
! 2023: s->depth[node] = 0;
! 2024: s->opt_len--; if (stree) s->static_len -= stree[node].Len;
! 2025: /* node is 0 or 1 so it does not have extra bits */
! 2026: }
! 2027: desc->max_code = max_code;
! 2028:
! 2029: /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
! 2030: * establish sub-heaps of increasing lengths:
! 2031: */
! 2032: for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
! 2033:
! 2034: /* Construct the Huffman tree by repeatedly combining the least two
! 2035: * frequent nodes.
! 2036: */
! 2037: node = elems; /* next internal node of the tree */
! 2038: do {
! 2039: pqremove(s, tree, n); /* n = node of least frequency */
! 2040: m = s->heap[SMALLEST]; /* m = node of next least frequency */
! 2041:
! 2042: s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
! 2043: s->heap[--(s->heap_max)] = m;
! 2044:
! 2045: /* Create a new node father of n and m */
! 2046: tree[node].Freq = tree[n].Freq + tree[m].Freq;
! 2047: s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1);
! 2048: tree[n].Dad = tree[m].Dad = (ush)node;
! 2049: #ifdef DUMP_BL_TREE
! 2050: if (tree == s->bl_tree) {
! 2051: fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
! 2052: node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
! 2053: }
! 2054: #endif
! 2055: /* and insert the new node in the heap */
! 2056: s->heap[SMALLEST] = node++;
! 2057: pqdownheap(s, tree, SMALLEST);
! 2058:
! 2059: } while (s->heap_len >= 2);
! 2060:
! 2061: s->heap[--(s->heap_max)] = s->heap[SMALLEST];
! 2062:
! 2063: /* At this point, the fields freq and dad are set. We can now
! 2064: * generate the bit lengths.
! 2065: */
! 2066: gen_bitlen(s, (tree_desc *)desc);
! 2067:
! 2068: /* The field len is now set, we can generate the bit codes */
! 2069: gen_codes ((ct_data *)tree, max_code, s->bl_count);
! 2070: }
! 2071:
! 2072: /* ===========================================================================
! 2073: * Scan a literal or distance tree to determine the frequencies of the codes
! 2074: * in the bit length tree.
! 2075: */
! 2076: local void scan_tree (s, tree, max_code)
! 2077: deflate_state *s;
! 2078: ct_data *tree; /* the tree to be scanned */
! 2079: int max_code; /* and its largest code of non zero frequency */
! 2080: {
! 2081: int n; /* iterates over all tree elements */
! 2082: int prevlen = -1; /* last emitted length */
! 2083: int curlen; /* length of current code */
! 2084: int nextlen = tree[0].Len; /* length of next code */
! 2085: int count = 0; /* repeat count of the current code */
! 2086: int max_count = 7; /* max repeat count */
! 2087: int min_count = 4; /* min repeat count */
! 2088:
! 2089: if (nextlen == 0) max_count = 138, min_count = 3;
! 2090: tree[max_code+1].Len = (ush)0xffff; /* guard */
! 2091:
! 2092: for (n = 0; n <= max_code; n++) {
! 2093: curlen = nextlen; nextlen = tree[n+1].Len;
! 2094: if (++count < max_count && curlen == nextlen) {
! 2095: continue;
! 2096: } else if (count < min_count) {
! 2097: s->bl_tree[curlen].Freq += count;
! 2098: } else if (curlen != 0) {
! 2099: if (curlen != prevlen) s->bl_tree[curlen].Freq++;
! 2100: s->bl_tree[REP_3_6].Freq++;
! 2101: } else if (count <= 10) {
! 2102: s->bl_tree[REPZ_3_10].Freq++;
! 2103: } else {
! 2104: s->bl_tree[REPZ_11_138].Freq++;
! 2105: }
! 2106: count = 0; prevlen = curlen;
! 2107: if (nextlen == 0) {
! 2108: max_count = 138, min_count = 3;
! 2109: } else if (curlen == nextlen) {
! 2110: max_count = 6, min_count = 3;
! 2111: } else {
! 2112: max_count = 7, min_count = 4;
! 2113: }
! 2114: }
! 2115: }
! 2116:
! 2117: /* ===========================================================================
! 2118: * Send a literal or distance tree in compressed form, using the codes in
! 2119: * bl_tree.
! 2120: */
! 2121: local void send_tree (s, tree, max_code)
! 2122: deflate_state *s;
! 2123: ct_data *tree; /* the tree to be scanned */
! 2124: int max_code; /* and its largest code of non zero frequency */
! 2125: {
! 2126: int n; /* iterates over all tree elements */
! 2127: int prevlen = -1; /* last emitted length */
! 2128: int curlen; /* length of current code */
! 2129: int nextlen = tree[0].Len; /* length of next code */
! 2130: int count = 0; /* repeat count of the current code */
! 2131: int max_count = 7; /* max repeat count */
! 2132: int min_count = 4; /* min repeat count */
! 2133:
! 2134: /* tree[max_code+1].Len = -1; */ /* guard already set */
! 2135: if (nextlen == 0) max_count = 138, min_count = 3;
! 2136:
! 2137: for (n = 0; n <= max_code; n++) {
! 2138: curlen = nextlen; nextlen = tree[n+1].Len;
! 2139: if (++count < max_count && curlen == nextlen) {
! 2140: continue;
! 2141: } else if (count < min_count) {
! 2142: do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
! 2143:
! 2144: } else if (curlen != 0) {
! 2145: if (curlen != prevlen) {
! 2146: send_code(s, curlen, s->bl_tree); count--;
! 2147: }
! 2148: Assert(count >= 3 && count <= 6, " 3_6?");
! 2149: send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
! 2150:
! 2151: } else if (count <= 10) {
! 2152: send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
! 2153:
! 2154: } else {
! 2155: send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
! 2156: }
! 2157: count = 0; prevlen = curlen;
! 2158: if (nextlen == 0) {
! 2159: max_count = 138, min_count = 3;
! 2160: } else if (curlen == nextlen) {
! 2161: max_count = 6, min_count = 3;
! 2162: } else {
! 2163: max_count = 7, min_count = 4;
! 2164: }
! 2165: }
! 2166: }
! 2167:
! 2168: /* ===========================================================================
! 2169: * Construct the Huffman tree for the bit lengths and return the index in
! 2170: * bl_order of the last bit length code to send.
! 2171: */
! 2172: local int build_bl_tree(s)
! 2173: deflate_state *s;
! 2174: {
! 2175: int max_blindex; /* index of last bit length code of non zero freq */
! 2176:
! 2177: /* Determine the bit length frequencies for literal and distance trees */
! 2178: scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
! 2179: scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
! 2180:
! 2181: /* Build the bit length tree: */
! 2182: build_tree(s, (tree_desc *)(&(s->bl_desc)));
! 2183: /* opt_len now includes the length of the tree representations, except
! 2184: * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
! 2185: */
! 2186:
! 2187: /* Determine the number of bit length codes to send. The pkzip format
! 2188: * requires that at least 4 bit length codes be sent. (appnote.txt says
! 2189: * 3 but the actual value used is 4.)
! 2190: */
! 2191: for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
! 2192: if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
! 2193: }
! 2194: /* Update opt_len to include the bit length tree and counts */
! 2195: s->opt_len += 3*(max_blindex+1) + 5+5+4;
! 2196: Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
! 2197: s->opt_len, s->static_len));
! 2198:
! 2199: return max_blindex;
! 2200: }
! 2201:
! 2202: /* ===========================================================================
! 2203: * Send the header for a block using dynamic Huffman trees: the counts, the
! 2204: * lengths of the bit length codes, the literal tree and the distance tree.
! 2205: * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
! 2206: */
! 2207: local void send_all_trees(s, lcodes, dcodes, blcodes)
! 2208: deflate_state *s;
! 2209: int lcodes, dcodes, blcodes; /* number of codes for each tree */
! 2210: {
! 2211: int rank; /* index in bl_order */
! 2212:
! 2213: Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
! 2214: Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
! 2215: "too many codes");
! 2216: Tracev((stderr, "\nbl counts: "));
! 2217: send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
! 2218: send_bits(s, dcodes-1, 5);
! 2219: send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */
! 2220: for (rank = 0; rank < blcodes; rank++) {
! 2221: Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
! 2222: send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
! 2223: }
! 2224: Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
! 2225:
! 2226: send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
! 2227: Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
! 2228:
! 2229: send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
! 2230: Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
! 2231: }
! 2232:
! 2233: /* ===========================================================================
! 2234: * Send a stored block
! 2235: */
! 2236: local void ct_stored_block(s, buf, stored_len, eof)
! 2237: deflate_state *s;
! 2238: charf *buf; /* input block */
! 2239: ulg stored_len; /* length of input block */
! 2240: int eof; /* true if this is the last block for a file */
! 2241: {
! 2242: send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */
! 2243: s->compressed_len = (s->compressed_len + 3 + 7) & ~7L;
! 2244: s->compressed_len += (stored_len + 4) << 3;
! 2245:
! 2246: copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
! 2247: }
! 2248:
! 2249: /* Send just the `stored block' type code without any length bytes or data.
! 2250: */
! 2251: local void ct_stored_type_only(s)
! 2252: deflate_state *s;
! 2253: {
! 2254: send_bits(s, (STORED_BLOCK << 1), 3);
! 2255: bi_windup(s);
! 2256: s->compressed_len = (s->compressed_len + 3) & ~7L;
! 2257: }
! 2258:
! 2259:
! 2260: /* ===========================================================================
! 2261: * Send one empty static block to give enough lookahead for inflate.
! 2262: * This takes 10 bits, of which 7 may remain in the bit buffer.
! 2263: * The current inflate code requires 9 bits of lookahead. If the EOB
! 2264: * code for the previous block was coded on 5 bits or less, inflate
! 2265: * may have only 5+3 bits of lookahead to decode this EOB.
! 2266: * (There are no problems if the previous block is stored or fixed.)
! 2267: */
! 2268: local void ct_align(s)
! 2269: deflate_state *s;
! 2270: {
! 2271: send_bits(s, STATIC_TREES<<1, 3);
! 2272: send_code(s, END_BLOCK, static_ltree);
! 2273: s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
! 2274: bi_flush(s);
! 2275: /* Of the 10 bits for the empty block, we have already sent
! 2276: * (10 - bi_valid) bits. The lookahead for the EOB of the previous
! 2277: * block was thus its length plus what we have just sent.
! 2278: */
! 2279: if (s->last_eob_len + 10 - s->bi_valid < 9) {
! 2280: send_bits(s, STATIC_TREES<<1, 3);
! 2281: send_code(s, END_BLOCK, static_ltree);
! 2282: s->compressed_len += 10L;
! 2283: bi_flush(s);
! 2284: }
! 2285: s->last_eob_len = 7;
! 2286: }
! 2287:
! 2288: /* ===========================================================================
! 2289: * Determine the best encoding for the current block: dynamic trees, static
! 2290: * trees or store, and output the encoded block to the zip file. This function
! 2291: * returns the total compressed length for the file so far.
! 2292: */
! 2293: local ulg ct_flush_block(s, buf, stored_len, flush)
! 2294: deflate_state *s;
! 2295: charf *buf; /* input block, or NULL if too old */
! 2296: ulg stored_len; /* length of input block */
! 2297: int flush; /* Z_FINISH if this is the last block for a file */
! 2298: {
! 2299: ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
! 2300: int max_blindex; /* index of last bit length code of non zero freq */
! 2301: int eof = flush == Z_FINISH;
! 2302:
! 2303: ++s->blocks_in_packet;
! 2304:
! 2305: /* Check if the file is ascii or binary */
! 2306: if (s->data_type == UNKNOWN) set_data_type(s);
! 2307:
! 2308: /* Construct the literal and distance trees */
! 2309: build_tree(s, (tree_desc *)(&(s->l_desc)));
! 2310: Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
! 2311: s->static_len));
! 2312:
! 2313: build_tree(s, (tree_desc *)(&(s->d_desc)));
! 2314: Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
! 2315: s->static_len));
! 2316: /* At this point, opt_len and static_len are the total bit lengths of
! 2317: * the compressed block data, excluding the tree representations.
! 2318: */
! 2319:
! 2320: /* Build the bit length tree for the above two trees, and get the index
! 2321: * in bl_order of the last bit length code to send.
! 2322: */
! 2323: max_blindex = build_bl_tree(s);
! 2324:
! 2325: /* Determine the best encoding. Compute first the block length in bytes */
! 2326: opt_lenb = (s->opt_len+3+7)>>3;
! 2327: static_lenb = (s->static_len+3+7)>>3;
! 2328:
! 2329: Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
! 2330: opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
! 2331: s->last_lit));
! 2332:
! 2333: if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
! 2334:
! 2335: /* If compression failed and this is the first and last block,
! 2336: * and if the .zip file can be seeked (to rewrite the local header),
! 2337: * the whole file is transformed into a stored file:
! 2338: */
! 2339: #ifdef STORED_FILE_OK
! 2340: # ifdef FORCE_STORED_FILE
! 2341: if (eof && compressed_len == 0L) /* force stored file */
! 2342: # else
! 2343: if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable())
! 2344: # endif
! 2345: {
! 2346: /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
! 2347: if (buf == (charf*)0) error ("block vanished");
! 2348:
! 2349: copy_block(buf, (unsigned)stored_len, 0); /* without header */
! 2350: s->compressed_len = stored_len << 3;
! 2351: s->method = STORED;
! 2352: } else
! 2353: #endif /* STORED_FILE_OK */
! 2354:
! 2355: /* For Z_PACKET_FLUSH, if we don't achieve the required minimum
! 2356: * compression, and this block contains all the data since the last
! 2357: * time we used Z_PACKET_FLUSH, then just omit this block completely
! 2358: * from the output.
! 2359: */
! 2360: if (flush == Z_PACKET_FLUSH && s->blocks_in_packet == 1
! 2361: && opt_lenb > stored_len - s->minCompr) {
! 2362: s->blocks_in_packet = 0;
! 2363: /* output nothing */
! 2364: } else
! 2365:
! 2366: #ifdef FORCE_STORED
! 2367: if (buf != (char*)0) /* force stored block */
! 2368: #else
! 2369: if (stored_len+4 <= opt_lenb && buf != (char*)0)
! 2370: /* 4: two words for the lengths */
! 2371: #endif
! 2372: {
! 2373: /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
! 2374: * Otherwise we can't have processed more than WSIZE input bytes since
! 2375: * the last block flush, because compression would have been
! 2376: * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
! 2377: * transform a block into a stored block.
! 2378: */
! 2379: ct_stored_block(s, buf, stored_len, eof);
! 2380: } else
! 2381:
! 2382: #ifdef FORCE_STATIC
! 2383: if (static_lenb >= 0) /* force static trees */
! 2384: #else
! 2385: if (static_lenb == opt_lenb)
! 2386: #endif
! 2387: {
! 2388: send_bits(s, (STATIC_TREES<<1)+eof, 3);
! 2389: compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
! 2390: s->compressed_len += 3 + s->static_len;
! 2391: } else {
! 2392: send_bits(s, (DYN_TREES<<1)+eof, 3);
! 2393: send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
! 2394: max_blindex+1);
! 2395: compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
! 2396: s->compressed_len += 3 + s->opt_len;
! 2397: }
! 2398: Assert (s->compressed_len == s->bits_sent, "bad compressed size");
! 2399: init_block(s);
! 2400:
! 2401: if (eof) {
! 2402: bi_windup(s);
! 2403: s->compressed_len += 7; /* align on byte boundary */
! 2404: }
! 2405: Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
! 2406: s->compressed_len-7*eof));
! 2407:
! 2408: return s->compressed_len >> 3;
! 2409: }
! 2410:
! 2411: /* ===========================================================================
! 2412: * Save the match info and tally the frequency counts. Return true if
! 2413: * the current block must be flushed.
! 2414: */
! 2415: local int ct_tally (s, dist, lc)
! 2416: deflate_state *s;
! 2417: int dist; /* distance of matched string */
! 2418: int lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
! 2419: {
! 2420: s->d_buf[s->last_lit] = (ush)dist;
! 2421: s->l_buf[s->last_lit++] = (uch)lc;
! 2422: if (dist == 0) {
! 2423: /* lc is the unmatched char */
! 2424: s->dyn_ltree[lc].Freq++;
! 2425: } else {
! 2426: s->matches++;
! 2427: /* Here, lc is the match length - MIN_MATCH */
! 2428: dist--; /* dist = match distance - 1 */
! 2429: Assert((ush)dist < (ush)MAX_DIST(s) &&
! 2430: (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
! 2431: (ush)d_code(dist) < (ush)D_CODES, "ct_tally: bad match");
! 2432:
! 2433: s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
! 2434: s->dyn_dtree[d_code(dist)].Freq++;
! 2435: }
! 2436:
! 2437: /* Try to guess if it is profitable to stop the current block here */
! 2438: if (s->level > 2 && (s->last_lit & 0xfff) == 0) {
! 2439: /* Compute an upper bound for the compressed length */
! 2440: ulg out_length = (ulg)s->last_lit*8L;
! 2441: ulg in_length = (ulg)s->strstart - s->block_start;
! 2442: int dcode;
! 2443: for (dcode = 0; dcode < D_CODES; dcode++) {
! 2444: out_length += (ulg)s->dyn_dtree[dcode].Freq *
! 2445: (5L+extra_dbits[dcode]);
! 2446: }
! 2447: out_length >>= 3;
! 2448: Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
! 2449: s->last_lit, in_length, out_length,
! 2450: 100L - out_length*100L/in_length));
! 2451: if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
! 2452: }
! 2453: return (s->last_lit == s->lit_bufsize-1);
! 2454: /* We avoid equality with lit_bufsize because of wraparound at 64K
! 2455: * on 16 bit machines and because stored blocks are restricted to
! 2456: * 64K-1 bytes.
! 2457: */
! 2458: }
! 2459:
! 2460: /* ===========================================================================
! 2461: * Send the block data compressed using the given Huffman trees
! 2462: */
! 2463: local void compress_block(s, ltree, dtree)
! 2464: deflate_state *s;
! 2465: ct_data *ltree; /* literal tree */
! 2466: ct_data *dtree; /* distance tree */
! 2467: {
! 2468: unsigned dist; /* distance of matched string */
! 2469: int lc; /* match length or unmatched char (if dist == 0) */
! 2470: unsigned lx = 0; /* running index in l_buf */
! 2471: unsigned code; /* the code to send */
! 2472: int extra; /* number of extra bits to send */
! 2473:
! 2474: if (s->last_lit != 0) do {
! 2475: dist = s->d_buf[lx];
! 2476: lc = s->l_buf[lx++];
! 2477: if (dist == 0) {
! 2478: send_code(s, lc, ltree); /* send a literal byte */
! 2479: Tracecv(isgraph(lc), (stderr," '%c' ", lc));
! 2480: } else {
! 2481: /* Here, lc is the match length - MIN_MATCH */
! 2482: code = length_code[lc];
! 2483: send_code(s, code+LITERALS+1, ltree); /* send the length code */
! 2484: extra = extra_lbits[code];
! 2485: if (extra != 0) {
! 2486: lc -= base_length[code];
! 2487: send_bits(s, lc, extra); /* send the extra length bits */
! 2488: }
! 2489: dist--; /* dist is now the match distance - 1 */
! 2490: code = d_code(dist);
! 2491: Assert (code < D_CODES, "bad d_code");
! 2492:
! 2493: send_code(s, code, dtree); /* send the distance code */
! 2494: extra = extra_dbits[code];
! 2495: if (extra != 0) {
! 2496: dist -= base_dist[code];
! 2497: send_bits(s, dist, extra); /* send the extra distance bits */
! 2498: }
! 2499: } /* literal or match pair ? */
! 2500:
! 2501: /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
! 2502: Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow");
! 2503:
! 2504: } while (lx < s->last_lit);
! 2505:
! 2506: send_code(s, END_BLOCK, ltree);
! 2507: s->last_eob_len = ltree[END_BLOCK].Len;
! 2508: }
! 2509:
! 2510: /* ===========================================================================
! 2511: * Set the data type to ASCII or BINARY, using a crude approximation:
! 2512: * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
! 2513: * IN assertion: the fields freq of dyn_ltree are set and the total of all
! 2514: * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
! 2515: */
! 2516: local void set_data_type(s)
! 2517: deflate_state *s;
! 2518: {
! 2519: int n = 0;
! 2520: unsigned ascii_freq = 0;
! 2521: unsigned bin_freq = 0;
! 2522: while (n < 7) bin_freq += s->dyn_ltree[n++].Freq;
! 2523: while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq;
! 2524: while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
! 2525: s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? BINARY : ASCII);
! 2526: }
! 2527:
! 2528: /* ===========================================================================
! 2529: * Reverse the first len bits of a code, using straightforward code (a faster
! 2530: * method would use a table)
! 2531: * IN assertion: 1 <= len <= 15
! 2532: */
! 2533: local unsigned bi_reverse(code, len)
! 2534: unsigned code; /* the value to invert */
! 2535: int len; /* its bit length */
! 2536: {
! 2537: unsigned res = 0;
! 2538: do {
! 2539: res |= code & 1;
! 2540: code >>= 1, res <<= 1;
! 2541: } while (--len > 0);
! 2542: return res >> 1;
! 2543: }
! 2544:
! 2545: /* ===========================================================================
! 2546: * Flush the bit buffer, keeping at most 7 bits in it.
! 2547: */
! 2548: local void bi_flush(s)
! 2549: deflate_state *s;
! 2550: {
! 2551: if (s->bi_valid == 16) {
! 2552: put_short(s, s->bi_buf);
! 2553: s->bi_buf = 0;
! 2554: s->bi_valid = 0;
! 2555: } else if (s->bi_valid >= 8) {
! 2556: put_byte(s, (Byte)s->bi_buf);
! 2557: s->bi_buf >>= 8;
! 2558: s->bi_valid -= 8;
! 2559: }
! 2560: }
! 2561:
! 2562: /* ===========================================================================
! 2563: * Flush the bit buffer and align the output on a byte boundary
! 2564: */
! 2565: local void bi_windup(s)
! 2566: deflate_state *s;
! 2567: {
! 2568: if (s->bi_valid > 8) {
! 2569: put_short(s, s->bi_buf);
! 2570: } else if (s->bi_valid > 0) {
! 2571: put_byte(s, (Byte)s->bi_buf);
! 2572: }
! 2573: s->bi_buf = 0;
! 2574: s->bi_valid = 0;
! 2575: #ifdef DEBUG_ZLIB
! 2576: s->bits_sent = (s->bits_sent+7) & ~7;
! 2577: #endif
! 2578: }
! 2579:
! 2580: /* ===========================================================================
! 2581: * Copy a stored block, storing first the length and its
! 2582: * one's complement if requested.
! 2583: */
! 2584: local void copy_block(s, buf, len, header)
! 2585: deflate_state *s;
! 2586: charf *buf; /* the input data */
! 2587: unsigned len; /* its length */
! 2588: int header; /* true if block header must be written */
! 2589: {
! 2590: bi_windup(s); /* align on byte boundary */
! 2591: s->last_eob_len = 8; /* enough lookahead for inflate */
! 2592:
! 2593: if (header) {
! 2594: put_short(s, (ush)len);
! 2595: put_short(s, (ush)~len);
! 2596: #ifdef DEBUG_ZLIB
! 2597: s->bits_sent += 2*16;
! 2598: #endif
! 2599: }
! 2600: #ifdef DEBUG_ZLIB
! 2601: s->bits_sent += (ulg)len<<3;
! 2602: #endif
! 2603: while (len--) {
! 2604: put_byte(s, *buf++);
! 2605: }
! 2606: }
! 2607: #endif /* NO_DEFLATE */
! 2608:
! 2609: /*+++++*/
! 2610: /* infblock.h -- header to use infblock.c
! 2611: * Copyright (C) 1995 Mark Adler
! 2612: * For conditions of distribution and use, see copyright notice in zlib.h
! 2613: */
! 2614:
! 2615: /* WARNING: this file should *not* be used by applications. It is
! 2616: part of the implementation of the compression library and is
! 2617: subject to change. Applications should only use zlib.h.
! 2618: */
! 2619:
! 2620: struct inflate_blocks_state;
! 2621: typedef struct inflate_blocks_state FAR inflate_blocks_statef;
! 2622:
! 2623: local inflate_blocks_statef * inflate_blocks_new OF((
! 2624: z_stream *z,
! 2625: check_func c, /* check function */
! 2626: uInt w)); /* window size */
! 2627:
! 2628: local int inflate_blocks OF((
! 2629: inflate_blocks_statef *,
! 2630: z_stream *,
! 2631: int)); /* initial return code */
! 2632:
! 2633: local void inflate_blocks_reset OF((
! 2634: inflate_blocks_statef *,
! 2635: z_stream *,
! 2636: uLongf *)); /* check value on output */
! 2637:
! 2638: local int inflate_blocks_free OF((
! 2639: inflate_blocks_statef *,
! 2640: z_stream *,
! 2641: uLongf *)); /* check value on output */
! 2642:
! 2643: local int inflate_addhistory OF((
! 2644: inflate_blocks_statef *,
! 2645: z_stream *));
! 2646:
! 2647: local int inflate_packet_flush OF((
! 2648: inflate_blocks_statef *));
! 2649:
! 2650: /*+++++*/
! 2651: /* inftrees.h -- header to use inftrees.c
! 2652: * Copyright (C) 1995 Mark Adler
! 2653: * For conditions of distribution and use, see copyright notice in zlib.h
! 2654: */
! 2655:
! 2656: /* WARNING: this file should *not* be used by applications. It is
! 2657: part of the implementation of the compression library and is
! 2658: subject to change. Applications should only use zlib.h.
! 2659: */
! 2660:
! 2661: /* Huffman code lookup table entry--this entry is four bytes for machines
! 2662: that have 16-bit pointers (e.g. PC's in the small or medium model). */
! 2663:
! 2664: typedef struct inflate_huft_s FAR inflate_huft;
! 2665:
! 2666: struct inflate_huft_s {
! 2667: union {
! 2668: struct {
! 2669: Byte Exop; /* number of extra bits or operation */
! 2670: Byte Bits; /* number of bits in this code or subcode */
! 2671: } what;
! 2672: uInt Nalloc; /* number of these allocated here */
! 2673: Bytef *pad; /* pad structure to a power of 2 (4 bytes for */
! 2674: } word; /* 16-bit, 8 bytes for 32-bit machines) */
! 2675: union {
! 2676: uInt Base; /* literal, length base, or distance base */
! 2677: inflate_huft *Next; /* pointer to next level of table */
! 2678: } more;
! 2679: };
! 2680:
! 2681: #ifdef DEBUG_ZLIB
! 2682: local uInt inflate_hufts;
! 2683: #endif
! 2684:
! 2685: local int inflate_trees_bits OF((
! 2686: uIntf *, /* 19 code lengths */
! 2687: uIntf *, /* bits tree desired/actual depth */
! 2688: inflate_huft * FAR *, /* bits tree result */
! 2689: z_stream *)); /* for zalloc, zfree functions */
! 2690:
! 2691: local int inflate_trees_dynamic OF((
! 2692: uInt, /* number of literal/length codes */
! 2693: uInt, /* number of distance codes */
! 2694: uIntf *, /* that many (total) code lengths */
! 2695: uIntf *, /* literal desired/actual bit depth */
! 2696: uIntf *, /* distance desired/actual bit depth */
! 2697: inflate_huft * FAR *, /* literal/length tree result */
! 2698: inflate_huft * FAR *, /* distance tree result */
! 2699: z_stream *)); /* for zalloc, zfree functions */
! 2700:
! 2701: local int inflate_trees_fixed OF((
! 2702: uIntf *, /* literal desired/actual bit depth */
! 2703: uIntf *, /* distance desired/actual bit depth */
! 2704: inflate_huft * FAR *, /* literal/length tree result */
! 2705: inflate_huft * FAR *)); /* distance tree result */
! 2706:
! 2707: local int inflate_trees_free OF((
! 2708: inflate_huft *, /* tables to free */
! 2709: z_stream *)); /* for zfree function */
! 2710:
! 2711:
! 2712: /*+++++*/
! 2713: /* infcodes.h -- header to use infcodes.c
! 2714: * Copyright (C) 1995 Mark Adler
! 2715: * For conditions of distribution and use, see copyright notice in zlib.h
! 2716: */
! 2717:
! 2718: /* WARNING: this file should *not* be used by applications. It is
! 2719: part of the implementation of the compression library and is
! 2720: subject to change. Applications should only use zlib.h.
! 2721: */
! 2722:
! 2723: struct inflate_codes_state;
! 2724: typedef struct inflate_codes_state FAR inflate_codes_statef;
! 2725:
! 2726: local inflate_codes_statef *inflate_codes_new OF((
! 2727: uInt, uInt,
! 2728: inflate_huft *, inflate_huft *,
! 2729: z_stream *));
! 2730:
! 2731: local int inflate_codes OF((
! 2732: inflate_blocks_statef *,
! 2733: z_stream *,
! 2734: int));
! 2735:
! 2736: local void inflate_codes_free OF((
! 2737: inflate_codes_statef *,
! 2738: z_stream *));
! 2739:
! 2740:
! 2741: /*+++++*/
! 2742: /* inflate.c -- zlib interface to inflate modules
! 2743: * Copyright (C) 1995 Mark Adler
! 2744: * For conditions of distribution and use, see copyright notice in zlib.h
! 2745: */
! 2746:
! 2747: /* inflate private state */
! 2748: struct internal_state {
! 2749:
! 2750: /* mode */
! 2751: enum {
! 2752: METHOD, /* waiting for method byte */
! 2753: FLAG, /* waiting for flag byte */
! 2754: BLOCKS, /* decompressing blocks */
! 2755: CHECK4, /* four check bytes to go */
! 2756: CHECK3, /* three check bytes to go */
! 2757: CHECK2, /* two check bytes to go */
! 2758: CHECK1, /* one check byte to go */
! 2759: DONE, /* finished check, done */
! 2760: BAD} /* got an error--stay here */
! 2761: mode; /* current inflate mode */
! 2762:
! 2763: /* mode dependent information */
! 2764: union {
! 2765: uInt method; /* if FLAGS, method byte */
! 2766: struct {
! 2767: uLong was; /* computed check value */
! 2768: uLong need; /* stream check value */
! 2769: } check; /* if CHECK, check values to compare */
! 2770: uInt marker; /* if BAD, inflateSync's marker bytes count */
! 2771: } sub; /* submode */
! 2772:
! 2773: /* mode independent information */
! 2774: int nowrap; /* flag for no wrapper */
! 2775: uInt wbits; /* log2(window size) (8..15, defaults to 15) */
! 2776: inflate_blocks_statef
! 2777: *blocks; /* current inflate_blocks state */
! 2778:
! 2779: };
! 2780:
! 2781:
! 2782: int inflateReset(z)
! 2783: z_stream *z;
! 2784: {
! 2785: uLong c;
! 2786:
! 2787: if (z == Z_NULL || z->state == Z_NULL)
! 2788: return Z_STREAM_ERROR;
! 2789: z->total_in = z->total_out = 0;
! 2790: z->msg = Z_NULL;
! 2791: z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
! 2792: inflate_blocks_reset(z->state->blocks, z, &c);
! 2793: Trace((stderr, "inflate: reset\n"));
! 2794: return Z_OK;
! 2795: }
! 2796:
! 2797:
! 2798: int inflateEnd(z)
! 2799: z_stream *z;
! 2800: {
! 2801: uLong c;
! 2802:
! 2803: if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
! 2804: return Z_STREAM_ERROR;
! 2805: if (z->state->blocks != Z_NULL)
! 2806: inflate_blocks_free(z->state->blocks, z, &c);
! 2807: ZFREE(z, z->state, sizeof(struct internal_state));
! 2808: z->state = Z_NULL;
! 2809: Trace((stderr, "inflate: end\n"));
! 2810: return Z_OK;
! 2811: }
! 2812:
! 2813:
! 2814: int inflateInit2(z, w)
! 2815: z_stream *z;
! 2816: int w;
! 2817: {
! 2818: /* initialize state */
! 2819: if (z == Z_NULL)
! 2820: return Z_STREAM_ERROR;
! 2821: /* if (z->zalloc == Z_NULL) z->zalloc = zcalloc; */
! 2822: /* if (z->zfree == Z_NULL) z->zfree = zcfree; */
! 2823: if ((z->state = (struct internal_state FAR *)
! 2824: ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL)
! 2825: return Z_MEM_ERROR;
! 2826: z->state->blocks = Z_NULL;
! 2827:
! 2828: /* handle undocumented nowrap option (no zlib header or check) */
! 2829: z->state->nowrap = 0;
! 2830: if (w < 0)
! 2831: {
! 2832: w = - w;
! 2833: z->state->nowrap = 1;
! 2834: }
! 2835:
! 2836: /* set window size */
! 2837: if (w < 8 || w > 15)
! 2838: {
! 2839: inflateEnd(z);
! 2840: return Z_STREAM_ERROR;
! 2841: }
! 2842: z->state->wbits = (uInt)w;
! 2843:
! 2844: /* create inflate_blocks state */
! 2845: if ((z->state->blocks =
! 2846: inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, 1 << w))
! 2847: == Z_NULL)
! 2848: {
! 2849: inflateEnd(z);
! 2850: return Z_MEM_ERROR;
! 2851: }
! 2852: Trace((stderr, "inflate: allocated\n"));
! 2853:
! 2854: /* reset state */
! 2855: inflateReset(z);
! 2856: return Z_OK;
! 2857: }
! 2858:
! 2859:
! 2860: int inflateInit(z)
! 2861: z_stream *z;
! 2862: {
! 2863: return inflateInit2(z, DEF_WBITS);
! 2864: }
! 2865:
! 2866:
! 2867: #define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;}
! 2868: #define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)
! 2869:
! 2870: int inflate(z, f)
! 2871: z_stream *z;
! 2872: int f;
! 2873: {
! 2874: int r;
! 2875: uInt b;
! 2876:
! 2877: if (z == Z_NULL || z->next_in == Z_NULL)
! 2878: return Z_STREAM_ERROR;
! 2879: r = Z_BUF_ERROR;
! 2880: while (1) switch (z->state->mode)
! 2881: {
! 2882: case METHOD:
! 2883: NEEDBYTE
! 2884: if (((z->state->sub.method = NEXTBYTE) & 0xf) != DEFLATED)
! 2885: {
! 2886: z->state->mode = BAD;
! 2887: z->msg = "unknown compression method";
! 2888: z->state->sub.marker = 5; /* can't try inflateSync */
! 2889: break;
! 2890: }
! 2891: if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
! 2892: {
! 2893: z->state->mode = BAD;
! 2894: z->msg = "invalid window size";
! 2895: z->state->sub.marker = 5; /* can't try inflateSync */
! 2896: break;
! 2897: }
! 2898: z->state->mode = FLAG;
! 2899: case FLAG:
! 2900: NEEDBYTE
! 2901: if ((b = NEXTBYTE) & 0x20)
! 2902: {
! 2903: z->state->mode = BAD;
! 2904: z->msg = "invalid reserved bit";
! 2905: z->state->sub.marker = 5; /* can't try inflateSync */
! 2906: break;
! 2907: }
! 2908: if (((z->state->sub.method << 8) + b) % 31)
! 2909: {
! 2910: z->state->mode = BAD;
! 2911: z->msg = "incorrect header check";
! 2912: z->state->sub.marker = 5; /* can't try inflateSync */
! 2913: break;
! 2914: }
! 2915: Trace((stderr, "inflate: zlib header ok\n"));
! 2916: z->state->mode = BLOCKS;
! 2917: case BLOCKS:
! 2918: r = inflate_blocks(z->state->blocks, z, r);
! 2919: if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
! 2920: r = inflate_packet_flush(z->state->blocks);
! 2921: if (r == Z_DATA_ERROR)
! 2922: {
! 2923: z->state->mode = BAD;
! 2924: z->state->sub.marker = 0; /* can try inflateSync */
! 2925: break;
! 2926: }
! 2927: if (r != Z_STREAM_END)
! 2928: return r;
! 2929: r = Z_OK;
! 2930: inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
! 2931: if (z->state->nowrap)
! 2932: {
! 2933: z->state->mode = DONE;
! 2934: break;
! 2935: }
! 2936: z->state->mode = CHECK4;
! 2937: case CHECK4:
! 2938: NEEDBYTE
! 2939: z->state->sub.check.need = (uLong)NEXTBYTE << 24;
! 2940: z->state->mode = CHECK3;
! 2941: case CHECK3:
! 2942: NEEDBYTE
! 2943: z->state->sub.check.need += (uLong)NEXTBYTE << 16;
! 2944: z->state->mode = CHECK2;
! 2945: case CHECK2:
! 2946: NEEDBYTE
! 2947: z->state->sub.check.need += (uLong)NEXTBYTE << 8;
! 2948: z->state->mode = CHECK1;
! 2949: case CHECK1:
! 2950: NEEDBYTE
! 2951: z->state->sub.check.need += (uLong)NEXTBYTE;
! 2952:
! 2953: if (z->state->sub.check.was != z->state->sub.check.need)
! 2954: {
! 2955: z->state->mode = BAD;
! 2956: z->msg = "incorrect data check";
! 2957: z->state->sub.marker = 5; /* can't try inflateSync */
! 2958: break;
! 2959: }
! 2960: Trace((stderr, "inflate: zlib check ok\n"));
! 2961: z->state->mode = DONE;
! 2962: case DONE:
! 2963: return Z_STREAM_END;
! 2964: case BAD:
! 2965: return Z_DATA_ERROR;
! 2966: default:
! 2967: return Z_STREAM_ERROR;
! 2968: }
! 2969:
! 2970: empty:
! 2971: if (f != Z_PACKET_FLUSH)
! 2972: return r;
! 2973: z->state->mode = BAD;
! 2974: z->state->sub.marker = 0; /* can try inflateSync */
! 2975: return Z_DATA_ERROR;
! 2976: }
! 2977:
! 2978: /*
! 2979: * This subroutine adds the data at next_in/avail_in to the output history
! 2980: * without performing any output. The output buffer must be "caught up";
! 2981: * i.e. no pending output (hence s->read equals s->write), and the state must
! 2982: * be BLOCKS (i.e. we should be willing to see the start of a series of
! 2983: * BLOCKS). On exit, the output will also be caught up, and the checksum
! 2984: * will have been updated if need be.
! 2985: */
! 2986:
! 2987: int inflateIncomp(z)
! 2988: z_stream *z;
! 2989: {
! 2990: if (z->state->mode != BLOCKS)
! 2991: return Z_DATA_ERROR;
! 2992: return inflate_addhistory(z->state->blocks, z);
! 2993: }
! 2994:
! 2995:
! 2996: int inflateSync(z)
! 2997: z_stream *z;
! 2998: {
! 2999: uInt n; /* number of bytes to look at */
! 3000: Bytef *p; /* pointer to bytes */
! 3001: uInt m; /* number of marker bytes found in a row */
! 3002: uLong r, w; /* temporaries to save total_in and total_out */
! 3003:
! 3004: /* set up */
! 3005: if (z == Z_NULL || z->state == Z_NULL)
! 3006: return Z_STREAM_ERROR;
! 3007: if (z->state->mode != BAD)
! 3008: {
! 3009: z->state->mode = BAD;
! 3010: z->state->sub.marker = 0;
! 3011: }
! 3012: if ((n = z->avail_in) == 0)
! 3013: return Z_BUF_ERROR;
! 3014: p = z->next_in;
! 3015: m = z->state->sub.marker;
! 3016:
! 3017: /* search */
! 3018: while (n && m < 4)
! 3019: {
! 3020: if (*p == (Byte)(m < 2 ? 0 : 0xff))
! 3021: m++;
! 3022: else if (*p)
! 3023: m = 0;
! 3024: else
! 3025: m = 4 - m;
! 3026: p++, n--;
! 3027: }
! 3028:
! 3029: /* restore */
! 3030: z->total_in += p - z->next_in;
! 3031: z->next_in = p;
! 3032: z->avail_in = n;
! 3033: z->state->sub.marker = m;
! 3034:
! 3035: /* return no joy or set up to restart on a new block */
! 3036: if (m != 4)
! 3037: return Z_DATA_ERROR;
! 3038: r = z->total_in; w = z->total_out;
! 3039: inflateReset(z);
! 3040: z->total_in = r; z->total_out = w;
! 3041: z->state->mode = BLOCKS;
! 3042: return Z_OK;
! 3043: }
! 3044:
! 3045: #undef NEEDBYTE
! 3046: #undef NEXTBYTE
! 3047:
! 3048: /*+++++*/
! 3049: /* infutil.h -- types and macros common to blocks and codes
! 3050: * Copyright (C) 1995 Mark Adler
! 3051: * For conditions of distribution and use, see copyright notice in zlib.h
! 3052: */
! 3053:
! 3054: /* WARNING: this file should *not* be used by applications. It is
! 3055: part of the implementation of the compression library and is
! 3056: subject to change. Applications should only use zlib.h.
! 3057: */
! 3058:
! 3059: /* inflate blocks semi-private state */
! 3060: struct inflate_blocks_state {
! 3061:
! 3062: /* mode */
! 3063: enum {
! 3064: TYPE, /* get type bits (3, including end bit) */
! 3065: LENS, /* get lengths for stored */
! 3066: STORED, /* processing stored block */
! 3067: TABLE, /* get table lengths */
! 3068: BTREE, /* get bit lengths tree for a dynamic block */
! 3069: DTREE, /* get length, distance trees for a dynamic block */
! 3070: CODES, /* processing fixed or dynamic block */
! 3071: DRY, /* output remaining window bytes */
! 3072: DONEB, /* finished last block, done */
! 3073: BADB} /* got a data error--stuck here */
! 3074: mode; /* current inflate_block mode */
! 3075:
! 3076: /* mode dependent information */
! 3077: union {
! 3078: uInt left; /* if STORED, bytes left to copy */
! 3079: struct {
! 3080: uInt table; /* table lengths (14 bits) */
! 3081: uInt index; /* index into blens (or border) */
! 3082: uIntf *blens; /* bit lengths of codes */
! 3083: uInt bb; /* bit length tree depth */
! 3084: inflate_huft *tb; /* bit length decoding tree */
! 3085: int nblens; /* # elements allocated at blens */
! 3086: } trees; /* if DTREE, decoding info for trees */
! 3087: struct {
! 3088: inflate_huft *tl, *td; /* trees to free */
! 3089: inflate_codes_statef
! 3090: *codes;
! 3091: } decode; /* if CODES, current state */
! 3092: } sub; /* submode */
! 3093: uInt last; /* true if this block is the last block */
! 3094:
! 3095: /* mode independent information */
! 3096: uInt bitk; /* bits in bit buffer */
! 3097: uLong bitb; /* bit buffer */
! 3098: Bytef *window; /* sliding window */
! 3099: Bytef *end; /* one byte after sliding window */
! 3100: Bytef *read; /* window read pointer */
! 3101: Bytef *write; /* window write pointer */
! 3102: check_func checkfn; /* check function */
! 3103: uLong check; /* check on output */
! 3104:
! 3105: };
! 3106:
! 3107:
! 3108: /* defines for inflate input/output */
! 3109: /* update pointers and return */
! 3110: #define UPDBITS {s->bitb=b;s->bitk=k;}
! 3111: #define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
! 3112: #define UPDOUT {s->write=q;}
! 3113: #define UPDATE {UPDBITS UPDIN UPDOUT}
! 3114: #define LEAVE {UPDATE return inflate_flush(s,z,r);}
! 3115: /* get bytes and bits */
! 3116: #define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
! 3117: #define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
! 3118: #define NEXTBYTE (n--,*p++)
! 3119: #define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
! 3120: #define DUMPBITS(j) {b>>=(j);k-=(j);}
! 3121: /* output bytes */
! 3122: #define WAVAIL (q<s->read?s->read-q-1:s->end-q)
! 3123: #define LOADOUT {q=s->write;m=WAVAIL;}
! 3124: #define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}}
! 3125: #define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
! 3126: #define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
! 3127: #define OUTBYTE(a) {*q++=(Byte)(a);m--;}
! 3128: /* load local pointers */
! 3129: #define LOAD {LOADIN LOADOUT}
! 3130:
! 3131: /* And'ing with mask[n] masks the lower n bits */
! 3132: local const uInt inflate_mask[] = {
! 3133: 0x0000,
! 3134: 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
! 3135: 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
! 3136: };
! 3137:
! 3138: /* copy as much as possible from the sliding window to the output area */
! 3139: local int inflate_flush OF((
! 3140: inflate_blocks_statef *,
! 3141: z_stream *,
! 3142: int));
! 3143:
! 3144: /*+++++*/
! 3145: /* inffast.h -- header to use inffast.c
! 3146: * Copyright (C) 1995 Mark Adler
! 3147: * For conditions of distribution and use, see copyright notice in zlib.h
! 3148: */
! 3149:
! 3150: /* WARNING: this file should *not* be used by applications. It is
! 3151: part of the implementation of the compression library and is
! 3152: subject to change. Applications should only use zlib.h.
! 3153: */
! 3154:
! 3155: local int inflate_fast OF((
! 3156: uInt,
! 3157: uInt,
! 3158: inflate_huft *,
! 3159: inflate_huft *,
! 3160: inflate_blocks_statef *,
! 3161: z_stream *));
! 3162:
! 3163:
! 3164: /*+++++*/
! 3165: /* infblock.c -- interpret and process block types to last block
! 3166: * Copyright (C) 1995 Mark Adler
! 3167: * For conditions of distribution and use, see copyright notice in zlib.h
! 3168: */
! 3169:
! 3170: /* Table for deflate from PKZIP's appnote.txt. */
! 3171: local uInt border[] = { /* Order of the bit length code lengths */
! 3172: 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
! 3173:
! 3174: /*
! 3175: Notes beyond the 1.93a appnote.txt:
! 3176:
! 3177: 1. Distance pointers never point before the beginning of the output
! 3178: stream.
! 3179: 2. Distance pointers can point back across blocks, up to 32k away.
! 3180: 3. There is an implied maximum of 7 bits for the bit length table and
! 3181: 15 bits for the actual data.
! 3182: 4. If only one code exists, then it is encoded using one bit. (Zero
! 3183: would be more efficient, but perhaps a little confusing.) If two
! 3184: codes exist, they are coded using one bit each (0 and 1).
! 3185: 5. There is no way of sending zero distance codes--a dummy must be
! 3186: sent if there are none. (History: a pre 2.0 version of PKZIP would
! 3187: store blocks with no distance codes, but this was discovered to be
! 3188: too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
! 3189: zero distance codes, which is sent as one code of zero bits in
! 3190: length.
! 3191: 6. There are up to 286 literal/length codes. Code 256 represents the
! 3192: end-of-block. Note however that the static length tree defines
! 3193: 288 codes just to fill out the Huffman codes. Codes 286 and 287
! 3194: cannot be used though, since there is no length base or extra bits
! 3195: defined for them. Similarily, there are up to 30 distance codes.
! 3196: However, static trees define 32 codes (all 5 bits) to fill out the
! 3197: Huffman codes, but the last two had better not show up in the data.
! 3198: 7. Unzip can check dynamic Huffman blocks for complete code sets.
! 3199: The exception is that a single code would not be complete (see #4).
! 3200: 8. The five bits following the block type is really the number of
! 3201: literal codes sent minus 257.
! 3202: 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
! 3203: (1+6+6). Therefore, to output three times the length, you output
! 3204: three codes (1+1+1), whereas to output four times the same length,
! 3205: you only need two codes (1+3). Hmm.
! 3206: 10. In the tree reconstruction algorithm, Code = Code + Increment
! 3207: only if BitLength(i) is not zero. (Pretty obvious.)
! 3208: 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
! 3209: 12. Note: length code 284 can represent 227-258, but length code 285
! 3210: really is 258. The last length deserves its own, short code
! 3211: since it gets used a lot in very redundant files. The length
! 3212: 258 is special since 258 - 3 (the min match length) is 255.
! 3213: 13. The literal/length and distance code bit lengths are read as a
! 3214: single stream of lengths. It is possible (and advantageous) for
! 3215: a repeat code (16, 17, or 18) to go across the boundary between
! 3216: the two sets of lengths.
! 3217: */
! 3218:
! 3219:
! 3220: local void inflate_blocks_reset(s, z, c)
! 3221: inflate_blocks_statef *s;
! 3222: z_stream *z;
! 3223: uLongf *c;
! 3224: {
! 3225: if (s->checkfn != Z_NULL)
! 3226: *c = s->check;
! 3227: if (s->mode == BTREE || s->mode == DTREE)
! 3228: ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
! 3229: if (s->mode == CODES)
! 3230: {
! 3231: inflate_codes_free(s->sub.decode.codes, z);
! 3232: inflate_trees_free(s->sub.decode.td, z);
! 3233: inflate_trees_free(s->sub.decode.tl, z);
! 3234: }
! 3235: s->mode = TYPE;
! 3236: s->bitk = 0;
! 3237: s->bitb = 0;
! 3238: s->read = s->write = s->window;
! 3239: if (s->checkfn != Z_NULL)
! 3240: s->check = (*s->checkfn)(0L, Z_NULL, 0);
! 3241: Trace((stderr, "inflate: blocks reset\n"));
! 3242: }
! 3243:
! 3244:
! 3245: local inflate_blocks_statef *inflate_blocks_new(z, c, w)
! 3246: z_stream *z;
! 3247: check_func c;
! 3248: uInt w;
! 3249: {
! 3250: inflate_blocks_statef *s;
! 3251:
! 3252: if ((s = (inflate_blocks_statef *)ZALLOC
! 3253: (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
! 3254: return s;
! 3255: if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
! 3256: {
! 3257: ZFREE(z, s, sizeof(struct inflate_blocks_state));
! 3258: return Z_NULL;
! 3259: }
! 3260: s->end = s->window + w;
! 3261: s->checkfn = c;
! 3262: s->mode = TYPE;
! 3263: Trace((stderr, "inflate: blocks allocated\n"));
! 3264: inflate_blocks_reset(s, z, &s->check);
! 3265: return s;
! 3266: }
! 3267:
! 3268:
! 3269: local int inflate_blocks(s, z, r)
! 3270: inflate_blocks_statef *s;
! 3271: z_stream *z;
! 3272: int r;
! 3273: {
! 3274: uInt t; /* temporary storage */
! 3275: uLong b; /* bit buffer */
! 3276: uInt k; /* bits in bit buffer */
! 3277: Bytef *p; /* input data pointer */
! 3278: uInt n; /* bytes available there */
! 3279: Bytef *q; /* output window write pointer */
! 3280: uInt m; /* bytes to end of window or read pointer */
! 3281:
! 3282: /* copy input/output information to locals (UPDATE macro restores) */
! 3283: LOAD
! 3284:
! 3285: /* process input based on current state */
! 3286: while (1) switch (s->mode)
! 3287: {
! 3288: case TYPE:
! 3289: NEEDBITS(3)
! 3290: t = (uInt)b & 7;
! 3291: s->last = t & 1;
! 3292: switch (t >> 1)
! 3293: {
! 3294: case 0: /* stored */
! 3295: Trace((stderr, "inflate: stored block%s\n",
! 3296: s->last ? " (last)" : ""));
! 3297: DUMPBITS(3)
! 3298: t = k & 7; /* go to byte boundary */
! 3299: DUMPBITS(t)
! 3300: s->mode = LENS; /* get length of stored block */
! 3301: break;
! 3302: case 1: /* fixed */
! 3303: Trace((stderr, "inflate: fixed codes block%s\n",
! 3304: s->last ? " (last)" : ""));
! 3305: {
! 3306: uInt bl, bd;
! 3307: inflate_huft *tl, *td;
! 3308:
! 3309: inflate_trees_fixed(&bl, &bd, &tl, &td);
! 3310: s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
! 3311: if (s->sub.decode.codes == Z_NULL)
! 3312: {
! 3313: r = Z_MEM_ERROR;
! 3314: LEAVE
! 3315: }
! 3316: s->sub.decode.tl = Z_NULL; /* don't try to free these */
! 3317: s->sub.decode.td = Z_NULL;
! 3318: }
! 3319: DUMPBITS(3)
! 3320: s->mode = CODES;
! 3321: break;
! 3322: case 2: /* dynamic */
! 3323: Trace((stderr, "inflate: dynamic codes block%s\n",
! 3324: s->last ? " (last)" : ""));
! 3325: DUMPBITS(3)
! 3326: s->mode = TABLE;
! 3327: break;
! 3328: case 3: /* illegal */
! 3329: DUMPBITS(3)
! 3330: s->mode = BADB;
! 3331: z->msg = "invalid block type";
! 3332: r = Z_DATA_ERROR;
! 3333: LEAVE
! 3334: }
! 3335: break;
! 3336: case LENS:
! 3337: NEEDBITS(32)
! 3338: if (((~b) >> 16) != (b & 0xffff))
! 3339: {
! 3340: s->mode = BADB;
! 3341: z->msg = "invalid stored block lengths";
! 3342: r = Z_DATA_ERROR;
! 3343: LEAVE
! 3344: }
! 3345: s->sub.left = (uInt)b & 0xffff;
! 3346: b = k = 0; /* dump bits */
! 3347: Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
! 3348: s->mode = s->sub.left ? STORED : TYPE;
! 3349: break;
! 3350: case STORED:
! 3351: if (n == 0)
! 3352: LEAVE
! 3353: NEEDOUT
! 3354: t = s->sub.left;
! 3355: if (t > n) t = n;
! 3356: if (t > m) t = m;
! 3357: zmemcpy(q, p, t);
! 3358: p += t; n -= t;
! 3359: q += t; m -= t;
! 3360: if ((s->sub.left -= t) != 0)
! 3361: break;
! 3362: Tracev((stderr, "inflate: stored end, %lu total out\n",
! 3363: z->total_out + (q >= s->read ? q - s->read :
! 3364: (s->end - s->read) + (q - s->window))));
! 3365: s->mode = s->last ? DRY : TYPE;
! 3366: break;
! 3367: case TABLE:
! 3368: NEEDBITS(14)
! 3369: s->sub.trees.table = t = (uInt)b & 0x3fff;
! 3370: #ifndef PKZIP_BUG_WORKAROUND
! 3371: if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
! 3372: {
! 3373: s->mode = BADB;
! 3374: z->msg = "too many length or distance symbols";
! 3375: r = Z_DATA_ERROR;
! 3376: LEAVE
! 3377: }
! 3378: #endif
! 3379: t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
! 3380: if (t < 19)
! 3381: t = 19;
! 3382: if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
! 3383: {
! 3384: r = Z_MEM_ERROR;
! 3385: LEAVE
! 3386: }
! 3387: s->sub.trees.nblens = t;
! 3388: DUMPBITS(14)
! 3389: s->sub.trees.index = 0;
! 3390: Tracev((stderr, "inflate: table sizes ok\n"));
! 3391: s->mode = BTREE;
! 3392: case BTREE:
! 3393: while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
! 3394: {
! 3395: NEEDBITS(3)
! 3396: s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
! 3397: DUMPBITS(3)
! 3398: }
! 3399: while (s->sub.trees.index < 19)
! 3400: s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
! 3401: s->sub.trees.bb = 7;
! 3402: t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
! 3403: &s->sub.trees.tb, z);
! 3404: if (t != Z_OK)
! 3405: {
! 3406: r = t;
! 3407: if (r == Z_DATA_ERROR)
! 3408: {
! 3409: ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
! 3410: s->mode = BADB;
! 3411: }
! 3412: LEAVE
! 3413: }
! 3414: s->sub.trees.index = 0;
! 3415: Tracev((stderr, "inflate: bits tree ok\n"));
! 3416: s->mode = DTREE;
! 3417: case DTREE:
! 3418: while (t = s->sub.trees.table,
! 3419: s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
! 3420: {
! 3421: inflate_huft *h;
! 3422: uInt i, j, c;
! 3423:
! 3424: t = s->sub.trees.bb;
! 3425: NEEDBITS(t)
! 3426: h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
! 3427: t = h->word.what.Bits;
! 3428: c = h->more.Base;
! 3429: if (c < 16)
! 3430: {
! 3431: DUMPBITS(t)
! 3432: s->sub.trees.blens[s->sub.trees.index++] = c;
! 3433: }
! 3434: else /* c == 16..18 */
! 3435: {
! 3436: i = c == 18 ? 7 : c - 14;
! 3437: j = c == 18 ? 11 : 3;
! 3438: NEEDBITS(t + i)
! 3439: DUMPBITS(t)
! 3440: j += (uInt)b & inflate_mask[i];
! 3441: DUMPBITS(i)
! 3442: i = s->sub.trees.index;
! 3443: t = s->sub.trees.table;
! 3444: if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
! 3445: (c == 16 && i < 1))
! 3446: {
! 3447: s->mode = BADB;
! 3448: z->msg = "invalid bit length repeat";
! 3449: r = Z_DATA_ERROR;
! 3450: LEAVE
! 3451: }
! 3452: c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
! 3453: do {
! 3454: s->sub.trees.blens[i++] = c;
! 3455: } while (--j);
! 3456: s->sub.trees.index = i;
! 3457: }
! 3458: }
! 3459: inflate_trees_free(s->sub.trees.tb, z);
! 3460: s->sub.trees.tb = Z_NULL;
! 3461: {
! 3462: uInt bl, bd;
! 3463: inflate_huft *tl, *td;
! 3464: inflate_codes_statef *c;
! 3465:
! 3466: bl = 9; /* must be <= 9 for lookahead assumptions */
! 3467: bd = 6; /* must be <= 9 for lookahead assumptions */
! 3468: t = s->sub.trees.table;
! 3469: t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
! 3470: s->sub.trees.blens, &bl, &bd, &tl, &td, z);
! 3471: if (t != Z_OK)
! 3472: {
! 3473: if (t == (uInt)Z_DATA_ERROR)
! 3474: {
! 3475: ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
! 3476: s->mode = BADB;
! 3477: }
! 3478: r = t;
! 3479: LEAVE
! 3480: }
! 3481: Tracev((stderr, "inflate: trees ok\n"));
! 3482: if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
! 3483: {
! 3484: inflate_trees_free(td, z);
! 3485: inflate_trees_free(tl, z);
! 3486: r = Z_MEM_ERROR;
! 3487: LEAVE
! 3488: }
! 3489: ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
! 3490: s->sub.decode.codes = c;
! 3491: s->sub.decode.tl = tl;
! 3492: s->sub.decode.td = td;
! 3493: }
! 3494: s->mode = CODES;
! 3495: case CODES:
! 3496: UPDATE
! 3497: if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
! 3498: return inflate_flush(s, z, r);
! 3499: r = Z_OK;
! 3500: inflate_codes_free(s->sub.decode.codes, z);
! 3501: inflate_trees_free(s->sub.decode.td, z);
! 3502: inflate_trees_free(s->sub.decode.tl, z);
! 3503: LOAD
! 3504: Tracev((stderr, "inflate: codes end, %lu total out\n",
! 3505: z->total_out + (q >= s->read ? q - s->read :
! 3506: (s->end - s->read) + (q - s->window))));
! 3507: if (!s->last)
! 3508: {
! 3509: s->mode = TYPE;
! 3510: break;
! 3511: }
! 3512: if (k > 7) /* return unused byte, if any */
! 3513: {
! 3514: Assert(k < 16, "inflate_codes grabbed too many bytes")
! 3515: k -= 8;
! 3516: n++;
! 3517: p--; /* can always return one */
! 3518: }
! 3519: s->mode = DRY;
! 3520: case DRY:
! 3521: FLUSH
! 3522: if (s->read != s->write)
! 3523: LEAVE
! 3524: s->mode = DONEB;
! 3525: case DONEB:
! 3526: r = Z_STREAM_END;
! 3527: LEAVE
! 3528: case BADB:
! 3529: r = Z_DATA_ERROR;
! 3530: LEAVE
! 3531: default:
! 3532: r = Z_STREAM_ERROR;
! 3533: LEAVE
! 3534: }
! 3535: }
! 3536:
! 3537:
! 3538: local int inflate_blocks_free(s, z, c)
! 3539: inflate_blocks_statef *s;
! 3540: z_stream *z;
! 3541: uLongf *c;
! 3542: {
! 3543: inflate_blocks_reset(s, z, c);
! 3544: ZFREE(z, s->window, s->end - s->window);
! 3545: ZFREE(z, s, sizeof(struct inflate_blocks_state));
! 3546: Trace((stderr, "inflate: blocks freed\n"));
! 3547: return Z_OK;
! 3548: }
! 3549:
! 3550: /*
! 3551: * This subroutine adds the data at next_in/avail_in to the output history
! 3552: * without performing any output. The output buffer must be "caught up";
! 3553: * i.e. no pending output (hence s->read equals s->write), and the state must
! 3554: * be BLOCKS (i.e. we should be willing to see the start of a series of
! 3555: * BLOCKS). On exit, the output will also be caught up, and the checksum
! 3556: * will have been updated if need be.
! 3557: */
! 3558: local int inflate_addhistory(s, z)
! 3559: inflate_blocks_statef *s;
! 3560: z_stream *z;
! 3561: {
! 3562: uLong b; /* bit buffer */ /* NOT USED HERE */
! 3563: uInt k; /* bits in bit buffer */ /* NOT USED HERE */
! 3564: uInt t; /* temporary storage */
! 3565: Bytef *p; /* input data pointer */
! 3566: uInt n; /* bytes available there */
! 3567: Bytef *q; /* output window write pointer */
! 3568: uInt m; /* bytes to end of window or read pointer */
! 3569:
! 3570: if (s->read != s->write)
! 3571: return Z_STREAM_ERROR;
! 3572: if (s->mode != TYPE)
! 3573: return Z_DATA_ERROR;
! 3574:
! 3575: /* we're ready to rock */
! 3576: LOAD
! 3577: /* while there is input ready, copy to output buffer, moving
! 3578: * pointers as needed.
! 3579: */
! 3580: while (n) {
! 3581: t = n; /* how many to do */
! 3582: /* is there room until end of buffer? */
! 3583: if (t > m) t = m;
! 3584: /* update check information */
! 3585: if (s->checkfn != Z_NULL)
! 3586: s->check = (*s->checkfn)(s->check, q, t);
! 3587: zmemcpy(q, p, t);
! 3588: q += t;
! 3589: p += t;
! 3590: n -= t;
! 3591: z->total_out += t;
! 3592: s->read = q; /* drag read pointer forward */
! 3593: /* WRAP */ /* expand WRAP macro by hand to handle s->read */
! 3594: if (q == s->end) {
! 3595: s->read = q = s->window;
! 3596: m = WAVAIL;
! 3597: }
! 3598: }
! 3599: UPDATE
! 3600: return Z_OK;
! 3601: }
! 3602:
! 3603:
! 3604: /*
! 3605: * At the end of a Deflate-compressed PPP packet, we expect to have seen
! 3606: * a `stored' block type value but not the (zero) length bytes.
! 3607: */
! 3608: local int inflate_packet_flush(s)
! 3609: inflate_blocks_statef *s;
! 3610: {
! 3611: if (s->mode != LENS)
! 3612: return Z_DATA_ERROR;
! 3613: s->mode = TYPE;
! 3614: return Z_OK;
! 3615: }
! 3616:
! 3617:
! 3618: /*+++++*/
! 3619: /* inftrees.c -- generate Huffman trees for efficient decoding
! 3620: * Copyright (C) 1995 Mark Adler
! 3621: * For conditions of distribution and use, see copyright notice in zlib.h
! 3622: */
! 3623:
! 3624: /* simplify the use of the inflate_huft type with some defines */
! 3625: #define base more.Base
! 3626: #define next more.Next
! 3627: #define exop word.what.Exop
! 3628: #define bits word.what.Bits
! 3629:
! 3630:
! 3631: local int huft_build OF((
! 3632: uIntf *, /* code lengths in bits */
! 3633: uInt, /* number of codes */
! 3634: uInt, /* number of "simple" codes */
! 3635: const uIntf *, /* list of base values for non-simple codes */
! 3636: const uIntf *, /* list of extra bits for non-simple codes */
! 3637: inflate_huft * FAR*,/* result: starting table */
! 3638: uIntf *, /* maximum lookup bits (returns actual) */
! 3639: z_stream *)); /* for zalloc function */
! 3640:
! 3641: local voidpf falloc OF((
! 3642: voidpf, /* opaque pointer (not used) */
! 3643: uInt, /* number of items */
! 3644: uInt)); /* size of item */
! 3645:
! 3646: local void ffree OF((
! 3647: voidpf q, /* opaque pointer (not used) */
! 3648: voidpf p, /* what to free (not used) */
! 3649: uInt n)); /* number of bytes (not used) */
! 3650:
! 3651: /* Tables for deflate from PKZIP's appnote.txt. */
! 3652: local const uInt cplens[] = { /* Copy lengths for literal codes 257..285 */
! 3653: 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
! 3654: 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
! 3655: /* actually lengths - 2; also see note #13 above about 258 */
! 3656: local const uInt cplext[] = { /* Extra bits for literal codes 257..285 */
! 3657: 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
! 3658: 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 192, 192}; /* 192==invalid */
! 3659: local const uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */
! 3660: 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
! 3661: 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
! 3662: 8193, 12289, 16385, 24577};
! 3663: local const uInt cpdext[] = { /* Extra bits for distance codes */
! 3664: 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
! 3665: 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
! 3666: 12, 12, 13, 13};
! 3667:
! 3668: /*
! 3669: Huffman code decoding is performed using a multi-level table lookup.
! 3670: The fastest way to decode is to simply build a lookup table whose
! 3671: size is determined by the longest code. However, the time it takes
! 3672: to build this table can also be a factor if the data being decoded
! 3673: is not very long. The most common codes are necessarily the
! 3674: shortest codes, so those codes dominate the decoding time, and hence
! 3675: the speed. The idea is you can have a shorter table that decodes the
! 3676: shorter, more probable codes, and then point to subsidiary tables for
! 3677: the longer codes. The time it costs to decode the longer codes is
! 3678: then traded against the time it takes to make longer tables.
! 3679:
! 3680: This results of this trade are in the variables lbits and dbits
! 3681: below. lbits is the number of bits the first level table for literal/
! 3682: length codes can decode in one step, and dbits is the same thing for
! 3683: the distance codes. Subsequent tables are also less than or equal to
! 3684: those sizes. These values may be adjusted either when all of the
! 3685: codes are shorter than that, in which case the longest code length in
! 3686: bits is used, or when the shortest code is *longer* than the requested
! 3687: table size, in which case the length of the shortest code in bits is
! 3688: used.
! 3689:
! 3690: There are two different values for the two tables, since they code a
! 3691: different number of possibilities each. The literal/length table
! 3692: codes 286 possible values, or in a flat code, a little over eight
! 3693: bits. The distance table codes 30 possible values, or a little less
! 3694: than five bits, flat. The optimum values for speed end up being
! 3695: about one bit more than those, so lbits is 8+1 and dbits is 5+1.
! 3696: The optimum values may differ though from machine to machine, and
! 3697: possibly even between compilers. Your mileage may vary.
! 3698: */
! 3699:
! 3700:
! 3701: /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
! 3702: #define BMAX 15 /* maximum bit length of any code */
! 3703: #define N_MAX 288 /* maximum number of codes in any set */
! 3704:
! 3705: #ifdef DEBUG_ZLIB
! 3706: uInt inflate_hufts;
! 3707: #endif
! 3708:
! 3709: local int huft_build(b, n, s, d, e, t, m, zs)
! 3710: uIntf *b; /* code lengths in bits (all assumed <= BMAX) */
! 3711: uInt n; /* number of codes (assumed <= N_MAX) */
! 3712: uInt s; /* number of simple-valued codes (0..s-1) */
! 3713: const uIntf *d; /* list of base values for non-simple codes */
! 3714: const uIntf *e; /* list of extra bits for non-simple codes */
! 3715: inflate_huft * FAR *t; /* result: starting table */
! 3716: uIntf *m; /* maximum lookup bits, returns actual */
! 3717: z_stream *zs; /* for zalloc function */
! 3718: /* Given a list of code lengths and a maximum table size, make a set of
! 3719: tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
! 3720: if the given code set is incomplete (the tables are still built in this
! 3721: case), Z_DATA_ERROR if the input is invalid (all zero length codes or an
! 3722: over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */
! 3723: {
! 3724:
! 3725: uInt a; /* counter for codes of length k */
! 3726: uInt c[BMAX+1]; /* bit length count table */
! 3727: uInt f; /* i repeats in table every f entries */
! 3728: int g; /* maximum code length */
! 3729: int h; /* table level */
! 3730: uInt i; /* counter, current code */
! 3731: uInt j; /* counter */
! 3732: int k; /* number of bits in current code */
! 3733: int l; /* bits per table (returned in m) */
! 3734: uIntf *p; /* pointer into c[], b[], or v[] */
! 3735: inflate_huft *q; /* points to current table */
! 3736: struct inflate_huft_s r; /* table entry for structure assignment */
! 3737: inflate_huft *u[BMAX]; /* table stack */
! 3738: uInt v[N_MAX]; /* values in order of bit length */
! 3739: int w; /* bits before this table == (l * h) */
! 3740: uInt x[BMAX+1]; /* bit offsets, then code stack */
! 3741: uIntf *xp; /* pointer into x */
! 3742: int y; /* number of dummy codes added */
! 3743: uInt z; /* number of entries in current table */
! 3744:
! 3745:
! 3746: /* Generate counts for each bit length */
! 3747: p = c;
! 3748: #define C0 *p++ = 0;
! 3749: #define C2 C0 C0 C0 C0
! 3750: #define C4 C2 C2 C2 C2
! 3751: C4 /* clear c[]--assume BMAX+1 is 16 */
! 3752: p = b; i = n;
! 3753: do {
! 3754: c[*p++]++; /* assume all entries <= BMAX */
! 3755: } while (--i);
! 3756: if (c[0] == n) /* null input--all zero length codes */
! 3757: {
! 3758: *t = (inflate_huft *)Z_NULL;
! 3759: *m = 0;
! 3760: return Z_OK;
! 3761: }
! 3762:
! 3763:
! 3764: /* Find minimum and maximum length, bound *m by those */
! 3765: l = *m;
! 3766: for (j = 1; j <= BMAX; j++)
! 3767: if (c[j])
! 3768: break;
! 3769: k = j; /* minimum code length */
! 3770: if ((uInt)l < j)
! 3771: l = j;
! 3772: for (i = BMAX; i; i--)
! 3773: if (c[i])
! 3774: break;
! 3775: g = i; /* maximum code length */
! 3776: if ((uInt)l > i)
! 3777: l = i;
! 3778: *m = l;
! 3779:
! 3780:
! 3781: /* Adjust last length count to fill out codes, if needed */
! 3782: for (y = 1 << j; j < i; j++, y <<= 1)
! 3783: if ((y -= c[j]) < 0)
! 3784: return Z_DATA_ERROR;
! 3785: if ((y -= c[i]) < 0)
! 3786: return Z_DATA_ERROR;
! 3787: c[i] += y;
! 3788:
! 3789:
! 3790: /* Generate starting offsets into the value table for each length */
! 3791: x[1] = j = 0;
! 3792: p = c + 1; xp = x + 2;
! 3793: while (--i) { /* note that i == g from above */
! 3794: *xp++ = (j += *p++);
! 3795: }
! 3796:
! 3797:
! 3798: /* Make a table of values in order of bit lengths */
! 3799: p = b; i = 0;
! 3800: do {
! 3801: if ((j = *p++) != 0)
! 3802: v[x[j]++] = i;
! 3803: } while (++i < n);
! 3804:
! 3805:
! 3806: /* Generate the Huffman codes and for each, make the table entries */
! 3807: x[0] = i = 0; /* first Huffman code is zero */
! 3808: p = v; /* grab values in bit order */
! 3809: h = -1; /* no tables yet--level -1 */
! 3810: w = -l; /* bits decoded == (l * h) */
! 3811: u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */
! 3812: q = (inflate_huft *)Z_NULL; /* ditto */
! 3813: z = 0; /* ditto */
! 3814:
! 3815: /* go through the bit lengths (k already is bits in shortest code) */
! 3816: for (; k <= g; k++)
! 3817: {
! 3818: a = c[k];
! 3819: while (a--)
! 3820: {
! 3821: /* here i is the Huffman code of length k bits for value *p */
! 3822: /* make tables up to required level */
! 3823: while (k > w + l)
! 3824: {
! 3825: h++;
! 3826: w += l; /* previous table always l bits */
! 3827:
! 3828: /* compute minimum size table less than or equal to l bits */
! 3829: z = (z = g - w) > (uInt)l ? l : z; /* table size upper limit */
! 3830: if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
! 3831: { /* too few codes for k-w bit table */
! 3832: f -= a + 1; /* deduct codes from patterns left */
! 3833: xp = c + k;
! 3834: if (j < z)
! 3835: while (++j < z) /* try smaller tables up to z bits */
! 3836: {
! 3837: if ((f <<= 1) <= *++xp)
! 3838: break; /* enough codes to use up j bits */
! 3839: f -= *xp; /* else deduct codes from patterns */
! 3840: }
! 3841: }
! 3842: z = 1 << j; /* table entries for j-bit table */
! 3843:
! 3844: /* allocate and link in new table */
! 3845: if ((q = (inflate_huft *)ZALLOC
! 3846: (zs,z + 1,sizeof(inflate_huft))) == Z_NULL)
! 3847: {
! 3848: if (h)
! 3849: inflate_trees_free(u[0], zs);
! 3850: return Z_MEM_ERROR; /* not enough memory */
! 3851: }
! 3852: q->word.Nalloc = z + 1;
! 3853: #ifdef DEBUG_ZLIB
! 3854: inflate_hufts += z + 1;
! 3855: #endif
! 3856: *t = q + 1; /* link to list for huft_free() */
! 3857: *(t = &(q->next)) = Z_NULL;
! 3858: u[h] = ++q; /* table starts after link */
! 3859:
! 3860: /* connect to last table, if there is one */
! 3861: if (h)
! 3862: {
! 3863: x[h] = i; /* save pattern for backing up */
! 3864: r.bits = (Byte)l; /* bits to dump before this table */
! 3865: r.exop = (Byte)j; /* bits in this table */
! 3866: r.next = q; /* pointer to this table */
! 3867: j = i >> (w - l); /* (get around Turbo C bug) */
! 3868: u[h-1][j] = r; /* connect to last table */
! 3869: }
! 3870: }
! 3871:
! 3872: /* set up table entry in r */
! 3873: r.bits = (Byte)(k - w);
! 3874: if (p >= v + n)
! 3875: r.exop = 128 + 64; /* out of values--invalid code */
! 3876: else if (*p < s)
! 3877: {
! 3878: r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */
! 3879: r.base = *p++; /* simple code is just the value */
! 3880: }
! 3881: else
! 3882: {
! 3883: r.exop = (Byte)e[*p - s] + 16 + 64; /* non-simple--look up in lists */
! 3884: r.base = d[*p++ - s];
! 3885: }
! 3886:
! 3887: /* fill code-like entries with r */
! 3888: f = 1 << (k - w);
! 3889: for (j = i >> w; j < z; j += f)
! 3890: q[j] = r;
! 3891:
! 3892: /* backwards increment the k-bit code i */
! 3893: for (j = 1 << (k - 1); i & j; j >>= 1)
! 3894: i ^= j;
! 3895: i ^= j;
! 3896:
! 3897: /* backup over finished tables */
! 3898: while ((i & ((1 << w) - 1)) != x[h])
! 3899: {
! 3900: h--; /* don't need to update q */
! 3901: w -= l;
! 3902: }
! 3903: }
! 3904: }
! 3905:
! 3906:
! 3907: /* Return Z_BUF_ERROR if we were given an incomplete table */
! 3908: return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
! 3909: }
! 3910:
! 3911:
! 3912: local int inflate_trees_bits(c, bb, tb, z)
! 3913: uIntf *c; /* 19 code lengths */
! 3914: uIntf *bb; /* bits tree desired/actual depth */
! 3915: inflate_huft * FAR *tb; /* bits tree result */
! 3916: z_stream *z; /* for zfree function */
! 3917: {
! 3918: int r;
! 3919:
! 3920: r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z);
! 3921: if (r == Z_DATA_ERROR)
! 3922: z->msg = "oversubscribed dynamic bit lengths tree";
! 3923: else if (r == Z_BUF_ERROR)
! 3924: {
! 3925: inflate_trees_free(*tb, z);
! 3926: z->msg = "incomplete dynamic bit lengths tree";
! 3927: r = Z_DATA_ERROR;
! 3928: }
! 3929: return r;
! 3930: }
! 3931:
! 3932:
! 3933: local int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z)
! 3934: uInt nl; /* number of literal/length codes */
! 3935: uInt nd; /* number of distance codes */
! 3936: uIntf *c; /* that many (total) code lengths */
! 3937: uIntf *bl; /* literal desired/actual bit depth */
! 3938: uIntf *bd; /* distance desired/actual bit depth */
! 3939: inflate_huft * FAR *tl; /* literal/length tree result */
! 3940: inflate_huft * FAR *td; /* distance tree result */
! 3941: z_stream *z; /* for zfree function */
! 3942: {
! 3943: int r;
! 3944:
! 3945: /* build literal/length tree */
! 3946: if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK)
! 3947: {
! 3948: if (r == Z_DATA_ERROR)
! 3949: z->msg = "oversubscribed literal/length tree";
! 3950: else if (r == Z_BUF_ERROR)
! 3951: {
! 3952: inflate_trees_free(*tl, z);
! 3953: z->msg = "incomplete literal/length tree";
! 3954: r = Z_DATA_ERROR;
! 3955: }
! 3956: return r;
! 3957: }
! 3958:
! 3959: /* build distance tree */
! 3960: if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK)
! 3961: {
! 3962: if (r == Z_DATA_ERROR)
! 3963: z->msg = "oversubscribed literal/length tree";
! 3964: else if (r == Z_BUF_ERROR) {
! 3965: #ifdef PKZIP_BUG_WORKAROUND
! 3966: r = Z_OK;
! 3967: }
! 3968: #else
! 3969: inflate_trees_free(*td, z);
! 3970: z->msg = "incomplete literal/length tree";
! 3971: r = Z_DATA_ERROR;
! 3972: }
! 3973: inflate_trees_free(*tl, z);
! 3974: return r;
! 3975: #endif
! 3976: }
! 3977:
! 3978: /* done */
! 3979: return Z_OK;
! 3980: }
! 3981:
! 3982:
! 3983: /* build fixed tables only once--keep them here */
! 3984: local int fixed_lock = 0;
! 3985: local int fixed_built = 0;
! 3986: #define FIXEDH 530 /* number of hufts used by fixed tables */
! 3987: local uInt fixed_left = FIXEDH;
! 3988: local inflate_huft fixed_mem[FIXEDH];
! 3989: local uInt fixed_bl;
! 3990: local uInt fixed_bd;
! 3991: local inflate_huft *fixed_tl;
! 3992: local inflate_huft *fixed_td;
! 3993:
! 3994:
! 3995: local voidpf falloc(q, n, s)
! 3996: voidpf q; /* opaque pointer (not used) */
! 3997: uInt n; /* number of items */
! 3998: uInt s; /* size of item */
! 3999: {
! 4000: Assert(s == sizeof(inflate_huft) && n <= fixed_left,
! 4001: "inflate_trees falloc overflow");
! 4002: if (q) s++; /* to make some compilers happy */
! 4003: fixed_left -= n;
! 4004: return (voidpf)(fixed_mem + fixed_left);
! 4005: }
! 4006:
! 4007:
! 4008: local void ffree(q, p, n)
! 4009: voidpf q;
! 4010: voidpf p;
! 4011: uInt n;
! 4012: {
! 4013: Assert(0, "inflate_trees ffree called!");
! 4014: if (q) q = p; /* to make some compilers happy */
! 4015: }
! 4016:
! 4017:
! 4018: local int inflate_trees_fixed(bl, bd, tl, td)
! 4019: uIntf *bl; /* literal desired/actual bit depth */
! 4020: uIntf *bd; /* distance desired/actual bit depth */
! 4021: inflate_huft * FAR *tl; /* literal/length tree result */
! 4022: inflate_huft * FAR *td; /* distance tree result */
! 4023: {
! 4024: /* build fixed tables if not built already--lock out other instances */
! 4025: while (++fixed_lock > 1)
! 4026: fixed_lock--;
! 4027: if (!fixed_built)
! 4028: {
! 4029: int k; /* temporary variable */
! 4030: unsigned c[288]; /* length list for huft_build */
! 4031: z_stream z; /* for falloc function */
! 4032:
! 4033: /* set up fake z_stream for memory routines */
! 4034: z.zalloc = falloc;
! 4035: z.zfree = ffree;
! 4036: z.opaque = Z_NULL;
! 4037:
! 4038: /* literal table */
! 4039: for (k = 0; k < 144; k++)
! 4040: c[k] = 8;
! 4041: for (; k < 256; k++)
! 4042: c[k] = 9;
! 4043: for (; k < 280; k++)
! 4044: c[k] = 7;
! 4045: for (; k < 288; k++)
! 4046: c[k] = 8;
! 4047: fixed_bl = 7;
! 4048: huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z);
! 4049:
! 4050: /* distance table */
! 4051: for (k = 0; k < 30; k++)
! 4052: c[k] = 5;
! 4053: fixed_bd = 5;
! 4054: huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z);
! 4055:
! 4056: /* done */
! 4057: fixed_built = 1;
! 4058: }
! 4059: fixed_lock--;
! 4060: *bl = fixed_bl;
! 4061: *bd = fixed_bd;
! 4062: *tl = fixed_tl;
! 4063: *td = fixed_td;
! 4064: return Z_OK;
! 4065: }
! 4066:
! 4067:
! 4068: local int inflate_trees_free(t, z)
! 4069: inflate_huft *t; /* table to free */
! 4070: z_stream *z; /* for zfree function */
! 4071: /* Free the malloc'ed tables built by huft_build(), which makes a linked
! 4072: list of the tables it made, with the links in a dummy first entry of
! 4073: each table. */
! 4074: {
! 4075: inflate_huft *p, *q;
! 4076:
! 4077: /* Go through linked list, freeing from the malloced (t[-1]) address. */
! 4078: p = t;
! 4079: while (p != Z_NULL)
! 4080: {
! 4081: q = (--p)->next;
! 4082: ZFREE(z, p, p->word.Nalloc * sizeof(inflate_huft));
! 4083: p = q;
! 4084: }
! 4085: return Z_OK;
! 4086: }
! 4087:
! 4088: /*+++++*/
! 4089: /* infcodes.c -- process literals and length/distance pairs
! 4090: * Copyright (C) 1995 Mark Adler
! 4091: * For conditions of distribution and use, see copyright notice in zlib.h
! 4092: */
! 4093:
! 4094: /* simplify the use of the inflate_huft type with some defines */
! 4095: #define base more.Base
! 4096: #define next more.Next
! 4097: #define exop word.what.Exop
! 4098: #define bits word.what.Bits
! 4099:
! 4100: /* inflate codes private state */
! 4101: struct inflate_codes_state {
! 4102:
! 4103: /* mode */
! 4104: enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
! 4105: START, /* x: set up for LEN */
! 4106: LEN, /* i: get length/literal/eob next */
! 4107: LENEXT, /* i: getting length extra (have base) */
! 4108: DIST, /* i: get distance next */
! 4109: DISTEXT, /* i: getting distance extra */
! 4110: COPY, /* o: copying bytes in window, waiting for space */
! 4111: LIT, /* o: got literal, waiting for output space */
! 4112: WASH, /* o: got eob, possibly still output waiting */
! 4113: END, /* x: got eob and all data flushed */
! 4114: BADCODE} /* x: got error */
! 4115: mode; /* current inflate_codes mode */
! 4116:
! 4117: /* mode dependent information */
! 4118: uInt len;
! 4119: union {
! 4120: struct {
! 4121: inflate_huft *tree; /* pointer into tree */
! 4122: uInt need; /* bits needed */
! 4123: } code; /* if LEN or DIST, where in tree */
! 4124: uInt lit; /* if LIT, literal */
! 4125: struct {
! 4126: uInt get; /* bits to get for extra */
! 4127: uInt dist; /* distance back to copy from */
! 4128: } copy; /* if EXT or COPY, where and how much */
! 4129: } sub; /* submode */
! 4130:
! 4131: /* mode independent information */
! 4132: Byte lbits; /* ltree bits decoded per branch */
! 4133: Byte dbits; /* dtree bits decoder per branch */
! 4134: inflate_huft *ltree; /* literal/length/eob tree */
! 4135: inflate_huft *dtree; /* distance tree */
! 4136:
! 4137: };
! 4138:
! 4139:
! 4140: local inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
! 4141: uInt bl, bd;
! 4142: inflate_huft *tl, *td;
! 4143: z_stream *z;
! 4144: {
! 4145: inflate_codes_statef *c;
! 4146:
! 4147: if ((c = (inflate_codes_statef *)
! 4148: ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
! 4149: {
! 4150: c->mode = START;
! 4151: c->lbits = (Byte)bl;
! 4152: c->dbits = (Byte)bd;
! 4153: c->ltree = tl;
! 4154: c->dtree = td;
! 4155: Tracev((stderr, "inflate: codes new\n"));
! 4156: }
! 4157: return c;
! 4158: }
! 4159:
! 4160:
! 4161: local int inflate_codes(s, z, r)
! 4162: inflate_blocks_statef *s;
! 4163: z_stream *z;
! 4164: int r;
! 4165: {
! 4166: uInt j; /* temporary storage */
! 4167: inflate_huft *t; /* temporary pointer */
! 4168: uInt e; /* extra bits or operation */
! 4169: uLong b; /* bit buffer */
! 4170: uInt k; /* bits in bit buffer */
! 4171: Bytef *p; /* input data pointer */
! 4172: uInt n; /* bytes available there */
! 4173: Bytef *q; /* output window write pointer */
! 4174: uInt m; /* bytes to end of window or read pointer */
! 4175: Bytef *f; /* pointer to copy strings from */
! 4176: inflate_codes_statef *c = s->sub.decode.codes; /* codes state */
! 4177:
! 4178: /* copy input/output information to locals (UPDATE macro restores) */
! 4179: LOAD
! 4180:
! 4181: /* process input and output based on current state */
! 4182: while (1) switch (c->mode)
! 4183: { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
! 4184: case START: /* x: set up for LEN */
! 4185: #ifndef SLOW
! 4186: if (m >= 258 && n >= 10)
! 4187: {
! 4188: UPDATE
! 4189: r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
! 4190: LOAD
! 4191: if (r != Z_OK)
! 4192: {
! 4193: c->mode = r == Z_STREAM_END ? WASH : BADCODE;
! 4194: break;
! 4195: }
! 4196: }
! 4197: #endif /* !SLOW */
! 4198: c->sub.code.need = c->lbits;
! 4199: c->sub.code.tree = c->ltree;
! 4200: c->mode = LEN;
! 4201: case LEN: /* i: get length/literal/eob next */
! 4202: j = c->sub.code.need;
! 4203: NEEDBITS(j)
! 4204: t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
! 4205: DUMPBITS(t->bits)
! 4206: e = (uInt)(t->exop);
! 4207: if (e == 0) /* literal */
! 4208: {
! 4209: c->sub.lit = t->base;
! 4210: Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
! 4211: "inflate: literal '%c'\n" :
! 4212: "inflate: literal 0x%02x\n", t->base));
! 4213: c->mode = LIT;
! 4214: break;
! 4215: }
! 4216: if (e & 16) /* length */
! 4217: {
! 4218: c->sub.copy.get = e & 15;
! 4219: c->len = t->base;
! 4220: c->mode = LENEXT;
! 4221: break;
! 4222: }
! 4223: if ((e & 64) == 0) /* next table */
! 4224: {
! 4225: c->sub.code.need = e;
! 4226: c->sub.code.tree = t->next;
! 4227: break;
! 4228: }
! 4229: if (e & 32) /* end of block */
! 4230: {
! 4231: Tracevv((stderr, "inflate: end of block\n"));
! 4232: c->mode = WASH;
! 4233: break;
! 4234: }
! 4235: c->mode = BADCODE; /* invalid code */
! 4236: z->msg = "invalid literal/length code";
! 4237: r = Z_DATA_ERROR;
! 4238: LEAVE
! 4239: case LENEXT: /* i: getting length extra (have base) */
! 4240: j = c->sub.copy.get;
! 4241: NEEDBITS(j)
! 4242: c->len += (uInt)b & inflate_mask[j];
! 4243: DUMPBITS(j)
! 4244: c->sub.code.need = c->dbits;
! 4245: c->sub.code.tree = c->dtree;
! 4246: Tracevv((stderr, "inflate: length %u\n", c->len));
! 4247: c->mode = DIST;
! 4248: case DIST: /* i: get distance next */
! 4249: j = c->sub.code.need;
! 4250: NEEDBITS(j)
! 4251: t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
! 4252: DUMPBITS(t->bits)
! 4253: e = (uInt)(t->exop);
! 4254: if (e & 16) /* distance */
! 4255: {
! 4256: c->sub.copy.get = e & 15;
! 4257: c->sub.copy.dist = t->base;
! 4258: c->mode = DISTEXT;
! 4259: break;
! 4260: }
! 4261: if ((e & 64) == 0) /* next table */
! 4262: {
! 4263: c->sub.code.need = e;
! 4264: c->sub.code.tree = t->next;
! 4265: break;
! 4266: }
! 4267: c->mode = BADCODE; /* invalid code */
! 4268: z->msg = "invalid distance code";
! 4269: r = Z_DATA_ERROR;
! 4270: LEAVE
! 4271: case DISTEXT: /* i: getting distance extra */
! 4272: j = c->sub.copy.get;
! 4273: NEEDBITS(j)
! 4274: c->sub.copy.dist += (uInt)b & inflate_mask[j];
! 4275: DUMPBITS(j)
! 4276: Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist));
! 4277: c->mode = COPY;
! 4278: case COPY: /* o: copying bytes in window, waiting for space */
! 4279: #ifndef __TURBOC__ /* Turbo C bug for following expression */
! 4280: f = (uInt)(q - s->window) < c->sub.copy.dist ?
! 4281: s->end - (c->sub.copy.dist - (q - s->window)) :
! 4282: q - c->sub.copy.dist;
! 4283: #else
! 4284: f = q - c->sub.copy.dist;
! 4285: if ((uInt)(q - s->window) < c->sub.copy.dist)
! 4286: f = s->end - (c->sub.copy.dist - (q - s->window));
! 4287: #endif
! 4288: while (c->len)
! 4289: {
! 4290: NEEDOUT
! 4291: OUTBYTE(*f++)
! 4292: if (f == s->end)
! 4293: f = s->window;
! 4294: c->len--;
! 4295: }
! 4296: c->mode = START;
! 4297: break;
! 4298: case LIT: /* o: got literal, waiting for output space */
! 4299: NEEDOUT
! 4300: OUTBYTE(c->sub.lit)
! 4301: c->mode = START;
! 4302: break;
! 4303: case WASH: /* o: got eob, possibly more output */
! 4304: FLUSH
! 4305: if (s->read != s->write)
! 4306: LEAVE
! 4307: c->mode = END;
! 4308: case END:
! 4309: r = Z_STREAM_END;
! 4310: LEAVE
! 4311: case BADCODE: /* x: got error */
! 4312: r = Z_DATA_ERROR;
! 4313: LEAVE
! 4314: default:
! 4315: r = Z_STREAM_ERROR;
! 4316: LEAVE
! 4317: }
! 4318: }
! 4319:
! 4320:
! 4321: local void inflate_codes_free(c, z)
! 4322: inflate_codes_statef *c;
! 4323: z_stream *z;
! 4324: {
! 4325: ZFREE(z, c, sizeof(struct inflate_codes_state));
! 4326: Tracev((stderr, "inflate: codes free\n"));
! 4327: }
! 4328:
! 4329: /*+++++*/
! 4330: /* inflate_util.c -- data and routines common to blocks and codes
! 4331: * Copyright (C) 1995 Mark Adler
! 4332: * For conditions of distribution and use, see copyright notice in zlib.h
! 4333: */
! 4334:
! 4335: /* copy as much as possible from the sliding window to the output area */
! 4336: local int inflate_flush(s, z, r)
! 4337: inflate_blocks_statef *s;
! 4338: z_stream *z;
! 4339: int r;
! 4340: {
! 4341: uInt n;
! 4342: Bytef *p, *q;
! 4343:
! 4344: /* local copies of source and destination pointers */
! 4345: p = z->next_out;
! 4346: q = s->read;
! 4347:
! 4348: /* compute number of bytes to copy as far as end of window */
! 4349: n = (uInt)((q <= s->write ? s->write : s->end) - q);
! 4350: if (n > z->avail_out) n = z->avail_out;
! 4351: if (n && r == Z_BUF_ERROR) r = Z_OK;
! 4352:
! 4353: /* update counters */
! 4354: z->avail_out -= n;
! 4355: z->total_out += n;
! 4356:
! 4357: /* update check information */
! 4358: if (s->checkfn != Z_NULL)
! 4359: s->check = (*s->checkfn)(s->check, q, n);
! 4360:
! 4361: /* copy as far as end of window */
! 4362: if (p != NULL) {
! 4363: zmemcpy(p, q, n);
! 4364: p += n;
! 4365: }
! 4366: q += n;
! 4367:
! 4368: /* see if more to copy at beginning of window */
! 4369: if (q == s->end)
! 4370: {
! 4371: /* wrap pointers */
! 4372: q = s->window;
! 4373: if (s->write == s->end)
! 4374: s->write = s->window;
! 4375:
! 4376: /* compute bytes to copy */
! 4377: n = (uInt)(s->write - q);
! 4378: if (n > z->avail_out) n = z->avail_out;
! 4379: if (n && r == Z_BUF_ERROR) r = Z_OK;
! 4380:
! 4381: /* update counters */
! 4382: z->avail_out -= n;
! 4383: z->total_out += n;
! 4384:
! 4385: /* update check information */
! 4386: if (s->checkfn != Z_NULL)
! 4387: s->check = (*s->checkfn)(s->check, q, n);
! 4388:
! 4389: /* copy */
! 4390: if (p != NULL) {
! 4391: zmemcpy(p, q, n);
! 4392: p += n;
! 4393: }
! 4394: q += n;
! 4395: }
! 4396:
! 4397: /* update pointers */
! 4398: z->next_out = p;
! 4399: s->read = q;
! 4400:
! 4401: /* done */
! 4402: return r;
! 4403: }
! 4404:
! 4405:
! 4406: /*+++++*/
! 4407: /* inffast.c -- process literals and length/distance pairs fast
! 4408: * Copyright (C) 1995 Mark Adler
! 4409: * For conditions of distribution and use, see copyright notice in zlib.h
! 4410: */
! 4411:
! 4412: /* simplify the use of the inflate_huft type with some defines */
! 4413: #define base more.Base
! 4414: #define next more.Next
! 4415: #define exop word.what.Exop
! 4416: #define bits word.what.Bits
! 4417:
! 4418: /* macros for bit input with no checking and for returning unused bytes */
! 4419: #define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
! 4420: #define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
! 4421:
! 4422: /* Called with number of bytes left to write in window at least 258
! 4423: (the maximum string length) and number of input bytes available
! 4424: at least ten. The ten bytes are six bytes for the longest length/
! 4425: distance pair plus four bytes for overloading the bit buffer. */
! 4426:
! 4427: local int inflate_fast(bl, bd, tl, td, s, z)
! 4428: uInt bl, bd;
! 4429: inflate_huft *tl, *td;
! 4430: inflate_blocks_statef *s;
! 4431: z_stream *z;
! 4432: {
! 4433: inflate_huft *t; /* temporary pointer */
! 4434: uInt e; /* extra bits or operation */
! 4435: uLong b; /* bit buffer */
! 4436: uInt k; /* bits in bit buffer */
! 4437: Bytef *p; /* input data pointer */
! 4438: uInt n; /* bytes available there */
! 4439: Bytef *q; /* output window write pointer */
! 4440: uInt m; /* bytes to end of window or read pointer */
! 4441: uInt ml; /* mask for literal/length tree */
! 4442: uInt md; /* mask for distance tree */
! 4443: uInt c; /* bytes to copy */
! 4444: uInt d; /* distance back to copy from */
! 4445: Bytef *r; /* copy source pointer */
! 4446:
! 4447: /* load input, output, bit values */
! 4448: LOAD
! 4449:
! 4450: /* initialize masks */
! 4451: ml = inflate_mask[bl];
! 4452: md = inflate_mask[bd];
! 4453:
! 4454: /* do until not enough input or output space for fast loop */
! 4455: do { /* assume called with m >= 258 && n >= 10 */
! 4456: /* get literal/length code */
! 4457: GRABBITS(20) /* max bits for literal/length code */
! 4458: if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
! 4459: {
! 4460: DUMPBITS(t->bits)
! 4461: Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
! 4462: "inflate: * literal '%c'\n" :
! 4463: "inflate: * literal 0x%02x\n", t->base));
! 4464: *q++ = (Byte)t->base;
! 4465: m--;
! 4466: continue;
! 4467: }
! 4468: do {
! 4469: DUMPBITS(t->bits)
! 4470: if (e & 16)
! 4471: {
! 4472: /* get extra bits for length */
! 4473: e &= 15;
! 4474: c = t->base + ((uInt)b & inflate_mask[e]);
! 4475: DUMPBITS(e)
! 4476: Tracevv((stderr, "inflate: * length %u\n", c));
! 4477:
! 4478: /* decode distance base of block to copy */
! 4479: GRABBITS(15); /* max bits for distance code */
! 4480: e = (t = td + ((uInt)b & md))->exop;
! 4481: do {
! 4482: DUMPBITS(t->bits)
! 4483: if (e & 16)
! 4484: {
! 4485: /* get extra bits to add to distance base */
! 4486: e &= 15;
! 4487: GRABBITS(e) /* get extra bits (up to 13) */
! 4488: d = t->base + ((uInt)b & inflate_mask[e]);
! 4489: DUMPBITS(e)
! 4490: Tracevv((stderr, "inflate: * distance %u\n", d));
! 4491:
! 4492: /* do the copy */
! 4493: m -= c;
! 4494: if ((uInt)(q - s->window) >= d) /* offset before dest */
! 4495: { /* just copy */
! 4496: r = q - d;
! 4497: *q++ = *r++; c--; /* minimum count is three, */
! 4498: *q++ = *r++; c--; /* so unroll loop a little */
! 4499: }
! 4500: else /* else offset after destination */
! 4501: {
! 4502: e = d - (q - s->window); /* bytes from offset to end */
! 4503: r = s->end - e; /* pointer to offset */
! 4504: if (c > e) /* if source crosses, */
! 4505: {
! 4506: c -= e; /* copy to end of window */
! 4507: do {
! 4508: *q++ = *r++;
! 4509: } while (--e);
! 4510: r = s->window; /* copy rest from start of window */
! 4511: }
! 4512: }
! 4513: do { /* copy all or what's left */
! 4514: *q++ = *r++;
! 4515: } while (--c);
! 4516: break;
! 4517: }
! 4518: else if ((e & 64) == 0)
! 4519: e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
! 4520: else
! 4521: {
! 4522: z->msg = "invalid distance code";
! 4523: UNGRAB
! 4524: UPDATE
! 4525: return Z_DATA_ERROR;
! 4526: }
! 4527: } while (1);
! 4528: break;
! 4529: }
! 4530: if ((e & 64) == 0)
! 4531: {
! 4532: if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0)
! 4533: {
! 4534: DUMPBITS(t->bits)
! 4535: Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
! 4536: "inflate: * literal '%c'\n" :
! 4537: "inflate: * literal 0x%02x\n", t->base));
! 4538: *q++ = (Byte)t->base;
! 4539: m--;
! 4540: break;
! 4541: }
! 4542: }
! 4543: else if (e & 32)
! 4544: {
! 4545: Tracevv((stderr, "inflate: * end of block\n"));
! 4546: UNGRAB
! 4547: UPDATE
! 4548: return Z_STREAM_END;
! 4549: }
! 4550: else
! 4551: {
! 4552: z->msg = "invalid literal/length code";
! 4553: UNGRAB
! 4554: UPDATE
! 4555: return Z_DATA_ERROR;
! 4556: }
! 4557: } while (1);
! 4558: } while (m >= 258 && n >= 10);
! 4559:
! 4560: /* not enough input or output--restore pointers and return */
! 4561: UNGRAB
! 4562: UPDATE
! 4563: return Z_OK;
! 4564: }
! 4565:
! 4566:
! 4567: /*+++++*/
! 4568: /* zutil.c -- target dependent utility functions for the compression library
! 4569: * Copyright (C) 1995 Jean-loup Gailly.
! 4570: * For conditions of distribution and use, see copyright notice in zlib.h
! 4571: */
! 4572:
! 4573: /* From: zutil.c,v 1.8 1995/05/03 17:27:12 jloup Exp */
! 4574:
! 4575: char *zlib_version = ZLIB_VERSION;
! 4576:
! 4577: #ifndef NO_DEFLATE
! 4578: char *z_errmsg[] = {
! 4579: "stream end", /* Z_STREAM_END 1 */
! 4580: "", /* Z_OK 0 */
! 4581: "file error", /* Z_ERRNO (-1) */
! 4582: "stream error", /* Z_STREAM_ERROR (-2) */
! 4583: "data error", /* Z_DATA_ERROR (-3) */
! 4584: "insufficient memory", /* Z_MEM_ERROR (-4) */
! 4585: "buffer error", /* Z_BUF_ERROR (-5) */
! 4586: ""};
! 4587: #endif /* NO_DEFLATE */
! 4588:
! 4589: /*+++++*/
! 4590: /* adler32.c -- compute the Adler-32 checksum of a data stream
! 4591: * Copyright (C) 1995 Mark Adler
! 4592: * For conditions of distribution and use, see copyright notice in zlib.h
! 4593: */
! 4594:
! 4595: /* From: adler32.c,v 1.6 1995/05/03 17:27:08 jloup Exp */
! 4596:
! 4597: #define BASE 65521L /* largest prime smaller than 65536 */
! 4598: #define NMAX 5552
! 4599: /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
! 4600:
! 4601: #define DO1(buf) {s1 += *buf++; s2 += s1;}
! 4602: #define DO2(buf) DO1(buf); DO1(buf);
! 4603: #define DO4(buf) DO2(buf); DO2(buf);
! 4604: #define DO8(buf) DO4(buf); DO4(buf);
! 4605: #define DO16(buf) DO8(buf); DO8(buf);
! 4606:
! 4607: /* ========================================================================= */
! 4608: uLong adler32(adler, buf, len)
! 4609: uLong adler;
! 4610: Bytef *buf;
! 4611: uInt len;
! 4612: {
! 4613: unsigned long s1 = adler & 0xffff;
! 4614: unsigned long s2 = (adler >> 16) & 0xffff;
! 4615: int k;
! 4616:
! 4617: if (buf == Z_NULL) return 1L;
! 4618:
! 4619: while (len > 0) {
! 4620: k = len < NMAX ? len : NMAX;
! 4621: len -= k;
! 4622: while (k >= 16) {
! 4623: DO16(buf);
! 4624: k -= 16;
! 4625: }
! 4626: if (k != 0) do {
! 4627: DO1(buf);
! 4628: } while (--k);
! 4629: s1 %= BASE;
! 4630: s2 %= BASE;
! 4631: }
! 4632: return (s2 << 16) | s1;
! 4633: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to zlib.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / net