putty/SSHZLIB.C

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