deflate.h File Reference

#include "zutil.h"

Go to the source code of this file.

Classes
struct	ct_data_s
struct	tree_desc_s
struct	internal_state

Macros
#define	GZIP
#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	Buf_size   16
#define	INIT_STATE   42 /* zlib header -> BUSY_STATE */
#define	GZIP_STATE   57 /* gzip header -> BUSY_STATE | EXTRA_STATE */
#define	EXTRA_STATE   69 /* gzip extra block -> NAME_STATE */
#define	NAME_STATE   73 /* gzip file name -> COMMENT_STATE */
#define	COMMENT_STATE   91 /* gzip comment -> HCRC_STATE */
#define	HCRC_STATE   103 /* gzip header CRC -> BUSY_STATE */
#define	BUSY_STATE   113 /* deflate -> FINISH_STATE */
#define	FINISH_STATE   666 /* stream complete */
#define	Freq   fc.freq
#define	Code   fc.code
#define	Dad   dl.dad
#define	Len   dl.len
#define	max_insert_length   max_lazy_match
#define	LIT_BUFS   4
#define	put_byte(s, c)
#define	MIN_LOOKAHEAD   (MAX_MATCH+MIN_MATCH+1)
#define	MAX_DIST(s)
#define	WIN_INIT   MAX_MATCH
#define	d_code(dist)
#define	_tr_tally_lit(s, c, flush)
#define	_tr_tally_dist(s, distance, length, flush)

Typedefs
typedef struct ct_data_s	ct_data
typedef struct static_tree_desc_s	static_tree_desc
typedef struct tree_desc_s	tree_desc
typedef ush	Pos
typedef Pos FAR	Posf
typedef unsigned	IPos
typedef struct internal_state	deflate_state

Functions
void ZLIB_INTERNAL	_tr_init (deflate_state *s)
int ZLIB_INTERNAL	_tr_tally (deflate_state *s, unsigned dist, unsigned lc)
void ZLIB_INTERNAL	_tr_flush_block (deflate_state *s, charf *buf, ulg stored_len, int last)
void ZLIB_INTERNAL	_tr_flush_bits (deflate_state *s)
void ZLIB_INTERNAL	_tr_align (deflate_state *s)
void ZLIB_INTERNAL	_tr_stored_block (deflate_state *s, charf *buf, ulg stored_len, int last)

Variables
uch ZLIB_INTERNAL	_length_code []
uch ZLIB_INTERNAL	_dist_code []

Macro Definition Documentation

_tr_tally_dist

#define _tr_tally_dist	(		s,
			distance,
			length,
			flush )

Value:

{ uch len = (uch)(length); \
  ush dist = (ush)(distance); \
  s->sym_buf[s->sym_next++] = (uch)dist; \
  s->sym_buf[s->sym_next++] = (uch)(dist >> 8); \
  s->sym_buf[s->sym_next++] = len; \
  dist--; \
  s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
  s->dyn_dtree[d_code(dist)].Freq++; \
  flush = (s->sym_next == s->sym_end); \
}

Definition at line 359 of file deflate.h.

# define _tr_tally_dist(s, distance, length, flush) \
  { uch len = (uch)(length); \
    ush dist = (ush)(distance); \
    s->sym_buf[s->sym_next++] = (uch)dist; \
    s->sym_buf[s->sym_next++] = (uch)(dist >> 8); \
    s->sym_buf[s->sym_next++] = len; \
    dist--; \
    s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
    s->dyn_dtree[d_code(dist)].Freq++; \
    flush = (s->sym_next == s->sym_end); \
  }

Referenced by deflate_fast(), deflate_rle(), and deflate_slow().

_tr_tally_lit

#define _tr_tally_lit	(		s,
			c,
			flush )

Value:

{ uch cc = (c); \
  s->sym_buf[s->sym_next++] = 0; \
  s->sym_buf[s->sym_next++] = 0; \
  s->sym_buf[s->sym_next++] = cc; \
  s->dyn_ltree[cc].Freq++; \
  flush = (s->sym_next == s->sym_end); \
 }

Definition at line 351 of file deflate.h.

