home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 5 / FreshFish_July-August1994.bin / bbs / gnu / gzip-1.2.4-src.lha / src / amiga / gzip-1.2.4 / trees.c < prev    next >
C/C++ Source or Header  |  1993-08-17  |  41KB  |  1,076 lines
  1. /* trees.c -- output deflated data using Huffman coding
  2.  * Copyright (C) 1992-1993 Jean-loup Gailly
  3.  * This is free software; you can redistribute it and/or modify it under the
  4.  * terms of the GNU General Public License, see the file COPYING.
  5.  */
  6.  
  7. /*
  8.  *  PURPOSE
  9.  *
  10.  *      Encode various sets of source values using variable-length
  11.  *      binary code trees.
  12.  *
  13.  *  DISCUSSION
  14.  *
  15.  *      The PKZIP "deflation" process uses several Huffman trees. The more
  16.  *      common source values are represented by shorter bit sequences.
  17.  *
  18.  *      Each code tree is stored in the ZIP file in a compressed form
  19.  *      which is itself a Huffman encoding of the lengths of
  20.  *      all the code strings (in ascending order by source values).
  21.  *      The actual code strings are reconstructed from the lengths in
  22.  *      the UNZIP process, as described in the "application note"
  23.  *      (APPNOTE.TXT) distributed as part of PKWARE's PKZIP program.
  24.  *
  25.  *  REFERENCES
  26.  *
  27.  *      Lynch, Thomas J.
  28.  *          Data Compression:  Techniques and Applications, pp. 53-55.
  29.  *          Lifetime Learning Publications, 1985.  ISBN 0-534-03418-7.
  30.  *
  31.  *      Storer, James A.
  32.  *          Data Compression:  Methods and Theory, pp. 49-50.
  33.  *          Computer Science Press, 1988.  ISBN 0-7167-8156-5.
  34.  *
  35.  *      Sedgewick, R.
  36.  *          Algorithms, p290.
  37.  *          Addison-Wesley, 1983. ISBN 0-201-06672-6.
  38.  *
  39.  *  INTERFACE
  40.  *
  41.  *      void ct_init (ush *attr, int *methodp)
  42.  *          Allocate the match buffer, initialize the various tables and save
  43.  *          the location of the internal file attribute (ascii/binary) and
  44.  *          method (DEFLATE/STORE)
  45.  *
  46.  *      void ct_tally (int dist, int lc);
  47.  *          Save the match info and tally the frequency counts.
  48.  *
  49.  *      long flush_block (char *buf, ulg stored_len, int eof)
  50.  *          Determine the best encoding for the current block: dynamic trees,
  51.  *          static trees or store, and output the encoded block to the zip
  52.  *          file. Returns the total compressed length for the file so far.
  53.  *
  54.  */
  55.  
  56. #include <ctype.h>
  57.  
  58. #include "tailor.h"
  59. #include "gzip.h"
  60.  
  61. #ifdef RCSID
  62. static char rcsid[] = "$Id: trees.c,v 0.12 1993/06/10 13:27:54 jloup Exp $";
  63. #endif
  64.  
  65. /* ===========================================================================
  66.  * Constants
  67.  */
  68.  
  69. #define MAX_BITS 15
  70. /* All codes must not exceed MAX_BITS bits */
  71.  
  72. #define MAX_BL_BITS 7
  73. /* Bit length codes must not exceed MAX_BL_BITS bits */
  74.  
  75. #define LENGTH_CODES 29
  76. /* number of length codes, not counting the special END_BLOCK code */
  77.  
  78. #define LITERALS  256
  79. /* number of literal bytes 0..255 */
  80.  
  81. #define END_BLOCK 256
  82. /* end of block literal code */
  83.  
  84. #define L_CODES (LITERALS+1+LENGTH_CODES)
  85. /* number of Literal or Length codes, including the END_BLOCK code */
  86.  
  87. #define D_CODES   30
  88. /* number of distance codes */
  89.  
  90. #define BL_CODES  19
  91. /* number of codes used to transfer the bit lengths */
  92.  
  93.  
  94. local int near extra_lbits[LENGTH_CODES] /* extra bits for each length code */
  95.    = {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};
  96.  
  97. local int near extra_dbits[D_CODES] /* extra bits for each distance code */
  98.    = {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};
  99.  
  100. local int near extra_blbits[BL_CODES]/* extra bits for each bit length code */
  101.    = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
  102.  
  103. #define STORED_BLOCK 0
  104. #define STATIC_TREES 1
  105. #define DYN_TREES    2
  106. /* The three kinds of block type */
  107.  
  108. #ifndef LIT_BUFSIZE
  109. #  ifdef SMALL_MEM
  110. #    define LIT_BUFSIZE  0x2000
  111. #  else
  112. #  ifdef MEDIUM_MEM
  113. #    define LIT_BUFSIZE  0x4000
  114. #  else
  115. #    define LIT_BUFSIZE  0x8000
  116. #  endif
  117. #  endif
  118. #endif
  119. #ifndef DIST_BUFSIZE
  120. #  define DIST_BUFSIZE  LIT_BUFSIZE
  121. #endif
  122. /* Sizes of match buffers for literals/lengths and distances.  There are
  123.  * 4 reasons for limiting LIT_BUFSIZE to 64K:
  124.  *   - frequencies can be kept in 16 bit counters
  125.  *   - if compression is not successful for the first block, all input data is
  126.  *     still in the window so we can still emit a stored block even when input
  127.  *     comes from standard input.  (This can also be done for all blocks if
  128.  *     LIT_BUFSIZE is not greater than 32K.)
  129.  *   - if compression is not successful for a file smaller than 64K, we can
  130.  *     even emit a stored file instead of a stored block (saving 5 bytes).
  131.  *   - creating new Huffman trees less frequently may not provide fast
  132.  *     adaptation to changes in the input data statistics. (Take for
  133.  *     example a binary file with poorly compressible code followed by
  134.  *     a highly compressible string table.) Smaller buffer sizes give
  135.  *     fast adaptation but have of course the overhead of transmitting trees
  136.  *     more frequently.
  137.  *   - I can't count above 4
  138.  * The current code is general and allows DIST_BUFSIZE < LIT_BUFSIZE (to save
  139.  * memory at the expense of compression). Some optimizations would be possible
  140.  * if we rely on DIST_BUFSIZE == LIT_BUFSIZE.
  141.  */
  142. #if LIT_BUFSIZE > INBUFSIZ
  143.     error cannot overlay l_buf and inbuf
  144. #endif
  145.  
  146. #define REP_3_6      16
  147. /* repeat previous bit length 3-6 times (2 bits of repeat count) */
  148.  
  149. #define REPZ_3_10    17
  150. /* repeat a zero length 3-10 times  (3 bits of repeat count) */
  151.  
  152. #define REPZ_11_138  18
  153. /* repeat a zero length 11-138 times  (7 bits of repeat count) */
  154.  
  155. /* ===========================================================================
  156.  * Local data
  157.  */
  158.  
  159. /* Data structure describing a single value and its code string. */
  160. typedef struct ct_data {
  161.     union {
  162.         ush  freq;       /* frequency count */
  163.         ush  code;       /* bit string */
  164.     } fc;
  165.     union {
  166.         ush  dad;        /* father node in Huffman tree */
  167.         ush  len;        /* length of bit string */
  168.     } dl;
  169. } ct_data;
  170.  
  171. #define Freq fc.freq
  172. #define Code fc.code
  173. #define Dad  dl.dad
  174. #define Len  dl.len
  175.  
  176. #define HEAP_SIZE (2*L_CODES+1)
  177. /* maximum heap size */
  178.  
  179. local ct_data near dyn_ltree[HEAP_SIZE];   /* literal and length tree */
  180. local ct_data near dyn_dtree[2*D_CODES+1]; /* distance tree */
  181.  
  182. local ct_data near static_ltree[L_CODES+2];
  183. /* The static literal tree. Since the bit lengths are imposed, there is no
  184.  * need for the L_CODES extra codes used during heap construction. However
  185.  * The codes 286 and 287 are needed to build a canonical tree (see ct_init
  186.  * below).
  187.  */
  188.  
  189. local ct_data near static_dtree[D_CODES];
  190. /* The static distance tree. (Actually a trivial tree since all codes use
  191.  * 5 bits.)
  192.  */
  193.  
  194. local ct_data near bl_tree[2*BL_CODES+1];
  195. /* Huffman tree for the bit lengths */
  196.  
  197. typedef struct tree_desc {
  198.     ct_data near *dyn_tree;      /* the dynamic tree */
  199.     ct_data near *static_tree;   /* corresponding static tree or NULL */
  200.     int     near *extra_bits;    /* extra bits for each code or NULL */
  201.     int     extra_base;          /* base index for extra_bits */
  202.     int     elems;               /* max number of elements in the tree */
  203.     int     max_length;          /* max bit length for the codes */
  204.     int     max_code;            /* largest code with non zero frequency */
  205. } tree_desc;
  206.  
  207. local tree_desc near l_desc =
  208. {dyn_ltree, static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS, 0};
  209.  
  210. local tree_desc near d_desc =
  211. {dyn_dtree, static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS, 0};
  212.  
  213. local tree_desc near bl_desc =
  214. {bl_tree, (ct_data near *)0, extra_blbits, 0,      BL_CODES, MAX_BL_BITS, 0};
  215.  
  216.  
  217. local ush near bl_count[MAX_BITS+1];
  218. /* number of codes at each bit length for an optimal tree */
  219.  
  220. local uch near bl_order[BL_CODES]
  221.    = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
  222. /* The lengths of the bit length codes are sent in order of decreasing
  223.  * probability, to avoid transmitting the lengths for unused bit length codes.
  224.  */
  225.  
  226. local int near heap[2*L_CODES+1]; /* heap used to build the Huffman trees */
  227. local int heap_len;               /* number of elements in the heap */
  228. local int heap_max;               /* element of largest frequency */
  229. /* The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  230.  * The same heap array is used to build all trees.
  231.  */
  232.  
  233. local uch near depth[2*L_CODES+1];
  234. /* Depth of each subtree used as tie breaker for trees of equal frequency */
  235.  
  236. local uch length_code[MAX_MATCH-MIN_MATCH+1];
  237. /* length co