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: stable/11/sys/libkern/zlib.c 331643 2018-03-27 18:52:27Z dim $ 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) 28245102Speter#define _tr_init _zlib104_tr_init 29245102Speter#define _tr_align _zlib104_tr_align 30245102Speter#define _tr_tally _zlib104_tr_tally 31245102Speter#define _tr_flush_block _zlib104_tr_flush_block 32245102Speter#define _tr_stored_block _zlib104_tr_stored_block 33245102Speter#define inflate_fast _zlib104_inflate_fast 34245102Speter#define inflate _zlib104_inflate 35245102Speter#define zlibVersion _zlib104_Version 3634768Speter#endif 3734768Speter 3834768Speter 3934768Speter/* +++ zutil.h */ 40139823Simp/*- 41139823Simp * zutil.h -- internal interface and configuration of the compression library 4234768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 4328415Speter * For conditions of distribution and use, see copyright notice in zlib.h 4428415Speter */ 4528415Speter 4628415Speter/* WARNING: this file should *not* be used by applications. It is 4728415Speter part of the implementation of the compression library and is 4828415Speter subject to change. Applications should only use zlib.h. 4928415Speter */ 5028415Speter 5134768Speter/* From: zutil.h,v 1.16 1996/07/24 13:41:13 me Exp $ */ 5228415Speter 5334768Speter#ifndef _Z_UTIL_H 5428415Speter#define _Z_UTIL_H 5528415Speter 5655205Speter#ifdef _KERNEL 57281855Srodrigc#include <sys/zlib.h> 5828415Speter#else 5928415Speter#include "zlib.h" 6028415Speter#endif 6128415Speter 6255205Speter#ifdef _KERNEL 6334768Speter/* Assume this is a *BSD or SVR4 kernel */ 6434768Speter#include <sys/types.h> 6534768Speter#include <sys/time.h> 6634768Speter#include <sys/systm.h> 67110235Salfred#include <sys/param.h> 68130799Smarkm#include <sys/kernel.h> 69130799Smarkm#include <sys/module.h> 7034768Speter# define HAVE_MEMCPY 7134768Speter 7234768Speter#else 7334768Speter#if defined(__KERNEL__) 7434768Speter/* Assume this is a Linux kernel */ 7534768Speter#include <linux/string.h> 7634768Speter#define HAVE_MEMCPY 7734768Speter 7834768Speter#else /* not kernel */ 7934768Speter 8034768Speter#if defined(MSDOS)||defined(VMS)||defined(CRAY)||defined(WIN32)||defined(RISCOS) 8134768Speter# include <stddef.h> 8234768Speter# include <errno.h> 8334768Speter#else 8434768Speter extern int errno; 8534768Speter#endif 8634768Speter#ifdef STDC 8734768Speter# include <string.h> 8834768Speter# include <stdlib.h> 8934768Speter#endif 9034768Speter#endif /* __KERNEL__ */ 9155205Speter#endif /* _KERNEL */ 9234768Speter 9328415Speter#ifndef local 9428415Speter# define local static 9528415Speter#endif 9628415Speter/* compile with -Dlocal if your debugger can't find static symbols */ 9728415Speter 9828415Spetertypedef unsigned char uch; 9928415Spetertypedef uch FAR uchf; 10028415Spetertypedef unsigned short ush; 10128415Spetertypedef ush FAR ushf; 10228415Spetertypedef unsigned long ulg; 10328415Speter 104149993Srodrigcstatic const char *z_errmsg[10]; /* indexed by 2-zlib_error */ 10534768Speter/* (size given to avoid silly warnings with Visual C++) */ 10628415Speter 10734768Speter#define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)] 10834768Speter 10934768Speter#define ERR_RETURN(strm,err) \ 11043305Sdillon return (strm->msg = (const char*)ERR_MSG(err), (err)) 11128415Speter/* To be used only when the state is known to be valid */ 11228415Speter 11328415Speter /* common constants */ 11428415Speter 11528415Speter#ifndef DEF_WBITS 11628415Speter# define DEF_WBITS MAX_WBITS 11728415Speter#endif 11828415Speter/* default windowBits for decompression. MAX_WBITS is for compression only */ 11928415Speter 12028415Speter#if MAX_MEM_LEVEL >= 8 12128415Speter# define DEF_MEM_LEVEL 8 12228415Speter#else 12328415Speter# define DEF_MEM_LEVEL MAX_MEM_LEVEL 12428415Speter#endif 12528415Speter/* default memLevel */ 12628415Speter 12728415Speter#define STORED_BLOCK 0 12828415Speter#define STATIC_TREES 1 12928415Speter#define DYN_TREES 2 13028415Speter/* The three kinds of block type */ 13128415Speter 13228415Speter#define MIN_MATCH 3 13328415Speter#define MAX_MATCH 258 13428415Speter/* The minimum and maximum match lengths */ 13528415Speter 13634768Speter#define PRESET_DICT 0x20 /* preset dictionary flag in zlib header */ 13734768Speter 13834768Speter /* target dependencies */ 13934768Speter 14034768Speter#ifdef MSDOS 14134768Speter# define OS_CODE 0x00 14234768Speter# ifdef __TURBOC__ 14334768Speter# include <alloc.h> 14434768Speter# else /* MSC or DJGPP */ 14534768Speter# include <malloc.h> 14634768Speter# endif 14734768Speter#endif 14834768Speter 14934768Speter#ifdef OS2 15034768Speter# define OS_CODE 0x06 15134768Speter#endif 15234768Speter 15334768Speter#ifdef WIN32 /* Window 95 & Windows NT */ 15434768Speter# define OS_CODE 0x0b 15534768Speter#endif 15634768Speter 15734768Speter#if defined(VAXC) || defined(VMS) 15834768Speter# define OS_CODE 0x02 15934768Speter# define FOPEN(name, mode) \ 16034768Speter fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512") 16134768Speter#endif 16234768Speter 16334768Speter#ifdef AMIGA 16434768Speter# define OS_CODE 0x01 16534768Speter#endif 16634768Speter 16734768Speter#if defined(ATARI) || defined(atarist) 16834768Speter# define OS_CODE 0x05 16934768Speter#endif 17034768Speter 17134768Speter#ifdef MACOS 17234768Speter# define OS_CODE 0x07 17334768Speter#endif 17434768Speter 17534768Speter#ifdef __50SERIES /* Prime/PRIMOS */ 17634768Speter# define OS_CODE 0x0F 17734768Speter#endif 17834768Speter 17934768Speter#ifdef TOPS20 18034768Speter# define OS_CODE 0x0a 18134768Speter#endif 18234768Speter 18334768Speter#if defined(_BEOS_) || defined(RISCOS) 18434768Speter# define fdopen(fd,mode) NULL /* No fdopen() */ 18534768Speter#endif 18634768Speter 18734768Speter /* Common defaults */ 18834768Speter 18934768Speter#ifndef OS_CODE 19034768Speter# define OS_CODE 0x03 /* assume Unix */ 19134768Speter#endif 19234768Speter 19334768Speter#ifndef FOPEN 19434768Speter# define FOPEN(name, mode) fopen((name), (mode)) 19534768Speter#endif 19634768Speter 19728415Speter /* functions */ 19828415Speter 19934768Speter#ifdef HAVE_STRERROR 20034768Speter extern char *strerror OF((int)); 20134768Speter# define zstrerror(errnum) strerror(errnum) 20228415Speter#else 20334768Speter# define zstrerror(errnum) "" 20434768Speter#endif 20528415Speter 20634768Speter#if defined(pyr) 20734768Speter# define NO_MEMCPY 20834768Speter#endif 20934768Speter#if (defined(M_I86SM) || defined(M_I86MM)) && !defined(_MSC_VER) 21034768Speter /* Use our own functions for small and medium model with MSC <= 5.0. 21134768Speter * You may have to use the same strategy for Borland C (untested). 21234768Speter */ 21334768Speter# define NO_MEMCPY 21434768Speter#endif 21528415Speter#if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY) 21628415Speter# define HAVE_MEMCPY 21728415Speter#endif 21828415Speter#ifdef HAVE_MEMCPY 21934768Speter# ifdef SMALL_MEDIUM /* MSDOS small or medium model */ 22034768Speter# define zmemcpy _fmemcpy 22134768Speter# define zmemcmp _fmemcmp 22234768Speter# define zmemzero(dest, len) _fmemset(dest, 0, len) 22334768Speter# else 22428415Speter# define zmemcpy memcpy 22534768Speter# define zmemcmp memcmp 22628415Speter# define zmemzero(dest, len) memset(dest, 0, len) 22734768Speter# endif 22828415Speter#else 22928415Speter extern void zmemcpy OF((Bytef* dest, Bytef* source, uInt len)); 23034768Speter extern int zmemcmp OF((Bytef* s1, Bytef* s2, uInt len)); 23128415Speter extern void zmemzero OF((Bytef* dest, uInt len)); 23228415Speter#endif 23328415Speter 23428415Speter/* Diagnostic functions */ 23528415Speter#ifdef DEBUG_ZLIB 23628415Speter# include <stdio.h> 23728415Speter# ifndef verbose 23828415Speter# define verbose 0 23928415Speter# endif 24034768Speter extern void z_error OF((char *m)); 24128415Speter# define Assert(cond,msg) {if(!(cond)) z_error(msg);} 24228415Speter# define Trace(x) fprintf x 24328415Speter# define Tracev(x) {if (verbose) fprintf x ;} 24428415Speter# define Tracevv(x) {if (verbose>1) fprintf x ;} 24528415Speter# define Tracec(c,x) {if (verbose && (c)) fprintf x ;} 24628415Speter# define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;} 24728415Speter#else 24828415Speter# define Assert(cond,msg) 24928415Speter# define Trace(x) 25028415Speter# define Tracev(x) 25128415Speter# define Tracevv(x) 25228415Speter# define Tracec(c,x) 25328415Speter# define Tracecv(c,x) 25428415Speter#endif 25528415Speter 25628415Speter 25734768Spetertypedef uLong (*check_func) OF((uLong check, const Bytef *buf, uInt len)); 25828415Speter 25934768Spetervoidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size)); 26034768Spetervoid zcfree OF((voidpf opaque, voidpf ptr)); 26128415Speter 26228415Speter#define ZALLOC(strm, items, size) \ 26328415Speter (*((strm)->zalloc))((strm)->opaque, (items), (size)) 26434768Speter#define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr)) 26534768Speter#define TRY_FREE(s, p) {if (p) ZFREE(s, p);} 26628415Speter 26734768Speter#endif /* _Z_UTIL_H */ 26834768Speter/* --- zutil.h */ 26934768Speter 27034768Speter/* +++ deflate.h */ 27128415Speter/* deflate.h -- internal compression state 27234768Speter * Copyright (C) 1995-1996 Jean-loup Gailly 27328415Speter * For conditions of distribution and use, see copyright notice in zlib.h 27428415Speter */ 27528415Speter 27628415Speter/* WARNING: this file should *not* be used by applications. It is 27728415Speter part of the implementation of the compression library and is 27828415Speter subject to change. Applications should only use zlib.h. 27928415Speter */ 28028415Speter 28134768Speter/* From: deflate.h,v 1.10 1996/07/02 12:41:00 me Exp $ */ 28228415Speter 28334768Speter#ifndef _DEFLATE_H 28434768Speter#define _DEFLATE_H 28528415Speter 28634768Speter/* #include "zutil.h" */ 28734768Speter 28828415Speter/* =========================================================================== 28928415Speter * Internal compression state. 29028415Speter */ 29128415Speter 29228415Speter#define LENGTH_CODES 29 29328415Speter/* number of length codes, not counting the special END_BLOCK code */ 29428415Speter 29528415Speter#define LITERALS 256 29628415Speter/* number of literal bytes 0..255 */ 29728415Speter 29828415Speter#define L_CODES (LITERALS+1+LENGTH_CODES) 29928415Speter/* number of Literal or Length codes, including the END_BLOCK code */ 30028415Speter 30128415Speter#define D_CODES 30 30228415Speter/* number of distance codes */ 30328415Speter 30428415Speter#define BL_CODES 19 30528415Speter/* number of codes used to transfer the bit lengths */ 30628415Speter 30728415Speter#define HEAP_SIZE (2*L_CODES+1) 30828415Speter/* maximum heap size */ 30928415Speter 31028415Speter#define MAX_BITS 15 31128415Speter/* All codes must not exceed MAX_BITS bits */ 31228415Speter 31328415Speter#define INIT_STATE 42 31428415Speter#define BUSY_STATE 113 31528415Speter#define FINISH_STATE 666 31628415Speter/* Stream status */ 31728415Speter 31828415Speter 31928415Speter/* Data structure describing a single value and its code string. */ 32028415Spetertypedef struct ct_data_s { 32128415Speter union { 32228415Speter ush freq; /* frequency count */ 32328415Speter ush code; /* bit string */ 32428415Speter } fc; 32528415Speter union { 32628415Speter ush dad; /* father node in Huffman tree */ 32728415Speter ush len; /* length of bit string */ 32828415Speter } dl; 32928415Speter} FAR ct_data; 33028415Speter 33128415Speter#define Freq fc.freq 33228415Speter#define Code fc.code 33328415Speter#define Dad dl.dad 33428415Speter#define Len dl.len 33528415Speter 33628415Spetertypedef struct static_tree_desc_s static_tree_desc; 33728415Speter 33828415Spetertypedef struct tree_desc_s { 33928415Speter ct_data *dyn_tree; /* the dynamic tree */ 34028415Speter int max_code; /* largest code with non zero frequency */ 34128415Speter static_tree_desc *stat_desc; /* the corresponding static tree */ 34228415Speter} FAR tree_desc; 34328415Speter 34428415Spetertypedef ush Pos; 34528415Spetertypedef Pos FAR Posf; 34628415Spetertypedef unsigned IPos; 34728415Speter 34828415Speter/* A Pos is an index in the character window. We use short instead of int to 34928415Speter * save space in the various tables. IPos is used only for parameter passing. 35028415Speter */ 35128415Speter 35228415Spetertypedef struct deflate_state { 35334768Speter z_streamp strm; /* pointer back to this zlib stream */ 35428415Speter int status; /* as the name implies */ 35528415Speter Bytef *pending_buf; /* output still pending */ 35634768Speter ulg pending_buf_size; /* size of pending_buf */ 35728415Speter Bytef *pending_out; /* next pending byte to output to the stream */ 35828415Speter int pending; /* nb of bytes in the pending buffer */ 35928415Speter int noheader; /* suppress zlib header and adler32 */ 36034768Speter Byte data_type; /* UNKNOWN, BINARY or ASCII */ 36128415Speter Byte method; /* STORED (for zip only) or DEFLATED */ 36234768Speter int last_flush; /* value of flush param for previous deflate call */ 36328415Speter 36428415Speter /* used by deflate.c: */ 36528415Speter 36628415Speter uInt w_size; /* LZ77 window size (32K by default) */ 36728415Speter uInt w_bits; /* log2(w_size) (8..16) */ 36828415Speter uInt w_mask; /* w_size - 1 */ 36928415Speter 37028415Speter Bytef *window; 37128415Speter /* Sliding window. Input bytes are read into the second half of the window, 37228415Speter * and move to the first half later to keep a dictionary of at least wSize 37328415Speter * bytes. With this organization, matches are limited to a distance of 37428415Speter * wSize-MAX_MATCH bytes, but this ensures that IO is always 37528415Speter * performed with a length multiple of the block size. Also, it limits 37628415Speter * the window size to 64K, which is quite useful on MSDOS. 37728415Speter * To do: use the user input buffer as sliding window. 37828415Speter */ 37928415Speter 38028415Speter ulg window_size; 38128415Speter /* Actual size of window: 2*wSize, except when the user input buffer 38228415Speter * is directly used as sliding window. 38328415Speter */ 38428415Speter 38528415Speter Posf *prev; 38628415Speter /* Link to older string with same hash index. To limit the size of this 38728415Speter * array to 64K, this link is maintained only for the last 32K strings. 38828415Speter * An index in this array is thus a window index modulo 32K. 38928415Speter */ 39028415Speter 39128415Speter Posf *head; /* Heads of the hash chains or NIL. */ 39228415Speter 39328415Speter uInt ins_h; /* hash index of string to be inserted */ 39428415Speter uInt hash_size; /* number of elements in hash table */ 39528415Speter uInt hash_bits; /* log2(hash_size) */ 39628415Speter uInt hash_mask; /* hash_size-1 */ 39728415Speter 39828415Speter uInt hash_shift; 39928415Speter /* Number of bits by which ins_h must be shifted at each input 40028415Speter * step. It must be such that after MIN_MATCH steps, the oldest 40128415Speter * byte no longer takes part in the hash key, that is: 40228415Speter * hash_shift * MIN_MATCH >= hash_bits 40328415Speter */ 40428415Speter 40528415Speter long block_start; 40628415Speter /* Window position at the beginning of the current output block. Gets 40728415Speter * negative when the window is moved backwards. 40828415Speter */ 40928415Speter 41028415Speter uInt match_length; /* length of best match */ 41128415Speter IPos prev_match; /* previous match */ 41228415Speter int match_available; /* set if previous match exists */ 41328415Speter uInt strstart; /* start of string to insert */ 41428415Speter uInt match_start; /* start of matching string */ 41528415Speter uInt lookahead; /* number of valid bytes ahead in window */ 41628415Speter 41728415Speter uInt prev_length; 41828415Speter /* Length of the best match at previous step. Matches not greater than this 41928415Speter * are discarded. This is used in the lazy match evaluation. 42028415Speter */ 42128415Speter 42228415Speter uInt max_chain_length; 42328415Speter /* To speed up deflation, hash chains are never searched beyond this 42428415Speter * length. A higher limit improves compression ratio but degrades the 42528415Speter * speed. 42628415Speter */ 42728415Speter 42828415Speter uInt max_lazy_match; 42928415Speter /* Attempt to find a better match only when the current match is strictly 43028415Speter * smaller than this value. This mechanism is used only for compression 43128415Speter * levels >= 4. 43228415Speter */ 43328415Speter# define max_insert_length max_lazy_match 43428415Speter /* Insert new strings in the hash table only if the match length is not 43528415Speter * greater than this length. This saves time but degrades compression. 43628415Speter * max_insert_length is used only for compression levels <= 3. 43728415Speter */ 43828415Speter 43928415Speter int level; /* compression level (1..9) */ 44028415Speter int strategy; /* favor or force Huffman coding*/ 44128415Speter 44228415Speter uInt good_match; 44328415Speter /* Use a faster search when the previous match is longer than this */ 44428415Speter 44534768Speter int nice_match; /* Stop searching when current match exceeds this */ 44628415Speter 44728415Speter /* used by trees.c: */ 44828415Speter /* Didn't use ct_data typedef below to supress compiler warning */ 44928415Speter struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */ 45028415Speter struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */ 45128415Speter struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */ 45228415Speter 45328415Speter struct tree_desc_s l_desc; /* desc. for literal tree */ 45428415Speter struct tree_desc_s d_desc; /* desc. for distance tree */ 45528415Speter struct tree_desc_s bl_desc; /* desc. for bit length tree */ 45628415Speter 45728415Speter ush bl_count[MAX_BITS+1]; 45828415Speter /* number of codes at each bit length for an optimal tree */ 45928415Speter 46028415Speter int heap[2*L_CODES+1]; /* heap used to build the Huffman trees */ 46128415Speter int heap_len; /* number of elements in the heap */ 46228415Speter int heap_max; /* element of largest frequency */ 46328415Speter /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 46428415Speter * The same heap array is used to build all trees. 46528415Speter */ 46628415Speter 46728415Speter uch depth[2*L_CODES+1]; 46828415Speter /* Depth of each subtree used as tie breaker for trees of equal frequency 46928415Speter */ 47028415Speter 47128415Speter uchf *l_buf; /* buffer for literals or lengths */ 47228415Speter 47328415Speter uInt lit_bufsize; 47428415Speter /* Size of match buffer for literals/lengths. There are 4 reasons for 47528415Speter * limiting lit_bufsize to 64K: 47628415Speter * - frequencies can be kept in 16 bit counters 47728415Speter * - if compression is not successful for the first block, all input 47828415Speter * data is still in the window so we can still emit a stored block even 47928415Speter * when input comes from standard input. (This can also be done for 48028415Speter * all blocks if lit_bufsize is not greater than 32K.) 48128415Speter * - if compression is not successful for a file smaller than 64K, we can 48228415Speter * even emit a stored file instead of a stored block (saving 5 bytes). 48328415Speter * This is applicable only for zip (not gzip or zlib). 48428415Speter * - creating new Huffman trees less frequently may not provide fast 48528415Speter * adaptation to changes in the input data statistics. (Take for 48628415Speter * example a binary file with poorly compressible code followed by 48728415Speter * a highly compressible string table.) Smaller buffer sizes give 48828415Speter * fast adaptation but have of course the overhead of transmitting 48928415Speter * trees more frequently. 49028415Speter * - I can't count above 4 49128415Speter */ 49228415Speter 49328415Speter uInt last_lit; /* running index in l_buf */ 49428415Speter 49528415Speter ushf *d_buf; 49628415Speter /* Buffer for distances. To simplify the code, d_buf and l_buf have 49728415Speter * the same number of elements. To use different lengths, an extra flag 49828415Speter * array would be necessary. 49928415Speter */ 50028415Speter 50128415Speter ulg opt_len; /* bit length of current block with optimal trees */ 50228415Speter ulg static_len; /* bit length of current block with static trees */ 50328415Speter ulg compressed_len; /* total bit length of compressed file */ 50428415Speter uInt matches; /* number of string matches in current block */ 50528415Speter int last_eob_len; /* bit length of EOB code for last block */ 50628415Speter 50728415Speter#ifdef DEBUG_ZLIB 50828415Speter ulg bits_sent; /* bit length of the compressed data */ 50928415Speter#endif 51028415Speter 51128415Speter ush bi_buf; 51228415Speter /* Output buffer. bits are inserted starting at the bottom (least 51328415Speter * significant bits). 51428415Speter */ 51528415Speter int bi_valid; 51628415Speter /* Number of valid bits in bi_buf. All bits above the last valid bit 51728415Speter * are always zero. 51828415Speter */ 51928415Speter 52028415Speter} FAR deflate_state; 52128415Speter 52228415Speter/* Output a byte on the stream. 52328415Speter * IN assertion: there is enough room in pending_buf. 52428415Speter */ 52528415Speter#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);} 52628415Speter 52728415Speter 52828415Speter#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 52928415Speter/* Minimum amount of lookahead, except at the end of the input file. 53028415Speter * See deflate.c for comments about the MIN_MATCH+1. 53128415Speter */ 53228415Speter 53328415Speter#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD) 53428415Speter/* In order to simplify the code, particularly on 16 bit machines, match 53528415Speter * distances are limited to MAX_DIST instead of WSIZE. 53628415Speter */ 53728415Speter 53828415Speter /* in trees.c */ 53934768Spetervoid _tr_init OF((deflate_state *s)); 54034768Speterint _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc)); 54134768Speterulg _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len, 54234768Speter int eof)); 54334768Spetervoid _tr_align OF((deflate_state *s)); 54434768Spetervoid _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len, 54528415Speter int eof)); 54634768Spetervoid _tr_stored_type_only OF((deflate_state *)); 54728415Speter 54834768Speter#endif 54934768Speter/* --- deflate.h */ 55028415Speter 55134768Speter/* +++ deflate.c */ 55228415Speter/* deflate.c -- compress data using the deflation algorithm 55334768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 55428415Speter * For conditions of distribution and use, see copyright notice in zlib.h 55528415Speter */ 55628415Speter 55728415Speter/* 55828415Speter * ALGORITHM 55928415Speter * 56028415Speter * The "deflation" process depends on being able to identify portions 56128415Speter * of the input text which are identical to earlier input (within a 56228415Speter * sliding window trailing behind the input currently being processed). 56328415Speter * 56428415Speter * The most straightforward technique turns out to be the fastest for 56528415Speter * most input files: try all possible matches and select the longest. 56628415Speter * The key feature of this algorithm is that insertions into the string 56728415Speter * dictionary are very simple and thus fast, and deletions are avoided 56828415Speter * completely. Insertions are performed at each input character, whereas 56928415Speter * string matches are performed only when the previous match ends. So it 57028415Speter * is preferable to spend more time in matches to allow very fast string 57128415Speter * insertions and avoid deletions. The matching algorithm for small 57228415Speter * strings is inspired from that of Rabin & Karp. A brute force approach 57328415Speter * is used to find longer strings when a small match has been found. 57428415Speter * A similar algorithm is used in comic (by Jan-Mark Wams) and freeze 57528415Speter * (by Leonid Broukhis). 57628415Speter * A previous version of this file used a more sophisticated algorithm 57728415Speter * (by Fiala and Greene) which is guaranteed to run in linear amortized 57828415Speter * time, but has a larger average cost, uses more memory and is patented. 57928415Speter * However the F&G algorithm may be faster for some highly redundant 58028415Speter * files if the parameter max_chain_length (described below) is too large. 58128415Speter * 58228415Speter * ACKNOWLEDGEMENTS 58328415Speter * 58428415Speter * The idea of lazy evaluation of matches is due to Jan-Mark Wams, and 58528415Speter * I found it in 'freeze' written by Leonid Broukhis. 58628415Speter * Thanks to many people for bug reports and testing. 58728415Speter * 58828415Speter * REFERENCES 58928415Speter * 59034768Speter * Deutsch, L.P.,"DEFLATE Compressed Data Format Specification". 59134768Speter * Available in ftp://ds.internic.net/rfc/rfc1951.txt 59228415Speter * 59328415Speter * A description of the Rabin and Karp algorithm is given in the book 59428415Speter * "Algorithms" by R. Sedgewick, Addison-Wesley, p252. 59528415Speter * 59628415Speter * Fiala,E.R., and Greene,D.H. 59728415Speter * Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595 59828415Speter * 59928415Speter */ 60028415Speter 60134768Speter/* From: deflate.c,v 1.15 1996/07/24 13:40:58 me Exp $ */ 60228415Speter 60334768Speter/* #include "deflate.h" */ 60434768Speter 60534768Speterchar deflate_copyright[] = " deflate 1.0.4 Copyright 1995-1996 Jean-loup Gailly "; 60628415Speter/* 60728415Speter If you use the zlib library in a product, an acknowledgment is welcome 60828415Speter in the documentation of your product. If for some reason you cannot 60928415Speter include such an acknowledgment, I would appreciate that you keep this 61028415Speter copyright string in the executable of your product. 61128415Speter */ 61228415Speter 61334768Speter/* =========================================================================== 61434768Speter * Function prototypes. 61534768Speter */ 61634768Spetertypedef enum { 61734768Speter need_more, /* block not completed, need more input or more output */ 61834768Speter block_done, /* block flush performed */ 61934768Speter finish_started, /* finish started, need only more output at next deflate */ 62034768Speter finish_done /* finish done, accept no more input or output */ 62134768Speter} block_state; 62234768Speter 62334768Spetertypedef block_state (*compress_func) OF((deflate_state *s, int flush)); 62434768Speter/* Compression function. Returns the block state after the call. */ 62534768Speter 62634768Speterlocal void fill_window OF((deflate_state *s)); 62734768Speterlocal block_state deflate_stored OF((deflate_state *s, int flush)); 62834768Speterlocal block_state deflate_fast OF((deflate_state *s, int flush)); 62934768Speterlocal block_state deflate_slow OF((deflate_state *s, int flush)); 63034768Speterlocal void lm_init OF((deflate_state *s)); 63134768Speterlocal void putShortMSB OF((deflate_state *s, uInt b)); 63234768Speterlocal void flush_pending OF((z_streamp strm)); 63334768Speterlocal int read_buf OF((z_streamp strm, charf *buf, unsigned size)); 63434768Speter#ifdef ASMV 63534768Speter void match_init OF((void)); /* asm code initialization */ 63634768Speter uInt longest_match OF((deflate_state *s, IPos cur_match)); 63734768Speter#else 63834768Speterlocal uInt longest_match OF((deflate_state *s, IPos cur_match)); 63934768Speter#endif 64034768Speter 64134768Speter#ifdef DEBUG_ZLIB 64234768Speterlocal void check_match OF((deflate_state *s, IPos start, IPos match, 64334768Speter int length)); 64434768Speter#endif 64534768Speter 64634768Speter/* =========================================================================== 64734768Speter * Local data 64834768Speter */ 64934768Speter 65028415Speter#define NIL 0 65128415Speter/* Tail of hash chains */ 65228415Speter 65328415Speter#ifndef TOO_FAR 65428415Speter# define TOO_FAR 4096 65528415Speter#endif 65628415Speter/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */ 65728415Speter 65828415Speter#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1) 65928415Speter/* Minimum amount of lookahead, except at the end of the input file. 66028415Speter * See deflate.c for comments about the MIN_MATCH+1. 66128415Speter */ 66228415Speter 66328415Speter/* Values for max_lazy_match, good_match and max_chain_length, depending on 66428415Speter * the desired pack level (0..9). The values given below have been tuned to 66528415Speter * exclude worst case performance for pathological files. Better values may be 66628415Speter * found for specific files. 66728415Speter */ 66828415Spetertypedef struct config_s { 66928415Speter ush good_length; /* reduce lazy search above this match length */ 67028415Speter ush max_lazy; /* do not perform lazy search above this match length */ 67128415Speter ush nice_length; /* quit search above this match length */ 67228415Speter ush max_chain; 67334768Speter compress_func func; 67428415Speter} config; 67528415Speter 67628415Speterlocal config configuration_table[10] = { 67728415Speter/* good lazy nice chain */ 67834768Speter/* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ 67934768Speter/* 1 */ {4, 4, 8, 4, deflate_fast}, /* maximum speed, no lazy matches */ 68034768Speter/* 2 */ {4, 5, 16, 8, deflate_fast}, 68134768Speter/* 3 */ {4, 6, 32, 32, deflate_fast}, 68228415Speter 68334768Speter/* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ 68434768Speter/* 5 */ {8, 16, 32, 32, deflate_slow}, 68534768Speter/* 6 */ {8, 16, 128, 128, deflate_slow}, 68634768Speter/* 7 */ {8, 32, 128, 256, deflate_slow}, 68734768Speter/* 8 */ {32, 128, 258, 1024, deflate_slow}, 68834768Speter/* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* maximum compression */ 68928415Speter 69028415Speter/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4 69128415Speter * For deflate_fast() (levels <= 3) good is ignored and lazy has a different 69228415Speter * meaning. 69328415Speter */ 69428415Speter 69528415Speter#define EQUAL 0 69628415Speter/* result of memcmp for equal strings */ 69728415Speter 69834768Speter#ifndef NO_DUMMY_DECL 69934768Speterstruct static_tree_desc_s {int dummy;}; /* for buggy compilers */ 70028415Speter#endif 70128415Speter 70228415Speter/* =========================================================================== 70328415Speter * Update a hash value with the given input byte 70428415Speter * IN assertion: all calls to to UPDATE_HASH are made with consecutive 70528415Speter * input characters, so that a running hash key can be computed from the 70628415Speter * previous key instead of complete recalculation each time. 70728415Speter */ 70828415Speter#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask) 70928415Speter 71028415Speter 71128415Speter/* =========================================================================== 71228415Speter * Insert string str in the dictionary and set match_head to the previous head 71328415Speter * of the hash chain (the most recent string with same hash key). Return 71428415Speter * the previous length of the hash chain. 71528415Speter * IN assertion: all calls to to INSERT_STRING are made with consecutive 71628415Speter * input characters and the first MIN_MATCH bytes of str are valid 71728415Speter * (except for the last MIN_MATCH-1 bytes of the input file). 71828415Speter */ 71928415Speter#define INSERT_STRING(s, str, match_head) \ 72028415Speter (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \ 72128415Speter s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \ 72234768Speter s->head[s->ins_h] = (Pos)(str)) 72328415Speter 72428415Speter/* =========================================================================== 72528415Speter * Initialize the hash table (avoiding 64K overflow for 16 bit systems). 72628415Speter * prev[] will be initialized on the fly. 72728415Speter */ 72828415Speter#define CLEAR_HASH(s) \ 72928415Speter s->head[s->hash_size-1] = NIL; \ 73028415Speter zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head)); 73128415Speter 73228415Speter/* ========================================================================= */ 73334768Speterint deflateInit_(strm, level, version, stream_size) 73434768Speter z_streamp strm; 73528415Speter int level; 73634768Speter const char *version; 73734768Speter int stream_size; 73828415Speter{ 73934768Speter return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 74034768Speter Z_DEFAULT_STRATEGY, version, stream_size); 74128415Speter /* To do: ignore strm->next_in if we use it as window */ 74228415Speter} 74328415Speter 74428415Speter/* ========================================================================= */ 74534768Speterint deflateInit2_(strm, level, method, windowBits, memLevel, strategy, 74634768Speter version, stream_size) 74734768Speter z_streamp strm; 74828415Speter int level; 74928415Speter int method; 75028415Speter int windowBits; 75128415Speter int memLevel; 75228415Speter int strategy; 75334768Speter const char *version; 75434768Speter int stream_size; 75528415Speter{ 75628415Speter deflate_state *s; 75728415Speter int noheader = 0; 75834768Speter static char* my_version = ZLIB_VERSION; 75928415Speter 76034768Speter ushf *overlay; 76134768Speter /* We overlay pending_buf and d_buf+l_buf. This works since the average 76234768Speter * output size for (length,distance) codes is <= 24 bits. 76334768Speter */ 76434768Speter 76534768Speter if (version == Z_NULL || version[0] != my_version[0] || 76634768Speter stream_size != sizeof(z_stream)) { 76734768Speter return Z_VERSION_ERROR; 76834768Speter } 76928415Speter if (strm == Z_NULL) return Z_STREAM_ERROR; 77028415Speter 77128415Speter strm->msg = Z_NULL; 77234768Speter#ifndef NO_ZCFUNCS 77334768Speter if (strm->zalloc == Z_NULL) { 77434768Speter strm->zalloc = zcalloc; 77534768Speter strm->opaque = (voidpf)0; 77634768Speter } 77734768Speter if (strm->zfree == Z_NULL) strm->zfree = zcfree; 77834768Speter#endif 77928415Speter 78028415Speter if (level == Z_DEFAULT_COMPRESSION) level = 6; 78128415Speter 78228415Speter if (windowBits < 0) { /* undocumented feature: suppress zlib header */ 78328415Speter noheader = 1; 78428415Speter windowBits = -windowBits; 78528415Speter } 78634768Speter if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED || 78793013Sjedgar windowBits < 9 || windowBits > 15 || level < 0 || level > 9 || 78834768Speter strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 78928415Speter return Z_STREAM_ERROR; 79028415Speter } 79134768Speter s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state)); 79228415Speter if (s == Z_NULL) return Z_MEM_ERROR; 79328415Speter strm->state = (struct internal_state FAR *)s; 79428415Speter s->strm = strm; 79528415Speter 79628415Speter s->noheader = noheader; 79728415Speter s->w_bits = windowBits; 79828415Speter s->w_size = 1 << s->w_bits; 79928415Speter s->w_mask = s->w_size - 1; 80028415Speter 80128415Speter s->hash_bits = memLevel + 7; 80228415Speter s->hash_size = 1 << s->hash_bits; 80328415Speter s->hash_mask = s->hash_size - 1; 80428415Speter s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH); 80528415Speter 80634768Speter s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte)); 80734768Speter s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos)); 80834768Speter s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos)); 80928415Speter 81028415Speter s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */ 81128415Speter 81234768Speter overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2); 81334768Speter s->pending_buf = (uchf *) overlay; 81434768Speter s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L); 81528415Speter 81628415Speter if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL || 81728415Speter s->pending_buf == Z_NULL) { 81843305Sdillon strm->msg = (const char*)ERR_MSG(Z_MEM_ERROR); 81928415Speter deflateEnd (strm); 82028415Speter return Z_MEM_ERROR; 82128415Speter } 82234768Speter s->d_buf = overlay + s->lit_bufsize/sizeof(ush); 82334768Speter s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize; 82428415Speter 82528415Speter s->level = level; 82628415Speter s->strategy = strategy; 82728415Speter s->method = (Byte)method; 82828415Speter 82928415Speter return deflateReset(strm); 83028415Speter} 83128415Speter 83228415Speter/* ========================================================================= */ 83334768Speterint deflateSetDictionary (strm, dictionary, dictLength) 83434768Speter z_streamp strm; 83534768Speter const Bytef *dictionary; 83634768Speter uInt dictLength; 83734768Speter{ 83834768Speter deflate_state *s; 83934768Speter uInt length = dictLength; 84034768Speter uInt n; 84134768Speter IPos hash_head = 0; 84234768Speter 84334768Speter if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL) 84434768Speter return Z_STREAM_ERROR; 84534768Speter 84634768Speter s = (deflate_state *) strm->state; 84734768Speter if (s->status != INIT_STATE) return Z_STREAM_ERROR; 84834768Speter 84934768Speter strm->adler = adler32(strm->adler, dictionary, dictLength); 85034768Speter 85134768Speter if (length < MIN_MATCH) return Z_OK; 85234768Speter if (length > MAX_DIST(s)) { 85334768Speter length = MAX_DIST(s); 85434768Speter#ifndef USE_DICT_HEAD 85534768Speter dictionary += dictLength - length; /* use the tail of the dictionary */ 85634768Speter#endif 85734768Speter } 85834768Speter zmemcpy((charf *)s->window, dictionary, length); 85934768Speter s->strstart = length; 86034768Speter s->block_start = (long)length; 86134768Speter 86234768Speter /* Insert all strings in the hash table (except for the last two bytes). 86334768Speter * s->lookahead stays null, so s->ins_h will be recomputed at the next 86434768Speter * call of fill_window. 86534768Speter */ 86634768Speter s->ins_h = s->window[0]; 86734768Speter UPDATE_HASH(s, s->ins_h, s->window[1]); 86834768Speter for (n = 0; n <= length - MIN_MATCH; n++) { 86934768Speter INSERT_STRING(s, n, hash_head); 87034768Speter } 87134768Speter if (hash_head) hash_head = 0; /* to make compiler happy */ 87234768Speter return Z_OK; 87334768Speter} 87434768Speter 87534768Speter/* ========================================================================= */ 87628415Speterint deflateReset (strm) 87734768Speter z_streamp strm; 87828415Speter{ 87928415Speter deflate_state *s; 88028415Speter 88128415Speter if (strm == Z_NULL || strm->state == Z_NULL || 88234768Speter strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR; 88328415Speter 88428415Speter strm->total_in = strm->total_out = 0; 88528415Speter strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */ 88628415Speter strm->data_type = Z_UNKNOWN; 88728415Speter 88828415Speter s = (deflate_state *)strm->state; 88928415Speter s->pending = 0; 89028415Speter s->pending_out = s->pending_buf; 89128415Speter 89228415Speter if (s->noheader < 0) { 89328415Speter s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */ 89428415Speter } 89528415Speter s->status = s->noheader ? BUSY_STATE : INIT_STATE; 89634768Speter strm->adler = 1; 89734768Speter s->last_flush = Z_NO_FLUSH; 89828415Speter 89934768Speter _tr_init(s); 90028415Speter lm_init(s); 90128415Speter 90228415Speter return Z_OK; 90328415Speter} 90428415Speter 90534768Speter/* ========================================================================= */ 90634768Speterint deflateParams(strm, level, strategy) 90734768Speter z_streamp strm; 90834768Speter int level; 90934768Speter int strategy; 91034768Speter{ 91134768Speter deflate_state *s; 91234768Speter compress_func func; 91334768Speter int err = Z_OK; 91434768Speter 91534768Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 91634768Speter s = (deflate_state *) strm->state; 91734768Speter 91834768Speter if (level == Z_DEFAULT_COMPRESSION) { 91934768Speter level = 6; 92034768Speter } 92134768Speter if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 92234768Speter return Z_STREAM_ERROR; 92334768Speter } 92434768Speter func = configuration_table[s->level].func; 92534768Speter 92634768Speter if (func != configuration_table[level].func && strm->total_in != 0) { 92734768Speter /* Flush the last buffer: */ 92834768Speter err = deflate(strm, Z_PARTIAL_FLUSH); 92934768Speter } 93034768Speter if (s->level != level) { 93134768Speter s->level = level; 93234768Speter s->max_lazy_match = configuration_table[level].max_lazy; 93334768Speter s->good_match = configuration_table[level].good_length; 93434768Speter s->nice_match = configuration_table[level].nice_length; 93534768Speter s->max_chain_length = configuration_table[level].max_chain; 93634768Speter } 93734768Speter s->strategy = strategy; 93834768Speter return err; 93934768Speter} 94034768Speter 94128415Speter/* ========================================================================= 94228415Speter * Put a short in the pending buffer. The 16-bit value is put in MSB order. 94328415Speter * IN assertion: the stream state is correct and there is enough room in 94428415Speter * pending_buf. 94528415Speter */ 94628415Speterlocal void putShortMSB (s, b) 94728415Speter deflate_state *s; 94828415Speter uInt b; 94928415Speter{ 95028415Speter put_byte(s, (Byte)(b >> 8)); 95128415Speter put_byte(s, (Byte)(b & 0xff)); 95228415Speter} 95328415Speter 95428415Speter/* ========================================================================= 95534768Speter * Flush as much pending output as possible. All deflate() output goes 95634768Speter * through this function so some applications may wish to modify it 95734768Speter * to avoid allocating a large strm->next_out buffer and copying into it. 95834768Speter * (See also read_buf()). 95928415Speter */ 96028415Speterlocal void flush_pending(strm) 96134768Speter z_streamp strm; 96228415Speter{ 96334768Speter deflate_state *s = (deflate_state *) strm->state; 96434768Speter unsigned len = s->pending; 96528415Speter 96628415Speter if (len > strm->avail_out) len = strm->avail_out; 96728415Speter if (len == 0) return; 96828415Speter 96934768Speter if (strm->next_out != Z_NULL) { 97034768Speter zmemcpy(strm->next_out, s->pending_out, len); 97128415Speter strm->next_out += len; 97228415Speter } 97334768Speter s->pending_out += len; 97428415Speter strm->total_out += len; 97534768Speter strm->avail_out -= len; 97634768Speter s->pending -= len; 97734768Speter if (s->pending == 0) { 97834768Speter s->pending_out = s->pending_buf; 97928415Speter } 98028415Speter} 98128415Speter 98228415Speter/* ========================================================================= */ 98328415Speterint deflate (strm, flush) 98434768Speter z_streamp strm; 98528415Speter int flush; 98628415Speter{ 98734768Speter int old_flush; /* value of flush param for previous deflate call */ 98834768Speter deflate_state *s; 98928415Speter 99034768Speter if (strm == Z_NULL || strm->state == Z_NULL || 99134768Speter flush > Z_FINISH || flush < 0) { 99234768Speter return Z_STREAM_ERROR; 99334768Speter } 99434768Speter s = (deflate_state *) strm->state; 99534768Speter 99634768Speter if ((strm->next_in == Z_NULL && strm->avail_in != 0) || 99734768Speter (s->status == FINISH_STATE && flush != Z_FINISH)) { 99828415Speter ERR_RETURN(strm, Z_STREAM_ERROR); 99928415Speter } 100028415Speter if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR); 100128415Speter 100234768Speter s->strm = strm; /* just in case */ 100334768Speter old_flush = s->last_flush; 100434768Speter s->last_flush = flush; 100528415Speter 100628415Speter /* Write the zlib header */ 100734768Speter if (s->status == INIT_STATE) { 100828415Speter 100934768Speter uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8; 101034768Speter uInt level_flags = (s->level-1) >> 1; 101128415Speter 101228415Speter if (level_flags > 3) level_flags = 3; 101328415Speter header |= (level_flags << 6); 101434768Speter if (s->strstart != 0) header |= PRESET_DICT; 101528415Speter header += 31 - (header % 31); 101628415Speter 101734768Speter s->status = BUSY_STATE; 101834768Speter putShortMSB(s, header); 101934768Speter 102034768Speter /* Save the adler32 of the preset dictionary: */ 102134768Speter if (s->strstart != 0) { 102234768Speter putShortMSB(s, (uInt)(strm->adler >> 16)); 102334768Speter putShortMSB(s, (uInt)(strm->adler & 0xffff)); 102434768Speter } 102534768Speter strm->adler = 1L; 102628415Speter } 102728415Speter 102828415Speter /* Flush as much pending output as possible */ 102934768Speter if (s->pending != 0) { 103028415Speter flush_pending(strm); 103134768Speter if (strm->avail_out == 0) { 103234768Speter /* Since avail_out is 0, deflate will be called again with 103334768Speter * more output space, but possibly with both pending and 103434768Speter * avail_in equal to zero. There won't be anything to do, 103534768Speter * but this is not an error situation so make sure we 103634768Speter * return OK instead of BUF_ERROR at next call of deflate: 103734768Speter */ 103834768Speter s->last_flush = -1; 103934768Speter return Z_OK; 104034768Speter } 104128415Speter 104234768Speter /* Make sure there is something to do and avoid duplicate consecutive 104334768Speter * flushes. For repeated and useless calls with Z_FINISH, we keep 104434768Speter * returning Z_STREAM_END instead of Z_BUFF_ERROR. 104528415Speter */ 104634768Speter } else if (strm->avail_in == 0 && flush <= old_flush && 104734768Speter flush != Z_FINISH) { 104834768Speter ERR_RETURN(strm, Z_BUF_ERROR); 104928415Speter } 105028415Speter 105128415Speter /* User must not provide more input after the first FINISH: */ 105234768Speter if (s->status == FINISH_STATE && strm->avail_in != 0) { 105328415Speter ERR_RETURN(strm, Z_BUF_ERROR); 105428415Speter } 105528415Speter 105628415Speter /* Start a new block or continue the current one. 105728415Speter */ 105834768Speter if (strm->avail_in != 0 || s->lookahead != 0 || 105934768Speter (flush != Z_NO_FLUSH && s->status != FINISH_STATE)) { 106034768Speter block_state bstate; 106128415Speter 106234768Speter bstate = (*(configuration_table[s->level].func))(s, flush); 106334768Speter 106434768Speter if (bstate == finish_started || bstate == finish_done) { 106534768Speter s->status = FINISH_STATE; 106628415Speter } 106734768Speter if (bstate == need_more || bstate == finish_started) { 106834768Speter if (strm->avail_out == 0) { 106934768Speter s->last_flush = -1; /* avoid BUF_ERROR next call, see above */ 107034768Speter } 107128415Speter return Z_OK; 107234768Speter /* If flush != Z_NO_FLUSH && avail_out == 0, the next call 107334768Speter * of deflate should use the same flush parameter to make sure 107434768Speter * that the flush is complete. So we don't have to output an 107534768Speter * empty block here, this will be done at next call. This also 107634768Speter * ensures that for a very small output buffer, we emit at most 107734768Speter * one empty block. 107828415Speter */ 107934768Speter } 108034768Speter if (bstate == block_done) { 108134768Speter if (flush == Z_PARTIAL_FLUSH) { 108234768Speter _tr_align(s); 108334768Speter } else if (flush == Z_PACKET_FLUSH) { 108434768Speter /* Output just the 3-bit `stored' block type value, 108534768Speter but not a zero length. */ 108634768Speter _tr_stored_type_only(s); 108734768Speter } else { /* FULL_FLUSH or SYNC_FLUSH */ 108834768Speter _tr_stored_block(s, (char*)0, 0L, 0); 108934768Speter /* For a full flush, this empty block will be recognized 109034768Speter * as a special marker by inflate_sync(). 109134768Speter */ 109234768Speter if (flush == Z_FULL_FLUSH) { 109334768Speter CLEAR_HASH(s); /* forget history */ 109434768Speter } 109534768Speter } 109634768Speter flush_pending(strm); 109734768Speter if (strm->avail_out == 0) { 109834768Speter s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */ 109934768Speter return Z_OK; 110028415Speter } 110134768Speter } 110228415Speter } 110328415Speter Assert(strm->avail_out > 0, "bug2"); 110428415Speter 110528415Speter if (flush != Z_FINISH) return Z_OK; 110634768Speter if (s->noheader) return Z_STREAM_END; 110728415Speter 110828415Speter /* Write the zlib trailer (adler32) */ 110934768Speter putShortMSB(s, (uInt)(strm->adler >> 16)); 111034768Speter putShortMSB(s, (uInt)(strm->adler & 0xffff)); 111128415Speter flush_pending(strm); 111228415Speter /* If avail_out is zero, the application will call deflate again 111328415Speter * to flush the rest. 111428415Speter */ 111534768Speter s->noheader = -1; /* write the trailer only once! */ 111634768Speter return s->pending != 0 ? Z_OK : Z_STREAM_END; 111728415Speter} 111828415Speter 111928415Speter/* ========================================================================= */ 112028415Speterint deflateEnd (strm) 112134768Speter z_streamp strm; 112228415Speter{ 112334768Speter int status; 112434768Speter deflate_state *s; 112528415Speter 112634768Speter if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR; 112734768Speter s = (deflate_state *) strm->state; 112828415Speter 112934768Speter status = s->status; 113034768Speter if (status != INIT_STATE && status != BUSY_STATE && 113134768Speter status != FINISH_STATE) { 113234768Speter return Z_STREAM_ERROR; 113334768Speter } 113428415Speter 113534768Speter /* Deallocate in reverse order of allocations: */ 113634768Speter TRY_FREE(strm, s->pending_buf); 113734768Speter TRY_FREE(strm, s->head); 113834768Speter TRY_FREE(strm, s->prev); 113934768Speter TRY_FREE(strm, s->window); 114034768Speter 114134768Speter ZFREE(strm, s); 114228415Speter strm->state = Z_NULL; 114328415Speter 114434768Speter return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 114534768Speter} 114634768Speter 114734768Speter/* ========================================================================= 114834768Speter * Copy the source state to the destination state. 114934768Speter */ 115034768Speterint deflateCopy (dest, source) 115134768Speter z_streamp dest; 115234768Speter z_streamp source; 115334768Speter{ 115434768Speter deflate_state *ds; 115534768Speter deflate_state *ss; 115634768Speter ushf *overlay; 115734768Speter 115834768Speter if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) 115934768Speter return Z_STREAM_ERROR; 116034768Speter ss = (deflate_state *) source->state; 116134768Speter 116237065Speter zmemcpy(dest, source, sizeof(*dest)); 116334768Speter 116434768Speter ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state)); 116534768Speter if (ds == Z_NULL) return Z_MEM_ERROR; 116634768Speter dest->state = (struct internal_state FAR *) ds; 116737065Speter zmemcpy(ds, ss, sizeof(*ds)); 116834768Speter ds->strm = dest; 116934768Speter 117034768Speter ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte)); 117134768Speter ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos)); 117234768Speter ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos)); 117334768Speter overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2); 117434768Speter ds->pending_buf = (uchf *) overlay; 117534768Speter 117634768Speter if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL || 117734768Speter ds->pending_buf == Z_NULL) { 117834768Speter deflateEnd (dest); 117934768Speter return Z_MEM_ERROR; 118034768Speter } 118134768Speter /* ??? following zmemcpy doesn't work for 16-bit MSDOS */ 118234768Speter zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte)); 118334768Speter zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos)); 118434768Speter zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos)); 118534768Speter zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size); 118634768Speter 118734768Speter ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf); 118834768Speter ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush); 118934768Speter ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize; 119034768Speter 119134768Speter ds->l_desc.dyn_tree = ds->dyn_ltree; 119234768Speter ds->d_desc.dyn_tree = ds->dyn_dtree; 119334768Speter ds->bl_desc.dyn_tree = ds->bl_tree; 119434768Speter 119528415Speter return Z_OK; 119628415Speter} 119728415Speter 119828415Speter/* =========================================================================== 119934768Speter * Return the number of bytes of output which are immediately available 120034768Speter * for output from the decompressor. 120134768Speter */ 120234768Speterint deflateOutputPending (strm) 120334768Speter z_streamp strm; 120434768Speter{ 120534768Speter if (strm == Z_NULL || strm->state == Z_NULL) return 0; 120634768Speter 120734768Speter return ((deflate_state *)(strm->state))->pending; 120834768Speter} 120934768Speter 121034768Speter/* =========================================================================== 121128415Speter * Read a new buffer from the current input stream, update the adler32 121234768Speter * and total number of bytes read. All deflate() input goes through 121334768Speter * this function so some applications may wish to modify it to avoid 121434768Speter * allocating a large strm->next_in buffer and copying from it. 121534768Speter * (See also flush_pending()). 121628415Speter */ 121728415Speterlocal int read_buf(strm, buf, size) 121834768Speter z_streamp strm; 121928415Speter charf *buf; 122028415Speter unsigned size; 122128415Speter{ 122228415Speter unsigned len = strm->avail_in; 122328415Speter 122428415Speter if (len > size) len = size; 122528415Speter if (len == 0) return 0; 122628415Speter 122728415Speter strm->avail_in -= len; 122828415Speter 122934768Speter if (!((deflate_state *)(strm->state))->noheader) { 123034768Speter strm->adler = adler32(strm->adler, strm->next_in, len); 123128415Speter } 123228415Speter zmemcpy(buf, strm->next_in, len); 123328415Speter strm->next_in += len; 123428415Speter strm->total_in += len; 123528415Speter 123628415Speter return (int)len; 123728415Speter} 123828415Speter 123928415Speter/* =========================================================================== 124028415Speter * Initialize the "longest match" routines for a new zlib stream 124128415Speter */ 124228415Speterlocal void lm_init (s) 124328415Speter deflate_state *s; 124428415Speter{ 124528415Speter s->window_size = (ulg)2L*s->w_size; 124628415Speter 124728415Speter CLEAR_HASH(s); 124828415Speter 124928415Speter /* Set the default configuration parameters: 125028415Speter */ 125128415Speter s->max_lazy_match = configuration_table[s->level].max_lazy; 125228415Speter s->good_match = configuration_table[s->level].good_length; 125328415Speter s->nice_match = configuration_table[s->level].nice_length; 125428415Speter s->max_chain_length = configuration_table[s->level].max_chain; 125528415Speter 125628415Speter s->strstart = 0; 125728415Speter s->block_start = 0L; 125828415Speter s->lookahead = 0; 125934768Speter s->match_length = s->prev_length = MIN_MATCH-1; 126028415Speter s->match_available = 0; 126128415Speter s->ins_h = 0; 126228415Speter#ifdef ASMV 126328415Speter match_init(); /* initialize the asm code */ 126428415Speter#endif 126528415Speter} 126628415Speter 126728415Speter/* =========================================================================== 126828415Speter * Set match_start to the longest match starting at the given string and 126928415Speter * return its length. Matches shorter or equal to prev_length are discarded, 127028415Speter * in which case the result is equal to prev_length and match_start is 127128415Speter * garbage. 127228415Speter * IN assertions: cur_match is the head of the hash chain for the current 127328415Speter * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 127434768Speter * OUT assertion: the match length is not greater than s->lookahead. 127528415Speter */ 127628415Speter#ifndef ASMV 127728415Speter/* For 80x86 and 680x0, an optimized version will be provided in match.asm or 127828415Speter * match.S. The code will be functionally equivalent. 127928415Speter */ 128034768Speterlocal uInt longest_match(s, cur_match) 128128415Speter deflate_state *s; 128228415Speter IPos cur_match; /* current match */ 128328415Speter{ 128428415Speter unsigned chain_length = s->max_chain_length;/* max hash chain length */ 1285331643Sdim Bytef *scan = s->window + s->strstart; /* current string */ 1286331643Sdim Bytef *match; /* matched string */ 1287331643Sdim int len; /* length of current match */ 128828415Speter int best_len = s->prev_length; /* best match length so far */ 128934768Speter int nice_match = s->nice_match; /* stop if match long enough */ 129028415Speter IPos limit = s->strstart > (IPos)MAX_DIST(s) ? 129128415Speter s->strstart - (IPos)MAX_DIST(s) : NIL; 129228415Speter /* Stop when cur_match becomes <= limit. To simplify the code, 129328415Speter * we prevent matches with the string of window index 0. 129428415Speter */ 129528415Speter Posf *prev = s->prev; 129628415Speter uInt wmask = s->w_mask; 129728415Speter 129828415Speter#ifdef UNALIGNED_OK 129928415Speter /* Compare two bytes at a time. Note: this is not always beneficial. 130028415Speter * Try with and without -DUNALIGNED_OK to check. 130128415Speter */ 1302331643Sdim Bytef *strend = s->window + s->strstart + MAX_MATCH - 1; 1303331643Sdim ush scan_start = *(ushf*)scan; 1304331643Sdim ush scan_end = *(ushf*)(scan+best_len-1); 130528415Speter#else 1306331643Sdim Bytef *strend = s->window + s->strstart + MAX_MATCH; 1307331643Sdim Byte scan_end1 = scan[best_len-1]; 1308331643Sdim Byte scan_end = scan[best_len]; 130928415Speter#endif 131028415Speter 131128415Speter /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 131228415Speter * It is easy to get rid of this optimization if necessary. 131328415Speter */ 131428415Speter Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever"); 131528415Speter 131628415Speter /* Do not waste too much time if we already have a good match: */ 131728415Speter if (s->prev_length >= s->good_match) { 131828415Speter chain_length >>= 2; 131928415Speter } 132034768Speter /* Do not look for matches beyond the end of the input. This is necessary 132134768Speter * to make deflate deterministic. 132234768Speter */ 132334768Speter if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead; 132434768Speter 132528415Speter Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead"); 132628415Speter 132728415Speter do { 132828415Speter Assert(cur_match < s->strstart, "no future"); 132928415Speter match = s->window + cur_match; 133028415Speter 133128415Speter /* Skip to next match if the match length cannot increase 133228415Speter * or if the match length is less than 2: 133328415Speter */ 133428415Speter#if (defined(UNALIGNED_OK) && MAX_MATCH == 258) 133528415Speter /* This code assumes sizeof(unsigned short) == 2. Do not use 133628415Speter * UNALIGNED_OK if your compiler uses a different size. 133728415Speter */ 133828415Speter if (*(ushf*)(match+best_len-1) != scan_end || 133928415Speter *(ushf*)match != scan_start) continue; 134028415Speter 134128415Speter /* It is not necessary to compare scan[2] and match[2] since they are 134228415Speter * always equal when the other bytes match, given that the hash keys 134328415Speter * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at 134428415Speter * strstart+3, +5, ... up to strstart+257. We check for insufficient 134528415Speter * lookahead only every 4th comparison; the 128th check will be made 134628415Speter * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is 134728415Speter * necessary to put more guard bytes at the end of the window, or 134828415Speter * to check more often for insufficient lookahead. 134928415Speter */ 135028415Speter Assert(scan[2] == match[2], "scan[2]?"); 135128415Speter scan++, match++; 135228415Speter do { 135328415Speter } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) && 135428415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 135528415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 135628415Speter *(ushf*)(scan+=2) == *(ushf*)(match+=2) && 135728415Speter scan < strend); 135828415Speter /* The funny "do {}" generates better code on most compilers */ 135928415Speter 136028415Speter /* Here, scan <= window+strstart+257 */ 136128415Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 136228415Speter if (*scan == *match) scan++; 136328415Speter 136428415Speter len = (MAX_MATCH - 1) - (int)(strend-scan); 136528415Speter scan = strend - (MAX_MATCH-1); 136628415Speter 136728415Speter#else /* UNALIGNED_OK */ 136828415Speter 136928415Speter if (match[best_len] != scan_end || 137028415Speter match[best_len-1] != scan_end1 || 137128415Speter *match != *scan || 137228415Speter *++match != scan[1]) continue; 137328415Speter 137428415Speter /* The check at best_len-1 can be removed because it will be made 137528415Speter * again later. (This heuristic is not always a win.) 137628415Speter * It is not necessary to compare scan[2] and match[2] since they 137728415Speter * are always equal when the other bytes match, given that 137828415Speter * the hash keys are equal and that HASH_BITS >= 8. 137928415Speter */ 138028415Speter scan += 2, match++; 138128415Speter Assert(*scan == *match, "match[2]?"); 138228415Speter 138328415Speter /* We check for insufficient lookahead only every 8th comparison; 138428415Speter * the 256th check will be made at strstart+258. 138528415Speter */ 138628415Speter do { 138728415Speter } while (*++scan == *++match && *++scan == *++match && 138828415Speter *++scan == *++match && *++scan == *++match && 138928415Speter *++scan == *++match && *++scan == *++match && 139028415Speter *++scan == *++match && *++scan == *++match && 139128415Speter scan < strend); 139228415Speter 139328415Speter Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan"); 139428415Speter 139528415Speter len = MAX_MATCH - (int)(strend - scan); 139628415Speter scan = strend - MAX_MATCH; 139728415Speter 139828415Speter#endif /* UNALIGNED_OK */ 139928415Speter 140028415Speter if (len > best_len) { 140128415Speter s->match_start = cur_match; 140228415Speter best_len = len; 140334768Speter if (len >= nice_match) break; 140428415Speter#ifdef UNALIGNED_OK 140528415Speter scan_end = *(ushf*)(scan+best_len-1); 140628415Speter#else 140728415Speter scan_end1 = scan[best_len-1]; 140828415Speter scan_end = scan[best_len]; 140928415Speter#endif 141028415Speter } 141128415Speter } while ((cur_match = prev[cur_match & wmask]) > limit 141228415Speter && --chain_length != 0); 141328415Speter 141434768Speter if ((uInt)best_len <= s->lookahead) return best_len; 141534768Speter return s->lookahead; 141628415Speter} 141728415Speter#endif /* ASMV */ 141828415Speter 141928415Speter#ifdef DEBUG_ZLIB 142028415Speter/* =========================================================================== 142128415Speter * Check that the match at match_start is indeed a match. 142228415Speter */ 142328415Speterlocal void check_match(s, start, match, length) 142428415Speter deflate_state *s; 142528415Speter IPos start, match; 142628415Speter int length; 142728415Speter{ 142828415Speter /* check that the match is indeed a match */ 142934768Speter if (zmemcmp((charf *)s->window + match, 143028415Speter (charf *)s->window + start, length) != EQUAL) { 143134768Speter fprintf(stderr, " start %u, match %u, length %d\n", 143234768Speter start, match, length); 143334768Speter do { 143434768Speter fprintf(stderr, "%c%c", s->window[match++], s->window[start++]); 143534768Speter } while (--length != 0); 143628415Speter z_error("invalid match"); 143728415Speter } 143834768Speter if (z_verbose > 1) { 143928415Speter fprintf(stderr,"\\[%d,%d]", start-match, length); 144028415Speter do { putc(s->window[start++], stderr); } while (--length != 0); 144128415Speter } 144228415Speter} 144328415Speter#else 144428415Speter# define check_match(s, start, match, length) 144528415Speter#endif 144628415Speter 144728415Speter/* =========================================================================== 144828415Speter * Fill the window when the lookahead becomes insufficient. 144928415Speter * Updates strstart and lookahead. 145028415Speter * 145128415Speter * IN assertion: lookahead < MIN_LOOKAHEAD 145228415Speter * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 145328415Speter * At least one byte has been read, or avail_in == 0; reads are 145428415Speter * performed for at least two bytes (required for the zip translate_eol 145528415Speter * option -- not supported here). 145628415Speter */ 145728415Speterlocal void fill_window(s) 145828415Speter deflate_state *s; 145928415Speter{ 1460331643Sdim unsigned n, m; 1461331643Sdim Posf *p; 146228415Speter unsigned more; /* Amount of free space at the end of the window. */ 146328415Speter uInt wsize = s->w_size; 146428415Speter 146528415Speter do { 146628415Speter more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart); 146728415Speter 146828415Speter /* Deal with !@#$% 64K limit: */ 146928415Speter if (more == 0 && s->strstart == 0 && s->lookahead == 0) { 147028415Speter more = wsize; 147134768Speter 147228415Speter } else if (more == (unsigned)(-1)) { 147328415Speter /* Very unlikely, but possible on 16 bit machine if strstart == 0 147428415Speter * and lookahead == 1 (input done one byte at time) 147528415Speter */ 147628415Speter more--; 147728415Speter 147828415Speter /* If the window is almost full and there is insufficient lookahead, 147928415Speter * move the upper half to the lower one to make room in the upper half. 148028415Speter */ 148128415Speter } else if (s->strstart >= wsize+MAX_DIST(s)) { 148228415Speter 148328415Speter zmemcpy((charf *)s->window, (charf *)s->window+wsize, 148428415Speter (unsigned)wsize); 148528415Speter s->match_start -= wsize; 148628415Speter s->strstart -= wsize; /* we now have strstart >= MAX_DIST */ 148728415Speter s->block_start -= (long) wsize; 148828415Speter 148928415Speter /* Slide the hash table (could be avoided with 32 bit values 149034768Speter at the expense of memory usage). We slide even when level == 0 149134768Speter to keep the hash table consistent if we switch back to level > 0 149234768Speter later. (Using level 0 permanently is not an optimal usage of 149334768Speter zlib, so we don't care about this pathological case.) 149428415Speter */ 149528415Speter n = s->hash_size; 149628415Speter p = &s->head[n]; 149728415Speter do { 149828415Speter m = *--p; 149928415Speter *p = (Pos)(m >= wsize ? m-wsize : NIL); 150028415Speter } while (--n); 150128415Speter 150228415Speter n = wsize; 150328415Speter p = &s->prev[n]; 150428415Speter do { 150528415Speter m = *--p; 150628415Speter *p = (Pos)(m >= wsize ? m-wsize : NIL); 150728415Speter /* If n is not on any hash chain, prev[n] is garbage but 150828415Speter * its value will never be used. 150928415Speter */ 151028415Speter } while (--n); 151128415Speter more += wsize; 151228415Speter } 151328415Speter if (s->strm->avail_in == 0) return; 151428415Speter 151528415Speter /* If there was no sliding: 151628415Speter * strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 151728415Speter * more == window_size - lookahead - strstart 151828415Speter * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 151928415Speter * => more >= window_size - 2*WSIZE + 2 152028415Speter * In the BIG_MEM or MMAP case (not yet supported), 152128415Speter * window_size == input_size + MIN_LOOKAHEAD && 152228415Speter * strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 152328415Speter * Otherwise, window_size == 2*WSIZE so more >= 2. 152428415Speter * If there was sliding, more >= WSIZE. So in all cases, more >= 2. 152528415Speter */ 152628415Speter Assert(more >= 2, "more < 2"); 152728415Speter 152828415Speter n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead, 152928415Speter more); 153028415Speter s->lookahead += n; 153128415Speter 153228415Speter /* Initialize the hash value now that we have some input: */ 153328415Speter if (s->lookahead >= MIN_MATCH) { 153428415Speter s->ins_h = s->window[s->strstart]; 153528415Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 153628415Speter#if MIN_MATCH != 3 153728415Speter Call UPDATE_HASH() MIN_MATCH-3 more times 153828415Speter#endif 153928415Speter } 154028415Speter /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 154128415Speter * but this is not important since only literal bytes will be emitted. 154228415Speter */ 154328415Speter 154428415Speter } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0); 154528415Speter} 154628415Speter 154728415Speter/* =========================================================================== 154828415Speter * Flush the current block, with given end-of-file flag. 154928415Speter * IN assertion: strstart is set to the end of the current match. 155028415Speter */ 155134768Speter#define FLUSH_BLOCK_ONLY(s, eof) { \ 155234768Speter _tr_flush_block(s, (s->block_start >= 0L ? \ 155334768Speter (charf *)&s->window[(unsigned)s->block_start] : \ 155434768Speter (charf *)Z_NULL), \ 155534768Speter (ulg)((long)s->strstart - s->block_start), \ 155634768Speter (eof)); \ 155728415Speter s->block_start = s->strstart; \ 155828415Speter flush_pending(s->strm); \ 155928415Speter Tracev((stderr,"[FLUSH]")); \ 156028415Speter} 156128415Speter 156228415Speter/* Same but force premature exit if necessary. */ 156334768Speter#define FLUSH_BLOCK(s, eof) { \ 156434768Speter FLUSH_BLOCK_ONLY(s, eof); \ 156534768Speter if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \ 156628415Speter} 156728415Speter 156828415Speter/* =========================================================================== 156934768Speter * Copy without compression as much as possible from the input stream, return 157034768Speter * the current block state. 157134768Speter * This function does not insert new strings in the dictionary since 157234768Speter * uncompressible data is probably not useful. This function is used 157334768Speter * only for the level=0 compression option. 157434768Speter * NOTE: this function should be optimized to avoid extra copying from 157534768Speter * window to pending_buf. 157634768Speter */ 157734768Speterlocal block_state deflate_stored(s, flush) 157834768Speter deflate_state *s; 157934768Speter int flush; 158034768Speter{ 158134768Speter /* Stored blocks are limited to 0xffff bytes, pending_buf is limited 158234768Speter * to pending_buf_size, and each stored block has a 5 byte header: 158334768Speter */ 158434768Speter ulg max_block_size = 0xffff; 158534768Speter ulg max_start; 158634768Speter 158734768Speter if (max_block_size > s->pending_buf_size - 5) { 158834768Speter max_block_size = s->pending_buf_size - 5; 158934768Speter } 159034768Speter 159134768Speter /* Copy as much as possible from input to output: */ 159234768Speter for (;;) { 159334768Speter /* Fill the window as much as possible: */ 159434768Speter if (s->lookahead <= 1) { 159534768Speter 159634768Speter Assert(s->strstart < s->w_size+MAX_DIST(s) || 159734768Speter s->block_start >= (long)s->w_size, "slide too late"); 159834768Speter 159934768Speter fill_window(s); 160034768Speter if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more; 160134768Speter 160234768Speter if (s->lookahead == 0) break; /* flush the current block */ 160334768Speter } 160434768Speter Assert(s->block_start >= 0L, "block gone"); 160534768Speter 160634768Speter s->strstart += s->lookahead; 160734768Speter s->lookahead = 0; 160834768Speter 160934768Speter /* Emit a stored block if pending_buf will be full: */ 161034768Speter max_start = s->block_start + max_block_size; 161134768Speter if (s->strstart == 0 || (ulg)s->strstart >= max_start) { 161234768Speter /* strstart == 0 is possible when wraparound on 16-bit machine */ 161334768Speter s->lookahead = (uInt)(s->strstart - max_start); 161434768Speter s->strstart = (uInt)max_start; 161534768Speter FLUSH_BLOCK(s, 0); 161634768Speter } 161734768Speter /* Flush if we may have to slide, otherwise block_start may become 161834768Speter * negative and the data will be gone: 161934768Speter */ 162034768Speter if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) { 162134768Speter FLUSH_BLOCK(s, 0); 162234768Speter } 162334768Speter } 162434768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 162534768Speter return flush == Z_FINISH ? finish_done : block_done; 162634768Speter} 162734768Speter 162834768Speter/* =========================================================================== 162934768Speter * Compress as much as possible from the input stream, return the current 163034768Speter * block state. 163134768Speter * This function does not perform lazy evaluation of matches and inserts 163228415Speter * new strings in the dictionary only for unmatched strings or for short 163328415Speter * matches. It is used only for the fast compression options. 163428415Speter */ 163534768Speterlocal block_state deflate_fast(s, flush) 163628415Speter deflate_state *s; 163728415Speter int flush; 163828415Speter{ 163928415Speter IPos hash_head = NIL; /* head of the hash chain */ 164034768Speter int bflush; /* set if current block must be flushed */ 164128415Speter 164228415Speter for (;;) { 164328415Speter /* Make sure that we always have enough lookahead, except 164428415Speter * at the end of the input file. We need MAX_MATCH bytes 164528415Speter * for the next match, plus MIN_MATCH bytes to insert the 164628415Speter * string following the next match. 164728415Speter */ 164828415Speter if (s->lookahead < MIN_LOOKAHEAD) { 164928415Speter fill_window(s); 165034768Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 165134768Speter return need_more; 165234768Speter } 165328415Speter if (s->lookahead == 0) break; /* flush the current block */ 165428415Speter } 165528415Speter 165628415Speter /* Insert the string window[strstart .. strstart+2] in the 165728415Speter * dictionary, and set hash_head to the head of the hash chain: 165828415Speter */ 165928415Speter if (s->lookahead >= MIN_MATCH) { 166028415Speter INSERT_STRING(s, s->strstart, hash_head); 166128415Speter } 166228415Speter 166328415Speter /* Find the longest match, discarding those <= prev_length. 166428415Speter * At this point we have always match_length < MIN_MATCH 166528415Speter */ 166628415Speter if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) { 166728415Speter /* To simplify the code, we prevent matches with the string 166828415Speter * of window index 0 (in particular we have to avoid a match 166928415Speter * of the string with itself at the start of the input file). 167028415Speter */ 167128415Speter if (s->strategy != Z_HUFFMAN_ONLY) { 167228415Speter s->match_length = longest_match (s, hash_head); 167328415Speter } 167428415Speter /* longest_match() sets match_start */ 167528415Speter } 167628415Speter if (s->match_length >= MIN_MATCH) { 167728415Speter check_match(s, s->strstart, s->match_start, s->match_length); 167828415Speter 167934768Speter bflush = _tr_tally(s, s->strstart - s->match_start, 168034768Speter s->match_length - MIN_MATCH); 168128415Speter 168228415Speter s->lookahead -= s->match_length; 168328415Speter 168428415Speter /* Insert new strings in the hash table only if the match length 168528415Speter * is not too large. This saves time but degrades compression. 168628415Speter */ 168728415Speter if (s->match_length <= s->max_insert_length && 168828415Speter s->lookahead >= MIN_MATCH) { 168928415Speter s->match_length--; /* string at strstart already in hash table */ 169028415Speter do { 169128415Speter s->strstart++; 169228415Speter INSERT_STRING(s, s->strstart, hash_head); 169328415Speter /* strstart never exceeds WSIZE-MAX_MATCH, so there are 169428415Speter * always MIN_MATCH bytes ahead. 169528415Speter */ 169628415Speter } while (--s->match_length != 0); 169728415Speter s->strstart++; 169828415Speter } else { 169928415Speter s->strstart += s->match_length; 170028415Speter s->match_length = 0; 170128415Speter s->ins_h = s->window[s->strstart]; 170228415Speter UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]); 170328415Speter#if MIN_MATCH != 3 170428415Speter Call UPDATE_HASH() MIN_MATCH-3 more times 170528415Speter#endif 170628415Speter /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not 170728415Speter * matter since it will be recomputed at next deflate call. 170828415Speter */ 170928415Speter } 171028415Speter } else { 171128415Speter /* No match, output a literal byte */ 171228415Speter Tracevv((stderr,"%c", s->window[s->strstart])); 171334768Speter bflush = _tr_tally (s, 0, s->window[s->strstart]); 171428415Speter s->lookahead--; 171528415Speter s->strstart++; 171628415Speter } 171734768Speter if (bflush) FLUSH_BLOCK(s, 0); 171828415Speter } 171934768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 172034768Speter return flush == Z_FINISH ? finish_done : block_done; 172128415Speter} 172228415Speter 172328415Speter/* =========================================================================== 172428415Speter * Same as above, but achieves better compression. We use a lazy 172528415Speter * evaluation for matches: a match is finally adopted only if there is 172628415Speter * no better match at the next window position. 172728415Speter */ 172834768Speterlocal block_state deflate_slow(s, flush) 172928415Speter deflate_state *s; 173028415Speter int flush; 173128415Speter{ 173228415Speter IPos hash_head = NIL; /* head of hash chain */ 173328415Speter int bflush; /* set if current block must be flushed */ 173428415Speter 173528415Speter /* Process the input block. */ 173628415Speter for (;;) { 173728415Speter /* Make sure that we always have enough lookahead, except 173828415Speter * at the end of the input file. We need MAX_MATCH bytes 173928415Speter * for the next match, plus MIN_MATCH bytes to insert the 174028415Speter * string following the next match. 174128415Speter */ 174228415Speter if (s->lookahead < MIN_LOOKAHEAD) { 174328415Speter fill_window(s); 174434768Speter if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 174534768Speter return need_more; 174634768Speter } 174728415Speter if (s->lookahead == 0) break; /* flush the current block */ 174828415Speter } 174928415Speter 175028415Speter /* Insert the string window[strstart .. strstart+2] in the 175128415Speter * dictionary, and set hash_head to the head of the hash chain: 175228415Speter */ 175328415Speter if (s->lookahead >= MIN_MATCH) { 175428415Speter INSERT_STRING(s, s->strstart, hash_head); 175528415Speter } 175628415Speter 175728415Speter /* Find the longest match, discarding those <= prev_length. 175828415Speter */ 175928415Speter s->prev_length = s->match_length, s->prev_match = s->match_start; 176028415Speter s->match_length = MIN_MATCH-1; 176128415Speter 176228415Speter if (hash_head != NIL && s->prev_length < s->max_lazy_match && 176328415Speter s->strstart - hash_head <= MAX_DIST(s)) { 176428415Speter /* To simplify the code, we prevent matches with the string 176528415Speter * of window index 0 (in particular we have to avoid a match 176628415Speter * of the string with itself at the start of the input file). 176728415Speter */ 176828415Speter if (s->strategy != Z_HUFFMAN_ONLY) { 176928415Speter s->match_length = longest_match (s, hash_head); 177028415Speter } 177128415Speter /* longest_match() sets match_start */ 177228415Speter 177328415Speter if (s->match_length <= 5 && (s->strategy == Z_FILTERED || 177428415Speter (s->match_length == MIN_MATCH && 177528415Speter s->strstart - s->match_start > TOO_FAR))) { 177628415Speter 177728415Speter /* If prev_match is also MIN_MATCH, match_start is garbage 177828415Speter * but we will ignore the current match anyway. 177928415Speter */ 178028415Speter s->match_length = MIN_MATCH-1; 178128415Speter } 178228415Speter } 178328415Speter /* If there was a match at the previous step and the current 178428415Speter * match is not better, output the previous match: 178528415Speter */ 178628415Speter if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) { 178728415Speter uInt max_insert = s->strstart + s->lookahead - MIN_MATCH; 178828415Speter /* Do not insert strings in hash table beyond this. */ 178928415Speter 179028415Speter check_match(s, s->strstart-1, s->prev_match, s->prev_length); 179128415Speter 179234768Speter bflush = _tr_tally(s, s->strstart -1 - s->prev_match, 179334768Speter s->prev_length - MIN_MATCH); 179428415Speter 179528415Speter /* Insert in hash table all strings up to the end of the match. 179628415Speter * strstart-1 and strstart are already inserted. If there is not 179728415Speter * enough lookahead, the last two strings are not inserted in 179828415Speter * the hash table. 179928415Speter */ 180028415Speter s->lookahead -= s->prev_length-1; 180128415Speter s->prev_length -= 2; 180228415Speter do { 180328415Speter if (++s->strstart <= max_insert) { 180428415Speter INSERT_STRING(s, s->strstart, hash_head); 180528415Speter } 180628415Speter } while (--s->prev_length != 0); 180728415Speter s->match_available = 0; 180828415Speter s->match_length = MIN_MATCH-1; 180928415Speter s->strstart++; 181028415Speter 181134768Speter if (bflush) FLUSH_BLOCK(s, 0); 181228415Speter 181328415Speter } else if (s->match_available) { 181428415Speter /* If there was no match at the previous position, output a 181528415Speter * single literal. If there was a match but the current match 181628415Speter * is longer, truncate the previous match to a single literal. 181728415Speter */ 181828415Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 181934768Speter if (_tr_tally (s, 0, s->window[s->strstart-1])) { 182034768Speter FLUSH_BLOCK_ONLY(s, 0); 182128415Speter } 182228415Speter s->strstart++; 182328415Speter s->lookahead--; 182434768Speter if (s->strm->avail_out == 0) return need_more; 182528415Speter } else { 182628415Speter /* There is no previous match to compare with, wait for 182728415Speter * the next step to decide. 182828415Speter */ 182928415Speter s->match_available = 1; 183028415Speter s->strstart++; 183128415Speter s->lookahead--; 183228415Speter } 183328415Speter } 183428415Speter Assert (flush != Z_NO_FLUSH, "no flush?"); 183528415Speter if (s->match_available) { 183628415Speter Tracevv((stderr,"%c", s->window[s->strstart-1])); 183734768Speter _tr_tally (s, 0, s->window[s->strstart-1]); 183828415Speter s->match_available = 0; 183928415Speter } 184034768Speter FLUSH_BLOCK(s, flush == Z_FINISH); 184134768Speter return flush == Z_FINISH ? finish_done : block_done; 184228415Speter} 184334768Speter/* --- deflate.c */ 184428415Speter 184534768Speter/* +++ trees.c */ 184628415Speter/* trees.c -- output deflated data using Huffman coding 184734768Speter * Copyright (C) 1995-1996 Jean-loup Gailly 184828415Speter * For conditions of distribution and use, see copyright notice in zlib.h 184928415Speter */ 185028415Speter 185128415Speter/* 185228415Speter * ALGORITHM 185328415Speter * 185428415Speter * The "deflation" process uses several Huffman trees. The more 185528415Speter * common source values are represented by shorter bit sequences. 185628415Speter * 185728415Speter * Each code tree is stored in a compressed form which is itself 185828415Speter * a Huffman encoding of the lengths of all the code strings (in 185928415Speter * ascending order by source values). The actual code strings are 186028415Speter * reconstructed from the lengths in the inflate process, as described 186128415Speter * in the deflate specification. 186228415Speter * 186328415Speter * REFERENCES 186428415Speter * 186528415Speter * Deutsch, L.P.,"'Deflate' Compressed Data Format Specification". 186628415Speter * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc 186728415Speter * 186828415Speter * Storer, James A. 186928415Speter * Data Compression: Methods and Theory, pp. 49-50. 187028415Speter * Computer Science Press, 1988. ISBN 0-7167-8156-5. 187128415Speter * 187228415Speter * Sedgewick, R. 187328415Speter * Algorithms, p290. 187428415Speter * Addison-Wesley, 1983. ISBN 0-201-06672-6. 187528415Speter */ 187628415Speter 187734768Speter/* From: trees.c,v 1.11 1996/07/24 13:41:06 me Exp $ */ 187828415Speter 187934768Speter/* #include "deflate.h" */ 188034768Speter 188128415Speter#ifdef DEBUG_ZLIB 188228415Speter# include <ctype.h> 188328415Speter#endif 188428415Speter 188528415Speter/* =========================================================================== 188628415Speter * Constants 188728415Speter */ 188828415Speter 188928415Speter#define MAX_BL_BITS 7 189028415Speter/* Bit length codes must not exceed MAX_BL_BITS bits */ 189128415Speter 189228415Speter#define END_BLOCK 256 189328415Speter/* end of block literal code */ 189428415Speter 189528415Speter#define REP_3_6 16 189628415Speter/* repeat previous bit length 3-6 times (2 bits of repeat count) */ 189728415Speter 189828415Speter#define REPZ_3_10 17 189928415Speter/* repeat a zero length 3-10 times (3 bits of repeat count) */ 190028415Speter 190128415Speter#define REPZ_11_138 18 190228415Speter/* repeat a zero length 11-138 times (7 bits of repeat count) */ 190328415Speter 190428415Speterlocal int extra_lbits[LENGTH_CODES] /* extra bits for each length code */ 190528415Speter = {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}; 190628415Speter 190728415Speterlocal int extra_dbits[D_CODES] /* extra bits for each distance code */ 190828415Speter = {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}; 190928415Speter 191028415Speterlocal int extra_blbits[BL_CODES]/* extra bits for each bit length code */ 191128415Speter = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7}; 191228415Speter 191328415Speterlocal uch bl_order[BL_CODES] 191428415Speter = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15}; 191528415Speter/* The lengths of the bit length codes are sent in order of decreasing 191628415Speter * probability, to avoid transmitting the lengths for unused bit length codes. 191728415Speter */ 191828415Speter 191928415Speter#define Buf_size (8 * 2*sizeof(char)) 192028415Speter/* Number of bits used within bi_buf. (bi_buf might be implemented on 192128415Speter * more than 16 bits on some systems.) 192228415Speter */ 192328415Speter 192428415Speter/* =========================================================================== 192528415Speter * Local data. These are initialized only once. 192628415Speter */ 192728415Speter 192828415Speterlocal ct_data static_ltree[L_CODES+2]; 192928415Speter/* The static literal tree. Since the bit lengths are imposed, there is no 193028415Speter * need for the L_CODES extra codes used during heap construction. However 193134768Speter * The codes 286 and 287 are needed to build a canonical tree (see _tr_init 193228415Speter * below). 193328415Speter */ 193428415Speter 193528415Speterlocal ct_data static_dtree[D_CODES]; 193628415Speter/* The static distance tree. (Actually a trivial tree since all codes use 193728415Speter * 5 bits.) 193828415Speter */ 193928415Speter 194028415Speterlocal uch dist_code[512]; 194128415Speter/* distance codes. The first 256 values correspond to the distances 194228415Speter * 3 .. 258, the last 256 values correspond to the top 8 bits of 194328415Speter * the 15 bit distances. 194428415Speter */ 194528415Speter 194628415Speterlocal uch length_code[MAX_MATCH-MIN_MATCH+1]; 194728415Speter/* length code for each normalized match length (0 == MIN_MATCH) */ 194828415Speter 194928415Speterlocal int base_length[LENGTH_CODES]; 195028415Speter/* First normalized length for each code (0 = MIN_MATCH) */ 195128415Speter 195228415Speterlocal int base_dist[D_CODES]; 195328415Speter/* First normalized distance for each code (0 = distance of 1) */ 195428415Speter 195528415Speterstruct static_tree_desc_s { 195628415Speter ct_data *static_tree; /* static tree or NULL */ 195728415Speter intf *extra_bits; /* extra bits for each code or NULL */ 195828415Speter int extra_base; /* base index for extra_bits */ 195928415Speter int elems; /* max number of elements in the tree */ 196028415Speter int max_length; /* max bit length for the codes */ 196128415Speter}; 196228415Speter 196328415Speterlocal static_tree_desc static_l_desc = 196428415Speter{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; 196528415Speter 196628415Speterlocal static_tree_desc static_d_desc = 196728415Speter{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; 196828415Speter 196928415Speterlocal static_tree_desc static_bl_desc = 197028415Speter{(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; 197128415Speter 197228415Speter/* =========================================================================== 197328415Speter * Local (static) routines in this file. 197428415Speter */ 197528415Speter 197634768Speterlocal void tr_static_init OF((void)); 197728415Speterlocal void init_block OF((deflate_state *s)); 197828415Speterlocal void pqdownheap OF((deflate_state *s, ct_data *tree, int k)); 197928415Speterlocal void gen_bitlen OF((deflate_state *s, tree_desc *desc)); 198028415Speterlocal void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count)); 198128415Speterlocal void build_tree OF((deflate_state *s, tree_desc *desc)); 198228415Speterlocal void scan_tree OF((deflate_state *s, ct_data *tree, int max_code)); 198328415Speterlocal void send_tree OF((deflate_state *s, ct_data *tree, int max_code)); 198428415Speterlocal int build_bl_tree OF((deflate_state *s)); 198528415Speterlocal void send_all_trees OF((deflate_state *s, int lcodes, int dcodes, 198628415Speter int blcodes)); 198728415Speterlocal void compress_block OF((deflate_state *s, ct_data *ltree, 198828415Speter ct_data *dtree)); 198928415Speterlocal void set_data_type OF((deflate_state *s)); 199028415Speterlocal unsigned bi_reverse OF((unsigned value, int length)); 199128415Speterlocal void bi_windup OF((deflate_state *s)); 199228415Speterlocal void bi_flush OF((deflate_state *s)); 199328415Speterlocal void copy_block OF((deflate_state *s, charf *buf, unsigned len, 199428415Speter int header)); 199528415Speter 199628415Speter#ifndef DEBUG_ZLIB 1997106696Salfred# define send_code(s, c, tree) send_bits(s, tree[(c)].Code, tree[(c)].Len) 199828415Speter /* Send a code of the given tree. c and tree must not have side effects */ 199928415Speter 200028415Speter#else /* DEBUG_ZLIB */ 200128415Speter# define send_code(s, c, tree) \ 200234768Speter { if (verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ 200328415Speter send_bits(s, tree[c].Code, tree[c].Len); } 200428415Speter#endif 200528415Speter 200628415Speter#define d_code(dist) \ 200728415Speter ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)]) 200828415Speter/* Mapping from a distance to a distance code. dist is the distance - 1 and 200928415Speter * must not have side effects. dist_code[256] and dist_code[257] are never 201028415Speter * used. 201128415Speter */ 201228415Speter 201328415Speter/* =========================================================================== 201428415Speter * Output a short LSB first on the stream. 201528415Speter * IN assertion: there is enough room in pendingBuf. 201628415Speter */ 201728415Speter#define put_short(s, w) { \ 201828415Speter put_byte(s, (uch)((w) & 0xff)); \ 201928415Speter put_byte(s, (uch)((ush)(w) >> 8)); \ 202028415Speter} 202128415Speter 202228415Speter/* =========================================================================== 202328415Speter * Send a value on a given number of bits. 202428415Speter * IN assertion: length <= 16 and value fits in length bits. 202528415Speter */ 202628415Speter#ifdef DEBUG_ZLIB 202728415Speterlocal void send_bits OF((deflate_state *s, int value, int length)); 202828415Speter 202928415Speterlocal void send_bits(s, value, length) 203028415Speter deflate_state *s; 203128415Speter int value; /* value to send */ 203228415Speter int length; /* number of bits */ 203328415Speter{ 203434768Speter Tracevv((stderr," l %2d v %4x ", length, value)); 203528415Speter Assert(length > 0 && length <= 15, "invalid length"); 203628415Speter s->bits_sent += (ulg)length; 203728415Speter 203828415Speter /* If not enough room in bi_buf, use (valid) bits from bi_buf and 203928415Speter * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 204028415Speter * unused bits in value. 204128415Speter */ 204228415Speter if (s->bi_valid > (int)Buf_size - length) { 204328415Speter s->bi_buf |= (value << s->bi_valid); 204428415Speter put_short(s, s->bi_buf); 204528415Speter s->bi_buf = (ush)value >> (Buf_size - s->bi_valid); 204628415Speter s->bi_valid += length - Buf_size; 204728415Speter } else { 204828415Speter s->bi_buf |= value << s->bi_valid; 204928415Speter s->bi_valid += length; 205028415Speter } 205128415Speter} 205228415Speter#else /* !DEBUG_ZLIB */ 205328415Speter 205428415Speter#define send_bits(s, value, length) \ 2055106696Salfred{ int len = (length);\ 2056106696Salfred if ((s)->bi_valid > (int)Buf_size - len) {\ 2057106696Salfred int val = (value);\ 2058106696Salfred (s)->bi_buf |= (val << (s)->bi_valid);\ 2059106696Salfred put_short((s), (s)->bi_buf);\ 2060106696Salfred (s)->bi_buf = (ush)val >> (Buf_size - (s)->bi_valid);\ 2061106696Salfred (s)->bi_valid += len - Buf_size;\ 206228415Speter } else {\ 2063106696Salfred (s)->bi_buf |= (value) << (s)->bi_valid;\ 2064106696Salfred (s)->bi_valid += len;\ 206528415Speter }\ 206628415Speter} 206728415Speter#endif /* DEBUG_ZLIB */ 206828415Speter 206928415Speter/* the arguments must not have side effects */ 207028415Speter 207128415Speter/* =========================================================================== 207234768Speter * Initialize the various 'constant' tables. In a multi-threaded environment, 207334768Speter * this function may be called by two threads concurrently, but this is 207434768Speter * harmless since both invocations do exactly the same thing. 207528415Speter */ 207634768Speterlocal void tr_static_init() 207728415Speter{ 207834768Speter static int static_init_done = 0; 207928415Speter int n; /* iterates over tree elements */ 208028415Speter int bits; /* bit counter */ 208128415Speter int length; /* length value */ 208228415Speter int code; /* code value */ 208328415Speter int dist; /* distance index */ 208428415Speter ush bl_count[MAX_BITS+1]; 208528415Speter /* number of codes at each bit length for an optimal tree */ 208628415Speter 208734768Speter if (static_init_done) return; 208834768Speter 208928415Speter /* Initialize the mapping length (0..255) -> length code (0..28) */ 209028415Speter length = 0; 209128415Speter for (code = 0; code < LENGTH_CODES-1; code++) { 209228415Speter base_length[code] = length; 209328415Speter for (n = 0; n < (1<<extra_lbits[code]); n++) { 209428415Speter length_code[length++] = (uch)code; 209528415Speter } 209628415Speter } 209734768Speter Assert (length == 256, "tr_static_init: length != 256"); 209828415Speter /* Note that the length 255 (match length 258) can be represented 209928415Speter * in two different ways: code 284 + 5 bits or code 285, so we 210028415Speter * overwrite length_code[255] to use the best encoding: 210128415Speter */ 210228415Speter length_code[length-1] = (uch)code; 210328415Speter 210428415Speter /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 210528415Speter dist = 0; 210628415Speter for (code = 0 ; code < 16; code++) { 210728415Speter base_dist[code] = dist; 210828415Speter for (n = 0; n < (1<<extra_dbits[code]); n++) { 210928415Speter dist_code[dist++] = (uch)code; 211028415Speter } 211128415Speter } 211234768Speter Assert (dist == 256, "tr_static_init: dist != 256"); 211328415Speter dist >>= 7; /* from now on, all distances are divided by 128 */ 211428415Speter for ( ; code < D_CODES; code++) { 211528415Speter base_dist[code] = dist << 7; 211628415Speter for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { 211728415Speter dist_code[256 + dist++] = (uch)code; 211828415Speter } 211928415Speter } 212034768Speter Assert (dist == 256, "tr_static_init: 256+dist != 512"); 212128415Speter 212228415Speter /* Construct the codes of the static literal tree */ 212328415Speter for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0; 212428415Speter n = 0; 212528415Speter while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++; 212628415Speter while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++; 212728415Speter while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++; 212828415Speter while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++; 212928415Speter /* Codes 286 and 287 do not exist, but we must include them in the 213028415Speter * tree construction to get a canonical Huffman tree (longest code 213128415Speter * all ones) 213228415Speter */ 213328415Speter gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count); 213428415Speter 213528415Speter /* The static distance tree is trivial: */ 213628415Speter for (n = 0; n < D_CODES; n++) { 213728415Speter static_dtree[n].Len = 5; 213834768Speter static_dtree[n].Code = bi_reverse((unsigned)n, 5); 213928415Speter } 214034768Speter static_init_done = 1; 214128415Speter} 214228415Speter 214328415Speter/* =========================================================================== 214428415Speter * Initialize the tree data structures for a new zlib stream. 214528415Speter */ 214634768Spetervoid _tr_init(s) 214728415Speter deflate_state *s; 214828415Speter{ 214934768Speter tr_static_init(); 215028415Speter 215128415Speter s->compressed_len = 0L; 215228415Speter 215328415Speter s->l_desc.dyn_tree = s->dyn_ltree; 215428415Speter s->l_desc.stat_desc = &static_l_desc; 215528415Speter 215628415Speter s->d_desc.dyn_tree = s->dyn_dtree; 215728415Speter s->d_desc.stat_desc = &static_d_desc; 215828415Speter 215928415Speter s->bl_desc.dyn_tree = s->bl_tree; 216028415Speter s->bl_desc.stat_desc = &static_bl_desc; 216128415Speter 216228415Speter s->bi_buf = 0; 216328415Speter s->bi_valid = 0; 216428415Speter s->last_eob_len = 8; /* enough lookahead for inflate */ 216528415Speter#ifdef DEBUG_ZLIB 216628415Speter s->bits_sent = 0L; 216728415Speter#endif 216828415Speter 216928415Speter /* Initialize the first block of the first file: */ 217028415Speter init_block(s); 217128415Speter} 217228415Speter 217328415Speter/* =========================================================================== 217428415Speter * Initialize a new block. 217528415Speter */ 217628415Speterlocal void init_block(s) 217728415Speter deflate_state *s; 217828415Speter{ 217928415Speter int n; /* iterates over tree elements */ 218028415Speter 218128415Speter /* Initialize the trees. */ 218228415Speter for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; 218328415Speter for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; 218428415Speter for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; 218528415Speter 218628415Speter s->dyn_ltree[END_BLOCK].Freq = 1; 218728415Speter s->opt_len = s->static_len = 0L; 218828415Speter s->last_lit = s->matches = 0; 218928415Speter} 219028415Speter 219128415Speter#define SMALLEST 1 219228415Speter/* Index within the heap array of least frequent node in the Huffman tree */ 219328415Speter 219428415Speter 219528415Speter/* =========================================================================== 219628415Speter * Remove the smallest element from the heap and recreate the heap with 219728415Speter * one less element. Updates heap and heap_len. 219828415Speter */ 219928415Speter#define pqremove(s, tree, top) \ 220028415Speter{\ 220128415Speter top = s->heap[SMALLEST]; \ 220228415Speter s->heap[SMALLEST] = s->heap[s->heap_len--]; \ 220328415Speter pqdownheap(s, tree, SMALLEST); \ 220428415Speter} 220528415Speter 220628415Speter/* =========================================================================== 220728415Speter * Compares to subtrees, using the tree depth as tie breaker when 220828415Speter * the subtrees have equal frequency. This minimizes the worst case length. 220928415Speter */ 221028415Speter#define smaller(tree, n, m, depth) \ 221128415Speter (tree[n].Freq < tree[m].Freq || \ 221228415Speter (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 221328415Speter 221428415Speter/* =========================================================================== 221528415Speter * Restore the heap property by moving down the tree starting at node k, 221628415Speter * exchanging a node with the smallest of its two sons if necessary, stopping 221728415Speter * when the heap property is re-established (each father smaller than its 221828415Speter * two sons). 221928415Speter */ 222028415Speterlocal void pqdownheap(s, tree, k) 222128415Speter deflate_state *s; 222228415Speter ct_data *tree; /* the tree to restore */ 222328415Speter int k; /* node to move down */ 222428415Speter{ 222528415Speter int v = s->heap[k]; 222628415Speter int j = k << 1; /* left son of k */ 222728415Speter while (j <= s->heap_len) { 222828415Speter /* Set j to the smallest of the two sons: */ 222928415Speter if (j < s->heap_len && 223028415Speter smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { 223128415Speter j++; 223228415Speter } 223328415Speter /* Exit if v is smaller than both sons */ 223428415Speter if (smaller(tree, v, s->heap[j], s->depth)) break; 223528415Speter 223628415Speter /* Exchange v with the smallest son */ 223728415Speter s->heap[k] = s->heap[j]; k = j; 223828415Speter 223928415Speter /* And continue down the tree, setting j to the left son of k */ 224028415Speter j <<= 1; 224128415Speter } 224228415Speter s->heap[k] = v; 224328415Speter} 224428415Speter 224528415Speter/* =========================================================================== 224628415Speter * Compute the optimal bit lengths for a tree and update the total bit length 224728415Speter * for the current block. 224828415Speter * IN assertion: the fields freq and dad are set, heap[heap_max] and 224928415Speter * above are the tree nodes sorted by increasing frequency. 225028415Speter * OUT assertions: the field len is set to the optimal bit length, the 225128415Speter * array bl_count contains the frequencies for each bit length. 225228415Speter * The length opt_len is updated; static_len is also updated if stree is 225328415Speter * not null. 225428415Speter */ 225528415Speterlocal void gen_bitlen(s, desc) 225628415Speter deflate_state *s; 225728415Speter tree_desc *desc; /* the tree descriptor */ 225828415Speter{ 225928415Speter ct_data *tree = desc->dyn_tree; 226028415Speter int max_code = desc->max_code; 226128415Speter ct_data *stree = desc->stat_desc->static_tree; 226228415Speter intf *extra = desc->stat_desc->extra_bits; 226328415Speter int base = desc->stat_desc->extra_base; 226428415Speter int max_length = desc->stat_desc->max_length; 226528415Speter int h; /* heap index */ 226628415Speter int n, m; /* iterate over the tree elements */ 226728415Speter int bits; /* bit length */ 226828415Speter int xbits; /* extra bits */ 226928415Speter ush f; /* frequency */ 227028415Speter int overflow = 0; /* number of elements with bit length too large */ 227128415Speter 227228415Speter for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; 227328415Speter 227428415Speter /* In a first pass, compute the optimal bit lengths (which may 227528415Speter * overflow in the case of the bit length tree). 227628415Speter */ 227728415Speter tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ 227828415Speter 227928415Speter for (h = s->heap_max+1; h < HEAP_SIZE; h++) { 228028415Speter n = s->heap[h]; 228128415Speter bits = tree[tree[n].Dad].Len + 1; 228228415Speter if (bits > max_length) bits = max_length, overflow++; 228328415Speter tree[n].Len = (ush)bits; 228428415Speter /* We overwrite tree[n].Dad which is no longer needed */ 228528415Speter 228628415Speter if (n > max_code) continue; /* not a leaf node */ 228728415Speter 228828415Speter s->bl_count[bits]++; 228928415Speter xbits = 0; 229028415Speter if (n >= base) xbits = extra[n-base]; 229128415Speter f = tree[n].Freq; 229228415Speter s->opt_len += (ulg)f * (bits + xbits); 229328415Speter if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); 229428415Speter } 229528415Speter if (overflow == 0) return; 229628415Speter 229728415Speter Trace((stderr,"\nbit length overflow\n")); 229828415Speter /* This happens for example on obj2 and pic of the Calgary corpus */ 229928415Speter 230028415Speter /* Find the first bit length which could increase: */ 230128415Speter do { 230228415Speter bits = max_length-1; 230328415Speter while (s->bl_count[bits] == 0) bits--; 230428415Speter s->bl_count[bits]--; /* move one leaf down the tree */ 230528415Speter s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ 230628415Speter s->bl_count[max_length]--; 230728415Speter /* The brother of the overflow item also moves one step up, 230828415Speter * but this does not affect bl_count[max_length] 230928415Speter */ 231028415Speter overflow -= 2; 231128415Speter } while (overflow > 0); 231228415Speter 231328415Speter /* Now recompute all bit lengths, scanning in increasing frequency. 231428415Speter * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 231528415Speter * lengths instead of fixing only the wrong ones. This idea is taken 231628415Speter * from 'ar' written by Haruhiko Okumura.) 231728415Speter */ 231828415Speter for (bits = max_length; bits != 0; bits--) { 231928415Speter n = s->bl_count[bits]; 232028415Speter while (n != 0) { 232128415Speter m = s->heap[--h]; 232228415Speter if (m > max_code) continue; 232328415Speter if (tree[m].Len != (unsigned) bits) { 232428415Speter Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); 232528415Speter s->opt_len += ((long)bits - (long)tree[m].Len) 232628415Speter *(long)tree[m].Freq; 232728415Speter tree[m].Len = (ush)bits; 232828415Speter } 232928415Speter n--; 233028415Speter } 233128415Speter } 233228415Speter} 233328415Speter 233428415Speter/* =========================================================================== 233528415Speter * Generate the codes for a given tree and bit counts (which need not be 233628415Speter * optimal). 233728415Speter * IN assertion: the array bl_count contains the bit length statistics for 233828415Speter * the given tree and the field len is set for all tree elements. 233928415Speter * OUT assertion: the field code is set for all tree elements of non 234028415Speter * zero code length. 234128415Speter */ 234228415Speterlocal void gen_codes (tree, max_code, bl_count) 234328415Speter ct_data *tree; /* the tree to decorate */ 234428415Speter int max_code; /* largest code with non zero frequency */ 234528415Speter ushf *bl_count; /* number of codes at each bit length */ 234628415Speter{ 234728415Speter ush next_code[MAX_BITS+1]; /* next code value for each bit length */ 234828415Speter ush code = 0; /* running code value */ 234928415Speter int bits; /* bit index */ 235028415Speter int n; /* code index */ 235128415Speter 235228415Speter /* The distribution counts are first used to generate the code values 235328415Speter * without bit reversal. 235428415Speter */ 235528415Speter for (bits = 1; bits <= MAX_BITS; bits++) { 235628415Speter next_code[bits] = code = (code + bl_count[bits-1]) << 1; 235728415Speter } 235828415Speter /* Check that the bit counts in bl_count are consistent. The last code 235928415Speter * must be all ones. 236028415Speter */ 236128415Speter Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 236228415Speter "inconsistent bit counts"); 236328415Speter Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); 236428415Speter 236528415Speter for (n = 0; n <= max_code; n++) { 236628415Speter int len = tree[n].Len; 236728415Speter if (len == 0) continue; 236828415Speter /* Now reverse the bits */ 236928415Speter tree[n].Code = bi_reverse(next_code[len]++, len); 237028415Speter 237134768Speter Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", 237228415Speter n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); 237328415Speter } 237428415Speter} 237528415Speter 237628415Speter/* =========================================================================== 237728415Speter * Construct one Huffman tree and assigns the code bit strings and lengths. 237828415Speter * Update the total bit length for the current block. 237928415Speter * IN assertion: the field freq is set for all tree elements. 238028415Speter * OUT assertions: the fields len and code are set to the optimal bit length 238128415Speter * and corresponding code. The length opt_len is updated; static_len is 238228415Speter * also updated if stree is not null. The field max_code is set. 238328415Speter */ 238428415Speterlocal void build_tree(s, desc) 238528415Speter deflate_state *s; 238628415Speter tree_desc *desc; /* the tree descriptor */ 238728415Speter{ 238828415Speter ct_data *tree = desc->dyn_tree; 238928415Speter ct_data *stree = desc->stat_desc->static_tree; 239028415Speter int elems = desc->stat_desc->elems; 239128415Speter int n, m; /* iterate over heap elements */ 239228415Speter int max_code = -1; /* largest code with non zero frequency */ 239328415Speter int node; /* new node being created */ 239428415Speter 239528415Speter /* Construct the initial heap, with least frequent element in 239628415Speter * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 239728415Speter * heap[0] is not used. 239828415Speter */ 239928415Speter s->heap_len = 0, s->heap_max = HEAP_SIZE; 240028415Speter 240128415Speter for (n = 0; n < elems; n++) { 240228415Speter if (tree[n].Freq != 0) { 240328415Speter s->heap[++(s->heap_len)] = max_code = n; 240428415Speter s->depth[n] = 0; 240528415Speter } else { 240628415Speter tree[n].Len = 0; 240728415Speter } 240828415Speter } 240928415Speter 241028415Speter /* The pkzip format requires that at least one distance code exists, 241128415Speter * and that at least one bit should be sent even if there is only one 241228415Speter * possible code. So to avoid special checks later on we force at least 241328415Speter * two codes of non zero frequency. 241428415Speter */ 241528415Speter while (s->heap_len < 2) { 241628415Speter node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); 241728415Speter tree[node].Freq = 1; 241828415Speter s->depth[node] = 0; 241928415Speter s->opt_len--; if (stree) s->static_len -= stree[node].Len; 242028415Speter /* node is 0 or 1 so it does not have extra bits */ 242128415Speter } 242228415Speter desc->max_code = max_code; 242328415Speter 242428415Speter /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 242528415Speter * establish sub-heaps of increasing lengths: 242628415Speter */ 242728415Speter for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); 242828415Speter 242928415Speter /* Construct the Huffman tree by repeatedly combining the least two 243028415Speter * frequent nodes. 243128415Speter */ 243228415Speter node = elems; /* next internal node of the tree */ 243328415Speter do { 243428415Speter pqremove(s, tree, n); /* n = node of least frequency */ 243528415Speter m = s->heap[SMALLEST]; /* m = node of next least frequency */ 243628415Speter 243728415Speter s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ 243828415Speter s->heap[--(s->heap_max)] = m; 243928415Speter 244028415Speter /* Create a new node father of n and m */ 244128415Speter tree[node].Freq = tree[n].Freq + tree[m].Freq; 244228415Speter s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1); 244328415Speter tree[n].Dad = tree[m].Dad = (ush)node; 244428415Speter#ifdef DUMP_BL_TREE 244528415Speter if (tree == s->bl_tree) { 244628415Speter fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)", 244728415Speter node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); 244828415Speter } 244928415Speter#endif 245028415Speter /* and insert the new node in the heap */ 245128415Speter s->heap[SMALLEST] = node++; 245228415Speter pqdownheap(s, tree, SMALLEST); 245328415Speter 245428415Speter } while (s->heap_len >= 2); 245528415Speter 245628415Speter s->heap[--(s->heap_max)] = s->heap[SMALLEST]; 245728415Speter 245828415Speter /* At this point, the fields freq and dad are set. We can now 245928415Speter * generate the bit lengths. 246028415Speter */ 246128415Speter gen_bitlen(s, (tree_desc *)desc); 246228415Speter 246328415Speter /* The field len is now set, we can generate the bit codes */ 246428415Speter gen_codes ((ct_data *)tree, max_code, s->bl_count); 246528415Speter} 246628415Speter 246728415Speter/* =========================================================================== 246828415Speter * Scan a literal or distance tree to determine the frequencies of the codes 246928415Speter * in the bit length tree. 247028415Speter */ 247128415Speterlocal void scan_tree (s, tree, max_code) 247228415Speter deflate_state *s; 247328415Speter ct_data *tree; /* the tree to be scanned */ 247428415Speter int max_code; /* and its largest code of non zero frequency */ 247528415Speter{ 247628415Speter int n; /* iterates over all tree elements */ 247728415Speter int prevlen = -1; /* last emitted length */ 247828415Speter int curlen; /* length of current code */ 247928415Speter int nextlen = tree[0].Len; /* length of next code */ 248028415Speter int count = 0; /* repeat count of the current code */ 248128415Speter int max_count = 7; /* max repeat count */ 248228415Speter int min_count = 4; /* min repeat count */ 248328415Speter 248428415Speter if (nextlen == 0) max_count = 138, min_count = 3; 248528415Speter tree[max_code+1].Len = (ush)0xffff; /* guard */ 248628415Speter 248728415Speter for (n = 0; n <= max_code; n++) { 248828415Speter curlen = nextlen; nextlen = tree[n+1].Len; 248928415Speter if (++count < max_count && curlen == nextlen) { 249028415Speter continue; 249128415Speter } else if (count < min_count) { 249228415Speter s->bl_tree[curlen].Freq += count; 249328415Speter } else if (curlen != 0) { 249428415Speter if (curlen != prevlen) s->bl_tree[curlen].Freq++; 249528415Speter s->bl_tree[REP_3_6].Freq++; 249628415Speter } else if (count <= 10) { 249728415Speter s->bl_tree[REPZ_3_10].Freq++; 249828415Speter } else { 249928415Speter s->bl_tree[REPZ_11_138].Freq++; 250028415Speter } 250128415Speter count = 0; prevlen = curlen; 250228415Speter if (nextlen == 0) { 250328415Speter max_count = 138, min_count = 3; 250428415Speter } else if (curlen == nextlen) { 250528415Speter max_count = 6, min_count = 3; 250628415Speter } else { 250728415Speter max_count = 7, min_count = 4; 250828415Speter } 250928415Speter } 251028415Speter} 251128415Speter 251228415Speter/* =========================================================================== 251328415Speter * Send a literal or distance tree in compressed form, using the codes in 251428415Speter * bl_tree. 251528415Speter */ 251628415Speterlocal void send_tree (s, tree, max_code) 251728415Speter deflate_state *s; 251828415Speter ct_data *tree; /* the tree to be scanned */ 251928415Speter int max_code; /* and its largest code of non zero frequency */ 252028415Speter{ 252128415Speter int n; /* iterates over all tree elements */ 252228415Speter int prevlen = -1; /* last emitted length */ 252328415Speter int curlen; /* length of current code */ 252428415Speter int nextlen = tree[0].Len; /* length of next code */ 252528415Speter int count = 0; /* repeat count of the current code */ 252628415Speter int max_count = 7; /* max repeat count */ 252728415Speter int min_count = 4; /* min repeat count */ 252828415Speter 252928415Speter /* tree[max_code+1].Len = -1; */ /* guard already set */ 253028415Speter if (nextlen == 0) max_count = 138, min_count = 3; 253128415Speter 253228415Speter for (n = 0; n <= max_code; n++) { 253328415Speter curlen = nextlen; nextlen = tree[n+1].Len; 253428415Speter if (++count < max_count && curlen == nextlen) { 253528415Speter continue; 253628415Speter } else if (count < min_count) { 253728415Speter do { send_code(s, curlen, s->bl_tree); } while (--count != 0); 253828415Speter 253928415Speter } else if (curlen != 0) { 254028415Speter if (curlen != prevlen) { 254128415Speter send_code(s, curlen, s->bl_tree); count--; 254228415Speter } 254328415Speter Assert(count >= 3 && count <= 6, " 3_6?"); 254428415Speter send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); 254528415Speter 254628415Speter } else if (count <= 10) { 254728415Speter send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); 254828415Speter 254928415Speter } else { 255028415Speter send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); 255128415Speter } 255228415Speter count = 0; prevlen = curlen; 255328415Speter if (nextlen == 0) { 255428415Speter max_count = 138, min_count = 3; 255528415Speter } else if (curlen == nextlen) { 255628415Speter max_count = 6, min_count = 3; 255728415Speter } else { 255828415Speter max_count = 7, min_count = 4; 255928415Speter } 256028415Speter } 256128415Speter} 256228415Speter 256328415Speter/* =========================================================================== 256428415Speter * Construct the Huffman tree for the bit lengths and return the index in 256528415Speter * bl_order of the last bit length code to send. 256628415Speter */ 256728415Speterlocal int build_bl_tree(s) 256828415Speter deflate_state *s; 256928415Speter{ 257028415Speter int max_blindex; /* index of last bit length code of non zero freq */ 257128415Speter 257228415Speter /* Determine the bit length frequencies for literal and distance trees */ 257328415Speter scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); 257428415Speter scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); 257528415Speter 257628415Speter /* Build the bit length tree: */ 257728415Speter build_tree(s, (tree_desc *)(&(s->bl_desc))); 257828415Speter /* opt_len now includes the length of the tree representations, except 257928415Speter * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 258028415Speter */ 258128415Speter 258228415Speter /* Determine the number of bit length codes to send. The pkzip format 258328415Speter * requires that at least 4 bit length codes be sent. (appnote.txt says 258428415Speter * 3 but the actual value used is 4.) 258528415Speter */ 258628415Speter for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 258728415Speter if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; 258828415Speter } 258928415Speter /* Update opt_len to include the bit length tree and counts */ 259028415Speter s->opt_len += 3*(max_blindex+1) + 5+5+4; 259128415Speter Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", 259228415Speter s->opt_len, s->static_len)); 259328415Speter 259428415Speter return max_blindex; 259528415Speter} 259628415Speter 259728415Speter/* =========================================================================== 259828415Speter * Send the header for a block using dynamic Huffman trees: the counts, the 259928415Speter * lengths of the bit length codes, the literal tree and the distance tree. 260028415Speter * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 260128415Speter */ 260228415Speterlocal void send_all_trees(s, lcodes, dcodes, blcodes) 260328415Speter deflate_state *s; 260428415Speter int lcodes, dcodes, blcodes; /* number of codes for each tree */ 260528415Speter{ 260628415Speter int rank; /* index in bl_order */ 260728415Speter 260828415Speter Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); 260928415Speter Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 261028415Speter "too many codes"); 261128415Speter Tracev((stderr, "\nbl counts: ")); 261228415Speter send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ 261328415Speter send_bits(s, dcodes-1, 5); 261428415Speter send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ 261528415Speter for (rank = 0; rank < blcodes; rank++) { 261628415Speter Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 261728415Speter send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); 261828415Speter } 261928415Speter Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); 262028415Speter 262128415Speter send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ 262228415Speter Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); 262328415Speter 262428415Speter send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ 262528415Speter Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); 262628415Speter} 262728415Speter 262828415Speter/* =========================================================================== 262928415Speter * Send a stored block 263028415Speter */ 263134768Spetervoid _tr_stored_block(s, buf, stored_len, eof) 263228415Speter deflate_state *s; 263328415Speter charf *buf; /* input block */ 263428415Speter ulg stored_len; /* length of input block */ 263528415Speter int eof; /* true if this is the last block for a file */ 263628415Speter{ 263728415Speter send_bits(s, (STORED_BLOCK<<1)+eof, 3); /* send block type */ 263834768Speter s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; 263928415Speter s->compressed_len += (stored_len + 4) << 3; 264028415Speter 264128415Speter copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ 264228415Speter} 264328415Speter 264428415Speter/* Send just the `stored block' type code without any length bytes or data. 264528415Speter */ 264634768Spetervoid _tr_stored_type_only(s) 264728415Speter deflate_state *s; 264828415Speter{ 264928415Speter send_bits(s, (STORED_BLOCK << 1), 3); 265028415Speter bi_windup(s); 265128415Speter s->compressed_len = (s->compressed_len + 3) & ~7L; 265228415Speter} 265328415Speter 265428415Speter 265528415Speter/* =========================================================================== 265628415Speter * Send one empty static block to give enough lookahead for inflate. 265728415Speter * This takes 10 bits, of which 7 may remain in the bit buffer. 265834768Speter * The current inflate code requires 9 bits of lookahead. If the 265934768Speter * last two codes for the previous block (real code plus EOB) were coded 266034768Speter * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode 266134768Speter * the last real code. In this case we send two empty static blocks instead 266234768Speter * of one. (There are no problems if the previous block is stored or fixed.) 266334768Speter * To simplify the code, we assume the worst case of last real code encoded 266434768Speter * on one bit only. 266528415Speter */ 266634768Spetervoid _tr_align(s) 266728415Speter deflate_state *s; 266828415Speter{ 266928415Speter send_bits(s, STATIC_TREES<<1, 3); 267028415Speter send_code(s, END_BLOCK, static_ltree); 267128415Speter s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ 267228415Speter bi_flush(s); 267328415Speter /* Of the 10 bits for the empty block, we have already sent 267434768Speter * (10 - bi_valid) bits. The lookahead for the last real code (before 267534768Speter * the EOB of the previous block) was thus at least one plus the length 267634768Speter * of the EOB plus what we have just sent of the empty static block. 267728415Speter */ 267834768Speter if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { 267928415Speter send_bits(s, STATIC_TREES<<1, 3); 268028415Speter send_code(s, END_BLOCK, static_ltree); 268128415Speter s->compressed_len += 10L; 268228415Speter bi_flush(s); 268328415Speter } 268428415Speter s->last_eob_len = 7; 268528415Speter} 268628415Speter 268728415Speter/* =========================================================================== 268828415Speter * Determine the best encoding for the current block: dynamic trees, static 268928415Speter * trees or store, and output the encoded block to the zip file. This function 269028415Speter * returns the total compressed length for the file so far. 269128415Speter */ 269234768Speterulg _tr_flush_block(s, buf, stored_len, eof) 269328415Speter deflate_state *s; 269428415Speter charf *buf; /* input block, or NULL if too old */ 269528415Speter ulg stored_len; /* length of input block */ 269634768Speter int eof; /* true if this is the last block for a file */ 269728415Speter{ 269828415Speter ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */ 269934768Speter int max_blindex = 0; /* index of last bit length code of non zero freq */ 270028415Speter 270134768Speter /* Build the Huffman trees unless a stored block is forced */ 270234768Speter if (s->level > 0) { 270328415Speter 270434768Speter /* Check if the file is ascii or binary */ 270534768Speter if (s->data_type == Z_UNKNOWN) set_data_type(s); 270628415Speter 270734768Speter /* Construct the literal and distance trees */ 270834768Speter build_tree(s, (tree_desc *)(&(s->l_desc))); 270934768Speter Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, 271034768Speter s->static_len)); 271128415Speter 271234768Speter build_tree(s, (tree_desc *)(&(s->d_desc))); 271334768Speter Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, 271434768Speter s->static_len)); 271534768Speter /* At this point, opt_len and static_len are the total bit lengths of 271634768Speter * the compressed block data, excluding the tree representations. 271734768Speter */ 271828415Speter 271934768Speter /* Build the bit length tree for the above two trees, and get the index 272034768Speter * in bl_order of the last bit length code to send. 272134768Speter */ 272234768Speter max_blindex = build_bl_tree(s); 272328415Speter 272434768Speter /* Determine the best encoding. Compute first the block length in bytes*/ 272534768Speter opt_lenb = (s->opt_len+3+7)>>3; 272634768Speter static_lenb = (s->static_len+3+7)>>3; 272728415Speter 272834768Speter Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ", 272934768Speter opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len, 273034768Speter s->last_lit)); 273128415Speter 273234768Speter if (static_lenb <= opt_lenb) opt_lenb = static_lenb; 273328415Speter 273434768Speter } else { 273534768Speter Assert(buf != (char*)0, "lost buf"); 273634768Speter opt_lenb = static_lenb = stored_len + 5; /* force a stored block */ 273734768Speter } 273834768Speter 273928415Speter /* If compression failed and this is the first and last block, 274028415Speter * and if the .zip file can be seeked (to rewrite the local header), 274128415Speter * the whole file is transformed into a stored file: 274228415Speter */ 274328415Speter#ifdef STORED_FILE_OK 274428415Speter# ifdef FORCE_STORED_FILE 274534768Speter if (eof && s->compressed_len == 0L) { /* force stored file */ 274628415Speter# else 274734768Speter if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) { 274828415Speter# endif 274928415Speter /* Since LIT_BUFSIZE <= 2*WSIZE, the input data must be there: */ 275028415Speter if (buf == (charf*)0) error ("block vanished"); 275128415Speter 275234768Speter copy_block(s, buf, (unsigned)stored_len, 0); /* without header */ 275328415Speter s->compressed_len = stored_len << 3; 275428415Speter s->method = STORED; 275528415Speter } else 275628415Speter#endif /* STORED_FILE_OK */ 275728415Speter 275828415Speter#ifdef FORCE_STORED 275934768Speter if (buf != (char*)0) { /* force stored block */ 276028415Speter#else 276134768Speter if (stored_len+4 <= opt_lenb && buf != (char*)0) { 276228415Speter /* 4: two words for the lengths */ 276328415Speter#endif 276428415Speter /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 276528415Speter * Otherwise we can't have processed more than WSIZE input bytes since 276628415Speter * the last block flush, because compression would have been 276728415Speter * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 276828415Speter * transform a block into a stored block. 276928415Speter */ 277034768Speter _tr_stored_block(s, buf, stored_len, eof); 277128415Speter 277228415Speter#ifdef FORCE_STATIC 277334768Speter } else if (static_lenb >= 0) { /* force static trees */ 277428415Speter#else 277534768Speter } else if (static_lenb == opt_lenb) { 277628415Speter#endif 277728415Speter send_bits(s, (STATIC_TREES<<1)+eof, 3); 277828415Speter compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree); 277928415Speter s->compressed_len += 3 + s->static_len; 278028415Speter } else { 278128415Speter send_bits(s, (DYN_TREES<<1)+eof, 3); 278228415Speter send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, 278328415Speter max_blindex+1); 278428415Speter compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); 278528415Speter s->compressed_len += 3 + s->opt_len; 278628415Speter } 278728415Speter Assert (s->compressed_len == s->bits_sent, "bad compressed size"); 278828415Speter init_block(s); 278928415Speter 279028415Speter if (eof) { 279128415Speter bi_windup(s); 279228415Speter s->compressed_len += 7; /* align on byte boundary */ 279328415Speter } 279428415Speter Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3, 279528415Speter s->compressed_len-7*eof)); 279628415Speter 279728415Speter return s->compressed_len >> 3; 279828415Speter} 279928415Speter 280028415Speter/* =========================================================================== 280128415Speter * Save the match info and tally the frequency counts. Return true if 280228415Speter * the current block must be flushed. 280328415Speter */ 280434768Speterint _tr_tally (s, dist, lc) 280528415Speter deflate_state *s; 280634768Speter unsigned dist; /* distance of matched string */ 280734768Speter unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */ 280828415Speter{ 280928415Speter s->d_buf[s->last_lit] = (ush)dist; 281028415Speter s->l_buf[s->last_lit++] = (uch)lc; 281128415Speter if (dist == 0) { 281228415Speter /* lc is the unmatched char */ 281328415Speter s->dyn_ltree[lc].Freq++; 281428415Speter } else { 281528415Speter s->matches++; 281628415Speter /* Here, lc is the match length - MIN_MATCH */ 281728415Speter dist--; /* dist = match distance - 1 */ 281828415Speter Assert((ush)dist < (ush)MAX_DIST(s) && 281928415Speter (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 282034768Speter (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match"); 282128415Speter 282228415Speter s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++; 282328415Speter s->dyn_dtree[d_code(dist)].Freq++; 282428415Speter } 282528415Speter 282628415Speter /* Try to guess if it is profitable to stop the current block here */ 282728415Speter if (s->level > 2 && (s->last_lit & 0xfff) == 0) { 282828415Speter /* Compute an upper bound for the compressed length */ 282928415Speter ulg out_length = (ulg)s->last_lit*8L; 283034768Speter ulg in_length = (ulg)((long)s->strstart - s->block_start); 283128415Speter int dcode; 283228415Speter for (dcode = 0; dcode < D_CODES; dcode++) { 283328415Speter out_length += (ulg)s->dyn_dtree[dcode].Freq * 283428415Speter (5L+extra_dbits[dcode]); 283528415Speter } 283628415Speter out_length >>= 3; 283728415Speter Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", 283828415Speter s->last_lit, in_length, out_length, 283928415Speter 100L - out_length*100L/in_length)); 284028415Speter if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1; 284128415Speter } 284228415Speter return (s->last_lit == s->lit_bufsize-1); 284328415Speter /* We avoid equality with lit_bufsize because of wraparound at 64K 284428415Speter * on 16 bit machines and because stored blocks are restricted to 284528415Speter * 64K-1 bytes. 284628415Speter */ 284728415Speter} 284828415Speter 284928415Speter/* =========================================================================== 285028415Speter * Send the block data compressed using the given Huffman trees 285128415Speter */ 285228415Speterlocal void compress_block(s, ltree, dtree) 285328415Speter deflate_state *s; 285428415Speter ct_data *ltree; /* literal tree */ 285528415Speter ct_data *dtree; /* distance tree */ 285628415Speter{ 285728415Speter unsigned dist; /* distance of matched string */ 285828415Speter int lc; /* match length or unmatched char (if dist == 0) */ 285928415Speter unsigned lx = 0; /* running index in l_buf */ 286028415Speter unsigned code; /* the code to send */ 286128415Speter int extra; /* number of extra bits to send */ 286228415Speter 286328415Speter if (s->last_lit != 0) do { 286428415Speter dist = s->d_buf[lx]; 286528415Speter lc = s->l_buf[lx++]; 286628415Speter if (dist == 0) { 286728415Speter send_code(s, lc, ltree); /* send a literal byte */ 286828415Speter Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 286928415Speter } else { 287028415Speter /* Here, lc is the match length - MIN_MATCH */ 287128415Speter code = length_code[lc]; 287228415Speter send_code(s, code+LITERALS+1, ltree); /* send the length code */ 287328415Speter extra = extra_lbits[code]; 287428415Speter if (extra != 0) { 287528415Speter lc -= base_length[code]; 287628415Speter send_bits(s, lc, extra); /* send the extra length bits */ 287728415Speter } 287828415Speter dist--; /* dist is now the match distance - 1 */ 287928415Speter code = d_code(dist); 288028415Speter Assert (code < D_CODES, "bad d_code"); 288128415Speter 288228415Speter send_code(s, code, dtree); /* send the distance code */ 288328415Speter extra = extra_dbits[code]; 288428415Speter if (extra != 0) { 288528415Speter dist -= base_dist[code]; 288628415Speter send_bits(s, dist, extra); /* send the extra distance bits */ 288728415Speter } 288828415Speter } /* literal or match pair ? */ 288928415Speter 289028415Speter /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ 289128415Speter Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow"); 289228415Speter 289328415Speter } while (lx < s->last_lit); 289428415Speter 289528415Speter send_code(s, END_BLOCK, ltree); 289628415Speter s->last_eob_len = ltree[END_BLOCK].Len; 289728415Speter} 289828415Speter 289928415Speter/* =========================================================================== 290034768Speter * Set the data type to ASCII or BINARY, using a crude approximation: 290128415Speter * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. 290228415Speter * IN assertion: the fields freq of dyn_ltree are set and the total of all 290328415Speter * frequencies does not exceed 64K (to fit in an int on 16 bit machines). 290428415Speter */ 290528415Speterlocal void set_data_type(s) 290628415Speter deflate_state *s; 290728415Speter{ 290828415Speter int n = 0; 290928415Speter unsigned ascii_freq = 0; 291028415Speter unsigned bin_freq = 0; 291128415Speter while (n < 7) bin_freq += s->dyn_ltree[n++].Freq; 291228415Speter while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq; 291328415Speter while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq; 291434768Speter s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII); 291528415Speter} 291628415Speter 291728415Speter/* =========================================================================== 291828415Speter * Reverse the first len bits of a code, using straightforward code (a faster 291928415Speter * method would use a table) 292028415Speter * IN assertion: 1 <= len <= 15 292128415Speter */ 292228415Speterlocal unsigned bi_reverse(code, len) 292328415Speter unsigned code; /* the value to invert */ 292428415Speter int len; /* its bit length */ 292528415Speter{ 2926331643Sdim unsigned res = 0; 292728415Speter do { 292828415Speter res |= code & 1; 292928415Speter code >>= 1, res <<= 1; 293028415Speter } while (--len > 0); 293128415Speter return res >> 1; 293228415Speter} 293328415Speter 293428415Speter/* =========================================================================== 293528415Speter * Flush the bit buffer, keeping at most 7 bits in it. 293628415Speter */ 293728415Speterlocal void bi_flush(s) 293828415Speter deflate_state *s; 293928415Speter{ 294028415Speter if (s->bi_valid == 16) { 294128415Speter put_short(s, s->bi_buf); 294228415Speter s->bi_buf = 0; 294328415Speter s->bi_valid = 0; 294428415Speter } else if (s->bi_valid >= 8) { 294528415Speter put_byte(s, (Byte)s->bi_buf); 294628415Speter s->bi_buf >>= 8; 294728415Speter s->bi_valid -= 8; 294828415Speter } 294928415Speter} 295028415Speter 295128415Speter/* =========================================================================== 295228415Speter * Flush the bit buffer and align the output on a byte boundary 295328415Speter */ 295428415Speterlocal void bi_windup(s) 295528415Speter deflate_state *s; 295628415Speter{ 295728415Speter if (s->bi_valid > 8) { 295828415Speter put_short(s, s->bi_buf); 295928415Speter } else if (s->bi_valid > 0) { 296028415Speter put_byte(s, (Byte)s->bi_buf); 296128415Speter } 296228415Speter s->bi_buf = 0; 296328415Speter s->bi_valid = 0; 296428415Speter#ifdef DEBUG_ZLIB 296528415Speter s->bits_sent = (s->bits_sent+7) & ~7; 296628415Speter#endif 296728415Speter} 296828415Speter 296928415Speter/* =========================================================================== 297028415Speter * Copy a stored block, storing first the length and its 297128415Speter * one's complement if requested. 297228415Speter */ 297328415Speterlocal void copy_block(s, buf, len, header) 297428415Speter deflate_state *s; 297528415Speter charf *buf; /* the input data */ 297628415Speter unsigned len; /* its length */ 297728415Speter int header; /* true if block header must be written */ 297828415Speter{ 297928415Speter bi_windup(s); /* align on byte boundary */ 298028415Speter s->last_eob_len = 8; /* enough lookahead for inflate */ 298128415Speter 298228415Speter if (header) { 298328415Speter put_short(s, (ush)len); 298428415Speter put_short(s, (ush)~len); 298528415Speter#ifdef DEBUG_ZLIB 298628415Speter s->bits_sent += 2*16; 298728415Speter#endif 298828415Speter } 298928415Speter#ifdef DEBUG_ZLIB 299028415Speter s->bits_sent += (ulg)len<<3; 299128415Speter#endif 299234768Speter /* bundle up the put_byte(s, *buf++) calls */ 299334768Speter zmemcpy(&s->pending_buf[s->pending], buf, len); 299434768Speter s->pending += len; 299528415Speter} 299634768Speter/* --- trees.c */ 299728415Speter 299834768Speter/* +++ inflate.c */ 299934768Speter/* inflate.c -- zlib interface to inflate modules 300034768Speter * Copyright (C) 1995-1996 Mark Adler 300134768Speter * For conditions of distribution and use, see copyright notice in zlib.h 300234768Speter */ 300328415Speter 300434768Speter/* #include "zutil.h" */ 300534768Speter 300634768Speter/* +++ infblock.h */ 300728415Speter/* infblock.h -- header to use infblock.c 300834768Speter * Copyright (C) 1995-1996 Mark Adler 300928415Speter * For conditions of distribution and use, see copyright notice in zlib.h 301028415Speter */ 301128415Speter 301228415Speter/* WARNING: this file should *not* be used by applications. It is 301328415Speter part of the implementation of the compression library and is 301428415Speter subject to change. Applications should only use zlib.h. 301528415Speter */ 301628415Speter 301728415Speterstruct inflate_blocks_state; 301828415Spetertypedef struct inflate_blocks_state FAR inflate_blocks_statef; 301928415Speter 302034768Speterextern inflate_blocks_statef * inflate_blocks_new OF(( 302134768Speter z_streamp z, 302228415Speter check_func c, /* check function */ 302328415Speter uInt w)); /* window size */ 302428415Speter 302534768Speterextern int inflate_blocks OF(( 302628415Speter inflate_blocks_statef *, 302734768Speter z_streamp , 302828415Speter int)); /* initial return code */ 302928415Speter 303034768Speterextern void inflate_blocks_reset OF(( 303128415Speter inflate_blocks_statef *, 303234768Speter z_streamp , 303328415Speter uLongf *)); /* check value on output */ 303428415Speter 303534768Speterextern int inflate_blocks_free OF(( 303628415Speter inflate_blocks_statef *, 303734768Speter z_streamp , 303828415Speter uLongf *)); /* check value on output */ 303928415Speter 304034768Speterextern void inflate_set_dictionary OF(( 304134768Speter inflate_blocks_statef *s, 304234768Speter const Bytef *d, /* dictionary */ 304334768Speter uInt n)); /* dictionary length */ 304434768Speter 304534768Speterextern int inflate_addhistory OF(( 304628415Speter inflate_blocks_statef *, 304734768Speter z_streamp)); 304828415Speter 304934768Speterextern int inflate_packet_flush OF(( 305028415Speter inflate_blocks_statef *)); 305134768Speter/* --- infblock.h */ 305228415Speter 305334768Speter#ifndef NO_DUMMY_DECL 305434768Speterstruct inflate_blocks_state {int dummy;}; /* for buggy compilers */ 305528415Speter#endif 305628415Speter 305728415Speter/* inflate private state */ 305828415Speterstruct internal_state { 305928415Speter 306028415Speter /* mode */ 306128415Speter enum { 306228415Speter METHOD, /* waiting for method byte */ 306328415Speter FLAG, /* waiting for flag byte */ 306434768Speter DICT4, /* four dictionary check bytes to go */ 306534768Speter DICT3, /* three dictionary check bytes to go */ 306634768Speter DICT2, /* two dictionary check bytes to go */ 306734768Speter DICT1, /* one dictionary check byte to go */ 306834768Speter DICT0, /* waiting for inflateSetDictionary */ 306928415Speter BLOCKS, /* decompressing blocks */ 307028415Speter CHECK4, /* four check bytes to go */ 307128415Speter CHECK3, /* three check bytes to go */ 307228415Speter CHECK2, /* two check bytes to go */ 307328415Speter CHECK1, /* one check byte to go */ 307428415Speter DONE, /* finished check, done */ 307528415Speter BAD} /* got an error--stay here */ 307628415Speter mode; /* current inflate mode */ 307728415Speter 307828415Speter /* mode dependent information */ 307928415Speter union { 308028415Speter uInt method; /* if FLAGS, method byte */ 308128415Speter struct { 308228415Speter uLong was; /* computed check value */ 308328415Speter uLong need; /* stream check value */ 308428415Speter } check; /* if CHECK, check values to compare */ 308528415Speter uInt marker; /* if BAD, inflateSync's marker bytes count */ 308628415Speter } sub; /* submode */ 308728415Speter 308828415Speter /* mode independent information */ 308928415Speter int nowrap; /* flag for no wrapper */ 309028415Speter uInt wbits; /* log2(window size) (8..15, defaults to 15) */ 309128415Speter inflate_blocks_statef 309228415Speter *blocks; /* current inflate_blocks state */ 309328415Speter 309428415Speter}; 309528415Speter 309628415Speter 309728415Speterint inflateReset(z) 309834768Speterz_streamp z; 309928415Speter{ 310028415Speter uLong c; 310128415Speter 310228415Speter if (z == Z_NULL || z->state == Z_NULL) 310328415Speter return Z_STREAM_ERROR; 310428415Speter z->total_in = z->total_out = 0; 310528415Speter z->msg = Z_NULL; 310628415Speter z->state->mode = z->state->nowrap ? BLOCKS : METHOD; 310728415Speter inflate_blocks_reset(z->state->blocks, z, &c); 310828415Speter Trace((stderr, "inflate: reset\n")); 310928415Speter return Z_OK; 311028415Speter} 311128415Speter 311228415Speter 311328415Speterint inflateEnd(z) 311434768Speterz_streamp z; 311528415Speter{ 311628415Speter uLong c; 311728415Speter 311828415Speter if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL) 311928415Speter return Z_STREAM_ERROR; 312028415Speter if (z->state->blocks != Z_NULL) 312128415Speter inflate_blocks_free(z->state->blocks, z, &c); 312234768Speter ZFREE(z, z->state); 312328415Speter z->state = Z_NULL; 312428415Speter Trace((stderr, "inflate: end\n")); 312528415Speter return Z_OK; 312628415Speter} 312728415Speter 312828415Speter 312934768Speterint inflateInit2_(z, w, version, stream_size) 313034768Speterz_streamp z; 313128415Speterint w; 313234768Speterconst char *version; 313334768Speterint stream_size; 313428415Speter{ 313534768Speter if (version == Z_NULL || version[0] != ZLIB_VERSION[0] || 313634768Speter stream_size != sizeof(z_stream)) 313734768Speter return Z_VERSION_ERROR; 313834768Speter 313928415Speter /* initialize state */ 314028415Speter if (z == Z_NULL) 314128415Speter return Z_STREAM_ERROR; 314234768Speter z->msg = Z_NULL; 314334768Speter#ifndef NO_ZCFUNCS 314434768Speter if (z->zalloc == Z_NULL) 314534768Speter { 314634768Speter z->zalloc = zcalloc; 314734768Speter z->opaque = (voidpf)0; 314834768Speter } 314934768Speter if (z->zfree == Z_NULL) z->zfree = zcfree; 315034768Speter#endif 315128415Speter if ((z->state = (struct internal_state FAR *) 315234768Speter ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL) 315328415Speter return Z_MEM_ERROR; 315428415Speter z->state->blocks = Z_NULL; 315528415Speter 315628415Speter /* handle undocumented nowrap option (no zlib header or check) */ 315728415Speter z->state->nowrap = 0; 315828415Speter if (w < 0) 315928415Speter { 316028415Speter w = - w; 316128415Speter z->state->nowrap = 1; 316228415Speter } 316328415Speter 316428415Speter /* set window size */ 316528415Speter if (w < 8 || w > 15) 316628415Speter { 316728415Speter inflateEnd(z); 316828415Speter return Z_STREAM_ERROR; 316928415Speter } 317028415Speter z->state->wbits = (uInt)w; 317128415Speter 317228415Speter /* create inflate_blocks state */ 317328415Speter if ((z->state->blocks = 317434768Speter inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, (uInt)1 << w)) 317528415Speter == Z_NULL) 317628415Speter { 317728415Speter inflateEnd(z); 317828415Speter return Z_MEM_ERROR; 317928415Speter } 318028415Speter Trace((stderr, "inflate: allocated\n")); 318128415Speter 318228415Speter /* reset state */ 318328415Speter inflateReset(z); 318428415Speter return Z_OK; 318528415Speter} 318628415Speter 318728415Speter 318834768Speterint inflateInit_(z, version, stream_size) 318934768Speterz_streamp z; 319034768Speterconst char *version; 319134768Speterint stream_size; 319228415Speter{ 319334768Speter return inflateInit2_(z, DEF_WBITS, version, stream_size); 319428415Speter} 319528415Speter 319628415Speter 319728415Speter#define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;} 319828415Speter#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++) 319928415Speter 320028415Speterint inflate(z, f) 320134768Speterz_streamp z; 320228415Speterint f; 320328415Speter{ 320428415Speter int r; 320528415Speter uInt b; 320628415Speter 320734768Speter if (z == Z_NULL || z->state == Z_NULL || z->next_in == Z_NULL || f < 0) 320828415Speter return Z_STREAM_ERROR; 320928415Speter r = Z_BUF_ERROR; 321028415Speter while (1) switch (z->state->mode) 321128415Speter { 321228415Speter case METHOD: 321328415Speter NEEDBYTE 321434768Speter if (((z->state->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED) 321528415Speter { 321628415Speter z->state->mode = BAD; 321734768Speter z->msg = (char*)"unknown compression method"; 321828415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 321928415Speter break; 322028415Speter } 322128415Speter if ((z->state->sub.method >> 4) + 8 > z->state->wbits) 322228415Speter { 322328415Speter z->state->mode = BAD; 322434768Speter z->msg = (char*)"invalid window size"; 322528415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 322628415Speter break; 322728415Speter } 322828415Speter z->state->mode = FLAG; 322928415Speter case FLAG: 323028415Speter NEEDBYTE 323134768Speter b = NEXTBYTE; 323234768Speter if (((z->state->sub.method << 8) + b) % 31) 323328415Speter { 323428415Speter z->state->mode = BAD; 323534768Speter z->msg = (char*)"incorrect header check"; 323628415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 323728415Speter break; 323828415Speter } 323934768Speter Trace((stderr, "inflate: zlib header ok\n")); 324034768Speter if (!(b & PRESET_DICT)) 324128415Speter { 324234768Speter z->state->mode = BLOCKS; 324334768Speter break; 324428415Speter } 324534768Speter z->state->mode = DICT4; 324634768Speter case DICT4: 324734768Speter NEEDBYTE 324834768Speter z->state->sub.check.need = (uLong)NEXTBYTE << 24; 324934768Speter z->state->mode = DICT3; 325034768Speter case DICT3: 325134768Speter NEEDBYTE 325234768Speter z->state->sub.check.need += (uLong)NEXTBYTE << 16; 325334768Speter z->state->mode = DICT2; 325434768Speter case DICT2: 325534768Speter NEEDBYTE 325634768Speter z->state->sub.check.need += (uLong)NEXTBYTE << 8; 325734768Speter z->state->mode = DICT1; 325834768Speter case DICT1: 325934768Speter NEEDBYTE 326034768Speter z->state->sub.check.need += (uLong)NEXTBYTE; 326134768Speter z->adler = z->state->sub.check.need; 326234768Speter z->state->mode = DICT0; 326334768Speter return Z_NEED_DICT; 326434768Speter case DICT0: 326534768Speter z->state->mode = BAD; 326634768Speter z->msg = (char*)"need dictionary"; 326734768Speter z->state->sub.marker = 0; /* can try inflateSync */ 326834768Speter return Z_STREAM_ERROR; 326928415Speter case BLOCKS: 327028415Speter r = inflate_blocks(z->state->blocks, z, r); 327128415Speter if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0) 327228415Speter r = inflate_packet_flush(z->state->blocks); 327328415Speter if (r == Z_DATA_ERROR) 327428415Speter { 327528415Speter z->state->mode = BAD; 327628415Speter z->state->sub.marker = 0; /* can try inflateSync */ 327728415Speter break; 327828415Speter } 327928415Speter if (r != Z_STREAM_END) 328028415Speter return r; 328128415Speter r = Z_OK; 328228415Speter inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was); 328328415Speter if (z->state->nowrap) 328428415Speter { 328528415Speter z->state->mode = DONE; 328628415Speter break; 328728415Speter } 328828415Speter z->state->mode = CHECK4; 328928415Speter case CHECK4: 329028415Speter NEEDBYTE 329128415Speter z->state->sub.check.need = (uLong)NEXTBYTE << 24; 329228415Speter z->state->mode = CHECK3; 329328415Speter case CHECK3: 329428415Speter NEEDBYTE 329528415Speter z->state->sub.check.need += (uLong)NEXTBYTE << 16; 329628415Speter z->state->mode = CHECK2; 329728415Speter case CHECK2: 329828415Speter NEEDBYTE 329928415Speter z->state->sub.check.need += (uLong)NEXTBYTE << 8; 330028415Speter z->state->mode = CHECK1; 330128415Speter case CHECK1: 330228415Speter NEEDBYTE 330328415Speter z->state->sub.check.need += (uLong)NEXTBYTE; 330428415Speter 330528415Speter if (z->state->sub.check.was != z->state->sub.check.need) 330628415Speter { 330728415Speter z->state->mode = BAD; 330834768Speter z->msg = (char*)"incorrect data check"; 330928415Speter z->state->sub.marker = 5; /* can't try inflateSync */ 331028415Speter break; 331128415Speter } 331228415Speter Trace((stderr, "inflate: zlib check ok\n")); 331328415Speter z->state->mode = DONE; 331428415Speter case DONE: 331528415Speter return Z_STREAM_END; 331628415Speter case BAD: 331728415Speter return Z_DATA_ERROR; 331828415Speter default: 331928415Speter return Z_STREAM_ERROR; 332028415Speter } 332128415Speter 332228415Speter empty: 332328415Speter if (f != Z_PACKET_FLUSH) 332428415Speter return r; 332528415Speter z->state->mode = BAD; 332634768Speter z->msg = (char *)"need more for packet flush"; 332728415Speter z->state->sub.marker = 0; /* can try inflateSync */ 332828415Speter return Z_DATA_ERROR; 332928415Speter} 333028415Speter 333134768Speter 333234768Speterint inflateSetDictionary(z, dictionary, dictLength) 333334768Speterz_streamp z; 333434768Speterconst Bytef *dictionary; 333534768SpeteruInt dictLength; 333634768Speter{ 333734768Speter uInt length = dictLength; 333834768Speter 333934768Speter if (z == Z_NULL || z->state == Z_NULL || z->state->mode != DICT0) 334034768Speter return Z_STREAM_ERROR; 334134768Speter 334234768Speter if (adler32(1L, dictionary, dictLength) != z->adler) return Z_DATA_ERROR; 334334768Speter z->adler = 1L; 334434768Speter 334534768Speter if (length >= ((uInt)1<<z->state->wbits)) 334634768Speter { 334734768Speter length = (1<<z->state->wbits)-1; 334834768Speter dictionary += dictLength - length; 334934768Speter } 335034768Speter inflate_set_dictionary(z->state->blocks, dictionary, length); 335134768Speter z->state->mode = BLOCKS; 335234768Speter return Z_OK; 335334768Speter} 335434768Speter 335528415Speter/* 335628415Speter * This subroutine adds the data at next_in/avail_in to the output history 335728415Speter * without performing any output. The output buffer must be "caught up"; 335828415Speter * i.e. no pending output (hence s->read equals s->write), and the state must 335928415Speter * be BLOCKS (i.e. we should be willing to see the start of a series of 336028415Speter * BLOCKS). On exit, the output will also be caught up, and the checksum 336128415Speter * will have been updated if need be. 336228415Speter */ 336328415Speter 336428415Speterint inflateIncomp(z) 336528415Speterz_stream *z; 336628415Speter{ 336728415Speter if (z->state->mode != BLOCKS) 336828415Speter return Z_DATA_ERROR; 336928415Speter return inflate_addhistory(z->state->blocks, z); 337028415Speter} 337128415Speter 337228415Speter 337328415Speterint inflateSync(z) 337434768Speterz_streamp z; 337528415Speter{ 337628415Speter uInt n; /* number of bytes to look at */ 337728415Speter Bytef *p; /* pointer to bytes */ 337828415Speter uInt m; /* number of marker bytes found in a row */ 337928415Speter uLong r, w; /* temporaries to save total_in and total_out */ 338028415Speter 338128415Speter /* set up */ 338228415Speter if (z == Z_NULL || z->state == Z_NULL) 338328415Speter return Z_STREAM_ERROR; 338428415Speter if (z->state->mode != BAD) 338528415Speter { 338628415Speter z->state->mode = BAD; 338728415Speter z->state->sub.marker = 0; 338828415Speter } 338928415Speter if ((n = z->avail_in) == 0) 339028415Speter return Z_BUF_ERROR; 339128415Speter p = z->next_in; 339228415Speter m = z->state->sub.marker; 339328415Speter 339428415Speter /* search */ 339528415Speter while (n && m < 4) 339628415Speter { 339728415Speter if (*p == (Byte)(m < 2 ? 0 : 0xff)) 339828415Speter m++; 339928415Speter else if (*p) 340028415Speter m = 0; 340128415Speter else 340228415Speter m = 4 - m; 340328415Speter p++, n--; 340428415Speter } 340528415Speter 340628415Speter /* restore */ 340728415Speter z->total_in += p - z->next_in; 340828415Speter z->next_in = p; 340928415Speter z->avail_in = n; 341028415Speter z->state->sub.marker = m; 341128415Speter 341228415Speter /* return no joy or set up to restart on a new block */ 341328415Speter if (m != 4) 341428415Speter return Z_DATA_ERROR; 341528415Speter r = z->total_in; w = z->total_out; 341628415Speter inflateReset(z); 341728415Speter z->total_in = r; z->total_out = w; 341828415Speter z->state->mode = BLOCKS; 341928415Speter return Z_OK; 342028415Speter} 342128415Speter 342228415Speter#undef NEEDBYTE 342328415Speter#undef NEXTBYTE 342434768Speter/* --- inflate.c */ 342528415Speter 342634768Speter/* +++ infblock.c */ 342734768Speter/* infblock.c -- interpret and process block types to last block 342834768Speter * Copyright (C) 1995-1996 Mark Adler 342934768Speter * For conditions of distribution and use, see copyright notice in zlib.h 343034768Speter */ 343134768Speter 343234768Speter/* #include "zutil.h" */ 343334768Speter/* #include "infblock.h" */ 343434768Speter 343534768Speter/* +++ inftrees.h */ 343634768Speter/* inftrees.h -- header to use inftrees.c 343734768Speter * Copyright (C) 1995-1996 Mark Adler 343834768Speter * For conditions of distribution and use, see copyright notice in zlib.h 343934768Speter */ 344034768Speter 344134768Speter/* WARNING: this file should *not* be used by applications. It is 344234768Speter part of the implementation of the compression library and is 344334768Speter subject to change. Applications should only use zlib.h. 344434768Speter */ 344534768Speter 344634768Speter/* Huffman code lookup table entry--this entry is four bytes for machines 344734768Speter that have 16-bit pointers (e.g. PC's in the small or medium model). */ 344834768Speter 344934768Spetertypedef struct inflate_huft_s FAR inflate_huft; 345034768Speter 345134768Speterstruct inflate_huft_s { 345234768Speter union { 345334768Speter struct { 345434768Speter Byte Exop; /* number of extra bits or operation */ 345534768Speter Byte Bits; /* number of bits in this code or subcode */ 345634768Speter } what; 345734768Speter Bytef *pad; /* pad structure to a power of 2 (4 bytes for */ 345834768Speter } word; /* 16-bit, 8 bytes for 32-bit machines) */ 345934768Speter union { 346034768Speter uInt Base; /* literal, length base, or distance base */ 346134768Speter inflate_huft *Next; /* pointer to next level of table */ 346234768Speter } more; 346334768Speter}; 346434768Speter 346534768Speter#ifdef DEBUG_ZLIB 346634768Speter extern uInt inflate_hufts; 346734768Speter#endif 346834768Speter 346934768Speterextern int inflate_trees_bits OF(( 347034768Speter uIntf *, /* 19 code lengths */ 347134768Speter uIntf *, /* bits tree desired/actual depth */ 347234768Speter inflate_huft * FAR *, /* bits tree result */ 347334768Speter z_streamp )); /* for zalloc, zfree functions */ 347434768Speter 347534768Speterextern int inflate_trees_dynamic OF(( 347634768Speter uInt, /* number of literal/length codes */ 347734768Speter uInt, /* number of distance codes */ 347834768Speter uIntf *, /* that many (total) code lengths */ 347934768Speter uIntf *, /* literal desired/actual bit depth */ 348034768Speter uIntf *, /* distance desired/actual bit depth */ 348134768Speter inflate_huft * FAR *, /* literal/length tree result */ 348234768Speter inflate_huft * FAR *, /* distance tree result */ 348334768Speter z_streamp )); /* for zalloc, zfree functions */ 348434768Speter 348534768Speterextern int inflate_trees_fixed OF(( 348634768Speter uIntf *, /* literal desired/actual bit depth */ 348734768Speter uIntf *, /* distance desired/actual bit depth */ 348834768Speter inflate_huft * FAR *, /* literal/length tree result */ 348934768Speter inflate_huft * FAR *)); /* distance tree result */ 349034768Speter 349134768Speterextern int inflate_trees_free OF(( 349234768Speter inflate_huft *, /* tables to free */ 349334768Speter z_streamp )); /* for zfree function */ 349434768Speter 349534768Speter/* --- inftrees.h */ 349634768Speter 349734768Speter/* +++ infcodes.h */ 349834768Speter/* infcodes.h -- header to use infcodes.c 349934768Speter * Copyright (C) 1995-1996 Mark Adler 350034768Speter * For conditions of distribution and use, see copyright notice in zlib.h 350134768Speter */ 350234768Speter 350334768Speter/* WARNING: this file should *not* be used by applications. It is 350434768Speter part of the implementation of the compression library and is 350534768Speter subject to change. Applications should only use zlib.h. 350634768Speter */ 350734768Speter 350834768Speterstruct inflate_codes_state; 350934768Spetertypedef struct inflate_codes_state FAR inflate_codes_statef; 351034768Speter 351134768Speterextern inflate_codes_statef *inflate_codes_new OF(( 351234768Speter uInt, uInt, 351334768Speter inflate_huft *, inflate_huft *, 351434768Speter z_streamp )); 351534768Speter 351634768Speterextern int inflate_codes OF(( 351734768Speter inflate_blocks_statef *, 351834768Speter z_streamp , 351934768Speter int)); 352034768Speter 352134768Speterextern void inflate_codes_free OF(( 352234768Speter inflate_codes_statef *, 352334768Speter z_streamp )); 352434768Speter 352534768Speter/* --- infcodes.h */ 352634768Speter 352734768Speter/* +++ infutil.h */ 352828415Speter/* infutil.h -- types and macros common to blocks and codes 352934768Speter * Copyright (C) 1995-1996 Mark Adler 353028415Speter * For conditions of distribution and use, see copyright notice in zlib.h 353128415Speter */ 353228415Speter 353328415Speter/* WARNING: this file should *not* be used by applications. It is 353428415Speter part of the implementation of the compression library and is 353528415Speter subject to change. Applications should only use zlib.h. 353628415Speter */ 353728415Speter 353834768Speter#ifndef _INFUTIL_H 353934768Speter#define _INFUTIL_H 354028415Speter 354134768Spetertypedef enum { 354228415Speter TYPE, /* get type bits (3, including end bit) */ 354328415Speter LENS, /* get lengths for stored */ 354428415Speter STORED, /* processing stored block */ 354528415Speter TABLE, /* get table lengths */ 354628415Speter BTREE, /* get bit lengths tree for a dynamic block */ 354728415Speter DTREE, /* get length, distance trees for a dynamic block */ 354828415Speter CODES, /* processing fixed or dynamic block */ 354928415Speter DRY, /* output remaining window bytes */ 355034768Speter DONEB, /* finished last block, done */ 355134768Speter BADB} /* got a data error--stuck here */ 355234768Speterinflate_block_mode; 355328415Speter 355434768Speter/* inflate blocks semi-private state */ 355534768Speterstruct inflate_blocks_state { 355634768Speter 355734768Speter /* mode */ 355834768Speter inflate_block_mode mode; /* current inflate_block mode */ 355934768Speter 356028415Speter /* mode dependent information */ 356128415Speter union { 356228415Speter uInt left; /* if STORED, bytes left to copy */ 356328415Speter struct { 356428415Speter uInt table; /* table lengths (14 bits) */ 356528415Speter uInt index; /* index into blens (or border) */ 356628415Speter uIntf *blens; /* bit lengths of codes */ 356728415Speter uInt bb; /* bit length tree depth */ 356828415Speter inflate_huft *tb; /* bit length decoding tree */ 356928415Speter } trees; /* if DTREE, decoding info for trees */ 357028415Speter struct { 357134768Speter inflate_huft *tl; 357234768Speter inflate_huft *td; /* trees to free */ 357328415Speter inflate_codes_statef 357428415Speter *codes; 357528415Speter } decode; /* if CODES, current state */ 357628415Speter } sub; /* submode */ 357728415Speter uInt last; /* true if this block is the last block */ 357828415Speter 357928415Speter /* mode independent information */ 358028415Speter uInt bitk; /* bits in bit buffer */ 358128415Speter uLong bitb; /* bit buffer */ 358228415Speter Bytef *window; /* sliding window */ 358328415Speter Bytef *end; /* one byte after sliding window */ 358428415Speter Bytef *read; /* window read pointer */ 358528415Speter Bytef *write; /* window write pointer */ 358628415Speter check_func checkfn; /* check function */ 358728415Speter uLong check; /* check on output */ 358828415Speter 358928415Speter}; 359028415Speter 359128415Speter 359228415Speter/* defines for inflate input/output */ 359328415Speter/* update pointers and return */ 359428415Speter#define UPDBITS {s->bitb=b;s->bitk=k;} 359528415Speter#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;} 359628415Speter#define UPDOUT {s->write=q;} 359728415Speter#define UPDATE {UPDBITS UPDIN UPDOUT} 359828415Speter#define LEAVE {UPDATE return inflate_flush(s,z,r);} 359928415Speter/* get bytes and bits */ 360028415Speter#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;} 360128415Speter#define NEEDBYTE {if(n)r=Z_OK;else LEAVE} 360228415Speter#define NEXTBYTE (n--,*p++) 360328415Speter#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}} 360428415Speter#define DUMPBITS(j) {b>>=(j);k-=(j);} 360528415Speter/* output bytes */ 360634768Speter#define WAVAIL (uInt)(q<s->read?s->read-q-1:s->end-q) 360734768Speter#define LOADOUT {q=s->write;m=(uInt)WAVAIL;} 360834768Speter#define WWRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}} 360928415Speter#define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT} 361034768Speter#define NEEDOUT {if(m==0){WWRAP if(m==0){FLUSH WWRAP if(m==0) LEAVE}}r=Z_OK;} 361128415Speter#define OUTBYTE(a) {*q++=(Byte)(a);m--;} 361228415Speter/* load local pointers */ 361328415Speter#define LOAD {LOADIN LOADOUT} 361428415Speter 361534768Speter/* masks for lower bits (size given to avoid silly warnings with Visual C++) */ 361634768Speterextern uInt inflate_mask[17]; 361728415Speter 361828415Speter/* copy as much as possible from the sliding window to the output area */ 361934768Speterextern int inflate_flush OF(( 362028415Speter inflate_blocks_statef *, 362134768Speter z_streamp , 362228415Speter int)); 362328415Speter 362434768Speter#ifndef NO_DUMMY_DECL 362534768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 362634768Speter#endif 362728415Speter 362834768Speter#endif 362934768Speter/* --- infutil.h */ 363028415Speter 363134768Speter#ifndef NO_DUMMY_DECL 363234768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 363334768Speter#endif 363428415Speter 363528415Speter/* Table for deflate from PKZIP's appnote.txt. */ 363634768Speterlocal const uInt border[] = { /* Order of the bit length code lengths */ 363728415Speter 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; 363828415Speter 363928415Speter/* 364028415Speter Notes beyond the 1.93a appnote.txt: 364128415Speter 364228415Speter 1. Distance pointers never point before the beginning of the output 364328415Speter stream. 364428415Speter 2. Distance pointers can point back across blocks, up to 32k away. 364528415Speter 3. There is an implied maximum of 7 bits for the bit length table and 364628415Speter 15 bits for the actual data. 364728415Speter 4. If only one code exists, then it is encoded using one bit. (Zero 364828415Speter would be more efficient, but perhaps a little confusing.) If two 364928415Speter codes exist, they are coded using one bit each (0 and 1). 365028415Speter 5. There is no way of sending zero distance codes--a dummy must be 365128415Speter sent if there are none. (History: a pre 2.0 version of PKZIP would 365228415Speter store blocks with no distance codes, but this was discovered to be 365328415Speter too harsh a criterion.) Valid only for 1.93a. 2.04c does allow 365428415Speter zero distance codes, which is sent as one code of zero bits in 365528415Speter length. 365628415Speter 6. There are up to 286 literal/length codes. Code 256 represents the 365728415Speter end-of-block. Note however that the static length tree defines 365828415Speter 288 codes just to fill out the Huffman codes. Codes 286 and 287 365928415Speter cannot be used though, since there is no length base or extra bits 366028415Speter defined for them. Similarily, there are up to 30 distance codes. 366128415Speter However, static trees define 32 codes (all 5 bits) to fill out the 366228415Speter Huffman codes, but the last two had better not show up in the data. 366328415Speter 7. Unzip can check dynamic Huffman blocks for complete code sets. 366428415Speter The exception is that a single code would not be complete (see #4). 366528415Speter 8. The five bits following the block type is really the number of 366628415Speter literal codes sent minus 257. 366728415Speter 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits 366828415Speter (1+6+6). Therefore, to output three times the length, you output 366928415Speter three codes (1+1+1), whereas to output four times the same length, 367028415Speter you only need two codes (1+3). Hmm. 367128415Speter 10. In the tree reconstruction algorithm, Code = Code + Increment 367228415Speter only if BitLength(i) is not zero. (Pretty obvious.) 367328415Speter 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19) 367428415Speter 12. Note: length code 284 can represent 227-258, but length code 285 367528415Speter really is 258. The last length deserves its own, short code 367628415Speter since it gets used a lot in very redundant files. The length 367728415Speter 258 is special since 258 - 3 (the min match length) is 255. 367828415Speter 13. The literal/length and distance code bit lengths are read as a 367928415Speter single stream of lengths. It is possible (and advantageous) for 368028415Speter a repeat code (16, 17, or 18) to go across the boundary between 368128415Speter the two sets of lengths. 368228415Speter */ 368328415Speter 368428415Speter 368534768Spetervoid inflate_blocks_reset(s, z, c) 368628415Speterinflate_blocks_statef *s; 368734768Speterz_streamp z; 368828415SpeteruLongf *c; 368928415Speter{ 369028415Speter if (s->checkfn != Z_NULL) 369128415Speter *c = s->check; 369228415Speter if (s->mode == BTREE || s->mode == DTREE) 369334768Speter ZFREE(z, s->sub.trees.blens); 369428415Speter if (s->mode == CODES) 369528415Speter { 369628415Speter inflate_codes_free(s->sub.decode.codes, z); 369728415Speter inflate_trees_free(s->sub.decode.td, z); 369828415Speter inflate_trees_free(s->sub.decode.tl, z); 369928415Speter } 370028415Speter s->mode = TYPE; 370128415Speter s->bitk = 0; 370228415Speter s->bitb = 0; 370328415Speter s->read = s->write = s->window; 370428415Speter if (s->checkfn != Z_NULL) 370534768Speter z->adler = s->check = (*s->checkfn)(0L, Z_NULL, 0); 370628415Speter Trace((stderr, "inflate: blocks reset\n")); 370728415Speter} 370828415Speter 370928415Speter 371034768Speterinflate_blocks_statef *inflate_blocks_new(z, c, w) 371134768Speterz_streamp z; 371228415Spetercheck_func c; 371328415SpeteruInt w; 371428415Speter{ 371528415Speter inflate_blocks_statef *s; 371628415Speter 371734768Speter if ((s = (inflate_blocks_statef *)ZALLOC 371828415Speter (z,1,sizeof(struct inflate_blocks_state))) == Z_NULL) 371928415Speter return s; 372034768Speter if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL) 372128415Speter { 372234768Speter ZFREE(z, s); 372328415Speter return Z_NULL; 372428415Speter } 372528415Speter s->end = s->window + w; 372628415Speter s->checkfn = c; 372728415Speter s->mode = TYPE; 372828415Speter Trace((stderr, "inflate: blocks allocated\n")); 372928415Speter inflate_blocks_reset(s, z, &s->check); 373028415Speter return s; 373128415Speter} 373228415Speter 373328415Speter 373434768Speter#ifdef DEBUG_ZLIB 373534768Speter extern uInt inflate_hufts; 373634768Speter#endif 373734768Speterint inflate_blocks(s, z, r) 373828415Speterinflate_blocks_statef *s; 373934768Speterz_streamp z; 374028415Speterint r; 374128415Speter{ 374228415Speter uInt t; /* temporary storage */ 374328415Speter uLong b; /* bit buffer */ 374428415Speter uInt k; /* bits in bit buffer */ 374528415Speter Bytef *p; /* input data pointer */ 374628415Speter uInt n; /* bytes available there */ 374728415Speter Bytef *q; /* output window write pointer */ 374828415Speter uInt m; /* bytes to end of window or read pointer */ 374928415Speter 375028415Speter /* copy input/output information to locals (UPDATE macro restores) */ 375128415Speter LOAD 375228415Speter 375328415Speter /* process input based on current state */ 375428415Speter while (1) switch (s->mode) 375528415Speter { 375628415Speter case TYPE: 375728415Speter NEEDBITS(3) 375828415Speter t = (uInt)b & 7; 375928415Speter s->last = t & 1; 376028415Speter switch (t >> 1) 376128415Speter { 376228415Speter case 0: /* stored */ 376328415Speter Trace((stderr, "inflate: stored block%s\n", 376428415Speter s->last ? " (last)" : "")); 376528415Speter DUMPBITS(3) 376628415Speter t = k & 7; /* go to byte boundary */ 376728415Speter DUMPBITS(t) 376828415Speter s->mode = LENS; /* get length of stored block */ 376928415Speter break; 377028415Speter case 1: /* fixed */ 377128415Speter Trace((stderr, "inflate: fixed codes block%s\n", 377228415Speter s->last ? " (last)" : "")); 377328415Speter { 377428415Speter uInt bl, bd; 377528415Speter inflate_huft *tl, *td; 377628415Speter 377728415Speter inflate_trees_fixed(&bl, &bd, &tl, &td); 377828415Speter s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z); 377928415Speter if (s->sub.decode.codes == Z_NULL) 378028415Speter { 378128415Speter r = Z_MEM_ERROR; 378228415Speter LEAVE 378328415Speter } 378428415Speter s->sub.decode.tl = Z_NULL; /* don't try to free these */ 378528415Speter s->sub.decode.td = Z_NULL; 378628415Speter } 378728415Speter DUMPBITS(3) 378828415Speter s->mode = CODES; 378928415Speter break; 379028415Speter case 2: /* dynamic */ 379128415Speter Trace((stderr, "inflate: dynamic codes block%s\n", 379228415Speter s->last ? " (last)" : "")); 379328415Speter DUMPBITS(3) 379428415Speter s->mode = TABLE; 379528415Speter break; 379628415Speter case 3: /* illegal */ 379728415Speter DUMPBITS(3) 379828415Speter s->mode = BADB; 379934768Speter z->msg = (char*)"invalid block type"; 380028415Speter r = Z_DATA_ERROR; 380128415Speter LEAVE 380228415Speter } 380328415Speter break; 380428415Speter case LENS: 380528415Speter NEEDBITS(32) 380634768Speter if ((((~b) >> 16) & 0xffff) != (b & 0xffff)) 380728415Speter { 380828415Speter s->mode = BADB; 380934768Speter z->msg = (char*)"invalid stored block lengths"; 381028415Speter r = Z_DATA_ERROR; 381128415Speter LEAVE 381228415Speter } 381328415Speter s->sub.left = (uInt)b & 0xffff; 381428415Speter b = k = 0; /* dump bits */ 381528415Speter Tracev((stderr, "inflate: stored length %u\n", s->sub.left)); 381634768Speter s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE); 381728415Speter break; 381828415Speter case STORED: 381928415Speter if (n == 0) 382028415Speter LEAVE 382128415Speter NEEDOUT 382228415Speter t = s->sub.left; 382328415Speter if (t > n) t = n; 382428415Speter if (t > m) t = m; 382528415Speter zmemcpy(q, p, t); 382628415Speter p += t; n -= t; 382728415Speter q += t; m -= t; 382828415Speter if ((s->sub.left -= t) != 0) 382928415Speter break; 383028415Speter Tracev((stderr, "inflate: stored end, %lu total out\n", 383128415Speter z->total_out + (q >= s->read ? q - s->read : 383228415Speter (s->end - s->read) + (q - s->window)))); 383328415Speter s->mode = s->last ? DRY : TYPE; 383428415Speter break; 383528415Speter case TABLE: 383628415Speter NEEDBITS(14) 383728415Speter s->sub.trees.table = t = (uInt)b & 0x3fff; 383828415Speter#ifndef PKZIP_BUG_WORKAROUND 383928415Speter if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29) 384028415Speter { 384128415Speter s->mode = BADB; 384234768Speter z->msg = (char*)"too many length or distance symbols"; 384328415Speter r = Z_DATA_ERROR; 384428415Speter LEAVE 384528415Speter } 384628415Speter#endif 384728415Speter t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f); 384828415Speter if (t < 19) 384928415Speter t = 19; 385028415Speter if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL) 385128415Speter { 385228415Speter r = Z_MEM_ERROR; 385328415Speter LEAVE 385428415Speter } 385528415Speter DUMPBITS(14) 385628415Speter s->sub.trees.index = 0; 385728415Speter Tracev((stderr, "inflate: table sizes ok\n")); 385828415Speter s->mode = BTREE; 385928415Speter case BTREE: 386028415Speter while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10)) 386128415Speter { 386228415Speter NEEDBITS(3) 386328415Speter s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7; 386428415Speter DUMPBITS(3) 386528415Speter } 386628415Speter while (s->sub.trees.index < 19) 386728415Speter s->sub.trees.blens[border[s->sub.trees.index++]] = 0; 386828415Speter s->sub.trees.bb = 7; 386928415Speter t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb, 387028415Speter &s->sub.trees.tb, z); 387128415Speter if (t != Z_OK) 387228415Speter { 387328415Speter r = t; 387490775Sjedgar if (r == Z_DATA_ERROR) { 387590775Sjedgar ZFREE(z, s->sub.trees.blens); 387628415Speter s->mode = BADB; 387790775Sjedgar } 387828415Speter LEAVE 387928415Speter } 388028415Speter s->sub.trees.index = 0; 388128415Speter Tracev((stderr, "inflate: bits tree ok\n")); 388228415Speter s->mode = DTREE; 388328415Speter case DTREE: 388428415Speter while (t = s->sub.trees.table, 388528415Speter s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f)) 388628415Speter { 388728415Speter inflate_huft *h; 388828415Speter uInt i, j, c; 388928415Speter 389028415Speter t = s->sub.trees.bb; 389128415Speter NEEDBITS(t) 389228415Speter h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]); 389328415Speter t = h->word.what.Bits; 389428415Speter c = h->more.Base; 389528415Speter if (c < 16) 389628415Speter { 389728415Speter DUMPBITS(t) 389828415Speter s->sub.trees.blens[s->sub.trees.index++] = c; 389928415Speter } 390028415Speter else /* c == 16..18 */ 390128415Speter { 390228415Speter i = c == 18 ? 7 : c - 14; 390328415Speter j = c == 18 ? 11 : 3; 390428415Speter NEEDBITS(t + i) 390528415Speter DUMPBITS(t) 390628415Speter j += (uInt)b & inflate_mask[i]; 390728415Speter DUMPBITS(i) 390828415Speter i = s->sub.trees.index; 390928415Speter t = s->sub.trees.table; 391028415Speter if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) || 391128415Speter (c == 16 && i < 1)) 391228415Speter { 391334768Speter inflate_trees_free(s->sub.trees.tb, z); 391434768Speter ZFREE(z, s->sub.trees.blens); 391528415Speter s->mode = BADB; 391634768Speter z->msg = (char*)"invalid bit length repeat"; 391728415Speter r = Z_DATA_ERROR; 391828415Speter LEAVE 391928415Speter } 392028415Speter c = c == 16 ? s->sub.trees.blens[i - 1] : 0; 392128415Speter do { 392228415Speter s->sub.trees.blens[i++] = c; 392328415Speter } while (--j); 392428415Speter s->sub.trees.index = i; 392528415Speter } 392628415Speter } 392728415Speter inflate_trees_free(s->sub.trees.tb, z); 392828415Speter s->sub.trees.tb = Z_NULL; 392928415Speter { 393028415Speter uInt bl, bd; 393128415Speter inflate_huft *tl, *td; 393228415Speter inflate_codes_statef *c; 393328415Speter 393428415Speter bl = 9; /* must be <= 9 for lookahead assumptions */ 393528415Speter bd = 6; /* must be <= 9 for lookahead assumptions */ 393628415Speter t = s->sub.trees.table; 393734768Speter#ifdef DEBUG_ZLIB 393834768Speter inflate_hufts = 0; 393934768Speter#endif 394028415Speter t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f), 394128415Speter s->sub.trees.blens, &bl, &bd, &tl, &td, z); 394228415Speter if (t != Z_OK) 394328415Speter { 394490775Sjedgar if (t == (uInt)Z_DATA_ERROR) { 394590775Sjedgar ZFREE(z, s->sub.trees.blens); 394628415Speter s->mode = BADB; 394790775Sjedgar } 394828415Speter r = t; 394928415Speter LEAVE 395028415Speter } 395134768Speter Tracev((stderr, "inflate: trees ok, %d * %d bytes used\n", 395234768Speter inflate_hufts, sizeof(inflate_huft))); 395328415Speter if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL) 395428415Speter { 395528415Speter inflate_trees_free(td, z); 395628415Speter inflate_trees_free(tl, z); 395728415Speter r = Z_MEM_ERROR; 395828415Speter LEAVE 395928415Speter } 396092749Sdillon /* 396192749Sdillon * this ZFREE must occur *BEFORE* we mess with sub.decode, because 396292749Sdillon * sub.trees is union'd with sub.decode. 396392749Sdillon */ 396492749Sdillon ZFREE(z, s->sub.trees.blens); 396528415Speter s->sub.decode.codes = c; 396628415Speter s->sub.decode.tl = tl; 396728415Speter s->sub.decode.td = td; 396828415Speter } 396928415Speter s->mode = CODES; 397028415Speter case CODES: 397128415Speter UPDATE 397228415Speter if ((r = inflate_codes(s, z, r)) != Z_STREAM_END) 397328415Speter return inflate_flush(s, z, r); 397428415Speter r = Z_OK; 397528415Speter inflate_codes_free(s->sub.decode.codes, z); 397628415Speter inflate_trees_free(s->sub.decode.td, z); 397728415Speter inflate_trees_free(s->sub.decode.tl, z); 397828415Speter LOAD 397928415Speter Tracev((stderr, "inflate: codes end, %lu total out\n", 398028415Speter z->total_out + (q >= s->read ? q - s->read : 398128415Speter (s->end - s->read) + (q - s->window)))); 398228415Speter if (!s->last) 398328415Speter { 398428415Speter s->mode = TYPE; 398528415Speter break; 398628415Speter } 398728415Speter if (k > 7) /* return unused byte, if any */ 398828415Speter { 398928415Speter Assert(k < 16, "inflate_codes grabbed too many bytes") 399028415Speter k -= 8; 399128415Speter n++; 399228415Speter p--; /* can always return one */ 399328415Speter } 399428415Speter s->mode = DRY; 399528415Speter case DRY: 399628415Speter FLUSH 399728415Speter if (s->read != s->write) 399828415Speter LEAVE 399928415Speter s->mode = DONEB; 400028415Speter case DONEB: 400128415Speter r = Z_STREAM_END; 400228415Speter LEAVE 400328415Speter case BADB: 400428415Speter r = Z_DATA_ERROR; 400528415Speter LEAVE 400628415Speter default: 400728415Speter r = Z_STREAM_ERROR; 400828415Speter LEAVE 400928415Speter } 401028415Speter} 401128415Speter 401228415Speter 401334768Speterint inflate_blocks_free(s, z, c) 401428415Speterinflate_blocks_statef *s; 401534768Speterz_streamp z; 401628415SpeteruLongf *c; 401728415Speter{ 401828415Speter inflate_blocks_reset(s, z, c); 401934768Speter ZFREE(z, s->window); 402034768Speter ZFREE(z, s); 402128415Speter Trace((stderr, "inflate: blocks freed\n")); 402228415Speter return Z_OK; 402328415Speter} 402428415Speter 402534768Speter 402634768Spetervoid inflate_set_dictionary(s, d, n) 402734768Speterinflate_blocks_statef *s; 402834768Speterconst Bytef *d; 402934768SpeteruInt n; 403034768Speter{ 403134768Speter zmemcpy((charf *)s->window, d, n); 403234768Speter s->read = s->write = s->window + n; 403334768Speter} 403434768Speter 403528415Speter/* 403628415Speter * This subroutine adds the data at next_in/avail_in to the output history 403728415Speter * without performing any output. The output buffer must be "caught up"; 403828415Speter * i.e. no pending output (hence s->read equals s->write), and the state must 403928415Speter * be BLOCKS (i.e. we should be willing to see the start of a series of 404028415Speter * BLOCKS). On exit, the output will also be caught up, and the checksum 404128415Speter * will have been updated if need be. 404228415Speter */ 404334768Speterint inflate_addhistory(s, z) 404428415Speterinflate_blocks_statef *s; 404528415Speterz_stream *z; 404628415Speter{ 404728415Speter uLong b; /* bit buffer */ /* NOT USED HERE */ 404828415Speter uInt k; /* bits in bit buffer */ /* NOT USED HERE */ 404928415Speter uInt t; /* temporary storage */ 405028415Speter Bytef *p; /* input data pointer */ 405128415Speter uInt n; /* bytes available there */ 405228415Speter Bytef *q; /* output window write pointer */ 405328415Speter uInt m; /* bytes to end of window or read pointer */ 405428415Speter 405528415Speter if (s->read != s->write) 405628415Speter return Z_STREAM_ERROR; 405728415Speter if (s->mode != TYPE) 405828415Speter return Z_DATA_ERROR; 405928415Speter 406028415Speter /* we're ready to rock */ 406128415Speter LOAD 406228415Speter /* while there is input ready, copy to output buffer, moving 406328415Speter * pointers as needed. 406428415Speter */ 406528415Speter while (n) { 406628415Speter t = n; /* how many to do */ 406728415Speter /* is there room until end of buffer? */ 406828415Speter if (t > m) t = m; 406928415Speter /* update check information */ 407028415Speter if (s->checkfn != Z_NULL) 407128415Speter s->check = (*s->checkfn)(s->check, q, t); 407228415Speter zmemcpy(q, p, t); 407328415Speter q += t; 407428415Speter p += t; 407528415Speter n -= t; 407628415Speter z->total_out += t; 407728415Speter s->read = q; /* drag read pointer forward */ 407834768Speter/* WWRAP */ /* expand WWRAP macro by hand to handle s->read */ 407928415Speter if (q == s->end) { 408028415Speter s->read = q = s->window; 408128415Speter m = WAVAIL; 408228415Speter } 408328415Speter } 408428415Speter UPDATE 408528415Speter return Z_OK; 408628415Speter} 408728415Speter 408828415Speter 408928415Speter/* 409028415Speter * At the end of a Deflate-compressed PPP packet, we expect to have seen 409128415Speter * a `stored' block type value but not the (zero) length bytes. 409228415Speter */ 409334768Speterint inflate_packet_flush(s) 409428415Speter inflate_blocks_statef *s; 409528415Speter{ 409628415Speter if (s->mode != LENS) 409728415Speter return Z_DATA_ERROR; 409828415Speter s->mode = TYPE; 409928415Speter return Z_OK; 410028415Speter} 410134768Speter/* --- infblock.c */ 410228415Speter 410334768Speter/* +++ inftrees.c */ 410428415Speter/* inftrees.c -- generate Huffman trees for efficient decoding 410534768Speter * Copyright (C) 1995-1996 Mark Adler 410628415Speter * For conditions of distribution and use, see copyright notice in zlib.h 410728415Speter */ 410828415Speter 410934768Speter/* #include "zutil.h" */ 411034768Speter/* #include "inftrees.h" */ 411134768Speter 411234768Speterchar inflate_copyright[] = " inflate 1.0.4 Copyright 1995-1996 Mark Adler "; 411334768Speter/* 411434768Speter If you use the zlib library in a product, an acknowledgment is welcome 411534768Speter in the documentation of your product. If for some reason you cannot 411634768Speter include such an acknowledgment, I would appreciate that you keep this 411734768Speter copyright string in the executable of your product. 411834768Speter */ 411934768Speter 412034768Speter#ifndef NO_DUMMY_DECL 412134768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 412234768Speter#endif 412334768Speter 412428415Speter/* simplify the use of the inflate_huft type with some defines */ 412528415Speter#define base more.Base 412628415Speter#define next more.Next 412728415Speter#define exop word.what.Exop 412828415Speter#define bits word.what.Bits 412928415Speter 413028415Speter 413128415Speterlocal int huft_build OF(( 413228415Speter uIntf *, /* code lengths in bits */ 413328415Speter uInt, /* number of codes */ 413428415Speter uInt, /* number of "simple" codes */ 413534768Speter const uIntf *, /* list of base values for non-simple codes */ 413634768Speter const uIntf *, /* list of extra bits for non-simple codes */ 413728415Speter inflate_huft * FAR*,/* result: starting table */ 413828415Speter uIntf *, /* maximum lookup bits (returns actual) */ 413934768Speter z_streamp )); /* for zalloc function */ 414028415Speter 414128415Speterlocal voidpf falloc OF(( 414228415Speter voidpf, /* opaque pointer (not used) */ 414328415Speter uInt, /* number of items */ 414428415Speter uInt)); /* size of item */ 414528415Speter 414628415Speter/* Tables for deflate from PKZIP's appnote.txt. */ 414734768Speterlocal const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */ 414828415Speter 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 414928415Speter 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0}; 415034768Speter /* see note #13 above about 258 */ 415134768Speterlocal const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */ 415228415Speter 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 415334768Speter 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */ 415434768Speterlocal const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */ 415528415Speter 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 415628415Speter 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 415728415Speter 8193, 12289, 16385, 24577}; 415834768Speterlocal const uInt cpdext[30] = { /* Extra bits for distance codes */ 415928415Speter 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 416028415Speter 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 416128415Speter 12, 12, 13, 13}; 416228415Speter 416328415Speter/* 416428415Speter Huffman code decoding is performed using a multi-level table lookup. 416528415Speter The fastest way to decode is to simply build a lookup table whose 416628415Speter size is determined by the longest code. However, the time it takes 416728415Speter to build this table can also be a factor if the data being decoded 416828415Speter is not very long. The most common codes are necessarily the 416928415Speter shortest codes, so those codes dominate the decoding time, and hence 417028415Speter the speed. The idea is you can have a shorter table that decodes the 417128415Speter shorter, more probable codes, and then point to subsidiary tables for 417228415Speter the longer codes. The time it costs to decode the longer codes is 417328415Speter then traded against the time it takes to make longer tables. 417428415Speter 417528415Speter This results of this trade are in the variables lbits and dbits 417628415Speter below. lbits is the number of bits the first level table for literal/ 417728415Speter length codes can decode in one step, and dbits is the same thing for 417828415Speter the distance codes. Subsequent tables are also less than or equal to 417928415Speter those sizes. These values may be adjusted either when all of the 418028415Speter codes are shorter than that, in which case the longest code length in 418128415Speter bits is used, or when the shortest code is *longer* than the requested 418228415Speter table size, in which case the length of the shortest code in bits is 418328415Speter used. 418428415Speter 418528415Speter There are two different values for the two tables, since they code a 418628415Speter different number of possibilities each. The literal/length table 418728415Speter codes 286 possible values, or in a flat code, a little over eight 418828415Speter bits. The distance table codes 30 possible values, or a little less 418928415Speter than five bits, flat. The optimum values for speed end up being 419028415Speter about one bit more than those, so lbits is 8+1 and dbits is 5+1. 419128415Speter The optimum values may differ though from machine to machine, and 419228415Speter possibly even between compilers. Your mileage may vary. 419328415Speter */ 419428415Speter 419528415Speter 419628415Speter/* If BMAX needs to be larger than 16, then h and x[] should be uLong. */ 419728415Speter#define BMAX 15 /* maximum bit length of any code */ 419828415Speter#define N_MAX 288 /* maximum number of codes in any set */ 419928415Speter 420028415Speter#ifdef DEBUG_ZLIB 420128415Speter uInt inflate_hufts; 420228415Speter#endif 420328415Speter 420428415Speterlocal int huft_build(b, n, s, d, e, t, m, zs) 420528415SpeteruIntf *b; /* code lengths in bits (all assumed <= BMAX) */ 420628415SpeteruInt n; /* number of codes (assumed <= N_MAX) */ 420728415SpeteruInt s; /* number of simple-valued codes (0..s-1) */ 420834768Speterconst uIntf *d; /* list of base values for non-simple codes */ 420934768Speterconst uIntf *e; /* list of extra bits for non-simple codes */ 421028415Speterinflate_huft * FAR *t; /* result: starting table */ 421128415SpeteruIntf *m; /* maximum lookup bits, returns actual */ 421234768Speterz_streamp zs; /* for zalloc function */ 421328415Speter/* Given a list of code lengths and a maximum table size, make a set of 421428415Speter tables to decode that set of codes. Return Z_OK on success, Z_BUF_ERROR 421528415Speter if the given code set is incomplete (the tables are still built in this 421634768Speter case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of 421734768Speter lengths), or Z_MEM_ERROR if not enough memory. */ 421828415Speter{ 421928415Speter 422028415Speter uInt a; /* counter for codes of length k */ 422128415Speter uInt c[BMAX+1]; /* bit length count table */ 422228415Speter uInt f; /* i repeats in table every f entries */ 422328415Speter int g; /* maximum code length */ 422428415Speter int h; /* table level */ 4225331643Sdim uInt i; /* counter, current code */ 4226331643Sdim uInt j; /* counter */ 4227331643Sdim int k; /* number of bits in current code */ 422828415Speter int l; /* bits per table (returned in m) */ 4229331643Sdim uIntf *p; /* pointer into c[], b[], or v[] */ 423028415Speter inflate_huft *q; /* points to current table */ 423128415Speter struct inflate_huft_s r; /* table entry for structure assignment */ 423228415Speter inflate_huft *u[BMAX]; /* table stack */ 423328415Speter uInt v[N_MAX]; /* values in order of bit length */ 4234331643Sdim int w; /* bits before this table == (l * h) */ 423528415Speter uInt x[BMAX+1]; /* bit offsets, then code stack */ 423628415Speter uIntf *xp; /* pointer into x */ 423728415Speter int y; /* number of dummy codes added */ 423828415Speter uInt z; /* number of entries in current table */ 423928415Speter 424028415Speter 424128415Speter /* Generate counts for each bit length */ 424228415Speter p = c; 424328415Speter#define C0 *p++ = 0; 424428415Speter#define C2 C0 C0 C0 C0 424528415Speter#define C4 C2 C2 C2 C2 424628415Speter C4 /* clear c[]--assume BMAX+1 is 16 */ 424728415Speter p = b; i = n; 424828415Speter do { 424928415Speter c[*p++]++; /* assume all entries <= BMAX */ 425028415Speter } while (--i); 425128415Speter if (c[0] == n) /* null input--all zero length codes */ 425228415Speter { 425328415Speter *t = (inflate_huft *)Z_NULL; 425428415Speter *m = 0; 425528415Speter return Z_OK; 425628415Speter } 425728415Speter 425828415Speter 425928415Speter /* Find minimum and maximum length, bound *m by those */ 426028415Speter l = *m; 426128415Speter for (j = 1; j <= BMAX; j++) 426228415Speter if (c[j]) 426328415Speter break; 426428415Speter k = j; /* minimum code length */ 426528415Speter if ((uInt)l < j) 426628415Speter l = j; 426728415Speter for (i = BMAX; i; i--) 426828415Speter if (c[i]) 426928415Speter break; 427028415Speter g = i; /* maximum code length */ 427128415Speter if ((uInt)l > i) 427228415Speter l = i; 427328415Speter *m = l; 427428415Speter 427528415Speter 427628415Speter /* Adjust last length count to fill out codes, if needed */ 427728415Speter for (y = 1 << j; j < i; j++, y <<= 1) 427828415Speter if ((y -= c[j]) < 0) 427928415Speter return Z_DATA_ERROR; 428028415Speter if ((y -= c[i]) < 0) 428128415Speter return Z_DATA_ERROR; 428228415Speter c[i] += y; 428328415Speter 428428415Speter 428528415Speter /* Generate starting offsets into the value table for each length */ 428628415Speter x[1] = j = 0; 428728415Speter p = c + 1; xp = x + 2; 428828415Speter while (--i) { /* note that i == g from above */ 428928415Speter *xp++ = (j += *p++); 429028415Speter } 429128415Speter 429228415Speter 429328415Speter /* Make a table of values in order of bit lengths */ 429428415Speter p = b; i = 0; 429528415Speter do { 429628415Speter if ((j = *p++) != 0) 429728415Speter v[x[j]++] = i; 429828415Speter } while (++i < n); 429934768Speter n = x[g]; /* set n to length of v */ 430028415Speter 430128415Speter 430228415Speter /* Generate the Huffman codes and for each, make the table entries */ 430328415Speter x[0] = i = 0; /* first Huffman code is zero */ 430428415Speter p = v; /* grab values in bit order */ 430528415Speter h = -1; /* no tables yet--level -1 */ 430628415Speter w = -l; /* bits decoded == (l * h) */ 430728415Speter u[0] = (inflate_huft *)Z_NULL; /* just to keep compilers happy */ 430828415Speter q = (inflate_huft *)Z_NULL; /* ditto */ 430928415Speter z = 0; /* ditto */ 431028415Speter 431128415Speter /* go through the bit lengths (k already is bits in shortest code) */ 431228415Speter for (; k <= g; k++) 431328415Speter { 431428415Speter a = c[k]; 431528415Speter while (a--) 431628415Speter { 431728415Speter /* here i is the Huffman code of length k bits for value *p */ 431828415Speter /* make tables up to required level */ 431928415Speter while (k > w + l) 432028415Speter { 432128415Speter h++; 432228415Speter w += l; /* previous table always l bits */ 432328415Speter 432428415Speter /* compute minimum size table less than or equal to l bits */ 432534768Speter z = g - w; 432634768Speter z = z > (uInt)l ? l : z; /* table size upper limit */ 432728415Speter if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ 432828415Speter { /* too few codes for k-w bit table */ 432928415Speter f -= a + 1; /* deduct codes from patterns left */ 433028415Speter xp = c + k; 433128415Speter if (j < z) 433228415Speter while (++j < z) /* try smaller tables up to z bits */ 433328415Speter { 433428415Speter if ((f <<= 1) <= *++xp) 433528415Speter break; /* enough codes to use up j bits */ 433628415Speter f -= *xp; /* else deduct codes from patterns */ 433728415Speter } 433828415Speter } 433928415Speter z = 1 << j; /* table entries for j-bit table */ 434028415Speter 434128415Speter /* allocate and link in new table */ 434228415Speter if ((q = (inflate_huft *)ZALLOC 434328415Speter (zs,z + 1,sizeof(inflate_huft))) == Z_NULL) 434428415Speter { 434528415Speter if (h) 434628415Speter inflate_trees_free(u[0], zs); 434728415Speter return Z_MEM_ERROR; /* not enough memory */ 434828415Speter } 434928415Speter#ifdef DEBUG_ZLIB 435028415Speter inflate_hufts += z + 1; 435128415Speter#endif 435228415Speter *t = q + 1; /* link to list for huft_free() */ 435328415Speter *(t = &(q->next)) = Z_NULL; 435428415Speter u[h] = ++q; /* table starts after link */ 435528415Speter 435628415Speter /* connect to last table, if there is one */ 435728415Speter if (h) 435828415Speter { 435928415Speter x[h] = i; /* save pattern for backing up */ 436028415Speter r.bits = (Byte)l; /* bits to dump before this table */ 436128415Speter r.exop = (Byte)j; /* bits in this table */ 436228415Speter r.next = q; /* pointer to this table */ 436328415Speter j = i >> (w - l); /* (get around Turbo C bug) */ 436428415Speter u[h-1][j] = r; /* connect to last table */ 436528415Speter } 436628415Speter } 436728415Speter 436828415Speter /* set up table entry in r */ 436928415Speter r.bits = (Byte)(k - w); 437028415Speter if (p >= v + n) 437128415Speter r.exop = 128 + 64; /* out of values--invalid code */ 437228415Speter else if (*p < s) 437328415Speter { 437428415Speter r.exop = (Byte)(*p < 256 ? 0 : 32 + 64); /* 256 is end-of-block */ 437528415Speter r.base = *p++; /* simple code is just the value */ 437628415Speter } 437728415Speter else 437828415Speter { 437934768Speter r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */ 438028415Speter r.base = d[*p++ - s]; 438128415Speter } 438228415Speter 438328415Speter /* fill code-like entries with r */ 438428415Speter f = 1 << (k - w); 438528415Speter for (j = i >> w; j < z; j += f) 438628415Speter q[j] = r; 438728415Speter 438828415Speter /* backwards increment the k-bit code i */ 438928415Speter for (j = 1 << (k - 1); i & j; j >>= 1) 439028415Speter i ^= j; 439128415Speter i ^= j; 439228415Speter 439328415Speter /* backup over finished tables */ 439428415Speter while ((i & ((1 << w) - 1)) != x[h]) 439528415Speter { 439628415Speter h--; /* don't need to update q */ 439728415Speter w -= l; 439828415Speter } 439928415Speter } 440028415Speter } 440128415Speter 440228415Speter 440328415Speter /* Return Z_BUF_ERROR if we were given an incomplete table */ 440428415Speter return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK; 440528415Speter} 440628415Speter 440728415Speter 440834768Speterint inflate_trees_bits(c, bb, tb, z) 440928415SpeteruIntf *c; /* 19 code lengths */ 441028415SpeteruIntf *bb; /* bits tree desired/actual depth */ 441128415Speterinflate_huft * FAR *tb; /* bits tree result */ 441234768Speterz_streamp z; /* for zfree function */ 441328415Speter{ 441428415Speter int r; 441528415Speter 441628415Speter r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z); 441728415Speter if (r == Z_DATA_ERROR) 441834768Speter z->msg = (char*)"oversubscribed dynamic bit lengths tree"; 441934768Speter else if (r == Z_BUF_ERROR || *bb == 0) 442028415Speter { 442128415Speter inflate_trees_free(*tb, z); 442234768Speter z->msg = (char*)"incomplete dynamic bit lengths tree"; 442328415Speter r = Z_DATA_ERROR; 442428415Speter } 442528415Speter return r; 442628415Speter} 442728415Speter 442828415Speter 442934768Speterint inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z) 443028415SpeteruInt nl; /* number of literal/length codes */ 443128415SpeteruInt nd; /* number of distance codes */ 443228415SpeteruIntf *c; /* that many (total) code lengths */ 443328415SpeteruIntf *bl; /* literal desired/actual bit depth */ 443428415SpeteruIntf *bd; /* distance desired/actual bit depth */ 443528415Speterinflate_huft * FAR *tl; /* literal/length tree result */ 443628415Speterinflate_huft * FAR *td; /* distance tree result */ 443734768Speterz_streamp z; /* for zfree function */ 443828415Speter{ 443928415Speter int r; 444028415Speter 444128415Speter /* build literal/length tree */ 444234768Speter r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z); 444334768Speter if (r != Z_OK || *bl == 0) 444428415Speter { 444528415Speter if (r == Z_DATA_ERROR) 444634768Speter z->msg = (char*)"oversubscribed literal/length tree"; 444734768Speter else if (r != Z_MEM_ERROR) 444828415Speter { 444928415Speter inflate_trees_free(*tl, z); 445034768Speter z->msg = (char*)"incomplete literal/length tree"; 445128415Speter r = Z_DATA_ERROR; 445228415Speter } 445328415Speter return r; 445428415Speter } 445528415Speter 445628415Speter /* build distance tree */ 445734768Speter r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z); 445834768Speter if (r != Z_OK || (*bd == 0 && nl > 257)) 445928415Speter { 446028415Speter if (r == Z_DATA_ERROR) 446134768Speter z->msg = (char*)"oversubscribed distance tree"; 446228415Speter else if (r == Z_BUF_ERROR) { 446328415Speter#ifdef PKZIP_BUG_WORKAROUND 446428415Speter r = Z_OK; 446528415Speter } 446628415Speter#else 446728415Speter inflate_trees_free(*td, z); 446834768Speter z->msg = (char*)"incomplete distance tree"; 446928415Speter r = Z_DATA_ERROR; 447028415Speter } 447134768Speter else if (r != Z_MEM_ERROR) 447234768Speter { 447334768Speter z->msg = (char*)"empty distance tree with lengths"; 447434768Speter r = Z_DATA_ERROR; 447534768Speter } 447628415Speter inflate_trees_free(*tl, z); 447728415Speter return r; 447828415Speter#endif 447928415Speter } 448028415Speter 448128415Speter /* done */ 448228415Speter return Z_OK; 448328415Speter} 448428415Speter 448528415Speter 448628415Speter/* build fixed tables only once--keep them here */ 448728415Speterlocal int fixed_built = 0; 448828415Speter#define FIXEDH 530 /* number of hufts used by fixed tables */ 448928415Speterlocal inflate_huft fixed_mem[FIXEDH]; 449028415Speterlocal uInt fixed_bl; 449128415Speterlocal uInt fixed_bd; 449228415Speterlocal inflate_huft *fixed_tl; 449328415Speterlocal inflate_huft *fixed_td; 449428415Speter 449528415Speter 449628415Speterlocal voidpf falloc(q, n, s) 449734768Spetervoidpf q; /* opaque pointer */ 449828415SpeteruInt n; /* number of items */ 449928415SpeteruInt s; /* size of item */ 450028415Speter{ 450134768Speter Assert(s == sizeof(inflate_huft) && n <= *(intf *)q, 450228415Speter "inflate_trees falloc overflow"); 450334768Speter *(intf *)q -= n+s-s; /* s-s to avoid warning */ 450434768Speter return (voidpf)(fixed_mem + *(intf *)q); 450528415Speter} 450628415Speter 450728415Speter 450834768Speterint inflate_trees_fixed(bl, bd, tl, td) 450928415SpeteruIntf *bl; /* literal desired/actual bit depth */ 451028415SpeteruIntf *bd; /* distance desired/actual bit depth */ 451128415Speterinflate_huft * FAR *tl; /* literal/length tree result */ 451228415Speterinflate_huft * FAR *td; /* distance tree result */ 451328415Speter{ 451434768Speter /* build fixed tables if not already (multiple overlapped executions ok) */ 451528415Speter if (!fixed_built) 451628415Speter { 451728415Speter int k; /* temporary variable */ 451828415Speter unsigned c[288]; /* length list for huft_build */ 451928415Speter z_stream z; /* for falloc function */ 452034768Speter int f = FIXEDH; /* number of hufts left in fixed_mem */ 452128415Speter 452228415Speter /* set up fake z_stream for memory routines */ 452328415Speter z.zalloc = falloc; 452434768Speter z.zfree = Z_NULL; 452534768Speter z.opaque = (voidpf)&f; 452628415Speter 452728415Speter /* literal table */ 452828415Speter for (k = 0; k < 144; k++) 452928415Speter c[k] = 8; 453028415Speter for (; k < 256; k++) 453128415Speter c[k] = 9; 453228415Speter for (; k < 280; k++) 453328415Speter c[k] = 7; 453428415Speter for (; k < 288; k++) 453528415Speter c[k] = 8; 453628415Speter fixed_bl = 7; 453728415Speter huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z); 453828415Speter 453928415Speter /* distance table */ 454028415Speter for (k = 0; k < 30; k++) 454128415Speter c[k] = 5; 454228415Speter fixed_bd = 5; 454328415Speter huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z); 454428415Speter 454528415Speter /* done */ 454634768Speter Assert(f == 0, "invalid build of fixed tables"); 454728415Speter fixed_built = 1; 454828415Speter } 454928415Speter *bl = fixed_bl; 455028415Speter *bd = fixed_bd; 455128415Speter *tl = fixed_tl; 455228415Speter *td = fixed_td; 455328415Speter return Z_OK; 455428415Speter} 455528415Speter 455628415Speter 455734768Speterint inflate_trees_free(t, z) 455828415Speterinflate_huft *t; /* table to free */ 455934768Speterz_streamp z; /* for zfree function */ 456028415Speter/* Free the malloc'ed tables built by huft_build(), which makes a linked 456128415Speter list of the tables it made, with the links in a dummy first entry of 456228415Speter each table. */ 456328415Speter{ 4564331643Sdim inflate_huft *p, *q, *r; 456528415Speter 456634768Speter /* Reverse linked list */ 456734768Speter p = Z_NULL; 456834768Speter q = t; 456934768Speter while (q != Z_NULL) 457034768Speter { 457134768Speter r = (q - 1)->next; 457234768Speter (q - 1)->next = p; 457334768Speter p = q; 457434768Speter q = r; 457534768Speter } 457628415Speter /* Go through linked list, freeing from the malloced (t[-1]) address. */ 457728415Speter while (p != Z_NULL) 457828415Speter { 457928415Speter q = (--p)->next; 458034768Speter ZFREE(z,p); 458128415Speter p = q; 458228415Speter } 458328415Speter return Z_OK; 458428415Speter} 458534768Speter/* --- inftrees.c */ 458628415Speter 458734768Speter/* +++ infcodes.c */ 458828415Speter/* infcodes.c -- process literals and length/distance pairs 458934768Speter * Copyright (C) 1995-1996 Mark Adler 459028415Speter * For conditions of distribution and use, see copyright notice in zlib.h 459128415Speter */ 459228415Speter 459334768Speter/* #include "zutil.h" */ 459434768Speter/* #include "inftrees.h" */ 459534768Speter/* #include "infblock.h" */ 459634768Speter/* #include "infcodes.h" */ 459734768Speter/* #include "infutil.h" */ 459834768Speter 459934768Speter/* +++ inffast.h */ 460034768Speter/* inffast.h -- header to use inffast.c 460134768Speter * Copyright (C) 1995-1996 Mark Adler 460234768Speter * For conditions of distribution and use, see copyright notice in zlib.h 460334768Speter */ 460434768Speter 460534768Speter/* WARNING: this file should *not* be used by applications. It is 460634768Speter part of the implementation of the compression library and is 460734768Speter subject to change. Applications should only use zlib.h. 460834768Speter */ 460934768Speter 461034768Speterextern int inflate_fast OF(( 461134768Speter uInt, 461234768Speter uInt, 461334768Speter inflate_huft *, 461434768Speter inflate_huft *, 461534768Speter inflate_blocks_statef *, 461634768Speter z_streamp )); 461734768Speter/* --- inffast.h */ 461834768Speter 461928415Speter/* simplify the use of the inflate_huft type with some defines */ 462028415Speter#define base more.Base 462128415Speter#define next more.Next 462228415Speter#define exop word.what.Exop 462328415Speter#define bits word.what.Bits 462428415Speter 462528415Speter/* inflate codes private state */ 462628415Speterstruct inflate_codes_state { 462728415Speter 462828415Speter /* mode */ 462928415Speter enum { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 463028415Speter START, /* x: set up for LEN */ 463128415Speter LEN, /* i: get length/literal/eob next */ 463228415Speter LENEXT, /* i: getting length extra (have base) */ 463328415Speter DIST, /* i: get distance next */ 463428415Speter DISTEXT, /* i: getting distance extra */ 463528415Speter COPY, /* o: copying bytes in window, waiting for space */ 463628415Speter LIT, /* o: got literal, waiting for output space */ 463728415Speter WASH, /* o: got eob, possibly still output waiting */ 463828415Speter END, /* x: got eob and all data flushed */ 463928415Speter BADCODE} /* x: got error */ 464028415Speter mode; /* current inflate_codes mode */ 464128415Speter 464228415Speter /* mode dependent information */ 464328415Speter uInt len; 464428415Speter union { 464528415Speter struct { 464628415Speter inflate_huft *tree; /* pointer into tree */ 464728415Speter uInt need; /* bits needed */ 464828415Speter } code; /* if LEN or DIST, where in tree */ 464928415Speter uInt lit; /* if LIT, literal */ 465028415Speter struct { 465128415Speter uInt get; /* bits to get for extra */ 465228415Speter uInt dist; /* distance back to copy from */ 465328415Speter } copy; /* if EXT or COPY, where and how much */ 465428415Speter } sub; /* submode */ 465528415Speter 465628415Speter /* mode independent information */ 465728415Speter Byte lbits; /* ltree bits decoded per branch */ 465828415Speter Byte dbits; /* dtree bits decoder per branch */ 465928415Speter inflate_huft *ltree; /* literal/length/eob tree */ 466028415Speter inflate_huft *dtree; /* distance tree */ 466128415Speter 466228415Speter}; 466328415Speter 466428415Speter 466534768Speterinflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z) 466628415SpeteruInt bl, bd; 466734768Speterinflate_huft *tl; 466834768Speterinflate_huft *td; /* need separate declaration for Borland C++ */ 466934768Speterz_streamp z; 467028415Speter{ 467128415Speter inflate_codes_statef *c; 467228415Speter 467328415Speter if ((c = (inflate_codes_statef *) 467428415Speter ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL) 467528415Speter { 467628415Speter c->mode = START; 467728415Speter c->lbits = (Byte)bl; 467828415Speter c->dbits = (Byte)bd; 467928415Speter c->ltree = tl; 468028415Speter c->dtree = td; 468128415Speter Tracev((stderr, "inflate: codes new\n")); 468228415Speter } 468328415Speter return c; 468428415Speter} 468528415Speter 468628415Speter 468734768Speterint inflate_codes(s, z, r) 468828415Speterinflate_blocks_statef *s; 468934768Speterz_streamp z; 469028415Speterint r; 469128415Speter{ 469228415Speter uInt j; /* temporary storage */ 469328415Speter inflate_huft *t; /* temporary pointer */ 469428415Speter uInt e; /* extra bits or operation */ 469528415Speter uLong b; /* bit buffer */ 469628415Speter uInt k; /* bits in bit buffer */ 469728415Speter Bytef *p; /* input data pointer */ 469828415Speter uInt n; /* bytes available there */ 469928415Speter Bytef *q; /* output window write pointer */ 470028415Speter uInt m; /* bytes to end of window or read pointer */ 470128415Speter Bytef *f; /* pointer to copy strings from */ 470228415Speter inflate_codes_statef *c = s->sub.decode.codes; /* codes state */ 470328415Speter 470428415Speter /* copy input/output information to locals (UPDATE macro restores) */ 470528415Speter LOAD 470628415Speter 470728415Speter /* process input and output based on current state */ 470828415Speter while (1) switch (c->mode) 470928415Speter { /* waiting for "i:"=input, "o:"=output, "x:"=nothing */ 471028415Speter case START: /* x: set up for LEN */ 471128415Speter#ifndef SLOW 471228415Speter if (m >= 258 && n >= 10) 471328415Speter { 471428415Speter UPDATE 471528415Speter r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z); 471628415Speter LOAD 471728415Speter if (r != Z_OK) 471828415Speter { 471928415Speter c->mode = r == Z_STREAM_END ? WASH : BADCODE; 472028415Speter break; 472128415Speter } 472228415Speter } 472328415Speter#endif /* !SLOW */ 472428415Speter c->sub.code.need = c->lbits; 472528415Speter c->sub.code.tree = c->ltree; 472628415Speter c->mode = LEN; 472728415Speter case LEN: /* i: get length/literal/eob next */ 472828415Speter j = c->sub.code.need; 472928415Speter NEEDBITS(j) 473028415Speter t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 473128415Speter DUMPBITS(t->bits) 473228415Speter e = (uInt)(t->exop); 473328415Speter if (e == 0) /* literal */ 473428415Speter { 473528415Speter c->sub.lit = t->base; 473628415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 473728415Speter "inflate: literal '%c'\n" : 473828415Speter "inflate: literal 0x%02x\n", t->base)); 473928415Speter c->mode = LIT; 474028415Speter break; 474128415Speter } 474228415Speter if (e & 16) /* length */ 474328415Speter { 474428415Speter c->sub.copy.get = e & 15; 474528415Speter c->len = t->base; 474628415Speter c->mode = LENEXT; 474728415Speter break; 474828415Speter } 474928415Speter if ((e & 64) == 0) /* next table */ 475028415Speter { 475128415Speter c->sub.code.need = e; 475228415Speter c->sub.code.tree = t->next; 475328415Speter break; 475428415Speter } 475528415Speter if (e & 32) /* end of block */ 475628415Speter { 475728415Speter Tracevv((stderr, "inflate: end of block\n")); 475828415Speter c->mode = WASH; 475928415Speter break; 476028415Speter } 476128415Speter c->mode = BADCODE; /* invalid code */ 476234768Speter z->msg = (char*)"invalid literal/length code"; 476328415Speter r = Z_DATA_ERROR; 476428415Speter LEAVE 476528415Speter case LENEXT: /* i: getting length extra (have base) */ 476628415Speter j = c->sub.copy.get; 476728415Speter NEEDBITS(j) 476828415Speter c->len += (uInt)b & inflate_mask[j]; 476928415Speter DUMPBITS(j) 477028415Speter c->sub.code.need = c->dbits; 477128415Speter c->sub.code.tree = c->dtree; 477228415Speter Tracevv((stderr, "inflate: length %u\n", c->len)); 477328415Speter c->mode = DIST; 477428415Speter case DIST: /* i: get distance next */ 477528415Speter j = c->sub.code.need; 477628415Speter NEEDBITS(j) 477728415Speter t = c->sub.code.tree + ((uInt)b & inflate_mask[j]); 477828415Speter DUMPBITS(t->bits) 477928415Speter e = (uInt)(t->exop); 478028415Speter if (e & 16) /* distance */ 478128415Speter { 478228415Speter c->sub.copy.get = e & 15; 478328415Speter c->sub.copy.dist = t->base; 478428415Speter c->mode = DISTEXT; 478528415Speter break; 478628415Speter } 478728415Speter if ((e & 64) == 0) /* next table */ 478828415Speter { 478928415Speter c->sub.code.need = e; 479028415Speter c->sub.code.tree = t->next; 479128415Speter break; 479228415Speter } 479328415Speter c->mode = BADCODE; /* invalid code */ 479434768Speter z->msg = (char*)"invalid distance code"; 479528415Speter r = Z_DATA_ERROR; 479628415Speter LEAVE 479728415Speter case DISTEXT: /* i: getting distance extra */ 479828415Speter j = c->sub.copy.get; 479928415Speter NEEDBITS(j) 480028415Speter c->sub.copy.dist += (uInt)b & inflate_mask[j]; 480128415Speter DUMPBITS(j) 480228415Speter Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist)); 480328415Speter c->mode = COPY; 480428415Speter case COPY: /* o: copying bytes in window, waiting for space */ 480528415Speter#ifndef __TURBOC__ /* Turbo C bug for following expression */ 480628415Speter f = (uInt)(q - s->window) < c->sub.copy.dist ? 480728415Speter s->end - (c->sub.copy.dist - (q - s->window)) : 480828415Speter q - c->sub.copy.dist; 480928415Speter#else 481028415Speter f = q - c->sub.copy.dist; 481128415Speter if ((uInt)(q - s->window) < c->sub.copy.dist) 481234768Speter f = s->end - (c->sub.copy.dist - (uInt)(q - s->window)); 481328415Speter#endif 481428415Speter while (c->len) 481528415Speter { 481628415Speter NEEDOUT 481728415Speter OUTBYTE(*f++) 481828415Speter if (f == s->end) 481928415Speter f = s->window; 482028415Speter c->len--; 482128415Speter } 482228415Speter c->mode = START; 482328415Speter break; 482428415Speter case LIT: /* o: got literal, waiting for output space */ 482528415Speter NEEDOUT 482628415Speter OUTBYTE(c->sub.lit) 482728415Speter c->mode = START; 482828415Speter break; 482928415Speter case WASH: /* o: got eob, possibly more output */ 483028415Speter FLUSH 483128415Speter if (s->read != s->write) 483228415Speter LEAVE 483328415Speter c->mode = END; 483428415Speter case END: 483528415Speter r = Z_STREAM_END; 483628415Speter LEAVE 483728415Speter case BADCODE: /* x: got error */ 483828415Speter r = Z_DATA_ERROR; 483928415Speter LEAVE 484028415Speter default: 484128415Speter r = Z_STREAM_ERROR; 484228415Speter LEAVE 484328415Speter } 484428415Speter} 484528415Speter 484628415Speter 484734768Spetervoid inflate_codes_free(c, z) 484828415Speterinflate_codes_statef *c; 484934768Speterz_streamp z; 485028415Speter{ 485134768Speter ZFREE(z, c); 485228415Speter Tracev((stderr, "inflate: codes free\n")); 485328415Speter} 485434768Speter/* --- infcodes.c */ 485528415Speter 485634768Speter/* +++ infutil.c */ 485728415Speter/* inflate_util.c -- data and routines common to blocks and codes 485834768Speter * Copyright (C) 1995-1996 Mark Adler 485928415Speter * For conditions of distribution and use, see copyright notice in zlib.h 486028415Speter */ 486128415Speter 486234768Speter/* #include "zutil.h" */ 486334768Speter/* #include "infblock.h" */ 486434768Speter/* #include "inftrees.h" */ 486534768Speter/* #include "infcodes.h" */ 486634768Speter/* #include "infutil.h" */ 486734768Speter 486834768Speter#ifndef NO_DUMMY_DECL 486934768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 487034768Speter#endif 487134768Speter 487234768Speter/* And'ing with mask[n] masks the lower n bits */ 487334768SpeteruInt inflate_mask[17] = { 487434768Speter 0x0000, 487534768Speter 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff, 487634768Speter 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff 487734768Speter}; 487834768Speter 487934768Speter 488028415Speter/* copy as much as possible from the sliding window to the output area */ 488134768Speterint inflate_flush(s, z, r) 488228415Speterinflate_blocks_statef *s; 488334768Speterz_streamp z; 488428415Speterint r; 488528415Speter{ 488628415Speter uInt n; 488734768Speter Bytef *p; 488834768Speter Bytef *q; 488928415Speter 489028415Speter /* local copies of source and destination pointers */ 489128415Speter p = z->next_out; 489228415Speter q = s->read; 489328415Speter 489428415Speter /* compute number of bytes to copy as far as end of window */ 489528415Speter n = (uInt)((q <= s->write ? s->write : s->end) - q); 489628415Speter if (n > z->avail_out) n = z->avail_out; 489728415Speter if (n && r == Z_BUF_ERROR) r = Z_OK; 489828415Speter 489928415Speter /* update counters */ 490028415Speter z->avail_out -= n; 490128415Speter z->total_out += n; 490228415Speter 490328415Speter /* update check information */ 490428415Speter if (s->checkfn != Z_NULL) 490534768Speter z->adler = s->check = (*s->checkfn)(s->check, q, n); 490628415Speter 490728415Speter /* copy as far as end of window */ 490834768Speter if (p != Z_NULL) { 490928415Speter zmemcpy(p, q, n); 491028415Speter p += n; 491128415Speter } 491228415Speter q += n; 491328415Speter 491428415Speter /* see if more to copy at beginning of window */ 491528415Speter if (q == s->end) 491628415Speter { 491728415Speter /* wrap pointers */ 491828415Speter q = s->window; 491928415Speter if (s->write == s->end) 492028415Speter s->write = s->window; 492128415Speter 492228415Speter /* compute bytes to copy */ 492328415Speter n = (uInt)(s->write - q); 492428415Speter if (n > z->avail_out) n = z->avail_out; 492528415Speter if (n && r == Z_BUF_ERROR) r = Z_OK; 492628415Speter 492728415Speter /* update counters */ 492828415Speter z->avail_out -= n; 492928415Speter z->total_out += n; 493028415Speter 493128415Speter /* update check information */ 493228415Speter if (s->checkfn != Z_NULL) 493334768Speter z->adler = s->check = (*s->checkfn)(s->check, q, n); 493428415Speter 493528415Speter /* copy */ 493634768Speter if (p != Z_NULL) { 493728415Speter zmemcpy(p, q, n); 493828415Speter p += n; 493928415Speter } 494028415Speter q += n; 494128415Speter } 494228415Speter 494328415Speter /* update pointers */ 494428415Speter z->next_out = p; 494528415Speter s->read = q; 494628415Speter 494728415Speter /* done */ 494828415Speter return r; 494928415Speter} 495034768Speter/* --- infutil.c */ 495128415Speter 495234768Speter/* +++ inffast.c */ 495328415Speter/* inffast.c -- process literals and length/distance pairs fast 495434768Speter * Copyright (C) 1995-1996 Mark Adler 495528415Speter * For conditions of distribution and use, see copyright notice in zlib.h 495628415Speter */ 495728415Speter 495834768Speter/* #include "zutil.h" */ 495934768Speter/* #include "inftrees.h" */ 496034768Speter/* #include "infblock.h" */ 496134768Speter/* #include "infcodes.h" */ 496234768Speter/* #include "infutil.h" */ 496334768Speter/* #include "inffast.h" */ 496434768Speter 496534768Speter#ifndef NO_DUMMY_DECL 496634768Speterstruct inflate_codes_state {int dummy;}; /* for buggy compilers */ 496734768Speter#endif 496834768Speter 496928415Speter/* simplify the use of the inflate_huft type with some defines */ 497028415Speter#define base more.Base 497128415Speter#define next more.Next 497228415Speter#define exop word.what.Exop 497328415Speter#define bits word.what.Bits 497428415Speter 497528415Speter/* macros for bit input with no checking and for returning unused bytes */ 497628415Speter#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}} 497728415Speter#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;} 497828415Speter 497928415Speter/* Called with number of bytes left to write in window at least 258 498028415Speter (the maximum string length) and number of input bytes available 498128415Speter at least ten. The ten bytes are six bytes for the longest length/ 498228415Speter distance pair plus four bytes for overloading the bit buffer. */ 498328415Speter 498434768Speterint inflate_fast(bl, bd, tl, td, s, z) 498528415SpeteruInt bl, bd; 498634768Speterinflate_huft *tl; 498734768Speterinflate_huft *td; /* need separate declaration for Borland C++ */ 498828415Speterinflate_blocks_statef *s; 498934768Speterz_streamp z; 499028415Speter{ 499128415Speter inflate_huft *t; /* temporary pointer */ 499228415Speter uInt e; /* extra bits or operation */ 499328415Speter uLong b; /* bit buffer */ 499428415Speter uInt k; /* bits in bit buffer */ 499528415Speter Bytef *p; /* input data pointer */ 499628415Speter uInt n; /* bytes available there */ 499728415Speter Bytef *q; /* output window write pointer */ 499828415Speter uInt m; /* bytes to end of window or read pointer */ 499928415Speter uInt ml; /* mask for literal/length tree */ 500028415Speter uInt md; /* mask for distance tree */ 500128415Speter uInt c; /* bytes to copy */ 500228415Speter uInt d; /* distance back to copy from */ 500328415Speter Bytef *r; /* copy source pointer */ 500428415Speter 500528415Speter /* load input, output, bit values */ 500628415Speter LOAD 500728415Speter 500828415Speter /* initialize masks */ 500928415Speter ml = inflate_mask[bl]; 501028415Speter md = inflate_mask[bd]; 501128415Speter 501228415Speter /* do until not enough input or output space for fast loop */ 501328415Speter do { /* assume called with m >= 258 && n >= 10 */ 501428415Speter /* get literal/length code */ 501528415Speter GRABBITS(20) /* max bits for literal/length code */ 501628415Speter if ((e = (t = tl + ((uInt)b & ml))->exop) == 0) 501728415Speter { 501828415Speter DUMPBITS(t->bits) 501928415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 502028415Speter "inflate: * literal '%c'\n" : 502128415Speter "inflate: * literal 0x%02x\n", t->base)); 502228415Speter *q++ = (Byte)t->base; 502328415Speter m--; 502428415Speter continue; 502528415Speter } 502628415Speter do { 502728415Speter DUMPBITS(t->bits) 502828415Speter if (e & 16) 502928415Speter { 503028415Speter /* get extra bits for length */ 503128415Speter e &= 15; 503228415Speter c = t->base + ((uInt)b & inflate_mask[e]); 503328415Speter DUMPBITS(e) 503428415Speter Tracevv((stderr, "inflate: * length %u\n", c)); 503528415Speter 503628415Speter /* decode distance base of block to copy */ 503728415Speter GRABBITS(15); /* max bits for distance code */ 503828415Speter e = (t = td + ((uInt)b & md))->exop; 503928415Speter do { 504028415Speter DUMPBITS(t->bits) 504128415Speter if (e & 16) 504228415Speter { 504328415Speter /* get extra bits to add to distance base */ 504428415Speter e &= 15; 504528415Speter GRABBITS(e) /* get extra bits (up to 13) */ 504628415Speter d = t->base + ((uInt)b & inflate_mask[e]); 504728415Speter DUMPBITS(e) 504828415Speter Tracevv((stderr, "inflate: * distance %u\n", d)); 504928415Speter 505028415Speter /* do the copy */ 505128415Speter m -= c; 505228415Speter if ((uInt)(q - s->window) >= d) /* offset before dest */ 505328415Speter { /* just copy */ 505428415Speter r = q - d; 505528415Speter *q++ = *r++; c--; /* minimum count is three, */ 505628415Speter *q++ = *r++; c--; /* so unroll loop a little */ 505728415Speter } 505828415Speter else /* else offset after destination */ 505928415Speter { 506034768Speter e = d - (uInt)(q - s->window); /* bytes from offset to end */ 506128415Speter r = s->end - e; /* pointer to offset */ 506228415Speter if (c > e) /* if source crosses, */ 506328415Speter { 506428415Speter c -= e; /* copy to end of window */ 506528415Speter do { 506628415Speter *q++ = *r++; 506728415Speter } while (--e); 506828415Speter r = s->window; /* copy rest from start of window */ 506928415Speter } 507028415Speter } 507128415Speter do { /* copy all or what's left */ 507228415Speter *q++ = *r++; 507328415Speter } while (--c); 507428415Speter break; 507528415Speter } 507628415Speter else if ((e & 64) == 0) 507728415Speter e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop; 507828415Speter else 507928415Speter { 508034768Speter z->msg = (char*)"invalid distance code"; 508128415Speter UNGRAB 508228415Speter UPDATE 508328415Speter return Z_DATA_ERROR; 508428415Speter } 508528415Speter } while (1); 508628415Speter break; 508728415Speter } 508828415Speter if ((e & 64) == 0) 508928415Speter { 509028415Speter if ((e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop) == 0) 509128415Speter { 509228415Speter DUMPBITS(t->bits) 509328415Speter Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ? 509428415Speter "inflate: * literal '%c'\n" : 509528415Speter "inflate: * literal 0x%02x\n", t->base)); 509628415Speter *q++ = (Byte)t->base; 509728415Speter m--; 509828415Speter break; 509928415Speter } 510028415Speter } 510128415Speter else if (e & 32) 510228415Speter { 510328415Speter Tracevv((stderr, "inflate: * end of block\n")); 510428415Speter UNGRAB 510528415Speter UPDATE 510628415Speter return Z_STREAM_END; 510728415Speter } 510828415Speter else 510928415Speter { 511034768Speter z->msg = (char*)"invalid literal/length code"; 511128415Speter UNGRAB 511228415Speter UPDATE 511328415Speter return Z_DATA_ERROR; 511428415Speter } 511528415Speter } while (1); 511628415Speter } while (m >= 258 && n >= 10); 511728415Speter 511828415Speter /* not enough input or output--restore pointers and return */ 511928415Speter UNGRAB 512028415Speter UPDATE 512128415Speter return Z_OK; 512228415Speter} 512334768Speter/* --- inffast.c */ 512428415Speter 512534768Speter/* +++ zutil.c */ 512628415Speter/* zutil.c -- target dependent utility functions for the compression library 512734768Speter * Copyright (C) 1995-1996 Jean-loup Gailly. 512828415Speter * For conditions of distribution and use, see copyright notice in zlib.h 512928415Speter */ 513028415Speter 513134768Speter/* From: zutil.c,v 1.17 1996/07/24 13:41:12 me Exp $ */ 513228415Speter 513334768Speter#ifdef DEBUG_ZLIB 513434768Speter#include <stdio.h> 513534768Speter#endif 513628415Speter 513734768Speter/* #include "zutil.h" */ 513834768Speter 513934768Speter#ifndef NO_DUMMY_DECL 514034768Speterstruct internal_state {int dummy;}; /* for buggy compilers */ 514134768Speter#endif 514234768Speter 514334768Speter#ifndef STDC 514434768Speterextern void exit OF((int)); 514534768Speter#endif 514634768Speter 514734768Speterstatic const char *z_errmsg[10] = { 514834768Speter"need dictionary", /* Z_NEED_DICT 2 */ 514934768Speter"stream end", /* Z_STREAM_END 1 */ 515034768Speter"", /* Z_OK 0 */ 515134768Speter"file error", /* Z_ERRNO (-1) */ 515234768Speter"stream error", /* Z_STREAM_ERROR (-2) */ 515334768Speter"data error", /* Z_DATA_ERROR (-3) */ 515434768Speter"insufficient memory", /* Z_MEM_ERROR (-4) */ 515534768Speter"buffer error", /* Z_BUF_ERROR (-5) */ 515634768Speter"incompatible version",/* Z_VERSION_ERROR (-6) */ 515728415Speter""}; 515828415Speter 515928415Speter 516034768Speterconst char *zlibVersion() 516134768Speter{ 516234768Speter return ZLIB_VERSION; 516334768Speter} 516434768Speter 516534768Speter#ifdef DEBUG_ZLIB 516634768Spetervoid z_error (m) 516734768Speter char *m; 516834768Speter{ 516934768Speter fprintf(stderr, "%s\n", m); 517034768Speter exit(1); 517134768Speter} 517234768Speter#endif 517334768Speter 517434768Speter#ifndef HAVE_MEMCPY 517534768Speter 517634768Spetervoid zmemcpy(dest, source, len) 517734768Speter Bytef* dest; 517834768Speter Bytef* source; 517934768Speter uInt len; 518034768Speter{ 518134768Speter if (len == 0) return; 518234768Speter do { 518334768Speter *dest++ = *source++; /* ??? to be unrolled */ 518434768Speter } while (--len != 0); 518534768Speter} 518634768Speter 518734768Speterint zmemcmp(s1, s2, len) 518834768Speter Bytef* s1; 518934768Speter Bytef* s2; 519034768Speter uInt len; 519134768Speter{ 519234768Speter uInt j; 519334768Speter 519434768Speter for (j = 0; j < len; j++) { 519534768Speter if (s1[j] != s2[j]) return 2*(s1[j] > s2[j])-1; 519634768Speter } 519734768Speter return 0; 519834768Speter} 519934768Speter 520034768Spetervoid zmemzero(dest, len) 520134768Speter Bytef* dest; 520234768Speter uInt len; 520334768Speter{ 520434768Speter if (len == 0) return; 520534768Speter do { 520634768Speter *dest++ = 0; /* ??? to be unrolled */ 520734768Speter } while (--len != 0); 520834768Speter} 520934768Speter#endif 521034768Speter 521134768Speter#ifdef __TURBOC__ 521234768Speter#if (defined( __BORLANDC__) || !defined(SMALL_MEDIUM)) && !defined(__32BIT__) 521334768Speter/* Small and medium model in Turbo C are for now limited to near allocation 521434768Speter * with reduced MAX_WBITS and MAX_MEM_LEVEL 521534768Speter */ 521634768Speter# define MY_ZCALLOC 521734768Speter 521834768Speter/* Turbo C malloc() does not allow dynamic allocation of 64K bytes 521934768Speter * and farmalloc(64K) returns a pointer with an offset of 8, so we 522034768Speter * must fix the pointer. Warning: the pointer must be put back to its 522134768Speter * original form in order to free it, use zcfree(). 522234768Speter */ 522334768Speter 522434768Speter#define MAX_PTR 10 522534768Speter/* 10*64K = 640K */ 522634768Speter 522734768Speterlocal int next_ptr = 0; 522834768Speter 522934768Spetertypedef struct ptr_table_s { 523034768Speter voidpf org_ptr; 523134768Speter voidpf new_ptr; 523234768Speter} ptr_table; 523334768Speter 523434768Speterlocal ptr_table table[MAX_PTR]; 523534768Speter/* This table is used to remember the original form of pointers 523634768Speter * to large buffers (64K). Such pointers are normalized with a zero offset. 523734768Speter * Since MSDOS is not a preemptive multitasking OS, this table is not 523834768Speter * protected from concurrent access. This hack doesn't work anyway on 523934768Speter * a protected system like OS/2. Use Microsoft C instead. 524034768Speter */ 524134768Speter 524234768Spetervoidpf zcalloc (voidpf opaque, unsigned items, unsigned size) 524334768Speter{ 524434768Speter voidpf buf = opaque; /* just to make some compilers happy */ 524534768Speter ulg bsize = (ulg)items*size; 524634768Speter 524734768Speter /* If we allocate less than 65520 bytes, we assume that farmalloc 524834768Speter * will return a usable pointer which doesn't have to be normalized. 524934768Speter */ 525034768Speter if (bsize < 65520L) { 525134768Speter buf = farmalloc(bsize); 525234768Speter if (*(ush*)&buf != 0) return buf; 525334768Speter } else { 525434768Speter buf = farmalloc(bsize + 16L); 525534768Speter } 525634768Speter if (buf == NULL || next_ptr >= MAX_PTR) return NULL; 525734768Speter table[next_ptr].org_ptr = buf; 525834768Speter 525934768Speter /* Normalize the pointer to seg:0 */ 526034768Speter *((ush*)&buf+1) += ((ush)((uch*)buf-0) + 15) >> 4; 526134768Speter *(ush*)&buf = 0; 526234768Speter table[next_ptr++].new_ptr = buf; 526334768Speter return buf; 526434768Speter} 526534768Speter 526634768Spetervoid zcfree (voidpf opaque, voidpf ptr) 526734768Speter{ 526834768Speter int n; 526934768Speter if (*(ush*)&ptr != 0) { /* object < 64K */ 527034768Speter farfree(ptr); 527134768Speter return; 527234768Speter } 527334768Speter /* Find the original pointer */ 527434768Speter for (n = 0; n < next_ptr; n++) { 527534768Speter if (ptr != table[n].new_ptr) continue; 527634768Speter 527734768Speter farfree(table[n].org_ptr); 527834768Speter while (++n < next_ptr) { 527934768Speter table[n-1] = table[n]; 528034768Speter } 528134768Speter next_ptr--; 528234768Speter return; 528334768Speter } 528434768Speter ptr = opaque; /* just to make some compilers happy */ 528534768Speter Assert(0, "zcfree: ptr not found"); 528634768Speter} 528734768Speter#endif 528834768Speter#endif /* __TURBOC__ */ 528934768Speter 529034768Speter 529134768Speter#if defined(M_I86) && !defined(__32BIT__) 529234768Speter/* Microsoft C in 16-bit mode */ 529334768Speter 529434768Speter# define MY_ZCALLOC 529534768Speter 529634768Speter#if (!defined(_MSC_VER) || (_MSC_VER < 600)) 529734768Speter# define _halloc halloc 529834768Speter# define _hfree hfree 529934768Speter#endif 530034768Speter 530134768Spetervoidpf zcalloc (voidpf opaque, unsigned items, unsigned size) 530234768Speter{ 530334768Speter if (opaque) opaque = 0; /* to make compiler happy */ 530434768Speter return _halloc((long)items, size); 530534768Speter} 530634768Speter 530734768Spetervoid zcfree (voidpf opaque, voidpf ptr) 530834768Speter{ 530934768Speter if (opaque) opaque = 0; /* to make compiler happy */ 531034768Speter _hfree(ptr); 531134768Speter} 531234768Speter 531334768Speter#endif /* MSC */ 531434768Speter 531534768Speter 531634768Speter#ifndef MY_ZCALLOC /* Any system without a special alloc function */ 531734768Speter 531834768Speter#ifndef STDC 531934768Speterextern voidp calloc OF((uInt items, uInt size)); 532034768Speterextern void free OF((voidpf ptr)); 532134768Speter#endif 532234768Speter 532334768Spetervoidpf zcalloc (opaque, items, size) 532434768Speter voidpf opaque; 532534768Speter unsigned items; 532634768Speter unsigned size; 532734768Speter{ 532834768Speter if (opaque) items += size - size; /* make compiler happy */ 532934768Speter return (voidpf)calloc(items, size); 533034768Speter} 533134768Speter 533234768Spetervoid zcfree (opaque, ptr) 533334768Speter voidpf opaque; 533434768Speter voidpf ptr; 533534768Speter{ 533634768Speter free(ptr); 533734768Speter if (opaque) return; /* make compiler happy */ 533834768Speter} 533934768Speter 534034768Speter#endif /* MY_ZCALLOC */ 534134768Speter/* --- zutil.c */ 534234768Speter 534334768Speter/* +++ adler32.c */ 534428415Speter/* adler32.c -- compute the Adler-32 checksum of a data stream 534534768Speter * Copyright (C) 1995-1996 Mark Adler 534628415Speter * For conditions of distribution and use, see copyright notice in zlib.h 534728415Speter */ 534828415Speter 534934768Speter/* From: adler32.c,v 1.10 1996/05/22 11:52:18 me Exp $ */ 535028415Speter 535134768Speter/* #include "zlib.h" */ 535234768Speter 535328415Speter#define BASE 65521L /* largest prime smaller than 65536 */ 535428415Speter#define NMAX 5552 535528415Speter/* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 535628415Speter 5357106696Salfred#define DO1(buf,i) {s1 += buf[(i)]; s2 += s1;} 5358106696Salfred#define DO2(buf,i) DO1(buf,i); DO1(buf,(i)+1); 5359106696Salfred#define DO4(buf,i) DO2(buf,i); DO2(buf,(i)+2); 5360106696Salfred#define DO8(buf,i) DO4(buf,i); DO4(buf,(i)+4); 536134768Speter#define DO16(buf) DO8(buf,0); DO8(buf,8); 536228415Speter 536328415Speter/* ========================================================================= */ 536428415SpeteruLong adler32(adler, buf, len) 536528415Speter uLong adler; 536634768Speter const Bytef *buf; 536728415Speter uInt len; 536828415Speter{ 536928415Speter unsigned long s1 = adler & 0xffff; 537028415Speter unsigned long s2 = (adler >> 16) & 0xffff; 537128415Speter int k; 537228415Speter 537328415Speter if (buf == Z_NULL) return 1L; 537428415Speter 537528415Speter while (len > 0) { 537628415Speter k = len < NMAX ? len : NMAX; 537728415Speter len -= k; 537828415Speter while (k >= 16) { 537928415Speter DO16(buf); 538034768Speter buf += 16; 538128415Speter k -= 16; 538228415Speter } 538328415Speter if (k != 0) do { 538434768Speter s1 += *buf++; 538534768Speter s2 += s1; 538628415Speter } while (--k); 538728415Speter s1 %= BASE; 538828415Speter s2 %= BASE; 538928415Speter } 539028415Speter return (s2 << 16) | s1; 539128415Speter} 539234768Speter/* --- adler32.c */ 5393130799Smarkm 5394130799Smarkm#ifdef _KERNEL 5395130799Smarkmstatic int 5396130799Smarkmzlib_modevent(module_t mod, int type, void *unused) 5397130799Smarkm{ 5398130799Smarkm switch (type) { 5399130799Smarkm case MOD_LOAD: 5400130799Smarkm return 0; 5401130799Smarkm case MOD_UNLOAD: 5402130799Smarkm return 0; 5403130799Smarkm } 5404130799Smarkm return EINVAL; 5405130799Smarkm} 5406130799Smarkm 5407130799Smarkmstatic moduledata_t zlib_mod = { 5408130799Smarkm "zlib", 5409130799Smarkm zlib_modevent, 5410241394Skevlo 0 5411130799Smarkm}; 5412130799SmarkmDECLARE_MODULE(zlib, zlib_mod, SI_SUB_DRIVERS, SI_ORDER_FIRST); 5413130799SmarkmMODULE_VERSION(zlib, 1); 5414130799Smarkm#endif /* _KERNEL */ 5415