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, distance, off, nmatch, matchlen, advance;
\r
205 struct Match defermatch, matches[MAXMATCH];
\r
208 assert(st->npending <= HASHCHARS);
\r
211 * Add any pending characters from last time to the window. (We
\r
212 * might not be able to.)
\r
214 * This leaves st->pending empty in the usual case (when len >=
\r
215 * HASHCHARS); otherwise it leaves st->pending empty enough that
\r
216 * adding all the remaining 'len' characters will not push it past
\r
217 * HASHCHARS in size.
\r
219 for (i = 0; i < st->npending; i++) {
\r
220 unsigned char foo[HASHCHARS];
\r
222 if (len + st->npending - i < HASHCHARS) {
\r
223 /* Update the pending array. */
\r
224 for (j = i; j < st->npending; j++)
\r
225 st->pending[j - i] = st->pending[j];
\r
228 for (j = 0; j < HASHCHARS; j++)
\r
229 foo[j] = (i + j < st->npending ? st->pending[i + j] :
\r
230 data[i + j - st->npending]);
\r
231 lz77_advance(st, foo[0], lz77_hash(foo));
\r
235 defermatch.distance = 0; /* appease compiler */
\r
236 defermatch.len = 0;
\r
240 /* Don't even look for a match, if we're not compressing. */
\r
241 if (compress && len >= HASHCHARS) {
\r
243 * Hash the next few characters.
\r
245 int hash = lz77_hash(data);
\r
248 * Look the hash up in the corresponding hash chain and see
\r
249 * what we can find.
\r
252 for (off = st->hashtab[hash].first;
\r
253 off != INVALID; off = st->win[off].next) {
\r
254 /* distance = 1 if off == st->winpos-1 */
\r
255 /* distance = WINSIZE if off == st->winpos */
\r
257 WINSIZE - (off + WINSIZE - st->winpos) % WINSIZE;
\r
258 for (i = 0; i < HASHCHARS; i++)
\r
259 if (CHARAT(i) != CHARAT(i - distance))
\r
261 if (i == HASHCHARS) {
\r
262 matches[nmatch].distance = distance;
\r
263 matches[nmatch].len = 3;
\r
264 if (++nmatch >= MAXMATCH)
\r
274 * We've now filled up matches[] with nmatch potential
\r
275 * matches. Follow them down to find the longest. (We
\r
276 * assume here that it's always worth favouring a
\r
277 * longer match over a shorter one.)
\r
279 matchlen = HASHCHARS;
\r
280 while (matchlen < len) {
\r
282 for (i = j = 0; i < nmatch; i++) {
\r
283 if (CHARAT(matchlen) ==
\r
284 CHARAT(matchlen - matches[i].distance)) {
\r
285 matches[j++] = matches[i];
\r
295 * We've now got all the longest matches. We favour the
\r
296 * shorter distances, which means we go with matches[0].
\r
297 * So see if we want to defer it or throw it away.
\r
299 matches[0].len = matchlen;
\r
300 if (defermatch.len > 0) {
\r
301 if (matches[0].len > defermatch.len + 1) {
\r
302 /* We have a better match. Emit the deferred char,
\r
303 * and defer this match. */
\r
304 ctx->literal(ctx, (unsigned char) deferchr);
\r
305 defermatch = matches[0];
\r
306 deferchr = data[0];
\r
309 /* We don't have a better match. Do the deferred one. */
\r
310 ctx->match(ctx, defermatch.distance, defermatch.len);
\r
311 advance = defermatch.len - 1;
\r
312 defermatch.len = 0;
\r
315 /* There was no deferred match. Defer this one. */
\r
316 defermatch = matches[0];
\r
317 deferchr = data[0];
\r
322 * We found no matches. Emit the deferred match, if
\r
323 * any; otherwise emit a literal.
\r
325 if (defermatch.len > 0) {
\r
326 ctx->match(ctx, defermatch.distance, defermatch.len);
\r
327 advance = defermatch.len - 1;
\r
328 defermatch.len = 0;
\r
330 ctx->literal(ctx, data[0]);
\r
336 * Now advance the position by `advance' characters,
\r
337 * keeping the window and hash chains consistent.
\r
339 while (advance > 0) {
\r
340 if (len >= HASHCHARS) {
\r
341 lz77_advance(st, *data, lz77_hash(data));
\r
343 assert(st->npending < HASHCHARS);
\r
344 st->pending[st->npending++] = *data;
\r
353 /* ----------------------------------------------------------------------
\r
354 * Zlib compression. We always use the static Huffman tree option.
\r
355 * Mostly this is because it's hard to scan a block in advance to
\r
356 * work out better trees; dynamic trees are great when you're
\r
357 * compressing a large file under no significant time constraint,
\r
358 * but when you're compressing little bits in real time, things get
\r
361 * I suppose it's possible that I could compute Huffman trees based
\r
362 * on the frequencies in the _previous_ block, as a sort of
\r
363 * heuristic, but I'm not confident that the gain would balance out
\r
364 * having to transmit the trees.
\r
368 unsigned char *outbuf;
\r
369 int outlen, outsize;
\r
370 unsigned long outbits;
\r
376 static void outbits(struct Outbuf *out, unsigned long bits, int nbits)
\r
378 assert(out->noutbits + nbits <= 32);
\r
379 out->outbits |= bits << out->noutbits;
\r
380 out->noutbits += nbits;
\r
381 while (out->noutbits >= 8) {
\r
382 if (out->outlen >= out->outsize) {
\r
383 out->outsize = out->outlen + 64;
\r
384 out->outbuf = sresize(out->outbuf, out->outsize, unsigned char);
\r
386 out->outbuf[out->outlen++] = (unsigned char) (out->outbits & 0xFF);
\r
387 out->outbits >>= 8;
\r
388 out->noutbits -= 8;
\r
392 static const unsigned char mirrorbytes[256] = {
\r
393 0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
\r
394 0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
\r
395 0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
\r
396 0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
\r
397 0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
\r
398 0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
\r
399 0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
\r
400 0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
\r
401 0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
\r
402 0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
\r
403 0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
\r
404 0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
\r
405 0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
\r
406 0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
\r
407 0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
\r
408 0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
\r
409 0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
\r
410 0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
\r
411 0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
\r
412 0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
\r
413 0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
\r
414 0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
\r
415 0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
\r
416 0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
\r
417 0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
\r
418 0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
\r
419 0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
\r
420 0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
\r
421 0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
\r
422 0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
\r
423 0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
\r
424 0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
\r
428 short code, extrabits;
\r
432 static const coderecord lencodes[] = {
\r
456 {280, 4, 115, 130},
\r
457 {281, 5, 131, 162},
\r
458 {282, 5, 163, 194},
\r
459 {283, 5, 195, 226},
\r
460 {284, 5, 227, 257},
\r
461 {285, 0, 258, 258},
\r
464 static const coderecord distcodes[] = {
\r
484 {19, 8, 769, 1024},
\r
485 {20, 9, 1025, 1536},
\r
486 {21, 9, 1537, 2048},
\r
487 {22, 10, 2049, 3072},
\r
488 {23, 10, 3073, 4096},
\r
489 {24, 11, 4097, 6144},
\r
490 {25, 11, 6145, 8192},
\r
491 {26, 12, 8193, 12288},
\r
492 {27, 12, 12289, 16384},
\r
493 {28, 13, 16385, 24576},
\r
494 {29, 13, 24577, 32768},
\r
497 static void zlib_literal(struct LZ77Context *ectx, unsigned char c)
\r
499 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
\r
501 if (out->comp_disabled) {
\r
503 * We're in an uncompressed block, so just output the byte.
\r
505 outbits(out, c, 8);
\r
510 /* 0 through 143 are 8 bits long starting at 00110000. */
\r
511 outbits(out, mirrorbytes[0x30 + c], 8);
\r
513 /* 144 through 255 are 9 bits long starting at 110010000. */
\r
514 outbits(out, 1 + 2 * mirrorbytes[0x90 - 144 + c], 9);
\r
518 static void zlib_match(struct LZ77Context *ectx, int distance, int len)
\r
520 const coderecord *d, *l;
\r
522 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
\r
524 assert(!out->comp_disabled);
\r
530 * We can transmit matches of lengths 3 through 258
\r
531 * inclusive. So if len exceeds 258, we must transmit in
\r
532 * several steps, with 258 or less in each step.
\r
534 * Specifically: if len >= 261, we can transmit 258 and be
\r
535 * sure of having at least 3 left for the next step. And if
\r
536 * len <= 258, we can just transmit len. But if len == 259
\r
537 * or 260, we must transmit len-3.
\r
539 thislen = (len > 260 ? 258 : len <= 258 ? len : len - 3);
\r
543 * Binary-search to find which length code we're
\r
547 j = sizeof(lencodes) / sizeof(*lencodes);
\r
549 assert(j - i >= 2);
\r
551 if (thislen < lencodes[k].min)
\r
553 else if (thislen > lencodes[k].max)
\r
557 break; /* found it! */
\r
562 * Transmit the length code. 256-279 are seven bits
\r
563 * starting at 0000000; 280-287 are eight bits starting at
\r
566 if (l->code <= 279) {
\r
567 outbits(out, mirrorbytes[(l->code - 256) * 2], 7);
\r
569 outbits(out, mirrorbytes[0xc0 - 280 + l->code], 8);
\r
573 * Transmit the extra bits.
\r
576 outbits(out, thislen - l->min, l->extrabits);
\r
579 * Binary-search to find which distance code we're
\r
583 j = sizeof(distcodes) / sizeof(*distcodes);
\r
585 assert(j - i >= 2);
\r
587 if (distance < distcodes[k].min)
\r
589 else if (distance > distcodes[k].max)
\r
593 break; /* found it! */
\r
598 * Transmit the distance code. Five bits starting at 00000.
\r
600 outbits(out, mirrorbytes[d->code * 8], 5);
\r
603 * Transmit the extra bits.
\r
606 outbits(out, distance - d->min, d->extrabits);
\r
610 void *zlib_compress_init(void)
\r
612 struct Outbuf *out;
\r
613 struct LZ77Context *ectx = snew(struct LZ77Context);
\r
616 ectx->literal = zlib_literal;
\r
617 ectx->match = zlib_match;
\r
619 out = snew(struct Outbuf);
\r
620 out->outbits = out->noutbits = 0;
\r
621 out->firstblock = 1;
\r
622 out->comp_disabled = FALSE;
\r
623 ectx->userdata = out;
\r
628 void zlib_compress_cleanup(void *handle)
\r
630 struct LZ77Context *ectx = (struct LZ77Context *)handle;
\r
631 sfree(ectx->userdata);
\r
637 * Turn off actual LZ77 analysis for one block, to facilitate
\r
638 * construction of a precise-length IGNORE packet. Returns the
\r
639 * length adjustment (which is only valid for packets < 65536
\r
640 * bytes, but that seems reasonable enough).
\r
642 static int zlib_disable_compression(void *handle)
\r
644 struct LZ77Context *ectx = (struct LZ77Context *)handle;
\r
645 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
\r
648 out->comp_disabled = TRUE;
\r
652 * If this is the first block, we will start by outputting two
\r
653 * header bytes, and then three bits to begin an uncompressed
\r
654 * block. This will cost three bytes (because we will start on
\r
655 * a byte boundary, this is certain).
\r
657 if (out->firstblock) {
\r
661 * Otherwise, we will output seven bits to close the
\r
662 * previous static block, and _then_ three bits to begin an
\r
663 * uncompressed block, and then flush the current byte.
\r
664 * This may cost two bytes or three, depending on noutbits.
\r
666 n += (out->noutbits + 10) / 8;
\r
670 * Now we output four bytes for the length / ~length pair in
\r
671 * the uncompressed block.
\r
678 int zlib_compress_block(void *handle, unsigned char *block, int len,
\r
679 unsigned char **outblock, int *outlen)
\r
681 struct LZ77Context *ectx = (struct LZ77Context *)handle;
\r
682 struct Outbuf *out = (struct Outbuf *) ectx->userdata;
\r
685 out->outbuf = NULL;
\r
686 out->outlen = out->outsize = 0;
\r
689 * If this is the first block, output the Zlib (RFC1950) header
\r
690 * bytes 78 9C. (Deflate compression, 32K window size, default
\r
693 if (out->firstblock) {
\r
694 outbits(out, 0x9C78, 16);
\r
695 out->firstblock = 0;
\r
701 if (out->comp_disabled) {
\r
703 outbits(out, 0, 7); /* close static block */
\r
706 int blen = (len < 65535 ? len : 65535);
\r
709 * Start a Deflate (RFC1951) uncompressed block. We
\r
710 * transmit a zero bit (BFINAL=0), followed by two more
\r
711 * zero bits (BTYPE=00). Of course these are in the
\r
712 * wrong order (00 0), not that it matters.
\r
714 outbits(out, 0, 3);
\r
717 * Output zero bits to align to a byte boundary.
\r
720 outbits(out, 0, 8 - out->noutbits);
\r
723 * Output the block length, and then its one's
\r
724 * complement. They're little-endian, so all we need to
\r
725 * do is pass them straight to outbits() with bit count
\r
728 outbits(out, blen, 16);
\r
729 outbits(out, blen ^ 0xFFFF, 16);
\r
732 * Do the `compression': we need to pass the data to
\r
733 * lz77_compress so that it will be taken into account
\r
734 * for subsequent (distance,length) pairs. But
\r
735 * lz77_compress is passed FALSE, which means it won't
\r
736 * actually find (or even look for) any matches; so
\r
737 * every character will be passed straight to
\r
738 * zlib_literal which will spot out->comp_disabled and
\r
739 * emit in the uncompressed format.
\r
741 lz77_compress(ectx, block, blen, FALSE);
\r
746 outbits(out, 2, 3); /* open new block */
\r
750 * Start a Deflate (RFC1951) fixed-trees block. We
\r
751 * transmit a zero bit (BFINAL=0), followed by a zero
\r
752 * bit and a one bit (BTYPE=01). Of course these are in
\r
753 * the wrong order (01 0).
\r
755 outbits(out, 2, 3);
\r
759 * Do the compression.
\r
761 lz77_compress(ectx, block, len, TRUE);
\r
764 * End the block (by transmitting code 256, which is
\r
765 * 0000000 in fixed-tree mode), and transmit some empty
\r
766 * blocks to ensure we have emitted the byte containing the
\r
767 * last piece of genuine data. There are three ways we can
\r
770 * - Minimal flush. Output end-of-block and then open a
\r
771 * new static block. This takes 9 bits, which is
\r
772 * guaranteed to flush out the last genuine code in the
\r
773 * closed block; but allegedly zlib can't handle it.
\r
775 * - Zlib partial flush. Output EOB, open and close an
\r
776 * empty static block, and _then_ open the new block.
\r
777 * This is the best zlib can handle.
\r
779 * - Zlib sync flush. Output EOB, then an empty
\r
780 * _uncompressed_ block (000, then sync to byte
\r
781 * boundary, then send bytes 00 00 FF FF). Then open the
\r
784 * For the moment, we will use Zlib partial flush.
\r
786 outbits(out, 0, 7); /* close block */
\r
787 outbits(out, 2, 3 + 7); /* empty static block */
\r
788 outbits(out, 2, 3); /* open new block */
\r
791 out->comp_disabled = FALSE;
\r
793 *outblock = out->outbuf;
\r
794 *outlen = out->outlen;
\r
799 /* ----------------------------------------------------------------------
\r
800 * Zlib decompression. Of course, even though our compressor always
\r
801 * uses static trees, our _decompressor_ has to be capable of
\r
802 * handling dynamic trees if it sees them.
\r
806 * The way we work the Huffman decode is to have a table lookup on
\r
807 * the first N bits of the input stream (in the order they arrive,
\r
808 * of course, i.e. the first bit of the Huffman code is in bit 0).
\r
809 * Each table entry lists the number of bits to consume, plus
\r
810 * either an output code or a pointer to a secondary table.
\r
813 struct zlib_tableentry;
\r
815 struct zlib_tableentry {
\r
816 unsigned char nbits;
\r
818 struct zlib_table *nexttable;
\r
821 struct zlib_table {
\r
822 int mask; /* mask applied to input bit stream */
\r
823 struct zlib_tableentry *table;
\r
826 #define MAXCODELEN 16
\r
827 #define MAXSYMS 288
\r
830 * Build a single-level decode table for elements
\r
831 * [minlength,maxlength) of the provided code/length tables, and
\r
832 * recurse to build subtables.
\r
834 static struct zlib_table *zlib_mkonetab(int *codes, unsigned char *lengths,
\r
836 int pfx, int pfxbits, int bits)
\r
838 struct zlib_table *tab = snew(struct zlib_table);
\r
839 int pfxmask = (1 << pfxbits) - 1;
\r
840 int nbits, i, j, code;
\r
842 tab->table = snewn(1 << bits, struct zlib_tableentry);
\r
843 tab->mask = (1 << bits) - 1;
\r
845 for (code = 0; code <= tab->mask; code++) {
\r
846 tab->table[code].code = -1;
\r
847 tab->table[code].nbits = 0;
\r
848 tab->table[code].nexttable = NULL;
\r
851 for (i = 0; i < nsyms; i++) {
\r
852 if (lengths[i] <= pfxbits || (codes[i] & pfxmask) != pfx)
\r
854 code = (codes[i] >> pfxbits) & tab->mask;
\r
855 for (j = code; j <= tab->mask; j += 1 << (lengths[i] - pfxbits)) {
\r
856 tab->table[j].code = i;
\r
857 nbits = lengths[i] - pfxbits;
\r
858 if (tab->table[j].nbits < nbits)
\r
859 tab->table[j].nbits = nbits;
\r
862 for (code = 0; code <= tab->mask; code++) {
\r
863 if (tab->table[code].nbits <= bits)
\r
865 /* Generate a subtable. */
\r
866 tab->table[code].code = -1;
\r
867 nbits = tab->table[code].nbits - bits;
\r
870 tab->table[code].nbits = bits;
\r
871 tab->table[code].nexttable = zlib_mkonetab(codes, lengths, nsyms,
\r
872 pfx | (code << pfxbits),
\r
873 pfxbits + bits, nbits);
\r
880 * Build a decode table, given a set of Huffman tree lengths.
\r
882 static struct zlib_table *zlib_mktable(unsigned char *lengths,
\r
885 int count[MAXCODELEN], startcode[MAXCODELEN], codes[MAXSYMS];
\r
889 /* Count the codes of each length. */
\r
891 for (i = 1; i < MAXCODELEN; i++)
\r
893 for (i = 0; i < nlengths; i++) {
\r
894 count[lengths[i]]++;
\r
895 if (maxlen < lengths[i])
\r
896 maxlen = lengths[i];
\r
898 /* Determine the starting code for each length block. */
\r
900 for (i = 1; i < MAXCODELEN; i++) {
\r
901 startcode[i] = code;
\r
905 /* Determine the code for each symbol. Mirrored, of course. */
\r
906 for (i = 0; i < nlengths; i++) {
\r
907 code = startcode[lengths[i]]++;
\r
909 for (j = 0; j < lengths[i]; j++) {
\r
910 codes[i] = (codes[i] << 1) | (code & 1);
\r
916 * Now we have the complete list of Huffman codes. Build a
\r
919 return zlib_mkonetab(codes, lengths, nlengths, 0, 0,
\r
920 maxlen < 9 ? maxlen : 9);
\r
923 static int zlib_freetable(struct zlib_table **ztab)
\r
925 struct zlib_table *tab;
\r
936 for (code = 0; code <= tab->mask; code++)
\r
937 if (tab->table[code].nexttable != NULL)
\r
938 zlib_freetable(&tab->table[code].nexttable);
\r
949 struct zlib_decompress_ctx {
\r
950 struct zlib_table *staticlentable, *staticdisttable;
\r
951 struct zlib_table *currlentable, *currdisttable, *lenlentable;
\r
954 TREES_HDR, TREES_LENLEN, TREES_LEN, TREES_LENREP,
\r
955 INBLK, GOTLENSYM, GOTLEN, GOTDISTSYM,
\r
956 UNCOMP_LEN, UNCOMP_NLEN, UNCOMP_DATA
\r
958 int sym, hlit, hdist, hclen, lenptr, lenextrabits, lenaddon, len,
\r
961 unsigned char lenlen[19];
\r
962 unsigned char lengths[286 + 32];
\r
963 unsigned long bits;
\r
965 unsigned char window[WINSIZE];
\r
967 unsigned char *outblk;
\r
968 int outlen, outsize;
\r
971 void *zlib_decompress_init(void)
\r
973 struct zlib_decompress_ctx *dctx = snew(struct zlib_decompress_ctx);
\r
974 unsigned char lengths[288];
\r
976 memset(lengths, 8, 144);
\r
977 memset(lengths + 144, 9, 256 - 144);
\r
978 memset(lengths + 256, 7, 280 - 256);
\r
979 memset(lengths + 280, 8, 288 - 280);
\r
980 dctx->staticlentable = zlib_mktable(lengths, 288);
\r
981 memset(lengths, 5, 32);
\r
982 dctx->staticdisttable = zlib_mktable(lengths, 32);
\r
983 dctx->state = START; /* even before header */
\r
984 dctx->currlentable = dctx->currdisttable = dctx->lenlentable = NULL;
\r
992 void zlib_decompress_cleanup(void *handle)
\r
994 struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
\r
996 if (dctx->currlentable && dctx->currlentable != dctx->staticlentable)
\r
997 zlib_freetable(&dctx->currlentable);
\r
998 if (dctx->currdisttable && dctx->currdisttable != dctx->staticdisttable)
\r
999 zlib_freetable(&dctx->currdisttable);
\r
1000 if (dctx->lenlentable)
\r
1001 zlib_freetable(&dctx->lenlentable);
\r
1002 zlib_freetable(&dctx->staticlentable);
\r
1003 zlib_freetable(&dctx->staticdisttable);
\r
1007 static int zlib_huflookup(unsigned long *bitsp, int *nbitsp,
\r
1008 struct zlib_table *tab)
\r
1010 unsigned long bits = *bitsp;
\r
1011 int nbits = *nbitsp;
\r
1013 struct zlib_tableentry *ent;
\r
1014 ent = &tab->table[bits & tab->mask];
\r
1015 if (ent->nbits > nbits)
\r
1016 return -1; /* not enough data */
\r
1017 bits >>= ent->nbits;
\r
1018 nbits -= ent->nbits;
\r
1019 if (ent->code == -1)
\r
1020 tab = ent->nexttable;
\r
1029 * There was a missing entry in the table, presumably
\r
1030 * due to an invalid Huffman table description, and the
\r
1031 * subsequent data has attempted to use the missing
\r
1032 * entry. Return a decoding failure.
\r
1039 static void zlib_emit_char(struct zlib_decompress_ctx *dctx, int c)
\r
1041 dctx->window[dctx->winpos] = c;
\r
1042 dctx->winpos = (dctx->winpos + 1) & (WINSIZE - 1);
\r
1043 if (dctx->outlen >= dctx->outsize) {
\r
1044 dctx->outsize = dctx->outlen + 512;
\r
1045 dctx->outblk = sresize(dctx->outblk, dctx->outsize, unsigned char);
\r
1047 dctx->outblk[dctx->outlen++] = c;
\r
1050 #define EATBITS(n) ( dctx->nbits -= (n), dctx->bits >>= (n) )
\r
1052 int zlib_decompress_block(void *handle, unsigned char *block, int len,
\r
1053 unsigned char **outblock, int *outlen)
\r
1055 struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
\r
1056 const coderecord *rec;
\r
1057 int code, blktype, rep, dist, nlen, header;
\r
1058 static const unsigned char lenlenmap[] = {
\r
1059 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
\r
1062 dctx->outblk = snewn(256, unsigned char);
\r
1063 dctx->outsize = 256;
\r
1066 while (len > 0 || dctx->nbits > 0) {
\r
1067 while (dctx->nbits < 24 && len > 0) {
\r
1068 dctx->bits |= (*block++) << dctx->nbits;
\r
1072 switch (dctx->state) {
\r
1074 /* Expect 16-bit zlib header. */
\r
1075 if (dctx->nbits < 16)
\r
1076 goto finished; /* done all we can */
\r
1079 * The header is stored as a big-endian 16-bit integer,
\r
1080 * in contrast to the general little-endian policy in
\r
1081 * the rest of the format :-(
\r
1083 header = (((dctx->bits & 0xFF00) >> 8) |
\r
1084 ((dctx->bits & 0x00FF) << 8));
\r
1088 * Check the header:
\r
1090 * - bits 8-11 should be 1000 (Deflate/RFC1951)
\r
1091 * - bits 12-15 should be at most 0111 (window size)
\r
1092 * - bit 5 should be zero (no dictionary present)
\r
1093 * - we don't care about bits 6-7 (compression rate)
\r
1094 * - bits 0-4 should be set up to make the whole thing
\r
1095 * a multiple of 31 (checksum).
\r
1097 if ((header & 0x0F00) != 0x0800 ||
\r
1098 (header & 0xF000) > 0x7000 ||
\r
1099 (header & 0x0020) != 0x0000 ||
\r
1100 (header % 31) != 0)
\r
1101 goto decode_error;
\r
1103 dctx->state = OUTSIDEBLK;
\r
1106 /* Expect 3-bit block header. */
\r
1107 if (dctx->nbits < 3)
\r
1108 goto finished; /* done all we can */
\r
1110 blktype = dctx->bits & 3;
\r
1112 if (blktype == 0) {
\r
1113 int to_eat = dctx->nbits & 7;
\r
1114 dctx->state = UNCOMP_LEN;
\r
1115 EATBITS(to_eat); /* align to byte boundary */
\r
1116 } else if (blktype == 1) {
\r
1117 dctx->currlentable = dctx->staticlentable;
\r
1118 dctx->currdisttable = dctx->staticdisttable;
\r
1119 dctx->state = INBLK;
\r
1120 } else if (blktype == 2) {
\r
1121 dctx->state = TREES_HDR;
\r
1126 * Dynamic block header. Five bits of HLIT, five of
\r
1127 * HDIST, four of HCLEN.
\r
1129 if (dctx->nbits < 5 + 5 + 4)
\r
1130 goto finished; /* done all we can */
\r
1131 dctx->hlit = 257 + (dctx->bits & 31);
\r
1133 dctx->hdist = 1 + (dctx->bits & 31);
\r
1135 dctx->hclen = 4 + (dctx->bits & 15);
\r
1138 dctx->state = TREES_LENLEN;
\r
1139 memset(dctx->lenlen, 0, sizeof(dctx->lenlen));
\r
1141 case TREES_LENLEN:
\r
1142 if (dctx->nbits < 3)
\r
1144 while (dctx->lenptr < dctx->hclen && dctx->nbits >= 3) {
\r
1145 dctx->lenlen[lenlenmap[dctx->lenptr++]] =
\r
1146 (unsigned char) (dctx->bits & 7);
\r
1149 if (dctx->lenptr == dctx->hclen) {
\r
1150 dctx->lenlentable = zlib_mktable(dctx->lenlen, 19);
\r
1151 dctx->state = TREES_LEN;
\r
1156 if (dctx->lenptr >= dctx->hlit + dctx->hdist) {
\r
1157 dctx->currlentable = zlib_mktable(dctx->lengths, dctx->hlit);
\r
1158 dctx->currdisttable = zlib_mktable(dctx->lengths + dctx->hlit,
\r
1160 zlib_freetable(&dctx->lenlentable);
\r
1161 dctx->lenlentable = NULL;
\r
1162 dctx->state = INBLK;
\r
1166 zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->lenlentable);
\r
1170 goto decode_error;
\r
1172 dctx->lengths[dctx->lenptr++] = code;
\r
1174 dctx->lenextrabits = (code == 16 ? 2 : code == 17 ? 3 : 7);
\r
1175 dctx->lenaddon = (code == 18 ? 11 : 3);
\r
1176 dctx->lenrep = (code == 16 && dctx->lenptr > 0 ?
\r
1177 dctx->lengths[dctx->lenptr - 1] : 0);
\r
1178 dctx->state = TREES_LENREP;
\r
1181 case TREES_LENREP:
\r
1182 if (dctx->nbits < dctx->lenextrabits)
\r
1186 (dctx->bits & ((1 << dctx->lenextrabits) - 1));
\r
1187 EATBITS(dctx->lenextrabits);
\r
1188 while (rep > 0 && dctx->lenptr < dctx->hlit + dctx->hdist) {
\r
1189 dctx->lengths[dctx->lenptr] = dctx->lenrep;
\r
1193 dctx->state = TREES_LEN;
\r
1197 zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->currlentable);
\r
1201 goto decode_error;
\r
1203 zlib_emit_char(dctx, code);
\r
1204 else if (code == 256) {
\r
1205 dctx->state = OUTSIDEBLK;
\r
1206 if (dctx->currlentable != dctx->staticlentable) {
\r
1207 zlib_freetable(&dctx->currlentable);
\r
1208 dctx->currlentable = NULL;
\r
1210 if (dctx->currdisttable != dctx->staticdisttable) {
\r
1211 zlib_freetable(&dctx->currdisttable);
\r
1212 dctx->currdisttable = NULL;
\r
1214 } else if (code < 286) { /* static tree can give >285; ignore */
\r
1215 dctx->state = GOTLENSYM;
\r
1220 rec = &lencodes[dctx->sym - 257];
\r
1221 if (dctx->nbits < rec->extrabits)
\r
1224 rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
\r
1225 EATBITS(rec->extrabits);
\r
1226 dctx->state = GOTLEN;
\r
1230 zlib_huflookup(&dctx->bits, &dctx->nbits,
\r
1231 dctx->currdisttable);
\r
1235 goto decode_error;
\r
1236 if (code >= 30) /* dist symbols 30 and 31 are invalid */
\r
1237 goto decode_error;
\r
1238 dctx->state = GOTDISTSYM;
\r
1242 rec = &distcodes[dctx->sym];
\r
1243 if (dctx->nbits < rec->extrabits)
\r
1245 dist = rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
\r
1246 EATBITS(rec->extrabits);
\r
1247 dctx->state = INBLK;
\r
1248 while (dctx->len--)
\r
1249 zlib_emit_char(dctx, dctx->window[(dctx->winpos - dist) &
\r
1254 * Uncompressed block. We expect to see a 16-bit LEN.
\r
1256 if (dctx->nbits < 16)
\r
1258 dctx->uncomplen = dctx->bits & 0xFFFF;
\r
1260 dctx->state = UNCOMP_NLEN;
\r
1264 * Uncompressed block. We expect to see a 16-bit NLEN,
\r
1265 * which should be the one's complement of the previous
\r
1268 if (dctx->nbits < 16)
\r
1270 nlen = dctx->bits & 0xFFFF;
\r
1272 if (dctx->uncomplen != (nlen ^ 0xFFFF))
\r
1273 goto decode_error;
\r
1274 if (dctx->uncomplen == 0)
\r
1275 dctx->state = OUTSIDEBLK; /* block is empty */
\r
1277 dctx->state = UNCOMP_DATA;
\r
1280 if (dctx->nbits < 8)
\r
1282 zlib_emit_char(dctx, dctx->bits & 0xFF);
\r
1284 if (--dctx->uncomplen == 0)
\r
1285 dctx->state = OUTSIDEBLK; /* end of uncompressed block */
\r
1291 *outblock = dctx->outblk;
\r
1292 *outlen = dctx->outlen;
\r
1296 sfree(dctx->outblk);
\r
1297 *outblock = dctx->outblk = NULL;
\r
1302 #ifdef ZLIB_STANDALONE
\r
1304 #include <stdio.h>
\r
1305 #include <string.h>
\r
1307 int main(int argc, char **argv)
\r
1309 unsigned char buf[16], *outbuf;
\r
1312 int noheader = FALSE, opts = TRUE;
\r
1313 char *filename = NULL;
\r
1317 char *p = *++argv;
\r
1319 if (p[0] == '-' && opts) {
\r
1320 if (!strcmp(p, "-d"))
\r
1322 else if (!strcmp(p, "--"))
\r
1323 opts = FALSE; /* next thing is filename */
\r
1325 fprintf(stderr, "unknown command line option '%s'\n", p);
\r
1328 } else if (!filename) {
\r
1331 fprintf(stderr, "can only handle one filename\n");
\r
1336 handle = zlib_decompress_init();
\r
1340 * Provide missing zlib header if -d was specified.
\r
1342 zlib_decompress_block(handle, "\x78\x9C", 2, &outbuf, &outlen);
\r
1343 assert(outlen == 0);
\r
1347 fp = fopen(filename, "rb");
\r
1353 fprintf(stderr, "unable to open '%s'\n", filename);
\r
1358 ret = fread(buf, 1, sizeof(buf), fp);
\r
1361 zlib_decompress_block(handle, buf, ret, &outbuf, &outlen);
\r
1364 fwrite(outbuf, 1, outlen, stdout);
\r
1367 fprintf(stderr, "decoding error\n");
\r
1373 zlib_decompress_cleanup(handle);
\r
1383 const struct ssh_compress ssh_zlib = {
\r
1385 "zlib@openssh.com", /* delayed version */
\r
1386 zlib_compress_init,
\r
1387 zlib_compress_cleanup,
\r
1388 zlib_compress_block,
\r
1389 zlib_decompress_init,
\r
1390 zlib_decompress_cleanup,
\r
1391 zlib_decompress_block,
\r
1392 zlib_disable_compression,
\r