summaryrefslogtreecommitdiff
path: root/xdelta3
diff options
context:
space:
mode:
authorjosh.macdonald <jmacd@users.noreply.github.com>2007-02-04 09:30:02 +0000
committerjosh.macdonald <jmacd@users.noreply.github.com>2007-02-04 09:30:02 +0000
commit400e5c3f9edbfedfa770c94c04e62aa8657ed04a (patch)
treea929bd434ec27cb53846fd43c910a244d3585011 /xdelta3
parent1e10015476fb24d78d0b14de6a7819586037382d (diff)
Adds a new compression level (-6), makes -1 faster and -9 better.
Diffstat (limited to 'xdelta3')
-rwxr-xr-xxdelta3/xdelta3-cfgs.h55
-rwxr-xr-xxdelta3/xdelta3-main.h3
-rwxr-xr-xxdelta3/xdelta3.c183
-rwxr-xr-xxdelta3/xdelta3.h3
4 files changed, 142 insertions, 102 deletions
diff --git a/xdelta3/xdelta3-cfgs.h b/xdelta3/xdelta3-cfgs.h
index beb7c48..955ff51 100755
--- a/xdelta3/xdelta3-cfgs.h
+++ b/xdelta3/xdelta3-cfgs.h
@@ -58,16 +58,16 @@
58 ******************************************************************************************/ 58 ******************************************************************************************/
59#if XD3_BUILD_FAST 59#if XD3_BUILD_FAST
60#define TEMPLATE fast 60#define TEMPLATE fast
61#define LLOOK 11 61#define LLOOK 9
62#define LSTEP 7 62#define LSTEP 8
63#define SLOOK 4 63#define SLOOK 4
64#define SCHAIN 5 64#define SCHAIN 5
65#define SLCHAIN 0 65#define SLCHAIN 1
66#define SSMATCH 0 66#define SSMATCH 0
67#define TRYLAZY 0 67#define TRYLAZY 1
68#define MAXLAZY 50 68#define MAXLAZY 5
69#define LONGENOUGH 0 69#define LONGENOUGH 4
70#define PROMOTE 1 70#define PROMOTE 0
71 71
72#include "xdelta3.c" 72#include "xdelta3.c"
73 73
@@ -89,15 +89,46 @@
89 ******************************************************************************************/ 89 ******************************************************************************************/
90#if XD3_BUILD_SLOW 90#if XD3_BUILD_SLOW
91#define TEMPLATE slow 91#define TEMPLATE slow
92#define LLOOK 10 92#define LLOOK 9
93#define LSTEP 1 93#define LSTEP 1
94#define SLOOK 4 94#define SLOOK 4
95#define SCHAIN 36 95#define SCHAIN 9
96#define SLCHAIN 13 96#define SLCHAIN 5
97#define SSMATCH 0
98#define TRYLAZY 1
99#define MAXLAZY 200
100#define LONGENOUGH 400
101#define PROMOTE 0
102
103#include "xdelta3.c"
104
105#undef TEMPLATE
106#undef LLOOK
107#undef SLOOK
108#undef LSTEP
109#undef SCHAIN
110#undef SLCHAIN
111#undef SSMATCH
112#undef TRYLAZY
113#undef MAXLAZY
114#undef LONGENOUGH
115#undef PROMOTE
116#endif
117
118/******************************************************************************************
119 DEFAULT string matcher
120 ******************************************************************************************/
121#if XD3_BUILD_DEFAULT
122#define TEMPLATE default
123#define LLOOK 9
124#define LSTEP 4
125#define SLOOK 4
126#define SCHAIN 7
127#define SLCHAIN 3
97#define SSMATCH 0 128#define SSMATCH 0
98#define TRYLAZY 1 129#define TRYLAZY 1
99#define MAXLAZY 512 130#define MAXLAZY 30
100#define LONGENOUGH 256 131#define LONGENOUGH 20
101#define PROMOTE 0 132#define PROMOTE 0
102 133
103#include "xdelta3.c" 134#include "xdelta3.c"
diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h
index f45ad06..887f368 100755
--- a/xdelta3/xdelta3-main.h
+++ b/xdelta3/xdelta3-main.h
@@ -245,7 +245,7 @@ static int option_stdout = 0;
245static int option_force = 0; 245static int option_force = 0;
246static int option_verbose = 0; 246static int option_verbose = 0;
247static int option_quiet = 0; 247static int option_quiet = 0;
248static int option_level = 5; 248static int option_level = 6;
249static int option_use_appheader = 1; 249static int option_use_appheader = 1;
250static uint8_t* option_appheader = NULL; 250static uint8_t* option_appheader = NULL;
251static int option_use_secondary = 0; 251static int option_use_secondary = 0;
@@ -2363,6 +2363,7 @@ main_input (xd3_cmd cmd,
2363 config.smatcher_soft.promote = values[9]; 2363 config.smatcher_soft.promote = values[9];
2364 } 2364 }
2365 else if (option_level <= 5) { config.smatch_cfg = XD3_SMATCH_FAST; } 2365 else if (option_level <= 5) { config.smatch_cfg = XD3_SMATCH_FAST; }
2366 else if (option_level == 6) { config.smatch_cfg = XD3_SMATCH_DEFAULT; }
2366 else { config.smatch_cfg = XD3_SMATCH_SLOW; } 2367 else { config.smatch_cfg = XD3_SMATCH_SLOW; }
2367 break; 2368 break;
2368#endif 2369#endif
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index f8c0bc7..4941408 100755
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -473,10 +473,16 @@ XD3_MAKELIST(xd3_rlist, xd3_rinst, link);
473#else 473#else
474#define IF_BUILD_SOFT(x) 474#define IF_BUILD_SOFT(x)
475#endif 475#endif
476#if XD3_BUILD_DEFAULT
477#define IF_BUILD_DEFAULT(x) x
478#else
479#define IF_BUILD_DEFAULT(x)
480#endif
476 481
477IF_BUILD_SOFT(static const xd3_smatcher __smatcher_soft;) 482IF_BUILD_SOFT(static const xd3_smatcher __smatcher_soft;)
478IF_BUILD_FAST(static const xd3_smatcher __smatcher_fast;) 483IF_BUILD_FAST(static const xd3_smatcher __smatcher_fast;)
479IF_BUILD_SLOW(static const xd3_smatcher __smatcher_slow;) 484IF_BUILD_SLOW(static const xd3_smatcher __smatcher_slow;)
485IF_BUILD_DEFAULT(static const xd3_smatcher __smatcher_default;)
480 486
481#if XD3_DEBUG 487#if XD3_DEBUG
482#define SMALL_HASH_DEBUG1(s,inp) \ 488#define SMALL_HASH_DEBUG1(s,inp) \
@@ -577,7 +583,6 @@ static usize_t xd3_sizeof_output (xd3_output *output);
577static int xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos); 583static int xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos);
578static int xd3_source_extend_match (xd3_stream *stream); 584static int xd3_source_extend_match (xd3_stream *stream);
579static int xd3_srcwin_setup (xd3_stream *stream); 585static int xd3_srcwin_setup (xd3_stream *stream);
580static int xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point);
581static usize_t xd3_iopt_last_matched (xd3_stream *stream); 586static usize_t xd3_iopt_last_matched (xd3_stream *stream);
582static int xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num); 587static int xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num);
583 588
@@ -2514,7 +2519,9 @@ xd3_config_stream(xd3_stream *stream,
2514 break; 2519 break;
2515 }) 2520 })
2516 2521
2517 IF_BUILD_SLOW(case XD3_SMATCH_DEFAULT:) 2522 IF_BUILD_DEFAULT(case XD3_SMATCH_DEFAULT:
2523 *smatcher = __smatcher_default;
2524 break;)
2518 IF_BUILD_SLOW(case XD3_SMATCH_SLOW: 2525 IF_BUILD_SLOW(case XD3_SMATCH_SLOW:
2519 *smatcher = __smatcher_slow; 2526 *smatcher = __smatcher_slow;
2520 break;) 2527 break;)
@@ -4061,6 +4068,89 @@ xd3_string_match_init (xd3_stream *stream)
4061 return 0; 4068 return 0;
4062} 4069}
4063 4070
4071/* This function handles the 32/64bit ambiguity -- file positions are 64bit but the hash
4072 * table for source-offsets is 32bit. */
4073static xoff_t
4074xd3_source_cksum_offset(xd3_stream *stream, usize_t low)
4075{
4076 xoff_t scp = stream->srcwin_cksum_pos;
4077 xoff_t s0 = scp >> 32;
4078
4079 usize_t sr = (usize_t) scp;
4080
4081 if (s0 == 0) {
4082 return low;
4083 }
4084
4085 // This should not be >= because srcwin_cksum_pos is the next position to index
4086 if (low > sr) {
4087 return (--s0 << 32) | low;
4088 }
4089
4090 return (s0 << 32) | low;
4091}
4092
4093/* This function sets up the stream->src fields srcbase, srclen. The call is delayed
4094 * until these values are needed to encode a copy address. At this point the decision has
4095 * to be made. */
4096static int
4097xd3_srcwin_setup (xd3_stream *stream)
4098{
4099 xd3_source *src = stream->src;
4100 xoff_t length;
4101
4102 /* Check the undecided state. */
4103 XD3_ASSERT (src->srclen == 0 && src->srcbase == 0);
4104
4105 /* Avoid repeating this call. */
4106 stream->srcwin_decided = 1;
4107
4108 /* If the stream is flushing, then the iopt buffer was able to contain the complete
4109 * encoding. If no copies were issued no source window is actually needed. This
4110 * prevents the VCDIFF header from including source base/len. xd3_emit_hdr checks
4111 * for srclen == 0. */
4112 if (stream->enc_state == ENC_FLUSH && stream->match_maxaddr == 0)
4113 {
4114 goto done;
4115 }
4116
4117 /* Check for overflow, srclen is usize_t - this can't happen unless XD3_DEFAULT_SRCBACK
4118 * and related parameters are extreme - should use smaller windows. */
4119 length = stream->match_maxaddr - stream->match_minaddr;
4120
4121 if (length > (xoff_t) USIZE_T_MAX)
4122 {
4123 stream->msg = "source window length overflow (not 64bit)";
4124 return XD3_INTERNAL;
4125 }
4126
4127 /* If ENC_FLUSH, then we know the exact source window to use because no more copies can
4128 * be issued. */
4129 if (stream->enc_state == ENC_FLUSH)
4130 {
4131 src->srcbase = stream->match_minaddr;
4132 src->srclen = (usize_t) length;
4133 XD3_ASSERT (src->srclen);
4134 goto done;
4135 }
4136
4137 /* Otherwise, we have to make a guess. More copies may still be issued, but we have to
4138 * decide the source window base and length now. */
4139 src->srcbase = stream->match_minaddr;
4140 src->srclen = max ((usize_t) length, stream->avail_in + (stream->avail_in >> 2));
4141 if (src->size < src->srcbase + (xoff_t) src->srclen)
4142 {
4143 /* Could reduce srcbase, as well. */
4144 src->srclen = src->size - src->srcbase;
4145 }
4146
4147 XD3_ASSERT (src->srclen);
4148 done:
4149 /* Set the taroff. This convenience variable is used even when stream->src == NULL. */
4150 stream->taroff = src->srclen;
4151 return 0;
4152}
4153
4064/* Called at every entrance to the string-match loop and each time 4154/* Called at every entrance to the string-match loop and each time
4065 * stream->input_position the value returned as *next_move_point. 4155 * stream->input_position the value returned as *next_move_point.
4066 * This function computes more source checksums to advance the window. */ 4156 * This function computes more source checksums to advance the window. */
@@ -4138,14 +4228,12 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
4138 diff = logical_input_cksum_pos - stream->srcwin_cksum_pos; 4228 diff = logical_input_cksum_pos - stream->srcwin_cksum_pos;
4139 onblk = min(blkoff + diff, onblk); 4229 onblk = min(blkoff + diff, onblk);
4140 4230
4141 /* TODO: This block needs to be included in the template pass... duh.
4142 */
4143
4144 /* Note: I experimented with rewriting this block to use LARGE_CKSUM_UPDATE() 4231 /* Note: I experimented with rewriting this block to use LARGE_CKSUM_UPDATE()
4145 * instead of recalculating the cksum every N bytes. It seemed to make performance 4232 * instead of recalculating the cksum every N bytes. It seemed to make performance
4146 * worse. */ 4233 * worse (except obviously for step == 1, not worth extra complexity) */
4147 while (blkoff <= onblk) 4234 while (blkoff <= onblk)
4148 { 4235 {
4236 /* It's a big win to have the compiler optimize this loop w/ fi. */
4149 uint32_t cksum = xd3_lcksum (stream->src->curblk + blkoff, stream->smatcher.large_look); 4237 uint32_t cksum = xd3_lcksum (stream->src->curblk + blkoff, stream->smatcher.large_look);
4150 usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum); 4238 usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum);
4151 4239
@@ -4167,89 +4255,6 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
4167 return 0; 4255 return 0;
4168} 4256}
4169 4257
4170/* This function handles the 32/64bit ambiguity -- file positions are 64bit but the hash
4171 * table for source-offsets is 32bit. */
4172static xoff_t
4173xd3_source_cksum_offset(xd3_stream *stream, usize_t low)
4174{
4175 xoff_t scp = stream->srcwin_cksum_pos;
4176 xoff_t s0 = scp >> 32;
4177
4178 usize_t sr = (usize_t) scp;
4179
4180 if (s0 == 0) {
4181 return low;
4182 }
4183
4184 // This should not be >= because srcwin_cksum_pos is the next position to index
4185 if (low > sr) {
4186 return (--s0 << 32) | low;
4187 }
4188
4189 return (s0 << 32) | low;
4190}
4191
4192/* This function sets up the stream->src fields srcbase, srclen. The call is delayed
4193 * until these values are needed to encode a copy address. At this point the decision has
4194 * to be made. */
4195static int
4196xd3_srcwin_setup (xd3_stream *stream)
4197{
4198 xd3_source *src = stream->src;
4199 xoff_t length;
4200
4201 /* Check the undecided state. */
4202 XD3_ASSERT (src->srclen == 0 && src->srcbase == 0);
4203
4204 /* Avoid repeating this call. */
4205 stream->srcwin_decided = 1;
4206
4207 /* If the stream is flushing, then the iopt buffer was able to contain the complete
4208 * encoding. If no copies were issued no source window is actually needed. This
4209 * prevents the VCDIFF header from including source base/len. xd3_emit_hdr checks
4210 * for srclen == 0. */
4211 if (stream->enc_state == ENC_FLUSH && stream->match_maxaddr == 0)
4212 {
4213 goto done;
4214 }
4215
4216 /* Check for overflow, srclen is usize_t - this can't happen unless XD3_DEFAULT_SRCBACK
4217 * and related parameters are extreme - should use smaller windows. */
4218 length = stream->match_maxaddr - stream->match_minaddr;
4219
4220 if (length > (xoff_t) USIZE_T_MAX)
4221 {
4222 stream->msg = "source window length overflow (not 64bit)";
4223 return XD3_INTERNAL;
4224 }
4225
4226 /* If ENC_FLUSH, then we know the exact source window to use because no more copies can
4227 * be issued. */
4228 if (stream->enc_state == ENC_FLUSH)
4229 {
4230 src->srcbase = stream->match_minaddr;
4231 src->srclen = (usize_t) length;
4232 XD3_ASSERT (src->srclen);
4233 goto done;
4234 }
4235
4236 /* Otherwise, we have to make a guess. More copies may still be issued, but we have to
4237 * decide the source window base and length now. */
4238 src->srcbase = stream->match_minaddr;
4239 src->srclen = max ((usize_t) length, stream->avail_in + (stream->avail_in >> 2));
4240 if (src->size < src->srcbase + (xoff_t) src->srclen)
4241 {
4242 /* Could reduce srcbase, as well. */
4243 src->srclen = src->size - src->srcbase;
4244 }
4245
4246 XD3_ASSERT (src->srclen);
4247 done:
4248 /* Set the taroff. This convenience variable is used even when stream->src == NULL. */
4249 stream->taroff = src->srclen;
4250 return 0;
4251}
4252
4253/* Sets the bounding region for a newly discovered source match, prior to calling 4258/* Sets the bounding region for a newly discovered source match, prior to calling
4254 * xd3_source_extend_match(). This sets the match_maxfwd, match_maxback variables. Note: 4259 * xd3_source_extend_match(). This sets the match_maxfwd, match_maxback variables. Note:
4255 * srcpos is an absolute position (xoff_t) but the match_maxfwd, match_maxback variables 4260 * srcpos is an absolute position (xoff_t) but the match_maxfwd, match_maxback variables
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h
index ca4c79a..6bc6d37 100755
--- a/xdelta3/xdelta3.h
+++ b/xdelta3/xdelta3.h
@@ -176,6 +176,9 @@ typedef uint32_t xoff_t;
176#ifndef XD3_BUILD_SOFT 176#ifndef XD3_BUILD_SOFT
177#define XD3_BUILD_SOFT 1 177#define XD3_BUILD_SOFT 1
178#endif 178#endif
179#ifndef XD3_BUILD_DEFAULT
180#define XD3_BUILD_DEFAULT 1
181#endif
179 182
180#if XD3_DEBUG 183#if XD3_DEBUG
181#include <stdio.h> 184#include <stdio.h>