diff options
author | Marc Lehmann <schmorpforge@schmorp.de> | 2015-06-30 02:34:41 +0300 |
---|---|---|
committer | Marc Lehmann <schmorpforge@schmorp.de> | 2015-06-30 02:34:41 +0300 |
commit | fb25820c3c0aeafd127956ae6c115063b47e459a (patch) | |
tree | f184249acf0f531dec740176b099255b1d71fbc7 | |
parent | 725b0c226296897090c70666e629ccbcd4ec38d7 (diff) |
-rw-r--r-- | Changes | 4 | ||||
-rw-r--r-- | lzfP.h | 20 | ||||
-rw-r--r-- | lzf_c.c | 12 | ||||
-rw-r--r-- | lzf_c_best.c | 85 |
4 files changed, 67 insertions, 54 deletions
@@ -2,7 +2,9 @@ TODO: try unaligned copy again in decompressor TODO: allow size-optimised binaries by avoiding unrolling TODO: implement lzf_c_best in lzf. -TODO: fix lzf_c_best. + +3.8 (unreleased) + - support a state arg for lzf_c_best. 3.7 (unreleased) - add lzf_c_best.c, a slower but better compressor. @@ -171,6 +171,10 @@ using namespace std; # include <limits.h> #endif +#if ULTRA_FAST +# undef VERY_FAST +#endif + #ifndef LZF_USE_OFFSETS # ifdef _WIN32 # define LZF_USE_OFFSETS defined(_M_X64) @@ -198,8 +202,6 @@ typedef unsigned char u8; # endif #endif -typedef LZF_HSLOT LZF_STATE[1 << (HLOG)]; - #if USHRT_MAX == 65535 typedef unsigned short u16; #elif UINT_MAX == 65535 @@ -209,9 +211,17 @@ typedef LZF_HSLOT LZF_STATE[1 << (HLOG)]; # define STRICT_ALIGN 1 #endif -#if ULTRA_FAST -# undef VERY_FAST -#endif +#define LZF_MAX_LIT (1 << 5) +#define LZF_MAX_OFF (1 << 13) +#define LZF_MAX_REF ((1 << 8) + (1 << 3)) + +typedef LZF_HSLOT LZF_STATE[1 << (HLOG)]; + +typedef struct +{ + const u8 *first [1 << (6+8)]; /* most recent occurance of a match */ + u16 prev [LZF_MAX_OFF]; /* how many bytes to go backwards for the next match */ +} LZF_STATE_BEST[1]; #endif @@ -71,10 +71,6 @@ # define IDX(h) ((h) & (HSIZE - 1)) #endif -#define MAX_LIT (1 << 5) -#define MAX_OFF (1 << 13) -#define MAX_REF ((1 << 8) + (1 << 3)) - #if __GNUC__ >= 3 # define expect(expr,value) __builtin_expect ((expr),(value)) # define inline inline @@ -154,7 +150,7 @@ lzf_compress (const void *const in_data, unsigned int in_len, #if INIT_HTAB && ref < ip /* the next test will actually take care of this, but this is faster */ #endif - && (off = ip - ref - 1) < MAX_OFF + && (off = ip - ref - 1) < LZF_MAX_OFF && ref > (u8 *)in_data && ref[2] == ip[2] #if STRICT_ALIGN @@ -167,7 +163,7 @@ lzf_compress (const void *const in_data, unsigned int in_len, /* match found at *ref++ */ unsigned int len = 2; unsigned int maxlen = in_end - ip - len; - maxlen = maxlen > MAX_REF ? MAX_REF : maxlen; + maxlen = maxlen > LZF_MAX_REF ? LZF_MAX_REF : maxlen; if (expect_false (op + 3 + 1 >= out_end)) /* first a faster conservative test */ if (op - !lit + 3 + 1 >= out_end) /* second the exact but rare test */ @@ -266,7 +262,7 @@ lzf_compress (const void *const in_data, unsigned int in_len, lit++; *op++ = *ip++; - if (expect_false (lit == MAX_LIT)) + if (expect_false (lit == LZF_MAX_LIT)) { op [- lit - 1] = lit - 1; /* stop run */ lit = 0; op++; /* start run */ @@ -281,7 +277,7 @@ lzf_compress (const void *const in_data, unsigned int in_len, { lit++; *op++ = *ip++; - if (expect_false (lit == MAX_LIT)) + if (expect_false (lit == LZF_MAX_LIT)) { op [- lit - 1] = lit - 1; /* stop run */ lit = 0; op++; /* start run */ diff --git a/lzf_c_best.c b/lzf_c_best.c index 13b175c..a997966 100644 --- a/lzf_c_best.c +++ b/lzf_c_best.c @@ -38,10 +38,6 @@ #define HASH(p) (p[0] << 6) ^ (p[1] << 3) ^ p[2] -#define MAX_LIT (1 << 5) -#define MAX_OFF (1 << 13) -#define MAX_REF ((1 << 8) + (1 << 3)) - #if __GNUC__ >= 3 # define expect(expr,value) __builtin_expect ((expr),(value)) # define inline inline @@ -64,15 +60,21 @@ unsigned int lzf_compress_best (const void *const in_data, unsigned int in_len, - void *out_data, unsigned int out_len) + void *out_data, unsigned int out_len +#if LZF_STATE_ARG + , LZF_STATE_BEST state +#endif + ) { const u8 *ip = (const u8 *)in_data; u8 *op = (u8 *)out_data; const u8 *in_end = ip + in_len; u8 *out_end = op + out_len; - const u8 *first [1 << (6+8)]; /* most recent occurance of a match */ - u16 prev [MAX_OFF]; /* how many bytes to go backwards for the next match */ +#if !LZF_STATE_ARG + LZF_STATE_BEST state; +#endif +#define STATE state[0] int lit; @@ -87,37 +89,37 @@ lzf_compress_best (const void *const in_data, unsigned int in_len, { int best_l = 0; const u8 *best_p; - int e = (in_end - ip < MAX_REF ? in_end - ip : MAX_REF) - 1; - unsigned int res = ((unsigned long)ip) & (MAX_OFF - 1); + int e = (in_end - ip < LZF_MAX_REF ? in_end - ip : LZF_MAX_REF) - 1; + unsigned int res = ((unsigned long)ip) & (LZF_MAX_OFF - 1); u16 hash = HASH (ip); u16 diff; - const u8 *b = ip < (u8 *)in_data + MAX_OFF ? in_data : ip - MAX_OFF; - const u8 *p = first [hash]; - prev [res] = ip - p; /* update ptr to previous hash match */ - first [hash] = ip; /* first hash match is here */ + const u8 *b = ip < (u8 *)in_data + LZF_MAX_OFF ? in_data : ip - LZF_MAX_OFF; + const u8 *p = STATE.first [hash]; + STATE.prev [res] = ip - p; /* update ptr to previous hash match */ + STATE.first [hash] = ip; /* first hash match is here */ if (p < ip) - while (p >= b) - { - if (p[2] == ip[2]) /* first two bytes almost always match */ - if (p[best_l] == ip[best_l]) /* new match must be longer than the old one to qualify */ - if (p[1] == ip[1] && p[0] == ip[0]) /* just to be sure */ - { - int l = 3; - - while (p[l] == ip[l] && l < e) - ++l; - - if (l >= best_l) - { - best_p = p; - best_l = l; - } - } - - diff = prev [((unsigned long)p) & (MAX_OFF - 1)]; - p = diff ? p - diff : 0; - } + while (p >= b) + { + if (p[2] == ip[2]) /* first two bytes almost always match */ + if (p[best_l] == ip[best_l]) /* new match must be longer than the old one to qualify */ + if (p[1] == ip[1] && p[0] == ip[0]) /* just to be sure */ + { + int l = 3; + + while (p[l] == ip[l] && l < e) + ++l; + + if (l >= best_l) + { + best_p = p; + best_l = l; + } + } + + diff = STATE.prev [((unsigned long)p) & (LZF_MAX_OFF - 1)]; + p = diff ? p - diff : 0; + } if (best_l) { @@ -159,11 +161,11 @@ lzf_compress_best (const void *const in_data, unsigned int in_len, do { u16 hash = HASH (ip); - res = ((unsigned long)ip) & (MAX_OFF - 1); + res = ((unsigned long)ip) & (LZF_MAX_OFF - 1); - p = first [hash]; - prev [res] = ip - p; /* update ptr to previous hash match */ - first [hash] = ip; /* first hash match is here */ + p = STATE.first [hash]; + STATE.prev [res] = ip - p; /* update ptr to previous hash match */ + STATE.first [hash] = ip; /* first hash match is here */ ip++; } @@ -177,7 +179,7 @@ lzf_compress_best (const void *const in_data, unsigned int in_len, lit++; *op++ = *ip++; - if (expect_false (lit == MAX_LIT)) + if (expect_false (lit == LZF_MAX_LIT)) { op [- lit - 1] = lit - 1; /* stop run */ lit = 0; op++; /* start run */ @@ -192,7 +194,7 @@ lzf_compress_best (const void *const in_data, unsigned int in_len, { lit++; *op++ = *ip++; - if (expect_false (lit == MAX_LIT)) + if (expect_false (lit == LZF_MAX_LIT)) { op [- lit - 1] = lit - 1; /* stop run */ lit = 0; op++; /* start run */ @@ -203,5 +205,8 @@ lzf_compress_best (const void *const in_data, unsigned int in_len, op -= !lit; /* undo run if length is zero */ return op - (u8 *)out_data; + +#undef STATE } + |