Mercurial > hg > toybox
annotate toys/pending/compress.c @ 1215:4eaac3e63fa7 draft
Cleanup freeramdisk: tabs to 2 spaces, square brackets for option name, do optional cleanup under if (CFG_TOYBOX_FREE) guard.
| author | Rob Landley <rob@landley.net> |
|---|---|
| date | Sun, 09 Mar 2014 14:38:51 -0500 |
| parents | 1b36fd8dd5cf |
| children | 6ca31490f581 |
| 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 * | |
| 8 * Divergence from posix: replace obsolete "compress" with mutiplexer. | |
| 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 |
|
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
17 USE_COMPRESS(NEWTOY(compress, "zcd9Lrg[-cd][!zgLr]", TOYFLAG_USR|TOYFLAG_BIN)) |
|
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
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 | |
|
1204
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
30 -c compress with -g gzip (default) -L zlib -r raw -z zip |
|
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" |
|
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
35 default n |
|
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
36 depends on COMPRESS |
|
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( | |
| 47 // base offset and extra bits tables (length and distance) | |
| 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); |
|
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
53 unsigned crc, len; |
| 1200 | 54 |
| 55 char *outbuf; | |
| 56 unsigned outlen; | |
| 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 | |
|
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
|
128 static void outbuf_crc(char sym) |
| 1200 | 129 { |
|
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
|
130 TT.outbuf[TT.outlen++ & 32767] = 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
|
131 |
|
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
|
132 if (!(TT.outlen & 32767)) { |
|
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
|
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 | |
| 149 // The symbols in deflate's huffman trees are sorted (first by bit length | |
| 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; |
|
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
|
219 while (pos--) outbuf_crc(*(p++)); |
|
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? |
|
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
|
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]); |
|
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
|
289 sym = TT.outlen & 32767; |
|
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 |
|
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
|
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 |
|
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
302 if (TT.outlen & 32767) { |
|
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
303 xwrite(TT.outfd, TT.outbuf, TT.outlen & 32767); |
|
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
304 if (TT.crcfunc) TT.crcfunc(0, TT.outlen & 32767); |
|
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
305 } |
| 1199 | 306 } |
| 307 | |
| 308 static void init_deflate(void) | |
| 309 { | |
| 310 int i, n = 1; | |
| 311 | |
| 1200 | 312 // Ye olde deflate window |
| 313 TT.outbuf = xmalloc(32768); | |
| 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; |
|
1b36fd8dd5cf
Add crc code: zcat now works.
Rob Landley <rob@landley.net>
parents:
1204
diff
changeset
|
368 for (i=0; i<len; i++) crc = crc_table[(crc^TT.outbuf[i])&0xff] ^ (crc>>8); |
|
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"); |
| 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 |
|
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
401 //#define CLEANUP_compress |
|
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
402 //#define FOR_zcat |
|
a0f08d393def
Update inflate code: fixed tables, bugfixes, zcat alias.
Rob Landley <rob@landley.net>
parents:
1201
diff
changeset
|
403 //#include "generated/flags.h" |
|
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 { |
| 1199 | 407 init_deflate(); |
| 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 } |