aboutsummaryrefslogtreecommitdiff
path: root/toys/pending/gzip.c
diff options
context:
space:
mode:
Diffstat (limited to 'toys/pending/gzip.c')
-rw-r--r--toys/pending/gzip.c627
1 files changed, 290 insertions, 337 deletions
diff --git a/toys/pending/gzip.c b/toys/pending/gzip.c
index 4c8bdd24..00775934 100644
--- a/toys/pending/gzip.c
+++ b/toys/pending/gzip.c
@@ -58,7 +58,8 @@ uint crc32(uchar *p, int n, uint crc);
uint crctab[256];
-void crc32init(void) {
+void crc32init(void)
+{
static const uint poly = 0xedb88320;
int i,j;
@@ -66,21 +67,20 @@ void crc32init(void) {
uint crc = i;
for (j = 0; j < 8; j++) {
- if (crc & 1)
- crc = (crc >> 1) ^ poly;
- else
- crc >>= 1;
+ if (crc & 1) crc = (crc >> 1) ^ poly;
+ else crc >>= 1;
}
crctab[i] = crc;
}
}
-uint crc32(uchar *p, int n, uint crc) {
+uint crc32(uchar *p, int n, uint crc)
+{
uchar *ep = p + n;
crc ^= 0xffffffff;
- while (p < ep)
- crc = crctab[(crc & 0xff) ^ *p++] ^ (crc >> 8);
+ while (p < ep) crc = crctab[(crc & 0xff) ^ *p++] ^ (crc >> 8);
+
return crc ^ 0xffffffff;
}
@@ -89,7 +89,8 @@ enum {
AdlerN = 5552 /* max iters before 32bit overflow */
};
-uint adler32(uchar *p, int n, uint adler) {
+uint adler32(uchar *p, int n, uint adler)
+{
uint s1 = adler & 0xffff;
uint s2 = (adler >> 16) & 0xffff;
uchar *ep;
@@ -262,18 +263,18 @@ static uchar clenorder[Nclen] = {
static uint revinc(uint n, uint len) {
uint i = 1 << (len - 1);
- while (n & i)
- i >>= 1;
+ while (n & i) i >>= 1;
if (i) {
n &= i - 1;
n |= i;
- } else
- n = 0;
+ } else n = 0;
+
return n;
}
/* build huffman code tree from code lengths (each should be < CodeBits) */
-static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) {
+static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits)
+{
int offs[CodeBits];
int left;
uint i, c, sum, code, len, min, max;
@@ -283,10 +284,8 @@ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) {
Entry entry;
/* count code lengths */
- for (i = 0; i < CodeBits; i++)
- count[i] = 0;
- for (i = 0; i < n; i++)
- count[lens[i]]++;
+ for (i = 0; i < CodeBits; i++) count[i] = 0;
+ for (i = 0; i < n; i++) count[lens[i]]++;
if (count[0] == n) {
huff->nbits = table[0].len = 0;
return 0;
@@ -294,18 +293,12 @@ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) {
count[0] = 0;
/* bound code lengths, force nbits to be within the bounds */
- for (max = CodeBits - 1; max > 0; max--)
- if (count[max] != 0)
- break;
- if (nbits > max)
- nbits = max;
- for (min = 1; min < CodeBits; min++)
- if (count[min] != 0)
- break;
+ for (max = CodeBits - 1; max > 0; max--) if (count[max] != 0) break;
+ if (nbits > max) nbits = max;
+ for (min = 1; min < CodeBits; min++) if (count[min] != 0) break;
if (nbits < min) {
nbits = min;
- if (nbits > TableBits)
- return -1;
+ if (nbits > TableBits) return -1;
}
huff->nbits = nbits;
@@ -313,8 +306,7 @@ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) {
for (left = 1 << min, i = min; i <= max; left <<= 1, i++) {
left -= count[i];
/* left < 0: over-subscribed, left > 0: incomplete */
- if (left < 0)
- return -1;
+ if (left < 0) return -1;
}
for (sum = 0, i = 0; i <= max; i++) {
@@ -322,25 +314,20 @@ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) {
sum += count[i];
}
/* needed for decoding codes longer than nbits */
- if (nbits < max)
- huff->sum = offs[nbits + 1];
+ if (nbits < max) huff->sum = offs[nbits + 1];
/* sort symbols by code length (lexicographic order) */
- for (i = 0; i < n; i++)
- if (lens[i])
- symbol[offs[lens[i]]++] = i;
+ for (i = 0; i < n; i++) if (lens[i]) symbol[offs[lens[i]]++] = i;
/* lookup table for decoding nbits from input.. */
- for (i = 0; i < 1 << nbits; i++)
- table[i].len = table[i].sym = 0;
+ for (i = 0; i < 1 << nbits; i++) table[i].len = table[i].sym = 0;
code = 0;
/* ..if code is at most nbits (bits are in reverse order, sigh..) */
for (len = min; len <= nbits; len++)
for (c = count[len]; c > 0; c--) {
entry.len = len;
entry.sym = *symbol;
- for (i = code; i < 1 << nbits; i += 1 << len)
- table[i] = entry;
+ for (i = code; i < 1 << nbits; i += 1 << len) table[i] = entry;
/* next code */
symbol++;
code = revinc(code, len);
@@ -351,60 +338,65 @@ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) {
table[code].sym = i << 1;
code = revinc(code, nbits);
}
+
return 0;
}
/* fixed huffman code trees (should be done at compile time..) */
-static void init_fixed_huffs(void) {
+static void init_fixed_huffs(void)
+{
int i;
uchar lens[Nlitlen];
- for (i = 0; i < 144; i++)
- lens[i] = 8;
- for (; i < 256; i++)
- lens[i] = 9;
- for (; i < 280; i++)
- lens[i] = 7;
- for (; i < Nlitlen; i++)
- lens[i] = 8;
+ for (i = 0; i < 144; i++) lens[i] = 8;
+ for (; i < 256; i++) lens[i] = 9;
+ for (; i < 280; i++) lens[i] = 7;
+ for (; i < Nlitlen; i++) lens[i] = 8;
build_huff(&lhuff, lens, Nlitlen, 8);
- for (i = 0; i < Ndist; i++)
- lens[i] = 5;
+ for (i = 0; i < Ndist; i++) lens[i] = 5;
build_huff(&dhuff, lens, Ndist, 5);
}
/* fill *bits with n bits from *src */
-static int fillbits_fast(uchar **src, uchar *srcend, uint *bits, uint *nbits, uint n) {
+static int fillbits_fast(uchar **src, uchar *srcend, uint *bits, uint *nbits,
+ uint n)
+{
while (*nbits < n) {
- if (*src == srcend)
- return 0;
+ if (*src == srcend) return 0;
*bits |= *(*src)++ << *nbits;
*nbits += 8;
}
+
return 1;
}
/* get n bits from *bits */
-static uint getbits_fast(uint *bits, uint *nbits, int n) {
+static uint getbits_fast(uint *bits, uint *nbits, int n)
+{
uint k;
k = *bits & ((1 << n) - 1);
*bits >>= n;
*nbits -= n;
+
return k;
}
-static int fillbits(DecodeState *s, uint n) {
+static int fillbits(DecodeState *s, uint n)
+{
return fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, n);
}
-static uint getbits(DecodeState *s, uint n) {
+static uint getbits(DecodeState *s, uint n)
+{
return getbits_fast(&s->bits, &s->nbits, n);
}
/* decode symbol bitwise if code is longer than huffbits */
-static uint decode_symbol_long(DecodeState *s, Huff *huff, uint bits, uint nbits, int cur) {
+static uint decode_symbol_long(DecodeState *s, Huff *huff, uint bits,
+ uint nbits, int cur)
+{
int sum = huff->sum;
uint huffbits = huff->nbits;
ushort *count = huff->count + huffbits + 1;
@@ -422,8 +414,7 @@ static uint decode_symbol_long(DecodeState *s, Huff *huff, uint bits, uint nbits
nbits -= huffbits;
for (;;) {
if (!nbits--) {
- if (s->src == s->srcend)
- return FlateIn;
+ if (s->src == s->srcend) return FlateIn;
bits = *s->src++;
nbits = 7;
}
@@ -431,8 +422,7 @@ static uint decode_symbol_long(DecodeState *s, Huff *huff, uint bits, uint nbits
bits >>= 1;
sum += *count;
cur -= *count;
- if (cur < 0)
- break;
+ if (cur < 0) break;
cur <<= 1;
count++;
if (count == huff->count + CodeBits)
@@ -440,11 +430,13 @@ static uint decode_symbol_long(DecodeState *s, Huff *huff, uint bits, uint nbits
}
s->bits = bits;
s->nbits = nbits;
+
return huff->symbol[sum + cur];
}
/* decode a symbol from stream with huff code */
-static uint decode_symbol(DecodeState *s, Huff *huff) {
+static uint decode_symbol(DecodeState *s, Huff *huff)
+{
uint huffbits = huff->nbits;
uint nbits = s->nbits;
uint bits = s->bits;
@@ -493,7 +485,8 @@ static uint decode_symbol(DecodeState *s, Huff *huff) {
}
/* decode a block of data from stream with trees */
-static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff) {
+static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff)
+{
uchar *win = s->win;
uint pos = s->pos;
uint sym = s->nclen;
@@ -516,12 +509,12 @@ static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff) {
if (sym >= Nlen) {
s->pos = pos;
s->state = DecodeBlock;
- if (sym + 257 == (uint)FlateIn)
- return FlateIn;
+ if (sym + 257 == (uint)FlateIn) return FlateIn;
return FlateErr;
}
case DecodeBlockLenBits:
- if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, lenbits[sym])) {
+ if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, lenbits[sym]))
+ {
s->nclen = sym; /* using nclen to store sym */
s->pos = pos;
s->state = DecodeBlockLenBits;
@@ -536,8 +529,7 @@ static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff) {
s->state = DecodeBlockDist;
return FlateIn;
}
- if (sym >= Ndist)
- return FlateErr;
+ if (sym >= Ndist) return FlateErr;
case DecodeBlockDistBits:
if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, distbits[sym])) {
s->nclen = sym; /* using nclen to store sym */
@@ -591,39 +583,31 @@ static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff) {
}
/* inflate state machine (decodes s->src into s->win) */
-static int inflate_state(DecodeState *s) {
+static int inflate_state(DecodeState *s)
+{
int n;
- if (s->posout)
- return FlateOut;
+ if (s->posout) return FlateOut;
for (;;) {
switch (s->state) {
case BlockHead:
if (s->final) {
- if (s->pos)
- return FlateOut;
- else
- return FlateOk;
+ if (s->pos) return FlateOut;
+ else return FlateOk;
}
- if (!fillbits(s, 3))
- return FlateIn;
+ if (!fillbits(s, 3)) return FlateIn;
s->final = getbits(s, 1);
n = getbits(s, 2);
- if (n == 0)
- s->state = UncompressedBlock;
- else if (n == 1)
- s->state = FixedHuff;
- else if (n == 2)
- s->state = DynamicHuff;
- else
- return s->err = "corrupt block header.", FlateErr;
+ if (n == 0) s->state = UncompressedBlock;
+ else if (n == 1) s->state = FixedHuff;
+ else if (n == 2) s->state = DynamicHuff;
+ else return s->err = "corrupt block header.", FlateErr;
break;
case UncompressedBlock:
/* start block on a byte boundary */
s->bits >>= s->nbits & 7;
s->nbits &= ~7;
- if (!fillbits(s, 32))
- return FlateIn;
+ if (!fillbits(s, 32)) return FlateIn;
s->lenpos = getbits(s, 16);
n = getbits(s, 16);
if (s->lenpos != (~n & 0xffff))
@@ -633,12 +617,10 @@ static int inflate_state(DecodeState *s) {
/* TODO: untested, slow, memcpy etc */
/* s->nbits should be 0 here */
while (s->lenpos) {
- if (s->src == s->srcend)
- return FlateIn;
+ if (s->src == s->srcend) return FlateIn;
s->lenpos--;
s->win[s->pos++] = *s->src++;
- if (s->pos == WinSize)
- return FlateOut;
+ if (s->pos == WinSize) return FlateOut;
}
s->state = BlockHead;
break;
@@ -648,24 +630,21 @@ static int inflate_state(DecodeState *s) {
break;
case DynamicHuff:
/* decode dynamic huffman code trees */
- if (!fillbits(s, 14))
- return FlateIn;
+ if (!fillbits(s, 14)) return FlateIn;
s->nlit = 257 + getbits(s, 5);
s->ndist = 1 + getbits(s, 5);
s->nclen = 4 + getbits(s, 4);
if (s->nlit > Nlitlen || s->ndist > Ndist)
return s->err = "corrupt code tree.", FlateErr;
/* build code length tree */
- for (n = 0; n < Nclen; n++)
- s->lens[n] = 0;
+ for (n = 0; n < Nclen; n++) s->lens[n] = 0;
s->fixed = 0;
s->state = DynamicHuffClen;
s->lenpos = 0;
case DynamicHuffClen:
for (n = s->lenpos; n < s->nclen; n++)
- if (fillbits(s, 3)) {
- s->lens[clenorder[n]] = getbits(s, 3);
- } else {
+ if (fillbits(s, 3)) s->lens[clenorder[n]] = getbits(s, 3);
+ else {
s->lenpos = n;
return FlateIn;
}
@@ -709,14 +688,11 @@ static int inflate_state(DecodeState *s) {
s->lens[n++] = c;
} else if (sym == 17) {
/* repeat 0 for 3-10 times */
- for (len = 3 + getbits(s, 3); len; len--)
- s->lens[n++] = 0;
+ for (len = 3 + getbits(s, 3); len; len--) s->lens[n++] = 0;
} else if (sym == 18) {
/* repeat 0 for 11-138 times */
- for (len = 11 + getbits(s, 7); len; len--)
- s->lens[n++] = 0;
- } else
- return s->err = "corrupt code tree.", FlateErr;
+ for (len = 11 + getbits(s, 7); len; len--) s->lens[n++] = 0;
+ } else return s->err = "corrupt code tree.", FlateErr;
}
/* build dynamic huffman code trees */
if (build_huff(&s->lhuff, s->lens, s->nlit, LitlenTableBits) < 0)
@@ -740,7 +716,8 @@ static int inflate_state(DecodeState *s) {
}
}
-static DecodeState *alloc_decode_state(void) {
+static DecodeState *alloc_decode_state(void)
+{
DecodeState *s = malloc(sizeof(DecodeState));
if (s) {
@@ -749,8 +726,7 @@ static DecodeState *alloc_decode_state(void) {
s->src = s->srcend = 0;
s->err = 0;
/* TODO: globals.. */
- if (lhuff.nbits == 0)
- init_fixed_huffs();
+ if (lhuff.nbits == 0) init_fixed_huffs();
}
return s;
}
@@ -758,7 +734,8 @@ static DecodeState *alloc_decode_state(void) {
/* extern */
-int inflate(FlateStream *stream) {
+int inflate(FlateStream *stream)
+{
DecodeState *s = stream->state;
int n;
@@ -771,8 +748,7 @@ int inflate(FlateStream *stream) {
}
if (!s) {
s = stream->state = alloc_decode_state();
- if (!s)
- return stream->err = "no mem.", FlateErr;
+ if (!s) return stream->err = "no mem.", FlateErr;
}
if (stream->nin) {
s->src = stream->in;
@@ -781,14 +757,11 @@ int inflate(FlateStream *stream) {
}
n = inflate_state(s);
if (n == FlateOut) {
- if (s->pos < stream->nout)
- stream->nout = s->pos;
+ if (s->pos < stream->nout) stream->nout = s->pos;
memcpy(stream->out, s->win + s->posout, stream->nout);
s->pos -= stream->nout;
- if (s->pos)
- s->posout += stream->nout;
- else
- s->posout = 0;
+ if (s->pos) s->posout += stream->nout;
+ else s->posout = 0;
}
if (n == FlateOk || n == FlateErr) {
if (s->nbits || s->src < s->srcend) {
@@ -843,7 +816,8 @@ static ushort fixlcode[Nlitlen];
static uchar fixdlen[Ndist]; /* fixed distance huffman code tree */
static ushort fixdcode[Ndist];
-static uint revcode(uint c, int n) {
+static uint revcode(uint c, int n)
+{
int i;
uint r = 0;
@@ -855,37 +829,34 @@ static uint revcode(uint c, int n) {
}
/* build huffman code tree from code lengths */
-static void huffcodes(ushort *codes, const uchar *lens, int n) {
+static void huffcodes(ushort *codes, const uchar *lens, int n)
+{
int c[CodeBits];
int i, code, count;
/* count code lengths and calc first code for each length */
- for (i = 0; i < CodeBits; i++)
- c[i] = 0;
- for (i = 0; i < n; i++)
- c[lens[i]]++;
+ for (i = 0; i < CodeBits; i++) c[i] = 0;
+ for (i = 0; i < n; i++) c[lens[i]]++;
for (code = 0, i = 1; i < CodeBits; i++) {
count = c[i];
c[i] = code;
code += count;
- if (code > (1 << i))
- abort(); /* over-subscribed */
+ if (code > (1 << i)) abort(); /* over-subscribed */
code <<= 1;
}
if (code < (1 << i))
/* incomplete */;
for (i = 0; i < n; i++)
- if (lens[i])
- codes[i] = revcode(c[lens[i]]++, lens[i]);
- else
- codes[i] = 0;
+ if (lens[i]) codes[i] = revcode(c[lens[i]]++, lens[i]);
+ else codes[i] = 0;
}
static int heapparent(int n) {return (n - 2)/4 * 2;}
static int heapchild(int n) {return 2 * n + 2;}
-static int heappush(int *heap, int len, int w, int n) {
+static int heappush(int *heap, int len, int w, int n)
+{
int p, c, tmp;
c = len;
@@ -897,13 +868,13 @@ static int heappush(int *heap, int len, int w, int n) {
tmp = heap[c]; heap[c] = heap[p]; heap[p] = tmp;
tmp = heap[c+1]; heap[c+1] = heap[p+1]; heap[p+1] = tmp;
c = p;
- } else
- break;
+ } else break;
}
return len;
}
-static int heappop(int *heap, int len, int *w, int *n) {
+static int heappop(int *heap, int len, int *w, int *n)
+{
int p, c, tmp;
*n = heap[0];
@@ -913,22 +884,20 @@ static int heappop(int *heap, int len, int *w, int *n) {
p = 0;
for (;;) {
c = heapchild(p);
- if (c >= len)
- break;
- if (c+2 < len && heap[c+3] < heap[c+1])
- c += 2;
+ if (c >= len) break;
+ if (c+2 < len && heap[c+3] < heap[c+1]) c += 2;
if (heap[p+1] > heap[c+1]) {
tmp = heap[p]; heap[p] = heap[c]; heap[c] = tmp;
tmp = heap[p+1]; heap[p+1] = heap[c+1]; heap[c+1] = tmp;
- } else
- break;
+ } else break;
p = c;
}
return len;
}
/* symbol frequencies -> code lengths (limited to 255) */
-static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) {
+static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit)
+{
/* 2 <= nsym <= Nlitlen, log(nsym) <= limit <= CodeBits-1 */
int parent[2*Nlitlen-1];
int count[CodeBits];
@@ -937,17 +906,13 @@ static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) {
int i, j;
int wi, wj;
- for (n = 0; n < limit+1; n++)
- count[n] = 0;
+ for (n = 0; n < limit+1; n++) count[n] = 0;
for (len = n = 0; n < nsym; n++)
- if (freqs[n] > 0)
- len = heappush(heap, len, freqs[n], n);
- else
- lens[n] = 0;
+ if (freqs[n] > 0) len = heappush(heap, len, freqs[n], n);
+ else lens[n] = 0;
/* deflate: fewer than two symbols: add new */
for (n = 0; len < 4; n++)
- if (freqs[n] == 0)
- len = heappush(heap, len, ++freqs[n], n);
+ if (freqs[n] == 0) len = heappush(heap, len, ++freqs[n], n);
/* build code tree */
top = len;
for (n = nsym; len > 2; n++) {
@@ -968,8 +933,7 @@ static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) {
if (n >= nsym) {
/* overwrite parent index with length */
parent[n] = parent[parent[n]] + 1;
- if (parent[n] > limit)
- overflow++;
+ if (parent[n] > limit) overflow++;
} else {
lens[n] = parent[parent[n]] + 1;
if (lens[n] > limit) {
@@ -979,8 +943,7 @@ static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) {
count[lens[n]]++;
}
}
- if (overflow == 0)
- return;
+ if (overflow == 0) return;
/* modify code tree to fix overflow (from zlib) */
while (overflow > 0) {
for (n = limit-1; count[n] == 0; n--);
@@ -1000,7 +963,8 @@ static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) {
}
/* output n (<= 16) bits */
-static void putbits(State *s, uint bits, int n) {
+static void putbits(State *s, uint bits, int n)
+{
s->bits |= bits << s->nbits;
s->nbits += n;
while (s->nbits >= 8) {
@@ -1011,14 +975,14 @@ static void putbits(State *s, uint bits, int n) {
}
/* run length encode literal and dist code lengths into codes and extra */
-static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit, uchar *dlen, int ndist) {
+static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit,
+ uchar *dlen, int ndist)
+{
int i, c, r, rr;
int n = 0;
- for (i = 0; i < nlit; i++)
- codes[i] = llen[i];
- for (i = 0; i < ndist; i++)
- codes[nlit + i] = dlen[i];
+ for (i = 0; i < nlit; i++) codes[i] = llen[i];
+ for (i = 0; i < ndist; i++) codes[nlit + i] = dlen[i];
for (i = 0; i < nlit + ndist;) {
c = codes[i];
for (r = 1; i + r < nlit + ndist && codes[i + r] == c; r++);
@@ -1050,16 +1014,17 @@ static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit, uchar *d
}
/* compress block data into s->dstbuf using given codes */
-static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar *dlen) {
+static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode,
+ uchar *dlen)
+{
int n;
LzCode *lz;
uchar *p;
- 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]);
- else {
+ 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]);
+ } else {
p += lenbase[lz->n] + lz->bits;
putbits(s, lcode[Nlit + lz->n + 1], llen[Nlit + lz->n + 1]);
putbits(s, lz->bits, lenbits[lz->n]);
@@ -1067,11 +1032,13 @@ static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar
putbits(s, dcode[lz->n], dlen[lz->n]);
putbits(s, lz->bits, distbits[lz->n]);
}
+ }
putbits(s, lcode[EOB], llen[EOB]);
}
/* build code trees and select dynamic/fixed/uncompressed block compression */
-static void deflate_block(State *s) {
+static void deflate_block(State *s)
+{
uchar codes[Nlitlen + Ndist], extra[Nlitlen + Ndist];
uchar llen[Nlitlen], dlen[Ndist], clen[Nclen];
ushort cfreq[Nclen];
@@ -1094,8 +1061,7 @@ static void deflate_block(State *s) {
for (ndist = Ndist; ndist > 1 && dlen[ndist-1] == 0; ndist--);
ncodes = clencodes(codes, extra, llen, nlit, dlen, ndist);
memset(cfreq, 0, sizeof(cfreq));
- for (i = 0; i < ncodes; i++)
- cfreq[codes[i]]++;
+ for (i = 0; i < ncodes; i++) cfreq[codes[i]]++;
hufflens(clen, cfreq, Nclen, 7);
huffcodes(ccode, clen, Nclen);
for (nclen = Nclen; nclen > 4 && clen[clenorder[nclen-1]] == 0; nclen--);
@@ -1107,21 +1073,18 @@ static void deflate_block(State *s) {
for (i = 0; i < ncodes; i++) {
c = codes[i];
dynsize += clen[c];
- if (c == 16)
- dynsize += 2;
- if (c == 17)
- dynsize += 3;
- if (c == 18)
- dynsize += 7;
+ if (c == 16) dynsize += 2;
+ if (c == 17) dynsize += 3;
+ if (c == 18) dynsize += 7;
}
/* dyntree = dynsize - 3; */
- for (lz = s->lzbuf, p = s->src + s->startpos; lz != s->lz; lz++)
- if (lz->bits & LzLitFlag)
+ 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];
dynsize += llen[*p];
}
- else {
+ } else {
p += lenbase[lz->n] + lz->bits;
fixsize += fixllen[Nlit + lz->n + 1];
dynsize += llen[Nlit + lz->n + 1];
@@ -1133,6 +1096,7 @@ static void deflate_block(State *s) {
fixsize += distbits[lz->n];
dynsize += distbits[lz->n];
}
+ }
fixsize += fixllen[EOB];
dynsize += llen[EOB];
@@ -1144,17 +1108,13 @@ static void deflate_block(State *s) {
putbits(s, nlit - 257, 5);
putbits(s, ndist - 1, 5);
putbits(s, nclen - 4, 4);
- for (i = 0; i < nclen; i++)
- putbits(s, clen[clenorder[i]], 3);
+ for (i = 0; i < nclen; i++) putbits(s, clen[clenorder[i]], 3);
for (i = 0; i < ncodes; i++) {
c = codes[i];
putbits(s, ccode[c], clen[c]);
- if (c == 16)
- putbits(s, extra[i], 2);
- if (c == 17)
- putbits(s, extra[i], 3);
- if (c == 18)
- putbits(s, extra[i], 7);
+ if (c == 16) putbits(s, extra[i], 2);
+ if (c == 17) putbits(s, extra[i], 3);
+ if (c == 18) putbits(s, extra[i], 7);
}
putblock(s, lcode, llen, dcode, dlen);
} else if (fixsize < uncsize) {
@@ -1179,23 +1139,23 @@ fprintf(stderr, "blen:%d [%d,%d] lzlen:%d dynlen:%d (tree:%d rate:%.3f) fixlen:%
}
/* find n in base */
-static int bisect(ushort *base, int len, int n) {
+static int bisect(ushort *base, int len, int n)
+{
int lo = 0;
int hi = len;
int k;
while (lo < hi) {
k = (lo + hi) / 2;
- if (n < base[k])
- hi = k;
- else
- lo = k + 1;
+ if (n < base[k]) hi = k;
+ else lo = k + 1;
}
return lo - 1;
}
/* add literal run length to lzbuf */
-static void flushlit(State *s) {
+static void flushlit(State *s)
+{
if (s->nlit) {
s->lz->bits = LzLitFlag;
s->lz->n = s->nlit;
@@ -1205,7 +1165,8 @@ static void flushlit(State *s) {
}
/* add match to lzbuf and update freq counts */
-static void recordmatch(State *s, Match m) {
+static void recordmatch(State *s, Match m)
+{
int n;
/*fprintf(stderr, "m %d %d\n", m.len, m.dist);*/
@@ -1223,37 +1184,41 @@ static void recordmatch(State *s, Match m) {
}
/* update literal run length */
-static void recordlit(State *s, int c) {
+static void recordlit(State *s, int c)
+{
/*fprintf(stderr, "l %c\n", c);*/
s->nlit++;
s->lfreq[c]++;
}
/* multiplicative hash (using a prime close to golden ratio * 2^32) */
-static int gethash(uchar *p) {
- return (0x9e3779b1 * ((p[0]<<16) + (p[1]<<8) + p[2]) >> (32 - HashBits)) % HashSize;
+static int gethash(uchar *p)
+{
+ return (0x9e3779b1 * ((p[0]<<16) + (p[1]<<8) + p[2]) >> (32 - HashBits))
+ % HashSize;
}
/* update hash chain at the current position */
-static int updatechain(State *s) {
+static int updatechain(State *s)
+{
int hash, next = 0, p = s->pos, i;
- if (s->endpos - p < MinMatch)
- p = s->endpos - MinMatch;
+ if (s->endpos - p < MinMatch) p = s->endpos - MinMatch;
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)
- next = 0;
+ if (next >= i || i - next >= MaxDist) next = 0;
s->chain[i % WinSize] = next;
}
s->skip = 0;
+
return next;
}
/* find longest match, next position in the hash chain is given */
-static Match getmatch(State *s, int next) {
+static Match getmatch(State *s, int next)
+{
Match m = {0, MinMatch-1};
int len;
int limit = s->pos - MaxDist;
@@ -1279,16 +1244,16 @@ static Match getmatch(State *s, int next) {
m.len = s->endpos - s->pos;
return m;
}
- if (len == MaxMatch)
- return m;
+ if (len == MaxMatch) return m;
}
} while ((next = s->chain[next % WinSize]) > limit && --chainlen);
- if (m.len < MinMatch || (m.len == MinMatch && m.dist > BigDist))
- m.len = 0;
+ if (m.len < MinMatch || (m.len == MinMatch && m.dist > BigDist)) m.len = 0;
+
return m;
}
-static void startblock(State *s) {
+static void startblock(State *s)
+{
s->startpos = s->pos;
s->dst = s->dstbegin = s->dstbuf;
s->lz = s->lzbuf;
@@ -1298,11 +1263,11 @@ static void startblock(State *s) {
s->lfreq[EOB]++;
}
-static int shiftwin(State *s) {
+static int shiftwin(State *s)
+{
int n;
- if (s->startpos < WinSize)
- return 0;
+ if (s->startpos < WinSize) return 0;
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;
@@ -1311,37 +1276,40 @@ static int shiftwin(State *s) {
s->pos -= WinSize;
s->startpos -= WinSize;
s->endpos -= WinSize;
+
return 1;
}
-static int endblock(State *s) {
- if ((s->pos >= 2*WinSize && !shiftwin(s)) || s->pos - s->startpos >= BlockSize ||
- s->lz - s->lzbuf >= LzGuard || (s->eof && s->pos == s->endpos)) {
+static int endblock(State *s)
+{
+ if ((s->pos >= 2*WinSize && !shiftwin(s))
+ || s->pos - s->startpos >= BlockSize || s->lz - s->lzbuf >= LzGuard
+ || (s->eof && s->pos == s->endpos))
+ {
/* deflate block */
flushlit(s);
- if (s->prevm.len)
- s->pos--;
+ if (s->prevm.len) s->pos--;
deflate_block(s);
- if (s->eof && s->pos == s->endpos)
- putbits(s, 0, 7);
+ if (s->eof && s->pos == s->endpos) putbits(s, 0, 7);
+
return 1;
}
+
return 0;
}
-static int fillsrc(State *s) {
+static int fillsrc(State *s)
+{
int n, k;
if (s->endpos < SrcSize && !s->eof) {
n = SrcSize - s->endpos;
k = s->inend - s->in;
- if (n > k)
- n = k;
+ if (n > k) n = k;
memcpy(s->src + s->endpos, s->in, n);
s->in += n;
s->endpos += n;
- if (s->endpos < SrcSize)
- return 0;
+ if (s->endpos < SrcSize) return 0;
}
return 1;
}
@@ -1354,74 +1322,61 @@ static int calcguard(State *s) {
}
/* deflate compress from s->src into s->dstbuf */
-static int deflate_state(State *s) {
+static int deflate_state(State *s)
+{
Match m;
int next;
int guard;
- if (s->state == FlateIn)
- s->eof = s->in == s->inend;
+ if (s->state == FlateIn) s->eof = s->in == s->inend;
else if (s->state == FlateOut) {
- if (s->dstbegin < s->dst)
- return (s->state = FlateOut);
- if (s->eof && s->pos == s->endpos)
- return (s->state = FlateOk);
+ if (s->dstbegin < s->dst) return (s->state = FlateOut);
+ if (s->eof && s->pos == s->endpos) return (s->state = FlateOk);
startblock(s);
- if (s->prevm.len)
- s->pos++;
- } else
- return s->state;
+ if (s->prevm.len) s->pos++;
+ } else return s->state;
guard = calcguard(s);
for (;;) {
if (s->pos >= guard || s->lz - s->lzbuf >= LzGuard) {
/*fprintf(stderr,"guard:%d pos:%d len:%d lzlen:%d end:%d start:%d nin:%d eof:%d\n", guard, s->pos, s->pos - s->startpos, s->lz - s->lzbuf, s->endpos, s->startpos, s->inend - s->in, s->eof);*/
- if (endblock(s))
- return (s->state = FlateOut);
- if (!fillsrc(s))
- return (s->state = FlateIn);
+ if (endblock(s)) return (s->state = FlateOut);
+ if (!fillsrc(s)) return (s->state = FlateIn);
guard = calcguard(s);
}
next = updatechain(s);
- if (next)
- m = getmatch(s, next);
+ if (next) m = getmatch(s, next);
if (next && m.len > s->prevm.len) {
- if (s->prevm.len)
- recordlit(s, s->src[s->pos-1]);
+ if (s->prevm.len) recordlit(s, s->src[s->pos-1]);
s->prevm = m;
} else if (s->prevm.len) {
recordmatch(s, s->prevm);
s->skip = s->prevm.len - 2;
s->prevm.len = 0;
s->pos += s->skip;
- } else
- recordlit(s, s->src[s->pos]);
+ } else recordlit(s, s->src[s->pos]);
s->pos++;
}
}
/* alloc and init state */
-static State *alloc_state(void) {
+static State *alloc_state(void)
+{
State *s = malloc(sizeof(State));
int i;
- if (!s)
- return s;
+ if (!s) return s;
+
memset(s->chain, 0, sizeof(s->chain));
memset(s->head, 0, sizeof(s->head));
s->bits = s->nbits = 0;
/* TODO: globals */
if (fixllen[0] == 0) {
- for (i = 0; i < 144; i++)
- fixllen[i] = 8;
- for (; i < 256; i++)
- fixllen[i] = 9;
- for (; i < 280; i++)
- fixllen[i] = 7;
- for (; i < Nlitlen; i++)
- fixllen[i] = 8;
- for (i = 0; i < Ndist; i++)
- fixdlen[i] = 5;
+ for (i = 0; i < 144; i++) fixllen[i] = 8;
+ for (; i < 256; i++) fixllen[i] = 9;
+ for (; i < 280; i++) fixllen[i] = 7;
+ for (; i < Nlitlen; i++) fixllen[i] = 8;
+ for (i = 0; i < Ndist; i++) fixdlen[i] = 5;
huffcodes(fixlcode, fixllen, Nlitlen);
huffcodes(fixdcode, fixdlen, Ndist);
}
@@ -1438,7 +1393,8 @@ static State *alloc_state(void) {
/* extern */
-int deflate(FlateStream *stream) {
+int deflate(FlateStream *stream)
+{
State *s = stream->state;
int n, k;
@@ -1449,48 +1405,54 @@ int deflate(FlateStream *stream) {
}
if (!s) {
s = stream->state = alloc_state();
- if (!s)
- return stream->err = "no mem.", FlateErr;
+ if (!s) return stream->err = "no mem.", FlateErr;
}
+
if (stream->nin) {
s->in = stream->in;
s->inend = s->in + stream->nin;
stream->nin = 0;
}
n = deflate_state(s);
+
if (n == FlateOut) {
k = s->dst - s->dstbegin;
- if (k < stream->nout)
- stream->nout = k;
+ if (k < stream->nout) stream->nout = k;
memcpy(stream->out, s->dstbegin, stream->nout);
s->dstbegin += stream->nout;
}
+
if (n == FlateOk || n == FlateErr) {
free(s);
stream->state = 0;
}
+
return n;
}
-static void set32(uchar *p, uint n) {
+static void set32(uchar *p, uint n)
+{
p[0] = n >> 24;
p[1] = n >> 16;
p[2] = n >> 8;
p[3] = n;
}
-static void set32le(uchar *p, uint n) {
+static void set32le(uchar *p, uint n)
+{
p[0] = n;
p[1] = n >> 8;
p[2] = n >> 16;
p[3] = n >> 24;
}
-static int check32(uchar *p, uint n) {
+static int check32(uchar *p, uint n)
+{
return n == ((p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3]);
}
-static int check32le(uchar *p, uint n) {
+static int check32le(uchar *p, uint n)
+{
return n == (p[0] | (p[1] << 8) | (p[2] << 16) | (p[3] << 24));
}
@@ -1502,34 +1464,35 @@ enum {
ZlibFCHK = 31 - (((ZlibCM | ZlibCINFO) << 8) | ZlibFLEV) % 31
};
-int deflate_zlib_header(uchar *p, int n) {
- if (n < 2)
- return FlateErr;
+int deflate_zlib_header(uchar *p, int n)
+{
+ if (n < 2) return FlateErr;
p[0] = ZlibCM | ZlibCINFO; /* deflate method, 32K window size */
p[1] = ZlibFLEV | ZlibFCHK; /* highest compression */
+
return 2;
}
-int deflate_zlib_footer(uchar *p, int n, uint sum, uint len, uint zlen) {
- if (n < 4)
- return FlateErr;
+int deflate_zlib_footer(uchar *p, int n, uint sum, uint len, uint zlen)
+{
+ if (n < 4) return FlateErr;
set32(p, sum);
+
return 4;
}
-int inflate_zlib_header(uchar *p, int n) {
- if (n < 2)
- return FlateErr;
- if (((p[0] << 8) | p[1]) % 31)
- return FlateErr;
- if ((p[0] & 0xf0) != ZlibCM || (p[0] & 0x0f) > ZlibCINFO)
- return FlateErr;
- if (p[1] & ZlibFDICT)
- return FlateErr;
+int inflate_zlib_header(uchar *p, int n)
+{
+ if (n < 2) return FlateErr;
+ if (((p[0] << 8) | p[1]) % 31) return FlateErr;
+ if ((p[0] & 0xf0) != ZlibCM || (p[0] & 0x0f) > ZlibCINFO) return FlateErr;
+ if (p[1] & ZlibFDICT) return FlateErr;
+
return 2;
}
-int inflate_zlib_footer(uchar *p, int n, uint sum, uint len, uint zlen) {
+int inflate_zlib_footer(uchar *p, int n, uint sum, uint len, uint zlen)
+{
if (n < 4 || !check32(p, sum))
return FlateErr;
return 4;
@@ -1548,7 +1511,8 @@ enum {
GZipOS = 255
};
-int deflate_gzip_header(uchar *p, int n) {
+int deflate_gzip_header(uchar *p, int n)
+{
if (n < 10)
return FlateErr;
memset(p, 0, 10);
@@ -1560,7 +1524,8 @@ int deflate_gzip_header(uchar *p, int n) {
return 10;
}
-int deflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) {
+int deflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen)
+{
if (n < 8)
return FlateErr;
set32le(p, sum);
@@ -1568,45 +1533,38 @@ int deflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) {
return 8;
}
-int inflate_gzip_header(uchar *p, int n) {
+int inflate_gzip_header(uchar *p, int n)
+{
int k = 10;
- if (k > n)
- return FlateErr;
- if (p[0] != GZipID1 || p[1] != GZipID2 || p[2] != GZipCM)
- return FlateErr;
+ if (k > n) return FlateErr;
+ if (p[0] != GZipID1 || p[1] != GZipID2 || p[2] != GZipCM) return FlateErr;
if (p[3] & GZipFEXTRA) {
k += 2 + ((p[k] << 8) | p[k+1]);
- if (k > n)
- return FlateErr;
+ if (k > n) return FlateErr;
}
if (p[3] & GZipFNAME) {
- for (; k < n; k++)
- if (p[k] == 0)
- break;
+ for (; k < n; k++) if (p[k] == 0) break;
k++;
- if (k > n)
- return FlateErr;
+ if (k > n) return FlateErr;
}
if (p[3] & GZipFCOMM) {
- for (; k < n; k++)
- if (p[k] == 0)
- break;
+ for (; k < n; k++) if (p[k] == 0) break;
k++;
- if (k > n)
- return FlateErr;
+ if (k > n) return FlateErr;
}
if (p[3] & GZipFHCRC) {
k += 2;
- if (k > n)
- return FlateErr;
+ if (k > n) return FlateErr;
}
+
return k;
}
-int inflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) {
- if (n < 8 || !check32le(p, sum) || !check32le(p+4, len))
- return FlateErr;
+int inflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen)
+{
+ if (n < 8 || !check32le(p, sum) || !check32le(p+4, len)) return FlateErr;
+
return 8;
}
@@ -1627,9 +1585,9 @@ enum {
PKNameLen = sizeof(pkname) - 1
};
-int deflate_pkzip_header(uchar *p, int n) {
- if (n < PKHeadSize + PKNameLen)
- return FlateErr;
+int deflate_pkzip_header(uchar *p, int n)
+{
+ if (n < PKHeadSize + PKNameLen) return FlateErr;
memset(p, 0, PKHeadSize);
set32le(p, PKHeadID);
set32le(p+4, PKVersion);
@@ -1641,13 +1599,12 @@ int deflate_pkzip_header(uchar *p, int n) {
return PKHeadSize + PKNameLen;
}
-int deflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) {
- if (n < PKDirSize + PKNameLen + 22)
- return FlateErr;
+int deflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen)
+{
+ if (n < PKDirSize + PKNameLen + 22) return FlateErr;
/* unzip bug */
/*
- if (n < 16 + PKDirSize + PKNameLen + 22)
- return FlateErr;
+ if (n < 16 + PKDirSize + PKNameLen + 22) return FlateErr;
set32le(p, PKDataID);
set32le(p+4, sum);
set32le(p+8, zlen);
@@ -1679,43 +1636,36 @@ int deflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) {
*/
}
-int inflate_pkzip_header(uchar *p, int n) {
+int inflate_pkzip_header(uchar *p, int n)
+{
int k = 30;
- if (k > n)
- return FlateErr;
- if (!check32le(p, PKHeadID))
- return FlateErr;
- if ((p[4] | (p[5] << 8)) > PKVersion)
- return FlateErr;
- if ((p[8] | (p[9] << 8)) != PKMethod)
- return FlateErr;
+ if (k > n) return FlateErr;
+ if (!check32le(p, PKHeadID)) return FlateErr;
+ if ((p[4] | (p[5] << 8)) > PKVersion) return FlateErr;
+ if ((p[8] | (p[9] << 8)) != PKMethod) return FlateErr;
k += p[26] | (p[27] << 8);
k += p[28] | (p[29] << 8);
- if (k > n)
- return FlateErr;
+ if (k > n) return FlateErr;
+
return k;
}
-int inflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) {
+int inflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen)
+{
int k = PKDirSize + 22;
- if (k > n)
- return FlateErr;
+ if (k > n) return FlateErr;
if (check32le(p, PKDataID)) {
p += 16;
k += 16;
- if (k > n)
- return FlateErr;
+ if (k > n) return FlateErr;
}
- if (!check32le(p, PKDirID))
- return FlateErr;
- if (!check32le(p+16, sum))
- return FlateErr;
- if (!check32le(p+20, zlen))
- return FlateErr;
- if (!check32le(p+24, len))
- return FlateErr;
+ if (!check32le(p, PKDirID)) return FlateErr;
+ if (!check32le(p+16, sum)) return FlateErr;
+ if (!check32le(p+20, zlen)) return FlateErr;
+ if (!check32le(p+24, len)) return FlateErr;
+
return k;
}
@@ -1744,7 +1694,8 @@ static uint dummysum(uchar *p, int n, uint sum) {
}
/* compress, using FlateStream interface */
-int compress_stream(FILE *in, FILE *out) {
+int compress_stream(FILE *in, FILE *out)
+{
FlateStream s;
int k, n;
enum {Nin = 1<<15, Nout = 1<<15};
@@ -1799,7 +1750,8 @@ int compress_stream(FILE *in, FILE *out) {
}
/* decompress, using FlateStream interface */
-int decompress_stream(FILE *in, FILE *out) {
+int decompress_stream(FILE *in, FILE *out)
+{
FlateStream s;
uchar *begin;
int k, n;
@@ -1859,7 +1811,8 @@ int decompress_stream(FILE *in, FILE *out) {
}
}
-static int old_main(int argc, char *argv[]) {
+static int old_main(int argc, char *argv[])
+{
char comp = 'c';
char fmt = 'r';
char verbose = 'q';
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-01 12:58:32 +0000