Add Szabolcs Nagy's deflate/inflate code from git://git.suckless.org/flate

Confirmed with him on IRC it's ok to use under toybox license, glued the files
together and hammered square peg into round hole, no other changes yet.

1 files changed, 1965 insertions, 0 deletions

diff --git a/toys/pending/gzip.c b/toys/pending/gzip.c
new file mode 100644
index 00000000..ada2b323
--- /dev/null
+++ b/toys/pending/gzip.c
@@ -0,0 +1,1965 @@
+/* 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", TOYFLAG_USR|TOYFLAG_BIN))
+
+config GZIP
+  bool "gzip"
+  default n
+  help
+    usage: gzip [-qvcdrgzp] FILE
+
+    Transitional gzip, needs work. Combines gzip, zlib, and pkzip.
+
+    -q quiet (default)\n
+    -v verbose\n
+    -c compress (default)\n
+    -d decompress\n
+    -r raw (default)\n
+    -g gzip\n
+    -z zlib\n
+    -p pkzip\n
+*/
+
+#define FOR_gzip
+#include "toys.h"
+
+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
+};
+
+typedef struct {
+	int nin;
+	int nout;
+	uchar *in;
+	uchar *out;
+	char *err;
+	void *state;
+} FlateStream;
+
+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;
+}
+
+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 */
+	Nlitlen         = Nlit+Nlen+3, /* litlen codes + block end + 2 unused */
+	Ndist           = 30,  /* number of distance codes */
+	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 {
+	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;
+
+/* TODO: globals.. initialization is not thread safe */
+static Huff lhuff; /* fixed lit/len huffman code tree */
+static Huff dhuff; /* fixed distance huffman code tree */
+
+/* base offset and extra bits tables */
+static uchar lenbits[Nlen] = {
+	0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
+};
+static ushort lenbase[Nlen] = {
+	3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
+};
+static uchar distbits[Ndist] = {
+	0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
+};
+static ushort distbase[Ndist] = {
+	1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
+};
+
+/* 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, lenbits[sym])) {
+				s->nclen = sym; /* using nclen to store sym */
+				s->pos = pos;
+				s->state = DecodeBlockLenBits;
+				return FlateIn;
+			}
+			len = lenbase[sym] + getbits_fast(&s->bits, &s->nbits, 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, distbits[sym])) {
+				s->nclen = sym; /* using nclen to store sym */
+				s->pos = pos;
+				s->lenpos = len;
+				s->state = DecodeBlockDistBits;
+				return FlateIn;
+			}
+			dist = distbase[sym] + getbits_fast(&s->bits, &s->nbits, distbits[sym]);
+			/* copy match, loop unroll in common case */
+			if (pos + len < WinSize) {
+				/* 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 += lenbase[lz->n] + lz->bits;
+			putbits(s, lcode[Nlit + lz->n + 1], llen[Nlit + lz->n + 1]);
+			putbits(s, lz->bits, lenbits[lz->n]);
+			lz++;
+			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) {
+	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 += lenbase[lz->n] + lz->bits;
+			fixsize += fixllen[Nlit + lz->n + 1];
+			dynsize += llen[Nlit + lz->n + 1];
+			fixsize += lenbits[lz->n];
+			dynsize += lenbits[lz->n];
+			lz++;
+			fixsize += fixdlen[lz->n];
+			dynsize += dlen[lz->n];
+			fixsize += distbits[lz->n];
+			dynsize += 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(lenbase, Nlen, m.len);
+	s->lz->n = n;
+	s->lz->bits = m.len - lenbase[n];
+	s->lz++;
+	s->lfreq[Nlit + n + 1]++;
+	n = bisect(distbase, Ndist, m.dist);
+	s->lz->n = n;
+	s->lz->bits = m.dist - 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;
+		}
+}
+
+static int old_main(int argc, char *argv[]) {
+	char comp = 'c';
+	char fmt = 'r';
+	char verbose = 'q';
+	int (*call)(FILE *, FILE*);
+	int n, i;
+
+	for (i = 1; i < argc; i++) {
+		if (argv[i][0] == '-' && argv[i][1] && argv[i][2] == 0)
+			switch (argv[i][1]) {
+			case 'q':
+			case 'v':
+				verbose = argv[i][1];
+				continue;
+			case 'c':
+			case 'd':
+				comp = argv[i][1];
+				continue;
+			case 'r':
+			case 'g':
+			case 'z':
+			case 'p':
+				fmt = argv[i][1];
+				continue;
+			}
+		fprintf(stderr, "usage: %s [-q|-v] [-c|-d] [-r|-g|-z|-p]\n\n"
+			"deflate stream compression\n"
+			" -q quiet (default)\n"
+			" -v verbose\n"
+			" -c compress (default)\n"
+			" -d decompress\n"
+			" -r raw (default)\n"
+			" -g gzip\n"
+			" -z zlib\n"
+			" -p pkzip\n", argv[0]);
+		return -1;
+	}
+	call = comp == 'c' ? compress_stream : decompress_stream;
+	switch (fmt) {
+	case 'r':
+		header = dummyheader;
+		footer = dummyfooter;
+		checksum = dummysum;
+		n = call(stdin, stdout);
+		break;
+	case 'g':
+		if (comp == 'c') {
+			header = deflate_gzip_header;
+			footer = deflate_gzip_footer;
+		} else {
+			header = inflate_gzip_header;
+			footer = inflate_gzip_footer;
+		}
+		checksum = crc32;
+		crc32init();
+		n = call(stdin, stdout);
+		break;
+	case 'z':
+		if (comp == 'c') {
+			header = deflate_zlib_header;
+			footer = deflate_zlib_footer;
+		} else {
+			header = inflate_zlib_header;
+			footer = inflate_zlib_footer;
+		}
+		checksum = adler32;
+		n = call(stdin, stdout);
+		break;
+	case 'p':
+		if (comp == 'c') {
+			header = deflate_pkzip_header;
+			footer = deflate_pkzip_footer;
+		} else {
+			header = inflate_pkzip_header;
+			footer = inflate_pkzip_footer;
+		}
+		checksum = crc32;
+		crc32init();
+		n = call(stdin, stdout);
+		break;
+	default:
+		err = "uninplemented.";
+		n = FlateErr;
+		break;
+	}
+	if (verbose == 'v')
+		fprintf(stderr, "in:%d out:%d checksum: 0x%08x (header:%d data:%d footer:%d extra input:%s)\n",
+			nin, nout, sum, headerlen, (comp == 'c' ? nout : nin) - headerlen - footerlen - extralen,
+			footerlen, extralen ? "yes" : "no");
+	if (n != FlateOk)
+		fprintf(stderr, "error: %s\n", err);
+	return n;
+}
+
+// Total hack
+void gzip_main(void)
+{
+  int i;
+
+  for (i=0; toys.argv[i]; i++);
+  old_main(i, toys.argv);
+}
+
+