1/* see LICENSE file for copyright and license details */
2
3/* deflate decoder adapted from puff.c, mark adlers rfc 1951 reference
4 * decoder. zlib license: copyright (c) 2002-2013 mark adler, provided
5 * as-is, free to use/alter/redistribute, origin not misrepresented,
6 * this notice kept. see zlib.net */
7
8#include <setjmp.h>
9#include <stdint.h>
10#include <stdio.h>
11#include <stdlib.h>
12#include <string.h>
13#include <time.h>
14#include <unistd.h>
15
16#include "util.h"
17
18#define MAXBITS 15
19#define MAXLCODES 286
20#define MAXDCODES 30
21#define MAXCODES (MAXLCODES + MAXDCODES)
22#define FIXLCODES 288
23
24struct InflateState {
25 unsigned char *out;
26 unsigned long outlen;
27 unsigned long outcnt;
28
29 const unsigned char *in;
30 unsigned long inlen;
31 unsigned long incnt;
32 int bitbuf;
33 int bitcnt;
34
35 jmp_buf env;
36};
37
38struct Huffman {
39 short *count;
40 short *symbol;
41};
42
43static int
44inflate_bits(struct InflateState *s, int need)
45{
46 long val;
47
48 val = s->bitbuf;
49 while (s->bitcnt < need) {
50 if (s->incnt == s->inlen)
51 longjmp(s->env, 1);
52 val |= (long)(s->in[s->incnt++]) << s->bitcnt;
53 s->bitcnt += 8;
54 }
55
56 s->bitbuf = (int)(val >> need);
57 s->bitcnt -= need;
58
59 return (int)(val & ((1L << need) - 1));
60}
61
62static int
63inflate_stored(struct InflateState *s)
64{
65 unsigned len;
66
67 s->bitbuf = 0;
68 s->bitcnt = 0;
69
70 if (s->incnt + 4 > s->inlen)
71 return 2;
72 len = s->in[s->incnt++];
73 len |= s->in[s->incnt++] << 8;
74 if (s->in[s->incnt++] != (~len & 0xff) || s->in[s->incnt++] != ((~len >> 8) & 0xff))
75 return -2;
76
77 if (s->incnt + len > s->inlen)
78 return 2;
79 if (s->out != NULL) {
80 if (s->outcnt + len > s->outlen)
81 return 1;
82 while (len--)
83 s->out[s->outcnt++] = s->in[s->incnt++];
84 } else {
85 s->outcnt += len;
86 s->incnt += len;
87 }
88
89 return 0;
90}
91
92/* codes are bit-reversed on the wire, rebuilt one bit at a time here */
93static int
94inflate_decode(struct InflateState *s, const struct Huffman *h)
95{
96 int len, code, first, count, index;
97 int bitbuf, left;
98 short *next;
99
100 bitbuf = s->bitbuf;
101 left = s->bitcnt;
102 code = first = index = 0;
103 len = 1;
104 next = h->count + 1;
105 for (;;) {
106 while (left--) {
107 code |= bitbuf & 1;
108 bitbuf >>= 1;
109 count = *next++;
110 if (code - count < first) {
111 s->bitbuf = bitbuf;
112 s->bitcnt = (s->bitcnt - len) & 7;
113 return h->symbol[index + (code - first)];
114 }
115 index += count;
116 first += count;
117 first <<= 1;
118 code <<= 1;
119 len++;
120 }
121 left = (MAXBITS + 1) - len;
122 if (left == 0)
123 break;
124 if (s->incnt == s->inlen)
125 longjmp(s->env, 1);
126 bitbuf = s->in[s->incnt++];
127 if (left > 8)
128 left = 8;
129 }
130 return -10;
131}
132
133/* 0: complete code, > 0: incomplete but usable, < 0: over-subscribed */
134static int
135huffman_construct(struct Huffman *h, const short *length, int n)
136{
137 int symbol, len, left;
138 short offs[MAXBITS + 1];
139
140 for (len = 0; len <= MAXBITS; len++)
141 h->count[len] = 0;
142 for (symbol = 0; symbol < n; symbol++)
143 (h->count[length[symbol]])++;
144 if (h->count[0] == n)
145 return 0;
146
147 left = 1;
148 for (len = 1; len <= MAXBITS; len++) {
149 left <<= 1;
150 left -= h->count[len];
151 if (left < 0)
152 return left;
153 }
154
155 offs[1] = 0;
156 for (len = 1; len < MAXBITS; len++)
157 offs[len + 1] = offs[len] + h->count[len];
158
159 for (symbol = 0; symbol < n; symbol++)
160 if (length[symbol] != 0)
161 h->symbol[offs[length[symbol]]++] = symbol;
162
163 return left;
164}
165
166static int
167inflate_codes(struct InflateState *s, const struct Huffman *lencode, const struct Huffman *distcode)
168{
169 int symbol, len;
170 unsigned dist;
171 static const short lens[29] = {3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19,
172 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131,
173 163, 195, 227, 258};
174 static const short lext[29] = {0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2,
175 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0};
176 static const short dists[30] = {1, 2, 3, 4, 5, 7, 9, 13, 17, 25,
177 33, 49, 65, 97, 129, 193, 257, 385, 513, 769,
178 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577};
179 static const short dext[30] = {0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6,
180 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13};
181
182 do {
183 symbol = inflate_decode(s, lencode);
184 if (symbol < 0)
185 return symbol;
186 if (symbol < 256) {
187 if (s->out != NULL) {
188 if (s->outcnt == s->outlen)
189 return 1;
190 s->out[s->outcnt] = symbol;
191 }
192 s->outcnt++;
193 } else if (symbol > 256) {
194 symbol -= 257;
195 if (symbol >= 29)
196 return -10;
197 len = lens[symbol] + inflate_bits(s, lext[symbol]);
198
199 symbol = inflate_decode(s, distcode);
200 if (symbol < 0)
201 return symbol;
202 dist = dists[symbol] + inflate_bits(s, dext[symbol]);
203 if (dist > s->outcnt)
204 return -11;
205
206 if (s->out != NULL) {
207 if (s->outcnt + len > s->outlen)
208 return 1;
209 while (len--) {
210 s->out[s->outcnt] = s->out[s->outcnt - dist];
211 s->outcnt++;
212 }
213 } else {
214 s->outcnt += len;
215 }
216 }
217 } while (symbol != 256);
218
219 return 0;
220}
221
222static int
223inflate_fixed(struct InflateState *s)
224{
225 static int built;
226 static short lencnt[MAXBITS + 1], lensym[FIXLCODES];
227 static short distcnt[MAXBITS + 1], distsym[MAXDCODES];
228 static struct Huffman lencode, distcode;
229
230 if (!built) {
231 int symbol;
232 short lengths[FIXLCODES];
233
234 lencode.count = lencnt;
235 lencode.symbol = lensym;
236 distcode.count = distcnt;
237 distcode.symbol = distsym;
238
239 for (symbol = 0; symbol < 144; symbol++)
240 lengths[symbol] = 8;
241 for (; symbol < 256; symbol++)
242 lengths[symbol] = 9;
243 for (; symbol < 280; symbol++)
244 lengths[symbol] = 7;
245 for (; symbol < FIXLCODES; symbol++)
246 lengths[symbol] = 8;
247 huffman_construct(&lencode, lengths, FIXLCODES);
248
249 for (symbol = 0; symbol < MAXDCODES; symbol++)
250 lengths[symbol] = 5;
251 huffman_construct(&distcode, lengths, MAXDCODES);
252
253 built = 1;
254 }
255
256 return inflate_codes(s, &lencode, &distcode);
257}
258
259static int
260inflate_dynamic(struct InflateState *s)
261{
262 int nlen, ndist, ncode, index, err;
263 short lengths[MAXCODES];
264 short lencnt[MAXBITS + 1], lensym[MAXLCODES];
265 short distcnt[MAXBITS + 1], distsym[MAXDCODES];
266 struct Huffman lencode, distcode;
267 static const short order[19] = {16, 17, 18, 0, 8, 7, 9, 6, 10, 5,
268 11, 4, 12, 3, 13, 2, 14, 1, 15};
269
270 lencode.count = lencnt;
271 lencode.symbol = lensym;
272 distcode.count = distcnt;
273 distcode.symbol = distsym;
274
275 nlen = inflate_bits(s, 5) + 257;
276 ndist = inflate_bits(s, 5) + 1;
277 ncode = inflate_bits(s, 4) + 4;
278 if (nlen > MAXLCODES || ndist > MAXDCODES)
279 return -3;
280
281 for (index = 0; index < ncode; index++)
282 lengths[order[index]] = inflate_bits(s, 3);
283 for (; index < 19; index++)
284 lengths[order[index]] = 0;
285
286 err = huffman_construct(&lencode, lengths, 19);
287 if (err != 0)
288 return -4;
289
290 index = 0;
291 while (index < nlen + ndist) {
292 int symbol, len;
293
294 symbol = inflate_decode(s, &lencode);
295 if (symbol < 0)
296 return symbol;
297 if (symbol < 16) {
298 lengths[index++] = symbol;
299 } else {
300 len = 0;
301 if (symbol == 16) {
302 if (index == 0)
303 return -5;
304 len = lengths[index - 1];
305 symbol = 3 + inflate_bits(s, 2);
306 } else if (symbol == 17) {
307 symbol = 3 + inflate_bits(s, 3);
308 } else {
309 symbol = 11 + inflate_bits(s, 7);
310 }
311 if (index + symbol > nlen + ndist)
312 return -6;
313 while (symbol--)
314 lengths[index++] = len;
315 }
316 }
317
318 if (lengths[256] == 0)
319 return -9;
320
321 err = huffman_construct(&lencode, lengths, nlen);
322 if (err && (err < 0 || nlen != lencode.count[0] + lencode.count[1]))
323 return -7;
324
325 err = huffman_construct(&distcode, lengths + nlen, ndist);
326 if (err && (err < 0 || ndist != distcode.count[0] + distcode.count[1]))
327 return -8;
328
329 return inflate_codes(s, &lencode, &distcode);
330}
331
332/* raw deflate (rfc 1951) decoder; dest null just computes destlen */
333static int
334inflate_raw(unsigned char *dest, unsigned long *destlen, const unsigned char *source,
335 unsigned long *sourcelen)
336{
337 struct InflateState s;
338 int last, type, err;
339
340 s.out = dest;
341 s.outlen = *destlen;
342 s.outcnt = 0;
343
344 s.in = source;
345 s.inlen = *sourcelen;
346 s.incnt = 0;
347 s.bitbuf = 0;
348 s.bitcnt = 0;
349
350 if (setjmp(s.env) != 0) {
351 err = 2;
352 } else {
353 do {
354 last = inflate_bits(&s, 1);
355 type = inflate_bits(&s, 2);
356 err = type == 0 ? inflate_stored(&s)
357 : type == 1 ? inflate_fixed(&s)
358 : type == 2 ? inflate_dynamic(&s)
359 : -1;
360 if (err != 0)
361 break;
362 } while (!last);
363 }
364
365 if (err <= 0) {
366 *destlen = s.outcnt;
367 *sourcelen = s.incnt;
368 }
369 return err;
370}
371
372static uint32_t crc32_table[256];
373
374static void
375crc32_init(void)
376{
377 uint32_t c;
378 int n, k;
379
380 for (n = 0; n < 256; n++) {
381 c = (uint32_t)n;
382 for (k = 0; k < 8; k++)
383 c = (c & 1) ? (0xedb88320u ^ (c >> 1)) : (c >> 1);
384 crc32_table[n] = c;
385 }
386}
387
388static uint32_t
389crc32_update(uint32_t crc, const unsigned char *buf, size_t len)
390{
391 crc = ~crc;
392 while (len--)
393 crc = crc32_table[(crc ^ *buf++) & 0xff] ^ (crc >> 8);
394 return ~crc;
395}
396
397static uint32_t
398get_le32(const unsigned char *p)
399{
400 return (uint32_t)p[0] | ((uint32_t)p[1] << 8) | ((uint32_t)p[2] << 16) | ((uint32_t)p[3] << 24);
401}
402
403static void
404put_le32(unsigned char *p, uint32_t v)
405{
406 p[0] = v & 0xff;
407 p[1] = (v >> 8) & 0xff;
408 p[2] = (v >> 16) & 0xff;
409 p[3] = (v >> 24) & 0xff;
410}
411
412/* FLG bits in the gzip header (rfc 1952) */
413enum GzipFlag {
414 GZ_FTEXT = 1 << 0,
415 GZ_FHCRC = 1 << 1,
416 GZ_FEXTRA = 1 << 2,
417 GZ_FNAME = 1 << 3,
418 GZ_FCOMMENT = 1 << 4,
419};
420
421static unsigned char *
422read_all(FILE *fp, size_t *len)
423{
424 unsigned char *buf;
425 size_t cap, n;
426 ssize_t r;
427
428 cap = 1 << 16;
429 buf = emalloc(cap);
430 n = 0;
431 for (;;) {
432 if (n == cap) {
433 cap *= 2;
434 buf = erealloc(buf, cap);
435 }
436 r = fread(buf + n, 1, cap - n, fp);
437 if (r <= 0)
438 break;
439 n += (size_t)r;
440 }
441 if (ferror(fp))
442 eprintf("read:");
443 *len = n;
444 return buf;
445}
446
447/* decodes one gzip member; multi-member streams are not supported */
448static void
449gunzip(const unsigned char *in, size_t inlen, FILE *out)
450{
451 size_t pos, hdr;
452 unsigned flg;
453 unsigned char *dest;
454 unsigned long destlen, srclen;
455 uint32_t want_crc, want_isize, got_crc;
456 int err;
457
458 if (inlen < 18 || in[0] != 0x1f || in[1] != 0x8b)
459 eprintf("gzip: not in gzip format\n");
460 if (in[2] != 8)
461 eprintf("gzip: unsupported compression method\n");
462
463 flg = in[3];
464 pos = 10;
465
466 if (flg & GZ_FEXTRA) {
467 unsigned xlen;
468 if (pos + 2 > inlen)
469 eprintf("gzip: truncated header\n");
470 xlen = in[pos] | (in[pos + 1] << 8);
471 pos += 2 + xlen;
472 }
473 if (flg & GZ_FNAME) {
474 while (pos < inlen && in[pos] != '\0')
475 pos++;
476 pos++;
477 }
478 if (flg & GZ_FCOMMENT) {
479 while (pos < inlen && in[pos] != '\0')
480 pos++;
481 pos++;
482 }
483 if (flg & GZ_FHCRC)
484 pos += 2;
485 if (pos + 8 > inlen)
486 eprintf("gzip: truncated header\n");
487
488 hdr = pos;
489
490 /* first pass just measures destlen, second pass does the real decode */
491 destlen = 0;
492 srclen = (unsigned long)(inlen - hdr - 8);
493 err = inflate_raw(NULL, &destlen, in + hdr, &srclen);
494 if (err != 0)
495 eprintf("gzip: corrupt compressed data\n");
496
497 dest = emalloc(destlen ? destlen : 1);
498 srclen = (unsigned long)(inlen - hdr - 8);
499 destlen = destlen ? destlen : 1;
500 err = inflate_raw(dest, &destlen, in + hdr, &srclen);
501 if (err != 0)
502 eprintf("gzip: corrupt compressed data\n");
503
504 want_crc = get_le32(in + hdr + srclen);
505 want_isize = get_le32(in + hdr + srclen + 4);
506 got_crc = crc32_update(0, dest, destlen);
507 if (got_crc != want_crc)
508 eprintf("gzip: crc mismatch\n");
509 if ((uint32_t)destlen != want_isize)
510 eprintf("gzip: size mismatch\n");
511
512 if (fwrite(dest, 1, destlen, out) != destlen)
513 eprintf("write:");
514 free(dest);
515}
516
517/* stored (uncompressed) deflate blocks: no compression, always valid */
518static void
519gzip_write_stored(const unsigned char *in, size_t len, FILE *out)
520{
521 unsigned char hdr[5];
522 size_t chunk;
523 int last;
524
525 if (len == 0) {
526 hdr[0] = 1;
527 hdr[1] = hdr[2] = hdr[3] = hdr[4] = 0;
528 if (fwrite(hdr, 1, 5, out) != 5)
529 eprintf("write:");
530 return;
531 }
532
533 while (len > 0) {
534 chunk = len > 65535 ? 65535 : len;
535 last = chunk == len;
536
537 hdr[0] = last ? 1 : 0;
538 hdr[1] = chunk & 0xff;
539 hdr[2] = (chunk >> 8) & 0xff;
540 hdr[3] = (~chunk) & 0xff;
541 hdr[4] = ((~chunk) >> 8) & 0xff;
542
543 if (fwrite(hdr, 1, 5, out) != 5 || fwrite(in, 1, chunk, out) != chunk)
544 eprintf("write:");
545
546 in += chunk;
547 len -= chunk;
548 }
549}
550
551static void
552gzip_compress(const unsigned char *in, size_t len, const char *name, FILE *out)
553{
554 unsigned char hdr[10];
555 unsigned char trl[8];
556 uint32_t crc;
557
558 hdr[0] = 0x1f;
559 hdr[1] = 0x8b;
560 hdr[2] = 8;
561 hdr[3] = name ? GZ_FNAME : 0;
562 put_le32(hdr + 4, 0);
563 hdr[8] = 0;
564 hdr[9] = 255;
565 if (fwrite(hdr, 1, 10, out) != 10)
566 eprintf("write:");
567 if (name && (fwrite(name, 1, strlen(name) + 1, out) != strlen(name) + 1))
568 eprintf("write:");
569
570 gzip_write_stored(in, len, out);
571
572 crc = crc32_update(0, in, len);
573 put_le32(trl, crc);
574 put_le32(trl + 4, (uint32_t)len);
575 if (fwrite(trl, 1, 8, out) != 8)
576 eprintf("write:");
577}
578
579static char *
580strip_gz_suffix(const char *name)
581{
582 size_t n = strlen(name);
583 if (n > 3 && strcmp(name + n - 3, ".gz") == 0)
584 return estrndup(name, n - 3);
585 return NULL;
586}
587
588static void
589usage(void)
590{
591 eprintf("usage: %s [-cdfkn] [-1..-9] [file ...]\n", argv0);
592}
593
594// ?man gzip: compress or decompress files
595// ?man arguments: [file ...]
596// ?man with no files, reads standard input and writes standard output
597// ?man compressing replaces each file with file.gz; decompressing
598// ?man reverses that. only single-member gzip streams are read back
599int
600main(int argc, char *argv[])
601{
602 int dflag = 0, cflag = 0, fflag = 0, kflag = 0, nflag = 0;
603 int i;
604 char outname[4096];
605
606 ARGBEGIN
607 {
608 // ?man -c: write to standard output, keep the input file
609 case 'c':
610 cflag = 1;
611 break;
612 // ?man -d: decompress instead of compress
613 case 'd':
614 dflag = 1;
615 break;
616 // ?man -f: accepted for compatibility, no effect
617 case 'f':
618 fflag = 1;
619 break;
620 // ?man -k: keep the input file instead of removing it
621 case 'k':
622 kflag = 1;
623 break;
624 // ?man -n: omit the original file name from the header
625 case 'n':
626 nflag = 1;
627 break;
628 // ?man -1: accepted for compatibility, no effect (stored blocks only)
629 case '1':
630 case '2':
631 case '3':
632 case '4':
633 case '5':
634 case '6':
635 case '7':
636 case '8':
637 case '9':
638 break;
639 default:
640 usage();
641 }
642 ARGEND
643
644 (void)fflag;
645 crc32_init();
646
647 if (argc == 0) {
648 unsigned char *buf;
649 size_t len;
650
651 buf = read_all(stdin, &len);
652 if (dflag)
653 gunzip(buf, len, stdout);
654 else
655 gzip_compress(buf, len, NULL, stdout);
656 free(buf);
657 return 0;
658 }
659
660 for (i = 0; i < argc; i++) {
661 FILE *fp;
662 unsigned char *buf;
663 size_t len;
664 char *stripped;
665
666 fp = fopen(argv[i], "rb");
667 if (!fp) {
668 weprintf("open %s:", argv[i]);
669 continue;
670 }
671 buf = read_all(fp, &len);
672 fclose(fp);
673
674 if (dflag) {
675 if (cflag) {
676 gunzip(buf, len, stdout);
677 } else {
678 stripped = strip_gz_suffix(argv[i]);
679 if (!stripped)
680 eprintf("gzip: %s: unknown suffix, ignored\n", argv[i]);
681 strlcpy(outname, stripped, sizeof(outname));
682 free(stripped);
683
684 fp = fopen(outname, "wb");
685 if (!fp)
686 eprintf("open %s:", outname);
687 gunzip(buf, len, fp);
688 if (fclose(fp))
689 eprintf("close %s:", outname);
690 if (!kflag && unlink(argv[i]) < 0)
691 weprintf("unlink %s:", argv[i]);
692 }
693 } else {
694 if (cflag) {
695 gzip_compress(buf, len, NULL, stdout);
696 } else {
697 strlcpy(outname, argv[i], sizeof(outname));
698 strlcat(outname, ".gz", sizeof(outname));
699
700 fp = fopen(outname, "wb");
701 if (!fp)
702 eprintf("open %s:", outname);
703 gzip_compress(buf, len, nflag ? NULL : argv[i], fp);
704 if (fclose(fp))
705 eprintf("close %s:", outname);
706 if (!kflag && unlink(argv[i]) < 0)
707 weprintf("unlink %s:", argv[i]);
708 }
709 }
710
711 free(buf);
712 }
713
714 return 0;
715}
