fb6647379367290be57a64e3082a633c715e35b7
[rsync-patches.git] / gzip-rsyncable-checksum.diff
1 NOTE: this patch is for _gzip_!
2
3 Kevin Day's version of the gzip-rsyncable patch that uses the rsync
4 checksum algorithm.
5
6 --- gzip-1.2.2/deflate.c        2004-09-15 10:28:14.000000000 -0700
7 +++ rsyncable/deflate.c 2005-02-17 14:37:14.660957200 -0700
8 @@ -98,6 +98,10 @@
9                              int length));
10  #endif
11  
12 +local void rsync_roll(deflate_state *s, unsigned start, unsigned num);
13 +local void rsync_roll_noop(deflate_state *s, unsigned start, unsigned num);
14 +local void rsync_roll2(deflate_state *s, unsigned start, unsigned num);
15 +
16  /* ===========================================================================
17   * Local data
18   */
19 @@ -115,6 +119,39 @@
20   * See deflate.c for comments about the MIN_MATCH+1.
21   */
22  
23 +
24 +
25 +/* 
26 +       Valid values for RSYNC_DEFAULT_CHECKSUM_TYPE are:
27 +
28 +       Z_RSYNCABLE_OFF
29 +       Z_RSYNCABLE_SIMPLESUM
30 +       Z_RSYNCABLE_RSSUM
31 +*/
32 +
33 +#ifndef RSYNC_DEFAULT_CHECKSUM_TYPE
34 +#      define RSYNC_DEFAULT_CHECKSUM_TYPE Z_RSYNCABLE_RSSUM
35 +#endif
36 +
37 +#ifndef RSYNC_DEFAULT_WINDOW_SIZE
38 +#      define RSYNC_DEFAULT_WINDOW_SIZE 30
39 +#endif
40 +
41 +#ifndef RSYNC_DEFAULT_RESET_BLOCK_SIZE
42 +#      define RSYNC_DEFAULT_RESET_BLOCK_SIZE 4096 
43 +#endif
44 +
45 +#ifndef RSYNC_RESET_MAGIC_VALUE
46 +#      define RSYNC_RESET_MAGIC_VALUE 0
47 +#endif
48 +
49 +#define RSYNC_SUM_MATCH(s) ((s)->rsync_sum % (s)->rsync_reset_block_size == RSYNC_RESET_MAGIC_VALUE)
50 +/* Whether window sum matches magic value */
51 +
52 +/* Global rsync mode control variable */
53 +int zlib_rsync = 1 ;
54 +
55 +
56  /* Values for max_lazy_match, good_match and max_chain_length, depending on
57   * the desired pack level (0..9). The values given below have been tuned to
58   * exclude worst case performance for pathological files. Better values may be
59 @@ -212,6 +249,36 @@
60      /* To do: ignore strm->next_in if we use it as window */
61  }
62  
63 +int ZEXPORT deflateSetRsyncParameters_(strm, checksum_type, window_size, reset_block_size)
64 +    z_streamp strm;
65 +    int  checksum_type;
66 +       ulg window_size;
67 +       ulg reset_block_size;
68 +{
69 +       deflate_state *s = strm->state;
70 +
71 +       switch(checksum_type){
72 +               case Z_RSYNCABLE_SIMPLESUM: 
73 +                       s->rsync_rollfunction = rsync_roll; 
74 +                       break;
75 +               case Z_RSYNCABLE_RSSUM: 
76 +                       s->rsync_rollfunction = rsync_roll2; 
77 +                       break;
78 +               default: 
79 +                       s->rsync_rollfunction = rsync_roll_noop;
80 +       }
81 +
82 +       s->rsync_window_size = window_size != 0 ? window_size : RSYNC_DEFAULT_WINDOW_SIZE;
83 +       s->rsync_reset_block_size = reset_block_size != 0 ? reset_block_size : s->rsync_window_size;
84 +
85 +    s->rsync_chunk_end = 0xFFFFFFFFUL;
86 +    s->rsync_sum = 0;
87 +       s->rsync_s1 = 0;
88 +       s->rsync_s2 = 0;
89 +
90 +       return Z_OK;
91 +}
92 +
93  /* ========================================================================= */
94  int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
95                    version, stream_size)
96 @@ -307,9 +374,13 @@
97      s->strategy = strategy;
98      s->method = (Byte)method;
99  
100 +       deflateSetRsyncParameters_(strm, RSYNC_DEFAULT_CHECKSUM_TYPE, RSYNC_DEFAULT_WINDOW_SIZE, RSYNC_DEFAULT_RESET_BLOCK_SIZE);
101 +
102      return deflateReset(strm);
103  }
104  
105 +
106 +
107  /* ========================================================================= */
108  int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
109      z_streamp strm;
110 @@ -841,6 +912,13 @@
111  #ifdef ASMV
112      match_init(); /* initialize the asm code */
113  #endif
114 +
115 +    /* rsync params */
116 +    s->rsync_chunk_end = 0xFFFFFFFFUL;
117 +    s->rsync_sum = 0;
118 +       s->rsync_s1 = 0;
119 +       s->rsync_s2 = 0;
120 +
121  }
122  
123  #ifndef FASTEST
124 @@ -1123,6 +1201,8 @@
125              zmemcpy(s->window, s->window+wsize, (unsigned)wsize);
126              s->match_start -= wsize;
127              s->strstart    -= wsize; /* we now have strstart >= MAX_DIST */
128 +            if (s->rsync_chunk_end != 0xFFFFFFFFUL)
129 +                s->rsync_chunk_end -= wsize;
130              s->block_start -= (long) wsize;
131  
132              /* Slide the hash table (could be avoided with 32 bit values
133 @@ -1184,15 +1264,98 @@
134      } while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
135  }
136  
137 +local void rsync_roll(s, start, num)
138 +    deflate_state *s;
139 +    unsigned start;
140 +    unsigned num;
141 +{
142 +    unsigned i;
143 +
144 +    if (start < s->rsync_window_size) {
145 +       /* before window fills. */
146 +       for (i = start; i < s->rsync_window_size; i++) {
147 +           if (i == start + num) return;
148 +           s->rsync_sum += (ulg)s->window[i];
149 +       }
150 +       num -= (s->rsync_window_size - start);
151 +       start = s->rsync_window_size;
152 +    }
153 +
154 +    /* buffer after window full */
155 +    for (i = start; i < start+num; i++) {
156 +       /* New character in */
157 +       s->rsync_sum += (ulg)s->window[i];
158 +       /* Old character out */
159 +       s->rsync_sum -= (ulg)s->window[i - s->rsync_window_size];
160 +       if (s->rsync_chunk_end == 0xFFFFFFFFUL
161 +            && RSYNC_SUM_MATCH(s))
162 +           s->rsync_chunk_end = i;
163 +    }
164 +}
165 +
166 +local void rsync_roll_noop(s, start, num)
167 +    deflate_state *s;
168 +    unsigned start;
169 +    unsigned num;
170 +{
171 +}
172 +
173 +/*
174 + Implements the 2 part rsync checksum, instead of a simple summation checksum.
175 +*/
176 +local void rsync_roll2(deflate_state *s, unsigned start, unsigned num)
177 +{
178 +    unsigned i;
179 +
180 +    if (start < s->rsync_window_size) {
181 +               /* before window fills. */
182 +               for (i = start; i < s->rsync_window_size; i++) {
183 +                       if (i == start + num) return;
184 +                       s->rsync_s1 = (s->rsync_s1 + (ulg)s->window[i]) & 0xffff;
185 +                       s->rsync_s2 = (s->rsync_s2 + s->rsync_s1) & 0xffff;
186 +               }
187 +               num -= (s->rsync_window_size - start);
188 +               start = s->rsync_window_size;
189 +    }
190 +
191 +    /* buffer after window full */
192 +    for (i = start; i < start+num; i++) {
193 +               /* Old character out */
194 +
195 +               s->rsync_s1 = (s->rsync_s1 - (ulg)s->window[i - s->rsync_window_size]) & 0xffff;
196 +               s->rsync_s2 = (s->rsync_s2 - s->rsync_window_size * (ulg)s->window[i - s->rsync_window_size]) & 0xffff;
197 +
198 +               /* New character in */
199 +               s->rsync_s1 = (s->rsync_s1 + (ulg)s->window[i]) & 0xffff;
200 +               s->rsync_s2 = (s->rsync_s2 + s->rsync_s1) & 0xffff;
201 +
202 +               // add the two together for the match calculation
203 +               s->rsync_sum = s->rsync_s1 + s->rsync_s2;
204 +
205 +
206 +               if (s->rsync_chunk_end == 0xFFFFFFFFUL
207 +                       && RSYNC_SUM_MATCH(s)){
208 +                       s->rsync_chunk_end = i;
209 +               }
210 +    }
211 +}
212 +
213 +/* ===========================================================================
214 + * Set rsync_chunk_end if window sum matches magic value.
215 + */
216 +#define RSYNC_ROLL(s, start, num) \
217 +   do { if (zlib_rsync) (s)->rsync_rollfunction((s), (start), (num)); } while(0)
218 +
219  /* ===========================================================================
220   * Flush the current block, with given end-of-file flag.
221   * IN assertion: strstart is set to the end of the current match.
222   */
223 -#define FLUSH_BLOCK_ONLY(s, eof) { \
224 +#define FLUSH_BLOCK_ONLY(s, eof, pad) { \
225     _tr_flush_block(s, (s->block_start >= 0L ? \
226                     (charf *)&s->window[(unsigned)s->block_start] : \
227                     (charf *)Z_NULL), \
228                  (ulg)((long)s->strstart - s->block_start), \
229 +                (pad), \
230                  (eof)); \
231     s->block_start = s->strstart; \
232     flush_pending(s->strm); \
233 @@ -1200,8 +1363,8 @@
234  }
235  
236  /* Same but force premature exit if necessary. */
237 -#define FLUSH_BLOCK(s, eof) { \
238 -   FLUSH_BLOCK_ONLY(s, eof); \
239 +#define FLUSH_BLOCK(s, eof, pad) { \
240 +   FLUSH_BLOCK_ONLY(s, eof, pad); \
241     if (s->strm->avail_out == 0) return (eof) ? finish_started : need_more; \
242  }
243  
244 @@ -1252,16 +1415,16 @@
245              /* strstart == 0 is possible when wraparound on 16-bit machine */
246              s->lookahead = (uInt)(s->strstart - max_start);
247              s->strstart = (uInt)max_start;
248 -            FLUSH_BLOCK(s, 0);
249 +            FLUSH_BLOCK(s, 0, 0);
250          }
251          /* Flush if we may have to slide, otherwise block_start may become
252           * negative and the data will be gone:
253           */
254          if (s->strstart - (uInt)s->block_start >= MAX_DIST(s)) {
255 -            FLUSH_BLOCK(s, 0);
256 +            FLUSH_BLOCK(s, 0, 0);
257          }
258      }
259 -    FLUSH_BLOCK(s, flush == Z_FINISH);
260 +    FLUSH_BLOCK(s, flush == Z_FINISH, 0);
261      return flush == Z_FINISH ? finish_done : block_done;
262  }
263  
264 @@ -1330,6 +1493,7 @@
265  
266              s->lookahead -= s->match_length;
267  
268 +            RSYNC_ROLL(s, s->strstart, s->match_length);
269              /* Insert new strings in the hash table only if the match length
270               * is not too large. This saves time but degrades compression.
271               */
272 @@ -1363,12 +1527,17 @@
273              /* No match, output a literal byte */
274              Tracevv((stderr,"%c", s->window[s->strstart]));
275              _tr_tally_lit (s, s->window[s->strstart], bflush);
276 +            RSYNC_ROLL(s, s->strstart, 1);
277              s->lookahead--;
278              s->strstart++;
279          }
280 -        if (bflush) FLUSH_BLOCK(s, 0);
281 +       if (zlib_rsync && s->strstart > s->rsync_chunk_end) {
282 +           s->rsync_chunk_end = 0xFFFFFFFFUL;
283 +           bflush = 2;
284 +       }
285 +        if (bflush) FLUSH_BLOCK(s, 0, bflush-1);
286      }
287 -    FLUSH_BLOCK(s, flush == Z_FINISH);
288 +    FLUSH_BLOCK(s, flush == Z_FINISH, bflush-1);
289      return flush == Z_FINISH ? finish_done : block_done;
290  }
291  
292 @@ -1457,6 +1626,7 @@
293               */
294              s->lookahead -= s->prev_length-1;
295              s->prev_length -= 2;
296 +            RSYNC_ROLL(s, s->strstart, s->prev_length+1);
297              do {
298                  if (++s->strstart <= max_insert) {
299                      INSERT_STRING(s, s->strstart, hash_head);
300 @@ -1466,7 +1636,11 @@
301              s->match_length = MIN_MATCH-1;
302              s->strstart++;
303  
304 -            if (bflush) FLUSH_BLOCK(s, 0);
305 +            if (zlib_rsync && s->strstart > s->rsync_chunk_end) {
306 +                s->rsync_chunk_end = 0xFFFFFFFFUL;
307 +                bflush = 2;
308 +            } 
309 +            if (bflush) FLUSH_BLOCK(s, 0, bflush-1);
310  
311          } else if (s->match_available) {
312              /* If there was no match at the previous position, output a
313 @@ -1475,9 +1649,14 @@
314               */
315              Tracevv((stderr,"%c", s->window[s->strstart-1]));
316              _tr_tally_lit(s, s->window[s->strstart-1], bflush);
317 +            if (zlib_rsync && s->strstart > s->rsync_chunk_end) {
318 +                s->rsync_chunk_end = 0xFFFFFFFFUL;
319 +               bflush = 2;
320 +            } 
321              if (bflush) {
322 -                FLUSH_BLOCK_ONLY(s, 0);
323 +                FLUSH_BLOCK_ONLY(s, 0, bflush-1);
324              }
325 +            RSYNC_ROLL(s, s->strstart, 1);
326              s->strstart++;
327              s->lookahead--;
328              if (s->strm->avail_out == 0) return need_more;
329 @@ -1485,7 +1664,14 @@
330              /* There is no previous match to compare with, wait for
331               * the next step to decide.
332               */
333 +            if (zlib_rsync && s->strstart > s->rsync_chunk_end) {
334 +                /* Reset huffman tree */
335 +                s->rsync_chunk_end = 0xFFFFFFFFUL;
336 +                bflush = 2;
337 +                FLUSH_BLOCK(s, 0, bflush-1);
338 +            } 
339              s->match_available = 1;
340 +            RSYNC_ROLL(s, s->strstart, 1);
341              s->strstart++;
342              s->lookahead--;
343          }
344 @@ -1496,7 +1682,7 @@
345          _tr_tally_lit(s, s->window[s->strstart-1], bflush);
346          s->match_available = 0;
347      }
348 -    FLUSH_BLOCK(s, flush == Z_FINISH);
349 +    FLUSH_BLOCK(s, flush == Z_FINISH, bflush-1);
350      return flush == Z_FINISH ? finish_done : block_done;
351  }
352  #endif /* FASTEST */
353 --- gzip-1.2.2/deflate.h        2004-02-24 07:38:44.000000000 -0700
354 +++ rsyncable/deflate.h 2005-02-17 13:46:12.056551200 -0700
355 @@ -254,6 +254,17 @@
356       * are always zero.
357       */
358  
359 +    ulg rsync_sum;      /* rolling sum of rsync window */
360 +    ulg rsync_chunk_end; /* next rsync sequence point */
361 +       ulg rsync_window_size; /* the number of bytes used in computing the rolling checksum */
362 +       ulg rsync_reset_block_size; /* the compressed stream will be reset approximately every 'rsync_reset_block_size' bytes */
363 +       ulg rsync_s1; /* part 1 of the checksum for use with checksum type Z_RSYNCABLE_RSSUM*/
364 +       ulg rsync_s2; /* part 2 of the checksum for use with checksum type Z_RSYNCABLE_RSSUM*/
365 +
366 +       /* the function that should be called for performing the rsyncable checksum roll */
367 +       void (*rsync_rollfunction)(struct internal_state*s , unsigned start, unsigned num);
368 +
369 +
370  } FAR deflate_state;
371  
372  /* Output a byte on the stream.
373 @@ -276,7 +287,7 @@
374  void _tr_init         OF((deflate_state *s));
375  int  _tr_tally        OF((deflate_state *s, unsigned dist, unsigned lc));
376  void _tr_flush_block  OF((deflate_state *s, charf *buf, ulg stored_len,
377 -                          int eof));
378 +                          int pad, int eof));
379  void _tr_align        OF((deflate_state *s));
380  void _tr_stored_block OF((deflate_state *s, charf *buf, ulg stored_len,
381                            int eof));
382 --- gzip-1.2.2/minigzip.c       2003-11-04 18:19:26.000000000 -0700
383 +++ rsyncable/minigzip.c        2005-02-17 13:11:35.472851600 -0700
384 @@ -215,7 +215,7 @@
385      }
386      gz_compress(in, out);
387  
388 -    unlink(file);
389 +    //unlink(file);
390  }
391  
392  
393 @@ -236,7 +236,10 @@
394      if (len > SUFFIX_LEN && strcmp(file+len-SUFFIX_LEN, GZ_SUFFIX) == 0) {
395          infile = file;
396          outfile = buf;
397 -        outfile[len-3] = '\0';
398 +        outfile[len-3] = '.';
399 +        outfile[len-2] = 'u';
400 +        outfile[len-1] = 'z';
401 +        outfile[len-0] = '\0';
402      } else {
403          outfile = file;
404          infile = buf;
405 @@ -255,7 +258,7 @@
406  
407      gz_uncompress(in, out);
408  
409 -    unlink(infile);
410 +    //unlink(infile);
411  }
412  
413  
414 --- gzip-1.2.2/trees.c  2004-02-24 07:36:38.000000000 -0700
415 +++ rsyncable/trees.c   2005-02-17 13:09:38.768435100 -0700
416 @@ -918,10 +918,11 @@
417   * Determine the best encoding for the current block: dynamic trees, static
418   * trees or store, and output the encoded block to the zip file.
419   */
420 -void _tr_flush_block(s, buf, stored_len, eof)
421 +void _tr_flush_block(s, buf, stored_len, pad, eof)
422      deflate_state *s;
423      charf *buf;       /* input block, or NULL if too old */
424      ulg stored_len;   /* length of input block */
425 +    int pad;          /* pad output to byte boundary */
426      int eof;          /* true if this is the last block for a file */
427  {
428      ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
429 @@ -1009,6 +1010,12 @@
430  #ifdef DEBUG
431          s->compressed_len += 7;  /* align on byte boundary */
432  #endif
433 +#ifdef DEBUG
434 +    } else if (pad && (s->compressed_len % 8) != 0) {
435 +#else
436 +    } else if (pad) {
437 +#endif
438 +        _tr_stored_block(s, buf, 0, eof);
439      }
440      Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
441             s->compressed_len-7*eof));
442 --- gzip-1.2.2/zlib.def 1969-12-31 17:00:00.000000000 -0700
443 +++ rsyncable/zlib.def  2005-02-17 14:01:48.972258000 -0700
444 @@ -0,0 +1,61 @@
445 +LIBRARY
446 +; zlib data compression library
447 +
448 +EXPORTS
449 +; basic functions
450 +    zlibVersion
451 +    deflate
452 +    deflateEnd
453 +    inflate
454 +    inflateEnd
455 +; advanced functions
456 +    deflateSetDictionary
457 +    deflateCopy
458 +    deflateReset
459 +    deflateParams
460 +    deflateBound
461 +    deflatePrime
462 +    inflateSetDictionary
463 +    inflateSync
464 +    inflateCopy
465 +    inflateReset
466 +    inflateBack
467 +    inflateBackEnd
468 +    zlibCompileFlags
469 +; utility functions
470 +    compress
471 +    compress2
472 +    compressBound
473 +    uncompress
474 +    gzopen
475 +    gzdopen
476 +    gzsetparams
477 +    gzread
478 +    gzwrite
479 +    gzprintf
480 +    gzputs
481 +    gzgets
482 +    gzputc
483 +    gzgetc
484 +    gzungetc
485 +    gzflush
486 +    gzseek
487 +    gzrewind
488 +    gztell
489 +    gzeof
490 +    gzclose
491 +    gzerror
492 +    gzclearerr
493 +; checksum functions
494 +    adler32
495 +    crc32
496 +; various hacks, don't look :)
497 +    deflateInit_
498 +    deflateInit2_
499 +    inflateInit_
500 +    inflateInit2_
501 +    inflateBackInit_
502 +    inflateSyncPoint
503 +    get_crc_table
504 +    zError
505 +       deflateSetRsyncParameters_
506 \ No newline at end of file
507 --- gzip-1.2.2/zlib.h   2004-10-03 22:57:26.000000000 -0700
508 +++ rsyncable/zlib.h    2005-02-17 14:02:11.753362200 -0700
509 @@ -179,6 +179,13 @@
510  
511  #define Z_NULL  0  /* for initializing zalloc, zfree, opaque */
512  
513 +
514 +/* Constants used for selecting Rsyncable checksum type */
515 +#define Z_RSYNCABLE_OFF                        0
516 +#define Z_RSYNCABLE_SIMPLESUM  1
517 +#define Z_RSYNCABLE_RSSUM              2
518 +
519 +
520  #define zlib_version zlibVersion()
521  /* for compatibility with versions < 1.0.2 */
522  
523 @@ -1185,6 +1192,17 @@
524          ZLIB_VERSION, sizeof(z_stream))
525  
526  
527 +
528 +/* deflateSetRsyncParameters allows for setting rsyncable parameters on a stream.
529 +       These parameters MUST be set immediately after the stream is created, and before
530 +       any data is written to the stream.
531 + */
532 +ZEXTERN int ZEXPORT deflateSetRsyncParameters_ OF((z_stream FAR *strm, int checksum_type, unsigned long window_size, unsigned long reset_block_size));
533 +
534 +#define deflateSetRsyncParameters(strm, checksum_type, window_size, reset_block_size) \
535 +        deflateSetRsyncParameters_((strm), (checksum_type), (window_size), (reset_block_size))
536 +
537 +
538  #if !defined(ZUTIL_H) && !defined(NO_DUMMY_DECL)
539      struct internal_state {int dummy;}; /* hack for buggy compilers */
540  #endif
541 @@ -1193,6 +1211,10 @@
542  ZEXTERN int            ZEXPORT inflateSyncPoint OF((z_streamp z));
543  ZEXTERN const uLongf * ZEXPORT get_crc_table    OF((void));
544  
545 +/* Global rsync mode control variable */
546 +extern int zlib_rsync;
547 +
548 +
549  #ifdef __cplusplus
550  }
551  #endif