2 * Zlib (RFC1950 / RFC1951) compression for PuTTY.
4 * There will no doubt be criticism of my decision to reimplement
5 * Zlib compression from scratch instead of using the existing zlib
6 * code. People will cry `reinventing the wheel'; they'll claim
7 * that the `fundamental basis of OSS' is code reuse; they'll want
8 * to see a really good reason for me having chosen not to use the
11 * Well, here are my reasons. Firstly, I don't want to link the
12 * whole of zlib into the PuTTY binary; PuTTY is justifiably proud
13 * of its small size and I think zlib contains a lot of unnecessary
14 * baggage for the kind of compression that SSH requires.
16 * Secondly, I also don't like the alternative of using zlib.dll.
17 * Another thing PuTTY is justifiably proud of is its ease of
18 * installation, and the last thing I want to do is to start
19 * mandating DLLs. Not only that, but there are two _kinds_ of
20 * zlib.dll kicking around, one with C calling conventions on the
21 * exported functions and another with WINAPI conventions, and
22 * there would be a significant danger of getting the wrong one.
24 * Thirdly, there seems to be a difference of opinion on the IETF
25 * secsh mailing list about the correct way to round off a
26 * compressed packet and start the next. In particular, there's
27 * some talk of switching to a mechanism zlib isn't currently
28 * capable of supporting (see below for an explanation). Given that
29 * sort of uncertainty, I thought it might be better to have code
30 * that will support even the zlib-incompatible worst case.
32 * Fourthly, it's a _second implementation_. Second implementations
33 * are fundamentally a Good Thing in standardisation efforts. The
34 * difference of opinion mentioned above has arisen _precisely_
35 * because there has been only one zlib implementation and
36 * everybody has used it. I don't intend that this should happen
43 #ifdef ZLIB_STANDALONE
46 * This module also makes a handy zlib decoding tool for when
47 * you're picking apart Zip files or PDFs or PNGs. If you compile
48 * it with ZLIB_STANDALONE defined, it builds on its own and
49 * becomes a command-line utility.
51 * Therefore, here I provide a self-contained implementation of the
52 * macros required from the rest of the PuTTY sources.
54 #define snew(type) ( (type *) malloc(sizeof(type)) )
55 #define snewn(n, type) ( (type *) malloc((n) * sizeof(type)) )
56 #define sresize(x, n, type) ( (type *) realloc((x), (n) * sizeof(type)) )
57 #define sfree(x) ( free((x)) )
68 /* ----------------------------------------------------------------------
69 * Basic LZ77 code. This bit is designed modularly, so it could be
70 * ripped out and used in a different LZ77 compressor. Go to it,
74 struct LZ77InternalContext;
76 struct LZ77InternalContext *ictx;
78 void (*literal) (struct LZ77Context * ctx, unsigned char c);
79 void (*match) (struct LZ77Context * ctx, int distance, int len);
83 * Initialise the private fields of an LZ77Context. It's up to the
84 * user to initialise the public fields.
86 static int lz77_init(struct LZ77Context *ctx);
89 * Supply data to be compressed. Will update the private fields of
90 * the LZ77Context, and will call literal() and match() to output.
91 * If `compress' is FALSE, it will never emit a match, but will
92 * instead call literal() for everything.
94 static void lz77_compress(struct LZ77Context *ctx,
95 unsigned char *data, int len, int compress);
98 * Modifiable parameters.
100 #define WINSIZE 32768 /* window size. Must be power of 2! */
101 #define HASHMAX 2039 /* one more than max hash value */
102 #define MAXMATCH 32 /* how many matches we track */
103 #define HASHCHARS 3 /* how many chars make a hash */
106 * This compressor takes a less slapdash approach than the
107 * gzip/zlib one. Rather than allowing our hash chains to fall into
108 * disuse near the far end, we keep them doubly linked so we can
109 * _find_ the far end, and then every time we add a new byte to the
110 * window (thus rolling round by one and removing the previous
111 * byte), we can carefully remove the hash chain entry.
114 #define INVALID -1 /* invalid hash _and_ invalid offset */
116 short next, prev; /* array indices within the window */
121 short first; /* window index of first in chain */
128 struct LZ77InternalContext {
129 struct WindowEntry win[WINSIZE];
130 unsigned char data[WINSIZE];
132 struct HashEntry hashtab[HASHMAX];
133 unsigned char pending[HASHCHARS];
137 static int lz77_hash(unsigned char *data)
139 return (257 * data[0] + 263 * data[1] + 269 * data[2]) % HASHMAX;
142 static int lz77_init(struct LZ77Context *ctx)
144 struct LZ77InternalContext *st;
147 st = snew(struct LZ77InternalContext);
153 for (i = 0; i < WINSIZE; i++)
154 st->win[i].next = st->win[i].prev = st->win[i].hashval = INVALID;
155 for (i = 0; i < HASHMAX; i++)
156 st->hashtab[i].first = INVALID;
164 static void lz77_advance(struct LZ77InternalContext *st,
165 unsigned char c, int hash)
170 * Remove the hash entry at winpos from the tail of its chain,
171 * or empty the chain if it's the only thing on the chain.
173 if (st->win[st->winpos].prev != INVALID) {
174 st->win[st->win[st->winpos].prev].next = INVALID;
175 } else if (st->win[st->winpos].hashval != INVALID) {
176 st->hashtab[st->win[st->winpos].hashval].first = INVALID;
180 * Create a new entry at winpos and add it to the head of its
183 st->win[st->winpos].hashval = hash;
184 st->win[st->winpos].prev = INVALID;
185 off = st->win[st->winpos].next = st->hashtab[hash].first;
186 st->hashtab[hash].first = st->winpos;
188 st->win[off].prev = st->winpos;
189 st->data[st->winpos] = c;
192 * Advance the window pointer.
194 st->winpos = (st->winpos + 1) & (WINSIZE - 1);
197 #define CHARAT(k) ( (k)<0 ? st->data[(st->winpos+k)&(WINSIZE-1)] : data[k] )
199 static void lz77_compress(struct LZ77Context *ctx,
200 unsigned char *data, int len, int compress)
202 struct LZ77InternalContext *st = ctx->ictx;
203 int i, hash, distance, off, nmatch, matchlen, advance;
204 struct Match defermatch, matches[MAXMATCH];
208 * Add any pending characters from last time to the window. (We
209 * might not be able to.)
211 for (i = 0; i < st->npending; i++) {
212 unsigned char foo[HASHCHARS];
214 if (len + st->npending - i < HASHCHARS) {
215 /* Update the pending array. */
216 for (j = i; j < st->npending; j++)
217 st->pending[j - i] = st->pending[j];
220 for (j = 0; j < HASHCHARS; j++)
221 foo[j] = (i + j < st->npending ? st->pending[i + j] :
222 data[i + j - st->npending]);
223 lz77_advance(st, foo[0], lz77_hash(foo));
231 /* Don't even look for a match, if we're not compressing. */
232 if (compress && len >= HASHCHARS) {
234 * Hash the next few characters.
236 hash = lz77_hash(data);
239 * Look the hash up in the corresponding hash chain and see
243 for (off = st->hashtab[hash].first;
244 off != INVALID; off = st->win[off].next) {
245 /* distance = 1 if off == st->winpos-1 */
246 /* distance = WINSIZE if off == st->winpos */
248 WINSIZE - (off + WINSIZE - st->winpos) % WINSIZE;
249 for (i = 0; i < HASHCHARS; i++)
250 if (CHARAT(i) != CHARAT(i - distance))
252 if (i == HASHCHARS) {
253 matches[nmatch].distance = distance;
254 matches[nmatch].len = 3;
255 if (++nmatch >= MAXMATCH)
266 * We've now filled up matches[] with nmatch potential
267 * matches. Follow them down to find the longest. (We
268 * assume here that it's always worth favouring a
269 * longer match over a shorter one.)
271 matchlen = HASHCHARS;
272 while (matchlen < len) {
274 for (i = j = 0; i < nmatch; i++) {
275 if (CHARAT(matchlen) ==
276 CHARAT(matchlen - matches[i].distance)) {
277 matches[j++] = matches[i];
287 * We've now got all the longest matches. We favour the
288 * shorter distances, which means we go with matches[0].
289 * So see if we want to defer it or throw it away.
291 matches[0].len = matchlen;
292 if (defermatch.len > 0) {
293 if (matches[0].len > defermatch.len + 1) {
294 /* We have a better match. Emit the deferred char,
295 * and defer this match. */
296 ctx->literal(ctx, (unsigned char) deferchr);
297 defermatch = matches[0];
301 /* We don't have a better match. Do the deferred one. */
302 ctx->match(ctx, defermatch.distance, defermatch.len);
303 advance = defermatch.len - 1;
307 /* There was no deferred match. Defer this one. */
308 defermatch = matches[0];
314 * We found no matches. Emit the deferred match, if
315 * any; otherwise emit a literal.
317 if (defermatch.len > 0) {
318 ctx->match(ctx, defermatch.distance, defermatch.len);
319 advance = defermatch.len - 1;
322 ctx->literal(ctx, data[0]);
328 * Now advance the position by `advance' characters,
329 * keeping the window and hash chains consistent.
331 while (advance > 0) {
332 if (len >= HASHCHARS) {
333 lz77_advance(st, *data, lz77_hash(data));
335 st->pending[st->npending++] = *data;
344 /* ----------------------------------------------------------------------
345 * Zlib compression. We always use the static Huffman tree option.
346 * Mostly this is because it's hard to scan a block in advance to
347 * work out better trees; dynamic trees are great when you're
348 * compressing a large file under no significant time constraint,
349 * but when you're compressing little bits in real time, things get
352 * I suppose it's possible that I could compute Huffman trees based
353 * on the frequencies in the _previous_ block, as a sort of
354 * heuristic, but I'm not confident that the gain would balance out
355 * having to transmit the trees.
359 unsigned char *outbuf;
361 unsigned long outbits;
367 static void outbits(struct Outbuf *out, unsigned long bits, int nbits)
369 assert(out->noutbits + nbits <= 32);
370 out->outbits |= bits << out->noutbits;
371 out->noutbits += nbits;
372 while (out->noutbits >= 8) {
373 if (out->outlen >= out->outsize) {
374 out->outsize = out->outlen + 64;
375 out->outbuf = sresize(out->outbuf, out->outsize, unsigned char);
377 out->outbuf[out->outlen++] = (unsigned char) (out->outbits & 0xFF);
383 static const unsigned char mirrorbytes[256] = {
384 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
385 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
386 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
387 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
388 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
389 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
390 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
391 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
392 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
393 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
394 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
395 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
396 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
397 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
398 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
399 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
400 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
401 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
402 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
403 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
404 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
405 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
406 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
407 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
408 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
409 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
410 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
411 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
412 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
413 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
414 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
415 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
419 short code, extrabits;
423 static const coderecord lencodes[] = {
455 static const coderecord distcodes[] = {
478 {22, 10, 2049, 3072},
479 {23, 10, 3073, 4096},
480 {24, 11, 4097, 6144},
481 {25, 11, 6145, 8192},
482 {26, 12, 8193, 12288},
483 {27, 12, 12289, 16384},
484 {28, 13, 16385, 24576},
485 {29, 13, 24577, 32768},
488 static void zlib_literal(struct LZ77Context *ectx, unsigned char c)
490 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
492 if (out->comp_disabled) {
494 * We're in an uncompressed block, so just output the byte.
501 /* 0 through 143 are 8 bits long starting at 00110000. */
502 outbits(out, mirrorbytes[0x30 + c], 8);
504 /* 144 through 255 are 9 bits long starting at 110010000. */
505 outbits(out, 1 + 2 * mirrorbytes[0x90 - 144 + c], 9);
509 static void zlib_match(struct LZ77Context *ectx, int distance, int len)
511 const coderecord *d, *l;
513 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
515 assert(!out->comp_disabled);
521 * We can transmit matches of lengths 3 through 258
522 * inclusive. So if len exceeds 258, we must transmit in
523 * several steps, with 258 or less in each step.
525 * Specifically: if len >= 261, we can transmit 258 and be
526 * sure of having at least 3 left for the next step. And if
527 * len <= 258, we can just transmit len. But if len == 259
528 * or 260, we must transmit len-3.
530 thislen = (len > 260 ? 258 : len <= 258 ? len : len - 3);
534 * Binary-search to find which length code we're
538 j = sizeof(lencodes) / sizeof(*lencodes);
542 if (thislen < lencodes[k].min)
544 else if (thislen > lencodes[k].max)
548 break; /* found it! */
553 * Transmit the length code. 256-279 are seven bits
554 * starting at 0000000; 280-287 are eight bits starting at
557 if (l->code <= 279) {
558 outbits(out, mirrorbytes[(l->code - 256) * 2], 7);
560 outbits(out, mirrorbytes[0xc0 - 280 + l->code], 8);
564 * Transmit the extra bits.
567 outbits(out, thislen - l->min, l->extrabits);
570 * Binary-search to find which distance code we're
574 j = sizeof(distcodes) / sizeof(*distcodes);
578 if (distance < distcodes[k].min)
580 else if (distance > distcodes[k].max)
584 break; /* found it! */
589 * Transmit the distance code. Five bits starting at 00000.
591 outbits(out, mirrorbytes[d->code * 8], 5);
594 * Transmit the extra bits.
597 outbits(out, distance - d->min, d->extrabits);
601 void *zlib_compress_init(void)
604 struct LZ77Context *ectx = snew(struct LZ77Context);
607 ectx->literal = zlib_literal;
608 ectx->match = zlib_match;
610 out = snew(struct Outbuf);
611 out->outbits = out->noutbits = 0;
613 out->comp_disabled = FALSE;
614 ectx->userdata = out;
619 void zlib_compress_cleanup(void *handle)
621 struct LZ77Context *ectx = (struct LZ77Context *)handle;
622 sfree(ectx->userdata);
628 * Turn off actual LZ77 analysis for one block, to facilitate
629 * construction of a precise-length IGNORE packet. Returns the
630 * length adjustment (which is only valid for packets < 65536
631 * bytes, but that seems reasonable enough).
633 static int zlib_disable_compression(void *handle)
635 struct LZ77Context *ectx = (struct LZ77Context *)handle;
636 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
639 out->comp_disabled = TRUE;
643 * If this is the first block, we will start by outputting two
644 * header bytes, and then three bits to begin an uncompressed
645 * block. This will cost three bytes (because we will start on
646 * a byte boundary, this is certain).
648 if (out->firstblock) {
652 * Otherwise, we will output seven bits to close the
653 * previous static block, and _then_ three bits to begin an
654 * uncompressed block, and then flush the current byte.
655 * This may cost two bytes or three, depending on noutbits.
657 n += (out->noutbits + 10) / 8;
661 * Now we output four bytes for the length / ~length pair in
662 * the uncompressed block.
669 int zlib_compress_block(void *handle, unsigned char *block, int len,
670 unsigned char **outblock, int *outlen)
672 struct LZ77Context *ectx = (struct LZ77Context *)handle;
673 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
677 out->outlen = out->outsize = 0;
680 * If this is the first block, output the Zlib (RFC1950) header
681 * bytes 78 9C. (Deflate compression, 32K window size, default
684 if (out->firstblock) {
685 outbits(out, 0x9C78, 16);
692 if (out->comp_disabled) {
694 outbits(out, 0, 7); /* close static block */
697 int blen = (len < 65535 ? len : 65535);
700 * Start a Deflate (RFC1951) uncompressed block. We
701 * transmit a zero bit (BFINAL=0), followed by a zero
702 * bit and a one bit (BTYPE=00). Of course these are in
703 * the wrong order (00 0).
708 * Output zero bits to align to a byte boundary.
711 outbits(out, 0, 8 - out->noutbits);
714 * Output the block length, and then its one's
715 * complement. They're little-endian, so all we need to
716 * do is pass them straight to outbits() with bit count
719 outbits(out, blen, 16);
720 outbits(out, blen ^ 0xFFFF, 16);
723 * Do the `compression': we need to pass the data to
724 * lz77_compress so that it will be taken into account
725 * for subsequent (distance,length) pairs. But
726 * lz77_compress is passed FALSE, which means it won't
727 * actually find (or even look for) any matches; so
728 * every character will be passed straight to
729 * zlib_literal which will spot out->comp_disabled and
730 * emit in the uncompressed format.
732 lz77_compress(ectx, block, blen, FALSE);
737 outbits(out, 2, 3); /* open new block */
741 * Start a Deflate (RFC1951) fixed-trees block. We
742 * transmit a zero bit (BFINAL=0), followed by a zero
743 * bit and a one bit (BTYPE=01). Of course these are in
744 * the wrong order (01 0).
750 * Do the compression.
752 lz77_compress(ectx, block, len, TRUE);
755 * End the block (by transmitting code 256, which is
756 * 0000000 in fixed-tree mode), and transmit some empty
757 * blocks to ensure we have emitted the byte containing the
758 * last piece of genuine data. There are three ways we can
761 * - Minimal flush. Output end-of-block and then open a
762 * new static block. This takes 9 bits, which is
763 * guaranteed to flush out the last genuine code in the
764 * closed block; but allegedly zlib can't handle it.
766 * - Zlib partial flush. Output EOB, open and close an
767 * empty static block, and _then_ open the new block.
768 * This is the best zlib can handle.
770 * - Zlib sync flush. Output EOB, then an empty
771 * _uncompressed_ block (000, then sync to byte
772 * boundary, then send bytes 00 00 FF FF). Then open the
775 * For the moment, we will use Zlib partial flush.
777 outbits(out, 0, 7); /* close block */
778 outbits(out, 2, 3 + 7); /* empty static block */
779 outbits(out, 2, 3); /* open new block */
782 out->comp_disabled = FALSE;
784 *outblock = out->outbuf;
785 *outlen = out->outlen;
790 /* ----------------------------------------------------------------------
791 * Zlib decompression. Of course, even though our compressor always
792 * uses static trees, our _decompressor_ has to be capable of
793 * handling dynamic trees if it sees them.
797 * The way we work the Huffman decode is to have a table lookup on
798 * the first N bits of the input stream (in the order they arrive,
799 * of course, i.e. the first bit of the Huffman code is in bit 0).
800 * Each table entry lists the number of bits to consume, plus
801 * either an output code or a pointer to a secondary table.
804 struct zlib_tableentry;
806 struct zlib_tableentry {
809 struct zlib_table *nexttable;
813 int mask; /* mask applied to input bit stream */
814 struct zlib_tableentry *table;
817 #define MAXCODELEN 16
821 * Build a single-level decode table for elements
822 * [minlength,maxlength) of the provided code/length tables, and
823 * recurse to build subtables.
825 static struct zlib_table *zlib_mkonetab(int *codes, unsigned char *lengths,
827 int pfx, int pfxbits, int bits)
829 struct zlib_table *tab = snew(struct zlib_table);
830 int pfxmask = (1 << pfxbits) - 1;
831 int nbits, i, j, code;
833 tab->table = snewn(1 << bits, struct zlib_tableentry);
834 tab->mask = (1 << bits) - 1;
836 for (code = 0; code <= tab->mask; code++) {
837 tab->table[code].code = -1;
838 tab->table[code].nbits = 0;
839 tab->table[code].nexttable = NULL;
842 for (i = 0; i < nsyms; i++) {
843 if (lengths[i] <= pfxbits || (codes[i] & pfxmask) != pfx)
845 code = (codes[i] >> pfxbits) & tab->mask;
846 for (j = code; j <= tab->mask; j += 1 << (lengths[i] - pfxbits)) {
847 tab->table[j].code = i;
848 nbits = lengths[i] - pfxbits;
849 if (tab->table[j].nbits < nbits)
850 tab->table[j].nbits = nbits;
853 for (code = 0; code <= tab->mask; code++) {
854 if (tab->table[code].nbits <= bits)
856 /* Generate a subtable. */
857 tab->table[code].code = -1;
858 nbits = tab->table[code].nbits - bits;
861 tab->table[code].nbits = bits;
862 tab->table[code].nexttable = zlib_mkonetab(codes, lengths, nsyms,
863 pfx | (code << pfxbits),
864 pfxbits + bits, nbits);
871 * Build a decode table, given a set of Huffman tree lengths.
873 static struct zlib_table *zlib_mktable(unsigned char *lengths,
876 int count[MAXCODELEN], startcode[MAXCODELEN], codes[MAXSYMS];
880 /* Count the codes of each length. */
882 for (i = 1; i < MAXCODELEN; i++)
884 for (i = 0; i < nlengths; i++) {
886 if (maxlen < lengths[i])
889 /* Determine the starting code for each length block. */
891 for (i = 1; i < MAXCODELEN; i++) {
896 /* Determine the code for each symbol. Mirrored, of course. */
897 for (i = 0; i < nlengths; i++) {
898 code = startcode[lengths[i]]++;
900 for (j = 0; j < lengths[i]; j++) {
901 codes[i] = (codes[i] << 1) | (code & 1);
907 * Now we have the complete list of Huffman codes. Build a
910 return zlib_mkonetab(codes, lengths, nlengths, 0, 0,
911 maxlen < 9 ? maxlen : 9);
914 static int zlib_freetable(struct zlib_table **ztab)
916 struct zlib_table *tab;
927 for (code = 0; code <= tab->mask; code++)
928 if (tab->table[code].nexttable != NULL)
929 zlib_freetable(&tab->table[code].nexttable);
940 struct zlib_decompress_ctx {
941 struct zlib_table *staticlentable, *staticdisttable;
942 struct zlib_table *currlentable, *currdisttable, *lenlentable;
945 TREES_HDR, TREES_LENLEN, TREES_LEN, TREES_LENREP,
946 INBLK, GOTLENSYM, GOTLEN, GOTDISTSYM,
947 UNCOMP_LEN, UNCOMP_NLEN, UNCOMP_DATA
949 int sym, hlit, hdist, hclen, lenptr, lenextrabits, lenaddon, len,
952 unsigned char lenlen[19];
953 unsigned char lengths[286 + 32];
956 unsigned char window[WINSIZE];
958 unsigned char *outblk;
962 void *zlib_decompress_init(void)
964 struct zlib_decompress_ctx *dctx = snew(struct zlib_decompress_ctx);
965 unsigned char lengths[288];
967 memset(lengths, 8, 144);
968 memset(lengths + 144, 9, 256 - 144);
969 memset(lengths + 256, 7, 280 - 256);
970 memset(lengths + 280, 8, 288 - 280);
971 dctx->staticlentable = zlib_mktable(lengths, 288);
972 memset(lengths, 5, 32);
973 dctx->staticdisttable = zlib_mktable(lengths, 32);
974 dctx->state = START; /* even before header */
975 dctx->currlentable = dctx->currdisttable = dctx->lenlentable = NULL;
983 void zlib_decompress_cleanup(void *handle)
985 struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
987 if (dctx->currlentable && dctx->currlentable != dctx->staticlentable)
988 zlib_freetable(&dctx->currlentable);
989 if (dctx->currdisttable && dctx->currdisttable != dctx->staticdisttable)
990 zlib_freetable(&dctx->currdisttable);
991 if (dctx->lenlentable)
992 zlib_freetable(&dctx->lenlentable);
993 zlib_freetable(&dctx->staticlentable);
994 zlib_freetable(&dctx->staticdisttable);
998 static int zlib_huflookup(unsigned long *bitsp, int *nbitsp,
999 struct zlib_table *tab)
1001 unsigned long bits = *bitsp;
1002 int nbits = *nbitsp;
1004 struct zlib_tableentry *ent;
1005 ent = &tab->table[bits & tab->mask];
1006 if (ent->nbits > nbits)
1007 return -1; /* not enough data */
1008 bits >>= ent->nbits;
1009 nbits -= ent->nbits;
1010 if (ent->code == -1)
1011 tab = ent->nexttable;
1020 * There was a missing entry in the table, presumably
1021 * due to an invalid Huffman table description, and the
1022 * subsequent data has attempted to use the missing
1023 * entry. Return a decoding failure.
1030 static void zlib_emit_char(struct zlib_decompress_ctx *dctx, int c)
1032 dctx->window[dctx->winpos] = c;
1033 dctx->winpos = (dctx->winpos + 1) & (WINSIZE - 1);
1034 if (dctx->outlen >= dctx->outsize) {
1035 dctx->outsize = dctx->outlen + 512;
1036 dctx->outblk = sresize(dctx->outblk, dctx->outsize, unsigned char);
1038 dctx->outblk[dctx->outlen++] = c;
1041 #define EATBITS(n) ( dctx->nbits -= (n), dctx->bits >>= (n) )
1043 int zlib_decompress_block(void *handle, unsigned char *block, int len,
1044 unsigned char **outblock, int *outlen)
1046 struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
1047 const coderecord *rec;
1048 int code, blktype, rep, dist, nlen, header;
1049 static const unsigned char lenlenmap[] = {
1050 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
1053 dctx->outblk = snewn(256, unsigned char);
1054 dctx->outsize = 256;
1057 while (len > 0 || dctx->nbits > 0) {
1058 while (dctx->nbits < 24 && len > 0) {
1059 dctx->bits |= (*block++) << dctx->nbits;
1063 switch (dctx->state) {
1065 /* Expect 16-bit zlib header. */
1066 if (dctx->nbits < 16)
1067 goto finished; /* done all we can */
1070 * The header is stored as a big-endian 16-bit integer,
1071 * in contrast to the general little-endian policy in
1072 * the rest of the format :-(
1074 header = (((dctx->bits & 0xFF00) >> 8) |
1075 ((dctx->bits & 0x00FF) << 8));
1081 * - bits 8-11 should be 1000 (Deflate/RFC1951)
1082 * - bits 12-15 should be at most 0111 (window size)
1083 * - bit 5 should be zero (no dictionary present)
1084 * - we don't care about bits 6-7 (compression rate)
1085 * - bits 0-4 should be set up to make the whole thing
1086 * a multiple of 31 (checksum).
1088 if ((header & 0x0F00) != 0x0800 ||
1089 (header & 0xF000) > 0x7000 ||
1090 (header & 0x0020) != 0x0000 ||
1094 dctx->state = OUTSIDEBLK;
1097 /* Expect 3-bit block header. */
1098 if (dctx->nbits < 3)
1099 goto finished; /* done all we can */
1101 blktype = dctx->bits & 3;
1104 int to_eat = dctx->nbits & 7;
1105 dctx->state = UNCOMP_LEN;
1106 EATBITS(to_eat); /* align to byte boundary */
1107 } else if (blktype == 1) {
1108 dctx->currlentable = dctx->staticlentable;
1109 dctx->currdisttable = dctx->staticdisttable;
1110 dctx->state = INBLK;
1111 } else if (blktype == 2) {
1112 dctx->state = TREES_HDR;
1117 * Dynamic block header. Five bits of HLIT, five of
1118 * HDIST, four of HCLEN.
1120 if (dctx->nbits < 5 + 5 + 4)
1121 goto finished; /* done all we can */
1122 dctx->hlit = 257 + (dctx->bits & 31);
1124 dctx->hdist = 1 + (dctx->bits & 31);
1126 dctx->hclen = 4 + (dctx->bits & 15);
1129 dctx->state = TREES_LENLEN;
1130 memset(dctx->lenlen, 0, sizeof(dctx->lenlen));
1133 if (dctx->nbits < 3)
1135 while (dctx->lenptr < dctx->hclen && dctx->nbits >= 3) {
1136 dctx->lenlen[lenlenmap[dctx->lenptr++]] =
1137 (unsigned char) (dctx->bits & 7);
1140 if (dctx->lenptr == dctx->hclen) {
1141 dctx->lenlentable = zlib_mktable(dctx->lenlen, 19);
1142 dctx->state = TREES_LEN;
1147 if (dctx->lenptr >= dctx->hlit + dctx->hdist) {
1148 dctx->currlentable = zlib_mktable(dctx->lengths, dctx->hlit);
1149 dctx->currdisttable = zlib_mktable(dctx->lengths + dctx->hlit,
1151 zlib_freetable(&dctx->lenlentable);
1152 dctx->lenlentable = NULL;
1153 dctx->state = INBLK;
1157 zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->lenlentable);
1163 dctx->lengths[dctx->lenptr++] = code;
1165 dctx->lenextrabits = (code == 16 ? 2 : code == 17 ? 3 : 7);
1166 dctx->lenaddon = (code == 18 ? 11 : 3);
1167 dctx->lenrep = (code == 16 && dctx->lenptr > 0 ?
1168 dctx->lengths[dctx->lenptr - 1] : 0);
1169 dctx->state = TREES_LENREP;
1173 if (dctx->nbits < dctx->lenextrabits)
1177 (dctx->bits & ((1 << dctx->lenextrabits) - 1));
1178 EATBITS(dctx->lenextrabits);
1179 while (rep > 0 && dctx->lenptr < dctx->hlit + dctx->hdist) {
1180 dctx->lengths[dctx->lenptr] = dctx->lenrep;
1184 dctx->state = TREES_LEN;
1188 zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->currlentable);
1194 zlib_emit_char(dctx, code);
1195 else if (code == 256) {
1196 dctx->state = OUTSIDEBLK;
1197 if (dctx->currlentable != dctx->staticlentable) {
1198 zlib_freetable(&dctx->currlentable);
1199 dctx->currlentable = NULL;
1201 if (dctx->currdisttable != dctx->staticdisttable) {
1202 zlib_freetable(&dctx->currdisttable);
1203 dctx->currdisttable = NULL;
1205 } else if (code < 286) { /* static tree can give >285; ignore */
1206 dctx->state = GOTLENSYM;
1211 rec = &lencodes[dctx->sym - 257];
1212 if (dctx->nbits < rec->extrabits)
1215 rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
1216 EATBITS(rec->extrabits);
1217 dctx->state = GOTLEN;
1221 zlib_huflookup(&dctx->bits, &dctx->nbits,
1222 dctx->currdisttable);
1227 dctx->state = GOTDISTSYM;
1231 rec = &distcodes[dctx->sym];
1232 if (dctx->nbits < rec->extrabits)
1234 dist = rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
1235 EATBITS(rec->extrabits);
1236 dctx->state = INBLK;
1238 zlib_emit_char(dctx, dctx->window[(dctx->winpos - dist) &
1243 * Uncompressed block. We expect to see a 16-bit LEN.
1245 if (dctx->nbits < 16)
1247 dctx->uncomplen = dctx->bits & 0xFFFF;
1249 dctx->state = UNCOMP_NLEN;
1253 * Uncompressed block. We expect to see a 16-bit NLEN,
1254 * which should be the one's complement of the previous
1257 if (dctx->nbits < 16)
1259 nlen = dctx->bits & 0xFFFF;
1261 if (dctx->uncomplen == 0)
1262 dctx->state = OUTSIDEBLK; /* block is empty */
1264 dctx->state = UNCOMP_DATA;
1267 if (dctx->nbits < 8)
1269 zlib_emit_char(dctx, dctx->bits & 0xFF);
1271 if (--dctx->uncomplen == 0)
1272 dctx->state = OUTSIDEBLK; /* end of uncompressed block */
1278 *outblock = dctx->outblk;
1279 *outlen = dctx->outlen;
1283 sfree(dctx->outblk);
1284 *outblock = dctx->outblk = NULL;
1289 #ifdef ZLIB_STANDALONE
1294 int main(int argc, char **argv)
1296 unsigned char buf[16], *outbuf;
1299 int noheader = FALSE, opts = TRUE;
1300 char *filename = NULL;
1306 if (p[0] == '-' && opts) {
1307 if (!strcmp(p, "-d"))
1309 else if (!strcmp(p, "--"))
1310 opts = FALSE; /* next thing is filename */
1312 fprintf(stderr, "unknown command line option '%s'\n", p);
1315 } else if (!filename) {
1318 fprintf(stderr, "can only handle one filename\n");
1323 handle = zlib_decompress_init();
1327 * Provide missing zlib header if -d was specified.
1329 zlib_decompress_block(handle, "\x78\x9C", 2, &outbuf, &outlen);
1330 assert(outlen == 0);
1334 fp = fopen(filename, "rb");
1340 fprintf(stderr, "unable to open '%s'\n", filename);
1345 ret = fread(buf, 1, sizeof(buf), fp);
1348 zlib_decompress_block(handle, buf, ret, &outbuf, &outlen);
1351 fwrite(outbuf, 1, outlen, stdout);
1354 fprintf(stderr, "decoding error\n");
1359 zlib_decompress_cleanup(handle);
1369 const struct ssh_compress ssh_zlib = {
1372 zlib_compress_cleanup,
1373 zlib_compress_block,
1374 zlib_decompress_init,
1375 zlib_decompress_cleanup,
1376 zlib_decompress_block,
1377 zlib_disable_compression,