document mingw linker fix and close associated bug

[debian/gzip] / deflate.c

diff --git a/deflate.c b/deflate.c
index 2f55a7cc8b8fa5b7bb50cff8ee41d469e1a5afa3..951d7af4e895b2285d1617c05a4940c6b7b336b6 100644 (file)
--- a/deflate.c
+++ b/deflate.c
@@ -1,11 +1,11 @@
 /* deflate.c -- compress data using the deflation algorithm
 
 /* deflate.c -- compress data using the deflation algorithm
 

-   Copyright (C) 1999, 2006 Free Software Foundation, Inc.
+   Copyright (C) 1999, 2006, 2009-2018 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
    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 2, or (at your option)
+   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,
    any later version.
 
    This program is distributed in the hope that it will be useful,


@@ -80,10 +80,7 @@
 #include "tailor.h"
 #include "gzip.h"
 #include "lzw.h" /* just for consistency checking */
 #include "tailor.h"
 #include "gzip.h"
 #include "lzw.h" /* just for consistency checking */

-
-#ifdef RCSID
-static char rcsid[] = "$Id: deflate.c,v 1.5 2006/12/07 23:53:00 eggert Exp $";
-#endif
+#include "verify.h"

 
 /* ===========================================================================
  * Configuration parameters
 
 /* ===========================================================================
  * Configuration parameters


@@ -135,6 +132,14 @@ static char rcsid[] = "$Id: deflate.c,v 1.5 2006/12/07 23:53:00 eggert Exp $";
 #endif
 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
 
 #endif
 /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
 

+#ifndef RSYNC_WIN
+#  define RSYNC_WIN 4096
+#endif
+verify(RSYNC_WIN < 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.
  */
 /* ===========================================================================
  * Local data used by the "longest match" routines.
  */


@@ -165,7 +170,7 @@ typedef unsigned IPos;
 /* DECLARE(Pos, head, 1<<HASH_BITS); */
 /* Heads of the hash chains or NIL. */
 
 /* DECLARE(Pos, head, 1<<HASH_BITS); */
 /* Heads of the hash chains or NIL. */
 

-ulg window_size = (ulg)2*WSIZE;
+static ulg window_size = (ulg)2*WSIZE;

 /* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
  * input file length plus MIN_LOOKAHEAD.
  */
 /* window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
  * input file length plus MIN_LOOKAHEAD.
  */


@@ -184,7 +189,7 @@ local unsigned ins_h;  /* hash index of string to be inserted */
  *   H_SHIFT * MIN_MATCH >= HASH_BITS
  */
 
  *   H_SHIFT * MIN_MATCH >= HASH_BITS
  */
 

-unsigned int near prev_length;
+       unsigned int near prev_length;

 /* Length of the best match at previous step. Matches not greater than this
  * are discarded. This is used in the lazy match evaluation.
  */
 /* Length of the best match at previous step. Matches not greater than this
  * are discarded. This is used in the lazy match evaluation.
  */


@@ -194,7 +199,7 @@ unsigned int near prev_length;
 local int           eofile;        /* flag set at end of input file */
 local unsigned      lookahead;     /* number of valid bytes ahead in window */
 
 local int           eofile;        /* flag set at end of input file */
 local unsigned      lookahead;     /* number of valid bytes ahead in window */
 

-unsigned near max_chain_length;
+       unsigned max_chain_length;

 /* To speed up deflation, hash chains are never searched beyond this length.
  * A higher limit improves compression ratio but degrades the speed.
  */
 /* To speed up deflation, hash chains are never searched beyond this length.
  * A higher limit improves compression ratio but degrades the speed.
  */


@@ -213,9 +218,11 @@ local unsigned int max_lazy_match;
 local int compr_level;
 /* compression level (1..9) */
 
 local int compr_level;
 /* compression level (1..9) */
 

