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