"Fossies" - the Fresh Open Source Software Archive

Member "xdelta3-3.1.0/testing/regtest.cc" (5 Jan 2016, 35915 Bytes) of package /linux/misc/xdelta3-3.1.0.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "regtest.cc": 3.0.11_vs_3.1.0.

    1 /* -*- Mode: C++ -*-  */
    2 #include "test.h"
    3 #include "random.h"
    4 #include "sizes.h"
    5 
    6 template <typename Constants>
    7 class Regtest {
    8 public:
    9   typedef typename Constants::Sizes Sizes;
   10 
   11   struct Options {
   12     Options()
   13       : encode_srcwin_maxsz(1<<20),
   14     block_size(Constants::BLOCK_SIZE),
   15     window_size(Constants::WINDOW_SIZE),
   16     size_known(false),
   17     iopt_size(XD3_DEFAULT_IOPT_SIZE),
   18     smatch_cfg(XD3_SMATCH_DEFAULT) { }
   19 
   20     xoff_t encode_srcwin_maxsz;
   21     size_t block_size;
   22     xoff_t window_size;
   23     bool size_known;
   24     usize_t iopt_size;
   25     xd3_smatch_cfg smatch_cfg;
   26   };
   27 
   28 #include "segment.h"
   29 #include "modify.h"
   30 #include "file.h"
   31 #include "cmp.h"
   32 #include "delta.h"
   33 
   34   void InMemoryEncodeDecode(const FileSpec &source_file,
   35                 const FileSpec &target_file,
   36                 Block *coded_data,
   37                 const Options &options) {
   38     xd3_stream encode_stream;
   39     xd3_config encode_config;
   40     xd3_source encode_source;
   41 
   42     xd3_stream decode_stream;
   43     xd3_config decode_config;
   44     xd3_source decode_source;
   45     xoff_t verified_bytes = 0;
   46     xoff_t encoded_bytes = 0;
   47 
   48     if (coded_data) {
   49       coded_data->Reset();
   50     }
   51 
   52     memset(&encode_stream, 0, sizeof (encode_stream));
   53     memset(&encode_source, 0, sizeof (encode_source));
   54 
   55     memset(&decode_stream, 0, sizeof (decode_stream));
   56     memset(&decode_source, 0, sizeof (decode_source));
   57 
   58     xd3_init_config(&encode_config, XD3_ADLER32);
   59     xd3_init_config(&decode_config, XD3_ADLER32);
   60 
   61     encode_config.winsize = options.window_size;
   62     encode_config.iopt_size = options.iopt_size;
   63     encode_config.smatch_cfg = options.smatch_cfg;
   64 
   65     CHECK_EQ(0, xd3_config_stream (&encode_stream, &encode_config));
   66     CHECK_EQ(0, xd3_config_stream (&decode_stream, &decode_config));
   67 
   68     encode_source.blksize = options.block_size;
   69     decode_source.blksize = options.block_size;
   70 
   71     encode_source.max_winsize = options.encode_srcwin_maxsz;
   72     decode_source.max_winsize = options.encode_srcwin_maxsz;
   73 
   74     if (!options.size_known)
   75       {
   76     xd3_set_source (&encode_stream, &encode_source);
   77     xd3_set_source (&decode_stream, &decode_source);
   78       }
   79     else
   80       {
   81     xd3_set_source_and_size (&encode_stream, &encode_source,
   82                  source_file.Size());
   83     xd3_set_source_and_size (&decode_stream, &decode_source,
   84                  source_file.Size());
   85       }
   86 
   87     BlockIterator source_iterator(source_file, options.block_size);
   88     BlockIterator target_iterator(target_file, Constants::WINDOW_SIZE);
   89     Block encode_source_block, decode_source_block;
   90     Block decoded_block, target_block;
   91     bool encoding = true;
   92     bool done = false;
   93     bool done_after_input = false;
   94 
   95     IF_DEBUG1 (XPR(NTR "source %" Q "u[%" Z "u] target %" Q "u winsize %" Z "u\n",
   96            source_file.Size(), options.block_size,
   97            target_file.Size(),
   98            Constants::WINDOW_SIZE));
   99 
  100     while (!done) {
  101       target_iterator.Get(&target_block);
  102 
  103       xoff_t blks = target_iterator.Blocks();
  104 
  105       IF_DEBUG2(XPR(NTR "target in %s: %" Q "u[%" Z "u] %" Q "u(%" Q "u) "
  106             "verified %" Q "u\n",
  107             encoding ? "encoding" : "decoding",
  108             target_iterator.Offset(),
  109             target_block.Size(),
  110             target_iterator.Blkno(),
  111             blks,
  112             verified_bytes));
  113 
  114       if (blks == 0 || target_iterator.Blkno() == (blks - 1)) {
  115     xd3_set_flags(&encode_stream, XD3_FLUSH | encode_stream.flags);
  116       }
  117 
  118       xd3_avail_input(&encode_stream, target_block.Data(), target_block.Size());
  119       encoded_bytes += target_block.Size();
  120 
  121     process:
  122       int ret;
  123       const char *msg;
  124       if (encoding) {
  125     ret = xd3_encode_input(&encode_stream);
  126     msg = encode_stream.msg;
  127       } else {
  128     ret = xd3_decode_input(&decode_stream);
  129     msg = decode_stream.msg;
  130       }
  131       (void) msg;
  132 
  133       switch (ret) {
  134       case XD3_OUTPUT:
  135     if (encoding) {
  136       if (coded_data != NULL) {
  137         // Optional encoded-output to the caller
  138         coded_data->Append(encode_stream.next_out,
  139                    encode_stream.avail_out);
  140       }
  141       // Feed this data to the decoder.
  142       xd3_avail_input(&decode_stream,
  143               encode_stream.next_out,
  144               encode_stream.avail_out);
  145       xd3_consume_output(&encode_stream);
  146       encoding = false;
  147     } else {
  148       decoded_block.Append(decode_stream.next_out,
  149                    decode_stream.avail_out);
  150       xd3_consume_output(&decode_stream);
  151     }
  152     goto process;
  153 
  154       case XD3_GETSRCBLK: {
  155     xd3_source *src = (encoding ? &encode_source : &decode_source);
  156     Block *block = (encoding ? &encode_source_block : &decode_source_block);
  157     if (encoding) {
  158       IF_DEBUG2(XPR(NTR "[srcblock] %" Q "u last srcpos %" Q "u "
  159             "encodepos %" Q "u\n",
  160             encode_source.getblkno,
  161             encode_stream.match_last_srcpos,
  162             encode_stream.input_position + encode_stream.total_in));
  163     }
  164 
  165     source_iterator.SetBlock(src->getblkno);
  166     source_iterator.Get(block);
  167     src->curblkno = src->getblkno;
  168     src->onblk = block->Size();
  169     src->curblk = block->Data();
  170 
  171     goto process;
  172       }
  173 
  174       case XD3_INPUT:
  175     if (!encoding) {
  176       encoding = true;
  177       goto process;
  178     } else {
  179       if (done_after_input) {
  180         done = true;
  181         continue;
  182       }
  183 
  184       if (target_block.Size() < target_iterator.BlockSize()) {
  185         encoding = false;
  186       } else {
  187         target_iterator.Next();
  188       }
  189       continue;
  190     }
  191 
  192       case XD3_WINFINISH:
  193     if (encoding) {
  194       if (encode_stream.flags & XD3_FLUSH) {
  195         done_after_input = true;
  196       }
  197       encoding = false;
  198     } else {
  199      CHECK_EQ(0, CmpDifferentBlockBytesAtOffset(decoded_block,
  200                             target_file,
  201                             verified_bytes));
  202      verified_bytes += decoded_block.Size();
  203      decoded_block.Reset();
  204      encoding = true;
  205        }
  206        goto process;
  207 
  208      case XD3_WINSTART:
  209      case XD3_GOTHEADER:
  210        goto process;
  211 
  212      default:
  213        XPR(NTR "%s = %s %s\n", encoding ? "E " : " D",
  214        xd3_strerror(ret),
  215        msg == NULL ? "" : msg);
  216 
  217        CHECK_EQ(0, ret);
  218        CHECK_EQ(-1, ret);
  219      }
  220    }
  221 
  222    CHECK_EQ(target_file.Size(), encoded_bytes);
  223    CHECK_EQ(target_file.Size(), verified_bytes);
  224    CHECK_EQ(0, xd3_close_stream(&decode_stream));
  225    CHECK_EQ(0, xd3_close_stream(&encode_stream));
  226    xd3_free_stream(&encode_stream);
  227    xd3_free_stream(&decode_stream);
  228  }
  229 
  230   void MainEncodeDecode(const TmpFile &source_file,
  231             const TmpFile &target_file,
  232             ExtFile *coded_data,
  233             const Options &options) {
  234     vector<const char*> ecmd;
  235     char bbuf[16];
  236     snprintf(bbuf, sizeof(bbuf), "-B%" Q "u", options.encode_srcwin_maxsz);
  237     ecmd.push_back("xdelta3");
  238     ecmd.push_back(bbuf);
  239     ecmd.push_back("-s");
  240     ecmd.push_back(source_file.Name());
  241     ecmd.push_back(target_file.Name());
  242     ecmd.push_back(coded_data->Name());
  243     ecmd.push_back(NULL);
  244 
  245     CHECK_EQ(0, xd3_main_cmdline(ecmd.size() - 1,
  246                  const_cast<char**>(&ecmd[0])));
  247 
  248     vector<const char*> dcmd;
  249     ExtFile recon_file;
  250     dcmd.push_back("xdelta3");
  251     ecmd.push_back(bbuf);
  252     dcmd.push_back("-d");
  253     dcmd.push_back("-s");
  254     dcmd.push_back(source_file.Name());
  255     dcmd.push_back(coded_data->Name());
  256     dcmd.push_back(recon_file.Name());
  257     dcmd.push_back(NULL);
  258 
  259     CHECK_EQ(0, xd3_main_cmdline(dcmd.size() - 1,
  260                  const_cast<char**>(&dcmd[0])));
  261 
  262     CHECK_EQ(0, test_compare_files(recon_file.Name(),
  263                    target_file.Name()));
  264   }
  265 
  266   // Similar to xd3_process_memory, with support for test Options.
  267   // Exercises xd3_process_stream.
  268   int TestProcessMemory (int            is_encode,
  269              int          (*func) (xd3_stream *),
  270              const uint8_t *input,
  271              usize_t        input_size,
  272              const uint8_t *source,
  273              usize_t        source_size,
  274              uint8_t       *output,
  275              usize_t       *output_size,
  276              usize_t        output_size_max,
  277              const Options &options) {
  278     xd3_stream stream;
  279     xd3_config config;
  280     xd3_source src;
  281     int ret;
  282 
  283     memset (& stream, 0, sizeof (stream));
  284     memset (& config, 0, sizeof (config));
  285 
  286     if (is_encode)
  287       {
  288     config.winsize = input_size;
  289     config.iopt_size = options.iopt_size;
  290     config.sprevsz = xd3_pow2_roundup (config.winsize);
  291       }
  292 
  293     if ((ret = xd3_config_stream (&stream, &config)) != 0)
  294       {
  295     goto exit;
  296       }
  297 
  298     if (source != NULL)
  299       {
  300     memset (& src, 0, sizeof (src));
  301 
  302     src.blksize = source_size;
  303     src.onblk = source_size;
  304     src.curblk = source;
  305     src.curblkno = 0;
  306     src.max_winsize = source_size;
  307 
  308     if ((ret = xd3_set_source_and_size (&stream, &src, source_size)) != 0)
  309       {
  310         goto exit;
  311       }
  312       }
  313 
  314     if ((ret = xd3_process_stream (is_encode,
  315                    & stream,
  316                    func, 1,
  317                    input, input_size,
  318                    output,
  319                    output_size,
  320                    output_size_max)) != 0)
  321       {
  322     goto exit;
  323       }
  324 
  325   exit:
  326     if (ret != 0)
  327       {
  328     IF_DEBUG2 (DP(RINT "test_process_memory: %d: %s\n", ret, stream.msg));
  329       }
  330     xd3_free_stream(&stream);
  331     return ret;
  332   }
  333 
  334   void EncodeDecodeAPI(const FileSpec &spec0, const FileSpec &spec1, 
  335                Block *delta, const Options &options) {
  336     Block from;
  337     Block to;
  338     spec0.Get(&from, 0, spec0.Size());
  339     spec1.Get(&to, 0, spec1.Size());
  340 
  341     delta->SetSize(to.Size() * 1.5);
  342     usize_t out_size;
  343     int enc_ret = TestProcessMemory(true,
  344                     &xd3_encode_input,
  345                     to.Data(),
  346                     to.Size(),
  347                     from.Data(),
  348                     from.Size(),
  349                     delta->Data(),
  350                     &out_size,
  351                     delta->Size(),
  352                     options);
  353     CHECK_EQ(0, enc_ret);
  354     delta->SetSize(out_size);
  355 
  356     Block recon;
  357     recon.SetSize(to.Size());
  358     usize_t recon_size;
  359     int dec_ret = xd3_decode_memory(delta->Data(),
  360                     delta->Size(),
  361                     from.Data(),
  362                     from.Size(),
  363                     recon.Data(),
  364                     &recon_size,
  365                     recon.Size(),
  366                     0);
  367     CHECK_EQ(0, dec_ret);
  368     CHECK_EQ(0, CmpDifferentBlockBytes(to, recon));
  369   }
  370 
  371 //////////////////////////////////////////////////////////////////////
  372 
  373 void TestPrintf() {
  374   char buf[64];
  375   xoff_t x = XOFF_T_MAX;
  376   snprintf_func (buf, sizeof(buf), "%" Q "u", x);
  377   const char *expect = XD3_USE_LARGEFILE64 ?
  378     "18446744073709551615" : "4294967295";
  379   XD3_ASSERT(strcmp (buf, expect) == 0);
  380 }
  381 
  382 void TestRandomNumbers() {
  383   MTRandom rand;
  384   int rounds = 1<<20;
  385   uint64_t usum = 0;
  386   uint64_t esum = 0;
  387 
  388   for (int i = 0; i < rounds; i++) {
  389     usum += rand.Rand32();
  390     esum += rand.ExpRand32(1024);
  391   }
  392 
  393   double allowed_error = 0.01;
  394 
  395   uint32_t umean = usum / rounds;
  396   uint32_t emean = esum / rounds;
  397 
  398   uint32_t uexpect = UINT32_MAX / 2;
  399   uint32_t eexpect = 1024;
  400 
  401   if (umean < uexpect * (1.0 - allowed_error) ||
  402       umean > uexpect * (1.0 + allowed_error)) {
  403     XPR(NT "uniform mean error: %u != %u\n", umean, uexpect);
  404     abort();
  405   }
  406 
  407   if (emean < eexpect * (1.0 - allowed_error) ||
  408       emean > eexpect * (1.0 + allowed_error)) {
  409     XPR(NT "exponential mean error: %u != %u\n", emean, eexpect);
  410     abort();
  411   }
  412 }
  413 
  414 void TestRandomFile() {
  415   MTRandom rand1;
  416   FileSpec spec1(&rand1);
  417   BlockIterator bi(spec1);
  418 
  419   spec1.GenerateFixedSize(0);
  420   CHECK_EQ(0, spec1.Size());
  421   CHECK_EQ(0, spec1.Segments());
  422   CHECK_EQ(0, spec1.Blocks());
  423   bi.SetBlock(0);
  424   CHECK_EQ(0, bi.BytesOnBlock());
  425 
  426   spec1.GenerateFixedSize(1);
  427   CHECK_EQ(1, spec1.Size());
  428   CHECK_EQ(1, spec1.Segments());
  429   CHECK_EQ(1, spec1.Blocks());
  430   bi.SetBlock(0);
  431   CHECK_EQ(1, bi.BytesOnBlock());
  432 
  433   spec1.GenerateFixedSize(Constants::BLOCK_SIZE);
  434   CHECK_EQ(Constants::BLOCK_SIZE, spec1.Size());
  435   CHECK_EQ(1, spec1.Segments());
  436   CHECK_EQ(1, spec1.Blocks());
  437   bi.SetBlock(0);
  438   CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
  439   bi.SetBlock(1);
  440   CHECK_EQ(0, bi.BytesOnBlock());
  441 
  442   spec1.GenerateFixedSize(Constants::BLOCK_SIZE + 1);
  443   CHECK_EQ(Constants::BLOCK_SIZE + 1, spec1.Size());
  444   CHECK_EQ(2, spec1.Segments());
  445   CHECK_EQ(2, spec1.Blocks());
  446   bi.SetBlock(0);
  447   CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
  448   bi.SetBlock(1);
  449   CHECK_EQ(1, bi.BytesOnBlock());
  450 
  451   spec1.GenerateFixedSize(Constants::BLOCK_SIZE * 2);
  452   CHECK_EQ(Constants::BLOCK_SIZE * 2, spec1.Size());
  453   CHECK_EQ(2, spec1.Segments());
  454   CHECK_EQ(2, spec1.Blocks());
  455   bi.SetBlock(0);
  456   CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
  457   bi.SetBlock(1);
  458   CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
  459 }
  460 
  461 void TestFirstByte() {
  462   MTRandom rand;
  463   FileSpec spec0(&rand);
  464   FileSpec spec1(&rand);
  465 
  466   spec0.GenerateFixedSize(0);
  467   spec1.GenerateFixedSize(1);
  468   CHECK_EQ(0, CmpDifferentBytes(spec0, spec0));
  469   CHECK_EQ(0, CmpDifferentBytes(spec1, spec1));
  470   CHECK_EQ(1, CmpDifferentBytes(spec0, spec1));
  471   CHECK_EQ(1, CmpDifferentBytes(spec1, spec0));
  472 
  473   spec0.GenerateFixedSize(1);
  474   spec0.ModifyTo(Modify1stByte(), &spec1);
  475   CHECK_EQ(1, CmpDifferentBytes(spec0, spec1));
  476 
  477   spec0.GenerateFixedSize(Constants::BLOCK_SIZE + 1);
  478   spec0.ModifyTo(Modify1stByte(), &spec1);
  479   CHECK_EQ(1, CmpDifferentBytes(spec0, spec1));
  480 
  481   SizeIterator<size_t, Sizes> si(&rand, Constants::TEST_ROUNDS);
  482 
  483   for (; !si.Done(); si.Next()) {
  484     size_t size = si.Get();
  485     if (size == 0) {
  486       continue;
  487     }
  488     spec0.GenerateFixedSize(size);
  489     spec0.ModifyTo(Modify1stByte(), &spec1);
  490     InMemoryEncodeDecode(spec0, spec1, NULL, Options());
  491   }
  492 }
  493 
  494 void TestModifyMutator() {
  495   MTRandom rand;
  496   FileSpec spec0(&rand);
  497   FileSpec spec1(&rand);
  498 
  499   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
  500 
  501   struct {
  502     size_t size;
  503     size_t addr;
  504   } test_cases[] = {
  505     { Constants::BLOCK_SIZE, 0 },
  506     { Constants::BLOCK_SIZE / 2, 1 },
  507     { Constants::BLOCK_SIZE, 1 },
  508     { Constants::BLOCK_SIZE * 2, 1 },
  509   };
  510 
  511   for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
  512     ChangeList cl1;
  513     cl1.push_back(Change(Change::MODIFY, test_cases[i].size,
  514              test_cases[i].addr));
  515     spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
  516     CHECK_EQ(spec0.Size(), spec1.Size());
  517 
  518     size_t diff = CmpDifferentBytes(spec0, spec1);
  519     CHECK_LE(diff, test_cases[i].size);
  520 
  521     // There is a 1/256 probability of the changed byte matching the
  522     // original value.  The following allows double the probability to
  523     // pass.
  524     CHECK_GE(diff, test_cases[i].size - (2 * test_cases[i].size / 256));
  525 
  526     InMemoryEncodeDecode(spec0, spec1, NULL, Options());
  527   }
  528 }
  529 
  530 void TestAddMutator() {
  531   MTRandom rand;
  532   FileSpec spec0(&rand);
  533   FileSpec spec1(&rand);
  534 
  535   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 2);
  536   // TODO: fix this test (for all block sizes)!  it's broken because
  537   // the same byte could be added?
  538 
  539   struct {
  540     size_t size;
  541     size_t addr;
  542     size_t expected_adds;
  543   } test_cases[] = {
  544     { 1, 0,                         2 /* 1st byte, last byte (short block) */ },
  545     { 1, 1,                         3 /* 1st 2 bytes, last byte */ },
  546     { 1, Constants::BLOCK_SIZE - 1, 2 /* changed, last */ },
  547     { 1, Constants::BLOCK_SIZE,     2 /* changed, last */ },
  548     { 1, Constants::BLOCK_SIZE + 1, 3 /* changed + 1st of 2nd block, last */ },
  549     { 1, 2 * Constants::BLOCK_SIZE, 1 /* last byte */ },
  550   };
  551 
  552   for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
  553     ChangeList cl1;
  554     cl1.push_back(Change(Change::ADD, test_cases[i].size, test_cases[i].addr));
  555     spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
  556     CHECK_EQ(spec0.Size() + test_cases[i].size, spec1.Size());
  557 
  558     Block coded;
  559     InMemoryEncodeDecode(spec0, spec1, &coded, Options());
  560 
  561     Delta delta(coded);
  562     CHECK_EQ(test_cases[i].expected_adds,
  563          delta.AddedBytes());
  564   }
  565 }
  566 
  567 void TestDeleteMutator() {
  568   MTRandom rand;
  569   FileSpec spec0(&rand);
  570   FileSpec spec1(&rand);
  571 
  572   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 4);
  573 
  574   struct {
  575     size_t size;
  576     size_t addr;
  577   } test_cases[] = {
  578     // Note: an entry { Constants::BLOCK_SIZE, 0 },
  579     // does not work because the xd3_srcwin_move_point logic won't
  580     // find a copy if it occurs >= double its size into the file.
  581     { Constants::BLOCK_SIZE / 2, 0 },
  582     { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2 },
  583     { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE / 2 },
  584     { Constants::BLOCK_SIZE * 2, Constants::BLOCK_SIZE * 3 / 2 },
  585     { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE * 2 },
  586   };
  587 
  588   for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
  589     ChangeList cl1;
  590     cl1.push_back(Change(Change::DELRANGE, test_cases[i].size,
  591              test_cases[i].addr));
  592     spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
  593     CHECK_EQ(spec0.Size() - test_cases[i].size, spec1.Size());
  594 
  595     Block coded;
  596     InMemoryEncodeDecode(spec0, spec1, &coded, Options());
  597 
  598     Delta delta(coded);
  599     CHECK_EQ(0, delta.AddedBytes());
  600   }
  601 }
  602 
  603 void TestCopyMutator() {
  604   MTRandom rand;
  605   FileSpec spec0(&rand);
  606   FileSpec spec1(&rand);
  607 
  608   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
  609 
  610   struct {
  611     size_t size;
  612     size_t from;
  613     size_t to;
  614   } test_cases[] = {
  615     // Copy is difficult to write tests for because where Xdelta finds
  616     // copies, it does not enter checksums.  So these tests copy data from
  617     // later to earlier so that checksumming will start.
  618     { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2, 0 },
  619     { Constants::BLOCK_SIZE, 2 * Constants::BLOCK_SIZE,
  620       Constants::BLOCK_SIZE, },
  621   };
  622 
  623   for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
  624     ChangeList cl1;
  625     cl1.push_back(Change(Change::COPY, test_cases[i].size,
  626              test_cases[i].from, test_cases[i].to));
  627     spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
  628     CHECK_EQ(spec0.Size() + test_cases[i].size, spec1.Size());
  629 
  630     Block coded;
  631     InMemoryEncodeDecode(spec0, spec1, &coded, Options());
  632 
  633     Delta delta(coded);
  634     CHECK_EQ(0, delta.AddedBytes());
  635   }
  636 }
  637 
  638 void TestMoveMutator() {
  639   MTRandom rand;
  640   FileSpec spec0(&rand);
  641   FileSpec spec1(&rand);
  642 
  643   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
  644 
  645   struct {
  646     size_t size;
  647     size_t from;
  648     size_t to;
  649   } test_cases[] = {
  650     // This is easier to test than Copy but has the same trouble as Delete.
  651     { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2, 0 },
  652     { Constants::BLOCK_SIZE / 2, 0, Constants::BLOCK_SIZE / 2 },
  653     { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE, 2 *
  654       Constants::BLOCK_SIZE },
  655     { Constants::BLOCK_SIZE, 2 * Constants::BLOCK_SIZE,
  656       Constants::BLOCK_SIZE },
  657     { Constants::BLOCK_SIZE * 3 / 2, Constants::BLOCK_SIZE,
  658       Constants::BLOCK_SIZE * 3 / 2 },
  659 
  660     // This is a no-op
  661     { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE * 2,
  662       3 * Constants::BLOCK_SIZE },
  663   };
  664 
  665   for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
  666     ChangeList cl1;
  667     cl1.push_back(Change(Change::MOVE, test_cases[i].size,
  668              test_cases[i].from, test_cases[i].to));
  669     spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
  670     CHECK_EQ(spec0.Size(), spec1.Size());
  671 
  672     Block coded;
  673     InMemoryEncodeDecode(spec0, spec1, &coded, Options());
  674 
  675     Delta delta(coded);
  676     CHECK_EQ(0, delta.AddedBytes());
  677   }
  678 }
  679 
  680 void TestOverwriteMutator() {
  681   MTRandom rand;
  682   FileSpec spec0(&rand);
  683   FileSpec spec1(&rand);
  684 
  685   spec0.GenerateFixedSize(Constants::BLOCK_SIZE);
  686 
  687   ChangeList cl1;
  688   cl1.push_back(Change(Change::COPYOVER, 10, 0, 20));
  689   spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
  690   CHECK_EQ(spec0.Size(), spec1.Size());
  691 
  692   Block b0, b1;
  693   BlockIterator(spec0).Get(&b0);
  694   BlockIterator(spec1).Get(&b1);
  695 
  696   CHECK(memcmp(b0.Data(), b1.Data() + 20, 10) == 0);
  697   CHECK(memcmp(b0.Data(), b1.Data(), 20) == 0);
  698   CHECK(memcmp(b0.Data() + 30, b1.Data() + 30,
  699            Constants::BLOCK_SIZE - 30) == 0);
  700 
  701   xoff_t zero = 0;
  702   cl1.clear();
  703   cl1.push_back(Change(Change::COPYOVER, 10, 20, zero));
  704   spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
  705   CHECK_EQ(spec0.Size(), spec1.Size());
  706 
  707   BlockIterator(spec0).Get(&b0);
  708   BlockIterator(spec1).Get(&b1);
  709 
  710   CHECK(memcmp(b0.Data() + 20, b1.Data(), 10) == 0);
  711   CHECK(memcmp(b0.Data() + 10, b1.Data() + 10,
  712            Constants::BLOCK_SIZE - 10) == 0);
  713 }
  714 
  715 // Note: this test is written to expose a problem, but the problem was
  716 // only exposed with BLOCK_SIZE = 128.
  717 void TestNonBlocking() {
  718   MTRandom rand;
  719   FileSpec spec0(&rand);
  720   FileSpec spec1(&rand);
  721   FileSpec spec2(&rand);
  722 
  723   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
  724 
  725   // This is a lazy target match
  726   Change ct(Change::COPYOVER, 22,
  727         Constants::BLOCK_SIZE + 50,
  728         Constants::BLOCK_SIZE + 20);
  729 
  730   // This is a source match just after the block boundary, shorter
  731   // than the lazy target match.
  732   Change cs1(Change::COPYOVER, 16,
  733          Constants::BLOCK_SIZE + 51,
  734          Constants::BLOCK_SIZE - 1);
  735 
  736   // This overwrites the original source bytes.
  737   Change cs2(Change::MODIFY, 108,
  738          Constants::BLOCK_SIZE + 20);
  739 
  740   // This changes the first blocks
  741   Change c1st(Change::MODIFY, Constants::BLOCK_SIZE - 2, 0);
  742 
  743   ChangeList csl;
  744   csl.push_back(cs1);
  745   csl.push_back(cs2);
  746   csl.push_back(c1st);
  747 
  748   spec0.ModifyTo(ChangeListMutator(csl), &spec1);
  749 
  750   ChangeList ctl;
  751   ctl.push_back(ct);
  752   ctl.push_back(c1st);
  753 
  754   spec0.ModifyTo(ChangeListMutator(ctl), &spec2);
  755 
  756   InMemoryEncodeDecode(spec1, spec2, NULL, Options());
  757 }
  758 
  759 void TestEmptyInMemory() {
  760   MTRandom rand;
  761   FileSpec spec0(&rand);
  762   FileSpec spec1(&rand);
  763   Block block;
  764 
  765   spec0.GenerateFixedSize(0);
  766   spec1.GenerateFixedSize(0);
  767 
  768   InMemoryEncodeDecode(spec0, spec1, &block, Options());
  769 
  770   Delta delta(block);
  771   CHECK_LT(0, block.Size());
  772   CHECK_EQ(1, delta.Windows());
  773 }
  774 
  775 void TestBlockInMemory() {
  776   MTRandom rand;
  777   FileSpec spec0(&rand);
  778   FileSpec spec1(&rand);
  779   Block block;
  780 
  781   spec0.GenerateFixedSize(Constants::BLOCK_SIZE);
  782   spec1.GenerateFixedSize(Constants::BLOCK_SIZE);
  783 
  784   InMemoryEncodeDecode(spec0, spec1, &block, Options());
  785 
  786   Delta delta(block);
  787   CHECK_EQ(spec1.Blocks(Constants::WINDOW_SIZE), delta.Windows());
  788 }
  789 
  790 void TestSmallStride() {
  791   MTRandom rand;
  792   FileSpec spec0(&rand);
  793   usize_t size = Constants::BLOCK_SIZE * 4;
  794   spec0.GenerateFixedSize(size);
  795 
  796   // Note: Not very good performance due to hash collisions, note 3x
  797   // multiplier below.
  798   for (int s = 15; s < 101; s++) {
  799     usize_t changes = 0;
  800     ChangeList cl;
  801     for (usize_t j = s; j < size; j += s, ++changes)
  802       {
  803     cl.push_back(Change(Change::MODIFY, 1, j));
  804       }
  805 
  806     FileSpec spec1(&rand);
  807     spec0.ModifyTo(ChangeListMutator(cl), &spec1);
  808 
  809     Options options;
  810     options.encode_srcwin_maxsz = size;
  811     options.iopt_size = 128;
  812     options.smatch_cfg = XD3_SMATCH_SLOW;
  813     options.size_known = false;
  814 
  815     Block block;
  816     InMemoryEncodeDecode(spec0, spec1, &block, options);
  817     Delta delta(block);
  818 
  819     IF_DEBUG1(DP(RINT "[stride=%d] changes=%" W "u adds=%" Q "u\n",
  820          s, changes, delta.AddedBytes()));
  821     double allowance = Constants::BLOCK_SIZE < 8192 || s < 30 ? 3.0 : 1.1;
  822     CHECK_GE(allowance * changes, (double)delta.AddedBytes());
  823   }
  824 }
  825 
  826 void TestCopyWindow() {
  827   // Construct an input that has many copies, to fill the IOPT buffer
  828   // and force a source window decision.  "srclen" may be set to a
  829   // value that goes beyond the end-of-source.
  830   const int clen = 16;
  831   const int size = 4096;
  832   const int nmov = size / clen;
  833   const int iters = 16;
  834   uint32_t added_01 = 0;
  835   uint32_t added_10 = 0;
  836   for (int i = 1; i <= iters; i++) {
  837     MTRandom rand(MTRandom::TEST_SEED1 * i);
  838     FileSpec spec0(&rand);
  839     ChangeList cl;
  840 
  841     spec0.GenerateFixedSize(size);
  842 
  843     for (int j = 0; j < nmov; j += 2)
  844       {
  845     cl.push_back(Change(Change::MOVE,
  846                 clen, (j + 1) * clen, j * clen));
  847       }
  848 
  849     FileSpec spec1(&rand);
  850     spec0.ModifyTo(ChangeListMutator(cl), &spec1);
  851 
  852     Options options;
  853     options.encode_srcwin_maxsz = size;
  854     options.iopt_size = 128;
  855     options.smatch_cfg = XD3_SMATCH_SLOW;
  856 
  857     Block block1;
  858     InMemoryEncodeDecode(spec0, spec1, &block1, options);
  859     Delta delta1(block1);
  860     // Allow one missed window (e.g., hash collisions)
  861     added_01 += delta1.AddedBytes();
  862 
  863     Block block2;
  864     InMemoryEncodeDecode(spec1, spec0, &block2, options);
  865     Delta delta2(block2);
  866     // Allow one missed window (e.g., hash collisions)
  867     added_10 += delta2.AddedBytes();
  868 
  869     Block block3;
  870     Block block4;
  871     EncodeDecodeAPI(spec0, spec1, &block3, options);
  872     EncodeDecodeAPI(spec1, spec0, &block4, options);
  873   }
  874   // Average less than 0.5 misses (of length clen) per iteration.
  875   CHECK_GE(clen * iters / 2, added_01);
  876   CHECK_GE(clen * iters / 2, added_10);
  877 }
  878 
  879 void TestCopyFromEnd() {
  880   // Copies from the end of the source buffer, which reach a block
  881   // boundary end-of-file.
  882   const int size = 4096;
  883   const int clen = 16;
  884   const int nmov = (size / 2) / clen;
  885   const int iters = 16;
  886   uint32_t added_01 = 0;
  887   uint32_t added_10 = 0;
  888   for (int i = 1; i <= iters; i++) {
  889     MTRandom rand(MTRandom::TEST_SEED1 * i);
  890     FileSpec spec0(&rand);
  891     ChangeList cl;
  892 
  893     spec0.GenerateFixedSize(size);
  894 
  895     cl.push_back(Change(Change::MODIFY, 2012, 2048));
  896 
  897     for (int j = 0; j < nmov; j += 2)
  898       {
  899     cl.push_back(Change(Change::MOVE,
  900                 clen, (j + 1) * clen, j * clen));
  901       }
  902 
  903     cl.push_back(Change(Change::COPYOVER, 28, 4068, 3000));
  904     cl.push_back(Change(Change::COPYOVER, 30, 4066, 3100));
  905     cl.push_back(Change(Change::COPYOVER, 32, 4064, 3200));
  906 
  907     FileSpec spec1(&rand);
  908     spec0.ModifyTo(ChangeListMutator(cl), &spec1);
  909 
  910     Options options;
  911     options.encode_srcwin_maxsz = size;
  912     options.iopt_size = 128;
  913     options.smatch_cfg = XD3_SMATCH_SLOW;
  914 
  915     Block block1;
  916     InMemoryEncodeDecode(spec0, spec1, &block1, options);
  917     Delta delta1(block1);
  918     added_01 += delta1.AddedBytes();
  919 
  920     Block block2;
  921     InMemoryEncodeDecode(spec1, spec0, &block2, options);
  922     Delta delta2(block2);
  923     added_10 += delta2.AddedBytes();
  924 
  925     Block block3;
  926     Block block4;
  927     EncodeDecodeAPI(spec0, spec1, &block3, options);
  928     EncodeDecodeAPI(spec1, spec0, &block4, options);
  929   }
  930   CHECK_GE(2000 * iters, added_01);
  931   CHECK_LE(2000 * iters, added_10);
  932 }
  933 
  934 void TestHalfBlockCopy() {
  935   // Create a half-block copy, 7.5 blocks apart, in a pair of files:
  936   //       0             1     ...     6             7
  937   // spec0 [bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb][ccccc][bbbb_]
  938   // spec1 [aaaaa][ccccc][aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa_]
  939   // where stage=
  940   // 0: the final block is full
  941   //   a. (source)spec1->(target)spec0 copies block C: reads 8 source
  942   //      blocks during target block 0.
  943   //   b. (source)spec0->(target)spec1 does not copy block C b/c attempt
  944   //      to read past EOF empties block 0 from (virtual) block cache
  945   // 1: the final block is less than full.
  946   //   a. (same) copies block C
  947   //   b. (same) copies block C, unlike 0a, no attempt to read past EOF
  948   //
  949   // "virtual" above refers to XD3_TOOFARBACK, since there is no caching
  950   // in the API, there is simply a promise not to request blocks that are
  951   // beyond source->max_winsize from the last known source file position.
  952   for (int stage = 0; stage < 2; stage++)
  953     {
  954       IF_DEBUG1 (DP(RINT "half_block_copy stage %d\n", stage));
  955 
  956       MTRandom rand;
  957       FileSpec spec0(&rand);
  958       FileSpec spec1(&rand);
  959 
  960       spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 8 - stage);
  961 
  962       ChangeList cl1;
  963       cl1.push_back(Change(Change::MODIFY,
  964                Constants::BLOCK_SIZE / 2,  // size
  965                0));
  966       cl1.push_back(Change(Change::COPYOVER,
  967                Constants::BLOCK_SIZE / 2,  // size
  968                Constants::BLOCK_SIZE * 7,  // offset
  969                Constants::BLOCK_SIZE / 2));
  970       cl1.push_back(Change(Change::MODIFY,
  971                Constants::BLOCK_SIZE * 7,
  972                Constants::BLOCK_SIZE - stage));
  973       spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
  974 
  975       Options options;
  976       options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * 8;
  977 
  978       Block block0;
  979       Block block1;
  980       InMemoryEncodeDecode(spec0, spec1, &block0, options);
  981       InMemoryEncodeDecode(spec1, spec0, &block1, options);
  982 
  983       Delta delta0(block0);
  984       Delta delta1(block1);
  985 
  986       const int yes =
  987     Constants::BLOCK_SIZE * 8 - Constants::BLOCK_SIZE / 2;
  988       const int no =
  989     Constants::BLOCK_SIZE * 8 - Constants::BLOCK_SIZE / 2;
  990 
  991       if (stage == 0)
  992     {
  993       CHECK_EQ(yes, delta0.AddedBytes());
  994       CHECK_EQ(no, delta1.AddedBytes());
  995     }
  996       else
  997     {
  998       CHECK_EQ(yes, delta0.AddedBytes());
  999       CHECK_EQ(yes, delta1.AddedBytes());
 1000     }
 1001     }
 1002 }
 1003 
 1004 void FourWayMergeTest(const FileSpec &spec0,
 1005               const FileSpec &spec1,
 1006               const FileSpec &spec2,
 1007               const FileSpec &spec3) {
 1008   TmpFile f0, f1, f2, f3;
 1009   ExtFile d01, d12, d23;
 1010   Options options;
 1011   options.encode_srcwin_maxsz =
 1012     std::max(spec0.Size(), options.encode_srcwin_maxsz);
 1013 
 1014   spec0.WriteTmpFile(&f0);
 1015   spec1.WriteTmpFile(&f1);
 1016   spec2.WriteTmpFile(&f2);
 1017   spec3.WriteTmpFile(&f3);
 1018 
 1019   MainEncodeDecode(f0, f1, &d01, options);
 1020   MainEncodeDecode(f1, f2, &d12, options);
 1021   MainEncodeDecode(f2, f3, &d23, options);
 1022 
 1023   // Merge 2
 1024   ExtFile out;
 1025   vector<const char*> mcmd;
 1026   mcmd.push_back("xdelta3");
 1027   mcmd.push_back("merge");
 1028   mcmd.push_back("-m");
 1029   mcmd.push_back(d01.Name());
 1030   mcmd.push_back(d12.Name());
 1031   mcmd.push_back(out.Name());
 1032   mcmd.push_back(NULL);
 1033 
 1034   // XPR(NTR "Running one merge: %s\n", CommandToString(mcmd).c_str());
 1035   CHECK_EQ(0, xd3_main_cmdline(mcmd.size() - 1,
 1036                    const_cast<char**>(&mcmd[0])));
 1037 
 1038   ExtFile recon;
 1039   vector<const char*> tcmd;
 1040   tcmd.push_back("xdelta3");
 1041   tcmd.push_back("-d");
 1042   tcmd.push_back("-s");
 1043   tcmd.push_back(f0.Name());
 1044   tcmd.push_back(out.Name());
 1045   tcmd.push_back(recon.Name());
 1046   tcmd.push_back(NULL);
 1047 
 1048   // XPR(NTR "Running one recon! %s\n", CommandToString(tcmd).c_str());
 1049   CHECK_EQ(0, xd3_main_cmdline(tcmd.size() - 1,
 1050                    const_cast<char**>(&tcmd[0])));
 1051   // XPR(NTR "Should equal! %s\n", f2.Name());
 1052 
 1053   CHECK(recon.EqualsSpec(spec2));
 1054 
 1055   // Merge 3
 1056   ExtFile out3;
 1057   vector<const char*> mcmd3;
 1058   mcmd3.push_back("xdelta3");
 1059   mcmd3.push_back("merge");
 1060   mcmd3.push_back("-m");
 1061   mcmd3.push_back(d01.Name());
 1062   mcmd3.push_back("-m");
 1063   mcmd3.push_back(d12.Name());
 1064   mcmd3.push_back(d23.Name());
 1065   mcmd3.push_back(out3.Name());
 1066   mcmd3.push_back(NULL);
 1067 
 1068   // XPR(NTR "Running one 3-merge: %s\n", CommandToString(mcmd3).c_str());
 1069   CHECK_EQ(0, xd3_main_cmdline(mcmd3.size() - 1,
 1070                    const_cast<char**>(&mcmd3[0])));
 1071 
 1072   ExtFile recon3;
 1073   vector<const char*> tcmd3;
 1074   tcmd3.push_back("xdelta3");
 1075   tcmd3.push_back("-d");
 1076   tcmd3.push_back("-s");
 1077   tcmd3.push_back(f0.Name());
 1078   tcmd3.push_back(out3.Name());
 1079   tcmd3.push_back(recon3.Name());
 1080   tcmd3.push_back(NULL);
 1081 
 1082   // XPR(NTR "Running one 3-recon %s\n", CommandToString(tcmd3).c_str());
 1083   CHECK_EQ(0, xd3_main_cmdline(tcmd3.size() - 1,
 1084                    const_cast<char**>(&tcmd3[0])));
 1085   // XPR(NTR "Should equal %s\n", f3.Name());
 1086 
 1087   CHECK(recon3.EqualsSpec(spec3));
 1088 }
 1089 
 1090 void TestMergeCommand1() {
 1091   /* Repeat random-input testing for a number of iterations.
 1092    * Test 2, 3, and 4-file scenarios (i.e., 1, 2, and 3-delta merges). */
 1093   MTRandom rand;
 1094   FileSpec spec0(&rand);
 1095   FileSpec spec1(&rand);
 1096   FileSpec spec2(&rand);
 1097   FileSpec spec3(&rand);
 1098 
 1099   SizeIterator<size_t, Sizes> si0(&rand, 10);
 1100 
 1101   for (; !si0.Done(); si0.Next()) {
 1102     size_t size0 = si0.Get();
 1103 
 1104     SizeIterator<size_t, Sizes> si1(&rand, 10);
 1105     for (; !si1.Done(); si1.Next()) {
 1106       size_t change1 = si1.Get();
 1107 
 1108       if (change1 == 0) {
 1109     continue;
 1110       }
 1111 
 1112       // XPR(NTR "S0 = %lu\n", size0);
 1113       // XPR(NTR "C1 = %lu\n", change1);
 1114       // XPR(NTR ".");
 1115 
 1116       size_t add1_pos = size0 ? rand.Rand32() % size0 : 0;
 1117       size_t del2_pos = size0 ? rand.Rand32() % size0 : 0;
 1118 
 1119       spec0.GenerateFixedSize(size0);
 1120 
 1121       ChangeList cl1, cl2, cl3;
 1122 
 1123       size_t change3 = change1;
 1124       size_t change3_pos;
 1125 
 1126       if (change3 >= size0) {
 1127     change3 = size0;
 1128     change3_pos = 0;
 1129       } else {
 1130     change3_pos = rand.Rand32() % (size0 - change3);
 1131       }
 1132 
 1133       cl1.push_back(Change(Change::ADD, change1, add1_pos));
 1134       cl2.push_back(Change(Change::DELRANGE, change1, del2_pos));
 1135       cl3.push_back(Change(Change::MODIFY, change3, change3_pos));
 1136 
 1137       spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 1138       spec1.ModifyTo(ChangeListMutator(cl2), &spec2);
 1139       spec2.ModifyTo(ChangeListMutator(cl3), &spec3);
 1140 
 1141       FourWayMergeTest(spec0, spec1, spec2, spec3);
 1142       FourWayMergeTest(spec3, spec2, spec1, spec0);
 1143     }
 1144   }
 1145 }
 1146 
 1147 void TestMergeCommand2() {
 1148   /* Same as above, different mutation pattern. */
 1149   /* TODO: run this with large sizes too */
 1150   /* TODO: run this with small sizes too */
 1151   MTRandom rand;
 1152   FileSpec spec0(&rand);
 1153   FileSpec spec1(&rand);
 1154   FileSpec spec2(&rand);
 1155   FileSpec spec3(&rand);
 1156 
 1157   SizeIterator<size_t, Sizes> si0(&rand, 10);
 1158   for (; !si0.Done(); si0.Next()) {
 1159     size_t size0 = si0.Get();
 1160 
 1161     SizeIterator<size_t, Sizes> si1(&rand, 10);
 1162     for (; !si1.Done(); si1.Next()) {
 1163       size_t size1 = si1.Get();
 1164 
 1165       SizeIterator<size_t, Sizes> si2(&rand, 10);
 1166       for (; !si2.Done(); si2.Next()) {
 1167     size_t size2 = si2.Get();
 1168 
 1169     SizeIterator<size_t, Sizes> si3(&rand, 10);
 1170     for (; !si3.Done(); si3.Next()) {
 1171       size_t size3 = si3.Get();
 1172 
 1173       // We're only interested in three sizes, strictly decreasing. */
 1174       if (size3 >= size2 || size2 >= size1 || size1 >= size0) {
 1175         continue;
 1176       }
 1177 
 1178       // XPR(NTR "S0 = %lu\n", size0);
 1179       // XPR(NTR "S1 = %lu\n", size1);
 1180       // XPR(NTR "S2 = %lu\n", size2);
 1181       // XPR(NTR "S3 = %lu\n", size3);
 1182       // XPR(NTR ".");
 1183 
 1184       spec0.GenerateFixedSize(size0);
 1185 
 1186       ChangeList cl1, cl2, cl3;
 1187 
 1188       cl1.push_back(Change(Change::DELRANGE, size0 - size1, 0));
 1189       cl2.push_back(Change(Change::DELRANGE, size0 - size2, 0));
 1190       cl3.push_back(Change(Change::DELRANGE, size0 - size3, 0));
 1191 
 1192       spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 1193       spec0.ModifyTo(ChangeListMutator(cl2), &spec2);
 1194       spec0.ModifyTo(ChangeListMutator(cl3), &spec3);
 1195 
 1196       FourWayMergeTest(spec0, spec1, spec2, spec3);
 1197       FourWayMergeTest(spec3, spec2, spec1, spec0);
 1198     }
 1199       }
 1200     }
 1201   }
 1202 }
 1203 
 1204 void TestLastFrontierBlock() {
 1205   // This test constructs an input that can expose
 1206   // https://github.com/jmacd/xdelta/issues/188
 1207   // when run through the command-line with source via a FIFO.
 1208   // That is not tested here, but the test stays.
 1209   if (Constants::WINDOW_SIZE < XD3_ALLOCSIZE)
 1210     {
 1211       return;
 1212     }
 1213 
 1214   MTRandom rand;
 1215   FileSpec spec0(&rand);
 1216   FileSpec spec1(&rand);
 1217   const xoff_t size = XD3_ALLOCSIZE * 64;  // == XD3_MINSRCWINSZ * 2
 1218   const xoff_t edit = XD3_ALLOCSIZE;
 1219 
 1220   Options options;
 1221   options.encode_srcwin_maxsz = XD3_MINSRCWINSZ;
 1222   options.block_size = XD3_ALLOCSIZE;
 1223   options.window_size = XD3_MINSRCWINSZ;
 1224   options.size_known = false;
 1225 
 1226   spec0.GenerateFixedSize(size);
 1227 
 1228   ChangeList cl;
 1229 
 1230   // Modify the 0th byte in order to induce indexing of subsequent
 1231   // bytes, but allow copying most of the file to keep the test fast.
 1232   cl.push_back(Change(Change::MODIFY, 1, edit * 31));
 1233   cl.push_back(Change(Change::COPYOVER, edit, edit * 31, edit * 63));
 1234 
 1235   spec0.ModifyTo(ChangeListMutator(cl), &spec1);
 1236 
 1237   Block noblock;
 1238   InMemoryEncodeDecode(spec0, spec1, &noblock, options);
 1239   InMemoryEncodeDecode(spec1, spec0, &noblock, options);
 1240 }
 1241 
 1242 };  // class Regtest<Constants>
 1243 
 1244 #define TEST(x) XPR(NTR #x "...\n"); regtest.x()
 1245 
 1246 // These tests are primarily tests of the testing framework itself.
 1247 template <class T>
 1248 void UnitTest() {
 1249   Regtest<T> regtest;
 1250   TEST(TestPrintf);
 1251   TEST(TestRandomNumbers);
 1252   TEST(TestRandomFile);
 1253   TEST(TestFirstByte);
 1254   TEST(TestModifyMutator);
 1255   TEST(TestAddMutator);
 1256   TEST(TestDeleteMutator);
 1257   TEST(TestCopyMutator);
 1258   TEST(TestMoveMutator);
 1259   TEST(TestOverwriteMutator);
 1260 }
 1261 
 1262 // These are Xdelta tests.
 1263 template <class T>
 1264 void MainTest() {
 1265   XPR(NT "Blocksize %" Q "u windowsize %" Z "u\n",
 1266       T::BLOCK_SIZE, T::WINDOW_SIZE);
 1267   Regtest<T> regtest;
 1268   TEST(TestEmptyInMemory);
 1269   TEST(TestBlockInMemory);
 1270   TEST(TestSmallStride);
 1271   TEST(TestCopyWindow);
 1272   TEST(TestCopyFromEnd);
 1273   TEST(TestNonBlocking);
 1274   TEST(TestHalfBlockCopy);
 1275   TEST(TestLastFrontierBlock);
 1276   TEST(TestMergeCommand1);
 1277   TEST(TestMergeCommand2);
 1278 }
 1279 
 1280 #undef TEST
 1281 
 1282 int main(int argc, char **argv)
 1283 {
 1284   vector<const char*> mcmd;
 1285   string pn;
 1286   const char *sp = strrchr(argv[0], '/');
 1287   if (sp != NULL) {
 1288     pn.append(argv[0], sp - argv[0] + 1);
 1289   }
 1290   pn.append("xdelta3");
 1291   mcmd.push_back(pn.c_str());
 1292   mcmd.push_back("test");
 1293   mcmd.push_back(NULL);
 1294 
 1295   UnitTest<SmallBlock>();
 1296   MainTest<SmallBlock>();
 1297   MainTest<MixedBlock>();
 1298   MainTest<OversizeBlock>();
 1299   MainTest<LargeBlock>();
 1300 
 1301   CHECK_EQ(0, xd3_main_cmdline(mcmd.size() - 1,
 1302                    const_cast<char**>(&mcmd[0])));
 1303 
 1304   return 0;
 1305 }
 1306