aboutsummaryrefslogtreecommitdiff
path: root/toys/pending
diff options
context:
space:
mode:
authorRob Landley <rob@landley.net>2014-02-13 06:45:35 -0600
committerRob Landley <rob@landley.net>2014-02-13 06:45:35 -0600
commit33b022d873abc5255e22bf70687e5c0a260fb107 (patch)
tree3adfed710b1639bf82d728f4da73fd5e6524de85 /toys/pending
parent3cd89c3f640e8ad2cdb422d0504554c2636a8412 (diff)
downloadtoybox-33b022d873abc5255e22bf70687e5c0a260fb107.tar.gz
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.
Diffstat (limited to 'toys/pending')
-rw-r--r--toys/pending/compress.c92
1 files changed, 66 insertions, 26 deletions
diff --git a/toys/pending/compress.c b/toys/pending/compress.c
index ca3af033..acc7d62b 100644
--- a/toys/pending/compress.c
+++ b/toys/pending/compress.c
@@ -41,7 +41,8 @@ GLOBALS(
char lenbits[29], distbits[30];
unsigned short lenbase[29], distbase[30];
- unsigned (*crc)(char *data, int len);
+ unsigned (*crcfunc)(char *data, int len);
+ unsigned crc;
char *outbuf;
unsigned outlen;
@@ -116,10 +117,14 @@ int bitbuf_get(struct bitbuf *bb, int bits)
return result;
}
-static void outbuf_crc(char *buf, int len)
+static void outbuf_crc(char sym)
{
- if (TT.crc) TT.crc(buf, len);
- xwrite(TT.outfd, buf, len);
+ TT.outbuf[TT.outlen++ & 32767] = sym;
+
+ if (!(TT.outlen & 32767)) {
+ xwrite(TT.outfd, TT.outbuf, 32768);
+ if (TT.crcfunc) TT.crcfunc(0, 32768);
+ }
}
// Huffman coding uses bits to traverse a binary tree to a leaf node,
@@ -139,7 +144,7 @@ struct huff {
static void len2huff(struct huff *huff, char bitlen[], int len)
{
int offset[16];
- int i, sum;
+ int i;
// Count number of codes at each bit length
memset(huff, 0, sizeof(struct huff));
@@ -147,7 +152,8 @@ static void len2huff(struct huff *huff, char bitlen[], int len)
// Sort symbols by bit length. (They'll remain sorted by symbol within that.)
*huff->length = *offset = 0;
- for (i = sum = 0; i<16; i++) offset[i] = offset[i-1] + huff->length[i];
+ for (i = 1; i<16; i++) offset[i] = offset[i-1] + huff->length[i-1];
+
for (i = 0; i<len; i++) if (bitlen[i]) huff->symbol[offset[bitlen[i]]++] = i;
}
@@ -165,10 +171,7 @@ static unsigned huff_and_puff(struct bitbuf *bb, struct huff *huff)
offset = (offset << 1) | bitbuf_bit(bb);
start += *++length;
if ((offset -= *length) < 0) break;
-// Note to self: what prevents overflow?
-// If we ensure ranges add up to sizeof(symbol), does that ensure all codes
-// terminate within table? Patholotical is 11111111...
-// if (length - huff_length > 16) error_exit("bad");
+ if ((length - huff->length) & 16) error_exit("bad symbol");
}
return huff->symbol[start + offset];
@@ -177,13 +180,18 @@ static unsigned huff_and_puff(struct bitbuf *bb, struct huff *huff)
// Decompress deflated data from bitbuf to filehandle.
static void inflate(struct bitbuf *bb)
{
+ struct huff *disthuff, *lithuff, *fixdisthuff = (struct huff *)(toybuf+2048),
+ *fixlithuff = (struct huff *)(toybuf+2560);
+
+// len2huff(
+
+ TT.crc = ~0;
// repeat until spanked
for (;;) {
int final, type;
final = bitbuf_get(bb, 1);
type = bitbuf_get(bb, 2);
-fprintf(stderr, "final=%d type=%d\n", final, type);
if (type == 3) error_exit("bad type");
@@ -200,27 +208,29 @@ fprintf(stderr, "final=%d type=%d\n", final, type);
// Dump output data
while (len) {
int pos = bb->bitpos >> 3, bblen = bb->len - pos;
+ char *p = bb->buf+pos;
+ // dump bytes until done or end of current bitbuf contents
if (bblen > len) bblen = len;
- if (bblen) outbuf_crc(bb->buf+pos, bblen);
- len -= bblen;
+ pos = bblen;
+ while (pos--) outbuf_crc(*(p++));
bitbuf_skip(bb, bblen << 3);
+ len -= bblen;
}
// Compressed block
} else {
-// struct huff huff;
// Dynamic huffman codes?
if (type == 2) {
- struct huff hlo;
- int i, literal, distance, hufflen;
+ struct huff *h2 = (struct huff *)(toybuf+512);
+ int i, litlen, distlen, hufflen;
char *hufflen_order = "\x10\x11\x12\0\x08\x07\x09\x06\x0a\x05\x0b"
"\x04\x0c\x03\x0d\x02\x0e\x01\x0f", *bits;
// The huffman trees are stored as a series of bit lengths
- literal = bitbuf_get(bb, 5)+257; // max 288
- distance = bitbuf_get(bb, 5)+1; // max 32
+ litlen = bitbuf_get(bb, 5)+257; // max 288
+ distlen = bitbuf_get(bb, 5)+1; // max 32
hufflen = bitbuf_get(bb, 4)+4; // max 19
// The literal and distance codes are themselves compressed, in
@@ -229,25 +239,55 @@ fprintf(stderr, "final=%d type=%d\n", final, type);
// in a magic order, leaving the rest 0. Then make a tree out of it:
memset(bits = toybuf+1, 0, 19);
for (i=0; i<hufflen; i++) bits[hufflen_order[i]] = bitbuf_get(bb, 3);
- len2huff(&hlo, bits, 19);
+ len2huff(h2, bits, 19);
// Use that tree to read in the literal and distance bit lengths
- for (i = 0; i < literal + distance; i++) {
- int sym = huff_and_puff(bb, &hlo);
+ for (i = 0; i < litlen + distlen;) {
+ int sym = huff_and_puff(bb, h2);
// 0-15 are literals, 16 = repeat previous code 3-6 times,
- // 17 = 3-10 zeroes, 18 = 11-138 zeroes
- if (sym < 16) bits[i] = sym;
- else memset(bits+i, bits[i-1] * !(sym&3),
- bitbuf_get(bb, (sym-14)+((sym&2)<<2)));
+ // 17 = 3-10 zeroes (3 bit), 18 = 11-138 zeroes (7 bit)
+ if (sym < 16) bits[i++] = sym;
+ else {
+ int len = sym & 2;
+
+ len = bitbuf_get(bb, sym-14+len+(len>>1)) + 3 + (len<<2);
+ memset(bits+i, bits[i-1] * !(sym&3), len);
+ i += len;
+ }
}
+ if (i > litlen+distlen) error_exit("bad tree");
+
+ len2huff(lithuff = (struct huff *)(toybuf+1024), bits, litlen);
+ len2huff(disthuff = (struct huff *)(toybuf+1536), bits+litlen, distlen);
+
// Static huffman codes
} else {
+ lithuff = fixlithuff;
+ disthuff = fixdisthuff;
+error_exit("todo static huffman init");
+ }
+ for (;;) {
+ int sym = huff_and_puff(bb, lithuff);
+
+ if (sym < 256) outbuf_crc(sym);
+ else if (sym > 256) {
+ int len, dist;
+
+ sym -= 257;
+ len = TT.lenbase[sym] + bitbuf_get(bb, TT.lenbits[sym]);
+ sym = huff_and_puff(bb, disthuff);
+ dist = TT.distbase[sym] + bitbuf_get(bb, TT.distbits[sym]);
+ sym = TT.outlen & 32767;
+
+ while (len--) outbuf_crc(TT.outbuf[(TT.outlen-dist) & 32767]);
+ } else break;
}
}
- if (final) return;
+ if (final) break;
}
+ if (TT.outlen & 32767) xwrite(TT.outfd, TT.outbuf, TT.outlen & 32767);
}
static void init_deflate(void)