8 files changed, 173 insertions, 395 deletions

diff --git a/xdelta3/examples/small_page_test.c b/xdelta3/examples/small_page_test.c
index 714fd6e..8a4532b 100755
--- a/xdelta3/examples/small_page_test.c
+++ b/xdelta3/examples/small_page_test.c
@@ -12,10 +12,6 @@
 // SPACE_MAX of 32K is sufficient for most inputs with XD3_COMPLEVEL_1
 // XD3_COMPLEVEL_9 requires about 4x more space than XD3_COMPLEVEL_1
 
-// TODO: experimental PROMOTE code in the encoder is using 16 bytes
-// per entry in a table, where 4 bytes are sufficient w/o this
-// (unimpressive) feature. Remove PROMOTE code.
-
 #include "xdelta3.h"
 #include "xdelta3.c"
 
diff --git a/xdelta3/xdelta3-cfgs.h b/xdelta3/xdelta3-cfgs.h
index c48df9f..1474d12 100644
--- a/xdelta3/xdelta3-cfgs.h
+++ b/xdelta3/xdelta3-cfgs.h
@@ -28,11 +28,8 @@
 #define SLOOK         stream->smatcher.small_look
 #define SCHAIN        stream->smatcher.small_chain
 #define SLCHAIN       stream->smatcher.small_lchain
-#define SSMATCH       stream->smatcher.ssmatch
-#define TRYLAZY       stream->smatcher.try_lazy
 #define MAXLAZY       stream->smatcher.max_lazy
 #define LONGENOUGH    stream->smatcher.long_enough
-#define PROMOTE       stream->smatcher.promote
 
 #define SOFTCFG 1
 #include "xdelta3.c"
@@ -44,11 +41,8 @@
 #undef  LSTEP
 #undef  SCHAIN
 #undef  SLCHAIN
-#undef  SSMATCH
-#undef  TRYLAZY
 #undef  MAXLAZY
 #undef  LONGENOUGH
-#undef  PROMOTE
 #endif
 
 #define SOFTCFG 0
@@ -63,11 +57,8 @@
 #define SLOOK         4
 #define SCHAIN        1
 #define SLCHAIN       1
-#define SSMATCH       0
-#define TRYLAZY       1
 #define MAXLAZY       18
 #define LONGENOUGH    18
-#define PROMOTE       0
 
 #include "xdelta3.c"
 
@@ -77,11 +68,8 @@
 #undef  LSTEP
 #undef  SCHAIN
 #undef  SLCHAIN
-#undef  SSMATCH
-#undef  TRYLAZY
 #undef  MAXLAZY
 #undef  LONGENOUGH
-#undef  PROMOTE
 #endif
 
 /******************************************************************************************
@@ -94,11 +82,8 @@
 #define SLOOK         4
 #define SCHAIN        4
 #define SLCHAIN       1
-#define SSMATCH       0
-#define TRYLAZY       1
 #define MAXLAZY       18
 #define LONGENOUGH    35
-#define PROMOTE       0
 
 #include "xdelta3.c"
 
@@ -108,11 +93,8 @@
 #undef  LSTEP
 #undef  SCHAIN
 #undef  SLCHAIN
-#undef  SSMATCH
-#undef  TRYLAZY
 #undef  MAXLAZY
 #undef  LONGENOUGH
-#undef  PROMOTE
 #endif
 
 /******************************************************************************************
@@ -125,11 +107,8 @@
 #define SLOOK         4
 #define SCHAIN        44
 #define SLCHAIN       13
-#define SSMATCH       0
-#define TRYLAZY       1
 #define MAXLAZY       90
 #define LONGENOUGH    70
-#define PROMOTE       0
 
 #include "xdelta3.c"
 
@@ -139,11 +118,8 @@
 #undef  LSTEP
 #undef  SCHAIN
 #undef  SLCHAIN
-#undef  SSMATCH
-#undef  TRYLAZY
 #undef  MAXLAZY
 #undef  LONGENOUGH
-#undef  PROMOTE
 #endif
 
 /******************************************************************************************
@@ -156,11 +132,8 @@
 #define SLOOK         4
 #define SCHAIN        8
 #define SLCHAIN       2
-#define SSMATCH       0
-#define TRYLAZY       1
 #define MAXLAZY       36
 #define LONGENOUGH    70
-#define PROMOTE       0
 
 #include "xdelta3.c"
 
@@ -170,9 +143,6 @@
 #undef  LSTEP
 #undef  SCHAIN
 #undef  SLCHAIN
-#undef  SSMATCH
-#undef  TRYLAZY
 #undef  MAXLAZY
 #undef  LONGENOUGH
-#undef  PROMOTE
 #endif
diff --git a/xdelta3/xdelta3-main.h b/xdelta3/xdelta3-main.h
index 3b7d11a..d33fd57 100644
--- a/xdelta3/xdelta3-main.h
+++ b/xdelta3/xdelta3-main.h
@@ -84,7 +84,7 @@ const char* xd3_mainerror(int err_num);
 #define PRINTHDR_SPECIAL -4378291
 
 /* The number of soft-config variables.  */
-#define XD3_SOFTCFG_VARCNT 10
+#define XD3_SOFTCFG_VARCNT 7
 
 /* this is used as in XPR(NT XD3_LIB_ERRMSG (stream, ret)) to print an error message
  * from the library. */
