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