-unsigned near good_match;
+unsigned good_match;

 /* Use a faster search when the previous match is longer than this */
 
 /* 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
 
 /* 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


@@ -230,10 +237,17 @@ typedef struct config {
    ush max_chain;
 } config;
 
    ush max_chain;
 } config;
 

+#ifdef ASMV
+# define static_unless_ASMV
+#else
+# define static_unless_ASMV static
+#endif
+

 #ifdef  FULL_SEARCH
 # define nice_match MAX_MATCH
 #else
 #ifdef  FULL_SEARCH
 # define nice_match MAX_MATCH
 #else

-  int near nice_match; /* Stop searching when current match exceeds this */
+  /* Stop searching when current match exceeds this */
+  static_unless_ASMV int nice_match;

 #endif
 
 local config configuration_table[10] = {
 #endif
 
 local config configuration_table[10] = {


@@ -255,27 +269,24 @@ local config configuration_table[10] = {
  * meaning.
  */
 
  * meaning.
  */
 

-#define EQUAL 0
-/* result of memcmp for equal strings */
-

 /* ===========================================================================
  *  Prototypes for local functions.
  */
 /* ===========================================================================
  *  Prototypes for local functions.
  */

-local void fill_window   OF((void));
-local off_t deflate_fast OF((void));
+local void fill_window   (void);
+local off_t deflate_fast (void);

 
 

-      int  longest_match OF((IPos cur_match));

 #ifdef ASMV
 #ifdef ASMV

-      void match_init OF((void)); /* asm code initialization */
+      int  longest_match (IPos cur_match);
+      void match_init (void); /* asm code initialization */

 #endif
 
 #ifdef DEBUG
 #endif
 
 #ifdef DEBUG

-local  void check_match OF((IPos start, IPos match, int length));
+local  void check_match (IPos start, IPos match, int length);

 #endif
 
 /* ===========================================================================
  * Update a hash value with the given input byte
 #endif
 
 /* ===========================================================================
  * Update a hash value with the given input byte

- * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
+ * IN  assertion: all calls to UPDATE_HASH are made with consecutive

  *    input characters, so that a running hash key can be computed from the
  *    previous key instead of complete recalculation each time.
  */
  *    input characters, so that a running hash key can be computed from the
  *    previous key instead of complete recalculation each time.
  */


@@ -285,7 +296,7 @@ local  void check_match OF((IPos start, IPos match, int length));
  * Insert string s in the dictionary and set match_head to the previous head
  * of the hash chain (the most recent string with same hash key). Return
  * the previous length of the hash chain.
  * Insert string s in the dictionary and set match_head to the previous head
  * of the hash chain (the most recent string with same hash key). Return
  * the previous length of the hash chain.

- * IN  assertion: all calls to to INSERT_STRING are made with consecutive
+ * IN  assertion: all calls to INSERT_STRING are made with consecutive

  *    input characters and the first MIN_MATCH bytes of s are valid
  *    (except for the last MIN_MATCH-1 bytes of the input file).
  */
  *    input characters and the first MIN_MATCH bytes of s are valid
  *    (except for the last MIN_MATCH-1 bytes of the input file).
  */


@@ -307,13 +318,17 @@ void lm_init (pack_level, flags)
     compr_level = pack_level;
 
     /* Initialize the hash table. */
     compr_level = pack_level;
 
     /* Initialize the hash table. */

-#if defined(MAXSEG_64K) && HASH_BITS == 15
+#if defined MAXSEG_64K && HASH_BITS == 15

     for (j = 0;  j < HASH_SIZE; j++) head[j] = NIL;
 #else
     memzero((char*)head, HASH_SIZE*sizeof(*head));
 #endif
     /* prev will be initialized on the fly */
 
     for (j = 0;  j < HASH_SIZE; j++) head[j] = NIL;
 #else
     memzero((char*)head, HASH_SIZE*sizeof(*head));
 #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;
     /* Set the default configuration parameters:
      */
     max_lazy_match   = configuration_table[pack_level].max_lazy;


@@ -336,7 +351,7 @@ void lm_init (pack_level, flags)
 #endif
 
     lookahead = read_buf((char*)window,
 #endif
 
     lookahead = read_buf((char*)window,

-                        sizeof(int) <= 2 ? (unsigned)WSIZE : 2*WSIZE);
+                         sizeof(int) <= 2 ? (unsigned)WSIZE : 2*WSIZE);

 
     if (lookahead == 0 || lookahead == (unsigned)EOF) {
        eofile = 1, lookahead = 0;
 
     if (lookahead == 0 || lookahead == (unsigned)EOF) {
        eofile = 1, lookahead = 0;


@@ -368,8 +383,8 @@ void lm_init (pack_level, flags)
  * match.s. The code is functionally equivalent, so you can use the C version
  * if desired.
  */
  * match.s. The code is functionally equivalent, so you can use the C version
  * if desired.
  */

-int longest_match(cur_match)
-    IPos cur_match;                             /* current match */
+static int
+longest_match(IPos cur_match)

 {
     unsigned chain_length = max_chain_length;   /* max hash chain length */
     register uch *scan = window + strstart;     /* current string */
 {
     unsigned chain_length = max_chain_length;   /* max hash chain length */
     register uch *scan = window + strstart;     /* current string */


@@ -414,7 +429,7 @@ int longest_match(cur_match)
         /* Skip to next match if the match length cannot increase
          * or if the match length is less than 2:
          */
         /* Skip to next match if the match length cannot increase
          * or if the match length is less than 2:
          */

-#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
+#if defined UNALIGNED_OK && MAX_MATCH == 258

         /* This code assumes sizeof(unsigned short) == 2. Do not use
          * UNALIGNED_OK if your compiler uses a different size.
          */
         /* This code assumes sizeof(unsigned short) == 2. Do not use
          * UNALIGNED_OK if your compiler uses a different size.
          */


@@ -488,7 +503,7 @@ int longest_match(cur_match)
 #endif
         }
     } while ((cur_match = prev[cur_match & WMASK]) > limit
 #endif
         }
     } while ((cur_match = prev[cur_match & WMASK]) > limit

-            && --chain_length != 0);
+             && --chain_length != 0);

 
     return best_len;
 }
 
     return best_len;
 }


@@ -504,7 +519,7 @@ local void check_match(start, match, length)
 {
     /* check that the match is indeed a match */
     if (memcmp((char*)window + match,
 {
     /* 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);
         fprintf(stderr,
             " start %d, match %d, length %d\n",
             start, match, length);


@@ -550,6 +565,8 @@ local void fill_window()
         memcpy((char*)window, (char*)window+WSIZE, (unsigned)WSIZE);
         match_start -= WSIZE;
         strstart    -= WSIZE; /* we now have strstart >= MAX_DIST: */
         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;
 
 
         block_start -= (long) WSIZE;
 


@@ -571,19 +588,55 @@ local void fill_window()
         n = read_buf((char*)window+strstart+lookahead, more);
         if (n == 0 || n == (unsigned)EOF) {
             eofile = 1;
         n = read_buf((char*)window+strstart+lookahead, more);
         if (n == 0 || n == (unsigned)EOF) {
             eofile = 1;

+            /* Don't let garbage pollute the dictionary.  */
+            memzero (window + strstart + lookahead, MIN_MATCH - 1);

         } else {
             lookahead += n;
         }
     }
 }
 
         } else {
             lookahead += n;
         }
     }
 }
 

+/* With an initial offset of START, advance rsync's rolling checksum
+   by NUM bytes.  */
+local void rsync_roll(unsigned int start, unsigned int 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] : \
 /* ===========================================================================
  * 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, (eof))
+                (char*)NULL, (long)strstart - block_start, flush-1, (eof))

 
 /* ===========================================================================
  * Processes a new input file and return its compressed length. This
 
 /* ===========================================================================
  * Processes a new input file and return its compressed length. This


@@ -594,7 +647,7 @@ local void fill_window()
 local off_t deflate_fast()
 {
     IPos hash_head; /* head of the hash chain */
 local off_t deflate_fast()
 {
     IPos hash_head; /* head of the hash chain */

-    int flush;      /* set if current block must be flushed */
+    int flush = 0;  /* set if current block must be flushed, 2=>and padded  */

     unsigned match_length = 0;  /* length of best match */
 
     prev_length = MIN_MATCH-1;
     unsigned match_length = 0;  /* length of best match */
 
     prev_length = MIN_MATCH-1;


@@ -608,7 +661,7 @@ local off_t deflate_fast()
          * At this point we have always match_length < MIN_MATCH
          */
         if (hash_head != NIL && strstart - hash_head <= MAX_DIST
          * At this point we have always match_length < MIN_MATCH
          */
         if (hash_head != NIL && 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).
             /* 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).


@@ -624,7 +677,8 @@ local off_t deflate_fast()
 
             lookahead -= match_length;
 
 
             lookahead -= match_length;
 

-           /* Insert new strings in the hash table only if the 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.
              */
             if (match_length <= max_insert_length) {
              * is not too large. This saves time but degrades compression.
              */
             if (match_length <= max_insert_length) {


@@ -638,12 +692,12 @@ local off_t deflate_fast()
                      * the next lookahead bytes will be emitted as literals.
                      */
                 } while (--match_length != 0);
                      * the next lookahead bytes will be emitted as literals.
                      */
                 } while (--match_length != 0);

-               strstart++;
+                strstart++;

             } else {
             } else {

-               strstart += match_length;
-               match_length = 0;
-               ins_h = window[strstart];
-               UPDATE_HASH(ins_h, window[strstart+1]);
+                strstart += match_length;
+                match_length = 0;
+                ins_h = window[strstart];
+                UPDATE_HASH(ins_h, window[strstart+1]);

 #if MIN_MATCH != 3
                 Call UPDATE_HASH() MIN_MATCH-3 more times
 #endif
 #if MIN_MATCH != 3
                 Call UPDATE_HASH() MIN_MATCH-3 more times
 #endif


@@ -652,8 +706,13 @@ local off_t deflate_fast()
             /* No match, output a literal byte */
             Tracevv((stderr,"%c",window[strstart]));
             flush = ct_tally (0, window[strstart]);
             /* No match, output a literal byte */
             Tracevv((stderr,"%c",window[strstart]));
             flush = ct_tally (0, window[strstart]);

+            RSYNC_ROLL(strstart, 1);

             lookahead--;
             lookahead--;

-           strstart++;
+            strstart++;
+        }
+        if (rsync && strstart > rsync_chunk_end) {
+            rsync_chunk_end = 0xFFFFFFFFUL;
+            flush = 2;

         }
         if (flush) FLUSH_BLOCK(0), block_start = strstart;
 
         }
         if (flush) FLUSH_BLOCK(0), block_start = strstart;
 


@@ -677,7 +736,7 @@ off_t deflate()
 {
     IPos hash_head;          /* head of hash chain */
     IPos prev_match;         /* previous match */
 {
     IPos hash_head;          /* head of hash chain */
     IPos prev_match;         /* previous match */

-    int flush;               /* set if current block must be flushed */
+    int flush = 0;           /* set if current block must be flushed */

     int match_available = 0; /* set if previous match exists */
     register unsigned match_length = MIN_MATCH-1; /* length of best match */
 
     int match_available = 0; /* set if previous match exists */
     register unsigned match_length = MIN_MATCH-1; /* length of best match */
 


@@ -728,6 +787,7 @@ off_t deflate()
              */
             lookahead -= prev_length-1;
             prev_length -= 2;
              */
             lookahead -= prev_length-1;
             prev_length -= 2;

+            RSYNC_ROLL(strstart, prev_length+1);

             do {
                 strstart++;
                 INSERT_STRING(strstart, hash_head);
             do {
                 strstart++;
                 INSERT_STRING(strstart, hash_head);


@@ -740,24 +800,40 @@ off_t deflate()
             match_available = 0;
             match_length = MIN_MATCH-1;
             strstart++;
             match_available = 0;
             match_length = MIN_MATCH-1;
             strstart++;

-            if (flush) FLUSH_BLOCK(0), block_start = 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]));
         } 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]));

-            if (ct_tally (0, window[strstart-1])) {
-                FLUSH_BLOCK(0), block_start = strstart;
+            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);

             strstart++;
             lookahead--;
         } else {
             /* There is no previous match to compare with, wait for
              * the next step to decide.
              */
             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;
             match_available = 1;

+            RSYNC_ROLL(strstart, 1);

             strstart++;
             lookahead--;
         }
             strstart++;
             lookahead--;
         }