@@ -338,7 +338,6 @@ main_config (void)
 {
   main_version ();
 
-  /* TODO: This needs cleaning up */
   P(RINT "EXTERNAL_COMPRESSION=%d\n", EXTERNAL_COMPRESSION);
   P(RINT "GENERIC_ENCODE_TABLES=%d\n", GENERIC_ENCODE_TABLES);
   P(RINT "GENERIC_ENCODE_TABLES_COMPUTE=%d\n", GENERIC_ENCODE_TABLES_COMPUTE);
@@ -367,7 +366,6 @@ main_config (void)
 static void
 reset_defaults(void)
 {
-  // TODO: this is dumb, use an object
   option_stdout = 0;
   option_force = 0;
   option_verbose = 0;
@@ -720,20 +718,22 @@ main_file_close (main_file *xfile)
 static void
 main_file_cleanup (main_file *xfile)
 {
-  /* TODO: inconsistent code style here */
-  if (main_file_isopen (xfile)) {
-    main_file_close (xfile);
-  }
+  if (main_file_isopen (xfile))
+    {
+      main_file_close (xfile);
+    }
 
-  if (xfile->snprintf_buf != NULL) {
-    main_free(xfile->snprintf_buf);
-    xfile->snprintf_buf = NULL;
-  }
+  if (xfile->snprintf_buf != NULL)
+    {
+      main_free(xfile->snprintf_buf);
+      xfile->snprintf_buf = NULL;
+    }
 
-  if (xfile->filename_copy != NULL) {
-    main_free(xfile->filename_copy);
-    xfile->filename_copy = NULL;
-  }
+  if (xfile->filename_copy != NULL)
+    {
+      main_free(xfile->filename_copy);
+      xfile->filename_copy = NULL;
+    }
 }
 
 static int
@@ -795,7 +795,6 @@ main_file_stat (main_file *xfile, xoff_t *size, int err_ifnoseek)
   } else {
       *size = li.QuadPart;
   }
-  // TODO: check err_ifnoseek
 #else
   struct stat sbuf;
   if (fstat (XFNO (xfile), & sbuf) < 0)
@@ -2457,11 +2456,8 @@ main_input (xd3_cmd     cmd,
           config.smatcher_soft.small_look    = values[2];
           config.smatcher_soft.small_chain   = values[3];
           config.smatcher_soft.small_lchain  = values[4];
-          config.smatcher_soft.ssmatch       = values[5];
-          config.smatcher_soft.try_lazy      = values[6];
-          config.smatcher_soft.max_lazy      = values[7];
-          config.smatcher_soft.long_enough   = values[8];
-          config.smatcher_soft.promote       = values[9];
+          config.smatcher_soft.max_lazy      = values[5];
+          config.smatcher_soft.long_enough   = values[6];
         }
       else
         {
@@ -2604,7 +2600,7 @@ main_input (xd3_cmd     cmd,
                   }
 
                 /* Check if we have no source name and need one. */
-                /* TODO: this doesn't fire due to cpyblocks_ calculation check */
+                /* TODO: this doesn't fire due to cpyblocks_ calculation check? */
                 if (need_src && ! recv_src)
                   {
                     XPR(NT "input requires a source file, use -s\n");
diff --git a/xdelta3/xdelta3-regtest.py b/xdelta3/xdelta3-regtest.py
index 1248584..5c7b6bf 100755
--- a/xdelta3/xdelta3-regtest.py
+++ b/xdelta3/xdelta3-regtest.py
@@ -16,13 +16,21 @@
 #  along with this program; if not, write to the Free Software
 #  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
-# TODO: Test 1.5 vs. greedy
-# TODO: Compare w/ bsdiff and generate more summary
+# TODO: test 1.5 vs. greedy
+# TODO: generate a graph
 
 import os, sys, math, re, time, types, array, random
 import xdelta3main
 import xdelta3
 
+#RCSDIR = '/mnt/polaroid/Polaroid/orbit_linux/home/jmacd/PRCS'
+RCSDIR = '/tmp/PRCS_read_copy/prcs'
+SAMPLEDIR = "/tmp/WESNOTH_tmp/diff"
+
+#RCSDIR = 'G:/jmacd/PRCS/prcs/b'
+#SAMPLEDIR = "C:/sample_data/Wesnoth/tar"
+
+#
 MIN_SIZE       = 0
 
 TIME_TOO_SHORT = 0.050
@@ -32,7 +40,7 @@ MIN_TRIALS     = 3
 MAX_TRIALS     = 15
 
 # 10 = fast 1.5 = slow
-MIN_STDDEV_PCT = 10
+MIN_STDDEV_PCT = 1.5
 
 # How many results per round
 MAX_RESULTS = 4
@@ -48,73 +56,76 @@ MIN_RUN = 1000 * 1000 * 1
 MAX_RUN = 1000 * 1000 * 10
 
 # Testwide defaults
-ALL_ARGS = [ '-f' ]
+ALL_ARGS = [
+    # -v
+    ]
 
-# The first 10 args go to -C
-SOFT_CONFIG_CNT = 10
+# The first 7 args go to -C
+SOFT_CONFIG_CNT = 7
 
 CONFIG_ORDER = [ 'large_look',
                  'large_step',
                  'small_look',
                  'small_chain',
                  'small_lchain',
-                 'ssmatch',
-                 'trylazy',
                  'max_lazy',
                  'long_enough',
-                 'promote',
+
+                 # > SOFT_CONFIG_CNT
+                 'nocompress',
                  'winsize',
                  'srcwinsize',
                  'sprevsz',
                  'iopt',
-
-                 # TODO: nocompress, djw (boolean flags)
+                 'djw',
                  ]
 
 CONFIG_ARGMAP = {
-    'winsize' : '-W',
+    'winsize'    : '-W',
     'srcwinsize' : '-B',
-    'sprevsz' : '-P',
-    'iopt' : '-I',
+    'sprevsz'    : '-P',
+    'iopt'       : '-I',
+    'nocompress' : '-N',
+    'djw'        : '-Sdjw'
     }
 
 def INPUT_SPEC(rand):
     return {
-    # computational costs
-    'large_look' : lambda d: rand.choice([9]),
-    'large_step' : lambda d: rand.choice([15]),
 
-    'small_chain'  : lambda d: rand.choice([1]),
-    'small_lchain' : lambda d: rand.choice([1]),
+    # Time/space costs.
 
+    # -C 1,2,3,4,5,6,7
+    'large_look' : lambda d: rand.choice([9]),
+    'large_step' : lambda d: rand.choice([3, 15]),
+    'small_chain'  : lambda d: rand.choice([1, 2]),
+    'small_lchain' : lambda d: rand.choice([1]),
     'max_lazy'     : lambda d: rand.choice([18]),
     'long_enough'  : lambda d: rand.choice([18]),
-
     'small_look'   : lambda d: rand.choice([4]),
-    'ssmatch'      : lambda d: rand.choice([0]),
 
-    'promote'      : lambda d: rand.choice([0]),
+    # -N
+    'nocompress'   : lambda d: rand.choice(['false']),
 
-    'trylazy'      : lambda d: rand.choice([1]),
+    # -S djw
+    'djw'          : lambda d: rand.choice(['false']),
 
-    # memory costs
-    'iopt'         : lambda d: 0,  # unlimited
+    # Mmemory costs.
 
+    # -W
     'winsize'      : lambda d: 8 * (1<<20),
+
+    # -B
     'srcwinsize'   : lambda d: 64 * (1<<20),
 
-    'sprevsz'      : lambda d: 1 * (1<<18), # only powers of two
-    }
+    # -I 0 is unlimited
+    'iopt'         : lambda d: 0,
 
-#
-#
-#RCSDIR = '/mnt/polaroid/Polaroid/orbit_linux/home/jmacd/PRCS'
-RCSDIR = '/tmp/PRCS_read_copy/prcs'
-SAMPLEDIR = "/tmp/WESNOTH_tmp/tar"
-
-#RCSDIR = 'G:/jmacd/PRCS/prcs/b'
-#SAMPLEDIR = "C:/sample_data/Wesnoth/tar"
+    # -P only powers of two
+    'sprevsz'      : lambda d: rand.choice([x * (1<<16) for x in [4]]),
+  }
+#end
 
+#
 TMPDIR = '/tmp/xd3regtest.%d' % os.getpid()
 
 RUNFILE = os.path.join(TMPDIR, 'run')
@@ -139,7 +150,7 @@ RE_HDRSZ   = re.compile('VCDIFF header size: +(\\d+)')
 RE_EXTCOMP = re.compile('XDELTA ext comp.*')
 
 def c2s(c):
-    return ' '.join(['%02d' % x for x in c])
+    return ' '.join(['%s' % x for x in c])
 #end
 
 def SumList(l):
@@ -470,8 +481,6 @@ class Xdelta1Runner:
     #end
 #end
 
-# TODO: cleanup below this line
-
 # exceptions
 class SkipRcsException:
     def __init__(self,reason):
@@ -771,14 +780,13 @@ def GetTestRcsFiles():
     return rcsf
 #end
 
-# TODO: cleanup below this line
-
 #
 class RandomTestResult:
-    def __init__(self, round, config, runtime, compsize):
+    def __init__(self, round, config, runtime, compsize, decodetime):
         self.round = round
         self.myconfig = config
         self.runtime = runtime
+        self.decodetime = decodetime
         self.compsize = compsize
         self.score = None
         self.time_pos = None
@@ -787,10 +795,11 @@ class RandomTestResult:
     #end
 
     def __str__(self):
-        return 'time %.6f%s size %d%s << %s >>' % (
+        return 'time %.6f%s size %d%s << %s >> %.6f' % (
             self.time(), ((self.time_pos != None) and (" (%s)" % self.time_pos) or ""),
             self.size(), ((self.size_pos != None) and (" (%s)" % self.size_pos) or ""),
-            c2s(self.config()))
+            c2s(self.config()),
+            self.decodetime)
     #end
 
     def time(self):
@@ -853,12 +862,6 @@ class RandomTester:
             config.append(val)
         #end
 
-        if map['small_chain'] < map['small_lchain']:
-            return None
-
-        if map['large_look'] < map['small_look']:
-            return None
-
         for r in self.results:
             if c2s(r.config()) == c2s(config):
                 return None
@@ -873,7 +876,13 @@ class RandomTester:
         for i in range(SOFT_CONFIG_CNT, len(CONFIG_ORDER)):
             key = CONFIG_ARGMAP[CONFIG_ORDER[i]]
             val = config[i]
-            args.append('%s=%s' % (key, val))
+            if val == 'true' or val == 'false':
+                if val == 'true':
+                    args.append('%s' % key)
+                #end
+            else:
+                args.append('%s=%s' % (key, val))
+            #end
         #end
         return args
     #end
@@ -924,7 +933,8 @@ class RandomTester:
         tr = RandomTestResult(self.round_num,
                               config,
                               result.encode_time.mean,
-                              result.encode_size)
+                              result.encode_size,
+                              result.decode_time.mean)
 
         self.results.append(tr)
 
@@ -1060,7 +1070,6 @@ def RunRandomRcsTest(rcsf):
 #end
 
 def RunSampleTest(d, files):
-    # TODO: consolidate w/ the above
     print 'testing %s with %d files' % (d, len(files))
     configs = []
     while len(files) > 1:
@@ -1106,6 +1115,11 @@ if __name__ == "__main__":
         #RunSpeedTest()
 
         #rcsf = GetTestRcsFiles()
+        #RunRandomRcsTest(rcsf)
+
+        RunSampleDataTest()
+
+        # Other
 
         #x3r = rcsf.AllPairsByDate(Xdelta3RunClass(['-9']))
         #x3r = rcsf.AllPairsByDate(Xdelta3RunClass(['-9', '-S', 'djw']))
@@ -1117,9 +1131,6 @@ if __name__ == "__main__":
         #x1r = rcsf.AllPairsByDate(Xdelta1RunClass())
         #ReportPairs('xdelta1', x1r)
 
-        #RunRandomRcsTest(rcsf)
-        RunSampleDataTest()
-
     except CommandError:
         pass
     else:
diff --git a/xdelta3/xdelta3-test.h b/xdelta3/xdelta3-test.h
index f4d5972..248691c 100644
--- a/xdelta3/xdelta3-test.h
+++ b/xdelta3/xdelta3-test.h
@@ -693,11 +693,8 @@ test_compress_text (xd3_stream  *stream,
   cfg.smatcher_soft.small_look = 4;
   cfg.smatcher_soft.small_chain = 128;
   cfg.smatcher_soft.small_lchain = 16;
-  cfg.smatcher_soft.ssmatch = 0;
-  cfg.smatcher_soft.try_lazy = 1;
   cfg.smatcher_soft.max_lazy = 8;
   cfg.smatcher_soft.long_enough = 128;
-  cfg.smatcher_soft.promote = 0;
   
   xd3_config_stream (stream, & cfg);
 
@@ -1959,9 +1956,7 @@ typedef struct _string_match_test string_match_test;
 typedef enum
 {
   SM_NONE    = 0,
-  SM_SSMATCH = (1 << 0),
   SM_LAZY    = (1 << 1),
-  SM_PROMOTE = (1 << 2),
 } string_match_flags;
 
 struct _string_match_test
@@ -1985,7 +1980,7 @@ static const string_match_test match_tests[] =
 
   /* simple promotion: the third copy address depends on promotion */
   { "ABCDEF_ABCDEF^ABCDEF", SM_NONE,    "C7/6@0 C14/6@7" },
-  { "ABCDEF_ABCDEF^ABCDEF", SM_PROMOTE, "C7/6@0 C14/6@0" },
+  /* { "ABCDEF_ABCDEF^ABCDEF", SM_PROMOTE, "C7/6@0 C14/6@0" }, forgotten */
 
   /* simple lazy: there is a better copy starting with "23 X" than "123 " */
   { "123 23 XYZ 123 XYZ", SM_NONE, "C11/4@0" },
@@ -2018,7 +2013,7 @@ static const string_match_test match_tests[] =
 
   /* ssmatch test */
   { "ABCDE___ABCDE*** BCDE***", SM_NONE, "C8/5@0 C17/4@1" },
-  { "ABCDE___ABCDE*** BCDE***", SM_SSMATCH, "C8/5@0 C17/7@9" },
+  /*{ "ABCDE___ABCDE*** BCDE***", SM_SSMATCH, "C8/5@0 C17/7@9" }, forgotten */
 };
 
 static int
@@ -2043,11 +2038,8 @@ test_string_matching (xd3_stream *stream, int ignore)
       config.smatcher_soft.small_look   = 4;
       config.smatcher_soft.small_chain  = 10;
       config.smatcher_soft.small_lchain = 10;
-      config.smatcher_soft.max_lazy     = 10;
+      config.smatcher_soft.max_lazy     = (test->flags & SM_LAZY) ? 10 : 0;
       config.smatcher_soft.long_enough  = 10;
-      config.smatcher_soft.ssmatch      = (test->flags & SM_SSMATCH) && 1;
-      config.smatcher_soft.try_lazy     = (test->flags & SM_LAZY) && 1;
-      config.smatcher_soft.promote      = (test->flags & SM_PROMOTE) && 1;
 
       if ((ret = xd3_config_stream (stream, & config))) { return ret; }
       if ((ret = xd3_encode_init (stream))) { return ret; }
@@ -2122,11 +2114,8 @@ test_iopt_flush_instructions (xd3_stream *stream, int ignore)
   config.smatcher_soft.small_look    = 4;
   config.smatcher_soft.small_chain   = 128;
   config.smatcher_soft.small_lchain  = 16;
-  config.smatcher_soft.ssmatch       = 0;
-  config.smatcher_soft.try_lazy      = 1;
   config.smatcher_soft.max_lazy      = 8;
   config.smatcher_soft.long_enough   = 128;
-  config.smatcher_soft.promote       = 0;
 
   if ((ret = xd3_config_stream (stream, & config))) { return ret; }
 
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index b6ac778..c0e7880 100644
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -61,12 +61,7 @@
    copies within the TARGET.  Small matching, which is more expensive,
    usually dominates the large STRING-MATCH costs in this code - the
    more exhaustive the search, the better the results.  Either of the
-   two string-matching mechanisms may be disabled.  Currently, large
-   checksums are only performed in the source file, if present, and
-   small checksums are performed only in the left-over target input.
-   However, small matches are possible in the source file too, with a
-   range of possibilities.  [I've seen a paper on this subject, but
-   I lost it.]
+   two string-matching mechanisms may be disabled.
 
    2. INSTRUCTION SELECTION.  The IOPT buffer here represents a queue
    used to store overlapping copy instructions.  There are two possible
@@ -486,11 +481,9 @@ IF_BUILD_DEFAULT(static const xd3_smatcher    __smatcher_default;)
 #define SMALL_HASH_DEBUG2(s,inp)                                  \
   XD3_ASSERT (debug_hval == xd3_checksum_hash (& (s)->small_hash, \
          xd3_scksum ((inp), (s)->smatcher.small_look)))
-#define SMALL_HASH_STATS(x) x
 #else
 #define SMALL_HASH_DEBUG1(s,inp)
 #define SMALL_HASH_DEBUG2(s,inp)
-#define SMALL_HASH_STATS(x)
 #endif /* XD3_DEBUG */
 
 /* Update the run-length state */
@@ -1169,6 +1162,7 @@ static usize_t  __alternate_code_table_compressed_size;
 int xd3_compute_code_table_encoding (xd3_stream *in_stream, const xd3_dinst *code_table,
                                      uint8_t *comp_string, usize_t *comp_string_size)
 {
+  /* TODO: use xd3_encode_memory() */
   uint8_t dflt_string[CODE_TABLE_STRING_SIZE];
   uint8_t code_string[CODE_TABLE_STRING_SIZE];
   xd3_stream stream;
@@ -1194,11 +1188,8 @@ int xd3_compute_code_table_encoding (xd3_stream *in_stream, const xd3_dinst *cod
   config.smatcher_soft.small_look    = 4;
   config.smatcher_soft.small_chain   = CODE_TABLE_STRING_SIZE;
   config.smatcher_soft.small_lchain  = CODE_TABLE_STRING_SIZE;
-  config.smatcher_soft.ssmatch       = 1;
-  config.smatcher_soft.try_lazy      = 1;
   config.smatcher_soft.max_lazy      = CODE_TABLE_STRING_SIZE;
   config.smatcher_soft.long_enough   = CODE_TABLE_STRING_SIZE;
-  config.smatcher_soft.promote       = 1;
 
   if ((ret = xd3_config_stream (& stream, & config))) { goto fail; }
 
@@ -2503,11 +2494,7 @@ xd3_config_stream(xd3_stream *stream,
         smatcher->name = __smatcher_soft.name;
         if (smatcher->large_look  < MIN_MATCH ||
             smatcher->large_step  < 1         ||
-            smatcher->small_look  < MIN_MATCH ||
-            smatcher->small_chain < 1         ||
-            smatcher->large_look  < smatcher->small_look ||
-            smatcher->small_chain < smatcher->small_lchain ||
-            (smatcher->small_lchain == 0 && smatcher->try_lazy))
+            smatcher->small_look  < MIN_MATCH)
           {
             stream->msg = "invalid soft string-match config";
             return XD3_INVALID;
@@ -3581,22 +3568,6 @@ xd3_encode_init (xd3_stream *stream)
   return ENOMEM;
 }
 
-#if XD3_DEBUG
-static int
-xd3_check_sprevlist (xd3_stream *stream)
-{
-  int i;
-  for (i = 0; i < stream->sprevsz; i += 1)
-    {
-      xd3_slist *l = & stream->small_prev[i];
-
-      XD3_ASSERT (l->prev->next == l);
-      XD3_ASSERT (l->next->prev == l);
-    }
-  return 1;
-}
-#endif
-
 /* Called after the ENC_POSTOUT state, this puts the output buffers back into separate
  * lists and re-initializes some variables.  (The output lists were spliced together
  * during the ENC_FLUSH state.) */
@@ -3606,8 +3577,6 @@ xd3_encode_reset (xd3_stream *stream)
   int i;
   xd3_output *olist;
 
-  XD3_ASSERT (stream->small_prev == NULL || xd3_check_sprevlist (stream));
-
   IF_DEBUG (stream->n_emit = 0);
   stream->avail_in     = 0;
   stream->small_reset  = 1;
@@ -3930,9 +3899,6 @@ xd3_process_memory (int            is_encode,
     return XD3_INTERNAL;
   }
 
-  /* TODO: for small inputs, the xd3_stream could be configured to allocate MUCH less
-   * memory.  Most of the allocations sizes are defaulted (see xdelta3.h), and assume
-   * large inputs. */
   memset (& stream, 0, sizeof (stream));
   memset (& config, 0, sizeof (config));
 
@@ -3940,9 +3906,10 @@ xd3_process_memory (int            is_encode,
 
   if (is_encode)
     {
-      /* TODO: for large inputs, limit window size, need to select a default ... */
       config.srcwin_maxsz = source_size;
       config.winsize = min(input_size, (usize_t) (1<<20));
+      config.sprevsz = min(input_size, XD3_DEFAULT_SPREVSZ);
+      config.iopt_size = min(input_size / 32, XD3_DEFAULT_IOPT_SIZE);
     }
 
   if ((ret = xd3_config_stream (&stream, &config)) != 0)
@@ -4056,6 +4023,14 @@ xd3_string_match_init (xd3_stream *stream)
   const int DO_SMALL = ! (stream->flags & XD3_NOCOMPRESS);
   const int DO_LARGE = (stream->src != NULL);
 
+  if (DO_LARGE && stream->large_table == NULL)
+    {
+      if ((stream->large_table = xd3_alloc0 (stream, stream->large_hash.size, sizeof (usize_t))) == NULL)
+        {
+          return ENOMEM;
+        }
+    }
+
   if (DO_SMALL)
     {
       /* Subsequent calls can return immediately after checking reset. */
@@ -4063,7 +4038,7 @@ xd3_string_match_init (xd3_stream *stream)
         {
           /* The target hash table is reinitialized once per window. */
           /* TODO: This would not have to be reinitialized if absolute offsets
-           * were being stored. */
+           * were being stored, as we would do for VCD_TARGET encoding. */
           if (stream->small_reset)
             {
               stream->small_reset = 0;
@@ -4081,31 +4056,15 @@ xd3_string_match_init (xd3_stream *stream)
         }
 
       /* If there is a previous table needed. */
-      if (stream->smatcher.small_chain > 1)
+      if (stream->smatcher.small_lchain > 1 ||
+          stream->smatcher.small_chain > 1)
         {
-          xd3_slist *p, *m;
-
           if ((stream->small_prev = xd3_alloc (stream,
                                                stream->sprevsz,
                                                sizeof (xd3_slist))) == NULL)
             {
               return ENOMEM;
             }
-
-          /* Initialize circular lists. */
-          for (p = stream->small_prev, m = stream->small_prev + stream->sprevsz; p != m; p += 1)
-            {
-              p->next = p;
-              p->prev = p;
-            }
-        }
-    }
-
-  if (DO_LARGE && stream->large_table == NULL)
-    {
-      if ((stream->large_table = xd3_alloc0 (stream, stream->large_hash.size, sizeof (usize_t))) == NULL)
-        {
-          return ENOMEM;
         }
     }
 
@@ -4648,67 +4607,22 @@ xd3_source_extend_match (xd3_stream *stream)
   return 0;
 }
 
-/* Update the small hash.  Values in the small_table are offset by HASH_CKOFFSET (1) to
- * distinguish empty buckets the zero offset.  This maintains the previous linked lists.
- * If owrite is true then this entry is replacing the existing record, otherwise it is
- * merely being called to promote the existing record in the hash bucket (for the same
- * address cache). */
+/* Update the small hash.  Values in the small_table are offset by
+ * HASH_CKOFFSET (1) to distinguish empty buckets from real offsets. */
 static void
-xd3_scksum_insert (xd3_stream *stream, usize_t inx, usize_t scksum, usize_t pos)
+xd3_scksum_insert (xd3_stream *stream,
+                   usize_t inx,
+                   usize_t scksum,
+                   usize_t pos)
 {
-  /* If we are maintaining previous links. */
+  /* If we are maintaining previous duplicates. */
   if (stream->small_prev)
     {
-      usize_t     last_pos = stream->small_table[inx];
+      usize_t    last_pos = stream->small_table[inx];
       xd3_slist *pos_list = & stream->small_prev[pos & stream->sprevmask];
-      xd3_slist *prev     = pos_list->prev;
-      xd3_slist *next     = pos_list->next;
-
-      /* Assert link structure, update pos, cksum */
-      XD3_ASSERT (prev->next == pos_list);
-      XD3_ASSERT (next->prev == pos_list);
-      pos_list->pos = pos;
-      pos_list->scksum = scksum;
-
-      /* Subtract HASH_CKOFFSET and test for a previous offset. */
-      if (last_pos-- != 0)
-        {
-          xd3_slist *last_list = & stream->small_prev[last_pos & stream->sprevmask];
-          xd3_slist *last_next;
-
-          /* Verify existing entry. */
-          SMALL_HASH_DEBUG1 (stream, stream->next_in + last_pos);
-          SMALL_HASH_DEBUG2 (stream, stream->next_in + pos);
-
-          /* The two positions (mod sprevsz) may have the same checksum, making the old
-           * and new entries the same.  That is why the removal step is not before the
-           * above if-stmt. */
-          if (last_list != pos_list)
-            {
-              /* Remove current position from any list it may belong to. */
-              next->prev = prev;
-              prev->next = next;
-
-              /* The ordinary case, add current position to last_list. */
-              last_next = last_list->next;
-
-              pos_list->next = last_next;
-              pos_list->prev = last_list;
-
-              last_next->prev = pos_list;
-              last_list->next = pos_list;
-            }
-        }
-      else
-        {
-          /* Remove current position from any list it may belong to. */
-          next->prev = prev;
-          prev->next = next;
 
-          /* Re-initialize current position. */
-          pos_list->next = pos_list;
-          pos_list->prev = pos_list;
-        }
+      /* Note last_pos is offset by HASH_CKOFFSET. */
+      pos_list->last_pos = last_pos;
     }
 
   /* Enter the new position into the hash bucket. */
@@ -4736,62 +4650,42 @@ xd3_check_smatch (const uint8_t *ref0, const uint8_t *inp0,
 }
 #endif /* XD3_DEBUG */
 
-/* When the hash table indicates a possible small string match, it calls this routine to
- * find the best match.  The first matching position is taken from the small_table,
- * HASH_CKOFFSET is subtracted to get the actual position.  After checking that match, if
- * previous linked lists are in use (because stream->smatcher.small_chain > 1), previous matches
- * are tested searching for the longest match.  If (stream->min_match > MIN_MATCH) then a lazy
- * match is in effect.
- *
- * OPT: This is by far the most expensive function.  The slowdown is in part due to the data
- * structure it maintains, which is relatively more expensive than it needs to be (in
- * comparison to zlib) in order to support the PROMOTE decision, which is to prefer the
- * most recently used matching address of a certain string to aid the VCDIFF same cache.
- *
- * --- TODO: declare the PROMOTE experiment a failure -- remove the extra LIST --
+/* When the hash table indicates a possible small string match, it
+ * calls this routine to find the best match.  The first matching
+ * position is taken from the small_table, HASH_CKOFFSET is subtracted
+ * to get the actual position.  After checking that match, if previous
+ * linked lists are in use (because stream->smatcher.small_chain > 1),
+ * previous matches are tested searching for the longest match.  If
+ * (stream->min_match > MIN_MATCH) then a lazy match is in effect.
  *
- * Weak reasoning? it's time to modularize this routine...?  Let's say the PROMOTE
- * feature supported by this slow data structure contributes around 2% improvement in
- * compressed size, is there a better code table that doesn't use the SAME address cache,
- * for which the speedup-discount could produce a better encoding?
+ * TODO: This is the second most-expensive function, after
+ * xd3_srcwin_move_point().
  */
-static /*inline*/ usize_t
-xd3_smatch (xd3_stream *stream, usize_t base, usize_t scksum, usize_t *match_offset)
+static usize_t
+xd3_smatch (xd3_stream *stream,
+            usize_t base,
+            usize_t scksum,
+            usize_t *match_offset)
 {
   usize_t         cmp_len;
   usize_t         match_length = 0;
   usize_t         chain        = (stream->min_match == MIN_MATCH ?
                                   stream->smatcher.small_chain :
                                   stream->smatcher.small_lchain);
-  xd3_slist     *current      = NULL;
-  xd3_slist     *first        = NULL;
   const uint8_t *inp_max      = stream->next_in + stream->avail_in;
   const uint8_t *inp;
   const uint8_t *ref;
 
-  SMALL_HASH_STATS  (usize_t search_cnt = 0);
   SMALL_HASH_DEBUG1 (stream, stream->next_in + stream->input_position);
-  SMALL_HASH_STATS  (stream->sh_searches += 1);
 
   XD3_ASSERT (stream->min_match + stream->input_position <= stream->avail_in);
 
   base -= HASH_CKOFFSET;
 
-  /* Initialize the chain. */
-  if (stream->small_prev != NULL)
-    {
-      first = current = & stream->small_prev[base & stream->sprevmask];
-
-      /* Check if current->pos is correct. */
-      if (current->pos != base) { goto done; }
-    }
-
  again:
 
-  SMALL_HASH_STATS (search_cnt += 1);
-
-  /* For small matches, we can always go to the end-of-input because the matching position
-   * must be less than the input position. */
+  /* For small matches, we can always go to the end-of-input because
+   * the matching position must be less than the input position. */
   XD3_ASSERT (base < stream->input_position);
 
   ref = stream->next_in + base;
@@ -4809,7 +4703,8 @@ xd3_smatch (xd3_stream *stream, usize_t base, usize_t scksum, usize_t *match_off
   cmp_len = inp - (stream->next_in + stream->input_position);
 
   /* Verify correctness */
-  XD3_ASSERT (xd3_check_smatch (stream->next_in + base, stream->next_in + stream->input_position,
+  XD3_ASSERT (xd3_check_smatch (stream->next_in + base,
+                                stream->next_in + stream->input_position,
                                 inp_max, cmp_len));
 
   /* Update longest match */
@@ -4818,38 +4713,39 @@ xd3_smatch (xd3_stream *stream, usize_t base, usize_t scksum, usize_t *match_off
       ( match_length) = cmp_len;
       (*match_offset) = base;
 
-      /* Stop if we match the entire input or discover a long_enough match. */
+      /* Stop if we match the entire input or have a long_enough match. */
       if (inp == inp_max || cmp_len >= stream->smatcher.long_enough)
         {
           goto done;
         }
     }
 
-  /* If we have not reached the chain limit, see if there is another previous position. */
-  if (current)
+  /* If we have not reached the chain limit, see if there is another
+     previous position. */
+  while (--chain != 0)
     {
-      while (--chain != 0)
+      /* Calculate the previous offset. */
+      usize_t last_pos = stream->small_prev[base & stream->sprevmask].last_pos;
+
+      if (last_pos == 0)
         {
-          /* Calculate the next base offset. */
-          current = current->prev;
-          base    = current->pos;
-
-          /* Stop if the next position was the first.  Stop if the position is wrong
-           * (because the lists are not re-initialized across input windows). Skip if the
-           * scksum is wrong. */
-          if (current != first && base < stream->input_position)
-            {
-              if (current->scksum != scksum)
-                {
-                  continue;
-                }
-              goto again;
-            }
+          break;
         }
+
+      last_pos -= HASH_CKOFFSET;
+      base = last_pos;
+
+      /* Stop if the position is wrong (because the lists are not
+       * re-initialized across input windows). */
+      if (base < stream->input_position)
+        {
+          goto again;
+        }
+
+      break;
     }
 
  done:
-  SMALL_HASH_STATS (stream->sh_compares += search_cnt);
   return match_length;
 }
 
@@ -4903,8 +4799,7 @@ xd3_verify_run_state (xd3_stream    *stream,
  Templates
  ******************************************************************************************/
 
-/* Template macros: less than 30 lines work.  the template parameters appear as, e.g.,
- * SLOOK, MIN_MATCH, TRYLAZY, etc. */
+/* Template macros */
 #define XD3_TEMPLATE(x)      XD3_TEMPLATE2(x,TEMPLATE)
 #define XD3_TEMPLATE2(x,n)   XD3_TEMPLATE3(x,n)
 #define XD3_TEMPLATE3(x,n)   x ## n
@@ -4918,10 +4813,9 @@ static const xd3_smatcher XD3_TEMPLATE(__smatcher_) =
   XD3_STRINGIFY(TEMPLATE),
   XD3_TEMPLATE(xd3_string_match_),
 #if SOFTCFG == 1
-  0, 0, 0, 0, 0, 0, 0, 0, 0, 0
+  0, 0, 0, 0, 0, 0, 0
 #else
-  LLOOK, LSTEP, SLOOK, SCHAIN, SLCHAIN, SSMATCH, TRYLAZY, MAXLAZY,
-  LONGENOUGH, PROMOTE
+  LLOOK, LSTEP, SLOOK, SCHAIN, SLCHAIN, MAXLAZY, LONGENOUGH
 #endif
 };
 
@@ -4999,13 +4893,13 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
    * checks that LEN is shorter than MAXLAZY and that there is enough leftover data to
    * consider lazy matching.  "Enough" is set to 2 since the next match will start at the
    * next offset, it must match two extra characters. */
-#define TRYLAZYLEN(LEN,POS,MAX) ((TRYLAZY && (LEN) < MAXLAZY) && ((POS) + (LEN) <= (MAX) - 2))
+#define TRYLAZYLEN(LEN,POS,MAX) ((MAXLAZY) > 0 && (LEN) < (MAXLAZY) && (POS) + (LEN) <= (MAX) - 2)
 
   /* HANDLELAZY: This statement is called each time an instruciton is emitted (three
    * cases).  If the instruction is large enough, the loop is restarted, otherwise lazy
    * matching may ensue. */
 #define HANDLELAZY(mlen) \
-  if (TRYLAZYLEN ((mlen), stream->input_position, stream->avail_in)) \
+  if (TRYLAZYLEN ((mlen), (stream->input_position), (stream->avail_in))) \
     { stream->min_match = (mlen) + LEAST_MATCH_INCR; goto updateone; } \
   else \
     { stream->input_position += (mlen); goto restartloop; }
@@ -5104,13 +4998,6 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
           /* Insert a hash for this string. */
           xd3_scksum_insert (stream, sinx, scksum, stream->input_position);
 
-          /* Promote the previous match address to head of the hash bucket.  This is
-           * intended to improve the same cache hit rate. */
-          if (match_length != 0 && PROMOTE)
-            {
-              xd3_scksum_insert (stream, sinx, scksum, match_offset);
-            }
-
           /* Maybe output a COPY instruction */
           if (unlikely (match_length >= stream->min_match))
             {
@@ -5132,67 +5019,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
                                         /* address */ match_offset,
                                         /* is_source */ 0))) { return ret; }
 
-              /* SSMATCH option: search small matches: continue the incremental checksum
-               * through the matched material.  Only if not lazy matching.  */
-              if (SSMATCH && !TRYLAZYLEN (match_length, stream->input_position, stream->avail_in))
-                {
-                  usize_t avail = stream->avail_in - SLOOK - stream->input_position;
-                  usize_t ml_m1 = match_length - 1;
-                  usize_t right;
-                  int    aincr;
-
-                  IF_DEBUG (usize_t nposi = stream->input_position + match_length);
-
-                  /* Avail is the last offset we can compute an incremental cksum.  If the
-                   * match length exceeds that offset then we are finished performing
-                   * incremental updates after this step.  */
-                  if (ml_m1 < avail)
-                    {
-                      right = ml_m1;
-                      aincr = 1;
-                    }
-                  else
-                    {
-                      right = avail;
-                      aincr = 0;
-                    }
-
-                  /* Compute incremental checksums within the match. */
-                  while (right > 0)
-                    {
-                      SMALL_CKSUM_UPDATE (scksum, inp, SLOOK);
-                      if (DO_LARGE && (stream->input_position + LLOOK < stream->avail_in)) {
-                        LARGE_CKSUM_UPDATE (lcksum, inp, LLOOK);
-                      }
-
-                      inp    += 1;
-                      stream->input_position += 1;
-                      right  -= 1;
-                      sinx = xd3_checksum_hash (& stream->small_hash, scksum);
-
-                      IF_DEBUG (xd3_verify_small_state (stream, inp, scksum));
-
-                      xd3_scksum_insert (stream, sinx, scksum, stream->input_position);
-                    }
-
-                  if (aincr)
-                    {
-                      /* Keep searching... */
-                      if (DO_RUN) { run_l = xd3_comprun (inp+1, SLOOK-1, & run_c); }
-                      XD3_ASSERT (nposi == stream->input_position + 1);
-                      XD3_ASSERT (stream->input_position + SLOOK < stream->avail_in);
-                      stream->min_match = MIN_MATCH;
-                      goto updatesure;
-                    }
-                  else
-                    {
-                      /* Not enough input for another match. */
-                      XD3_ASSERT (stream->input_position + SLOOK >= stream->avail_in);
-                      goto loopnomore;
-                    }
-                }
-
-              /* Else case: copy instruction, but no SSMATCH. */
+              /* Copy instruction. */
               HANDLELAZY (match_length);
             }
         }
@@ -5213,8 +5040,6 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
           goto loopnomore;
         }
 
-    updatesure:
-
       /* Compute next RUN, CKSUM */
       if (DO_RUN)   { NEXTRUN (inp[SLOOK]); }
       if (DO_SMALL) { SMALL_CKSUM_UPDATE (scksum, inp, SLOOK); }
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h
index 6204d3f..1f20c10 100644
--- a/xdelta3/xdelta3.h
+++ b/xdelta3/xdelta3.h
@@ -71,7 +71,7 @@
  * 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)
+#define XD3_DEFAULT_IOPT_SIZE    (1U<<15)
 #endif
 
 /* The maximum distance backward to search for small matches */
@@ -529,11 +529,8 @@ struct _xd3_smatcher
   uint               small_look;
   uint               small_chain;
   uint               small_lchain;
-  uint               ssmatch;
-  uint               try_lazy;
   uint               max_lazy;
   uint               long_enough;
-  uint               promote;
 };
 
 /* hash table size & power-of-two hash function. */
@@ -544,13 +541,10 @@ struct _xd3_hash_cfg
   usize_t           mask;
 };
 
