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