diff options
author | josh.macdonald <jmacd@users.noreply.github.com> | 2007-02-04 09:30:02 +0000 |
---|---|---|
committer | josh.macdonald <jmacd@users.noreply.github.com> | 2007-02-04 09:30:02 +0000 |
commit | 400e5c3f9edbfedfa770c94c04e62aa8657ed04a (patch) | |
tree | a929bd434ec27cb53846fd43c910a244d3585011 /xdelta3 | |
parent | 1e10015476fb24d78d0b14de6a7819586037382d (diff) |
Adds a new compression level (-6), makes -1 faster and -9 better.
Diffstat (limited to 'xdelta3')
-rwxr-xr-x | xdelta3/xdelta3-cfgs.h | 55 | ||||
-rwxr-xr-x | xdelta3/xdelta3-main.h | 3 | ||||
-rwxr-xr-x | xdelta3/xdelta3.c | 183 | ||||
-rwxr-xr-x | xdelta3/xdelta3.h | 3 |
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; | |||
245 | static int option_force = 0; | 245 | static int option_force = 0; |
246 | static int option_verbose = 0; | 246 | static int option_verbose = 0; |
247 | static int option_quiet = 0; | 247 | static int option_quiet = 0; |
248 | static int option_level = 5; | 248 | static int option_level = 6; |
249 | static int option_use_appheader = 1; | 249 | static int option_use_appheader = 1; |
250 | static uint8_t* option_appheader = NULL; | 250 | static uint8_t* option_appheader = NULL; |
251 | static int option_use_secondary = 0; | 251 | static 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 | ||
477 | IF_BUILD_SOFT(static const xd3_smatcher __smatcher_soft;) | 482 | IF_BUILD_SOFT(static const xd3_smatcher __smatcher_soft;) |
478 | IF_BUILD_FAST(static const xd3_smatcher __smatcher_fast;) | 483 | IF_BUILD_FAST(static const xd3_smatcher __smatcher_fast;) |
479 | IF_BUILD_SLOW(static const xd3_smatcher __smatcher_slow;) | 484 | IF_BUILD_SLOW(static const xd3_smatcher __smatcher_slow;) |
485 | IF_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); | |||
577 | static int xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos); | 583 | static int xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos); |
578 | static int xd3_source_extend_match (xd3_stream *stream); | 584 | static int xd3_source_extend_match (xd3_stream *stream); |
579 | static int xd3_srcwin_setup (xd3_stream *stream); | 585 | static int xd3_srcwin_setup (xd3_stream *stream); |
580 | static int xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point); | ||
581 | static usize_t xd3_iopt_last_matched (xd3_stream *stream); | 586 | static usize_t xd3_iopt_last_matched (xd3_stream *stream); |
582 | static int xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num); | 587 | static 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. */ | ||
4073 | static xoff_t | ||
4074 | xd3_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. */ | ||
4096 | static int | ||
4097 | xd3_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. */ | ||
4172 | static xoff_t | ||
4173 | xd3_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. */ | ||
4195 | static int | ||
4196 | xd3_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> |