-/* a hash-chain link in the small match table, embedded with position and checksum */
+/* the sprev list */
 struct _xd3_slist
 {
-  xd3_slist *next;
-  xd3_slist *prev;
-  usize_t     pos;
-  usize_t     scksum;
+  usize_t     last_pos;
 };
 
 /* a decoder section (data, inst, or addr).  there is an optimization to avoid copying
@@ -815,9 +809,6 @@ struct _xd3_stream
   usize_t           i_slots_used;
 
 #if XD3_DEBUG
-  usize_t            sh_searches;
-  usize_t            sh_compares;
-
   usize_t            large_ckcnt;
 
   /* memory usage */
diff --git a/xdelta3/xdelta3.prj b/xdelta3/xdelta3.prj
index 10c9f77..3fa7b32 100644
--- a/xdelta3/xdelta3.prj
+++ b/xdelta3/xdelta3.prj
@@ -1,11 +1,11 @@
 ;; -*- Prcs -*-
 (Created-By-Prcs-Version 1 3 4)
 (Project-Description "")
-(Project-Version xdelta3 0 19)
-(Parent-Version xdelta3 0 18)
-(Version-Log "pre-3.0p")
+(Project-Version xdelta3 0 27)
+(Parent-Version xdelta3 0 26)
+(Version-Log "raise default iopt_size, happy")
 (New-Version-Log "")
