Simplifies xd3_srcwin_move_point; reads the full max_winsize before starting to compress (see notes in the corresponding comments); eliminates xd3_stream::frontier_pos; changes as a result, and improvements in testing/regtest.cc; tested on osx-darwin

6 files changed, 171 insertions, 195 deletions

diff --git a/xdelta3/Makefile.am b/xdelta3/Makefile.am
index 6ab3a42..d2f7b31 100644
--- a/xdelta3/Makefile.am
+++ b/xdelta3/Makefile.am
@@ -75,9 +75,9 @@ xdelta3decode_CFLAGS = \
         -DVCDIFF_TOOLS=0
 
 xdelta3regtest_CXXFLAGS = \
-        $(CXX_WFLAGS) $(common_CFLAGS) -DNOT_MAIN=1 -DXD3_DEBUG=2
+        $(CXX_WFLAGS) $(common_CFLAGS) -DNOT_MAIN=1 -DXD3_DEBUG=1
 xdelta3regtest_CFLAGS = \
-        $(C_WFLAGS) $(common_CFLAGS) -DNOT_MAIN=1 -DXD3_DEBUG=2
+        $(C_WFLAGS) $(common_CFLAGS) -DNOT_MAIN=1 -DXD3_DEBUG=1
 xdelta3regtest_LDADD = -lm
 
 man1_MANS = xdelta3.1
