summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorjosh.macdonald <jmacd@users.noreply.github.com>2007-10-20 10:28:50 +0000
committerjosh.macdonald <jmacd@users.noreply.github.com>2007-10-20 10:28:50 +0000
commitd14c20c9747073d2752af20cb5f5c55725fe3db1 (patch)
treed10406cf5b4562fe2f313adef7af5a03fdd63de4
parentcfdf9bf3be42b455a77d72cc58bcdfca76b7a889 (diff)
working on inline functions
-rw-r--r--xdelta3/Makefile2
-rwxr-xr-xxdelta3/releases/xdelta30r.tar.gzbin0 -> 183110 bytes
-rw-r--r--xdelta3/xdelta3-main.h19
-rw-r--r--xdelta3/xdelta3.c284
-rw-r--r--xdelta3/xdelta3.prj2
5 files changed, 153 insertions, 154 deletions
diff --git a/xdelta3/Makefile b/xdelta3/Makefile
index 17fd314..8ce2113 100644
--- a/xdelta3/Makefile
+++ b/xdelta3/Makefile
@@ -104,6 +104,8 @@ wix: xdelta3.wxs xdelta3.wxi readme.txt Release\xdelta3.exe
104 $(WIXDIR)/candle.exe xdelta3.wxs -out xdelta3.wixobj 104 $(WIXDIR)/candle.exe xdelta3.wxs -out xdelta3.wixobj
105 $(WIXDIR)/light.exe xdelta3.wixobj -out xdelta3.msi 105 $(WIXDIR)/light.exe xdelta3.wixobj -out xdelta3.msi
106 106
107CC=gcc-4.2.0
108
107xdelta3: $(SOURCES) 109xdelta3: $(SOURCES)
108 $(CC) -O3 -Wall -Wshadow xdelta3.c -lm -o xdelta3 \ 110 $(CC) -O3 -Wall -Wshadow xdelta3.c -lm -o xdelta3 \
109 -DXD3_DEBUG=0 \ 111 -DXD3_DEBUG=0 \
diff --git a/xdelta3/releases/xdelta30r.tar.gz b/xdelta3/releases/xdelta30r.tar.gz
new file mode 100755
index 0000000..e1bba34
--- /dev/null
+++ b/xdelta3/releases/xdelta30r.tar.gz
Binary files differ
diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h
index c02be63..7f75c98 100644
--- a/xdelta3/xdelta3-main.h
+++ b/xdelta3/xdelta3-main.h
@@ -1370,11 +1370,11 @@ static char* ext_tmpfile = NULL;
1370 1370
1371/* Like write(), but makes repeated calls to empty the buffer. */ 1371/* Like write(), but makes repeated calls to empty the buffer. */
1372static int 1372static int
1373main_pipe_write (int outfd, const uint8_t *exist_buf, usize_t remain) 1373main_pipe_write (int outfd, uint8_t *exist_buf, usize_t remain)
1374{ 1374{
1375 int ret; 1375 int ret;
1376 1376
1377 if ((ret = xd3_posix_io (outfd, (uint8_t*) exist_buf, remain, (xd3_posix_func*) &write, NULL))) 1377 if ((ret = xd3_posix_io (outfd, exist_buf, remain, (xd3_posix_func*) &write, NULL)))
1378 { 1378 {
1379 XPR(NT "pipe write failed: %s", xd3_mainerror (ret)); 1379 XPR(NT "pipe write failed: %s", xd3_mainerror (ret));
1380 return ret; 1380 return ret;
@@ -3420,10 +3420,13 @@ main (int argc, char **argv)
3420static int 3420static int
3421main_help (void) 3421main_help (void)
3422{ 3422{
3423 /* TODO: license info */ 3423 /* $Format: " DP(RINT \"Xdelta version $Xdelta3Version$, Copyright (C) 2007, Joshua MacDonald\n\");" $ */
3424
3425 DP(RINT "Xdelta comes with ABSOLUTELY NO WARRANTY.\n");
3426 DP(RINT "This is free software, and you are welcome to redistribute it\n");
3427 DP(RINT "under certain conditions; see \"COPYING\" for details.\n");
3424 3428
3425 /* Note: update wiki when command-line features change */ 3429 /* Note: update wiki when command-line features change */
3426 main_version ();
3427 DP(RINT "usage: xdelta3 [command/options] [input [output]]\n"); 3430 DP(RINT "usage: xdelta3 [command/options] [input [output]]\n");
3428 DP(RINT "special command names:\n"); 3431 DP(RINT "special command names:\n");
3429 DP(RINT " config prints xdelta3 configuration\n"); 3432 DP(RINT " config prints xdelta3 configuration\n");
@@ -3465,13 +3468,8 @@ main_help (void)
3465 DP(RINT " -n disable checksum (encode/decode)\n"); 3468 DP(RINT " -n disable checksum (encode/decode)\n");
3466 DP(RINT " -C soft config (encode, undocumented)\n"); 3469 DP(RINT " -C soft config (encode, undocumented)\n");
3467 DP(RINT " -A [apphead] disable/provide application header (encode)\n"); 3470 DP(RINT " -A [apphead] disable/provide application header (encode)\n");
3468
3469#if XD3_DEBUG > 0
3470 DP(RINT "developer options:\n");
3471 DP(RINT " -J disable output (check/compute only)\n"); 3471 DP(RINT " -J disable output (check/compute only)\n");
3472 DP(RINT " -P repeat count (for profiling)\n"); 3472 DP(RINT " -T use alternate code table (test)\n");
3473 DP(RINT " -T use alternate code table\n");
3474#endif
3475 3473
3476 DP(RINT "the XDELTA environment variable may contain extra args:\n"); 3474 DP(RINT "the XDELTA environment variable may contain extra args:\n");
3477 DP(RINT " XDELTA=\"-s source-x.y.tar.gz\" \\\n"); 3475 DP(RINT " XDELTA=\"-s source-x.y.tar.gz\" \\\n");
@@ -3479,4 +3477,3 @@ main_help (void)
3479 DP(RINT " -cf target-x.z.tar.gz.vcdiff target-x.y/\n"); 3477 DP(RINT " -cf target-x.z.tar.gz.vcdiff target-x.y/\n");
3480 return EXIT_FAILURE; 3478 return EXIT_FAILURE;
3481} 3479}
3482
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index a545b66..fc0b780 100644
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -4199,145 +4199,6 @@ xd3_srcwin_setup (xd3_stream *stream)
4199 return 0; 4199 return 0;
4200} 4200}
4201 4201
4202/* This function computes more source checksums to advance the window.
4203 * Called at every entrance to the string-match loop and each time
4204 * stream->input_position reaches the value returned as
4205 * *next_move_point. NB: this is one of the most expensive functions
4206 * in this code and also the most critical for good compression.
4207 *
4208 * TODO: really would like a good test for this logic. how?
4209 * TODO: optimize the inner loop
4210 */
4211static int
4212xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
4213{
4214 xoff_t logical_input_cksum_pos;
4215
4216 XD3_ASSERT(stream->srcwin_cksum_pos <= stream->src->size);
4217 if (stream->srcwin_cksum_pos == stream->src->size)
4218 {
4219 *next_move_point = USIZE_T_MAX;
4220 return 0;
4221 }
4222
4223 /* Begin by advancing at twice the input rate, up to half the
4224 * maximum window size. */
4225 logical_input_cksum_pos = min((stream->total_in + stream->input_position) * 2,
4226 (stream->total_in + stream->input_position) +
4227 (stream->srcwin_maxsz / 2));
4228
4229 /* If srcwin_cksum_pos is already greater, wait until the difference
4230 * is met. */
4231 if (stream->srcwin_cksum_pos > logical_input_cksum_pos)
4232 {
4233 *next_move_point = stream->input_position +
4234 (usize_t)(stream->srcwin_cksum_pos - logical_input_cksum_pos);
4235 return 0;
4236 }
4237
4238 /* A long match may have extended past srcwin_cksum_pos. Don't
4239 * start checksumming already-matched source data. */
4240 if (stream->maxsrcaddr > stream->srcwin_cksum_pos)
4241 {
4242 stream->srcwin_cksum_pos = stream->maxsrcaddr;
4243 }
4244
4245 if (logical_input_cksum_pos < stream->srcwin_cksum_pos)
4246 {
4247 logical_input_cksum_pos = stream->srcwin_cksum_pos;
4248 }
4249
4250 /* Advance at least one source block. With the command-line
4251 * defaults this means:
4252 *
4253 * if (src->size <= srcwin_maxsz), index the entire source at once
4254 * using the position of the first non-match. This is good for
4255 * small inputs, especially when the content may have moved anywhere
4256 * in the file (e.g., tar files).
4257 *
4258 * if (src->size > srcwin_maxsz), index at least one block (which
4259 * the command-line sets to 1/32 of srcwin_maxsz) ahead of the
4260 * logical position. This is good for different reasons: when a
4261 * long match spanning several source blocks is encountered, this
4262 * avoids computing checksums for those blocks. If the data can
4263 * move anywhere, this is bad.
4264 */
4265 logical_input_cksum_pos += stream->src->blksize;
4266
4267 IF_DEBUG1 (DP(RINT "[srcwin_move_point] T=%"Q"u S=%"Q"u/%"Q"u\n",
4268 stream->total_in + stream->input_position,
4269 stream->srcwin_cksum_pos,
4270 logical_input_cksum_pos));
4271
4272 while (stream->srcwin_cksum_pos < logical_input_cksum_pos &&
4273 stream->srcwin_cksum_pos < stream->src->size)
4274 {
4275 xoff_t blkno = stream->srcwin_cksum_pos / stream->src->blksize;
4276 ssize_t oldpos = stream->srcwin_cksum_pos % stream->src->blksize;
4277 ssize_t blkpos = xd3_bytes_on_srcblk (stream->src, blkno);
4278 int ret;
4279
4280 if (oldpos + stream->smatcher.large_look > blkpos)
4281 {
4282 stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize;
4283 continue;
4284 }
4285
4286 if ((ret = xd3_getblk (stream, blkno)))
4287 {
4288 /* TOOFARBACK should never occur here, since we read forward. */
4289 if (ret == XD3_TOOFARBACK)
4290 {
4291 ret = XD3_INTERNAL;
4292 }
4293 return ret;
4294 }
4295
4296 /* This inserts checksums for the entire block, in reverse,
4297 * starting from the end of the block. This logic does not test
4298 * stream->srcwin_cksum_pos because it always advances it to the
4299 * start of the next block.
4300 *
4301 * oldpos is the srcwin_cksum_pos within this block. blkpos is
4302 * the number of bytes available. Each iteration inspects
4303 * large_look bytes then steps back large_step bytes. The
4304 * if-stmt above ensures at least one large_look of data. */
4305 blkpos -= stream->smatcher.large_look;
4306
4307 do
4308 {
4309 uint32_t cksum = xd3_lcksum (stream->src->curblk + blkpos,
4310 stream->smatcher.large_look);
4311 usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum);
4312
4313 stream->large_table[hval] =
4314 (usize_t) ((stream->src->blksize * blkno) +
4315 (xoff_t)(blkpos + HASH_CKOFFSET));
4316
4317 IF_DEBUG (stream->large_ckcnt += 1);
4318
4319 blkpos -= stream->smatcher.large_step;
4320 }
4321 while (blkpos >= oldpos);
4322
4323 stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize;
4324 }
4325
4326 if (stream->srcwin_cksum_pos >= stream->src->size)
4327 {
4328 /* This invariant is needed for xd3_source_cksum_offset() */
4329 stream->srcwin_cksum_pos = stream->src->size;
4330 *next_move_point = USIZE_T_MAX;
4331 return 0;
4332 }
4333
4334 /* How long until this function should be called again. */
4335 XD3_ASSERT(stream->srcwin_cksum_pos >= logical_input_cksum_pos);
4336 *next_move_point = stream->input_position + 1 +
4337 (usize_t)(stream->srcwin_cksum_pos - logical_input_cksum_pos);
4338 return 0;
4339}
4340
4341/* Sets the bounding region for a newly discovered source match, prior to calling 4202/* Sets the bounding region for a newly discovered source match, prior to calling
4342 * xd3_source_extend_match(). This sets the match_maxfwd, match_maxback variables. Note: 4203 * xd3_source_extend_match(). This sets the match_maxfwd, match_maxback variables. Note:
4343 * srcpos is an absolute position (xoff_t) but the match_maxfwd, match_maxback variables 4204 * srcpos is an absolute position (xoff_t) but the match_maxfwd, match_maxback variables
@@ -4848,6 +4709,145 @@ static const xd3_smatcher XD3_TEMPLATE(__smatcher_) =
4848#endif 4709#endif
4849}; 4710};
4850 4711
4712/* This function computes more source checksums to advance the window.
4713 * Called at every entrance to the string-match loop and each time
4714 * stream->input_position reaches the value returned as
4715 * *next_move_point. NB: this is one of the most expensive functions
4716 * in this code and also the most critical for good compression.
4717 *
4718 * TODO: really would like a good test for this logic. how?
4719 * TODO: optimize the inner loop
4720 */
4721static int
4722XD3_TEMPLATE(xd3_srcwin_move_point_) (xd3_stream *stream, usize_t *next_move_point)
4723{
4724 xoff_t logical_input_cksum_pos;
4725
4726 XD3_ASSERT(stream->srcwin_cksum_pos <= stream->src->size);
4727 if (stream->srcwin_cksum_pos == stream->src->size)
4728 {
4729 *next_move_point = USIZE_T_MAX;
4730 return 0;
4731 }
4732
4733 /* Begin by advancing at twice the input rate, up to half the
4734 * maximum window size. */
4735 logical_input_cksum_pos = min((stream->total_in + stream->input_position) * 2,
4736 (stream->total_in + stream->input_position) +
4737 (stream->srcwin_maxsz / 2));
4738
4739 /* If srcwin_cksum_pos is already greater, wait until the difference
4740 * is met. */
4741 if (stream->srcwin_cksum_pos > logical_input_cksum_pos)
4742 {
4743 *next_move_point = stream->input_position +
4744 (usize_t)(stream->srcwin_cksum_pos - logical_input_cksum_pos);
4745 return 0;
4746 }
4747
4748 /* A long match may have extended past srcwin_cksum_pos. Don't
4749 * start checksumming already-matched source data. */
4750 if (stream->maxsrcaddr > stream->srcwin_cksum_pos)
4751 {
4752 stream->srcwin_cksum_pos = stream->maxsrcaddr;
4753 }
4754
4755 if (logical_input_cksum_pos < stream->srcwin_cksum_pos)
4756 {
4757 logical_input_cksum_pos = stream->srcwin_cksum_pos;
4758 }
4759
4760 /* Advance at least one source block. With the command-line
4761 * defaults this means:
4762 *
4763 * if (src->size <= srcwin_maxsz), index the entire source at once
4764 * using the position of the first non-match. This is good for
4765 * small inputs, especially when the content may have moved anywhere
4766 * in the file (e.g., tar files).
4767 *
4768 * if (src->size > srcwin_maxsz), index at least one block (which
4769 * the command-line sets to 1/32 of srcwin_maxsz) ahead of the
4770 * logical position. This is good for different reasons: when a
4771 * long match spanning several source blocks is encountered, this
4772 * avoids computing checksums for those blocks. If the data can
4773 * move anywhere, this is bad.
4774 */
4775 logical_input_cksum_pos += stream->src->blksize;
4776
4777 IF_DEBUG1 (DP(RINT "[srcwin_move_point] T=%"Q"u S=%"Q"u/%"Q"u\n",
4778 stream->total_in + stream->input_position,
4779 stream->srcwin_cksum_pos,
4780 logical_input_cksum_pos));
4781
4782 while (stream->srcwin_cksum_pos < logical_input_cksum_pos &&
4783 stream->srcwin_cksum_pos < stream->src->size)
4784 {
4785 xoff_t blkno = stream->srcwin_cksum_pos / stream->src->blksize;
4786 ssize_t oldpos = stream->srcwin_cksum_pos % stream->src->blksize;
4787 ssize_t blkpos = xd3_bytes_on_srcblk (stream->src, blkno);
4788 int ret;
4789
4790 if (oldpos + stream->smatcher.large_look > blkpos)
4791 {
4792 stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize;
4793 continue;
4794 }
4795
4796 if ((ret = xd3_getblk (stream, blkno)))
4797 {
4798 /* TOOFARBACK should never occur here, since we read forward. */
4799 if (ret == XD3_TOOFARBACK)
4800 {
4801 ret = XD3_INTERNAL;
4802 }
4803 return ret;
4804 }
4805
4806 /* This inserts checksums for the entire block, in reverse,
4807 * starting from the end of the block. This logic does not test
4808 * stream->srcwin_cksum_pos because it always advances it to the
4809 * start of the next block.
4810 *
4811 * oldpos is the srcwin_cksum_pos within this block. blkpos is
4812 * the number of bytes available. Each iteration inspects
4813 * large_look bytes then steps back large_step bytes. The
4814 * if-stmt above ensures at least one large_look of data. */
4815 blkpos -= stream->smatcher.large_look;
4816
4817 do
4818 {
4819 uint32_t cksum = xd3_lcksum (stream->src->curblk + blkpos,
4820 stream->smatcher.large_look);
4821 usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum);
4822
4823 stream->large_table[hval] =
4824 (usize_t) ((stream->src->blksize * blkno) +
4825 (xoff_t)(blkpos + HASH_CKOFFSET));
4826
4827 IF_DEBUG (stream->large_ckcnt += 1);
4828
4829 blkpos -= stream->smatcher.large_step;
4830 }
4831 while (blkpos >= oldpos);
4832
4833 stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize;
4834 }
4835
4836 if (stream->srcwin_cksum_pos >= stream->src->size)
4837 {
4838 /* This invariant is needed for xd3_source_cksum_offset() */
4839 stream->srcwin_cksum_pos = stream->src->size;
4840 *next_move_point = USIZE_T_MAX;
4841 return 0;
4842 }
4843
4844 /* How long until this function should be called again. */
4845 XD3_ASSERT(stream->srcwin_cksum_pos >= logical_input_cksum_pos);
4846 *next_move_point = stream->input_position + 1 +
4847 (usize_t)(stream->srcwin_cksum_pos - logical_input_cksum_pos);
4848 return 0;
4849}
4850
4851static int 4851static int
4852XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream) 4852XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
4853{ 4853{
@@ -4866,7 +4866,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
4866 int run_l; 4866 int run_l;
4867 int ret; 4867 int ret;
4868 usize_t match_length; 4868 usize_t match_length;
4869 usize_t match_offset; /* "may be unused" warnings are bogus (due to min_match test) */ 4869 usize_t match_offset = 0;
4870 usize_t next_move_point; 4870 usize_t next_move_point;
4871 4871
4872 /* If there will be no compression due to settings or short input, skip it entirely. */ 4872 /* If there will be no compression due to settings or short input, skip it entirely. */
@@ -4917,7 +4917,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
4917 { 4917 {
4918 /* Source window: next_move_point is the point that stream->input_position must reach before 4918 /* Source window: next_move_point is the point that stream->input_position must reach before
4919 * computing more source checksum. */ 4919 * computing more source checksum. */
4920 if ((ret = xd3_srcwin_move_point (stream, & next_move_point))) 4920 if ((ret = XD3_TEMPLATE(xd3_srcwin_move_point_) (stream, & next_move_point)))
4921 { 4921 {
4922 return ret; 4922 return ret;
4923 } 4923 }
@@ -4973,7 +4973,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
4973 if (DO_LARGE && (stream->input_position + LLOOK <= stream->avail_in)) 4973 if (DO_LARGE && (stream->input_position + LLOOK <= stream->avail_in))
4974 { 4974 {
4975 if ((stream->input_position >= next_move_point) && 4975 if ((stream->input_position >= next_move_point) &&
4976 (ret = xd3_srcwin_move_point (stream, & next_move_point))) 4976 (ret = XD3_TEMPLATE(xd3_srcwin_move_point_) (stream, & next_move_point)))
4977 { 4977 {
4978 return ret; 4978 return ret;
4979 } 4979 }
diff --git a/xdelta3/xdelta3.prj b/xdelta3/xdelta3.prj
index de7b70a..7bcb904 100644
--- a/xdelta3/xdelta3.prj
+++ b/xdelta3/xdelta3.prj
@@ -9,7 +9,7 @@
9(Checkin-Login jmacd) 9(Checkin-Login jmacd)
10(Populate-Ignore ("\\.svn")) 10(Populate-Ignore ("\\.svn"))
11(Project-Keywords 11(Project-Keywords
12 (Xdelta3Version "0r") 12 (Xdelta3Version "3.0r")
13 ) 13 )
14(Files 14(Files
15 (COPYING (xdelta3/b/29_COPYING 1.1 744)) 15 (COPYING (xdelta3/b/29_COPYING 1.1 744))