Adds a new compression level (-6), makes -1 faster and -9 better.

4 files changed, 142 insertions, 102 deletions

diff --git a/xdelta3/xdelta3-cfgs.h b/xdelta3/xdelta3-cfgs.h
index beb7c48..955ff51 100755
--- a/xdelta3/xdelta3-cfgs.h
+++ b/xdelta3/xdelta3-cfgs.h
@@ -58,16 +58,16 @@
  ******************************************************************************************/
 #if XD3_BUILD_FAST
 #define TEMPLATE      fast
-#define LLOOK         11
-#define LSTEP         7
+#define LLOOK         9
+#define LSTEP         8
 #define SLOOK         4
 #define SCHAIN        5
-#define SLCHAIN       0
+#define SLCHAIN       1
 #define SSMATCH       0
-#define TRYLAZY       0
-#define MAXLAZY       50
-#define LONGENOUGH    0
-#define PROMOTE       1
+#define TRYLAZY       1
+#define MAXLAZY       5
+#define LONGENOUGH    4
+#define PROMOTE       0
 
 #include "xdelta3.c"
 
@@ -89,15 +89,46 @@
  ******************************************************************************************/
 #if XD3_BUILD_SLOW
 #define TEMPLATE      slow
-#define LLOOK         10
+#define LLOOK         9
 #define LSTEP         1
 #define SLOOK         4
-#define SCHAIN        36
-#define SLCHAIN       13
+#define SCHAIN        9
+#define SLCHAIN       5
+#define SSMATCH       0
+#define TRYLAZY       1
+#define MAXLAZY       200
+#define LONGENOUGH    400
+#define PROMOTE       0
+
+#include "xdelta3.c"
+
+#undef  TEMPLATE
+#undef  LLOOK
+#undef  SLOOK
+#undef  LSTEP
+#undef  SCHAIN
+#undef  SLCHAIN
+#undef  SSMATCH
+#undef  TRYLAZY
+#undef  MAXLAZY
+#undef  LONGENOUGH
+#undef  PROMOTE
+#endif
+
+/******************************************************************************************
+ DEFAULT string matcher
+ ******************************************************************************************/
+#if XD3_BUILD_DEFAULT
+#define TEMPLATE      default
+#define LLOOK         9
+#define LSTEP         4
+#define SLOOK         4
+#define SCHAIN        7
+#define SLCHAIN       3
 #define SSMATCH       0
 #define TRYLAZY       1
-#define MAXLAZY       512
-#define LONGENOUGH    256
+#define MAXLAZY       30
+#define LONGENOUGH    20
 #define PROMOTE       0
 
 #include "xdelta3.c"
diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h
index f45ad06..887f368 100755
--- a/xdelta3/xdelta3-main.h
+++ b/xdelta3/xdelta3-main.h
@@ -245,7 +245,7 @@ static int         option_stdout             = 0;
 static int         option_force              = 0;
 static int         option_verbose            = 0;
 static int         option_quiet              = 0;
-static int         option_level              = 5;
+static int         option_level              = 6;
 static int         option_use_appheader      = 1;
 static uint8_t*    option_appheader          = NULL;
 static int         option_use_secondary      = 0;
@@ -2363,6 +2363,7 @@ main_input (xd3_cmd     cmd,
           config.smatcher_soft.promote       = values[9];
         }
       else if (option_level <= 5) { config.smatch_cfg = XD3_SMATCH_FAST; }
+      else if (option_level == 6) { config.smatch_cfg = XD3_SMATCH_DEFAULT; }
       else                        { config.smatch_cfg = XD3_SMATCH_SLOW; }
       break;
 #endif
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index f8c0bc7..4941408 100755
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -473,10 +473,16 @@ XD3_MAKELIST(xd3_rlist, xd3_rinst, link);
 #else
 #define IF_BUILD_SOFT(x)
 #endif
+#if XD3_BUILD_DEFAULT
+#define IF_BUILD_DEFAULT(x) x
+#else
+#define IF_BUILD_DEFAULT(x)
+#endif
 
 IF_BUILD_SOFT(static const xd3_smatcher    __smatcher_soft;)
 IF_BUILD_FAST(static const xd3_smatcher    __smatcher_fast;)
 IF_BUILD_SLOW(static const xd3_smatcher    __smatcher_slow;)
