git.cworth.org Git - gzip/blob - deflate.c

   1 /* deflate.c -- compress data using the deflation algorithm
   2
   3    Copyright (C) 1999, 2006 Free Software Foundation, Inc.
   4    Copyright (C) 1992-1993 Jean-loup Gailly
   5
   6    This program is free software; you can redistribute it and/or modify
   7    it under the terms of the GNU General Public License as published by
   8    the Free Software Foundation; either version 2, or (at your option)
   9    any later version.
  10
  11    This program is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14    GNU General Public License for more details.
  15
  16    You should have received a copy of the GNU General Public License
  17    along with this program; if not, write to the Free Software Foundation,
  18    Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
  19
  20 /*
  21  *  PURPOSE
  22  *
  23  *      Identify new text as repetitions of old text within a fixed-
  24  *      length sliding window trailing behind the new text.
  25  *
  26  *  DISCUSSION
  27  *
  28  *      The "deflation" process depends on being able to identify portions
  29  *      of the input text which are identical to earlier input (within a
  30  *      sliding window trailing behind the input currently being processed).
  31  *
  32  *      The most straightforward technique turns out to be the fastest for
  33  *      most input files: try all possible matches and select the longest.
  34  *      The key feature of this algorithm is that insertions into the string
  35  *      dictionary are very simple and thus fast, and deletions are avoided
  36  *      completely. Insertions are performed at each input character, whereas
  37  *      string matches are performed only when the previous match ends. So it
  38  *      is preferable to spend more time in matches to allow very fast string
  39  *      insertions and avoid deletions. The matching algorithm for small
  40  *      strings is inspired from that of Rabin & Karp. A brute force approach
  41  *      is used to find longer strings when a small match has been found.
  42  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
  43  *      (by Leonid Broukhis).
  44  *         A previous version of this file used a more sophisticated algorithm
  45  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
  46  *      time, but has a larger average cost, uses more memory and is patented.
  47  *      However the F&G algorithm may be faster for some highly redundant
  48  *      files if the parameter max_chain_length (described below) is too large.
  49  *
  50  *  ACKNOWLEDGEMENTS
  51  *
  52  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
  53  *      I found it in 'freeze' written by Leonid Broukhis.
  54  *      Thanks to many info-zippers for bug reports and testing.
  55  *
  56  *  REFERENCES
  57  *
  58  *      APPNOTE.TXT documentation file in PKZIP 1.93a distribution.
  59  *
  60  *      A description of the Rabin and Karp algorithm is given in the book
  61  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
  62  *
  63  *      Fiala,E.R., and Greene,D.H.
  64  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
  65  *
  66  *  INTERFACE
  67  *
  68  *      void lm_init (int pack_level, ush *flags)
  69  *          Initialize the "longest match" routines for a new file
  70  *
  71  *      off_t deflate (void)
  72  *          Processes a new input file and return its compressed length. Sets
  73  *          the compressed length, crc, deflate flags and internal file
  74  *          attributes.
  75  */
  76
  77 #include <config.h>
  78 #include <stdio.h>
  79
  80 #include "tailor.h"
  81 #include "gzip.h"
  82 #include "lzw.h" /* just for consistency checking */
  83
  84 #ifdef RCSID
  85 static char rcsid[] = "$Id: deflate.c,v 1.5 2006/12/07 23:53:00 eggert Exp $";
  86 #endif
  87
  88 /* ===========================================================================
  89  * Configuration parameters
  90  */
  91
  92 /* Compile with MEDIUM_MEM to reduce the memory requirements or
  93  * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the
  94  * entire input file can be held in memory (not possible on 16 bit systems).
  95  * Warning: defining these symbols affects HASH_BITS (see below) and thus
  96  * affects the compression ratio. The compressed output
  97  * is still correct, and might even be smaller in some cases.
  98  */
  99
 100 #ifdef SMALL_MEM
 101 #   define HASH_BITS  13  /* Number of bits used to hash strings */
 102 #endif
 103 #ifdef MEDIUM_MEM
 104 #   define HASH_BITS  14
 105 #endif
 106 #ifndef HASH_BITS
 107 #   define HASH_BITS  15
 108    /* For portability to 16 bit machines, do not use values above 15. */
 109 #endif
 110
 111 /* To save space (see unlzw.c), we overlay prev+head with tab_prefix and
 112  * window with tab_suffix. Check that we can do this:
 113  */
 114 #if (WSIZE<<1) > (1<<BITS)
 115    error: cannot overlay window with tab_suffix and prev with tab_prefix0
 116 #endif
 117 #if HASH_BITS > BITS-1
 118    error: cannot overlay head with tab_prefix1
 119 #endif
 120
 121 #define HASH_SIZE (unsigned)(1<<HASH_BITS)
 122 #define HASH_MASK (HASH_SIZE-1)
 123 #define WMASK     (WSIZE-1)
 124 /* HASH_SIZE and WSIZE must be powers of two */
 125
 126 #define NIL 0
 127 /* Tail of hash chains */
 128
 129 #define FAST 4
 130 #define SLOW 2
 131 /* speed options for the general purpose bit flag */
 132
 133 #ifndef TOO_FAR
 134 #  define TOO_FAR 4096
 135 #endif
 136 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
 137
 138 #ifndef RSYNC_WIN
 139 #  define RSYNC_WIN 4096
 140 #endif
 141 /* Size of rsync window, must be < MAX_DIST */
 142
 143 #define RSYNC_SUM_MATCH(sum) ((sum) % RSYNC_WIN == 0)
 144 /* Whether window sum matches magic value */
 145
 146 /* ===========================================================================
 147  * Local data used by the "longest match" routines.
 148  */
 149
 150 typedef ush Pos;
 151 typedef unsigned IPos;
 152 /* A Pos is an index in the character window. We use short instead of int to
 153  * save space in the various tables. IPos is used only for parameter passing.
 154  */
 155
 156 /* DECLARE(uch, window, 2L*WSIZE); */
 157 /* Sliding window. Input bytes are read into the second half of the window,
 158  * and move to the first half later to keep a dictionary of at least WSIZE
 159  * bytes. With this organization, matches are limited to a distance of
 160  * WSIZE-MAX_MATCH bytes, but this ensures that IO is always
 161  * performed with a length multiple of the block size. Also, it limits
 162  * the window size to 64K, which is quite useful on MSDOS.
 163  * To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would
 164  * be less efficient).
 165  */
 166
 167 /* DECLARE(Pos, prev, WSIZE); */
 168 /* Link to older string with same hash index. To limit the size of this
 169  * array to 64K, this link is maintained only for the last 32K strings.
 170  * An index in this array is thus a window index modulo 32K.
 171  */
 172
 173 /* DECLARE(Pos, head, 1<<HASH_BITS); */
 174 /* Heads of the hash chains or NIL. */
 175
 176 ulg window_size = (ulg)2*WSIZE;
 177 /* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
 178  * input file length plus MIN_LOOKAHEAD.
 179  */
 180
 181 long block_start;
 182 /* window position at the beginning of the current output block. Gets
 183  * negative when the window is moved backwards.
 184  */
 185
 186 local unsigned ins_h;  /* hash index of string to be inserted */
 187
 188 #define H_SHIFT  ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)
 189 /* Number of bits by which ins_h and del_h must be shifted at each
 190  * input step. It must be such that after MIN_MATCH steps, the oldest
 191  * byte no longer takes part in the hash key, that is:
 192  *   H_SHIFT * MIN_MATCH >= HASH_BITS
 193  */
 194
 195 unsigned int near prev_length;
 196 /* Length of the best match at previous step. Matches not greater than this
 197  * are discarded. This is used in the lazy match evaluation.
 198  */
 199
 200       unsigned near strstart;      /* start of string to insert */
 201       unsigned near match_start;   /* start of matching string */
 202 local int           eofile;        /* flag set at end of input file */
 203 local unsigned      lookahead;     /* number of valid bytes ahead in window */
 204
 205 unsigned near max_chain_length;
 206 /* To speed up deflation, hash chains are never searched beyond this length.
 207  * A higher limit improves compression ratio but degrades the speed.
 208  */
 209
 210 local unsigned int max_lazy_match;
 211 /* Attempt to find a better match only when the current match is strictly
 212  * smaller than this value. This mechanism is used only for compression
 213  * levels >= 4.
 214  */
 215 #define max_insert_length  max_lazy_match
 216 /* Insert new strings in the hash table only if the match length
 217  * is not greater than this length. This saves time but degrades compression.
 218  * max_insert_length is used only for compression levels <= 3.
 219  */
 220
 221 local int compr_level;
 222 /* compression level (1..9) */
 223
 224 unsigned near good_match;
 225 /* Use a faster search when the previous match is longer than this */
 226
 227 local ulg rsync_sum;  /* rolling sum of rsync window */
 228 local ulg rsync_chunk_end; /* next rsync sequence point */
 229
 230 /* Values for max_lazy_match, good_match and max_chain_length, depending on
 231  * the desired pack level (0..9). The values given below have been tuned to
 232  * exclude worst case performance for pathological files. Better values may be
 233  * found for specific files.
 234  */
 235
 236 typedef struct config {
 237    ush good_length; /* reduce lazy search above this match length */
 238    ush max_lazy;    /* do not perform lazy search above this match length */
 239    ush nice_length; /* quit search above this match length */
 240    ush max_chain;
 241 } config;
 242
 243 #ifdef  FULL_SEARCH
 244 # define nice_match MAX_MATCH
 245 #else
 246   int near nice_match; /* Stop searching when current match exceeds this */
 247 #endif
 248
 249 local config configuration_table[10] = {
 250 /*      good lazy nice chain */
 251 /* 0 */ {0,    0,  0,    0},  /* store only */
 252 /* 1 */ {4,    4,  8,    4},  /* maximum speed, no lazy matches */
 253 /* 2 */ {4,    5, 16,    8},
 254 /* 3 */ {4,    6, 32,   32},
 255
 256 /* 4 */ {4,    4, 16,   16},  /* lazy matches */
 257 /* 5 */ {8,   16, 32,   32},
 258 /* 6 */ {8,   16, 128, 128},
 259 /* 7 */ {8,   32, 128, 256},
 260 /* 8 */ {32, 128, 258, 1024},
 261 /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
 262
 263 /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
 264  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
 265  * meaning.
 266  */
 267
 268 #define EQUAL 0
 269 /* result of memcmp for equal strings */
 270
 271 /* ===========================================================================
 272  *  Prototypes for local functions.
 273  */
 274 local void fill_window   OF((void));
 275 local off_t deflate_fast OF((void));
 276
 277       int  longest_match OF((IPos cur_match));
 278 #ifdef ASMV
 279       void match_init OF((void)); /* asm code initialization */
 280 #endif
 281
 282 #ifdef DEBUG
 283 local  void check_match OF((IPos start, IPos match, int length));
 284 #endif
 285
 286 /* ===========================================================================
 287  * Update a hash value with the given input byte
 288  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
 289  *    input characters, so that a running hash key can be computed from the
 290  *    previous key instead of complete recalculation each time.
 291  */
 292 #define UPDATE_HASH(h,c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
 293
 294 /* ===========================================================================
 295  * Insert string s in the dictionary and set match_head to the previous head
 296  * of the hash chain (the most recent string with same hash key). Return
 297  * the previous length of the hash chain.
 298  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
 299  *    input characters and the first MIN_MATCH bytes of s are valid
 300  *    (except for the last MIN_MATCH-1 bytes of the input file).
 301  */
 302 #define INSERT_STRING(s, match_head) \
 303    (UPDATE_HASH(ins_h, window[(s) + MIN_MATCH-1]), \
 304     prev[(s) & WMASK] = match_head = head[ins_h], \
 305     head[ins_h] = (s))
 306
 307 /* ===========================================================================
 308  * Initialize the "longest match" routines for a new file
 309  */
 310 void lm_init (pack_level, flags)
 311     int pack_level; /* 0: store, 1: best speed, 9: best compression */
 312     ush *flags;     /* general purpose bit flag */
 313 {
 314     register unsigned j;
 315
 316     if (pack_level < 1 || pack_level > 9) gzip_error ("bad pack level");
 317     compr_level = pack_level;
 318
 319     /* Initialize the hash table. */
 320 #if defined(MAXSEG_64K) && HASH_BITS == 15
 321     for (j = 0;  j < HASH_SIZE; j++) head[j] = NIL;
 322 #else
 323     memzero((char*)head, HASH_SIZE*sizeof(*head));
 324 #endif
 325     /* prev will be initialized on the fly */
 326
 327     /* rsync params */
 328     rsync_chunk_end = 0xFFFFFFFFUL;
 329     rsync_sum = 0;
 330
 331     /* Set the default configuration parameters:
 332      */
 333     max_lazy_match   = configuration_table[pack_level].max_lazy;
 334     good_match       = configuration_table[pack_level].good_length;
 335 #ifndef FULL_SEARCH
 336     nice_match       = configuration_table[pack_level].nice_length;
 337 #endif
 338     max_chain_length = configuration_table[pack_level].max_chain;
 339     if (pack_level == 1) {
 340        *flags |= FAST;
 341     } else if (pack_level == 9) {
 342        *flags |= SLOW;
 343     }
 344     /* ??? reduce max_chain_length for binary files */
 345
 346     strstart = 0;
 347     block_start = 0L;
 348 #ifdef ASMV
 349     match_init(); /* initialize the asm code */
 350 #endif
 351
 352     lookahead = read_buf((char*)window,
 353                          sizeof(int) <= 2 ? (unsigned)WSIZE : 2*WSIZE);
 354
 355     if (lookahead == 0 || lookahead == (unsigned)EOF) {
 356        eofile = 1, lookahead = 0;
 357        return;
 358     }
 359     eofile = 0;
 360     /* Make sure that we always have enough lookahead. This is important
 361      * if input comes from a device such as a tty.
 362      */
 363     while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window();
 364
 365     ins_h = 0;
 366     for (j=0; j<MIN_MATCH-1; j++) UPDATE_HASH(ins_h, window[j]);
 367     /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
 368      * not important since only literal bytes will be emitted.
 369      */
 370 }
 371
 372 /* ===========================================================================
 373  * Set match_start to the longest match starting at the given string and
 374  * return its length. Matches shorter or equal to prev_length are discarded,
 375  * in which case the result is equal to prev_length and match_start is
 376  * garbage.
 377  * IN assertions: cur_match is the head of the hash chain for the current
 378  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
 379  */
 380 #ifndef ASMV
 381 /* For MSDOS, OS/2 and 386 Unix, an optimized version is in match.asm or
 382  * match.s. The code is functionally equivalent, so you can use the C version
 383  * if desired.
 384  */
 385 int longest_match(cur_match)
 386     IPos cur_match;                             /* current match */
 387 {
 388     unsigned chain_length = max_chain_length;   /* max hash chain length */
 389     register uch *scan = window + strstart;     /* current string */
 390     register uch *match;                        /* matched string */
 391     register int len;                           /* length of current match */
 392     int best_len = prev_length;                 /* best match length so far */
 393     IPos limit = strstart > (IPos)MAX_DIST ? strstart - (IPos)MAX_DIST : NIL;
 394     /* Stop when cur_match becomes <= limit. To simplify the code,
 395      * we prevent matches with the string of window index 0.
 396      */
 397
 398 /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
 399  * It is easy to get rid of this optimization if necessary.
 400  */
 401 #if HASH_BITS < 8 || MAX_MATCH != 258
 402    error: Code too clever
 403 #endif
 404
 405 #ifdef UNALIGNED_OK
 406     /* Compare two bytes at a time. Note: this is not always beneficial.
 407      * Try with and without -DUNALIGNED_OK to check.
 408      */
 409     register uch *strend = window + strstart + MAX_MATCH - 1;
 410     register ush scan_start = *(ush*)scan;
 411     register ush scan_end   = *(ush*)(scan+best_len-1);
 412 #else
 413     register uch *strend = window + strstart + MAX_MATCH;
 414     register uch scan_end1  = scan[best_len-1];
 415     register uch scan_end   = scan[best_len];
 416 #endif
 417
 418     /* Do not waste too much time if we already have a good match: */
 419     if (prev_length >= good_match) {
 420         chain_length >>= 2;
 421     }
 422     Assert(strstart <= window_size-MIN_LOOKAHEAD, "insufficient lookahead");
 423
 424     do {
 425         Assert(cur_match < strstart, "no future");
 426         match = window + cur_match;
 427
 428         /* Skip to next match if the match length cannot increase
 429          * or if the match length is less than 2:
 430          */
 431 #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
 432         /* This code assumes sizeof(unsigned short) == 2. Do not use
 433          * UNALIGNED_OK if your compiler uses a different size.
 434          */
 435         if (*(ush*)(match+best_len-1) != scan_end ||
 436             *(ush*)match != scan_start) continue;
 437
 438         /* It is not necessary to compare scan[2] and match[2] since they are
 439          * always equal when the other bytes match, given that the hash keys
 440          * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
 441          * strstart+3, +5, ... up to strstart+257. We check for insufficient
 442          * lookahead only every 4th comparison; the 128th check will be made
 443          * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
 444          * necessary to put more guard bytes at the end of the window, or
 445          * to check more often for insufficient lookahead.
 446          */
 447         scan++, match++;
 448         do {
 449         } while (*(ush*)(scan+=2) == *(ush*)(match+=2) &&
 450                  *(ush*)(scan+=2) == *(ush*)(match+=2) &&
 451                  *(ush*)(scan+=2) == *(ush*)(match+=2) &&
 452                  *(ush*)(scan+=2) == *(ush*)(match+=2) &&
 453                  scan < strend);
 454         /* The funny "do {}" generates better code on most compilers */
 455
 456         /* Here, scan <= window+strstart+257 */
 457         Assert(scan <= window+(unsigned)(window_size-1), "wild scan");
 458         if (*scan == *match) scan++;
 459
 460         len = (MAX_MATCH - 1) - (int)(strend-scan);
 461         scan = strend - (MAX_MATCH-1);
 462
 463 #else /* UNALIGNED_OK */
 464
 465         if (match[best_len]   != scan_end  ||
 466             match[best_len-1] != scan_end1 ||
 467             *match            != *scan     ||
 468             *++match          != scan[1])      continue;
 469
 470         /* The check at best_len-1 can be removed because it will be made
 471          * again later. (This heuristic is not always a win.)
 472          * It is not necessary to compare scan[2] and match[2] since they
 473          * are always equal when the other bytes match, given that
 474          * the hash keys are equal and that HASH_BITS >= 8.
 475          */
 476         scan += 2, match++;
 477
 478         /* We check for insufficient lookahead only every 8th comparison;
 479          * the 256th check will be made at strstart+258.
 480          */
 481         do {
 482         } while (*++scan == *++match && *++scan == *++match &&
 483                  *++scan == *++match && *++scan == *++match &&
 484                  *++scan == *++match && *++scan == *++match &&
 485                  *++scan == *++match && *++scan == *++match &&
 486                  scan < strend);
 487
 488         len = MAX_MATCH - (int)(strend - scan);
 489         scan = strend - MAX_MATCH;
 490
 491 #endif /* UNALIGNED_OK */
 492
 493         if (len > best_len) {
 494             match_start = cur_match;
 495             best_len = len;
 496             if (len >= nice_match) break;
 497 #ifdef UNALIGNED_OK
 498             scan_end = *(ush*)(scan+best_len-1);
 499 #else
 500             scan_end1  = scan[best_len-1];
 501             scan_end   = scan[best_len];
 502 #endif
 503         }
 504     } while ((cur_match = prev[cur_match & WMASK]) > limit
 505              && --chain_length != 0);
 506
 507     return best_len;
 508 }
 509 #endif /* ASMV */
 510
 511 #ifdef DEBUG
 512 /* ===========================================================================
 513  * Check that the match at match_start is indeed a match.
 514  */
 515 local void check_match(start, match, length)
 516     IPos start, match;
 517     int length;
 518 {
 519     /* check that the match is indeed a match */
 520     if (memcmp((char*)window + match,
 521                 (char*)window + start, length) != EQUAL) {
 522         fprintf(stderr,
 523             " start %d, match %d, length %d\n",
 524             start, match, length);
 525         gzip_error ("invalid match");
 526     }
 527     if (verbose > 1) {
 528         fprintf(stderr,"\\[%d,%d]", start-match, length);
 529         do { putc(window[start++], stderr); } while (--length != 0);
 530     }
 531 }
 532 #else
 533 #  define check_match(start, match, length)
 534 #endif
 535
 536 /* ===========================================================================
 537  * Fill the window when the lookahead becomes insufficient.
 538  * Updates strstart and lookahead, and sets eofile if end of input file.
 539  * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0
 540  * OUT assertions: at least one byte has been read, or eofile is set;
 541  *    file reads are performed for at least two bytes (required for the
 542  *    translate_eol option).
 543  */
 544 local void fill_window()
 545 {
 546     register unsigned n, m;
 547     unsigned more = (unsigned)(window_size - (ulg)lookahead - (ulg)strstart);
 548     /* Amount of free space at the end of the window. */
 549
 550     /* If the window is almost full and there is insufficient lookahead,
 551      * move the upper half to the lower one to make room in the upper half.
 552      */
 553     if (more == (unsigned)EOF) {
 554         /* Very unlikely, but possible on 16 bit machine if strstart == 0
 555          * and lookahead == 1 (input done one byte at time)
 556          */
 557         more--;
 558     } else if (strstart >= WSIZE+MAX_DIST) {
 559         /* By the IN assertion, the window is not empty so we can't confuse
 560          * more == 0 with more == 64K on a 16 bit machine.
 561          */
 562         Assert(window_size == (ulg)2*WSIZE, "no sliding with BIG_MEM");
 563
 564         memcpy((char*)window, (char*)window+WSIZE, (unsigned)WSIZE);
 565         match_start -= WSIZE;
 566         strstart    -= WSIZE; /* we now have strstart >= MAX_DIST: */
 567         if (rsync_chunk_end != 0xFFFFFFFFUL)
 568             rsync_chunk_end -= WSIZE;
 569
 570         block_start -= (long) WSIZE;
 571
 572         for (n = 0; n < HASH_SIZE; n++) {
 573             m = head[n];
 574             head[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
 575         }
 576         for (n = 0; n < WSIZE; n++) {
 577             m = prev[n];
 578             prev[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
 579             /* If n is not on any hash chain, prev[n] is garbage but
 580              * its value will never be used.
 581              */
 582         }
 583         more += WSIZE;
 584     }
 585     /* At this point, more >= 2 */
 586     if (!eofile) {
 587         n = read_buf((char*)window+strstart+lookahead, more);
 588         if (n == 0 || n == (unsigned)EOF) {
 589             eofile = 1;
 590         } else {
 591             lookahead += n;
 592         }
 593     }
 594 }
 595
 596 local void rsync_roll(start, num)
 597     unsigned start;
 598     unsigned num;
 599 {
 600     unsigned i;
 601
 602     if (start < RSYNC_WIN) {
 603         /* before window fills. */
 604         for (i = start; i < RSYNC_WIN; i++) {
 605             if (i == start + num) return;
 606             rsync_sum += (ulg)window[i];
 607         }
 608         num -= (RSYNC_WIN - start);
 609         start = RSYNC_WIN;
 610     }
 611
 612     /* buffer after window full */
 613     for (i = start; i < start+num; i++) {
 614         /* New character in */
 615         rsync_sum += (ulg)window[i];
 616         /* Old character out */
 617         rsync_sum -= (ulg)window[i - RSYNC_WIN];
 618         if (rsync_chunk_end == 0xFFFFFFFFUL && RSYNC_SUM_MATCH(rsync_sum))
 619             rsync_chunk_end = i;
 620     }
 621 }
 622
 623 /* ===========================================================================
 624  * Set rsync_chunk_end if window sum matches magic value.
 625  */
 626 #define RSYNC_ROLL(s, n) \
 627    do { if (rsync) rsync_roll((s), (n)); } while(0)
 628
 629 /* ===========================================================================
 630  * Flush the current block, with given end-of-file flag.
 631  * IN assertion: strstart is set to the end of the current match.
 632  */
 633 #define FLUSH_BLOCK(eof) \
 634    flush_block(block_start >= 0L ? (char*)&window[(unsigned)block_start] : \
 635                 (char*)NULL, (long)strstart - block_start, flush-1, (eof))
 636
 637 /* ===========================================================================
 638  * Processes a new input file and return its compressed length. This
 639  * function does not perform lazy evaluationof matches and inserts
 640  * new strings in the dictionary only for unmatched strings or for short
 641  * matches. It is used only for the fast compression options.
 642  */
 643 local off_t deflate_fast()
 644 {
 645     IPos hash_head; /* head of the hash chain */
 646     int flush;      /* set if current block must be flushed, 2=>and padded  */
 647     unsigned match_length = 0;  /* length of best match */
 648
 649     prev_length = MIN_MATCH-1;
 650     while (lookahead != 0) {
 651         /* Insert the string window[strstart .. strstart+2] in the
 652          * dictionary, and set hash_head to the head of the hash chain:
 653          */
 654         INSERT_STRING(strstart, hash_head);
 655
 656         /* Find the longest match, discarding those <= prev_length.
 657          * At this point we have always match_length < MIN_MATCH
 658          */
 659         if (hash_head != NIL && strstart - hash_head <= MAX_DIST
 660             && strstart <= window_size - MIN_LOOKAHEAD) {
 661             /* To simplify the code, we prevent matches with the string
 662              * of window index 0 (in particular we have to avoid a match
 663              * of the string with itself at the start of the input file).
 664              */
 665             match_length = longest_match (hash_head);
 666             /* longest_match() sets match_start */
 667             if (match_length > lookahead) match_length = lookahead;
 668         }
 669         if (match_length >= MIN_MATCH) {
 670             check_match(strstart, match_start, match_length);
 671
 672             flush = ct_tally(strstart-match_start, match_length - MIN_MATCH);
 673
 674             lookahead -= match_length;
 675
 676             RSYNC_ROLL(strstart, match_length);
 677             /* Insert new strings in the hash table only if the match length
 678              * is not too large. This saves time but degrades compression.
 679              */
 680             if (match_length <= max_insert_length) {
 681                 match_length--; /* string at strstart already in hash table */
 682                 do {
 683                     strstart++;
 684                     INSERT_STRING(strstart, hash_head);
 685                     /* strstart never exceeds WSIZE-MAX_MATCH, so there are
 686                      * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
 687                      * these bytes are garbage, but it does not matter since
 688                      * the next lookahead bytes will be emitted as literals.
 689                      */
 690                 } while (--match_length != 0);
 691                 strstart++;
 692             } else {
 693                 strstart += match_length;
 694                 match_length = 0;
 695                 ins_h = window[strstart];
 696                 UPDATE_HASH(ins_h, window[strstart+1]);
 697 #if MIN_MATCH != 3
 698                 Call UPDATE_HASH() MIN_MATCH-3 more times
 699 #endif
 700             }
 701         } else {
 702             /* No match, output a literal byte */
 703             Tracevv((stderr,"%c",window[strstart]));
 704             flush = ct_tally (0, window[strstart]);
 705             RSYNC_ROLL(strstart, 1);
 706             lookahead--;
 707             strstart++;
 708         }
 709         if (rsync && strstart > rsync_chunk_end) {
 710             rsync_chunk_end = 0xFFFFFFFFUL;
 711             flush = 2;
 712         }
 713         if (flush) FLUSH_BLOCK(0), block_start = strstart;
 714
 715         /* Make sure that we always have enough lookahead, except
 716          * at the end of the input file. We need MAX_MATCH bytes
 717          * for the next match, plus MIN_MATCH bytes to insert the
 718          * string following the next match.
 719          */
 720         while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window();
 721
 722     }
 723     return FLUSH_BLOCK(1); /* eof */
 724 }
 725
 726 /* ===========================================================================
 727  * Same as above, but achieves better compression. We use a lazy
 728  * evaluation for matches: a match is finally adopted only if there is
 729  * no better match at the next window position.
 730  */
 731 off_t deflate()
 732 {
 733     IPos hash_head;          /* head of hash chain */
 734     IPos prev_match;         /* previous match */
 735     int flush;               /* set if current block must be flushed */
 736     int match_available = 0; /* set if previous match exists */
 737     register unsigned match_length = MIN_MATCH-1; /* length of best match */
 738
 739     if (compr_level <= 3) return deflate_fast(); /* optimized for speed */
 740
 741     /* Process the input block. */
 742     while (lookahead != 0) {
 743         /* Insert the string window[strstart .. strstart+2] in the
 744          * dictionary, and set hash_head to the head of the hash chain:
 745          */
 746         INSERT_STRING(strstart, hash_head);
 747
 748         /* Find the longest match, discarding those <= prev_length.
 749          */
 750         prev_length = match_length, prev_match = match_start;
 751         match_length = MIN_MATCH-1;
 752
 753         if (hash_head != NIL && prev_length < max_lazy_match &&
 754             strstart - hash_head <= MAX_DIST &&
 755             strstart <= window_size - MIN_LOOKAHEAD) {
 756             /* To simplify the code, we prevent matches with the string
 757              * of window index 0 (in particular we have to avoid a match
 758              * of the string with itself at the start of the input file).
 759              */
 760             match_length = longest_match (hash_head);
 761             /* longest_match() sets match_start */
 762             if (match_length > lookahead) match_length = lookahead;
 763
 764             /* Ignore a length 3 match if it is too distant: */
 765             if (match_length == MIN_MATCH && strstart-match_start > TOO_FAR){
 766                 /* If prev_match is also MIN_MATCH, match_start is garbage
 767                  * but we will ignore the current match anyway.
 768                  */
 769                 match_length--;
 770             }
 771         }
 772         /* If there was a match at the previous step and the current
 773          * match is not better, output the previous match:
 774          */
 775         if (prev_length >= MIN_MATCH && match_length <= prev_length) {
 776
 777             check_match(strstart-1, prev_match, prev_length);
 778
 779             flush = ct_tally(strstart-1-prev_match, prev_length - MIN_MATCH);
 780
 781             /* Insert in hash table all strings up to the end of the match.
 782              * strstart-1 and strstart are already inserted.
 783              */
 784             lookahead -= prev_length-1;
 785             prev_length -= 2;
 786             RSYNC_ROLL(strstart, prev_length+1);
 787             do {
 788                 strstart++;
 789                 INSERT_STRING(strstart, hash_head);
 790                 /* strstart never exceeds WSIZE-MAX_MATCH, so there are
 791                  * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
 792                  * these bytes are garbage, but it does not matter since the
 793                  * next lookahead bytes will always be emitted as literals.
 794                  */
 795             } while (--prev_length != 0);
 796             match_available = 0;
 797             match_length = MIN_MATCH-1;
 798             strstart++;
 799
 800             if (rsync && strstart > rsync_chunk_end) {
 801                 rsync_chunk_end = 0xFFFFFFFFUL;
 802                 flush = 2;
 803             }
 804             if (flush) FLUSH_BLOCK(0), block_start = strstart;
 805         } else if (match_available) {
 806             /* If there was no match at the previous position, output a
 807              * single literal. If there was a match but the current match
 808              * is longer, truncate the previous match to a single literal.
 809              */
 810             Tracevv((stderr,"%c",window[strstart-1]));
 811             flush = ct_tally (0, window[strstart-1]);
 812             if (rsync && strstart > rsync_chunk_end) {
 813                 rsync_chunk_end = 0xFFFFFFFFUL;
 814                 flush = 2;
 815             }
 816             if (flush) FLUSH_BLOCK(0), block_start = strstart;
 817             RSYNC_ROLL(strstart, 1);
 818             strstart++;
 819             lookahead--;
 820         } else {
 821             /* There is no previous match to compare with, wait for
 822              * the next step to decide.
 823              */
 824             if (rsync && strstart > rsync_chunk_end) {
 825                 /* Reset huffman tree */
 826                 rsync_chunk_end = 0xFFFFFFFFUL;
 827                 flush = 2;
 828                 FLUSH_BLOCK(0), block_start = strstart;
 829             }
 830             match_available = 1;
 831             RSYNC_ROLL(strstart, 1);
 832             strstart++;
 833             lookahead--;
 834         }
 835         Assert (strstart <= bytes_in && lookahead <= bytes_in, "a bit too far");
 836
 837         /* Make sure that we always have enough lookahead, except
 838          * at the end of the input file. We need MAX_MATCH bytes
 839          * for the next match, plus MIN_MATCH bytes to insert the
 840          * string following the next match.
 841          */
 842         while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window();
 843     }
 844     if (match_available) ct_tally (0, window[strstart-1]);
 845
 846     return FLUSH_BLOCK(1); /* eof */
 847 }