sshzlib.c

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