2 * Zlib (RFC1950 / RFC1951) compression for PuTTY.
\r
4 * There will no doubt be criticism of my decision to reimplement
\r
5 * Zlib compression from scratch instead of using the existing zlib
\r
6 * code. People will cry `reinventing the wheel'; they'll claim
\r
7 * that the `fundamental basis of OSS' is code reuse; they'll want
\r
8 * to see a really good reason for me having chosen not to use the
\r
11 * Well, here are my reasons. Firstly, I don't want to link the
\r
12 * whole of zlib into the PuTTY binary; PuTTY is justifiably proud
\r
13 * of its small size and I think zlib contains a lot of unnecessary
\r
14 * baggage for the kind of compression that SSH requires.
\r
16 * Secondly, I also don't like the alternative of using zlib.dll.
\r
17 * Another thing PuTTY is justifiably proud of is its ease of
\r
18 * installation, and the last thing I want to do is to start
\r
19 * mandating DLLs. Not only that, but there are two _kinds_ of
\r
20 * zlib.dll kicking around, one with C calling conventions on the
\r
21 * exported functions and another with WINAPI conventions, and
\r
22 * there would be a significant danger of getting the wrong one.
\r
24 * Thirdly, there seems to be a difference of opinion on the IETF
\r
25 * secsh mailing list about the correct way to round off a
\r
26 * compressed packet and start the next. In particular, there's
\r
27 * some talk of switching to a mechanism zlib isn't currently
\r
28 * capable of supporting (see below for an explanation). Given that
\r
29 * sort of uncertainty, I thought it might be better to have code
\r
30 * that will support even the zlib-incompatible worst case.
\r
32 * Fourthly, it's a _second implementation_. Second implementations
\r
33 * are fundamentally a Good Thing in standardisation efforts. The
\r
34 * difference of opinion mentioned above has arisen _precisely_
\r
35 * because there has been only one zlib implementation and
\r
36 * everybody has used it. I don't intend that this should happen
\r
44 #ifdef ZLIB_STANDALONE
\r
47 * This module also makes a handy zlib decoding tool for when
\r
48 * you're picking apart Zip files or PDFs or PNGs. If you compile
\r
49 * it with ZLIB_STANDALONE defined, it builds on its own and
\r
50 * becomes a command-line utility.
\r
52 * Therefore, here I provide a self-contained implementation of the
\r
53 * macros required from the rest of the PuTTY sources.
\r
55 #define snew(type) ( (type *) malloc(sizeof(type)) )
\r
56 #define snewn(n, type) ( (type *) malloc((n) * sizeof(type)) )
\r
57 #define sresize(x, n, type) ( (type *) realloc((x), (n) * sizeof(type)) )
\r
58 #define sfree(x) ( free((x)) )
\r
66 #define TRUE (!FALSE)
\r
69 /* ----------------------------------------------------------------------
\r
70 * Basic LZ77 code. This bit is designed modularly, so it could be
\r
71 * ripped out and used in a different LZ77 compressor. Go to it,
\r
75 struct LZ77InternalContext;
\r
76 struct LZ77Context {
\r
77 struct LZ77InternalContext *ictx;
\r
79 void (*literal) (struct LZ77Context * ctx, unsigned char c);
\r
80 void (*match) (struct LZ77Context * ctx, int distance, int len);
\r
84 * Initialise the private fields of an LZ77Context. It's up to the
\r
85 * user to initialise the public fields.
\r
87 static int lz77_init(struct LZ77Context *ctx);
\r
90 * Supply data to be compressed. Will update the private fields of
\r
91 * the LZ77Context, and will call literal() and match() to output.
\r
92 * If `compress' is FALSE, it will never emit a match, but will
\r
93 * instead call literal() for everything.
\r
95 static void lz77_compress(struct LZ77Context *ctx,
\r
96 unsigned char *data, int len, int compress);
\r
99 * Modifiable parameters.
\r
101 #define WINSIZE 32768 /* window size. Must be power of 2! */
\r
102 #define HASHMAX 2039 /* one more than max hash value */
\r
103 #define MAXMATCH 32 /* how many matches we track */
\r
104 #define HASHCHARS 3 /* how many chars make a hash */
\r
107 * This compressor takes a less slapdash approach than the
\r
108 * gzip/zlib one. Rather than allowing our hash chains to fall into
\r
109 * disuse near the far end, we keep them doubly linked so we can
\r
110 * _find_ the far end, and then every time we add a new byte to the
\r
111 * window (thus rolling round by one and removing the previous
\r
112 * byte), we can carefully remove the hash chain entry.
\r
115 #define INVALID -1 /* invalid hash _and_ invalid offset */
\r
116 struct WindowEntry {
\r
117 short next, prev; /* array indices within the window */
\r
122 short first; /* window index of first in chain */
\r
129 struct LZ77InternalContext {
\r
130 struct WindowEntry win[WINSIZE];
\r
131 unsigned char data[WINSIZE];
\r
133 struct HashEntry hashtab[HASHMAX];
\r
134 unsigned char pending[HASHCHARS];
\r
138 static int lz77_hash(unsigned char *data)
\r
140 return (257 * data[0] + 263 * data[1] + 269 * data[2]) % HASHMAX;
\r
143 static int lz77_init(struct LZ77Context *ctx)
\r
145 struct LZ77InternalContext *st;
\r
148 st = snew(struct LZ77InternalContext);
\r
154 for (i = 0; i < WINSIZE; i++)
\r
155 st->win[i].next = st->win[i].prev = st->win[i].hashval = INVALID;
\r
156 for (i = 0; i < HASHMAX; i++)
\r
157 st->hashtab[i].first = INVALID;
\r
165 static void lz77_advance(struct LZ77InternalContext *st,
\r
166 unsigned char c, int hash)
\r
171 * Remove the hash entry at winpos from the tail of its chain,
\r
172 * or empty the chain if it's the only thing on the chain.
\r
174 if (st->win[st->winpos].prev != INVALID) {
\r
175 st->win[st->win[st->winpos].prev].next = INVALID;
\r
176 } else if (st->win[st->winpos].hashval != INVALID) {
\r
177 st->hashtab[st->win[st->winpos].hashval].first = INVALID;
\r
181 * Create a new entry at winpos and add it to the head of its
\r
184 st->win[st->winpos].hashval = hash;
\r
185 st->win[st->winpos].prev = INVALID;
\r
186 off = st->win[st->winpos].next = st->hashtab[hash].first;
\r
187 st->hashtab[hash].first = st->winpos;
\r
188 if (off != INVALID)
\r
189 st->win[off].prev = st->winpos;
\r
190 st->data[st->winpos] = c;
\r
193 * Advance the window pointer.
\r
195 st->winpos = (st->winpos + 1) & (WINSIZE - 1);
\r
198 #define CHARAT(k) ( (k)<0 ? st->data[(st->winpos+k)&(WINSIZE-1)] : data[k] )
\r
200 static void lz77_compress(struct LZ77Context *ctx,
\r
201 unsigned char *data, int len, int compress)
\r
203 struct LZ77InternalContext *st = ctx->ictx;
\r
204 int i, hash, distance, off, nmatch, matchlen, advance;
\r
205 struct Match defermatch, matches[MAXMATCH];
\r
209 * Add any pending characters from last time to the window. (We
\r
210 * might not be able to.)
\r
212 for (i = 0; i < st->npending; i++) {
\r
213 unsigned char foo[HASHCHARS];
\r
215 if (len + st->npending - i < HASHCHARS) {
\r
216 /* Update the pending array. */
\r
217 for (j = i; j < st->npending; j++)
\r
218 st->pending[j - i] = st->pending[j];
\r
221 for (j = 0; j < HASHCHARS; j++)
\r
222 foo[j] = (i + j < st->npending ? st->pending[i + j] :
\r
223 data[i + j - st->npending]);
\r
224 lz77_advance(st, foo[0], lz77_hash(foo));
\r
228 defermatch.distance = 0; /* appease compiler */
\r
229 defermatch.len = 0;
\r
233 /* Don't even look for a match, if we're not compressing. */
\r
234 if (compress && len >= HASHCHARS) {
\r
236 * Hash the next few characters.
\r
238 hash = lz77_hash(data);
\r
241 * Look the hash up in the corresponding hash chain and see
\r
242 * what we can find.
\r
245 for (off = st->hashtab[hash].first;
\r
246 off != INVALID; off = st->win[off].next) {
\r
247 /* distance = 1 if off == st->winpos-1 */
\r
248 /* distance = WINSIZE if off == st->winpos */
\r
250 WINSIZE - (off + WINSIZE - st->winpos) % WINSIZE;
\r
251 for (i = 0; i < HASHCHARS; i++)
\r
252 if (CHARAT(i) != CHARAT(i - distance))
\r
254 if (i == HASHCHARS) {
\r
255 matches[nmatch].distance = distance;
\r
256 matches[nmatch].len = 3;
\r
257 if (++nmatch >= MAXMATCH)
\r
268 * We've now filled up matches[] with nmatch potential
\r
269 * matches. Follow them down to find the longest. (We
\r
270 * assume here that it's always worth favouring a
\r
271 * longer match over a shorter one.)
\r
273 matchlen = HASHCHARS;
\r
274 while (matchlen < len) {
\r
276 for (i = j = 0; i < nmatch; i++) {
\r
277 if (CHARAT(matchlen) ==
\r
278 CHARAT(matchlen - matches[i].distance)) {
\r
279 matches[j++] = matches[i];
\r
289 * We've now got all the longest matches. We favour the
\r
290 * shorter distances, which means we go with matches[0].
\r
291 * So see if we want to defer it or throw it away.
\r
293 matches[0].len = matchlen;
\r
294 if (defermatch.len > 0) {
\r
295 if (matches[0].len > defermatch.len + 1) {
\r
296 /* We have a better match. Emit the deferred char,
\r
297 * and defer this match. */
\r
298 ctx->literal(ctx, (unsigned char) deferchr);
\r
299 defermatch = matches[0];
\r
300 deferchr = data[0];
\r
303 /* We don't have a better match. Do the deferred one. */
\r
304 ctx->match(ctx, defermatch.distance, defermatch.len);
\r
305 advance = defermatch.len - 1;
\r
306 defermatch.len = 0;
\r
309 /* There was no deferred match. Defer this one. */
\r
310 defermatch = matches[0];
\r
311 deferchr = data[0];
\r
316 * We found no matches. Emit the deferred match, if
\r
317 * any; otherwise emit a literal.
\r
319 if (defermatch.len > 0) {
\r
320 ctx->match(ctx, defermatch.distance, defermatch.len);
\r
321 advance = defermatch.len - 1;
\r
322 defermatch.len = 0;
\r
324 ctx->literal(ctx, data[0]);
\r
330 * Now advance the position by `advance' characters,
\r
331 * keeping the window and hash chains consistent.
\r
333 while (advance > 0) {
\r
334 if (len >= HASHCHARS) {
\r
335 lz77_advance(st, *data, lz77_hash(data));
\r
337 st->pending[st->npending++] = *data;
\r
346 /* ----------------------------------------------------------------------
\r
347 * Zlib compression. We always use the static Huffman tree option.
\r
348 * Mostly this is because it's hard to scan a block in advance to
\r
349 * work out better trees; dynamic trees are great when you're
\r
350 * compressing a large file under no significant time constraint,
\r
351 * but when you're compressing little bits in real time, things get
\r
354 * I suppose it's possible that I could compute Huffman trees based
\r
355 * on the frequencies in the _previous_ block, as a sort of
\r
356 * heuristic, but I'm not confident that the gain would balance out
\r
357 * having to transmit the trees.
\r
361 unsigned char *outbuf;
\r
362 int outlen, outsize;
\r
363 unsigned long outbits;
\r
369 static void outbits(struct Outbuf *out, unsigned long bits, int nbits)
\r
371 assert(out->noutbits + nbits <= 32);
\r
372 out->outbits |= bits << out->noutbits;
\r
373 out->noutbits += nbits;
\r
374 while (out->noutbits >= 8) {
\r
375 if (out->outlen >= out->outsize) {
\r
376 out->outsize = out->outlen + 64;
\r
377 out->outbuf = sresize(out->outbuf, out->outsize, unsigned char);
\r
379 out->outbuf[out->outlen++] = (unsigned char) (out->outbits & 0xFF);
\r
380 out->outbits >>= 8;
\r
381 out->noutbits -= 8;
\r
385 static const unsigned char mirrorbytes[256] = {
\r
386 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
\r
387 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
\r
388 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
\r
389 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
\r
390 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
\r
391 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
\r
392 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
\r
393 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
\r
394 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
\r
395 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
\r
396 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
\r
397 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
\r
398 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
\r
399 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
\r
400 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
\r
401 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
\r
402 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
\r
403 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
\r
404 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
\r
405 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
\r
406 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
\r
407 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
\r
408 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
\r
409 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
\r
410 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
\r
411 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
\r
412 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
\r
413 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
\r
414 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
\r
415 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
\r
416 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
\r
417 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
\r
421 short code, extrabits;
\r
425 static const coderecord lencodes[] = {
\r
449 {280, 4, 115, 130},
\r
450 {281, 5, 131, 162},
\r
451 {282, 5, 163, 194},
\r
452 {283, 5, 195, 226},
\r
453 {284, 5, 227, 257},
\r
454 {285, 0, 258, 258},
\r
457 static const coderecord distcodes[] = {
\r
477 {19, 8, 769, 1024},
\r
478 {20, 9, 1025, 1536},
\r
479 {21, 9, 1537, 2048},
\r
480 {22, 10, 2049, 3072},
\r
481 {23, 10, 3073, 4096},
\r
482 {24, 11, 4097, 6144},
\r
483 {25, 11, 6145, 8192},
\r
484 {26, 12, 8193, 12288},
\r
485 {27, 12, 12289, 16384},
\r
486 {28, 13, 16385, 24576},
\r
487 {29, 13, 24577, 32768},
\r
490 static void zlib_literal(struct LZ77Context *ectx, unsigned char c)
\r
492 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
\r
494 if (out->comp_disabled) {
\r
496 * We're in an uncompressed block, so just output the byte.
\r
498 outbits(out, c, 8);
\r
503 /* 0 through 143 are 8 bits long starting at 00110000. */
\r
504 outbits(out, mirrorbytes[0x30 + c], 8);
\r
506 /* 144 through 255 are 9 bits long starting at 110010000. */
\r
507 outbits(out, 1 + 2 * mirrorbytes[0x90 - 144 + c], 9);
\r
511 static void zlib_match(struct LZ77Context *ectx, int distance, int len)
\r
513 const coderecord *d, *l;
\r
515 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
\r
517 assert(!out->comp_disabled);
\r
523 * We can transmit matches of lengths 3 through 258
\r
524 * inclusive. So if len exceeds 258, we must transmit in
\r
525 * several steps, with 258 or less in each step.
\r
527 * Specifically: if len >= 261, we can transmit 258 and be
\r
528 * sure of having at least 3 left for the next step. And if
\r
529 * len <= 258, we can just transmit len. But if len == 259
\r
530 * or 260, we must transmit len-3.
\r
532 thislen = (len > 260 ? 258 : len <= 258 ? len : len - 3);
\r
536 * Binary-search to find which length code we're
\r
540 j = sizeof(lencodes) / sizeof(*lencodes);
\r
542 assert(j - i >= 2);
\r
544 if (thislen < lencodes[k].min)
\r
546 else if (thislen > lencodes[k].max)
\r
550 break; /* found it! */
\r
555 * Transmit the length code. 256-279 are seven bits
\r
556 * starting at 0000000; 280-287 are eight bits starting at
\r
559 if (l->code <= 279) {
\r
560 outbits(out, mirrorbytes[(l->code - 256) * 2], 7);
\r
562 outbits(out, mirrorbytes[0xc0 - 280 + l->code], 8);
\r
566 * Transmit the extra bits.
\r
569 outbits(out, thislen - l->min, l->extrabits);
\r
572 * Binary-search to find which distance code we're
\r
576 j = sizeof(distcodes) / sizeof(*distcodes);
\r
578 assert(j - i >= 2);
\r
580 if (distance < distcodes[k].min)
\r
582 else if (distance > distcodes[k].max)
\r
586 break; /* found it! */
\r
591 * Transmit the distance code. Five bits starting at 00000.
\r
593 outbits(out, mirrorbytes[d->code * 8], 5);
\r
596 * Transmit the extra bits.
\r
599 outbits(out, distance - d->min, d->extrabits);
\r
603 void *zlib_compress_init(void)
\r
605 struct Outbuf *out;
\r
606 struct LZ77Context *ectx = snew(struct LZ77Context);
\r
609 ectx->literal = zlib_literal;
\r
610 ectx->match = zlib_match;
\r
612 out = snew(struct Outbuf);
\r
613 out->outbits = out->noutbits = 0;
\r
614 out->firstblock = 1;
\r
615 out->comp_disabled = FALSE;
\r
616 ectx->userdata = out;
\r
621 void zlib_compress_cleanup(void *handle)
\r
623 struct LZ77Context *ectx = (struct LZ77Context *)handle;
\r
624 sfree(ectx->userdata);
\r
630 * Turn off actual LZ77 analysis for one block, to facilitate
\r
631 * construction of a precise-length IGNORE packet. Returns the
\r
632 * length adjustment (which is only valid for packets < 65536
\r
633 * bytes, but that seems reasonable enough).
\r
635 static int zlib_disable_compression(void *handle)
\r
637 struct LZ77Context *ectx = (struct LZ77Context *)handle;
\r
638 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
\r
641 out->comp_disabled = TRUE;
\r
645 * If this is the first block, we will start by outputting two
\r
646 * header bytes, and then three bits to begin an uncompressed
\r
647 * block. This will cost three bytes (because we will start on
\r
648 * a byte boundary, this is certain).
\r
650 if (out->firstblock) {
\r
654 * Otherwise, we will output seven bits to close the
\r
655 * previous static block, and _then_ three bits to begin an
\r
656 * uncompressed block, and then flush the current byte.
\r
657 * This may cost two bytes or three, depending on noutbits.
\r
659 n += (out->noutbits + 10) / 8;
\r
663 * Now we output four bytes for the length / ~length pair in
\r
664 * the uncompressed block.
\r
671 int zlib_compress_block(void *handle, unsigned char *block, int len,
\r
672 unsigned char **outblock, int *outlen)
\r
674 struct LZ77Context *ectx = (struct LZ77Context *)handle;
\r
675 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
\r
678 out->outbuf = NULL;
\r
679 out->outlen = out->outsize = 0;
\r
682 * If this is the first block, output the Zlib (RFC1950) header
\r
683 * bytes 78 9C. (Deflate compression, 32K window size, default
\r
686 if (out->firstblock) {
\r
687 outbits(out, 0x9C78, 16);
\r
688 out->firstblock = 0;
\r
694 if (out->comp_disabled) {
\r
696 outbits(out, 0, 7); /* close static block */
\r
699 int blen = (len < 65535 ? len : 65535);
\r
702 * Start a Deflate (RFC1951) uncompressed block. We
\r
703 * transmit a zero bit (BFINAL=0), followed by two more
\r
704 * zero bits (BTYPE=00). Of course these are in the
\r
705 * wrong order (00 0), not that it matters.
\r
707 outbits(out, 0, 3);
\r
710 * Output zero bits to align to a byte boundary.
\r
713 outbits(out, 0, 8 - out->noutbits);
\r
716 * Output the block length, and then its one's
\r
717 * complement. They're little-endian, so all we need to
\r
718 * do is pass them straight to outbits() with bit count
\r
721 outbits(out, blen, 16);
\r
722 outbits(out, blen ^ 0xFFFF, 16);
\r
725 * Do the `compression': we need to pass the data to
\r
726 * lz77_compress so that it will be taken into account
\r
727 * for subsequent (distance,length) pairs. But
\r
728 * lz77_compress is passed FALSE, which means it won't
\r
729 * actually find (or even look for) any matches; so
\r
730 * every character will be passed straight to
\r
731 * zlib_literal which will spot out->comp_disabled and
\r
732 * emit in the uncompressed format.
\r
734 lz77_compress(ectx, block, blen, FALSE);
\r
739 outbits(out, 2, 3); /* open new block */
\r
743 * Start a Deflate (RFC1951) fixed-trees block. We
\r
744 * transmit a zero bit (BFINAL=0), followed by a zero
\r
745 * bit and a one bit (BTYPE=01). Of course these are in
\r
746 * the wrong order (01 0).
\r
748 outbits(out, 2, 3);
\r
752 * Do the compression.
\r
754 lz77_compress(ectx, block, len, TRUE);
\r
757 * End the block (by transmitting code 256, which is
\r
758 * 0000000 in fixed-tree mode), and transmit some empty
\r
759 * blocks to ensure we have emitted the byte containing the
\r
760 * last piece of genuine data. There are three ways we can
\r
763 * - Minimal flush. Output end-of-block and then open a
\r
764 * new static block. This takes 9 bits, which is
\r
765 * guaranteed to flush out the last genuine code in the
\r
766 * closed block; but allegedly zlib can't handle it.
\r
768 * - Zlib partial flush. Output EOB, open and close an
\r
769 * empty static block, and _then_ open the new block.
\r
770 * This is the best zlib can handle.
\r
772 * - Zlib sync flush. Output EOB, then an empty
\r
773 * _uncompressed_ block (000, then sync to byte
\r
774 * boundary, then send bytes 00 00 FF FF). Then open the
\r
777 * For the moment, we will use Zlib partial flush.
\r
779 outbits(out, 0, 7); /* close block */
\r
780 outbits(out, 2, 3 + 7); /* empty static block */
\r
781 outbits(out, 2, 3); /* open new block */
\r
784 out->comp_disabled = FALSE;
\r
786 *outblock = out->outbuf;
\r
787 *outlen = out->outlen;
\r
792 /* ----------------------------------------------------------------------
\r
793 * Zlib decompression. Of course, even though our compressor always
\r
794 * uses static trees, our _decompressor_ has to be capable of
\r
795 * handling dynamic trees if it sees them.
\r
799 * The way we work the Huffman decode is to have a table lookup on
\r
800 * the first N bits of the input stream (in the order they arrive,
\r
801 * of course, i.e. the first bit of the Huffman code is in bit 0).
\r
802 * Each table entry lists the number of bits to consume, plus
\r
803 * either an output code or a pointer to a secondary table.
\r
806 struct zlib_tableentry;
\r
808 struct zlib_tableentry {
\r
809 unsigned char nbits;
\r
811 struct zlib_table *nexttable;
\r
814 struct zlib_table {
\r
815 int mask; /* mask applied to input bit stream */
\r
816 struct zlib_tableentry *table;
\r
819 #define MAXCODELEN 16
\r
820 #define MAXSYMS 288
\r
823 * Build a single-level decode table for elements
\r
824 * [minlength,maxlength) of the provided code/length tables, and
\r
825 * recurse to build subtables.
\r
827 static struct zlib_table *zlib_mkonetab(int *codes, unsigned char *lengths,
\r
829 int pfx, int pfxbits, int bits)
\r
831 struct zlib_table *tab = snew(struct zlib_table);
\r
832 int pfxmask = (1 << pfxbits) - 1;
\r
833 int nbits, i, j, code;
\r
835 tab->table = snewn(1 << bits, struct zlib_tableentry);
\r
836 tab->mask = (1 << bits) - 1;
\r
838 for (code = 0; code <= tab->mask; code++) {
\r
839 tab->table[code].code = -1;
\r
840 tab->table[code].nbits = 0;
\r
841 tab->table[code].nexttable = NULL;
\r
844 for (i = 0; i < nsyms; i++) {
\r
845 if (lengths[i] <= pfxbits || (codes[i] & pfxmask) != pfx)
\r
847 code = (codes[i] >> pfxbits) & tab->mask;
\r
848 for (j = code; j <= tab->mask; j += 1 << (lengths[i] - pfxbits)) {
\r
849 tab->table[j].code = i;
\r
850 nbits = lengths[i] - pfxbits;
\r
851 if (tab->table[j].nbits < nbits)
\r
852 tab->table[j].nbits = nbits;
\r
855 for (code = 0; code <= tab->mask; code++) {
\r
856 if (tab->table[code].nbits <= bits)
\r
858 /* Generate a subtable. */
\r
859 tab->table[code].code = -1;
\r
860 nbits = tab->table[code].nbits - bits;
\r
863 tab->table[code].nbits = bits;
\r
864 tab->table[code].nexttable = zlib_mkonetab(codes, lengths, nsyms,
\r
865 pfx | (code << pfxbits),
\r
866 pfxbits + bits, nbits);
\r
873 * Build a decode table, given a set of Huffman tree lengths.
\r
875 static struct zlib_table *zlib_mktable(unsigned char *lengths,
\r
878 int count[MAXCODELEN], startcode[MAXCODELEN], codes[MAXSYMS];
\r
882 /* Count the codes of each length. */
\r
884 for (i = 1; i < MAXCODELEN; i++)
\r
886 for (i = 0; i < nlengths; i++) {
\r
887 count[lengths[i]]++;
\r
888 if (maxlen < lengths[i])
\r
889 maxlen = lengths[i];
\r
891 /* Determine the starting code for each length block. */
\r
893 for (i = 1; i < MAXCODELEN; i++) {
\r
894 startcode[i] = code;
\r
898 /* Determine the code for each symbol. Mirrored, of course. */
\r
899 for (i = 0; i < nlengths; i++) {
\r
900 code = startcode[lengths[i]]++;
\r
902 for (j = 0; j < lengths[i]; j++) {
\r
903 codes[i] = (codes[i] << 1) | (code & 1);
\r
909 * Now we have the complete list of Huffman codes. Build a
\r
912 return zlib_mkonetab(codes, lengths, nlengths, 0, 0,
\r
913 maxlen < 9 ? maxlen : 9);
\r
916 static int zlib_freetable(struct zlib_table **ztab)
\r
918 struct zlib_table *tab;
\r
929 for (code = 0; code <= tab->mask; code++)
\r
930 if (tab->table[code].nexttable != NULL)
\r
931 zlib_freetable(&tab->table[code].nexttable);
\r
942 struct zlib_decompress_ctx {
\r
943 struct zlib_table *staticlentable, *staticdisttable;
\r
944 struct zlib_table *currlentable, *currdisttable, *lenlentable;
\r
947 TREES_HDR, TREES_LENLEN, TREES_LEN, TREES_LENREP,
\r
948 INBLK, GOTLENSYM, GOTLEN, GOTDISTSYM,
\r
949 UNCOMP_LEN, UNCOMP_NLEN, UNCOMP_DATA
\r
951 int sym, hlit, hdist, hclen, lenptr, lenextrabits, lenaddon, len,
\r
954 unsigned char lenlen[19];
\r
955 unsigned char lengths[286 + 32];
\r
956 unsigned long bits;
\r
958 unsigned char window[WINSIZE];
\r
960 unsigned char *outblk;
\r
961 int outlen, outsize;
\r
964 void *zlib_decompress_init(void)
\r
966 struct zlib_decompress_ctx *dctx = snew(struct zlib_decompress_ctx);
\r
967 unsigned char lengths[288];
\r
969 memset(lengths, 8, 144);
\r
970 memset(lengths + 144, 9, 256 - 144);
\r
971 memset(lengths + 256, 7, 280 - 256);
\r
972 memset(lengths + 280, 8, 288 - 280);
\r
973 dctx->staticlentable = zlib_mktable(lengths, 288);
\r
974 memset(lengths, 5, 32);
\r
975 dctx->staticdisttable = zlib_mktable(lengths, 32);
\r
976 dctx->state = START; /* even before header */
\r
977 dctx->currlentable = dctx->currdisttable = dctx->lenlentable = NULL;
\r
985 void zlib_decompress_cleanup(void *handle)
\r
987 struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
\r
989 if (dctx->currlentable && dctx->currlentable != dctx->staticlentable)
\r
990 zlib_freetable(&dctx->currlentable);
\r
991 if (dctx->currdisttable && dctx->currdisttable != dctx->staticdisttable)
\r
992 zlib_freetable(&dctx->currdisttable);
\r
993 if (dctx->lenlentable)
\r
994 zlib_freetable(&dctx->lenlentable);
\r
995 zlib_freetable(&dctx->staticlentable);
\r
996 zlib_freetable(&dctx->staticdisttable);
\r
1000 static int zlib_huflookup(unsigned long *bitsp, int *nbitsp,
\r
1001 struct zlib_table *tab)
\r
1003 unsigned long bits = *bitsp;
\r
1004 int nbits = *nbitsp;
\r
1006 struct zlib_tableentry *ent;
\r
1007 ent = &tab->table[bits & tab->mask];
\r
1008 if (ent->nbits > nbits)
\r
1009 return -1; /* not enough data */
\r
1010 bits >>= ent->nbits;
\r
1011 nbits -= ent->nbits;
\r
1012 if (ent->code == -1)
\r
1013 tab = ent->nexttable;
\r
1022 * There was a missing entry in the table, presumably
\r
1023 * due to an invalid Huffman table description, and the
\r
1024 * subsequent data has attempted to use the missing
\r
1025 * entry. Return a decoding failure.
\r
1032 static void zlib_emit_char(struct zlib_decompress_ctx *dctx, int c)
\r
1034 dctx->window[dctx->winpos] = c;
\r
1035 dctx->winpos = (dctx->winpos + 1) & (WINSIZE - 1);
\r
1036 if (dctx->outlen >= dctx->outsize) {
\r
1037 dctx->outsize = dctx->outlen + 512;
\r
1038 dctx->outblk = sresize(dctx->outblk, dctx->outsize, unsigned char);
\r
1040 dctx->outblk[dctx->outlen++] = c;
\r
1043 #define EATBITS(n) ( dctx->nbits -= (n), dctx->bits >>= (n) )
\r
1045 int zlib_decompress_block(void *handle, unsigned char *block, int len,
\r
1046 unsigned char **outblock, int *outlen)
\r
1048 struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
\r
1049 const coderecord *rec;
\r
1050 int code, blktype, rep, dist, nlen, header;
\r
1051 static const unsigned char lenlenmap[] = {
\r
1052 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
\r
1055 dctx->outblk = snewn(256, unsigned char);
\r
1056 dctx->outsize = 256;
\r
1059 while (len > 0 || dctx->nbits > 0) {
\r
1060 while (dctx->nbits < 24 && len > 0) {
\r
1061 dctx->bits |= (*block++) << dctx->nbits;
\r
1065 switch (dctx->state) {
\r
1067 /* Expect 16-bit zlib header. */
\r
1068 if (dctx->nbits < 16)
\r
1069 goto finished; /* done all we can */
\r
1072 * The header is stored as a big-endian 16-bit integer,
\r
1073 * in contrast to the general little-endian policy in
\r
1074 * the rest of the format :-(
\r
1076 header = (((dctx->bits & 0xFF00) >> 8) |
\r
1077 ((dctx->bits & 0x00FF) << 8));
\r
1081 * Check the header:
\r
1083 * - bits 8-11 should be 1000 (Deflate/RFC1951)
\r
1084 * - bits 12-15 should be at most 0111 (window size)
\r
1085 * - bit 5 should be zero (no dictionary present)
\r
1086 * - we don't care about bits 6-7 (compression rate)
\r
1087 * - bits 0-4 should be set up to make the whole thing
\r
1088 * a multiple of 31 (checksum).
\r
1090 if ((header & 0x0F00) != 0x0800 ||
\r
1091 (header & 0xF000) > 0x7000 ||
\r
1092 (header & 0x0020) != 0x0000 ||
\r
1093 (header % 31) != 0)
\r
1094 goto decode_error;
\r
1096 dctx->state = OUTSIDEBLK;
\r
1099 /* Expect 3-bit block header. */
\r
1100 if (dctx->nbits < 3)
\r
1101 goto finished; /* done all we can */
\r
1103 blktype = dctx->bits & 3;
\r
1105 if (blktype == 0) {
\r
1106 int to_eat = dctx->nbits & 7;
\r
1107 dctx->state = UNCOMP_LEN;
\r
1108 EATBITS(to_eat); /* align to byte boundary */
\r
1109 } else if (blktype == 1) {
\r
1110 dctx->currlentable = dctx->staticlentable;
\r
1111 dctx->currdisttable = dctx->staticdisttable;
\r
1112 dctx->state = INBLK;
\r
1113 } else if (blktype == 2) {
\r
1114 dctx->state = TREES_HDR;
\r
1119 * Dynamic block header. Five bits of HLIT, five of
\r
1120 * HDIST, four of HCLEN.
\r
1122 if (dctx->nbits < 5 + 5 + 4)
\r
1123 goto finished; /* done all we can */
\r
1124 dctx->hlit = 257 + (dctx->bits & 31);
\r
1126 dctx->hdist = 1 + (dctx->bits & 31);
\r
1128 dctx->hclen = 4 + (dctx->bits & 15);
\r
1131 dctx->state = TREES_LENLEN;
\r
1132 memset(dctx->lenlen, 0, sizeof(dctx->lenlen));
\r
1134 case TREES_LENLEN:
\r
1135 if (dctx->nbits < 3)
\r
1137 while (dctx->lenptr < dctx->hclen && dctx->nbits >= 3) {
\r
1138 dctx->lenlen[lenlenmap[dctx->lenptr++]] =
\r
1139 (unsigned char) (dctx->bits & 7);
\r
1142 if (dctx->lenptr == dctx->hclen) {
\r
1143 dctx->lenlentable = zlib_mktable(dctx->lenlen, 19);
\r
1144 dctx->state = TREES_LEN;
\r
1149 if (dctx->lenptr >= dctx->hlit + dctx->hdist) {
\r
1150 dctx->currlentable = zlib_mktable(dctx->lengths, dctx->hlit);
\r
1151 dctx->currdisttable = zlib_mktable(dctx->lengths + dctx->hlit,
\r
1153 zlib_freetable(&dctx->lenlentable);
\r
1154 dctx->lenlentable = NULL;
\r
1155 dctx->state = INBLK;
\r
1159 zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->lenlentable);
\r
1163 goto decode_error;
\r
1165 dctx->lengths[dctx->lenptr++] = code;
\r
1167 dctx->lenextrabits = (code == 16 ? 2 : code == 17 ? 3 : 7);
\r
1168 dctx->lenaddon = (code == 18 ? 11 : 3);
\r
1169 dctx->lenrep = (code == 16 && dctx->lenptr > 0 ?
\r
1170 dctx->lengths[dctx->lenptr - 1] : 0);
\r
1171 dctx->state = TREES_LENREP;
\r
1174 case TREES_LENREP:
\r
1175 if (dctx->nbits < dctx->lenextrabits)
\r
1179 (dctx->bits & ((1 << dctx->lenextrabits) - 1));
\r
1180 EATBITS(dctx->lenextrabits);
\r
1181 while (rep > 0 && dctx->lenptr < dctx->hlit + dctx->hdist) {
\r
1182 dctx->lengths[dctx->lenptr] = dctx->lenrep;
\r
1186 dctx->state = TREES_LEN;
\r
1190 zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->currlentable);
\r
1194 goto decode_error;
\r
1196 zlib_emit_char(dctx, code);
\r
1197 else if (code == 256) {
\r
1198 dctx->state = OUTSIDEBLK;
\r
1199 if (dctx->currlentable != dctx->staticlentable) {
\r
1200 zlib_freetable(&dctx->currlentable);
\r
1201 dctx->currlentable = NULL;
\r
1203 if (dctx->currdisttable != dctx->staticdisttable) {
\r
1204 zlib_freetable(&dctx->currdisttable);
\r
1205 dctx->currdisttable = NULL;
\r
1207 } else if (code < 286) { /* static tree can give >285; ignore */
\r
1208 dctx->state = GOTLENSYM;
\r
1213 rec = &lencodes[dctx->sym - 257];
\r
1214 if (dctx->nbits < rec->extrabits)
\r
1217 rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
\r
1218 EATBITS(rec->extrabits);
\r
1219 dctx->state = GOTLEN;
\r
1223 zlib_huflookup(&dctx->bits, &dctx->nbits,
\r
1224 dctx->currdisttable);
\r
1228 goto decode_error;
\r
1229 dctx->state = GOTDISTSYM;
\r
1233 rec = &distcodes[dctx->sym];
\r
1234 if (dctx->nbits < rec->extrabits)
\r
1236 dist = rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
\r
1237 EATBITS(rec->extrabits);
\r
1238 dctx->state = INBLK;
\r
1239 while (dctx->len--)
\r
1240 zlib_emit_char(dctx, dctx->window[(dctx->winpos - dist) &
\r
1245 * Uncompressed block. We expect to see a 16-bit LEN.
\r
1247 if (dctx->nbits < 16)
\r
1249 dctx->uncomplen = dctx->bits & 0xFFFF;
\r
1251 dctx->state = UNCOMP_NLEN;
\r
1255 * Uncompressed block. We expect to see a 16-bit NLEN,
\r
1256 * which should be the one's complement of the previous
\r
1259 if (dctx->nbits < 16)
\r
1261 nlen = dctx->bits & 0xFFFF;
\r
1263 if (dctx->uncomplen != (nlen ^ 0xFFFF))
\r
1264 goto decode_error;
\r
1265 if (dctx->uncomplen == 0)
\r
1266 dctx->state = OUTSIDEBLK; /* block is empty */
\r
1268 dctx->state = UNCOMP_DATA;
\r
1271 if (dctx->nbits < 8)
\r
1273 zlib_emit_char(dctx, dctx->bits & 0xFF);
\r
1275 if (--dctx->uncomplen == 0)
\r
1276 dctx->state = OUTSIDEBLK; /* end of uncompressed block */
\r
1282 *outblock = dctx->outblk;
\r
1283 *outlen = dctx->outlen;
\r
1287 sfree(dctx->outblk);
\r
1288 *outblock = dctx->outblk = NULL;
\r
1293 #ifdef ZLIB_STANDALONE
\r
1295 #include <stdio.h>
\r
1296 #include <string.h>
\r
1298 int main(int argc, char **argv)
\r
1300 unsigned char buf[16], *outbuf;
\r
1303 int noheader = FALSE, opts = TRUE;
\r
1304 char *filename = NULL;
\r
1308 char *p = *++argv;
\r
1310 if (p[0] == '-' && opts) {
\r
1311 if (!strcmp(p, "-d"))
\r
1313 else if (!strcmp(p, "--"))
\r
1314 opts = FALSE; /* next thing is filename */
\r
1316 fprintf(stderr, "unknown command line option '%s'\n", p);
\r
1319 } else if (!filename) {
\r
1322 fprintf(stderr, "can only handle one filename\n");
\r
1327 handle = zlib_decompress_init();
\r
1331 * Provide missing zlib header if -d was specified.
\r
1333 zlib_decompress_block(handle, "\x78\x9C", 2, &outbuf, &outlen);
\r
1334 assert(outlen == 0);
\r
1338 fp = fopen(filename, "rb");
\r
1344 fprintf(stderr, "unable to open '%s'\n", filename);
\r
1349 ret = fread(buf, 1, sizeof(buf), fp);
\r
1352 zlib_decompress_block(handle, buf, ret, &outbuf, &outlen);
\r
1355 fwrite(outbuf, 1, outlen, stdout);
\r
1358 fprintf(stderr, "decoding error\n");
\r
1363 zlib_decompress_cleanup(handle);
\r
1373 const struct ssh_compress ssh_zlib = {
\r
1375 "zlib@openssh.com", /* delayed version */
\r
1376 zlib_compress_init,
\r
1377 zlib_compress_cleanup,
\r
1378 zlib_compress_block,
\r
1379 zlib_decompress_init,
\r
1380 zlib_decompress_cleanup,
\r
1381 zlib_decompress_block,
\r
1382 zlib_disable_compression,
\r