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) {
120 return (257*data[0] + 263*data[1] + 269*data[2]) % HASHMAX;
123 static int lz77_init(struct LZ77Context *ctx) {
124 struct LZ77InternalContext *st;
127 st = (struct LZ77InternalContext *)smalloc(sizeof(*st));
133 for (i = 0; i < WINSIZE; i++)
134 st->win[i].next = st->win[i].prev = st->win[i].hashval = INVALID;
135 for (i = 0; i < HASHMAX; i++)
136 st->hashtab[i].first = INVALID;
144 static void lz77_advance(struct LZ77InternalContext *st,
145 unsigned char c, int hash) {
149 * Remove the hash entry at winpos from the tail of its chain,
150 * or empty the chain if it's the only thing on the chain.
152 if (st->win[st->winpos].prev != INVALID) {
153 st->win[st->win[st->winpos].prev].next = INVALID;
154 } else if (st->win[st->winpos].hashval != INVALID) {
155 st->hashtab[st->win[st->winpos].hashval].first = INVALID;
159 * Create a new entry at winpos and add it to the head of its
162 st->win[st->winpos].hashval = hash;
163 st->win[st->winpos].prev = INVALID;
164 off = st->win[st->winpos].next = st->hashtab[hash].first;
165 st->hashtab[hash].first = st->winpos;
167 st->win[off].prev = st->winpos;
168 st->data[st->winpos] = c;
171 * Advance the window pointer.
173 st->winpos = (st->winpos + 1) & (WINSIZE-1);
176 #define CHARAT(k) ( (k)<0 ? st->data[(st->winpos+k)&(WINSIZE-1)] : data[k] )
178 static void lz77_compress(struct LZ77Context *ctx,
179 unsigned char *data, int len, int compress) {
180 struct LZ77InternalContext *st = ctx->ictx;
181 int i, hash, distance, off, nmatch, matchlen, advance;
182 struct Match defermatch, matches[MAXMATCH];
186 * Add any pending characters from last time to the window. (We
187 * might not be able to.)
189 for (i = 0; i < st->npending; i++) {
190 unsigned char foo[HASHCHARS];
192 if (len + st->npending - i < HASHCHARS) {
193 /* Update the pending array. */
194 for (j = i; j < st->npending; j++)
195 st->pending[j-i] = st->pending[j];
198 for (j = 0; j < HASHCHARS; j++)
199 foo[j] = (i + j < st->npending ? st->pending[i+j] :
200 data[i + j - st->npending]);
201 lz77_advance(st, foo[0], lz77_hash(foo));
208 /* Don't even look for a match, if we're not compressing. */
209 if (compress && len >= HASHCHARS) {
211 * Hash the next few characters.
213 hash = lz77_hash(data);
216 * Look the hash up in the corresponding hash chain and see
220 for (off = st->hashtab[hash].first;
221 off != INVALID; off = st->win[off].next) {
222 /* distance = 1 if off == st->winpos-1 */
223 /* distance = WINSIZE if off == st->winpos */
224 distance = WINSIZE - (off + WINSIZE - st->winpos) % WINSIZE;
225 for (i = 0; i < HASHCHARS; i++)
226 if (CHARAT(i) != CHARAT(i-distance))
228 if (i == HASHCHARS) {
229 matches[nmatch].distance = distance;
230 matches[nmatch].len = 3;
231 if (++nmatch >= MAXMATCH)
242 * We've now filled up matches[] with nmatch potential
243 * matches. Follow them down to find the longest. (We
244 * assume here that it's always worth favouring a
245 * longer match over a shorter one.)
247 matchlen = HASHCHARS;
248 while (matchlen < len) {
250 for (i = j = 0; i < nmatch; i++) {
251 if (CHARAT(matchlen) ==
252 CHARAT(matchlen - matches[i].distance)) {
253 matches[j++] = matches[i];
263 * We've now got all the longest matches. We favour the
264 * shorter distances, which means we go with matches[0].
265 * So see if we want to defer it or throw it away.
267 matches[0].len = matchlen;
268 if (defermatch.len > 0) {
269 if (matches[0].len > defermatch.len + 1) {
270 /* We have a better match. Emit the deferred char,
271 * and defer this match. */
272 ctx->literal(ctx, (unsigned char)deferchr);
273 defermatch = matches[0];
277 /* We don't have a better match. Do the deferred one. */
278 ctx->match(ctx, defermatch.distance, defermatch.len);
279 advance = defermatch.len - 1;
283 /* There was no deferred match. Defer this one. */
284 defermatch = matches[0];
290 * We found no matches. Emit the deferred match, if
291 * any; otherwise emit a literal.
293 if (defermatch.len > 0) {
294 ctx->match(ctx, defermatch.distance, defermatch.len);
295 advance = defermatch.len - 1;
298 ctx->literal(ctx, data[0]);
304 * Now advance the position by `advance' characters,
305 * keeping the window and hash chains consistent.
307 while (advance > 0) {
308 if (len >= HASHCHARS) {
309 lz77_advance(st, *data, lz77_hash(data));
311 st->pending[st->npending++] = *data;
320 /* ----------------------------------------------------------------------
321 * Zlib compression. We always use the static Huffman tree option.
322 * Mostly this is because it's hard to scan a block in advance to
323 * work out better trees; dynamic trees are great when you're
324 * compressing a large file under no significant time constraint,
325 * but when you're compressing little bits in real time, things get
328 * I suppose it's possible that I could compute Huffman trees based
329 * on the frequencies in the _previous_ block, as a sort of
330 * heuristic, but I'm not confident that the gain would balance out
331 * having to transmit the trees.
334 static struct LZ77Context ectx;
337 unsigned char *outbuf;
339 unsigned long outbits;
345 static void outbits(struct Outbuf *out, unsigned long bits, int nbits) {
346 assert(out->noutbits + nbits <= 32);
347 out->outbits |= bits << out->noutbits;
348 out->noutbits += nbits;
349 while (out->noutbits >= 8) {
350 if (out->outlen >= out->outsize) {
351 out->outsize = out->outlen + 64;
352 out->outbuf = srealloc(out->outbuf, out->outsize);
354 out->outbuf[out->outlen++] = (unsigned char)(out->outbits & 0xFF);
360 static const unsigned char mirrorbytes[256] = {
361 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
362 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
363 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
364 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
365 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
366 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
367 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
368 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
369 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
370 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
371 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
372 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
373 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
374 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
375 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
376 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
377 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
378 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
379 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
380 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
381 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
382 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
383 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
384 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
385 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
386 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
387 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
388 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
389 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
390 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
391 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
392 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
396 short code, extrabits;
400 static const coderecord lencodes[] = {
432 static const coderecord distcodes[] = {
459 {26, 12, 8193,12288},
460 {27, 12, 12289,16384},
461 {28, 13, 16385,24576},
462 {29, 13, 24577,32768},
465 static void zlib_literal(struct LZ77Context *ectx, unsigned char c) {
466 struct Outbuf *out = (struct Outbuf *)ectx->userdata;
468 if (out->comp_disabled) {
470 * We're in an uncompressed block, so just output the byte.
477 /* 0 through 143 are 8 bits long starting at 00110000. */
478 outbits(out, mirrorbytes[0x30 + c], 8);
480 /* 144 through 255 are 9 bits long starting at 110010000. */
481 outbits(out, 1 + 2*mirrorbytes[0x90 - 144 + c], 9);
485 static void zlib_match(struct LZ77Context *ectx, int distance, int len) {
486 const coderecord *d, *l;
488 struct Outbuf *out = (struct Outbuf *)ectx->userdata;
490 assert(!out->comp_disabled);
496 * We can transmit matches of lengths 3 through 258
497 * inclusive. So if len exceeds 258, we must transmit in
498 * several steps, with 258 or less in each step.
500 * Specifically: if len >= 261, we can transmit 258 and be
501 * sure of having at least 3 left for the next step. And if
502 * len <= 258, we can just transmit len. But if len == 259
503 * or 260, we must transmit len-3.
505 thislen = (len > 260 ? 258 : len <= 258 ? len : len-3);
509 * Binary-search to find which length code we're
512 i = -1; j = sizeof(lencodes)/sizeof(*lencodes);
515 if (thislen < lencodes[k].min)
517 else if (thislen > lencodes[k].max)
521 break; /* found it! */
526 * Transmit the length code. 256-279 are seven bits
527 * starting at 0000000; 280-287 are eight bits starting at
530 if (l->code <= 279) {
531 outbits(out, mirrorbytes[(l->code-256)*2], 7);
533 outbits(out, mirrorbytes[0xc0 - 280 + l->code], 8);
537 * Transmit the extra bits.
540 outbits(out, thislen - l->min, l->extrabits);
543 * Binary-search to find which distance code we're
546 i = -1; j = sizeof(distcodes)/sizeof(*distcodes);
549 if (distance < distcodes[k].min)
551 else if (distance > distcodes[k].max)
555 break; /* found it! */
560 * Transmit the distance code. Five bits starting at 00000.
562 outbits(out, mirrorbytes[d->code*8], 5);
565 * Transmit the extra bits.
568 outbits(out, distance - d->min, d->extrabits);
572 void zlib_compress_init(void) {
576 ectx.literal = zlib_literal;
577 ectx.match = zlib_match;
579 out = smalloc(sizeof(struct Outbuf));
580 out->outbits = out->noutbits = 0;
582 out->comp_disabled = FALSE;
585 logevent("Initialised zlib (RFC1950) compression");
589 * Turn off actual LZ77 analysis for one block, to facilitate
590 * construction of a precise-length IGNORE packet. Returns the
591 * length adjustment (which is only valid for packets < 65536
592 * bytes, but that seems reasonable enough).
594 int zlib_disable_compression(void) {
595 struct Outbuf *out = (struct Outbuf *)ectx.userdata;
598 out->comp_disabled = TRUE;
602 * If this is the first block, we will start by outputting two
603 * header bytes, and then three bits to begin an uncompressed
604 * block. This will cost three bytes (because we will start on
605 * a byte boundary, this is certain).
607 if (out->firstblock) {
611 * Otherwise, we will output seven bits to close the
612 * previous static block, and _then_ three bits to begin an
613 * uncompressed block, and then flush the current byte.
614 * This may cost two bytes or three, depending on noutbits.
616 n += (out->noutbits + 10) / 8;
620 * Now we output four bytes for the length / ~length pair in
621 * the uncompressed block.
628 int zlib_compress_block(unsigned char *block, int len,
629 unsigned char **outblock, int *outlen) {
630 struct Outbuf *out = (struct Outbuf *)ectx.userdata;
634 out->outlen = out->outsize = 0;
637 * If this is the first block, output the Zlib (RFC1950) header
638 * bytes 78 9C. (Deflate compression, 32K window size, default
641 if (out->firstblock) {
642 outbits(out, 0x9C78, 16);
648 if (out->comp_disabled) {
650 outbits(out, 0, 7); /* close static block */
653 int blen = (len < 65535 ? len : 65535);
656 * Start a Deflate (RFC1951) uncompressed block. We
657 * transmit a zero bit (BFINAL=0), followed by a zero
658 * bit and a one bit (BTYPE=00). Of course these are in
659 * the wrong order (00 0).
664 * Output zero bits to align to a byte boundary.
667 outbits(out, 0, 8 - out->noutbits);
670 * Output the block length, and then its one's
671 * complement. They're little-endian, so all we need to
672 * do is pass them straight to outbits() with bit count
675 outbits(out, blen, 16);
676 outbits(out, blen ^ 0xFFFF, 16);
679 * Do the `compression': we need to pass the data to
680 * lz77_compress so that it will be taken into account
681 * for subsequent (distance,length) pairs. But
682 * lz77_compress is passed FALSE, which means it won't
683 * actually find (or even look for) any matches; so
684 * every character will be passed straight to
685 * zlib_literal which will spot out->comp_disabled and
686 * emit in the uncompressed format.
688 lz77_compress(&ectx, block, blen, FALSE);
693 outbits(out, 2, 3); /* open new block */
697 * Start a Deflate (RFC1951) fixed-trees block. We
698 * transmit a zero bit (BFINAL=0), followed by a zero
699 * bit and a one bit (BTYPE=01). Of course these are in
700 * the wrong order (01 0).
706 * Do the compression.
708 lz77_compress(&ectx, block, len, TRUE);
711 * End the block (by transmitting code 256, which is
712 * 0000000 in fixed-tree mode), and transmit some empty
713 * blocks to ensure we have emitted the byte containing the
714 * last piece of genuine data. There are three ways we can
717 * - Minimal flush. Output end-of-block and then open a
718 * new static block. This takes 9 bits, which is
719 * guaranteed to flush out the last genuine code in the
720 * closed block; but allegedly zlib can't handle it.
722 * - Zlib partial flush. Output EOB, open and close an
723 * empty static block, and _then_ open the new block.
724 * This is the best zlib can handle.
726 * - Zlib sync flush. Output EOB, then an empty
727 * _uncompressed_ block (000, then sync to byte
728 * boundary, then send bytes 00 00 FF FF). Then open the
731 * For the moment, we will use Zlib partial flush.
733 outbits(out, 0, 7); /* close block */
734 outbits(out, 2, 3+7); /* empty static block */
735 outbits(out, 2, 3); /* open new block */
738 out->comp_disabled = FALSE;
740 *outblock = out->outbuf;
741 *outlen = out->outlen;
746 /* ----------------------------------------------------------------------
747 * Zlib decompression. Of course, even though our compressor always
748 * uses static trees, our _decompressor_ has to be capable of
749 * handling dynamic trees if it sees them.
753 * The way we work the Huffman decode is to have a table lookup on
754 * the first N bits of the input stream (in the order they arrive,
755 * of course, i.e. the first bit of the Huffman code is in bit 0).
756 * Each table entry lists the number of bits to consume, plus
757 * either an output code or a pointer to a secondary table.
760 struct zlib_tableentry;
762 struct zlib_tableentry {
765 struct zlib_table *nexttable;
769 int mask; /* mask applied to input bit stream */
770 struct zlib_tableentry *table;
773 #define MAXCODELEN 16
777 * Build a single-level decode table for elements
778 * [minlength,maxlength) of the provided code/length tables, and
779 * recurse to build subtables.
781 static struct zlib_table *zlib_mkonetab(int *codes, unsigned char *lengths,
783 int pfx, int pfxbits, int bits) {
784 struct zlib_table *tab = smalloc(sizeof(struct zlib_table));
785 int pfxmask = (1 << pfxbits) - 1;
786 int nbits, i, j, code;
788 tab->table = smalloc((1 << bits) * sizeof(struct zlib_tableentry));
789 tab->mask = (1 << bits) - 1;
791 for (code = 0; code <= tab->mask; code++) {
792 tab->table[code].code = -1;
793 tab->table[code].nbits = 0;
794 tab->table[code].nexttable = NULL;
797 for (i = 0; i < nsyms; i++) {
798 if (lengths[i] <= pfxbits || (codes[i] & pfxmask) != pfx)
800 code = (codes[i] >> pfxbits) & tab->mask;
801 for (j = code; j <= tab->mask; j += 1 << (lengths[i]-pfxbits)) {
802 tab->table[j].code = i;
803 nbits = lengths[i] - pfxbits;
804 if (tab->table[j].nbits < nbits)
805 tab->table[j].nbits = nbits;
808 for (code = 0; code <= tab->mask; code++) {
809 if (tab->table[code].nbits <= bits)
811 /* Generate a subtable. */
812 tab->table[code].code = -1;
813 nbits = tab->table[code].nbits - bits;
816 tab->table[code].nbits = bits;
817 tab->table[code].nexttable = zlib_mkonetab(codes, lengths, nsyms,
818 pfx | (code << pfxbits),
819 pfxbits + bits, nbits);
826 * Build a decode table, given a set of Huffman tree lengths.
828 static struct zlib_table *zlib_mktable(unsigned char *lengths, int nlengths) {
829 int count[MAXCODELEN], startcode[MAXCODELEN], codes[MAXSYMS];
833 /* Count the codes of each length. */
835 for (i = 1; i < MAXCODELEN; i++) count[i] = 0;
836 for (i = 0; i < nlengths; i++) {
838 if (maxlen < lengths[i])
841 /* Determine the starting code for each length block. */
843 for (i = 1; i < MAXCODELEN; i++) {
848 /* Determine the code for each symbol. Mirrored, of course. */
849 for (i = 0; i < nlengths; i++) {
850 code = startcode[lengths[i]]++;
852 for (j = 0; j < lengths[i]; j++) {
853 codes[i] = (codes[i] << 1) | (code & 1);
859 * Now we have the complete list of Huffman codes. Build a
862 return zlib_mkonetab(codes, lengths, nlengths, 0, 0,
863 maxlen < 9 ? maxlen : 9);
866 static int zlib_freetable(struct zlib_table ** ztab) {
867 struct zlib_table *tab;
878 for (code = 0; code <= tab->mask; code++)
879 if (tab->table[code].nexttable != NULL)
880 zlib_freetable(&tab->table[code].nexttable);
891 static struct zlib_decompress_ctx {
892 struct zlib_table *staticlentable, *staticdisttable;
893 struct zlib_table *currlentable, *currdisttable, *lenlentable;
896 TREES_HDR, TREES_LENLEN, TREES_LEN, TREES_LENREP,
897 INBLK, GOTLENSYM, GOTLEN, GOTDISTSYM,
898 UNCOMP_LEN, UNCOMP_NLEN, UNCOMP_DATA
900 int sym, hlit, hdist, hclen, lenptr, lenextrabits, lenaddon, len, lenrep;
902 unsigned char lenlen[19];
903 unsigned char lengths[286+32];
906 unsigned char window[WINSIZE];
908 unsigned char *outblk;
912 void zlib_decompress_init(void) {
913 unsigned char lengths[288];
914 memset(lengths, 8, 144);
915 memset(lengths+144, 9, 256-144);
916 memset(lengths+256, 7, 280-256);
917 memset(lengths+280, 8, 288-280);
918 dctx.staticlentable = zlib_mktable(lengths, 288);
919 memset(lengths, 5, 32);
920 dctx.staticdisttable = zlib_mktable(lengths, 32);
921 dctx.state = START; /* even before header */
922 dctx.currlentable = dctx.currdisttable = dctx.lenlentable = NULL;
925 logevent("Initialised zlib (RFC1950) decompression");
928 int zlib_huflookup(unsigned long *bitsp, int *nbitsp, struct zlib_table *tab) {
929 unsigned long bits = *bitsp;
932 struct zlib_tableentry *ent;
933 ent = &tab->table[bits & tab->mask];
934 if (ent->nbits > nbits)
935 return -1; /* not enough data */
939 tab = ent->nexttable;
948 static void zlib_emit_char(int c) {
949 dctx.window[dctx.winpos] = c;
950 dctx.winpos = (dctx.winpos + 1) & (WINSIZE-1);
951 if (dctx.outlen >= dctx.outsize) {
952 dctx.outsize = dctx.outlen + 512;
953 dctx.outblk = srealloc(dctx.outblk, dctx.outsize);
955 dctx.outblk[dctx.outlen++] = c;
958 #define EATBITS(n) ( dctx.nbits -= (n), dctx.bits >>= (n) )
960 int zlib_decompress_block(unsigned char *block, int len,
961 unsigned char **outblock, int *outlen) {
962 const coderecord *rec;
963 int code, blktype, rep, dist, nlen;
964 static const unsigned char lenlenmap[] = {
965 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
969 dctx.outsize = dctx.outlen = 0;
971 while (len > 0 || dctx.nbits > 0) {
972 while (dctx.nbits < 24 && len > 0) {
973 dctx.bits |= (*block++) << dctx.nbits;
977 switch (dctx.state) {
979 /* Expect 16-bit zlib header, which we'll dishonourably ignore. */
981 goto finished; /* done all we can */
983 dctx.state = OUTSIDEBLK;
986 /* Expect 3-bit block header. */
988 goto finished; /* done all we can */
990 blktype = dctx.bits & 3;
993 int to_eat = dctx.nbits & 7;
994 dctx.state = UNCOMP_LEN;
995 EATBITS(to_eat); /* align to byte boundary */
996 } else if (blktype == 1) {
997 dctx.currlentable = dctx.staticlentable;
998 dctx.currdisttable = dctx.staticdisttable;
1000 } else if (blktype == 2) {
1001 dctx.state = TREES_HDR;
1006 * Dynamic block header. Five bits of HLIT, five of
1007 * HDIST, four of HCLEN.
1009 if (dctx.nbits < 5+5+4)
1010 goto finished; /* done all we can */
1011 dctx.hlit = 257 + (dctx.bits & 31); EATBITS(5);
1012 dctx.hdist = 1 + (dctx.bits & 31); EATBITS(5);
1013 dctx.hclen = 4 + (dctx.bits & 15); EATBITS(4);
1015 dctx.state = TREES_LENLEN;
1016 memset(dctx.lenlen, 0, sizeof(dctx.lenlen));
1021 while (dctx.lenptr < dctx.hclen && dctx.nbits >= 3) {
1022 dctx.lenlen[lenlenmap[dctx.lenptr++]] =
1023 (unsigned char)(dctx.bits & 7);
1026 if (dctx.lenptr == dctx.hclen) {
1027 dctx.lenlentable = zlib_mktable(dctx.lenlen, 19);
1028 dctx.state = TREES_LEN;
1033 if (dctx.lenptr >= dctx.hlit+dctx.hdist) {
1034 dctx.currlentable = zlib_mktable(dctx.lengths, dctx.hlit);
1035 dctx.currdisttable = zlib_mktable(dctx.lengths + dctx.hlit,
1037 zlib_freetable(&dctx.lenlentable);
1041 code = zlib_huflookup(&dctx.bits, &dctx.nbits, dctx.lenlentable);
1045 dctx.lengths[dctx.lenptr++] = code;
1047 dctx.lenextrabits = (code == 16 ? 2 : code == 17 ? 3 : 7);
1048 dctx.lenaddon = (code == 18 ? 11 : 3);
1049 dctx.lenrep = (code == 16 && dctx.lenptr > 0 ?
1050 dctx.lengths[dctx.lenptr-1] : 0);
1051 dctx.state = TREES_LENREP;
1055 if (dctx.nbits < dctx.lenextrabits)
1057 rep = dctx.lenaddon + (dctx.bits & ((1<<dctx.lenextrabits)-1));
1058 EATBITS(dctx.lenextrabits);
1059 while (rep > 0 && dctx.lenptr < dctx.hlit+dctx.hdist) {
1060 dctx.lengths[dctx.lenptr] = dctx.lenrep;
1064 dctx.state = TREES_LEN;
1067 code = zlib_huflookup(&dctx.bits, &dctx.nbits, dctx.currlentable);
1071 zlib_emit_char(code);
1072 else if (code == 256) {
1073 dctx.state = OUTSIDEBLK;
1074 if (dctx.currlentable != dctx.staticlentable)
1075 zlib_freetable(&dctx.currlentable);
1076 if (dctx.currdisttable != dctx.staticdisttable)
1077 zlib_freetable(&dctx.currdisttable);
1078 } else if (code < 286) { /* static tree can give >285; ignore */
1079 dctx.state = GOTLENSYM;
1084 rec = &lencodes[dctx.sym - 257];
1085 if (dctx.nbits < rec->extrabits)
1087 dctx.len = rec->min + (dctx.bits & ((1<<rec->extrabits)-1));
1088 EATBITS(rec->extrabits);
1089 dctx.state = GOTLEN;
1092 code = zlib_huflookup(&dctx.bits, &dctx.nbits, dctx.currdisttable);
1095 dctx.state = GOTDISTSYM;
1099 rec = &distcodes[dctx.sym];
1100 if (dctx.nbits < rec->extrabits)
1102 dist = rec->min + (dctx.bits & ((1<<rec->extrabits)-1));
1103 EATBITS(rec->extrabits);
1106 zlib_emit_char(dctx.window[(dctx.winpos-dist) & (WINSIZE-1)]);
1110 * Uncompressed block. We expect to see a 16-bit LEN.
1112 if (dctx.nbits < 16)
1114 dctx.uncomplen = dctx.bits & 0xFFFF;
1116 dctx.state = UNCOMP_NLEN;
1120 * Uncompressed block. We expect to see a 16-bit NLEN,
1121 * which should be the one's complement of the previous
1124 if (dctx.nbits < 16)
1126 nlen = dctx.bits & 0xFFFF;
1128 dctx.state = UNCOMP_DATA;
1133 zlib_emit_char(dctx.bits & 0xFF);
1135 if (--dctx.uncomplen == 0)
1136 dctx.state = OUTSIDEBLK; /* end of uncompressed block */
1142 *outblock = dctx.outblk;
1143 *outlen = dctx.outlen;
1148 const struct ssh_compress ssh_zlib = {
1151 zlib_compress_block,
1152 zlib_decompress_init,
1153 zlib_decompress_block,
1154 zlib_disable_compression