| 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 | /* ===========================================================================
|
|---|
| 139 | * Local data used by the "longest match" routines.
|
|---|
| 140 | */
|
|---|
| 141 |
|
|---|
| 142 | typedef ush Pos;
|
|---|
| 143 | typedef unsigned IPos;
|
|---|
| 144 | /* A Pos is an index in the character window. We use short instead of int to
|
|---|
| 145 | * save space in the various tables. IPos is used only for parameter passing.
|
|---|
| 146 | */
|
|---|
| 147 |
|
|---|
| 148 | /* DECLARE(uch, window, 2L*WSIZE); */
|
|---|
| 149 | /* Sliding window. Input bytes are read into the second half of the window,
|
|---|
| 150 | * and move to the first half later to keep a dictionary of at least WSIZE
|
|---|
| 151 | * bytes. With this organization, matches are limited to a distance of
|
|---|
| 152 | * WSIZE-MAX_MATCH bytes, but this ensures that IO is always
|
|---|
| 153 | * performed with a length multiple of the block size. Also, it limits
|
|---|
| 154 | * the window size to 64K, which is quite useful on MSDOS.
|
|---|
| 155 | * To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would
|
|---|
| 156 | * be less efficient).
|
|---|
| 157 | */
|
|---|
| 158 |
|
|---|
| 159 | /* DECLARE(Pos, prev, WSIZE); */
|
|---|
| 160 | /* Link to older string with same hash index. To limit the size of this
|
|---|
| 161 | * array to 64K, this link is maintained only for the last 32K strings.
|
|---|
| 162 | * An index in this array is thus a window index modulo 32K.
|
|---|
| 163 | */
|
|---|
| 164 |
|
|---|
| 165 | /* DECLARE(Pos, head, 1<<HASH_BITS); */
|
|---|
| 166 | /* Heads of the hash chains or NIL. */
|
|---|
| 167 |
|
|---|
| 168 | ulg window_size = (ulg)2*WSIZE;
|
|---|
| 169 | /* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
|
|---|
| 170 | * input file length plus MIN_LOOKAHEAD.
|
|---|
| 171 | */
|
|---|
| 172 |
|
|---|
| 173 | long block_start;
|
|---|
| 174 | /* window position at the beginning of the current output block. Gets
|
|---|
| 175 | * negative when the window is moved backwards.
|
|---|
| 176 | */
|
|---|
| 177 |
|
|---|
| 178 | local unsigned ins_h; /* hash index of string to be inserted */
|
|---|
| 179 |
|
|---|
| 180 | #define H_SHIFT ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)
|
|---|
| 181 | /* Number of bits by which ins_h and del_h must be shifted at each
|
|---|
| 182 | * input step. It must be such that after MIN_MATCH steps, the oldest
|
|---|
| 183 | * byte no longer takes part in the hash key, that is:
|
|---|
| 184 | * H_SHIFT * MIN_MATCH >= HASH_BITS
|
|---|
| 185 | */
|
|---|
| 186 |
|
|---|
| 187 | unsigned int near prev_length;
|
|---|
| 188 | /* Length of the best match at previous step. Matches not greater than this
|
|---|
| 189 | * are discarded. This is used in the lazy match evaluation.
|
|---|
| 190 | */
|
|---|
| 191 |
|
|---|
| 192 | unsigned near strstart; /* start of string to insert */
|
|---|
| 193 | unsigned near match_start; /* start of matching string */
|
|---|
| 194 | local int eofile; /* flag set at end of input file */
|
|---|
| 195 | local unsigned lookahead; /* number of valid bytes ahead in window */
|
|---|
| 196 |
|
|---|
| 197 | unsigned near max_chain_length;
|
|---|
| 198 | /* To speed up deflation, hash chains are never searched beyond this length.
|
|---|
| 199 | * A higher limit improves compression ratio but degrades the speed.
|
|---|
| 200 | */
|
|---|
| 201 |
|
|---|
| 202 | local unsigned int max_lazy_match;
|
|---|
| 203 | /* Attempt to find a better match only when the current match is strictly
|
|---|
| 204 | * smaller than this value. This mechanism is used only for compression
|
|---|
| 205 | * levels >= 4.
|
|---|
| 206 | */
|
|---|
| 207 | #define max_insert_length max_lazy_match
|
|---|
| 208 | /* Insert new strings in the hash table only if the match length
|
|---|
| 209 | * is not greater than this length. This saves time but degrades compression.
|
|---|
| 210 | * max_insert_length is used only for compression levels <= 3.
|
|---|
| 211 | */
|
|---|
| 212 |
|
|---|
| 213 | local int compr_level;
|
|---|
| 214 | /* compression level (1..9) */
|
|---|
| 215 |
|
|---|
| 216 | unsigned near good_match;
|
|---|
| 217 | /* Use a faster search when the previous match is longer than this */
|
|---|
| 218 |
|
|---|
| 219 |
|
|---|
| 220 | /* Values for max_lazy_match, good_match and max_chain_length, depending on
|
|---|
| 221 | * the desired pack level (0..9). The values given below have been tuned to
|
|---|
| 222 | * exclude worst case performance for pathological files. Better values may be
|
|---|
| 223 | * found for specific files.
|
|---|
| 224 | */
|
|---|
| 225 |
|
|---|
| 226 | typedef struct config {
|
|---|
| 227 | ush good_length; /* reduce lazy search above this match length */
|
|---|
| 228 | ush max_lazy; /* do not perform lazy search above this match length */
|
|---|
| 229 | ush nice_length; /* quit search above this match length */
|
|---|
| 230 | ush max_chain;
|
|---|
| 231 | } config;
|
|---|
| 232 |
|
|---|
| 233 | #ifdef FULL_SEARCH
|
|---|
| 234 | # define nice_match MAX_MATCH
|
|---|
| 235 | #else
|
|---|
| 236 | int near nice_match; /* Stop searching when current match exceeds this */
|
|---|
| 237 | #endif
|
|---|
| 238 |
|
|---|
| 239 | local config configuration_table[10] = {
|
|---|
| 240 | /* good lazy nice chain */
|
|---|
| 241 | /* 0 */ {0, 0, 0, 0}, /* store only */
|
|---|
| 242 | /* 1 */ {4, 4, 8, 4}, /* maximum speed, no lazy matches */
|
|---|
| 243 | /* 2 */ {4, 5, 16, 8},
|
|---|
| 244 | /* 3 */ {4, 6, 32, 32},
|
|---|
| 245 |
|
|---|
| 246 | /* 4 */ {4, 4, 16, 16}, /* lazy matches */
|
|---|
| 247 | /* 5 */ {8, 16, 32, 32},
|
|---|
| 248 | /* 6 */ {8, 16, 128, 128},
|
|---|
| 249 | /* 7 */ {8, 32, 128, 256},
|
|---|
| 250 | /* 8 */ {32, 128, 258, 1024},
|
|---|
| 251 | /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
|
|---|
| 252 |
|
|---|
| 253 | /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
|
|---|
| 254 | * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
|
|---|
| 255 | * meaning.
|
|---|
| 256 | */
|
|---|
| 257 |
|
|---|
| 258 | #define EQUAL 0
|
|---|
| 259 | /* result of memcmp for equal strings */
|
|---|
| 260 |
|
|---|
| 261 | /* ===========================================================================
|
|---|
| 262 | * Prototypes for local functions.
|
|---|
| 263 | */
|
|---|
| 264 | local void fill_window OF((void));
|
|---|
| 265 | local off_t deflate_fast OF((void));
|
|---|
| 266 |
|
|---|
| 267 | int longest_match OF((IPos cur_match));
|
|---|
| 268 | #ifdef ASMV
|
|---|
| 269 | void match_init OF((void)); /* asm code initialization */
|
|---|
| 270 | #endif
|
|---|
| 271 |
|
|---|
| 272 | #ifdef DEBUG
|
|---|
| 273 | local void check_match OF((IPos start, IPos match, int length));
|
|---|
| 274 | #endif
|
|---|
| 275 |
|
|---|
| 276 | /* ===========================================================================
|
|---|
| 277 | * Update a hash value with the given input byte
|
|---|
| 278 | * IN assertion: all calls to to UPDATE_HASH are made with consecutive
|
|---|
| 279 | * input characters, so that a running hash key can be computed from the
|
|---|
| 280 | * previous key instead of complete recalculation each time.
|
|---|
| 281 | */
|
|---|
| 282 | #define UPDATE_HASH(h,c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
|
|---|
| 283 |
|
|---|
| 284 | /* ===========================================================================
|
|---|
| 285 | * Insert string s in the dictionary and set match_head to the previous head
|
|---|
| 286 | * of the hash chain (the most recent string with same hash key). Return
|
|---|
| 287 | * the previous length of the hash chain.
|
|---|
| 288 | * IN assertion: all calls to to INSERT_STRING are made with consecutive
|
|---|
| 289 | * input characters and the first MIN_MATCH bytes of s are valid
|
|---|
| 290 | * (except for the last MIN_MATCH-1 bytes of the input file).
|
|---|
| 291 | */
|
|---|
| 292 | #define INSERT_STRING(s, match_head) \
|
|---|
| 293 | (UPDATE_HASH(ins_h, window[(s) + MIN_MATCH-1]), \
|
|---|
| 294 | prev[(s) & WMASK] = match_head = head[ins_h], \
|
|---|
| 295 | head[ins_h] = (s))
|
|---|
| 296 |
|
|---|
| 297 | /* ===========================================================================
|
|---|
| 298 | * Initialize the "longest match" routines for a new file
|
|---|
| 299 | */
|
|---|
| 300 | void lm_init (pack_level, flags)
|
|---|
| 301 | int pack_level; /* 0: store, 1: best speed, 9: best compression */
|
|---|
| 302 | ush *flags; /* general purpose bit flag */
|
|---|
| 303 | {
|
|---|
| 304 | register unsigned j;
|
|---|
| 305 |
|
|---|
| 306 | if (pack_level < 1 || pack_level > 9) gzip_error ("bad pack level");
|
|---|
| 307 | compr_level = pack_level;
|
|---|
| 308 |
|
|---|
| 309 | /* Initialize the hash table. */
|
|---|
| 310 | #if defined(MAXSEG_64K) && HASH_BITS == 15
|
|---|
| 311 | for (j = 0; j < HASH_SIZE; j++) head[j] = NIL;
|
|---|
| 312 | #else
|
|---|
| 313 | memzero((char*)head, HASH_SIZE*sizeof(*head));
|
|---|
| 314 | #endif
|
|---|
| 315 | /* prev will be initialized on the fly */
|
|---|
| 316 |
|
|---|
| 317 | /* Set the default configuration parameters:
|
|---|
| 318 | */
|
|---|
| 319 | max_lazy_match = configuration_table[pack_level].max_lazy;
|
|---|
| 320 | good_match = configuration_table[pack_level].good_length;
|
|---|
| 321 | #ifndef FULL_SEARCH
|
|---|
| 322 | nice_match = configuration_table[pack_level].nice_length;
|
|---|
| 323 | #endif
|
|---|
| 324 | max_chain_length = configuration_table[pack_level].max_chain;
|
|---|
| 325 | if (pack_level == 1) {
|
|---|
| 326 | *flags |= FAST;
|
|---|
| 327 | } else if (pack_level == 9) {
|
|---|
| 328 | *flags |= SLOW;
|
|---|
| 329 | }
|
|---|
| 330 | /* ??? reduce max_chain_length for binary files */
|
|---|
| 331 |
|
|---|
| 332 | strstart = 0;
|
|---|
| 333 | block_start = 0L;
|
|---|
| 334 | #ifdef ASMV
|
|---|
| 335 | match_init(); /* initialize the asm code */
|
|---|
| 336 | #endif
|
|---|
| 337 |
|
|---|
| 338 | lookahead = read_buf((char*)window,
|
|---|
| 339 | sizeof(int) <= 2 ? (unsigned)WSIZE : 2*WSIZE);
|
|---|
| 340 |
|
|---|
| 341 | if (lookahead == 0 || lookahead == (unsigned)EOF) {
|
|---|
| 342 | eofile = 1, lookahead = 0;
|
|---|
| 343 | return;
|
|---|
| 344 | }
|
|---|
| 345 | eofile = 0;
|
|---|
| 346 | /* Make sure that we always have enough lookahead. This is important
|
|---|
| 347 | * if input comes from a device such as a tty.
|
|---|
| 348 | */
|
|---|
| 349 | while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window();
|
|---|
| 350 |
|
|---|
| 351 | ins_h = 0;
|
|---|
| 352 | for (j=0; j<MIN_MATCH-1; j++) UPDATE_HASH(ins_h, window[j]);
|
|---|
| 353 | /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
|
|---|
| 354 | * not important since only literal bytes will be emitted.
|
|---|
| 355 | */
|
|---|
| 356 | }
|
|---|
| 357 |
|
|---|
| 358 | /* ===========================================================================
|
|---|
| 359 | * Set match_start to the longest match starting at the given string and
|
|---|
| 360 | * return its length. Matches shorter or equal to prev_length are discarded,
|
|---|
| 361 | * in which case the result is equal to prev_length and match_start is
|
|---|
| 362 | * garbage.
|
|---|
| 363 | * IN assertions: cur_match is the head of the hash chain for the current
|
|---|
| 364 | * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
|
|---|
| 365 | */
|
|---|
| 366 | #ifndef ASMV
|
|---|
| 367 | /* For MSDOS, OS/2 and 386 Unix, an optimized version is in match.asm or
|
|---|
| 368 | * match.s. The code is functionally equivalent, so you can use the C version
|
|---|
| 369 | * if desired.
|
|---|
| 370 | */
|
|---|
| 371 | int longest_match(cur_match)
|
|---|
| 372 | IPos cur_match; /* current match */
|
|---|
| 373 | {
|
|---|
| 374 | unsigned chain_length = max_chain_length; /* max hash chain length */
|
|---|
| 375 | register uch *scan = window + strstart; /* current string */
|
|---|
| 376 | register uch *match; /* matched string */
|
|---|
| 377 | register int len; /* length of current match */
|
|---|
| 378 | int best_len = prev_length; /* best match length so far */
|
|---|
| 379 | IPos limit = strstart > (IPos)MAX_DIST ? strstart - (IPos)MAX_DIST : NIL;
|
|---|
| 380 | /* Stop when cur_match becomes <= limit. To simplify the code,
|
|---|
| 381 | * we prevent matches with the string of window index 0.
|
|---|
| 382 | */
|
|---|
| 383 |
|
|---|
| 384 | /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
|
|---|
| 385 | * It is easy to get rid of this optimization if necessary.
|
|---|
| 386 | */
|
|---|
| 387 | #if HASH_BITS < 8 || MAX_MATCH != 258
|
|---|
| 388 | error: Code too clever
|
|---|
| 389 | #endif
|
|---|
| 390 |
|
|---|
| 391 | #ifdef UNALIGNED_OK
|
|---|
| 392 | /* Compare two bytes at a time. Note: this is not always beneficial.
|
|---|
| 393 | * Try with and without -DUNALIGNED_OK to check.
|
|---|
| 394 | */
|
|---|
| 395 | register uch *strend = window + strstart + MAX_MATCH - 1;
|
|---|
| 396 | register ush scan_start = *(ush*)scan;
|
|---|
| 397 | register ush scan_end = *(ush*)(scan+best_len-1);
|
|---|
| 398 | #else
|
|---|
| 399 | register uch *strend = window + strstart + MAX_MATCH;
|
|---|
| 400 | register uch scan_end1 = scan[best_len-1];
|
|---|
| 401 | register uch scan_end = scan[best_len];
|
|---|
| 402 | #endif
|
|---|
| 403 |
|
|---|
| 404 | /* Do not waste too much time if we already have a good match: */
|
|---|
| 405 | if (prev_length >= good_match) {
|
|---|
| 406 | chain_length >>= 2;
|
|---|
| 407 | }
|
|---|
| 408 | Assert(strstart <= window_size-MIN_LOOKAHEAD, "insufficient lookahead");
|
|---|
| 409 |
|
|---|
| 410 | do {
|
|---|
| 411 | Assert(cur_match < strstart, "no future");
|
|---|
| 412 | match = window + cur_match;
|
|---|
| 413 |
|
|---|
| 414 | /* Skip to next match if the match length cannot increase
|
|---|
| 415 | * or if the match length is less than 2:
|
|---|
| 416 | */
|
|---|
| 417 | #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
|
|---|
| 418 | /* This code assumes sizeof(unsigned short) == 2. Do not use
|
|---|
| 419 | * UNALIGNED_OK if your compiler uses a different size.
|
|---|
| 420 | */
|
|---|
| 421 | if (*(ush*)(match+best_len-1) != scan_end ||
|
|---|
| 422 | *(ush*)match != scan_start) continue;
|
|---|
| 423 |
|
|---|
| 424 | /* It is not necessary to compare scan[2] and match[2] since they are
|
|---|
| 425 | * always equal when the other bytes match, given that the hash keys
|
|---|
| 426 | * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
|
|---|
| 427 | * strstart+3, +5, ... up to strstart+257. We check for insufficient
|
|---|
| 428 | * lookahead only every 4th comparison; the 128th check will be made
|
|---|
| 429 | * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
|
|---|
| 430 | * necessary to put more guard bytes at the end of the window, or
|
|---|
| 431 | * to check more often for insufficient lookahead.
|
|---|
| 432 | */
|
|---|
| 433 | scan++, match++;
|
|---|
| 434 | do {
|
|---|
| 435 | } while (*(ush*)(scan+=2) == *(ush*)(match+=2) &&
|
|---|
| 436 | *(ush*)(scan+=2) == *(ush*)(match+=2) &&
|
|---|
| 437 | *(ush*)(scan+=2) == *(ush*)(match+=2) &&
|
|---|
| 438 | *(ush*)(scan+=2) == *(ush*)(match+=2) &&
|
|---|
| 439 | scan < strend);
|
|---|
| 440 | /* The funny "do {}" generates better code on most compilers */
|
|---|
| 441 |
|
|---|
| 442 | /* Here, scan <= window+strstart+257 */
|
|---|
| 443 | Assert(scan <= window+(unsigned)(window_size-1), "wild scan");
|
|---|
| 444 | if (*scan == *match) scan++;
|
|---|
| 445 |
|
|---|
| 446 | len = (MAX_MATCH - 1) - (int)(strend-scan);
|
|---|
| 447 | scan = strend - (MAX_MATCH-1);
|
|---|
| 448 |
|
|---|
| 449 | #else /* UNALIGNED_OK */
|
|---|
| 450 |
|
|---|
| 451 | if (match[best_len] != scan_end ||
|
|---|
| 452 | match[best_len-1] != scan_end1 ||
|
|---|
| 453 | *match != *scan ||
|
|---|
| 454 | *++match != scan[1]) continue;
|
|---|
| 455 |
|
|---|
| 456 | /* The check at best_len-1 can be removed because it will be made
|
|---|
| 457 | * again later. (This heuristic is not always a win.)
|
|---|
| 458 | * It is not necessary to compare scan[2] and match[2] since they
|
|---|
| 459 | * are always equal when the other bytes match, given that
|
|---|
| 460 | * the hash keys are equal and that HASH_BITS >= 8.
|
|---|
| 461 | */
|
|---|
| 462 | scan += 2, match++;
|
|---|
| 463 |
|
|---|
| 464 | /* We check for insufficient lookahead only every 8th comparison;
|
|---|
| 465 | * the 256th check will be made at strstart+258.
|
|---|
| 466 | */
|
|---|
| 467 | do {
|
|---|
| 468 | } while (*++scan == *++match && *++scan == *++match &&
|
|---|
| 469 | *++scan == *++match && *++scan == *++match &&
|
|---|
| 470 | *++scan == *++match && *++scan == *++match &&
|
|---|
| 471 | *++scan == *++match && *++scan == *++match &&
|
|---|
| 472 | scan < strend);
|
|---|
| 473 |
|
|---|
| 474 | len = MAX_MATCH - (int)(strend - scan);
|
|---|
| 475 | scan = strend - MAX_MATCH;
|
|---|
| 476 |
|
|---|
| 477 | #endif /* UNALIGNED_OK */
|
|---|
| 478 |
|
|---|
| 479 | if (len > best_len) {
|
|---|
| 480 | match_start = cur_match;
|
|---|
| 481 | best_len = len;
|
|---|
| 482 | if (len >= nice_match) break;
|
|---|
| 483 | #ifdef UNALIGNED_OK
|
|---|
| 484 | scan_end = *(ush*)(scan+best_len-1);
|
|---|
| 485 | #else
|
|---|
| 486 | scan_end1 = scan[best_len-1];
|
|---|
| 487 | scan_end = scan[best_len];
|
|---|
| 488 | #endif
|
|---|
| 489 | }
|
|---|
| 490 | } while ((cur_match = prev[cur_match & WMASK]) > limit
|
|---|
| 491 | && --chain_length != 0);
|
|---|
| 492 |
|
|---|
| 493 | return best_len;
|
|---|
| 494 | }
|
|---|
| 495 | #endif /* ASMV */
|
|---|
| 496 |
|
|---|
| 497 | #ifdef DEBUG
|
|---|
| 498 | /* ===========================================================================
|
|---|
| 499 | * Check that the match at match_start is indeed a match.
|
|---|
| 500 | */
|
|---|
| 501 | local void check_match(start, match, length)
|
|---|
| 502 | IPos start, match;
|
|---|
| 503 | int length;
|
|---|
| 504 | {
|
|---|
| 505 | /* check that the match is indeed a match */
|
|---|
| 506 | if (memcmp((char*)window + match,
|
|---|
| 507 | (char*)window + start, length) != EQUAL) {
|
|---|
| 508 | fprintf(stderr,
|
|---|
| 509 | " start %d, match %d, length %d\n",
|
|---|
| 510 | start, match, length);
|
|---|
| 511 | gzip_error ("invalid match");
|
|---|
| 512 | }
|
|---|
| 513 | if (verbose > 1) {
|
|---|
| 514 | fprintf(stderr,"\\[%d,%d]", start-match, length);
|
|---|
| 515 | do { putc(window[start++], stderr); } while (--length != 0);
|
|---|
| 516 | }
|
|---|
| 517 | }
|
|---|
| 518 | #else
|
|---|
| 519 | # define check_match(start, match, length)
|
|---|
| 520 | #endif
|
|---|
| 521 |
|
|---|
| 522 | /* ===========================================================================
|
|---|
| 523 | * Fill the window when the lookahead becomes insufficient.
|
|---|
| 524 | * Updates strstart and lookahead, and sets eofile if end of input file.
|
|---|
| 525 | * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0
|
|---|
| 526 | * OUT assertions: at least one byte has been read, or eofile is set;
|
|---|
| 527 | * file reads are performed for at least two bytes (required for the
|
|---|
| 528 | * translate_eol option).
|
|---|
| 529 | */
|
|---|
| 530 | local void fill_window()
|
|---|
| 531 | {
|
|---|
| 532 | register unsigned n, m;
|
|---|
| 533 | unsigned more = (unsigned)(window_size - (ulg)lookahead - (ulg)strstart);
|
|---|
| 534 | /* Amount of free space at the end of the window. */
|
|---|
| 535 |
|
|---|
| 536 | /* If the window is almost full and there is insufficient lookahead,
|
|---|
| 537 | * move the upper half to the lower one to make room in the upper half.
|
|---|
| 538 | */
|
|---|
| 539 | if (more == (unsigned)EOF) {
|
|---|
| 540 | /* Very unlikely, but possible on 16 bit machine if strstart == 0
|
|---|
| 541 | * and lookahead == 1 (input done one byte at time)
|
|---|
| 542 | */
|
|---|
| 543 | more--;
|
|---|
| 544 | } else if (strstart >= WSIZE+MAX_DIST) {
|
|---|
| 545 | /* By the IN assertion, the window is not empty so we can't confuse
|
|---|
| 546 | * more == 0 with more == 64K on a 16 bit machine.
|
|---|
| 547 | */
|
|---|
| 548 | Assert(window_size == (ulg)2*WSIZE, "no sliding with BIG_MEM");
|
|---|
| 549 |
|
|---|
| 550 | memcpy((char*)window, (char*)window+WSIZE, (unsigned)WSIZE);
|
|---|
| 551 | match_start -= WSIZE;
|
|---|
| 552 | strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */
|
|---|
| 553 |
|
|---|
| 554 | block_start -= (long) WSIZE;
|
|---|
| 555 |
|
|---|
| 556 | for (n = 0; n < HASH_SIZE; n++) {
|
|---|
| 557 | m = head[n];
|
|---|
| 558 | head[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
|
|---|
| 559 | }
|
|---|
| 560 | for (n = 0; n < WSIZE; n++) {
|
|---|
| 561 | m = prev[n];
|
|---|
| 562 | prev[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
|
|---|
| 563 | /* If n is not on any hash chain, prev[n] is garbage but
|
|---|
| 564 | * its value will never be used.
|
|---|
| 565 | */
|
|---|
| 566 | }
|
|---|
| 567 | more += WSIZE;
|
|---|
| 568 | }
|
|---|
| 569 | /* At this point, more >= 2 */
|
|---|
| 570 | if (!eofile) {
|
|---|
| 571 | n = read_buf((char*)window+strstart+lookahead, more);
|
|---|
| 572 | if (n == 0 || n == (unsigned)EOF) {
|
|---|
| 573 | eofile = 1;
|
|---|
| 574 | } else {
|
|---|
| 575 | lookahead += n;
|
|---|
| 576 | }
|
|---|
| 577 | }
|
|---|
| 578 | }
|
|---|
| 579 |
|
|---|
| 580 | /* ===========================================================================
|
|---|
| 581 | * Flush the current block, with given end-of-file flag.
|
|---|
| 582 | * IN assertion: strstart is set to the end of the current match.
|
|---|
| 583 | */
|
|---|
| 584 | #define FLUSH_BLOCK(eof) \
|
|---|
| 585 | flush_block(block_start >= 0L ? (char*)&window[(unsigned)block_start] : \
|
|---|
| 586 | (char*)NULL, (long)strstart - block_start, (eof))
|
|---|
| 587 |
|
|---|
| 588 | /* ===========================================================================
|
|---|
| 589 | * Processes a new input file and return its compressed length. This
|
|---|
| 590 | * function does not perform lazy evaluationof matches and inserts
|
|---|
| 591 | * new strings in the dictionary only for unmatched strings or for short
|
|---|
| 592 | * matches. It is used only for the fast compression options.
|
|---|
| 593 | */
|
|---|
| 594 | local off_t deflate_fast()
|
|---|
| 595 | {
|
|---|
| 596 | IPos hash_head; /* head of the hash chain */
|
|---|
| 597 | int flush; /* set if current block must be flushed */
|
|---|
| 598 | unsigned match_length = 0; /* length of best match */
|
|---|
| 599 |
|
|---|
| 600 | prev_length = MIN_MATCH-1;
|
|---|
| 601 | while (lookahead != 0) {
|
|---|
| 602 | /* Insert the string window[strstart .. strstart+2] in the
|
|---|
| 603 | * dictionary, and set hash_head to the head of the hash chain:
|
|---|
| 604 | */
|
|---|
| 605 | INSERT_STRING(strstart, hash_head);
|
|---|
| 606 |
|
|---|
| 607 | /* Find the longest match, discarding those <= prev_length.
|
|---|
| 608 | * At this point we have always match_length < MIN_MATCH
|
|---|
| 609 | */
|
|---|
| 610 | if (hash_head != NIL && strstart - hash_head <= MAX_DIST
|
|---|
| 611 | && strstart <= window_size - MIN_LOOKAHEAD) {
|
|---|
| 612 | /* To simplify the code, we prevent matches with the string
|
|---|
| 613 | * of window index 0 (in particular we have to avoid a match
|
|---|
| 614 | * of the string with itself at the start of the input file).
|
|---|
| 615 | */
|
|---|
| 616 | match_length = longest_match (hash_head);
|
|---|
| 617 | /* longest_match() sets match_start */
|
|---|
| 618 | if (match_length > lookahead) match_length = lookahead;
|
|---|
| 619 | }
|
|---|
| 620 | if (match_length >= MIN_MATCH) {
|
|---|
| 621 | check_match(strstart, match_start, match_length);
|
|---|
| 622 |
|
|---|
| 623 | flush = ct_tally(strstart-match_start, match_length - MIN_MATCH);
|
|---|
| 624 |
|
|---|
| 625 | lookahead -= match_length;
|
|---|
| 626 |
|
|---|
| 627 | /* Insert new strings in the hash table only if the match length
|
|---|
| 628 | * is not too large. This saves time but degrades compression.
|
|---|
| 629 | */
|
|---|
| 630 | if (match_length <= max_insert_length) {
|
|---|
| 631 | match_length--; /* string at strstart already in hash table */
|
|---|
| 632 | do {
|
|---|
| 633 | strstart++;
|
|---|
| 634 | INSERT_STRING(strstart, hash_head);
|
|---|
| 635 | /* strstart never exceeds WSIZE-MAX_MATCH, so there are
|
|---|
| 636 | * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
|
|---|
| 637 | * these bytes are garbage, but it does not matter since
|
|---|
| 638 | * the next lookahead bytes will be emitted as literals.
|
|---|
| 639 | */
|
|---|
| 640 | } while (--match_length != 0);
|
|---|
| 641 | strstart++;
|
|---|
| 642 | } else {
|
|---|
| 643 | strstart += match_length;
|
|---|
| 644 | match_length = 0;
|
|---|
| 645 | ins_h = window[strstart];
|
|---|
| 646 | UPDATE_HASH(ins_h, window[strstart+1]);
|
|---|
| 647 | #if MIN_MATCH != 3
|
|---|
| 648 | Call UPDATE_HASH() MIN_MATCH-3 more times
|
|---|
| 649 | #endif
|
|---|
| 650 | }
|
|---|
| 651 | } else {
|
|---|
| 652 | /* No match, output a literal byte */
|
|---|
| 653 | Tracevv((stderr,"%c",window[strstart]));
|
|---|
| 654 | flush = ct_tally (0, window[strstart]);
|
|---|
| 655 | lookahead--;
|
|---|
| 656 | strstart++;
|
|---|
| 657 | }
|
|---|
| 658 | if (flush) FLUSH_BLOCK(0), block_start = strstart;
|
|---|
| 659 |
|
|---|
| 660 | /* Make sure that we always have enough lookahead, except
|
|---|
| 661 | * at the end of the input file. We need MAX_MATCH bytes
|
|---|
| 662 | * for the next match, plus MIN_MATCH bytes to insert the
|
|---|
| 663 | * string following the next match.
|
|---|
| 664 | */
|
|---|
| 665 | while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window();
|
|---|
| 666 |
|
|---|
| 667 | }
|
|---|
| 668 | return FLUSH_BLOCK(1); /* eof */
|
|---|
| 669 | }
|
|---|
| 670 |
|
|---|
| 671 | /* ===========================================================================
|
|---|
| 672 | * Same as above, but achieves better compression. We use a lazy
|
|---|
| 673 | * evaluation for matches: a match is finally adopted only if there is
|
|---|
| 674 | * no better match at the next window position.
|
|---|
| 675 | */
|
|---|
| 676 | off_t deflate()
|
|---|
| 677 | {
|
|---|
| 678 | IPos hash_head; /* head of hash chain */
|
|---|
| 679 | IPos prev_match; /* previous match */
|
|---|
| 680 | int flush; /* set if current block must be flushed */
|
|---|
| 681 | int match_available = 0; /* set if previous match exists */
|
|---|
| 682 | register unsigned match_length = MIN_MATCH-1; /* length of best match */
|
|---|
| 683 |
|
|---|
| 684 | if (compr_level <= 3) return deflate_fast(); /* optimized for speed */
|
|---|
| 685 |
|
|---|
| 686 | /* Process the input block. */
|
|---|
| 687 | while (lookahead != 0) {
|
|---|
| 688 | /* Insert the string window[strstart .. strstart+2] in the
|
|---|
| 689 | * dictionary, and set hash_head to the head of the hash chain:
|
|---|
| 690 | */
|
|---|
| 691 | INSERT_STRING(strstart, hash_head);
|
|---|
| 692 |
|
|---|
| 693 | /* Find the longest match, discarding those <= prev_length.
|
|---|
| 694 | */
|
|---|
| 695 | prev_length = match_length, prev_match = match_start;
|
|---|
| 696 | match_length = MIN_MATCH-1;
|
|---|
| 697 |
|
|---|
| 698 | if (hash_head != NIL && prev_length < max_lazy_match &&
|
|---|
| 699 | strstart - hash_head <= MAX_DIST &&
|
|---|
| 700 | strstart <= window_size - MIN_LOOKAHEAD) {
|
|---|
| 701 | /* To simplify the code, we prevent matches with the string
|
|---|
| 702 | * of window index 0 (in particular we have to avoid a match
|
|---|
| 703 | * of the string with itself at the start of the input file).
|
|---|
| 704 | */
|
|---|
| 705 | match_length = longest_match (hash_head);
|
|---|
| 706 | /* longest_match() sets match_start */
|
|---|
| 707 | if (match_length > lookahead) match_length = lookahead;
|
|---|
| 708 |
|
|---|
| 709 | /* Ignore a length 3 match if it is too distant: */
|
|---|
| 710 | if (match_length == MIN_MATCH && strstart-match_start > TOO_FAR){
|
|---|
| 711 | /* If prev_match is also MIN_MATCH, match_start is garbage
|
|---|
| 712 | * but we will ignore the current match anyway.
|
|---|
| 713 | */
|
|---|
| 714 | match_length--;
|
|---|
| 715 | }
|
|---|
| 716 | }
|
|---|
| 717 | /* If there was a match at the previous step and the current
|
|---|
| 718 | * match is not better, output the previous match:
|
|---|
| 719 | */
|
|---|
| 720 | if (prev_length >= MIN_MATCH && match_length <= prev_length) {
|
|---|
| 721 |
|
|---|
| 722 | check_match(strstart-1, prev_match, prev_length);
|
|---|
| 723 |
|
|---|
| 724 | flush = ct_tally(strstart-1-prev_match, prev_length - MIN_MATCH);
|
|---|
| 725 |
|
|---|
| 726 | /* Insert in hash table all strings up to the end of the match.
|
|---|
| 727 | * strstart-1 and strstart are already inserted.
|
|---|
| 728 | */
|
|---|
| 729 | lookahead -= prev_length-1;
|
|---|
| 730 | prev_length -= 2;
|
|---|
| 731 | do {
|
|---|
| 732 | strstart++;
|
|---|
| 733 | INSERT_STRING(strstart, hash_head);
|
|---|
| 734 | /* strstart never exceeds WSIZE-MAX_MATCH, so there are
|
|---|
| 735 | * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
|
|---|
| 736 | * these bytes are garbage, but it does not matter since the
|
|---|
| 737 | * next lookahead bytes will always be emitted as literals.
|
|---|
| 738 | */
|
|---|
| 739 | } while (--prev_length != 0);
|
|---|
| 740 | match_available = 0;
|
|---|
| 741 | match_length = MIN_MATCH-1;
|
|---|
| 742 | strstart++;
|
|---|
| 743 | if (flush) FLUSH_BLOCK(0), block_start = strstart;
|
|---|
| 744 |
|
|---|
| 745 | } else if (match_available) {
|
|---|
| 746 | /* If there was no match at the previous position, output a
|
|---|
| 747 | * single literal. If there was a match but the current match
|
|---|
| 748 | * is longer, truncate the previous match to a single literal.
|
|---|
| 749 | */
|
|---|
| 750 | Tracevv((stderr,"%c",window[strstart-1]));
|
|---|
| 751 | if (ct_tally (0, window[strstart-1])) {
|
|---|
| 752 | FLUSH_BLOCK(0), block_start = strstart;
|
|---|
| 753 | }
|
|---|
| 754 | strstart++;
|
|---|
| 755 | lookahead--;
|
|---|
| 756 | } else {
|
|---|
| 757 | /* There is no previous match to compare with, wait for
|
|---|
| 758 | * the next step to decide.
|
|---|
| 759 | */
|
|---|
| 760 | match_available = 1;
|
|---|
| 761 | strstart++;
|
|---|
| 762 | lookahead--;
|
|---|
| 763 | }
|
|---|
| 764 | Assert (strstart <= bytes_in && lookahead <= bytes_in, "a bit too far");
|
|---|
| 765 |
|
|---|
| 766 | /* Make sure that we always have enough lookahead, except
|
|---|
| 767 | * at the end of the input file. We need MAX_MATCH bytes
|
|---|
| 768 | * for the next match, plus MIN_MATCH bytes to insert the
|
|---|
| 769 | * string following the next match.
|
|---|
| 770 | */
|
|---|
| 771 | while (lookahead < MIN_LOOKAHEAD && !eofile) fill_window();
|
|---|
| 772 | }
|
|---|
| 773 | if (match_available) ct_tally (0, window[strstart-1]);
|
|---|
| 774 |
|
|---|
| 775 | return FLUSH_BLOCK(1); /* eof */
|
|---|
| 776 | }
|
|---|
