home *** CD-ROM | disk | FTP | other *** search
/ Chip 2004 March / CMCD0304.ISO / Software / Freeware / Programare / nullsoft / nsis20.exe / Source / zlib / DEFLATE.H < prev    next >
C/C++ Source or Header  |  2003-07-12  |  8KB  |  239 lines
  1. /* deflate.h -- internal compression state
  2.  * Copyright (C) 1995-1998 Jean-loup Gailly
  3.  * For conditions of distribution and use, see copyright notice in zlib.h 
  4.  */
  5.  
  6.  
  7. #ifndef _DEFLATE_H
  8. #define _DEFLATE_H
  9.  
  10. #include "zutil.h"
  11.  
  12. /* ===========================================================================
  13.  * Internal compression state.
  14.  */
  15.  
  16. #define LENGTH_CODES 29
  17. /* number of length codes, not counting the special END_BLOCK code */
  18.  
  19. #define LITERALS  256
  20. /* number of literal bytes 0..255 */
  21.  
  22. #define L_CODES (LITERALS+1+LENGTH_CODES)
  23. /* number of Literal or Length codes, including the END_BLOCK code */
  24.  
  25. #define D_CODES   30
  26. /* number of distance codes */
  27.  
  28. #define BL_CODES  19
  29. /* number of codes used to transfer the bit lengths */
  30.  
  31. #define HEAP_SIZE (2*L_CODES+1)
  32. /* maximum heap size */
  33.  
  34. #define MAX_BITS 15
  35. /* All codes must not exceed MAX_BITS bits */
  36.  
  37. #define INIT_STATE    42
  38. #define BUSY_STATE   113
  39. #define FINISH_STATE 666
  40. /* Stream status */
  41.  
  42.  
  43. /* Data structure describing a single value and its code string. */
  44. typedef struct ct_data_s {
  45.     union {
  46.         ush  freq;       /* frequency count */
  47.         ush  code;       /* bit string */
  48.     } fc;
  49.     union {
  50.         ush  dad;        /* father node in Huffman tree */
  51.         ush  len;        /* length of bit string */
  52.     } dl;
  53. } FAR ct_data;
  54.  
  55. #define Freq fc.freq
  56. #define Code fc.code
  57. #define Dad  dl.dad
  58. #define Len  dl.len
  59.  
  60. typedef struct static_tree_desc_s  static_tree_desc;
  61.  
  62. typedef struct tree_desc_s {
  63.     ct_data *dyn_tree;           /* the dynamic tree */
  64.     int     max_code;            /* largest code with non zero frequency */
  65.     static_tree_desc *stat_desc; /* the corresponding static tree */
  66. } FAR tree_desc;
  67.  
  68. typedef ush Pos;
  69. typedef Pos FAR Posf;
  70. typedef unsigned IPos;
  71.  
  72. /* A Pos is an index in the character window. We use short instead of int to
  73.  * save space in the various tables. IPos is used only for parameter passing.
  74.  */
  75.  
  76. typedef struct internal_state {
  77.     z_streamp strm;      /* pointer back to this zlib stream */
  78.     int   status;        /* as the name implies */
  79.     Bytef *pending_buf;  /* output still pending */
  80.     ulg   pending_buf_size; /* size of pending_buf */
  81.     Bytef *pending_out;  /* next pending byte to output to the stream */
  82.     int   pending;       /* nb of bytes in the pending buffer */
  83.     int   noheader;      /* suppress zlib header and adler32 */
  84.     Byte  method;        /* STORED (for zip only) or DEFLATED */
  85.     int   last_flush;    /* value of flush param for previous deflate call */
  86.  
  87.                 /* used by deflate.c: */
  88.  
  89.     uInt  w_size;        /* LZ77 window size (32K by default) */
  90.     uInt  w_bits;        /* log2(w_size)  (8..16) */
  91.     uInt  w_mask;        /* w_size - 1 */
  92.  
  93.     Bytef *window;
  94.  
  95.     ulg window_size;
  96.  
  97.     Posf *prev;
  98.  
  99.     Posf *head; /* Heads of the hash chains or NIL. */
  100.  
  101.     uInt  ins_h;          /* hash index of string to be inserted */
  102.     uInt  hash_size;      /* number of elements in hash table */
  103.     uInt  hash_bits;      /* log2(hash_size) */
  104.     uInt  hash_mask;      /* hash_size-1 */
  105.  
  106.     uInt  hash_shift;
  107.     long block_start;
  108.  
  109.     uInt match_length;           /* length of best match */
  110.     IPos prev_match;             /* previous match */
  111.     int match_available;         /* set if previous match exists */
  112.     uInt strstart;               /* start of string to insert */
  113.     uInt match_start;            /* start of matching string */
  114.     uInt lookahead;              /* number of valid bytes ahead in window */
  115.  
  116.     uInt prev_length;
  117.  
  118.     uInt max_chain_length;
  119.  
  120.     uInt max_lazy_match;
  121. #   define max_insert_length  max_lazy_match
  122.  
  123.     int level;    /* compression level (1..9) */
  124.     int strategy; /* favor or force Huffman coding*/
  125.  
  126.     uInt good_match;
  127.  
  128.     int nice_match; /* Stop searching when current match exceeds this */
  129.  
  130.     struct ct_data_s dyn_ltree[HEAP_SIZE];   /* literal and length tree */
  131.     struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
  132.     struct ct_data_s bl_tree[2*BL_CODES+1];  /* Huffman tree for bit lengths */
  133.  
  134.     struct tree_desc_s l_desc;               /* desc. for literal tree */
  135.     struct tree_desc_s d_desc;               /* desc. for distance tree */
  136.     struct tree_desc_s bl_desc;              /* desc. for bit length tree */
  137.  
  138.     ush bl_count[MAX_BITS+1];
  139.     /* number of codes at each bit length for an optimal tree */
  140.  
  141.     int heap[2*L_CODES+1];      /* heap used to build the Huffman trees */
  142.     int heap_len;               /* number of elements in the heap */
  143.     int heap_max;               /* element of largest frequency */
  144.  
  145.     uch depth[2*L_CODES+1];
  146.     /* Depth of each subtree used as tie breaker for trees of equal frequency
  147.      */
  148.  
  149.     uchf *l_buf;          /* buffer for literals or lengths */
  150.  
  151.     uInt  lit_bufsize;
  152.  
  153.     uInt last_lit;      /* running index in l_buf */
  154.  
  155.     ushf *d_buf;
  156.  
  157.     ulg opt_len;        /* bit length of current block with optimal trees */
  158.     ulg static_len;     /* bit length of current block with static trees */
  159.     uInt matches;       /* number of string matches in current block */
  160.     int last_eob_len;   /* bit length of EOB code for last block */
  161.  
  162. #ifdef DEBUG
  163.     ulg compressed_len; /* total bit length of compressed file mod 2^32 */
  164.     ulg bits_sent;      /* bit length of compressed data sent mod 2^32 */
  165. #endif
  166.  
  167.     ush bi_buf;
  168.     int bi_valid;
  169.  
  170. } FAR deflate_state;
  171.  
  172. /* Output a byte on the stream.
  173.  * IN assertion: there is enough room in pending_buf.
  174.  */
  175. #define put_byte(s, c) {s->pending_buf[s->pending++] = (c);}
  176.  
  177.  
  178. #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
  179. /* Minimum amount of lookahead, except at the end of the input file.
  180.  * See deflate.c for comments about the MIN_MATCH+1.
  181.  */
  182.  
  183. #define MAX_DIST(s)  ((s)->w_size-MIN_LOOKAHEAD)
  184. /* In order to simplify the code, particularly on 16 bit machines, match
  185.  * distances are limited to MAX_DIST instead of WSIZE.
  186.  */
  187.  
  188.         /* in trees.c */
  189. void _tr_init         OF((deflate_state *s));
  190. int  _tr_tally        OF((deflate_state *s, unsigned dist, unsigned lc));
  191. void _tr_flush_block  OF((deflate_state *s, charf *buf, ulg stored_len,
  192.                           int eof));
  193. void _tr_align        OF((deflate_state *s));
  194. void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
  195.                           int eof));
  196.  
  197. #define d_code(dist) \
  198.    ((dist) < 256 ? _dist_code[dist] : _dist_code[256+((dist)>>7)])
  199. /* Mapping from a distance to a distance code. dist is the distance - 1 and
  200.  * must not have side effects. _dist_code[256] and _dist_code[257] are never
  201.  * used.
  202.  */
  203.  
  204. #ifndef DEBUG
  205. /* Inline versions of _tr_tally for speed: */
  206.  
  207. #if defined(GEN_TREES_H) || !defined(STDC)
  208.   extern uch _length_code[];
  209.   extern uch _dist_code[];
  210. #else
  211.   extern const uch _length_code[];
  212.   extern const uch _dist_code[];
  213. #endif
  214.  
  215. # define _tr_tally_lit(s, c, flush) \
  216.   { uch cc = (c); \
  217.     s->d_buf[s->last_lit] = 0; \
  218.     s->l_buf[s->last_lit++] = cc; \
  219.     s->dyn_ltree[cc].Freq++; \
  220.     flush = (s->last_lit == s->lit_bufsize-1); \
  221.    }
  222. # define _tr_tally_dist(s, distance, length, flush) \
  223.   { uch len = (length); \
  224.     ush dist = (distance); \
  225.     s->d_buf[s->last_lit] = dist; \
  226.     s->l_buf[s->last_lit++] = len; \
  227.     dist--; \
  228.     s->dyn_ltree[_length_code[len]+LITERALS+1].Freq++; \
  229.     s->dyn_dtree[d_code(dist)].Freq++; \
  230.     flush = (s->last_lit == s->lit_bufsize-1); \
  231.   }
  232. #else
  233. # define _tr_tally_lit(s, c, flush) flush = _tr_tally(s, 0, c)
  234. # define _tr_tally_dist(s, distance, length, flush) \
  235.               flush = _tr_tally(s, distance, length) 
  236. #endif
  237.  
  238. #endif
  239.