summaryrefslogtreecommitdiff
path: root/testing/regtest.cc
diff options
context:
space:
mode:
Diffstat (limited to 'testing/regtest.cc')
-rw-r--r--testing/regtest.cc289
1 files changed, 164 insertions, 125 deletions
diff --git a/testing/regtest.cc b/testing/regtest.cc
index 84ee100..b2cdaa5 100644
--- a/testing/regtest.cc
+++ b/testing/regtest.cc
@@ -12,12 +12,14 @@ public:
Options()
: encode_srcwin_maxsz(1<<20),
block_size(Constants::BLOCK_SIZE),
+ window_size(Constants::WINDOW_SIZE),
size_known(false),
iopt_size(XD3_DEFAULT_IOPT_SIZE),
smatch_cfg(XD3_SMATCH_DEFAULT) { }
xoff_t encode_srcwin_maxsz;
size_t block_size;
+ xoff_t window_size;
bool size_known;
usize_t iopt_size;
xd3_smatch_cfg smatch_cfg;
@@ -56,7 +58,7 @@ public:
xd3_init_config(&encode_config, XD3_ADLER32);
xd3_init_config(&decode_config, XD3_ADLER32);
- encode_config.winsize = Constants::WINDOW_SIZE;
+ encode_config.winsize = options.window_size;
encode_config.iopt_size = options.iopt_size;
encode_config.smatch_cfg = options.smatch_cfg;
@@ -90,7 +92,7 @@ public:
bool done = false;
bool done_after_input = false;
- IF_DEBUG1 (XPR(NTR "source %"Q"u[%"Q"u] target %"Q"u winsize %lu\n",
+ IF_DEBUG1 (XPR(NTR "source %"Q"u[%"Q"u] target %"Q"u winsize %"Z"u\n",
source_file.Size(), options.block_size,
target_file.Size(),
Constants::WINDOW_SIZE));
@@ -151,11 +153,11 @@ public:
xd3_source *src = (encoding ? &encode_source : &decode_source);
Block *block = (encoding ? &encode_source_block : &decode_source_block);
if (encoding) {
- IF_DEBUG1(XPR(NTR "[srcblock] %"Q"u last srcpos %"Q"u "
- "encodepos %"Q"u\n",
- encode_source.getblkno,
- encode_stream.match_last_srcpos,
- encode_stream.input_position + encode_stream.total_in));
+ IF_DEBUG2(XPR(NTR "[srcblock] %"Q"u last srcpos %"Q"u "
+ "encodepos %"Q"u\n",
+ encode_source.getblkno,
+ encode_stream.match_last_srcpos,
+ encode_stream.input_position + encode_stream.total_in));
}
source_iterator.SetBlock(src->getblkno);
@@ -228,10 +230,10 @@ public:
ExtFile *coded_data,
const Options &options) {
vector<const char*> ecmd;
- char wbuf[16];
- snprintf(wbuf, sizeof(wbuf), "-B%"Q"u", options.encode_srcwin_maxsz);
+ char bbuf[16];
+ snprintf(bbuf, sizeof(bbuf), "-B%"Q"u", options.encode_srcwin_maxsz);
ecmd.push_back("xdelta3");
- ecmd.push_back(wbuf);
+ ecmd.push_back(bbuf);
ecmd.push_back("-s");
ecmd.push_back(source_file.Name());
ecmd.push_back(target_file.Name());
@@ -244,7 +246,7 @@ public:
vector<const char*> dcmd;
ExtFile recon_file;
dcmd.push_back("xdelta3");
- ecmd.push_back(wbuf);
+ ecmd.push_back(bbuf);
dcmd.push_back("-d");
dcmd.push_back("-s");
dcmd.push_back(source_file.Name());
@@ -364,28 +366,37 @@ public:
CHECK_EQ(0, CmpDifferentBlockBytes(to, recon));
}
- //////////////////////////////////////////////////////////////////////
+//////////////////////////////////////////////////////////////////////
- void TestRandomNumbers() {
- MTRandom rand;
- int rounds = 1<<20;
- uint64_t usum = 0;
- uint64_t esum = 0;
+void TestPrintf() {
+ char buf[64];
+ xoff_t x = XOFF_T_MAX;
+ snprintf_func (buf, sizeof(buf), "%"Q"u", x);
+ const char *expect = XD3_USE_LARGEFILE64 ?
+ "18446744073709551615" : "4294967295";
+ XD3_ASSERT(strcmp (buf, expect) == 0);
+}
- for (int i = 0; i < rounds; i++) {
- usum += rand.Rand32();
- esum += rand.ExpRand32(1024);
- }
+void TestRandomNumbers() {
+ MTRandom rand;
+ int rounds = 1<<20;
+ uint64_t usum = 0;
+ uint64_t esum = 0;
+
+ for (int i = 0; i < rounds; i++) {
+ usum += rand.Rand32();
+ esum += rand.ExpRand32(1024);
+ }
- double allowed_error = 0.01;
+ double allowed_error = 0.01;
- uint32_t umean = usum / rounds;
- uint32_t emean = esum / rounds;
+ uint32_t umean = usum / rounds;
+ uint32_t emean = esum / rounds;
- uint32_t uexpect = UINT32_MAX / 2;
- uint32_t eexpect = 1024;
+ uint32_t uexpect = UINT32_MAX / 2;
+ uint32_t eexpect = 1024;
- if (umean < uexpect * (1.0 - allowed_error) ||
+ if (umean < uexpect * (1.0 - allowed_error) ||
umean > uexpect * (1.0 + allowed_error)) {
XPR(NT "uniform mean error: %u != %u\n", umean, uexpect);
abort();
@@ -574,7 +585,7 @@ void TestDeleteMutator() {
for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
ChangeList cl1;
- cl1.push_back(Change(Change::DELETE, test_cases[i].size,
+ cl1.push_back(Change(Change::DELRANGE, test_cases[i].size,
test_cases[i].addr));
spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
CHECK_EQ(spec0.Size() - test_cases[i].size, spec1.Size());
@@ -779,32 +790,34 @@ void TestSmallStride() {
usize_t size = Constants::BLOCK_SIZE * 4;
spec0.GenerateFixedSize(size);
- /* TODO Need to study the actual causes of missed adds for tests
- * less than 30 bytes. */
- const int s = 30;
- usize_t adds = 0;
- ChangeList cl;
- for (usize_t j = s; j < size; j += s, ++adds)
- {
- cl.push_back(Change(Change::MODIFY, 1, j));
- }
+ // Note: Not very good performance due to hash collisions, note 3x
+ // multiplier below.
+ for (int s = 15; s < 101; s++) {
+ usize_t changes = 0;
+ ChangeList cl;
+ for (usize_t j = s; j < size; j += s, ++changes)
+ {
+ cl.push_back(Change(Change::MODIFY, 1, j));
+ }
- FileSpec spec1(&rand);
- spec0.ModifyTo(ChangeListMutator(cl), &spec1);
+ FileSpec spec1(&rand);
+ spec0.ModifyTo(ChangeListMutator(cl), &spec1);
- Options options;
- options.encode_srcwin_maxsz = size;
- options.iopt_size = 128;
- options.smatch_cfg = XD3_SMATCH_SLOW;
- options.size_known = false;
+ Options options;
+ options.encode_srcwin_maxsz = size;
+ options.iopt_size = 128;
+ options.smatch_cfg = XD3_SMATCH_SLOW;
+ options.size_known = false;
- Block block;
- InMemoryEncodeDecode(spec0, spec1, &block, options);
- Delta delta(block);
+ Block block;
+ InMemoryEncodeDecode(spec0, spec1, &block, options);
+ Delta delta(block);
- // Allow an additional two byte of add per window
- usize_t allowance = 2 * size / Constants::WINDOW_SIZE;
- CHECK_GE(adds + allowance, delta.AddedBytes());
+ IF_DEBUG1(DP(RINT "[stride=%d] changes=%u adds=%"Q"u\n",
+ s, changes, delta.AddedBytes()));
+ double allowance = Constants::BLOCK_SIZE < 8192 || s < 30 ? 3.0 : 1.1;
+ CHECK_GE(allowance * changes, (double)delta.AddedBytes());
+ }
}
void TestCopyWindow() {
@@ -837,7 +850,6 @@ void TestCopyWindow() {
options.encode_srcwin_maxsz = size;
options.iopt_size = 128;
options.smatch_cfg = XD3_SMATCH_SLOW;
- options.size_known = false;
Block block1;
InMemoryEncodeDecode(spec0, spec1, &block1, options);
@@ -917,87 +929,73 @@ void TestCopyFromEnd() {
}
void TestHalfBlockCopy() {
- MTRandom rand;
- FileSpec spec0(&rand);
- FileSpec spec1(&rand);
-
- spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 4);
-
- // Create a half-block copy, 2.5 blocks apart, from the second half
- // of the source version to the first half of the target version.
- // 0 1 2 3
- // spec0 [bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb][ccccc][bbbbb]
- // spec1 [aaaaa][ccccc][aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa]
- ChangeList cl1;
- cl1.push_back(Change(Change::MODIFY,
- Constants::BLOCK_SIZE / 2, // size
- 0));
- cl1.push_back(Change(Change::COPYOVER,
- Constants::BLOCK_SIZE / 2, // size
- Constants::BLOCK_SIZE * 3, // offset
- Constants::BLOCK_SIZE / 2));
- cl1.push_back(Change(Change::MODIFY,
- Constants::BLOCK_SIZE * 3,
- Constants::BLOCK_SIZE));
- spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
-
- const int onecopy_adds =
- 4 * Constants::BLOCK_SIZE - Constants::BLOCK_SIZE / 2;
- const int nocopy_adds = 4 * Constants::BLOCK_SIZE;
-
- // Note the case b=4 is contrived: the caller should use a single block
- // containing the entire source, if possible.
- for (int b = 1; b <= 4; b++)
+ // Create a half-block copy, 7.5 blocks apart, in a pair of files:
+ // 0 1 ... 6 7
+ // spec0 [bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb][ccccc][bbbb_]
+ // spec1 [aaaaa][ccccc][aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa_]
+ // where stage=
+ // 0: the final block is full
+ // a. (source)spec1->(target)spec0 copies block C: reads 8 source
+ // blocks during target block 0.
+ // b. (source)spec0->(target)spec1 does not copy block C b/c attempt
+ // to read past EOF empties block 0 from (virtual) block cache
+ // 1: the final block is less than full.
+ // a. (same) copies block C
+ // b. (same) copies block C, unlike 0a, no attempt to read past EOF
+ //
+ // "virtual" above refers to XD3_TOOFARBACK, since there is no caching
+ // in the API, there is simply a promise not to request blocks that are
+ // beyond source->max_winsize from the last known source file position.
+ for (int stage = 0; stage < 2; stage++)
{
+ IF_DEBUG1 (DP(RINT "half_block_copy stage %d\n", stage));
+
+ MTRandom rand;
+ FileSpec spec0(&rand);
+ FileSpec spec1(&rand);
+
+ spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 8 - stage);
+
+ ChangeList cl1;
+ cl1.push_back(Change(Change::MODIFY,
+ Constants::BLOCK_SIZE / 2, // size
+ 0));
+ cl1.push_back(Change(Change::COPYOVER,
+ Constants::BLOCK_SIZE / 2, // size
+ Constants::BLOCK_SIZE * 7, // offset
+ Constants::BLOCK_SIZE / 2));
+ cl1.push_back(Change(Change::MODIFY,
+ Constants::BLOCK_SIZE * 7,
+ Constants::BLOCK_SIZE - stage));
+ spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
+
Options options;
- options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * b;
+ options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * 8;
Block block0;
Block block1;
InMemoryEncodeDecode(spec0, spec1, &block0, options);
InMemoryEncodeDecode(spec1, spec0, &block1, options);
+
Delta delta0(block0);
Delta delta1(block1);
- // The first block never copies from the last source block, by
- // design, because if the last source block is available when
- // the first target block is ready, the caller is expected to
- // use a single block.
- CHECK_EQ(nocopy_adds, delta0.AddedBytes());
- if (Constants::BLOCK_SIZE < 8192 || b > 2)
- {
- // For small-block inputs, the entire file is read into one
- // block (the min source window size is 16kB).
- //
- // For large blocks, at least 3 blocks of source window are
- // needed.
- CHECK_EQ(onecopy_adds, delta1.AddedBytes());
- }
+ const int yes =
+ Constants::BLOCK_SIZE * 8 - Constants::BLOCK_SIZE / 2;
+ const int no =
+ Constants::BLOCK_SIZE * 8 - Constants::BLOCK_SIZE / 2;
+
+ if (stage == 0)
+ {
+ CHECK_EQ(yes, delta0.AddedBytes());
+ CHECK_EQ(no, delta1.AddedBytes());
+ }
else
- {
- // When there are fewer than 3 source blocks.
- CHECK_EQ(nocopy_adds, delta1.AddedBytes());
- }
- // XPR(NT "0=%zu 1=%zu\n", delta0.AddedBytes(), delta1.AddedBytes());
+ {
+ CHECK_EQ(yes, delta0.AddedBytes());
+ CHECK_EQ(yes, delta1.AddedBytes());
+ }
}
-
- Options options;
- options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * 4;
- options.block_size = Constants::BLOCK_SIZE * 4;
-
- // Test the whole-buffer case.
- Block block0;
- Block block1;
- InMemoryEncodeDecode(spec0, spec1, &block0, options);
- InMemoryEncodeDecode(spec1, spec0, &block1, options);
- Delta delta0(block0);
- Delta delta1(block1);
- // This <= >= are only for blocksize = 512, which has irregular readsize.
- CHECK_LE(onecopy_adds, delta0.AddedBytes());
- CHECK_GE(onecopy_adds + 1, delta0.AddedBytes());
-
- CHECK_EQ(onecopy_adds, delta1.AddedBytes());
- // XPR(NT "0=%zu 1=%zu\n", delta0.AddedBytes(), delta1.AddedBytes());
}
void FourWayMergeTest(const FileSpec &spec0,
@@ -1130,7 +1128,7 @@ void TestMergeCommand1() {
}
cl1.push_back(Change(Change::ADD, change1, add1_pos));
- cl2.push_back(Change(Change::DELETE, change1, del2_pos));
+ cl2.push_back(Change(Change::DELRANGE, change1, del2_pos));
cl3.push_back(Change(Change::MODIFY, change3, change3_pos));
spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
@@ -1184,9 +1182,9 @@ void TestMergeCommand2() {
ChangeList cl1, cl2, cl3;
- cl1.push_back(Change(Change::DELETE, size0 - size1, 0));
- cl2.push_back(Change(Change::DELETE, size0 - size2, 0));
- cl3.push_back(Change(Change::DELETE, size0 - size3, 0));
+ cl1.push_back(Change(Change::DELRANGE, size0 - size1, 0));
+ cl2.push_back(Change(Change::DELRANGE, size0 - size2, 0));
+ cl3.push_back(Change(Change::DELRANGE, size0 - size3, 0));
spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
spec0.ModifyTo(ChangeListMutator(cl2), &spec2);
@@ -1200,6 +1198,44 @@ void TestMergeCommand2() {
}
}
+void TestLastFrontierBlock() {
+ // This test constructs an input that can expose
+ // https://github.com/jmacd/xdelta/issues/188
+ // when run through the command-line with source via a FIFO.
+ // That is not tested here, but the test stays.
+ if (Constants::WINDOW_SIZE < XD3_ALLOCSIZE)
+ {
+ return;
+ }
+
+ MTRandom rand;
+ FileSpec spec0(&rand);
+ FileSpec spec1(&rand);
+ const xoff_t size = XD3_ALLOCSIZE * 64; // == XD3_MINSRCWINSZ * 2
+ const xoff_t edit = XD3_ALLOCSIZE;
+
+ Options options;
+ options.encode_srcwin_maxsz = XD3_MINSRCWINSZ;
+ options.block_size = XD3_ALLOCSIZE;
+ options.window_size = XD3_MINSRCWINSZ;
+ options.size_known = false;
+
+ spec0.GenerateFixedSize(size);
+
+ ChangeList cl;
+
+ // Modify the 0th byte in order to induce indexing of subsequent
+ // bytes, but allow copying most of the file to keep the test fast.
+ cl.push_back(Change(Change::MODIFY, 1, edit * 31));
+ cl.push_back(Change(Change::COPYOVER, edit, edit * 31, edit * 63));
+
+ spec0.ModifyTo(ChangeListMutator(cl), &spec1);
+
+ Block noblock;
+ InMemoryEncodeDecode(spec0, spec1, &noblock, options);
+ InMemoryEncodeDecode(spec1, spec0, &noblock, options);
+}
+
}; // class Regtest<Constants>
#define TEST(x) XPR(NTR #x "...\n"); regtest.x()
@@ -1208,6 +1244,7 @@ void TestMergeCommand2() {
template <class T>
void UnitTest() {
Regtest<T> regtest;
+ TEST(TestPrintf);
TEST(TestRandomNumbers);
TEST(TestRandomFile);
TEST(TestFirstByte);
@@ -1222,7 +1259,7 @@ void UnitTest() {
// These are Xdelta tests.
template <class T>
void MainTest() {
- XPR(NT "Blocksize %"Q"u windowsize %"Q"u\n",
+ XPR(NT "Blocksize %"Q"u windowsize %"Z"u\n",
T::BLOCK_SIZE, T::WINDOW_SIZE);
Regtest<T> regtest;
TEST(TestEmptyInMemory);
@@ -1232,6 +1269,7 @@ void MainTest() {
TEST(TestCopyFromEnd);
TEST(TestNonBlocking);
TEST(TestHalfBlockCopy);
+ TEST(TestLastFrontierBlock);
TEST(TestMergeCommand1);
TEST(TestMergeCommand2);
}
@@ -1262,3 +1300,4 @@ int main(int argc, char **argv)
return 0;
}
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-09 04:07:01 +0000