# define _tr_tally_lit(s, c, flush) \
  { uch cc = (c); \
    s->sym_buf[s->sym_next++] = 0; \
    s->sym_buf[s->sym_next++] = 0; \
    s->sym_buf[s->sym_next++] = cc; \
    s->dyn_ltree[cc].Freq++; \
    flush = (s->sym_next == s->sym_end); \
   }

Referenced by deflate_fast(), deflate_huff(), deflate_rle(), and deflate_slow().

BL_CODES

#define BL_CODES   19

Definition at line 46 of file deflate.h.

Referenced by build_bl_tree(), init_block(), and send_all_trees().

Buf_size

#define Buf_size   16

Definition at line 55 of file deflate.h.

Referenced by deflatePrime().

BUSY_STATE

#define BUSY_STATE   113 /* deflate -> FINISH_STATE */

Definition at line 66 of file deflate.h.

Referenced by deflate(), deflateEnd(), and deflateStateCheck().

Code

#define Code   fc.code

Definition at line 84 of file deflate.h.

Referenced by gen_codes().

COMMENT_STATE

#define COMMENT_STATE   91 /* gzip comment -> HCRC_STATE */

Definition at line 64 of file deflate.h.

Referenced by deflate(), and deflateStateCheck().

d_code

#define d_code

(

dist

)

Value:

((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])

Definition at line 314 of file deflate.h.

#define d_code(dist) \
   ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])

Referenced by _tr_tally(), and compress_block().

D_CODES

#define D_CODES   30

Definition at line 43 of file deflate.h.

Referenced by _tr_tally(), compress_block(), init_block(), send_all_trees(), and tr_static_init().

Dad

#define Dad   dl.dad

Definition at line 85 of file deflate.h.

EXTRA_STATE

#define EXTRA_STATE   69 /* gzip extra block -> NAME_STATE */

Definition at line 62 of file deflate.h.

Referenced by deflate(), and deflateStateCheck().

FINISH_STATE

#define FINISH_STATE   666 /* stream complete */

Definition at line 67 of file deflate.h.

Referenced by deflate(), deflateInit2_(), and deflateStateCheck().

Freq

#define Freq   fc.freq

Definition at line 83 of file deflate.h.

Referenced by build_tree(), and gen_bitlen().

GZIP

#define GZIP

Definition at line 23 of file deflate.h.

Referenced by deflateStateCheck(), gz_fetch(), and gz_look().

GZIP_STATE

#define GZIP_STATE   57 /* gzip header -> BUSY_STATE | EXTRA_STATE */

Definition at line 60 of file deflate.h.

Referenced by deflate(), deflateResetKeep(), and deflateStateCheck().

HCRC_STATE

#define HCRC_STATE   103 /* gzip header CRC -> BUSY_STATE */

Definition at line 65 of file deflate.h.

Referenced by deflate(), and deflateStateCheck().

HEAP_SIZE

#define HEAP_SIZE   (2*L_CODES+1)

Definition at line 49 of file deflate.h.

Referenced by build_tree(), and gen_bitlen().

INIT_STATE

#define INIT_STATE   42 /* zlib header -> BUSY_STATE */

Definition at line 58 of file deflate.h.

Referenced by deflate(), deflateInit2_(), deflateResetKeep(), deflateSetDictionary(), and deflateStateCheck().

L_CODES

#define L_CODES   (LITERALS+1+LENGTH_CODES)

Definition at line 40 of file deflate.h.

Referenced by init_block(), send_all_trees(), and tr_static_init().

Len

#define Len   dl.len

Definition at line 86 of file deflate.h.

Referenced by gen_bitlen().

LENGTH_CODES

#define LENGTH_CODES   29

Definition at line 34 of file deflate.h.

Referenced by tr_static_init().

LIT_BUFS

#define LIT_BUFS   4

Definition at line 229 of file deflate.h.

Referenced by deflateCopy(), and deflateInit2_().

LITERALS

#define LITERALS   256

Definition at line 37 of file deflate.h.

Referenced by _tr_tally(), compress_block(), and detect_data_type().

