commit 1642ddea0105b95c4b88e7dd794656a13d5a777d
parent c10b847118d0735b2f65b002110a781ac2e8f0a5
Author: nsz <nszabolcs@gmail.com>
Date: Sun, 23 Aug 2009 14:38:24 +0200
deflate renames (wip)
Diffstat:
| deflate.c | | | 122 | +++++++++++++++++++++++++++++++------------------------------------------------ |
1 file changed, 47 insertions(+), 75 deletions(-)
diff --git a/deflate.c b/deflate.c
@@ -2,7 +2,6 @@
#include <string.h>
#include "flate.h"
-#include <stdio.h>
enum {
CodeBits = 16, /* max number of bits in a code + 1 */
EOB = 256, /* end of block symbol */
@@ -19,12 +18,11 @@ enum {
HashBits = 13,
HashSize = 1 << HashBits, /* hash table size */
BigDist = 1 << 12, /* max match distance for short match length */
- BlockSize = (1 << 15) - 234, /* --- */
- MaxDist = WinSize - MaxMatch,
- WinBufSize = 2*WinSize + MaxMatch,
+ BlockSize = (1 << 15) - 300, /* TODO */
+ MaxDist = WinSize,
+ SrcSize = 2*WinSize + MaxMatch,
DstSize = BlockSize + MaxMatch + 6, /* worst case compressed block size */
LzSize = 1 << 13, /* lz buffer size */
- LzEnd = LzSize - 2, /* guard lzbuf not to overflow in the next iteration */
LzLitFlag = 1 << 15 /* marks literal run length in lz buffer */
};
@@ -39,20 +37,20 @@ typedef struct {
} LzCode;
typedef struct {
+ int pos; /* position in input src */
+ int startpos; /* block start pos in input src */
+ int endpos; /* end of available bytes in src */
+ int skip; /* skipped hash chain updates (until next iter) */
int state; /* prev return value */
int eof; /* end of input */
- int pos; /* position in input win */
- int startpos; /* block start pos in input win */
- int endpos; /* end of available bytes in win */
- int skip; /* skipped hash chain updates (until next iter) */
Match prevm; /* previous (deferred) match */
- uchar *src; /* input data (not yet in win) */
- uchar *srcend;
+ int nin;
+ uchar *in; /* input data (not yet in src) */
uchar *dst; /* compressed output (position in dstbuf) */
uchar *dstbegin; /* start position of unflushed data in dstbuf */
uint bits;
int nbits;
- uchar win[WinBufSize]; /* input window */
+ uchar src[SrcSize]; /* input buf */
ushort head[HashSize]; /* position of hash chain heads */
ushort chain[WinSize]; /* hash chain */
LzCode lzbuf[LzSize]; /* literal run length, match len, match dist */
@@ -300,7 +298,7 @@ static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar
LzCode *lz;
uchar *p;
- for (lz = s->lzbuf, p = s->win + s->startpos; lz != s->lz; lz++)
+ for (lz = s->lzbuf, p = s->src + s->startpos; lz != s->lz; lz++)
if (lz->bits & LzLitFlag)
for (n = lz->n; n > 0; n--, p++)
putbits(s, lcode[*p], llen[*p]);
@@ -360,7 +358,7 @@ static void deflate_block(State *s) {
dynsize += 7;
}
dyntree = dynsize - 3;
- for (lz = s->lzbuf, p = s->win + s->startpos; lz != s->lz; lz++)
+ for (lz = s->lzbuf, p = s->src + s->startpos; lz != s->lz; lz++)
if (lz->bits & LzLitFlag)
for (n = lz->n; n > 0; n--, p++) {
fixsize += fixllen[*p];
@@ -413,7 +411,7 @@ static void deflate_block(State *s) {
s->nbits = 0;
putbits(s, blocklen, 16);
putbits(s, ~blocklen & 0xffff, 16);
- memcpy(s->dst, s->win + s->startpos, blocklen);
+ memcpy(s->dst, s->src + s->startpos, blocklen);
s->dst += blocklen;
}
/*
@@ -481,12 +479,12 @@ static int gethash(uchar *p) {
/* update hash chain at the current position */
static int updatechain(State *s) {
- int hash, next = 0, p = s->pos, i = p;
+ int hash, next = 0, p = s->pos, i;
if (s->endpos - p < MinMatch)
p = s->endpos - MinMatch;
- for (i -= s->skip; i <= p; i++) {
- hash = gethash(s->win + i);
+ for (i = s->pos - s->skip; i <= p; i++) {
+ hash = gethash(s->src + i);
next = s->head[hash];
s->head[hash] = i;
if (next >= i || i - next >= MaxDist)
@@ -504,22 +502,15 @@ static Match getmatch(State *s, int next) {
int limit = s->pos - MaxDist;
int chainlen = MaxChainLen;
uchar *q;
- uchar *p = s->win + s->pos;
+ uchar *p = s->src + s->pos;
uchar *end = p + MaxMatch;
do {
- q = s->win + next;
+ q = s->src + next;
/*fprintf(stderr,"match: next:%d pos:%d limit:%d\n", next, s->pos, limit);*/
/* 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;
- /* loop unroll: MaxMatch % 10 == 8 */
-/* while (*++q == *++p && *++q == *++p
- && *++q == *++p && *++q == *++p
- && *++q == *++p && *++q == *++p
- && *++q == *++p && ++p != end && *++q == *p
- && *++q == *++p && *++q == *++p);
-*/
while (++p != end && *++q == *p);
len = MaxMatch - (end - p);
p -= len;
@@ -540,7 +531,6 @@ static Match getmatch(State *s, int next) {
return m;
}
-/* start a new block */
static void startblock(State *s) {
s->startpos = s->pos;
s->dst = s->dstbegin = s->dstbuf;
@@ -556,30 +546,22 @@ static int shiftwin(State *s) {
if (s->startpos < WinSize)
return 0;
- memmove(s->win, s->win + WinSize, WinBufSize - WinSize);
+ memmove(s->src, s->src + WinSize, SrcSize - 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;
-/* n++;
- s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0;
- n++;
+ for (n = 0; n < WinSize; n++)
s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0;
- n++;
- s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0;
-*/ }
s->pos -= WinSize;
s->startpos -= WinSize;
s->endpos -= WinSize;
return 1;
}
-/* if block should be ended then end it and shift input window */
static int endblock(State *s) {
- if ((s->pos >= 2*WinSize && !shiftwin(s)) ||
- s->pos - s->startpos >= BlockSize ||
- s->lz - s->lzbuf >= LzEnd ||
- (s->eof && s->pos == s->endpos)) {
+ LzCode *lzend = s->lzbuf + LzSize - 2;
+
+ if ((s->pos >= 2*WinSize && !shiftwin(s)) || s->pos - s->startpos >= BlockSize ||
+ s->lz >= lzend || (s->eof && s->pos == s->endpos)) {
/* deflate block */
flushlit(s);
if (s->prevm.len)
@@ -592,23 +574,18 @@ static int endblock(State *s) {
return 0;
}
-/* fill input window */
-static int fillwin(State *s) {
- int n, k;
+static int fillsrc(State *s) {
+ int n;
-/* todo: lzend */
- if (s->endpos < WinBufSize && !s->eof) {
- k = s->srcend - s->src;
- n = WinBufSize - s->endpos;
- if (k > n)
- k = n;
- memcpy(s->win + s->endpos, s->src, k);
- s->src += k;
- s->endpos += k;
-/*
-fprintf(stderr,"fill: pos:%d k:%d n:%d end:%d start:%d\n", s->pos, k, n, s->endpos, s->startpos);
-*/
- if (s->endpos < WinBufSize)
+ if (s->endpos < SrcSize && !s->eof) {
+ n = SrcSize - s->endpos;
+ if (n > s->nin)
+ n = s->nin;
+ memcpy(s->src + s->endpos, s->in, n);
+ s->in += n;
+ s->nin -= n;
+ s->endpos += n;
+ if (s->endpos < SrcSize)
return 0;
}
return 1;
@@ -629,7 +606,7 @@ static int deflate_state(State *s) {
LzCode *lzend;
if (s->state == FlateIn)
- s->eof = s->src == s->srcend;
+ s->eof = s->nin == 0;
else if (s->state == FlateOut) {
if (s->dstbegin < s->dst)
return (s->state = FlateOut);
@@ -641,31 +618,24 @@ static int deflate_state(State *s) {
} else
return s->state;
- lzend = s->lzbuf + LzSize - 2;
guard = calcguard(s);
-/*fprintf(stderr,"guard:%d pos:%d\n", guard, s->pos);*/
+ lzend = s->lzbuf + LzSize - 2;
+/*fprintf(stderr,"guard:%d pos:%d nin:%d\n", guard, s->pos, s->nin);*/
for (;;) {
if (s->pos >= guard || s->lz >= lzend) {
-/*fprintf(stderr,"guard:%d pos:%d len:%d end:%d start:%d\n", guard, s->pos, s->pos - s->startpos, s->endpos, s->startpos);*/
+/*fprintf(stderr,"guard:%d pos:%d len:%d end:%d start:%d nin:%d\n", guard, s->pos, s->pos - s->startpos, s->endpos, s->startpos, s->nin);*/
if (endblock(s))
return (s->state = FlateOut);
- if (!fillwin(s))
+ if (!fillsrc(s))
return (s->state = FlateIn);
guard = calcguard(s);
}
-/*
-if (s->lz - s->lzbuf > LzEnd - 3)
-fprintf(stderr, "near lzend: %d, len:%d\n", s->lz-s->lzbuf, s->pos - s->startpos);
-*/
next = updatechain(s);
if (next)
-{
m = getmatch(s, next);
-/*fprintf(stderr, "pos:%d len:%d next:%d match:%d,%d\n", s->pos, s->pos - s->startpos, next, m.len, m.dist);*/
-}
if (next && m.len > s->prevm.len) {
if (s->prevm.len)
- recordlit(s, s->win[s->pos-1]);
+ recordlit(s, s->src[s->pos-1]);
s->prevm = m;
} else if (s->prevm.len) {
recordmatch(s, s->prevm);
@@ -673,7 +643,7 @@ fprintf(stderr, "near lzend: %d, len:%d\n", s->lz-s->lzbuf, s->pos - s->startpos
s->prevm.len = 0;
s->pos += s->skip;
} else
- recordlit(s, s->win[s->pos]);
+ recordlit(s, s->src[s->pos]);
s->pos++;
}
}
@@ -701,7 +671,7 @@ static State *alloc_state(void) {
huffcodes(fixlcode, fixllen, Nlitlen);
huffcodes(fixdcode, fixdlen, Ndist);
s->state = FlateOut;
- s->src = s->srcend = 0;
+ s->nin = 0;
s->dst = s->dstbegin = s->dstbuf;
s->pos = s->startpos = s->endpos = WinSize;
s->eof = 0;
@@ -728,8 +698,8 @@ int deflate(FlateStream *stream) {
return stream->err = "no mem.", FlateErr;
}
if (stream->nin) {
- s->src = stream->in;
- s->srcend = s->src + stream->nin;
+ s->in = stream->in;
+ s->nin = stream->nin;
stream->nin = 0;
}
n = deflate_state(s);
@@ -747,6 +717,7 @@ int deflate(FlateStream *stream) {
return n;
}
+/*
int deflate_callback(int (*r)(void *, int, void *), void *rdata, int (*w)(void *, int, void *), void *wdata) {
State *s;
uchar *src;
@@ -784,3 +755,4 @@ int deflate_callback(int (*r)(void *, int, void *), void *rdata, int (*w)(void *
}
}
}
+*/
