Cleanup the calculation of -B and -W, get the minimum source buffer size

(-B) to work, enforce a maximum input window size (-W).  Add some 
debugging output. Correct a bug in setting the large hashtable size. 
I've noticed some odd behavior with the -W setting, more tests to do.

5 files changed, 105 insertions, 138 deletions

diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h
index d33ccd3..0a2592e 100755
--- a/xdelta3/xdelta3-main.h
+++ b/xdelta3/xdelta3-main.h
@@ -234,6 +234,9 @@ struct _main_blklru
   main_blklru_list  link;
 };
 
+#define LRU_SIZE 32U
+#define XD3_MINSRCWINSZ XD3_ALLOCSIZE
+
 /* ... represented as a list (no cache index). */
 XD3_MAKELIST(main_blklru_list,main_blklru,link);
 
@@ -402,7 +405,7 @@ main_malloc1 (usize_t size)
 {
   void* r = malloc (size);
   if (r == NULL) { XPR(NT "malloc: %s\n", xd3_mainerror (ENOMEM)); }
-  else if (option_verbose > 2) { XPR(NT "malloc: %u: %p\n", size, r); }
+  else if (option_verbose > 3) { XPR(NT "malloc: %u: %p\n", size, r); }
   return r;
 }
 
@@ -425,7 +428,7 @@ main_alloc (void   *opaque,
 static void
 main_free1 (void *opaque, void *ptr)
 {
-  if (option_verbose > 2) { XPR(NT "free: %p\n", ptr); }
+  if (option_verbose > 3) { XPR(NT "free: %p\n", ptr); }
   free (ptr);
 }
 
@@ -589,16 +592,25 @@ main_strtoxoff (const char* s, xoff_t *xo, char which)
 }
 
 static int
-main_atou (const char* arg, usize_t *xo, usize_t low, char which)
+main_atou (const char* arg, usize_t *xo, usize_t low, usize_t high, char which)
 {
   xoff_t x;
   int ret;
 
   if ((ret = main_strtoxoff (arg, & x, which))) { return ret; }
 
-  if (x > USIZE_T_MAX || x < low)
+  if (x < low)
+    {
+      XPR(NT "-%c: minimum value: %u\n", which, low);
+      return EXIT_FAILURE;
+    }
+  if (high == 0)
+    {
+      high = USIZE_T_MAX;
+    }
+  if (x > high)
     {
-      XPR(NT "-%c: minimum value: %u", which, low);
+      XPR(NT "-%c: maximum value: %u\n", which, high);
       return EXIT_FAILURE;
     }
   (*xo) = (usize_t)x;
@@ -863,7 +875,7 @@ main_file_read (main_file   *ifile,
     }
   else
     {
-      if (option_verbose > 2) { XPR(NT "main read: %s: %u\n", ifile->filename, (*nread)); }
+      if (option_verbose > 3) { XPR(NT "main read: %s: %u\n", ifile->filename, (*nread)); }
       ifile->nread += (*nread);
     }
 
@@ -903,7 +915,7 @@ main_file_write (main_file *ofile, uint8_t *buf, usize_t size, const char *msg)
     }
   else
     {
-      if (option_verbose > 2) { XPR(NT "main write: %s: %u\n", ofile->filename, size); }
+      if (option_verbose > 3) { XPR(NT "main write: %s: %u\n", ofile->filename, size); }
       ofile->nwrite += size;
     }
 
@@ -2035,16 +2047,16 @@ main_set_source (xd3_stream *stream, int cmd, main_file *sfile, xd3_source *sour
   else
     {
       /* Minimum size check */
-      option_srcwinsz = max(option_srcwinsz, XD3_ALLOCSIZE);
+      option_srcwinsz = max(option_srcwinsz, XD3_MINSRCWINSZ);
 
       if (!option_srcwinsz_set)
         {
           /* If the flag was not set, scale srcwinsz up to 64MB. */
-          option_srcwinsz = min(1ULL<<26, source->size);
+          option_srcwinsz = min((xoff_t) XD3_DEFAULT_SRCWINSZ, source->size);
         }
 
-      source->blksize = (option_srcwinsz / 32) & ~(XD3_ALLOCSIZE - 1);;
-      lru_size = 32;
+      source->blksize = (option_srcwinsz / LRU_SIZE);
+      lru_size = LRU_SIZE;
     }
 
   main_blklru_list_init (& lru_list);
@@ -2398,11 +2410,6 @@ main_input (xd3_cmd     cmd,
       return EXIT_FAILURE;
     }
 
-  if (option_verbose > 1)
-    {
-      XPR(NT "scanner configuration: %s\n", stream.smatcher.name); 
-    }
-
   /* This times each window. */
   get_millisecs_since ();
 
@@ -2637,6 +2644,24 @@ done:
       return EXIT_FAILURE;
     }
 