diff --git a/xdelta3/testing/regtest.cc b/xdelta3/testing/regtest.cc
index eeb0e4b..23c985e 100644
--- a/xdelta3/testing/regtest.cc
+++ b/xdelta3/testing/regtest.cc
@@ -790,32 +790,34 @@ void TestSmallStride() {
   usize_t size = Constants::BLOCK_SIZE * 4;
   spec0.GenerateFixedSize(size);
 
-  /* TODO Need to study the actual causes of missed adds for tests
-   * less than 30 bytes. */
-  const int s = 30;
-  usize_t adds = 0;
-  ChangeList cl;
-  for (usize_t j = s; j < size; j += s, ++adds)
-    {
-      cl.push_back(Change(Change::MODIFY, 1, j));
-    }
+  // Note: Not very good performance due to hash collisions, note 3x
+  // multiplier below.
+  for (int s = 15; s < 101; s++) {
+    usize_t changes = 0;
+    ChangeList cl;
+    for (usize_t j = s; j < size; j += s, ++changes)
+      {
+        cl.push_back(Change(Change::MODIFY, 1, j));
+      }
 
-  FileSpec spec1(&rand);
-  spec0.ModifyTo(ChangeListMutator(cl), &spec1);
+    FileSpec spec1(&rand);
+    spec0.ModifyTo(ChangeListMutator(cl), &spec1);
 
-  Options options;
-  options.encode_srcwin_maxsz = size;
-  options.iopt_size = 128;
-  options.smatch_cfg = XD3_SMATCH_SLOW;
-  options.size_known = false;
+    Options options;
+    options.encode_srcwin_maxsz = size;
+    options.iopt_size = 128;
+    options.smatch_cfg = XD3_SMATCH_SLOW;
+    options.size_known = false;
 
-  Block block;
-  InMemoryEncodeDecode(spec0, spec1, &block, options);
-  Delta delta(block);
+    Block block;
+    InMemoryEncodeDecode(spec0, spec1, &block, options);
+    Delta delta(block);
 
-  // Allow an additional two byte of add per window
-  usize_t allowance = 2 * size / Constants::WINDOW_SIZE;
-  CHECK_GE(adds + allowance, delta.AddedBytes());
+    IF_DEBUG1(DP(RINT "[stride=%d] changes=%u adds=%"Q"u\n",
+                 s, changes, delta.AddedBytes()));
+    double allowance = Constants::BLOCK_SIZE < 8192 ? 3.0 : 1.1;
+    CHECK_GE(allowance, (double)delta.AddedBytes());
+  }
 }
 
 void TestCopyWindow() {
@@ -927,85 +929,73 @@ void TestCopyFromEnd() {
 }
 
 void TestHalfBlockCopy() {
-  MTRandom rand;
-  FileSpec spec0(&rand);
-  FileSpec spec1(&rand);
-
-  // The test takes place over four blocks, but we create a 8-block
-  // file to ensure that the whole input doesn't fit in memory.
-  spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 8);
-
-  // Create a half-block copy, 2.5 blocks apart, from the second half
-  // of the source version to the first half of the target version.
-  //       0             1             2             3
-  // spec0 [bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb][ccccc][bbbbb...]
-  // spec1 [aaaaa][ccccc][aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...]
-  ChangeList cl1;
-  cl1.push_back(Change(Change::MODIFY,
-                       Constants::BLOCK_SIZE / 2,  // size
-                       0));
-  cl1.push_back(Change(Change::COPYOVER,
-                       Constants::BLOCK_SIZE / 2,  // size
-                       Constants::BLOCK_SIZE * 3,  // offset
-                       Constants::BLOCK_SIZE / 2));
-  cl1.push_back(Change(Change::MODIFY,
-                       Constants::BLOCK_SIZE * 7,
-                       Constants::BLOCK_SIZE));
-  spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
-
-  const int nocopy_adds = 8 * Constants::BLOCK_SIZE;
-  const int onecopy_adds = nocopy_adds - Constants::BLOCK_SIZE / 2;
-
-  // TODO Note restricted loop
-  for (int b = 4; b <= 4; b++)
+  // Create a half-block copy, 7.5 blocks apart, in a pair of files:
+  //       0             1     ...     6             7
+  // spec0 [bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb][ccccc][bbbb_]
+  // spec1 [aaaaa][ccccc][aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa_]
+  // where stage=
+  // 0: the final block is full
+  //   a. (source)spec1->(target)spec0 copies block C: reads 8 source
+  //      blocks during target block 0.
+  //   b. (source)spec0->(target)spec1 does not copy block C b/c attempt
+  //      to read past EOF empties block 0 from (virtual) block cache
+  // 1: the final block is less than full.
+  //   a. (same) copies block C
+  //   b. (same) copies block C, unlike 0a, no attempt to read past EOF
+  //
+  // "virtual" above refers to XD3_TOOFARBACK, since there is no caching
+  // in the API, there is simply a promise not to request blocks that are
+  // beyond source->max_winsize from the last known source file position.
+  for (int stage = 0; stage < 2; stage++)
     {
+      IF_DEBUG1 (DP(RINT "half_block_copy stage %d\n", stage));
+
+      MTRandom rand;
+      FileSpec spec0(&rand);
+      FileSpec spec1(&rand);
+
+      spec0.GenerateFixedSize(Constants::BLOCK_SIZE * 8 - stage);
+
+      ChangeList cl1;
+      cl1.push_back(Change(Change::MODIFY,
+                           Constants::BLOCK_SIZE / 2,  // size
+                           0));
+      cl1.push_back(Change(Change::COPYOVER,
+                           Constants::BLOCK_SIZE / 2,  // size
+                           Constants::BLOCK_SIZE * 7,  // offset
+                           Constants::BLOCK_SIZE / 2));
+      cl1.push_back(Change(Change::MODIFY,
+                           Constants::BLOCK_SIZE * 7,
+                           Constants::BLOCK_SIZE - stage));
+      spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
+
       Options options;
-      options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * b;
+      options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * 8;
 
       Block block0;
       Block block1;
       InMemoryEncodeDecode(spec0, spec1, &block0, options);
       InMemoryEncodeDecode(spec1, spec0, &block1, options);
+
       Delta delta0(block0);
       Delta delta1(block1);
 
-      // The first block never copies from the last source block, by
-      // design, because if the last source block is available when
-      // the first target block is ready, the caller is expected to
-      // use a single block.
-      CHECK_EQ(nocopy_adds, delta0.AddedBytes());
-      if (Constants::BLOCK_SIZE < 8192 || b > 3)
-        {
-          // For small-block inputs, the entire file is read into one
-          // block (the min source window size is 16kB).
-          //
-          // For large blocks, at least 4 blocks of source window are
-          // needed.
-          CHECK_EQ(onecopy_adds, delta1.AddedBytes());
-        }
+      const int yes =
+        Constants::BLOCK_SIZE * 8 - Constants::BLOCK_SIZE / 2;
+      const int no =
+        Constants::BLOCK_SIZE * 8 - Constants::BLOCK_SIZE / 2;
+
+      if (stage == 0)
+        {
+          CHECK_EQ(yes, delta0.AddedBytes());
+          CHECK_EQ(no, delta1.AddedBytes());
+        }
       else
-        {
-          // When there are fewer than 3 source blocks.
-          CHECK_EQ(nocopy_adds, delta1.AddedBytes());
-        }
+        {
+          CHECK_EQ(yes, delta0.AddedBytes());
+          CHECK_EQ(yes, delta1.AddedBytes());
+        }
     }
-
-  Options options;
-  options.encode_srcwin_maxsz = Constants::BLOCK_SIZE * 4;
-  options.block_size = Constants::BLOCK_SIZE * 4;
-
-  // Test the whole-buffer case.
-  Block block0;
-  Block block1;
-  InMemoryEncodeDecode(spec0, spec1, &block0, options);
-  InMemoryEncodeDecode(spec1, spec0, &block1, options);
-  Delta delta0(block0);
-  Delta delta1(block1);
-  // This <= >= are only for blocksize = 512, which has irregular readsize.
-  CHECK_LE(onecopy_adds, delta0.AddedBytes());
-  CHECK_GE(onecopy_adds + 1, delta0.AddedBytes());
-
-  CHECK_EQ(onecopy_adds, delta1.AddedBytes());
 }
 
 void FourWayMergeTest(const FileSpec &spec0,
@@ -1299,10 +1289,10 @@ int main(int argc, char **argv)
   mcmd.push_back("test");
   mcmd.push_back(NULL);
 
-  // UnitTest<SmallBlock>();
-  // MainTest<SmallBlock>();
-  // MainTest<MixedBlock>();
-  // MainTest<OversizeBlock>();
+  UnitTest<SmallBlock>();
+  MainTest<SmallBlock>();
+  MainTest<MixedBlock>();
+  MainTest<OversizeBlock>();
   MainTest<LargeBlock>();
 
   CHECK_EQ(0, xd3_main_cmdline(mcmd.size() - 1,
@@ -1310,3 +1300,4 @@ int main(int argc, char **argv)
 
   return 0;
 }
+
diff --git a/xdelta3/testing/test.h b/xdelta3/testing/test.h
index d1f1a22..1eabcbd 100644
--- a/xdelta3/testing/test.h
+++ b/xdelta3/testing/test.h
@@ -22,8 +22,8 @@ extern "C" {
     typeof(x) _y(y); \
     if (!(_x OP _y)) { \
       cerr << __FILE__ << ":" << __LINE__ << " Check failed: " << #x " " #OP " " #y << endl; \
-      cerr << __FILE__ << ":" << __LINE__ << " Expected: " << _x << endl; \
-      cerr << __FILE__ << ":" << __LINE__ << " Actual: " << _y << endl; \
+      cerr << __FILE__ << ":" << __LINE__ << " {0} " << _x << endl; \
+      cerr << __FILE__ << ":" << __LINE__ << " {1} " << _y << endl; \
     abort(); \
     } } while (false)
 #undef CHECK
diff --git a/xdelta3/xdelta3-decode.h b/xdelta3/xdelta3-decode.h
index dc28323..6b3815f 100644
--- a/xdelta3/xdelta3-decode.h
+++ b/xdelta3/xdelta3-decode.h
@@ -207,9 +207,6 @@ xd3_decode_section (xd3_stream *stream,
           /* No allocation/copy needed */
           section->buf = stream->next_in;
           sect_take    = section->size;
-
-          IF_DEBUG2 (DP(RINT "[xd3_decode_section] copy==0 @ 0 %u\n",
-                        sect_take, section->alloc1));
         }
       else
         {
@@ -1166,8 +1163,8 @@ xd3_decode_input (xd3_stream *stream)
                           &src->cpyoff_blocks,
                           &src->cpyoff_blkoff);
           
-          IF_DEBUG1(DP(RINT
-                       "decode cpyoff %"Q"u "
+          IF_DEBUG2(DP(RINT
+                       "[decode_cpyoff] %"Q"u "
                        "cpyblkno %"Q"u "
                        "cpyblkoff %u "
                        "blksize %u\n",
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index 74889f2..2264e8e 100644
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -522,7 +522,7 @@ static void xd3_verify_large_state (xd3_stream *stream,
                                     uint32_t x_cksum);
 static void xd3_verify_small_state (xd3_stream    *stream,
                                     const uint8_t *inp,
-                                    uint32_t          x_cksum);
+                                    uint32_t       x_cksum);
 
 #endif /* XD3_DEBUG */
 #endif /* XD3_ENCODER */
@@ -1906,7 +1906,7 @@ usize_t xd3_bytes_on_srcblk (xd3_source *src, xoff_t blkno)
 }
 
 /* This function interfaces with the client getblk function, checks
- * its results, updates frontier_pos, max_blkno, onlastblk, eof_known. */
+ * its results, updates max_blkno, onlastblk, eof_known. */
 static int
 xd3_getblk (xd3_stream *stream, xoff_t blkno)
 {
@@ -1919,6 +1919,7 @@ xd3_getblk (xd3_stream *stream, xoff_t blkno)
 
       if (stream->getblk == NULL)
         {
+          IF_DEBUG2 (DP(RINT "[getblk] XD3_GETSRCBLK %"Q"u\n", blkno));
           stream->msg = "getblk source input";
           return XD3_GETSRCBLK;
         }
@@ -1930,8 +1931,10 @@ xd3_getblk (xd3_stream *stream, xoff_t blkno)
                         blkno, xd3_strerror (ret)));
           return ret;
         }
+
       IF_DEBUG2 (DP(RINT "[getblk] read source block %"Q"u onblk "
-                    "%u blksize %u\n", blkno, source->onblk, source->blksize));
+                    "%u blksize %u max_blkno %"Q"u\n", blkno, source->onblk,
+                    source->blksize, source->max_blkno));
     }
 
   if (blkno > source->max_blkno)
