deflate.h

Go to the documentation of this file.

 
/* @(#) $Id$ */
 
#ifndef DEFLATE_H
#define DEFLATE_H
 
#include "zutil.h"
 
/* define NO_GZIP when compiling if you want to disable gzip header and
   trailer creation by deflate().  NO_GZIP would be used to avoid linking in
   the crc code when it is not needed.  For shared libraries, gzip encoding
   should be left enabled. */
#ifndef NO_GZIP
#  define GZIP
#endif
 
/* define LIT_MEM to slightly increase the speed of deflate (order 1% to 2%) at
   the cost of a larger memory footprint */
/* #define LIT_MEM */
 
/* ===========================================================================
 * Internal compression state.
 */
 
#define LENGTH_CODES 29
/* number of length codes, not counting the special END_BLOCK code */
 
#define LITERALS  256
/* number of literal bytes 0..255 */
 
#define L_CODES (LITERALS+1+LENGTH_CODES)
/* number of Literal or Length codes, including the END_BLOCK code */
 
#define D_CODES   30
/* number of distance codes */
 
#define BL_CODES  19
/* number of codes used to transfer the bit lengths */
 
#define HEAP_SIZE (2*L_CODES+1)
/* maximum heap size */
 
#define MAX_BITS 15
/* All codes must not exceed MAX_BITS bits */
 
#define Buf_size 16
/* size of bit buffer in bi_buf */
 
#define INIT_STATE    42    /* zlib header -> BUSY_STATE */
#ifdef GZIP
#  define GZIP_STATE  57    /* gzip header -> BUSY_STATE | EXTRA_STATE */
#endif
#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 */
/* Stream status */
 
 
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;           /* the dynamic tree */
    int     max_code;            /* largest code with non zero frequency */
    const static_tree_desc *stat_desc;  /* the corresponding static tree */
} FAR tree_desc;
 
typedef ush Pos;
typedef Pos FAR Posf;
typedef unsigned IPos;
 
/* A Pos is an index in the character window. We use short instead of int to
 * save space in the various tables. IPos is used only for parameter passing.
 */
 
typedef struct internal_state {
    z_streamp strm;      
    int   status;        
    Bytef *pending_buf;  
    ulg   pending_buf_size; 
    Bytef *pending_out;  
    ulg   pending;       
    int   wrap;          
    gz_headerp  gzhead;  
    ulg   gzindex;       
    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; 
 
    /* Didn't use ct_data typedef below to suppress compiler warning */
    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;               
    /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
     * The same heap array is used to build all trees.
     */
 
    uch depth[2*L_CODES+1];
#ifdef LIT_MEM
    ushf *d_buf;          
    uchf *l_buf;          
#else
    uchf *sym_buf;        
#endif
 
    uInt  lit_bufsize;
    uInt sym_next;      
    uInt sym_end;       
    ulg opt_len;        
    ulg static_len;     
    uInt matches;       
    uInt insert;        
#ifdef ZLIB_DEBUG
    ulg compressed_len; 
    ulg bits_sent;      
#endif
 
    ush bi_buf;
    int bi_valid;
    ulg high_water;
} FAR deflate_state;
 
/* Output a byte on the stream.
 * IN assertion: there is enough room in pending_buf.
 */
#define put_byte(s, c) {s->pending_buf[s->pending++] = (Bytef)(c);}
 
 
#define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
/* Minimum amount of lookahead, except at the end of the input file.
 * See deflate.c for comments about the MIN_MATCH+1.
 */
 
#define MAX_DIST(s)  ((s)->w_size-MIN_LOOKAHEAD)
/* In order to simplify the code, particularly on 16 bit machines, match
 * distances are limited to MAX_DIST instead of WSIZE.
 */
 
#define WIN_INIT MAX_MATCH
/* Number of bytes after end of data in window to initialize in order to avoid
   memory checker errors from longest match routines */
 
        /* in trees.c */
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);
 
#define d_code(dist) \
   ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])
/* Mapping from a distance to a distance code. dist is the distance - 1 and
 * must not have side effects. _dist_code[256] and _dist_code[257] are never
 * used.
 */
 
#ifndef ZLIB_DEBUG
/* Inline versions of _tr_tally for speed: */
 
#if defined(GEN_TREES_H) || !defined(STDC)
  extern uch ZLIB_INTERNAL _length_code[];
  extern uch ZLIB_INTERNAL _dist_code[];
#else
  extern const uch ZLIB_INTERNAL _length_code[];
  extern const uch ZLIB_INTERNAL _dist_code[];
#endif
 
#ifdef LIT_MEM
# define _tr_tally_lit(s, c, flush) \
  { uch cc = (c); \
    s->d_buf[s->sym_next] = 0; \
    s->l_buf[s->sym_next++] = cc; \
    s->dyn_ltree[cc].Freq++; \
    flush = (s->sym_next == s->sym_end); \
   }
# define _tr_tally_dist(s, distance, length, flush) \
  { uch len = (uch)(length); \
    ush dist = (ush)(distance); \
    s->d_buf[s->sym_next] = dist; \
    s->l_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); \
  }
#else
# 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); \
   }
# 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); \
  }
#endif
#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 /* DEFLATE_H */