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