Mercurial > hg > toybox
comparison toys/pending/gzip.c @ 1189:95ae2805622f draft
Add Szabolcs Nagy's deflate/inflate code from git://git.suckless.org/flate
Confirmed with him on IRC it's ok to use under toybox license, glued the files
together and hammered square peg into round hole, no other changes yet.
author | Rob Landley <rob@landley.net> |
---|---|
date | Fri, 31 Jan 2014 06:01:30 -0600 |
parents | |
children | 1568ba420f32 |
comparison
equal
deleted
inserted
replaced
1188:cb62f7090473 | 1189:95ae2805622f |
---|---|
1 /* gzip.c - deflate and inflate code rolled into a ball. | |
2 * | |
3 * Copyright 2009 Szabolcs Nagy <nszabolcs@gmail.com> | |
4 * | |
5 * See http://refspecs.linuxfoundation.org/LSB_4.1.0/LSB-Core-generic/LSB-Core-generic/gzip.html | |
6 * And RFCs 1950, 1951, and 1952 | |
7 | |
8 USE_GZIP(NEWTOY(gzip, "qvcdrgzp", TOYFLAG_USR|TOYFLAG_BIN)) | |
9 | |
10 config GZIP | |
11 bool "gzip" | |
12 default n | |
13 help | |
14 usage: gzip [-qvcdrgzp] FILE | |
15 | |
16 Transitional gzip, needs work. Combines gzip, zlib, and pkzip. | |
17 | |
18 -q quiet (default)\n | |
19 -v verbose\n | |
20 -c compress (default)\n | |
21 -d decompress\n | |
22 -r raw (default)\n | |
23 -g gzip\n | |
24 -z zlib\n | |
25 -p pkzip\n | |
26 */ | |
27 | |
28 #define FOR_gzip | |
29 #include "toys.h" | |
30 | |
31 typedef unsigned char uchar; | |
32 typedef unsigned short ushort; | |
33 typedef unsigned int uint; | |
34 | |
35 /* deflate and inflate return values */ | |
36 enum { | |
37 FlateOk = 0, | |
38 FlateErr = -1, | |
39 FlateIn = -2, | |
40 FlateOut = -3 | |
41 }; | |
42 | |
43 typedef struct { | |
44 int nin; | |
45 int nout; | |
46 uchar *in; | |
47 uchar *out; | |
48 char *err; | |
49 void *state; | |
50 } FlateStream; | |
51 | |
52 int deflate(FlateStream *s); | |
53 int inflate(FlateStream *s); | |
54 | |
55 uint adler32(uchar *p, int n, uint adler); | |
56 void crc32init(void); | |
57 uint crc32(uchar *p, int n, uint crc); | |
58 | |
59 uint crctab[256]; | |
60 | |
61 void crc32init(void) { | |
62 static const uint poly = 0xedb88320; | |
63 int i,j; | |
64 | |
65 for (i = 0; i < 256; ++i) { | |
66 uint crc = i; | |
67 | |
68 for (j = 0; j < 8; j++) { | |
69 if (crc & 1) | |
70 crc = (crc >> 1) ^ poly; | |
71 else | |
72 crc >>= 1; | |
73 } | |
74 crctab[i] = crc; | |
75 } | |
76 } | |
77 | |
78 uint crc32(uchar *p, int n, uint crc) { | |
79 uchar *ep = p + n; | |
80 | |
81 crc ^= 0xffffffff; | |
82 while (p < ep) | |
83 crc = crctab[(crc & 0xff) ^ *p++] ^ (crc >> 8); | |
84 return crc ^ 0xffffffff; | |
85 } | |
86 | |
87 enum { | |
88 AdlerBase = 65521, /* largest 16bit prime */ | |
89 AdlerN = 5552 /* max iters before 32bit overflow */ | |
90 }; | |
91 | |
92 uint adler32(uchar *p, int n, uint adler) { | |
93 uint s1 = adler & 0xffff; | |
94 uint s2 = (adler >> 16) & 0xffff; | |
95 uchar *ep; | |
96 int k; | |
97 | |
98 for (; n >= 16; n -= k) { | |
99 k = n < AdlerN ? n : AdlerN; | |
100 k &= ~0xf; | |
101 for (ep = p + k; p < ep; p += 16) { | |
102 s1 += p[0]; | |
103 s2 += s1; | |
104 s1 += p[1]; | |
105 s2 += s1; | |
106 s1 += p[2]; | |
107 s2 += s1; | |
108 s1 += p[3]; | |
109 s2 += s1; | |
110 s1 += p[4]; | |
111 s2 += s1; | |
112 s1 += p[5]; | |
113 s2 += s1; | |
114 s1 += p[6]; | |
115 s2 += s1; | |
116 s1 += p[7]; | |
117 s2 += s1; | |
118 s1 += p[8]; | |
119 s2 += s1; | |
120 s1 += p[9]; | |
121 s2 += s1; | |
122 s1 += p[10]; | |
123 s2 += s1; | |
124 s1 += p[11]; | |
125 s2 += s1; | |
126 s1 += p[12]; | |
127 s2 += s1; | |
128 s1 += p[13]; | |
129 s2 += s1; | |
130 s1 += p[14]; | |
131 s2 += s1; | |
132 s1 += p[15]; | |
133 s2 += s1; | |
134 } | |
135 s1 %= AdlerBase; | |
136 s2 %= AdlerBase; | |
137 } | |
138 if (n) { | |
139 for (ep = p + n; p < ep; p++) { | |
140 s1 += p[0]; | |
141 s2 += s1; | |
142 } | |
143 s1 %= AdlerBase; | |
144 s2 %= AdlerBase; | |
145 } | |
146 return (s2 << 16) + s1; | |
147 } | |
148 | |
149 enum { | |
150 CodeBits = 16, /* max number of bits in a code + 1 */ | |
151 LitlenTableBits = 9, /* litlen code bits used in lookup table */ | |
152 DistTableBits = 6, /* dist code bits used in lookup table */ | |
153 ClenTableBits = 6, /* clen code bits used in lookup table */ | |
154 TableBits = LitlenTableBits, /* log2(lookup table size) */ | |
155 Nlit = 256, /* number of lit codes */ | |
156 Nlen = 29, /* number of len codes */ | |
157 Nlitlen = Nlit+Nlen+3, /* litlen codes + block end + 2 unused */ | |
158 Ndist = 30, /* number of distance codes */ | |
159 Nclen = 19, /* number of code length codes */ | |
160 | |
161 EOB = 256, /* end of block symbol */ | |
162 MinMatch = 3, /* min match length */ | |
163 MaxMatch = 258, /* max match length */ | |
164 WinSize = 1 << 15, /* sliding window size */ | |
165 | |
166 MaxChainLen = 256, /* max length of hash chain */ | |
167 HashBits = 13, | |
168 HashSize = 1 << HashBits, /* hash table size */ | |
169 BigDist = 1 << 12, /* max match distance for short match length */ | |
170 MaxDist = WinSize, | |
171 BlockSize = 1 << 15, /* TODO */ | |
172 SrcSize = 2*WinSize + MaxMatch, | |
173 DstSize = BlockSize + MaxMatch + 6, /* worst case compressed block size */ | |
174 LzSize = 1 << 13, /* lz buffer size */ | |
175 LzGuard = LzSize - 2, | |
176 LzLitFlag = 1 << 15 /* marks literal run length in lz buffer */ | |
177 }; | |
178 | |
179 /* states */ | |
180 enum { | |
181 BlockHead, | |
182 UncompressedBlock, | |
183 CopyUncompressed, | |
184 FixedHuff, | |
185 DynamicHuff, | |
186 DynamicHuffClen, | |
187 DynamicHuffLitlenDist, | |
188 DynamicHuffContinue, | |
189 DecodeBlock, | |
190 DecodeBlockLenBits, | |
191 DecodeBlockDist, | |
192 DecodeBlockDistBits, | |
193 DecodeBlockCopy | |
194 }; | |
195 | |
196 typedef struct { | |
197 short len; /* code length */ | |
198 ushort sym; /* symbol */ | |
199 } Entry; | |
200 | |
201 /* huffman code tree */ | |
202 typedef struct { | |
203 Entry table[1 << TableBits]; /* prefix lookup table */ | |
204 uint nbits; /* prefix length (table size is 1 << nbits) */ | |
205 uint sum; /* full codes in table: sum(count[0..nbits]) */ | |
206 ushort count[CodeBits]; /* number of codes with given length */ | |
207 ushort symbol[Nlitlen]; /* symbols ordered by code length (lexic.) */ | |
208 } Huff; | |
209 | |
210 typedef struct { | |
211 uchar *src; /* input buffer pointer */ | |
212 uchar *srcend; | |
213 | |
214 uint bits; | |
215 uint nbits; | |
216 | |
217 uchar win[WinSize]; /* output window */ | |
218 uint pos; /* window pos */ | |
219 uint posout; /* used for flushing win */ | |
220 | |
221 int state; /* decode state */ | |
222 int final; /* last block flag */ | |
223 char *err; /* TODO: error message */ | |
224 | |
225 /* for decoding dynamic code trees in inflate() */ | |
226 int nlit; | |
227 int ndist; | |
228 int nclen; /* also used in decode_block() */ | |
229 int lenpos; /* also used in decode_block() */ | |
230 uchar lens[Nlitlen + Ndist]; | |
231 | |
232 int fixed; /* fixed code tree flag */ | |
233 Huff lhuff; /* dynamic lit/len huffman code tree */ | |
234 Huff dhuff; /* dynamic distance huffman code tree */ | |
235 } DecodeState; | |
236 | |
237 /* TODO: globals.. initialization is not thread safe */ | |
238 static Huff lhuff; /* fixed lit/len huffman code tree */ | |
239 static Huff dhuff; /* fixed distance huffman code tree */ | |
240 | |
241 /* base offset and extra bits tables */ | |
242 static uchar lenbits[Nlen] = { | |
243 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 | |
244 }; | |
245 static ushort lenbase[Nlen] = { | |
246 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258 | |
247 }; | |
248 static uchar distbits[Ndist] = { | |
249 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 | |
250 }; | |
251 static ushort distbase[Ndist] = { | |
252 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577 | |
253 }; | |
254 | |
255 /* ordering of code lengths */ | |
256 static uchar clenorder[Nclen] = { | |
257 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 | |
258 }; | |
259 | |
260 /* TODO: this or normal inc + reverse() */ | |
261 /* increment bitwise reversed n (msb is bit 0, lsb is bit len-1) */ | |
262 static uint revinc(uint n, uint len) { | |
263 uint i = 1 << (len - 1); | |
264 | |
265 while (n & i) | |
266 i >>= 1; | |
267 if (i) { | |
268 n &= i - 1; | |
269 n |= i; | |
270 } else | |
271 n = 0; | |
272 return n; | |
273 } | |
274 | |
275 /* build huffman code tree from code lengths (each should be < CodeBits) */ | |
276 static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) { | |
277 int offs[CodeBits]; | |
278 int left; | |
279 uint i, c, sum, code, len, min, max; | |
280 ushort *count = huff->count; | |
281 ushort *symbol = huff->symbol; | |
282 Entry *table = huff->table; | |
283 Entry entry; | |
284 | |
285 /* count code lengths */ | |
286 for (i = 0; i < CodeBits; i++) | |
287 count[i] = 0; | |
288 for (i = 0; i < n; i++) | |
289 count[lens[i]]++; | |
290 if (count[0] == n) { | |
291 huff->nbits = table[0].len = 0; | |
292 return 0; | |
293 } | |
294 count[0] = 0; | |
295 | |
296 /* bound code lengths, force nbits to be within the bounds */ | |
297 for (max = CodeBits - 1; max > 0; max--) | |
298 if (count[max] != 0) | |
299 break; | |
300 if (nbits > max) | |
301 nbits = max; | |
302 for (min = 1; min < CodeBits; min++) | |
303 if (count[min] != 0) | |
304 break; | |
305 if (nbits < min) { | |
306 nbits = min; | |
307 if (nbits > TableBits) | |
308 return -1; | |
309 } | |
310 huff->nbits = nbits; | |
311 | |
312 /* check if length is over-subscribed or incomplete */ | |
313 for (left = 1 << min, i = min; i <= max; left <<= 1, i++) { | |
314 left -= count[i]; | |
315 /* left < 0: over-subscribed, left > 0: incomplete */ | |
316 if (left < 0) | |
317 return -1; | |
318 } | |
319 | |
320 for (sum = 0, i = 0; i <= max; i++) { | |
321 offs[i] = sum; | |
322 sum += count[i]; | |
323 } | |
324 /* needed for decoding codes longer than nbits */ | |
325 if (nbits < max) | |
326 huff->sum = offs[nbits + 1]; | |
327 | |
328 /* sort symbols by code length (lexicographic order) */ | |
329 for (i = 0; i < n; i++) | |
330 if (lens[i]) | |
331 symbol[offs[lens[i]]++] = i; | |
332 | |
333 /* lookup table for decoding nbits from input.. */ | |
334 for (i = 0; i < 1 << nbits; i++) | |
335 table[i].len = table[i].sym = 0; | |
336 code = 0; | |
337 /* ..if code is at most nbits (bits are in reverse order, sigh..) */ | |
338 for (len = min; len <= nbits; len++) | |
339 for (c = count[len]; c > 0; c--) { | |
340 entry.len = len; | |
341 entry.sym = *symbol; | |
342 for (i = code; i < 1 << nbits; i += 1 << len) | |
343 table[i] = entry; | |
344 /* next code */ | |
345 symbol++; | |
346 code = revinc(code, len); | |
347 } | |
348 /* ..if code is longer than nbits: values for simple bitwise decode */ | |
349 for (i = 0; code; i++) { | |
350 table[code].len = -1; | |
351 table[code].sym = i << 1; | |
352 code = revinc(code, nbits); | |
353 } | |
354 return 0; | |
355 } | |
356 | |
357 /* fixed huffman code trees (should be done at compile time..) */ | |
358 static void init_fixed_huffs(void) { | |
359 int i; | |
360 uchar lens[Nlitlen]; | |
361 | |
362 for (i = 0; i < 144; i++) | |
363 lens[i] = 8; | |
364 for (; i < 256; i++) | |
365 lens[i] = 9; | |
366 for (; i < 280; i++) | |
367 lens[i] = 7; | |
368 for (; i < Nlitlen; i++) | |
369 lens[i] = 8; | |
370 build_huff(&lhuff, lens, Nlitlen, 8); | |
371 | |
372 for (i = 0; i < Ndist; i++) | |
373 lens[i] = 5; | |
374 build_huff(&dhuff, lens, Ndist, 5); | |
375 } | |
376 | |
377 /* fill *bits with n bits from *src */ | |
378 static int fillbits_fast(uchar **src, uchar *srcend, uint *bits, uint *nbits, uint n) { | |
379 while (*nbits < n) { | |
380 if (*src == srcend) | |
381 return 0; | |
382 *bits |= *(*src)++ << *nbits; | |
383 *nbits += 8; | |
384 } | |
385 return 1; | |
386 } | |
387 | |
388 /* get n bits from *bits */ | |
389 static uint getbits_fast(uint *bits, uint *nbits, int n) { | |
390 uint k; | |
391 | |
392 k = *bits & ((1 << n) - 1); | |
393 *bits >>= n; | |
394 *nbits -= n; | |
395 return k; | |
396 } | |
397 | |
398 static int fillbits(DecodeState *s, uint n) { | |
399 return fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, n); | |
400 } | |
401 | |
402 static uint getbits(DecodeState *s, uint n) { | |
403 return getbits_fast(&s->bits, &s->nbits, n); | |
404 } | |
405 | |
406 /* decode symbol bitwise if code is longer than huffbits */ | |
407 static uint decode_symbol_long(DecodeState *s, Huff *huff, uint bits, uint nbits, int cur) { | |
408 int sum = huff->sum; | |
409 uint huffbits = huff->nbits; | |
410 ushort *count = huff->count + huffbits + 1; | |
411 | |
412 /* get bits if we are near the end */ | |
413 if (s->src + 2 >= s->srcend) { | |
414 while (nbits < CodeBits - 1 && s->src < s->srcend) { | |
415 bits |= *s->src++ << nbits; | |
416 nbits += 8; | |
417 } | |
418 s->bits = bits; | |
419 s->nbits = nbits; | |
420 } | |
421 bits >>= huffbits; | |
422 nbits -= huffbits; | |
423 for (;;) { | |
424 if (!nbits--) { | |
425 if (s->src == s->srcend) | |
426 return FlateIn; | |
427 bits = *s->src++; | |
428 nbits = 7; | |
429 } | |
430 cur |= bits & 1; | |
431 bits >>= 1; | |
432 sum += *count; | |
433 cur -= *count; | |
434 if (cur < 0) | |
435 break; | |
436 cur <<= 1; | |
437 count++; | |
438 if (count == huff->count + CodeBits) | |
439 return s->err = "symbol decoding failed.", FlateErr; | |
440 } | |
441 s->bits = bits; | |
442 s->nbits = nbits; | |
443 return huff->symbol[sum + cur]; | |
444 } | |
445 | |
446 /* decode a symbol from stream with huff code */ | |
447 static uint decode_symbol(DecodeState *s, Huff *huff) { | |
448 uint huffbits = huff->nbits; | |
449 uint nbits = s->nbits; | |
450 uint bits = s->bits; | |
451 uint mask = (1 << huffbits) - 1; | |
452 Entry entry; | |
453 | |
454 /* get enough bits efficiently */ | |
455 if (nbits < huffbits) { | |
456 uchar *src = s->src; | |
457 | |
458 if (src + 2 < s->srcend) { | |
459 /* we assume huffbits <= 9 */ | |
460 bits |= *src++ << nbits; | |
461 nbits += 8; | |
462 bits |= *src++ << nbits; | |
463 nbits += 8; | |
464 bits |= *src++ << nbits; | |
465 nbits += 8; | |
466 s->src = src; | |
467 } else /* rare */ | |
468 do { | |
469 if (s->src == s->srcend) { | |
470 entry = huff->table[bits & mask]; | |
471 if (entry.len > 0 && entry.len <= nbits) { | |
472 s->bits = bits >> entry.len; | |
473 s->nbits = nbits - entry.len; | |
474 return entry.sym; | |
475 } | |
476 s->bits = bits; | |
477 s->nbits = nbits; | |
478 return FlateIn; | |
479 } | |
480 bits |= *s->src++ << nbits; | |
481 nbits += 8; | |
482 } while (nbits < huffbits); | |
483 } | |
484 /* decode bits */ | |
485 entry = huff->table[bits & mask]; | |
486 if (entry.len > 0) { | |
487 s->bits = bits >> entry.len; | |
488 s->nbits = nbits - entry.len; | |
489 return entry.sym; | |
490 } else if (entry.len == 0) | |
491 return s->err = "symbol decoding failed.", FlateErr; | |
492 return decode_symbol_long(s, huff, bits, nbits, entry.sym); | |
493 } | |
494 | |
495 /* decode a block of data from stream with trees */ | |
496 static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff) { | |
497 uchar *win = s->win; | |
498 uint pos = s->pos; | |
499 uint sym = s->nclen; | |
500 uint len = s->lenpos; | |
501 uint dist = s->nclen; | |
502 | |
503 switch (s->state) { | |
504 case DecodeBlock: | |
505 for (;;) { | |
506 sym = decode_symbol(s, lhuff); | |
507 if (sym < 256) { | |
508 win[pos++] = sym; | |
509 if (pos == WinSize) { | |
510 s->pos = WinSize; | |
511 s->state = DecodeBlock; | |
512 return FlateOut; | |
513 } | |
514 } else if (sym > 256) { | |
515 sym -= 257; | |
516 if (sym >= Nlen) { | |
517 s->pos = pos; | |
518 s->state = DecodeBlock; | |
519 if (sym + 257 == (uint)FlateIn) | |
520 return FlateIn; | |
521 return FlateErr; | |
522 } | |
523 case DecodeBlockLenBits: | |
524 if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, lenbits[sym])) { | |
525 s->nclen = sym; /* using nclen to store sym */ | |
526 s->pos = pos; | |
527 s->state = DecodeBlockLenBits; | |
528 return FlateIn; | |
529 } | |
530 len = lenbase[sym] + getbits_fast(&s->bits, &s->nbits, lenbits[sym]); | |
531 case DecodeBlockDist: | |
532 sym = decode_symbol(s, dhuff); | |
533 if (sym == (uint)FlateIn) { | |
534 s->pos = pos; | |
535 s->lenpos = len; | |
536 s->state = DecodeBlockDist; | |
537 return FlateIn; | |
538 } | |
539 if (sym >= Ndist) | |
540 return FlateErr; | |
541 case DecodeBlockDistBits: | |
542 if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, distbits[sym])) { | |
543 s->nclen = sym; /* using nclen to store sym */ | |
544 s->pos = pos; | |
545 s->lenpos = len; | |
546 s->state = DecodeBlockDistBits; | |
547 return FlateIn; | |
548 } | |
549 dist = distbase[sym] + getbits_fast(&s->bits, &s->nbits, distbits[sym]); | |
550 /* copy match, loop unroll in common case */ | |
551 if (pos + len < WinSize) { | |
552 /* lenbase[sym] >= 3 */ | |
553 do { | |
554 win[pos] = win[(pos - dist) % WinSize]; | |
555 pos++; | |
556 win[pos] = win[(pos - dist) % WinSize]; | |
557 pos++; | |
558 win[pos] = win[(pos - dist) % WinSize]; | |
559 pos++; | |
560 len -= 3; | |
561 } while (len >= 3); | |
562 if (len--) { | |
563 win[pos] = win[(pos - dist) % WinSize]; | |
564 pos++; | |
565 if (len) { | |
566 win[pos] = win[(pos - dist) % WinSize]; | |
567 pos++; | |
568 } | |
569 } | |
570 } else { /* rare */ | |
571 case DecodeBlockCopy: | |
572 while (len--) { | |
573 win[pos] = win[(pos - dist) % WinSize]; | |
574 pos++; | |
575 if (pos == WinSize) { | |
576 s->pos = WinSize; | |
577 s->lenpos = len; | |
578 s->nclen = dist; /* using nclen to store dist */ | |
579 s->state = DecodeBlockCopy; | |
580 return FlateOut; | |
581 } | |
582 } | |
583 } | |
584 } else { /* EOB: sym == 256 */ | |
585 s->pos = pos; | |
586 return FlateOk; | |
587 } | |
588 } /* for (;;) */ | |
589 } /* switch () */ | |
590 return s->err = "corrupted state.", FlateErr; | |
591 } | |
592 | |
593 /* inflate state machine (decodes s->src into s->win) */ | |
594 static int inflate_state(DecodeState *s) { | |
595 int n; | |
596 | |
597 if (s->posout) | |
598 return FlateOut; | |
599 for (;;) { | |
600 switch (s->state) { | |
601 case BlockHead: | |
602 if (s->final) { | |
603 if (s->pos) | |
604 return FlateOut; | |
605 else | |
606 return FlateOk; | |
607 } | |
608 if (!fillbits(s, 3)) | |
609 return FlateIn; | |
610 s->final = getbits(s, 1); | |
611 n = getbits(s, 2); | |
612 if (n == 0) | |
613 s->state = UncompressedBlock; | |
614 else if (n == 1) | |
615 s->state = FixedHuff; | |
616 else if (n == 2) | |
617 s->state = DynamicHuff; | |
618 else | |
619 return s->err = "corrupt block header.", FlateErr; | |
620 break; | |
621 case UncompressedBlock: | |
622 /* start block on a byte boundary */ | |
623 s->bits >>= s->nbits & 7; | |
624 s->nbits &= ~7; | |
625 if (!fillbits(s, 32)) | |
626 return FlateIn; | |
627 s->lenpos = getbits(s, 16); | |
628 n = getbits(s, 16); | |
629 if (s->lenpos != (~n & 0xffff)) | |
630 return s->err = "corrupt uncompressed length.", FlateErr; | |
631 s->state = CopyUncompressed; | |
632 case CopyUncompressed: | |
633 /* TODO: untested, slow, memcpy etc */ | |
634 /* s->nbits should be 0 here */ | |
635 while (s->lenpos) { | |
636 if (s->src == s->srcend) | |
637 return FlateIn; | |
638 s->lenpos--; | |
639 s->win[s->pos++] = *s->src++; | |
640 if (s->pos == WinSize) | |
641 return FlateOut; | |
642 } | |
643 s->state = BlockHead; | |
644 break; | |
645 case FixedHuff: | |
646 s->fixed = 1; | |
647 s->state = DecodeBlock; | |
648 break; | |
649 case DynamicHuff: | |
650 /* decode dynamic huffman code trees */ | |
651 if (!fillbits(s, 14)) | |
652 return FlateIn; | |
653 s->nlit = 257 + getbits(s, 5); | |
654 s->ndist = 1 + getbits(s, 5); | |
655 s->nclen = 4 + getbits(s, 4); | |
656 if (s->nlit > Nlitlen || s->ndist > Ndist) | |
657 return s->err = "corrupt code tree.", FlateErr; | |
658 /* build code length tree */ | |
659 for (n = 0; n < Nclen; n++) | |
660 s->lens[n] = 0; | |
661 s->fixed = 0; | |
662 s->state = DynamicHuffClen; | |
663 s->lenpos = 0; | |
664 case DynamicHuffClen: | |
665 for (n = s->lenpos; n < s->nclen; n++) | |
666 if (fillbits(s, 3)) { | |
667 s->lens[clenorder[n]] = getbits(s, 3); | |
668 } else { | |
669 s->lenpos = n; | |
670 return FlateIn; | |
671 } | |
672 /* using lhuff for code length huff code */ | |
673 if (build_huff(&s->lhuff, s->lens, Nclen, ClenTableBits) < 0) | |
674 return s->err = "building clen tree failed.", FlateErr; | |
675 s->state = DynamicHuffLitlenDist; | |
676 s->lenpos = 0; | |
677 case DynamicHuffLitlenDist: | |
678 /* decode code lengths for the dynamic trees */ | |
679 for (n = s->lenpos; n < s->nlit + s->ndist; ) { | |
680 uint sym = decode_symbol(s, &s->lhuff); | |
681 uint len; | |
682 uchar c; | |
683 | |
684 if (sym < 16) { | |
685 s->lens[n++] = sym; | |
686 continue; | |
687 } else if (sym == (uint)FlateIn) { | |
688 s->lenpos = n; | |
689 return FlateIn; | |
690 case DynamicHuffContinue: | |
691 n = s->lenpos; | |
692 sym = s->nclen; | |
693 s->state = DynamicHuffLitlenDist; | |
694 } | |
695 if (!fillbits(s, 7)) { | |
696 /* TODO: 7 is too much when an almost empty block is at the end */ | |
697 if (sym == (uint)FlateErr) | |
698 return FlateErr; | |
699 s->nclen = sym; | |
700 s->lenpos = n; | |
701 s->state = DynamicHuffContinue; | |
702 return FlateIn; | |
703 } | |
704 /* TODO: bound check s->lens */ | |
705 if (sym == 16) { | |
706 /* copy previous code length 3-6 times */ | |
707 c = s->lens[n - 1]; | |
708 for (len = 3 + getbits(s, 2); len; len--) | |
709 s->lens[n++] = c; | |
710 } else if (sym == 17) { | |
711 /* repeat 0 for 3-10 times */ | |
712 for (len = 3 + getbits(s, 3); len; len--) | |
713 s->lens[n++] = 0; | |
714 } else if (sym == 18) { | |
715 /* repeat 0 for 11-138 times */ | |
716 for (len = 11 + getbits(s, 7); len; len--) | |
717 s->lens[n++] = 0; | |
718 } else | |
719 return s->err = "corrupt code tree.", FlateErr; | |
720 } | |
721 /* build dynamic huffman code trees */ | |
722 if (build_huff(&s->lhuff, s->lens, s->nlit, LitlenTableBits) < 0) | |
723 return s->err = "building litlen tree failed.", FlateErr; | |
724 if (build_huff(&s->dhuff, s->lens + s->nlit, s->ndist, DistTableBits) < 0) | |
725 return s->err = "building dist tree failed.", FlateErr; | |
726 s->state = DecodeBlock; | |
727 case DecodeBlock: | |
728 case DecodeBlockLenBits: | |
729 case DecodeBlockDist: | |
730 case DecodeBlockDistBits: | |
731 case DecodeBlockCopy: | |
732 n = decode_block(s, s->fixed ? &lhuff : &s->lhuff, s->fixed ? &dhuff : &s->dhuff); | |
733 if (n != FlateOk) | |
734 return n; | |
735 s->state = BlockHead; | |
736 break; | |
737 default: | |
738 return s->err = "corrupt internal state.", FlateErr; | |
739 } | |
740 } | |
741 } | |
742 | |
743 static DecodeState *alloc_decode_state(void) { | |
744 DecodeState *s = malloc(sizeof(DecodeState)); | |
745 | |
746 if (s) { | |
747 s->final = s->pos = s->posout = s->bits = s->nbits = 0; | |
748 s->state = BlockHead; | |
749 s->src = s->srcend = 0; | |
750 s->err = 0; | |
751 /* TODO: globals.. */ | |
752 if (lhuff.nbits == 0) | |
753 init_fixed_huffs(); | |
754 } | |
755 return s; | |
756 } | |
757 | |
758 | |
759 /* extern */ | |
760 | |
761 int inflate(FlateStream *stream) { | |
762 DecodeState *s = stream->state; | |
763 int n; | |
764 | |
765 if (stream->err) { | |
766 if (s) { | |
767 free(s); | |
768 stream->state = 0; | |
769 } | |
770 return FlateErr; | |
771 } | |
772 if (!s) { | |
773 s = stream->state = alloc_decode_state(); | |
774 if (!s) | |
775 return stream->err = "no mem.", FlateErr; | |
776 } | |
777 if (stream->nin) { | |
778 s->src = stream->in; | |
779 s->srcend = s->src + stream->nin; | |
780 stream->nin = 0; | |
781 } | |
782 n = inflate_state(s); | |
783 if (n == FlateOut) { | |
784 if (s->pos < stream->nout) | |
785 stream->nout = s->pos; | |
786 memcpy(stream->out, s->win + s->posout, stream->nout); | |
787 s->pos -= stream->nout; | |
788 if (s->pos) | |
789 s->posout += stream->nout; | |
790 else | |
791 s->posout = 0; | |
792 } | |
793 if (n == FlateOk || n == FlateErr) { | |
794 if (s->nbits || s->src < s->srcend) { | |
795 s->nbits /= 8; | |
796 stream->in = s->src - s->nbits; | |
797 stream->nin = s->srcend - s->src + s->nbits; | |
798 } | |
799 stream->err = s->err; | |
800 free(s); | |
801 stream->state = 0; | |
802 } | |
803 return n; | |
804 } | |
805 | |
806 typedef struct { | |
807 ushort dist; | |
808 ushort len; | |
809 } Match; | |
810 | |
811 typedef struct { | |
812 ushort n; | |
813 ushort bits; | |
814 } LzCode; | |
815 | |
816 typedef struct { | |
817 int pos; /* position in input src */ | |
818 int startpos; /* block start pos in input src */ | |
819 int endpos; /* end of available bytes in src */ | |
820 int skip; /* skipped hash chain updates (until next iter) */ | |
821 Match prevm; /* previous (deferred) match */ | |
822 int state; /* prev return value */ | |
823 int eof; /* end of input */ | |
824 uchar *in; /* input data (not yet in src) */ | |
825 uchar *inend; | |
826 uint bits; /* for output */ | |
827 int nbits; /* for output */ | |
828 uchar *dst; /* compressed output (position in dstbuf) */ | |
829 uchar *dstbegin; /* start position of unflushed data in dstbuf */ | |
830 LzCode *lz; /* current pos in lzbuf */ | |
831 int nlit; /* literal run length in lzbuf */ | |
832 ushort head[HashSize]; /* position of hash chain heads */ | |
833 ushort chain[WinSize]; /* hash chain */ | |
834 ushort lfreq[Nlitlen]; | |
835 ushort dfreq[Ndist]; | |
836 uchar src[SrcSize]; /* input buf */ | |
837 uchar dstbuf[DstSize]; | |
838 LzCode lzbuf[LzSize]; /* literal run length, match len, match dist */ | |
839 } State; | |
840 | |
841 static uchar fixllen[Nlitlen]; /* fixed lit/len huffman code tree */ | |
842 static ushort fixlcode[Nlitlen]; | |
843 static uchar fixdlen[Ndist]; /* fixed distance huffman code tree */ | |
844 static ushort fixdcode[Ndist]; | |
845 | |
846 static uint revcode(uint c, int n) { | |
847 int i; | |
848 uint r = 0; | |
849 | |
850 for (i = 0; i < n; i++) { | |
851 r = (r << 1) | (c & 1); | |
852 c >>= 1; | |
853 } | |
854 return r; | |
855 } | |
856 | |
857 /* build huffman code tree from code lengths */ | |
858 static void huffcodes(ushort *codes, const uchar *lens, int n) { | |
859 int c[CodeBits]; | |
860 int i, code, count; | |
861 | |
862 /* count code lengths and calc first code for each length */ | |
863 for (i = 0; i < CodeBits; i++) | |
864 c[i] = 0; | |
865 for (i = 0; i < n; i++) | |
866 c[lens[i]]++; | |
867 for (code = 0, i = 1; i < CodeBits; i++) { | |
868 count = c[i]; | |
869 c[i] = code; | |
870 code += count; | |
871 if (code > (1 << i)) | |
872 abort(); /* over-subscribed */ | |
873 code <<= 1; | |
874 } | |
875 if (code < (1 << i)) | |
876 /* incomplete */; | |
877 | |
878 for (i = 0; i < n; i++) | |
879 if (lens[i]) | |
880 codes[i] = revcode(c[lens[i]]++, lens[i]); | |
881 else | |
882 codes[i] = 0; | |
883 } | |
884 | |
885 static int heapparent(int n) {return (n - 2)/4 * 2;} | |
886 static int heapchild(int n) {return 2 * n + 2;} | |
887 | |
888 static int heappush(int *heap, int len, int w, int n) { | |
889 int p, c, tmp; | |
890 | |
891 c = len; | |
892 heap[len++] = n; | |
893 heap[len++] = w; | |
894 while (c > 0) { | |
895 p = heapparent(c); | |
896 if (heap[c+1] < heap[p+1]) { | |
897 tmp = heap[c]; heap[c] = heap[p]; heap[p] = tmp; | |
898 tmp = heap[c+1]; heap[c+1] = heap[p+1]; heap[p+1] = tmp; | |
899 c = p; | |
900 } else | |
901 break; | |
902 } | |
903 return len; | |
904 } | |
905 | |
906 static int heappop(int *heap, int len, int *w, int *n) { | |
907 int p, c, tmp; | |
908 | |
909 *n = heap[0]; | |
910 *w = heap[1]; | |
911 heap[1] = heap[--len]; | |
912 heap[0] = heap[--len]; | |
913 p = 0; | |
914 for (;;) { | |
915 c = heapchild(p); | |
916 if (c >= len) | |
917 break; | |
918 if (c+2 < len && heap[c+3] < heap[c+1]) | |
919 c += 2; | |
920 if (heap[p+1] > heap[c+1]) { | |
921 tmp = heap[p]; heap[p] = heap[c]; heap[c] = tmp; | |
922 tmp = heap[p+1]; heap[p+1] = heap[c+1]; heap[c+1] = tmp; | |
923 } else | |
924 break; | |
925 p = c; | |
926 } | |
927 return len; | |
928 } | |
929 | |
930 /* symbol frequencies -> code lengths (limited to 255) */ | |
931 static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) { | |
932 /* 2 <= nsym <= Nlitlen, log(nsym) <= limit <= CodeBits-1 */ | |
933 int parent[2*Nlitlen-1]; | |
934 int count[CodeBits]; | |
935 int heap[2*Nlitlen]; | |
936 int n, len, top, overflow; | |
937 int i, j; | |
938 int wi, wj; | |
939 | |
940 for (n = 0; n < limit+1; n++) | |
941 count[n] = 0; | |
942 for (len = n = 0; n < nsym; n++) | |
943 if (freqs[n] > 0) | |
944 len = heappush(heap, len, freqs[n], n); | |
945 else | |
946 lens[n] = 0; | |
947 /* deflate: fewer than two symbols: add new */ | |
948 for (n = 0; len < 4; n++) | |
949 if (freqs[n] == 0) | |
950 len = heappush(heap, len, ++freqs[n], n); | |
951 /* build code tree */ | |
952 top = len; | |
953 for (n = nsym; len > 2; n++) { | |
954 len = heappop(heap, len, &wi, &i); | |
955 len = heappop(heap, len, &wj, &j); | |
956 parent[i] = n; | |
957 parent[j] = n; | |
958 len = heappush(heap, len, wi + wj, n); | |
959 /* keep an ordered list of nodes at the end */ | |
960 heap[len+1] = i; | |
961 heap[len] = j; | |
962 } | |
963 /* calc code lengths (deflate: with limit) */ | |
964 overflow = 0; | |
965 parent[--n] = 0; | |
966 for (i = 2; i < top; i++) { | |
967 n = heap[i]; | |
968 if (n >= nsym) { | |
969 /* overwrite parent index with length */ | |
970 parent[n] = parent[parent[n]] + 1; | |
971 if (parent[n] > limit) | |
972 overflow++; | |
973 } else { | |
974 lens[n] = parent[parent[n]] + 1; | |
975 if (lens[n] > limit) { | |
976 lens[n] = limit; | |
977 overflow++; | |
978 } | |
979 count[lens[n]]++; | |
980 } | |
981 } | |
982 if (overflow == 0) | |
983 return; | |
984 /* modify code tree to fix overflow (from zlib) */ | |
985 while (overflow > 0) { | |
986 for (n = limit-1; count[n] == 0; n--); | |
987 count[n]--; | |
988 count[n+1] += 2; | |
989 count[limit]--; | |
990 overflow -= 2; | |
991 } | |
992 for (len = limit; len > 0; len--) | |
993 for (i = count[len]; i > 0;) { | |
994 n = heap[--top]; | |
995 if (n < nsym) { | |
996 lens[n] = len; | |
997 i--; | |
998 } | |
999 } | |
1000 } | |
1001 | |
1002 /* output n (<= 16) bits */ | |
1003 static void putbits(State *s, uint bits, int n) { | |
1004 s->bits |= bits << s->nbits; | |
1005 s->nbits += n; | |
1006 while (s->nbits >= 8) { | |
1007 *s->dst++ = s->bits & 0xff; | |
1008 s->bits >>= 8; | |
1009 s->nbits -= 8; | |
1010 } | |
1011 } | |
1012 | |
1013 /* run length encode literal and dist code lengths into codes and extra */ | |
1014 static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit, uchar *dlen, int ndist) { | |
1015 int i, c, r, rr; | |
1016 int n = 0; | |
1017 | |
1018 for (i = 0; i < nlit; i++) | |
1019 codes[i] = llen[i]; | |
1020 for (i = 0; i < ndist; i++) | |
1021 codes[nlit + i] = dlen[i]; | |
1022 for (i = 0; i < nlit + ndist;) { | |
1023 c = codes[i]; | |
1024 for (r = 1; i + r < nlit + ndist && codes[i + r] == c; r++); | |
1025 i += r; | |
1026 if (c == 0) { | |
1027 while (r >= 11) { | |
1028 rr = r > 138 ? 138 : r; | |
1029 codes[n] = 18; | |
1030 extra[n++] = rr - 11; | |
1031 r -= rr; | |
1032 } | |
1033 if (r >= 3) { | |
1034 codes[n] = 17; | |
1035 extra[n++] = r - 3; | |
1036 r = 0; | |
1037 } | |
1038 } | |
1039 while (r--) { | |
1040 codes[n++] = c; | |
1041 while (r >= 3) { | |
1042 rr = r > 6 ? 6 : r; | |
1043 codes[n] = 16; | |
1044 extra[n++] = rr - 3; | |
1045 r -= rr; | |
1046 } | |
1047 } | |
1048 } | |
1049 return n; | |
1050 } | |
1051 | |
1052 /* compress block data into s->dstbuf using given codes */ | |
1053 static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar *dlen) { | |
1054 int n; | |
1055 LzCode *lz; | |
1056 uchar *p; | |
1057 | |
1058 for (lz = s->lzbuf, p = s->src + s->startpos; lz != s->lz; lz++) | |
1059 if (lz->bits & LzLitFlag) | |
1060 for (n = lz->n; n > 0; n--, p++) | |
1061 putbits(s, lcode[*p], llen[*p]); | |
1062 else { | |
1063 p += lenbase[lz->n] + lz->bits; | |
1064 putbits(s, lcode[Nlit + lz->n + 1], llen[Nlit + lz->n + 1]); | |
1065 putbits(s, lz->bits, lenbits[lz->n]); | |
1066 lz++; | |
1067 putbits(s, dcode[lz->n], dlen[lz->n]); | |
1068 putbits(s, lz->bits, distbits[lz->n]); | |
1069 } | |
1070 putbits(s, lcode[EOB], llen[EOB]); | |
1071 } | |
1072 | |
1073 /* build code trees and select dynamic/fixed/uncompressed block compression */ | |
1074 static void deflate_block(State *s) { | |
1075 uchar codes[Nlitlen + Ndist], extra[Nlitlen + Ndist]; | |
1076 uchar llen[Nlitlen], dlen[Ndist], clen[Nclen]; | |
1077 ushort cfreq[Nclen]; | |
1078 /* freq can be overwritten by code */ | |
1079 ushort *lcode = s->lfreq, *dcode = s->dfreq, *ccode = cfreq; | |
1080 int i, c, n, ncodes; | |
1081 int nlit, ndist, nclen; | |
1082 LzCode *lz; | |
1083 uchar *p; | |
1084 int dynsize, fixsize, uncsize; | |
1085 int blocklen = s->pos - s->startpos; | |
1086 /* int dyntree; */ | |
1087 | |
1088 /* calc dynamic codes */ | |
1089 hufflens(llen, s->lfreq, Nlitlen, CodeBits-1); | |
1090 hufflens(dlen, s->dfreq, Ndist, CodeBits-1); | |
1091 huffcodes(lcode, llen, Nlitlen); | |
1092 huffcodes(dcode, dlen, Ndist); | |
1093 for (nlit = Nlitlen; nlit > Nlit && llen[nlit-1] == 0; nlit--); | |
1094 for (ndist = Ndist; ndist > 1 && dlen[ndist-1] == 0; ndist--); | |
1095 ncodes = clencodes(codes, extra, llen, nlit, dlen, ndist); | |
1096 memset(cfreq, 0, sizeof(cfreq)); | |
1097 for (i = 0; i < ncodes; i++) | |
1098 cfreq[codes[i]]++; | |
1099 hufflens(clen, cfreq, Nclen, 7); | |
1100 huffcodes(ccode, clen, Nclen); | |
1101 for (nclen = Nclen; nclen > 4 && clen[clenorder[nclen-1]] == 0; nclen--); | |
1102 | |
1103 /* calc compressed size */ | |
1104 uncsize = 3 + 16 + 8 * blocklen + (16 - 3 - s->nbits) % 8; /* byte aligned */ | |
1105 fixsize = 3; | |
1106 dynsize = 3 + 5 + 5 + 4 + 3 * nclen; | |
1107 for (i = 0; i < ncodes; i++) { | |
1108 c = codes[i]; | |
1109 dynsize += clen[c]; | |
1110 if (c == 16) | |
1111 dynsize += 2; | |
1112 if (c == 17) | |
1113 dynsize += 3; | |
1114 if (c == 18) | |
1115 dynsize += 7; | |
1116 } | |
1117 /* dyntree = dynsize - 3; */ | |
1118 for (lz = s->lzbuf, p = s->src + s->startpos; lz != s->lz; lz++) | |
1119 if (lz->bits & LzLitFlag) | |
1120 for (n = lz->n; n > 0; n--, p++) { | |
1121 fixsize += fixllen[*p]; | |
1122 dynsize += llen[*p]; | |
1123 } | |
1124 else { | |
1125 p += lenbase[lz->n] + lz->bits; | |
1126 fixsize += fixllen[Nlit + lz->n + 1]; | |
1127 dynsize += llen[Nlit + lz->n + 1]; | |
1128 fixsize += lenbits[lz->n]; | |
1129 dynsize += lenbits[lz->n]; | |
1130 lz++; | |
1131 fixsize += fixdlen[lz->n]; | |
1132 dynsize += dlen[lz->n]; | |
1133 fixsize += distbits[lz->n]; | |
1134 dynsize += distbits[lz->n]; | |
1135 } | |
1136 fixsize += fixllen[EOB]; | |
1137 dynsize += llen[EOB]; | |
1138 | |
1139 /* emit block */ | |
1140 putbits(s, s->eof && s->pos == s->endpos, 1); | |
1141 if (dynsize < fixsize && dynsize < uncsize) { | |
1142 /* dynamic code */ | |
1143 putbits(s, 2, 2); | |
1144 putbits(s, nlit - 257, 5); | |
1145 putbits(s, ndist - 1, 5); | |
1146 putbits(s, nclen - 4, 4); | |
1147 for (i = 0; i < nclen; i++) | |
1148 putbits(s, clen[clenorder[i]], 3); | |
1149 for (i = 0; i < ncodes; i++) { | |
1150 c = codes[i]; | |
1151 putbits(s, ccode[c], clen[c]); | |
1152 if (c == 16) | |
1153 putbits(s, extra[i], 2); | |
1154 if (c == 17) | |
1155 putbits(s, extra[i], 3); | |
1156 if (c == 18) | |
1157 putbits(s, extra[i], 7); | |
1158 } | |
1159 putblock(s, lcode, llen, dcode, dlen); | |
1160 } else if (fixsize < uncsize) { | |
1161 /* fixed code */ | |
1162 putbits(s, 1, 2); | |
1163 putblock(s, fixlcode, fixllen, fixdcode, fixdlen); | |
1164 } else { | |
1165 /* uncompressed */ | |
1166 putbits(s, 0, 2); | |
1167 putbits(s, 0, 7); /* align to byte boundary */ | |
1168 s->nbits = 0; | |
1169 putbits(s, blocklen, 16); | |
1170 putbits(s, ~blocklen & 0xffff, 16); | |
1171 memcpy(s->dst, s->src + s->startpos, blocklen); | |
1172 s->dst += blocklen; | |
1173 } | |
1174 /* | |
1175 fprintf(stderr, "blen:%d [%d,%d] lzlen:%d dynlen:%d (tree:%d rate:%.3f) fixlen:%d (rate:%.3f) unclen:%d (rate:%.3f)\n", | |
1176 blocklen, s->startpos, s->pos, s->lz - s->lzbuf, dynsize, dyntree, dynsize/(float)blocklen, | |
1177 fixsize, fixsize/(float)blocklen, uncsize, uncsize/(float)blocklen); | |
1178 */ | |
1179 } | |
1180 | |
1181 /* find n in base */ | |
1182 static int bisect(ushort *base, int len, int n) { | |
1183 int lo = 0; | |
1184 int hi = len; | |
1185 int k; | |
1186 | |
1187 while (lo < hi) { | |
1188 k = (lo + hi) / 2; | |
1189 if (n < base[k]) | |
1190 hi = k; | |
1191 else | |
1192 lo = k + 1; | |
1193 } | |
1194 return lo - 1; | |
1195 } | |
1196 | |
1197 /* add literal run length to lzbuf */ | |
1198 static void flushlit(State *s) { | |
1199 if (s->nlit) { | |
1200 s->lz->bits = LzLitFlag; | |
1201 s->lz->n = s->nlit; | |
1202 s->lz++; | |
1203 s->nlit = 0; | |
1204 } | |
1205 } | |
1206 | |
1207 /* add match to lzbuf and update freq counts */ | |
1208 static void recordmatch(State *s, Match m) { | |
1209 int n; | |
1210 | |
1211 /*fprintf(stderr, "m %d %d\n", m.len, m.dist);*/ | |
1212 flushlit(s); | |
1213 n = bisect(lenbase, Nlen, m.len); | |
1214 s->lz->n = n; | |
1215 s->lz->bits = m.len - lenbase[n]; | |
1216 s->lz++; | |
1217 s->lfreq[Nlit + n + 1]++; | |
1218 n = bisect(distbase, Ndist, m.dist); | |
1219 s->lz->n = n; | |
1220 s->lz->bits = m.dist - distbase[n]; | |
1221 s->lz++; | |
1222 s->dfreq[n]++; | |
1223 } | |
1224 | |
1225 /* update literal run length */ | |
1226 static void recordlit(State *s, int c) { | |
1227 /*fprintf(stderr, "l %c\n", c);*/ | |
1228 s->nlit++; | |
1229 s->lfreq[c]++; | |
1230 } | |
1231 | |
1232 /* multiplicative hash (using a prime close to golden ratio * 2^32) */ | |
1233 static int gethash(uchar *p) { | |
1234 return (0x9e3779b1 * ((p[0]<<16) + (p[1]<<8) + p[2]) >> (32 - HashBits)) % HashSize; | |
1235 } | |
1236 | |
1237 /* update hash chain at the current position */ | |
1238 static int updatechain(State *s) { | |
1239 int hash, next = 0, p = s->pos, i; | |
1240 | |
1241 if (s->endpos - p < MinMatch) | |
1242 p = s->endpos - MinMatch; | |
1243 for (i = s->pos - s->skip; i <= p; i++) { | |
1244 hash = gethash(s->src + i); | |
1245 next = s->head[hash]; | |
1246 s->head[hash] = i; | |
1247 if (next >= i || i - next >= MaxDist) | |
1248 next = 0; | |
1249 s->chain[i % WinSize] = next; | |
1250 } | |
1251 s->skip = 0; | |
1252 return next; | |
1253 } | |
1254 | |
1255 /* find longest match, next position in the hash chain is given */ | |
1256 static Match getmatch(State *s, int next) { | |
1257 Match m = {0, MinMatch-1}; | |
1258 int len; | |
1259 int limit = s->pos - MaxDist; | |
1260 int chainlen = MaxChainLen; | |
1261 uchar *q; | |
1262 uchar *p = s->src + s->pos; | |
1263 uchar *end = p + MaxMatch; | |
1264 | |
1265 do { | |
1266 q = s->src + next; | |
1267 /*fprintf(stderr,"match: next:%d pos:%d limit:%d\n", next, s->pos, limit);*/ | |
1268 /* next match should be at least m.len+1 long */ | |
1269 if (q[m.len] != p[m.len] || q[m.len-1] != p[m.len-1] || q[0] != p[0]) | |
1270 continue; | |
1271 while (++p != end && *++q == *p); | |
1272 len = MaxMatch - (end - p); | |
1273 p -= len; | |
1274 /*fprintf(stderr,"match: len:%d dist:%d\n", len, s->pos - next);*/ | |
1275 if (len > m.len) { | |
1276 m.dist = s->pos - next; | |
1277 m.len = len; | |
1278 if (s->pos + len >= s->endpos) { /* TODO: overflow */ | |
1279 m.len = s->endpos - s->pos; | |
1280 return m; | |
1281 } | |
1282 if (len == MaxMatch) | |
1283 return m; | |
1284 } | |
1285 } while ((next = s->chain[next % WinSize]) > limit && --chainlen); | |
1286 if (m.len < MinMatch || (m.len == MinMatch && m.dist > BigDist)) | |
1287 m.len = 0; | |
1288 return m; | |
1289 } | |
1290 | |
1291 static void startblock(State *s) { | |
1292 s->startpos = s->pos; | |
1293 s->dst = s->dstbegin = s->dstbuf; | |
1294 s->lz = s->lzbuf; | |
1295 s->nlit = 0; | |
1296 memset(s->lfreq, 0, sizeof(s->lfreq)); | |
1297 memset(s->dfreq, 0, sizeof(s->dfreq)); | |
1298 s->lfreq[EOB]++; | |
1299 } | |
1300 | |
1301 static int shiftwin(State *s) { | |
1302 int n; | |
1303 | |
1304 if (s->startpos < WinSize) | |
1305 return 0; | |
1306 memmove(s->src, s->src + WinSize, SrcSize - WinSize); | |
1307 for (n = 0; n < HashSize; n++) | |
1308 s->head[n] = s->head[n] > WinSize ? s->head[n] - WinSize : 0; | |
1309 for (n = 0; n < WinSize; n++) | |
1310 s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0; | |
1311 s->pos -= WinSize; | |
1312 s->startpos -= WinSize; | |
1313 s->endpos -= WinSize; | |
1314 return 1; | |
1315 } | |
1316 | |
1317 static int endblock(State *s) { | |
1318 if ((s->pos >= 2*WinSize && !shiftwin(s)) || s->pos - s->startpos >= BlockSize || | |
1319 s->lz - s->lzbuf >= LzGuard || (s->eof && s->pos == s->endpos)) { | |
1320 /* deflate block */ | |
1321 flushlit(s); | |
1322 if (s->prevm.len) | |
1323 s->pos--; | |
1324 deflate_block(s); | |
1325 if (s->eof && s->pos == s->endpos) | |
1326 putbits(s, 0, 7); | |
1327 return 1; | |
1328 } | |
1329 return 0; | |
1330 } | |
1331 | |
1332 static int fillsrc(State *s) { | |
1333 int n, k; | |
1334 | |
1335 if (s->endpos < SrcSize && !s->eof) { | |
1336 n = SrcSize - s->endpos; | |
1337 k = s->inend - s->in; | |
1338 if (n > k) | |
1339 n = k; | |
1340 memcpy(s->src + s->endpos, s->in, n); | |
1341 s->in += n; | |
1342 s->endpos += n; | |
1343 if (s->endpos < SrcSize) | |
1344 return 0; | |
1345 } | |
1346 return 1; | |
1347 } | |
1348 | |
1349 static int calcguard(State *s) { | |
1350 int p = s->endpos - MaxMatch; | |
1351 int q = s->startpos + BlockSize; | |
1352 | |
1353 return p < q ? p : q; | |
1354 } | |
1355 | |
1356 /* deflate compress from s->src into s->dstbuf */ | |
1357 static int deflate_state(State *s) { | |
1358 Match m; | |
1359 int next; | |
1360 int guard; | |
1361 | |
1362 if (s->state == FlateIn) | |
1363 s->eof = s->in == s->inend; | |
1364 else if (s->state == FlateOut) { | |
1365 if (s->dstbegin < s->dst) | |
1366 return (s->state = FlateOut); | |
1367 if (s->eof && s->pos == s->endpos) | |
1368 return (s->state = FlateOk); | |
1369 startblock(s); | |
1370 if (s->prevm.len) | |
1371 s->pos++; | |
1372 } else | |
1373 return s->state; | |
1374 | |
1375 guard = calcguard(s); | |
1376 for (;;) { | |
1377 if (s->pos >= guard || s->lz - s->lzbuf >= LzGuard) { | |
1378 /*fprintf(stderr,"guard:%d pos:%d len:%d lzlen:%d end:%d start:%d nin:%d eof:%d\n", guard, s->pos, s->pos - s->startpos, s->lz - s->lzbuf, s->endpos, s->startpos, s->inend - s->in, s->eof);*/ | |
1379 if (endblock(s)) | |
1380 return (s->state = FlateOut); | |
1381 if (!fillsrc(s)) | |
1382 return (s->state = FlateIn); | |
1383 guard = calcguard(s); | |
1384 } | |
1385 next = updatechain(s); | |
1386 if (next) | |
1387 m = getmatch(s, next); | |
1388 if (next && m.len > s->prevm.len) { | |
1389 if (s->prevm.len) | |
1390 recordlit(s, s->src[s->pos-1]); | |
1391 s->prevm = m; | |
1392 } else if (s->prevm.len) { | |
1393 recordmatch(s, s->prevm); | |
1394 s->skip = s->prevm.len - 2; | |
1395 s->prevm.len = 0; | |
1396 s->pos += s->skip; | |
1397 } else | |
1398 recordlit(s, s->src[s->pos]); | |
1399 s->pos++; | |
1400 } | |
1401 } | |
1402 | |
1403 /* alloc and init state */ | |
1404 static State *alloc_state(void) { | |
1405 State *s = malloc(sizeof(State)); | |
1406 int i; | |
1407 | |
1408 if (!s) | |
1409 return s; | |
1410 memset(s->chain, 0, sizeof(s->chain)); | |
1411 memset(s->head, 0, sizeof(s->head)); | |
1412 s->bits = s->nbits = 0; | |
1413 /* TODO: globals */ | |
1414 if (fixllen[0] == 0) { | |
1415 for (i = 0; i < 144; i++) | |
1416 fixllen[i] = 8; | |
1417 for (; i < 256; i++) | |
1418 fixllen[i] = 9; | |
1419 for (; i < 280; i++) | |
1420 fixllen[i] = 7; | |
1421 for (; i < Nlitlen; i++) | |
1422 fixllen[i] = 8; | |
1423 for (i = 0; i < Ndist; i++) | |
1424 fixdlen[i] = 5; | |
1425 huffcodes(fixlcode, fixllen, Nlitlen); | |
1426 huffcodes(fixdcode, fixdlen, Ndist); | |
1427 } | |
1428 s->state = FlateOut; | |
1429 s->in = s->inend = 0; | |
1430 s->dst = s->dstbegin = s->dstbuf; | |
1431 s->pos = s->startpos = s->endpos = WinSize; | |
1432 s->eof = 0; | |
1433 s->skip = 0; | |
1434 s->prevm.len = 0; | |
1435 return s; | |
1436 } | |
1437 | |
1438 | |
1439 /* extern */ | |
1440 | |
1441 int deflate(FlateStream *stream) { | |
1442 State *s = stream->state; | |
1443 int n, k; | |
1444 | |
1445 if (stream->err) { | |
1446 free(s); | |
1447 stream->state = 0; | |
1448 return FlateErr; | |
1449 } | |
1450 if (!s) { | |
1451 s = stream->state = alloc_state(); | |
1452 if (!s) | |
1453 return stream->err = "no mem.", FlateErr; | |
1454 } | |
1455 if (stream->nin) { | |
1456 s->in = stream->in; | |
1457 s->inend = s->in + stream->nin; | |
1458 stream->nin = 0; | |
1459 } | |
1460 n = deflate_state(s); | |
1461 if (n == FlateOut) { | |
1462 k = s->dst - s->dstbegin; | |
1463 if (k < stream->nout) | |
1464 stream->nout = k; | |
1465 memcpy(stream->out, s->dstbegin, stream->nout); | |
1466 s->dstbegin += stream->nout; | |
1467 } | |
1468 if (n == FlateOk || n == FlateErr) { | |
1469 free(s); | |
1470 stream->state = 0; | |
1471 } | |
1472 return n; | |
1473 } | |
1474 | |
1475 static void set32(uchar *p, uint n) { | |
1476 p[0] = n >> 24; | |
1477 p[1] = n >> 16; | |
1478 p[2] = n >> 8; | |
1479 p[3] = n; | |
1480 } | |
1481 | |
1482 static void set32le(uchar *p, uint n) { | |
1483 p[0] = n; | |
1484 p[1] = n >> 8; | |
1485 p[2] = n >> 16; | |
1486 p[3] = n >> 24; | |
1487 } | |
1488 | |
1489 static int check32(uchar *p, uint n) { | |
1490 return n == ((p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3]); | |
1491 } | |
1492 | |
1493 static int check32le(uchar *p, uint n) { | |
1494 return n == (p[0] | (p[1] << 8) | (p[2] << 16) | (p[3] << 24)); | |
1495 } | |
1496 | |
1497 enum { | |
1498 ZlibCM = 7 << 4, | |
1499 ZlibCINFO = 8, | |
1500 ZlibFLEV = 3 << 6, | |
1501 ZlibFDICT = 1 << 5, | |
1502 ZlibFCHK = 31 - (((ZlibCM | ZlibCINFO) << 8) | ZlibFLEV) % 31 | |
1503 }; | |
1504 | |
1505 int deflate_zlib_header(uchar *p, int n) { | |
1506 if (n < 2) | |
1507 return FlateErr; | |
1508 p[0] = ZlibCM | ZlibCINFO; /* deflate method, 32K window size */ | |
1509 p[1] = ZlibFLEV | ZlibFCHK; /* highest compression */ | |
1510 return 2; | |
1511 } | |
1512 | |
1513 int deflate_zlib_footer(uchar *p, int n, uint sum, uint len, uint zlen) { | |
1514 if (n < 4) | |
1515 return FlateErr; | |
1516 set32(p, sum); | |
1517 return 4; | |
1518 } | |
1519 | |
1520 int inflate_zlib_header(uchar *p, int n) { | |
1521 if (n < 2) | |
1522 return FlateErr; | |
1523 if (((p[0] << 8) | p[1]) % 31) | |
1524 return FlateErr; | |
1525 if ((p[0] & 0xf0) != ZlibCM || (p[0] & 0x0f) > ZlibCINFO) | |
1526 return FlateErr; | |
1527 if (p[1] & ZlibFDICT) | |
1528 return FlateErr; | |
1529 return 2; | |
1530 } | |
1531 | |
1532 int inflate_zlib_footer(uchar *p, int n, uint sum, uint len, uint zlen) { | |
1533 if (n < 4 || !check32(p, sum)) | |
1534 return FlateErr; | |
1535 return 4; | |
1536 } | |
1537 | |
1538 | |
1539 enum { | |
1540 GZipID1 = 0x1f, | |
1541 GZipID2 = 0x8b, | |
1542 GZipCM = 8, | |
1543 GZipFHCRC = 1 << 1, | |
1544 GZipFEXTRA = 1 << 2, | |
1545 GZipFNAME = 1 << 3, | |
1546 GZipFCOMM = 1 << 4, | |
1547 GZipXFL = 2, | |
1548 GZipOS = 255 | |
1549 }; | |
1550 | |
1551 int deflate_gzip_header(uchar *p, int n) { | |
1552 if (n < 10) | |
1553 return FlateErr; | |
1554 memset(p, 0, 10); | |
1555 p[0] = GZipID1; | |
1556 p[1] = GZipID2; | |
1557 p[2] = GZipCM; | |
1558 p[8] = GZipXFL; | |
1559 p[9] = GZipOS; | |
1560 return 10; | |
1561 } | |
1562 | |
1563 int deflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { | |
1564 if (n < 8) | |
1565 return FlateErr; | |
1566 set32le(p, sum); | |
1567 set32le(p+4, len); | |
1568 return 8; | |
1569 } | |
1570 | |
1571 int inflate_gzip_header(uchar *p, int n) { | |
1572 int k = 10; | |
1573 | |
1574 if (k > n) | |
1575 return FlateErr; | |
1576 if (p[0] != GZipID1 || p[1] != GZipID2 || p[2] != GZipCM) | |
1577 return FlateErr; | |
1578 if (p[3] & GZipFEXTRA) { | |
1579 k += 2 + ((p[k] << 8) | p[k+1]); | |
1580 if (k > n) | |
1581 return FlateErr; | |
1582 } | |
1583 if (p[3] & GZipFNAME) { | |
1584 for (; k < n; k++) | |
1585 if (p[k] == 0) | |
1586 break; | |
1587 k++; | |
1588 if (k > n) | |
1589 return FlateErr; | |
1590 } | |
1591 if (p[3] & GZipFCOMM) { | |
1592 for (; k < n; k++) | |
1593 if (p[k] == 0) | |
1594 break; | |
1595 k++; | |
1596 if (k > n) | |
1597 return FlateErr; | |
1598 } | |
1599 if (p[3] & GZipFHCRC) { | |
1600 k += 2; | |
1601 if (k > n) | |
1602 return FlateErr; | |
1603 } | |
1604 return k; | |
1605 } | |
1606 | |
1607 int inflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { | |
1608 if (n < 8 || !check32le(p, sum) || !check32le(p+4, len)) | |
1609 return FlateErr; | |
1610 return 8; | |
1611 } | |
1612 | |
1613 | |
1614 static char pkname[] = "sflate_stream"; | |
1615 | |
1616 enum { | |
1617 PKHeadID = 0x04034b50, | |
1618 PKDataID = 0x08074b50, | |
1619 PKDirID = 0x02014b50, | |
1620 PKFootID = 0x06054b50, | |
1621 PKVersion = 20, | |
1622 PKFlag = 1 << 3, | |
1623 PKMethod = 8, | |
1624 PKDate = ((2009 - 1980) << 25) | (1 << 21) | (1 << 16), | |
1625 PKHeadSize = 30, | |
1626 PKDirSize = 46, | |
1627 PKNameLen = sizeof(pkname) - 1 | |
1628 }; | |
1629 | |
1630 int deflate_pkzip_header(uchar *p, int n) { | |
1631 if (n < PKHeadSize + PKNameLen) | |
1632 return FlateErr; | |
1633 memset(p, 0, PKHeadSize); | |
1634 set32le(p, PKHeadID); | |
1635 set32le(p+4, PKVersion); | |
1636 set32le(p+6, PKFlag); | |
1637 set32le(p+8, PKMethod); | |
1638 set32le(p+10, PKDate); | |
1639 set32le(p+26, PKNameLen); | |
1640 memcpy(p + PKHeadSize, pkname, PKNameLen); | |
1641 return PKHeadSize + PKNameLen; | |
1642 } | |
1643 | |
1644 int deflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { | |
1645 if (n < PKDirSize + PKNameLen + 22) | |
1646 return FlateErr; | |
1647 /* unzip bug */ | |
1648 /* | |
1649 if (n < 16 + PKDirSize + PKNameLen + 22) | |
1650 return FlateErr; | |
1651 set32le(p, PKDataID); | |
1652 set32le(p+4, sum); | |
1653 set32le(p+8, zlen); | |
1654 set32le(p+12, len); | |
1655 p += 16; | |
1656 */ | |
1657 memset(p, 0, PKDirSize); | |
1658 set32le(p, PKDirID); | |
1659 set32le(p+4, PKVersion | (PKVersion << 16)); | |
1660 set32le(p+8, PKFlag); | |
1661 set32le(p+10, PKMethod); | |
1662 set32le(p+12, PKDate); | |
1663 set32le(p+16, sum); | |
1664 set32le(p+20, zlen); | |
1665 set32le(p+24, len); | |
1666 set32le(p+28, PKNameLen); | |
1667 memcpy(p + PKDirSize, pkname, PKNameLen); | |
1668 p += PKDirSize + PKNameLen; | |
1669 memset(p, 0, 22); | |
1670 set32le(p, PKFootID); | |
1671 p[8] = p[10] = 1; | |
1672 set32le(p+12, PKDirSize + PKNameLen); | |
1673 set32le(p+16, zlen + PKHeadSize + PKNameLen); | |
1674 return PKDirSize + PKNameLen + 22; | |
1675 /* | |
1676 set32le(p+12, 16 + PKDirSize + PKNameLen); | |
1677 set32le(p+16, zlen + PKHeadSize + PKNameLen); | |
1678 return 16 + PKDirSize + PKNameLen + 22; | |
1679 */ | |
1680 } | |
1681 | |
1682 int inflate_pkzip_header(uchar *p, int n) { | |
1683 int k = 30; | |
1684 | |
1685 if (k > n) | |
1686 return FlateErr; | |
1687 if (!check32le(p, PKHeadID)) | |
1688 return FlateErr; | |
1689 if ((p[4] | (p[5] << 8)) > PKVersion) | |
1690 return FlateErr; | |
1691 if ((p[8] | (p[9] << 8)) != PKMethod) | |
1692 return FlateErr; | |
1693 k += p[26] | (p[27] << 8); | |
1694 k += p[28] | (p[29] << 8); | |
1695 if (k > n) | |
1696 return FlateErr; | |
1697 return k; | |
1698 } | |
1699 | |
1700 int inflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { | |
1701 int k = PKDirSize + 22; | |
1702 | |
1703 if (k > n) | |
1704 return FlateErr; | |
1705 if (check32le(p, PKDataID)) { | |
1706 p += 16; | |
1707 k += 16; | |
1708 if (k > n) | |
1709 return FlateErr; | |
1710 } | |
1711 if (!check32le(p, PKDirID)) | |
1712 return FlateErr; | |
1713 if (!check32le(p+16, sum)) | |
1714 return FlateErr; | |
1715 if (!check32le(p+20, zlen)) | |
1716 return FlateErr; | |
1717 if (!check32le(p+24, len)) | |
1718 return FlateErr; | |
1719 return k; | |
1720 } | |
1721 | |
1722 | |
1723 /* example usage */ | |
1724 | |
1725 static int (*header)(uchar *, int); | |
1726 static int (*footer)(uchar *, int, uint, uint, uint); | |
1727 static uint (*checksum)(uchar *, int, uint); | |
1728 static char *err; | |
1729 static uint sum; | |
1730 static uint nin; | |
1731 static uint nout; | |
1732 static uint headerlen; | |
1733 static uint footerlen; | |
1734 static uint extralen; | |
1735 | |
1736 static int dummyheader(uchar *p, int n) { | |
1737 return 0; | |
1738 } | |
1739 static int dummyfooter(uchar *p, int n, uint sum, uint len, uint zlen) { | |
1740 return 0; | |
1741 } | |
1742 static uint dummysum(uchar *p, int n, uint sum) { | |
1743 return 0; | |
1744 } | |
1745 | |
1746 /* compress, using FlateStream interface */ | |
1747 int compress_stream(FILE *in, FILE *out) { | |
1748 FlateStream s; | |
1749 int k, n; | |
1750 enum {Nin = 1<<15, Nout = 1<<15}; | |
1751 | |
1752 s.in = malloc(Nin); | |
1753 s.out = malloc(Nout); | |
1754 s.nin = 0; | |
1755 s.nout = Nout; | |
1756 s.err = 0; | |
1757 s.state = 0; | |
1758 | |
1759 k = header(s.out, s.nout); | |
1760 if (k == FlateErr) { | |
1761 s.err = "header error."; | |
1762 n = FlateErr; | |
1763 } else { | |
1764 headerlen = s.nout = k; | |
1765 n = FlateOut; | |
1766 } | |
1767 for (;; n = deflate(&s)) | |
1768 switch (n) { | |
1769 case FlateOk: | |
1770 k = footer(s.out, s.nout, sum, nin, nout - headerlen); | |
1771 if (k == FlateErr) { | |
1772 s.err = "footer error."; | |
1773 n = FlateErr; | |
1774 } else if (k != fwrite(s.out, 1, k, out)) { | |
1775 s.err = "write error."; | |
1776 n = FlateErr; | |
1777 } else { | |
1778 footerlen = k; | |
1779 nout += k; | |
1780 } | |
1781 case FlateErr: | |
1782 free(s.in); | |
1783 free(s.out); | |
1784 err = s.err; | |
1785 return n; | |
1786 case FlateIn: | |
1787 s.nin = fread(s.in, 1, Nin, in); | |
1788 nin += s.nin; | |
1789 sum = checksum(s.in, s.nin, sum); | |
1790 break; | |
1791 case FlateOut: | |
1792 k = fwrite(s.out, 1, s.nout, out); | |
1793 if (k != s.nout) | |
1794 s.err = "write error."; | |
1795 nout += k; | |
1796 s.nout = Nout; | |
1797 break; | |
1798 } | |
1799 } | |
1800 | |
1801 /* decompress, using FlateStream interface */ | |
1802 int decompress_stream(FILE *in, FILE *out) { | |
1803 FlateStream s; | |
1804 uchar *begin; | |
1805 int k, n; | |
1806 enum {Nin = 1<<15, Nout = 1<<15}; | |
1807 | |
1808 s.in = begin = malloc(Nin); | |
1809 s.out = malloc(Nout); | |
1810 s.nout = Nout; | |
1811 s.err = 0; | |
1812 s.state = 0; | |
1813 | |
1814 s.nin = fread(s.in, 1, Nin, in); | |
1815 nin += s.nin; | |
1816 k = header(s.in, s.nin); | |
1817 if (k == FlateErr) { | |
1818 s.err = "header error."; | |
1819 n = FlateErr; | |
1820 } else { | |
1821 headerlen = k; | |
1822 s.nin -= k; | |
1823 s.in += k; | |
1824 n = inflate(&s); | |
1825 } | |
1826 for (;; n = inflate(&s)) | |
1827 switch (n) { | |
1828 case FlateOk: | |
1829 memmove(begin, s.in, s.nin); | |
1830 k = fread(begin, 1, Nin-s.nin, in); | |
1831 nin += k; | |
1832 s.nin += k; | |
1833 k = footer(begin, s.nin, sum, nout, nin - s.nin - headerlen); | |
1834 if (k == FlateErr) { | |
1835 s.err = "footer error."; | |
1836 n = FlateErr; | |
1837 } else { | |
1838 footerlen = k; | |
1839 extralen = s.nin - k; | |
1840 } | |
1841 case FlateErr: | |
1842 free(begin); | |
1843 free(s.out); | |
1844 err = s.err; | |
1845 return n; | |
1846 case FlateIn: | |
1847 s.in = begin; | |
1848 s.nin = fread(s.in, 1, Nin, in); | |
1849 nin += s.nin; | |
1850 break; | |
1851 case FlateOut: | |
1852 k = fwrite(s.out, 1, s.nout, out); | |
1853 if (k != s.nout) | |
1854 s.err = "write error."; | |
1855 sum = checksum(s.out, k, sum); | |
1856 nout += k; | |
1857 s.nout = Nout; | |
1858 break; | |
1859 } | |
1860 } | |
1861 | |
1862 static int old_main(int argc, char *argv[]) { | |
1863 char comp = 'c'; | |
1864 char fmt = 'r'; | |
1865 char verbose = 'q'; | |
1866 int (*call)(FILE *, FILE*); | |
1867 int n, i; | |
1868 | |
1869 for (i = 1; i < argc; i++) { | |
1870 if (argv[i][0] == '-' && argv[i][1] && argv[i][2] == 0) | |
1871 switch (argv[i][1]) { | |
1872 case 'q': | |
1873 case 'v': | |
1874 verbose = argv[i][1]; | |
1875 continue; | |
1876 case 'c': | |
1877 case 'd': | |
1878 comp = argv[i][1]; | |
1879 continue; | |
1880 case 'r': | |
1881 case 'g': | |
1882 case 'z': | |
1883 case 'p': | |
1884 fmt = argv[i][1]; | |
1885 continue; | |
1886 } | |
1887 fprintf(stderr, "usage: %s [-q|-v] [-c|-d] [-r|-g|-z|-p]\n\n" | |
1888 "deflate stream compression\n" | |
1889 " -q quiet (default)\n" | |
1890 " -v verbose\n" | |
1891 " -c compress (default)\n" | |
1892 " -d decompress\n" | |
1893 " -r raw (default)\n" | |
1894 " -g gzip\n" | |
1895 " -z zlib\n" | |
1896 " -p pkzip\n", argv[0]); | |
1897 return -1; | |
1898 } | |
1899 call = comp == 'c' ? compress_stream : decompress_stream; | |
1900 switch (fmt) { | |
1901 case 'r': | |
1902 header = dummyheader; | |
1903 footer = dummyfooter; | |
1904 checksum = dummysum; | |
1905 n = call(stdin, stdout); | |
1906 break; | |
1907 case 'g': | |
1908 if (comp == 'c') { | |
1909 header = deflate_gzip_header; | |
1910 footer = deflate_gzip_footer; | |
1911 } else { | |
1912 header = inflate_gzip_header; | |
1913 footer = inflate_gzip_footer; | |
1914 } | |
1915 checksum = crc32; | |
1916 crc32init(); | |
1917 n = call(stdin, stdout); | |
1918 break; | |
1919 case 'z': | |
1920 if (comp == 'c') { | |
1921 header = deflate_zlib_header; | |
1922 footer = deflate_zlib_footer; | |
1923 } else { | |
1924 header = inflate_zlib_header; | |
1925 footer = inflate_zlib_footer; | |
1926 } | |
1927 checksum = adler32; | |
1928 n = call(stdin, stdout); | |
1929 break; | |
1930 case 'p': | |
1931 if (comp == 'c') { | |
1932 header = deflate_pkzip_header; | |
1933 footer = deflate_pkzip_footer; | |
1934 } else { | |
1935 header = inflate_pkzip_header; | |
1936 footer = inflate_pkzip_footer; | |
1937 } | |
1938 checksum = crc32; | |
1939 crc32init(); | |
1940 n = call(stdin, stdout); | |
1941 break; | |
1942 default: | |
1943 err = "uninplemented."; | |
1944 n = FlateErr; | |
1945 break; | |
1946 } | |
1947 if (verbose == 'v') | |
1948 fprintf(stderr, "in:%d out:%d checksum: 0x%08x (header:%d data:%d footer:%d extra input:%s)\n", | |
1949 nin, nout, sum, headerlen, (comp == 'c' ? nout : nin) - headerlen - footerlen - extralen, | |
1950 footerlen, extralen ? "yes" : "no"); | |
1951 if (n != FlateOk) | |
1952 fprintf(stderr, "error: %s\n", err); | |
1953 return n; | |
1954 } | |
1955 | |
1956 // Total hack | |
1957 void gzip_main(void) | |
1958 { | |
1959 int i; | |
1960 | |
1961 for (i=0; toys.argv[i]; i++); | |
1962 old_main(i, toys.argv); | |
1963 } | |
1964 | |
1965 |