sshzlib.c

   1 /*
   2  * Zlib (RFC1950 / RFC1951) compression for PuTTY.
   3  *
   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
   9  * existing code.
  10  *
  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.
  15  *
  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.
  23  *
  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.
  31  *
  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
  37  * again.
  38  */
  39
  40 #include <stdlib.h>
  41 #include <assert.h>
  42
  43 #ifdef ZLIB_STANDALONE
  44
  45 /*
  46  * This module also makes a handy zlib decoding tool for when
  47  * you're picking apart Zip files or PDFs or PNGs. If you compile
  48  * it with ZLIB_STANDALONE defined, it builds on its own and
  49  * becomes a command-line utility.
  50  *
  51  * Therefore, here I provide a self-contained implementation of the
  52  * macros required from the rest of the PuTTY sources.
  53  */
  54 #define snew(type) ( (type *) malloc(sizeof(type)) )
  55 #define snewn(n, type) ( (type *) malloc((n) * sizeof(type)) )
  56 #define sresize(x, n, type) ( (type *) realloc((x), (n) * sizeof(type)) )
  57 #define sfree(x) ( free((x)) )
  58
  59 #else
  60 #include "ssh.h"
  61 #endif
  62
  63 #ifndef FALSE
  64 #define FALSE 0
  65 #define TRUE (!FALSE)
  66 #endif
  67
  68 /* ----------------------------------------------------------------------
  69  * Basic LZ77 code. This bit is designed modularly, so it could be
  70  * ripped out and used in a different LZ77 compressor. Go to it,
  71  * and good luck :-)
  72  */
  73
  74 struct LZ77InternalContext;
  75 struct LZ77Context {
  76     struct LZ77InternalContext *ictx;
  77     void *userdata;
  78     void (*literal) (struct LZ77Context * ctx, unsigned char c);
  79     void (*match) (struct LZ77Context * ctx, int distance, int len);
  80 };
  81
  82 /*
  83  * Initialise the private fields of an LZ77Context. It's up to the
  84  * user to initialise the public fields.
  85  */
  86 static int lz77_init(struct LZ77Context *ctx);
  87
  88 /*
  89  * Supply data to be compressed. Will update the private fields of
  90  * the LZ77Context, and will call literal() and match() to output.
  91  * If `compress' is FALSE, it will never emit a match, but will
  92  * instead call literal() for everything.
  93  */
  94 static void lz77_compress(struct LZ77Context *ctx,
  95                           unsigned char *data, int len, int compress);
  96
  97 /*
  98  * Modifiable parameters.
  99  */
 100 #define WINSIZE 32768                  /* window size. Must be power of 2! */
 101 #define HASHMAX 2039                   /* one more than max hash value */
 102 #define MAXMATCH 32                    /* how many matches we track */
 103 #define HASHCHARS 3                    /* how many chars make a hash */
 104
 105 /*
 106  * This compressor takes a less slapdash approach than the
 107  * gzip/zlib one. Rather than allowing our hash chains to fall into
 108  * disuse near the far end, we keep them doubly linked so we can
 109  * _find_ the far end, and then every time we add a new byte to the
 110  * window (thus rolling round by one and removing the previous
 111  * byte), we can carefully remove the hash chain entry.
 112  */
 113
 114 #define INVALID -1                     /* invalid hash _and_ invalid offset */
 115 struct WindowEntry {
 116     short next, prev;                  /* array indices within the window */
 117     short hashval;
 118 };
 119
 120 struct HashEntry {
 121     short first;                       /* window index of first in chain */
 122 };
 123
 124 struct Match {
 125     int distance, len;
 126 };
 127
 128 struct LZ77InternalContext {
 129     struct WindowEntry win[WINSIZE];
 130     unsigned char data[WINSIZE];
 131     int winpos;
 132     struct HashEntry hashtab[HASHMAX];
 133     unsigned char pending[HASHCHARS];
 134     int npending;
 135 };
 136
 137 static int lz77_hash(unsigned char *data)
 138 {
 139     return (257 * data[0] + 263 * data[1] + 269 * data[2]) % HASHMAX;
 140 }
 141
 142 static int lz77_init(struct LZ77Context *ctx)
 143 {
 144     struct LZ77InternalContext *st;
 145     int i;
 146
 147     st = snew(struct LZ77InternalContext);
 148     if (!st)
 149         return 0;
 150
 151     ctx->ictx = st;
 152
 153     for (i = 0; i < WINSIZE; i++)
 154         st->win[i].next = st->win[i].prev = st->win[i].hashval = INVALID;
 155     for (i = 0; i < HASHMAX; i++)
 156         st->hashtab[i].first = INVALID;
 157     st->winpos = 0;
 158
 159     st->npending = 0;
 160
 161     return 1;
 162 }
 163
 164 static void lz77_advance(struct LZ77InternalContext *st,
 165                          unsigned char c, int hash)
 166 {
 167     int off;
 168
 169     /*
 170      * Remove the hash entry at winpos from the tail of its chain,
 171      * or empty the chain if it's the only thing on the chain.
 172      */
 173     if (st->win[st->winpos].prev != INVALID) {
 174         st->win[st->win[st->winpos].prev].next = INVALID;
 175     } else if (st->win[st->winpos].hashval != INVALID) {
 176         st->hashtab[st->win[st->winpos].hashval].first = INVALID;
 177     }
 178
 179     /*
 180      * Create a new entry at winpos and add it to the head of its
 181      * hash chain.
 182      */
 183     st->win[st->winpos].hashval = hash;
 184     st->win[st->winpos].prev = INVALID;
 185     off = st->win[st->winpos].next = st->hashtab[hash].first;
 186     st->hashtab[hash].first = st->winpos;
 187     if (off != INVALID)
 188         st->win[off].prev = st->winpos;
 189     st->data[st->winpos] = c;
 190
 191     /*
 192      * Advance the window pointer.
 193      */
 194     st->winpos = (st->winpos + 1) & (WINSIZE - 1);
 195 }
 196
 197 #define CHARAT(k) ( (k)<0 ? st->data[(st->winpos+k)&(WINSIZE-1)] : data[k] )
 198
 199 static void lz77_compress(struct LZ77Context *ctx,
 200                           unsigned char *data, int len, int compress)
 201 {
 202     struct LZ77InternalContext *st = ctx->ictx;
 203     int i, hash, distance, off, nmatch, matchlen, advance;
 204     struct Match defermatch, matches[MAXMATCH];
 205     int deferchr;
 206
 207     /*
 208      * Add any pending characters from last time to the window. (We
 209      * might not be able to.)
 210      */
 211     for (i = 0; i < st->npending; i++) {
 212         unsigned char foo[HASHCHARS];
 213         int j;
 214         if (len + st->npending - i < HASHCHARS) {
 215             /* Update the pending array. */
 216             for (j = i; j < st->npending; j++)
 217                 st->pending[j - i] = st->pending[j];
 218             break;
 219         }
 220         for (j = 0; j < HASHCHARS; j++)
 221             foo[j] = (i + j < st->npending ? st->pending[i + j] :
 222                       data[i + j - st->npending]);
 223         lz77_advance(st, foo[0], lz77_hash(foo));
 224     }
 225     st->npending -= i;
 226
 227     defermatch.distance = 0; /* appease compiler */
 228     defermatch.len = 0;
 229     deferchr = '\0';
 230     while (len > 0) {
 231
 232         /* Don't even look for a match, if we're not compressing. */
 233         if (compress && len >= HASHCHARS) {
 234             /*
 235              * Hash the next few characters.
 236              */
 237             hash = lz77_hash(data);
 238
 239             /*
 240              * Look the hash up in the corresponding hash chain and see
 241              * what we can find.
 242              */
 243             nmatch = 0;
 244             for (off = st->hashtab[hash].first;
 245                  off != INVALID; off = st->win[off].next) {
 246                 /* distance = 1       if off == st->winpos-1 */
 247                 /* distance = WINSIZE if off == st->winpos   */
 248                 distance =
 249                     WINSIZE - (off + WINSIZE - st->winpos) % WINSIZE;
 250                 for (i = 0; i < HASHCHARS; i++)
 251                     if (CHARAT(i) != CHARAT(i - distance))
 252                         break;
 253                 if (i == HASHCHARS) {
 254                     matches[nmatch].distance = distance;
 255                     matches[nmatch].len = 3;
 256                     if (++nmatch >= MAXMATCH)
 257                         break;
 258                 }
 259             }
 260         } else {
 261             nmatch = 0;
 262             hash = INVALID;
 263         }
 264
 265         if (nmatch > 0) {
 266             /*
 267              * We've now filled up matches[] with nmatch potential
 268              * matches. Follow them down to find the longest. (We
 269              * assume here that it's always worth favouring a
 270              * longer match over a shorter one.)
 271              */
 272             matchlen = HASHCHARS;
 273             while (matchlen < len) {
 274                 int j;
 275                 for (i = j = 0; i < nmatch; i++) {
 276                     if (CHARAT(matchlen) ==
 277                         CHARAT(matchlen - matches[i].distance)) {
 278                         matches[j++] = matches[i];
 279                     }
 280                 }
 281                 if (j == 0)
 282                     break;
 283                 matchlen++;
 284                 nmatch = j;
 285             }
 286
 287             /*
 288              * We've now got all the longest matches. We favour the
 289              * shorter distances, which means we go with matches[0].
 290              * So see if we want to defer it or throw it away.
 291              */
 292             matches[0].len = matchlen;
 293             if (defermatch.len > 0) {
 294                 if (matches[0].len > defermatch.len + 1) {
 295                     /* We have a better match. Emit the deferred char,
 296                      * and defer this match. */
 297                     ctx->literal(ctx, (unsigned char) deferchr);
 298                     defermatch = matches[0];
 299                     deferchr = data[0];
 300                     advance = 1;
 301                 } else {
 302                     /* We don't have a better match. Do the deferred one. */
 303                     ctx->match(ctx, defermatch.distance, defermatch.len);
 304                     advance = defermatch.len - 1;
 305                     defermatch.len = 0;
 306                 }
 307             } else {
 308                 /* There was no deferred match. Defer this one. */
 309                 defermatch = matches[0];
 310                 deferchr = data[0];
 311                 advance = 1;
 312             }
 313         } else {
 314             /*
 315              * We found no matches. Emit the deferred match, if
 316              * any; otherwise emit a literal.
 317              */
 318             if (defermatch.len > 0) {
 319                 ctx->match(ctx, defermatch.distance, defermatch.len);
 320                 advance = defermatch.len - 1;
 321                 defermatch.len = 0;
 322             } else {
 323                 ctx->literal(ctx, data[0]);
 324                 advance = 1;
 325             }
 326         }
 327
 328         /*
 329          * Now advance the position by `advance' characters,
 330          * keeping the window and hash chains consistent.
 331          */
 332         while (advance > 0) {
 333             if (len >= HASHCHARS) {
 334                 lz77_advance(st, *data, lz77_hash(data));
 335             } else {
 336                 st->pending[st->npending++] = *data;
 337             }
 338             data++;
 339             len--;
 340             advance--;
 341         }
 342     }
 343 }
 344
 345 /* ----------------------------------------------------------------------
 346  * Zlib compression. We always use the static Huffman tree option.
 347  * Mostly this is because it's hard to scan a block in advance to
 348  * work out better trees; dynamic trees are great when you're
 349  * compressing a large file under no significant time constraint,
 350  * but when you're compressing little bits in real time, things get
 351  * hairier.
 352  *
 353  * I suppose it's possible that I could compute Huffman trees based
 354  * on the frequencies in the _previous_ block, as a sort of
 355  * heuristic, but I'm not confident that the gain would balance out
 356  * having to transmit the trees.
 357  */
 358
 359 struct Outbuf {
 360     unsigned char *outbuf;
 361     int outlen, outsize;
 362     unsigned long outbits;
 363     int noutbits;
 364     int firstblock;
 365     int comp_disabled;
 366 };
 367
 368 static void outbits(struct Outbuf *out, unsigned long bits, int nbits)
 369 {
 370     assert(out->noutbits + nbits <= 32);
 371     out->outbits |= bits << out->noutbits;
 372     out->noutbits += nbits;
 373     while (out->noutbits >= 8) {
 374         if (out->outlen >= out->outsize) {
 375             out->outsize = out->outlen + 64;
 376             out->outbuf = sresize(out->outbuf, out->outsize, unsigned char);
 377         }
 378         out->outbuf[out->outlen++] = (unsigned char) (out->outbits & 0xFF);
 379         out->outbits >>= 8;
 380         out->noutbits -= 8;
 381     }
 382 }
 383
 384 static const unsigned char mirrorbytes[256] = {
 385     0x00, 0x80, 0x40, 0xc0, 0x20, 0xa0, 0x60, 0xe0,
 386     0x10, 0x90, 0x50, 0xd0, 0x30, 0xb0, 0x70, 0xf0,
 387     0x08, 0x88, 0x48, 0xc8, 0x28, 0xa8, 0x68, 0xe8,
 388     0x18, 0x98, 0x58, 0xd8, 0x38, 0xb8, 0x78, 0xf8,
 389     0x04, 0x84, 0x44, 0xc4, 0x24, 0xa4, 0x64, 0xe4,
 390     0x14, 0x94, 0x54, 0xd4, 0x34, 0xb4, 0x74, 0xf4,
 391     0x0c, 0x8c, 0x4c, 0xcc, 0x2c, 0xac, 0x6c, 0xec,
 392     0x1c, 0x9c, 0x5c, 0xdc, 0x3c, 0xbc, 0x7c, 0xfc,
 393     0x02, 0x82, 0x42, 0xc2, 0x22, 0xa2, 0x62, 0xe2,
 394     0x12, 0x92, 0x52, 0xd2, 0x32, 0xb2, 0x72, 0xf2,
 395     0x0a, 0x8a, 0x4a, 0xca, 0x2a, 0xaa, 0x6a, 0xea,
 396     0x1a, 0x9a, 0x5a, 0xda, 0x3a, 0xba, 0x7a, 0xfa,
 397     0x06, 0x86, 0x46, 0xc6, 0x26, 0xa6, 0x66, 0xe6,
 398     0x16, 0x96, 0x56, 0xd6, 0x36, 0xb6, 0x76, 0xf6,
 399     0x0e, 0x8e, 0x4e, 0xce, 0x2e, 0xae, 0x6e, 0xee,
 400     0x1e, 0x9e, 0x5e, 0xde, 0x3e, 0xbe, 0x7e, 0xfe,
 401     0x01, 0x81, 0x41, 0xc1, 0x21, 0xa1, 0x61, 0xe1,
 402     0x11, 0x91, 0x51, 0xd1, 0x31, 0xb1, 0x71, 0xf1,
 403     0x09, 0x89, 0x49, 0xc9, 0x29, 0xa9, 0x69, 0xe9,
 404     0x19, 0x99, 0x59, 0xd9, 0x39, 0xb9, 0x79, 0xf9,
 405     0x05, 0x85, 0x45, 0xc5, 0x25, 0xa5, 0x65, 0xe5,
 406     0x15, 0x95, 0x55, 0xd5, 0x35, 0xb5, 0x75, 0xf5,
 407     0x0d, 0x8d, 0x4d, 0xcd, 0x2d, 0xad, 0x6d, 0xed,
 408     0x1d, 0x9d, 0x5d, 0xdd, 0x3d, 0xbd, 0x7d, 0xfd,
 409     0x03, 0x83, 0x43, 0xc3, 0x23, 0xa3, 0x63, 0xe3,
 410     0x13, 0x93, 0x53, 0xd3, 0x33, 0xb3, 0x73, 0xf3,
 411     0x0b, 0x8b, 0x4b, 0xcb, 0x2b, 0xab, 0x6b, 0xeb,
 412     0x1b, 0x9b, 0x5b, 0xdb, 0x3b, 0xbb, 0x7b, 0xfb,
 413     0x07, 0x87, 0x47, 0xc7, 0x27, 0xa7, 0x67, 0xe7,
 414     0x17, 0x97, 0x57, 0xd7, 0x37, 0xb7, 0x77, 0xf7,
 415     0x0f, 0x8f, 0x4f, 0xcf, 0x2f, 0xaf, 0x6f, 0xef,
 416     0x1f, 0x9f, 0x5f, 0xdf, 0x3f, 0xbf, 0x7f, 0xff,
 417 };
 418
 419 typedef struct {
 420     short code, extrabits;
 421     int min, max;
 422 } coderecord;
 423
 424 static const coderecord lencodes[] = {
 425     {257, 0, 3, 3},
 426     {258, 0, 4, 4},
 427     {259, 0, 5, 5},
 428     {260, 0, 6, 6},
 429     {261, 0, 7, 7},
 430     {262, 0, 8, 8},
 431     {263, 0, 9, 9},
 432     {264, 0, 10, 10},
 433     {265, 1, 11, 12},
 434     {266, 1, 13, 14},
 435     {267, 1, 15, 16},
 436     {268, 1, 17, 18},
 437     {269, 2, 19, 22},
 438     {270, 2, 23, 26},
 439     {271, 2, 27, 30},
 440     {272, 2, 31, 34},
 441     {273, 3, 35, 42},
 442     {274, 3, 43, 50},
 443     {275, 3, 51, 58},
 444     {276, 3, 59, 66},
 445     {277, 4, 67, 82},
 446     {278, 4, 83, 98},
 447     {279, 4, 99, 114},
 448     {280, 4, 115, 130},
 449     {281, 5, 131, 162},
 450     {282, 5, 163, 194},
 451     {283, 5, 195, 226},
 452     {284, 5, 227, 257},
 453     {285, 0, 258, 258},
 454 };
 455
 456 static const coderecord distcodes[] = {
 457     {0, 0, 1, 1},
 458     {1, 0, 2, 2},
 459     {2, 0, 3, 3},
 460     {3, 0, 4, 4},
 461     {4, 1, 5, 6},
 462     {5, 1, 7, 8},
 463     {6, 2, 9, 12},
 464     {7, 2, 13, 16},
 465     {8, 3, 17, 24},
 466     {9, 3, 25, 32},
 467     {10, 4, 33, 48},
 468     {11, 4, 49, 64},
 469     {12, 5, 65, 96},
 470     {13, 5, 97, 128},
 471     {14, 6, 129, 192},
 472     {15, 6, 193, 256},
 473     {16, 7, 257, 384},
 474     {17, 7, 385, 512},
 475     {18, 8, 513, 768},
 476     {19, 8, 769, 1024},
 477     {20, 9, 1025, 1536},
 478     {21, 9, 1537, 2048},
 479     {22, 10, 2049, 3072},
 480     {23, 10, 3073, 4096},
 481     {24, 11, 4097, 6144},
 482     {25, 11, 6145, 8192},
 483     {26, 12, 8193, 12288},
 484     {27, 12, 12289, 16384},
 485     {28, 13, 16385, 24576},
 486     {29, 13, 24577, 32768},
 487 };
 488
 489 static void zlib_literal(struct LZ77Context *ectx, unsigned char c)
 490 {
 491     struct Outbuf *out = (struct Outbuf *) ectx->userdata;
 492
 493     if (out->comp_disabled) {
 494         /*
 495          * We're in an uncompressed block, so just output the byte.
 496          */
 497         outbits(out, c, 8);
 498         return;
 499     }
 500
 501     if (c <= 143) {
 502         /* 0 through 143 are 8 bits long starting at 00110000. */
 503         outbits(out, mirrorbytes[0x30 + c], 8);
 504     } else {
 505         /* 144 through 255 are 9 bits long starting at 110010000. */
 506         outbits(out, 1 + 2 * mirrorbytes[0x90 - 144 + c], 9);
 507     }
 508 }
 509
 510 static void zlib_match(struct LZ77Context *ectx, int distance, int len)
 511 {
 512     const coderecord *d, *l;
 513     int i, j, k;
 514     struct Outbuf *out = (struct Outbuf *) ectx->userdata;
 515
 516     assert(!out->comp_disabled);
 517
 518     while (len > 0) {
 519         int thislen;
 520
 521         /*
 522          * We can transmit matches of lengths 3 through 258
 523          * inclusive. So if len exceeds 258, we must transmit in
 524          * several steps, with 258 or less in each step.
 525          *
 526          * Specifically: if len >= 261, we can transmit 258 and be
 527          * sure of having at least 3 left for the next step. And if
 528          * len <= 258, we can just transmit len. But if len == 259
 529          * or 260, we must transmit len-3.
 530          */
 531         thislen = (len > 260 ? 258 : len <= 258 ? len : len - 3);
 532         len -= thislen;
 533
 534         /*
 535          * Binary-search to find which length code we're
 536          * transmitting.
 537          */
 538         i = -1;
 539         j = sizeof(lencodes) / sizeof(*lencodes);
 540         while (1) {
 541             assert(j - i >= 2);
 542             k = (j + i) / 2;
 543             if (thislen < lencodes[k].min)
 544                 j = k;
 545             else if (thislen > lencodes[k].max)
 546                 i = k;
 547             else {
 548                 l = &lencodes[k];
 549                 break;                 /* found it! */
 550             }
 551         }
 552
 553         /*
 554          * Transmit the length code. 256-279 are seven bits
 555          * starting at 0000000; 280-287 are eight bits starting at
 556          * 11000000.
 557          */
 558         if (l->code <= 279) {
 559             outbits(out, mirrorbytes[(l->code - 256) * 2], 7);
 560         } else {
 561             outbits(out, mirrorbytes[0xc0 - 280 + l->code], 8);
 562         }
 563
 564         /*
 565          * Transmit the extra bits.
 566          */
 567         if (l->extrabits)
 568             outbits(out, thislen - l->min, l->extrabits);
 569
 570         /*
 571          * Binary-search to find which distance code we're
 572          * transmitting.
 573          */
 574         i = -1;
 575         j = sizeof(distcodes) / sizeof(*distcodes);
 576         while (1) {
 577             assert(j - i >= 2);
 578             k = (j + i) / 2;
 579             if (distance < distcodes[k].min)
 580                 j = k;
 581             else if (distance > distcodes[k].max)
 582                 i = k;
 583             else {
 584                 d = &distcodes[k];
 585                 break;                 /* found it! */
 586             }
 587         }
 588
 589         /*
 590          * Transmit the distance code. Five bits starting at 00000.
 591          */
 592         outbits(out, mirrorbytes[d->code * 8], 5);
 593
 594         /*
 595          * Transmit the extra bits.
 596          */
 597         if (d->extrabits)
 598             outbits(out, distance - d->min, d->extrabits);
 599     }
 600 }
 601
 602 void *zlib_compress_init(void)
 603 {
 604     struct Outbuf *out;
 605     struct LZ77Context *ectx = snew(struct LZ77Context);
 606
 607     lz77_init(ectx);
 608     ectx->literal = zlib_literal;
 609     ectx->match = zlib_match;
 610
 611     out = snew(struct Outbuf);
 612     out->outbits = out->noutbits = 0;
 613     out->firstblock = 1;
 614     out->comp_disabled = FALSE;
 615     ectx->userdata = out;
 616
 617     return ectx;
 618 }
 619
 620 void zlib_compress_cleanup(void *handle)
 621 {
 622     struct LZ77Context *ectx = (struct LZ77Context *)handle;
 623     sfree(ectx->userdata);
 624     sfree(ectx->ictx);
 625     sfree(ectx);
 626 }
 627
 628 /*
 629  * Turn off actual LZ77 analysis for one block, to facilitate
 630  * construction of a precise-length IGNORE packet. Returns the
 631  * length adjustment (which is only valid for packets < 65536
 632  * bytes, but that seems reasonable enough).
 633  */
 634 static int zlib_disable_compression(void *handle)
 635 {
 636     struct LZ77Context *ectx = (struct LZ77Context *)handle;
 637     struct Outbuf *out = (struct Outbuf *) ectx->userdata;
 638     int n;
 639
 640     out->comp_disabled = TRUE;
 641
 642     n = 0;
 643     /*
 644      * If this is the first block, we will start by outputting two
 645      * header bytes, and then three bits to begin an uncompressed
 646      * block. This will cost three bytes (because we will start on
 647      * a byte boundary, this is certain).
 648      */
 649     if (out->firstblock) {
 650         n = 3;
 651     } else {
 652         /*
 653          * Otherwise, we will output seven bits to close the
 654          * previous static block, and _then_ three bits to begin an
 655          * uncompressed block, and then flush the current byte.
 656          * This may cost two bytes or three, depending on noutbits.
 657          */
 658         n += (out->noutbits + 10) / 8;
 659     }
 660
 661     /*
 662      * Now we output four bytes for the length / ~length pair in
 663      * the uncompressed block.
 664      */
 665     n += 4;
 666
 667     return n;
 668 }
 669
 670 int zlib_compress_block(void *handle, unsigned char *block, int len,
 671                         unsigned char **outblock, int *outlen)
 672 {
 673     struct LZ77Context *ectx = (struct LZ77Context *)handle;
 674     struct Outbuf *out = (struct Outbuf *) ectx->userdata;
 675     int in_block;
 676
 677     out->outbuf = NULL;
 678     out->outlen = out->outsize = 0;
 679
 680     /*
 681      * If this is the first block, output the Zlib (RFC1950) header
 682      * bytes 78 9C. (Deflate compression, 32K window size, default
 683      * algorithm.)
 684      */
 685     if (out->firstblock) {
 686         outbits(out, 0x9C78, 16);
 687         out->firstblock = 0;
 688
 689         in_block = FALSE;
 690     } else
 691         in_block = TRUE;
 692
 693     if (out->comp_disabled) {
 694         if (in_block)
 695             outbits(out, 0, 7);        /* close static block */
 696
 697         while (len > 0) {
 698             int blen = (len < 65535 ? len : 65535);
 699
 700             /*
 701              * Start a Deflate (RFC1951) uncompressed block. We
 702              * transmit a zero bit (BFINAL=0), followed by two more
 703              * zero bits (BTYPE=00). Of course these are in the
 704              * wrong order (00 0), not that it matters.
 705              */
 706             outbits(out, 0, 3);
 707
 708             /*
 709              * Output zero bits to align to a byte boundary.
 710              */
 711             if (out->noutbits)
 712                 outbits(out, 0, 8 - out->noutbits);
 713
 714             /*
 715              * Output the block length, and then its one's
 716              * complement. They're little-endian, so all we need to
 717              * do is pass them straight to outbits() with bit count
 718              * 16.
 719              */
 720             outbits(out, blen, 16);
 721             outbits(out, blen ^ 0xFFFF, 16);
 722
 723             /*
 724              * Do the `compression': we need to pass the data to
 725              * lz77_compress so that it will be taken into account
 726              * for subsequent (distance,length) pairs. But
 727              * lz77_compress is passed FALSE, which means it won't
 728              * actually find (or even look for) any matches; so
 729              * every character will be passed straight to
 730              * zlib_literal which will spot out->comp_disabled and
 731              * emit in the uncompressed format.
 732              */
 733             lz77_compress(ectx, block, blen, FALSE);
 734
 735             len -= blen;
 736             block += blen;
 737         }
 738         outbits(out, 2, 3);            /* open new block */
 739     } else {
 740         if (!in_block) {
 741             /*
 742              * Start a Deflate (RFC1951) fixed-trees block. We
 743              * transmit a zero bit (BFINAL=0), followed by a zero
 744              * bit and a one bit (BTYPE=01). Of course these are in
 745              * the wrong order (01 0).
 746              */
 747             outbits(out, 2, 3);
 748         }
 749
 750         /*
 751          * Do the compression.
 752          */
 753         lz77_compress(ectx, block, len, TRUE);
 754
 755         /*
 756          * End the block (by transmitting code 256, which is
 757          * 0000000 in fixed-tree mode), and transmit some empty
 758          * blocks to ensure we have emitted the byte containing the
 759          * last piece of genuine data. There are three ways we can
 760          * do this:
 761          *
 762          *  - Minimal flush. Output end-of-block and then open a
 763          *    new static block. This takes 9 bits, which is
 764          *    guaranteed to flush out the last genuine code in the
 765          *    closed block; but allegedly zlib can't handle it.
 766          *
 767          *  - Zlib partial flush. Output EOB, open and close an
 768          *    empty static block, and _then_ open the new block.
 769          *    This is the best zlib can handle.
 770          *
 771          *  - Zlib sync flush. Output EOB, then an empty
 772          *    _uncompressed_ block (000, then sync to byte
 773          *    boundary, then send bytes 00 00 FF FF). Then open the
 774          *    new block.
 775          *
 776          * For the moment, we will use Zlib partial flush.
 777          */
 778         outbits(out, 0, 7);            /* close block */
 779         outbits(out, 2, 3 + 7);        /* empty static block */
 780         outbits(out, 2, 3);            /* open new block */
 781     }
 782
 783     out->comp_disabled = FALSE;
 784
 785     *outblock = out->outbuf;
 786     *outlen = out->outlen;
 787
 788     return 1;
 789 }
 790
 791 /* ----------------------------------------------------------------------
 792  * Zlib decompression. Of course, even though our compressor always
 793  * uses static trees, our _decompressor_ has to be capable of
 794  * handling dynamic trees if it sees them.
 795  */
 796
 797 /*
 798  * The way we work the Huffman decode is to have a table lookup on
 799  * the first N bits of the input stream (in the order they arrive,
 800  * of course, i.e. the first bit of the Huffman code is in bit 0).
 801  * Each table entry lists the number of bits to consume, plus
 802  * either an output code or a pointer to a secondary table.
 803  */
 804 struct zlib_table;
 805 struct zlib_tableentry;
 806
 807 struct zlib_tableentry {
 808     unsigned char nbits;
 809     short code;
 810     struct zlib_table *nexttable;
 811 };
 812
 813 struct zlib_table {
 814     int mask;                          /* mask applied to input bit stream */
 815     struct zlib_tableentry *table;
 816 };
 817
 818 #define MAXCODELEN 16
 819 #define MAXSYMS 288
 820
 821 /*
 822  * Build a single-level decode table for elements
 823  * [minlength,maxlength) of the provided code/length tables, and
 824  * recurse to build subtables.
 825  */
 826 static struct zlib_table *zlib_mkonetab(int *codes, unsigned char *lengths,
 827                                         int nsyms,
 828                                         int pfx, int pfxbits, int bits)
 829 {
 830     struct zlib_table *tab = snew(struct zlib_table);
 831     int pfxmask = (1 << pfxbits) - 1;
 832     int nbits, i, j, code;
 833
 834     tab->table = snewn(1 << bits, struct zlib_tableentry);
 835     tab->mask = (1 << bits) - 1;
 836
 837     for (code = 0; code <= tab->mask; code++) {
 838         tab->table[code].code = -1;
 839         tab->table[code].nbits = 0;
 840         tab->table[code].nexttable = NULL;
 841     }
 842
 843     for (i = 0; i < nsyms; i++) {
 844         if (lengths[i] <= pfxbits || (codes[i] & pfxmask) != pfx)
 845             continue;
 846         code = (codes[i] >> pfxbits) & tab->mask;
 847         for (j = code; j <= tab->mask; j += 1 << (lengths[i] - pfxbits)) {
 848             tab->table[j].code = i;
 849             nbits = lengths[i] - pfxbits;
 850             if (tab->table[j].nbits < nbits)
 851                 tab->table[j].nbits = nbits;
 852         }
 853     }
 854     for (code = 0; code <= tab->mask; code++) {
 855         if (tab->table[code].nbits <= bits)
 856             continue;
 857         /* Generate a subtable. */
 858         tab->table[code].code = -1;
 859         nbits = tab->table[code].nbits - bits;
 860         if (nbits > 7)
 861             nbits = 7;
 862         tab->table[code].nbits = bits;
 863         tab->table[code].nexttable = zlib_mkonetab(codes, lengths, nsyms,
 864                                                    pfx | (code << pfxbits),
 865                                                    pfxbits + bits, nbits);
 866     }
 867
 868     return tab;
 869 }
 870
 871 /*
 872  * Build a decode table, given a set of Huffman tree lengths.
 873  */
 874 static struct zlib_table *zlib_mktable(unsigned char *lengths,
 875                                        int nlengths)
 876 {
 877     int count[MAXCODELEN], startcode[MAXCODELEN], codes[MAXSYMS];
 878     int code, maxlen;
 879     int i, j;
 880
 881     /* Count the codes of each length. */
 882     maxlen = 0;
 883     for (i = 1; i < MAXCODELEN; i++)
 884         count[i] = 0;
 885     for (i = 0; i < nlengths; i++) {
 886         count[lengths[i]]++;
 887         if (maxlen < lengths[i])
 888             maxlen = lengths[i];
 889     }
 890     /* Determine the starting code for each length block. */
 891     code = 0;
 892     for (i = 1; i < MAXCODELEN; i++) {
 893         startcode[i] = code;
 894         code += count[i];
 895         code <<= 1;
 896     }
 897     /* Determine the code for each symbol. Mirrored, of course. */
 898     for (i = 0; i < nlengths; i++) {
 899         code = startcode[lengths[i]]++;
 900         codes[i] = 0;
 901         for (j = 0; j < lengths[i]; j++) {
 902             codes[i] = (codes[i] << 1) | (code & 1);
 903             code >>= 1;
 904         }
 905     }
 906
 907     /*
 908      * Now we have the complete list of Huffman codes. Build a
 909      * table.
 910      */
 911     return zlib_mkonetab(codes, lengths, nlengths, 0, 0,
 912                          maxlen < 9 ? maxlen : 9);
 913 }
 914
 915 static int zlib_freetable(struct zlib_table **ztab)
 916 {
 917     struct zlib_table *tab;
 918     int code;
 919
 920     if (ztab == NULL)
 921         return -1;
 922
 923     if (*ztab == NULL)
 924         return 0;
 925
 926     tab = *ztab;
 927
 928     for (code = 0; code <= tab->mask; code++)
 929         if (tab->table[code].nexttable != NULL)
 930             zlib_freetable(&tab->table[code].nexttable);
 931
 932     sfree(tab->table);
 933     tab->table = NULL;
 934
 935     sfree(tab);
 936     *ztab = NULL;
 937
 938     return (0);
 939 }
 940
 941 struct zlib_decompress_ctx {
 942     struct zlib_table *staticlentable, *staticdisttable;
 943     struct zlib_table *currlentable, *currdisttable, *lenlentable;
 944     enum {
 945         START, OUTSIDEBLK,
 946         TREES_HDR, TREES_LENLEN, TREES_LEN, TREES_LENREP,
 947         INBLK, GOTLENSYM, GOTLEN, GOTDISTSYM,
 948         UNCOMP_LEN, UNCOMP_NLEN, UNCOMP_DATA
 949     } state;
 950     int sym, hlit, hdist, hclen, lenptr, lenextrabits, lenaddon, len,
 951         lenrep;
 952     int uncomplen;
 953     unsigned char lenlen[19];
 954     unsigned char lengths[286 + 32];
 955     unsigned long bits;
 956     int nbits;
 957     unsigned char window[WINSIZE];
 958     int winpos;
 959     unsigned char *outblk;
 960     int outlen, outsize;
 961 };
 962
 963 void *zlib_decompress_init(void)
 964 {
 965     struct zlib_decompress_ctx *dctx = snew(struct zlib_decompress_ctx);
 966     unsigned char lengths[288];
 967
 968     memset(lengths, 8, 144);
 969     memset(lengths + 144, 9, 256 - 144);
 970     memset(lengths + 256, 7, 280 - 256);
 971     memset(lengths + 280, 8, 288 - 280);
 972     dctx->staticlentable = zlib_mktable(lengths, 288);
 973     memset(lengths, 5, 32);
 974     dctx->staticdisttable = zlib_mktable(lengths, 32);
 975     dctx->state = START;                       /* even before header */
 976     dctx->currlentable = dctx->currdisttable = dctx->lenlentable = NULL;
 977     dctx->bits = 0;
 978     dctx->nbits = 0;
 979     dctx->winpos = 0;
 980
 981     return dctx;
 982 }
 983
 984 void zlib_decompress_cleanup(void *handle)
 985 {
 986     struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
 987
 988     if (dctx->currlentable && dctx->currlentable != dctx->staticlentable)
 989         zlib_freetable(&dctx->currlentable);
 990     if (dctx->currdisttable && dctx->currdisttable != dctx->staticdisttable)
 991         zlib_freetable(&dctx->currdisttable);
 992     if (dctx->lenlentable)
 993         zlib_freetable(&dctx->lenlentable);
 994     zlib_freetable(&dctx->staticlentable);
 995     zlib_freetable(&dctx->staticdisttable);
 996     sfree(dctx);
 997 }
 998
 999 static int zlib_huflookup(unsigned long *bitsp, int *nbitsp,
1000                    struct zlib_table *tab)
1001 {
1002     unsigned long bits = *bitsp;
1003     int nbits = *nbitsp;
1004     while (1) {
1005         struct zlib_tableentry *ent;
1006         ent = &tab->table[bits & tab->mask];
1007         if (ent->nbits > nbits)
1008             return -1;                 /* not enough data */
1009         bits >>= ent->nbits;
1010         nbits -= ent->nbits;
1011         if (ent->code == -1)
1012             tab = ent->nexttable;
1013         else {
1014             *bitsp = bits;
1015             *nbitsp = nbits;
1016             return ent->code;
1017         }
1018
1019         if (!tab) {
1020             /*
1021              * There was a missing entry in the table, presumably
1022              * due to an invalid Huffman table description, and the
1023              * subsequent data has attempted to use the missing
1024              * entry. Return a decoding failure.
1025              */
1026             return -2;
1027         }
1028     }
1029 }
1030
1031 static void zlib_emit_char(struct zlib_decompress_ctx *dctx, int c)
1032 {
1033     dctx->window[dctx->winpos] = c;
1034     dctx->winpos = (dctx->winpos + 1) & (WINSIZE - 1);
1035     if (dctx->outlen >= dctx->outsize) {
1036         dctx->outsize = dctx->outlen + 512;
1037         dctx->outblk = sresize(dctx->outblk, dctx->outsize, unsigned char);
1038     }
1039     dctx->outblk[dctx->outlen++] = c;
1040 }
1041
1042 #define EATBITS(n) ( dctx->nbits -= (n), dctx->bits >>= (n) )
1043
1044 int zlib_decompress_block(void *handle, unsigned char *block, int len,
1045                           unsigned char **outblock, int *outlen)
1046 {
1047     struct zlib_decompress_ctx *dctx = (struct zlib_decompress_ctx *)handle;
1048     const coderecord *rec;
1049     int code, blktype, rep, dist, nlen, header;
1050     static const unsigned char lenlenmap[] = {
1051         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
1052     };
1053
1054     dctx->outblk = snewn(256, unsigned char);
1055     dctx->outsize = 256;
1056     dctx->outlen = 0;
1057
1058     while (len > 0 || dctx->nbits > 0) {
1059         while (dctx->nbits < 24 && len > 0) {
1060             dctx->bits |= (*block++) << dctx->nbits;
1061             dctx->nbits += 8;
1062             len--;
1063         }
1064         switch (dctx->state) {
1065           case START:
1066             /* Expect 16-bit zlib header. */
1067             if (dctx->nbits < 16)
1068                 goto finished;         /* done all we can */
1069
1070             /*
1071              * The header is stored as a big-endian 16-bit integer,
1072              * in contrast to the general little-endian policy in
1073              * the rest of the format :-(
1074              */
1075             header = (((dctx->bits & 0xFF00) >> 8) |
1076                       ((dctx->bits & 0x00FF) << 8));
1077             EATBITS(16);
1078
1079             /*
1080              * Check the header:
1081              *
1082              *  - bits 8-11 should be 1000 (Deflate/RFC1951)
1083              *  - bits 12-15 should be at most 0111 (window size)
1084              *  - bit 5 should be zero (no dictionary present)
1085              *  - we don't care about bits 6-7 (compression rate)
1086              *  - bits 0-4 should be set up to make the whole thing
1087              *    a multiple of 31 (checksum).
1088              */
1089             if ((header & 0x0F00) != 0x0800 ||
1090                 (header & 0xF000) >  0x7000 ||
1091                 (header & 0x0020) != 0x0000 ||
1092                 (header % 31) != 0)
1093                 goto decode_error;
1094
1095             dctx->state = OUTSIDEBLK;
1096             break;
1097           case OUTSIDEBLK:
1098             /* Expect 3-bit block header. */
1099             if (dctx->nbits < 3)
1100                 goto finished;         /* done all we can */
1101             EATBITS(1);
1102             blktype = dctx->bits & 3;
1103             EATBITS(2);
1104             if (blktype == 0) {
1105                 int to_eat = dctx->nbits & 7;
1106                 dctx->state = UNCOMP_LEN;
1107                 EATBITS(to_eat);       /* align to byte boundary */
1108             } else if (blktype == 1) {
1109                 dctx->currlentable = dctx->staticlentable;
1110                 dctx->currdisttable = dctx->staticdisttable;
1111                 dctx->state = INBLK;
1112             } else if (blktype == 2) {
1113                 dctx->state = TREES_HDR;
1114             }
1115             break;
1116           case TREES_HDR:
1117             /*
1118              * Dynamic block header. Five bits of HLIT, five of
1119              * HDIST, four of HCLEN.
1120              */
1121             if (dctx->nbits < 5 + 5 + 4)
1122                 goto finished;         /* done all we can */
1123             dctx->hlit = 257 + (dctx->bits & 31);
1124             EATBITS(5);
1125             dctx->hdist = 1 + (dctx->bits & 31);
1126             EATBITS(5);
1127             dctx->hclen = 4 + (dctx->bits & 15);
1128             EATBITS(4);
1129             dctx->lenptr = 0;
1130             dctx->state = TREES_LENLEN;
1131             memset(dctx->lenlen, 0, sizeof(dctx->lenlen));
1132             break;
1133           case TREES_LENLEN:
1134             if (dctx->nbits < 3)
1135                 goto finished;
1136             while (dctx->lenptr < dctx->hclen && dctx->nbits >= 3) {
1137                 dctx->lenlen[lenlenmap[dctx->lenptr++]] =
1138                     (unsigned char) (dctx->bits & 7);
1139                 EATBITS(3);
1140             }
1141             if (dctx->lenptr == dctx->hclen) {
1142                 dctx->lenlentable = zlib_mktable(dctx->lenlen, 19);
1143                 dctx->state = TREES_LEN;
1144                 dctx->lenptr = 0;
1145             }
1146             break;
1147           case TREES_LEN:
1148             if (dctx->lenptr >= dctx->hlit + dctx->hdist) {
1149                 dctx->currlentable = zlib_mktable(dctx->lengths, dctx->hlit);
1150                 dctx->currdisttable = zlib_mktable(dctx->lengths + dctx->hlit,
1151                                                   dctx->hdist);
1152                 zlib_freetable(&dctx->lenlentable);
1153                 dctx->lenlentable = NULL;
1154                 dctx->state = INBLK;
1155                 break;
1156             }
1157             code =
1158                 zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->lenlentable);
1159             if (code == -1)
1160                 goto finished;
1161             if (code == -2)
1162                 goto decode_error;
1163             if (code < 16)
1164                 dctx->lengths[dctx->lenptr++] = code;
1165             else {
1166                 dctx->lenextrabits = (code == 16 ? 2 : code == 17 ? 3 : 7);
1167                 dctx->lenaddon = (code == 18 ? 11 : 3);
1168                 dctx->lenrep = (code == 16 && dctx->lenptr > 0 ?
1169                                dctx->lengths[dctx->lenptr - 1] : 0);
1170                 dctx->state = TREES_LENREP;
1171             }
1172             break;
1173           case TREES_LENREP:
1174             if (dctx->nbits < dctx->lenextrabits)
1175                 goto finished;
1176             rep =
1177                 dctx->lenaddon +
1178                 (dctx->bits & ((1 << dctx->lenextrabits) - 1));
1179             EATBITS(dctx->lenextrabits);
1180             while (rep > 0 && dctx->lenptr < dctx->hlit + dctx->hdist) {
1181                 dctx->lengths[dctx->lenptr] = dctx->lenrep;
1182                 dctx->lenptr++;
1183                 rep--;
1184             }
1185             dctx->state = TREES_LEN;
1186             break;
1187           case INBLK:
1188             code =
1189                 zlib_huflookup(&dctx->bits, &dctx->nbits, dctx->currlentable);
1190             if (code == -1)
1191                 goto finished;
1192             if (code == -2)
1193                 goto decode_error;
1194             if (code < 256)
1195                 zlib_emit_char(dctx, code);
1196             else if (code == 256) {
1197                 dctx->state = OUTSIDEBLK;
1198                 if (dctx->currlentable != dctx->staticlentable) {
1199                     zlib_freetable(&dctx->currlentable);
1200                     dctx->currlentable = NULL;
1201                 }
1202                 if (dctx->currdisttable != dctx->staticdisttable) {
1203                     zlib_freetable(&dctx->currdisttable);
1204                     dctx->currdisttable = NULL;
1205                 }
1206             } else if (code < 286) {   /* static tree can give >285; ignore */
1207                 dctx->state = GOTLENSYM;
1208                 dctx->sym = code;
1209             }
1210             break;
1211           case GOTLENSYM:
1212             rec = &lencodes[dctx->sym - 257];
1213             if (dctx->nbits < rec->extrabits)
1214                 goto finished;
1215             dctx->len =
1216                 rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
1217             EATBITS(rec->extrabits);
1218             dctx->state = GOTLEN;
1219             break;
1220           case GOTLEN:
1221             code =
1222                 zlib_huflookup(&dctx->bits, &dctx->nbits,
1223                                dctx->currdisttable);
1224             if (code == -1)
1225                 goto finished;
1226             if (code == -2)
1227                 goto decode_error;
1228             dctx->state = GOTDISTSYM;
1229             dctx->sym = code;
1230             break;
1231           case GOTDISTSYM:
1232             rec = &distcodes[dctx->sym];
1233             if (dctx->nbits < rec->extrabits)
1234                 goto finished;
1235             dist = rec->min + (dctx->bits & ((1 << rec->extrabits) - 1));
1236             EATBITS(rec->extrabits);
1237             dctx->state = INBLK;
1238             while (dctx->len--)
1239                 zlib_emit_char(dctx, dctx->window[(dctx->winpos - dist) &
1240                                                   (WINSIZE - 1)]);
1241             break;
1242           case UNCOMP_LEN:
1243             /*
1244              * Uncompressed block. We expect to see a 16-bit LEN.
1245              */
1246             if (dctx->nbits < 16)
1247                 goto finished;
1248             dctx->uncomplen = dctx->bits & 0xFFFF;
1249             EATBITS(16);
1250             dctx->state = UNCOMP_NLEN;
1251             break;
1252           case UNCOMP_NLEN:
1253             /*
1254              * Uncompressed block. We expect to see a 16-bit NLEN,
1255              * which should be the one's complement of the previous
1256              * LEN.
1257              */
1258             if (dctx->nbits < 16)
1259                 goto finished;
1260             nlen = dctx->bits & 0xFFFF;
1261             EATBITS(16);
1262             if (dctx->uncomplen != (nlen ^ 0xFFFF))
1263                 goto decode_error;
1264             if (dctx->uncomplen == 0)
1265                 dctx->state = OUTSIDEBLK;       /* block is empty */
1266             else
1267                 dctx->state = UNCOMP_DATA;
1268             break;
1269           case UNCOMP_DATA:
1270             if (dctx->nbits < 8)
1271                 goto finished;
1272             zlib_emit_char(dctx, dctx->bits & 0xFF);
1273             EATBITS(8);
1274             if (--dctx->uncomplen == 0)
1275                 dctx->state = OUTSIDEBLK;       /* end of uncompressed block */
1276             break;
1277         }
1278     }
1279
1280   finished:
1281     *outblock = dctx->outblk;
1282     *outlen = dctx->outlen;
1283     return 1;
1284
1285   decode_error:
1286     sfree(dctx->outblk);
1287     *outblock = dctx->outblk = NULL;
1288     *outlen = 0;
1289     return 0;
1290 }
1291
1292 #ifdef ZLIB_STANDALONE
1293
1294 #include <stdio.h>
1295 #include <string.h>
1296
1297 int main(int argc, char **argv)
1298 {
1299     unsigned char buf[16], *outbuf;
1300     int ret, outlen;
1301     void *handle;
1302     int noheader = FALSE, opts = TRUE;
1303     char *filename = NULL;
1304     FILE *fp;
1305
1306     while (--argc) {
1307         char *p = *++argv;
1308
1309         if (p[0] == '-' && opts) {
1310             if (!strcmp(p, "-d"))
1311                 noheader = TRUE;
1312             else if (!strcmp(p, "--"))
1313                 opts = FALSE;          /* next thing is filename */
1314             else {
1315                 fprintf(stderr, "unknown command line option '%s'\n", p);
1316                 return 1;
1317             }
1318         } else if (!filename) {
1319             filename = p;
1320         } else {
1321             fprintf(stderr, "can only handle one filename\n");
1322             return 1;
1323         }
1324     }
1325
1326     handle = zlib_decompress_init();
1327
1328     if (noheader) {
1329         /*
1330          * Provide missing zlib header if -d was specified.
1331          */
1332         zlib_decompress_block(handle, "\x78\x9C", 2, &outbuf, &outlen);
1333         assert(outlen == 0);
1334     }
1335
1336     if (filename)
1337         fp = fopen(filename, "rb");
1338     else
1339         fp = stdin;
1340
1341     if (!fp) {
1342         assert(filename);
1343         fprintf(stderr, "unable to open '%s'\n", filename);
1344         return 1;
1345     }
1346
1347     while (1) {
1348         ret = fread(buf, 1, sizeof(buf), fp);
1349         if (ret <= 0)
1350             break;
1351         zlib_decompress_block(handle, buf, ret, &outbuf, &outlen);
1352         if (outbuf) {
1353             if (outlen)
1354                 fwrite(outbuf, 1, outlen, stdout);
1355             sfree(outbuf);
1356         } else {
1357             fprintf(stderr, "decoding error\n");
1358             return 1;
1359         }
1360     }
1361
1362     zlib_decompress_cleanup(handle);
1363
1364     if (filename)
1365         fclose(fp);
1366
1367     return 0;
1368 }
1369
1370 #else
1371
1372 const struct ssh_compress ssh_zlib = {
1373     "zlib",
1374     "zlib@openssh.com", /* delayed version */
1375     zlib_compress_init,
1376     zlib_compress_cleanup,
1377     zlib_compress_block,
1378     zlib_decompress_init,
1379     zlib_decompress_cleanup,
1380     zlib_decompress_block,
1381     zlib_disable_compression,
1382     "zlib (RFC1950)"
1383 };
1384
1385 #endif