MAX_BITS

#define MAX_BITS   15

Definition at line 52 of file deflate.h.

Referenced by gen_bitlen(), gen_codes(), and tr_static_init().

MAX_DIST

#define MAX_DIST

(

s

)

Value:

((s)->w_size-MIN_LOOKAHEAD)

Definition at line 295 of file deflate.h.

Referenced by _tr_tally(), deflate_fast(), deflate_slow(), fill_window(), and longest_match().

max_insert_length

#define max_insert_length   max_lazy_match

Definition at line 186 of file deflate.h.

MIN_LOOKAHEAD

#define MIN_LOOKAHEAD   (MAX_MATCH+MIN_MATCH+1)

Definition at line 290 of file deflate.h.

Referenced by deflate_fast(), deflate_slow(), fill_window(), and longest_match().

NAME_STATE

#define NAME_STATE   73 /* gzip file name -> COMMENT_STATE */

Definition at line 63 of file deflate.h.

Referenced by deflate(), and deflateStateCheck().

put_byte

#define put_byte	(		s,
			c )

Value:

{s->pending_buf[s->pending++] = (Bytef)(c);}

Definition at line 287 of file deflate.h.

Referenced by bi_flush(), bi_windup(), deflate(), and putShortMSB().

WIN_INIT

#define WIN_INIT   MAX_MATCH

Definition at line 300 of file deflate.h.

Referenced by fill_window().

Typedef Documentation

ct_data

typedef struct ct_data_s ct_data

deflate_state

typedef struct internal_state deflate_state

IPos

typedef unsigned IPos

Definition at line 98 of file deflate.h.

Pos

typedef ush Pos

Definition at line 96 of file deflate.h.

Posf

typedef Pos FAR Posf

Definition at line 97 of file deflate.h.

static_tree_desc

typedef struct static_tree_desc_s static_tree_desc

Definition at line 88 of file deflate.h.

tree_desc

typedef struct tree_desc_s tree_desc

Function Documentation

_tr_align()

void ZLIB_INTERNAL _tr_align

(

deflate_state *

s

)

Definition at line 886 of file trees.c.

                                               {
    send_bits(s, STATIC_TREES<<1, 3);
    send_code(s, END_BLOCK, static_ltree);
#ifdef ZLIB_DEBUG
    s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
#endif
    bi_flush(s);
}

Referenced by deflate().

_tr_flush_bits()

void ZLIB_INTERNAL _tr_flush_bits

(

deflate_state *

s

)

Definition at line 878 of file trees.c.

                                                    {
    bi_flush(s);
}

Referenced by deflatePrime(), and flush_pending().

_tr_flush_block()

void ZLIB_INTERNAL _tr_flush_block	(	deflate_state *	s,
		charf *	buf,
		ulg	stored_len,
		int	last )

Definition at line 995 of file trees.c.

                                                             {
    ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
    int max_blindex = 0;  /* index of last bit length code of non zero freq */
 
    /* Build the Huffman trees unless a stored block is forced */
    if (s->level > 0) {
 
        /* Check if the file is binary or text */
        if (s->strm->data_type == Z_UNKNOWN)
            s->strm->data_type = detect_data_type(s);
 
        /* Construct the literal and distance trees */
        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));
        /* At this point, opt_len and static_len are the total bit lengths of
         * the compressed block data, excluding the tree representations.
         */
 
        /* Build the bit length tree for the above two trees, and get the index
         * in bl_order of the last bit length code to send.
         */
        max_blindex = build_bl_tree(s);
 
        /* Determine the best encoding. Compute the block lengths in bytes. */
        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->sym_next / 3));
 
#ifndef FORCE_STATIC
        if (static_lenb <= opt_lenb || s->strategy == Z_FIXED)
#endif
            opt_lenb = static_lenb;
 
    } else {
        Assert(buf != (char*)0, "lost buf");
        opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
    }
 
