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