+IF_BUILD_DEFAULT(static const xd3_smatcher    __smatcher_default;)
 
 #if XD3_DEBUG
 #define SMALL_HASH_DEBUG1(s,inp)                                  \
@@ -577,7 +583,6 @@ static usize_t      xd3_sizeof_output (xd3_output *output);
 static int         xd3_source_match_setup (xd3_stream *stream, xoff_t srcpos);
 static int         xd3_source_extend_match (xd3_stream *stream);
 static int         xd3_srcwin_setup (xd3_stream *stream);
-static int         xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point);
 static usize_t     xd3_iopt_last_matched (xd3_stream *stream);
 static int         xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num);
 
@@ -2514,7 +2519,9 @@ xd3_config_stream(xd3_stream *stream,
         break;
       })
 
-      IF_BUILD_SLOW(case XD3_SMATCH_DEFAULT:)
+      IF_BUILD_DEFAULT(case XD3_SMATCH_DEFAULT:
+                    *smatcher = __smatcher_default;
+                    break;)
       IF_BUILD_SLOW(case XD3_SMATCH_SLOW:
                     *smatcher = __smatcher_slow;
                     break;)
@@ -4061,6 +4068,89 @@ xd3_string_match_init (xd3_stream *stream)
   return 0;
 }
 
+/* This function handles the 32/64bit ambiguity -- file positions are 64bit but the hash
+ * table for source-offsets is 32bit. */
+static xoff_t
+xd3_source_cksum_offset(xd3_stream *stream, usize_t low)
+{
+  xoff_t scp = stream->srcwin_cksum_pos;
+  xoff_t s0 = scp >> 32;
+
+  usize_t sr = (usize_t) scp;
+
+  if (s0 == 0) {
+    return low;
+  }
+
+  // This should not be >= because srcwin_cksum_pos is the next position to index
+  if (low > sr) {
+    return (--s0 << 32) | low;
+  }
+
+  return (s0 << 32) | low;
+}
+
+/* This function sets up the stream->src fields srcbase, srclen.  The call is delayed
+ * until these values are needed to encode a copy address.  At this point the decision has
+ * to be made. */
+static int
+xd3_srcwin_setup (xd3_stream *stream)
+{
+  xd3_source *src = stream->src;
+  xoff_t length;
+
+  /* Check the undecided state. */
+  XD3_ASSERT (src->srclen == 0 && src->srcbase == 0);
+
+  /* Avoid repeating this call. */
+  stream->srcwin_decided = 1;
+
+  /* If the stream is flushing, then the iopt buffer was able to contain the complete
+   * encoding.  If no copies were issued no source window is actually needed.  This
+   * prevents the VCDIFF header from including source base/len.  xd3_emit_hdr checks
+   * for srclen == 0. */
+  if (stream->enc_state == ENC_FLUSH && stream->match_maxaddr == 0)
+    {
+      goto done;
+    }
+
+  /* Check for overflow, srclen is usize_t - this can't happen unless XD3_DEFAULT_SRCBACK
+   * and related parameters are extreme - should use smaller windows. */
+  length = stream->match_maxaddr - stream->match_minaddr;
+
+  if (length > (xoff_t) USIZE_T_MAX)
+    {
+      stream->msg = "source window length overflow (not 64bit)";
+      return XD3_INTERNAL;
+    }
+
+  /* If ENC_FLUSH, then we know the exact source window to use because no more copies can
+   * be issued. */
+  if (stream->enc_state == ENC_FLUSH)
+    {
+      src->srcbase = stream->match_minaddr;
+      src->srclen  = (usize_t) length;
+      XD3_ASSERT (src->srclen);
+      goto done;
+    }
+
+  /* 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.  */
+  src->srcbase = stream->match_minaddr;
+  src->srclen  = max ((usize_t) length, stream->avail_in + (stream->avail_in >> 2));
+  if (src->size < src->srcbase + (xoff_t) src->srclen)
+    {
+      /* Could reduce srcbase, as well. */
+      src->srclen = src->size - src->srcbase;
+    }
+
+  XD3_ASSERT (src->srclen);
+ done:
+  /* Set the taroff.  This convenience variable is used even when stream->src == NULL. */
+  stream->taroff = src->srclen;
+  return 0;
+}
+
 /* Called at every entrance to the string-match loop and each time
  * stream->input_position the value returned as *next_move_point.
  * This function computes more source checksums to advance the window. */