@@ -1960,9 +1963,8 @@ xd3_getblk (xd3_stream *stream, xoff_t blkno)
   if (blkno == source->max_blkno)
     {
       /* In case the application sets the source as 1 block w/ a
-         preset buffer. */
+       * preset buffer. */
       source->onlastblk = source->onblk;
-      source->frontier_pos = (blkno + 1) << source->shiftby;
     }
   return 0;
 }
@@ -1999,8 +2001,6 @@ xd3_set_source (xd3_stream *stream,
       IF_DEBUG1 (DP(RINT "raising src_maxsize to %u\n", src->blksize));
     }
   src->max_winsize = xd3_max (src->max_winsize, XD3_ALLOCSIZE);
-  src->frontier_pos = src->max_winsize;
-
   return 0;
 }
 
@@ -2012,13 +2012,14 @@ xd3_set_source_and_size (xd3_stream *stream,
   if (ret == 0)
     {
       stream->src->eof_known = 1;
-      IF_DEBUG2 (DP(RINT "[set source] size known %"Q"u\n",
-                    source_size));
 
       xd3_blksize_div(source_size,
                       stream->src,
                       &stream->src->max_blkno,
                       &stream->src->onlastblk);
+
+      IF_DEBUG1 (DP(RINT "[set source] size known %"Q"u max_blkno %"Q"u\n",
+                    source_size, stream->src->max_blkno));
     }
   return ret;
 }
