From 4c89419158d9aff46164db5ef49004152fbc9453 Mon Sep 17 00:00:00 2001
From: root <root>
Date: Sun, 27 Mar 2011 23:53:23 +0000
Subject: *** empty log message ***

---
 Changes |  6 ++++++
 bench.c |  1 +
 lzfP.h  | 34 ++++++++++++++++++++++++++++------
 lzf_c.c | 26 +++++++++++++-------------
 4 files changed, 48 insertions(+), 19 deletions(-)

diff --git a/Changes b/Changes
index 3445969..3134742 100644
--- a/Changes
+++ b/Changes
@@ -1,4 +1,10 @@
 
+	- switch to a multiplicative hash (developed with Steinar Gunderson),
+          which is faster on modern cpus and compresses a bit better. The old
+          hash function which uses only shifts is still available.
+        - allow user configurable hash table slots, which makes it possible
+          to use e.g. 16 bit offsets for a smaller hashtable (if your data is
+          always < 64kb).
 	- use _WIN32, not WIN32, when testing for windows (fails with bcc),
           patch by Tamas Tevesz.
 
diff --git a/bench.c b/bench.c
index 2ef977b..a495421 100644
--- a/bench.c
+++ b/bench.c
@@ -43,6 +43,7 @@ static void sigu (int signum)
 }
 
 #define DSIZE 2821120
+#define DSIZE 32768
 
 unsigned char data[DSIZE], data2[DSIZE*2], data3[DSIZE*2];
 
diff --git a/lzfP.h b/lzfP.h
index cf4af7f..97aabf4 100644
--- a/lzfP.h
+++ b/lzfP.h
@@ -88,7 +88,7 @@
  * deterministic/repeatable when the configuration otherwise is the same).
  */
 #ifndef INIT_HTAB
-# define INIT_HTAB 0
+# define INIT_HTAB 1
 #endif
 
 /*
@@ -121,12 +121,30 @@
 # define CHECK_INPUT 1
 #endif
 
+/*
+ * Whether the target CPU has a slow multiplication. This affects
+ * the default hash function for the compressor, and enables a slightly
+ * worse hash function that needs only shifts.
+ */
+#ifndef MULTIPLICATION_IS_SLOW
+# define MULTIPLICATION_IS_SLOW 0
+#endif
+
+/*
+ * If defined, then this data type will be used for storing offsets.
+ * This can be useful if you want to use a huge hashtable, want to
+ * conserve memory, or both, and your data fits into e.g. 64kb.
+ * If instead you want to compress data > 4GB, then it's better to
+ * to "#define LZF_USE_OFFSETS 0" instead.
+ */
+/*#define LZF_HSLOT unsigned short*/
+
 /*
  * Whether to store pointers or offsets inside the hash table. On
  * 64 bit architetcures, pointers take up twice as much space,
  * and might also be slower. Default is to autodetect.
  */
-/*#define LZF_USER_OFFSETS autodetect */
+/*#define LZF_USE_OFFSETS autodetect */
 
 /*****************************************************************************/
 /* nothing should be changed below */
@@ -155,12 +173,16 @@ using namespace std;
 
 typedef unsigned char u8;
 
-#if LZF_USE_OFFSETS
+#ifdef LZF_HSLOT
 # define LZF_HSLOT_BIAS ((const u8 *)in_data)
-  typedef unsigned int LZF_HSLOT;
 #else
-# define LZF_HSLOT_BIAS 0
-  typedef const u8 *LZF_HSLOT;
+# if LZF_USE_OFFSETS
+#  define LZF_HSLOT_BIAS ((const u8 *)in_data)
+   typedef unsigned int LZF_HSLOT;
+# else
+#  define LZF_HSLOT_BIAS 0
+   typedef const u8 *LZF_HSLOT;
+# endif
 #endif
 
 typedef LZF_HSLOT LZF_STATE[1 << (HLOG)];
diff --git a/lzf_c.c b/lzf_c.c
index bc07084..99d93cb 100644
--- a/lzf_c.c
+++ b/lzf_c.c
@@ -47,22 +47,22 @@
 #ifndef FRST
 # define FRST(p) (((p[0]) << 8) | p[1])
 # define NEXT(v,p) (((v) << 8) | p[2])
-# if ULTRA_FAST
-#  define IDX(h) ((( h             >> (3*8 - HLOG)) - h  ) & (HSIZE - 1))
-# elif VERY_FAST
-#  define IDX(h) ((( h             >> (3*8 - HLOG)) - h*5) & (HSIZE - 1))
+# if MULTIPLICATION_IS_SLOW
+#  if ULTRA_FAST
+#   define IDX(h) ((( h             >> (3*8 - HLOG)) - h  ) & (HSIZE - 1))
+#  elif VERY_FAST
+#   define IDX(h) ((( h             >> (3*8 - HLOG)) - h*5) & (HSIZE - 1))
+#  else
+#   define IDX(h) ((((h ^ (h << 5)) >> (3*8 - HLOG)) - h*5) & (HSIZE - 1))
+#  endif
 # else
-#  define IDX(h) ((((h ^ (h << 5)) >> (3*8 - HLOG)) - h*5) & (HSIZE - 1))
+/* this one was developed with sesse,
+ * and is very similar to the one in snappy.
+ * it does need a modern enough cpu with a fast multiplication.
+ */
+#  define IDX(h) (((h * 0x1e35a7bdU) >> (32 - HLOG - 8)) & (HSIZE - 1))
 # endif
 #endif
-/*
- * IDX works because it is very similar to a multiplicative hash, e.g.
- * ((h * 57321 >> (3*8 - HLOG)) & (HSIZE - 1))
- * the latter is also quite fast on newer CPUs, and compresses similarly.
- *
- * the next one is also quite good, albeit slow ;)
- * (int)(cos(h & 0xffffff) * 1e6)
- */
 
 #if 0
 /* original lzv-like hash function, much worse and thus slower */
-- 
cgit v1.2.3