1 /* -*- Mode: C++ -*- */
6 template <typename Constants>
9 typedef typename Constants::Sizes Sizes;
13 : encode_srcwin_maxsz(1<<20),
14 block_size(Constants::BLOCK_SIZE),
16 iopt_size(XD3_DEFAULT_IOPT_SIZE),
17 smatch_cfg(XD3_SMATCH_DEFAULT) { }
19 xoff_t encode_srcwin_maxsz;
23 xd3_smatch_cfg smatch_cfg;
32 void InMemoryEncodeDecode(const FileSpec &source_file,
33 const FileSpec &target_file,
35 const Options &options) {
36 xd3_stream encode_stream;
37 xd3_config encode_config;
38 xd3_source encode_source;
40 xd3_stream decode_stream;
41 xd3_config decode_config;
42 xd3_source decode_source;
43 xoff_t verified_bytes = 0;
44 xoff_t encoded_bytes = 0;
50 memset(&encode_stream, 0, sizeof (encode_stream));
51 memset(&encode_source, 0, sizeof (encode_source));
53 memset(&decode_stream, 0, sizeof (decode_stream));
54 memset(&decode_source, 0, sizeof (decode_source));
56 xd3_init_config(&encode_config, XD3_ADLER32);
57 xd3_init_config(&decode_config, XD3_ADLER32);
59 encode_config.winsize = Constants::WINDOW_SIZE;
60 encode_config.iopt_size = options.iopt_size;
61 encode_config.smatch_cfg = options.smatch_cfg;
63 CHECK_EQ(0, xd3_config_stream (&encode_stream, &encode_config));
64 CHECK_EQ(0, xd3_config_stream (&decode_stream, &decode_config));
66 encode_source.blksize = options.block_size;
67 decode_source.blksize = options.block_size;
69 encode_source.max_winsize = options.encode_srcwin_maxsz;
70 decode_source.max_winsize = options.encode_srcwin_maxsz;
72 if (!options.size_known)
74 xd3_set_source (&encode_stream, &encode_source);
75 xd3_set_source (&decode_stream, &decode_source);
79 xd3_set_source_and_size (&encode_stream, &encode_source,
81 xd3_set_source_and_size (&decode_stream, &decode_source,
85 BlockIterator source_iterator(source_file, options.block_size);
86 BlockIterator target_iterator(target_file, Constants::WINDOW_SIZE);
87 Block encode_source_block, decode_source_block;
88 Block decoded_block, target_block;
91 bool done_after_input = false;
93 IF_DEBUG1 (XPR(NTR "source %"Q"u[%"Q"u] target %"Q"u winsize %lu\n",
94 source_file.Size(), options.block_size,
96 Constants::WINDOW_SIZE));
99 target_iterator.Get(&target_block);
101 xoff_t blks = target_iterator.Blocks();
103 IF_DEBUG2(XPR(NTR "target in %s: %"Q"u..%"Q"u %"Q"u(%"Q"u) "
105 encoding ? "encoding" : "decoding",
106 target_iterator.Offset(),
107 target_iterator.Offset() + target_block.Size(),
108 target_iterator.Blkno(), blks, verified_bytes));
110 if (blks == 0 || target_iterator.Blkno() == (blks - 1)) {
111 xd3_set_flags(&encode_stream, XD3_FLUSH | encode_stream.flags);
114 xd3_avail_input(&encode_stream, target_block.Data(), target_block.Size());
115 encoded_bytes += target_block.Size();
121 ret = xd3_encode_input(&encode_stream);
122 msg = encode_stream.msg;
124 ret = xd3_decode_input(&decode_stream);
125 msg = decode_stream.msg;
132 if (coded_data != NULL) {
133 // Optional encoded-output to the caller
134 coded_data->Append(encode_stream.next_out,
135 encode_stream.avail_out);
137 // Feed this data to the decoder.
138 xd3_avail_input(&decode_stream,
139 encode_stream.next_out,
140 encode_stream.avail_out);
141 xd3_consume_output(&encode_stream);
144 decoded_block.Append(decode_stream.next_out,
145 decode_stream.avail_out);
146 xd3_consume_output(&decode_stream);
150 case XD3_GETSRCBLK: {
151 xd3_source *src = (encoding ? &encode_source : &decode_source);
152 Block *block = (encoding ? &encode_source_block : &decode_source_block);
154 IF_DEBUG1(XPR(NTR "[srcblock] %"Q"u last srcpos %"Q"u "
156 encode_source.getblkno,
157 encode_stream.match_last_srcpos,
158 encode_stream.input_position + encode_stream.total_in));
161 source_iterator.SetBlock(src->getblkno);
162 source_iterator.Get(block);
163 src->curblkno = src->getblkno;
164 src->onblk = block->Size();
165 src->curblk = block->Data();
175 if (done_after_input) {
180 if (target_block.Size() < target_iterator.BlockSize()) {
183 target_iterator.Next();
190 if (encode_stream.flags & XD3_FLUSH) {
191 done_after_input = true;
195 CHECK_EQ(0, CmpDifferentBlockBytesAtOffset(decoded_block,
198 verified_bytes += decoded_block.Size();
199 decoded_block.Reset();
209 XPR(NTR "%s = %s %s\n", encoding ? "E " : " D",
211 msg == NULL ? "" : msg);
218 CHECK_EQ(target_file.Size(), encoded_bytes);
219 CHECK_EQ(target_file.Size(), verified_bytes);
220 CHECK_EQ(0, xd3_close_stream(&decode_stream));
221 CHECK_EQ(0, xd3_close_stream(&encode_stream));
222 xd3_free_stream(&encode_stream);
223 xd3_free_stream(&decode_stream);
226 void MainEncodeDecode(const TmpFile &source_file,
227 const TmpFile &target_file,
229 const Options &options) {
230 vector<const char*> ecmd;
232 snprintf(wbuf, sizeof(wbuf), "-B%"Q"u", options.encode_srcwin_maxsz);
233 ecmd.push_back("xdelta3");
234 ecmd.push_back(wbuf);
235 ecmd.push_back("-s");
236 ecmd.push_back(source_file.Name());
237 ecmd.push_back(target_file.Name());
238 ecmd.push_back(coded_data->Name());
239 ecmd.push_back(NULL);
241 CHECK_EQ(0, xd3_main_cmdline(ecmd.size() - 1,
242 const_cast<char**>(&ecmd[0])));
244 vector<const char*> dcmd;
246 dcmd.push_back("xdelta3");
247 ecmd.push_back(wbuf);
248 dcmd.push_back("-d");
249 dcmd.push_back("-s");
250 dcmd.push_back(source_file.Name());
251 dcmd.push_back(coded_data->Name());
252 dcmd.push_back(recon_file.Name());
253 dcmd.push_back(NULL);
255 CHECK_EQ(0, xd3_main_cmdline(dcmd.size() - 1,
256 const_cast<char**>(&dcmd[0])));
258 CHECK_EQ(0, test_compare_files(recon_file.Name(),
259 target_file.Name()));
262 // Similar to xd3_process_memory, with support for test Options.
263 // Exercises xd3_process_stream.
264 int TestProcessMemory (int is_encode,
265 int (*func) (xd3_stream *),
266 const uint8_t *input,
268 const uint8_t *source,
271 usize_t *output_size,
272 usize_t output_size_max,
273 const Options &options) {
279 memset (& stream, 0, sizeof (stream));
280 memset (& config, 0, sizeof (config));
284 config.winsize = input_size;
285 config.iopt_size = options.iopt_size;
286 config.sprevsz = xd3_pow2_roundup (config.winsize);
289 if ((ret = xd3_config_stream (&stream, &config)) != 0)
296 memset (& src, 0, sizeof (src));
298 src.blksize = source_size;
299 src.onblk = source_size;
302 src.max_winsize = source_size;
304 if ((ret = xd3_set_source_and_size (&stream, &src, source_size)) != 0)
310 if ((ret = xd3_process_stream (is_encode,
316 output_size_max)) != 0)
324 IF_DEBUG2 (DP(RINT "test_process_memory: %d: %s\n", ret, stream.msg));
326 xd3_free_stream(&stream);
330 void EncodeDecodeAPI(const FileSpec &spec0, const FileSpec &spec1,
331 Block *delta, const Options &options) {
334 spec0.Get(&from, 0, spec0.Size());
335 spec1.Get(&to, 0, spec1.Size());
337 delta->SetSize(to.Size() * 1.5);
339 int enc_ret = TestProcessMemory(true,
349 CHECK_EQ(0, enc_ret);
350 delta->SetSize(out_size);
353 recon.SetSize(to.Size());
355 int dec_ret = xd3_decode_memory(delta->Data(),
363 CHECK_EQ(0, dec_ret);
364 CHECK_EQ(0, CmpDifferentBlockBytes(to, recon));
367 //////////////////////////////////////////////////////////////////////
369 void TestRandomNumbers() {
375 for (int i = 0; i < rounds; i++) {
376 usum += rand.Rand32();
377 esum += rand.ExpRand32(1024);
380 double allowed_error = 0.01;
382 uint32_t umean = usum / rounds;
383 uint32_t emean = esum / rounds;
385 uint32_t uexpect = UINT32_MAX / 2;
386 uint32_t eexpect = 1024;
388 if (umean < uexpect * (1.0 - allowed_error) ||
389 umean > uexpect * (1.0 + allowed_error)) {
390 XPR(NT "uniform mean error: %u != %u\n", umean, uexpect);
394 if (emean < eexpect * (1.0 - allowed_error) ||
395 emean > eexpect * (1.0 + allowed_error)) {
396 XPR(NT "exponential mean error: %u != %u\n", emean, eexpect);
401 void TestRandomFile() {
403 FileSpec spec1(&rand1);
404 BlockIterator bi(spec1);
406 spec1.GenerateFixedSize(0);
407 CHECK_EQ(0, spec1.Size());
408 CHECK_EQ(0, spec1.Segments());
409 CHECK_EQ(0, spec1.Blocks());
411 CHECK_EQ(0, bi.BytesOnBlock());
413 spec1.GenerateFixedSize(1);
414 CHECK_EQ(1, spec1.Size());
415 CHECK_EQ(1, spec1.Segments());
416 CHECK_EQ(1, spec1.Blocks());
418 CHECK_EQ(1, bi.BytesOnBlock());
420 spec1.GenerateFixedSize(Constants::BLOCK_SIZE);
421 CHECK_EQ(Constants::BLOCK_SIZE, spec1.Size());
422 CHECK_EQ(1, spec1.Segments());
423 CHECK_EQ(1, spec1.Blocks());
425 CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
427 CHECK_EQ(0, bi.BytesOnBlock());
429 spec1.GenerateFixedSize(Constants::BLOCK_SIZE + 1);
430 CHECK_EQ(Constants::BLOCK_SIZE + 1, spec1.Size());
431 CHECK_EQ(2, spec1.Segments());
432 CHECK_EQ(2, spec1.Blocks());
434 CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
436 CHECK_EQ(1, bi.BytesOnBlock());
438 spec1.GenerateFixedSize(Constants::BLOCK_SIZE * 2);
439 CHECK_EQ(Constants::BLOCK_SIZE * 2, spec1.Size());
440 CHECK_EQ(2, spec1.Segments());
441 CHECK_EQ(2, spec1.Blocks());
443 CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
445 CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
448 void TestFirstByte() {
450 FileSpec spec0(&rand);
451 FileSpec spec1(&rand);
453 spec0.GenerateFixedSize(0);
454 spec1.GenerateFixedSize(1);
455 CHECK_EQ(0, CmpDifferentBytes(spec0, spec0));
456 CHECK_EQ(0, CmpDifferentBytes(spec1, spec1));
457 CHECK_EQ(1, CmpDifferentBytes(spec0, spec1));
458 CHECK_EQ(1, CmpDifferentBytes(spec1, spec0));
460 spec0.GenerateFixedSize(1);
461 spec0.ModifyTo(Modify1stByte(), &spec1);
462 CHECK_EQ(1, CmpDifferentBytes(spec0, spec1));
464 spec0.GenerateFixedSize(Constants::BLOCK_SIZE + 1);
465 spec0.ModifyTo(Modify1stByte(), &spec1);
466 CHECK_EQ(1, CmpDifferentBytes(spec0, spec1));
468 SizeIterator<size_t, Sizes> si(&rand, Constants::TEST_ROUNDS);
470 for (; !si.Done(); si.Next()) {
471 size_t size = si.Get();
475 spec0.GenerateFixedSize(size);
476 spec0.ModifyTo(Modify1stByte(), &spec1);
477 InMemoryEncodeDecode(spec0, spec1, NULL, Options());
481 void TestModifyMutator() {
483 FileSpec spec0(&rand);
484 FileSpec spec1(&rand);
486 spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
492 { Constants::BLOCK_SIZE, 0 },
493 { Constants::BLOCK_SIZE / 2, 1 },
494 { Constants::BLOCK_SIZE, 1 },
495 { Constants::BLOCK_SIZE * 2, 1 },
498 for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
500 cl1.push_back(Change(Change::MODIFY, test_cases[i].size,
501 test_cases[i].addr));
502 spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
503 CHECK_EQ(spec0.Size(), spec1.Size());
505 size_t diff = CmpDifferentBytes(spec0, spec1);
506 CHECK_LE(diff, test_cases[i].size);
508 // There is a 1/256 probability of the changed byte matching the
509 // original value. The following allows double the probability to
511 CHECK_GE(diff, test_cases[i].size - (2 * test_cases[i].size / 256));
513 InMemoryEncodeDecode(spec0, spec1, NULL, Options());
517 void TestAddMutator() {
519 FileSpec spec0(&rand);
520 FileSpec spec1(&rand);
522 spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 2);
523 // TODO: fix this test (for all block sizes)! it's broken because
524 // the same byte could be added?
529 size_t expected_adds;
531 { 1, 0, 2 /* 1st byte, last byte (short block) */ },
532 { 1, 1, 3 /* 1st 2 bytes, last byte */ },
533 { 1, Constants::BLOCK_SIZE - 1, 2 /* changed, last */ },
534 { 1, Constants::BLOCK_SIZE, 2 /* changed, last */ },
535 { 1, Constants::BLOCK_SIZE + 1, 3 /* changed + 1st of 2nd block, last */ },
536 { 1, 2 * Constants::BLOCK_SIZE, 1 /* last byte */ },
539 for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
541 cl1.push_back(Change(Change::ADD, test_cases[i].size, test_cases[i].addr));
542 spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
543 CHECK_EQ(spec0.Size() + test_cases[i].size, spec1.Size());
546 InMemoryEncodeDecode(spec0, spec1, &coded, Options());
549 CHECK_EQ(test_cases[i].expected_adds,
554 void TestDeleteMutator() {
556 FileSpec spec0(&rand);
557 FileSpec spec1(&rand);
559 spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 4);
565 // Note: an entry { Constants::BLOCK_SIZE, 0 },
566 // does not work because the xd3_srcwin_move_point logic won't
567 // find a copy if it occurs >= double its size into the file.
568 { Constants::BLOCK_SIZE / 2, 0 },
569 { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2 },
570 { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE / 2 },
571 { Constants::BLOCK_SIZE * 2, Constants::BLOCK_SIZE * 3 / 2 },
572 { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE * 2 },
575 for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
577 cl1.push_back(Change(Change::DELETE, test_cases[i].size,
578 test_cases[i].addr));
579 spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
580 CHECK_EQ(spec0.Size() - test_cases[i].size, spec1.Size());
583 InMemoryEncodeDecode(spec0, spec1, &coded, Options());
586 CHECK_EQ(0, delta.AddedBytes());
590 void TestCopyMutator() {
592 FileSpec spec0(&rand);
593 FileSpec spec1(&rand);
595 spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
602 // Copy is difficult to write tests for because where Xdelta finds
603 // copies, it does not enter checksums. So these tests copy data from
604 // later to earlier so that checksumming will start.
605 { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2, 0 },
606 { Constants::BLOCK_SIZE, 2 * Constants::BLOCK_SIZE,
607 Constants::BLOCK_SIZE, },
610 for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
612 cl1.push_back(Change(Change::COPY, test_cases[i].size,
613 test_cases[i].from, test_cases[i].to));
614 spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
615 CHECK_EQ(spec0.Size() + test_cases[i].size, spec1.Size());
618 InMemoryEncodeDecode(spec0, spec1, &coded, Options());
621 CHECK_EQ(0, delta.AddedBytes());
625 void TestMoveMutator() {
627 FileSpec spec0(&rand);
628 FileSpec spec1(&rand);
630 spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
637 // This is easier to test than Copy but has the same trouble as Delete.
638 { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2, 0 },
639 { Constants::BLOCK_SIZE / 2, 0, Constants::BLOCK_SIZE / 2 },
640 { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE, 2 *
641 Constants::BLOCK_SIZE },
642 { Constants::BLOCK_SIZE, 2 * Constants::BLOCK_SIZE,
643 Constants::BLOCK_SIZE },
644 { Constants::BLOCK_SIZE * 3 / 2, Constants::BLOCK_SIZE,
645 Constants::BLOCK_SIZE * 3 / 2 },
648 { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE * 2,
649 3 * Constants::BLOCK_SIZE },
652 for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
654 cl1.push_back(Change(Change::MOVE, test_cases[i].size,
655 test_cases[i].from, test_cases[i].to));
656 spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
657 CHECK_EQ(spec0.Size(), spec1.Size());
660 InMemoryEncodeDecode(spec0, spec1, &coded, Options());
663 CHECK_EQ(0, delta.AddedBytes());
667 void TestOverwriteMutator() {
669 FileSpec spec0(&rand);
670 FileSpec spec1(&rand);
672 spec0.GenerateFixedSize(Constants::BLOCK_SIZE);
675 cl1.push_back(Change(Change::COPYOVER, 10, 0, 20));
676 spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
677 CHECK_EQ(spec0.Size(), spec1.Size());
680 BlockIterator(spec0).Get(&b0);
681 BlockIterator(spec1).Get(&b1);
683 CHECK(memcmp(b0.Data(), b1.Data() + 20, 10) == 0);
684 CHECK(memcmp(b0.Data(), b1.Data(), 20) == 0);
685 CHECK(memcmp(b0.Data() + 30, b1.Data() + 30,
686 Constants::BLOCK_SIZE - 30) == 0);
689 cl1.push_back(Change(Change::COPYOVER, 10, 20, (xoff_t)0));
690 spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
691 CHECK_EQ(spec0.Size(), spec1.Size());
693 BlockIterator(spec0).Get(&b0);
694 BlockIterator(spec1).Get(&b1);
696 CHECK(memcmp(b0.Data() + 20, b1.Data(), 10) == 0);
697 CHECK(memcmp(b0.Data() + 10, b1.Data() + 10,
698 Constants::BLOCK_SIZE - 10) == 0);
701 // Note: this test is written to expose a problem, but the problem was
702 // only exposed with BLOCK_SIZE = 128.
703 void TestNonBlocking() {
705 FileSpec spec0(&rand);
706 FileSpec spec1(&rand);
707 FileSpec spec2(&rand);
709 spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
711 // This is a lazy target match
712 Change ct(Change::COPYOVER, 22,
713 Constants::BLOCK_SIZE + 50,
714 Constants::BLOCK_SIZE + 20);
716 // This is a source match just after the block boundary, shorter
717 // than the lazy target match.
718 Change cs1(Change::COPYOVER, 16,
719 Constants::BLOCK_SIZE + 51,
720 Constants::BLOCK_SIZE - 1);
722 // This overwrites the original source bytes.
723 Change cs2(Change::MODIFY, 108,
724 Constants::BLOCK_SIZE + 20);
726 // This changes the first blocks
727 Change c1st(Change::MODIFY, Constants::BLOCK_SIZE - 2, 0);
734 spec0.ModifyTo(ChangeListMutator(csl), &spec1);
740 spec0.ModifyTo(ChangeListMutator(ctl), &spec2);
742 InMemoryEncodeDecode(spec1, spec2, NULL, Options());
745 void TestEmptyInMemory() {
747 FileSpec spec0(&rand);
748 FileSpec spec1(&rand);
751 spec0.GenerateFixedSize(0);
752 spec1.GenerateFixedSize(0);
754 InMemoryEncodeDecode(spec0, spec1, &block, Options());
757 CHECK_LT(0, block.Size());
758 CHECK_EQ(1, delta.Windows());
761 void TestBlockInMemory() {
763 FileSpec spec0(&rand);
764 FileSpec spec1(&rand);
767 spec0.GenerateFixedSize(Constants::BLOCK_SIZE);
768 spec1.GenerateFixedSize(Constants::BLOCK_SIZE);
770 InMemoryEncodeDecode(spec0, spec1, &block, Options());
773 CHECK_EQ(spec1.Blocks(Constants::WINDOW_SIZE), delta.Windows());
776 void TestSmallStride() {
778 FileSpec spec0(&rand);
779 usize_t size = Constants::BLOCK_SIZE * 4;
780 spec0.GenerateFixedSize(size);
782 /* TODO Need to study the actual causes of missed adds for tests
783 * less than 30 bytes. */
787 for (usize_t j = s; j < size; j += s, ++adds)
789 cl.push_back(Change(Change::MODIFY, 1, j));
792 FileSpec spec1(&rand);
793 spec0.ModifyTo(ChangeListMutator(cl), &spec1);
796 options.encode_srcwin_maxsz = size;
797 options.iopt_size = 128;
798 options.smatch_cfg = XD3_SMATCH_SLOW;
799 options.size_known = false;
802 InMemoryEncodeDecode(spec0, spec1, &block, options);
805 // Allow an additional two byte of add per window
806 usize_t allowance = 2 * size / Constants::WINDOW_SIZE;
807 CHECK_GE(adds + allowance, delta.AddedBytes());
810 void TestCopyWindow() {
811 // Construct an input that has many copies, to fill the IOPT buffer
812 // and force a source window decision. "srclen" may be set to a
813 // value that goes beyond the end-of-source.
815 const int size = 4096;
816 const int nmov = size / clen;
817 const int iters = 16;
818 uint32_t added_01 = 0;
819 uint32_t added_10 = 0;
820 for (int i = 1; i <= iters; i++) {
821 MTRandom rand(MTRandom::TEST_SEED1 * i);
822 FileSpec spec0(&rand);
825 spec0.GenerateFixedSize(size);
827 for (int j = 0; j < nmov; j += 2)
829 cl.push_back(Change(Change::MOVE,
830 clen, (j + 1) * clen, j * clen));
833 FileSpec spec1(&rand);
834 spec0.ModifyTo(ChangeListMutator(cl), &spec1);
837 options.encode_srcwin_maxsz = size;
838 options.iopt_size = 128;
839 options.smatch_cfg = XD3_SMATCH_SLOW;
840 options.size_known = false;
843 InMemoryEncodeDecode(spec0, spec1, &block1, options);
844 Delta delta1(block1);
845 // Allow one missed window (e.g., hash collisions)
846 added_01 += delta1.AddedBytes();
849 InMemoryEncodeDecode(spec1, spec0, &block2, options);
850 Delta delta2(block2);
851 // Allow one missed window (e.g., hash collisions)
852 added_10 += delta2.AddedBytes();
856 EncodeDecodeAPI(spec0, spec1, &block3, options);
857 EncodeDecodeAPI(spec1, spec0, &block4, options);
859 // Average less than 0.5 misses (of length clen) per iteration.
860 CHECK_GE(clen * iters / 2, added_01);
861 CHECK_GE(clen * iters / 2, added_10);
864 void TestCopyFromEnd() {
865 // Copies from the end of the source buffer, which reach a block
866 // boundary end-of-file.
867 const int size = 4096;
869 const int nmov = (size / 2) / clen;
870 const int iters = 16;
871 uint32_t added_01 = 0;
872 uint32_t added_10 = 0;
873 for (int i = 1; i <= iters; i++) {
874 MTRandom rand(MTRandom::TEST_SEED1 * i);
875 FileSpec spec0(&rand);
878 spec0.GenerateFixedSize(size);
880 cl.push_back(Change(Change::MODIFY, 2012, 2048));
882 for (int j = 0; j < nmov; j += 2)
884 cl.push_back(Change(Change::MOVE,
885 clen, (j + 1) * clen, j * clen));
888 cl.push_back(Change(Change::COPYOVER, 28, 4068, 3000));
889 cl.push_back(Change(Change::COPYOVER, 30, 4066, 3100));
890 cl.push_back(Change(Change::COPYOVER, 32, 4064, 3200));
892 FileSpec spec1(&rand);
893 spec0.ModifyTo(ChangeListMutator(cl), &spec1);
896 options.encode_srcwin_maxsz = size;
897 options.iopt_size = 128;
898 options.smatch_cfg = XD3_SMATCH_SLOW;
901 InMemoryEncodeDecode(spec0, spec1, &block1, options);
902 Delta delta1(block1);
903 added_01 += delta1.AddedBytes();
906 InMemoryEncodeDecode(spec1, spec0, &block2, options);
907 Delta delta2(block2);
908 added_10 += delta2.AddedBytes();
912 EncodeDecodeAPI(spec0, spec1, &block3, options);
913 EncodeDecodeAPI(spec1, spec0, &block4, options);
915 CHECK_GE(2000 * iters, added_01);
916 CHECK_LE(2000 * iters, added_10);
919 void TestHalfBlockCopy() {
921 FileSpec spec0(&rand);
922 FileSpec spec1(&rand);
924 spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 4);
926 // Create a half-block copy, 2.5 blocks apart, from the second half
927 // of the source version to the first half of the target version.
929 // spec0 [bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb][ccccc][bbbbb]
930 // spec1 [aaaaa][ccccc][aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa]
932 cl1.push_back(Change(Change::MODIFY,
933 Constants::BLOCK_SIZE / 2, // size
935 cl1.push_back(Change(Change::COPYOVER,
936 Constants::BLOCK_SIZE / 2, // size
937 Constants::BLOCK_SIZE * 3, // offset
938 Constants::BLOCK_SIZE / 2));
939 cl1.push_back(Change(Change::MODIFY,
940 Constants::BLOCK_SIZE * 3,
941 Constants::BLOCK_SIZE));
942 spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
944 const int onecopy_adds =
945 4 * Constants::BLOCK_SIZE - Constants::BLOCK_SIZE / 2;
946 const int nocopy_adds = 4 * Constants::BLOCK_SIZE;
948 // Note the case b=4 is contrived: the caller should use a single block
949 // containing the entire source, if possible.
950 for (int b = 1; b <= 4; b++)
953 options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * b;
957 InMemoryEncodeDecode(spec0, spec1, &block0, options);
958 InMemoryEncodeDecode(spec1, spec0, &block1, options);
959 Delta delta0(block0);
960 Delta delta1(block1);
962 // The first block never copies from the last source block, by
963 // design, because if the last source block is available when
964 // the first target block is ready, the caller is expected to
965 // use a single block.
966 CHECK_EQ(nocopy_adds, delta0.AddedBytes());
967 if (Constants::BLOCK_SIZE < 8192 || b > 2)
969 // For small-block inputs, the entire file is read into one
970 // block (the min source window size is 16kB).
972 // For large blocks, at least 3 blocks of source window are
974 CHECK_EQ(onecopy_adds, delta1.AddedBytes());
978 // When there are fewer than 3 source blocks.
979 CHECK_EQ(nocopy_adds, delta1.AddedBytes());
981 // XPR(NT "0=%zu 1=%zu\n", delta0.AddedBytes(), delta1.AddedBytes());
985 options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * 4;
986 options.block_size = Constants::BLOCK_SIZE * 4;
988 // Test the whole-buffer case.
991 InMemoryEncodeDecode(spec0, spec1, &block0, options);
992 InMemoryEncodeDecode(spec1, spec0, &block1, options);
993 Delta delta0(block0);
994 Delta delta1(block1);
995 // This <= >= are only for blocksize = 512, which has irregular readsize.
996 CHECK_LE(onecopy_adds, delta0.AddedBytes());
997 CHECK_GE(onecopy_adds + 1, delta0.AddedBytes());
999 CHECK_EQ(onecopy_adds, delta1.AddedBytes());
1000 // XPR(NT "0=%zu 1=%zu\n", delta0.AddedBytes(), delta1.AddedBytes());
1003 void FourWayMergeTest(const FileSpec &spec0,
1004 const FileSpec &spec1,
1005 const FileSpec &spec2,
1006 const FileSpec &spec3) {
1007 TmpFile f0, f1, f2, f3;
1008 ExtFile d01, d12, d23;
1010 options.encode_srcwin_maxsz =
1011 std::max(spec0.Size(), options.encode_srcwin_maxsz);
1013 spec0.WriteTmpFile(&f0);
1014 spec1.WriteTmpFile(&f1);
1015 spec2.WriteTmpFile(&f2);
1016 spec3.WriteTmpFile(&f3);
1018 MainEncodeDecode(f0, f1, &d01, options);
1019 MainEncodeDecode(f1, f2, &d12, options);
1020 MainEncodeDecode(f2, f3, &d23, options);
1024 vector<const char*> mcmd;
1025 mcmd.push_back("xdelta3");
1026 mcmd.push_back("merge");
1027 mcmd.push_back("-m");
1028 mcmd.push_back(d01.Name());
1029 mcmd.push_back(d12.Name());
1030 mcmd.push_back(out.Name());
1031 mcmd.push_back(NULL);
1033 // XPR(NTR "Running one merge: %s\n", CommandToString(mcmd).c_str());
1034 CHECK_EQ(0, xd3_main_cmdline(mcmd.size() - 1,
1035 const_cast<char**>(&mcmd[0])));
1038 vector<const char*> tcmd;
1039 tcmd.push_back("xdelta3");
1040 tcmd.push_back("-d");
1041 tcmd.push_back("-s");
1042 tcmd.push_back(f0.Name());
1043 tcmd.push_back(out.Name());
1044 tcmd.push_back(recon.Name());
1045 tcmd.push_back(NULL);
1047 // XPR(NTR "Running one recon! %s\n", CommandToString(tcmd).c_str());
1048 CHECK_EQ(0, xd3_main_cmdline(tcmd.size() - 1,
1049 const_cast<char**>(&tcmd[0])));
1050 // XPR(NTR "Should equal! %s\n", f2.Name());
1052 CHECK(recon.EqualsSpec(spec2));
1056 vector<const char*> mcmd3;
1057 mcmd3.push_back("xdelta3");
1058 mcmd3.push_back("merge");
1059 mcmd3.push_back("-m");
1060 mcmd3.push_back(d01.Name());
1061 mcmd3.push_back("-m");
1062 mcmd3.push_back(d12.Name());
1063 mcmd3.push_back(d23.Name());
1064 mcmd3.push_back(out3.Name());
1065 mcmd3.push_back(NULL);
1067 // XPR(NTR "Running one 3-merge: %s\n", CommandToString(mcmd3).c_str());
1068 CHECK_EQ(0, xd3_main_cmdline(mcmd3.size() - 1,
1069 const_cast<char**>(&mcmd3[0])));
1072 vector<const char*> tcmd3;
1073 tcmd3.push_back("xdelta3");
1074 tcmd3.push_back("-d");
1075 tcmd3.push_back("-s");
1076 tcmd3.push_back(f0.Name());
1077 tcmd3.push_back(out3.Name());
1078 tcmd3.push_back(recon3.Name());
1079 tcmd3.push_back(NULL);
1081 // XPR(NTR "Running one 3-recon %s\n", CommandToString(tcmd3).c_str());
1082 CHECK_EQ(0, xd3_main_cmdline(tcmd3.size() - 1,
1083 const_cast<char**>(&tcmd3[0])));
1084 // XPR(NTR "Should equal %s\n", f3.Name());
1086 CHECK(recon3.EqualsSpec(spec3));
1089 void TestMergeCommand1() {
1090 /* Repeat random-input testing for a number of iterations.
1091 * Test 2, 3, and 4-file scenarios (i.e., 1, 2, and 3-delta merges). */
1093 FileSpec spec0(&rand);
1094 FileSpec spec1(&rand);
1095 FileSpec spec2(&rand);
1096 FileSpec spec3(&rand);
1098 SizeIterator<size_t, Sizes> si0(&rand, 10);
1100 for (; !si0.Done(); si0.Next()) {
1101 size_t size0 = si0.Get();
1103 SizeIterator<size_t, Sizes> si1(&rand, 10);
1104 for (; !si1.Done(); si1.Next()) {
1105 size_t change1 = si1.Get();
1111 // XPR(NTR "S0 = %lu\n", size0);
1112 // XPR(NTR "C1 = %lu\n", change1);
1115 size_t add1_pos = size0 ? rand.Rand32() % size0 : 0;
1116 size_t del2_pos = size0 ? rand.Rand32() % size0 : 0;
1118 spec0.GenerateFixedSize(size0);
1120 ChangeList cl1, cl2, cl3;
1122 size_t change3 = change1;
1125 if (change3 >= size0) {
1129 change3_pos = rand.Rand32() % (size0 - change3);
1132 cl1.push_back(Change(Change::ADD, change1, add1_pos));
1133 cl2.push_back(Change(Change::DELETE, change1, del2_pos));
1134 cl3.push_back(Change(Change::MODIFY, change3, change3_pos));
1136 spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
1137 spec1.ModifyTo(ChangeListMutator(cl2), &spec2);
1138 spec2.ModifyTo(ChangeListMutator(cl3), &spec3);
1140 FourWayMergeTest(spec0, spec1, spec2, spec3);
1141 FourWayMergeTest(spec3, spec2, spec1, spec0);
1146 void TestMergeCommand2() {
1147 /* Same as above, different mutation pattern. */
1148 /* TODO: run this with large sizes too */
1149 /* TODO: run this with small sizes too */
1151 FileSpec spec0(&rand);
1152 FileSpec spec1(&rand);
1153 FileSpec spec2(&rand);
1154 FileSpec spec3(&rand);
1156 SizeIterator<size_t, Sizes> si0(&rand, 10);
1157 for (; !si0.Done(); si0.Next()) {
1158 size_t size0 = si0.Get();
1160 SizeIterator<size_t, Sizes> si1(&rand, 10);
1161 for (; !si1.Done(); si1.Next()) {
1162 size_t size1 = si1.Get();
1164 SizeIterator<size_t, Sizes> si2(&rand, 10);
1165 for (; !si2.Done(); si2.Next()) {
1166 size_t size2 = si2.Get();
1168 SizeIterator<size_t, Sizes> si3(&rand, 10);
1169 for (; !si3.Done(); si3.Next()) {
1170 size_t size3 = si3.Get();
1172 // We're only interested in three sizes, strictly decreasing. */
1173 if (size3 >= size2 || size2 >= size1 || size1 >= size0) {
1177 // XPR(NTR "S0 = %lu\n", size0);
1178 // XPR(NTR "S1 = %lu\n", size1);
1179 // XPR(NTR "S2 = %lu\n", size2);
1180 // XPR(NTR "S3 = %lu\n", size3);
1183 spec0.GenerateFixedSize(size0);
1185 ChangeList cl1, cl2, cl3;
1187 cl1.push_back(Change(Change::DELETE, size0 - size1, 0));
1188 cl2.push_back(Change(Change::DELETE, size0 - size2, 0));
1189 cl3.push_back(Change(Change::DELETE, size0 - size3, 0));
1191 spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
1192 spec0.ModifyTo(ChangeListMutator(cl2), &spec2);
1193 spec0.ModifyTo(ChangeListMutator(cl3), &spec3);
1195 FourWayMergeTest(spec0, spec1, spec2, spec3);
1196 FourWayMergeTest(spec3, spec2, spec1, spec0);
1203 }; // class Regtest<Constants>
1205 #define TEST(x) XPR(NTR #x "...\n"); regtest.x()
1207 // These tests are primarily tests of the testing framework itself.
1211 TEST(TestRandomNumbers);
1212 TEST(TestRandomFile);
1213 TEST(TestFirstByte);
1214 TEST(TestModifyMutator);
1215 TEST(TestAddMutator);
1216 TEST(TestDeleteMutator);
1217 TEST(TestCopyMutator);
1218 TEST(TestMoveMutator);
1219 TEST(TestOverwriteMutator);
1222 // These are Xdelta tests.
1225 XPR(NT "Blocksize %"Q"u windowsize %"Q"u\n",
1226 T::BLOCK_SIZE, T::WINDOW_SIZE);
1228 TEST(TestEmptyInMemory);
1229 TEST(TestBlockInMemory);
1230 TEST(TestSmallStride);
1231 TEST(TestCopyWindow);
1232 TEST(TestCopyFromEnd);
1233 TEST(TestNonBlocking);
1234 TEST(TestHalfBlockCopy);
1235 TEST(TestMergeCommand1);
1236 TEST(TestMergeCommand2);
1241 int main(int argc, char **argv)
1243 vector<const char*> mcmd;
1245 const char *sp = strrchr(argv[0], '/');
1247 pn.append(argv[0], sp - argv[0] + 1);
1249 pn.append("xdelta3");
1250 mcmd.push_back(pn.c_str());
1251 mcmd.push_back("test");
1252 mcmd.push_back(NULL);
1254 UnitTest<SmallBlock>();
1255 MainTest<SmallBlock>();
1256 MainTest<MixedBlock>();
1257 MainTest<OversizeBlock>();
1258 MainTest<LargeBlock>();
1260 CHECK_EQ(0, xd3_main_cmdline(mcmd.size() - 1,
1261 const_cast<char**>(&mcmd[0])));