/*
* Copyright 2007 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
/*
* Updated from zlib-1.0.4 to zlib-1.1.3 by James Carlson.
*
* This file is derived from various .h and .c files from the zlib-1.0.4
* distribution by Jean-loup Gailly and Mark Adler, with some additions
* by Paul Mackerras to aid in implementing Deflate compression and
* decompression for PPP packets. See zlib.h for conditions of
* distribution and use.
*
* Changes that have been made include:
* - added Z_PACKET_FLUSH (see zlib.h for details)
* - added inflateIncomp and deflateOutputPending
* - allow strm->next_out to be NULL, meaning discard the output
*
* $Id: zlib.c,v 1.11 1998/09/13 23:37:12 paulus Exp $
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* ==FILEVERSION 971210==
*
* This marker is used by the Linux installation script to determine
* whether an up-to-date version of this file is already installed.
*/
#define NO_DUMMY_DECL
#define NO_ZCFUNCS
#define MY_ZCALLOC
#endif
/* +++ zutil.h */
/*
*
* zutil.h -- internal interface and configuration of the compression library
* Copyright (C) 1995-1998 Jean-loup Gailly.
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/*
* WARNING: this file should *not* be used by applications. It is part
* of the implementation of the compression library and is subject to
* change. Applications should only use zlib.h.
*/
/* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */
#ifndef _Z_UTIL_H
#define _Z_UTIL_H
#include "zlib.h"
/* Assume this is a *BSD or SVR4 kernel */
#ifdef SOL2
#endif
#define HAVE_MEMCPY
#else
#if defined(__KERNEL__)
/* Assume this is a Linux kernel */
#define HAVE_MEMCPY
#else /* not kernel */
#include <stddef.h>
#ifdef NO_ERRNO_H
extern int errno;
#else
#include <errno.h>
#endif
#ifdef STDC
#include <string.h>
#include <stdlib.h>
#endif
#endif /* __KERNEL__ */
#endif /* _KERNEL || KERNEL */
#ifndef local
#define local static
#endif
/* compile with -Dlocal if your debugger can't find static symbols */
typedef unsigned char uch;
typedef unsigned short ush;
typedef unsigned long ulg;
/* (size given to avoid silly warnings with Visual C++) */
/* To be used only when the state is known to be valid */
/* common constants */
#ifndef DEF_WBITS
#endif
/* default windowBits for decompression. MAX_WBITS is for compression only */
#if MAX_MEM_LEVEL >= 8
#else
#endif
/* default memLevel */
#define STORED_BLOCK 0
/* The three kinds of block type */
/* The minimum and maximum match lengths */
/* target dependencies */
#ifdef MSDOS
#ifdef __TURBOC__
#include <alloc.h>
#else /* MSC or DJGPP */
#include <malloc.h>
#endif
#endif
#ifdef OS2
#endif
#ifdef WIN32 /* Window 95 & Windows NT */
#endif
#endif
#ifdef AMIGA
#endif
#endif
#ifdef MACOS
#endif
#ifdef __50SERIES /* Prime/PRIMOS */
#endif
#ifdef TOPS20
#endif
#endif
/* Common defaults */
#ifndef OS_CODE
#endif
#ifndef F_OPEN
#endif
/* functions */
#ifdef HAVE_STRERROR
#else
#endif
#if defined(pyr)
#define NO_MEMCPY
#endif
/*
* Use our own functions for small and medium model with MSC <= 5.0.
* You may have to use the same strategy for Borland C (untested).
*/
#define NO_MEMCPY
#endif
#define HAVE_MEMCPY
#endif
#ifdef HAVE_MEMCPY
#ifdef SMALL_MEDIUM /* MSDOS small or medium model */
#else
#endif
#else
#endif
/* Diagnostic functions */
#ifdef DEBUG_ZLIB
#include <stdio.h>
#ifndef verbose
#define verbose 0
#endif
#else
#else
#endif
#define Trace(x) ((void)0)
#define Tracev(x) ((void)0)
#define Tracevv(x) ((void)0)
#define Tracec(c, x) ((void)0)
#define Tracecv(c, x) ((void)0)
#endif
/* voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); */
/* void zcfree OF((voidpf opaque, voidpf ptr)); */
#endif /* _Z_UTIL_H */
/* --- zutil.h */
/* +++ deflate.h */
/*
* deflate.h -- internal compression state
* Copyright (C) 1995-1998 Jean-loup Gailly
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/*
* WARNING: this file should *not* be used by applications. It is part
* of the implementation of the compression library and is subject to
* change. Applications should only use zlib.h.
*/
/* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */
#ifndef _DEFLATE_H
#define _DEFLATE_H
/* #include "zutil.h" */
/*
* ===========================================================================
* Internal compression state.
*/
/* number of length codes, not counting the special END_BLOCK code */
/* number of literal bytes 0..255 */
/* number of Literal or Length codes, including the END_BLOCK code */
/* number of distance codes */
/* number of codes used to transfer the bit lengths */
/* maximum heap size */
/* All codes must not exceed MAX_BITS bits */
/* Stream status */
/* Data structure describing a single value and its code string. */
typedef struct ct_data_s {
union {
} fc;
union {
} dl;
typedef struct tree_desc_s {
typedef unsigned IPos;
/*
* A Pos is an index in the character window. We use short instead of
* int to save space in the various tables. IPos is used only for
* parameter passing.
*/
typedef struct deflate_state {
/* value of flush param for previous deflate call */
int last_flush;
/* used by deflate.c: */
/*
* Sliding window. Input bytes are read into the second half
* of the window, and move to the first half later to keep a
* dictionary of at least wSize bytes. With this organization,
* matches are limited to a distance of wSize-MAX_MATCH bytes,
* but this ensures that IO is always performed with a length
* multiple of the block size. Also, it limits the window size
* to 64K, which is quite useful on MSDOS. To do: use the
* user input buffer as sliding window.
*/
/*
* Actual size of window: 2*wSize, except when the user input
* buffer is directly used as sliding window.
*/
/*
* Link to older string with same hash index. To limit the
* size of this array to 64K, this link is maintained only for
* the last 32K strings. An index in this array is thus a
* window index modulo 32K.
*/
/*
* Number of bits by which ins_h must be shifted at each input
* step. It must be such that after MIN_MATCH steps, the
* oldest byte no longer takes part in the hash key, that is:
* hash_shift * MIN_MATCH >= hash_bits
*/
long block_start;
/*
* Window position at the beginning of the current output
* block. Gets negative when the window is moved backwards.
*/
/*
* Length of the best match at previous step. Matches not
* greater than this are discarded. This is used in the lazy
* match evaluation.
*/
/*
* To speed up deflation, hash chains are never searched
* beyond *this length. A higher limit improves compression
* ratio but *degrades the speed.
*/
/*
* Attempt to find a better match only when the current match
* is strictly smaller than this value. This mechanism is used
* only for compression levels >= 4.
*/
/*
* Insert new strings in the hash table only if the match
* length is not greater than this length. This saves time but
* degrades compression. max_insert_length is used only for
* compression levels <= 3.
*/
/* Use a faster search when the previous match is longer than this */
/* used by trees.c: */
/* Didn't use ct_data typedef below to supress compiler warning */
/* Huffman tree for bit lengths */
/* number of codes at each bit length for an optimal tree */
/*
* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0]
* is not used. The same heap array is used to build all
* trees.
*/
/*
* Depth of each subtree used as tie breaker for trees of
* equal frequency
*/
/*
* reasons for limiting lit_bufsize to 64K:
*
* - frequencies can be kept in 16 bit counters
*
* - if compression is not successful for the first block,
* all input data is still in the window so we can still
* emit a stored block even when input comes from standard
* input. (This can also be done for all blocks if
* lit_bufsize is not greater than 32K.)
*
* - if compression is not successful for a file smaller
* than 64K, we can even emit a stored file instead of a
* stored block (saving 5 bytes). This is applicable only
* for zip (not gzip or zlib).
*
* - creating new Huffman trees less frequently may not
* provide fast adaptation to changes in the input data
* statistics. (Take for example a binary file with poorly
* compressible code followed by a highly compressible
* string table.) Smaller buffer sizes give fast adaptation
* but have of course the overhead of transmitting trees
* more frequently.
*
* - I can't count above 4
*/
/*
* Buffer for distances. To simplify the code, d_buf and l_buf
* have the same number of elements. To use different lengths,
* an extra flag array would be necessary.
*/
#ifdef DEBUG_ZLIB
#endif
/*
* Output buffer. bits are inserted starting at the bottom
* (least significant bits).
*/
int bi_valid;
/*
* Number of valid bits in bi_buf. All bits above the last
* valid bit are always zero.
*/
/*
* Output a byte on the stream. IN assertion: there is enough room in
* pending_buf.
*/
/*
* Minimum amount of lookahead, except at the end of the input file.
* See deflate.c for comments about the MIN_MATCH+1.
*/
/*
* In order to simplify the code, particularly on 16 bit machines,
* match distances are limited to MAX_DIST instead of WSIZE.
*/
/* in trees.c */
int eof));
int eof));
/*
* Mapping from a distance to a distance code. dist is the distance - 1 and
* must not have side effects. _dist_code[256] and _dist_code[257] are never
* used.
*/
#ifndef DEBUG_ZLIB
/* Inline versions of _tr_tally for speed: */
}
dist--; \
}
#else
#endif
#endif
/* --- deflate.h */
/* +++ deflate.c */
/*
* deflate.c -- compress data using the deflation algorithm
* Copyright (C) 1995-1998 Jean-loup Gailly.
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/*
* ALGORITHM
*
* The "deflation" process depends on being able to identify portions
* of the input text which are identical to earlier input (within a
* sliding window trailing behind the input currently being processed).
*
* The most straightforward technique turns out to be the fastest for
* most input files: try all possible matches and select the longest.
* The key feature of this algorithm is that insertions into the string
* dictionary are very simple and thus fast, and deletions are avoided
* completely. Insertions are performed at each input character, whereas
* string matches are performed only when the previous match ends. So it
* is preferable to spend more time in matches to allow very fast string
* insertions and avoid deletions. The matching algorithm for small
* strings is inspired from that of Rabin & Karp. A brute force approach
* is used to find longer strings when a small match has been found.
* A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
* (by Leonid Broukhis).
* A previous version of this file used a more sophisticated algorithm
* (by Fiala and Greene) which is guaranteed to run in linear amortized
* time, but has a larger average cost, uses more memory and is patented.
* However the F&G algorithm may be faster for some highly redundant
* files if the parameter max_chain_length (described below) is too large.
*
* ACKNOWLEDGEMENTS
*
* The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
* I found it in 'freeze' written by Leonid Broukhis.
* Thanks to many people for bug reports and testing.
*
* REFERENCES
*
* Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
* Available in ftp://ds.internic.net/rfc/rfc1951.txt
*
* A description of the Rabin and Karp algorithm is given in the book
* "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
*
* Fiala,E.R., and Greene,D.H.
* Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
*
*/
/* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */
/* #include "deflate.h" */
const char deflate_copyright[] =
" deflate 1.1.3 Copyright 1995-1998 Jean-loup Gailly ";
/*
* If you use the zlib library in a product, an acknowledgment is
* welcome in the documentation of your product. If for some reason
* you cannot include such an acknowledgment, I would appreciate that
* you keep this copyright string in the executable of your product.
*/
/*
* ===========================================================================
* Function prototypes.
*/
typedef enum {
/* block not completed, need more input or more output */
/* finish started, need only more output at next deflate */
} block_state;
/* Compression function. Returns the block state after the call. */
#ifdef ASMV
#else
#endif
#ifdef DEBUG_ZLIB
int length));
#endif
/*
* ===========================================================================
* Local data
*/
#define NIL 0
/* Tail of hash chains */
#ifndef TOO_FAR
#endif
/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
/*
* Minimum amount of lookahead, except at the end of the input file.
* See deflate.c for comments about the MIN_MATCH+1.
*/
/*
* Values for max_lazy_match, good_match and max_chain_length,
* depending on the desired pack level (0..9). The values given below
* have been tuned to exclude worst case performance for pathological
* files. Better values may be found for specific files.
*/
typedef struct config_s {
} config;
/* good lazy nice chain */
/*
* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
* For deflate_fast() (levels <= 3) good is ignored and lazy has a different
* meaning.
*/
#define EQUAL 0
/* result of memcmp for equal strings */
#ifndef NO_DUMMY_DECL
#endif
/*
* ===========================================================================
* Update a hash value with the given input byte
* IN assertion: all calls to to UPDATE_HASH are made with consecutive
* input characters, so that a running hash key can be computed from the
* previous key instead of complete recalculation each time.
*/
/*
* ===========================================================================
* Insert string str in the dictionary and set match_head to the previous head
* of the hash chain (the most recent string with same hash key). Return
* the previous length of the hash chain.
* If this file is compiled with -DFASTEST, the compression level is forced
* to 1, and no hash chains are maintained.
* IN assertion: all calls to to INSERT_STRING are made with consecutive
* input characters and the first MIN_MATCH bytes of str are valid
* (except for the last MIN_MATCH-1 bytes of the input file).
*/
#ifdef FASTEST
#else
#endif
/*
* ===========================================================================
* Initialize the hash table (avoiding 64K overflow for 16 bit systems).
* prev[] will be initialized on the fly.
*/
#define CLEAR_HASH(s) \
/* ========================================================================= */
int
int level;
const char *version;
int stream_size;
{
(void) deflate_copyright;
/* To do: ignore strm->next_in if we use it as window */
}
/* ========================================================================= */
int level;
int method;
int windowBits;
int memLevel;
int strategy;
const char *version;
int stream_size;
{
deflate_state *s;
int noheader = 0;
/*
* We overlay pending_buf and d_buf+l_buf. This works since
* the average output size for (length, distance) codes is <=
* 24 bits.
*/
stream_size != sizeof (z_stream)) {
return (Z_VERSION_ERROR);
}
return (Z_STREAM_ERROR);
#ifndef NO_ZCFUNCS
}
#endif
#ifdef FASTEST
level = 1;
#endif
if (windowBits < 0) { /* undocumented feature: suppress zlib header */
noheader = 1;
windowBits = -windowBits;
}
return (Z_STREAM_ERROR);
}
if (s == Z_NULL)
return (Z_MEM_ERROR);
s->w_bits = windowBits;
s->pending_buf == Z_NULL) {
s->status = INIT_STATE;
(void) deflateEnd(strm);
return (Z_MEM_ERROR);
}
return (deflateReset(strm));
}
/* ========================================================================= */
int
const Bytef *dictionary;
{
deflate_state *s;
uInt n;
return (Z_STREAM_ERROR);
if (s->status != INIT_STATE)
return (Z_STREAM_ERROR);
return (Z_OK);
#ifndef USE_DICT_HEAD
/* use the tail of the dictionary */
#endif
}
s->block_start = (long)length;
/*
* Insert all strings in the hash table (except for the last
* two bytes). s->lookahead stays null, so s->ins_h will be
* recomputed at the next call of fill_window.
*/
INSERT_STRING(s, n, hash_head);
}
return (Z_OK);
}
/* ========================================================================= */
int
{
deflate_state *s;
return (Z_STREAM_ERROR);
/* use zfree if we ever allocate msg dynamically */
s->pending = 0;
s->pending_out = s->pending_buf;
if (s->noheader < 0) {
/* was set to -1 by deflate(..., Z_FINISH); */
s->noheader = 0;
}
s->last_flush = Z_NO_FLUSH;
_tr_init(s);
lm_init(s);
return (Z_OK);
}
/* ========================================================================= */
int
int level;
int strategy;
{
deflate_state *s;
return (Z_STREAM_ERROR);
if (level == Z_DEFAULT_COMPRESSION) {
level = 6;
}
strategy > Z_HUFFMAN_ONLY) {
return (Z_STREAM_ERROR);
}
/* Flush the last buffer: */
}
}
return (err);
}
/*
* =========================================================================
* Put a short in the pending buffer. The 16-bit value is put in MSB order.
* IN assertion: the stream state is correct and there is enough room in
* pending_buf.
*/
local void
putShortMSB(s, b)
deflate_state *s;
uInt b;
{
}
/*
* =========================================================================
* Flush as much pending output as possible. All deflate() output goes
* through this function so some applications may wish to modify it
* to avoid allocating a large strm->next_out buffer and copying into it.
* (See also read_buf()).
*/
local void
{
if (len == 0)
return;
} /* PPP */
s->pending_out += len;
if (s->pending == 0) {
s->pending_out = s->pending_buf;
}
}
/* ========================================================================= */
int
int flush;
{
deflate_state *s;
return (Z_STREAM_ERROR);
}
if (/* strm->next_out == Z_NULL || --- we allow null --- PPP */
}
old_flush = s->last_flush;
s->last_flush = flush;
/* Write the zlib header */
if (s->status == INIT_STATE) {
s->status = BUSY_STATE;
putShortMSB(s, header);
/* Save the adler32 of the preset dictionary: */
if (s->strstart != 0) {
}
}
/* Flush as much pending output as possible */
if (s->pending != 0) {
/*
* Since avail_out is 0, deflate will be
* called again with more output space, but
* possibly with both pending and avail_in
* equal to zero. There won't be anything to
* do, but this is not an error situation so
* make sure we return OK instead of BUF_ERROR
* at next call of deflate:
*/
s->last_flush = -1;
return (Z_OK);
}
/*
* Make sure there is something to do and avoid
* duplicate consecutive flushes. For repeated and
* useless calls with Z_FINISH, we keep returning
* Z_STREAM_END instead of Z_BUFF_ERROR.
*/
}
/* User must not provide more input after the first FINISH: */
}
/* Start a new block or continue the current one. */
s->status = FINISH_STATE;
}
/* avoid BUF_ERROR next call, see above */
s->last_flush = -1;
}
return (Z_OK);
/*
* If flush != Z_NO_FLUSH && avail_out == 0,
* the next call of deflate should use the
* same flush parameter to make sure that the
* flush is complete. So we don't have to
* output an empty block here, this will be
* done at next call. This also ensures that
* for a very small output buffer, we emit at
* most one empty block.
*/
}
if (bstate == block_done) {
if (flush == Z_PARTIAL_FLUSH) {
_tr_align(s);
/*
* Output just the 3-bit `stored'
* block type value, but not a zero
* length. Added for PPP.
*/
_tr_stored_type_only(s); /* PPP */
} else { /* FULL_FLUSH or SYNC_FLUSH */
_tr_stored_block(s, (char *)0, 0L, 0);
/*
* For a full flush, this empty block
* will be recognized as a special
* marker by inflate_sync().
*/
if (flush == Z_FULL_FLUSH) {
CLEAR_HASH(s); /* forget history */
}
}
/* avoid BUF_ERROR at next call, see above */
s->last_flush = -1;
return (Z_OK);
}
}
}
return (Z_OK);
if (s->noheader)
return (Z_STREAM_END);
/* Write the zlib trailer (adler32) */
/*
* If avail_out is zero, the application will call deflate
* again to flush the rest.
*/
}
/* ========================================================================= */
int
{
int status;
deflate_state *s;
return (Z_STREAM_ERROR);
status != FINISH_STATE) {
return (Z_STREAM_ERROR);
}
/* Deallocate in reverse order of allocations: */
}
/*
* =========================================================================
* Copy the source state to the destination state.
* To simplify the source, this is not supported for 16-bit MSDOS (which
* doesn't have enough memory anyway to duplicate compression states).
*/
int
{
#ifdef MAXSEG_64K
return (Z_STREAM_ERROR);
#else
return (Z_STREAM_ERROR);
return (Z_MEM_ERROR);
(void) deflateEnd(dest);
return (Z_MEM_ERROR);
}
/* following zmemcpy doesn't work for 16-bit MSDOS */
return (Z_OK);
#endif
}
/*
* ===========================================================================
* Return the number of bytes of output which are immediately available
* for output from the decompressor. ---PPP---
*/
int
{
return (0);
}
/*
* ===========================================================================
* Read a new buffer from the current input stream, update the adler32
* and total number of bytes read. All deflate() input goes through
* this function so some applications may wish to modify it to avoid
* allocating a large strm->next_in buffer and copying from it.
* (See also flush_pending()).
*/
local int
unsigned size;
{
if (len == 0)
return (0);
}
return ((int)len);
}
/*
* ===========================================================================
* Initialize the "longest match" routines for a new zlib stream
*/
local void
lm_init(s)
deflate_state *s;
{
CLEAR_HASH(s);
/* Set the default configuration parameters: */
s->strstart = 0;
s->block_start = 0L;
s->lookahead = 0;
s->match_available = 0;
s->ins_h = 0;
#ifdef ASMV
match_init(); /* initialize the asm code */
#endif
}
/*
* ===========================================================================
* Set match_start to the longest match starting at the given string and
* return its length. Matches shorter or equal to prev_length are discarded,
* in which case the result is equal to prev_length and match_start is
* garbage.
* IN assertions: cur_match is the head of the hash chain for the current
* string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
* OUT assertion: the match length is not greater than s->lookahead.
*/
#ifndef ASMV
/*
* For 80x86 and 680x0, an optimized version will be provided in
* match.asm or match.S. The code will be functionally equivalent.
*/
#ifndef FASTEST
deflate_state *s;
{
/* max hash chain length */
/*
* Stop when cur_match becomes <= limit. To simplify the code,
* we prevent matches with the string of window index 0.
*/
#ifdef UNALIGNED_OK
/*
* Compare two bytes at a time. Note: this is not always
* beneficial. Try with and without -DUNALIGNED_OK to check.
*/
#else
#endif
/*
* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2
* multiple of 16. It is easy to get rid of this optimization
* if necessary.
*/
/* Do not waste too much time if we already have a good match: */
if (s->prev_length >= s->good_match) {
chain_length >>= 2;
}
/*
* Do not look for matches beyond the end of the input. This
* is necessary to make deflate deterministic.
*/
"need lookahead");
do {
/*
* Skip to next match if the match length cannot
* increase or if the match length is less than 2:
*/
/*
* This code assumes sizeof (unsigned short) == 2. Do
* not use UNALIGNED_OK if your compiler uses a
* different size.
*/
/*
* It is not necessary to compare scan[2] and match[2]
* since they are always equal when the other bytes
* match, given that the hash keys are equal and that
* HASH_BITS >= 8. Compare 2 bytes at a time at
* strstart+3, +5, ... up to strstart+257. We check
* for insufficient lookahead only every 4th
* comparison; the 128th check will be made at
* strstart+257. If MAX_MATCH-2 is not a multiple of
* 8, it is necessary to put more guard bytes at the
* end of the window, or to check more often for
* insufficient lookahead.
*/
do {
/* The funny "do {}" generates better code on most compilers */
/* Here, scan <= window+strstart+257 */
"wild scan");
#else /* UNALIGNED_OK */
continue;
/*
* The check at best_len-1 can be removed because it
* will be made again later. (This heuristic is not
* always a win.) It is not necessary to compare
* scan[2] and match[2] since they are always equal
* when the other bytes match, given that the hash
* keys are equal and that HASH_BITS >= 8.
*/
/*
* We check for insufficient lookahead only every 8th
* comparison; the 256th check will be made at
* strstart+258.
*/
do {
"wild scan");
#endif /* UNALIGNED_OK */
s->match_start = cur_match;
if (len >= nice_match) break;
#ifdef UNALIGNED_OK
#else
#endif
}
--chain_length != 0);
return (best_len);
return (s->lookahead);
}
#else /* FASTEST */
/*
* ---------------------------------------------------------------------------
* Optimized version for level == 1 only
*/
deflate_state *s;
{
/*
* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2
* multiple of 16. It is easy to get rid of this optimization
* if necessary.
*/
"need lookahead");
/* Return failure if the match length is less than 2: */
return (MIN_MATCH-1);
/*
* The check at best_len-1 can be removed because it will be
* made again later. (This heuristic is not always a win.) It
* is not necessary to compare scan[2] and match[2] since they
* are always equal when the other bytes match, given that the
* hash keys are equal and that HASH_BITS >= 8.
*/
/*
* We check for insufficient lookahead only every 8th comparison;
* the 256th check will be made at strstart+258.
*/
do {
return (MIN_MATCH - 1);
s->match_start = cur_match;
}
#endif /* FASTEST */
#endif /* ASMV */
#ifdef DEBUG_ZLIB
/*
* ===========================================================================
* Check that the match at match_start is indeed a match.
*/
local void
deflate_state *s;
int length;
{
/* check that the match is indeed a match */
do {
} while (--length != 0);
z_error("invalid match");
}
if (z_verbose > 1) {
}
}
#else
#endif
/*
* ===========================================================================
* Fill the window when the lookahead becomes insufficient.
* Updates strstart and lookahead.
*
* IN assertion: lookahead < MIN_LOOKAHEAD
* OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
* At least one byte has been read, or avail_in == 0; reads are
* performed for at least two bytes (required for the zip translate_eol
* option -- not supported here).
*/
local void
fill_window(s)
deflate_state *s;
{
register unsigned n, m;
register Posf *p;
do {
/* Deal with !@#$% 64K limit: */
} else if (more == (unsigned)(-1)) {
/*
* Very unlikely, but possible on 16 bit
* machine if strstart == 0 and lookahead == 1
* (input done one byte at time)
*/
more--;
/*
* If the window is almost full and there is
* insufficient lookahead, move the upper half
* to the lower one to make room in the upper
* half.
*/
s->match_start -= wsize;
/* we now have strstart >= MAX_DIST */
s->block_start -= (long)wsize;
/*
* Slide the hash table (could be avoided with
* 32 bit values at the expense of memory
* usage). We slide even when level == 0 to
* keep the hash table consistent if we switch
* back to level > 0 later. (Using level 0
* permanently is not an optimal usage of
* zlib, so we don't care about this
* pathological case.)
*/
n = s->hash_size;
p = &s->head[n];
do {
m = *--p;
} while (--n);
n = wsize;
#ifndef FASTEST
p = &s->prev[n];
do {
m = *--p;
/*
* If n is not on any hash chain,
* prev[n] is garbage but its value
* will never be used.
*/
} while (--n);
#endif
}
return;
/*
* If there was no sliding:
* strstart <= WSIZE+MAX_DIST-1 &&
* lookahead <= MIN_LOOKAHEAD - 1 &&
* more == window_size - lookahead - strstart
* => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE +
* MAX_DIST-1)
* => more >= window_size - 2*WSIZE + 2
* In the BIG_MEM or MMAP case (not yet supported),
* window_size == input_size + MIN_LOOKAHEAD &&
* strstart + s->lookahead <= input_size =>
* more >= MIN_LOOKAHEAD.
* Otherwise, window_size == 2*WSIZE so more >= 2.
* If there was sliding, more >= WSIZE. So in all cases,
* more >= 2.
*/
"read too much");
more);
s->lookahead += n;
/* Initialize the hash value now that we have some input: */
#if MIN_MATCH != 3
#endif
}
/*
* If the whole input has less than MIN_MATCH bytes,
* ins_h is garbage, but this is not important since
* only literal bytes will be emitted.
*/
}
/*
* ===========================================================================
* Flush the current block, with given end-of-file flag.
* IN assertion: strstart is set to the end of the current match.
*/
_tr_flush_block(s, (s->block_start >= 0L ? \
(eof)); \
s->block_start = s->strstart; \
flush_pending(s->strm); \
}
/* Same but force premature exit if necessary. */
FLUSH_BLOCK_ONLY(s, eof); \
}
/*
* ===========================================================================
* Copy without compression as much as possible from the input stream, return
* the current block state.
* This function does not insert new strings in the dictionary since
* uncompressible data is probably not useful. This function is used
* only for the level=0 compression option.
* NOTE: this function should be optimized to avoid extra copying from
* window to pending_buf.
*/
deflate_state *s;
int flush;
{
/*
* Stored blocks are limited to 0xffff bytes, pending_buf is
* limited to pending_buf_size, and each stored block has a 5
* byte header:
*/
}
/* Copy as much as possible from input to output: */
for (;;) {
/* Fill the window as much as possible: */
if (s->lookahead <= 1) {
s->block_start >= (long)s->w_size,
"slide too late");
fill_window(s);
return (need_more);
if (s->lookahead == 0)
break; /* flush the current block */
}
s->lookahead = 0;
/* Emit a stored block if pending_buf will be full: */
/*
* strstart == 0 is possible when wraparound
* on 16-bit machine
*/
FLUSH_BLOCK(s, 0);
}
/*
* Flush if we may have to slide, otherwise
* block_start may become negative and the data will
* be gone:
*/
FLUSH_BLOCK(s, 0);
}
}
}
/*
* ===========================================================================
* Compress as much as possible from the input stream, return the current
* block state.
* This function does not perform lazy evaluation of matches and inserts
* new strings in the dictionary only for unmatched strings or for short
* matches. It is used only for the fast compression options.
*/
deflate_state *s;
int flush;
{
for (;;) {
/*
* Make sure that we always have enough lookahead,
* except at the end of the input file. We need
* MAX_MATCH bytes for the next match, plus MIN_MATCH
* bytes to insert the string following the next
* match.
*/
if (s->lookahead < MIN_LOOKAHEAD) {
fill_window(s);
if (s->lookahead < MIN_LOOKAHEAD &&
flush == Z_NO_FLUSH) {
return (need_more);
}
if (s->lookahead == 0)
break; /* flush the current block */
}
/*
* Insert the string window[strstart .. strstart+2] in
* the dictionary, and set hash_head to the head of
* the hash chain:
*/
}
/*
* Find the longest match, discarding those <=
* prev_length. At this point we have always
* match_length < MIN_MATCH
*/
MAX_DIST(s)) {
/*
* To simplify the code, we prevent matches
* with the string of window index 0 (in
* particular we have to avoid a match of the
* string with itself at the start of the
* input file).
*/
if (s->strategy != Z_HUFFMAN_ONLY) {
}
/* longest_match() sets match_start */
}
if (s->match_length >= MIN_MATCH) {
s->match_length);
s->lookahead -= s->match_length;
/*
* Insert new strings in the hash table only
* if the match length is not too large. This
* saves time but degrades compression.
*/
#ifndef FASTEST
if (s->match_length <= s->max_insert_length &&
/* string at strstart already in hash table */
s->match_length--;
do {
s->strstart++;
INSERT_STRING(s, s->strstart,
/*
* strstart never exceeds
* WSIZE-MAX_MATCH, so there
* are always MIN_MATCH bytes
* ahead.
*/
} while (--s->match_length != 0);
s->strstart++;
} else
#endif
{
s->strstart += s->match_length;
s->match_length = 0;
UPDATE_HASH(s, s->ins_h,
#if MIN_MATCH != 3
#endif
/*
* If lookahead < MIN_MATCH, ins_h is
* garbage, but it does not matter
* since it will be recomputed at next
* deflate call.
*/
}
} else {
/* No match, output a literal byte */
s->lookahead--;
s->strstart++;
}
if (bflush) FLUSH_BLOCK(s, 0);
}
}
/*
* ===========================================================================
* Same as above, but achieves better compression. We use a lazy
* evaluation for matches: a match is finally adopted only if there is
* no better match at the next window position.
*/
deflate_state *s;
int flush;
{
/* Process the input block. */
for (;;) {
/*
* Make sure that we always have enough lookahead,
* except at the end of the input file. We need
* MAX_MATCH bytes for the next match, plus MIN_MATCH
* bytes to insert the string following the next
* match.
*/
if (s->lookahead < MIN_LOOKAHEAD) {
fill_window(s);
if (s->lookahead < MIN_LOOKAHEAD &&
flush == Z_NO_FLUSH) {
return (need_more);
}
/* flush the current block */
if (s->lookahead == 0)
break;
}
/*
* Insert the string window[strstart .. strstart+2] in
* the dictionary, and set hash_head to the head of
* the hash chain:
*/
}
/*
* Find the longest match, discarding those <=
* prev_length.
*/
s->prev_length = s->match_length;
s->prev_match = s->match_start;
/*
* To simplify the code, we prevent matches
* with the string of window index 0 (in
* particular we have to avoid a match of the
* string with itself at the start of the
* input file).
*/
if (s->strategy != Z_HUFFMAN_ONLY) {
}
/* longest_match() sets match_start */
if (s->match_length <= 5 &&
(s->strategy == Z_FILTERED ||
(s->match_length == MIN_MATCH &&
/*
* If prev_match is also MIN_MATCH,
* match_start is garbage but we will
* ignore the current match anyway.
*/
}
}
/*
* If there was a match at the previous step and the
* current match is not better, output the previous
* match:
*/
if (s->prev_length >= MIN_MATCH &&
s->match_length <= s->prev_length) {
/* Do not insert strings in hash table beyond this. */
s->prev_length);
/*
* Insert in hash table all strings up to the
* end of the match. strstart-1 and strstart
* are already inserted. If there is not
* enough lookahead, the last two strings are
* not inserted in the hash table.
*/
s->prev_length -= 2;
do {
if (++s->strstart <= max_insert) {
INSERT_STRING(s, s->strstart,
}
} while (--s->prev_length != 0);
s->match_available = 0;
s->strstart++;
if (bflush) FLUSH_BLOCK(s, 0);
} else if (s->match_available) {
/*
* If there was no match at the previous
* position, output a single literal. If there
* was a match but the current match is
* longer, truncate the previous match to a
* single literal.
*/
if (bflush) {
FLUSH_BLOCK_ONLY(s, 0);
}
s->strstart++;
s->lookahead--;
return (need_more);
} else {
/*
* There is no previous match to compare with,
* wait for the next step to decide.
*/
s->match_available = 1;
s->strstart++;
s->lookahead--;
}
}
if (s->match_available) {
s->match_available = 0;
}
}
/* --- deflate.c */
/* +++ trees.c */
/*
* trees.c -- output deflated data using Huffman coding
* Copyright (C) 1995-1998 Jean-loup Gailly
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/*
* ALGORITHM
*
* The "deflation" process uses several Huffman trees. The more
* common source values are represented by shorter bit sequences.
*
* Each code tree is stored in a compressed form which is itself
* a Huffman encoding of the lengths of all the code strings (in
* ascending order by source values). The actual code strings are
* reconstructed from the lengths in the inflate process, as described
* in the deflate specification.
*
* REFERENCES
*
* Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
* Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
*
* Storer, James A.
* Data Compression: Methods and Theory, pp. 49-50.
* Computer Science Press, 1988. ISBN 0-7167-8156-5.
*
* Sedgewick, R.
* Algorithms, p290.
* Addison-Wesley, 1983. ISBN 0-201-06672-6.
*/
/* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */
/* #include "deflate.h" */
#ifdef DEBUG_ZLIB
#include <ctype.h>
#endif
/*
* ===========================================================================
* Constants
*/
/* Bit length codes must not exceed MAX_BL_BITS bits */
/* end of block literal code */
/* repeat previous bit length 3-6 times (2 bits of repeat count) */
/* repeat a zero length 3-10 times (3 bits of repeat count) */
/* repeat a zero length 11-138 times (7 bits of repeat count) */
/* extra bits for each length code */
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};
/* extra bits for each distance code */
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};
/* extra bits for each bit length code */
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7};
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
/*
* The lengths of the bit length codes are sent in order of decreasing
* probability, to avoid transmitting the lengths for unused bit
* length codes.
*/
/*
* Number of bits used within bi_buf. (bi_buf might be implemented on
* more than 16 bits on some systems.)
*/
/*
* ===========================================================================
* Local data. These are initialized only once.
*/
/*
* The static literal tree. Since the bit lengths are imposed, there
* is no need for the L_CODES extra codes used during heap
* construction. However The codes 286 and 287 are needed to build a
* canonical tree (see _tr_init below).
*/
/*
* The static distance tree. (Actually a trivial tree since all codes
* use 5 bits.)
*/
/*
* distance codes. The first 256 values correspond to the distances 3
* .. 258, the last 256 values correspond to the top 8 bits of the 15
* bit distances.
*/
/* length code for each normalized match length (0 == MIN_MATCH) */
/* First normalized length for each code (0 = MIN_MATCH) */
/* First normalized distance for each code (0 = distance of 1) */
struct static_tree_desc_s {
};
/*
* ===========================================================================
* Local (static) routines in this file.
*/
int blcodes));
int header));
#ifndef DEBUG_ZLIB
/* Send a code of the given tree. c and tree must not have side effects */
#else /* DEBUG_ZLIB */
#endif
/*
* ===========================================================================
* Output a short LSB first on the stream.
* IN assertion: there is enough room in pendingBuf.
*/
#define put_short(s, w) { \
}
/*
* ===========================================================================
* Send a value on a given number of bits.
* IN assertion: length <= 16 and value fits in length bits.
*/
#ifdef DEBUG_ZLIB
local void
deflate_state *s;
int value; /* value to send */
int length; /* number of bits */
{
/*
* If not enough room in bi_buf, use (valid) bits from bi_buf
* and (16 - bi_valid) bits from value, leaving (width -
* (16-bi_valid)) unused bits in value.
*/
} else {
}
}
#else /* !DEBUG_ZLIB */
} else {\
}\
}
#endif /* DEBUG_ZLIB */
#define MAX(a, b) (a >= b ? a : b)
/* the arguments must not have side effects */
/*
* ===========================================================================
* Initialize the various 'constant' tables. In a multi-threaded environment,
* this function may be called by two threads concurrently, but this is
* harmless since both invocations do exactly the same thing.
*/
local void
{
static int static_init_done = 0;
int n; /* iterates over tree elements */
/* number of codes at each bit length for an optimal tree */
if (static_init_done)
return;
/* For some embedded targets, global variables are not initialized: */
/* Initialize the mapping length (0..255) -> length code (0..28) */
length = 0;
}
}
/*
* Note that the length 255 (match length 258) can be
* represented in two different ways: code 284 + 5 bits or
* code 285, so we overwrite _length_code[255] to use the best
* encoding:
*/
/* Initialize the mapping dist (0..32K) -> dist code (0..29) */
dist = 0;
}
}
}
}
/* Construct the codes of the static literal tree */
n = 0;
/*
* Codes 286 and 287 do not exist, but we must include them in the
* tree construction to get a canonical Huffman tree (longest code
* all ones)
*/
/* The static distance tree is trivial: */
for (n = 0; n < D_CODES; n++) {
}
static_init_done = 1;
}
/*
* ===========================================================================
* Initialize the tree data structures for a new zlib stream.
*/
void
_tr_init(s)
deflate_state *s;
{
s->bi_buf = 0;
s->bi_valid = 0;
s->compressed_len = 0L; /* PPP */
#ifdef DEBUG_ZLIB
s->bits_sent = 0L;
#endif
/* Initialize the first block of the first file: */
init_block(s);
}
/*
* ===========================================================================
* Initialize a new block.
*/
local void
init_block(s)
deflate_state *s;
{
int n; /* iterates over tree elements */
/* Initialize the trees. */
s->opt_len = s->static_len = 0L;
}
/* Index within the heap array of least frequent node in the Huffman tree */
/*
* ===========================================================================
* Remove the smallest element from the heap and recreate the heap with
* one less element. Updates heap and heap_len.
*/
{\
}
/*
* ===========================================================================
* Compares to subtrees, using the tree depth as tie breaker when
* the subtrees have equal frequency. This minimizes the worst case length.
*/
/*
* ===========================================================================
* Restore the heap property by moving down the tree starting at node k,
* exchanging a node with the smallest of its two sons if necessary, stopping
* when the heap property is re-established (each father smaller than its
* two sons).
*/
local void
deflate_state *s;
int k; /* node to move down */
{
int v = s->heap[k];
int j = k << 1; /* left son of k */
while (j <= s->heap_len) {
/* Set j to the smallest of the two sons: */
if (j < s->heap_len &&
j++;
}
/* Exit if v is smaller than both sons */
/* Exchange v with the smallest son */
/* And continue down the tree, setting j to the left son of k */
j <<= 1;
}
s->heap[k] = v;
}
/*
* ===========================================================================
* Compute the optimal bit lengths for a tree and update the total bit length
* for the current block.
* IN assertion: the fields freq and dad are set, heap[heap_max] and
* above are the tree nodes sorted by increasing frequency.
* OUT assertions: the field len is set to the optimal bit length, the
* array bl_count contains the frequencies for each bit length.
* The length opt_len is updated; static_len is also updated if stree is
* not null.
*/
local void
deflate_state *s;
{
int h; /* heap index */
int n, m; /* iterate over the tree elements */
ush f; /* frequency */
/* number of elements with bit length too large */
int overflow = 0;
/*
* In a first pass, compute the optimal bit lengths (which may
* overflow in the case of the bit length tree).
*/
n = s->heap[h];
/* We overwrite tree[n].Dad which is no longer needed */
if (n > max_code) continue; /* not a leaf node */
xbits = 0;
}
if (overflow == 0)
return;
/* This happens for example on obj2 and pic of the Calgary corpus */
/* Find the first bit length which could increase: */
do {
/* move one overflow item as its brother */
s->bl_count[max_length]--;
/*
* The brother of the overflow item also moves one
* step up, but this does not affect
* bl_count[max_length]
*/
overflow -= 2;
} while (overflow > 0);
/*
* Now recompute all bit lengths, scanning in increasing
* frequency. h is still equal to HEAP_SIZE. (It is simpler
* to reconstruct all lengths instead of fixing only the wrong
* ones. This idea is taken from 'ar' written by Haruhiko
* Okumura.)
*/
while (n != 0) {
m = s->heap[--h];
if (m > max_code) continue;
}
n--;
}
}
}
/*
* ===========================================================================
* Generate the codes for a given tree and bit counts (which need not be
* optimal).
* IN assertion: the array bl_count contains the bit length statistics for
* the given tree and the field len is set for all tree elements.
* OUT assertion: the field code is set for all tree elements of non
* zero code length.
*/
local void
int max_code; /* largest code with non zero frequency */
{
/* next code value for each bit length */
int n; /* code index */
/*
* The distribution counts are first used to generate the code
* values without bit reversal.
*/
}
/*
* Check that the bit counts in bl_count are consistent. The
* last code must be all ones.
*/
"inconsistent bit counts");
for (n = 0; n <= max_code; n++) {
if (len == 0) continue;
/* Now reverse the bits */
(stderr, "\nn %3d %c l %2d c %4x (%x) ",
}
}
/*
* ===========================================================================
* Construct one Huffman tree and assigns the code bit strings and lengths.
* Update the total bit length for the current block.
* IN assertion: the field freq is set for all tree elements.
* OUT assertions: the fields len and code are set to the optimal bit length
* and corresponding code. The length opt_len is updated; static_len is
* also updated if stree is not null. The field max_code is set.
*/
local void
deflate_state *s;
{
int n, m; /* iterate over heap elements */
/*
* Construct the initial heap, with least frequent element in
* heap[SMALLEST]. The sons of heap[n] are heap[2*n] and
* heap[2*n+1]. heap[0] is not used.
*/
for (n = 0; n < elems; n++) {
s->depth[n] = 0;
} else {
}
}
/*
* The pkzip format requires that at least one distance code
* exists, and that at least one bit should be sent even if
* there is only one possible code. So to avoid special checks
* later on we force at least two codes of non zero frequency.
*/
while (s->heap_len < 2) {
++max_code : 0);
/* node is 0 or 1 so it does not have extra bits */
}
/*
* The elements heap[heap_len/2+1 .. heap_len] are leaves of
* the tree, establish sub-heaps of increasing lengths:
*/
/*
* Construct the Huffman tree by repeatedly combining the
* least two frequent nodes.
*/
do {
/* keep the nodes sorted by frequency */
/* Create a new node father of n and m */
#ifdef DUMP_BL_TREE
}
#endif
/* and insert the new node in the heap */
} while (s->heap_len >= 2);
/*
* At this point, the fields freq and dad are set. We can now
* generate the bit lengths.
*/
/* The field len is now set, we can generate the bit codes */
}
/*
* ===========================================================================
* Scan a literal or distance tree to determine the frequencies of the codes
* in the bit length tree.
*/
local void
deflate_state *s;
int max_code; /* and its largest code of non zero frequency */
{
int n; /* iterates over all tree elements */
for (n = 0; n <= max_code; n++) {
continue;
} else if (curlen != 0) {
} else if (count <= 10) {
} else {
}
if (nextlen == 0) {
} else {
}
}
}
/*
* ===========================================================================
* Send a literal or distance tree in compressed form, using the codes in
* bl_tree.
*/
local void
deflate_state *s;
int max_code; /* and its largest code of non zero frequency */
{
int n; /* iterates over all tree elements */
/* tree[max_code+1].Len = -1; */ /* guard already set */
for (n = 0; n <= max_code; n++) {
continue;
while (--count != 0);
} else if (curlen != 0) {
}
} else if (count <= 10) {
} else {
}
if (nextlen == 0) {
} else {
}
}
}
/*
* ===========================================================================
* Construct the Huffman tree for the bit lengths and return the index in
* bl_order of the last bit length code to send.
*/
local int
deflate_state *s;
{
/* index of last bit length code of non zero freq */
int max_blindex;
/*
* Determine the bit length frequencies for literal and
* distance trees
*/
/* Build the bit length tree: */
/*
* opt_len now includes the length of the tree
* representations, except the lengths of the bit lengths
* codes and the 5+5+4 bits for the counts.
*/
/*
* Determine the number of bit length codes to send. The pkzip
* format requires that at least 4 bit length codes be
* sent. (appnote.txt says 3 but the actual value used is 4.)
*/
}
/* Update opt_len to include the bit length tree and counts */
s->opt_len, s->static_len));
return (max_blindex);
}
/*
* ===========================================================================
* Send the header for a block using dynamic Huffman trees: the counts, the
* lengths of the bit length codes, the literal tree and the distance tree.
* IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
*/
local void
deflate_state *s;
{
"not enough codes");
"too many codes");
}
#ifdef DEBUG_ZLIB
#endif
/* literal tree */
#ifdef DEBUG_ZLIB
#endif
/* distance tree */
#ifdef DEBUG_ZLIB
#endif
}
/*
* ===========================================================================
* Send a stored block
*/
void
deflate_state *s;
int eof; /* true if this is the last block for a file */
{
}
/*
* Send just the `stored block' type code without any length bytes or data.
* ---PPP---
*/
void
deflate_state *s;
{
bi_windup(s);
}
/*
* ===========================================================================
* Send one empty static block to give enough lookahead for inflate.
* This takes 10 bits, of which 7 may remain in the bit buffer.
* The current inflate code requires 9 bits of lookahead. If the
* last two codes for the previous block (real code plus EOB) were coded
* on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
* the last real code. In this case we send two empty static blocks instead
* of one. (There are no problems if the previous block is stored or fixed.)
* To simplify the code, we assume the worst case of last real code encoded
* on one bit only.
*/
void
_tr_align(s)
deflate_state *s;
{
bi_flush(s);
/*
* Of the 10 bits for the empty block, we have already sent
* (10 - bi_valid) bits. The lookahead for the last real code
* (before the EOB of the previous block) was thus at least
* one plus the length of the EOB plus what we have just sent
* of the empty static block.
*/
s->compressed_len += 10L;
bi_flush(s);
}
s->last_eob_len = 7;
}
/*
* ===========================================================================
* Determine the best encoding for the current block: dynamic trees, static
* trees or store, and output the encoded block to the zip file.
*/
void
deflate_state *s;
int eof; /* true if this is the last block for a file */
{
/* index of last bit length code of non zero freq */
int max_blindex = 0;
/* Build the Huffman trees unless a stored block is forced */
if (s->level > 0) {
/* Check if the file is ascii or binary */
/* Construct the literal and distance trees */
s->static_len));
s->static_len));
/*
* At this point, opt_len and static_len are the total
* bit lengths of the compressed block data, excluding
* the tree representations.
*/
/*
* Build the bit length tree for the above two trees,
* and get the index in bl_order of the last bit
* length code to send.
*/
max_blindex = build_bl_tree(s);
/*
* Determine the best encoding. Compute first the
* block length in bytes
*/
"\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
stored_len, s->last_lit));
} else {
/* force a stored block */
}
/*
* If compression failed and this is the first and last block,
* and if the .zip file can be seeked (to rewrite the local
* header), the whole file is transformed into a stored file:
*/
#ifdef STORED_FILE_OK
#ifdef FORCE_STORED_FILE
#else
s->compressed_len == 0L && seekable()
#endif
if (FRC_STR_COND) {
/*
* Since LIT_BUFSIZE <= 2*WSIZE, the input data must
* be there:
*/
/* without header */
} else
#endif /* STORED_FILE_OK */
#ifdef FORCE_STORED
#else
/* 4: two words for the lengths */
#endif
if (FRC_STR_COND) {
/*
* The test buf != NULL is only necessary if
* LIT_BUFSIZE > WSIZE. Otherwise we can't
* have processed more than WSIZE input bytes
* since the last block flush, because
* compression would have been successful. If
* LIT_BUFSIZE <= WSIZE, it is never too late
* to transform a block into a stored block.
*/
#ifdef FORCE_STATIC
#else
#endif
} else if (FRC_STAT_COND) {
(ct_data *)static_dtree);
} else {
max_blindex+1);
}
#ifdef DEBUG_ZLIB
#endif
/*
* The above check is made mod 2^32, for files larger than 512
* MB and uLong implemented on 32 bits.
*/
init_block(s);
if (eof) {
bi_windup(s);
}
/* return (s->compressed_len >> 3); */
}
/*
* ===========================================================================
* Save the match info and tally the frequency counts. Return true if
* the current block must be flushed.
*/
int
deflate_state *s;
unsigned dist; /* distance of matched string */
/* match length-MIN_MATCH or unmatched char (if dist==0) */
unsigned lc;
{
if (dist == 0) {
/* lc is the unmatched char */
} else {
s->matches++;
/* Here, lc is the match length - MIN_MATCH */
dist--; /* dist = match distance - 1 */
}
#ifdef TRUNCATE_BLOCK
/* Try to guess if it is profitable to stop the current block here */
/* Compute an upper bound for the compressed length */
int dcode;
}
out_length >>= 3;
return (1);
}
#endif
/*
* We avoid equality with lit_bufsize because of wraparound at 64K
* on 16 bit machines and because stored blocks are restricted to
* 64K-1 bytes.
*/
}
/*
* ===========================================================================
* Send the block data compressed using the given Huffman trees
*/
local void
deflate_state *s;
{
if (s->last_lit != 0) do {
if (dist == 0) {
/* send a literal byte */
} else {
/* Here, lc is the match length - MIN_MATCH */
/* send the length code */
if (extra != 0) {
/* send the extra length bits */
}
/* dist is now the match distance - 1 */
dist--;
/* send the distance code */
if (extra != 0) {
/* send the extra distance bits */
}
} /* literal or match pair ? */
/*
* Check that the overlay between pending_buf and
* d_buf+l_buf is ok:
*/
"pendingBuf overflow");
}
/*
* ===========================================================================
* Set the data type to ASCII or BINARY, using a crude approximation:
* binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
* IN assertion: the fields freq of dyn_ltree are set and the total of all
* frequencies does not exceed 64K (to fit in an int on 16 bit machines).
*/
local void
deflate_state *s;
{
int n = 0;
unsigned ascii_freq = 0;
unsigned bin_freq = 0;
}
/*
* ===========================================================================
* Reverse the first len bits of a code, using straightforward code (a faster
* method would use a table)
* IN assertion: 1 <= len <= 15
*/
local unsigned
unsigned code; /* the value to invert */
int len; /* its bit length */
{
register unsigned res = 0;
do {
} while (--len > 0);
return (res >> 1);
}
/*
* ===========================================================================
* Flush the bit buffer, keeping at most 7 bits in it.
*/
local void
bi_flush(s)
deflate_state *s;
{
if (s->bi_valid == 16) {
s->bi_buf = 0;
s->bi_valid = 0;
} else if (s->bi_valid >= 8) {
s->bi_buf >>= 8;
s->bi_valid -= 8;
}
}
/*
* ===========================================================================
* Flush the bit buffer and align the output on a byte boundary
*/
local void
bi_windup(s)
deflate_state *s;
{
if (s->bi_valid > 8) {
} else if (s->bi_valid > 0) {
}
s->bi_buf = 0;
s->bi_valid = 0;
#ifdef DEBUG_ZLIB
#endif
}
/*
* ===========================================================================
* Copy a stored block, storing first the length and its
* one's complement if requested.
*/
local void
deflate_state *s;
unsigned len; /* its length */
int header; /* true if block header must be written */
{
bi_windup(s); /* align on byte boundary */
if (header) {
#ifdef DEBUG_ZLIB
#endif
}
#ifdef DEBUG_ZLIB
#endif
/* bundle up the put_byte(s, *buf++) calls PPP */
}
/* --- trees.c */
/* +++ inflate.c */
/*
* inflate.c -- zlib interface to inflate modules
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/* #include "zutil.h" */
/* +++ infblock.h */
/*
* infblock.h -- header to use infblock.c
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/*
* WARNING: this file should *not* be used by applications. It is part
* of the implementation of the compression library and is subject to
* change. Applications should only use zlib.h.
*/
struct inflate_blocks_state;
z_streamp z,
check_func c, /* check function */
uInt w)); /* window size */
extern int inflate_blocks OF((
int)); /* initial return code */
extern void inflate_blocks_reset OF((
uLongf *)); /* check value on output */
extern int inflate_blocks_free OF((
z_streamp));
extern void inflate_set_dictionary OF((
const Bytef *d, /* dictionary */
uInt n)); /* dictionary length */
extern int inflate_blocks_sync_point OF((
inflate_blocks_statef *s));
/* PPP -- added function */
extern int inflate_addhistory OF((
z_streamp));
/* PPP -- added function */
extern int inflate_packet_flush OF((
/* --- infblock.h */
#ifndef NO_DUMMY_DECL
#endif
/* inflate private state */
struct internal_state {
/* mode */
enum {
/* mode dependent information */
union {
struct {
/* mode independent information */
/* current inflate_blocks state */
};
int
inflateReset(z)
z_streamp z;
{
return (Z_STREAM_ERROR);
return (Z_OK);
}
int
inflateEnd(z)
z_streamp z;
{
return (Z_STREAM_ERROR);
}
return (Z_OK);
}
int
z_streamp z;
int w;
const char *version;
int stream_size;
{
stream_size != sizeof (z_stream))
return (Z_VERSION_ERROR);
/* initialize state */
if (z == Z_NULL)
return (Z_STREAM_ERROR);
#ifndef NO_ZCFUNCS
{
}
#endif
return (Z_MEM_ERROR);
/* handle undocumented nowrap option (no zlib header or check) */
if (w < 0)
{
w = - w;
}
/* set window size */
if (w < 8 || w > 15)
{
(void) inflateEnd(z);
return (Z_STREAM_ERROR);
}
/* create inflate_blocks state */
== Z_NULL)
{
(void) inflateEnd(z);
return (Z_MEM_ERROR);
}
/* reset state */
(void) inflateReset(z);
return (Z_OK);
}
int
z_streamp z;
const char *version;
int stream_size;
{
}
/* PPP -- added "empty" label and changed f to Z_OK */
int
inflate(z, f)
z_streamp z;
int f;
{
int r;
uInt b;
return (Z_STREAM_ERROR);
/* f = f == Z_FINISH ? Z_BUF_ERROR : Z_OK; -- PPP; Z_FINISH unused */
r = Z_BUF_ERROR;
/* CONSTCOND */
while (1)
{
case METHOD:
{
z->msg = "unknown compression method";
/* can't try inflateSync */
break;
}
{
z->msg = "invalid window size";
/* can't try inflateSync */
break;
}
/* FALLTHRU */
case FLAG:
b = NEXTBYTE;
{
z->msg = "incorrect header check";
/* can't try inflateSync */
break;
}
if (!(b & PRESET_DICT))
{
break;
}
/* FALLTHRU */
case DICT4:
/* FALLTHRU */
case DICT3:
/* FALLTHRU */
case DICT2:
/* FALLTHRU */
case DICT1:
return (Z_NEED_DICT);
case DICT0:
z->msg = "need dictionary";
return (Z_STREAM_ERROR);
case BLOCKS:
z->avail_out != 0) /* PPP */
if (r == Z_DATA_ERROR)
{
/* can try inflateSync */
break;
}
/* PPP */
if (r != Z_STREAM_END)
return (r);
r = Z_OK; /* PPP */
{
break;
}
/* FALLTHRU */
case CHECK4:
/* FALLTHRU */
case CHECK3:
/* FALLTHRU */
case CHECK2:
/* FALLTHRU */
case CHECK1:
{
z->msg = "incorrect data check";
/* can't try inflateSync */
break;
}
/* FALLTHRU */
case DONE:
return (Z_STREAM_END);
case BAD:
return (Z_DATA_ERROR);
default:
return (Z_STREAM_ERROR);
}
/* PPP -- packet flush handling */
if (f != Z_PACKET_FLUSH)
return (r);
z->msg = "need more for packet flush";
return (Z_DATA_ERROR);
}
int
z_streamp z;
const Bytef *dictionary;
{
return (Z_STREAM_ERROR);
return (Z_DATA_ERROR);
z->adler = 1L;
{
}
return (Z_OK);
}
/*
* without performing any output. The output buffer must be "caught up";
* i.e. no pending output (hence s->read equals s->write), and the state must
* be BLOCKS (i.e. we should be willing to see the start of a series of
* BLOCKS). On exit, the output will also be caught up, and the checksum
* will have been updated if need be.
*
* Added for PPP.
*/
int
z_stream *z;
{
return (Z_DATA_ERROR);
}
int
inflateSync(z)
z_streamp z;
{
uInt n; /* number of bytes to look at */
Bytef *p; /* pointer to bytes */
uInt m; /* number of marker bytes found in a row */
uLong r, w; /* temporaries to save total_in and total_out */
/* set up */
return (Z_STREAM_ERROR);
{
}
if ((n = z->avail_in) == 0)
return (Z_BUF_ERROR);
p = z->next_in;
/* search */
while (n && m < 4)
{
if (*p == mark[m])
m++;
else if (*p)
m = 0;
else
/*
* This statement maps 2->2 and 3->1 because a
* mismatch with input byte 0x00 on the first
* 0xFF in the pattern means that we still
* have two contiguous zeros matched (thus
* offset 2 is kept), but a mismatch on the
* second 0xFF means that only one 0x00 byte
* has been matched. (Boyer-Moore like
* search.)
*/
m = 4 - m;
p++, n--;
}
/* restore */
z->next_in = p;
z->avail_in = n;
/* return no joy or set up to restart on a new block */
if (m != 4)
return (Z_DATA_ERROR);
(void) inflateReset(z);
return (Z_OK);
}
/*
* Returns true if inflate is currently at the end of a block
* generated by Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by
* one PPP implementation to provide an additional safety check. PPP
* uses Z_SYNC_FLUSH but removes the length bytes of the resulting
* empty stored block. When decompressing, PPP checks that at the end
* of input packet, inflate is waiting for these length bytes.
*/
int
z_streamp z;
{
return (Z_STREAM_ERROR);
}
/* --- inflate.c */
/* +++ infblock.c */
/*
* infblock.c -- interpret and process block types to last block
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/* #include "zutil.h" */
/* #include "infblock.h" */
/* +++ inftrees.h */
/*
* inftrees.h -- header to use inftrees.c
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/*
* WARNING: this file should *not* be used by applications. It is part
* of the implementation of the compression library and is subject to
* change. Applications should only use zlib.h.
*/
/*
* Huffman code lookup table entry--this entry is four bytes for
* machines that have 16-bit pointers (e.g. PC's in the small or
* medium model).
*/
struct inflate_huft_s {
union {
struct {
/* number of bits in this code or subcode */
} what;
/* literal, length base, distance base, or table offset */
};
/*
* Maximum size of dynamic tree. The maximum found in a long but non-
* and 154 for distances, the latter actually the result of an
* exhaustive search). The actual maximum is not known, but the value
* below is more than safe.
*/
extern int inflate_trees_bits OF((
uIntf *, /* 19 code lengths */
inflate_huft *, /* space for trees */
z_streamp)); /* for zalloc, zfree functions */
extern int inflate_trees_dynamic OF((
uInt, /* number of distance codes */
uIntf *, /* that many (total) code lengths */
inflate_huft *, /* space for trees */
z_streamp)); /* for zalloc, zfree functions */
extern int inflate_trees_fixed OF((
z_streamp));
/* --- inftrees.h */
/* +++ infcodes.h */
/*
* infcodes.h -- header to use infcodes.c
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/*
* WARNING: this file should *not* be used by applications. It is part
* of the implementation of the compression library and is subject to
* change. Applications should only use zlib.h.
*/
struct inflate_codes_state;
const inflate_huft *, const inflate_huft *,
z_streamp));
extern int inflate_codes OF((
int));
extern void inflate_codes_free OF((
z_streamp));
/* --- infcodes.h */
/* +++ infutil.h */
/*
* infutil.h -- types and macros common to blocks and codes
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/*
* WARNING: this file should *not* be used by applications. It is part
* of the implementation of the compression library and is subject to
* change. Applications should only use zlib.h.
*/
#ifndef _INFUTIL_H
#define _INFUTIL_H
typedef enum {
/* inflate blocks semi-private state */
struct inflate_blocks_state {
/* mode */
/* mode dependent information */
union {
struct {
struct {
/* mode independent information */
};
/* update pointers and return */
/* get bytes and bits */
#define NEXTBYTE (n--, *p++)
k += 8; }}
#define DUMPBITS(j) {b >>= (j); k -= (j); }
/* output bytes */
/* load local pointers */
/* masks for lower bits (size given to avoid silly warnings with Visual C++) */
/* copy as much as possible from the sliding window to the output area */
extern int inflate_flush OF((
int));
#ifndef NO_DUMMY_DECL
#endif
#endif
/* --- infutil.h */
#ifndef NO_DUMMY_DECL
#endif
/* Table for deflate from PKZIP's appnote.txt. */
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
/*
* Notes beyond the 1.93a appnote.txt:
*
* 1. Distance pointers never point before the beginning of the output
* stream.
* 2. Distance pointers can point back across blocks, up to 32k away.
* 3. There is an implied maximum of 7 bits for the bit length table and
* 15 bits for the actual data.
* 4. If only one code exists, then it is encoded using one bit. (Zero
* would be more efficient, but perhaps a little confusing.) If two
* codes exist, they are coded using one bit each (0 and 1).
* 5. There is no way of sending zero distance codes--a dummy must be
* sent if there are none. (History: a pre 2.0 version of PKZIP would
* store blocks with no distance codes, but this was discovered to be
* too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
* zero distance codes, which is sent as one code of zero bits in
* length.
* end-of-block. Note however that the static length tree defines
* 288 codes just to fill out the Huffman codes. Codes 286 and 287
* cannot be used though, since there is no length base or extra bits
* defined for them. Similarily, there are up to 30 distance codes.
* However, static trees define 32 codes (all 5 bits) to fill out the
* Huffman codes, but the last two had better not show up in the data.
* 7. Unzip can check dynamic Huffman blocks for complete code sets.
* The exception is that a single code would not be complete (see #4).
* 8. The five bits following the block type is really the number of
* literal codes sent minus 257.
* 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
* (1+6+6). Therefore, to output three times the length, you output
* three codes (1+1+1), whereas to output four times the same length,
* you only need two codes (1+3). Hmm.
* 10. In the tree reconstruction algorithm, Code = Code + Increment
* only if BitLength(i) is not zero. (Pretty obvious.)
* 11. Correction: 4 Bits: #of Bit Length codes - 4 (4 - 19)
* 12. Note: length code 284 can represent 227-258, but length code 285
* really is 258. The last length deserves its own, short code
* since it gets used a lot in very redundant files. The length
* 258 is special since 258 - 3 (the min match length) is 255.
* single stream of lengths. It is possible (and advantageous) for
* a repeat code (16, 17, or 18) to go across the boundary between
* the two sets of lengths.
*/
void
inflate_blocks_reset(s, z, c)
z_streamp z;
uLongf *c;
{
if (c != Z_NULL)
*c = s->check;
}
}
s->bitk = 0;
s->bitb = 0;
}
inflate_blocks_new(z, c, w)
z_streamp z;
check_func c;
uInt w;
{
if ((s = (inflate_blocks_statef *)ZALLOC
return (s);
ZFREE(z, s);
return (Z_NULL);
}
{
ZFREE(z, s);
return (Z_NULL);
}
s->checkfn = c;
inflate_blocks_reset(s, z, Z_NULL);
return (s);
}
int
inflate_blocks(s, z, r)
z_streamp z;
int r;
{
uInt t; /* temporary storage */
uLong b; /* bit buffer */
uInt k; /* bits in bit buffer */
Bytef *p; /* input data pointer */
uInt n; /* bytes available there */
Bytef *q; /* output window write pointer */
uInt m; /* bytes to end of window or read pointer */
LOAD;
/* process input based on current state */
/* CONSTCOND */
while (1)
switch (s->mode)
{
case TYPE:
NEEDBITS(3);
t = (uInt)b & 7;
s->last = t & 1;
switch (t >> 1)
{
case 0: /* stored */
DUMPBITS(3);
t = k & 7; /* go to byte boundary */
DUMPBITS(t);
break;
case 1: /* fixed */
{
z);
{
r = Z_MEM_ERROR;
}
}
DUMPBITS(3);
break;
case 2: /* dynamic */
DUMPBITS(3);
break;
case 3: /* illegal */
DUMPBITS(3);
z->msg = "invalid block type";
r = Z_DATA_ERROR;
}
break;
case LENS:
NEEDBITS(32);
if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
{
z->msg = "invalid stored block lengths";
r = Z_DATA_ERROR;
}
b = k = 0; /* dump bits */
break;
case STORED:
if (n == 0)
if (t > n) t = n;
if (t > m) t = m;
zmemcpy(q, p, t);
p += t; n -= t;
q += t; m -= t;
break;
"inflate: stored end, %lu total out\n",
break;
case TABLE:
NEEDBITS(14);
#ifndef PKZIP_BUG_WORKAROUND
if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
{
z->msg =
(char *)"too many length or distance symbols";
r = Z_DATA_ERROR;
}
#endif
t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
/* if (t < 19) t = 19; */
{
r = Z_MEM_ERROR;
}
DUMPBITS(14);
/* FALLTHRU */
case BTREE:
{
NEEDBITS(3);
(uInt)b & 7;
DUMPBITS(3);
}
0;
if (t != Z_OK)
{
r = t;
if (r == Z_DATA_ERROR)
}
/* FALLTHRU */
case DTREE:
((t >> 5) & 0x1f))
{
inflate_huft *h;
uInt i, j, c;
NEEDBITS(t);
c = h->base;
if (c < 16)
{
DUMPBITS(t);
c;
} else { /* c == 16..18 */
i = c == 18 ? 7 : c - 14;
j = c == 18 ? 11 : 3;
NEEDBITS(t + i);
DUMPBITS(t);
j += (uInt)b & inflate_mask[i];
DUMPBITS(i);
if (i + j > 258 + (t & 0x1f) +
((t >> 5) & 0x1f) ||
(c == 16 && i < 1))
{
z->msg = "invalid bit length repeat";
r = Z_DATA_ERROR;
}
do {
} while (--j);
}
}
{
/* must be <= 9 for lookahead assumptions */
bl = 9;
/* must be <= 9 for lookahead assumptions */
bd = 6;
1 + ((t >> 5) & 0x1f),
s->hufts, z);
if (t != Z_OK)
{
if (t == (uInt)Z_DATA_ERROR)
r = t;
}
{
r = Z_MEM_ERROR;
}
}
/* FALLTHRU */
case CODES:
if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
return (inflate_flush(s, z, r));
r = Z_OK;
LOAD;
if (!s->last)
{
break;
}
/* FALLTHRU */
case DRY:
/* FALLTHRU */
case DONEB:
r = Z_STREAM_END;
case BADB:
r = Z_DATA_ERROR;
default:
r = Z_STREAM_ERROR;
}
/* NOTREACHED */
/* otherwise lint complains */
}
int
inflate_blocks_free(s, z)
z_streamp z;
{
inflate_blocks_reset(s, z, Z_NULL);
ZFREE(z, s);
return (Z_OK);
}
void
inflate_set_dictionary(s, d, n)
const Bytef *d;
uInt n;
{
}
/*
* Returns true if inflate is currently at the end of a block
* generated by Z_SYNC_FLUSH or Z_FULL_FLUSH.
* IN assertion: s != Z_NULL
*/
int
{
}
/*
* without performing any output. The output buffer must be "caught up";
* i.e. no pending output (hence s->read equals s->write), and the state must
* be BLOCKS (i.e. we should be willing to see the start of a series of
* BLOCKS). On exit, the output will also be caught up, and the checksum
* will have been updated if need be.
*/
int
inflate_addhistory(s, z)
z_stream *z;
{
uInt t; /* temporary storage */
Bytef *p; /* input data pointer */
uInt n; /* bytes available there */
Bytef *q; /* output window write pointer */
uInt m; /* bytes to end of window or read pointer */
return (Z_STREAM_ERROR);
return (Z_DATA_ERROR);
/* we're ready to rock */
LOAD;
/*
* while there is input ready, copy to output buffer, moving
* pointers as needed.
*/
while (n) {
t = n; /* how many to do */
/* is there room until end of buffer? */
if (t > m) t = m;
/* update check information */
zmemcpy(q, p, t);
q += t;
p += t;
n -= t;
z->total_out += t;
s->read = q; /* drag read pointer forward */
/* WWRAP */ /* expand WWRAP macro by hand to handle s->read */
if (q == s->end) {
m = WAVAIL;
}
}
return (Z_OK);
}
/*
* At the end of a Deflate-compressed PPP packet, we expect to have seen
* a `stored' block type value but not the (zero) length bytes.
*/
int
{
return (Z_DATA_ERROR);
return (Z_OK);
}
/* --- infblock.c */
/* +++ inftrees.c */
/*
* inftrees.c -- generate Huffman trees for efficient decoding
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/* #include "zutil.h" */
/* #include "inftrees.h" */
const char inflate_copyright[] =
" inflate 1.1.3 Copyright 1995-1998 Mark Adler ";
/*
* If you use the zlib library in a product, an acknowledgment is
* welcome in the documentation of your product. If for some reason
* you cannot include such an acknowledgment, I would appreciate that
* you keep this copyright string in the executable of your product.
*/
#ifndef NO_DUMMY_DECL
#endif
/* simplify the use of the inflate_huft type with some defines */
uIntf *, /* code lengths in bits */
uInt, /* number of codes */
uInt, /* number of "simple" codes */
const uIntf *, /* list of base values for non-simple codes */
const uIntf *, /* list of extra bits for non-simple codes */
uIntf *, /* maximum lookup bits (returns actual) */
uIntf *v)); /* working area: values in order of bit length */
/* Tables for deflate from PKZIP's appnote.txt. */
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
/* see note #13 above about 258 */
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, 112, 112};
/* 112==invalid */
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
8193, 12289, 16385, 24577};
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};
/*
* Huffman code decoding is performed using a multi-level table
* lookup. The fastest way to decode is to simply build a lookup
* table whose size is determined by the longest code. However, the
* time it takes to build this table can also be a factor if the data
* being decoded is not very long. The most common codes are
* necessarily the shortest codes, so those codes dominate the
* decoding time, and hence the speed. The idea is you can have a
* shorter table that decodes the shorter, more probable codes, and
* then point to subsidiary tables for the longer codes. The time it
* costs to decode the longer codes is then traded against the time it
* takes to make longer tables.
*
* This results of this trade are in the variables lbits and dbits
* below. lbits is the number of bits the first level table for
* literal/ length codes can decode in one step, and dbits is the same
* thing for the distance codes. Subsequent tables are also less than
* or equal to those sizes. These values may be adjusted either when
* all of the codes are shorter than that, in which case the longest
* code length in bits is used, or when the shortest code is *longer*
* than the requested table size, in which case the length of the
* shortest code in bits is used.
*
* There are two different values for the two tables, since they code
* codes 286 possible values, or in a flat code, a little over eight
* bits. The distance table codes 30 possible values, or a little
* less than five bits, flat. The optimum values for speed end up
* being about one bit more than those, so lbits is 8+1 and dbits is
* 5+1. The optimum values may differ though from machine to machine,
* and possibly even between compilers. Your mileage may vary.
*/
/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
local int
uIntf *b; /* code lengths in bits (all assumed <= BMAX) */
uInt n; /* number of codes (assumed <= 288) */
uInt s; /* number of simple-valued codes (0..s-1) */
const uIntf *d; /* list of base values for non-simple codes */
const uIntf *e; /* list of extra bits for non-simple codes */
uIntf *m; /* maximum lookup bits, returns actual */
uIntf *v; /* working area: values in order of bit length */
/*
* Given a list of code lengths and a maximum table size, make a set
* of tables to decode that set of codes. Return Z_OK on success,
* Z_BUF_ERROR if the given code set is incomplete (the tables are
* still built in this case), Z_DATA_ERROR if the input is invalid (an
* over-subscribed set of lengths), or Z_MEM_ERROR if not enough
* memory.
*/
{
uInt a; /* counter for codes of length k */
uInt f; /* i repeats in table every f entries */
int g; /* maximum code length */
int h; /* table level */
register uInt i; /* counter, current code */
register uInt j; /* counter */
register int k; /* number of bits in current code */
int l; /* bits per table (returned in m) */
register uIntf *p; /* pointer into c[], b[], or v[] */
inflate_huft *q; /* points to current table */
struct inflate_huft_s r; /* table entry for structure assignment */
register int w; /* bits before this table == (l * h) */
int y; /* number of dummy codes added */
uInt z; /* number of entries in current table */
(void) inflate_copyright;
/* Generate counts for each bit length */
p = c;
#define C0 *p++ = 0;
C4 /* clear c[]--assume BMAX+1 is 16 */
p = b; i = n;
do {
c[*p++]++; /* assume all entries <= BMAX */
} while (--i);
if (c[0] == n) /* null input--all zero length codes */
{
*t = (inflate_huft *)Z_NULL;
*m = 0;
return (Z_OK);
}
/* Find minimum and maximum length, bound *m by those */
l = *m;
for (j = 1; j <= BMAX; j++)
if (c[j])
break;
k = j; /* minimum code length */
if ((uInt)l < j)
l = j;
for (i = BMAX; i; i--)
if (c[i])
break;
g = i; /* maximum code length */
if ((uInt)l > i)
l = i;
*m = l;
/* Adjust last length count to fill out codes, if needed */
for (y = 1 << j; j < i; j++, y <<= 1)
if ((y -= c[j]) < 0)
return (Z_DATA_ERROR);
if ((y -= c[i]) < 0)
return (Z_DATA_ERROR);
c[i] += y;
/* Generate starting offsets into the value table for each length */
x[1] = j = 0;
while (--i) { /* note that i == g from above */
*xp++ = (j += *p++);
}
/* Make a table of values in order of bit lengths */
p = b; i = 0;
do {
if ((j = *p++) != 0)
v[x[j]++] = i;
} while (++i < n);
n = x[g]; /* set n to length of v */
/* Generate the Huffman codes and for each, make the table entries */
x[0] = i = 0; /* first Huffman code is zero */
p = v; /* grab values in bit order */
h = -1; /* no tables yet--level -1 */
w = -l; /* bits decoded == (l * h) */
z = 0; /* ditto */
/* go through the bit lengths (k already is bits in shortest code) */
for (; k <= g; k++) {
a = c[k];
while (a--) {
/*
* here i is the Huffman code of length k bits
* for value *p. make tables up to required
* level.
*/
while (k > w + l) {
h++;
w += l; /* previous table always l bits */
/*
* compute minimum size table less
* than or equal to l bits
*/
z = g - w;
/* table size upper limit */
z = z > (uInt)l ? l : z;
/* try a k-w bit table */
if ((f = 1 << (j = k - w)) > a + 1) {
/* too few codes for k-w bit table */
/* deduct codes from patterns left */
f -= a + 1;
xp = c + k;
if (j < z)
/*
* try smaller tables
* up to z bits
*/
while (++j < z) {
/*
* enough
* codes to
* use up j
* bits
*/
if ((f <<= 1) <= *++xp)
break;
f -= *xp;
/*
* else deduct
* codes from
* patterns
*/
}
}
/* table entries for j-bit table */
z = 1 << j;
/* allocate new table */
/* (note: doesn't matter for fixed) */
/* not enough memory */
return (Z_MEM_ERROR);
*hn += z;
/* connect to last table, if there is one */
if (h) {
/* save pattern for backing up */
x[h] = i;
/* bits to dump before this table */
/* bits in this table */
j = i >> (w - l);
/* offset to this table */
/* connect to last table */
u[h-1][j] = r;
} else
/* first table is returned result */
*t = q;
}
/* set up table entry in r */
if (p >= v + n)
/* out of values--invalid code */
else if (*p < s)
{
/* 256 is end-of-block */
/* simple code is just the value */
r.base = *p++;
}
else
{
/* non-simple--look up in lists */
r.base = d[*p++ - s];
}
/* fill code-like entries with r */
f = 1 << (k - w);
for (j = i >> w; j < z; j += f)
q[j] = r;
/* backwards increment the k-bit code i */
for (j = 1 << (k - 1); i & j; j >>= 1)
i ^= j;
i ^= j;
/* backup over finished tables */
while ((i & mask) != x[h])
{
h--; /* don't need to update q */
w -= l;
}
}
}
/* Return Z_BUF_ERROR if we were given an incomplete table */
}
int
uIntf *c; /* 19 code lengths */
z_streamp z; /* for zfree function */
{
int r;
if (r == Z_DATA_ERROR)
z->msg = "oversubscribed dynamic bit lengths tree";
else if (r == Z_BUF_ERROR || *bb == 0)
{
z->msg = "incomplete dynamic bit lengths tree";
r = Z_DATA_ERROR;
}
return (r);
}
int
uIntf *c; /* that many (total) code lengths */
z_streamp z; /* for zfree function */
{
int r;
{
if (r == Z_DATA_ERROR)
else if (r != Z_MEM_ERROR)
{
r = Z_DATA_ERROR;
}
return (r);
}
/* build distance tree */
{
if (r == Z_DATA_ERROR)
z->msg = "oversubscribed distance tree";
else if (r == Z_BUF_ERROR) {
#ifdef PKZIP_BUG_WORKAROUND
r = Z_OK;
#else
z->msg = "incomplete distance tree";
r = Z_DATA_ERROR;
} else if (r != Z_MEM_ERROR) {
z->msg = "empty distance tree with lengths";
r = Z_DATA_ERROR;
#endif
}
return (r);
}
/* done */
return (Z_OK);
}
/* build fixed tables only once--keep them here */
/* #define BUILDFIXED */
#ifdef BUILDFIXED
#else
#include "inffixed.h"
#endif
/*ARGSUSED*/
int
z_streamp z; /* for memory allocation */
{
#ifdef BUILDFIXED
/*
* build fixed tables if not already (multiple overlapped
* executions ok)
*/
if (!fixed_built)
{
int k; /* temporary variable */
uInt f = 0; /* number of hufts used in fixed_mem */
uIntf *c; /* length list for huft_build */
uIntf *v;
/* allocate memory */
return (Z_MEM_ERROR);
{
ZFREE(z, c);
return (Z_MEM_ERROR);
}
/* literal table */
for (k = 0; k < 144; k++)
c[k] = 8;
for (; k < 256; k++)
c[k] = 9;
for (; k < 280; k++)
c[k] = 7;
for (; k < 288; k++)
c[k] = 8;
fixed_bl = 9;
/* distance table */
for (k = 0; k < 30; k++)
c[k] = 5;
fixed_bd = 5;
/* done */
ZFREE(z, v);
ZFREE(z, c);
fixed_built = 1;
}
#endif
return (Z_OK);
}
/* --- inftrees.c */
/* +++ infcodes.c */
/*
* infcodes.c -- process literals and length/distance pairs
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/* #include "zutil.h" */
/* #include "inftrees.h" */
/* #include "infblock.h" */
/* #include "infcodes.h" */
/* #include "infutil.h" */
/* +++ inffast.h */
/*
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/*
* WARNING: this file should *not* be used by applications. It is part
* of the implementation of the compression library and is subject to
* change. Applications should only use zlib.h.
*/
extern int inflate_fast OF((
uInt,
uInt,
const inflate_huft *,
const inflate_huft *,
z_streamp));
/* --- inffast.h */
/* simplify the use of the inflate_huft type with some defines */
/* inflate codes private state */
struct inflate_codes_state {
/* mode */
enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */
/* mode dependent information */
union {
struct {
struct {
/* mode independent information */
};
const inflate_huft *tl;
z_streamp z;
{
if ((c = (inflate_codes_statef *)
{
}
return (c);
}
int
inflate_codes(s, z, r)
z_streamp z;
int r;
{
uInt j; /* temporary storage */
const inflate_huft *t; /* temporary pointer */
uInt e; /* extra bits or operation */
uLong b; /* bit buffer */
uInt k; /* bits in bit buffer */
Bytef *p; /* input data pointer */
uInt n; /* bytes available there */
Bytef *q; /* output window write pointer */
uInt m; /* bytes to end of window or read pointer */
Bytef *f; /* pointer to copy strings from */
LOAD;
/* process input and output based on current state */
/* CONSTCOND */
while (1)
/* waiting for "i:"=input, "o:"=output, "x:"=nothing */
switch (c->mode) {
case START: /* x: set up for LEN */
#ifndef SLOW
if (m >= 258 && n >= 10)
{
LOAD;
if (r != Z_OK) {
c->mode = r == Z_STREAM_END ?
break;
}
}
#endif /* !SLOW */
/* FALLTHRU */
NEEDBITS(j);
((uInt)b & inflate_mask[j]);
if (e == 0) { /* literal */
t->base < 0x7f ?
"inflate: literal '%c'\n" :
"inflate: literal 0x%02x\n",
t->base));
break;
}
if (e & 16) { /* length */
break;
}
if ((e & 64) == 0) { /* next table */
break;
}
if (e & 32) { /* end of block */
"inflate: end of block\n"));
break;
}
r = Z_DATA_ERROR;
case LENEXT: /* i: getting length extra (have base) */
NEEDBITS(j);
DUMPBITS(j);
"inflate: length %u\n", c->len));
/* FALLTHRU */
case DIST: /* i: get distance next */
NEEDBITS(j);
if (e & 16) { /* distance */
break;
}
if ((e & 64) == 0) { /* next table */
break;
}
z->msg = "invalid distance code";
r = Z_DATA_ERROR;
case DISTEXT: /* i: getting distance extra */
NEEDBITS(j);
DUMPBITS(j);
"inflate: distance %u\n",
/* FALLTHRU */
case COPY:
/* o: copying bytes in window, waiting for space */
#ifndef __TURBOC__ /* Turbo C bug for following expression */
#else
#endif
while (c->len)
{
OUTBYTE(*f++);
if (f == s->end)
f = s->window;
c->len--;
}
break;
case LIT: /* o: got literal, waiting for output space */
break;
case WASH: /* o: got eob, possibly more output */
if (k > 7) { /* return unused byte, if any */
Assert(k < 16,
"inflate_codes grabbed too many bytes");
k -= 8;
n++;
p--; /* can always return one */
}
/* FALLTHRU */
case END:
r = Z_STREAM_END;
case BADCODE: /* x: got error */
r = Z_DATA_ERROR;
default:
r = Z_STREAM_ERROR;
}
/* NOTREACHED */
/* otherwise lint complains */
}
void
inflate_codes_free(c, z)
z_streamp z;
{
ZFREE(z, c);
}
/* --- infcodes.c */
/* +++ infutil.c */
/*
* inflate_util.c -- data and routines common to blocks and codes
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/* #include "zutil.h" */
/* #include "infblock.h" */
/* #include "inftrees.h" */
/* #include "infcodes.h" */
/* #include "infutil.h" */
#ifndef NO_DUMMY_DECL
#endif
/* And'ing with mask[n] masks the lower n bits */
0x0000,
0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
};
/* copy as much as possible from the sliding window to the output area */
int
inflate_flush(s, z, r)
z_streamp z;
int r;
{
uInt n;
Bytef *p;
Bytef *q;
/* local copies of source and destination pointers */
p = z->next_out;
q = s->read;
/* compute number of bytes to copy as far as end of window */
if (n && r == Z_BUF_ERROR) r = Z_OK;
/* update counters */
z->avail_out -= n;
z->total_out += n;
/* update check information */
/* copy as far as end of window */
if (p != Z_NULL) { /* PPP */
zmemcpy(p, q, n);
p += n;
} /* PPP */
q += n;
/* see if more to copy at beginning of window */
if (q == s->end)
{
/* wrap pointers */
q = s->window;
/* compute bytes to copy */
if (n && r == Z_BUF_ERROR) r = Z_OK;
/* update counters */
z->avail_out -= n;
z->total_out += n;
/* update check information */
/* copy */
if (p != Z_NULL) { /* PPP */
zmemcpy(p, q, n);
p += n;
} /* PPP */
q += n;
}
/* update pointers */
z->next_out = p;
s->read = q;
/* done */
return (r);
}
/* --- infutil.c */
/* +++ inffast.c */
/*
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/* #include "zutil.h" */
/* #include "inftrees.h" */
/* #include "infblock.h" */
/* #include "infcodes.h" */
/* #include "infutil.h" */
/* #include "inffast.h" */
#ifndef NO_DUMMY_DECL
#endif
/* simplify the use of the inflate_huft type with some defines */
/* macros for bit input with no checking and for returning unused bytes */
k -= c<<3; }
/*
* Called with number of bytes left to write in window at least 258
* (the maximum string length) and number of input bytes available at
* least ten. The ten bytes are six bytes for the longest length/
* distance pair plus four bytes for overloading the bit buffer.
*/
int
const inflate_huft *tl;
z_streamp z;
{
const inflate_huft *t; /* temporary pointer */
uInt e; /* extra bits or operation */
uLong b; /* bit buffer */
uInt k; /* bits in bit buffer */
Bytef *p; /* input data pointer */
uInt n; /* bytes available there */
Bytef *q; /* output window write pointer */
uInt m; /* bytes to end of window or read pointer */
uInt c; /* bytes to copy */
uInt d; /* distance back to copy from */
Bytef *r; /* copy source pointer */
/* load input, output, bit values */
LOAD;
/* initialize masks */
/* do until not enough input or output space for fast loop */
do { /* assume called with m >= 258 && n >= 10 */
GRABBITS(20);
"inflate: * literal '%c'\n" :
"inflate: * literal 0x%02x\n", t->base));
m--;
continue;
}
do {
if (e & 16) {
/* get extra bits for length */
e &= 15;
DUMPBITS(e);
"inflate: * length %u\n", c));
/* decode distance base of block to copy */
do {
if (e & 16) {
/*
* get extra bits to
* add to distance
* base
*/
e &= 15;
/* get extra bits (up to 13) */
GRABBITS(e);
inflate_mask[e]);
DUMPBITS(e);
"inflate: * "
"distance %u\n", d));
/* do the copy */
m -= c;
/* offset before dest */
/* just copy */
{
r = q - d;
/*
* minimum
* count is
* three, so
* unroll loop
* a little
*/
*q++ = *r++; c--;
*q++ = *r++; c--;
}
/* else offset after destination */
else {
/* bytes from offset to end */
e = d - (uInt)(q -
s->window);
/* pointer to offset */
r = s->end - e;
/* if source crosses */
if (c > e) {
/* copy to end of window */
c -= e;
do {
*q++ =
*r
++;
} while (--e);
/* copy rest from start of window */
r = s->window;
}
}
/* copy all or what's left */
do {
*q++ = *r++;
} while (--c);
break;
} else if ((e & 64) == 0) {
t += t->base;
e = (t += ((uInt)b &
inflate_mask[e]))->exop;
} else {
z->msg =
"invalid distance code";
return (Z_DATA_ERROR);
}
/* CONSTCOND */
} while (1);
break;
}
if ((e & 64) == 0)
{
t += t->base;
if ((e = (t += ((uInt)b &
inflate_mask[e]))->exop) == 0)
{
t->base < 0x7f ?
"inflate: * literal '%c'\n"
:
"inflate: * literal "
"0x%02x\n", t->base));
m--;
break;
}
} else if (e & 32) {
"inflate: * end of block\n"));
return (Z_STREAM_END);
} else {
return (Z_DATA_ERROR);
}
/* CONSTCOND */
} while (1);
} while (m >= 258 && n >= 10);
/* not enough input or output--restore pointers and return */
return (Z_OK);
}
/* --- inffast.c */
/* +++ zutil.c */
/*
* zutil.c -- target dependent utility functions for the compression library
* Copyright (C) 1995-1998 Jean-loup Gailly.
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/* From: zutil.c,v 1.17 1996/07/24 13:41:12 me Exp $ */
#ifdef DEBUG_ZLIB
#include <stdio.h>
#endif
/* #include "zutil.h" */
#ifndef NO_DUMMY_DECL
#endif
#ifndef STDC
#endif
"need dictionary", /* Z_NEED_DICT 2 */
"stream end", /* Z_STREAM_END 1 */
"", /* Z_OK 0 */
"file error", /* Z_ERRNO (-1) */
"stream error", /* Z_STREAM_ERROR (-2) */
"data error", /* Z_DATA_ERROR (-3) */
"insufficient memory", /* Z_MEM_ERROR (-4) */
"buffer error", /* Z_BUF_ERROR (-5) */
"incompatible version", /* Z_VERSION_ERROR (-6) */
""};
const char *
{
return (ZLIB_VERSION);
}
#ifdef DEBUG_ZLIB
void
z_error(m)
char *m;
{
exit(1);
}
#endif
#ifndef HAVE_MEMCPY
void
{
if (len == 0)
return;
do {
} while (--len != 0);
}
int
{
uInt j;
for (j = 0; j < len; j++) {
}
return (0);
}
void
{
if (len == 0)
return;
do {
*dest++ = 0; /* ??? to be unrolled */
} while (--len != 0);
}
#endif
#ifdef __TURBOC__
/*
* Small and medium model in Turbo C are for now limited to near
* allocation with reduced MAX_WBITS and MAX_MEM_LEVEL
*/
#define MY_ZCALLOC
/*
* Turbo C malloc() does not allow dynamic allocation of 64K bytes and
* farmalloc(64K) returns a pointer with an offset of 8, so we must
* fix the pointer. Warning: the pointer must be put back to its
* original form in order to free it, use zcfree().
*/
/* 10*64K = 640K */
typedef struct ptr_table_s {
} ptr_table;
/*
* This table is used to remember the original form of pointers to
* large buffers (64K). Such pointers are normalized with a zero
* offset. Since MSDOS is not a preemptive multitasking OS, this
* table is not protected from concurrent access. This hack doesn't
* work anyway on a protected system like OS/2. Use Microsoft C
* instead.
*/
{
/*
* If we allocate less than 65520 bytes, we assume that
* farmalloc will return a usable pointer which doesn't have
* to be normalized.
*/
if (bsize < 65520L) {
return (buf);
} else {
}
return (NULL);
/* Normalize the pointer to seg:0 */
return (buf);
}
void
{
int n;
return;
}
/* Find the original pointer */
for (n = 0; n < next_ptr; n++) {
continue;
while (++n < next_ptr) {
}
next_ptr--;
return;
}
Assert(0, "zcfree: ptr not found");
}
#endif
#endif /* __TURBOC__ */
/* Microsoft C in 16-bit mode */
#define MY_ZCALLOC
#endif
{
}
void
{
}
#endif /* MSC */
#ifndef MY_ZCALLOC /* Any system without a special alloc function */
#ifndef STDC
#endif
unsigned items;
unsigned size;
{
}
/*ARGSUSED*/
void
{
}
#endif /* MY_ZCALLOC */
/* --- zutil.c */
/* +++ adler32.c */
/*
* adler32.c -- compute the Adler-32 checksum of a data stream
* Copyright (C) 1995-1998 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*/
/* From: adler32.c,v 1.10 1996/05/22 11:52:18 me Exp $ */
/* #include "zlib.h" */
/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
/* ========================================================================= */
{
int k;
return (1L);
while (len > 0) {
len -= k;
while (k >= 16) {
buf += 16;
k -= 16;
}
if (k != 0) do {
} while (--k);
}
}
/* --- adler32.c */