123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485 |
- /* deflate.c - deflate/inflate code for gzip and friends
- *
- * Copyright 2014 Rob Landley <rob@landley.net>
- *
- * See RFCs 1950 (zlib), 1951 (deflate), and 1952 (gzip)
- * LSB 4.1 has gzip, gunzip, and zcat
- *
- * TODO: zip -d DIR -x LIST -list -quiet -no overwrite -overwrite -p to stdout
- */
- #include "toys.h"
- struct deflate {
- // Huffman codes: base offset and extra bits tables (length and distance)
- char lenbits[29], distbits[30];
- unsigned short lenbase[29], distbase[30];
- void *fixdisthuff, *fixlithuff;
- // CRC
- void (*crcfunc)(struct deflate *dd, char *data, int len);
- unsigned crctable[256], crc;
- // Tables only used for deflation
- unsigned short *hashhead, *hashchain;
- // Compressed data buffer (extra space malloced at end)
- unsigned pos, len;
- int infd, outfd;
- char data[];
- };
- // little endian bit buffer
- struct bitbuf {
- int fd, bitpos, len, max;
- char buf[];
- };
- // malloc a struct bitbuf
- static struct bitbuf *bitbuf_init(int fd, int size)
- {
- struct bitbuf *bb = xzalloc(sizeof(struct bitbuf)+size);
- bb->max = size;
- bb->fd = fd;
- return bb;
- }
- // Advance bitpos without the overhead of recording bits
- // Loads more data when input buffer empty
- static void bitbuf_skip(struct bitbuf *bb, int bits)
- {
- int pos = bb->bitpos + bits, len = bb->len << 3;
- while (pos >= len) {
- pos -= len;
- len = (bb->len = read(bb->fd, bb->buf, bb->max)) << 3;
- if (bb->len < 1) perror_exit("inflate EOF");
- }
- bb->bitpos = pos;
- }
- // Optimized single bit inlined version
- static inline int bitbuf_bit(struct bitbuf *bb)
- {
- int bufpos = bb->bitpos>>3;
- if (bufpos == bb->len) {
- bitbuf_skip(bb, 0);
- bufpos = 0;
- }
- return (bb->buf[bufpos]>>(bb->bitpos++&7))&1;
- }
- // Fetch the next X bits from the bitbuf, little endian
- static unsigned bitbuf_get(struct bitbuf *bb, int bits)
- {
- int result = 0, offset = 0;
- while (bits) {
- int click = bb->bitpos >> 3, blow, blen;
- // Load more data if buffer empty
- if (click == bb->len) bitbuf_skip(bb, click = 0);
- // grab bits from next byte
- blow = bb->bitpos & 7;
- blen = 8-blow;
- if (blen > bits) blen = bits;
- result |= ((bb->buf[click] >> blow) & ((1<<blen)-1)) << offset;
- offset += blen;
- bits -= blen;
- bb->bitpos += blen;
- }
- return result;
- }
- static void bitbuf_flush(struct bitbuf *bb)
- {
- if (!bb->bitpos) return;
- xwrite(bb->fd, bb->buf, (bb->bitpos+7)>>3);
- memset(bb->buf, 0, bb->max);
- bb->bitpos = 0;
- }
- static void bitbuf_put(struct bitbuf *bb, int data, int len)
- {
- while (len) {
- int click = bb->bitpos >> 3, blow, blen;
- // Flush buffer if necessary
- if (click == bb->max) {
- bitbuf_flush(bb);
- click = 0;
- }
- blow = bb->bitpos & 7;
- blen = 8-blow;
- if (blen > len) blen = len;
- bb->buf[click] |= data << blow;
- bb->bitpos += blen;
- data >>= blen;
- len -= blen;
- }
- }
- static void output_byte(struct deflate *dd, char sym)
- {
- int pos = dd->pos++ & 32767;
- dd->data[pos] = sym;
- if (pos == 32767) {
- xwrite(dd->outfd, dd->data, 32768);
- if (dd->crcfunc) dd->crcfunc(dd, dd->data, 32768);
- }
- }
- // Huffman coding uses bits to traverse a binary tree to a leaf node,
- // By placing frequently occurring symbols at shorter paths, frequently
- // used symbols may be represented in fewer bits than uncommon symbols.
- // (length[0] isn't used but code's clearer if it's there.)
- struct huff {
- unsigned short length[16]; // How many symbols have this bit length?
- unsigned short symbol[288]; // sorted by bit length, then ascending order
- };
- // Create simple huffman tree from array of bit lengths.
- // The symbols in the huffman trees are sorted (first by bit length
- // of the code to reach them, then by symbol number). This means that given
- // the bit length of each symbol, we can construct a unique tree.
- static void len2huff(struct huff *huff, char bitlen[], int len)
- {
- int offset[16];
- int i;
- // Count number of codes at each bit length
- memset(huff, 0, sizeof(struct huff));
- for (i = 0; i<len; i++) huff->length[bitlen[i]]++;
- // Sort symbols by bit length, then symbol. Get list of starting positions
- // for each group, then write each symbol to next position within its group.
- *huff->length = *offset = 0;
- 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;
- }
- // Fetch and decode next huffman coded symbol from bitbuf.
- // This takes advantage of the sorting to navigate the tree as an array:
- // each time we fetch a bit we have all the codes at that bit level in
- // order with no gaps.
- static unsigned huff_and_puff(struct bitbuf *bb, struct huff *huff)
- {
- unsigned short *length = huff->length;
- int start = 0, offset = 0;
- // Traverse through the bit lengths until our code is in this range
- for (;;) {
- offset = (offset << 1) | bitbuf_bit(bb);
- start += *++length;
- if ((offset -= *length) < 0) break;
- if ((length - huff->length) & 16) error_exit("bad symbol");
- }
- return huff->symbol[start + offset];
- }
- // Decompress deflated data from bitbuf to dd->outfd.
- static void inflate(struct deflate *dd, struct bitbuf *bb)
- {
- dd->crc = ~0;
- // repeat until spanked
- for (;;) {
- int final, type;
- final = bitbuf_get(bb, 1);
- type = bitbuf_get(bb, 2);
- if (type == 3) error_exit("bad type");
- // Uncompressed block?
- if (!type) {
- int len, nlen;
- // Align to byte, read length
- bitbuf_skip(bb, (8-bb->bitpos)&7);
- len = bitbuf_get(bb, 16);
- nlen = bitbuf_get(bb, 16);
- if (len != (0xffff & ~nlen)) error_exit("bad len");
- // Dump literal 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;
- pos = bblen;
- while (pos--) output_byte(dd, *(p++));
- bitbuf_skip(bb, bblen << 3);
- len -= bblen;
- }
- // Compressed block
- } else {
- struct huff *disthuff, *lithuff;
- // Dynamic huffman codes?
- if (type == 2) {
- struct huff *h2 = ((struct huff *)libbuf)+1;
- 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
- 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
- // a complicated way: an array of bit lengths (hufflen many
- // entries, each 3 bits) is used to fill out an array of 19 entries
- // in a magic order, leaving the rest 0. Then make a tree out of it:
- memset(bits = libbuf+1, 0, 19);
- for (i=0; i<hufflen; i++) bits[hufflen_order[i]] = bitbuf_get(bb, 3);
- len2huff(h2, bits, 19);
- // Use that tree to read in the literal and distance bit lengths
- 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 (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 = h2, bits, litlen);
- len2huff(disthuff = ((struct huff *)libbuf)+2, bits+litlen, distlen);
- // Static huffman codes
- } else {
- lithuff = dd->fixlithuff;
- disthuff = dd->fixdisthuff;
- }
- // Use huffman tables to decode block of compressed symbols
- for (;;) {
- int sym = huff_and_puff(bb, lithuff);
- // Literal?
- if (sym < 256) output_byte(dd, sym);
- // Copy range?
- else if (sym > 256) {
- int len, dist;
- sym -= 257;
- len = dd->lenbase[sym] + bitbuf_get(bb, dd->lenbits[sym]);
- sym = huff_and_puff(bb, disthuff);
- dist = dd->distbase[sym] + bitbuf_get(bb, dd->distbits[sym]);
- sym = dd->pos & 32767;
- while (len--) output_byte(dd, dd->data[(dd->pos-dist) & 32767]);
- // End of block
- } else break;
- }
- }
- // Was that the last block?
- if (final) break;
- }
- if (dd->pos & 32767) {
- xwrite(dd->outfd, dd->data, dd->pos&32767);
- if (dd->crcfunc) dd->crcfunc(dd, dd->data, dd->pos&32767);
- }
- }
- // Deflate from dd->infd to bitbuf
- // For deflate, dd->len = input read, dd->pos = input consumed
- static void deflate(struct deflate *dd, struct bitbuf *bb)
- {
- char *data = dd->data;
- int len, final = 0;
- dd->crc = ~0;
- while (!final) {
- // Read next half-window of data if we haven't hit EOF yet.
- len = readall(dd->infd, data+(dd->len&32768), 32768);
- if (len < 0) perror_exit("read"); // todo: add filename
- if (len != 32768) final++;
- if (dd->crcfunc) dd->crcfunc(dd, data+(dd->len&32768), len);
- // dd->len += len; crcfunc advances len TODO
- // store block as literal
- bitbuf_put(bb, final, 1);
- bitbuf_put(bb, 0, 1);
- bitbuf_put(bb, 0, (8-bb->bitpos)&7);
- bitbuf_put(bb, len, 16);
- bitbuf_put(bb, 0xffff & ~len, 16);
- // repeat until spanked
- while (dd->pos != dd->len) {
- unsigned pos = dd->pos&65535;
- bitbuf_put(bb, data[pos], 8);
- // need to refill buffer?
- if (!(32767 & ++dd->pos) && !final) break;
- }
- }
- bitbuf_flush(bb);
- }
- // Allocate memory for deflate/inflate.
- static struct deflate *init_deflate(int compress)
- {
- int i, n = 1;
- struct deflate *dd = xmalloc(sizeof(struct deflate)+32768*(compress ? 4 : 1));
- memset(dd, 0, sizeof(struct deflate));
- // decompress needs 32k history, compress adds 64k hashhead and 32k hashchain
- if (compress) {
- dd->hashhead = (unsigned short *)(dd->data+65536);
- dd->hashchain = (unsigned short *)(dd->data+65536+32768);
- }
- // Calculate lenbits, lenbase, distbits, distbase
- *dd->lenbase = 3;
- for (i = 0; i<sizeof(dd->lenbits)-1; i++) {
- if (i>4) {
- if (!(i&3)) {
- dd->lenbits[i]++;
- n <<= 1;
- }
- if (i == 27) n--;
- else dd->lenbits[i+1] = dd->lenbits[i];
- }
- dd->lenbase[i+1] = n + dd->lenbase[i];
- }
- n = 0;
- for (i = 0; i<sizeof(dd->distbits); i++) {
- dd->distbase[i] = 1<<n;
- if (i) dd->distbase[i] += dd->distbase[i-1];
- if (i>3 && !(i&1)) n++;
- dd->distbits[i] = n;
- }
- // TODO layout and lifetime of this?
- // Init fixed huffman tables
- for (i=0; i<288; i++) libbuf[i] = 8 + (i>143) - ((i>255)<<1) + (i>279);
- len2huff(dd->fixlithuff = ((struct huff *)libbuf)+3, libbuf, 288);
- memset(libbuf, 5, 30);
- len2huff(dd->fixdisthuff = ((struct huff *)libbuf)+4, libbuf, 30);
- return dd;
- }
- // Return true/false whether we consumed a gzip header.
- static int is_gzip(struct bitbuf *bb)
- {
- int flags;
- // Confirm signature
- if (bitbuf_get(bb, 24) != 0x088b1f || (flags = bitbuf_get(bb, 8)) > 31)
- return 0;
- bitbuf_skip(bb, 6*8);
- // Skip extra, name, comment, header CRC fields
- if (flags & 4) bitbuf_skip(bb, bitbuf_get(bb, 16) * 8);
- if (flags & 8) while (bitbuf_get(bb, 8));
- if (flags & 16) while (bitbuf_get(bb, 8));
- if (flags & 2) bitbuf_skip(bb, 16);
- return 1;
- }
- static void gzip_crc(struct deflate *dd, char *data, int len)
- {
- int i;
- unsigned crc, *crc_table = dd->crctable;
- crc = dd->crc;
- for (i=0; i<len; i++) crc = crc_table[(crc^data[i])&0xff] ^ (crc>>8);
- dd->crc = crc;
- dd->len += len;
- }
- long long gzip_fd(int infd, int outfd)
- {
- struct bitbuf *bb = bitbuf_init(outfd, 4096);
- struct deflate *dd = init_deflate(1);
- long long rc;
- // Header from RFC 1952 section 2.2:
- // 2 ID bytes (1F, 8b), gzip method byte (8=deflate), FLAG byte (none),
- // 4 byte MTIME (zeroed), Extra Flags (2=maximum compression),
- // Operating System (FF=unknown)
-
- dd->infd = infd;
- xwrite(bb->fd, "\x1f\x8b\x08\0\0\0\0\0\x02\xff", 10);
- // Little endian crc table
- crc_init(dd->crctable, 1);
- dd->crcfunc = gzip_crc;
- deflate(dd, bb);
- // tail: crc32, len32
- bitbuf_put(bb, 0, (8-bb->bitpos)&7);
- bitbuf_put(bb, ~dd->crc, 32);
- bitbuf_put(bb, dd->len, 32);
- rc = dd->len;
- bitbuf_flush(bb);
- free(bb);
- free(dd);
- return rc;
- }
- long long gunzip_fd(int infd, int outfd)
- {
- struct bitbuf *bb = bitbuf_init(infd, 4096);
- struct deflate *dd = init_deflate(0);
- long long rc;
- if (!is_gzip(bb)) error_exit("not gzip");
- dd->outfd = outfd;
- // Little endian crc table
- crc_init(dd->crctable, 1);
- dd->crcfunc = gzip_crc;
- inflate(dd, bb);
- // tail: crc32, len32
- bitbuf_skip(bb, (8-bb->bitpos)&7);
- if (~dd->crc != bitbuf_get(bb, 32) || dd->len != bitbuf_get(bb, 32))
- error_exit("bad crc");
- rc = dd->len;
- free(bb);
- free(dd);
- return rc;
- }
|