Adds a test for the fix for issue 70. The new regression test

framework's ability to craft specific inputs is very handy.

5 files changed, 123 insertions, 57 deletions

diff --git a/xdelta3/testing/Makefile b/xdelta3/testing/Makefile
index 814f477..df9854d 100755
--- a/xdelta3/testing/Makefile
+++ b/xdelta3/testing/Makefile
@@ -1,5 +1,5 @@
-#CFLAGS = -g -Wall -I.. -DXD3_DEBUG=1 -DNDEBUG=0
-CFLAGS = -g -Wall -I.. -DXD3_DEBUG=2 -DNDEBUG=0
+CFLAGS = -g -Wall -I.. -DXD3_DEBUG=1 -DNDEBUG=0
+#CFLAGS = -g -Wall -I.. -DXD3_DEBUG=2 -DNDEBUG=0
 #CFLAGS = -O2 -Wall -I.. -DXD3_DEBUG=0 -DNDEBUG=1
 
 DEPS = ../*.h ../*.c *.cc *.h
diff --git a/xdelta3/testing/file.h b/xdelta3/testing/file.h
index d38a720..4153e5f 100644
--- a/xdelta3/testing/file.h
+++ b/xdelta3/testing/file.h
@@ -53,6 +53,18 @@ class FileSpec {
                 FileSpec *modify) const {
     modify->Reset();
     mutator.Mutate(&modify->table_, &table_, rand_);
+    modify->CheckSegments();
+  }
+
+  void CheckSegments() const {
+    for (SegmentMap::const_iterator iter(table_.begin());
+         iter != table_.end(); ) {
+      SegmentMap::const_iterator iter0(iter++);
+      if (iter == table_.end()) {
+        break;
+      }
+      CHECK_EQ(iter0->first + iter0->second.Size(), iter->first);
+    }
   }
 
   void Reset() {
diff --git a/xdelta3/testing/modify.h b/xdelta3/testing/modify.h
index 8b81baf..67cccd9 100644
--- a/xdelta3/testing/modify.h
+++ b/xdelta3/testing/modify.h
@@ -17,6 +17,7 @@ public:
     DELETE = 3,
     MOVE = 4,
     COPY = 5,
+    OVERWRITE = 6,
   };
 
   // Constructor for modify, add, delete.
@@ -25,7 +26,7 @@ public:
       size(size),
       addr1(addr1),
     insert(NULL) { 
-    CHECK(kind != MOVE && kind != COPY);
+    CHECK(kind != MOVE && kind != COPY && kind != OVERWRITE);
   }
 
   // Constructor for modify, add w/ provided data.
@@ -34,7 +35,7 @@ public:
       size(size),
       addr1(addr1),
       insert(insert) { 
-    CHECK(kind != MOVE && kind != COPY);
+    CHECK(kind != MOVE && kind != COPY && kind != OVERWRITE);
   }
 
   // Constructor for move
@@ -44,7 +45,7 @@ public:
       addr1(addr1),
       addr2(addr2),
       insert(NULL) { 
-    CHECK(kind == MOVE || kind == COPY);
+    CHECK(kind == MOVE || kind == COPY || kind == OVERWRITE);
   }
 
   Kind kind;
@@ -92,6 +93,11 @@ public:
                          const SegmentMap *source_table,
                          MTRandom *rand);
 
+  static void OverwriteChange(const Change &ch, 
+                              SegmentMap *table,
+                              const SegmentMap *source_table,
+                              MTRandom *rand);
+
   static void CopyChange(const Change &ch, 
                          SegmentMap *table,
                          const SegmentMap *source_table,
@@ -124,6 +130,7 @@ void ChangeListMutator::Mutate(SegmentMap *table,
 
   for (ChangeList::const_iterator iter(cl_.begin()); iter != cl_.end(); ++iter) {
     const Change &ch = *iter;
+    tmp.clear();
     Mutate(ch, &tmp, source_table, rand);
     tmp.swap(*table);
     source_table = table;
@@ -150,6 +157,9 @@ void ChangeListMutator::Mutate(const Change &ch,
   case Change::MOVE:
     MoveChange(ch, table, source_table, rand);
     break;
+  case Change::OVERWRITE:
+    OverwriteChange(ch, table, source_table, rand);
+    break;
   }
 }
 
@@ -311,6 +321,17 @@ void ChangeListMutator::MoveChange(const Change &ch,
   DeleteChange(d, table, &tmp, rand);
 }
 
+void ChangeListMutator::OverwriteChange(const Change &ch, 
+                                   SegmentMap *table,
+                                   const SegmentMap *source_table,
+                                   MTRandom *rand) {
+  SegmentMap tmp;
+  CHECK_NE(ch.addr1, ch.addr2);
+  CopyChange(ch, &tmp, source_table, rand);
+  Change d(Change::DELETE, ch.size, ch.addr2 + ch.size);
+  DeleteChange(d, table, &tmp, rand);
+}
+
 void ChangeListMutator::CopyChange(const Change &ch, 
                                    SegmentMap *table,
                                    const SegmentMap *source_table,
diff --git a/xdelta3/testing/regtest.cc b/xdelta3/testing/regtest.cc
index fe4983b..d615196 100644
--- a/xdelta3/testing/regtest.cc
+++ b/xdelta3/testing/regtest.cc
@@ -29,6 +29,7 @@ struct TestOptions {
   size_t large_cksum_size;
 };
 
+// TODO! the smatcher setup isn't working, 
 void InMemoryEncodeDecode(const TestOptions &options,
                           FileSpec &source_file, 
                           FileSpec &target_file, 
@@ -173,7 +174,9 @@ void InMemoryEncodeDecode(const TestOptions &options,
     }
   }
 
-  xd3_close_stream(&encode_stream);
+  CHECK_EQ(0, xd3_close_stream(&decode_stream));
+  CHECK_EQ(0, xd3_close_stream(&encode_stream));
+  xd3_free_stream(&encode_stream);
   xd3_free_stream(&decode_stream);
 }
 
@@ -477,6 +480,7 @@ void TestMoveMutator() {
 }
 
 void FindCksumCollision() {
+  // TODO! This is not being used.
   if (golden_cksum_bytes[0] != 0) {
     CHECK(memcmp(golden_cksum_bytes, collision_cksum_bytes, CKSUM_SIZE) != 0);
     CHECK_EQ(xd3_lcksum(golden_cksum_bytes, CKSUM_SIZE),
@@ -516,56 +520,80 @@ void FindCksumCollision() {
   b2.Print();
 }
 
-void TestNonBlockingCollisionProgress() {
+void TestOverwriteMutator() {
   MTRandom rand;
   FileSpec spec0(&rand);
   FileSpec spec1(&rand);
-  FileSpec spec2(&rand);
   TestOptions options;
 
-  FindCksumCollision();
+  spec0.GenerateFixedSize(Constants::BLOCK_SIZE);
 
-  spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 2);
+  ChangeList cl1;
+  cl1.push_back(Change(Change::OVERWRITE, 10, 0, 20));
+  spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
+  CHECK_EQ(spec0.Size(), spec1.Size());
 
-  Segment gcksum(CKSUM_SIZE, golden_cksum_bytes);
-  Segment ccksum(CKSUM_SIZE, collision_cksum_bytes);
+  Block b0, b1;
+  BlockIterator(spec0).Get(&b0);
+  BlockIterator(spec1).Get(&b1);
+  
+  CHECK(memcmp(b0.Data(), b1.Data() + 20, 10) == 0);
+  CHECK(memcmp(b0.Data(), b1.Data(), 20) == 0);
+  CHECK(memcmp(b0.Data() + 30, b1.Data() + 30, Constants::BLOCK_SIZE - 30) == 0);
 
-  uint32_t v1 = xd3_lcksum(golden_cksum_bytes, CKSUM_SIZE);
-  uint32_t v2 = xd3_lcksum(collision_cksum_bytes, CKSUM_SIZE);
-  CHECK_EQ(v1, v2);
+  cl1.clear();
+  cl1.push_back(Change(Change::OVERWRITE, 10, 20, (xoff_t)0));
+  spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
+  CHECK_EQ(spec0.Size(), spec1.Size());
 
-  // TODO! the smatcher setup isn't working, the default is 9/3
+  BlockIterator(spec0).Get(&b0);
+  BlockIterator(spec1).Get(&b1);
+  
+  CHECK(memcmp(b0.Data() + 20, b1.Data(), 10) == 0);
+  CHECK(memcmp(b0.Data() + 10, b1.Data() + 10, Constants::BLOCK_SIZE - 10) == 0);
+}
 
-  // Place the collision just before the 1st block end, place the
-  // matching bytes at the start of the next block.  Note that
-  // source checksums are computed in reverse from the end of the
-  // block, so placing the collision at the end of the block works.
+void TestNonBlockingProgress() {
+  MTRandom rand;
+  FileSpec spec0(&rand);
+  FileSpec spec1(&rand);
+  FileSpec spec2(&rand);
+  TestOptions options;
 
-  xoff_t false_offset = Constants::BLOCK_SIZE - CKSUM_SIZE;
-  xoff_t modify_offset = Constants::BLOCK_SIZE + 20;
+  // TODO! this test assumes block_size == 128
 
-  // Fixed content for a backward match prior to the collision, which
-  // makes the total match length long enough for the min_match.
-  Segment preamble(20, 0xabcd);
+  spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 2);
 
-  Change c1(Change::MODIFY, CKSUM_SIZE, false_offset, &gcksum);
-  Change c2(Change::MODIFY, CKSUM_SIZE, modify_offset, &ccksum);
+  // This is a lazy target match
+  Change ct(Change::OVERWRITE, 22, 
+            Constants::BLOCK_SIZE + 50,
+            Constants::BLOCK_SIZE + 20);
 
-  Change cp1(Change::MODIFY, 20, false_offset - 20, &preamble);
-  Change cp2(Change::MODIFY, 20, modify_offset - 20, &preamble);
+  // This is a source match just after the block boundary, shorter
+  // than the lazy target match.
+  Change cs1(Change::OVERWRITE, 16,
+             Constants::BLOCK_SIZE + 51,
+             Constants::BLOCK_SIZE - 1);
 
-  ChangeList cl1;
-  ChangeList cl2;
-  cl1.push_back(c1);
-  cl1.push_back(cp1);
-  cl2.push_back(c2);
-  cl2.push_back(cp2);
+  // This overwrites the original source bytes.
+  Change cs2(Change::MODIFY, 108,
+             Constants::BLOCK_SIZE + 20);
 
-  spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
-  spec0.ModifyTo(ChangeListMutator(cl2), &spec2);
+  // This changes the first blocks
+  Change c1st(Change::MODIFY, Constants::BLOCK_SIZE - 2, 0);
+
+  ChangeList csl;
+  csl.push_back(cs1);
+  csl.push_back(cs2);
+  csl.push_back(c1st);
+
+  spec0.ModifyTo(ChangeListMutator(csl), &spec1);
+
+  ChangeList ctl;
+  ctl.push_back(ct);
+  ctl.push_back(c1st);
 
-  spec1.Print();
-  spec2.Print();
+  spec0.ModifyTo(ChangeListMutator(ctl), &spec2);
 
   InMemoryEncodeDecode(options, spec1, spec2, NULL);
 }
@@ -574,15 +602,16 @@ void TestNonBlockingCollisionProgress() {
 
 int main(int argc, char **argv) {
 #define TEST(x) cerr << #x << "..." << endl; x()
-//   TEST(TestRandomNumbers);
-//   TEST(TestRandomFile);
-//   TEST(TestFirstByte);
-//   TEST(TestModifyMutator);
-//   TEST(TestAddMutator);
-//   TEST(TestDeleteMutator);
-//   TEST(TestCopyMutator);
-//   TEST(TestMoveMutator);
-  TEST(TestNonBlockingCollisionProgress);
+  TEST(TestRandomNumbers);
+  TEST(TestRandomFile);
+  TEST(TestFirstByte);
+  TEST(TestModifyMutator);
+  TEST(TestAddMutator);
+  TEST(TestDeleteMutator);
+  TEST(TestCopyMutator);
+  TEST(TestMoveMutator);
+  TEST(TestOverwriteMutator);
+  TEST(TestNonBlockingProgress);
   return 0;
 }
 
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index c2061a0..bdf02af 100644
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -2103,7 +2103,7 @@ xd3_alloc (xd3_stream *stream,
   if (a != NULL)
     {
       IF_DEBUG (stream->alloc_cnt += 1);
-      IF_DEBUG1 (DP(RINT "[stream %p malloc] size %u ptr %p\n", 
+      IF_DEBUG2 (DP(RINT "[stream %p malloc] size %u ptr %p\n", 
                     stream, elts * size, a));
     }
   else
@@ -2122,7 +2122,7 @@ xd3_free (xd3_stream *stream,
     {
       IF_DEBUG (stream->free_cnt += 1);
       XD3_ASSERT (stream->free_cnt <= stream->alloc_cnt);
-      IF_DEBUG1 (DP(RINT "[stream %p free] %p\n", 
+      IF_DEBUG2 (DP(RINT "[stream %p free] %p\n", 
                     stream, ptr));
       stream->free (stream->opaque, ptr);
     }
@@ -3228,7 +3228,7 @@ xd3_emit_single (xd3_stream *stream, xd3_rinst *single, usize_t code)
 
   IF_DEBUG1 (DP(RINT "[emit1] %u %s (%u) code %u\n",
                single->pos,
-               xd3_rtype_to_string (single->type, 0),
+                xd3_rtype_to_string ((xd3_rtype) single->type, 0),
                single->size,
                code));
 
@@ -3266,9 +3266,9 @@ xd3_emit_double (xd3_stream *stream, xd3_rinst *first,
 
   IF_DEBUG1 (DP(RINT "[emit2]: %u %s (%u) %s (%u) code %u\n",
                first->pos,
-               xd3_rtype_to_string (first->type, 0),
+                xd3_rtype_to_string ((xd3_rtype) first->type, 0),
                first->size,
-               xd3_rtype_to_string (second->type, 0),
+                xd3_rtype_to_string ((xd3_rtype) second->type, 0),
                second->size,
                code));
 
@@ -4329,10 +4329,14 @@ xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos)
   stream->match_back    = 0;
   stream->match_fwd     = 0;
 
-  /* This avoids a loop.  TODO: if ever duplicates are added to the
-   * source hash table, this logic won't suffice to avoid loops. 
-   * TODO: how can you test this in a unittest?  Need to search for
-   * hash collisions, I suppose. */
+  /* This avoids a non-blocking endless loop caused by scanning
+   * backwards across a block boundary, only to find not enough
+   * matching bytes to beat the current min_match due to a better lazy
+   * target match: the re-entry to xd3_string_match() repeats the same
+   * long match because the input position hasn't changed.  TODO: if
+   * ever duplicates are added to the source hash table, this logic
+   * won't suffice to avoid loops.  See testing/regtest.cc's
+   * TestNonBlockingProgress test! */
   if (srcpos != 0 && srcpos == stream->match_last_srcpos)
     {
       goto bad;