Checksum test cleanups & dev

8 files changed, 333 insertions, 236 deletions

diff --git a/xdelta3/Makefile.am b/xdelta3/Makefile.am
index a60f337..d485333 100644
--- a/xdelta3/Makefile.am
+++ b/xdelta3/Makefile.am
@@ -42,7 +42,7 @@ xdelta3checksum_SOURCES = $(common_SOURCES) \
 # Note: for extra sanity checks, enable -Wconversion. Note there
 # are a lot of false positives.
 WFLAGS = -Wall -Wshadow -fno-builtin -Wextra -Wsign-compare \
-         -Wno-unused-parameter # -Weverything #-Wconversion
+         -Wno-unused-parameter # -Wconversion
 
 
 C_WFLAGS = $(WFLAGS) -pedantic -std=c99
diff --git a/xdelta3/run_release.sh b/xdelta3/run_release.sh
index 3060f96..d2ead52 100755
--- a/xdelta3/run_release.sh
+++ b/xdelta3/run_release.sh
@@ -1,10 +1,18 @@
 #!/bin/sh
 
-CFLAGS=-O2
-CXXFLAGS=-O2
 CC=clang 
 CXX=clang++
 
+#CC=gcc
+#CXX=g++
+
+# These are updated below
+CFLAGS=
+CXXFLAGS=
+
+# Place C/C++ common flags here
+COMMON=-O3
+
 export CFLAGS
 export CXXFLAGS
 export CC
