[hackers] [flate] deflate at fixed endpos, removing avail check made the code slower! || nsz

changeset: 103:1440204759f6
user: nsz <nszabolcs_AT_gmail.com>
date: Tue Aug 18 11:12:10 2009 +0200
files: deflate.c
description:
deflate at fixed endpos, removing avail check made the code slower!

diff -r 4a4dda29bc6a -r 1440204759f6 deflate.c
--- a/deflate.c Sun Aug 16 15:26:55 2009 +0200
+++ b/deflate.c Tue Aug 18 11:12:10 2009 +0200
@@ -18,13 +18,17 @@
         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 */
         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) */
         LzSize = 1 << 13, /* lz buffer size */
- LzLitFlag = 1 << 15 /* marks literal run length in lz buffer */
+ LzLitFlag = 1 << 15, /* marks literal run length in lz buffer */
+
+ MinAvail = MaxMatch + MinMatch - 1,
+ EndPos = HistSize - MinAvail
 };
 
 typedef struct {
@@ -479,13 +483,14 @@
 static int updatechain(State *s) {
         int h, i;
 
- if (s->avail < MinMatch) /* assert(s->eof) */
+/* 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 - i >= HistSafe)
- i = 0;
+ if (i >= s->pos || s->pos >= HistSafe + i)
+ return 0;
         s->chain[s->pos % WinSize] = i;
         return i;
 }
@@ -523,7 +528,7 @@
 }
 
 /* start a new block */
-static void newblock(State *s) {
+static void startblock(State *s) {
         s->startpos = s->pos;
         s->dst = s->dstbegin = s->dstbuf;
         s->lz = s->lzbuf;
@@ -545,40 +550,50 @@
         - startpos does not underflow during shift hist
 */
 
-/* shift and fill s->hist */
-static int updatehist(State *s) {
- int n, k;
+/* if block should be ended then end it and shift input window */
+static int endblock(State *s) {
+ int n;
 
- if (s->pos >= HistSize - HistEnd) {
- /* shift hist */
- memcpy(s->hist, s->hist + WinSize, HistSize - WinSize);
+ if (s->pos >= EndPos || s->lz - s->lzbuf > LzSize - 3 || (s->eof && s->avail == 0)) {
+ /* deflate block */
+ flushlit(s);
+ if (s->prevm.len)
+ s->pos--;
+ deflate_block(s);
+ if (s->eof) {
+ putbits(s, 0, 7);
+ return 1;
+ }
+ /* shift input window */
+ memcpy(s->hist, s->hist + WinSize, WinSize);
                 for (n = 0; n < HashSize; n++)
                         s->head[n] = s->head[n] > WinSize ? s->head[n] - WinSize : 0;
                 for (n = 0; n < WinSize; n++)
                         s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0;
- s->startpos -= WinSize;
                 s->pos -= WinSize;
+ return 1;
         }
- if (s->avail <= HistEnd && !s->eof) {
- /* fill hist */
+ return 0;
+}
+
+static int fillwin(State *s) {
+ int n, k;
+
+ /* s->avail <= MinAvail && s->pos < EndPos */
+ if (!s->eof) {
                 k = s->srcend - s->src;
- n = HistSize - s->pos - s->avail; /* s->avail + n > HistEnd */
+ n = 2*WinSize - s->pos - s->avail; /* s->avail + n > MinAvail */
                 if (k > n)
                         k = n;
                 memcpy(s->hist + s->pos + s->avail, s->src, k);
                 s->src += k;
                 s->avail += k;
- if (s->avail <= HistEnd) /* s->srcend == s->src */
+ if (s->avail <= MinAvail) /* s->srcend == s->src */
                         return 0;
         }
         return 1;
 }
 
-/* check if the current block should be ended */
-static int endofblock(State *s) {
- return s->avail == 0 || s->pos - s->startpos >= BlockSize || s->lz - s->lzbuf > LzSize - 3;
-}
-
 /* deflate from s->src into s->dstbuf */
 static int deflate_state(State *s) {
         Match m;
@@ -591,23 +606,23 @@
                         return FlateOut;
                 if (s->eof)
                         return FlateOk;
- newblock(s);
+ startblock(s);
                 if (s->prevm.len)
                         s->pos++;
         } else
                 return s->state;
 
         for (;;) {
- if (!updatehist(s))
- return FlateIn;
- if (endofblock(s)) {
- flushlit(s);
- if (s->prevm.len)
- s->pos--;
- deflate_block(s);
- if (s->eof)
- putbits(s, 0, 7);
- return FlateOut;
+ if (s->avail <= MinAvail) {
+ if (s->eof && s->avail < MinMatch)
+ while (s->avail) {
+ recordlit(s, s->hist[s->pos++]);
+ s->avail--;
+ }
+ if (endblock(s))
+ return FlateOut;
+ if (!fillwin(s))
+ return FlateIn;
                 }
                 head = updatechain(s);
                 if (head)
@@ -619,11 +634,16 @@
                 } else if (s->prevm.len) {
                         recordmatch(s, s->prevm);
                         s->prevm.len -= 2;
- do {
- s->pos++;
- s->avail--;
- updatechain(s);
- } while (--s->prevm.len);
+ 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);
                 } else
                         recordlit(s, s->hist[s->pos]);
                 s->pos++;
Received on Fri Aug 21 2009 - 13:50:13 UTC