/* deflate.c -- compress data using the deflation algorithm
- * Copyright (C) 1992-1993 Jean-loup Gailly
- * This is free software; you can redistribute it and/or modify it under the
- * terms of the GNU General Public License, see the file COPYING.
- */
+
+ Copyright (C) 1999, 2006, 2009-2010 Free Software Foundation, Inc.
+ Copyright (C) 1992-1993 Jean-loup Gailly
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3, or (at your option)
+ any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software Foundation,
+ Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
/*
* PURPOSE
#include "gzip.h"
#include "lzw.h" /* just for consistency checking */
-#ifdef RCSID
-static char rcsid[] = "$Id: deflate.c,v 0.15 1993/06/24 10:53:53 jloup Exp $";
-#endif
-
/* ===========================================================================
* Configuration parameters
*/
#endif
/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
-#ifndef RSYNC_WIN
-# define RSYNC_WIN 4096
-#endif
-/* Size of rsync window, must be < MAX_DIST */
-
-#define RSYNC_SUM_MATCH(sum) ((sum) % RSYNC_WIN == 0)
-/* Whether window sum matches magic value */
-
/* ===========================================================================
* Local data used by the "longest match" routines.
*/
unsigned near good_match;
/* Use a faster search when the previous match is longer than this */
-local ulg rsync_sum; /* rolling sum of rsync window */
-local ulg rsync_chunk_end; /* next rsync sequence point */
/* Values for max_lazy_match, good_match and max_chain_length, depending on
* the desired pack level (0..9). The values given below have been tuned to
* meaning.
*/
-#define EQUAL 0
-/* result of memcmp for equal strings */
-
/* ===========================================================================
* Prototypes for local functions.
*/
{
register unsigned j;
- if (pack_level < 1 || pack_level > 9) error("bad pack level");
+ if (pack_level < 1 || pack_level > 9) gzip_error ("bad pack level");
compr_level = pack_level;
/* Initialize the hash table. */
#endif
/* prev will be initialized on the fly */
- /* rsync params */
- rsync_chunk_end = 0xFFFFFFFFUL;
- rsync_sum = 0;
-
/* Set the default configuration parameters:
*/
max_lazy_match = configuration_table[pack_level].max_lazy;
{
/* check that the match is indeed a match */
if (memcmp((char*)window + match,
- (char*)window + start, length) != EQUAL) {
+ (char*)window + start, length) != 0) {
fprintf(stderr,
" start %d, match %d, length %d\n",
start, match, length);
- error("invalid match");
+ gzip_error ("invalid match");
}
if (verbose > 1) {
fprintf(stderr,"\\[%d,%d]", start-match, length);
memcpy((char*)window, (char*)window+WSIZE, (unsigned)WSIZE);
match_start -= WSIZE;
strstart -= WSIZE; /* we now have strstart >= MAX_DIST: */
- if (rsync_chunk_end != 0xFFFFFFFFUL)
- rsync_chunk_end -= WSIZE;
block_start -= (long) WSIZE;
}
}
-local void rsync_roll(start, num)
- unsigned start;
- unsigned num;
-{
- unsigned i;
-
- if (start < RSYNC_WIN) {
- /* before window fills. */
- for (i = start; i < RSYNC_WIN; i++) {
- if (i == start + num) return;
- rsync_sum += (ulg)window[i];
- }
- num -= (RSYNC_WIN - start);
- start = RSYNC_WIN;
- }
-
- /* buffer after window full */
- for (i = start; i < start+num; i++) {
- /* New character in */
- rsync_sum += (ulg)window[i];
- /* Old character out */
- rsync_sum -= (ulg)window[i - RSYNC_WIN];
- if (rsync_chunk_end == 0xFFFFFFFFUL && RSYNC_SUM_MATCH(rsync_sum))
- rsync_chunk_end = i;
- }
-}
-
-/* ===========================================================================
- * Set rsync_chunk_end if window sum matches magic value.
- */
-#define RSYNC_ROLL(s, n) \
- do { if (rsync) rsync_roll((s), (n)); } while(0)
-
/* ===========================================================================
* Flush the current block, with given end-of-file flag.
* IN assertion: strstart is set to the end of the current match.
*/
#define FLUSH_BLOCK(eof) \
flush_block(block_start >= 0L ? (char*)&window[(unsigned)block_start] : \
- (char*)NULL, (long)strstart - block_start, flush-1, (eof))
+ (char*)NULL, (long)strstart - block_start, (eof))
/* ===========================================================================
* Processes a new input file and return its compressed length. This
local off_t deflate_fast()
{
IPos hash_head; /* head of the hash chain */
- int flush; /* set if current block must be flushed, 2=>and padded */
+ int flush; /* set if current block must be flushed */
unsigned match_length = 0; /* length of best match */
prev_length = MIN_MATCH-1;
/* Find the longest match, discarding those <= prev_length.
* At this point we have always match_length < MIN_MATCH
*/
- if (hash_head != NIL && strstart - hash_head <= MAX_DIST &&
- strstart <= window_size - MIN_LOOKAHEAD) {
+ if (hash_head != NIL && strstart - hash_head <= MAX_DIST
+ && strstart <= window_size - MIN_LOOKAHEAD) {
/* To simplify the code, we prevent matches with the string
* of window index 0 (in particular we have to avoid a match
* of the string with itself at the start of the input file).
lookahead -= match_length;
- RSYNC_ROLL(strstart, match_length);
/* Insert new strings in the hash table only if the match length
* is not too large. This saves time but degrades compression.
*/
* the next lookahead bytes will be emitted as literals.
*/
} while (--match_length != 0);
- strstart++;
+ strstart++;
} else {
strstart += match_length;
match_length = 0;
/* No match, output a literal byte */
Tracevv((stderr,"%c",window[strstart]));
flush = ct_tally (0, window[strstart]);
- RSYNC_ROLL(strstart, 1);
lookahead--;
- strstart++;
+ strstart++;
}
- if (rsync && strstart > rsync_chunk_end) {
- rsync_chunk_end = 0xFFFFFFFFUL;
- flush = 2;
- }
if (flush) FLUSH_BLOCK(0), block_start = strstart;
/* Make sure that we always have enough lookahead, except
if (hash_head != NIL && prev_length < max_lazy_match &&
strstart - hash_head <= MAX_DIST &&
- strstart <= window_size - MIN_LOOKAHEAD) {
+ strstart <= window_size - MIN_LOOKAHEAD) {
/* To simplify the code, we prevent matches with the string
* of window index 0 (in particular we have to avoid a match
* of the string with itself at the start of the input file).
*/
lookahead -= prev_length-1;
prev_length -= 2;
- RSYNC_ROLL(strstart, prev_length+1);
do {
strstart++;
INSERT_STRING(strstart, hash_head);
match_available = 0;
match_length = MIN_MATCH-1;
strstart++;
-
- if (rsync && strstart > rsync_chunk_end) {
- rsync_chunk_end = 0xFFFFFFFFUL;
- flush = 2;
- }
if (flush) FLUSH_BLOCK(0), block_start = strstart;
+
} else if (match_available) {
/* If there was no match at the previous position, output a
* single literal. If there was a match but the current match
* is longer, truncate the previous match to a single literal.
*/
Tracevv((stderr,"%c",window[strstart-1]));
- flush = ct_tally (0, window[strstart-1]);
- if (rsync && strstart > rsync_chunk_end) {
- rsync_chunk_end = 0xFFFFFFFFUL;
- flush = 2;
- }
- if (flush) FLUSH_BLOCK(0), block_start = strstart;
- RSYNC_ROLL(strstart, 1);
+ if (ct_tally (0, window[strstart-1])) {
+ FLUSH_BLOCK(0), block_start = strstart;
+ }
strstart++;
lookahead--;
} else {
/* There is no previous match to compare with, wait for
* the next step to decide.
*/
- if (rsync && strstart > rsync_chunk_end) {
- /* Reset huffman tree */
- rsync_chunk_end = 0xFFFFFFFFUL;
- flush = 2;
- FLUSH_BLOCK(0), block_start = strstart;
- }
match_available = 1;
- RSYNC_ROLL(strstart, 1);
strstart++;
lookahead--;
}