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