@@ -4138,14 +4228,12 @@ 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: This block needs to be included in the template pass... duh.
-       */
-
       /* Note: I experimented with rewriting this block to use LARGE_CKSUM_UPDATE()
        * instead of recalculating the cksum every N bytes.  It seemed to make performance
-       * worse. */
+       * worse (except obviously for step == 1, not worth extra complexity) */
       while (blkoff <= onblk)
         {
+          /* It's a big win to have the compiler optimize this loop w/ fi. */
           uint32_t cksum = xd3_lcksum (stream->src->curblk + blkoff, stream->smatcher.large_look);
           usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum);
 
@@ -4167,89 +4255,6 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
   return 0;
 }
 
-/* This function handles the 32/64bit ambiguity -- file positions are 64bit but the hash
- * table for source-offsets is 32bit. */
-static xoff_t
-xd3_source_cksum_offset(xd3_stream *stream, usize_t low)
-{
-  xoff_t scp = stream->srcwin_cksum_pos;
-  xoff_t s0 = scp >> 32;
-
-  usize_t sr = (usize_t) scp;
-
-  if (s0 == 0) {
-    return low;
-  }
-
-  // This should not be >= because srcwin_cksum_pos is the next position to index
-  if (low > sr) {
-    return (--s0 << 32) | low;
-  }
-
-  return (s0 << 32) | low;
-}
-
-/* This function sets up the stream->src fields srcbase, srclen.  The call is delayed
- * until these values are needed to encode a copy address.  At this point the decision has
- * to be made. */
-static int
-xd3_srcwin_setup (xd3_stream *stream)
-{
-  xd3_source *src = stream->src;
-  xoff_t length;
-
-  /* Check the undecided state. */
-  XD3_ASSERT (src->srclen == 0 && src->srcbase == 0);
-
-  /* Avoid repeating this call. */
-  stream->srcwin_decided = 1;
-
-  /* If the stream is flushing, then the iopt buffer was able to contain the complete
-   * encoding.  If no copies were issued no source window is actually needed.  This
-   * prevents the VCDIFF header from including source base/len.  xd3_emit_hdr checks
-   * for srclen == 0. */
-  if (stream->enc_state == ENC_FLUSH && stream->match_maxaddr == 0)
-    {
-      goto done;
-    }
-
-  /* Check for overflow, srclen is usize_t - this can't happen unless XD3_DEFAULT_SRCBACK
-   * and related parameters are extreme - should use smaller windows. */
-  length = stream->match_maxaddr - stream->match_minaddr;
-
-  if (length > (xoff_t) USIZE_T_MAX)
-    {
-      stream->msg = "source window length overflow (not 64bit)";
-      return XD3_INTERNAL;
-    }
-
-  /* If ENC_FLUSH, then we know the exact source window to use because no more copies can
-   * be issued. */
-  if (stream->enc_state == ENC_FLUSH)
-    {
-      src->srcbase = stream->match_minaddr;
-      src->srclen  = (usize_t) length;
-      XD3_ASSERT (src->srclen);
-      goto done;
-    }
-
-  /* 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.  */
-  src->srcbase = stream->match_minaddr;
-  src->srclen  = max ((usize_t) length, stream->avail_in + (stream->avail_in >> 2));
-  if (src->size < src->srcbase + (xoff_t) src->srclen)
-    {
-      /* Could reduce srcbase, as well. */
-      src->srclen = src->size - src->srcbase;
-    }
-
-  XD3_ASSERT (src->srclen);
- done:
-  /* Set the taroff.  This convenience variable is used even when stream->src == NULL. */
-  stream->taroff = src->srclen;
-  return 0;
-}
-
 /* Sets the bounding region for a newly discovered source match, prior to calling
  * xd3_source_extend_match().  This sets the match_maxfwd, match_maxback variables.  Note:
  * srcpos is an absolute position (xoff_t) but the match_maxfwd, match_maxback variables
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h
index ca4c79a..6bc6d37 100755
--- a/xdelta3/xdelta3.h
+++ b/xdelta3/xdelta3.h
@@ -176,6 +176,9 @@ typedef uint32_t xoff_t;
 #ifndef XD3_BUILD_SOFT
 #define XD3_BUILD_SOFT 1
 #endif
+#ifndef XD3_BUILD_DEFAULT
+#define XD3_BUILD_DEFAULT 1
+#endif
 
 #if XD3_DEBUG
 #include <stdio.h>