Changes to support -I IOPT_SIZE on the commandline. New support for unlimited instruction

buffer size set by -I 0. The default remains 4096.

5 files changed, 143 insertions, 70 deletions

diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h
index cada82b..44bd6e5 100755
--- a/xdelta3/xdelta3-main.h
+++ b/xdelta3/xdelta3-main.h
@@ -248,7 +248,7 @@ static int         option_quiet              = 0;
 static int         option_level              = 5;
 static int         option_use_appheader      = 1;
 static uint8_t*    option_appheader          = NULL;
-static int         option_use_secondary      = /* until-standardized, leave this off */ 0;
+static int         option_use_secondary      = 0;
 static char*       option_secondary          = NULL;
 static int         option_use_checksum       = 1;
 static int         option_use_altcodetable   = 0;
@@ -257,6 +257,7 @@ static int         option_no_compress        = 0;
 static int         option_no_output          = 0; /* go through the motions, but do not open or write output */
 static const char *option_source_filename    = NULL;
 
+static int         option_iopt_size          = XD3_DEFAULT_IOPT_SIZE;
 static usize_t     option_winsize            = XD3_DEFAULT_WINSIZE;
 static usize_t     option_srcwinsz           = XD3_DEFAULT_SRCWINSZ;
 static int         option_srcwinsz_set       = 0;
