Fixes two merge bugs:

1. The whole_state struct now keeps an array of window sizes so that
during reconstruction it can use the same window size as the target
delta.  The code was previously using dec_tgtlen, which was the window
size of the last target delta window.

2. xd3_merge_copy_source(), which applys a source-copy instruction 
during merge was not properly translating target-copy instructions
in the target.  The solution here is SLOW and INEFFICIENT, but it at
least allows the tests to pass.  A big TODO here is to improve the 
algorithm: it has a potentially O(N) recursion for each target-copy
that it sees, and the naive approach also can produce duplicate adds.

4 files changed, 97 insertions, 16 deletions

diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h
index ae6fc19..46b2cfb 100644
--- a/xdelta3/xdelta3-main.h
+++ b/xdelta3/xdelta3-main.h
@@ -1265,7 +1265,7 @@ main_print_window (xd3_stream* stream, main_file *xfile)
             {
               if (stream->dec_current1.addr >= stream->dec_cpylen) 
                 {
-                  VC(UT " T@%-6"Q"u", 
+                  VC(UT " T@%-6u", 
                      stream->dec_current1.addr - stream->dec_cpylen)VE;
                 } 
               else
@@ -1293,7 +1293,7 @@ main_print_window (xd3_stream* stream, main_file *xfile)
             {
               if (stream->dec_current2.addr >= stream->dec_cpylen) 
                 {
-                  VC(UT " T@%-6"Q"u", 
+                  VC(UT " T@%-6u", 
                      stream->dec_current2.addr - stream->dec_cpylen)VE;
                 } 
               else
@@ -1794,6 +1794,7 @@ main_merge_output (xd3_stream *stream, main_file *ofile)
   usize_t inst_pos = 0;
   xoff_t output_pos = 0;
   xd3_source recode_source;
+  usize_t window_num = 0;
   int at_least_once = 0;
 
   /* merge_stream is set if there were arguments.  this stream's input
@@ -1821,6 +1822,7 @@ main_merge_output (xd3_stream *stream, main_file *ofile)
       xoff_t window_srcmin = 0;
       xoff_t window_srcmax = 0;
       usize_t window_pos = 0;
+      usize_t window_size;
 
       /* at_least_once ensures that we encode at least one window,
        * which handles the 0-byte case. */
@@ -1834,25 +1836,31 @@ main_merge_output (xd3_stream *stream, main_file *ofile)
           return XD3_INVALID;
         }
 
-      if (main_bsize < stream->dec_tgtlen)
+      /* Window sizes must match from the input to the output, so that
+       * target copies are in-range (and so that checksums carry
+       * over). */
+      XD3_ASSERT (window_num < stream->whole_target.winsizeslen);
+      window_size = stream->whole_target.winsizes[window_num++];
+
+      if (main_bsize < window_size)
         {
           main_free (main_bdata);
           main_bdata = NULL;
           main_bsize = 0;
           if ((main_bdata = (uint8_t*) 
-               main_malloc (stream->dec_tgtlen)) == NULL)
+               main_malloc (window_size)) == NULL)
             {
               return ENOMEM;
             }
-          main_bsize = stream->dec_tgtlen;
+          main_bsize = window_size;
         }
 
       /* This encodes a single target window. */
-      while (window_pos < stream->dec_tgtlen &&
+      while (window_pos < window_size &&
              inst_pos < stream->whole_target.instlen)
         {
           xd3_winst *inst = &stream->whole_target.inst[inst_pos];
-          usize_t take = min(inst->size, stream->dec_tgtlen - window_pos);
+          usize_t take = min(inst->size, window_size - window_pos);
           xoff_t addr;
 
           switch (inst->type)
diff --git a/xdelta3/xdelta3-merge.h b/xdelta3/xdelta3-merge.h
index fefe55d..553fbf0 100644
--- a/xdelta3/xdelta3-merge.h
+++ b/xdelta3/xdelta3-merge.h
@@ -28,15 +28,19 @@ xd3_whole_state_init (xd3_stream *stream)
 {
   XD3_ASSERT (stream->whole_target.adds == NULL);
   XD3_ASSERT (stream->whole_target.inst == NULL);
+  XD3_ASSERT (stream->whole_target.winsizes == NULL);
   XD3_ASSERT (stream->whole_target.length == 0);
 
   stream->whole_target.adds_alloc = XD3_ALLOCSIZE;
-  stream->whole_target.inst_alloc = XD3_ALLOCSIZE / sizeof (xd3_winst);
+  stream->whole_target.inst_alloc = XD3_ALLOCSIZE;
+  stream->whole_target.winsizes_alloc = XD3_ALLOCSIZE;
 
   if ((stream->whole_target.adds = (uint8_t*) 
-       xd3_alloc (stream, XD3_ALLOCSIZE, 1)) == NULL ||
+       xd3_alloc (stream, stream->whole_target.adds_alloc, 1)) == NULL ||
       (stream->whole_target.inst = (xd3_winst*) 
-       xd3_alloc (stream, XD3_ALLOCSIZE, sizeof(xd3_winst))) == NULL)
+       xd3_alloc (stream, stream->whole_target.inst_alloc, 1)) == NULL ||
+      (stream->whole_target.winsizes = (usize_t*) 
+       xd3_alloc (stream, stream->whole_target.winsizes_alloc, 1)) == NULL)
     {
       return ENOMEM;
     }
@@ -50,6 +54,7 @@ xd3_swap_whole_state (xd3_whole_state *a,
   xd3_whole_state tmp;
   XD3_ASSERT (a->inst != NULL && a->adds != NULL);
   XD3_ASSERT (b->inst != NULL && b->adds != NULL);
+  XD3_ASSERT (b->winsizes != NULL && b->winsizes != NULL);
   memcpy (&tmp, a, sizeof (xd3_whole_state));
   memcpy (a, b, sizeof (xd3_whole_state));
   memcpy (b, &tmp, sizeof (xd3_whole_state));
@@ -134,6 +139,27 @@ xd3_whole_alloc_adds (xd3_stream *stream,
 }
 
 static int
+xd3_whole_alloc_winsize (xd3_stream *stream,
+                         usize_t **winsizep)
+{
+  int ret;
+
+  if ((ret = xd3_realloc_buffer (stream, 
+                                 stream->whole_target.winsizeslen, 
+                                 sizeof (xd3_winst),
+                                 1,
+                                 & stream->whole_target.winsizes_alloc, 
+                                 (void**) & stream->whole_target.winsizes))) 
+    { 
+      return ret; 
+    }
+
+  *winsizep = &stream->whole_target.winsizes[stream->whole_target.winsizeslen++];
+
+  return 0;
+}
+
+static int
 xd3_whole_append_inst (xd3_stream *stream,
                        xd3_hinst *inst)
 {
@@ -197,8 +223,13 @@ int
 xd3_whole_append_window (xd3_stream *stream)
 {
   int ret;
+  usize_t *winsize;
 
   stream->whole_target.windows += 1;
+  
+  if ((ret = xd3_whole_alloc_winsize (stream, &winsize))) { return ret; }
+
+  *winsize = stream->dec_tgtlen;
 
   while (stream->inst_sect.buf < stream->inst_sect.buf_max)
     {
@@ -325,7 +356,6 @@ xd3_merge_target_copy (xd3_stream *stream,
     }
 
   XD3_ASSERT (stream->whole_target.length == iinst->position);
-  stream->whole_target.length += iinst->size;
 
   memcpy (oinst, iinst, sizeof (*oinst));
   return 0;
@@ -381,7 +411,7 @@ xd3_merge_find_position (xd3_stream *stream,
 static int
 xd3_merge_source_copy (xd3_stream *stream,
                        xd3_whole_state *source,
-                       xd3_winst *iinst_orig)
+                       const xd3_winst *iinst_orig)
 {
   int ret;
   xd3_winst iinst;
@@ -455,12 +485,35 @@ xd3_merge_source_copy (xd3_stream *stream,
           stream->whole_target.addslen += this_take;
           break;
         default:
-          minst->mode = sinst->mode;
-          minst->addr = sinst->addr + sinst_offset;
+          if (sinst->mode != 0)
+            {
+              minst->mode = sinst->mode;
+              minst->addr = sinst->addr + sinst_offset;
+            }
+          else
+            {
+              // TODO: this is slow because of the recursion, which
+              // could reach a depth equal to the number of target
+              // copies, and this is compression-inefficient because
+              // it can produce duplicate adds.
+              xd3_winst tinst;
+              tinst.type = XD3_CPY;
+              tinst.mode = iinst.mode;
+              tinst.addr = sinst->addr + sinst_offset;
+              tinst.size = this_take;
+              tinst.position = iinst.position;
+
+              // The instruction allocated in this frame will not be used.
+              stream->whole_target.instlen -= 1;
+
+              if ((ret = xd3_merge_source_copy (stream, source, &tinst)))
+                { 
+                  return ret;
+                }
+            }
           break;
         }
 
-      stream->whole_target.length += this_take;
       iinst.position += this_take;
       iinst.addr += this_take;
       iinst.size -= this_take;
@@ -477,8 +530,17 @@ int xd3_merge_inputs (xd3_stream *stream,
                       xd3_whole_state *input)
 {
   int ret = 0;
+  usize_t i;
   size_t input_i;
 
+  for (i = 0; i < input->winsizeslen; ++i) {
+    usize_t *copysize;
+
+    if ((ret = xd3_whole_alloc_winsize (stream, &copysize))) { return ret; }
+
+    *copysize = input->winsizes[i];
+  }
+
   /* iterate over each instruction. */
   for (input_i = 0; ret == 0 && input_i < input->instlen; ++input_i)
     {
@@ -493,7 +555,7 @@ int xd3_merge_inputs (xd3_stream *stream,
           ret = xd3_merge_add (stream, input, iinst);
           break;
         default:
-          /* Note: VCD_TARGET support is completely untested all 
+          /* TODO: VCD_TARGET support is completely untested all
            * throughout. */
           if (iinst->mode == 0 || iinst->mode == VCD_TARGET)
             {
@@ -503,6 +565,10 @@ int xd3_merge_inputs (xd3_stream *stream,
             {
               ret = xd3_merge_source_copy (stream, source, iinst);
             }
+
+          /* The whole_target.length is not updated in the xd3_merge*copy
+           * routine because of recursion in xd3_merge_source_copy. */
+          stream->whole_target.length += iinst->size;
           break;
         }
     }
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index bdf02af..7921556 100644
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -2295,6 +2295,7 @@ xd3_free_stream (xd3_stream *stream)
 
   xd3_free (stream, stream->whole_target.adds);
   xd3_free (stream, stream->whole_target.inst);
+  xd3_free (stream, stream->whole_target.winsizes);
 
   XD3_ASSERT (stream->alloc_cnt == stream->free_cnt);
 
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h
index fc3316a..1e6d4af 100644
--- a/xdelta3/xdelta3.h
+++ b/xdelta3/xdelta3.h
@@ -643,9 +643,15 @@ struct _xd3_whole_state {
   usize_t addslen;
   uint8_t *adds;
   usize_t  adds_alloc;
+
   usize_t instlen;
   xd3_winst *inst;
   usize_t  inst_alloc;
+
+  usize_t winsizeslen;
+  usize_t *winsizes;
+  usize_t winsizes_alloc;
+
   xoff_t length;
   xoff_t windows;
 };