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
50 /* ----------------------------------------------------------------------
51 * Basic LZ77 code. This bit is designed modularly, so it could be
52 * ripped out and used in a different LZ77 compressor. Go to it,
56 struct LZ77InternalContext;
58 struct LZ77InternalContext *ictx;
60 void (*literal) (struct LZ77Context * ctx, unsigned char c);
61 void (*match) (struct LZ77Context * ctx, int distance, int len);
65 * Initialise the private fields of an LZ77Context. It's up to the
66 * user to initialise the public fields.
68 static int lz77_init(struct LZ77Context *ctx);
71 * Supply data to be compressed. Will update the private fields of
72 * the LZ77Context, and will call literal() and match() to output.
73 * If `compress' is FALSE, it will never emit a match, but will
74 * instead call literal() for everything.
76 static void lz77_compress(struct LZ77Context *ctx,
77 unsigned char *data, int len, int compress);
80 * Modifiable parameters.
82 #define WINSIZE 32768 /* window size. Must be power of 2! */
83 #define HASHMAX 2039 /* one more than max hash value */
84 #define MAXMATCH 32 /* how many matches we track */
85 #define HASHCHARS 3 /* how many chars make a hash */
88 * This compressor takes a less slapdash approach than the
89 * gzip/zlib one. Rather than allowing our hash chains to fall into
90 * disuse near the far end, we keep them doubly linked so we can
91 * _find_ the far end, and then every time we add a new byte to the
92 * window (thus rolling round by one and removing the previous
93 * byte), we can carefully remove the hash chain entry.
96 #define INVALID -1 /* invalid hash _and_ invalid offset */
98 short next, prev; /* array indices within the window */
103 short first; /* window index of first in chain */
110 struct LZ77InternalContext {
111 struct WindowEntry win[WINSIZE];
112 unsigned char data[WINSIZE];
114 struct HashEntry hashtab[HASHMAX];
115 unsigned char pending[HASHCHARS];
119 static int lz77_hash(unsigned char *data)
121 return (257 * data[0] + 263 * data[1] + 269 * data[2]) % HASHMAX;
124 static int lz77_init(struct LZ77Context *ctx)
126 struct LZ77InternalContext *st;
129 st = snew(struct LZ77InternalContext);
135 for (i = 0; i < WINSIZE; i++)
136 st->win[i].next = st->win[i].prev = st->win[i].hashval = INVALID;
137 for (i = 0; i < HASHMAX; i++)
138 st->hashtab[i].first = INVALID;
146 static void lz77_advance(struct LZ77InternalContext *st,
147 unsigned char c, int hash)
152 * Remove the hash entry at winpos from the tail of its chain,
153 * or empty the chain if it's the only thing on the chain.
155 if (st->win[st->winpos].prev != INVALID) {
156 st->win[st->win[st->winpos].prev].next = INVALID;
157 } else if (st->win[st->winpos].hashval != INVALID) {
158 st->hashtab[st->win[st->winpos].hashval].first = INVALID;
162 * Create a new entry at winpos and add it to the head of its
165 st->win[st->winpos].hashval = hash;
166 st->win[st->winpos].prev = INVALID;
167 off = st->win[st->winpos].next = st->hashtab[hash].first;
168 st->hashtab[hash].first = st->winpos;
170 st->win[off].prev = st->winpos;
171 st->data[st->winpos] = c;
174 * Advance the window pointer.
176 st->winpos = (st->winpos + 1) & (WINSIZE - 1);
179 #define CHARAT(k) ( (k)<0 ? st->data[(st->winpos+k)&(WINSIZE-1)] : data[k] )
181 static void lz77_compress(struct LZ77Context *ctx,
182 unsigned char *data, int len, int compress)
184 struct LZ77InternalContext *st = ctx->ictx;
185 int i, hash, distance, off, nmatch, matchlen, advance;
186 struct Match defermatch, matches[MAXMATCH];
190 * Add any pending characters from last time to the window. (We
191 * might not be able to.)
193 for (i = 0; i < st->npending; i++) {
194 unsigned char foo[HASHCHARS];
196 if (len + st->npending - i < HASHCHARS) {
197 /* Update the pending array. */
198 for (j = i; j < st->npending; j++)
199 st->pending[j - i] = st->pending[j];
202 for (j = 0; j < HASHCHARS; j++)
203 foo[j] = (i + j < st->npending ? st->pending[i + j] :
204 data[i + j - st->npending]);
205 lz77_advance(st, foo[0], lz77_hash(foo));
213 /* Don't even look for a match, if we're not compressing. */
214 if (compress && len >= HASHCHARS) {
216 * Hash the next few characters.
218 hash = lz77_hash(data);
221 * Look the hash up in the corresponding hash chain and see
225 for (off = st->hashtab[hash].first;
226 off != INVALID; off = st->win[off].next) {
227 /* distance = 1 if off == st->winpos-1 */
228 /* distance = WINSIZE if off == st->winpos */
230 WINSIZE - (off + WINSIZE - st->winpos) % WINSIZE;
231 for (i = 0; i < HASHCHARS; i++)
232 if (CHARAT(i) != CHARAT(i - distance))
234 if (i == HASHCHARS) {
235 matches[nmatch].distance = distance;
236 matches[nmatch].len = 3;
237 if (++nmatch >= MAXMATCH)
248 * We've now filled up matches[] with nmatch potential
249 * matches. Follow them down to find the longest. (We
250 * assume here that it's always worth favouring a
251 * longer match over a shorter one.)
253 matchlen = HASHCHARS;
254 while (matchlen < len) {
256 for (i = j = 0; i < nmatch; i++) {
257 if (CHARAT(matchlen) ==
258 CHARAT(matchlen - matches[i].distance)) {
259 matches[j++] = matches[i];
269 * We've now got all the longest matches. We favour the
270 * shorter distances, which means we go with matches[0].
271 * So see if we want to defer it or throw it away.
273 matches[0].len = matchlen;
274 if (defermatch.len > 0) {
275 if (matches[0].len > defermatch.len + 1) {
276 /* We have a better match. Emit the deferred char,
277 * and defer this match. */
278 ctx->literal(ctx, (unsigned char) deferchr);
279 defermatch = matches[0];
283 /* We don't have a better match. Do the deferred one. */
284 ctx->match(ctx, defermatch.distance, defermatch.len);
285 advance = defermatch.len - 1;
289 /* There was no deferred match. Defer this one. */
290 defermatch = matches[0];
296 * We found no matches. Emit the deferred match, if
297 * any; otherwise emit a literal.
299 if (defermatch.len > 0) {
300 ctx->match(ctx, defermatch.distance, defermatch.len);
301 advance = defermatch.len - 1;
304 ctx->literal(ctx, data[0]);
310 * Now advance the position by `advance' characters,
311 * keeping the window and hash chains consistent.
313 while (advance > 0) {
314 if (len >= HASHCHARS) {
315 lz77_advance(st, *data, lz77_hash(data));
317 st->pending[st->npending++] = *data;
326 /* ----------------------------------------------------------------------
327 * Zlib compression. We always use the static Huffman tree option.
328 * Mostly this is because it's hard to scan a block in advance to
329 * work out better trees; dynamic trees are great when you're
330 * compressing a large file under no significant time constraint,
331 * but when you're compressing little bits in real time, things get
334 * I suppose it's possible that I could compute Huffman trees based
335 * on the frequencies in the _previous_ block, as a sort of
336 * heuristic, but I'm not confident that the gain would balance out
337 * having to transmit the trees.
341 unsigned char *outbuf;
343 unsigned long outbits;
349 static void outbits(struct Outbuf *out, unsigned long bits, int nbits)
351 assert(out->noutbits + nbits <= 32);
352 out->outbits |= bits << out->noutbits;
353 out->noutbits += nbits;
354 while (out->noutbits >= 8) {
355 if (out->outlen >= out->outsize) {
356 out->outsize = out->outlen + 64;
357 out->outbuf = sresize(out->outbuf, out->outsize, unsigned char);
359 out->outbuf[out->outlen++] = (unsigned char) (out->outbits & 0xFF);
365 static const unsigned char mirrorbytes[256] = {
366 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
367 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
368 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
369 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
370 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
371 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
372 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
373 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
374 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
375 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
376 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
377 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
378 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
379 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
380 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
381 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
382 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
383 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
384 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
385 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
386 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
387 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
388 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
389 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
390 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
391 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
392 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
393 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
394 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
395 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
396 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
397 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
401 short code, extrabits;
405 static const coderecord lencodes[] = {
437 static const coderecord distcodes[] = {
460 {22, 10, 2049, 3072},
461 {23, 10, 3073, 4096},
462 {24, 11, 4097, 6144},
463 {25, 11, 6145, 8192},
464 {26, 12, 8193, 12288},
465 {27, 12, 12289, 16384},
466 {28, 13, 16385, 24576},
467 {29, 13, 24577, 32768},
470 static void zlib_literal(struct LZ77Context *ectx, unsigned char c)
472 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
474 if (out->comp_disabled) {
476 * We're in an uncompressed block, so just output the byte.
483 /* 0 through 143 are 8 bits long starting at 00110000. */
484 outbits(out, mirrorbytes[0x30 + c], 8);
486 /* 144 through 255 are 9 bits long starting at 110010000. */
487 outbits(out, 1 + 2 * mirrorbytes[0x90 - 144 + c], 9);
491 static void zlib_match(struct LZ77Context *ectx, int distance, int len)
493 const coderecord *d, *l;
495 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
497 assert(!out->comp_disabled);
503 * We can transmit matches of lengths 3 through 258
504 * inclusive. So if len exceeds 258, we must transmit in
505 * several steps, with 258 or less in each step.
507 * Specifically: if len >= 261, we can transmit 258 and be
508 * sure of having at least 3 left for the next step. And if
509 * len <= 258, we can just transmit len. But if len == 259
510 * or 260, we must transmit len-3.
512 thislen = (len > 260 ? 258 : len <= 258 ? len : len - 3);
516 * Binary-search to find which length code we're
520 j = sizeof(lencodes) / sizeof(*lencodes);
524 if (thislen < lencodes[k].min)
526 else if (thislen > lencodes[k].max)
530 break; /* found it! */
535 * Transmit the length code. 256-279 are seven bits
536 * starting at 0000000; 280-287 are eight bits starting at
539 if (l->code <= 279) {
540 outbits(out, mirrorbytes[(l->code - 256) * 2], 7);
542 outbits(out, mirrorbytes[0xc0 - 280 + l->code], 8);
546 * Transmit the extra bits.
549 outbits(out, thislen - l->min, l->extrabits);
552 * Binary-search to find which distance code we're
556 j = sizeof(distcodes) / sizeof(*distcodes);
560 if (distance < distcodes[k].min)
562 else if (distance > distcodes[k].max)
566 break; /* found it! */
571 * Transmit the distance code. Five bits starting at 00000.
573 outbits(out, mirrorbytes[d->code * 8], 5);
576 * Transmit the extra bits.
579 outbits(out, distance - d->min, d->extrabits);
583 void *zlib_compress_init(void)
586 struct LZ77Context *ectx = snew(struct LZ77Context);
589 ectx->literal = zlib_literal;
590 ectx->match = zlib_match;
592 out = snew(struct Outbuf);
593 out->outbits = out->noutbits = 0;
595 out->comp_disabled = FALSE;
596 ectx->userdata = out;
601 void zlib_compress_cleanup(void *handle)
603 struct LZ77Context *ectx = (struct LZ77Context *)handle;
604 sfree(ectx->userdata);
608 * Turn off actual LZ77 analysis for one block, to facilitate
609 * construction of a precise-length IGNORE packet. Returns the
610 * length adjustment (which is only valid for packets < 65536
611 * bytes, but that seems reasonable enough).
613 static int zlib_disable_compression(void *handle)
615 struct LZ77Context *ectx = (struct LZ77Context *)handle;
616 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
619 out->comp_disabled = TRUE;
623 * If this is the first block, we will start by outputting two
624 * header bytes, and then three bits to begin an uncompressed
625 * block. This will cost three bytes (because we will start on
626 * a byte boundary, this is certain).
628 if (out->firstblock) {
632 * Otherwise, we will output seven bits to close the
633 * previous static block, and _then_ three bits to begin an
634 * uncompressed block, and then flush the current byte.
635 * This may cost two bytes or three, depending on noutbits.
637 n += (out->noutbits + 10) / 8;
641 * Now we output four bytes for the length / ~length pair in
642 * the uncompressed block.
649 int zlib_compress_block(void *handle, unsigned char *block, int len,
650 unsigned char **outblock, int *outlen)
652 struct LZ77Context *ectx = (struct LZ77Context *)handle;
653 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
657 out->outlen = out->outsize = 0;
660 * If this is the first block, output the Zlib (RFC1950) header
661 * bytes 78 9C. (Deflate compression, 32K window size, default
664 if (out->firstblock) {
665 outbits(out, 0x9C78, 16);
672 if (out->comp_disabled) {
674 outbits(out, 0, 7); /* close static block */
677 int blen = (len < 65535 ? len : 65535);
680 * Start a Deflate (RFC1951) uncompressed block. We
681 * transmit a zero bit (BFINAL=0), followed by a zero
682 * bit and a one bit (BTYPE=00). Of course these are in
683 * the wrong order (00 0).
688 * Output zero bits to align to a byte boundary.
691 outbits(out, 0, 8 - out->noutbits);
694 * Output the block length, and then its one's
695 * complement. They're little-endian, so all we need to
696 * do is pass them straight to outbits() with bit count
699 outbits(out, blen, 16);
700 outbits(out, blen ^ 0xFFFF, 16);
703 * Do the `compression': we need to pass the data to
704 * lz77_compress so that it will be taken into account
705 * for subsequent (distance,length) pairs. But
706 * lz77_compress is passed FALSE, which means it won't
707 * actually find (or even look for) any matches; so
708 * every character will be passed straight to
709 * zlib_literal which will spot out->comp_disabled and
710 * emit in the uncompressed format.
712 lz77_compress(ectx, block, blen, FALSE);
717 outbits(out, 2, 3); /* open new block */
721 * Start a Deflate (RFC1951) fixed-trees block. We
722 * transmit a zero bit (BFINAL=0), followed by a zero
723 * bit and a one bit (BTYPE=01). Of course these are in
724 * the wrong order (01 0).
730 * Do the compression.
732 lz77_compress(ectx, block, len, TRUE);
735 * End the block (by transmitting code 256, which is
736 * 0000000 in fixed-tree mode), and transmit some empty
737 * blocks to ensure we have emitted the byte containing the
738 * last piece of genuine data. There are three ways we can
741 * - Minimal flush. Output end-of-block and then open a
742 * new static block. This takes 9 bits, which is
743 * guaranteed to flush out the last genuine code in the
744 * closed block; but allegedly zlib can't handle it.
746 * - Zlib partial flush. Output EOB, open and close an
747 * empty static block, and _then_ open the new block.
748 * This is the best zlib can handle.
750 * - Zlib sync flush. Output EOB, then an empty
751 * _uncompressed_ block (000, then sync to byte
752 * boundary, then send bytes 00 00 FF FF). Then open the
755 * For the moment, we will use Zlib partial flush.
757 outbits(out, 0, 7); /* close block */
758 outbits(out, 2, 3 + 7); /* empty static block */
759 outbits(out, 2, 3); /* open new block */
762 out->comp_disabled = FALSE;
764 *outblock = out->outbuf;
765 *outlen = out->outlen;
770 /* ----------------------------------------------------------------------
771 * Zlib decompression. Of course, even though our compressor always
772 * uses static trees, our _decompressor_ has to be capable of
773 * handling dynamic trees if it sees them.
777 * The way we work the Huffman decode is to have a table lookup on
778 * the first N bits of the input stream (in the order they arrive,
779 * of course, i.e. the first bit of the Huffman code is in bit 0).
780 * Each table entry lists the number of bits to consume, plus
781 * either an output code or a pointer to a secondary table.
784 struct zlib_tableentry;
786 struct zlib_tableentry {
789 struct zlib_table *nexttable;
793 int mask; /* mask applied to input bit stream */
794 struct zlib_tableentry *table;
797 #define MAXCODELEN 16
801 * Build a single-level decode table for elements
802 * [minlength,maxlength) of the provided code/length tables, and
803 * recurse to build subtables.
805 static struct zlib_table *zlib_mkonetab(int *codes, unsigned char *lengths,
807 int pfx, int pfxbits, int bits)
809 struct zlib_table *tab = snew(struct zlib_table);
810 int pfxmask = (1 << pfxbits) - 1;
811 int nbits, i, j, code;
813 tab->table = snewn(1 << bits, struct zlib_tableentry);
814 tab->mask = (1 << bits) - 1;
816 for (code = 0; code <= tab->mask; code++) {
817 tab->table[code].code = -1;
818 tab->table[code].nbits = 0;
819 tab->table[code].nexttable = NULL;
822 for (i = 0; i < nsyms; i++) {
823 if (lengths[i] <= pfxbits || (codes[i] & pfxmask) != pfx)
825 code = (codes[i] >> pfxbits) & tab->mask;
826 for (j = code; j <= tab->mask; j += 1 << (lengths[i] - pfxbits)) {
827 tab->table[j].code = i;
828 nbits = lengths[i] - pfxbits;
829 if (tab->table[j].nbits < nbits)
830 tab->table[j].nbits = nbits;
833 for (code = 0; code <= tab->mask; code++) {
834 if (tab->table[code].nbits <= bits)
836 /* Generate a subtable. */
837 tab->table[code].code = -1;
838 nbits = tab->table[code].nbits - bits;
841 tab->table[code].nbits = bits;
842 tab->table[code].nexttable = zlib_mkonetab(codes, lengths, nsyms,
843 pfx | (code << pfxbits),
844 pfxbits + bits, nbits);
851 * Build a decode table, given a set of Huffman tree lengths.
853 static struct zlib_table *zlib_mktable(unsigned char *lengths,
856 int count[MAXCODELEN], startcode[MAXCODELEN], codes[MAXSYMS];
860 /* Count the codes of each length. */
862 for (i = 1; i < MAXCODELEN; i++)
864 for (i = 0; i < nlengths; i++) {
866 if (maxlen < lengths[i])
869 /* Determine the starting code for each length block. */
871 for (i = 1; i < MAXCODELEN; i++) {
876 /* Determine the code for each symbol. Mirrored, of course. */
877 for (i = 0; i < nlengths; i++) {
878 code = startcode[lengths[i]]++;
880 for (j = 0; j < lengths[i]; j++) {
881 codes[i] = (codes[i] << 1) | (code & 1);
887 * Now we have the complete list of Huffman codes. Build a
890 return zlib_mkonetab(codes, lengths, nlengths, 0, 0,
891 maxlen < 9 ? maxlen : 9);
894 static int zlib_freetable(struct zlib_table **ztab)
896 struct zlib_table *tab;
907 for (code = 0; code <= tab->mask; code++)
908 if (tab->table[code].nexttable != NULL)
909 zlib_freetable(&tab->table[code].nexttable);
920 struct zlib_decompress_ctx {
921 struct zlib_table *staticlentable, *staticdisttable;
922 struct zlib_table *currlentable, *currdisttable, *lenlentable;
925 TREES_HDR, TREES_LENLEN, TREES_LEN, TREES_LENREP,
926 INBLK, GOTLENSYM, GOTLEN, GOTDISTSYM,
927 UNCOMP_LEN, UNCOMP_NLEN, UNCOMP_DATA
929 int sym, hlit, hdist, hclen, lenptr, lenextrabits, lenaddon, len,
932 unsigned char lenlen[19];
933 unsigned char lengths[286 + 32];
936 unsigned char window[WINSIZE];
938 unsigned char *outblk;
942 void *zlib_decompress_init(void)
944 struct zlib_decompress_ctx *dctx = snew(struct zlib_decompress_ctx);
945 unsigned char lengths[288];
947 memset(lengths, 8, 144);
948 memset(lengths + 144, 9, 256 - 144);
949 memset(lengths + 256, 7, 280 - 256);
950 memset(lengths + 280, 8, 288 - 280);
951 dctx->staticlentable = zlib_mktable(lengths, 288);
952 memset(lengths, 5, 32);
953 dctx->staticdisttable = zlib_mktable(lengths, 32);
954 dctx->state = START; /* even before header */
955 dctx->currlentable = dctx->currdisttable = dctx->lenlentable = NULL;
963 void zlib_decompress_cleanup(void *handle)
965 struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
967 if (dctx->currlentable && dctx->currlentable != dctx->staticlentable)
968 zlib_freetable(&dctx->currlentable);
969 if (dctx->currdisttable && dctx->currdisttable != dctx->staticdisttable)
970 zlib_freetable(&dctx->currdisttable);
971 if (dctx->lenlentable)
972 zlib_freetable(&dctx->lenlentable);
976 static int zlib_huflookup(unsigned long *bitsp, int *nbitsp,
977 struct zlib_table *tab)
979 unsigned long bits = *bitsp;
982 struct zlib_tableentry *ent;
983 ent = &tab->table[bits & tab->mask];
984 if (ent->nbits > nbits)
985 return -1; /* not enough data */
989 tab = ent->nexttable;
998 * There was a missing entry in the table, presumably
999 * due to an invalid Huffman table description, and the
1000 * subsequent data has attempted to use the missing
1001 * entry. Return a decoding failure.
1008 static void zlib_emit_char(struct zlib_decompress_ctx *dctx, int c)
1010 dctx->window[dctx->winpos] = c;
1011 dctx->winpos = (dctx->winpos + 1) & (WINSIZE - 1);
1012 if (dctx->outlen >= dctx->outsize) {
1013 dctx->outsize = dctx->outlen + 512;
1014 dctx->outblk = sresize(dctx->outblk, dctx->outsize, unsigned char);
1016 dctx->outblk[dctx->outlen++] = c;
1019 #define EATBITS(n) ( dctx->nbits -= (n), dctx->bits >>= (n) )
1021 int zlib_decompress_block(void *handle, unsigned char *block, int len,
1022 unsigned char **outblock, int *outlen)
1024 struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
1025 const coderecord *rec;
1026 int code, blktype, rep, dist, nlen;
1027 static const unsigned char lenlenmap[] = {
1028 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
1031 dctx->outblk = NULL;
1032 dctx->outsize = dctx->outlen = 0;
1034 while (len > 0 || dctx->nbits > 0) {
1035 while (dctx->nbits < 24 && len > 0) {
1036 dctx->bits |= (*block++) << dctx->nbits;
1040 switch (dctx->state) {
1042 /* Expect 16-bit zlib header, which we'll dishonourably ignore. */
1043 if (dctx->nbits < 16)
1044 goto finished; /* done all we can */
1046 dctx->state = OUTSIDEBLK;
1049 /* Expect 3-bit block header. */
1050 if (dctx->nbits < 3)
1051 goto finished; /* done all we can */
1053 blktype = dctx->bits & 3;
1056 int to_eat = dctx->nbits & 7;
1057 dctx->state = UNCOMP_LEN;
1058 EATBITS(to_eat); /* align to byte boundary */
1059 } else if (blktype == 1) {
1060 dctx->currlentable = dctx->staticlentable;
1061 dctx->currdisttable = dctx->staticdisttable;
1062 dctx->state = INBLK;
1063 } else if (blktype == 2) {
1064 dctx->state = TREES_HDR;
1069 * Dynamic block header. Five bits of HLIT, five of
1070 * HDIST, four of HCLEN.
1072 if (dctx->nbits < 5 + 5 + 4)
1073 goto finished; /* done all we can */
1074 dctx->hlit = 257 + (dctx->bits & 31);
1076 dctx->hdist = 1 + (dctx->bits & 31);
1078 dctx->hclen = 4 + (dctx->bits & 15);
1081 dctx->state = TREES_LENLEN;
1082 memset(dctx->lenlen, 0, sizeof(dctx->lenlen));
1085 if (dctx->nbits < 3)
1087 while (dctx->lenptr < dctx->hclen && dctx->nbits >= 3) {
1088 dctx->lenlen[lenlenmap[dctx->lenptr++]] =
1089 (unsigned char) (dctx->bits & 7);
1092 if (dctx->lenptr == dctx->hclen) {
1093 dctx->lenlentable = zlib_mktable(dctx->lenlen, 19);
1094 dctx->state = TREES_LEN;
1099 if (dctx->lenptr >= dctx->hlit + dctx->hdist) {
1100 dctx->currlentable = zlib_mktable(dctx->lengths, dctx->hlit);
1101 dctx->currdisttable = zlib_mktable(dctx->lengths + dctx->hlit,
1103 zlib_freetable(&dctx->lenlentable);
1104 dctx->lenlentable = NULL;
1105 dctx->state = INBLK;
1109 zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->lenlentable);
1115 dctx->lengths[dctx->lenptr++] = code;
1117 dctx->lenextrabits = (code == 16 ? 2 : code == 17 ? 3 : 7);
1118 dctx->lenaddon = (code == 18 ? 11 : 3);
1119 dctx->lenrep = (code == 16 && dctx->lenptr > 0 ?
1120 dctx->lengths[dctx->lenptr - 1] : 0);
1121 dctx->state = TREES_LENREP;
1125 if (dctx->nbits < dctx->lenextrabits)
1129 (dctx->bits & ((1 << dctx->lenextrabits) - 1));
1130 EATBITS(dctx->lenextrabits);
1131 while (rep > 0 && dctx->lenptr < dctx->hlit + dctx->hdist) {
1132 dctx->lengths[dctx->lenptr] = dctx->lenrep;
1136 dctx->state = TREES_LEN;
1140 zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->currlentable);
1146 zlib_emit_char(dctx, code);
1147 else if (code == 256) {
1148 dctx->state = OUTSIDEBLK;
1149 if (dctx->currlentable != dctx->staticlentable) {
1150 zlib_freetable(&dctx->currlentable);
1151 dctx->currlentable = NULL;
1153 if (dctx->currdisttable != dctx->staticdisttable) {
1154 zlib_freetable(&dctx->currdisttable);
1155 dctx->currdisttable = NULL;
1157 } else if (code < 286) { /* static tree can give >285; ignore */
1158 dctx->state = GOTLENSYM;
1163 rec = &lencodes[dctx->sym - 257];
1164 if (dctx->nbits < rec->extrabits)
1167 rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
1168 EATBITS(rec->extrabits);
1169 dctx->state = GOTLEN;
1173 zlib_huflookup(&dctx->bits, &dctx->nbits,
1174 dctx->currdisttable);
1179 dctx->state = GOTDISTSYM;
1183 rec = &distcodes[dctx->sym];
1184 if (dctx->nbits < rec->extrabits)
1186 dist = rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
1187 EATBITS(rec->extrabits);
1188 dctx->state = INBLK;
1190 zlib_emit_char(dctx, dctx->window[(dctx->winpos - dist) &
1195 * Uncompressed block. We expect to see a 16-bit LEN.
1197 if (dctx->nbits < 16)
1199 dctx->uncomplen = dctx->bits & 0xFFFF;
1201 dctx->state = UNCOMP_NLEN;
1205 * Uncompressed block. We expect to see a 16-bit NLEN,
1206 * which should be the one's complement of the previous
1209 if (dctx->nbits < 16)
1211 nlen = dctx->bits & 0xFFFF;
1213 if (dctx->uncomplen == 0)
1214 dctx->state = OUTSIDEBLK; /* block is empty */
1216 dctx->state = UNCOMP_DATA;
1219 if (dctx->nbits < 8)
1221 zlib_emit_char(dctx, dctx->bits & 0xFF);
1223 if (--dctx->uncomplen == 0)
1224 dctx->state = OUTSIDEBLK; /* end of uncompressed block */
1230 *outblock = dctx->outblk;
1231 *outlen = dctx->outlen;
1235 sfree(dctx->outblk);
1236 *outblock = dctx->outblk = NULL;
1241 const struct ssh_compress ssh_zlib = {
1244 zlib_compress_cleanup,
1245 zlib_compress_block,
1246 zlib_decompress_init,
1247 zlib_decompress_cleanup,
1248 zlib_decompress_block,
1249 zlib_disable_compression,