+  if (option_verbose > 1)
+    {
+      XPR(NT "scanner configuration: %s\n", stream.smatcher.name);
+      XPR(NT "target hash table size: %u\n", stream.small_hash.size);
+      if (sfile->filename != NULL)
+        {
+          XPR(NT "source hash table size: %u\n", stream.large_hash.size);
+        }
+    }
+
+  if (option_verbose > 2)
+    {
+      XPR(NT "source copies: %"Q"u (%"Q"u bytes)\n", stream.n_scpy, stream.l_scpy);
+      XPR(NT "target copies: %"Q"u (%"Q"u bytes)\n", stream.n_tcpy, stream.l_tcpy);
+      XPR(NT "adds: %"Q"u (%"Q"u bytes)\n", stream.n_add, stream.l_add);
+      XPR(NT "runs: %"Q"u (%"Q"u bytes)\n", stream.n_run, stream.l_run);
+    }
+
   xd3_free_stream (& stream);
 
   if (option_verbose)
@@ -2870,7 +2895,10 @@ main (int argc, char **argv)
           /* only set profile count once, since... */
           if (option_profile_cnt == 0)
             {
-              if ((ret = main_atou(my_optarg, (usize_t*) & option_profile_cnt, 0, 'P'))) { goto exit; }
+              if ((ret = main_atou(my_optarg, (usize_t*) & option_profile_cnt, 0, 0, 'P')))
+                {
+                  goto exit;
+                }
 
               if (option_profile_cnt <= 0)
                 {
@@ -2891,12 +2919,15 @@ main (int argc, char **argv)
                   else { option_appheader = (uint8_t*) my_optarg; } break;
         case 'B':
           option_srcwinsz_set = 1;
-          if ((ret = main_atou (my_optarg, & option_srcwinsz, XD3_ALLOCSIZE, 'B')))
+          if ((ret = main_atou (my_optarg, & option_srcwinsz, XD3_MINSRCWINSZ,
+                                0, 'B')))
             {
               goto exit;
             }
           break;
-        case 'W': if ((ret = main_atou (my_optarg, & option_winsize, XD3_ALLOCSIZE, 'W')))
+        case 'W':
+          if ((ret = main_atou (my_optarg, & option_winsize, XD3_ALLOCSIZE,
+                                XD3_HARDMAXWINSIZE, 'W')))
           {
             goto exit;
           }
diff --git a/xdelta3/xdelta3-regtest.py b/xdelta3/xdelta3-regtest.py
index fdebffe..520ec81 100755
--- a/xdelta3/xdelta3-regtest.py
+++ b/xdelta3/xdelta3-regtest.py
@@ -559,34 +559,27 @@ def ReportSpeed(L,tr,desc):
     print '%s 0-run length %u: dsize %u: time %.3f ms: encode %.0f B/sec: in %ux%u trials' % \
           (desc, L, tr.r1.dsize, tr.time.mean * 1000.0, ((L+tr.r1.dsize) / tr.time.mean), tr.trials, tr.reps)
 
-def BigFileRuns(rcsf):
-    while 1:
-
-        rand = random.Random()
-        f1 = open(TMPDIR + "/big.1", "w")
-        f2 = open(TMPDIR + "/big.2", "w")
-        f1sz = 0
-        f2sz = 0
-        for file in rcsf.rcsfiles:
-            if file.versions < 2:
-                continue
-            r1 = 0
-            r2 = 0
-            while r1 == r2:
-                r1 = rand.randint(0, len(file.versions) - 1)
-                r2 = rand.randint(0, len(file.versions) - 1)
-            f1sz += file.AppendVersion(f1, r1)
-            f2sz += file.AppendVersion(f2, r2)
-
-        f1.close()
-        f2.close()
-
-        print "Test input sizes: %d %d" % (f1sz, f2sz)
-
-        BigFileRun(TMPDIR + "/big.1",
-                   TMPDIR + "/big.2")
-        #continue
-    #end
+def MakeBigFiles(rcsf):
+    rand = random.Random()
+    f1 = open(TMPDIR + "/big.1", "w")
+    f2 = open(TMPDIR + "/big.2", "w")
+    f1sz = 0
+    f2sz = 0
+    for file in rcsf.rcsfiles:
+        if file.versions < 2:
+            continue
+        r1 = 0
+        r2 = 0
+        while r1 == r2:
+            r1 = rand.randint(0, len(file.versions) - 1)
+            r2 = rand.randint(0, len(file.versions) - 1)
+        f1sz += file.AppendVersion(f1, r1)
+        f2sz += file.AppendVersion(f2, r2)
+
+    f1.close()
+    f2.close()
+    return (TMPDIR + "/big.1",
+            TMPDIR + "/big.2")
 
 def BigFileRun(f1, f2):
                    
@@ -616,12 +609,12 @@ def BigFileRun(f1, f2):
 def RandomBigRun(f1, f2):
 
     input_ranges = [
-        (7, 13, 'large_look'),
-        (1, 50, 'large_step'),
-        (4, 6, 'small_look'),
-        (1, 10, 'small_chain'),
-        (1, 5, 'small_lchain'),
-        (0, 0, 'ssmatch'),
+        (7, 9, 'large_look'),
+        (1, 10, 'large_step'),
+        (4, 5, 'small_look'),
+        (1, 20, 'small_chain'),
+        (1, 10, 'small_lchain'),
+        (0, 1, 'ssmatch'),
         (0, 1, 'trylazy'),
         (1, 32, 'max_lazy'),
         (1, 64, 'long_enough'),
@@ -656,6 +649,8 @@ def RandomBigRun(f1, f2):
            result.time.mean,
            result.trials)
 
+    return (config, result.r1.dsize, result.time.mean)
+
 def RunSpeed():
     for L in Decimals(MAX_RUN):
         SetFileSize(RUNFILE, L)
@@ -670,8 +665,6 @@ if __name__ == "__main__":
         #rcsf = Test()
         #rcsf.PairsByDate(Xdelta3Pair())
         #RunSpeed()
-        #BigFileRuns(rcsf)
-        #BigFileRun("/tmp/big.1", "/tmp/big.2")
         while 1:
             try:
                 RandomBigRun("/tmp/big.1", "/tmp/big.2")
diff --git a/xdelta3/xdelta3-test.h b/xdelta3/xdelta3-test.h
index 1694a6d..dc67848 100755
--- a/xdelta3/xdelta3-test.h
+++ b/xdelta3/xdelta3-test.h
@@ -1908,7 +1908,7 @@ test_identical_behavior (xd3_stream *stream, int ignore)
   if (memcmp (rec, buf, IDB_TGTSZ) != 0) { stream->msg = "wrong data reconstruction"; goto fail; }
 
   /* Check that there was one copy per window. */
-  IF_DEBUG (if (stream->n_cpy != IDB_WINCNT ||
+  IF_DEBUG (if (stream->n_scpy != IDB_WINCNT ||
                 stream->n_add != 0 ||
                 stream->n_run != 0) { stream->msg = "wrong copy count"; goto fail; });
 
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index 9d6c3b6..14a3c08 100755
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -1970,46 +1970,6 @@ xd3_sizeof_uint64_t (uint64_t num)
 #endif
 
 /******************************************************************************************
- Debug instruction statistics
- ******************************************************************************************/
-
-#if XD3_DEBUG
-static void
-xd3_count_inst (xd3_stream *stream, uint code)
-{
-  IF_DEBUG1 ({
-    if (stream->i_freqs == NULL &&
-        (stream->i_freqs = xd3_alloc0 (stream, sizeof (stream->i_freqs[0]), 256)) == NULL) { abort (); }
-
-    stream->i_freqs[code] += 1;
-  });
-  stream->n_ibytes += 1;
-}
-
-static void
-xd3_count_mode (xd3_stream *stream, uint mode)
-{
-  IF_DEBUG1 ({
-  if (stream->i_modes == NULL &&
-      (stream->i_modes = xd3_alloc0 (stream, sizeof (stream->i_modes[0]), TOTAL_MODES (stream))) == NULL) { abort (); }
-  stream->i_modes[mode] += 1;
-  });
-}
-
-static void
-xd3_count_size (xd3_stream *stream, usize_t size)
-{
-  IF_DEBUG1({
-    if (stream->i_sizes == NULL &&
-        (stream->i_sizes = xd3_alloc0 (stream, sizeof (stream->i_sizes[0]), 64)) == NULL) { abort (); }
-
-    if (size < 64) { stream->i_sizes[size] += 1; }
-  });
-  stream->n_sbytes += xd3_sizeof_size (size);
-}
-#endif
-
-/******************************************************************************************
  Address cache stuff
  ******************************************************************************************/
 
@@ -2114,8 +2074,6 @@ xd3_encode_address (xd3_stream *stream, usize_t addr, usize_t here, uint8_t* mod
 
   xd3_update_cache (acache, addr);
 
-  IF_DEBUG (xd3_count_mode (stream, bestm));
-
   (*mode) += bestm;
 
   return 0;
@@ -2368,10 +2326,6 @@ xd3_free_stream (xd3_stream *stream)
     }
 #endif
 
-  IF_DEBUG (xd3_free (stream, stream->i_freqs));
-  IF_DEBUG (xd3_free (stream, stream->i_modes));
-  IF_DEBUG (xd3_free (stream, stream->i_sizes));
-
   XD3_ASSERT (stream->alloc_cnt == stream->free_cnt);
 
   memset (stream, 0, sizeof (xd3_stream));
@@ -2768,16 +2722,22 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst)
                 XD3_ASSERT (inst->addr >= src->srcbase);
                 XD3_ASSERT (inst->addr + inst->size <= src->srcbase + src->srclen);
                 addr = (inst->addr - src->srcbase);
+                stream->n_scpy += 1;
+                stream->l_scpy += inst->size;
               }
             else
               {
                 /* with source window: target copy address is offset by taroff. */
                 addr = stream->taroff + (usize_t) inst->addr;
+                stream->n_tcpy += 1;
+                stream->l_tcpy += inst->size;
               }
           }
         else
           {
             addr = (usize_t) inst->addr;
+            stream->n_tcpy += 1;
+            stream->l_tcpy += inst->size;
           }
 
         XD3_ASSERT (inst->size >= MIN_MATCH);
@@ -2788,9 +2748,6 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst)
             return ret;
           }
 
