Mercurial > hg > toybox
annotate toys/pending/compress.c @ 1276:d48bdc1cb017 draft
Switch human_readable() to just outputing decimal kilo/mega/gigabytes, make du use it, move it from lib/pending.c to lib.c.
author | Rob Landley <rob@landley.net> |
---|---|
date | Tue, 06 May 2014 06:31:28 -0500 |
parents | 9e105bab92e5 |
children | c0dee3caad31 |
rev | line source |
---|---|
1199 | 1 /* compress.c - deflate/inflate code for zip, gzip, zlib, and raw |
2 * | |
3 * Copyright 2014 Rob Landley <rob@landley.net> | |
4 * | |
5 * The inflate/deflate code lives here, so the various things that use it | |
6 * either live here or call these commands to pipe data through them. | |
7 * | |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
8 * Divergence from posix: replace obsolete "compress" with mutiplexer. |
1199 | 9 * |
10 * See RFCs 1950 (zlib), 1951 (deflate), and 1952 (gzip) | |
11 * LSB 4.1 has gzip, gunzip, and zcat | |
12 * TODO: zip -d DIR -x LIST -list -quiet -no overwrite -overwrite -p to stdout | |
13 | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
14 // Accept many different kinds of command line argument. |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
15 // Leave Lrg at end so flag values line up. |
1199 | 16 |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
17 USE_COMPRESS(NEWTOY(compress, "zcd9Lrg[-cd][!zgLr]", TOYFLAG_USR|TOYFLAG_BIN)) |
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
18 USE_COMPRESS(NEWTOY(zcat, "aLrg[!aLrg]", TOYFLAG_USR|TOYFLAG_BIN)) |
1199 | 19 |
20 //zip unzip gzip gunzip zcat | |
21 | |
22 config COMPRESS | |
23 bool "compress" | |
24 default n | |
25 help | |
26 usage: compress [-zglrcd9] [FILE] | |
27 | |
28 Compress or decompress file (or stdin) using "deflate" algorithm. | |
29 | |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
30 -c compress with -g gzip (default) -L zlib -r raw -z zip |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
31 -d decompress (autodetects type) |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
32 |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
33 config ZCAT |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
34 bool "zcat" |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
35 default n |
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
36 depends on COMPRESS |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
37 help |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
38 usage: zcat [FILE...] |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
39 |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
40 Decompress deflated file(s) to stdout |
1199 | 41 */ |
42 | |
43 #define FOR_compress | |
44 #include "toys.h" | |
45 | |
46 GLOBALS( | |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
47 // base offset and extra bits tables (length and distance) |
1199 | 48 char lenbits[29], distbits[30]; |
49 unsigned short lenbase[29], distbase[30]; | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
50 void *fixdisthuff, *fixlithuff; |
1200 | 51 |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
52 void (*crcfunc)(char *data, int len); |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
53 unsigned crc, len; |
1200 | 54 |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
55 char *outbuf; |
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
56 unsigned outlen; |
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
57 int outfd; |
1199 | 58 ) |
59 | |
60 // little endian bit buffer | |
61 struct bitbuf { | |
1200 | 62 int fd, bitpos, len, max; |
1199 | 63 char buf[]; |
64 }; | |
65 | |
1200 | 66 // malloc a struct bitbuf |
67 struct bitbuf *bitbuf_init(int fd, int size) | |
1199 | 68 { |
69 struct bitbuf *bb = xmalloc(sizeof(struct bitbuf)+size); | |
70 | |
71 memset(bb, 0, sizeof(struct bitbuf)); | |
72 bb->max = size; | |
73 bb->fd = fd; | |
74 | |
75 return bb; | |
76 } | |
77 | |
1200 | 78 // Advance bitpos without the overhead of recording bits |
79 void bitbuf_skip(struct bitbuf *bb, int bits) | |
80 { | |
81 int pos = bb->bitpos + bits, len = bb->len << 3; | |
82 | |
83 while (pos >= len) { | |
84 pos -= len; | |
85 len = (bb->len = read(bb->fd, bb->buf, bb->max)) << 3; | |
86 if (bb->len < 1) perror_exit("inflate EOF"); | |
87 } | |
88 bb->bitpos = pos; | |
89 } | |
90 | |
91 // Optimized single bit inlined version | |
92 static inline int bitbuf_bit(struct bitbuf *bb) | |
93 { | |
94 int bufpos = bb->bitpos>>3; | |
95 | |
96 if (bufpos == bb->len) { | |
97 bitbuf_skip(bb, 0); | |
98 bufpos = 0; | |
99 } | |
100 | |
101 return (bb->buf[bufpos]>>(bb->bitpos++&7))&1; | |
102 } | |
103 | |
104 // Fetch the next X bits from the bitbuf, little endian | |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
105 unsigned bitbuf_get(struct bitbuf *bb, int bits) |
1199 | 106 { |
107 int result = 0, offset = 0; | |
108 | |
109 while (bits) { | |
1200 | 110 int click = bb->bitpos >> 3, blow, blen; |
1199 | 111 |
112 // Load more data if buffer empty | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
113 if (click == bb->len) bitbuf_skip(bb, click = 0); |
1199 | 114 |
115 // grab bits from next byte | |
1200 | 116 blow = bb->bitpos & 7; |
1199 | 117 blen = 8-blow; |
118 if (blen > bits) blen = bits; | |
119 result |= ((bb->buf[click] >> blow) & ((1<<blen)-1)) << offset; | |
120 offset += blen; | |
121 bits -= blen; | |
1200 | 122 bb->bitpos += blen; |
1199 | 123 } |
124 | |
125 return result; | |
126 } | |
127 | |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
128 static void outbuf_crc(char sym) |
1200 | 129 { |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
130 TT.outbuf[TT.outlen++ & 32767] = sym; |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
131 |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
132 if (!(TT.outlen & 32767)) { |
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
133 xwrite(TT.outfd, TT.outbuf, 32768); |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
134 if (TT.crcfunc) TT.crcfunc(0, 32768); |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
135 } |
1200 | 136 } |
137 | |
138 // Huffman coding uses bits to traverse a binary tree to a leaf node, | |
139 // By placing frequently occurring symbols at shorter paths, frequently | |
140 // used symbols may be represented in fewer bits than uncommon symbols. | |
141 | |
142 struct huff { | |
143 unsigned short length[16]; | |
144 unsigned short symbol[288]; | |
145 }; | |
146 | |
147 // Create simple huffman tree from array of bit lengths. | |
148 | |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
149 // The symbols in deflate's huffman trees are sorted (first by bit length |
1200 | 150 // of the code to reach them, then by symbol number). This means that given |
151 // the bit length of each symbol, we can construct a unique tree. | |
152 static void len2huff(struct huff *huff, char bitlen[], int len) | |
153 { | |
154 int offset[16]; | |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
155 int i; |
1200 | 156 |
157 // Count number of codes at each bit length | |
158 memset(huff, 0, sizeof(struct huff)); | |
159 for (i = 0; i<len; i++) huff->length[bitlen[i]]++; | |
160 | |
161 // Sort symbols by bit length. (They'll remain sorted by symbol within that.) | |
162 *huff->length = *offset = 0; | |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
163 for (i = 1; i<16; i++) offset[i] = offset[i-1] + huff->length[i-1]; |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
164 |
1200 | 165 for (i = 0; i<len; i++) if (bitlen[i]) huff->symbol[offset[bitlen[i]]++] = i; |
166 } | |
167 | |
168 // Fetch and decode next huffman coded symbol from bitbuf. | |
169 // This takes advantage of the the sorting to navigate the tree as an array: | |
170 // each time we fetch a bit we have all the codes at that bit level in | |
171 // order with no gaps.. | |
172 static unsigned huff_and_puff(struct bitbuf *bb, struct huff *huff) | |
173 { | |
174 unsigned short *length = huff->length; | |
175 int start = 0, offset = 0; | |
176 | |
177 // Traverse through the bit lengths until our code is in this range | |
178 for (;;) { | |
179 offset = (offset << 1) | bitbuf_bit(bb); | |
180 start += *++length; | |
181 if ((offset -= *length) < 0) break; | |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
182 if ((length - huff->length) & 16) error_exit("bad symbol"); |
1200 | 183 } |
184 | |
185 return huff->symbol[start + offset]; | |
186 } | |
187 | |
188 // Decompress deflated data from bitbuf to filehandle. | |
189 static void inflate(struct bitbuf *bb) | |
1199 | 190 { |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
191 TT.crc = ~0; |
1200 | 192 // repeat until spanked |
193 for (;;) { | |
194 int final, type; | |
195 | |
196 final = bitbuf_get(bb, 1); | |
197 type = bitbuf_get(bb, 2); | |
198 | |
199 if (type == 3) error_exit("bad type"); | |
200 | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
201 // Uncompressed block? |
1200 | 202 if (!type) { |
203 int len, nlen; | |
204 | |
205 // Align to byte, read length | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
206 bitbuf_skip(bb, (8-bb->bitpos)&7); |
1200 | 207 len = bitbuf_get(bb, 16); |
208 nlen = bitbuf_get(bb, 16); | |
209 if (len != (0xffff & ~nlen)) error_exit("bad len"); | |
210 | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
211 // Dump literal output data |
1200 | 212 while (len) { |
213 int pos = bb->bitpos >> 3, bblen = bb->len - pos; | |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
214 char *p = bb->buf+pos; |
1200 | 215 |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
216 // dump bytes until done or end of current bitbuf contents |
1200 | 217 if (bblen > len) bblen = len; |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
218 pos = bblen; |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
219 while (pos--) outbuf_crc(*(p++)); |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
220 bitbuf_skip(bb, bblen << 3); |
1200 | 221 len -= bblen; |
222 } | |
223 | |
224 // Compressed block | |
225 } else { | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
226 struct huff *disthuff, *lithuff; |
1200 | 227 |
228 // Dynamic huffman codes? | |
229 if (type == 2) { | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
230 struct huff *h2 = ((struct huff *)toybuf)+1; |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
231 int i, litlen, distlen, hufflen; |
1200 | 232 char *hufflen_order = "\x10\x11\x12\0\x08\x07\x09\x06\x0a\x05\x0b" |
233 "\x04\x0c\x03\x0d\x02\x0e\x01\x0f", *bits; | |
234 | |
235 // The huffman trees are stored as a series of bit lengths | |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
236 litlen = bitbuf_get(bb, 5)+257; // max 288 |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
237 distlen = bitbuf_get(bb, 5)+1; // max 32 |
1200 | 238 hufflen = bitbuf_get(bb, 4)+4; // max 19 |
239 | |
240 // The literal and distance codes are themselves compressed, in | |
241 // a complicated way: an array of bit lengths (hufflen many | |
242 // entries, each 3 bits) is used to fill out an array of 19 entries | |
243 // in a magic order, leaving the rest 0. Then make a tree out of it: | |
244 memset(bits = toybuf+1, 0, 19); | |
245 for (i=0; i<hufflen; i++) bits[hufflen_order[i]] = bitbuf_get(bb, 3); | |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
246 len2huff(h2, bits, 19); |
1200 | 247 |
248 // Use that tree to read in the literal and distance bit lengths | |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
249 for (i = 0; i < litlen + distlen;) { |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
250 int sym = huff_and_puff(bb, h2); |
1200 | 251 |
252 // 0-15 are literals, 16 = repeat previous code 3-6 times, | |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
253 // 17 = 3-10 zeroes (3 bit), 18 = 11-138 zeroes (7 bit) |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
254 if (sym < 16) bits[i++] = sym; |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
255 else { |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
256 int len = sym & 2; |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
257 |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
258 len = bitbuf_get(bb, sym-14+len+(len>>1)) + 3 + (len<<2); |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
259 memset(bits+i, bits[i-1] * !(sym&3), len); |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
260 i += len; |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
261 } |
1200 | 262 } |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
263 if (i > litlen+distlen) error_exit("bad tree"); |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
264 |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
265 len2huff(lithuff = h2, bits, litlen); |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
266 len2huff(disthuff = ((struct huff *)toybuf)+2, bits+litlen, distlen); |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
267 |
1200 | 268 // Static huffman codes |
269 } else { | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
270 lithuff = TT.fixlithuff; |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
271 disthuff = TT.fixdisthuff; |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
272 } |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
273 |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
274 // Use huffman tables to decode block of compressed symbols |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
275 for (;;) { |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
276 int sym = huff_and_puff(bb, lithuff); |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
277 |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
278 // Literal? |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
279 if (sym < 256) outbuf_crc(sym); |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
280 |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
281 // Copy range? |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
282 else if (sym > 256) { |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
283 int len, dist; |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
284 |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
285 sym -= 257; |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
286 len = TT.lenbase[sym] + bitbuf_get(bb, TT.lenbits[sym]); |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
287 sym = huff_and_puff(bb, disthuff); |
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
288 dist = TT.distbase[sym] + bitbuf_get(bb, TT.distbits[sym]); |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
289 sym = TT.outlen & 32767; |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
290 |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
291 while (len--) outbuf_crc(TT.outbuf[(TT.outlen-dist) & 32767]); |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
292 |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
293 // End of block |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
294 } else break; |
1200 | 295 } |
296 } | |
297 | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
298 // Was that the last block? |
1201
9adf66c7dd4e
Ok, _maybe_ I'm rewriting deflate from scratch rather than cleaning up the existing one, but you can't prove it. I plead the fifth, third, twelvefth, twentieth, twenty-first, twenth-fith, and twenty-seventh.
Rob Landley <rob@landley.net>
parents:
1200
diff
changeset
|
299 if (final) break; |
1200 | 300 } |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
301 |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
302 if (TT.outlen & 32767) { |
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
303 xwrite(TT.outfd, TT.outbuf, TT.outlen & 32767); |
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
304 if (TT.crcfunc) TT.crcfunc(0, TT.outlen & 32767); |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
305 } |
1199 | 306 } |
307 | |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
308 static void init_deflate(void) |
1199 | 309 { |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
310 int i, n = 1; |
1199 | 311 |
1200 | 312 // Ye olde deflate window |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
313 TT.outbuf = xmalloc(32768); |
1200 | 314 |
1199 | 315 // Calculate lenbits, lenbase, distbits, distbase |
316 *TT.lenbase = 3; | |
317 for (i = 0; i<sizeof(TT.lenbits)-1; i++) { | |
318 if (i>4) { | |
319 if (!(i&3)) { | |
320 TT.lenbits[i]++; | |
321 n <<= 1; | |
322 } | |
323 if (i == 27) n--; | |
324 else TT.lenbits[i+1] = TT.lenbits[i]; | |
325 } | |
326 TT.lenbase[i+1] = n + TT.lenbase[i]; | |
327 } | |
328 n = 0; | |
329 for (i = 0; i<sizeof(TT.distbits); i++) { | |
330 TT.distbase[i] = 1<<n; | |
331 if (i) TT.distbase[i] += TT.distbase[i-1]; | |
332 if (i>3 && !(i&1)) n++; | |
333 TT.distbits[i] = n; | |
334 } | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
335 |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
336 // Init fixed huffman tables |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
337 for (i=0; i<288; i++) toybuf[i] = 8 + (i>143) - ((i>255)<<1) + (i>279); |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
338 len2huff(TT.fixlithuff = ((struct huff *)toybuf)+3, toybuf, 288); |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
339 memset(toybuf, 5, 30); |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
340 len2huff(TT.fixdisthuff = ((struct huff *)toybuf)+4, toybuf, 30); |
1199 | 341 } |
342 | |
343 // Return true/false whether we consumed a gzip header. | |
344 static int is_gzip(struct bitbuf *bb) | |
345 { | |
346 int flags; | |
347 | |
348 // Confirm signature | |
1200 | 349 if (bitbuf_get(bb, 24) != 0x088b1f || (flags = bitbuf_get(bb, 8)) > 31) |
350 return 0; | |
351 bitbuf_skip(bb, 6*8); | |
1199 | 352 |
353 // Skip extra, name, comment, header CRC fields | |
1200 | 354 if (flags & 4) bitbuf_skip(bb, 16); |
355 if (flags & 8) while (bitbuf_get(bb, 8)); | |
356 if (flags & 16) while (bitbuf_get(bb, 8)); | |
357 if (flags & 2) bitbuf_skip(bb, 16); | |
1199 | 358 |
359 return 1; | |
360 } | |
361 | |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
362 void gzip_crc(char *data, int len) |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
363 { |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
364 int i; |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
365 unsigned crc, *crc_table = (unsigned *)(toybuf+sizeof(toybuf)-1024); |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
366 |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
367 crc = TT.crc; |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
368 for (i=0; i<len; i++) crc = crc_table[(crc^TT.outbuf[i])&0xff] ^ (crc>>8); |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
369 TT.crc = crc; |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
370 TT.len += len; |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
371 } |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
372 |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
373 static void do_zcat(int fd, char *name) |
1199 | 374 { |
1200 | 375 struct bitbuf *bb = bitbuf_init(fd, sizeof(toybuf)); |
1199 | 376 |
1200 | 377 if (!is_gzip(bb)) error_exit("not gzip"); |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
378 TT.outfd = 1; |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
379 |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
380 // Use last 1k of toybuf for little endian crc table |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
381 crc_init((unsigned *)(toybuf+sizeof(toybuf)-1024), 1); |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
382 TT.crcfunc = gzip_crc; |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
383 |
1200 | 384 inflate(bb); |
1199 | 385 |
386 // tail: crc32, len32 | |
387 | |
1206
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
388 bitbuf_skip(bb, (8-bb->bitpos)&7); |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
389 if (~TT.crc != bitbuf_get(bb, 32) || TT.len != bitbuf_get(bb, 32)) |
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
390 error_exit("bad crc"); |
1199 | 391 free(bb); |
392 } | |
393 | |
394 // Parse many different kinds of command line argument: | |
395 | |
396 void compress_main(void) | |
397 { | |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
398 zcat_main(); |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
399 } |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
400 |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
401 //#define CLEANUP_compress |
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
402 //#define FOR_zcat |
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
403 //#include "generated/flags.h" |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
404 |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
405 void zcat_main(void) |
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
406 { |
1261
9e105bab92e5
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Rob Landley <rob@landley.net>
parents:
1251
diff
changeset
|
407 init_deflate(); |
1199 | 408 |
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
409 loopfiles(toys.optargs, do_zcat); |
1199 | 410 } |