aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorRob Landley <rob@landley.net>2014-04-02 06:37:14 -0500
committerRob Landley <rob@landley.net>2014-04-02 06:37:14 -0500
commit7183a637432c9f0957e4e0e68b71e61a67fa89d6 (patch)
treeaf91bd482011c3233a530fc084c38c774607efb9
parent18720dc21a8de3e5cff780f6b89111fe1d9b17a1 (diff)
downloadtoybox-7183a637432c9f0957e4e0e68b71e61a67fa89d6.tar.gz
Decided not to go with the sflate implementation of deflate/inflate. The decompression side's already reimplemented in compress, and I'm working on compression side.
-rw-r--r--toys/pending/gzip.c1878
1 files changed, 0 insertions, 1878 deletions
diff --git a/toys/pending/gzip.c b/toys/pending/gzip.c
deleted file mode 100644
index 87fc2fda..00000000
--- a/toys/pending/gzip.c
+++ /dev/null
@@ -1,1878 +0,0 @@
-/* gzip.c - deflate and inflate code rolled into a ball.
- *
- * Copyright 2009 Szabolcs Nagy <nszabolcs@gmail.com>
- *
- * See http://refspecs.linuxfoundation.org/LSB_4.1.0/LSB-Core-generic/LSB-Core-generic/gzip.html
- * And RFCs 1950, 1951, and 1952
-
-USE_GZIP(NEWTOY(gzip, "qvcdrgzp[-qv][-cd][!rgpz]", TOYFLAG_USR|TOYFLAG_BIN))
-
-config GZIP
- bool "gzip"
- default n
- help
- usage: gzip [-cdgpqrvz] [FILE]
-
- Transitional gzip, needs work. Combines gzip, zlib, and pkzip.
-
- -c compress (default)
- -d decompress
- -g gzip
- -p pkzip
- -q quiet (default)
- -r raw (default)
- -v verbose
- -z zlib
-*/
-
-#define FOR_gzip
-#include "toys.h"
-
-GLOBALS(
- // base offset and extra bits tables (length and distance)
- char lenbits[29], distbits[30];
- unsigned short lenbase[29], distbase[30];
-)
-
-typedef unsigned char uchar;
-typedef unsigned short ushort;
-typedef unsigned int uint;
-
-/* deflate and inflate return values */
-enum {
- FlateOk = 0,
- FlateErr = -1,
- FlateIn = -2,
- FlateOut = -3
-};
-
-enum {
- CodeBits = 16, /* max number of bits in a code + 1 */
- LitlenTableBits = 9, /* litlen code bits used in lookup table */
- DistTableBits = 6, /* dist code bits used in lookup table */
- ClenTableBits = 6, /* clen code bits used in lookup table */
- TableBits = LitlenTableBits, /* log2(lookup table size) */
- Nlit = 256, /* number of lit codes */
- Nlen = 29, /* number of len codes */ // sizeof(lenbits)
- Nlitlen = Nlit+Nlen+3, /* litlen codes + block end + 2 unused */
- Ndist = 30, /* number of distance codes */ // sizeof(distbits)
- Nclen = 19, /* number of code length codes */
-
- EOB = 256, /* end of block symbol */
- MinMatch = 3, /* min match length */
- MaxMatch = 258, /* max match length */
- WinSize = 1 << 15, /* sliding window size */
-
- MaxChainLen = 256, /* max length of hash chain */
- HashBits = 13,
- HashSize = 1 << HashBits, /* hash table size */
- BigDist = 1 << 12, /* max match distance for short match length */
- MaxDist = WinSize,
- BlockSize = 1 << 15, /* TODO */
- SrcSize = 2*WinSize + MaxMatch,
- DstSize = BlockSize + MaxMatch + 6, /* worst case compressed block size */
- LzSize = 1 << 13, /* lz buffer size */
- LzGuard = LzSize - 2,
- LzLitFlag = 1 << 15 /* marks literal run length in lz buffer */
-};
-
-/* states */
-enum {
- BlockHead,
- UncompressedBlock,
- CopyUncompressed,
- FixedHuff,
- DynamicHuff,
- DynamicHuffClen,
- DynamicHuffLitlenDist,
- DynamicHuffContinue,
- DecodeBlock,
- DecodeBlockLenBits,
- DecodeBlockDist,
- DecodeBlockDistBits,
- DecodeBlockCopy
-};
-
-typedef struct {
- int nin;
- int nout;
- uchar *in;
- uchar *out;
- char *err;
- void *state;
-} FlateStream;
-
-typedef struct {
- short len; /* code length */
- ushort sym; /* symbol */
-} Entry;
-
-/* huffman code tree */
-typedef struct {
- Entry table[1 << TableBits]; /* prefix lookup table */
- uint nbits; /* prefix length (table size is 1 << nbits) */
- uint sum; /* full codes in table: sum(count[0..nbits]) */
- ushort count[CodeBits]; /* number of codes with given length */
- ushort symbol[Nlitlen]; /* symbols ordered by code length (lexic.) */
-} Huff;
-
-typedef struct {
- uchar *src; /* input buffer pointer */
- uchar *srcend;
-
- uint bits;
- uint nbits;
-
- uchar win[WinSize]; /* output window */
- uint pos; /* window pos */
- uint posout; /* used for flushing win */
-
- int state; /* decode state */
- int final; /* last block flag */
- char *err; /* TODO: error message */
-
- /* for decoding dynamic code trees in inflate() */
- int nlit;
- int ndist;
- int nclen; /* also used in decode_block() */
- int lenpos; /* also used in decode_block() */
- uchar lens[Nlitlen + Ndist];
-
- int fixed; /* fixed code tree flag */
- Huff lhuff; /* dynamic lit/len huffman code tree */
- Huff dhuff; /* dynamic distance huffman code tree */
-} DecodeState;
-
-int deflate(FlateStream *s);
-int inflate(FlateStream *s);
-
-uint adler32(uchar *p, int n, uint adler);
-void crc32init(void);
-uint crc32(uchar *p, int n, uint crc);
-
-uint crctab[256];
-
-void crc32init(void)
-{
- static const uint poly = 0xedb88320;
- int i,j;
-
- for (i = 0; i < 256; ++i) {
- uint crc = i;
-
- for (j = 0; j < 8; j++) {
- if (crc & 1) crc = (crc >> 1) ^ poly;
- else crc >>= 1;
- }
- crctab[i] = 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);
-
- return crc ^ 0xffffffff;
-}
-
-enum {
- AdlerBase = 65521, /* largest 16bit prime */
- AdlerN = 5552 /* max iters before 32bit overflow */
-};
-
-uint adler32(uchar *p, int n, uint adler)
-{
- uint s1 = adler & 0xffff;
- uint s2 = (adler >> 16) & 0xffff;
- uchar *ep;
- int k;
-
- for (; n >= 16; n -= k) {
- k = n < AdlerN ? n : AdlerN;
- k &= ~0xf;
- for (ep = p + k; p < ep; p += 16) {
- s1 += p[0];
- s2 += s1;
- s1 += p[1];
- s2 += s1;
- s1 += p[2];
- s2 += s1;
- s1 += p[3];
- s2 += s1;
- s1 += p[4];
- s2 += s1;
- s1 += p[5];
- s2 += s1;
- s1 += p[6];
- s2 += s1;
- s1 += p[7];
- s2 += s1;
- s1 += p[8];
- s2 += s1;
- s1 += p[9];
- s2 += s1;
- s1 += p[10];
- s2 += s1;
- s1 += p[11];
- s2 += s1;
- s1 += p[12];
- s2 += s1;
- s1 += p[13];
- s2 += s1;
- s1 += p[14];
- s2 += s1;
- s1 += p[15];
- s2 += s1;
- }
- s1 %= AdlerBase;
- s2 %= AdlerBase;
- }
- if (n) {
- for (ep = p + n; p < ep; p++) {
- s1 += p[0];
- s2 += s1;
- }
- s1 %= AdlerBase;
- s2 %= AdlerBase;
- }
- return (s2 << 16) + s1;
-}
-
-/* TODO: globals.. initialization is not thread safe */
-static Huff lhuff; /* fixed lit/len huffman code tree */
-static Huff dhuff; /* fixed distance huffman code tree */
-
-/* ordering of code lengths */
-static uchar clenorder[Nclen] = {
- 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
-};
-
-/* TODO: this or normal inc + reverse() */
-/* increment bitwise reversed n (msb is bit 0, lsb is bit len-1) */
-static uint revinc(uint n, uint len) {
- uint i = 1 << (len - 1);
-
- while (n & i) i >>= 1;
- if (i) {
- n &= i - 1;
- n |= i;
- } 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)
-{
- int offs[CodeBits];
- int left;
- uint i, c, sum, code, len, min, max;
- ushort *count = huff->count;
- ushort *symbol = huff->symbol;
- Entry *table = huff->table;
- Entry entry;
-
- /* count code lengths */
- 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;
- }
- 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;
- if (nbits < min) {
- nbits = min;
- if (nbits > TableBits) return -1;
- }
- huff->nbits = nbits;
-
- /* check if length is over-subscribed or incomplete */
- 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;
- }
-
- for (sum = 0, i = 0; i <= max; i++) {
- offs[i] = sum;
- sum += count[i];
- }
- /* needed for decoding codes longer than nbits */
- 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;
-
- /* lookup table for decoding nbits from input.. */
- 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;
- /* next code */
- symbol++;
- code = revinc(code, len);
- }
- /* ..if code is longer than nbits: values for simple bitwise decode */
- for (i = 0; code; i++) {
- table[code].len = -1;
- 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)
-{
- 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;
- build_huff(&lhuff, lens, Nlitlen, 8);
-
- 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)
-{
- while (*nbits < n) {
- 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)
-{
- uint k;
-
- k = *bits & ((1 << n) - 1);
- *bits >>= n;
- *nbits -= n;
-
- return k;
-}
-
-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)
-{
- 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)
-{
- int sum = huff->sum;
- uint huffbits = huff->nbits;
- ushort *count = huff->count + huffbits + 1;
-
- /* get bits if we are near the end */
- if (s->src + 2 >= s->srcend) {
- while (nbits < CodeBits - 1 && s->src < s->srcend) {
- bits |= *s->src++ << nbits;
- nbits += 8;
- }
- s->bits = bits;
- s->nbits = nbits;
- }
- bits >>= huffbits;
- nbits -= huffbits;
- for (;;) {
- if (!nbits--) {
- if (s->src == s->srcend) return FlateIn;
- bits = *s->src++;
- nbits = 7;
- }
- cur |= bits & 1;
- bits >>= 1;
- sum += *count;
- cur -= *count;
- if (cur < 0) break;
- cur <<= 1;
- count++;
- if (count == huff->count + CodeBits)
- return s->err = "symbol decoding failed.", FlateErr;
- }
- 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)
-{
- uint huffbits = huff->nbits;
- uint nbits = s->nbits;
- uint bits = s->bits;
- uint mask = (1 << huffbits) - 1;
- Entry entry;
-
- /* get enough bits efficiently */
- if (nbits < huffbits) {
- uchar *src = s->src;
-
- if (src + 2 < s->srcend) {
- /* we assume huffbits <= 9 */
- bits |= *src++ << nbits;
- nbits += 8;
- bits |= *src++ << nbits;
- nbits += 8;
- bits |= *src++ << nbits;
- nbits += 8;
- s->src = src;
- } else /* rare */
- do {
- if (s->src == s->srcend) {
- entry = huff->table[bits & mask];
- if (entry.len > 0 && entry.len <= nbits) {
- s->bits = bits >> entry.len;
- s->nbits = nbits - entry.len;
- return entry.sym;
- }
- s->bits = bits;
- s->nbits = nbits;
- return FlateIn;
- }
- bits |= *s->src++ << nbits;
- nbits += 8;
- } while (nbits < huffbits);
- }
- /* decode bits */
- entry = huff->table[bits & mask];
- if (entry.len > 0) {
- s->bits = bits >> entry.len;
- s->nbits = nbits - entry.len;
- return entry.sym;
- } else if (entry.len == 0)
- return s->err = "symbol decoding failed.", FlateErr;
- return decode_symbol_long(s, huff, bits, nbits, entry.sym);
-}
-
-/* decode a block of data from stream with trees */
-static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff)
-{
- uchar *win = s->win;
- uint pos = s->pos;
- uint sym = s->nclen;
- uint len = s->lenpos;
- uint dist = s->nclen;
-
- switch (s->state) {
- case DecodeBlock:
- for (;;) {
- sym = decode_symbol(s, lhuff);
- if (sym < 256) {
- win[pos++] = sym;
- if (pos == WinSize) {
- s->pos = WinSize;
- s->state = DecodeBlock;
- return FlateOut;
- }
- } else if (sym > 256) {
- sym -= 257;
- if (sym >= Nlen) {
- s->pos = pos;
- s->state = DecodeBlock;
- if (sym + 257 == (uint)FlateIn) return FlateIn;
- return FlateErr;
- }
- case DecodeBlockLenBits:
- if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, TT.lenbits[sym]))
- {
- s->nclen = sym; /* using nclen to store sym */
- s->pos = pos;
- s->state = DecodeBlockLenBits;
- return FlateIn;
- }
- len = TT.lenbase[sym] + getbits_fast(&s->bits, &s->nbits, TT.lenbits[sym]);
- case DecodeBlockDist:
- sym = decode_symbol(s, dhuff);
- if (sym == (uint)FlateIn) {
- s->pos = pos;
- s->lenpos = len;
- s->state = DecodeBlockDist;
- return FlateIn;
- }
- if (sym >= Ndist) return FlateErr;
- case DecodeBlockDistBits:
- if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, TT.distbits[sym])) {
- s->nclen = sym; /* using nclen to store sym */
- s->pos = pos;
- s->lenpos = len;
- s->state = DecodeBlockDistBits;
- return FlateIn;
- }
- dist = TT.distbase[sym] + getbits_fast(&s->bits, &s->nbits, TT.distbits[sym]);
- /* copy match, loop unroll in common case */
- if (pos + len < WinSize) {
- /* TT.lenbase[sym] >= 3 */
- do {
- win[pos] = win[(pos - dist) % WinSize];
- pos++;
- win[pos] = win[(pos - dist) % WinSize];
- pos++;
- win[pos] = win[(pos - dist) % WinSize];
- pos++;
- len -= 3;
- } while (len >= 3);
- if (len--) {
- win[pos] = win[(pos - dist) % WinSize];
- pos++;
- if (len) {
- win[pos] = win[(pos - dist) % WinSize];
- pos++;
- }
- }
- } else { /* rare */
- case DecodeBlockCopy:
- while (len--) {
- win[pos] = win[(pos - dist) % WinSize];
- pos++;
- if (pos == WinSize) {
- s->pos = WinSize;
- s->lenpos = len;
- s->nclen = dist; /* using nclen to store dist */
- s->state = DecodeBlockCopy;
- return FlateOut;
- }
- }
- }
- } else { /* EOB: sym == 256 */
- s->pos = pos;
- return FlateOk;
- }
- } /* for (;;) */
- } /* switch () */
- return s->err = "corrupted state.", FlateErr;
-}
-
-/* inflate state machine (decodes s->src into s->win) */
-static int inflate_state(DecodeState *s)
-{
- int n;
-
- if (s->posout) return FlateOut;
- for (;;) {
- switch (s->state) {
- case BlockHead:
- if (s->final) {
- if (s->pos) return FlateOut;
- else return FlateOk;
- }
- 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;
- break;
- case UncompressedBlock:
- /* start block on a byte boundary */
- s->bits >>= s->nbits & 7;
- s->nbits &= ~7;
- if (!fillbits(s, 32)) return FlateIn;
- s->lenpos = getbits(s, 16);
- n = getbits(s, 16);
- if (s->lenpos != (~n & 0xffff))
- return s->err = "corrupt uncompressed length.", FlateErr;
- s->state = CopyUncompressed;
- case CopyUncompressed:
- /* TODO: untested, slow, memcpy etc */
- /* s->nbits should be 0 here */
- while (s->lenpos) {
- if (s->src == s->srcend) return FlateIn;
- s->lenpos--;
- s->win[s->pos++] = *s->src++;
- if (s->pos == WinSize) return FlateOut;
- }
- s->state = BlockHead;
- break;
- case FixedHuff:
- s->fixed = 1;
- s->state = DecodeBlock;
- break;
- case DynamicHuff:
- /* decode dynamic huffman code trees */
- 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;
- 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 {
- s->lenpos = n;
- return FlateIn;
- }
- /* using lhuff for code length huff code */
- if (build_huff(&s->lhuff, s->lens, Nclen, ClenTableBits) < 0)
- return s->err = "building clen tree failed.", FlateErr;
- s->state = DynamicHuffLitlenDist;
- s->lenpos = 0;
- case DynamicHuffLitlenDist:
- /* decode code lengths for the dynamic trees */
- for (n = s->lenpos; n < s->nlit + s->ndist; ) {
- uint sym = decode_symbol(s, &s->lhuff);
- uint len;
- uchar c;
-
- if (sym < 16) {
- s->lens[n++] = sym;
- continue;
- } else if (sym == (uint)FlateIn) {
- s->lenpos = n;
- return FlateIn;
- case DynamicHuffContinue:
- n = s->lenpos;
- sym = s->nclen;
- s->state = DynamicHuffLitlenDist;
- }
- if (!fillbits(s, 7)) {
- /* TODO: 7 is too much when an almost empty block is at the end */
- if (sym == (uint)FlateErr)
- return FlateErr;
- s->nclen = sym;
- s->lenpos = n;
- s->state = DynamicHuffContinue;
- return FlateIn;
- }
- /* TODO: bound check s->lens */
- if (sym == 16) {
- /* copy previous code length 3-6 times */
- c = s->lens[n - 1];
- for (len = 3 + getbits(s, 2); len; len--)
- 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;
- } 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;
- }
- /* build dynamic huffman code trees */
- if (build_huff(&s->lhuff, s->lens, s->nlit, LitlenTableBits) < 0)
- return s->err = "building litlen tree failed.", FlateErr;
- if (build_huff(&s->dhuff, s->lens + s->nlit, s->ndist, DistTableBits) < 0)
- return s->err = "building dist tree failed.", FlateErr;
- s->state = DecodeBlock;
- case DecodeBlock:
- case DecodeBlockLenBits:
- case DecodeBlockDist:
- case DecodeBlockDistBits:
- case DecodeBlockCopy:
- n = decode_block(s, s->fixed ? &lhuff : &s->lhuff, s->fixed ? &dhuff : &s->dhuff);
- if (n != FlateOk)
- return n;
- s->state = BlockHead;
- break;
- default:
- return s->err = "corrupt internal state.", FlateErr;
- }
- }
-}
-
-static DecodeState *alloc_decode_state(void)
-{
- DecodeState *s = malloc(sizeof(DecodeState));
-
- if (s) {
- s->final = s->pos = s->posout = s->bits = s->nbits = 0;
- s->state = BlockHead;
- s->src = s->srcend = 0;
- s->err = 0;
- /* TODO: globals.. */
- if (lhuff.nbits == 0) init_fixed_huffs();
- }
- return s;
-}
-
-
-/* extern */
-
-int inflate(FlateStream *stream)
-{
- DecodeState *s = stream->state;
- int n;
-
- if (stream->err) {
- if (s) {
- free(s);
- stream->state = 0;
- }
- return FlateErr;
- }
- if (!s) {
- s = stream->state = alloc_decode_state();
- if (!s) return stream->err = "no mem.", FlateErr;
- }
- if (stream->nin) {
- s->src = stream->in;
- s->srcend = s->src + stream->nin;
- stream->nin = 0;
- }
- n = inflate_state(s);
- if (n == FlateOut) {
- 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 (n == FlateOk || n == FlateErr) {
- if (s->nbits || s->src < s->srcend) {
- s->nbits /= 8;
- stream->in = s->src - s->nbits;
- stream->nin = s->srcend - s->src + s->nbits;
- }
- stream->err = s->err;
- free(s);
- stream->state = 0;
- }
- return n;
-}
-
-typedef struct {
- ushort dist;
- ushort len;
-} Match;
-
-typedef struct {
- ushort n;
- ushort bits;
-} 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) */
- Match prevm; /* previous (deferred) match */
- int state; /* prev return value */
- int eof; /* end of input */
- uchar *in; /* input data (not yet in src) */
- uchar *inend;
- uint bits; /* for output */
- int nbits; /* for output */
- uchar *dst; /* compressed output (position in dstbuf) */
- uchar *dstbegin; /* start position of unflushed data in dstbuf */
- LzCode *lz; /* current pos in lzbuf */
- int nlit; /* literal run length in lzbuf */
- ushort head[HashSize]; /* position of hash chain heads */
- ushort chain[WinSize]; /* hash chain */
- ushort lfreq[Nlitlen];
- ushort dfreq[Ndist];
- uchar src[SrcSize]; /* input buf */
- uchar dstbuf[DstSize];
- LzCode lzbuf[LzSize]; /* literal run length, match len, match dist */
-} State;
-
-static uchar fixllen[Nlitlen]; /* fixed lit/len huffman code tree */
-static ushort fixlcode[Nlitlen];
-static uchar fixdlen[Ndist]; /* fixed distance huffman code tree */
-static ushort fixdcode[Ndist];
-
-static uint revcode(uint c, int n)
-{
- int i;
- uint r = 0;
-
- for (i = 0; i < n; i++) {
- r = (r << 1) | (c & 1);
- c >>= 1;
- }
- return r;
-}
-
-/* build huffman code tree from code lengths */
-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 (code = 0, i = 1; i < CodeBits; i++) {
- count = c[i];
- c[i] = code;
- code += count;
- 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;
-}
-
-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)
-{
- int p, c, tmp;
-
- c = len;
- heap[len++] = n;
- heap[len++] = w;
- while (c > 0) {
- p = heapparent(c);
- if (heap[c+1] < heap[p+1]) {
- 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;
- }
- return len;
-}
-
-static int heappop(int *heap, int len, int *w, int *n)
-{
- int p, c, tmp;
-
- *n = heap[0];
- *w = heap[1];
- heap[1] = heap[--len];
- heap[0] = heap[--len];
- p = 0;
- for (;;) {
- c = heapchild(p);
- 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;
- p = c;
- }
- return len;
-}
-
-/* symbol frequencies -> code lengths (limited to 255) */
-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];
- int heap[2*Nlitlen];
- int n, len, top, overflow;
- int i, j;
- int wi, wj;
-
- 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;
- /* deflate: fewer than two symbols: add new */
- for (n = 0; len < 4; n++)
- if (freqs[n] == 0) len = heappush(heap, len, ++freqs[n], n);
- /* build code tree */
- top = len;
- for (n = nsym; len > 2; n++) {
- len = heappop(heap, len, &wi, &i);
- len = heappop(heap, len, &wj, &j);
- parent[i] = n;
- parent[j] = n;
- len = heappush(heap, len, wi + wj, n);
- /* keep an ordered list of nodes at the end */
- heap[len+1] = i;
- heap[len] = j;
- }
- /* calc code lengths (deflate: with limit) */
- overflow = 0;
- parent[--n] = 0;
- for (i = 2; i < top; i++) {
- n = heap[i];
- if (n >= nsym) {
- /* overwrite parent index with length */
- parent[n] = parent[parent[n]] + 1;
- if (parent[n] > limit) overflow++;
- } else {
- lens[n] = parent[parent[n]] + 1;
- if (lens[n] > limit) {
- lens[n] = limit;
- overflow++;
- }
- count[lens[n]]++;
- }
- }
- if (overflow == 0) return;
- /* modify code tree to fix overflow (from zlib) */
- while (overflow > 0) {
- for (n = limit-1; count[n] == 0; n--);
- count[n]--;
- count[n+1] += 2;
- count[limit]--;
- overflow -= 2;
- }
- for (len = limit; len > 0; len--)
- for (i = count[len]; i > 0;) {
- n = heap[--top];
- if (n < nsym) {
- lens[n] = len;
- i--;
- }
- }
-}
-
-/* output n (<= 16) bits */
-static void putbits(State *s, uint bits, int n)
-{
- s->bits |= bits << s->nbits;
- s->nbits += n;
- while (s->nbits >= 8) {
- *s->dst++ = s->bits & 0xff;
- s->bits >>= 8;
- s->nbits -= 8;
- }
-}
-
-/* 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)
-{
- 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 + ndist;) {
- c = codes[i];
- for (r = 1; i + r < nlit + ndist && codes[i + r] == c; r++);
- i += r;
- if (c == 0) {
- while (r >= 11) {
- rr = r > 138 ? 138 : r;
- codes[n] = 18;
- extra[n++] = rr - 11;
- r -= rr;
- }
- if (r >= 3) {
- codes[n] = 17;
- extra[n++] = r - 3;
- r = 0;
- }
- }
- while (r--) {
- codes[n++] = c;
- while (r >= 3) {
- rr = r > 6 ? 6 : r;
- codes[n] = 16;
- extra[n++] = rr - 3;
- r -= rr;
- }
- }
- }
- return n;
-}
-
-/* compress block data into s->dstbuf using given codes */
-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 {
- p += TT.lenbase[lz->n] + lz->bits;
- putbits(s, lcode[Nlit + lz->n + 1], llen[Nlit + lz->n + 1]);
- putbits(s, lz->bits, TT.lenbits[lz->n]);
- lz++;
- putbits(s, dcode[lz->n], dlen[lz->n]);
- putbits(s, lz->bits, TT.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)
-{
- uchar codes[Nlitlen + Ndist], extra[Nlitlen + Ndist];
- uchar llen[Nlitlen], dlen[Ndist], clen[Nclen];
- ushort cfreq[Nclen];
- /* freq can be overwritten by code */
- ushort *lcode = s->lfreq, *dcode = s->dfreq, *ccode = cfreq;
- int i, c, n, ncodes;
- int nlit, ndist, nclen;
- LzCode *lz;
- uchar *p;
- int dynsize, fixsize, uncsize;
- int blocklen = s->pos - s->startpos;
-/* int dyntree; */
-
- /* calc dynamic codes */
- hufflens(llen, s->lfreq, Nlitlen, CodeBits-1);
- hufflens(dlen, s->dfreq, Ndist, CodeBits-1);
- huffcodes(lcode, llen, Nlitlen);
- huffcodes(dcode, dlen, Ndist);
- for (nlit = Nlitlen; nlit > Nlit && llen[nlit-1] == 0; nlit--);
- 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]]++;
- hufflens(clen, cfreq, Nclen, 7);
- huffcodes(ccode, clen, Nclen);
- for (nclen = Nclen; nclen > 4 && clen[clenorder[nclen-1]] == 0; nclen--);
-
- /* calc compressed size */
- uncsize = 3 + 16 + 8 * blocklen + (16 - 3 - s->nbits) % 8; /* byte aligned */
- fixsize = 3;
- dynsize = 3 + 5 + 5 + 4 + 3 * nclen;
- 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;
- }
-/* dyntree = dynsize - 3; */
- 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 {
- p += TT.lenbase[lz->n] + lz->bits;
- fixsize += fixllen[Nlit + lz->n + 1];
- dynsize += llen[Nlit + lz->n + 1];
- fixsize += TT.lenbits[lz->n];
- dynsize += TT.lenbits[lz->n];
- lz++;
- fixsize += fixdlen[lz->n];
- dynsize += dlen[lz->n];
- fixsize += TT.distbits[lz->n];
- dynsize += TT.distbits[lz->n];
- }
- }
- fixsize += fixllen[EOB];
- dynsize += llen[EOB];
-
- /* emit block */
- putbits(s, s->eof && s->pos == s->endpos, 1);
- if (dynsize < fixsize && dynsize < uncsize) {
- /* dynamic code */
- putbits(s, 2, 2);
- 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 < 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);
- }
- putblock(s, lcode, llen, dcode, dlen);
- } else if (fixsize < uncsize) {
- /* fixed code */
- putbits(s, 1, 2);
- putblock(s, fixlcode, fixllen, fixdcode, fixdlen);
- } else {
- /* uncompressed */
- putbits(s, 0, 2);
- putbits(s, 0, 7); /* align to byte boundary */
- s->nbits = 0;
- putbits(s, blocklen, 16);
- putbits(s, ~blocklen & 0xffff, 16);
- memcpy(s->dst, s->src + s->startpos, blocklen);
- s->dst += blocklen;
- }
-/*
-fprintf(stderr, "blen:%d [%d,%d] lzlen:%d dynlen:%d (tree:%d rate:%.3f) fixlen:%d (rate:%.3f) unclen:%d (rate:%.3f)\n",
- blocklen, s->startpos, s->pos, s->lz - s->lzbuf, dynsize, dyntree, dynsize/(float)blocklen,
- fixsize, fixsize/(float)blocklen, uncsize, uncsize/(float)blocklen);
-*/
-}
-
-/* find n in base */
-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;
- }
- return lo - 1;
-}
-
-/* add literal run length to lzbuf */
-static void flushlit(State *s)
-{
- if (s->nlit) {
- s->lz->bits = LzLitFlag;
- s->lz->n = s->nlit;
- s->lz++;
- s->nlit = 0;
- }
-}
-
-/* add match to lzbuf and update freq counts */
-static void recordmatch(State *s, Match m)
-{
- int n;
-
-/*fprintf(stderr, "m %d %d\n", m.len, m.dist);*/
- flushlit(s);
- n = bisect(TT.lenbase, Nlen, m.len);
- s->lz->n = n;
- s->lz->bits = m.len - TT.lenbase[n];
- s->lz++;
- s->lfreq[Nlit + n + 1]++;
- n = bisect(TT.distbase, Ndist, m.dist);
- s->lz->n = n;
- s->lz->bits = m.dist - TT.distbase[n];
- s->lz++;
- s->dfreq[n]++;
-}
-
-/* update literal run length */
-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;
-}
-
-/* update hash chain at the current position */
-static int updatechain(State *s)
-{
- int hash, next = 0, p = s->pos, i;
-
- 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;
- 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)
-{
- Match m = {0, MinMatch-1};
- int len;
- int limit = s->pos - MaxDist;
- int chainlen = MaxChainLen;
- uchar *q;
- uchar *p = s->src + s->pos;
- uchar *end = p + MaxMatch;
-
- do {
- 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;
- while (++p != end && *++q == *p);
- len = MaxMatch - (end - p);
- p -= len;
-/*fprintf(stderr,"match: len:%d dist:%d\n", len, s->pos - next);*/
- if (len > m.len) {
- m.dist = s->pos - next;
- m.len = len;
- if (s->pos + len >= s->endpos) { /* TODO: overflow */
- m.len = s->endpos - s->pos;
- 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;
-
- return m;
-}
-
-static void startblock(State *s)
-{
- s->startpos = s->pos;
- s->dst = s->dstbegin = s->dstbuf;
- s->lz = s->lzbuf;
- s->nlit = 0;
- memset(s->lfreq, 0, sizeof(s->lfreq));
- memset(s->dfreq, 0, sizeof(s->dfreq));
- s->lfreq[EOB]++;
-}
-
-static int shiftwin(State *s)
-{
- int n;
-
- 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;
- for (n = 0; n < WinSize; n++)
- s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0;
- 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))
- {
- /* deflate block */
- flushlit(s);
- if (s->prevm.len) s->pos--;
- deflate_block(s);
- if (s->eof && s->pos == s->endpos) putbits(s, 0, 7);
-
- return 1;
- }
-
- return 0;
-}
-
-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;
- memcpy(s->src + s->endpos, s->in, n);
- s->in += n;
- s->endpos += n;
- if (s->endpos < SrcSize) return 0;
- }
- return 1;
-}
-
-static int calcguard(State *s) {
- int p = s->endpos - MaxMatch;
- int q = s->startpos + BlockSize;
-
- return p < q ? p : q;
-}
-
-/* deflate compress from s->src into s->dstbuf */
-static int deflate_state(State *s)
-{
- Match m;
- int next;
- int guard;
-
- 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);
- startblock(s);
- 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);
- guard = calcguard(s);
- }
- next = updatechain(s);
- if (next) m = getmatch(s, next);
- if (next && m.len > s->prevm.len) {
- 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]);
- s->pos++;
- }
-}
-
-/* alloc and init state */
-static State *alloc_state(void)
-{
- State *s = malloc(sizeof(State));
- int i;
-
- 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;
- huffcodes(fixlcode, fixllen, Nlitlen);
- huffcodes(fixdcode, fixdlen, Ndist);
- }
- s->state = FlateOut;
- s->in = s->inend = 0;
- s->dst = s->dstbegin = s->dstbuf;
- s->pos = s->startpos = s->endpos = WinSize;
- s->eof = 0;
- s->skip = 0;
- s->prevm.len = 0;
- return s;
-}
-
-
-/* extern */
-
-int deflate(FlateStream *stream)
-{
- State *s = stream->state;
- int n, k;
-
- if (stream->err) {
- free(s);
- stream->state = 0;
- return FlateErr;
- }
- if (!s) {
- s = stream->state = alloc_state();
- 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;
- 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)
-{
- p[0] = n >> 24;
- p[1] = n >> 16;
- p[2] = n >> 8;
- p[3] = 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)
-{
- return n == ((p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3]);
-}
-
-static int check32le(uchar *p, uint n)
-{
- return n == (p[0] | (p[1] << 8) | (p[2] << 16) | (p[3] << 24));
-}
-
-enum {
- ZlibCM = 7 << 4,
- ZlibCINFO = 8,
- ZlibFLEV = 3 << 6,
- ZlibFDICT = 1 << 5,
- ZlibFCHK = 31 - (((ZlibCM | ZlibCINFO) << 8) | ZlibFLEV) % 31
-};
-
-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;
- 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;
-
- return 2;
-}
-
-int inflate_zlib_footer(uchar *p, int n, uint sum, uint len, uint zlen)
-{
- if (n < 4 || !check32(p, sum))
- return FlateErr;
- return 4;
-}
-
-
-enum {
- GZipID1 = 0x1f,
- GZipID2 = 0x8b,
- GZipCM = 8,
- GZipFHCRC = 1 << 1,
- GZipFEXTRA = 1 << 2,
- GZipFNAME = 1 << 3,
- GZipFCOMM = 1 << 4,
- GZipXFL = 2,
- GZipOS = 255
-};
-
-int deflate_gzip_header(uchar *p, int n)
-{
- if (n < 10)
- return FlateErr;
- memset(p, 0, 10);
- p[0] = GZipID1;
- p[1] = GZipID2;
- p[2] = GZipCM;
- p[8] = GZipXFL;
- p[9] = GZipOS;
- return 10;
-}
-
-int deflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen)
-{
- if (n < 8)
- return FlateErr;
- set32le(p, sum);
- set32le(p+4, len);
- return 8;
-}
-
-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 (p[3] & GZipFEXTRA) {
- k += 2 + ((p[k] << 8) | p[k+1]);
- if (k > n) return FlateErr;
- }
- if (p[3] & GZipFNAME) {
- for (; k < n; k++) if (p[k] == 0) break;
- k++;
- if (k > n) return FlateErr;
- }
- if (p[3] & GZipFCOMM) {
- for (; k < n; k++) if (p[k] == 0) break;
- k++;
- if (k > n) return FlateErr;
- }
- if (p[3] & GZipFHCRC) {
- k += 2;
- 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;
-
- return 8;
-}
-
-
-static char pkname[] = "sflate_stream";
-
-enum {
- PKHeadID = 0x04034b50,
- PKDataID = 0x08074b50,
- PKDirID = 0x02014b50,
- PKFootID = 0x06054b50,
- PKVersion = 20,
- PKFlag = 1 << 3,
- PKMethod = 8,
- PKDate = ((2009 - 1980) << 25) | (1 << 21) | (1 << 16),
- PKHeadSize = 30,
- PKDirSize = 46,
- PKNameLen = sizeof(pkname) - 1
-};
-
-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);
- set32le(p+6, PKFlag);
- set32le(p+8, PKMethod);
- set32le(p+10, PKDate);
- set32le(p+26, PKNameLen);
- memcpy(p + PKHeadSize, pkname, PKNameLen);
- return PKHeadSize + PKNameLen;
-}
-
-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;
- set32le(p, PKDataID);
- set32le(p+4, sum);
- set32le(p+8, zlen);
- set32le(p+12, len);
- p += 16;
-*/
- memset(p, 0, PKDirSize);
- set32le(p, PKDirID);
- set32le(p+4, PKVersion | (PKVersion << 16));
- set32le(p+8, PKFlag);
- set32le(p+10, PKMethod);
- set32le(p+12, PKDate);
- set32le(p+16, sum);
- set32le(p+20, zlen);
- set32le(p+24, len);
- set32le(p+28, PKNameLen);
- memcpy(p + PKDirSize, pkname, PKNameLen);
- p += PKDirSize + PKNameLen;
- memset(p, 0, 22);
- set32le(p, PKFootID);
- p[8] = p[10] = 1;
- set32le(p+12, PKDirSize + PKNameLen);
- set32le(p+16, zlen + PKHeadSize + PKNameLen);
- return PKDirSize + PKNameLen + 22;
-/*
- set32le(p+12, 16 + PKDirSize + PKNameLen);
- set32le(p+16, zlen + PKHeadSize + PKNameLen);
- return 16 + PKDirSize + PKNameLen + 22;
-*/
-}
-
-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;
- k += p[26] | (p[27] << 8);
- k += p[28] | (p[29] << 8);
- if (k > n) return FlateErr;
-
- return k;
-}
-
-int inflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen)
-{
- int k = PKDirSize + 22;
-
- if (k > n) return FlateErr;
- if (check32le(p, PKDataID)) {
- p += 16;
- k += 16;
- 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;
-
- return k;
-}
-
-
-/* example usage */
-
-static int (*header)(uchar *, int);
-static int (*footer)(uchar *, int, uint, uint, uint);
-static uint (*checksum)(uchar *, int, uint);
-static char *err;
-static uint sum;
-static uint nin;
-static uint nout;
-static uint headerlen;
-static uint footerlen;
-static uint extralen;
-
-static int dummyheader(uchar *p, int n) {
- return 0;
-}
-static int dummyfooter(uchar *p, int n, uint sum, uint len, uint zlen) {
- return 0;
-}
-static uint dummysum(uchar *p, int n, uint sum) {
- return 0;
-}
-
-/* compress, using FlateStream interface */
-int compress_stream(FILE *in, FILE *out)
-{
- FlateStream s;
- int k, n;
- enum {Nin = 1<<15, Nout = 1<<15};
-
- s.in = malloc(Nin);
- s.out = malloc(Nout);
- s.nin = 0;
- s.nout = Nout;
- s.err = 0;
- s.state = 0;
-
- k = header(s.out, s.nout);
- if (k == FlateErr) {
- s.err = "header error.";
- n = FlateErr;
- } else {
- headerlen = s.nout = k;
- n = FlateOut;
- }
- for (;; n = deflate(&s))
- switch (n) {
- case FlateOk:
- k = footer(s.out, s.nout, sum, nin, nout - headerlen);
- if (k == FlateErr) {
- s.err = "footer error.";
- n = FlateErr;
- } else if (k != fwrite(s.out, 1, k, out)) {
- s.err = "write error.";
- n = FlateErr;
- } else {
- footerlen = k;
- nout += k;
- }
- case FlateErr:
- free(s.in);
- free(s.out);
- err = s.err;
- return n;
- case FlateIn:
- s.nin = fread(s.in, 1, Nin, in);
- nin += s.nin;
- sum = checksum(s.in, s.nin, sum);
- break;
- case FlateOut:
- k = fwrite(s.out, 1, s.nout, out);
- if (k != s.nout)
- s.err = "write error.";
- nout += k;
- s.nout = Nout;
- break;
- }
-}
-
-/* decompress, using FlateStream interface */
-int decompress_stream(FILE *in, FILE *out)
-{
- FlateStream s;
- uchar *begin;
- int k, n;
- enum {Nin = 1<<15, Nout = 1<<15};
-
- s.in = begin = malloc(Nin);
- s.out = malloc(Nout);
- s.nout = Nout;
- s.err = 0;
- s.state = 0;
-
- s.nin = fread(s.in, 1, Nin, in);
- nin += s.nin;
- k = header(s.in, s.nin);
- if (k == FlateErr) {
- s.err = "header error.";
- n = FlateErr;
- } else {
- headerlen = k;
- s.nin -= k;
- s.in += k;
- n = inflate(&s);
- }
- for (;; n = inflate(&s))
- switch (n) {
- case FlateOk:
- memmove(begin, s.in, s.nin);
- k = fread(begin, 1, Nin-s.nin, in);
- nin += k;
- s.nin += k;
- k = footer(begin, s.nin, sum, nout, nin - s.nin - headerlen);
- if (k == FlateErr) {
- s.err = "footer error.";
- n = FlateErr;
- } else {
- footerlen = k;
- extralen = s.nin - k;
- }
- case FlateErr:
- free(begin);
- free(s.out);
- err = s.err;
- return n;
- case FlateIn:
- s.in = begin;
- s.nin = fread(s.in, 1, Nin, in);
- nin += s.nin;
- break;
- case FlateOut:
- k = fwrite(s.out, 1, s.nout, out);
- if (k != s.nout)
- s.err = "write error.";
- sum = checksum(s.out, k, sum);
- nout += k;
- s.nout = Nout;
- break;
- }
-}
-
-void gzip_main(void)
-{
- int (*call)(FILE *, FILE*);
- int n = 1, i;
-
- // Calculate lenbits, lenbase, distbits, distbase
- *TT.lenbase = 3;
- for (i = 0; i<sizeof(TT.lenbits)-1; i++) {
- if (i>4) {
- if (!(i&3)) {
- TT.lenbits[i]++;
- n <<= 1;
- }
- if (i == 27) n--;
- else TT.lenbits[i+1] = TT.lenbits[i];
- }
- TT.lenbase[i+1] = n + TT.lenbase[i];
- }
- n = 0;
- for (i = 0; i<sizeof(TT.distbits); i++) {
- TT.distbase[i] = 1<<n;
- if (i) TT.distbase[i] += TT.distbase[i-1];
- if (i>3 && !(i&1)) n++;
- TT.distbits[i] = n;
- }
-
- call = (toys.optflags & FLAG_c) ? compress_stream : decompress_stream;
-
- if (toys.optflags & FLAG_r) {
- header = dummyheader;
- footer = dummyfooter;
- checksum = dummysum;
- } else if (toys.optflags & FLAG_z) {
- if (toys.optflags & FLAG_c) {
- header = deflate_zlib_header;
- footer = deflate_zlib_footer;
- } else {
- header = inflate_zlib_header;
- footer = inflate_zlib_footer;
- }
- checksum = adler32;
- } else {
- checksum = crc32;
- crc32init();
-
- if (toys.optflags & FLAG_p) {
- if (toys.optflags & FLAG_c) {
- header = deflate_pkzip_header;
- footer = deflate_pkzip_footer;
- } else {
- header = inflate_pkzip_header;
- footer = inflate_pkzip_footer;
- }
- } else {
- if (toys.optflags & FLAG_c) {
- header = deflate_gzip_header;
- footer = deflate_gzip_footer;
- } else {
- header = inflate_gzip_header;
- footer = inflate_gzip_footer;
- }
- }
- }
-
- toys.exitval = call(stdin, stdout);
-
- if (toys.optflags & FLAG_v)
- fprintf(stderr, "in:%d out:%d checksum: 0x%08x (header:%d data:%d footer:%d extra input:%s)\n",
- nin, nout, sum, headerlen, ((toys.optflags & FLAG_c) ? nout : nin) - headerlen - footerlen - extralen,
- footerlen, extralen ? "yes" : "no");
-
- if (toys.exitval) fprintf(stderr, "error: %s\n", err);
-}