diff options
| -rw-r--r-- | Changes | 6 | ||||
| -rw-r--r-- | bench.c | 1 | ||||
| -rw-r--r-- | lzfP.h | 34 | ||||
| -rw-r--r-- | lzf_c.c | 26 |
4 files changed, 48 insertions, 19 deletions
@@ -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. @@ -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]; @@ -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)]; @@ -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 */ |