Author: matz
Date: Sun Feb 17 19:08:02 2008
New Revision: 8771
URL: http://svn.opensuse.org/viewcvs/zypp?rev=8771&view=rev
Log:
Compress a bit better and faster.
Modified:
trunk/sat-solver/src/fastlz.c
Modified: trunk/sat-solver/src/fastlz.c
URL: http://svn.opensuse.org/viewcvs/zypp/trunk/sat-solver/src/fastlz.c?rev=8771&r1=8770&r2=8771&view=diff
==============================================================================
--- trunk/sat-solver/src/fastlz.c (original)
+++ trunk/sat-solver/src/fastlz.c Sun Feb 17 19:08:02 2008
@@ -5,13 +5,19 @@
* for further information
*/
+#include
#include
#include
#include
#include
#include
-#define BLOCK_SIZE 65536
+#define BLOCK_SIZE (65536*1)
+#if BLOCK_SIZE <= 65536
+typedef __uint16_t Ref;
+#else
+typedef __uint32_t Ref;
+#endif
/*
The format is tailored for fast decompression (i.e. only byte based),
@@ -60,8 +66,8 @@
unsigned int oo = 0; //out-offset
unsigned int io = 0; //in-offset
#define HS (65536)
- unsigned short htab[HS];
- unsigned short hnext[BLOCK_SIZE];
+ unsigned int htab[HS];
+ unsigned int hnext[BLOCK_SIZE];
memset (htab, 0, sizeof (htab));
memset (hnext, 0, sizeof (hnext));
unsigned int litofs = 0;
@@ -78,30 +84,96 @@
htab[hval] = io;
mlen = 0;
mofs = 0;
+
for (tries = 0; tries < 4; tries++)
- {
- unsigned int this_len, this_ofs;
- this_len = 0;
- this_ofs = 0;
- if (try < io)
+ {
+ if (try < io
+ && in[try] == in[io] && in[try + 1] == in[io + 1])
{
+ mlen = 2;
+ mofs = (io - try) - 1;
+ break;
+ }
+ try = hnext[try];
+ }
+ for (; tries < 4; tries++)
+ {
+ //assert (mlen >= 2);
+ //assert (io + mlen < in_len);
+ /* Try a match starting from [io] with the strings at [try].
+ That's only sensible if TRY actually is before IO (can happen
+ with uninit hash table). If we have a previous match already
+ we're only going to take the new one if it's longer, hence
+ check the potentially last character. */
+ if (try < io && in[try + mlen] == in[io + mlen])
+ {
+ unsigned int this_len, this_ofs;
+ if (memcmp (in + try, in + io, mlen))
+ goto no_match;
+ this_len = mlen + 1;
+ /* Now try extending the match by more characters. */
for (;
io + this_len < in_len
&& in[try + this_len] == in[io + this_len]; this_len++)
;
+#if 0
+ unsigned int testi;
+ for (testi = 0; testi < this_len; testi++)
+ assert (in[try + testi] == in[io + testi]);
+#endif
this_ofs = (io - try) - 1;
- if (this_len < 2)
- this_len = 0;
- else if (this_len == 2 && (litofs || ((io - try) - 1) >= 1024))
- this_len = 0;
- else if (this_len >= 4096 + 18)
- this_len = 4095 + 18;
- else if (this_ofs >= 65536)
- this_len = 0;
- if (this_len > mlen || (this_len == mlen && this_ofs < mofs))
- mlen = this_len, mofs = this_ofs;
+ /*if (this_ofs > 65535)
+ goto no_match; */
+#if 0
+ assert (this_len >= 2);
+ assert (this_len >= mlen);
+ assert (this_len > mlen || (this_len == mlen && this_ofs > mofs));
+#endif
+ mlen = this_len, mofs = this_ofs;
+ /* If our match extends up to the end of input, no next
+ match can become better. This is not just an
+ optimization, it establishes a loop invariant
+ (io + mlen < in_len). */
+ if (io + mlen >= in_len)
+ goto match_done;
}
+ no_match:
try = hnext[try];
+ if (io - try - 1 >= 65536)
+ break;
+ }
+
+match_done:
+ if (mlen)
+ {
+ if (mlen == 2 && (0 || litofs || mofs >= 1024))
+ mlen = 0;
+ else if (mofs >= 65536)
+ mlen = 0;
+ else if (mlen >= 4096 + 18)
+ mlen = 4095 + 18;
+ if (mlen && io + 3 < in_len)
+ {
+ unsigned int hval =
+ in[io + 1] | in[io + 2] << 8 | in[io + 3] << 16;
+ unsigned int try;
+ hval = (hval ^ (hval << 5) ^ (hval >> 5)) - hval * 5;
+ hval = hval & (HS - 1);
+ try = htab[hval];
+ if (try < io + 1
+ && in[try] == in[io + 1] && in[try + 1] == in[io + 2])
+ {
+ unsigned int this_len;
+ this_len = 2;
+ for (;
+ io + 1 + this_len < in_len
+ && in[try + this_len] == in[io + 1 + this_len];
+ this_len++)
+ ;
+ if (this_len >= mlen)
+ mlen = 0;
+ }
+ }
}
if (!mlen)
{
@@ -118,23 +190,27 @@
//fprintf (stderr, "lit: %d\n", litlen);
while (litlen)
{
- if (litlen == 1 && in[litofs] < 0x80)
- {
- if (oo + 1 >= out_len)
- return 0;
- out[oo++] = in[litofs++];
- break;
- }
- else if (litlen == 2 && in[litofs] < 0x80
- && in[litofs + 1] < 0x80)
+ unsigned int easy_sz;
+ /* Emit everything we can as self-describers. As soon as
+ we hit a byte we can't emit as such we're going to emit
+ a length descriptor anyway, so we can as well include
+ bytes < 0x80 which might follow afterwards in that run. */
+ for (easy_sz = 0;
+ easy_sz < litlen && in[litofs + easy_sz] < 0x80;
+ easy_sz++)
+ ;
+ if (easy_sz)
{
- if (oo + 2 >= out_len)
+ if (oo + easy_sz >= out_len)
return 0;
- out[oo++] = in[litofs++];
- out[oo++] = in[litofs++];
- break;
+ memcpy (out + oo, in + litofs, easy_sz);
+ litofs += easy_sz;
+ oo += easy_sz;
+ litlen -= easy_sz;
+ if (!litlen)
+ break;
}
- else if (litlen <= 32)
+ if (litlen <= 32)
{
if (oo + 1 + litlen >= out_len)
return 0;
@@ -226,22 +302,26 @@
//fprintf (stderr, "lit: %d\n", litlen);
while (litlen)
{
- if (litlen == 1 && in[litofs] < 0x80)
+ unsigned int easy_sz;
+ /* Emit everything we can as self-describers. As soon as we hit a
+ byte we can't emit as such we're going to emit a length
+ descriptor anyway, so we can as well include bytes < 0x80 which
+ might follow afterwards in that run. */
+ for (easy_sz = 0; easy_sz < litlen && in[litofs + easy_sz] < 0x80;
+ easy_sz++)
+ ;
+ if (easy_sz)
{
- if (oo + 1 >= out_len)
+ if (oo + easy_sz >= out_len)
return 0;
- out[oo++] = in[litofs++];
- break;
- }
- else if (litlen == 2 && in[litofs] < 0x80 && in[litofs + 1] < 0x80)
- {
- if (oo + 2 >= out_len)
- return 0;
- out[oo++] = in[litofs++];
- out[oo++] = in[litofs++];
- break;
+ memcpy (out + oo, in + litofs, easy_sz);
+ litofs += easy_sz;
+ oo += easy_sz;
+ litlen -= easy_sz;
+ if (!litlen)
+ break;
}
- else if (litlen <= 32)
+ if (litlen <= 32)
{
if (oo + 1 + litlen >= out_len)
return 0;
--
To unsubscribe, e-mail: zypp-commit+unsubscribe@opensuse.org
For additional commands, e-mail: zypp-commit+help@opensuse.org
