flate

deflate implementation
git clone git://git.suckless.org/flate
Log | Files | Refs | README

deflate.c (18222B)


      1 #include <stdlib.h>
      2 #include <string.h>
      3 #include "flate.h"
      4 
      5 enum {
      6 	CodeBits    = 16,      /* max number of bits in a code + 1 */
      7 	EOB         = 256,     /* end of block symbol */
      8 	Nlit        = 256,     /* number of lit codes */
      9 	Nlen        = 29,      /* number of len codes */
     10 	Nlitlen     = Nlit + Nlen + 3, /* litlen codes + block end + 2 unused */
     11 	Ndist       = 30,      /* number of distance codes */
     12 	Nclen       = 19,      /* number of code length codes */
     13 	MinMatch    = 3,       /* min match length */
     14 	MaxMatch    = 258,     /* max match length */
     15 	WinSize     = 1 << 15, /* sliding window size */
     16 
     17 	MaxChainLen = 256,     /* max length of hash chain */
     18 	HashBits    = 13,
     19 	HashSize    = 1 << HashBits, /* hash table size */
     20 	BigDist     = 1 << 12, /* max match distance for short match length */
     21 	MaxDist     = WinSize,
     22 	BlockSize   = 1 << 15, /* TODO */
     23 	SrcSize     = 2*WinSize + MaxMatch,
     24 	DstSize     = BlockSize + MaxMatch + 6, /* worst case compressed block size */
     25 	LzSize      = 1 << 13, /* lz buffer size */
     26 	LzGuard     = LzSize - 2,
     27 	LzLitFlag   = 1 << 15  /* marks literal run length in lz buffer */
     28 };
     29 
     30 typedef struct {
     31 	ushort dist;
     32 	ushort len;
     33 } Match;
     34 
     35 typedef struct {
     36 	ushort n;
     37 	ushort bits;
     38 } LzCode;
     39 
     40 typedef struct {
     41 	int pos;               /* position in input src */
     42 	int startpos;          /* block start pos in input src */
     43 	int endpos;            /* end of available bytes in src */
     44 	int skip;              /* skipped hash chain updates (until next iter) */
     45 	Match prevm;           /* previous (deferred) match */
     46 	int state;             /* prev return value */
     47 	int eof;               /* end of input */
     48 	uchar *in;             /* input data (not yet in src) */
     49 	uchar *inend;
     50 	uint bits;             /* for output */
     51 	int nbits;             /* for output */
     52 	uchar *dst;            /* compressed output (position in dstbuf) */
     53 	uchar *dstbegin;       /* start position of unflushed data in dstbuf */
     54 	LzCode *lz;            /* current pos in lzbuf */
     55 	int nlit;              /* literal run length in lzbuf */
     56 	ushort head[HashSize]; /* position of hash chain heads */
     57 	ushort chain[WinSize]; /* hash chain */
     58 	ushort lfreq[Nlitlen];
     59 	ushort dfreq[Ndist];
     60 	uchar src[SrcSize];    /* input buf */
     61 	uchar dstbuf[DstSize];
     62 	LzCode lzbuf[LzSize];  /* literal run length, match len, match dist */
     63 } State;
     64 
     65 static uchar fixllen[Nlitlen]; /* fixed lit/len huffman code tree */
     66 static ushort fixlcode[Nlitlen];
     67 static uchar fixdlen[Ndist];   /* fixed distance huffman code tree */
     68 static ushort fixdcode[Ndist];
     69 
     70 /* base offset and extra bits tables */
     71 static uchar lenbits[Nlen] = {
     72 	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
     73 };
     74 static ushort lenbase[Nlen] = {
     75 	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
     76 };
     77 static uchar distbits[Ndist] = {
     78 	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
     79 };
     80 static ushort distbase[Ndist] = {
     81 	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
     82 };
     83 
     84 /* ordering of code lengths */
     85 static uchar clenorder[Nclen] = {
     86 	16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
     87 };
     88 
     89 
     90 static uint revcode(uint c, int n) {
     91 	int i;
     92 	uint r = 0;
     93 
     94 	for (i = 0; i < n; i++) {
     95 		r = (r << 1) | (c & 1);
     96 		c >>= 1;
     97 	}
     98 	return r;
     99 }
    100 
    101 /* build huffman code tree from code lengths */
    102 static void huffcodes(ushort *codes, const uchar *lens, int n) {
    103 	int c[CodeBits];
    104 	int i, code, count;
    105 
    106 	/* count code lengths and calc first code for each length */
    107 	for (i = 0; i < CodeBits; i++)
    108 		c[i] = 0;
    109 	for (i = 0; i < n; i++)
    110 		c[lens[i]]++;
    111 	for (code = 0, i = 1; i < CodeBits; i++) {
    112 		count = c[i];
    113 		c[i] = code;
    114 		code += count;
    115 		if (code > (1 << i))
    116 			abort(); /* over-subscribed */
    117 		code <<= 1;
    118 	}
    119 	if (code < (1 << i))
    120 		/* incomplete */;
    121 
    122 	for (i = 0; i < n; i++)
    123 		if (lens[i])
    124 			codes[i] = revcode(c[lens[i]]++, lens[i]);
    125 		else
    126 			codes[i] = 0;
    127 }
    128 
    129 static int heapparent(int n) {return (n - 2)/4 * 2;}
    130 static int heapchild(int n)  {return 2 * n + 2;}
    131 
    132 static int heappush(int *heap, int len, int w, int n) {
    133 	int p, c, tmp;
    134 
    135 	c = len;
    136 	heap[len++] = n;
    137 	heap[len++] = w;
    138 	while (c > 0) {
    139 		p = heapparent(c);
    140 		if (heap[c+1] < heap[p+1]) {
    141 			tmp = heap[c]; heap[c] = heap[p]; heap[p] = tmp;
    142 			tmp = heap[c+1]; heap[c+1] = heap[p+1]; heap[p+1] = tmp;
    143 			c = p;
    144 		} else
    145 			break;
    146 	}
    147 	return len;
    148 }
    149 
    150 static int heappop(int *heap, int len, int *w, int *n) {
    151 	int p, c, tmp;
    152 
    153 	*n = heap[0];
    154 	*w = heap[1];
    155 	heap[1] = heap[--len];
    156 	heap[0] = heap[--len];
    157 	p = 0;
    158 	for (;;) {
    159 		c = heapchild(p);
    160 		if (c >= len)
    161 			break;
    162 		if (c+2 < len && heap[c+3] < heap[c+1])
    163 			c += 2;
    164 		if (heap[p+1] > heap[c+1]) {
    165 			tmp = heap[p]; heap[p] = heap[c]; heap[c] = tmp;
    166 			tmp = heap[p+1]; heap[p+1] = heap[c+1]; heap[c+1] = tmp;
    167 		} else
    168 			break;
    169 		p = c;
    170 	}
    171 	return len;
    172 }
    173 
    174 /* symbol frequencies -> code lengths (limited to 255) */
    175 static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) {
    176 	/* 2 <= nsym <= Nlitlen, log(nsym) <= limit <= CodeBits-1 */
    177 	int parent[2*Nlitlen-1];
    178 	int count[CodeBits];
    179 	int heap[2*Nlitlen];
    180 	int n, len, top, overflow;
    181 	int i, j;
    182 	int wi, wj;
    183 
    184 	for (n = 0; n < limit+1; n++)
    185 		count[n] = 0;
    186 	for (len = n = 0; n < nsym; n++)
    187 		if (freqs[n] > 0)
    188 			len = heappush(heap, len, freqs[n], n);
    189 		else
    190 			lens[n] = 0;
    191 	/* deflate: fewer than two symbols: add new */
    192 	for (n = 0; len < 4; n++)
    193 		if (freqs[n] == 0)
    194 			len = heappush(heap, len, ++freqs[n], n);
    195 	/* build code tree */
    196 	top = len;
    197 	for (n = nsym; len > 2; n++) {
    198 		len = heappop(heap, len, &wi, &i);
    199 		len = heappop(heap, len, &wj, &j);
    200 		parent[i] = n;
    201 		parent[j] = n;
    202 		len = heappush(heap, len, wi + wj, n);
    203 		/* keep an ordered list of nodes at the end */
    204 		heap[len+1] = i;
    205 		heap[len] = j;
    206 	}
    207 	/* calc code lengths (deflate: with limit) */
    208 	overflow = 0;
    209 	parent[--n] = 0;
    210 	for (i = 2; i < top; i++) {
    211 		n = heap[i];
    212 		if (n >= nsym) {
    213 			/* overwrite parent index with length */
    214 			parent[n] = parent[parent[n]] + 1;
    215 			if (parent[n] > limit)
    216 				overflow++;
    217 		} else {
    218 			lens[n] = parent[parent[n]] + 1;
    219 			if (lens[n] > limit) {
    220 				lens[n] = limit;
    221 				overflow++;
    222 			}
    223 			count[lens[n]]++;
    224 		}
    225 	}
    226 	if (overflow == 0)
    227 		return;
    228 	/* modify code tree to fix overflow (from zlib) */
    229 	while (overflow > 0) {
    230 		for (n = limit-1; count[n] == 0; n--);
    231 		count[n]--;
    232 		count[n+1] += 2;
    233 		count[limit]--;
    234 		overflow -= 2;
    235 	}
    236 	for (len = limit; len > 0; len--)
    237 		for (i = count[len]; i > 0;) {
    238 			n = heap[--top];
    239 			if (n < nsym) {
    240 				lens[n] = len;
    241 				i--;
    242 			}
    243 		}
    244 }
    245 
    246 /* output n (<= 16) bits */
    247 static void putbits(State *s, uint bits, int n) {
    248 	s->bits |= bits << s->nbits;
    249 	s->nbits += n;
    250 	while (s->nbits >= 8) {
    251 		*s->dst++ = s->bits & 0xff;
    252 		s->bits >>= 8;
    253 		s->nbits -= 8;
    254 	}
    255 }
    256 
    257 /* run length encode literal and dist code lengths into codes and extra */
    258 static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit, uchar *dlen, int ndist) {
    259 	int i, c, r, rr;
    260 	int n = 0;
    261 
    262 	for (i = 0; i < nlit; i++)
    263 		codes[i] = llen[i];
    264 	for (i = 0; i < ndist; i++)
    265 		codes[nlit + i] = dlen[i];
    266 	for (i = 0; i < nlit + ndist;) {
    267 		c = codes[i];
    268 		for (r = 1; i + r < nlit + ndist && codes[i + r] == c; r++);
    269 		i += r;
    270 		if (c == 0) {
    271 			while (r >= 11) {
    272 				rr = r > 138 ? 138 : r;
    273 				codes[n] = 18;
    274 				extra[n++] = rr - 11;
    275 				r -= rr;
    276 			}
    277 			if (r >= 3) {
    278 				codes[n] = 17;
    279 				extra[n++] = r - 3;
    280 				r = 0;
    281 			}
    282 		}
    283 		while (r--) {
    284 			codes[n++] = c;
    285 			while (r >= 3) {
    286 				rr = r > 6 ? 6 : r;
    287 				codes[n] = 16;
    288 				extra[n++] = rr - 3;
    289 				r -= rr;
    290 			}
    291 		}
    292 	}
    293 	return n;
    294 }
    295 
    296 /* compress block data into s->dstbuf using given codes */
    297 static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar *dlen) {
    298 	int n;
    299 	LzCode *lz;
    300 	uchar *p;
    301 
    302 	for (lz = s->lzbuf, p = s->src + s->startpos; lz != s->lz; lz++)
    303 		if (lz->bits & LzLitFlag)
    304 			for (n = lz->n; n > 0; n--, p++)
    305 				putbits(s, lcode[*p], llen[*p]);
    306 		else {
    307 			p += lenbase[lz->n] + lz->bits;
    308 			putbits(s, lcode[Nlit + lz->n + 1], llen[Nlit + lz->n + 1]);
    309 			putbits(s, lz->bits, lenbits[lz->n]);
    310 			lz++;
    311 			putbits(s, dcode[lz->n], dlen[lz->n]);
    312 			putbits(s, lz->bits, distbits[lz->n]);
    313 		}
    314 	putbits(s, lcode[EOB], llen[EOB]);
    315 }
    316 
    317 /* build code trees and select dynamic/fixed/uncompressed block compression */
    318 static void deflate_block(State *s) {
    319 	uchar codes[Nlitlen + Ndist], extra[Nlitlen + Ndist];
    320 	uchar llen[Nlitlen], dlen[Ndist], clen[Nclen];
    321 	ushort cfreq[Nclen];
    322 	/* freq can be overwritten by code */
    323 	ushort *lcode = s->lfreq, *dcode = s->dfreq, *ccode = cfreq;
    324 	int i, c, n, ncodes;
    325 	int nlit, ndist, nclen;
    326 	LzCode *lz;
    327 	uchar *p;
    328 	int dynsize, fixsize, uncsize;
    329 	int blocklen = s->pos - s->startpos;
    330 /* int dyntree; */
    331 
    332 	/* calc dynamic codes */
    333 	hufflens(llen, s->lfreq, Nlitlen, CodeBits-1);
    334 	hufflens(dlen, s->dfreq, Ndist, CodeBits-1);
    335 	huffcodes(lcode, llen, Nlitlen);
    336 	huffcodes(dcode, dlen, Ndist);
    337 	for (nlit = Nlitlen; nlit > Nlit && llen[nlit-1] == 0; nlit--);
    338 	for (ndist = Ndist; ndist > 1 && dlen[ndist-1] == 0; ndist--);
    339 	ncodes = clencodes(codes, extra, llen, nlit, dlen, ndist);
    340 	memset(cfreq, 0, sizeof(cfreq));
    341 	for (i = 0; i < ncodes; i++)
    342 		cfreq[codes[i]]++;
    343 	hufflens(clen, cfreq, Nclen, 7);
    344 	huffcodes(ccode, clen, Nclen);
    345 	for (nclen = Nclen; nclen > 4 && clen[clenorder[nclen-1]] == 0; nclen--);
    346 
    347 	/* calc compressed size */
    348 	uncsize = 3 + 16 + 8 * blocklen + (16 - 3 - s->nbits) % 8; /* byte aligned */
    349 	fixsize = 3;
    350 	dynsize = 3 + 5 + 5 + 4 + 3 * nclen;
    351 	for (i = 0; i < ncodes; i++) {
    352 		c = codes[i];
    353 		dynsize += clen[c];
    354 		if (c == 16)
    355 			dynsize += 2;
    356 		if (c == 17)
    357 			dynsize += 3;
    358 		if (c == 18)
    359 			dynsize += 7;
    360 	}
    361 /* dyntree = dynsize - 3; */
    362 	for (lz = s->lzbuf, p = s->src + s->startpos; lz != s->lz; lz++)
    363 		if (lz->bits & LzLitFlag)
    364 			for (n = lz->n; n > 0; n--, p++) {
    365 				fixsize += fixllen[*p];
    366 				dynsize += llen[*p];
    367 			}
    368 		else {
    369 			p += lenbase[lz->n] + lz->bits;
    370 			fixsize += fixllen[Nlit + lz->n + 1];
    371 			dynsize += llen[Nlit + lz->n + 1];
    372 			fixsize += lenbits[lz->n];
    373 			dynsize += lenbits[lz->n];
    374 			lz++;
    375 			fixsize += fixdlen[lz->n];
    376 			dynsize += dlen[lz->n];
    377 			fixsize += distbits[lz->n];
    378 			dynsize += distbits[lz->n];
    379 		}
    380 	fixsize += fixllen[EOB];
    381 	dynsize += llen[EOB];
    382 
    383 	/* emit block */
    384 	putbits(s, s->eof && s->pos == s->endpos, 1);
    385 	if (dynsize < fixsize && dynsize < uncsize) {
    386 		/* dynamic code */
    387 		putbits(s, 2, 2);
    388 		putbits(s, nlit - 257, 5);
    389 		putbits(s, ndist - 1, 5);
    390 		putbits(s, nclen - 4, 4);
    391 		for (i = 0; i < nclen; i++)
    392 			putbits(s, clen[clenorder[i]], 3);
    393 		for (i = 0; i < ncodes; i++) {
    394 			c = codes[i];
    395 			putbits(s, ccode[c], clen[c]);
    396 			if (c == 16)
    397 				putbits(s, extra[i], 2);
    398 			if (c == 17)
    399 				putbits(s, extra[i], 3);
    400 			if (c == 18)
    401 				putbits(s, extra[i], 7);
    402 		}
    403 		putblock(s, lcode, llen, dcode, dlen);
    404 	} else if (fixsize < uncsize) {
    405 		/* fixed code */
    406 		putbits(s, 1, 2);
    407 		putblock(s, fixlcode, fixllen, fixdcode, fixdlen);
    408 	} else {
    409 		/* uncompressed */
    410 		putbits(s, 0, 2);
    411 		putbits(s, 0, 7); /* align to byte boundary */
    412 		s->nbits = 0;
    413 		putbits(s, blocklen, 16);
    414 		putbits(s, ~blocklen & 0xffff, 16);
    415 		memcpy(s->dst, s->src + s->startpos, blocklen);
    416 		s->dst += blocklen;
    417 	}
    418 /*
    419 fprintf(stderr, "blen:%d [%d,%d] lzlen:%d dynlen:%d (tree:%d rate:%.3f) fixlen:%d (rate:%.3f) unclen:%d (rate:%.3f)\n",
    420 	blocklen, s->startpos, s->pos, s->lz - s->lzbuf, dynsize, dyntree, dynsize/(float)blocklen,
    421 	fixsize, fixsize/(float)blocklen, uncsize, uncsize/(float)blocklen);
    422 */
    423 }
    424 
    425 /* find n in base */
    426 static int bisect(ushort *base, int len, int n) {
    427 	int lo = 0;
    428 	int hi = len;
    429 	int k;
    430 
    431 	while (lo < hi) {
    432 		k = (lo + hi) / 2;
    433 		if (n < base[k])
    434 			hi = k;
    435 		else
    436 			lo = k + 1;
    437 	}
    438 	return lo - 1;
    439 }
    440 
    441 /* add literal run length to lzbuf */
    442 static void flushlit(State *s) {
    443 	if (s->nlit) {
    444 		s->lz->bits = LzLitFlag;
    445 		s->lz->n = s->nlit;
    446 		s->lz++;
    447 		s->nlit = 0;
    448 	}
    449 }
    450 
    451 /* add match to lzbuf and update freq counts */
    452 static void recordmatch(State *s, Match m) {
    453 	int n;
    454 
    455 /*fprintf(stderr, "m %d %d\n", m.len, m.dist);*/
    456 	flushlit(s);
    457 	n = bisect(lenbase, Nlen, m.len);
    458 	s->lz->n = n;
    459 	s->lz->bits = m.len - lenbase[n];
    460 	s->lz++;
    461 	s->lfreq[Nlit + n + 1]++;
    462 	n = bisect(distbase, Ndist, m.dist);
    463 	s->lz->n = n;
    464 	s->lz->bits = m.dist - distbase[n];
    465 	s->lz++;
    466 	s->dfreq[n]++;
    467 }
    468 
    469 /* update literal run length */
    470 static void recordlit(State *s, int c) {
    471 /*fprintf(stderr, "l %c\n", c);*/
    472 	s->nlit++;
    473 	s->lfreq[c]++;
    474 }
    475 
    476 /* multiplicative hash (using a prime close to golden ratio * 2^32) */
    477 static int gethash(uchar *p) {
    478 	return (0x9e3779b1 * ((p[0]<<16) + (p[1]<<8) + p[2]) >> (32 - HashBits)) % HashSize;
    479 }
    480 
    481 /* update hash chain at the current position */
    482 static int updatechain(State *s) {
    483 	int hash, next = 0, p = s->pos, i;
    484 
    485 	if (s->endpos - p < MinMatch)
    486 		p = s->endpos - MinMatch;
    487 	for (i = s->pos - s->skip; i <= p; i++) {
    488 		hash = gethash(s->src + i);
    489 		next = s->head[hash];
    490 		s->head[hash] = i;
    491 		if (next >= i || i - next >= MaxDist)
    492 			next = 0;
    493 		s->chain[i % WinSize] = next;
    494 	}
    495 	s->skip = 0;
    496 	return next;
    497 }
    498 
    499 /* find longest match, next position in the hash chain is given */
    500 static Match getmatch(State *s, int next) {
    501 	Match m = {0, MinMatch-1};
    502 	int len;
    503 	int limit = s->pos - MaxDist;
    504 	int chainlen = MaxChainLen;
    505 	uchar *q;
    506 	uchar *p = s->src + s->pos;
    507 	uchar *end = p + MaxMatch;
    508 
    509 	do {
    510 		q = s->src + next;
    511 /*fprintf(stderr,"match: next:%d pos:%d limit:%d\n", next, s->pos, limit);*/
    512 		/* next match should be at least m.len+1 long */
    513 		if (q[m.len] != p[m.len] || q[m.len-1] != p[m.len-1] || q[0] != p[0])
    514 			continue;
    515 		while (++p != end && *++q == *p);
    516 		len = MaxMatch - (end - p);
    517 		p -= len;
    518 /*fprintf(stderr,"match: len:%d dist:%d\n", len, s->pos - next);*/
    519 		if (len > m.len) {
    520 			m.dist = s->pos - next;
    521 			m.len = len;
    522 			if (s->pos + len >= s->endpos) { /* TODO: overflow */
    523 				m.len = s->endpos - s->pos;
    524 				return m;
    525 			}
    526 			if (len == MaxMatch)
    527 				return m;
    528 		}
    529 	} while ((next = s->chain[next % WinSize]) > limit && --chainlen);
    530 	if (m.len < MinMatch || (m.len == MinMatch && m.dist > BigDist))
    531 		m.len = 0;
    532 	return m;
    533 }
    534 
    535 static void startblock(State *s) {
    536 	s->startpos = s->pos;
    537 	s->dst = s->dstbegin = s->dstbuf;
    538 	s->lz = s->lzbuf;
    539 	s->nlit = 0;
    540 	memset(s->lfreq, 0, sizeof(s->lfreq));
    541 	memset(s->dfreq, 0, sizeof(s->dfreq));
    542 	s->lfreq[EOB]++;
    543 }
    544 
    545 static int shiftwin(State *s) {
    546 	int n;
    547 
    548 	if (s->startpos < WinSize)
    549 		return 0;
    550 	memmove(s->src, s->src + WinSize, SrcSize - WinSize);
    551 	for (n = 0; n < HashSize; n++)
    552 		s->head[n] = s->head[n] > WinSize ? s->head[n] - WinSize : 0;
    553 	for (n = 0; n < WinSize; n++)
    554 		s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0;
    555 	s->pos -= WinSize;
    556 	s->startpos -= WinSize;
    557 	s->endpos -= WinSize;
    558 	return 1;
    559 }
    560 
    561 static int endblock(State *s) {
    562 	if ((s->pos >= 2*WinSize && !shiftwin(s)) || s->pos - s->startpos >= BlockSize ||
    563 	  s->lz - s->lzbuf >= LzGuard || (s->eof && s->pos == s->endpos)) {
    564 		/* deflate block */
    565 		flushlit(s);
    566 		if (s->prevm.len)
    567 			s->pos--;
    568 		deflate_block(s);
    569 		if (s->eof && s->pos == s->endpos)
    570 			putbits(s, 0, 7);
    571 		return 1;
    572 	}
    573 	return 0;
    574 }
    575 
    576 static int fillsrc(State *s) {
    577 	int n, k;
    578 
    579 	if (s->endpos < SrcSize && !s->eof) {
    580 		n = SrcSize - s->endpos;
    581 		k = s->inend - s->in;
    582 		if (n > k)
    583 			n = k;
    584 		memcpy(s->src + s->endpos, s->in, n);
    585 		s->in += n;
    586 		s->endpos += n;
    587 		if (s->endpos < SrcSize)
    588 			return 0;
    589 	}
    590 	return 1;
    591 }
    592 
    593 static int calcguard(State *s) {
    594 	int p = s->endpos - MaxMatch;
    595 	int q = s->startpos + BlockSize;
    596 
    597 	return p < q ? p : q;
    598 }
    599 
    600 /* deflate compress from s->src into s->dstbuf */
    601 static int deflate_state(State *s) {
    602 	Match m;
    603 	int next;
    604 	int guard;
    605 
    606 	if (s->state == FlateIn)
    607 		s->eof = s->in == s->inend;
    608 	else if (s->state == FlateOut) {
    609 		if (s->dstbegin < s->dst)
    610 			return (s->state = FlateOut);
    611 		if (s->eof && s->pos == s->endpos)
    612 			return (s->state = FlateOk);
    613 		startblock(s);
    614 		if (s->prevm.len)
    615 			s->pos++;
    616 	} else
    617 		return s->state;
    618 
    619 	guard = calcguard(s);
    620 	for (;;) {
    621 		if (s->pos >= guard || s->lz - s->lzbuf >= LzGuard) {
    622 /*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);*/
    623 			if (endblock(s))
    624 				return (s->state = FlateOut);
    625 			if (!fillsrc(s))
    626 				return (s->state = FlateIn);
    627 			guard = calcguard(s);
    628 		}
    629 		next = updatechain(s);
    630 		if (next)
    631 			m = getmatch(s, next);
    632 		if (next && m.len > s->prevm.len) {
    633 			if (s->prevm.len)
    634 				recordlit(s, s->src[s->pos-1]);
    635 			s->prevm = m;
    636 		} else if (s->prevm.len) {
    637 			recordmatch(s, s->prevm);
    638 			s->skip = s->prevm.len - 2;
    639 			s->prevm.len = 0;
    640 			s->pos += s->skip;
    641 		} else
    642 			recordlit(s, s->src[s->pos]);
    643 		s->pos++;
    644 	}
    645 }
    646 
    647 /* alloc and init state */
    648 static State *alloc_state(void) {
    649 	State *s = malloc(sizeof(State));
    650 	int i;
    651 
    652 	if (!s)
    653 		return s;
    654 	memset(s->chain, 0, sizeof(s->chain));
    655 	memset(s->head, 0, sizeof(s->head));
    656 	s->bits = s->nbits = 0;
    657 	/* TODO: globals */
    658 	if (fixllen[0] == 0) {
    659 		for (i = 0; i < 144; i++)
    660 			fixllen[i] = 8;
    661 		for (; i < 256; i++)
    662 			fixllen[i] = 9;
    663 		for (; i < 280; i++)
    664 			fixllen[i] = 7;
    665 		for (; i < Nlitlen; i++)
    666 			fixllen[i] = 8;
    667 		for (i = 0; i < Ndist; i++)
    668 			fixdlen[i] = 5;
    669 		huffcodes(fixlcode, fixllen, Nlitlen);
    670 		huffcodes(fixdcode, fixdlen, Ndist);
    671 	}
    672 	s->state = FlateOut;
    673 	s->in = s->inend = 0;
    674 	s->dst = s->dstbegin = s->dstbuf;
    675 	s->pos = s->startpos = s->endpos = WinSize;
    676 	s->eof = 0;
    677 	s->skip = 0;
    678 	s->prevm.len = 0;
    679 	return s;
    680 }
    681 
    682 
    683 /* extern */
    684 
    685 int deflate(FlateStream *stream) {
    686 	State *s = stream->state;
    687 	int n, k;
    688 
    689 	if (stream->err) {
    690 		free(s);
    691 		stream->state = 0;
    692 		return FlateErr;
    693 	}
    694 	if (!s) {
    695 		s = stream->state = alloc_state();
    696 		if (!s)
    697 			return stream->err = "no mem.", FlateErr;
    698 	}
    699 	if (stream->nin) {
    700 		s->in = stream->in;
    701 		s->inend = s->in + stream->nin;
    702 		stream->nin = 0;
    703 	}
    704 	n = deflate_state(s);
    705 	if (n == FlateOut) {
    706 		k = s->dst - s->dstbegin;
    707 		if (k < stream->nout)
    708 			stream->nout = k;
    709 		memcpy(stream->out, s->dstbegin, stream->nout);
    710 		s->dstbegin += stream->nout;
    711 	}
    712 	if (n == FlateOk || n == FlateErr) {
    713 		free(s);
    714 		stream->state = 0;
    715 	}
    716 	return n;
    717 }