#ifdef FORCE_STORED
    if (buf != (char*)0) { /* force stored block */
#else
    if (stored_len + 4 <= opt_lenb && buf != (char*)0) {
                       /* 4: two words for the lengths */
#endif
        /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
         * Otherwise we can't have processed more than WSIZE input bytes since
         * the last block flush, because compression would have been
         * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
         * transform a block into a stored block.
         */
        _tr_stored_block(s, buf, stored_len, last);
 
    } else if (static_lenb == opt_lenb) {
        send_bits(s, (STATIC_TREES<<1) + last, 3);
        compress_block(s, (const ct_data *)static_ltree,
                       (const ct_data *)static_dtree);
#ifdef ZLIB_DEBUG
        s->compressed_len += 3 + s->static_len;
#endif
    } else {
        send_bits(s, (DYN_TREES<<1) + last, 3);
        send_all_trees(s, s->l_desc.max_code + 1, s->d_desc.max_code + 1,
                       max_blindex + 1);
        compress_block(s, (const ct_data *)s->dyn_ltree,
                       (const ct_data *)s->dyn_dtree);
#ifdef ZLIB_DEBUG
        s->compressed_len += 3 + s->opt_len;
#endif
    }
    Assert (s->compressed_len == s->bits_sent, "bad compressed size");
    /* The above check is made mod 2^32, for files larger than 512 MB
     * and uLong implemented on 32 bits.
     */
    init_block(s);
 
    if (last) {
        bi_windup(s);
#ifdef ZLIB_DEBUG
        s->compressed_len += 7;  /* align on byte boundary */
#endif
    }
    Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len >> 3,
           s->compressed_len - 7*last));
}

_tr_init()

void ZLIB_INTERNAL _tr_init

(

deflate_state *

s

)

Definition at line 455 of file trees.c.

                                              {
    tr_static_init();
 
    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;
#ifdef ZLIB_DEBUG
    s->compressed_len = 0L;
    s->bits_sent = 0L;
#endif
 
    /* Initialize the first block of the first file: */
    init_block(s);
}

Referenced by deflateResetKeep().

_tr_stored_block()

void ZLIB_INTERNAL _tr_stored_block	(	deflate_state *	s,
		charf *	buf,
		ulg	stored_len,
		int	last )

Definition at line 858 of file trees.c.

                                                              {
    send_bits(s, (STORED_BLOCK<<1) + last, 3);  /* send block type */
    bi_windup(s);        /* align on byte boundary */
    put_short(s, (ush)stored_len);
    put_short(s, (ush)~stored_len);
    if (stored_len)
        zmemcpy(s->pending_buf + s->pending, (Bytef *)buf, stored_len);
    s->pending += stored_len;
#ifdef ZLIB_DEBUG
    s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
    s->compressed_len += (stored_len + 4) << 3;
    s->bits_sent += 2*16;
    s->bits_sent += stored_len << 3;
#endif
}

Referenced by _tr_flush_block(), deflate(), and deflate_stored().

_tr_tally()

int ZLIB_INTERNAL _tr_tally	(	deflate_state *	s,
		unsigned	dist,
		unsigned	lc )

Definition at line 1093 of file trees.c.

                                                                          {
#ifdef LIT_MEM
    s->d_buf[s->sym_next] = (ush)dist;
    s->l_buf[s->sym_next++] = (uch)lc;
#else
    s->sym_buf[s->sym_next++] = (uch)dist;
    s->sym_buf[s->sym_next++] = (uch)(dist >> 8);
    s->sym_buf[s->sym_next++] = (uch)lc;
#endif
    if (dist == 0) {
        /* lc is the unmatched char */
        s->dyn_ltree[lc].Freq++;
    } else {
        s->matches++;
        /* Here, lc is the match length - MIN_MATCH */
        dist--;             /* dist = match distance - 1 */
        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++;
    }
    return (s->sym_next == s->sym_end);
}

Variable Documentation

_dist_code

uch ZLIB_INTERNAL _dist_code[]

extern

Definition at line 73 of file trees.h.

                                                  {
 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
};

Referenced by tr_static_init().

_length_code

uch ZLIB_INTERNAL _length_code[]

extern

Definition at line 102 of file trees.h.

                                                           {
 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
};

Referenced by _tr_tally(), compress_block(), and tr_static_init().