zlib.c revision 90775
128415Speter/* 234768Speter * This file is derived from various .h and .c files from the zlib-1.0.4 328415Speter * distribution by Jean-loup Gailly and Mark Adler, with some additions 428415Speter * by Paul Mackerras to aid in implementing Deflate compression and 528415Speter * decompression for PPP packets. See zlib.h for conditions of 628415Speter * distribution and use. 728415Speter * 828415Speter * Changes that have been made include: 928415Speter * - added Z_PACKET_FLUSH (see zlib.h for details) 1034768Speter * - added inflateIncomp and deflateOutputPending 1134768Speter * - allow strm->next_out to be NULL, meaning discard the output 1228415Speter * 1350477Speter * $FreeBSD: head/sys/net/zlib.c 90775 2002-02-17 17:35:18Z jedgar $ 1428415Speter */ 1528415Speter 1628415Speter/* 1734768Speter * ==FILEVERSION 971210== 1828415Speter * 1928415Speter * This marker is used by the Linux installation script to determine 2028415Speter * whether an up-to-date version of this file is already installed. 2128415Speter */ 2228415Speter 2334768Speter#define NO_DUMMY_DECL 2434768Speter#define NO_ZCFUNCS 2534768Speter#define MY_ZCALLOC 2634768Speter 2755205Speter#if defined(__FreeBSD__) && defined(_KERNEL) 2834768Speter#define inflate inflate_ppp /* FreeBSD already has an inflate :-( */ 2934768Speter#endif 3034768Speter 3134768Speter 3234768Speter/* +++ zutil.h */ 3328415Speter/* zutil.h -- internal interface and configuration of the compression library 3434768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 3528415Speter * For conditions of distribution and use, see copyright notice in zlib.h 3628415Speter */ 3728415Speter 3828415Speter/* WARNING: this file should *not* be used by applications. It is 3928415Speter part of the implementation of the compression library and is 4028415Speter subject to change. Applications should only use zlib.h. 4128415Speter */ 4228415Speter 4334768Speter/* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */ 4428415Speter 4534768Speter#ifndef _Z_UTIL_H 4628415Speter#define _Z_UTIL_H 4728415Speter 4855205Speter#ifdef _KERNEL 4928415Speter#include <net/zlib.h> 5028415Speter#else 5128415Speter#include "zlib.h" 5228415Speter#endif 5328415Speter 5455205Speter#ifdef _KERNEL 5534768Speter/* Assume this is a *BSD or SVR4 kernel */ 5634768Speter#include <sys/types.h> 5734768Speter#include <sys/time.h> 5834768Speter#include <sys/systm.h> 5934768Speter# define HAVE_MEMCPY 6034768Speter# define memcpy(d, s, n) bcopy((s), (d), (n)) 6134768Speter# define memset(d, v, n) bzero((d), (n)) 6234768Speter# define memcmp bcmp 6334768Speter 6434768Speter#else 6534768Speter#if defined(__KERNEL__) 6634768Speter/* Assume this is a Linux kernel */ 6734768Speter#include <linux/string.h> 6834768Speter#define HAVE_MEMCPY 6934768Speter 7034768Speter#else /* not kernel */ 7134768Speter 7234768Speter#if defined(MSDOS)||defined(VMS)||defined(CRAY)||defined(WIN32)||defined(RISCOS) 7334768Speter# include <stddef.h> 7434768Speter# include <errno.h> 7534768Speter#else 7634768Speter extern int errno; 7734768Speter#endif 7834768Speter#ifdef STDC 7934768Speter# include <string.h> 8034768Speter# include <stdlib.h> 8134768Speter#endif 8234768Speter#endif /* __KERNEL__ */ 8355205Speter#endif /* _KERNEL */ 8434768Speter 8528415Speter#ifndef local 8628415Speter# define local static 8728415Speter#endif 8828415Speter/* compile with -Dlocal if your debugger can't find static symbols */ 8928415Speter 9028415Spetertypedef unsigned char uch; 9128415Spetertypedef uch FAR uchf; 9228415Spetertypedef unsigned short ush; 9328415Spetertypedef ush FAR ushf; 9428415Spetertypedef unsigned long ulg; 9528415Speter 9634768Speterextern const char *z_errmsg[10]; /* indexed by 2-zlib_error */ 9734768Speter/* (size given to avoid silly warnings with Visual C++) */ 9828415Speter 9934768Speter#define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)] 10034768Speter 10134768Speter#define ERR_RETURN(strm,err) \ 10243305Sdillon return (strm->msg = (const char*)ERR_MSG(err), (err)) 10328415Speter/* To be used only when the state is known to be valid */ 10428415Speter 10528415Speter /* common constants */ 10628415Speter 10728415Speter#ifndef DEF_WBITS 10828415Speter# define DEF_WBITS MAX_WBITS 10928415Speter#endif 11028415Speter/* default windowBits for decompression. MAX_WBITS is for compression only */ 11128415Speter 11228415Speter#if MAX_MEM_LEVEL >= 8 11328415Speter# define DEF_MEM_LEVEL 8 11428415Speter#else 11528415Speter# define DEF_MEM_LEVEL MAX_MEM_LEVEL 11628415Speter#endif 11728415Speter/* default memLevel */ 11828415Speter 11928415Speter#define STORED_BLOCK 0 12028415Speter#define STATIC_TREES 1 12128415Speter#define DYN_TREES 2 12228415Speter/* The three kinds of block type */ 12328415Speter 12428415Speter#define MIN_MATCH 3 12528415Speter#define MAX_MATCH 258 12628415Speter/* The minimum and maximum match lengths */ 12728415Speter 12834768Speter#define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */ 12934768Speter 13034768Speter /* target dependencies */ 13134768Speter 13234768Speter#ifdef MSDOS 13334768Speter# define OS_CODE 0x00 13434768Speter# ifdef __TURBOC__ 13534768Speter# include <alloc.h> 13634768Speter# else /* MSC or DJGPP */ 13734768Speter# include <malloc.h> 13834768Speter# endif 13934768Speter#endif 14034768Speter 14134768Speter#ifdef OS2 14234768Speter# define OS_CODE 0x06 14334768Speter#endif 14434768Speter 14534768Speter#ifdef WIN32 /* Window 95 & Windows NT */ 14634768Speter# define OS_CODE 0x0b 14734768Speter#endif 14834768Speter 14934768Speter#if defined(VAXC) || defined(VMS) 15034768Speter# define OS_CODE 0x02 15134768Speter# define FOPEN(name, mode) \ 15234768Speter fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512") 15334768Speter#endif 15434768Speter 15534768Speter#ifdef AMIGA 15634768Speter# define OS_CODE 0x01 15734768Speter#endif 15834768Speter 15934768Speter#if defined(ATARI) || defined(atarist) 16034768Speter# define OS_CODE 0x05 16134768Speter#endif 16234768Speter 16334768Speter#ifdef MACOS 16434768Speter# define OS_CODE 0x07 16534768Speter#endif 16634768Speter 16734768Speter#ifdef __50SERIES /* Prime/PRIMOS */ 16834768Speter# define OS_CODE 0x0F 16934768Speter#endif 17034768Speter 17134768Speter#ifdef TOPS20 17234768Speter# define OS_CODE 0x0a 17334768Speter#endif 17434768Speter 17534768Speter#if defined(_BEOS_) || defined(RISCOS) 17634768Speter# define fdopen(fd,mode) NULL /* No fdopen() */ 17734768Speter#endif 17834768Speter 17934768Speter /* Common defaults */ 18034768Speter 18134768Speter#ifndef OS_CODE 18234768Speter# define OS_CODE 0x03 /* assume Unix */ 18334768Speter#endif 18434768Speter 18534768Speter#ifndef FOPEN 18634768Speter# define FOPEN(name, mode) fopen((name), (mode)) 18734768Speter#endif 18834768Speter 18928415Speter /* functions */ 19028415Speter 19134768Speter#ifdef HAVE_STRERROR 19234768Speter extern char *strerror OF((int)); 19334768Speter# define zstrerror(errnum) strerror(errnum) 19428415Speter#else 19534768Speter# define zstrerror(errnum) "" 19634768Speter#endif 19728415Speter 19834768Speter#if defined(pyr) 19934768Speter# define NO_MEMCPY 20034768Speter#endif 20134768Speter#if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER) 20234768Speter /* Use our own functions for small and medium model with MSC <= 5.0. 20334768Speter * You may have to use the same strategy for Borland C (untested). 20434768Speter */ 20534768Speter# define NO_MEMCPY 20634768Speter#endif 20728415Speter#if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY) 20828415Speter# define HAVE_MEMCPY 20928415Speter#endif 21028415Speter#ifdef HAVE_MEMCPY 21134768Speter# ifdef SMALL_MEDIUM /* MSDOS small or medium model */ 21234768Speter# define zmemcpy _fmemcpy 21334768Speter# define zmemcmp _fmemcmp 21434768Speter# define zmemzero(dest, len) _fmemset(dest, 0, len) 21534768Speter# else 21628415Speter# define zmemcpy memcpy 21734768Speter# define zmemcmp memcmp 21828415Speter# define zmemzero(dest, len) memset(dest, 0, len) 21934768Speter# endif 22028415Speter#else 22128415Speter extern void zmemcpy OF((Bytef* dest, Bytef* source, uInt len)); 22234768Speter extern int zmemcmp OF((Bytef* s1, Bytef* s2, uInt len)); 22328415Speter extern void zmemzero OF((Bytef* dest, uInt len)); 22428415Speter#endif 22528415Speter 22628415Speter/* Diagnostic functions */ 22728415Speter#ifdef DEBUG_ZLIB 22828415Speter# include <stdio.h> 22928415Speter# ifndef verbose 23028415Speter# define verbose 0 23128415Speter# endif 23234768Speter extern void z_error OF((char *m)); 23328415Speter# define Assert(cond,msg) {if(!(cond)) z_error(msg);} 23428415Speter# define Trace(x) fprintf x 23528415Speter# define Tracev(x) {if (verbose) fprintf x ;} 23628415Speter# define Tracevv(x) {if (verbose>1) fprintf x ;} 23728415Speter# define Tracec(c,x) {if (verbose && (c)) fprintf x ;} 23828415Speter# define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;} 23928415Speter#else 24028415Speter# define Assert(cond,msg) 24128415Speter# define Trace(x) 24228415Speter# define Tracev(x) 24328415Speter# define Tracevv(x) 24428415Speter# define Tracec(c,x) 24528415Speter# define Tracecv(c,x) 24628415Speter#endif 24728415Speter 24828415Speter 24934768Spetertypedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len)); 25028415Speter 25134768Spetervoidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); 25234768Spetervoid zcfree OF((voidpf opaque, voidpf ptr)); 25328415Speter 25428415Speter#define ZALLOC(strm, items, size) \ 25528415Speter (*((strm)->zalloc))((strm)->opaque, (items), (size)) 25634768Speter#define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr)) 25734768Speter#define TRY_FREE(s, p) {if (p) ZFREE(s, p);} 25828415Speter 25934768Speter#endif /* _Z_UTIL_H */ 26034768Speter/* --- zutil.h */ 26134768Speter 26234768Speter/* +++ deflate.h */ 26328415Speter/* deflate.h -- internal compression state 26434768Speter * Copyright (C) 1995-1996 Jean-loup Gailly 26528415Speter * For conditions of distribution and use, see copyright notice in zlib.h 26628415Speter */ 26728415Speter 26828415Speter/* WARNING: this file should *not* be used by applications. It is 26928415Speter part of the implementation of the compression library and is 27028415Speter subject to change. Applications should only use zlib.h. 27128415Speter */ 27228415Speter 27334768Speter/* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */ 27428415Speter 27534768Speter#ifndef _DEFLATE_H 27634768Speter#define _DEFLATE_H 27728415Speter 27834768Speter/* #include "zutil.h" */ 27934768Speter 28028415Speter/* =========================================================================== 28128415Speter * Internal compression state. 28228415Speter */ 28328415Speter 28428415Speter#define LENGTH_CODES 29 28528415Speter/* number of length codes, not counting the special END_BLOCK code */ 28628415Speter 28728415Speter#define LITERALS 256 28828415Speter/* number of literal bytes 0..255 */ 28928415Speter 29028415Speter#define L_CODES (LITERALS+1+LENGTH_CODES) 29128415Speter/* number of Literal or Length codes, including the END_BLOCK code */ 29228415Speter 29328415Speter#define D_CODES 30 29428415Speter/* number of distance codes */ 29528415Speter 29628415Speter#define BL_CODES 19 29728415Speter/* number of codes used to transfer the bit lengths */ 29828415Speter 29928415Speter#define HEAP_SIZE (2*L_CODES+1) 30028415Speter/* maximum heap size */ 30128415Speter 30228415Speter#define MAX_BITS 15 30328415Speter/* All codes must not exceed MAX_BITS bits */ 30428415Speter 30528415Speter#define INIT_STATE 42 30628415Speter#define BUSY_STATE 113 30728415Speter#define FINISH_STATE 666 30828415Speter/* Stream status */ 30928415Speter 31028415Speter 31128415Speter/* Data structure describing a single value and its code string. */ 31228415Spetertypedef struct ct_data_s { 31328415Speter union { 31428415Speter ush freq; /* frequency count */ 31528415Speter ush code; /* bit string */ 31628415Speter } fc; 31728415Speter union { 31828415Speter ush dad; /* father node in Huffman tree */ 31928415Speter ush len; /* length of bit string */ 32028415Speter } dl; 32128415Speter} FAR ct_data; 32228415Speter 32328415Speter#define Freq fc.freq 32428415Speter#define Code fc.code 32528415Speter#define Dad dl.dad 32628415Speter#define Len dl.len 32728415Speter 32828415Spetertypedef struct static_tree_desc_s static_tree_desc; 32928415Speter 33028415Spetertypedef struct tree_desc_s { 33128415Speter ct_data *dyn_tree; /* the dynamic tree */ 33228415Speter int max_code; /* largest code with non zero frequency */ 33328415Speter static_tree_desc *stat_desc; /* the corresponding static tree */ 33428415Speter} FAR tree_desc; 33528415Speter 33628415Spetertypedef ush Pos; 33728415Spetertypedef Pos FAR Posf; 33828415Spetertypedef unsigned IPos; 33928415Speter 34028415Speter/* A Pos is an index in the character window. We use short instead of int to 34128415Speter * save space in the various tables. IPos is used only for parameter passing. 34228415Speter */ 34328415Speter 34428415Spetertypedef struct deflate_state { 34534768Speter z_streamp strm; /* pointer back to this zlib stream */ 34628415Speter int status; /* as the name implies */ 34728415Speter Bytef *pending_buf; /* output still pending */ 34834768Speter ulg pending_buf_size; /* size of pending_buf */ 34928415Speter Bytef *pending_out; /* next pending byte to output to the stream */ 35028415Speter int pending; /* nb of bytes in the pending buffer */ 35128415Speter int noheader; /* suppress zlib header and adler32 */ 35234768Speter Byte data_type; /* UNKNOWN, BINARY or ASCII */ 35328415Speter Byte method; /* STORED (for zip only) or DEFLATED */ 35434768Speter int last_flush; /* value of flush param for previous deflate call */ 35528415Speter 35628415Speter /* used by deflate.c: */ 35728415Speter 35828415Speter uInt w_size; /* LZ77 window size (32K by default) */ 35928415Speter uInt w_bits; /* log2(w_size) (8..16) */ 36028415Speter uInt w_mask; /* w_size - 1 */ 36128415Speter 36228415Speter Bytef *window; 36328415Speter /* Sliding window. Input bytes are read into the second half of the window, 36428415Speter * and move to the first half later to keep a dictionary of at least wSize 36528415Speter * bytes. With this organization, matches are limited to a distance of 36628415Speter * wSize-MAX_MATCH bytes, but this ensures that IO is always 36728415Speter * performed with a length multiple of the block size. Also, it limits 36828415Speter * the window size to 64K, which is quite useful on MSDOS. 36928415Speter * To do: use the user input buffer as sliding window. 37028415Speter */ 37128415Speter 37228415Speter ulg window_size; 37328415Speter /* Actual size of window: 2*wSize, except when the user input buffer 37428415Speter * is directly used as sliding window. 37528415Speter */ 37628415Speter 37728415Speter Posf *prev; 37828415Speter /* Link to older string with same hash index. To limit the size of this 37928415Speter * array to 64K, this link is maintained only for the last 32K strings. 38028415Speter * An index in this array is thus a window index modulo 32K. 38128415Speter */ 38228415Speter 38328415Speter Posf *head; /* Heads of the hash chains or NIL. */ 38428415Speter 38528415Speter uInt ins_h; /* hash index of string to be inserted */ 38628415Speter uInt hash_size; /* number of elements in hash table */ 38728415Speter uInt hash_bits; /* log2(hash_size) */ 38828415Speter uInt hash_mask; /* hash_size-1 */ 38928415Speter 39028415Speter uInt hash_shift; 39128415Speter /* Number of bits by which ins_h must be shifted at each input 39228415Speter * step. It must be such that after MIN_MATCH steps, the oldest 39328415Speter * byte no longer takes part in the hash key, that is: 39428415Speter * hash_shift * MIN_MATCH >= hash_bits 39528415Speter */ 39628415Speter 39728415Speter long block_start; 39828415Speter /* Window position at the beginning of the current output block. Gets 39928415Speter * negative when the window is moved backwards. 40028415Speter */ 40128415Speter 40228415Speter uInt match_length; /* length of best match */ 40328415Speter IPos prev_match; /* previous match */ 40428415Speter int match_available; /* set if previous match exists */ 40528415Speter uInt strstart; /* start of string to insert */ 40628415Speter uInt match_start; /* start of matching string */ 40728415Speter uInt lookahead; /* number of valid bytes ahead in window */ 40828415Speter 40928415Speter uInt prev_length; 41028415Speter /* Length of the best match at previous step. Matches not greater than this 41128415Speter * are discarded. This is used in the lazy match evaluation. 41228415Speter */ 41328415Speter 41428415Speter uInt max_chain_length; 41528415Speter /* To speed up deflation, hash chains are never searched beyond this 41628415Speter * length. A higher limit improves compression ratio but degrades the 41728415Speter * speed. 41828415Speter */ 41928415Speter 42028415Speter uInt max_lazy_match; 42128415Speter /* Attempt to find a better match only when the current match is strictly 42228415Speter * smaller than this value. This mechanism is used only for compression 42328415Speter * levels >= 4. 42428415Speter */ 42528415Speter# define max_insert_length max_lazy_match 42628415Speter /* Insert new strings in the hash table only if the match length is not 42728415Speter * greater than this length. This saves time but degrades compression. 42828415Speter * max_insert_length is used only for compression levels <= 3. 42928415Speter */ 43028415Speter 43128415Speter int level; /* compression level (1..9) */ 43228415Speter int strategy; /* favor or force Huffman coding*/ 43328415Speter 43428415Speter uInt good_match; 43528415Speter /* Use a faster search when the previous match is longer than this */ 43628415Speter 43734768Speter int nice_match; /* Stop searching when current match exceeds this */ 43828415Speter 43928415Speter /* used by trees.c: */ 44028415Speter /* Didn't use ct_data typedef below to supress compiler warning */ 44128415Speter struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 44228415Speter struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ 44328415Speter struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */ 44428415Speter 44528415Speter struct tree_desc_s l_desc; /* desc. for literal tree */ 44628415Speter struct tree_desc_s d_desc; /* desc. for distance tree */ 44728415Speter struct tree_desc_s bl_desc; /* desc. for bit length tree */ 44828415Speter 44928415Speter ush bl_count[MAX_BITS+1]; 45028415Speter /* number of codes at each bit length for an optimal tree */ 45128415Speter 45228415Speter int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 45328415Speter int heap_len; /* number of elements in the heap */ 45428415Speter int heap_max; /* element of largest frequency */ 45528415Speter /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 45628415Speter * The same heap array is used to build all trees. 45728415Speter */ 45828415Speter 45928415Speter uch depth[2*L_CODES+1]; 46028415Speter /* Depth of each subtree used as tie breaker for trees of equal frequency 46128415Speter */ 46228415Speter 46328415Speter uchf *l_buf; /* buffer for literals or lengths */ 46428415Speter 46528415Speter uInt lit_bufsize; 46628415Speter /* Size of match buffer for literals/lengths. There are 4 reasons for 46728415Speter * limiting lit_bufsize to 64K: 46828415Speter * - frequencies can be kept in 16 bit counters 46928415Speter * - if compression is not successful for the first block, all input 47028415Speter * data is still in the window so we can still emit a stored block even 47128415Speter * when input comes from standard input. (This can also be done for 47228415Speter * all blocks if lit_bufsize is not greater than 32K.) 47328415Speter * - if compression is not successful for a file smaller than 64K, we can 47428415Speter * even emit a stored file instead of a stored block (saving 5 bytes). 47528415Speter * This is applicable only for zip (not gzip or zlib). 47628415Speter * - creating new Huffman trees less frequently may not provide fast 47728415Speter * adaptation to changes in the input data statistics. (Take for 47828415Speter * example a binary file with poorly compressible code followed by 47928415Speter * a highly compressible string table.) Smaller buffer sizes give 48028415Speter * fast adaptation but have of course the overhead of transmitting 48128415Speter * trees more frequently. 48228415Speter * - I can't count above 4 48328415Speter */ 48428415Speter 48528415Speter uInt last_lit; /* running index in l_buf */ 48628415Speter 48728415Speter ushf *d_buf; 48828415Speter /* Buffer for distances. To simplify the code, d_buf and l_buf have 48928415Speter * the same number of elements. To use different lengths, an extra flag 49028415Speter * array would be necessary. 49128415Speter */ 49228415Speter 49328415Speter ulg opt_len; /* bit length of current block with optimal trees */ 49428415Speter ulg static_len; /* bit length of current block with static trees */ 49528415Speter ulg compressed_len; /* total bit length of compressed file */ 49628415Speter uInt matches; /* number of string matches in current block */ 49728415Speter int last_eob_len; /* bit length of EOB code for last block */ 49828415Speter 49928415Speter#ifdef DEBUG_ZLIB 50028415Speter ulg bits_sent; /* bit length of the compressed data */ 50128415Speter#endif 50228415Speter 50328415Speter ush bi_buf; 50428415Speter /* Output buffer. bits are inserted starting at the bottom (least 50528415Speter * significant bits). 50628415Speter */ 50728415Speter int bi_valid; 50828415Speter /* Number of valid bits in bi_buf. All bits above the last valid bit 50928415Speter * are always zero. 51028415Speter */ 51128415Speter 51228415Speter} FAR deflate_state; 51328415Speter 51428415Speter/* Output a byte on the stream. 51528415Speter * IN assertion: there is enough room in pending_buf. 51628415Speter */ 51728415Speter#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);} 51828415Speter 51928415Speter 52028415Speter#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 52128415Speter/* Minimum amount of lookahead, except at the end of the input file. 52228415Speter * See deflate.c for comments about the MIN_MATCH+1. 52328415Speter */ 52428415Speter 52528415Speter#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) 52628415Speter/* In order to simplify the code, particularly on 16 bit machines, match 52728415Speter * distances are limited to MAX_DIST instead of WSIZE. 52828415Speter */ 52928415Speter 53028415Speter /* in trees.c */ 53134768Spetervoid _tr_init OF((deflate_state *s)); 53234768Speterint _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); 53334768Speterulg _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len, 53434768Speter int eof)); 53534768Spetervoid _tr_align OF((deflate_state *s)); 53634768Spetervoid _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len, 53728415Speter int eof)); 53834768Spetervoid _tr_stored_type_only OF((deflate_state *)); 53928415Speter 54034768Speter#endif 54134768Speter/* --- deflate.h */ 54228415Speter 54334768Speter/* +++ deflate.c */ 54428415Speter/* deflate.c -- compress data using the deflation algorithm 54534768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 54628415Speter * For conditions of distribution and use, see copyright notice in zlib.h 54728415Speter */ 54828415Speter 54928415Speter/* 55028415Speter * ALGORITHM 55128415Speter * 55228415Speter * The "deflation" process depends on being able to identify portions 55328415Speter * of the input text which are identical to earlier input (within a 55428415Speter * sliding window trailing behind the input currently being processed). 55528415Speter * 55628415Speter * The most straightforward technique turns out to be the fastest for 55728415Speter * most input files: try all possible matches and select the longest. 55828415Speter * The key feature of this algorithm is that insertions into the string 55928415Speter * dictionary are very simple and thus fast, and deletions are avoided 56028415Speter * completely. Insertions are performed at each input character, whereas 56128415Speter * string matches are performed only when the previous match ends. So it 56228415Speter * is preferable to spend more time in matches to allow very fast string 56328415Speter * insertions and avoid deletions. The matching algorithm for small 56428415Speter * strings is inspired from that of Rabin & Karp. A brute force approach 56528415Speter * is used to find longer strings when a small match has been found. 56628415Speter * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 56728415Speter * (by Leonid Broukhis). 56828415Speter * A previous version of this file used a more sophisticated algorithm 56928415Speter * (by Fiala and Greene) which is guaranteed to run in linear amortized 57028415Speter * time, but has a larger average cost, uses more memory and is patented. 57128415Speter * However the F&G algorithm may be faster for some highly redundant 57228415Speter * files if the parameter max_chain_length (described below) is too large. 57328415Speter * 57428415Speter * ACKNOWLEDGEMENTS 57528415Speter * 57628415Speter * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 57728415Speter * I found it in 'freeze' written by Leonid Broukhis. 57828415Speter * Thanks to many people for bug reports and testing. 57928415Speter * 58028415Speter * REFERENCES 58128415Speter * 58234768Speter * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 58334768Speter * Available in ftp://ds.internic.net/rfc/rfc1951.txt 58428415Speter * 58528415Speter * A description of the Rabin and Karp algorithm is given in the book 58628415Speter * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 58728415Speter * 58828415Speter * Fiala,E.R., and Greene,D.H. 58928415Speter * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 59028415Speter * 59128415Speter */ 59228415Speter 59334768Speter/* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */ 59428415Speter 59534768Speter/* #include "deflate.h" */ 59634768Speter 59734768Speterchar deflate_copyright[] = " deflate 1.0.4 Copyright 1995-1996 Jean-loup Gailly "; 59828415Speter/* 59928415Speter If you use the zlib library in a product, an acknowledgment is welcome 60028415Speter in the documentation of your product. If for some reason you cannot 60128415Speter include such an acknowledgment, I would appreciate that you keep this 60228415Speter copyright string in the executable of your product. 60328415Speter */ 60428415Speter 60534768Speter/* =========================================================================== 60634768Speter * Function prototypes. 60734768Speter */ 60834768Spetertypedef enum { 60934768Speter need_more, /* block not completed, need more input or more output */ 61034768Speter block_done, /* block flush performed */ 61134768Speter finish_started, /* finish started, need only more output at next deflate */ 61234768Speter finish_done /* finish done, accept no more input or output */ 61334768Speter} block_state; 61434768Speter 61534768Spetertypedef block_state (*compress_func) OF((deflate_state *s, int flush)); 61634768Speter/* Compression function. Returns the block state after the call. */ 61734768Speter 61834768Speterlocal void fill_window OF((deflate_state *s)); 61934768Speterlocal block_state deflate_stored OF((deflate_state *s, int flush)); 62034768Speterlocal block_state deflate_fast OF((deflate_state *s, int flush)); 62134768Speterlocal block_state deflate_slow OF((deflate_state *s, int flush)); 62234768Speterlocal void lm_init OF((deflate_state *s)); 62334768Speterlocal void putShortMSB OF((deflate_state *s, uInt b)); 62434768Speterlocal void flush_pending OF((z_streamp strm)); 62534768Speterlocal int read_buf OF((z_streamp strm, charf *buf, unsigned size)); 62634768Speter#ifdef ASMV 62734768Speter void match_init OF((void)); /* asm code initialization */ 62834768Speter uInt longest_match OF((deflate_state *s, IPos cur_match)); 62934768Speter#else 63034768Speterlocal uInt longest_match OF((deflate_state *s, IPos cur_match)); 63134768Speter#endif 63234768Speter 63334768Speter#ifdef DEBUG_ZLIB 63434768Speterlocal void check_match OF((deflate_state *s, IPos start, IPos match, 63534768Speter int length)); 63634768Speter#endif 63734768Speter 63834768Speter/* =========================================================================== 63934768Speter * Local data 64034768Speter */ 64134768Speter 64228415Speter#define NIL 0 64328415Speter/* Tail of hash chains */ 64428415Speter 64528415Speter#ifndef TOO_FAR 64628415Speter# define TOO_FAR 4096 64728415Speter#endif 64828415Speter/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 64928415Speter 65028415Speter#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 65128415Speter/* Minimum amount of lookahead, except at the end of the input file. 65228415Speter * See deflate.c for comments about the MIN_MATCH+1. 65328415Speter */ 65428415Speter 65528415Speter/* Values for max_lazy_match, good_match and max_chain_length, depending on 65628415Speter * the desired pack level (0..9). The values given below have been tuned to 65728415Speter * exclude worst case performance for pathological files. Better values may be 65828415Speter * found for specific files. 65928415Speter */ 66028415Spetertypedef struct config_s { 66128415Speter ush good_length; /* reduce lazy search above this match length */ 66228415Speter ush max_lazy; /* do not perform lazy search above this match length */ 66328415Speter ush nice_length; /* quit search above this match length */ 66428415Speter ush max_chain; 66534768Speter compress_func func; 66628415Speter} config; 66728415Speter 66828415Speterlocal config configuration_table[10] = { 66928415Speter/* good lazy nice chain */ 67034768Speter/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 67134768Speter/* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ 67234768Speter/* 2 */ {4, 5, 16, 8, deflate_fast}, 67334768Speter/* 3 */ {4, 6, 32, 32, deflate_fast}, 67428415Speter 67534768Speter/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 67634768Speter/* 5 */ {8, 16, 32, 32, deflate_slow}, 67734768Speter/* 6 */ {8, 16, 128, 128, deflate_slow}, 67834768Speter/* 7 */ {8, 32, 128, 256, deflate_slow}, 67934768Speter/* 8 */ {32, 128, 258, 1024, deflate_slow}, 68034768Speter/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ 68128415Speter 68228415Speter/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 68328415Speter * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 68428415Speter * meaning. 68528415Speter */ 68628415Speter 68728415Speter#define EQUAL 0 68828415Speter/* result of memcmp for equal strings */ 68928415Speter 69034768Speter#ifndef NO_DUMMY_DECL 69134768Speterstruct static_tree_desc_s {int dummy;}; /* for buggy compilers */ 69228415Speter#endif 69328415Speter 69428415Speter/* =========================================================================== 69528415Speter * Update a hash value with the given input byte 69628415Speter * IN assertion: all calls to to UPDATE_HASH are made with consecutive 69728415Speter * input characters, so that a running hash key can be computed from the 69828415Speter * previous key instead of complete recalculation each time. 69928415Speter */ 70028415Speter#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 70128415Speter 70228415Speter 70328415Speter/* =========================================================================== 70428415Speter * Insert string str in the dictionary and set match_head to the previous head 70528415Speter * of the hash chain (the most recent string with same hash key). Return 70628415Speter * the previous length of the hash chain. 70728415Speter * IN assertion: all calls to to INSERT_STRING are made with consecutive 70828415Speter * input characters and the first MIN_MATCH bytes of str are valid 70928415Speter * (except for the last MIN_MATCH-1 bytes of the input file). 71028415Speter */ 71128415Speter#define INSERT_STRING(s, str, match_head) \ 71228415Speter (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 71328415Speter s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ 71434768Speter s->head[s->ins_h] = (Pos)(str)) 71528415Speter 71628415Speter/* =========================================================================== 71728415Speter * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 71828415Speter * prev[] will be initialized on the fly. 71928415Speter */ 72028415Speter#define CLEAR_HASH(s) \ 72128415Speter s->head[s->hash_size-1] = NIL; \ 72228415Speter zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 72328415Speter 72428415Speter/* ========================================================================= */ 72534768Speterint deflateInit_(strm, level, version, stream_size) 72634768Speter z_streamp strm; 72728415Speter int level; 72834768Speter const char *version; 72934768Speter int stream_size; 73028415Speter{ 73134768Speter return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 73234768Speter Z_DEFAULT_STRATEGY, version, stream_size); 73328415Speter /* To do: ignore strm->next_in if we use it as window */ 73428415Speter} 73528415Speter 73628415Speter/* ========================================================================= */ 73734768Speterint deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 73834768Speter version, stream_size) 73934768Speter z_streamp strm; 74028415Speter int level; 74128415Speter int method; 74228415Speter int windowBits; 74328415Speter int memLevel; 74428415Speter int strategy; 74534768Speter const char *version; 74634768Speter int stream_size; 74728415Speter{ 74828415Speter deflate_state *s; 74928415Speter int noheader = 0; 75034768Speter static char* my_version = ZLIB_VERSION; 75128415Speter 75234768Speter ushf *overlay; 75334768Speter /* We overlay pending_buf and d_buf+l_buf. This works since the average 75434768Speter * output size for (length,distance) codes is <= 24 bits. 75534768Speter */ 75634768Speter 75734768Speter if (version == Z_NULL || version[0] != my_version[0] || 75834768Speter stream_size != sizeof(z_stream)) { 75934768Speter return Z_VERSION_ERROR; 76034768Speter } 76128415Speter if (strm == Z_NULL) return Z_STREAM_ERROR; 76228415Speter 76328415Speter strm->msg = Z_NULL; 76434768Speter#ifndef NO_ZCFUNCS 76534768Speter if (strm->zalloc == Z_NULL) { 76634768Speter strm->zalloc = zcalloc; 76734768Speter strm->opaque = (voidpf)0; 76834768Speter } 76934768Speter if (strm->zfree == Z_NULL) strm->zfree = zcfree; 77034768Speter#endif 77128415Speter 77228415Speter if (level == Z_DEFAULT_COMPRESSION) level = 6; 77328415Speter 77428415Speter if (windowBits < 0) { /* undocumented feature: suppress zlib header */ 77528415Speter noheader = 1; 77628415Speter windowBits = -windowBits; 77728415Speter } 77834768Speter if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 77934768Speter windowBits < 8 || windowBits > 15 || level < 0 || level > 9 || 78034768Speter strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 78128415Speter return Z_STREAM_ERROR; 78228415Speter } 78334768Speter s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 78428415Speter if (s == Z_NULL) return Z_MEM_ERROR; 78528415Speter strm->state = (struct internal_state FAR *)s; 78628415Speter s->strm = strm; 78728415Speter 78828415Speter s->noheader = noheader; 78928415Speter s->w_bits = windowBits; 79028415Speter s->w_size = 1 << s->w_bits; 79128415Speter s->w_mask = s->w_size - 1; 79228415Speter 79328415Speter s->hash_bits = memLevel + 7; 79428415Speter s->hash_size = 1 << s->hash_bits; 79528415Speter s->hash_mask = s->hash_size - 1; 79628415Speter s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 79728415Speter 79834768Speter s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 79934768Speter s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 80034768Speter s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 80128415Speter 80228415Speter s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 80328415Speter 80434768Speter overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 80534768Speter s->pending_buf = (uchf *) overlay; 80634768Speter s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 80728415Speter 80828415Speter if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 80928415Speter s->pending_buf == Z_NULL) { 81043305Sdillon strm->msg = (const char*)ERR_MSG(Z_MEM_ERROR); 81128415Speter deflateEnd (strm); 81228415Speter return Z_MEM_ERROR; 81328415Speter } 81434768Speter s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 81534768Speter s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 81628415Speter 81728415Speter s->level = level; 81828415Speter s->strategy = strategy; 81928415Speter s->method = (Byte)method; 82028415Speter 82128415Speter return deflateReset(strm); 82228415Speter} 82328415Speter 82428415Speter/* ========================================================================= */ 82534768Speterint deflateSetDictionary (strm, dictionary, dictLength) 82634768Speter z_streamp strm; 82734768Speter const Bytef *dictionary; 82834768Speter uInt dictLength; 82934768Speter{ 83034768Speter deflate_state *s; 83134768Speter uInt length = dictLength; 83234768Speter uInt n; 83334768Speter IPos hash_head = 0; 83434768Speter 83534768Speter if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL) 83634768Speter return Z_STREAM_ERROR; 83734768Speter 83834768Speter s = (deflate_state *) strm->state; 83934768Speter if (s->status != INIT_STATE) return Z_STREAM_ERROR; 84034768Speter 84134768Speter strm->adler = adler32(strm->adler, dictionary, dictLength); 84234768Speter 84334768Speter if (length < MIN_MATCH) return Z_OK; 84434768Speter if (length > MAX_DIST(s)) { 84534768Speter length = MAX_DIST(s); 84634768Speter#ifndef USE_DICT_HEAD 84734768Speter dictionary += dictLength - length; /* use the tail of the dictionary */ 84834768Speter#endif 84934768Speter } 85034768Speter zmemcpy((charf *)s->window, dictionary, length); 85134768Speter s->strstart = length; 85234768Speter s->block_start = (long)length; 85334768Speter 85434768Speter /* Insert all strings in the hash table (except for the last two bytes). 85534768Speter * s->lookahead stays null, so s->ins_h will be recomputed at the next 85634768Speter * call of fill_window. 85734768Speter */ 85834768Speter s->ins_h = s->window[0]; 85934768Speter UPDATE_HASH(s, s->ins_h, s->window[1]); 86034768Speter for (n = 0; n <= length - MIN_MATCH; n++) { 86134768Speter INSERT_STRING(s, n, hash_head); 86234768Speter } 86334768Speter if (hash_head) hash_head = 0; /* to make compiler happy */ 86434768Speter return Z_OK; 86534768Speter} 86634768Speter 86734768Speter/* ========================================================================= */ 86828415Speterint deflateReset (strm) 86934768Speter z_streamp strm; 87028415Speter{ 87128415Speter deflate_state *s; 87228415Speter 87328415Speter if (strm == Z_NULL || strm->state == Z_NULL || 87434768Speter strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR; 87528415Speter 87628415Speter strm->total_in = strm->total_out = 0; 87728415Speter strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 87828415Speter strm->data_type = Z_UNKNOWN; 87928415Speter 88028415Speter s = (deflate_state *)strm->state; 88128415Speter s->pending = 0; 88228415Speter s->pending_out = s->pending_buf; 88328415Speter 88428415Speter if (s->noheader < 0) { 88528415Speter s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */ 88628415Speter } 88728415Speter s->status = s->noheader ? BUSY_STATE : INIT_STATE; 88834768Speter strm->adler = 1; 88934768Speter s->last_flush = Z_NO_FLUSH; 89028415Speter 89134768Speter _tr_init(s); 89228415Speter lm_init(s); 89328415Speter 89428415Speter return Z_OK; 89528415Speter} 89628415Speter 89734768Speter/* ========================================================================= */ 89834768Speterint deflateParams(strm, level, strategy) 89934768Speter z_streamp strm; 90034768Speter int level; 90134768Speter int strategy; 90234768Speter{ 90334768Speter deflate_state *s; 90434768Speter compress_func func; 90534768Speter int err = Z_OK; 90634768Speter 90734768Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 90834768Speter s = (deflate_state *) strm->state; 90934768Speter 91034768Speter if (level == Z_DEFAULT_COMPRESSION) { 91134768Speter level = 6; 91234768Speter } 91334768Speter if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 91434768Speter return Z_STREAM_ERROR; 91534768Speter } 91634768Speter func = configuration_table[s->level].func; 91734768Speter 91834768Speter if (func != configuration_table[level].func && strm->total_in != 0) { 91934768Speter /* Flush the last buffer: */ 92034768Speter err = deflate(strm, Z_PARTIAL_FLUSH); 92134768Speter } 92234768Speter if (s->level != level) { 92334768Speter s->level = level; 92434768Speter s->max_lazy_match = configuration_table[level].max_lazy; 92534768Speter s->good_match = configuration_table[level].good_length; 92634768Speter s->nice_match = configuration_table[level].nice_length; 92734768Speter s->max_chain_length = configuration_table[level].max_chain; 92834768Speter } 92934768Speter s->strategy = strategy; 93034768Speter return err; 93134768Speter} 93234768Speter 93328415Speter/* ========================================================================= 93428415Speter * Put a short in the pending buffer. The 16-bit value is put in MSB order. 93528415Speter * IN assertion: the stream state is correct and there is enough room in 93628415Speter * pending_buf. 93728415Speter */ 93828415Speterlocal void putShortMSB (s, b) 93928415Speter deflate_state *s; 94028415Speter uInt b; 94128415Speter{ 94228415Speter put_byte(s, (Byte)(b >> 8)); 94328415Speter put_byte(s, (Byte)(b & 0xff)); 94428415Speter} 94528415Speter 94628415Speter/* ========================================================================= 94734768Speter * Flush as much pending output as possible. All deflate() output goes 94834768Speter * through this function so some applications may wish to modify it 94934768Speter * to avoid allocating a large strm->next_out buffer and copying into it. 95034768Speter * (See also read_buf()). 95128415Speter */ 95228415Speterlocal void flush_pending(strm) 95334768Speter z_streamp strm; 95428415Speter{ 95534768Speter deflate_state *s = (deflate_state *) strm->state; 95634768Speter unsigned len = s->pending; 95728415Speter 95828415Speter if (len > strm->avail_out) len = strm->avail_out; 95928415Speter if (len == 0) return; 96028415Speter 96134768Speter if (strm->next_out != Z_NULL) { 96234768Speter zmemcpy(strm->next_out, s->pending_out, len); 96328415Speter strm->next_out += len; 96428415Speter } 96534768Speter s->pending_out += len; 96628415Speter strm->total_out += len; 96734768Speter strm->avail_out -= len; 96834768Speter s->pending -= len; 96934768Speter if (s->pending == 0) { 97034768Speter s->pending_out = s->pending_buf; 97128415Speter } 97228415Speter} 97328415Speter 97428415Speter/* ========================================================================= */ 97528415Speterint deflate (strm, flush) 97634768Speter z_streamp strm; 97728415Speter int flush; 97828415Speter{ 97934768Speter int old_flush; /* value of flush param for previous deflate call */ 98034768Speter deflate_state *s; 98128415Speter 98234768Speter if (strm == Z_NULL || strm->state == Z_NULL || 98334768Speter flush > Z_FINISH || flush < 0) { 98434768Speter return Z_STREAM_ERROR; 98534768Speter } 98634768Speter s = (deflate_state *) strm->state; 98734768Speter 98834768Speter if ((strm->next_in == Z_NULL && strm->avail_in != 0) || 98934768Speter (s->status == FINISH_STATE && flush != Z_FINISH)) { 99028415Speter ERR_RETURN(strm, Z_STREAM_ERROR); 99128415Speter } 99228415Speter if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 99328415Speter 99434768Speter s->strm = strm; /* just in case */ 99534768Speter old_flush = s->last_flush; 99634768Speter s->last_flush = flush; 99728415Speter 99828415Speter /* Write the zlib header */ 99934768Speter if (s->status == INIT_STATE) { 100028415Speter 100134768Speter uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 100234768Speter uInt level_flags = (s->level-1) >> 1; 100328415Speter 100428415Speter if (level_flags > 3) level_flags = 3; 100528415Speter header |= (level_flags << 6); 100634768Speter if (s->strstart != 0) header |= PRESET_DICT; 100728415Speter header += 31 - (header % 31); 100828415Speter 100934768Speter s->status = BUSY_STATE; 101034768Speter putShortMSB(s, header); 101134768Speter 101234768Speter /* Save the adler32 of the preset dictionary: */ 101334768Speter if (s->strstart != 0) { 101434768Speter putShortMSB(s, (uInt)(strm->adler >> 16)); 101534768Speter putShortMSB(s, (uInt)(strm->adler & 0xffff)); 101634768Speter } 101734768Speter strm->adler = 1L; 101828415Speter } 101928415Speter 102028415Speter /* Flush as much pending output as possible */ 102134768Speter if (s->pending != 0) { 102228415Speter flush_pending(strm); 102334768Speter if (strm->avail_out == 0) { 102434768Speter /* Since avail_out is 0, deflate will be called again with 102534768Speter * more output space, but possibly with both pending and 102634768Speter * avail_in equal to zero. There won't be anything to do, 102734768Speter * but this is not an error situation so make sure we 102834768Speter * return OK instead of BUF_ERROR at next call of deflate: 102934768Speter */ 103034768Speter s->last_flush = -1; 103134768Speter return Z_OK; 103234768Speter } 103328415Speter 103434768Speter /* Make sure there is something to do and avoid duplicate consecutive 103534768Speter * flushes. For repeated and useless calls with Z_FINISH, we keep 103634768Speter * returning Z_STREAM_END instead of Z_BUFF_ERROR. 103728415Speter */ 103834768Speter } else if (strm->avail_in == 0 && flush <= old_flush && 103934768Speter flush != Z_FINISH) { 104034768Speter ERR_RETURN(strm, Z_BUF_ERROR); 104128415Speter } 104228415Speter 104328415Speter /* User must not provide more input after the first FINISH: */ 104434768Speter if (s->status == FINISH_STATE && strm->avail_in != 0) { 104528415Speter ERR_RETURN(strm, Z_BUF_ERROR); 104628415Speter } 104728415Speter 104828415Speter /* Start a new block or continue the current one. 104928415Speter */ 105034768Speter if (strm->avail_in != 0 || s->lookahead != 0 || 105134768Speter (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 105234768Speter block_state bstate; 105328415Speter 105434768Speter bstate = (*(configuration_table[s->level].func))(s, flush); 105534768Speter 105634768Speter if (bstate == finish_started || bstate == finish_done) { 105734768Speter s->status = FINISH_STATE; 105828415Speter } 105934768Speter if (bstate == need_more || bstate == finish_started) { 106034768Speter if (strm->avail_out == 0) { 106134768Speter s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 106234768Speter } 106328415Speter return Z_OK; 106434768Speter /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 106534768Speter * of deflate should use the same flush parameter to make sure 106634768Speter * that the flush is complete. So we don't have to output an 106734768Speter * empty block here, this will be done at next call. This also 106834768Speter * ensures that for a very small output buffer, we emit at most 106934768Speter * one empty block. 107028415Speter */ 107134768Speter } 107234768Speter if (bstate == block_done) { 107334768Speter if (flush == Z_PARTIAL_FLUSH) { 107434768Speter _tr_align(s); 107534768Speter } else if (flush == Z_PACKET_FLUSH) { 107634768Speter /* Output just the 3-bit `stored' block type value, 107734768Speter but not a zero length. */ 107834768Speter _tr_stored_type_only(s); 107934768Speter } else { /* FULL_FLUSH or SYNC_FLUSH */ 108034768Speter _tr_stored_block(s, (char*)0, 0L, 0); 108134768Speter /* For a full flush, this empty block will be recognized 108234768Speter * as a special marker by inflate_sync(). 108334768Speter */ 108434768Speter if (flush == Z_FULL_FLUSH) { 108534768Speter CLEAR_HASH(s); /* forget history */ 108634768Speter } 108734768Speter } 108834768Speter flush_pending(strm); 108934768Speter if (strm->avail_out == 0) { 109034768Speter s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 109134768Speter return Z_OK; 109228415Speter } 109334768Speter } 109428415Speter } 109528415Speter Assert(strm->avail_out > 0, "bug2"); 109628415Speter 109728415Speter if (flush != Z_FINISH) return Z_OK; 109834768Speter if (s->noheader) return Z_STREAM_END; 109928415Speter 110028415Speter /* Write the zlib trailer (adler32) */ 110134768Speter putShortMSB(s, (uInt)(strm->adler >> 16)); 110234768Speter putShortMSB(s, (uInt)(strm->adler & 0xffff)); 110328415Speter flush_pending(strm); 110428415Speter /* If avail_out is zero, the application will call deflate again 110528415Speter * to flush the rest. 110628415Speter */ 110734768Speter s->noheader = -1; /* write the trailer only once! */ 110834768Speter return s->pending != 0 ? Z_OK : Z_STREAM_END; 110928415Speter} 111028415Speter 111128415Speter/* ========================================================================= */ 111228415Speterint deflateEnd (strm) 111334768Speter z_streamp strm; 111428415Speter{ 111534768Speter int status; 111634768Speter deflate_state *s; 111728415Speter 111834768Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 111934768Speter s = (deflate_state *) strm->state; 112028415Speter 112134768Speter status = s->status; 112234768Speter if (status != INIT_STATE && status != BUSY_STATE && 112334768Speter status != FINISH_STATE) { 112434768Speter return Z_STREAM_ERROR; 112534768Speter } 112628415Speter 112734768Speter /* Deallocate in reverse order of allocations: */ 112834768Speter TRY_FREE(strm, s->pending_buf); 112934768Speter TRY_FREE(strm, s->head); 113034768Speter TRY_FREE(strm, s->prev); 113134768Speter TRY_FREE(strm, s->window); 113234768Speter 113334768Speter ZFREE(strm, s); 113428415Speter strm->state = Z_NULL; 113528415Speter 113634768Speter return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 113734768Speter} 113834768Speter 113934768Speter/* ========================================================================= 114034768Speter * Copy the source state to the destination state. 114134768Speter */ 114234768Speterint deflateCopy (dest, source) 114334768Speter z_streamp dest; 114434768Speter z_streamp source; 114534768Speter{ 114634768Speter deflate_state *ds; 114734768Speter deflate_state *ss; 114834768Speter ushf *overlay; 114934768Speter 115034768Speter if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) 115134768Speter return Z_STREAM_ERROR; 115234768Speter ss = (deflate_state *) source->state; 115334768Speter 115437065Speter zmemcpy(dest, source, sizeof(*dest)); 115534768Speter 115634768Speter ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 115734768Speter if (ds == Z_NULL) return Z_MEM_ERROR; 115834768Speter dest->state = (struct internal_state FAR *) ds; 115937065Speter zmemcpy(ds, ss, sizeof(*ds)); 116034768Speter ds->strm = dest; 116134768Speter 116234768Speter ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 116334768Speter ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 116434768Speter ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 116534768Speter overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 116634768Speter ds->pending_buf = (uchf *) overlay; 116734768Speter 116834768Speter if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 116934768Speter ds->pending_buf == Z_NULL) { 117034768Speter deflateEnd (dest); 117134768Speter return Z_MEM_ERROR; 117234768Speter } 117334768Speter /* ??? following zmemcpy doesn't work for 16-bit MSDOS */ 117434768Speter zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 117534768Speter zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); 117634768Speter zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); 117734768Speter zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 117834768Speter 117934768Speter ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 118034768Speter ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 118134768Speter ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 118234768Speter 118334768Speter ds->l_desc.dyn_tree = ds->dyn_ltree; 118434768Speter ds->d_desc.dyn_tree = ds->dyn_dtree; 118534768Speter ds->bl_desc.dyn_tree = ds->bl_tree; 118634768Speter 118728415Speter return Z_OK; 118828415Speter} 118928415Speter 119028415Speter/* =========================================================================== 119134768Speter * Return the number of bytes of output which are immediately available 119234768Speter * for output from the decompressor. 119334768Speter */ 119434768Speterint deflateOutputPending (strm) 119534768Speter z_streamp strm; 119634768Speter{ 119734768Speter if (strm == Z_NULL || strm->state == Z_NULL) return 0; 119834768Speter 119934768Speter return ((deflate_state *)(strm->state))->pending; 120034768Speter} 120134768Speter 120234768Speter/* =========================================================================== 120328415Speter * Read a new buffer from the current input stream, update the adler32 120434768Speter * and total number of bytes read. All deflate() input goes through 120534768Speter * this function so some applications may wish to modify it to avoid 120634768Speter * allocating a large strm->next_in buffer and copying from it. 120734768Speter * (See also flush_pending()). 120828415Speter */ 120928415Speterlocal int read_buf(strm, buf, size) 121034768Speter z_streamp strm; 121128415Speter charf *buf; 121228415Speter unsigned size; 121328415Speter{ 121428415Speter unsigned len = strm->avail_in; 121528415Speter 121628415Speter if (len > size) len = size; 121728415Speter if (len == 0) return 0; 121828415Speter 121928415Speter strm->avail_in -= len; 122028415Speter 122134768Speter if (!((deflate_state *)(strm->state))->noheader) { 122234768Speter strm->adler = adler32(strm->adler, strm->next_in, len); 122328415Speter } 122428415Speter zmemcpy(buf, strm->next_in, len); 122528415Speter strm->next_in += len; 122628415Speter strm->total_in += len; 122728415Speter 122828415Speter return (int)len; 122928415Speter} 123028415Speter 123128415Speter/* =========================================================================== 123228415Speter * Initialize the "longest match" routines for a new zlib stream 123328415Speter */ 123428415Speterlocal void lm_init (s) 123528415Speter deflate_state *s; 123628415Speter{ 123728415Speter s->window_size = (ulg)2L*s->w_size; 123828415Speter 123928415Speter CLEAR_HASH(s); 124028415Speter 124128415Speter /* Set the default configuration parameters: 124228415Speter */ 124328415Speter s->max_lazy_match = configuration_table[s->level].max_lazy; 124428415Speter s->good_match = configuration_table[s->level].good_length; 124528415Speter s->nice_match = configuration_table[s->level].nice_length; 124628415Speter s->max_chain_length = configuration_table[s->level].max_chain; 124728415Speter 124828415Speter s->strstart = 0; 124928415Speter s->block_start = 0L; 125028415Speter s->lookahead = 0; 125134768Speter s->match_length = s->prev_length = MIN_MATCH-1; 125228415Speter s->match_available = 0; 125328415Speter s->ins_h = 0; 125428415Speter#ifdef ASMV 125528415Speter match_init(); /* initialize the asm code */ 125628415Speter#endif 125728415Speter} 125828415Speter 125928415Speter/* =========================================================================== 126028415Speter * Set match_start to the longest match starting at the given string and 126128415Speter * return its length. Matches shorter or equal to prev_length are discarded, 126228415Speter * in which case the result is equal to prev_length and match_start is 126328415Speter * garbage. 126428415Speter * IN assertions: cur_match is the head of the hash chain for the current 126528415Speter * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 126634768Speter * OUT assertion: the match length is not greater than s->lookahead. 126728415Speter */ 126828415Speter#ifndef ASMV 126928415Speter/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 127028415Speter * match.S. The code will be functionally equivalent. 127128415Speter */ 127234768Speterlocal uInt longest_match(s, cur_match) 127328415Speter deflate_state *s; 127428415Speter IPos cur_match; /* current match */ 127528415Speter{ 127628415Speter unsigned chain_length = s->max_chain_length;/* max hash chain length */ 127728415Speter register Bytef *scan = s->window + s->strstart; /* current string */ 127828415Speter register Bytef *match; /* matched string */ 127928415Speter register int len; /* length of current match */ 128028415Speter int best_len = s->prev_length; /* best match length so far */ 128134768Speter int nice_match = s->nice_match; /* stop if match long enough */ 128228415Speter IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 128328415Speter s->strstart - (IPos)MAX_DIST(s) : NIL; 128428415Speter /* Stop when cur_match becomes <= limit. To simplify the code, 128528415Speter * we prevent matches with the string of window index 0. 128628415Speter */ 128728415Speter Posf *prev = s->prev; 128828415Speter uInt wmask = s->w_mask; 128928415Speter 129028415Speter#ifdef UNALIGNED_OK 129128415Speter /* Compare two bytes at a time. Note: this is not always beneficial. 129228415Speter * Try with and without -DUNALIGNED_OK to check. 129328415Speter */ 129428415Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 129528415Speter register ush scan_start = *(ushf*)scan; 129628415Speter register ush scan_end = *(ushf*)(scan+best_len-1); 129728415Speter#else 129828415Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH; 129928415Speter register Byte scan_end1 = scan[best_len-1]; 130028415Speter register Byte scan_end = scan[best_len]; 130128415Speter#endif 130228415Speter 130328415Speter /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 130428415Speter * It is easy to get rid of this optimization if necessary. 130528415Speter */ 130628415Speter Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 130728415Speter 130828415Speter /* Do not waste too much time if we already have a good match: */ 130928415Speter if (s->prev_length >= s->good_match) { 131028415Speter chain_length >>= 2; 131128415Speter } 131234768Speter /* Do not look for matches beyond the end of the input. This is necessary 131334768Speter * to make deflate deterministic. 131434768Speter */ 131534768Speter if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 131634768Speter 131728415Speter Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 131828415Speter 131928415Speter do { 132028415Speter Assert(cur_match < s->strstart, "no future"); 132128415Speter match = s->window + cur_match; 132228415Speter 132328415Speter /* Skip to next match if the match length cannot increase 132428415Speter * or if the match length is less than 2: 132528415Speter */ 132628415Speter#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 132728415Speter /* This code assumes sizeof(unsigned short) == 2. Do not use 132828415Speter * UNALIGNED_OK if your compiler uses a different size. 132928415Speter */ 133028415Speter if (*(ushf*)(match+best_len-1) != scan_end || 133128415Speter *(ushf*)match != scan_start) continue; 133228415Speter 133328415Speter /* It is not necessary to compare scan[2] and match[2] since they are 133428415Speter * always equal when the other bytes match, given that the hash keys 133528415Speter * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 133628415Speter * strstart+3, +5, ... up to strstart+257. We check for insufficient 133728415Speter * lookahead only every 4th comparison; the 128th check will be made 133828415Speter * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 133928415Speter * necessary to put more guard bytes at the end of the window, or 134028415Speter * to check more often for insufficient lookahead. 134128415Speter */ 134228415Speter Assert(scan[2] == match[2], "scan[2]?"); 134328415Speter scan++, match++; 134428415Speter do { 134528415Speter } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 134628415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 134728415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 134828415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 134928415Speter scan < strend); 135028415Speter /* The funny "do {}" generates better code on most compilers */ 135128415Speter 135228415Speter /* Here, scan <= window+strstart+257 */ 135328415Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 135428415Speter if (*scan == *match) scan++; 135528415Speter 135628415Speter len = (MAX_MATCH - 1) - (int)(strend-scan); 135728415Speter scan = strend - (MAX_MATCH-1); 135828415Speter 135928415Speter#else /* UNALIGNED_OK */ 136028415Speter 136128415Speter if (match[best_len] != scan_end || 136228415Speter match[best_len-1] != scan_end1 || 136328415Speter *match != *scan || 136428415Speter *++match != scan[1]) continue; 136528415Speter 136628415Speter /* The check at best_len-1 can be removed because it will be made 136728415Speter * again later. (This heuristic is not always a win.) 136828415Speter * It is not necessary to compare scan[2] and match[2] since they 136928415Speter * are always equal when the other bytes match, given that 137028415Speter * the hash keys are equal and that HASH_BITS >= 8. 137128415Speter */ 137228415Speter scan += 2, match++; 137328415Speter Assert(*scan == *match, "match[2]?"); 137428415Speter 137528415Speter /* We check for insufficient lookahead only every 8th comparison; 137628415Speter * the 256th check will be made at strstart+258. 137728415Speter */ 137828415Speter do { 137928415Speter } while (*++scan == *++match && *++scan == *++match && 138028415Speter *++scan == *++match && *++scan == *++match && 138128415Speter *++scan == *++match && *++scan == *++match && 138228415Speter *++scan == *++match && *++scan == *++match && 138328415Speter scan < strend); 138428415Speter 138528415Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 138628415Speter 138728415Speter len = MAX_MATCH - (int)(strend - scan); 138828415Speter scan = strend - MAX_MATCH; 138928415Speter 139028415Speter#endif /* UNALIGNED_OK */ 139128415Speter 139228415Speter if (len > best_len) { 139328415Speter s->match_start = cur_match; 139428415Speter best_len = len; 139534768Speter if (len >= nice_match) break; 139628415Speter#ifdef UNALIGNED_OK 139728415Speter scan_end = *(ushf*)(scan+best_len-1); 139828415Speter#else 139928415Speter scan_end1 = scan[best_len-1]; 140028415Speter scan_end = scan[best_len]; 140128415Speter#endif 140228415Speter } 140328415Speter } while ((cur_match = prev[cur_match & wmask]) > limit 140428415Speter && --chain_length != 0); 140528415Speter 140634768Speter if ((uInt)best_len <= s->lookahead) return best_len; 140734768Speter return s->lookahead; 140828415Speter} 140928415Speter#endif /* ASMV */ 141028415Speter 141128415Speter#ifdef DEBUG_ZLIB 141228415Speter/* =========================================================================== 141328415Speter * Check that the match at match_start is indeed a match. 141428415Speter */ 141528415Speterlocal void check_match(s, start, match, length) 141628415Speter deflate_state *s; 141728415Speter IPos start, match; 141828415Speter int length; 141928415Speter{ 142028415Speter /* check that the match is indeed a match */ 142134768Speter if (zmemcmp((charf *)s->window + match, 142228415Speter (charf *)s->window + start, length) != EQUAL) { 142334768Speter fprintf(stderr, " start %u, match %u, length %d\n", 142434768Speter start, match, length); 142534768Speter do { 142634768Speter fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 142734768Speter } while (--length != 0); 142828415Speter z_error("invalid match"); 142928415Speter } 143034768Speter if (z_verbose > 1) { 143128415Speter fprintf(stderr,"\\[%d,%d]", start-match, length); 143228415Speter do { putc(s->window[start++], stderr); } while (--length != 0); 143328415Speter } 143428415Speter} 143528415Speter#else 143628415Speter# define check_match(s, start, match, length) 143728415Speter#endif 143828415Speter 143928415Speter/* =========================================================================== 144028415Speter * Fill the window when the lookahead becomes insufficient. 144128415Speter * Updates strstart and lookahead. 144228415Speter * 144328415Speter * IN assertion: lookahead < MIN_LOOKAHEAD 144428415Speter * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 144528415Speter * At least one byte has been read, or avail_in == 0; reads are 144628415Speter * performed for at least two bytes (required for the zip translate_eol 144728415Speter * option -- not supported here). 144828415Speter */ 144928415Speterlocal void fill_window(s) 145028415Speter deflate_state *s; 145128415Speter{ 145228415Speter register unsigned n, m; 145328415Speter register Posf *p; 145428415Speter unsigned more; /* Amount of free space at the end of the window. */ 145528415Speter uInt wsize = s->w_size; 145628415Speter 145728415Speter do { 145828415Speter more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 145928415Speter 146028415Speter /* Deal with !@#$% 64K limit: */ 146128415Speter if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 146228415Speter more = wsize; 146334768Speter 146428415Speter } else if (more == (unsigned)(-1)) { 146528415Speter /* Very unlikely, but possible on 16 bit machine if strstart == 0 146628415Speter * and lookahead == 1 (input done one byte at time) 146728415Speter */ 146828415Speter more--; 146928415Speter 147028415Speter /* If the window is almost full and there is insufficient lookahead, 147128415Speter * move the upper half to the lower one to make room in the upper half. 147228415Speter */ 147328415Speter } else if (s->strstart >= wsize+MAX_DIST(s)) { 147428415Speter 147528415Speter zmemcpy((charf *)s->window, (charf *)s->window+wsize, 147628415Speter (unsigned)wsize); 147728415Speter s->match_start -= wsize; 147828415Speter s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 147928415Speter s->block_start -= (long) wsize; 148028415Speter 148128415Speter /* Slide the hash table (could be avoided with 32 bit values 148234768Speter at the expense of memory usage). We slide even when level == 0 148334768Speter to keep the hash table consistent if we switch back to level > 0 148434768Speter later. (Using level 0 permanently is not an optimal usage of 148534768Speter zlib, so we don't care about this pathological case.) 148628415Speter */ 148728415Speter n = s->hash_size; 148828415Speter p = &s->head[n]; 148928415Speter do { 149028415Speter m = *--p; 149128415Speter *p = (Pos)(m >= wsize ? m-wsize : NIL); 149228415Speter } while (--n); 149328415Speter 149428415Speter n = wsize; 149528415Speter p = &s->prev[n]; 149628415Speter do { 149728415Speter m = *--p; 149828415Speter *p = (Pos)(m >= wsize ? m-wsize : NIL); 149928415Speter /* If n is not on any hash chain, prev[n] is garbage but 150028415Speter * its value will never be used. 150128415Speter */ 150228415Speter } while (--n); 150328415Speter more += wsize; 150428415Speter } 150528415Speter if (s->strm->avail_in == 0) return; 150628415Speter 150728415Speter /* If there was no sliding: 150828415Speter * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 150928415Speter * more == window_size - lookahead - strstart 151028415Speter * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 151128415Speter * => more >= window_size - 2*WSIZE + 2 151228415Speter * In the BIG_MEM or MMAP case (not yet supported), 151328415Speter * window_size == input_size + MIN_LOOKAHEAD && 151428415Speter * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 151528415Speter * Otherwise, window_size == 2*WSIZE so more >= 2. 151628415Speter * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 151728415Speter */ 151828415Speter Assert(more >= 2, "more < 2"); 151928415Speter 152028415Speter n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead, 152128415Speter more); 152228415Speter s->lookahead += n; 152328415Speter 152428415Speter /* Initialize the hash value now that we have some input: */ 152528415Speter if (s->lookahead >= MIN_MATCH) { 152628415Speter s->ins_h = s->window[s->strstart]; 152728415Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 152828415Speter#if MIN_MATCH != 3 152928415Speter Call UPDATE_HASH() MIN_MATCH-3 more times 153028415Speter#endif 153128415Speter } 153228415Speter /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 153328415Speter * but this is not important since only literal bytes will be emitted. 153428415Speter */ 153528415Speter 153628415Speter } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 153728415Speter} 153828415Speter 153928415Speter/* =========================================================================== 154028415Speter * Flush the current block, with given end-of-file flag. 154128415Speter * IN assertion: strstart is set to the end of the current match. 154228415Speter */ 154334768Speter#define FLUSH_BLOCK_ONLY(s, eof) { \ 154434768Speter _tr_flush_block(s, (s->block_start >= 0L ? \ 154534768Speter (charf *)&s->window[(unsigned)s->block_start] : \ 154634768Speter (charf *)Z_NULL), \ 154734768Speter (ulg)((long)s->strstart - s->block_start), \ 154834768Speter (eof)); \ 154928415Speter s->block_start = s->strstart; \ 155028415Speter flush_pending(s->strm); \ 155128415Speter Tracev((stderr,"[FLUSH]")); \ 155228415Speter} 155328415Speter 155428415Speter/* Same but force premature exit if necessary. */ 155534768Speter#define FLUSH_BLOCK(s, eof) { \ 155634768Speter FLUSH_BLOCK_ONLY(s, eof); \ 155734768Speter if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ 155828415Speter} 155928415Speter 156028415Speter/* =========================================================================== 156134768Speter * Copy without compression as much as possible from the input stream, return 156234768Speter * the current block state. 156334768Speter * This function does not insert new strings in the dictionary since 156434768Speter * uncompressible data is probably not useful. This function is used 156534768Speter * only for the level=0 compression option. 156634768Speter * NOTE: this function should be optimized to avoid extra copying from 156734768Speter * window to pending_buf. 156834768Speter */ 156934768Speterlocal block_state deflate_stored(s, flush) 157034768Speter deflate_state *s; 157134768Speter int flush; 157234768Speter{ 157334768Speter /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 157434768Speter * to pending_buf_size, and each stored block has a 5 byte header: 157534768Speter */ 157634768Speter ulg max_block_size = 0xffff; 157734768Speter ulg max_start; 157834768Speter 157934768Speter if (max_block_size > s->pending_buf_size - 5) { 158034768Speter max_block_size = s->pending_buf_size - 5; 158134768Speter } 158234768Speter 158334768Speter /* Copy as much as possible from input to output: */ 158434768Speter for (;;) { 158534768Speter /* Fill the window as much as possible: */ 158634768Speter if (s->lookahead <= 1) { 158734768Speter 158834768Speter Assert(s->strstart < s->w_size+MAX_DIST(s) || 158934768Speter s->block_start >= (long)s->w_size, "slide too late"); 159034768Speter 159134768Speter fill_window(s); 159234768Speter if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 159334768Speter 159434768Speter if (s->lookahead == 0) break; /* flush the current block */ 159534768Speter } 159634768Speter Assert(s->block_start >= 0L, "block gone"); 159734768Speter 159834768Speter s->strstart += s->lookahead; 159934768Speter s->lookahead = 0; 160034768Speter 160134768Speter /* Emit a stored block if pending_buf will be full: */ 160234768Speter max_start = s->block_start + max_block_size; 160334768Speter if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 160434768Speter /* strstart == 0 is possible when wraparound on 16-bit machine */ 160534768Speter s->lookahead = (uInt)(s->strstart - max_start); 160634768Speter s->strstart = (uInt)max_start; 160734768Speter FLUSH_BLOCK(s, 0); 160834768Speter } 160934768Speter /* Flush if we may have to slide, otherwise block_start may become 161034768Speter * negative and the data will be gone: 161134768Speter */ 161234768Speter if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 161334768Speter FLUSH_BLOCK(s, 0); 161434768Speter } 161534768Speter } 161634768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 161734768Speter return flush == Z_FINISH ? finish_done : block_done; 161834768Speter} 161934768Speter 162034768Speter/* =========================================================================== 162134768Speter * Compress as much as possible from the input stream, return the current 162234768Speter * block state. 162334768Speter * This function does not perform lazy evaluation of matches and inserts 162428415Speter * new strings in the dictionary only for unmatched strings or for short 162528415Speter * matches. It is used only for the fast compression options. 162628415Speter */ 162734768Speterlocal block_state deflate_fast(s, flush) 162828415Speter deflate_state *s; 162928415Speter int flush; 163028415Speter{ 163128415Speter IPos hash_head = NIL; /* head of the hash chain */ 163234768Speter int bflush; /* set if current block must be flushed */ 163328415Speter 163428415Speter for (;;) { 163528415Speter /* Make sure that we always have enough lookahead, except 163628415Speter * at the end of the input file. We need MAX_MATCH bytes 163728415Speter * for the next match, plus MIN_MATCH bytes to insert the 163828415Speter * string following the next match. 163928415Speter */ 164028415Speter if (s->lookahead < MIN_LOOKAHEAD) { 164128415Speter fill_window(s); 164234768Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 164334768Speter return need_more; 164434768Speter } 164528415Speter if (s->lookahead == 0) break; /* flush the current block */ 164628415Speter } 164728415Speter 164828415Speter /* Insert the string window[strstart .. strstart+2] in the 164928415Speter * dictionary, and set hash_head to the head of the hash chain: 165028415Speter */ 165128415Speter if (s->lookahead >= MIN_MATCH) { 165228415Speter INSERT_STRING(s, s->strstart, hash_head); 165328415Speter } 165428415Speter 165528415Speter /* Find the longest match, discarding those <= prev_length. 165628415Speter * At this point we have always match_length < MIN_MATCH 165728415Speter */ 165828415Speter if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 165928415Speter /* To simplify the code, we prevent matches with the string 166028415Speter * of window index 0 (in particular we have to avoid a match 166128415Speter * of the string with itself at the start of the input file). 166228415Speter */ 166328415Speter if (s->strategy != Z_HUFFMAN_ONLY) { 166428415Speter s->match_length = longest_match (s, hash_head); 166528415Speter } 166628415Speter /* longest_match() sets match_start */ 166728415Speter } 166828415Speter if (s->match_length >= MIN_MATCH) { 166928415Speter check_match(s, s->strstart, s->match_start, s->match_length); 167028415Speter 167134768Speter bflush = _tr_tally(s, s->strstart - s->match_start, 167234768Speter s->match_length - MIN_MATCH); 167328415Speter 167428415Speter s->lookahead -= s->match_length; 167528415Speter 167628415Speter /* Insert new strings in the hash table only if the match length 167728415Speter * is not too large. This saves time but degrades compression. 167828415Speter */ 167928415Speter if (s->match_length <= s->max_insert_length && 168028415Speter s->lookahead >= MIN_MATCH) { 168128415Speter s->match_length--; /* string at strstart already in hash table */ 168228415Speter do { 168328415Speter s->strstart++; 168428415Speter INSERT_STRING(s, s->strstart, hash_head); 168528415Speter /* strstart never exceeds WSIZE-MAX_MATCH, so there are 168628415Speter * always MIN_MATCH bytes ahead. 168728415Speter */ 168828415Speter } while (--s->match_length != 0); 168928415Speter s->strstart++; 169028415Speter } else { 169128415Speter s->strstart += s->match_length; 169228415Speter s->match_length = 0; 169328415Speter s->ins_h = s->window[s->strstart]; 169428415Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 169528415Speter#if MIN_MATCH != 3 169628415Speter Call UPDATE_HASH() MIN_MATCH-3 more times 169728415Speter#endif 169828415Speter /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 169928415Speter * matter since it will be recomputed at next deflate call. 170028415Speter */ 170128415Speter } 170228415Speter } else { 170328415Speter /* No match, output a literal byte */ 170428415Speter Tracevv((stderr,"%c", s->window[s->strstart])); 170534768Speter bflush = _tr_tally (s, 0, s->window[s->strstart]); 170628415Speter s->lookahead--; 170728415Speter s->strstart++; 170828415Speter } 170934768Speter if (bflush) FLUSH_BLOCK(s, 0); 171028415Speter } 171134768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 171234768Speter return flush == Z_FINISH ? finish_done : block_done; 171328415Speter} 171428415Speter 171528415Speter/* =========================================================================== 171628415Speter * Same as above, but achieves better compression. We use a lazy 171728415Speter * evaluation for matches: a match is finally adopted only if there is 171828415Speter * no better match at the next window position. 171928415Speter */ 172034768Speterlocal block_state deflate_slow(s, flush) 172128415Speter deflate_state *s; 172228415Speter int flush; 172328415Speter{ 172428415Speter IPos hash_head = NIL; /* head of hash chain */ 172528415Speter int bflush; /* set if current block must be flushed */ 172628415Speter 172728415Speter /* Process the input block. */ 172828415Speter for (;;) { 172928415Speter /* Make sure that we always have enough lookahead, except 173028415Speter * at the end of the input file. We need MAX_MATCH bytes 173128415Speter * for the next match, plus MIN_MATCH bytes to insert the 173228415Speter * string following the next match. 173328415Speter */ 173428415Speter if (s->lookahead < MIN_LOOKAHEAD) { 173528415Speter fill_window(s); 173634768Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 173734768Speter return need_more; 173834768Speter } 173928415Speter if (s->lookahead == 0) break; /* flush the current block */ 174028415Speter } 174128415Speter 174228415Speter /* Insert the string window[strstart .. strstart+2] in the 174328415Speter * dictionary, and set hash_head to the head of the hash chain: 174428415Speter */ 174528415Speter if (s->lookahead >= MIN_MATCH) { 174628415Speter INSERT_STRING(s, s->strstart, hash_head); 174728415Speter } 174828415Speter 174928415Speter /* Find the longest match, discarding those <= prev_length. 175028415Speter */ 175128415Speter s->prev_length = s->match_length, s->prev_match = s->match_start; 175228415Speter s->match_length = MIN_MATCH-1; 175328415Speter 175428415Speter if (hash_head != NIL && s->prev_length < s->max_lazy_match && 175528415Speter s->strstart - hash_head <= MAX_DIST(s)) { 175628415Speter /* To simplify the code, we prevent matches with the string 175728415Speter * of window index 0 (in particular we have to avoid a match 175828415Speter * of the string with itself at the start of the input file). 175928415Speter */ 176028415Speter if (s->strategy != Z_HUFFMAN_ONLY) { 176128415Speter s->match_length = longest_match (s, hash_head); 176228415Speter } 176328415Speter /* longest_match() sets match_start */ 176428415Speter 176528415Speter if (s->match_length <= 5 && (s->strategy == Z_FILTERED || 176628415Speter (s->match_length == MIN_MATCH && 176728415Speter s->strstart - s->match_start > TOO_FAR))) { 176828415Speter 176928415Speter /* If prev_match is also MIN_MATCH, match_start is garbage 177028415Speter * but we will ignore the current match anyway. 177128415Speter */ 177228415Speter s->match_length = MIN_MATCH-1; 177328415Speter } 177428415Speter } 177528415Speter /* If there was a match at the previous step and the current 177628415Speter * match is not better, output the previous match: 177728415Speter */ 177828415Speter if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 177928415Speter uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 178028415Speter /* Do not insert strings in hash table beyond this. */ 178128415Speter 178228415Speter check_match(s, s->strstart-1, s->prev_match, s->prev_length); 178328415Speter 178434768Speter bflush = _tr_tally(s, s->strstart -1 - s->prev_match, 178534768Speter s->prev_length - MIN_MATCH); 178628415Speter 178728415Speter /* Insert in hash table all strings up to the end of the match. 178828415Speter * strstart-1 and strstart are already inserted. If there is not 178928415Speter * enough lookahead, the last two strings are not inserted in 179028415Speter * the hash table. 179128415Speter */ 179228415Speter s->lookahead -= s->prev_length-1; 179328415Speter s->prev_length -= 2; 179428415Speter do { 179528415Speter if (++s->strstart <= max_insert) { 179628415Speter INSERT_STRING(s, s->strstart, hash_head); 179728415Speter } 179828415Speter } while (--s->prev_length != 0); 179928415Speter s->match_available = 0; 180028415Speter s->match_length = MIN_MATCH-1; 180128415Speter s->strstart++; 180228415Speter 180334768Speter if (bflush) FLUSH_BLOCK(s, 0); 180428415Speter 180528415Speter } else if (s->match_available) { 180628415Speter /* If there was no match at the previous position, output a 180728415Speter * single literal. If there was a match but the current match 180828415Speter * is longer, truncate the previous match to a single literal. 180928415Speter */ 181028415Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 181134768Speter if (_tr_tally (s, 0, s->window[s->strstart-1])) { 181234768Speter FLUSH_BLOCK_ONLY(s, 0); 181328415Speter } 181428415Speter s->strstart++; 181528415Speter s->lookahead--; 181634768Speter if (s->strm->avail_out == 0) return need_more; 181728415Speter } else { 181828415Speter /* There is no previous match to compare with, wait for 181928415Speter * the next step to decide. 182028415Speter */ 182128415Speter s->match_available = 1; 182228415Speter s->strstart++; 182328415Speter s->lookahead--; 182428415Speter } 182528415Speter } 182628415Speter Assert (flush != Z_NO_FLUSH, "no flush?"); 182728415Speter if (s->match_available) { 182828415Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 182934768Speter _tr_tally (s, 0, s->window[s->strstart-1]); 183028415Speter s->match_available = 0; 183128415Speter } 183234768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 183334768Speter return flush == Z_FINISH ? finish_done : block_done; 183428415Speter} 183534768Speter/* --- deflate.c */ 183628415Speter 183734768Speter/* +++ trees.c */ 183828415Speter/* trees.c -- output deflated data using Huffman coding 183934768Speter * Copyright (C) 1995-1996 Jean-loup Gailly 184028415Speter * For conditions of distribution and use, see copyright notice in zlib.h 184128415Speter */ 184228415Speter 184328415Speter/* 184428415Speter * ALGORITHM 184528415Speter * 184628415Speter * The "deflation" process uses several Huffman trees. The more 184728415Speter * common source values are represented by shorter bit sequences. 184828415Speter * 184928415Speter * Each code tree is stored in a compressed form which is itself 185028415Speter * a Huffman encoding of the lengths of all the code strings (in 185128415Speter * ascending order by source values). The actual code strings are 185228415Speter * reconstructed from the lengths in the inflate process, as described 185328415Speter * in the deflate specification. 185428415Speter * 185528415Speter * REFERENCES 185628415Speter * 185728415Speter * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". 185828415Speter * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc 185928415Speter * 186028415Speter * Storer, James A. 186128415Speter * Data Compression: Methods and Theory, pp. 49-50. 186228415Speter * Computer Science Press, 1988. ISBN 0-7167-8156-5. 186328415Speter * 186428415Speter * Sedgewick, R. 186528415Speter * Algorithms, p290. 186628415Speter * Addison-Wesley, 1983. ISBN 0-201-06672-6. 186728415Speter */ 186828415Speter 186934768Speter/* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */ 187028415Speter 187134768Speter/* #include "deflate.h" */ 187234768Speter 187328415Speter#ifdef DEBUG_ZLIB 187428415Speter# include <ctype.h> 187528415Speter#endif 187628415Speter 187728415Speter/* =========================================================================== 187828415Speter * Constants 187928415Speter */ 188028415Speter 188128415Speter#define MAX_BL_BITS 7 188228415Speter/* Bit length codes must not exceed MAX_BL_BITS bits */ 188328415Speter 188428415Speter#define END_BLOCK 256 188528415Speter/* end of block literal code */ 188628415Speter 188728415Speter#define REP_3_6 16 188828415Speter/* repeat previous bit length 3-6 times (2 bits of repeat count) */ 188928415Speter 189028415Speter#define REPZ_3_10 17 189128415Speter/* repeat a zero length 3-10 times (3 bits of repeat count) */ 189228415Speter 189328415Speter#define REPZ_11_138 18 189428415Speter/* repeat a zero length 11-138 times (7 bits of repeat count) */ 189528415Speter 189628415Speterlocal int extra_lbits[LENGTH_CODES] /* extra bits for each length code */ 189728415Speter = {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}; 189828415Speter 189928415Speterlocal int extra_dbits[D_CODES] /* extra bits for each distance code */ 190028415Speter = {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}; 190128415Speter 190228415Speterlocal int extra_blbits[BL_CODES]/* extra bits for each bit length code */ 190328415Speter = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; 190428415Speter 190528415Speterlocal uch bl_order[BL_CODES] 190628415Speter = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; 190728415Speter/* The lengths of the bit length codes are sent in order of decreasing 190828415Speter * probability, to avoid transmitting the lengths for unused bit length codes. 190928415Speter */ 191028415Speter 191128415Speter#define Buf_size (8 * 2*sizeof(char)) 191228415Speter/* Number of bits used within bi_buf. (bi_buf might be implemented on 191328415Speter * more than 16 bits on some systems.) 191428415Speter */ 191528415Speter 191628415Speter/* =========================================================================== 191728415Speter * Local data. These are initialized only once. 191828415Speter */ 191928415Speter 192028415Speterlocal ct_data static_ltree[L_CODES+2]; 192128415Speter/* The static literal tree. Since the bit lengths are imposed, there is no 192228415Speter * need for the L_CODES extra codes used during heap construction. However 192334768Speter * The codes 286 and 287 are needed to build a canonical tree (see _tr_init 192428415Speter * below). 192528415Speter */ 192628415Speter 192728415Speterlocal ct_data static_dtree[D_CODES]; 192828415Speter/* The static distance tree. (Actually a trivial tree since all codes use 192928415Speter * 5 bits.) 193028415Speter */ 193128415Speter 193228415Speterlocal uch dist_code[512]; 193328415Speter/* distance codes. The first 256 values correspond to the distances 193428415Speter * 3 .. 258, the last 256 values correspond to the top 8 bits of 193528415Speter * the 15 bit distances. 193628415Speter */ 193728415Speter 193828415Speterlocal uch length_code[MAX_MATCH-MIN_MATCH+1]; 193928415Speter/* length code for each normalized match length (0 == MIN_MATCH) */ 194028415Speter 194128415Speterlocal int base_length[LENGTH_CODES]; 194228415Speter/* First normalized length for each code (0 = MIN_MATCH) */ 194328415Speter 194428415Speterlocal int base_dist[D_CODES]; 194528415Speter/* First normalized distance for each code (0 = distance of 1) */ 194628415Speter 194728415Speterstruct static_tree_desc_s { 194828415Speter ct_data *static_tree; /* static tree or NULL */ 194928415Speter intf *extra_bits; /* extra bits for each code or NULL */ 195028415Speter int extra_base; /* base index for extra_bits */ 195128415Speter int elems; /* max number of elements in the tree */ 195228415Speter int max_length; /* max bit length for the codes */ 195328415Speter}; 195428415Speter 195528415Speterlocal static_tree_desc static_l_desc = 195628415Speter{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; 195728415Speter 195828415Speterlocal static_tree_desc static_d_desc = 195928415Speter{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; 196028415Speter 196128415Speterlocal static_tree_desc static_bl_desc = 196228415Speter{(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; 196328415Speter 196428415Speter/* =========================================================================== 196528415Speter * Local (static) routines in this file. 196628415Speter */ 196728415Speter 196834768Speterlocal void tr_static_init OF((void)); 196928415Speterlocal void init_block OF((deflate_state *s)); 197028415Speterlocal void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); 197128415Speterlocal void gen_bitlen OF((deflate_state *s, tree_desc *desc)); 197228415Speterlocal void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); 197328415Speterlocal void build_tree OF((deflate_state *s, tree_desc *desc)); 197428415Speterlocal void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); 197528415Speterlocal void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); 197628415Speterlocal int build_bl_tree OF((deflate_state *s)); 197728415Speterlocal void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, 197828415Speter int blcodes)); 197928415Speterlocal void compress_block OF((deflate_state *s, ct_data *ltree, 198028415Speter ct_data *dtree)); 198128415Speterlocal void set_data_type OF((deflate_state *s)); 198228415Speterlocal unsigned bi_reverse OF((unsigned value, int length)); 198328415Speterlocal void bi_windup OF((deflate_state *s)); 198428415Speterlocal void bi_flush OF((deflate_state *s)); 198528415Speterlocal void copy_block OF((deflate_state *s, charf *buf, unsigned len, 198628415Speter int header)); 198728415Speter 198828415Speter#ifndef DEBUG_ZLIB 198928415Speter# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) 199028415Speter /* Send a code of the given tree. c and tree must not have side effects */ 199128415Speter 199228415Speter#else /* DEBUG_ZLIB */ 199328415Speter# define send_code(s, c, tree) \ 199434768Speter { if (verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ 199528415Speter send_bits(s, tree[c].Code, tree[c].Len); } 199628415Speter#endif 199728415Speter 199828415Speter#define d_code(dist) \ 199928415Speter ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)]) 200028415Speter/* Mapping from a distance to a distance code. dist is the distance - 1 and 200128415Speter * must not have side effects. dist_code[256] and dist_code[257] are never 200228415Speter * used. 200328415Speter */ 200428415Speter 200528415Speter/* =========================================================================== 200628415Speter * Output a short LSB first on the stream. 200728415Speter * IN assertion: there is enough room in pendingBuf. 200828415Speter */ 200928415Speter#define put_short(s, w) { \ 201028415Speter put_byte(s, (uch)((w) & 0xff)); \ 201128415Speter put_byte(s, (uch)((ush)(w) >> 8)); \ 201228415Speter} 201328415Speter 201428415Speter/* =========================================================================== 201528415Speter * Send a value on a given number of bits. 201628415Speter * IN assertion: length <= 16 and value fits in length bits. 201728415Speter */ 201828415Speter#ifdef DEBUG_ZLIB 201928415Speterlocal void send_bits OF((deflate_state *s, int value, int length)); 202028415Speter 202128415Speterlocal void send_bits(s, value, length) 202228415Speter deflate_state *s; 202328415Speter int value; /* value to send */ 202428415Speter int length; /* number of bits */ 202528415Speter{ 202634768Speter Tracevv((stderr," l %2d v %4x ", length, value)); 202728415Speter Assert(length > 0 && length <= 15, "invalid length"); 202828415Speter s->bits_sent += (ulg)length; 202928415Speter 203028415Speter /* If not enough room in bi_buf, use (valid) bits from bi_buf and 203128415Speter * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 203228415Speter * unused bits in value. 203328415Speter */ 203428415Speter if (s->bi_valid > (int)Buf_size - length) { 203528415Speter s->bi_buf |= (value << s->bi_valid); 203628415Speter put_short(s, s->bi_buf); 203728415Speter s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); 203828415Speter s->bi_valid += length - Buf_size; 203928415Speter } else { 204028415Speter s->bi_buf |= value << s->bi_valid; 204128415Speter s->bi_valid += length; 204228415Speter } 204328415Speter} 204428415Speter#else /* !DEBUG_ZLIB */ 204528415Speter 204628415Speter#define send_bits(s, value, length) \ 204728415Speter{ int len = length;\ 204828415Speter if (s->bi_valid > (int)Buf_size - len) {\ 204928415Speter int val = value;\ 205028415Speter s->bi_buf |= (val << s->bi_valid);\ 205128415Speter put_short(s, s->bi_buf);\ 205228415Speter s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ 205328415Speter s->bi_valid += len - Buf_size;\ 205428415Speter } else {\ 205528415Speter s->bi_buf |= (value) << s->bi_valid;\ 205628415Speter s->bi_valid += len;\ 205728415Speter }\ 205828415Speter} 205928415Speter#endif /* DEBUG_ZLIB */ 206028415Speter 206128415Speter 206228415Speter#define MAX(a,b) (a >= b ? a : b) 206328415Speter/* the arguments must not have side effects */ 206428415Speter 206528415Speter/* =========================================================================== 206634768Speter * Initialize the various 'constant' tables. In a multi-threaded environment, 206734768Speter * this function may be called by two threads concurrently, but this is 206834768Speter * harmless since both invocations do exactly the same thing. 206928415Speter */ 207034768Speterlocal void tr_static_init() 207128415Speter{ 207234768Speter static int static_init_done = 0; 207328415Speter int n; /* iterates over tree elements */ 207428415Speter int bits; /* bit counter */ 207528415Speter int length; /* length value */ 207628415Speter int code; /* code value */ 207728415Speter int dist; /* distance index */ 207828415Speter ush bl_count[MAX_BITS+1]; 207928415Speter /* number of codes at each bit length for an optimal tree */ 208028415Speter 208134768Speter if (static_init_done) return; 208234768Speter 208328415Speter /* Initialize the mapping length (0..255) -> length code (0..28) */ 208428415Speter length = 0; 208528415Speter for (code = 0; code < LENGTH_CODES-1; code++) { 208628415Speter base_length[code] = length; 208728415Speter for (n = 0; n < (1<<extra_lbits[code]); n++) { 208828415Speter length_code[length++] = (uch)code; 208928415Speter } 209028415Speter } 209134768Speter Assert (length == 256, "tr_static_init: length != 256"); 209228415Speter /* Note that the length 255 (match length 258) can be represented 209328415Speter * in two different ways: code 284 + 5 bits or code 285, so we 209428415Speter * overwrite length_code[255] to use the best encoding: 209528415Speter */ 209628415Speter length_code[length-1] = (uch)code; 209728415Speter 209828415Speter /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 209928415Speter dist = 0; 210028415Speter for (code = 0 ; code < 16; code++) { 210128415Speter base_dist[code] = dist; 210228415Speter for (n = 0; n < (1<<extra_dbits[code]); n++) { 210328415Speter dist_code[dist++] = (uch)code; 210428415Speter } 210528415Speter } 210634768Speter Assert (dist == 256, "tr_static_init: dist != 256"); 210728415Speter dist >>= 7; /* from now on, all distances are divided by 128 */ 210828415Speter for ( ; code < D_CODES; code++) { 210928415Speter base_dist[code] = dist << 7; 211028415Speter for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 211128415Speter dist_code[256 + dist++] = (uch)code; 211228415Speter } 211328415Speter } 211434768Speter Assert (dist == 256, "tr_static_init: 256+dist != 512"); 211528415Speter 211628415Speter /* Construct the codes of the static literal tree */ 211728415Speter for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 211828415Speter n = 0; 211928415Speter while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 212028415Speter while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 212128415Speter while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 212228415Speter while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 212328415Speter /* Codes 286 and 287 do not exist, but we must include them in the 212428415Speter * tree construction to get a canonical Huffman tree (longest code 212528415Speter * all ones) 212628415Speter */ 212728415Speter gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); 212828415Speter 212928415Speter /* The static distance tree is trivial: */ 213028415Speter for (n = 0; n < D_CODES; n++) { 213128415Speter static_dtree[n].Len = 5; 213234768Speter static_dtree[n].Code = bi_reverse((unsigned)n, 5); 213328415Speter } 213434768Speter static_init_done = 1; 213528415Speter} 213628415Speter 213728415Speter/* =========================================================================== 213828415Speter * Initialize the tree data structures for a new zlib stream. 213928415Speter */ 214034768Spetervoid _tr_init(s) 214128415Speter deflate_state *s; 214228415Speter{ 214334768Speter tr_static_init(); 214428415Speter 214528415Speter s->compressed_len = 0L; 214628415Speter 214728415Speter s->l_desc.dyn_tree = s->dyn_ltree; 214828415Speter s->l_desc.stat_desc = &static_l_desc; 214928415Speter 215028415Speter s->d_desc.dyn_tree = s->dyn_dtree; 215128415Speter s->d_desc.stat_desc = &static_d_desc; 215228415Speter 215328415Speter s->bl_desc.dyn_tree = s->bl_tree; 215428415Speter s->bl_desc.stat_desc = &static_bl_desc; 215528415Speter 215628415Speter s->bi_buf = 0; 215728415Speter s->bi_valid = 0; 215828415Speter s->last_eob_len = 8; /* enough lookahead for inflate */ 215928415Speter#ifdef DEBUG_ZLIB 216028415Speter s->bits_sent = 0L; 216128415Speter#endif 216228415Speter 216328415Speter /* Initialize the first block of the first file: */ 216428415Speter init_block(s); 216528415Speter} 216628415Speter 216728415Speter/* =========================================================================== 216828415Speter * Initialize a new block. 216928415Speter */ 217028415Speterlocal void init_block(s) 217128415Speter deflate_state *s; 217228415Speter{ 217328415Speter int n; /* iterates over tree elements */ 217428415Speter 217528415Speter /* Initialize the trees. */ 217628415Speter for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; 217728415Speter for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; 217828415Speter for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; 217928415Speter 218028415Speter s->dyn_ltree[END_BLOCK].Freq = 1; 218128415Speter s->opt_len = s->static_len = 0L; 218228415Speter s->last_lit = s->matches = 0; 218328415Speter} 218428415Speter 218528415Speter#define SMALLEST 1 218628415Speter/* Index within the heap array of least frequent node in the Huffman tree */ 218728415Speter 218828415Speter 218928415Speter/* =========================================================================== 219028415Speter * Remove the smallest element from the heap and recreate the heap with 219128415Speter * one less element. Updates heap and heap_len. 219228415Speter */ 219328415Speter#define pqremove(s, tree, top) \ 219428415Speter{\ 219528415Speter top = s->heap[SMALLEST]; \ 219628415Speter s->heap[SMALLEST] = s->heap[s->heap_len--]; \ 219728415Speter pqdownheap(s, tree, SMALLEST); \ 219828415Speter} 219928415Speter 220028415Speter/* =========================================================================== 220128415Speter * Compares to subtrees, using the tree depth as tie breaker when 220228415Speter * the subtrees have equal frequency. This minimizes the worst case length. 220328415Speter */ 220428415Speter#define smaller(tree, n, m, depth) \ 220528415Speter (tree[n].Freq < tree[m].Freq || \ 220628415Speter (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 220728415Speter 220828415Speter/* =========================================================================== 220928415Speter * Restore the heap property by moving down the tree starting at node k, 221028415Speter * exchanging a node with the smallest of its two sons if necessary, stopping 221128415Speter * when the heap property is re-established (each father smaller than its 221228415Speter * two sons). 221328415Speter */ 221428415Speterlocal void pqdownheap(s, tree, k) 221528415Speter deflate_state *s; 221628415Speter ct_data *tree; /* the tree to restore */ 221728415Speter int k; /* node to move down */ 221828415Speter{ 221928415Speter int v = s->heap[k]; 222028415Speter int j = k << 1; /* left son of k */ 222128415Speter while (j <= s->heap_len) { 222228415Speter /* Set j to the smallest of the two sons: */ 222328415Speter if (j < s->heap_len && 222428415Speter smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { 222528415Speter j++; 222628415Speter } 222728415Speter /* Exit if v is smaller than both sons */ 222828415Speter if (smaller(tree, v, s->heap[j], s->depth)) break; 222928415Speter 223028415Speter /* Exchange v with the smallest son */ 223128415Speter s->heap[k] = s->heap[j]; k = j; 223228415Speter 223328415Speter /* And continue down the tree, setting j to the left son of k */ 223428415Speter j <<= 1; 223528415Speter } 223628415Speter s->heap[k] = v; 223728415Speter} 223828415Speter 223928415Speter/* =========================================================================== 224028415Speter * Compute the optimal bit lengths for a tree and update the total bit length 224128415Speter * for the current block. 224228415Speter * IN assertion: the fields freq and dad are set, heap[heap_max] and 224328415Speter * above are the tree nodes sorted by increasing frequency. 224428415Speter * OUT assertions: the field len is set to the optimal bit length, the 224528415Speter * array bl_count contains the frequencies for each bit length. 224628415Speter * The length opt_len is updated; static_len is also updated if stree is 224728415Speter * not null. 224828415Speter */ 224928415Speterlocal void gen_bitlen(s, desc) 225028415Speter deflate_state *s; 225128415Speter tree_desc *desc; /* the tree descriptor */ 225228415Speter{ 225328415Speter ct_data *tree = desc->dyn_tree; 225428415Speter int max_code = desc->max_code; 225528415Speter ct_data *stree = desc->stat_desc->static_tree; 225628415Speter intf *extra = desc->stat_desc->extra_bits; 225728415Speter int base = desc->stat_desc->extra_base; 225828415Speter int max_length = desc->stat_desc->max_length; 225928415Speter int h; /* heap index */ 226028415Speter int n, m; /* iterate over the tree elements */ 226128415Speter int bits; /* bit length */ 226228415Speter int xbits; /* extra bits */ 226328415Speter ush f; /* frequency */ 226428415Speter int overflow = 0; /* number of elements with bit length too large */ 226528415Speter 226628415Speter for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; 226728415Speter 226828415Speter /* In a first pass, compute the optimal bit lengths (which may 226928415Speter * overflow in the case of the bit length tree). 227028415Speter */ 227128415Speter tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ 227228415Speter 227328415Speter for (h = s->heap_max+1; h < HEAP_SIZE; h++) { 227428415Speter n = s->heap[h]; 227528415Speter bits = tree[tree[n].Dad].Len + 1; 227628415Speter if (bits > max_length) bits = max_length, overflow++; 227728415Speter tree[n].Len = (ush)bits; 227828415Speter /* We overwrite tree[n].Dad which is no longer needed */ 227928415Speter 228028415Speter if (n > max_code) continue; /* not a leaf node */ 228128415Speter 228228415Speter s->bl_count[bits]++; 228328415Speter xbits = 0; 228428415Speter if (n >= base) xbits = extra[n-base]; 228528415Speter f = tree[n].Freq; 228628415Speter s->opt_len += (ulg)f * (bits + xbits); 228728415Speter if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); 228828415Speter } 228928415Speter if (overflow == 0) return; 229028415Speter 229128415Speter Trace((stderr,"\nbit length overflow\n")); 229228415Speter /* This happens for example on obj2 and pic of the Calgary corpus */ 229328415Speter 229428415Speter /* Find the first bit length which could increase: */ 229528415Speter do { 229628415Speter bits = max_length-1; 229728415Speter while (s->bl_count[bits] == 0) bits--; 229828415Speter s->bl_count[bits]--; /* move one leaf down the tree */ 229928415Speter s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ 230028415Speter s->bl_count[max_length]--; 230128415Speter /* The brother of the overflow item also moves one step up, 230228415Speter * but this does not affect bl_count[max_length] 230328415Speter */ 230428415Speter overflow -= 2; 230528415Speter } while (overflow > 0); 230628415Speter 230728415Speter /* Now recompute all bit lengths, scanning in increasing frequency. 230828415Speter * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 230928415Speter * lengths instead of fixing only the wrong ones. This idea is taken 231028415Speter * from 'ar' written by Haruhiko Okumura.) 231128415Speter */ 231228415Speter for (bits = max_length; bits != 0; bits--) { 231328415Speter n = s->bl_count[bits]; 231428415Speter while (n != 0) { 231528415Speter m = s->heap[--h]; 231628415Speter if (m > max_code) continue; 231728415Speter if (tree[m].Len != (unsigned) bits) { 231828415Speter Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); 231928415Speter s->opt_len += ((long)bits - (long)tree[m].Len) 232028415Speter *(long)tree[m].Freq; 232128415Speter tree[m].Len = (ush)bits; 232228415Speter } 232328415Speter n--; 232428415Speter } 232528415Speter } 232628415Speter} 232728415Speter 232828415Speter/* =========================================================================== 232928415Speter * Generate the codes for a given tree and bit counts (which need not be 233028415Speter * optimal). 233128415Speter * IN assertion: the array bl_count contains the bit length statistics for 233228415Speter * the given tree and the field len is set for all tree elements. 233328415Speter * OUT assertion: the field code is set for all tree elements of non 233428415Speter * zero code length. 233528415Speter */ 233628415Speterlocal void gen_codes (tree, max_code, bl_count) 233728415Speter ct_data *tree; /* the tree to decorate */ 233828415Speter int max_code; /* largest code with non zero frequency */ 233928415Speter ushf *bl_count; /* number of codes at each bit length */ 234028415Speter{ 234128415Speter ush next_code[MAX_BITS+1]; /* next code value for each bit length */ 234228415Speter ush code = 0; /* running code value */ 234328415Speter int bits; /* bit index */ 234428415Speter int n; /* code index */ 234528415Speter 234628415Speter /* The distribution counts are first used to generate the code values 234728415Speter * without bit reversal. 234828415Speter */ 234928415Speter for (bits = 1; bits <= MAX_BITS; bits++) { 235028415Speter next_code[bits] = code = (code + bl_count[bits-1]) << 1; 235128415Speter } 235228415Speter /* Check that the bit counts in bl_count are consistent. The last code 235328415Speter * must be all ones. 235428415Speter */ 235528415Speter Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 235628415Speter "inconsistent bit counts"); 235728415Speter Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); 235828415Speter 235928415Speter for (n = 0; n <= max_code; n++) { 236028415Speter int len = tree[n].Len; 236128415Speter if (len == 0) continue; 236228415Speter /* Now reverse the bits */ 236328415Speter tree[n].Code = bi_reverse(next_code[len]++, len); 236428415Speter 236534768Speter Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", 236628415Speter n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); 236728415Speter } 236828415Speter} 236928415Speter 237028415Speter/* =========================================================================== 237128415Speter * Construct one Huffman tree and assigns the code bit strings and lengths. 237228415Speter * Update the total bit length for the current block. 237328415Speter * IN assertion: the field freq is set for all tree elements. 237428415Speter * OUT assertions: the fields len and code are set to the optimal bit length 237528415Speter * and corresponding code. The length opt_len is updated; static_len is 237628415Speter * also updated if stree is not null. The field max_code is set. 237728415Speter */ 237828415Speterlocal void build_tree(s, desc) 237928415Speter deflate_state *s; 238028415Speter tree_desc *desc; /* the tree descriptor */ 238128415Speter{ 238228415Speter ct_data *tree = desc->dyn_tree; 238328415Speter ct_data *stree = desc->stat_desc->static_tree; 238428415Speter int elems = desc->stat_desc->elems; 238528415Speter int n, m; /* iterate over heap elements */ 238628415Speter int max_code = -1; /* largest code with non zero frequency */ 238728415Speter int node; /* new node being created */ 238828415Speter 238928415Speter /* Construct the initial heap, with least frequent element in 239028415Speter * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 239128415Speter * heap[0] is not used. 239228415Speter */ 239328415Speter s->heap_len = 0, s->heap_max = HEAP_SIZE; 239428415Speter 239528415Speter for (n = 0; n < elems; n++) { 239628415Speter if (tree[n].Freq != 0) { 239728415Speter s->heap[++(s->heap_len)] = max_code = n; 239828415Speter s->depth[n] = 0; 239928415Speter } else { 240028415Speter tree[n].Len = 0; 240128415Speter } 240228415Speter } 240328415Speter 240428415Speter /* The pkzip format requires that at least one distance code exists, 240528415Speter * and that at least one bit should be sent even if there is only one 240628415Speter * possible code. So to avoid special checks later on we force at least 240728415Speter * two codes of non zero frequency. 240828415Speter */ 240928415Speter while (s->heap_len < 2) { 241028415Speter node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); 241128415Speter tree[node].Freq = 1; 241228415Speter s->depth[node] = 0; 241328415Speter s->opt_len--; if (stree) s->static_len -= stree[node].Len; 241428415Speter /* node is 0 or 1 so it does not have extra bits */ 241528415Speter } 241628415Speter desc->max_code = max_code; 241728415Speter 241828415Speter /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 241928415Speter * establish sub-heaps of increasing lengths: 242028415Speter */ 242128415Speter for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); 242228415Speter 242328415Speter /* Construct the Huffman tree by repeatedly combining the least two 242428415Speter * frequent nodes. 242528415Speter */ 242628415Speter node = elems; /* next internal node of the tree */ 242728415Speter do { 242828415Speter pqremove(s, tree, n); /* n = node of least frequency */ 242928415Speter m = s->heap[SMALLEST]; /* m = node of next least frequency */ 243028415Speter 243128415Speter s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ 243228415Speter s->heap[--(s->heap_max)] = m; 243328415Speter 243428415Speter /* Create a new node father of n and m */ 243528415Speter tree[node].Freq = tree[n].Freq + tree[m].Freq; 243628415Speter s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1); 243728415Speter tree[n].Dad = tree[m].Dad = (ush)node; 243828415Speter#ifdef DUMP_BL_TREE 243928415Speter if (tree == s->bl_tree) { 244028415Speter fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", 244128415Speter node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); 244228415Speter } 244328415Speter#endif 244428415Speter /* and insert the new node in the heap */ 244528415Speter s->heap[SMALLEST] = node++; 244628415Speter pqdownheap(s, tree, SMALLEST); 244728415Speter 244828415Speter } while (s->heap_len >= 2); 244928415Speter 245028415Speter s->heap[--(s->heap_max)] = s->heap[SMALLEST]; 245128415Speter 245228415Speter /* At this point, the fields freq and dad are set. We can now 245328415Speter * generate the bit lengths. 245428415Speter */ 245528415Speter gen_bitlen(s, (tree_desc *)desc); 245628415Speter 245728415Speter /* The field len is now set, we can generate the bit codes */ 245828415Speter gen_codes ((ct_data *)tree, max_code, s->bl_count); 245928415Speter} 246028415Speter 246128415Speter/* =========================================================================== 246228415Speter * Scan a literal or distance tree to determine the frequencies of the codes 246328415Speter * in the bit length tree. 246428415Speter */ 246528415Speterlocal void scan_tree (s, tree, max_code) 246628415Speter deflate_state *s; 246728415Speter ct_data *tree; /* the tree to be scanned */ 246828415Speter int max_code; /* and its largest code of non zero frequency */ 246928415Speter{ 247028415Speter int n; /* iterates over all tree elements */ 247128415Speter int prevlen = -1; /* last emitted length */ 247228415Speter int curlen; /* length of current code */ 247328415Speter int nextlen = tree[0].Len; /* length of next code */ 247428415Speter int count = 0; /* repeat count of the current code */ 247528415Speter int max_count = 7; /* max repeat count */ 247628415Speter int min_count = 4; /* min repeat count */ 247728415Speter 247828415Speter if (nextlen == 0) max_count = 138, min_count = 3; 247928415Speter tree[max_code+1].Len = (ush)0xffff; /* guard */ 248028415Speter 248128415Speter for (n = 0; n <= max_code; n++) { 248228415Speter curlen = nextlen; nextlen = tree[n+1].Len; 248328415Speter if (++count < max_count && curlen == nextlen) { 248428415Speter continue; 248528415Speter } else if (count < min_count) { 248628415Speter s->bl_tree[curlen].Freq += count; 248728415Speter } else if (curlen != 0) { 248828415Speter if (curlen != prevlen) s->bl_tree[curlen].Freq++; 248928415Speter s->bl_tree[REP_3_6].Freq++; 249028415Speter } else if (count <= 10) { 249128415Speter s->bl_tree[REPZ_3_10].Freq++; 249228415Speter } else { 249328415Speter s->bl_tree[REPZ_11_138].Freq++; 249428415Speter } 249528415Speter count = 0; prevlen = curlen; 249628415Speter if (nextlen == 0) { 249728415Speter max_count = 138, min_count = 3; 249828415Speter } else if (curlen == nextlen) { 249928415Speter max_count = 6, min_count = 3; 250028415Speter } else { 250128415Speter max_count = 7, min_count = 4; 250228415Speter } 250328415Speter } 250428415Speter} 250528415Speter 250628415Speter/* =========================================================================== 250728415Speter * Send a literal or distance tree in compressed form, using the codes in 250828415Speter * bl_tree. 250928415Speter */ 251028415Speterlocal void send_tree (s, tree, max_code) 251128415Speter deflate_state *s; 251228415Speter ct_data *tree; /* the tree to be scanned */ 251328415Speter int max_code; /* and its largest code of non zero frequency */ 251428415Speter{ 251528415Speter int n; /* iterates over all tree elements */ 251628415Speter int prevlen = -1; /* last emitted length */ 251728415Speter int curlen; /* length of current code */ 251828415Speter int nextlen = tree[0].Len; /* length of next code */ 251928415Speter int count = 0; /* repeat count of the current code */ 252028415Speter int max_count = 7; /* max repeat count */ 252128415Speter int min_count = 4; /* min repeat count */ 252228415Speter 252328415Speter /* tree[max_code+1].Len = -1; */ /* guard already set */ 252428415Speter if (nextlen == 0) max_count = 138, min_count = 3; 252528415Speter 252628415Speter for (n = 0; n <= max_code; n++) { 252728415Speter curlen = nextlen; nextlen = tree[n+1].Len; 252828415Speter if (++count < max_count && curlen == nextlen) { 252928415Speter continue; 253028415Speter } else if (count < min_count) { 253128415Speter do { send_code(s, curlen, s->bl_tree); } while (--count != 0); 253228415Speter 253328415Speter } else if (curlen != 0) { 253428415Speter if (curlen != prevlen) { 253528415Speter send_code(s, curlen, s->bl_tree); count--; 253628415Speter } 253728415Speter Assert(count >= 3 && count <= 6, " 3_6?"); 253828415Speter send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); 253928415Speter 254028415Speter } else if (count <= 10) { 254128415Speter send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); 254228415Speter 254328415Speter } else { 254428415Speter send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); 254528415Speter } 254628415Speter count = 0; prevlen = curlen; 254728415Speter if (nextlen == 0) { 254828415Speter max_count = 138, min_count = 3; 254928415Speter } else if (curlen == nextlen) { 255028415Speter max_count = 6, min_count = 3; 255128415Speter } else { 255228415Speter max_count = 7, min_count = 4; 255328415Speter } 255428415Speter } 255528415Speter} 255628415Speter 255728415Speter/* =========================================================================== 255828415Speter * Construct the Huffman tree for the bit lengths and return the index in 255928415Speter * bl_order of the last bit length code to send. 256028415Speter */ 256128415Speterlocal int build_bl_tree(s) 256228415Speter deflate_state *s; 256328415Speter{ 256428415Speter int max_blindex; /* index of last bit length code of non zero freq */ 256528415Speter 256628415Speter /* Determine the bit length frequencies for literal and distance trees */ 256728415Speter scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); 256828415Speter scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); 256928415Speter 257028415Speter /* Build the bit length tree: */ 257128415Speter build_tree(s, (tree_desc *)(&(s->bl_desc))); 257228415Speter /* opt_len now includes the length of the tree representations, except 257328415Speter * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 257428415Speter */ 257528415Speter 257628415Speter /* Determine the number of bit length codes to send. The pkzip format 257728415Speter * requires that at least 4 bit length codes be sent. (appnote.txt says 257828415Speter * 3 but the actual value used is 4.) 257928415Speter */ 258028415Speter for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 258128415Speter if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; 258228415Speter } 258328415Speter /* Update opt_len to include the bit length tree and counts */ 258428415Speter s->opt_len += 3*(max_blindex+1) + 5+5+4; 258528415Speter Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", 258628415Speter s->opt_len, s->static_len)); 258728415Speter 258828415Speter return max_blindex; 258928415Speter} 259028415Speter 259128415Speter/* =========================================================================== 259228415Speter * Send the header for a block using dynamic Huffman trees: the counts, the 259328415Speter * lengths of the bit length codes, the literal tree and the distance tree. 259428415Speter * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 259528415Speter */ 259628415Speterlocal void send_all_trees(s, lcodes, dcodes, blcodes) 259728415Speter deflate_state *s; 259828415Speter int lcodes, dcodes, blcodes; /* number of codes for each tree */ 259928415Speter{ 260028415Speter int rank; /* index in bl_order */ 260128415Speter 260228415Speter Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); 260328415Speter Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 260428415Speter "too many codes"); 260528415Speter Tracev((stderr, "\nbl counts: ")); 260628415Speter send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ 260728415Speter send_bits(s, dcodes-1, 5); 260828415Speter send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ 260928415Speter for (rank = 0; rank < blcodes; rank++) { 261028415Speter Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 261128415Speter send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); 261228415Speter } 261328415Speter Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); 261428415Speter 261528415Speter send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ 261628415Speter Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); 261728415Speter 261828415Speter send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ 261928415Speter Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); 262028415Speter} 262128415Speter 262228415Speter/* =========================================================================== 262328415Speter * Send a stored block 262428415Speter */ 262534768Spetervoid _tr_stored_block(s, buf, stored_len, eof) 262628415Speter deflate_state *s; 262728415Speter charf *buf; /* input block */ 262828415Speter ulg stored_len; /* length of input block */ 262928415Speter int eof; /* true if this is the last block for a file */ 263028415Speter{ 263128415Speter send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ 263234768Speter s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; 263328415Speter s->compressed_len += (stored_len + 4) << 3; 263428415Speter 263528415Speter copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ 263628415Speter} 263728415Speter 263828415Speter/* Send just the `stored block' type code without any length bytes or data. 263928415Speter */ 264034768Spetervoid _tr_stored_type_only(s) 264128415Speter deflate_state *s; 264228415Speter{ 264328415Speter send_bits(s, (STORED_BLOCK << 1), 3); 264428415Speter bi_windup(s); 264528415Speter s->compressed_len = (s->compressed_len + 3) & ~7L; 264628415Speter} 264728415Speter 264828415Speter 264928415Speter/* =========================================================================== 265028415Speter * Send one empty static block to give enough lookahead for inflate. 265128415Speter * This takes 10 bits, of which 7 may remain in the bit buffer. 265234768Speter * The current inflate code requires 9 bits of lookahead. If the 265334768Speter * last two codes for the previous block (real code plus EOB) were coded 265434768Speter * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode 265534768Speter * the last real code. In this case we send two empty static blocks instead 265634768Speter * of one. (There are no problems if the previous block is stored or fixed.) 265734768Speter * To simplify the code, we assume the worst case of last real code encoded 265834768Speter * on one bit only. 265928415Speter */ 266034768Spetervoid _tr_align(s) 266128415Speter deflate_state *s; 266228415Speter{ 266328415Speter send_bits(s, STATIC_TREES<<1, 3); 266428415Speter send_code(s, END_BLOCK, static_ltree); 266528415Speter s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ 266628415Speter bi_flush(s); 266728415Speter /* Of the 10 bits for the empty block, we have already sent 266834768Speter * (10 - bi_valid) bits. The lookahead for the last real code (before 266934768Speter * the EOB of the previous block) was thus at least one plus the length 267034768Speter * of the EOB plus what we have just sent of the empty static block. 267128415Speter */ 267234768Speter if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { 267328415Speter send_bits(s, STATIC_TREES<<1, 3); 267428415Speter send_code(s, END_BLOCK, static_ltree); 267528415Speter s->compressed_len += 10L; 267628415Speter bi_flush(s); 267728415Speter } 267828415Speter s->last_eob_len = 7; 267928415Speter} 268028415Speter 268128415Speter/* =========================================================================== 268228415Speter * Determine the best encoding for the current block: dynamic trees, static 268328415Speter * trees or store, and output the encoded block to the zip file. This function 268428415Speter * returns the total compressed length for the file so far. 268528415Speter */ 268634768Speterulg _tr_flush_block(s, buf, stored_len, eof) 268728415Speter deflate_state *s; 268828415Speter charf *buf; /* input block, or NULL if too old */ 268928415Speter ulg stored_len; /* length of input block */ 269034768Speter int eof; /* true if this is the last block for a file */ 269128415Speter{ 269228415Speter ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 269334768Speter int max_blindex = 0; /* index of last bit length code of non zero freq */ 269428415Speter 269534768Speter /* Build the Huffman trees unless a stored block is forced */ 269634768Speter if (s->level > 0) { 269728415Speter 269834768Speter /* Check if the file is ascii or binary */ 269934768Speter if (s->data_type == Z_UNKNOWN) set_data_type(s); 270028415Speter 270134768Speter /* Construct the literal and distance trees */ 270234768Speter build_tree(s, (tree_desc *)(&(s->l_desc))); 270334768Speter Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, 270434768Speter s->static_len)); 270528415Speter 270634768Speter build_tree(s, (tree_desc *)(&(s->d_desc))); 270734768Speter Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, 270834768Speter s->static_len)); 270934768Speter /* At this point, opt_len and static_len are the total bit lengths of 271034768Speter * the compressed block data, excluding the tree representations. 271134768Speter */ 271228415Speter 271334768Speter /* Build the bit length tree for the above two trees, and get the index 271434768Speter * in bl_order of the last bit length code to send. 271534768Speter */ 271634768Speter max_blindex = build_bl_tree(s); 271728415Speter 271834768Speter /* Determine the best encoding. Compute first the block length in bytes*/ 271934768Speter opt_lenb = (s->opt_len+3+7)>>3; 272034768Speter static_lenb = (s->static_len+3+7)>>3; 272128415Speter 272234768Speter Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 272334768Speter opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 272434768Speter s->last_lit)); 272528415Speter 272634768Speter if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 272728415Speter 272834768Speter } else { 272934768Speter Assert(buf != (char*)0, "lost buf"); 273034768Speter opt_lenb = static_lenb = stored_len + 5; /* force a stored block */ 273134768Speter } 273234768Speter 273328415Speter /* If compression failed and this is the first and last block, 273428415Speter * and if the .zip file can be seeked (to rewrite the local header), 273528415Speter * the whole file is transformed into a stored file: 273628415Speter */ 273728415Speter#ifdef STORED_FILE_OK 273828415Speter# ifdef FORCE_STORED_FILE 273934768Speter if (eof && s->compressed_len == 0L) { /* force stored file */ 274028415Speter# else 274134768Speter if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) { 274228415Speter# endif 274328415Speter /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ 274428415Speter if (buf == (charf*)0) error ("block vanished"); 274528415Speter 274634768Speter copy_block(s, buf, (unsigned)stored_len, 0); /* without header */ 274728415Speter s->compressed_len = stored_len << 3; 274828415Speter s->method = STORED; 274928415Speter } else 275028415Speter#endif /* STORED_FILE_OK */ 275128415Speter 275228415Speter#ifdef FORCE_STORED 275334768Speter if (buf != (char*)0) { /* force stored block */ 275428415Speter#else 275534768Speter if (stored_len+4 <= opt_lenb && buf != (char*)0) { 275628415Speter /* 4: two words for the lengths */ 275728415Speter#endif 275828415Speter /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 275928415Speter * Otherwise we can't have processed more than WSIZE input bytes since 276028415Speter * the last block flush, because compression would have been 276128415Speter * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 276228415Speter * transform a block into a stored block. 276328415Speter */ 276434768Speter _tr_stored_block(s, buf, stored_len, eof); 276528415Speter 276628415Speter#ifdef FORCE_STATIC 276734768Speter } else if (static_lenb >= 0) { /* force static trees */ 276828415Speter#else 276934768Speter } else if (static_lenb == opt_lenb) { 277028415Speter#endif 277128415Speter send_bits(s, (STATIC_TREES<<1)+eof, 3); 277228415Speter compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); 277328415Speter s->compressed_len += 3 + s->static_len; 277428415Speter } else { 277528415Speter send_bits(s, (DYN_TREES<<1)+eof, 3); 277628415Speter send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, 277728415Speter max_blindex+1); 277828415Speter compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); 277928415Speter s->compressed_len += 3 + s->opt_len; 278028415Speter } 278128415Speter Assert (s->compressed_len == s->bits_sent, "bad compressed size"); 278228415Speter init_block(s); 278328415Speter 278428415Speter if (eof) { 278528415Speter bi_windup(s); 278628415Speter s->compressed_len += 7; /* align on byte boundary */ 278728415Speter } 278828415Speter Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, 278928415Speter s->compressed_len-7*eof)); 279028415Speter 279128415Speter return s->compressed_len >> 3; 279228415Speter} 279328415Speter 279428415Speter/* =========================================================================== 279528415Speter * Save the match info and tally the frequency counts. Return true if 279628415Speter * the current block must be flushed. 279728415Speter */ 279834768Speterint _tr_tally (s, dist, lc) 279928415Speter deflate_state *s; 280034768Speter unsigned dist; /* distance of matched string */ 280134768Speter unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ 280228415Speter{ 280328415Speter s->d_buf[s->last_lit] = (ush)dist; 280428415Speter s->l_buf[s->last_lit++] = (uch)lc; 280528415Speter if (dist == 0) { 280628415Speter /* lc is the unmatched char */ 280728415Speter s->dyn_ltree[lc].Freq++; 280828415Speter } else { 280928415Speter s->matches++; 281028415Speter /* Here, lc is the match length - MIN_MATCH */ 281128415Speter dist--; /* dist = match distance - 1 */ 281228415Speter Assert((ush)dist < (ush)MAX_DIST(s) && 281328415Speter (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 281434768Speter (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match"); 281528415Speter 281628415Speter s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++; 281728415Speter s->dyn_dtree[d_code(dist)].Freq++; 281828415Speter } 281928415Speter 282028415Speter /* Try to guess if it is profitable to stop the current block here */ 282128415Speter if (s->level > 2 && (s->last_lit & 0xfff) == 0) { 282228415Speter /* Compute an upper bound for the compressed length */ 282328415Speter ulg out_length = (ulg)s->last_lit*8L; 282434768Speter ulg in_length = (ulg)((long)s->strstart - s->block_start); 282528415Speter int dcode; 282628415Speter for (dcode = 0; dcode < D_CODES; dcode++) { 282728415Speter out_length += (ulg)s->dyn_dtree[dcode].Freq * 282828415Speter (5L+extra_dbits[dcode]); 282928415Speter } 283028415Speter out_length >>= 3; 283128415Speter Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", 283228415Speter s->last_lit, in_length, out_length, 283328415Speter 100L - out_length*100L/in_length)); 283428415Speter if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; 283528415Speter } 283628415Speter return (s->last_lit == s->lit_bufsize-1); 283728415Speter /* We avoid equality with lit_bufsize because of wraparound at 64K 283828415Speter * on 16 bit machines and because stored blocks are restricted to 283928415Speter * 64K-1 bytes. 284028415Speter */ 284128415Speter} 284228415Speter 284328415Speter/* =========================================================================== 284428415Speter * Send the block data compressed using the given Huffman trees 284528415Speter */ 284628415Speterlocal void compress_block(s, ltree, dtree) 284728415Speter deflate_state *s; 284828415Speter ct_data *ltree; /* literal tree */ 284928415Speter ct_data *dtree; /* distance tree */ 285028415Speter{ 285128415Speter unsigned dist; /* distance of matched string */ 285228415Speter int lc; /* match length or unmatched char (if dist == 0) */ 285328415Speter unsigned lx = 0; /* running index in l_buf */ 285428415Speter unsigned code; /* the code to send */ 285528415Speter int extra; /* number of extra bits to send */ 285628415Speter 285728415Speter if (s->last_lit != 0) do { 285828415Speter dist = s->d_buf[lx]; 285928415Speter lc = s->l_buf[lx++]; 286028415Speter if (dist == 0) { 286128415Speter send_code(s, lc, ltree); /* send a literal byte */ 286228415Speter Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 286328415Speter } else { 286428415Speter /* Here, lc is the match length - MIN_MATCH */ 286528415Speter code = length_code[lc]; 286628415Speter send_code(s, code+LITERALS+1, ltree); /* send the length code */ 286728415Speter extra = extra_lbits[code]; 286828415Speter if (extra != 0) { 286928415Speter lc -= base_length[code]; 287028415Speter send_bits(s, lc, extra); /* send the extra length bits */ 287128415Speter } 287228415Speter dist--; /* dist is now the match distance - 1 */ 287328415Speter code = d_code(dist); 287428415Speter Assert (code < D_CODES, "bad d_code"); 287528415Speter 287628415Speter send_code(s, code, dtree); /* send the distance code */ 287728415Speter extra = extra_dbits[code]; 287828415Speter if (extra != 0) { 287928415Speter dist -= base_dist[code]; 288028415Speter send_bits(s, dist, extra); /* send the extra distance bits */ 288128415Speter } 288228415Speter } /* literal or match pair ? */ 288328415Speter 288428415Speter /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 288528415Speter Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow"); 288628415Speter 288728415Speter } while (lx < s->last_lit); 288828415Speter 288928415Speter send_code(s, END_BLOCK, ltree); 289028415Speter s->last_eob_len = ltree[END_BLOCK].Len; 289128415Speter} 289228415Speter 289328415Speter/* =========================================================================== 289434768Speter * Set the data type to ASCII or BINARY, using a crude approximation: 289528415Speter * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. 289628415Speter * IN assertion: the fields freq of dyn_ltree are set and the total of all 289728415Speter * frequencies does not exceed 64K (to fit in an int on 16 bit machines). 289828415Speter */ 289928415Speterlocal void set_data_type(s) 290028415Speter deflate_state *s; 290128415Speter{ 290228415Speter int n = 0; 290328415Speter unsigned ascii_freq = 0; 290428415Speter unsigned bin_freq = 0; 290528415Speter while (n < 7) bin_freq += s->dyn_ltree[n++].Freq; 290628415Speter while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq; 290728415Speter while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq; 290834768Speter s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII); 290928415Speter} 291028415Speter 291128415Speter/* =========================================================================== 291228415Speter * Reverse the first len bits of a code, using straightforward code (a faster 291328415Speter * method would use a table) 291428415Speter * IN assertion: 1 <= len <= 15 291528415Speter */ 291628415Speterlocal unsigned bi_reverse(code, len) 291728415Speter unsigned code; /* the value to invert */ 291828415Speter int len; /* its bit length */ 291928415Speter{ 292028415Speter register unsigned res = 0; 292128415Speter do { 292228415Speter res |= code & 1; 292328415Speter code >>= 1, res <<= 1; 292428415Speter } while (--len > 0); 292528415Speter return res >> 1; 292628415Speter} 292728415Speter 292828415Speter/* =========================================================================== 292928415Speter * Flush the bit buffer, keeping at most 7 bits in it. 293028415Speter */ 293128415Speterlocal void bi_flush(s) 293228415Speter deflate_state *s; 293328415Speter{ 293428415Speter if (s->bi_valid == 16) { 293528415Speter put_short(s, s->bi_buf); 293628415Speter s->bi_buf = 0; 293728415Speter s->bi_valid = 0; 293828415Speter } else if (s->bi_valid >= 8) { 293928415Speter put_byte(s, (Byte)s->bi_buf); 294028415Speter s->bi_buf >>= 8; 294128415Speter s->bi_valid -= 8; 294228415Speter } 294328415Speter} 294428415Speter 294528415Speter/* =========================================================================== 294628415Speter * Flush the bit buffer and align the output on a byte boundary 294728415Speter */ 294828415Speterlocal void bi_windup(s) 294928415Speter deflate_state *s; 295028415Speter{ 295128415Speter if (s->bi_valid > 8) { 295228415Speter put_short(s, s->bi_buf); 295328415Speter } else if (s->bi_valid > 0) { 295428415Speter put_byte(s, (Byte)s->bi_buf); 295528415Speter } 295628415Speter s->bi_buf = 0; 295728415Speter s->bi_valid = 0; 295828415Speter#ifdef DEBUG_ZLIB 295928415Speter s->bits_sent = (s->bits_sent+7) & ~7; 296028415Speter#endif 296128415Speter} 296228415Speter 296328415Speter/* =========================================================================== 296428415Speter * Copy a stored block, storing first the length and its 296528415Speter * one's complement if requested. 296628415Speter */ 296728415Speterlocal void copy_block(s, buf, len, header) 296828415Speter deflate_state *s; 296928415Speter charf *buf; /* the input data */ 297028415Speter unsigned len; /* its length */ 297128415Speter int header; /* true if block header must be written */ 297228415Speter{ 297328415Speter bi_windup(s); /* align on byte boundary */ 297428415Speter s->last_eob_len = 8; /* enough lookahead for inflate */ 297528415Speter 297628415Speter if (header) { 297728415Speter put_short(s, (ush)len); 297828415Speter put_short(s, (ush)~len); 297928415Speter#ifdef DEBUG_ZLIB 298028415Speter s->bits_sent += 2*16; 298128415Speter#endif 298228415Speter } 298328415Speter#ifdef DEBUG_ZLIB 298428415Speter s->bits_sent += (ulg)len<<3; 298528415Speter#endif 298634768Speter /* bundle up the put_byte(s, *buf++) calls */ 298734768Speter zmemcpy(&s->pending_buf[s->pending], buf, len); 298834768Speter s->pending += len; 298928415Speter} 299034768Speter/* --- trees.c */ 299128415Speter 299234768Speter/* +++ inflate.c */ 299334768Speter/* inflate.c -- zlib interface to inflate modules 299434768Speter * Copyright (C) 1995-1996 Mark Adler 299534768Speter * For conditions of distribution and use, see copyright notice in zlib.h 299634768Speter */ 299728415Speter 299834768Speter/* #include "zutil.h" */ 299934768Speter 300034768Speter/* +++ infblock.h */ 300128415Speter/* infblock.h -- header to use infblock.c 300234768Speter * Copyright (C) 1995-1996 Mark Adler 300328415Speter * For conditions of distribution and use, see copyright notice in zlib.h 300428415Speter */ 300528415Speter 300628415Speter/* WARNING: this file should *not* be used by applications. It is 300728415Speter part of the implementation of the compression library and is 300828415Speter subject to change. Applications should only use zlib.h. 300928415Speter */ 301028415Speter 301128415Speterstruct inflate_blocks_state; 301228415Spetertypedef struct inflate_blocks_state FAR inflate_blocks_statef; 301328415Speter 301434768Speterextern inflate_blocks_statef * inflate_blocks_new OF(( 301534768Speter z_streamp z, 301628415Speter check_func c, /* check function */ 301728415Speter uInt w)); /* window size */ 301828415Speter 301934768Speterextern int inflate_blocks OF(( 302028415Speter inflate_blocks_statef *, 302134768Speter z_streamp , 302228415Speter int)); /* initial return code */ 302328415Speter 302434768Speterextern void inflate_blocks_reset OF(( 302528415Speter inflate_blocks_statef *, 302634768Speter z_streamp , 302728415Speter uLongf *)); /* check value on output */ 302828415Speter 302934768Speterextern int inflate_blocks_free OF(( 303028415Speter inflate_blocks_statef *, 303134768Speter z_streamp , 303228415Speter uLongf *)); /* check value on output */ 303328415Speter 303434768Speterextern void inflate_set_dictionary OF(( 303534768Speter inflate_blocks_statef *s, 303634768Speter const Bytef *d, /* dictionary */ 303734768Speter uInt n)); /* dictionary length */ 303834768Speter 303934768Speterextern int inflate_addhistory OF(( 304028415Speter inflate_blocks_statef *, 304134768Speter z_streamp)); 304228415Speter 304334768Speterextern int inflate_packet_flush OF(( 304428415Speter inflate_blocks_statef *)); 304534768Speter/* --- infblock.h */ 304628415Speter 304734768Speter#ifndef NO_DUMMY_DECL 304834768Speterstruct inflate_blocks_state {int dummy;}; /* for buggy compilers */ 304928415Speter#endif 305028415Speter 305128415Speter/* inflate private state */ 305228415Speterstruct internal_state { 305328415Speter 305428415Speter /* mode */ 305528415Speter enum { 305628415Speter METHOD, /* waiting for method byte */ 305728415Speter FLAG, /* waiting for flag byte */ 305834768Speter DICT4, /* four dictionary check bytes to go */ 305934768Speter DICT3, /* three dictionary check bytes to go */ 306034768Speter DICT2, /* two dictionary check bytes to go */ 306134768Speter DICT1, /* one dictionary check byte to go */ 306234768Speter DICT0, /* waiting for inflateSetDictionary */ 306328415Speter BLOCKS, /* decompressing blocks */ 306428415Speter CHECK4, /* four check bytes to go */ 306528415Speter CHECK3, /* three check bytes to go */ 306628415Speter CHECK2, /* two check bytes to go */ 306728415Speter CHECK1, /* one check byte to go */ 306828415Speter DONE, /* finished check, done */ 306928415Speter BAD} /* got an error--stay here */ 307028415Speter mode; /* current inflate mode */ 307128415Speter 307228415Speter /* mode dependent information */ 307328415Speter union { 307428415Speter uInt method; /* if FLAGS, method byte */ 307528415Speter struct { 307628415Speter uLong was; /* computed check value */ 307728415Speter uLong need; /* stream check value */ 307828415Speter } check; /* if CHECK, check values to compare */ 307928415Speter uInt marker; /* if BAD, inflateSync's marker bytes count */ 308028415Speter } sub; /* submode */ 308128415Speter 308228415Speter /* mode independent information */ 308328415Speter int nowrap; /* flag for no wrapper */ 308428415Speter uInt wbits; /* log2(window size) (8..15, defaults to 15) */ 308528415Speter inflate_blocks_statef 308628415Speter *blocks; /* current inflate_blocks state */ 308728415Speter 308828415Speter}; 308928415Speter 309028415Speter 309128415Speterint inflateReset(z) 309234768Speterz_streamp z; 309328415Speter{ 309428415Speter uLong c; 309528415Speter 309628415Speter if (z == Z_NULL || z->state == Z_NULL) 309728415Speter return Z_STREAM_ERROR; 309828415Speter z->total_in = z->total_out = 0; 309928415Speter z->msg = Z_NULL; 310028415Speter z->state->mode = z->state->nowrap ? BLOCKS : METHOD; 310128415Speter inflate_blocks_reset(z->state->blocks, z, &c); 310228415Speter Trace((stderr, "inflate: reset\n")); 310328415Speter return Z_OK; 310428415Speter} 310528415Speter 310628415Speter 310728415Speterint inflateEnd(z) 310834768Speterz_streamp z; 310928415Speter{ 311028415Speter uLong c; 311128415Speter 311228415Speter if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL) 311328415Speter return Z_STREAM_ERROR; 311428415Speter if (z->state->blocks != Z_NULL) 311528415Speter inflate_blocks_free(z->state->blocks, z, &c); 311634768Speter ZFREE(z, z->state); 311728415Speter z->state = Z_NULL; 311828415Speter Trace((stderr, "inflate: end\n")); 311928415Speter return Z_OK; 312028415Speter} 312128415Speter 312228415Speter 312334768Speterint inflateInit2_(z, w, version, stream_size) 312434768Speterz_streamp z; 312528415Speterint w; 312634768Speterconst char *version; 312734768Speterint stream_size; 312828415Speter{ 312934768Speter if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 313034768Speter stream_size != sizeof(z_stream)) 313134768Speter return Z_VERSION_ERROR; 313234768Speter 313328415Speter /* initialize state */ 313428415Speter if (z == Z_NULL) 313528415Speter return Z_STREAM_ERROR; 313634768Speter z->msg = Z_NULL; 313734768Speter#ifndef NO_ZCFUNCS 313834768Speter if (z->zalloc == Z_NULL) 313934768Speter { 314034768Speter z->zalloc = zcalloc; 314134768Speter z->opaque = (voidpf)0; 314234768Speter } 314334768Speter if (z->zfree == Z_NULL) z->zfree = zcfree; 314434768Speter#endif 314528415Speter if ((z->state = (struct internal_state FAR *) 314634768Speter ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL) 314728415Speter return Z_MEM_ERROR; 314828415Speter z->state->blocks = Z_NULL; 314928415Speter 315028415Speter /* handle undocumented nowrap option (no zlib header or check) */ 315128415Speter z->state->nowrap = 0; 315228415Speter if (w < 0) 315328415Speter { 315428415Speter w = - w; 315528415Speter z->state->nowrap = 1; 315628415Speter } 315728415Speter 315828415Speter /* set window size */ 315928415Speter if (w < 8 || w > 15) 316028415Speter { 316128415Speter inflateEnd(z); 316228415Speter return Z_STREAM_ERROR; 316328415Speter } 316428415Speter z->state->wbits = (uInt)w; 316528415Speter 316628415Speter /* create inflate_blocks state */ 316728415Speter if ((z->state->blocks = 316834768Speter inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, (uInt)1 << w)) 316928415Speter == Z_NULL) 317028415Speter { 317128415Speter inflateEnd(z); 317228415Speter return Z_MEM_ERROR; 317328415Speter } 317428415Speter Trace((stderr, "inflate: allocated\n")); 317528415Speter 317628415Speter /* reset state */ 317728415Speter inflateReset(z); 317828415Speter return Z_OK; 317928415Speter} 318028415Speter 318128415Speter 318234768Speterint inflateInit_(z, version, stream_size) 318334768Speterz_streamp z; 318434768Speterconst char *version; 318534768Speterint stream_size; 318628415Speter{ 318734768Speter return inflateInit2_(z, DEF_WBITS, version, stream_size); 318828415Speter} 318928415Speter 319028415Speter 319128415Speter#define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;} 319228415Speter#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++) 319328415Speter 319428415Speterint inflate(z, f) 319534768Speterz_streamp z; 319628415Speterint f; 319728415Speter{ 319828415Speter int r; 319928415Speter uInt b; 320028415Speter 320134768Speter if (z == Z_NULL || z->state == Z_NULL || z->next_in == Z_NULL || f < 0) 320228415Speter return Z_STREAM_ERROR; 320328415Speter r = Z_BUF_ERROR; 320428415Speter while (1) switch (z->state->mode) 320528415Speter { 320628415Speter case METHOD: 320728415Speter NEEDBYTE 320834768Speter if (((z->state->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED) 320928415Speter { 321028415Speter z->state->mode = BAD; 321134768Speter z->msg = (char*)"unknown compression method"; 321228415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 321328415Speter break; 321428415Speter } 321528415Speter if ((z->state->sub.method >> 4) + 8 > z->state->wbits) 321628415Speter { 321728415Speter z->state->mode = BAD; 321834768Speter z->msg = (char*)"invalid window size"; 321928415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 322028415Speter break; 322128415Speter } 322228415Speter z->state->mode = FLAG; 322328415Speter case FLAG: 322428415Speter NEEDBYTE 322534768Speter b = NEXTBYTE; 322634768Speter if (((z->state->sub.method << 8) + b) % 31) 322728415Speter { 322828415Speter z->state->mode = BAD; 322934768Speter z->msg = (char*)"incorrect header check"; 323028415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 323128415Speter break; 323228415Speter } 323334768Speter Trace((stderr, "inflate: zlib header ok\n")); 323434768Speter if (!(b & PRESET_DICT)) 323528415Speter { 323634768Speter z->state->mode = BLOCKS; 323734768Speter break; 323828415Speter } 323934768Speter z->state->mode = DICT4; 324034768Speter case DICT4: 324134768Speter NEEDBYTE 324234768Speter z->state->sub.check.need = (uLong)NEXTBYTE << 24; 324334768Speter z->state->mode = DICT3; 324434768Speter case DICT3: 324534768Speter NEEDBYTE 324634768Speter z->state->sub.check.need += (uLong)NEXTBYTE << 16; 324734768Speter z->state->mode = DICT2; 324834768Speter case DICT2: 324934768Speter NEEDBYTE 325034768Speter z->state->sub.check.need += (uLong)NEXTBYTE << 8; 325134768Speter z->state->mode = DICT1; 325234768Speter case DICT1: 325334768Speter NEEDBYTE 325434768Speter z->state->sub.check.need += (uLong)NEXTBYTE; 325534768Speter z->adler = z->state->sub.check.need; 325634768Speter z->state->mode = DICT0; 325734768Speter return Z_NEED_DICT; 325834768Speter case DICT0: 325934768Speter z->state->mode = BAD; 326034768Speter z->msg = (char*)"need dictionary"; 326134768Speter z->state->sub.marker = 0; /* can try inflateSync */ 326234768Speter return Z_STREAM_ERROR; 326328415Speter case BLOCKS: 326428415Speter r = inflate_blocks(z->state->blocks, z, r); 326528415Speter if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0) 326628415Speter r = inflate_packet_flush(z->state->blocks); 326728415Speter if (r == Z_DATA_ERROR) 326828415Speter { 326928415Speter z->state->mode = BAD; 327028415Speter z->state->sub.marker = 0; /* can try inflateSync */ 327128415Speter break; 327228415Speter } 327328415Speter if (r != Z_STREAM_END) 327428415Speter return r; 327528415Speter r = Z_OK; 327628415Speter inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was); 327728415Speter if (z->state->nowrap) 327828415Speter { 327928415Speter z->state->mode = DONE; 328028415Speter break; 328128415Speter } 328228415Speter z->state->mode = CHECK4; 328328415Speter case CHECK4: 328428415Speter NEEDBYTE 328528415Speter z->state->sub.check.need = (uLong)NEXTBYTE << 24; 328628415Speter z->state->mode = CHECK3; 328728415Speter case CHECK3: 328828415Speter NEEDBYTE 328928415Speter z->state->sub.check.need += (uLong)NEXTBYTE << 16; 329028415Speter z->state->mode = CHECK2; 329128415Speter case CHECK2: 329228415Speter NEEDBYTE 329328415Speter z->state->sub.check.need += (uLong)NEXTBYTE << 8; 329428415Speter z->state->mode = CHECK1; 329528415Speter case CHECK1: 329628415Speter NEEDBYTE 329728415Speter z->state->sub.check.need += (uLong)NEXTBYTE; 329828415Speter 329928415Speter if (z->state->sub.check.was != z->state->sub.check.need) 330028415Speter { 330128415Speter z->state->mode = BAD; 330234768Speter z->msg = (char*)"incorrect data check"; 330328415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 330428415Speter break; 330528415Speter } 330628415Speter Trace((stderr, "inflate: zlib check ok\n")); 330728415Speter z->state->mode = DONE; 330828415Speter case DONE: 330928415Speter return Z_STREAM_END; 331028415Speter case BAD: 331128415Speter return Z_DATA_ERROR; 331228415Speter default: 331328415Speter return Z_STREAM_ERROR; 331428415Speter } 331528415Speter 331628415Speter empty: 331728415Speter if (f != Z_PACKET_FLUSH) 331828415Speter return r; 331928415Speter z->state->mode = BAD; 332034768Speter z->msg = (char *)"need more for packet flush"; 332128415Speter z->state->sub.marker = 0; /* can try inflateSync */ 332228415Speter return Z_DATA_ERROR; 332328415Speter} 332428415Speter 332534768Speter 332634768Speterint inflateSetDictionary(z, dictionary, dictLength) 332734768Speterz_streamp z; 332834768Speterconst Bytef *dictionary; 332934768SpeteruInt dictLength; 333034768Speter{ 333134768Speter uInt length = dictLength; 333234768Speter 333334768Speter if (z == Z_NULL || z->state == Z_NULL || z->state->mode != DICT0) 333434768Speter return Z_STREAM_ERROR; 333534768Speter 333634768Speter if (adler32(1L, dictionary, dictLength) != z->adler) return Z_DATA_ERROR; 333734768Speter z->adler = 1L; 333834768Speter 333934768Speter if (length >= ((uInt)1<<z->state->wbits)) 334034768Speter { 334134768Speter length = (1<<z->state->wbits)-1; 334234768Speter dictionary += dictLength - length; 334334768Speter } 334434768Speter inflate_set_dictionary(z->state->blocks, dictionary, length); 334534768Speter z->state->mode = BLOCKS; 334634768Speter return Z_OK; 334734768Speter} 334834768Speter 334928415Speter/* 335028415Speter * This subroutine adds the data at next_in/avail_in to the output history 335128415Speter * without performing any output. The output buffer must be "caught up"; 335228415Speter * i.e. no pending output (hence s->read equals s->write), and the state must 335328415Speter * be BLOCKS (i.e. we should be willing to see the start of a series of 335428415Speter * BLOCKS). On exit, the output will also be caught up, and the checksum 335528415Speter * will have been updated if need be. 335628415Speter */ 335728415Speter 335828415Speterint inflateIncomp(z) 335928415Speterz_stream *z; 336028415Speter{ 336128415Speter if (z->state->mode != BLOCKS) 336228415Speter return Z_DATA_ERROR; 336328415Speter return inflate_addhistory(z->state->blocks, z); 336428415Speter} 336528415Speter 336628415Speter 336728415Speterint inflateSync(z) 336834768Speterz_streamp z; 336928415Speter{ 337028415Speter uInt n; /* number of bytes to look at */ 337128415Speter Bytef *p; /* pointer to bytes */ 337228415Speter uInt m; /* number of marker bytes found in a row */ 337328415Speter uLong r, w; /* temporaries to save total_in and total_out */ 337428415Speter 337528415Speter /* set up */ 337628415Speter if (z == Z_NULL || z->state == Z_NULL) 337728415Speter return Z_STREAM_ERROR; 337828415Speter if (z->state->mode != BAD) 337928415Speter { 338028415Speter z->state->mode = BAD; 338128415Speter z->state->sub.marker = 0; 338228415Speter } 338328415Speter if ((n = z->avail_in) == 0) 338428415Speter return Z_BUF_ERROR; 338528415Speter p = z->next_in; 338628415Speter m = z->state->sub.marker; 338728415Speter 338828415Speter /* search */ 338928415Speter while (n && m < 4) 339028415Speter { 339128415Speter if (*p == (Byte)(m < 2 ? 0 : 0xff)) 339228415Speter m++; 339328415Speter else if (*p) 339428415Speter m = 0; 339528415Speter else 339628415Speter m = 4 - m; 339728415Speter p++, n--; 339828415Speter } 339928415Speter 340028415Speter /* restore */ 340128415Speter z->total_in += p - z->next_in; 340228415Speter z->next_in = p; 340328415Speter z->avail_in = n; 340428415Speter z->state->sub.marker = m; 340528415Speter 340628415Speter /* return no joy or set up to restart on a new block */ 340728415Speter if (m != 4) 340828415Speter return Z_DATA_ERROR; 340928415Speter r = z->total_in; w = z->total_out; 341028415Speter inflateReset(z); 341128415Speter z->total_in = r; z->total_out = w; 341228415Speter z->state->mode = BLOCKS; 341328415Speter return Z_OK; 341428415Speter} 341528415Speter 341628415Speter#undef NEEDBYTE 341728415Speter#undef NEXTBYTE 341834768Speter/* --- inflate.c */ 341928415Speter 342034768Speter/* +++ infblock.c */ 342134768Speter/* infblock.c -- interpret and process block types to last block 342234768Speter * Copyright (C) 1995-1996 Mark Adler 342334768Speter * For conditions of distribution and use, see copyright notice in zlib.h 342434768Speter */ 342534768Speter 342634768Speter/* #include "zutil.h" */ 342734768Speter/* #include "infblock.h" */ 342834768Speter 342934768Speter/* +++ inftrees.h */ 343034768Speter/* inftrees.h -- header to use inftrees.c 343134768Speter * Copyright (C) 1995-1996 Mark Adler 343234768Speter * For conditions of distribution and use, see copyright notice in zlib.h 343334768Speter */ 343434768Speter 343534768Speter/* WARNING: this file should *not* be used by applications. It is 343634768Speter part of the implementation of the compression library and is 343734768Speter subject to change. Applications should only use zlib.h. 343834768Speter */ 343934768Speter 344034768Speter/* Huffman code lookup table entry--this entry is four bytes for machines 344134768Speter that have 16-bit pointers (e.g. PC's in the small or medium model). */ 344234768Speter 344334768Spetertypedef struct inflate_huft_s FAR inflate_huft; 344434768Speter 344534768Speterstruct inflate_huft_s { 344634768Speter union { 344734768Speter struct { 344834768Speter Byte Exop; /* number of extra bits or operation */ 344934768Speter Byte Bits; /* number of bits in this code or subcode */ 345034768Speter } what; 345134768Speter Bytef *pad; /* pad structure to a power of 2 (4 bytes for */ 345234768Speter } word; /* 16-bit, 8 bytes for 32-bit machines) */ 345334768Speter union { 345434768Speter uInt Base; /* literal, length base, or distance base */ 345534768Speter inflate_huft *Next; /* pointer to next level of table */ 345634768Speter } more; 345734768Speter}; 345834768Speter 345934768Speter#ifdef DEBUG_ZLIB 346034768Speter extern uInt inflate_hufts; 346134768Speter#endif 346234768Speter 346334768Speterextern int inflate_trees_bits OF(( 346434768Speter uIntf *, /* 19 code lengths */ 346534768Speter uIntf *, /* bits tree desired/actual depth */ 346634768Speter inflate_huft * FAR *, /* bits tree result */ 346734768Speter z_streamp )); /* for zalloc, zfree functions */ 346834768Speter 346934768Speterextern int inflate_trees_dynamic OF(( 347034768Speter uInt, /* number of literal/length codes */ 347134768Speter uInt, /* number of distance codes */ 347234768Speter uIntf *, /* that many (total) code lengths */ 347334768Speter uIntf *, /* literal desired/actual bit depth */ 347434768Speter uIntf *, /* distance desired/actual bit depth */ 347534768Speter inflate_huft * FAR *, /* literal/length tree result */ 347634768Speter inflate_huft * FAR *, /* distance tree result */ 347734768Speter z_streamp )); /* for zalloc, zfree functions */ 347834768Speter 347934768Speterextern int inflate_trees_fixed OF(( 348034768Speter uIntf *, /* literal desired/actual bit depth */ 348134768Speter uIntf *, /* distance desired/actual bit depth */ 348234768Speter inflate_huft * FAR *, /* literal/length tree result */ 348334768Speter inflate_huft * FAR *)); /* distance tree result */ 348434768Speter 348534768Speterextern int inflate_trees_free OF(( 348634768Speter inflate_huft *, /* tables to free */ 348734768Speter z_streamp )); /* for zfree function */ 348834768Speter 348934768Speter/* --- inftrees.h */ 349034768Speter 349134768Speter/* +++ infcodes.h */ 349234768Speter/* infcodes.h -- header to use infcodes.c 349334768Speter * Copyright (C) 1995-1996 Mark Adler 349434768Speter * For conditions of distribution and use, see copyright notice in zlib.h 349534768Speter */ 349634768Speter 349734768Speter/* WARNING: this file should *not* be used by applications. It is 349834768Speter part of the implementation of the compression library and is 349934768Speter subject to change. Applications should only use zlib.h. 350034768Speter */ 350134768Speter 350234768Speterstruct inflate_codes_state; 350334768Spetertypedef struct inflate_codes_state FAR inflate_codes_statef; 350434768Speter 350534768Speterextern inflate_codes_statef *inflate_codes_new OF(( 350634768Speter uInt, uInt, 350734768Speter inflate_huft *, inflate_huft *, 350834768Speter z_streamp )); 350934768Speter 351034768Speterextern int inflate_codes OF(( 351134768Speter inflate_blocks_statef *, 351234768Speter z_streamp , 351334768Speter int)); 351434768Speter 351534768Speterextern void inflate_codes_free OF(( 351634768Speter inflate_codes_statef *, 351734768Speter z_streamp )); 351834768Speter 351934768Speter/* --- infcodes.h */ 352034768Speter 352134768Speter/* +++ infutil.h */ 352228415Speter/* infutil.h -- types and macros common to blocks and codes 352334768Speter * Copyright (C) 1995-1996 Mark Adler 352428415Speter * For conditions of distribution and use, see copyright notice in zlib.h 352528415Speter */ 352628415Speter 352728415Speter/* WARNING: this file should *not* be used by applications. It is 352828415Speter part of the implementation of the compression library and is 352928415Speter subject to change. Applications should only use zlib.h. 353028415Speter */ 353128415Speter 353234768Speter#ifndef _INFUTIL_H 353334768Speter#define _INFUTIL_H 353428415Speter 353534768Spetertypedef enum { 353628415Speter TYPE, /* get type bits (3, including end bit) */ 353728415Speter LENS, /* get lengths for stored */ 353828415Speter STORED, /* processing stored block */ 353928415Speter TABLE, /* get table lengths */ 354028415Speter BTREE, /* get bit lengths tree for a dynamic block */ 354128415Speter DTREE, /* get length, distance trees for a dynamic block */ 354228415Speter CODES, /* processing fixed or dynamic block */ 354328415Speter DRY, /* output remaining window bytes */ 354434768Speter DONEB, /* finished last block, done */ 354534768Speter BADB} /* got a data error--stuck here */ 354634768Speterinflate_block_mode; 354728415Speter 354834768Speter/* inflate blocks semi-private state */ 354934768Speterstruct inflate_blocks_state { 355034768Speter 355134768Speter /* mode */ 355234768Speter inflate_block_mode mode; /* current inflate_block mode */ 355334768Speter 355428415Speter /* mode dependent information */ 355528415Speter union { 355628415Speter uInt left; /* if STORED, bytes left to copy */ 355728415Speter struct { 355828415Speter uInt table; /* table lengths (14 bits) */ 355928415Speter uInt index; /* index into blens (or border) */ 356028415Speter uIntf *blens; /* bit lengths of codes */ 356128415Speter uInt bb; /* bit length tree depth */ 356228415Speter inflate_huft *tb; /* bit length decoding tree */ 356328415Speter } trees; /* if DTREE, decoding info for trees */ 356428415Speter struct { 356534768Speter inflate_huft *tl; 356634768Speter inflate_huft *td; /* trees to free */ 356728415Speter inflate_codes_statef 356828415Speter *codes; 356928415Speter } decode; /* if CODES, current state */ 357028415Speter } sub; /* submode */ 357128415Speter uInt last; /* true if this block is the last block */ 357228415Speter 357328415Speter /* mode independent information */ 357428415Speter uInt bitk; /* bits in bit buffer */ 357528415Speter uLong bitb; /* bit buffer */ 357628415Speter Bytef *window; /* sliding window */ 357728415Speter Bytef *end; /* one byte after sliding window */ 357828415Speter Bytef *read; /* window read pointer */ 357928415Speter Bytef *write; /* window write pointer */ 358028415Speter check_func checkfn; /* check function */ 358128415Speter uLong check; /* check on output */ 358228415Speter 358328415Speter}; 358428415Speter 358528415Speter 358628415Speter/* defines for inflate input/output */ 358728415Speter/* update pointers and return */ 358828415Speter#define UPDBITS {s->bitb=b;s->bitk=k;} 358928415Speter#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;} 359028415Speter#define UPDOUT {s->write=q;} 359128415Speter#define UPDATE {UPDBITS UPDIN UPDOUT} 359228415Speter#define LEAVE {UPDATE return inflate_flush(s,z,r);} 359328415Speter/* get bytes and bits */ 359428415Speter#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;} 359528415Speter#define NEEDBYTE {if(n)r=Z_OK;else LEAVE} 359628415Speter#define NEXTBYTE (n--,*p++) 359728415Speter#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}} 359828415Speter#define DUMPBITS(j) {b>>=(j);k-=(j);} 359928415Speter/* output bytes */ 360034768Speter#define WAVAIL (uInt)(q<s->read?s->read-q-1:s->end-q) 360134768Speter#define LOADOUT {q=s->write;m=(uInt)WAVAIL;} 360234768Speter#define WWRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}} 360328415Speter#define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT} 360434768Speter#define NEEDOUT {if(m==0){WWRAP if(m==0){FLUSH WWRAP if(m==0) LEAVE}}r=Z_OK;} 360528415Speter#define OUTBYTE(a) {*q++=(Byte)(a);m--;} 360628415Speter/* load local pointers */ 360728415Speter#define LOAD {LOADIN LOADOUT} 360828415Speter 360934768Speter/* masks for lower bits (size given to avoid silly warnings with Visual C++) */ 361034768Speterextern uInt inflate_mask[17]; 361128415Speter 361228415Speter/* copy as much as possible from the sliding window to the output area */ 361334768Speterextern int inflate_flush OF(( 361428415Speter inflate_blocks_statef *, 361534768Speter z_streamp , 361628415Speter int)); 361728415Speter 361834768Speter#ifndef NO_DUMMY_DECL 361934768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 362034768Speter#endif 362128415Speter 362234768Speter#endif 362334768Speter/* --- infutil.h */ 362428415Speter 362534768Speter#ifndef NO_DUMMY_DECL 362634768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 362734768Speter#endif 362828415Speter 362928415Speter/* Table for deflate from PKZIP's appnote.txt. */ 363034768Speterlocal const uInt border[] = { /* Order of the bit length code lengths */ 363128415Speter 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 363228415Speter 363328415Speter/* 363428415Speter Notes beyond the 1.93a appnote.txt: 363528415Speter 363628415Speter 1. Distance pointers never point before the beginning of the output 363728415Speter stream. 363828415Speter 2. Distance pointers can point back across blocks, up to 32k away. 363928415Speter 3. There is an implied maximum of 7 bits for the bit length table and 364028415Speter 15 bits for the actual data. 364128415Speter 4. If only one code exists, then it is encoded using one bit. (Zero 364228415Speter would be more efficient, but perhaps a little confusing.) If two 364328415Speter codes exist, they are coded using one bit each (0 and 1). 364428415Speter 5. There is no way of sending zero distance codes--a dummy must be 364528415Speter sent if there are none. (History: a pre 2.0 version of PKZIP would 364628415Speter store blocks with no distance codes, but this was discovered to be 364728415Speter too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 364828415Speter zero distance codes, which is sent as one code of zero bits in 364928415Speter length. 365028415Speter 6. There are up to 286 literal/length codes. Code 256 represents the 365128415Speter end-of-block. Note however that the static length tree defines 365228415Speter 288 codes just to fill out the Huffman codes. Codes 286 and 287 365328415Speter cannot be used though, since there is no length base or extra bits 365428415Speter defined for them. Similarily, there are up to 30 distance codes. 365528415Speter However, static trees define 32 codes (all 5 bits) to fill out the 365628415Speter Huffman codes, but the last two had better not show up in the data. 365728415Speter 7. Unzip can check dynamic Huffman blocks for complete code sets. 365828415Speter The exception is that a single code would not be complete (see #4). 365928415Speter 8. The five bits following the block type is really the number of 366028415Speter literal codes sent minus 257. 366128415Speter 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 366228415Speter (1+6+6). Therefore, to output three times the length, you output 366328415Speter three codes (1+1+1), whereas to output four times the same length, 366428415Speter you only need two codes (1+3). Hmm. 366528415Speter 10. In the tree reconstruction algorithm, Code = Code + Increment 366628415Speter only if BitLength(i) is not zero. (Pretty obvious.) 366728415Speter 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 366828415Speter 12. Note: length code 284 can represent 227-258, but length code 285 366928415Speter really is 258. The last length deserves its own, short code 367028415Speter since it gets used a lot in very redundant files. The length 367128415Speter 258 is special since 258 - 3 (the min match length) is 255. 367228415Speter 13. The literal/length and distance code bit lengths are read as a 367328415Speter single stream of lengths. It is possible (and advantageous) for 367428415Speter a repeat code (16, 17, or 18) to go across the boundary between 367528415Speter the two sets of lengths. 367628415Speter */ 367728415Speter 367828415Speter 367934768Spetervoid inflate_blocks_reset(s, z, c) 368028415Speterinflate_blocks_statef *s; 368134768Speterz_streamp z; 368228415SpeteruLongf *c; 368328415Speter{ 368428415Speter if (s->checkfn != Z_NULL) 368528415Speter *c = s->check; 368628415Speter if (s->mode == BTREE || s->mode == DTREE) 368734768Speter ZFREE(z, s->sub.trees.blens); 368828415Speter if (s->mode == CODES) 368928415Speter { 369028415Speter inflate_codes_free(s->sub.decode.codes, z); 369128415Speter inflate_trees_free(s->sub.decode.td, z); 369228415Speter inflate_trees_free(s->sub.decode.tl, z); 369328415Speter } 369428415Speter s->mode = TYPE; 369528415Speter s->bitk = 0; 369628415Speter s->bitb = 0; 369728415Speter s->read = s->write = s->window; 369828415Speter if (s->checkfn != Z_NULL) 369934768Speter z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0); 370028415Speter Trace((stderr, "inflate: blocks reset\n")); 370128415Speter} 370228415Speter 370328415Speter 370434768Speterinflate_blocks_statef *inflate_blocks_new(z, c, w) 370534768Speterz_streamp z; 370628415Spetercheck_func c; 370728415SpeteruInt w; 370828415Speter{ 370928415Speter inflate_blocks_statef *s; 371028415Speter 371134768Speter if ((s = (inflate_blocks_statef *)ZALLOC 371228415Speter (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) 371328415Speter return s; 371434768Speter if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) 371528415Speter { 371634768Speter ZFREE(z, s); 371728415Speter return Z_NULL; 371828415Speter } 371928415Speter s->end = s->window + w; 372028415Speter s->checkfn = c; 372128415Speter s->mode = TYPE; 372228415Speter Trace((stderr, "inflate: blocks allocated\n")); 372328415Speter inflate_blocks_reset(s, z, &s->check); 372428415Speter return s; 372528415Speter} 372628415Speter 372728415Speter 372834768Speter#ifdef DEBUG_ZLIB 372934768Speter extern uInt inflate_hufts; 373034768Speter#endif 373134768Speterint inflate_blocks(s, z, r) 373228415Speterinflate_blocks_statef *s; 373334768Speterz_streamp z; 373428415Speterint r; 373528415Speter{ 373628415Speter uInt t; /* temporary storage */ 373728415Speter uLong b; /* bit buffer */ 373828415Speter uInt k; /* bits in bit buffer */ 373928415Speter Bytef *p; /* input data pointer */ 374028415Speter uInt n; /* bytes available there */ 374128415Speter Bytef *q; /* output window write pointer */ 374228415Speter uInt m; /* bytes to end of window or read pointer */ 374328415Speter 374428415Speter /* copy input/output information to locals (UPDATE macro restores) */ 374528415Speter LOAD 374628415Speter 374728415Speter /* process input based on current state */ 374828415Speter while (1) switch (s->mode) 374928415Speter { 375028415Speter case TYPE: 375128415Speter NEEDBITS(3) 375228415Speter t = (uInt)b & 7; 375328415Speter s->last = t & 1; 375428415Speter switch (t >> 1) 375528415Speter { 375628415Speter case 0: /* stored */ 375728415Speter Trace((stderr, "inflate: stored block%s\n", 375828415Speter s->last ? " (last)" : "")); 375928415Speter DUMPBITS(3) 376028415Speter t = k & 7; /* go to byte boundary */ 376128415Speter DUMPBITS(t) 376228415Speter s->mode = LENS; /* get length of stored block */ 376328415Speter break; 376428415Speter case 1: /* fixed */ 376528415Speter Trace((stderr, "inflate: fixed codes block%s\n", 376628415Speter s->last ? " (last)" : "")); 376728415Speter { 376828415Speter uInt bl, bd; 376928415Speter inflate_huft *tl, *td; 377028415Speter 377128415Speter inflate_trees_fixed(&bl, &bd, &tl, &td); 377228415Speter s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); 377328415Speter if (s->sub.decode.codes == Z_NULL) 377428415Speter { 377528415Speter r = Z_MEM_ERROR; 377628415Speter LEAVE 377728415Speter } 377828415Speter s->sub.decode.tl = Z_NULL; /* don't try to free these */ 377928415Speter s->sub.decode.td = Z_NULL; 378028415Speter } 378128415Speter DUMPBITS(3) 378228415Speter s->mode = CODES; 378328415Speter break; 378428415Speter case 2: /* dynamic */ 378528415Speter Trace((stderr, "inflate: dynamic codes block%s\n", 378628415Speter s->last ? " (last)" : "")); 378728415Speter DUMPBITS(3) 378828415Speter s->mode = TABLE; 378928415Speter break; 379028415Speter case 3: /* illegal */ 379128415Speter DUMPBITS(3) 379228415Speter s->mode = BADB; 379334768Speter z->msg = (char*)"invalid block type"; 379428415Speter r = Z_DATA_ERROR; 379528415Speter LEAVE 379628415Speter } 379728415Speter break; 379828415Speter case LENS: 379928415Speter NEEDBITS(32) 380034768Speter if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) 380128415Speter { 380228415Speter s->mode = BADB; 380334768Speter z->msg = (char*)"invalid stored block lengths"; 380428415Speter r = Z_DATA_ERROR; 380528415Speter LEAVE 380628415Speter } 380728415Speter s->sub.left = (uInt)b & 0xffff; 380828415Speter b = k = 0; /* dump bits */ 380928415Speter Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); 381034768Speter s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); 381128415Speter break; 381228415Speter case STORED: 381328415Speter if (n == 0) 381428415Speter LEAVE 381528415Speter NEEDOUT 381628415Speter t = s->sub.left; 381728415Speter if (t > n) t = n; 381828415Speter if (t > m) t = m; 381928415Speter zmemcpy(q, p, t); 382028415Speter p += t; n -= t; 382128415Speter q += t; m -= t; 382228415Speter if ((s->sub.left -= t) != 0) 382328415Speter break; 382428415Speter Tracev((stderr, "inflate: stored end, %lu total out\n", 382528415Speter z->total_out + (q >= s->read ? q - s->read : 382628415Speter (s->end - s->read) + (q - s->window)))); 382728415Speter s->mode = s->last ? DRY : TYPE; 382828415Speter break; 382928415Speter case TABLE: 383028415Speter NEEDBITS(14) 383128415Speter s->sub.trees.table = t = (uInt)b & 0x3fff; 383228415Speter#ifndef PKZIP_BUG_WORKAROUND 383328415Speter if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) 383428415Speter { 383528415Speter s->mode = BADB; 383634768Speter z->msg = (char*)"too many length or distance symbols"; 383728415Speter r = Z_DATA_ERROR; 383828415Speter LEAVE 383928415Speter } 384028415Speter#endif 384128415Speter t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); 384228415Speter if (t < 19) 384328415Speter t = 19; 384428415Speter if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) 384528415Speter { 384628415Speter r = Z_MEM_ERROR; 384728415Speter LEAVE 384828415Speter } 384928415Speter DUMPBITS(14) 385028415Speter s->sub.trees.index = 0; 385128415Speter Tracev((stderr, "inflate: table sizes ok\n")); 385228415Speter s->mode = BTREE; 385328415Speter case BTREE: 385428415Speter while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) 385528415Speter { 385628415Speter NEEDBITS(3) 385728415Speter s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; 385828415Speter DUMPBITS(3) 385928415Speter } 386028415Speter while (s->sub.trees.index < 19) 386128415Speter s->sub.trees.blens[border[s->sub.trees.index++]] = 0; 386228415Speter s->sub.trees.bb = 7; 386328415Speter t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, 386428415Speter &s->sub.trees.tb, z); 386528415Speter if (t != Z_OK) 386628415Speter { 386728415Speter r = t; 386890775Sjedgar if (r == Z_DATA_ERROR) { 386990775Sjedgar ZFREE(z, s->sub.trees.blens); 387028415Speter s->mode = BADB; 387190775Sjedgar } 387228415Speter LEAVE 387328415Speter } 387428415Speter s->sub.trees.index = 0; 387528415Speter Tracev((stderr, "inflate: bits tree ok\n")); 387628415Speter s->mode = DTREE; 387728415Speter case DTREE: 387828415Speter while (t = s->sub.trees.table, 387928415Speter s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) 388028415Speter { 388128415Speter inflate_huft *h; 388228415Speter uInt i, j, c; 388328415Speter 388428415Speter t = s->sub.trees.bb; 388528415Speter NEEDBITS(t) 388628415Speter h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); 388728415Speter t = h->word.what.Bits; 388828415Speter c = h->more.Base; 388928415Speter if (c < 16) 389028415Speter { 389128415Speter DUMPBITS(t) 389228415Speter s->sub.trees.blens[s->sub.trees.index++] = c; 389328415Speter } 389428415Speter else /* c == 16..18 */ 389528415Speter { 389628415Speter i = c == 18 ? 7 : c - 14; 389728415Speter j = c == 18 ? 11 : 3; 389828415Speter NEEDBITS(t + i) 389928415Speter DUMPBITS(t) 390028415Speter j += (uInt)b & inflate_mask[i]; 390128415Speter DUMPBITS(i) 390228415Speter i = s->sub.trees.index; 390328415Speter t = s->sub.trees.table; 390428415Speter if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || 390528415Speter (c == 16 && i < 1)) 390628415Speter { 390734768Speter inflate_trees_free(s->sub.trees.tb, z); 390834768Speter ZFREE(z, s->sub.trees.blens); 390928415Speter s->mode = BADB; 391034768Speter z->msg = (char*)"invalid bit length repeat"; 391128415Speter r = Z_DATA_ERROR; 391228415Speter LEAVE 391328415Speter } 391428415Speter c = c == 16 ? s->sub.trees.blens[i - 1] : 0; 391528415Speter do { 391628415Speter s->sub.trees.blens[i++] = c; 391728415Speter } while (--j); 391828415Speter s->sub.trees.index = i; 391928415Speter } 392028415Speter } 392128415Speter inflate_trees_free(s->sub.trees.tb, z); 392228415Speter s->sub.trees.tb = Z_NULL; 392328415Speter { 392428415Speter uInt bl, bd; 392528415Speter inflate_huft *tl, *td; 392628415Speter inflate_codes_statef *c; 392728415Speter 392828415Speter bl = 9; /* must be <= 9 for lookahead assumptions */ 392928415Speter bd = 6; /* must be <= 9 for lookahead assumptions */ 393028415Speter t = s->sub.trees.table; 393134768Speter#ifdef DEBUG_ZLIB 393234768Speter inflate_hufts = 0; 393334768Speter#endif 393428415Speter t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), 393528415Speter s->sub.trees.blens, &bl, &bd, &tl, &td, z); 393628415Speter if (t != Z_OK) 393728415Speter { 393890775Sjedgar if (t == (uInt)Z_DATA_ERROR) { 393990775Sjedgar ZFREE(z, s->sub.trees.blens); 394028415Speter s->mode = BADB; 394190775Sjedgar } 394228415Speter r = t; 394328415Speter LEAVE 394428415Speter } 394534768Speter Tracev((stderr, "inflate: trees ok, %d * %d bytes used\n", 394634768Speter inflate_hufts, sizeof(inflate_huft))); 394728415Speter if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) 394828415Speter { 394928415Speter inflate_trees_free(td, z); 395028415Speter inflate_trees_free(tl, z); 395128415Speter r = Z_MEM_ERROR; 395228415Speter LEAVE 395328415Speter } 395428415Speter s->sub.decode.codes = c; 395528415Speter s->sub.decode.tl = tl; 395628415Speter s->sub.decode.td = td; 395728415Speter } 395890775Sjedgar ZFREE(z, s->sub.trees.blens); 395928415Speter s->mode = CODES; 396028415Speter case CODES: 396128415Speter UPDATE 396228415Speter if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) 396328415Speter return inflate_flush(s, z, r); 396428415Speter r = Z_OK; 396528415Speter inflate_codes_free(s->sub.decode.codes, z); 396628415Speter inflate_trees_free(s->sub.decode.td, z); 396728415Speter inflate_trees_free(s->sub.decode.tl, z); 396828415Speter LOAD 396928415Speter Tracev((stderr, "inflate: codes end, %lu total out\n", 397028415Speter z->total_out + (q >= s->read ? q - s->read : 397128415Speter (s->end - s->read) + (q - s->window)))); 397228415Speter if (!s->last) 397328415Speter { 397428415Speter s->mode = TYPE; 397528415Speter break; 397628415Speter } 397728415Speter if (k > 7) /* return unused byte, if any */ 397828415Speter { 397928415Speter Assert(k < 16, "inflate_codes grabbed too many bytes") 398028415Speter k -= 8; 398128415Speter n++; 398228415Speter p--; /* can always return one */ 398328415Speter } 398428415Speter s->mode = DRY; 398528415Speter case DRY: 398628415Speter FLUSH 398728415Speter if (s->read != s->write) 398828415Speter LEAVE 398928415Speter s->mode = DONEB; 399028415Speter case DONEB: 399128415Speter r = Z_STREAM_END; 399228415Speter LEAVE 399328415Speter case BADB: 399428415Speter r = Z_DATA_ERROR; 399528415Speter LEAVE 399628415Speter default: 399728415Speter r = Z_STREAM_ERROR; 399828415Speter LEAVE 399928415Speter } 400028415Speter} 400128415Speter 400228415Speter 400334768Speterint inflate_blocks_free(s, z, c) 400428415Speterinflate_blocks_statef *s; 400534768Speterz_streamp z; 400628415SpeteruLongf *c; 400728415Speter{ 400828415Speter inflate_blocks_reset(s, z, c); 400934768Speter ZFREE(z, s->window); 401034768Speter ZFREE(z, s); 401128415Speter Trace((stderr, "inflate: blocks freed\n")); 401228415Speter return Z_OK; 401328415Speter} 401428415Speter 401534768Speter 401634768Spetervoid inflate_set_dictionary(s, d, n) 401734768Speterinflate_blocks_statef *s; 401834768Speterconst Bytef *d; 401934768SpeteruInt n; 402034768Speter{ 402134768Speter zmemcpy((charf *)s->window, d, n); 402234768Speter s->read = s->write = s->window + n; 402334768Speter} 402434768Speter 402528415Speter/* 402628415Speter * This subroutine adds the data at next_in/avail_in to the output history 402728415Speter * without performing any output. The output buffer must be "caught up"; 402828415Speter * i.e. no pending output (hence s->read equals s->write), and the state must 402928415Speter * be BLOCKS (i.e. we should be willing to see the start of a series of 403028415Speter * BLOCKS). On exit, the output will also be caught up, and the checksum 403128415Speter * will have been updated if need be. 403228415Speter */ 403334768Speterint inflate_addhistory(s, z) 403428415Speterinflate_blocks_statef *s; 403528415Speterz_stream *z; 403628415Speter{ 403728415Speter uLong b; /* bit buffer */ /* NOT USED HERE */ 403828415Speter uInt k; /* bits in bit buffer */ /* NOT USED HERE */ 403928415Speter uInt t; /* temporary storage */ 404028415Speter Bytef *p; /* input data pointer */ 404128415Speter uInt n; /* bytes available there */ 404228415Speter Bytef *q; /* output window write pointer */ 404328415Speter uInt m; /* bytes to end of window or read pointer */ 404428415Speter 404528415Speter if (s->read != s->write) 404628415Speter return Z_STREAM_ERROR; 404728415Speter if (s->mode != TYPE) 404828415Speter return Z_DATA_ERROR; 404928415Speter 405028415Speter /* we're ready to rock */ 405128415Speter LOAD 405228415Speter /* while there is input ready, copy to output buffer, moving 405328415Speter * pointers as needed. 405428415Speter */ 405528415Speter while (n) { 405628415Speter t = n; /* how many to do */ 405728415Speter /* is there room until end of buffer? */ 405828415Speter if (t > m) t = m; 405928415Speter /* update check information */ 406028415Speter if (s->checkfn != Z_NULL) 406128415Speter s->check = (*s->checkfn)(s->check, q, t); 406228415Speter zmemcpy(q, p, t); 406328415Speter q += t; 406428415Speter p += t; 406528415Speter n -= t; 406628415Speter z->total_out += t; 406728415Speter s->read = q; /* drag read pointer forward */ 406834768Speter/* WWRAP */ /* expand WWRAP macro by hand to handle s->read */ 406928415Speter if (q == s->end) { 407028415Speter s->read = q = s->window; 407128415Speter m = WAVAIL; 407228415Speter } 407328415Speter } 407428415Speter UPDATE 407528415Speter return Z_OK; 407628415Speter} 407728415Speter 407828415Speter 407928415Speter/* 408028415Speter * At the end of a Deflate-compressed PPP packet, we expect to have seen 408128415Speter * a `stored' block type value but not the (zero) length bytes. 408228415Speter */ 408334768Speterint inflate_packet_flush(s) 408428415Speter inflate_blocks_statef *s; 408528415Speter{ 408628415Speter if (s->mode != LENS) 408728415Speter return Z_DATA_ERROR; 408828415Speter s->mode = TYPE; 408928415Speter return Z_OK; 409028415Speter} 409134768Speter/* --- infblock.c */ 409228415Speter 409334768Speter/* +++ inftrees.c */ 409428415Speter/* inftrees.c -- generate Huffman trees for efficient decoding 409534768Speter * Copyright (C) 1995-1996 Mark Adler 409628415Speter * For conditions of distribution and use, see copyright notice in zlib.h 409728415Speter */ 409828415Speter 409934768Speter/* #include "zutil.h" */ 410034768Speter/* #include "inftrees.h" */ 410134768Speter 410234768Speterchar inflate_copyright[] = " inflate 1.0.4 Copyright 1995-1996 Mark Adler "; 410334768Speter/* 410434768Speter If you use the zlib library in a product, an acknowledgment is welcome 410534768Speter in the documentation of your product. If for some reason you cannot 410634768Speter include such an acknowledgment, I would appreciate that you keep this 410734768Speter copyright string in the executable of your product. 410834768Speter */ 410934768Speter 411034768Speter#ifndef NO_DUMMY_DECL 411134768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 411234768Speter#endif 411334768Speter 411428415Speter/* simplify the use of the inflate_huft type with some defines */ 411528415Speter#define base more.Base 411628415Speter#define next more.Next 411728415Speter#define exop word.what.Exop 411828415Speter#define bits word.what.Bits 411928415Speter 412028415Speter 412128415Speterlocal int huft_build OF(( 412228415Speter uIntf *, /* code lengths in bits */ 412328415Speter uInt, /* number of codes */ 412428415Speter uInt, /* number of "simple" codes */ 412534768Speter const uIntf *, /* list of base values for non-simple codes */ 412634768Speter const uIntf *, /* list of extra bits for non-simple codes */ 412728415Speter inflate_huft * FAR*,/* result: starting table */ 412828415Speter uIntf *, /* maximum lookup bits (returns actual) */ 412934768Speter z_streamp )); /* for zalloc function */ 413028415Speter 413128415Speterlocal voidpf falloc OF(( 413228415Speter voidpf, /* opaque pointer (not used) */ 413328415Speter uInt, /* number of items */ 413428415Speter uInt)); /* size of item */ 413528415Speter 413628415Speter/* Tables for deflate from PKZIP's appnote.txt. */ 413734768Speterlocal const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */ 413828415Speter 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 413928415Speter 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 414034768Speter /* see note #13 above about 258 */ 414134768Speterlocal const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */ 414228415Speter 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 414334768Speter 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */ 414434768Speterlocal const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */ 414528415Speter 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 414628415Speter 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 414728415Speter 8193, 12289, 16385, 24577}; 414834768Speterlocal const uInt cpdext[30] = { /* Extra bits for distance codes */ 414928415Speter 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 415028415Speter 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 415128415Speter 12, 12, 13, 13}; 415228415Speter 415328415Speter/* 415428415Speter Huffman code decoding is performed using a multi-level table lookup. 415528415Speter The fastest way to decode is to simply build a lookup table whose 415628415Speter size is determined by the longest code. However, the time it takes 415728415Speter to build this table can also be a factor if the data being decoded 415828415Speter is not very long. The most common codes are necessarily the 415928415Speter shortest codes, so those codes dominate the decoding time, and hence 416028415Speter the speed. The idea is you can have a shorter table that decodes the 416128415Speter shorter, more probable codes, and then point to subsidiary tables for 416228415Speter the longer codes. The time it costs to decode the longer codes is 416328415Speter then traded against the time it takes to make longer tables. 416428415Speter 416528415Speter This results of this trade are in the variables lbits and dbits 416628415Speter below. lbits is the number of bits the first level table for literal/ 416728415Speter length codes can decode in one step, and dbits is the same thing for 416828415Speter the distance codes. Subsequent tables are also less than or equal to 416928415Speter those sizes. These values may be adjusted either when all of the 417028415Speter codes are shorter than that, in which case the longest code length in 417128415Speter bits is used, or when the shortest code is *longer* than the requested 417228415Speter table size, in which case the length of the shortest code in bits is 417328415Speter used. 417428415Speter 417528415Speter There are two different values for the two tables, since they code a 417628415Speter different number of possibilities each. The literal/length table 417728415Speter codes 286 possible values, or in a flat code, a little over eight 417828415Speter bits. The distance table codes 30 possible values, or a little less 417928415Speter than five bits, flat. The optimum values for speed end up being 418028415Speter about one bit more than those, so lbits is 8+1 and dbits is 5+1. 418128415Speter The optimum values may differ though from machine to machine, and 418228415Speter possibly even between compilers. Your mileage may vary. 418328415Speter */ 418428415Speter 418528415Speter 418628415Speter/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ 418728415Speter#define BMAX 15 /* maximum bit length of any code */ 418828415Speter#define N_MAX 288 /* maximum number of codes in any set */ 418928415Speter 419028415Speter#ifdef DEBUG_ZLIB 419128415Speter uInt inflate_hufts; 419228415Speter#endif 419328415Speter 419428415Speterlocal int huft_build(b, n, s, d, e, t, m, zs) 419528415SpeteruIntf *b; /* code lengths in bits (all assumed <= BMAX) */ 419628415SpeteruInt n; /* number of codes (assumed <= N_MAX) */ 419728415SpeteruInt s; /* number of simple-valued codes (0..s-1) */ 419834768Speterconst uIntf *d; /* list of base values for non-simple codes */ 419934768Speterconst uIntf *e; /* list of extra bits for non-simple codes */ 420028415Speterinflate_huft * FAR *t; /* result: starting table */ 420128415SpeteruIntf *m; /* maximum lookup bits, returns actual */ 420234768Speterz_streamp zs; /* for zalloc function */ 420328415Speter/* Given a list of code lengths and a maximum table size, make a set of 420428415Speter tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR 420528415Speter if the given code set is incomplete (the tables are still built in this 420634768Speter case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of 420734768Speter lengths), or Z_MEM_ERROR if not enough memory. */ 420828415Speter{ 420928415Speter 421028415Speter uInt a; /* counter for codes of length k */ 421128415Speter uInt c[BMAX+1]; /* bit length count table */ 421228415Speter uInt f; /* i repeats in table every f entries */ 421328415Speter int g; /* maximum code length */ 421428415Speter int h; /* table level */ 421528415Speter register uInt i; /* counter, current code */ 421628415Speter register uInt j; /* counter */ 421728415Speter register int k; /* number of bits in current code */ 421828415Speter int l; /* bits per table (returned in m) */ 421928415Speter register uIntf *p; /* pointer into c[], b[], or v[] */ 422028415Speter inflate_huft *q; /* points to current table */ 422128415Speter struct inflate_huft_s r; /* table entry for structure assignment */ 422228415Speter inflate_huft *u[BMAX]; /* table stack */ 422328415Speter uInt v[N_MAX]; /* values in order of bit length */ 422428415Speter register int w; /* bits before this table == (l * h) */ 422528415Speter uInt x[BMAX+1]; /* bit offsets, then code stack */ 422628415Speter uIntf *xp; /* pointer into x */ 422728415Speter int y; /* number of dummy codes added */ 422828415Speter uInt z; /* number of entries in current table */ 422928415Speter 423028415Speter 423128415Speter /* Generate counts for each bit length */ 423228415Speter p = c; 423328415Speter#define C0 *p++ = 0; 423428415Speter#define C2 C0 C0 C0 C0 423528415Speter#define C4 C2 C2 C2 C2 423628415Speter C4 /* clear c[]--assume BMAX+1 is 16 */ 423728415Speter p = b; i = n; 423828415Speter do { 423928415Speter c[*p++]++; /* assume all entries <= BMAX */ 424028415Speter } while (--i); 424128415Speter if (c[0] == n) /* null input--all zero length codes */ 424228415Speter { 424328415Speter *t = (inflate_huft *)Z_NULL; 424428415Speter *m = 0; 424528415Speter return Z_OK; 424628415Speter } 424728415Speter 424828415Speter 424928415Speter /* Find minimum and maximum length, bound *m by those */ 425028415Speter l = *m; 425128415Speter for (j = 1; j <= BMAX; j++) 425228415Speter if (c[j]) 425328415Speter break; 425428415Speter k = j; /* minimum code length */ 425528415Speter if ((uInt)l < j) 425628415Speter l = j; 425728415Speter for (i = BMAX; i; i--) 425828415Speter if (c[i]) 425928415Speter break; 426028415Speter g = i; /* maximum code length */ 426128415Speter if ((uInt)l > i) 426228415Speter l = i; 426328415Speter *m = l; 426428415Speter 426528415Speter 426628415Speter /* Adjust last length count to fill out codes, if needed */ 426728415Speter for (y = 1 << j; j < i; j++, y <<= 1) 426828415Speter if ((y -= c[j]) < 0) 426928415Speter return Z_DATA_ERROR; 427028415Speter if ((y -= c[i]) < 0) 427128415Speter return Z_DATA_ERROR; 427228415Speter c[i] += y; 427328415Speter 427428415Speter 427528415Speter /* Generate starting offsets into the value table for each length */ 427628415Speter x[1] = j = 0; 427728415Speter p = c + 1; xp = x + 2; 427828415Speter while (--i) { /* note that i == g from above */ 427928415Speter *xp++ = (j += *p++); 428028415Speter } 428128415Speter 428228415Speter 428328415Speter /* Make a table of values in order of bit lengths */ 428428415Speter p = b; i = 0; 428528415Speter do { 428628415Speter if ((j = *p++) != 0) 428728415Speter v[x[j]++] = i; 428828415Speter } while (++i < n); 428934768Speter n = x[g]; /* set n to length of v */ 429028415Speter 429128415Speter 429228415Speter /* Generate the Huffman codes and for each, make the table entries */ 429328415Speter x[0] = i = 0; /* first Huffman code is zero */ 429428415Speter p = v; /* grab values in bit order */ 429528415Speter h = -1; /* no tables yet--level -1 */ 429628415Speter w = -l; /* bits decoded == (l * h) */ 429728415Speter u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ 429828415Speter q = (inflate_huft *)Z_NULL; /* ditto */ 429928415Speter z = 0; /* ditto */ 430028415Speter 430128415Speter /* go through the bit lengths (k already is bits in shortest code) */ 430228415Speter for (; k <= g; k++) 430328415Speter { 430428415Speter a = c[k]; 430528415Speter while (a--) 430628415Speter { 430728415Speter /* here i is the Huffman code of length k bits for value *p */ 430828415Speter /* make tables up to required level */ 430928415Speter while (k > w + l) 431028415Speter { 431128415Speter h++; 431228415Speter w += l; /* previous table always l bits */ 431328415Speter 431428415Speter /* compute minimum size table less than or equal to l bits */ 431534768Speter z = g - w; 431634768Speter z = z > (uInt)l ? l : z; /* table size upper limit */ 431728415Speter if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 431828415Speter { /* too few codes for k-w bit table */ 431928415Speter f -= a + 1; /* deduct codes from patterns left */ 432028415Speter xp = c + k; 432128415Speter if (j < z) 432228415Speter while (++j < z) /* try smaller tables up to z bits */ 432328415Speter { 432428415Speter if ((f <<= 1) <= *++xp) 432528415Speter break; /* enough codes to use up j bits */ 432628415Speter f -= *xp; /* else deduct codes from patterns */ 432728415Speter } 432828415Speter } 432928415Speter z = 1 << j; /* table entries for j-bit table */ 433028415Speter 433128415Speter /* allocate and link in new table */ 433228415Speter if ((q = (inflate_huft *)ZALLOC 433328415Speter (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) 433428415Speter { 433528415Speter if (h) 433628415Speter inflate_trees_free(u[0], zs); 433728415Speter return Z_MEM_ERROR; /* not enough memory */ 433828415Speter } 433928415Speter#ifdef DEBUG_ZLIB 434028415Speter inflate_hufts += z + 1; 434128415Speter#endif 434228415Speter *t = q + 1; /* link to list for huft_free() */ 434328415Speter *(t = &(q->next)) = Z_NULL; 434428415Speter u[h] = ++q; /* table starts after link */ 434528415Speter 434628415Speter /* connect to last table, if there is one */ 434728415Speter if (h) 434828415Speter { 434928415Speter x[h] = i; /* save pattern for backing up */ 435028415Speter r.bits = (Byte)l; /* bits to dump before this table */ 435128415Speter r.exop = (Byte)j; /* bits in this table */ 435228415Speter r.next = q; /* pointer to this table */ 435328415Speter j = i >> (w - l); /* (get around Turbo C bug) */ 435428415Speter u[h-1][j] = r; /* connect to last table */ 435528415Speter } 435628415Speter } 435728415Speter 435828415Speter /* set up table entry in r */ 435928415Speter r.bits = (Byte)(k - w); 436028415Speter if (p >= v + n) 436128415Speter r.exop = 128 + 64; /* out of values--invalid code */ 436228415Speter else if (*p < s) 436328415Speter { 436428415Speter r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ 436528415Speter r.base = *p++; /* simple code is just the value */ 436628415Speter } 436728415Speter else 436828415Speter { 436934768Speter r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */ 437028415Speter r.base = d[*p++ - s]; 437128415Speter } 437228415Speter 437328415Speter /* fill code-like entries with r */ 437428415Speter f = 1 << (k - w); 437528415Speter for (j = i >> w; j < z; j += f) 437628415Speter q[j] = r; 437728415Speter 437828415Speter /* backwards increment the k-bit code i */ 437928415Speter for (j = 1 << (k - 1); i & j; j >>= 1) 438028415Speter i ^= j; 438128415Speter i ^= j; 438228415Speter 438328415Speter /* backup over finished tables */ 438428415Speter while ((i & ((1 << w) - 1)) != x[h]) 438528415Speter { 438628415Speter h--; /* don't need to update q */ 438728415Speter w -= l; 438828415Speter } 438928415Speter } 439028415Speter } 439128415Speter 439228415Speter 439328415Speter /* Return Z_BUF_ERROR if we were given an incomplete table */ 439428415Speter return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; 439528415Speter} 439628415Speter 439728415Speter 439834768Speterint inflate_trees_bits(c, bb, tb, z) 439928415SpeteruIntf *c; /* 19 code lengths */ 440028415SpeteruIntf *bb; /* bits tree desired/actual depth */ 440128415Speterinflate_huft * FAR *tb; /* bits tree result */ 440234768Speterz_streamp z; /* for zfree function */ 440328415Speter{ 440428415Speter int r; 440528415Speter 440628415Speter r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z); 440728415Speter if (r == Z_DATA_ERROR) 440834768Speter z->msg = (char*)"oversubscribed dynamic bit lengths tree"; 440934768Speter else if (r == Z_BUF_ERROR || *bb == 0) 441028415Speter { 441128415Speter inflate_trees_free(*tb, z); 441234768Speter z->msg = (char*)"incomplete dynamic bit lengths tree"; 441328415Speter r = Z_DATA_ERROR; 441428415Speter } 441528415Speter return r; 441628415Speter} 441728415Speter 441828415Speter 441934768Speterint inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z) 442028415SpeteruInt nl; /* number of literal/length codes */ 442128415SpeteruInt nd; /* number of distance codes */ 442228415SpeteruIntf *c; /* that many (total) code lengths */ 442328415SpeteruIntf *bl; /* literal desired/actual bit depth */ 442428415SpeteruIntf *bd; /* distance desired/actual bit depth */ 442528415Speterinflate_huft * FAR *tl; /* literal/length tree result */ 442628415Speterinflate_huft * FAR *td; /* distance tree result */ 442734768Speterz_streamp z; /* for zfree function */ 442828415Speter{ 442928415Speter int r; 443028415Speter 443128415Speter /* build literal/length tree */ 443234768Speter r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z); 443334768Speter if (r != Z_OK || *bl == 0) 443428415Speter { 443528415Speter if (r == Z_DATA_ERROR) 443634768Speter z->msg = (char*)"oversubscribed literal/length tree"; 443734768Speter else if (r != Z_MEM_ERROR) 443828415Speter { 443928415Speter inflate_trees_free(*tl, z); 444034768Speter z->msg = (char*)"incomplete literal/length tree"; 444128415Speter r = Z_DATA_ERROR; 444228415Speter } 444328415Speter return r; 444428415Speter } 444528415Speter 444628415Speter /* build distance tree */ 444734768Speter r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z); 444834768Speter if (r != Z_OK || (*bd == 0 && nl > 257)) 444928415Speter { 445028415Speter if (r == Z_DATA_ERROR) 445134768Speter z->msg = (char*)"oversubscribed distance tree"; 445228415Speter else if (r == Z_BUF_ERROR) { 445328415Speter#ifdef PKZIP_BUG_WORKAROUND 445428415Speter r = Z_OK; 445528415Speter } 445628415Speter#else 445728415Speter inflate_trees_free(*td, z); 445834768Speter z->msg = (char*)"incomplete distance tree"; 445928415Speter r = Z_DATA_ERROR; 446028415Speter } 446134768Speter else if (r != Z_MEM_ERROR) 446234768Speter { 446334768Speter z->msg = (char*)"empty distance tree with lengths"; 446434768Speter r = Z_DATA_ERROR; 446534768Speter } 446628415Speter inflate_trees_free(*tl, z); 446728415Speter return r; 446828415Speter#endif 446928415Speter } 447028415Speter 447128415Speter /* done */ 447228415Speter return Z_OK; 447328415Speter} 447428415Speter 447528415Speter 447628415Speter/* build fixed tables only once--keep them here */ 447728415Speterlocal int fixed_built = 0; 447828415Speter#define FIXEDH 530 /* number of hufts used by fixed tables */ 447928415Speterlocal inflate_huft fixed_mem[FIXEDH]; 448028415Speterlocal uInt fixed_bl; 448128415Speterlocal uInt fixed_bd; 448228415Speterlocal inflate_huft *fixed_tl; 448328415Speterlocal inflate_huft *fixed_td; 448428415Speter 448528415Speter 448628415Speterlocal voidpf falloc(q, n, s) 448734768Spetervoidpf q; /* opaque pointer */ 448828415SpeteruInt n; /* number of items */ 448928415SpeteruInt s; /* size of item */ 449028415Speter{ 449134768Speter Assert(s == sizeof(inflate_huft) && n <= *(intf *)q, 449228415Speter "inflate_trees falloc overflow"); 449334768Speter *(intf *)q -= n+s-s; /* s-s to avoid warning */ 449434768Speter return (voidpf)(fixed_mem + *(intf *)q); 449528415Speter} 449628415Speter 449728415Speter 449834768Speterint inflate_trees_fixed(bl, bd, tl, td) 449928415SpeteruIntf *bl; /* literal desired/actual bit depth */ 450028415SpeteruIntf *bd; /* distance desired/actual bit depth */ 450128415Speterinflate_huft * FAR *tl; /* literal/length tree result */ 450228415Speterinflate_huft * FAR *td; /* distance tree result */ 450328415Speter{ 450434768Speter /* build fixed tables if not already (multiple overlapped executions ok) */ 450528415Speter if (!fixed_built) 450628415Speter { 450728415Speter int k; /* temporary variable */ 450828415Speter unsigned c[288]; /* length list for huft_build */ 450928415Speter z_stream z; /* for falloc function */ 451034768Speter int f = FIXEDH; /* number of hufts left in fixed_mem */ 451128415Speter 451228415Speter /* set up fake z_stream for memory routines */ 451328415Speter z.zalloc = falloc; 451434768Speter z.zfree = Z_NULL; 451534768Speter z.opaque = (voidpf)&f; 451628415Speter 451728415Speter /* literal table */ 451828415Speter for (k = 0; k < 144; k++) 451928415Speter c[k] = 8; 452028415Speter for (; k < 256; k++) 452128415Speter c[k] = 9; 452228415Speter for (; k < 280; k++) 452328415Speter c[k] = 7; 452428415Speter for (; k < 288; k++) 452528415Speter c[k] = 8; 452628415Speter fixed_bl = 7; 452728415Speter huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z); 452828415Speter 452928415Speter /* distance table */ 453028415Speter for (k = 0; k < 30; k++) 453128415Speter c[k] = 5; 453228415Speter fixed_bd = 5; 453328415Speter huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z); 453428415Speter 453528415Speter /* done */ 453634768Speter Assert(f == 0, "invalid build of fixed tables"); 453728415Speter fixed_built = 1; 453828415Speter } 453928415Speter *bl = fixed_bl; 454028415Speter *bd = fixed_bd; 454128415Speter *tl = fixed_tl; 454228415Speter *td = fixed_td; 454328415Speter return Z_OK; 454428415Speter} 454528415Speter 454628415Speter 454734768Speterint inflate_trees_free(t, z) 454828415Speterinflate_huft *t; /* table to free */ 454934768Speterz_streamp z; /* for zfree function */ 455028415Speter/* Free the malloc'ed tables built by huft_build(), which makes a linked 455128415Speter list of the tables it made, with the links in a dummy first entry of 455228415Speter each table. */ 455328415Speter{ 455434768Speter register inflate_huft *p, *q, *r; 455528415Speter 455634768Speter /* Reverse linked list */ 455734768Speter p = Z_NULL; 455834768Speter q = t; 455934768Speter while (q != Z_NULL) 456034768Speter { 456134768Speter r = (q - 1)->next; 456234768Speter (q - 1)->next = p; 456334768Speter p = q; 456434768Speter q = r; 456534768Speter } 456628415Speter /* Go through linked list, freeing from the malloced (t[-1]) address. */ 456728415Speter while (p != Z_NULL) 456828415Speter { 456928415Speter q = (--p)->next; 457034768Speter ZFREE(z,p); 457128415Speter p = q; 457228415Speter } 457328415Speter return Z_OK; 457428415Speter} 457534768Speter/* --- inftrees.c */ 457628415Speter 457734768Speter/* +++ infcodes.c */ 457828415Speter/* infcodes.c -- process literals and length/distance pairs 457934768Speter * Copyright (C) 1995-1996 Mark Adler 458028415Speter * For conditions of distribution and use, see copyright notice in zlib.h 458128415Speter */ 458228415Speter 458334768Speter/* #include "zutil.h" */ 458434768Speter/* #include "inftrees.h" */ 458534768Speter/* #include "infblock.h" */ 458634768Speter/* #include "infcodes.h" */ 458734768Speter/* #include "infutil.h" */ 458834768Speter 458934768Speter/* +++ inffast.h */ 459034768Speter/* inffast.h -- header to use inffast.c 459134768Speter * Copyright (C) 1995-1996 Mark Adler 459234768Speter * For conditions of distribution and use, see copyright notice in zlib.h 459334768Speter */ 459434768Speter 459534768Speter/* WARNING: this file should *not* be used by applications. It is 459634768Speter part of the implementation of the compression library and is 459734768Speter subject to change. Applications should only use zlib.h. 459834768Speter */ 459934768Speter 460034768Speterextern int inflate_fast OF(( 460134768Speter uInt, 460234768Speter uInt, 460334768Speter inflate_huft *, 460434768Speter inflate_huft *, 460534768Speter inflate_blocks_statef *, 460634768Speter z_streamp )); 460734768Speter/* --- inffast.h */ 460834768Speter 460928415Speter/* simplify the use of the inflate_huft type with some defines */ 461028415Speter#define base more.Base 461128415Speter#define next more.Next 461228415Speter#define exop word.what.Exop 461328415Speter#define bits word.what.Bits 461428415Speter 461528415Speter/* inflate codes private state */ 461628415Speterstruct inflate_codes_state { 461728415Speter 461828415Speter /* mode */ 461928415Speter enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 462028415Speter START, /* x: set up for LEN */ 462128415Speter LEN, /* i: get length/literal/eob next */ 462228415Speter LENEXT, /* i: getting length extra (have base) */ 462328415Speter DIST, /* i: get distance next */ 462428415Speter DISTEXT, /* i: getting distance extra */ 462528415Speter COPY, /* o: copying bytes in window, waiting for space */ 462628415Speter LIT, /* o: got literal, waiting for output space */ 462728415Speter WASH, /* o: got eob, possibly still output waiting */ 462828415Speter END, /* x: got eob and all data flushed */ 462928415Speter BADCODE} /* x: got error */ 463028415Speter mode; /* current inflate_codes mode */ 463128415Speter 463228415Speter /* mode dependent information */ 463328415Speter uInt len; 463428415Speter union { 463528415Speter struct { 463628415Speter inflate_huft *tree; /* pointer into tree */ 463728415Speter uInt need; /* bits needed */ 463828415Speter } code; /* if LEN or DIST, where in tree */ 463928415Speter uInt lit; /* if LIT, literal */ 464028415Speter struct { 464128415Speter uInt get; /* bits to get for extra */ 464228415Speter uInt dist; /* distance back to copy from */ 464328415Speter } copy; /* if EXT or COPY, where and how much */ 464428415Speter } sub; /* submode */ 464528415Speter 464628415Speter /* mode independent information */ 464728415Speter Byte lbits; /* ltree bits decoded per branch */ 464828415Speter Byte dbits; /* dtree bits decoder per branch */ 464928415Speter inflate_huft *ltree; /* literal/length/eob tree */ 465028415Speter inflate_huft *dtree; /* distance tree */ 465128415Speter 465228415Speter}; 465328415Speter 465428415Speter 465534768Speterinflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z) 465628415SpeteruInt bl, bd; 465734768Speterinflate_huft *tl; 465834768Speterinflate_huft *td; /* need separate declaration for Borland C++ */ 465934768Speterz_streamp z; 466028415Speter{ 466128415Speter inflate_codes_statef *c; 466228415Speter 466328415Speter if ((c = (inflate_codes_statef *) 466428415Speter ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL) 466528415Speter { 466628415Speter c->mode = START; 466728415Speter c->lbits = (Byte)bl; 466828415Speter c->dbits = (Byte)bd; 466928415Speter c->ltree = tl; 467028415Speter c->dtree = td; 467128415Speter Tracev((stderr, "inflate: codes new\n")); 467228415Speter } 467328415Speter return c; 467428415Speter} 467528415Speter 467628415Speter 467734768Speterint inflate_codes(s, z, r) 467828415Speterinflate_blocks_statef *s; 467934768Speterz_streamp z; 468028415Speterint r; 468128415Speter{ 468228415Speter uInt j; /* temporary storage */ 468328415Speter inflate_huft *t; /* temporary pointer */ 468428415Speter uInt e; /* extra bits or operation */ 468528415Speter uLong b; /* bit buffer */ 468628415Speter uInt k; /* bits in bit buffer */ 468728415Speter Bytef *p; /* input data pointer */ 468828415Speter uInt n; /* bytes available there */ 468928415Speter Bytef *q; /* output window write pointer */ 469028415Speter uInt m; /* bytes to end of window or read pointer */ 469128415Speter Bytef *f; /* pointer to copy strings from */ 469228415Speter inflate_codes_statef *c = s->sub.decode.codes; /* codes state */ 469328415Speter 469428415Speter /* copy input/output information to locals (UPDATE macro restores) */ 469528415Speter LOAD 469628415Speter 469728415Speter /* process input and output based on current state */ 469828415Speter while (1) switch (c->mode) 469928415Speter { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 470028415Speter case START: /* x: set up for LEN */ 470128415Speter#ifndef SLOW 470228415Speter if (m >= 258 && n >= 10) 470328415Speter { 470428415Speter UPDATE 470528415Speter r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); 470628415Speter LOAD 470728415Speter if (r != Z_OK) 470828415Speter { 470928415Speter c->mode = r == Z_STREAM_END ? WASH : BADCODE; 471028415Speter break; 471128415Speter } 471228415Speter } 471328415Speter#endif /* !SLOW */ 471428415Speter c->sub.code.need = c->lbits; 471528415Speter c->sub.code.tree = c->ltree; 471628415Speter c->mode = LEN; 471728415Speter case LEN: /* i: get length/literal/eob next */ 471828415Speter j = c->sub.code.need; 471928415Speter NEEDBITS(j) 472028415Speter t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 472128415Speter DUMPBITS(t->bits) 472228415Speter e = (uInt)(t->exop); 472328415Speter if (e == 0) /* literal */ 472428415Speter { 472528415Speter c->sub.lit = t->base; 472628415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 472728415Speter "inflate: literal '%c'\n" : 472828415Speter "inflate: literal 0x%02x\n", t->base)); 472928415Speter c->mode = LIT; 473028415Speter break; 473128415Speter } 473228415Speter if (e & 16) /* length */ 473328415Speter { 473428415Speter c->sub.copy.get = e & 15; 473528415Speter c->len = t->base; 473628415Speter c->mode = LENEXT; 473728415Speter break; 473828415Speter } 473928415Speter if ((e & 64) == 0) /* next table */ 474028415Speter { 474128415Speter c->sub.code.need = e; 474228415Speter c->sub.code.tree = t->next; 474328415Speter break; 474428415Speter } 474528415Speter if (e & 32) /* end of block */ 474628415Speter { 474728415Speter Tracevv((stderr, "inflate: end of block\n")); 474828415Speter c->mode = WASH; 474928415Speter break; 475028415Speter } 475128415Speter c->mode = BADCODE; /* invalid code */ 475234768Speter z->msg = (char*)"invalid literal/length code"; 475328415Speter r = Z_DATA_ERROR; 475428415Speter LEAVE 475528415Speter case LENEXT: /* i: getting length extra (have base) */ 475628415Speter j = c->sub.copy.get; 475728415Speter NEEDBITS(j) 475828415Speter c->len += (uInt)b & inflate_mask[j]; 475928415Speter DUMPBITS(j) 476028415Speter c->sub.code.need = c->dbits; 476128415Speter c->sub.code.tree = c->dtree; 476228415Speter Tracevv((stderr, "inflate: length %u\n", c->len)); 476328415Speter c->mode = DIST; 476428415Speter case DIST: /* i: get distance next */ 476528415Speter j = c->sub.code.need; 476628415Speter NEEDBITS(j) 476728415Speter t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 476828415Speter DUMPBITS(t->bits) 476928415Speter e = (uInt)(t->exop); 477028415Speter if (e & 16) /* distance */ 477128415Speter { 477228415Speter c->sub.copy.get = e & 15; 477328415Speter c->sub.copy.dist = t->base; 477428415Speter c->mode = DISTEXT; 477528415Speter break; 477628415Speter } 477728415Speter if ((e & 64) == 0) /* next table */ 477828415Speter { 477928415Speter c->sub.code.need = e; 478028415Speter c->sub.code.tree = t->next; 478128415Speter break; 478228415Speter } 478328415Speter c->mode = BADCODE; /* invalid code */ 478434768Speter z->msg = (char*)"invalid distance code"; 478528415Speter r = Z_DATA_ERROR; 478628415Speter LEAVE 478728415Speter case DISTEXT: /* i: getting distance extra */ 478828415Speter j = c->sub.copy.get; 478928415Speter NEEDBITS(j) 479028415Speter c->sub.copy.dist += (uInt)b & inflate_mask[j]; 479128415Speter DUMPBITS(j) 479228415Speter Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist)); 479328415Speter c->mode = COPY; 479428415Speter case COPY: /* o: copying bytes in window, waiting for space */ 479528415Speter#ifndef __TURBOC__ /* Turbo C bug for following expression */ 479628415Speter f = (uInt)(q - s->window) < c->sub.copy.dist ? 479728415Speter s->end - (c->sub.copy.dist - (q - s->window)) : 479828415Speter q - c->sub.copy.dist; 479928415Speter#else 480028415Speter f = q - c->sub.copy.dist; 480128415Speter if ((uInt)(q - s->window) < c->sub.copy.dist) 480234768Speter f = s->end - (c->sub.copy.dist - (uInt)(q - s->window)); 480328415Speter#endif 480428415Speter while (c->len) 480528415Speter { 480628415Speter NEEDOUT 480728415Speter OUTBYTE(*f++) 480828415Speter if (f == s->end) 480928415Speter f = s->window; 481028415Speter c->len--; 481128415Speter } 481228415Speter c->mode = START; 481328415Speter break; 481428415Speter case LIT: /* o: got literal, waiting for output space */ 481528415Speter NEEDOUT 481628415Speter OUTBYTE(c->sub.lit) 481728415Speter c->mode = START; 481828415Speter break; 481928415Speter case WASH: /* o: got eob, possibly more output */ 482028415Speter FLUSH 482128415Speter if (s->read != s->write) 482228415Speter LEAVE 482328415Speter c->mode = END; 482428415Speter case END: 482528415Speter r = Z_STREAM_END; 482628415Speter LEAVE 482728415Speter case BADCODE: /* x: got error */ 482828415Speter r = Z_DATA_ERROR; 482928415Speter LEAVE 483028415Speter default: 483128415Speter r = Z_STREAM_ERROR; 483228415Speter LEAVE 483328415Speter } 483428415Speter} 483528415Speter 483628415Speter 483734768Spetervoid inflate_codes_free(c, z) 483828415Speterinflate_codes_statef *c; 483934768Speterz_streamp z; 484028415Speter{ 484134768Speter ZFREE(z, c); 484228415Speter Tracev((stderr, "inflate: codes free\n")); 484328415Speter} 484434768Speter/* --- infcodes.c */ 484528415Speter 484634768Speter/* +++ infutil.c */ 484728415Speter/* inflate_util.c -- data and routines common to blocks and codes 484834768Speter * Copyright (C) 1995-1996 Mark Adler 484928415Speter * For conditions of distribution and use, see copyright notice in zlib.h 485028415Speter */ 485128415Speter 485234768Speter/* #include "zutil.h" */ 485334768Speter/* #include "infblock.h" */ 485434768Speter/* #include "inftrees.h" */ 485534768Speter/* #include "infcodes.h" */ 485634768Speter/* #include "infutil.h" */ 485734768Speter 485834768Speter#ifndef NO_DUMMY_DECL 485934768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 486034768Speter#endif 486134768Speter 486234768Speter/* And'ing with mask[n] masks the lower n bits */ 486334768SpeteruInt inflate_mask[17] = { 486434768Speter 0x0000, 486534768Speter 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 486634768Speter 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 486734768Speter}; 486834768Speter 486934768Speter 487028415Speter/* copy as much as possible from the sliding window to the output area */ 487134768Speterint inflate_flush(s, z, r) 487228415Speterinflate_blocks_statef *s; 487334768Speterz_streamp z; 487428415Speterint r; 487528415Speter{ 487628415Speter uInt n; 487734768Speter Bytef *p; 487834768Speter Bytef *q; 487928415Speter 488028415Speter /* local copies of source and destination pointers */ 488128415Speter p = z->next_out; 488228415Speter q = s->read; 488328415Speter 488428415Speter /* compute number of bytes to copy as far as end of window */ 488528415Speter n = (uInt)((q <= s->write ? s->write : s->end) - q); 488628415Speter if (n > z->avail_out) n = z->avail_out; 488728415Speter if (n && r == Z_BUF_ERROR) r = Z_OK; 488828415Speter 488928415Speter /* update counters */ 489028415Speter z->avail_out -= n; 489128415Speter z->total_out += n; 489228415Speter 489328415Speter /* update check information */ 489428415Speter if (s->checkfn != Z_NULL) 489534768Speter z->adler = s->check = (*s->checkfn)(s->check, q, n); 489628415Speter 489728415Speter /* copy as far as end of window */ 489834768Speter if (p != Z_NULL) { 489928415Speter zmemcpy(p, q, n); 490028415Speter p += n; 490128415Speter } 490228415Speter q += n; 490328415Speter 490428415Speter /* see if more to copy at beginning of window */ 490528415Speter if (q == s->end) 490628415Speter { 490728415Speter /* wrap pointers */ 490828415Speter q = s->window; 490928415Speter if (s->write == s->end) 491028415Speter s->write = s->window; 491128415Speter 491228415Speter /* compute bytes to copy */ 491328415Speter n = (uInt)(s->write - q); 491428415Speter if (n > z->avail_out) n = z->avail_out; 491528415Speter if (n && r == Z_BUF_ERROR) r = Z_OK; 491628415Speter 491728415Speter /* update counters */ 491828415Speter z->avail_out -= n; 491928415Speter z->total_out += n; 492028415Speter 492128415Speter /* update check information */ 492228415Speter if (s->checkfn != Z_NULL) 492334768Speter z->adler = s->check = (*s->checkfn)(s->check, q, n); 492428415Speter 492528415Speter /* copy */ 492634768Speter if (p != Z_NULL) { 492728415Speter zmemcpy(p, q, n); 492828415Speter p += n; 492928415Speter } 493028415Speter q += n; 493128415Speter } 493228415Speter 493328415Speter /* update pointers */ 493428415Speter z->next_out = p; 493528415Speter s->read = q; 493628415Speter 493728415Speter /* done */ 493828415Speter return r; 493928415Speter} 494034768Speter/* --- infutil.c */ 494128415Speter 494234768Speter/* +++ inffast.c */ 494328415Speter/* inffast.c -- process literals and length/distance pairs fast 494434768Speter * Copyright (C) 1995-1996 Mark Adler 494528415Speter * For conditions of distribution and use, see copyright notice in zlib.h 494628415Speter */ 494728415Speter 494834768Speter/* #include "zutil.h" */ 494934768Speter/* #include "inftrees.h" */ 495034768Speter/* #include "infblock.h" */ 495134768Speter/* #include "infcodes.h" */ 495234768Speter/* #include "infutil.h" */ 495334768Speter/* #include "inffast.h" */ 495434768Speter 495534768Speter#ifndef NO_DUMMY_DECL 495634768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 495734768Speter#endif 495834768Speter 495928415Speter/* simplify the use of the inflate_huft type with some defines */ 496028415Speter#define base more.Base 496128415Speter#define next more.Next 496228415Speter#define exop word.what.Exop 496328415Speter#define bits word.what.Bits 496428415Speter 496528415Speter/* macros for bit input with no checking and for returning unused bytes */ 496628415Speter#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} 496728415Speter#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;} 496828415Speter 496928415Speter/* Called with number of bytes left to write in window at least 258 497028415Speter (the maximum string length) and number of input bytes available 497128415Speter at least ten. The ten bytes are six bytes for the longest length/ 497228415Speter distance pair plus four bytes for overloading the bit buffer. */ 497328415Speter 497434768Speterint inflate_fast(bl, bd, tl, td, s, z) 497528415SpeteruInt bl, bd; 497634768Speterinflate_huft *tl; 497734768Speterinflate_huft *td; /* need separate declaration for Borland C++ */ 497828415Speterinflate_blocks_statef *s; 497934768Speterz_streamp z; 498028415Speter{ 498128415Speter inflate_huft *t; /* temporary pointer */ 498228415Speter uInt e; /* extra bits or operation */ 498328415Speter uLong b; /* bit buffer */ 498428415Speter uInt k; /* bits in bit buffer */ 498528415Speter Bytef *p; /* input data pointer */ 498628415Speter uInt n; /* bytes available there */ 498728415Speter Bytef *q; /* output window write pointer */ 498828415Speter uInt m; /* bytes to end of window or read pointer */ 498928415Speter uInt ml; /* mask for literal/length tree */ 499028415Speter uInt md; /* mask for distance tree */ 499128415Speter uInt c; /* bytes to copy */ 499228415Speter uInt d; /* distance back to copy from */ 499328415Speter Bytef *r; /* copy source pointer */ 499428415Speter 499528415Speter /* load input, output, bit values */ 499628415Speter LOAD 499728415Speter 499828415Speter /* initialize masks */ 499928415Speter ml = inflate_mask[bl]; 500028415Speter md = inflate_mask[bd]; 500128415Speter 500228415Speter /* do until not enough input or output space for fast loop */ 500328415Speter do { /* assume called with m >= 258 && n >= 10 */ 500428415Speter /* get literal/length code */ 500528415Speter GRABBITS(20) /* max bits for literal/length code */ 500628415Speter if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) 500728415Speter { 500828415Speter DUMPBITS(t->bits) 500928415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 501028415Speter "inflate: * literal '%c'\n" : 501128415Speter "inflate: * literal 0x%02x\n", t->base)); 501228415Speter *q++ = (Byte)t->base; 501328415Speter m--; 501428415Speter continue; 501528415Speter } 501628415Speter do { 501728415Speter DUMPBITS(t->bits) 501828415Speter if (e & 16) 501928415Speter { 502028415Speter /* get extra bits for length */ 502128415Speter e &= 15; 502228415Speter c = t->base + ((uInt)b & inflate_mask[e]); 502328415Speter DUMPBITS(e) 502428415Speter Tracevv((stderr, "inflate: * length %u\n", c)); 502528415Speter 502628415Speter /* decode distance base of block to copy */ 502728415Speter GRABBITS(15); /* max bits for distance code */ 502828415Speter e = (t = td + ((uInt)b & md))->exop; 502928415Speter do { 503028415Speter DUMPBITS(t->bits) 503128415Speter if (e & 16) 503228415Speter { 503328415Speter /* get extra bits to add to distance base */ 503428415Speter e &= 15; 503528415Speter GRABBITS(e) /* get extra bits (up to 13) */ 503628415Speter d = t->base + ((uInt)b & inflate_mask[e]); 503728415Speter DUMPBITS(e) 503828415Speter Tracevv((stderr, "inflate: * distance %u\n", d)); 503928415Speter 504028415Speter /* do the copy */ 504128415Speter m -= c; 504228415Speter if ((uInt)(q - s->window) >= d) /* offset before dest */ 504328415Speter { /* just copy */ 504428415Speter r = q - d; 504528415Speter *q++ = *r++; c--; /* minimum count is three, */ 504628415Speter *q++ = *r++; c--; /* so unroll loop a little */ 504728415Speter } 504828415Speter else /* else offset after destination */ 504928415Speter { 505034768Speter e = d - (uInt)(q - s->window); /* bytes from offset to end */ 505128415Speter r = s->end - e; /* pointer to offset */ 505228415Speter if (c > e) /* if source crosses, */ 505328415Speter { 505428415Speter c -= e; /* copy to end of window */ 505528415Speter do { 505628415Speter *q++ = *r++; 505728415Speter } while (--e); 505828415Speter r = s->window; /* copy rest from start of window */ 505928415Speter } 506028415Speter } 506128415Speter do { /* copy all or what's left */ 506228415Speter *q++ = *r++; 506328415Speter } while (--c); 506428415Speter break; 506528415Speter } 506628415Speter else if ((e & 64) == 0) 506728415Speter e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop; 506828415Speter else 506928415Speter { 507034768Speter z->msg = (char*)"invalid distance code"; 507128415Speter UNGRAB 507228415Speter UPDATE 507328415Speter return Z_DATA_ERROR; 507428415Speter } 507528415Speter } while (1); 507628415Speter break; 507728415Speter } 507828415Speter if ((e & 64) == 0) 507928415Speter { 508028415Speter if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0) 508128415Speter { 508228415Speter DUMPBITS(t->bits) 508328415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 508428415Speter "inflate: * literal '%c'\n" : 508528415Speter "inflate: * literal 0x%02x\n", t->base)); 508628415Speter *q++ = (Byte)t->base; 508728415Speter m--; 508828415Speter break; 508928415Speter } 509028415Speter } 509128415Speter else if (e & 32) 509228415Speter { 509328415Speter Tracevv((stderr, "inflate: * end of block\n")); 509428415Speter UNGRAB 509528415Speter UPDATE 509628415Speter return Z_STREAM_END; 509728415Speter } 509828415Speter else 509928415Speter { 510034768Speter z->msg = (char*)"invalid literal/length code"; 510128415Speter UNGRAB 510228415Speter UPDATE 510328415Speter return Z_DATA_ERROR; 510428415Speter } 510528415Speter } while (1); 510628415Speter } while (m >= 258 && n >= 10); 510728415Speter 510828415Speter /* not enough input or output--restore pointers and return */ 510928415Speter UNGRAB 511028415Speter UPDATE 511128415Speter return Z_OK; 511228415Speter} 511334768Speter/* --- inffast.c */ 511428415Speter 511534768Speter/* +++ zutil.c */ 511628415Speter/* zutil.c -- target dependent utility functions for the compression library 511734768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 511828415Speter * For conditions of distribution and use, see copyright notice in zlib.h 511928415Speter */ 512028415Speter 512134768Speter/* From: zutil.c,v 1.17 1996/07/24 13:41:12 me Exp $ */ 512228415Speter 512334768Speter#ifdef DEBUG_ZLIB 512434768Speter#include <stdio.h> 512534768Speter#endif 512628415Speter 512734768Speter/* #include "zutil.h" */ 512834768Speter 512934768Speter#ifndef NO_DUMMY_DECL 513034768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 513134768Speter#endif 513234768Speter 513334768Speter#ifndef STDC 513434768Speterextern void exit OF((int)); 513534768Speter#endif 513634768Speter 513734768Speterstatic const char *z_errmsg[10] = { 513834768Speter"need dictionary", /* Z_NEED_DICT 2 */ 513934768Speter"stream end", /* Z_STREAM_END 1 */ 514034768Speter"", /* Z_OK 0 */ 514134768Speter"file error", /* Z_ERRNO (-1) */ 514234768Speter"stream error", /* Z_STREAM_ERROR (-2) */ 514334768Speter"data error", /* Z_DATA_ERROR (-3) */ 514434768Speter"insufficient memory", /* Z_MEM_ERROR (-4) */ 514534768Speter"buffer error", /* Z_BUF_ERROR (-5) */ 514634768Speter"incompatible version",/* Z_VERSION_ERROR (-6) */ 514728415Speter""}; 514828415Speter 514928415Speter 515034768Speterconst char *zlibVersion() 515134768Speter{ 515234768Speter return ZLIB_VERSION; 515334768Speter} 515434768Speter 515534768Speter#ifdef DEBUG_ZLIB 515634768Spetervoid z_error (m) 515734768Speter char *m; 515834768Speter{ 515934768Speter fprintf(stderr, "%s\n", m); 516034768Speter exit(1); 516134768Speter} 516234768Speter#endif 516334768Speter 516434768Speter#ifndef HAVE_MEMCPY 516534768Speter 516634768Spetervoid zmemcpy(dest, source, len) 516734768Speter Bytef* dest; 516834768Speter Bytef* source; 516934768Speter uInt len; 517034768Speter{ 517134768Speter if (len == 0) return; 517234768Speter do { 517334768Speter *dest++ = *source++; /* ??? to be unrolled */ 517434768Speter } while (--len != 0); 517534768Speter} 517634768Speter 517734768Speterint zmemcmp(s1, s2, len) 517834768Speter Bytef* s1; 517934768Speter Bytef* s2; 518034768Speter uInt len; 518134768Speter{ 518234768Speter uInt j; 518334768Speter 518434768Speter for (j = 0; j < len; j++) { 518534768Speter if (s1[j] != s2[j]) return 2*(s1[j] > s2[j])-1; 518634768Speter } 518734768Speter return 0; 518834768Speter} 518934768Speter 519034768Spetervoid zmemzero(dest, len) 519134768Speter Bytef* dest; 519234768Speter uInt len; 519334768Speter{ 519434768Speter if (len == 0) return; 519534768Speter do { 519634768Speter *dest++ = 0; /* ??? to be unrolled */ 519734768Speter } while (--len != 0); 519834768Speter} 519934768Speter#endif 520034768Speter 520134768Speter#ifdef __TURBOC__ 520234768Speter#if (defined( __BORLANDC__) || !defined(SMALL_MEDIUM)) && !defined(__32BIT__) 520334768Speter/* Small and medium model in Turbo C are for now limited to near allocation 520434768Speter * with reduced MAX_WBITS and MAX_MEM_LEVEL 520534768Speter */ 520634768Speter# define MY_ZCALLOC 520734768Speter 520834768Speter/* Turbo C malloc() does not allow dynamic allocation of 64K bytes 520934768Speter * and farmalloc(64K) returns a pointer with an offset of 8, so we 521034768Speter * must fix the pointer. Warning: the pointer must be put back to its 521134768Speter * original form in order to free it, use zcfree(). 521234768Speter */ 521334768Speter 521434768Speter#define MAX_PTR 10 521534768Speter/* 10*64K = 640K */ 521634768Speter 521734768Speterlocal int next_ptr = 0; 521834768Speter 521934768Spetertypedef struct ptr_table_s { 522034768Speter voidpf org_ptr; 522134768Speter voidpf new_ptr; 522234768Speter} ptr_table; 522334768Speter 522434768Speterlocal ptr_table table[MAX_PTR]; 522534768Speter/* This table is used to remember the original form of pointers 522634768Speter * to large buffers (64K). Such pointers are normalized with a zero offset. 522734768Speter * Since MSDOS is not a preemptive multitasking OS, this table is not 522834768Speter * protected from concurrent access. This hack doesn't work anyway on 522934768Speter * a protected system like OS/2. Use Microsoft C instead. 523034768Speter */ 523134768Speter 523234768Spetervoidpf zcalloc (voidpf opaque, unsigned items, unsigned size) 523334768Speter{ 523434768Speter voidpf buf = opaque; /* just to make some compilers happy */ 523534768Speter ulg bsize = (ulg)items*size; 523634768Speter 523734768Speter /* If we allocate less than 65520 bytes, we assume that farmalloc 523834768Speter * will return a usable pointer which doesn't have to be normalized. 523934768Speter */ 524034768Speter if (bsize < 65520L) { 524134768Speter buf = farmalloc(bsize); 524234768Speter if (*(ush*)&buf != 0) return buf; 524334768Speter } else { 524434768Speter buf = farmalloc(bsize + 16L); 524534768Speter } 524634768Speter if (buf == NULL || next_ptr >= MAX_PTR) return NULL; 524734768Speter table[next_ptr].org_ptr = buf; 524834768Speter 524934768Speter /* Normalize the pointer to seg:0 */ 525034768Speter *((ush*)&buf+1) += ((ush)((uch*)buf-0) + 15) >> 4; 525134768Speter *(ush*)&buf = 0; 525234768Speter table[next_ptr++].new_ptr = buf; 525334768Speter return buf; 525434768Speter} 525534768Speter 525634768Spetervoid zcfree (voidpf opaque, voidpf ptr) 525734768Speter{ 525834768Speter int n; 525934768Speter if (*(ush*)&ptr != 0) { /* object < 64K */ 526034768Speter farfree(ptr); 526134768Speter return; 526234768Speter } 526334768Speter /* Find the original pointer */ 526434768Speter for (n = 0; n < next_ptr; n++) { 526534768Speter if (ptr != table[n].new_ptr) continue; 526634768Speter 526734768Speter farfree(table[n].org_ptr); 526834768Speter while (++n < next_ptr) { 526934768Speter table[n-1] = table[n]; 527034768Speter } 527134768Speter next_ptr--; 527234768Speter return; 527334768Speter } 527434768Speter ptr = opaque; /* just to make some compilers happy */ 527534768Speter Assert(0, "zcfree: ptr not found"); 527634768Speter} 527734768Speter#endif 527834768Speter#endif /* __TURBOC__ */ 527934768Speter 528034768Speter 528134768Speter#if defined(M_I86) && !defined(__32BIT__) 528234768Speter/* Microsoft C in 16-bit mode */ 528334768Speter 528434768Speter# define MY_ZCALLOC 528534768Speter 528634768Speter#if (!defined(_MSC_VER) || (_MSC_VER < 600)) 528734768Speter# define _halloc halloc 528834768Speter# define _hfree hfree 528934768Speter#endif 529034768Speter 529134768Spetervoidpf zcalloc (voidpf opaque, unsigned items, unsigned size) 529234768Speter{ 529334768Speter if (opaque) opaque = 0; /* to make compiler happy */ 529434768Speter return _halloc((long)items, size); 529534768Speter} 529634768Speter 529734768Spetervoid zcfree (voidpf opaque, voidpf ptr) 529834768Speter{ 529934768Speter if (opaque) opaque = 0; /* to make compiler happy */ 530034768Speter _hfree(ptr); 530134768Speter} 530234768Speter 530334768Speter#endif /* MSC */ 530434768Speter 530534768Speter 530634768Speter#ifndef MY_ZCALLOC /* Any system without a special alloc function */ 530734768Speter 530834768Speter#ifndef STDC 530934768Speterextern voidp calloc OF((uInt items, uInt size)); 531034768Speterextern void free OF((voidpf ptr)); 531134768Speter#endif 531234768Speter 531334768Spetervoidpf zcalloc (opaque, items, size) 531434768Speter voidpf opaque; 531534768Speter unsigned items; 531634768Speter unsigned size; 531734768Speter{ 531834768Speter if (opaque) items += size - size; /* make compiler happy */ 531934768Speter return (voidpf)calloc(items, size); 532034768Speter} 532134768Speter 532234768Spetervoid zcfree (opaque, ptr) 532334768Speter voidpf opaque; 532434768Speter voidpf ptr; 532534768Speter{ 532634768Speter free(ptr); 532734768Speter if (opaque) return; /* make compiler happy */ 532834768Speter} 532934768Speter 533034768Speter#endif /* MY_ZCALLOC */ 533134768Speter/* --- zutil.c */ 533234768Speter 533334768Speter/* +++ adler32.c */ 533428415Speter/* adler32.c -- compute the Adler-32 checksum of a data stream 533534768Speter * Copyright (C) 1995-1996 Mark Adler 533628415Speter * For conditions of distribution and use, see copyright notice in zlib.h 533728415Speter */ 533828415Speter 533934768Speter/* From: adler32.c,v 1.10 1996/05/22 11:52:18 me Exp $ */ 534028415Speter 534134768Speter/* #include "zlib.h" */ 534234768Speter 534328415Speter#define BASE 65521L /* largest prime smaller than 65536 */ 534428415Speter#define NMAX 5552 534528415Speter/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 534628415Speter 534734768Speter#define DO1(buf,i) {s1 += buf[i]; s2 += s1;} 534834768Speter#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1); 534934768Speter#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2); 535034768Speter#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4); 535134768Speter#define DO16(buf) DO8(buf,0); DO8(buf,8); 535228415Speter 535328415Speter/* ========================================================================= */ 535428415SpeteruLong adler32(adler, buf, len) 535528415Speter uLong adler; 535634768Speter const Bytef *buf; 535728415Speter uInt len; 535828415Speter{ 535928415Speter unsigned long s1 = adler & 0xffff; 536028415Speter unsigned long s2 = (adler >> 16) & 0xffff; 536128415Speter int k; 536228415Speter 536328415Speter if (buf == Z_NULL) return 1L; 536428415Speter 536528415Speter while (len > 0) { 536628415Speter k = len < NMAX ? len : NMAX; 536728415Speter len -= k; 536828415Speter while (k >= 16) { 536928415Speter DO16(buf); 537034768Speter buf += 16; 537128415Speter k -= 16; 537228415Speter } 537328415Speter if (k != 0) do { 537434768Speter s1 += *buf++; 537534768Speter s2 += s1; 537628415Speter } while (--k); 537728415Speter s1 %= BASE; 537828415Speter s2 %= BASE; 537928415Speter } 538028415Speter return (s2 << 16) | s1; 538128415Speter} 538234768Speter/* --- adler32.c */ 5383