summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--Changes6
-rw-r--r--bench.c1
-rw-r--r--lzfP.h34
-rw-r--r--lzf_c.c26
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
/*
@@ -122,11 +122,29 @@
#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 */