1N/A/*
1N/A * This file is derived from various .h and .c files from the zlib-0.95
1N/A * distribution by Jean-loup Gailly and Mark Adler, with some additions
1N/A * by Paul Mackerras to aid in implementing Deflate compression and
1N/A * decompression for PPP packets. See zlib.h for conditions of
1N/A * distribution and use.
1N/A *
1N/A * Changes that have been made include:
1N/A * - changed functions not used outside this file to "local"
1N/A * - added minCompression parameter to deflateInit2
1N/A * - added Z_PACKET_FLUSH (see zlib.h for details)
1N/A * - added inflateIncomp
1N/A *
1N/A * $Id: zlib.c,v 1.2 1999/04/01 07:26:30 paulus Exp $
1N/A */
1N/A
1N/A
1N/A/*+++++*/
1N/A/* zutil.h -- internal interface and configuration of the compression library
1N/A * Copyright (C) 1995 Jean-loup Gailly.
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* WARNING: this file should *not* be used by applications. It is
1N/A part of the implementation of the compression library and is
1N/A subject to change. Applications should only use zlib.h.
1N/A */
1N/A
1N/A/* From: zutil.h,v 1.9 1995/05/03 17:27:12 jloup Exp */
1N/A
1N/A#define _Z_UTIL_H
1N/A
1N/A#include "zlib.h"
1N/A
1N/A#ifdef STDC
1N/A# include <string.h>
1N/A#endif
1N/A
1N/A#ifndef local
1N/A# define local static
1N/A#endif
1N/A/* compile with -Dlocal if your debugger can't find static symbols */
1N/A
1N/A#define FAR
1N/A
1N/Atypedef unsigned char uch;
1N/Atypedef uch FAR uchf;
1N/Atypedef unsigned short ush;
1N/Atypedef ush FAR ushf;
1N/Atypedef unsigned long ulg;
1N/A
1N/Aextern char *z_errmsg[]; /* indexed by 1-zlib_error */
1N/A
1N/A#define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err)
1N/A/* To be used only when the state is known to be valid */
1N/A
1N/A#ifndef NULL
1N/A#define NULL ((void *) 0)
1N/A#endif
1N/A
1N/A /* common constants */
1N/A
1N/A#define DEFLATED 8
1N/A
1N/A#ifndef DEF_WBITS
1N/A# define DEF_WBITS MAX_WBITS
1N/A#endif
1N/A/* default windowBits for decompression. MAX_WBITS is for compression only */
1N/A
1N/A#if MAX_MEM_LEVEL >= 8
1N/A# define DEF_MEM_LEVEL 8
1N/A#else
1N/A# define DEF_MEM_LEVEL MAX_MEM_LEVEL
1N/A#endif
1N/A/* default memLevel */
1N/A
1N/A#define STORED_BLOCK 0
1N/A#define STATIC_TREES 1
1N/A#define DYN_TREES 2
1N/A/* The three kinds of block type */
1N/A
1N/A#define MIN_MATCH 3
1N/A#define MAX_MATCH 258
1N/A/* The minimum and maximum match lengths */
1N/A
1N/A /* functions */
1N/A
1N/A#if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY)
1N/A# define HAVE_MEMCPY
1N/A#endif
1N/A#ifdef HAVE_MEMCPY
1N/A# define zmemcpy memcpy
1N/A# define zmemzero(dest, len) memset(dest, 0, len)
1N/A#else
1N/A# define zmemcpy(d, s, n) bcopy((s), (d), (n))
1N/A# define zmemzero bzero
1N/A#endif
1N/A
1N/A/* Diagnostic functions */
1N/A#ifdef DEBUG_ZLIB
1N/A# include <stdio.h>
1N/A# ifndef verbose
1N/A# define verbose 0
1N/A# endif
1N/A# define Assert(cond,msg) {if(!(cond)) z_error(msg);}
1N/A# define Trace(x) fprintf x
1N/A# define Tracev(x) {if (verbose) fprintf x ;}
1N/A# define Tracevv(x) {if (verbose>1) fprintf x ;}
1N/A# define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
1N/A# define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
1N/A#else
1N/A# define Assert(cond,msg)
1N/A# define Trace(x)
1N/A# define Tracev(x)
1N/A# define Tracevv(x)
1N/A# define Tracec(c,x)
1N/A# define Tracecv(c,x)
1N/A#endif
1N/A
1N/A
1N/Atypedef uLong (*check_func) OF((uLong check, Bytef *buf, uInt len));
1N/A
1N/A/* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */
1N/A/* void zcfree OF((voidpf opaque, voidpf ptr)); */
1N/A
1N/A#define ZALLOC(strm, items, size) \
1N/A (*((strm)->zalloc))((strm)->opaque, (items), (size))
1N/A#define ZFREE(strm, addr, size) \
1N/A (*((strm)->zfree))((strm)->opaque, (voidpf)(addr), (size))
1N/A#define TRY_FREE(s, p, n) {if (p) ZFREE(s, p, n);}
1N/A
1N/A/* deflate.h -- internal compression state
1N/A * Copyright (C) 1995 Jean-loup Gailly
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* WARNING: this file should *not* be used by applications. It is
1N/A part of the implementation of the compression library and is
1N/A subject to change. Applications should only use zlib.h.
1N/A */
1N/A
1N/A
1N/A/*+++++*/
1N/A/* From: deflate.h,v 1.5 1995/05/03 17:27:09 jloup Exp */
1N/A
1N/A/* ===========================================================================
1N/A * Internal compression state.
1N/A */
1N/A
1N/A/* Data type */
1N/A#define BINARY 0
1N/A#define ASCII 1
1N/A#define UNKNOWN 2
1N/A
1N/A#define LENGTH_CODES 29
1N/A/* number of length codes, not counting the special END_BLOCK code */
1N/A
1N/A#define LITERALS 256
1N/A/* number of literal bytes 0..255 */
1N/A
1N/A#define L_CODES (LITERALS+1+LENGTH_CODES)
1N/A/* number of Literal or Length codes, including the END_BLOCK code */
1N/A
1N/A#define D_CODES 30
1N/A/* number of distance codes */
1N/A
1N/A#define BL_CODES 19
1N/A/* number of codes used to transfer the bit lengths */
1N/A
1N/A#define HEAP_SIZE (2*L_CODES+1)
1N/A/* maximum heap size */
1N/A
1N/A#define MAX_BITS 15
1N/A/* All codes must not exceed MAX_BITS bits */
1N/A
1N/A#define INIT_STATE 42
1N/A#define BUSY_STATE 113
1N/A#define FLUSH_STATE 124
1N/A#define FINISH_STATE 666
1N/A/* Stream status */
1N/A
1N/A
1N/A/* Data structure describing a single value and its code string. */
1N/Atypedef struct ct_data_s {
1N/A union {
1N/A ush freq; /* frequency count */
1N/A ush code; /* bit string */
1N/A } fc;
1N/A union {
1N/A ush dad; /* father node in Huffman tree */
1N/A ush len; /* length of bit string */
1N/A } dl;
1N/A} FAR ct_data;
1N/A
1N/A#define Freq fc.freq
1N/A#define Code fc.code
1N/A#define Dad dl.dad
1N/A#define Len dl.len
1N/A
1N/Atypedef struct static_tree_desc_s static_tree_desc;
1N/A
1N/Atypedef struct tree_desc_s {
1N/A ct_data *dyn_tree; /* the dynamic tree */
1N/A int max_code; /* largest code with non zero frequency */
1N/A static_tree_desc *stat_desc; /* the corresponding static tree */
1N/A} FAR tree_desc;
1N/A
1N/Atypedef ush Pos;
1N/Atypedef Pos FAR Posf;
1N/Atypedef unsigned IPos;
1N/A
1N/A/* A Pos is an index in the character window. We use short instead of int to
1N/A * save space in the various tables. IPos is used only for parameter passing.
1N/A */
1N/A
1N/Atypedef struct deflate_state {
1N/A z_stream *strm; /* pointer back to this zlib stream */
1N/A int status; /* as the name implies */
1N/A Bytef *pending_buf; /* output still pending */
1N/A Bytef *pending_out; /* next pending byte to output to the stream */
1N/A int pending; /* nb of bytes in the pending buffer */
1N/A uLong adler; /* adler32 of uncompressed data */
1N/A int noheader; /* suppress zlib header and adler32 */
1N/A Byte data_type; /* UNKNOWN, BINARY or ASCII */
1N/A Byte method; /* STORED (for zip only) or DEFLATED */
1N/A int minCompr; /* min size decrease for Z_FLUSH_NOSTORE */
1N/A
1N/A /* used by deflate.c: */
1N/A
1N/A uInt w_size; /* LZ77 window size (32K by default) */
1N/A uInt w_bits; /* log2(w_size) (8..16) */
1N/A uInt w_mask; /* w_size - 1 */
1N/A
1N/A Bytef *window;
1N/A /* Sliding window. Input bytes are read into the second half of the window,
1N/A * and move to the first half later to keep a dictionary of at least wSize
1N/A * bytes. With this organization, matches are limited to a distance of
1N/A * wSize-MAX_MATCH bytes, but this ensures that IO is always
1N/A * performed with a length multiple of the block size. Also, it limits
1N/A * the window size to 64K, which is quite useful on MSDOS.
1N/A * To do: use the user input buffer as sliding window.
1N/A */
1N/A
1N/A ulg window_size;
1N/A /* Actual size of window: 2*wSize, except when the user input buffer
1N/A * is directly used as sliding window.
1N/A */
1N/A
1N/A Posf *prev;
1N/A /* Link to older string with same hash index. To limit the size of this
1N/A * array to 64K, this link is maintained only for the last 32K strings.
1N/A * An index in this array is thus a window index modulo 32K.
1N/A */
1N/A
1N/A Posf *head; /* Heads of the hash chains or NIL. */
1N/A
1N/A uInt ins_h; /* hash index of string to be inserted */
1N/A uInt hash_size; /* number of elements in hash table */
1N/A uInt hash_bits; /* log2(hash_size) */
1N/A uInt hash_mask; /* hash_size-1 */
1N/A
1N/A uInt hash_shift;
1N/A /* Number of bits by which ins_h must be shifted at each input
1N/A * step. It must be such that after MIN_MATCH steps, the oldest
1N/A * byte no longer takes part in the hash key, that is:
1N/A * hash_shift * MIN_MATCH >= hash_bits
1N/A */
1N/A
1N/A long block_start;
1N/A /* Window position at the beginning of the current output block. Gets
1N/A * negative when the window is moved backwards.
1N/A */
1N/A
1N/A uInt match_length; /* length of best match */
1N/A IPos prev_match; /* previous match */
1N/A int match_available; /* set if previous match exists */
1N/A uInt strstart; /* start of string to insert */
1N/A uInt match_start; /* start of matching string */
1N/A uInt lookahead; /* number of valid bytes ahead in window */
1N/A
1N/A uInt prev_length;
1N/A /* Length of the best match at previous step. Matches not greater than this
1N/A * are discarded. This is used in the lazy match evaluation.
1N/A */
1N/A
1N/A uInt max_chain_length;
1N/A /* To speed up deflation, hash chains are never searched beyond this
1N/A * length. A higher limit improves compression ratio but degrades the
1N/A * speed.
1N/A */
1N/A
1N/A uInt max_lazy_match;
1N/A /* Attempt to find a better match only when the current match is strictly
1N/A * smaller than this value. This mechanism is used only for compression
1N/A * levels >= 4.
1N/A */
1N/A# define max_insert_length max_lazy_match
1N/A /* Insert new strings in the hash table only if the match length is not
1N/A * greater than this length. This saves time but degrades compression.
1N/A * max_insert_length is used only for compression levels <= 3.
1N/A */
1N/A
1N/A int level; /* compression level (1..9) */
1N/A int strategy; /* favor or force Huffman coding*/
1N/A
1N/A uInt good_match;
1N/A /* Use a faster search when the previous match is longer than this */
1N/A
1N/A int nice_match; /* Stop searching when current match exceeds this */
1N/A
1N/A /* used by trees.c: */
1N/A /* Didn't use ct_data typedef below to suppress compiler warning */
1N/A struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */
1N/A struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
1N/A struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */
1N/A
1N/A struct tree_desc_s l_desc; /* desc. for literal tree */
1N/A struct tree_desc_s d_desc; /* desc. for distance tree */
1N/A struct tree_desc_s bl_desc; /* desc. for bit length tree */
1N/A
1N/A ush bl_count[MAX_BITS+1];
1N/A /* number of codes at each bit length for an optimal tree */
1N/A
1N/A int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
1N/A int heap_len; /* number of elements in the heap */
1N/A int heap_max; /* element of largest frequency */
1N/A /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
1N/A * The same heap array is used to build all trees.
1N/A */
1N/A
1N/A uch depth[2*L_CODES+1];
1N/A /* Depth of each subtree used as tie breaker for trees of equal frequency
1N/A */
1N/A
1N/A uchf *l_buf; /* buffer for literals or lengths */
1N/A
1N/A uInt lit_bufsize;
1N/A /* Size of match buffer for literals/lengths. There are 4 reasons for
1N/A * limiting lit_bufsize to 64K:
1N/A * - frequencies can be kept in 16 bit counters
1N/A * - if compression is not successful for the first block, all input
1N/A * data is still in the window so we can still emit a stored block even
1N/A * when input comes from standard input. (This can also be done for
1N/A * all blocks if lit_bufsize is not greater than 32K.)
1N/A * - if compression is not successful for a file smaller than 64K, we can
1N/A * even emit a stored file instead of a stored block (saving 5 bytes).
1N/A * This is applicable only for zip (not gzip or zlib).
1N/A * - creating new Huffman trees less frequently may not provide fast
1N/A * adaptation to changes in the input data statistics. (Take for
1N/A * example a binary file with poorly compressible code followed by
1N/A * a highly compressible string table.) Smaller buffer sizes give
1N/A * fast adaptation but have of course the overhead of transmitting
1N/A * trees more frequently.
1N/A * - I can't count above 4
1N/A */
1N/A
1N/A uInt last_lit; /* running index in l_buf */
1N/A
1N/A ushf *d_buf;
1N/A /* Buffer for distances. To simplify the code, d_buf and l_buf have
1N/A * the same number of elements. To use different lengths, an extra flag
1N/A * array would be necessary.
1N/A */
1N/A
1N/A ulg opt_len; /* bit length of current block with optimal trees */
1N/A ulg static_len; /* bit length of current block with static trees */
1N/A ulg compressed_len; /* total bit length of compressed file */
1N/A uInt matches; /* number of string matches in current block */
1N/A int last_eob_len; /* bit length of EOB code for last block */
1N/A
1N/A#ifdef DEBUG_ZLIB
1N/A ulg bits_sent; /* bit length of the compressed data */
1N/A#endif
1N/A
1N/A ush bi_buf;
1N/A /* Output buffer. bits are inserted starting at the bottom (least
1N/A * significant bits).
1N/A */
1N/A int bi_valid;
1N/A /* Number of valid bits in bi_buf. All bits above the last valid bit
1N/A * are always zero.
1N/A */
1N/A
1N/A uInt blocks_in_packet;
1N/A /* Number of blocks produced since the last time Z_PACKET_FLUSH
1N/A * was used.
1N/A */
1N/A
1N/A} FAR deflate_state;
1N/A
1N/A/* Output a byte on the stream.
1N/A * IN assertion: there is enough room in pending_buf.
1N/A */
1N/A#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
1N/A
1N/A
1N/A#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
1N/A/* Minimum amount of lookahead, except at the end of the input file.
1N/A * See deflate.c for comments about the MIN_MATCH+1.
1N/A */
1N/A
1N/A#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)
1N/A/* In order to simplify the code, particularly on 16 bit machines, match
1N/A * distances are limited to MAX_DIST instead of WSIZE.
1N/A */
1N/A
1N/A /* in trees.c */
1N/Alocal void ct_init OF((deflate_state *s));
1N/Alocal int ct_tally OF((deflate_state *s, int dist, int lc));
1N/Alocal ulg ct_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
1N/A int flush));
1N/Alocal void ct_align OF((deflate_state *s));
1N/Alocal void ct_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
1N/A int eof));
1N/Alocal void ct_stored_type_only OF((deflate_state *s));
1N/A
1N/A
1N/A/*+++++*/
1N/A/* deflate.c -- compress data using the deflation algorithm
1N/A * Copyright (C) 1995 Jean-loup Gailly.
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/*
1N/A * ALGORITHM
1N/A *
1N/A * The "deflation" process depends on being able to identify portions
1N/A * of the input text which are identical to earlier input (within a
1N/A * sliding window trailing behind the input currently being processed).
1N/A *
1N/A * The most straightforward technique turns out to be the fastest for
1N/A * most input files: try all possible matches and select the longest.
1N/A * The key feature of this algorithm is that insertions into the string
1N/A * dictionary are very simple and thus fast, and deletions are avoided
1N/A * completely. Insertions are performed at each input character, whereas
1N/A * string matches are performed only when the previous match ends. So it
1N/A * is preferable to spend more time in matches to allow very fast string
1N/A * insertions and avoid deletions. The matching algorithm for small
1N/A * strings is inspired from that of Rabin & Karp. A brute force approach
1N/A * is used to find longer strings when a small match has been found.
1N/A * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
1N/A * (by Leonid Broukhis).
1N/A * A previous version of this file used a more sophisticated algorithm
1N/A * (by Fiala and Greene) which is guaranteed to run in linear amortized
1N/A * time, but has a larger average cost, uses more memory and is patented.
1N/A * However the F&G algorithm may be faster for some highly redundant
1N/A * files if the parameter max_chain_length (described below) is too large.
1N/A *
1N/A * ACKNOWLEDGEMENTS
1N/A *
1N/A * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
1N/A * I found it in 'freeze' written by Leonid Broukhis.
1N/A * Thanks to many people for bug reports and testing.
1N/A *
1N/A * REFERENCES
1N/A *
1N/A * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
1N/A * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
1N/A *
1N/A * A description of the Rabin and Karp algorithm is given in the book
1N/A * "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
1N/A *
1N/A * Fiala,E.R., and Greene,D.H.
1N/A * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
1N/A *
1N/A */
1N/A
1N/A/* From: deflate.c,v 1.8 1995/05/03 17:27:08 jloup Exp */
1N/A
1N/Alocal char zlib_copyright[] = " deflate Copyright 1995 Jean-loup Gailly ";
1N/A/*
1N/A If you use the zlib library in a product, an acknowledgment is welcome
1N/A in the documentation of your product. If for some reason you cannot
1N/A include such an acknowledgment, I would appreciate that you keep this
1N/A copyright string in the executable of your product.
1N/A */
1N/A
1N/A#define NIL 0
1N/A/* Tail of hash chains */
1N/A
1N/A#ifndef TOO_FAR
1N/A# define TOO_FAR 4096
1N/A#endif
1N/A/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
1N/A
1N/A#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
1N/A/* Minimum amount of lookahead, except at the end of the input file.
1N/A * See deflate.c for comments about the MIN_MATCH+1.
1N/A */
1N/A
1N/A/* Values for max_lazy_match, good_match and max_chain_length, depending on
1N/A * the desired pack level (0..9). The values given below have been tuned to
1N/A * exclude worst case performance for pathological files. Better values may be
1N/A * found for specific files.
1N/A */
1N/A
1N/Atypedef struct config_s {
1N/A ush good_length; /* reduce lazy search above this match length */
1N/A ush max_lazy; /* do not perform lazy search above this match length */
1N/A ush nice_length; /* quit search above this match length */
1N/A ush max_chain;
1N/A} config;
1N/A
1N/Alocal config configuration_table[10] = {
1N/A/* good lazy nice chain */
1N/A/* 0 */ {0, 0, 0, 0}, /* store only */
1N/A/* 1 */ {4, 4, 8, 4}, /* maximum speed, no lazy matches */
1N/A/* 2 */ {4, 5, 16, 8},
1N/A/* 3 */ {4, 6, 32, 32},
1N/A
1N/A/* 4 */ {4, 4, 16, 16}, /* lazy matches */
1N/A/* 5 */ {8, 16, 32, 32},
1N/A/* 6 */ {8, 16, 128, 128},
1N/A/* 7 */ {8, 32, 128, 256},
1N/A/* 8 */ {32, 128, 258, 1024},
1N/A/* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
1N/A
1N/A/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
1N/A * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
1N/A * meaning.
1N/A */
1N/A
1N/A#define EQUAL 0
1N/A/* result of memcmp for equal strings */
1N/A
1N/A/* ===========================================================================
1N/A * Prototypes for local functions.
1N/A */
1N/A
1N/Alocal void fill_window OF((deflate_state *s));
1N/Alocal int deflate_fast OF((deflate_state *s, int flush));
1N/Alocal int deflate_slow OF((deflate_state *s, int flush));
1N/Alocal void lm_init OF((deflate_state *s));
1N/Alocal int longest_match OF((deflate_state *s, IPos cur_match));
1N/Alocal void putShortMSB OF((deflate_state *s, uInt b));
1N/Alocal void flush_pending OF((z_stream *strm));
1N/Alocal int read_buf OF((z_stream *strm, charf *buf, unsigned size));
1N/A#ifdef ASMV
1N/A void match_init OF((void)); /* asm code initialization */
1N/A#endif
1N/A
1N/A#ifdef DEBUG_ZLIB
1N/Alocal void check_match OF((deflate_state *s, IPos start, IPos match,
1N/A int length));
1N/A#endif
1N/A
1N/A
1N/A/* ===========================================================================
1N/A * Update a hash value with the given input byte
1N/A * IN assertion: all calls to to UPDATE_HASH are made with consecutive
1N/A * input characters, so that a running hash key can be computed from the
1N/A * previous key instead of complete recalculation each time.
1N/A */
1N/A#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
1N/A
1N/A
1N/A/* ===========================================================================
1N/A * Insert string str in the dictionary and set match_head to the previous head
1N/A * of the hash chain (the most recent string with same hash key). Return
1N/A * the previous length of the hash chain.
1N/A * IN assertion: all calls to to INSERT_STRING are made with consecutive
1N/A * input characters and the first MIN_MATCH bytes of str are valid
1N/A * (except for the last MIN_MATCH-1 bytes of the input file).
1N/A */
1N/A#define INSERT_STRING(s, str, match_head) \
1N/A (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
1N/A s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
1N/A s->head[s->ins_h] = (str))
1N/A
1N/A/* ===========================================================================
1N/A * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
1N/A * prev[] will be initialized on the fly.
1N/A */
1N/A#define CLEAR_HASH(s) \
1N/A s->head[s->hash_size-1] = NIL; \
1N/A zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
1N/A
1N/A/* ========================================================================= */
1N/Aint deflateInit (strm, level)
1N/A z_stream *strm;
1N/A int level;
1N/A{
1N/A return deflateInit2 (strm, level, DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
1N/A 0, 0);
1N/A /* To do: ignore strm->next_in if we use it as window */
1N/A}
1N/A
1N/A/* ========================================================================= */
1N/Aint deflateInit2 (strm, level, method, windowBits, memLevel,
1N/A strategy, minCompression)
1N/A z_stream *strm;
1N/A int level;
1N/A int method;
1N/A int windowBits;
1N/A int memLevel;
1N/A int strategy;
1N/A int minCompression;
1N/A{
1N/A deflate_state *s;
1N/A int noheader = 0;
1N/A
1N/A if (strm == Z_NULL) return Z_STREAM_ERROR;
1N/A
1N/A strm->msg = Z_NULL;
1N/A/* if (strm->zalloc == Z_NULL) strm->zalloc = zcalloc; */
1N/A/* if (strm->zfree == Z_NULL) strm->zfree = zcfree; */
1N/A
1N/A if (level == Z_DEFAULT_COMPRESSION) level = 6;
1N/A
1N/A if (windowBits < 0) { /* undocumented feature: suppress zlib header */
1N/A noheader = 1;
1N/A windowBits = -windowBits;
1N/A }
1N/A if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != DEFLATED ||
1N/A windowBits < 8 || windowBits > 15 || level < 1 || level > 9) {
1N/A return Z_STREAM_ERROR;
1N/A }
1N/A s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
1N/A if (s == Z_NULL) return Z_MEM_ERROR;
1N/A strm->state = (struct internal_state FAR *)s;
1N/A s->strm = strm;
1N/A
1N/A s->noheader = noheader;
1N/A s->w_bits = windowBits;
1N/A s->w_size = 1 << s->w_bits;
1N/A s->w_mask = s->w_size - 1;
1N/A
1N/A s->hash_bits = memLevel + 7;
1N/A s->hash_size = 1 << s->hash_bits;
1N/A s->hash_mask = s->hash_size - 1;
1N/A s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
1N/A
1N/A s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
1N/A s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
1N/A s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
1N/A
1N/A s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
1N/A
1N/A s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 2*sizeof(ush));
1N/A
1N/A if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
1N/A s->pending_buf == Z_NULL) {
1N/A strm->msg = z_errmsg[1-Z_MEM_ERROR];
1N/A deflateEnd (strm);
1N/A return Z_MEM_ERROR;
1N/A }
1N/A s->d_buf = (ushf *) &(s->pending_buf[s->lit_bufsize]);
1N/A s->l_buf = (uchf *) &(s->pending_buf[3*s->lit_bufsize]);
1N/A /* We overlay pending_buf and d_buf+l_buf. This works since the average
1N/A * output size for (length,distance) codes is <= 32 bits (worst case
1N/A * is 15+15+13=33).
1N/A */
1N/A
1N/A s->level = level;
1N/A s->strategy = strategy;
1N/A s->method = (Byte)method;
1N/A s->minCompr = minCompression;
1N/A s->blocks_in_packet = 0;
1N/A
1N/A return deflateReset(strm);
1N/A}
1N/A
1N/A/* ========================================================================= */
1N/Aint deflateReset (strm)
1N/A z_stream *strm;
1N/A{
1N/A deflate_state *s;
1N/A
1N/A if (strm == Z_NULL || strm->state == Z_NULL ||
1N/A strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR;
1N/A
1N/A strm->total_in = strm->total_out = 0;
1N/A strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
1N/A strm->data_type = Z_UNKNOWN;
1N/A
1N/A s = (deflate_state *)strm->state;
1N/A s->pending = 0;
1N/A s->pending_out = s->pending_buf;
1N/A
1N/A if (s->noheader < 0) {
1N/A s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
1N/A }
1N/A s->status = s->noheader ? BUSY_STATE : INIT_STATE;
1N/A s->adler = 1;
1N/A
1N/A ct_init(s);
1N/A lm_init(s);
1N/A
1N/A return Z_OK;
1N/A}
1N/A
1N/A/* =========================================================================
1N/A * Put a short in the pending buffer. The 16-bit value is put in MSB order.
1N/A * IN assertion: the stream state is correct and there is enough room in
1N/A * pending_buf.
1N/A */
1N/Alocal void putShortMSB (s, b)
1N/A deflate_state *s;
1N/A uInt b;
1N/A{
1N/A put_byte(s, (Byte)(b >> 8));
1N/A put_byte(s, (Byte)(b & 0xff));
1N/A}
1N/A
1N/A/* =========================================================================
1N/A * Flush as much pending output as possible.
1N/A */
1N/Alocal void flush_pending(strm)
1N/A z_stream *strm;
1N/A{
1N/A deflate_state *state = (deflate_state *) strm->state;
1N/A unsigned len = state->pending;
1N/A
1N/A if (len > strm->avail_out) len = strm->avail_out;
1N/A if (len == 0) return;
1N/A
1N/A if (strm->next_out != NULL) {
1N/A zmemcpy(strm->next_out, state->pending_out, len);
1N/A strm->next_out += len;
1N/A }
1N/A state->pending_out += len;
1N/A strm->total_out += len;
1N/A strm->avail_out -= len;
1N/A state->pending -= len;
1N/A if (state->pending == 0) {
1N/A state->pending_out = state->pending_buf;
1N/A }
1N/A}
1N/A
1N/A/* ========================================================================= */
1N/Aint deflate (strm, flush)
1N/A z_stream *strm;
1N/A int flush;
1N/A{
1N/A deflate_state *state = (deflate_state *) strm->state;
1N/A
1N/A if (strm == Z_NULL || state == Z_NULL) return Z_STREAM_ERROR;
1N/A
1N/A if (strm->next_in == Z_NULL && strm->avail_in != 0) {
1N/A ERR_RETURN(strm, Z_STREAM_ERROR);
1N/A }
1N/A if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
1N/A
1N/A state->strm = strm; /* just in case */
1N/A
1N/A /* Write the zlib header */
1N/A if (state->status == INIT_STATE) {
1N/A
1N/A uInt header = (DEFLATED + ((state->w_bits-8)<<4)) << 8;
1N/A uInt level_flags = (state->level-1) >> 1;
1N/A
1N/A if (level_flags > 3) level_flags = 3;
1N/A header |= (level_flags << 6);
1N/A header += 31 - (header % 31);
1N/A
1N/A state->status = BUSY_STATE;
1N/A putShortMSB(state, header);
1N/A }
1N/A
1N/A /* Flush as much pending output as possible */
1N/A if (state->pending != 0) {
1N/A flush_pending(strm);
1N/A if (strm->avail_out == 0) return Z_OK;
1N/A }
1N/A
1N/A /* If we came back in here to get the last output from
1N/A * a previous flush, we're done for now.
1N/A */
1N/A if (state->status == FLUSH_STATE) {
1N/A state->status = BUSY_STATE;
1N/A if (flush != Z_NO_FLUSH && flush != Z_FINISH)
1N/A return Z_OK;
1N/A }
1N/A
1N/A /* User must not provide more input after the first FINISH: */
1N/A if (state->status == FINISH_STATE && strm->avail_in != 0) {
1N/A ERR_RETURN(strm, Z_BUF_ERROR);
1N/A }
1N/A
1N/A /* Start a new block or continue the current one.
1N/A */
1N/A if (strm->avail_in != 0 || state->lookahead != 0 ||
1N/A (flush == Z_FINISH && state->status != FINISH_STATE)) {
1N/A int quit;
1N/A
1N/A if (flush == Z_FINISH) {
1N/A state->status = FINISH_STATE;
1N/A }
1N/A if (state->level <= 3) {
1N/A quit = deflate_fast(state, flush);
1N/A } else {
1N/A quit = deflate_slow(state, flush);
1N/A }
1N/A if (quit || strm->avail_out == 0)
1N/A return Z_OK;
1N/A /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
1N/A * of deflate should use the same flush parameter to make sure
1N/A * that the flush is complete. So we don't have to output an
1N/A * empty block here, this will be done at next call. This also
1N/A * ensures that for a very small output buffer, we emit at most
1N/A * one empty block.
1N/A */
1N/A }
1N/A
1N/A /* If a flush was requested, we have a little more to output now. */
1N/A if (flush != Z_NO_FLUSH && flush != Z_FINISH
1N/A && state->status != FINISH_STATE) {
1N/A switch (flush) {
1N/A case Z_PARTIAL_FLUSH:
1N/A ct_align(state);
1N/A break;
1N/A case Z_PACKET_FLUSH:
1N/A /* Output just the 3-bit `stored' block type value,
1N/A but not a zero length. */
1N/A ct_stored_type_only(state);
1N/A break;
1N/A default:
1N/A ct_stored_block(state, (char*)0, 0L, 0);
1N/A /* For a full flush, this empty block will be recognized
1N/A * as a special marker by inflate_sync().
1N/A */
1N/A if (flush == Z_FULL_FLUSH) {
1N/A CLEAR_HASH(state); /* forget history */
1N/A }
1N/A }
1N/A flush_pending(strm);
1N/A if (strm->avail_out == 0) {
1N/A /* We'll have to come back to get the rest of the output;
1N/A * this ensures we don't output a second zero-length stored
1N/A * block (or whatever).
1N/A */
1N/A state->status = FLUSH_STATE;
1N/A return Z_OK;
1N/A }
1N/A }
1N/A
1N/A Assert(strm->avail_out > 0, "bug2");
1N/A
1N/A if (flush != Z_FINISH) return Z_OK;
1N/A if (state->noheader) return Z_STREAM_END;
1N/A
1N/A /* Write the zlib trailer (adler32) */
1N/A putShortMSB(state, (uInt)(state->adler >> 16));
1N/A putShortMSB(state, (uInt)(state->adler & 0xffff));
1N/A flush_pending(strm);
1N/A /* If avail_out is zero, the application will call deflate again
1N/A * to flush the rest.
1N/A */
1N/A state->noheader = -1; /* write the trailer only once! */
1N/A return state->pending != 0 ? Z_OK : Z_STREAM_END;
1N/A}
1N/A
1N/A/* ========================================================================= */
1N/Aint deflateEnd (strm)
1N/A z_stream *strm;
1N/A{
1N/A deflate_state *state = (deflate_state *) strm->state;
1N/A
1N/A if (strm == Z_NULL || state == Z_NULL) return Z_STREAM_ERROR;
1N/A
1N/A TRY_FREE(strm, state->window, state->w_size * 2 * sizeof(Byte));
1N/A TRY_FREE(strm, state->prev, state->w_size * sizeof(Pos));
1N/A TRY_FREE(strm, state->head, state->hash_size * sizeof(Pos));
1N/A TRY_FREE(strm, state->pending_buf, state->lit_bufsize * 2 * sizeof(ush));
1N/A
1N/A ZFREE(strm, state, sizeof(deflate_state));
1N/A strm->state = Z_NULL;
1N/A
1N/A return Z_OK;
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Read a new buffer from the current input stream, update the adler32
1N/A * and total number of bytes read.
1N/A */
1N/Alocal int read_buf(strm, buf, size)
1N/A z_stream *strm;
1N/A charf *buf;
1N/A unsigned size;
1N/A{
1N/A unsigned len = strm->avail_in;
1N/A deflate_state *state = (deflate_state *) strm->state;
1N/A
1N/A if (len > size) len = size;
1N/A if (len == 0) return 0;
1N/A
1N/A strm->avail_in -= len;
1N/A
1N/A if (!state->noheader) {
1N/A state->adler = adler32(state->adler, strm->next_in, len);
1N/A }
1N/A zmemcpy(buf, strm->next_in, len);
1N/A strm->next_in += len;
1N/A strm->total_in += len;
1N/A
1N/A return (int)len;
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Initialize the "longest match" routines for a new zlib stream
1N/A */
1N/Alocal void lm_init (s)
1N/A deflate_state *s;
1N/A{
1N/A s->window_size = (ulg)2L*s->w_size;
1N/A
1N/A CLEAR_HASH(s);
1N/A
1N/A /* Set the default configuration parameters:
1N/A */
1N/A s->max_lazy_match = configuration_table[s->level].max_lazy;
1N/A s->good_match = configuration_table[s->level].good_length;
1N/A s->nice_match = configuration_table[s->level].nice_length;
1N/A s->max_chain_length = configuration_table[s->level].max_chain;
1N/A
1N/A s->strstart = 0;
1N/A s->block_start = 0L;
1N/A s->lookahead = 0;
1N/A s->match_length = MIN_MATCH-1;
1N/A s->match_available = 0;
1N/A s->ins_h = 0;
1N/A#ifdef ASMV
1N/A match_init(); /* initialize the asm code */
1N/A#endif
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Set match_start to the longest match starting at the given string and
1N/A * return its length. Matches shorter or equal to prev_length are discarded,
1N/A * in which case the result is equal to prev_length and match_start is
1N/A * garbage.
1N/A * IN assertions: cur_match is the head of the hash chain for the current
1N/A * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
1N/A */
1N/A#ifndef ASMV
1N/A/* For 80x86 and 680x0, an optimized version will be provided in match.asm or
1N/A * match.S. The code will be functionally equivalent.
1N/A */
1N/Alocal int longest_match(s, cur_match)
1N/A deflate_state *s;
1N/A IPos cur_match; /* current match */
1N/A{
1N/A unsigned chain_length = s->max_chain_length;/* max hash chain length */
1N/A register Bytef *scan = s->window + s->strstart; /* current string */
1N/A register Bytef *match; /* matched string */
1N/A register int len; /* length of current match */
1N/A int best_len = s->prev_length; /* best match length so far */
1N/A IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
1N/A s->strstart - (IPos)MAX_DIST(s) : NIL;
1N/A /* Stop when cur_match becomes <= limit. To simplify the code,
1N/A * we prevent matches with the string of window index 0.
1N/A */
1N/A Posf *prev = s->prev;
1N/A uInt wmask = s->w_mask;
1N/A
1N/A#ifdef UNALIGNED_OK
1N/A /* Compare two bytes at a time. Note: this is not always beneficial.
1N/A * Try with and without -DUNALIGNED_OK to check.
1N/A */
1N/A register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
1N/A register ush scan_start = *(ushf*)scan;
1N/A register ush scan_end = *(ushf*)(scan+best_len-1);
1N/A#else
1N/A register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1N/A register Byte scan_end1 = scan[best_len-1];
1N/A register Byte scan_end = scan[best_len];
1N/A#endif
1N/A
1N/A /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1N/A * It is easy to get rid of this optimization if necessary.
1N/A */
1N/A Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1N/A
1N/A /* Do not waste too much time if we already have a good match: */
1N/A if (s->prev_length >= s->good_match) {
1N/A chain_length >>= 2;
1N/A }
1N/A Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1N/A
1N/A do {
1N/A Assert(cur_match < s->strstart, "no future");
1N/A match = s->window + cur_match;
1N/A
1N/A /* Skip to next match if the match length cannot increase
1N/A * or if the match length is less than 2:
1N/A */
1N/A#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1N/A /* This code assumes sizeof(unsigned short) == 2. Do not use
1N/A * UNALIGNED_OK if your compiler uses a different size.
1N/A */
1N/A if (*(ushf*)(match+best_len-1) != scan_end ||
1N/A *(ushf*)match != scan_start) continue;
1N/A
1N/A /* It is not necessary to compare scan[2] and match[2] since they are
1N/A * always equal when the other bytes match, given that the hash keys
1N/A * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
1N/A * strstart+3, +5, ... up to strstart+257. We check for insufficient
1N/A * lookahead only every 4th comparison; the 128th check will be made
1N/A * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
1N/A * necessary to put more guard bytes at the end of the window, or
1N/A * to check more often for insufficient lookahead.
1N/A */
1N/A Assert(scan[2] == match[2], "scan[2]?");
1N/A scan++, match++;
1N/A do {
1N/A } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1N/A *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1N/A *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1N/A *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
1N/A scan < strend);
1N/A /* The funny "do {}" generates better code on most compilers */
1N/A
1N/A /* Here, scan <= window+strstart+257 */
1N/A Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1N/A if (*scan == *match) scan++;
1N/A
1N/A len = (MAX_MATCH - 1) - (int)(strend-scan);
1N/A scan = strend - (MAX_MATCH-1);
1N/A
1N/A#else /* UNALIGNED_OK */
1N/A
1N/A if (match[best_len] != scan_end ||
1N/A match[best_len-1] != scan_end1 ||
1N/A *match != *scan ||
1N/A *++match != scan[1]) continue;
1N/A
1N/A /* The check at best_len-1 can be removed because it will be made
1N/A * again later. (This heuristic is not always a win.)
1N/A * It is not necessary to compare scan[2] and match[2] since they
1N/A * are always equal when the other bytes match, given that
1N/A * the hash keys are equal and that HASH_BITS >= 8.
1N/A */
1N/A scan += 2, match++;
1N/A Assert(*scan == *match, "match[2]?");
1N/A
1N/A /* We check for insufficient lookahead only every 8th comparison;
1N/A * the 256th check will be made at strstart+258.
1N/A */
1N/A do {
1N/A } while (*++scan == *++match && *++scan == *++match &&
1N/A *++scan == *++match && *++scan == *++match &&
1N/A *++scan == *++match && *++scan == *++match &&
1N/A *++scan == *++match && *++scan == *++match &&
1N/A scan < strend);
1N/A
1N/A Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1N/A
1N/A len = MAX_MATCH - (int)(strend - scan);
1N/A scan = strend - MAX_MATCH;
1N/A
1N/A#endif /* UNALIGNED_OK */
1N/A
1N/A if (len > best_len) {
1N/A s->match_start = cur_match;
1N/A best_len = len;
1N/A if (len >= s->nice_match) break;
1N/A#ifdef UNALIGNED_OK
1N/A scan_end = *(ushf*)(scan+best_len-1);
1N/A#else
1N/A scan_end1 = scan[best_len-1];
1N/A scan_end = scan[best_len];
1N/A#endif
1N/A }
1N/A } while ((cur_match = prev[cur_match & wmask]) > limit
1N/A && --chain_length != 0);
1N/A
1N/A return best_len;
1N/A}
1N/A#endif /* ASMV */
1N/A
1N/A#ifdef DEBUG_ZLIB
1N/A/* ===========================================================================
1N/A * Check that the match at match_start is indeed a match.
1N/A */
1N/Alocal void check_match(s, start, match, length)
1N/A deflate_state *s;
1N/A IPos start, match;
1N/A int length;
1N/A{
1N/A /* check that the match is indeed a match */
1N/A if (memcmp((charf *)s->window + match,
1N/A (charf *)s->window + start, length) != EQUAL) {
1N/A fprintf(stderr,
1N/A " start %u, match %u, length %d\n",
1N/A start, match, length);
1N/A do { fprintf(stderr, "%c%c", s->window[match++],
1N/A s->window[start++]); } while (--length != 0);
1N/A z_error("invalid match");
1N/A }
1N/A if (verbose > 1) {
1N/A fprintf(stderr,"\\[%d,%d]", start-match, length);
1N/A do { putc(s->window[start++], stderr); } while (--length != 0);
1N/A }
1N/A}
1N/A#else
1N/A# define check_match(s, start, match, length)
1N/A#endif
1N/A
1N/A/* ===========================================================================
1N/A * Fill the window when the lookahead becomes insufficient.
1N/A * Updates strstart and lookahead.
1N/A *
1N/A * IN assertion: lookahead < MIN_LOOKAHEAD
1N/A * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
1N/A * At least one byte has been read, or avail_in == 0; reads are
1N/A * performed for at least two bytes (required for the zip translate_eol
1N/A * option -- not supported here).
1N/A */
1N/Alocal void fill_window(s)
1N/A deflate_state *s;
1N/A{
1N/A register unsigned n, m;
1N/A register Posf *p;
1N/A unsigned more; /* Amount of free space at the end of the window. */
1N/A uInt wsize = s->w_size;
1N/A
1N/A do {
1N/A more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
1N/A
1N/A /* Deal with !@#$% 64K limit: */
1N/A if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1N/A more = wsize;
1N/A } else if (more == (unsigned)(-1)) {
1N/A /* Very unlikely, but possible on 16 bit machine if strstart == 0
1N/A * and lookahead == 1 (input done one byte at time)
1N/A */
1N/A more--;
1N/A
1N/A /* If the window is almost full and there is insufficient lookahead,
1N/A * move the upper half to the lower one to make room in the upper half.
1N/A */
1N/A } else if (s->strstart >= wsize+MAX_DIST(s)) {
1N/A
1N/A /* By the IN assertion, the window is not empty so we can't confuse
1N/A * more == 0 with more == 64K on a 16 bit machine.
1N/A */
1N/A zmemcpy((charf *)s->window, (charf *)s->window+wsize,
1N/A (unsigned)wsize);
1N/A s->match_start -= wsize;
1N/A s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
1N/A
1N/A s->block_start -= (long) wsize;
1N/A
1N/A /* Slide the hash table (could be avoided with 32 bit values
1N/A at the expense of memory usage):
1N/A */
1N/A n = s->hash_size;
1N/A p = &s->head[n];
1N/A do {
1N/A m = *--p;
1N/A *p = (Pos)(m >= wsize ? m-wsize : NIL);
1N/A } while (--n);
1N/A
1N/A n = wsize;
1N/A p = &s->prev[n];
1N/A do {
1N/A m = *--p;
1N/A *p = (Pos)(m >= wsize ? m-wsize : NIL);
1N/A /* If n is not on any hash chain, prev[n] is garbage but
1N/A * its value will never be used.
1N/A */
1N/A } while (--n);
1N/A
1N/A more += wsize;
1N/A }
1N/A if (s->strm->avail_in == 0) return;
1N/A
1N/A /* If there was no sliding:
1N/A * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1N/A * more == window_size - lookahead - strstart
1N/A * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1N/A * => more >= window_size - 2*WSIZE + 2
1N/A * In the BIG_MEM or MMAP case (not yet supported),
1N/A * window_size == input_size + MIN_LOOKAHEAD &&
1N/A * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1N/A * Otherwise, window_size == 2*WSIZE so more >= 2.
1N/A * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1N/A */
1N/A Assert(more >= 2, "more < 2");
1N/A
1N/A n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead,
1N/A more);
1N/A s->lookahead += n;
1N/A
1N/A /* Initialize the hash value now that we have some input: */
1N/A if (s->lookahead >= MIN_MATCH) {
1N/A s->ins_h = s->window[s->strstart];
1N/A UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1N/A#if MIN_MATCH != 3
1N/A Call UPDATE_HASH() MIN_MATCH-3 more times
1N/A#endif
1N/A }
1N/A /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
1N/A * but this is not important since only literal bytes will be emitted.
1N/A */
1N/A
1N/A } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Flush the current block, with given end-of-file flag.
1N/A * IN assertion: strstart is set to the end of the current match.
1N/A */
1N/A#define FLUSH_BLOCK_ONLY(s, flush) { \
1N/A ct_flush_block(s, (s->block_start >= 0L ? \
1N/A (charf *)&s->window[(unsigned)s->block_start] : \
1N/A (charf *)Z_NULL), (long)s->strstart - s->block_start, (flush)); \
1N/A s->block_start = s->strstart; \
1N/A flush_pending(s->strm); \
1N/A Tracev((stderr,"[FLUSH]")); \
1N/A}
1N/A
1N/A/* Same but force premature exit if necessary. */
1N/A#define FLUSH_BLOCK(s, flush) { \
1N/A FLUSH_BLOCK_ONLY(s, flush); \
1N/A if (s->strm->avail_out == 0) return 1; \
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Compress as much as possible from the input stream, return true if
1N/A * processing was terminated prematurely (no more input or output space).
1N/A * This function does not perform lazy evaluationof matches and inserts
1N/A * new strings in the dictionary only for unmatched strings or for short
1N/A * matches. It is used only for the fast compression options.
1N/A */
1N/Alocal int deflate_fast(s, flush)
1N/A deflate_state *s;
1N/A int flush;
1N/A{
1N/A IPos hash_head = NIL; /* head of the hash chain */
1N/A int bflush; /* set if current block must be flushed */
1N/A
1N/A s->prev_length = MIN_MATCH-1;
1N/A
1N/A for (;;) {
1N/A /* Make sure that we always have enough lookahead, except
1N/A * at the end of the input file. We need MAX_MATCH bytes
1N/A * for the next match, plus MIN_MATCH bytes to insert the
1N/A * string following the next match.
1N/A */
1N/A if (s->lookahead < MIN_LOOKAHEAD) {
1N/A fill_window(s);
1N/A if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
1N/A
1N/A if (s->lookahead == 0) break; /* flush the current block */
1N/A }
1N/A
1N/A /* Insert the string window[strstart .. strstart+2] in the
1N/A * dictionary, and set hash_head to the head of the hash chain:
1N/A */
1N/A if (s->lookahead >= MIN_MATCH) {
1N/A INSERT_STRING(s, s->strstart, hash_head);
1N/A }
1N/A
1N/A /* Find the longest match, discarding those <= prev_length.
1N/A * At this point we have always match_length < MIN_MATCH
1N/A */
1N/A if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
1N/A /* To simplify the code, we prevent matches with the string
1N/A * of window index 0 (in particular we have to avoid a match
1N/A * of the string with itself at the start of the input file).
1N/A */
1N/A if (s->strategy != Z_HUFFMAN_ONLY) {
1N/A s->match_length = longest_match (s, hash_head);
1N/A }
1N/A /* longest_match() sets match_start */
1N/A
1N/A if (s->match_length > s->lookahead) s->match_length = s->lookahead;
1N/A }
1N/A if (s->match_length >= MIN_MATCH) {
1N/A check_match(s, s->strstart, s->match_start, s->match_length);
1N/A
1N/A bflush = ct_tally(s, s->strstart - s->match_start,
1N/A s->match_length - MIN_MATCH);
1N/A
1N/A s->lookahead -= s->match_length;
1N/A
1N/A /* Insert new strings in the hash table only if the match length
1N/A * is not too large. This saves time but degrades compression.
1N/A */
1N/A if (s->match_length <= s->max_insert_length &&
1N/A s->lookahead >= MIN_MATCH) {
1N/A s->match_length--; /* string at strstart already in hash table */
1N/A do {
1N/A s->strstart++;
1N/A INSERT_STRING(s, s->strstart, hash_head);
1N/A /* strstart never exceeds WSIZE-MAX_MATCH, so there are
1N/A * always MIN_MATCH bytes ahead.
1N/A */
1N/A } while (--s->match_length != 0);
1N/A s->strstart++;
1N/A } else {
1N/A s->strstart += s->match_length;
1N/A s->match_length = 0;
1N/A s->ins_h = s->window[s->strstart];
1N/A UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1N/A#if MIN_MATCH != 3
1N/A Call UPDATE_HASH() MIN_MATCH-3 more times
1N/A#endif
1N/A /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
1N/A * matter since it will be recomputed at next deflate call.
1N/A */
1N/A }
1N/A } else {
1N/A /* No match, output a literal byte */
1N/A Tracevv((stderr,"%c", s->window[s->strstart]));
1N/A bflush = ct_tally (s, 0, s->window[s->strstart]);
1N/A s->lookahead--;
1N/A s->strstart++;
1N/A }
1N/A if (bflush) FLUSH_BLOCK(s, Z_NO_FLUSH);
1N/A }
1N/A FLUSH_BLOCK(s, flush);
1N/A return 0; /* normal exit */
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Same as above, but achieves better compression. We use a lazy
1N/A * evaluation for matches: a match is finally adopted only if there is
1N/A * no better match at the next window position.
1N/A */
1N/Alocal int deflate_slow(s, flush)
1N/A deflate_state *s;
1N/A int flush;
1N/A{
1N/A IPos hash_head = NIL; /* head of hash chain */
1N/A int bflush; /* set if current block must be flushed */
1N/A
1N/A /* Process the input block. */
1N/A for (;;) {
1N/A /* Make sure that we always have enough lookahead, except
1N/A * at the end of the input file. We need MAX_MATCH bytes
1N/A * for the next match, plus MIN_MATCH bytes to insert the
1N/A * string following the next match.
1N/A */
1N/A if (s->lookahead < MIN_LOOKAHEAD) {
1N/A fill_window(s);
1N/A if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
1N/A
1N/A if (s->lookahead == 0) break; /* flush the current block */
1N/A }
1N/A
1N/A /* Insert the string window[strstart .. strstart+2] in the
1N/A * dictionary, and set hash_head to the head of the hash chain:
1N/A */
1N/A if (s->lookahead >= MIN_MATCH) {
1N/A INSERT_STRING(s, s->strstart, hash_head);
1N/A }
1N/A
1N/A /* Find the longest match, discarding those <= prev_length.
1N/A */
1N/A s->prev_length = s->match_length, s->prev_match = s->match_start;
1N/A s->match_length = MIN_MATCH-1;
1N/A
1N/A if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
1N/A s->strstart - hash_head <= MAX_DIST(s)) {
1N/A /* To simplify the code, we prevent matches with the string
1N/A * of window index 0 (in particular we have to avoid a match
1N/A * of the string with itself at the start of the input file).
1N/A */
1N/A if (s->strategy != Z_HUFFMAN_ONLY) {
1N/A s->match_length = longest_match (s, hash_head);
1N/A }
1N/A /* longest_match() sets match_start */
1N/A if (s->match_length > s->lookahead) s->match_length = s->lookahead;
1N/A
1N/A if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
1N/A (s->match_length == MIN_MATCH &&
1N/A s->strstart - s->match_start > TOO_FAR))) {
1N/A
1N/A /* If prev_match is also MIN_MATCH, match_start is garbage
1N/A * but we will ignore the current match anyway.
1N/A */
1N/A s->match_length = MIN_MATCH-1;
1N/A }
1N/A }
1N/A /* If there was a match at the previous step and the current
1N/A * match is not better, output the previous match:
1N/A */
1N/A if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
1N/A uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
1N/A /* Do not insert strings in hash table beyond this. */
1N/A
1N/A check_match(s, s->strstart-1, s->prev_match, s->prev_length);
1N/A
1N/A bflush = ct_tally(s, s->strstart -1 - s->prev_match,
1N/A s->prev_length - MIN_MATCH);
1N/A
1N/A /* Insert in hash table all strings up to the end of the match.
1N/A * strstart-1 and strstart are already inserted. If there is not
1N/A * enough lookahead, the last two strings are not inserted in
1N/A * the hash table.
1N/A */
1N/A s->lookahead -= s->prev_length-1;
1N/A s->prev_length -= 2;
1N/A do {
1N/A if (++s->strstart <= max_insert) {
1N/A INSERT_STRING(s, s->strstart, hash_head);
1N/A }
1N/A } while (--s->prev_length != 0);
1N/A s->match_available = 0;
1N/A s->match_length = MIN_MATCH-1;
1N/A s->strstart++;
1N/A
1N/A if (bflush) FLUSH_BLOCK(s, Z_NO_FLUSH);
1N/A
1N/A } else if (s->match_available) {
1N/A /* If there was no match at the previous position, output a
1N/A * single literal. If there was a match but the current match
1N/A * is longer, truncate the previous match to a single literal.
1N/A */
1N/A Tracevv((stderr,"%c", s->window[s->strstart-1]));
1N/A if (ct_tally (s, 0, s->window[s->strstart-1])) {
1N/A FLUSH_BLOCK_ONLY(s, Z_NO_FLUSH);
1N/A }
1N/A s->strstart++;
1N/A s->lookahead--;
1N/A if (s->strm->avail_out == 0) return 1;
1N/A } else {
1N/A /* There is no previous match to compare with, wait for
1N/A * the next step to decide.
1N/A */
1N/A s->match_available = 1;
1N/A s->strstart++;
1N/A s->lookahead--;
1N/A }
1N/A }
1N/A Assert (flush != Z_NO_FLUSH, "no flush?");
1N/A if (s->match_available) {
1N/A Tracevv((stderr,"%c", s->window[s->strstart-1]));
1N/A ct_tally (s, 0, s->window[s->strstart-1]);
1N/A s->match_available = 0;
1N/A }
1N/A FLUSH_BLOCK(s, flush);
1N/A return 0;
1N/A}
1N/A
1N/A
1N/A/*+++++*/
1N/A/* trees.c -- output deflated data using Huffman coding
1N/A * Copyright (C) 1995 Jean-loup Gailly
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/*
1N/A * ALGORITHM
1N/A *
1N/A * The "deflation" process uses several Huffman trees. The more
1N/A * common source values are represented by shorter bit sequences.
1N/A *
1N/A * Each code tree is stored in a compressed form which is itself
1N/A * a Huffman encoding of the lengths of all the code strings (in
1N/A * ascending order by source values). The actual code strings are
1N/A * reconstructed from the lengths in the inflate process, as described
1N/A * in the deflate specification.
1N/A *
1N/A * REFERENCES
1N/A *
1N/A * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
1N/A * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
1N/A *
1N/A * Storer, James A.
1N/A * Data Compression: Methods and Theory, pp. 49-50.
1N/A * Computer Science Press, 1988. ISBN 0-7167-8156-5.
1N/A *
1N/A * Sedgewick, R.
1N/A * Algorithms, p290.
1N/A * Addison-Wesley, 1983. ISBN 0-201-06672-6.
1N/A */
1N/A
1N/A/* From: trees.c,v 1.5 1995/05/03 17:27:12 jloup Exp */
1N/A
1N/A#ifdef DEBUG_ZLIB
1N/A# include <ctype.h>
1N/A#endif
1N/A
1N/A/* ===========================================================================
1N/A * Constants
1N/A */
1N/A
1N/A#define MAX_BL_BITS 7
1N/A/* Bit length codes must not exceed MAX_BL_BITS bits */
1N/A
1N/A#define END_BLOCK 256
1N/A/* end of block literal code */
1N/A
1N/A#define REP_3_6 16
1N/A/* repeat previous bit length 3-6 times (2 bits of repeat count) */
1N/A
1N/A#define REPZ_3_10 17
1N/A/* repeat a zero length 3-10 times (3 bits of repeat count) */
1N/A
1N/A#define REPZ_11_138 18
1N/A/* repeat a zero length 11-138 times (7 bits of repeat count) */
1N/A
1N/Alocal int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
1N/A = {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};
1N/A
1N/Alocal int extra_dbits[D_CODES] /* extra bits for each distance code */
1N/A = {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};
1N/A
1N/Alocal int extra_blbits[BL_CODES]/* extra bits for each bit length code */
1N/A = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
1N/A
1N/Alocal uch bl_order[BL_CODES]
1N/A = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
1N/A/* The lengths of the bit length codes are sent in order of decreasing
1N/A * probability, to avoid transmitting the lengths for unused bit length codes.
1N/A */
1N/A
1N/A#define Buf_size (8 * 2*sizeof(char))
1N/A/* Number of bits used within bi_buf. (bi_buf might be implemented on
1N/A * more than 16 bits on some systems.)
1N/A */
1N/A
1N/A/* ===========================================================================
1N/A * Local data. These are initialized only once.
1N/A * To do: initialize at compile time to be completely reentrant. ???
1N/A */
1N/A
1N/Alocal ct_data static_ltree[L_CODES+2];
1N/A/* The static literal tree. Since the bit lengths are imposed, there is no
1N/A * need for the L_CODES extra codes used during heap construction. However
1N/A * The codes 286 and 287 are needed to build a canonical tree (see ct_init
1N/A * below).
1N/A */
1N/A
1N/Alocal ct_data static_dtree[D_CODES];
1N/A/* The static distance tree. (Actually a trivial tree since all codes use
1N/A * 5 bits.)
1N/A */
1N/A
1N/Alocal uch dist_code[512];
1N/A/* distance codes. The first 256 values correspond to the distances
1N/A * 3 .. 258, the last 256 values correspond to the top 8 bits of
1N/A * the 15 bit distances.
1N/A */
1N/A
1N/Alocal uch length_code[MAX_MATCH-MIN_MATCH+1];
1N/A/* length code for each normalized match length (0 == MIN_MATCH) */
1N/A
1N/Alocal int base_length[LENGTH_CODES];
1N/A/* First normalized length for each code (0 = MIN_MATCH) */
1N/A
1N/Alocal int base_dist[D_CODES];
1N/A/* First normalized distance for each code (0 = distance of 1) */
1N/A
1N/Astruct static_tree_desc_s {
1N/A ct_data *static_tree; /* static tree or NULL */
1N/A intf *extra_bits; /* extra bits for each code or NULL */
1N/A int extra_base; /* base index for extra_bits */
1N/A int elems; /* max number of elements in the tree */
1N/A int max_length; /* max bit length for the codes */
1N/A};
1N/A
1N/Alocal static_tree_desc static_l_desc =
1N/A{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
1N/A
1N/Alocal static_tree_desc static_d_desc =
1N/A{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
1N/A
1N/Alocal static_tree_desc static_bl_desc =
1N/A{(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
1N/A
1N/A/* ===========================================================================
1N/A * Local (static) routines in this file.
1N/A */
1N/A
1N/Alocal void ct_static_init OF((void));
1N/Alocal void init_block OF((deflate_state *s));
1N/Alocal void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
1N/Alocal void gen_bitlen OF((deflate_state *s, tree_desc *desc));
1N/Alocal void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count));
1N/Alocal void build_tree OF((deflate_state *s, tree_desc *desc));
1N/Alocal void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
1N/Alocal void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
1N/Alocal int build_bl_tree OF((deflate_state *s));
1N/Alocal void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
1N/A int blcodes));
1N/Alocal void compress_block OF((deflate_state *s, ct_data *ltree,
1N/A ct_data *dtree));
1N/Alocal void set_data_type OF((deflate_state *s));
1N/Alocal unsigned bi_reverse OF((unsigned value, int length));
1N/Alocal void bi_windup OF((deflate_state *s));
1N/Alocal void bi_flush OF((deflate_state *s));
1N/Alocal void copy_block OF((deflate_state *s, charf *buf, unsigned len,
1N/A int header));
1N/A
1N/A#ifndef DEBUG_ZLIB
1N/A# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
1N/A /* Send a code of the given tree. c and tree must not have side effects */
1N/A
1N/A#else /* DEBUG_ZLIB */
1N/A# define send_code(s, c, tree) \
1N/A { if (verbose>1) fprintf(stderr,"\ncd %3d ",(c)); \
1N/A send_bits(s, tree[c].Code, tree[c].Len); }
1N/A#endif
1N/A
1N/A#define d_code(dist) \
1N/A ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
1N/A/* Mapping from a distance to a distance code. dist is the distance - 1 and
1N/A * must not have side effects. dist_code[256] and dist_code[257] are never
1N/A * used.
1N/A */
1N/A
1N/A/* ===========================================================================
1N/A * Output a short LSB first on the stream.
1N/A * IN assertion: there is enough room in pendingBuf.
1N/A */
1N/A#define put_short(s, w) { \
1N/A put_byte(s, (uch)((w) & 0xff)); \
1N/A put_byte(s, (uch)((ush)(w) >> 8)); \
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Send a value on a given number of bits.
1N/A * IN assertion: length <= 16 and value fits in length bits.
1N/A */
1N/A#ifdef DEBUG_ZLIB
1N/Alocal void send_bits OF((deflate_state *s, int value, int length));
1N/A
1N/Alocal void send_bits(s, value, length)
1N/A deflate_state *s;
1N/A int value; /* value to send */
1N/A int length; /* number of bits */
1N/A{
1N/A Tracev((stderr," l %2d v %4x ", length, value));
1N/A Assert(length > 0 && length <= 15, "invalid length");
1N/A s->bits_sent += (ulg)length;
1N/A
1N/A /* If not enough room in bi_buf, use (valid) bits from bi_buf and
1N/A * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
1N/A * unused bits in value.
1N/A */
1N/A if (s->bi_valid > (int)Buf_size - length) {
1N/A s->bi_buf |= (value << s->bi_valid);
1N/A put_short(s, s->bi_buf);
1N/A s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
1N/A s->bi_valid += length - Buf_size;
1N/A } else {
1N/A s->bi_buf |= value << s->bi_valid;
1N/A s->bi_valid += length;
1N/A }
1N/A}
1N/A#else /* !DEBUG_ZLIB */
1N/A
1N/A#define send_bits(s, value, length) \
1N/A{ int len = length;\
1N/A if (s->bi_valid > (int)Buf_size - len) {\
1N/A int val = value;\
1N/A s->bi_buf |= (val << s->bi_valid);\
1N/A put_short(s, s->bi_buf);\
1N/A s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
1N/A s->bi_valid += len - Buf_size;\
1N/A } else {\
1N/A s->bi_buf |= (value) << s->bi_valid;\
1N/A s->bi_valid += len;\
1N/A }\
1N/A}
1N/A#endif /* DEBUG_ZLIB */
1N/A
1N/A
1N/A#define MAX(a,b) (a >= b ? a : b)
1N/A/* the arguments must not have side effects */
1N/A
1N/A/* ===========================================================================
1N/A * Initialize the various 'constant' tables.
1N/A * To do: do this at compile time.
1N/A */
1N/Alocal void ct_static_init()
1N/A{
1N/A int n; /* iterates over tree elements */
1N/A int bits; /* bit counter */
1N/A int length; /* length value */
1N/A int code; /* code value */
1N/A int dist; /* distance index */
1N/A ush bl_count[MAX_BITS+1];
1N/A /* number of codes at each bit length for an optimal tree */
1N/A
1N/A /* Initialize the mapping length (0..255) -> length code (0..28) */
1N/A length = 0;
1N/A for (code = 0; code < LENGTH_CODES-1; code++) {
1N/A base_length[code] = length;
1N/A for (n = 0; n < (1<<extra_lbits[code]); n++) {
1N/A length_code[length++] = (uch)code;
1N/A }
1N/A }
1N/A Assert (length == 256, "ct_static_init: length != 256");
1N/A /* Note that the length 255 (match length 258) can be represented
1N/A * in two different ways: code 284 + 5 bits or code 285, so we
1N/A * overwrite length_code[255] to use the best encoding:
1N/A */
1N/A length_code[length-1] = (uch)code;
1N/A
1N/A /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
1N/A dist = 0;
1N/A for (code = 0 ; code < 16; code++) {
1N/A base_dist[code] = dist;
1N/A for (n = 0; n < (1<<extra_dbits[code]); n++) {
1N/A dist_code[dist++] = (uch)code;
1N/A }
1N/A }
1N/A Assert (dist == 256, "ct_static_init: dist != 256");
1N/A dist >>= 7; /* from now on, all distances are divided by 128 */
1N/A for ( ; code < D_CODES; code++) {
1N/A base_dist[code] = dist << 7;
1N/A for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
1N/A dist_code[256 + dist++] = (uch)code;
1N/A }
1N/A }
1N/A Assert (dist == 256, "ct_static_init: 256+dist != 512");
1N/A
1N/A /* Construct the codes of the static literal tree */
1N/A for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
1N/A n = 0;
1N/A while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
1N/A while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
1N/A while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
1N/A while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
1N/A /* Codes 286 and 287 do not exist, but we must include them in the
1N/A * tree construction to get a canonical Huffman tree (longest code
1N/A * all ones)
1N/A */
1N/A gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
1N/A
1N/A /* The static distance tree is trivial: */
1N/A for (n = 0; n < D_CODES; n++) {
1N/A static_dtree[n].Len = 5;
1N/A static_dtree[n].Code = bi_reverse(n, 5);
1N/A }
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Initialize the tree data structures for a new zlib stream.
1N/A */
1N/Alocal void ct_init(s)
1N/A deflate_state *s;
1N/A{
1N/A if (static_dtree[0].Len == 0) {
1N/A ct_static_init(); /* To do: at compile time */
1N/A }
1N/A
1N/A s->compressed_len = 0L;
1N/A
1N/A s->l_desc.dyn_tree = s->dyn_ltree;
1N/A s->l_desc.stat_desc = &static_l_desc;
1N/A
1N/A s->d_desc.dyn_tree = s->dyn_dtree;
1N/A s->d_desc.stat_desc = &static_d_desc;
1N/A
1N/A s->bl_desc.dyn_tree = s->bl_tree;
1N/A s->bl_desc.stat_desc = &static_bl_desc;
1N/A
1N/A s->bi_buf = 0;
1N/A s->bi_valid = 0;
1N/A s->last_eob_len = 8; /* enough lookahead for inflate */
1N/A#ifdef DEBUG_ZLIB
1N/A s->bits_sent = 0L;
1N/A#endif
1N/A s->blocks_in_packet = 0;
1N/A
1N/A /* Initialize the first block of the first file: */
1N/A init_block(s);
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Initialize a new block.
1N/A */
1N/Alocal void init_block(s)
1N/A deflate_state *s;
1N/A{
1N/A int n; /* iterates over tree elements */
1N/A
1N/A /* Initialize the trees. */
1N/A for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
1N/A for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
1N/A for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
1N/A
1N/A s->dyn_ltree[END_BLOCK].Freq = 1;
1N/A s->opt_len = s->static_len = 0L;
1N/A s->last_lit = s->matches = 0;
1N/A}
1N/A
1N/A#define SMALLEST 1
1N/A/* Index within the heap array of least frequent node in the Huffman tree */
1N/A
1N/A
1N/A/* ===========================================================================
1N/A * Remove the smallest element from the heap and recreate the heap with
1N/A * one less element. Updates heap and heap_len.
1N/A */
1N/A#define pqremove(s, tree, top) \
1N/A{\
1N/A top = s->heap[SMALLEST]; \
1N/A s->heap[SMALLEST] = s->heap[s->heap_len--]; \
1N/A pqdownheap(s, tree, SMALLEST); \
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Compares to subtrees, using the tree depth as tie breaker when
1N/A * the subtrees have equal frequency. This minimizes the worst case length.
1N/A */
1N/A#define smaller(tree, n, m, depth) \
1N/A (tree[n].Freq < tree[m].Freq || \
1N/A (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
1N/A
1N/A/* ===========================================================================
1N/A * Restore the heap property by moving down the tree starting at node k,
1N/A * exchanging a node with the smallest of its two sons if necessary, stopping
1N/A * when the heap property is re-established (each father smaller than its
1N/A * two sons).
1N/A */
1N/Alocal void pqdownheap(s, tree, k)
1N/A deflate_state *s;
1N/A ct_data *tree; /* the tree to restore */
1N/A int k; /* node to move down */
1N/A{
1N/A int v = s->heap[k];
1N/A int j = k << 1; /* left son of k */
1N/A while (j <= s->heap_len) {
1N/A /* Set j to the smallest of the two sons: */
1N/A if (j < s->heap_len &&
1N/A smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
1N/A j++;
1N/A }
1N/A /* Exit if v is smaller than both sons */
1N/A if (smaller(tree, v, s->heap[j], s->depth)) break;
1N/A
1N/A /* Exchange v with the smallest son */
1N/A s->heap[k] = s->heap[j]; k = j;
1N/A
1N/A /* And continue down the tree, setting j to the left son of k */
1N/A j <<= 1;
1N/A }
1N/A s->heap[k] = v;
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Compute the optimal bit lengths for a tree and update the total bit length
1N/A * for the current block.
1N/A * IN assertion: the fields freq and dad are set, heap[heap_max] and
1N/A * above are the tree nodes sorted by increasing frequency.
1N/A * OUT assertions: the field len is set to the optimal bit length, the
1N/A * array bl_count contains the frequencies for each bit length.
1N/A * The length opt_len is updated; static_len is also updated if stree is
1N/A * not null.
1N/A */
1N/Alocal void gen_bitlen(s, desc)
1N/A deflate_state *s;
1N/A tree_desc *desc; /* the tree descriptor */
1N/A{
1N/A ct_data *tree = desc->dyn_tree;
1N/A int max_code = desc->max_code;
1N/A ct_data *stree = desc->stat_desc->static_tree;
1N/A intf *extra = desc->stat_desc->extra_bits;
1N/A int base = desc->stat_desc->extra_base;
1N/A int max_length = desc->stat_desc->max_length;
1N/A int h; /* heap index */
1N/A int n, m; /* iterate over the tree elements */
1N/A int bits; /* bit length */
1N/A int xbits; /* extra bits */
1N/A ush f; /* frequency */
1N/A int overflow = 0; /* number of elements with bit length too large */
1N/A
1N/A for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
1N/A
1N/A /* In a first pass, compute the optimal bit lengths (which may
1N/A * overflow in the case of the bit length tree).
1N/A */
1N/A tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
1N/A
1N/A for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
1N/A n = s->heap[h];
1N/A bits = tree[tree[n].Dad].Len + 1;
1N/A if (bits > max_length) bits = max_length, overflow++;
1N/A tree[n].Len = (ush)bits;
1N/A /* We overwrite tree[n].Dad which is no longer needed */
1N/A
1N/A if (n > max_code) continue; /* not a leaf node */
1N/A
1N/A s->bl_count[bits]++;
1N/A xbits = 0;
1N/A if (n >= base) xbits = extra[n-base];
1N/A f = tree[n].Freq;
1N/A s->opt_len += (ulg)f * (bits + xbits);
1N/A if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
1N/A }
1N/A if (overflow == 0) return;
1N/A
1N/A Trace((stderr,"\nbit length overflow\n"));
1N/A /* This happens for example on obj2 and pic of the Calgary corpus */
1N/A
1N/A /* Find the first bit length which could increase: */
1N/A do {
1N/A bits = max_length-1;
1N/A while (s->bl_count[bits] == 0) bits--;
1N/A s->bl_count[bits]--; /* move one leaf down the tree */
1N/A s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
1N/A s->bl_count[max_length]--;
1N/A /* The brother of the overflow item also moves one step up,
1N/A * but this does not affect bl_count[max_length]
1N/A */
1N/A overflow -= 2;
1N/A } while (overflow > 0);
1N/A
1N/A /* Now recompute all bit lengths, scanning in increasing frequency.
1N/A * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
1N/A * lengths instead of fixing only the wrong ones. This idea is taken
1N/A * from 'ar' written by Haruhiko Okumura.)
1N/A */
1N/A for (bits = max_length; bits != 0; bits--) {
1N/A n = s->bl_count[bits];
1N/A while (n != 0) {
1N/A m = s->heap[--h];
1N/A if (m > max_code) continue;
1N/A if (tree[m].Len != (unsigned) bits) {
1N/A Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
1N/A s->opt_len += ((long)bits - (long)tree[m].Len)
1N/A *(long)tree[m].Freq;
1N/A tree[m].Len = (ush)bits;
1N/A }
1N/A n--;
1N/A }
1N/A }
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Generate the codes for a given tree and bit counts (which need not be
1N/A * optimal).
1N/A * IN assertion: the array bl_count contains the bit length statistics for
1N/A * the given tree and the field len is set for all tree elements.
1N/A * OUT assertion: the field code is set for all tree elements of non
1N/A * zero code length.
1N/A */
1N/Alocal void gen_codes (tree, max_code, bl_count)
1N/A ct_data *tree; /* the tree to decorate */
1N/A int max_code; /* largest code with non zero frequency */
1N/A ushf *bl_count; /* number of codes at each bit length */
1N/A{
1N/A ush next_code[MAX_BITS+1]; /* next code value for each bit length */
1N/A ush code = 0; /* running code value */
1N/A int bits; /* bit index */
1N/A int n; /* code index */
1N/A
1N/A /* The distribution counts are first used to generate the code values
1N/A * without bit reversal.
1N/A */
1N/A for (bits = 1; bits <= MAX_BITS; bits++) {
1N/A next_code[bits] = code = (code + bl_count[bits-1]) << 1;
1N/A }
1N/A /* Check that the bit counts in bl_count are consistent. The last code
1N/A * must be all ones.
1N/A */
1N/A Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
1N/A "inconsistent bit counts");
1N/A Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
1N/A
1N/A for (n = 0; n <= max_code; n++) {
1N/A int len = tree[n].Len;
1N/A if (len == 0) continue;
1N/A /* Now reverse the bits */
1N/A tree[n].Code = bi_reverse(next_code[len]++, len);
1N/A
1N/A Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
1N/A n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
1N/A }
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Construct one Huffman tree and assigns the code bit strings and lengths.
1N/A * Update the total bit length for the current block.
1N/A * IN assertion: the field freq is set for all tree elements.
1N/A * OUT assertions: the fields len and code are set to the optimal bit length
1N/A * and corresponding code. The length opt_len is updated; static_len is
1N/A * also updated if stree is not null. The field max_code is set.
1N/A */
1N/Alocal void build_tree(s, desc)
1N/A deflate_state *s;
1N/A tree_desc *desc; /* the tree descriptor */
1N/A{
1N/A ct_data *tree = desc->dyn_tree;
1N/A ct_data *stree = desc->stat_desc->static_tree;
1N/A int elems = desc->stat_desc->elems;
1N/A int n, m; /* iterate over heap elements */
1N/A int max_code = -1; /* largest code with non zero frequency */
1N/A int node; /* new node being created */
1N/A
1N/A /* Construct the initial heap, with least frequent element in
1N/A * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
1N/A * heap[0] is not used.
1N/A */
1N/A s->heap_len = 0, s->heap_max = HEAP_SIZE;
1N/A
1N/A for (n = 0; n < elems; n++) {
1N/A if (tree[n].Freq != 0) {
1N/A s->heap[++(s->heap_len)] = max_code = n;
1N/A s->depth[n] = 0;
1N/A } else {
1N/A tree[n].Len = 0;
1N/A }
1N/A }
1N/A
1N/A /* The pkzip format requires that at least one distance code exists,
1N/A * and that at least one bit should be sent even if there is only one
1N/A * possible code. So to avoid special checks later on we force at least
1N/A * two codes of non zero frequency.
1N/A */
1N/A while (s->heap_len < 2) {
1N/A node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
1N/A tree[node].Freq = 1;
1N/A s->depth[node] = 0;
1N/A s->opt_len--; if (stree) s->static_len -= stree[node].Len;
1N/A /* node is 0 or 1 so it does not have extra bits */
1N/A }
1N/A desc->max_code = max_code;
1N/A
1N/A /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
1N/A * establish sub-heaps of increasing lengths:
1N/A */
1N/A for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
1N/A
1N/A /* Construct the Huffman tree by repeatedly combining the least two
1N/A * frequent nodes.
1N/A */
1N/A node = elems; /* next internal node of the tree */
1N/A do {
1N/A pqremove(s, tree, n); /* n = node of least frequency */
1N/A m = s->heap[SMALLEST]; /* m = node of next least frequency */
1N/A
1N/A s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
1N/A s->heap[--(s->heap_max)] = m;
1N/A
1N/A /* Create a new node father of n and m */
1N/A tree[node].Freq = tree[n].Freq + tree[m].Freq;
1N/A s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1);
1N/A tree[n].Dad = tree[m].Dad = (ush)node;
1N/A#ifdef DUMP_BL_TREE
1N/A if (tree == s->bl_tree) {
1N/A fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
1N/A node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
1N/A }
1N/A#endif
1N/A /* and insert the new node in the heap */
1N/A s->heap[SMALLEST] = node++;
1N/A pqdownheap(s, tree, SMALLEST);
1N/A
1N/A } while (s->heap_len >= 2);
1N/A
1N/A s->heap[--(s->heap_max)] = s->heap[SMALLEST];
1N/A
1N/A /* At this point, the fields freq and dad are set. We can now
1N/A * generate the bit lengths.
1N/A */
1N/A gen_bitlen(s, (tree_desc *)desc);
1N/A
1N/A /* The field len is now set, we can generate the bit codes */
1N/A gen_codes ((ct_data *)tree, max_code, s->bl_count);
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Scan a literal or distance tree to determine the frequencies of the codes
1N/A * in the bit length tree.
1N/A */
1N/Alocal void scan_tree (s, tree, max_code)
1N/A deflate_state *s;
1N/A ct_data *tree; /* the tree to be scanned */
1N/A int max_code; /* and its largest code of non zero frequency */
1N/A{
1N/A int n; /* iterates over all tree elements */
1N/A int prevlen = -1; /* last emitted length */
1N/A int curlen; /* length of current code */
1N/A int nextlen = tree[0].Len; /* length of next code */
1N/A int count = 0; /* repeat count of the current code */
1N/A int max_count = 7; /* max repeat count */
1N/A int min_count = 4; /* min repeat count */
1N/A
1N/A if (nextlen == 0) max_count = 138, min_count = 3;
1N/A tree[max_code+1].Len = (ush)0xffff; /* guard */
1N/A
1N/A for (n = 0; n <= max_code; n++) {
1N/A curlen = nextlen; nextlen = tree[n+1].Len;
1N/A if (++count < max_count && curlen == nextlen) {
1N/A continue;
1N/A } else if (count < min_count) {
1N/A s->bl_tree[curlen].Freq += count;
1N/A } else if (curlen != 0) {
1N/A if (curlen != prevlen) s->bl_tree[curlen].Freq++;
1N/A s->bl_tree[REP_3_6].Freq++;
1N/A } else if (count <= 10) {
1N/A s->bl_tree[REPZ_3_10].Freq++;
1N/A } else {
1N/A s->bl_tree[REPZ_11_138].Freq++;
1N/A }
1N/A count = 0; prevlen = curlen;
1N/A if (nextlen == 0) {
1N/A max_count = 138, min_count = 3;
1N/A } else if (curlen == nextlen) {
1N/A max_count = 6, min_count = 3;
1N/A } else {
1N/A max_count = 7, min_count = 4;
1N/A }
1N/A }
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Send a literal or distance tree in compressed form, using the codes in
1N/A * bl_tree.
1N/A */
1N/Alocal void send_tree (s, tree, max_code)
1N/A deflate_state *s;
1N/A ct_data *tree; /* the tree to be scanned */
1N/A int max_code; /* and its largest code of non zero frequency */
1N/A{
1N/A int n; /* iterates over all tree elements */
1N/A int prevlen = -1; /* last emitted length */
1N/A int curlen; /* length of current code */
1N/A int nextlen = tree[0].Len; /* length of next code */
1N/A int count = 0; /* repeat count of the current code */
1N/A int max_count = 7; /* max repeat count */
1N/A int min_count = 4; /* min repeat count */
1N/A
1N/A /* tree[max_code+1].Len = -1; */ /* guard already set */
1N/A if (nextlen == 0) max_count = 138, min_count = 3;
1N/A
1N/A for (n = 0; n <= max_code; n++) {
1N/A curlen = nextlen; nextlen = tree[n+1].Len;
1N/A if (++count < max_count && curlen == nextlen) {
1N/A continue;
1N/A } else if (count < min_count) {
1N/A do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
1N/A
1N/A } else if (curlen != 0) {
1N/A if (curlen != prevlen) {
1N/A send_code(s, curlen, s->bl_tree); count--;
1N/A }
1N/A Assert(count >= 3 && count <= 6, " 3_6?");
1N/A send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
1N/A
1N/A } else if (count <= 10) {
1N/A send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
1N/A
1N/A } else {
1N/A send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
1N/A }
1N/A count = 0; prevlen = curlen;
1N/A if (nextlen == 0) {
1N/A max_count = 138, min_count = 3;
1N/A } else if (curlen == nextlen) {
1N/A max_count = 6, min_count = 3;
1N/A } else {
1N/A max_count = 7, min_count = 4;
1N/A }
1N/A }
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Construct the Huffman tree for the bit lengths and return the index in
1N/A * bl_order of the last bit length code to send.
1N/A */
1N/Alocal int build_bl_tree(s)
1N/A deflate_state *s;
1N/A{
1N/A int max_blindex; /* index of last bit length code of non zero freq */
1N/A
1N/A /* Determine the bit length frequencies for literal and distance trees */
1N/A scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
1N/A scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
1N/A
1N/A /* Build the bit length tree: */
1N/A build_tree(s, (tree_desc *)(&(s->bl_desc)));
1N/A /* opt_len now includes the length of the tree representations, except
1N/A * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
1N/A */
1N/A
1N/A /* Determine the number of bit length codes to send. The pkzip format
1N/A * requires that at least 4 bit length codes be sent. (appnote.txt says
1N/A * 3 but the actual value used is 4.)
1N/A */
1N/A for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
1N/A if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
1N/A }
1N/A /* Update opt_len to include the bit length tree and counts */
1N/A s->opt_len += 3*(max_blindex+1) + 5+5+4;
1N/A Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
1N/A s->opt_len, s->static_len));
1N/A
1N/A return max_blindex;
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Send the header for a block using dynamic Huffman trees: the counts, the
1N/A * lengths of the bit length codes, the literal tree and the distance tree.
1N/A * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
1N/A */
1N/Alocal void send_all_trees(s, lcodes, dcodes, blcodes)
1N/A deflate_state *s;
1N/A int lcodes, dcodes, blcodes; /* number of codes for each tree */
1N/A{
1N/A int rank; /* index in bl_order */
1N/A
1N/A Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
1N/A Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
1N/A "too many codes");
1N/A Tracev((stderr, "\nbl counts: "));
1N/A send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
1N/A send_bits(s, dcodes-1, 5);
1N/A send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */
1N/A for (rank = 0; rank < blcodes; rank++) {
1N/A Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
1N/A send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
1N/A }
1N/A Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
1N/A
1N/A send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
1N/A Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
1N/A
1N/A send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
1N/A Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Send a stored block
1N/A */
1N/Alocal void ct_stored_block(s, buf, stored_len, eof)
1N/A deflate_state *s;
1N/A charf *buf; /* input block */
1N/A ulg stored_len; /* length of input block */
1N/A int eof; /* true if this is the last block for a file */
1N/A{
1N/A send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */
1N/A s->compressed_len = (s->compressed_len + 3 + 7) & ~7L;
1N/A s->compressed_len += (stored_len + 4) << 3;
1N/A
1N/A copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
1N/A}
1N/A
1N/A/* Send just the `stored block' type code without any length bytes or data.
1N/A */
1N/Alocal void ct_stored_type_only(s)
1N/A deflate_state *s;
1N/A{
1N/A send_bits(s, (STORED_BLOCK << 1), 3);
1N/A bi_windup(s);
1N/A s->compressed_len = (s->compressed_len + 3) & ~7L;
1N/A}
1N/A
1N/A
1N/A/* ===========================================================================
1N/A * Send one empty static block to give enough lookahead for inflate.
1N/A * This takes 10 bits, of which 7 may remain in the bit buffer.
1N/A * The current inflate code requires 9 bits of lookahead. If the EOB
1N/A * code for the previous block was coded on 5 bits or less, inflate
1N/A * may have only 5+3 bits of lookahead to decode this EOB.
1N/A * (There are no problems if the previous block is stored or fixed.)
1N/A */
1N/Alocal void ct_align(s)
1N/A deflate_state *s;
1N/A{
1N/A send_bits(s, STATIC_TREES<<1, 3);
1N/A send_code(s, END_BLOCK, static_ltree);
1N/A s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
1N/A bi_flush(s);
1N/A /* Of the 10 bits for the empty block, we have already sent
1N/A * (10 - bi_valid) bits. The lookahead for the EOB of the previous
1N/A * block was thus its length plus what we have just sent.
1N/A */
1N/A if (s->last_eob_len + 10 - s->bi_valid < 9) {
1N/A send_bits(s, STATIC_TREES<<1, 3);
1N/A send_code(s, END_BLOCK, static_ltree);
1N/A s->compressed_len += 10L;
1N/A bi_flush(s);
1N/A }
1N/A s->last_eob_len = 7;
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Determine the best encoding for the current block: dynamic trees, static
1N/A * trees or store, and output the encoded block to the zip file. This function
1N/A * returns the total compressed length for the file so far.
1N/A */
1N/Alocal ulg ct_flush_block(s, buf, stored_len, flush)
1N/A deflate_state *s;
1N/A charf *buf; /* input block, or NULL if too old */
1N/A ulg stored_len; /* length of input block */
1N/A int flush; /* Z_FINISH if this is the last block for a file */
1N/A{
1N/A ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
1N/A int max_blindex; /* index of last bit length code of non zero freq */
1N/A int eof = flush == Z_FINISH;
1N/A
1N/A ++s->blocks_in_packet;
1N/A
1N/A /* Check if the file is ascii or binary */
1N/A if (s->data_type == UNKNOWN) set_data_type(s);
1N/A
1N/A /* Construct the literal and distance trees */
1N/A build_tree(s, (tree_desc *)(&(s->l_desc)));
1N/A Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
1N/A s->static_len));
1N/A
1N/A build_tree(s, (tree_desc *)(&(s->d_desc)));
1N/A Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
1N/A s->static_len));
1N/A /* At this point, opt_len and static_len are the total bit lengths of
1N/A * the compressed block data, excluding the tree representations.
1N/A */
1N/A
1N/A /* Build the bit length tree for the above two trees, and get the index
1N/A * in bl_order of the last bit length code to send.
1N/A */
1N/A max_blindex = build_bl_tree(s);
1N/A
1N/A /* Determine the best encoding. Compute first the block length in bytes */
1N/A opt_lenb = (s->opt_len+3+7)>>3;
1N/A static_lenb = (s->static_len+3+7)>>3;
1N/A
1N/A Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
1N/A opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
1N/A s->last_lit));
1N/A
1N/A if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
1N/A
1N/A /* If compression failed and this is the first and last block,
1N/A * and if the .zip file can be seeked (to rewrite the local header),
1N/A * the whole file is transformed into a stored file:
1N/A */
1N/A#ifdef STORED_FILE_OK
1N/A# ifdef FORCE_STORED_FILE
1N/A if (eof && compressed_len == 0L) /* force stored file */
1N/A# else
1N/A if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable())
1N/A# endif
1N/A {
1N/A /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */
1N/A if (buf == (charf*)0) error ("block vanished");
1N/A
1N/A copy_block(buf, (unsigned)stored_len, 0); /* without header */
1N/A s->compressed_len = stored_len << 3;
1N/A s->method = STORED;
1N/A } else
1N/A#endif /* STORED_FILE_OK */
1N/A
1N/A /* For Z_PACKET_FLUSH, if we don't achieve the required minimum
1N/A * compression, and this block contains all the data since the last
1N/A * time we used Z_PACKET_FLUSH, then just omit this block completely
1N/A * from the output.
1N/A */
1N/A if (flush == Z_PACKET_FLUSH && s->blocks_in_packet == 1
1N/A && opt_lenb > stored_len - s->minCompr) {
1N/A s->blocks_in_packet = 0;
1N/A /* output nothing */
1N/A } else
1N/A
1N/A#ifdef FORCE_STORED
1N/A if (buf != (char*)0) /* force stored block */
1N/A#else
1N/A if (stored_len+4 <= opt_lenb && buf != (char*)0)
1N/A /* 4: two words for the lengths */
1N/A#endif
1N/A {
1N/A /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
1N/A * Otherwise we can't have processed more than WSIZE input bytes since
1N/A * the last block flush, because compression would have been
1N/A * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
1N/A * transform a block into a stored block.
1N/A */
1N/A ct_stored_block(s, buf, stored_len, eof);
1N/A } else
1N/A
1N/A#ifdef FORCE_STATIC
1N/A if (static_lenb >= 0) /* force static trees */
1N/A#else
1N/A if (static_lenb == opt_lenb)
1N/A#endif
1N/A {
1N/A send_bits(s, (STATIC_TREES<<1)+eof, 3);
1N/A compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
1N/A s->compressed_len += 3 + s->static_len;
1N/A } else {
1N/A send_bits(s, (DYN_TREES<<1)+eof, 3);
1N/A send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
1N/A max_blindex+1);
1N/A compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
1N/A s->compressed_len += 3 + s->opt_len;
1N/A }
1N/A Assert (s->compressed_len == s->bits_sent, "bad compressed size");
1N/A init_block(s);
1N/A
1N/A if (eof) {
1N/A bi_windup(s);
1N/A s->compressed_len += 7; /* align on byte boundary */
1N/A }
1N/A Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
1N/A s->compressed_len-7*eof));
1N/A
1N/A return s->compressed_len >> 3;
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Save the match info and tally the frequency counts. Return true if
1N/A * the current block must be flushed.
1N/A */
1N/Alocal int ct_tally (s, dist, lc)
1N/A deflate_state *s;
1N/A int dist; /* distance of matched string */
1N/A int lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
1N/A{
1N/A s->d_buf[s->last_lit] = (ush)dist;
1N/A s->l_buf[s->last_lit++] = (uch)lc;
1N/A if (dist == 0) {
1N/A /* lc is the unmatched char */
1N/A s->dyn_ltree[lc].Freq++;
1N/A } else {
1N/A s->matches++;
1N/A /* Here, lc is the match length - MIN_MATCH */
1N/A dist--; /* dist = match distance - 1 */
1N/A Assert((ush)dist < (ush)MAX_DIST(s) &&
1N/A (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
1N/A (ush)d_code(dist) < (ush)D_CODES, "ct_tally: bad match");
1N/A
1N/A s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
1N/A s->dyn_dtree[d_code(dist)].Freq++;
1N/A }
1N/A
1N/A /* Try to guess if it is profitable to stop the current block here */
1N/A if (s->level > 2 && (s->last_lit & 0xfff) == 0) {
1N/A /* Compute an upper bound for the compressed length */
1N/A ulg out_length = (ulg)s->last_lit*8L;
1N/A ulg in_length = (ulg)s->strstart - s->block_start;
1N/A int dcode;
1N/A for (dcode = 0; dcode < D_CODES; dcode++) {
1N/A out_length += (ulg)s->dyn_dtree[dcode].Freq *
1N/A (5L+extra_dbits[dcode]);
1N/A }
1N/A out_length >>= 3;
1N/A Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1N/A s->last_lit, in_length, out_length,
1N/A 100L - out_length*100L/in_length));
1N/A if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
1N/A }
1N/A return (s->last_lit == s->lit_bufsize-1);
1N/A /* We avoid equality with lit_bufsize because of wraparound at 64K
1N/A * on 16 bit machines and because stored blocks are restricted to
1N/A * 64K-1 bytes.
1N/A */
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Send the block data compressed using the given Huffman trees
1N/A */
1N/Alocal void compress_block(s, ltree, dtree)
1N/A deflate_state *s;
1N/A ct_data *ltree; /* literal tree */
1N/A ct_data *dtree; /* distance tree */
1N/A{
1N/A unsigned dist; /* distance of matched string */
1N/A int lc; /* match length or unmatched char (if dist == 0) */
1N/A unsigned lx = 0; /* running index in l_buf */
1N/A unsigned code; /* the code to send */
1N/A int extra; /* number of extra bits to send */
1N/A
1N/A if (s->last_lit != 0) do {
1N/A dist = s->d_buf[lx];
1N/A lc = s->l_buf[lx++];
1N/A if (dist == 0) {
1N/A send_code(s, lc, ltree); /* send a literal byte */
1N/A Tracecv(isgraph(lc), (stderr," '%c' ", lc));
1N/A } else {
1N/A /* Here, lc is the match length - MIN_MATCH */
1N/A code = length_code[lc];
1N/A send_code(s, code+LITERALS+1, ltree); /* send the length code */
1N/A extra = extra_lbits[code];
1N/A if (extra != 0) {
1N/A lc -= base_length[code];
1N/A send_bits(s, lc, extra); /* send the extra length bits */
1N/A }
1N/A dist--; /* dist is now the match distance - 1 */
1N/A code = d_code(dist);
1N/A Assert (code < D_CODES, "bad d_code");
1N/A
1N/A send_code(s, code, dtree); /* send the distance code */
1N/A extra = extra_dbits[code];
1N/A if (extra != 0) {
1N/A dist -= base_dist[code];
1N/A send_bits(s, dist, extra); /* send the extra distance bits */
1N/A }
1N/A } /* literal or match pair ? */
1N/A
1N/A /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
1N/A Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow");
1N/A
1N/A } while (lx < s->last_lit);
1N/A
1N/A send_code(s, END_BLOCK, ltree);
1N/A s->last_eob_len = ltree[END_BLOCK].Len;
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Set the data type to ASCII or BINARY, using a crude approximation:
1N/A * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
1N/A * IN assertion: the fields freq of dyn_ltree are set and the total of all
1N/A * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
1N/A */
1N/Alocal void set_data_type(s)
1N/A deflate_state *s;
1N/A{
1N/A int n = 0;
1N/A unsigned ascii_freq = 0;
1N/A unsigned bin_freq = 0;
1N/A while (n < 7) bin_freq += s->dyn_ltree[n++].Freq;
1N/A while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq;
1N/A while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
1N/A s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? BINARY : ASCII);
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Reverse the first len bits of a code, using straightforward code (a faster
1N/A * method would use a table)
1N/A * IN assertion: 1 <= len <= 15
1N/A */
1N/Alocal unsigned bi_reverse(code, len)
1N/A unsigned code; /* the value to invert */
1N/A int len; /* its bit length */
1N/A{
1N/A register unsigned res = 0;
1N/A do {
1N/A res |= code & 1;
1N/A code >>= 1, res <<= 1;
1N/A } while (--len > 0);
1N/A return res >> 1;
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Flush the bit buffer, keeping at most 7 bits in it.
1N/A */
1N/Alocal void bi_flush(s)
1N/A deflate_state *s;
1N/A{
1N/A if (s->bi_valid == 16) {
1N/A put_short(s, s->bi_buf);
1N/A s->bi_buf = 0;
1N/A s->bi_valid = 0;
1N/A } else if (s->bi_valid >= 8) {
1N/A put_byte(s, (Byte)s->bi_buf);
1N/A s->bi_buf >>= 8;
1N/A s->bi_valid -= 8;
1N/A }
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Flush the bit buffer and align the output on a byte boundary
1N/A */
1N/Alocal void bi_windup(s)
1N/A deflate_state *s;
1N/A{
1N/A if (s->bi_valid > 8) {
1N/A put_short(s, s->bi_buf);
1N/A } else if (s->bi_valid > 0) {
1N/A put_byte(s, (Byte)s->bi_buf);
1N/A }
1N/A s->bi_buf = 0;
1N/A s->bi_valid = 0;
1N/A#ifdef DEBUG_ZLIB
1N/A s->bits_sent = (s->bits_sent+7) & ~7;
1N/A#endif
1N/A}
1N/A
1N/A/* ===========================================================================
1N/A * Copy a stored block, storing first the length and its
1N/A * one's complement if requested.
1N/A */
1N/Alocal void copy_block(s, buf, len, header)
1N/A deflate_state *s;
1N/A charf *buf; /* the input data */
1N/A unsigned len; /* its length */
1N/A int header; /* true if block header must be written */
1N/A{
1N/A bi_windup(s); /* align on byte boundary */
1N/A s->last_eob_len = 8; /* enough lookahead for inflate */
1N/A
1N/A if (header) {
1N/A put_short(s, (ush)len);
1N/A put_short(s, (ush)~len);
1N/A#ifdef DEBUG_ZLIB
1N/A s->bits_sent += 2*16;
1N/A#endif
1N/A }
1N/A#ifdef DEBUG_ZLIB
1N/A s->bits_sent += (ulg)len<<3;
1N/A#endif
1N/A while (len--) {
1N/A put_byte(s, *buf++);
1N/A }
1N/A}
1N/A
1N/A
1N/A/*+++++*/
1N/A/* infblock.h -- header to use infblock.c
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* WARNING: this file should *not* be used by applications. It is
1N/A part of the implementation of the compression library and is
1N/A subject to change. Applications should only use zlib.h.
1N/A */
1N/A
1N/Astruct inflate_blocks_state;
1N/Atypedef struct inflate_blocks_state FAR inflate_blocks_statef;
1N/A
1N/Alocal inflate_blocks_statef * inflate_blocks_new OF((
1N/A z_stream *z,
1N/A check_func c, /* check function */
1N/A uInt w)); /* window size */
1N/A
1N/Alocal int inflate_blocks OF((
1N/A inflate_blocks_statef *,
1N/A z_stream *,
1N/A int)); /* initial return code */
1N/A
1N/Alocal void inflate_blocks_reset OF((
1N/A inflate_blocks_statef *,
1N/A z_stream *,
1N/A uLongf *)); /* check value on output */
1N/A
1N/Alocal int inflate_blocks_free OF((
1N/A inflate_blocks_statef *,
1N/A z_stream *,
1N/A uLongf *)); /* check value on output */
1N/A
1N/Alocal int inflate_addhistory OF((
1N/A inflate_blocks_statef *,
1N/A z_stream *));
1N/A
1N/Alocal int inflate_packet_flush OF((
1N/A inflate_blocks_statef *));
1N/A
1N/A/*+++++*/
1N/A/* inftrees.h -- header to use inftrees.c
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* WARNING: this file should *not* be used by applications. It is
1N/A part of the implementation of the compression library and is
1N/A subject to change. Applications should only use zlib.h.
1N/A */
1N/A
1N/A/* Huffman code lookup table entry--this entry is four bytes for machines
1N/A that have 16-bit pointers (e.g. PC's in the small or medium model). */
1N/A
1N/Atypedef struct inflate_huft_s FAR inflate_huft;
1N/A
1N/Astruct inflate_huft_s {
1N/A union {
1N/A struct {
1N/A Byte Exop; /* number of extra bits or operation */
1N/A Byte Bits; /* number of bits in this code or subcode */
1N/A } what;
1N/A uInt Nalloc; /* number of these allocated here */
1N/A Bytef *pad; /* pad structure to a power of 2 (4 bytes for */
1N/A } word; /* 16-bit, 8 bytes for 32-bit machines) */
1N/A union {
1N/A uInt Base; /* literal, length base, or distance base */
1N/A inflate_huft *Next; /* pointer to next level of table */
1N/A } more;
1N/A};
1N/A
1N/A#ifdef DEBUG_ZLIB
1N/A local uInt inflate_hufts;
1N/A#endif
1N/A
1N/Alocal int inflate_trees_bits OF((
1N/A uIntf *, /* 19 code lengths */
1N/A uIntf *, /* bits tree desired/actual depth */
1N/A inflate_huft * FAR *, /* bits tree result */
1N/A z_stream *)); /* for zalloc, zfree functions */
1N/A
1N/Alocal int inflate_trees_dynamic OF((
1N/A uInt, /* number of literal/length codes */
1N/A uInt, /* number of distance codes */
1N/A uIntf *, /* that many (total) code lengths */
1N/A uIntf *, /* literal desired/actual bit depth */
1N/A uIntf *, /* distance desired/actual bit depth */
1N/A inflate_huft * FAR *, /* literal/length tree result */
1N/A inflate_huft * FAR *, /* distance tree result */
1N/A z_stream *)); /* for zalloc, zfree functions */
1N/A
1N/Alocal int inflate_trees_fixed OF((
1N/A uIntf *, /* literal desired/actual bit depth */
1N/A uIntf *, /* distance desired/actual bit depth */
1N/A inflate_huft * FAR *, /* literal/length tree result */
1N/A inflate_huft * FAR *)); /* distance tree result */
1N/A
1N/Alocal int inflate_trees_free OF((
1N/A inflate_huft *, /* tables to free */
1N/A z_stream *)); /* for zfree function */
1N/A
1N/A
1N/A/*+++++*/
1N/A/* infcodes.h -- header to use infcodes.c
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* WARNING: this file should *not* be used by applications. It is
1N/A part of the implementation of the compression library and is
1N/A subject to change. Applications should only use zlib.h.
1N/A */
1N/A
1N/Astruct inflate_codes_state;
1N/Atypedef struct inflate_codes_state FAR inflate_codes_statef;
1N/A
1N/Alocal inflate_codes_statef *inflate_codes_new OF((
1N/A uInt, uInt,
1N/A inflate_huft *, inflate_huft *,
1N/A z_stream *));
1N/A
1N/Alocal int inflate_codes OF((
1N/A inflate_blocks_statef *,
1N/A z_stream *,
1N/A int));
1N/A
1N/Alocal void inflate_codes_free OF((
1N/A inflate_codes_statef *,
1N/A z_stream *));
1N/A
1N/A
1N/A/*+++++*/
1N/A/* inflate.c -- zlib interface to inflate modules
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* inflate private state */
1N/Astruct internal_state {
1N/A
1N/A /* mode */
1N/A enum {
1N/A METHOD, /* waiting for method byte */
1N/A FLAG, /* waiting for flag byte */
1N/A BLOCKS, /* decompressing blocks */
1N/A CHECK4, /* four check bytes to go */
1N/A CHECK3, /* three check bytes to go */
1N/A CHECK2, /* two check bytes to go */
1N/A CHECK1, /* one check byte to go */
1N/A DONE, /* finished check, done */
1N/A BAD} /* got an error--stay here */
1N/A mode; /* current inflate mode */
1N/A
1N/A /* mode dependent information */
1N/A union {
1N/A uInt method; /* if FLAGS, method byte */
1N/A struct {
1N/A uLong was; /* computed check value */
1N/A uLong need; /* stream check value */
1N/A } check; /* if CHECK, check values to compare */
1N/A uInt marker; /* if BAD, inflateSync's marker bytes count */
1N/A } sub; /* submode */
1N/A
1N/A /* mode independent information */
1N/A int nowrap; /* flag for no wrapper */
1N/A uInt wbits; /* log2(window size) (8..15, defaults to 15) */
1N/A inflate_blocks_statef
1N/A *blocks; /* current inflate_blocks state */
1N/A
1N/A};
1N/A
1N/A
1N/Aint inflateReset(z)
1N/Az_stream *z;
1N/A{
1N/A uLong c;
1N/A
1N/A if (z == Z_NULL || z->state == Z_NULL)
1N/A return Z_STREAM_ERROR;
1N/A z->total_in = z->total_out = 0;
1N/A z->msg = Z_NULL;
1N/A z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
1N/A inflate_blocks_reset(z->state->blocks, z, &c);
1N/A Trace((stderr, "inflate: reset\n"));
1N/A return Z_OK;
1N/A}
1N/A
1N/A
1N/Aint inflateEnd(z)
1N/Az_stream *z;
1N/A{
1N/A uLong c;
1N/A
1N/A if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
1N/A return Z_STREAM_ERROR;
1N/A if (z->state->blocks != Z_NULL)
1N/A inflate_blocks_free(z->state->blocks, z, &c);
1N/A ZFREE(z, z->state, sizeof(struct internal_state));
1N/A z->state = Z_NULL;
1N/A Trace((stderr, "inflate: end\n"));
1N/A return Z_OK;
1N/A}
1N/A
1N/A
1N/Aint inflateInit2(z, w)
1N/Az_stream *z;
1N/Aint w;
1N/A{
1N/A /* initialize state */
1N/A if (z == Z_NULL)
1N/A return Z_STREAM_ERROR;
1N/A/* if (z->zalloc == Z_NULL) z->zalloc = zcalloc; */
1N/A/* if (z->zfree == Z_NULL) z->zfree = zcfree; */
1N/A if ((z->state = (struct internal_state FAR *)
1N/A ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL)
1N/A return Z_MEM_ERROR;
1N/A z->state->blocks = Z_NULL;
1N/A
1N/A /* handle undocumented nowrap option (no zlib header or check) */
1N/A z->state->nowrap = 0;
1N/A if (w < 0)
1N/A {
1N/A w = - w;
1N/A z->state->nowrap = 1;
1N/A }
1N/A
1N/A /* set window size */
1N/A if (w < 8 || w > 15)
1N/A {
1N/A inflateEnd(z);
1N/A return Z_STREAM_ERROR;
1N/A }
1N/A z->state->wbits = (uInt)w;
1N/A
1N/A /* create inflate_blocks state */
1N/A if ((z->state->blocks =
1N/A inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, 1 << w))
1N/A == Z_NULL)
1N/A {
1N/A inflateEnd(z);
1N/A return Z_MEM_ERROR;
1N/A }
1N/A Trace((stderr, "inflate: allocated\n"));
1N/A
1N/A /* reset state */
1N/A inflateReset(z);
1N/A return Z_OK;
1N/A}
1N/A
1N/A
1N/Aint inflateInit(z)
1N/Az_stream *z;
1N/A{
1N/A return inflateInit2(z, DEF_WBITS);
1N/A}
1N/A
1N/A
1N/A#define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;}
1N/A#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)
1N/A
1N/Aint inflate(z, f)
1N/Az_stream *z;
1N/Aint f;
1N/A{
1N/A int r;
1N/A uInt b;
1N/A
1N/A if (z == Z_NULL || z->next_in == Z_NULL)
1N/A return Z_STREAM_ERROR;
1N/A r = Z_BUF_ERROR;
1N/A while (1) switch (z->state->mode)
1N/A {
1N/A case METHOD:
1N/A NEEDBYTE
1N/A if (((z->state->sub.method = NEXTBYTE) & 0xf) != DEFLATED)
1N/A {
1N/A z->state->mode = BAD;
1N/A z->msg = "unknown compression method";
1N/A z->state->sub.marker = 5; /* can't try inflateSync */
1N/A break;
1N/A }
1N/A if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
1N/A {
1N/A z->state->mode = BAD;
1N/A z->msg = "invalid window size";
1N/A z->state->sub.marker = 5; /* can't try inflateSync */
1N/A break;
1N/A }
1N/A z->state->mode = FLAG;
1N/A case FLAG:
1N/A NEEDBYTE
1N/A if ((b = NEXTBYTE) & 0x20)
1N/A {
1N/A z->state->mode = BAD;
1N/A z->msg = "invalid reserved bit";
1N/A z->state->sub.marker = 5; /* can't try inflateSync */
1N/A break;
1N/A }
1N/A if (((z->state->sub.method << 8) + b) % 31)
1N/A {
1N/A z->state->mode = BAD;
1N/A z->msg = "incorrect header check";
1N/A z->state->sub.marker = 5; /* can't try inflateSync */
1N/A break;
1N/A }
1N/A Trace((stderr, "inflate: zlib header ok\n"));
1N/A z->state->mode = BLOCKS;
1N/A case BLOCKS:
1N/A r = inflate_blocks(z->state->blocks, z, r);
1N/A if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
1N/A r = inflate_packet_flush(z->state->blocks);
1N/A if (r == Z_DATA_ERROR)
1N/A {
1N/A z->state->mode = BAD;
1N/A z->state->sub.marker = 0; /* can try inflateSync */
1N/A break;
1N/A }
1N/A if (r != Z_STREAM_END)
1N/A return r;
1N/A r = Z_OK;
1N/A inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
1N/A if (z->state->nowrap)
1N/A {
1N/A z->state->mode = DONE;
1N/A break;
1N/A }
1N/A z->state->mode = CHECK4;
1N/A case CHECK4:
1N/A NEEDBYTE
1N/A z->state->sub.check.need = (uLong)NEXTBYTE << 24;
1N/A z->state->mode = CHECK3;
1N/A case CHECK3:
1N/A NEEDBYTE
1N/A z->state->sub.check.need += (uLong)NEXTBYTE << 16;
1N/A z->state->mode = CHECK2;
1N/A case CHECK2:
1N/A NEEDBYTE
1N/A z->state->sub.check.need += (uLong)NEXTBYTE << 8;
1N/A z->state->mode = CHECK1;
1N/A case CHECK1:
1N/A NEEDBYTE
1N/A z->state->sub.check.need += (uLong)NEXTBYTE;
1N/A
1N/A if (z->state->sub.check.was != z->state->sub.check.need)
1N/A {
1N/A z->state->mode = BAD;
1N/A z->msg = "incorrect data check";
1N/A z->state->sub.marker = 5; /* can't try inflateSync */
1N/A break;
1N/A }
1N/A Trace((stderr, "inflate: zlib check ok\n"));
1N/A z->state->mode = DONE;
1N/A case DONE:
1N/A return Z_STREAM_END;
1N/A case BAD:
1N/A return Z_DATA_ERROR;
1N/A default:
1N/A return Z_STREAM_ERROR;
1N/A }
1N/A
1N/A empty:
1N/A if (f != Z_PACKET_FLUSH)
1N/A return r;
1N/A z->state->mode = BAD;
1N/A z->state->sub.marker = 0; /* can try inflateSync */
1N/A return Z_DATA_ERROR;
1N/A}
1N/A
1N/A/*
1N/A * This subroutine adds the data at next_in/avail_in to the output history
1N/A * without performing any output. The output buffer must be "caught up";
1N/A * i.e. no pending output (hence s->read equals s->write), and the state must
1N/A * be BLOCKS (i.e. we should be willing to see the start of a series of
1N/A * BLOCKS). On exit, the output will also be caught up, and the checksum
1N/A * will have been updated if need be.
1N/A */
1N/A
1N/Aint inflateIncomp(z)
1N/Az_stream *z;
1N/A{
1N/A if (z->state->mode != BLOCKS)
1N/A return Z_DATA_ERROR;
1N/A return inflate_addhistory(z->state->blocks, z);
1N/A}
1N/A
1N/A
1N/Aint inflateSync(z)
1N/Az_stream *z;
1N/A{
1N/A uInt n; /* number of bytes to look at */
1N/A Bytef *p; /* pointer to bytes */
1N/A uInt m; /* number of marker bytes found in a row */
1N/A uLong r, w; /* temporaries to save total_in and total_out */
1N/A
1N/A /* set up */
1N/A if (z == Z_NULL || z->state == Z_NULL)
1N/A return Z_STREAM_ERROR;
1N/A if (z->state->mode != BAD)
1N/A {
1N/A z->state->mode = BAD;
1N/A z->state->sub.marker = 0;
1N/A }
1N/A if ((n = z->avail_in) == 0)
1N/A return Z_BUF_ERROR;
1N/A p = z->next_in;
1N/A m = z->state->sub.marker;
1N/A
1N/A /* search */
1N/A while (n && m < 4)
1N/A {
1N/A if (*p == (Byte)(m < 2 ? 0 : 0xff))
1N/A m++;
1N/A else if (*p)
1N/A m = 0;
1N/A else
1N/A m = 4 - m;
1N/A p++, n--;
1N/A }
1N/A
1N/A /* restore */
1N/A z->total_in += p - z->next_in;
1N/A z->next_in = p;
1N/A z->avail_in = n;
1N/A z->state->sub.marker = m;
1N/A
1N/A /* return no joy or set up to restart on a new block */
1N/A if (m != 4)
1N/A return Z_DATA_ERROR;
1N/A r = z->total_in; w = z->total_out;
1N/A inflateReset(z);
1N/A z->total_in = r; z->total_out = w;
1N/A z->state->mode = BLOCKS;
1N/A return Z_OK;
1N/A}
1N/A
1N/A#undef NEEDBYTE
1N/A#undef NEXTBYTE
1N/A
1N/A/*+++++*/
1N/A/* infutil.h -- types and macros common to blocks and codes
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* WARNING: this file should *not* be used by applications. It is
1N/A part of the implementation of the compression library and is
1N/A subject to change. Applications should only use zlib.h.
1N/A */
1N/A
1N/A/* inflate blocks semi-private state */
1N/Astruct inflate_blocks_state {
1N/A
1N/A /* mode */
1N/A enum {
1N/A TYPE, /* get type bits (3, including end bit) */
1N/A LENS, /* get lengths for stored */
1N/A STORED, /* processing stored block */
1N/A TABLE, /* get table lengths */
1N/A BTREE, /* get bit lengths tree for a dynamic block */
1N/A DTREE, /* get length, distance trees for a dynamic block */
1N/A CODES, /* processing fixed or dynamic block */
1N/A DRY, /* output remaining window bytes */
1N/A DONEB, /* finished last block, done */
1N/A BADB} /* got a data error--stuck here */
1N/A mode; /* current inflate_block mode */
1N/A
1N/A /* mode dependent information */
1N/A union {
1N/A uInt left; /* if STORED, bytes left to copy */
1N/A struct {
1N/A uInt table; /* table lengths (14 bits) */
1N/A uInt index; /* index into blens (or border) */
1N/A uIntf *blens; /* bit lengths of codes */
1N/A uInt bb; /* bit length tree depth */
1N/A inflate_huft *tb; /* bit length decoding tree */
1N/A int nblens; /* # elements allocated at blens */
1N/A } trees; /* if DTREE, decoding info for trees */
1N/A struct {
1N/A inflate_huft *tl, *td; /* trees to free */
1N/A inflate_codes_statef
1N/A *codes;
1N/A } decode; /* if CODES, current state */
1N/A } sub; /* submode */
1N/A uInt last; /* true if this block is the last block */
1N/A
1N/A /* mode independent information */
1N/A uInt bitk; /* bits in bit buffer */
1N/A uLong bitb; /* bit buffer */
1N/A Bytef *window; /* sliding window */
1N/A Bytef *end; /* one byte after sliding window */
1N/A Bytef *read; /* window read pointer */
1N/A Bytef *write; /* window write pointer */
1N/A check_func checkfn; /* check function */
1N/A uLong check; /* check on output */
1N/A
1N/A};
1N/A
1N/A
1N/A/* defines for inflate input/output */
1N/A/* update pointers and return */
1N/A#define UPDBITS {s->bitb=b;s->bitk=k;}
1N/A#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
1N/A#define UPDOUT {s->write=q;}
1N/A#define UPDATE {UPDBITS UPDIN UPDOUT}
1N/A#define LEAVE {UPDATE return inflate_flush(s,z,r);}
1N/A/* get bytes and bits */
1N/A#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
1N/A#define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
1N/A#define NEXTBYTE (n--,*p++)
1N/A#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
1N/A#define DUMPBITS(j) {b>>=(j);k-=(j);}
1N/A/* output bytes */
1N/A#define WAVAIL (q<s->read?s->read-q-1:s->end-q)
1N/A#define LOADOUT {q=s->write;m=WAVAIL;}
1N/A#define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=WAVAIL;}}
1N/A#define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
1N/A#define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
1N/A#define OUTBYTE(a) {*q++=(Byte)(a);m--;}
1N/A/* load local pointers */
1N/A#define LOAD {LOADIN LOADOUT}
1N/A
1N/A/* And'ing with mask[n] masks the lower n bits */
1N/Alocal uInt inflate_mask[] = {
1N/A 0x0000,
1N/A 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
1N/A 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
1N/A};
1N/A
1N/A/* copy as much as possible from the sliding window to the output area */
1N/Alocal int inflate_flush OF((
1N/A inflate_blocks_statef *,
1N/A z_stream *,
1N/A int));
1N/A
1N/A/*+++++*/
1N/A/* inffast.h -- header to use inffast.c
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* WARNING: this file should *not* be used by applications. It is
1N/A part of the implementation of the compression library and is
1N/A subject to change. Applications should only use zlib.h.
1N/A */
1N/A
1N/Alocal int inflate_fast OF((
1N/A uInt,
1N/A uInt,
1N/A inflate_huft *,
1N/A inflate_huft *,
1N/A inflate_blocks_statef *,
1N/A z_stream *));
1N/A
1N/A
1N/A/*+++++*/
1N/A/* infblock.c -- interpret and process block types to last block
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* Table for deflate from PKZIP's appnote.txt. */
1N/Alocal uInt border[] = { /* Order of the bit length code lengths */
1N/A 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
1N/A
1N/A/*
1N/A Notes beyond the 1.93a appnote.txt:
1N/A
1N/A 1. Distance pointers never point before the beginning of the output
1N/A stream.
1N/A 2. Distance pointers can point back across blocks, up to 32k away.
1N/A 3. There is an implied maximum of 7 bits for the bit length table and
1N/A 15 bits for the actual data.
1N/A 4. If only one code exists, then it is encoded using one bit. (Zero
1N/A would be more efficient, but perhaps a little confusing.) If two
1N/A codes exist, they are coded using one bit each (0 and 1).
1N/A 5. There is no way of sending zero distance codes--a dummy must be
1N/A sent if there are none. (History: a pre 2.0 version of PKZIP would
1N/A store blocks with no distance codes, but this was discovered to be
1N/A too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
1N/A zero distance codes, which is sent as one code of zero bits in
1N/A length.
1N/A 6. There are up to 286 literal/length codes. Code 256 represents the
1N/A end-of-block. Note however that the static length tree defines
1N/A 288 codes just to fill out the Huffman codes. Codes 286 and 287
1N/A cannot be used though, since there is no length base or extra bits
1N/A defined for them. Similarily, there are up to 30 distance codes.
1N/A However, static trees define 32 codes (all 5 bits) to fill out the
1N/A Huffman codes, but the last two had better not show up in the data.
1N/A 7. Unzip can check dynamic Huffman blocks for complete code sets.
1N/A The exception is that a single code would not be complete (see #4).
1N/A 8. The five bits following the block type is really the number of
1N/A literal codes sent minus 257.
1N/A 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
1N/A (1+6+6). Therefore, to output three times the length, you output
1N/A three codes (1+1+1), whereas to output four times the same length,
1N/A you only need two codes (1+3). Hmm.
1N/A 10. In the tree reconstruction algorithm, Code = Code + Increment
1N/A only if BitLength(i) is not zero. (Pretty obvious.)
1N/A 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
1N/A 12. Note: length code 284 can represent 227-258, but length code 285
1N/A really is 258. The last length deserves its own, short code
1N/A since it gets used a lot in very redundant files. The length
1N/A 258 is special since 258 - 3 (the min match length) is 255.
1N/A 13. The literal/length and distance code bit lengths are read as a
1N/A single stream of lengths. It is possible (and advantageous) for
1N/A a repeat code (16, 17, or 18) to go across the boundary between
1N/A the two sets of lengths.
1N/A */
1N/A
1N/A
1N/Alocal void inflate_blocks_reset(s, z, c)
1N/Ainflate_blocks_statef *s;
1N/Az_stream *z;
1N/AuLongf *c;
1N/A{
1N/A if (s->checkfn != Z_NULL)
1N/A *c = s->check;
1N/A if (s->mode == BTREE || s->mode == DTREE)
1N/A ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
1N/A if (s->mode == CODES)
1N/A {
1N/A inflate_codes_free(s->sub.decode.codes, z);
1N/A inflate_trees_free(s->sub.decode.td, z);
1N/A inflate_trees_free(s->sub.decode.tl, z);
1N/A }
1N/A s->mode = TYPE;
1N/A s->bitk = 0;
1N/A s->bitb = 0;
1N/A s->read = s->write = s->window;
1N/A if (s->checkfn != Z_NULL)
1N/A s->check = (*s->checkfn)(0L, Z_NULL, 0);
1N/A Trace((stderr, "inflate: blocks reset\n"));
1N/A}
1N/A
1N/A
1N/Alocal inflate_blocks_statef *inflate_blocks_new(z, c, w)
1N/Az_stream *z;
1N/Acheck_func c;
1N/AuInt w;
1N/A{
1N/A inflate_blocks_statef *s;
1N/A
1N/A if ((s = (inflate_blocks_statef *)ZALLOC
1N/A (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
1N/A return s;
1N/A if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
1N/A {
1N/A ZFREE(z, s, sizeof(struct inflate_blocks_state));
1N/A return Z_NULL;
1N/A }
1N/A s->end = s->window + w;
1N/A s->checkfn = c;
1N/A s->mode = TYPE;
1N/A Trace((stderr, "inflate: blocks allocated\n"));
1N/A inflate_blocks_reset(s, z, &s->check);
1N/A return s;
1N/A}
1N/A
1N/A
1N/Alocal int inflate_blocks(s, z, r)
1N/Ainflate_blocks_statef *s;
1N/Az_stream *z;
1N/Aint r;
1N/A{
1N/A uInt t; /* temporary storage */
1N/A uLong b; /* bit buffer */
1N/A uInt k; /* bits in bit buffer */
1N/A Bytef *p; /* input data pointer */
1N/A uInt n; /* bytes available there */
1N/A Bytef *q; /* output window write pointer */
1N/A uInt m; /* bytes to end of window or read pointer */
1N/A
1N/A /* copy input/output information to locals (UPDATE macro restores) */
1N/A LOAD
1N/A
1N/A /* process input based on current state */
1N/A while (1) switch (s->mode)
1N/A {
1N/A case TYPE:
1N/A NEEDBITS(3)
1N/A t = (uInt)b & 7;
1N/A s->last = t & 1;
1N/A switch (t >> 1)
1N/A {
1N/A case 0: /* stored */
1N/A Trace((stderr, "inflate: stored block%s\n",
1N/A s->last ? " (last)" : ""));
1N/A DUMPBITS(3)
1N/A t = k & 7; /* go to byte boundary */
1N/A DUMPBITS(t)
1N/A s->mode = LENS; /* get length of stored block */
1N/A break;
1N/A case 1: /* fixed */
1N/A Trace((stderr, "inflate: fixed codes block%s\n",
1N/A s->last ? " (last)" : ""));
1N/A {
1N/A uInt bl, bd;
1N/A inflate_huft *tl, *td;
1N/A
1N/A inflate_trees_fixed(&bl, &bd, &tl, &td);
1N/A s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
1N/A if (s->sub.decode.codes == Z_NULL)
1N/A {
1N/A r = Z_MEM_ERROR;
1N/A LEAVE
1N/A }
1N/A s->sub.decode.tl = Z_NULL; /* don't try to free these */
1N/A s->sub.decode.td = Z_NULL;
1N/A }
1N/A DUMPBITS(3)
1N/A s->mode = CODES;
1N/A break;
1N/A case 2: /* dynamic */
1N/A Trace((stderr, "inflate: dynamic codes block%s\n",
1N/A s->last ? " (last)" : ""));
1N/A DUMPBITS(3)
1N/A s->mode = TABLE;
1N/A break;
1N/A case 3: /* illegal */
1N/A DUMPBITS(3)
1N/A s->mode = BADB;
1N/A z->msg = "invalid block type";
1N/A r = Z_DATA_ERROR;
1N/A LEAVE
1N/A }
1N/A break;
1N/A case LENS:
1N/A NEEDBITS(32)
1N/A if (((~b) >> 16) != (b & 0xffff))
1N/A {
1N/A s->mode = BADB;
1N/A z->msg = "invalid stored block lengths";
1N/A r = Z_DATA_ERROR;
1N/A LEAVE
1N/A }
1N/A s->sub.left = (uInt)b & 0xffff;
1N/A b = k = 0; /* dump bits */
1N/A Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
1N/A s->mode = s->sub.left ? STORED : TYPE;
1N/A break;
1N/A case STORED:
1N/A if (n == 0)
1N/A LEAVE
1N/A NEEDOUT
1N/A t = s->sub.left;
1N/A if (t > n) t = n;
1N/A if (t > m) t = m;
1N/A zmemcpy(q, p, t);
1N/A p += t; n -= t;
1N/A q += t; m -= t;
1N/A if ((s->sub.left -= t) != 0)
1N/A break;
1N/A Tracev((stderr, "inflate: stored end, %lu total out\n",
1N/A z->total_out + (q >= s->read ? q - s->read :
1N/A (s->end - s->read) + (q - s->window))));
1N/A s->mode = s->last ? DRY : TYPE;
1N/A break;
1N/A case TABLE:
1N/A NEEDBITS(14)
1N/A s->sub.trees.table = t = (uInt)b & 0x3fff;
1N/A#ifndef PKZIP_BUG_WORKAROUND
1N/A if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
1N/A {
1N/A s->mode = BADB;
1N/A z->msg = "too many length or distance symbols";
1N/A r = Z_DATA_ERROR;
1N/A LEAVE
1N/A }
1N/A#endif
1N/A t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
1N/A if (t < 19)
1N/A t = 19;
1N/A if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
1N/A {
1N/A r = Z_MEM_ERROR;
1N/A LEAVE
1N/A }
1N/A s->sub.trees.nblens = t;
1N/A DUMPBITS(14)
1N/A s->sub.trees.index = 0;
1N/A Tracev((stderr, "inflate: table sizes ok\n"));
1N/A s->mode = BTREE;
1N/A case BTREE:
1N/A while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
1N/A {
1N/A NEEDBITS(3)
1N/A s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
1N/A DUMPBITS(3)
1N/A }
1N/A while (s->sub.trees.index < 19)
1N/A s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
1N/A s->sub.trees.bb = 7;
1N/A t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
1N/A &s->sub.trees.tb, z);
1N/A if (t != Z_OK)
1N/A {
1N/A r = t;
1N/A if (r == Z_DATA_ERROR)
1N/A s->mode = BADB;
1N/A LEAVE
1N/A }
1N/A s->sub.trees.index = 0;
1N/A Tracev((stderr, "inflate: bits tree ok\n"));
1N/A s->mode = DTREE;
1N/A case DTREE:
1N/A while (t = s->sub.trees.table,
1N/A s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
1N/A {
1N/A inflate_huft *h;
1N/A uInt i, j, c;
1N/A
1N/A t = s->sub.trees.bb;
1N/A NEEDBITS(t)
1N/A h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
1N/A t = h->word.what.Bits;
1N/A c = h->more.Base;
1N/A if (c < 16)
1N/A {
1N/A DUMPBITS(t)
1N/A s->sub.trees.blens[s->sub.trees.index++] = c;
1N/A }
1N/A else /* c == 16..18 */
1N/A {
1N/A i = c == 18 ? 7 : c - 14;
1N/A j = c == 18 ? 11 : 3;
1N/A NEEDBITS(t + i)
1N/A DUMPBITS(t)
1N/A j += (uInt)b & inflate_mask[i];
1N/A DUMPBITS(i)
1N/A i = s->sub.trees.index;
1N/A t = s->sub.trees.table;
1N/A if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
1N/A (c == 16 && i < 1))
1N/A {
1N/A s->mode = BADB;
1N/A z->msg = "invalid bit length repeat";
1N/A r = Z_DATA_ERROR;
1N/A LEAVE
1N/A }
1N/A c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
1N/A do {
1N/A s->sub.trees.blens[i++] = c;
1N/A } while (--j);
1N/A s->sub.trees.index = i;
1N/A }
1N/A }
1N/A inflate_trees_free(s->sub.trees.tb, z);
1N/A s->sub.trees.tb = Z_NULL;
1N/A {
1N/A uInt bl, bd;
1N/A inflate_huft *tl, *td;
1N/A inflate_codes_statef *c;
1N/A
1N/A bl = 9; /* must be <= 9 for lookahead assumptions */
1N/A bd = 6; /* must be <= 9 for lookahead assumptions */
1N/A t = s->sub.trees.table;
1N/A t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
1N/A s->sub.trees.blens, &bl, &bd, &tl, &td, z);
1N/A if (t != Z_OK)
1N/A {
1N/A if (t == (uInt)Z_DATA_ERROR)
1N/A s->mode = BADB;
1N/A r = t;
1N/A LEAVE
1N/A }
1N/A Tracev((stderr, "inflate: trees ok\n"));
1N/A if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
1N/A {
1N/A inflate_trees_free(td, z);
1N/A inflate_trees_free(tl, z);
1N/A r = Z_MEM_ERROR;
1N/A LEAVE
1N/A }
1N/A ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
1N/A s->sub.decode.codes = c;
1N/A s->sub.decode.tl = tl;
1N/A s->sub.decode.td = td;
1N/A }
1N/A s->mode = CODES;
1N/A case CODES:
1N/A UPDATE
1N/A if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
1N/A return inflate_flush(s, z, r);
1N/A r = Z_OK;
1N/A inflate_codes_free(s->sub.decode.codes, z);
1N/A inflate_trees_free(s->sub.decode.td, z);
1N/A inflate_trees_free(s->sub.decode.tl, z);
1N/A LOAD
1N/A Tracev((stderr, "inflate: codes end, %lu total out\n",
1N/A z->total_out + (q >= s->read ? q - s->read :
1N/A (s->end - s->read) + (q - s->window))));
1N/A if (!s->last)
1N/A {
1N/A s->mode = TYPE;
1N/A break;
1N/A }
1N/A if (k > 7) /* return unused byte, if any */
1N/A {
1N/A Assert(k < 16, "inflate_codes grabbed too many bytes")
1N/A k -= 8;
1N/A n++;
1N/A p--; /* can always return one */
1N/A }
1N/A s->mode = DRY;
1N/A case DRY:
1N/A FLUSH
1N/A if (s->read != s->write)
1N/A LEAVE
1N/A s->mode = DONEB;
1N/A case DONEB:
1N/A r = Z_STREAM_END;
1N/A LEAVE
1N/A case BADB:
1N/A r = Z_DATA_ERROR;
1N/A LEAVE
1N/A default:
1N/A r = Z_STREAM_ERROR;
1N/A LEAVE
1N/A }
1N/A}
1N/A
1N/A
1N/Alocal int inflate_blocks_free(s, z, c)
1N/Ainflate_blocks_statef *s;
1N/Az_stream *z;
1N/AuLongf *c;
1N/A{
1N/A inflate_blocks_reset(s, z, c);
1N/A ZFREE(z, s->window, s->end - s->window);
1N/A ZFREE(z, s, sizeof(struct inflate_blocks_state));
1N/A Trace((stderr, "inflate: blocks freed\n"));
1N/A return Z_OK;
1N/A}
1N/A
1N/A/*
1N/A * This subroutine adds the data at next_in/avail_in to the output history
1N/A * without performing any output. The output buffer must be "caught up";
1N/A * i.e. no pending output (hence s->read equals s->write), and the state must
1N/A * be BLOCKS (i.e. we should be willing to see the start of a series of
1N/A * BLOCKS). On exit, the output will also be caught up, and the checksum
1N/A * will have been updated if need be.
1N/A */
1N/Alocal int inflate_addhistory(s, z)
1N/Ainflate_blocks_statef *s;
1N/Az_stream *z;
1N/A{
1N/A uLong b; /* bit buffer */ /* NOT USED HERE */
1N/A uInt k; /* bits in bit buffer */ /* NOT USED HERE */
1N/A uInt t; /* temporary storage */
1N/A Bytef *p; /* input data pointer */
1N/A uInt n; /* bytes available there */
1N/A Bytef *q; /* output window write pointer */
1N/A uInt m; /* bytes to end of window or read pointer */
1N/A
1N/A if (s->read != s->write)
1N/A return Z_STREAM_ERROR;
1N/A if (s->mode != TYPE)
1N/A return Z_DATA_ERROR;
1N/A
1N/A /* we're ready to rock */
1N/A LOAD
1N/A /* while there is input ready, copy to output buffer, moving
1N/A * pointers as needed.
1N/A */
1N/A while (n) {
1N/A t = n; /* how many to do */
1N/A /* is there room until end of buffer? */
1N/A if (t > m) t = m;
1N/A /* update check information */
1N/A if (s->checkfn != Z_NULL)
1N/A s->check = (*s->checkfn)(s->check, q, t);
1N/A zmemcpy(q, p, t);
1N/A q += t;
1N/A p += t;
1N/A n -= t;
1N/A z->total_out += t;
1N/A s->read = q; /* drag read pointer forward */
1N/A/* WRAP */ /* expand WRAP macro by hand to handle s->read */
1N/A if (q == s->end) {
1N/A s->read = q = s->window;
1N/A m = WAVAIL;
1N/A }
1N/A }
1N/A UPDATE
1N/A return Z_OK;
1N/A}
1N/A
1N/A
1N/A/*
1N/A * At the end of a Deflate-compressed PPP packet, we expect to have seen
1N/A * a `stored' block type value but not the (zero) length bytes.
1N/A */
1N/Alocal int inflate_packet_flush(s)
1N/A inflate_blocks_statef *s;
1N/A{
1N/A if (s->mode != LENS)
1N/A return Z_DATA_ERROR;
1N/A s->mode = TYPE;
1N/A return Z_OK;
1N/A}
1N/A
1N/A
1N/A/*+++++*/
1N/A/* inftrees.c -- generate Huffman trees for efficient decoding
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* simplify the use of the inflate_huft type with some defines */
1N/A#define base more.Base
1N/A#define next more.Next
1N/A#define exop word.what.Exop
1N/A#define bits word.what.Bits
1N/A
1N/A
1N/Alocal int huft_build OF((
1N/A uIntf *, /* code lengths in bits */
1N/A uInt, /* number of codes */
1N/A uInt, /* number of "simple" codes */
1N/A uIntf *, /* list of base values for non-simple codes */
1N/A uIntf *, /* list of extra bits for non-simple codes */
1N/A inflate_huft * FAR*,/* result: starting table */
1N/A uIntf *, /* maximum lookup bits (returns actual) */
1N/A z_stream *)); /* for zalloc function */
1N/A
1N/Alocal voidpf falloc OF((
1N/A voidpf, /* opaque pointer (not used) */
1N/A uInt, /* number of items */
1N/A uInt)); /* size of item */
1N/A
1N/Alocal void ffree OF((
1N/A voidpf q, /* opaque pointer (not used) */
1N/A voidpf p, /* what to free (not used) */
1N/A uInt n)); /* number of bytes (not used) */
1N/A
1N/A/* Tables for deflate from PKZIP's appnote.txt. */
1N/Alocal uInt cplens[] = { /* Copy lengths for literal codes 257..285 */
1N/A 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
1N/A 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
1N/A /* actually lengths - 2; also see note #13 above about 258 */
1N/Alocal uInt cplext[] = { /* Extra bits for literal codes 257..285 */
1N/A 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
1N/A 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 192, 192}; /* 192==invalid */
1N/Alocal uInt cpdist[] = { /* Copy offsets for distance codes 0..29 */
1N/A 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
1N/A 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
1N/A 8193, 12289, 16385, 24577};
1N/Alocal uInt cpdext[] = { /* Extra bits for distance codes */
1N/A 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
1N/A 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
1N/A 12, 12, 13, 13};
1N/A
1N/A/*
1N/A Huffman code decoding is performed using a multi-level table lookup.
1N/A The fastest way to decode is to simply build a lookup table whose
1N/A size is determined by the longest code. However, the time it takes
1N/A to build this table can also be a factor if the data being decoded
1N/A is not very long. The most common codes are necessarily the
1N/A shortest codes, so those codes dominate the decoding time, and hence
1N/A the speed. The idea is you can have a shorter table that decodes the
1N/A shorter, more probable codes, and then point to subsidiary tables for
1N/A the longer codes. The time it costs to decode the longer codes is
1N/A then traded against the time it takes to make longer tables.
1N/A
1N/A This results of this trade are in the variables lbits and dbits
1N/A below. lbits is the number of bits the first level table for literal/
1N/A length codes can decode in one step, and dbits is the same thing for
1N/A the distance codes. Subsequent tables are also less than or equal to
1N/A those sizes. These values may be adjusted either when all of the
1N/A codes are shorter than that, in which case the longest code length in
1N/A bits is used, or when the shortest code is *longer* than the requested
1N/A table size, in which case the length of the shortest code in bits is
1N/A used.
1N/A
1N/A There are two different values for the two tables, since they code a
1N/A different number of possibilities each. The literal/length table
1N/A codes 286 possible values, or in a flat code, a little over eight
1N/A bits. The distance table codes 30 possible values, or a little less
1N/A than five bits, flat. The optimum values for speed end up being
1N/A about one bit more than those, so lbits is 8+1 and dbits is 5+1.
1N/A The optimum values may differ though from machine to machine, and
1N/A possibly even between compilers. Your mileage may vary.
1N/A */
1N/A
1N/A
1N/A/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
1N/A#define BMAX 15 /* maximum bit length of any code */
1N/A#define N_MAX 288 /* maximum number of codes in any set */
1N/A
1N/A#ifdef DEBUG_ZLIB
1N/A uInt inflate_hufts;
1N/A#endif
1N/A
1N/Alocal int huft_build(b, n, s, d, e, t, m, zs)
1N/AuIntf *b; /* code lengths in bits (all assumed <= BMAX) */
1N/AuInt n; /* number of codes (assumed <= N_MAX) */
1N/AuInt s; /* number of simple-valued codes (0..s-1) */
1N/AuIntf *d; /* list of base values for non-simple codes */
1N/AuIntf *e; /* list of extra bits for non-simple codes */
1N/Ainflate_huft * FAR *t; /* result: starting table */
1N/AuIntf *m; /* maximum lookup bits, returns actual */
1N/Az_stream *zs; /* for zalloc function */
1N/A/* Given a list of code lengths and a maximum table size, make a set of
1N/A tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR
1N/A if the given code set is incomplete (the tables are still built in this
1N/A case), Z_DATA_ERROR if the input is invalid (all zero length codes or an
1N/A over-subscribed set of lengths), or Z_MEM_ERROR if not enough memory. */
1N/A{
1N/A
1N/A uInt a; /* counter for codes of length k */
1N/A uInt c[BMAX+1]; /* bit length count table */
1N/A uInt f; /* i repeats in table every f entries */
1N/A int g; /* maximum code length */
1N/A int h; /* table level */
1N/A register uInt i; /* counter, current code */
1N/A register uInt j; /* counter */
1N/A register int k; /* number of bits in current code */
1N/A int l; /* bits per table (returned in m) */
1N/A register uIntf *p; /* pointer into c[], b[], or v[] */
1N/A inflate_huft *q; /* points to current table */
1N/A struct inflate_huft_s r; /* table entry for structure assignment */
1N/A inflate_huft *u[BMAX]; /* table stack */
1N/A uInt v[N_MAX]; /* values in order of bit length */
1N/A register int w; /* bits before this table == (l * h) */
1N/A uInt x[BMAX+1]; /* bit offsets, then code stack */
1N/A uIntf *xp; /* pointer into x */
1N/A int y; /* number of dummy codes added */
1N/A uInt z; /* number of entries in current table */
1N/A
1N/A
1N/A /* Generate counts for each bit length */
1N/A p = c;
1N/A#define C0 *p++ = 0;
1N/A#define C2 C0 C0 C0 C0
1N/A#define C4 C2 C2 C2 C2
1N/A C4 /* clear c[]--assume BMAX+1 is 16 */
1N/A p = b; i = n;
1N/A do {
1N/A c[*p++]++; /* assume all entries <= BMAX */
1N/A } while (--i);
1N/A if (c[0] == n) /* null input--all zero length codes */
1N/A {
1N/A *t = (inflate_huft *)Z_NULL;
1N/A *m = 0;
1N/A return Z_OK;
1N/A }
1N/A
1N/A
1N/A /* Find minimum and maximum length, bound *m by those */
1N/A l = *m;
1N/A for (j = 1; j <= BMAX; j++)
1N/A if (c[j])
1N/A break;
1N/A k = j; /* minimum code length */
1N/A if ((uInt)l < j)
1N/A l = j;
1N/A for (i = BMAX; i; i--)
1N/A if (c[i])
1N/A break;
1N/A g = i; /* maximum code length */
1N/A if ((uInt)l > i)
1N/A l = i;
1N/A *m = l;
1N/A
1N/A
1N/A /* Adjust last length count to fill out codes, if needed */
1N/A for (y = 1 << j; j < i; j++, y <<= 1)
1N/A if ((y -= c[j]) < 0)
1N/A return Z_DATA_ERROR;
1N/A if ((y -= c[i]) < 0)
1N/A return Z_DATA_ERROR;
1N/A c[i] += y;
1N/A
1N/A
1N/A /* Generate starting offsets into the value table for each length */
1N/A x[1] = j = 0;
1N/A p = c + 1; xp = x + 2;
1N/A while (--i) { /* note that i == g from above */
1N/A *xp++ = (j += *p++);
1N/A }
1N/A
1N/A
1N/A /* Make a table of values in order of bit lengths */
1N/A p = b; i = 0;
1N/A do {
1N/A if ((j = *p++) != 0)
1N/A v[x[j]++] = i;
1N/A } while (++i < n);
1N/A
1N/A
1N/A /* Generate the Huffman codes and for each, make the table entries */
1N/A x[0] = i = 0; /* first Huffman code is zero */
1N/A p = v; /* grab values in bit order */
1N/A h = -1; /* no tables yet--level -1 */
1N/A w = -l; /* bits decoded == (l * h) */
1N/A u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */
1N/A q = (inflate_huft *)Z_NULL; /* ditto */
1N/A z = 0; /* ditto */
1N/A
1N/A /* go through the bit lengths (k already is bits in shortest code) */
1N/A for (; k <= g; k++)
1N/A {
1N/A a = c[k];
1N/A while (a--)
1N/A {
1N/A /* here i is the Huffman code of length k bits for value *p */
1N/A /* make tables up to required level */
1N/A while (k > w + l)
1N/A {
1N/A h++;
1N/A w += l; /* previous table always l bits */
1N/A
1N/A /* compute minimum size table less than or equal to l bits */
1N/A z = (z = g - w) > (uInt)l ? l : z; /* table size upper limit */
1N/A if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
1N/A { /* too few codes for k-w bit table */
1N/A f -= a + 1; /* deduct codes from patterns left */
1N/A xp = c + k;
1N/A if (j < z)
1N/A while (++j < z) /* try smaller tables up to z bits */
1N/A {
1N/A if ((f <<= 1) <= *++xp)
1N/A break; /* enough codes to use up j bits */
1N/A f -= *xp; /* else deduct codes from patterns */
1N/A }
1N/A }
1N/A z = 1 << j; /* table entries for j-bit table */
1N/A
1N/A /* allocate and link in new table */
1N/A if ((q = (inflate_huft *)ZALLOC
1N/A (zs,z + 1,sizeof(inflate_huft))) == Z_NULL)
1N/A {
1N/A if (h)
1N/A inflate_trees_free(u[0], zs);
1N/A return Z_MEM_ERROR; /* not enough memory */
1N/A }
1N/A q->word.Nalloc = z + 1;
1N/A#ifdef DEBUG_ZLIB
1N/A inflate_hufts += z + 1;
1N/A#endif
1N/A *t = q + 1; /* link to list for huft_free() */
1N/A *(t = &(q->next)) = Z_NULL;
1N/A u[h] = ++q; /* table starts after link */
1N/A
1N/A /* connect to last table, if there is one */
1N/A if (h)
1N/A {
1N/A x[h] = i; /* save pattern for backing up */
1N/A r.bits = (Byte)l; /* bits to dump before this table */
1N/A r.exop = (Byte)j; /* bits in this table */
1N/A r.next = q; /* pointer to this table */
1N/A j = i >> (w - l); /* (get around Turbo C bug) */
1N/A u[h-1][j] = r; /* connect to last table */
1N/A }
1N/A }
1N/A
1N/A /* set up table entry in r */
1N/A r.bits = (Byte)(k - w);
1N/A if (p >= v + n)
1N/A r.exop = 128 + 64; /* out of values--invalid code */
1N/A else if (*p < s)
1N/A {
1N/A r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */
1N/A r.base = *p++; /* simple code is just the value */
1N/A }
1N/A else
1N/A {
1N/A r.exop = (Byte)e[*p - s] + 16 + 64; /* non-simple--look up in lists */
1N/A r.base = d[*p++ - s];
1N/A }
1N/A
1N/A /* fill code-like entries with r */
1N/A f = 1 << (k - w);
1N/A for (j = i >> w; j < z; j += f)
1N/A q[j] = r;
1N/A
1N/A /* backwards increment the k-bit code i */
1N/A for (j = 1 << (k - 1); i & j; j >>= 1)
1N/A i ^= j;
1N/A i ^= j;
1N/A
1N/A /* backup over finished tables */
1N/A while ((i & ((1 << w) - 1)) != x[h])
1N/A {
1N/A h--; /* don't need to update q */
1N/A w -= l;
1N/A }
1N/A }
1N/A }
1N/A
1N/A
1N/A /* Return Z_BUF_ERROR if we were given an incomplete table */
1N/A return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
1N/A}
1N/A
1N/A
1N/Alocal int inflate_trees_bits(c, bb, tb, z)
1N/AuIntf *c; /* 19 code lengths */
1N/AuIntf *bb; /* bits tree desired/actual depth */
1N/Ainflate_huft * FAR *tb; /* bits tree result */
1N/Az_stream *z; /* for zfree function */
1N/A{
1N/A int r;
1N/A
1N/A r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z);
1N/A if (r == Z_DATA_ERROR)
1N/A z->msg = "oversubscribed dynamic bit lengths tree";
1N/A else if (r == Z_BUF_ERROR)
1N/A {
1N/A inflate_trees_free(*tb, z);
1N/A z->msg = "incomplete dynamic bit lengths tree";
1N/A r = Z_DATA_ERROR;
1N/A }
1N/A return r;
1N/A}
1N/A
1N/A
1N/Alocal int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z)
1N/AuInt nl; /* number of literal/length codes */
1N/AuInt nd; /* number of distance codes */
1N/AuIntf *c; /* that many (total) code lengths */
1N/AuIntf *bl; /* literal desired/actual bit depth */
1N/AuIntf *bd; /* distance desired/actual bit depth */
1N/Ainflate_huft * FAR *tl; /* literal/length tree result */
1N/Ainflate_huft * FAR *td; /* distance tree result */
1N/Az_stream *z; /* for zfree function */
1N/A{
1N/A int r;
1N/A
1N/A /* build literal/length tree */
1N/A if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK)
1N/A {
1N/A if (r == Z_DATA_ERROR)
1N/A z->msg = "oversubscribed literal/length tree";
1N/A else if (r == Z_BUF_ERROR)
1N/A {
1N/A inflate_trees_free(*tl, z);
1N/A z->msg = "incomplete literal/length tree";
1N/A r = Z_DATA_ERROR;
1N/A }
1N/A return r;
1N/A }
1N/A
1N/A /* build distance tree */
1N/A if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK)
1N/A {
1N/A if (r == Z_DATA_ERROR)
1N/A z->msg = "oversubscribed literal/length tree";
1N/A else if (r == Z_BUF_ERROR) {
1N/A#ifdef PKZIP_BUG_WORKAROUND
1N/A r = Z_OK;
1N/A }
1N/A#else
1N/A inflate_trees_free(*td, z);
1N/A z->msg = "incomplete literal/length tree";
1N/A r = Z_DATA_ERROR;
1N/A }
1N/A inflate_trees_free(*tl, z);
1N/A return r;
1N/A#endif
1N/A }
1N/A
1N/A /* done */
1N/A return Z_OK;
1N/A}
1N/A
1N/A
1N/A/* build fixed tables only once--keep them here */
1N/Alocal int fixed_lock = 0;
1N/Alocal int fixed_built = 0;
1N/A#define FIXEDH 530 /* number of hufts used by fixed tables */
1N/Alocal uInt fixed_left = FIXEDH;
1N/Alocal inflate_huft fixed_mem[FIXEDH];
1N/Alocal uInt fixed_bl;
1N/Alocal uInt fixed_bd;
1N/Alocal inflate_huft *fixed_tl;
1N/Alocal inflate_huft *fixed_td;
1N/A
1N/A
1N/Alocal voidpf falloc(q, n, s)
1N/Avoidpf q; /* opaque pointer (not used) */
1N/AuInt n; /* number of items */
1N/AuInt s; /* size of item */
1N/A{
1N/A Assert(s == sizeof(inflate_huft) && n <= fixed_left,
1N/A "inflate_trees falloc overflow");
1N/A if (q) s++; /* to make some compilers happy */
1N/A fixed_left -= n;
1N/A return (voidpf)(fixed_mem + fixed_left);
1N/A}
1N/A
1N/A
1N/Alocal void ffree(q, p, n)
1N/Avoidpf q;
1N/Avoidpf p;
1N/AuInt n;
1N/A{
1N/A Assert(0, "inflate_trees ffree called!");
1N/A if (q) q = p; /* to make some compilers happy */
1N/A}
1N/A
1N/A
1N/Alocal int inflate_trees_fixed(bl, bd, tl, td)
1N/AuIntf *bl; /* literal desired/actual bit depth */
1N/AuIntf *bd; /* distance desired/actual bit depth */
1N/Ainflate_huft * FAR *tl; /* literal/length tree result */
1N/Ainflate_huft * FAR *td; /* distance tree result */
1N/A{
1N/A /* build fixed tables if not built already--lock out other instances */
1N/A while (++fixed_lock > 1)
1N/A fixed_lock--;
1N/A if (!fixed_built)
1N/A {
1N/A int k; /* temporary variable */
1N/A unsigned c[288]; /* length list for huft_build */
1N/A z_stream z; /* for falloc function */
1N/A
1N/A /* set up fake z_stream for memory routines */
1N/A z.zalloc = falloc;
1N/A z.zfree = ffree;
1N/A z.opaque = Z_NULL;
1N/A
1N/A /* literal table */
1N/A for (k = 0; k < 144; k++)
1N/A c[k] = 8;
1N/A for (; k < 256; k++)
1N/A c[k] = 9;
1N/A for (; k < 280; k++)
1N/A c[k] = 7;
1N/A for (; k < 288; k++)
1N/A c[k] = 8;
1N/A fixed_bl = 7;
1N/A huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z);
1N/A
1N/A /* distance table */
1N/A for (k = 0; k < 30; k++)
1N/A c[k] = 5;
1N/A fixed_bd = 5;
1N/A huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z);
1N/A
1N/A /* done */
1N/A fixed_built = 1;
1N/A }
1N/A fixed_lock--;
1N/A *bl = fixed_bl;
1N/A *bd = fixed_bd;
1N/A *tl = fixed_tl;
1N/A *td = fixed_td;
1N/A return Z_OK;
1N/A}
1N/A
1N/A
1N/Alocal int inflate_trees_free(t, z)
1N/Ainflate_huft *t; /* table to free */
1N/Az_stream *z; /* for zfree function */
1N/A/* Free the malloc'ed tables built by huft_build(), which makes a linked
1N/A list of the tables it made, with the links in a dummy first entry of
1N/A each table. */
1N/A{
1N/A register inflate_huft *p, *q;
1N/A
1N/A /* Go through linked list, freeing from the malloced (t[-1]) address. */
1N/A p = t;
1N/A while (p != Z_NULL)
1N/A {
1N/A q = (--p)->next;
1N/A ZFREE(z, p, p->word.Nalloc * sizeof(inflate_huft));
1N/A p = q;
1N/A }
1N/A return Z_OK;
1N/A}
1N/A
1N/A/*+++++*/
1N/A/* infcodes.c -- process literals and length/distance pairs
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* simplify the use of the inflate_huft type with some defines */
1N/A#define base more.Base
1N/A#define next more.Next
1N/A#define exop word.what.Exop
1N/A#define bits word.what.Bits
1N/A
1N/A/* inflate codes private state */
1N/Astruct inflate_codes_state {
1N/A
1N/A /* mode */
1N/A enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
1N/A START, /* x: set up for LEN */
1N/A LEN, /* i: get length/literal/eob next */
1N/A LENEXT, /* i: getting length extra (have base) */
1N/A DIST, /* i: get distance next */
1N/A DISTEXT, /* i: getting distance extra */
1N/A COPY, /* o: copying bytes in window, waiting for space */
1N/A LIT, /* o: got literal, waiting for output space */
1N/A WASH, /* o: got eob, possibly still output waiting */
1N/A END, /* x: got eob and all data flushed */
1N/A BADCODE} /* x: got error */
1N/A mode; /* current inflate_codes mode */
1N/A
1N/A /* mode dependent information */
1N/A uInt len;
1N/A union {
1N/A struct {
1N/A inflate_huft *tree; /* pointer into tree */
1N/A uInt need; /* bits needed */
1N/A } code; /* if LEN or DIST, where in tree */
1N/A uInt lit; /* if LIT, literal */
1N/A struct {
1N/A uInt get; /* bits to get for extra */
1N/A uInt dist; /* distance back to copy from */
1N/A } copy; /* if EXT or COPY, where and how much */
1N/A } sub; /* submode */
1N/A
1N/A /* mode independent information */
1N/A Byte lbits; /* ltree bits decoded per branch */
1N/A Byte dbits; /* dtree bits decoder per branch */
1N/A inflate_huft *ltree; /* literal/length/eob tree */
1N/A inflate_huft *dtree; /* distance tree */
1N/A
1N/A};
1N/A
1N/A
1N/Alocal inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
1N/AuInt bl, bd;
1N/Ainflate_huft *tl, *td;
1N/Az_stream *z;
1N/A{
1N/A inflate_codes_statef *c;
1N/A
1N/A if ((c = (inflate_codes_statef *)
1N/A ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
1N/A {
1N/A c->mode = START;
1N/A c->lbits = (Byte)bl;
1N/A c->dbits = (Byte)bd;
1N/A c->ltree = tl;
1N/A c->dtree = td;
1N/A Tracev((stderr, "inflate: codes new\n"));
1N/A }
1N/A return c;
1N/A}
1N/A
1N/A
1N/Alocal int inflate_codes(s, z, r)
1N/Ainflate_blocks_statef *s;
1N/Az_stream *z;
1N/Aint r;
1N/A{
1N/A uInt j; /* temporary storage */
1N/A inflate_huft *t; /* temporary pointer */
1N/A uInt e; /* extra bits or operation */
1N/A uLong b; /* bit buffer */
1N/A uInt k; /* bits in bit buffer */
1N/A Bytef *p; /* input data pointer */
1N/A uInt n; /* bytes available there */
1N/A Bytef *q; /* output window write pointer */
1N/A uInt m; /* bytes to end of window or read pointer */
1N/A Bytef *f; /* pointer to copy strings from */
1N/A inflate_codes_statef *c = s->sub.decode.codes; /* codes state */
1N/A
1N/A /* copy input/output information to locals (UPDATE macro restores) */
1N/A LOAD
1N/A
1N/A /* process input and output based on current state */
1N/A while (1) switch (c->mode)
1N/A { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
1N/A case START: /* x: set up for LEN */
1N/A#ifndef SLOW
1N/A if (m >= 258 && n >= 10)
1N/A {
1N/A UPDATE
1N/A r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
1N/A LOAD
1N/A if (r != Z_OK)
1N/A {
1N/A c->mode = r == Z_STREAM_END ? WASH : BADCODE;
1N/A break;
1N/A }
1N/A }
1N/A#endif /* !SLOW */
1N/A c->sub.code.need = c->lbits;
1N/A c->sub.code.tree = c->ltree;
1N/A c->mode = LEN;
1N/A case LEN: /* i: get length/literal/eob next */
1N/A j = c->sub.code.need;
1N/A NEEDBITS(j)
1N/A t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
1N/A DUMPBITS(t->bits)
1N/A e = (uInt)(t->exop);
1N/A if (e == 0) /* literal */
1N/A {
1N/A c->sub.lit = t->base;
1N/A Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
1N/A "inflate: literal '%c'\n" :
1N/A "inflate: literal 0x%02x\n", t->base));
1N/A c->mode = LIT;
1N/A break;
1N/A }
1N/A if (e & 16) /* length */
1N/A {
1N/A c->sub.copy.get = e & 15;
1N/A c->len = t->base;
1N/A c->mode = LENEXT;
1N/A break;
1N/A }
1N/A if ((e & 64) == 0) /* next table */
1N/A {
1N/A c->sub.code.need = e;
1N/A c->sub.code.tree = t->next;
1N/A break;
1N/A }
1N/A if (e & 32) /* end of block */
1N/A {
1N/A Tracevv((stderr, "inflate: end of block\n"));
1N/A c->mode = WASH;
1N/A break;
1N/A }
1N/A c->mode = BADCODE; /* invalid code */
1N/A z->msg = "invalid literal/length code";
1N/A r = Z_DATA_ERROR;
1N/A LEAVE
1N/A case LENEXT: /* i: getting length extra (have base) */
1N/A j = c->sub.copy.get;
1N/A NEEDBITS(j)
1N/A c->len += (uInt)b & inflate_mask[j];
1N/A DUMPBITS(j)
1N/A c->sub.code.need = c->dbits;
1N/A c->sub.code.tree = c->dtree;
1N/A Tracevv((stderr, "inflate: length %u\n", c->len));
1N/A c->mode = DIST;
1N/A case DIST: /* i: get distance next */
1N/A j = c->sub.code.need;
1N/A NEEDBITS(j)
1N/A t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
1N/A DUMPBITS(t->bits)
1N/A e = (uInt)(t->exop);
1N/A if (e & 16) /* distance */
1N/A {
1N/A c->sub.copy.get = e & 15;
1N/A c->sub.copy.dist = t->base;
1N/A c->mode = DISTEXT;
1N/A break;
1N/A }
1N/A if ((e & 64) == 0) /* next table */
1N/A {
1N/A c->sub.code.need = e;
1N/A c->sub.code.tree = t->next;
1N/A break;
1N/A }
1N/A c->mode = BADCODE; /* invalid code */
1N/A z->msg = "invalid distance code";
1N/A r = Z_DATA_ERROR;
1N/A LEAVE
1N/A case DISTEXT: /* i: getting distance extra */
1N/A j = c->sub.copy.get;
1N/A NEEDBITS(j)
1N/A c->sub.copy.dist += (uInt)b & inflate_mask[j];
1N/A DUMPBITS(j)
1N/A Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist));
1N/A c->mode = COPY;
1N/A case COPY: /* o: copying bytes in window, waiting for space */
1N/A#ifndef __TURBOC__ /* Turbo C bug for following expression */
1N/A f = (uInt)(q - s->window) < c->sub.copy.dist ?
1N/A s->end - (c->sub.copy.dist - (q - s->window)) :
1N/A q - c->sub.copy.dist;
1N/A#else
1N/A f = q - c->sub.copy.dist;
1N/A if ((uInt)(q - s->window) < c->sub.copy.dist)
1N/A f = s->end - (c->sub.copy.dist - (q - s->window));
1N/A#endif
1N/A while (c->len)
1N/A {
1N/A NEEDOUT
1N/A OUTBYTE(*f++)
1N/A if (f == s->end)
1N/A f = s->window;
1N/A c->len--;
1N/A }
1N/A c->mode = START;
1N/A break;
1N/A case LIT: /* o: got literal, waiting for output space */
1N/A NEEDOUT
1N/A OUTBYTE(c->sub.lit)
1N/A c->mode = START;
1N/A break;
1N/A case WASH: /* o: got eob, possibly more output */
1N/A FLUSH
1N/A if (s->read != s->write)
1N/A LEAVE
1N/A c->mode = END;
1N/A case END:
1N/A r = Z_STREAM_END;
1N/A LEAVE
1N/A case BADCODE: /* x: got error */
1N/A r = Z_DATA_ERROR;
1N/A LEAVE
1N/A default:
1N/A r = Z_STREAM_ERROR;
1N/A LEAVE
1N/A }
1N/A}
1N/A
1N/A
1N/Alocal void inflate_codes_free(c, z)
1N/Ainflate_codes_statef *c;
1N/Az_stream *z;
1N/A{
1N/A ZFREE(z, c, sizeof(struct inflate_codes_state));
1N/A Tracev((stderr, "inflate: codes free\n"));
1N/A}
1N/A
1N/A/*+++++*/
1N/A/* inflate_util.c -- data and routines common to blocks and codes
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* copy as much as possible from the sliding window to the output area */
1N/Alocal int inflate_flush(s, z, r)
1N/Ainflate_blocks_statef *s;
1N/Az_stream *z;
1N/Aint r;
1N/A{
1N/A uInt n;
1N/A Bytef *p, *q;
1N/A
1N/A /* local copies of source and destination pointers */
1N/A p = z->next_out;
1N/A q = s->read;
1N/A
1N/A /* compute number of bytes to copy as far as end of window */
1N/A n = (uInt)((q <= s->write ? s->write : s->end) - q);
1N/A if (n > z->avail_out) n = z->avail_out;
1N/A if (n && r == Z_BUF_ERROR) r = Z_OK;
1N/A
1N/A /* update counters */
1N/A z->avail_out -= n;
1N/A z->total_out += n;
1N/A
1N/A /* update check information */
1N/A if (s->checkfn != Z_NULL)
1N/A s->check = (*s->checkfn)(s->check, q, n);
1N/A
1N/A /* copy as far as end of window */
1N/A if (p != NULL) {
1N/A zmemcpy(p, q, n);
1N/A p += n;
1N/A }
1N/A q += n;
1N/A
1N/A /* see if more to copy at beginning of window */
1N/A if (q == s->end)
1N/A {
1N/A /* wrap pointers */
1N/A q = s->window;
1N/A if (s->write == s->end)
1N/A s->write = s->window;
1N/A
1N/A /* compute bytes to copy */
1N/A n = (uInt)(s->write - q);
1N/A if (n > z->avail_out) n = z->avail_out;
1N/A if (n && r == Z_BUF_ERROR) r = Z_OK;
1N/A
1N/A /* update counters */
1N/A z->avail_out -= n;
1N/A z->total_out += n;
1N/A
1N/A /* update check information */
1N/A if (s->checkfn != Z_NULL)
1N/A s->check = (*s->checkfn)(s->check, q, n);
1N/A
1N/A /* copy */
1N/A if (p != NULL) {
1N/A zmemcpy(p, q, n);
1N/A p += n;
1N/A }
1N/A q += n;
1N/A }
1N/A
1N/A /* update pointers */
1N/A z->next_out = p;
1N/A s->read = q;
1N/A
1N/A /* done */
1N/A return r;
1N/A}
1N/A
1N/A
1N/A/*+++++*/
1N/A/* inffast.c -- process literals and length/distance pairs fast
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* simplify the use of the inflate_huft type with some defines */
1N/A#define base more.Base
1N/A#define next more.Next
1N/A#define exop word.what.Exop
1N/A#define bits word.what.Bits
1N/A
1N/A/* macros for bit input with no checking and for returning unused bytes */
1N/A#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
1N/A#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
1N/A
1N/A/* Called with number of bytes left to write in window at least 258
1N/A (the maximum string length) and number of input bytes available
1N/A at least ten. The ten bytes are six bytes for the longest length/
1N/A distance pair plus four bytes for overloading the bit buffer. */
1N/A
1N/Alocal int inflate_fast(bl, bd, tl, td, s, z)
1N/AuInt bl, bd;
1N/Ainflate_huft *tl, *td;
1N/Ainflate_blocks_statef *s;
1N/Az_stream *z;
1N/A{
1N/A inflate_huft *t; /* temporary pointer */
1N/A uInt e; /* extra bits or operation */
1N/A uLong b; /* bit buffer */
1N/A uInt k; /* bits in bit buffer */
1N/A Bytef *p; /* input data pointer */
1N/A uInt n; /* bytes available there */
1N/A Bytef *q; /* output window write pointer */
1N/A uInt m; /* bytes to end of window or read pointer */
1N/A uInt ml; /* mask for literal/length tree */
1N/A uInt md; /* mask for distance tree */
1N/A uInt c; /* bytes to copy */
1N/A uInt d; /* distance back to copy from */
1N/A Bytef *r; /* copy source pointer */
1N/A
1N/A /* load input, output, bit values */
1N/A LOAD
1N/A
1N/A /* initialize masks */
1N/A ml = inflate_mask[bl];
1N/A md = inflate_mask[bd];
1N/A
1N/A /* do until not enough input or output space for fast loop */
1N/A do { /* assume called with m >= 258 && n >= 10 */
1N/A /* get literal/length code */
1N/A GRABBITS(20) /* max bits for literal/length code */
1N/A if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
1N/A {
1N/A DUMPBITS(t->bits)
1N/A Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
1N/A "inflate: * literal '%c'\n" :
1N/A "inflate: * literal 0x%02x\n", t->base));
1N/A *q++ = (Byte)t->base;
1N/A m--;
1N/A continue;
1N/A }
1N/A do {
1N/A DUMPBITS(t->bits)
1N/A if (e & 16)
1N/A {
1N/A /* get extra bits for length */
1N/A e &= 15;
1N/A c = t->base + ((uInt)b & inflate_mask[e]);
1N/A DUMPBITS(e)
1N/A Tracevv((stderr, "inflate: * length %u\n", c));
1N/A
1N/A /* decode distance base of block to copy */
1N/A GRABBITS(15); /* max bits for distance code */
1N/A e = (t = td + ((uInt)b & md))->exop;
1N/A do {
1N/A DUMPBITS(t->bits)
1N/A if (e & 16)
1N/A {
1N/A /* get extra bits to add to distance base */
1N/A e &= 15;
1N/A GRABBITS(e) /* get extra bits (up to 13) */
1N/A d = t->base + ((uInt)b & inflate_mask[e]);
1N/A DUMPBITS(e)
1N/A Tracevv((stderr, "inflate: * distance %u\n", d));
1N/A
1N/A /* do the copy */
1N/A m -= c;
1N/A if ((uInt)(q - s->window) >= d) /* offset before dest */
1N/A { /* just copy */
1N/A r = q - d;
1N/A *q++ = *r++; c--; /* minimum count is three, */
1N/A *q++ = *r++; c--; /* so unroll loop a little */
1N/A }
1N/A else /* else offset after destination */
1N/A {
1N/A e = d - (q - s->window); /* bytes from offset to end */
1N/A r = s->end - e; /* pointer to offset */
1N/A if (c > e) /* if source crosses, */
1N/A {
1N/A c -= e; /* copy to end of window */
1N/A do {
1N/A *q++ = *r++;
1N/A } while (--e);
1N/A r = s->window; /* copy rest from start of window */
1N/A }
1N/A }
1N/A do { /* copy all or what's left */
1N/A *q++ = *r++;
1N/A } while (--c);
1N/A break;
1N/A }
1N/A else if ((e & 64) == 0)
1N/A e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
1N/A else
1N/A {
1N/A z->msg = "invalid distance code";
1N/A UNGRAB
1N/A UPDATE
1N/A return Z_DATA_ERROR;
1N/A }
1N/A } while (1);
1N/A break;
1N/A }
1N/A if ((e & 64) == 0)
1N/A {
1N/A if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0)
1N/A {
1N/A DUMPBITS(t->bits)
1N/A Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
1N/A "inflate: * literal '%c'\n" :
1N/A "inflate: * literal 0x%02x\n", t->base));
1N/A *q++ = (Byte)t->base;
1N/A m--;
1N/A break;
1N/A }
1N/A }
1N/A else if (e & 32)
1N/A {
1N/A Tracevv((stderr, "inflate: * end of block\n"));
1N/A UNGRAB
1N/A UPDATE
1N/A return Z_STREAM_END;
1N/A }
1N/A else
1N/A {
1N/A z->msg = "invalid literal/length code";
1N/A UNGRAB
1N/A UPDATE
1N/A return Z_DATA_ERROR;
1N/A }
1N/A } while (1);
1N/A } while (m >= 258 && n >= 10);
1N/A
1N/A /* not enough input or output--restore pointers and return */
1N/A UNGRAB
1N/A UPDATE
1N/A return Z_OK;
1N/A}
1N/A
1N/A
1N/A/*+++++*/
1N/A/* zutil.c -- target dependent utility functions for the compression library
1N/A * Copyright (C) 1995 Jean-loup Gailly.
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* From: zutil.c,v 1.8 1995/05/03 17:27:12 jloup Exp */
1N/A
1N/Achar *zlib_version = ZLIB_VERSION;
1N/A
1N/Achar *z_errmsg[] = {
1N/A"stream end", /* Z_STREAM_END 1 */
1N/A"", /* Z_OK 0 */
1N/A"file error", /* Z_ERRNO (-1) */
1N/A"stream error", /* Z_STREAM_ERROR (-2) */
1N/A"data error", /* Z_DATA_ERROR (-3) */
1N/A"insufficient memory", /* Z_MEM_ERROR (-4) */
1N/A"buffer error", /* Z_BUF_ERROR (-5) */
1N/A""};
1N/A
1N/A
1N/A/*+++++*/
1N/A/* adler32.c -- compute the Adler-32 checksum of a data stream
1N/A * Copyright (C) 1995 Mark Adler
1N/A * For conditions of distribution and use, see copyright notice in zlib.h
1N/A */
1N/A
1N/A/* From: adler32.c,v 1.6 1995/05/03 17:27:08 jloup Exp */
1N/A
1N/A#define BASE 65521L /* largest prime smaller than 65536 */
1N/A#define NMAX 5552
1N/A/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
1N/A
1N/A#define DO1(buf) {s1 += *buf++; s2 += s1;}
1N/A#define DO2(buf) DO1(buf); DO1(buf);
1N/A#define DO4(buf) DO2(buf); DO2(buf);
1N/A#define DO8(buf) DO4(buf); DO4(buf);
1N/A#define DO16(buf) DO8(buf); DO8(buf);
1N/A
1N/A/* ========================================================================= */
1N/AuLong adler32(adler, buf, len)
1N/A uLong adler;
1N/A Bytef *buf;
1N/A uInt len;
1N/A{
1N/A unsigned long s1 = adler & 0xffff;
1N/A unsigned long s2 = (adler >> 16) & 0xffff;
1N/A int k;
1N/A
1N/A if (buf == Z_NULL) return 1L;
1N/A
1N/A while (len > 0) {
1N/A k = len < NMAX ? len : NMAX;
1N/A len -= k;
1N/A while (k >= 16) {
1N/A DO16(buf);
1N/A k -= 16;
1N/A }
1N/A if (k != 0) do {
1N/A DO1(buf);
1N/A } while (--k);
1N/A s1 %= BASE;
1N/A s2 %= BASE;
1N/A }
1N/A return (s2 << 16) | s1;
1N/A}