summaryrefslogtreecommitdiff
path: root/xdelta3
diff options
context:
space:
mode:
Diffstat (limited to 'xdelta3')
-rw-r--r--xdelta3/Makefile26
-rwxr-xr-xxdelta3/examples/Makefile4
-rw-r--r--xdelta3/xdelta3-decode.h181
-rw-r--r--xdelta3/xdelta3-djw.h5
-rw-r--r--xdelta3/xdelta3-main.h10
-rw-r--r--xdelta3/xdelta3-test.h213
-rw-r--r--xdelta3/xdelta3.c372
-rw-r--r--xdelta3/xdelta3.h153
8 files changed, 576 insertions, 388 deletions
diff --git a/xdelta3/Makefile b/xdelta3/Makefile
index 40647e8..10f5d33 100644
--- a/xdelta3/Makefile
+++ b/xdelta3/Makefile
@@ -125,12 +125,30 @@ xdelta3-32: $(SOURCES)
125 -DXD3_POSIX=1 125 -DXD3_POSIX=1
126 126
127xdelta3-debug: $(SOURCES) 127xdelta3-debug: $(SOURCES)
128 $(CC) -g -Wall -Wshadow xdelta3.c -o xdelta3-debug -DXD3_MAIN=1 -DGENERIC_ENCODE_TABLES=1 \ 128 $(CC) -g -Wall -Wshadow \
129 -DXD3_USE_LARGEFILE64=1 -DXD3_STDIO=1 -DREGRESSION_TEST=1 -DXD3_DEBUG=1 -DSECONDARY_DJW=1 -DSECONDARY_FGK=1 -lm 129 xdelta3.c -o xdelta3-debug \
130 -DXD3_DEBUG=1 \
131 -DXD3_MAIN=1 \
132 -DXD3_STDIO=1 \
133 -DXD3_USE_LARGEFILE64=1 \
134 -DGENERIC_ENCODE_TABLES=1 \
135 -DREGRESSION_TEST=1 \
136 -DSECONDARY_DJW=1 \
137 -DSECONDARY_FGK=1 \
138 -lm
130 139
131xdelta3-debug2: $(SOURCES) 140xdelta3-debug2: $(SOURCES)
132 $(CC) -g -Wall -Wshadow xdelta3.c -o xdelta3-debug2 -DXD3_MAIN=1 -DGENERIC_ENCODE_TABLES=1 \ 141 $(CC) -g -Wall -Wshadow \
133 -DXD3_USE_LARGEFILE64=1 -DXD3_STDIO=1 -DREGRESSION_TEST=1 -DXD3_DEBUG=2 -DSECONDARY_DJW=1 -DSECONDARY_FGK=1 -lm 142 xdelta3.c -o xdelta3-debug2 \
143 -DXD3_DEBUG=2 \
144 -DXD3_MAIN=1 \
145 -DXD3_STDIO=1 \
146 -DXD3_USE_LARGEFILE64=1 \
147 -DGENERIC_ENCODE_TABLES=1 \
148 -DREGRESSION_TEST=1 \
149 -DSECONDARY_DJW=1 \
150 -DSECONDARY_FGK=1 \
151 -lm
134 152
135xdelta3-debug3: $(SOURCES) 153xdelta3-debug3: $(SOURCES)
136 $(CC) -g -Wall -Wshadow xdelta3.c -o xdelta3-debug3 -DXD3_MAIN=1 -DGENERIC_ENCODE_TABLES=1 \ 154 $(CC) -g -Wall -Wshadow xdelta3.c -o xdelta3-debug3 -DXD3_MAIN=1 -DGENERIC_ENCODE_TABLES=1 \
diff --git a/xdelta3/examples/Makefile b/xdelta3/examples/Makefile
index 2a6c966..d171a80 100755
--- a/xdelta3/examples/Makefile
+++ b/xdelta3/examples/Makefile
@@ -1,5 +1,7 @@
1#CFLAGS = -g -Wall -I.. -DXD3_DEBUG=1 1#CFLAGS = -g -Wall -I..
2# -DXD3_DEBUG=1
2CFLAGS = -O3 -pg -Wall -I.. -DXD3_DEBUG=0 3CFLAGS = -O3 -pg -Wall -I.. -DXD3_DEBUG=0
4# -pg
3 5
4SOURCES = small_page_test.c encode_decode_test.c speed_test.c 6SOURCES = small_page_test.c encode_decode_test.c speed_test.c
5 7
diff --git a/xdelta3/xdelta3-decode.h b/xdelta3/xdelta3-decode.h
index bb03c04..5ddf823 100644
--- a/xdelta3/xdelta3-decode.h
+++ b/xdelta3/xdelta3-decode.h
@@ -20,19 +20,21 @@
20#define _XDELTA3_DECODE_H_ 20#define _XDELTA3_DECODE_H_
21 21
22 22
23/* Return true if the caller must provide a source. Theoretically, this has to be checked 23/* Return true if the caller must provide a source. Theoretically,
24 * after every window. It could be that the first window requires no source, but the 24 * this has to be checked after every window. It could be that the
25 * second window does. In practice? */ 25 * first window requires no source, but the second window does. In
26 * practice? */
26int xd3_decoder_needs_source (xd3_stream *stream) 27int xd3_decoder_needs_source (xd3_stream *stream)
27{ 28{
28 return stream->dec_win_ind & VCD_SOURCE; 29 return stream->dec_win_ind & VCD_SOURCE;
29} 30}
30 31
31/* Initialize the decoder for a new window. The dec_tgtlen value is preserved across 32/* Initialize the decoder for a new window. The dec_tgtlen value is
32 * successive window decodings, and the update to dec_winstart is delayed until a new 33 * preserved across successive window decodings, and the update to
33 * window actually starts. This is to avoid throwing an error due to overflow until the 34 * dec_winstart is delayed until a new window actually starts. This
34 * last possible moment. This makes it possible to encode exactly 4GB through a 32-bit 35 * is to avoid throwing an error due to overflow until the last
35 * encoder. */ 36 * possible moment. This makes it possible to encode exactly 4GB
37 * through a 32-bit encoder. */
36static int 38static int
37xd3_decode_init_window (xd3_stream *stream) 39xd3_decode_init_window (xd3_stream *stream)
38{ 40{
@@ -45,25 +47,28 @@ xd3_decode_init_window (xd3_stream *stream)
45 return 0; 47 return 0;
46} 48}
47 49
48/* Allocates buffer space for the target window and possibly the VCD_TARGET copy-window. 50/* Allocates buffer space for the target window and possibly the
49 * Also sets the base of the two copy segments. */ 51 * VCD_TARGET copy-window. Also sets the base of the two copy
52 * segments. */
50static int 53static int
51xd3_decode_setup_buffers (xd3_stream *stream) 54xd3_decode_setup_buffers (xd3_stream *stream)
52{ 55{
53 /* If VCD_TARGET is set then the previous buffer may be reused. */ 56 /* If VCD_TARGET is set then the previous buffer may be reused. */
54 if (stream->dec_win_ind & VCD_TARGET) 57 if (stream->dec_win_ind & VCD_TARGET)
55 { 58 {
56 /* But this implementation only supports copying from the last target window. If the 59 /* But this implementation only supports copying from the last
57 * offset is outside that range, it can't be done. */ 60 * target window. If the offset is outside that range, it can't
61 * be done. */
58 if (stream->dec_cpyoff < stream->dec_laststart) 62 if (stream->dec_cpyoff < stream->dec_laststart)
59 { 63 {
60 stream->msg = "unsupported VCD_TARGET offset"; 64 stream->msg = "unsupported VCD_TARGET offset";
61 return XD3_INVALID_INPUT; 65 return XD3_INVALID_INPUT;
62 } 66 }
63 67
64 /* See if the two windows are the same. This indicates the first time VCD_TARGET is 68 /* See if the two windows are the same. This indicates the
65 * used. This causes a second buffer to be allocated, after that the two are 69 * first time VCD_TARGET is used. This causes a second buffer
66 * swapped in the DEC_FINISH case. */ 70 * to be allocated, after that the two are swapped in the
71 * DEC_FINISH case. */
67 if (stream->dec_lastwin == stream->next_out) 72 if (stream->dec_lastwin == stream->next_out)
68 { 73 {
69 stream->next_out = NULL; 74 stream->next_out = NULL;
@@ -88,9 +93,10 @@ xd3_decode_setup_buffers (xd3_stream *stream)
88 stream->next_out = stream->dec_buffer; 93 stream->next_out = stream->dec_buffer;
89 } 94 }
90 95
91 /* dec_tgtaddrbase refers to an invalid base address, but it is always used with a 96 /* dec_tgtaddrbase refers to an invalid base address, but it is
92 * sufficiently large instruction offset (i.e., beyond the copy window). This condition 97 * always used with a sufficiently large instruction offset (i.e.,
93 * is enforced by xd3_decode_output_halfinst. */ 98 * beyond the copy window). This condition is enforced by
99 * xd3_decode_output_halfinst. */
94 stream->dec_tgtaddrbase = stream->next_out - stream->dec_cpylen; 100 stream->dec_tgtaddrbase = stream->next_out - stream->dec_cpylen;
95 101
96 return 0; 102 return 0;
@@ -190,9 +196,10 @@ xd3_decode_section (xd3_stream *stream,
190 return 0; 196 return 0;
191} 197}
192 198
193/* Decode the size and address for half of an instruction (i.e., a single opcode). This 199/* Decode the size and address for half of an instruction (i.e., a
194 * updates the stream->dec_position, which are bytes already output prior to processing 200 * single opcode). This updates the stream->dec_position, which are
195 * this instruction. Perform bounds checking for sizes and copy addresses, which uses the 201 * bytes already output prior to processing this instruction. Perform
202 * bounds checking for sizes and copy addresses, which uses the
196 * dec_position (which is why these checks are done here). */ 203 * dec_position (which is why these checks are done here). */
197static int 204static int
198xd3_decode_parse_halfinst (xd3_stream *stream, xd3_hinst *inst) 205xd3_decode_parse_halfinst (xd3_stream *stream, xd3_hinst *inst)
@@ -303,9 +310,10 @@ xd3_decode_instruction (xd3_stream *stream)
303 stream->dec_current1.size = inst->size1; 310 stream->dec_current1.size = inst->size1;
304 stream->dec_current2.size = inst->size2; 311 stream->dec_current2.size = inst->size2;
305 312
306 /* For each instruction with a real operation, decode the corresponding size and 313 /* For each instruction with a real operation, decode the
307 * addresses if necessary. Assume a code-table may have NOOP in either position, 314 * corresponding size and addresses if necessary. Assume a
308 * although this is unlikely. */ 315 * code-table may have NOOP in either position, although this is
316 * unlikely. */
309 if (inst->type1 != XD3_NOOP && (ret = xd3_decode_parse_halfinst (stream, & stream->dec_current1))) 317 if (inst->type1 != XD3_NOOP && (ret = xd3_decode_parse_halfinst (stream, & stream->dec_current1)))
310 { 318 {
311 return ret; 319 return ret;
@@ -317,11 +325,13 @@ xd3_decode_instruction (xd3_stream *stream)
317 return 0; 325 return 0;
318} 326}
319 327
320/* Output the result of a single half-instruction. OPT: This the decoder hotspot. */ 328/* Output the result of a single half-instruction. OPT: This the
329 decoder hotspot. */
321static int 330static int
322xd3_decode_output_halfinst (xd3_stream *stream, xd3_hinst *inst) 331xd3_decode_output_halfinst (xd3_stream *stream, xd3_hinst *inst)
323{ 332{
324 /* To make this reentrant, set take = min (inst->size, available space)... */ 333 /* To make this reentrant, set take = min (inst->size, available
334 space)... */
325 usize_t take = inst->size; 335 usize_t take = inst->size;
326 336
327 XD3_ASSERT (inst->type != XD3_NOOP); 337 XD3_ASSERT (inst->type != XD3_NOOP);
@@ -370,14 +380,15 @@ xd3_decode_output_halfinst (xd3_stream *stream, xd3_hinst *inst)
370 const uint8_t *src; 380 const uint8_t *src;
371 uint8_t *dst; 381 uint8_t *dst;
372 382
373 /* See if it copies from the VCD_TARGET/VCD_SOURCE window or the target window. 383 /* See if it copies from the VCD_TARGET/VCD_SOURCE window or
374 * Out-of-bounds checks for the addresses and sizes are performed in 384 * the target window. Out-of-bounds checks for the addresses
375 * xd3_decode_parse_halfinst. */ 385 * and sizes are performed in xd3_decode_parse_halfinst. */
376 if (inst->addr < stream->dec_cpylen) 386 if (inst->addr < stream->dec_cpylen)
377 { 387 {
378 if (stream->dec_win_ind & VCD_TARGET) 388 if (stream->dec_win_ind & VCD_TARGET)
379 { 389 {
380 /* For VCD_TARGET we know the entire range is in-memory, as established by 390 /* For VCD_TARGET we know the entire range is
391 * in-memory, as established by
381 * decode_setup_buffers. */ 392 * decode_setup_buffers. */
382 src = stream->dec_cpyaddrbase + inst->addr; 393 src = stream->dec_cpyaddrbase + inst->addr;
383 inst->type = XD3_NOOP; 394 inst->type = XD3_NOOP;
@@ -385,8 +396,9 @@ xd3_decode_output_halfinst (xd3_stream *stream, xd3_hinst *inst)
385 } 396 }
386 else 397 else
387 { 398 {
388 /* In this case we have to read a source block, which could return control 399 /* In this case we have to read a source block, which
389 * to the caller. We need to know the first block number needed for this 400 * could return control to the caller. We need to
401 * know the first block number needed for this
390 * copy. */ 402 * copy. */
391 xd3_source *source; 403 xd3_source *source;
392 xoff_t block; 404 xoff_t block;
@@ -419,8 +431,8 @@ xd3_decode_output_halfinst (xd3_stream *stream, xd3_hinst *inst)
419 431
420 src = source->curblk + blkoff; 432 src = source->curblk + blkoff;
421 433
422 /* This block either contains enough data or the source file is 434 /* This block either contains enough data or the
423 * short. */ 435 * source file is short. */
424 if ((source->onblk != blksize) && (blkoff + take > source->onblk)) 436 if ((source->onblk != blksize) && (blkoff + take > source->onblk))
425 { 437 {
426 stream->msg = "source file too short"; 438 stream->msg = "source file too short";
@@ -437,8 +449,8 @@ xd3_decode_output_halfinst (xd3_stream *stream, xd3_hinst *inst)
437 } 449 }
438 else 450 else
439 { 451 {
440 /* This block doesn't contain all the data, modify the instruction, do 452 /* This block doesn't contain all the data, modify
441 * not set to XD3_NOOP. */ 453 * the instruction, do not set to XD3_NOOP. */
442 take = blksize - blkoff; 454 take = blksize - blkoff;
443 inst->size -= take; 455 inst->size -= take;
444 inst->addr += take; 456 inst->addr += take;
@@ -447,9 +459,10 @@ xd3_decode_output_halfinst (xd3_stream *stream, xd3_hinst *inst)
447 } 459 }
448 else 460 else
449 { 461 {
450 /* For a target-window copy, we know the entire range is in-memory. The 462 /* For a target-window copy, we know the entire range is
451 * dec_tgtaddrbase is negatively offset by dec_cpylen because the addresses 463 * in-memory. The dec_tgtaddrbase is negatively offset by
452 * start beyond that point. */ 464 * dec_cpylen because the addresses start beyond that
465 * point. */
453 src = stream->dec_tgtaddrbase + inst->addr; 466 src = stream->dec_tgtaddrbase + inst->addr;
454 inst->type = XD3_NOOP; 467 inst->type = XD3_NOOP;
455 inst->size = 0; 468 inst->size = 0;
@@ -587,9 +600,10 @@ xd3_decode_sections (xd3_stream *stream)
587 return xd3_decode_finish_window (stream); 600 return xd3_decode_finish_window (stream);
588 } 601 }
589 602
590 /* OPT: A possible optimization is to avoid allocating memory in decode_setup_buffers 603 /* OPT: A possible optimization is to avoid allocating memory in
591 * and to avoid a large memcpy when the window consists of a single VCD_SOURCE copy 604 * decode_setup_buffers and to avoid a large memcpy when the window
592 * instruction. The only potential problem is if the following window is a VCD_TARGET, 605 * consists of a single VCD_SOURCE copy instruction. The only
606 * potential problem is if the following window is a VCD_TARGET,
593 * then you need to remember... */ 607 * then you need to remember... */
594 if ((ret = xd3_decode_setup_buffers (stream))) { return ret; } 608 if ((ret = xd3_decode_setup_buffers (stream))) { return ret; }
595 609
@@ -601,14 +615,16 @@ xd3_decode_emit (xd3_stream *stream)
601{ 615{
602 int ret; 616 int ret;
603 617
604 /* Produce output: originally structured to allow reentrant code that fills as much of 618 /* Produce output: originally structured to allow reentrant code
605 * the output buffer as possible, but VCDIFF semantics allows to copy from anywhere from 619 * that fills as much of the output buffer as possible, but VCDIFF
606 * the target window, so instead allocate a sufficiently sized buffer after the target 620 * semantics allows to copy from anywhere from the target window, so
621 * instead allocate a sufficiently sized buffer after the target
607 * window length is decoded. 622 * window length is decoded.
608 * 623 *
609 * This code still needs to be reentrant to allow XD3_GETSRCBLK to return control. This 624 * This code still needs to be reentrant to allow XD3_GETSRCBLK to
610 * is handled by setting the stream->dec_currentN instruction types to XD3_NOOP after 625 * return control. This is handled by setting the
611 * they have been processed. */ 626 * stream->dec_currentN instruction types to XD3_NOOP after they
627 * have been processed. */
612 XD3_ASSERT (! (stream->flags & XD3_SKIP_EMIT)); 628 XD3_ASSERT (! (stream->flags & XD3_SKIP_EMIT));
613 XD3_ASSERT (stream->dec_tgtlen <= stream->space_out); 629 XD3_ASSERT (stream->dec_tgtlen <= stream->space_out);
614 630
@@ -683,35 +699,39 @@ xd3_decode_input (xd3_stream *stream)
683 return XD3_INVALID_INPUT; 699 return XD3_INVALID_INPUT;
684 } 700 }
685 701
686#define BYTE_CASE(expr,x,nstate) \ 702#define BYTE_CASE(expr,x,nstate) \
687 do { \ 703 do { \
688 if ( (expr) && \ 704 if ( (expr) && \
689 ((ret = xd3_decode_byte (stream, & (x))) != 0) ) { return ret; } \ 705 ((ret = xd3_decode_byte (stream, & (x))) != 0) ) { return ret; } \
690 stream->dec_state = (nstate); \ 706 stream->dec_state = (nstate); \
691 } while (0) 707 } while (0)
692 708
693#define OFFSET_CASE(expr,x,nstate) \ 709#define OFFSET_CASE(expr,x,nstate) \
694 do { \ 710 do { \
695 if ( (expr) && \ 711 if ( (expr) && \
696 ((ret = xd3_decode_offset (stream, & (x))) != 0) ) { return ret; } \ 712 ((ret = xd3_decode_offset (stream, & (x))) != 0) ) { return ret; } \
697 stream->dec_state = (nstate); \ 713 stream->dec_state = (nstate); \
698 } while (0) 714 } while (0)
699 715
700#define SIZE_CASE(expr,x,nstate) \ 716#define SIZE_CASE(expr,x,nstate) \
701 do { \ 717 do { \
702 if ( (expr) && \ 718 if ( (expr) && \
703 ((ret = xd3_decode_size (stream, & (x))) != 0) ) { return ret; } \ 719 ((ret = xd3_decode_size (stream, & (x))) != 0) ) { return ret; } \
704 stream->dec_state = (nstate); \ 720 stream->dec_state = (nstate); \
705 } while (0) 721 } while (0)
706 722
707#define SRCORTGT(x) (((x) & VCD_SRCORTGT) == VCD_SOURCE || \ 723#define SRCORTGT(x) (((x) & VCD_SRCORTGT) == VCD_SOURCE || \
708 ((x) & VCD_SRCORTGT) == VCD_TARGET) 724 ((x) & VCD_SRCORTGT) == VCD_TARGET)
709 725
710 switch (stream->dec_state) 726 switch (stream->dec_state)
711 { 727 {
712 case DEC_VCHEAD: 728 case DEC_VCHEAD:
713 { 729 {
714 if ((ret = xd3_decode_bytes (stream, stream->dec_magic, & stream->dec_magicbytes, 4))) { return ret; } 730 if ((ret = xd3_decode_bytes (stream, stream->dec_magic,
731 & stream->dec_magicbytes, 4)))
732 {
733 return ret;
734 }
715 735
716 if (stream->dec_magic[0] != VCDIFF_MAGIC1 || 736 if (stream->dec_magic[0] != VCDIFF_MAGIC1 ||
717 stream->dec_magic[1] != VCDIFF_MAGIC2 || 737 stream->dec_magic[1] != VCDIFF_MAGIC2 ||
@@ -817,7 +837,8 @@ xd3_decode_input (xd3_stream *stream)
817 /* Application data */ 837 /* Application data */
818 if (stream->dec_hdr_ind & VCD_APPHEADER) 838 if (stream->dec_hdr_ind & VCD_APPHEADER)
819 { 839 {
820 /* Note: we add an additional byte for padding, to allow 0-termination. */ 840 /* Note: we add an additional byte for padding, to allow
841 0-termination. */
821 if ((stream->dec_appheader == NULL) && 842 if ((stream->dec_appheader == NULL) &&
822 (stream->dec_appheader = xd3_alloc (stream, stream->dec_appheadsz+1, 1)) == NULL) { return ENOMEM; } 843 (stream->dec_appheader = xd3_alloc (stream, stream->dec_appheadsz+1, 1)) == NULL) { return ENOMEM; }
823 844
@@ -865,9 +886,10 @@ xd3_decode_input (xd3_stream *stream)
865 /* Copy window length: only if VCD_SOURCE or VCD_TARGET is set */ 886 /* Copy window length: only if VCD_SOURCE or VCD_TARGET is set */
866 SIZE_CASE(SRCORTGT (stream->dec_win_ind), stream->dec_cpylen, DEC_CPYOFF); 887 SIZE_CASE(SRCORTGT (stream->dec_win_ind), stream->dec_cpylen, DEC_CPYOFF);
867 888
868 /* Set the initial, logical decoder position (HERE address) in dec_position. This 889 /* Set the initial, logical decoder position (HERE address) in
869 * is set to just after the source/copy window, as we are just about to output the 890 * dec_position. This is set to just after the source/copy
870 * first byte of target window. */ 891 * window, as we are just about to output the first byte of
892 * target window. */
871 stream->dec_position = stream->dec_cpylen; 893 stream->dec_position = stream->dec_cpylen;
872 894
873 case DEC_CPYOFF: 895 case DEC_CPYOFF:
@@ -881,7 +903,8 @@ xd3_decode_input (xd3_stream *stream)
881 return XD3_INVALID_INPUT; 903 return XD3_INVALID_INPUT;
882 } 904 }
883 905
884 /* Check copy window bounds: VCD_TARGET window may not exceed current position. */ 906 /* Check copy window bounds: VCD_TARGET window may not exceed
907 current position. */
885 if ((stream->dec_win_ind & VCD_TARGET) && 908 if ((stream->dec_win_ind & VCD_TARGET) &&
886 (stream->dec_cpyoff + (xoff_t) stream->dec_cpylen > stream->dec_winstart)) 909 (stream->dec_cpyoff + (xoff_t) stream->dec_cpylen > stream->dec_winstart))
887 { 910 {
@@ -896,9 +919,9 @@ xd3_decode_input (xd3_stream *stream)
896 /* Length of target window */ 919 /* Length of target window */
897 SIZE_CASE(1, stream->dec_tgtlen, DEC_DELIND); 920 SIZE_CASE(1, stream->dec_tgtlen, DEC_DELIND);
898 921
899 /* Set the maximum decoder position, beyond which we should not decode any data. 922 /* Set the maximum decoder position, beyond which we should not
900 * This is the maximum value for dec_position. This may not exceed the size of a 923 * decode any data. This is the maximum value for dec_position.
901 * usize_t. */ 924 * This may not exceed the size of a usize_t. */
902 if (USIZE_T_OVERFLOW (stream->dec_cpylen, stream->dec_tgtlen)) 925 if (USIZE_T_OVERFLOW (stream->dec_cpylen, stream->dec_tgtlen))
903 { 926 {
904 stream->msg = "decoder target window overflows a usize_t"; 927 stream->msg = "decoder target window overflows a usize_t";
@@ -973,8 +996,8 @@ xd3_decode_input (xd3_stream *stream)
973 } 996 }
974 } 997 }
975 998
976 /* Returning here gives the application a chance to inspect the header, skip the 999 /* Returning here gives the application a chance to inspect the
977 * window, etc. */ 1000 * header, skip the window, etc. */
978 if (stream->current_window == 0) { return XD3_GOTHEADER; } 1001 if (stream->current_window == 0) { return XD3_GOTHEADER; }
979 else { return XD3_WINSTART; } 1002 else { return XD3_WINSTART; }
980 1003
@@ -986,8 +1009,8 @@ xd3_decode_input (xd3_stream *stream)
986 1009
987 case DEC_EMIT: 1010 case DEC_EMIT:
988 1011
989 /* To speed VCD_SOURCE block-address calculations, the source cpyoff_blocks and 1012 /* To speed VCD_SOURCE block-address calculations, the source
990 * cpyoff_blkoff are pre-computed. */ 1013 * cpyoff_blocks and cpyoff_blkoff are pre-computed. */
991 if (stream->dec_win_ind & VCD_SOURCE) 1014 if (stream->dec_win_ind & VCD_SOURCE)
992 { 1015 {
993 xd3_source *src = stream->src; 1016 xd3_source *src = stream->src;
@@ -1030,8 +1053,8 @@ xd3_decode_input (xd3_stream *stream)
1030 stream->dec_laststart = stream->dec_winstart; 1053 stream->dec_laststart = stream->dec_winstart;
1031 stream->dec_window_count += 1; 1054 stream->dec_window_count += 1;
1032 1055
1033 /* Note: the updates to dec_winstart & current_window are deferred until after the 1056 /* Note: the updates to dec_winstart & current_window are
1034 * next DEC_WININD byte is read. */ 1057 * deferred until after the next DEC_WININD byte is read. */
1035 stream->dec_state = DEC_WININD; 1058 stream->dec_state = DEC_WININD;
1036 return XD3_WINFINISH; 1059 return XD3_WINFINISH;
1037 } 1060 }
diff --git a/xdelta3/xdelta3-djw.h b/xdelta3/xdelta3-djw.h
index a9f6e6f..2623e63 100644
--- a/xdelta3/xdelta3-djw.h
+++ b/xdelta3/xdelta3-djw.h
@@ -601,7 +601,10 @@ djw_count_freqs (djw_weight *freq, xd3_output *input)
601 601
602 IF_DEBUG1 ({int i; 602 IF_DEBUG1 ({int i;
603 DP(RINT "freqs: "); 603 DP(RINT "freqs: ");
604 for (i = 0; i < ALPHABET_SIZE; i += 1) { DP(RINT "%u ", freq[i]); } 604 for (i = 0; i < ALPHABET_SIZE; i += 1)
605 {
606 DP(RINT "%u ", freq[i]);
607 }
605 DP(RINT "\n");}); 608 DP(RINT "\n");});
606 609
607 return size; 610 return size;
diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h
index 4d642df..bb06a13 100644
--- a/xdelta3/xdelta3-main.h
+++ b/xdelta3/xdelta3-main.h
@@ -555,10 +555,10 @@ main_format_bcnt (xoff_t r, char *buf)
555 for (i = 0; i < SIZEOF_ARRAY(fmts); i += 1) 555 for (i = 0; i < SIZEOF_ARRAY(fmts); i += 1)
556 { 556 {
557 if (r <= (10 * 1024) || i == (-1 + (int)SIZEOF_ARRAY(fmts))) 557 if (r <= (10 * 1024) || i == (-1 + (int)SIZEOF_ARRAY(fmts)))
558 { 558 {
559 sprintf (buf, "%"Q"u %s", r, fmts[i]); 559 sprintf (buf, "%"Q"u %s", r, fmts[i]);
560 break; 560 break;
561 } 561 }
562 r /= 1024; 562 r /= 1024;
563 } 563 }
564 return buf; 564 return buf;
@@ -2436,7 +2436,7 @@ main_getblk_func (xd3_stream *stream,
2436 xoff_t pos = blkno * source->blksize; 2436 xoff_t pos = blkno * source->blksize;
2437 main_file *sfile = (main_file*) source->ioh; 2437 main_file *sfile = (main_file*) source->ioh;
2438 main_blklru *blru = NULL; 2438 main_blklru *blru = NULL;
2439 usize_t onblk = xd3_bytes_on_srcblk (source, blkno); 2439 usize_t onblk = xd3_bytes_on_srcblk_fast (source, blkno);
2440 usize_t nread; 2440 usize_t nread;
2441 int ret; 2441 int ret;
2442 int i; 2442 int i;
diff --git a/xdelta3/xdelta3-test.h b/xdelta3/xdelta3-test.h
index 0739e2d..a2d762a 100644
--- a/xdelta3/xdelta3-test.h
+++ b/xdelta3/xdelta3-test.h
@@ -49,12 +49,13 @@ static int test_exponential_dist (usize_t mean, usize_t max);
49 49
50#define CHECK(cond) if (!(cond)) { DP(RINT "check failure: " #cond); abort(); } 50#define CHECK(cond) if (!(cond)) { DP(RINT "check failure: " #cond); abort(); }
51 51
52/* Use a fixed soft config so that test values are fixed. See also test_compress_text(). */ 52/* Use a fixed soft config so that test values are fixed. See also
53 test_compress_text(). */
53static const char* test_softcfg_str = "-C64,64,4,128,16,8,128"; 54static const char* test_softcfg_str = "-C64,64,4,128,16,8,128";
54 55
55/****************************************************************************************** 56/***********************************************************************
56 TEST HELPERS 57 TEST HELPERS
57 ******************************************************************************************/ 58 ***********************************************************************/
58 59
59static void DOT (void) { DP(RINT "."); } 60static void DOT (void) { DP(RINT "."); }
60static int do_cmd (xd3_stream *stream, const char *buf) 61static int do_cmd (xd3_stream *stream, const char *buf)
@@ -193,9 +194,10 @@ test_make_inputs (xd3_stream *stream, xoff_t *ss_out, xoff_t *ts_out)
193 goto failure; 194 goto failure;
194 } 195 }
195 196
196 /* Then modify the data to produce copies, everything not copied is an add. The 197 /* Then modify the data to produce copies, everything not copied is
197 * following logic produces the TEST_ADD_RATIO. The variable SADD contains the number 198 * an add. The following logic produces the TEST_ADD_RATIO. The
198 * of adds so far, which should not exceed SADD_MAX. */ 199 * variable SADD contains the number of adds so far, which should
200 * not exceed SADD_MAX. */
199 for (i = 0; i < ss; ) 201 for (i = 0; i < ss; )
200 { 202 {
201 usize_t left = ss - i; 203 usize_t left = ss - i;
@@ -350,13 +352,14 @@ test_file_size (const char* file, xoff_t *size)
350 return 0; 352 return 0;
351} 353}
352 354
353/****************************************************************************************** 355/***********************************************************************
354 READ OFFSET 356 READ OFFSET
355 ******************************************************************************************/ 357 ***********************************************************************/
356 358
357/* Common test for read_integer errors: encodes a 64-bit value and then attempts to read 359/* Common test for read_integer errors: encodes a 64-bit value and
358 * as a 32-bit value. If TRUNC is non-zero, attempts to get errors by shortening the 360 * then attempts to read as a 32-bit value. If TRUNC is non-zero,
359 * input, otherwise it should overflow. Expects XD3_INTERNAL and MSG. */ 361 * attempts to get errors by shortening the input, otherwise it should
362 * overflow. Expects XD3_INTERNAL and MSG. */
360static int 363static int
361test_read_integer_error (xd3_stream *stream, int trunto, const char *msg) 364test_read_integer_error (xd3_stream *stream, int trunto, const char *msg)
362{ 365{
@@ -538,9 +541,9 @@ test_usize_t_overflow (xd3_stream *stream, int unused)
538 return XD3_INTERNAL; 541 return XD3_INTERNAL;
539} 542}
540 543
541/****************************************************************************************** 544/***********************************************************************
542 Address cache 545 Address cache
543 ******************************************************************************************/ 546 ***********************************************************************/
544 547
545static int 548static int
546test_address_cache (xd3_stream *stream, int unused) 549test_address_cache (xd3_stream *stream, int unused)
@@ -644,9 +647,9 @@ test_address_cache (xd3_stream *stream, int unused)
644 return 0; 647 return 0;
645} 648}
646 649
647/****************************************************************************************** 650/***********************************************************************
648 Encode and decode with single bit error 651 Encode and decode with single bit error
649 ******************************************************************************************/ 652 ***********************************************************************/
650 653
651/* It compresses from 256 to around 185 bytes. 654/* It compresses from 256 to around 185 bytes.
652 * Avoids matching addresses that are a single-bit difference. 655 * Avoids matching addresses that are a single-bit difference.
@@ -814,9 +817,10 @@ test_decompress_single_bit_error (xd3_stream *stream, int expected_non_failures)
814#if 1 817#if 1
815#define TEST_FAILURES() 818#define TEST_FAILURES()
816#else 819#else
817 /* For checking non-failure cases by hand, enable this macro and run xdelta printdelta 820 /* For checking non-failure cases by hand, enable this macro and run
818 * with print_cpymode enabled. Every non-failure should change a copy address mode, 821 * xdelta printdelta with print_cpymode enabled. Every non-failure
819 * which doesn't cause a failure because the address cache starts out with all zeros. 822 * should change a copy address mode, which doesn't cause a failure
823 * because the address cache starts out with all zeros.
820 824
821 ./xdelta3 test 825 ./xdelta3 test
822 for i in test_text.xz.*; do ./xdelta3 printdelta $i > $i.out; diff $i.out test_text.xz.0.out; done 826 for i in test_text.xz.*; do ./xdelta3 printdelta $i > $i.out; diff $i.out test_text.xz.0.out; done
@@ -909,9 +913,9 @@ test_decompress_single_bit_error (xd3_stream *stream, int expected_non_failures)
909 return 0; 913 return 0;
910} 914}
911 915
912/****************************************************************************************** 916/***********************************************************************
913 Secondary compression tests 917 Secondary compression tests
914 ******************************************************************************************/ 918 ***********************************************************************/
915 919
916#if SECONDARY_ANY 920#if SECONDARY_ANY
917typedef int (*sec_dist_func) (xd3_stream *stream, xd3_output *data); 921typedef int (*sec_dist_func) (xd3_stream *stream, xd3_output *data);
@@ -1031,8 +1035,8 @@ sec_dist_func7 (xd3_stream *stream, xd3_output *data)
1031 return 0; 1035 return 0;
1032} 1036}
1033 1037
1034/* Test distribution: A small number of frequent characters, difficult to divide into many 1038/* Test distribution: A small number of frequent characters, difficult
1035 * groups */ 1039 * to divide into many groups */
1036static int 1040static int
1037sec_dist_func8 (xd3_stream *stream, xd3_output *data) 1041sec_dist_func8 (xd3_stream *stream, xd3_output *data)
1038{ 1042{
@@ -1058,9 +1062,9 @@ sec_dist_func9 (xd3_stream *stream, xd3_output *data)
1058 int prom = 0; 1062 int prom = 0;
1059 int pcount = 0; 1063 int pcount = 0;
1060 1064
1061 /* 200 was long enough to trigger it--only when stricter checking that counted all 1065 /* 200 was long enough to trigger it--only when stricter checking
1062 * blocks was turned on, but it seems I deleted this code. (missing fgk_free_block on 1066 * that counted all blocks was turned on, but it seems I deleted
1063 * line 398). */ 1067 * this code. (missing fgk_free_block on line 398). */
1064 for (i = 0; i < ALPHABET_SIZE*200; i += 1) 1068 for (i = 0; i < ALPHABET_SIZE*200; i += 1)
1065 { 1069 {
1066 repeat: 1070 repeat:
@@ -1259,9 +1263,10 @@ test_secondary (xd3_stream *stream, const xd3_sec_type *sec, int groups)
1259 goto fail; 1263 goto fail;
1260 } 1264 }
1261 1265
1262 /* Single-bit error test, only cover the first 10 bytes. Some non-failures are 1266 /* Single-bit error test, only cover the first 10 bytes.
1263 * expected in the Huffman case: Changing the clclen array, for example, may not 1267 * Some non-failures are expected in the Huffman case:
1264 * harm the decoding. Really looking for faults here. */ 1268 * Changing the clclen array, for example, may not harm the
1269 * decoding. Really looking for faults here. */
1265 { 1270 {
1266 int i; 1271 int i;
1267 int bytes = min (compress_size, 10U); 1272 int bytes = min (compress_size, 10U);
@@ -1310,9 +1315,9 @@ IF_DJW (static int test_secondary_huff (xd3_stream *stream, int gp)
1310 { return test_secondary (stream, & djw_sec_type, gp); }) 1315 { return test_secondary (stream, & djw_sec_type, gp); })
1311#endif 1316#endif
1312 1317
1313/****************************************************************************************** 1318/***********************************************************************
1314 TEST INSTRUCTION TABLE 1319 TEST INSTRUCTION TABLE
1315 ******************************************************************************************/ 1320 ***********************************************************************/
1316 1321
1317/* Test that xd3_choose_instruction() does the right thing for its code table. */ 1322/* Test that xd3_choose_instruction() does the right thing for its code table. */
1318static int 1323static int
@@ -1369,9 +1374,9 @@ test_choose_instruction (xd3_stream *stream, int ignore)
1369 return 0; 1374 return 0;
1370} 1375}
1371 1376
1372/****************************************************************************************** 1377/***********************************************************************
1373 TEST INSTRUCTION TABLE CODING 1378 TEST INSTRUCTION TABLE CODING
1374 ******************************************************************************************/ 1379 ***********************************************************************/
1375 1380
1376#if GENERIC_ENCODE_TABLES 1381#if GENERIC_ENCODE_TABLES
1377/* Test that encoding and decoding a code table works */ 1382/* Test that encoding and decoding a code table works */
@@ -1405,12 +1410,13 @@ test_encode_code_table (xd3_stream *stream, int ignore)
1405} 1410}
1406#endif 1411#endif
1407 1412
1408/****************************************************************************************** 1413/***********************************************************************
1409 64BIT STREAMING 1414 64BIT STREAMING
1410 ******************************************************************************************/ 1415 ***********************************************************************/
1411 1416
1412/* This test encodes and decodes a series of 1 megabyte windows, each containing a long 1417/* This test encodes and decodes a series of 1 megabyte windows, each
1413 * run of zeros along with a single xoff_t size record to indicate the sequence. */ 1418 * containing a long run of zeros along with a single xoff_t size
1419 * record to indicate the sequence. */
1414static int 1420static int
1415test_streaming (xd3_stream *in_stream, uint8_t *encbuf, uint8_t *decbuf, uint8_t *delbuf, usize_t megs) 1421test_streaming (xd3_stream *in_stream, uint8_t *encbuf, uint8_t *decbuf, uint8_t *delbuf, usize_t megs)
1416{ 1422{
@@ -1503,14 +1509,16 @@ test_compressed_stream_overflow (xd3_stream *stream, int ignore)
1503 return ret; 1509 return ret;
1504} 1510}
1505 1511
1506/****************************************************************************************** 1512/***********************************************************************
1507 COMMAND LINE 1513 COMMAND LINE
1508 ******************************************************************************************/ 1514 ***********************************************************************/
1509 1515
1510/* For each pair of command templates in the array below, test that encoding and decoding 1516/* For each pair of command templates in the array below, test that
1511 * commands work. Also check for the expected size delta, which should be approximately 1517 * encoding and decoding commands work. Also check for the expected
1512 * TEST_ADD_RATIO times the file size created by test_make_inputs. Due to differences in 1518 * size delta, which should be approximately TEST_ADD_RATIO times the
1513 * the application header, it is suppressed (-A) so that all delta files are the same. */ 1519 * file size created by test_make_inputs. Due to differences in the
1520 * application header, it is suppressed (-A) so that all delta files
1521 * are the same. */
1514static int 1522static int
1515test_command_line_arguments (xd3_stream *stream, int ignore) 1523test_command_line_arguments (xd3_stream *stream, int ignore)
1516{ 1524{
@@ -1616,14 +1624,15 @@ test_command_line_arguments (xd3_stream *stream, int ignore)
1616 return 0; 1624 return 0;
1617} 1625}
1618 1626
1619/****************************************************************************************** 1627/***********************************************************************
1620 EXTERNAL I/O DECOMPRESSION/RECOMPRESSION 1628 EXTERNAL I/O DECOMPRESSION/RECOMPRESSION
1621 ******************************************************************************************/ 1629 ***********************************************************************/
1622 1630
1623#if EXTERNAL_COMPRESSION 1631#if EXTERNAL_COMPRESSION
1624/* This performs one step of the test_externally_compressed_io function described below. 1632/* This performs one step of the test_externally_compressed_io
1625 * It builds a pipe containing both Xdelta and external compression/decompression that 1633 * function described below. It builds a pipe containing both Xdelta
1626 * should not modify the data passing through. */ 1634 * and external compression/decompression that should not modify the
1635 * data passing through. */
1627static int 1636static int
1628test_compressed_pipe (xd3_stream *stream, main_extcomp *ext, char* buf, 1637test_compressed_pipe (xd3_stream *stream, main_extcomp *ext, char* buf,
1629 const char* comp_options, const char* decomp_options, 1638 const char* comp_options, const char* decomp_options,
@@ -1668,11 +1677,12 @@ test_compressed_pipe (xd3_stream *stream, main_extcomp *ext, char* buf,
1668 * 1677 *
1669 * --> | gzip -cf | xdelta3 -cf | xdelta3 -dcf | gzip -dcf | --> 1678 * --> | gzip -cf | xdelta3 -cf | xdelta3 -dcf | gzip -dcf | -->
1670 * 1679 *
1671 * is transparent, i.e., does not modify the stream of data. However, we also want to 1680 * is transparent, i.e., does not modify the stream of data. However,
1672 * verify that at the center the data is properly compressed, i.e., that we do not just 1681 * we also want to verify that at the center the data is properly
1673 * have a re-compressed gzip format, that we have an VCDIFF format. We do this in two 1682 * compressed, i.e., that we do not just have a re-compressed gzip
1674 * steps. First test the above pipe, then test with suppressed output recompression 1683 * format, that we have an VCDIFF format. We do this in two steps.
1675 * (-D). The result should be the original input: 1684 * First test the above pipe, then test with suppressed output
1685 * recompression (-D). The result should be the original input:
1676 * 1686 *
1677 * --> | gzip -cf | xdelta3 -cf | xdelta3 -Ddcf | --> 1687 * --> | gzip -cf | xdelta3 -cf | xdelta3 -Ddcf | -->
1678 * 1688 *
@@ -1717,14 +1727,17 @@ test_externally_compressed_io (xd3_stream *stream, int ignore)
1717 return 0; 1727 return 0;
1718} 1728}
1719 1729
1720/* This tests the proper functioning of external decompression for source files. The 1730/* This tests the proper functioning of external decompression for
1721 * source and target files are identical and compressed by gzip. Decoding such a delta 1731 * source files. The source and target files are identical and
1722 * with recompression disbaled (-R) should produce the original, uncompressed 1732 * compressed by gzip. Decoding such a delta with recompression
1723 * source/target file. Then it checks with output recompression enabled--in this case the 1733 * disbaled (-R) should produce the original, uncompressed
1724 * output should be a compressed copy of the original source/target file. Then it checks 1734 * source/target file. Then it checks with output recompression
1725 * that encoding with decompression disabled works--the compressed files are identical and 1735 * enabled--in this case the output should be a compressed copy of the
1726 * decoding them should always produce a compressed output, regardless of -R since the 1736 * original source/target file. Then it checks that encoding with
1727 * encoded delta file had decompression disabled.. 1737 * decompression disabled works--the compressed files are identical
1738 * and decoding them should always produce a compressed output,
1739 * regardless of -R since the encoded delta file had decompression
1740 * disabled..
1728 */ 1741 */
1729static int 1742static int
1730test_source_decompression (xd3_stream *stream, int ignore) 1743test_source_decompression (xd3_stream *stream, int ignore)
@@ -1789,12 +1802,13 @@ test_source_decompression (xd3_stream *stream, int ignore)
1789} 1802}
1790#endif 1803#endif
1791 1804
1792/****************************************************************************************** 1805/***********************************************************************
1793 FORCE, STDOUT 1806 FORCE, STDOUT
1794 ******************************************************************************************/ 1807 ***********************************************************************/
1795 1808
1796/* This tests that output will not overwrite an existing file unless -f was specified. 1809/* This tests that output will not overwrite an existing file unless
1797 * The test is for encoding (the same code handles it for decoding). */ 1810 * -f was specified. The test is for encoding (the same code handles
1811 * it for decoding). */
1798static int 1812static int
1799test_force_behavior (xd3_stream *stream, int ignore) 1813test_force_behavior (xd3_stream *stream, int ignore)
1800{ 1814{
@@ -1821,9 +1835,9 @@ test_force_behavior (xd3_stream *stream, int ignore)
1821 return 0; 1835 return 0;
1822} 1836}
1823 1837
1824/* This checks the proper operation of the -c flag. When specified the default output 1838/* This checks the proper operation of the -c flag. When specified
1825 * becomes stdout, otherwise the input must be provided (encode) or it may be defaulted 1839 * the default output becomes stdout, otherwise the input must be
1826 * (decode w/ app header). */ 1840 * provided (encode) or it may be defaulted (decode w/ app header). */
1827static int 1841static int
1828test_stdout_behavior (xd3_stream *stream, int ignore) 1842test_stdout_behavior (xd3_stream *stream, int ignore)
1829{ 1843{
@@ -1886,13 +1900,14 @@ test_no_output (xd3_stream *stream, int ignore)
1886 return 0; 1900 return 0;
1887} 1901}
1888 1902
1889/****************************************************************************************** 1903/***********************************************************************
1890 Source identical optimization 1904 Source identical optimization
1891 ******************************************************************************************/ 1905 ***********************************************************************/
1892 1906
1893/* Computing a delta should be fastest when the two inputs are identical, this checks it. 1907/* Computing a delta should be fastest when the two inputs are
1894 * The library is called to compute a delta between a 10000 byte file, 1000 byte winsize, 1908 * identical, this checks it. The library is called to compute a
1895 * 500 byte source blocksize. The same buffer is used for both source and target. */ 1909 * delta between a 10000 byte file, 1000 byte winsize, 500 byte source
1910 * blocksize. The same buffer is used for both source and target. */
1896static int 1911static int
1897test_identical_behavior (xd3_stream *stream, int ignore) 1912test_identical_behavior (xd3_stream *stream, int ignore)
1898{ 1913{
@@ -1907,7 +1922,9 @@ test_identical_behavior (xd3_stream *stream, int ignore)
1907 uint8_t del[IDB_DELSZ]; 1922 uint8_t del[IDB_DELSZ];
1908 uint8_t rec[IDB_TGTSZ]; 1923 uint8_t rec[IDB_TGTSZ];
1909 xd3_source source; 1924 xd3_source source;
1910 int encwin = 0; 1925 int nextencwin = 0;
1926 int winstarts = 0, winfinishes = 0;
1927 xoff_t srcwin = -1;
1911 usize_t delpos = 0, recsize; 1928 usize_t delpos = 0, recsize;
1912 xd3_config config; 1929 xd3_config config;
1913 1930
@@ -1930,9 +1947,8 @@ test_identical_behavior (xd3_stream *stream, int ignore)
1930 1947
1931 if (ret == XD3_INPUT) 1948 if (ret == XD3_INPUT)
1932 { 1949 {
1933 if (encwin == IDB_WINCNT-1) { break; } 1950 xd3_avail_input (stream, buf + (IDB_WINSZ * nextencwin), IDB_WINSZ);
1934 xd3_avail_input (stream, buf + (IDB_WINSZ * encwin), IDB_WINSZ); 1951 nextencwin += 1;
1935 encwin += 1;
1936 continue; 1952 continue;
1937 } 1953 }
1938 1954
@@ -1941,11 +1957,24 @@ test_identical_behavior (xd3_stream *stream, int ignore)
1941 source.curblkno = source.getblkno; 1957 source.curblkno = source.getblkno;
1942 source.onblk = IDB_BLKSZ; 1958 source.onblk = IDB_BLKSZ;
1943 source.curblk = buf + source.getblkno * IDB_BLKSZ; 1959 source.curblk = buf + source.getblkno * IDB_BLKSZ;
1960 srcwin = source.getblkno;
1944 continue; 1961 continue;
1945 } 1962 }
1946 1963
1947 if (ret == XD3_WINSTART) { continue; } 1964 if (ret == XD3_WINSTART)
1948 if (ret == XD3_WINFINISH) { continue; } 1965 {
1966 winstarts++;
1967 continue;
1968 }
1969 if (ret == XD3_WINFINISH)
1970 {
1971 winfinishes++;
1972 if (winfinishes == IDB_WINCNT)
1973 {
1974 break;
1975 }
1976 continue;
1977 }
1949 1978
1950 if (ret != XD3_OUTPUT) { goto fail; } 1979 if (ret != XD3_OUTPUT) { goto fail; }
1951 1980
@@ -1958,6 +1987,11 @@ test_identical_behavior (xd3_stream *stream, int ignore)
1958 xd3_consume_output (stream); 1987 xd3_consume_output (stream);
1959 } 1988 }
1960 1989
1990 XD3_ASSERT(srcwin == source.blocks - 1);
1991 XD3_ASSERT(winfinishes == IDB_WINCNT);
1992 XD3_ASSERT(winstarts == IDB_WINCNT);
1993 XD3_ASSERT(nextencwin == IDB_WINCNT);
1994
1961 /* Reset. */ 1995 /* Reset. */
1962 source.blksize = IDB_TGTSZ; 1996 source.blksize = IDB_TGTSZ;
1963 source.onblk = IDB_TGTSZ; 1997 source.onblk = IDB_TGTSZ;
@@ -1982,7 +2016,8 @@ test_identical_behavior (xd3_stream *stream, int ignore)
1982 stream->n_add != 0 || 2016 stream->n_add != 0 ||
1983 stream->n_run != 0) { stream->msg = "wrong copy count"; goto fail; }); 2017 stream->n_run != 0) { stream->msg = "wrong copy count"; goto fail; });
1984 2018
1985 /* Check that no checksums were computed because the initial match was presumed. */ 2019 /* Check that no checksums were computed because the initial match
2020 was presumed. */
1986 IF_DEBUG (if (stream->large_ckcnt != 0) { stream->msg = "wrong checksum behavior"; goto fail; }); 2021 IF_DEBUG (if (stream->large_ckcnt != 0) { stream->msg = "wrong checksum behavior"; goto fail; });
1987 2022
1988 ret = 0; 2023 ret = 0;
@@ -1990,12 +2025,12 @@ test_identical_behavior (xd3_stream *stream, int ignore)
1990 return ret; 2025 return ret;
1991} 2026}
1992 2027
1993/****************************************************************************************** 2028/***********************************************************************
1994 String matching test 2029 String matching test
1995 ******************************************************************************************/ 2030 ***********************************************************************/
1996 2031
1997/* Check particular matching behaviors by calling xd3_string_match_soft directly with 2032/* Check particular matching behaviors by calling
1998 * specific arguments. */ 2033 * xd3_string_match_soft directly with specific arguments. */
1999typedef struct _string_match_test string_match_test; 2034typedef struct _string_match_test string_match_test;
2000 2035
2001typedef enum 2036typedef enum
@@ -2285,9 +2320,9 @@ test_in_memory (xd3_stream *stream, int ignore)
2285 return 0; 2320 return 0;
2286} 2321}
2287 2322
2288/****************************************************************************************** 2323/***********************************************************************
2289 TEST MAIN 2324 TEST MAIN
2290 ******************************************************************************************/ 2325 ***********************************************************************/
2291 2326
2292static int 2327static int
2293xd3_selftest (void) 2328xd3_selftest (void)
@@ -2322,13 +2357,13 @@ xd3_selftest (void)
2322 IF_GENCODETBL (DO_TEST (address_cache, XD3_ALT_CODE_TABLE, 0)); 2357 IF_GENCODETBL (DO_TEST (address_cache, XD3_ALT_CODE_TABLE, 0));
2323 2358
2324 DO_TEST (string_matching, 0, 0); 2359 DO_TEST (string_matching, 0, 0);
2325
2326 DO_TEST (choose_instruction, 0, 0); 2360 DO_TEST (choose_instruction, 0, 0);
2361 DO_TEST (identical_behavior, 0, 0);
2362 DO_TEST (in_memory, 0, 0);
2363
2327 IF_GENCODETBL (DO_TEST (choose_instruction, XD3_ALT_CODE_TABLE, 0)); 2364 IF_GENCODETBL (DO_TEST (choose_instruction, XD3_ALT_CODE_TABLE, 0));
2328 IF_GENCODETBL (DO_TEST (encode_code_table, 0, 0)); 2365 IF_GENCODETBL (DO_TEST (encode_code_table, 0, 0));
2329 2366
2330 DO_TEST (in_memory, 0, 0);
2331 DO_TEST (identical_behavior, 0, 0);
2332 DO_TEST (iopt_flush_instructions, 0, 0); 2367 DO_TEST (iopt_flush_instructions, 0, 0);
2333 DO_TEST (source_cksum_offset, 0, 0); 2368 DO_TEST (source_cksum_offset, 0, 0);
2334 2369
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index 0381206..58fb8b5 100644
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -268,9 +268,9 @@
268 268
269#include "xdelta3.h" 269#include "xdelta3.h"
270 270
271/****************************************************************************************** 271/***********************************************************************
272 STATIC CONFIGURATION 272 STATIC CONFIGURATION
273 ******************************************************************************************/ 273 ***********************************************************************/
274 274
275#ifndef XD3_MAIN /* the main application */ 275#ifndef XD3_MAIN /* the main application */
276#define XD3_MAIN 0 276#define XD3_MAIN 0
@@ -304,7 +304,7 @@
304#define IF_ENCODER(x) 304#define IF_ENCODER(x)
305#endif 305#endif
306 306
307/******************************************************************************************/ 307/***********************************************************************/
308 308
309typedef enum { 309typedef enum {
310 310
@@ -354,13 +354,13 @@ typedef enum
354 XD3_CPY = 3, /* XD3_CPY rtypes are represented as (XD3_CPY + copy-mode value) */ 354 XD3_CPY = 3, /* XD3_CPY rtypes are represented as (XD3_CPY + copy-mode value) */
355} xd3_rtype; 355} xd3_rtype;
356 356
357/******************************************************************************************/ 357/***********************************************************************/
358 358
359#include "xdelta3-list.h" 359#include "xdelta3-list.h"
360 360
361XD3_MAKELIST(xd3_rlist, xd3_rinst, link); 361XD3_MAKELIST(xd3_rlist, xd3_rinst, link);
362 362
363/******************************************************************************************/ 363/***********************************************************************/
364 364
365#ifndef unlikely /* The unlikely macro - any good? */ 365#ifndef unlikely /* The unlikely macro - any good? */
366#if defined(__GNUC__) && __GNUC__ >= 3 366#if defined(__GNUC__) && __GNUC__ >= 3
@@ -536,7 +536,7 @@ IF_BUILD_DEFAULT(static const xd3_smatcher __smatcher_default;)
536#define IF_REGRESSION(x) 536#define IF_REGRESSION(x)
537#endif 537#endif
538 538
539/******************************************************************************************/ 539/***********************************************************************/
540 540
541#if XD3_ENCODER 541#if XD3_ENCODER
542static void* xd3_alloc0 (xd3_stream *stream, 542static void* xd3_alloc0 (xd3_stream *stream,
@@ -565,6 +565,7 @@ static int xd3_emit_double (xd3_stream *stream, xd3_rinst *first, xd3_ri
565static int xd3_emit_single (xd3_stream *stream, xd3_rinst *single, uint code); 565static int xd3_emit_single (xd3_stream *stream, xd3_rinst *single, uint code);
566 566
567static usize_t xd3_sizeof_output (xd3_output *output); 567static usize_t xd3_sizeof_output (xd3_output *output);
568static void xd3_encode_reset (xd3_stream *stream);
568 569
569static int xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos); 570static int xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos);
570static int xd3_source_extend_match (xd3_stream *stream); 571static int xd3_source_extend_match (xd3_stream *stream);
@@ -588,7 +589,7 @@ static int xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp,
588static int xd3_selftest (void); 589static int xd3_selftest (void);
589#endif 590#endif
590 591
591/******************************************************************************************/ 592/***********************************************************************/
592 593
593#define UINT32_OFLOW_MASK 0xfe000000U 594#define UINT32_OFLOW_MASK 0xfe000000U
594#define UINT64_OFLOW_MASK 0xfe00000000000000ULL 595#define UINT64_OFLOW_MASK 0xfe00000000000000ULL
@@ -644,7 +645,7 @@ const char* xd3_strerror (int ret)
644 return NULL; 645 return NULL;
645} 646}
646 647
647/******************************************************************************************/ 648/***********************************************************************/
648 649
649#if SECONDARY_ANY == 0 650#if SECONDARY_ANY == 0
650#define IF_SEC(x) 651#define IF_SEC(x)
@@ -707,7 +708,7 @@ static const xd3_sec_type djw_sec_type =
707 return XD3_INTERNAL; 708 return XD3_INTERNAL;
708#endif 709#endif
709 710
710/******************************************************************************************/ 711/***********************************************************************/
711 712
712/* Process the inline pass. */ 713/* Process the inline pass. */
713#define __XDELTA3_C_INLINE_PASS__ 714#define __XDELTA3_C_INLINE_PASS__
@@ -734,9 +735,9 @@ static const xd3_sec_type djw_sec_type =
734#endif /* __XDELTA3_C_HEADER_PASS__ */ 735#endif /* __XDELTA3_C_HEADER_PASS__ */
735#ifdef __XDELTA3_C_INLINE_PASS__ 736#ifdef __XDELTA3_C_INLINE_PASS__
736 737
737/****************************************************************************************** 738/****************************************************************
738 Instruction tables 739 Instruction tables
739 ******************************************************************************************/ 740 *****************************************************************/
740 741
741/* The following code implements a parametrized description of the 742/* The following code implements a parametrized description of the
742 * code table given above for a few reasons. It is not necessary for 743 * code table given above for a few reasons. It is not necessary for
@@ -969,9 +970,10 @@ xd3_alternate_code_table (void)
969 return __alternate_code_table; 970 return __alternate_code_table;
970} 971}
971 972
972/* This function computes the ideal second instruction INST based on preceding instruction 973/* This function computes the ideal second instruction INST based on
973 * PREV. If it is possible to issue a double instruction based on this pair it sets 974 * preceding instruction PREV. If it is possible to issue a double
974 * PREV->code2, otherwise it sets INST->code1. */ 975 * instruction based on this pair it sets PREV->code2, otherwise it
976 * sets INST->code1. */
975static void 977static void
976xd3_choose_instruction (const xd3_code_table_desc *desc, xd3_rinst *prev, xd3_rinst *inst) 978xd3_choose_instruction (const xd3_code_table_desc *desc, xd3_rinst *prev, xd3_rinst *inst)
977{ 979{
@@ -999,17 +1001,19 @@ xd3_choose_instruction (const xd3_code_table_desc *desc, xd3_rinst *prev, xd3_ri
999 { 1001 {
1000 int prev_mode = prev->type - XD3_CPY; 1002 int prev_mode = prev->type - XD3_CPY;
1001 1003
1002 /* If previous is a copy. Note: as long as the previous is not a RUN 1004 /* If previous is a copy. Note: as long as the previous
1003 * instruction, it should be a copy because it cannot be an add. This check 1005 * is not a RUN instruction, it should be a copy because
1004 * is more clear. */ 1006 * it cannot be an add. This check is more clear. */
1005 if (prev_mode >= 0 && inst->size <= desc->copyadd_add_max) 1007 if (prev_mode >= 0 && inst->size <= desc->copyadd_add_max)
1006 { 1008 {
1007 const xd3_code_table_sizes *sizes = & desc->copyadd_max_sizes[prev_mode]; 1009 const xd3_code_table_sizes *sizes = & desc->copyadd_max_sizes[prev_mode];
1008 1010
1009 /* This check and the inst->size-<= above are == in the default table. */ 1011 /* This check and the inst->size-<= above are == in
1012 the default table. */
1010 if (prev->size <= sizes->cpy_max) 1013 if (prev->size <= sizes->cpy_max)
1011 { 1014 {
1012 /* The second and third exprs are 0 in the default table. */ 1015 /* The second and third exprs are 0 in the
1016 default table. */
1013 prev->code2 = sizes->offset + (sizes->mult * (prev->size - MIN_MATCH)) + (inst->size - MIN_ADD); 1017 prev->code2 = sizes->offset + (sizes->mult * (prev->size - MIN_MATCH)) + (inst->size - MIN_ADD);
1014 } 1018 }
1015 } 1019 }
@@ -1021,9 +1025,10 @@ xd3_choose_instruction (const xd3_code_table_desc *desc, xd3_rinst *prev, xd3_ri
1021 { 1025 {
1022 int mode = inst->type - XD3_CPY; 1026 int mode = inst->type - XD3_CPY;
1023 1027
1024 /* The large copy instruction is offset by the run, large add, and immediate adds, 1028 /* The large copy instruction is offset by the run, large add,
1025 * then multipled by the number of immediate copies plus one (the large copy) 1029 * and immediate adds, then multipled by the number of
1026 * (i.e., if there are 15 immediate copy instructions then there are 16 copy 1030 * immediate copies plus one (the large copy) (i.e., if there
1031 * are 15 immediate copy instructions then there are 16 copy
1027 * instructions per mode). */ 1032 * instructions per mode). */
1028 inst->code1 = 2 + desc->add_sizes + (1 + desc->cpy_sizes) * mode; 1033 inst->code1 = 2 + desc->add_sizes + (1 + desc->cpy_sizes) * mode;
1029 1034
@@ -1118,16 +1123,17 @@ xd3_choose_instruction (/* const xd3_code_table_desc *desc,*/ xd3_rinst *prev, x
1118} 1123}
1119#endif /* GENERIC_ENCODE_TABLES */ 1124#endif /* GENERIC_ENCODE_TABLES */
1120 1125
1121/****************************************************************************************** 1126/***********************************************************************
1122 Instruction table encoder/decoder 1127 Instruction table encoder/decoder
1123 ******************************************************************************************/ 1128 ***********************************************************************/
1124 1129
1125#if GENERIC_ENCODE_TABLES 1130#if GENERIC_ENCODE_TABLES
1126#if GENERIC_ENCODE_TABLES_COMPUTE == 0 1131#if GENERIC_ENCODE_TABLES_COMPUTE == 0
1127 1132
1128/* In this case, we hard-code the result of compute_code_table_encoding for each alternate 1133/* In this case, we hard-code the result of
1129 * code table, presuming that saves time/space. This has been 131 bytes, but secondary 1134 * compute_code_table_encoding for each alternate code table,
1130 * compression was turned off. */ 1135 * presuming that saves time/space. This has been 131 bytes, but
1136 * secondary compression was turned off. */
1131static const uint8_t __alternate_code_table_compressed[178] = 1137static const uint8_t __alternate_code_table_compressed[178] =
1132{0xd6,0xc3,0xc4,0x00,0x00,0x01,0x8a,0x6f,0x40,0x81,0x27,0x8c,0x00,0x00,0x4a,0x4a,0x0d,0x02,0x01,0x03, 1138{0xd6,0xc3,0xc4,0x00,0x00,0x01,0x8a,0x6f,0x40,0x81,0x27,0x8c,0x00,0x00,0x4a,0x4a,0x0d,0x02,0x01,0x03,
11330x01,0x03,0x00,0x01,0x00,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e, 11390x01,0x03,0x00,0x01,0x00,0x00,0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08,0x09,0x0a,0x0b,0x0c,0x0d,0x0e,
@@ -1210,9 +1216,9 @@ int xd3_compute_code_table_encoding (xd3_stream *in_stream, const xd3_dinst *cod
1210 return ret; 1216 return ret;
1211} 1217}
1212 1218
1213/* Compute a delta between alternate and rfc3284 tables. As soon as another alternate 1219/* Compute a delta between alternate and rfc3284 tables. As soon as
1214 * table is added, this code should become generic. For now there is only one alternate 1220 * another alternate table is added, this code should become generic.
1215 * table for testing. */ 1221 * For now there is only one alternate table for testing. */
1216static int 1222static int
1217xd3_compute_alternate_table_encoding (xd3_stream *stream, const uint8_t **data, usize_t *size) 1223xd3_compute_alternate_table_encoding (xd3_stream *stream, const uint8_t **data, usize_t *size)
1218{ 1224{
@@ -1417,9 +1423,9 @@ xd3_apply_table_encoding (xd3_stream *in_stream, const uint8_t *data, usize_t si
1417 return ret; 1423 return ret;
1418} 1424}
1419 1425
1420/****************************************************************************************** 1426/***********************************************************************
1421 Permute stuff 1427 Permute stuff
1422 ******************************************************************************************/ 1428 ***********************************************************************/
1423 1429
1424#if HASH_PERMUTE == 0 1430#if HASH_PERMUTE == 0
1425#define PERMUTE(x) (x) 1431#define PERMUTE(x) (x)
@@ -1465,9 +1471,9 @@ static const uint16_t __single_hash[256] =
1465}; 1471};
1466#endif 1472#endif
1467 1473
1468/****************************************************************************************** 1474/***********************************************************************
1469 Ctable stuff 1475 Ctable stuff
1470 ******************************************************************************************/ 1476 ***********************************************************************/
1471 1477
1472#if HASH_PRIME 1478#if HASH_PRIME
1473static const usize_t __primes[] = 1479static const usize_t __primes[] =
@@ -1499,9 +1505,9 @@ xd3_checksum_hash (const xd3_hash_cfg *cfg, const uint32_t cksum)
1499#endif 1505#endif
1500} 1506}
1501 1507
1502/****************************************************************************************** 1508/***********************************************************************
1503 Create the hash table. 1509 Create the hash table.
1504 ******************************************************************************************/ 1510 ***********************************************************************/
1505 1511
1506static inline void 1512static inline void
1507xd3_swap_uint8p (uint8_t** p1, uint8_t** p2) 1513xd3_swap_uint8p (uint8_t** p1, uint8_t** p2)
@@ -1605,9 +1611,9 @@ xd3_size_hashtable (xd3_stream *stream,
1605} 1611}
1606#endif 1612#endif
1607 1613
1608/****************************************************************************************** 1614/***********************************************************************
1609 Cksum function 1615 Cksum function
1610 ******************************************************************************************/ 1616 ***********************************************************************/
1611 1617
1612#if OLD_LARGE_CKSUM 1618#if OLD_LARGE_CKSUM
1613static inline uint32_t 1619static inline uint32_t
@@ -1652,9 +1658,9 @@ xd3_scksum (const uint8_t *seg, const int ln)
1652#define xd3_scksum(seg,ln) xd3_lcksum(seg,ln) 1658#define xd3_scksum(seg,ln) xd3_lcksum(seg,ln)
1653#endif 1659#endif
1654 1660
1655/****************************************************************************************** 1661/***********************************************************************
1656 Adler32 stream function: code copied from Zlib, defined in RFC1950 1662 Adler32 stream function: code copied from Zlib, defined in RFC1950
1657 ******************************************************************************************/ 1663 ***********************************************************************/
1658 1664
1659#define A32_BASE 65521L /* Largest prime smaller than 2^16 */ 1665#define A32_BASE 65521L /* Largest prime smaller than 2^16 */
1660#define A32_NMAX 5552 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */ 1666#define A32_NMAX 5552 /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
@@ -1700,9 +1706,9 @@ static unsigned long adler32 (unsigned long adler, const uint8_t *buf, usize_t l
1700 return (s2 << 16) | s1; 1706 return (s2 << 16) | s1;
1701} 1707}
1702 1708
1703/****************************************************************************************** 1709/***********************************************************************
1704 Run-length function 1710 Run-length function
1705 ******************************************************************************************/ 1711 ***********************************************************************/
1706 1712
1707static inline int 1713static inline int
1708xd3_comprun (const uint8_t *seg, int slook, uint8_t *run_cp) 1714xd3_comprun (const uint8_t *seg, int slook, uint8_t *run_cp)
@@ -1721,9 +1727,9 @@ xd3_comprun (const uint8_t *seg, int slook, uint8_t *run_cp)
1721 return run_l; 1727 return run_l;
1722} 1728}
1723 1729
1724/****************************************************************************************** 1730/***********************************************************************
1725 Basic encoder/decoder functions 1731 Basic encoder/decoder functions
1726 ******************************************************************************************/ 1732 ***********************************************************************/
1727 1733
1728static int 1734static int
1729xd3_decode_byte (xd3_stream *stream, uint *val) 1735xd3_decode_byte (xd3_stream *stream, uint *val)
@@ -1980,9 +1986,9 @@ xd3_sizeof_uint64_t (uint64_t num)
1980 1986
1981#endif 1987#endif
1982 1988
1983/****************************************************************************************** 1989/***********************************************************************
1984 Address cache stuff 1990 Address cache stuff
1985 ******************************************************************************************/ 1991 ***********************************************************************/
1986 1992
1987static int 1993static int
1988xd3_alloc_cache (xd3_stream *stream) 1994xd3_alloc_cache (xd3_stream *stream)
@@ -2135,9 +2141,9 @@ xd3_decode_address (xd3_stream *stream, usize_t here, uint mode, const uint8_t *
2135 return 0; 2141 return 0;
2136} 2142}
2137 2143
2138/****************************************************************************************** 2144/***********************************************************************
2139 Alloc/free 2145 Alloc/free
2140 ******************************************************************************************/ 2146***********************************************************************/
2141 2147
2142static void* 2148static void*
2143__xd3_alloc_func (void* opaque, usize_t items, usize_t size) 2149__xd3_alloc_func (void* opaque, usize_t items, usize_t size)
@@ -2387,9 +2393,9 @@ xd3_rtype_to_string (xd3_rtype type, int print_mode)
2387} 2393}
2388#endif 2394#endif
2389 2395
2390/****************************************************************************************** 2396/****************************************************************
2391 Stream configuration 2397 Stream configuration
2392 ******************************************************************************************/ 2398 ******************************************************************/
2393 2399
2394int 2400int
2395xd3_config_stream(xd3_stream *stream, 2401xd3_config_stream(xd3_stream *stream,
@@ -2565,26 +2571,27 @@ xd3_config_stream(xd3_stream *stream,
2565 return 0; 2571 return 0;
2566} 2572}
2567 2573
2568/****************************************************************************************** 2574/*****************************************************************
2569 Getblk interface 2575 Getblk interface
2570 ******************************************************************************************/ 2576 ***********************************************************/
2571 2577
2572/* This function interfaces with the client getblk function, checks its results, etc. */ 2578/* This function interfaces with the client getblk function, checks
2579 * its results, etc. */
2573static int 2580static int
2574xd3_getblk (xd3_stream *stream/*, xd3_source *source*/, xoff_t blkno) 2581xd3_getblk (xd3_stream *stream, xoff_t blkno)
2575{ 2582{
2576 int ret; 2583 int ret;
2577 xd3_source *source = stream->src; 2584 xd3_source *source = stream->src;
2578 2585
2579 if (blkno >= source->blocks) 2586 if (source->curblk == NULL ||
2587 blkno != source->curblkno)
2580 { 2588 {
2581 IF_DEBUG1 (DP(RINT "[getblk] block %"Q"u\n", blkno)); 2589 if (blkno >= source->blocks)
2582 stream->msg = "source file too short"; 2590 {
2583 return XD3_INTERNAL; 2591 stream->msg = "source file too short";
2584 } 2592 return XD3_INTERNAL;
2593 }
2585 2594
2586 if (blkno != source->curblkno || source->curblk == NULL)
2587 {
2588 XD3_ASSERT (source->curblk != NULL || blkno != source->curblkno); 2595 XD3_ASSERT (source->curblk != NULL || blkno != source->curblkno);
2589 2596
2590 source->getblkno = blkno; 2597 source->getblkno = blkno;
@@ -2603,7 +2610,8 @@ xd3_getblk (xd3_stream *stream/*, xd3_source *source*/, xoff_t blkno)
2603 XD3_ASSERT (source->curblk != NULL); 2610 XD3_ASSERT (source->curblk != NULL);
2604 } 2611 }
2605 2612
2606 if (source->onblk != xd3_bytes_on_srcblk (source, blkno)) 2613 if (source->onblk != (blkno == source->blocks - 1 ?
2614 source->onlastblk : source->blksize))
2607 { 2615 {
2608 stream->msg = "getblk returned short block"; 2616 stream->msg = "getblk returned short block";
2609 return XD3_INTERNAL; 2617 return XD3_INTERNAL;
@@ -2612,9 +2620,9 @@ xd3_getblk (xd3_stream *stream/*, xd3_source *source*/, xoff_t blkno)
2612 return 0; 2620 return 0;
2613} 2621}
2614 2622
2615/****************************************************************************************** 2623/***********************************************************
2616 Stream open/close 2624 Stream open/close
2617 ******************************************************************************************/ 2625 ***************************************************************/
2618 2626
2619int 2627int
2620xd3_set_source (xd3_stream *stream, 2628xd3_set_source (xd3_stream *stream,
@@ -2629,8 +2637,9 @@ xd3_set_source (xd3_stream *stream,
2629 2637
2630 stream->src = src; 2638 stream->src = src;
2631 blk_num = src->size / src->blksize; 2639 blk_num = src->size / src->blksize;
2632 tail_size = src->size % src->blksize; 2640 tail_size = src->size - (blk_num * src->blksize);
2633 src->blocks = blk_num + (tail_size > 0); 2641 src->blocks = blk_num + (tail_size > 0);
2642 src->onlastblk = xd3_bytes_on_srcblk (src, src->blocks - 1);
2634 src->srclen = 0; 2643 src->srclen = 0;
2635 src->srcbase = 0; 2644 src->srcbase = 0;
2636 2645
@@ -2649,7 +2658,22 @@ xd3_close_stream (xd3_stream *stream)
2649{ 2658{
2650 if (stream->enc_state != 0 && stream->enc_state != ENC_ABORTED) 2659 if (stream->enc_state != 0 && stream->enc_state != ENC_ABORTED)
2651 { 2660 {
2652 /* If encoding, should be ready for more input but not actually have any. */ 2661 if (stream->buf_leftover != NULL)
2662 {
2663 stream->msg = "encoding is incomplete";
2664 return XD3_INTERNAL;
2665 }
2666
2667 if (stream->enc_state == ENC_POSTWIN)
2668 {
2669 xd3_encode_reset (stream);
2670
2671 stream->current_window += 1;
2672 stream->enc_state = ENC_INPUT;
2673 }
2674
2675 /* If encoding, should be ready for more input but not actually
2676 have any. */
2653 if (stream->enc_state != ENC_INPUT || stream->avail_in != 0) 2677 if (stream->enc_state != ENC_INPUT || stream->avail_in != 0)
2654 { 2678 {
2655 stream->msg = "encoding is incomplete"; 2679 stream->msg = "encoding is incomplete";
@@ -2678,9 +2702,9 @@ xd3_close_stream (xd3_stream *stream)
2678 return 0; 2702 return 0;
2679} 2703}
2680 2704
2681/****************************************************************************************** 2705/**************************************************************
2682 Application header 2706 Application header
2683 ******************************************************************************************/ 2707 ****************************************************************/
2684 2708
2685int 2709int
2686xd3_get_appheader (xd3_stream *stream, 2710xd3_get_appheader (xd3_stream *stream,
@@ -2698,15 +2722,15 @@ xd3_get_appheader (xd3_stream *stream,
2698 return 0; 2722 return 0;
2699} 2723}
2700 2724
2701/****************************************************************************************** 2725/**********************************************************
2702 Decoder stuff 2726 Decoder stuff
2703 ******************************************************************************************/ 2727 *************************************************/
2704 2728
2705#include "xdelta3-decode.h" 2729#include "xdelta3-decode.h"
2706 2730
2707/****************************************************************************************** 2731/****************************************************************
2708 Encoder stuff 2732 Encoder stuff
2709 ******************************************************************************************/ 2733 *****************************************************************/
2710 2734
2711#if XD3_ENCODER 2735#if XD3_ENCODER
2712void 2736void
@@ -3461,9 +3485,9 @@ xd3_emit_hdr (xd3_stream *stream)
3461 return 0; 3485 return 0;
3462} 3486}
3463 3487
3464/****************************************************************************************** 3488/****************************************************************
3465 Encode routines 3489 Encode routines
3466 ******************************************************************************************/ 3490 ****************************************************************/
3467 3491
3468static int 3492static int
3469xd3_encode_buffer_leftover (xd3_stream *stream) 3493xd3_encode_buffer_leftover (xd3_stream *stream)
@@ -3716,9 +3740,9 @@ xd3_encode_input (xd3_stream *stream)
3716 3740
3717 stream->enc_state = ENC_SEARCH; 3741 stream->enc_state = ENC_SEARCH;
3718 3742
3719 IF_DEBUG1 (DP(RINT "[input window:%"Q"u] input bytes %u offset %"Q"u\n", 3743 IF_DEBUG1 (DP(RINT "[WINSTART:%"Q"u] input bytes %u offset %"Q"u\n",
3720 stream->current_window, stream->avail_in, stream->total_in)); 3744 stream->current_window, stream->avail_in,
3721 3745 stream->total_in));
3722 return XD3_WINSTART; 3746 return XD3_WINSTART;
3723 3747
3724 case ENC_SEARCH: 3748 case ENC_SEARCH:
@@ -3847,6 +3871,9 @@ xd3_encode_input (xd3_stream *stream)
3847 stream->total_in += (xoff_t) stream->avail_in; 3871 stream->total_in += (xoff_t) stream->avail_in;
3848 stream->enc_state = ENC_POSTWIN; 3872 stream->enc_state = ENC_POSTWIN;
3849 3873
3874 IF_DEBUG1 (DP(RINT "[WINFINISH:%"Q"u] in=%"Q"u\n",
3875 stream->current_window,
3876 stream->total_in));
3850 return XD3_WINFINISH; 3877 return XD3_WINFINISH;
3851 3878
3852 case ENC_POSTWIN: 3879 case ENC_POSTWIN:
@@ -4390,7 +4417,7 @@ xd3_source_extend_match (xd3_stream *stream)
4390 matchoff = stream->match_srcpos - stream->match_back; 4417 matchoff = stream->match_srcpos - stream->match_back;
4391 streamoff = stream->input_position - stream->match_back; 4418 streamoff = stream->input_position - stream->match_back;
4392 tryblk = matchoff / src->blksize; 4419 tryblk = matchoff / src->blksize;
4393 tryoff = matchoff % src->blksize; 4420 tryoff = matchoff - (tryblk * src->blksize);
4394 4421
4395 /* this loops backward over source blocks */ 4422 /* this loops backward over source blocks */
4396 while (stream->match_back < stream->match_maxback) 4423 while (stream->match_back < stream->match_maxback)
@@ -4439,7 +4466,7 @@ xd3_source_extend_match (xd3_stream *stream)
4439 matchoff = stream->match_srcpos + stream->match_fwd; 4466 matchoff = stream->match_srcpos + stream->match_fwd;
4440 streamoff = stream->input_position + stream->match_fwd; 4467 streamoff = stream->input_position + stream->match_fwd;
4441 tryblk = matchoff / src->blksize; 4468 tryblk = matchoff / src->blksize;
4442 tryoff = matchoff % src->blksize; 4469 tryoff = matchoff - (tryblk * src->blksize);
4443 4470
4444 /* Note: practically the same code as backwards case above: same comments */ 4471 /* Note: practically the same code as backwards case above: same comments */
4445 while (stream->match_fwd < stream->match_maxfwd) 4472 while (stream->match_fwd < stream->match_maxfwd)
@@ -4481,10 +4508,11 @@ xd3_source_extend_match (xd3_stream *stream)
4481 donefwd: 4508 donefwd:
4482 stream->match_state = MATCH_SEARCHING; 4509 stream->match_state = MATCH_SEARCHING;
4483 4510
4484 /* If the match ends short of the last instruction end, we probably don't want it. 4511 /* If the match ends short of the last instruction end, we probably
4485 * There is the possibility that a copy ends short of the last copy but also goes 4512 * don't want it. There is the possibility that a copy ends short
4486 * further back, in which case we might want it. This code does not implement such: if 4513 * of the last copy but also goes further back, in which case we
4487 * so we would need more complicated xd3_iopt_erase logic. */ 4514 * might want it. This code does not implement such: if so we would
4515 * need more complicated xd3_iopt_erase logic. */
4488 if (stream->match_fwd < stream->min_match) 4516 if (stream->match_fwd < stream->min_match)
4489 { 4517 {
4490 stream->match_fwd = 0; 4518 stream->match_fwd = 0;
@@ -4499,8 +4527,9 @@ xd3_source_extend_match (xd3_stream *stream)
4499 xoff_t match_position = stream->match_srcpos - stream->match_back; 4527 xoff_t match_position = stream->match_srcpos - stream->match_back;
4500 xoff_t match_end = stream->match_srcpos + stream->match_fwd; 4528 xoff_t match_end = stream->match_srcpos + stream->match_fwd;
4501 4529
4502 /* At this point we may have to erase any iopt-buffer instructions that are 4530 /* At this point we may have to erase any iopt-buffer
4503 * fully covered by a backward-extending copy. */ 4531 * instructions that are fully covered by a backward-extending
4532 * copy. */
4504 if (stream->match_back > 0) 4533 if (stream->match_back > 0)
4505 { 4534 {
4506 xd3_iopt_erase (stream, target_position, total); 4535 xd3_iopt_erase (stream, target_position, total);
@@ -4508,7 +4537,8 @@ xd3_source_extend_match (xd3_stream *stream)
4508 4537
4509 stream->match_back = 0; 4538 stream->match_back = 0;
4510 4539
4511 /* Update ranges. The first source match occurs with both values set to 0. */ 4540 /* Update ranges. The first source match occurs with both
4541 values set to 0. */
4512 if (stream->match_maxaddr == 0 || 4542 if (stream->match_maxaddr == 0 ||
4513 match_position < stream->match_minaddr) 4543 match_position < stream->match_minaddr)
4514 { 4544 {
@@ -4735,40 +4765,6 @@ xd3_verify_run_state (xd3_stream *stream,
4735 XD3_ASSERT (x_run_l > slook || run_l == x_run_l); 4765 XD3_ASSERT (x_run_l > slook || run_l == x_run_l);
4736} 4766}
4737#endif /* XD3_DEBUG */ 4767#endif /* XD3_DEBUG */
4738#endif /* XD3_ENCODER */
4739
4740/******************************************************************************************
4741 TEMPLATE pass
4742 ******************************************************************************************/
4743
4744#endif /* __XDELTA3_C_INLINE_PASS__ */
4745#ifdef __XDELTA3_C_TEMPLATE_PASS__
4746
4747#if XD3_ENCODER
4748
4749/******************************************************************************************
4750 Templates
4751 ******************************************************************************************/
4752
4753/* Template macros */
4754#define XD3_TEMPLATE(x) XD3_TEMPLATE2(x,TEMPLATE)
4755#define XD3_TEMPLATE2(x,n) XD3_TEMPLATE3(x,n)
4756#define XD3_TEMPLATE3(x,n) x ## n
4757#define XD3_STRINGIFY(x) XD3_STRINGIFY2(x)
4758#define XD3_STRINGIFY2(x) #x
4759
4760static int XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream);
4761
4762static const xd3_smatcher XD3_TEMPLATE(__smatcher_) =
4763{
4764 XD3_STRINGIFY(TEMPLATE),
4765 XD3_TEMPLATE(xd3_string_match_),
4766#if SOFTCFG == 1
4767 0, 0, 0, 0, 0, 0, 0
4768#else
4769 LLOOK, LSTEP, SLOOK, SCHAIN, SLCHAIN, MAXLAZY, LONGENOUGH
4770#endif
4771};
4772 4768
4773/* This function computes more source checksums to advance the window. 4769/* This function computes more source checksums to advance the window.
4774 * Called at every entrance to the string-match loop and each time 4770 * Called at every entrance to the string-match loop and each time
@@ -4778,10 +4774,9 @@ static const xd3_smatcher XD3_TEMPLATE(__smatcher_) =
4778 * 4774 *
4779 * TODO: really would like a good test for this logic. how? 4775 * TODO: really would like a good test for this logic. how?
4780 * TODO: optimize the inner loop 4776 * TODO: optimize the inner loop
4781 * TODO: do-templatize this
4782 */ 4777 */
4783static int 4778static int
4784XD3_TEMPLATE(xd3_srcwin_move_point_) (xd3_stream *stream, usize_t *next_move_point) 4779xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
4785{ 4780{
4786 xoff_t logical_input_cksum_pos; 4781 xoff_t logical_input_cksum_pos;
4787 4782
@@ -4845,11 +4840,12 @@ XD3_TEMPLATE(xd3_srcwin_move_point_) (xd3_stream *stream, usize_t *next_move_poi
4845 stream->srcwin_cksum_pos < stream->src->size) 4840 stream->srcwin_cksum_pos < stream->src->size)
4846 { 4841 {
4847 xoff_t blkno = stream->srcwin_cksum_pos / stream->src->blksize; 4842 xoff_t blkno = stream->srcwin_cksum_pos / stream->src->blksize;
4848 ssize_t oldpos = stream->srcwin_cksum_pos % stream->src->blksize; 4843 xoff_t blkbaseoffset = blkno * stream->src->blksize;
4849 ssize_t blkpos = xd3_bytes_on_srcblk (stream->src, blkno); 4844 ssize_t oldpos = stream->srcwin_cksum_pos - blkbaseoffset;
4845 ssize_t blkpos = xd3_bytes_on_srcblk_fast (stream->src, blkno);
4850 int ret; 4846 int ret;
4851 4847
4852 if (oldpos + LLOOK > blkpos) 4848 if (oldpos + stream->smatcher.large_look > blkpos)
4853 { 4849 {
4854 stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize; 4850 stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize;
4855 continue; 4851 continue;
@@ -4874,20 +4870,22 @@ XD3_TEMPLATE(xd3_srcwin_move_point_) (xd3_stream *stream, usize_t *next_move_poi
4874 * the number of bytes available. Each iteration inspects 4870 * the number of bytes available. Each iteration inspects
4875 * large_look bytes then steps back large_step bytes. The 4871 * large_look bytes then steps back large_step bytes. The
4876 * if-stmt above ensures at least one large_look of data. */ 4872 * if-stmt above ensures at least one large_look of data. */
4877 blkpos -= LLOOK; 4873 blkpos -= stream->smatcher.large_look;
4874 blkbaseoffset = stream->src->blksize * blkno;
4878 4875
4879 do 4876 do
4880 { 4877 {
4881 uint32_t cksum = xd3_lcksum (stream->src->curblk + blkpos, LLOOK); 4878 uint32_t cksum = xd3_lcksum (stream->src->curblk + blkpos,
4879 stream->smatcher.large_look);
4882 usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum); 4880 usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum);
4883 4881
4884 stream->large_table[hval] = 4882 stream->large_table[hval] =
4885 (usize_t) ((stream->src->blksize * blkno) + 4883 (usize_t) (blkbaseoffset +
4886 (xoff_t)(blkpos + HASH_CKOFFSET)); 4884 (xoff_t)(blkpos + HASH_CKOFFSET));
4887 4885
4888 IF_DEBUG (stream->large_ckcnt += 1); 4886 IF_DEBUG (stream->large_ckcnt += 1);
4889 4887
4890 blkpos -= LSTEP; 4888 blkpos -= stream->smatcher.large_step;
4891 } 4889 }
4892 while (blkpos >= oldpos); 4890 while (blkpos >= oldpos);
4893 4891
@@ -4909,6 +4907,41 @@ XD3_TEMPLATE(xd3_srcwin_move_point_) (xd3_stream *stream, usize_t *next_move_poi
4909 return 0; 4907 return 0;
4910} 4908}
4911 4909
4910#endif /* XD3_ENCODER */
4911
4912/********************************************************************
4913 TEMPLATE pass
4914 *********************************************************************/
4915
4916#endif /* __XDELTA3_C_INLINE_PASS__ */
4917#ifdef __XDELTA3_C_TEMPLATE_PASS__
4918
4919#if XD3_ENCODER
4920
4921/********************************************************************
4922 Templates
4923 *******************************************************************/
4924
4925/* Template macros */
4926#define XD3_TEMPLATE(x) XD3_TEMPLATE2(x,TEMPLATE)
4927#define XD3_TEMPLATE2(x,n) XD3_TEMPLATE3(x,n)
4928#define XD3_TEMPLATE3(x,n) x ## n
4929#define XD3_STRINGIFY(x) XD3_STRINGIFY2(x)
4930#define XD3_STRINGIFY2(x) #x
4931
4932static int XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream);
4933
4934static const xd3_smatcher XD3_TEMPLATE(__smatcher_) =
4935{
4936 XD3_STRINGIFY(TEMPLATE),
4937 XD3_TEMPLATE(xd3_string_match_),
4938#if SOFTCFG == 1
4939 0, 0, 0, 0, 0, 0, 0
4940#else
4941 LLOOK, LSTEP, SLOOK, SCHAIN, SLCHAIN, MAXLAZY, LONGENOUGH
4942#endif
4943};
4944
4912static int 4945static int
4913XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream) 4946XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
4914{ 4947{
@@ -4930,24 +4963,27 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
4930 usize_t match_offset = 0; 4963 usize_t match_offset = 0;
4931 usize_t next_move_point; 4964 usize_t next_move_point;
4932 4965
4933 /* If there will be no compression due to settings or short input, skip it entirely. */ 4966 /* If there will be no compression due to settings or short input,
4967 skip it entirely. */
4934 if (! (DO_SMALL || DO_LARGE || DO_RUN) || 4968 if (! (DO_SMALL || DO_LARGE || DO_RUN) ||
4935 stream->input_position + SLOOK > stream->avail_in) { goto loopnomore; } 4969 stream->input_position + SLOOK > stream->avail_in) { goto loopnomore; }
4936 4970
4937 if ((ret = xd3_string_match_init (stream))) { return ret; } 4971 if ((ret = xd3_string_match_init (stream))) { return ret; }
4938 4972
4939 /* The restartloop label is reached when the incremental loop state needs to be 4973 /* The restartloop label is reached when the incremental loop state
4940 * reset. */ 4974 * needs to be reset. */
4941 restartloop: 4975 restartloop:
4942 4976
4943 /* If there is not enough input remaining for any kind of match, skip it. */ 4977 /* If there is not enough input remaining for any kind of match,
4978 skip it. */
4944 if (stream->input_position + SLOOK > stream->avail_in) { goto loopnomore; } 4979 if (stream->input_position + SLOOK > stream->avail_in) { goto loopnomore; }
4945 4980
4946 /* Now reset the incremental loop state: */ 4981 /* Now reset the incremental loop state: */
4947 4982
4948 /* The min_match variable is updated to avoid matching the same lazy match over and over 4983 /* The min_match variable is updated to avoid matching the same lazy
4949 * again. For example, if you find a (small) match of length 9 at one position, you 4984 * match over and over again. For example, if you find a (small)
4950 * will likely find a match of length 8 at the next position. */ 4985 * match of length 9 at one position, you will likely find a match
4986 * of length 8 at the next position. */
4951 if (xd3_iopt_last_matched (stream) > stream->input_position) 4987 if (xd3_iopt_last_matched (stream) > stream->input_position)
4952 { 4988 {
4953 stream->min_match = max(MIN_MATCH, 1 + xd3_iopt_last_matched(stream) - stream->input_position); 4989 stream->min_match = max(MIN_MATCH, 1 + xd3_iopt_last_matched(stream) - stream->input_position);
@@ -4972,13 +5008,15 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
4972 run_l = xd3_comprun (inp, SLOOK, & run_c); 5008 run_l = xd3_comprun (inp, SLOOK, & run_c);
4973 } 5009 }
4974 5010
4975 /* Large match state. We continue the loop even after not enough bytes for LLOOK 5011 /* Large match state. We continue the loop even after not enough
4976 * remain, so always check stream->input_position in DO_LARGE code. */ 5012 * bytes for LLOOK remain, so always check stream->input_position in
5013 * DO_LARGE code. */
4977 if (DO_LARGE && (stream->input_position + LLOOK <= stream->avail_in)) 5014 if (DO_LARGE && (stream->input_position + LLOOK <= stream->avail_in))
4978 { 5015 {
4979 /* Source window: next_move_point is the point that stream->input_position must reach before 5016 /* Source window: next_move_point is the point that
4980 * computing more source checksum. */ 5017 * stream->input_position must reach before computing more
4981 if ((ret = XD3_TEMPLATE(xd3_srcwin_move_point_) (stream, & next_move_point))) 5018 * source checksum. */
5019 if ((ret = xd3_srcwin_move_point (stream, & next_move_point)))
4982 { 5020 {
4983 return ret; 5021 return ret;
4984 } 5022 }
@@ -4986,15 +5024,16 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
4986 lcksum = xd3_lcksum (inp, LLOOK); 5024 lcksum = xd3_lcksum (inp, LLOOK);
4987 } 5025 }
4988 5026
4989 /* TRYLAZYLEN: True if a certain length match should be followed by lazy search. This 5027 /* TRYLAZYLEN: True if a certain length match should be followed by
4990 * checks that LEN is shorter than MAXLAZY and that there is enough leftover data to 5028 * lazy search. This checks that LEN is shorter than MAXLAZY and
4991 * consider lazy matching. "Enough" is set to 2 since the next match will start at the 5029 * that there is enough leftover data to consider lazy matching.
4992 * next offset, it must match two extra characters. */ 5030 * "Enough" is set to 2 since the next match will start at the next
5031 * offset, it must match two extra characters. */
4993#define TRYLAZYLEN(LEN,POS,MAX) ((MAXLAZY) > 0 && (LEN) < (MAXLAZY) && (POS) + (LEN) <= (MAX) - 2) 5032#define TRYLAZYLEN(LEN,POS,MAX) ((MAXLAZY) > 0 && (LEN) < (MAXLAZY) && (POS) + (LEN) <= (MAX) - 2)
4994 5033
4995 /* HANDLELAZY: This statement is called each time an instruciton is emitted (three 5034 /* HANDLELAZY: This statement is called each time an instruciton is
4996 * cases). If the instruction is large enough, the loop is restarted, otherwise lazy 5035 * emitted (three cases). If the instruction is large enough, the
4997 * matching may ensue. */ 5036 * loop is restarted, otherwise lazy matching may ensue. */
4998#define HANDLELAZY(mlen) \ 5037#define HANDLELAZY(mlen) \
4999 if (TRYLAZYLEN ((mlen), (stream->input_position), (stream->avail_in))) \ 5038 if (TRYLAZYLEN ((mlen), (stream->input_position), (stream->avail_in))) \
5000 { stream->min_match = (mlen) + LEAST_MATCH_INCR; goto updateone; } \ 5039 { stream->min_match = (mlen) + LEAST_MATCH_INCR; goto updateone; } \
@@ -5007,12 +5046,13 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
5007 /* Now we try three kinds of string match in order of expense: 5046 /* Now we try three kinds of string match in order of expense:
5008 * run, large match, small match. */ 5047 * run, large match, small match. */
5009 5048
5010 /* Expand the start of a RUN. The test for (run_l == SLOOK) avoids repeating this 5049 /* Expand the start of a RUN. The test for (run_l == SLOOK)
5011 * check when we pass through a run area performing lazy matching. The run is only 5050 * avoids repeating this check when we pass through a run area
5012 * expanded once when the min_match is first reached. If lazy matching is 5051 * performing lazy matching. The run is only expanded once when
5013 * performed, the run_l variable will remain inconsistent until the first 5052 * the min_match is first reached. If lazy matching is
5014 * non-running input character is reached, at which time the run_l may then again 5053 * performed, the run_l variable will remain inconsistent until
5015 * grow to SLOOK. */ 5054 * the first non-running input character is reached, at which
5055 * time the run_l may then again grow to SLOOK. */
5016 if (DO_RUN && run_l == SLOOK) 5056 if (DO_RUN && run_l == SLOOK)
5017 { 5057 {
5018 usize_t max_len = stream->avail_in - stream->input_position; 5058 usize_t max_len = stream->avail_in - stream->input_position;
@@ -5034,7 +5074,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
5034 if (DO_LARGE && (stream->input_position + LLOOK <= stream->avail_in)) 5074 if (DO_LARGE && (stream->input_position + LLOOK <= stream->avail_in))
5035 { 5075 {
5036 if ((stream->input_position >= next_move_point) && 5076 if ((stream->input_position >= next_move_point) &&
5037 (ret = XD3_TEMPLATE(xd3_srcwin_move_point_) (stream, & next_move_point))) 5077 (ret = xd3_srcwin_move_point (stream, & next_move_point)))
5038 { 5078 {
5039 return ret; 5079 return ret;
5040 } 5080 }
@@ -5043,15 +5083,18 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
5043 5083
5044 IF_DEBUG (xd3_verify_large_state (stream, inp, lcksum)); 5084 IF_DEBUG (xd3_verify_large_state (stream, inp, lcksum));
5045 5085
5046 /* Note: To handle large checksum duplicates, this code should be rearranged to 5086 /* Note: To handle large checksum duplicates, this code
5047 * resemble the small_match case more. But how much of the code can be truly 5087 * should be rearranged to resemble the small_match case
5048 * shared? The main difference is the need for xd3_source_extend_match to work 5088 * more. But how much of the code can be truly shared? The
5049 * outside of xd3_string_match, in the case where inputs are identical. */ 5089 * main difference is the need for xd3_source_extend_match
5090 * to work outside of xd3_string_match, in the case where
5091 * inputs are identical. */
5050 if (unlikely (stream->large_table[linx] != 0)) 5092 if (unlikely (stream->large_table[linx] != 0))
5051 { 5093 {
5052 /* the match_setup will fail if the source window has been decided and the 5094 /* the match_setup will fail if the source window has
5053 * match lies outside it. You could consider forcing a window at this point 5095 * been decided and the match lies outside it. You
5054 * to permit a new source window. */ 5096 * could consider forcing a window at this point to
5097 * permit a new source window. */
5055 xoff_t adj_offset = 5098 xoff_t adj_offset =
5056 xd3_source_cksum_offset(stream, 5099 xd3_source_cksum_offset(stream,
5057 stream->large_table[linx] - HASH_CKOFFSET); 5100 stream->large_table[linx] - HASH_CKOFFSET);
@@ -5121,8 +5164,9 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
5121 } 5164 }
5122 } 5165 }
5123 5166
5124 /* The logic above prevents excess work during lazy matching by increasing min_match 5167 /* The logic above prevents excess work during lazy matching by
5125 * to avoid smaller matches. Each time we advance stream->input_position by one, the minimum match 5168 * increasing min_match to avoid smaller matches. Each time we
5169 * advance stream->input_position by one, the minimum match
5126 * shortens as well. */ 5170 * shortens as well. */
5127 if (stream->min_match > MIN_MATCH) 5171 if (stream->min_match > MIN_MATCH)
5128 { 5172 {
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h
index ce90cd7..af79839 100644
--- a/xdelta3/xdelta3.h
+++ b/xdelta3/xdelta3.h
@@ -126,7 +126,11 @@ typedef uint64_t xoff_t;
126#define Q "I64" 126#define Q "I64"
127#endif 127#endif
128#else 128#else
129#ifndef __uint32_t_defined
130typedef unsigned int xoff_t;
131#else
129typedef uint32_t xoff_t; 132typedef uint32_t xoff_t;
133#endif
130#define SIZEOF_XOFF_T 4 134#define SIZEOF_XOFF_T 4
131#define SIZEOF_USIZE_T 4 135#define SIZEOF_USIZE_T 4
132#define Q 136#define Q
@@ -614,23 +618,31 @@ struct _xd3_sec_cfg
614struct _xd3_config 618struct _xd3_config
615{ 619{
616 usize_t winsize; /* The encoder window size. */ 620 usize_t winsize; /* The encoder window size. */
617 usize_t sprevsz; /* How far back small string matching goes */ 621 usize_t sprevsz; /* How far back small string
618 usize_t iopt_size; /* entries in the instruction-optimizing buffer */ 622 matching goes */
619 usize_t srcwin_maxsz; /* srcwin_size grows by a factor of 2 when no matches are found */ 623 usize_t iopt_size; /* entries in the
624 instruction-optimizing
625 buffer */
626 usize_t srcwin_maxsz; /* srcwin_size grows by a factor
627 of 2 when no matches are
628 found */
620 629
621 xd3_getblk_func *getblk; /* The three callbacks. */ 630 xd3_getblk_func *getblk; /* The three callbacks. */
622 xd3_alloc_func *alloc; 631 xd3_alloc_func *alloc;
623 xd3_free_func *freef; 632 xd3_free_func *freef;
624 void *opaque; /* Not used. */ 633 void *opaque; /* Not used. */
625 int flags; /* stream->flags are initialized from xd3_config & 634 int flags; /* stream->flags are initialized
626 * never modified by the library. Use xd3_set_flags 635 * from xd3_config & never
627 * to modify flags settings mid-stream. */ 636 * modified by the library. Use
637 * xd3_set_flags to modify flags
638 * settings mid-stream. */
628 639
629 xd3_sec_cfg sec_data; /* Secondary compressor config: data */ 640 xd3_sec_cfg sec_data; /* Secondary compressor config: data */
630 xd3_sec_cfg sec_inst; /* Secondary compressor config: inst */ 641 xd3_sec_cfg sec_inst; /* Secondary compressor config: inst */
631 xd3_sec_cfg sec_addr; /* Secondary compressor config: addr */ 642 xd3_sec_cfg sec_addr; /* Secondary compressor config: addr */
632 643
633 xd3_smatch_cfg smatch_cfg; /* See enum: use fields below for soft config */ 644 xd3_smatch_cfg smatch_cfg; /* See enum: use fields below for
645 soft config */
634 xd3_smatcher smatcher_soft; 646 xd3_smatcher smatcher_soft;
635}; 647};
636 648
@@ -645,49 +657,66 @@ struct _xd3_source
645 /* you set */ 657 /* you set */
646 xoff_t size; /* size of this source */ 658 xoff_t size; /* size of this source */
647 usize_t blksize; /* block size */ 659 usize_t blksize; /* block size */
648 const char *name; /* its name, for debug/print purposes */ 660 const char *name; /* its name, for debug/print
661 purposes */
649 void *ioh; /* opaque handle */ 662 void *ioh; /* opaque handle */
650 663
651 /* getblk sets */ 664 /* getblk sets */
652 xoff_t curblkno; /* current block number: client sets after getblk request */ 665 xoff_t curblkno; /* current block number: client
653 usize_t onblk; /* number of bytes on current block: client sets, xd3 verifies */ 666 sets after getblk request */
654 const uint8_t *curblk; /* current block array: client sets after getblk request */ 667 usize_t onblk; /* number of bytes on current
668 block: client sets, xd3
669 verifies */
670 const uint8_t *curblk; /* current block array: client
671 sets after getblk request */
655 672
656 /* xd3 sets */ 673 /* xd3 sets */
657 usize_t srclen; /* length of this source window */ 674 usize_t srclen; /* length of this source window */
658 xoff_t srcbase; /* offset of this source window in the source itself */ 675 xoff_t srcbase; /* offset of this source window
659 xoff_t blocks; /* the total number of blocks in this source */ 676 in the source itself */
660 usize_t cpyoff_blocks; /* offset of copy window in blocks */ 677 xoff_t blocks; /* the total number of blocks in
661 usize_t cpyoff_blkoff; /* offset of copy window in blocks, remainder */ 678 this source */
662 xoff_t getblkno; /* request block number: xd3 sets current getblk request */ 679 usize_t onlastblk; /* cached size info, avoid __udivdi3 */
680 usize_t cpyoff_blocks; /* offset of copy window in
681 blocks */
682 usize_t cpyoff_blkoff; /* offset of copy window in
683 blocks, remainder */
684 xoff_t getblkno; /* request block number: xd3 sets
685 current getblk request */
663}; 686};
664 687
665/* The primary xd3_stream object, used for encoding and decoding. You may access only two 688/* The primary xd3_stream object, used for encoding and decoding. You
666 * fields: avail_out, next_out. Use the methods above to operate on xd3_stream. */ 689 * may access only two fields: avail_out, next_out. Use the methods
690 * above to operate on xd3_stream. */
667struct _xd3_stream 691struct _xd3_stream
668{ 692{
669 /* input state */ 693 /* input state */
670 const uint8_t *next_in; /* next input byte */ 694 const uint8_t *next_in; /* next input byte */
671 usize_t avail_in; /* number of bytes available at next_in */ 695 usize_t avail_in; /* number of bytes available at
696 next_in */
672 xoff_t total_in; /* how many bytes in */ 697 xoff_t total_in; /* how many bytes in */
673 698
674 /* output state */ 699 /* output state */
675 uint8_t *next_out; /* next output byte */ 700 uint8_t *next_out; /* next output byte */
676 usize_t avail_out; /* number of bytes available at next_out */ 701 usize_t avail_out; /* number of bytes available at
702 next_out */
677 usize_t space_out; /* total out space */ 703 usize_t space_out; /* total out space */
678 xoff_t current_window; /* number of windows encoded/decoded */ 704 xoff_t current_window; /* number of windows encoded/decoded */
679 xoff_t total_out; /* how many bytes out */ 705 xoff_t total_out; /* how many bytes out */
680 706
681 /* to indicate an error, xd3 sets */ 707 /* to indicate an error, xd3 sets */
682 const char *msg; /* last error message, NULL if no error */ 708 const char *msg; /* last error message, NULL if
709 no error */
683 710
684 /* source configuration */ 711 /* source configuration */
685 xd3_source *src; /* source array */ 712 xd3_source *src; /* source array */
686 713
687 /* encoder memory configuration */ 714 /* encoder memory configuration */
688 usize_t winsize; /* suggested window size */ 715 usize_t winsize; /* suggested window size */
689 usize_t sprevsz; /* small string, previous window size (power of 2) */ 716 usize_t sprevsz; /* small string, previous window
690 usize_t sprevmask; /* small string, previous window size mask */ 717 size (power of 2) */
718 usize_t sprevmask; /* small string, previous window
719 size mask */
691 uint iopt_size; 720 uint iopt_size;
692 uint iopt_unlimited; 721 uint iopt_unlimited;
693 uint srcwin_maxsz; 722 uint srcwin_maxsz;
@@ -696,7 +725,8 @@ struct _xd3_stream
696 xd3_getblk_func *getblk; /* set nxtblk, nxtblkno to scanblkno */ 725 xd3_getblk_func *getblk; /* set nxtblk, nxtblkno to scanblkno */
697 xd3_alloc_func *alloc; /* malloc function */ 726 xd3_alloc_func *alloc; /* malloc function */
698 xd3_free_func *free; /* free function */ 727 xd3_free_func *free; /* free function */
699 void* opaque; /* private data object passed to alloc, free, and getblk */ 728 void* opaque; /* private data object passed to
729 alloc, free, and getblk */
700 int flags; /* various options */ 730 int flags; /* various options */
701 731
702 /* secondary compressor configuration */ 732 /* secondary compressor configuration */
@@ -710,8 +740,10 @@ struct _xd3_stream
710 xd3_hash_cfg large_hash; /* large hash config */ 740 xd3_hash_cfg large_hash; /* large hash config */
711 741
712 usize_t *small_table; /* table of small checksums */ 742 usize_t *small_table; /* table of small checksums */
713 xd3_slist *small_prev; /* table of previous offsets, circular linked list */ 743 xd3_slist *small_prev; /* table of previous offsets,
714 int small_reset; /* true if small table should be reset */ 744 circular linked list */
745 int small_reset; /* true if small table should
746 be reset */
715 747
716 xd3_hash_cfg small_hash; /* small hash config */ 748 xd3_hash_cfg small_hash; /* small hash config */
717 xd3_addr_cache acache; /* the vcdiff address cache */ 749 xd3_addr_cache acache; /* the vcdiff address cache */
@@ -719,39 +751,54 @@ struct _xd3_stream
719 751
720 usize_t taroff; /* base offset of the target input */ 752 usize_t taroff; /* base offset of the target input */
721 usize_t input_position; /* current input position */ 753 usize_t input_position; /* current input position */
722 usize_t min_match; /* current minimum match length, avoids redundent matches */ 754 usize_t min_match; /* current minimum match
723 usize_t unencoded_offset; /* current input, first unencoded offset. this value is <= the first 755 length, avoids redundent
724 * instruction's position in the iopt buffer, if there is at least one 756 matches */
757 usize_t unencoded_offset; /* current input, first
758 * unencoded offset. this value
759 * is <= the first instruction's
760 * position in the iopt buffer,
761 * if there is at least one
725 * match in the buffer. */ 762 * match in the buffer. */
726 763
727 // SRCWIN 764 // SRCWIN
728 // these variables plus srcwin_maxsz above (set by config) 765 // these variables plus srcwin_maxsz above (set by config)
729 int srcwin_decided; /* boolean: true if the srclen,srcbase have been decided. */ 766 int srcwin_decided; /* boolean: true if the
767 srclen,srcbase have been
768 decided. */
730 xoff_t srcwin_cksum_pos; /* Source checksum position */ 769 xoff_t srcwin_cksum_pos; /* Source checksum position */
731 770
732 // MATCH 771 // MATCH
733 xd3_match_state match_state; /* encoder match state */ 772 xd3_match_state match_state; /* encoder match state */
734 xoff_t match_srcpos; /* current match source position relative to srcbase */ 773 xoff_t match_srcpos; /* current match source
735 xoff_t match_minaddr; /* smallest matching address to set window params 774 position relative to
736 * (reset each window xd3_encode_reset) */ 775 srcbase */
737 xoff_t match_maxaddr; /* largest matching address to set window params 776 xoff_t match_minaddr; /* smallest matching address to
738 * (reset each window xd3_encode_reset) */ 777 * set window params (reset each
778 * window xd3_encode_reset) */
779 xoff_t match_maxaddr; /* largest matching address to
780 * set window params (reset each
781 * window xd3_encode_reset) */
739 usize_t match_back; /* match extends back so far */ 782 usize_t match_back; /* match extends back so far */
740 usize_t match_maxback; /* match extends back maximum */ 783 usize_t match_maxback; /* match extends back maximum */
741 usize_t match_fwd; /* match extends forward so far */ 784 usize_t match_fwd; /* match extends forward so far */
742 usize_t match_maxfwd; /* match extends forward maximum */ 785 usize_t match_maxfwd; /* match extends forward maximum */
743 786
744 xoff_t maxsrcaddr; /* address of the last source match (across windows) */ 787 xoff_t maxsrcaddr; /* address of the last source
788 match (across windows) */
745 789
746 uint8_t *buf_in; /* for saving buffered input */ 790 uint8_t *buf_in; /* for saving buffered input */
747 usize_t buf_avail; /* amount of saved input */ 791 usize_t buf_avail; /* amount of saved input */
748 const uint8_t *buf_leftover; /* leftover content of next_in (i.e., user's buffer) */ 792 const uint8_t *buf_leftover; /* leftover content of next_in
793 (i.e., user's buffer) */
749 usize_t buf_leftavail; /* amount of leftover content */ 794 usize_t buf_leftavail; /* amount of leftover content */
750 795
751 xd3_output *enc_current; /* current output buffer */ 796 xd3_output *enc_current; /* current output buffer */
752 xd3_output *enc_free; /* free output buffers */ 797 xd3_output *enc_free; /* free output buffers */
753 xd3_output *enc_heads[4]; /* array of encoded outputs: head of chain */ 798 xd3_output *enc_heads[4]; /* array of encoded outputs:
754 xd3_output *enc_tails[4]; /* array of encoded outputs: tail of chain */ 799 head of chain */
800 xd3_output *enc_tails[4]; /* array of encoded outputs:
801 tail of chain */
755 802
756 xd3_rlist iopt_used; /* instruction optimizing buffer */ 803 xd3_rlist iopt_used; /* instruction optimizing buffer */
757 xd3_rlist iopt_free; 804 xd3_rlist iopt_free;
@@ -776,16 +823,21 @@ struct _xd3_stream
776 uint8_t *dec_codetbl; /* Optional code table: storage. */ 823 uint8_t *dec_codetbl; /* Optional code table: storage. */
777 usize_t dec_codetblbytes; /* Optional code table: position. */ 824 usize_t dec_codetblbytes; /* Optional code table: position. */
778 825
779 uint32_t dec_appheadsz; /* Optional application header: size. */ 826 uint32_t dec_appheadsz; /* Optional application header:
780 uint8_t *dec_appheader; /* Optional application header: storage */ 827 size. */
781 usize_t dec_appheadbytes; /* Optional application header: position. */ 828 uint8_t *dec_appheader; /* Optional application header:
829 storage */
830 usize_t dec_appheadbytes; /* Optional application header:
831 position. */
782 832
783 usize_t dec_cksumbytes; /* Optional checksum: position. */ 833 usize_t dec_cksumbytes; /* Optional checksum: position. */
784 uint8_t dec_cksum[4]; /* Optional checksum: storage. */ 834 uint8_t dec_cksum[4]; /* Optional checksum: storage. */
785 uint32_t dec_adler32; /* Optional checksum: value. */ 835 uint32_t dec_adler32; /* Optional checksum: value. */
786 836
787 uint32_t dec_cpylen; /* length of copy window (VCD_SOURCE or VCD_TARGET) */ 837 uint32_t dec_cpylen; /* length of copy window
788 xoff_t dec_cpyoff; /* offset of copy window (VCD_SOURCE or VCD_TARGET) */ 838 (VCD_SOURCE or VCD_TARGET) */
839 xoff_t dec_cpyoff; /* offset of copy window
840 (VCD_SOURCE or VCD_TARGET) */
789 uint32_t dec_enclen; /* length of delta encoding */ 841 uint32_t dec_enclen; /* length of delta encoding */
790 uint32_t dec_tgtlen; /* length of target window */ 842 uint32_t dec_tgtlen; /* length of target window */
791 843
@@ -1114,7 +1166,10 @@ const char* xd3_errstring (xd3_stream *stream)
1114 1166
1115/* This function tells the number of bytes expected to be set in 1167/* This function tells the number of bytes expected to be set in
1116 * source->onblk after a getblk request. This is for convenience of 1168 * source->onblk after a getblk request. This is for convenience of
1117 * handling a partial last block. */ 1169 * handling a partial last block. Note that this is a relatively
1170 * expensive function for 64-bit binaries on platforms w/o native
1171 * 64-bit integers, so source->onlastblk is set to this value.
1172 * TODO: force source->blksize to a power of two? */
1118static inline 1173static inline
1119usize_t xd3_bytes_on_srcblk (xd3_source *source, xoff_t blkno) 1174usize_t xd3_bytes_on_srcblk (xd3_source *source, xoff_t blkno)
1120{ 1175{
@@ -1128,4 +1183,12 @@ usize_t xd3_bytes_on_srcblk (xd3_source *source, xoff_t blkno)
1128 return (usize_t)((source->size - 1) % source->blksize) + 1; 1183 return (usize_t)((source->size - 1) % source->blksize) + 1;
1129} 1184}
1130 1185
1186static inline
1187usize_t xd3_bytes_on_srcblk_fast (xd3_source *source, xoff_t blkno)
1188{
1189 return (blkno == source->blocks - 1 ?
1190 source->onlastblk :
1191 source->blksize);
1192}
1193
1131#endif /* _XDELTA3_H_ */ 1194#endif /* _XDELTA3_H_ */
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-07 19:04:07 +0000