#define STDC
#define NO_DUMMY_DECL
#define NO_ZCFUNCS
#define MY_ZCALLOC
#ifndef _Z_UTIL_H
#define _Z_UTIL_H
#ifdef KERNEL
#include <libkern/zlib.h>
#else
#include "zlib.h"
#endif
#ifdef KERNEL
#include <sys/types.h>
#include <sys/time.h>
#include <sys/systm.h>
# define HAVE_MEMCPY
# define memcpy(d, s, n) bcopy((s), (d), (n))
# define memset(d, v, n) bzero((d), (n))
# define memcmp bcmp
#else
#if defined(__KERNEL__)
#include <linux/string.h>
#define HAVE_MEMCPY
#else
#ifdef STDC
# include <stddef.h>
# include <string.h>
# include <stdlib.h>
#endif
#ifdef NO_ERRNO_H
extern int errno;
#else
# include <errno.h>
#endif
#endif
#endif
typedef unsigned char uch;
typedef uch FAR uchf;
typedef unsigned short ush;
typedef ush FAR ushf;
typedef unsigned long ulg;
static const char *z_errmsg[10] = {
"need dictionary",
"stream end",
"",
"file error",
"stream error",
"data error",
"insufficient memory",
"buffer error",
"incompatible version",
""};
#define ERR_MSG(err) z_errmsg[Z_NEED_DICT-(err)]
#define ERR_RETURN(strm,err) \
return (strm->msg = (char*)ERR_MSG(err), (err))
#ifndef DEF_WBITS
# define DEF_WBITS MAX_WBITS
#endif
#if MAX_MEM_LEVEL >= 8
# define DEF_MEM_LEVEL 8
#else
# define DEF_MEM_LEVEL MAX_MEM_LEVEL
#endif
#define STORED_BLOCK 0
#define STATIC_TREES 1
#define DYN_TREES 2
#define MIN_MATCH 3
#define MAX_MATCH 258
#define PRESET_DICT 0x20
#ifdef MSDOS
# define OS_CODE 0x00
# if defined(__TURBOC__) || defined(__BORLANDC__)
# if(__STDC__ == 1) && (defined(__LARGE__) || defined(__COMPACT__))
void _Cdecl farfree( void *block );
void *_Cdecl farmalloc( unsigned long nbytes );
# else
# include <alloc.h>
# endif
# else
# include <malloc.h>
# endif
#endif
#ifdef OS2
# define OS_CODE 0x06
#endif
#ifdef WIN32
# define OS_CODE 0x0b
#endif
#if defined(VAXC) || defined(VMS)
# define OS_CODE 0x02
# define F_OPEN(name, mode) \
fopen((name), (mode), "mbc=60", "ctx=stm", "rfm=fix", "mrs=512")
#endif
#ifdef AMIGA
# define OS_CODE 0x01
#endif
#if defined(ATARI) || defined(atarist)
# define OS_CODE 0x05
#endif
#if defined(MACOS) || defined(TARGET_OS_MAC)
# define OS_CODE 0x07
# if defined(__MWERKS__) && __dest_os != __be_os && __dest_os != __win32_os
# include <unix.h>
# else
# ifndef fdopen
# define fdopen(fd,mode) NULL
# endif
# endif
#endif
#ifdef __50SERIES
# define OS_CODE 0x0F
#endif
#ifdef TOPS20
# define OS_CODE 0x0a
#endif
#if defined(_BEOS_) || defined(RISCOS)
# define fdopen(fd,mode) NULL
#endif
#if (defined(_MSC_VER) && (_MSC_VER > 600))
# define fdopen(fd,type) _fdopen(fd,type)
#endif
#ifndef OS_CODE
# define OS_CODE 0x03
#endif
#ifndef F_OPEN
# define F_OPEN(name, mode) fopen((name), (mode))
#endif
#ifdef HAVE_STRERROR
extern char *strerror OF((int));
# define zstrerror(errnum) strerror(errnum)
#else
# define zstrerror(errnum) ""
#endif
#if defined(pyr)
# define NO_MEMCPY
#endif
#if defined(SMALL_MEDIUM) && !defined(_MSC_VER) && !defined(__SC__)
# define NO_MEMCPY
#endif
#if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY)
# define HAVE_MEMCPY
#endif
#ifdef HAVE_MEMCPY
# ifdef SMALL_MEDIUM
# define zmemcpy _fmemcpy
# define zmemcmp _fmemcmp
# define zmemzero(dest, len) _fmemset(dest, 0, len)
# else
# define zmemcpy memcpy
# define zmemcmp memcmp
# define zmemzero(dest, len) memset(dest, 0, len)
# endif
#else
extern void zmemcpy OF((Bytef* dest, const Bytef* source, uInt len));
extern int zmemcmp OF((const Bytef* s1, const Bytef* s2, uInt len));
extern void zmemzero OF((Bytef* dest, uInt len));
#endif
#ifdef DEBUG_ZLIB
# include <stdio.h>
extern int z_verbose;
extern void z_error OF((char *m));
# define Assert(cond,msg) {if(!(cond)) z_error(msg);}
# define Trace(x) {if (z_verbose>=0) fprintf x ;}
# define Tracev(x) {if (z_verbose>0) fprintf x ;}
# define Tracevv(x) {if (z_verbose>1) fprintf x ;}
# define Tracec(c,x) {if (z_verbose>0 && (c)) fprintf x ;}
# define Tracecv(c,x) {if (z_verbose>1 && (c)) fprintf x ;}
#else
# define Assert(cond,msg) do {} while(0)
# define Trace(x) do {} while(0)
# define Tracev(x) do {} while(0)
# define Tracevv(x) do {} while(0)
# define Tracec(c,x) do {} while(0)
# define Tracecv(c,x) do {} while(0)
#endif
typedef uLong (ZEXPORT *check_func) OF((uLong check, const Bytef *buf,
uInt len));
voidpf zcalloc OF((voidpf opaque, unsigned items, unsigned size));
void zcfree OF((voidpf opaque, voidpf ptr));
#define ZALLOC(strm, items, size) \
(*((strm)->zalloc))((strm)->opaque, (items), (size))
#define ZFREE(strm, addr) (*((strm)->zfree))((strm)->opaque, (voidpf)(addr))
#define TRY_FREE(s, p) {if (p) ZFREE(s, p);}
#endif
#ifndef _DEFLATE_H
#define _DEFLATE_H
#define LENGTH_CODES 29
#define LITERALS 256
#define L_CODES (LITERALS+1+LENGTH_CODES)
#define D_CODES 30
#define BL_CODES 19
#define HEAP_SIZE (2*L_CODES+1)
#define MAX_BITS 15
#define INIT_STATE 42
#define BUSY_STATE 113
#define FINISH_STATE 666
typedef struct ct_data_s {
union {
ush freq;
ush code;
} fc;
union {
ush dad;
ush len;
} dl;
} FAR ct_data;
#define Freq fc.freq
#define Code fc.code
#define Dad dl.dad
#define Len dl.len
typedef struct static_tree_desc_s static_tree_desc;
typedef struct tree_desc_s {
ct_data *dyn_tree;
int max_code;
static_tree_desc *stat_desc;
} FAR tree_desc;
typedef ush Pos;
typedef Pos FAR Posf;
typedef unsigned IPos;
typedef struct deflate_state {
z_streamp strm;
int status;
Bytef *pending_buf;
ulg pending_buf_size;
Bytef *pending_out;
int pending;
int noheader;
Byte data_type;
Byte method;
int last_flush;
uInt w_size;
uInt w_bits;
uInt w_mask;
Bytef *window;
ulg window_size;
Posf *prev;
Posf *head;
uInt ins_h;
uInt hash_size;
uInt hash_bits;
uInt hash_mask;
uInt hash_shift;
long block_start;
uInt match_length;
IPos prev_match;
int match_available;
uInt strstart;
uInt match_start;
uInt lookahead;
uInt prev_length;
uInt max_chain_length;
uInt max_lazy_match;
# define max_insert_length max_lazy_match
int level;
int strategy;
uInt good_match;
int nice_match;
struct ct_data_s dyn_ltree[HEAP_SIZE];
struct ct_data_s dyn_dtree[2*D_CODES+1];
struct ct_data_s bl_tree[2*BL_CODES+1];
struct tree_desc_s l_desc;
struct tree_desc_s d_desc;
struct tree_desc_s bl_desc;
ush bl_count[MAX_BITS+1];
int heap[2*L_CODES+1];
int heap_len;
int heap_max;
uch depth[2*L_CODES+1];
uchf *l_buf;
uInt lit_bufsize;
uInt last_lit;
ushf *d_buf;
ulg opt_len;
ulg static_len;
uInt matches;
int last_eob_len;
#ifdef DEBUG_ZLIB
ulg compressed_len;
ulg bits_sent;
#endif
ush bi_buf;
int bi_valid;
} FAR deflate_state;
#define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
#define MAX_DIST(s) ((s)->w_size-MIN_LOOKAHEAD)
static void _tr_init OF((deflate_state *s));
static int _tr_tally OF((deflate_state *s, unsigned dist, unsigned lc));
static void _tr_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
int eof));
static void _tr_align OF((deflate_state *s));
static void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
int eof));
#define d_code(dist) \
((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])
#ifndef DEBUG_ZLIB
#if defined(GEN_TREES_H) || !defined(STDC)
extern uch _length_code[];
extern uch _dist_code[];
#else
extern const uch _length_code[];
extern const uch _dist_code[];
#endif
# define _tr_tally_lit(s, c, flush) \
{ uch cc = (c); \
s->d_buf[s->last_lit] = 0; \
s->l_buf[s->last_lit++] = cc; \
s->dyn_ltree[cc].Freq++; \
flush = (s->last_lit == s->lit_bufsize-1); \
}
# define _tr_tally_dist(s, distance, length, flush) \
{ uch len = (length); \
ush dist = (distance); \
s->d_buf[s->last_lit] = dist; \
s->l_buf[s->last_lit++] = len; \
dist--; \
s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
s->dyn_dtree[d_code(dist)].Freq++; \
flush = (s->last_lit == s->lit_bufsize-1); \
}
#else
# define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c)
# define _tr_tally_dist(s, distance, length, flush) \
flush = _tr_tally(s, distance, length)
#endif
#endif
const char deflate_copyright[] =
" deflate 1.1.4 Copyright 1995-2002 Jean-loup Gailly ";
typedef enum {
need_more,
block_done,
finish_started,
finish_done
} block_state;
typedef block_state (*compress_func) OF((deflate_state *s, int flush));
static void fill_window OF((deflate_state *s));
static block_state deflate_stored OF((deflate_state *s, int flush));
static block_state deflate_fast OF((deflate_state *s, int flush));
static block_state deflate_slow OF((deflate_state *s, int flush));
static void lm_init OF((deflate_state *s));
static void putShortMSB OF((deflate_state *s, uInt b));
static void flush_pending OF((z_streamp strm));
static int read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
#ifdef ASMV
void match_init OF((void));
uInt longest_match OF((deflate_state *s, IPos cur_match));
#else
static uInt longest_match OF((deflate_state *s, IPos cur_match));
#endif
#ifdef DEBUG_ZLIB
static void check_match OF((deflate_state *s, IPos start, IPos match,
int length));
#endif
#define NIL 0
#ifndef TOO_FAR
# define TOO_FAR 4096
#endif
#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
typedef struct config_s {
ush good_length;
ush max_lazy;
ush nice_length;
ush max_chain;
compress_func func;
} config;
static const config configuration_table[10] = {
{0, 0, 0, 0, deflate_stored},
{4, 4, 8, 4, deflate_fast},
{4, 5, 16, 8, deflate_fast},
{4, 6, 32, 32, deflate_fast},
{4, 4, 16, 16, deflate_slow},
{8, 16, 32, 32, deflate_slow},
{8, 16, 128, 128, deflate_slow},
{8, 32, 128, 256, deflate_slow},
{32, 128, 258, 1024, deflate_slow},
{32, 258, 258, 4096, deflate_slow}};
#define EQUAL 0
#ifndef NO_DUMMY_DECL
struct static_tree_desc_s {int dummy;};
#endif
#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
#ifdef FASTEST
#define INSERT_STRING(s, str, match_head) \
(UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
match_head = s->head[s->ins_h], \
s->head[s->ins_h] = (Pos)(str))
#else
#define INSERT_STRING(s, str, match_head) \
(UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
s->head[s->ins_h] = (Pos)(str))
#endif
#define CLEAR_HASH(s) \
s->head[s->hash_size-1] = NIL; \
zmemzero((Bytef *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
int ZEXPORT
deflateInit_(z_streamp strm, int level, const char *ver, int stream_size)
{
return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
Z_DEFAULT_STRATEGY, ver, stream_size);
}
int ZEXPORT
deflateInit2_(z_streamp strm, int level, int method, int windowBits,
int memLevel, int strategy, const char *ver, int stream_size)
{
deflate_state *s;
int noheader = 0;
static const char* my_version = ZLIB_VERSION;
ushf *overlay;
if (ver == Z_NULL || ver[0] != my_version[0] ||
stream_size != sizeof(z_stream)) {
return Z_VERSION_ERROR;
}
if (strm == Z_NULL) return Z_STREAM_ERROR;
strm->msg = Z_NULL;
#ifndef NO_ZCFUNCS
if (strm->zalloc == Z_NULL) {
strm->zalloc = zcalloc;
strm->opaque = (voidpf)0;
}
if (strm->zfree == Z_NULL) strm->zfree = zcfree;
#endif
if (level == Z_DEFAULT_COMPRESSION) level = 6;
#ifdef FASTEST
level = 1;
#endif
if (windowBits < 0) {
noheader = 1;
windowBits = -windowBits;
}
if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != Z_DEFLATED ||
windowBits < 9 || windowBits > 15 || level < 0 || level > 9 ||
strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
return Z_STREAM_ERROR;
}
s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
if (s == Z_NULL) return Z_MEM_ERROR;
strm->state = (struct internal_state FAR *)s;
s->strm = strm;
s->noheader = noheader;
s->w_bits = windowBits;
s->w_size = 1 << s->w_bits;
s->w_mask = s->w_size - 1;
s->hash_bits = memLevel + 7;
s->hash_size = 1 << s->hash_bits;
s->hash_mask = s->hash_size - 1;
s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
s->lit_bufsize = 1 << (memLevel + 6);
overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
s->pending_buf = (uchf *) overlay;
s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
s->pending_buf == Z_NULL) {
strm->msg = (char*)ERR_MSG(Z_MEM_ERROR);
deflateEnd (strm);
return Z_MEM_ERROR;
}
s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
s->level = level;
s->strategy = strategy;
s->method = (Byte)method;
return deflateReset(strm);
}
int ZEXPORT
deflateSetDictionary(z_streamp strm, const Bytef *dictionary, uInt dictLength)
{
deflate_state *s;
uInt length = dictLength;
uInt n;
IPos hash_head = 0;
if (strm == Z_NULL || strm->state == Z_NULL || dictionary == Z_NULL ||
((deflate_state*)strm->state)->status != INIT_STATE) return Z_STREAM_ERROR;
s = (deflate_state*)strm->state;
strm->adler = adler32(strm->adler, dictionary, dictLength);
if (length < MIN_MATCH) return Z_OK;
if (length > MAX_DIST(s)) {
length = MAX_DIST(s);
#ifndef USE_DICT_HEAD
dictionary += dictLength - length;
#endif
}
zmemcpy(s->window, dictionary, length);
s->strstart = length;
s->block_start = (long)length;
s->ins_h = s->window[0];
UPDATE_HASH(s, s->ins_h, s->window[1]);
for (n = 0; n <= length - MIN_MATCH; n++) {
INSERT_STRING(s, n, hash_head);
}
if (hash_head) hash_head = 0;
return Z_OK;
}
int ZEXPORT
deflateReset(z_streamp strm)
{
deflate_state *s;
if (strm == Z_NULL || strm->state == Z_NULL ||
strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR;
strm->total_in = strm->total_out = 0;
strm->msg = Z_NULL;
strm->data_type = Z_UNKNOWN;
s = (deflate_state *)strm->state;
s->pending = 0;
s->pending_out = s->pending_buf;
if (s->noheader < 0) {
s->noheader = 0;
}
s->status = s->noheader ? BUSY_STATE : INIT_STATE;
strm->adler = 1;
s->last_flush = Z_NO_FLUSH;
_tr_init(s);
lm_init(s);
return Z_OK;
}
int ZEXPORT
deflateParams(z_streamp strm, int level, int strategy)
{
deflate_state *s;
compress_func func;
int err = Z_OK;
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
s = (deflate_state*)strm->state;
if (level == Z_DEFAULT_COMPRESSION) {
level = 6;
}
if (level < 0 || level > 9 || strategy < 0 || strategy > Z_HUFFMAN_ONLY) {
return Z_STREAM_ERROR;
}
func = configuration_table[s->level].func;
if (func != configuration_table[level].func && strm->total_in != 0) {
err = deflate(strm, Z_PARTIAL_FLUSH);
}
if (s->level != level) {
s->level = level;
s->max_lazy_match = configuration_table[level].max_lazy;
s->good_match = configuration_table[level].good_length;
s->nice_match = configuration_table[level].nice_length;
s->max_chain_length = configuration_table[level].max_chain;
}
s->strategy = strategy;
return err;
}
static void
putShortMSB(deflate_state *s, uInt b)
{
put_byte(s, (Byte)(b >> 8));
put_byte(s, (Byte)(b & 0xff));
}
static void
flush_pending(z_streamp strm)
{
deflate_state* s = (deflate_state*)strm->state;
unsigned len = s->pending;
if (len > strm->avail_out) len = strm->avail_out;
if (len == 0) return;
zmemcpy(strm->next_out, s->pending_out, len);
strm->next_out += len;
s->pending_out += len;
strm->total_out += len;
strm->avail_out -= len;
s->pending -= len;
if (s->pending == 0) {
s->pending_out = s->pending_buf;
}
}
int ZEXPORT
deflate (z_streamp strm, int flush)
{
int old_flush;
deflate_state *s;
if (strm == Z_NULL || strm->state == Z_NULL ||
flush > Z_FINISH || flush < 0) {
return Z_STREAM_ERROR;
}
s = (deflate_state*)strm->state;
if (strm->next_out == Z_NULL ||
(strm->next_in == Z_NULL && strm->avail_in != 0) ||
(s->status == FINISH_STATE && flush != Z_FINISH)) {
ERR_RETURN(strm, Z_STREAM_ERROR);
}
if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
s->strm = strm;
old_flush = s->last_flush;
s->last_flush = flush;
if (s->status == INIT_STATE) {
uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
uInt level_flags = (s->level-1) >> 1;
if (level_flags > 3) level_flags = 3;
header |= (level_flags << 6);
if (s->strstart != 0) header |= PRESET_DICT;
header += 31 - (header % 31);
s->status = BUSY_STATE;
putShortMSB(s, header);
if (s->strstart != 0) {
putShortMSB(s, (uInt)(strm->adler >> 16));
putShortMSB(s, (uInt)(strm->adler & 0xffff));
}
strm->adler = 1L;
}
if (s->pending != 0) {
flush_pending(strm);
if (strm->avail_out == 0) {
s->last_flush = -1;
return Z_OK;
}
} else if (strm->avail_in == 0 && flush <= old_flush &&
flush != Z_FINISH) {
ERR_RETURN(strm, Z_BUF_ERROR);
}
if (s->status == FINISH_STATE && strm->avail_in != 0) {
ERR_RETURN(strm, Z_BUF_ERROR);
}
if (strm->avail_in != 0 || s->lookahead != 0 ||
(flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
block_state bstate;
bstate = (*(configuration_table[s->level].func))(s, flush);
if (bstate == finish_started || bstate == finish_done) {
s->status = FINISH_STATE;
}
if (bstate == need_more || bstate == finish_started) {
if (strm->avail_out == 0) {
s->last_flush = -1;
}
return Z_OK;
}
if (bstate == block_done) {
if (flush == Z_PARTIAL_FLUSH) {
_tr_align(s);
} else {
_tr_stored_block(s, (char*)0, 0L, 0);
if (flush == Z_FULL_FLUSH) {
CLEAR_HASH(s);
}
}
flush_pending(strm);
if (strm->avail_out == 0) {
s->last_flush = -1;
return Z_OK;
}
}
}
Assert(strm->avail_out > 0, "bug2");
if (flush != Z_FINISH) return Z_OK;
if (s->noheader) return Z_STREAM_END;
putShortMSB(s, (uInt)(strm->adler >> 16));
putShortMSB(s, (uInt)(strm->adler & 0xffff));
flush_pending(strm);
s->noheader = -1;
return s->pending != 0 ? Z_OK : Z_STREAM_END;
}
int ZEXPORT
deflateEnd(z_streamp strm)
{
deflate_state* s;
int status;
if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
s = (deflate_state*)strm->state;
status = s->status;
if (status != INIT_STATE && status != BUSY_STATE &&
status != FINISH_STATE) {
return Z_STREAM_ERROR;
}
TRY_FREE(strm, s->pending_buf);
TRY_FREE(strm, s->head);
TRY_FREE(strm, s->prev);
TRY_FREE(strm, s->window);
ZFREE(strm, s);
strm->state = Z_NULL;
return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
}
int ZEXPORT
deflateCopy(z_streamp dest, z_streamp source)
{
#ifdef MAXSEG_64K
return Z_STREAM_ERROR;
#else
deflate_state *ds;
deflate_state *ss;
ushf *overlay;
if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
return Z_STREAM_ERROR;
}
ss = (deflate_state*)source->state;
*dest = *source;
ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
if (ds == Z_NULL) return Z_MEM_ERROR;
dest->state = (struct internal_state FAR *) ds;
*ds = *ss;
ds->strm = dest;
ds->window = (Bytef *) ZALLOC(dest, ds->w_size, 2*sizeof(Byte));
ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos));
ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos));
overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
ds->pending_buf = (uchf *) overlay;
if (ds->window == Z_NULL || ds->prev == Z_NULL || ds->head == Z_NULL ||
ds->pending_buf == Z_NULL) {
deflateEnd (dest);
return Z_MEM_ERROR;
}
zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
zmemcpy(ds->prev, ss->prev, ds->w_size * sizeof(Pos));
zmemcpy(ds->head, ss->head, ds->hash_size * sizeof(Pos));
zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
ds->l_desc.dyn_tree = ds->dyn_ltree;
ds->d_desc.dyn_tree = ds->dyn_dtree;
ds->bl_desc.dyn_tree = ds->bl_tree;
return Z_OK;
#endif
}
static int
read_buf(z_streamp strm, Bytef *buf, unsigned int size)
{
unsigned len = strm->avail_in;
if (len > size) len = size;
if (len == 0) return 0;
strm->avail_in -= len;
if (!((deflate_state*)strm->state)->noheader) {
strm->adler = adler32(strm->adler, strm->next_in, len);
}
zmemcpy(buf, strm->next_in, len);
strm->next_in += len;
strm->total_in += len;
return (int)len;
}
static void
lm_init(deflate_state *s)
{
s->window_size = (ulg)2L*s->w_size;
CLEAR_HASH(s);
s->max_lazy_match = configuration_table[s->level].max_lazy;
s->good_match = configuration_table[s->level].good_length;
s->nice_match = configuration_table[s->level].nice_length;
s->max_chain_length = configuration_table[s->level].max_chain;
s->strstart = 0;
s->block_start = 0L;
s->lookahead = 0;
s->match_length = s->prev_length = MIN_MATCH-1;
s->match_available = 0;
s->ins_h = 0;
#ifdef ASMV
match_init();
#endif
}
#ifndef ASMV
#ifndef FASTEST
static uInt
longest_match(deflate_state *s, IPos cur_match)
{
unsigned chain_length = s->max_chain_length;
Bytef *scan = s->window + s->strstart;
Bytef *match;
int len;
int best_len = s->prev_length;
int nice_match = s->nice_match;
IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
s->strstart - (IPos)MAX_DIST(s) : NIL;
Posf *prev = s->prev;
uInt wmask = s->w_mask;
#ifdef UNALIGNED_OK
Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
ush scan_start = *(ushf*)scan;
ush scan_end = *(ushf*)(scan+best_len-1);
#else
Bytef *strend = s->window + s->strstart + MAX_MATCH;
Byte scan_end1 = scan[best_len-1];
Byte scan_end = scan[best_len];
#endif
Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
if (s->prev_length >= s->good_match) {
chain_length >>= 2;
}
if ((uInt)nice_match > s->lookahead) nice_match = s->lookahead;
Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
do {
Assert(cur_match < s->strstart, "no future");
match = s->window + cur_match;
#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
if (*(ushf*)(match+best_len-1) != scan_end ||
*(ushf*)match != scan_start) continue;
Assert(scan[2] == match[2], "scan[2]?");
scan++, match++;
do {
} while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
scan < strend);
Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
if (*scan == *match) scan++;
len = (MAX_MATCH - 1) - (int)(strend-scan);
scan = strend - (MAX_MATCH-1);
#else
if (match[best_len] != scan_end ||
match[best_len-1] != scan_end1 ||
*match != *scan ||
*++match != scan[1]) continue;
scan += 2, match++;
Assert(*scan == *match, "match[2]?");
do {
} while (*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
scan < strend);
Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
len = MAX_MATCH - (int)(strend - scan);
scan = strend - MAX_MATCH;
#endif
if (len > best_len) {
s->match_start = cur_match;
best_len = len;
if (len >= nice_match) break;
#ifdef UNALIGNED_OK
scan_end = *(ushf*)(scan+best_len-1);
#else
scan_end1 = scan[best_len-1];
scan_end = scan[best_len];
#endif
}
} while ((cur_match = prev[cur_match & wmask]) > limit
&& --chain_length != 0);
if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
return s->lookahead;
}
#else
static uInt
longest_match(deflate_state *s, IPos cur_match)
{
Bytef *scan = s->window + s->strstart;
Bytef *match;
int len;
Bytef *strend = s->window + s->strstart + MAX_MATCH;
Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
Assert(cur_match < s->strstart, "no future");
match = s->window + cur_match;
if (match[0] != scan[0] || match[1] != scan[1]) return MIN_MATCH-1;
scan += 2, match += 2;
Assert(*scan == *match, "match[2]?");
do {
} while (*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
*++scan == *++match && *++scan == *++match &&
scan < strend);
Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
len = MAX_MATCH - (int)(strend - scan);
if (len < MIN_MATCH) return MIN_MATCH - 1;
s->match_start = cur_match;
return len <= s->lookahead ? len : s->lookahead;
}
#endif
#endif
#ifdef DEBUG_ZLIB
static void
check_match(deflate_state *s, IPos start, IPos match, int length)
{
if (zmemcmp(s->window + match,
s->window + start, length) != EQUAL) {
fprintf(stderr, " start %u, match %u, length %d\n",
start, match, length);
do {
fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
} while (--length != 0);
z_error("invalid match");
}
if (z_verbose > 1) {
fprintf(stderr,"\\[%d,%d]", start-match, length);
do { putc(s->window[start++], stderr); } while (--length != 0);
}
}
#else
# define check_match(s, start, match, length)
#endif
static void
fill_window(deflate_state *s)
{
unsigned n, m;
Posf *p;
unsigned more;
uInt wsize = s->w_size;
do {
more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
more = wsize;
} else if (more == (unsigned)(-1)) {
more--;
} else if (s->strstart >= wsize+MAX_DIST(s)) {
zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
s->match_start -= wsize;
s->strstart -= wsize;
s->block_start -= (long) wsize;
n = s->hash_size;
p = &s->head[n];
do {
m = *--p;
*p = (Pos)(m >= wsize ? m-wsize : NIL);
} while (--n);
n = wsize;
#ifndef FASTEST
p = &s->prev[n];
do {
m = *--p;
*p = (Pos)(m >= wsize ? m-wsize : NIL);
} while (--n);
#endif
more += wsize;
}
if (s->strm->avail_in == 0) return;
Assert(more >= 2, "more < 2");
n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
s->lookahead += n;
if (s->lookahead >= MIN_MATCH) {
s->ins_h = s->window[s->strstart];
UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
#if MIN_MATCH != 3
Call UPDATE_HASH() MIN_MATCH-3 more times
#endif
}
} while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
}
#define FLUSH_BLOCK_ONLY(s, eof) { \
_tr_flush_block(s, (s->block_start >= 0L ? \
(charf *)&s->window[(unsigned)s->block_start] : \
(charf *)Z_NULL), \
(ulg)((long)s->strstart - s->block_start), \
(eof)); \
s->block_start = s->strstart; \
flush_pending(s->strm); \
Tracev((stderr,"[FLUSH]")); \
}
#define FLUSH_BLOCK(s, eof) { \
FLUSH_BLOCK_ONLY(s, eof); \
if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \
}
static block_state
deflate_stored(deflate_state *s, int flush)
{
ulg max_block_size = 0xffff;
ulg max_start;
if (max_block_size > s->pending_buf_size - 5) {
max_block_size = s->pending_buf_size - 5;
}
for (;;) {
if (s->lookahead <= 1) {
Assert(s->strstart < s->w_size+MAX_DIST(s) ||
s->block_start >= (long)s->w_size, "slide too late");
fill_window(s);
if (s->lookahead == 0 && flush == Z_NO_FLUSH) return need_more;
if (s->lookahead == 0) break;
}
Assert(s->block_start >= 0L, "block gone");
s->strstart += s->lookahead;
s->lookahead = 0;
max_start = s->block_start + max_block_size;
if (s->strstart == 0 || (ulg)s->strstart >= max_start) {
s->lookahead = (uInt)(s->strstart - max_start);
s->strstart = (uInt)max_start;
FLUSH_BLOCK(s, 0);
}
if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
FLUSH_BLOCK(s, 0);
}
}
FLUSH_BLOCK(s, flush == Z_FINISH);
return flush == Z_FINISH ? finish_done : block_done;
}
static block_state
deflate_fast(deflate_state *s, int flush)
{
IPos hash_head = NIL;
int bflush;
for (;;) {
if (s->lookahead < MIN_LOOKAHEAD) {
fill_window(s);
if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
return need_more;
}
if (s->lookahead == 0) break;
}
if (s->lookahead >= MIN_MATCH) {
INSERT_STRING(s, s->strstart, hash_head);
}
if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
if (s->strategy != Z_HUFFMAN_ONLY) {
s->match_length = longest_match (s, hash_head);
}
}
if (s->match_length >= MIN_MATCH) {
check_match(s, s->strstart, s->match_start, s->match_length);
_tr_tally_dist(s, s->strstart - s->match_start,
s->match_length - MIN_MATCH, bflush);
s->lookahead -= s->match_length;
#ifndef FASTEST
if (s->match_length <= s->max_insert_length &&
s->lookahead >= MIN_MATCH) {
s->match_length--;
do {
s->strstart++;
INSERT_STRING(s, s->strstart, hash_head);
} while (--s->match_length != 0);
s->strstart++;
} else
#endif
{
s->strstart += s->match_length;
s->match_length = 0;
s->ins_h = s->window[s->strstart];
UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
#if MIN_MATCH != 3
Call UPDATE_HASH() MIN_MATCH-3 more times
#endif
}
} else {
Tracevv((stderr,"%c", s->window[s->strstart]));
_tr_tally_lit (s, s->window[s->strstart], bflush);
s->lookahead--;
s->strstart++;
}
if (bflush) FLUSH_BLOCK(s, 0);
}
FLUSH_BLOCK(s, flush == Z_FINISH);
return flush == Z_FINISH ? finish_done : block_done;
}
static block_state
deflate_slow(deflate_state *s, int flush)
{
IPos hash_head = NIL;
int bflush;
for (;;) {
if (s->lookahead < MIN_LOOKAHEAD) {
fill_window(s);
if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
return need_more;
}
if (s->lookahead == 0) break;
}
if (s->lookahead >= MIN_MATCH) {
INSERT_STRING(s, s->strstart, hash_head);
}
s->prev_length = s->match_length, s->prev_match = s->match_start;
s->match_length = MIN_MATCH-1;
if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
s->strstart - hash_head <= MAX_DIST(s)) {
if (s->strategy != Z_HUFFMAN_ONLY) {
s->match_length = longest_match (s, hash_head);
}
if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
(s->match_length == MIN_MATCH &&
s->strstart - s->match_start > TOO_FAR))) {
s->match_length = MIN_MATCH-1;
}
}
if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
check_match(s, s->strstart-1, s->prev_match, s->prev_length);
_tr_tally_dist(s, s->strstart -1 - s->prev_match,
s->prev_length - MIN_MATCH, bflush);
s->lookahead -= s->prev_length-1;
s->prev_length -= 2;
do {
if (++s->strstart <= max_insert) {
INSERT_STRING(s, s->strstart, hash_head);
}
} while (--s->prev_length != 0);
s->match_available = 0;
s->match_length = MIN_MATCH-1;
s->strstart++;
if (bflush) FLUSH_BLOCK(s, 0);
} else if (s->match_available) {
Tracevv((stderr,"%c", s->window[s->strstart-1]));
_tr_tally_lit(s, s->window[s->strstart-1], bflush);
if (bflush) {
FLUSH_BLOCK_ONLY(s, 0);
}
s->strstart++;
s->lookahead--;
if (s->strm->avail_out == 0) return need_more;
} else {
s->match_available = 1;
s->strstart++;
s->lookahead--;
}
}
Assert (flush != Z_NO_FLUSH, "no flush?");
if (s->match_available) {
Tracevv((stderr,"%c", s->window[s->strstart-1]));
_tr_tally_lit(s, s->window[s->strstart-1], bflush);
s->match_available = 0;
}
FLUSH_BLOCK(s, flush == Z_FINISH);
return flush == Z_FINISH ? finish_done : block_done;
}
#ifdef DEBUG_ZLIB
# include <ctype.h>
#endif
#define MAX_BL_BITS 7
#define END_BLOCK 256
#define REP_3_6 16
#define REPZ_3_10 17
#define REPZ_11_138 18
static const int extra_lbits[LENGTH_CODES]
= {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};
static const int extra_dbits[D_CODES]
= {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};
static const int extra_blbits[BL_CODES]
= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
static const uch bl_order[BL_CODES]
= {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
#define Buf_size (8 * 2*sizeof(char))
#define DIST_CODE_LEN 512
#if defined(GEN_TREES_H) || !defined(STDC)
static ct_data *static_ltree = Z_NULL;
static ct_data *static_dtree = Z_NULL;
uch *_dist_code = Z_NULL;
uch *_length_code = Z_NULL;
static int *base_length = Z_NULL;
static int *base_dist = Z_NULL;
#else
static const ct_data static_ltree[L_CODES+2] = {
{{ 12},{ 8}}, {{140},{ 8}}, {{ 76},{ 8}}, {{204},{ 8}}, {{ 44},{ 8}},
{{172},{ 8}}, {{108},{ 8}}, {{236},{ 8}}, {{ 28},{ 8}}, {{156},{ 8}},
{{ 92},{ 8}}, {{220},{ 8}}, {{ 60},{ 8}}, {{188},{ 8}}, {{124},{ 8}},
{{252},{ 8}}, {{ 2},{ 8}}, {{130},{ 8}}, {{ 66},{ 8}}, {{194},{ 8}},
{{ 34},{ 8}}, {{162},{ 8}}, {{ 98},{ 8}}, {{226},{ 8}}, {{ 18},{ 8}},
{{146},{ 8}}, {{ 82},{ 8}}, {{210},{ 8}}, {{ 50},{ 8}}, {{178},{ 8}},
{{114},{ 8}}, {{242},{ 8}}, {{ 10},{ 8}}, {{138},{ 8}}, {{ 74},{ 8}},
{{202},{ 8}}, {{ 42},{ 8}}, {{170},{ 8}}, {{106},{ 8}}, {{234},{ 8}},
{{ 26},{ 8}}, {{154},{ 8}}, {{ 90},{ 8}}, {{218},{ 8}}, {{ 58},{ 8}},
{{186},{ 8}}, {{122},{ 8}}, {{250},{ 8}}, {{ 6},{ 8}}, {{134},{ 8}},
{{ 70},{ 8}}, {{198},{ 8}}, {{ 38},{ 8}}, {{166},{ 8}}, {{102},{ 8}},
{{230},{ 8}}, {{ 22},{ 8}}, {{150},{ 8}}, {{ 86},{ 8}}, {{214},{ 8}},
{{ 54},{ 8}}, {{182},{ 8}}, {{118},{ 8}}, {{246},{ 8}}, {{ 14},{ 8}},
{{142},{ 8}}, {{ 78},{ 8}}, {{206},{ 8}}, {{ 46},{ 8}}, {{174},{ 8}},
{{110},{ 8}}, {{238},{ 8}}, {{ 30},{ 8}}, {{158},{ 8}}, {{ 94},{ 8}},
{{222},{ 8}}, {{ 62},{ 8}}, {{190},{ 8}}, {{126},{ 8}}, {{254},{ 8}},
{{ 1},{ 8}}, {{129},{ 8}}, {{ 65},{ 8}}, {{193},{ 8}}, {{ 33},{ 8}},
{{161},{ 8}}, {{ 97},{ 8}}, {{225},{ 8}}, {{ 17},{ 8}}, {{145},{ 8}},
{{ 81},{ 8}}, {{209},{ 8}}, {{ 49},{ 8}}, {{177},{ 8}}, {{113},{ 8}},
{{241},{ 8}}, {{ 9},{ 8}}, {{137},{ 8}}, {{ 73},{ 8}}, {{201},{ 8}},
{{ 41},{ 8}}, {{169},{ 8}}, {{105},{ 8}}, {{233},{ 8}}, {{ 25},{ 8}},
{{153},{ 8}}, {{ 89},{ 8}}, {{217},{ 8}}, {{ 57},{ 8}}, {{185},{ 8}},
{{121},{ 8}}, {{249},{ 8}}, {{ 5},{ 8}}, {{133},{ 8}}, {{ 69},{ 8}},
{{197},{ 8}}, {{ 37},{ 8}}, {{165},{ 8}}, {{101},{ 8}}, {{229},{ 8}},
{{ 21},{ 8}}, {{149},{ 8}}, {{ 85},{ 8}}, {{213},{ 8}}, {{ 53},{ 8}},
{{181},{ 8}}, {{117},{ 8}}, {{245},{ 8}}, {{ 13},{ 8}}, {{141},{ 8}},
{{ 77},{ 8}}, {{205},{ 8}}, {{ 45},{ 8}}, {{173},{ 8}}, {{109},{ 8}},
{{237},{ 8}}, {{ 29},{ 8}}, {{157},{ 8}}, {{ 93},{ 8}}, {{221},{ 8}},
{{ 61},{ 8}}, {{189},{ 8}}, {{125},{ 8}}, {{253},{ 8}}, {{ 19},{ 9}},
{{275},{ 9}}, {{147},{ 9}}, {{403},{ 9}}, {{ 83},{ 9}}, {{339},{ 9}},
{{211},{ 9}}, {{467},{ 9}}, {{ 51},{ 9}}, {{307},{ 9}}, {{179},{ 9}},
{{435},{ 9}}, {{115},{ 9}}, {{371},{ 9}}, {{243},{ 9}}, {{499},{ 9}},
{{ 11},{ 9}}, {{267},{ 9}}, {{139},{ 9}}, {{395},{ 9}}, {{ 75},{ 9}},
{{331},{ 9}}, {{203},{ 9}}, {{459},{ 9}}, {{ 43},{ 9}}, {{299},{ 9}},
{{171},{ 9}}, {{427},{ 9}}, {{107},{ 9}}, {{363},{ 9}}, {{235},{ 9}},
{{491},{ 9}}, {{ 27},{ 9}}, {{283},{ 9}}, {{155},{ 9}}, {{411},{ 9}},
{{ 91},{ 9}}, {{347},{ 9}}, {{219},{ 9}}, {{475},{ 9}}, {{ 59},{ 9}},
{{315},{ 9}}, {{187},{ 9}}, {{443},{ 9}}, {{123},{ 9}}, {{379},{ 9}},
{{251},{ 9}}, {{507},{ 9}}, {{ 7},{ 9}}, {{263},{ 9}}, {{135},{ 9}},
{{391},{ 9}}, {{ 71},{ 9}}, {{327},{ 9}}, {{199},{ 9}}, {{455},{ 9}},
{{ 39},{ 9}}, {{295},{ 9}}, {{167},{ 9}}, {{423},{ 9}}, {{103},{ 9}},
{{359},{ 9}}, {{231},{ 9}}, {{487},{ 9}}, {{ 23},{ 9}}, {{279},{ 9}},
{{151},{ 9}}, {{407},{ 9}}, {{ 87},{ 9}}, {{343},{ 9}}, {{215},{ 9}},
{{471},{ 9}}, {{ 55},{ 9}}, {{311},{ 9}}, {{183},{ 9}}, {{439},{ 9}},
{{119},{ 9}}, {{375},{ 9}}, {{247},{ 9}}, {{503},{ 9}}, {{ 15},{ 9}},
{{271},{ 9}}, {{143},{ 9}}, {{399},{ 9}}, {{ 79},{ 9}}, {{335},{ 9}},
{{207},{ 9}}, {{463},{ 9}}, {{ 47},{ 9}}, {{303},{ 9}}, {{175},{ 9}},
{{431},{ 9}}, {{111},{ 9}}, {{367},{ 9}}, {{239},{ 9}}, {{495},{ 9}},
{{ 31},{ 9}}, {{287},{ 9}}, {{159},{ 9}}, {{415},{ 9}}, {{ 95},{ 9}},
{{351},{ 9}}, {{223},{ 9}}, {{479},{ 9}}, {{ 63},{ 9}}, {{319},{ 9}},
{{191},{ 9}}, {{447},{ 9}}, {{127},{ 9}}, {{383},{ 9}}, {{255},{ 9}},
{{511},{ 9}}, {{ 0},{ 7}}, {{ 64},{ 7}}, {{ 32},{ 7}}, {{ 96},{ 7}},
{{ 16},{ 7}}, {{ 80},{ 7}}, {{ 48},{ 7}}, {{112},{ 7}}, {{ 8},{ 7}},
{{ 72},{ 7}}, {{ 40},{ 7}}, {{104},{ 7}}, {{ 24},{ 7}}, {{ 88},{ 7}},
{{ 56},{ 7}}, {{120},{ 7}}, {{ 4},{ 7}}, {{ 68},{ 7}}, {{ 36},{ 7}},
{{100},{ 7}}, {{ 20},{ 7}}, {{ 84},{ 7}}, {{ 52},{ 7}}, {{116},{ 7}},
{{ 3},{ 8}}, {{131},{ 8}}, {{ 67},{ 8}}, {{195},{ 8}}, {{ 35},{ 8}},
{{163},{ 8}}, {{ 99},{ 8}}, {{227},{ 8}}
};
static const ct_data static_dtree[D_CODES] = {
{{ 0},{ 5}}, {{16},{ 5}}, {{ 8},{ 5}}, {{24},{ 5}}, {{ 4},{ 5}},
{{20},{ 5}}, {{12},{ 5}}, {{28},{ 5}}, {{ 2},{ 5}}, {{18},{ 5}},
{{10},{ 5}}, {{26},{ 5}}, {{ 6},{ 5}}, {{22},{ 5}}, {{14},{ 5}},
{{30},{ 5}}, {{ 1},{ 5}}, {{17},{ 5}}, {{ 9},{ 5}}, {{25},{ 5}},
{{ 5},{ 5}}, {{21},{ 5}}, {{13},{ 5}}, {{29},{ 5}}, {{ 3},{ 5}},
{{19},{ 5}}, {{11},{ 5}}, {{27},{ 5}}, {{ 7},{ 5}}, {{23},{ 5}}
};
const uch _dist_code[DIST_CODE_LEN] = {
0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8,
8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 10,
10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13,
13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15,
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 0, 0, 16, 17,
18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22,
23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27,
27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29
};
const uch _length_code[MAX_MATCH-MIN_MATCH+1]= {
0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12,
13, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16,
17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 19, 19, 19, 19,
19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22,
22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23,
23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26, 26, 26, 26, 26, 26,
26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28
};
static const int base_length[LENGTH_CODES] = {
0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56,
64, 80, 96, 112, 128, 160, 192, 224, 0
};
static const int base_dist[D_CODES] = {
0, 1, 2, 3, 4, 6, 8, 12, 16, 24,
32, 48, 64, 96, 128, 192, 256, 384, 512, 768,
1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576
};
#endif
struct static_tree_desc_s {
const ct_data *static_tree;
const intf *extra_bits;
int extra_base;
int elems;
int max_length;
};
static static_tree_desc static_l_desc =
{NULL, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
static static_tree_desc static_d_desc =
{NULL, extra_dbits, 0, D_CODES, MAX_BITS};
static static_tree_desc static_bl_desc =
{(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
static int tr_static_init OF((z_streamp z));
static void init_block OF((deflate_state *s));
static void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
static void gen_bitlen OF((deflate_state *s, tree_desc *desc));
static void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count));
static void build_tree OF((deflate_state *s, tree_desc *desc));
static void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
static void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
static int build_bl_tree OF((deflate_state *s));
static void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
int blcodes));
static void compress_block OF((deflate_state *s, ct_data *ltree,
ct_data *dtree));
static void set_data_type OF((deflate_state *s));
static unsigned bi_reverse OF((unsigned value, int length));
static void bi_windup OF((deflate_state *s));
static void bi_flush OF((deflate_state *s));
static void copy_block OF((deflate_state *s, charf *buf, unsigned len,
int header));
#ifdef GEN_TREES_H
static void gen_trees_header OF((void));
#endif
#ifndef DEBUG_ZLIB
# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
#else
# define send_code(s, c, tree) \
{ if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
send_bits(s, tree[c].Code, tree[c].Len); }
#endif
#define put_short(s, w) { \
put_byte(s, (uch)((w) & 0xff)); \
put_byte(s, (uch)((ush)(w) >> 8)); \
}
#ifdef DEBUG_ZLIB
static void send_bits OF((deflate_state *s, int value, int length));
static void send_bits(deflate_state *s, int value, int length)
{
Tracevv((stderr," l %2d v %4x ", length, value));
Assert(length > 0 && length <= 15, "invalid length");
s->bits_sent += (ulg)length;
if (s->bi_valid > (int)Buf_size - length) {
s->bi_buf |= (value << s->bi_valid);
put_short(s, s->bi_buf);
s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
s->bi_valid += length - Buf_size;
} else {
s->bi_buf |= value << s->bi_valid;
s->bi_valid += length;
}
}
#else
#define send_bits(s, value, length) \
{ int len = length;\
if (s->bi_valid > (int)Buf_size - len) {\
int val = value;\
s->bi_buf |= (val << s->bi_valid);\
put_short(s, s->bi_buf);\
s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
s->bi_valid += len - Buf_size;\
} else {\
s->bi_buf |= (value) << s->bi_valid;\
s->bi_valid += len;\
}\
}
#endif
#ifndef MAX
#define MAX(a,b) (a >= b ? a : b)
#endif
typedef struct {
ct_data static_ltree[L_CODES+2];
ct_data static_dtree[D_CODES];
uch _dist_code[DIST_CODE_LEN];
uch _length_code[MAX_MATCH-MIN_MATCH+1];
int base_length[LENGTH_CODES];
int base_dist[D_CODES];
} __used_to_be_static;
#if defined(GEN_TREES_H) || !defined(STDC)
static __used_to_be_static *static_storage = Z_NULL;
#endif
static int tr_static_init(
z_streamp z)
{
#if defined(GEN_TREES_H) || !defined(STDC)
static int static_init_done = 0;
int n;
int bits;
int length;
int code;
int dist;
ush bl_count[MAX_BITS+1];
if (static_init_done) return Z_OK;
if (static_storage == Z_NULL) {
static_storage = (__used_to_be_static*)ZALLOC(z, 1, sizeof(__used_to_be_static));
if (static_storage == Z_NULL)
return Z_MEM_ERROR;
}
static_ltree = static_storage->static_ltree;
static_dtree = static_storage->static_dtree;
_dist_code = static_storage->_dist_code;
_length_code = static_storage->_length_code;
base_length = static_storage->base_length;
base_dist = static_storage->base_dist;
static_l_desc.static_tree = static_ltree;
static_l_desc.extra_bits = extra_lbits;
static_d_desc.static_tree = static_dtree;
static_d_desc.extra_bits = extra_dbits;
static_bl_desc.extra_bits = extra_blbits;
length = 0;
for (code = 0; code < LENGTH_CODES-1; code++) {
base_length[code] = length;
for (n = 0; n < (1<<extra_lbits[code]); n++) {
_length_code[length++] = (uch)code;
}
}
Assert (length == 256, "tr_static_init: length != 256");
_length_code[length-1] = (uch)code;
dist = 0;
for (code = 0 ; code < 16; code++) {
base_dist[code] = dist;
for (n = 0; n < (1<<extra_dbits[code]); n++) {
_dist_code[dist++] = (uch)code;
}
}
Assert (dist == 256, "tr_static_init: dist != 256");
dist >>= 7;
for ( ; code < D_CODES; code++) {
base_dist[code] = dist << 7;
for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
_dist_code[256 + dist++] = (uch)code;
}
}
Assert (dist == 256, "tr_static_init: 256+dist != 512");
for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
n = 0;
while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
for (n = 0; n < D_CODES; n++) {
static_dtree[n].Len = 5;
static_dtree[n].Code = bi_reverse((unsigned)n, 5);
}
static_init_done = 1;
# ifdef GEN_TREES_H
gen_trees_header();
# endif
#endif
return Z_OK;
}
#ifdef GEN_TREES_H
# ifndef DEBUG_ZLIB
# include <stdio.h>
# endif
# define SEPARATOR(i, last, width) \
((i) == (last)? "\n};\n\n" : \
((i) % (width) == (width)-1 ? ",\n" : ", "))
void gen_trees_header()
{
FILE *header = fopen("trees.h", "w");
int i;
Assert (header != NULL, "Can't open trees.h");
fprintf(header,
"/* header created automatically with -DGEN_TREES_H */\n\n");
fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");
for (i = 0; i < L_CODES+2; i++) {
fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
}
fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");
for (i = 0; i < D_CODES; i++) {
fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
}
fprintf(header, "const uch _dist_code[DIST_CODE_LEN] = {\n");
for (i = 0; i < DIST_CODE_LEN; i++) {
fprintf(header, "%2u%s", _dist_code[i],
SEPARATOR(i, DIST_CODE_LEN-1, 20));
}
fprintf(header, "const uch _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
fprintf(header, "%2u%s", _length_code[i],
SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
}
fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");
for (i = 0; i < LENGTH_CODES; i++) {
fprintf(header, "%1u%s", base_length[i],
SEPARATOR(i, LENGTH_CODES-1, 20));
}
fprintf(header, "local const int base_dist[D_CODES] = {\n");
for (i = 0; i < D_CODES; i++) {
fprintf(header, "%5u%s", base_dist[i],
SEPARATOR(i, D_CODES-1, 10));
}
fclose(header);
}
#endif
static void
_tr_init(deflate_state *s)
{
tr_static_init(s->strm);
s->l_desc.dyn_tree = s->dyn_ltree;
s->l_desc.stat_desc = &static_l_desc;
s->d_desc.dyn_tree = s->dyn_dtree;
s->d_desc.stat_desc = &static_d_desc;
s->bl_desc.dyn_tree = s->bl_tree;
s->bl_desc.stat_desc = &static_bl_desc;
s->bi_buf = 0;
s->bi_valid = 0;
s->last_eob_len = 8;
#ifdef DEBUG_ZLIB
s->compressed_len = 0L;
s->bits_sent = 0L;
#endif
init_block(s);
}
static void
init_block(deflate_state *s)
{
int n;
for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
s->dyn_ltree[END_BLOCK].Freq = 1;
s->opt_len = s->static_len = 0L;
s->last_lit = s->matches = 0;
}
#define SMALLEST 1
#define pqremove(s, tree, top) \
{\
top = s->heap[SMALLEST]; \
s->heap[SMALLEST] = s->heap[s->heap_len--]; \
pqdownheap(s, tree, SMALLEST); \
}
#define smaller(tree, n, m, depth) \
(tree[n].Freq < tree[m].Freq || \
(tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
static void
pqdownheap(deflate_state *s, ct_data *tree, int k)
{
int v = s->heap[k];
int j = k << 1;
while (j <= s->heap_len) {
if (j < s->heap_len &&
smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
j++;
}
if (smaller(tree, v, s->heap[j], s->depth)) break;
s->heap[k] = s->heap[j]; k = j;
j <<= 1;
}
s->heap[k] = v;
}
static void
gen_bitlen(deflate_state *s, tree_desc *desc)
{
ct_data *tree = desc->dyn_tree;
int max_code = desc->max_code;
const ct_data *stree = desc->stat_desc->static_tree;
const intf *extra = desc->stat_desc->extra_bits;
int base = desc->stat_desc->extra_base;
int max_length = desc->stat_desc->max_length;
int h;
int n, m;
int bits;
int xbits;
ush f;
int overflow = 0;
for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
tree[s->heap[s->heap_max]].Len = 0;
for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
n = s->heap[h];
bits = tree[tree[n].Dad].Len + 1;
if (bits > max_length) bits = max_length, overflow++;
tree[n].Len = (ush)bits;
if (n > max_code) continue;
s->bl_count[bits]++;
xbits = 0;
if (n >= base) xbits = extra[n-base];
f = tree[n].Freq;
s->opt_len += (ulg)f * (bits + xbits);
if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
}
if (overflow == 0) return;
Trace((stderr,"\nbit length overflow\n"));
do {
bits = max_length-1;
while (s->bl_count[bits] == 0) bits--;
s->bl_count[bits]--;
s->bl_count[bits+1] += 2;
s->bl_count[max_length]--;
overflow -= 2;
} while (overflow > 0);
for (bits = max_length; bits != 0; bits--) {
n = s->bl_count[bits];
while (n != 0) {
m = s->heap[--h];
if (m > max_code) continue;
if (tree[m].Len != (unsigned) bits) {
Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
s->opt_len += ((long)bits - (long)tree[m].Len)
*(long)tree[m].Freq;
tree[m].Len = (ush)bits;
}
n--;
}
}
}
static void
gen_codes(ct_data *tree, int max_code, ushf *bl_count)
{
ush next_code[MAX_BITS+1];
ush code = 0;
int bits;
int n;
for (bits = 1; bits <= MAX_BITS; bits++) {
next_code[bits] = code = (code + bl_count[bits-1]) << 1;
}
Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
"inconsistent bit counts");
Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
for (n = 0; n <= max_code; n++) {
int len = tree[n].Len;
if (len == 0) continue;
tree[n].Code = bi_reverse(next_code[len]++, len);
Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
}
}
static void
build_tree(deflate_state *s, tree_desc *desc)
{
ct_data *tree = desc->dyn_tree;
const ct_data *stree = desc->stat_desc->static_tree;
int elems = desc->stat_desc->elems;
int n, m;
int max_code = -1;
int node;
s->heap_len = 0, s->heap_max = HEAP_SIZE;
for (n = 0; n < elems; n++) {
if (tree[n].Freq != 0) {
s->heap[++(s->heap_len)] = max_code = n;
s->depth[n] = 0;
} else {
tree[n].Len = 0;
}
}
while (s->heap_len < 2) {
node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
tree[node].Freq = 1;
s->depth[node] = 0;
s->opt_len--; if (stree) s->static_len -= stree[node].Len;
}
desc->max_code = max_code;
for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
node = elems;
do {
pqremove(s, tree, n);
m = s->heap[SMALLEST];
s->heap[--(s->heap_max)] = n;
s->heap[--(s->heap_max)] = m;
tree[node].Freq = tree[n].Freq + tree[m].Freq;
s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1);
tree[n].Dad = tree[m].Dad = (ush)node;
#ifdef DUMP_BL_TREE
if (tree == s->bl_tree) {
fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
}
#endif
s->heap[SMALLEST] = node++;
pqdownheap(s, tree, SMALLEST);
} while (s->heap_len >= 2);
s->heap[--(s->heap_max)] = s->heap[SMALLEST];
gen_bitlen(s, (tree_desc *)desc);
gen_codes ((ct_data *)tree, max_code, s->bl_count);
}
static void
scan_tree(deflate_state *s, ct_data *tree, int max_code)
{
int n;
int prevlen = -1;
int curlen;
int nextlen = tree[0].Len;
int count = 0;
int max_count = 7;
int min_count = 4;
if (nextlen == 0) max_count = 138, min_count = 3;
tree[max_code+1].Len = (ush)0xffff;
for (n = 0; n <= max_code; n++) {
curlen = nextlen; nextlen = tree[n+1].Len;
if (++count < max_count && curlen == nextlen) {
continue;
} else if (count < min_count) {
s->bl_tree[curlen].Freq += count;
} else if (curlen != 0) {
if (curlen != prevlen) s->bl_tree[curlen].Freq++;
s->bl_tree[REP_3_6].Freq++;
} else if (count <= 10) {
s->bl_tree[REPZ_3_10].Freq++;
} else {
s->bl_tree[REPZ_11_138].Freq++;
}
count = 0; prevlen = curlen;
if (nextlen == 0) {
max_count = 138, min_count = 3;
} else if (curlen == nextlen) {
max_count = 6, min_count = 3;
} else {
max_count = 7, min_count = 4;
}
}
}
static void
send_tree(deflate_state *s, ct_data *tree, int max_code)
{
int n;
int prevlen = -1;
int curlen;
int nextlen = tree[0].Len;
int count = 0;
int max_count = 7;
int min_count = 4;
if (nextlen == 0) max_count = 138, min_count = 3;
for (n = 0; n <= max_code; n++) {
curlen = nextlen; nextlen = tree[n+1].Len;
if (++count < max_count && curlen == nextlen) {
continue;
} else if (count < min_count) {
do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
} else if (curlen != 0) {
if (curlen != prevlen) {
send_code(s, curlen, s->bl_tree); count--;
}
Assert(count >= 3 && count <= 6, " 3_6?");
send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
} else if (count <= 10) {
send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
} else {
send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
}
count = 0; prevlen = curlen;
if (nextlen == 0) {
max_count = 138, min_count = 3;
} else if (curlen == nextlen) {
max_count = 6, min_count = 3;
} else {
max_count = 7, min_count = 4;
}
}
}
static int
build_bl_tree(deflate_state *s)
{
int max_blindex;
scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
build_tree(s, (tree_desc *)(&(s->bl_desc)));
for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
}
s->opt_len += 3*(max_blindex+1) + 5+5+4;
Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
s->opt_len, s->static_len));
return max_blindex;
}
static void
send_all_trees(deflate_state *s, int lcodes, int dcodes, int blcodes)
{
int rank;
Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
"too many codes");
Tracev((stderr, "\nbl counts: "));
send_bits(s, lcodes-257, 5);
send_bits(s, dcodes-1, 5);
send_bits(s, blcodes-4, 4);
for (rank = 0; rank < blcodes; rank++) {
Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
}
Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1);
Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1);
Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
}
static void
_tr_stored_block(deflate_state *s, charf *buf, ulg stored_len, int eof)
{
send_bits(s, (STORED_BLOCK<<1)+eof, 3);
#ifdef DEBUG_ZLIB
s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
s->compressed_len += (stored_len + 4) << 3;
#endif
copy_block(s, buf, (unsigned)stored_len, 1);
}
static void
_tr_align(deflate_state *s)
{
send_bits(s, STATIC_TREES<<1, 3);
send_code(s, END_BLOCK, static_ltree);
#ifdef DEBUG_ZLIB
s->compressed_len += 10L;
#endif
bi_flush(s);
if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
send_bits(s, STATIC_TREES<<1, 3);
send_code(s, END_BLOCK, static_ltree);
#ifdef DEBUG_ZLIB
s->compressed_len += 10L;
#endif
bi_flush(s);
}
s->last_eob_len = 7;
}
static void
_tr_flush_block(deflate_state *s, charf *buf, ulg stored_len, int eof)
{
ulg opt_lenb, static_lenb;
int max_blindex = 0;
if (s->level > 0) {
if (s->data_type == Z_UNKNOWN) set_data_type(s);
build_tree(s, (tree_desc *)(&(s->l_desc)));
Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
s->static_len));
build_tree(s, (tree_desc *)(&(s->d_desc)));
Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
s->static_len));
max_blindex = build_bl_tree(s);
opt_lenb = (s->opt_len+3+7)>>3;
static_lenb = (s->static_len+3+7)>>3;
Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
s->last_lit));
if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
} else {
Assert(buf != (char*)0, "lost buf");
opt_lenb = static_lenb = stored_len + 5;
}
#ifdef FORCE_STORED
if (buf != (char*)0) {
#else
if (stored_len+4 <= opt_lenb && buf != (char*)0) {
#endif
_tr_stored_block(s, buf, stored_len, eof);
#ifdef FORCE_STATIC
} else if (static_lenb >= 0) {
#else
} else if (static_lenb == opt_lenb) {
#endif
send_bits(s, (STATIC_TREES<<1)+eof, 3);
compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
#ifdef DEBUG_ZLIB
s->compressed_len += 3 + s->static_len;
#endif
} else {
send_bits(s, (DYN_TREES<<1)+eof, 3);
send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
max_blindex+1);
compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
#ifdef DEBUG_ZLIB
s->compressed_len += 3 + s->opt_len;
#endif
}
Assert (s->compressed_len == s->bits_sent, "bad compressed size");
init_block(s);
if (eof) {
bi_windup(s);
#ifdef DEBUG_ZLIB
s->compressed_len += 7;
#endif
}
Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
s->compressed_len-7*eof));
}
static int
_tr_tally(deflate_state *s, unsigned int dist, unsigned int lc)
{
s->d_buf[s->last_lit] = (ush)dist;
s->l_buf[s->last_lit++] = (uch)lc;
if (dist == 0) {
s->dyn_ltree[lc].Freq++;
} else {
s->matches++;
dist--;
Assert((ush)dist < (ush)MAX_DIST(s) &&
(ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
(ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match");
s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
s->dyn_dtree[d_code(dist)].Freq++;
}
#ifdef TRUNCATE_BLOCK
if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
ulg out_length = (ulg)s->last_lit*8L;
ulg in_length = (ulg)((long)s->strstart - s->block_start);
int dcode;
for (dcode = 0; dcode < D_CODES; dcode++) {
out_length += (ulg)s->dyn_dtree[dcode].Freq *
(5L+extra_dbits[dcode]);
}
out_length >>= 3;
Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
s->last_lit, in_length, out_length,
100L - out_length*100L/in_length));
if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
}
#endif
return (s->last_lit == s->lit_bufsize-1);
}
static void
compress_block(deflate_state *s, ct_data *ltree, ct_data *dtree)
{
unsigned dist;
int lc;
unsigned lx = 0;
unsigned code;
int extra;
if (s->last_lit != 0) do {
dist = s->d_buf[lx];
lc = s->l_buf[lx++];
if (dist == 0) {
send_code(s, lc, ltree);
Tracecv(isgraph(lc), (stderr," '%c' ", lc));
} else {
code = _length_code[lc];
send_code(s, code+LITERALS+1, ltree);
extra = extra_lbits[code];
if (extra != 0) {
lc -= base_length[code];
send_bits(s, lc, extra);
}
dist--;
code = d_code(dist);
Assert (code < D_CODES, "bad d_code");
send_code(s, code, dtree);
extra = extra_dbits[code];
if (extra != 0) {
dist -= base_dist[code];
send_bits(s, dist, extra);
}
}
Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow");
} while (lx < s->last_lit);
send_code(s, END_BLOCK, ltree);
s->last_eob_len = ltree[END_BLOCK].Len;
}
static void
set_data_type(deflate_state *s)
{
int n = 0;
unsigned ascii_freq = 0;
unsigned bin_freq = 0;
while (n < 7) bin_freq += s->dyn_ltree[n++].Freq;
while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq;
while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII);
}
static unsigned
bi_reverse(unsigned code, int len)
{
unsigned res = 0;
do {
res |= code & 1;
code >>= 1, res <<= 1;
} while (--len > 0);
return res >> 1;
}
static void
bi_flush(deflate_state *s)
{
if (s->bi_valid == 16) {
put_short(s, s->bi_buf);
s->bi_buf = 0;
s->bi_valid = 0;
} else if (s->bi_valid >= 8) {
put_byte(s, (Byte)s->bi_buf);
s->bi_buf >>= 8;
s->bi_valid -= 8;
}
}
static void
bi_windup(deflate_state *s)
{
if (s->bi_valid > 8) {
put_short(s, s->bi_buf);
} else if (s->bi_valid > 0) {
put_byte(s, (Byte)s->bi_buf);
}
s->bi_buf = 0;
s->bi_valid = 0;
#ifdef DEBUG_ZLIB
s->bits_sent = (s->bits_sent+7) & ~7;
#endif
}
static void
copy_block(deflate_state *s, charf *buf, unsigned int len, int header)
{
bi_windup(s);
s->last_eob_len = 8;
if (header) {
put_short(s, (ush)len);
put_short(s, (ush)~len);
#ifdef DEBUG_ZLIB
s->bits_sent += 2*16;
#endif
}
#ifdef DEBUG_ZLIB
s->bits_sent += (ulg)len<<3;
#endif
while (len--) {
put_byte(s, *buf++);
}
}
struct inflate_blocks_state;
typedef struct inflate_blocks_state FAR inflate_blocks_statef;
static inflate_blocks_statef * inflate_blocks_new OF((
z_streamp z,
check_func c,
uInt w));
static int inflate_blocks OF((
inflate_blocks_statef *,
z_streamp ,
int));
static void inflate_blocks_reset OF((
inflate_blocks_statef *,
z_streamp ,
uLongf *));
static int inflate_blocks_free OF((
inflate_blocks_statef *,
z_streamp));
static void inflate_set_dictionary OF((
inflate_blocks_statef *s,
const Bytef *d,
uInt n));
static int inflate_blocks_sync_point OF((
inflate_blocks_statef *s));
#ifndef NO_DUMMY_DECL
struct inflate_blocks_state {int dummy;};
#endif
typedef struct inflate_state {
enum {
METHOD,
FLAG,
DICT4,
DICT3,
DICT2,
DICT1,
DICT0,
BLOCKS,
CHECK4,
CHECK3,
CHECK2,
CHECK1,
DONE,
BAD}
mode;
union {
uInt method;
struct {
uLong was;
uLong need;
} check;
uInt marker;
} sub;
int nowrap;
uInt wbits;
inflate_blocks_statef
*blocks;
}inflate_state;
int ZEXPORT
inflateReset(z_streamp z)
{
inflate_state* s;
if (z == Z_NULL || z->state == Z_NULL)
return Z_STREAM_ERROR;
s = (inflate_state*)z->state;
z->total_in = z->total_out = 0;
z->msg = Z_NULL;
s->mode = s->nowrap ? BLOCKS : METHOD;
inflate_blocks_reset(s->blocks, z, Z_NULL);
Tracev((stderr, "inflate: reset\n"));
return Z_OK;
}
int ZEXPORT
inflateEnd(z_streamp z)
{
if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
return Z_STREAM_ERROR;
if (((inflate_state*)z->state)->blocks != Z_NULL)
inflate_blocks_free(((inflate_state*)z->state)->blocks, z);
ZFREE(z, z->state);
z->state = Z_NULL;
Tracev((stderr, "inflate: end\n"));
return Z_OK;
}
int ZEXPORT
inflateInit2_(z_streamp z, int w, const char *ver, int stream_size)
{
inflate_state* s;
if (ver == Z_NULL || ver[0] != ZLIB_VERSION[0] ||
stream_size != sizeof(z_stream))
return Z_VERSION_ERROR;
if (z == Z_NULL)
return Z_STREAM_ERROR;
z->msg = Z_NULL;
#ifndef NO_ZCFUNCS
if (z->zalloc == Z_NULL)
{
z->zalloc = zcalloc;
z->opaque = (voidpf)0;
}
if (z->zfree == Z_NULL) z->zfree = zcfree;
#endif
if ((z->state = (struct internal_state FAR *)
ZALLOC(z,1,sizeof(struct inflate_state))) == Z_NULL)
return Z_MEM_ERROR;
s = (inflate_state*)z->state;
s->blocks = Z_NULL;
s->nowrap = 0;
if (w < 0)
{
w = - w;
s->nowrap = 1;
}
if (w < 8 || w > 15)
{
inflateEnd(z);
return Z_STREAM_ERROR;
}
s->wbits = (uInt)w;
if ((s->blocks =
inflate_blocks_new(z, s->nowrap ? Z_NULL : adler32, (uInt)1 << w))
== Z_NULL)
{
inflateEnd(z);
return Z_MEM_ERROR;
}
Tracev((stderr, "inflate: allocated\n"));
inflateReset(z);
return Z_OK;
}
int ZEXPORT
inflateInit_(z_streamp z, const char *ver, int stream_size)
{
return inflateInit2_(z, DEF_WBITS, ver, stream_size);
}
#define NEEDBYTE {if(z->avail_in==0)return r;r=f;}
#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)
int ZEXPORT
inflate(z_streamp z, int f)
{
int r;
uInt b;
inflate_state* s;
if (z == Z_NULL || z->state == Z_NULL || z->next_in == Z_NULL)
return Z_STREAM_ERROR;
f = f == Z_FINISH ? Z_BUF_ERROR : Z_OK;
r = Z_BUF_ERROR;
s = (inflate_state*)z->state;
while (1) switch (s->mode)
{
case METHOD:
NEEDBYTE
if (((s->sub.method = NEXTBYTE) & 0xf) != Z_DEFLATED)
{
s->mode = BAD;
z->msg = (char*)"unknown compression method";
s->sub.marker = 5;
break;
}
if ((s->sub.method >> 4) + 8 > s->wbits)
{
s->mode = BAD;
z->msg = (char*)"invalid window size";
s->sub.marker = 5;
break;
}
s->mode = FLAG;
case FLAG:
NEEDBYTE
b = NEXTBYTE;
if (((s->sub.method << 8) + b) % 31)
{
s->mode = BAD;
z->msg = (char*)"incorrect header check";
s->sub.marker = 5;
break;
}
Tracev((stderr, "inflate: zlib header ok\n"));
if (!(b & PRESET_DICT))
{
s->mode = BLOCKS;
break;
}
s->mode = DICT4;
case DICT4:
NEEDBYTE
s->sub.check.need = (uLong)NEXTBYTE << 24;
s->mode = DICT3;
case DICT3:
NEEDBYTE
s->sub.check.need += (uLong)NEXTBYTE << 16;
s->mode = DICT2;
case DICT2:
NEEDBYTE
s->sub.check.need += (uLong)NEXTBYTE << 8;
s->mode = DICT1;
case DICT1:
NEEDBYTE
s->sub.check.need += (uLong)NEXTBYTE;
z->adler = s->sub.check.need;
s->mode = DICT0;
return Z_NEED_DICT;
case DICT0:
s->mode = BAD;
z->msg = (char*)"need dictionary";
s->sub.marker = 0;
return Z_STREAM_ERROR;
case BLOCKS:
r = inflate_blocks(s->blocks, z, r);
if (r == Z_DATA_ERROR)
{
s->mode = BAD;
s->sub.marker = 0;
break;
}
if (r == Z_OK)
r = f;
if (r != Z_STREAM_END)
return r;
r = f;
inflate_blocks_reset(s->blocks, z, &s->sub.check.was);
if (s->nowrap)
{
s->mode = DONE;
break;
}
s->mode = CHECK4;
case CHECK4:
NEEDBYTE
s->sub.check.need = (uLong)NEXTBYTE << 24;
s->mode = CHECK3;
case CHECK3:
NEEDBYTE
s->sub.check.need += (uLong)NEXTBYTE << 16;
s->mode = CHECK2;
case CHECK2:
NEEDBYTE
s->sub.check.need += (uLong)NEXTBYTE << 8;
s->mode = CHECK1;
case CHECK1:
NEEDBYTE
s->sub.check.need += (uLong)NEXTBYTE;
if (s->sub.check.was != s->sub.check.need)
{
s->mode = BAD;
z->msg = (char*)"incorrect data check";
s->sub.marker = 5;
break;
}
Tracev((stderr, "inflate: zlib check ok\n"));
s->mode = DONE;
case DONE:
return Z_STREAM_END;
case BAD:
return Z_DATA_ERROR;
default:
return Z_STREAM_ERROR;
}
#ifdef NEED_DUMMY_RETURN
return Z_STREAM_ERROR;
#endif
}
int ZEXPORT inflateSetDictionary(z, dictionary, dictLength)
z_streamp z;
const Bytef *dictionary;
uInt dictLength;
{
uInt length = dictLength;
inflate_state* s;
if (z == Z_NULL || z->state == Z_NULL || ((inflate_state*)z->state)->mode != DICT0)
return Z_STREAM_ERROR;
s = (inflate_state*)z->state;
if (adler32(1L, dictionary, dictLength) != z->adler) return Z_DATA_ERROR;
z->adler = 1L;
if (length >= ((uInt)1<<s->wbits))
{
length = (1<<s->wbits)-1;
dictionary += dictLength - length;
}
inflate_set_dictionary(s->blocks, dictionary, length);
s->mode = BLOCKS;
return Z_OK;
}
int ZEXPORT inflateSync(z)
z_streamp z;
{
uInt n;
Bytef *p;
uInt m;
uLong r, w;
inflate_state* s;
if (z == Z_NULL || z->state == Z_NULL)
return Z_STREAM_ERROR;
s = (inflate_state*)z->state;
if (s->mode != BAD)
{
s->mode = BAD;
s->sub.marker = 0;
}
if ((n = z->avail_in) == 0)
return Z_BUF_ERROR;
p = z->next_in;
m = s->sub.marker;
while (n && m < 4)
{
static const Byte mark[4] = {0, 0, 0xff, 0xff};
if (*p == mark[m])
m++;
else if (*p)
m = 0;
else
m = 4 - m;
p++, n--;
}
z->total_in += p - z->next_in;
z->next_in = p;
z->avail_in = n;
s->sub.marker = m;
if (m != 4)
return Z_DATA_ERROR;
r = z->total_in; w = z->total_out;
inflateReset(z);
z->total_in = r; z->total_out = w;
s->mode = BLOCKS;
return Z_OK;
}
int ZEXPORT inflateSyncPoint(z)
z_streamp z;
{
if (z == Z_NULL || z->state == Z_NULL || ((inflate_state*)z->state)->blocks == Z_NULL)
return Z_STREAM_ERROR;
return inflate_blocks_sync_point(((inflate_state*)z->state)->blocks);
}
#undef NEEDBYTE
#undef NEXTBYTE
typedef struct inflate_huft_s FAR inflate_huft;
struct inflate_huft_s {
union {
struct {
Byte Exop;
Byte Bits;
} what;
uInt pad;
} word;
uInt base;
};
#define MANY 1440
static int inflate_trees_bits OF((
uIntf *,
uIntf *,
inflate_huft * FAR *,
inflate_huft *,
z_streamp));
static int inflate_trees_dynamic OF((
uInt,
uInt,
uIntf *,
uIntf *,
uIntf *,
inflate_huft * FAR *,
inflate_huft * FAR *,
inflate_huft *,
z_streamp));
static int inflate_trees_fixed OF((
uIntf *,
uIntf *,
inflate_huft * FAR *,
inflate_huft * FAR *,
z_streamp));
struct inflate_codes_state;
typedef struct inflate_codes_state FAR inflate_codes_statef;
static inflate_codes_statef *inflate_codes_new OF((
uInt, uInt,
inflate_huft *, inflate_huft *,
z_streamp ));
static int inflate_codes OF((
inflate_blocks_statef *,
z_streamp ,
int));
static void inflate_codes_free OF((
inflate_codes_statef *,
z_streamp ));
#ifndef _INFUTIL_H
#define _INFUTIL_H
typedef enum {
TYPE,
LENS,
STORED,
TABLE,
BTREE,
DTREE,
CODES,
DRY,
DONEB,
BADB}
inflate_block_mode;
struct inflate_blocks_state {
inflate_block_mode mode;
union {
uInt left;
struct {
uInt table;
uInt index;
uIntf *blens;
uInt bb;
inflate_huft *tb;
} trees;
struct {
inflate_codes_statef
*codes;
} decode;
} sub;
uInt last;
uInt bitk;
uLong bitb;
inflate_huft *hufts;
Bytef *window;
Bytef *end;
Bytef *read;
Bytef *write;
check_func checkfn;
uLong check;
};
#define UPDBITS {s->bitb=b;s->bitk=k;}
#define UPDIN {z->avail_in=n;z->total_in+=p-z->next_in;z->next_in=p;}
#define UPDOUT {s->write=q;}
#define UPDATE {UPDBITS UPDIN UPDOUT}
#define LEAVE {UPDATE return inflate_flush(s,z,r);}
#define LOADIN {p=z->next_in;n=z->avail_in;b=s->bitb;k=s->bitk;}
#define NEEDBYTE {if(n)r=Z_OK;else LEAVE}
#define NEXTBYTE (n--,*p++)
#define NEEDBITS(j) {while(k<(j)){NEEDBYTE;b|=((uLong)NEXTBYTE)<<k;k+=8;}}
#define DUMPBITS(j) {b>>=(j);k-=(j);}
#define WAVAIL (uInt)(q<s->read?s->read-q-1:s->end-q)
#define LOADOUT {q=s->write;m=(uInt)WAVAIL;}
#define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=(uInt)WAVAIL;}}
#define FLUSH {UPDOUT r=inflate_flush(s,z,r); LOADOUT}
#define NEEDOUT {if(m==0){WRAP if(m==0){FLUSH WRAP if(m==0) LEAVE}}r=Z_OK;}
#define OUTBYTE(a) {*q++=(Byte)(a);m--;}
#define LOAD {LOADIN LOADOUT}
static uInt inflate_mask[17] = {
0x0000,
0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
};
static int inflate_flush OF((
inflate_blocks_statef *,
z_streamp ,
int));
#ifndef NO_DUMMY_DECL
struct internal_state {int dummy;};
#endif
#endif
#ifndef NO_DUMMY_DECL
struct inflate_codes_state {int dummy;};
#endif
#define exop word.what.Exop
#define bits word.what.Bits
static const uInt border[] = {
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
static void inflate_blocks_reset(s, z, c)
inflate_blocks_statef *s;
z_streamp z;
uLongf *c;
{
if (c != Z_NULL)
*c = s->check;
if (s->mode == BTREE || s->mode == DTREE)
ZFREE(z, s->sub.trees.blens);
if (s->mode == CODES)
inflate_codes_free(s->sub.decode.codes, z);
s->mode = TYPE;
s->bitk = 0;
s->bitb = 0;
s->read = s->write = s->window;
if (s->checkfn != Z_NULL)
z->adler = s->check = (*s->checkfn)(0L, (const Bytef *)Z_NULL, 0);
Tracev((stderr, "inflate: blocks reset\n"));
}
static inflate_blocks_statef *inflate_blocks_new(z, c, w)
z_streamp z;
check_func c;
uInt w;
{
inflate_blocks_statef *s;
if ((s = (inflate_blocks_statef *)ZALLOC
(z,1,sizeof(struct inflate_blocks_state))) == Z_NULL)
return s;
if ((s->hufts =
(inflate_huft *)ZALLOC(z, sizeof(inflate_huft), MANY)) == Z_NULL)
{
ZFREE(z, s);
return Z_NULL;
}
if ((s->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
{
ZFREE(z, s->hufts);
ZFREE(z, s);
return Z_NULL;
}
s->end = s->window + w;
s->checkfn = c;
s->mode = TYPE;
Tracev((stderr, "inflate: blocks allocated\n"));
inflate_blocks_reset(s, z, Z_NULL);
return s;
}
static int inflate_blocks(s, z, r)
inflate_blocks_statef *s;
z_streamp z;
int r;
{
uInt t;
uLong b;
uInt k;
Bytef *p;
uInt n;
Bytef *q;
uInt m;
LOAD
while (1) switch (s->mode)
{
case TYPE:
NEEDBITS(3)
t = (uInt)b & 7;
s->last = t & 1;
switch (t >> 1)
{
case 0:
Tracev((stderr, "inflate: stored block%s\n",
s->last ? " (last)" : ""));
DUMPBITS(3)
t = k & 7;
DUMPBITS(t)
s->mode = LENS;
break;
case 1:
Tracev((stderr, "inflate: fixed codes block%s\n",
s->last ? " (last)" : ""));
{
uInt bl, bd;
inflate_huft *tl, *td;
inflate_trees_fixed(&bl, &bd, &tl, &td, z);
s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
if (s->sub.decode.codes == Z_NULL)
{
r = Z_MEM_ERROR;
LEAVE
}
}
DUMPBITS(3)
s->mode = CODES;
break;
case 2:
Tracev((stderr, "inflate: dynamic codes block%s\n",
s->last ? " (last)" : ""));
DUMPBITS(3)
s->mode = TABLE;
break;
case 3:
DUMPBITS(3)
s->mode = BADB;
z->msg = (char*)"invalid block type";
r = Z_DATA_ERROR;
LEAVE
}
break;
case LENS:
NEEDBITS(32)
if ((((~b) >> 16) & 0xffff) != (b & 0xffff))
{
s->mode = BADB;
z->msg = (char*)"invalid stored block lengths";
r = Z_DATA_ERROR;
LEAVE
}
s->sub.left = (uInt)b & 0xffff;
b = k = 0;
Tracev((stderr, "inflate: stored length %u\n", s->sub.left));
s->mode = s->sub.left ? STORED : (s->last ? DRY : TYPE);
break;
case STORED:
if (n == 0)
LEAVE
NEEDOUT
t = s->sub.left;
if (t > n) t = n;
if (t > m) t = m;
zmemcpy(q, p, t);
p += t; n -= t;
q += t; m -= t;
if ((s->sub.left -= t) != 0)
break;
Tracev((stderr, "inflate: stored end, %lu total out\n",
z->total_out + (q >= s->read ? q - s->read :
(s->end - s->read) + (q - s->window))));
s->mode = s->last ? DRY : TYPE;
break;
case TABLE:
NEEDBITS(14)
s->sub.trees.table = t = (uInt)b & 0x3fff;
#ifndef PKZIP_BUG_WORKAROUND
if ((t & 0x1f) > 29 || ((t >> 5) & 0x1f) > 29)
{
s->mode = BADB;
z->msg = (char*)"too many length or distance symbols";
r = Z_DATA_ERROR;
LEAVE
}
#endif
t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
{
r = Z_MEM_ERROR;
LEAVE
}
DUMPBITS(14)
s->sub.trees.index = 0;
Tracev((stderr, "inflate: table sizes ok\n"));
s->mode = BTREE;
case BTREE:
while (s->sub.trees.index < 4 + (s->sub.trees.table >> 10))
{
NEEDBITS(3)
s->sub.trees.blens[border[s->sub.trees.index++]] = (uInt)b & 7;
DUMPBITS(3)
}
while (s->sub.trees.index < 19)
s->sub.trees.blens[border[s->sub.trees.index++]] = 0;
s->sub.trees.bb = 7;
t = inflate_trees_bits(s->sub.trees.blens, &s->sub.trees.bb,
&s->sub.trees.tb, s->hufts, z);
if (t != Z_OK)
{
r = t;
if (r == Z_DATA_ERROR)
{
ZFREE(z, s->sub.trees.blens);
s->mode = BADB;
}
LEAVE
}
s->sub.trees.index = 0;
Tracev((stderr, "inflate: bits tree ok\n"));
s->mode = DTREE;
case DTREE:
while (t = s->sub.trees.table,
s->sub.trees.index < 258 + (t & 0x1f) + ((t >> 5) & 0x1f))
{
inflate_huft *h;
uInt i, j, c;
t = s->sub.trees.bb;
NEEDBITS(t)
h = s->sub.trees.tb + ((uInt)b & inflate_mask[t]);
t = h->bits;
c = h->base;
if (c < 16)
{
DUMPBITS(t)
s->sub.trees.blens[s->sub.trees.index++] = c;
}
else
{
i = c == 18 ? 7 : c - 14;
j = c == 18 ? 11 : 3;
NEEDBITS(t + i)
DUMPBITS(t)
j += (uInt)b & inflate_mask[i];
DUMPBITS(i)
i = s->sub.trees.index;
t = s->sub.trees.table;
if (i + j > 258 + (t & 0x1f) + ((t >> 5) & 0x1f) ||
(c == 16 && i < 1))
{
ZFREE(z, s->sub.trees.blens);
s->mode = BADB;
z->msg = (char*)"invalid bit length repeat";
r = Z_DATA_ERROR;
LEAVE
}
c = c == 16 ? s->sub.trees.blens[i - 1] : 0;
do {
s->sub.trees.blens[i++] = c;
} while (--j);
s->sub.trees.index = i;
}
}
s->sub.trees.tb = Z_NULL;
{
uInt bl, bd;
inflate_huft *tl, *td;
inflate_codes_statef *c;
bl = 9;
bd = 6;
t = s->sub.trees.table;
t = inflate_trees_dynamic(257 + (t & 0x1f), 1 + ((t >> 5) & 0x1f),
s->sub.trees.blens, &bl, &bd, &tl, &td,
s->hufts, z);
if (t != Z_OK)
{
if (t == (uInt)Z_DATA_ERROR)
{
ZFREE(z, s->sub.trees.blens);
s->mode = BADB;
}
r = t;
LEAVE
}
Tracev((stderr, "inflate: trees ok\n"));
if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
{
r = Z_MEM_ERROR;
LEAVE
}
s->sub.decode.codes = c;
}
ZFREE(z, s->sub.trees.blens);
s->mode = CODES;
case CODES:
UPDATE
if ((r = inflate_codes(s, z, r)) != Z_STREAM_END)
return inflate_flush(s, z, r);
r = Z_OK;
inflate_codes_free(s->sub.decode.codes, z);
LOAD
Tracev((stderr, "inflate: codes end, %lu total out\n",
z->total_out + (q >= s->read ? q - s->read :
(s->end - s->read) + (q - s->window))));
if (!s->last)
{
s->mode = TYPE;
break;
}
s->mode = DRY;
case DRY:
FLUSH
if (s->read != s->write)
LEAVE
s->mode = DONEB;
case DONEB:
r = Z_STREAM_END;
LEAVE
case BADB:
r = Z_DATA_ERROR;
LEAVE
default:
r = Z_STREAM_ERROR;
LEAVE
}
}
static int inflate_blocks_free(s, z)
inflate_blocks_statef *s;
z_streamp z;
{
inflate_blocks_reset(s, z, Z_NULL);
ZFREE(z, s->window);
ZFREE(z, s->hufts);
ZFREE(z, s);
Tracev((stderr, "inflate: blocks freed\n"));
return Z_OK;
}
static void inflate_set_dictionary(s, d, n)
inflate_blocks_statef *s;
const Bytef *d;
uInt n;
{
zmemcpy(s->window, d, n);
s->read = s->write = s->window + n;
}
static int inflate_blocks_sync_point(s)
inflate_blocks_statef *s;
{
return s->mode == LENS;
}
#if !defined(BUILDFIXED) && !defined(STDC)
# define BUILDFIXED
#endif
const char inflate_copyright[] =
" inflate 1.1.4 Copyright 1995-2002 Mark Adler ";
#ifndef NO_DUMMY_DECL
struct internal_state {int dummy;};
#endif
#define exop word.what.Exop
#define bits word.what.Bits
static int
huft_build OF((
uIntf *,
uInt,
uInt,
const uIntf *,
const uIntf *,
inflate_huft * FAR*,
uIntf *,
inflate_huft *,
uInt *,
uIntf * ));
static const uInt cplens[31] = {
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
static const uInt cplext[31] = {
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112};
static const uInt cpdist[30] = {
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
8193, 12289, 16385, 24577};
static const uInt cpdext[30] = {
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};
#define BMAX 15
#if 0
uIntf *b;
uInt n;
uInt s;
const uIntf *d;
const uIntf *e;
inflate_huft * FAR *t;
uIntf *m;
inflate_huft *hp;
uInt *hn;
uIntf *v;
#endif
static int
huft_build(uIntf *b, uInt n, uInt s, const uIntf *d, const uIntf *e,
inflate_huft * FAR *t, uIntf *m, inflate_huft *hp, uInt *hn,
uIntf *v)
{
uInt a;
uInt c[BMAX+1];
uInt f;
int g;
int h;
uInt i;
uInt j;
int k;
int l;
uInt mask;
uIntf *p;
inflate_huft *q;
struct inflate_huft_s r;
inflate_huft *u[BMAX];
int w;
uInt x[BMAX+1];
uIntf *xp;
int y;
uInt z;
p = c;
#define C0 *p++ = 0;
#define C2 C0 C0 C0 C0
#define C4 C2 C2 C2 C2
C4
p = b; i = n;
do {
c[*p++]++;
} while (--i);
if (c[0] == n)
{
*t = (inflate_huft *)Z_NULL;
*m = 0;
return Z_OK;
}
l = *m;
for (j = 1; j <= BMAX; j++)
if (c[j])
break;
k = j;
if ((uInt)l < j)
l = j;
for (i = BMAX; i; i--)
if (c[i])
break;
g = i;
if ((uInt)l > i)
l = i;
*m = l;
for (y = 1 << j; j < i; j++, y <<= 1)
if ((y -= c[j]) < 0)
return Z_DATA_ERROR;
if ((y -= c[i]) < 0)
return Z_DATA_ERROR;
c[i] += y;
x[1] = j = 0;
p = c + 1; xp = x + 2;
while (--i) {
*xp++ = (j += *p++);
}
p = b; i = 0;
do {
if ((j = *p++) != 0)
v[x[j]++] = i;
} while (++i < n);
n = x[g];
x[0] = i = 0;
p = v;
h = -1;
w = -l;
u[0] = (inflate_huft *)Z_NULL;
q = (inflate_huft *)Z_NULL;
z = 0;
for (; k <= g; k++)
{
a = c[k];
while (a--)
{
while (k > w + l)
{
h++;
w += l;
z = g - w;
z = z > (uInt)l ? l : z;
if ((f = 1 << (j = k - w)) > a + 1)
{
f -= a + 1;
xp = c + k;
if (j < z)
while (++j < z)
{
if ((f <<= 1) <= *++xp)
break;
f -= *xp;
}
}
z = 1 << j;
if (*hn + z > MANY)
return Z_DATA_ERROR;
u[h] = q = hp + *hn;
*hn += z;
if (h)
{
x[h] = i;
r.bits = (Byte)l;
r.exop = (Byte)j;
j = i >> (w - l);
r.base = (uInt)(q - u[h-1] - j);
u[h-1][j] = r;
}
else
*t = q;
}
r.bits = (Byte)(k - w);
if (p >= v + n)
r.exop = 128 + 64;
else if (*p < s)
{
r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);
r.base = *p++;
}
else
{
r.exop = (Byte)(e[*p - s] + 16 + 64);
r.base = d[*p++ - s];
}
f = 1 << (k - w);
for (j = i >> w; j < z; j += f)
q[j] = r;
for (j = 1 << (k - 1); i & j; j >>= 1)
i ^= j;
i ^= j;
mask = (1 << w) - 1;
while ((i & mask) != x[h])
{
h--;
w -= l;
mask = (1 << w) - 1;
}
}
}
return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
}
static int inflate_trees_bits(c, bb, tb, hp, z)
uIntf *c;
uIntf *bb;
inflate_huft * FAR *tb;
inflate_huft *hp;
z_streamp z;
{
int r;
uInt hn = 0;
uIntf *v;
if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL)
return Z_MEM_ERROR;
r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL,
tb, bb, hp, &hn, v);
if (r == Z_DATA_ERROR)
z->msg = (char*)"oversubscribed dynamic bit lengths tree";
else if (r == Z_BUF_ERROR || *bb == 0)
{
z->msg = (char*)"incomplete dynamic bit lengths tree";
r = Z_DATA_ERROR;
}
ZFREE(z, v);
return r;
}
static int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, hp, z)
uInt nl;
uInt nd;
uIntf *c;
uIntf *bl;
uIntf *bd;
inflate_huft * FAR *tl;
inflate_huft * FAR *td;
inflate_huft *hp;
z_streamp z;
{
int r;
uInt hn = 0;
uIntf *v;
if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
return Z_MEM_ERROR;
r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
if (r != Z_OK || *bl == 0)
{
if (r == Z_DATA_ERROR)
z->msg = (char*)"oversubscribed literal/length tree";
else if (r != Z_MEM_ERROR)
{
z->msg = (char*)"incomplete literal/length tree";
r = Z_DATA_ERROR;
}
ZFREE(z, v);
return r;
}
r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
if (r != Z_OK || (*bd == 0 && nl > 257))
{
if (r == Z_DATA_ERROR)
z->msg = (char*)"oversubscribed distance tree";
else if (r == Z_BUF_ERROR) {
#ifdef PKZIP_BUG_WORKAROUND
r = Z_OK;
}
#else
z->msg = (char*)"incomplete distance tree";
r = Z_DATA_ERROR;
}
else if (r != Z_MEM_ERROR)
{
z->msg = (char*)"empty distance tree with lengths";
r = Z_DATA_ERROR;
}
ZFREE(z, v);
return r;
#endif
}
ZFREE(z, v);
return Z_OK;
}
#ifdef BUILDFIXED
static int fixed_built = 0;
#define FIXEDH 544
static inflate_huft *fixed_mem = NULL;
static uInt fixed_bl;
static uInt fixed_bd;
static inflate_huft *fixed_tl;
static inflate_huft *fixed_td;
#else
static uInt fixed_bl = 9;
static uInt fixed_bd = 5;
static inflate_huft fixed_tl[] = {
{{{96,7}},256}, {{{0,8}},80}, {{{0,8}},16}, {{{84,8}},115},
{{{82,7}},31}, {{{0,8}},112}, {{{0,8}},48}, {{{0,9}},192},
{{{80,7}},10}, {{{0,8}},96}, {{{0,8}},32}, {{{0,9}},160},
{{{0,8}},0}, {{{0,8}},128}, {{{0,8}},64}, {{{0,9}},224},
{{{80,7}},6}, {{{0,8}},88}, {{{0,8}},24}, {{{0,9}},144},
{{{83,7}},59}, {{{0,8}},120}, {{{0,8}},56}, {{{0,9}},208},
{{{81,7}},17}, {{{0,8}},104}, {{{0,8}},40}, {{{0,9}},176},
{{{0,8}},8}, {{{0,8}},136}, {{{0,8}},72}, {{{0,9}},240},
{{{80,7}},4}, {{{0,8}},84}, {{{0,8}},20}, {{{85,8}},227},
{{{83,7}},43}, {{{0,8}},116}, {{{0,8}},52}, {{{0,9}},200},
{{{81,7}},13}, {{{0,8}},100}, {{{0,8}},36}, {{{0,9}},168},
{{{0,8}},4}, {{{0,8}},132}, {{{0,8}},68}, {{{0,9}},232},
{{{80,7}},8}, {{{0,8}},92}, {{{0,8}},28}, {{{0,9}},152},
{{{84,7}},83}, {{{0,8}},124}, {{{0,8}},60}, {{{0,9}},216},
{{{82,7}},23}, {{{0,8}},108}, {{{0,8}},44}, {{{0,9}},184},
{{{0,8}},12}, {{{0,8}},140}, {{{0,8}},76}, {{{0,9}},248},
{{{80,7}},3}, {{{0,8}},82}, {{{0,8}},18}, {{{85,8}},163},
{{{83,7}},35}, {{{0,8}},114}, {{{0,8}},50}, {{{0,9}},196},
{{{81,7}},11}, {{{0,8}},98}, {{{0,8}},34}, {{{0,9}},164},
{{{0,8}},2}, {{{0,8}},130}, {{{0,8}},66}, {{{0,9}},228},
{{{80,7}},7}, {{{0,8}},90}, {{{0,8}},26}, {{{0,9}},148},
{{{84,7}},67}, {{{0,8}},122}, {{{0,8}},58}, {{{0,9}},212},
{{{82,7}},19}, {{{0,8}},106}, {{{0,8}},42}, {{{0,9}},180},
{{{0,8}},10}, {{{0,8}},138}, {{{0,8}},74}, {{{0,9}},244},
{{{80,7}},5}, {{{0,8}},86}, {{{0,8}},22}, {{{192,8}},0},
{{{83,7}},51}, {{{0,8}},118}, {{{0,8}},54}, {{{0,9}},204},
{{{81,7}},15}, {{{0,8}},102}, {{{0,8}},38}, {{{0,9}},172},
{{{0,8}},6}, {{{0,8}},134}, {{{0,8}},70}, {{{0,9}},236},
{{{80,7}},9}, {{{0,8}},94}, {{{0,8}},30}, {{{0,9}},156},
{{{84,7}},99}, {{{0,8}},126}, {{{0,8}},62}, {{{0,9}},220},
{{{82,7}},27}, {{{0,8}},110}, {{{0,8}},46}, {{{0,9}},188},
{{{0,8}},14}, {{{0,8}},142}, {{{0,8}},78}, {{{0,9}},252},
{{{96,7}},256}, {{{0,8}},81}, {{{0,8}},17}, {{{85,8}},131},
{{{82,7}},31}, {{{0,8}},113}, {{{0,8}},49}, {{{0,9}},194},
{{{80,7}},10}, {{{0,8}},97}, {{{0,8}},33}, {{{0,9}},162},
{{{0,8}},1}, {{{0,8}},129}, {{{0,8}},65}, {{{0,9}},226},
{{{80,7}},6}, {{{0,8}},89}, {{{0,8}},25}, {{{0,9}},146},
{{{83,7}},59}, {{{0,8}},121}, {{{0,8}},57}, {{{0,9}},210},
{{{81,7}},17}, {{{0,8}},105}, {{{0,8}},41}, {{{0,9}},178},
{{{0,8}},9}, {{{0,8}},137}, {{{0,8}},73}, {{{0,9}},242},
{{{80,7}},4}, {{{0,8}},85}, {{{0,8}},21}, {{{80,8}},258},
{{{83,7}},43}, {{{0,8}},117}, {{{0,8}},53}, {{{0,9}},202},
{{{81,7}},13}, {{{0,8}},101}, {{{0,8}},37}, {{{0,9}},170},
{{{0,8}},5}, {{{0,8}},133}, {{{0,8}},69}, {{{0,9}},234},
{{{80,7}},8}, {{{0,8}},93}, {{{0,8}},29}, {{{0,9}},154},
{{{84,7}},83}, {{{0,8}},125}, {{{0,8}},61}, {{{0,9}},218},
{{{82,7}},23}, {{{0,8}},109}, {{{0,8}},45}, {{{0,9}},186},
{{{0,8}},13}, {{{0,8}},141}, {{{0,8}},77}, {{{0,9}},250},
{{{80,7}},3}, {{{0,8}},83}, {{{0,8}},19}, {{{85,8}},195},
{{{83,7}},35}, {{{0,8}},115}, {{{0,8}},51}, {{{0,9}},198},
{{{81,7}},11}, {{{0,8}},99}, {{{0,8}},35}, {{{0,9}},166},
{{{0,8}},3}, {{{0,8}},131}, {{{0,8}},67}, {{{0,9}},230},
{{{80,7}},7}, {{{0,8}},91}, {{{0,8}},27}, {{{0,9}},150},
{{{84,7}},67}, {{{0,8}},123}, {{{0,8}},59}, {{{0,9}},214},
{{{82,7}},19}, {{{0,8}},107}, {{{0,8}},43}, {{{0,9}},182},
{{{0,8}},11}, {{{0,8}},139}, {{{0,8}},75}, {{{0,9}},246},
{{{80,7}},5}, {{{0,8}},87}, {{{0,8}},23}, {{{192,8}},0},
{{{83,7}},51}, {{{0,8}},119}, {{{0,8}},55}, {{{0,9}},206},
{{{81,7}},15}, {{{0,8}},103}, {{{0,8}},39}, {{{0,9}},174},
{{{0,8}},7}, {{{0,8}},135}, {{{0,8}},71}, {{{0,9}},238},
{{{80,7}},9}, {{{0,8}},95}, {{{0,8}},31}, {{{0,9}},158},
{{{84,7}},99}, {{{0,8}},127}, {{{0,8}},63}, {{{0,9}},222},
{{{82,7}},27}, {{{0,8}},111}, {{{0,8}},47}, {{{0,9}},190},
{{{0,8}},15}, {{{0,8}},143}, {{{0,8}},79}, {{{0,9}},254},
{{{96,7}},256}, {{{0,8}},80}, {{{0,8}},16}, {{{84,8}},115},
{{{82,7}},31}, {{{0,8}},112}, {{{0,8}},48}, {{{0,9}},193},
{{{80,7}},10}, {{{0,8}},96}, {{{0,8}},32}, {{{0,9}},161},
{{{0,8}},0}, {{{0,8}},128}, {{{0,8}},64}, {{{0,9}},225},
{{{80,7}},6}, {{{0,8}},88}, {{{0,8}},24}, {{{0,9}},145},
{{{83,7}},59}, {{{0,8}},120}, {{{0,8}},56}, {{{0,9}},209},
{{{81,7}},17}, {{{0,8}},104}, {{{0,8}},40}, {{{0,9}},177},
{{{0,8}},8}, {{{0,8}},136}, {{{0,8}},72}, {{{0,9}},241},
{{{80,7}},4}, {{{0,8}},84}, {{{0,8}},20}, {{{85,8}},227},
{{{83,7}},43}, {{{0,8}},116}, {{{0,8}},52}, {{{0,9}},201},
{{{81,7}},13}, {{{0,8}},100}, {{{0,8}},36}, {{{0,9}},169},
{{{0,8}},4}, {{{0,8}},132}, {{{0,8}},68}, {{{0,9}},233},
{{{80,7}},8}, {{{0,8}},92}, {{{0,8}},28}, {{{0,9}},153},
{{{84,7}},83}, {{{0,8}},124}, {{{0,8}},60}, {{{0,9}},217},
{{{82,7}},23}, {{{0,8}},108}, {{{0,8}},44}, {{{0,9}},185},
{{{0,8}},12}, {{{0,8}},140}, {{{0,8}},76}, {{{0,9}},249},
{{{80,7}},3}, {{{0,8}},82}, {{{0,8}},18}, {{{85,8}},163},
{{{83,7}},35}, {{{0,8}},114}, {{{0,8}},50}, {{{0,9}},197},
{{{81,7}},11}, {{{0,8}},98}, {{{0,8}},34}, {{{0,9}},165},
{{{0,8}},2}, {{{0,8}},130}, {{{0,8}},66}, {{{0,9}},229},
{{{80,7}},7}, {{{0,8}},90}, {{{0,8}},26}, {{{0,9}},149},
{{{84,7}},67}, {{{0,8}},122}, {{{0,8}},58}, {{{0,9}},213},
{{{82,7}},19}, {{{0,8}},106}, {{{0,8}},42}, {{{0,9}},181},
{{{0,8}},10}, {{{0,8}},138}, {{{0,8}},74}, {{{0,9}},245},
{{{80,7}},5}, {{{0,8}},86}, {{{0,8}},22}, {{{192,8}},0},
{{{83,7}},51}, {{{0,8}},118}, {{{0,8}},54}, {{{0,9}},205},
{{{81,7}},15}, {{{0,8}},102}, {{{0,8}},38}, {{{0,9}},173},
{{{0,8}},6}, {{{0,8}},134}, {{{0,8}},70}, {{{0,9}},237},
{{{80,7}},9}, {{{0,8}},94}, {{{0,8}},30}, {{{0,9}},157},
{{{84,7}},99}, {{{0,8}},126}, {{{0,8}},62}, {{{0,9}},221},
{{{82,7}},27}, {{{0,8}},110}, {{{0,8}},46}, {{{0,9}},189},
{{{0,8}},14}, {{{0,8}},142}, {{{0,8}},78}, {{{0,9}},253},
{{{96,7}},256}, {{{0,8}},81}, {{{0,8}},17}, {{{85,8}},131},
{{{82,7}},31}, {{{0,8}},113}, {{{0,8}},49}, {{{0,9}},195},
{{{80,7}},10}, {{{0,8}},97}, {{{0,8}},33}, {{{0,9}},163},
{{{0,8}},1}, {{{0,8}},129}, {{{0,8}},65}, {{{0,9}},227},
{{{80,7}},6}, {{{0,8}},89}, {{{0,8}},25}, {{{0,9}},147},
{{{83,7}},59}, {{{0,8}},121}, {{{0,8}},57}, {{{0,9}},211},
{{{81,7}},17}, {{{0,8}},105}, {{{0,8}},41}, {{{0,9}},179},
{{{0,8}},9}, {{{0,8}},137}, {{{0,8}},73}, {{{0,9}},243},
{{{80,7}},4}, {{{0,8}},85}, {{{0,8}},21}, {{{80,8}},258},
{{{83,7}},43}, {{{0,8}},117}, {{{0,8}},53}, {{{0,9}},203},
{{{81,7}},13}, {{{0,8}},101}, {{{0,8}},37}, {{{0,9}},171},
{{{0,8}},5}, {{{0,8}},133}, {{{0,8}},69}, {{{0,9}},235},
{{{80,7}},8}, {{{0,8}},93}, {{{0,8}},29}, {{{0,9}},155},
{{{84,7}},83}, {{{0,8}},125}, {{{0,8}},61}, {{{0,9}},219},
{{{82,7}},23}, {{{0,8}},109}, {{{0,8}},45}, {{{0,9}},187},
{{{0,8}},13}, {{{0,8}},141}, {{{0,8}},77}, {{{0,9}},251},
{{{80,7}},3}, {{{0,8}},83}, {{{0,8}},19}, {{{85,8}},195},
{{{83,7}},35}, {{{0,8}},115}, {{{0,8}},51}, {{{0,9}},199},
{{{81,7}},11}, {{{0,8}},99}, {{{0,8}},35}, {{{0,9}},167},
{{{0,8}},3}, {{{0,8}},131}, {{{0,8}},67}, {{{0,9}},231},
{{{80,7}},7}, {{{0,8}},91}, {{{0,8}},27}, {{{0,9}},151},
{{{84,7}},67}, {{{0,8}},123}, {{{0,8}},59}, {{{0,9}},215},
{{{82,7}},19}, {{{0,8}},107}, {{{0,8}},43}, {{{0,9}},183},
{{{0,8}},11}, {{{0,8}},139}, {{{0,8}},75}, {{{0,9}},247},
{{{80,7}},5}, {{{0,8}},87}, {{{0,8}},23}, {{{192,8}},0},
{{{83,7}},51}, {{{0,8}},119}, {{{0,8}},55}, {{{0,9}},207},
{{{81,7}},15}, {{{0,8}},103}, {{{0,8}},39}, {{{0,9}},175},
{{{0,8}},7}, {{{0,8}},135}, {{{0,8}},71}, {{{0,9}},239},
{{{80,7}},9}, {{{0,8}},95}, {{{0,8}},31}, {{{0,9}},159},
{{{84,7}},99}, {{{0,8}},127}, {{{0,8}},63}, {{{0,9}},223},
{{{82,7}},27}, {{{0,8}},111}, {{{0,8}},47}, {{{0,9}},191},
{{{0,8}},15}, {{{0,8}},143}, {{{0,8}},79}, {{{0,9}},255}
};
static inflate_huft fixed_td[] = {
{{{80,5}},1}, {{{87,5}},257}, {{{83,5}},17}, {{{91,5}},4097},
{{{81,5}},5}, {{{89,5}},1025}, {{{85,5}},65}, {{{93,5}},16385},
{{{80,5}},3}, {{{88,5}},513}, {{{84,5}},33}, {{{92,5}},8193},
{{{82,5}},9}, {{{90,5}},2049}, {{{86,5}},129}, {{{192,5}},24577},
{{{80,5}},2}, {{{87,5}},385}, {{{83,5}},25}, {{{91,5}},6145},
{{{81,5}},7}, {{{89,5}},1537}, {{{85,5}},97}, {{{93,5}},24577},
{{{80,5}},4}, {{{88,5}},769}, {{{84,5}},49}, {{{92,5}},12289},
{{{82,5}},13}, {{{90,5}},3073}, {{{86,5}},193}, {{{192,5}},24577}
};
#endif
static int inflate_trees_fixed(bl, bd, tl, td, z)
uIntf *bl;
uIntf *bd;
inflate_huft * FAR *tl;
inflate_huft * FAR *td;
z_streamp z;
{
#ifdef BUILDFIXED
if (!fixed_built)
{
int k;
uInt f = 0;
uIntf *c;
uIntf *v;
if ((c = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
return Z_MEM_ERROR;
if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
{
ZFREE(z, c);
return Z_MEM_ERROR;
}
if ((fixed_mem = (inflate_huft*)ZALLOC(z, FIXEDH, sizeof(inflate_huft))) == Z_NULL)
{
ZFREE(z, c);
ZFREE(z, v);
return Z_MEM_ERROR;
}
for (k = 0; k < 144; k++)
c[k] = 8;
for (; k < 256; k++)
c[k] = 9;
for (; k < 280; k++)
c[k] = 7;
for (; k < 288; k++)
c[k] = 8;
fixed_bl = 9;
huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl,
fixed_mem, &f, v);
for (k = 0; k < 30; k++)
c[k] = 5;
fixed_bd = 5;
huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd,
fixed_mem, &f, v);
ZFREE(z, v);
ZFREE(z, c);
fixed_built = 1;
}
#endif
*bl = fixed_bl;
*bd = fixed_bd;
*tl = fixed_tl;
*td = fixed_td;
return Z_OK;
}
static int inflate_fast OF((
uInt,
uInt,
inflate_huft *,
inflate_huft *,
inflate_blocks_statef *,
z_streamp ));
#define exop word.what.Exop
#define bits word.what.Bits
typedef enum {
START,
LEN,
LENEXT,
DIST,
DISTEXT,
COPY,
LIT,
WASH,
END,
BADCODE}
inflate_codes_mode;
struct inflate_codes_state {
inflate_codes_mode mode;
uInt len;
union {
struct {
inflate_huft *tree;
uInt need;
} code;
uInt lit;
struct {
uInt get;
uInt dist;
} copy;
} sub;
Byte lbits;
Byte dbits;
inflate_huft *ltree;
inflate_huft *dtree;
};
static inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
uInt bl, bd;
inflate_huft *tl;
inflate_huft *td;
z_streamp z;
{
inflate_codes_statef *c;
if ((c = (inflate_codes_statef *)
ZALLOC(z,1,sizeof(struct inflate_codes_state))) != Z_NULL)
{
c->mode = START;
c->lbits = (Byte)bl;
c->dbits = (Byte)bd;
c->ltree = tl;
c->dtree = td;
Tracev((stderr, "inflate: codes new\n"));
}
return c;
}
static int inflate_codes(s, z, r)
inflate_blocks_statef *s;
z_streamp z;
int r;
{
uInt j;
inflate_huft *t;
uInt e;
uLong b;
uInt k;
Bytef *p;
uInt n;
Bytef *q;
uInt m;
Bytef *f;
inflate_codes_statef *c = s->sub.decode.codes;
LOAD
while (1) switch (c->mode)
{
case START:
#ifndef SLOW
if (m >= 258 && n >= 10)
{
UPDATE
r = inflate_fast(c->lbits, c->dbits, c->ltree, c->dtree, s, z);
LOAD
if (r != Z_OK)
{
c->mode = r == Z_STREAM_END ? WASH : BADCODE;
break;
}
}
#endif
c->sub.code.need = c->lbits;
c->sub.code.tree = c->ltree;
c->mode = LEN;
case LEN:
j = c->sub.code.need;
NEEDBITS(j)
t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
DUMPBITS(t->bits)
e = (uInt)(t->exop);
if (e == 0)
{
c->sub.lit = t->base;
Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
"inflate: literal '%c'\n" :
"inflate: literal 0x%02x\n", t->base));
c->mode = LIT;
break;
}
if (e & 16)
{
c->sub.copy.get = e & 15;
c->len = t->base;
c->mode = LENEXT;
break;
}
if ((e & 64) == 0)
{
c->sub.code.need = e;
c->sub.code.tree = t + t->base;
break;
}
if (e & 32)
{
Tracevv((stderr, "inflate: end of block\n"));
c->mode = WASH;
break;
}
c->mode = BADCODE;
z->msg = (char*)"invalid literal/length code";
r = Z_DATA_ERROR;
LEAVE
case LENEXT:
j = c->sub.copy.get;
NEEDBITS(j)
c->len += (uInt)b & inflate_mask[j];
DUMPBITS(j)
c->sub.code.need = c->dbits;
c->sub.code.tree = c->dtree;
Tracevv((stderr, "inflate: length %u\n", c->len));
c->mode = DIST;
case DIST:
j = c->sub.code.need;
NEEDBITS(j)
t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
DUMPBITS(t->bits)
e = (uInt)(t->exop);
if (e & 16)
{
c->sub.copy.get = e & 15;
c->sub.copy.dist = t->base;
c->mode = DISTEXT;
break;
}
if ((e & 64) == 0)
{
c->sub.code.need = e;
c->sub.code.tree = t + t->base;
break;
}
c->mode = BADCODE;
z->msg = (char*)"invalid distance code";
r = Z_DATA_ERROR;
LEAVE
case DISTEXT:
j = c->sub.copy.get;
NEEDBITS(j)
c->sub.copy.dist += (uInt)b & inflate_mask[j];
DUMPBITS(j)
Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist));
c->mode = COPY;
case COPY:
f = q - c->sub.copy.dist;
while (f < s->window)
f += s->end - s->window;
while (c->len)
{
NEEDOUT
OUTBYTE(*f++)
if (f == s->end)
f = s->window;
c->len--;
}
c->mode = START;
break;
case LIT:
NEEDOUT
OUTBYTE(c->sub.lit)
c->mode = START;
break;
case WASH:
if (k > 7)
{
Assert(k < 16, "inflate_codes grabbed too many bytes");
k -= 8;
n++;
p--;
}
FLUSH
if (s->read != s->write)
LEAVE
c->mode = END;
case END:
r = Z_STREAM_END;
LEAVE
case BADCODE:
r = Z_DATA_ERROR;
LEAVE
default:
r = Z_STREAM_ERROR;
LEAVE
}
#ifdef NEED_DUMMY_RETURN
return Z_STREAM_ERROR;
#endif
}
static void inflate_codes_free(c, z)
inflate_codes_statef *c;
z_streamp z;
{
ZFREE(z, c);
Tracev((stderr, "inflate: codes free\n"));
}
#ifndef NO_DUMMY_DECL
struct inflate_codes_state {int dummy;};
#endif
static int inflate_flush(s, z, r)
inflate_blocks_statef *s;
z_streamp z;
int r;
{
uInt n;
Bytef *p;
Bytef *q;
p = z->next_out;
q = s->read;
n = (uInt)((q <= s->write ? s->write : s->end) - q);
if (n > z->avail_out) n = z->avail_out;
if (n && r == Z_BUF_ERROR) r = Z_OK;
z->avail_out -= n;
z->total_out += n;
if (s->checkfn != Z_NULL)
z->adler = s->check = (*s->checkfn)(s->check, q, n);
zmemcpy(p, q, n);
p += n;
q += n;
if (q == s->end)
{
q = s->window;
if (s->write == s->end)
s->write = s->window;
n = (uInt)(s->write - q);
if (n > z->avail_out) n = z->avail_out;
if (n && r == Z_BUF_ERROR) r = Z_OK;
z->avail_out -= n;
z->total_out += n;
if (s->checkfn != Z_NULL)
z->adler = s->check = (*s->checkfn)(s->check, q, n);
zmemcpy(p, q, n);
p += n;
q += n;
}
z->next_out = p;
s->read = q;
return r;
}
#ifndef NO_DUMMY_DECL
struct inflate_codes_state {int dummy;};
#endif
#define exop word.what.Exop
#define bits word.what.Bits
#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
#define UNGRAB {c=z->avail_in-n;c=(k>>3)<c?k>>3:c;n+=c;p-=c;k-=c<<3;}
static int inflate_fast(bl, bd, tl, td, s, z)
uInt bl, bd;
inflate_huft *tl;
inflate_huft *td;
inflate_blocks_statef *s;
z_streamp z;
{
inflate_huft *t;
uInt e;
uLong b;
uInt k;
Bytef *p;
uInt n;
Bytef *q;
uInt m;
uInt ml;
uInt md;
uInt c;
uInt d;
Bytef *r;
LOAD
ml = inflate_mask[bl];
md = inflate_mask[bd];
do {
GRABBITS(20)
if ((e = (t = tl + ((uInt)b & ml))->exop) == 0)
{
DUMPBITS(t->bits)
Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
"inflate: * literal '%c'\n" :
"inflate: * literal 0x%02x\n", t->base));
*q++ = (Byte)t->base;
m--;
continue;
}
do {
DUMPBITS(t->bits)
if (e & 16)
{
e &= 15;
c = t->base + ((uInt)b & inflate_mask[e]);
DUMPBITS(e)
Tracevv((stderr, "inflate: * length %u\n", c));
GRABBITS(15);
e = (t = td + ((uInt)b & md))->exop;
do {
DUMPBITS(t->bits)
if (e & 16)
{
e &= 15;
GRABBITS(e)
d = t->base + ((uInt)b & inflate_mask[e]);
DUMPBITS(e)
Tracevv((stderr, "inflate: * distance %u\n", d));
m -= c;
r = q - d;
if (r < s->window)
{
do {
r += s->end - s->window;
} while (r < s->window);
e = s->end - r;
if (c > e)
{
c -= e;
do {
*q++ = *r++;
} while (--e);
r = s->window;
do {
*q++ = *r++;
} while (--c);
}
else
{
*q++ = *r++; c--;
*q++ = *r++; c--;
do {
*q++ = *r++;
} while (--c);
}
}
else
{
*q++ = *r++; c--;
*q++ = *r++; c--;
do {
*q++ = *r++;
} while (--c);
}
break;
}
else if ((e & 64) == 0)
{
t += t->base;
e = (t += ((uInt)b & inflate_mask[e]))->exop;
}
else
{
z->msg = (char*)"invalid distance code";
UNGRAB
UPDATE
return Z_DATA_ERROR;
}
} while (1);
break;
}
if ((e & 64) == 0)
{
t += t->base;
if ((e = (t += ((uInt)b & inflate_mask[e]))->exop) == 0)
{
DUMPBITS(t->bits)
Tracevv((stderr, t->base >= 0x20 && t->base < 0x7f ?
"inflate: * literal '%c'\n" :
"inflate: * literal 0x%02x\n", t->base));
*q++ = (Byte)t->base;
m--;
break;
}
}
else if (e & 32)
{
Tracevv((stderr, "inflate: * end of block\n"));
UNGRAB
UPDATE
return Z_STREAM_END;
}
else
{
z->msg = (char*)"invalid literal/length code";
UNGRAB
UPDATE
return Z_DATA_ERROR;
}
} while (1);
} while (m >= 258 && n >= 10);
UNGRAB
UPDATE
return Z_OK;
}
#ifndef NO_DUMMY_DECL
struct internal_state {int dummy;};
#endif
#ifndef STDC
extern void exit OF((int));
#endif
const char * ZEXPORT zlibVersion()
{
return ZLIB_VERSION;
}
#ifdef DEBUG_ZLIB
# ifndef verbose
# define verbose 0
# endif
int z_verbose = verbose;
void z_error (m)
char *m;
{
fprintf(stderr, "%s\n", m);
exit(1);
}
#endif
const char * ZEXPORT zError(err)
int err;
{
return ERR_MSG(err);
}
#ifndef HAVE_MEMCPY
void zmemcpy(dest, source, len)
Bytef* dest;
const Bytef* source;
uInt len;
{
if (len == 0) return;
do {
*dest++ = *source++;
} while (--len != 0);
}
int zmemcmp(s1, s2, len)
const Bytef* s1;
const Bytef* s2;
uInt len;
{
uInt j;
for (j = 0; j < len; j++) {
if (s1[j] != s2[j]) return 2*(s1[j] > s2[j])-1;
}
return 0;
}
void zmemzero(dest, len)
Bytef* dest;
uInt len;
{
if (len == 0) return;
do {
*dest++ = 0;
} while (--len != 0);
}
#endif
#ifdef __TURBOC__
#if (defined( __BORLANDC__) || !defined(SMALL_MEDIUM)) && !defined(__32BIT__)
# define MY_ZCALLOC
#define MAX_PTR 10
static int next_ptr = 0;
typedef struct ptr_table_s {
voidpf org_ptr;
voidpf new_ptr;
} ptr_table;
static ptr_table table[MAX_PTR];
voidpf zcalloc (voidpf opaque, unsigned items, unsigned size)
{
voidpf buf = opaque;
ulg bsize = (ulg)items*size;
if (bsize < 65520L) {
buf = farmalloc(bsize);
if (*(ush*)&buf != 0) return buf;
} else {
buf = farmalloc(bsize + 16L);
}
if (buf == NULL || next_ptr >= MAX_PTR) return NULL;
table[next_ptr].org_ptr = buf;
*((ush*)&buf+1) += ((ush)((uch*)buf-0) + 15) >> 4;
*(ush*)&buf = 0;
table[next_ptr++].new_ptr = buf;
return buf;
}
void zcfree (voidpf opaque, voidpf ptr)
{
int n;
if (*(ush*)&ptr != 0) {
farfree(ptr);
return;
}
for (n = 0; n < next_ptr; n++) {
if (ptr != table[n].new_ptr) continue;
farfree(table[n].org_ptr);
while (++n < next_ptr) {
table[n-1] = table[n];
}
next_ptr--;
return;
}
ptr = opaque;
Assert(0, "zcfree: ptr not found");
}
#endif
#endif
#if defined(M_I86) && !defined(__32BIT__)
# define MY_ZCALLOC
#if (!defined(_MSC_VER) || (_MSC_VER <= 600))
# define _halloc halloc
# define _hfree hfree
#endif
voidpf zcalloc (voidpf opaque, unsigned items, unsigned size)
{
if (opaque) opaque = 0;
return _halloc((long)items, size);
}
void zcfree (voidpf opaque, voidpf ptr)
{
if (opaque) opaque = 0;
_hfree(ptr);
}
#endif
#ifndef MY_ZCALLOC
#ifndef STDC
extern voidp calloc OF((uInt items, uInt size));
extern void free OF((voidpf ptr));
#endif
voidpf zcalloc (opaque, items, size)
voidpf opaque;
unsigned items;
unsigned size;
{
if (opaque) items += size - size;
return (voidpf)calloc(items, size);
}
void zcfree (opaque, ptr)
voidpf opaque;
voidpf ptr;
{
_FREE(ptr);
if (opaque) return;
}
#endif
#define BASE 65521L
#define NMAX 5552
#define DO1(buf,i) {s1 += buf[i]; s2 += s1;}
#define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
#define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
#define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
#define DO16(buf) DO8(buf,0); DO8(buf,8);
uLong ZEXPORT
adler32(uLong adler, const Bytef *buf, uInt len)
{
unsigned long s1 = adler & 0xffff;
unsigned long s2 = (adler >> 16) & 0xffff;
int k;
if (buf == Z_NULL) return 1L;
while (len > 0) {
k = len < NMAX ? len : NMAX;
len -= k;
while (k >= 16) {
DO16(buf);
buf += 16;
k -= 16;
}
if (k != 0) do {
s1 += *buf++;
s2 += s1;
} while (--k);
s1 %= BASE;
s2 %= BASE;
}
return (s2 << 16) | s1;
}