8 files changed, 993 insertions, 53 deletions

diff --git a/xdelta3/testing/Makefile b/xdelta3/testing/Makefile
index f859f94..d0b9c9e 100644
--- a/xdelta3/testing/Makefile
+++ b/xdelta3/testing/Makefile
@@ -3,3 +3,6 @@ all:
 
 xdelta3regtest:
         (cd .. && make xdelta3regtest)
+
+xdelta3checksum:
+        (cd .. && make xdelta3checksum)
diff --git a/xdelta3/testing/checksum_test.cc b/xdelta3/testing/checksum_test.cc
new file mode 100644
index 0000000..9418d24
--- /dev/null
+++ b/xdelta3/testing/checksum_test.cc
@@ -0,0 +1,756 @@
+/* Copyright (C) 2007 Josh MacDonald */
+
+#include "test.h"
+#include <assert.h>
+#include <list>
+#include <vector>
+#include <algorithm>
+
+#include "../cpp-btree/btree_map.h"
+
+extern "C" {
+uint32_t xd3_large32_cksum_old (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look);
+uint32_t xd3_large32_cksum_update_old (xd3_hash_cfg *cfg, uint32_t cksum, 
+                                       const uint8_t *base, const usize_t look);
+
+uint64_t xd3_large64_cksum_old (xd3_hash_cfg *cfg, const uint8_t *base, const usize_t look);
+uint64_t xd3_large64_cksum_update_old (xd3_hash_cfg *cfg, uint64_t cksum, 
+                                       const uint8_t *base, const usize_t look);
+}
+
+using btree::btree_map;
+using std::list;
+using std::vector;
+
+// MLCG parameters
+// a, a*
+uint32_t good_32bit_values[] = {
+  1597334677U, // ...
+  741103597U, 887987685U,
+};
+
+// a, a*
+uint64_t good_64bit_values[] = {
+  1181783497276652981ULL, 4292484099903637661ULL,
+  7664345821815920749ULL, // ...
+};
+
+void print_header() {
+  static int hdr_cnt = 0;
+  if (hdr_cnt++ % 20 == 0) {
+    printf("%-32sConf\t\tCount\tUniq\tFull\tCover\tColls"
+           "\tMB/s\tIters\t#Colls\n", "Name");
+  }
+}
+
+struct true_type { };
+struct false_type { };
+
+template <typename Word>
+usize_t bitsof();
+
+template<>
+usize_t bitsof<unsigned int>() {
+  return sizeof(unsigned int) * 8;
+}
+
+template<>
+usize_t bitsof<unsigned long>() {
+  return sizeof(unsigned long) * 8;
+}
+
+template<>
+usize_t bitsof<unsigned long long>() {
+  return sizeof(unsigned long long) * 8;
+}
+
+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>
+Word good_word();
+
+template<>
+uint32_t good_word<uint32_t>() {
+  return good_32bit_values[0];
+}
+
+template<>
+uint64_t good_word<uint64_t>() {
+  return good_64bit_values[0];
+}
+
+// CLASSES
+
+#define SELF Word, CksumSize, CksumSkip, Hash, Compaction
+#define MEMBER template <typename Word,         \
+                         int CksumSize,         \
+                         int CksumSkip,         \
+                         typename Hash,         \
+                         int Compaction>
+
+MEMBER
+struct cksum_params {
+  typedef Word word_type;
+  typedef Hash hash_type;
+
+  static const int cksum_size = CksumSize;
+  static const int cksum_skip = CksumSkip;
+  static const int compaction = Compaction;
+};
+
+MEMBER
+struct rabin_karp : public cksum_params<SELF> {
+  // (a^cksum_size-1 c_0) + (a^cksum_size-2 c_1) ...
+  rabin_karp()
+    : powers(make_powers()),
+      product(powers[0] * good_word<Word>()),
+      incr_state(0) { }
+
+  static Word* make_powers() {
+    Word *p = new Word[CksumSize];
+    p[CksumSize - 1] = 1;
+    for (int i = CksumSize - 2; i >= 0; i--) {
+      p[i] = p[i + 1] * good_word<Word>();
+    }
+    return p;
+  }
+
+  ~rabin_karp() {
+    delete [] powers;
+  }
+
+  Word step(const uint8_t *ptr) {
+    Word h = 0;
+    for (int i = 0; i < CksumSize; i++) {
+      h += (ptr[i]) * powers[i];
+    }
+    return h;
+  }
+
+  Word state0(const uint8_t *ptr) {
+    incr_state = step(ptr);
+    return incr_state;
+  }
+
+  Word incr(const uint8_t *ptr) {
+    incr_state = good_word<Word>() * incr_state -
+      product * (ptr[-1]) + (ptr[CksumSize - 1]);
+    return incr_state;
+  }
+
+  const Word *const powers;
+  const Word  product;
+  Word        incr_state;
+};
+
+MEMBER
+struct with_stream : public cksum_params<SELF> {
+  xd3_stream stream;
+
+  with_stream()
+  {
+    xd3_config cfg;
+    memset (&stream, 0, sizeof (stream));
+    xd3_init_config (&cfg, 0);
+    cfg.smatch_cfg = XD3_SMATCH_SOFT;
+    cfg.smatcher_soft.large_look = CksumSize;
+    cfg.smatcher_soft.large_step = CksumSkip;
+    cfg.smatcher_soft.small_look = 4;
+    cfg.smatcher_soft.small_chain = 4;
+    cfg.smatcher_soft.small_lchain = 4;
+    cfg.smatcher_soft.max_lazy = 4;
+    cfg.smatcher_soft.long_enough = 4;
+    CHECK_EQ(0, xd3_config_stream (&stream, &cfg));
+
+    CHECK_EQ(0, xd3_size_hashtable (&stream,
+                                    1<<10 /* ignored */,
+                                    stream.smatcher.large_look,
+                                    & stream.large_hash));
+  }
+  ~with_stream() 
+  {
+    xd3_free_stream (&stream);
+  }
+};
+
+MEMBER
+struct large_cksum : public with_stream<SELF> {
+  Word step(const uint8_t *ptr) {
+    return xd3_large_cksum (&this->stream.large_hash, ptr, CksumSize);
+  }
+
+  Word state0(const uint8_t *ptr) {
+    incr_state = step(ptr);
+    return incr_state;
+  }
+
+  Word incr(const uint8_t *ptr) {
+    incr_state = xd3_large_cksum_update (&this->stream.large_hash, 
+                                         incr_state, ptr - 1, CksumSize);
+    return incr_state;
+  }
+
+  Word incr_state;
+};
+
+#if SIZEOF_USIZE_T == 4
+#define xd3_large_cksum_old         xd3_large32_cksum_old
+#define xd3_large_cksum_update_old  xd3_large32_cksum_update_old
+#elif SIZEOF_USIZE_T == 8
+#define xd3_large_cksum_old         xd3_large64_cksum_old
+#define xd3_large_cksum_update_old  xd3_large64_cksum_update_old
+#endif
+
+MEMBER
+struct large_cksum_old : public with_stream<SELF> {
+  Word step(const uint8_t *ptr) {
+    return xd3_large_cksum_old (&this->stream.large_hash, ptr, CksumSize);
+  }
+
+  Word state0(const uint8_t *ptr) {
+    incr_state = step(ptr);
+    return incr_state;
+  }
+
+  Word incr(const uint8_t *ptr) {
+    incr_state = xd3_large_cksum_update_old (&this->stream.large_hash, 
+                                             incr_state, ptr - 1, CksumSize);
+    return incr_state;
+  }
+
+  Word incr_state;
+};
+
+// TESTS
+
+template <typename Word>
+struct file_stats {
+  typedef const uint8_t* ptr_type;
+  typedef Word word_type;
+  typedef btree::btree_multimap<word_type, ptr_type> table_type;
+  typedef typename table_type::iterator table_iterator;
+
+  usize_t cksum_size;
+  usize_t cksum_skip;
+  usize_t unique;
+  usize_t unique_values;
+  usize_t count;
+  table_type table;
+
+  file_stats(usize_t size, usize_t skip)
+    : cksum_size(size),
+      cksum_skip(skip),
+      unique(0),
+      unique_values(0),
+      count(0) {
+  }
+
+  void reset() {
+    unique = 0;
+    unique_values = 0;
+    count = 0;
+    table.clear();
+  }
+
+  void update(word_type word, ptr_type ptr) {
+    table_iterator t_i = table.find(word);
+
+    count++;
+    if (t_i != table.end()) {
+      int collisions = 0;
+      for (table_iterator p_i = t_i;
+           p_i != table.end() && p_i->first == word;
+           ++p_i) {
+        if (memcmp(p_i->second, ptr, cksum_size) == 0) {
+          return;
+        }
+        collisions++;
+      }
+      if (collisions >= 1000) {
+        fprintf(stderr, "Something is not right, lots of collisions=%d\n", 
+                collisions);
+        abort();
+      }
+    } else {
+      unique_values++;
+    }
+    unique++;
+    table.insert(std::make_pair(word, ptr));
+    return;
+  }
+
+  void freeze() {
+    table.clear();
+  }
+};
+
+struct test_result_base;
+
+static vector<test_result_base*> all_tests;
+
+struct test_result_base {
+  virtual ~test_result_base() {
+  }
+  virtual void reset() = 0;
+  virtual void print() = 0;
+  virtual void get(const uint8_t* buf, const size_t buf_size, 
+                   usize_t iters) = 0;
+  virtual void stat() = 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 total_time() = 0;
+  virtual usize_t total_count() = 0;
+  virtual usize_t total_dups() = 0;
+};
+
+template <typename Checksum>
+struct test_result : public test_result_base {
+  Checksum cksum;
+  const char *test_name;
+  file_stats<typename Checksum::word_type> fstats;
+  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;
+  usize_t accum_iters;
+
+  // These are not reset
+  double accum_time;
+  usize_t accum_count;
+  usize_t accum_dups;
+  usize_t accum_colls;
+  size_t accum_size;
+
+  test_result(const char *name)
+    : test_name(name),
+      fstats(Checksum::cksum_size, Checksum::cksum_skip),
+      hash_table(NULL),
+      accum_millis(0),
+      accum_iters(0),
+      accum_time(0.0),
+      accum_count(0),
+      accum_dups(0),
+      accum_colls(0),
+      accum_size(0) {
+    all_tests.push_back(this);
+  }
+
+  ~test_result() {
+    reset();
+  }
+
+  void reset() {
+    // size of file
+    test_size = 0;
+
+    // count
+    n_steps = 0;
+    n_incrs = 0;
+
+    // four values used by new_table()/summarize_table()
+    s_bits = 0;
+    s_mask = 0;
+    t_entries = 0;
+    h_bits = 0;
+    h_buckets_full = 0;
+
+    accum_millis = 0;
+    accum_iters = 0;
+
+    fstats.reset();
+
+    // temporary
+    if (hash_table) {
+      delete(hash_table);
+      hash_table = NULL;
+    }
+  }
+
+  usize_t count() {
+    if (Checksum::cksum_skip == 1) {
+      return n_incrs;
+    } else {
+      return n_steps;
+    }
+  }
+
+  usize_t dups() {
+    return fstats.count - fstats.unique;
+  }
+
+  /* Fraction of distinct strings of length cksum_size which are not
+   * represented in the hash table. */
+  double collisions() {
+    return (fstats.unique - fstats.unique_values) / (double) fstats.unique;
+  }
+  usize_t colls() {
+    return (fstats.unique - fstats.unique_values);
+  }
+
+  double uniqueness() {
+    return 1.0 - (double) dups() / count();
+  }
+
+  double fullness() {
+    return (double) h_buckets_full / (1 << h_bits);
+  }
+
+  double coverage() {
+    return (double) h_buckets_full / uniqueness() / count();
+  }
+
+  double compression() {
+    return 1.0 - coverage();
+  }
+
+  double time() {
+    return (double) accum_millis / accum_iters;
+  }
+
+  double total_time() {
+    return accum_time;
+  }
+
+  usize_t total_count() {
+    return accum_count;
+  }
+
+  usize_t total_dups() {
+    return accum_dups;
+  }
+
+  usize_t total_colls() {
+    return accum_dups;
+  }
+
+  void stat() {
+    accum_time += time();
+    accum_count += count();
+    accum_dups += dups();
+    accum_colls += colls();
+    accum_size += test_size;
+  }
+
+  void print() {
+    if (fstats.count != count()) {
+      fprintf(stderr, "internal error: %" W "d != %" W "d\n", fstats.count, count());
+      abort();
+    }
+    print_header();
+    printf("%-32s%d/%d 2^%" W "u\t%" W "u\t%0.4f\t%.4f\t%.4f\t%.1e\t%.2f\t"
+           "%" W "u\t%" W "u\n",
+           test_name,
+           Checksum::cksum_size,
+           Checksum::cksum_skip,
+           h_bits,
+           count(),
+           uniqueness(),
+           fullness(),
+           coverage(),
+           collisions(),
+           0.001 * accum_iters * test_size / accum_millis,
+           accum_iters,
+           colls());
+  }
+
+  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 <= (1U << i)) {
+        return i - Checksum::compaction;
+      }
+    }
+
+    return bits;
+  }
+
+  void new_table(usize_t entries) {
+    t_entries = entries;
+    h_bits = size_log2(entries);
+
+    usize_t n = 1 << h_bits;
+
+    s_bits = bitsof<typename Checksum::word_type>() - h_bits;
+    s_mask = n - 1U;
+
+    hash_table = new char[n / 8];
+    memset(hash_table, 0, n / 8);
+  }
+
+  int get_table_bit(usize_t i) {
+    return hash_table[i/8] & (1 << i%8);
+  }
+
+  int set_table_bit(usize_t i) {
+    return hash_table[i/8] |= (1 << i%8);
+  }
+
+  void summarize_table() {
+    usize_t n = 1 << h_bits;
+    usize_t f = 0;
+    for (usize_t i = 0; i < n; i++) {
+      if (get_table_bit(i)) {
+        f++;
+      }
+    }
+    h_buckets_full = f;
+  }
+
+  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;
+    int64_t last_offset;
+    int64_t stop;
+
+    test_size = buf_size;
+    last_offset = buf_size - Checksum::cksum_size;
+
+    if (last_offset < 0) {
+      periods = 0;
+      n_steps = 0;
+      n_incrs = 0;
+      stop = -Checksum::cksum_size;
+    } else {
+      periods = last_offset / Checksum::cksum_skip;
+      n_steps = periods + 1;
+      n_incrs = last_offset + 1;
+      stop = last_offset - (periods + 1) * Checksum::cksum_skip;
+    }
+
+    // Compute file stats once.
+    if (fstats.unique_values == 0) {
+      if (Checksum::cksum_skip == 1) {
+        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 {
+        ptr = buf + last_offset;
+        end = buf + stop;
+
+        for (; ptr != end; ptr -= Checksum::cksum_skip) {
+          fstats.update(hash(cksum.step(ptr), s_bits, s_mask), ptr);
+        }
+      }
+      fstats.freeze();
+    }
+
+    long start_test = get_millisecs_now();
+
+    if (Checksum::cksum_skip != 1) {
+      new_table(n_steps);
+
+      for (usize_t i = 0; i < test_iters; i++) {
+        ptr = buf + last_offset;
+        end = buf + stop;
+
+        for (; ptr != end; ptr -= Checksum::cksum_skip) {
+          set_table_bit(hash(cksum.step(ptr), s_bits, s_mask));
+        }
+      }
+
+      summarize_table();
+    }
+
+    stop = buf_size - Checksum::cksum_size + 1;
+    if (stop < 0) {
+      stop = 0;
+    }
+
+    if (Checksum::cksum_skip == 1) {
+      new_table(n_incrs);
+
+      for (usize_t i = 0; i < test_iters; i++) {
+        ptr = buf;
+        end = buf + stop;
+
+        if (ptr != end) {
+          set_table_bit(hash(cksum.state0(ptr++), s_bits, s_mask));
+        }
+
+        for (; ptr != end; ptr++) {
+          typename Checksum::word_type w = cksum.incr(ptr);
+          CHECK_EQ(w, cksum.step(ptr));
+          set_table_bit(hash(w, s_bits, s_mask));
+        }
+      }
+
+      summarize_table();
+    }
+
+    accum_iters += test_iters;
+    accum_millis += get_millisecs_now() - start_test;
+  }
+};
+
+static int read_whole_file(const char *name,
+                           uint8_t **buf_ptr,
+                           size_t *buf_len) {
+  main_file file;
+  int ret;
+  xoff_t len;
+  size_t nread;
+  main_file_init(&file);
+  file.filename = name;
+  ret = main_file_open(&file, name, XO_READ);
+  if (ret != 0) {
+    fprintf(stderr, "open failed\n");
+    goto exit;
+  }
+  ret = main_file_stat(&file, &len);
+  if (ret != 0) {
+    fprintf(stderr, "stat failed\n");
+    goto exit;
+  }
+  
+  (*buf_len) = (size_t)len;
+  (*buf_ptr) = (uint8_t*) main_malloc(*buf_len);
+  ret = main_file_read(&file, *buf_ptr, *buf_len, &nread,
+                       "read failed");
+  if (ret == 0 && *buf_len == nread) {
+    ret = 0;
+  } else {
+    fprintf(stderr, "invalid read\n");
+    ret = XD3_INTERNAL;
+  }
+ exit:
+  main_file_cleanup(&file);
+  return ret;
+}
+
+int main(int argc, char** argv) {
+  int i;
+  uint8_t *buf = NULL;
+  size_t buf_len = 0;
+  int ret;
+
+  if (argc <= 1) {
+    fprintf(stderr, "usage: %s file ...\n", argv[0]);
+    return 1;
+  }
+
+// TODO: The xdelta3-hash.h code is identical now; add sameness test.
+// using rabin_karp<> template.
+#define TEST(T,Z,S,C)                                   \
+  test_result<large_cksum<T,Z,S,hhash<T>,C>>            \
+    _xck_ ## T ## _ ## Z ## _ ## S ## _ ## C            \
+    ("xck_" #T "_" #Z "_" #S "_" #C);                   \
+  test_result<large_cksum_old<T,Z,S,hhash<T>,C>>        \
+    _old_ ## T ## _ ## Z ## _ ## S ## _ ## C            \
+    ("old_" #T "_" #Z "_" #S "_" #C)
+
+#define TESTS(SIZE, SKIP)        \
+  TEST(usize_t, SIZE, SKIP, 1);  \
+  TEST(usize_t, SIZE, SKIP, 2)
+   
+  TESTS(5, 1);
+  TESTS(6, 1);
+  TESTS(7, 1);
+  TESTS(8, 1);
+  TESTS(9, 1);
+  TESTS(10, 1);
+  TESTS(11, 1);
+  TESTS(12, 1);
+  TESTS(13, 1);
+  TESTS(14, 1);
+  TESTS(15, 1);
+  TESTS(16, 1);
+  TESTS(17, 1);
+  TESTS(18, 1);
+  TESTS(19, 1);
+  TESTS(20, 1);
+  TESTS(21, 1);
+  TESTS(22, 1);
+  TESTS(23, 1);
+  TESTS(24, 1);
+  TESTS(25, 1);
+  TESTS(26, 1);
+  TESTS(27, 1);
+  TESTS(28, 1);
+  TESTS(29, 1);
+  TESTS(30, 1);
+  TESTS(31, 1);
+  TESTS(32, 1);
+  TESTS(33, 1);
+  TESTS(34, 1);
+  TESTS(35, 1);
+  TESTS(36, 1);
+  TESTS(37, 1);
+  TESTS(38, 1);
+  TESTS(39, 1);
+
+
+  for (i = 1; i < argc; i++) {
+    if ((ret = read_whole_file(argv[i],
+                               & buf,
+                               & buf_len))) {
+      return 1;
+    }
+
+    fprintf(stderr, "file %s is %zu bytes\n",
+            argv[i], buf_len);
+
+    double min_time = -1.0;
+    double min_compression = 0.0;
+
+    for (vector<test_result_base*>::iterator iter = all_tests.begin();
+         iter != all_tests.end(); ++iter) {
+      test_result_base *test = *iter;
+      test->reset();
+
+      usize_t iters = 1;
+      long start_test = get_millisecs_now();
+
+      do {
+        test->get(buf, buf_len, iters);
+        iters *= 3;
+        iters /= 2;
+      } while (get_millisecs_now() - start_test < 2000);
+
+      test->stat();
+
+      if (min_time < 0.0) {
+        min_compression = test->compression();
+        min_time = test->time();
+      }
+
+      if (min_time > test->time()) {
+        min_time = test->time();
+      }
+
+      if (min_compression > test->compression()) {
+        min_compression = test->compression();
+      }
+
+      test->print();
+    }
+
+    main_free(buf);
+    buf = NULL;
+  }
+
+  return 0;      
+}
diff --git a/xdelta3/testing/checksum_test_c.c b/xdelta3/testing/checksum_test_c.c
new file mode 100644
index 0000000..8f0507a
--- /dev/null
+++ b/xdelta3/testing/checksum_test_c.c
@@ -0,0 +1,174 @@
+#include "../xdelta3.c"
+
+// OLD CHECKSUM CODE
+
+#define PERMUTE32(x) (__single_hash32[x])
+#define PERMUTE64(x) (__single_hash64[x])
+
+const uint16_t __single_hash32[256] =
+{
+  /* 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,
+  0xb645, 0xcb4d, 0xc44b, 0xe5dc, 0x9fe6, 0x5b5c, 0x35f5, 0x701a,
+  0x220f, 0x6c38, 0x1a56, 0x4ca3, 0xffc6, 0xb152, 0x8d61, 0x7a58,
+  0x9025, 0x8b3d, 0xbf0f, 0x95a3, 0xe5f4, 0xc127, 0x3bed, 0x320b,
+  0xb7f3, 0x6054, 0x333c, 0xd383, 0x8154, 0x5242, 0x4e0d, 0x0a94,
+  0x7028, 0x8689, 0x3a22, 0x0980, 0x1847, 0xb0f1, 0x9b5c, 0x4176,
+  0xb858, 0xd542, 0x1f6c, 0x2497, 0x6a5a, 0x9fa9, 0x8c5a, 0x7743,
+  0xa8a9, 0x9a02, 0x4918, 0x438c, 0xc388, 0x9e2b, 0x4cad, 0x01b6,
+  0xab19, 0xf777, 0x365f, 0x1eb2, 0x091e, 0x7bf8, 0x7a8e, 0x5227,
+  0xeab1, 0x2074, 0x4523, 0xe781, 0x01a3, 0x163d, 0x3b2e, 0x287d,
+  0x5e7f, 0xa063, 0xb134, 0x8fae, 0x5e8e, 0xb7b7, 0x4548, 0x1f5a,
+  0xfa56, 0x7a24, 0x900f, 0x42dc, 0xcc69, 0x02a0, 0x0b22, 0xdb31,
+  0x71fe, 0x0c7d, 0x1732, 0x1159, 0xcb09, 0xe1d2, 0x1351, 0x52e9,
+  0xf536, 0x5a4f, 0xc316, 0x6bf9, 0x8994, 0xb774, 0x5f3e, 0xf6d6,
+  0x3a61, 0xf82c, 0xcc22, 0x9d06, 0x299c, 0x09e5, 0x1eec, 0x514f,
+  0x8d53, 0xa650, 0x5c6e, 0xc577, 0x7958, 0x71ac, 0x8916, 0x9b4f,
+  0x2c09, 0x5211, 0xf6d8, 0xcaaa, 0xf7ef, 0x287f, 0x7a94, 0xab49,
+  0xfa2c, 0x7222, 0xe457, 0xd71a, 0x00c3, 0x1a76, 0xe98c, 0xc037,
+  0x8208, 0x5c2d, 0xdfda, 0xe5f5, 0x0b45, 0x15ce, 0x8a7e, 0xfcad,
+  0xaa2d, 0x4b5c, 0xd42e, 0xb251, 0x907e, 0x9a47, 0xc9a6, 0xd93f,
+  0x085e, 0x35ce, 0xa153, 0x7e7b, 0x9f0b, 0x25aa, 0x5d9f, 0xc04d,
+  0x8a0e, 0x2875, 0x4a1c, 0x295f, 0x1393, 0xf760, 0x9178, 0x0f5b,
+  0xfa7d, 0x83b4, 0x2082, 0x721d, 0x6462, 0x0368, 0x67e2, 0x8624,
+  0x194d, 0x22f6, 0x78fb, 0x6791, 0xb238, 0xb332, 0x7276, 0xf272,
+  0x47ec, 0x4504, 0xa961, 0x9fc8, 0x3fdc, 0xb413, 0x007a, 0x0806,
+  0x7458, 0x95c6, 0xccaa, 0x18d6, 0xe2ae, 0x1b06, 0xf3f6, 0x5050,
+  0xc8e8, 0xf4ac, 0xc04c, 0xf41c, 0x992f, 0xae44, 0x5f1b, 0x1113,
+  0x1738, 0xd9a8, 0x19ea, 0x2d33, 0x9698, 0x2fe9, 0x323f, 0xcde2,
+  0x6d71, 0xe37d, 0xb697, 0x2c4f, 0x4373, 0x9102, 0x075d, 0x8e25,
+  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,
+};
+
+uint64_t
+xd3_large64_cksum_old (xd3_hash_cfg *ignore, const uint8_t *base, const usize_t look)
+{
+  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 < look; i += 1)
+    {
+      low  += PERMUTE64(*base++);
+      high += low;
+    }
+
+  return ((high & kMask) << kBits) | (low & kMask);
+}
+
+uint64_t
+xd3_large64_cksum_update_old (xd3_hash_cfg *ignore, const uint64_t cksum,
+                              const uint8_t *base, const 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;
+}
+
+uint32_t
+xd3_large32_cksum_old (xd3_hash_cfg *ignore, const uint8_t *base, const usize_t look)
+{
+  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 < look; i += 1)
+    {
+      low  += PERMUTE32(*base++);
+      high += low;
+    }
+
+  return ((high & kMask) << kBits) | (low & kMask);
+}
+
+uint32_t
+xd3_large32_cksum_update_old (xd3_hash_cfg *ignore, const uint32_t cksum,
+                              const uint8_t *base, const 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;
+}
diff --git a/xdelta3/testing/delta.h b/xdelta3/testing/delta.h
index b0cca7c..deac217 100644
--- a/xdelta3/testing/delta.h
+++ b/xdelta3/testing/delta.h
@@ -30,7 +30,7 @@ public:
       case XD3_WINFINISH:
         break;
       default:
-        DP(RINT "error code %s\n", xd3_strerror (ret));
+        cerr << "decode: " << done;
         abort();
       }
     }
@@ -48,23 +48,25 @@ public:
     return stream_.whole_target.wininfolen;
   }
 
-  void Print() const {
-    for (size_t i = 0; i < stream_.whole_target.instlen; i++) {
-      xd3_winst &winst = stream_.whole_target.inst[i];
-      switch (winst.type) {
-      case XD3_RUN: 
-        DP(RINT "%"Q"u run %u\n", winst.position, winst.size);
-        break;
-      case XD3_ADD: 
-        DP(RINT "%"Q"u add %u\n", winst.position, winst.size);
-        break;
-      default:
-        DP(RINT "%"Q"u copy %u @ %"Q"u (mode %u)\n", 
-           winst.position, winst.size, winst.addr, winst.mode);
-        break;
-      }
-    }
-  }
+// Note: This does not benefit from -Wformat= checking, due to the
+// enclosing template. Further, it was not used.
+// void Print() const {
+//     for (size_t i = 0; i < stream_.whole_target.instlen; i++) {
+//       xd3_winst &winst = stream_.whole_target.inst[i];
+//       switch (winst.type) {
+//       case XD3_RUN: 
+//      DP(RINT, "%" Q "u run %" W "u\n", winst.position, winst.size);
+//      break;
+//       case XD3_ADD: 
+//      DP(RINT "%" Q "u add %" W "u\n", winst.position, winst.size);
+//      break;
+//       default:
+//      DP(RINT "%" Q "u copy %" W "u @ %" Q "u (mode %u)\n", 
+//         winst.position, winst.size, winst.addr, winst.mode);
+//      break;
+//       }
+//     }
+//   }
 
 private:
   xd3_stream stream_;
diff --git a/xdelta3/testing/file.h b/xdelta3/testing/file.h
index 55b0eb8..2188f7a 100644
--- a/xdelta3/testing/file.h
+++ b/xdelta3/testing/file.h
@@ -62,20 +62,22 @@ public:
     size_ = 0;
   }
 
-  void Print() const {
-    xoff_t pos = 0;
-    for (size_t i = 0; i < Size(); i++) {
-      if (pos % 16 == 0) {
-        DP(RINT "%5"Q"x: ", pos);
-      }
-      DP(RINT "%02x ", (*this)[i]);
-      if (pos % 16 == 15) {
-        DP(RINT "\n");
-      }
-      pos++;
-    }
-    DP(RINT "\n");
-  }
+  // Note: This does not benefit from -Wformat= checking, due to the
+  // enclosing template. Further, it was not used.
+  // void Print() const {
+  //   xoff_t pos = 0;
+  //   for (size_t i = 0; i < Size(); i++) {
+  //     if (pos % 16 == 0) {
+  //    DP(RINT "%5" Q "x: ", pos);
+  //     }
+  //     DP(RINT "%02x ", (*this)[i]);
+  //     if (pos % 16 == 15) {
+  //    DP(RINT "\n");
+  //     }
+  //     pos++;
+  //   }
+  //   DP(RINT "\n");
+  // }
 
   void WriteTmpFile(TmpFile *f) const {
     f->Append(this);
diff --git a/xdelta3/testing/regtest.cc b/xdelta3/testing/regtest.cc
index b2cdaa5..dd2ab8d 100644
--- a/xdelta3/testing/regtest.cc
+++ b/xdelta3/testing/regtest.cc
@@ -92,22 +92,24 @@ public:
     bool done = false;
     bool done_after_input = false;
 
-    IF_DEBUG1 (XPR(NTR "source %"Q"u[%"Q"u] target %"Q"u winsize %"Z"u\n",
-                  source_file.Size(), options.block_size,
-                  target_file.Size(),
-                  Constants::WINDOW_SIZE));
+    IF_DEBUG1 (XPR(NTR "source %" Q "u[%" Z "u] target %" Q "u winsize %" Z "u\n",
+                   source_file.Size(), options.block_size,
+                   target_file.Size(),
+                   Constants::WINDOW_SIZE));
 
     while (!done) {
       target_iterator.Get(&target_block);
 
       xoff_t blks = target_iterator.Blocks();
 
-      IF_DEBUG2(XPR(NTR "target in %s: %"Q"u..%"Q"u %"Q"u(%"Q"u) "
-                    "verified %"Q"u\n",
-                   encoding ? "encoding" : "decoding",
-                   target_iterator.Offset(),
-                   target_iterator.Offset() + target_block.Size(),
-                   target_iterator.Blkno(), blks, verified_bytes));
+      IF_DEBUG2(XPR(NTR "target in %s: %" Q "u[%" Z "u] %" Q "u(%" Q "u) "
+                    "verified %" Q "u\n",
+                    encoding ? "encoding" : "decoding",
+                    target_iterator.Offset(),
+                    target_block.Size(),
+                    target_iterator.Blkno(),
+                    blks,
+                    verified_bytes));
 
       if (blks == 0 || target_iterator.Blkno() == (blks - 1)) {
         xd3_set_flags(&encode_stream, XD3_FLUSH | encode_stream.flags);
@@ -153,8 +155,8 @@ public:
         xd3_source *src = (encoding ? &encode_source : &decode_source);
         Block *block = (encoding ? &encode_source_block : &decode_source_block);
         if (encoding) {
-          IF_DEBUG2(XPR(NTR "[srcblock] %"Q"u last srcpos %"Q"u "
-                        "encodepos %"Q"u\n",
+          IF_DEBUG2(XPR(NTR "[srcblock] %" Q "u last srcpos %" Q "u "
+                        "encodepos %" Q "u\n",
                         encode_source.getblkno,
                         encode_stream.match_last_srcpos,
                         encode_stream.input_position + encode_stream.total_in));
@@ -231,7 +233,7 @@ public:
                         const Options &options) {
     vector<const char*> ecmd;
     char bbuf[16];
-    snprintf(bbuf, sizeof(bbuf), "-B%"Q"u", options.encode_srcwin_maxsz);
+    snprintf(bbuf, sizeof(bbuf), "-B%" Q "u", options.encode_srcwin_maxsz);
     ecmd.push_back("xdelta3");
     ecmd.push_back(bbuf);
     ecmd.push_back("-s");
@@ -371,7 +373,7 @@ public:
 void TestPrintf() {
   char buf[64];
   xoff_t x = XOFF_T_MAX;
-  snprintf_func (buf, sizeof(buf), "%"Q"u", x);
+  snprintf_func (buf, sizeof(buf), "%" Q "u", x);
   const char *expect = XD3_USE_LARGEFILE64 ?
     "18446744073709551615" : "4294967295";
   XD3_ASSERT(strcmp (buf, expect) == 0);
@@ -696,8 +698,9 @@ void TestOverwriteMutator() {
   CHECK(memcmp(b0.Data() + 30, b1.Data() + 30,
                Constants::BLOCK_SIZE - 30) == 0);
 
+  xoff_t zero = 0;
   cl1.clear();
-  cl1.push_back(Change(Change::COPYOVER, 10, 20, (xoff_t)0));
+  cl1.push_back(Change(Change::COPYOVER, 10, 20, zero));
   spec0.ModifyTo(ChangeListMutator(cl1), &spec1);
   CHECK_EQ(spec0.Size(), spec1.Size());
 
@@ -813,7 +816,7 @@ void TestSmallStride() {
     InMemoryEncodeDecode(spec0, spec1, &block, options);
     Delta delta(block);
 
-    IF_DEBUG1(DP(RINT "[stride=%d] changes=%u adds=%"Q"u\n",
+    IF_DEBUG1(DP(RINT "[stride=%d] changes=%" W "u adds=%" Q "u\n",
                  s, changes, delta.AddedBytes()));
     double allowance = Constants::BLOCK_SIZE < 8192 || s < 30 ? 3.0 : 1.1;
     CHECK_GE(allowance * changes, (double)delta.AddedBytes());
@@ -1259,7 +1262,7 @@ void UnitTest() {
 // These are Xdelta tests.
 template <class T>
 void MainTest() {
-  XPR(NT "Blocksize %"Q"u windowsize %"Z"u\n",
+  XPR(NT "Blocksize %" Q "u windowsize %" Z "u\n",
       T::BLOCK_SIZE, T::WINDOW_SIZE);
   Regtest<T> regtest;
   TEST(TestEmptyInMemory);
diff --git a/xdelta3/testing/run_release.sh b/xdelta3/testing/run_release.sh
new file mode 100755
index 0000000..85ed1f7
--- /dev/null
+++ b/xdelta3/testing/run_release.sh
@@ -0,0 +1,2 @@
+#!/bin/sh
+(cd .. && ./run_release.sh)
diff --git a/xdelta3/testing/test.h b/xdelta3/testing/test.h
index 1eabcbd..7de24fb 100644
--- a/xdelta3/testing/test.h
+++ b/xdelta3/testing/test.h
@@ -18,8 +18,8 @@ extern "C" {
 
 #define CHECK_OP(x,y,OP) \
   do { \
-    typeof(x) _x(x); \
-    typeof(x) _y(y); \
+    __typeof__(x) _x(x); \
+    __typeof__(x) _y(y); \
     if (!(_x OP _y)) { \
       cerr << __FILE__ << ":" << __LINE__ << " Check failed: " << #x " " #OP " " #y << endl; \
       cerr << __FILE__ << ":" << __LINE__ << " {0} " << _x << endl; \
@@ -68,5 +68,3 @@ pair<T, U> make_pair(const T& t, const U& u) {
 
 using std::min;
 using std::max;
-
-