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 = (struct LZ77InternalContext *) smalloc(sizeof(*st));
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));
212 /* Don't even look for a match, if we're not compressing. */
213 if (compress && len >= HASHCHARS) {
215 * Hash the next few characters.
217 hash = lz77_hash(data);
220 * Look the hash up in the corresponding hash chain and see
224 for (off = st->hashtab[hash].first;
225 off != INVALID; off = st->win[off].next) {
226 /* distance = 1 if off == st->winpos-1 */
227 /* distance = WINSIZE if off == st->winpos */
229 WINSIZE - (off + WINSIZE - st->winpos) % WINSIZE;
230 for (i = 0; i < HASHCHARS; i++)
231 if (CHARAT(i) != CHARAT(i - distance))
233 if (i == HASHCHARS) {
234 matches[nmatch].distance = distance;
235 matches[nmatch].len = 3;
236 if (++nmatch >= MAXMATCH)
247 * We've now filled up matches[] with nmatch potential
248 * matches. Follow them down to find the longest. (We
249 * assume here that it's always worth favouring a
250 * longer match over a shorter one.)
252 matchlen = HASHCHARS;
253 while (matchlen < len) {
255 for (i = j = 0; i < nmatch; i++) {
256 if (CHARAT(matchlen) ==
257 CHARAT(matchlen - matches[i].distance)) {
258 matches[j++] = matches[i];
268 * We've now got all the longest matches. We favour the
269 * shorter distances, which means we go with matches[0].
270 * So see if we want to defer it or throw it away.
272 matches[0].len = matchlen;
273 if (defermatch.len > 0) {
274 if (matches[0].len > defermatch.len + 1) {
275 /* We have a better match. Emit the deferred char,
276 * and defer this match. */
277 ctx->literal(ctx, (unsigned char) deferchr);
278 defermatch = matches[0];
282 /* We don't have a better match. Do the deferred one. */
283 ctx->match(ctx, defermatch.distance, defermatch.len);
284 advance = defermatch.len - 1;
288 /* There was no deferred match. Defer this one. */
289 defermatch = matches[0];
295 * We found no matches. Emit the deferred match, if
296 * any; otherwise emit a literal.
298 if (defermatch.len > 0) {
299 ctx->match(ctx, defermatch.distance, defermatch.len);
300 advance = defermatch.len - 1;
303 ctx->literal(ctx, data[0]);
309 * Now advance the position by `advance' characters,
310 * keeping the window and hash chains consistent.
312 while (advance > 0) {
313 if (len >= HASHCHARS) {
314 lz77_advance(st, *data, lz77_hash(data));
316 st->pending[st->npending++] = *data;
325 /* ----------------------------------------------------------------------
326 * Zlib compression. We always use the static Huffman tree option.
327 * Mostly this is because it's hard to scan a block in advance to
328 * work out better trees; dynamic trees are great when you're
329 * compressing a large file under no significant time constraint,
330 * but when you're compressing little bits in real time, things get
333 * I suppose it's possible that I could compute Huffman trees based
334 * on the frequencies in the _previous_ block, as a sort of
335 * heuristic, but I'm not confident that the gain would balance out
336 * having to transmit the trees.
339 static struct LZ77Context ectx;
342 unsigned char *outbuf;
344 unsigned long outbits;
350 static void outbits(struct Outbuf *out, unsigned long bits, int nbits)
352 assert(out->noutbits + nbits <= 32);
353 out->outbits |= bits << out->noutbits;
354 out->noutbits += nbits;
355 while (out->noutbits >= 8) {
356 if (out->outlen >= out->outsize) {
357 out->outsize = out->outlen + 64;
358 out->outbuf = srealloc(out->outbuf, out->outsize);
360 out->outbuf[out->outlen++] = (unsigned char) (out->outbits & 0xFF);
366 static const unsigned char mirrorbytes[256] = {
367 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
368 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
369 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
370 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
371 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
372 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
373 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
374 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
375 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
376 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
377 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
378 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
379 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
380 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
381 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
382 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
383 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
384 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
385 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
386 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
387 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
388 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
389 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
390 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
391 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
392 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
393 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
394 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
395 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
396 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
397 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
398 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
402 short code, extrabits;
406 static const coderecord lencodes[] = {
438 static const coderecord distcodes[] = {
461 {22, 10, 2049, 3072},
462 {23, 10, 3073, 4096},
463 {24, 11, 4097, 6144},
464 {25, 11, 6145, 8192},
465 {26, 12, 8193, 12288},
466 {27, 12, 12289, 16384},
467 {28, 13, 16385, 24576},
468 {29, 13, 24577, 32768},
471 static void zlib_literal(struct LZ77Context *ectx, unsigned char c)
473 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
475 if (out->comp_disabled) {
477 * We're in an uncompressed block, so just output the byte.
484 /* 0 through 143 are 8 bits long starting at 00110000. */
485 outbits(out, mirrorbytes[0x30 + c], 8);
487 /* 144 through 255 are 9 bits long starting at 110010000. */
488 outbits(out, 1 + 2 * mirrorbytes[0x90 - 144 + c], 9);
492 static void zlib_match(struct LZ77Context *ectx, int distance, int len)
494 const coderecord *d, *l;
496 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
498 assert(!out->comp_disabled);
504 * We can transmit matches of lengths 3 through 258
505 * inclusive. So if len exceeds 258, we must transmit in
506 * several steps, with 258 or less in each step.
508 * Specifically: if len >= 261, we can transmit 258 and be
509 * sure of having at least 3 left for the next step. And if
510 * len <= 258, we can just transmit len. But if len == 259
511 * or 260, we must transmit len-3.
513 thislen = (len > 260 ? 258 : len <= 258 ? len : len - 3);
517 * Binary-search to find which length code we're
521 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);
559 if (distance < distcodes[k].min)
561 else if (distance > distcodes[k].max)
565 break; /* found it! */
570 * Transmit the distance code. Five bits starting at 00000.
572 outbits(out, mirrorbytes[d->code * 8], 5);
575 * Transmit the extra bits.
578 outbits(out, distance - d->min, d->extrabits);
582 void zlib_compress_init(void)
587 ectx.literal = zlib_literal;
588 ectx.match = zlib_match;
590 out = smalloc(sizeof(struct Outbuf));
591 out->outbits = out->noutbits = 0;
593 out->comp_disabled = FALSE;
596 logevent("Initialised zlib (RFC1950) compression");
600 * Turn off actual LZ77 analysis for one block, to facilitate
601 * construction of a precise-length IGNORE packet. Returns the
602 * length adjustment (which is only valid for packets < 65536
603 * bytes, but that seems reasonable enough).
605 int zlib_disable_compression(void)
607 struct Outbuf *out = (struct Outbuf *) ectx.userdata;
610 out->comp_disabled = TRUE;
614 * If this is the first block, we will start by outputting two
615 * header bytes, and then three bits to begin an uncompressed
616 * block. This will cost three bytes (because we will start on
617 * a byte boundary, this is certain).
619 if (out->firstblock) {
623 * Otherwise, we will output seven bits to close the
624 * previous static block, and _then_ three bits to begin an
625 * uncompressed block, and then flush the current byte.
626 * This may cost two bytes or three, depending on noutbits.
628 n += (out->noutbits + 10) / 8;
632 * Now we output four bytes for the length / ~length pair in
633 * the uncompressed block.
640 int zlib_compress_block(unsigned char *block, int len,
641 unsigned char **outblock, int *outlen)
643 struct Outbuf *out = (struct Outbuf *) ectx.userdata;
647 out->outlen = out->outsize = 0;
650 * If this is the first block, output the Zlib (RFC1950) header
651 * bytes 78 9C. (Deflate compression, 32K window size, default
654 if (out->firstblock) {
655 outbits(out, 0x9C78, 16);
661 if (out->comp_disabled) {
663 outbits(out, 0, 7); /* close static block */
666 int blen = (len < 65535 ? len : 65535);
669 * Start a Deflate (RFC1951) uncompressed block. We
670 * transmit a zero bit (BFINAL=0), followed by a zero
671 * bit and a one bit (BTYPE=00). Of course these are in
672 * the wrong order (00 0).
677 * Output zero bits to align to a byte boundary.
680 outbits(out, 0, 8 - out->noutbits);
683 * Output the block length, and then its one's
684 * complement. They're little-endian, so all we need to
685 * do is pass them straight to outbits() with bit count
688 outbits(out, blen, 16);
689 outbits(out, blen ^ 0xFFFF, 16);
692 * Do the `compression': we need to pass the data to
693 * lz77_compress so that it will be taken into account
694 * for subsequent (distance,length) pairs. But
695 * lz77_compress is passed FALSE, which means it won't
696 * actually find (or even look for) any matches; so
697 * every character will be passed straight to
698 * zlib_literal which will spot out->comp_disabled and
699 * emit in the uncompressed format.
701 lz77_compress(&ectx, block, blen, FALSE);
706 outbits(out, 2, 3); /* open new block */
710 * Start a Deflate (RFC1951) fixed-trees block. We
711 * transmit a zero bit (BFINAL=0), followed by a zero
712 * bit and a one bit (BTYPE=01). Of course these are in
713 * the wrong order (01 0).
719 * Do the compression.
721 lz77_compress(&ectx, block, len, TRUE);
724 * End the block (by transmitting code 256, which is
725 * 0000000 in fixed-tree mode), and transmit some empty
726 * blocks to ensure we have emitted the byte containing the
727 * last piece of genuine data. There are three ways we can
730 * - Minimal flush. Output end-of-block and then open a
731 * new static block. This takes 9 bits, which is
732 * guaranteed to flush out the last genuine code in the
733 * closed block; but allegedly zlib can't handle it.
735 * - Zlib partial flush. Output EOB, open and close an
736 * empty static block, and _then_ open the new block.
737 * This is the best zlib can handle.
739 * - Zlib sync flush. Output EOB, then an empty
740 * _uncompressed_ block (000, then sync to byte
741 * boundary, then send bytes 00 00 FF FF). Then open the
744 * For the moment, we will use Zlib partial flush.
746 outbits(out, 0, 7); /* close block */
747 outbits(out, 2, 3 + 7); /* empty static block */
748 outbits(out, 2, 3); /* open new block */
751 out->comp_disabled = FALSE;
753 *outblock = out->outbuf;
754 *outlen = out->outlen;
759 /* ----------------------------------------------------------------------
760 * Zlib decompression. Of course, even though our compressor always
761 * uses static trees, our _decompressor_ has to be capable of
762 * handling dynamic trees if it sees them.
766 * The way we work the Huffman decode is to have a table lookup on
767 * the first N bits of the input stream (in the order they arrive,
768 * of course, i.e. the first bit of the Huffman code is in bit 0).
769 * Each table entry lists the number of bits to consume, plus
770 * either an output code or a pointer to a secondary table.
773 struct zlib_tableentry;
775 struct zlib_tableentry {
778 struct zlib_table *nexttable;
782 int mask; /* mask applied to input bit stream */
783 struct zlib_tableentry *table;
786 #define MAXCODELEN 16
790 * Build a single-level decode table for elements
791 * [minlength,maxlength) of the provided code/length tables, and
792 * recurse to build subtables.
794 static struct zlib_table *zlib_mkonetab(int *codes, unsigned char *lengths,
796 int pfx, int pfxbits, int bits)
798 struct zlib_table *tab = smalloc(sizeof(struct zlib_table));
799 int pfxmask = (1 << pfxbits) - 1;
800 int nbits, i, j, code;
802 tab->table = smalloc((1 << bits) * sizeof(struct zlib_tableentry));
803 tab->mask = (1 << bits) - 1;
805 for (code = 0; code <= tab->mask; code++) {
806 tab->table[code].code = -1;
807 tab->table[code].nbits = 0;
808 tab->table[code].nexttable = NULL;
811 for (i = 0; i < nsyms; i++) {
812 if (lengths[i] <= pfxbits || (codes[i] & pfxmask) != pfx)
814 code = (codes[i] >> pfxbits) & tab->mask;
815 for (j = code; j <= tab->mask; j += 1 << (lengths[i] - pfxbits)) {
816 tab->table[j].code = i;
817 nbits = lengths[i] - pfxbits;
818 if (tab->table[j].nbits < nbits)
819 tab->table[j].nbits = nbits;
822 for (code = 0; code <= tab->mask; code++) {
823 if (tab->table[code].nbits <= bits)
825 /* Generate a subtable. */
826 tab->table[code].code = -1;
827 nbits = tab->table[code].nbits - bits;
830 tab->table[code].nbits = bits;
831 tab->table[code].nexttable = zlib_mkonetab(codes, lengths, nsyms,
832 pfx | (code << pfxbits),
833 pfxbits + bits, nbits);
840 * Build a decode table, given a set of Huffman tree lengths.
842 static struct zlib_table *zlib_mktable(unsigned char *lengths,
845 int count[MAXCODELEN], startcode[MAXCODELEN], codes[MAXSYMS];
849 /* Count the codes of each length. */
851 for (i = 1; i < MAXCODELEN; i++)
853 for (i = 0; i < nlengths; i++) {
855 if (maxlen < lengths[i])
858 /* Determine the starting code for each length block. */
860 for (i = 1; i < MAXCODELEN; i++) {
865 /* Determine the code for each symbol. Mirrored, of course. */
866 for (i = 0; i < nlengths; i++) {
867 code = startcode[lengths[i]]++;
869 for (j = 0; j < lengths[i]; j++) {
870 codes[i] = (codes[i] << 1) | (code & 1);
876 * Now we have the complete list of Huffman codes. Build a
879 return zlib_mkonetab(codes, lengths, nlengths, 0, 0,
880 maxlen < 9 ? maxlen : 9);
883 static int zlib_freetable(struct zlib_table **ztab)
885 struct zlib_table *tab;
896 for (code = 0; code <= tab->mask; code++)
897 if (tab->table[code].nexttable != NULL)
898 zlib_freetable(&tab->table[code].nexttable);
909 static struct zlib_decompress_ctx {
910 struct zlib_table *staticlentable, *staticdisttable;
911 struct zlib_table *currlentable, *currdisttable, *lenlentable;
914 TREES_HDR, TREES_LENLEN, TREES_LEN, TREES_LENREP,
915 INBLK, GOTLENSYM, GOTLEN, GOTDISTSYM,
916 UNCOMP_LEN, UNCOMP_NLEN, UNCOMP_DATA
918 int sym, hlit, hdist, hclen, lenptr, lenextrabits, lenaddon, len,
921 unsigned char lenlen[19];
922 unsigned char lengths[286 + 32];
925 unsigned char window[WINSIZE];
927 unsigned char *outblk;
931 void zlib_decompress_init(void)
933 unsigned char lengths[288];
934 memset(lengths, 8, 144);
935 memset(lengths + 144, 9, 256 - 144);
936 memset(lengths + 256, 7, 280 - 256);
937 memset(lengths + 280, 8, 288 - 280);
938 dctx.staticlentable = zlib_mktable(lengths, 288);
939 memset(lengths, 5, 32);
940 dctx.staticdisttable = zlib_mktable(lengths, 32);
941 dctx.state = START; /* even before header */
942 dctx.currlentable = dctx.currdisttable = dctx.lenlentable = NULL;
945 logevent("Initialised zlib (RFC1950) decompression");
948 int zlib_huflookup(unsigned long *bitsp, int *nbitsp,
949 struct zlib_table *tab)
951 unsigned long bits = *bitsp;
954 struct zlib_tableentry *ent;
955 ent = &tab->table[bits & tab->mask];
956 if (ent->nbits > nbits)
957 return -1; /* not enough data */
961 tab = ent->nexttable;
970 static void zlib_emit_char(int c)
972 dctx.window[dctx.winpos] = c;
973 dctx.winpos = (dctx.winpos + 1) & (WINSIZE - 1);
974 if (dctx.outlen >= dctx.outsize) {
975 dctx.outsize = dctx.outlen + 512;
976 dctx.outblk = srealloc(dctx.outblk, dctx.outsize);
978 dctx.outblk[dctx.outlen++] = c;
981 #define EATBITS(n) ( dctx.nbits -= (n), dctx.bits >>= (n) )
983 int zlib_decompress_block(unsigned char *block, int len,
984 unsigned char **outblock, int *outlen)
986 const coderecord *rec;
987 int code, blktype, rep, dist, nlen;
988 static const unsigned char lenlenmap[] = {
989 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
993 dctx.outsize = dctx.outlen = 0;
995 while (len > 0 || dctx.nbits > 0) {
996 while (dctx.nbits < 24 && len > 0) {
997 dctx.bits |= (*block++) << dctx.nbits;
1001 switch (dctx.state) {
1003 /* Expect 16-bit zlib header, which we'll dishonourably ignore. */
1004 if (dctx.nbits < 16)
1005 goto finished; /* done all we can */
1007 dctx.state = OUTSIDEBLK;
1010 /* Expect 3-bit block header. */
1012 goto finished; /* done all we can */
1014 blktype = dctx.bits & 3;
1017 int to_eat = dctx.nbits & 7;
1018 dctx.state = UNCOMP_LEN;
1019 EATBITS(to_eat); /* align to byte boundary */
1020 } else if (blktype == 1) {
1021 dctx.currlentable = dctx.staticlentable;
1022 dctx.currdisttable = dctx.staticdisttable;
1024 } else if (blktype == 2) {
1025 dctx.state = TREES_HDR;
1030 * Dynamic block header. Five bits of HLIT, five of
1031 * HDIST, four of HCLEN.
1033 if (dctx.nbits < 5 + 5 + 4)
1034 goto finished; /* done all we can */
1035 dctx.hlit = 257 + (dctx.bits & 31);
1037 dctx.hdist = 1 + (dctx.bits & 31);
1039 dctx.hclen = 4 + (dctx.bits & 15);
1042 dctx.state = TREES_LENLEN;
1043 memset(dctx.lenlen, 0, sizeof(dctx.lenlen));
1048 while (dctx.lenptr < dctx.hclen && dctx.nbits >= 3) {
1049 dctx.lenlen[lenlenmap[dctx.lenptr++]] =
1050 (unsigned char) (dctx.bits & 7);
1053 if (dctx.lenptr == dctx.hclen) {
1054 dctx.lenlentable = zlib_mktable(dctx.lenlen, 19);
1055 dctx.state = TREES_LEN;
1060 if (dctx.lenptr >= dctx.hlit + dctx.hdist) {
1061 dctx.currlentable = zlib_mktable(dctx.lengths, dctx.hlit);
1062 dctx.currdisttable = zlib_mktable(dctx.lengths + dctx.hlit,
1064 zlib_freetable(&dctx.lenlentable);
1069 zlib_huflookup(&dctx.bits, &dctx.nbits, dctx.lenlentable);
1073 dctx.lengths[dctx.lenptr++] = code;
1075 dctx.lenextrabits = (code == 16 ? 2 : code == 17 ? 3 : 7);
1076 dctx.lenaddon = (code == 18 ? 11 : 3);
1077 dctx.lenrep = (code == 16 && dctx.lenptr > 0 ?
1078 dctx.lengths[dctx.lenptr - 1] : 0);
1079 dctx.state = TREES_LENREP;
1083 if (dctx.nbits < dctx.lenextrabits)
1087 (dctx.bits & ((1 << dctx.lenextrabits) - 1));
1088 EATBITS(dctx.lenextrabits);
1089 while (rep > 0 && dctx.lenptr < dctx.hlit + dctx.hdist) {
1090 dctx.lengths[dctx.lenptr] = dctx.lenrep;
1094 dctx.state = TREES_LEN;
1098 zlib_huflookup(&dctx.bits, &dctx.nbits, dctx.currlentable);
1102 zlib_emit_char(code);
1103 else if (code == 256) {
1104 dctx.state = OUTSIDEBLK;
1105 if (dctx.currlentable != dctx.staticlentable)
1106 zlib_freetable(&dctx.currlentable);
1107 if (dctx.currdisttable != dctx.staticdisttable)
1108 zlib_freetable(&dctx.currdisttable);
1109 } else if (code < 286) { /* static tree can give >285; ignore */
1110 dctx.state = GOTLENSYM;
1115 rec = &lencodes[dctx.sym - 257];
1116 if (dctx.nbits < rec->extrabits)
1119 rec->min + (dctx.bits & ((1 << rec->extrabits) - 1));
1120 EATBITS(rec->extrabits);
1121 dctx.state = GOTLEN;
1125 zlib_huflookup(&dctx.bits, &dctx.nbits,
1126 dctx.currdisttable);
1129 dctx.state = GOTDISTSYM;
1133 rec = &distcodes[dctx.sym];
1134 if (dctx.nbits < rec->extrabits)
1136 dist = rec->min + (dctx.bits & ((1 << rec->extrabits) - 1));
1137 EATBITS(rec->extrabits);
1140 zlib_emit_char(dctx.window[(dctx.winpos - dist) &
1145 * Uncompressed block. We expect to see a 16-bit LEN.
1147 if (dctx.nbits < 16)
1149 dctx.uncomplen = dctx.bits & 0xFFFF;
1151 dctx.state = UNCOMP_NLEN;
1155 * Uncompressed block. We expect to see a 16-bit NLEN,
1156 * which should be the one's complement of the previous
1159 if (dctx.nbits < 16)
1161 nlen = dctx.bits & 0xFFFF;
1163 dctx.state = UNCOMP_DATA;
1168 zlib_emit_char(dctx.bits & 0xFF);
1170 if (--dctx.uncomplen == 0)
1171 dctx.state = OUTSIDEBLK; /* end of uncompressed block */
1177 *outblock = dctx.outblk;
1178 *outlen = dctx.outlen;
1183 const struct ssh_compress ssh_zlib = {
1186 zlib_compress_block,
1187 zlib_decompress_init,
1188 zlib_decompress_block,
1189 zlib_disable_compression