testing/regtest.cc

   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() : encode_srcwin_maxsz(1<<20),
  13                 block_size(Constants::BLOCK_SIZE),
  14                 size_known(false) { }
  15     uint64_t encode_srcwin_maxsz;
  16     size_t block_size;
  17     bool size_known;
  18   };
  19
  20 #include "segment.h"
  21 #include "modify.h"
  22 #include "file.h"
  23 #include "cmp.h"
  24 #include "delta.h"
  25
  26   void InMemoryEncodeDecode(const FileSpec &source_file,
  27                             const FileSpec &target_file,
  28                             Block *coded_data,
  29                             const Options &options = Options()) {
  30     xd3_stream encode_stream;
  31     xd3_config encode_config;
  32     xd3_source encode_source;
  33
  34     xd3_stream decode_stream;
  35     xd3_config decode_config;
  36     xd3_source decode_source;
  37     xoff_t verified_bytes = 0;
  38     xoff_t encoded_bytes = 0;
  39
  40     if (coded_data) {
  41       coded_data->Reset();
  42     }
  43
  44     memset(&encode_stream, 0, sizeof (encode_stream));
  45     memset(&encode_source, 0, sizeof (encode_source));
  46
  47     memset(&decode_stream, 0, sizeof (decode_stream));
  48     memset(&decode_source, 0, sizeof (decode_source));
  49
  50     xd3_init_config(&encode_config, XD3_ADLER32);
  51     xd3_init_config(&decode_config, XD3_ADLER32);
  52
  53     encode_config.winsize = Constants::WINDOW_SIZE;
  54
  55     // TODO! the smatcher setup isn't working,
  56   //   if (options.large_cksum_step) {
  57   //     encode_config.smatch_cfg = XD3_SMATCH_SOFT;
  58   //     encode_config.smatcher_soft.large_step = options.large_cksum_step;
  59   //   }
  60   //   if (options.large_cksum_size) {
  61   //     encode_config.smatch_cfg = XD3_SMATCH_SOFT;
  62   //     encode_config.smatcher_soft.large_look = options.large_cksum_size;
  63   //   }
  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::READ_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[%"Q"u] target %"Q"u[%lu] winsize %lu\n",
  96                   source_file.Size(), options.block_size,
  97                   target_file.Size(), Constants::READ_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: %llu..%llu %"Q"u(%"Q"u) verified %"Q"u\n",
 106                    encoding ? "encoding" : "decoding",
 107                    target_iterator.Offset(),
 108                    target_iterator.Offset() + target_block.Size(),
 109                    target_iterator.Blkno(), blks, verified_bytes));
 110
 111       if (blks == 0 || target_iterator.Blkno() == (blks - 1)) {
 112         xd3_set_flags(&encode_stream, XD3_FLUSH | encode_stream.flags);
 113       }
 114
 115       xd3_avail_input(&encode_stream, target_block.Data(), target_block.Size());
 116       encoded_bytes += target_block.Size();
 117
 118     process:
 119       int ret;
 120       const char *msg;
 121       if (encoding) {
 122         ret = xd3_encode_input(&encode_stream);
 123         msg = encode_stream.msg;
 124       } else {
 125         ret = xd3_decode_input(&decode_stream);
 126         msg = decode_stream.msg;
 127       }
 128       (void) msg;
 129
 130       switch (ret) {
 131       case XD3_OUTPUT:
 132         if (encoding) {
 133           if (coded_data != NULL) {
 134             // Optional encoded-output to the caller
 135             coded_data->Append(encode_stream.next_out,
 136                                encode_stream.avail_out);
 137           }
 138           // Feed this data to the decoder.
 139           xd3_avail_input(&decode_stream,
 140                           encode_stream.next_out,
 141                           encode_stream.avail_out);
 142           xd3_consume_output(&encode_stream);
 143           encoding = false;
 144         } else {
 145           decoded_block.Append(decode_stream.next_out,
 146                                decode_stream.avail_out);
 147           xd3_consume_output(&decode_stream);
 148         }
 149         goto process;
 150
 151       case XD3_GETSRCBLK: {
 152         xd3_source *src = (encoding ? &encode_source : &decode_source);
 153         Block *block = (encoding ? &encode_source_block : &decode_source_block);
 154         if (encoding) {
 155           IF_DEBUG1(XPR(NTR "[srcblock] %"Q"u last srcpos %"Q"u "
 156                        "encodepos %"Q"u\n",
 157                        encode_source.getblkno,
 158                        encode_stream.match_last_srcpos,
 159                        encode_stream.input_position + encode_stream.total_in));
 160         }
 161
 162         source_iterator.SetBlock(src->getblkno);
 163         source_iterator.Get(block);
 164         src->curblkno = src->getblkno;
 165         src->onblk = block->Size();
 166         src->curblk = block->Data();
 167
 168         goto process;
 169       }
 170
 171       case XD3_INPUT:
 172         if (!encoding) {
 173           encoding = true;
 174           goto process;
 175         } else {
 176           if (done_after_input) {
 177             done = true;
 178             continue;
 179           }
 180
 181           if (target_block.Size() < target_iterator.BlockSize()) {
 182             encoding = false;
 183           } else {
 184             target_iterator.Next();
 185           }
 186           continue;
 187         }
 188
 189       case XD3_WINFINISH:
 190         if (encoding) {
 191           if (encode_stream.flags & XD3_FLUSH) {
 192             done_after_input = true;
 193           }
 194           encoding = false;
 195         } else {
 196          CHECK_EQ(0, CmpDifferentBlockBytesAtOffset(decoded_block,
 197                                                     target_file,
 198                                                     verified_bytes));
 199          verified_bytes += decoded_block.Size();
 200          decoded_block.Reset();
 201          encoding = true;
 202        }
 203        goto process;
 204
 205      case XD3_WINSTART:
 206      case XD3_GOTHEADER:
 207        goto process;
 208
 209      default:
 210        XPR(NTR "%s = %s %s\n", encoding ? "E " : " D",
 211            xd3_strerror(ret),
 212            msg == NULL ? "" : msg);
 213
 214        CHECK_EQ(0, ret);
 215        CHECK_EQ(-1, ret);
 216      }
 217    }
 218
 219    CHECK_EQ(target_file.Size(), encoded_bytes);
 220    CHECK_EQ(target_file.Size(), verified_bytes);
 221    CHECK_EQ(0, xd3_close_stream(&decode_stream));
 222    CHECK_EQ(0, xd3_close_stream(&encode_stream));
 223    xd3_free_stream(&encode_stream);
 224    xd3_free_stream(&decode_stream);
 225  }
 226
 227   void MainEncodeDecode(const TmpFile &source_file,
 228                         const TmpFile &target_file,
 229                         ExtFile *coded_data,
 230                         const Options &options) {
 231     vector<const char*> ecmd;
 232     char buf[16];
 233     snprintf(buf, sizeof(buf), "-B%"Q"u", options.encode_srcwin_maxsz);
 234     ecmd.push_back("xdelta3");
 235     ecmd.push_back(buf);
 236     ecmd.push_back("-s");
 237     ecmd.push_back(source_file.Name());
 238     ecmd.push_back(target_file.Name());
 239     ecmd.push_back(coded_data->Name());
 240     ecmd.push_back(NULL);
 241
 242     CHECK_EQ(0, xd3_main_cmdline(ecmd.size() - 1,
 243                                  const_cast<char**>(&ecmd[0])));
 244
 245     vector<const char*> dcmd;
 246     ExtFile recon_file;
 247     dcmd.push_back("xdelta3");
 248     ecmd.push_back(buf);
 249     dcmd.push_back("-d");
 250     dcmd.push_back("-s");
 251     dcmd.push_back(source_file.Name());
 252     dcmd.push_back(coded_data->Name());
 253     dcmd.push_back(recon_file.Name());
 254     dcmd.push_back(NULL);
 255
 256     CHECK_EQ(0, xd3_main_cmdline(dcmd.size() - 1,
 257                                  const_cast<char**>(&dcmd[0])));
 258
 259     CHECK_EQ(0, test_compare_files(recon_file.Name(),
 260                                    target_file.Name()));
 261   }
 262
 263  //////////////////////////////////////////////////////////////////////
 264
 265  void TestRandomNumbers() {
 266    MTRandom rand;
 267    int rounds = 1<<20;
 268    uint64_t usum = 0;
 269    uint64_t esum = 0;
 270
 271    for (int i = 0; i < rounds; i++) {
 272      usum += rand.Rand32();
 273      esum += rand.ExpRand32(1024);
 274    }
 275
 276    double allowed_error = 0.01;
 277
 278    uint32_t umean = usum / rounds;
 279    uint32_t emean = esum / rounds;
 280
 281    uint32_t uexpect = UINT32_MAX / 2;
 282    uint32_t eexpect = 1024;
 283
 284    if (umean < uexpect * (1.0 - allowed_error) ||
 285       umean > uexpect * (1.0 + allowed_error)) {
 286     XPR(NT "uniform mean error: %u != %u\n", umean, uexpect);
 287     abort();
 288   }
 289
 290   if (emean < eexpect * (1.0 - allowed_error) ||
 291       emean > eexpect * (1.0 + allowed_error)) {
 292     XPR(NT "exponential mean error: %u != %u\n", emean, eexpect);
 293     abort();
 294   }
 295 }
 296
 297 void TestRandomFile() {
 298   MTRandom rand1;
 299   FileSpec spec1(&rand1);
 300   BlockIterator bi(spec1);
 301
 302   spec1.GenerateFixedSize(0);
 303   CHECK_EQ(0, spec1.Size());
 304   CHECK_EQ(0, spec1.Segments());
 305   CHECK_EQ(0, spec1.Blocks());
 306   bi.SetBlock(0);
 307   CHECK_EQ(0, bi.BytesOnBlock());
 308
 309   spec1.GenerateFixedSize(1);
 310   CHECK_EQ(1, spec1.Size());
 311   CHECK_EQ(1, spec1.Segments());
 312   CHECK_EQ(1, spec1.Blocks());
 313   bi.SetBlock(0);
 314   CHECK_EQ(1, bi.BytesOnBlock());
 315
 316   spec1.GenerateFixedSize(Constants::BLOCK_SIZE);
 317   CHECK_EQ(Constants::BLOCK_SIZE, spec1.Size());
 318   CHECK_EQ(1, spec1.Segments());
 319   CHECK_EQ(1, spec1.Blocks());
 320   bi.SetBlock(0);
 321   CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
 322   bi.SetBlock(1);
 323   CHECK_EQ(0, bi.BytesOnBlock());
 324
 325   spec1.GenerateFixedSize(Constants::BLOCK_SIZE + 1);
 326   CHECK_EQ(Constants::BLOCK_SIZE + 1, spec1.Size());
 327   CHECK_EQ(2, spec1.Segments());
 328   CHECK_EQ(2, spec1.Blocks());
 329   bi.SetBlock(0);
 330   CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
 331   bi.SetBlock(1);
 332   CHECK_EQ(1, bi.BytesOnBlock());
 333
 334   spec1.GenerateFixedSize(Constants::BLOCK_SIZE * 2);
 335   CHECK_EQ(Constants::BLOCK_SIZE * 2, spec1.Size());
 336   CHECK_EQ(2, spec1.Segments());
 337   CHECK_EQ(2, spec1.Blocks());
 338   bi.SetBlock(0);
 339   CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
 340   bi.SetBlock(1);
 341   CHECK_EQ(Constants::BLOCK_SIZE, bi.BytesOnBlock());
 342 }
 343
 344 void TestFirstByte() {
 345   MTRandom rand;
 346   FileSpec spec0(&rand);
 347   FileSpec spec1(&rand);
 348
 349   spec0.GenerateFixedSize(0);
 350   spec1.GenerateFixedSize(1);
 351   CHECK_EQ(0, CmpDifferentBytes(spec0, spec0));
 352   CHECK_EQ(0, CmpDifferentBytes(spec1, spec1));
 353   CHECK_EQ(1, CmpDifferentBytes(spec0, spec1));
 354   CHECK_EQ(1, CmpDifferentBytes(spec1, spec0));
 355
 356   spec0.GenerateFixedSize(1);
 357   spec0.ModifyTo(Modify1stByte(), &spec1);
 358   CHECK_EQ(1, CmpDifferentBytes(spec0, spec1));
 359
 360   spec0.GenerateFixedSize(Constants::BLOCK_SIZE + 1);
 361   spec0.ModifyTo(Modify1stByte(), &spec1);
 362   CHECK_EQ(1, CmpDifferentBytes(spec0, spec1));
 363
 364   SizeIterator<size_t, Sizes> si(&rand, Constants::TEST_ROUNDS);
 365
 366   for (; !si.Done(); si.Next()) {
 367     size_t size = si.Get();
 368     if (size == 0) {
 369       continue;
 370     }
 371     spec0.GenerateFixedSize(size);
 372     spec0.ModifyTo(Modify1stByte(), &spec1);
 373     InMemoryEncodeDecode(spec0, spec1, NULL);
 374   }
 375 }
 376
 377 void TestModifyMutator() {
 378   MTRandom rand;
 379   FileSpec spec0(&rand);
 380   FileSpec spec1(&rand);
 381
 382   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
 383
 384   struct {
 385     size_t size;
 386     size_t addr;
 387   } test_cases[] = {
 388     { Constants::BLOCK_SIZE, 0 },
 389     { Constants::BLOCK_SIZE / 2, 1 },
 390     { Constants::BLOCK_SIZE, 1 },
 391     { Constants::BLOCK_SIZE * 2, 1 },
 392   };
 393
 394   for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
 395     ChangeList cl1;
 396     cl1.push_back(Change(Change::MODIFY, test_cases[i].size,
 397                          test_cases[i].addr));
 398     spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 399     CHECK_EQ(spec0.Size(), spec1.Size());
 400
 401     size_t diff = CmpDifferentBytes(spec0, spec1);
 402     CHECK_LE(diff, test_cases[i].size);
 403
 404     // There is a 1/256 probability of the changed byte matching the
 405     // original value.  The following allows double the probability to
 406     // pass.
 407     CHECK_GE(diff, test_cases[i].size - (2 * test_cases[i].size / 256));
 408
 409     InMemoryEncodeDecode(spec0, spec1, NULL);
 410   }
 411 }
 412
 413 void TestAddMutator() {
 414   MTRandom rand;
 415   FileSpec spec0(&rand);
 416   FileSpec spec1(&rand);
 417
 418   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 2);
 419   // TODO: fix this test (for all block sizes)!  it's broken because
 420   // the same byte could be added?
 421
 422   struct {
 423     size_t size;
 424     size_t addr;
 425     size_t expected_adds;
 426   } test_cases[] = {
 427     { 1, 0,                         2 /* 1st byte, last byte (short block) */ },
 428     { 1, 1,                         3 /* 1st 2 bytes, last byte */ },
 429     { 1, Constants::BLOCK_SIZE - 1, 2 /* changed, last */ },
 430     { 1, Constants::BLOCK_SIZE,     2 /* changed, last */ },
 431     { 1, Constants::BLOCK_SIZE + 1, 3 /* changed + 1st of 2nd block, last */ },
 432     { 1, 2 * Constants::BLOCK_SIZE, 1 /* last byte */ },
 433   };
 434
 435   for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
 436     ChangeList cl1;
 437     cl1.push_back(Change(Change::ADD, test_cases[i].size, test_cases[i].addr));
 438     spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 439     CHECK_EQ(spec0.Size() + test_cases[i].size, spec1.Size());
 440
 441     Block coded;
 442     InMemoryEncodeDecode(spec0, spec1, &coded);
 443
 444     Delta delta(coded);
 445     CHECK_EQ(test_cases[i].expected_adds,
 446              delta.AddedBytes());
 447   }
 448 }
 449
 450 void TestDeleteMutator() {
 451   MTRandom rand;
 452   FileSpec spec0(&rand);
 453   FileSpec spec1(&rand);
 454
 455   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 4);
 456
 457   struct {
 458     size_t size;
 459     size_t addr;
 460   } test_cases[] = {
 461     // Note: an entry { Constants::BLOCK_SIZE, 0 },
 462     // does not work because the xd3_srcwin_move_point logic won't
 463     // find a copy if it occurs >= double its size into the file.
 464     { Constants::BLOCK_SIZE / 2, 0 },
 465     { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2 },
 466     { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE / 2 },
 467     { Constants::BLOCK_SIZE * 2, Constants::BLOCK_SIZE * 3 / 2 },
 468     { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE * 2 },
 469   };
 470
 471   for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
 472     ChangeList cl1;
 473     cl1.push_back(Change(Change::DELETE, test_cases[i].size,
 474                          test_cases[i].addr));
 475     spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 476     CHECK_EQ(spec0.Size() - test_cases[i].size, spec1.Size());
 477
 478     Block coded;
 479     InMemoryEncodeDecode(spec0, spec1, &coded);
 480
 481     Delta delta(coded);
 482     CHECK_EQ(0, delta.AddedBytes());
 483   }
 484 }
 485
 486 void TestCopyMutator() {
 487   MTRandom rand;
 488   FileSpec spec0(&rand);
 489   FileSpec spec1(&rand);
 490
 491   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
 492
 493   struct {
 494     size_t size;
 495     size_t from;
 496     size_t to;
 497   } test_cases[] = {
 498     // Copy is difficult to write tests for because where Xdelta finds
 499     // copies, it does not enter checksums.  So these tests copy data from
 500     // later to earlier so that checksumming will start.
 501     { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2, 0 },
 502     { Constants::BLOCK_SIZE, 2 * Constants::BLOCK_SIZE,
 503       Constants::BLOCK_SIZE, },
 504   };
 505
 506   for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
 507     ChangeList cl1;
 508     cl1.push_back(Change(Change::COPY, test_cases[i].size,
 509                          test_cases[i].from, test_cases[i].to));
 510     spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 511     CHECK_EQ(spec0.Size() + test_cases[i].size, spec1.Size());
 512
 513     Block coded;
 514     InMemoryEncodeDecode(spec0, spec1, &coded);
 515
 516     Delta delta(coded);
 517     CHECK_EQ(0, delta.AddedBytes());
 518   }
 519 }
 520
 521 void TestMoveMutator() {
 522   MTRandom rand;
 523   FileSpec spec0(&rand);
 524   FileSpec spec1(&rand);
 525
 526   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
 527
 528   struct {
 529     size_t size;
 530     size_t from;
 531     size_t to;
 532   } test_cases[] = {
 533     // This is easier to test than Copy but has the same trouble as Delete.
 534     { Constants::BLOCK_SIZE / 2, Constants::BLOCK_SIZE / 2, 0 },
 535     { Constants::BLOCK_SIZE / 2, 0, Constants::BLOCK_SIZE / 2 },
 536     { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE, 2 *
 537       Constants::BLOCK_SIZE },
 538     { Constants::BLOCK_SIZE, 2 * Constants::BLOCK_SIZE,
 539       Constants::BLOCK_SIZE },
 540     { Constants::BLOCK_SIZE * 3 / 2, Constants::BLOCK_SIZE,
 541       Constants::BLOCK_SIZE * 3 / 2 },
 542
 543     // This is a no-op
 544     { Constants::BLOCK_SIZE, Constants::BLOCK_SIZE * 2,
 545       3 * Constants::BLOCK_SIZE },
 546   };
 547
 548   for (size_t i = 0; i < SIZEOF_ARRAY(test_cases); i++) {
 549     ChangeList cl1;
 550     cl1.push_back(Change(Change::MOVE, test_cases[i].size,
 551                          test_cases[i].from, test_cases[i].to));
 552     spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 553     CHECK_EQ(spec0.Size(), spec1.Size());
 554
 555     Block coded;
 556     InMemoryEncodeDecode(spec0, spec1, &coded);
 557
 558     Delta delta(coded);
 559     CHECK_EQ(0, delta.AddedBytes());
 560   }
 561 }
 562
 563 void TestOverwriteMutator() {
 564   MTRandom rand;
 565   FileSpec spec0(&rand);
 566   FileSpec spec1(&rand);
 567
 568   spec0.GenerateFixedSize(Constants::BLOCK_SIZE);
 569
 570   ChangeList cl1;
 571   cl1.push_back(Change(Change::COPYOVER, 10, 0, 20));
 572   spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 573   CHECK_EQ(spec0.Size(), spec1.Size());
 574
 575   Block b0, b1;
 576   BlockIterator(spec0).Get(&b0);
 577   BlockIterator(spec1).Get(&b1);
 578
 579   CHECK(memcmp(b0.Data(), b1.Data() + 20, 10) == 0);
 580   CHECK(memcmp(b0.Data(), b1.Data(), 20) == 0);
 581   CHECK(memcmp(b0.Data() + 30, b1.Data() + 30,
 582                Constants::BLOCK_SIZE - 30) == 0);
 583
 584   cl1.clear();
 585   cl1.push_back(Change(Change::COPYOVER, 10, 20, (xoff_t)0));
 586   spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 587   CHECK_EQ(spec0.Size(), spec1.Size());
 588
 589   BlockIterator(spec0).Get(&b0);
 590   BlockIterator(spec1).Get(&b1);
 591
 592   CHECK(memcmp(b0.Data() + 20, b1.Data(), 10) == 0);
 593   CHECK(memcmp(b0.Data() + 10, b1.Data() + 10,
 594                Constants::BLOCK_SIZE - 10) == 0);
 595 }
 596
 597 // Note: this test is written to expose a problem, but the problem was
 598 // only exposed with BLOCK_SIZE = 128.
 599 void TestNonBlockingProgress() {
 600   MTRandom rand;
 601   FileSpec spec0(&rand);
 602   FileSpec spec1(&rand);
 603   FileSpec spec2(&rand);
 604
 605   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 3);
 606
 607   // This is a lazy target match
 608   Change ct(Change::COPYOVER, 22,
 609             Constants::BLOCK_SIZE + 50,
 610             Constants::BLOCK_SIZE + 20);
 611
 612   // This is a source match just after the block boundary, shorter
 613   // than the lazy target match.
 614   Change cs1(Change::COPYOVER, 16,
 615              Constants::BLOCK_SIZE + 51,
 616              Constants::BLOCK_SIZE - 1);
 617
 618   // This overwrites the original source bytes.
 619   Change cs2(Change::MODIFY, 108,
 620              Constants::BLOCK_SIZE + 20);
 621
 622   // This changes the first blocks
 623   Change c1st(Change::MODIFY, Constants::BLOCK_SIZE - 2, 0);
 624
 625   ChangeList csl;
 626   csl.push_back(cs1);
 627   csl.push_back(cs2);
 628   csl.push_back(c1st);
 629
 630   spec0.ModifyTo(ChangeListMutator(csl), &spec1);
 631
 632   ChangeList ctl;
 633   ctl.push_back(ct);
 634   ctl.push_back(c1st);
 635
 636   spec0.ModifyTo(ChangeListMutator(ctl), &spec2);
 637
 638   InMemoryEncodeDecode(spec1, spec2, NULL);
 639 }
 640
 641 void TestEmptyInMemory() {
 642   MTRandom rand;
 643   FileSpec spec0(&rand);
 644   FileSpec spec1(&rand);
 645   Block block;
 646
 647   spec0.GenerateFixedSize(0);
 648   spec1.GenerateFixedSize(0);
 649
 650   InMemoryEncodeDecode(spec0, spec1, &block);
 651
 652   Delta delta(block);
 653   CHECK_LT(0, block.Size());
 654   CHECK_EQ(1, delta.Windows());
 655 }
 656
 657 void TestBlockInMemory() {
 658   MTRandom rand;
 659   FileSpec spec0(&rand);
 660   FileSpec spec1(&rand);
 661   Block block;
 662
 663   spec0.GenerateFixedSize(Constants::BLOCK_SIZE);
 664   spec1.GenerateFixedSize(Constants::BLOCK_SIZE);
 665
 666   InMemoryEncodeDecode(spec0, spec1, &block);
 667
 668   Delta delta(block);
 669   CHECK_EQ(spec1.Blocks(Constants::WINDOW_SIZE), delta.Windows());
 670 }
 671
 672 void TestHalfBlockCopy() {
 673   MTRandom rand;
 674   FileSpec spec0(&rand);
 675   FileSpec spec1(&rand);
 676
 677   spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 4);
 678
 679   // Create a half-block copy, 2.5 blocks apart, from the second half
 680   // of the source version to the first half of the target version.
 681   //       0             1             2             3
 682   // spec0 [bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb][ccccc][bbbbb]
 683   // spec1 [aaaaa][ccccc][aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa]
 684   ChangeList cl1;
 685   cl1.push_back(Change(Change::MODIFY,
 686                        Constants::BLOCK_SIZE / 2,  // size
 687                        0));
 688   cl1.push_back(Change(Change::COPYOVER,
 689                        Constants::BLOCK_SIZE / 2,  // size
 690                        Constants::BLOCK_SIZE * 3,  // offset
 691                        Constants::BLOCK_SIZE / 2));
 692   cl1.push_back(Change(Change::MODIFY,
 693                        Constants::BLOCK_SIZE * 3,
 694                        Constants::BLOCK_SIZE));
 695   spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 696
 697   const int onecopy_adds =
 698     4 * Constants::BLOCK_SIZE - Constants::BLOCK_SIZE / 2;
 699   const int nocopy_adds = 4 * Constants::BLOCK_SIZE;
 700
 701   // Note the case b=4 is contrived: the caller should use a single block
 702   // containing the entire source, if possible.
 703   for (int b = 1; b <= 4; b++)
 704     {
 705       Options options;
 706       options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * b;
 707
 708       Block block0;
 709       Block block1;
 710       InMemoryEncodeDecode(spec0, spec1, &block0, options);
 711       InMemoryEncodeDecode(spec1, spec0, &block1, options);
 712       Delta delta0(block0);
 713       Delta delta1(block1);
 714
 715       // The first block never copies from the last source block, by
 716       // design, because if the last source block is available when
 717       // the first target block is ready, the caller is expected to
 718       // use a single block.
 719       CHECK_EQ(nocopy_adds, delta0.AddedBytes());
 720       if (Constants::BLOCK_SIZE < 8192 || b > 2)
 721         {
 722           // For small-block inputs, the entire file is read into one
 723           // block (the min source window size is 16kB).
 724           //
 725           // For large blocks, at least 3 blocks of source window are
 726           // needed.
 727           CHECK_EQ(onecopy_adds, delta1.AddedBytes());
 728         }
 729       else
 730         {
 731           // When there are fewer than 3 source blocks.
 732           CHECK_EQ(nocopy_adds, delta1.AddedBytes());
 733         }
 734       // XPR(NT "0=%zu 1=%zu\n", delta0.AddedBytes(), delta1.AddedBytes());
 735     }
 736
 737   Options options;
 738   options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * 4;
 739   options.block_size = Constants::BLOCK_SIZE * 4;
 740
 741   // Test the whole-buffer case.
 742   Block block0;
 743   Block block1;
 744   InMemoryEncodeDecode(spec0, spec1, &block0, options);
 745   InMemoryEncodeDecode(spec1, spec0, &block1, options);
 746   Delta delta0(block0);
 747   Delta delta1(block1);
 748   // This <= >= are only for blocksize = 512, which has irregular readsize.
 749   CHECK_LE(onecopy_adds, delta0.AddedBytes());
 750   CHECK_GE(onecopy_adds + 1, delta0.AddedBytes());
 751
 752   CHECK_EQ(onecopy_adds, delta1.AddedBytes());
 753   // XPR(NT "0=%zu 1=%zu\n", delta0.AddedBytes(), delta1.AddedBytes());
 754 }
 755
 756 void FourWayMergeTest(const FileSpec &spec0,
 757                       const FileSpec &spec1,
 758                       const FileSpec &spec2,
 759                       const FileSpec &spec3) {
 760   TmpFile f0, f1, f2, f3;
 761   ExtFile d01, d12, d23;
 762   Options options;
 763   options.encode_srcwin_maxsz =
 764     std::max(spec0.Size(), options.encode_srcwin_maxsz);
 765
 766   spec0.WriteTmpFile(&f0);
 767   spec1.WriteTmpFile(&f1);
 768   spec2.WriteTmpFile(&f2);
 769   spec3.WriteTmpFile(&f3);
 770
 771   MainEncodeDecode(f0, f1, &d01, options);
 772   MainEncodeDecode(f1, f2, &d12, options);
 773   MainEncodeDecode(f2, f3, &d23, options);
 774
 775   // Merge 2
 776   ExtFile out;
 777   vector<const char*> mcmd;
 778   mcmd.push_back("xdelta3");
 779   mcmd.push_back("merge");
 780   mcmd.push_back("-m");
 781   mcmd.push_back(d01.Name());
 782   mcmd.push_back(d12.Name());
 783   mcmd.push_back(out.Name());
 784   mcmd.push_back(NULL);
 785
 786   // XPR(NTR "Running one merge: %s\n", CommandToString(mcmd).c_str());
 787   CHECK_EQ(0, xd3_main_cmdline(mcmd.size() - 1,
 788                                const_cast<char**>(&mcmd[0])));
 789
 790   ExtFile recon;
 791   vector<const char*> tcmd;
 792   tcmd.push_back("xdelta3");
 793   tcmd.push_back("-d");
 794   tcmd.push_back("-s");
 795   tcmd.push_back(f0.Name());
 796   tcmd.push_back(out.Name());
 797   tcmd.push_back(recon.Name());
 798   tcmd.push_back(NULL);
 799
 800   // XPR(NTR "Running one recon! %s\n", CommandToString(tcmd).c_str());
 801   CHECK_EQ(0, xd3_main_cmdline(tcmd.size() - 1,
 802                                const_cast<char**>(&tcmd[0])));
 803   // XPR(NTR "Should equal! %s\n", f2.Name());
 804
 805   CHECK(recon.EqualsSpec(spec2));
 806
 807   // Merge 3
 808   ExtFile out3;
 809   vector<const char*> mcmd3;
 810   mcmd3.push_back("xdelta3");
 811   mcmd3.push_back("merge");
 812   mcmd3.push_back("-m");
 813   mcmd3.push_back(d01.Name());
 814   mcmd3.push_back("-m");
 815   mcmd3.push_back(d12.Name());
 816   mcmd3.push_back(d23.Name());
 817   mcmd3.push_back(out3.Name());
 818   mcmd3.push_back(NULL);
 819
 820   // XPR(NTR "Running one 3-merge: %s\n", CommandToString(mcmd3).c_str());
 821   CHECK_EQ(0, xd3_main_cmdline(mcmd3.size() - 1,
 822                                const_cast<char**>(&mcmd3[0])));
 823
 824   ExtFile recon3;
 825   vector<const char*> tcmd3;
 826   tcmd3.push_back("xdelta3");
 827   tcmd3.push_back("-d");
 828   tcmd3.push_back("-s");
 829   tcmd3.push_back(f0.Name());
 830   tcmd3.push_back(out3.Name());
 831   tcmd3.push_back(recon3.Name());
 832   tcmd3.push_back(NULL);
 833
 834   // XPR(NTR "Running one 3-recon %s\n", CommandToString(tcmd3).c_str());
 835   CHECK_EQ(0, xd3_main_cmdline(tcmd3.size() - 1,
 836                                const_cast<char**>(&tcmd3[0])));
 837   // XPR(NTR "Should equal %s\n", f3.Name());
 838
 839   CHECK(recon3.EqualsSpec(spec3));
 840 }
 841
 842 void TestMergeCommand1() {
 843   /* Repeat random-input testing for a number of iterations.
 844    * Test 2, 3, and 4-file scenarios (i.e., 1, 2, and 3-delta merges). */
 845   MTRandom rand;
 846   FileSpec spec0(&rand);
 847   FileSpec spec1(&rand);
 848   FileSpec spec2(&rand);
 849   FileSpec spec3(&rand);
 850
 851   SizeIterator<size_t, Sizes> si0(&rand, 10);
 852
 853   for (; !si0.Done(); si0.Next()) {
 854     size_t size0 = si0.Get();
 855
 856     SizeIterator<size_t, Sizes> si1(&rand, 10);
 857     for (; !si1.Done(); si1.Next()) {
 858       size_t change1 = si1.Get();
 859
 860       if (change1 == 0) {
 861         continue;
 862       }
 863
 864       // XPR(NTR "S0 = %lu\n", size0);
 865       // XPR(NTR "C1 = %lu\n", change1);
 866       // XPR(NTR ".");
 867
 868       size_t add1_pos = size0 ? rand.Rand32() % size0 : 0;
 869       size_t del2_pos = size0 ? rand.Rand32() % size0 : 0;
 870
 871       spec0.GenerateFixedSize(size0);
 872
 873       ChangeList cl1, cl2, cl3;
 874
 875       size_t change3 = change1;
 876       size_t change3_pos;
 877
 878       if (change3 >= size0) {
 879         change3 = size0;
 880         change3_pos = 0;
 881       } else {
 882         change3_pos = rand.Rand32() % (size0 - change3);
 883       }
 884
 885       cl1.push_back(Change(Change::ADD, change1, add1_pos));
 886       cl2.push_back(Change(Change::DELETE, change1, del2_pos));
 887       cl3.push_back(Change(Change::MODIFY, change3, change3_pos));
 888
 889       spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 890       spec1.ModifyTo(ChangeListMutator(cl2), &spec2);
 891       spec2.ModifyTo(ChangeListMutator(cl3), &spec3);
 892
 893       FourWayMergeTest(spec0, spec1, spec2, spec3);
 894       FourWayMergeTest(spec3, spec2, spec1, spec0);
 895     }
 896   }
 897 }
 898
 899 void TestMergeCommand2() {
 900   /* Same as above, different mutation pattern. */
 901   /* TODO: run this with large sizes too */
 902   /* TODO: run this with small sizes too */
 903   MTRandom rand;
 904   FileSpec spec0(&rand);
 905   FileSpec spec1(&rand);
 906   FileSpec spec2(&rand);
 907   FileSpec spec3(&rand);
 908
 909   SizeIterator<size_t, Sizes> si0(&rand, 10);
 910   for (; !si0.Done(); si0.Next()) {
 911     size_t size0 = si0.Get();
 912
 913     SizeIterator<size_t, Sizes> si1(&rand, 10);
 914     for (; !si1.Done(); si1.Next()) {
 915       size_t size1 = si1.Get();
 916
 917       SizeIterator<size_t, Sizes> si2(&rand, 10);
 918       for (; !si2.Done(); si2.Next()) {
 919         size_t size2 = si2.Get();
 920
 921         SizeIterator<size_t, Sizes> si3(&rand, 10);
 922         for (; !si3.Done(); si3.Next()) {
 923           size_t size3 = si3.Get();
 924
 925           // We're only interested in three sizes, strictly decreasing. */
 926           if (size3 >= size2 || size2 >= size1 || size1 >= size0) {
 927             continue;
 928           }
 929
 930           // XPR(NTR "S0 = %lu\n", size0);
 931           // XPR(NTR "S1 = %lu\n", size1);
 932           // XPR(NTR "S2 = %lu\n", size2);
 933           // XPR(NTR "S3 = %lu\n", size3);
 934           // XPR(NTR ".");
 935
 936           spec0.GenerateFixedSize(size0);
 937
 938           ChangeList cl1, cl2, cl3;
 939
 940           cl1.push_back(Change(Change::DELETE, size0 - size1, 0));
 941           cl2.push_back(Change(Change::DELETE, size0 - size2, 0));
 942           cl3.push_back(Change(Change::DELETE, size0 - size3, 0));
 943
 944           spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
 945           spec0.ModifyTo(ChangeListMutator(cl2), &spec2);
 946           spec0.ModifyTo(ChangeListMutator(cl3), &spec3);
 947
 948           FourWayMergeTest(spec0, spec1, spec2, spec3);
 949           FourWayMergeTest(spec3, spec2, spec1, spec0);
 950         }
 951       }
 952     }
 953   }
 954 }
 955
 956 };  // class Regtest<Constants>
 957
 958 #define TEST(x) XPR(NTR #x "...\n"); regtest.x()
 959
 960 // These tests are primarily tests of the testing framework itself.
 961 template <class T>
 962 void UnitTest() {
 963   Regtest<T> regtest;
 964   TEST(TestRandomNumbers);
 965   TEST(TestRandomFile);
 966   TEST(TestFirstByte);
 967   TEST(TestModifyMutator);
 968   TEST(TestAddMutator);
 969   TEST(TestDeleteMutator);
 970   TEST(TestCopyMutator);
 971   TEST(TestMoveMutator);
 972   TEST(TestOverwriteMutator);
 973 }
 974
 975 // These are Xdelta tests.
 976 template <class T>
 977 void MainTest() {
 978   XPR(NT "Blocksize %"Q"u readsize %"Q"u windowsize %"Q"u\n",
 979       T::BLOCK_SIZE, T::READ_SIZE, T::WINDOW_SIZE);
 980   Regtest<T> regtest;
 981   TEST(TestEmptyInMemory);
 982   TEST(TestBlockInMemory);
 983   TEST(TestNonBlockingProgress);
 984   TEST(TestHalfBlockCopy);
 985   TEST(TestMergeCommand1);
 986   TEST(TestMergeCommand2);
 987 }
 988
 989 #undef TEST
 990
 991 int main(int argc, char **argv)
 992 {
 993   vector<const char*> mcmd;
 994   string pn;
 995   const char *sp = strrchr(argv[0], '/');
 996   if (sp != NULL) {
 997     pn.append(argv[0], sp - argv[0] + 1);
 998   }
 999   pn.append("xdelta3");
1000   mcmd.push_back(pn.c_str());
1001   mcmd.push_back("test");
1002   mcmd.push_back(NULL);
1003
1004   UnitTest<SmallBlock>();
1005   MainTest<SmallBlock>();
1006   MainTest<MixedBlock>();
1007   MainTest<PrimeBlock>();
1008   MainTest<OversizeBlock>();
1009   MainTest<LargeBlock>();
1010
1011   CHECK_EQ(0, xd3_main_cmdline(mcmd.size() - 1,
1012                                const_cast<char**>(&mcmd[0])));
1013
1014   return 0;
1015 }