#define _Z_UTIL_H
#include "zlib.h"
#ifdef STDC
# include <string.h>
#endif
#ifndef local
# define local static
#endif
#define FAR
typedef unsigned char uch;
typedef uch FAR uchf;
typedef unsigned short ush;
typedef ush FAR ushf;
typedef unsigned long ulg;
extern char *z_errmsg[];
#define ERR_RETURN(strm,err) return (strm->msg=z_errmsg[1-err], err)
#ifndef NULL
#define NULL ((void *) 0)
#endif
#define DEFLATED 8
#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
#if defined(STDC) && !defined(HAVE_MEMCPY) && !defined(NO_MEMCPY)
# define HAVE_MEMCPY
#endif
#ifdef HAVE_MEMCPY
# define zmemcpy memcpy
# define zmemzero(dest, len) memset(dest, 0, len)
#else
# define zmemcpy(d, s, n) bcopy((s), (d), (n))
# define zmemzero bzero
#endif
#ifdef DEBUG_ZLIB
# include <stdio.h>
# ifndef verbose
# define verbose 0
# endif
# define Assert(cond,msg) {if(!(cond)) z_error(msg);}
# define Trace(x) fprintf x
# define Tracev(x) {if (verbose) fprintf x ;}
# define Tracevv(x) {if (verbose>1) fprintf x ;}
# define Tracec(c,x) {if (verbose && (c)) fprintf x ;}
# define Tracecv(c,x) {if (verbose>1 && (c)) fprintf x ;}
#else
# define Assert(cond,msg)
# define Trace(x)
# define Tracev(x)
# define Tracevv(x)
# define Tracec(c,x)
# define Tracecv(c,x)
#endif
typedef uLong (*check_func) OF((uLong check, Bytef *buf, uInt len));
#define ZALLOC(strm, items, size) \
(*((strm)->zalloc))((strm)->opaque, (items), (size))
#define ZFREE(strm, addr, size) \
(*((strm)->zfree))((strm)->opaque, (voidpf)(addr), (size))
#define TRY_FREE(s, p, n) {if (p) ZFREE(s, p, n);}
#define BINARY 0
#define ASCII 1
#define UNKNOWN 2
#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 FLUSH_STATE 124
#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_stream *strm;
int status;
Bytef *pending_buf;
Bytef *pending_out;
int pending;
uLong adler;
int noheader;
Byte data_type;
Byte method;
int minCompr;
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;
ulg compressed_len;
uInt matches;
int last_eob_len;
#ifdef DEBUG_ZLIB
ulg bits_sent;
#endif
ush bi_buf;
int bi_valid;
uInt blocks_in_packet;
} 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)
local void ct_init OF((deflate_state *s));
local int ct_tally OF((deflate_state *s, int dist, int lc));
local ulg ct_flush_block OF((deflate_state *s, charf *buf, ulg stored_len,
int flush));
local void ct_align OF((deflate_state *s));
local void ct_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
int eof));
local void ct_stored_type_only OF((deflate_state *s));
local char zlib_copyright[] = " deflate Copyright 1995 Jean-loup Gailly ";
#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;
} config;
local config configuration_table[10] = {
{0, 0, 0, 0},
{4, 4, 8, 4},
{4, 5, 16, 8},
{4, 6, 32, 32},
{4, 4, 16, 16},
{8, 16, 32, 32},
{8, 16, 128, 128},
{8, 32, 128, 256},
{32, 128, 258, 1024},
{32, 258, 258, 4096}};
#define EQUAL 0
local void fill_window OF((deflate_state *s));
local int deflate_fast OF((deflate_state *s, int flush));
local int deflate_slow OF((deflate_state *s, int flush));
local void lm_init OF((deflate_state *s));
local int longest_match OF((deflate_state *s, IPos cur_match));
local void putShortMSB OF((deflate_state *s, uInt b));
local void flush_pending OF((z_stream *strm));
local int read_buf OF((z_stream *strm, charf *buf, unsigned size));
#ifdef ASMV
void match_init OF((void));
#endif
#ifdef DEBUG_ZLIB
local void check_match OF((deflate_state *s, IPos start, IPos match,
int length));
#endif
#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
#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] = (str))
#define CLEAR_HASH(s) \
s->head[s->hash_size-1] = NIL; \
zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
int deflateInit (strm, level)
z_stream *strm;
int level;
{
return deflateInit2 (strm, level, DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
0, 0);
}
int deflateInit2 (strm, level, method, windowBits, memLevel,
strategy, minCompression)
z_stream *strm;
int level;
int method;
int windowBits;
int memLevel;
int strategy;
int minCompression;
{
deflate_state *s;
int noheader = 0;
if (strm == Z_NULL) return Z_STREAM_ERROR;
strm->msg = Z_NULL;
if (level == Z_DEFAULT_COMPRESSION) level = 6;
if (windowBits < 0) {
noheader = 1;
windowBits = -windowBits;
}
if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != DEFLATED ||
windowBits < 8 || windowBits > 15 || level < 1 || level > 9) {
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);
s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 2*sizeof(ush));
if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
s->pending_buf == Z_NULL) {
strm->msg = z_errmsg[1-Z_MEM_ERROR];
deflateEnd (strm);
return Z_MEM_ERROR;
}
s->d_buf = (ushf *) &(s->pending_buf[s->lit_bufsize]);
s->l_buf = (uchf *) &(s->pending_buf[3*s->lit_bufsize]);
s->level = level;
s->strategy = strategy;
s->method = (Byte)method;
s->minCompr = minCompression;
s->blocks_in_packet = 0;
return deflateReset(strm);
}
int deflateReset (strm)
z_stream *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;
s->adler = 1;
ct_init(s);
lm_init(s);
return Z_OK;
}
local void putShortMSB (s, b)
deflate_state *s;
uInt b;
{
put_byte(s, (Byte)(b >> 8));
put_byte(s, (Byte)(b & 0xff));
}
local void flush_pending(strm)
z_stream *strm;
{
deflate_state *state = (deflate_state *) strm->state;
unsigned len = state->pending;
if (len > strm->avail_out) len = strm->avail_out;
if (len == 0) return;
if (strm->next_out != NULL) {
zmemcpy(strm->next_out, state->pending_out, len);
strm->next_out += len;
}
state->pending_out += len;
strm->total_out += len;
strm->avail_out -= len;
state->pending -= len;
if (state->pending == 0) {
state->pending_out = state->pending_buf;
}
}
int deflate (strm, flush)
z_stream *strm;
int flush;
{
deflate_state *state = (deflate_state *) strm->state;
if (strm == Z_NULL || state == Z_NULL) return Z_STREAM_ERROR;
if (strm->next_in == Z_NULL && strm->avail_in != 0) {
ERR_RETURN(strm, Z_STREAM_ERROR);
}
if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
state->strm = strm;
if (state->status == INIT_STATE) {
uInt header = (DEFLATED + ((state->w_bits-8)<<4)) << 8;
uInt level_flags = (state->level-1) >> 1;
if (level_flags > 3) level_flags = 3;
header |= (level_flags << 6);
header += 31 - (header % 31);
state->status = BUSY_STATE;
putShortMSB(state, header);
}
if (state->pending != 0) {
flush_pending(strm);
if (strm->avail_out == 0) return Z_OK;
}
if (state->status == FLUSH_STATE) {
state->status = BUSY_STATE;
if (flush != Z_NO_FLUSH && flush != Z_FINISH)
return Z_OK;
}
if (state->status == FINISH_STATE && strm->avail_in != 0) {
ERR_RETURN(strm, Z_BUF_ERROR);
}
if (strm->avail_in != 0 || state->lookahead != 0 ||
(flush == Z_FINISH && state->status != FINISH_STATE)) {
int quit;
if (flush == Z_FINISH) {
state->status = FINISH_STATE;
}
if (state->level <= 3) {
quit = deflate_fast(state, flush);
} else {
quit = deflate_slow(state, flush);
}
if (quit || strm->avail_out == 0)
return Z_OK;
}
if (flush != Z_NO_FLUSH && flush != Z_FINISH
&& state->status != FINISH_STATE) {
switch (flush) {
case Z_PARTIAL_FLUSH:
ct_align(state);
break;
case Z_PACKET_FLUSH:
ct_stored_type_only(state);
break;
default:
ct_stored_block(state, (char*)0, 0L, 0);
if (flush == Z_FULL_FLUSH) {
CLEAR_HASH(state);
}
}
flush_pending(strm);
if (strm->avail_out == 0) {
state->status = FLUSH_STATE;
return Z_OK;
}
}
Assert(strm->avail_out > 0, "bug2");
if (flush != Z_FINISH) return Z_OK;
if (state->noheader) return Z_STREAM_END;
putShortMSB(state, (uInt)(state->adler >> 16));
putShortMSB(state, (uInt)(state->adler & 0xffff));
flush_pending(strm);
state->noheader = -1;
return state->pending != 0 ? Z_OK : Z_STREAM_END;
}
int deflateEnd (strm)
z_stream *strm;
{
deflate_state *state = (deflate_state *) strm->state;
if (strm == Z_NULL || state == Z_NULL) return Z_STREAM_ERROR;
TRY_FREE(strm, state->window, state->w_size * 2 * sizeof(Byte));
TRY_FREE(strm, state->prev, state->w_size * sizeof(Pos));
TRY_FREE(strm, state->head, state->hash_size * sizeof(Pos));
TRY_FREE(strm, state->pending_buf, state->lit_bufsize * 2 * sizeof(ush));
ZFREE(strm, state, sizeof(deflate_state));
strm->state = Z_NULL;
return Z_OK;
}
local int read_buf(strm, buf, size)
z_stream *strm;
charf *buf;
unsigned size;
{
unsigned len = strm->avail_in;
deflate_state *state = (deflate_state *) strm->state;
if (len > size) len = size;
if (len == 0) return 0;
strm->avail_in -= len;
if (!state->noheader) {
state->adler = adler32(state->adler, strm->next_in, len);
}
zmemcpy(buf, strm->next_in, len);
strm->next_in += len;
strm->total_in += len;
return (int)len;
}
local void lm_init (s)
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 = MIN_MATCH-1;
s->match_available = 0;
s->ins_h = 0;
#ifdef ASMV
match_init();
#endif
}
#ifndef ASMV
local int longest_match(s, cur_match)
deflate_state *s;
IPos cur_match;
{
unsigned chain_length = s->max_chain_length;
register Bytef *scan = s->window + s->strstart;
register Bytef *match;
register int len;
int best_len = s->prev_length;
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
register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
register ush scan_start = *(ushf*)scan;
register ush scan_end = *(ushf*)(scan+best_len-1);
#else
register Bytef *strend = s->window + s->strstart + MAX_MATCH;
register Byte scan_end1 = scan[best_len-1];
register 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;
}
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 >= s->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);
return best_len;
}
#endif
#ifdef DEBUG_ZLIB
local void check_match(s, start, match, length)
deflate_state *s;
IPos start, match;
int length;
{
if (memcmp((charf *)s->window + match,
(charf *)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 (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
local void fill_window(s)
deflate_state *s;
{
register unsigned n, m;
register 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((charf *)s->window, (charf *)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;
p = &s->prev[n];
do {
m = *--p;
*p = (Pos)(m >= wsize ? m-wsize : NIL);
} while (--n);
more += wsize;
}
if (s->strm->avail_in == 0) return;
Assert(more >= 2, "more < 2");
n = read_buf(s->strm, (charf *)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, flush) { \
ct_flush_block(s, (s->block_start >= 0L ? \
(charf *)&s->window[(unsigned)s->block_start] : \
(charf *)Z_NULL), (long)s->strstart - s->block_start, (flush)); \
s->block_start = s->strstart; \
flush_pending(s->strm); \
Tracev((stderr,"[FLUSH]")); \
}
#define FLUSH_BLOCK(s, flush) { \
FLUSH_BLOCK_ONLY(s, flush); \
if (s->strm->avail_out == 0) return 1; \
}
local int deflate_fast(s, flush)
deflate_state *s;
int flush;
{
IPos hash_head = NIL;
int bflush;
s->prev_length = MIN_MATCH-1;
for (;;) {
if (s->lookahead < MIN_LOOKAHEAD) {
fill_window(s);
if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
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 > s->lookahead) s->match_length = s->lookahead;
}
if (s->match_length >= MIN_MATCH) {
check_match(s, s->strstart, s->match_start, s->match_length);
bflush = ct_tally(s, s->strstart - s->match_start,
s->match_length - MIN_MATCH);
s->lookahead -= s->match_length;
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 {
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]));
bflush = ct_tally (s, 0, s->window[s->strstart]);
s->lookahead--;
s->strstart++;
}
if (bflush) FLUSH_BLOCK(s, Z_NO_FLUSH);
}
FLUSH_BLOCK(s, flush);
return 0;
}
local int deflate_slow(s, flush)
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 1;
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 > s->lookahead) s->match_length = s->lookahead;
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);
bflush = ct_tally(s, s->strstart -1 - s->prev_match,
s->prev_length - MIN_MATCH);
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, Z_NO_FLUSH);
} else if (s->match_available) {
Tracevv((stderr,"%c", s->window[s->strstart-1]));
if (ct_tally (s, 0, s->window[s->strstart-1])) {
FLUSH_BLOCK_ONLY(s, Z_NO_FLUSH);
}
s->strstart++;
s->lookahead--;
if (s->strm->avail_out == 0) return 1;
} 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]));
ct_tally (s, 0, s->window[s->strstart-1]);
s->match_available = 0;
}
FLUSH_BLOCK(s, flush);
return 0;
}
#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
local 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};
local 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};
local int extra_blbits[BL_CODES]
= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
local 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))
local ct_data static_ltree[L_CODES+2];
local ct_data static_dtree[D_CODES];
local uch dist_code[512];
local uch length_code[MAX_MATCH-MIN_MATCH+1];
local int base_length[LENGTH_CODES];
local int base_dist[D_CODES];
struct static_tree_desc_s {
ct_data *static_tree;
intf *extra_bits;
int extra_base;
int elems;
int max_length;
};
local static_tree_desc static_l_desc =
{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
local static_tree_desc static_d_desc =
{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
local static_tree_desc static_bl_desc =
{(ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
local void ct_static_init OF((void));
local void init_block OF((deflate_state *s));
local void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
local void gen_bitlen OF((deflate_state *s, tree_desc *desc));
local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count));
local void build_tree OF((deflate_state *s, tree_desc *desc));
local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
local void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
local int build_bl_tree OF((deflate_state *s));
local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
int blcodes));
local void compress_block OF((deflate_state *s, ct_data *ltree,
ct_data *dtree));
local void set_data_type OF((deflate_state *s));
local unsigned bi_reverse OF((unsigned value, int length));
local void bi_windup OF((deflate_state *s));
local void bi_flush OF((deflate_state *s));
local void copy_block OF((deflate_state *s, charf *buf, unsigned len,
int header));
#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 (verbose>1) fprintf(stderr,"\ncd %3d ",(c)); \
send_bits(s, tree[c].Code, tree[c].Len); }
#endif
#define d_code(dist) \
((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
#define put_short(s, w) { \
put_byte(s, (uch)((w) & 0xff)); \
put_byte(s, (uch)((ush)(w) >> 8)); \
}
#ifdef DEBUG_ZLIB
local void send_bits OF((deflate_state *s, int value, int length));
local void send_bits(s, value, length)
deflate_state *s;
int value;
int length;
{
Tracev((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
#define MAX(a,b) (a >= b ? a : b)
local void ct_static_init()
{
int n;
int bits;
int length;
int code;
int dist;
ush bl_count[MAX_BITS+1];
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, "ct_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, "ct_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, "ct_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(n, 5);
}
}
local void ct_init(s)
deflate_state *s;
{
if (static_dtree[0].Len == 0) {
ct_static_init();
}
s->compressed_len = 0L;
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->bits_sent = 0L;
#endif
s->blocks_in_packet = 0;
init_block(s);
}
local void init_block(s)
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]))
local void pqdownheap(s, tree, k)
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;
}
local void gen_bitlen(s, desc)
deflate_state *s;
tree_desc *desc;
{
ct_data *tree = desc->dyn_tree;
int max_code = desc->max_code;
ct_data *stree = desc->stat_desc->static_tree;
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--;
}
}
}
local void gen_codes (tree, max_code, bl_count)
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);
Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
}
}
local void build_tree(s, desc)
deflate_state *s;
tree_desc *desc;
{
ct_data *tree = desc->dyn_tree;
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);
}
local void scan_tree (s, tree, max_code)
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;
}
}
}
local void send_tree (s, tree, max_code)
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;
}
}
}
local int build_bl_tree(s)
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;
}
local void send_all_trees(s, lcodes, dcodes, blcodes)
deflate_state *s;
int lcodes, dcodes, 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));
}
local void ct_stored_block(s, buf, stored_len, eof)
deflate_state *s;
charf *buf;
ulg stored_len;
int eof;
{
send_bits(s, (STORED_BLOCK<<1)+eof, 3);
s->compressed_len = (s->compressed_len + 3 + 7) & ~7L;
s->compressed_len += (stored_len + 4) << 3;
copy_block(s, buf, (unsigned)stored_len, 1);
}
local void ct_stored_type_only(s)
deflate_state *s;
{
send_bits(s, (STORED_BLOCK << 1), 3);
bi_windup(s);
s->compressed_len = (s->compressed_len + 3) & ~7L;
}
local void ct_align(s)
deflate_state *s;
{
send_bits(s, STATIC_TREES<<1, 3);
send_code(s, END_BLOCK, static_ltree);
s->compressed_len += 10L;
bi_flush(s);
if (s->last_eob_len + 10 - s->bi_valid < 9) {
send_bits(s, STATIC_TREES<<1, 3);
send_code(s, END_BLOCK, static_ltree);
s->compressed_len += 10L;
bi_flush(s);
}
s->last_eob_len = 7;
}
local ulg ct_flush_block(s, buf, stored_len, flush)
deflate_state *s;
charf *buf;
ulg stored_len;
int flush;
{
ulg opt_lenb, static_lenb;
int max_blindex;
int eof = flush == Z_FINISH;
++s->blocks_in_packet;
if (s->data_type == 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;
#ifdef STORED_FILE_OK
# ifdef FORCE_STORED_FILE
if (eof && compressed_len == 0L)
# else
if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable())
# endif
{
if (buf == (charf*)0) error ("block vanished");
copy_block(buf, (unsigned)stored_len, 0);
s->compressed_len = stored_len << 3;
s->method = STORED;
} else
#endif
if (flush == Z_PACKET_FLUSH && s->blocks_in_packet == 1
&& opt_lenb > stored_len - s->minCompr) {
s->blocks_in_packet = 0;
} else
#ifdef FORCE_STORED
if (buf != (char*)0)
#else
if (stored_len+4 <= opt_lenb && buf != (char*)0)
#endif
{
ct_stored_block(s, buf, stored_len, eof);
} else
#ifdef FORCE_STATIC
if (static_lenb >= 0)
#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);
s->compressed_len += 3 + s->static_len;
} 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);
s->compressed_len += 3 + s->opt_len;
}
Assert (s->compressed_len == s->bits_sent, "bad compressed size");
init_block(s);
if (eof) {
bi_windup(s);
s->compressed_len += 7;
}
Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
s->compressed_len-7*eof));
return s->compressed_len >> 3;
}
local int ct_tally (s, dist, lc)
deflate_state *s;
int dist;
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, "ct_tally: bad match");
s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
s->dyn_dtree[d_code(dist)].Freq++;
}
if (s->level > 2 && (s->last_lit & 0xfff) == 0) {
ulg out_length = (ulg)s->last_lit*8L;
ulg in_length = (ulg)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;
}
return (s->last_lit == s->lit_bufsize-1);
}
local void compress_block(s, ltree, dtree)
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;
}
local void set_data_type(s)
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) ? BINARY : ASCII);
}
local unsigned bi_reverse(code, len)
unsigned code;
int len;
{
register unsigned res = 0;
do {
res |= code & 1;
code >>= 1, res <<= 1;
} while (--len > 0);
return res >> 1;
}
local void bi_flush(s)
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;
}
}
local void bi_windup(s)
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
}
local void copy_block(s, buf, len, header)
deflate_state *s;
charf *buf;
unsigned 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;
local inflate_blocks_statef * inflate_blocks_new OF((
z_stream *z,
check_func c,
uInt w));
local int inflate_blocks OF((
inflate_blocks_statef *,
z_stream *,
int));
local void inflate_blocks_reset OF((
inflate_blocks_statef *,
z_stream *,
uLongf *));
local int inflate_blocks_free OF((
inflate_blocks_statef *,
z_stream *,
uLongf *));
local int inflate_addhistory OF((
inflate_blocks_statef *,
z_stream *));
local int inflate_packet_flush OF((
inflate_blocks_statef *));
typedef struct inflate_huft_s FAR inflate_huft;
struct inflate_huft_s {
union {
struct {
Byte Exop;
Byte Bits;
} what;
uInt Nalloc;
Bytef *pad;
} word;
union {
uInt Base;
inflate_huft *Next;
} more;
};
#ifdef DEBUG_ZLIB
local uInt inflate_hufts;
#endif
local int inflate_trees_bits OF((
uIntf *,
uIntf *,
inflate_huft * FAR *,
z_stream *));
local int inflate_trees_dynamic OF((
uInt,
uInt,
uIntf *,
uIntf *,
uIntf *,
inflate_huft * FAR *,
inflate_huft * FAR *,
z_stream *));
local int inflate_trees_fixed OF((
uIntf *,
uIntf *,
inflate_huft * FAR *,
inflate_huft * FAR *));
local int inflate_trees_free OF((
inflate_huft *,
z_stream *));
struct inflate_codes_state;
typedef struct inflate_codes_state FAR inflate_codes_statef;
local inflate_codes_statef *inflate_codes_new OF((
uInt, uInt,
inflate_huft *, inflate_huft *,
z_stream *));
local int inflate_codes OF((
inflate_blocks_statef *,
z_stream *,
int));
local void inflate_codes_free OF((
inflate_codes_statef *,
z_stream *));
struct internal_state {
enum {
METHOD,
FLAG,
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;
};
int inflateReset(z)
z_stream *z;
{
uLong c;
if (z == Z_NULL || z->state == Z_NULL)
return Z_STREAM_ERROR;
z->total_in = z->total_out = 0;
z->msg = Z_NULL;
z->state->mode = z->state->nowrap ? BLOCKS : METHOD;
inflate_blocks_reset(z->state->blocks, z, &c);
Trace((stderr, "inflate: reset\n"));
return Z_OK;
}
int inflateEnd(z)
z_stream *z;
{
uLong c;
if (z == Z_NULL || z->state == Z_NULL || z->zfree == Z_NULL)
return Z_STREAM_ERROR;
if (z->state->blocks != Z_NULL)
inflate_blocks_free(z->state->blocks, z, &c);
ZFREE(z, z->state, sizeof(struct internal_state));
z->state = Z_NULL;
Trace((stderr, "inflate: end\n"));
return Z_OK;
}
int inflateInit2(z, w)
z_stream *z;
int w;
{
if (z == Z_NULL)
return Z_STREAM_ERROR;
if ((z->state = (struct internal_state FAR *)
ZALLOC(z,1,sizeof(struct internal_state))) == Z_NULL)
return Z_MEM_ERROR;
z->state->blocks = Z_NULL;
z->state->nowrap = 0;
if (w < 0)
{
w = - w;
z->state->nowrap = 1;
}
if (w < 8 || w > 15)
{
inflateEnd(z);
return Z_STREAM_ERROR;
}
z->state->wbits = (uInt)w;
if ((z->state->blocks =
inflate_blocks_new(z, z->state->nowrap ? Z_NULL : adler32, 1 << w))
== Z_NULL)
{
inflateEnd(z);
return Z_MEM_ERROR;
}
Trace((stderr, "inflate: allocated\n"));
inflateReset(z);
return Z_OK;
}
int inflateInit(z)
z_stream *z;
{
return inflateInit2(z, DEF_WBITS);
}
#define NEEDBYTE {if(z->avail_in==0)goto empty;r=Z_OK;}
#define NEXTBYTE (z->avail_in--,z->total_in++,*z->next_in++)
int inflate(z, f)
z_stream *z;
int f;
{
int r;
uInt b;
if (z == Z_NULL || z->next_in == Z_NULL)
return Z_STREAM_ERROR;
r = Z_BUF_ERROR;
while (1) switch (z->state->mode)
{
case METHOD:
NEEDBYTE
if (((z->state->sub.method = NEXTBYTE) & 0xf) != DEFLATED)
{
z->state->mode = BAD;
z->msg = "unknown compression method";
z->state->sub.marker = 5;
break;
}
if ((z->state->sub.method >> 4) + 8 > z->state->wbits)
{
z->state->mode = BAD;
z->msg = "invalid window size";
z->state->sub.marker = 5;
break;
}
z->state->mode = FLAG;
case FLAG:
NEEDBYTE
if ((b = NEXTBYTE) & 0x20)
{
z->state->mode = BAD;
z->msg = "invalid reserved bit";
z->state->sub.marker = 5;
break;
}
if (((z->state->sub.method << 8) + b) % 31)
{
z->state->mode = BAD;
z->msg = "incorrect header check";
z->state->sub.marker = 5;
break;
}
Trace((stderr, "inflate: zlib header ok\n"));
z->state->mode = BLOCKS;
case BLOCKS:
r = inflate_blocks(z->state->blocks, z, r);
if (f == Z_PACKET_FLUSH && z->avail_in == 0 && z->avail_out != 0)
r = inflate_packet_flush(z->state->blocks);
if (r == Z_DATA_ERROR)
{
z->state->mode = BAD;
z->state->sub.marker = 0;
break;
}
if (r != Z_STREAM_END)
return r;
r = Z_OK;
inflate_blocks_reset(z->state->blocks, z, &z->state->sub.check.was);
if (z->state->nowrap)
{
z->state->mode = DONE;
break;
}
z->state->mode = CHECK4;
case CHECK4:
NEEDBYTE
z->state->sub.check.need = (uLong)NEXTBYTE << 24;
z->state->mode = CHECK3;
case CHECK3:
NEEDBYTE
z->state->sub.check.need += (uLong)NEXTBYTE << 16;
z->state->mode = CHECK2;
case CHECK2:
NEEDBYTE
z->state->sub.check.need += (uLong)NEXTBYTE << 8;
z->state->mode = CHECK1;
case CHECK1:
NEEDBYTE
z->state->sub.check.need += (uLong)NEXTBYTE;
if (z->state->sub.check.was != z->state->sub.check.need)
{
z->state->mode = BAD;
z->msg = "incorrect data check";
z->state->sub.marker = 5;
break;
}
Trace((stderr, "inflate: zlib check ok\n"));
z->state->mode = DONE;
case DONE:
return Z_STREAM_END;
case BAD:
return Z_DATA_ERROR;
default:
return Z_STREAM_ERROR;
}
empty:
if (f != Z_PACKET_FLUSH)
return r;
z->state->mode = BAD;
z->state->sub.marker = 0;
return Z_DATA_ERROR;
}
int inflateIncomp(z)
z_stream *z;
{
if (z->state->mode != BLOCKS)
return Z_DATA_ERROR;
return inflate_addhistory(z->state->blocks, z);
}
int inflateSync(z)
z_stream *z;
{
uInt n;
Bytef *p;
uInt m;
uLong r, w;
if (z == Z_NULL || z->state == Z_NULL)
return Z_STREAM_ERROR;
if (z->state->mode != BAD)
{
z->state->mode = BAD;
z->state->sub.marker = 0;
}
if ((n = z->avail_in) == 0)
return Z_BUF_ERROR;
p = z->next_in;
m = z->state->sub.marker;
while (n && m < 4)
{
if (*p == (Byte)(m < 2 ? 0 : 0xff))
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;
z->state->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;
z->state->mode = BLOCKS;
return Z_OK;
}
#undef NEEDBYTE
#undef NEXTBYTE
struct inflate_blocks_state {
enum {
TYPE,
LENS,
STORED,
TABLE,
BTREE,
DTREE,
CODES,
DRY,
DONEB,
BADB}
mode;
union {
uInt left;
struct {
uInt table;
uInt index;
uIntf *blens;
uInt bb;
inflate_huft *tb;
int nblens;
} trees;
struct {
inflate_huft *tl, *td;
inflate_codes_statef
*codes;
} decode;
} sub;
uInt last;
uInt bitk;
uLong bitb;
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 (q<s->read?s->read-q-1:s->end-q)
#define LOADOUT {q=s->write;m=WAVAIL;}
#define WRAP {if(q==s->end&&s->read!=s->window){q=s->window;m=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}
local uInt inflate_mask[] = {
0x0000,
0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
};
local int inflate_flush OF((
inflate_blocks_statef *,
z_stream *,
int));
local int inflate_fast OF((
uInt,
uInt,
inflate_huft *,
inflate_huft *,
inflate_blocks_statef *,
z_stream *));
local uInt border[] = {
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
local void inflate_blocks_reset(s, z, c)
inflate_blocks_statef *s;
z_stream *z;
uLongf *c;
{
if (s->checkfn != Z_NULL)
*c = s->check;
if (s->mode == BTREE || s->mode == DTREE)
ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
if (s->mode == CODES)
{
inflate_codes_free(s->sub.decode.codes, z);
inflate_trees_free(s->sub.decode.td, z);
inflate_trees_free(s->sub.decode.tl, z);
}
s->mode = TYPE;
s->bitk = 0;
s->bitb = 0;
s->read = s->write = s->window;
if (s->checkfn != Z_NULL)
s->check = (*s->checkfn)(0L, Z_NULL, 0);
Trace((stderr, "inflate: blocks reset\n"));
}
local inflate_blocks_statef *inflate_blocks_new(z, c, w)
z_stream *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->window = (Bytef *)ZALLOC(z, 1, w)) == Z_NULL)
{
ZFREE(z, s, sizeof(struct inflate_blocks_state));
return Z_NULL;
}
s->end = s->window + w;
s->checkfn = c;
s->mode = TYPE;
Trace((stderr, "inflate: blocks allocated\n"));
inflate_blocks_reset(s, z, &s->check);
return s;
}
local int inflate_blocks(s, z, r)
inflate_blocks_statef *s;
z_stream *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:
Trace((stderr, "inflate: stored block%s\n",
s->last ? " (last)" : ""));
DUMPBITS(3)
t = k & 7;
DUMPBITS(t)
s->mode = LENS;
break;
case 1:
Trace((stderr, "inflate: fixed codes block%s\n",
s->last ? " (last)" : ""));
{
uInt bl, bd;
inflate_huft *tl, *td;
inflate_trees_fixed(&bl, &bd, &tl, &td);
s->sub.decode.codes = inflate_codes_new(bl, bd, tl, td, z);
if (s->sub.decode.codes == Z_NULL)
{
r = Z_MEM_ERROR;
LEAVE
}
s->sub.decode.tl = Z_NULL;
s->sub.decode.td = Z_NULL;
}
DUMPBITS(3)
s->mode = CODES;
break;
case 2:
Trace((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 = "invalid block type";
r = Z_DATA_ERROR;
LEAVE
}
break;
case LENS:
NEEDBITS(32)
if (((~b) >> 16) != (b & 0xffff))
{
s->mode = BADB;
z->msg = "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 : 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 = "too many length or distance symbols";
r = Z_DATA_ERROR;
LEAVE
}
#endif
t = 258 + (t & 0x1f) + ((t >> 5) & 0x1f);
if (t < 19)
t = 19;
if ((s->sub.trees.blens = (uIntf*)ZALLOC(z, t, sizeof(uInt))) == Z_NULL)
{
r = Z_MEM_ERROR;
LEAVE
}
s->sub.trees.nblens = t;
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, z);
if (t != Z_OK)
{
r = t;
if (r == Z_DATA_ERROR)
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->word.what.Bits;
c = h->more.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))
{
s->mode = BADB;
z->msg = "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;
}
}
inflate_trees_free(s->sub.trees.tb, z);
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, z);
if (t != Z_OK)
{
if (t == (uInt)Z_DATA_ERROR)
s->mode = BADB;
r = t;
LEAVE
}
Tracev((stderr, "inflate: trees ok\n"));
if ((c = inflate_codes_new(bl, bd, tl, td, z)) == Z_NULL)
{
inflate_trees_free(td, z);
inflate_trees_free(tl, z);
r = Z_MEM_ERROR;
LEAVE
}
ZFREE(z, s->sub.trees.blens, s->sub.trees.nblens * sizeof(uInt));
s->sub.decode.codes = c;
s->sub.decode.tl = tl;
s->sub.decode.td = td;
}
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);
inflate_trees_free(s->sub.decode.td, z);
inflate_trees_free(s->sub.decode.tl, 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;
}
if (k > 7)
{
Assert(k < 16, "inflate_codes grabbed too many bytes")
k -= 8;
n++;
p--;
}
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
}
}
local int inflate_blocks_free(s, z, c)
inflate_blocks_statef *s;
z_stream *z;
uLongf *c;
{
inflate_blocks_reset(s, z, c);
ZFREE(z, s->window, s->end - s->window);
ZFREE(z, s, sizeof(struct inflate_blocks_state));
Trace((stderr, "inflate: blocks freed\n"));
return Z_OK;
}
local int inflate_addhistory(s, z)
inflate_blocks_statef *s;
z_stream *z;
{
uLong b;
uInt k;
uInt t;
Bytef *p;
uInt n;
Bytef *q;
uInt m;
if (s->read != s->write)
return Z_STREAM_ERROR;
if (s->mode != TYPE)
return Z_DATA_ERROR;
LOAD
while (n) {
t = n;
if (t > m) t = m;
if (s->checkfn != Z_NULL)
s->check = (*s->checkfn)(s->check, q, t);
zmemcpy(q, p, t);
q += t;
p += t;
n -= t;
z->total_out += t;
s->read = q;
if (q == s->end) {
s->read = q = s->window;
m = WAVAIL;
}
}
UPDATE
return Z_OK;
}
local int inflate_packet_flush(s)
inflate_blocks_statef *s;
{
if (s->mode != LENS)
return Z_DATA_ERROR;
s->mode = TYPE;
return Z_OK;
}
#define base more.Base
#define next more.Next
#define exop word.what.Exop
#define bits word.what.Bits
local int huft_build OF((
uIntf *,
uInt,
uInt,
uIntf *,
uIntf *,
inflate_huft * FAR*,
uIntf *,
z_stream *));
local voidpf falloc OF((
voidpf,
uInt,
uInt));
local void ffree OF((
voidpf q,
voidpf p,
uInt n));
local uInt cplens[] = {
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};
local uInt cplext[] = {
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, 192, 192};
local uInt cpdist[] = {
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};
local uInt cpdext[] = {
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
#define N_MAX 288
#ifdef DEBUG_ZLIB
uInt inflate_hufts;
#endif
local int huft_build(b, n, s, d, e, t, m, zs)
uIntf *b;
uInt n;
uInt s;
uIntf *d;
uIntf *e;
inflate_huft * FAR *t;
uIntf *m;
z_stream *zs;
{
uInt a;
uInt c[BMAX+1];
uInt f;
int g;
int h;
register uInt i;
register uInt j;
register int k;
int l;
register uIntf *p;
inflate_huft *q;
struct inflate_huft_s r;
inflate_huft *u[BMAX];
uInt v[N_MAX];
register 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);
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 = (z = g - w) > (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 ((q = (inflate_huft *)ZALLOC
(zs,z + 1,sizeof(inflate_huft))) == Z_NULL)
{
if (h)
inflate_trees_free(u[0], zs);
return Z_MEM_ERROR;
}
q->word.Nalloc = z + 1;
#ifdef DEBUG_ZLIB
inflate_hufts += z + 1;
#endif
*t = q + 1;
*(t = &(q->next)) = Z_NULL;
u[h] = ++q;
if (h)
{
x[h] = i;
r.bits = (Byte)l;
r.exop = (Byte)j;
r.next = q;
j = i >> (w - l);
u[h-1][j] = r;
}
}
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;
while ((i & ((1 << w) - 1)) != x[h])
{
h--;
w -= l;
}
}
}
return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
}
local int inflate_trees_bits(c, bb, tb, z)
uIntf *c;
uIntf *bb;
inflate_huft * FAR *tb;
z_stream *z;
{
int r;
r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL, tb, bb, z);
if (r == Z_DATA_ERROR)
z->msg = "oversubscribed dynamic bit lengths tree";
else if (r == Z_BUF_ERROR)
{
inflate_trees_free(*tb, z);
z->msg = "incomplete dynamic bit lengths tree";
r = Z_DATA_ERROR;
}
return r;
}
local int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, z)
uInt nl;
uInt nd;
uIntf *c;
uIntf *bl;
uIntf *bd;
inflate_huft * FAR *tl;
inflate_huft * FAR *td;
z_stream *z;
{
int r;
if ((r = huft_build(c, nl, 257, cplens, cplext, tl, bl, z)) != Z_OK)
{
if (r == Z_DATA_ERROR)
z->msg = "oversubscribed literal/length tree";
else if (r == Z_BUF_ERROR)
{
inflate_trees_free(*tl, z);
z->msg = "incomplete literal/length tree";
r = Z_DATA_ERROR;
}
return r;
}
if ((r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, z)) != Z_OK)
{
if (r == Z_DATA_ERROR)
z->msg = "oversubscribed literal/length tree";
else if (r == Z_BUF_ERROR) {
#ifdef PKZIP_BUG_WORKAROUND
r = Z_OK;
}
#else
inflate_trees_free(*td, z);
z->msg = "incomplete literal/length tree";
r = Z_DATA_ERROR;
}
inflate_trees_free(*tl, z);
return r;
#endif
}
return Z_OK;
}
local int fixed_lock = 0;
local int fixed_built = 0;
#define FIXEDH 530
local uInt fixed_left = FIXEDH;
local inflate_huft fixed_mem[FIXEDH];
local uInt fixed_bl;
local uInt fixed_bd;
local inflate_huft *fixed_tl;
local inflate_huft *fixed_td;
local voidpf falloc(q, n, s)
voidpf q;
uInt n;
uInt s;
{
Assert(s == sizeof(inflate_huft) && n <= fixed_left,
"inflate_trees falloc overflow");
if (q) s++;
fixed_left -= n;
return (voidpf)(fixed_mem + fixed_left);
}
local void ffree(q, p, n)
voidpf q;
voidpf p;
uInt n;
{
Assert(0, "inflate_trees ffree called!");
if (q) q = p;
}
local int inflate_trees_fixed(bl, bd, tl, td)
uIntf *bl;
uIntf *bd;
inflate_huft * FAR *tl;
inflate_huft * FAR *td;
{
while (++fixed_lock > 1)
fixed_lock--;
if (!fixed_built)
{
int k;
unsigned c[288];
z_stream z;
z.zalloc = falloc;
z.zfree = ffree;
z.opaque = Z_NULL;
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 = 7;
huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl, &z);
for (k = 0; k < 30; k++)
c[k] = 5;
fixed_bd = 5;
huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd, &z);
fixed_built = 1;
}
fixed_lock--;
*bl = fixed_bl;
*bd = fixed_bd;
*tl = fixed_tl;
*td = fixed_td;
return Z_OK;
}
local int inflate_trees_free(t, z)
inflate_huft *t;
z_stream *z;
{
register inflate_huft *p, *q;
p = t;
while (p != Z_NULL)
{
q = (--p)->next;
ZFREE(z, p, p->word.Nalloc * sizeof(inflate_huft));
p = q;
}
return Z_OK;
}
#define base more.Base
#define next more.Next
#define exop word.what.Exop
#define bits word.what.Bits
struct inflate_codes_state {
enum {
START,
LEN,
LENEXT,
DIST,
DISTEXT,
COPY,
LIT,
WASH,
END,
BADCODE}
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;
};
local inflate_codes_statef *inflate_codes_new(bl, bd, tl, td, z)
uInt bl, bd;
inflate_huft *tl, *td;
z_stream *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;
}
local int inflate_codes(s, z, r)
inflate_blocks_statef *s;
z_stream *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->next;
break;
}
if (e & 32)
{
Tracevv((stderr, "inflate: end of block\n"));
c->mode = WASH;
break;
}
c->mode = BADCODE;
z->msg = "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->next;
break;
}
c->mode = BADCODE;
z->msg = "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:
#ifndef __TURBOC__
f = (uInt)(q - s->window) < c->sub.copy.dist ?
s->end - (c->sub.copy.dist - (q - s->window)) :
q - c->sub.copy.dist;
#else
f = q - c->sub.copy.dist;
if ((uInt)(q - s->window) < c->sub.copy.dist)
f = s->end - (c->sub.copy.dist - (q - s->window));
#endif
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:
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
}
}
local void inflate_codes_free(c, z)
inflate_codes_statef *c;
z_stream *z;
{
ZFREE(z, c, sizeof(struct inflate_codes_state));
Tracev((stderr, "inflate: codes free\n"));
}
local int inflate_flush(s, z, r)
inflate_blocks_statef *s;
z_stream *z;
int r;
{
uInt n;
Bytef *p, *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)
s->check = (*s->checkfn)(s->check, q, n);
if (p != NULL) {
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)
s->check = (*s->checkfn)(s->check, q, n);
if (p != NULL) {
zmemcpy(p, q, n);
p += n;
}
q += n;
}
z->next_out = p;
s->read = q;
return r;
}
#define base more.Base
#define next more.Next
#define exop word.what.Exop
#define bits word.what.Bits
#define GRABBITS(j) {while(k<(j)){b|=((uLong)NEXTBYTE)<<k;k+=8;}}
#define UNGRAB {n+=(c=k>>3);p-=c;k&=7;}
local int inflate_fast(bl, bd, tl, td, s, z)
uInt bl, bd;
inflate_huft *tl, *td;
inflate_blocks_statef *s;
z_stream *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;
if ((uInt)(q - s->window) >= d)
{
r = q - d;
*q++ = *r++; c--;
*q++ = *r++; c--;
}
else
{
e = d - (q - s->window);
r = s->end - e;
if (c > e)
{
c -= e;
do {
*q++ = *r++;
} while (--e);
r = s->window;
}
}
do {
*q++ = *r++;
} while (--c);
break;
}
else if ((e & 64) == 0)
e = (t = t->next + ((uInt)b & inflate_mask[e]))->exop;
else
{
z->msg = "invalid distance code";
UNGRAB
UPDATE
return Z_DATA_ERROR;
}
} while (1);
break;
}
if ((e & 64) == 0)
{
if ((e = (t = t->next + ((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 = "invalid literal/length code";
UNGRAB
UPDATE
return Z_DATA_ERROR;
}
} while (1);
} while (m >= 258 && n >= 10);
UNGRAB
UPDATE
return Z_OK;
}
char *zlib_version = ZLIB_VERSION;
char *z_errmsg[] = {
"stream end",
"",
"file error",
"stream error",
"data error",
"insufficient memory",
"buffer error",
""};
#define BASE 65521L
#define NMAX 5552
#define DO1(buf) {s1 += *buf++; s2 += s1;}
#define DO2(buf) DO1(buf); DO1(buf);
#define DO4(buf) DO2(buf); DO2(buf);
#define DO8(buf) DO4(buf); DO4(buf);
#define DO16(buf) DO8(buf); DO8(buf);
uLong adler32(adler, buf, len)
uLong adler;
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);
k -= 16;
}
if (k != 0) do {
DO1(buf);
} while (--k);
s1 %= BASE;
s2 %= BASE;
}
return (s2 << 16) | s1;
}
