[hackers] [flate] deflate with fixed 32K block || nsz

From: <hg_AT_suckless.org>
Date: Fri, 21 Aug 2009 13:50:13 +0000 (UTC)

changeset: 104:e48c7741b70b
user: nsz <nszabolcs_AT_gmail.com>
date: Tue Aug 18 13:47:19 2009 +0200
files: Makefile deflate.c
description:
deflate with fixed 32K block

diff -r 1440204759f6 -r e48c7741b70b Makefile
--- a/Makefile Tue Aug 18 11:12:10 2009 +0200
+++ b/Makefile Tue Aug 18 13:47:19 2009 +0200
@@ -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 -r 1440204759f6 -r e48c7741b70b deflate.c
--- a/deflate.c Tue Aug 18 11:12:10 2009 +0200
+++ b/deflate.c Tue Aug 18 13:47:19 2009 +0200
@@ -18,17 +18,13 @@
         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 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 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 @@
 
         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 @@
                         }
                         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 @@
         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 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 @@
                 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 @@
                 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 @@
                 } 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 @@
         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 @@
                 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 @@
         }
         s->state = FlateOut;
         for (;;) {
- n = s->state = deflate_state(s);
+ n = deflate_state(s);
                 switch (n) {
                 case FlateIn:
                         len = r(s->src, SrcSize, rdata);
Received on Fri Aug 21 2009 - 13:50:13 UTC

This archive was generated by hypermail 2.2.0 : Fri Aug 21 2009 - 14:00:10 UTC