@@ -3206,6 +3207,7 @@ xd3_encode_input (xd3_stream *stream)
                    * or else it can get stuck in a match-backward
                    * (getsrcblk) then match-forward (getsrcblk),
                    * find insufficient match length, then repeat
+
                    * exactly the same search.
                    */
                   stream->input_position += stream->match_fwd;
@@ -3231,7 +3233,7 @@ xd3_encode_input (xd3_stream *stream)
 
     case ENC_INSTR:
       /* Note: Jump here to encode VCDIFF deltas w/o using this
-       * string-matching code.  Merging code code enters here. */
+       * string-matching code.  Merging code enters here. */
 
       /* Flush the instrution buffer, then possibly add one more
        * instruction, then emit the header. */
@@ -3686,6 +3688,7 @@ xd3_srcwin_setup (xd3_stream *stream)
   /* Otherwise, we have to make a guess.  More copies may still be
    * issued, but we have to decide the source window base and length
    * now.  */
+  /* TODO: This may not working well in practice, more testing needed. */
   src->srcbase = stream->match_minaddr;
   src->srclen  = xd3_max ((usize_t) length,
                           stream->avail_in + (stream->avail_in >> 2));
@@ -3737,30 +3740,27 @@ xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos)
    * TestNonBlockingProgress test! */
   if (srcpos != 0 && srcpos == stream->match_last_srcpos)
     {
-      IF_DEBUG1(DP(RINT "[match_setup] looping failure\n"));
+      IF_DEBUG2(DP(RINT "[match_setup] looping failure\n"));
       goto bad;
     }
 
   /* Implement src->max_winsize, which prevents the encoder from seeking
    * back further than the LRU cache maintaining FIFO discipline, (to
    * avoid seeking). */
