From a96d62621beefe4aa20b696744be6325bc536fb6 Mon Sep 17 00:00:00 2001 From: Jun Wang Date: Wed, 18 May 2016 10:24:32 +0800 Subject: Import from upstream 3.1.0 --- testing/regtest.cc | 1306 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1306 insertions(+) create mode 100644 testing/regtest.cc (limited to 'testing/regtest.cc') diff --git a/testing/regtest.cc b/testing/regtest.cc new file mode 100644 index 0000000..dd2ab8d --- /dev/null +++ b/testing/regtest.cc @@ -0,0 +1,1306 @@ +/* -*- Mode: C++ -*- */ +#include "test.h" +#include "random.h" +#include "sizes.h" + +template +class Regtest { +public: + typedef typename Constants::Sizes Sizes; + + struct Options { + 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; + }; + +#include "segment.h" +#include "modify.h" +#include "file.h" +#include "cmp.h" +#include "delta.h" + + void InMemoryEncodeDecode(const FileSpec &source_file, + const FileSpec &target_file, + Block *coded_data, + const Options &options) { + xd3_stream encode_stream; + xd3_config encode_config; + xd3_source encode_source; + + xd3_stream decode_stream; + xd3_config decode_config; + xd3_source decode_source; + xoff_t verified_bytes = 0; + xoff_t encoded_bytes = 0; + + if (coded_data) { + coded_data->Reset(); + } + + memset(&encode_stream, 0, sizeof (encode_stream)); + memset(&encode_source, 0, sizeof (encode_source)); + + memset(&decode_stream, 0, sizeof (decode_stream)); + memset(&decode_source, 0, sizeof (decode_source)); + + xd3_init_config(&encode_config, XD3_ADLER32); + xd3_init_config(&decode_config, XD3_ADLER32); + + encode_config.winsize = options.window_size; + encode_config.iopt_size = options.iopt_size; + encode_config.smatch_cfg = options.smatch_cfg; + + CHECK_EQ(0, xd3_config_stream (&encode_stream, &encode_config)); + CHECK_EQ(0, xd3_config_stream (&decode_stream, &decode_config)); + + encode_source.blksize = options.block_size; + decode_source.blksize = options.block_size; + + encode_source.max_winsize = options.encode_srcwin_maxsz; + decode_source.max_winsize = options.encode_srcwin_maxsz; + + if (!options.size_known) + { + xd3_set_source (&encode_stream, &encode_source); + xd3_set_source (&decode_stream, &decode_source); + } + else + { + xd3_set_source_and_size (&encode_stream, &encode_source, + source_file.Size()); + xd3_set_source_and_size (&decode_stream, &decode_source, + source_file.Size()); + } + + BlockIterator source_iterator(source_file, options.block_size); + BlockIterator target_iterator(target_file, Constants::WINDOW_SIZE); + Block encode_source_block, decode_source_block; + Block decoded_block, target_block; + bool encoding = true; + bool done = false; + bool done_after_input = false; + + IF_DEBUG1 (XPR(NTR "source %" Q "u[%" Z "u] target %" Q "u winsize %" Z "u\n", + source_file.Size(), options.block_size, + target_file.Size(), + Constants::WINDOW_SIZE)); + + while (!done) { + target_iterator.Get(&target_block); + + xoff_t blks = target_iterator.Blocks(); + + IF_DEBUG2(XPR(NTR "target in %s: %" Q "u[%" Z "u] %" Q "u(%" Q "u) " + "verified %" Q "u\n", + encoding ? "encoding" : "decoding", + target_iterator.Offset(), + target_block.Size(), + target_iterator.Blkno(), + blks, + verified_bytes)); + + if (blks == 0 || target_iterator.Blkno() == (blks - 1)) { + xd3_set_flags(&encode_stream, XD3_FLUSH | encode_stream.flags); + } + + xd3_avail_input(&encode_stream, target_block.Data(), target_block.Size()); + encoded_bytes += target_block.Size(); + + process: + int ret; + const char *msg; + if (encoding) { + ret = xd3_encode_input(&encode_stream); + msg = encode_stream.msg; + } else { + ret = xd3_decode_input(&decode_stream); + msg = decode_stream.msg; + } + (void) msg; + + switch (ret) { + case XD3_OUTPUT: + if (encoding) { + if (coded_data != NULL) { + // Optional encoded-output to the caller + coded_data->Append(encode_stream.next_out, + encode_stream.avail_out); + } + // Feed this data to the decoder. + xd3_avail_input(&decode_stream, + encode_stream.next_out, + encode_stream.avail_out); + xd3_consume_output(&encode_stream); + encoding = false; + } else { + decoded_block.Append(decode_stream.next_out, + decode_stream.avail_out); + xd3_consume_output(&decode_stream); + } + goto process; + + case XD3_GETSRCBLK: { + xd3_source *src = (encoding ? &encode_source : &decode_source); + Block *block = (encoding ? &encode_source_block : &decode_source_block); + if (encoding) { + 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); + source_iterator.Get(block); + src->curblkno = src->getblkno; + src->onblk = block->Size(); + src->curblk = block->Data(); + + goto process; + } + + case XD3_INPUT: + if (!encoding) { + encoding = true; + goto process; + } else { + if (done_after_input) { + done = true; + continue; + } + + if (target_block.Size() < target_iterator.BlockSize()) { + encoding = false; + } else { + target_iterator.Next(); + } + continue; + } + + case XD3_WINFINISH: + if (encoding) { + if (encode_stream.flags & XD3_FLUSH) { + done_after_input = true; + } + encoding = false; + } else { + CHECK_EQ(0, CmpDifferentBlockBytesAtOffset(decoded_block, + target_file, + verified_bytes)); + verified_bytes += decoded_block.Size(); + decoded_block.Reset(); + encoding = true; + } + goto process; + + case XD3_WINSTART: + case XD3_GOTHEADER: + goto process; + + default: + XPR(NTR "%s = %s %s\n", encoding ? "E " : " D", + xd3_strerror(ret), + msg == NULL ? "" : msg); + + CHECK_EQ(0, ret); + CHECK_EQ(-1, ret); + } + } + + CHECK_EQ(target_file.Size(), encoded_bytes); + CHECK_EQ(target_file.Size(), verified_bytes); + CHECK_EQ(0, xd3_close_stream(&decode_stream)); + CHECK_EQ(0, xd3_close_stream(&encode_stream)); + xd3_free_stream(&encode_stream); + xd3_free_stream(&decode_stream); + } + + void MainEncodeDecode(const TmpFile &source_file, + const TmpFile &target_file, + ExtFile *coded_data, + const Options &options) { + vector ecmd; + char bbuf[16]; + snprintf(bbuf, sizeof(bbuf), "-B%" Q "u", options.encode_srcwin_maxsz); + ecmd.push_back("xdelta3"); + ecmd.push_back(bbuf); + ecmd.push_back("-s"); + ecmd.push_back(source_file.Name()); + ecmd.push_back(target_file.Name()); + ecmd.push_back(coded_data->Name()); + ecmd.push_back(NULL); + + CHECK_EQ(0, xd3_main_cmdline(ecmd.size() - 1, + const_cast(&ecmd[0]))); + + vector dcmd; + ExtFile recon_file; + dcmd.push_back("xdelta3"); + ecmd.push_back(bbuf); + dcmd.push_back("-d"); + dcmd.push_back("-s"); + dcmd.push_back(source_file.Name()); + dcmd.push_back(coded_data->Name()); + dcmd.push_back(recon_file.Name()); + dcmd.push_back(NULL); + + CHECK_EQ(0, xd3_main_cmdline(dcmd.size() - 1, + const_cast(&dcmd[0]))); + + CHECK_EQ(0, test_compare_files(recon_file.Name(), + target_file.Name())); + } + + // Similar to xd3_process_memory, with support for test Options. + // Exercises xd3_process_stream. + int TestProcessMemory (int is_encode, + int (*func) (xd3_stream *), + const uint8_t *input, + usize_t input_size, + const uint8_t *source, + usize_t source_size, + uint8_t *output, + usize_t *output_size, + usize_t output_size_max, + const Options &options) { + xd3_stream stream; + xd3_config config; + xd3_source src; + int ret; + + memset (& stream, 0, sizeof (stream)); + memset (& config, 0, sizeof (config)); + + if (is_encode) + { + config.winsize = input_size; + config.iopt_size = options.iopt_size; + config.sprevsz = xd3_pow2_roundup (config.winsize); + } + + if ((ret = xd3_config_stream (&stream, &config)) != 0) + { + goto exit; + } + + if (source != NULL) + { + memset (& src, 0, sizeof (src)); + + src.blksize = source_size; + src.onblk = source_size; + src.curblk = source; + src.curblkno = 0; + src.max_winsize = source_size; + + if ((ret = xd3_set_source_and_size (&stream, &src, source_size)) != 0) + { + goto exit; + } + } + + if ((ret = xd3_process_stream (is_encode, + & stream, + func, 1, + input, input_size, + output, + output_size, + output_size_max)) != 0) + { + goto exit; + } + + exit: + if (ret != 0) + { + IF_DEBUG2 (DP(RINT "test_process_memory: %d: %s\n", ret, stream.msg)); + } + xd3_free_stream(&stream); + return ret; + } + + void EncodeDecodeAPI(const FileSpec &spec0, const FileSpec &spec1, + Block *delta, const Options &options) { + Block from; + Block to; + spec0.Get(&from, 0, spec0.Size()); + spec1.Get(&to, 0, spec1.Size()); + + delta->SetSize(to.Size() * 1.5); + usize_t out_size; + int enc_ret = TestProcessMemory(true, + &xd3_encode_input, + to.Data(), + to.Size(), + from.Data(), + from.Size(), + delta->Data(), + &out_size, + delta->Size(), + options); + CHECK_EQ(0, enc_ret); + delta->SetSize(out_size); + + Block recon; + recon.SetSize(to.Size()); + usize_t recon_size; + int dec_ret = xd3_decode_memory(delta->Data(), + delta->Size(), + from.Data(), + from.Size(), + recon.Data(), + &recon_size, + recon.Size(), + 0); + CHECK_EQ(0, dec_ret); + CHECK_EQ(0, CmpDifferentBlockBytes(to, recon)); + } + +////////////////////////////////////////////////////////////////////// + +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); +} + +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; + + uint32_t umean = usum / rounds; + uint32_t emean = esum / rounds; + + uint32_t uexpect = UINT32_MAX / 2; + uint32_t eexpect = 1024; + + if (umean < uexpect * (1.0 - allowed_error) || + umean > uexpect * (1.0 + allowed_error)) { + XPR(NT "uniform mean error: %u != %u\n", umean, uexpect); + abort(); + } + + if (emean < eexpect * (1.0 - allowed_error) || + emean > eexpect * (1.0 + allowed_error)) { + XPR(NT "exponential mean error: %u != %u\n", emean, eexpect); + abort(); + } +} + +void TestRandomFile() { + MTRandom rand1; + FileSpec spec1(&rand1); + BlockIterator bi(spec1); + + spec1.GenerateFixedSize(0); + CHECK_EQ(0, spec1.Size()); + CHECK_EQ(0, spec1.Segments()); + CHECK_EQ(0, spec1.Blocks()); + bi.SetBlock(0); + CHECK_EQ(0, bi.BytesOnBlock()); + + spec1.GenerateFixedSize(1); + CHECK_EQ(1, spec1.Size()); + CHECK_EQ(1, spec1.Segments()); + CHECK_EQ(1, spec1.Blocks()); + bi.SetBlock(0); + CHECK_EQ(1, bi.BytesOnBlock()); + + spec1.GenerateFixedSize(Constants::BLOCK_SIZE); + CHECK_EQ(Constants::BLOCK_SIZE, spec1.Size()); + CHECK_EQ(1, spec1.Segments()); + CHECK_EQ(1, spec1.Blocks()); + bi.SetBlock(0); + CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock()); + bi.SetBlock(1); + CHECK_EQ(0, bi.BytesOnBlock()); + + spec1.GenerateFixedSize(Constants::BLOCK_SIZE + 1); + CHECK_EQ(Constants::BLOCK_SIZE + 1, spec1.Size()); + CHECK_EQ(2, spec1.Segments()); + CHECK_EQ(2, spec1.Blocks()); + bi.SetBlock(0); + CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock()); + bi.SetBlock(1); + CHECK_EQ(1, bi.BytesOnBlock()); + + spec1.GenerateFixedSize(Constants::BLOCK_SIZE * 2); + CHECK_EQ(Constants::BLOCK_SIZE * 2, spec1.Size()); + CHECK_EQ(2, spec1.Segments()); + CHECK_EQ(2, spec1.Blocks()); + bi.SetBlock(0); + CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock()); + bi.SetBlock(1); + CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock()); +} + +void TestFirstByte() { + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + + spec0.GenerateFixedSize(0); + spec1.GenerateFixedSize(1); + CHECK_EQ(0, CmpDifferentBytes(spec0, spec0)); + CHECK_EQ(0, CmpDifferentBytes(spec1, spec1)); + CHECK_EQ(1, CmpDifferentBytes(spec0, spec1)); + CHECK_EQ(1, CmpDifferentBytes(spec1, spec0)); + + spec0.GenerateFixedSize(1); + spec0.ModifyTo(Modify1stByte(), &spec1); + CHECK_EQ(1, CmpDifferentBytes(spec0, spec1)); + + spec0.GenerateFixedSize(Constants::BLOCK_SIZE + 1); + spec0.ModifyTo(Modify1stByte(), &spec1); + CHECK_EQ(1, CmpDifferentBytes(spec0, spec1)); + + SizeIterator si(&rand, Constants::TEST_ROUNDS); + + for (; !si.Done(); si.Next()) { + size_t size = si.Get(); + if (size == 0) { + continue; + } + spec0.GenerateFixedSize(size); + spec0.ModifyTo(Modify1stByte(), &spec1); + InMemoryEncodeDecode(spec0, spec1, NULL, Options()); + } +} + +void TestModifyMutator() { + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + + spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3); + + struct { + size_t size; + size_t addr; + } test_cases[] = { + { Constants::BLOCK_SIZE, 0 }, + { Constants::BLOCK_SIZE / 2, 1 }, + { Constants::BLOCK_SIZE, 1 }, + { Constants::BLOCK_SIZE * 2, 1 }, + }; + + for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) { + ChangeList cl1; + cl1.push_back(Change(Change::MODIFY, test_cases[i].size, + test_cases[i].addr)); + spec0.ModifyTo(ChangeListMutator(cl1), &spec1); + CHECK_EQ(spec0.Size(), spec1.Size()); + + size_t diff = CmpDifferentBytes(spec0, spec1); + CHECK_LE(diff, test_cases[i].size); + + // There is a 1/256 probability of the changed byte matching the + // original value. The following allows double the probability to + // pass. + CHECK_GE(diff, test_cases[i].size - (2 * test_cases[i].size / 256)); + + InMemoryEncodeDecode(spec0, spec1, NULL, Options()); + } +} + +void TestAddMutator() { + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + + spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 2); + // TODO: fix this test (for all block sizes)! it's broken because + // the same byte could be added? + + struct { + size_t size; + size_t addr; + size_t expected_adds; + } test_cases[] = { + { 1, 0, 2 /* 1st byte, last byte (short block) */ }, + { 1, 1, 3 /* 1st 2 bytes, last byte */ }, + { 1, Constants::BLOCK_SIZE - 1, 2 /* changed, last */ }, + { 1, Constants::BLOCK_SIZE, 2 /* changed, last */ }, + { 1, Constants::BLOCK_SIZE + 1, 3 /* changed + 1st of 2nd block, last */ }, + { 1, 2 * Constants::BLOCK_SIZE, 1 /* last byte */ }, + }; + + for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) { + ChangeList cl1; + cl1.push_back(Change(Change::ADD, test_cases[i].size, test_cases[i].addr)); + spec0.ModifyTo(ChangeListMutator(cl1), &spec1); + CHECK_EQ(spec0.Size() + test_cases[i].size, spec1.Size()); + + Block coded; + InMemoryEncodeDecode(spec0, spec1, &coded, Options()); + + Delta delta(coded); + CHECK_EQ(test_cases[i].expected_adds, + delta.AddedBytes()); + } +} + +void TestDeleteMutator() { + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + + spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 4); + + struct { + size_t size; + size_t addr; + } test_cases[] = { + // Note: an entry { Constants::BLOCK_SIZE, 0 }, + // does not work because the xd3_srcwin_move_point logic won't + // find a copy if it occurs >= double its size into the file. + { Constants::BLOCK_SIZE / 2, 0 }, + { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2 }, + { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE / 2 }, + { Constants::BLOCK_SIZE * 2, Constants::BLOCK_SIZE * 3 / 2 }, + { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE * 2 }, + }; + + for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) { + ChangeList cl1; + 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()); + + Block coded; + InMemoryEncodeDecode(spec0, spec1, &coded, Options()); + + Delta delta(coded); + CHECK_EQ(0, delta.AddedBytes()); + } +} + +void TestCopyMutator() { + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + + spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3); + + struct { + size_t size; + size_t from; + size_t to; + } test_cases[] = { + // Copy is difficult to write tests for because where Xdelta finds + // copies, it does not enter checksums. So these tests copy data from + // later to earlier so that checksumming will start. + { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2, 0 }, + { Constants::BLOCK_SIZE, 2 * Constants::BLOCK_SIZE, + Constants::BLOCK_SIZE, }, + }; + + for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) { + ChangeList cl1; + cl1.push_back(Change(Change::COPY, test_cases[i].size, + test_cases[i].from, test_cases[i].to)); + spec0.ModifyTo(ChangeListMutator(cl1), &spec1); + CHECK_EQ(spec0.Size() + test_cases[i].size, spec1.Size()); + + Block coded; + InMemoryEncodeDecode(spec0, spec1, &coded, Options()); + + Delta delta(coded); + CHECK_EQ(0, delta.AddedBytes()); + } +} + +void TestMoveMutator() { + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + + spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3); + + struct { + size_t size; + size_t from; + size_t to; + } test_cases[] = { + // This is easier to test than Copy but has the same trouble as Delete. + { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2, 0 }, + { Constants::BLOCK_SIZE / 2, 0, Constants::BLOCK_SIZE / 2 }, + { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE, 2 * + Constants::BLOCK_SIZE }, + { Constants::BLOCK_SIZE, 2 * Constants::BLOCK_SIZE, + Constants::BLOCK_SIZE }, + { Constants::BLOCK_SIZE * 3 / 2, Constants::BLOCK_SIZE, + Constants::BLOCK_SIZE * 3 / 2 }, + + // This is a no-op + { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE * 2, + 3 * Constants::BLOCK_SIZE }, + }; + + for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) { + ChangeList cl1; + cl1.push_back(Change(Change::MOVE, test_cases[i].size, + test_cases[i].from, test_cases[i].to)); + spec0.ModifyTo(ChangeListMutator(cl1), &spec1); + CHECK_EQ(spec0.Size(), spec1.Size()); + + Block coded; + InMemoryEncodeDecode(spec0, spec1, &coded, Options()); + + Delta delta(coded); + CHECK_EQ(0, delta.AddedBytes()); + } +} + +void TestOverwriteMutator() { + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + + spec0.GenerateFixedSize(Constants::BLOCK_SIZE); + + ChangeList cl1; + cl1.push_back(Change(Change::COPYOVER, 10, 0, 20)); + spec0.ModifyTo(ChangeListMutator(cl1), &spec1); + CHECK_EQ(spec0.Size(), spec1.Size()); + + Block b0, b1; + BlockIterator(spec0).Get(&b0); + BlockIterator(spec1).Get(&b1); + + CHECK(memcmp(b0.Data(), b1.Data() + 20, 10) == 0); + CHECK(memcmp(b0.Data(), b1.Data(), 20) == 0); + CHECK(memcmp(b0.Data() + 30, b1.Data() + 30, + Constants::BLOCK_SIZE - 30) == 0); + + xoff_t zero = 0; + cl1.clear(); + cl1.push_back(Change(Change::COPYOVER, 10, 20, zero)); + spec0.ModifyTo(ChangeListMutator(cl1), &spec1); + CHECK_EQ(spec0.Size(), spec1.Size()); + + BlockIterator(spec0).Get(&b0); + BlockIterator(spec1).Get(&b1); + + CHECK(memcmp(b0.Data() + 20, b1.Data(), 10) == 0); + CHECK(memcmp(b0.Data() + 10, b1.Data() + 10, + Constants::BLOCK_SIZE - 10) == 0); +} + +// Note: this test is written to expose a problem, but the problem was +// only exposed with BLOCK_SIZE = 128. +void TestNonBlocking() { + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + FileSpec spec2(&rand); + + spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3); + + // This is a lazy target match + Change ct(Change::COPYOVER, 22, + Constants::BLOCK_SIZE + 50, + Constants::BLOCK_SIZE + 20); + + // This is a source match just after the block boundary, shorter + // than the lazy target match. + Change cs1(Change::COPYOVER, 16, + Constants::BLOCK_SIZE + 51, + Constants::BLOCK_SIZE - 1); + + // This overwrites the original source bytes. + Change cs2(Change::MODIFY, 108, + Constants::BLOCK_SIZE + 20); + + // This changes the first blocks + Change c1st(Change::MODIFY, Constants::BLOCK_SIZE - 2, 0); + + ChangeList csl; + csl.push_back(cs1); + csl.push_back(cs2); + csl.push_back(c1st); + + spec0.ModifyTo(ChangeListMutator(csl), &spec1); + + ChangeList ctl; + ctl.push_back(ct); + ctl.push_back(c1st); + + spec0.ModifyTo(ChangeListMutator(ctl), &spec2); + + InMemoryEncodeDecode(spec1, spec2, NULL, Options()); +} + +void TestEmptyInMemory() { + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + Block block; + + spec0.GenerateFixedSize(0); + spec1.GenerateFixedSize(0); + + InMemoryEncodeDecode(spec0, spec1, &block, Options()); + + Delta delta(block); + CHECK_LT(0, block.Size()); + CHECK_EQ(1, delta.Windows()); +} + +void TestBlockInMemory() { + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + Block block; + + spec0.GenerateFixedSize(Constants::BLOCK_SIZE); + spec1.GenerateFixedSize(Constants::BLOCK_SIZE); + + InMemoryEncodeDecode(spec0, spec1, &block, Options()); + + Delta delta(block); + CHECK_EQ(spec1.Blocks(Constants::WINDOW_SIZE), delta.Windows()); +} + +void TestSmallStride() { + MTRandom rand; + FileSpec spec0(&rand); + usize_t size = Constants::BLOCK_SIZE * 4; + spec0.GenerateFixedSize(size); + + // 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); + + 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); + + IF_DEBUG1(DP(RINT "[stride=%d] changes=%" W "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() { + // Construct an input that has many copies, to fill the IOPT buffer + // and force a source window decision. "srclen" may be set to a + // value that goes beyond the end-of-source. + const int clen = 16; + const int size = 4096; + const int nmov = size / clen; + const int iters = 16; + uint32_t added_01 = 0; + uint32_t added_10 = 0; + for (int i = 1; i <= iters; i++) { + MTRandom rand(MTRandom::TEST_SEED1 * i); + FileSpec spec0(&rand); + ChangeList cl; + + spec0.GenerateFixedSize(size); + + for (int j = 0; j < nmov; j += 2) + { + cl.push_back(Change(Change::MOVE, + clen, (j + 1) * clen, j * clen)); + } + + 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; + + Block block1; + InMemoryEncodeDecode(spec0, spec1, &block1, options); + Delta delta1(block1); + // Allow one missed window (e.g., hash collisions) + added_01 += delta1.AddedBytes(); + + Block block2; + InMemoryEncodeDecode(spec1, spec0, &block2, options); + Delta delta2(block2); + // Allow one missed window (e.g., hash collisions) + added_10 += delta2.AddedBytes(); + + Block block3; + Block block4; + EncodeDecodeAPI(spec0, spec1, &block3, options); + EncodeDecodeAPI(spec1, spec0, &block4, options); + } + // Average less than 0.5 misses (of length clen) per iteration. + CHECK_GE(clen * iters / 2, added_01); + CHECK_GE(clen * iters / 2, added_10); +} + +void TestCopyFromEnd() { + // Copies from the end of the source buffer, which reach a block + // boundary end-of-file. + const int size = 4096; + const int clen = 16; + const int nmov = (size / 2) / clen; + const int iters = 16; + uint32_t added_01 = 0; + uint32_t added_10 = 0; + for (int i = 1; i <= iters; i++) { + MTRandom rand(MTRandom::TEST_SEED1 * i); + FileSpec spec0(&rand); + ChangeList cl; + + spec0.GenerateFixedSize(size); + + cl.push_back(Change(Change::MODIFY, 2012, 2048)); + + for (int j = 0; j < nmov; j += 2) + { + cl.push_back(Change(Change::MOVE, + clen, (j + 1) * clen, j * clen)); + } + + cl.push_back(Change(Change::COPYOVER, 28, 4068, 3000)); + cl.push_back(Change(Change::COPYOVER, 30, 4066, 3100)); + cl.push_back(Change(Change::COPYOVER, 32, 4064, 3200)); + + 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; + + Block block1; + InMemoryEncodeDecode(spec0, spec1, &block1, options); + Delta delta1(block1); + added_01 += delta1.AddedBytes(); + + Block block2; + InMemoryEncodeDecode(spec1, spec0, &block2, options); + Delta delta2(block2); + added_10 += delta2.AddedBytes(); + + Block block3; + Block block4; + EncodeDecodeAPI(spec0, spec1, &block3, options); + EncodeDecodeAPI(spec1, spec0, &block4, options); + } + CHECK_GE(2000 * iters, added_01); + CHECK_LE(2000 * iters, added_10); +} + +void TestHalfBlockCopy() { + // 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 * 8; + + Block block0; + Block block1; + InMemoryEncodeDecode(spec0, spec1, &block0, options); + InMemoryEncodeDecode(spec1, spec0, &block1, options); + + Delta delta0(block0); + Delta delta1(block1); + + 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 + { + CHECK_EQ(yes, delta0.AddedBytes()); + CHECK_EQ(yes, delta1.AddedBytes()); + } + } +} + +void FourWayMergeTest(const FileSpec &spec0, + const FileSpec &spec1, + const FileSpec &spec2, + const FileSpec &spec3) { + TmpFile f0, f1, f2, f3; + ExtFile d01, d12, d23; + Options options; + options.encode_srcwin_maxsz = + std::max(spec0.Size(), options.encode_srcwin_maxsz); + + spec0.WriteTmpFile(&f0); + spec1.WriteTmpFile(&f1); + spec2.WriteTmpFile(&f2); + spec3.WriteTmpFile(&f3); + + MainEncodeDecode(f0, f1, &d01, options); + MainEncodeDecode(f1, f2, &d12, options); + MainEncodeDecode(f2, f3, &d23, options); + + // Merge 2 + ExtFile out; + vector mcmd; + mcmd.push_back("xdelta3"); + mcmd.push_back("merge"); + mcmd.push_back("-m"); + mcmd.push_back(d01.Name()); + mcmd.push_back(d12.Name()); + mcmd.push_back(out.Name()); + mcmd.push_back(NULL); + + // XPR(NTR "Running one merge: %s\n", CommandToString(mcmd).c_str()); + CHECK_EQ(0, xd3_main_cmdline(mcmd.size() - 1, + const_cast(&mcmd[0]))); + + ExtFile recon; + vector tcmd; + tcmd.push_back("xdelta3"); + tcmd.push_back("-d"); + tcmd.push_back("-s"); + tcmd.push_back(f0.Name()); + tcmd.push_back(out.Name()); + tcmd.push_back(recon.Name()); + tcmd.push_back(NULL); + + // XPR(NTR "Running one recon! %s\n", CommandToString(tcmd).c_str()); + CHECK_EQ(0, xd3_main_cmdline(tcmd.size() - 1, + const_cast(&tcmd[0]))); + // XPR(NTR "Should equal! %s\n", f2.Name()); + + CHECK(recon.EqualsSpec(spec2)); + + // Merge 3 + ExtFile out3; + vector mcmd3; + mcmd3.push_back("xdelta3"); + mcmd3.push_back("merge"); + mcmd3.push_back("-m"); + mcmd3.push_back(d01.Name()); + mcmd3.push_back("-m"); + mcmd3.push_back(d12.Name()); + mcmd3.push_back(d23.Name()); + mcmd3.push_back(out3.Name()); + mcmd3.push_back(NULL); + + // XPR(NTR "Running one 3-merge: %s\n", CommandToString(mcmd3).c_str()); + CHECK_EQ(0, xd3_main_cmdline(mcmd3.size() - 1, + const_cast(&mcmd3[0]))); + + ExtFile recon3; + vector tcmd3; + tcmd3.push_back("xdelta3"); + tcmd3.push_back("-d"); + tcmd3.push_back("-s"); + tcmd3.push_back(f0.Name()); + tcmd3.push_back(out3.Name()); + tcmd3.push_back(recon3.Name()); + tcmd3.push_back(NULL); + + // XPR(NTR "Running one 3-recon %s\n", CommandToString(tcmd3).c_str()); + CHECK_EQ(0, xd3_main_cmdline(tcmd3.size() - 1, + const_cast(&tcmd3[0]))); + // XPR(NTR "Should equal %s\n", f3.Name()); + + CHECK(recon3.EqualsSpec(spec3)); +} + +void TestMergeCommand1() { + /* Repeat random-input testing for a number of iterations. + * Test 2, 3, and 4-file scenarios (i.e., 1, 2, and 3-delta merges). */ + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + FileSpec spec2(&rand); + FileSpec spec3(&rand); + + SizeIterator si0(&rand, 10); + + for (; !si0.Done(); si0.Next()) { + size_t size0 = si0.Get(); + + SizeIterator si1(&rand, 10); + for (; !si1.Done(); si1.Next()) { + size_t change1 = si1.Get(); + + if (change1 == 0) { + continue; + } + + // XPR(NTR "S0 = %lu\n", size0); + // XPR(NTR "C1 = %lu\n", change1); + // XPR(NTR "."); + + size_t add1_pos = size0 ? rand.Rand32() % size0 : 0; + size_t del2_pos = size0 ? rand.Rand32() % size0 : 0; + + spec0.GenerateFixedSize(size0); + + ChangeList cl1, cl2, cl3; + + size_t change3 = change1; + size_t change3_pos; + + if (change3 >= size0) { + change3 = size0; + change3_pos = 0; + } else { + change3_pos = rand.Rand32() % (size0 - change3); + } + + cl1.push_back(Change(Change::ADD, change1, add1_pos)); + cl2.push_back(Change(Change::DELRANGE, change1, del2_pos)); + cl3.push_back(Change(Change::MODIFY, change3, change3_pos)); + + spec0.ModifyTo(ChangeListMutator(cl1), &spec1); + spec1.ModifyTo(ChangeListMutator(cl2), &spec2); + spec2.ModifyTo(ChangeListMutator(cl3), &spec3); + + FourWayMergeTest(spec0, spec1, spec2, spec3); + FourWayMergeTest(spec3, spec2, spec1, spec0); + } + } +} + +void TestMergeCommand2() { + /* Same as above, different mutation pattern. */ + /* TODO: run this with large sizes too */ + /* TODO: run this with small sizes too */ + MTRandom rand; + FileSpec spec0(&rand); + FileSpec spec1(&rand); + FileSpec spec2(&rand); + FileSpec spec3(&rand); + + SizeIterator si0(&rand, 10); + for (; !si0.Done(); si0.Next()) { + size_t size0 = si0.Get(); + + SizeIterator si1(&rand, 10); + for (; !si1.Done(); si1.Next()) { + size_t size1 = si1.Get(); + + SizeIterator si2(&rand, 10); + for (; !si2.Done(); si2.Next()) { + size_t size2 = si2.Get(); + + SizeIterator si3(&rand, 10); + for (; !si3.Done(); si3.Next()) { + size_t size3 = si3.Get(); + + // We're only interested in three sizes, strictly decreasing. */ + if (size3 >= size2 || size2 >= size1 || size1 >= size0) { + continue; + } + + // XPR(NTR "S0 = %lu\n", size0); + // XPR(NTR "S1 = %lu\n", size1); + // XPR(NTR "S2 = %lu\n", size2); + // XPR(NTR "S3 = %lu\n", size3); + // XPR(NTR "."); + + spec0.GenerateFixedSize(size0); + + ChangeList cl1, cl2, cl3; + + 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); + spec0.ModifyTo(ChangeListMutator(cl3), &spec3); + + FourWayMergeTest(spec0, spec1, spec2, spec3); + FourWayMergeTest(spec3, spec2, spec1, spec0); + } + } + } + } +} + +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 + +#define TEST(x) XPR(NTR #x "...\n"); regtest.x() + +// These tests are primarily tests of the testing framework itself. +template +void UnitTest() { + Regtest regtest; + TEST(TestPrintf); + TEST(TestRandomNumbers); + TEST(TestRandomFile); + TEST(TestFirstByte); + TEST(TestModifyMutator); + TEST(TestAddMutator); + TEST(TestDeleteMutator); + TEST(TestCopyMutator); + TEST(TestMoveMutator); + TEST(TestOverwriteMutator); +} + +// These are Xdelta tests. +template +void MainTest() { + XPR(NT "Blocksize %" Q "u windowsize %" Z "u\n", + T::BLOCK_SIZE, T::WINDOW_SIZE); + Regtest regtest; + TEST(TestEmptyInMemory); + TEST(TestBlockInMemory); + TEST(TestSmallStride); + TEST(TestCopyWindow); + TEST(TestCopyFromEnd); + TEST(TestNonBlocking); + TEST(TestHalfBlockCopy); + TEST(TestLastFrontierBlock); + TEST(TestMergeCommand1); + TEST(TestMergeCommand2); +} + +#undef TEST + +int main(int argc, char **argv) +{ + vector mcmd; + string pn; + const char *sp = strrchr(argv[0], '/'); + if (sp != NULL) { + pn.append(argv[0], sp - argv[0] + 1); + } + pn.append("xdelta3"); + mcmd.push_back(pn.c_str()); + mcmd.push_back("test"); + mcmd.push_back(NULL); + + UnitTest(); + MainTest(); + MainTest(); + MainTest(); + MainTest(); + + CHECK_EQ(0, xd3_main_cmdline(mcmd.size() - 1, + const_cast(&mcmd[0]))); + + return 0; +} + -- cgit v1.2.3