Mercurial > hg > toybox
annotate toys/pending/compress.c @ 1261:9e105bab92e5 draft
Revert lots of half-finished local debris I didn't mean to check in with Isaac's roadmap update.
Mercurial's "import" command is still broken, committing local tree changes to files that weren't even touched by the patch because the hg developers inisist, when I point out how stupid it is, that they meant to do that. (hg record can do hunks, but import can't even track _files_.)
author | Rob Landley <rob@landley.net> |
---|---|
date | Wed, 16 Apr 2014 08:54:19 -0500 |
parents | 6ca31490f581 |
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 } |