diff options
author | Joshua MacDonald <josh.macdonald@gmail.com> | 2015-11-17 22:52:01 -0800 |
---|---|---|
committer | Joshua MacDonald <josh.macdonald@gmail.com> | 2015-11-17 22:52:01 -0800 |
commit | dc410accc1e1dcef1100d4c047fadb3c6545d172 (patch) | |
tree | 5df6805271e4a6d79b385a25df6f487010593d78 /xdelta3 | |
parent | 97a6543f64e84821b638a60c88c814c2bdcdfc60 (diff) |
Simplifies xd3_srcwin_move_point; reads the full max_winsize before starting to compress (see notes in the corresponding comments); eliminates xd3_stream::frontier_pos; changes as a result, and improvements in testing/regtest.cc; tested on osx-darwin
Diffstat (limited to 'xdelta3')
-rw-r--r-- | xdelta3/Makefile.am | 4 | ||||
-rw-r--r-- | xdelta3/testing/regtest.cc | 177 | ||||
-rw-r--r-- | xdelta3/testing/test.h | 4 | ||||
-rw-r--r-- | xdelta3/xdelta3-decode.h | 7 | ||||
-rw-r--r-- | xdelta3/xdelta3.c | 171 | ||||
-rw-r--r-- | xdelta3/xdelta3.h | 3 |
6 files changed, 171 insertions, 195 deletions
diff --git a/xdelta3/Makefile.am b/xdelta3/Makefile.am index 6ab3a42..d2f7b31 100644 --- a/xdelta3/Makefile.am +++ b/xdelta3/Makefile.am | |||
@@ -75,9 +75,9 @@ xdelta3decode_CFLAGS = \ | |||
75 | -DVCDIFF_TOOLS=0 | 75 | -DVCDIFF_TOOLS=0 |
76 | 76 | ||
77 | xdelta3regtest_CXXFLAGS = \ | 77 | xdelta3regtest_CXXFLAGS = \ |
78 | $(CXX_WFLAGS) $(common_CFLAGS) -DNOT_MAIN=1 -DXD3_DEBUG=2 | 78 | $(CXX_WFLAGS) $(common_CFLAGS) -DNOT_MAIN=1 -DXD3_DEBUG=1 |
79 | xdelta3regtest_CFLAGS = \ | 79 | xdelta3regtest_CFLAGS = \ |
80 | $(C_WFLAGS) $(common_CFLAGS) -DNOT_MAIN=1 -DXD3_DEBUG=2 | 80 | $(C_WFLAGS) $(common_CFLAGS) -DNOT_MAIN=1 -DXD3_DEBUG=1 |
81 | xdelta3regtest_LDADD = -lm | 81 | xdelta3regtest_LDADD = -lm |
82 | 82 | ||
83 | man1_MANS = xdelta3.1 | 83 | man1_MANS = xdelta3.1 |
diff --git a/xdelta3/testing/regtest.cc b/xdelta3/testing/regtest.cc index eeb0e4b..23c985e 100644 --- a/xdelta3/testing/regtest.cc +++ b/xdelta3/testing/regtest.cc | |||
@@ -790,32 +790,34 @@ void TestSmallStride() { | |||
790 | usize_t size = Constants::BLOCK_SIZE * 4; | 790 | usize_t size = Constants::BLOCK_SIZE * 4; |
791 | spec0.GenerateFixedSize(size); | 791 | spec0.GenerateFixedSize(size); |
792 | 792 | ||
793 | /* TODO Need to study the actual causes of missed adds for tests | 793 | // Note: Not very good performance due to hash collisions, note 3x |
794 | * less than 30 bytes. */ | 794 | // multiplier below. |
795 | const int s = 30; | 795 | for (int s = 15; s < 101; s++) { |
796 | usize_t adds = 0; | 796 | usize_t changes = 0; |
797 | ChangeList cl; | 797 | ChangeList cl; |
798 | for (usize_t j = s; j < size; j += s, ++adds) | 798 | for (usize_t j = s; j < size; j += s, ++changes) |
799 | { | 799 | { |
800 | cl.push_back(Change(Change::MODIFY, 1, j)); | 800 | cl.push_back(Change(Change::MODIFY, 1, j)); |
801 | } | 801 | } |
802 | 802 | ||
803 | FileSpec spec1(&rand); | 803 | FileSpec spec1(&rand); |
804 | spec0.ModifyTo(ChangeListMutator(cl), &spec1); | 804 | spec0.ModifyTo(ChangeListMutator(cl), &spec1); |
805 | 805 | ||
806 | Options options; | 806 | Options options; |
807 | options.encode_srcwin_maxsz = size; | 807 | options.encode_srcwin_maxsz = size; |
808 | options.iopt_size = 128; | 808 | options.iopt_size = 128; |
809 | options.smatch_cfg = XD3_SMATCH_SLOW; | 809 | options.smatch_cfg = XD3_SMATCH_SLOW; |
810 | options.size_known = false; | 810 | options.size_known = false; |
811 | 811 | ||
812 | Block block; | 812 | Block block; |
813 | InMemoryEncodeDecode(spec0, spec1, &block, options); | 813 | InMemoryEncodeDecode(spec0, spec1, &block, options); |
814 | Delta delta(block); | 814 | Delta delta(block); |
815 | 815 | ||
816 | // Allow an additional two byte of add per window | 816 | IF_DEBUG1(DP(RINT "[stride=%d] changes=%u adds=%"Q"u\n", |
817 | usize_t allowance = 2 * size / Constants::WINDOW_SIZE; | 817 | s, changes, delta.AddedBytes())); |
818 | CHECK_GE(adds + allowance, delta.AddedBytes()); | 818 | double allowance = Constants::BLOCK_SIZE < 8192 ? 3.0 : 1.1; |
819 | CHECK_GE(allowance, (double)delta.AddedBytes()); | ||
820 | } | ||
819 | } | 821 | } |
820 | 822 | ||
821 | void TestCopyWindow() { | 823 | void TestCopyWindow() { |
@@ -927,85 +929,73 @@ void TestCopyFromEnd() { | |||
927 | } | 929 | } |
928 | 930 | ||
929 | void TestHalfBlockCopy() { | 931 | void TestHalfBlockCopy() { |
930 | MTRandom rand; | 932 | // Create a half-block copy, 7.5 blocks apart, in a pair of files: |
931 | FileSpec spec0(&rand); | 933 | // 0 1 ... 6 7 |
932 | FileSpec spec1(&rand); | 934 | // spec0 [bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb][ccccc][bbbb_] |
933 | 935 | // spec1 [aaaaa][ccccc][aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa_] | |
934 | // The test takes place over four blocks, but we create a 8-block | 936 | // where stage= |
935 | // file to ensure that the whole input doesn't fit in memory. | 937 | // 0: the final block is full |
936 | spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 8); | 938 | // a. (source)spec1->(target)spec0 copies block C: reads 8 source |
937 | 939 | // blocks during target block 0. | |
938 | // Create a half-block copy, 2.5 blocks apart, from the second half | 940 | // b. (source)spec0->(target)spec1 does not copy block C b/c attempt |
939 | // of the source version to the first half of the target version. | 941 | // to read past EOF empties block 0 from (virtual) block cache |
940 | // 0 1 2 3 | 942 | // 1: the final block is less than full. |
941 | // spec0 [bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb][ccccc][bbbbb...] | 943 | // a. (same) copies block C |
942 | // spec1 [aaaaa][ccccc][aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...] | 944 | // b. (same) copies block C, unlike 0a, no attempt to read past EOF |
943 | ChangeList cl1; | 945 | // |
944 | cl1.push_back(Change(Change::MODIFY, | 946 | // "virtual" above refers to XD3_TOOFARBACK, since there is no caching |
945 | Constants::BLOCK_SIZE / 2, // size | 947 | // in the API, there is simply a promise not to request blocks that are |
946 | 0)); | 948 | // beyond source->max_winsize from the last known source file position. |
947 | cl1.push_back(Change(Change::COPYOVER, | 949 | for (int stage = 0; stage < 2; stage++) |
948 | Constants::BLOCK_SIZE / 2, // size | ||
949 | Constants::BLOCK_SIZE * 3, // offset | ||
950 | Constants::BLOCK_SIZE / 2)); | ||
951 | cl1.push_back(Change(Change::MODIFY, | ||
952 | Constants::BLOCK_SIZE * 7, | ||
953 | Constants::BLOCK_SIZE)); | ||
954 | spec0.ModifyTo(ChangeListMutator(cl1), &spec1); | ||
955 | |||
956 | const int nocopy_adds = 8 * Constants::BLOCK_SIZE; | ||
957 | const int onecopy_adds = nocopy_adds - Constants::BLOCK_SIZE / 2; | ||
958 | |||
959 | // TODO Note restricted loop | ||
960 | for (int b = 4; b <= 4; b++) | ||
961 | { | 950 | { |
951 | IF_DEBUG1 (DP(RINT "half_block_copy stage %d\n", stage)); | ||
952 | |||
953 | MTRandom rand; | ||
954 | FileSpec spec0(&rand); | ||
955 | FileSpec spec1(&rand); | ||
956 | |||
957 | spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 8 - stage); | ||
958 | |||
959 | ChangeList cl1; | ||
960 | cl1.push_back(Change(Change::MODIFY, | ||
961 | Constants::BLOCK_SIZE / 2, // size | ||
962 | 0)); | ||
963 | cl1.push_back(Change(Change::COPYOVER, | ||
964 | Constants::BLOCK_SIZE / 2, // size | ||
965 | Constants::BLOCK_SIZE * 7, // offset | ||
966 | Constants::BLOCK_SIZE / 2)); | ||
967 | cl1.push_back(Change(Change::MODIFY, | ||
968 | Constants::BLOCK_SIZE * 7, | ||
969 | Constants::BLOCK_SIZE - stage)); | ||
970 | spec0.ModifyTo(ChangeListMutator(cl1), &spec1); | ||
971 | |||
962 | Options options; | 972 | Options options; |
963 | options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * b; | 973 | options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * 8; |
964 | 974 | ||
965 | Block block0; | 975 | Block block0; |
966 | Block block1; | 976 | Block block1; |
967 | InMemoryEncodeDecode(spec0, spec1, &block0, options); | 977 | InMemoryEncodeDecode(spec0, spec1, &block0, options); |
968 | InMemoryEncodeDecode(spec1, spec0, &block1, options); | 978 | InMemoryEncodeDecode(spec1, spec0, &block1, options); |
979 | |||
969 | Delta delta0(block0); | 980 | Delta delta0(block0); |
970 | Delta delta1(block1); | 981 | Delta delta1(block1); |
971 | 982 | ||
972 | // The first block never copies from the last source block, by | 983 | const int yes = |
973 | // design, because if the last source block is available when | 984 | Constants::BLOCK_SIZE * 8 - Constants::BLOCK_SIZE / 2; |
974 | // the first target block is ready, the caller is expected to | 985 | const int no = |
975 | // use a single block. | 986 | Constants::BLOCK_SIZE * 8 - Constants::BLOCK_SIZE / 2; |
976 | CHECK_EQ(nocopy_adds, delta0.AddedBytes()); | 987 | |
977 | if (Constants::BLOCK_SIZE < 8192 || b > 3) | 988 | if (stage == 0) |
978 | { | 989 | { |
979 | // For small-block inputs, the entire file is read into one | 990 | CHECK_EQ(yes, delta0.AddedBytes()); |
980 | // block (the min source window size is 16kB). | 991 | CHECK_EQ(no, delta1.AddedBytes()); |
981 | // | 992 | } |
982 | // For large blocks, at least 4 blocks of source window are | ||
983 | // needed. | ||
984 | CHECK_EQ(onecopy_adds, delta1.AddedBytes()); | ||
985 | } | ||
986 | else | 993 | else |
987 | { | 994 | { |
988 | // When there are fewer than 3 source blocks. | 995 | CHECK_EQ(yes, delta0.AddedBytes()); |
989 | CHECK_EQ(nocopy_adds, delta1.AddedBytes()); | 996 | CHECK_EQ(yes, delta1.AddedBytes()); |
990 | } | 997 | } |
991 | } | 998 | } |
992 | |||
993 | Options options; | ||
994 | options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * 4; | ||
995 | options.block_size = Constants::BLOCK_SIZE * 4; | ||
996 | |||
997 | // Test the whole-buffer case. | ||
998 | Block block0; | ||
999 | Block block1; | ||
1000 | InMemoryEncodeDecode(spec0, spec1, &block0, options); | ||
1001 | InMemoryEncodeDecode(spec1, spec0, &block1, options); | ||
1002 | Delta delta0(block0); | ||
1003 | Delta delta1(block1); | ||
1004 | // This <= >= are only for blocksize = 512, which has irregular readsize. | ||
1005 | CHECK_LE(onecopy_adds, delta0.AddedBytes()); | ||
1006 | CHECK_GE(onecopy_adds + 1, delta0.AddedBytes()); | ||
1007 | |||
1008 | CHECK_EQ(onecopy_adds, delta1.AddedBytes()); | ||
1009 | } | 999 | } |
1010 | 1000 | ||
1011 | void FourWayMergeTest(const FileSpec &spec0, | 1001 | void FourWayMergeTest(const FileSpec &spec0, |
@@ -1299,10 +1289,10 @@ int main(int argc, char **argv) | |||
1299 | mcmd.push_back("test"); | 1289 | mcmd.push_back("test"); |
1300 | mcmd.push_back(NULL); | 1290 | mcmd.push_back(NULL); |
1301 | 1291 | ||
1302 | // UnitTest<SmallBlock>(); | 1292 | UnitTest<SmallBlock>(); |
1303 | // MainTest<SmallBlock>(); | 1293 | MainTest<SmallBlock>(); |
1304 | // MainTest<MixedBlock>(); | 1294 | MainTest<MixedBlock>(); |
1305 | // MainTest<OversizeBlock>(); | 1295 | MainTest<OversizeBlock>(); |
1306 | MainTest<LargeBlock>(); | 1296 | MainTest<LargeBlock>(); |
1307 | 1297 | ||
1308 | CHECK_EQ(0, xd3_main_cmdline(mcmd.size() - 1, | 1298 | CHECK_EQ(0, xd3_main_cmdline(mcmd.size() - 1, |
@@ -1310,3 +1300,4 @@ int main(int argc, char **argv) | |||
1310 | 1300 | ||
1311 | return 0; | 1301 | return 0; |
1312 | } | 1302 | } |
1303 | |||
diff --git a/xdelta3/testing/test.h b/xdelta3/testing/test.h index d1f1a22..1eabcbd 100644 --- a/xdelta3/testing/test.h +++ b/xdelta3/testing/test.h | |||
@@ -22,8 +22,8 @@ extern "C" { | |||
22 | typeof(x) _y(y); \ | 22 | typeof(x) _y(y); \ |
23 | if (!(_x OP _y)) { \ | 23 | if (!(_x OP _y)) { \ |
24 | cerr << __FILE__ << ":" << __LINE__ << " Check failed: " << #x " " #OP " " #y << endl; \ | 24 | cerr << __FILE__ << ":" << __LINE__ << " Check failed: " << #x " " #OP " " #y << endl; \ |
25 | cerr << __FILE__ << ":" << __LINE__ << " Expected: " << _x << endl; \ | 25 | cerr << __FILE__ << ":" << __LINE__ << " {0} " << _x << endl; \ |
26 | cerr << __FILE__ << ":" << __LINE__ << " Actual: " << _y << endl; \ | 26 | cerr << __FILE__ << ":" << __LINE__ << " {1} " << _y << endl; \ |
27 | abort(); \ | 27 | abort(); \ |
28 | } } while (false) | 28 | } } while (false) |
29 | #undef CHECK | 29 | #undef CHECK |
diff --git a/xdelta3/xdelta3-decode.h b/xdelta3/xdelta3-decode.h index dc28323..6b3815f 100644 --- a/xdelta3/xdelta3-decode.h +++ b/xdelta3/xdelta3-decode.h | |||
@@ -207,9 +207,6 @@ xd3_decode_section (xd3_stream *stream, | |||
207 | /* No allocation/copy needed */ | 207 | /* No allocation/copy needed */ |
208 | section->buf = stream->next_in; | 208 | section->buf = stream->next_in; |
209 | sect_take = section->size; | 209 | sect_take = section->size; |
210 | |||
211 | IF_DEBUG2 (DP(RINT "[xd3_decode_section] copy==0 @ 0 %u\n", | ||
212 | sect_take, section->alloc1)); | ||
213 | } | 210 | } |
214 | else | 211 | else |
215 | { | 212 | { |
@@ -1166,8 +1163,8 @@ xd3_decode_input (xd3_stream *stream) | |||
1166 | &src->cpyoff_blocks, | 1163 | &src->cpyoff_blocks, |
1167 | &src->cpyoff_blkoff); | 1164 | &src->cpyoff_blkoff); |
1168 | 1165 | ||
1169 | IF_DEBUG1(DP(RINT | 1166 | IF_DEBUG2(DP(RINT |
1170 | "decode cpyoff %"Q"u " | 1167 | "[decode_cpyoff] %"Q"u " |
1171 | "cpyblkno %"Q"u " | 1168 | "cpyblkno %"Q"u " |
1172 | "cpyblkoff %u " | 1169 | "cpyblkoff %u " |
1173 | "blksize %u\n", | 1170 | "blksize %u\n", |
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c index 74889f2..2264e8e 100644 --- a/xdelta3/xdelta3.c +++ b/xdelta3/xdelta3.c | |||
@@ -522,7 +522,7 @@ static void xd3_verify_large_state (xd3_stream *stream, | |||
522 | uint32_t x_cksum); | 522 | uint32_t x_cksum); |
523 | static void xd3_verify_small_state (xd3_stream *stream, | 523 | static void xd3_verify_small_state (xd3_stream *stream, |
524 | const uint8_t *inp, | 524 | const uint8_t *inp, |
525 | uint32_t x_cksum); | 525 | uint32_t x_cksum); |
526 | 526 | ||
527 | #endif /* XD3_DEBUG */ | 527 | #endif /* XD3_DEBUG */ |
528 | #endif /* XD3_ENCODER */ | 528 | #endif /* XD3_ENCODER */ |
@@ -1906,7 +1906,7 @@ usize_t xd3_bytes_on_srcblk (xd3_source *src, xoff_t blkno) | |||
1906 | } | 1906 | } |
1907 | 1907 | ||
1908 | /* This function interfaces with the client getblk function, checks | 1908 | /* This function interfaces with the client getblk function, checks |
1909 | * its results, updates frontier_pos, max_blkno, onlastblk, eof_known. */ | 1909 | * its results, updates max_blkno, onlastblk, eof_known. */ |
1910 | static int | 1910 | static int |
1911 | xd3_getblk (xd3_stream *stream, xoff_t blkno) | 1911 | xd3_getblk (xd3_stream *stream, xoff_t blkno) |
1912 | { | 1912 | { |
@@ -1919,6 +1919,7 @@ xd3_getblk (xd3_stream *stream, xoff_t blkno) | |||
1919 | 1919 | ||
1920 | if (stream->getblk == NULL) | 1920 | if (stream->getblk == NULL) |
1921 | { | 1921 | { |
1922 | IF_DEBUG2 (DP(RINT "[getblk] XD3_GETSRCBLK %"Q"u\n", blkno)); | ||
1922 | stream->msg = "getblk source input"; | 1923 | stream->msg = "getblk source input"; |
1923 | return XD3_GETSRCBLK; | 1924 | return XD3_GETSRCBLK; |
1924 | } | 1925 | } |
@@ -1930,8 +1931,10 @@ xd3_getblk (xd3_stream *stream, xoff_t blkno) | |||
1930 | blkno, xd3_strerror (ret))); | 1931 | blkno, xd3_strerror (ret))); |
1931 | return ret; | 1932 | return ret; |
1932 | } | 1933 | } |
1934 | |||
1933 | IF_DEBUG2 (DP(RINT "[getblk] read source block %"Q"u onblk " | 1935 | IF_DEBUG2 (DP(RINT "[getblk] read source block %"Q"u onblk " |
1934 | "%u blksize %u\n", blkno, source->onblk, source->blksize)); | 1936 | "%u blksize %u max_blkno %"Q"u\n", blkno, source->onblk, |
1937 | source->blksize, source->max_blkno)); | ||
1935 | } | 1938 | } |
1936 | 1939 | ||
1937 | if (blkno > source->max_blkno) | 1940 | if (blkno > source->max_blkno) |
@@ -1960,9 +1963,8 @@ xd3_getblk (xd3_stream *stream, xoff_t blkno) | |||
1960 | if (blkno == source->max_blkno) | 1963 | if (blkno == source->max_blkno) |
1961 | { | 1964 | { |
1962 | /* In case the application sets the source as 1 block w/ a | 1965 | /* In case the application sets the source as 1 block w/ a |
1963 | preset buffer. */ | 1966 | * preset buffer. */ |
1964 | source->onlastblk = source->onblk; | 1967 | source->onlastblk = source->onblk; |
1965 | source->frontier_pos = (blkno + 1) << source->shiftby; | ||
1966 | } | 1968 | } |
1967 | return 0; | 1969 | return 0; |
1968 | } | 1970 | } |
@@ -1999,8 +2001,6 @@ xd3_set_source (xd3_stream *stream, | |||
1999 | IF_DEBUG1 (DP(RINT "raising src_maxsize to %u\n", src->blksize)); | 2001 | IF_DEBUG1 (DP(RINT "raising src_maxsize to %u\n", src->blksize)); |
2000 | } | 2002 | } |
2001 | src->max_winsize = xd3_max (src->max_winsize, XD3_ALLOCSIZE); | 2003 | src->max_winsize = xd3_max (src->max_winsize, XD3_ALLOCSIZE); |
2002 | src->frontier_pos = src->max_winsize; | ||
2003 | |||
2004 | return 0; | 2004 | return 0; |
2005 | } | 2005 | } |
2006 | 2006 | ||
@@ -2012,13 +2012,14 @@ xd3_set_source_and_size (xd3_stream *stream, | |||
2012 | if (ret == 0) | 2012 | if (ret == 0) |
2013 | { | 2013 | { |
2014 | stream->src->eof_known = 1; | 2014 | stream->src->eof_known = 1; |
2015 | IF_DEBUG2 (DP(RINT "[set source] size known %"Q"u\n", | ||
2016 | source_size)); | ||
2017 | 2015 | ||
2018 | xd3_blksize_div(source_size, | 2016 | xd3_blksize_div(source_size, |
2019 | stream->src, | 2017 | stream->src, |
2020 | &stream->src->max_blkno, | 2018 | &stream->src->max_blkno, |
2021 | &stream->src->onlastblk); | 2019 | &stream->src->onlastblk); |
2020 | |||
2021 | IF_DEBUG1 (DP(RINT "[set source] size known %"Q"u max_blkno %"Q"u\n", | ||
2022 | source_size, stream->src->max_blkno)); | ||
2022 | } | 2023 | } |
2023 | return ret; | 2024 | return ret; |
2024 | } | 2025 | } |
@@ -3206,6 +3207,7 @@ xd3_encode_input (xd3_stream *stream) | |||
3206 | * or else it can get stuck in a match-backward | 3207 | * or else it can get stuck in a match-backward |
3207 | * (getsrcblk) then match-forward (getsrcblk), | 3208 | * (getsrcblk) then match-forward (getsrcblk), |
3208 | * find insufficient match length, then repeat | 3209 | * find insufficient match length, then repeat |
3210 | |||
3209 | * exactly the same search. | 3211 | * exactly the same search. |
3210 | */ | 3212 | */ |
3211 | stream->input_position += stream->match_fwd; | 3213 | stream->input_position += stream->match_fwd; |
@@ -3231,7 +3233,7 @@ xd3_encode_input (xd3_stream *stream) | |||
3231 | 3233 | ||
3232 | case ENC_INSTR: | 3234 | case ENC_INSTR: |
3233 | /* Note: Jump here to encode VCDIFF deltas w/o using this | 3235 | /* Note: Jump here to encode VCDIFF deltas w/o using this |
3234 | * string-matching code. Merging code code enters here. */ | 3236 | * string-matching code. Merging code enters here. */ |
3235 | 3237 | ||
3236 | /* Flush the instrution buffer, then possibly add one more | 3238 | /* Flush the instrution buffer, then possibly add one more |
3237 | * instruction, then emit the header. */ | 3239 | * instruction, then emit the header. */ |
@@ -3686,6 +3688,7 @@ xd3_srcwin_setup (xd3_stream *stream) | |||
3686 | /* Otherwise, we have to make a guess. More copies may still be | 3688 | /* Otherwise, we have to make a guess. More copies may still be |
3687 | * issued, but we have to decide the source window base and length | 3689 | * issued, but we have to decide the source window base and length |
3688 | * now. */ | 3690 | * now. */ |
3691 | /* TODO: This may not working well in practice, more testing needed. */ | ||
3689 | src->srcbase = stream->match_minaddr; | 3692 | src->srcbase = stream->match_minaddr; |
3690 | src->srclen = xd3_max ((usize_t) length, | 3693 | src->srclen = xd3_max ((usize_t) length, |
3691 | stream->avail_in + (stream->avail_in >> 2)); | 3694 | stream->avail_in + (stream->avail_in >> 2)); |
@@ -3737,30 +3740,27 @@ xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos) | |||
3737 | * TestNonBlockingProgress test! */ | 3740 | * TestNonBlockingProgress test! */ |
3738 | if (srcpos != 0 && srcpos == stream->match_last_srcpos) | 3741 | if (srcpos != 0 && srcpos == stream->match_last_srcpos) |
3739 | { | 3742 | { |
3740 | IF_DEBUG1(DP(RINT "[match_setup] looping failure\n")); | 3743 | IF_DEBUG2(DP(RINT "[match_setup] looping failure\n")); |
3741 | goto bad; | 3744 | goto bad; |
3742 | } | 3745 | } |
3743 | 3746 | ||
3744 | /* Implement src->max_winsize, which prevents the encoder from seeking | 3747 | /* Implement src->max_winsize, which prevents the encoder from seeking |
3745 | * back further than the LRU cache maintaining FIFO discipline, (to | 3748 | * back further than the LRU cache maintaining FIFO discipline, (to |
3746 | * avoid seeking). */ | 3749 | * avoid seeking). */ |
3747 | XD3_ASSERT (srcpos <= src->frontier_pos); | 3750 | if (srcpos < stream->srcwin_cksum_pos && |
3748 | 3751 | stream->srcwin_cksum_pos - srcpos > src->max_winsize) | |
3749 | /* Prevent backwards seeks. This prevents an XD3_TOOFARBACK code | ||
3750 | (checked below). */ | ||
3751 | if (src->frontier_pos - srcpos > src->max_winsize) | ||
3752 | { | 3752 | { |
3753 | IF_DEBUG1(DP(RINT "[match_setup] rejected due to src->max_winsize " | 3753 | IF_DEBUG2(DP(RINT "[match_setup] rejected due to src->max_winsize " |
3754 | "distance eof=%"Q"u srcpos=%"Q"u frontier_pos=%"Q"u max_winsz=%"Q"u\n", | 3754 | "distance eof=%"Q"u srcpos=%"Q"u max_winsz=%"Q"u\n", |
3755 | xd3_source_eof (src), | 3755 | xd3_source_eof (src), |
3756 | srcpos, src->frontier_pos, src->max_winsize)); | 3756 | srcpos, src->max_winsize)); |
3757 | goto bad; | 3757 | goto bad; |
3758 | } | 3758 | } |
3759 | 3759 | ||
3760 | IF_DEBUG1(DP(RINT "[match_setup] %"Q"u frontier_pos %"Q"u, srcpos %"Q"u, " | 3760 | IF_DEBUG2(DP(RINT "[match_setup] %"Q"u srcpos %"Q"u, " |
3761 | "src->max_winsize %"Q"u\n", | 3761 | "src->max_winsize %"Q"u\n", |
3762 | stream->total_in + stream->input_position, | 3762 | stream->total_in + stream->input_position, |
3763 | src->frontier_pos, srcpos, src->max_winsize)); | 3763 | srcpos, src->max_winsize)); |
3764 | 3764 | ||
3765 | /* Going backwards, the 1.5-pass algorithm allows some | 3765 | /* Going backwards, the 1.5-pass algorithm allows some |
3766 | * already-matched input may be covered by a longer source match. | 3766 | * already-matched input may be covered by a longer source match. |
@@ -3937,7 +3937,7 @@ xd3_source_extend_match (xd3_stream *stream) | |||
3937 | if (stream->match_state == MATCH_BACKWARD) | 3937 | if (stream->match_state == MATCH_BACKWARD) |
3938 | { | 3938 | { |
3939 | /* Note: this code is practically duplicated below, substituting | 3939 | /* Note: this code is practically duplicated below, substituting |
3940 | * match_fwd/match_back and direction. TODO: Consolidate? */ | 3940 | * match_fwd/match_back and direction. */ |
3941 | matchoff = stream->match_srcpos - stream->match_back; | 3941 | matchoff = stream->match_srcpos - stream->match_back; |
3942 | streamoff = stream->input_position - stream->match_back; | 3942 | streamoff = stream->input_position - stream->match_back; |
3943 | xd3_blksize_div (matchoff, src, &tryblk, &tryoff); | 3943 | xd3_blksize_div (matchoff, src, &tryblk, &tryoff); |
@@ -3956,10 +3956,8 @@ xd3_source_extend_match (xd3_stream *stream) | |||
3956 | { | 3956 | { |
3957 | if (ret == XD3_TOOFARBACK) | 3957 | if (ret == XD3_TOOFARBACK) |
3958 | { | 3958 | { |
3959 | IF_DEBUG1({ | 3959 | IF_DEBUG1(DP(RINT "[maxback] frontier block %u TOOFARBACK block %u\n", |
3960 | DP(RINT "[maxback] frontier block %u TOOFARBACK block %u\n", | 3960 | stream->src->frontier_pos >> stream->src->shiftby, tryblk)); |
3961 | stream->src->frontier_pos >> stream->src->shiftby, tryblk); | ||
3962 | }); | ||
3963 | /* the starting position is too far back. */ | 3961 | /* the starting position is too far back. */ |
3964 | if (stream->match_back == 0) | 3962 | if (stream->match_back == 0) |
3965 | { | 3963 | { |
@@ -4343,13 +4341,14 @@ xd3_verify_run_state (xd3_stream *stream, | |||
4343 | static int | 4341 | static int |
4344 | xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) | 4342 | xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) |
4345 | { | 4343 | { |
4346 | xoff_t logical_input_cksum_pos; | 4344 | /* the source file is indexed until this point */ |
4345 | xoff_t target_cksum_pos; | ||
4346 | /* the absolute target file input position */ | ||
4347 | xoff_t absolute_input_pos; | 4347 | xoff_t absolute_input_pos; |
4348 | xoff_t source_size; | ||
4349 | 4348 | ||
4350 | if (stream->src->eof_known) | 4349 | if (stream->src->eof_known) |
4351 | { | 4350 | { |
4352 | source_size = xd3_source_eof (stream->src); | 4351 | xoff_t source_size = xd3_source_eof (stream->src); |
4353 | XD3_ASSERT(stream->srcwin_cksum_pos <= source_size); | 4352 | XD3_ASSERT(stream->srcwin_cksum_pos <= source_size); |
4354 | 4353 | ||
4355 | if (stream->srcwin_cksum_pos == source_size) | 4354 | if (stream->srcwin_cksum_pos == source_size) |
@@ -4361,30 +4360,29 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) | |||
4361 | 4360 | ||
4362 | absolute_input_pos = stream->total_in + stream->input_position; | 4361 | absolute_input_pos = stream->total_in + stream->input_position; |
4363 | 4362 | ||
4364 | /* Begin by advancing at twice the input rate, up to half the | 4363 | /* Immediately read the entire window. |
4365 | * maximum window size. */ | 4364 | * |
4366 | #if 1 | 4365 | * Note: this reverses a long held policy, at this point in the |
4367 | if (absolute_input_pos < stream->src->max_winsize) { | 4366 | * code, of advancing relatively slowly as the input is read, which |
4368 | logical_input_cksum_pos = stream->src->max_winsize; | 4367 | * results in better compression for very-similar inputs, but worse |
4369 | } else { | 4368 | * compression where data is deleted near the beginning of the file. |
4370 | logical_input_cksum_pos = absolute_input_pos + stream->src->max_winsize / 2; | 4369 | * |
4371 | } | 4370 | * The new policy is slower and may benefit, or slightly worsen, |
4372 | #else | 4371 | * compression performance. TODO test these changes in 3.0.10 to |
4373 | logical_input_cksum_pos = xd3_min(absolute_input_pos * 2, | 4372 | * 3.0.11 releases. */ |
4374 | absolute_input_pos + (stream->src->max_winsize / 2)); | 4373 | if (absolute_input_pos < stream->src->max_winsize / 2) |
4375 | #endif | 4374 | { |
4376 | 4375 | target_cksum_pos = stream->src->max_winsize; | |
4377 | /* If srcwin_cksum_pos is already greater, wait until the difference | 4376 | } |
4378 | * is met. */ | 4377 | else |
4379 | if (stream->srcwin_cksum_pos > logical_input_cksum_pos) | ||
4380 | { | 4378 | { |
4381 | *next_move_point = stream->input_position + | 4379 | target_cksum_pos = absolute_input_pos + stream->src->max_winsize / 2; |
4382 | (usize_t)(stream->srcwin_cksum_pos - logical_input_cksum_pos); | 4380 | target_cksum_pos &= ~stream->src->maskby; |
4383 | IF_DEBUG1 (DP(RINT | ||
4384 | "[srcwin_move_point] %"Q"u cksum_pos greater than logical pos %"Q"u\n", | ||
4385 | stream->srcwin_cksum_pos, logical_input_cksum_pos)); | ||
4386 | return 0; | ||
4387 | } | 4381 | } |
4382 | |||
4383 | /* If srcwin_cksum_pos is already greater, wait until the difference | ||
4384 | * is met. */ | ||
4385 | XD3_ASSERT (stream->srcwin_cksum_pos <= target_cksum_pos); | ||
4388 | 4386 | ||
4389 | /* A long match may have extended past srcwin_cksum_pos. Don't | 4387 | /* A long match may have extended past srcwin_cksum_pos. Don't |
4390 | * start checksumming already-matched source data. */ | 4388 | * start checksumming already-matched source data. */ |
@@ -4393,27 +4391,12 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) | |||
4393 | stream->srcwin_cksum_pos = stream->maxsrcaddr; | 4391 | stream->srcwin_cksum_pos = stream->maxsrcaddr; |
4394 | } | 4392 | } |
4395 | 4393 | ||
4396 | if (logical_input_cksum_pos < stream->srcwin_cksum_pos) | 4394 | if (target_cksum_pos < stream->srcwin_cksum_pos) |
4397 | { | 4395 | { |
4398 | logical_input_cksum_pos = stream->srcwin_cksum_pos; | 4396 | target_cksum_pos = stream->srcwin_cksum_pos; |
4399 | } | 4397 | } |
4400 | 4398 | ||
4401 | /* Advance at least one source block. With the command-line | 4399 | while (stream->srcwin_cksum_pos < target_cksum_pos && |
4402 | * defaults this means: | ||
4403 | * | ||
4404 | * if (src->size <= src->max_winsize), index the entire source at once | ||
4405 | * using the position of the first non-match. This is good for | ||
4406 | * small inputs, especially when the content may have moved anywhere | ||
4407 | * in the file (e.g., tar files). | ||
4408 | * | ||
4409 | * if (src->size > src->max_winsize), index at least one block ahead | ||
4410 | * of the logical position. This is good for different reasons: | ||
4411 | * when a long match spanning several source blocks is encountered, | ||
4412 | * this avoids computing checksums for those blocks. | ||
4413 | */ | ||
4414 | logical_input_cksum_pos += stream->src->blksize; | ||
4415 | |||
4416 | while (stream->srcwin_cksum_pos < logical_input_cksum_pos && | ||
4417 | (!stream->src->eof_known || | 4400 | (!stream->src->eof_known || |
4418 | stream->srcwin_cksum_pos < xd3_source_eof (stream->src))) | 4401 | stream->srcwin_cksum_pos < xd3_source_eof (stream->src))) |
4419 | { | 4402 | { |
@@ -4437,17 +4420,17 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) | |||
4437 | } | 4420 | } |
4438 | 4421 | ||
4439 | IF_DEBUG1 (DP(RINT | 4422 | IF_DEBUG1 (DP(RINT |
4440 | "[srcwin_move_point] async getblk return for %"Q"u\n", | 4423 | "[srcwin_move_point] async getblk return for %"Q"u: %s\n", |
4441 | blkno)); | 4424 | blkno, xd3_strerror (ret))); |
4442 | |||
4443 | return ret; | 4425 | return ret; |
4444 | } | 4426 | } |
4445 | 4427 | ||
4446 | IF_DEBUG1 (DP(RINT | 4428 | IF_DEBUG1 (DP(RINT |
4447 | "[srcwin_move_point] T=%"Q"u S=%"Q"u L=%"Q"u EOF=%"Q"u %s\n", | 4429 | "[srcwin_move_point] block %"Q"u T=%"Q"u S=%"Q"u L=%"Q"u EOF=%"Q"u %s\n", |
4430 | blkno, | ||
4448 | stream->total_in + stream->input_position, | 4431 | stream->total_in + stream->input_position, |
4449 | stream->srcwin_cksum_pos, | 4432 | stream->srcwin_cksum_pos, |
4450 | logical_input_cksum_pos, | 4433 | target_cksum_pos, |
4451 | xd3_source_eof (stream->src), | 4434 | xd3_source_eof (stream->src), |
4452 | stream->src->eof_known ? "known" : "unknown")); | 4435 | stream->src->eof_known ? "known" : "unknown")); |
4453 | 4436 | ||
@@ -4456,7 +4439,7 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) | |||
4456 | if (blkpos < (ssize_t) stream->smatcher.large_look) | 4439 | if (blkpos < (ssize_t) stream->smatcher.large_look) |
4457 | { | 4440 | { |
4458 | stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize; | 4441 | stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize; |
4459 | IF_DEBUG1 (DP(RINT "[srcwin_move_point] continue (end-of-block)\n")); | 4442 | IF_DEBUG2 (DP(RINT "[srcwin_move_point] continue (end-of-block): %"Q"u\n", blkpos)); |
4460 | continue; | 4443 | continue; |
4461 | } | 4444 | } |
4462 | 4445 | ||
@@ -4491,19 +4474,9 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) | |||
4491 | stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize; | 4474 | stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize; |
4492 | } | 4475 | } |
4493 | 4476 | ||
4494 | IF_DEBUG1 (DP(RINT | ||
4495 | "[srcwin_move_point] exited loop T=%"Q"u " | ||
4496 | "S=%"Q"u L=%"Q"u EOF=%"Q"u %s\n", | ||
4497 | stream->total_in + stream->input_position, | ||
4498 | stream->srcwin_cksum_pos, | ||
4499 | logical_input_cksum_pos, | ||
4500 | xd3_source_eof (stream->src), | ||
4501 | stream->src->eof_known ? "known" : "unknown")); | ||
4502 | |||
4503 | if (stream->src->eof_known) | 4477 | if (stream->src->eof_known) |
4504 | { | 4478 | { |
4505 | source_size = xd3_source_eof (stream->src); | 4479 | xoff_t source_size = xd3_source_eof (stream->src); |
4506 | |||
4507 | if (stream->srcwin_cksum_pos >= source_size) | 4480 | if (stream->srcwin_cksum_pos >= source_size) |
4508 | { | 4481 | { |
4509 | /* This invariant is needed for xd3_source_cksum_offset() */ | 4482 | /* This invariant is needed for xd3_source_cksum_offset() */ |
@@ -4516,9 +4489,21 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point) | |||
4516 | } | 4489 | } |
4517 | 4490 | ||
4518 | /* How long until this function should be called again. */ | 4491 | /* How long until this function should be called again. */ |
4519 | XD3_ASSERT(stream->srcwin_cksum_pos >= logical_input_cksum_pos); | 4492 | XD3_ASSERT(stream->srcwin_cksum_pos >= target_cksum_pos); |
4520 | *next_move_point = stream->input_position + 1 + | 4493 | |
4521 | (usize_t)(stream->srcwin_cksum_pos - logical_input_cksum_pos); | 4494 | *next_move_point = stream->input_position + stream->src->blksize / 2 - |
4495 | (stream->input_position & stream->src->maskby); | ||
4496 | |||
4497 | IF_DEBUG2 (DP(RINT | ||
4498 | "[srcwin_move_point] finished T=%"Q"u " | ||
4499 | "S=%"Q"u L=%"Q"u EOF=%"Q"u %s again in %u\n", | ||
4500 | stream->total_in + stream->input_position, | ||
4501 | stream->srcwin_cksum_pos, | ||
4502 | target_cksum_pos, | ||
4503 | xd3_source_eof (stream->src), | ||
4504 | stream->src->eof_known ? "known" : "unknown", | ||
4505 | *next_move_point - stream->input_position)); | ||
4506 | |||
4522 | return 0; | 4507 | return 0; |
4523 | } | 4508 | } |
4524 | 4509 | ||
@@ -4577,6 +4562,8 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream) | |||
4577 | usize_t match_offset = 0; | 4562 | usize_t match_offset = 0; |
4578 | usize_t next_move_point; | 4563 | usize_t next_move_point; |
4579 | 4564 | ||
4565 | IF_DEBUG2(DP(RINT "[string_match] initial entry %u\n", stream->input_position)); | ||
4566 | |||
4580 | /* If there will be no compression due to settings or short input, | 4567 | /* If there will be no compression due to settings or short input, |
4581 | * skip it entirely. */ | 4568 | * skip it entirely. */ |
4582 | if (! (DO_SMALL || DO_LARGE || DO_RUN) || | 4569 | if (! (DO_SMALL || DO_LARGE || DO_RUN) || |
@@ -4588,6 +4575,8 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream) | |||
4588 | * needs to be reset. */ | 4575 | * needs to be reset. */ |
4589 | restartloop: | 4576 | restartloop: |
4590 | 4577 | ||
4578 | IF_DEBUG2(DP(RINT "[string_match] restartloop %u\n", stream->input_position)); | ||
4579 | |||
4591 | /* If there is not enough input remaining for any kind of match, | 4580 | /* If there is not enough input remaining for any kind of match, |
4592 | skip it. */ | 4581 | skip it. */ |
4593 | if (stream->input_position + SLOOK > stream->avail_in) { goto loopnomore; } | 4582 | if (stream->input_position + SLOOK > stream->avail_in) { goto loopnomore; } |
@@ -4631,7 +4620,9 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream) | |||
4631 | { | 4620 | { |
4632 | /* Source window: next_move_point is the point that | 4621 | /* Source window: next_move_point is the point that |
4633 | * stream->input_position must reach before computing more | 4622 | * stream->input_position must reach before computing more |
4634 | * source checksum. */ | 4623 | * source checksum. Note: this is called unconditionally |
4624 | * the first time after reentry, subsequent calls will be | ||
4625 | * avoided if next_move_point is > input_position */ | ||
4635 | if ((ret = xd3_srcwin_move_point (stream, & next_move_point))) | 4626 | if ((ret = xd3_srcwin_move_point (stream, & next_move_point))) |
4636 | { | 4627 | { |
4637 | return ret; | 4628 | return ret; |
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h index 1aef6be..6cc0f9f 100644 --- a/xdelta3/xdelta3.h +++ b/xdelta3/xdelta3.h | |||
@@ -783,9 +783,6 @@ struct _xd3_source | |||
783 | xoff_t max_blkno; /* Maximum block, if eof is known, | 783 | xoff_t max_blkno; /* Maximum block, if eof is known, |
784 | * otherwise, equals frontier_blkno | 784 | * otherwise, equals frontier_blkno |
785 | * (initially 0). */ | 785 | * (initially 0). */ |
786 | xoff_t frontier_pos; /* The next source position to be | ||
787 | * read, equal to ((max_blkno+1) | ||
788 | * << shiftby) */ | ||
789 | usize_t onlastblk; /* Number of bytes on max_blkno */ | 786 | usize_t onlastblk; /* Number of bytes on max_blkno */ |
790 | int eof_known; /* Set to true when the first | 787 | int eof_known; /* Set to true when the first |
791 | * partial block is read. */ | 788 | * partial block is read. */ |