home *** CD-ROM | disk | FTP | other *** search
/ CD Shareware Magazine 1996 December / CD_shareware_12-96.iso / DOS / Programa / ZLIB095.ZIP / DEFLATE.C < prev    next >
Encoding:
C/C++ Source or Header  |  1995-08-13  |  37.2 KB  |  1,004 lines
  1. /* deflate.c -- compress data using the deflation algorithm
  2.  * Copyright (C) 1995 Jean-loup Gailly.
  3.  * For conditions of distribution and use, see copyright notice in zlib.h 
  4.  */
  5.  
  6. /*
  7.  *  ALGORITHM
  8.  *
  9.  *      The "deflation" process depends on being able to identify portions
  10.  *      of the input text which are identical to earlier input (within a
  11.  *      sliding window trailing behind the input currently being processed).
  12.  *
  13.  *      The most straightforward technique turns out to be the fastest for
  14.  *      most input files: try all possible matches and select the longest.
  15.  *      The key feature of this algorithm is that insertions into the string
  16.  *      dictionary are very simple and thus fast, and deletions are avoided
  17.  *      completely. Insertions are performed at each input character, whereas
  18.  *      string matches are performed only when the previous match ends. So it
  19.  *      is preferable to spend more time in matches to allow very fast string
  20.  *      insertions and avoid deletions. The matching algorithm for small
  21.  *      strings is inspired from that of Rabin & Karp. A brute force approach
  22.  *      is used to find longer strings when a small match has been found.
  23.  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
  24.  *      (by Leonid Broukhis).
  25.  *         A previous version of this file used a more sophisticated algorithm
  26.  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
  27.  *      time, but has a larger average cost, uses more memory and is patented.
  28.  *      However the F&G algorithm may be faster for some highly redundant
  29.  *      files if the parameter max_chain_length (described below) is too large.
  30.  *
  31.  *  ACKNOWLEDGEMENTS
  32.  *
  33.  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
  34.  *      I found it in 'freeze' written by Leonid Broukhis.
  35.  *      Thanks to many people for bug reports and testing.
  36.  *
  37.  *  REFERENCES
  38.  *
  39.  *      Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
  40.  *      Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
  41.  *
  42.  *      A description of the Rabin and Karp algorithm is given in the book
  43.  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
  44.  *
  45.  *      Fiala,E.R., and Greene,D.H.
  46.  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
  47.  *
  48.  */
  49.  
  50. /* $Id: deflate.c,v 1.8 1995/05/03 17:27:08 jloup Exp $ */
  51.  
  52. #include "deflate.h"
  53.  
  54. char copyright[] = " deflate Copyright 1995 Jean-loup Gailly ";
  55. /*
  56.   If you use the zlib library in a product, an acknowledgment is welcome
  57.   in the documentation of your product. If for some reason you cannot
  58.   include such an acknowledgment, I would appreciate that you keep this
  59.   copyright string in the executable of your product.
  60.  */
  61.  
  62. #define NIL 0
  63. /* Tail of hash chains */
  64.  
  65. #ifndef TOO_FAR
  66. #  define TOO_FAR 4096
  67. #endif
  68. /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
  69.  
  70. #define MIN_LOOKAHEAD (MAX_MATCH+MIN_MATCH+1)
  71. /* Minimum amount of lookahead, except at the end of the input file.
  72.  * See deflate.c for comments about the MIN_MATCH+1.
  73.  */
  74.  
  75. /* Values for max_lazy_match, good_match and max_chain_length, depending on
  76.  * the desired pack level (0..9). The values given below have been tuned to
  77.  * exclude worst case performance for pathological files. Better values may be
  78.  * found for specific files.
  79.  */
  80.  
  81. typedef struct config_s {
  82.    ush good_length; /* reduce lazy search above this match length */
  83.    ush max_lazy;    /* do not perform lazy search above this match length */
  84.    ush nice_length; /* quit search above this match length */
  85.    ush max_chain;
  86. } config;
  87.  
  88. local config configuration_table[10] = {
  89. /*      good lazy nice chain */
  90. /* 0 */ {0,    0,  0,    0},  /* store only */
  91. /* 1 */ {4,    4,  8,    4},  /* maximum speed, no lazy matches */
  92. /* 2 */ {4,    5, 16,    8},
  93. /* 3 */ {4,    6, 32,   32},
  94.  
  95. /* 4 */ {4,    4, 16,   16},  /* lazy matches */
  96. /* 5 */ {8,   16, 32,   32},
  97. /* 6 */ {8,   16, 128, 128},
  98. /* 7 */ {8,   32, 128, 256},
  99. /* 8 */ {32, 128, 258, 1024},
  100. /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
  101.  
  102. /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
  103.  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
  104.  * meaning.
  105.  */
  106.  
  107. #define EQUAL 0
  108. /* result of memcmp for equal strings */
  109.  
  110. struct static_tree_desc_s {int dummy;}; /* for buggy compilers */
  111.  
  112. /* ===========================================================================
  113.  *  Prototypes for local functions.
  114.  */
  115.  
  116. local void fill_window   OF((deflate_state *s));
  117. local int  deflate_fast  OF((deflate_state *s, int flush));
  118. local int  deflate_slow  OF((deflate_state *s, int flush));
  119. local void lm_init       OF((deflate_state *s));
  120. local int longest_match  OF((deflate_state *s, IPos cur_match));
  121. local void putShortMSB   OF((deflate_state *s, uInt b));
  122. local void flush_pending OF((z_stream *strm));
  123. local int read_buf       OF((z_stream *strm, charf *buf, unsigned size));
  124. #ifdef ASMV
  125.       void match_init OF((void)); /* asm code initialization */
  126. #endif
  127.  
  128. #ifdef DEBUG
  129. local  void check_match OF((deflate_state *s, IPos start, IPos match,
  130.                             int length));
  131. #endif
  132.  
  133.  
  134. /* ===========================================================================
  135.  * Update a hash value with the given input byte
  136.  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
  137.  *    input characters, so that a running hash key can be computed from the
  138.  *    previous key instead of complete recalculation each time.
  139.  */
  140. #define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
  141.  
  142.  
  143. /* ===========================================================================
  144.  * Insert string str in the dictionary and set match_head to the previous head
  145.  * of the hash chain (the most recent string with same hash key). Return
  146.  * the previous length of the hash chain.
  147.  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
  148.  *    input characters and the first MIN_MATCH bytes of str are valid
  149.  *    (except for the last MIN_MATCH-1 bytes of the input file).
  150.  */
  151. #define INSERT_STRING(s, str, match_head) \
  152.    (UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
  153.     s->prev[(str) & s->w_mask] = match_head = s->head[s->ins_h], \
  154.     s->head[s->ins_h] = (str))
  155.  
  156. /* ===========================================================================
  157.  * Initialize the hash table (avoiding 64K overflow for 16 bit systems).
  158.  * prev[] will be initialized on the fly.
  159.  */
  160. #define CLEAR_HASH(s) \
  161.     s->head[s->hash_size-1] = NIL; \
  162.     zmemzero((charf *)s->head, (unsigned)(s->hash_size-1)*sizeof(*s->head));
  163.  
  164. /* ========================================================================= */
  165. int deflateInit (strm, level)
  166.     z_stream *strm;
  167.     int level;
  168. {
  169.     return deflateInit2 (strm, level, DEFLATED, MAX_WBITS, DEF_MEM_LEVEL, 0);
  170.     /* To do: ignore strm->next_in if we use it as window */
  171. }
  172.  
  173. /* ========================================================================= */
  174. int deflateInit2 (strm, level, method, windowBits, memLevel, strategy)
  175.     z_stream *strm;
  176.     int  level;
  177.     int  method;
  178.     int  windowBits;
  179.     int  memLevel;
  180.     int  strategy;
  181. {
  182.     deflate_state *s;
  183.     int noheader = 0;
  184.  
  185.     if (strm == Z_NULL) return Z_STREAM_ERROR;
  186.  
  187.     strm->msg = Z_NULL;
  188.     if (strm->zalloc == Z_NULL) strm->zalloc = zcalloc;
  189.     if (strm->zfree == Z_NULL) strm->zfree = zcfree;
  190.  
  191.     if (level == Z_DEFAULT_COMPRESSION) level = 6;
  192.  
  193.     if (windowBits < 0) { /* undocumented feature: suppress zlib header */
  194.         noheader = 1;
  195.         windowBits = -windowBits;
  196.     }
  197.     if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || method != DEFLATED ||
  198.         windowBits < 8 || windowBits > 15 || level < 1 || level > 9) {
  199.         return Z_STREAM_ERROR;
  200.     }
  201.     s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
  202.     if (s == Z_NULL) return Z_MEM_ERROR;
  203.     strm->state = (struct internal_state FAR *)s;
  204.     s->strm = strm;
  205.  
  206.     s->noheader = noheader;
  207.     s->w_bits = windowBits;
  208.     s->w_size = 1 << s->w_bits;
  209.     s->w_mask = s->w_size - 1;
  210.  
  211.     s->hash_bits = memLevel + 7;
  212.     s->hash_size = 1 << s->hash_bits;
  213.     s->hash_mask = s->hash_size - 1;
  214.     s->hash_shift =  ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
  215.  
  216.     s->window = (Bytef *) ZALLOC(strm, s->w_size, 2*sizeof(Byte));
  217.     s->prev   = (Posf *)  ZALLOC(strm, s->w_size, sizeof(Pos));
  218.     s->head   = (Posf *)  ZALLOC(strm, s->hash_size, sizeof(Pos));
  219.  
  220.     s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
  221.  
  222.     s->pending_buf = (uchf *) ZALLOC(strm, s->lit_bufsize, 2*sizeof(ush));
  223.  
  224.     if (s->window == Z_NULL || s->prev == Z_NULL || s->head == Z_NULL ||
  225.         s->pending_buf == Z_NULL) {
  226.         strm->msg = z_errmsg[1-Z_MEM_ERROR];
  227.         deflateEnd (strm);
  228.         return Z_MEM_ERROR;
  229.     }
  230.     s->d_buf = (ushf *) &(s->pending_buf[s->lit_bufsize]);
  231.     s->l_buf = (uchf *) &(s->pending_buf[3*s->lit_bufsize]);
  232.     /* We overlay pending_buf and d_buf+l_buf. This works since the average
  233.      * output size for (length,distance) codes is <= 32 bits (worst case
  234.      * is 15+15+13=33).
  235.      */
  236.  
  237.     s->level = level;
  238.     s->strategy = strategy;
  239.     s->method = (Byte)method;
  240.  
  241.     return deflateReset(strm);
  242. }
  243.  
  244. /* ========================================================================= */
  245. int deflateReset (strm)
  246.     z_stream *strm;
  247. {
  248.     deflate_state *s;
  249.     
  250.     if (strm == Z_NULL || strm->state == Z_NULL ||
  251.         strm->zalloc == Z_NULL || strm->zfree == Z_NULL) return Z_STREAM_ERROR;
  252.  
  253.     strm->total_in = strm->total_out = 0;
  254.     strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
  255.     strm->data_type = Z_UNKNOWN;
  256.  
  257.     s = (deflate_state *)strm->state;
  258.     s->pending = 0;
  259.     s->pending_out = s->pending_buf;
  260.  
  261.     if (s->noheader < 0) {
  262.         s->noheader = 0; /* was set to -1 by deflate(..., Z_FINISH); */
  263.     }
  264.     s->status = s->noheader ? BUSY_STATE : INIT_STATE;
  265.     s->adler = 1;
  266.  
  267.     ct_init(s);
  268.     lm_init(s);
  269.  
  270.     return Z_OK;
  271. }
  272.  
  273. /* =========================================================================
  274.  * Put a short in the pending buffer. The 16-bit value is put in MSB order.
  275.  * IN assertion: the stream state is correct and there is enough room in
  276.  * pending_buf.
  277.  */
  278. local void putShortMSB (s, b)
  279.     deflate_state *s;
  280.     uInt b;
  281. {
  282.     put_byte(s, (Byte)(b >> 8));
  283.     put_byte(s, (Byte)(b & 0xff));
  284. }   
  285.  
  286. /* =========================================================================
  287.  * Flush as much pending output as possible.
  288.  */
  289. local void flush_pending(strm)
  290.     z_stream *strm;
  291. {
  292.     unsigned len = strm->state->pending;
  293.  
  294.     if (len > strm->avail_out) len = strm->avail_out;
  295.     if (len == 0) return;
  296.  
  297.     zmemcpy(strm->next_out, strm->state->pending_out, len);
  298.     strm->next_out  += len;
  299.     strm->state->pending_out  += len;
  300.     strm->total_out += len;
  301.     strm->avail_out  -= len;
  302.     strm->state->pending -= len;
  303.     if (strm->state->pending == 0) {
  304.         strm->state->pending_out = strm->state->pending_buf;
  305.     }
  306. }
  307.  
  308. /* ========================================================================= */
  309. int deflate (strm, flush)
  310.     z_stream *strm;
  311.     int flush;
  312. {
  313.     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  314.     
  315.     if (strm->next_out == Z_NULL ||
  316.         (strm->next_in == Z_NULL && strm->avail_in != 0)) {
  317.         ERR_RETURN(strm, Z_STREAM_ERROR);
  318.     }
  319.     if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
  320.  
  321.     strm->state->strm = strm; /* just in case */
  322.  
  323.     /* Write the zlib header */
  324.     if (strm->state->status == INIT_STATE) {
  325.  
  326.         uInt header = (DEFLATED + ((strm->state->w_bits-8)<<4)) << 8;
  327.         uInt level_flags = (strm->state->level-1) >> 1;
  328.  
  329.         if (level_flags > 3) level_flags = 3;
  330.         header |= (level_flags << 6);
  331.         header += 31 - (header % 31);
  332.  
  333.         strm->state->status = BUSY_STATE;
  334.         putShortMSB(strm->state, header);
  335.     }
  336.  
  337.     /* Flush as much pending output as possible */
  338.     if (strm->state->pending != 0) {
  339.         flush_pending(strm);
  340.         if (strm->avail_out == 0) return Z_OK;
  341.     }
  342.  
  343.     /* User must not provide more input after the first FINISH: */
  344.     if (strm->state->status == FINISH_STATE && strm->avail_in != 0) {
  345.         ERR_RETURN(strm, Z_BUF_ERROR);
  346.     }
  347.  
  348.     /* Start a new block or continue the current one.
  349.      */
  350.     if (strm->avail_in != 0 || strm->state->lookahead != 0 ||
  351.         (flush != Z_NO_FLUSH && strm->state->status != FINISH_STATE)) {
  352.         int quit;
  353.  
  354.         if (flush == Z_FINISH) {
  355.             strm->state->status = FINISH_STATE;
  356.         }
  357.         if (strm->state->level <= 3) {
  358.             quit = deflate_fast(strm->state, flush);
  359.         } else {
  360.             quit = deflate_slow(strm->state, flush);
  361.         }
  362.         if (quit || strm->avail_out == 0) return Z_OK;
  363.         /* If flush != Z_NO_FLUSH && avail_out == 0, the next call
  364.          * of deflate should use the same flush parameter to make sure
  365.          * that the flush is complete. So we don't have to output an
  366.          * empty block here, this will be done at next call. This also
  367.          * ensures that for a very small output buffer, we emit at most
  368.          * one empty block.
  369.          */
  370.         if (flush != Z_OK && flush != Z_FINISH) {
  371.             if (flush == Z_PARTIAL_FLUSH) {
  372.                 ct_align(strm->state);
  373.             } else { /* FULL_FLUSH or SYNC_FLUSH */
  374.                 ct_stored_block(strm->state, (char*)0, 0L, 0);
  375.                 /* For a full flush, this empty block will be recognized
  376.                  * as a special marker by inflate_sync().
  377.                  */
  378.                 if (flush == Z_FULL_FLUSH) {
  379.                     CLEAR_HASH(strm->state);             /* forget history */
  380.                 }
  381.             }
  382.             flush_pending(strm);
  383.             if (strm->avail_out == 0) return Z_OK;
  384.         }
  385.     }
  386.     Assert(strm->avail_out > 0, "bug2");
  387.  
  388.     if (flush != Z_FINISH) return Z_OK;
  389.     if (strm->state->noheader) return Z_STREAM_END;
  390.  
  391.     /* Write the zlib trailer (adler32) */
  392.     putShortMSB(strm->state, (uInt)(strm->state->adler >> 16));
  393.     putShortMSB(strm->state, (uInt)(strm->state->adler & 0xffff));
  394.     flush_pending(strm);
  395.     /* If avail_out is zero, the application will call deflate again
  396.      * to flush the rest.
  397.      */
  398.     strm->state->noheader = -1; /* write the trailer only once! */
  399.     return strm->state->pending != 0 ? Z_OK : Z_STREAM_END;
  400. }
  401.  
  402. /* ========================================================================= */
  403. int deflateEnd (strm)
  404.     z_stream *strm;
  405. {
  406.     if (strm == Z_NULL || strm->state == Z_NULL) return Z_STREAM_ERROR;
  407.  
  408.     TRY_FREE(strm, strm->state->window);
  409.     TRY_FREE(strm, strm->state->prev);
  410.     TRY_FREE(strm, strm->state->head);
  411.     TRY_FREE(strm, strm->state->pending_buf);
  412.  
  413.     ZFREE(strm, strm->state);
  414.     strm->state = Z_NULL;
  415.  
  416.     return Z_OK;
  417. }
  418.  
  419. /* ========================================================================= */
  420. int deflateCopy (dest, source)
  421.     z_stream *dest;
  422.     z_stream *source;
  423. {
  424.     if (source == Z_NULL || dest == Z_NULL || source->state == Z_NULL) {
  425.         return Z_STREAM_ERROR;
  426.     }
  427.     *dest = *source;
  428.     return Z_STREAM_ERROR; /* to be implemented */
  429. #if 0
  430.     dest->state = (struct internal_state FAR *)
  431.         (*dest->zalloc)(1, sizeof(deflate_state));
  432.     if (dest->state == Z_NULL) return Z_MEM_ERROR;
  433.  
  434.     *(dest->state) = *(source->state);
  435.     return Z_OK;
  436. #endif
  437. }
  438.  
  439. /* ===========================================================================
  440.  * Read a new buffer from the current input stream, update the adler32
  441.  * and total number of bytes read.
  442.  */
  443. local int read_buf(strm, buf, size)
  444.     z_stream *strm;
  445.     charf *buf;
  446.     unsigned size;
  447. {
  448.     unsigned len = strm->avail_in;
  449.  
  450.     if (len > size) len = size;
  451.     if (len == 0) return 0;
  452.  
  453.     strm->avail_in  -= len;
  454.  
  455.     if (!strm->state->noheader) {
  456.         strm->state->adler = adler32(strm->state->adler, strm->next_in, len);
  457.     }
  458.     zmemcpy(buf, strm->next_in, len);
  459.     strm->next_in  += len;
  460.     strm->total_in += len;
  461.  
  462.     return (int)len;
  463. }
  464.  
  465. /* ===========================================================================
  466.  * Initialize the "longest match" routines for a new zlib stream
  467.  */
  468. local void lm_init (s)
  469.     deflate_state *s;
  470. {
  471.     s->window_size = (ulg)2L*s->w_size;
  472.  
  473.     CLEAR_HASH(s);
  474.  
  475.     /* Set the default configuration parameters:
  476.      */
  477.     s->max_lazy_match   = configuration_table[s->level].max_lazy;
  478.     s->good_match       = configuration_table[s->level].good_length;
  479.     s->nice_match       = configuration_table[s->level].nice_length;
  480.     s->max_chain_length = configuration_table[s->level].max_chain;
  481.  
  482.     s->strstart = 0;
  483.     s->block_start = 0L;
  484.     s->lookahead = 0;
  485.     s->match_length = MIN_MATCH-1;
  486.     s->match_available = 0;
  487.     s->ins_h = 0;
  488. #ifdef ASMV
  489.     match_init(); /* initialize the asm code */
  490. #endif
  491. }
  492.  
  493. /* ===========================================================================
  494.  * Set match_start to the longest match starting at the given string and
  495.  * return its length. Matches shorter or equal to prev_length are discarded,
  496.  * in which case the result is equal to prev_length and match_start is
  497.  * garbage.
  498.  * IN assertions: cur_match is the head of the hash chain for the current
  499.  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  500.  */
  501. #ifndef ASMV
  502. /* For 80x86 and 680x0, an optimized version will be provided in match.asm or
  503.  * match.S. The code will be functionally equivalent.
  504.  */
  505. local int longest_match(s, cur_match)
  506.     deflate_state *s;
  507.     IPos cur_match;                             /* current match */
  508. {
  509.     unsigned chain_length = s->max_chain_length;/* max hash chain length */
  510.     register Bytef *scan = s->window + s->strstart; /* current string */
  511.     register Bytef *match;                       /* matched string */
  512.     register int len;                           /* length of current match */
  513.     int best_len = s->prev_length;              /* best match length so far */
  514.     IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
  515.         s->strstart - (IPos)MAX_DIST(s) : NIL;
  516.     /* Stop when cur_match becomes <= limit. To simplify the code,
  517.      * we prevent matches with the string of window index 0.
  518.      */
  519.     Posf *prev = s->prev;
  520.     uInt wmask = s->w_mask;
  521.  
  522. #ifdef UNALIGNED_OK
  523.     /* Compare two bytes at a time. Note: this is not always beneficial.
  524.      * Try with and without -DUNALIGNED_OK to check.
  525.      */
  526.     register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
  527.     register ush scan_start = *(ushf*)scan;
  528.     register ush scan_end   = *(ushf*)(scan+best_len-1);
  529. #else
  530.     register Bytef *strend = s->window + s->strstart + MAX_MATCH;
  531.     register Byte scan_end1  = scan[best_len-1];
  532.     register Byte scan_end   = scan[best_len];
  533. #endif
  534.  
  535.     /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
  536.      * It is easy to get rid of this optimization if necessary.
  537.      */
  538.     Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
  539.  
  540.     /* Do not waste too much time if we already have a good match: */
  541.     if (s->prev_length >= s->good_match) {
  542.         chain_length >>= 2;
  543.     }
  544.     Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
  545.  
  546.     do {
  547.         Assert(cur_match < s->strstart, "no future");
  548.         match = s->window + cur_match;
  549.  
  550.         /* Skip to next match if the match length cannot increase
  551.          * or if the match length is less than 2:
  552.          */
  553. #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
  554.         /* This code assumes sizeof(unsigned short) == 2. Do not use
  555.          * UNALIGNED_OK if your compiler uses a different size.
  556.          */
  557.         if (*(ushf*)(match+best_len-1) != scan_end ||
  558.             *(ushf*)match != scan_start) continue;
  559.  
  560.         /* It is not necessary to compare scan[2] and match[2] since they are
  561.          * always equal when the other bytes match, given that the hash keys
  562.          * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
  563.          * strstart+3, +5, ... up to strstart+257. We check for insufficient
  564.          * lookahead only every 4th comparison; the 128th check will be made
  565.          * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
  566.          * necessary to put more guard bytes at the end of the window, or
  567.          * to check more often for insufficient lookahead.
  568.          */
  569.         Assert(scan[2] == match[2], "scan[2]?");
  570.         scan++, match++;
  571.         do {
  572.         } while (*(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
  573.                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
  574.                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
  575.                  *(ushf*)(scan+=2) == *(ushf*)(match+=2) &&
  576.                  scan < strend);
  577.         /* The funny "do {}" generates better code on most compilers */
  578.  
  579.         /* Here, scan <= window+strstart+257 */
  580.         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
  581.         if (*scan == *match) scan++;
  582.  
  583.         len = (MAX_MATCH - 1) - (int)(strend-scan);
  584.         scan = strend - (MAX_MATCH-1);
  585.  
  586. #else /* UNALIGNED_OK */
  587.  
  588.         if (match[best_len]   != scan_end  ||
  589.             match[best_len-1] != scan_end1 ||
  590.             *match            != *scan     ||
  591.             *++match          != scan[1])      continue;
  592.  
  593.         /* The check at best_len-1 can be removed because it will be made
  594.          * again later. (This heuristic is not always a win.)
  595.          * It is not necessary to compare scan[2] and match[2] since they
  596.          * are always equal when the other bytes match, given that
  597.          * the hash keys are equal and that HASH_BITS >= 8.
  598.          */
  599.         scan += 2, match++;
  600.         Assert(*scan == *match, "match[2]?");
  601.  
  602.         /* We check for insufficient lookahead only every 8th comparison;
  603.          * the 256th check will be made at strstart+258.
  604.          */
  605.         do {
  606.         } while (*++scan == *++match && *++scan == *++match &&
  607.                  *++scan == *++match && *++scan == *++match &&
  608.                  *++scan == *++match && *++scan == *++match &&
  609.                  *++scan == *++match && *++scan == *++match &&
  610.                  scan < strend);
  611.  
  612.         Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
  613.  
  614.         len = MAX_MATCH - (int)(strend - scan);
  615.         scan = strend - MAX_MATCH;
  616.  
  617. #endif /* UNALIGNED_OK */
  618.  
  619.         if (len > best_len) {
  620.             s->match_start = cur_match;
  621.             best_len = len;
  622.             if (len >= s->nice_match) break;
  623. #ifdef UNALIGNED_OK
  624.             scan_end = *(ushf*)(scan+best_len-1);
  625. #else
  626.             scan_end1  = scan[best_len-1];
  627.             scan_end   = scan[best_len];
  628. #endif
  629.         }
  630.     } while ((cur_match = prev[cur_match & wmask]) > limit
  631.              && --chain_length != 0);
  632.  
  633.     return best_len;
  634. }
  635. #endif /* ASMV */
  636.  
  637. #ifdef DEBUG
  638. /* ===========================================================================
  639.  * Check that the match at match_start is indeed a match.
  640.  */
  641. local void check_match(s, start, match, length)
  642.     deflate_state *s;
  643.     IPos start, match;
  644.     int length;
  645. {
  646.     /* check that the match is indeed a match */
  647.     if (memcmp((charf *)s->window + match,
  648.                 (charf *)s->window + start, length) != EQUAL) {
  649.         fprintf(stderr,
  650.             " start %u, match %u, length %d\n",
  651.             start, match, length);
  652.         do { fprintf(stderr, "%c%c", s->window[match++],
  653.                      s->window[start++]); } while (--length != 0);
  654.         z_error("invalid match");
  655.     }
  656.     if (verbose > 1) {
  657.         fprintf(stderr,"\\[%d,%d]", start-match, length);
  658.         do { putc(s->window[start++], stderr); } while (--length != 0);
  659.     }
  660. }
  661. #else
  662. #  define check_match(s, start, match, length)
  663. #endif
  664.  
  665. /* ===========================================================================
  666.  * Fill the window when the lookahead becomes insufficient.
  667.  * Updates strstart and lookahead.
  668.  *
  669.  * IN assertion: lookahead < MIN_LOOKAHEAD
  670.  * OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
  671.  *    At least one byte has been read, or avail_in == 0; reads are
  672.  *    performed for at least two bytes (required for the zip translate_eol
  673.  *    option -- not supported here).
  674.  */
  675. local void fill_window(s)
  676.     deflate_state *s;
  677. {
  678.     register unsigned n, m;
  679.     register Posf *p;
  680.     unsigned more;    /* Amount of free space at the end of the window. */
  681.     uInt wsize = s->w_size;
  682.  
  683.     do {
  684.         more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
  685.  
  686.         /* Deal with !@#$% 64K limit: */
  687.         if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
  688.             more = wsize;
  689.         } else if (more == (unsigned)(-1)) {
  690.             /* Very unlikely, but possible on 16 bit machine if strstart == 0
  691.              * and lookahead == 1 (input done one byte at time)
  692.              */
  693.             more--;
  694.  
  695.         /* If the window is almost full and there is insufficient lookahead,
  696.          * move the upper half to the lower one to make room in the upper half.
  697.          */
  698.         } else if (s->strstart >= wsize+MAX_DIST(s)) {
  699.  
  700.             /* By the IN assertion, the window is not empty so we can't confuse
  701.              * more == 0 with more == 64K on a 16 bit machine.
  702.              */
  703.             zmemcpy((charf *)s->window, (charf *)s->window+wsize,
  704.                    (unsigned)wsize);
  705.             s->match_start -= wsize;
  706.             s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
  707.  
  708.             s->block_start -= (long) wsize;
  709.  
  710.             /* Slide the hash table (could be avoided with 32 bit values
  711.                at the expense of memory usage):
  712.              */
  713.             n = s->hash_size;
  714.             p = &s->head[n];
  715.             do {
  716.                 m = *--p;
  717.                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
  718.             } while (--n);
  719.  
  720.             n = wsize;
  721.             p = &s->prev[n];
  722.             do {
  723.                 m = *--p;
  724.                 *p = (Pos)(m >= wsize ? m-wsize : NIL);
  725.                 /* If n is not on any hash chain, prev[n] is garbage but
  726.                  * its value will never be used.
  727.                  */
  728.             } while (--n);
  729.  
  730.             more += wsize;
  731.         }
  732.         if (s->strm->avail_in == 0) return;
  733.  
  734.         /* If there was no sliding:
  735.          *    strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
  736.          *    more == window_size - lookahead - strstart
  737.          * => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
  738.          * => more >= window_size - 2*WSIZE + 2
  739.          * In the BIG_MEM or MMAP case (not yet supported),
  740.          *   window_size == input_size + MIN_LOOKAHEAD  &&
  741.          *   strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
  742.          * Otherwise, window_size == 2*WSIZE so more >= 2.
  743.          * If there was sliding, more >= WSIZE. So in all cases, more >= 2.
  744.          */
  745.         Assert(more >= 2, "more < 2");
  746.  
  747.         n = read_buf(s->strm, (charf *)s->window + s->strstart + s->lookahead,
  748.                      more);
  749.         s->lookahead += n;
  750.  
  751.         /* Initialize the hash value now that we have some input: */
  752.         if (s->lookahead >= MIN_MATCH) {
  753.             s->ins_h = s->window[s->strstart];
  754.             UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
  755. #if MIN_MATCH != 3
  756.             Call UPDATE_HASH() MIN_MATCH-3 more times
  757. #endif
  758.         }
  759.         /* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
  760.          * but this is not important since only literal bytes will be emitted.
  761.          */
  762.  
  763.     } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
  764. }
  765.  
  766. /* ===========================================================================
  767.  * Flush the current block, with given end-of-file flag.
  768.  * IN assertion: strstart is set to the end of the current match.
  769.  */
  770. #define FLUSH_BLOCK_ONLY(s, eof) { \
  771.    ct_flush_block(s, (s->block_start >= 0L ? \
  772.                (charf *)&s->window[(unsigned)s->block_start] : \
  773.                (charf *)Z_NULL), (long)s->strstart - s->block_start, (eof)); \
  774.    s->block_start = s->strstart; \
  775.    flush_pending(s->strm); \
  776.    Tracev((stderr,"[FLUSH]")); \
  777. }
  778.  
  779. /* Same but force premature exit if necessary. */
  780. #define FLUSH_BLOCK(s, eof) { \
  781.    FLUSH_BLOCK_ONLY(s, eof); \
  782.    if (s->strm->avail_out == 0) return 1; \
  783. }
  784.  
  785. /* ===========================================================================
  786.  * Compress as much as possible from the input stream, return true if
  787.  * processing was terminated prematurely (no more input or output space).
  788.  * This function does not perform lazy evaluationof matches and inserts
  789.  * new strings in the dictionary only for unmatched strings or for short
  790.  * matches. It is used only for the fast compression options.
  791.  */
  792. local int deflate_fast(s, flush)
  793.     deflate_state *s;
  794.     int flush;
  795. {
  796.     IPos hash_head; /* head of the hash chain */
  797.     int bflush;     /* set if current block must be flushed */
  798.  
  799.     s->prev_length = MIN_MATCH-1;
  800.  
  801.     for (;;) {
  802.         /* Make sure that we always have enough lookahead, except
  803.          * at the end of the input file. We need MAX_MATCH bytes
  804.          * for the next match, plus MIN_MATCH bytes to insert the
  805.          * string following the next match.
  806.          */
  807.         if (s->lookahead < MIN_LOOKAHEAD) {
  808.             fill_window(s);
  809.             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
  810.  
  811.             if (s->lookahead == 0) break; /* flush the current block */
  812.         }
  813.  
  814.         /* Insert the string window[strstart .. strstart+2] in the
  815.          * dictionary, and set hash_head to the head of the hash chain:
  816.          */
  817.         if (s->lookahead >= MIN_MATCH) {
  818.             INSERT_STRING(s, s->strstart, hash_head);
  819.         }
  820.  
  821.         /* Find the longest match, discarding those <= prev_length.
  822.          * At this point we have always match_length < MIN_MATCH
  823.          */
  824.         if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
  825.             /* To simplify the code, we prevent matches with the string
  826.              * of window index 0 (in particular we have to avoid a match
  827.              * of the string with itself at the start of the input file).
  828.              */
  829.             if (s->strategy != Z_HUFFMAN_ONLY) {
  830.                 s->match_length = longest_match (s, hash_head);
  831.             }
  832.             /* longest_match() sets match_start */
  833.  
  834.             if (s->match_length > s->lookahead) s->match_length = s->lookahead;
  835.         }
  836.         if (s->match_length >= MIN_MATCH) {
  837.             check_match(s, s->strstart, s->match_start, s->match_length);
  838.  
  839.             bflush = ct_tally(s, s->strstart - s->match_start,
  840.                               s->match_length - MIN_MATCH);
  841.  
  842.             s->lookahead -= s->match_length;
  843.  
  844.             /* Insert new strings in the hash table only if the match length
  845.              * is not too large. This saves time but degrades compression.
  846.              */
  847.             if (s->match_length <= s->max_insert_length &&
  848.                 s->lookahead >= MIN_MATCH) {
  849.                 s->match_length--; /* string at strstart already in hash table */
  850.                 do {
  851.                     s->strstart++;
  852.                     INSERT_STRING(s, s->strstart, hash_head);
  853.                     /* strstart never exceeds WSIZE-MAX_MATCH, so there are
  854.                      * always MIN_MATCH bytes ahead.
  855.                      */
  856.                 } while (--s->match_length != 0);
  857.                 s->strstart++; 
  858.             } else {
  859.                 s->strstart += s->match_length;
  860.                 s->match_length = 0;
  861.                 s->ins_h = s->window[s->strstart];
  862.                 UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
  863. #if MIN_MATCH != 3
  864.                 Call UPDATE_HASH() MIN_MATCH-3 more times
  865. #endif
  866.                 /* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
  867.                  * matter since it will be recomputed at next deflate call.
  868.                  */
  869.             }
  870.         } else {
  871.             /* No match, output a literal byte */
  872.             Tracevv((stderr,"%c", s->window[s->strstart]));
  873.             bflush = ct_tally (s, 0, s->window[s->strstart]);
  874.             s->lookahead--;
  875.             s->strstart++; 
  876.         }
  877.         if (bflush) FLUSH_BLOCK(s, 0);
  878.     }
  879.     FLUSH_BLOCK(s, flush == Z_FINISH);
  880.     return 0; /* normal exit */
  881. }
  882.  
  883. /* ===========================================================================
  884.  * Same as above, but achieves better compression. We use a lazy
  885.  * evaluation for matches: a match is finally adopted only if there is
  886.  * no better match at the next window position.
  887.  */
  888. local int deflate_slow(s, flush)
  889.     deflate_state *s;
  890.     int flush;
  891. {
  892.     IPos hash_head;          /* head of hash chain */
  893.     int bflush;              /* set if current block must be flushed */
  894.  
  895.     /* Process the input block. */
  896.     for (;;) {
  897.         /* Make sure that we always have enough lookahead, except
  898.          * at the end of the input file. We need MAX_MATCH bytes
  899.          * for the next match, plus MIN_MATCH bytes to insert the
  900.          * string following the next match.
  901.          */
  902.         if (s->lookahead < MIN_LOOKAHEAD) {
  903.             fill_window(s);
  904.             if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) return 1;
  905.  
  906.             if (s->lookahead == 0) break; /* flush the current block */
  907.         }
  908.  
  909.         /* Insert the string window[strstart .. strstart+2] in the
  910.          * dictionary, and set hash_head to the head of the hash chain:
  911.          */
  912.         if (s->lookahead >= MIN_MATCH) {
  913.             INSERT_STRING(s, s->strstart, hash_head);
  914.         }
  915.  
  916.         /* Find the longest match, discarding those <= prev_length.
  917.          */
  918.         s->prev_length = s->match_length, s->prev_match = s->match_start;
  919.         s->match_length = MIN_MATCH-1;
  920.  
  921.         if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
  922.             s->strstart - hash_head <= MAX_DIST(s)) {
  923.             /* To simplify the code, we prevent matches with the string
  924.              * of window index 0 (in particular we have to avoid a match
  925.              * of the string with itself at the start of the input file).
  926.              */
  927.             if (s->strategy != Z_HUFFMAN_ONLY) {
  928.                 s->match_length = longest_match (s, hash_head);
  929.             }
  930.             /* longest_match() sets match_start */
  931.             if (s->match_length > s->lookahead) s->match_length = s->lookahead;
  932.  
  933.             if (s->match_length <= 5 && (s->strategy == Z_FILTERED ||
  934.                  (s->match_length == MIN_MATCH &&
  935.                   s->strstart - s->match_start > TOO_FAR))) {
  936.  
  937.                 /* If prev_match is also MIN_MATCH, match_start is garbage
  938.                  * but we will ignore the current match anyway.
  939.                  */
  940.                 s->match_length = MIN_MATCH-1;
  941.             }
  942.         }
  943.         /* If there was a match at the previous step and the current
  944.          * match is not better, output the previous match:
  945.          */
  946.         if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
  947.             uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
  948.             /* Do not insert strings in hash table beyond this. */
  949.  
  950.             check_match(s, s->strstart-1, s->prev_match, s->prev_length);
  951.  
  952.             bflush = ct_tally(s, s->strstart -1 - s->prev_match,
  953.                               s->prev_length - MIN_MATCH);
  954.  
  955.             /* Insert in hash table all strings up to the end of the match.
  956.              * strstart-1 and strstart are already inserted. If there is not
  957.              * enough lookahead, the last two strings are not inserted in
  958.              * the hash table.
  959.              */
  960.             s->lookahead -= s->prev_length-1;
  961.             s->prev_length -= 2;
  962.             do {
  963.                 if (++s->strstart <= max_insert) {
  964.                     INSERT_STRING(s, s->strstart, hash_head);
  965.                 }
  966.             } while (--s->prev_length != 0);
  967.             s->match_available = 0;
  968.             s->match_length = MIN_MATCH-1;
  969.             s->strstart++;
  970.  
  971.             if (bflush) FLUSH_BLOCK(s, 0);
  972.  
  973.         } else if (s->match_available) {
  974.             /* If there was no match at the previous position, output a
  975.              * single literal. If there was a match but the current match
  976.              * is longer, truncate the previous match to a single literal.
  977.              */
  978.             Tracevv((stderr,"%c", s->window[s->strstart-1]));
  979.             if (ct_tally (s, 0, s->window[s->strstart-1])) {
  980.                 FLUSH_BLOCK_ONLY(s, 0);
  981.             }
  982.             s->strstart++;
  983.             s->lookahead--;
  984.             if (s->strm->avail_out == 0) return 1;
  985.         } else {
  986.             /* There is no previous match to compare with, wait for
  987.              * the next step to decide.
  988.              */
  989.             s->match_available = 1;
  990.             s->strstart++;
  991.             s->lookahead--;
  992.         }
  993.     }
  994.     Assert (flush != Z_NO_FLUSH, "no flush?");
  995.     if (s->match_available) {
  996.         Tracevv((stderr,"%c", s->window[s->strstart-1]));
  997.         ct_tally (s, 0, s->window[s->strstart-1]);
  998.         s->match_available = 0;
  999.     }
  1000.     FLUSH_BLOCK(s, flush == Z_FINISH);
  1001.     return 0;
  1002. }
  1003.  
  1004.