-  XD3_ASSERT (srcpos <= src->frontier_pos);
-
-  /* Prevent backwards seeks. This prevents an XD3_TOOFARBACK code
-     (checked below). */
-  if (src->frontier_pos - srcpos > src->max_winsize)
+  if (srcpos < stream->srcwin_cksum_pos &&
+      stream->srcwin_cksum_pos - srcpos > src->max_winsize)
     {
-      IF_DEBUG1(DP(RINT "[match_setup] rejected due to src->max_winsize "
-                   "distance eof=%"Q"u srcpos=%"Q"u frontier_pos=%"Q"u max_winsz=%"Q"u\n",
+      IF_DEBUG2(DP(RINT "[match_setup] rejected due to src->max_winsize "
+                   "distance eof=%"Q"u srcpos=%"Q"u max_winsz=%"Q"u\n",
                    xd3_source_eof (src),
-                   srcpos, src->frontier_pos, src->max_winsize));
+                   srcpos, src->max_winsize));
       goto bad;
     }
 
-  IF_DEBUG1(DP(RINT "[match_setup] %"Q"u frontier_pos %"Q"u, srcpos %"Q"u, "
+  IF_DEBUG2(DP(RINT "[match_setup] %"Q"u srcpos %"Q"u, "
                "src->max_winsize %"Q"u\n",
                stream->total_in + stream->input_position,
-               src->frontier_pos, srcpos, src->max_winsize));
+               srcpos, src->max_winsize));
 
   /* Going backwards, the 1.5-pass algorithm allows some
    * already-matched input may be covered by a longer source match.
@@ -3937,7 +3937,7 @@ xd3_source_extend_match (xd3_stream *stream)
   if (stream->match_state == MATCH_BACKWARD)
     {
       /* Note: this code is practically duplicated below, substituting
-       * match_fwd/match_back and direction.  TODO: Consolidate? */
+       * match_fwd/match_back and direction. */
       matchoff  = stream->match_srcpos - stream->match_back;
       streamoff = stream->input_position - stream->match_back;
       xd3_blksize_div (matchoff, src, &tryblk, &tryoff);
