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