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$ 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 */ 33139823Simp/*- 34139823Simp * zutil.h -- internal interface and configuration of the compression library 3534768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 3628415Speter * For conditions of distribution and use, see copyright notice in zlib.h 3728415Speter */ 3828415Speter 3928415Speter/* WARNING: this file should *not* be used by applications. It is 4028415Speter part of the implementation of the compression library and is 4128415Speter subject to change. Applications should only use zlib.h. 4228415Speter */ 4328415Speter 4434768Speter/* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */ 4528415Speter 4634768Speter#ifndef _Z_UTIL_H 4728415Speter#define _Z_UTIL_H 4828415Speter 4955205Speter#ifdef _KERNEL 5028415Speter#include <net/zlib.h> 5128415Speter#else 5228415Speter#include "zlib.h" 5328415Speter#endif 5428415Speter 5555205Speter#ifdef _KERNEL 5634768Speter/* Assume this is a *BSD or SVR4 kernel */ 5734768Speter#include <sys/types.h> 5834768Speter#include <sys/time.h> 5934768Speter#include <sys/systm.h> 60110235Salfred#include <sys/param.h> 61130799Smarkm#include <sys/kernel.h> 62130799Smarkm#include <sys/module.h> 6334768Speter# define HAVE_MEMCPY 6434768Speter 6534768Speter#else 6634768Speter#if defined(__KERNEL__) 6734768Speter/* Assume this is a Linux kernel */ 6834768Speter#include <linux/string.h> 6934768Speter#define HAVE_MEMCPY 7034768Speter 7134768Speter#else /* not kernel */ 7234768Speter 7334768Speter#if defined(MSDOS)||defined(VMS)||defined(CRAY)||defined(WIN32)||defined(RISCOS) 7434768Speter# include <stddef.h> 7534768Speter# include <errno.h> 7634768Speter#else 7734768Speter extern int errno; 7834768Speter#endif 7934768Speter#ifdef STDC 8034768Speter# include <string.h> 8134768Speter# include <stdlib.h> 8234768Speter#endif 8334768Speter#endif /* __KERNEL__ */ 8455205Speter#endif /* _KERNEL */ 8534768Speter 8628415Speter#ifndef local 8728415Speter# define local static 8828415Speter#endif 8928415Speter/* compile with -Dlocal if your debugger can't find static symbols */ 9028415Speter 9128415Spetertypedef unsigned char uch; 9228415Spetertypedef uch FAR uchf; 9328415Spetertypedef unsigned short ush; 9428415Spetertypedef ush FAR ushf; 9528415Spetertypedef unsigned long ulg; 9628415Speter 97149993Srodrigcstatic const char *z_errmsg[10]; /* indexed by 2-zlib_error */ 9834768Speter/* (size given to avoid silly warnings with Visual C++) */ 9928415Speter 10034768Speter#define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)] 10134768Speter 10234768Speter#define ERR_RETURN(strm,err) \ 10343305Sdillon return (strm->msg = (const char*)ERR_MSG(err), (err)) 10428415Speter/* To be used only when the state is known to be valid */ 10528415Speter 10628415Speter /* common constants */ 10728415Speter 10828415Speter#ifndef DEF_WBITS 10928415Speter# define DEF_WBITS MAX_WBITS 11028415Speter#endif 11128415Speter/* default windowBits for decompression. MAX_WBITS is for compression only */ 11228415Speter 11328415Speter#if MAX_MEM_LEVEL >= 8 11428415Speter# define DEF_MEM_LEVEL 8 11528415Speter#else 11628415Speter# define DEF_MEM_LEVEL MAX_MEM_LEVEL 11728415Speter#endif 11828415Speter/* default memLevel */ 11928415Speter 12028415Speter#define STORED_BLOCK 0 12128415Speter#define STATIC_TREES 1 12228415Speter#define DYN_TREES 2 12328415Speter/* The three kinds of block type */ 12428415Speter 12528415Speter#define MIN_MATCH 3 12628415Speter#define MAX_MATCH 258 12728415Speter/* The minimum and maximum match lengths */ 12828415Speter 12934768Speter#define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */ 13034768Speter 13134768Speter /* target dependencies */ 13234768Speter 13334768Speter#ifdef MSDOS 13434768Speter# define OS_CODE 0x00 13534768Speter# ifdef __TURBOC__ 13634768Speter# include <alloc.h> 13734768Speter# else /* MSC or DJGPP */ 13834768Speter# include <malloc.h> 13934768Speter# endif 14034768Speter#endif 14134768Speter 14234768Speter#ifdef OS2 14334768Speter# define OS_CODE 0x06 14434768Speter#endif 14534768Speter 14634768Speter#ifdef WIN32 /* Window 95 & Windows NT */ 14734768Speter# define OS_CODE 0x0b 14834768Speter#endif 14934768Speter 15034768Speter#if defined(VAXC) || defined(VMS) 15134768Speter# define OS_CODE 0x02 15234768Speter# define FOPEN(name, mode) \ 15334768Speter fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512") 15434768Speter#endif 15534768Speter 15634768Speter#ifdef AMIGA 15734768Speter# define OS_CODE 0x01 15834768Speter#endif 15934768Speter 16034768Speter#if defined(ATARI) || defined(atarist) 16134768Speter# define OS_CODE 0x05 16234768Speter#endif 16334768Speter 16434768Speter#ifdef MACOS 16534768Speter# define OS_CODE 0x07 16634768Speter#endif 16734768Speter 16834768Speter#ifdef __50SERIES /* Prime/PRIMOS */ 16934768Speter# define OS_CODE 0x0F 17034768Speter#endif 17134768Speter 17234768Speter#ifdef TOPS20 17334768Speter# define OS_CODE 0x0a 17434768Speter#endif 17534768Speter 17634768Speter#if defined(_BEOS_) || defined(RISCOS) 17734768Speter# define fdopen(fd,mode) NULL /* No fdopen() */ 17834768Speter#endif 17934768Speter 18034768Speter /* Common defaults */ 18134768Speter 18234768Speter#ifndef OS_CODE 18334768Speter# define OS_CODE 0x03 /* assume Unix */ 18434768Speter#endif 18534768Speter 18634768Speter#ifndef FOPEN 18734768Speter# define FOPEN(name, mode) fopen((name), (mode)) 18834768Speter#endif 18934768Speter 19028415Speter /* functions */ 19128415Speter 19234768Speter#ifdef HAVE_STRERROR 19334768Speter extern char *strerror OF((int)); 19434768Speter# define zstrerror(errnum) strerror(errnum) 19528415Speter#else 19634768Speter# define zstrerror(errnum) "" 19734768Speter#endif 19828415Speter 19934768Speter#if defined(pyr) 20034768Speter# define NO_MEMCPY 20134768Speter#endif 20234768Speter#if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER) 20334768Speter /* Use our own functions for small and medium model with MSC <= 5.0. 20434768Speter * You may have to use the same strategy for Borland C (untested). 20534768Speter */ 20634768Speter# define NO_MEMCPY 20734768Speter#endif 20828415Speter#if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY) 20928415Speter# define HAVE_MEMCPY 21028415Speter#endif 21128415Speter#ifdef HAVE_MEMCPY 21234768Speter# ifdef SMALL_MEDIUM /* MSDOS small or medium model */ 21334768Speter# define zmemcpy _fmemcpy 21434768Speter# define zmemcmp _fmemcmp 21534768Speter# define zmemzero(dest, len) _fmemset(dest, 0, len) 21634768Speter# else 21728415Speter# define zmemcpy memcpy 21834768Speter# define zmemcmp memcmp 21928415Speter# define zmemzero(dest, len) memset(dest, 0, len) 22034768Speter# endif 22128415Speter#else 22228415Speter extern void zmemcpy OF((Bytef* dest, Bytef* source, uInt len)); 22334768Speter extern int zmemcmp OF((Bytef* s1, Bytef* s2, uInt len)); 22428415Speter extern void zmemzero OF((Bytef* dest, uInt len)); 22528415Speter#endif 22628415Speter 22728415Speter/* Diagnostic functions */ 22828415Speter#ifdef DEBUG_ZLIB 22928415Speter# include <stdio.h> 23028415Speter# ifndef verbose 23128415Speter# define verbose 0 23228415Speter# endif 23334768Speter extern void z_error OF((char *m)); 23428415Speter# define Assert(cond,msg) {if(!(cond)) z_error(msg);} 23528415Speter# define Trace(x) fprintf x 23628415Speter# define Tracev(x) {if (verbose) fprintf x ;} 23728415Speter# define Tracevv(x) {if (verbose>1) fprintf x ;} 23828415Speter# define Tracec(c,x) {if (verbose && (c)) fprintf x ;} 23928415Speter# define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;} 24028415Speter#else 24128415Speter# define Assert(cond,msg) 24228415Speter# define Trace(x) 24328415Speter# define Tracev(x) 24428415Speter# define Tracevv(x) 24528415Speter# define Tracec(c,x) 24628415Speter# define Tracecv(c,x) 24728415Speter#endif 24828415Speter 24928415Speter 25034768Spetertypedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len)); 25128415Speter 25234768Spetervoidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); 25334768Spetervoid zcfree OF((voidpf opaque, voidpf ptr)); 25428415Speter 25528415Speter#define ZALLOC(strm, items, size) \ 25628415Speter (*((strm)->zalloc))((strm)->opaque, (items), (size)) 25734768Speter#define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr)) 25834768Speter#define TRY_FREE(s, p) {if (p) ZFREE(s, p);} 25928415Speter 26034768Speter#endif /* _Z_UTIL_H */ 26134768Speter/* --- zutil.h */ 26234768Speter 26334768Speter/* +++ deflate.h */ 26428415Speter/* deflate.h -- internal compression state 26534768Speter * Copyright (C) 1995-1996 Jean-loup Gailly 26628415Speter * For conditions of distribution and use, see copyright notice in zlib.h 26728415Speter */ 26828415Speter 26928415Speter/* WARNING: this file should *not* be used by applications. It is 27028415Speter part of the implementation of the compression library and is 27128415Speter subject to change. Applications should only use zlib.h. 27228415Speter */ 27328415Speter 27434768Speter/* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */ 27528415Speter 27634768Speter#ifndef _DEFLATE_H 27734768Speter#define _DEFLATE_H 27828415Speter 27934768Speter/* #include "zutil.h" */ 28034768Speter 28128415Speter/* =========================================================================== 28228415Speter * Internal compression state. 28328415Speter */ 28428415Speter 28528415Speter#define LENGTH_CODES 29 28628415Speter/* number of length codes, not counting the special END_BLOCK code */ 28728415Speter 28828415Speter#define LITERALS 256 28928415Speter/* number of literal bytes 0..255 */ 29028415Speter 29128415Speter#define L_CODES (LITERALS+1+LENGTH_CODES) 29228415Speter/* number of Literal or Length codes, including the END_BLOCK code */ 29328415Speter 29428415Speter#define D_CODES 30 29528415Speter/* number of distance codes */ 29628415Speter 29728415Speter#define BL_CODES 19 29828415Speter/* number of codes used to transfer the bit lengths */ 29928415Speter 30028415Speter#define HEAP_SIZE (2*L_CODES+1) 30128415Speter/* maximum heap size */ 30228415Speter 30328415Speter#define MAX_BITS 15 30428415Speter/* All codes must not exceed MAX_BITS bits */ 30528415Speter 30628415Speter#define INIT_STATE 42 30728415Speter#define BUSY_STATE 113 30828415Speter#define FINISH_STATE 666 30928415Speter/* Stream status */ 31028415Speter 31128415Speter 31228415Speter/* Data structure describing a single value and its code string. */ 31328415Spetertypedef struct ct_data_s { 31428415Speter union { 31528415Speter ush freq; /* frequency count */ 31628415Speter ush code; /* bit string */ 31728415Speter } fc; 31828415Speter union { 31928415Speter ush dad; /* father node in Huffman tree */ 32028415Speter ush len; /* length of bit string */ 32128415Speter } dl; 32228415Speter} FAR ct_data; 32328415Speter 32428415Speter#define Freq fc.freq 32528415Speter#define Code fc.code 32628415Speter#define Dad dl.dad 32728415Speter#define Len dl.len 32828415Speter 32928415Spetertypedef struct static_tree_desc_s static_tree_desc; 33028415Speter 33128415Spetertypedef struct tree_desc_s { 33228415Speter ct_data *dyn_tree; /* the dynamic tree */ 33328415Speter int max_code; /* largest code with non zero frequency */ 33428415Speter static_tree_desc *stat_desc; /* the corresponding static tree */ 33528415Speter} FAR tree_desc; 33628415Speter 33728415Spetertypedef ush Pos; 33828415Spetertypedef Pos FAR Posf; 33928415Spetertypedef unsigned IPos; 34028415Speter 34128415Speter/* A Pos is an index in the character window. We use short instead of int to 34228415Speter * save space in the various tables. IPos is used only for parameter passing. 34328415Speter */ 34428415Speter 34528415Spetertypedef struct deflate_state { 34634768Speter z_streamp strm; /* pointer back to this zlib stream */ 34728415Speter int status; /* as the name implies */ 34828415Speter Bytef *pending_buf; /* output still pending */ 34934768Speter ulg pending_buf_size; /* size of pending_buf */ 35028415Speter Bytef *pending_out; /* next pending byte to output to the stream */ 35128415Speter int pending; /* nb of bytes in the pending buffer */ 35228415Speter int noheader; /* suppress zlib header and adler32 */ 35334768Speter Byte data_type; /* UNKNOWN, BINARY or ASCII */ 35428415Speter Byte method; /* STORED (for zip only) or DEFLATED */ 35534768Speter int last_flush; /* value of flush param for previous deflate call */ 35628415Speter 35728415Speter /* used by deflate.c: */ 35828415Speter 35928415Speter uInt w_size; /* LZ77 window size (32K by default) */ 36028415Speter uInt w_bits; /* log2(w_size) (8..16) */ 36128415Speter uInt w_mask; /* w_size - 1 */ 36228415Speter 36328415Speter Bytef *window; 36428415Speter /* Sliding window. Input bytes are read into the second half of the window, 36528415Speter * and move to the first half later to keep a dictionary of at least wSize 36628415Speter * bytes. With this organization, matches are limited to a distance of 36728415Speter * wSize-MAX_MATCH bytes, but this ensures that IO is always 36828415Speter * performed with a length multiple of the block size. Also, it limits 36928415Speter * the window size to 64K, which is quite useful on MSDOS. 37028415Speter * To do: use the user input buffer as sliding window. 37128415Speter */ 37228415Speter 37328415Speter ulg window_size; 37428415Speter /* Actual size of window: 2*wSize, except when the user input buffer 37528415Speter * is directly used as sliding window. 37628415Speter */ 37728415Speter 37828415Speter Posf *prev; 37928415Speter /* Link to older string with same hash index. To limit the size of this 38028415Speter * array to 64K, this link is maintained only for the last 32K strings. 38128415Speter * An index in this array is thus a window index modulo 32K. 38228415Speter */ 38328415Speter 38428415Speter Posf *head; /* Heads of the hash chains or NIL. */ 38528415Speter 38628415Speter uInt ins_h; /* hash index of string to be inserted */ 38728415Speter uInt hash_size; /* number of elements in hash table */ 38828415Speter uInt hash_bits; /* log2(hash_size) */ 38928415Speter uInt hash_mask; /* hash_size-1 */ 39028415Speter 39128415Speter uInt hash_shift; 39228415Speter /* Number of bits by which ins_h must be shifted at each input 39328415Speter * step. It must be such that after MIN_MATCH steps, the oldest 39428415Speter * byte no longer takes part in the hash key, that is: 39528415Speter * hash_shift * MIN_MATCH >= hash_bits 39628415Speter */ 39728415Speter 39828415Speter long block_start; 39928415Speter /* Window position at the beginning of the current output block. Gets 40028415Speter * negative when the window is moved backwards. 40128415Speter */ 40228415Speter 40328415Speter uInt match_length; /* length of best match */ 40428415Speter IPos prev_match; /* previous match */ 40528415Speter int match_available; /* set if previous match exists */ 40628415Speter uInt strstart; /* start of string to insert */ 40728415Speter uInt match_start; /* start of matching string */ 40828415Speter uInt lookahead; /* number of valid bytes ahead in window */ 40928415Speter 41028415Speter uInt prev_length; 41128415Speter /* Length of the best match at previous step. Matches not greater than this 41228415Speter * are discarded. This is used in the lazy match evaluation. 41328415Speter */ 41428415Speter 41528415Speter uInt max_chain_length; 41628415Speter /* To speed up deflation, hash chains are never searched beyond this 41728415Speter * length. A higher limit improves compression ratio but degrades the 41828415Speter * speed. 41928415Speter */ 42028415Speter 42128415Speter uInt max_lazy_match; 42228415Speter /* Attempt to find a better match only when the current match is strictly 42328415Speter * smaller than this value. This mechanism is used only for compression 42428415Speter * levels >= 4. 42528415Speter */ 42628415Speter# define max_insert_length max_lazy_match 42728415Speter /* Insert new strings in the hash table only if the match length is not 42828415Speter * greater than this length. This saves time but degrades compression. 42928415Speter * max_insert_length is used only for compression levels <= 3. 43028415Speter */ 43128415Speter 43228415Speter int level; /* compression level (1..9) */ 43328415Speter int strategy; /* favor or force Huffman coding*/ 43428415Speter 43528415Speter uInt good_match; 43628415Speter /* Use a faster search when the previous match is longer than this */ 43728415Speter 43834768Speter int nice_match; /* Stop searching when current match exceeds this */ 43928415Speter 44028415Speter /* used by trees.c: */ 44128415Speter /* Didn't use ct_data typedef below to supress compiler warning */ 44228415Speter struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 44328415Speter struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ 44428415Speter struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */ 44528415Speter 44628415Speter struct tree_desc_s l_desc; /* desc. for literal tree */ 44728415Speter struct tree_desc_s d_desc; /* desc. for distance tree */ 44828415Speter struct tree_desc_s bl_desc; /* desc. for bit length tree */ 44928415Speter 45028415Speter ush bl_count[MAX_BITS+1]; 45128415Speter /* number of codes at each bit length for an optimal tree */ 45228415Speter 45328415Speter int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 45428415Speter int heap_len; /* number of elements in the heap */ 45528415Speter int heap_max; /* element of largest frequency */ 45628415Speter /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 45728415Speter * The same heap array is used to build all trees. 45828415Speter */ 45928415Speter 46028415Speter uch depth[2*L_CODES+1]; 46128415Speter /* Depth of each subtree used as tie breaker for trees of equal frequency 46228415Speter */ 46328415Speter 46428415Speter uchf *l_buf; /* buffer for literals or lengths */ 46528415Speter 46628415Speter uInt lit_bufsize; 46728415Speter /* Size of match buffer for literals/lengths. There are 4 reasons for 46828415Speter * limiting lit_bufsize to 64K: 46928415Speter * - frequencies can be kept in 16 bit counters 47028415Speter * - if compression is not successful for the first block, all input 47128415Speter * data is still in the window so we can still emit a stored block even 47228415Speter * when input comes from standard input. (This can also be done for 47328415Speter * all blocks if lit_bufsize is not greater than 32K.) 47428415Speter * - if compression is not successful for a file smaller than 64K, we can 47528415Speter * even emit a stored file instead of a stored block (saving 5 bytes). 47628415Speter * This is applicable only for zip (not gzip or zlib). 47728415Speter * - creating new Huffman trees less frequently may not provide fast 47828415Speter * adaptation to changes in the input data statistics. (Take for 47928415Speter * example a binary file with poorly compressible code followed by 48028415Speter * a highly compressible string table.) Smaller buffer sizes give 48128415Speter * fast adaptation but have of course the overhead of transmitting 48228415Speter * trees more frequently. 48328415Speter * - I can't count above 4 48428415Speter */ 48528415Speter 48628415Speter uInt last_lit; /* running index in l_buf */ 48728415Speter 48828415Speter ushf *d_buf; 48928415Speter /* Buffer for distances. To simplify the code, d_buf and l_buf have 49028415Speter * the same number of elements. To use different lengths, an extra flag 49128415Speter * array would be necessary. 49228415Speter */ 49328415Speter 49428415Speter ulg opt_len; /* bit length of current block with optimal trees */ 49528415Speter ulg static_len; /* bit length of current block with static trees */ 49628415Speter ulg compressed_len; /* total bit length of compressed file */ 49728415Speter uInt matches; /* number of string matches in current block */ 49828415Speter int last_eob_len; /* bit length of EOB code for last block */ 49928415Speter 50028415Speter#ifdef DEBUG_ZLIB 50128415Speter ulg bits_sent; /* bit length of the compressed data */ 50228415Speter#endif 50328415Speter 50428415Speter ush bi_buf; 50528415Speter /* Output buffer. bits are inserted starting at the bottom (least 50628415Speter * significant bits). 50728415Speter */ 50828415Speter int bi_valid; 50928415Speter /* Number of valid bits in bi_buf. All bits above the last valid bit 51028415Speter * are always zero. 51128415Speter */ 51228415Speter 51328415Speter} FAR deflate_state; 51428415Speter 51528415Speter/* Output a byte on the stream. 51628415Speter * IN assertion: there is enough room in pending_buf. 51728415Speter */ 51828415Speter#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);} 51928415Speter 52028415Speter 52128415Speter#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 52228415Speter/* Minimum amount of lookahead, except at the end of the input file. 52328415Speter * See deflate.c for comments about the MIN_MATCH+1. 52428415Speter */ 52528415Speter 52628415Speter#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) 52728415Speter/* In order to simplify the code, particularly on 16 bit machines, match 52828415Speter * distances are limited to MAX_DIST instead of WSIZE. 52928415Speter */ 53028415Speter 53128415Speter /* in trees.c */ 53234768Spetervoid _tr_init OF((deflate_state *s)); 53334768Speterint _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); 53434768Speterulg _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len, 53534768Speter int eof)); 53634768Spetervoid _tr_align OF((deflate_state *s)); 53734768Spetervoid _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len, 53828415Speter int eof)); 53934768Spetervoid _tr_stored_type_only OF((deflate_state *)); 54028415Speter 54134768Speter#endif 54234768Speter/* --- deflate.h */ 54328415Speter 54434768Speter/* +++ deflate.c */ 54528415Speter/* deflate.c -- compress data using the deflation algorithm 54634768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 54728415Speter * For conditions of distribution and use, see copyright notice in zlib.h 54828415Speter */ 54928415Speter 55028415Speter/* 55128415Speter * ALGORITHM 55228415Speter * 55328415Speter * The "deflation" process depends on being able to identify portions 55428415Speter * of the input text which are identical to earlier input (within a 55528415Speter * sliding window trailing behind the input currently being processed). 55628415Speter * 55728415Speter * The most straightforward technique turns out to be the fastest for 55828415Speter * most input files: try all possible matches and select the longest. 55928415Speter * The key feature of this algorithm is that insertions into the string 56028415Speter * dictionary are very simple and thus fast, and deletions are avoided 56128415Speter * completely. Insertions are performed at each input character, whereas 56228415Speter * string matches are performed only when the previous match ends. So it 56328415Speter * is preferable to spend more time in matches to allow very fast string 56428415Speter * insertions and avoid deletions. The matching algorithm for small 56528415Speter * strings is inspired from that of Rabin & Karp. A brute force approach 56628415Speter * is used to find longer strings when a small match has been found. 56728415Speter * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 56828415Speter * (by Leonid Broukhis). 56928415Speter * A previous version of this file used a more sophisticated algorithm 57028415Speter * (by Fiala and Greene) which is guaranteed to run in linear amortized 57128415Speter * time, but has a larger average cost, uses more memory and is patented. 57228415Speter * However the F&G algorithm may be faster for some highly redundant 57328415Speter * files if the parameter max_chain_length (described below) is too large. 57428415Speter * 57528415Speter * ACKNOWLEDGEMENTS 57628415Speter * 57728415Speter * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 57828415Speter * I found it in 'freeze' written by Leonid Broukhis. 57928415Speter * Thanks to many people for bug reports and testing. 58028415Speter * 58128415Speter * REFERENCES 58228415Speter * 58334768Speter * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 58434768Speter * Available in ftp://ds.internic.net/rfc/rfc1951.txt 58528415Speter * 58628415Speter * A description of the Rabin and Karp algorithm is given in the book 58728415Speter * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 58828415Speter * 58928415Speter * Fiala,E.R., and Greene,D.H. 59028415Speter * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 59128415Speter * 59228415Speter */ 59328415Speter 59434768Speter/* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */ 59528415Speter 59634768Speter/* #include "deflate.h" */ 59734768Speter 59834768Speterchar deflate_copyright[] = " deflate 1.0.4 Copyright 1995-1996 Jean-loup Gailly "; 59928415Speter/* 60028415Speter If you use the zlib library in a product, an acknowledgment is welcome 60128415Speter in the documentation of your product. If for some reason you cannot 60228415Speter include such an acknowledgment, I would appreciate that you keep this 60328415Speter copyright string in the executable of your product. 60428415Speter */ 60528415Speter 60634768Speter/* =========================================================================== 60734768Speter * Function prototypes. 60834768Speter */ 60934768Spetertypedef enum { 61034768Speter need_more, /* block not completed, need more input or more output */ 61134768Speter block_done, /* block flush performed */ 61234768Speter finish_started, /* finish started, need only more output at next deflate */ 61334768Speter finish_done /* finish done, accept no more input or output */ 61434768Speter} block_state; 61534768Speter 61634768Spetertypedef block_state (*compress_func) OF((deflate_state *s, int flush)); 61734768Speter/* Compression function. Returns the block state after the call. */ 61834768Speter 61934768Speterlocal void fill_window OF((deflate_state *s)); 62034768Speterlocal block_state deflate_stored OF((deflate_state *s, int flush)); 62134768Speterlocal block_state deflate_fast OF((deflate_state *s, int flush)); 62234768Speterlocal block_state deflate_slow OF((deflate_state *s, int flush)); 62334768Speterlocal void lm_init OF((deflate_state *s)); 62434768Speterlocal void putShortMSB OF((deflate_state *s, uInt b)); 62534768Speterlocal void flush_pending OF((z_streamp strm)); 62634768Speterlocal int read_buf OF((z_streamp strm, charf *buf, unsigned size)); 62734768Speter#ifdef ASMV 62834768Speter void match_init OF((void)); /* asm code initialization */ 62934768Speter uInt longest_match OF((deflate_state *s, IPos cur_match)); 63034768Speter#else 63134768Speterlocal uInt longest_match OF((deflate_state *s, IPos cur_match)); 63234768Speter#endif 63334768Speter 63434768Speter#ifdef DEBUG_ZLIB 63534768Speterlocal void check_match OF((deflate_state *s, IPos start, IPos match, 63634768Speter int length)); 63734768Speter#endif 63834768Speter 63934768Speter/* =========================================================================== 64034768Speter * Local data 64134768Speter */ 64234768Speter 64328415Speter#define NIL 0 64428415Speter/* Tail of hash chains */ 64528415Speter 64628415Speter#ifndef TOO_FAR 64728415Speter# define TOO_FAR 4096 64828415Speter#endif 64928415Speter/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 65028415Speter 65128415Speter#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 65228415Speter/* Minimum amount of lookahead, except at the end of the input file. 65328415Speter * See deflate.c for comments about the MIN_MATCH+1. 65428415Speter */ 65528415Speter 65628415Speter/* Values for max_lazy_match, good_match and max_chain_length, depending on 65728415Speter * the desired pack level (0..9). The values given below have been tuned to 65828415Speter * exclude worst case performance for pathological files. Better values may be 65928415Speter * found for specific files. 66028415Speter */ 66128415Spetertypedef struct config_s { 66228415Speter ush good_length; /* reduce lazy search above this match length */ 66328415Speter ush max_lazy; /* do not perform lazy search above this match length */ 66428415Speter ush nice_length; /* quit search above this match length */ 66528415Speter ush max_chain; 66634768Speter compress_func func; 66728415Speter} config; 66828415Speter 66928415Speterlocal config configuration_table[10] = { 67028415Speter/* good lazy nice chain */ 67134768Speter/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 67234768Speter/* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ 67334768Speter/* 2 */ {4, 5, 16, 8, deflate_fast}, 67434768Speter/* 3 */ {4, 6, 32, 32, deflate_fast}, 67528415Speter 67634768Speter/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 67734768Speter/* 5 */ {8, 16, 32, 32, deflate_slow}, 67834768Speter/* 6 */ {8, 16, 128, 128, deflate_slow}, 67934768Speter/* 7 */ {8, 32, 128, 256, deflate_slow}, 68034768Speter/* 8 */ {32, 128, 258, 1024, deflate_slow}, 68134768Speter/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ 68228415Speter 68328415Speter/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 68428415Speter * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 68528415Speter * meaning. 68628415Speter */ 68728415Speter 68828415Speter#define EQUAL 0 68928415Speter/* result of memcmp for equal strings */ 69028415Speter 69134768Speter#ifndef NO_DUMMY_DECL 69234768Speterstruct static_tree_desc_s {int dummy;}; /* for buggy compilers */ 69328415Speter#endif 69428415Speter 69528415Speter/* =========================================================================== 69628415Speter * Update a hash value with the given input byte 69728415Speter * IN assertion: all calls to to UPDATE_HASH are made with consecutive 69828415Speter * input characters, so that a running hash key can be computed from the 69928415Speter * previous key instead of complete recalculation each time. 70028415Speter */ 70128415Speter#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 70228415Speter 70328415Speter 70428415Speter/* =========================================================================== 70528415Speter * Insert string str in the dictionary and set match_head to the previous head 70628415Speter * of the hash chain (the most recent string with same hash key). Return 70728415Speter * the previous length of the hash chain. 70828415Speter * IN assertion: all calls to to INSERT_STRING are made with consecutive 70928415Speter * input characters and the first MIN_MATCH bytes of str are valid 71028415Speter * (except for the last MIN_MATCH-1 bytes of the input file). 71128415Speter */ 71228415Speter#define INSERT_STRING(s, str, match_head) \ 71328415Speter (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 71428415Speter s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ 71534768Speter s->head[s->ins_h] = (Pos)(str)) 71628415Speter 71728415Speter/* =========================================================================== 71828415Speter * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 71928415Speter * prev[] will be initialized on the fly. 72028415Speter */ 72128415Speter#define CLEAR_HASH(s) \ 72228415Speter s->head[s->hash_size-1] = NIL; \ 72328415Speter zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 72428415Speter 72528415Speter/* ========================================================================= */ 72634768Speterint deflateInit_(strm, level, version, stream_size) 72734768Speter z_streamp strm; 72828415Speter int level; 72934768Speter const char *version; 73034768Speter int stream_size; 73128415Speter{ 73234768Speter return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 73334768Speter Z_DEFAULT_STRATEGY, version, stream_size); 73428415Speter /* To do: ignore strm->next_in if we use it as window */ 73528415Speter} 73628415Speter 73728415Speter/* ========================================================================= */ 73834768Speterint deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 73934768Speter version, stream_size) 74034768Speter z_streamp strm; 74128415Speter int level; 74228415Speter int method; 74328415Speter int windowBits; 74428415Speter int memLevel; 74528415Speter int strategy; 74634768Speter const char *version; 74734768Speter int stream_size; 74828415Speter{ 74928415Speter deflate_state *s; 75028415Speter int noheader = 0; 75134768Speter static char* my_version = ZLIB_VERSION; 75228415Speter 75334768Speter ushf *overlay; 75434768Speter /* We overlay pending_buf and d_buf+l_buf. This works since the average 75534768Speter * output size for (length,distance) codes is <= 24 bits. 75634768Speter */ 75734768Speter 75834768Speter if (version == Z_NULL || version[0] != my_version[0] || 75934768Speter stream_size != sizeof(z_stream)) { 76034768Speter return Z_VERSION_ERROR; 76134768Speter } 76228415Speter if (strm == Z_NULL) return Z_STREAM_ERROR; 76328415Speter 76428415Speter strm->msg = Z_NULL; 76534768Speter#ifndef NO_ZCFUNCS 76634768Speter if (strm->zalloc == Z_NULL) { 76734768Speter strm->zalloc = zcalloc; 76834768Speter strm->opaque = (voidpf)0; 76934768Speter } 77034768Speter if (strm->zfree == Z_NULL) strm->zfree = zcfree; 77134768Speter#endif 77228415Speter 77328415Speter if (level == Z_DEFAULT_COMPRESSION) level = 6; 77428415Speter 77528415Speter if (windowBits < 0) { /* undocumented feature: suppress zlib header */ 77628415Speter noheader = 1; 77728415Speter windowBits = -windowBits; 77828415Speter } 77934768Speter if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 78093013Sjedgar windowBits < 9 || windowBits > 15 || level < 0 || level > 9 || 78134768Speter strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 78228415Speter return Z_STREAM_ERROR; 78328415Speter } 78434768Speter s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 78528415Speter if (s == Z_NULL) return Z_MEM_ERROR; 78628415Speter strm->state = (struct internal_state FAR *)s; 78728415Speter s->strm = strm; 78828415Speter 78928415Speter s->noheader = noheader; 79028415Speter s->w_bits = windowBits; 79128415Speter s->w_size = 1 << s->w_bits; 79228415Speter s->w_mask = s->w_size - 1; 79328415Speter 79428415Speter s->hash_bits = memLevel + 7; 79528415Speter s->hash_size = 1 << s->hash_bits; 79628415Speter s->hash_mask = s->hash_size - 1; 79728415Speter s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 79828415Speter 79934768Speter s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 80034768Speter s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 80134768Speter s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 80228415Speter 80328415Speter s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 80428415Speter 80534768Speter overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 80634768Speter s->pending_buf = (uchf *) overlay; 80734768Speter s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 80828415Speter 80928415Speter if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 81028415Speter s->pending_buf == Z_NULL) { 81143305Sdillon strm->msg = (const char*)ERR_MSG(Z_MEM_ERROR); 81228415Speter deflateEnd (strm); 81328415Speter return Z_MEM_ERROR; 81428415Speter } 81534768Speter s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 81634768Speter s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 81728415Speter 81828415Speter s->level = level; 81928415Speter s->strategy = strategy; 82028415Speter s->method = (Byte)method; 82128415Speter 82228415Speter return deflateReset(strm); 82328415Speter} 82428415Speter 82528415Speter/* ========================================================================= */ 82634768Speterint deflateSetDictionary (strm, dictionary, dictLength) 82734768Speter z_streamp strm; 82834768Speter const Bytef *dictionary; 82934768Speter uInt dictLength; 83034768Speter{ 83134768Speter deflate_state *s; 83234768Speter uInt length = dictLength; 83334768Speter uInt n; 83434768Speter IPos hash_head = 0; 83534768Speter 83634768Speter if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL) 83734768Speter return Z_STREAM_ERROR; 83834768Speter 83934768Speter s = (deflate_state *) strm->state; 84034768Speter if (s->status != INIT_STATE) return Z_STREAM_ERROR; 84134768Speter 84234768Speter strm->adler = adler32(strm->adler, dictionary, dictLength); 84334768Speter 84434768Speter if (length < MIN_MATCH) return Z_OK; 84534768Speter if (length > MAX_DIST(s)) { 84634768Speter length = MAX_DIST(s); 84734768Speter#ifndef USE_DICT_HEAD 84834768Speter dictionary += dictLength - length; /* use the tail of the dictionary */ 84934768Speter#endif 85034768Speter } 85134768Speter zmemcpy((charf *)s->window, dictionary, length); 85234768Speter s->strstart = length; 85334768Speter s->block_start = (long)length; 85434768Speter 85534768Speter /* Insert all strings in the hash table (except for the last two bytes). 85634768Speter * s->lookahead stays null, so s->ins_h will be recomputed at the next 85734768Speter * call of fill_window. 85834768Speter */ 85934768Speter s->ins_h = s->window[0]; 86034768Speter UPDATE_HASH(s, s->ins_h, s->window[1]); 86134768Speter for (n = 0; n <= length - MIN_MATCH; n++) { 86234768Speter INSERT_STRING(s, n, hash_head); 86334768Speter } 86434768Speter if (hash_head) hash_head = 0; /* to make compiler happy */ 86534768Speter return Z_OK; 86634768Speter} 86734768Speter 86834768Speter/* ========================================================================= */ 86928415Speterint deflateReset (strm) 87034768Speter z_streamp strm; 87128415Speter{ 87228415Speter deflate_state *s; 87328415Speter 87428415Speter if (strm == Z_NULL || strm->state == Z_NULL || 87534768Speter strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR; 87628415Speter 87728415Speter strm->total_in = strm->total_out = 0; 87828415Speter strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 87928415Speter strm->data_type = Z_UNKNOWN; 88028415Speter 88128415Speter s = (deflate_state *)strm->state; 88228415Speter s->pending = 0; 88328415Speter s->pending_out = s->pending_buf; 88428415Speter 88528415Speter if (s->noheader < 0) { 88628415Speter s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */ 88728415Speter } 88828415Speter s->status = s->noheader ? BUSY_STATE : INIT_STATE; 88934768Speter strm->adler = 1; 89034768Speter s->last_flush = Z_NO_FLUSH; 89128415Speter 89234768Speter _tr_init(s); 89328415Speter lm_init(s); 89428415Speter 89528415Speter return Z_OK; 89628415Speter} 89728415Speter 89834768Speter/* ========================================================================= */ 89934768Speterint deflateParams(strm, level, strategy) 90034768Speter z_streamp strm; 90134768Speter int level; 90234768Speter int strategy; 90334768Speter{ 90434768Speter deflate_state *s; 90534768Speter compress_func func; 90634768Speter int err = Z_OK; 90734768Speter 90834768Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 90934768Speter s = (deflate_state *) strm->state; 91034768Speter 91134768Speter if (level == Z_DEFAULT_COMPRESSION) { 91234768Speter level = 6; 91334768Speter } 91434768Speter if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 91534768Speter return Z_STREAM_ERROR; 91634768Speter } 91734768Speter func = configuration_table[s->level].func; 91834768Speter 91934768Speter if (func != configuration_table[level].func && strm->total_in != 0) { 92034768Speter /* Flush the last buffer: */ 92134768Speter err = deflate(strm, Z_PARTIAL_FLUSH); 92234768Speter } 92334768Speter if (s->level != level) { 92434768Speter s->level = level; 92534768Speter s->max_lazy_match = configuration_table[level].max_lazy; 92634768Speter s->good_match = configuration_table[level].good_length; 92734768Speter s->nice_match = configuration_table[level].nice_length; 92834768Speter s->max_chain_length = configuration_table[level].max_chain; 92934768Speter } 93034768Speter s->strategy = strategy; 93134768Speter return err; 93234768Speter} 93334768Speter 93428415Speter/* ========================================================================= 93528415Speter * Put a short in the pending buffer. The 16-bit value is put in MSB order. 93628415Speter * IN assertion: the stream state is correct and there is enough room in 93728415Speter * pending_buf. 93828415Speter */ 93928415Speterlocal void putShortMSB (s, b) 94028415Speter deflate_state *s; 94128415Speter uInt b; 94228415Speter{ 94328415Speter put_byte(s, (Byte)(b >> 8)); 94428415Speter put_byte(s, (Byte)(b & 0xff)); 94528415Speter} 94628415Speter 94728415Speter/* ========================================================================= 94834768Speter * Flush as much pending output as possible. All deflate() output goes 94934768Speter * through this function so some applications may wish to modify it 95034768Speter * to avoid allocating a large strm->next_out buffer and copying into it. 95134768Speter * (See also read_buf()). 95228415Speter */ 95328415Speterlocal void flush_pending(strm) 95434768Speter z_streamp strm; 95528415Speter{ 95634768Speter deflate_state *s = (deflate_state *) strm->state; 95734768Speter unsigned len = s->pending; 95828415Speter 95928415Speter if (len > strm->avail_out) len = strm->avail_out; 96028415Speter if (len == 0) return; 96128415Speter 96234768Speter if (strm->next_out != Z_NULL) { 96334768Speter zmemcpy(strm->next_out, s->pending_out, len); 96428415Speter strm->next_out += len; 96528415Speter } 96634768Speter s->pending_out += len; 96728415Speter strm->total_out += len; 96834768Speter strm->avail_out -= len; 96934768Speter s->pending -= len; 97034768Speter if (s->pending == 0) { 97134768Speter s->pending_out = s->pending_buf; 97228415Speter } 97328415Speter} 97428415Speter 97528415Speter/* ========================================================================= */ 97628415Speterint deflate (strm, flush) 97734768Speter z_streamp strm; 97828415Speter int flush; 97928415Speter{ 98034768Speter int old_flush; /* value of flush param for previous deflate call */ 98134768Speter deflate_state *s; 98228415Speter 98334768Speter if (strm == Z_NULL || strm->state == Z_NULL || 98434768Speter flush > Z_FINISH || flush < 0) { 98534768Speter return Z_STREAM_ERROR; 98634768Speter } 98734768Speter s = (deflate_state *) strm->state; 98834768Speter 98934768Speter if ((strm->next_in == Z_NULL && strm->avail_in != 0) || 99034768Speter (s->status == FINISH_STATE && flush != Z_FINISH)) { 99128415Speter ERR_RETURN(strm, Z_STREAM_ERROR); 99228415Speter } 99328415Speter if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 99428415Speter 99534768Speter s->strm = strm; /* just in case */ 99634768Speter old_flush = s->last_flush; 99734768Speter s->last_flush = flush; 99828415Speter 99928415Speter /* Write the zlib header */ 100034768Speter if (s->status == INIT_STATE) { 100128415Speter 100234768Speter uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 100334768Speter uInt level_flags = (s->level-1) >> 1; 100428415Speter 100528415Speter if (level_flags > 3) level_flags = 3; 100628415Speter header |= (level_flags << 6); 100734768Speter if (s->strstart != 0) header |= PRESET_DICT; 100828415Speter header += 31 - (header % 31); 100928415Speter 101034768Speter s->status = BUSY_STATE; 101134768Speter putShortMSB(s, header); 101234768Speter 101334768Speter /* Save the adler32 of the preset dictionary: */ 101434768Speter if (s->strstart != 0) { 101534768Speter putShortMSB(s, (uInt)(strm->adler >> 16)); 101634768Speter putShortMSB(s, (uInt)(strm->adler & 0xffff)); 101734768Speter } 101834768Speter strm->adler = 1L; 101928415Speter } 102028415Speter 102128415Speter /* Flush as much pending output as possible */ 102234768Speter if (s->pending != 0) { 102328415Speter flush_pending(strm); 102434768Speter if (strm->avail_out == 0) { 102534768Speter /* Since avail_out is 0, deflate will be called again with 102634768Speter * more output space, but possibly with both pending and 102734768Speter * avail_in equal to zero. There won't be anything to do, 102834768Speter * but this is not an error situation so make sure we 102934768Speter * return OK instead of BUF_ERROR at next call of deflate: 103034768Speter */ 103134768Speter s->last_flush = -1; 103234768Speter return Z_OK; 103334768Speter } 103428415Speter 103534768Speter /* Make sure there is something to do and avoid duplicate consecutive 103634768Speter * flushes. For repeated and useless calls with Z_FINISH, we keep 103734768Speter * returning Z_STREAM_END instead of Z_BUFF_ERROR. 103828415Speter */ 103934768Speter } else if (strm->avail_in == 0 && flush <= old_flush && 104034768Speter flush != Z_FINISH) { 104134768Speter ERR_RETURN(strm, Z_BUF_ERROR); 104228415Speter } 104328415Speter 104428415Speter /* User must not provide more input after the first FINISH: */ 104534768Speter if (s->status == FINISH_STATE && strm->avail_in != 0) { 104628415Speter ERR_RETURN(strm, Z_BUF_ERROR); 104728415Speter } 104828415Speter 104928415Speter /* Start a new block or continue the current one. 105028415Speter */ 105134768Speter if (strm->avail_in != 0 || s->lookahead != 0 || 105234768Speter (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 105334768Speter block_state bstate; 105428415Speter 105534768Speter bstate = (*(configuration_table[s->level].func))(s, flush); 105634768Speter 105734768Speter if (bstate == finish_started || bstate == finish_done) { 105834768Speter s->status = FINISH_STATE; 105928415Speter } 106034768Speter if (bstate == need_more || bstate == finish_started) { 106134768Speter if (strm->avail_out == 0) { 106234768Speter s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 106334768Speter } 106428415Speter return Z_OK; 106534768Speter /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 106634768Speter * of deflate should use the same flush parameter to make sure 106734768Speter * that the flush is complete. So we don't have to output an 106834768Speter * empty block here, this will be done at next call. This also 106934768Speter * ensures that for a very small output buffer, we emit at most 107034768Speter * one empty block. 107128415Speter */ 107234768Speter } 107334768Speter if (bstate == block_done) { 107434768Speter if (flush == Z_PARTIAL_FLUSH) { 107534768Speter _tr_align(s); 107634768Speter } else if (flush == Z_PACKET_FLUSH) { 107734768Speter /* Output just the 3-bit `stored' block type value, 107834768Speter but not a zero length. */ 107934768Speter _tr_stored_type_only(s); 108034768Speter } else { /* FULL_FLUSH or SYNC_FLUSH */ 108134768Speter _tr_stored_block(s, (char*)0, 0L, 0); 108234768Speter /* For a full flush, this empty block will be recognized 108334768Speter * as a special marker by inflate_sync(). 108434768Speter */ 108534768Speter if (flush == Z_FULL_FLUSH) { 108634768Speter CLEAR_HASH(s); /* forget history */ 108734768Speter } 108834768Speter } 108934768Speter flush_pending(strm); 109034768Speter if (strm->avail_out == 0) { 109134768Speter s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 109234768Speter return Z_OK; 109328415Speter } 109434768Speter } 109528415Speter } 109628415Speter Assert(strm->avail_out > 0, "bug2"); 109728415Speter 109828415Speter if (flush != Z_FINISH) return Z_OK; 109934768Speter if (s->noheader) return Z_STREAM_END; 110028415Speter 110128415Speter /* Write the zlib trailer (adler32) */ 110234768Speter putShortMSB(s, (uInt)(strm->adler >> 16)); 110334768Speter putShortMSB(s, (uInt)(strm->adler & 0xffff)); 110428415Speter flush_pending(strm); 110528415Speter /* If avail_out is zero, the application will call deflate again 110628415Speter * to flush the rest. 110728415Speter */ 110834768Speter s->noheader = -1; /* write the trailer only once! */ 110934768Speter return s->pending != 0 ? Z_OK : Z_STREAM_END; 111028415Speter} 111128415Speter 111228415Speter/* ========================================================================= */ 111328415Speterint deflateEnd (strm) 111434768Speter z_streamp strm; 111528415Speter{ 111634768Speter int status; 111734768Speter deflate_state *s; 111828415Speter 111934768Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 112034768Speter s = (deflate_state *) strm->state; 112128415Speter 112234768Speter status = s->status; 112334768Speter if (status != INIT_STATE && status != BUSY_STATE && 112434768Speter status != FINISH_STATE) { 112534768Speter return Z_STREAM_ERROR; 112634768Speter } 112728415Speter 112834768Speter /* Deallocate in reverse order of allocations: */ 112934768Speter TRY_FREE(strm, s->pending_buf); 113034768Speter TRY_FREE(strm, s->head); 113134768Speter TRY_FREE(strm, s->prev); 113234768Speter TRY_FREE(strm, s->window); 113334768Speter 113434768Speter ZFREE(strm, s); 113528415Speter strm->state = Z_NULL; 113628415Speter 113734768Speter return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 113834768Speter} 113934768Speter 114034768Speter/* ========================================================================= 114134768Speter * Copy the source state to the destination state. 114234768Speter */ 114334768Speterint deflateCopy (dest, source) 114434768Speter z_streamp dest; 114534768Speter z_streamp source; 114634768Speter{ 114734768Speter deflate_state *ds; 114834768Speter deflate_state *ss; 114934768Speter ushf *overlay; 115034768Speter 115134768Speter if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) 115234768Speter return Z_STREAM_ERROR; 115334768Speter ss = (deflate_state *) source->state; 115434768Speter 115537065Speter zmemcpy(dest, source, sizeof(*dest)); 115634768Speter 115734768Speter ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 115834768Speter if (ds == Z_NULL) return Z_MEM_ERROR; 115934768Speter dest->state = (struct internal_state FAR *) ds; 116037065Speter zmemcpy(ds, ss, sizeof(*ds)); 116134768Speter ds->strm = dest; 116234768Speter 116334768Speter ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 116434768Speter ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 116534768Speter ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 116634768Speter overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 116734768Speter ds->pending_buf = (uchf *) overlay; 116834768Speter 116934768Speter if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 117034768Speter ds->pending_buf == Z_NULL) { 117134768Speter deflateEnd (dest); 117234768Speter return Z_MEM_ERROR; 117334768Speter } 117434768Speter /* ??? following zmemcpy doesn't work for 16-bit MSDOS */ 117534768Speter zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 117634768Speter zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); 117734768Speter zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); 117834768Speter zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 117934768Speter 118034768Speter ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 118134768Speter ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 118234768Speter ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 118334768Speter 118434768Speter ds->l_desc.dyn_tree = ds->dyn_ltree; 118534768Speter ds->d_desc.dyn_tree = ds->dyn_dtree; 118634768Speter ds->bl_desc.dyn_tree = ds->bl_tree; 118734768Speter 118828415Speter return Z_OK; 118928415Speter} 119028415Speter 119128415Speter/* =========================================================================== 119234768Speter * Return the number of bytes of output which are immediately available 119334768Speter * for output from the decompressor. 119434768Speter */ 119534768Speterint deflateOutputPending (strm) 119634768Speter z_streamp strm; 119734768Speter{ 119834768Speter if (strm == Z_NULL || strm->state == Z_NULL) return 0; 119934768Speter 120034768Speter return ((deflate_state *)(strm->state))->pending; 120134768Speter} 120234768Speter 120334768Speter/* =========================================================================== 120428415Speter * Read a new buffer from the current input stream, update the adler32 120534768Speter * and total number of bytes read. All deflate() input goes through 120634768Speter * this function so some applications may wish to modify it to avoid 120734768Speter * allocating a large strm->next_in buffer and copying from it. 120834768Speter * (See also flush_pending()). 120928415Speter */ 121028415Speterlocal int read_buf(strm, buf, size) 121134768Speter z_streamp strm; 121228415Speter charf *buf; 121328415Speter unsigned size; 121428415Speter{ 121528415Speter unsigned len = strm->avail_in; 121628415Speter 121728415Speter if (len > size) len = size; 121828415Speter if (len == 0) return 0; 121928415Speter 122028415Speter strm->avail_in -= len; 122128415Speter 122234768Speter if (!((deflate_state *)(strm->state))->noheader) { 122334768Speter strm->adler = adler32(strm->adler, strm->next_in, len); 122428415Speter } 122528415Speter zmemcpy(buf, strm->next_in, len); 122628415Speter strm->next_in += len; 122728415Speter strm->total_in += len; 122828415Speter 122928415Speter return (int)len; 123028415Speter} 123128415Speter 123228415Speter/* =========================================================================== 123328415Speter * Initialize the "longest match" routines for a new zlib stream 123428415Speter */ 123528415Speterlocal void lm_init (s) 123628415Speter deflate_state *s; 123728415Speter{ 123828415Speter s->window_size = (ulg)2L*s->w_size; 123928415Speter 124028415Speter CLEAR_HASH(s); 124128415Speter 124228415Speter /* Set the default configuration parameters: 124328415Speter */ 124428415Speter s->max_lazy_match = configuration_table[s->level].max_lazy; 124528415Speter s->good_match = configuration_table[s->level].good_length; 124628415Speter s->nice_match = configuration_table[s->level].nice_length; 124728415Speter s->max_chain_length = configuration_table[s->level].max_chain; 124828415Speter 124928415Speter s->strstart = 0; 125028415Speter s->block_start = 0L; 125128415Speter s->lookahead = 0; 125234768Speter s->match_length = s->prev_length = MIN_MATCH-1; 125328415Speter s->match_available = 0; 125428415Speter s->ins_h = 0; 125528415Speter#ifdef ASMV 125628415Speter match_init(); /* initialize the asm code */ 125728415Speter#endif 125828415Speter} 125928415Speter 126028415Speter/* =========================================================================== 126128415Speter * Set match_start to the longest match starting at the given string and 126228415Speter * return its length. Matches shorter or equal to prev_length are discarded, 126328415Speter * in which case the result is equal to prev_length and match_start is 126428415Speter * garbage. 126528415Speter * IN assertions: cur_match is the head of the hash chain for the current 126628415Speter * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 126734768Speter * OUT assertion: the match length is not greater than s->lookahead. 126828415Speter */ 126928415Speter#ifndef ASMV 127028415Speter/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 127128415Speter * match.S. The code will be functionally equivalent. 127228415Speter */ 127334768Speterlocal uInt longest_match(s, cur_match) 127428415Speter deflate_state *s; 127528415Speter IPos cur_match; /* current match */ 127628415Speter{ 127728415Speter unsigned chain_length = s->max_chain_length;/* max hash chain length */ 127828415Speter register Bytef *scan = s->window + s->strstart; /* current string */ 127928415Speter register Bytef *match; /* matched string */ 128028415Speter register int len; /* length of current match */ 128128415Speter int best_len = s->prev_length; /* best match length so far */ 128234768Speter int nice_match = s->nice_match; /* stop if match long enough */ 128328415Speter IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 128428415Speter s->strstart - (IPos)MAX_DIST(s) : NIL; 128528415Speter /* Stop when cur_match becomes <= limit. To simplify the code, 128628415Speter * we prevent matches with the string of window index 0. 128728415Speter */ 128828415Speter Posf *prev = s->prev; 128928415Speter uInt wmask = s->w_mask; 129028415Speter 129128415Speter#ifdef UNALIGNED_OK 129228415Speter /* Compare two bytes at a time. Note: this is not always beneficial. 129328415Speter * Try with and without -DUNALIGNED_OK to check. 129428415Speter */ 129528415Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 129628415Speter register ush scan_start = *(ushf*)scan; 129728415Speter register ush scan_end = *(ushf*)(scan+best_len-1); 129828415Speter#else 129928415Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH; 130028415Speter register Byte scan_end1 = scan[best_len-1]; 130128415Speter register Byte scan_end = scan[best_len]; 130228415Speter#endif 130328415Speter 130428415Speter /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 130528415Speter * It is easy to get rid of this optimization if necessary. 130628415Speter */ 130728415Speter Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 130828415Speter 130928415Speter /* Do not waste too much time if we already have a good match: */ 131028415Speter if (s->prev_length >= s->good_match) { 131128415Speter chain_length >>= 2; 131228415Speter } 131334768Speter /* Do not look for matches beyond the end of the input. This is necessary 131434768Speter * to make deflate deterministic. 131534768Speter */ 131634768Speter if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 131734768Speter 131828415Speter Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 131928415Speter 132028415Speter do { 132128415Speter Assert(cur_match < s->strstart, "no future"); 132228415Speter match = s->window + cur_match; 132328415Speter 132428415Speter /* Skip to next match if the match length cannot increase 132528415Speter * or if the match length is less than 2: 132628415Speter */ 132728415Speter#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 132828415Speter /* This code assumes sizeof(unsigned short) == 2. Do not use 132928415Speter * UNALIGNED_OK if your compiler uses a different size. 133028415Speter */ 133128415Speter if (*(ushf*)(match+best_len-1) != scan_end || 133228415Speter *(ushf*)match != scan_start) continue; 133328415Speter 133428415Speter /* It is not necessary to compare scan[2] and match[2] since they are 133528415Speter * always equal when the other bytes match, given that the hash keys 133628415Speter * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 133728415Speter * strstart+3, +5, ... up to strstart+257. We check for insufficient 133828415Speter * lookahead only every 4th comparison; the 128th check will be made 133928415Speter * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 134028415Speter * necessary to put more guard bytes at the end of the window, or 134128415Speter * to check more often for insufficient lookahead. 134228415Speter */ 134328415Speter Assert(scan[2] == match[2], "scan[2]?"); 134428415Speter scan++, match++; 134528415Speter do { 134628415Speter } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 134728415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 134828415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 134928415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 135028415Speter scan < strend); 135128415Speter /* The funny "do {}" generates better code on most compilers */ 135228415Speter 135328415Speter /* Here, scan <= window+strstart+257 */ 135428415Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 135528415Speter if (*scan == *match) scan++; 135628415Speter 135728415Speter len = (MAX_MATCH - 1) - (int)(strend-scan); 135828415Speter scan = strend - (MAX_MATCH-1); 135928415Speter 136028415Speter#else /* UNALIGNED_OK */ 136128415Speter 136228415Speter if (match[best_len] != scan_end || 136328415Speter match[best_len-1] != scan_end1 || 136428415Speter *match != *scan || 136528415Speter *++match != scan[1]) continue; 136628415Speter 136728415Speter /* The check at best_len-1 can be removed because it will be made 136828415Speter * again later. (This heuristic is not always a win.) 136928415Speter * It is not necessary to compare scan[2] and match[2] since they 137028415Speter * are always equal when the other bytes match, given that 137128415Speter * the hash keys are equal and that HASH_BITS >= 8. 137228415Speter */ 137328415Speter scan += 2, match++; 137428415Speter Assert(*scan == *match, "match[2]?"); 137528415Speter 137628415Speter /* We check for insufficient lookahead only every 8th comparison; 137728415Speter * the 256th check will be made at strstart+258. 137828415Speter */ 137928415Speter do { 138028415Speter } while (*++scan == *++match && *++scan == *++match && 138128415Speter *++scan == *++match && *++scan == *++match && 138228415Speter *++scan == *++match && *++scan == *++match && 138328415Speter *++scan == *++match && *++scan == *++match && 138428415Speter scan < strend); 138528415Speter 138628415Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 138728415Speter 138828415Speter len = MAX_MATCH - (int)(strend - scan); 138928415Speter scan = strend - MAX_MATCH; 139028415Speter 139128415Speter#endif /* UNALIGNED_OK */ 139228415Speter 139328415Speter if (len > best_len) { 139428415Speter s->match_start = cur_match; 139528415Speter best_len = len; 139634768Speter if (len >= nice_match) break; 139728415Speter#ifdef UNALIGNED_OK 139828415Speter scan_end = *(ushf*)(scan+best_len-1); 139928415Speter#else 140028415Speter scan_end1 = scan[best_len-1]; 140128415Speter scan_end = scan[best_len]; 140228415Speter#endif 140328415Speter } 140428415Speter } while ((cur_match = prev[cur_match & wmask]) > limit 140528415Speter && --chain_length != 0); 140628415Speter 140734768Speter if ((uInt)best_len <= s->lookahead) return best_len; 140834768Speter return s->lookahead; 140928415Speter} 141028415Speter#endif /* ASMV */ 141128415Speter 141228415Speter#ifdef DEBUG_ZLIB 141328415Speter/* =========================================================================== 141428415Speter * Check that the match at match_start is indeed a match. 141528415Speter */ 141628415Speterlocal void check_match(s, start, match, length) 141728415Speter deflate_state *s; 141828415Speter IPos start, match; 141928415Speter int length; 142028415Speter{ 142128415Speter /* check that the match is indeed a match */ 142234768Speter if (zmemcmp((charf *)s->window + match, 142328415Speter (charf *)s->window + start, length) != EQUAL) { 142434768Speter fprintf(stderr, " start %u, match %u, length %d\n", 142534768Speter start, match, length); 142634768Speter do { 142734768Speter fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 142834768Speter } while (--length != 0); 142928415Speter z_error("invalid match"); 143028415Speter } 143134768Speter if (z_verbose > 1) { 143228415Speter fprintf(stderr,"\\[%d,%d]", start-match, length); 143328415Speter do { putc(s->window[start++], stderr); } while (--length != 0); 143428415Speter } 143528415Speter} 143628415Speter#else 143728415Speter# define check_match(s, start, match, length) 143828415Speter#endif 143928415Speter 144028415Speter/* =========================================================================== 144128415Speter * Fill the window when the lookahead becomes insufficient. 144228415Speter * Updates strstart and lookahead. 144328415Speter * 144428415Speter * IN assertion: lookahead < MIN_LOOKAHEAD 144528415Speter * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 144628415Speter * At least one byte has been read, or avail_in == 0; reads are 144728415Speter * performed for at least two bytes (required for the zip translate_eol 144828415Speter * option -- not supported here). 144928415Speter */ 145028415Speterlocal void fill_window(s) 145128415Speter deflate_state *s; 145228415Speter{ 145328415Speter register unsigned n, m; 145428415Speter register Posf *p; 145528415Speter unsigned more; /* Amount of free space at the end of the window. */ 145628415Speter uInt wsize = s->w_size; 145728415Speter 145828415Speter do { 145928415Speter more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 146028415Speter 146128415Speter /* Deal with !@#$% 64K limit: */ 146228415Speter if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 146328415Speter more = wsize; 146434768Speter 146528415Speter } else if (more == (unsigned)(-1)) { 146628415Speter /* Very unlikely, but possible on 16 bit machine if strstart == 0 146728415Speter * and lookahead == 1 (input done one byte at time) 146828415Speter */ 146928415Speter more--; 147028415Speter 147128415Speter /* If the window is almost full and there is insufficient lookahead, 147228415Speter * move the upper half to the lower one to make room in the upper half. 147328415Speter */ 147428415Speter } else if (s->strstart >= wsize+MAX_DIST(s)) { 147528415Speter 147628415Speter zmemcpy((charf *)s->window, (charf *)s->window+wsize, 147728415Speter (unsigned)wsize); 147828415Speter s->match_start -= wsize; 147928415Speter s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 148028415Speter s->block_start -= (long) wsize; 148128415Speter 148228415Speter /* Slide the hash table (could be avoided with 32 bit values 148334768Speter at the expense of memory usage). We slide even when level == 0 148434768Speter to keep the hash table consistent if we switch back to level > 0 148534768Speter later. (Using level 0 permanently is not an optimal usage of 148634768Speter zlib, so we don't care about this pathological case.) 148728415Speter */ 148828415Speter n = s->hash_size; 148928415Speter p = &s->head[n]; 149028415Speter do { 149128415Speter m = *--p; 149228415Speter *p = (Pos)(m >= wsize ? m-wsize : NIL); 149328415Speter } while (--n); 149428415Speter 149528415Speter n = wsize; 149628415Speter p = &s->prev[n]; 149728415Speter do { 149828415Speter m = *--p; 149928415Speter *p = (Pos)(m >= wsize ? m-wsize : NIL); 150028415Speter /* If n is not on any hash chain, prev[n] is garbage but 150128415Speter * its value will never be used. 150228415Speter */ 150328415Speter } while (--n); 150428415Speter more += wsize; 150528415Speter } 150628415Speter if (s->strm->avail_in == 0) return; 150728415Speter 150828415Speter /* If there was no sliding: 150928415Speter * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 151028415Speter * more == window_size - lookahead - strstart 151128415Speter * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 151228415Speter * => more >= window_size - 2*WSIZE + 2 151328415Speter * In the BIG_MEM or MMAP case (not yet supported), 151428415Speter * window_size == input_size + MIN_LOOKAHEAD && 151528415Speter * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 151628415Speter * Otherwise, window_size == 2*WSIZE so more >= 2. 151728415Speter * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 151828415Speter */ 151928415Speter Assert(more >= 2, "more < 2"); 152028415Speter 152128415Speter n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead, 152228415Speter more); 152328415Speter s->lookahead += n; 152428415Speter 152528415Speter /* Initialize the hash value now that we have some input: */ 152628415Speter if (s->lookahead >= MIN_MATCH) { 152728415Speter s->ins_h = s->window[s->strstart]; 152828415Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 152928415Speter#if MIN_MATCH != 3 153028415Speter Call UPDATE_HASH() MIN_MATCH-3 more times 153128415Speter#endif 153228415Speter } 153328415Speter /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 153428415Speter * but this is not important since only literal bytes will be emitted. 153528415Speter */ 153628415Speter 153728415Speter } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 153828415Speter} 153928415Speter 154028415Speter/* =========================================================================== 154128415Speter * Flush the current block, with given end-of-file flag. 154228415Speter * IN assertion: strstart is set to the end of the current match. 154328415Speter */ 154434768Speter#define FLUSH_BLOCK_ONLY(s, eof) { \ 154534768Speter _tr_flush_block(s, (s->block_start >= 0L ? \ 154634768Speter (charf *)&s->window[(unsigned)s->block_start] : \ 154734768Speter (charf *)Z_NULL), \ 154834768Speter (ulg)((long)s->strstart - s->block_start), \ 154934768Speter (eof)); \ 155028415Speter s->block_start = s->strstart; \ 155128415Speter flush_pending(s->strm); \ 155228415Speter Tracev((stderr,"[FLUSH]")); \ 155328415Speter} 155428415Speter 155528415Speter/* Same but force premature exit if necessary. */ 155634768Speter#define FLUSH_BLOCK(s, eof) { \ 155734768Speter FLUSH_BLOCK_ONLY(s, eof); \ 155834768Speter if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ 155928415Speter} 156028415Speter 156128415Speter/* =========================================================================== 156234768Speter * Copy without compression as much as possible from the input stream, return 156334768Speter * the current block state. 156434768Speter * This function does not insert new strings in the dictionary since 156534768Speter * uncompressible data is probably not useful. This function is used 156634768Speter * only for the level=0 compression option. 156734768Speter * NOTE: this function should be optimized to avoid extra copying from 156834768Speter * window to pending_buf. 156934768Speter */ 157034768Speterlocal block_state deflate_stored(s, flush) 157134768Speter deflate_state *s; 157234768Speter int flush; 157334768Speter{ 157434768Speter /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 157534768Speter * to pending_buf_size, and each stored block has a 5 byte header: 157634768Speter */ 157734768Speter ulg max_block_size = 0xffff; 157834768Speter ulg max_start; 157934768Speter 158034768Speter if (max_block_size > s->pending_buf_size - 5) { 158134768Speter max_block_size = s->pending_buf_size - 5; 158234768Speter } 158334768Speter 158434768Speter /* Copy as much as possible from input to output: */ 158534768Speter for (;;) { 158634768Speter /* Fill the window as much as possible: */ 158734768Speter if (s->lookahead <= 1) { 158834768Speter 158934768Speter Assert(s->strstart < s->w_size+MAX_DIST(s) || 159034768Speter s->block_start >= (long)s->w_size, "slide too late"); 159134768Speter 159234768Speter fill_window(s); 159334768Speter if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 159434768Speter 159534768Speter if (s->lookahead == 0) break; /* flush the current block */ 159634768Speter } 159734768Speter Assert(s->block_start >= 0L, "block gone"); 159834768Speter 159934768Speter s->strstart += s->lookahead; 160034768Speter s->lookahead = 0; 160134768Speter 160234768Speter /* Emit a stored block if pending_buf will be full: */ 160334768Speter max_start = s->block_start + max_block_size; 160434768Speter if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 160534768Speter /* strstart == 0 is possible when wraparound on 16-bit machine */ 160634768Speter s->lookahead = (uInt)(s->strstart - max_start); 160734768Speter s->strstart = (uInt)max_start; 160834768Speter FLUSH_BLOCK(s, 0); 160934768Speter } 161034768Speter /* Flush if we may have to slide, otherwise block_start may become 161134768Speter * negative and the data will be gone: 161234768Speter */ 161334768Speter if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 161434768Speter FLUSH_BLOCK(s, 0); 161534768Speter } 161634768Speter } 161734768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 161834768Speter return flush == Z_FINISH ? finish_done : block_done; 161934768Speter} 162034768Speter 162134768Speter/* =========================================================================== 162234768Speter * Compress as much as possible from the input stream, return the current 162334768Speter * block state. 162434768Speter * This function does not perform lazy evaluation of matches and inserts 162528415Speter * new strings in the dictionary only for unmatched strings or for short 162628415Speter * matches. It is used only for the fast compression options. 162728415Speter */ 162834768Speterlocal block_state deflate_fast(s, flush) 162928415Speter deflate_state *s; 163028415Speter int flush; 163128415Speter{ 163228415Speter IPos hash_head = NIL; /* head of the hash chain */ 163334768Speter int bflush; /* set if current block must be flushed */ 163428415Speter 163528415Speter for (;;) { 163628415Speter /* Make sure that we always have enough lookahead, except 163728415Speter * at the end of the input file. We need MAX_MATCH bytes 163828415Speter * for the next match, plus MIN_MATCH bytes to insert the 163928415Speter * string following the next match. 164028415Speter */ 164128415Speter if (s->lookahead < MIN_LOOKAHEAD) { 164228415Speter fill_window(s); 164334768Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 164434768Speter return need_more; 164534768Speter } 164628415Speter if (s->lookahead == 0) break; /* flush the current block */ 164728415Speter } 164828415Speter 164928415Speter /* Insert the string window[strstart .. strstart+2] in the 165028415Speter * dictionary, and set hash_head to the head of the hash chain: 165128415Speter */ 165228415Speter if (s->lookahead >= MIN_MATCH) { 165328415Speter INSERT_STRING(s, s->strstart, hash_head); 165428415Speter } 165528415Speter 165628415Speter /* Find the longest match, discarding those <= prev_length. 165728415Speter * At this point we have always match_length < MIN_MATCH 165828415Speter */ 165928415Speter if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 166028415Speter /* To simplify the code, we prevent matches with the string 166128415Speter * of window index 0 (in particular we have to avoid a match 166228415Speter * of the string with itself at the start of the input file). 166328415Speter */ 166428415Speter if (s->strategy != Z_HUFFMAN_ONLY) { 166528415Speter s->match_length = longest_match (s, hash_head); 166628415Speter } 166728415Speter /* longest_match() sets match_start */ 166828415Speter } 166928415Speter if (s->match_length >= MIN_MATCH) { 167028415Speter check_match(s, s->strstart, s->match_start, s->match_length); 167128415Speter 167234768Speter bflush = _tr_tally(s, s->strstart - s->match_start, 167334768Speter s->match_length - MIN_MATCH); 167428415Speter 167528415Speter s->lookahead -= s->match_length; 167628415Speter 167728415Speter /* Insert new strings in the hash table only if the match length 167828415Speter * is not too large. This saves time but degrades compression. 167928415Speter */ 168028415Speter if (s->match_length <= s->max_insert_length && 168128415Speter s->lookahead >= MIN_MATCH) { 168228415Speter s->match_length--; /* string at strstart already in hash table */ 168328415Speter do { 168428415Speter s->strstart++; 168528415Speter INSERT_STRING(s, s->strstart, hash_head); 168628415Speter /* strstart never exceeds WSIZE-MAX_MATCH, so there are 168728415Speter * always MIN_MATCH bytes ahead. 168828415Speter */ 168928415Speter } while (--s->match_length != 0); 169028415Speter s->strstart++; 169128415Speter } else { 169228415Speter s->strstart += s->match_length; 169328415Speter s->match_length = 0; 169428415Speter s->ins_h = s->window[s->strstart]; 169528415Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 169628415Speter#if MIN_MATCH != 3 169728415Speter Call UPDATE_HASH() MIN_MATCH-3 more times 169828415Speter#endif 169928415Speter /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 170028415Speter * matter since it will be recomputed at next deflate call. 170128415Speter */ 170228415Speter } 170328415Speter } else { 170428415Speter /* No match, output a literal byte */ 170528415Speter Tracevv((stderr,"%c", s->window[s->strstart])); 170634768Speter bflush = _tr_tally (s, 0, s->window[s->strstart]); 170728415Speter s->lookahead--; 170828415Speter s->strstart++; 170928415Speter } 171034768Speter if (bflush) FLUSH_BLOCK(s, 0); 171128415Speter } 171234768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 171334768Speter return flush == Z_FINISH ? finish_done : block_done; 171428415Speter} 171528415Speter 171628415Speter/* =========================================================================== 171728415Speter * Same as above, but achieves better compression. We use a lazy 171828415Speter * evaluation for matches: a match is finally adopted only if there is 171928415Speter * no better match at the next window position. 172028415Speter */ 172134768Speterlocal block_state deflate_slow(s, flush) 172228415Speter deflate_state *s; 172328415Speter int flush; 172428415Speter{ 172528415Speter IPos hash_head = NIL; /* head of hash chain */ 172628415Speter int bflush; /* set if current block must be flushed */ 172728415Speter 172828415Speter /* Process the input block. */ 172928415Speter for (;;) { 173028415Speter /* Make sure that we always have enough lookahead, except 173128415Speter * at the end of the input file. We need MAX_MATCH bytes 173228415Speter * for the next match, plus MIN_MATCH bytes to insert the 173328415Speter * string following the next match. 173428415Speter */ 173528415Speter if (s->lookahead < MIN_LOOKAHEAD) { 173628415Speter fill_window(s); 173734768Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 173834768Speter return need_more; 173934768Speter } 174028415Speter if (s->lookahead == 0) break; /* flush the current block */ 174128415Speter } 174228415Speter 174328415Speter /* Insert the string window[strstart .. strstart+2] in the 174428415Speter * dictionary, and set hash_head to the head of the hash chain: 174528415Speter */ 174628415Speter if (s->lookahead >= MIN_MATCH) { 174728415Speter INSERT_STRING(s, s->strstart, hash_head); 174828415Speter } 174928415Speter 175028415Speter /* Find the longest match, discarding those <= prev_length. 175128415Speter */ 175228415Speter s->prev_length = s->match_length, s->prev_match = s->match_start; 175328415Speter s->match_length = MIN_MATCH-1; 175428415Speter 175528415Speter if (hash_head != NIL && s->prev_length < s->max_lazy_match && 175628415Speter s->strstart - hash_head <= MAX_DIST(s)) { 175728415Speter /* To simplify the code, we prevent matches with the string 175828415Speter * of window index 0 (in particular we have to avoid a match 175928415Speter * of the string with itself at the start of the input file). 176028415Speter */ 176128415Speter if (s->strategy != Z_HUFFMAN_ONLY) { 176228415Speter s->match_length = longest_match (s, hash_head); 176328415Speter } 176428415Speter /* longest_match() sets match_start */ 176528415Speter 176628415Speter if (s->match_length <= 5 && (s->strategy == Z_FILTERED || 176728415Speter (s->match_length == MIN_MATCH && 176828415Speter s->strstart - s->match_start > TOO_FAR))) { 176928415Speter 177028415Speter /* If prev_match is also MIN_MATCH, match_start is garbage 177128415Speter * but we will ignore the current match anyway. 177228415Speter */ 177328415Speter s->match_length = MIN_MATCH-1; 177428415Speter } 177528415Speter } 177628415Speter /* If there was a match at the previous step and the current 177728415Speter * match is not better, output the previous match: 177828415Speter */ 177928415Speter if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 178028415Speter uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 178128415Speter /* Do not insert strings in hash table beyond this. */ 178228415Speter 178328415Speter check_match(s, s->strstart-1, s->prev_match, s->prev_length); 178428415Speter 178534768Speter bflush = _tr_tally(s, s->strstart -1 - s->prev_match, 178634768Speter s->prev_length - MIN_MATCH); 178728415Speter 178828415Speter /* Insert in hash table all strings up to the end of the match. 178928415Speter * strstart-1 and strstart are already inserted. If there is not 179028415Speter * enough lookahead, the last two strings are not inserted in 179128415Speter * the hash table. 179228415Speter */ 179328415Speter s->lookahead -= s->prev_length-1; 179428415Speter s->prev_length -= 2; 179528415Speter do { 179628415Speter if (++s->strstart <= max_insert) { 179728415Speter INSERT_STRING(s, s->strstart, hash_head); 179828415Speter } 179928415Speter } while (--s->prev_length != 0); 180028415Speter s->match_available = 0; 180128415Speter s->match_length = MIN_MATCH-1; 180228415Speter s->strstart++; 180328415Speter 180434768Speter if (bflush) FLUSH_BLOCK(s, 0); 180528415Speter 180628415Speter } else if (s->match_available) { 180728415Speter /* If there was no match at the previous position, output a 180828415Speter * single literal. If there was a match but the current match 180928415Speter * is longer, truncate the previous match to a single literal. 181028415Speter */ 181128415Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 181234768Speter if (_tr_tally (s, 0, s->window[s->strstart-1])) { 181334768Speter FLUSH_BLOCK_ONLY(s, 0); 181428415Speter } 181528415Speter s->strstart++; 181628415Speter s->lookahead--; 181734768Speter if (s->strm->avail_out == 0) return need_more; 181828415Speter } else { 181928415Speter /* There is no previous match to compare with, wait for 182028415Speter * the next step to decide. 182128415Speter */ 182228415Speter s->match_available = 1; 182328415Speter s->strstart++; 182428415Speter s->lookahead--; 182528415Speter } 182628415Speter } 182728415Speter Assert (flush != Z_NO_FLUSH, "no flush?"); 182828415Speter if (s->match_available) { 182928415Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 183034768Speter _tr_tally (s, 0, s->window[s->strstart-1]); 183128415Speter s->match_available = 0; 183228415Speter } 183334768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 183434768Speter return flush == Z_FINISH ? finish_done : block_done; 183528415Speter} 183634768Speter/* --- deflate.c */ 183728415Speter 183834768Speter/* +++ trees.c */ 183928415Speter/* trees.c -- output deflated data using Huffman coding 184034768Speter * Copyright (C) 1995-1996 Jean-loup Gailly 184128415Speter * For conditions of distribution and use, see copyright notice in zlib.h 184228415Speter */ 184328415Speter 184428415Speter/* 184528415Speter * ALGORITHM 184628415Speter * 184728415Speter * The "deflation" process uses several Huffman trees. The more 184828415Speter * common source values are represented by shorter bit sequences. 184928415Speter * 185028415Speter * Each code tree is stored in a compressed form which is itself 185128415Speter * a Huffman encoding of the lengths of all the code strings (in 185228415Speter * ascending order by source values). The actual code strings are 185328415Speter * reconstructed from the lengths in the inflate process, as described 185428415Speter * in the deflate specification. 185528415Speter * 185628415Speter * REFERENCES 185728415Speter * 185828415Speter * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". 185928415Speter * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc 186028415Speter * 186128415Speter * Storer, James A. 186228415Speter * Data Compression: Methods and Theory, pp. 49-50. 186328415Speter * Computer Science Press, 1988. ISBN 0-7167-8156-5. 186428415Speter * 186528415Speter * Sedgewick, R. 186628415Speter * Algorithms, p290. 186728415Speter * Addison-Wesley, 1983. ISBN 0-201-06672-6. 186828415Speter */ 186928415Speter 187034768Speter/* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */ 187128415Speter 187234768Speter/* #include "deflate.h" */ 187334768Speter 187428415Speter#ifdef DEBUG_ZLIB 187528415Speter# include <ctype.h> 187628415Speter#endif 187728415Speter 187828415Speter/* =========================================================================== 187928415Speter * Constants 188028415Speter */ 188128415Speter 188228415Speter#define MAX_BL_BITS 7 188328415Speter/* Bit length codes must not exceed MAX_BL_BITS bits */ 188428415Speter 188528415Speter#define END_BLOCK 256 188628415Speter/* end of block literal code */ 188728415Speter 188828415Speter#define REP_3_6 16 188928415Speter/* repeat previous bit length 3-6 times (2 bits of repeat count) */ 189028415Speter 189128415Speter#define REPZ_3_10 17 189228415Speter/* repeat a zero length 3-10 times (3 bits of repeat count) */ 189328415Speter 189428415Speter#define REPZ_11_138 18 189528415Speter/* repeat a zero length 11-138 times (7 bits of repeat count) */ 189628415Speter 189728415Speterlocal int extra_lbits[LENGTH_CODES] /* extra bits for each length code */ 189828415Speter = {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}; 189928415Speter 190028415Speterlocal int extra_dbits[D_CODES] /* extra bits for each distance code */ 190128415Speter = {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}; 190228415Speter 190328415Speterlocal int extra_blbits[BL_CODES]/* extra bits for each bit length code */ 190428415Speter = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; 190528415Speter 190628415Speterlocal uch bl_order[BL_CODES] 190728415Speter = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; 190828415Speter/* The lengths of the bit length codes are sent in order of decreasing 190928415Speter * probability, to avoid transmitting the lengths for unused bit length codes. 191028415Speter */ 191128415Speter 191228415Speter#define Buf_size (8 * 2*sizeof(char)) 191328415Speter/* Number of bits used within bi_buf. (bi_buf might be implemented on 191428415Speter * more than 16 bits on some systems.) 191528415Speter */ 191628415Speter 191728415Speter/* =========================================================================== 191828415Speter * Local data. These are initialized only once. 191928415Speter */ 192028415Speter 192128415Speterlocal ct_data static_ltree[L_CODES+2]; 192228415Speter/* The static literal tree. Since the bit lengths are imposed, there is no 192328415Speter * need for the L_CODES extra codes used during heap construction. However 192434768Speter * The codes 286 and 287 are needed to build a canonical tree (see _tr_init 192528415Speter * below). 192628415Speter */ 192728415Speter 192828415Speterlocal ct_data static_dtree[D_CODES]; 192928415Speter/* The static distance tree. (Actually a trivial tree since all codes use 193028415Speter * 5 bits.) 193128415Speter */ 193228415Speter 193328415Speterlocal uch dist_code[512]; 193428415Speter/* distance codes. The first 256 values correspond to the distances 193528415Speter * 3 .. 258, the last 256 values correspond to the top 8 bits of 193628415Speter * the 15 bit distances. 193728415Speter */ 193828415Speter 193928415Speterlocal uch length_code[MAX_MATCH-MIN_MATCH+1]; 194028415Speter/* length code for each normalized match length (0 == MIN_MATCH) */ 194128415Speter 194228415Speterlocal int base_length[LENGTH_CODES]; 194328415Speter/* First normalized length for each code (0 = MIN_MATCH) */ 194428415Speter 194528415Speterlocal int base_dist[D_CODES]; 194628415Speter/* First normalized distance for each code (0 = distance of 1) */ 194728415Speter 194828415Speterstruct static_tree_desc_s { 194928415Speter ct_data *static_tree; /* static tree or NULL */ 195028415Speter intf *extra_bits; /* extra bits for each code or NULL */ 195128415Speter int extra_base; /* base index for extra_bits */ 195228415Speter int elems; /* max number of elements in the tree */ 195328415Speter int max_length; /* max bit length for the codes */ 195428415Speter}; 195528415Speter 195628415Speterlocal static_tree_desc static_l_desc = 195728415Speter{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; 195828415Speter 195928415Speterlocal static_tree_desc static_d_desc = 196028415Speter{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; 196128415Speter 196228415Speterlocal static_tree_desc static_bl_desc = 196328415Speter{(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; 196428415Speter 196528415Speter/* =========================================================================== 196628415Speter * Local (static) routines in this file. 196728415Speter */ 196828415Speter 196934768Speterlocal void tr_static_init OF((void)); 197028415Speterlocal void init_block OF((deflate_state *s)); 197128415Speterlocal void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); 197228415Speterlocal void gen_bitlen OF((deflate_state *s, tree_desc *desc)); 197328415Speterlocal void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); 197428415Speterlocal void build_tree OF((deflate_state *s, tree_desc *desc)); 197528415Speterlocal void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); 197628415Speterlocal void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); 197728415Speterlocal int build_bl_tree OF((deflate_state *s)); 197828415Speterlocal void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, 197928415Speter int blcodes)); 198028415Speterlocal void compress_block OF((deflate_state *s, ct_data *ltree, 198128415Speter ct_data *dtree)); 198228415Speterlocal void set_data_type OF((deflate_state *s)); 198328415Speterlocal unsigned bi_reverse OF((unsigned value, int length)); 198428415Speterlocal void bi_windup OF((deflate_state *s)); 198528415Speterlocal void bi_flush OF((deflate_state *s)); 198628415Speterlocal void copy_block OF((deflate_state *s, charf *buf, unsigned len, 198728415Speter int header)); 198828415Speter 198928415Speter#ifndef DEBUG_ZLIB 1990106696Salfred# define send_code(s, c, tree) send_bits(s, tree[(c)].Code, tree[(c)].Len) 199128415Speter /* Send a code of the given tree. c and tree must not have side effects */ 199228415Speter 199328415Speter#else /* DEBUG_ZLIB */ 199428415Speter# define send_code(s, c, tree) \ 199534768Speter { if (verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ 199628415Speter send_bits(s, tree[c].Code, tree[c].Len); } 199728415Speter#endif 199828415Speter 199928415Speter#define d_code(dist) \ 200028415Speter ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)]) 200128415Speter/* Mapping from a distance to a distance code. dist is the distance - 1 and 200228415Speter * must not have side effects. dist_code[256] and dist_code[257] are never 200328415Speter * used. 200428415Speter */ 200528415Speter 200628415Speter/* =========================================================================== 200728415Speter * Output a short LSB first on the stream. 200828415Speter * IN assertion: there is enough room in pendingBuf. 200928415Speter */ 201028415Speter#define put_short(s, w) { \ 201128415Speter put_byte(s, (uch)((w) & 0xff)); \ 201228415Speter put_byte(s, (uch)((ush)(w) >> 8)); \ 201328415Speter} 201428415Speter 201528415Speter/* =========================================================================== 201628415Speter * Send a value on a given number of bits. 201728415Speter * IN assertion: length <= 16 and value fits in length bits. 201828415Speter */ 201928415Speter#ifdef DEBUG_ZLIB 202028415Speterlocal void send_bits OF((deflate_state *s, int value, int length)); 202128415Speter 202228415Speterlocal void send_bits(s, value, length) 202328415Speter deflate_state *s; 202428415Speter int value; /* value to send */ 202528415Speter int length; /* number of bits */ 202628415Speter{ 202734768Speter Tracevv((stderr," l %2d v %4x ", length, value)); 202828415Speter Assert(length > 0 && length <= 15, "invalid length"); 202928415Speter s->bits_sent += (ulg)length; 203028415Speter 203128415Speter /* If not enough room in bi_buf, use (valid) bits from bi_buf and 203228415Speter * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 203328415Speter * unused bits in value. 203428415Speter */ 203528415Speter if (s->bi_valid > (int)Buf_size - length) { 203628415Speter s->bi_buf |= (value << s->bi_valid); 203728415Speter put_short(s, s->bi_buf); 203828415Speter s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); 203928415Speter s->bi_valid += length - Buf_size; 204028415Speter } else { 204128415Speter s->bi_buf |= value << s->bi_valid; 204228415Speter s->bi_valid += length; 204328415Speter } 204428415Speter} 204528415Speter#else /* !DEBUG_ZLIB */ 204628415Speter 204728415Speter#define send_bits(s, value, length) \ 2048106696Salfred{ int len = (length);\ 2049106696Salfred if ((s)->bi_valid > (int)Buf_size - len) {\ 2050106696Salfred int val = (value);\ 2051106696Salfred (s)->bi_buf |= (val << (s)->bi_valid);\ 2052106696Salfred put_short((s), (s)->bi_buf);\ 2053106696Salfred (s)->bi_buf = (ush)val >> (Buf_size - (s)->bi_valid);\ 2054106696Salfred (s)->bi_valid += len - Buf_size;\ 205528415Speter } else {\ 2056106696Salfred (s)->bi_buf |= (value) << (s)->bi_valid;\ 2057106696Salfred (s)->bi_valid += len;\ 205828415Speter }\ 205928415Speter} 206028415Speter#endif /* DEBUG_ZLIB */ 206128415Speter 206228415Speter/* the arguments must not have side effects */ 206328415Speter 206428415Speter/* =========================================================================== 206534768Speter * Initialize the various 'constant' tables. In a multi-threaded environment, 206634768Speter * this function may be called by two threads concurrently, but this is 206734768Speter * harmless since both invocations do exactly the same thing. 206828415Speter */ 206934768Speterlocal void tr_static_init() 207028415Speter{ 207134768Speter static int static_init_done = 0; 207228415Speter int n; /* iterates over tree elements */ 207328415Speter int bits; /* bit counter */ 207428415Speter int length; /* length value */ 207528415Speter int code; /* code value */ 207628415Speter int dist; /* distance index */ 207728415Speter ush bl_count[MAX_BITS+1]; 207828415Speter /* number of codes at each bit length for an optimal tree */ 207928415Speter 208034768Speter if (static_init_done) return; 208134768Speter 208228415Speter /* Initialize the mapping length (0..255) -> length code (0..28) */ 208328415Speter length = 0; 208428415Speter for (code = 0; code < LENGTH_CODES-1; code++) { 208528415Speter base_length[code] = length; 208628415Speter for (n = 0; n < (1<<extra_lbits[code]); n++) { 208728415Speter length_code[length++] = (uch)code; 208828415Speter } 208928415Speter } 209034768Speter Assert (length == 256, "tr_static_init: length != 256"); 209128415Speter /* Note that the length 255 (match length 258) can be represented 209228415Speter * in two different ways: code 284 + 5 bits or code 285, so we 209328415Speter * overwrite length_code[255] to use the best encoding: 209428415Speter */ 209528415Speter length_code[length-1] = (uch)code; 209628415Speter 209728415Speter /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 209828415Speter dist = 0; 209928415Speter for (code = 0 ; code < 16; code++) { 210028415Speter base_dist[code] = dist; 210128415Speter for (n = 0; n < (1<<extra_dbits[code]); n++) { 210228415Speter dist_code[dist++] = (uch)code; 210328415Speter } 210428415Speter } 210534768Speter Assert (dist == 256, "tr_static_init: dist != 256"); 210628415Speter dist >>= 7; /* from now on, all distances are divided by 128 */ 210728415Speter for ( ; code < D_CODES; code++) { 210828415Speter base_dist[code] = dist << 7; 210928415Speter for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 211028415Speter dist_code[256 + dist++] = (uch)code; 211128415Speter } 211228415Speter } 211334768Speter Assert (dist == 256, "tr_static_init: 256+dist != 512"); 211428415Speter 211528415Speter /* Construct the codes of the static literal tree */ 211628415Speter for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 211728415Speter n = 0; 211828415Speter while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 211928415Speter while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 212028415Speter while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 212128415Speter while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 212228415Speter /* Codes 286 and 287 do not exist, but we must include them in the 212328415Speter * tree construction to get a canonical Huffman tree (longest code 212428415Speter * all ones) 212528415Speter */ 212628415Speter gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); 212728415Speter 212828415Speter /* The static distance tree is trivial: */ 212928415Speter for (n = 0; n < D_CODES; n++) { 213028415Speter static_dtree[n].Len = 5; 213134768Speter static_dtree[n].Code = bi_reverse((unsigned)n, 5); 213228415Speter } 213334768Speter static_init_done = 1; 213428415Speter} 213528415Speter 213628415Speter/* =========================================================================== 213728415Speter * Initialize the tree data structures for a new zlib stream. 213828415Speter */ 213934768Spetervoid _tr_init(s) 214028415Speter deflate_state *s; 214128415Speter{ 214234768Speter tr_static_init(); 214328415Speter 214428415Speter s->compressed_len = 0L; 214528415Speter 214628415Speter s->l_desc.dyn_tree = s->dyn_ltree; 214728415Speter s->l_desc.stat_desc = &static_l_desc; 214828415Speter 214928415Speter s->d_desc.dyn_tree = s->dyn_dtree; 215028415Speter s->d_desc.stat_desc = &static_d_desc; 215128415Speter 215228415Speter s->bl_desc.dyn_tree = s->bl_tree; 215328415Speter s->bl_desc.stat_desc = &static_bl_desc; 215428415Speter 215528415Speter s->bi_buf = 0; 215628415Speter s->bi_valid = 0; 215728415Speter s->last_eob_len = 8; /* enough lookahead for inflate */ 215828415Speter#ifdef DEBUG_ZLIB 215928415Speter s->bits_sent = 0L; 216028415Speter#endif 216128415Speter 216228415Speter /* Initialize the first block of the first file: */ 216328415Speter init_block(s); 216428415Speter} 216528415Speter 216628415Speter/* =========================================================================== 216728415Speter * Initialize a new block. 216828415Speter */ 216928415Speterlocal void init_block(s) 217028415Speter deflate_state *s; 217128415Speter{ 217228415Speter int n; /* iterates over tree elements */ 217328415Speter 217428415Speter /* Initialize the trees. */ 217528415Speter for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; 217628415Speter for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; 217728415Speter for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; 217828415Speter 217928415Speter s->dyn_ltree[END_BLOCK].Freq = 1; 218028415Speter s->opt_len = s->static_len = 0L; 218128415Speter s->last_lit = s->matches = 0; 218228415Speter} 218328415Speter 218428415Speter#define SMALLEST 1 218528415Speter/* Index within the heap array of least frequent node in the Huffman tree */ 218628415Speter 218728415Speter 218828415Speter/* =========================================================================== 218928415Speter * Remove the smallest element from the heap and recreate the heap with 219028415Speter * one less element. Updates heap and heap_len. 219128415Speter */ 219228415Speter#define pqremove(s, tree, top) \ 219328415Speter{\ 219428415Speter top = s->heap[SMALLEST]; \ 219528415Speter s->heap[SMALLEST] = s->heap[s->heap_len--]; \ 219628415Speter pqdownheap(s, tree, SMALLEST); \ 219728415Speter} 219828415Speter 219928415Speter/* =========================================================================== 220028415Speter * Compares to subtrees, using the tree depth as tie breaker when 220128415Speter * the subtrees have equal frequency. This minimizes the worst case length. 220228415Speter */ 220328415Speter#define smaller(tree, n, m, depth) \ 220428415Speter (tree[n].Freq < tree[m].Freq || \ 220528415Speter (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 220628415Speter 220728415Speter/* =========================================================================== 220828415Speter * Restore the heap property by moving down the tree starting at node k, 220928415Speter * exchanging a node with the smallest of its two sons if necessary, stopping 221028415Speter * when the heap property is re-established (each father smaller than its 221128415Speter * two sons). 221228415Speter */ 221328415Speterlocal void pqdownheap(s, tree, k) 221428415Speter deflate_state *s; 221528415Speter ct_data *tree; /* the tree to restore */ 221628415Speter int k; /* node to move down */ 221728415Speter{ 221828415Speter int v = s->heap[k]; 221928415Speter int j = k << 1; /* left son of k */ 222028415Speter while (j <= s->heap_len) { 222128415Speter /* Set j to the smallest of the two sons: */ 222228415Speter if (j < s->heap_len && 222328415Speter smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { 222428415Speter j++; 222528415Speter } 222628415Speter /* Exit if v is smaller than both sons */ 222728415Speter if (smaller(tree, v, s->heap[j], s->depth)) break; 222828415Speter 222928415Speter /* Exchange v with the smallest son */ 223028415Speter s->heap[k] = s->heap[j]; k = j; 223128415Speter 223228415Speter /* And continue down the tree, setting j to the left son of k */ 223328415Speter j <<= 1; 223428415Speter } 223528415Speter s->heap[k] = v; 223628415Speter} 223728415Speter 223828415Speter/* =========================================================================== 223928415Speter * Compute the optimal bit lengths for a tree and update the total bit length 224028415Speter * for the current block. 224128415Speter * IN assertion: the fields freq and dad are set, heap[heap_max] and 224228415Speter * above are the tree nodes sorted by increasing frequency. 224328415Speter * OUT assertions: the field len is set to the optimal bit length, the 224428415Speter * array bl_count contains the frequencies for each bit length. 224528415Speter * The length opt_len is updated; static_len is also updated if stree is 224628415Speter * not null. 224728415Speter */ 224828415Speterlocal void gen_bitlen(s, desc) 224928415Speter deflate_state *s; 225028415Speter tree_desc *desc; /* the tree descriptor */ 225128415Speter{ 225228415Speter ct_data *tree = desc->dyn_tree; 225328415Speter int max_code = desc->max_code; 225428415Speter ct_data *stree = desc->stat_desc->static_tree; 225528415Speter intf *extra = desc->stat_desc->extra_bits; 225628415Speter int base = desc->stat_desc->extra_base; 225728415Speter int max_length = desc->stat_desc->max_length; 225828415Speter int h; /* heap index */ 225928415Speter int n, m; /* iterate over the tree elements */ 226028415Speter int bits; /* bit length */ 226128415Speter int xbits; /* extra bits */ 226228415Speter ush f; /* frequency */ 226328415Speter int overflow = 0; /* number of elements with bit length too large */ 226428415Speter 226528415Speter for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; 226628415Speter 226728415Speter /* In a first pass, compute the optimal bit lengths (which may 226828415Speter * overflow in the case of the bit length tree). 226928415Speter */ 227028415Speter tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ 227128415Speter 227228415Speter for (h = s->heap_max+1; h < HEAP_SIZE; h++) { 227328415Speter n = s->heap[h]; 227428415Speter bits = tree[tree[n].Dad].Len + 1; 227528415Speter if (bits > max_length) bits = max_length, overflow++; 227628415Speter tree[n].Len = (ush)bits; 227728415Speter /* We overwrite tree[n].Dad which is no longer needed */ 227828415Speter 227928415Speter if (n > max_code) continue; /* not a leaf node */ 228028415Speter 228128415Speter s->bl_count[bits]++; 228228415Speter xbits = 0; 228328415Speter if (n >= base) xbits = extra[n-base]; 228428415Speter f = tree[n].Freq; 228528415Speter s->opt_len += (ulg)f * (bits + xbits); 228628415Speter if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); 228728415Speter } 228828415Speter if (overflow == 0) return; 228928415Speter 229028415Speter Trace((stderr,"\nbit length overflow\n")); 229128415Speter /* This happens for example on obj2 and pic of the Calgary corpus */ 229228415Speter 229328415Speter /* Find the first bit length which could increase: */ 229428415Speter do { 229528415Speter bits = max_length-1; 229628415Speter while (s->bl_count[bits] == 0) bits--; 229728415Speter s->bl_count[bits]--; /* move one leaf down the tree */ 229828415Speter s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ 229928415Speter s->bl_count[max_length]--; 230028415Speter /* The brother of the overflow item also moves one step up, 230128415Speter * but this does not affect bl_count[max_length] 230228415Speter */ 230328415Speter overflow -= 2; 230428415Speter } while (overflow > 0); 230528415Speter 230628415Speter /* Now recompute all bit lengths, scanning in increasing frequency. 230728415Speter * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 230828415Speter * lengths instead of fixing only the wrong ones. This idea is taken 230928415Speter * from 'ar' written by Haruhiko Okumura.) 231028415Speter */ 231128415Speter for (bits = max_length; bits != 0; bits--) { 231228415Speter n = s->bl_count[bits]; 231328415Speter while (n != 0) { 231428415Speter m = s->heap[--h]; 231528415Speter if (m > max_code) continue; 231628415Speter if (tree[m].Len != (unsigned) bits) { 231728415Speter Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); 231828415Speter s->opt_len += ((long)bits - (long)tree[m].Len) 231928415Speter *(long)tree[m].Freq; 232028415Speter tree[m].Len = (ush)bits; 232128415Speter } 232228415Speter n--; 232328415Speter } 232428415Speter } 232528415Speter} 232628415Speter 232728415Speter/* =========================================================================== 232828415Speter * Generate the codes for a given tree and bit counts (which need not be 232928415Speter * optimal). 233028415Speter * IN assertion: the array bl_count contains the bit length statistics for 233128415Speter * the given tree and the field len is set for all tree elements. 233228415Speter * OUT assertion: the field code is set for all tree elements of non 233328415Speter * zero code length. 233428415Speter */ 233528415Speterlocal void gen_codes (tree, max_code, bl_count) 233628415Speter ct_data *tree; /* the tree to decorate */ 233728415Speter int max_code; /* largest code with non zero frequency */ 233828415Speter ushf *bl_count; /* number of codes at each bit length */ 233928415Speter{ 234028415Speter ush next_code[MAX_BITS+1]; /* next code value for each bit length */ 234128415Speter ush code = 0; /* running code value */ 234228415Speter int bits; /* bit index */ 234328415Speter int n; /* code index */ 234428415Speter 234528415Speter /* The distribution counts are first used to generate the code values 234628415Speter * without bit reversal. 234728415Speter */ 234828415Speter for (bits = 1; bits <= MAX_BITS; bits++) { 234928415Speter next_code[bits] = code = (code + bl_count[bits-1]) << 1; 235028415Speter } 235128415Speter /* Check that the bit counts in bl_count are consistent. The last code 235228415Speter * must be all ones. 235328415Speter */ 235428415Speter Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 235528415Speter "inconsistent bit counts"); 235628415Speter Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); 235728415Speter 235828415Speter for (n = 0; n <= max_code; n++) { 235928415Speter int len = tree[n].Len; 236028415Speter if (len == 0) continue; 236128415Speter /* Now reverse the bits */ 236228415Speter tree[n].Code = bi_reverse(next_code[len]++, len); 236328415Speter 236434768Speter Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", 236528415Speter n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); 236628415Speter } 236728415Speter} 236828415Speter 236928415Speter/* =========================================================================== 237028415Speter * Construct one Huffman tree and assigns the code bit strings and lengths. 237128415Speter * Update the total bit length for the current block. 237228415Speter * IN assertion: the field freq is set for all tree elements. 237328415Speter * OUT assertions: the fields len and code are set to the optimal bit length 237428415Speter * and corresponding code. The length opt_len is updated; static_len is 237528415Speter * also updated if stree is not null. The field max_code is set. 237628415Speter */ 237728415Speterlocal void build_tree(s, desc) 237828415Speter deflate_state *s; 237928415Speter tree_desc *desc; /* the tree descriptor */ 238028415Speter{ 238128415Speter ct_data *tree = desc->dyn_tree; 238228415Speter ct_data *stree = desc->stat_desc->static_tree; 238328415Speter int elems = desc->stat_desc->elems; 238428415Speter int n, m; /* iterate over heap elements */ 238528415Speter int max_code = -1; /* largest code with non zero frequency */ 238628415Speter int node; /* new node being created */ 238728415Speter 238828415Speter /* Construct the initial heap, with least frequent element in 238928415Speter * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 239028415Speter * heap[0] is not used. 239128415Speter */ 239228415Speter s->heap_len = 0, s->heap_max = HEAP_SIZE; 239328415Speter 239428415Speter for (n = 0; n < elems; n++) { 239528415Speter if (tree[n].Freq != 0) { 239628415Speter s->heap[++(s->heap_len)] = max_code = n; 239728415Speter s->depth[n] = 0; 239828415Speter } else { 239928415Speter tree[n].Len = 0; 240028415Speter } 240128415Speter } 240228415Speter 240328415Speter /* The pkzip format requires that at least one distance code exists, 240428415Speter * and that at least one bit should be sent even if there is only one 240528415Speter * possible code. So to avoid special checks later on we force at least 240628415Speter * two codes of non zero frequency. 240728415Speter */ 240828415Speter while (s->heap_len < 2) { 240928415Speter node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); 241028415Speter tree[node].Freq = 1; 241128415Speter s->depth[node] = 0; 241228415Speter s->opt_len--; if (stree) s->static_len -= stree[node].Len; 241328415Speter /* node is 0 or 1 so it does not have extra bits */ 241428415Speter } 241528415Speter desc->max_code = max_code; 241628415Speter 241728415Speter /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 241828415Speter * establish sub-heaps of increasing lengths: 241928415Speter */ 242028415Speter for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); 242128415Speter 242228415Speter /* Construct the Huffman tree by repeatedly combining the least two 242328415Speter * frequent nodes. 242428415Speter */ 242528415Speter node = elems; /* next internal node of the tree */ 242628415Speter do { 242728415Speter pqremove(s, tree, n); /* n = node of least frequency */ 242828415Speter m = s->heap[SMALLEST]; /* m = node of next least frequency */ 242928415Speter 243028415Speter s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ 243128415Speter s->heap[--(s->heap_max)] = m; 243228415Speter 243328415Speter /* Create a new node father of n and m */ 243428415Speter tree[node].Freq = tree[n].Freq + tree[m].Freq; 243528415Speter s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1); 243628415Speter tree[n].Dad = tree[m].Dad = (ush)node; 243728415Speter#ifdef DUMP_BL_TREE 243828415Speter if (tree == s->bl_tree) { 243928415Speter fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", 244028415Speter node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); 244128415Speter } 244228415Speter#endif 244328415Speter /* and insert the new node in the heap */ 244428415Speter s->heap[SMALLEST] = node++; 244528415Speter pqdownheap(s, tree, SMALLEST); 244628415Speter 244728415Speter } while (s->heap_len >= 2); 244828415Speter 244928415Speter s->heap[--(s->heap_max)] = s->heap[SMALLEST]; 245028415Speter 245128415Speter /* At this point, the fields freq and dad are set. We can now 245228415Speter * generate the bit lengths. 245328415Speter */ 245428415Speter gen_bitlen(s, (tree_desc *)desc); 245528415Speter 245628415Speter /* The field len is now set, we can generate the bit codes */ 245728415Speter gen_codes ((ct_data *)tree, max_code, s->bl_count); 245828415Speter} 245928415Speter 246028415Speter/* =========================================================================== 246128415Speter * Scan a literal or distance tree to determine the frequencies of the codes 246228415Speter * in the bit length tree. 246328415Speter */ 246428415Speterlocal void scan_tree (s, tree, max_code) 246528415Speter deflate_state *s; 246628415Speter ct_data *tree; /* the tree to be scanned */ 246728415Speter int max_code; /* and its largest code of non zero frequency */ 246828415Speter{ 246928415Speter int n; /* iterates over all tree elements */ 247028415Speter int prevlen = -1; /* last emitted length */ 247128415Speter int curlen; /* length of current code */ 247228415Speter int nextlen = tree[0].Len; /* length of next code */ 247328415Speter int count = 0; /* repeat count of the current code */ 247428415Speter int max_count = 7; /* max repeat count */ 247528415Speter int min_count = 4; /* min repeat count */ 247628415Speter 247728415Speter if (nextlen == 0) max_count = 138, min_count = 3; 247828415Speter tree[max_code+1].Len = (ush)0xffff; /* guard */ 247928415Speter 248028415Speter for (n = 0; n <= max_code; n++) { 248128415Speter curlen = nextlen; nextlen = tree[n+1].Len; 248228415Speter if (++count < max_count && curlen == nextlen) { 248328415Speter continue; 248428415Speter } else if (count < min_count) { 248528415Speter s->bl_tree[curlen].Freq += count; 248628415Speter } else if (curlen != 0) { 248728415Speter if (curlen != prevlen) s->bl_tree[curlen].Freq++; 248828415Speter s->bl_tree[REP_3_6].Freq++; 248928415Speter } else if (count <= 10) { 249028415Speter s->bl_tree[REPZ_3_10].Freq++; 249128415Speter } else { 249228415Speter s->bl_tree[REPZ_11_138].Freq++; 249328415Speter } 249428415Speter count = 0; prevlen = curlen; 249528415Speter if (nextlen == 0) { 249628415Speter max_count = 138, min_count = 3; 249728415Speter } else if (curlen == nextlen) { 249828415Speter max_count = 6, min_count = 3; 249928415Speter } else { 250028415Speter max_count = 7, min_count = 4; 250128415Speter } 250228415Speter } 250328415Speter} 250428415Speter 250528415Speter/* =========================================================================== 250628415Speter * Send a literal or distance tree in compressed form, using the codes in 250728415Speter * bl_tree. 250828415Speter */ 250928415Speterlocal void send_tree (s, tree, max_code) 251028415Speter deflate_state *s; 251128415Speter ct_data *tree; /* the tree to be scanned */ 251228415Speter int max_code; /* and its largest code of non zero frequency */ 251328415Speter{ 251428415Speter int n; /* iterates over all tree elements */ 251528415Speter int prevlen = -1; /* last emitted length */ 251628415Speter int curlen; /* length of current code */ 251728415Speter int nextlen = tree[0].Len; /* length of next code */ 251828415Speter int count = 0; /* repeat count of the current code */ 251928415Speter int max_count = 7; /* max repeat count */ 252028415Speter int min_count = 4; /* min repeat count */ 252128415Speter 252228415Speter /* tree[max_code+1].Len = -1; */ /* guard already set */ 252328415Speter if (nextlen == 0) max_count = 138, min_count = 3; 252428415Speter 252528415Speter for (n = 0; n <= max_code; n++) { 252628415Speter curlen = nextlen; nextlen = tree[n+1].Len; 252728415Speter if (++count < max_count && curlen == nextlen) { 252828415Speter continue; 252928415Speter } else if (count < min_count) { 253028415Speter do { send_code(s, curlen, s->bl_tree); } while (--count != 0); 253128415Speter 253228415Speter } else if (curlen != 0) { 253328415Speter if (curlen != prevlen) { 253428415Speter send_code(s, curlen, s->bl_tree); count--; 253528415Speter } 253628415Speter Assert(count >= 3 && count <= 6, " 3_6?"); 253728415Speter send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); 253828415Speter 253928415Speter } else if (count <= 10) { 254028415Speter send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); 254128415Speter 254228415Speter } else { 254328415Speter send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); 254428415Speter } 254528415Speter count = 0; prevlen = curlen; 254628415Speter if (nextlen == 0) { 254728415Speter max_count = 138, min_count = 3; 254828415Speter } else if (curlen == nextlen) { 254928415Speter max_count = 6, min_count = 3; 255028415Speter } else { 255128415Speter max_count = 7, min_count = 4; 255228415Speter } 255328415Speter } 255428415Speter} 255528415Speter 255628415Speter/* =========================================================================== 255728415Speter * Construct the Huffman tree for the bit lengths and return the index in 255828415Speter * bl_order of the last bit length code to send. 255928415Speter */ 256028415Speterlocal int build_bl_tree(s) 256128415Speter deflate_state *s; 256228415Speter{ 256328415Speter int max_blindex; /* index of last bit length code of non zero freq */ 256428415Speter 256528415Speter /* Determine the bit length frequencies for literal and distance trees */ 256628415Speter scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); 256728415Speter scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); 256828415Speter 256928415Speter /* Build the bit length tree: */ 257028415Speter build_tree(s, (tree_desc *)(&(s->bl_desc))); 257128415Speter /* opt_len now includes the length of the tree representations, except 257228415Speter * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 257328415Speter */ 257428415Speter 257528415Speter /* Determine the number of bit length codes to send. The pkzip format 257628415Speter * requires that at least 4 bit length codes be sent. (appnote.txt says 257728415Speter * 3 but the actual value used is 4.) 257828415Speter */ 257928415Speter for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 258028415Speter if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; 258128415Speter } 258228415Speter /* Update opt_len to include the bit length tree and counts */ 258328415Speter s->opt_len += 3*(max_blindex+1) + 5+5+4; 258428415Speter Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", 258528415Speter s->opt_len, s->static_len)); 258628415Speter 258728415Speter return max_blindex; 258828415Speter} 258928415Speter 259028415Speter/* =========================================================================== 259128415Speter * Send the header for a block using dynamic Huffman trees: the counts, the 259228415Speter * lengths of the bit length codes, the literal tree and the distance tree. 259328415Speter * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 259428415Speter */ 259528415Speterlocal void send_all_trees(s, lcodes, dcodes, blcodes) 259628415Speter deflate_state *s; 259728415Speter int lcodes, dcodes, blcodes; /* number of codes for each tree */ 259828415Speter{ 259928415Speter int rank; /* index in bl_order */ 260028415Speter 260128415Speter Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); 260228415Speter Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 260328415Speter "too many codes"); 260428415Speter Tracev((stderr, "\nbl counts: ")); 260528415Speter send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ 260628415Speter send_bits(s, dcodes-1, 5); 260728415Speter send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ 260828415Speter for (rank = 0; rank < blcodes; rank++) { 260928415Speter Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 261028415Speter send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); 261128415Speter } 261228415Speter Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); 261328415Speter 261428415Speter send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ 261528415Speter Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); 261628415Speter 261728415Speter send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ 261828415Speter Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); 261928415Speter} 262028415Speter 262128415Speter/* =========================================================================== 262228415Speter * Send a stored block 262328415Speter */ 262434768Spetervoid _tr_stored_block(s, buf, stored_len, eof) 262528415Speter deflate_state *s; 262628415Speter charf *buf; /* input block */ 262728415Speter ulg stored_len; /* length of input block */ 262828415Speter int eof; /* true if this is the last block for a file */ 262928415Speter{ 263028415Speter send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ 263134768Speter s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; 263228415Speter s->compressed_len += (stored_len + 4) << 3; 263328415Speter 263428415Speter copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ 263528415Speter} 263628415Speter 263728415Speter/* Send just the `stored block' type code without any length bytes or data. 263828415Speter */ 263934768Spetervoid _tr_stored_type_only(s) 264028415Speter deflate_state *s; 264128415Speter{ 264228415Speter send_bits(s, (STORED_BLOCK << 1), 3); 264328415Speter bi_windup(s); 264428415Speter s->compressed_len = (s->compressed_len + 3) & ~7L; 264528415Speter} 264628415Speter 264728415Speter 264828415Speter/* =========================================================================== 264928415Speter * Send one empty static block to give enough lookahead for inflate. 265028415Speter * This takes 10 bits, of which 7 may remain in the bit buffer. 265134768Speter * The current inflate code requires 9 bits of lookahead. If the 265234768Speter * last two codes for the previous block (real code plus EOB) were coded 265334768Speter * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode 265434768Speter * the last real code. In this case we send two empty static blocks instead 265534768Speter * of one. (There are no problems if the previous block is stored or fixed.) 265634768Speter * To simplify the code, we assume the worst case of last real code encoded 265734768Speter * on one bit only. 265828415Speter */ 265934768Spetervoid _tr_align(s) 266028415Speter deflate_state *s; 266128415Speter{ 266228415Speter send_bits(s, STATIC_TREES<<1, 3); 266328415Speter send_code(s, END_BLOCK, static_ltree); 266428415Speter s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ 266528415Speter bi_flush(s); 266628415Speter /* Of the 10 bits for the empty block, we have already sent 266734768Speter * (10 - bi_valid) bits. The lookahead for the last real code (before 266834768Speter * the EOB of the previous block) was thus at least one plus the length 266934768Speter * of the EOB plus what we have just sent of the empty static block. 267028415Speter */ 267134768Speter if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { 267228415Speter send_bits(s, STATIC_TREES<<1, 3); 267328415Speter send_code(s, END_BLOCK, static_ltree); 267428415Speter s->compressed_len += 10L; 267528415Speter bi_flush(s); 267628415Speter } 267728415Speter s->last_eob_len = 7; 267828415Speter} 267928415Speter 268028415Speter/* =========================================================================== 268128415Speter * Determine the best encoding for the current block: dynamic trees, static 268228415Speter * trees or store, and output the encoded block to the zip file. This function 268328415Speter * returns the total compressed length for the file so far. 268428415Speter */ 268534768Speterulg _tr_flush_block(s, buf, stored_len, eof) 268628415Speter deflate_state *s; 268728415Speter charf *buf; /* input block, or NULL if too old */ 268828415Speter ulg stored_len; /* length of input block */ 268934768Speter int eof; /* true if this is the last block for a file */ 269028415Speter{ 269128415Speter ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 269234768Speter int max_blindex = 0; /* index of last bit length code of non zero freq */ 269328415Speter 269434768Speter /* Build the Huffman trees unless a stored block is forced */ 269534768Speter if (s->level > 0) { 269628415Speter 269734768Speter /* Check if the file is ascii or binary */ 269834768Speter if (s->data_type == Z_UNKNOWN) set_data_type(s); 269928415Speter 270034768Speter /* Construct the literal and distance trees */ 270134768Speter build_tree(s, (tree_desc *)(&(s->l_desc))); 270234768Speter Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, 270334768Speter s->static_len)); 270428415Speter 270534768Speter build_tree(s, (tree_desc *)(&(s->d_desc))); 270634768Speter Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, 270734768Speter s->static_len)); 270834768Speter /* At this point, opt_len and static_len are the total bit lengths of 270934768Speter * the compressed block data, excluding the tree representations. 271034768Speter */ 271128415Speter 271234768Speter /* Build the bit length tree for the above two trees, and get the index 271334768Speter * in bl_order of the last bit length code to send. 271434768Speter */ 271534768Speter max_blindex = build_bl_tree(s); 271628415Speter 271734768Speter /* Determine the best encoding. Compute first the block length in bytes*/ 271834768Speter opt_lenb = (s->opt_len+3+7)>>3; 271934768Speter static_lenb = (s->static_len+3+7)>>3; 272028415Speter 272134768Speter Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 272234768Speter opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 272334768Speter s->last_lit)); 272428415Speter 272534768Speter if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 272628415Speter 272734768Speter } else { 272834768Speter Assert(buf != (char*)0, "lost buf"); 272934768Speter opt_lenb = static_lenb = stored_len + 5; /* force a stored block */ 273034768Speter } 273134768Speter 273228415Speter /* If compression failed and this is the first and last block, 273328415Speter * and if the .zip file can be seeked (to rewrite the local header), 273428415Speter * the whole file is transformed into a stored file: 273528415Speter */ 273628415Speter#ifdef STORED_FILE_OK 273728415Speter# ifdef FORCE_STORED_FILE 273834768Speter if (eof && s->compressed_len == 0L) { /* force stored file */ 273928415Speter# else 274034768Speter if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) { 274128415Speter# endif 274228415Speter /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ 274328415Speter if (buf == (charf*)0) error ("block vanished"); 274428415Speter 274534768Speter copy_block(s, buf, (unsigned)stored_len, 0); /* without header */ 274628415Speter s->compressed_len = stored_len << 3; 274728415Speter s->method = STORED; 274828415Speter } else 274928415Speter#endif /* STORED_FILE_OK */ 275028415Speter 275128415Speter#ifdef FORCE_STORED 275234768Speter if (buf != (char*)0) { /* force stored block */ 275328415Speter#else 275434768Speter if (stored_len+4 <= opt_lenb && buf != (char*)0) { 275528415Speter /* 4: two words for the lengths */ 275628415Speter#endif 275728415Speter /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 275828415Speter * Otherwise we can't have processed more than WSIZE input bytes since 275928415Speter * the last block flush, because compression would have been 276028415Speter * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 276128415Speter * transform a block into a stored block. 276228415Speter */ 276334768Speter _tr_stored_block(s, buf, stored_len, eof); 276428415Speter 276528415Speter#ifdef FORCE_STATIC 276634768Speter } else if (static_lenb >= 0) { /* force static trees */ 276728415Speter#else 276834768Speter } else if (static_lenb == opt_lenb) { 276928415Speter#endif 277028415Speter send_bits(s, (STATIC_TREES<<1)+eof, 3); 277128415Speter compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); 277228415Speter s->compressed_len += 3 + s->static_len; 277328415Speter } else { 277428415Speter send_bits(s, (DYN_TREES<<1)+eof, 3); 277528415Speter send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, 277628415Speter max_blindex+1); 277728415Speter compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); 277828415Speter s->compressed_len += 3 + s->opt_len; 277928415Speter } 278028415Speter Assert (s->compressed_len == s->bits_sent, "bad compressed size"); 278128415Speter init_block(s); 278228415Speter 278328415Speter if (eof) { 278428415Speter bi_windup(s); 278528415Speter s->compressed_len += 7; /* align on byte boundary */ 278628415Speter } 278728415Speter Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, 278828415Speter s->compressed_len-7*eof)); 278928415Speter 279028415Speter return s->compressed_len >> 3; 279128415Speter} 279228415Speter 279328415Speter/* =========================================================================== 279428415Speter * Save the match info and tally the frequency counts. Return true if 279528415Speter * the current block must be flushed. 279628415Speter */ 279734768Speterint _tr_tally (s, dist, lc) 279828415Speter deflate_state *s; 279934768Speter unsigned dist; /* distance of matched string */ 280034768Speter unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ 280128415Speter{ 280228415Speter s->d_buf[s->last_lit] = (ush)dist; 280328415Speter s->l_buf[s->last_lit++] = (uch)lc; 280428415Speter if (dist == 0) { 280528415Speter /* lc is the unmatched char */ 280628415Speter s->dyn_ltree[lc].Freq++; 280728415Speter } else { 280828415Speter s->matches++; 280928415Speter /* Here, lc is the match length - MIN_MATCH */ 281028415Speter dist--; /* dist = match distance - 1 */ 281128415Speter Assert((ush)dist < (ush)MAX_DIST(s) && 281228415Speter (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 281334768Speter (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match"); 281428415Speter 281528415Speter s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++; 281628415Speter s->dyn_dtree[d_code(dist)].Freq++; 281728415Speter } 281828415Speter 281928415Speter /* Try to guess if it is profitable to stop the current block here */ 282028415Speter if (s->level > 2 && (s->last_lit & 0xfff) == 0) { 282128415Speter /* Compute an upper bound for the compressed length */ 282228415Speter ulg out_length = (ulg)s->last_lit*8L; 282334768Speter ulg in_length = (ulg)((long)s->strstart - s->block_start); 282428415Speter int dcode; 282528415Speter for (dcode = 0; dcode < D_CODES; dcode++) { 282628415Speter out_length += (ulg)s->dyn_dtree[dcode].Freq * 282728415Speter (5L+extra_dbits[dcode]); 282828415Speter } 282928415Speter out_length >>= 3; 283028415Speter Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", 283128415Speter s->last_lit, in_length, out_length, 283228415Speter 100L - out_length*100L/in_length)); 283328415Speter if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; 283428415Speter } 283528415Speter return (s->last_lit == s->lit_bufsize-1); 283628415Speter /* We avoid equality with lit_bufsize because of wraparound at 64K 283728415Speter * on 16 bit machines and because stored blocks are restricted to 283828415Speter * 64K-1 bytes. 283928415Speter */ 284028415Speter} 284128415Speter 284228415Speter/* =========================================================================== 284328415Speter * Send the block data compressed using the given Huffman trees 284428415Speter */ 284528415Speterlocal void compress_block(s, ltree, dtree) 284628415Speter deflate_state *s; 284728415Speter ct_data *ltree; /* literal tree */ 284828415Speter ct_data *dtree; /* distance tree */ 284928415Speter{ 285028415Speter unsigned dist; /* distance of matched string */ 285128415Speter int lc; /* match length or unmatched char (if dist == 0) */ 285228415Speter unsigned lx = 0; /* running index in l_buf */ 285328415Speter unsigned code; /* the code to send */ 285428415Speter int extra; /* number of extra bits to send */ 285528415Speter 285628415Speter if (s->last_lit != 0) do { 285728415Speter dist = s->d_buf[lx]; 285828415Speter lc = s->l_buf[lx++]; 285928415Speter if (dist == 0) { 286028415Speter send_code(s, lc, ltree); /* send a literal byte */ 286128415Speter Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 286228415Speter } else { 286328415Speter /* Here, lc is the match length - MIN_MATCH */ 286428415Speter code = length_code[lc]; 286528415Speter send_code(s, code+LITERALS+1, ltree); /* send the length code */ 286628415Speter extra = extra_lbits[code]; 286728415Speter if (extra != 0) { 286828415Speter lc -= base_length[code]; 286928415Speter send_bits(s, lc, extra); /* send the extra length bits */ 287028415Speter } 287128415Speter dist--; /* dist is now the match distance - 1 */ 287228415Speter code = d_code(dist); 287328415Speter Assert (code < D_CODES, "bad d_code"); 287428415Speter 287528415Speter send_code(s, code, dtree); /* send the distance code */ 287628415Speter extra = extra_dbits[code]; 287728415Speter if (extra != 0) { 287828415Speter dist -= base_dist[code]; 287928415Speter send_bits(s, dist, extra); /* send the extra distance bits */ 288028415Speter } 288128415Speter } /* literal or match pair ? */ 288228415Speter 288328415Speter /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 288428415Speter Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow"); 288528415Speter 288628415Speter } while (lx < s->last_lit); 288728415Speter 288828415Speter send_code(s, END_BLOCK, ltree); 288928415Speter s->last_eob_len = ltree[END_BLOCK].Len; 289028415Speter} 289128415Speter 289228415Speter/* =========================================================================== 289334768Speter * Set the data type to ASCII or BINARY, using a crude approximation: 289428415Speter * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. 289528415Speter * IN assertion: the fields freq of dyn_ltree are set and the total of all 289628415Speter * frequencies does not exceed 64K (to fit in an int on 16 bit machines). 289728415Speter */ 289828415Speterlocal void set_data_type(s) 289928415Speter deflate_state *s; 290028415Speter{ 290128415Speter int n = 0; 290228415Speter unsigned ascii_freq = 0; 290328415Speter unsigned bin_freq = 0; 290428415Speter while (n < 7) bin_freq += s->dyn_ltree[n++].Freq; 290528415Speter while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq; 290628415Speter while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq; 290734768Speter s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII); 290828415Speter} 290928415Speter 291028415Speter/* =========================================================================== 291128415Speter * Reverse the first len bits of a code, using straightforward code (a faster 291228415Speter * method would use a table) 291328415Speter * IN assertion: 1 <= len <= 15 291428415Speter */ 291528415Speterlocal unsigned bi_reverse(code, len) 291628415Speter unsigned code; /* the value to invert */ 291728415Speter int len; /* its bit length */ 291828415Speter{ 291928415Speter register unsigned res = 0; 292028415Speter do { 292128415Speter res |= code & 1; 292228415Speter code >>= 1, res <<= 1; 292328415Speter } while (--len > 0); 292428415Speter return res >> 1; 292528415Speter} 292628415Speter 292728415Speter/* =========================================================================== 292828415Speter * Flush the bit buffer, keeping at most 7 bits in it. 292928415Speter */ 293028415Speterlocal void bi_flush(s) 293128415Speter deflate_state *s; 293228415Speter{ 293328415Speter if (s->bi_valid == 16) { 293428415Speter put_short(s, s->bi_buf); 293528415Speter s->bi_buf = 0; 293628415Speter s->bi_valid = 0; 293728415Speter } else if (s->bi_valid >= 8) { 293828415Speter put_byte(s, (Byte)s->bi_buf); 293928415Speter s->bi_buf >>= 8; 294028415Speter s->bi_valid -= 8; 294128415Speter } 294228415Speter} 294328415Speter 294428415Speter/* =========================================================================== 294528415Speter * Flush the bit buffer and align the output on a byte boundary 294628415Speter */ 294728415Speterlocal void bi_windup(s) 294828415Speter deflate_state *s; 294928415Speter{ 295028415Speter if (s->bi_valid > 8) { 295128415Speter put_short(s, s->bi_buf); 295228415Speter } else if (s->bi_valid > 0) { 295328415Speter put_byte(s, (Byte)s->bi_buf); 295428415Speter } 295528415Speter s->bi_buf = 0; 295628415Speter s->bi_valid = 0; 295728415Speter#ifdef DEBUG_ZLIB 295828415Speter s->bits_sent = (s->bits_sent+7) & ~7; 295928415Speter#endif 296028415Speter} 296128415Speter 296228415Speter/* =========================================================================== 296328415Speter * Copy a stored block, storing first the length and its 296428415Speter * one's complement if requested. 296528415Speter */ 296628415Speterlocal void copy_block(s, buf, len, header) 296728415Speter deflate_state *s; 296828415Speter charf *buf; /* the input data */ 296928415Speter unsigned len; /* its length */ 297028415Speter int header; /* true if block header must be written */ 297128415Speter{ 297228415Speter bi_windup(s); /* align on byte boundary */ 297328415Speter s->last_eob_len = 8; /* enough lookahead for inflate */ 297428415Speter 297528415Speter if (header) { 297628415Speter put_short(s, (ush)len); 297728415Speter put_short(s, (ush)~len); 297828415Speter#ifdef DEBUG_ZLIB 297928415Speter s->bits_sent += 2*16; 298028415Speter#endif 298128415Speter } 298228415Speter#ifdef DEBUG_ZLIB 298328415Speter s->bits_sent += (ulg)len<<3; 298428415Speter#endif 298534768Speter /* bundle up the put_byte(s, *buf++) calls */ 298634768Speter zmemcpy(&s->pending_buf[s->pending], buf, len); 298734768Speter s->pending += len; 298828415Speter} 298934768Speter/* --- trees.c */ 299028415Speter 299134768Speter/* +++ inflate.c */ 299234768Speter/* inflate.c -- zlib interface to inflate modules 299334768Speter * Copyright (C) 1995-1996 Mark Adler 299434768Speter * For conditions of distribution and use, see copyright notice in zlib.h 299534768Speter */ 299628415Speter 299734768Speter/* #include "zutil.h" */ 299834768Speter 299934768Speter/* +++ infblock.h */ 300028415Speter/* infblock.h -- header to use infblock.c 300134768Speter * Copyright (C) 1995-1996 Mark Adler 300228415Speter * For conditions of distribution and use, see copyright notice in zlib.h 300328415Speter */ 300428415Speter 300528415Speter/* WARNING: this file should *not* be used by applications. It is 300628415Speter part of the implementation of the compression library and is 300728415Speter subject to change. Applications should only use zlib.h. 300828415Speter */ 300928415Speter 301028415Speterstruct inflate_blocks_state; 301128415Spetertypedef struct inflate_blocks_state FAR inflate_blocks_statef; 301228415Speter 301334768Speterextern inflate_blocks_statef * inflate_blocks_new OF(( 301434768Speter z_streamp z, 301528415Speter check_func c, /* check function */ 301628415Speter uInt w)); /* window size */ 301728415Speter 301834768Speterextern int inflate_blocks OF(( 301928415Speter inflate_blocks_statef *, 302034768Speter z_streamp , 302128415Speter int)); /* initial return code */ 302228415Speter 302334768Speterextern void inflate_blocks_reset OF(( 302428415Speter inflate_blocks_statef *, 302534768Speter z_streamp , 302628415Speter uLongf *)); /* check value on output */ 302728415Speter 302834768Speterextern int inflate_blocks_free OF(( 302928415Speter inflate_blocks_statef *, 303034768Speter z_streamp , 303128415Speter uLongf *)); /* check value on output */ 303228415Speter 303334768Speterextern void inflate_set_dictionary OF(( 303434768Speter inflate_blocks_statef *s, 303534768Speter const Bytef *d, /* dictionary */ 303634768Speter uInt n)); /* dictionary length */ 303734768Speter 303834768Speterextern int inflate_addhistory OF(( 303928415Speter inflate_blocks_statef *, 304034768Speter z_streamp)); 304128415Speter 304234768Speterextern int inflate_packet_flush OF(( 304328415Speter inflate_blocks_statef *)); 304434768Speter/* --- infblock.h */ 304528415Speter 304634768Speter#ifndef NO_DUMMY_DECL 304734768Speterstruct inflate_blocks_state {int dummy;}; /* for buggy compilers */ 304828415Speter#endif 304928415Speter 305028415Speter/* inflate private state */ 305128415Speterstruct internal_state { 305228415Speter 305328415Speter /* mode */ 305428415Speter enum { 305528415Speter METHOD, /* waiting for method byte */ 305628415Speter FLAG, /* waiting for flag byte */ 305734768Speter DICT4, /* four dictionary check bytes to go */ 305834768Speter DICT3, /* three dictionary check bytes to go */ 305934768Speter DICT2, /* two dictionary check bytes to go */ 306034768Speter DICT1, /* one dictionary check byte to go */ 306134768Speter DICT0, /* waiting for inflateSetDictionary */ 306228415Speter BLOCKS, /* decompressing blocks */ 306328415Speter CHECK4, /* four check bytes to go */ 306428415Speter CHECK3, /* three check bytes to go */ 306528415Speter CHECK2, /* two check bytes to go */ 306628415Speter CHECK1, /* one check byte to go */ 306728415Speter DONE, /* finished check, done */ 306828415Speter BAD} /* got an error--stay here */ 306928415Speter mode; /* current inflate mode */ 307028415Speter 307128415Speter /* mode dependent information */ 307228415Speter union { 307328415Speter uInt method; /* if FLAGS, method byte */ 307428415Speter struct { 307528415Speter uLong was; /* computed check value */ 307628415Speter uLong need; /* stream check value */ 307728415Speter } check; /* if CHECK, check values to compare */ 307828415Speter uInt marker; /* if BAD, inflateSync's marker bytes count */ 307928415Speter } sub; /* submode */ 308028415Speter 308128415Speter /* mode independent information */ 308228415Speter int nowrap; /* flag for no wrapper */ 308328415Speter uInt wbits; /* log2(window size) (8..15, defaults to 15) */ 308428415Speter inflate_blocks_statef 308528415Speter *blocks; /* current inflate_blocks state */ 308628415Speter 308728415Speter}; 308828415Speter 308928415Speter 309028415Speterint inflateReset(z) 309134768Speterz_streamp z; 309228415Speter{ 309328415Speter uLong c; 309428415Speter 309528415Speter if (z == Z_NULL || z->state == Z_NULL) 309628415Speter return Z_STREAM_ERROR; 309728415Speter z->total_in = z->total_out = 0; 309828415Speter z->msg = Z_NULL; 309928415Speter z->state->mode = z->state->nowrap ? BLOCKS : METHOD; 310028415Speter inflate_blocks_reset(z->state->blocks, z, &c); 310128415Speter Trace((stderr, "inflate: reset\n")); 310228415Speter return Z_OK; 310328415Speter} 310428415Speter 310528415Speter 310628415Speterint inflateEnd(z) 310734768Speterz_streamp z; 310828415Speter{ 310928415Speter uLong c; 311028415Speter 311128415Speter if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL) 311228415Speter return Z_STREAM_ERROR; 311328415Speter if (z->state->blocks != Z_NULL) 311428415Speter inflate_blocks_free(z->state->blocks, z, &c); 311534768Speter ZFREE(z, z->state); 311628415Speter z->state = Z_NULL; 311728415Speter Trace((stderr, "inflate: end\n")); 311828415Speter return Z_OK; 311928415Speter} 312028415Speter 312128415Speter 312234768Speterint inflateInit2_(z, w, version, stream_size) 312334768Speterz_streamp z; 312428415Speterint w; 312534768Speterconst char *version; 312634768Speterint stream_size; 312728415Speter{ 312834768Speter if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 312934768Speter stream_size != sizeof(z_stream)) 313034768Speter return Z_VERSION_ERROR; 313134768Speter 313228415Speter /* initialize state */ 313328415Speter if (z == Z_NULL) 313428415Speter return Z_STREAM_ERROR; 313534768Speter z->msg = Z_NULL; 313634768Speter#ifndef NO_ZCFUNCS 313734768Speter if (z->zalloc == Z_NULL) 313834768Speter { 313934768Speter z->zalloc = zcalloc; 314034768Speter z->opaque = (voidpf)0; 314134768Speter } 314234768Speter if (z->zfree == Z_NULL) z->zfree = zcfree; 314334768Speter#endif 314428415Speter if ((z->state = (struct internal_state FAR *) 314534768Speter ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL) 314628415Speter return Z_MEM_ERROR; 314728415Speter z->state->blocks = Z_NULL; 314828415Speter 314928415Speter /* handle undocumented nowrap option (no zlib header or check) */ 315028415Speter z->state->nowrap = 0; 315128415Speter if (w < 0) 315228415Speter { 315328415Speter w = - w; 315428415Speter z->state->nowrap = 1; 315528415Speter } 315628415Speter 315728415Speter /* set window size */ 315828415Speter if (w < 8 || w > 15) 315928415Speter { 316028415Speter inflateEnd(z); 316128415Speter return Z_STREAM_ERROR; 316228415Speter } 316328415Speter z->state->wbits = (uInt)w; 316428415Speter 316528415Speter /* create inflate_blocks state */ 316628415Speter if ((z->state->blocks = 316734768Speter inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, (uInt)1 << w)) 316828415Speter == Z_NULL) 316928415Speter { 317028415Speter inflateEnd(z); 317128415Speter return Z_MEM_ERROR; 317228415Speter } 317328415Speter Trace((stderr, "inflate: allocated\n")); 317428415Speter 317528415Speter /* reset state */ 317628415Speter inflateReset(z); 317728415Speter return Z_OK; 317828415Speter} 317928415Speter 318028415Speter 318134768Speterint inflateInit_(z, version, stream_size) 318234768Speterz_streamp z; 318334768Speterconst char *version; 318434768Speterint stream_size; 318528415Speter{ 318634768Speter return inflateInit2_(z, DEF_WBITS, version, stream_size); 318728415Speter} 318828415Speter 318928415Speter 319028415Speter#define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;} 319128415Speter#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++) 319228415Speter 319328415Speterint inflate(z, f) 319434768Speterz_streamp z; 319528415Speterint f; 319628415Speter{ 319728415Speter int r; 319828415Speter uInt b; 319928415Speter 320034768Speter if (z == Z_NULL || z->state == Z_NULL || z->next_in == Z_NULL || f < 0) 320128415Speter return Z_STREAM_ERROR; 320228415Speter r = Z_BUF_ERROR; 320328415Speter while (1) switch (z->state->mode) 320428415Speter { 320528415Speter case METHOD: 320628415Speter NEEDBYTE 320734768Speter if (((z->state->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED) 320828415Speter { 320928415Speter z->state->mode = BAD; 321034768Speter z->msg = (char*)"unknown compression method"; 321128415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 321228415Speter break; 321328415Speter } 321428415Speter if ((z->state->sub.method >> 4) + 8 > z->state->wbits) 321528415Speter { 321628415Speter z->state->mode = BAD; 321734768Speter z->msg = (char*)"invalid window size"; 321828415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 321928415Speter break; 322028415Speter } 322128415Speter z->state->mode = FLAG; 322228415Speter case FLAG: 322328415Speter NEEDBYTE 322434768Speter b = NEXTBYTE; 322534768Speter if (((z->state->sub.method << 8) + b) % 31) 322628415Speter { 322728415Speter z->state->mode = BAD; 322834768Speter z->msg = (char*)"incorrect header check"; 322928415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 323028415Speter break; 323128415Speter } 323234768Speter Trace((stderr, "inflate: zlib header ok\n")); 323334768Speter if (!(b & PRESET_DICT)) 323428415Speter { 323534768Speter z->state->mode = BLOCKS; 323634768Speter break; 323728415Speter } 323834768Speter z->state->mode = DICT4; 323934768Speter case DICT4: 324034768Speter NEEDBYTE 324134768Speter z->state->sub.check.need = (uLong)NEXTBYTE << 24; 324234768Speter z->state->mode = DICT3; 324334768Speter case DICT3: 324434768Speter NEEDBYTE 324534768Speter z->state->sub.check.need += (uLong)NEXTBYTE << 16; 324634768Speter z->state->mode = DICT2; 324734768Speter case DICT2: 324834768Speter NEEDBYTE 324934768Speter z->state->sub.check.need += (uLong)NEXTBYTE << 8; 325034768Speter z->state->mode = DICT1; 325134768Speter case DICT1: 325234768Speter NEEDBYTE 325334768Speter z->state->sub.check.need += (uLong)NEXTBYTE; 325434768Speter z->adler = z->state->sub.check.need; 325534768Speter z->state->mode = DICT0; 325634768Speter return Z_NEED_DICT; 325734768Speter case DICT0: 325834768Speter z->state->mode = BAD; 325934768Speter z->msg = (char*)"need dictionary"; 326034768Speter z->state->sub.marker = 0; /* can try inflateSync */ 326134768Speter return Z_STREAM_ERROR; 326228415Speter case BLOCKS: 326328415Speter r = inflate_blocks(z->state->blocks, z, r); 326428415Speter if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0) 326528415Speter r = inflate_packet_flush(z->state->blocks); 326628415Speter if (r == Z_DATA_ERROR) 326728415Speter { 326828415Speter z->state->mode = BAD; 326928415Speter z->state->sub.marker = 0; /* can try inflateSync */ 327028415Speter break; 327128415Speter } 327228415Speter if (r != Z_STREAM_END) 327328415Speter return r; 327428415Speter r = Z_OK; 327528415Speter inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was); 327628415Speter if (z->state->nowrap) 327728415Speter { 327828415Speter z->state->mode = DONE; 327928415Speter break; 328028415Speter } 328128415Speter z->state->mode = CHECK4; 328228415Speter case CHECK4: 328328415Speter NEEDBYTE 328428415Speter z->state->sub.check.need = (uLong)NEXTBYTE << 24; 328528415Speter z->state->mode = CHECK3; 328628415Speter case CHECK3: 328728415Speter NEEDBYTE 328828415Speter z->state->sub.check.need += (uLong)NEXTBYTE << 16; 328928415Speter z->state->mode = CHECK2; 329028415Speter case CHECK2: 329128415Speter NEEDBYTE 329228415Speter z->state->sub.check.need += (uLong)NEXTBYTE << 8; 329328415Speter z->state->mode = CHECK1; 329428415Speter case CHECK1: 329528415Speter NEEDBYTE 329628415Speter z->state->sub.check.need += (uLong)NEXTBYTE; 329728415Speter 329828415Speter if (z->state->sub.check.was != z->state->sub.check.need) 329928415Speter { 330028415Speter z->state->mode = BAD; 330134768Speter z->msg = (char*)"incorrect data check"; 330228415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 330328415Speter break; 330428415Speter } 330528415Speter Trace((stderr, "inflate: zlib check ok\n")); 330628415Speter z->state->mode = DONE; 330728415Speter case DONE: 330828415Speter return Z_STREAM_END; 330928415Speter case BAD: 331028415Speter return Z_DATA_ERROR; 331128415Speter default: 331228415Speter return Z_STREAM_ERROR; 331328415Speter } 331428415Speter 331528415Speter empty: 331628415Speter if (f != Z_PACKET_FLUSH) 331728415Speter return r; 331828415Speter z->state->mode = BAD; 331934768Speter z->msg = (char *)"need more for packet flush"; 332028415Speter z->state->sub.marker = 0; /* can try inflateSync */ 332128415Speter return Z_DATA_ERROR; 332228415Speter} 332328415Speter 332434768Speter 332534768Speterint inflateSetDictionary(z, dictionary, dictLength) 332634768Speterz_streamp z; 332734768Speterconst Bytef *dictionary; 332834768SpeteruInt dictLength; 332934768Speter{ 333034768Speter uInt length = dictLength; 333134768Speter 333234768Speter if (z == Z_NULL || z->state == Z_NULL || z->state->mode != DICT0) 333334768Speter return Z_STREAM_ERROR; 333434768Speter 333534768Speter if (adler32(1L, dictionary, dictLength) != z->adler) return Z_DATA_ERROR; 333634768Speter z->adler = 1L; 333734768Speter 333834768Speter if (length >= ((uInt)1<<z->state->wbits)) 333934768Speter { 334034768Speter length = (1<<z->state->wbits)-1; 334134768Speter dictionary += dictLength - length; 334234768Speter } 334334768Speter inflate_set_dictionary(z->state->blocks, dictionary, length); 334434768Speter z->state->mode = BLOCKS; 334534768Speter return Z_OK; 334634768Speter} 334734768Speter 334828415Speter/* 334928415Speter * This subroutine adds the data at next_in/avail_in to the output history 335028415Speter * without performing any output. The output buffer must be "caught up"; 335128415Speter * i.e. no pending output (hence s->read equals s->write), and the state must 335228415Speter * be BLOCKS (i.e. we should be willing to see the start of a series of 335328415Speter * BLOCKS). On exit, the output will also be caught up, and the checksum 335428415Speter * will have been updated if need be. 335528415Speter */ 335628415Speter 335728415Speterint inflateIncomp(z) 335828415Speterz_stream *z; 335928415Speter{ 336028415Speter if (z->state->mode != BLOCKS) 336128415Speter return Z_DATA_ERROR; 336228415Speter return inflate_addhistory(z->state->blocks, z); 336328415Speter} 336428415Speter 336528415Speter 336628415Speterint inflateSync(z) 336734768Speterz_streamp z; 336828415Speter{ 336928415Speter uInt n; /* number of bytes to look at */ 337028415Speter Bytef *p; /* pointer to bytes */ 337128415Speter uInt m; /* number of marker bytes found in a row */ 337228415Speter uLong r, w; /* temporaries to save total_in and total_out */ 337328415Speter 337428415Speter /* set up */ 337528415Speter if (z == Z_NULL || z->state == Z_NULL) 337628415Speter return Z_STREAM_ERROR; 337728415Speter if (z->state->mode != BAD) 337828415Speter { 337928415Speter z->state->mode = BAD; 338028415Speter z->state->sub.marker = 0; 338128415Speter } 338228415Speter if ((n = z->avail_in) == 0) 338328415Speter return Z_BUF_ERROR; 338428415Speter p = z->next_in; 338528415Speter m = z->state->sub.marker; 338628415Speter 338728415Speter /* search */ 338828415Speter while (n && m < 4) 338928415Speter { 339028415Speter if (*p == (Byte)(m < 2 ? 0 : 0xff)) 339128415Speter m++; 339228415Speter else if (*p) 339328415Speter m = 0; 339428415Speter else 339528415Speter m = 4 - m; 339628415Speter p++, n--; 339728415Speter } 339828415Speter 339928415Speter /* restore */ 340028415Speter z->total_in += p - z->next_in; 340128415Speter z->next_in = p; 340228415Speter z->avail_in = n; 340328415Speter z->state->sub.marker = m; 340428415Speter 340528415Speter /* return no joy or set up to restart on a new block */ 340628415Speter if (m != 4) 340728415Speter return Z_DATA_ERROR; 340828415Speter r = z->total_in; w = z->total_out; 340928415Speter inflateReset(z); 341028415Speter z->total_in = r; z->total_out = w; 341128415Speter z->state->mode = BLOCKS; 341228415Speter return Z_OK; 341328415Speter} 341428415Speter 341528415Speter#undef NEEDBYTE 341628415Speter#undef NEXTBYTE 341734768Speter/* --- inflate.c */ 341828415Speter 341934768Speter/* +++ infblock.c */ 342034768Speter/* infblock.c -- interpret and process block types to last block 342134768Speter * Copyright (C) 1995-1996 Mark Adler 342234768Speter * For conditions of distribution and use, see copyright notice in zlib.h 342334768Speter */ 342434768Speter 342534768Speter/* #include "zutil.h" */ 342634768Speter/* #include "infblock.h" */ 342734768Speter 342834768Speter/* +++ inftrees.h */ 342934768Speter/* inftrees.h -- header to use inftrees.c 343034768Speter * Copyright (C) 1995-1996 Mark Adler 343134768Speter * For conditions of distribution and use, see copyright notice in zlib.h 343234768Speter */ 343334768Speter 343434768Speter/* WARNING: this file should *not* be used by applications. It is 343534768Speter part of the implementation of the compression library and is 343634768Speter subject to change. Applications should only use zlib.h. 343734768Speter */ 343834768Speter 343934768Speter/* Huffman code lookup table entry--this entry is four bytes for machines 344034768Speter that have 16-bit pointers (e.g. PC's in the small or medium model). */ 344134768Speter 344234768Spetertypedef struct inflate_huft_s FAR inflate_huft; 344334768Speter 344434768Speterstruct inflate_huft_s { 344534768Speter union { 344634768Speter struct { 344734768Speter Byte Exop; /* number of extra bits or operation */ 344834768Speter Byte Bits; /* number of bits in this code or subcode */ 344934768Speter } what; 345034768Speter Bytef *pad; /* pad structure to a power of 2 (4 bytes for */ 345134768Speter } word; /* 16-bit, 8 bytes for 32-bit machines) */ 345234768Speter union { 345334768Speter uInt Base; /* literal, length base, or distance base */ 345434768Speter inflate_huft *Next; /* pointer to next level of table */ 345534768Speter } more; 345634768Speter}; 345734768Speter 345834768Speter#ifdef DEBUG_ZLIB 345934768Speter extern uInt inflate_hufts; 346034768Speter#endif 346134768Speter 346234768Speterextern int inflate_trees_bits OF(( 346334768Speter uIntf *, /* 19 code lengths */ 346434768Speter uIntf *, /* bits tree desired/actual depth */ 346534768Speter inflate_huft * FAR *, /* bits tree result */ 346634768Speter z_streamp )); /* for zalloc, zfree functions */ 346734768Speter 346834768Speterextern int inflate_trees_dynamic OF(( 346934768Speter uInt, /* number of literal/length codes */ 347034768Speter uInt, /* number of distance codes */ 347134768Speter uIntf *, /* that many (total) code lengths */ 347234768Speter uIntf *, /* literal desired/actual bit depth */ 347334768Speter uIntf *, /* distance desired/actual bit depth */ 347434768Speter inflate_huft * FAR *, /* literal/length tree result */ 347534768Speter inflate_huft * FAR *, /* distance tree result */ 347634768Speter z_streamp )); /* for zalloc, zfree functions */ 347734768Speter 347834768Speterextern int inflate_trees_fixed OF(( 347934768Speter uIntf *, /* literal desired/actual bit depth */ 348034768Speter uIntf *, /* distance desired/actual bit depth */ 348134768Speter inflate_huft * FAR *, /* literal/length tree result */ 348234768Speter inflate_huft * FAR *)); /* distance tree result */ 348334768Speter 348434768Speterextern int inflate_trees_free OF(( 348534768Speter inflate_huft *, /* tables to free */ 348634768Speter z_streamp )); /* for zfree function */ 348734768Speter 348834768Speter/* --- inftrees.h */ 348934768Speter 349034768Speter/* +++ infcodes.h */ 349134768Speter/* infcodes.h -- header to use infcodes.c 349234768Speter * Copyright (C) 1995-1996 Mark Adler 349334768Speter * For conditions of distribution and use, see copyright notice in zlib.h 349434768Speter */ 349534768Speter 349634768Speter/* WARNING: this file should *not* be used by applications. It is 349734768Speter part of the implementation of the compression library and is 349834768Speter subject to change. Applications should only use zlib.h. 349934768Speter */ 350034768Speter 350134768Speterstruct inflate_codes_state; 350234768Spetertypedef struct inflate_codes_state FAR inflate_codes_statef; 350334768Speter 350434768Speterextern inflate_codes_statef *inflate_codes_new OF(( 350534768Speter uInt, uInt, 350634768Speter inflate_huft *, inflate_huft *, 350734768Speter z_streamp )); 350834768Speter 350934768Speterextern int inflate_codes OF(( 351034768Speter inflate_blocks_statef *, 351134768Speter z_streamp , 351234768Speter int)); 351334768Speter 351434768Speterextern void inflate_codes_free OF(( 351534768Speter inflate_codes_statef *, 351634768Speter z_streamp )); 351734768Speter 351834768Speter/* --- infcodes.h */ 351934768Speter 352034768Speter/* +++ infutil.h */ 352128415Speter/* infutil.h -- types and macros common to blocks and codes 352234768Speter * Copyright (C) 1995-1996 Mark Adler 352328415Speter * For conditions of distribution and use, see copyright notice in zlib.h 352428415Speter */ 352528415Speter 352628415Speter/* WARNING: this file should *not* be used by applications. It is 352728415Speter part of the implementation of the compression library and is 352828415Speter subject to change. Applications should only use zlib.h. 352928415Speter */ 353028415Speter 353134768Speter#ifndef _INFUTIL_H 353234768Speter#define _INFUTIL_H 353328415Speter 353434768Spetertypedef enum { 353528415Speter TYPE, /* get type bits (3, including end bit) */ 353628415Speter LENS, /* get lengths for stored */ 353728415Speter STORED, /* processing stored block */ 353828415Speter TABLE, /* get table lengths */ 353928415Speter BTREE, /* get bit lengths tree for a dynamic block */ 354028415Speter DTREE, /* get length, distance trees for a dynamic block */ 354128415Speter CODES, /* processing fixed or dynamic block */ 354228415Speter DRY, /* output remaining window bytes */ 354334768Speter DONEB, /* finished last block, done */ 354434768Speter BADB} /* got a data error--stuck here */ 354534768Speterinflate_block_mode; 354628415Speter 354734768Speter/* inflate blocks semi-private state */ 354834768Speterstruct inflate_blocks_state { 354934768Speter 355034768Speter /* mode */ 355134768Speter inflate_block_mode mode; /* current inflate_block mode */ 355234768Speter 355328415Speter /* mode dependent information */ 355428415Speter union { 355528415Speter uInt left; /* if STORED, bytes left to copy */ 355628415Speter struct { 355728415Speter uInt table; /* table lengths (14 bits) */ 355828415Speter uInt index; /* index into blens (or border) */ 355928415Speter uIntf *blens; /* bit lengths of codes */ 356028415Speter uInt bb; /* bit length tree depth */ 356128415Speter inflate_huft *tb; /* bit length decoding tree */ 356228415Speter } trees; /* if DTREE, decoding info for trees */ 356328415Speter struct { 356434768Speter inflate_huft *tl; 356534768Speter inflate_huft *td; /* trees to free */ 356628415Speter inflate_codes_statef 356728415Speter *codes; 356828415Speter } decode; /* if CODES, current state */ 356928415Speter } sub; /* submode */ 357028415Speter uInt last; /* true if this block is the last block */ 357128415Speter 357228415Speter /* mode independent information */ 357328415Speter uInt bitk; /* bits in bit buffer */ 357428415Speter uLong bitb; /* bit buffer */ 357528415Speter Bytef *window; /* sliding window */ 357628415Speter Bytef *end; /* one byte after sliding window */ 357728415Speter Bytef *read; /* window read pointer */ 357828415Speter Bytef *write; /* window write pointer */ 357928415Speter check_func checkfn; /* check function */ 358028415Speter uLong check; /* check on output */ 358128415Speter 358228415Speter}; 358328415Speter 358428415Speter 358528415Speter/* defines for inflate input/output */ 358628415Speter/* update pointers and return */ 358728415Speter#define UPDBITS {s->bitb=b;s->bitk=k;} 358828415Speter#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;} 358928415Speter#define UPDOUT {s->write=q;} 359028415Speter#define UPDATE {UPDBITS UPDIN UPDOUT} 359128415Speter#define LEAVE {UPDATE return inflate_flush(s,z,r);} 359228415Speter/* get bytes and bits */ 359328415Speter#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;} 359428415Speter#define NEEDBYTE {if(n)r=Z_OK;else LEAVE} 359528415Speter#define NEXTBYTE (n--,*p++) 359628415Speter#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}} 359728415Speter#define DUMPBITS(j) {b>>=(j);k-=(j);} 359828415Speter/* output bytes */ 359934768Speter#define WAVAIL (uInt)(q<s->read?s->read-q-1:s->end-q) 360034768Speter#define LOADOUT {q=s->write;m=(uInt)WAVAIL;} 360134768Speter#define WWRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}} 360228415Speter#define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT} 360334768Speter#define NEEDOUT {if(m==0){WWRAP if(m==0){FLUSH WWRAP if(m==0) LEAVE}}r=Z_OK;} 360428415Speter#define OUTBYTE(a) {*q++=(Byte)(a);m--;} 360528415Speter/* load local pointers */ 360628415Speter#define LOAD {LOADIN LOADOUT} 360728415Speter 360834768Speter/* masks for lower bits (size given to avoid silly warnings with Visual C++) */ 360934768Speterextern uInt inflate_mask[17]; 361028415Speter 361128415Speter/* copy as much as possible from the sliding window to the output area */ 361234768Speterextern int inflate_flush OF(( 361328415Speter inflate_blocks_statef *, 361434768Speter z_streamp , 361528415Speter int)); 361628415Speter 361734768Speter#ifndef NO_DUMMY_DECL 361834768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 361934768Speter#endif 362028415Speter 362134768Speter#endif 362234768Speter/* --- infutil.h */ 362328415Speter 362434768Speter#ifndef NO_DUMMY_DECL 362534768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 362634768Speter#endif 362728415Speter 362828415Speter/* Table for deflate from PKZIP's appnote.txt. */ 362934768Speterlocal const uInt border[] = { /* Order of the bit length code lengths */ 363028415Speter 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 363128415Speter 363228415Speter/* 363328415Speter Notes beyond the 1.93a appnote.txt: 363428415Speter 363528415Speter 1. Distance pointers never point before the beginning of the output 363628415Speter stream. 363728415Speter 2. Distance pointers can point back across blocks, up to 32k away. 363828415Speter 3. There is an implied maximum of 7 bits for the bit length table and 363928415Speter 15 bits for the actual data. 364028415Speter 4. If only one code exists, then it is encoded using one bit. (Zero 364128415Speter would be more efficient, but perhaps a little confusing.) If two 364228415Speter codes exist, they are coded using one bit each (0 and 1). 364328415Speter 5. There is no way of sending zero distance codes--a dummy must be 364428415Speter sent if there are none. (History: a pre 2.0 version of PKZIP would 364528415Speter store blocks with no distance codes, but this was discovered to be 364628415Speter too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 364728415Speter zero distance codes, which is sent as one code of zero bits in 364828415Speter length. 364928415Speter 6. There are up to 286 literal/length codes. Code 256 represents the 365028415Speter end-of-block. Note however that the static length tree defines 365128415Speter 288 codes just to fill out the Huffman codes. Codes 286 and 287 365228415Speter cannot be used though, since there is no length base or extra bits 365328415Speter defined for them. Similarily, there are up to 30 distance codes. 365428415Speter However, static trees define 32 codes (all 5 bits) to fill out the 365528415Speter Huffman codes, but the last two had better not show up in the data. 365628415Speter 7. Unzip can check dynamic Huffman blocks for complete code sets. 365728415Speter The exception is that a single code would not be complete (see #4). 365828415Speter 8. The five bits following the block type is really the number of 365928415Speter literal codes sent minus 257. 366028415Speter 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 366128415Speter (1+6+6). Therefore, to output three times the length, you output 366228415Speter three codes (1+1+1), whereas to output four times the same length, 366328415Speter you only need two codes (1+3). Hmm. 366428415Speter 10. In the tree reconstruction algorithm, Code = Code + Increment 366528415Speter only if BitLength(i) is not zero. (Pretty obvious.) 366628415Speter 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 366728415Speter 12. Note: length code 284 can represent 227-258, but length code 285 366828415Speter really is 258. The last length deserves its own, short code 366928415Speter since it gets used a lot in very redundant files. The length 367028415Speter 258 is special since 258 - 3 (the min match length) is 255. 367128415Speter 13. The literal/length and distance code bit lengths are read as a 367228415Speter single stream of lengths. It is possible (and advantageous) for 367328415Speter a repeat code (16, 17, or 18) to go across the boundary between 367428415Speter the two sets of lengths. 367528415Speter */ 367628415Speter 367728415Speter 367834768Spetervoid inflate_blocks_reset(s, z, c) 367928415Speterinflate_blocks_statef *s; 368034768Speterz_streamp z; 368128415SpeteruLongf *c; 368228415Speter{ 368328415Speter if (s->checkfn != Z_NULL) 368428415Speter *c = s->check; 368528415Speter if (s->mode == BTREE || s->mode == DTREE) 368634768Speter ZFREE(z, s->sub.trees.blens); 368728415Speter if (s->mode == CODES) 368828415Speter { 368928415Speter inflate_codes_free(s->sub.decode.codes, z); 369028415Speter inflate_trees_free(s->sub.decode.td, z); 369128415Speter inflate_trees_free(s->sub.decode.tl, z); 369228415Speter } 369328415Speter s->mode = TYPE; 369428415Speter s->bitk = 0; 369528415Speter s->bitb = 0; 369628415Speter s->read = s->write = s->window; 369728415Speter if (s->checkfn != Z_NULL) 369834768Speter z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0); 369928415Speter Trace((stderr, "inflate: blocks reset\n")); 370028415Speter} 370128415Speter 370228415Speter 370334768Speterinflate_blocks_statef *inflate_blocks_new(z, c, w) 370434768Speterz_streamp z; 370528415Spetercheck_func c; 370628415SpeteruInt w; 370728415Speter{ 370828415Speter inflate_blocks_statef *s; 370928415Speter 371034768Speter if ((s = (inflate_blocks_statef *)ZALLOC 371128415Speter (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) 371228415Speter return s; 371334768Speter if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) 371428415Speter { 371534768Speter ZFREE(z, s); 371628415Speter return Z_NULL; 371728415Speter } 371828415Speter s->end = s->window + w; 371928415Speter s->checkfn = c; 372028415Speter s->mode = TYPE; 372128415Speter Trace((stderr, "inflate: blocks allocated\n")); 372228415Speter inflate_blocks_reset(s, z, &s->check); 372328415Speter return s; 372428415Speter} 372528415Speter 372628415Speter 372734768Speter#ifdef DEBUG_ZLIB 372834768Speter extern uInt inflate_hufts; 372934768Speter#endif 373034768Speterint inflate_blocks(s, z, r) 373128415Speterinflate_blocks_statef *s; 373234768Speterz_streamp z; 373328415Speterint r; 373428415Speter{ 373528415Speter uInt t; /* temporary storage */ 373628415Speter uLong b; /* bit buffer */ 373728415Speter uInt k; /* bits in bit buffer */ 373828415Speter Bytef *p; /* input data pointer */ 373928415Speter uInt n; /* bytes available there */ 374028415Speter Bytef *q; /* output window write pointer */ 374128415Speter uInt m; /* bytes to end of window or read pointer */ 374228415Speter 374328415Speter /* copy input/output information to locals (UPDATE macro restores) */ 374428415Speter LOAD 374528415Speter 374628415Speter /* process input based on current state */ 374728415Speter while (1) switch (s->mode) 374828415Speter { 374928415Speter case TYPE: 375028415Speter NEEDBITS(3) 375128415Speter t = (uInt)b & 7; 375228415Speter s->last = t & 1; 375328415Speter switch (t >> 1) 375428415Speter { 375528415Speter case 0: /* stored */ 375628415Speter Trace((stderr, "inflate: stored block%s\n", 375728415Speter s->last ? " (last)" : "")); 375828415Speter DUMPBITS(3) 375928415Speter t = k & 7; /* go to byte boundary */ 376028415Speter DUMPBITS(t) 376128415Speter s->mode = LENS; /* get length of stored block */ 376228415Speter break; 376328415Speter case 1: /* fixed */ 376428415Speter Trace((stderr, "inflate: fixed codes block%s\n", 376528415Speter s->last ? " (last)" : "")); 376628415Speter { 376728415Speter uInt bl, bd; 376828415Speter inflate_huft *tl, *td; 376928415Speter 377028415Speter inflate_trees_fixed(&bl, &bd, &tl, &td); 377128415Speter s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); 377228415Speter if (s->sub.decode.codes == Z_NULL) 377328415Speter { 377428415Speter r = Z_MEM_ERROR; 377528415Speter LEAVE 377628415Speter } 377728415Speter s->sub.decode.tl = Z_NULL; /* don't try to free these */ 377828415Speter s->sub.decode.td = Z_NULL; 377928415Speter } 378028415Speter DUMPBITS(3) 378128415Speter s->mode = CODES; 378228415Speter break; 378328415Speter case 2: /* dynamic */ 378428415Speter Trace((stderr, "inflate: dynamic codes block%s\n", 378528415Speter s->last ? " (last)" : "")); 378628415Speter DUMPBITS(3) 378728415Speter s->mode = TABLE; 378828415Speter break; 378928415Speter case 3: /* illegal */ 379028415Speter DUMPBITS(3) 379128415Speter s->mode = BADB; 379234768Speter z->msg = (char*)"invalid block type"; 379328415Speter r = Z_DATA_ERROR; 379428415Speter LEAVE 379528415Speter } 379628415Speter break; 379728415Speter case LENS: 379828415Speter NEEDBITS(32) 379934768Speter if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) 380028415Speter { 380128415Speter s->mode = BADB; 380234768Speter z->msg = (char*)"invalid stored block lengths"; 380328415Speter r = Z_DATA_ERROR; 380428415Speter LEAVE 380528415Speter } 380628415Speter s->sub.left = (uInt)b & 0xffff; 380728415Speter b = k = 0; /* dump bits */ 380828415Speter Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); 380934768Speter s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); 381028415Speter break; 381128415Speter case STORED: 381228415Speter if (n == 0) 381328415Speter LEAVE 381428415Speter NEEDOUT 381528415Speter t = s->sub.left; 381628415Speter if (t > n) t = n; 381728415Speter if (t > m) t = m; 381828415Speter zmemcpy(q, p, t); 381928415Speter p += t; n -= t; 382028415Speter q += t; m -= t; 382128415Speter if ((s->sub.left -= t) != 0) 382228415Speter break; 382328415Speter Tracev((stderr, "inflate: stored end, %lu total out\n", 382428415Speter z->total_out + (q >= s->read ? q - s->read : 382528415Speter (s->end - s->read) + (q - s->window)))); 382628415Speter s->mode = s->last ? DRY : TYPE; 382728415Speter break; 382828415Speter case TABLE: 382928415Speter NEEDBITS(14) 383028415Speter s->sub.trees.table = t = (uInt)b & 0x3fff; 383128415Speter#ifndef PKZIP_BUG_WORKAROUND 383228415Speter if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) 383328415Speter { 383428415Speter s->mode = BADB; 383534768Speter z->msg = (char*)"too many length or distance symbols"; 383628415Speter r = Z_DATA_ERROR; 383728415Speter LEAVE 383828415Speter } 383928415Speter#endif 384028415Speter t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); 384128415Speter if (t < 19) 384228415Speter t = 19; 384328415Speter if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) 384428415Speter { 384528415Speter r = Z_MEM_ERROR; 384628415Speter LEAVE 384728415Speter } 384828415Speter DUMPBITS(14) 384928415Speter s->sub.trees.index = 0; 385028415Speter Tracev((stderr, "inflate: table sizes ok\n")); 385128415Speter s->mode = BTREE; 385228415Speter case BTREE: 385328415Speter while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) 385428415Speter { 385528415Speter NEEDBITS(3) 385628415Speter s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; 385728415Speter DUMPBITS(3) 385828415Speter } 385928415Speter while (s->sub.trees.index < 19) 386028415Speter s->sub.trees.blens[border[s->sub.trees.index++]] = 0; 386128415Speter s->sub.trees.bb = 7; 386228415Speter t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, 386328415Speter &s->sub.trees.tb, z); 386428415Speter if (t != Z_OK) 386528415Speter { 386628415Speter r = t; 386790775Sjedgar if (r == Z_DATA_ERROR) { 386890775Sjedgar ZFREE(z, s->sub.trees.blens); 386928415Speter s->mode = BADB; 387090775Sjedgar } 387128415Speter LEAVE 387228415Speter } 387328415Speter s->sub.trees.index = 0; 387428415Speter Tracev((stderr, "inflate: bits tree ok\n")); 387528415Speter s->mode = DTREE; 387628415Speter case DTREE: 387728415Speter while (t = s->sub.trees.table, 387828415Speter s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) 387928415Speter { 388028415Speter inflate_huft *h; 388128415Speter uInt i, j, c; 388228415Speter 388328415Speter t = s->sub.trees.bb; 388428415Speter NEEDBITS(t) 388528415Speter h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); 388628415Speter t = h->word.what.Bits; 388728415Speter c = h->more.Base; 388828415Speter if (c < 16) 388928415Speter { 389028415Speter DUMPBITS(t) 389128415Speter s->sub.trees.blens[s->sub.trees.index++] = c; 389228415Speter } 389328415Speter else /* c == 16..18 */ 389428415Speter { 389528415Speter i = c == 18 ? 7 : c - 14; 389628415Speter j = c == 18 ? 11 : 3; 389728415Speter NEEDBITS(t + i) 389828415Speter DUMPBITS(t) 389928415Speter j += (uInt)b & inflate_mask[i]; 390028415Speter DUMPBITS(i) 390128415Speter i = s->sub.trees.index; 390228415Speter t = s->sub.trees.table; 390328415Speter if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || 390428415Speter (c == 16 && i < 1)) 390528415Speter { 390634768Speter inflate_trees_free(s->sub.trees.tb, z); 390734768Speter ZFREE(z, s->sub.trees.blens); 390828415Speter s->mode = BADB; 390934768Speter z->msg = (char*)"invalid bit length repeat"; 391028415Speter r = Z_DATA_ERROR; 391128415Speter LEAVE 391228415Speter } 391328415Speter c = c == 16 ? s->sub.trees.blens[i - 1] : 0; 391428415Speter do { 391528415Speter s->sub.trees.blens[i++] = c; 391628415Speter } while (--j); 391728415Speter s->sub.trees.index = i; 391828415Speter } 391928415Speter } 392028415Speter inflate_trees_free(s->sub.trees.tb, z); 392128415Speter s->sub.trees.tb = Z_NULL; 392228415Speter { 392328415Speter uInt bl, bd; 392428415Speter inflate_huft *tl, *td; 392528415Speter inflate_codes_statef *c; 392628415Speter 392728415Speter bl = 9; /* must be <= 9 for lookahead assumptions */ 392828415Speter bd = 6; /* must be <= 9 for lookahead assumptions */ 392928415Speter t = s->sub.trees.table; 393034768Speter#ifdef DEBUG_ZLIB 393134768Speter inflate_hufts = 0; 393234768Speter#endif 393328415Speter t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), 393428415Speter s->sub.trees.blens, &bl, &bd, &tl, &td, z); 393528415Speter if (t != Z_OK) 393628415Speter { 393790775Sjedgar if (t == (uInt)Z_DATA_ERROR) { 393890775Sjedgar ZFREE(z, s->sub.trees.blens); 393928415Speter s->mode = BADB; 394090775Sjedgar } 394128415Speter r = t; 394228415Speter LEAVE 394328415Speter } 394434768Speter Tracev((stderr, "inflate: trees ok, %d * %d bytes used\n", 394534768Speter inflate_hufts, sizeof(inflate_huft))); 394628415Speter if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) 394728415Speter { 394828415Speter inflate_trees_free(td, z); 394928415Speter inflate_trees_free(tl, z); 395028415Speter r = Z_MEM_ERROR; 395128415Speter LEAVE 395228415Speter } 395392749Sdillon /* 395492749Sdillon * this ZFREE must occur *BEFORE* we mess with sub.decode, because 395592749Sdillon * sub.trees is union'd with sub.decode. 395692749Sdillon */ 395792749Sdillon ZFREE(z, s->sub.trees.blens); 395828415Speter s->sub.decode.codes = c; 395928415Speter s->sub.decode.tl = tl; 396028415Speter s->sub.decode.td = td; 396128415Speter } 396228415Speter s->mode = CODES; 396328415Speter case CODES: 396428415Speter UPDATE 396528415Speter if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) 396628415Speter return inflate_flush(s, z, r); 396728415Speter r = Z_OK; 396828415Speter inflate_codes_free(s->sub.decode.codes, z); 396928415Speter inflate_trees_free(s->sub.decode.td, z); 397028415Speter inflate_trees_free(s->sub.decode.tl, z); 397128415Speter LOAD 397228415Speter Tracev((stderr, "inflate: codes end, %lu total out\n", 397328415Speter z->total_out + (q >= s->read ? q - s->read : 397428415Speter (s->end - s->read) + (q - s->window)))); 397528415Speter if (!s->last) 397628415Speter { 397728415Speter s->mode = TYPE; 397828415Speter break; 397928415Speter } 398028415Speter if (k > 7) /* return unused byte, if any */ 398128415Speter { 398228415Speter Assert(k < 16, "inflate_codes grabbed too many bytes") 398328415Speter k -= 8; 398428415Speter n++; 398528415Speter p--; /* can always return one */ 398628415Speter } 398728415Speter s->mode = DRY; 398828415Speter case DRY: 398928415Speter FLUSH 399028415Speter if (s->read != s->write) 399128415Speter LEAVE 399228415Speter s->mode = DONEB; 399328415Speter case DONEB: 399428415Speter r = Z_STREAM_END; 399528415Speter LEAVE 399628415Speter case BADB: 399728415Speter r = Z_DATA_ERROR; 399828415Speter LEAVE 399928415Speter default: 400028415Speter r = Z_STREAM_ERROR; 400128415Speter LEAVE 400228415Speter } 400328415Speter} 400428415Speter 400528415Speter 400634768Speterint inflate_blocks_free(s, z, c) 400728415Speterinflate_blocks_statef *s; 400834768Speterz_streamp z; 400928415SpeteruLongf *c; 401028415Speter{ 401128415Speter inflate_blocks_reset(s, z, c); 401234768Speter ZFREE(z, s->window); 401334768Speter ZFREE(z, s); 401428415Speter Trace((stderr, "inflate: blocks freed\n")); 401528415Speter return Z_OK; 401628415Speter} 401728415Speter 401834768Speter 401934768Spetervoid inflate_set_dictionary(s, d, n) 402034768Speterinflate_blocks_statef *s; 402134768Speterconst Bytef *d; 402234768SpeteruInt n; 402334768Speter{ 402434768Speter zmemcpy((charf *)s->window, d, n); 402534768Speter s->read = s->write = s->window + n; 402634768Speter} 402734768Speter 402828415Speter/* 402928415Speter * This subroutine adds the data at next_in/avail_in to the output history 403028415Speter * without performing any output. The output buffer must be "caught up"; 403128415Speter * i.e. no pending output (hence s->read equals s->write), and the state must 403228415Speter * be BLOCKS (i.e. we should be willing to see the start of a series of 403328415Speter * BLOCKS). On exit, the output will also be caught up, and the checksum 403428415Speter * will have been updated if need be. 403528415Speter */ 403634768Speterint inflate_addhistory(s, z) 403728415Speterinflate_blocks_statef *s; 403828415Speterz_stream *z; 403928415Speter{ 404028415Speter uLong b; /* bit buffer */ /* NOT USED HERE */ 404128415Speter uInt k; /* bits in bit buffer */ /* NOT USED HERE */ 404228415Speter uInt t; /* temporary storage */ 404328415Speter Bytef *p; /* input data pointer */ 404428415Speter uInt n; /* bytes available there */ 404528415Speter Bytef *q; /* output window write pointer */ 404628415Speter uInt m; /* bytes to end of window or read pointer */ 404728415Speter 404828415Speter if (s->read != s->write) 404928415Speter return Z_STREAM_ERROR; 405028415Speter if (s->mode != TYPE) 405128415Speter return Z_DATA_ERROR; 405228415Speter 405328415Speter /* we're ready to rock */ 405428415Speter LOAD 405528415Speter /* while there is input ready, copy to output buffer, moving 405628415Speter * pointers as needed. 405728415Speter */ 405828415Speter while (n) { 405928415Speter t = n; /* how many to do */ 406028415Speter /* is there room until end of buffer? */ 406128415Speter if (t > m) t = m; 406228415Speter /* update check information */ 406328415Speter if (s->checkfn != Z_NULL) 406428415Speter s->check = (*s->checkfn)(s->check, q, t); 406528415Speter zmemcpy(q, p, t); 406628415Speter q += t; 406728415Speter p += t; 406828415Speter n -= t; 406928415Speter z->total_out += t; 407028415Speter s->read = q; /* drag read pointer forward */ 407134768Speter/* WWRAP */ /* expand WWRAP macro by hand to handle s->read */ 407228415Speter if (q == s->end) { 407328415Speter s->read = q = s->window; 407428415Speter m = WAVAIL; 407528415Speter } 407628415Speter } 407728415Speter UPDATE 407828415Speter return Z_OK; 407928415Speter} 408028415Speter 408128415Speter 408228415Speter/* 408328415Speter * At the end of a Deflate-compressed PPP packet, we expect to have seen 408428415Speter * a `stored' block type value but not the (zero) length bytes. 408528415Speter */ 408634768Speterint inflate_packet_flush(s) 408728415Speter inflate_blocks_statef *s; 408828415Speter{ 408928415Speter if (s->mode != LENS) 409028415Speter return Z_DATA_ERROR; 409128415Speter s->mode = TYPE; 409228415Speter return Z_OK; 409328415Speter} 409434768Speter/* --- infblock.c */ 409528415Speter 409634768Speter/* +++ inftrees.c */ 409728415Speter/* inftrees.c -- generate Huffman trees for efficient decoding 409834768Speter * Copyright (C) 1995-1996 Mark Adler 409928415Speter * For conditions of distribution and use, see copyright notice in zlib.h 410028415Speter */ 410128415Speter 410234768Speter/* #include "zutil.h" */ 410334768Speter/* #include "inftrees.h" */ 410434768Speter 410534768Speterchar inflate_copyright[] = " inflate 1.0.4 Copyright 1995-1996 Mark Adler "; 410634768Speter/* 410734768Speter If you use the zlib library in a product, an acknowledgment is welcome 410834768Speter in the documentation of your product. If for some reason you cannot 410934768Speter include such an acknowledgment, I would appreciate that you keep this 411034768Speter copyright string in the executable of your product. 411134768Speter */ 411234768Speter 411334768Speter#ifndef NO_DUMMY_DECL 411434768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 411534768Speter#endif 411634768Speter 411728415Speter/* simplify the use of the inflate_huft type with some defines */ 411828415Speter#define base more.Base 411928415Speter#define next more.Next 412028415Speter#define exop word.what.Exop 412128415Speter#define bits word.what.Bits 412228415Speter 412328415Speter 412428415Speterlocal int huft_build OF(( 412528415Speter uIntf *, /* code lengths in bits */ 412628415Speter uInt, /* number of codes */ 412728415Speter uInt, /* number of "simple" codes */ 412834768Speter const uIntf *, /* list of base values for non-simple codes */ 412934768Speter const uIntf *, /* list of extra bits for non-simple codes */ 413028415Speter inflate_huft * FAR*,/* result: starting table */ 413128415Speter uIntf *, /* maximum lookup bits (returns actual) */ 413234768Speter z_streamp )); /* for zalloc function */ 413328415Speter 413428415Speterlocal voidpf falloc OF(( 413528415Speter voidpf, /* opaque pointer (not used) */ 413628415Speter uInt, /* number of items */ 413728415Speter uInt)); /* size of item */ 413828415Speter 413928415Speter/* Tables for deflate from PKZIP's appnote.txt. */ 414034768Speterlocal const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */ 414128415Speter 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 414228415Speter 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 414334768Speter /* see note #13 above about 258 */ 414434768Speterlocal const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */ 414528415Speter 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 414634768Speter 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */ 414734768Speterlocal const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */ 414828415Speter 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 414928415Speter 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 415028415Speter 8193, 12289, 16385, 24577}; 415134768Speterlocal const uInt cpdext[30] = { /* Extra bits for distance codes */ 415228415Speter 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 415328415Speter 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 415428415Speter 12, 12, 13, 13}; 415528415Speter 415628415Speter/* 415728415Speter Huffman code decoding is performed using a multi-level table lookup. 415828415Speter The fastest way to decode is to simply build a lookup table whose 415928415Speter size is determined by the longest code. However, the time it takes 416028415Speter to build this table can also be a factor if the data being decoded 416128415Speter is not very long. The most common codes are necessarily the 416228415Speter shortest codes, so those codes dominate the decoding time, and hence 416328415Speter the speed. The idea is you can have a shorter table that decodes the 416428415Speter shorter, more probable codes, and then point to subsidiary tables for 416528415Speter the longer codes. The time it costs to decode the longer codes is 416628415Speter then traded against the time it takes to make longer tables. 416728415Speter 416828415Speter This results of this trade are in the variables lbits and dbits 416928415Speter below. lbits is the number of bits the first level table for literal/ 417028415Speter length codes can decode in one step, and dbits is the same thing for 417128415Speter the distance codes. Subsequent tables are also less than or equal to 417228415Speter those sizes. These values may be adjusted either when all of the 417328415Speter codes are shorter than that, in which case the longest code length in 417428415Speter bits is used, or when the shortest code is *longer* than the requested 417528415Speter table size, in which case the length of the shortest code in bits is 417628415Speter used. 417728415Speter 417828415Speter There are two different values for the two tables, since they code a 417928415Speter different number of possibilities each. The literal/length table 418028415Speter codes 286 possible values, or in a flat code, a little over eight 418128415Speter bits. The distance table codes 30 possible values, or a little less 418228415Speter than five bits, flat. The optimum values for speed end up being 418328415Speter about one bit more than those, so lbits is 8+1 and dbits is 5+1. 418428415Speter The optimum values may differ though from machine to machine, and 418528415Speter possibly even between compilers. Your mileage may vary. 418628415Speter */ 418728415Speter 418828415Speter 418928415Speter/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ 419028415Speter#define BMAX 15 /* maximum bit length of any code */ 419128415Speter#define N_MAX 288 /* maximum number of codes in any set */ 419228415Speter 419328415Speter#ifdef DEBUG_ZLIB 419428415Speter uInt inflate_hufts; 419528415Speter#endif 419628415Speter 419728415Speterlocal int huft_build(b, n, s, d, e, t, m, zs) 419828415SpeteruIntf *b; /* code lengths in bits (all assumed <= BMAX) */ 419928415SpeteruInt n; /* number of codes (assumed <= N_MAX) */ 420028415SpeteruInt s; /* number of simple-valued codes (0..s-1) */ 420134768Speterconst uIntf *d; /* list of base values for non-simple codes */ 420234768Speterconst uIntf *e; /* list of extra bits for non-simple codes */ 420328415Speterinflate_huft * FAR *t; /* result: starting table */ 420428415SpeteruIntf *m; /* maximum lookup bits, returns actual */ 420534768Speterz_streamp zs; /* for zalloc function */ 420628415Speter/* Given a list of code lengths and a maximum table size, make a set of 420728415Speter tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR 420828415Speter if the given code set is incomplete (the tables are still built in this 420934768Speter case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of 421034768Speter lengths), or Z_MEM_ERROR if not enough memory. */ 421128415Speter{ 421228415Speter 421328415Speter uInt a; /* counter for codes of length k */ 421428415Speter uInt c[BMAX+1]; /* bit length count table */ 421528415Speter uInt f; /* i repeats in table every f entries */ 421628415Speter int g; /* maximum code length */ 421728415Speter int h; /* table level */ 421828415Speter register uInt i; /* counter, current code */ 421928415Speter register uInt j; /* counter */ 422028415Speter register int k; /* number of bits in current code */ 422128415Speter int l; /* bits per table (returned in m) */ 422228415Speter register uIntf *p; /* pointer into c[], b[], or v[] */ 422328415Speter inflate_huft *q; /* points to current table */ 422428415Speter struct inflate_huft_s r; /* table entry for structure assignment */ 422528415Speter inflate_huft *u[BMAX]; /* table stack */ 422628415Speter uInt v[N_MAX]; /* values in order of bit length */ 422728415Speter register int w; /* bits before this table == (l * h) */ 422828415Speter uInt x[BMAX+1]; /* bit offsets, then code stack */ 422928415Speter uIntf *xp; /* pointer into x */ 423028415Speter int y; /* number of dummy codes added */ 423128415Speter uInt z; /* number of entries in current table */ 423228415Speter 423328415Speter 423428415Speter /* Generate counts for each bit length */ 423528415Speter p = c; 423628415Speter#define C0 *p++ = 0; 423728415Speter#define C2 C0 C0 C0 C0 423828415Speter#define C4 C2 C2 C2 C2 423928415Speter C4 /* clear c[]--assume BMAX+1 is 16 */ 424028415Speter p = b; i = n; 424128415Speter do { 424228415Speter c[*p++]++; /* assume all entries <= BMAX */ 424328415Speter } while (--i); 424428415Speter if (c[0] == n) /* null input--all zero length codes */ 424528415Speter { 424628415Speter *t = (inflate_huft *)Z_NULL; 424728415Speter *m = 0; 424828415Speter return Z_OK; 424928415Speter } 425028415Speter 425128415Speter 425228415Speter /* Find minimum and maximum length, bound *m by those */ 425328415Speter l = *m; 425428415Speter for (j = 1; j <= BMAX; j++) 425528415Speter if (c[j]) 425628415Speter break; 425728415Speter k = j; /* minimum code length */ 425828415Speter if ((uInt)l < j) 425928415Speter l = j; 426028415Speter for (i = BMAX; i; i--) 426128415Speter if (c[i]) 426228415Speter break; 426328415Speter g = i; /* maximum code length */ 426428415Speter if ((uInt)l > i) 426528415Speter l = i; 426628415Speter *m = l; 426728415Speter 426828415Speter 426928415Speter /* Adjust last length count to fill out codes, if needed */ 427028415Speter for (y = 1 << j; j < i; j++, y <<= 1) 427128415Speter if ((y -= c[j]) < 0) 427228415Speter return Z_DATA_ERROR; 427328415Speter if ((y -= c[i]) < 0) 427428415Speter return Z_DATA_ERROR; 427528415Speter c[i] += y; 427628415Speter 427728415Speter 427828415Speter /* Generate starting offsets into the value table for each length */ 427928415Speter x[1] = j = 0; 428028415Speter p = c + 1; xp = x + 2; 428128415Speter while (--i) { /* note that i == g from above */ 428228415Speter *xp++ = (j += *p++); 428328415Speter } 428428415Speter 428528415Speter 428628415Speter /* Make a table of values in order of bit lengths */ 428728415Speter p = b; i = 0; 428828415Speter do { 428928415Speter if ((j = *p++) != 0) 429028415Speter v[x[j]++] = i; 429128415Speter } while (++i < n); 429234768Speter n = x[g]; /* set n to length of v */ 429328415Speter 429428415Speter 429528415Speter /* Generate the Huffman codes and for each, make the table entries */ 429628415Speter x[0] = i = 0; /* first Huffman code is zero */ 429728415Speter p = v; /* grab values in bit order */ 429828415Speter h = -1; /* no tables yet--level -1 */ 429928415Speter w = -l; /* bits decoded == (l * h) */ 430028415Speter u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ 430128415Speter q = (inflate_huft *)Z_NULL; /* ditto */ 430228415Speter z = 0; /* ditto */ 430328415Speter 430428415Speter /* go through the bit lengths (k already is bits in shortest code) */ 430528415Speter for (; k <= g; k++) 430628415Speter { 430728415Speter a = c[k]; 430828415Speter while (a--) 430928415Speter { 431028415Speter /* here i is the Huffman code of length k bits for value *p */ 431128415Speter /* make tables up to required level */ 431228415Speter while (k > w + l) 431328415Speter { 431428415Speter h++; 431528415Speter w += l; /* previous table always l bits */ 431628415Speter 431728415Speter /* compute minimum size table less than or equal to l bits */ 431834768Speter z = g - w; 431934768Speter z = z > (uInt)l ? l : z; /* table size upper limit */ 432028415Speter if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 432128415Speter { /* too few codes for k-w bit table */ 432228415Speter f -= a + 1; /* deduct codes from patterns left */ 432328415Speter xp = c + k; 432428415Speter if (j < z) 432528415Speter while (++j < z) /* try smaller tables up to z bits */ 432628415Speter { 432728415Speter if ((f <<= 1) <= *++xp) 432828415Speter break; /* enough codes to use up j bits */ 432928415Speter f -= *xp; /* else deduct codes from patterns */ 433028415Speter } 433128415Speter } 433228415Speter z = 1 << j; /* table entries for j-bit table */ 433328415Speter 433428415Speter /* allocate and link in new table */ 433528415Speter if ((q = (inflate_huft *)ZALLOC 433628415Speter (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) 433728415Speter { 433828415Speter if (h) 433928415Speter inflate_trees_free(u[0], zs); 434028415Speter return Z_MEM_ERROR; /* not enough memory */ 434128415Speter } 434228415Speter#ifdef DEBUG_ZLIB 434328415Speter inflate_hufts += z + 1; 434428415Speter#endif 434528415Speter *t = q + 1; /* link to list for huft_free() */ 434628415Speter *(t = &(q->next)) = Z_NULL; 434728415Speter u[h] = ++q; /* table starts after link */ 434828415Speter 434928415Speter /* connect to last table, if there is one */ 435028415Speter if (h) 435128415Speter { 435228415Speter x[h] = i; /* save pattern for backing up */ 435328415Speter r.bits = (Byte)l; /* bits to dump before this table */ 435428415Speter r.exop = (Byte)j; /* bits in this table */ 435528415Speter r.next = q; /* pointer to this table */ 435628415Speter j = i >> (w - l); /* (get around Turbo C bug) */ 435728415Speter u[h-1][j] = r; /* connect to last table */ 435828415Speter } 435928415Speter } 436028415Speter 436128415Speter /* set up table entry in r */ 436228415Speter r.bits = (Byte)(k - w); 436328415Speter if (p >= v + n) 436428415Speter r.exop = 128 + 64; /* out of values--invalid code */ 436528415Speter else if (*p < s) 436628415Speter { 436728415Speter r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ 436828415Speter r.base = *p++; /* simple code is just the value */ 436928415Speter } 437028415Speter else 437128415Speter { 437234768Speter r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */ 437328415Speter r.base = d[*p++ - s]; 437428415Speter } 437528415Speter 437628415Speter /* fill code-like entries with r */ 437728415Speter f = 1 << (k - w); 437828415Speter for (j = i >> w; j < z; j += f) 437928415Speter q[j] = r; 438028415Speter 438128415Speter /* backwards increment the k-bit code i */ 438228415Speter for (j = 1 << (k - 1); i & j; j >>= 1) 438328415Speter i ^= j; 438428415Speter i ^= j; 438528415Speter 438628415Speter /* backup over finished tables */ 438728415Speter while ((i & ((1 << w) - 1)) != x[h]) 438828415Speter { 438928415Speter h--; /* don't need to update q */ 439028415Speter w -= l; 439128415Speter } 439228415Speter } 439328415Speter } 439428415Speter 439528415Speter 439628415Speter /* Return Z_BUF_ERROR if we were given an incomplete table */ 439728415Speter return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; 439828415Speter} 439928415Speter 440028415Speter 440134768Speterint inflate_trees_bits(c, bb, tb, z) 440228415SpeteruIntf *c; /* 19 code lengths */ 440328415SpeteruIntf *bb; /* bits tree desired/actual depth */ 440428415Speterinflate_huft * FAR *tb; /* bits tree result */ 440534768Speterz_streamp z; /* for zfree function */ 440628415Speter{ 440728415Speter int r; 440828415Speter 440928415Speter r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z); 441028415Speter if (r == Z_DATA_ERROR) 441134768Speter z->msg = (char*)"oversubscribed dynamic bit lengths tree"; 441234768Speter else if (r == Z_BUF_ERROR || *bb == 0) 441328415Speter { 441428415Speter inflate_trees_free(*tb, z); 441534768Speter z->msg = (char*)"incomplete dynamic bit lengths tree"; 441628415Speter r = Z_DATA_ERROR; 441728415Speter } 441828415Speter return r; 441928415Speter} 442028415Speter 442128415Speter 442234768Speterint inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z) 442328415SpeteruInt nl; /* number of literal/length codes */ 442428415SpeteruInt nd; /* number of distance codes */ 442528415SpeteruIntf *c; /* that many (total) code lengths */ 442628415SpeteruIntf *bl; /* literal desired/actual bit depth */ 442728415SpeteruIntf *bd; /* distance desired/actual bit depth */ 442828415Speterinflate_huft * FAR *tl; /* literal/length tree result */ 442928415Speterinflate_huft * FAR *td; /* distance tree result */ 443034768Speterz_streamp z; /* for zfree function */ 443128415Speter{ 443228415Speter int r; 443328415Speter 443428415Speter /* build literal/length tree */ 443534768Speter r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z); 443634768Speter if (r != Z_OK || *bl == 0) 443728415Speter { 443828415Speter if (r == Z_DATA_ERROR) 443934768Speter z->msg = (char*)"oversubscribed literal/length tree"; 444034768Speter else if (r != Z_MEM_ERROR) 444128415Speter { 444228415Speter inflate_trees_free(*tl, z); 444334768Speter z->msg = (char*)"incomplete literal/length tree"; 444428415Speter r = Z_DATA_ERROR; 444528415Speter } 444628415Speter return r; 444728415Speter } 444828415Speter 444928415Speter /* build distance tree */ 445034768Speter r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z); 445134768Speter if (r != Z_OK || (*bd == 0 && nl > 257)) 445228415Speter { 445328415Speter if (r == Z_DATA_ERROR) 445434768Speter z->msg = (char*)"oversubscribed distance tree"; 445528415Speter else if (r == Z_BUF_ERROR) { 445628415Speter#ifdef PKZIP_BUG_WORKAROUND 445728415Speter r = Z_OK; 445828415Speter } 445928415Speter#else 446028415Speter inflate_trees_free(*td, z); 446134768Speter z->msg = (char*)"incomplete distance tree"; 446228415Speter r = Z_DATA_ERROR; 446328415Speter } 446434768Speter else if (r != Z_MEM_ERROR) 446534768Speter { 446634768Speter z->msg = (char*)"empty distance tree with lengths"; 446734768Speter r = Z_DATA_ERROR; 446834768Speter } 446928415Speter inflate_trees_free(*tl, z); 447028415Speter return r; 447128415Speter#endif 447228415Speter } 447328415Speter 447428415Speter /* done */ 447528415Speter return Z_OK; 447628415Speter} 447728415Speter 447828415Speter 447928415Speter/* build fixed tables only once--keep them here */ 448028415Speterlocal int fixed_built = 0; 448128415Speter#define FIXEDH 530 /* number of hufts used by fixed tables */ 448228415Speterlocal inflate_huft fixed_mem[FIXEDH]; 448328415Speterlocal uInt fixed_bl; 448428415Speterlocal uInt fixed_bd; 448528415Speterlocal inflate_huft *fixed_tl; 448628415Speterlocal inflate_huft *fixed_td; 448728415Speter 448828415Speter 448928415Speterlocal voidpf falloc(q, n, s) 449034768Spetervoidpf q; /* opaque pointer */ 449128415SpeteruInt n; /* number of items */ 449228415SpeteruInt s; /* size of item */ 449328415Speter{ 449434768Speter Assert(s == sizeof(inflate_huft) && n <= *(intf *)q, 449528415Speter "inflate_trees falloc overflow"); 449634768Speter *(intf *)q -= n+s-s; /* s-s to avoid warning */ 449734768Speter return (voidpf)(fixed_mem + *(intf *)q); 449828415Speter} 449928415Speter 450028415Speter 450134768Speterint inflate_trees_fixed(bl, bd, tl, td) 450228415SpeteruIntf *bl; /* literal desired/actual bit depth */ 450328415SpeteruIntf *bd; /* distance desired/actual bit depth */ 450428415Speterinflate_huft * FAR *tl; /* literal/length tree result */ 450528415Speterinflate_huft * FAR *td; /* distance tree result */ 450628415Speter{ 450734768Speter /* build fixed tables if not already (multiple overlapped executions ok) */ 450828415Speter if (!fixed_built) 450928415Speter { 451028415Speter int k; /* temporary variable */ 451128415Speter unsigned c[288]; /* length list for huft_build */ 451228415Speter z_stream z; /* for falloc function */ 451334768Speter int f = FIXEDH; /* number of hufts left in fixed_mem */ 451428415Speter 451528415Speter /* set up fake z_stream for memory routines */ 451628415Speter z.zalloc = falloc; 451734768Speter z.zfree = Z_NULL; 451834768Speter z.opaque = (voidpf)&f; 451928415Speter 452028415Speter /* literal table */ 452128415Speter for (k = 0; k < 144; k++) 452228415Speter c[k] = 8; 452328415Speter for (; k < 256; k++) 452428415Speter c[k] = 9; 452528415Speter for (; k < 280; k++) 452628415Speter c[k] = 7; 452728415Speter for (; k < 288; k++) 452828415Speter c[k] = 8; 452928415Speter fixed_bl = 7; 453028415Speter huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z); 453128415Speter 453228415Speter /* distance table */ 453328415Speter for (k = 0; k < 30; k++) 453428415Speter c[k] = 5; 453528415Speter fixed_bd = 5; 453628415Speter huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z); 453728415Speter 453828415Speter /* done */ 453934768Speter Assert(f == 0, "invalid build of fixed tables"); 454028415Speter fixed_built = 1; 454128415Speter } 454228415Speter *bl = fixed_bl; 454328415Speter *bd = fixed_bd; 454428415Speter *tl = fixed_tl; 454528415Speter *td = fixed_td; 454628415Speter return Z_OK; 454728415Speter} 454828415Speter 454928415Speter 455034768Speterint inflate_trees_free(t, z) 455128415Speterinflate_huft *t; /* table to free */ 455234768Speterz_streamp z; /* for zfree function */ 455328415Speter/* Free the malloc'ed tables built by huft_build(), which makes a linked 455428415Speter list of the tables it made, with the links in a dummy first entry of 455528415Speter each table. */ 455628415Speter{ 455734768Speter register inflate_huft *p, *q, *r; 455828415Speter 455934768Speter /* Reverse linked list */ 456034768Speter p = Z_NULL; 456134768Speter q = t; 456234768Speter while (q != Z_NULL) 456334768Speter { 456434768Speter r = (q - 1)->next; 456534768Speter (q - 1)->next = p; 456634768Speter p = q; 456734768Speter q = r; 456834768Speter } 456928415Speter /* Go through linked list, freeing from the malloced (t[-1]) address. */ 457028415Speter while (p != Z_NULL) 457128415Speter { 457228415Speter q = (--p)->next; 457334768Speter ZFREE(z,p); 457428415Speter p = q; 457528415Speter } 457628415Speter return Z_OK; 457728415Speter} 457834768Speter/* --- inftrees.c */ 457928415Speter 458034768Speter/* +++ infcodes.c */ 458128415Speter/* infcodes.c -- process literals and length/distance pairs 458234768Speter * Copyright (C) 1995-1996 Mark Adler 458328415Speter * For conditions of distribution and use, see copyright notice in zlib.h 458428415Speter */ 458528415Speter 458634768Speter/* #include "zutil.h" */ 458734768Speter/* #include "inftrees.h" */ 458834768Speter/* #include "infblock.h" */ 458934768Speter/* #include "infcodes.h" */ 459034768Speter/* #include "infutil.h" */ 459134768Speter 459234768Speter/* +++ inffast.h */ 459334768Speter/* inffast.h -- header to use inffast.c 459434768Speter * Copyright (C) 1995-1996 Mark Adler 459534768Speter * For conditions of distribution and use, see copyright notice in zlib.h 459634768Speter */ 459734768Speter 459834768Speter/* WARNING: this file should *not* be used by applications. It is 459934768Speter part of the implementation of the compression library and is 460034768Speter subject to change. Applications should only use zlib.h. 460134768Speter */ 460234768Speter 460334768Speterextern int inflate_fast OF(( 460434768Speter uInt, 460534768Speter uInt, 460634768Speter inflate_huft *, 460734768Speter inflate_huft *, 460834768Speter inflate_blocks_statef *, 460934768Speter z_streamp )); 461034768Speter/* --- inffast.h */ 461134768Speter 461228415Speter/* simplify the use of the inflate_huft type with some defines */ 461328415Speter#define base more.Base 461428415Speter#define next more.Next 461528415Speter#define exop word.what.Exop 461628415Speter#define bits word.what.Bits 461728415Speter 461828415Speter/* inflate codes private state */ 461928415Speterstruct inflate_codes_state { 462028415Speter 462128415Speter /* mode */ 462228415Speter enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 462328415Speter START, /* x: set up for LEN */ 462428415Speter LEN, /* i: get length/literal/eob next */ 462528415Speter LENEXT, /* i: getting length extra (have base) */ 462628415Speter DIST, /* i: get distance next */ 462728415Speter DISTEXT, /* i: getting distance extra */ 462828415Speter COPY, /* o: copying bytes in window, waiting for space */ 462928415Speter LIT, /* o: got literal, waiting for output space */ 463028415Speter WASH, /* o: got eob, possibly still output waiting */ 463128415Speter END, /* x: got eob and all data flushed */ 463228415Speter BADCODE} /* x: got error */ 463328415Speter mode; /* current inflate_codes mode */ 463428415Speter 463528415Speter /* mode dependent information */ 463628415Speter uInt len; 463728415Speter union { 463828415Speter struct { 463928415Speter inflate_huft *tree; /* pointer into tree */ 464028415Speter uInt need; /* bits needed */ 464128415Speter } code; /* if LEN or DIST, where in tree */ 464228415Speter uInt lit; /* if LIT, literal */ 464328415Speter struct { 464428415Speter uInt get; /* bits to get for extra */ 464528415Speter uInt dist; /* distance back to copy from */ 464628415Speter } copy; /* if EXT or COPY, where and how much */ 464728415Speter } sub; /* submode */ 464828415Speter 464928415Speter /* mode independent information */ 465028415Speter Byte lbits; /* ltree bits decoded per branch */ 465128415Speter Byte dbits; /* dtree bits decoder per branch */ 465228415Speter inflate_huft *ltree; /* literal/length/eob tree */ 465328415Speter inflate_huft *dtree; /* distance tree */ 465428415Speter 465528415Speter}; 465628415Speter 465728415Speter 465834768Speterinflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z) 465928415SpeteruInt bl, bd; 466034768Speterinflate_huft *tl; 466134768Speterinflate_huft *td; /* need separate declaration for Borland C++ */ 466234768Speterz_streamp z; 466328415Speter{ 466428415Speter inflate_codes_statef *c; 466528415Speter 466628415Speter if ((c = (inflate_codes_statef *) 466728415Speter ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL) 466828415Speter { 466928415Speter c->mode = START; 467028415Speter c->lbits = (Byte)bl; 467128415Speter c->dbits = (Byte)bd; 467228415Speter c->ltree = tl; 467328415Speter c->dtree = td; 467428415Speter Tracev((stderr, "inflate: codes new\n")); 467528415Speter } 467628415Speter return c; 467728415Speter} 467828415Speter 467928415Speter 468034768Speterint inflate_codes(s, z, r) 468128415Speterinflate_blocks_statef *s; 468234768Speterz_streamp z; 468328415Speterint r; 468428415Speter{ 468528415Speter uInt j; /* temporary storage */ 468628415Speter inflate_huft *t; /* temporary pointer */ 468728415Speter uInt e; /* extra bits or operation */ 468828415Speter uLong b; /* bit buffer */ 468928415Speter uInt k; /* bits in bit buffer */ 469028415Speter Bytef *p; /* input data pointer */ 469128415Speter uInt n; /* bytes available there */ 469228415Speter Bytef *q; /* output window write pointer */ 469328415Speter uInt m; /* bytes to end of window or read pointer */ 469428415Speter Bytef *f; /* pointer to copy strings from */ 469528415Speter inflate_codes_statef *c = s->sub.decode.codes; /* codes state */ 469628415Speter 469728415Speter /* copy input/output information to locals (UPDATE macro restores) */ 469828415Speter LOAD 469928415Speter 470028415Speter /* process input and output based on current state */ 470128415Speter while (1) switch (c->mode) 470228415Speter { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 470328415Speter case START: /* x: set up for LEN */ 470428415Speter#ifndef SLOW 470528415Speter if (m >= 258 && n >= 10) 470628415Speter { 470728415Speter UPDATE 470828415Speter r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); 470928415Speter LOAD 471028415Speter if (r != Z_OK) 471128415Speter { 471228415Speter c->mode = r == Z_STREAM_END ? WASH : BADCODE; 471328415Speter break; 471428415Speter } 471528415Speter } 471628415Speter#endif /* !SLOW */ 471728415Speter c->sub.code.need = c->lbits; 471828415Speter c->sub.code.tree = c->ltree; 471928415Speter c->mode = LEN; 472028415Speter case LEN: /* i: get length/literal/eob next */ 472128415Speter j = c->sub.code.need; 472228415Speter NEEDBITS(j) 472328415Speter t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 472428415Speter DUMPBITS(t->bits) 472528415Speter e = (uInt)(t->exop); 472628415Speter if (e == 0) /* literal */ 472728415Speter { 472828415Speter c->sub.lit = t->base; 472928415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 473028415Speter "inflate: literal '%c'\n" : 473128415Speter "inflate: literal 0x%02x\n", t->base)); 473228415Speter c->mode = LIT; 473328415Speter break; 473428415Speter } 473528415Speter if (e & 16) /* length */ 473628415Speter { 473728415Speter c->sub.copy.get = e & 15; 473828415Speter c->len = t->base; 473928415Speter c->mode = LENEXT; 474028415Speter break; 474128415Speter } 474228415Speter if ((e & 64) == 0) /* next table */ 474328415Speter { 474428415Speter c->sub.code.need = e; 474528415Speter c->sub.code.tree = t->next; 474628415Speter break; 474728415Speter } 474828415Speter if (e & 32) /* end of block */ 474928415Speter { 475028415Speter Tracevv((stderr, "inflate: end of block\n")); 475128415Speter c->mode = WASH; 475228415Speter break; 475328415Speter } 475428415Speter c->mode = BADCODE; /* invalid code */ 475534768Speter z->msg = (char*)"invalid literal/length code"; 475628415Speter r = Z_DATA_ERROR; 475728415Speter LEAVE 475828415Speter case LENEXT: /* i: getting length extra (have base) */ 475928415Speter j = c->sub.copy.get; 476028415Speter NEEDBITS(j) 476128415Speter c->len += (uInt)b & inflate_mask[j]; 476228415Speter DUMPBITS(j) 476328415Speter c->sub.code.need = c->dbits; 476428415Speter c->sub.code.tree = c->dtree; 476528415Speter Tracevv((stderr, "inflate: length %u\n", c->len)); 476628415Speter c->mode = DIST; 476728415Speter case DIST: /* i: get distance next */ 476828415Speter j = c->sub.code.need; 476928415Speter NEEDBITS(j) 477028415Speter t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 477128415Speter DUMPBITS(t->bits) 477228415Speter e = (uInt)(t->exop); 477328415Speter if (e & 16) /* distance */ 477428415Speter { 477528415Speter c->sub.copy.get = e & 15; 477628415Speter c->sub.copy.dist = t->base; 477728415Speter c->mode = DISTEXT; 477828415Speter break; 477928415Speter } 478028415Speter if ((e & 64) == 0) /* next table */ 478128415Speter { 478228415Speter c->sub.code.need = e; 478328415Speter c->sub.code.tree = t->next; 478428415Speter break; 478528415Speter } 478628415Speter c->mode = BADCODE; /* invalid code */ 478734768Speter z->msg = (char*)"invalid distance code"; 478828415Speter r = Z_DATA_ERROR; 478928415Speter LEAVE 479028415Speter case DISTEXT: /* i: getting distance extra */ 479128415Speter j = c->sub.copy.get; 479228415Speter NEEDBITS(j) 479328415Speter c->sub.copy.dist += (uInt)b & inflate_mask[j]; 479428415Speter DUMPBITS(j) 479528415Speter Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist)); 479628415Speter c->mode = COPY; 479728415Speter case COPY: /* o: copying bytes in window, waiting for space */ 479828415Speter#ifndef __TURBOC__ /* Turbo C bug for following expression */ 479928415Speter f = (uInt)(q - s->window) < c->sub.copy.dist ? 480028415Speter s->end - (c->sub.copy.dist - (q - s->window)) : 480128415Speter q - c->sub.copy.dist; 480228415Speter#else 480328415Speter f = q - c->sub.copy.dist; 480428415Speter if ((uInt)(q - s->window) < c->sub.copy.dist) 480534768Speter f = s->end - (c->sub.copy.dist - (uInt)(q - s->window)); 480628415Speter#endif 480728415Speter while (c->len) 480828415Speter { 480928415Speter NEEDOUT 481028415Speter OUTBYTE(*f++) 481128415Speter if (f == s->end) 481228415Speter f = s->window; 481328415Speter c->len--; 481428415Speter } 481528415Speter c->mode = START; 481628415Speter break; 481728415Speter case LIT: /* o: got literal, waiting for output space */ 481828415Speter NEEDOUT 481928415Speter OUTBYTE(c->sub.lit) 482028415Speter c->mode = START; 482128415Speter break; 482228415Speter case WASH: /* o: got eob, possibly more output */ 482328415Speter FLUSH 482428415Speter if (s->read != s->write) 482528415Speter LEAVE 482628415Speter c->mode = END; 482728415Speter case END: 482828415Speter r = Z_STREAM_END; 482928415Speter LEAVE 483028415Speter case BADCODE: /* x: got error */ 483128415Speter r = Z_DATA_ERROR; 483228415Speter LEAVE 483328415Speter default: 483428415Speter r = Z_STREAM_ERROR; 483528415Speter LEAVE 483628415Speter } 483728415Speter} 483828415Speter 483928415Speter 484034768Spetervoid inflate_codes_free(c, z) 484128415Speterinflate_codes_statef *c; 484234768Speterz_streamp z; 484328415Speter{ 484434768Speter ZFREE(z, c); 484528415Speter Tracev((stderr, "inflate: codes free\n")); 484628415Speter} 484734768Speter/* --- infcodes.c */ 484828415Speter 484934768Speter/* +++ infutil.c */ 485028415Speter/* inflate_util.c -- data and routines common to blocks and codes 485134768Speter * Copyright (C) 1995-1996 Mark Adler 485228415Speter * For conditions of distribution and use, see copyright notice in zlib.h 485328415Speter */ 485428415Speter 485534768Speter/* #include "zutil.h" */ 485634768Speter/* #include "infblock.h" */ 485734768Speter/* #include "inftrees.h" */ 485834768Speter/* #include "infcodes.h" */ 485934768Speter/* #include "infutil.h" */ 486034768Speter 486134768Speter#ifndef NO_DUMMY_DECL 486234768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 486334768Speter#endif 486434768Speter 486534768Speter/* And'ing with mask[n] masks the lower n bits */ 486634768SpeteruInt inflate_mask[17] = { 486734768Speter 0x0000, 486834768Speter 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 486934768Speter 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 487034768Speter}; 487134768Speter 487234768Speter 487328415Speter/* copy as much as possible from the sliding window to the output area */ 487434768Speterint inflate_flush(s, z, r) 487528415Speterinflate_blocks_statef *s; 487634768Speterz_streamp z; 487728415Speterint r; 487828415Speter{ 487928415Speter uInt n; 488034768Speter Bytef *p; 488134768Speter Bytef *q; 488228415Speter 488328415Speter /* local copies of source and destination pointers */ 488428415Speter p = z->next_out; 488528415Speter q = s->read; 488628415Speter 488728415Speter /* compute number of bytes to copy as far as end of window */ 488828415Speter n = (uInt)((q <= s->write ? s->write : s->end) - q); 488928415Speter if (n > z->avail_out) n = z->avail_out; 489028415Speter if (n && r == Z_BUF_ERROR) r = Z_OK; 489128415Speter 489228415Speter /* update counters */ 489328415Speter z->avail_out -= n; 489428415Speter z->total_out += n; 489528415Speter 489628415Speter /* update check information */ 489728415Speter if (s->checkfn != Z_NULL) 489834768Speter z->adler = s->check = (*s->checkfn)(s->check, q, n); 489928415Speter 490028415Speter /* copy as far as end of window */ 490134768Speter if (p != Z_NULL) { 490228415Speter zmemcpy(p, q, n); 490328415Speter p += n; 490428415Speter } 490528415Speter q += n; 490628415Speter 490728415Speter /* see if more to copy at beginning of window */ 490828415Speter if (q == s->end) 490928415Speter { 491028415Speter /* wrap pointers */ 491128415Speter q = s->window; 491228415Speter if (s->write == s->end) 491328415Speter s->write = s->window; 491428415Speter 491528415Speter /* compute bytes to copy */ 491628415Speter n = (uInt)(s->write - q); 491728415Speter if (n > z->avail_out) n = z->avail_out; 491828415Speter if (n && r == Z_BUF_ERROR) r = Z_OK; 491928415Speter 492028415Speter /* update counters */ 492128415Speter z->avail_out -= n; 492228415Speter z->total_out += n; 492328415Speter 492428415Speter /* update check information */ 492528415Speter if (s->checkfn != Z_NULL) 492634768Speter z->adler = s->check = (*s->checkfn)(s->check, q, n); 492728415Speter 492828415Speter /* copy */ 492934768Speter if (p != Z_NULL) { 493028415Speter zmemcpy(p, q, n); 493128415Speter p += n; 493228415Speter } 493328415Speter q += n; 493428415Speter } 493528415Speter 493628415Speter /* update pointers */ 493728415Speter z->next_out = p; 493828415Speter s->read = q; 493928415Speter 494028415Speter /* done */ 494128415Speter return r; 494228415Speter} 494334768Speter/* --- infutil.c */ 494428415Speter 494534768Speter/* +++ inffast.c */ 494628415Speter/* inffast.c -- process literals and length/distance pairs fast 494734768Speter * Copyright (C) 1995-1996 Mark Adler 494828415Speter * For conditions of distribution and use, see copyright notice in zlib.h 494928415Speter */ 495028415Speter 495134768Speter/* #include "zutil.h" */ 495234768Speter/* #include "inftrees.h" */ 495334768Speter/* #include "infblock.h" */ 495434768Speter/* #include "infcodes.h" */ 495534768Speter/* #include "infutil.h" */ 495634768Speter/* #include "inffast.h" */ 495734768Speter 495834768Speter#ifndef NO_DUMMY_DECL 495934768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 496034768Speter#endif 496134768Speter 496228415Speter/* simplify the use of the inflate_huft type with some defines */ 496328415Speter#define base more.Base 496428415Speter#define next more.Next 496528415Speter#define exop word.what.Exop 496628415Speter#define bits word.what.Bits 496728415Speter 496828415Speter/* macros for bit input with no checking and for returning unused bytes */ 496928415Speter#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} 497028415Speter#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;} 497128415Speter 497228415Speter/* Called with number of bytes left to write in window at least 258 497328415Speter (the maximum string length) and number of input bytes available 497428415Speter at least ten. The ten bytes are six bytes for the longest length/ 497528415Speter distance pair plus four bytes for overloading the bit buffer. */ 497628415Speter 497734768Speterint inflate_fast(bl, bd, tl, td, s, z) 497828415SpeteruInt bl, bd; 497934768Speterinflate_huft *tl; 498034768Speterinflate_huft *td; /* need separate declaration for Borland C++ */ 498128415Speterinflate_blocks_statef *s; 498234768Speterz_streamp z; 498328415Speter{ 498428415Speter inflate_huft *t; /* temporary pointer */ 498528415Speter uInt e; /* extra bits or operation */ 498628415Speter uLong b; /* bit buffer */ 498728415Speter uInt k; /* bits in bit buffer */ 498828415Speter Bytef *p; /* input data pointer */ 498928415Speter uInt n; /* bytes available there */ 499028415Speter Bytef *q; /* output window write pointer */ 499128415Speter uInt m; /* bytes to end of window or read pointer */ 499228415Speter uInt ml; /* mask for literal/length tree */ 499328415Speter uInt md; /* mask for distance tree */ 499428415Speter uInt c; /* bytes to copy */ 499528415Speter uInt d; /* distance back to copy from */ 499628415Speter Bytef *r; /* copy source pointer */ 499728415Speter 499828415Speter /* load input, output, bit values */ 499928415Speter LOAD 500028415Speter 500128415Speter /* initialize masks */ 500228415Speter ml = inflate_mask[bl]; 500328415Speter md = inflate_mask[bd]; 500428415Speter 500528415Speter /* do until not enough input or output space for fast loop */ 500628415Speter do { /* assume called with m >= 258 && n >= 10 */ 500728415Speter /* get literal/length code */ 500828415Speter GRABBITS(20) /* max bits for literal/length code */ 500928415Speter if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) 501028415Speter { 501128415Speter DUMPBITS(t->bits) 501228415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 501328415Speter "inflate: * literal '%c'\n" : 501428415Speter "inflate: * literal 0x%02x\n", t->base)); 501528415Speter *q++ = (Byte)t->base; 501628415Speter m--; 501728415Speter continue; 501828415Speter } 501928415Speter do { 502028415Speter DUMPBITS(t->bits) 502128415Speter if (e & 16) 502228415Speter { 502328415Speter /* get extra bits for length */ 502428415Speter e &= 15; 502528415Speter c = t->base + ((uInt)b & inflate_mask[e]); 502628415Speter DUMPBITS(e) 502728415Speter Tracevv((stderr, "inflate: * length %u\n", c)); 502828415Speter 502928415Speter /* decode distance base of block to copy */ 503028415Speter GRABBITS(15); /* max bits for distance code */ 503128415Speter e = (t = td + ((uInt)b & md))->exop; 503228415Speter do { 503328415Speter DUMPBITS(t->bits) 503428415Speter if (e & 16) 503528415Speter { 503628415Speter /* get extra bits to add to distance base */ 503728415Speter e &= 15; 503828415Speter GRABBITS(e) /* get extra bits (up to 13) */ 503928415Speter d = t->base + ((uInt)b & inflate_mask[e]); 504028415Speter DUMPBITS(e) 504128415Speter Tracevv((stderr, "inflate: * distance %u\n", d)); 504228415Speter 504328415Speter /* do the copy */ 504428415Speter m -= c; 504528415Speter if ((uInt)(q - s->window) >= d) /* offset before dest */ 504628415Speter { /* just copy */ 504728415Speter r = q - d; 504828415Speter *q++ = *r++; c--; /* minimum count is three, */ 504928415Speter *q++ = *r++; c--; /* so unroll loop a little */ 505028415Speter } 505128415Speter else /* else offset after destination */ 505228415Speter { 505334768Speter e = d - (uInt)(q - s->window); /* bytes from offset to end */ 505428415Speter r = s->end - e; /* pointer to offset */ 505528415Speter if (c > e) /* if source crosses, */ 505628415Speter { 505728415Speter c -= e; /* copy to end of window */ 505828415Speter do { 505928415Speter *q++ = *r++; 506028415Speter } while (--e); 506128415Speter r = s->window; /* copy rest from start of window */ 506228415Speter } 506328415Speter } 506428415Speter do { /* copy all or what's left */ 506528415Speter *q++ = *r++; 506628415Speter } while (--c); 506728415Speter break; 506828415Speter } 506928415Speter else if ((e & 64) == 0) 507028415Speter e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop; 507128415Speter else 507228415Speter { 507334768Speter z->msg = (char*)"invalid distance code"; 507428415Speter UNGRAB 507528415Speter UPDATE 507628415Speter return Z_DATA_ERROR; 507728415Speter } 507828415Speter } while (1); 507928415Speter break; 508028415Speter } 508128415Speter if ((e & 64) == 0) 508228415Speter { 508328415Speter if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0) 508428415Speter { 508528415Speter DUMPBITS(t->bits) 508628415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 508728415Speter "inflate: * literal '%c'\n" : 508828415Speter "inflate: * literal 0x%02x\n", t->base)); 508928415Speter *q++ = (Byte)t->base; 509028415Speter m--; 509128415Speter break; 509228415Speter } 509328415Speter } 509428415Speter else if (e & 32) 509528415Speter { 509628415Speter Tracevv((stderr, "inflate: * end of block\n")); 509728415Speter UNGRAB 509828415Speter UPDATE 509928415Speter return Z_STREAM_END; 510028415Speter } 510128415Speter else 510228415Speter { 510334768Speter z->msg = (char*)"invalid literal/length code"; 510428415Speter UNGRAB 510528415Speter UPDATE 510628415Speter return Z_DATA_ERROR; 510728415Speter } 510828415Speter } while (1); 510928415Speter } while (m >= 258 && n >= 10); 511028415Speter 511128415Speter /* not enough input or output--restore pointers and return */ 511228415Speter UNGRAB 511328415Speter UPDATE 511428415Speter return Z_OK; 511528415Speter} 511634768Speter/* --- inffast.c */ 511728415Speter 511834768Speter/* +++ zutil.c */ 511928415Speter/* zutil.c -- target dependent utility functions for the compression library 512034768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 512128415Speter * For conditions of distribution and use, see copyright notice in zlib.h 512228415Speter */ 512328415Speter 512434768Speter/* From: zutil.c,v 1.17 1996/07/24 13:41:12 me Exp $ */ 512528415Speter 512634768Speter#ifdef DEBUG_ZLIB 512734768Speter#include <stdio.h> 512834768Speter#endif 512928415Speter 513034768Speter/* #include "zutil.h" */ 513134768Speter 513234768Speter#ifndef NO_DUMMY_DECL 513334768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 513434768Speter#endif 513534768Speter 513634768Speter#ifndef STDC 513734768Speterextern void exit OF((int)); 513834768Speter#endif 513934768Speter 514034768Speterstatic const char *z_errmsg[10] = { 514134768Speter"need dictionary", /* Z_NEED_DICT 2 */ 514234768Speter"stream end", /* Z_STREAM_END 1 */ 514334768Speter"", /* Z_OK 0 */ 514434768Speter"file error", /* Z_ERRNO (-1) */ 514534768Speter"stream error", /* Z_STREAM_ERROR (-2) */ 514634768Speter"data error", /* Z_DATA_ERROR (-3) */ 514734768Speter"insufficient memory", /* Z_MEM_ERROR (-4) */ 514834768Speter"buffer error", /* Z_BUF_ERROR (-5) */ 514934768Speter"incompatible version",/* Z_VERSION_ERROR (-6) */ 515028415Speter""}; 515128415Speter 515228415Speter 515334768Speterconst char *zlibVersion() 515434768Speter{ 515534768Speter return ZLIB_VERSION; 515634768Speter} 515734768Speter 515834768Speter#ifdef DEBUG_ZLIB 515934768Spetervoid z_error (m) 516034768Speter char *m; 516134768Speter{ 516234768Speter fprintf(stderr, "%s\n", m); 516334768Speter exit(1); 516434768Speter} 516534768Speter#endif 516634768Speter 516734768Speter#ifndef HAVE_MEMCPY 516834768Speter 516934768Spetervoid zmemcpy(dest, source, len) 517034768Speter Bytef* dest; 517134768Speter Bytef* source; 517234768Speter uInt len; 517334768Speter{ 517434768Speter if (len == 0) return; 517534768Speter do { 517634768Speter *dest++ = *source++; /* ??? to be unrolled */ 517734768Speter } while (--len != 0); 517834768Speter} 517934768Speter 518034768Speterint zmemcmp(s1, s2, len) 518134768Speter Bytef* s1; 518234768Speter Bytef* s2; 518334768Speter uInt len; 518434768Speter{ 518534768Speter uInt j; 518634768Speter 518734768Speter for (j = 0; j < len; j++) { 518834768Speter if (s1[j] != s2[j]) return 2*(s1[j] > s2[j])-1; 518934768Speter } 519034768Speter return 0; 519134768Speter} 519234768Speter 519334768Spetervoid zmemzero(dest, len) 519434768Speter Bytef* dest; 519534768Speter uInt len; 519634768Speter{ 519734768Speter if (len == 0) return; 519834768Speter do { 519934768Speter *dest++ = 0; /* ??? to be unrolled */ 520034768Speter } while (--len != 0); 520134768Speter} 520234768Speter#endif 520334768Speter 520434768Speter#ifdef __TURBOC__ 520534768Speter#if (defined( __BORLANDC__) || !defined(SMALL_MEDIUM)) && !defined(__32BIT__) 520634768Speter/* Small and medium model in Turbo C are for now limited to near allocation 520734768Speter * with reduced MAX_WBITS and MAX_MEM_LEVEL 520834768Speter */ 520934768Speter# define MY_ZCALLOC 521034768Speter 521134768Speter/* Turbo C malloc() does not allow dynamic allocation of 64K bytes 521234768Speter * and farmalloc(64K) returns a pointer with an offset of 8, so we 521334768Speter * must fix the pointer. Warning: the pointer must be put back to its 521434768Speter * original form in order to free it, use zcfree(). 521534768Speter */ 521634768Speter 521734768Speter#define MAX_PTR 10 521834768Speter/* 10*64K = 640K */ 521934768Speter 522034768Speterlocal int next_ptr = 0; 522134768Speter 522234768Spetertypedef struct ptr_table_s { 522334768Speter voidpf org_ptr; 522434768Speter voidpf new_ptr; 522534768Speter} ptr_table; 522634768Speter 522734768Speterlocal ptr_table table[MAX_PTR]; 522834768Speter/* This table is used to remember the original form of pointers 522934768Speter * to large buffers (64K). Such pointers are normalized with a zero offset. 523034768Speter * Since MSDOS is not a preemptive multitasking OS, this table is not 523134768Speter * protected from concurrent access. This hack doesn't work anyway on 523234768Speter * a protected system like OS/2. Use Microsoft C instead. 523334768Speter */ 523434768Speter 523534768Spetervoidpf zcalloc (voidpf opaque, unsigned items, unsigned size) 523634768Speter{ 523734768Speter voidpf buf = opaque; /* just to make some compilers happy */ 523834768Speter ulg bsize = (ulg)items*size; 523934768Speter 524034768Speter /* If we allocate less than 65520 bytes, we assume that farmalloc 524134768Speter * will return a usable pointer which doesn't have to be normalized. 524234768Speter */ 524334768Speter if (bsize < 65520L) { 524434768Speter buf = farmalloc(bsize); 524534768Speter if (*(ush*)&buf != 0) return buf; 524634768Speter } else { 524734768Speter buf = farmalloc(bsize + 16L); 524834768Speter } 524934768Speter if (buf == NULL || next_ptr >= MAX_PTR) return NULL; 525034768Speter table[next_ptr].org_ptr = buf; 525134768Speter 525234768Speter /* Normalize the pointer to seg:0 */ 525334768Speter *((ush*)&buf+1) += ((ush)((uch*)buf-0) + 15) >> 4; 525434768Speter *(ush*)&buf = 0; 525534768Speter table[next_ptr++].new_ptr = buf; 525634768Speter return buf; 525734768Speter} 525834768Speter 525934768Spetervoid zcfree (voidpf opaque, voidpf ptr) 526034768Speter{ 526134768Speter int n; 526234768Speter if (*(ush*)&ptr != 0) { /* object < 64K */ 526334768Speter farfree(ptr); 526434768Speter return; 526534768Speter } 526634768Speter /* Find the original pointer */ 526734768Speter for (n = 0; n < next_ptr; n++) { 526834768Speter if (ptr != table[n].new_ptr) continue; 526934768Speter 527034768Speter farfree(table[n].org_ptr); 527134768Speter while (++n < next_ptr) { 527234768Speter table[n-1] = table[n]; 527334768Speter } 527434768Speter next_ptr--; 527534768Speter return; 527634768Speter } 527734768Speter ptr = opaque; /* just to make some compilers happy */ 527834768Speter Assert(0, "zcfree: ptr not found"); 527934768Speter} 528034768Speter#endif 528134768Speter#endif /* __TURBOC__ */ 528234768Speter 528334768Speter 528434768Speter#if defined(M_I86) && !defined(__32BIT__) 528534768Speter/* Microsoft C in 16-bit mode */ 528634768Speter 528734768Speter# define MY_ZCALLOC 528834768Speter 528934768Speter#if (!defined(_MSC_VER) || (_MSC_VER < 600)) 529034768Speter# define _halloc halloc 529134768Speter# define _hfree hfree 529234768Speter#endif 529334768Speter 529434768Spetervoidpf zcalloc (voidpf opaque, unsigned items, unsigned size) 529534768Speter{ 529634768Speter if (opaque) opaque = 0; /* to make compiler happy */ 529734768Speter return _halloc((long)items, size); 529834768Speter} 529934768Speter 530034768Spetervoid zcfree (voidpf opaque, voidpf ptr) 530134768Speter{ 530234768Speter if (opaque) opaque = 0; /* to make compiler happy */ 530334768Speter _hfree(ptr); 530434768Speter} 530534768Speter 530634768Speter#endif /* MSC */ 530734768Speter 530834768Speter 530934768Speter#ifndef MY_ZCALLOC /* Any system without a special alloc function */ 531034768Speter 531134768Speter#ifndef STDC 531234768Speterextern voidp calloc OF((uInt items, uInt size)); 531334768Speterextern void free OF((voidpf ptr)); 531434768Speter#endif 531534768Speter 531634768Spetervoidpf zcalloc (opaque, items, size) 531734768Speter voidpf opaque; 531834768Speter unsigned items; 531934768Speter unsigned size; 532034768Speter{ 532134768Speter if (opaque) items += size - size; /* make compiler happy */ 532234768Speter return (voidpf)calloc(items, size); 532334768Speter} 532434768Speter 532534768Spetervoid zcfree (opaque, ptr) 532634768Speter voidpf opaque; 532734768Speter voidpf ptr; 532834768Speter{ 532934768Speter free(ptr); 533034768Speter if (opaque) return; /* make compiler happy */ 533134768Speter} 533234768Speter 533334768Speter#endif /* MY_ZCALLOC */ 533434768Speter/* --- zutil.c */ 533534768Speter 533634768Speter/* +++ adler32.c */ 533728415Speter/* adler32.c -- compute the Adler-32 checksum of a data stream 533834768Speter * Copyright (C) 1995-1996 Mark Adler 533928415Speter * For conditions of distribution and use, see copyright notice in zlib.h 534028415Speter */ 534128415Speter 534234768Speter/* From: adler32.c,v 1.10 1996/05/22 11:52:18 me Exp $ */ 534328415Speter 534434768Speter/* #include "zlib.h" */ 534534768Speter 534628415Speter#define BASE 65521L /* largest prime smaller than 65536 */ 534728415Speter#define NMAX 5552 534828415Speter/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 534928415Speter 5350106696Salfred#define DO1(buf,i) {s1 += buf[(i)]; s2 += s1;} 5351106696Salfred#define DO2(buf,i) DO1(buf,i); DO1(buf,(i)+1); 5352106696Salfred#define DO4(buf,i) DO2(buf,i); DO2(buf,(i)+2); 5353106696Salfred#define DO8(buf,i) DO4(buf,i); DO4(buf,(i)+4); 535434768Speter#define DO16(buf) DO8(buf,0); DO8(buf,8); 535528415Speter 535628415Speter/* ========================================================================= */ 535728415SpeteruLong adler32(adler, buf, len) 535828415Speter uLong adler; 535934768Speter const Bytef *buf; 536028415Speter uInt len; 536128415Speter{ 536228415Speter unsigned long s1 = adler & 0xffff; 536328415Speter unsigned long s2 = (adler >> 16) & 0xffff; 536428415Speter int k; 536528415Speter 536628415Speter if (buf == Z_NULL) return 1L; 536728415Speter 536828415Speter while (len > 0) { 536928415Speter k = len < NMAX ? len : NMAX; 537028415Speter len -= k; 537128415Speter while (k >= 16) { 537228415Speter DO16(buf); 537334768Speter buf += 16; 537428415Speter k -= 16; 537528415Speter } 537628415Speter if (k != 0) do { 537734768Speter s1 += *buf++; 537834768Speter s2 += s1; 537928415Speter } while (--k); 538028415Speter s1 %= BASE; 538128415Speter s2 %= BASE; 538228415Speter } 538328415Speter return (s2 << 16) | s1; 538428415Speter} 538534768Speter/* --- adler32.c */ 5386130799Smarkm 5387130799Smarkm#ifdef _KERNEL 5388130799Smarkmstatic int 5389130799Smarkmzlib_modevent(module_t mod, int type, void *unused) 5390130799Smarkm{ 5391130799Smarkm switch (type) { 5392130799Smarkm case MOD_LOAD: 5393130799Smarkm return 0; 5394130799Smarkm case MOD_UNLOAD: 5395130799Smarkm return 0; 5396130799Smarkm } 5397130799Smarkm return EINVAL; 5398130799Smarkm} 5399130799Smarkm 5400130799Smarkmstatic moduledata_t zlib_mod = { 5401130799Smarkm "zlib", 5402130799Smarkm zlib_modevent, 5403130799Smarkm 0 5404130799Smarkm}; 5405130799SmarkmDECLARE_MODULE(zlib, zlib_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST); 5406130799SmarkmMODULE_VERSION(zlib, 1); 5407130799Smarkm#endif /* _KERNEL */ 5408