@@ -2267,6 +2268,7 @@ main_input (xd3_cmd     cmd,
   config.sec_data.ngroups = 1;
   config.sec_addr.ngroups = 1;
   config.sec_inst.ngroups = 1;
+  config.iopt_size = option_iopt_size;
 
   /* TODO: eliminate static variables. */
   do_not_lru = 0;
@@ -2553,12 +2555,22 @@ main_input (xd3_cmd     cmd,
           {
             if (IS_ENCODE (cmd) || cmd == CMD_DECODE)
               {
-                int used_source = xd3_encoder_used_source (& stream);
-
-                if (! option_quiet && IS_ENCODE (cmd) && main_file_isopen (sfile) && ! used_source)
+                if (! option_quiet && IS_ENCODE (cmd))
                   {
-                    XPR(NT "warning: input position %"Q"u no source copies\n",
-                        stream.current_window * option_winsize);
+                    /* Warn when no source copies are found */
+                    if (main_file_isopen (sfile) && ! xd3_encoder_used_source (& stream))
+                      {
+                        XPR(NT "warning: input position %"Q"u no source copies\n",
+                            stream.current_window * option_winsize);
+                      }
+
+                    /* Warn about bad compression due to limited instruction buffer */
+                    if (stream.i_slots_used > stream.iopt_size)
+                      {
+                        XPR(NT "warning: input position %"Q"u overflowed instruction buffer, "
+                            "needed %u (vs. %u)\n",
+                            stream.current_window * option_winsize, stream.i_slots_used, stream.iopt_size);
+                      }
                   }
 
                 if (option_verbose)
@@ -2723,7 +2735,7 @@ main (int argc, char **argv)
   main_file ifile;
   main_file ofile;
   main_file sfile;
-  static char *flags = "0123456789cdefhnqvDJNORTVs:B:C:E:F:L:O:P:M:W:A::S::";
+  static char *flags = "0123456789cdefhnqvDJNORTVs:B:C:E:F:I:L:O:P:M:W:A::S::";
   int my_optind;
   char *my_optarg;
   char *my_optstr;
@@ -2925,6 +2937,13 @@ main (int argc, char **argv)
               goto exit;
             }
           break;
+        case 'I':
+          if ((ret = main_atou (my_optarg, & option_iopt_size, 0,
+                                0, 'I')))
+            {
+              goto exit;
+            }
+          break;
         case 'W':
           if ((ret = main_atou (my_optarg, & option_winsize, XD3_ALLOCSIZE,
                                 XD3_HARDMAXWINSIZE, 'W')))
@@ -3126,6 +3145,7 @@ main_help (void)
   P(RINT "memory options:\n");
   P(RINT "   -B bytes     source window size\n");
   P(RINT "   -W bytes     input window size\n");
+  P(RINT "   -I size      instruction buffer size (0 = unlimited)\n");
 
   P(RINT "compression options:\n");
   P(RINT "   -s source    source file to copy from (if any)\n");
@@ -3133,15 +3153,15 @@ main_help (void)
   P(RINT "   -N           disable small string-matching compression\n");
   P(RINT "   -D           disable external decompression (encode/decode)\n");
   P(RINT "   -R           disable external recompression (decode)\n");
+  P(RINT "   -n           disable checksum (encode/decode)\n");
+  P(RINT "   -C           soft config (encode, undocumented)\n");
+  P(RINT "   -A [apphead] disable/provide application header (encode)\n");
 
 #if XD3_DEBUG > 0
   P(RINT "developer options:\n");
-  P(RINT "   -A [apphead] disable/provide application header\n");
-  P(RINT "   -C           soft config (see xdelta3-cfgs.h)\n");
   P(RINT "   -J           disable output (check/compute only)\n");
   P(RINT "   -P           repeat count (for profiling)\n");
   P(RINT "   -T           use alternate code table\n");
-  P(RINT "   -n           disable checksum (encode/decode)\n");
 #endif
   return EXIT_FAILURE;
 }
diff --git a/xdelta3/xdelta3-regtest.py b/xdelta3/xdelta3-regtest.py
index 7bb7a1c..bf064bb 100755
--- a/xdelta3/xdelta3-regtest.py
+++ b/xdelta3/xdelta3-regtest.py
@@ -611,15 +611,15 @@ def BigFileRun(f1, f2):
 def RandomBigRun(f1, f2):
 
     input_ranges = [
-        (7, 9, 'large_look'),
-        (1, 10, 'large_step'),
+        (7, 20, 'large_look'),
+        (1, 30, 'large_step'),
         (4, 5, 'small_look'),
-        (1, 20, 'small_chain'),
-        (1, 10, 'small_lchain'),
+        (1, 32, 'small_chain'),
+        (1, 16, 'small_lchain'),
         (0, 1, 'ssmatch'),
         (0, 1, 'trylazy'),
-        (1, 32, 'max_lazy'),
-        (1, 64, 'long_enough'),
+        (1, 128, 'max_lazy'),
+        (1, 256, 'long_enough'),
         (0, 1, 'promote'),
     ]
 
diff --git a/xdelta3/xdelta3-test.h b/xdelta3/xdelta3-test.h
index 2c7af22..36166c6 100755
--- a/xdelta3/xdelta3-test.h
+++ b/xdelta3/xdelta3-test.h
@@ -2049,9 +2049,9 @@ test_string_matching (xd3_stream *stream, int ignore)
       if ((ret = stream->smatcher.string_match (stream))) { return ret; }
 
       *rptr = 0;
-      while (! xd3_rlist_empty (& stream->iopt.used))
+      while (! xd3_rlist_empty (& stream->iopt_used))
         {
-          xd3_rinst *inst = xd3_rlist_pop_front (& stream->iopt.used);
+          xd3_rinst *inst = xd3_rlist_pop_front (& stream->iopt_used);
 
           switch (inst->type)
             {
@@ -2072,7 +2072,7 @@ test_string_matching (xd3_stream *stream, int ignore)
 
           *rptr++ = ' ';
 
-          xd3_rlist_push_back (& stream->iopt.free, inst);
+          xd3_rlist_push_back (& stream->iopt_free, inst);
         }
 
       if (rptr != rbuf)
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index 14a3c08..97c3390 100755
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -550,7 +550,7 @@ static void*       xd3_alloc0 (xd3_stream *stream,
 static xd3_output* xd3_alloc_output (xd3_stream *stream,
                                      xd3_output *old_output);
 
-
+static int         xd3_alloc_iopt (xd3_stream *stream, int elts);
 
 static void        xd3_free_output (xd3_stream *stream,
                                     xd3_output *output);
@@ -2281,11 +2281,20 @@ xd3_free_output (xd3_stream *stream,
 void
 xd3_free_stream (xd3_stream *stream)
 {
+  xd3_iopt_buflist *blist = stream->iopt_alloc;
+
+  do
+    {
+      xd3_iopt_buflist *tmp = blist;
+      blist = blist->next;
+      xd3_free (stream, tmp->buffer);
+      xd3_free (stream, tmp);
+    }
+  while (blist != NULL);
 
   xd3_free (stream, stream->large_table);
   xd3_free (stream, stream->small_table);
   xd3_free (stream, stream->small_prev);
-  xd3_free (stream, stream->iopt.buffer);
 
 #if XD3_ENCODER
   {
@@ -2393,6 +2402,12 @@ xd3_config_stream(xd3_stream *stream,
   stream->srcwin_size  = config->srcwin_size ? config->srcwin_size : XD3_DEFAULT_CKSUM_ADVANCE;
   stream->srcwin_maxsz = config->srcwin_maxsz ? config->srcwin_maxsz : XD3_DEFAULT_SRCWINSZ;
 
+  if (stream->iopt_size == 0)
+    {
+      stream->iopt_size = XD3_ALLOCSIZE / sizeof(xd3_rinst);
+      stream->iopt_unlimited = 1;
+    }
+
   stream->getblk    = config->getblk;
   stream->alloc     = config->alloc ? config->alloc : __xd3_alloc_func;
   stream->free      = config->freef ? config->freef : __xd3_free_func;
@@ -2663,8 +2678,8 @@ xd3_set_appheader (xd3_stream    *stream,
 static int
 xd3_iopt_check (xd3_stream *stream)
 {
-  int ul = xd3_rlist_length (& stream->iopt.used);
-  int fl = xd3_rlist_length (& stream->iopt.free);
+  int ul = xd3_rlist_length (& stream->iopt_used);
+  int fl = xd3_rlist_length (& stream->iopt_free);
 
   return (ul + fl + (stream->iout ? 1 : 0)) == stream->iopt_size;
 }
@@ -2674,7 +2689,7 @@ static xd3_rinst*
 xd3_iopt_free (xd3_stream *stream, xd3_rinst *i)
 {
   xd3_rinst *n = xd3_rlist_remove (i);
-  xd3_rlist_push_back (& stream->iopt.free, i);
+  xd3_rlist_push_back (& stream->iopt_free, i);
   return n;
 }
 
@@ -2683,7 +2698,7 @@ xd3_iopt_free_nonadd (xd3_stream *stream, xd3_rinst *i)
 {
   if (i->type != XD3_ADD)
     {
-      xd3_rlist_push_back (& stream->iopt.free, i);
+      xd3_rlist_push_back (& stream->iopt_free, i);
     }
 }
 
@@ -2885,7 +2900,7 @@ xd3_iopt_add_finalize (xd3_stream *stream)
 static int
 xd3_iopt_flush_instructions (xd3_stream *stream, int force)
 {
-  xd3_rinst *r1 = xd3_rlist_front (& stream->iopt.used);
+  xd3_rinst *r1 = xd3_rlist_front (& stream->iopt_used);
   xd3_rinst *r2;
   xd3_rinst *r3;
   usize_t r1end;
@@ -2901,8 +2916,8 @@ xd3_iopt_flush_instructions (xd3_stream *stream, int force)
   /* Note: once tried to skip this step if it's possible to assert there are no
    * overlapping instructions.  Doesn't work because xd3_opt_erase leaves overlapping
    * instructions. */
-  while (! xd3_rlist_end (& stream->iopt.used, r1) &&
-         ! xd3_rlist_end (& stream->iopt.used, r2 = xd3_rlist_next (r1)))
+  while (! xd3_rlist_end (& stream->iopt_used, r1) &&
+         ! xd3_rlist_end (& stream->iopt_used, r2 = xd3_rlist_next (r1)))
     {
       r1end = r1->pos + r1->size;
 
@@ -2919,7 +2934,7 @@ xd3_iopt_flush_instructions (xd3_stream *stream, int force)
       XD3_ASSERT (r2end > (r1end + LEAST_MATCH_INCR));
 
       /* If r3 is available... */
-      if (! xd3_rlist_end (& stream->iopt.used, r3 = xd3_rlist_next (r2)))
+      if (! xd3_rlist_end (& stream->iopt_used, r3 = xd3_rlist_next (r2)))
         {
           /* If r3 starts before r1 finishes or just about, r2 is irrelevant */
           if (r3->pos <= r1end + 1)
@@ -3026,9 +3041,9 @@ xd3_iopt_flush_instructions (xd3_stream *stream, int force)
 
   /* If forcing, pick instructions until the list is empty, otherwise this empties 50% of
    * the queue. */
-  for (flushed = 0; ! xd3_rlist_empty (& stream->iopt.used); )
+  for (flushed = 0; ! xd3_rlist_empty (& stream->iopt_used); )
     {
-      xd3_rinst *renc = xd3_rlist_pop_front (& stream->iopt.used);
+      xd3_rinst *renc = xd3_rlist_pop_front (& stream->iopt_used);
       if ((ret = xd3_iopt_add_encoding (stream, renc)))
         {
           return ret;
@@ -3044,10 +3059,10 @@ xd3_iopt_flush_instructions (xd3_stream *stream, int force)
           /* If there are only two instructions remaining, break, because they were
            * not optimized.  This means there were more than 50% eliminated by the
            * loop above. */
-          r1 = xd3_rlist_front (& stream->iopt.used);
-          if (xd3_rlist_end(& stream->iopt.used, r1) ||
-              xd3_rlist_end(& stream->iopt.used, r2 = xd3_rlist_next (r1)) ||
-              xd3_rlist_end(& stream->iopt.used, r3 = xd3_rlist_next (r2)))
+          r1 = xd3_rlist_front (& stream->iopt_used);
+          if (xd3_rlist_end(& stream->iopt_used, r1) ||
+              xd3_rlist_end(& stream->iopt_used, r2 = xd3_rlist_next (r1)) ||
+              xd3_rlist_end(& stream->iopt_used, r3 = xd3_rlist_next (r2)))
             {
               break;
             }
@@ -3056,7 +3071,7 @@ xd3_iopt_flush_instructions (xd3_stream *stream, int force)
 
   XD3_ASSERT (xd3_iopt_check (stream));
 
-  XD3_ASSERT (!force || xd3_rlist_length (& stream->iopt.used) == 0);
+  XD3_ASSERT (!force || xd3_rlist_length (& stream->iopt_used) == 0);
 
   return 0;
 }
@@ -3067,19 +3082,33 @@ xd3_iopt_get_slot (xd3_stream *stream, xd3_rinst** iptr)
   xd3_rinst *i;
   int ret;
 
-  if (xd3_rlist_empty (& stream->iopt.free))
+  if (xd3_rlist_empty (& stream->iopt_free))
     {
-      if ((ret = xd3_iopt_flush_instructions (stream, 0))) { return ret; }
+      if (stream->iopt_unlimited)
+        {
+          int elts = XD3_ALLOCSIZE / sizeof(xd3_rinst);
+          if ((ret = xd3_alloc_iopt (stream, elts)))
+            {
+              return ret;
+            }
+          stream->iopt_size += elts;
+        }
+      else
+        {
+          if ((ret = xd3_iopt_flush_instructions (stream, 0))) { return ret; }
 
-      XD3_ASSERT (! xd3_rlist_empty (& stream->iopt.free));
+          XD3_ASSERT (! xd3_rlist_empty (& stream->iopt_free));
+        }
     }
 
-  i = xd3_rlist_pop_back (& stream->iopt.free);
+  i = xd3_rlist_pop_back (& stream->iopt_free);
 
-  xd3_rlist_push_back (& stream->iopt.used, i);
+  xd3_rlist_push_back (& stream->iopt_used, i);
 
   (*iptr) = i;
 
+  ++stream->i_slots_used;
+
   return 0;
 }
 
@@ -3090,9 +3119,9 @@ xd3_iopt_get_slot (xd3_stream *stream, xd3_rinst** iptr)
 static void
 xd3_iopt_erase (xd3_stream *stream, usize_t pos, usize_t size)
 {
-  while (! xd3_rlist_empty (& stream->iopt.used))
+  while (! xd3_rlist_empty (& stream->iopt_used))
     {
-      xd3_rinst *r = xd3_rlist_back (& stream->iopt.used);
+      xd3_rinst *r = xd3_rlist_back (& stream->iopt_used);
 
       /* Verify that greedy is working.  The previous instruction should end before the
        * new one begins. */
@@ -3110,7 +3139,8 @@ xd3_iopt_erase (xd3_stream *stream, usize_t pos, usize_t size)
 
       /* Otherwise, the new instruction covers the old one, delete it and repeat. */
       xd3_rlist_remove (r);
-      xd3_rlist_push_back (& stream->iopt.free, r);
+      xd3_rlist_push_back (& stream->iopt_free, r);
+      --stream->i_slots_used;
     }
 }
 
@@ -3120,12 +3150,12 @@ xd3_iopt_last_matched (xd3_stream *stream)
 {
   xd3_rinst *r;
 
-  if (xd3_rlist_empty (& stream->iopt.used))
+  if (xd3_rlist_empty (& stream->iopt_used))
     {
       return 0;
     }
 
-  r = xd3_rlist_back (& stream->iopt.used);
+  r = xd3_rlist_back (& stream->iopt_used);
 
   return r->pos + r->size;
 }
@@ -3430,6 +3460,31 @@ xd3_encode_buffer_leftover (xd3_stream *stream)
   return 0;
 }
 
+/* Allocates one block of xd3_rlist elements */
+static int
+xd3_alloc_iopt (xd3_stream *stream, int elts)
+{
+  int i;
+  xd3_iopt_buflist* next = stream->iopt_alloc;
+  xd3_iopt_buflist* last = xd3_alloc (stream, sizeof (xd3_iopt_buflist), 1);
+
+  if (last == NULL ||
+      (last->buffer = xd3_alloc (stream, sizeof (xd3_rinst), elts)) == NULL)
+    {
+      return ENOMEM;
+    }
+
+  last->next = next;
+  stream->iopt_alloc = last;
+
+  for (i = 0; i < elts; i += 1)
+    {
+      xd3_rlist_push_back (& stream->iopt_free, & last->buffer[i]);
+    }
+
+  return 0;
+}
+
 /* This function allocates all memory initially used by the encoder. */
 static int
 xd3_encode_init (xd3_stream *stream)
@@ -3454,9 +3509,9 @@ xd3_encode_init (xd3_stream *stream)
 
   if (small_comp)
     {
-      /* Hard-coded, keeps table small because small matches become inefficient. */
-      // TODO: verify this
-      usize_t hash_values = min(stream->winsize, 65536U);
+      /* Hard-coded, keeps table small because small matches become inefficient.
+       * TODO: verify this stuff. */
+      usize_t hash_values = min(stream->winsize, XD3_DEFAULT_SPREVSZ);
 
       xd3_size_hashtable (stream,
                           hash_values,
@@ -3474,21 +3529,13 @@ xd3_encode_init (xd3_stream *stream)
     }
 
   /* iopt buffer */
-  xd3_rlist_init (& stream->iopt.used);
-  xd3_rlist_init (& stream->iopt.free);
+  xd3_rlist_init (& stream->iopt_used);
+  xd3_rlist_init (& stream->iopt_free);
 
-  if ((stream->iopt.buffer = xd3_alloc (stream, sizeof (xd3_rinst), stream->iopt_size)) == NULL)
-    {
-      goto fail;
-    }
-
-  for (i = 0; i < stream->iopt_size; i += 1)
-    {
-      xd3_rlist_push_back (& stream->iopt.free, & stream->iopt.buffer[i]);
-    }
+  if (xd3_alloc_iopt (stream, stream->iopt_size) != 0) { goto fail; }
 
-  XD3_ASSERT (xd3_rlist_length (& stream->iopt.free) == stream->iopt_size);
-  XD3_ASSERT (xd3_rlist_length (& stream->iopt.used) == 0);
+  XD3_ASSERT (xd3_rlist_length (& stream->iopt_free) == stream->iopt_size);
+  XD3_ASSERT (xd3_rlist_length (& stream->iopt_used) == 0);
 
   /* address cache, code table */
   stream->acache.s_near = stream->code_table_desc->near_modes;
@@ -3532,6 +3579,7 @@ xd3_encode_reset (xd3_stream *stream)
   IF_DEBUG (stream->n_emit = 0);
   stream->avail_in     = 0;
   stream->small_reset  = 1;
+  stream->i_slots_used = 0;
 
   if (stream->src != NULL)
     {
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h
index a9ca8f1..c2fe0a6 100755
--- a/xdelta3/xdelta3.h
+++ b/xdelta3/xdelta3.h
@@ -74,7 +74,8 @@
 
 /* The IOPT_SIZE value sets the size of a buffer used to batch overlapping copy
  * instructions before they are optimized by picking the best non-overlapping ranges.  The
- * larger this buffer, the longer a forced xd3_srcwin_setup() decision is held off. */
+ * larger this buffer, the longer a forced xd3_srcwin_setup() decision is held off.
+ * Setting this value to 0 causes an unlimited buffer to be used. */
 #ifndef XD3_DEFAULT_IOPT_SIZE
 #define XD3_DEFAULT_IOPT_SIZE    (1U<<12)
 #endif
@@ -192,7 +193,7 @@ typedef struct _xd3_rpage              xd3_rpage;
 typedef struct _xd3_addr_cache         xd3_addr_cache;
 typedef struct _xd3_output             xd3_output;
 typedef struct _xd3_desect             xd3_desect;
-typedef struct _xd3_iopt_buf           xd3_iopt_buf;
+typedef struct _xd3_iopt_buflist       xd3_iopt_buflist;
 typedef struct _xd3_rlist              xd3_rlist;
 typedef struct _xd3_sec_type           xd3_sec_type;
 typedef struct _xd3_sec_cfg            xd3_sec_cfg;
@@ -484,13 +485,12 @@ struct _xd3_addr_cache
   usize_t *same_array; /* array of size s_same*256    */
 };
 
-/* the IOPT buffer has a used list of (ordered) instructions, possibly overlapping in
- * target addresses, awaiting a flush */
-struct _xd3_iopt_buf
+/* the IOPT buffer list is just a list of buffers, which may be allocated
+ * during encode when using an unlimited buffer. */
+struct _xd3_iopt_buflist
 {
-  xd3_rlist  used;
-  xd3_rlist  free;
   xd3_rinst *buffer;
+  xd3_iopt_buflist *next;
 };
 
 /* This is the record of a pre-compiled configuration, a subset of xd3_config. */
@@ -634,6 +634,7 @@ struct _xd3_stream
   usize_t           sprevsz;          /* small string, previous window size (power of 2) */
   usize_t           sprevmask;        /* small string, previous window size mask */
   uint              iopt_size;
+  uint              iopt_unlimited;
   uint              srcwin_size;
   uint              srcwin_maxsz;
 
@@ -698,8 +699,10 @@ struct _xd3_stream
   xd3_output       *enc_heads[4];     /* array of encoded outputs: head of chain */
   xd3_output       *enc_tails[4];     /* array of encoded outputs: tail of chain */
 
-  xd3_iopt_buf      iopt;             /* instruction optimizing buffer */
+  xd3_rlist         iopt_used;        /* instruction optimizing buffer */
+  xd3_rlist         iopt_free;
   xd3_rinst        *iout;             /* next single instruction */
+  xd3_iopt_buflist *iopt_alloc;
 
   const uint8_t    *enc_appheader;    /* application header to encode */
   usize_t            enc_appheadsz;    /* application header size */
@@ -785,6 +788,8 @@ struct _xd3_stream
   xoff_t            l_add;
   xoff_t            l_run;
 
+  usize_t           i_slots_used;
+
 #if XD3_DEBUG
   usize_t            sh_searches;
   usize_t            sh_compares;