1 files changed, 48 insertions, 94 deletions

diff --git a/xdelta3/xdelta3-hash.h b/xdelta3/xdelta3-hash.h
index fd18099..2919b98 100644
--- a/xdelta3/xdelta3-hash.h
+++ b/xdelta3/xdelta3-hash.h
@@ -41,10 +41,11 @@
 #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
+/* These are good hash multipliers for 32-bit and 64-bit LCGs: see
+ * "linear congruential generators of different sizes and good lattice
  * structure" */
-static const uint32_t hash_multiplier = 1597334677U;
+#define xd3_hash_multiplier32 1597334677U
+#define xd3_hash_multiplier64 1181783497276652981ULL
 
 /* TODO: small cksum is hard-coded for 4 bytes (i.e., "look" is unused) */
 static inline uint32_t
@@ -53,7 +54,7 @@ xd3_scksum (uint32_t *state,
             const usize_t look)
 {
   UNALIGNED_READ32(state, base);
-  return (*state) * hash_multiplier;
+  return (*state) * xd3_hash_multiplier32;
 }
 static inline uint32_t
 xd3_small_cksum_update (uint32_t *state,
@@ -61,112 +62,48 @@ xd3_small_cksum_update (uint32_t *state,
                         usize_t look)
 {
   UNALIGNED_READ32(state, base+1);
-  return (*state) * hash_multiplier;
+  return (*state) * xd3_hash_multiplier32;
 }
 
-static inline usize_t
+#if XD3_ENCODER
+inline usize_t
 xd3_checksum_hash (const xd3_hash_cfg *cfg, const usize_t cksum)
 {
   return (cksum >> cfg->shift) ^ (cksum & cfg->mask);
 }
 
-#if XD3_ENCODER
-#define PERMUTE32(x) (__single_hash32[x])
-extern const uint16_t __single_hash32[256];
-
 inline uint32_t
-xd3_large32_cksum (const uint8_t *seg, const usize_t ln)
+xd3_large32_cksum (xd3_hash_cfg *cfg, 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 < ln; i += 1)
-    {
-      low  += PERMUTE32(*seg++);
-      high += low;
-    }
-
-  return ((high & kMask) << kBits) | (low & kMask);
+  uint32_t h = 0;
+  for (usize_t i = 0; i < look; i++) {
+    h += base[i] * cfg->powers[i];
+  }
+  return h;
 }
 
 inline uint32_t
-xd3_large32_cksum_update (uint32_t cksum,
-                          const uint8_t *base,
-                          usize_t look) 
+xd3_large32_cksum_update (xd3_hash_cfg *cfg, 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;
+  return xd3_hash_multiplier32 * cksum - cfg->multiplier * base[0] + base[look];
 }
 
-#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)
+xd3_large64_cksum (xd3_hash_cfg *cfg, 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 < len; i += 1)
-    {
-      low  += PERMUTE64(*seg++);
-      high += low;
-    }
-
-  return ((high & kMask) << kBits) | (low & kMask);
+  uint64_t h = 0;
+  for (usize_t i = 0; i < look; i++) {
+    h += base[i] * cfg->powers[i];
+  }
+  return h;
 }
 
 inline uint64_t
-xd3_large64_cksum_update (uint64_t cksum,
-                          const uint8_t *base,
-                          usize_t look) 
+xd3_large64_cksum_update (xd3_hash_cfg *cfg, 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;
-}
-
-#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
-  return xd3_large64_cksum_update (cksum, base, look);
-#endif
+  return xd3_hash_multiplier64 * cksum - cfg->multiplier * base[0] + base[look];
 }
 
 static usize_t
@@ -179,9 +116,9 @@ xd3_size_hashtable_bits (usize_t slots)
     {
       if (slots < (1U << i))
         {
-          /* TODO: this is compaction=1 in checksum_test.cc and maybe should
-           * not be fixed at -1. */
-          bits = i - 1; 
+          /* Note: this is the compaction=1 setting measured in
+           * checksum_test */
+          bits = i - 1;
           break;
         }
     }
@@ -189,9 +126,10 @@ xd3_size_hashtable_bits (usize_t slots)
   return bits;
 }
 
-static void
+int
 xd3_size_hashtable (xd3_stream   *stream,
                     usize_t       slots,
+                    usize_t       look,
                     xd3_hash_cfg *cfg)
 {
   usize_t bits = xd3_size_hashtable_bits (slots);
@@ -199,7 +137,23 @@ xd3_size_hashtable (xd3_stream   *stream,
   cfg->size  = (1U << bits);
   cfg->mask  = (cfg->size - 1);
   cfg->shift = (SIZEOF_USIZE_T * 8) - bits;
+  cfg->look  = look;
+
+  if ((cfg->powers = 
+       (usize_t*) xd3_alloc0 (stream, look, sizeof (usize_t))) == NULL)
+    {
+      return ENOMEM;
+    }
+
+  cfg->powers[look-1] = 1;
+  for (int i = look-2; i >= 0; i--)
+    {
+      cfg->powers[i] = cfg->powers[i+1] * xd3_hash_multiplier;
+    }
+  cfg->multiplier = cfg->powers[0] * xd3_hash_multiplier;
+
+  return 0;
 }
 
-#endif
+#endif /* XD3_ENCODER */
 #endif /* _XDELTA3_HASH_H_ */