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 / deflate.c < prev    next >
C/C++ Source or Header  |  1993-08-13  |  29KB  |  764 lines
  1. /* deflate.c -- compress data using the deflation algorithm
  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.  *      Identify new text as repetitions of old text within a fixed-
  11.  *      length sliding window trailing behind the new text.
  12.  *
  13.  *  DISCUSSION
  14.  *
  15.  *      The "deflation" process depends on being able to identify portions
  16.  *      of the input text which are identical to earlier input (within a
  17.  *      sliding window trailing behind the input currently being processed).
  18.  *
  19.  *      The most straightforward technique turns out to be the fastest for
  20.  *      most input files: try all possible matches and select the longest.
  21.  *      The key feature of this algorithm is that insertions into the string
  22.  *      dictionary are very simple and thus fast, and deletions are avoided
  23.  *      completely. Insertions are performed at each input character, whereas
  24.  *      string matches are performed only when the previous match ends. So it
  25.  *      is preferable to spend more time in matches to allow very fast string
  26.  *      insertions and avoid deletions. The matching algorithm for small
  27.  *      strings is inspired from that of Rabin & Karp. A brute force approach
  28.  *      is used to find longer strings when a small match has been found.
  29.  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
  30.  *      (by Leonid Broukhis).
  31.  *         A previous version of this file used a more sophisticated algorithm
  32.  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
  33.  *      time, but has a larger average cost, uses more memory and is patented.
  34.  *      However the F&G algorithm may be faster for some highly redundant
  35.  *      files if the parameter max_chain_length (described below) is too large.
  36.  *
  37.  *  ACKNOWLEDGEMENTS
  38.  *
  39.  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
  40.  *      I found it in 'freeze' written by Leonid Broukhis.
  41.  *      Thanks to many info-zippers for bug reports and testing.
  42.  *
  43.  *  REFERENCES
  44.  *
  45.  *      APPNOTE.TXT documentation file in PKZIP 1.93a distribution.
  46.  *
  47.  *      A description of the Rabin and Karp algorithm is given in the book
  48.  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
  49.  *
  50.  *      Fiala,E.R., and Greene,D.H.
  51.  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
  52.  *
  53.  *  INTERFACE
  54.  *
  55.  *      void lm_init (int pack_level, ush *flags)
  56.  *          Initialize the "longest match" routines for a new file
  57.  *
  58.  *      ulg deflate (void)
  59.  *          Processes a new input file and return its compressed length. Sets
  60.  *          the compressed length, crc, deflate flags and internal file
  61.  *          attributes.
  62.  */
  63.  
  64. #include <stdio.h>
  65.  
  66. #include "tailor.h"
  67. #include "gzip.h"
  68. #include "lzw.h" /* just for consistency checking */
  69.  
  70. #ifdef RCSID
  71. static char rcsid[] = "$Id: deflate.c,v 0.15 1993/06/24 10:53:53 jloup Exp $";
  72. #endif
  73.  
  74. /* ===========================================================================
  75.  * Configuration parameters
  76.  */
  77.  
  78. /* Compile with MEDIUM_MEM to reduce the memory requirements or
  79.  * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the
  80.  * entire input file can be held in memory (not possible on 16 bit systems).
  81.  * Warning: defining these symbols affects HASH_BITS (see below) and thus
  82.  * affects the compression ratio. The compressed output
  83.  * is still correct, and might even be smaller in some cases.
  84.  */
  85.  
  86. #ifdef SMALL_MEM
  87. #   define HASH_BITS  13  /* Number of bits used to hash strings */
  88. #endif
  89. #ifdef MEDIUM_MEM
  90. #   define HASH_BITS  14
  91. #endif
  92. #ifndef HASH_BITS
  93. #   define HASH_BITS  15
  94.    /* For portability to 16 bit machines, do not use values above 15. */
  95. #endif
  96.  
  97. /* To save space (see unlzw.c), we overlay prev+head with tab_prefix and
  98.  * window with tab_suffix. Check that we can do this:
  99.  */
  100. #if (WSIZE<<1) > (1<<BITS)
  101.    error: cannot overlay window with tab_suffix and prev with tab_prefix0
  102. #endif
  103. #if HASH_BITS > BITS-1
  104.    error: cannot overlay head with tab_prefix1
  105. #endif
  106.  
  107. #define HASH_SIZE (unsigned)(1<<HASH_BITS)
  108. #define HASH_MASK (HASH_SIZE-1)
  109. #define WMASK     (WSIZE-1)
  110. /* HASH_SIZE and WSIZE must be powers of two */
  111.  
  112. #define NIL 0
  113. /* Tail of hash chains */
  114.  
  115. #define FAST 4
  116. #define SLOW 2
  117. /* speed options for the general purpose bit flag */
  118.  
  119. #ifndef TOO_FAR
  120. #  define TOO_FAR 4096
  121. #endif
  122. /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
  123.  
  124. /* ===========================================================================
  125.  * Local data used by the "longest match" routines.
  126.  */
  127.  
  128. typedef ush Pos;
  129. typedef unsigned IPos;
  130. /* A Pos is an index in the character window. We use short instead of int to
  131.  * save space in the various tables. IPos is used only for parameter passing.
  132.  */
  133.  
  134. /* DECLARE(uch, window, 2L*WSIZE); */
  135. /* Sliding window. Input bytes are read into the second half of the window,
  136.  * and move to the first half later to keep a dictionary of at least WSIZE
  137.  * bytes. With this organization, matches are limited to a distance of
  138.  * WSIZE-MAX_MATCH bytes, but this ensures that IO is always
  139.  * performed with a length multiple of the block size. Also, it limits
  140.  * the window size to 64K, which is quite useful on MSDOS.
  141.  * To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would
  142.  * be less efficient).
  143.  */
  144.  
  145. /* DECLARE(Pos, prev, WSIZE); */
  146. /* Link to older string with same hash index. To limit the size of this
  147.  * array to 64K, this link is maintained only for the last 32K strings.
  148.  * An index in this array is thus a window index modulo 32K.
  149.  */
  150.  
  151. /* DECLARE(Pos, head, 1<<HASH_BITS); */
  152. /* Heads of the hash chains or NIL. */
  153.  
  154. ulg window_size = (ulg)2*WSIZE;
  155. /* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
  156.  * input file length plus MIN_LOOKAHEAD.
  157.  */
  158.  
  159. long block_start;
  160. /* window position at the beginning of the current output block. Gets
  161.  * negative when the window is moved backwards.
  162.  */
  163.  
  164. local unsigned ins_h;  /* hash index of string to be inserted */
  165.  
  166. #define H_SHIFT  ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)
  167. /* Number of bits by which ins_h and del_h must be shifted at each
  168.  * input step. It must be such that after MIN_MATCH steps, the oldest
  169.  * byte no longer takes part in the hash key, that is:
  170.  *   H_SHIFT * MIN_MATCH >= HASH_BITS
  171.  */
  172.  
  173. unsigned int near prev_length;
  174. /* Length of the best match at previous step. Matches not greater than this
  175.  * are discarded. This is used in the lazy match evaluation.
  176.  */
  177.  
  178.       unsigned near strstart;      /* start of string to insert */
  179.       unsigned near match_start;   /* start of matching string */
  180. local int           eofile;        /* flag set at end of input file */
  181. local unsigned      lookahead;     /* number of valid bytes ahead in window */
  182.  
  183. unsigned near max_chain_length;
  184. /* To speed up deflation, hash chains are never searched beyond this length.
  185.  * A higher limit improves compression ratio but degrades the speed.
  186.  */
  187.  
  188. local unsigned int max_lazy_match;
  189. /* Attempt to find a better match only when the current match is strictly
  190.  * smaller than this value. This mechanism is used only for compression
  191.  * levels >= 4.
  192.  */
  193. #define max_insert_length  max_lazy_match
  194. /* Insert new strings in the hash table only if the match length
  195.  * is not greater than this length. This saves time but degrades compression.
  196.  * max_insert_length is used only for compression levels <= 3.
  197.  */
  198.  
  199. local int compr_level;
  200. /* compression level (1..9) */
  201.  
  202. unsigned near good_match;
  203. /* Use a faster search when the previous match is longer than this */
  204.  
  205.  
  206. /* Values for max_lazy_match, good_match and max_chain_length, depending on
  207.  * the desired pack level (0..9). The values given below have been tuned to
  208.  * exclude worst case performance for pathological files. Better values may be
  209.  * found for specific files.
  210.  */
  211.  
  212. typedef struct config {
  213.    ush good_length; /* reduce lazy search above this match length */
  214.    ush max_lazy;    /* do not perform lazy search above this match length */
  215.    ush nice_length; /* quit search above this match length */
  216.    ush max_chain;
  217. } config;
  218.  
  219. #ifdef  FULL_SEARCH
  220. # de