/* compress.c - deflate/inflate code for zip, gzip, zlib, and raw
*
* Copyright 2014 Rob Landley <rob@landley.net>
*
* The inflate/deflate code lives here, so the various things that use it
* either live here or call these commands to pipe data through them.
*
* Divergence from posix: replace obsolete/patented "compress" with mutiplexer.
* (gzip already replaces "uncompress".)
*
* 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
// Accept many different kinds of command line argument.
// Leave Lrg at end so flag values line up.
USE_COMPRESS(NEWTOY(compress, "zcd9lrg[-cd][!zgLr]", TOYFLAG_USR|TOYFLAG_BIN))
USE_GZIP(NEWTOY(gzip, USE_GZIP_D("d")"19dcflqStvgLRz[!gLRz]", TOYFLAG_USR|TOYFLAG_BIN))
USE_ZCAT(NEWTOY(zcat, 0, TOYFLAG_USR|TOYFLAG_BIN))
USE_GUNZIP(NEWTOY(gunzip, "cflqStv", TOYFLAG_USR|TOYFLAG_BIN))
//zip unzip gzip gunzip zcat
config COMPRESS
bool "compress"
default n
help
usage: compress [-zgLR19] [FILE]
Compress or decompress file (or stdin) using "deflate" algorithm.
-1 min compression
-9 max compression (default)
-g gzip (default)
-L zlib
-R raw
-z zip
config GZIP
bool "gzip"
default y
depends on COMPRESS
help
usage: gzip [-19cfqStvzgLR] [FILE...]
Compess (deflate) file(s). With no files, compress stdin to stdout.
On successful decompression, compressed files are replaced with the
uncompressed version. The input file is removed and replaced with
a new file without the .gz extension (with same ownership/permissions).
-1 Minimal compression (fastest)
-9 Max compression (default)
-c cat to stdout (act as zcat)
-f force (if output file exists, input is tty, unrecognized extension)
-q quiet (no warnings)
-S specify exension (default .*)
-t test compressed file(s)
-v verbose (like -l, but compress files)
Compression type:
-g gzip (default) -L zlib -R raw -z zip
config GZIP_D
bool
default y
depends on GZIP && DECOMPRESS
help
usage: gzip [-d]
-d decompress (act as gunzip)
config DECOMPRESS
bool "decompress"
default n
help
usage: compress [-zglrcd9] [FILE]
Compress or decompress file (or stdin) using "deflate" algorithm.
-c compress with -g gzip (default) -l zlib -r raw -z zip
-d decompress (autodetects type)
config ZCAT
bool "zcat"
default y
depends on DECOMPRESS
help
usage: zcat [FILE...]
Decompress deflated file(s) to stdout
config GUNZIP
bool "gunzip"
default y
depends on DECOMPRESS
help
usage: gunzip [-cflqStv] [FILE...]
Decompess (deflate) file(s). With no files, compress stdin to stdout.
On successful decompression, compressed files are replaced with the
uncompressed version. The input file is removed and replaced with
a new file without the .gz extension (with same ownership/permissions).
-c cat to stdout (act as zcat)
-f force (output file exists, input is tty, unrecognized extension)
-l list compressed/uncompressed/ratio/name for each input file.
-q quiet (no warnings)
-S specify exension (default .*)
-t test compressed file(s)
-v verbose (like -l, but decompress files)
*/
#define FOR_compress
#include "toys.h"
GLOBALS(
// 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)(char *data, int len);
unsigned crc;
// Compressed data buffer
char *data;
unsigned pos, len;
int infd, outfd;
// Tables only used for deflation
unsigned short *hashhead, *hashchain;
)
// little endian bit buffer
struct bitbuf {
int fd, bitpos, len, max;
char buf[];
};
// malloc a struct bitbuf
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
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
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;
}
void bitbuf_flush(struct bitbuf *bb)
{
if (!bb->bitpos) return;
xwrite(bb->fd, bb->buf, (bb->bitpos+7)/8);
memset(bb->buf, 0, bb->max);
bb->bitpos = 0;
}
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(char sym)
{
int pos = TT.pos++ & 32767;
TT.data[pos] = sym;
if (!pos) {
xwrite(TT.outfd, TT.data, 32768);
if (TT.crcfunc) TT.crcfunc(TT.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.
struct huff {
unsigned short length[16];
unsigned short symbol[288];
};
// 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. (They'll remain sorted by symbol within that.)
*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 TT.outfd.
static void inflate(struct bitbuf *bb)
{
TT.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(*(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 *)toybuf)+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 = toybuf+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 *)toybuf)+2, bits+litlen, distlen);
// Static huffman codes
} else {
lithuff = TT.fixlithuff;
disthuff = TT.fixdisthuff;
}
// Use huffman tables to decode block of compressed symbols
for (;;) {
int sym = huff_and_puff(bb, lithuff);
// Literal?
if (sym < 256) output_byte(sym);
// Copy range?
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.pos & 32767;
while (len--) output_byte(TT.data[(TT.pos-dist) & 32767]);
// End of block
} else break;
}
}
// Was that the last block?
if (final) break;
}
if (TT.pos & 32767) {
xwrite(TT.outfd, TT.data, TT.pos & 32767);
if (TT.crcfunc) TT.crcfunc(TT.data, TT.pos & 32767);
}
}
// Deflate from TT.infd to bitbuf
// For deflate, TT.len = input read, TT.pos = input consumed
static void deflate(struct bitbuf *bb)
{
char *data = TT.data;
int len, final = 0;
TT.crc = ~0;
while (!final) {
// Read next half-window of data if we haven't hit EOF yet.
len = readall(TT.infd, data+(TT.len&32768), 32768);
if (len < 0) perror_exit("read"); // todo: add filename
if (len != 32768) final++;
if (TT.crcfunc) TT.crcfunc(data+(TT.len&32768), len);
// TT.len += len; crcfunc advances len
// 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 (TT.pos != TT.len) {
unsigned pos = TT.pos & 65535;
bitbuf_put(bb, data[pos], 8);
// need to refill buffer?
if (!(32767 & ++TT.pos) && !final) break;
}
}
bitbuf_flush(bb);
}
// Allocate memory for deflate/inflate.
static void init_deflate(int compress)
{
int i, n = 1;
// compress needs 64k data and 32k each for hashhead and hashchain.
// decompress just needs 32k data.
TT.data = xmalloc(32768*(compress ? 4 : 1));
if (compress) {
TT.hashhead = (unsigned short *)(TT.data + 65536);
TT.hashchain = (unsigned short *)(TT.data + 65536 + 32768);
}
// Calculate lenbits, lenbase, distbits, distbase
*TT.lenbase = 3;
for (i = 0; i<sizeof(TT.lenbits)-1; i++) {
if (i>4) {
if (!(i&3)) {
TT.lenbits[i]++;
n <<= 1;
}
if (i == 27) n--;
else TT.lenbits[i+1] = TT.lenbits[i];
}
TT.lenbase[i+1] = n + TT.lenbase[i];
}
n = 0;
for (i = 0; i<sizeof(TT.distbits); i++) {
TT.distbase[i] = 1<<n;
if (i) TT.distbase[i] += TT.distbase[i-1];
if (i>3 && !(i&1)) n++;
TT.distbits[i] = n;
}
// Init fixed huffman tables
for (i=0; i<288; i++) toybuf[i] = 8 + (i>143) - ((i>255)<<1) + (i>279);
len2huff(TT.fixlithuff = ((struct huff *)toybuf)+3, toybuf, 288);
memset(toybuf, 5, 30);
len2huff(TT.fixdisthuff = ((struct huff *)toybuf)+4, toybuf, 30);
}
// 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, 16);
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;
}
void gzip_crc(char *data, int len)
{
int i;
unsigned crc, *crc_table = (unsigned *)(toybuf+sizeof(toybuf)-1024);
crc = TT.crc;
for (i=0; i<len; i++) crc = crc_table[(crc^data[i])&0xff] ^ (crc>>8);
TT.crc = crc;
TT.len += len;
}
static void do_gzip(int fd, char *name)
{
struct bitbuf *bb = bitbuf_init(1, sizeof(toybuf));
// 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)
TT.infd = fd;
xwrite(bb->fd, "\x1f\x8b\x08\0\0\0\0\0\x02\xff", 10);
// Use last 1k of toybuf for little endian crc table
crc_init((unsigned *)(toybuf+sizeof(toybuf)-1024), 1);
TT.crcfunc = gzip_crc;
deflate(bb);
// tail: crc32, len32
bitbuf_put(bb, 0, (8-bb->bitpos)&7);
bitbuf_put(bb, ~TT.crc, 32);
bitbuf_put(bb, TT.len, 32);
bitbuf_flush(bb);
free(bb);
}
static void do_zcat(int fd, char *name)
{
struct bitbuf *bb = bitbuf_init(fd, sizeof(toybuf));
if (!is_gzip(bb)) error_exit("not gzip");
TT.outfd = 1;
// Use last 1k of toybuf for little endian crc table
crc_init((unsigned *)(toybuf+sizeof(toybuf)-1024), 1);
TT.crcfunc = gzip_crc;
inflate(bb);
// tail: crc32, len32
bitbuf_skip(bb, (8-bb->bitpos)&7);
if (~TT.crc != bitbuf_get(bb, 32) || TT.len != bitbuf_get(bb, 32))
error_exit("bad crc");
free(bb);
}
// Parse many different kinds of command line argument:
void compress_main(void)
{
// todo: this
printf("hello world");
}
//#define CLEANUP_compress
//#define FOR_zcat
//#include "generated/flags.h"
void zcat_main(void)
{
init_deflate(0);
loopfiles(toys.optargs, do_zcat);
}
void gunzip_main(void)
{
init_deflate(0);
loopfiles(toys.optargs, do_zcat);
}
void gzip_main(void)
{
init_deflate(1);
loopfiles(toys.optargs, do_gzip);
}