-(Checkin-Time "Sat, 17 Feb 2007 04:08:43 -0800")
+(Checkin-Time "Sun, 18 Feb 2007 03:09:06 -0800")
 (Checkin-Login jmacd)
 (Populate-Ignore ("\\.svn"))
 (Project-Keywords
@@ -14,20 +14,20 @@
 (Files
   (COPYING (xdelta3/b/29_COPYING 1.1 744))
 
-  (xdelta3-cfgs.h (xdelta3/9_xdelta3-cf 1.5 744))
+  (xdelta3-cfgs.h (xdelta3/9_xdelta3-cf 1.8 744))
   (xdelta3-decode.h (xdelta3/b/30_xdelta3-de 1.5 744))
   (xdelta3-djw.h (xdelta3/8_xdelta3-dj 1.6 744))
   (xdelta3-fgk.h (xdelta3/7_xdelta3-fg 1.3 744))
   (xdelta3-list.h (xdelta3/6_xdelta3-li 1.3 744))
-  (xdelta3-main.h (xdelta3/5_xdelta3-ma 1.12 744))
+  (xdelta3-main.h (xdelta3/5_xdelta3-ma 1.17 744))
   (xdelta3-python.h (xdelta3/4_xdelta3-py 1.5 744))
-  (xdelta3-regtest.py (xdelta3/10_xdelta3-re 1.11 744))
+  (xdelta3-regtest.py (xdelta3/10_xdelta3-re 1.17 744))
   (xdelta3-second.h (xdelta3/3_xdelta3-se 1.4 744))
-  (xdelta3-test.h (xdelta3/2_xdelta3-te 1.10 744))
-  (xdelta3.c (xdelta3/16_xdelta3.c 1.11 744))
-  (xdelta3.h (xdelta3/1_xdelta3.h 1.9 744))
+  (xdelta3-test.h (xdelta3/2_xdelta3-te 1.13 744))
+  (xdelta3.c (xdelta3/16_xdelta3.c 1.16 744))
+  (xdelta3.h (xdelta3/1_xdelta3.h 1.14 744))
 
-  (Makefile (xdelta3/0_Makefile 1.10 744))
+  (Makefile (xdelta3/0_Makefile 1.11 744))
   (setup.py (xdelta3/11_setup.py 1.5 744))
 
   (draft-korn-vcdiff.txt (xdelta3/b/22_draft-korn 1.1 744))
@@ -45,7 +45,7 @@
   (xdelta3-test.py (xdelta3/b/28_xdelta3-te 1.3 744))
 
   (examples/Makefile (xdelta3/b/34_Makefile 1.1 744))
-  (examples/small_page_test.c (xdelta3/b/35_small_page 1.1 744))
+  (examples/small_page_test.c (xdelta3/b/35_small_page 1.2 744))
 )
 (Merge-Parents)
 (New-Merge-Parents)