@@ -25,9 +33,9 @@ rm -rf build
 # autoconf
 
 function resetflag {
-    CFLAGS="-$1 -I$LIBBASE/$MACH/include"
-    CXXFLAGS="-$1 -I$LIBBASE/$MACH/include"
-    LDFLAGS="-$1 -L$LIBBASE/$MACH/lib"
+    CFLAGS="$COMMON -$1 -I$LIBBASE/$MACH/include"
+    CXXFLAGS="$COMMON -$1 -I$LIBBASE/$MACH/include"
+    LDFLAGS="$COMMON -$1 -L$LIBBASE/$MACH/lib"
 }    
 
 function addflag {
@@ -44,7 +52,7 @@ function buildit {
     D=build/$MACH/${sizebits}size-${offsetbits}off
     mkdir -p $D
     (cd $D && $SRCDIR/configure --prefix=$PWD/bin --enable-debug-symbols)
-    (cd $D && make && make install)
+    (cd $D && make xdelta3checksum)
     #echo Running regtest.
     #(cd $D && ./xdelta3regtest)
 }
@@ -67,5 +75,5 @@ function buildall {
     buildit 64 64
 }
 
-buildall m32
 buildall m64
+buildall m32
diff --git a/xdelta3/testing/checksum_test.cc b/xdelta3/testing/checksum_test.cc
index 9937f14..b9a4b0b 100644
--- a/xdelta3/testing/checksum_test.cc
+++ b/xdelta3/testing/checksum_test.cc
@@ -28,37 +28,32 @@ struct true_type { };
 struct false_type { };
 
 template <typename Word>
-int bitsof();
+usize_t bitsof();
 
 template<>
-int bitsof<uint32_t>() {
+usize_t bitsof<uint32_t>() {
   return 32;
 }
 
 template<>
-int bitsof<uint64_t>() {
+usize_t bitsof<uint64_t>() {
   return 64;
 }
 
-struct plain {
-  usize_t operator()(const uint8_t &c) {
-    return c;
-  }
-};
-
-struct randperm {
-  usize_t operator()(const uint8_t &c) {
-    return __single_hash[c];
+template <typename Word>
+struct hhash {  // shift "s" bits leaving the high bits as a hash value for
+                // this checksum, which are the most "distant" in terms of the
+                // spectral test for the rabin_karp MLCG.  For short windows,
+                // the high bits aren't enough, XOR "mask" worth of these in.
+  Word operator()(const Word t, const Word s, const Word mask) {
+    return (t >> s) ^ (t & mask);
   }
 };
 
 template <typename Word>
-struct hhash {  // take "h" of the high-bits as a hash value for this
-                // checksum, which are the most "distant" in terms of the
-                // spectral test for the rabin_karp MLCG.  For short windows,
-                // the high bits aren't enough, XOR "mask" worth of these in.
-  Word operator()(const Word& t, const int &h, const int &mask) {
-    return (t >> h) ^ (t & mask);
+struct nonhash {
+  Word operator()(const Word t, const Word h, const Word mask) {
+    return (t >> h) & mask;
   }
 };
 
@@ -77,18 +72,16 @@ uint64_t good_word<uint64_t>() {
 
 // CLASSES
 
-#define SELF Word, CksumSize, CksumSkip, Permute, Hash, Compaction
+#define SELF Word, CksumSize, CksumSkip, Hash, Compaction
 #define MEMBER template <typename Word,         \
                          int CksumSize,         \
                          int CksumSkip,         \
-                         typename Permute,      \
                          typename Hash,         \
                          int Compaction>
 
 MEMBER
 struct cksum_params {
   typedef Word word_type;
-  typedef Permute permute_type;
   typedef Hash hash_type;
 
   static const int cksum_size = CksumSize;
@@ -116,7 +109,7 @@ struct rabin_karp : public cksum_params<SELF> {
   Word step(const uint8_t *ptr) {
     Word h = 0;
     for (int i = 0; i < CksumSize; i++) {
-      h += Permute()(ptr[i]) * powers[i];
+      h += (ptr[i]) * powers[i];
     }
     return h;
   }
@@ -128,8 +121,7 @@ struct rabin_karp : public cksum_params<SELF> {
 
   Word incr(const uint8_t *ptr) {
     incr_state = multiplier * incr_state -
-      product * Permute()(ptr[-1]) +
-      Permute()(ptr[CksumSize - 1]);
+      product * (ptr[-1]) + (ptr[CksumSize - 1]);
     return incr_state;
   }
 
@@ -140,7 +132,7 @@ struct rabin_karp : public cksum_params<SELF> {
 };
 
 MEMBER
-struct adler32_cksum : public cksum_params<SELF> {
+struct large_cksum : public cksum_params<SELF> {
   Word step(const uint8_t *ptr) {
     return xd3_large_cksum (ptr, CksumSize);
   }
@@ -168,15 +160,15 @@ struct file_stats {
   typedef typename table_type::iterator table_iterator;
   typedef typename ptr_list::iterator ptr_iterator;
 
-  int CksumSize;
-  int cksum_skip;
-  int unique;
-  int unique_values;
-  int count;
+  usize_t cksum_size;
+  usize_t cksum_skip;
+  usize_t unique;
+  usize_t unique_values;
+  usize_t count;
   table_type table;
 
-  file_stats(int size, int skip)
-    : CksumSize(size),
+  file_stats(usize_t size, usize_t skip)
+    : cksum_size(size),
       cksum_skip(skip),
       unique(0),
       unique_values(0),
@@ -204,7 +196,7 @@ struct file_stats {
     for (ptr_iterator p_i = pl.begin();
          p_i != pl.end();
          ++p_i) {
-      if (memcmp(*p_i, ptr, CksumSize) == 0) {
+      if (memcmp(*p_i, ptr, cksum_size) == 0) {
         return;
       }
     }
@@ -228,28 +220,20 @@ struct test_result_base {
   }
   virtual void reset() = 0;
   virtual void print() = 0;
-  virtual void get(const uint8_t* buf, const int buf_size, int iters) = 0;
+  virtual void get(const uint8_t* buf, const size_t buf_size, 
+                   usize_t iters) = 0;
   virtual void stat() = 0;
-  virtual int count() = 0;
-  virtual int dups() = 0;
+  virtual usize_t count() = 0;
+  virtual usize_t dups() = 0;
   virtual double uniqueness() = 0;
   virtual double fullness() = 0;
   virtual double collisions() = 0;
   virtual double coverage() = 0;
   virtual double compression() = 0;
   virtual double time() = 0;
-  virtual double score() = 0;
-  virtual void set_score(double min_dups_frac, double min_time) = 0;
   virtual double total_time() = 0;
-  virtual int total_count() = 0;
-  virtual int total_dups() = 0;
-};
-
-struct compare_h {
-  bool operator()(test_result_base *a,
-                  test_result_base *b) {
-    return a->score() < b->score();
-  }
+  virtual usize_t total_count() = 0;
+  virtual usize_t total_dups() = 0;
 };
 
 template <typename Checksum>
@@ -257,25 +241,24 @@ struct test_result : public test_result_base {
   Checksum cksum;
   const char *test_name;
   file_stats<typename Checksum::word_type> fstats;
-  int test_size;
-  int n_steps;
-  int n_incrs;
-  int s_bits;
-  int s_mask;
-  int t_entries;
-  int h_bits;
-  int h_buckets_full;
-  double h_score;
+  usize_t test_size;
+  usize_t n_steps;
+  usize_t n_incrs;
+  typename Checksum::word_type s_bits;
+  typename Checksum::word_type s_mask;
+  usize_t t_entries;
+  usize_t h_bits;
+  usize_t h_buckets_full;
   char *hash_table;
   long accum_millis;
-  int accum_iters;
+  usize_t accum_iters;
 
   // These are not reset
   double accum_time;
-  int accum_count;
-  int accum_dups;
-  int accum_colls;
-  int accum_size;
+  usize_t accum_count;
+  usize_t accum_dups;
+  usize_t accum_colls;
+  size_t accum_size;
 
   test_result(const char *name)
     : test_name(name),
@@ -297,18 +280,18 @@ struct test_result : public test_result_base {
 
   void reset() {
     // size of file
-    test_size = -1;
+    test_size = 0;
 
     // count
-    n_steps = -1;
-    n_incrs = -1;
+    n_steps = 0;
+    n_incrs = 0;
 
     // four values used by new_table()/summarize_table()
-    s_bits = -1;
-    s_mask = -1;
-    t_entries = -1;
-    h_bits = -1;
-    h_buckets_full = -1;
+    s_bits = 0;
+    s_mask = 0;
+    t_entries = 0;
+    h_bits = 0;
+    h_buckets_full = 0;
 
     accum_millis = 0;
     accum_iters = 0;
@@ -322,7 +305,7 @@ struct test_result : public test_result_base {
     }
   }
 
-  int count() {
+  usize_t count() {
     if (Checksum::cksum_skip == 1) {
       return n_incrs;
     } else {
@@ -330,12 +313,17 @@ struct test_result : public test_result_base {
     }
   }
 
-  int dups() {
+  usize_t dups() {
     return fstats.count - fstats.unique;
   }
 
-  int colls() {
-    return fstats.unique - fstats.unique_values;
+  /* Fraction of distinct strings of length cksum_size which are not
+   * represented in the hash table. */
+  double collisions() {
+    return (fstats.unique - fstats.unique_values) / fstats.unique;
+  }
+  usize_t colls() {
+    return (fstats.unique - fstats.unique_values);
   }
 
   double uniqueness() {
@@ -346,10 +334,6 @@ struct test_result : public test_result_base {
     return (double) h_buckets_full / (1 << h_bits);
   }
 
-  double collisions() {
-    return (double) colls() / fstats.unique;
-  }
-
   double coverage() {
     return (double) h_buckets_full / uniqueness() / count();
   }
@@ -362,28 +346,19 @@ struct test_result : public test_result_base {
     return (double) accum_millis / accum_iters;
   }
 
-  double score() {
-    return h_score;
-  }
-
-  void set_score(double min_compression, double min_time) {
-    h_score = (compression() - 0.99 * min_compression)
-      * (time() - 0.99 * min_time);
-  }
-
   double total_time() {
     return accum_time;
   }
 
-  int total_count() {
+  usize_t total_count() {
     return accum_count;
   }
 
-  int total_dups() {
+  usize_t total_dups() {
     return accum_dups;
   }
 
-  int total_colls() {
+  usize_t total_colls() {
     return accum_dups;
   }
 
@@ -400,26 +375,29 @@ struct test_result : public test_result_base {
       fprintf(stderr, "internal error: %d != %d\n", fstats.count, count());
       abort();
     }
-    printf("%s: (%u#%u) count %u uniq %0.2f%% full %u (%0.4f%% coll %0.4f%%) "
-           "covers %0.2f%% w/ 2^%d @ %.4f MB/s %u iters\n",
+    {
+      static int hdr_cnt = 0;
+      if (hdr_cnt++ % 20 == 0) {
+        printf("Name\tConf\tCount\tUniq\tFull\tColl\tCov\tMB/s\tIters\n");
+      }
+    }
+    printf("%s\t%d/%d/1<<%d\t%u\t%0.2f\t%.2f\t%.2f\t%.2f\t%.4f\t%u\n",
            test_name,
            Checksum::cksum_size,
            Checksum::cksum_skip,
-           count(),
-           100.0 * uniqueness(),
-           h_buckets_full,
-           100.0 * fullness(),
-           100.0 * collisions(),
-           100.0 * coverage(),
            h_bits,
+           count(),
+           uniqueness(),
+           fullness(),
+           collisions(),
+           coverage(),
            0.001 * accum_iters * test_size / accum_millis,
            accum_iters);
   }
 
-  int size_log2 (int slots)
-  {
-    int bits = bitsof<typename Checksum::word_type>() - 1;
-    int i;
+  usize_t size_log2 (usize_t slots) {
+    usize_t bits = bitsof<typename Checksum::word_type>() - 1;
+    usize_t i;
 
     for (i = 3; i <= bits; i += 1) {
       if (slots <= (1 << i)) {
@@ -430,31 +408,31 @@ struct test_result : public test_result_base {
     return bits;
   }
 
-  void new_table(int entries) {
+  void new_table(usize_t entries) {
     t_entries = entries;
     h_bits = size_log2(entries);
 
-    int n = 1 << h_bits;
+    usize_t n = 1 << h_bits;
 
     s_bits = bitsof<typename Checksum::word_type>() - h_bits;
-    s_mask = n - 1;
+    s_mask = n - 1U;
 
     hash_table = new char[n / 8];
     memset(hash_table, 0, n / 8);
   }
 
-  int get_table_bit(int i) {
+  int get_table_bit(usize_t i) {
     return hash_table[i/8] & (1 << i%8);
   }
 
-  int set_table_bit(int i) {
+  int set_table_bit(usize_t i) {
     return hash_table[i/8] |= (1 << i%8);
   }
 
   void summarize_table() {
-    int n = 1 << h_bits;
-    int f = 0;
-    for (int i = 0; i < n; i++) {
+    usize_t n = 1 << h_bits;
+    usize_t f = 0;
+    for (usize_t i = 0; i < n; i++) {
       if (get_table_bit(i)) {
         f++;
       }
@@ -462,12 +440,12 @@ struct test_result : public test_result_base {
     h_buckets_full = f;
   }
 
-  void get(const uint8_t* buf, const int buf_size, int test_iters) {
+  void get(const uint8_t* buf, const size_t buf_size, usize_t test_iters) {
     typename Checksum::hash_type hash;
     const uint8_t *ptr;
     const uint8_t *end;
+    usize_t periods;
     int last_offset;
-    int periods;
     int stop;
 
     test_size = buf_size;
@@ -488,7 +466,7 @@ struct test_result : public test_result_base {
     // Compute file stats once.
     if (fstats.unique_values == 0) {
       if (Checksum::cksum_skip == 1) {
-        for (int i = 0; i <= buf_size - Checksum::cksum_size; i++) {
+        for (size_t i = 0; i <= buf_size - Checksum::cksum_size; i++) {
           fstats.update(hash(cksum.step(buf + i), s_bits, s_mask), buf + i);
         }
       } else {
@@ -507,7 +485,7 @@ struct test_result : public test_result_base {
     if (Checksum::cksum_skip != 1) {
       new_table(n_steps);
 
-      for (int i = 0; i < test_iters; i++) {
+      for (usize_t i = 0; i < test_iters; i++) {
         ptr = buf + last_offset;
         end = buf + stop;
 
@@ -528,7 +506,7 @@ struct test_result : public test_result_base {
 
       new_table(n_incrs);
 
-      for (int i = 0; i < test_iters; i++) {
+      for (usize_t i = 0; i < test_iters; i++) {
         ptr = buf;
         end = buf + stop;
 
@@ -608,29 +586,31 @@ int main(int argc, char** argv) {
     return 1;
   }
 
-#define TEST(T,Z,S,P,H,C)                                      \
-  test_result<rabin_karp<T,Z,S,P,H<T>,C>>                       \
-    _rka_ ## T ## _ ## Z ## _ ## S ## _ ## P ## _ ## H ## _ ## C        \
-    ("rka_" #T "_" #Z "_" #S "_" #P "_" #H "_" #C);             \
-  test_result<adler32_cksum<T,Z,S,P,H<T>,C>>                            \
-    _a32_ ## T ## _ ## Z ## _ ## S ## _ ## P ## _ ## H ## _ ## C        \
-    ("a32_" #T "_" #Z "_" #S "_" #P "_" #H "_" #C)
+#define TEST(T,Z,S,H,C)                                      \
+  test_result<rabin_karp<T,Z,S,H<T>,C>>                 \
+    _rka_ ## T ## _ ## Z ## _ ## S ## _ ## H ## _ ## C  \
+    ("rka_" #T "_" #Z "_" #S "_" #H "_" #C);            \
+  test_result<large_cksum<T,Z,S,H<T>,C>>                                \
+    _xck_ ## T ## _ ## Z ## _ ## S ## _ ## H ## _ ## C                  \
+    ("xck_" #T "_" #Z "_" #S "_" #H "_" #C)
 
 
 #define TESTS(SIZE, SKIP)                               \
-  TEST(uint32_t, SIZE, SKIP, randperm, hhash, 1);       \
-  TEST(uint32_t, SIZE, SKIP, plain, hhash, 1);          \
-  TEST(uint32_t, SIZE, SKIP, randperm, hhash, 2);       \
-  TEST(uint32_t, SIZE, SKIP, plain, hhash, 2);          \
-  TEST(uint32_t, SIZE, SKIP, randperm, hhash, 3);       \
-  TEST(uint32_t, SIZE, SKIP, plain, hhash, 3)
+  TEST(uint32_t, SIZE, SKIP, nonhash, 1);               \
+  TEST(uint32_t, SIZE, SKIP, nonhash, 2);               \
+  TEST(uint32_t, SIZE, SKIP, hhash, 1);                 \
+  TEST(uint32_t, SIZE, SKIP, hhash, 2);                 \
+  TEST(uint64_t, SIZE, SKIP, nonhash, 1);               \
+  TEST(uint64_t, SIZE, SKIP, nonhash, 2);               \
+  TEST(uint64_t, SIZE, SKIP, hhash, 1);                 \
+  TEST(uint64_t, SIZE, SKIP, hhash, 2)
   
-  // TESTS(9, 9);
+  TESTS(9, 9);
   // TESTS(9, 15);
-  // TESTS(15, 15);
+  TESTS(15, 15);
   TESTS(127, 127);
   // TESTS(127, 211);
-  // TESTS(211, 211);
+  TESTS(211, 211);
 
   for (i = 1; i < argc; i++) {
     if ((ret = read_whole_file(argv[i],
@@ -650,7 +630,7 @@ int main(int argc, char** argv) {
       test_result_base *test = *iter;
       test->reset();
 
-      int iters = 100;
+      usize_t iters = 100;
       long start_test = get_millisecs_now();
 
       do {
diff --git a/xdelta3/testing/checksum_test_c.c b/xdelta3/testing/checksum_test_c.c
new file mode 100644
index 0000000..2b32019
--- /dev/null
+++ b/xdelta3/testing/checksum_test_c.c
@@ -0,0 +1 @@
+#include "../xdelta3.c"
diff --git a/xdelta3/xdelta3-hash.h b/xdelta3/xdelta3-hash.h
index bcdddc3..fd18099 100644
--- a/xdelta3/xdelta3-hash.h
+++ b/xdelta3/xdelta3-hash.h
@@ -1,5 +1,6 @@
 /* xdelta 3 - delta compression tools and library
- * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007.  Joshua P. MacDonald
+ * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007, 2011, 2012, 2014.
+ * Joshua P. MacDonald
  *
  *  This program is free software; you can redistribute it and/or modify
  *  it under the terms of the GNU General Public License as published by
@@ -34,37 +35,17 @@
 #define SMALL_HASH_DEBUG2(s,inp)
 #endif /* XD3_DEBUG */
 
-/* This is a good hash multiplier for 32-bit LCGs: see "linear
- * congruential generators of different sizes and good lattice
- * structure" */
-static const uint32_t hash_multiplier = 1597334677U;
-
-/***********************************************************************
- Permute stuff
- ***********************************************************************/
-
-/* Update the checksum state. */
-#if ADLER_LARGE_CKSUM
-inline uint32_t
-xd3_large_cksum_update (uint32_t cksum,
-                        const uint8_t *base,
-                        usize_t look) {
-  uint32_t old_c = PERMUTE(base[0]);
-  uint32_t new_c = PERMUTE(base[look]);
-  uint32_t low   = ((cksum & 0xffff) - old_c + new_c) & 0xffff;
-  uint32_t high  = ((cksum >> 16) - (old_c * look) + low) & 0xffff;
-  return (high << 16) | low;
-}
-#else
-/* TODO: revisit this topic */
-#endif
-
 #if UNALIGNED_OK
 #define UNALIGNED_READ32(dest,src) (*(dest)) = (*(uint32_t*)(src))
 #else
 #define UNALIGNED_READ32(dest,src) memcpy((dest), (src), 4);
 #endif
 
+/* This is a good hash multiplier for 32-bit LCGs: see "linear
+ * congruential generators of different sizes and good lattice
+ * structure" */
+static const uint32_t hash_multiplier = 1597334677U;
+
 /* TODO: small cksum is hard-coded for 4 bytes (i.e., "look" is unused) */
 static inline uint32_t
 xd3_scksum (uint32_t *state,
@@ -83,41 +64,111 @@ xd3_small_cksum_update (uint32_t *state,
   return (*state) * hash_multiplier;
 }
 
-/***********************************************************************
- Ctable stuff
- ***********************************************************************/
-
 static inline usize_t
 xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum)
 {
   return (cksum >> cfg->shift) ^ (cksum & cfg->mask);
 }
 
-/***********************************************************************
- Cksum function
- ***********************************************************************/
+#if XD3_ENCODER
+#define PERMUTE32(x) (__single_hash32[x])
+extern const uint16_t __single_hash32[256];
 
-#if ADLER_LARGE_CKSUM
-inline usize_t
-xd3_large_cksum (const uint8_t *seg, const usize_t ln)
+inline uint32_t
+xd3_large32_cksum (const uint8_t *seg, const usize_t ln)
 {
+  static const uint32_t kBits = 16;
+  static const uint32_t kMask = 0xffff;
   usize_t i = 0;
   uint32_t low  = 0;
   uint32_t high = 0;
 
   for (; i < ln; i += 1)
     {
-      low  += PERMUTE(*seg++);
+      low  += PERMUTE32(*seg++);
+      high += low;
+    }
+
+  return ((high & kMask) << kBits) | (low & kMask);
+}
+
+inline uint32_t
+xd3_large32_cksum_update (uint32_t cksum,
+                          const uint8_t *base,
+                          usize_t look) 
+{
+  static const uint32_t kBits = 16;
+  static const uint32_t kMask = 0xffff;
+  uint32_t old_c = PERMUTE32(base[0]);
+  uint32_t new_c = PERMUTE32(base[look]);
+  uint32_t low   = ((cksum & kMask) - old_c + new_c) & kMask;
+  uint32_t high  = ((cksum >> kBits) - (old_c * look) + low) & kMask;
+  return (high << kBits) | low;
+}
+
+#undef PERMUTE32
+
+#define PERMUTE64(x) (__single_hash64[x])
+extern const uint32_t __single_hash64[256];
+
+inline uint64_t
+xd3_large64_cksum (const uint8_t *seg, const usize_t len)
+{
+  static const uint64_t kBits = 32;
+  static const uint64_t kMask = 0xffffffff;
+  usize_t i = 0;
+  uint64_t low  = 0;
+  uint64_t high = 0;
+
+  for (; i < len; i += 1)
+    {
+      low  += PERMUTE64(*seg++);
       high += low;
     }
 
-  return ((high & 0xffff) << 16) | (low & 0xffff);
+  return ((high & kMask) << kBits) | (low & kMask);
+}
+
+inline uint64_t
+xd3_large64_cksum_update (uint64_t cksum,
+                          const uint8_t *base,
+                          usize_t look) 
+{
+  static const uint64_t kBits = 32;
+  static const uint64_t kMask = 0xffffffff;
+  uint64_t old_c = PERMUTE64(base[0]);
+  uint64_t new_c = PERMUTE64(base[look]);
+  uint64_t low   = ((cksum & kMask) - old_c + new_c) & kMask;
+  uint64_t high  = ((cksum >> kBits) - (old_c * look) + low) & kMask;
+  return (high << kBits) | low;
+}
+
+#undef PERMUTE64
+
+inline usize_t
+xd3_large_cksum (const uint8_t *seg, const usize_t len) 
+{
+  if (SIZEOF_USIZE_T == 4) 
+    {
+      return xd3_large32_cksum (seg, len);     
+    }
+  else
+    {
+      return xd3_large64_cksum (seg, len);
+    }
 }
+
+inline usize_t
+xd3_large_cksum_update (usize_t cksum,
+                        const uint8_t *base,
+                        usize_t look) {
+#if SIZEOF_USIZE_T == 4
+  return xd3_large32_cksum_update (cksum, base, look);
 #else
-/* TODO */
+  return xd3_large64_cksum_update (cksum, base, look);
 #endif
+}
 
-#if XD3_ENCODER
 static usize_t
 xd3_size_hashtable_bits (usize_t slots)
 {
@@ -139,16 +190,16 @@ xd3_size_hashtable_bits (usize_t slots)
 }
 
 static void
-xd3_size_hashtable (xd3_stream    *stream,
-                    usize_t        slots,
-                    xd3_hash_cfg  *cfg)
+xd3_size_hashtable (xd3_stream   *stream,
+                    usize_t       slots,
+                    xd3_hash_cfg *cfg)
 {
   usize_t bits = xd3_size_hashtable_bits (slots);
 
-  cfg->size  = (1 << bits);
+  cfg->size  = (1U << bits);
   cfg->mask  = (cfg->size - 1);
   cfg->shift = (SIZEOF_USIZE_T * 8) - bits;
 }
-#endif
 
 #endif
+#endif /* _XDELTA3_HASH_H_ */
diff --git a/xdelta3/xdelta3-internal.h b/xdelta3/xdelta3-internal.h
index 773a8e4..d9d56b9 100644
--- a/xdelta3/xdelta3-internal.h
+++ b/xdelta3/xdelta3-internal.h
@@ -1,5 +1,5 @@
 /* xdelta3 - delta compression tools and library
- * Copyright (C) 2011, 2012 Joshua P. MacDonald
+ * Copyright (C) 2011, 2012, 2014 Joshua P. MacDonald
  *
  *  This program is free software; you can redistribute it and/or modify
  *  it under the terms of the GNU General Public License as published by
@@ -47,9 +47,6 @@ void main_free (void *ptr);
 int test_compare_files (const char* f0, const char* f1);
 usize_t xd3_bytes_on_srcblk (xd3_source *src, xoff_t blkno);
 xoff_t xd3_source_eof(const xd3_source *src);
-uint32_t xd3_large_cksum_update (uint32_t cksum,
-                                 const uint8_t *base,
-                                 usize_t look);
 int xd3_encode_init_full (xd3_stream *stream);
 usize_t xd3_pow2_roundup (usize_t x);
 long get_millisecs_now ();
@@ -158,18 +155,9 @@ void xprintf(const char *fmt, ...) PRINTF_ATTRIBUTE(1,2);
 #define UINT64_MAX 18446744073709551615ULL
 #endif
 
-/* TODO Eliminate this framework... */
-#define HASH_PERMUTE       1    /* The input is permuted by random nums */
-#define ADLER_LARGE_CKSUM  1    /* Adler checksum vs. RK checksum */
-
-#if HASH_PERMUTE == 0
-#define PERMUTE(x) (x)
-#else
-#define PERMUTE(x) (__single_hash[x])
-
-extern const uint16_t __single_hash[256];
-#endif
-
 usize_t xd3_large_cksum (const uint8_t *seg, const usize_t ln);
+usize_t xd3_large_cksum_update (usize_t cksum,
+                                const uint8_t *base,
+                                usize_t look);
 
-#endif // XDELTA3_INTERNAL_H__
+#endif /* XDELTA3_INTERNAL_H__ */
diff --git a/xdelta3/xdelta3.c b/xdelta3/xdelta3.c
index 5f52ad9..b8aa9eb 100644
--- a/xdelta3/xdelta3.c
+++ b/xdelta3/xdelta3.c
@@ -535,7 +535,7 @@ static void xd3_verify_run_state (xd3_stream    *stream,
                                   uint8_t       *x_run_c);
 static void xd3_verify_large_state (xd3_stream *stream,
                                     const uint8_t *inp,
-                                    uint32_t x_cksum);
+                                    usize_t x_cksum);
 static void xd3_verify_small_state (xd3_stream    *stream,
                                     const uint8_t *inp,
                                     uint32_t          x_cksum);
@@ -567,17 +567,17 @@ static int         xd3_selftest      (void);
 #define UINT64_OFLOW_MASK 0xfe00000000000000ULL
 
 #if SIZEOF_USIZE_T == 4
-#define USIZE_T_MAX        UINT32_MAX
-#define xd3_decode_size   xd3_decode_uint32_t
-#define xd3_emit_size     xd3_emit_uint32_t
-#define xd3_sizeof_size   xd3_sizeof_uint32_t
-#define xd3_read_size     xd3_read_uint32_t
+#define USIZE_T_MAX             UINT32_MAX
+#define xd3_decode_size         xd3_decode_uint32_t
+#define xd3_emit_size           xd3_emit_uint32_t
+#define xd3_sizeof_size         xd3_sizeof_uint32_t
+#define xd3_read_size           xd3_read_uint32_t
 #elif SIZEOF_USIZE_T == 8
-#define USIZE_T_MAX        UINT64_MAX
-#define xd3_decode_size   xd3_decode_uint64_t
-#define xd3_emit_size     xd3_emit_uint64_t
-#define xd3_sizeof_size   xd3_sizeof_uint64_t
-#define xd3_read_size     xd3_read_uint64_t
+#define USIZE_T_MAX             UINT64_MAX
+#define xd3_decode_size         xd3_decode_uint64_t
+#define xd3_emit_size           xd3_emit_uint64_t
+#define xd3_sizeof_size         xd3_sizeof_uint64_t
+#define xd3_read_size           xd3_read_uint64_t
 #endif
 
 #if SIZEOF_XOFF_T == 4
@@ -798,10 +798,9 @@ const xd3_sec_type lzma_sec_type =
 #endif /* __XDELTA3_C_HEADER_PASS__ */
 #ifdef __XDELTA3_C_INLINE_PASS__
 
-const uint16_t __single_hash[256] =
+const uint16_t __single_hash32[256] =
 {
-  /* Random numbers generated using SLIB's pseudo-random number generator.
-   * This hashes the input alphabet. */
+  /* This hashes the input alphabet (Scheme SLIB pseudo-random). */
   0xbcd1, 0xbb65, 0x42c2, 0xdffe, 0x9666, 0x431b, 0x8504, 0xeb46,
   0x6379, 0xd460, 0xcf14, 0x53cf, 0xdb51, 0xdb08, 0x12c8, 0xf602,
   0xe766, 0x2394, 0x250d, 0xdcbb, 0xa678, 0x02af, 0xa5c6, 0x7ea6,
@@ -836,6 +835,75 @@ const uint16_t __single_hash[256] =
   0x1672, 0xec28, 0x6acb, 0x86cc, 0x186e, 0x9414, 0xd674, 0xd1a5
 };
 
+const uint32_t __single_hash64[256] =
+{
+  /* http://random.org 2014.10.24 */
+  0xd25e9f0a, 0xb1af9d5e, 0xb753dfa2, 0x157050f7,  /* 0 */
+  0xc84b072c, 0xdd14fe7c, 0xf92208c3, 0xdf08a0c0,
+  0x63a5c118, 0x76f5d90f, 0xa2f8b93e, 0xb6c12d22,
+  0xaf074957, 0x966fb7d9, 0x62f7b785, 0xb40e8a09,
+  0x0a811d5d, 0x323a6daa, 0xb62f7c5b, 0xfdcb9a53,
+  0xf25a9067, 0x4506bc7a, 0xff58a74b, 0x5ae62817,
+  0x74097675, 0x722c0fd9, 0x116a2a66, 0x65f76728,
+  0x72c79651, 0xe043cf9d, 0x64b867c7, 0x6604834f,
+  0xcdca58a6, 0x0f164e2d, 0x24515f05, 0x632cdbf8,
+  0x18091d4a, 0x3eff4128, 0x673d1c33, 0xd8e10c71,
+  0x1a3edf11, 0xba52892f, 0xa56949e0, 0xf3e1dd77,  /* 10 */
+  0x86fcbe3e, 0x138d66d0, 0x4fc98359, 0xc22e5dd6,
+  0xc59f2267, 0x6c6dd739, 0xe03da190, 0x07e8469c,
+  0xadcfb02c, 0x00d3b0d9, 0xa1f44918, 0x8bd84d87,
+  0x08ec9ec1, 0xbbcd156f, 0xb57718e3, 0x3177e752,
+  0xf52a4d70, 0xde7aaad9, 0x075f1da0, 0x21ba00c6,
+  0xb9469a5c, 0xcf08d5ba, 0x91ac9edc, 0xc6167b63,
+  0xc1974919, 0xc8c8d195, 0x4b1996dd, 0xeff8991c,
+  0xf7f66c6b, 0x25b012e2, 0x59d12a98, 0xea40d3cc,
+  0x41f9970b, 0xec48101a, 0xa3bdcf90, 0x99f16905,
+  0x27af6c97, 0xc849af37, 0x49cad89b, 0xf48c2278,  /* 20 */
+  0x5529c3d8, 0x9e7d6dce, 0x16feb52d, 0xf1b0aca1,
+  0xaf28fccb, 0x48e4ce3c, 0xc4436617, 0x64524e3e,
+  0x61806681, 0x6384f2d7, 0x1172880f, 0x34a5ef5f,
+  0xcc8cc0a8, 0x66e8f100, 0x2866085f, 0xba9b1b2d,
+  0x51285949, 0x2be4b574, 0x889b1ef5, 0x3dbe920d,
+  0x9277a62f, 0x0584a9f6, 0x085d8fc4, 0x4b5d403d,
+  0x4e46ca78, 0x3294c2f9, 0x29313e70, 0xe4f09b24,
+  0xe73b331c, 0x072f5552, 0x2e390b78, 0xea0021ca,
+  0xd8f40320, 0xed0e16fd, 0x7de9cf7a, 0xf17e3d6c,
+  0x8df1bd85, 0x052cae67, 0x3486e512, 0x3a1c09b8,  /* 30 */
+  0x6c2a7b4e, 0x83455753, 0xbc0353ac, 0x0ffe20b6,
+  0x5fdcef85, 0x010f506c, 0x595ce972, 0xe28680d0,
+  0xa7e216b2, 0xa392ee0f, 0x25b73faa, 0x2b1f4983,
+  0xeeaefe98, 0x1d3d9cbc, 0x6aebe97b, 0x8b7b3584,
+  0x9e6a9a07, 0xd37f1e99, 0x4ac2a441, 0x8ae9a213,
+  0x7d0e27d7, 0x5de54b9a, 0x8621de1f, 0xf0f2f866,
+  0xcb08d275, 0x49c3f87e, 0xd5ee68c1, 0x9802fc77,
+  0x68be6c5e, 0x65aa8c27, 0xf423d5f7, 0x10ec5502,
+  0x9909bce1, 0x509cdf1b, 0x338fea72, 0x2733e9bf,
+  0xf92f4fd7, 0x87738ea2, 0x931a8bbc, 0x0a5c9155,  /* 40 */
+  0xbe5edd9b, 0xadbf5838, 0x0338f8d2, 0x290da210,
+  0x390c37d8, 0xe7cffae8, 0x20617ebe, 0x464322dd,
+  0x7b3c4e78, 0xac142dcb, 0x2d5cef76, 0xd8fe49fc,
+  0x60f4e9a9, 0x7473816f, 0x0dc35f39, 0x5eed80c1,
+  0x0cb55ab6, 0x1d3ac541, 0x13c7f529, 0x7bffdf4a,
+  0xe334785b, 0x85263ec1, 0xd132ae56, 0x7c868b9e,
+  0x47f60638, 0x1012b979, 0x81c31dd3, 0x1af868c8,
+  0x0c5d0742, 0xd1b3e1a2, 0x5873200a, 0xf848465c,
+  0x0fc4d596, 0x609c18af, 0xc9f5a480, 0xd1a94a84,
+  0xa1431a3f, 0x7de8bb1a, 0x25f1256b, 0x1dcc732c,  /* 50 */
+  0x6aa1549a, 0xa2367281, 0x32f2a77e, 0x82e62a0f,
+  0x045cbb56, 0x74b2027c, 0xd71a32d9, 0x022e7cb5,
+  0xe99be177, 0x60222fdf, 0xd69681ca, 0x9008ee2c,
+  0x32923db4, 0xcf82bf97, 0x38960a5b, 0xb3503d5b,
+  0x9bd4c7f2, 0x33c029c8, 0x1ef504a3, 0xdb249d3b,
+  0x91e89676, 0x4ca43b36, 0x9191433c, 0x465d5dc4,
+  0xf4dcb118, 0x9d11dd00, 0xb592f058, 0xdbe5ce30,
+  0x74790d92, 0x779850a8, 0x7180d25b, 0xfa951d99,
+  0x5990935a, 0x921cb022, 0x3b7c39bc, 0x6a38a7c7,
+  0xdc22703b, 0x142bab3b, 0x4e3d9479, 0x44bb8482,  /* 60 */
+  0x8043abce, 0xfebe832a, 0x8e6a2f98, 0x4d43c4fe,
+  0xd192a70a, 0x802f3c3a, 0x5d11bbab, 0x2665d241,
+  0xb3f3a680, 0x3a8d223f, 0xcf82cdb4, 0x4ed28743,
+};
+
 /****************************************************************
  Instruction tables
  *****************************************************************/
@@ -952,7 +1020,7 @@ xd3_build_code_table (const xd3_code_table_desc *desc, xd3_dinst *tbl)
 {
   uint8_t size1, size2;
   uint8_t mode;
-  usize_t cpy_modes = 2 + desc->near_modes + desc->same_modes;
+  usize_t cpy_modes = 2U + desc->near_modes + desc->same_modes;
   xd3_dinst *d = tbl;
 
   (d++)->type1 = XD3_RUN;
@@ -968,7 +1036,7 @@ xd3_build_code_table (const xd3_code_table_desc *desc, xd3_dinst *tbl)
     {
       (d++)->type1 = XD3_CPY + mode;
 
-      for (size1 = MIN_MATCH; size1 < MIN_MATCH + desc->cpy_sizes; 
+      for (size1 = MIN_MATCH; size1 < MIN_MATCH + desc->cpy_sizes;
            size1 += 1, d += 1)
         {
           d->type1 = XD3_CPY + mode;
@@ -1078,8 +1146,8 @@ xd3_choose_instruction (xd3_rinst *prev, xd3_rinst *inst)
                 if ( (inst->size <= 6) &&
                      (mode       <= 5) )
                   {
-                    prev->code2 = (uint8_t)(163 + (mode * 12) + 
-                                            (3 * (prev->size - 1)) + 
+                    prev->code2 = (uint8_t)(163 + (mode * 12) +
+                                            (3 * (prev->size - 1)) +
                                             (inst->size - 4));
                     XD3_ASSERT (prev->code2 <= 234);
                   }
@@ -1358,10 +1426,10 @@ xd3_emit_bytes (xd3_stream     *stream,
  Integer encoder/decoder functions
  **********************************************************************/
 
-#define DECODE_INTEGER_TYPE(PART,OFLOW)                                \
+#define DECODE_INTEGER_TYPE(TYPE,PART,OFLOW)                           \
   while (stream->avail_in != 0)                                        \
     {                                                                  \
-      usize_t next = stream->next_in[0];                               \
+      TYPE next = stream->next_in[0];                                  \
                                                                        \
       DECODE_INPUT(1);                                                 \
                                                                        \
@@ -1386,8 +1454,8 @@ xd3_emit_bytes (xd3_stream     *stream,
 
 #define READ_INTEGER_TYPE(TYPE, OFLOW)                                 \
   TYPE val = 0;                                                        \
+  TYPE next;                                                           \
   const uint8_t *inp = (*inpp);                                        \
-  usize_t next;                                                        \
                                                                        \
   do                                                                   \
     {                                                                  \
@@ -1447,7 +1515,7 @@ xd3_sizeof_uint32_t (uint32_t num)
 
 int
 xd3_decode_uint32_t (xd3_stream *stream, uint32_t *val)
-{ DECODE_INTEGER_TYPE (stream->dec_32part, UINT32_OFLOW_MASK); }
+{ DECODE_INTEGER_TYPE (uint32_t, stream->dec_32part, UINT32_OFLOW_MASK); }
 
 int
 xd3_read_uint32_t (xd3_stream *stream, const uint8_t **inpp,
@@ -1464,7 +1532,7 @@ xd3_emit_uint32_t (xd3_stream *stream, xd3_output **output, uint32_t num)
 #if USE_UINT64
 int
 xd3_decode_uint64_t (xd3_stream *stream, uint64_t *val)
-{ DECODE_INTEGER_TYPE (stream->dec_64part, UINT64_OFLOW_MASK); }
+{ DECODE_INTEGER_TYPE (uint64_t, stream->dec_64part, UINT64_OFLOW_MASK); }
 
 #if XD3_ENCODER
 int
@@ -2525,7 +2593,8 @@ xd3_iopt_finish_encoding (xd3_stream *stream, xd3_rinst *inst)
     {
       if (stream->iout->code2 != 0)
         {
-          if ((ret = xd3_emit_double (stream, stream->iout, inst, stream->iout->code2))) { return ret; }
+          if ((ret = xd3_emit_double (stream, stream->iout, inst, 
+                                      stream->iout->code2))) { return ret; }
 
           xd3_iopt_free_nonadd (stream, stream->iout);
           xd3_iopt_free_nonadd (stream, inst);
@@ -3612,7 +3681,7 @@ xd3_process_stream (int            is_encode,
         case XD3_OUTPUT: { /* memcpy below */ break; }
         case XD3_INPUT: {
           n = min(stream->winsize, input_size - ipos);
-          if (n == 0) 
+          if (n == 0)
             {
               goto done;
             }
@@ -3948,13 +4017,13 @@ xd3_srcwin_setup (xd3_stream *stream)
 
   if (src->eof_known)
     {
-      /* Note: if the source size is known, we must reduce srclen or 
+      /* Note: if the source size is known, we must reduce srclen or
        * code that expects to pass a single block w/ getblk == NULL
        * will not function, as the code will return GETSRCBLK asking
        * for the second block. */
       src->srclen = min (src->srclen, xd3_source_eof(src) - src->srcbase);
     }
-  
+
   IF_DEBUG1 (DP(RINT "[srcwin_setup_constrained] base %llu len %llu\n",
                 src->srcbase, src->srclen));
 
@@ -4545,7 +4614,7 @@ xd3_smatch (xd3_stream *stream,
 static void
 xd3_verify_small_state (xd3_stream    *stream,
                         const uint8_t *inp,
-                        uint32_t          x_cksum)
+                        uint32_t       x_cksum)
 {
   uint32_t state;
   uint32_t cksum = xd3_scksum (&state, inp, stream->smatcher.small_look);
@@ -4556,9 +4625,9 @@ xd3_verify_small_state (xd3_stream    *stream,
 static void
 xd3_verify_large_state (xd3_stream    *stream,
                         const uint8_t *inp,
-                        uint32_t          x_cksum)
+                        usize_t        x_cksum)
 {
-  uint32_t cksum = xd3_large_cksum (inp, stream->smatcher.large_look);
+  usize_t cksum = xd3_large_cksum (inp, stream->smatcher.large_look);
   XD3_ASSERT (cksum == x_cksum);
 }
 static void
@@ -4702,7 +4771,7 @@ xd3_srcwin_move_point (xd3_stream *stream, usize_t *next_move_point)
 
       do
         {
-          uint32_t cksum = xd3_large_cksum (stream->src->curblk + blkpos,
+          usize_t cksum = xd3_large_cksum (stream->src->curblk + blkpos,
                                        stream->smatcher.large_look);
           usize_t hval = xd3_checksum_hash (& stream->large_hash, cksum);
 
@@ -4795,7 +4864,7 @@ XD3_TEMPLATE(xd3_string_match_) (xd3_stream *stream)
   const uint8_t *inp;
   uint32_t       scksum = 0;
   uint32_t       scksum_state = 0;
-  uint32_t       lcksum = 0;
+  usize_t        lcksum = 0;
   usize_t        sinx;
   usize_t        linx;
   uint8_t        run_c;
diff --git a/xdelta3/xdelta3.h b/xdelta3/xdelta3.h
index 31603f0..1fd55b0 100644
--- a/xdelta3/xdelta3.h
+++ b/xdelta3/xdelta3.h
@@ -1,6 +1,6 @@
 /* xdelta 3 - delta compression tools and library
  * Copyright (C) 2001, 2003, 2004, 2005, 2006, 2007,
- * 2008, 2009, 2010, 2011, 2012, 2013.  Joshua P. MacDonald
+ * 2008, 2009, 2010, 2011, 2012, 2013, 2014.  Joshua P. MacDonald
  *
  *  This program is free software; you can redistribute it and/or modify
  *  it under the terms of the GNU General Public License as published by
@@ -720,7 +720,7 @@ struct _xd3_config
   xd3_alloc_func    *alloc;
   xd3_free_func     *freef;
   void              *opaque;        /* Not used. */
-  int                flags;         /* stream->flags are initialized
+  uint32_t           flags;         /* stream->flags are initialized
                                      * from xd3_config & never
                                      * modified by the library.  Use
                                      * xd3_set_flags to modify flags
@@ -1249,7 +1249,7 @@ const char* xd3_strerror (int ret);
    specified flags. */
 static inline
 void    xd3_init_config (xd3_config *config,
-                         int         flags)
+                         uint32_t    flags)
 {
   memset (config, 0, sizeof (*config));
   config->flags = flags;