zlib.c revision 106696
128415Speter/* 234768Speter * This file is derived from various .h and .c files from the zlib-1.0.4 328415Speter * distribution by Jean-loup Gailly and Mark Adler, with some additions 428415Speter * by Paul Mackerras to aid in implementing Deflate compression and 528415Speter * decompression for PPP packets. See zlib.h for conditions of 628415Speter * distribution and use. 728415Speter * 828415Speter * Changes that have been made include: 928415Speter * - added Z_PACKET_FLUSH (see zlib.h for details) 1034768Speter * - added inflateIncomp and deflateOutputPending 1134768Speter * - allow strm->next_out to be NULL, meaning discard the output 1228415Speter * 1350477Speter * $FreeBSD: head/sys/net/zlib.c 106696 2002-11-09 12:55:07Z alfred $ 1428415Speter */ 1528415Speter 1628415Speter/* 1734768Speter * ==FILEVERSION 971210== 1828415Speter * 1928415Speter * This marker is used by the Linux installation script to determine 2028415Speter * whether an up-to-date version of this file is already installed. 2128415Speter */ 2228415Speter 2334768Speter#define NO_DUMMY_DECL 2434768Speter#define NO_ZCFUNCS 2534768Speter#define MY_ZCALLOC 2634768Speter 2755205Speter#if defined(__FreeBSD__) && defined(_KERNEL) 2834768Speter#define inflate inflate_ppp /* FreeBSD already has an inflate :-( */ 2934768Speter#endif 3034768Speter 3134768Speter 3234768Speter/* +++ zutil.h */ 3328415Speter/* zutil.h -- internal interface and configuration of the compression library 3434768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 3528415Speter * For conditions of distribution and use, see copyright notice in zlib.h 3628415Speter */ 3728415Speter 3828415Speter/* WARNING: this file should *not* be used by applications. It is 3928415Speter part of the implementation of the compression library and is 4028415Speter subject to change. Applications should only use zlib.h. 4128415Speter */ 4228415Speter 4334768Speter/* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */ 4428415Speter 4534768Speter#ifndef _Z_UTIL_H 4628415Speter#define _Z_UTIL_H 4728415Speter 4855205Speter#ifdef _KERNEL 4928415Speter#include <net/zlib.h> 5028415Speter#else 5128415Speter#include "zlib.h" 5228415Speter#endif 5328415Speter 5455205Speter#ifdef _KERNEL 5534768Speter/* Assume this is a *BSD or SVR4 kernel */ 5634768Speter#include <sys/types.h> 5734768Speter#include <sys/time.h> 5834768Speter#include <sys/systm.h> 5934768Speter# define HAVE_MEMCPY 6034768Speter 6134768Speter#else 6234768Speter#if defined(__KERNEL__) 6334768Speter/* Assume this is a Linux kernel */ 6434768Speter#include <linux/string.h> 6534768Speter#define HAVE_MEMCPY 6634768Speter 6734768Speter#else /* not kernel */ 6834768Speter 6934768Speter#if defined(MSDOS)||defined(VMS)||defined(CRAY)||defined(WIN32)||defined(RISCOS) 7034768Speter# include <stddef.h> 7134768Speter# include <errno.h> 7234768Speter#else 7334768Speter extern int errno; 7434768Speter#endif 7534768Speter#ifdef STDC 7634768Speter# include <string.h> 7734768Speter# include <stdlib.h> 7834768Speter#endif 7934768Speter#endif /* __KERNEL__ */ 8055205Speter#endif /* _KERNEL */ 8134768Speter 8228415Speter#ifndef local 8328415Speter# define local static 8428415Speter#endif 8528415Speter/* compile with -Dlocal if your debugger can't find static symbols */ 8628415Speter 8728415Spetertypedef unsigned char uch; 8828415Spetertypedef uch FAR uchf; 8928415Spetertypedef unsigned short ush; 9028415Spetertypedef ush FAR ushf; 9128415Spetertypedef unsigned long ulg; 9228415Speter 9334768Speterextern const char *z_errmsg[10]; /* indexed by 2-zlib_error */ 9434768Speter/* (size given to avoid silly warnings with Visual C++) */ 9528415Speter 9634768Speter#define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)] 9734768Speter 9834768Speter#define ERR_RETURN(strm,err) \ 9943305Sdillon return (strm->msg = (const char*)ERR_MSG(err), (err)) 10028415Speter/* To be used only when the state is known to be valid */ 10128415Speter 10228415Speter /* common constants */ 10328415Speter 10428415Speter#ifndef DEF_WBITS 10528415Speter# define DEF_WBITS MAX_WBITS 10628415Speter#endif 10728415Speter/* default windowBits for decompression. MAX_WBITS is for compression only */ 10828415Speter 10928415Speter#if MAX_MEM_LEVEL >= 8 11028415Speter# define DEF_MEM_LEVEL 8 11128415Speter#else 11228415Speter# define DEF_MEM_LEVEL MAX_MEM_LEVEL 11328415Speter#endif 11428415Speter/* default memLevel */ 11528415Speter 11628415Speter#define STORED_BLOCK 0 11728415Speter#define STATIC_TREES 1 11828415Speter#define DYN_TREES 2 11928415Speter/* The three kinds of block type */ 12028415Speter 12128415Speter#define MIN_MATCH 3 12228415Speter#define MAX_MATCH 258 12328415Speter/* The minimum and maximum match lengths */ 12428415Speter 12534768Speter#define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */ 12634768Speter 12734768Speter /* target dependencies */ 12834768Speter 12934768Speter#ifdef MSDOS 13034768Speter# define OS_CODE 0x00 13134768Speter# ifdef __TURBOC__ 13234768Speter# include <alloc.h> 13334768Speter# else /* MSC or DJGPP */ 13434768Speter# include <malloc.h> 13534768Speter# endif 13634768Speter#endif 13734768Speter 13834768Speter#ifdef OS2 13934768Speter# define OS_CODE 0x06 14034768Speter#endif 14134768Speter 14234768Speter#ifdef WIN32 /* Window 95 & Windows NT */ 14334768Speter# define OS_CODE 0x0b 14434768Speter#endif 14534768Speter 14634768Speter#if defined(VAXC) || defined(VMS) 14734768Speter# define OS_CODE 0x02 14834768Speter# define FOPEN(name, mode) \ 14934768Speter fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512") 15034768Speter#endif 15134768Speter 15234768Speter#ifdef AMIGA 15334768Speter# define OS_CODE 0x01 15434768Speter#endif 15534768Speter 15634768Speter#if defined(ATARI) || defined(atarist) 15734768Speter# define OS_CODE 0x05 15834768Speter#endif 15934768Speter 16034768Speter#ifdef MACOS 16134768Speter# define OS_CODE 0x07 16234768Speter#endif 16334768Speter 16434768Speter#ifdef __50SERIES /* Prime/PRIMOS */ 16534768Speter# define OS_CODE 0x0F 16634768Speter#endif 16734768Speter 16834768Speter#ifdef TOPS20 16934768Speter# define OS_CODE 0x0a 17034768Speter#endif 17134768Speter 17234768Speter#if defined(_BEOS_) || defined(RISCOS) 17334768Speter# define fdopen(fd,mode) NULL /* No fdopen() */ 17434768Speter#endif 17534768Speter 17634768Speter /* Common defaults */ 17734768Speter 17834768Speter#ifndef OS_CODE 17934768Speter# define OS_CODE 0x03 /* assume Unix */ 18034768Speter#endif 18134768Speter 18234768Speter#ifndef FOPEN 18334768Speter# define FOPEN(name, mode) fopen((name), (mode)) 18434768Speter#endif 18534768Speter 18628415Speter /* functions */ 18728415Speter 18834768Speter#ifdef HAVE_STRERROR 18934768Speter extern char *strerror OF((int)); 19034768Speter# define zstrerror(errnum) strerror(errnum) 19128415Speter#else 19234768Speter# define zstrerror(errnum) "" 19334768Speter#endif 19428415Speter 19534768Speter#if defined(pyr) 19634768Speter# define NO_MEMCPY 19734768Speter#endif 19834768Speter#if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER) 19934768Speter /* Use our own functions for small and medium model with MSC <= 5.0. 20034768Speter * You may have to use the same strategy for Borland C (untested). 20134768Speter */ 20234768Speter# define NO_MEMCPY 20334768Speter#endif 20428415Speter#if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY) 20528415Speter# define HAVE_MEMCPY 20628415Speter#endif 20728415Speter#ifdef HAVE_MEMCPY 20834768Speter# ifdef SMALL_MEDIUM /* MSDOS small or medium model */ 20934768Speter# define zmemcpy _fmemcpy 21034768Speter# define zmemcmp _fmemcmp 21134768Speter# define zmemzero(dest, len) _fmemset(dest, 0, len) 21234768Speter# else 21328415Speter# define zmemcpy memcpy 21434768Speter# define zmemcmp memcmp 21528415Speter# define zmemzero(dest, len) memset(dest, 0, len) 21634768Speter# endif 21728415Speter#else 21828415Speter extern void zmemcpy OF((Bytef* dest, Bytef* source, uInt len)); 21934768Speter extern int zmemcmp OF((Bytef* s1, Bytef* s2, uInt len)); 22028415Speter extern void zmemzero OF((Bytef* dest, uInt len)); 22128415Speter#endif 22228415Speter 22328415Speter/* Diagnostic functions */ 22428415Speter#ifdef DEBUG_ZLIB 22528415Speter# include <stdio.h> 22628415Speter# ifndef verbose 22728415Speter# define verbose 0 22828415Speter# endif 22934768Speter extern void z_error OF((char *m)); 23028415Speter# define Assert(cond,msg) {if(!(cond)) z_error(msg);} 23128415Speter# define Trace(x) fprintf x 23228415Speter# define Tracev(x) {if (verbose) fprintf x ;} 23328415Speter# define Tracevv(x) {if (verbose>1) fprintf x ;} 23428415Speter# define Tracec(c,x) {if (verbose && (c)) fprintf x ;} 23528415Speter# define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;} 23628415Speter#else 23728415Speter# define Assert(cond,msg) 23828415Speter# define Trace(x) 23928415Speter# define Tracev(x) 24028415Speter# define Tracevv(x) 24128415Speter# define Tracec(c,x) 24228415Speter# define Tracecv(c,x) 24328415Speter#endif 24428415Speter 24528415Speter 24634768Spetertypedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len)); 24728415Speter 24834768Spetervoidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); 24934768Spetervoid zcfree OF((voidpf opaque, voidpf ptr)); 25028415Speter 25128415Speter#define ZALLOC(strm, items, size) \ 25228415Speter (*((strm)->zalloc))((strm)->opaque, (items), (size)) 25334768Speter#define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr)) 25434768Speter#define TRY_FREE(s, p) {if (p) ZFREE(s, p);} 25528415Speter 25634768Speter#endif /* _Z_UTIL_H */ 25734768Speter/* --- zutil.h */ 25834768Speter 25934768Speter/* +++ deflate.h */ 26028415Speter/* deflate.h -- internal compression state 26134768Speter * Copyright (C) 1995-1996 Jean-loup Gailly 26228415Speter * For conditions of distribution and use, see copyright notice in zlib.h 26328415Speter */ 26428415Speter 26528415Speter/* WARNING: this file should *not* be used by applications. It is 26628415Speter part of the implementation of the compression library and is 26728415Speter subject to change. Applications should only use zlib.h. 26828415Speter */ 26928415Speter 27034768Speter/* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */ 27128415Speter 27234768Speter#ifndef _DEFLATE_H 27334768Speter#define _DEFLATE_H 27428415Speter 27534768Speter/* #include "zutil.h" */ 27634768Speter 27728415Speter/* =========================================================================== 27828415Speter * Internal compression state. 27928415Speter */ 28028415Speter 28128415Speter#define LENGTH_CODES 29 28228415Speter/* number of length codes, not counting the special END_BLOCK code */ 28328415Speter 28428415Speter#define LITERALS 256 28528415Speter/* number of literal bytes 0..255 */ 28628415Speter 28728415Speter#define L_CODES (LITERALS+1+LENGTH_CODES) 28828415Speter/* number of Literal or Length codes, including the END_BLOCK code */ 28928415Speter 29028415Speter#define D_CODES 30 29128415Speter/* number of distance codes */ 29228415Speter 29328415Speter#define BL_CODES 19 29428415Speter/* number of codes used to transfer the bit lengths */ 29528415Speter 29628415Speter#define HEAP_SIZE (2*L_CODES+1) 29728415Speter/* maximum heap size */ 29828415Speter 29928415Speter#define MAX_BITS 15 30028415Speter/* All codes must not exceed MAX_BITS bits */ 30128415Speter 30228415Speter#define INIT_STATE 42 30328415Speter#define BUSY_STATE 113 30428415Speter#define FINISH_STATE 666 30528415Speter/* Stream status */ 30628415Speter 30728415Speter 30828415Speter/* Data structure describing a single value and its code string. */ 30928415Spetertypedef struct ct_data_s { 31028415Speter union { 31128415Speter ush freq; /* frequency count */ 31228415Speter ush code; /* bit string */ 31328415Speter } fc; 31428415Speter union { 31528415Speter ush dad; /* father node in Huffman tree */ 31628415Speter ush len; /* length of bit string */ 31728415Speter } dl; 31828415Speter} FAR ct_data; 31928415Speter 32028415Speter#define Freq fc.freq 32128415Speter#define Code fc.code 32228415Speter#define Dad dl.dad 32328415Speter#define Len dl.len 32428415Speter 32528415Spetertypedef struct static_tree_desc_s static_tree_desc; 32628415Speter 32728415Spetertypedef struct tree_desc_s { 32828415Speter ct_data *dyn_tree; /* the dynamic tree */ 32928415Speter int max_code; /* largest code with non zero frequency */ 33028415Speter static_tree_desc *stat_desc; /* the corresponding static tree */ 33128415Speter} FAR tree_desc; 33228415Speter 33328415Spetertypedef ush Pos; 33428415Spetertypedef Pos FAR Posf; 33528415Spetertypedef unsigned IPos; 33628415Speter 33728415Speter/* A Pos is an index in the character window. We use short instead of int to 33828415Speter * save space in the various tables. IPos is used only for parameter passing. 33928415Speter */ 34028415Speter 34128415Spetertypedef struct deflate_state { 34234768Speter z_streamp strm; /* pointer back to this zlib stream */ 34328415Speter int status; /* as the name implies */ 34428415Speter Bytef *pending_buf; /* output still pending */ 34534768Speter ulg pending_buf_size; /* size of pending_buf */ 34628415Speter Bytef *pending_out; /* next pending byte to output to the stream */ 34728415Speter int pending; /* nb of bytes in the pending buffer */ 34828415Speter int noheader; /* suppress zlib header and adler32 */ 34934768Speter Byte data_type; /* UNKNOWN, BINARY or ASCII */ 35028415Speter Byte method; /* STORED (for zip only) or DEFLATED */ 35134768Speter int last_flush; /* value of flush param for previous deflate call */ 35228415Speter 35328415Speter /* used by deflate.c: */ 35428415Speter 35528415Speter uInt w_size; /* LZ77 window size (32K by default) */ 35628415Speter uInt w_bits; /* log2(w_size) (8..16) */ 35728415Speter uInt w_mask; /* w_size - 1 */ 35828415Speter 35928415Speter Bytef *window; 36028415Speter /* Sliding window. Input bytes are read into the second half of the window, 36128415Speter * and move to the first half later to keep a dictionary of at least wSize 36228415Speter * bytes. With this organization, matches are limited to a distance of 36328415Speter * wSize-MAX_MATCH bytes, but this ensures that IO is always 36428415Speter * performed with a length multiple of the block size. Also, it limits 36528415Speter * the window size to 64K, which is quite useful on MSDOS. 36628415Speter * To do: use the user input buffer as sliding window. 36728415Speter */ 36828415Speter 36928415Speter ulg window_size; 37028415Speter /* Actual size of window: 2*wSize, except when the user input buffer 37128415Speter * is directly used as sliding window. 37228415Speter */ 37328415Speter 37428415Speter Posf *prev; 37528415Speter /* Link to older string with same hash index. To limit the size of this 37628415Speter * array to 64K, this link is maintained only for the last 32K strings. 37728415Speter * An index in this array is thus a window index modulo 32K. 37828415Speter */ 37928415Speter 38028415Speter Posf *head; /* Heads of the hash chains or NIL. */ 38128415Speter 38228415Speter uInt ins_h; /* hash index of string to be inserted */ 38328415Speter uInt hash_size; /* number of elements in hash table */ 38428415Speter uInt hash_bits; /* log2(hash_size) */ 38528415Speter uInt hash_mask; /* hash_size-1 */ 38628415Speter 38728415Speter uInt hash_shift; 38828415Speter /* Number of bits by which ins_h must be shifted at each input 38928415Speter * step. It must be such that after MIN_MATCH steps, the oldest 39028415Speter * byte no longer takes part in the hash key, that is: 39128415Speter * hash_shift * MIN_MATCH >= hash_bits 39228415Speter */ 39328415Speter 39428415Speter long block_start; 39528415Speter /* Window position at the beginning of the current output block. Gets 39628415Speter * negative when the window is moved backwards. 39728415Speter */ 39828415Speter 39928415Speter uInt match_length; /* length of best match */ 40028415Speter IPos prev_match; /* previous match */ 40128415Speter int match_available; /* set if previous match exists */ 40228415Speter uInt strstart; /* start of string to insert */ 40328415Speter uInt match_start; /* start of matching string */ 40428415Speter uInt lookahead; /* number of valid bytes ahead in window */ 40528415Speter 40628415Speter uInt prev_length; 40728415Speter /* Length of the best match at previous step. Matches not greater than this 40828415Speter * are discarded. This is used in the lazy match evaluation. 40928415Speter */ 41028415Speter 41128415Speter uInt max_chain_length; 41228415Speter /* To speed up deflation, hash chains are never searched beyond this 41328415Speter * length. A higher limit improves compression ratio but degrades the 41428415Speter * speed. 41528415Speter */ 41628415Speter 41728415Speter uInt max_lazy_match; 41828415Speter /* Attempt to find a better match only when the current match is strictly 41928415Speter * smaller than this value. This mechanism is used only for compression 42028415Speter * levels >= 4. 42128415Speter */ 42228415Speter# define max_insert_length max_lazy_match 42328415Speter /* Insert new strings in the hash table only if the match length is not 42428415Speter * greater than this length. This saves time but degrades compression. 42528415Speter * max_insert_length is used only for compression levels <= 3. 42628415Speter */ 42728415Speter 42828415Speter int level; /* compression level (1..9) */ 42928415Speter int strategy; /* favor or force Huffman coding*/ 43028415Speter 43128415Speter uInt good_match; 43228415Speter /* Use a faster search when the previous match is longer than this */ 43328415Speter 43434768Speter int nice_match; /* Stop searching when current match exceeds this */ 43528415Speter 43628415Speter /* used by trees.c: */ 43728415Speter /* Didn't use ct_data typedef below to supress compiler warning */ 43828415Speter struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 43928415Speter struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ 44028415Speter struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */ 44128415Speter 44228415Speter struct tree_desc_s l_desc; /* desc. for literal tree */ 44328415Speter struct tree_desc_s d_desc; /* desc. for distance tree */ 44428415Speter struct tree_desc_s bl_desc; /* desc. for bit length tree */ 44528415Speter 44628415Speter ush bl_count[MAX_BITS+1]; 44728415Speter /* number of codes at each bit length for an optimal tree */ 44828415Speter 44928415Speter int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 45028415Speter int heap_len; /* number of elements in the heap */ 45128415Speter int heap_max; /* element of largest frequency */ 45228415Speter /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 45328415Speter * The same heap array is used to build all trees. 45428415Speter */ 45528415Speter 45628415Speter uch depth[2*L_CODES+1]; 45728415Speter /* Depth of each subtree used as tie breaker for trees of equal frequency 45828415Speter */ 45928415Speter 46028415Speter uchf *l_buf; /* buffer for literals or lengths */ 46128415Speter 46228415Speter uInt lit_bufsize; 46328415Speter /* Size of match buffer for literals/lengths. There are 4 reasons for 46428415Speter * limiting lit_bufsize to 64K: 46528415Speter * - frequencies can be kept in 16 bit counters 46628415Speter * - if compression is not successful for the first block, all input 46728415Speter * data is still in the window so we can still emit a stored block even 46828415Speter * when input comes from standard input. (This can also be done for 46928415Speter * all blocks if lit_bufsize is not greater than 32K.) 47028415Speter * - if compression is not successful for a file smaller than 64K, we can 47128415Speter * even emit a stored file instead of a stored block (saving 5 bytes). 47228415Speter * This is applicable only for zip (not gzip or zlib). 47328415Speter * - creating new Huffman trees less frequently may not provide fast 47428415Speter * adaptation to changes in the input data statistics. (Take for 47528415Speter * example a binary file with poorly compressible code followed by 47628415Speter * a highly compressible string table.) Smaller buffer sizes give 47728415Speter * fast adaptation but have of course the overhead of transmitting 47828415Speter * trees more frequently. 47928415Speter * - I can't count above 4 48028415Speter */ 48128415Speter 48228415Speter uInt last_lit; /* running index in l_buf */ 48328415Speter 48428415Speter ushf *d_buf; 48528415Speter /* Buffer for distances. To simplify the code, d_buf and l_buf have 48628415Speter * the same number of elements. To use different lengths, an extra flag 48728415Speter * array would be necessary. 48828415Speter */ 48928415Speter 49028415Speter ulg opt_len; /* bit length of current block with optimal trees */ 49128415Speter ulg static_len; /* bit length of current block with static trees */ 49228415Speter ulg compressed_len; /* total bit length of compressed file */ 49328415Speter uInt matches; /* number of string matches in current block */ 49428415Speter int last_eob_len; /* bit length of EOB code for last block */ 49528415Speter 49628415Speter#ifdef DEBUG_ZLIB 49728415Speter ulg bits_sent; /* bit length of the compressed data */ 49828415Speter#endif 49928415Speter 50028415Speter ush bi_buf; 50128415Speter /* Output buffer. bits are inserted starting at the bottom (least 50228415Speter * significant bits). 50328415Speter */ 50428415Speter int bi_valid; 50528415Speter /* Number of valid bits in bi_buf. All bits above the last valid bit 50628415Speter * are always zero. 50728415Speter */ 50828415Speter 50928415Speter} FAR deflate_state; 51028415Speter 51128415Speter/* Output a byte on the stream. 51228415Speter * IN assertion: there is enough room in pending_buf. 51328415Speter */ 51428415Speter#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);} 51528415Speter 51628415Speter 51728415Speter#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 51828415Speter/* Minimum amount of lookahead, except at the end of the input file. 51928415Speter * See deflate.c for comments about the MIN_MATCH+1. 52028415Speter */ 52128415Speter 52228415Speter#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) 52328415Speter/* In order to simplify the code, particularly on 16 bit machines, match 52428415Speter * distances are limited to MAX_DIST instead of WSIZE. 52528415Speter */ 52628415Speter 52728415Speter /* in trees.c */ 52834768Spetervoid _tr_init OF((deflate_state *s)); 52934768Speterint _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); 53034768Speterulg _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len, 53134768Speter int eof)); 53234768Spetervoid _tr_align OF((deflate_state *s)); 53334768Spetervoid _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len, 53428415Speter int eof)); 53534768Spetervoid _tr_stored_type_only OF((deflate_state *)); 53628415Speter 53734768Speter#endif 53834768Speter/* --- deflate.h */ 53928415Speter 54034768Speter/* +++ deflate.c */ 54128415Speter/* deflate.c -- compress data using the deflation algorithm 54234768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 54328415Speter * For conditions of distribution and use, see copyright notice in zlib.h 54428415Speter */ 54528415Speter 54628415Speter/* 54728415Speter * ALGORITHM 54828415Speter * 54928415Speter * The "deflation" process depends on being able to identify portions 55028415Speter * of the input text which are identical to earlier input (within a 55128415Speter * sliding window trailing behind the input currently being processed). 55228415Speter * 55328415Speter * The most straightforward technique turns out to be the fastest for 55428415Speter * most input files: try all possible matches and select the longest. 55528415Speter * The key feature of this algorithm is that insertions into the string 55628415Speter * dictionary are very simple and thus fast, and deletions are avoided 55728415Speter * completely. Insertions are performed at each input character, whereas 55828415Speter * string matches are performed only when the previous match ends. So it 55928415Speter * is preferable to spend more time in matches to allow very fast string 56028415Speter * insertions and avoid deletions. The matching algorithm for small 56128415Speter * strings is inspired from that of Rabin & Karp. A brute force approach 56228415Speter * is used to find longer strings when a small match has been found. 56328415Speter * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 56428415Speter * (by Leonid Broukhis). 56528415Speter * A previous version of this file used a more sophisticated algorithm 56628415Speter * (by Fiala and Greene) which is guaranteed to run in linear amortized 56728415Speter * time, but has a larger average cost, uses more memory and is patented. 56828415Speter * However the F&G algorithm may be faster for some highly redundant 56928415Speter * files if the parameter max_chain_length (described below) is too large. 57028415Speter * 57128415Speter * ACKNOWLEDGEMENTS 57228415Speter * 57328415Speter * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 57428415Speter * I found it in 'freeze' written by Leonid Broukhis. 57528415Speter * Thanks to many people for bug reports and testing. 57628415Speter * 57728415Speter * REFERENCES 57828415Speter * 57934768Speter * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 58034768Speter * Available in ftp://ds.internic.net/rfc/rfc1951.txt 58128415Speter * 58228415Speter * A description of the Rabin and Karp algorithm is given in the book 58328415Speter * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 58428415Speter * 58528415Speter * Fiala,E.R., and Greene,D.H. 58628415Speter * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 58728415Speter * 58828415Speter */ 58928415Speter 59034768Speter/* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */ 59128415Speter 59234768Speter/* #include "deflate.h" */ 59334768Speter 59434768Speterchar deflate_copyright[] = " deflate 1.0.4 Copyright 1995-1996 Jean-loup Gailly "; 59528415Speter/* 59628415Speter If you use the zlib library in a product, an acknowledgment is welcome 59728415Speter in the documentation of your product. If for some reason you cannot 59828415Speter include such an acknowledgment, I would appreciate that you keep this 59928415Speter copyright string in the executable of your product. 60028415Speter */ 60128415Speter 60234768Speter/* =========================================================================== 60334768Speter * Function prototypes. 60434768Speter */ 60534768Spetertypedef enum { 60634768Speter need_more, /* block not completed, need more input or more output */ 60734768Speter block_done, /* block flush performed */ 60834768Speter finish_started, /* finish started, need only more output at next deflate */ 60934768Speter finish_done /* finish done, accept no more input or output */ 61034768Speter} block_state; 61134768Speter 61234768Spetertypedef block_state (*compress_func) OF((deflate_state *s, int flush)); 61334768Speter/* Compression function. Returns the block state after the call. */ 61434768Speter 61534768Speterlocal void fill_window OF((deflate_state *s)); 61634768Speterlocal block_state deflate_stored OF((deflate_state *s, int flush)); 61734768Speterlocal block_state deflate_fast OF((deflate_state *s, int flush)); 61834768Speterlocal block_state deflate_slow OF((deflate_state *s, int flush)); 61934768Speterlocal void lm_init OF((deflate_state *s)); 62034768Speterlocal void putShortMSB OF((deflate_state *s, uInt b)); 62134768Speterlocal void flush_pending OF((z_streamp strm)); 62234768Speterlocal int read_buf OF((z_streamp strm, charf *buf, unsigned size)); 62334768Speter#ifdef ASMV 62434768Speter void match_init OF((void)); /* asm code initialization */ 62534768Speter uInt longest_match OF((deflate_state *s, IPos cur_match)); 62634768Speter#else 62734768Speterlocal uInt longest_match OF((deflate_state *s, IPos cur_match)); 62834768Speter#endif 62934768Speter 63034768Speter#ifdef DEBUG_ZLIB 63134768Speterlocal void check_match OF((deflate_state *s, IPos start, IPos match, 63234768Speter int length)); 63334768Speter#endif 63434768Speter 63534768Speter/* =========================================================================== 63634768Speter * Local data 63734768Speter */ 63834768Speter 63928415Speter#define NIL 0 64028415Speter/* Tail of hash chains */ 64128415Speter 64228415Speter#ifndef TOO_FAR 64328415Speter# define TOO_FAR 4096 64428415Speter#endif 64528415Speter/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 64628415Speter 64728415Speter#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 64828415Speter/* Minimum amount of lookahead, except at the end of the input file. 64928415Speter * See deflate.c for comments about the MIN_MATCH+1. 65028415Speter */ 65128415Speter 65228415Speter/* Values for max_lazy_match, good_match and max_chain_length, depending on 65328415Speter * the desired pack level (0..9). The values given below have been tuned to 65428415Speter * exclude worst case performance for pathological files. Better values may be 65528415Speter * found for specific files. 65628415Speter */ 65728415Spetertypedef struct config_s { 65828415Speter ush good_length; /* reduce lazy search above this match length */ 65928415Speter ush max_lazy; /* do not perform lazy search above this match length */ 66028415Speter ush nice_length; /* quit search above this match length */ 66128415Speter ush max_chain; 66234768Speter compress_func func; 66328415Speter} config; 66428415Speter 66528415Speterlocal config configuration_table[10] = { 66628415Speter/* good lazy nice chain */ 66734768Speter/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 66834768Speter/* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ 66934768Speter/* 2 */ {4, 5, 16, 8, deflate_fast}, 67034768Speter/* 3 */ {4, 6, 32, 32, deflate_fast}, 67128415Speter 67234768Speter/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 67334768Speter/* 5 */ {8, 16, 32, 32, deflate_slow}, 67434768Speter/* 6 */ {8, 16, 128, 128, deflate_slow}, 67534768Speter/* 7 */ {8, 32, 128, 256, deflate_slow}, 67634768Speter/* 8 */ {32, 128, 258, 1024, deflate_slow}, 67734768Speter/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ 67828415Speter 67928415Speter/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 68028415Speter * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 68128415Speter * meaning. 68228415Speter */ 68328415Speter 68428415Speter#define EQUAL 0 68528415Speter/* result of memcmp for equal strings */ 68628415Speter 68734768Speter#ifndef NO_DUMMY_DECL 68834768Speterstruct static_tree_desc_s {int dummy;}; /* for buggy compilers */ 68928415Speter#endif 69028415Speter 69128415Speter/* =========================================================================== 69228415Speter * Update a hash value with the given input byte 69328415Speter * IN assertion: all calls to to UPDATE_HASH are made with consecutive 69428415Speter * input characters, so that a running hash key can be computed from the 69528415Speter * previous key instead of complete recalculation each time. 69628415Speter */ 69728415Speter#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 69828415Speter 69928415Speter 70028415Speter/* =========================================================================== 70128415Speter * Insert string str in the dictionary and set match_head to the previous head 70228415Speter * of the hash chain (the most recent string with same hash key). Return 70328415Speter * the previous length of the hash chain. 70428415Speter * IN assertion: all calls to to INSERT_STRING are made with consecutive 70528415Speter * input characters and the first MIN_MATCH bytes of str are valid 70628415Speter * (except for the last MIN_MATCH-1 bytes of the input file). 70728415Speter */ 70828415Speter#define INSERT_STRING(s, str, match_head) \ 70928415Speter (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 71028415Speter s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ 71134768Speter s->head[s->ins_h] = (Pos)(str)) 71228415Speter 71328415Speter/* =========================================================================== 71428415Speter * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 71528415Speter * prev[] will be initialized on the fly. 71628415Speter */ 71728415Speter#define CLEAR_HASH(s) \ 71828415Speter s->head[s->hash_size-1] = NIL; \ 71928415Speter zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 72028415Speter 72128415Speter/* ========================================================================= */ 72234768Speterint deflateInit_(strm, level, version, stream_size) 72334768Speter z_streamp strm; 72428415Speter int level; 72534768Speter const char *version; 72634768Speter int stream_size; 72728415Speter{ 72834768Speter return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 72934768Speter Z_DEFAULT_STRATEGY, version, stream_size); 73028415Speter /* To do: ignore strm->next_in if we use it as window */ 73128415Speter} 73228415Speter 73328415Speter/* ========================================================================= */ 73434768Speterint deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 73534768Speter version, stream_size) 73634768Speter z_streamp strm; 73728415Speter int level; 73828415Speter int method; 73928415Speter int windowBits; 74028415Speter int memLevel; 74128415Speter int strategy; 74234768Speter const char *version; 74334768Speter int stream_size; 74428415Speter{ 74528415Speter deflate_state *s; 74628415Speter int noheader = 0; 74734768Speter static char* my_version = ZLIB_VERSION; 74828415Speter 74934768Speter ushf *overlay; 75034768Speter /* We overlay pending_buf and d_buf+l_buf. This works since the average 75134768Speter * output size for (length,distance) codes is <= 24 bits. 75234768Speter */ 75334768Speter 75434768Speter if (version == Z_NULL || version[0] != my_version[0] || 75534768Speter stream_size != sizeof(z_stream)) { 75634768Speter return Z_VERSION_ERROR; 75734768Speter } 75828415Speter if (strm == Z_NULL) return Z_STREAM_ERROR; 75928415Speter 76028415Speter strm->msg = Z_NULL; 76134768Speter#ifndef NO_ZCFUNCS 76234768Speter if (strm->zalloc == Z_NULL) { 76334768Speter strm->zalloc = zcalloc; 76434768Speter strm->opaque = (voidpf)0; 76534768Speter } 76634768Speter if (strm->zfree == Z_NULL) strm->zfree = zcfree; 76734768Speter#endif 76828415Speter 76928415Speter if (level == Z_DEFAULT_COMPRESSION) level = 6; 77028415Speter 77128415Speter if (windowBits < 0) { /* undocumented feature: suppress zlib header */ 77228415Speter noheader = 1; 77328415Speter windowBits = -windowBits; 77428415Speter } 77534768Speter if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 77693013Sjedgar windowBits < 9 || windowBits > 15 || level < 0 || level > 9 || 77734768Speter strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 77828415Speter return Z_STREAM_ERROR; 77928415Speter } 78034768Speter s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 78128415Speter if (s == Z_NULL) return Z_MEM_ERROR; 78228415Speter strm->state = (struct internal_state FAR *)s; 78328415Speter s->strm = strm; 78428415Speter 78528415Speter s->noheader = noheader; 78628415Speter s->w_bits = windowBits; 78728415Speter s->w_size = 1 << s->w_bits; 78828415Speter s->w_mask = s->w_size - 1; 78928415Speter 79028415Speter s->hash_bits = memLevel + 7; 79128415Speter s->hash_size = 1 << s->hash_bits; 79228415Speter s->hash_mask = s->hash_size - 1; 79328415Speter s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 79428415Speter 79534768Speter s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 79634768Speter s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 79734768Speter s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 79828415Speter 79928415Speter s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 80028415Speter 80134768Speter overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 80234768Speter s->pending_buf = (uchf *) overlay; 80334768Speter s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 80428415Speter 80528415Speter if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 80628415Speter s->pending_buf == Z_NULL) { 80743305Sdillon strm->msg = (const char*)ERR_MSG(Z_MEM_ERROR); 80828415Speter deflateEnd (strm); 80928415Speter return Z_MEM_ERROR; 81028415Speter } 81134768Speter s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 81234768Speter s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 81328415Speter 81428415Speter s->level = level; 81528415Speter s->strategy = strategy; 81628415Speter s->method = (Byte)method; 81728415Speter 81828415Speter return deflateReset(strm); 81928415Speter} 82028415Speter 82128415Speter/* ========================================================================= */ 82234768Speterint deflateSetDictionary (strm, dictionary, dictLength) 82334768Speter z_streamp strm; 82434768Speter const Bytef *dictionary; 82534768Speter uInt dictLength; 82634768Speter{ 82734768Speter deflate_state *s; 82834768Speter uInt length = dictLength; 82934768Speter uInt n; 83034768Speter IPos hash_head = 0; 83134768Speter 83234768Speter if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL) 83334768Speter return Z_STREAM_ERROR; 83434768Speter 83534768Speter s = (deflate_state *) strm->state; 83634768Speter if (s->status != INIT_STATE) return Z_STREAM_ERROR; 83734768Speter 83834768Speter strm->adler = adler32(strm->adler, dictionary, dictLength); 83934768Speter 84034768Speter if (length < MIN_MATCH) return Z_OK; 84134768Speter if (length > MAX_DIST(s)) { 84234768Speter length = MAX_DIST(s); 84334768Speter#ifndef USE_DICT_HEAD 84434768Speter dictionary += dictLength - length; /* use the tail of the dictionary */ 84534768Speter#endif 84634768Speter } 84734768Speter zmemcpy((charf *)s->window, dictionary, length); 84834768Speter s->strstart = length; 84934768Speter s->block_start = (long)length; 85034768Speter 85134768Speter /* Insert all strings in the hash table (except for the last two bytes). 85234768Speter * s->lookahead stays null, so s->ins_h will be recomputed at the next 85334768Speter * call of fill_window. 85434768Speter */ 85534768Speter s->ins_h = s->window[0]; 85634768Speter UPDATE_HASH(s, s->ins_h, s->window[1]); 85734768Speter for (n = 0; n <= length - MIN_MATCH; n++) { 85834768Speter INSERT_STRING(s, n, hash_head); 85934768Speter } 86034768Speter if (hash_head) hash_head = 0; /* to make compiler happy */ 86134768Speter return Z_OK; 86234768Speter} 86334768Speter 86434768Speter/* ========================================================================= */ 86528415Speterint deflateReset (strm) 86634768Speter z_streamp strm; 86728415Speter{ 86828415Speter deflate_state *s; 86928415Speter 87028415Speter if (strm == Z_NULL || strm->state == Z_NULL || 87134768Speter strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR; 87228415Speter 87328415Speter strm->total_in = strm->total_out = 0; 87428415Speter strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 87528415Speter strm->data_type = Z_UNKNOWN; 87628415Speter 87728415Speter s = (deflate_state *)strm->state; 87828415Speter s->pending = 0; 87928415Speter s->pending_out = s->pending_buf; 88028415Speter 88128415Speter if (s->noheader < 0) { 88228415Speter s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */ 88328415Speter } 88428415Speter s->status = s->noheader ? BUSY_STATE : INIT_STATE; 88534768Speter strm->adler = 1; 88634768Speter s->last_flush = Z_NO_FLUSH; 88728415Speter 88834768Speter _tr_init(s); 88928415Speter lm_init(s); 89028415Speter 89128415Speter return Z_OK; 89228415Speter} 89328415Speter 89434768Speter/* ========================================================================= */ 89534768Speterint deflateParams(strm, level, strategy) 89634768Speter z_streamp strm; 89734768Speter int level; 89834768Speter int strategy; 89934768Speter{ 90034768Speter deflate_state *s; 90134768Speter compress_func func; 90234768Speter int err = Z_OK; 90334768Speter 90434768Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 90534768Speter s = (deflate_state *) strm->state; 90634768Speter 90734768Speter if (level == Z_DEFAULT_COMPRESSION) { 90834768Speter level = 6; 90934768Speter } 91034768Speter if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 91134768Speter return Z_STREAM_ERROR; 91234768Speter } 91334768Speter func = configuration_table[s->level].func; 91434768Speter 91534768Speter if (func != configuration_table[level].func && strm->total_in != 0) { 91634768Speter /* Flush the last buffer: */ 91734768Speter err = deflate(strm, Z_PARTIAL_FLUSH); 91834768Speter } 91934768Speter if (s->level != level) { 92034768Speter s->level = level; 92134768Speter s->max_lazy_match = configuration_table[level].max_lazy; 92234768Speter s->good_match = configuration_table[level].good_length; 92334768Speter s->nice_match = configuration_table[level].nice_length; 92434768Speter s->max_chain_length = configuration_table[level].max_chain; 92534768Speter } 92634768Speter s->strategy = strategy; 92734768Speter return err; 92834768Speter} 92934768Speter 93028415Speter/* ========================================================================= 93128415Speter * Put a short in the pending buffer. The 16-bit value is put in MSB order. 93228415Speter * IN assertion: the stream state is correct and there is enough room in 93328415Speter * pending_buf. 93428415Speter */ 93528415Speterlocal void putShortMSB (s, b) 93628415Speter deflate_state *s; 93728415Speter uInt b; 93828415Speter{ 93928415Speter put_byte(s, (Byte)(b >> 8)); 94028415Speter put_byte(s, (Byte)(b & 0xff)); 94128415Speter} 94228415Speter 94328415Speter/* ========================================================================= 94434768Speter * Flush as much pending output as possible. All deflate() output goes 94534768Speter * through this function so some applications may wish to modify it 94634768Speter * to avoid allocating a large strm->next_out buffer and copying into it. 94734768Speter * (See also read_buf()). 94828415Speter */ 94928415Speterlocal void flush_pending(strm) 95034768Speter z_streamp strm; 95128415Speter{ 95234768Speter deflate_state *s = (deflate_state *) strm->state; 95334768Speter unsigned len = s->pending; 95428415Speter 95528415Speter if (len > strm->avail_out) len = strm->avail_out; 95628415Speter if (len == 0) return; 95728415Speter 95834768Speter if (strm->next_out != Z_NULL) { 95934768Speter zmemcpy(strm->next_out, s->pending_out, len); 96028415Speter strm->next_out += len; 96128415Speter } 96234768Speter s->pending_out += len; 96328415Speter strm->total_out += len; 96434768Speter strm->avail_out -= len; 96534768Speter s->pending -= len; 96634768Speter if (s->pending == 0) { 96734768Speter s->pending_out = s->pending_buf; 96828415Speter } 96928415Speter} 97028415Speter 97128415Speter/* ========================================================================= */ 97228415Speterint deflate (strm, flush) 97334768Speter z_streamp strm; 97428415Speter int flush; 97528415Speter{ 97634768Speter int old_flush; /* value of flush param for previous deflate call */ 97734768Speter deflate_state *s; 97828415Speter 97934768Speter if (strm == Z_NULL || strm->state == Z_NULL || 98034768Speter flush > Z_FINISH || flush < 0) { 98134768Speter return Z_STREAM_ERROR; 98234768Speter } 98334768Speter s = (deflate_state *) strm->state; 98434768Speter 98534768Speter if ((strm->next_in == Z_NULL && strm->avail_in != 0) || 98634768Speter (s->status == FINISH_STATE && flush != Z_FINISH)) { 98728415Speter ERR_RETURN(strm, Z_STREAM_ERROR); 98828415Speter } 98928415Speter if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 99028415Speter 99134768Speter s->strm = strm; /* just in case */ 99234768Speter old_flush = s->last_flush; 99334768Speter s->last_flush = flush; 99428415Speter 99528415Speter /* Write the zlib header */ 99634768Speter if (s->status == INIT_STATE) { 99728415Speter 99834768Speter uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 99934768Speter uInt level_flags = (s->level-1) >> 1; 100028415Speter 100128415Speter if (level_flags > 3) level_flags = 3; 100228415Speter header |= (level_flags << 6); 100334768Speter if (s->strstart != 0) header |= PRESET_DICT; 100428415Speter header += 31 - (header % 31); 100528415Speter 100634768Speter s->status = BUSY_STATE; 100734768Speter putShortMSB(s, header); 100834768Speter 100934768Speter /* Save the adler32 of the preset dictionary: */ 101034768Speter if (s->strstart != 0) { 101134768Speter putShortMSB(s, (uInt)(strm->adler >> 16)); 101234768Speter putShortMSB(s, (uInt)(strm->adler & 0xffff)); 101334768Speter } 101434768Speter strm->adler = 1L; 101528415Speter } 101628415Speter 101728415Speter /* Flush as much pending output as possible */ 101834768Speter if (s->pending != 0) { 101928415Speter flush_pending(strm); 102034768Speter if (strm->avail_out == 0) { 102134768Speter /* Since avail_out is 0, deflate will be called again with 102234768Speter * more output space, but possibly with both pending and 102334768Speter * avail_in equal to zero. There won't be anything to do, 102434768Speter * but this is not an error situation so make sure we 102534768Speter * return OK instead of BUF_ERROR at next call of deflate: 102634768Speter */ 102734768Speter s->last_flush = -1; 102834768Speter return Z_OK; 102934768Speter } 103028415Speter 103134768Speter /* Make sure there is something to do and avoid duplicate consecutive 103234768Speter * flushes. For repeated and useless calls with Z_FINISH, we keep 103334768Speter * returning Z_STREAM_END instead of Z_BUFF_ERROR. 103428415Speter */ 103534768Speter } else if (strm->avail_in == 0 && flush <= old_flush && 103634768Speter flush != Z_FINISH) { 103734768Speter ERR_RETURN(strm, Z_BUF_ERROR); 103828415Speter } 103928415Speter 104028415Speter /* User must not provide more input after the first FINISH: */ 104134768Speter if (s->status == FINISH_STATE && strm->avail_in != 0) { 104228415Speter ERR_RETURN(strm, Z_BUF_ERROR); 104328415Speter } 104428415Speter 104528415Speter /* Start a new block or continue the current one. 104628415Speter */ 104734768Speter if (strm->avail_in != 0 || s->lookahead != 0 || 104834768Speter (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 104934768Speter block_state bstate; 105028415Speter 105134768Speter bstate = (*(configuration_table[s->level].func))(s, flush); 105234768Speter 105334768Speter if (bstate == finish_started || bstate == finish_done) { 105434768Speter s->status = FINISH_STATE; 105528415Speter } 105634768Speter if (bstate == need_more || bstate == finish_started) { 105734768Speter if (strm->avail_out == 0) { 105834768Speter s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 105934768Speter } 106028415Speter return Z_OK; 106134768Speter /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 106234768Speter * of deflate should use the same flush parameter to make sure 106334768Speter * that the flush is complete. So we don't have to output an 106434768Speter * empty block here, this will be done at next call. This also 106534768Speter * ensures that for a very small output buffer, we emit at most 106634768Speter * one empty block. 106728415Speter */ 106834768Speter } 106934768Speter if (bstate == block_done) { 107034768Speter if (flush == Z_PARTIAL_FLUSH) { 107134768Speter _tr_align(s); 107234768Speter } else if (flush == Z_PACKET_FLUSH) { 107334768Speter /* Output just the 3-bit `stored' block type value, 107434768Speter but not a zero length. */ 107534768Speter _tr_stored_type_only(s); 107634768Speter } else { /* FULL_FLUSH or SYNC_FLUSH */ 107734768Speter _tr_stored_block(s, (char*)0, 0L, 0); 107834768Speter /* For a full flush, this empty block will be recognized 107934768Speter * as a special marker by inflate_sync(). 108034768Speter */ 108134768Speter if (flush == Z_FULL_FLUSH) { 108234768Speter CLEAR_HASH(s); /* forget history */ 108334768Speter } 108434768Speter } 108534768Speter flush_pending(strm); 108634768Speter if (strm->avail_out == 0) { 108734768Speter s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 108834768Speter return Z_OK; 108928415Speter } 109034768Speter } 109128415Speter } 109228415Speter Assert(strm->avail_out > 0, "bug2"); 109328415Speter 109428415Speter if (flush != Z_FINISH) return Z_OK; 109534768Speter if (s->noheader) return Z_STREAM_END; 109628415Speter 109728415Speter /* Write the zlib trailer (adler32) */ 109834768Speter putShortMSB(s, (uInt)(strm->adler >> 16)); 109934768Speter putShortMSB(s, (uInt)(strm->adler & 0xffff)); 110028415Speter flush_pending(strm); 110128415Speter /* If avail_out is zero, the application will call deflate again 110228415Speter * to flush the rest. 110328415Speter */ 110434768Speter s->noheader = -1; /* write the trailer only once! */ 110534768Speter return s->pending != 0 ? Z_OK : Z_STREAM_END; 110628415Speter} 110728415Speter 110828415Speter/* ========================================================================= */ 110928415Speterint deflateEnd (strm) 111034768Speter z_streamp strm; 111128415Speter{ 111234768Speter int status; 111334768Speter deflate_state *s; 111428415Speter 111534768Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 111634768Speter s = (deflate_state *) strm->state; 111728415Speter 111834768Speter status = s->status; 111934768Speter if (status != INIT_STATE && status != BUSY_STATE && 112034768Speter status != FINISH_STATE) { 112134768Speter return Z_STREAM_ERROR; 112234768Speter } 112328415Speter 112434768Speter /* Deallocate in reverse order of allocations: */ 112534768Speter TRY_FREE(strm, s->pending_buf); 112634768Speter TRY_FREE(strm, s->head); 112734768Speter TRY_FREE(strm, s->prev); 112834768Speter TRY_FREE(strm, s->window); 112934768Speter 113034768Speter ZFREE(strm, s); 113128415Speter strm->state = Z_NULL; 113228415Speter 113334768Speter return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 113434768Speter} 113534768Speter 113634768Speter/* ========================================================================= 113734768Speter * Copy the source state to the destination state. 113834768Speter */ 113934768Speterint deflateCopy (dest, source) 114034768Speter z_streamp dest; 114134768Speter z_streamp source; 114234768Speter{ 114334768Speter deflate_state *ds; 114434768Speter deflate_state *ss; 114534768Speter ushf *overlay; 114634768Speter 114734768Speter if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) 114834768Speter return Z_STREAM_ERROR; 114934768Speter ss = (deflate_state *) source->state; 115034768Speter 115137065Speter zmemcpy(dest, source, sizeof(*dest)); 115234768Speter 115334768Speter ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 115434768Speter if (ds == Z_NULL) return Z_MEM_ERROR; 115534768Speter dest->state = (struct internal_state FAR *) ds; 115637065Speter zmemcpy(ds, ss, sizeof(*ds)); 115734768Speter ds->strm = dest; 115834768Speter 115934768Speter ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 116034768Speter ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 116134768Speter ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 116234768Speter overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 116334768Speter ds->pending_buf = (uchf *) overlay; 116434768Speter 116534768Speter if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 116634768Speter ds->pending_buf == Z_NULL) { 116734768Speter deflateEnd (dest); 116834768Speter return Z_MEM_ERROR; 116934768Speter } 117034768Speter /* ??? following zmemcpy doesn't work for 16-bit MSDOS */ 117134768Speter zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 117234768Speter zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); 117334768Speter zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); 117434768Speter zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 117534768Speter 117634768Speter ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 117734768Speter ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 117834768Speter ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 117934768Speter 118034768Speter ds->l_desc.dyn_tree = ds->dyn_ltree; 118134768Speter ds->d_desc.dyn_tree = ds->dyn_dtree; 118234768Speter ds->bl_desc.dyn_tree = ds->bl_tree; 118334768Speter 118428415Speter return Z_OK; 118528415Speter} 118628415Speter 118728415Speter/* =========================================================================== 118834768Speter * Return the number of bytes of output which are immediately available 118934768Speter * for output from the decompressor. 119034768Speter */ 119134768Speterint deflateOutputPending (strm) 119234768Speter z_streamp strm; 119334768Speter{ 119434768Speter if (strm == Z_NULL || strm->state == Z_NULL) return 0; 119534768Speter 119634768Speter return ((deflate_state *)(strm->state))->pending; 119734768Speter} 119834768Speter 119934768Speter/* =========================================================================== 120028415Speter * Read a new buffer from the current input stream, update the adler32 120134768Speter * and total number of bytes read. All deflate() input goes through 120234768Speter * this function so some applications may wish to modify it to avoid 120334768Speter * allocating a large strm->next_in buffer and copying from it. 120434768Speter * (See also flush_pending()). 120528415Speter */ 120628415Speterlocal int read_buf(strm, buf, size) 120734768Speter z_streamp strm; 120828415Speter charf *buf; 120928415Speter unsigned size; 121028415Speter{ 121128415Speter unsigned len = strm->avail_in; 121228415Speter 121328415Speter if (len > size) len = size; 121428415Speter if (len == 0) return 0; 121528415Speter 121628415Speter strm->avail_in -= len; 121728415Speter 121834768Speter if (!((deflate_state *)(strm->state))->noheader) { 121934768Speter strm->adler = adler32(strm->adler, strm->next_in, len); 122028415Speter } 122128415Speter zmemcpy(buf, strm->next_in, len); 122228415Speter strm->next_in += len; 122328415Speter strm->total_in += len; 122428415Speter 122528415Speter return (int)len; 122628415Speter} 122728415Speter 122828415Speter/* =========================================================================== 122928415Speter * Initialize the "longest match" routines for a new zlib stream 123028415Speter */ 123128415Speterlocal void lm_init (s) 123228415Speter deflate_state *s; 123328415Speter{ 123428415Speter s->window_size = (ulg)2L*s->w_size; 123528415Speter 123628415Speter CLEAR_HASH(s); 123728415Speter 123828415Speter /* Set the default configuration parameters: 123928415Speter */ 124028415Speter s->max_lazy_match = configuration_table[s->level].max_lazy; 124128415Speter s->good_match = configuration_table[s->level].good_length; 124228415Speter s->nice_match = configuration_table[s->level].nice_length; 124328415Speter s->max_chain_length = configuration_table[s->level].max_chain; 124428415Speter 124528415Speter s->strstart = 0; 124628415Speter s->block_start = 0L; 124728415Speter s->lookahead = 0; 124834768Speter s->match_length = s->prev_length = MIN_MATCH-1; 124928415Speter s->match_available = 0; 125028415Speter s->ins_h = 0; 125128415Speter#ifdef ASMV 125228415Speter match_init(); /* initialize the asm code */ 125328415Speter#endif 125428415Speter} 125528415Speter 125628415Speter/* =========================================================================== 125728415Speter * Set match_start to the longest match starting at the given string and 125828415Speter * return its length. Matches shorter or equal to prev_length are discarded, 125928415Speter * in which case the result is equal to prev_length and match_start is 126028415Speter * garbage. 126128415Speter * IN assertions: cur_match is the head of the hash chain for the current 126228415Speter * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 126334768Speter * OUT assertion: the match length is not greater than s->lookahead. 126428415Speter */ 126528415Speter#ifndef ASMV 126628415Speter/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 126728415Speter * match.S. The code will be functionally equivalent. 126828415Speter */ 126934768Speterlocal uInt longest_match(s, cur_match) 127028415Speter deflate_state *s; 127128415Speter IPos cur_match; /* current match */ 127228415Speter{ 127328415Speter unsigned chain_length = s->max_chain_length;/* max hash chain length */ 127428415Speter register Bytef *scan = s->window + s->strstart; /* current string */ 127528415Speter register Bytef *match; /* matched string */ 127628415Speter register int len; /* length of current match */ 127728415Speter int best_len = s->prev_length; /* best match length so far */ 127834768Speter int nice_match = s->nice_match; /* stop if match long enough */ 127928415Speter IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 128028415Speter s->strstart - (IPos)MAX_DIST(s) : NIL; 128128415Speter /* Stop when cur_match becomes <= limit. To simplify the code, 128228415Speter * we prevent matches with the string of window index 0. 128328415Speter */ 128428415Speter Posf *prev = s->prev; 128528415Speter uInt wmask = s->w_mask; 128628415Speter 128728415Speter#ifdef UNALIGNED_OK 128828415Speter /* Compare two bytes at a time. Note: this is not always beneficial. 128928415Speter * Try with and without -DUNALIGNED_OK to check. 129028415Speter */ 129128415Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 129228415Speter register ush scan_start = *(ushf*)scan; 129328415Speter register ush scan_end = *(ushf*)(scan+best_len-1); 129428415Speter#else 129528415Speter register Bytef *strend = s->window + s->strstart + MAX_MATCH; 129628415Speter register Byte scan_end1 = scan[best_len-1]; 129728415Speter register Byte scan_end = scan[best_len]; 129828415Speter#endif 129928415Speter 130028415Speter /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 130128415Speter * It is easy to get rid of this optimization if necessary. 130228415Speter */ 130328415Speter Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 130428415Speter 130528415Speter /* Do not waste too much time if we already have a good match: */ 130628415Speter if (s->prev_length >= s->good_match) { 130728415Speter chain_length >>= 2; 130828415Speter } 130934768Speter /* Do not look for matches beyond the end of the input. This is necessary 131034768Speter * to make deflate deterministic. 131134768Speter */ 131234768Speter if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 131334768Speter 131428415Speter Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 131528415Speter 131628415Speter do { 131728415Speter Assert(cur_match < s->strstart, "no future"); 131828415Speter match = s->window + cur_match; 131928415Speter 132028415Speter /* Skip to next match if the match length cannot increase 132128415Speter * or if the match length is less than 2: 132228415Speter */ 132328415Speter#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 132428415Speter /* This code assumes sizeof(unsigned short) == 2. Do not use 132528415Speter * UNALIGNED_OK if your compiler uses a different size. 132628415Speter */ 132728415Speter if (*(ushf*)(match+best_len-1) != scan_end || 132828415Speter *(ushf*)match != scan_start) continue; 132928415Speter 133028415Speter /* It is not necessary to compare scan[2] and match[2] since they are 133128415Speter * always equal when the other bytes match, given that the hash keys 133228415Speter * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 133328415Speter * strstart+3, +5, ... up to strstart+257. We check for insufficient 133428415Speter * lookahead only every 4th comparison; the 128th check will be made 133528415Speter * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 133628415Speter * necessary to put more guard bytes at the end of the window, or 133728415Speter * to check more often for insufficient lookahead. 133828415Speter */ 133928415Speter Assert(scan[2] == match[2], "scan[2]?"); 134028415Speter scan++, match++; 134128415Speter do { 134228415Speter } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 134328415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 134428415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 134528415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 134628415Speter scan < strend); 134728415Speter /* The funny "do {}" generates better code on most compilers */ 134828415Speter 134928415Speter /* Here, scan <= window+strstart+257 */ 135028415Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 135128415Speter if (*scan == *match) scan++; 135228415Speter 135328415Speter len = (MAX_MATCH - 1) - (int)(strend-scan); 135428415Speter scan = strend - (MAX_MATCH-1); 135528415Speter 135628415Speter#else /* UNALIGNED_OK */ 135728415Speter 135828415Speter if (match[best_len] != scan_end || 135928415Speter match[best_len-1] != scan_end1 || 136028415Speter *match != *scan || 136128415Speter *++match != scan[1]) continue; 136228415Speter 136328415Speter /* The check at best_len-1 can be removed because it will be made 136428415Speter * again later. (This heuristic is not always a win.) 136528415Speter * It is not necessary to compare scan[2] and match[2] since they 136628415Speter * are always equal when the other bytes match, given that 136728415Speter * the hash keys are equal and that HASH_BITS >= 8. 136828415Speter */ 136928415Speter scan += 2, match++; 137028415Speter Assert(*scan == *match, "match[2]?"); 137128415Speter 137228415Speter /* We check for insufficient lookahead only every 8th comparison; 137328415Speter * the 256th check will be made at strstart+258. 137428415Speter */ 137528415Speter do { 137628415Speter } while (*++scan == *++match && *++scan == *++match && 137728415Speter *++scan == *++match && *++scan == *++match && 137828415Speter *++scan == *++match && *++scan == *++match && 137928415Speter *++scan == *++match && *++scan == *++match && 138028415Speter scan < strend); 138128415Speter 138228415Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 138328415Speter 138428415Speter len = MAX_MATCH - (int)(strend - scan); 138528415Speter scan = strend - MAX_MATCH; 138628415Speter 138728415Speter#endif /* UNALIGNED_OK */ 138828415Speter 138928415Speter if (len > best_len) { 139028415Speter s->match_start = cur_match; 139128415Speter best_len = len; 139234768Speter if (len >= nice_match) break; 139328415Speter#ifdef UNALIGNED_OK 139428415Speter scan_end = *(ushf*)(scan+best_len-1); 139528415Speter#else 139628415Speter scan_end1 = scan[best_len-1]; 139728415Speter scan_end = scan[best_len]; 139828415Speter#endif 139928415Speter } 140028415Speter } while ((cur_match = prev[cur_match & wmask]) > limit 140128415Speter && --chain_length != 0); 140228415Speter 140334768Speter if ((uInt)best_len <= s->lookahead) return best_len; 140434768Speter return s->lookahead; 140528415Speter} 140628415Speter#endif /* ASMV */ 140728415Speter 140828415Speter#ifdef DEBUG_ZLIB 140928415Speter/* =========================================================================== 141028415Speter * Check that the match at match_start is indeed a match. 141128415Speter */ 141228415Speterlocal void check_match(s, start, match, length) 141328415Speter deflate_state *s; 141428415Speter IPos start, match; 141528415Speter int length; 141628415Speter{ 141728415Speter /* check that the match is indeed a match */ 141834768Speter if (zmemcmp((charf *)s->window + match, 141928415Speter (charf *)s->window + start, length) != EQUAL) { 142034768Speter fprintf(stderr, " start %u, match %u, length %d\n", 142134768Speter start, match, length); 142234768Speter do { 142334768Speter fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 142434768Speter } while (--length != 0); 142528415Speter z_error("invalid match"); 142628415Speter } 142734768Speter if (z_verbose > 1) { 142828415Speter fprintf(stderr,"\\[%d,%d]", start-match, length); 142928415Speter do { putc(s->window[start++], stderr); } while (--length != 0); 143028415Speter } 143128415Speter} 143228415Speter#else 143328415Speter# define check_match(s, start, match, length) 143428415Speter#endif 143528415Speter 143628415Speter/* =========================================================================== 143728415Speter * Fill the window when the lookahead becomes insufficient. 143828415Speter * Updates strstart and lookahead. 143928415Speter * 144028415Speter * IN assertion: lookahead < MIN_LOOKAHEAD 144128415Speter * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 144228415Speter * At least one byte has been read, or avail_in == 0; reads are 144328415Speter * performed for at least two bytes (required for the zip translate_eol 144428415Speter * option -- not supported here). 144528415Speter */ 144628415Speterlocal void fill_window(s) 144728415Speter deflate_state *s; 144828415Speter{ 144928415Speter register unsigned n, m; 145028415Speter register Posf *p; 145128415Speter unsigned more; /* Amount of free space at the end of the window. */ 145228415Speter uInt wsize = s->w_size; 145328415Speter 145428415Speter do { 145528415Speter more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 145628415Speter 145728415Speter /* Deal with !@#$% 64K limit: */ 145828415Speter if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 145928415Speter more = wsize; 146034768Speter 146128415Speter } else if (more == (unsigned)(-1)) { 146228415Speter /* Very unlikely, but possible on 16 bit machine if strstart == 0 146328415Speter * and lookahead == 1 (input done one byte at time) 146428415Speter */ 146528415Speter more--; 146628415Speter 146728415Speter /* If the window is almost full and there is insufficient lookahead, 146828415Speter * move the upper half to the lower one to make room in the upper half. 146928415Speter */ 147028415Speter } else if (s->strstart >= wsize+MAX_DIST(s)) { 147128415Speter 147228415Speter zmemcpy((charf *)s->window, (charf *)s->window+wsize, 147328415Speter (unsigned)wsize); 147428415Speter s->match_start -= wsize; 147528415Speter s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 147628415Speter s->block_start -= (long) wsize; 147728415Speter 147828415Speter /* Slide the hash table (could be avoided with 32 bit values 147934768Speter at the expense of memory usage). We slide even when level == 0 148034768Speter to keep the hash table consistent if we switch back to level > 0 148134768Speter later. (Using level 0 permanently is not an optimal usage of 148234768Speter zlib, so we don't care about this pathological case.) 148328415Speter */ 148428415Speter n = s->hash_size; 148528415Speter p = &s->head[n]; 148628415Speter do { 148728415Speter m = *--p; 148828415Speter *p = (Pos)(m >= wsize ? m-wsize : NIL); 148928415Speter } while (--n); 149028415Speter 149128415Speter n = wsize; 149228415Speter p = &s->prev[n]; 149328415Speter do { 149428415Speter m = *--p; 149528415Speter *p = (Pos)(m >= wsize ? m-wsize : NIL); 149628415Speter /* If n is not on any hash chain, prev[n] is garbage but 149728415Speter * its value will never be used. 149828415Speter */ 149928415Speter } while (--n); 150028415Speter more += wsize; 150128415Speter } 150228415Speter if (s->strm->avail_in == 0) return; 150328415Speter 150428415Speter /* If there was no sliding: 150528415Speter * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 150628415Speter * more == window_size - lookahead - strstart 150728415Speter * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 150828415Speter * => more >= window_size - 2*WSIZE + 2 150928415Speter * In the BIG_MEM or MMAP case (not yet supported), 151028415Speter * window_size == input_size + MIN_LOOKAHEAD && 151128415Speter * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 151228415Speter * Otherwise, window_size == 2*WSIZE so more >= 2. 151328415Speter * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 151428415Speter */ 151528415Speter Assert(more >= 2, "more < 2"); 151628415Speter 151728415Speter n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead, 151828415Speter more); 151928415Speter s->lookahead += n; 152028415Speter 152128415Speter /* Initialize the hash value now that we have some input: */ 152228415Speter if (s->lookahead >= MIN_MATCH) { 152328415Speter s->ins_h = s->window[s->strstart]; 152428415Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 152528415Speter#if MIN_MATCH != 3 152628415Speter Call UPDATE_HASH() MIN_MATCH-3 more times 152728415Speter#endif 152828415Speter } 152928415Speter /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 153028415Speter * but this is not important since only literal bytes will be emitted. 153128415Speter */ 153228415Speter 153328415Speter } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 153428415Speter} 153528415Speter 153628415Speter/* =========================================================================== 153728415Speter * Flush the current block, with given end-of-file flag. 153828415Speter * IN assertion: strstart is set to the end of the current match. 153928415Speter */ 154034768Speter#define FLUSH_BLOCK_ONLY(s, eof) { \ 154134768Speter _tr_flush_block(s, (s->block_start >= 0L ? \ 154234768Speter (charf *)&s->window[(unsigned)s->block_start] : \ 154334768Speter (charf *)Z_NULL), \ 154434768Speter (ulg)((long)s->strstart - s->block_start), \ 154534768Speter (eof)); \ 154628415Speter s->block_start = s->strstart; \ 154728415Speter flush_pending(s->strm); \ 154828415Speter Tracev((stderr,"[FLUSH]")); \ 154928415Speter} 155028415Speter 155128415Speter/* Same but force premature exit if necessary. */ 155234768Speter#define FLUSH_BLOCK(s, eof) { \ 155334768Speter FLUSH_BLOCK_ONLY(s, eof); \ 155434768Speter if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ 155528415Speter} 155628415Speter 155728415Speter/* =========================================================================== 155834768Speter * Copy without compression as much as possible from the input stream, return 155934768Speter * the current block state. 156034768Speter * This function does not insert new strings in the dictionary since 156134768Speter * uncompressible data is probably not useful. This function is used 156234768Speter * only for the level=0 compression option. 156334768Speter * NOTE: this function should be optimized to avoid extra copying from 156434768Speter * window to pending_buf. 156534768Speter */ 156634768Speterlocal block_state deflate_stored(s, flush) 156734768Speter deflate_state *s; 156834768Speter int flush; 156934768Speter{ 157034768Speter /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 157134768Speter * to pending_buf_size, and each stored block has a 5 byte header: 157234768Speter */ 157334768Speter ulg max_block_size = 0xffff; 157434768Speter ulg max_start; 157534768Speter 157634768Speter if (max_block_size > s->pending_buf_size - 5) { 157734768Speter max_block_size = s->pending_buf_size - 5; 157834768Speter } 157934768Speter 158034768Speter /* Copy as much as possible from input to output: */ 158134768Speter for (;;) { 158234768Speter /* Fill the window as much as possible: */ 158334768Speter if (s->lookahead <= 1) { 158434768Speter 158534768Speter Assert(s->strstart < s->w_size+MAX_DIST(s) || 158634768Speter s->block_start >= (long)s->w_size, "slide too late"); 158734768Speter 158834768Speter fill_window(s); 158934768Speter if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 159034768Speter 159134768Speter if (s->lookahead == 0) break; /* flush the current block */ 159234768Speter } 159334768Speter Assert(s->block_start >= 0L, "block gone"); 159434768Speter 159534768Speter s->strstart += s->lookahead; 159634768Speter s->lookahead = 0; 159734768Speter 159834768Speter /* Emit a stored block if pending_buf will be full: */ 159934768Speter max_start = s->block_start + max_block_size; 160034768Speter if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 160134768Speter /* strstart == 0 is possible when wraparound on 16-bit machine */ 160234768Speter s->lookahead = (uInt)(s->strstart - max_start); 160334768Speter s->strstart = (uInt)max_start; 160434768Speter FLUSH_BLOCK(s, 0); 160534768Speter } 160634768Speter /* Flush if we may have to slide, otherwise block_start may become 160734768Speter * negative and the data will be gone: 160834768Speter */ 160934768Speter if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 161034768Speter FLUSH_BLOCK(s, 0); 161134768Speter } 161234768Speter } 161334768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 161434768Speter return flush == Z_FINISH ? finish_done : block_done; 161534768Speter} 161634768Speter 161734768Speter/* =========================================================================== 161834768Speter * Compress as much as possible from the input stream, return the current 161934768Speter * block state. 162034768Speter * This function does not perform lazy evaluation of matches and inserts 162128415Speter * new strings in the dictionary only for unmatched strings or for short 162228415Speter * matches. It is used only for the fast compression options. 162328415Speter */ 162434768Speterlocal block_state deflate_fast(s, flush) 162528415Speter deflate_state *s; 162628415Speter int flush; 162728415Speter{ 162828415Speter IPos hash_head = NIL; /* head of the hash chain */ 162934768Speter int bflush; /* set if current block must be flushed */ 163028415Speter 163128415Speter for (;;) { 163228415Speter /* Make sure that we always have enough lookahead, except 163328415Speter * at the end of the input file. We need MAX_MATCH bytes 163428415Speter * for the next match, plus MIN_MATCH bytes to insert the 163528415Speter * string following the next match. 163628415Speter */ 163728415Speter if (s->lookahead < MIN_LOOKAHEAD) { 163828415Speter fill_window(s); 163934768Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 164034768Speter return need_more; 164134768Speter } 164228415Speter if (s->lookahead == 0) break; /* flush the current block */ 164328415Speter } 164428415Speter 164528415Speter /* Insert the string window[strstart .. strstart+2] in the 164628415Speter * dictionary, and set hash_head to the head of the hash chain: 164728415Speter */ 164828415Speter if (s->lookahead >= MIN_MATCH) { 164928415Speter INSERT_STRING(s, s->strstart, hash_head); 165028415Speter } 165128415Speter 165228415Speter /* Find the longest match, discarding those <= prev_length. 165328415Speter * At this point we have always match_length < MIN_MATCH 165428415Speter */ 165528415Speter if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 165628415Speter /* To simplify the code, we prevent matches with the string 165728415Speter * of window index 0 (in particular we have to avoid a match 165828415Speter * of the string with itself at the start of the input file). 165928415Speter */ 166028415Speter if (s->strategy != Z_HUFFMAN_ONLY) { 166128415Speter s->match_length = longest_match (s, hash_head); 166228415Speter } 166328415Speter /* longest_match() sets match_start */ 166428415Speter } 166528415Speter if (s->match_length >= MIN_MATCH) { 166628415Speter check_match(s, s->strstart, s->match_start, s->match_length); 166728415Speter 166834768Speter bflush = _tr_tally(s, s->strstart - s->match_start, 166934768Speter s->match_length - MIN_MATCH); 167028415Speter 167128415Speter s->lookahead -= s->match_length; 167228415Speter 167328415Speter /* Insert new strings in the hash table only if the match length 167428415Speter * is not too large. This saves time but degrades compression. 167528415Speter */ 167628415Speter if (s->match_length <= s->max_insert_length && 167728415Speter s->lookahead >= MIN_MATCH) { 167828415Speter s->match_length--; /* string at strstart already in hash table */ 167928415Speter do { 168028415Speter s->strstart++; 168128415Speter INSERT_STRING(s, s->strstart, hash_head); 168228415Speter /* strstart never exceeds WSIZE-MAX_MATCH, so there are 168328415Speter * always MIN_MATCH bytes ahead. 168428415Speter */ 168528415Speter } while (--s->match_length != 0); 168628415Speter s->strstart++; 168728415Speter } else { 168828415Speter s->strstart += s->match_length; 168928415Speter s->match_length = 0; 169028415Speter s->ins_h = s->window[s->strstart]; 169128415Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 169228415Speter#if MIN_MATCH != 3 169328415Speter Call UPDATE_HASH() MIN_MATCH-3 more times 169428415Speter#endif 169528415Speter /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 169628415Speter * matter since it will be recomputed at next deflate call. 169728415Speter */ 169828415Speter } 169928415Speter } else { 170028415Speter /* No match, output a literal byte */ 170128415Speter Tracevv((stderr,"%c", s->window[s->strstart])); 170234768Speter bflush = _tr_tally (s, 0, s->window[s->strstart]); 170328415Speter s->lookahead--; 170428415Speter s->strstart++; 170528415Speter } 170634768Speter if (bflush) FLUSH_BLOCK(s, 0); 170728415Speter } 170834768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 170934768Speter return flush == Z_FINISH ? finish_done : block_done; 171028415Speter} 171128415Speter 171228415Speter/* =========================================================================== 171328415Speter * Same as above, but achieves better compression. We use a lazy 171428415Speter * evaluation for matches: a match is finally adopted only if there is 171528415Speter * no better match at the next window position. 171628415Speter */ 171734768Speterlocal block_state deflate_slow(s, flush) 171828415Speter deflate_state *s; 171928415Speter int flush; 172028415Speter{ 172128415Speter IPos hash_head = NIL; /* head of hash chain */ 172228415Speter int bflush; /* set if current block must be flushed */ 172328415Speter 172428415Speter /* Process the input block. */ 172528415Speter for (;;) { 172628415Speter /* Make sure that we always have enough lookahead, except 172728415Speter * at the end of the input file. We need MAX_MATCH bytes 172828415Speter * for the next match, plus MIN_MATCH bytes to insert the 172928415Speter * string following the next match. 173028415Speter */ 173128415Speter if (s->lookahead < MIN_LOOKAHEAD) { 173228415Speter fill_window(s); 173334768Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 173434768Speter return need_more; 173534768Speter } 173628415Speter if (s->lookahead == 0) break; /* flush the current block */ 173728415Speter } 173828415Speter 173928415Speter /* Insert the string window[strstart .. strstart+2] in the 174028415Speter * dictionary, and set hash_head to the head of the hash chain: 174128415Speter */ 174228415Speter if (s->lookahead >= MIN_MATCH) { 174328415Speter INSERT_STRING(s, s->strstart, hash_head); 174428415Speter } 174528415Speter 174628415Speter /* Find the longest match, discarding those <= prev_length. 174728415Speter */ 174828415Speter s->prev_length = s->match_length, s->prev_match = s->match_start; 174928415Speter s->match_length = MIN_MATCH-1; 175028415Speter 175128415Speter if (hash_head != NIL && s->prev_length < s->max_lazy_match && 175228415Speter s->strstart - hash_head <= MAX_DIST(s)) { 175328415Speter /* To simplify the code, we prevent matches with the string 175428415Speter * of window index 0 (in particular we have to avoid a match 175528415Speter * of the string with itself at the start of the input file). 175628415Speter */ 175728415Speter if (s->strategy != Z_HUFFMAN_ONLY) { 175828415Speter s->match_length = longest_match (s, hash_head); 175928415Speter } 176028415Speter /* longest_match() sets match_start */ 176128415Speter 176228415Speter if (s->match_length <= 5 && (s->strategy == Z_FILTERED || 176328415Speter (s->match_length == MIN_MATCH && 176428415Speter s->strstart - s->match_start > TOO_FAR))) { 176528415Speter 176628415Speter /* If prev_match is also MIN_MATCH, match_start is garbage 176728415Speter * but we will ignore the current match anyway. 176828415Speter */ 176928415Speter s->match_length = MIN_MATCH-1; 177028415Speter } 177128415Speter } 177228415Speter /* If there was a match at the previous step and the current 177328415Speter * match is not better, output the previous match: 177428415Speter */ 177528415Speter if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 177628415Speter uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 177728415Speter /* Do not insert strings in hash table beyond this. */ 177828415Speter 177928415Speter check_match(s, s->strstart-1, s->prev_match, s->prev_length); 178028415Speter 178134768Speter bflush = _tr_tally(s, s->strstart -1 - s->prev_match, 178234768Speter s->prev_length - MIN_MATCH); 178328415Speter 178428415Speter /* Insert in hash table all strings up to the end of the match. 178528415Speter * strstart-1 and strstart are already inserted. If there is not 178628415Speter * enough lookahead, the last two strings are not inserted in 178728415Speter * the hash table. 178828415Speter */ 178928415Speter s->lookahead -= s->prev_length-1; 179028415Speter s->prev_length -= 2; 179128415Speter do { 179228415Speter if (++s->strstart <= max_insert) { 179328415Speter INSERT_STRING(s, s->strstart, hash_head); 179428415Speter } 179528415Speter } while (--s->prev_length != 0); 179628415Speter s->match_available = 0; 179728415Speter s->match_length = MIN_MATCH-1; 179828415Speter s->strstart++; 179928415Speter 180034768Speter if (bflush) FLUSH_BLOCK(s, 0); 180128415Speter 180228415Speter } else if (s->match_available) { 180328415Speter /* If there was no match at the previous position, output a 180428415Speter * single literal. If there was a match but the current match 180528415Speter * is longer, truncate the previous match to a single literal. 180628415Speter */ 180728415Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 180834768Speter if (_tr_tally (s, 0, s->window[s->strstart-1])) { 180934768Speter FLUSH_BLOCK_ONLY(s, 0); 181028415Speter } 181128415Speter s->strstart++; 181228415Speter s->lookahead--; 181334768Speter if (s->strm->avail_out == 0) return need_more; 181428415Speter } else { 181528415Speter /* There is no previous match to compare with, wait for 181628415Speter * the next step to decide. 181728415Speter */ 181828415Speter s->match_available = 1; 181928415Speter s->strstart++; 182028415Speter s->lookahead--; 182128415Speter } 182228415Speter } 182328415Speter Assert (flush != Z_NO_FLUSH, "no flush?"); 182428415Speter if (s->match_available) { 182528415Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 182634768Speter _tr_tally (s, 0, s->window[s->strstart-1]); 182728415Speter s->match_available = 0; 182828415Speter } 182934768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 183034768Speter return flush == Z_FINISH ? finish_done : block_done; 183128415Speter} 183234768Speter/* --- deflate.c */ 183328415Speter 183434768Speter/* +++ trees.c */ 183528415Speter/* trees.c -- output deflated data using Huffman coding 183634768Speter * Copyright (C) 1995-1996 Jean-loup Gailly 183728415Speter * For conditions of distribution and use, see copyright notice in zlib.h 183828415Speter */ 183928415Speter 184028415Speter/* 184128415Speter * ALGORITHM 184228415Speter * 184328415Speter * The "deflation" process uses several Huffman trees. The more 184428415Speter * common source values are represented by shorter bit sequences. 184528415Speter * 184628415Speter * Each code tree is stored in a compressed form which is itself 184728415Speter * a Huffman encoding of the lengths of all the code strings (in 184828415Speter * ascending order by source values). The actual code strings are 184928415Speter * reconstructed from the lengths in the inflate process, as described 185028415Speter * in the deflate specification. 185128415Speter * 185228415Speter * REFERENCES 185328415Speter * 185428415Speter * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". 185528415Speter * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc 185628415Speter * 185728415Speter * Storer, James A. 185828415Speter * Data Compression: Methods and Theory, pp. 49-50. 185928415Speter * Computer Science Press, 1988. ISBN 0-7167-8156-5. 186028415Speter * 186128415Speter * Sedgewick, R. 186228415Speter * Algorithms, p290. 186328415Speter * Addison-Wesley, 1983. ISBN 0-201-06672-6. 186428415Speter */ 186528415Speter 186634768Speter/* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */ 186728415Speter 186834768Speter/* #include "deflate.h" */ 186934768Speter 187028415Speter#ifdef DEBUG_ZLIB 187128415Speter# include <ctype.h> 187228415Speter#endif 187328415Speter 187428415Speter/* =========================================================================== 187528415Speter * Constants 187628415Speter */ 187728415Speter 187828415Speter#define MAX_BL_BITS 7 187928415Speter/* Bit length codes must not exceed MAX_BL_BITS bits */ 188028415Speter 188128415Speter#define END_BLOCK 256 188228415Speter/* end of block literal code */ 188328415Speter 188428415Speter#define REP_3_6 16 188528415Speter/* repeat previous bit length 3-6 times (2 bits of repeat count) */ 188628415Speter 188728415Speter#define REPZ_3_10 17 188828415Speter/* repeat a zero length 3-10 times (3 bits of repeat count) */ 188928415Speter 189028415Speter#define REPZ_11_138 18 189128415Speter/* repeat a zero length 11-138 times (7 bits of repeat count) */ 189228415Speter 189328415Speterlocal int extra_lbits[LENGTH_CODES] /* extra bits for each length code */ 189428415Speter = {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}; 189528415Speter 189628415Speterlocal int extra_dbits[D_CODES] /* extra bits for each distance code */ 189728415Speter = {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}; 189828415Speter 189928415Speterlocal int extra_blbits[BL_CODES]/* extra bits for each bit length code */ 190028415Speter = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; 190128415Speter 190228415Speterlocal uch bl_order[BL_CODES] 190328415Speter = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; 190428415Speter/* The lengths of the bit length codes are sent in order of decreasing 190528415Speter * probability, to avoid transmitting the lengths for unused bit length codes. 190628415Speter */ 190728415Speter 190828415Speter#define Buf_size (8 * 2*sizeof(char)) 190928415Speter/* Number of bits used within bi_buf. (bi_buf might be implemented on 191028415Speter * more than 16 bits on some systems.) 191128415Speter */ 191228415Speter 191328415Speter/* =========================================================================== 191428415Speter * Local data. These are initialized only once. 191528415Speter */ 191628415Speter 191728415Speterlocal ct_data static_ltree[L_CODES+2]; 191828415Speter/* The static literal tree. Since the bit lengths are imposed, there is no 191928415Speter * need for the L_CODES extra codes used during heap construction. However 192034768Speter * The codes 286 and 287 are needed to build a canonical tree (see _tr_init 192128415Speter * below). 192228415Speter */ 192328415Speter 192428415Speterlocal ct_data static_dtree[D_CODES]; 192528415Speter/* The static distance tree. (Actually a trivial tree since all codes use 192628415Speter * 5 bits.) 192728415Speter */ 192828415Speter 192928415Speterlocal uch dist_code[512]; 193028415Speter/* distance codes. The first 256 values correspond to the distances 193128415Speter * 3 .. 258, the last 256 values correspond to the top 8 bits of 193228415Speter * the 15 bit distances. 193328415Speter */ 193428415Speter 193528415Speterlocal uch length_code[MAX_MATCH-MIN_MATCH+1]; 193628415Speter/* length code for each normalized match length (0 == MIN_MATCH) */ 193728415Speter 193828415Speterlocal int base_length[LENGTH_CODES]; 193928415Speter/* First normalized length for each code (0 = MIN_MATCH) */ 194028415Speter 194128415Speterlocal int base_dist[D_CODES]; 194228415Speter/* First normalized distance for each code (0 = distance of 1) */ 194328415Speter 194428415Speterstruct static_tree_desc_s { 194528415Speter ct_data *static_tree; /* static tree or NULL */ 194628415Speter intf *extra_bits; /* extra bits for each code or NULL */ 194728415Speter int extra_base; /* base index for extra_bits */ 194828415Speter int elems; /* max number of elements in the tree */ 194928415Speter int max_length; /* max bit length for the codes */ 195028415Speter}; 195128415Speter 195228415Speterlocal static_tree_desc static_l_desc = 195328415Speter{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; 195428415Speter 195528415Speterlocal static_tree_desc static_d_desc = 195628415Speter{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; 195728415Speter 195828415Speterlocal static_tree_desc static_bl_desc = 195928415Speter{(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; 196028415Speter 196128415Speter/* =========================================================================== 196228415Speter * Local (static) routines in this file. 196328415Speter */ 196428415Speter 196534768Speterlocal void tr_static_init OF((void)); 196628415Speterlocal void init_block OF((deflate_state *s)); 196728415Speterlocal void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); 196828415Speterlocal void gen_bitlen OF((deflate_state *s, tree_desc *desc)); 196928415Speterlocal void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); 197028415Speterlocal void build_tree OF((deflate_state *s, tree_desc *desc)); 197128415Speterlocal void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); 197228415Speterlocal void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); 197328415Speterlocal int build_bl_tree OF((deflate_state *s)); 197428415Speterlocal void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, 197528415Speter int blcodes)); 197628415Speterlocal void compress_block OF((deflate_state *s, ct_data *ltree, 197728415Speter ct_data *dtree)); 197828415Speterlocal void set_data_type OF((deflate_state *s)); 197928415Speterlocal unsigned bi_reverse OF((unsigned value, int length)); 198028415Speterlocal void bi_windup OF((deflate_state *s)); 198128415Speterlocal void bi_flush OF((deflate_state *s)); 198228415Speterlocal void copy_block OF((deflate_state *s, charf *buf, unsigned len, 198328415Speter int header)); 198428415Speter 198528415Speter#ifndef DEBUG_ZLIB 1986106696Salfred# define send_code(s, c, tree) send_bits(s, tree[(c)].Code, tree[(c)].Len) 198728415Speter /* Send a code of the given tree. c and tree must not have side effects */ 198828415Speter 198928415Speter#else /* DEBUG_ZLIB */ 199028415Speter# define send_code(s, c, tree) \ 199134768Speter { if (verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ 199228415Speter send_bits(s, tree[c].Code, tree[c].Len); } 199328415Speter#endif 199428415Speter 199528415Speter#define d_code(dist) \ 199628415Speter ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)]) 199728415Speter/* Mapping from a distance to a distance code. dist is the distance - 1 and 199828415Speter * must not have side effects. dist_code[256] and dist_code[257] are never 199928415Speter * used. 200028415Speter */ 200128415Speter 200228415Speter/* =========================================================================== 200328415Speter * Output a short LSB first on the stream. 200428415Speter * IN assertion: there is enough room in pendingBuf. 200528415Speter */ 200628415Speter#define put_short(s, w) { \ 200728415Speter put_byte(s, (uch)((w) & 0xff)); \ 200828415Speter put_byte(s, (uch)((ush)(w) >> 8)); \ 200928415Speter} 201028415Speter 201128415Speter/* =========================================================================== 201228415Speter * Send a value on a given number of bits. 201328415Speter * IN assertion: length <= 16 and value fits in length bits. 201428415Speter */ 201528415Speter#ifdef DEBUG_ZLIB 201628415Speterlocal void send_bits OF((deflate_state *s, int value, int length)); 201728415Speter 201828415Speterlocal void send_bits(s, value, length) 201928415Speter deflate_state *s; 202028415Speter int value; /* value to send */ 202128415Speter int length; /* number of bits */ 202228415Speter{ 202334768Speter Tracevv((stderr," l %2d v %4x ", length, value)); 202428415Speter Assert(length > 0 && length <= 15, "invalid length"); 202528415Speter s->bits_sent += (ulg)length; 202628415Speter 202728415Speter /* If not enough room in bi_buf, use (valid) bits from bi_buf and 202828415Speter * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 202928415Speter * unused bits in value. 203028415Speter */ 203128415Speter if (s->bi_valid > (int)Buf_size - length) { 203228415Speter s->bi_buf |= (value << s->bi_valid); 203328415Speter put_short(s, s->bi_buf); 203428415Speter s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); 203528415Speter s->bi_valid += length - Buf_size; 203628415Speter } else { 203728415Speter s->bi_buf |= value << s->bi_valid; 203828415Speter s->bi_valid += length; 203928415Speter } 204028415Speter} 204128415Speter#else /* !DEBUG_ZLIB */ 204228415Speter 204328415Speter#define send_bits(s, value, length) \ 2044106696Salfred{ int len = (length);\ 2045106696Salfred if ((s)->bi_valid > (int)Buf_size - len) {\ 2046106696Salfred int val = (value);\ 2047106696Salfred (s)->bi_buf |= (val << (s)->bi_valid);\ 2048106696Salfred put_short((s), (s)->bi_buf);\ 2049106696Salfred (s)->bi_buf = (ush)val >> (Buf_size - (s)->bi_valid);\ 2050106696Salfred (s)->bi_valid += len - Buf_size;\ 205128415Speter } else {\ 2052106696Salfred (s)->bi_buf |= (value) << (s)->bi_valid;\ 2053106696Salfred (s)->bi_valid += len;\ 205428415Speter }\ 205528415Speter} 205628415Speter#endif /* DEBUG_ZLIB */ 205728415Speter 205828415Speter 205928415Speter#define MAX(a,b) (a >= b ? a : b) 206028415Speter/* the arguments must not have side effects */ 206128415Speter 206228415Speter/* =========================================================================== 206334768Speter * Initialize the various 'constant' tables. In a multi-threaded environment, 206434768Speter * this function may be called by two threads concurrently, but this is 206534768Speter * harmless since both invocations do exactly the same thing. 206628415Speter */ 206734768Speterlocal void tr_static_init() 206828415Speter{ 206934768Speter static int static_init_done = 0; 207028415Speter int n; /* iterates over tree elements */ 207128415Speter int bits; /* bit counter */ 207228415Speter int length; /* length value */ 207328415Speter int code; /* code value */ 207428415Speter int dist; /* distance index */ 207528415Speter ush bl_count[MAX_BITS+1]; 207628415Speter /* number of codes at each bit length for an optimal tree */ 207728415Speter 207834768Speter if (static_init_done) return; 207934768Speter 208028415Speter /* Initialize the mapping length (0..255) -> length code (0..28) */ 208128415Speter length = 0; 208228415Speter for (code = 0; code < LENGTH_CODES-1; code++) { 208328415Speter base_length[code] = length; 208428415Speter for (n = 0; n < (1<<extra_lbits[code]); n++) { 208528415Speter length_code[length++] = (uch)code; 208628415Speter } 208728415Speter } 208834768Speter Assert (length == 256, "tr_static_init: length != 256"); 208928415Speter /* Note that the length 255 (match length 258) can be represented 209028415Speter * in two different ways: code 284 + 5 bits or code 285, so we 209128415Speter * overwrite length_code[255] to use the best encoding: 209228415Speter */ 209328415Speter length_code[length-1] = (uch)code; 209428415Speter 209528415Speter /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 209628415Speter dist = 0; 209728415Speter for (code = 0 ; code < 16; code++) { 209828415Speter base_dist[code] = dist; 209928415Speter for (n = 0; n < (1<<extra_dbits[code]); n++) { 210028415Speter dist_code[dist++] = (uch)code; 210128415Speter } 210228415Speter } 210334768Speter Assert (dist == 256, "tr_static_init: dist != 256"); 210428415Speter dist >>= 7; /* from now on, all distances are divided by 128 */ 210528415Speter for ( ; code < D_CODES; code++) { 210628415Speter base_dist[code] = dist << 7; 210728415Speter for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 210828415Speter dist_code[256 + dist++] = (uch)code; 210928415Speter } 211028415Speter } 211134768Speter Assert (dist == 256, "tr_static_init: 256+dist != 512"); 211228415Speter 211328415Speter /* Construct the codes of the static literal tree */ 211428415Speter for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 211528415Speter n = 0; 211628415Speter while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 211728415Speter while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 211828415Speter while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 211928415Speter while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 212028415Speter /* Codes 286 and 287 do not exist, but we must include them in the 212128415Speter * tree construction to get a canonical Huffman tree (longest code 212228415Speter * all ones) 212328415Speter */ 212428415Speter gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); 212528415Speter 212628415Speter /* The static distance tree is trivial: */ 212728415Speter for (n = 0; n < D_CODES; n++) { 212828415Speter static_dtree[n].Len = 5; 212934768Speter static_dtree[n].Code = bi_reverse((unsigned)n, 5); 213028415Speter } 213134768Speter static_init_done = 1; 213228415Speter} 213328415Speter 213428415Speter/* =========================================================================== 213528415Speter * Initialize the tree data structures for a new zlib stream. 213628415Speter */ 213734768Spetervoid _tr_init(s) 213828415Speter deflate_state *s; 213928415Speter{ 214034768Speter tr_static_init(); 214128415Speter 214228415Speter s->compressed_len = 0L; 214328415Speter 214428415Speter s->l_desc.dyn_tree = s->dyn_ltree; 214528415Speter s->l_desc.stat_desc = &static_l_desc; 214628415Speter 214728415Speter s->d_desc.dyn_tree = s->dyn_dtree; 214828415Speter s->d_desc.stat_desc = &static_d_desc; 214928415Speter 215028415Speter s->bl_desc.dyn_tree = s->bl_tree; 215128415Speter s->bl_desc.stat_desc = &static_bl_desc; 215228415Speter 215328415Speter s->bi_buf = 0; 215428415Speter s->bi_valid = 0; 215528415Speter s->last_eob_len = 8; /* enough lookahead for inflate */ 215628415Speter#ifdef DEBUG_ZLIB 215728415Speter s->bits_sent = 0L; 215828415Speter#endif 215928415Speter 216028415Speter /* Initialize the first block of the first file: */ 216128415Speter init_block(s); 216228415Speter} 216328415Speter 216428415Speter/* =========================================================================== 216528415Speter * Initialize a new block. 216628415Speter */ 216728415Speterlocal void init_block(s) 216828415Speter deflate_state *s; 216928415Speter{ 217028415Speter int n; /* iterates over tree elements */ 217128415Speter 217228415Speter /* Initialize the trees. */ 217328415Speter for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; 217428415Speter for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; 217528415Speter for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; 217628415Speter 217728415Speter s->dyn_ltree[END_BLOCK].Freq = 1; 217828415Speter s->opt_len = s->static_len = 0L; 217928415Speter s->last_lit = s->matches = 0; 218028415Speter} 218128415Speter 218228415Speter#define SMALLEST 1 218328415Speter/* Index within the heap array of least frequent node in the Huffman tree */ 218428415Speter 218528415Speter 218628415Speter/* =========================================================================== 218728415Speter * Remove the smallest element from the heap and recreate the heap with 218828415Speter * one less element. Updates heap and heap_len. 218928415Speter */ 219028415Speter#define pqremove(s, tree, top) \ 219128415Speter{\ 219228415Speter top = s->heap[SMALLEST]; \ 219328415Speter s->heap[SMALLEST] = s->heap[s->heap_len--]; \ 219428415Speter pqdownheap(s, tree, SMALLEST); \ 219528415Speter} 219628415Speter 219728415Speter/* =========================================================================== 219828415Speter * Compares to subtrees, using the tree depth as tie breaker when 219928415Speter * the subtrees have equal frequency. This minimizes the worst case length. 220028415Speter */ 220128415Speter#define smaller(tree, n, m, depth) \ 220228415Speter (tree[n].Freq < tree[m].Freq || \ 220328415Speter (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 220428415Speter 220528415Speter/* =========================================================================== 220628415Speter * Restore the heap property by moving down the tree starting at node k, 220728415Speter * exchanging a node with the smallest of its two sons if necessary, stopping 220828415Speter * when the heap property is re-established (each father smaller than its 220928415Speter * two sons). 221028415Speter */ 221128415Speterlocal void pqdownheap(s, tree, k) 221228415Speter deflate_state *s; 221328415Speter ct_data *tree; /* the tree to restore */ 221428415Speter int k; /* node to move down */ 221528415Speter{ 221628415Speter int v = s->heap[k]; 221728415Speter int j = k << 1; /* left son of k */ 221828415Speter while (j <= s->heap_len) { 221928415Speter /* Set j to the smallest of the two sons: */ 222028415Speter if (j < s->heap_len && 222128415Speter smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { 222228415Speter j++; 222328415Speter } 222428415Speter /* Exit if v is smaller than both sons */ 222528415Speter if (smaller(tree, v, s->heap[j], s->depth)) break; 222628415Speter 222728415Speter /* Exchange v with the smallest son */ 222828415Speter s->heap[k] = s->heap[j]; k = j; 222928415Speter 223028415Speter /* And continue down the tree, setting j to the left son of k */ 223128415Speter j <<= 1; 223228415Speter } 223328415Speter s->heap[k] = v; 223428415Speter} 223528415Speter 223628415Speter/* =========================================================================== 223728415Speter * Compute the optimal bit lengths for a tree and update the total bit length 223828415Speter * for the current block. 223928415Speter * IN assertion: the fields freq and dad are set, heap[heap_max] and 224028415Speter * above are the tree nodes sorted by increasing frequency. 224128415Speter * OUT assertions: the field len is set to the optimal bit length, the 224228415Speter * array bl_count contains the frequencies for each bit length. 224328415Speter * The length opt_len is updated; static_len is also updated if stree is 224428415Speter * not null. 224528415Speter */ 224628415Speterlocal void gen_bitlen(s, desc) 224728415Speter deflate_state *s; 224828415Speter tree_desc *desc; /* the tree descriptor */ 224928415Speter{ 225028415Speter ct_data *tree = desc->dyn_tree; 225128415Speter int max_code = desc->max_code; 225228415Speter ct_data *stree = desc->stat_desc->static_tree; 225328415Speter intf *extra = desc->stat_desc->extra_bits; 225428415Speter int base = desc->stat_desc->extra_base; 225528415Speter int max_length = desc->stat_desc->max_length; 225628415Speter int h; /* heap index */ 225728415Speter int n, m; /* iterate over the tree elements */ 225828415Speter int bits; /* bit length */ 225928415Speter int xbits; /* extra bits */ 226028415Speter ush f; /* frequency */ 226128415Speter int overflow = 0; /* number of elements with bit length too large */ 226228415Speter 226328415Speter for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; 226428415Speter 226528415Speter /* In a first pass, compute the optimal bit lengths (which may 226628415Speter * overflow in the case of the bit length tree). 226728415Speter */ 226828415Speter tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ 226928415Speter 227028415Speter for (h = s->heap_max+1; h < HEAP_SIZE; h++) { 227128415Speter n = s->heap[h]; 227228415Speter bits = tree[tree[n].Dad].Len + 1; 227328415Speter if (bits > max_length) bits = max_length, overflow++; 227428415Speter tree[n].Len = (ush)bits; 227528415Speter /* We overwrite tree[n].Dad which is no longer needed */ 227628415Speter 227728415Speter if (n > max_code) continue; /* not a leaf node */ 227828415Speter 227928415Speter s->bl_count[bits]++; 228028415Speter xbits = 0; 228128415Speter if (n >= base) xbits = extra[n-base]; 228228415Speter f = tree[n].Freq; 228328415Speter s->opt_len += (ulg)f * (bits + xbits); 228428415Speter if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); 228528415Speter } 228628415Speter if (overflow == 0) return; 228728415Speter 228828415Speter Trace((stderr,"\nbit length overflow\n")); 228928415Speter /* This happens for example on obj2 and pic of the Calgary corpus */ 229028415Speter 229128415Speter /* Find the first bit length which could increase: */ 229228415Speter do { 229328415Speter bits = max_length-1; 229428415Speter while (s->bl_count[bits] == 0) bits--; 229528415Speter s->bl_count[bits]--; /* move one leaf down the tree */ 229628415Speter s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ 229728415Speter s->bl_count[max_length]--; 229828415Speter /* The brother of the overflow item also moves one step up, 229928415Speter * but this does not affect bl_count[max_length] 230028415Speter */ 230128415Speter overflow -= 2; 230228415Speter } while (overflow > 0); 230328415Speter 230428415Speter /* Now recompute all bit lengths, scanning in increasing frequency. 230528415Speter * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 230628415Speter * lengths instead of fixing only the wrong ones. This idea is taken 230728415Speter * from 'ar' written by Haruhiko Okumura.) 230828415Speter */ 230928415Speter for (bits = max_length; bits != 0; bits--) { 231028415Speter n = s->bl_count[bits]; 231128415Speter while (n != 0) { 231228415Speter m = s->heap[--h]; 231328415Speter if (m > max_code) continue; 231428415Speter if (tree[m].Len != (unsigned) bits) { 231528415Speter Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); 231628415Speter s->opt_len += ((long)bits - (long)tree[m].Len) 231728415Speter *(long)tree[m].Freq; 231828415Speter tree[m].Len = (ush)bits; 231928415Speter } 232028415Speter n--; 232128415Speter } 232228415Speter } 232328415Speter} 232428415Speter 232528415Speter/* =========================================================================== 232628415Speter * Generate the codes for a given tree and bit counts (which need not be 232728415Speter * optimal). 232828415Speter * IN assertion: the array bl_count contains the bit length statistics for 232928415Speter * the given tree and the field len is set for all tree elements. 233028415Speter * OUT assertion: the field code is set for all tree elements of non 233128415Speter * zero code length. 233228415Speter */ 233328415Speterlocal void gen_codes (tree, max_code, bl_count) 233428415Speter ct_data *tree; /* the tree to decorate */ 233528415Speter int max_code; /* largest code with non zero frequency */ 233628415Speter ushf *bl_count; /* number of codes at each bit length */ 233728415Speter{ 233828415Speter ush next_code[MAX_BITS+1]; /* next code value for each bit length */ 233928415Speter ush code = 0; /* running code value */ 234028415Speter int bits; /* bit index */ 234128415Speter int n; /* code index */ 234228415Speter 234328415Speter /* The distribution counts are first used to generate the code values 234428415Speter * without bit reversal. 234528415Speter */ 234628415Speter for (bits = 1; bits <= MAX_BITS; bits++) { 234728415Speter next_code[bits] = code = (code + bl_count[bits-1]) << 1; 234828415Speter } 234928415Speter /* Check that the bit counts in bl_count are consistent. The last code 235028415Speter * must be all ones. 235128415Speter */ 235228415Speter Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 235328415Speter "inconsistent bit counts"); 235428415Speter Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); 235528415Speter 235628415Speter for (n = 0; n <= max_code; n++) { 235728415Speter int len = tree[n].Len; 235828415Speter if (len == 0) continue; 235928415Speter /* Now reverse the bits */ 236028415Speter tree[n].Code = bi_reverse(next_code[len]++, len); 236128415Speter 236234768Speter Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", 236328415Speter n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); 236428415Speter } 236528415Speter} 236628415Speter 236728415Speter/* =========================================================================== 236828415Speter * Construct one Huffman tree and assigns the code bit strings and lengths. 236928415Speter * Update the total bit length for the current block. 237028415Speter * IN assertion: the field freq is set for all tree elements. 237128415Speter * OUT assertions: the fields len and code are set to the optimal bit length 237228415Speter * and corresponding code. The length opt_len is updated; static_len is 237328415Speter * also updated if stree is not null. The field max_code is set. 237428415Speter */ 237528415Speterlocal void build_tree(s, desc) 237628415Speter deflate_state *s; 237728415Speter tree_desc *desc; /* the tree descriptor */ 237828415Speter{ 237928415Speter ct_data *tree = desc->dyn_tree; 238028415Speter ct_data *stree = desc->stat_desc->static_tree; 238128415Speter int elems = desc->stat_desc->elems; 238228415Speter int n, m; /* iterate over heap elements */ 238328415Speter int max_code = -1; /* largest code with non zero frequency */ 238428415Speter int node; /* new node being created */ 238528415Speter 238628415Speter /* Construct the initial heap, with least frequent element in 238728415Speter * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 238828415Speter * heap[0] is not used. 238928415Speter */ 239028415Speter s->heap_len = 0, s->heap_max = HEAP_SIZE; 239128415Speter 239228415Speter for (n = 0; n < elems; n++) { 239328415Speter if (tree[n].Freq != 0) { 239428415Speter s->heap[++(s->heap_len)] = max_code = n; 239528415Speter s->depth[n] = 0; 239628415Speter } else { 239728415Speter tree[n].Len = 0; 239828415Speter } 239928415Speter } 240028415Speter 240128415Speter /* The pkzip format requires that at least one distance code exists, 240228415Speter * and that at least one bit should be sent even if there is only one 240328415Speter * possible code. So to avoid special checks later on we force at least 240428415Speter * two codes of non zero frequency. 240528415Speter */ 240628415Speter while (s->heap_len < 2) { 240728415Speter node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); 240828415Speter tree[node].Freq = 1; 240928415Speter s->depth[node] = 0; 241028415Speter s->opt_len--; if (stree) s->static_len -= stree[node].Len; 241128415Speter /* node is 0 or 1 so it does not have extra bits */ 241228415Speter } 241328415Speter desc->max_code = max_code; 241428415Speter 241528415Speter /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 241628415Speter * establish sub-heaps of increasing lengths: 241728415Speter */ 241828415Speter for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); 241928415Speter 242028415Speter /* Construct the Huffman tree by repeatedly combining the least two 242128415Speter * frequent nodes. 242228415Speter */ 242328415Speter node = elems; /* next internal node of the tree */ 242428415Speter do { 242528415Speter pqremove(s, tree, n); /* n = node of least frequency */ 242628415Speter m = s->heap[SMALLEST]; /* m = node of next least frequency */ 242728415Speter 242828415Speter s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ 242928415Speter s->heap[--(s->heap_max)] = m; 243028415Speter 243128415Speter /* Create a new node father of n and m */ 243228415Speter tree[node].Freq = tree[n].Freq + tree[m].Freq; 243328415Speter s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1); 243428415Speter tree[n].Dad = tree[m].Dad = (ush)node; 243528415Speter#ifdef DUMP_BL_TREE 243628415Speter if (tree == s->bl_tree) { 243728415Speter fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", 243828415Speter node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); 243928415Speter } 244028415Speter#endif 244128415Speter /* and insert the new node in the heap */ 244228415Speter s->heap[SMALLEST] = node++; 244328415Speter pqdownheap(s, tree, SMALLEST); 244428415Speter 244528415Speter } while (s->heap_len >= 2); 244628415Speter 244728415Speter s->heap[--(s->heap_max)] = s->heap[SMALLEST]; 244828415Speter 244928415Speter /* At this point, the fields freq and dad are set. We can now 245028415Speter * generate the bit lengths. 245128415Speter */ 245228415Speter gen_bitlen(s, (tree_desc *)desc); 245328415Speter 245428415Speter /* The field len is now set, we can generate the bit codes */ 245528415Speter gen_codes ((ct_data *)tree, max_code, s->bl_count); 245628415Speter} 245728415Speter 245828415Speter/* =========================================================================== 245928415Speter * Scan a literal or distance tree to determine the frequencies of the codes 246028415Speter * in the bit length tree. 246128415Speter */ 246228415Speterlocal void scan_tree (s, tree, max_code) 246328415Speter deflate_state *s; 246428415Speter ct_data *tree; /* the tree to be scanned */ 246528415Speter int max_code; /* and its largest code of non zero frequency */ 246628415Speter{ 246728415Speter int n; /* iterates over all tree elements */ 246828415Speter int prevlen = -1; /* last emitted length */ 246928415Speter int curlen; /* length of current code */ 247028415Speter int nextlen = tree[0].Len; /* length of next code */ 247128415Speter int count = 0; /* repeat count of the current code */ 247228415Speter int max_count = 7; /* max repeat count */ 247328415Speter int min_count = 4; /* min repeat count */ 247428415Speter 247528415Speter if (nextlen == 0) max_count = 138, min_count = 3; 247628415Speter tree[max_code+1].Len = (ush)0xffff; /* guard */ 247728415Speter 247828415Speter for (n = 0; n <= max_code; n++) { 247928415Speter curlen = nextlen; nextlen = tree[n+1].Len; 248028415Speter if (++count < max_count && curlen == nextlen) { 248128415Speter continue; 248228415Speter } else if (count < min_count) { 248328415Speter s->bl_tree[curlen].Freq += count; 248428415Speter } else if (curlen != 0) { 248528415Speter if (curlen != prevlen) s->bl_tree[curlen].Freq++; 248628415Speter s->bl_tree[REP_3_6].Freq++; 248728415Speter } else if (count <= 10) { 248828415Speter s->bl_tree[REPZ_3_10].Freq++; 248928415Speter } else { 249028415Speter s->bl_tree[REPZ_11_138].Freq++; 249128415Speter } 249228415Speter count = 0; prevlen = curlen; 249328415Speter if (nextlen == 0) { 249428415Speter max_count = 138, min_count = 3; 249528415Speter } else if (curlen == nextlen) { 249628415Speter max_count = 6, min_count = 3; 249728415Speter } else { 249828415Speter max_count = 7, min_count = 4; 249928415Speter } 250028415Speter } 250128415Speter} 250228415Speter 250328415Speter/* =========================================================================== 250428415Speter * Send a literal or distance tree in compressed form, using the codes in 250528415Speter * bl_tree. 250628415Speter */ 250728415Speterlocal void send_tree (s, tree, max_code) 250828415Speter deflate_state *s; 250928415Speter ct_data *tree; /* the tree to be scanned */ 251028415Speter int max_code; /* and its largest code of non zero frequency */ 251128415Speter{ 251228415Speter int n; /* iterates over all tree elements */ 251328415Speter int prevlen = -1; /* last emitted length */ 251428415Speter int curlen; /* length of current code */ 251528415Speter int nextlen = tree[0].Len; /* length of next code */ 251628415Speter int count = 0; /* repeat count of the current code */ 251728415Speter int max_count = 7; /* max repeat count */ 251828415Speter int min_count = 4; /* min repeat count */ 251928415Speter 252028415Speter /* tree[max_code+1].Len = -1; */ /* guard already set */ 252128415Speter if (nextlen == 0) max_count = 138, min_count = 3; 252228415Speter 252328415Speter for (n = 0; n <= max_code; n++) { 252428415Speter curlen = nextlen; nextlen = tree[n+1].Len; 252528415Speter if (++count < max_count && curlen == nextlen) { 252628415Speter continue; 252728415Speter } else if (count < min_count) { 252828415Speter do { send_code(s, curlen, s->bl_tree); } while (--count != 0); 252928415Speter 253028415Speter } else if (curlen != 0) { 253128415Speter if (curlen != prevlen) { 253228415Speter send_code(s, curlen, s->bl_tree); count--; 253328415Speter } 253428415Speter Assert(count >= 3 && count <= 6, " 3_6?"); 253528415Speter send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); 253628415Speter 253728415Speter } else if (count <= 10) { 253828415Speter send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); 253928415Speter 254028415Speter } else { 254128415Speter send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); 254228415Speter } 254328415Speter count = 0; prevlen = curlen; 254428415Speter if (nextlen == 0) { 254528415Speter max_count = 138, min_count = 3; 254628415Speter } else if (curlen == nextlen) { 254728415Speter max_count = 6, min_count = 3; 254828415Speter } else { 254928415Speter max_count = 7, min_count = 4; 255028415Speter } 255128415Speter } 255228415Speter} 255328415Speter 255428415Speter/* =========================================================================== 255528415Speter * Construct the Huffman tree for the bit lengths and return the index in 255628415Speter * bl_order of the last bit length code to send. 255728415Speter */ 255828415Speterlocal int build_bl_tree(s) 255928415Speter deflate_state *s; 256028415Speter{ 256128415Speter int max_blindex; /* index of last bit length code of non zero freq */ 256228415Speter 256328415Speter /* Determine the bit length frequencies for literal and distance trees */ 256428415Speter scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); 256528415Speter scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); 256628415Speter 256728415Speter /* Build the bit length tree: */ 256828415Speter build_tree(s, (tree_desc *)(&(s->bl_desc))); 256928415Speter /* opt_len now includes the length of the tree representations, except 257028415Speter * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 257128415Speter */ 257228415Speter 257328415Speter /* Determine the number of bit length codes to send. The pkzip format 257428415Speter * requires that at least 4 bit length codes be sent. (appnote.txt says 257528415Speter * 3 but the actual value used is 4.) 257628415Speter */ 257728415Speter for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 257828415Speter if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; 257928415Speter } 258028415Speter /* Update opt_len to include the bit length tree and counts */ 258128415Speter s->opt_len += 3*(max_blindex+1) + 5+5+4; 258228415Speter Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", 258328415Speter s->opt_len, s->static_len)); 258428415Speter 258528415Speter return max_blindex; 258628415Speter} 258728415Speter 258828415Speter/* =========================================================================== 258928415Speter * Send the header for a block using dynamic Huffman trees: the counts, the 259028415Speter * lengths of the bit length codes, the literal tree and the distance tree. 259128415Speter * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 259228415Speter */ 259328415Speterlocal void send_all_trees(s, lcodes, dcodes, blcodes) 259428415Speter deflate_state *s; 259528415Speter int lcodes, dcodes, blcodes; /* number of codes for each tree */ 259628415Speter{ 259728415Speter int rank; /* index in bl_order */ 259828415Speter 259928415Speter Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); 260028415Speter Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 260128415Speter "too many codes"); 260228415Speter Tracev((stderr, "\nbl counts: ")); 260328415Speter send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ 260428415Speter send_bits(s, dcodes-1, 5); 260528415Speter send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ 260628415Speter for (rank = 0; rank < blcodes; rank++) { 260728415Speter Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 260828415Speter send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); 260928415Speter } 261028415Speter Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); 261128415Speter 261228415Speter send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ 261328415Speter Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); 261428415Speter 261528415Speter send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ 261628415Speter Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); 261728415Speter} 261828415Speter 261928415Speter/* =========================================================================== 262028415Speter * Send a stored block 262128415Speter */ 262234768Spetervoid _tr_stored_block(s, buf, stored_len, eof) 262328415Speter deflate_state *s; 262428415Speter charf *buf; /* input block */ 262528415Speter ulg stored_len; /* length of input block */ 262628415Speter int eof; /* true if this is the last block for a file */ 262728415Speter{ 262828415Speter send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ 262934768Speter s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; 263028415Speter s->compressed_len += (stored_len + 4) << 3; 263128415Speter 263228415Speter copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ 263328415Speter} 263428415Speter 263528415Speter/* Send just the `stored block' type code without any length bytes or data. 263628415Speter */ 263734768Spetervoid _tr_stored_type_only(s) 263828415Speter deflate_state *s; 263928415Speter{ 264028415Speter send_bits(s, (STORED_BLOCK << 1), 3); 264128415Speter bi_windup(s); 264228415Speter s->compressed_len = (s->compressed_len + 3) & ~7L; 264328415Speter} 264428415Speter 264528415Speter 264628415Speter/* =========================================================================== 264728415Speter * Send one empty static block to give enough lookahead for inflate. 264828415Speter * This takes 10 bits, of which 7 may remain in the bit buffer. 264934768Speter * The current inflate code requires 9 bits of lookahead. If the 265034768Speter * last two codes for the previous block (real code plus EOB) were coded 265134768Speter * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode 265234768Speter * the last real code. In this case we send two empty static blocks instead 265334768Speter * of one. (There are no problems if the previous block is stored or fixed.) 265434768Speter * To simplify the code, we assume the worst case of last real code encoded 265534768Speter * on one bit only. 265628415Speter */ 265734768Spetervoid _tr_align(s) 265828415Speter deflate_state *s; 265928415Speter{ 266028415Speter send_bits(s, STATIC_TREES<<1, 3); 266128415Speter send_code(s, END_BLOCK, static_ltree); 266228415Speter s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ 266328415Speter bi_flush(s); 266428415Speter /* Of the 10 bits for the empty block, we have already sent 266534768Speter * (10 - bi_valid) bits. The lookahead for the last real code (before 266634768Speter * the EOB of the previous block) was thus at least one plus the length 266734768Speter * of the EOB plus what we have just sent of the empty static block. 266828415Speter */ 266934768Speter if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { 267028415Speter send_bits(s, STATIC_TREES<<1, 3); 267128415Speter send_code(s, END_BLOCK, static_ltree); 267228415Speter s->compressed_len += 10L; 267328415Speter bi_flush(s); 267428415Speter } 267528415Speter s->last_eob_len = 7; 267628415Speter} 267728415Speter 267828415Speter/* =========================================================================== 267928415Speter * Determine the best encoding for the current block: dynamic trees, static 268028415Speter * trees or store, and output the encoded block to the zip file. This function 268128415Speter * returns the total compressed length for the file so far. 268228415Speter */ 268334768Speterulg _tr_flush_block(s, buf, stored_len, eof) 268428415Speter deflate_state *s; 268528415Speter charf *buf; /* input block, or NULL if too old */ 268628415Speter ulg stored_len; /* length of input block */ 268734768Speter int eof; /* true if this is the last block for a file */ 268828415Speter{ 268928415Speter ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 269034768Speter int max_blindex = 0; /* index of last bit length code of non zero freq */ 269128415Speter 269234768Speter /* Build the Huffman trees unless a stored block is forced */ 269334768Speter if (s->level > 0) { 269428415Speter 269534768Speter /* Check if the file is ascii or binary */ 269634768Speter if (s->data_type == Z_UNKNOWN) set_data_type(s); 269728415Speter 269834768Speter /* Construct the literal and distance trees */ 269934768Speter build_tree(s, (tree_desc *)(&(s->l_desc))); 270034768Speter Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, 270134768Speter s->static_len)); 270228415Speter 270334768Speter build_tree(s, (tree_desc *)(&(s->d_desc))); 270434768Speter Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, 270534768Speter s->static_len)); 270634768Speter /* At this point, opt_len and static_len are the total bit lengths of 270734768Speter * the compressed block data, excluding the tree representations. 270834768Speter */ 270928415Speter 271034768Speter /* Build the bit length tree for the above two trees, and get the index 271134768Speter * in bl_order of the last bit length code to send. 271234768Speter */ 271334768Speter max_blindex = build_bl_tree(s); 271428415Speter 271534768Speter /* Determine the best encoding. Compute first the block length in bytes*/ 271634768Speter opt_lenb = (s->opt_len+3+7)>>3; 271734768Speter static_lenb = (s->static_len+3+7)>>3; 271828415Speter 271934768Speter Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 272034768Speter opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 272134768Speter s->last_lit)); 272228415Speter 272334768Speter if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 272428415Speter 272534768Speter } else { 272634768Speter Assert(buf != (char*)0, "lost buf"); 272734768Speter opt_lenb = static_lenb = stored_len + 5; /* force a stored block */ 272834768Speter } 272934768Speter 273028415Speter /* If compression failed and this is the first and last block, 273128415Speter * and if the .zip file can be seeked (to rewrite the local header), 273228415Speter * the whole file is transformed into a stored file: 273328415Speter */ 273428415Speter#ifdef STORED_FILE_OK 273528415Speter# ifdef FORCE_STORED_FILE 273634768Speter if (eof && s->compressed_len == 0L) { /* force stored file */ 273728415Speter# else 273834768Speter if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) { 273928415Speter# endif 274028415Speter /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ 274128415Speter if (buf == (charf*)0) error ("block vanished"); 274228415Speter 274334768Speter copy_block(s, buf, (unsigned)stored_len, 0); /* without header */ 274428415Speter s->compressed_len = stored_len << 3; 274528415Speter s->method = STORED; 274628415Speter } else 274728415Speter#endif /* STORED_FILE_OK */ 274828415Speter 274928415Speter#ifdef FORCE_STORED 275034768Speter if (buf != (char*)0) { /* force stored block */ 275128415Speter#else 275234768Speter if (stored_len+4 <= opt_lenb && buf != (char*)0) { 275328415Speter /* 4: two words for the lengths */ 275428415Speter#endif 275528415Speter /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 275628415Speter * Otherwise we can't have processed more than WSIZE input bytes since 275728415Speter * the last block flush, because compression would have been 275828415Speter * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 275928415Speter * transform a block into a stored block. 276028415Speter */ 276134768Speter _tr_stored_block(s, buf, stored_len, eof); 276228415Speter 276328415Speter#ifdef FORCE_STATIC 276434768Speter } else if (static_lenb >= 0) { /* force static trees */ 276528415Speter#else 276634768Speter } else if (static_lenb == opt_lenb) { 276728415Speter#endif 276828415Speter send_bits(s, (STATIC_TREES<<1)+eof, 3); 276928415Speter compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); 277028415Speter s->compressed_len += 3 + s->static_len; 277128415Speter } else { 277228415Speter send_bits(s, (DYN_TREES<<1)+eof, 3); 277328415Speter send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, 277428415Speter max_blindex+1); 277528415Speter compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); 277628415Speter s->compressed_len += 3 + s->opt_len; 277728415Speter } 277828415Speter Assert (s->compressed_len == s->bits_sent, "bad compressed size"); 277928415Speter init_block(s); 278028415Speter 278128415Speter if (eof) { 278228415Speter bi_windup(s); 278328415Speter s->compressed_len += 7; /* align on byte boundary */ 278428415Speter } 278528415Speter Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, 278628415Speter s->compressed_len-7*eof)); 278728415Speter 278828415Speter return s->compressed_len >> 3; 278928415Speter} 279028415Speter 279128415Speter/* =========================================================================== 279228415Speter * Save the match info and tally the frequency counts. Return true if 279328415Speter * the current block must be flushed. 279428415Speter */ 279534768Speterint _tr_tally (s, dist, lc) 279628415Speter deflate_state *s; 279734768Speter unsigned dist; /* distance of matched string */ 279834768Speter unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ 279928415Speter{ 280028415Speter s->d_buf[s->last_lit] = (ush)dist; 280128415Speter s->l_buf[s->last_lit++] = (uch)lc; 280228415Speter if (dist == 0) { 280328415Speter /* lc is the unmatched char */ 280428415Speter s->dyn_ltree[lc].Freq++; 280528415Speter } else { 280628415Speter s->matches++; 280728415Speter /* Here, lc is the match length - MIN_MATCH */ 280828415Speter dist--; /* dist = match distance - 1 */ 280928415Speter Assert((ush)dist < (ush)MAX_DIST(s) && 281028415Speter (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 281134768Speter (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match"); 281228415Speter 281328415Speter s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++; 281428415Speter s->dyn_dtree[d_code(dist)].Freq++; 281528415Speter } 281628415Speter 281728415Speter /* Try to guess if it is profitable to stop the current block here */ 281828415Speter if (s->level > 2 && (s->last_lit & 0xfff) == 0) { 281928415Speter /* Compute an upper bound for the compressed length */ 282028415Speter ulg out_length = (ulg)s->last_lit*8L; 282134768Speter ulg in_length = (ulg)((long)s->strstart - s->block_start); 282228415Speter int dcode; 282328415Speter for (dcode = 0; dcode < D_CODES; dcode++) { 282428415Speter out_length += (ulg)s->dyn_dtree[dcode].Freq * 282528415Speter (5L+extra_dbits[dcode]); 282628415Speter } 282728415Speter out_length >>= 3; 282828415Speter Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", 282928415Speter s->last_lit, in_length, out_length, 283028415Speter 100L - out_length*100L/in_length)); 283128415Speter if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; 283228415Speter } 283328415Speter return (s->last_lit == s->lit_bufsize-1); 283428415Speter /* We avoid equality with lit_bufsize because of wraparound at 64K 283528415Speter * on 16 bit machines and because stored blocks are restricted to 283628415Speter * 64K-1 bytes. 283728415Speter */ 283828415Speter} 283928415Speter 284028415Speter/* =========================================================================== 284128415Speter * Send the block data compressed using the given Huffman trees 284228415Speter */ 284328415Speterlocal void compress_block(s, ltree, dtree) 284428415Speter deflate_state *s; 284528415Speter ct_data *ltree; /* literal tree */ 284628415Speter ct_data *dtree; /* distance tree */ 284728415Speter{ 284828415Speter unsigned dist; /* distance of matched string */ 284928415Speter int lc; /* match length or unmatched char (if dist == 0) */ 285028415Speter unsigned lx = 0; /* running index in l_buf */ 285128415Speter unsigned code; /* the code to send */ 285228415Speter int extra; /* number of extra bits to send */ 285328415Speter 285428415Speter if (s->last_lit != 0) do { 285528415Speter dist = s->d_buf[lx]; 285628415Speter lc = s->l_buf[lx++]; 285728415Speter if (dist == 0) { 285828415Speter send_code(s, lc, ltree); /* send a literal byte */ 285928415Speter Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 286028415Speter } else { 286128415Speter /* Here, lc is the match length - MIN_MATCH */ 286228415Speter code = length_code[lc]; 286328415Speter send_code(s, code+LITERALS+1, ltree); /* send the length code */ 286428415Speter extra = extra_lbits[code]; 286528415Speter if (extra != 0) { 286628415Speter lc -= base_length[code]; 286728415Speter send_bits(s, lc, extra); /* send the extra length bits */ 286828415Speter } 286928415Speter dist--; /* dist is now the match distance - 1 */ 287028415Speter code = d_code(dist); 287128415Speter Assert (code < D_CODES, "bad d_code"); 287228415Speter 287328415Speter send_code(s, code, dtree); /* send the distance code */ 287428415Speter extra = extra_dbits[code]; 287528415Speter if (extra != 0) { 287628415Speter dist -= base_dist[code]; 287728415Speter send_bits(s, dist, extra); /* send the extra distance bits */ 287828415Speter } 287928415Speter } /* literal or match pair ? */ 288028415Speter 288128415Speter /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 288228415Speter Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow"); 288328415Speter 288428415Speter } while (lx < s->last_lit); 288528415Speter 288628415Speter send_code(s, END_BLOCK, ltree); 288728415Speter s->last_eob_len = ltree[END_BLOCK].Len; 288828415Speter} 288928415Speter 289028415Speter/* =========================================================================== 289134768Speter * Set the data type to ASCII or BINARY, using a crude approximation: 289228415Speter * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. 289328415Speter * IN assertion: the fields freq of dyn_ltree are set and the total of all 289428415Speter * frequencies does not exceed 64K (to fit in an int on 16 bit machines). 289528415Speter */ 289628415Speterlocal void set_data_type(s) 289728415Speter deflate_state *s; 289828415Speter{ 289928415Speter int n = 0; 290028415Speter unsigned ascii_freq = 0; 290128415Speter unsigned bin_freq = 0; 290228415Speter while (n < 7) bin_freq += s->dyn_ltree[n++].Freq; 290328415Speter while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq; 290428415Speter while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq; 290534768Speter s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII); 290628415Speter} 290728415Speter 290828415Speter/* =========================================================================== 290928415Speter * Reverse the first len bits of a code, using straightforward code (a faster 291028415Speter * method would use a table) 291128415Speter * IN assertion: 1 <= len <= 15 291228415Speter */ 291328415Speterlocal unsigned bi_reverse(code, len) 291428415Speter unsigned code; /* the value to invert */ 291528415Speter int len; /* its bit length */ 291628415Speter{ 291728415Speter register unsigned res = 0; 291828415Speter do { 291928415Speter res |= code & 1; 292028415Speter code >>= 1, res <<= 1; 292128415Speter } while (--len > 0); 292228415Speter return res >> 1; 292328415Speter} 292428415Speter 292528415Speter/* =========================================================================== 292628415Speter * Flush the bit buffer, keeping at most 7 bits in it. 292728415Speter */ 292828415Speterlocal void bi_flush(s) 292928415Speter deflate_state *s; 293028415Speter{ 293128415Speter if (s->bi_valid == 16) { 293228415Speter put_short(s, s->bi_buf); 293328415Speter s->bi_buf = 0; 293428415Speter s->bi_valid = 0; 293528415Speter } else if (s->bi_valid >= 8) { 293628415Speter put_byte(s, (Byte)s->bi_buf); 293728415Speter s->bi_buf >>= 8; 293828415Speter s->bi_valid -= 8; 293928415Speter } 294028415Speter} 294128415Speter 294228415Speter/* =========================================================================== 294328415Speter * Flush the bit buffer and align the output on a byte boundary 294428415Speter */ 294528415Speterlocal void bi_windup(s) 294628415Speter deflate_state *s; 294728415Speter{ 294828415Speter if (s->bi_valid > 8) { 294928415Speter put_short(s, s->bi_buf); 295028415Speter } else if (s->bi_valid > 0) { 295128415Speter put_byte(s, (Byte)s->bi_buf); 295228415Speter } 295328415Speter s->bi_buf = 0; 295428415Speter s->bi_valid = 0; 295528415Speter#ifdef DEBUG_ZLIB 295628415Speter s->bits_sent = (s->bits_sent+7) & ~7; 295728415Speter#endif 295828415Speter} 295928415Speter 296028415Speter/* =========================================================================== 296128415Speter * Copy a stored block, storing first the length and its 296228415Speter * one's complement if requested. 296328415Speter */ 296428415Speterlocal void copy_block(s, buf, len, header) 296528415Speter deflate_state *s; 296628415Speter charf *buf; /* the input data */ 296728415Speter unsigned len; /* its length */ 296828415Speter int header; /* true if block header must be written */ 296928415Speter{ 297028415Speter bi_windup(s); /* align on byte boundary */ 297128415Speter s->last_eob_len = 8; /* enough lookahead for inflate */ 297228415Speter 297328415Speter if (header) { 297428415Speter put_short(s, (ush)len); 297528415Speter put_short(s, (ush)~len); 297628415Speter#ifdef DEBUG_ZLIB 297728415Speter s->bits_sent += 2*16; 297828415Speter#endif 297928415Speter } 298028415Speter#ifdef DEBUG_ZLIB 298128415Speter s->bits_sent += (ulg)len<<3; 298228415Speter#endif 298334768Speter /* bundle up the put_byte(s, *buf++) calls */ 298434768Speter zmemcpy(&s->pending_buf[s->pending], buf, len); 298534768Speter s->pending += len; 298628415Speter} 298734768Speter/* --- trees.c */ 298828415Speter 298934768Speter/* +++ inflate.c */ 299034768Speter/* inflate.c -- zlib interface to inflate modules 299134768Speter * Copyright (C) 1995-1996 Mark Adler 299234768Speter * For conditions of distribution and use, see copyright notice in zlib.h 299334768Speter */ 299428415Speter 299534768Speter/* #include "zutil.h" */ 299634768Speter 299734768Speter/* +++ infblock.h */ 299828415Speter/* infblock.h -- header to use infblock.c 299934768Speter * Copyright (C) 1995-1996 Mark Adler 300028415Speter * For conditions of distribution and use, see copyright notice in zlib.h 300128415Speter */ 300228415Speter 300328415Speter/* WARNING: this file should *not* be used by applications. It is 300428415Speter part of the implementation of the compression library and is 300528415Speter subject to change. Applications should only use zlib.h. 300628415Speter */ 300728415Speter 300828415Speterstruct inflate_blocks_state; 300928415Spetertypedef struct inflate_blocks_state FAR inflate_blocks_statef; 301028415Speter 301134768Speterextern inflate_blocks_statef * inflate_blocks_new OF(( 301234768Speter z_streamp z, 301328415Speter check_func c, /* check function */ 301428415Speter uInt w)); /* window size */ 301528415Speter 301634768Speterextern int inflate_blocks OF(( 301728415Speter inflate_blocks_statef *, 301834768Speter z_streamp , 301928415Speter int)); /* initial return code */ 302028415Speter 302134768Speterextern void inflate_blocks_reset OF(( 302228415Speter inflate_blocks_statef *, 302334768Speter z_streamp , 302428415Speter uLongf *)); /* check value on output */ 302528415Speter 302634768Speterextern int inflate_blocks_free OF(( 302728415Speter inflate_blocks_statef *, 302834768Speter z_streamp , 302928415Speter uLongf *)); /* check value on output */ 303028415Speter 303134768Speterextern void inflate_set_dictionary OF(( 303234768Speter inflate_blocks_statef *s, 303334768Speter const Bytef *d, /* dictionary */ 303434768Speter uInt n)); /* dictionary length */ 303534768Speter 303634768Speterextern int inflate_addhistory OF(( 303728415Speter inflate_blocks_statef *, 303834768Speter z_streamp)); 303928415Speter 304034768Speterextern int inflate_packet_flush OF(( 304128415Speter inflate_blocks_statef *)); 304234768Speter/* --- infblock.h */ 304328415Speter 304434768Speter#ifndef NO_DUMMY_DECL 304534768Speterstruct inflate_blocks_state {int dummy;}; /* for buggy compilers */ 304628415Speter#endif 304728415Speter 304828415Speter/* inflate private state */ 304928415Speterstruct internal_state { 305028415Speter 305128415Speter /* mode */ 305228415Speter enum { 305328415Speter METHOD, /* waiting for method byte */ 305428415Speter FLAG, /* waiting for flag byte */ 305534768Speter DICT4, /* four dictionary check bytes to go */ 305634768Speter DICT3, /* three dictionary check bytes to go */ 305734768Speter DICT2, /* two dictionary check bytes to go */ 305834768Speter DICT1, /* one dictionary check byte to go */ 305934768Speter DICT0, /* waiting for inflateSetDictionary */ 306028415Speter BLOCKS, /* decompressing blocks */ 306128415Speter CHECK4, /* four check bytes to go */ 306228415Speter CHECK3, /* three check bytes to go */ 306328415Speter CHECK2, /* two check bytes to go */ 306428415Speter CHECK1, /* one check byte to go */ 306528415Speter DONE, /* finished check, done */ 306628415Speter BAD} /* got an error--stay here */ 306728415Speter mode; /* current inflate mode */ 306828415Speter 306928415Speter /* mode dependent information */ 307028415Speter union { 307128415Speter uInt method; /* if FLAGS, method byte */ 307228415Speter struct { 307328415Speter uLong was; /* computed check value */ 307428415Speter uLong need; /* stream check value */ 307528415Speter } check; /* if CHECK, check values to compare */ 307628415Speter uInt marker; /* if BAD, inflateSync's marker bytes count */ 307728415Speter } sub; /* submode */ 307828415Speter 307928415Speter /* mode independent information */ 308028415Speter int nowrap; /* flag for no wrapper */ 308128415Speter uInt wbits; /* log2(window size) (8..15, defaults to 15) */ 308228415Speter inflate_blocks_statef 308328415Speter *blocks; /* current inflate_blocks state */ 308428415Speter 308528415Speter}; 308628415Speter 308728415Speter 308828415Speterint inflateReset(z) 308934768Speterz_streamp z; 309028415Speter{ 309128415Speter uLong c; 309228415Speter 309328415Speter if (z == Z_NULL || z->state == Z_NULL) 309428415Speter return Z_STREAM_ERROR; 309528415Speter z->total_in = z->total_out = 0; 309628415Speter z->msg = Z_NULL; 309728415Speter z->state->mode = z->state->nowrap ? BLOCKS : METHOD; 309828415Speter inflate_blocks_reset(z->state->blocks, z, &c); 309928415Speter Trace((stderr, "inflate: reset\n")); 310028415Speter return Z_OK; 310128415Speter} 310228415Speter 310328415Speter 310428415Speterint inflateEnd(z) 310534768Speterz_streamp z; 310628415Speter{ 310728415Speter uLong c; 310828415Speter 310928415Speter if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL) 311028415Speter return Z_STREAM_ERROR; 311128415Speter if (z->state->blocks != Z_NULL) 311228415Speter inflate_blocks_free(z->state->blocks, z, &c); 311334768Speter ZFREE(z, z->state); 311428415Speter z->state = Z_NULL; 311528415Speter Trace((stderr, "inflate: end\n")); 311628415Speter return Z_OK; 311728415Speter} 311828415Speter 311928415Speter 312034768Speterint inflateInit2_(z, w, version, stream_size) 312134768Speterz_streamp z; 312228415Speterint w; 312334768Speterconst char *version; 312434768Speterint stream_size; 312528415Speter{ 312634768Speter if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 312734768Speter stream_size != sizeof(z_stream)) 312834768Speter return Z_VERSION_ERROR; 312934768Speter 313028415Speter /* initialize state */ 313128415Speter if (z == Z_NULL) 313228415Speter return Z_STREAM_ERROR; 313334768Speter z->msg = Z_NULL; 313434768Speter#ifndef NO_ZCFUNCS 313534768Speter if (z->zalloc == Z_NULL) 313634768Speter { 313734768Speter z->zalloc = zcalloc; 313834768Speter z->opaque = (voidpf)0; 313934768Speter } 314034768Speter if (z->zfree == Z_NULL) z->zfree = zcfree; 314134768Speter#endif 314228415Speter if ((z->state = (struct internal_state FAR *) 314334768Speter ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL) 314428415Speter return Z_MEM_ERROR; 314528415Speter z->state->blocks = Z_NULL; 314628415Speter 314728415Speter /* handle undocumented nowrap option (no zlib header or check) */ 314828415Speter z->state->nowrap = 0; 314928415Speter if (w < 0) 315028415Speter { 315128415Speter w = - w; 315228415Speter z->state->nowrap = 1; 315328415Speter } 315428415Speter 315528415Speter /* set window size */ 315628415Speter if (w < 8 || w > 15) 315728415Speter { 315828415Speter inflateEnd(z); 315928415Speter return Z_STREAM_ERROR; 316028415Speter } 316128415Speter z->state->wbits = (uInt)w; 316228415Speter 316328415Speter /* create inflate_blocks state */ 316428415Speter if ((z->state->blocks = 316534768Speter inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, (uInt)1 << w)) 316628415Speter == Z_NULL) 316728415Speter { 316828415Speter inflateEnd(z); 316928415Speter return Z_MEM_ERROR; 317028415Speter } 317128415Speter Trace((stderr, "inflate: allocated\n")); 317228415Speter 317328415Speter /* reset state */ 317428415Speter inflateReset(z); 317528415Speter return Z_OK; 317628415Speter} 317728415Speter 317828415Speter 317934768Speterint inflateInit_(z, version, stream_size) 318034768Speterz_streamp z; 318134768Speterconst char *version; 318234768Speterint stream_size; 318328415Speter{ 318434768Speter return inflateInit2_(z, DEF_WBITS, version, stream_size); 318528415Speter} 318628415Speter 318728415Speter 318828415Speter#define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;} 318928415Speter#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++) 319028415Speter 319128415Speterint inflate(z, f) 319234768Speterz_streamp z; 319328415Speterint f; 319428415Speter{ 319528415Speter int r; 319628415Speter uInt b; 319728415Speter 319834768Speter if (z == Z_NULL || z->state == Z_NULL || z->next_in == Z_NULL || f < 0) 319928415Speter return Z_STREAM_ERROR; 320028415Speter r = Z_BUF_ERROR; 320128415Speter while (1) switch (z->state->mode) 320228415Speter { 320328415Speter case METHOD: 320428415Speter NEEDBYTE 320534768Speter if (((z->state->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED) 320628415Speter { 320728415Speter z->state->mode = BAD; 320834768Speter z->msg = (char*)"unknown compression method"; 320928415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 321028415Speter break; 321128415Speter } 321228415Speter if ((z->state->sub.method >> 4) + 8 > z->state->wbits) 321328415Speter { 321428415Speter z->state->mode = BAD; 321534768Speter z->msg = (char*)"invalid window size"; 321628415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 321728415Speter break; 321828415Speter } 321928415Speter z->state->mode = FLAG; 322028415Speter case FLAG: 322128415Speter NEEDBYTE 322234768Speter b = NEXTBYTE; 322334768Speter if (((z->state->sub.method << 8) + b) % 31) 322428415Speter { 322528415Speter z->state->mode = BAD; 322634768Speter z->msg = (char*)"incorrect header check"; 322728415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 322828415Speter break; 322928415Speter } 323034768Speter Trace((stderr, "inflate: zlib header ok\n")); 323134768Speter if (!(b & PRESET_DICT)) 323228415Speter { 323334768Speter z->state->mode = BLOCKS; 323434768Speter break; 323528415Speter } 323634768Speter z->state->mode = DICT4; 323734768Speter case DICT4: 323834768Speter NEEDBYTE 323934768Speter z->state->sub.check.need = (uLong)NEXTBYTE << 24; 324034768Speter z->state->mode = DICT3; 324134768Speter case DICT3: 324234768Speter NEEDBYTE 324334768Speter z->state->sub.check.need += (uLong)NEXTBYTE << 16; 324434768Speter z->state->mode = DICT2; 324534768Speter case DICT2: 324634768Speter NEEDBYTE 324734768Speter z->state->sub.check.need += (uLong)NEXTBYTE << 8; 324834768Speter z->state->mode = DICT1; 324934768Speter case DICT1: 325034768Speter NEEDBYTE 325134768Speter z->state->sub.check.need += (uLong)NEXTBYTE; 325234768Speter z->adler = z->state->sub.check.need; 325334768Speter z->state->mode = DICT0; 325434768Speter return Z_NEED_DICT; 325534768Speter case DICT0: 325634768Speter z->state->mode = BAD; 325734768Speter z->msg = (char*)"need dictionary"; 325834768Speter z->state->sub.marker = 0; /* can try inflateSync */ 325934768Speter return Z_STREAM_ERROR; 326028415Speter case BLOCKS: 326128415Speter r = inflate_blocks(z->state->blocks, z, r); 326228415Speter if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0) 326328415Speter r = inflate_packet_flush(z->state->blocks); 326428415Speter if (r == Z_DATA_ERROR) 326528415Speter { 326628415Speter z->state->mode = BAD; 326728415Speter z->state->sub.marker = 0; /* can try inflateSync */ 326828415Speter break; 326928415Speter } 327028415Speter if (r != Z_STREAM_END) 327128415Speter return r; 327228415Speter r = Z_OK; 327328415Speter inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was); 327428415Speter if (z->state->nowrap) 327528415Speter { 327628415Speter z->state->mode = DONE; 327728415Speter break; 327828415Speter } 327928415Speter z->state->mode = CHECK4; 328028415Speter case CHECK4: 328128415Speter NEEDBYTE 328228415Speter z->state->sub.check.need = (uLong)NEXTBYTE << 24; 328328415Speter z->state->mode = CHECK3; 328428415Speter case CHECK3: 328528415Speter NEEDBYTE 328628415Speter z->state->sub.check.need += (uLong)NEXTBYTE << 16; 328728415Speter z->state->mode = CHECK2; 328828415Speter case CHECK2: 328928415Speter NEEDBYTE 329028415Speter z->state->sub.check.need += (uLong)NEXTBYTE << 8; 329128415Speter z->state->mode = CHECK1; 329228415Speter case CHECK1: 329328415Speter NEEDBYTE 329428415Speter z->state->sub.check.need += (uLong)NEXTBYTE; 329528415Speter 329628415Speter if (z->state->sub.check.was != z->state->sub.check.need) 329728415Speter { 329828415Speter z->state->mode = BAD; 329934768Speter z->msg = (char*)"incorrect data check"; 330028415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 330128415Speter break; 330228415Speter } 330328415Speter Trace((stderr, "inflate: zlib check ok\n")); 330428415Speter z->state->mode = DONE; 330528415Speter case DONE: 330628415Speter return Z_STREAM_END; 330728415Speter case BAD: 330828415Speter return Z_DATA_ERROR; 330928415Speter default: 331028415Speter return Z_STREAM_ERROR; 331128415Speter } 331228415Speter 331328415Speter empty: 331428415Speter if (f != Z_PACKET_FLUSH) 331528415Speter return r; 331628415Speter z->state->mode = BAD; 331734768Speter z->msg = (char *)"need more for packet flush"; 331828415Speter z->state->sub.marker = 0; /* can try inflateSync */ 331928415Speter return Z_DATA_ERROR; 332028415Speter} 332128415Speter 332234768Speter 332334768Speterint inflateSetDictionary(z, dictionary, dictLength) 332434768Speterz_streamp z; 332534768Speterconst Bytef *dictionary; 332634768SpeteruInt dictLength; 332734768Speter{ 332834768Speter uInt length = dictLength; 332934768Speter 333034768Speter if (z == Z_NULL || z->state == Z_NULL || z->state->mode != DICT0) 333134768Speter return Z_STREAM_ERROR; 333234768Speter 333334768Speter if (adler32(1L, dictionary, dictLength) != z->adler) return Z_DATA_ERROR; 333434768Speter z->adler = 1L; 333534768Speter 333634768Speter if (length >= ((uInt)1<<z->state->wbits)) 333734768Speter { 333834768Speter length = (1<<z->state->wbits)-1; 333934768Speter dictionary += dictLength - length; 334034768Speter } 334134768Speter inflate_set_dictionary(z->state->blocks, dictionary, length); 334234768Speter z->state->mode = BLOCKS; 334334768Speter return Z_OK; 334434768Speter} 334534768Speter 334628415Speter/* 334728415Speter * This subroutine adds the data at next_in/avail_in to the output history 334828415Speter * without performing any output. The output buffer must be "caught up"; 334928415Speter * i.e. no pending output (hence s->read equals s->write), and the state must 335028415Speter * be BLOCKS (i.e. we should be willing to see the start of a series of 335128415Speter * BLOCKS). On exit, the output will also be caught up, and the checksum 335228415Speter * will have been updated if need be. 335328415Speter */ 335428415Speter 335528415Speterint inflateIncomp(z) 335628415Speterz_stream *z; 335728415Speter{ 335828415Speter if (z->state->mode != BLOCKS) 335928415Speter return Z_DATA_ERROR; 336028415Speter return inflate_addhistory(z->state->blocks, z); 336128415Speter} 336228415Speter 336328415Speter 336428415Speterint inflateSync(z) 336534768Speterz_streamp z; 336628415Speter{ 336728415Speter uInt n; /* number of bytes to look at */ 336828415Speter Bytef *p; /* pointer to bytes */ 336928415Speter uInt m; /* number of marker bytes found in a row */ 337028415Speter uLong r, w; /* temporaries to save total_in and total_out */ 337128415Speter 337228415Speter /* set up */ 337328415Speter if (z == Z_NULL || z->state == Z_NULL) 337428415Speter return Z_STREAM_ERROR; 337528415Speter if (z->state->mode != BAD) 337628415Speter { 337728415Speter z->state->mode = BAD; 337828415Speter z->state->sub.marker = 0; 337928415Speter } 338028415Speter if ((n = z->avail_in) == 0) 338128415Speter return Z_BUF_ERROR; 338228415Speter p = z->next_in; 338328415Speter m = z->state->sub.marker; 338428415Speter 338528415Speter /* search */ 338628415Speter while (n && m < 4) 338728415Speter { 338828415Speter if (*p == (Byte)(m < 2 ? 0 : 0xff)) 338928415Speter m++; 339028415Speter else if (*p) 339128415Speter m = 0; 339228415Speter else 339328415Speter m = 4 - m; 339428415Speter p++, n--; 339528415Speter } 339628415Speter 339728415Speter /* restore */ 339828415Speter z->total_in += p - z->next_in; 339928415Speter z->next_in = p; 340028415Speter z->avail_in = n; 340128415Speter z->state->sub.marker = m; 340228415Speter 340328415Speter /* return no joy or set up to restart on a new block */ 340428415Speter if (m != 4) 340528415Speter return Z_DATA_ERROR; 340628415Speter r = z->total_in; w = z->total_out; 340728415Speter inflateReset(z); 340828415Speter z->total_in = r; z->total_out = w; 340928415Speter z->state->mode = BLOCKS; 341028415Speter return Z_OK; 341128415Speter} 341228415Speter 341328415Speter#undef NEEDBYTE 341428415Speter#undef NEXTBYTE 341534768Speter/* --- inflate.c */ 341628415Speter 341734768Speter/* +++ infblock.c */ 341834768Speter/* infblock.c -- interpret and process block types to last block 341934768Speter * Copyright (C) 1995-1996 Mark Adler 342034768Speter * For conditions of distribution and use, see copyright notice in zlib.h 342134768Speter */ 342234768Speter 342334768Speter/* #include "zutil.h" */ 342434768Speter/* #include "infblock.h" */ 342534768Speter 342634768Speter/* +++ inftrees.h */ 342734768Speter/* inftrees.h -- header to use inftrees.c 342834768Speter * Copyright (C) 1995-1996 Mark Adler 342934768Speter * For conditions of distribution and use, see copyright notice in zlib.h 343034768Speter */ 343134768Speter 343234768Speter/* WARNING: this file should *not* be used by applications. It is 343334768Speter part of the implementation of the compression library and is 343434768Speter subject to change. Applications should only use zlib.h. 343534768Speter */ 343634768Speter 343734768Speter/* Huffman code lookup table entry--this entry is four bytes for machines 343834768Speter that have 16-bit pointers (e.g. PC's in the small or medium model). */ 343934768Speter 344034768Spetertypedef struct inflate_huft_s FAR inflate_huft; 344134768Speter 344234768Speterstruct inflate_huft_s { 344334768Speter union { 344434768Speter struct { 344534768Speter Byte Exop; /* number of extra bits or operation */ 344634768Speter Byte Bits; /* number of bits in this code or subcode */ 344734768Speter } what; 344834768Speter Bytef *pad; /* pad structure to a power of 2 (4 bytes for */ 344934768Speter } word; /* 16-bit, 8 bytes for 32-bit machines) */ 345034768Speter union { 345134768Speter uInt Base; /* literal, length base, or distance base */ 345234768Speter inflate_huft *Next; /* pointer to next level of table */ 345334768Speter } more; 345434768Speter}; 345534768Speter 345634768Speter#ifdef DEBUG_ZLIB 345734768Speter extern uInt inflate_hufts; 345834768Speter#endif 345934768Speter 346034768Speterextern int inflate_trees_bits OF(( 346134768Speter uIntf *, /* 19 code lengths */ 346234768Speter uIntf *, /* bits tree desired/actual depth */ 346334768Speter inflate_huft * FAR *, /* bits tree result */ 346434768Speter z_streamp )); /* for zalloc, zfree functions */ 346534768Speter 346634768Speterextern int inflate_trees_dynamic OF(( 346734768Speter uInt, /* number of literal/length codes */ 346834768Speter uInt, /* number of distance codes */ 346934768Speter uIntf *, /* that many (total) code lengths */ 347034768Speter uIntf *, /* literal desired/actual bit depth */ 347134768Speter uIntf *, /* distance desired/actual bit depth */ 347234768Speter inflate_huft * FAR *, /* literal/length tree result */ 347334768Speter inflate_huft * FAR *, /* distance tree result */ 347434768Speter z_streamp )); /* for zalloc, zfree functions */ 347534768Speter 347634768Speterextern int inflate_trees_fixed OF(( 347734768Speter uIntf *, /* literal desired/actual bit depth */ 347834768Speter uIntf *, /* distance desired/actual bit depth */ 347934768Speter inflate_huft * FAR *, /* literal/length tree result */ 348034768Speter inflate_huft * FAR *)); /* distance tree result */ 348134768Speter 348234768Speterextern int inflate_trees_free OF(( 348334768Speter inflate_huft *, /* tables to free */ 348434768Speter z_streamp )); /* for zfree function */ 348534768Speter 348634768Speter/* --- inftrees.h */ 348734768Speter 348834768Speter/* +++ infcodes.h */ 348934768Speter/* infcodes.h -- header to use infcodes.c 349034768Speter * Copyright (C) 1995-1996 Mark Adler 349134768Speter * For conditions of distribution and use, see copyright notice in zlib.h 349234768Speter */ 349334768Speter 349434768Speter/* WARNING: this file should *not* be used by applications. It is 349534768Speter part of the implementation of the compression library and is 349634768Speter subject to change. Applications should only use zlib.h. 349734768Speter */ 349834768Speter 349934768Speterstruct inflate_codes_state; 350034768Spetertypedef struct inflate_codes_state FAR inflate_codes_statef; 350134768Speter 350234768Speterextern inflate_codes_statef *inflate_codes_new OF(( 350334768Speter uInt, uInt, 350434768Speter inflate_huft *, inflate_huft *, 350534768Speter z_streamp )); 350634768Speter 350734768Speterextern int inflate_codes OF(( 350834768Speter inflate_blocks_statef *, 350934768Speter z_streamp , 351034768Speter int)); 351134768Speter 351234768Speterextern void inflate_codes_free OF(( 351334768Speter inflate_codes_statef *, 351434768Speter z_streamp )); 351534768Speter 351634768Speter/* --- infcodes.h */ 351734768Speter 351834768Speter/* +++ infutil.h */ 351928415Speter/* infutil.h -- types and macros common to blocks and codes 352034768Speter * Copyright (C) 1995-1996 Mark Adler 352128415Speter * For conditions of distribution and use, see copyright notice in zlib.h 352228415Speter */ 352328415Speter 352428415Speter/* WARNING: this file should *not* be used by applications. It is 352528415Speter part of the implementation of the compression library and is 352628415Speter subject to change. Applications should only use zlib.h. 352728415Speter */ 352828415Speter 352934768Speter#ifndef _INFUTIL_H 353034768Speter#define _INFUTIL_H 353128415Speter 353234768Spetertypedef enum { 353328415Speter TYPE, /* get type bits (3, including end bit) */ 353428415Speter LENS, /* get lengths for stored */ 353528415Speter STORED, /* processing stored block */ 353628415Speter TABLE, /* get table lengths */ 353728415Speter BTREE, /* get bit lengths tree for a dynamic block */ 353828415Speter DTREE, /* get length, distance trees for a dynamic block */ 353928415Speter CODES, /* processing fixed or dynamic block */ 354028415Speter DRY, /* output remaining window bytes */ 354134768Speter DONEB, /* finished last block, done */ 354234768Speter BADB} /* got a data error--stuck here */ 354334768Speterinflate_block_mode; 354428415Speter 354534768Speter/* inflate blocks semi-private state */ 354634768Speterstruct inflate_blocks_state { 354734768Speter 354834768Speter /* mode */ 354934768Speter inflate_block_mode mode; /* current inflate_block mode */ 355034768Speter 355128415Speter /* mode dependent information */ 355228415Speter union { 355328415Speter uInt left; /* if STORED, bytes left to copy */ 355428415Speter struct { 355528415Speter uInt table; /* table lengths (14 bits) */ 355628415Speter uInt index; /* index into blens (or border) */ 355728415Speter uIntf *blens; /* bit lengths of codes */ 355828415Speter uInt bb; /* bit length tree depth */ 355928415Speter inflate_huft *tb; /* bit length decoding tree */ 356028415Speter } trees; /* if DTREE, decoding info for trees */ 356128415Speter struct { 356234768Speter inflate_huft *tl; 356334768Speter inflate_huft *td; /* trees to free */ 356428415Speter inflate_codes_statef 356528415Speter *codes; 356628415Speter } decode; /* if CODES, current state */ 356728415Speter } sub; /* submode */ 356828415Speter uInt last; /* true if this block is the last block */ 356928415Speter 357028415Speter /* mode independent information */ 357128415Speter uInt bitk; /* bits in bit buffer */ 357228415Speter uLong bitb; /* bit buffer */ 357328415Speter Bytef *window; /* sliding window */ 357428415Speter Bytef *end; /* one byte after sliding window */ 357528415Speter Bytef *read; /* window read pointer */ 357628415Speter Bytef *write; /* window write pointer */ 357728415Speter check_func checkfn; /* check function */ 357828415Speter uLong check; /* check on output */ 357928415Speter 358028415Speter}; 358128415Speter 358228415Speter 358328415Speter/* defines for inflate input/output */ 358428415Speter/* update pointers and return */ 358528415Speter#define UPDBITS {s->bitb=b;s->bitk=k;} 358628415Speter#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;} 358728415Speter#define UPDOUT {s->write=q;} 358828415Speter#define UPDATE {UPDBITS UPDIN UPDOUT} 358928415Speter#define LEAVE {UPDATE return inflate_flush(s,z,r);} 359028415Speter/* get bytes and bits */ 359128415Speter#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;} 359228415Speter#define NEEDBYTE {if(n)r=Z_OK;else LEAVE} 359328415Speter#define NEXTBYTE (n--,*p++) 359428415Speter#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}} 359528415Speter#define DUMPBITS(j) {b>>=(j);k-=(j);} 359628415Speter/* output bytes */ 359734768Speter#define WAVAIL (uInt)(q<s->read?s->read-q-1:s->end-q) 359834768Speter#define LOADOUT {q=s->write;m=(uInt)WAVAIL;} 359934768Speter#define WWRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}} 360028415Speter#define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT} 360134768Speter#define NEEDOUT {if(m==0){WWRAP if(m==0){FLUSH WWRAP if(m==0) LEAVE}}r=Z_OK;} 360228415Speter#define OUTBYTE(a) {*q++=(Byte)(a);m--;} 360328415Speter/* load local pointers */ 360428415Speter#define LOAD {LOADIN LOADOUT} 360528415Speter 360634768Speter/* masks for lower bits (size given to avoid silly warnings with Visual C++) */ 360734768Speterextern uInt inflate_mask[17]; 360828415Speter 360928415Speter/* copy as much as possible from the sliding window to the output area */ 361034768Speterextern int inflate_flush OF(( 361128415Speter inflate_blocks_statef *, 361234768Speter z_streamp , 361328415Speter int)); 361428415Speter 361534768Speter#ifndef NO_DUMMY_DECL 361634768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 361734768Speter#endif 361828415Speter 361934768Speter#endif 362034768Speter/* --- infutil.h */ 362128415Speter 362234768Speter#ifndef NO_DUMMY_DECL 362334768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 362434768Speter#endif 362528415Speter 362628415Speter/* Table for deflate from PKZIP's appnote.txt. */ 362734768Speterlocal const uInt border[] = { /* Order of the bit length code lengths */ 362828415Speter 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 362928415Speter 363028415Speter/* 363128415Speter Notes beyond the 1.93a appnote.txt: 363228415Speter 363328415Speter 1. Distance pointers never point before the beginning of the output 363428415Speter stream. 363528415Speter 2. Distance pointers can point back across blocks, up to 32k away. 363628415Speter 3. There is an implied maximum of 7 bits for the bit length table and 363728415Speter 15 bits for the actual data. 363828415Speter 4. If only one code exists, then it is encoded using one bit. (Zero 363928415Speter would be more efficient, but perhaps a little confusing.) If two 364028415Speter codes exist, they are coded using one bit each (0 and 1). 364128415Speter 5. There is no way of sending zero distance codes--a dummy must be 364228415Speter sent if there are none. (History: a pre 2.0 version of PKZIP would 364328415Speter store blocks with no distance codes, but this was discovered to be 364428415Speter too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 364528415Speter zero distance codes, which is sent as one code of zero bits in 364628415Speter length. 364728415Speter 6. There are up to 286 literal/length codes. Code 256 represents the 364828415Speter end-of-block. Note however that the static length tree defines 364928415Speter 288 codes just to fill out the Huffman codes. Codes 286 and 287 365028415Speter cannot be used though, since there is no length base or extra bits 365128415Speter defined for them. Similarily, there are up to 30 distance codes. 365228415Speter However, static trees define 32 codes (all 5 bits) to fill out the 365328415Speter Huffman codes, but the last two had better not show up in the data. 365428415Speter 7. Unzip can check dynamic Huffman blocks for complete code sets. 365528415Speter The exception is that a single code would not be complete (see #4). 365628415Speter 8. The five bits following the block type is really the number of 365728415Speter literal codes sent minus 257. 365828415Speter 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 365928415Speter (1+6+6). Therefore, to output three times the length, you output 366028415Speter three codes (1+1+1), whereas to output four times the same length, 366128415Speter you only need two codes (1+3). Hmm. 366228415Speter 10. In the tree reconstruction algorithm, Code = Code + Increment 366328415Speter only if BitLength(i) is not zero. (Pretty obvious.) 366428415Speter 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 366528415Speter 12. Note: length code 284 can represent 227-258, but length code 285 366628415Speter really is 258. The last length deserves its own, short code 366728415Speter since it gets used a lot in very redundant files. The length 366828415Speter 258 is special since 258 - 3 (the min match length) is 255. 366928415Speter 13. The literal/length and distance code bit lengths are read as a 367028415Speter single stream of lengths. It is possible (and advantageous) for 367128415Speter a repeat code (16, 17, or 18) to go across the boundary between 367228415Speter the two sets of lengths. 367328415Speter */ 367428415Speter 367528415Speter 367634768Spetervoid inflate_blocks_reset(s, z, c) 367728415Speterinflate_blocks_statef *s; 367834768Speterz_streamp z; 367928415SpeteruLongf *c; 368028415Speter{ 368128415Speter if (s->checkfn != Z_NULL) 368228415Speter *c = s->check; 368328415Speter if (s->mode == BTREE || s->mode == DTREE) 368434768Speter ZFREE(z, s->sub.trees.blens); 368528415Speter if (s->mode == CODES) 368628415Speter { 368728415Speter inflate_codes_free(s->sub.decode.codes, z); 368828415Speter inflate_trees_free(s->sub.decode.td, z); 368928415Speter inflate_trees_free(s->sub.decode.tl, z); 369028415Speter } 369128415Speter s->mode = TYPE; 369228415Speter s->bitk = 0; 369328415Speter s->bitb = 0; 369428415Speter s->read = s->write = s->window; 369528415Speter if (s->checkfn != Z_NULL) 369634768Speter z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0); 369728415Speter Trace((stderr, "inflate: blocks reset\n")); 369828415Speter} 369928415Speter 370028415Speter 370134768Speterinflate_blocks_statef *inflate_blocks_new(z, c, w) 370234768Speterz_streamp z; 370328415Spetercheck_func c; 370428415SpeteruInt w; 370528415Speter{ 370628415Speter inflate_blocks_statef *s; 370728415Speter 370834768Speter if ((s = (inflate_blocks_statef *)ZALLOC 370928415Speter (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) 371028415Speter return s; 371134768Speter if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) 371228415Speter { 371334768Speter ZFREE(z, s); 371428415Speter return Z_NULL; 371528415Speter } 371628415Speter s->end = s->window + w; 371728415Speter s->checkfn = c; 371828415Speter s->mode = TYPE; 371928415Speter Trace((stderr, "inflate: blocks allocated\n")); 372028415Speter inflate_blocks_reset(s, z, &s->check); 372128415Speter return s; 372228415Speter} 372328415Speter 372428415Speter 372534768Speter#ifdef DEBUG_ZLIB 372634768Speter extern uInt inflate_hufts; 372734768Speter#endif 372834768Speterint inflate_blocks(s, z, r) 372928415Speterinflate_blocks_statef *s; 373034768Speterz_streamp z; 373128415Speterint r; 373228415Speter{ 373328415Speter uInt t; /* temporary storage */ 373428415Speter uLong b; /* bit buffer */ 373528415Speter uInt k; /* bits in bit buffer */ 373628415Speter Bytef *p; /* input data pointer */ 373728415Speter uInt n; /* bytes available there */ 373828415Speter Bytef *q; /* output window write pointer */ 373928415Speter uInt m; /* bytes to end of window or read pointer */ 374028415Speter 374128415Speter /* copy input/output information to locals (UPDATE macro restores) */ 374228415Speter LOAD 374328415Speter 374428415Speter /* process input based on current state */ 374528415Speter while (1) switch (s->mode) 374628415Speter { 374728415Speter case TYPE: 374828415Speter NEEDBITS(3) 374928415Speter t = (uInt)b & 7; 375028415Speter s->last = t & 1; 375128415Speter switch (t >> 1) 375228415Speter { 375328415Speter case 0: /* stored */ 375428415Speter Trace((stderr, "inflate: stored block%s\n", 375528415Speter s->last ? " (last)" : "")); 375628415Speter DUMPBITS(3) 375728415Speter t = k & 7; /* go to byte boundary */ 375828415Speter DUMPBITS(t) 375928415Speter s->mode = LENS; /* get length of stored block */ 376028415Speter break; 376128415Speter case 1: /* fixed */ 376228415Speter Trace((stderr, "inflate: fixed codes block%s\n", 376328415Speter s->last ? " (last)" : "")); 376428415Speter { 376528415Speter uInt bl, bd; 376628415Speter inflate_huft *tl, *td; 376728415Speter 376828415Speter inflate_trees_fixed(&bl, &bd, &tl, &td); 376928415Speter s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); 377028415Speter if (s->sub.decode.codes == Z_NULL) 377128415Speter { 377228415Speter r = Z_MEM_ERROR; 377328415Speter LEAVE 377428415Speter } 377528415Speter s->sub.decode.tl = Z_NULL; /* don't try to free these */ 377628415Speter s->sub.decode.td = Z_NULL; 377728415Speter } 377828415Speter DUMPBITS(3) 377928415Speter s->mode = CODES; 378028415Speter break; 378128415Speter case 2: /* dynamic */ 378228415Speter Trace((stderr, "inflate: dynamic codes block%s\n", 378328415Speter s->last ? " (last)" : "")); 378428415Speter DUMPBITS(3) 378528415Speter s->mode = TABLE; 378628415Speter break; 378728415Speter case 3: /* illegal */ 378828415Speter DUMPBITS(3) 378928415Speter s->mode = BADB; 379034768Speter z->msg = (char*)"invalid block type"; 379128415Speter r = Z_DATA_ERROR; 379228415Speter LEAVE 379328415Speter } 379428415Speter break; 379528415Speter case LENS: 379628415Speter NEEDBITS(32) 379734768Speter if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) 379828415Speter { 379928415Speter s->mode = BADB; 380034768Speter z->msg = (char*)"invalid stored block lengths"; 380128415Speter r = Z_DATA_ERROR; 380228415Speter LEAVE 380328415Speter } 380428415Speter s->sub.left = (uInt)b & 0xffff; 380528415Speter b = k = 0; /* dump bits */ 380628415Speter Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); 380734768Speter s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); 380828415Speter break; 380928415Speter case STORED: 381028415Speter if (n == 0) 381128415Speter LEAVE 381228415Speter NEEDOUT 381328415Speter t = s->sub.left; 381428415Speter if (t > n) t = n; 381528415Speter if (t > m) t = m; 381628415Speter zmemcpy(q, p, t); 381728415Speter p += t; n -= t; 381828415Speter q += t; m -= t; 381928415Speter if ((s->sub.left -= t) != 0) 382028415Speter break; 382128415Speter Tracev((stderr, "inflate: stored end, %lu total out\n", 382228415Speter z->total_out + (q >= s->read ? q - s->read : 382328415Speter (s->end - s->read) + (q - s->window)))); 382428415Speter s->mode = s->last ? DRY : TYPE; 382528415Speter break; 382628415Speter case TABLE: 382728415Speter NEEDBITS(14) 382828415Speter s->sub.trees.table = t = (uInt)b & 0x3fff; 382928415Speter#ifndef PKZIP_BUG_WORKAROUND 383028415Speter if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) 383128415Speter { 383228415Speter s->mode = BADB; 383334768Speter z->msg = (char*)"too many length or distance symbols"; 383428415Speter r = Z_DATA_ERROR; 383528415Speter LEAVE 383628415Speter } 383728415Speter#endif 383828415Speter t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); 383928415Speter if (t < 19) 384028415Speter t = 19; 384128415Speter if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) 384228415Speter { 384328415Speter r = Z_MEM_ERROR; 384428415Speter LEAVE 384528415Speter } 384628415Speter DUMPBITS(14) 384728415Speter s->sub.trees.index = 0; 384828415Speter Tracev((stderr, "inflate: table sizes ok\n")); 384928415Speter s->mode = BTREE; 385028415Speter case BTREE: 385128415Speter while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) 385228415Speter { 385328415Speter NEEDBITS(3) 385428415Speter s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; 385528415Speter DUMPBITS(3) 385628415Speter } 385728415Speter while (s->sub.trees.index < 19) 385828415Speter s->sub.trees.blens[border[s->sub.trees.index++]] = 0; 385928415Speter s->sub.trees.bb = 7; 386028415Speter t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, 386128415Speter &s->sub.trees.tb, z); 386228415Speter if (t != Z_OK) 386328415Speter { 386428415Speter r = t; 386590775Sjedgar if (r == Z_DATA_ERROR) { 386690775Sjedgar ZFREE(z, s->sub.trees.blens); 386728415Speter s->mode = BADB; 386890775Sjedgar } 386928415Speter LEAVE 387028415Speter } 387128415Speter s->sub.trees.index = 0; 387228415Speter Tracev((stderr, "inflate: bits tree ok\n")); 387328415Speter s->mode = DTREE; 387428415Speter case DTREE: 387528415Speter while (t = s->sub.trees.table, 387628415Speter s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) 387728415Speter { 387828415Speter inflate_huft *h; 387928415Speter uInt i, j, c; 388028415Speter 388128415Speter t = s->sub.trees.bb; 388228415Speter NEEDBITS(t) 388328415Speter h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); 388428415Speter t = h->word.what.Bits; 388528415Speter c = h->more.Base; 388628415Speter if (c < 16) 388728415Speter { 388828415Speter DUMPBITS(t) 388928415Speter s->sub.trees.blens[s->sub.trees.index++] = c; 389028415Speter } 389128415Speter else /* c == 16..18 */ 389228415Speter { 389328415Speter i = c == 18 ? 7 : c - 14; 389428415Speter j = c == 18 ? 11 : 3; 389528415Speter NEEDBITS(t + i) 389628415Speter DUMPBITS(t) 389728415Speter j += (uInt)b & inflate_mask[i]; 389828415Speter DUMPBITS(i) 389928415Speter i = s->sub.trees.index; 390028415Speter t = s->sub.trees.table; 390128415Speter if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || 390228415Speter (c == 16 && i < 1)) 390328415Speter { 390434768Speter inflate_trees_free(s->sub.trees.tb, z); 390534768Speter ZFREE(z, s->sub.trees.blens); 390628415Speter s->mode = BADB; 390734768Speter z->msg = (char*)"invalid bit length repeat"; 390828415Speter r = Z_DATA_ERROR; 390928415Speter LEAVE 391028415Speter } 391128415Speter c = c == 16 ? s->sub.trees.blens[i - 1] : 0; 391228415Speter do { 391328415Speter s->sub.trees.blens[i++] = c; 391428415Speter } while (--j); 391528415Speter s->sub.trees.index = i; 391628415Speter } 391728415Speter } 391828415Speter inflate_trees_free(s->sub.trees.tb, z); 391928415Speter s->sub.trees.tb = Z_NULL; 392028415Speter { 392128415Speter uInt bl, bd; 392228415Speter inflate_huft *tl, *td; 392328415Speter inflate_codes_statef *c; 392428415Speter 392528415Speter bl = 9; /* must be <= 9 for lookahead assumptions */ 392628415Speter bd = 6; /* must be <= 9 for lookahead assumptions */ 392728415Speter t = s->sub.trees.table; 392834768Speter#ifdef DEBUG_ZLIB 392934768Speter inflate_hufts = 0; 393034768Speter#endif 393128415Speter t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), 393228415Speter s->sub.trees.blens, &bl, &bd, &tl, &td, z); 393328415Speter if (t != Z_OK) 393428415Speter { 393590775Sjedgar if (t == (uInt)Z_DATA_ERROR) { 393690775Sjedgar ZFREE(z, s->sub.trees.blens); 393728415Speter s->mode = BADB; 393890775Sjedgar } 393928415Speter r = t; 394028415Speter LEAVE 394128415Speter } 394234768Speter Tracev((stderr, "inflate: trees ok, %d * %d bytes used\n", 394334768Speter inflate_hufts, sizeof(inflate_huft))); 394428415Speter if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) 394528415Speter { 394628415Speter inflate_trees_free(td, z); 394728415Speter inflate_trees_free(tl, z); 394828415Speter r = Z_MEM_ERROR; 394928415Speter LEAVE 395028415Speter } 395192749Sdillon /* 395292749Sdillon * this ZFREE must occur *BEFORE* we mess with sub.decode, because 395392749Sdillon * sub.trees is union'd with sub.decode. 395492749Sdillon */ 395592749Sdillon ZFREE(z, s->sub.trees.blens); 395628415Speter s->sub.decode.codes = c; 395728415Speter s->sub.decode.tl = tl; 395828415Speter s->sub.decode.td = td; 395928415Speter } 396028415Speter s->mode = CODES; 396128415Speter case CODES: 396228415Speter UPDATE 396328415Speter if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) 396428415Speter return inflate_flush(s, z, r); 396528415Speter r = Z_OK; 396628415Speter inflate_codes_free(s->sub.decode.codes, z); 396728415Speter inflate_trees_free(s->sub.decode.td, z); 396828415Speter inflate_trees_free(s->sub.decode.tl, z); 396928415Speter LOAD 397028415Speter Tracev((stderr, "inflate: codes end, %lu total out\n", 397128415Speter z->total_out + (q >= s->read ? q - s->read : 397228415Speter (s->end - s->read) + (q - s->window)))); 397328415Speter if (!s->last) 397428415Speter { 397528415Speter s->mode = TYPE; 397628415Speter break; 397728415Speter } 397828415Speter if (k > 7) /* return unused byte, if any */ 397928415Speter { 398028415Speter Assert(k < 16, "inflate_codes grabbed too many bytes") 398128415Speter k -= 8; 398228415Speter n++; 398328415Speter p--; /* can always return one */ 398428415Speter } 398528415Speter s->mode = DRY; 398628415Speter case DRY: 398728415Speter FLUSH 398828415Speter if (s->read != s->write) 398928415Speter LEAVE 399028415Speter s->mode = DONEB; 399128415Speter case DONEB: 399228415Speter r = Z_STREAM_END; 399328415Speter LEAVE 399428415Speter case BADB: 399528415Speter r = Z_DATA_ERROR; 399628415Speter LEAVE 399728415Speter default: 399828415Speter r = Z_STREAM_ERROR; 399928415Speter LEAVE 400028415Speter } 400128415Speter} 400228415Speter 400328415Speter 400434768Speterint inflate_blocks_free(s, z, c) 400528415Speterinflate_blocks_statef *s; 400634768Speterz_streamp z; 400728415SpeteruLongf *c; 400828415Speter{ 400928415Speter inflate_blocks_reset(s, z, c); 401034768Speter ZFREE(z, s->window); 401134768Speter ZFREE(z, s); 401228415Speter Trace((stderr, "inflate: blocks freed\n")); 401328415Speter return Z_OK; 401428415Speter} 401528415Speter 401634768Speter 401734768Spetervoid inflate_set_dictionary(s, d, n) 401834768Speterinflate_blocks_statef *s; 401934768Speterconst Bytef *d; 402034768SpeteruInt n; 402134768Speter{ 402234768Speter zmemcpy((charf *)s->window, d, n); 402334768Speter s->read = s->write = s->window + n; 402434768Speter} 402534768Speter 402628415Speter/* 402728415Speter * This subroutine adds the data at next_in/avail_in to the output history 402828415Speter * without performing any output. The output buffer must be "caught up"; 402928415Speter * i.e. no pending output (hence s->read equals s->write), and the state must 403028415Speter * be BLOCKS (i.e. we should be willing to see the start of a series of 403128415Speter * BLOCKS). On exit, the output will also be caught up, and the checksum 403228415Speter * will have been updated if need be. 403328415Speter */ 403434768Speterint inflate_addhistory(s, z) 403528415Speterinflate_blocks_statef *s; 403628415Speterz_stream *z; 403728415Speter{ 403828415Speter uLong b; /* bit buffer */ /* NOT USED HERE */ 403928415Speter uInt k; /* bits in bit buffer */ /* NOT USED HERE */ 404028415Speter uInt t; /* temporary storage */ 404128415Speter Bytef *p; /* input data pointer */ 404228415Speter uInt n; /* bytes available there */ 404328415Speter Bytef *q; /* output window write pointer */ 404428415Speter uInt m; /* bytes to end of window or read pointer */ 404528415Speter 404628415Speter if (s->read != s->write) 404728415Speter return Z_STREAM_ERROR; 404828415Speter if (s->mode != TYPE) 404928415Speter return Z_DATA_ERROR; 405028415Speter 405128415Speter /* we're ready to rock */ 405228415Speter LOAD 405328415Speter /* while there is input ready, copy to output buffer, moving 405428415Speter * pointers as needed. 405528415Speter */ 405628415Speter while (n) { 405728415Speter t = n; /* how many to do */ 405828415Speter /* is there room until end of buffer? */ 405928415Speter if (t > m) t = m; 406028415Speter /* update check information */ 406128415Speter if (s->checkfn != Z_NULL) 406228415Speter s->check = (*s->checkfn)(s->check, q, t); 406328415Speter zmemcpy(q, p, t); 406428415Speter q += t; 406528415Speter p += t; 406628415Speter n -= t; 406728415Speter z->total_out += t; 406828415Speter s->read = q; /* drag read pointer forward */ 406934768Speter/* WWRAP */ /* expand WWRAP macro by hand to handle s->read */ 407028415Speter if (q == s->end) { 407128415Speter s->read = q = s->window; 407228415Speter m = WAVAIL; 407328415Speter } 407428415Speter } 407528415Speter UPDATE 407628415Speter return Z_OK; 407728415Speter} 407828415Speter 407928415Speter 408028415Speter/* 408128415Speter * At the end of a Deflate-compressed PPP packet, we expect to have seen 408228415Speter * a `stored' block type value but not the (zero) length bytes. 408328415Speter */ 408434768Speterint inflate_packet_flush(s) 408528415Speter inflate_blocks_statef *s; 408628415Speter{ 408728415Speter if (s->mode != LENS) 408828415Speter return Z_DATA_ERROR; 408928415Speter s->mode = TYPE; 409028415Speter return Z_OK; 409128415Speter} 409234768Speter/* --- infblock.c */ 409328415Speter 409434768Speter/* +++ inftrees.c */ 409528415Speter/* inftrees.c -- generate Huffman trees for efficient decoding 409634768Speter * Copyright (C) 1995-1996 Mark Adler 409728415Speter * For conditions of distribution and use, see copyright notice in zlib.h 409828415Speter */ 409928415Speter 410034768Speter/* #include "zutil.h" */ 410134768Speter/* #include "inftrees.h" */ 410234768Speter 410334768Speterchar inflate_copyright[] = " inflate 1.0.4 Copyright 1995-1996 Mark Adler "; 410434768Speter/* 410534768Speter If you use the zlib library in a product, an acknowledgment is welcome 410634768Speter in the documentation of your product. If for some reason you cannot 410734768Speter include such an acknowledgment, I would appreciate that you keep this 410834768Speter copyright string in the executable of your product. 410934768Speter */ 411034768Speter 411134768Speter#ifndef NO_DUMMY_DECL 411234768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 411334768Speter#endif 411434768Speter 411528415Speter/* simplify the use of the inflate_huft type with some defines */ 411628415Speter#define base more.Base 411728415Speter#define next more.Next 411828415Speter#define exop word.what.Exop 411928415Speter#define bits word.what.Bits 412028415Speter 412128415Speter 412228415Speterlocal int huft_build OF(( 412328415Speter uIntf *, /* code lengths in bits */ 412428415Speter uInt, /* number of codes */ 412528415Speter uInt, /* number of "simple" codes */ 412634768Speter const uIntf *, /* list of base values for non-simple codes */ 412734768Speter const uIntf *, /* list of extra bits for non-simple codes */ 412828415Speter inflate_huft * FAR*,/* result: starting table */ 412928415Speter uIntf *, /* maximum lookup bits (returns actual) */ 413034768Speter z_streamp )); /* for zalloc function */ 413128415Speter 413228415Speterlocal voidpf falloc OF(( 413328415Speter voidpf, /* opaque pointer (not used) */ 413428415Speter uInt, /* number of items */ 413528415Speter uInt)); /* size of item */ 413628415Speter 413728415Speter/* Tables for deflate from PKZIP's appnote.txt. */ 413834768Speterlocal const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */ 413928415Speter 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 414028415Speter 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 414134768Speter /* see note #13 above about 258 */ 414234768Speterlocal const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */ 414328415Speter 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 414434768Speter 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */ 414534768Speterlocal const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */ 414628415Speter 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 414728415Speter 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 414828415Speter 8193, 12289, 16385, 24577}; 414934768Speterlocal const uInt cpdext[30] = { /* Extra bits for distance codes */ 415028415Speter 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 415128415Speter 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 415228415Speter 12, 12, 13, 13}; 415328415Speter 415428415Speter/* 415528415Speter Huffman code decoding is performed using a multi-level table lookup. 415628415Speter The fastest way to decode is to simply build a lookup table whose 415728415Speter size is determined by the longest code. However, the time it takes 415828415Speter to build this table can also be a factor if the data being decoded 415928415Speter is not very long. The most common codes are necessarily the 416028415Speter shortest codes, so those codes dominate the decoding time, and hence 416128415Speter the speed. The idea is you can have a shorter table that decodes the 416228415Speter shorter, more probable codes, and then point to subsidiary tables for 416328415Speter the longer codes. The time it costs to decode the longer codes is 416428415Speter then traded against the time it takes to make longer tables. 416528415Speter 416628415Speter This results of this trade are in the variables lbits and dbits 416728415Speter below. lbits is the number of bits the first level table for literal/ 416828415Speter length codes can decode in one step, and dbits is the same thing for 416928415Speter the distance codes. Subsequent tables are also less than or equal to 417028415Speter those sizes. These values may be adjusted either when all of the 417128415Speter codes are shorter than that, in which case the longest code length in 417228415Speter bits is used, or when the shortest code is *longer* than the requested 417328415Speter table size, in which case the length of the shortest code in bits is 417428415Speter used. 417528415Speter 417628415Speter There are two different values for the two tables, since they code a 417728415Speter different number of possibilities each. The literal/length table 417828415Speter codes 286 possible values, or in a flat code, a little over eight 417928415Speter bits. The distance table codes 30 possible values, or a little less 418028415Speter than five bits, flat. The optimum values for speed end up being 418128415Speter about one bit more than those, so lbits is 8+1 and dbits is 5+1. 418228415Speter The optimum values may differ though from machine to machine, and 418328415Speter possibly even between compilers. Your mileage may vary. 418428415Speter */ 418528415Speter 418628415Speter 418728415Speter/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ 418828415Speter#define BMAX 15 /* maximum bit length of any code */ 418928415Speter#define N_MAX 288 /* maximum number of codes in any set */ 419028415Speter 419128415Speter#ifdef DEBUG_ZLIB 419228415Speter uInt inflate_hufts; 419328415Speter#endif 419428415Speter 419528415Speterlocal int huft_build(b, n, s, d, e, t, m, zs) 419628415SpeteruIntf *b; /* code lengths in bits (all assumed <= BMAX) */ 419728415SpeteruInt n; /* number of codes (assumed <= N_MAX) */ 419828415SpeteruInt s; /* number of simple-valued codes (0..s-1) */ 419934768Speterconst uIntf *d; /* list of base values for non-simple codes */ 420034768Speterconst uIntf *e; /* list of extra bits for non-simple codes */ 420128415Speterinflate_huft * FAR *t; /* result: starting table */ 420228415SpeteruIntf *m; /* maximum lookup bits, returns actual */ 420334768Speterz_streamp zs; /* for zalloc function */ 420428415Speter/* Given a list of code lengths and a maximum table size, make a set of 420528415Speter tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR 420628415Speter if the given code set is incomplete (the tables are still built in this 420734768Speter case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of 420834768Speter lengths), or Z_MEM_ERROR if not enough memory. */ 420928415Speter{ 421028415Speter 421128415Speter uInt a; /* counter for codes of length k */ 421228415Speter uInt c[BMAX+1]; /* bit length count table */ 421328415Speter uInt f; /* i repeats in table every f entries */ 421428415Speter int g; /* maximum code length */ 421528415Speter int h; /* table level */ 421628415Speter register uInt i; /* counter, current code */ 421728415Speter register uInt j; /* counter */ 421828415Speter register int k; /* number of bits in current code */ 421928415Speter int l; /* bits per table (returned in m) */ 422028415Speter register uIntf *p; /* pointer into c[], b[], or v[] */ 422128415Speter inflate_huft *q; /* points to current table */ 422228415Speter struct inflate_huft_s r; /* table entry for structure assignment */ 422328415Speter inflate_huft *u[BMAX]; /* table stack */ 422428415Speter uInt v[N_MAX]; /* values in order of bit length */ 422528415Speter register int w; /* bits before this table == (l * h) */ 422628415Speter uInt x[BMAX+1]; /* bit offsets, then code stack */ 422728415Speter uIntf *xp; /* pointer into x */ 422828415Speter int y; /* number of dummy codes added */ 422928415Speter uInt z; /* number of entries in current table */ 423028415Speter 423128415Speter 423228415Speter /* Generate counts for each bit length */ 423328415Speter p = c; 423428415Speter#define C0 *p++ = 0; 423528415Speter#define C2 C0 C0 C0 C0 423628415Speter#define C4 C2 C2 C2 C2 423728415Speter C4 /* clear c[]--assume BMAX+1 is 16 */ 423828415Speter p = b; i = n; 423928415Speter do { 424028415Speter c[*p++]++; /* assume all entries <= BMAX */ 424128415Speter } while (--i); 424228415Speter if (c[0] == n) /* null input--all zero length codes */ 424328415Speter { 424428415Speter *t = (inflate_huft *)Z_NULL; 424528415Speter *m = 0; 424628415Speter return Z_OK; 424728415Speter } 424828415Speter 424928415Speter 425028415Speter /* Find minimum and maximum length, bound *m by those */ 425128415Speter l = *m; 425228415Speter for (j = 1; j <= BMAX; j++) 425328415Speter if (c[j]) 425428415Speter break; 425528415Speter k = j; /* minimum code length */ 425628415Speter if ((uInt)l < j) 425728415Speter l = j; 425828415Speter for (i = BMAX; i; i--) 425928415Speter if (c[i]) 426028415Speter break; 426128415Speter g = i; /* maximum code length */ 426228415Speter if ((uInt)l > i) 426328415Speter l = i; 426428415Speter *m = l; 426528415Speter 426628415Speter 426728415Speter /* Adjust last length count to fill out codes, if needed */ 426828415Speter for (y = 1 << j; j < i; j++, y <<= 1) 426928415Speter if ((y -= c[j]) < 0) 427028415Speter return Z_DATA_ERROR; 427128415Speter if ((y -= c[i]) < 0) 427228415Speter return Z_DATA_ERROR; 427328415Speter c[i] += y; 427428415Speter 427528415Speter 427628415Speter /* Generate starting offsets into the value table for each length */ 427728415Speter x[1] = j = 0; 427828415Speter p = c + 1; xp = x + 2; 427928415Speter while (--i) { /* note that i == g from above */ 428028415Speter *xp++ = (j += *p++); 428128415Speter } 428228415Speter 428328415Speter 428428415Speter /* Make a table of values in order of bit lengths */ 428528415Speter p = b; i = 0; 428628415Speter do { 428728415Speter if ((j = *p++) != 0) 428828415Speter v[x[j]++] = i; 428928415Speter } while (++i < n); 429034768Speter n = x[g]; /* set n to length of v */ 429128415Speter 429228415Speter 429328415Speter /* Generate the Huffman codes and for each, make the table entries */ 429428415Speter x[0] = i = 0; /* first Huffman code is zero */ 429528415Speter p = v; /* grab values in bit order */ 429628415Speter h = -1; /* no tables yet--level -1 */ 429728415Speter w = -l; /* bits decoded == (l * h) */ 429828415Speter u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ 429928415Speter q = (inflate_huft *)Z_NULL; /* ditto */ 430028415Speter z = 0; /* ditto */ 430128415Speter 430228415Speter /* go through the bit lengths (k already is bits in shortest code) */ 430328415Speter for (; k <= g; k++) 430428415Speter { 430528415Speter a = c[k]; 430628415Speter while (a--) 430728415Speter { 430828415Speter /* here i is the Huffman code of length k bits for value *p */ 430928415Speter /* make tables up to required level */ 431028415Speter while (k > w + l) 431128415Speter { 431228415Speter h++; 431328415Speter w += l; /* previous table always l bits */ 431428415Speter 431528415Speter /* compute minimum size table less than or equal to l bits */ 431634768Speter z = g - w; 431734768Speter z = z > (uInt)l ? l : z; /* table size upper limit */ 431828415Speter if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 431928415Speter { /* too few codes for k-w bit table */ 432028415Speter f -= a + 1; /* deduct codes from patterns left */ 432128415Speter xp = c + k; 432228415Speter if (j < z) 432328415Speter while (++j < z) /* try smaller tables up to z bits */ 432428415Speter { 432528415Speter if ((f <<= 1) <= *++xp) 432628415Speter break; /* enough codes to use up j bits */ 432728415Speter f -= *xp; /* else deduct codes from patterns */ 432828415Speter } 432928415Speter } 433028415Speter z = 1 << j; /* table entries for j-bit table */ 433128415Speter 433228415Speter /* allocate and link in new table */ 433328415Speter if ((q = (inflate_huft *)ZALLOC 433428415Speter (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) 433528415Speter { 433628415Speter if (h) 433728415Speter inflate_trees_free(u[0], zs); 433828415Speter return Z_MEM_ERROR; /* not enough memory */ 433928415Speter } 434028415Speter#ifdef DEBUG_ZLIB 434128415Speter inflate_hufts += z + 1; 434228415Speter#endif 434328415Speter *t = q + 1; /* link to list for huft_free() */ 434428415Speter *(t = &(q->next)) = Z_NULL; 434528415Speter u[h] = ++q; /* table starts after link */ 434628415Speter 434728415Speter /* connect to last table, if there is one */ 434828415Speter if (h) 434928415Speter { 435028415Speter x[h] = i; /* save pattern for backing up */ 435128415Speter r.bits = (Byte)l; /* bits to dump before this table */ 435228415Speter r.exop = (Byte)j; /* bits in this table */ 435328415Speter r.next = q; /* pointer to this table */ 435428415Speter j = i >> (w - l); /* (get around Turbo C bug) */ 435528415Speter u[h-1][j] = r; /* connect to last table */ 435628415Speter } 435728415Speter } 435828415Speter 435928415Speter /* set up table entry in r */ 436028415Speter r.bits = (Byte)(k - w); 436128415Speter if (p >= v + n) 436228415Speter r.exop = 128 + 64; /* out of values--invalid code */ 436328415Speter else if (*p < s) 436428415Speter { 436528415Speter r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ 436628415Speter r.base = *p++; /* simple code is just the value */ 436728415Speter } 436828415Speter else 436928415Speter { 437034768Speter r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */ 437128415Speter r.base = d[*p++ - s]; 437228415Speter } 437328415Speter 437428415Speter /* fill code-like entries with r */ 437528415Speter f = 1 << (k - w); 437628415Speter for (j = i >> w; j < z; j += f) 437728415Speter q[j] = r; 437828415Speter 437928415Speter /* backwards increment the k-bit code i */ 438028415Speter for (j = 1 << (k - 1); i & j; j >>= 1) 438128415Speter i ^= j; 438228415Speter i ^= j; 438328415Speter 438428415Speter /* backup over finished tables */ 438528415Speter while ((i & ((1 << w) - 1)) != x[h]) 438628415Speter { 438728415Speter h--; /* don't need to update q */ 438828415Speter w -= l; 438928415Speter } 439028415Speter } 439128415Speter } 439228415Speter 439328415Speter 439428415Speter /* Return Z_BUF_ERROR if we were given an incomplete table */ 439528415Speter return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; 439628415Speter} 439728415Speter 439828415Speter 439934768Speterint inflate_trees_bits(c, bb, tb, z) 440028415SpeteruIntf *c; /* 19 code lengths */ 440128415SpeteruIntf *bb; /* bits tree desired/actual depth */ 440228415Speterinflate_huft * FAR *tb; /* bits tree result */ 440334768Speterz_streamp z; /* for zfree function */ 440428415Speter{ 440528415Speter int r; 440628415Speter 440728415Speter r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z); 440828415Speter if (r == Z_DATA_ERROR) 440934768Speter z->msg = (char*)"oversubscribed dynamic bit lengths tree"; 441034768Speter else if (r == Z_BUF_ERROR || *bb == 0) 441128415Speter { 441228415Speter inflate_trees_free(*tb, z); 441334768Speter z->msg = (char*)"incomplete dynamic bit lengths tree"; 441428415Speter r = Z_DATA_ERROR; 441528415Speter } 441628415Speter return r; 441728415Speter} 441828415Speter 441928415Speter 442034768Speterint inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z) 442128415SpeteruInt nl; /* number of literal/length codes */ 442228415SpeteruInt nd; /* number of distance codes */ 442328415SpeteruIntf *c; /* that many (total) code lengths */ 442428415SpeteruIntf *bl; /* literal desired/actual bit depth */ 442528415SpeteruIntf *bd; /* distance desired/actual bit depth */ 442628415Speterinflate_huft * FAR *tl; /* literal/length tree result */ 442728415Speterinflate_huft * FAR *td; /* distance tree result */ 442834768Speterz_streamp z; /* for zfree function */ 442928415Speter{ 443028415Speter int r; 443128415Speter 443228415Speter /* build literal/length tree */ 443334768Speter r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z); 443434768Speter if (r != Z_OK || *bl == 0) 443528415Speter { 443628415Speter if (r == Z_DATA_ERROR) 443734768Speter z->msg = (char*)"oversubscribed literal/length tree"; 443834768Speter else if (r != Z_MEM_ERROR) 443928415Speter { 444028415Speter inflate_trees_free(*tl, z); 444134768Speter z->msg = (char*)"incomplete literal/length tree"; 444228415Speter r = Z_DATA_ERROR; 444328415Speter } 444428415Speter return r; 444528415Speter } 444628415Speter 444728415Speter /* build distance tree */ 444834768Speter r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z); 444934768Speter if (r != Z_OK || (*bd == 0 && nl > 257)) 445028415Speter { 445128415Speter if (r == Z_DATA_ERROR) 445234768Speter z->msg = (char*)"oversubscribed distance tree"; 445328415Speter else if (r == Z_BUF_ERROR) { 445428415Speter#ifdef PKZIP_BUG_WORKAROUND 445528415Speter r = Z_OK; 445628415Speter } 445728415Speter#else 445828415Speter inflate_trees_free(*td, z); 445934768Speter z->msg = (char*)"incomplete distance tree"; 446028415Speter r = Z_DATA_ERROR; 446128415Speter } 446234768Speter else if (r != Z_MEM_ERROR) 446334768Speter { 446434768Speter z->msg = (char*)"empty distance tree with lengths"; 446534768Speter r = Z_DATA_ERROR; 446634768Speter } 446728415Speter inflate_trees_free(*tl, z); 446828415Speter return r; 446928415Speter#endif 447028415Speter } 447128415Speter 447228415Speter /* done */ 447328415Speter return Z_OK; 447428415Speter} 447528415Speter 447628415Speter 447728415Speter/* build fixed tables only once--keep them here */ 447828415Speterlocal int fixed_built = 0; 447928415Speter#define FIXEDH 530 /* number of hufts used by fixed tables */ 448028415Speterlocal inflate_huft fixed_mem[FIXEDH]; 448128415Speterlocal uInt fixed_bl; 448228415Speterlocal uInt fixed_bd; 448328415Speterlocal inflate_huft *fixed_tl; 448428415Speterlocal inflate_huft *fixed_td; 448528415Speter 448628415Speter 448728415Speterlocal voidpf falloc(q, n, s) 448834768Spetervoidpf q; /* opaque pointer */ 448928415SpeteruInt n; /* number of items */ 449028415SpeteruInt s; /* size of item */ 449128415Speter{ 449234768Speter Assert(s == sizeof(inflate_huft) && n <= *(intf *)q, 449328415Speter "inflate_trees falloc overflow"); 449434768Speter *(intf *)q -= n+s-s; /* s-s to avoid warning */ 449534768Speter return (voidpf)(fixed_mem + *(intf *)q); 449628415Speter} 449728415Speter 449828415Speter 449934768Speterint inflate_trees_fixed(bl, bd, tl, td) 450028415SpeteruIntf *bl; /* literal desired/actual bit depth */ 450128415SpeteruIntf *bd; /* distance desired/actual bit depth */ 450228415Speterinflate_huft * FAR *tl; /* literal/length tree result */ 450328415Speterinflate_huft * FAR *td; /* distance tree result */ 450428415Speter{ 450534768Speter /* build fixed tables if not already (multiple overlapped executions ok) */ 450628415Speter if (!fixed_built) 450728415Speter { 450828415Speter int k; /* temporary variable */ 450928415Speter unsigned c[288]; /* length list for huft_build */ 451028415Speter z_stream z; /* for falloc function */ 451134768Speter int f = FIXEDH; /* number of hufts left in fixed_mem */ 451228415Speter 451328415Speter /* set up fake z_stream for memory routines */ 451428415Speter z.zalloc = falloc; 451534768Speter z.zfree = Z_NULL; 451634768Speter z.opaque = (voidpf)&f; 451728415Speter 451828415Speter /* literal table */ 451928415Speter for (k = 0; k < 144; k++) 452028415Speter c[k] = 8; 452128415Speter for (; k < 256; k++) 452228415Speter c[k] = 9; 452328415Speter for (; k < 280; k++) 452428415Speter c[k] = 7; 452528415Speter for (; k < 288; k++) 452628415Speter c[k] = 8; 452728415Speter fixed_bl = 7; 452828415Speter huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z); 452928415Speter 453028415Speter /* distance table */ 453128415Speter for (k = 0; k < 30; k++) 453228415Speter c[k] = 5; 453328415Speter fixed_bd = 5; 453428415Speter huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z); 453528415Speter 453628415Speter /* done */ 453734768Speter Assert(f == 0, "invalid build of fixed tables"); 453828415Speter fixed_built = 1; 453928415Speter } 454028415Speter *bl = fixed_bl; 454128415Speter *bd = fixed_bd; 454228415Speter *tl = fixed_tl; 454328415Speter *td = fixed_td; 454428415Speter return Z_OK; 454528415Speter} 454628415Speter 454728415Speter 454834768Speterint inflate_trees_free(t, z) 454928415Speterinflate_huft *t; /* table to free */ 455034768Speterz_streamp z; /* for zfree function */ 455128415Speter/* Free the malloc'ed tables built by huft_build(), which makes a linked 455228415Speter list of the tables it made, with the links in a dummy first entry of 455328415Speter each table. */ 455428415Speter{ 455534768Speter register inflate_huft *p, *q, *r; 455628415Speter 455734768Speter /* Reverse linked list */ 455834768Speter p = Z_NULL; 455934768Speter q = t; 456034768Speter while (q != Z_NULL) 456134768Speter { 456234768Speter r = (q - 1)->next; 456334768Speter (q - 1)->next = p; 456434768Speter p = q; 456534768Speter q = r; 456634768Speter } 456728415Speter /* Go through linked list, freeing from the malloced (t[-1]) address. */ 456828415Speter while (p != Z_NULL) 456928415Speter { 457028415Speter q = (--p)->next; 457134768Speter ZFREE(z,p); 457228415Speter p = q; 457328415Speter } 457428415Speter return Z_OK; 457528415Speter} 457634768Speter/* --- inftrees.c */ 457728415Speter 457834768Speter/* +++ infcodes.c */ 457928415Speter/* infcodes.c -- process literals and length/distance pairs 458034768Speter * Copyright (C) 1995-1996 Mark Adler 458128415Speter * For conditions of distribution and use, see copyright notice in zlib.h 458228415Speter */ 458328415Speter 458434768Speter/* #include "zutil.h" */ 458534768Speter/* #include "inftrees.h" */ 458634768Speter/* #include "infblock.h" */ 458734768Speter/* #include "infcodes.h" */ 458834768Speter/* #include "infutil.h" */ 458934768Speter 459034768Speter/* +++ inffast.h */ 459134768Speter/* inffast.h -- header to use inffast.c 459234768Speter * Copyright (C) 1995-1996 Mark Adler 459334768Speter * For conditions of distribution and use, see copyright notice in zlib.h 459434768Speter */ 459534768Speter 459634768Speter/* WARNING: this file should *not* be used by applications. It is 459734768Speter part of the implementation of the compression library and is 459834768Speter subject to change. Applications should only use zlib.h. 459934768Speter */ 460034768Speter 460134768Speterextern int inflate_fast OF(( 460234768Speter uInt, 460334768Speter uInt, 460434768Speter inflate_huft *, 460534768Speter inflate_huft *, 460634768Speter inflate_blocks_statef *, 460734768Speter z_streamp )); 460834768Speter/* --- inffast.h */ 460934768Speter 461028415Speter/* simplify the use of the inflate_huft type with some defines */ 461128415Speter#define base more.Base 461228415Speter#define next more.Next 461328415Speter#define exop word.what.Exop 461428415Speter#define bits word.what.Bits 461528415Speter 461628415Speter/* inflate codes private state */ 461728415Speterstruct inflate_codes_state { 461828415Speter 461928415Speter /* mode */ 462028415Speter enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 462128415Speter START, /* x: set up for LEN */ 462228415Speter LEN, /* i: get length/literal/eob next */ 462328415Speter LENEXT, /* i: getting length extra (have base) */ 462428415Speter DIST, /* i: get distance next */ 462528415Speter DISTEXT, /* i: getting distance extra */ 462628415Speter COPY, /* o: copying bytes in window, waiting for space */ 462728415Speter LIT, /* o: got literal, waiting for output space */ 462828415Speter WASH, /* o: got eob, possibly still output waiting */ 462928415Speter END, /* x: got eob and all data flushed */ 463028415Speter BADCODE} /* x: got error */ 463128415Speter mode; /* current inflate_codes mode */ 463228415Speter 463328415Speter /* mode dependent information */ 463428415Speter uInt len; 463528415Speter union { 463628415Speter struct { 463728415Speter inflate_huft *tree; /* pointer into tree */ 463828415Speter uInt need; /* bits needed */ 463928415Speter } code; /* if LEN or DIST, where in tree */ 464028415Speter uInt lit; /* if LIT, literal */ 464128415Speter struct { 464228415Speter uInt get; /* bits to get for extra */ 464328415Speter uInt dist; /* distance back to copy from */ 464428415Speter } copy; /* if EXT or COPY, where and how much */ 464528415Speter } sub; /* submode */ 464628415Speter 464728415Speter /* mode independent information */ 464828415Speter Byte lbits; /* ltree bits decoded per branch */ 464928415Speter Byte dbits; /* dtree bits decoder per branch */ 465028415Speter inflate_huft *ltree; /* literal/length/eob tree */ 465128415Speter inflate_huft *dtree; /* distance tree */ 465228415Speter 465328415Speter}; 465428415Speter 465528415Speter 465634768Speterinflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z) 465728415SpeteruInt bl, bd; 465834768Speterinflate_huft *tl; 465934768Speterinflate_huft *td; /* need separate declaration for Borland C++ */ 466034768Speterz_streamp z; 466128415Speter{ 466228415Speter inflate_codes_statef *c; 466328415Speter 466428415Speter if ((c = (inflate_codes_statef *) 466528415Speter ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL) 466628415Speter { 466728415Speter c->mode = START; 466828415Speter c->lbits = (Byte)bl; 466928415Speter c->dbits = (Byte)bd; 467028415Speter c->ltree = tl; 467128415Speter c->dtree = td; 467228415Speter Tracev((stderr, "inflate: codes new\n")); 467328415Speter } 467428415Speter return c; 467528415Speter} 467628415Speter 467728415Speter 467834768Speterint inflate_codes(s, z, r) 467928415Speterinflate_blocks_statef *s; 468034768Speterz_streamp z; 468128415Speterint r; 468228415Speter{ 468328415Speter uInt j; /* temporary storage */ 468428415Speter inflate_huft *t; /* temporary pointer */ 468528415Speter uInt e; /* extra bits or operation */ 468628415Speter uLong b; /* bit buffer */ 468728415Speter uInt k; /* bits in bit buffer */ 468828415Speter Bytef *p; /* input data pointer */ 468928415Speter uInt n; /* bytes available there */ 469028415Speter Bytef *q; /* output window write pointer */ 469128415Speter uInt m; /* bytes to end of window or read pointer */ 469228415Speter Bytef *f; /* pointer to copy strings from */ 469328415Speter inflate_codes_statef *c = s->sub.decode.codes; /* codes state */ 469428415Speter 469528415Speter /* copy input/output information to locals (UPDATE macro restores) */ 469628415Speter LOAD 469728415Speter 469828415Speter /* process input and output based on current state */ 469928415Speter while (1) switch (c->mode) 470028415Speter { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 470128415Speter case START: /* x: set up for LEN */ 470228415Speter#ifndef SLOW 470328415Speter if (m >= 258 && n >= 10) 470428415Speter { 470528415Speter UPDATE 470628415Speter r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); 470728415Speter LOAD 470828415Speter if (r != Z_OK) 470928415Speter { 471028415Speter c->mode = r == Z_STREAM_END ? WASH : BADCODE; 471128415Speter break; 471228415Speter } 471328415Speter } 471428415Speter#endif /* !SLOW */ 471528415Speter c->sub.code.need = c->lbits; 471628415Speter c->sub.code.tree = c->ltree; 471728415Speter c->mode = LEN; 471828415Speter case LEN: /* i: get length/literal/eob next */ 471928415Speter j = c->sub.code.need; 472028415Speter NEEDBITS(j) 472128415Speter t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 472228415Speter DUMPBITS(t->bits) 472328415Speter e = (uInt)(t->exop); 472428415Speter if (e == 0) /* literal */ 472528415Speter { 472628415Speter c->sub.lit = t->base; 472728415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 472828415Speter "inflate: literal '%c'\n" : 472928415Speter "inflate: literal 0x%02x\n", t->base)); 473028415Speter c->mode = LIT; 473128415Speter break; 473228415Speter } 473328415Speter if (e & 16) /* length */ 473428415Speter { 473528415Speter c->sub.copy.get = e & 15; 473628415Speter c->len = t->base; 473728415Speter c->mode = LENEXT; 473828415Speter break; 473928415Speter } 474028415Speter if ((e & 64) == 0) /* next table */ 474128415Speter { 474228415Speter c->sub.code.need = e; 474328415Speter c->sub.code.tree = t->next; 474428415Speter break; 474528415Speter } 474628415Speter if (e & 32) /* end of block */ 474728415Speter { 474828415Speter Tracevv((stderr, "inflate: end of block\n")); 474928415Speter c->mode = WASH; 475028415Speter break; 475128415Speter } 475228415Speter c->mode = BADCODE; /* invalid code */ 475334768Speter z->msg = (char*)"invalid literal/length code"; 475428415Speter r = Z_DATA_ERROR; 475528415Speter LEAVE 475628415Speter case LENEXT: /* i: getting length extra (have base) */ 475728415Speter j = c->sub.copy.get; 475828415Speter NEEDBITS(j) 475928415Speter c->len += (uInt)b & inflate_mask[j]; 476028415Speter DUMPBITS(j) 476128415Speter c->sub.code.need = c->dbits; 476228415Speter c->sub.code.tree = c->dtree; 476328415Speter Tracevv((stderr, "inflate: length %u\n", c->len)); 476428415Speter c->mode = DIST; 476528415Speter case DIST: /* i: get distance next */ 476628415Speter j = c->sub.code.need; 476728415Speter NEEDBITS(j) 476828415Speter t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 476928415Speter DUMPBITS(t->bits) 477028415Speter e = (uInt)(t->exop); 477128415Speter if (e & 16) /* distance */ 477228415Speter { 477328415Speter c->sub.copy.get = e & 15; 477428415Speter c->sub.copy.dist = t->base; 477528415Speter c->mode = DISTEXT; 477628415Speter break; 477728415Speter } 477828415Speter if ((e & 64) == 0) /* next table */ 477928415Speter { 478028415Speter c->sub.code.need = e; 478128415Speter c->sub.code.tree = t->next; 478228415Speter break; 478328415Speter } 478428415Speter c->mode = BADCODE; /* invalid code */ 478534768Speter z->msg = (char*)"invalid distance code"; 478628415Speter r = Z_DATA_ERROR; 478728415Speter LEAVE 478828415Speter case DISTEXT: /* i: getting distance extra */ 478928415Speter j = c->sub.copy.get; 479028415Speter NEEDBITS(j) 479128415Speter c->sub.copy.dist += (uInt)b & inflate_mask[j]; 479228415Speter DUMPBITS(j) 479328415Speter Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist)); 479428415Speter c->mode = COPY; 479528415Speter case COPY: /* o: copying bytes in window, waiting for space */ 479628415Speter#ifndef __TURBOC__ /* Turbo C bug for following expression */ 479728415Speter f = (uInt)(q - s->window) < c->sub.copy.dist ? 479828415Speter s->end - (c->sub.copy.dist - (q - s->window)) : 479928415Speter q - c->sub.copy.dist; 480028415Speter#else 480128415Speter f = q - c->sub.copy.dist; 480228415Speter if ((uInt)(q - s->window) < c->sub.copy.dist) 480334768Speter f = s->end - (c->sub.copy.dist - (uInt)(q - s->window)); 480428415Speter#endif 480528415Speter while (c->len) 480628415Speter { 480728415Speter NEEDOUT 480828415Speter OUTBYTE(*f++) 480928415Speter if (f == s->end) 481028415Speter f = s->window; 481128415Speter c->len--; 481228415Speter } 481328415Speter c->mode = START; 481428415Speter break; 481528415Speter case LIT: /* o: got literal, waiting for output space */ 481628415Speter NEEDOUT 481728415Speter OUTBYTE(c->sub.lit) 481828415Speter c->mode = START; 481928415Speter break; 482028415Speter case WASH: /* o: got eob, possibly more output */ 482128415Speter FLUSH 482228415Speter if (s->read != s->write) 482328415Speter LEAVE 482428415Speter c->mode = END; 482528415Speter case END: 482628415Speter r = Z_STREAM_END; 482728415Speter LEAVE 482828415Speter case BADCODE: /* x: got error */ 482928415Speter r = Z_DATA_ERROR; 483028415Speter LEAVE 483128415Speter default: 483228415Speter r = Z_STREAM_ERROR; 483328415Speter LEAVE 483428415Speter } 483528415Speter} 483628415Speter 483728415Speter 483834768Spetervoid inflate_codes_free(c, z) 483928415Speterinflate_codes_statef *c; 484034768Speterz_streamp z; 484128415Speter{ 484234768Speter ZFREE(z, c); 484328415Speter Tracev((stderr, "inflate: codes free\n")); 484428415Speter} 484534768Speter/* --- infcodes.c */ 484628415Speter 484734768Speter/* +++ infutil.c */ 484828415Speter/* inflate_util.c -- data and routines common to blocks and codes 484934768Speter * Copyright (C) 1995-1996 Mark Adler 485028415Speter * For conditions of distribution and use, see copyright notice in zlib.h 485128415Speter */ 485228415Speter 485334768Speter/* #include "zutil.h" */ 485434768Speter/* #include "infblock.h" */ 485534768Speter/* #include "inftrees.h" */ 485634768Speter/* #include "infcodes.h" */ 485734768Speter/* #include "infutil.h" */ 485834768Speter 485934768Speter#ifndef NO_DUMMY_DECL 486034768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 486134768Speter#endif 486234768Speter 486334768Speter/* And'ing with mask[n] masks the lower n bits */ 486434768SpeteruInt inflate_mask[17] = { 486534768Speter 0x0000, 486634768Speter 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 486734768Speter 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 486834768Speter}; 486934768Speter 487034768Speter 487128415Speter/* copy as much as possible from the sliding window to the output area */ 487234768Speterint inflate_flush(s, z, r) 487328415Speterinflate_blocks_statef *s; 487434768Speterz_streamp z; 487528415Speterint r; 487628415Speter{ 487728415Speter uInt n; 487834768Speter Bytef *p; 487934768Speter Bytef *q; 488028415Speter 488128415Speter /* local copies of source and destination pointers */ 488228415Speter p = z->next_out; 488328415Speter q = s->read; 488428415Speter 488528415Speter /* compute number of bytes to copy as far as end of window */ 488628415Speter n = (uInt)((q <= s->write ? s->write : s->end) - q); 488728415Speter if (n > z->avail_out) n = z->avail_out; 488828415Speter if (n && r == Z_BUF_ERROR) r = Z_OK; 488928415Speter 489028415Speter /* update counters */ 489128415Speter z->avail_out -= n; 489228415Speter z->total_out += n; 489328415Speter 489428415Speter /* update check information */ 489528415Speter if (s->checkfn != Z_NULL) 489634768Speter z->adler = s->check = (*s->checkfn)(s->check, q, n); 489728415Speter 489828415Speter /* copy as far as end of window */ 489934768Speter if (p != Z_NULL) { 490028415Speter zmemcpy(p, q, n); 490128415Speter p += n; 490228415Speter } 490328415Speter q += n; 490428415Speter 490528415Speter /* see if more to copy at beginning of window */ 490628415Speter if (q == s->end) 490728415Speter { 490828415Speter /* wrap pointers */ 490928415Speter q = s->window; 491028415Speter if (s->write == s->end) 491128415Speter s->write = s->window; 491228415Speter 491328415Speter /* compute bytes to copy */ 491428415Speter n = (uInt)(s->write - q); 491528415Speter if (n > z->avail_out) n = z->avail_out; 491628415Speter if (n && r == Z_BUF_ERROR) r = Z_OK; 491728415Speter 491828415Speter /* update counters */ 491928415Speter z->avail_out -= n; 492028415Speter z->total_out += n; 492128415Speter 492228415Speter /* update check information */ 492328415Speter if (s->checkfn != Z_NULL) 492434768Speter z->adler = s->check = (*s->checkfn)(s->check, q, n); 492528415Speter 492628415Speter /* copy */ 492734768Speter if (p != Z_NULL) { 492828415Speter zmemcpy(p, q, n); 492928415Speter p += n; 493028415Speter } 493128415Speter q += n; 493228415Speter } 493328415Speter 493428415Speter /* update pointers */ 493528415Speter z->next_out = p; 493628415Speter s->read = q; 493728415Speter 493828415Speter /* done */ 493928415Speter return r; 494028415Speter} 494134768Speter/* --- infutil.c */ 494228415Speter 494334768Speter/* +++ inffast.c */ 494428415Speter/* inffast.c -- process literals and length/distance pairs fast 494534768Speter * Copyright (C) 1995-1996 Mark Adler 494628415Speter * For conditions of distribution and use, see copyright notice in zlib.h 494728415Speter */ 494828415Speter 494934768Speter/* #include "zutil.h" */ 495034768Speter/* #include "inftrees.h" */ 495134768Speter/* #include "infblock.h" */ 495234768Speter/* #include "infcodes.h" */ 495334768Speter/* #include "infutil.h" */ 495434768Speter/* #include "inffast.h" */ 495534768Speter 495634768Speter#ifndef NO_DUMMY_DECL 495734768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 495834768Speter#endif 495934768Speter 496028415Speter/* simplify the use of the inflate_huft type with some defines */ 496128415Speter#define base more.Base 496228415Speter#define next more.Next 496328415Speter#define exop word.what.Exop 496428415Speter#define bits word.what.Bits 496528415Speter 496628415Speter/* macros for bit input with no checking and for returning unused bytes */ 496728415Speter#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} 496828415Speter#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;} 496928415Speter 497028415Speter/* Called with number of bytes left to write in window at least 258 497128415Speter (the maximum string length) and number of input bytes available 497228415Speter at least ten. The ten bytes are six bytes for the longest length/ 497328415Speter distance pair plus four bytes for overloading the bit buffer. */ 497428415Speter 497534768Speterint inflate_fast(bl, bd, tl, td, s, z) 497628415SpeteruInt bl, bd; 497734768Speterinflate_huft *tl; 497834768Speterinflate_huft *td; /* need separate declaration for Borland C++ */ 497928415Speterinflate_blocks_statef *s; 498034768Speterz_streamp z; 498128415Speter{ 498228415Speter inflate_huft *t; /* temporary pointer */ 498328415Speter uInt e; /* extra bits or operation */ 498428415Speter uLong b; /* bit buffer */ 498528415Speter uInt k; /* bits in bit buffer */ 498628415Speter Bytef *p; /* input data pointer */ 498728415Speter uInt n; /* bytes available there */ 498828415Speter Bytef *q; /* output window write pointer */ 498928415Speter uInt m; /* bytes to end of window or read pointer */ 499028415Speter uInt ml; /* mask for literal/length tree */ 499128415Speter uInt md; /* mask for distance tree */ 499228415Speter uInt c; /* bytes to copy */ 499328415Speter uInt d; /* distance back to copy from */ 499428415Speter Bytef *r; /* copy source pointer */ 499528415Speter 499628415Speter /* load input, output, bit values */ 499728415Speter LOAD 499828415Speter 499928415Speter /* initialize masks */ 500028415Speter ml = inflate_mask[bl]; 500128415Speter md = inflate_mask[bd]; 500228415Speter 500328415Speter /* do until not enough input or output space for fast loop */ 500428415Speter do { /* assume called with m >= 258 && n >= 10 */ 500528415Speter /* get literal/length code */ 500628415Speter GRABBITS(20) /* max bits for literal/length code */ 500728415Speter if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) 500828415Speter { 500928415Speter DUMPBITS(t->bits) 501028415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 501128415Speter "inflate: * literal '%c'\n" : 501228415Speter "inflate: * literal 0x%02x\n", t->base)); 501328415Speter *q++ = (Byte)t->base; 501428415Speter m--; 501528415Speter continue; 501628415Speter } 501728415Speter do { 501828415Speter DUMPBITS(t->bits) 501928415Speter if (e & 16) 502028415Speter { 502128415Speter /* get extra bits for length */ 502228415Speter e &= 15; 502328415Speter c = t->base + ((uInt)b & inflate_mask[e]); 502428415Speter DUMPBITS(e) 502528415Speter Tracevv((stderr, "inflate: * length %u\n", c)); 502628415Speter 502728415Speter /* decode distance base of block to copy */ 502828415Speter GRABBITS(15); /* max bits for distance code */ 502928415Speter e = (t = td + ((uInt)b & md))->exop; 503028415Speter do { 503128415Speter DUMPBITS(t->bits) 503228415Speter if (e & 16) 503328415Speter { 503428415Speter /* get extra bits to add to distance base */ 503528415Speter e &= 15; 503628415Speter GRABBITS(e) /* get extra bits (up to 13) */ 503728415Speter d = t->base + ((uInt)b & inflate_mask[e]); 503828415Speter DUMPBITS(e) 503928415Speter Tracevv((stderr, "inflate: * distance %u\n", d)); 504028415Speter 504128415Speter /* do the copy */ 504228415Speter m -= c; 504328415Speter if ((uInt)(q - s->window) >= d) /* offset before dest */ 504428415Speter { /* just copy */ 504528415Speter r = q - d; 504628415Speter *q++ = *r++; c--; /* minimum count is three, */ 504728415Speter *q++ = *r++; c--; /* so unroll loop a little */ 504828415Speter } 504928415Speter else /* else offset after destination */ 505028415Speter { 505134768Speter e = d - (uInt)(q - s->window); /* bytes from offset to end */ 505228415Speter r = s->end - e; /* pointer to offset */ 505328415Speter if (c > e) /* if source crosses, */ 505428415Speter { 505528415Speter c -= e; /* copy to end of window */ 505628415Speter do { 505728415Speter *q++ = *r++; 505828415Speter } while (--e); 505928415Speter r = s->window; /* copy rest from start of window */ 506028415Speter } 506128415Speter } 506228415Speter do { /* copy all or what's left */ 506328415Speter *q++ = *r++; 506428415Speter } while (--c); 506528415Speter break; 506628415Speter } 506728415Speter else if ((e & 64) == 0) 506828415Speter e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop; 506928415Speter else 507028415Speter { 507134768Speter z->msg = (char*)"invalid distance code"; 507228415Speter UNGRAB 507328415Speter UPDATE 507428415Speter return Z_DATA_ERROR; 507528415Speter } 507628415Speter } while (1); 507728415Speter break; 507828415Speter } 507928415Speter if ((e & 64) == 0) 508028415Speter { 508128415Speter if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0) 508228415Speter { 508328415Speter DUMPBITS(t->bits) 508428415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 508528415Speter "inflate: * literal '%c'\n" : 508628415Speter "inflate: * literal 0x%02x\n", t->base)); 508728415Speter *q++ = (Byte)t->base; 508828415Speter m--; 508928415Speter break; 509028415Speter } 509128415Speter } 509228415Speter else if (e & 32) 509328415Speter { 509428415Speter Tracevv((stderr, "inflate: * end of block\n")); 509528415Speter UNGRAB 509628415Speter UPDATE 509728415Speter return Z_STREAM_END; 509828415Speter } 509928415Speter else 510028415Speter { 510134768Speter z->msg = (char*)"invalid literal/length code"; 510228415Speter UNGRAB 510328415Speter UPDATE 510428415Speter return Z_DATA_ERROR; 510528415Speter } 510628415Speter } while (1); 510728415Speter } while (m >= 258 && n >= 10); 510828415Speter 510928415Speter /* not enough input or output--restore pointers and return */ 511028415Speter UNGRAB 511128415Speter UPDATE 511228415Speter return Z_OK; 511328415Speter} 511434768Speter/* --- inffast.c */ 511528415Speter 511634768Speter/* +++ zutil.c */ 511728415Speter/* zutil.c -- target dependent utility functions for the compression library 511834768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 511928415Speter * For conditions of distribution and use, see copyright notice in zlib.h 512028415Speter */ 512128415Speter 512234768Speter/* From: zutil.c,v 1.17 1996/07/24 13:41:12 me Exp $ */ 512328415Speter 512434768Speter#ifdef DEBUG_ZLIB 512534768Speter#include <stdio.h> 512634768Speter#endif 512728415Speter 512834768Speter/* #include "zutil.h" */ 512934768Speter 513034768Speter#ifndef NO_DUMMY_DECL 513134768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 513234768Speter#endif 513334768Speter 513434768Speter#ifndef STDC 513534768Speterextern void exit OF((int)); 513634768Speter#endif 513734768Speter 513834768Speterstatic const char *z_errmsg[10] = { 513934768Speter"need dictionary", /* Z_NEED_DICT 2 */ 514034768Speter"stream end", /* Z_STREAM_END 1 */ 514134768Speter"", /* Z_OK 0 */ 514234768Speter"file error", /* Z_ERRNO (-1) */ 514334768Speter"stream error", /* Z_STREAM_ERROR (-2) */ 514434768Speter"data error", /* Z_DATA_ERROR (-3) */ 514534768Speter"insufficient memory", /* Z_MEM_ERROR (-4) */ 514634768Speter"buffer error", /* Z_BUF_ERROR (-5) */ 514734768Speter"incompatible version",/* Z_VERSION_ERROR (-6) */ 514828415Speter""}; 514928415Speter 515028415Speter 515134768Speterconst char *zlibVersion() 515234768Speter{ 515334768Speter return ZLIB_VERSION; 515434768Speter} 515534768Speter 515634768Speter#ifdef DEBUG_ZLIB 515734768Spetervoid z_error (m) 515834768Speter char *m; 515934768Speter{ 516034768Speter fprintf(stderr, "%s\n", m); 516134768Speter exit(1); 516234768Speter} 516334768Speter#endif 516434768Speter 516534768Speter#ifndef HAVE_MEMCPY 516634768Speter 516734768Spetervoid zmemcpy(dest, source, len) 516834768Speter Bytef* dest; 516934768Speter Bytef* source; 517034768Speter uInt len; 517134768Speter{ 517234768Speter if (len == 0) return; 517334768Speter do { 517434768Speter *dest++ = *source++; /* ??? to be unrolled */ 517534768Speter } while (--len != 0); 517634768Speter} 517734768Speter 517834768Speterint zmemcmp(s1, s2, len) 517934768Speter Bytef* s1; 518034768Speter Bytef* s2; 518134768Speter uInt len; 518234768Speter{ 518334768Speter uInt j; 518434768Speter 518534768Speter for (j = 0; j < len; j++) { 518634768Speter if (s1[j] != s2[j]) return 2*(s1[j] > s2[j])-1; 518734768Speter } 518834768Speter return 0; 518934768Speter} 519034768Speter 519134768Spetervoid zmemzero(dest, len) 519234768Speter Bytef* dest; 519334768Speter uInt len; 519434768Speter{ 519534768Speter if (len == 0) return; 519634768Speter do { 519734768Speter *dest++ = 0; /* ??? to be unrolled */ 519834768Speter } while (--len != 0); 519934768Speter} 520034768Speter#endif 520134768Speter 520234768Speter#ifdef __TURBOC__ 520334768Speter#if (defined( __BORLANDC__) || !defined(SMALL_MEDIUM)) && !defined(__32BIT__) 520434768Speter/* Small and medium model in Turbo C are for now limited to near allocation 520534768Speter * with reduced MAX_WBITS and MAX_MEM_LEVEL 520634768Speter */ 520734768Speter# define MY_ZCALLOC 520834768Speter 520934768Speter/* Turbo C malloc() does not allow dynamic allocation of 64K bytes 521034768Speter * and farmalloc(64K) returns a pointer with an offset of 8, so we 521134768Speter * must fix the pointer. Warning: the pointer must be put back to its 521234768Speter * original form in order to free it, use zcfree(). 521334768Speter */ 521434768Speter 521534768Speter#define MAX_PTR 10 521634768Speter/* 10*64K = 640K */ 521734768Speter 521834768Speterlocal int next_ptr = 0; 521934768Speter 522034768Spetertypedef struct ptr_table_s { 522134768Speter voidpf org_ptr; 522234768Speter voidpf new_ptr; 522334768Speter} ptr_table; 522434768Speter 522534768Speterlocal ptr_table table[MAX_PTR]; 522634768Speter/* This table is used to remember the original form of pointers 522734768Speter * to large buffers (64K). Such pointers are normalized with a zero offset. 522834768Speter * Since MSDOS is not a preemptive multitasking OS, this table is not 522934768Speter * protected from concurrent access. This hack doesn't work anyway on 523034768Speter * a protected system like OS/2. Use Microsoft C instead. 523134768Speter */ 523234768Speter 523334768Spetervoidpf zcalloc (voidpf opaque, unsigned items, unsigned size) 523434768Speter{ 523534768Speter voidpf buf = opaque; /* just to make some compilers happy */ 523634768Speter ulg bsize = (ulg)items*size; 523734768Speter 523834768Speter /* If we allocate less than 65520 bytes, we assume that farmalloc 523934768Speter * will return a usable pointer which doesn't have to be normalized. 524034768Speter */ 524134768Speter if (bsize < 65520L) { 524234768Speter buf = farmalloc(bsize); 524334768Speter if (*(ush*)&buf != 0) return buf; 524434768Speter } else { 524534768Speter buf = farmalloc(bsize + 16L); 524634768Speter } 524734768Speter if (buf == NULL || next_ptr >= MAX_PTR) return NULL; 524834768Speter table[next_ptr].org_ptr = buf; 524934768Speter 525034768Speter /* Normalize the pointer to seg:0 */ 525134768Speter *((ush*)&buf+1) += ((ush)((uch*)buf-0) + 15) >> 4; 525234768Speter *(ush*)&buf = 0; 525334768Speter table[next_ptr++].new_ptr = buf; 525434768Speter return buf; 525534768Speter} 525634768Speter 525734768Spetervoid zcfree (voidpf opaque, voidpf ptr) 525834768Speter{ 525934768Speter int n; 526034768Speter if (*(ush*)&ptr != 0) { /* object < 64K */ 526134768Speter farfree(ptr); 526234768Speter return; 526334768Speter } 526434768Speter /* Find the original pointer */ 526534768Speter for (n = 0; n < next_ptr; n++) { 526634768Speter if (ptr != table[n].new_ptr) continue; 526734768Speter 526834768Speter farfree(table[n].org_ptr); 526934768Speter while (++n < next_ptr) { 527034768Speter table[n-1] = table[n]; 527134768Speter } 527234768Speter next_ptr--; 527334768Speter return; 527434768Speter } 527534768Speter ptr = opaque; /* just to make some compilers happy */ 527634768Speter Assert(0, "zcfree: ptr not found"); 527734768Speter} 527834768Speter#endif 527934768Speter#endif /* __TURBOC__ */ 528034768Speter 528134768Speter 528234768Speter#if defined(M_I86) && !defined(__32BIT__) 528334768Speter/* Microsoft C in 16-bit mode */ 528434768Speter 528534768Speter# define MY_ZCALLOC 528634768Speter 528734768Speter#if (!defined(_MSC_VER) || (_MSC_VER < 600)) 528834768Speter# define _halloc halloc 528934768Speter# define _hfree hfree 529034768Speter#endif 529134768Speter 529234768Spetervoidpf zcalloc (voidpf opaque, unsigned items, unsigned size) 529334768Speter{ 529434768Speter if (opaque) opaque = 0; /* to make compiler happy */ 529534768Speter return _halloc((long)items, size); 529634768Speter} 529734768Speter 529834768Spetervoid zcfree (voidpf opaque, voidpf ptr) 529934768Speter{ 530034768Speter if (opaque) opaque = 0; /* to make compiler happy */ 530134768Speter _hfree(ptr); 530234768Speter} 530334768Speter 530434768Speter#endif /* MSC */ 530534768Speter 530634768Speter 530734768Speter#ifndef MY_ZCALLOC /* Any system without a special alloc function */ 530834768Speter 530934768Speter#ifndef STDC 531034768Speterextern voidp calloc OF((uInt items, uInt size)); 531134768Speterextern void free OF((voidpf ptr)); 531234768Speter#endif 531334768Speter 531434768Spetervoidpf zcalloc (opaque, items, size) 531534768Speter voidpf opaque; 531634768Speter unsigned items; 531734768Speter unsigned size; 531834768Speter{ 531934768Speter if (opaque) items += size - size; /* make compiler happy */ 532034768Speter return (voidpf)calloc(items, size); 532134768Speter} 532234768Speter 532334768Spetervoid zcfree (opaque, ptr) 532434768Speter voidpf opaque; 532534768Speter voidpf ptr; 532634768Speter{ 532734768Speter free(ptr); 532834768Speter if (opaque) return; /* make compiler happy */ 532934768Speter} 533034768Speter 533134768Speter#endif /* MY_ZCALLOC */ 533234768Speter/* --- zutil.c */ 533334768Speter 533434768Speter/* +++ adler32.c */ 533528415Speter/* adler32.c -- compute the Adler-32 checksum of a data stream 533634768Speter * Copyright (C) 1995-1996 Mark Adler 533728415Speter * For conditions of distribution and use, see copyright notice in zlib.h 533828415Speter */ 533928415Speter 534034768Speter/* From: adler32.c,v 1.10 1996/05/22 11:52:18 me Exp $ */ 534128415Speter 534234768Speter/* #include "zlib.h" */ 534334768Speter 534428415Speter#define BASE 65521L /* largest prime smaller than 65536 */ 534528415Speter#define NMAX 5552 534628415Speter/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 534728415Speter 5348106696Salfred#define DO1(buf,i) {s1 += buf[(i)]; s2 += s1;} 5349106696Salfred#define DO2(buf,i) DO1(buf,i); DO1(buf,(i)+1); 5350106696Salfred#define DO4(buf,i) DO2(buf,i); DO2(buf,(i)+2); 5351106696Salfred#define DO8(buf,i) DO4(buf,i); DO4(buf,(i)+4); 535234768Speter#define DO16(buf) DO8(buf,0); DO8(buf,8); 535328415Speter 535428415Speter/* ========================================================================= */ 535528415SpeteruLong adler32(adler, buf, len) 535628415Speter uLong adler; 535734768Speter const Bytef *buf; 535828415Speter uInt len; 535928415Speter{ 536028415Speter unsigned long s1 = adler & 0xffff; 536128415Speter unsigned long s2 = (adler >> 16) & 0xffff; 536228415Speter int k; 536328415Speter 536428415Speter if (buf == Z_NULL) return 1L; 536528415Speter 536628415Speter while (len > 0) { 536728415Speter k = len < NMAX ? len : NMAX; 536828415Speter len -= k; 536928415Speter while (k >= 16) { 537028415Speter DO16(buf); 537134768Speter buf += 16; 537228415Speter k -= 16; 537328415Speter } 537428415Speter if (k != 0) do { 537534768Speter s1 += *buf++; 537634768Speter s2 += s1; 537728415Speter } while (--k); 537828415Speter s1 %= BASE; 537928415Speter s2 %= BASE; 538028415Speter } 538128415Speter return (s2 << 16) | s1; 538228415Speter} 538334768Speter/* --- adler32.c */ 5384