| blob | 9c780a41f6b66b64282127915f9fa52ba6084502 |
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