commit 8f48bb5e3d99531d9fb7eae7c71a8e288229719e
parent d33497ff1a084ba6e0d11741973808c5c83777d5
Author: nsz <nszabolcs@gmail.com>
Date: Tue, 18 Aug 2009 13:47:19 +0200
deflate with fixed 32K block
Diffstat:
| Makefile | | | 2 | +- |
| deflate.c | | | 82 | ++++++++++++++++++++++++++++--------------------------------------------------- |
2 files changed, 30 insertions(+), 54 deletions(-)
diff --git a/Makefile b/Makefile
@@ -1,5 +1,5 @@
#CFLAGS=-g -Wall -ansi -pedantic
-CFLAGS=-O3 -Wall -ansi -pedantic
+CFLAGS=-O3 -march=pentium4 -Wall -ansi -pedantic
LDFLAGS=
SRC=inflate.c inflate_example.c inflate_simple.c \
deflate.c deflate_example.c
diff --git a/deflate.c b/deflate.c
@@ -18,17 +18,13 @@ enum {
HashBits = 13,
HashSize = 1 << HashBits, /* hash table size */
BigDist = 1 << 12, /* max match distance for short match length */
- MaxDist = 1 << 15, /* max match distance for short match length */
+ MaxDist = WinSize - MaxMatch + 1, /* worst case available history */
+ StartPos = WinSize - MaxMatch + 1, /* block start position */
+ EndPos = 2*WinSize - MaxMatch + 1, /* block end position */
HistSize = 2*WinSize, /* history buffer size (64K, indexed with ushort) */
- HistEnd = MaxMatch + MinMatch - 1, /* reserved space at the end of hist buffer */
- HistSafe = HistSize - HistEnd - WinSize, /* worst case available history */
- BlockSize = HistSafe, /* block size (should be <= HistSafe) */
- DstSize = BlockSize + MaxMatch + 6, /* output buffer size (worst case compressed block size + 1) */
+ DstSize = WinSize + MaxMatch + 6, /* worst case compressed block size */
LzSize = 1 << 13, /* lz buffer size */
- LzLitFlag = 1 << 15, /* marks literal run length in lz buffer */
-
- MinAvail = MaxMatch + MinMatch - 1,
- EndPos = HistSize - MinAvail
+ LzLitFlag = 1 << 15 /* marks literal run length in lz buffer */
};
typedef struct {
@@ -483,14 +479,14 @@ static int gethash(uchar *p) {
static int updatechain(State *s) {
int h, i;
-/* if (s->avail < MinMatch)
+ /* eliminating this check didn't make the code faster */
+ if (s->avail < MinMatch)
return 0;
-*/
h = gethash(s->hist + s->pos);
i = s->head[h];
s->head[h] = s->pos;
- if (i >= s->pos || s->pos >= HistSafe + i)
- return 0;
+ if (i >= s->pos || s->pos - i > MaxDist)
+ i = 0;
s->chain[s->pos % WinSize] = i;
return i;
}
@@ -499,7 +495,7 @@ static int updatechain(State *s) {
static Match getmatch(State *s, int mpos) {
Match m = {0, MinMatch-1};
int len;
- int limit = s->pos - HistSafe;
+ int limit = s->pos - MaxDist;
int chainlen = MaxChainLen;
uchar *q;
uchar *p = s->hist + s->pos;
@@ -507,7 +503,7 @@ static Match getmatch(State *s, int mpos) {
do {
q = s->hist + mpos;
- /* at least m.len+1 long */
+ /* next match should be at least m.len+1 long */
if (q[m.len] != p[m.len] || q[m.len-1] != p[m.len-1] || q[0] != p[0])
continue;
while (++p != end && *++q == *p);
@@ -521,6 +517,7 @@ static Match getmatch(State *s, int mpos) {
}
m.len = len;
}
+ /* >= limit can be allowed except if limit == 0 */
} while ((mpos = s->chain[mpos % WinSize]) > limit && --chainlen);
if (m.len < MinMatch || (m.len == MinMatch && m.dist > BigDist))
m.len = 0;
@@ -538,18 +535,6 @@ static void startblock(State *s) {
s->lfreq[EOB]++;
}
-/*
-correctness assertions:
- - pos < 64K in updatechain (head and chain is ushort)
- - updatechain has at least MinMatch input (except at eof)
- - getmatch has at least MaxMatch input in hist
- - getmatch has at least HistSafe history
- - lzbuf does not overflow before endblock
- - dstbuf does not overflow before endblock
- - updatehist only fails if src == srcend
- - startpos does not underflow during shift hist
-*/
-
/* if block should be ended then end it and shift input window */
static int endblock(State *s) {
int n;
@@ -579,16 +564,16 @@ static int endblock(State *s) {
static int fillwin(State *s) {
int n, k;
- /* s->avail <= MinAvail && s->pos < EndPos */
+ /* s->avail < MaxMatch && s->pos < EndPos */
if (!s->eof) {
k = s->srcend - s->src;
- n = 2*WinSize - s->pos - s->avail; /* s->avail + n > MinAvail */
+ n = 2*WinSize - s->pos - s->avail; /* s->avail + n >= MaxMatch */
if (k > n)
k = n;
memcpy(s->hist + s->pos + s->avail, s->src, k);
s->src += k;
s->avail += k;
- if (s->avail <= MinAvail) /* s->srcend == s->src */
+ if (s->avail < MaxMatch) /* s->srcend == s->src */
return 0;
}
return 1;
@@ -603,9 +588,9 @@ static int deflate_state(State *s) {
s->eof = s->src == s->srcend;
else if (s->state == FlateOut) {
if (s->dstbegin < s->dst)
- return FlateOut;
+ return (s->state = FlateOut);
if (s->eof)
- return FlateOk;
+ return (s->state = FlateOk);
startblock(s);
if (s->prevm.len)
s->pos++;
@@ -613,16 +598,11 @@ static int deflate_state(State *s) {
return s->state;
for (;;) {
- if (s->avail <= MinAvail) {
- if (s->eof && s->avail < MinMatch)
- while (s->avail) {
- recordlit(s, s->hist[s->pos++]);
- s->avail--;
- }
+ if (s->avail < MaxMatch) {
if (endblock(s))
- return FlateOut;
+ return (s->state = FlateOut);
if (!fillwin(s))
- return FlateIn;
+ return (s->state = FlateIn);
}
head = updatechain(s);
if (head)
@@ -634,16 +614,11 @@ static int deflate_state(State *s) {
} else if (s->prevm.len) {
recordmatch(s, s->prevm);
s->prevm.len -= 2;
- if (s->avail < s->prevm.len + MinMatch) {
- s->pos += s->prevm.len;
- s->avail -= s->prevm.len;
- s->prevm.len = 0;
- } else
- do {
- s->pos++;
- s->avail--;
- updatechain(s);
- } while (--s->prevm.len);
+ do {
+ s->pos++;
+ s->avail--;
+ updatechain(s);
+ } while (--s->prevm.len);
} else
recordlit(s, s->hist[s->pos]);
s->pos++;
@@ -674,13 +649,14 @@ static State *alloc_state(void) {
huffcodes(fixlcode, fixllen, Nlitlen);
huffcodes(fixdcode, fixdlen, Ndist);
s->dst = s->dstbegin = s->dstbuf;
- s->pos = s->startpos = WinSize;
+ s->pos = s->startpos = StartPos;
s->eof = 0;
s->avail = 0;
s->prevm.len = 0;
return s;
}
+
/* extern */
int deflate(FlateStream *stream) {
@@ -704,7 +680,7 @@ int deflate(FlateStream *stream) {
s->srcend = s->src + stream->nin;
stream->nin = 0;
}
- n = s->state = deflate_state(s);
+ n = deflate_state(s);
if (n == FlateOut) {
k = s->dst - s->dstbegin;
if (k < stream->nout)
@@ -734,7 +710,7 @@ int deflate_callback(int (*r)(void *, int, void *), void *rdata, int (*w)(void *
}
s->state = FlateOut;
for (;;) {
- n = s->state = deflate_state(s);
+ n = deflate_state(s);
switch (n) {
case FlateIn:
len = r(s->src, SrcSize, rdata);