-        IF_DEBUG (stream->n_cpy += 1);
-        IF_DEBUG (stream->l_cpy += inst->size);
-
         IF_DEBUG1 ({
           static int cnt;
           P(RINT "[iopt copy:%d] pos %"Q"u-%"Q"u addr %"Q"u-%"Q"u size %u\n",
@@ -2807,9 +2764,8 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst)
 
         if ((ret = xd3_emit_byte (stream, & DATA_TAIL (stream), inst->xtra))) { return ret; }
 
-        IF_DEBUG (stream->n_run += 1);
-        IF_DEBUG (stream->l_run += inst->size);
-        IF_DEBUG (stream->n_dbytes += 1);
+        stream->n_run += 1;
+        stream->l_run += inst->size;
 
         IF_DEBUG1 ({
           static int cnt;
@@ -2822,9 +2778,8 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst)
         if ((ret = xd3_emit_bytes (stream, & DATA_TAIL (stream),
                                    stream->next_in + inst->pos, inst->size))) { return ret; }
 
-        IF_DEBUG (stream->n_add += 1);
-        IF_DEBUG (stream->l_add += inst->size);
-        IF_DEBUG (stream->n_dbytes += inst->size);
+        stream->n_add += 1;
+        stream->l_add += inst->size;
 
         IF_DEBUG1 ({
           static int cnt;
@@ -3196,12 +3151,8 @@ xd3_emit_single (xd3_stream *stream, xd3_rinst *single, uint code)
   if (has_size)
     {
       if ((ret = xd3_emit_size (stream, & INST_TAIL (stream), single->size))) { return ret; }
-
-      IF_DEBUG (xd3_count_size (stream, single->size));
     }
 
-  IF_DEBUG (xd3_count_inst (stream, code));
-
   return 0;
 }
 
@@ -3225,8 +3176,6 @@ xd3_emit_double (xd3_stream *stream, xd3_rinst *first, xd3_rinst *second, uint c
                second->size,
                code));
 
-  IF_DEBUG (xd3_count_inst (stream, code));
-
   return 0;
 }
 
@@ -3496,23 +3445,22 @@ xd3_encode_init (xd3_stream *stream)
   // TODO: experiments have to be done!!!
   if (large_comp)
     {
-      usize_t hash_values = (stream->srcwin_maxsz / stream->smatcher.large_look);
+      usize_t hash_values = (stream->srcwin_maxsz / stream->smatcher.large_step);
 
       xd3_size_hashtable (stream,
                           hash_values,
                           & stream->large_hash);
-      IF_DEBUG1 (P(RINT "[encode_init] large hash %u slots\n", hash_values));
     }
 
   if (small_comp)
     {
       /* Hard-coded, keeps table small because small matches become inefficient. */
-      usize_t hash_values = min(stream->winsize / stream->smatcher.small_look, 65536U);
+      // TODO: verify this
+      usize_t hash_values = min(stream->winsize, 65536U);
 
       xd3_size_hashtable (stream,
                           hash_values,
                           & stream->small_hash);
-      IF_DEBUG1 (P(RINT "[encode_init] small hash %u slots\n", hash_values));
     }
 
   for (i = 0; i < ENC_SECTS; i += 1)
@@ -4040,6 +3988,7 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
       diff = logical_input_cksum_pos - stream->srcwin_cksum_pos;
       onblk = min(blkoff + diff, onblk);
 
+      // TODO: is this inefficient for large_step < large_look?
       while (blkoff <= onblk)
         {
           uint32_t cksum = xd3_lcksum (stream->src->curblk + blkoff, stream->smatcher.large_look);
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h
index 2ae1273..0c5bd43 100755
--- a/xdelta3/xdelta3.h
+++ b/xdelta3/xdelta3.h
@@ -45,7 +45,7 @@
 
 /* Default total size of the source window used in xdelta3-main.h */
 #ifndef XD3_DEFAULT_SRCWINSZ
-#define XD3_DEFAULT_SRCWINSZ (1U << 23)
+#define XD3_DEFAULT_SRCWINSZ (1U << 26)
 #endif
 
 /* When Xdelta requests a memory allocation for certain buffers, it rounds up to units of
@@ -61,7 +61,7 @@
  * without a copy window will require 3 bytes to encode (7 bits per byte, HERE and SAME
  * modes making every address within half the window away. */
 #ifndef XD3_HARDMAXWINSIZE
-#define XD3_HARDMAXWINSIZE (1U<<23)
+#define XD3_HARDMAXWINSIZE (1U<<24)
 #endif
 
 /* The XD3_NODECOMPRESSSIZE parameter tells the xdelta main routine not to try to
@@ -774,27 +774,21 @@ struct _xd3_stream
   xd3_sec_stream     *sec_stream_i;
   xd3_sec_stream     *sec_stream_a;
 
-#if XD3_DEBUG
   /* statistics */
-  usize_t            n_cpy;
-  usize_t            n_add;
-  usize_t            n_run;
-
-  usize_t            n_ibytes;
-  usize_t            n_sbytes;
-  usize_t            n_dbytes;
+  xoff_t            n_scpy;
+  xoff_t            n_tcpy;
+  xoff_t            n_add;
+  xoff_t            n_run;
 
-  usize_t            l_cpy;
-  usize_t            l_add;
-  usize_t            l_run;
+  xoff_t            l_scpy;
+  xoff_t            l_tcpy;
+  xoff_t            l_add;
+  xoff_t            l_run;
 
+#if XD3_DEBUG
   usize_t            sh_searches;
   usize_t            sh_compares;
 
-  usize_t           *i_freqs;
-  usize_t           *i_modes;
-  usize_t           *i_sizes;
-
   usize_t            large_ckcnt;
 
   /* memory usage */