@@ -3956,10 +3956,8 @@ xd3_source_extend_match (xd3_stream *stream)
             {
               if (ret == XD3_TOOFARBACK)
                 {
-                  IF_DEBUG1({
-                      DP(RINT "[maxback] frontier block %u TOOFARBACK block %u\n",
-                         stream->src->frontier_pos >> stream->src->shiftby, tryblk);
-                    });
+                  IF_DEBUG1(DP(RINT "[maxback] frontier block %u TOOFARBACK block %u\n",
+                               stream->src->frontier_pos >> stream->src->shiftby, tryblk));
                   /* the starting position is too far back. */
                   if (stream->match_back == 0)
                     {
@@ -4343,13 +4341,14 @@ xd3_verify_run_state (xd3_stream    *stream,
 static int
 xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
 {
-  xoff_t logical_input_cksum_pos;
+  /* the source file is indexed until this point */
+  xoff_t target_cksum_pos;
+  /* the absolute target file input position */
   xoff_t absolute_input_pos;
-  xoff_t source_size;
 
   if (stream->src->eof_known)
     {
-      source_size = xd3_source_eof (stream->src);
+      xoff_t source_size = xd3_source_eof (stream->src);
       XD3_ASSERT(stream->srcwin_cksum_pos <= source_size);
 
       if (stream->srcwin_cksum_pos == source_size)
@@ -4361,30 +4360,29 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
 
   absolute_input_pos = stream->total_in + stream->input_position;
 
-  /* Begin by advancing at twice the input rate, up to half the
-   * maximum window size. */
-#if 1
-  if (absolute_input_pos < stream->src->max_winsize) {
-    logical_input_cksum_pos = stream->src->max_winsize;
-  } else {
-    logical_input_cksum_pos = absolute_input_pos + stream->src->max_winsize / 2;
-  }
-#else
-  logical_input_cksum_pos = xd3_min(absolute_input_pos * 2,
-                                    absolute_input_pos + (stream->src->max_winsize / 2));
-#endif
-
-  /* If srcwin_cksum_pos is already greater, wait until the difference
-   * is met. */
-  if (stream->srcwin_cksum_pos > logical_input_cksum_pos)
+  /* Immediately read the entire window. 
+   *
+   * Note: this reverses a long held policy, at this point in the
+   * code, of advancing relatively slowly as the input is read, which
+   * results in better compression for very-similar inputs, but worse
+   * compression where data is deleted near the beginning of the file.
+   * 
+   * The new policy is slower and may benefit, or slightly worsen,
+   * compression performance. TODO test these changes in 3.0.10 to
+   * 3.0.11 releases. */
+  if (absolute_input_pos < stream->src->max_winsize / 2)
+    {
+      target_cksum_pos = stream->src->max_winsize;
+    }
+  else
     {
-      *next_move_point = stream->input_position +
-        (usize_t)(stream->srcwin_cksum_pos - logical_input_cksum_pos);
-      IF_DEBUG1 (DP(RINT
-                    "[srcwin_move_point] %"Q"u cksum_pos greater than logical pos %"Q"u\n",
-                    stream->srcwin_cksum_pos, logical_input_cksum_pos));
-      return 0;
+      target_cksum_pos = absolute_input_pos + stream->src->max_winsize / 2;
+      target_cksum_pos &= ~stream->src->maskby;
     }
+  
+  /* If srcwin_cksum_pos is already greater, wait until the difference
+   * is met. */
+  XD3_ASSERT (stream->srcwin_cksum_pos <= target_cksum_pos);
 
   /* A long match may have extended past srcwin_cksum_pos.  Don't
    * start checksumming already-matched source data. */
@@ -4393,27 +4391,12 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
       stream->srcwin_cksum_pos = stream->maxsrcaddr;
     }
 
-  if (logical_input_cksum_pos < stream->srcwin_cksum_pos)
+  if (target_cksum_pos < stream->srcwin_cksum_pos)
     {
-      logical_input_cksum_pos = stream->srcwin_cksum_pos;
+      target_cksum_pos = stream->srcwin_cksum_pos;
     }
 
-  /* Advance at least one source block.  With the command-line
-   * defaults this means:
-   *
-   * if (src->size <= src->max_winsize), index the entire source at once
-   * using the position of the first non-match.  This is good for
-   * small inputs, especially when the content may have moved anywhere
-   * in the file (e.g., tar files).
-   *
-   * if (src->size > src->max_winsize), index at least one block ahead
-   * of the logical position.  This is good for different reasons:
-   * when a long match spanning several source blocks is encountered,
-   * this avoids computing checksums for those blocks.
-   */
-  logical_input_cksum_pos += stream->src->blksize;
-
-  while (stream->srcwin_cksum_pos < logical_input_cksum_pos &&
+  while (stream->srcwin_cksum_pos < target_cksum_pos &&
          (!stream->src->eof_known ||
           stream->srcwin_cksum_pos < xd3_source_eof (stream->src)))
     {
@@ -4437,17 +4420,17 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
             }
 
           IF_DEBUG1 (DP(RINT
-                        "[srcwin_move_point] async getblk return for %"Q"u\n",
-                        blkno));
-
+                        "[srcwin_move_point] async getblk return for %"Q"u: %s\n",
+                        blkno, xd3_strerror (ret)));
           return ret;
         }
 
       IF_DEBUG1 (DP(RINT
-                    "[srcwin_move_point] T=%"Q"u S=%"Q"u L=%"Q"u EOF=%"Q"u %s\n",
+                    "[srcwin_move_point] block %"Q"u T=%"Q"u S=%"Q"u L=%"Q"u EOF=%"Q"u %s\n",
+                    blkno,
                     stream->total_in + stream->input_position,
                     stream->srcwin_cksum_pos,
-                    logical_input_cksum_pos,
+                    target_cksum_pos,
                     xd3_source_eof (stream->src),
                     stream->src->eof_known ? "known" : "unknown"));
 
@@ -4456,7 +4439,7 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
       if (blkpos < (ssize_t) stream->smatcher.large_look)
         {
           stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize;
-          IF_DEBUG1 (DP(RINT "[srcwin_move_point] continue (end-of-block)\n"));
+          IF_DEBUG2 (DP(RINT "[srcwin_move_point] continue (end-of-block): %"Q"u\n", blkpos));
           continue;
         }
 
@@ -4491,19 +4474,9 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
       stream->srcwin_cksum_pos = (blkno + 1) * stream->src->blksize;
     }
 
-  IF_DEBUG1 (DP(RINT
-                "[srcwin_move_point] exited loop T=%"Q"u "
-                "S=%"Q"u L=%"Q"u EOF=%"Q"u %s\n",
-                stream->total_in + stream->input_position,
-                stream->srcwin_cksum_pos,
-                logical_input_cksum_pos,
-                xd3_source_eof (stream->src),
-                stream->src->eof_known ? "known" : "unknown"));
-
   if (stream->src->eof_known)
     {
-      source_size = xd3_source_eof (stream->src);
-
+      xoff_t source_size = xd3_source_eof (stream->src);
       if (stream->srcwin_cksum_pos >= source_size)
         {
           /* This invariant is needed for xd3_source_cksum_offset() */
@@ -4516,9 +4489,21 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
     }
 
   /* How long until this function should be called again. */
-  XD3_ASSERT(stream->srcwin_cksum_pos >= logical_input_cksum_pos);
-  *next_move_point = stream->input_position + 1 +
-    (usize_t)(stream->srcwin_cksum_pos - logical_input_cksum_pos);
+  XD3_ASSERT(stream->srcwin_cksum_pos >= target_cksum_pos);
+
+  *next_move_point = stream->input_position + stream->src->blksize / 2 -
+    (stream->input_position & stream->src->maskby);
+  
+  IF_DEBUG2 (DP(RINT
+                "[srcwin_move_point] finished T=%"Q"u "
+                "S=%"Q"u L=%"Q"u EOF=%"Q"u %s again in %u\n",
+                stream->total_in + stream->input_position,
+                stream->srcwin_cksum_pos,
+                target_cksum_pos,
+                xd3_source_eof (stream->src),
+                stream->src->eof_known ? "known" : "unknown",
+                *next_move_point - stream->input_position));
+
   return 0;
 }
 
@@ -4577,6 +4562,8 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
   usize_t        match_offset = 0;
   usize_t        next_move_point;
 
+  IF_DEBUG2(DP(RINT "[string_match] initial entry %u\n", stream->input_position));
+
   /* If there will be no compression due to settings or short input,
    * skip it entirely. */
   if (! (DO_SMALL || DO_LARGE || DO_RUN) ||
@@ -4588,6 +4575,8 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
    * needs to be reset. */
  restartloop:
 
+  IF_DEBUG2(DP(RINT "[string_match] restartloop %u\n", stream->input_position));
+
   /* If there is not enough input remaining for any kind of match,
      skip it. */
   if (stream->input_position + SLOOK > stream->avail_in) { goto loopnomore; }
@@ -4631,7 +4620,9 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
     {
       /* Source window: next_move_point is the point that
        * stream->input_position must reach before computing more
-       * source checksum. */
+       * source checksum.  Note: this is called unconditionally
+       * the first time after reentry, subsequent calls will be
+       * avoided if next_move_point is > input_position */
       if ((ret = xd3_srcwin_move_point (stream, & next_move_point)))
         {
           return ret;
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h
index 1aef6be..6cc0f9f 100644
--- a/xdelta3/xdelta3.h
+++ b/xdelta3/xdelta3.h
@@ -783,9 +783,6 @@ struct _xd3_source
   xoff_t              max_blkno;  /* Maximum block, if eof is known,
                                    * otherwise, equals frontier_blkno
                                    * (initially 0). */
-  xoff_t              frontier_pos;  /* The next source position to be
-                                      * read, equal to ((max_blkno+1)
-                                      * << shiftby) */
   usize_t             onlastblk;  /* Number of bytes on max_blkno */
   int                 eof_known;  /* Set to true when the first
                                    * partial block is read. */