1b34b237e6229344ce460e117eb442db9a32fe813Rob Landley/* compress.c - deflate/inflate code for zip, gzip, zlib, and raw 2b34b237e6229344ce460e117eb442db9a32fe813Rob Landley * 3b34b237e6229344ce460e117eb442db9a32fe813Rob Landley * Copyright 2014 Rob Landley <rob@landley.net> 4b34b237e6229344ce460e117eb442db9a32fe813Rob Landley * 5b34b237e6229344ce460e117eb442db9a32fe813Rob Landley * The inflate/deflate code lives here, so the various things that use it 6b34b237e6229344ce460e117eb442db9a32fe813Rob Landley * either live here or call these commands to pipe data through them. 7b34b237e6229344ce460e117eb442db9a32fe813Rob Landley * 81ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley * Divergence from posix: replace obsolete/patented "compress" with mutiplexer. 91ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley * (gzip already replaces "uncompress".) 10b34b237e6229344ce460e117eb442db9a32fe813Rob Landley * 11b34b237e6229344ce460e117eb442db9a32fe813Rob Landley * See RFCs 1950 (zlib), 1951 (deflate), and 1952 (gzip) 12b34b237e6229344ce460e117eb442db9a32fe813Rob Landley * LSB 4.1 has gzip, gunzip, and zcat 13b34b237e6229344ce460e117eb442db9a32fe813Rob Landley * TODO: zip -d DIR -x LIST -list -quiet -no overwrite -overwrite -p to stdout 14b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 15c5dabf136495a69e9226eaa8316332de57ad481eRob Landley// Accept many different kinds of command line argument. 16c5dabf136495a69e9226eaa8316332de57ad481eRob Landley// Leave Lrg at end so flag values line up. 17b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 181ba12b427e84c5c6578aa767a096f5859e7283ceRob LandleyUSE_COMPRESS(NEWTOY(compress, "zcd9lrg[-cd][!zgLr]", TOYFLAG_USR|TOYFLAG_BIN)) 19b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 20b34b237e6229344ce460e117eb442db9a32fe813Rob Landley//zip unzip gzip gunzip zcat 21b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 22b34b237e6229344ce460e117eb442db9a32fe813Rob Landleyconfig COMPRESS 23b34b237e6229344ce460e117eb442db9a32fe813Rob Landley bool "compress" 24b34b237e6229344ce460e117eb442db9a32fe813Rob Landley default n 25b34b237e6229344ce460e117eb442db9a32fe813Rob Landley help 261ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley usage: compress [-zgLR19] [FILE] 271ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley 281ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley Compress or decompress file (or stdin) using "deflate" algorithm. 291ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley 301ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley -1 min compression 311ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley -9 max compression (default) 321ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley -g gzip (default) 331ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley -L zlib 341ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley -R raw 351ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley -z zip 361ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley 371ba12b427e84c5c6578aa767a096f5859e7283ceRob Landleyconfig DECOMPRESS 381ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley bool "decompress" 391ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley default n 401ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley help 41b34b237e6229344ce460e117eb442db9a32fe813Rob Landley usage: compress [-zglrcd9] [FILE] 42b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 43b34b237e6229344ce460e117eb442db9a32fe813Rob Landley Compress or decompress file (or stdin) using "deflate" algorithm. 44b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 451ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley -c compress with -g gzip (default) -l zlib -r raw -z zip 46c5dabf136495a69e9226eaa8316332de57ad481eRob Landley -d decompress (autodetects type) 47b34b237e6229344ce460e117eb442db9a32fe813Rob Landley*/ 48b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 49b34b237e6229344ce460e117eb442db9a32fe813Rob Landley#define FOR_compress 50b34b237e6229344ce460e117eb442db9a32fe813Rob Landley#include "toys.h" 51b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 52b34b237e6229344ce460e117eb442db9a32fe813Rob LandleyGLOBALS( 531ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley // Huffman codes: base offset and extra bits tables (length and distance) 54b34b237e6229344ce460e117eb442db9a32fe813Rob Landley char lenbits[29], distbits[30]; 55b34b237e6229344ce460e117eb442db9a32fe813Rob Landley unsigned short lenbase[29], distbase[30]; 56c5dabf136495a69e9226eaa8316332de57ad481eRob Landley void *fixdisthuff, *fixlithuff; 573cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 581ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley // CRC 59fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley void (*crcfunc)(char *data, int len); 601ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley unsigned crc; 611ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley 621ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley // Compressed data buffer 631ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley char *data; 641ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley unsigned pos, len; 652ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley int infd, outfd; 663cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 671ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley // Tables only used for deflation 682ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley unsigned short *hashhead, *hashchain; 69b34b237e6229344ce460e117eb442db9a32fe813Rob Landley) 70b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 71b34b237e6229344ce460e117eb442db9a32fe813Rob Landley// little endian bit buffer 72b34b237e6229344ce460e117eb442db9a32fe813Rob Landleystruct bitbuf { 733cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley int fd, bitpos, len, max; 74b34b237e6229344ce460e117eb442db9a32fe813Rob Landley char buf[]; 75b34b237e6229344ce460e117eb442db9a32fe813Rob Landley}; 76b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 773cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// malloc a struct bitbuf 783cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landleystruct bitbuf *bitbuf_init(int fd, int size) 79b34b237e6229344ce460e117eb442db9a32fe813Rob Landley{ 802ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley struct bitbuf *bb = xzalloc(sizeof(struct bitbuf)+size); 81b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 82b34b237e6229344ce460e117eb442db9a32fe813Rob Landley bb->max = size; 83b34b237e6229344ce460e117eb442db9a32fe813Rob Landley bb->fd = fd; 84b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 85b34b237e6229344ce460e117eb442db9a32fe813Rob Landley return bb; 86b34b237e6229344ce460e117eb442db9a32fe813Rob Landley} 87b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 883cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// Advance bitpos without the overhead of recording bits 893cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landleyvoid bitbuf_skip(struct bitbuf *bb, int bits) 903cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley{ 913cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley int pos = bb->bitpos + bits, len = bb->len << 3; 923cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 933cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley while (pos >= len) { 943cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley pos -= len; 953cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley len = (bb->len = read(bb->fd, bb->buf, bb->max)) << 3; 963cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (bb->len < 1) perror_exit("inflate EOF"); 973cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley } 983cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley bb->bitpos = pos; 993cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley} 1003cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 1013cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// Optimized single bit inlined version 1023cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landleystatic inline int bitbuf_bit(struct bitbuf *bb) 1033cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley{ 1043cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley int bufpos = bb->bitpos>>3; 1053cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 1063cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (bufpos == bb->len) { 1073cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley bitbuf_skip(bb, 0); 1083cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley bufpos = 0; 1093cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley } 1103cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 1113cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley return (bb->buf[bufpos]>>(bb->bitpos++&7))&1; 1123cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley} 1133cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 1143cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// Fetch the next X bits from the bitbuf, little endian 115fa1625d84e803df9a6a92551a106d42c62464e88Rob Landleyunsigned bitbuf_get(struct bitbuf *bb, int bits) 116b34b237e6229344ce460e117eb442db9a32fe813Rob Landley{ 117b34b237e6229344ce460e117eb442db9a32fe813Rob Landley int result = 0, offset = 0; 118b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 119b34b237e6229344ce460e117eb442db9a32fe813Rob Landley while (bits) { 1203cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley int click = bb->bitpos >> 3, blow, blen; 121b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 122b34b237e6229344ce460e117eb442db9a32fe813Rob Landley // Load more data if buffer empty 123c5dabf136495a69e9226eaa8316332de57ad481eRob Landley if (click == bb->len) bitbuf_skip(bb, click = 0); 124b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 125b34b237e6229344ce460e117eb442db9a32fe813Rob Landley // grab bits from next byte 1263cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley blow = bb->bitpos & 7; 127b34b237e6229344ce460e117eb442db9a32fe813Rob Landley blen = 8-blow; 128b34b237e6229344ce460e117eb442db9a32fe813Rob Landley if (blen > bits) blen = bits; 129b34b237e6229344ce460e117eb442db9a32fe813Rob Landley result |= ((bb->buf[click] >> blow) & ((1<<blen)-1)) << offset; 130b34b237e6229344ce460e117eb442db9a32fe813Rob Landley offset += blen; 131b34b237e6229344ce460e117eb442db9a32fe813Rob Landley bits -= blen; 1323cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley bb->bitpos += blen; 133b34b237e6229344ce460e117eb442db9a32fe813Rob Landley } 134b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 135b34b237e6229344ce460e117eb442db9a32fe813Rob Landley return result; 136b34b237e6229344ce460e117eb442db9a32fe813Rob Landley} 137b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 1382ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landleyvoid bitbuf_flush(struct bitbuf *bb) 1392ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley{ 1402ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley if (!bb->bitpos) return; 1412ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 1422ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley xwrite(bb->fd, bb->buf, (bb->bitpos+7)/8); 1432ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley memset(bb->buf, 0, bb->max); 1442ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bb->bitpos = 0; 1452ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley} 1462ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 1472ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landleyvoid bitbuf_put(struct bitbuf *bb, int data, int len) 1482ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley{ 1492ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley while (len) { 1502ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley int click = bb->bitpos >> 3, blow, blen; 1512ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 1522ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley // Flush buffer if necessary 1532ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley if (click == bb->max) { 1542ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_flush(bb); 1552ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley click = 0; 1562ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley } 1572ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley blow = bb->bitpos & 7; 1582ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley blen = 8-blow; 1592ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley if (blen > len) blen = len; 1602ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bb->buf[click] |= data << blow; 1612ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bb->bitpos += blen; 1622ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley data >>= blen; 1632ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley len -= blen; 1642ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley } 1652ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley} 1662ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 167747e74852b982f8b2c54dc3e3650352843a6bedeRob Landleystatic void output_byte(char sym) 1683cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley{ 169747e74852b982f8b2c54dc3e3650352843a6bedeRob Landley int pos = TT.pos++ & 32767; 17033b022d873abc5255e22bf70687e5c0a260fb107Rob Landley 171747e74852b982f8b2c54dc3e3650352843a6bedeRob Landley TT.data[pos] = sym; 172747e74852b982f8b2c54dc3e3650352843a6bedeRob Landley 17331b18720cc8aea4e531bcff4fc5a719b42a5d24bMike Moreton if (pos == 32767) { 1742ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley xwrite(TT.outfd, TT.data, 32768); 1752ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley if (TT.crcfunc) TT.crcfunc(TT.data, 32768); 17633b022d873abc5255e22bf70687e5c0a260fb107Rob Landley } 1773cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley} 1783cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 1793cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// Huffman coding uses bits to traverse a binary tree to a leaf node, 1803cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// By placing frequently occurring symbols at shorter paths, frequently 1813cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// used symbols may be represented in fewer bits than uncommon symbols. 1823cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 1833cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landleystruct huff { 1843cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley unsigned short length[16]; 1853cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley unsigned short symbol[288]; 1863cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley}; 1873cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 1883cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// Create simple huffman tree from array of bit lengths. 1893cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 1901ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley// The symbols in the huffman trees are sorted (first by bit length 1913cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// of the code to reach them, then by symbol number). This means that given 1923cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// the bit length of each symbol, we can construct a unique tree. 1933cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landleystatic void len2huff(struct huff *huff, char bitlen[], int len) 1943cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley{ 1953cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley int offset[16]; 19633b022d873abc5255e22bf70687e5c0a260fb107Rob Landley int i; 1973cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 1983cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // Count number of codes at each bit length 1993cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley memset(huff, 0, sizeof(struct huff)); 2003cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley for (i = 0; i<len; i++) huff->length[bitlen[i]]++; 2013cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2023cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // Sort symbols by bit length. (They'll remain sorted by symbol within that.) 2033cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley *huff->length = *offset = 0; 20433b022d873abc5255e22bf70687e5c0a260fb107Rob Landley for (i = 1; i<16; i++) offset[i] = offset[i-1] + huff->length[i-1]; 20533b022d873abc5255e22bf70687e5c0a260fb107Rob Landley 2063cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley for (i = 0; i<len; i++) if (bitlen[i]) huff->symbol[offset[bitlen[i]]++] = i; 2073cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley} 2083cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2093cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// Fetch and decode next huffman coded symbol from bitbuf. 2102ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley// This takes advantage of the sorting to navigate the tree as an array: 2113cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley// each time we fetch a bit we have all the codes at that bit level in 2122ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley// order with no gaps. 2133cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landleystatic unsigned huff_and_puff(struct bitbuf *bb, struct huff *huff) 214b34b237e6229344ce460e117eb442db9a32fe813Rob Landley{ 2153cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley unsigned short *length = huff->length; 2163cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley int start = 0, offset = 0; 2173cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2183cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // Traverse through the bit lengths until our code is in this range 2193cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley for (;;) { 2203cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley offset = (offset << 1) | bitbuf_bit(bb); 2213cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley start += *++length; 2223cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if ((offset -= *length) < 0) break; 22333b022d873abc5255e22bf70687e5c0a260fb107Rob Landley if ((length - huff->length) & 16) error_exit("bad symbol"); 2243cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley } 2253cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2263cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley return huff->symbol[start + offset]; 2273cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley} 2283cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2292ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley// Decompress deflated data from bitbuf to TT.outfd. 2303cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landleystatic void inflate(struct bitbuf *bb) 2313cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley{ 23233b022d873abc5255e22bf70687e5c0a260fb107Rob Landley TT.crc = ~0; 2333cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // repeat until spanked 2343cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley for (;;) { 2353cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley int final, type; 2363cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2373cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley final = bitbuf_get(bb, 1); 2383cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley type = bitbuf_get(bb, 2); 2393cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2403cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (type == 3) error_exit("bad type"); 2413cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 242c5dabf136495a69e9226eaa8316332de57ad481eRob Landley // Uncompressed block? 2433cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (!type) { 2443cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley int len, nlen; 2453cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2463cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // Align to byte, read length 247c5dabf136495a69e9226eaa8316332de57ad481eRob Landley bitbuf_skip(bb, (8-bb->bitpos)&7); 2483cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley len = bitbuf_get(bb, 16); 2493cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley nlen = bitbuf_get(bb, 16); 2503cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (len != (0xffff & ~nlen)) error_exit("bad len"); 2513cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 252c5dabf136495a69e9226eaa8316332de57ad481eRob Landley // Dump literal output data 2533cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley while (len) { 2543cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley int pos = bb->bitpos >> 3, bblen = bb->len - pos; 25533b022d873abc5255e22bf70687e5c0a260fb107Rob Landley char *p = bb->buf+pos; 2563cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 25733b022d873abc5255e22bf70687e5c0a260fb107Rob Landley // dump bytes until done or end of current bitbuf contents 2583cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (bblen > len) bblen = len; 25933b022d873abc5255e22bf70687e5c0a260fb107Rob Landley pos = bblen; 260747e74852b982f8b2c54dc3e3650352843a6bedeRob Landley while (pos--) output_byte(*(p++)); 2613cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley bitbuf_skip(bb, bblen << 3); 26233b022d873abc5255e22bf70687e5c0a260fb107Rob Landley len -= bblen; 2633cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley } 2643cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2653cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // Compressed block 2663cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley } else { 267c5dabf136495a69e9226eaa8316332de57ad481eRob Landley struct huff *disthuff, *lithuff; 2683cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2693cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // Dynamic huffman codes? 2703cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (type == 2) { 271c5dabf136495a69e9226eaa8316332de57ad481eRob Landley struct huff *h2 = ((struct huff *)toybuf)+1; 27233b022d873abc5255e22bf70687e5c0a260fb107Rob Landley int i, litlen, distlen, hufflen; 2733cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley char *hufflen_order = "\x10\x11\x12\0\x08\x07\x09\x06\x0a\x05\x0b" 2743cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley "\x04\x0c\x03\x0d\x02\x0e\x01\x0f", *bits; 2753cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2763cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // The huffman trees are stored as a series of bit lengths 27733b022d873abc5255e22bf70687e5c0a260fb107Rob Landley litlen = bitbuf_get(bb, 5)+257; // max 288 27833b022d873abc5255e22bf70687e5c0a260fb107Rob Landley distlen = bitbuf_get(bb, 5)+1; // max 32 2793cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley hufflen = bitbuf_get(bb, 4)+4; // max 19 2803cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2813cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // The literal and distance codes are themselves compressed, in 2823cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // a complicated way: an array of bit lengths (hufflen many 2833cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // entries, each 3 bits) is used to fill out an array of 19 entries 2843cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // in a magic order, leaving the rest 0. Then make a tree out of it: 2853cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley memset(bits = toybuf+1, 0, 19); 2863cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley for (i=0; i<hufflen; i++) bits[hufflen_order[i]] = bitbuf_get(bb, 3); 28733b022d873abc5255e22bf70687e5c0a260fb107Rob Landley len2huff(h2, bits, 19); 2883cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2893cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // Use that tree to read in the literal and distance bit lengths 29033b022d873abc5255e22bf70687e5c0a260fb107Rob Landley for (i = 0; i < litlen + distlen;) { 29133b022d873abc5255e22bf70687e5c0a260fb107Rob Landley int sym = huff_and_puff(bb, h2); 2923cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 2933cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // 0-15 are literals, 16 = repeat previous code 3-6 times, 29433b022d873abc5255e22bf70687e5c0a260fb107Rob Landley // 17 = 3-10 zeroes (3 bit), 18 = 11-138 zeroes (7 bit) 29533b022d873abc5255e22bf70687e5c0a260fb107Rob Landley if (sym < 16) bits[i++] = sym; 29633b022d873abc5255e22bf70687e5c0a260fb107Rob Landley else { 29733b022d873abc5255e22bf70687e5c0a260fb107Rob Landley int len = sym & 2; 29833b022d873abc5255e22bf70687e5c0a260fb107Rob Landley 29933b022d873abc5255e22bf70687e5c0a260fb107Rob Landley len = bitbuf_get(bb, sym-14+len+(len>>1)) + 3 + (len<<2); 30033b022d873abc5255e22bf70687e5c0a260fb107Rob Landley memset(bits+i, bits[i-1] * !(sym&3), len); 30133b022d873abc5255e22bf70687e5c0a260fb107Rob Landley i += len; 30233b022d873abc5255e22bf70687e5c0a260fb107Rob Landley } 3033cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley } 30433b022d873abc5255e22bf70687e5c0a260fb107Rob Landley if (i > litlen+distlen) error_exit("bad tree"); 30533b022d873abc5255e22bf70687e5c0a260fb107Rob Landley 306fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley len2huff(lithuff = h2, bits, litlen); 307fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley len2huff(disthuff = ((struct huff *)toybuf)+2, bits+litlen, distlen); 30833b022d873abc5255e22bf70687e5c0a260fb107Rob Landley 3093cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley // Static huffman codes 3103cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley } else { 311c5dabf136495a69e9226eaa8316332de57ad481eRob Landley lithuff = TT.fixlithuff; 312c5dabf136495a69e9226eaa8316332de57ad481eRob Landley disthuff = TT.fixdisthuff; 31333b022d873abc5255e22bf70687e5c0a260fb107Rob Landley } 314c5dabf136495a69e9226eaa8316332de57ad481eRob Landley 315c5dabf136495a69e9226eaa8316332de57ad481eRob Landley // Use huffman tables to decode block of compressed symbols 31633b022d873abc5255e22bf70687e5c0a260fb107Rob Landley for (;;) { 31733b022d873abc5255e22bf70687e5c0a260fb107Rob Landley int sym = huff_and_puff(bb, lithuff); 31833b022d873abc5255e22bf70687e5c0a260fb107Rob Landley 319c5dabf136495a69e9226eaa8316332de57ad481eRob Landley // Literal? 320747e74852b982f8b2c54dc3e3650352843a6bedeRob Landley if (sym < 256) output_byte(sym); 321c5dabf136495a69e9226eaa8316332de57ad481eRob Landley 322c5dabf136495a69e9226eaa8316332de57ad481eRob Landley // Copy range? 32333b022d873abc5255e22bf70687e5c0a260fb107Rob Landley else if (sym > 256) { 32433b022d873abc5255e22bf70687e5c0a260fb107Rob Landley int len, dist; 32533b022d873abc5255e22bf70687e5c0a260fb107Rob Landley 32633b022d873abc5255e22bf70687e5c0a260fb107Rob Landley sym -= 257; 32733b022d873abc5255e22bf70687e5c0a260fb107Rob Landley len = TT.lenbase[sym] + bitbuf_get(bb, TT.lenbits[sym]); 32833b022d873abc5255e22bf70687e5c0a260fb107Rob Landley sym = huff_and_puff(bb, disthuff); 32933b022d873abc5255e22bf70687e5c0a260fb107Rob Landley dist = TT.distbase[sym] + bitbuf_get(bb, TT.distbits[sym]); 3301ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley sym = TT.pos & 32767; 33133b022d873abc5255e22bf70687e5c0a260fb107Rob Landley 332747e74852b982f8b2c54dc3e3650352843a6bedeRob Landley while (len--) output_byte(TT.data[(TT.pos-dist) & 32767]); 333c5dabf136495a69e9226eaa8316332de57ad481eRob Landley 334c5dabf136495a69e9226eaa8316332de57ad481eRob Landley // End of block 33533b022d873abc5255e22bf70687e5c0a260fb107Rob Landley } else break; 3363cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley } 3373cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley } 3383cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 339c5dabf136495a69e9226eaa8316332de57ad481eRob Landley // Was that the last block? 34033b022d873abc5255e22bf70687e5c0a260fb107Rob Landley if (final) break; 3413cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley } 342fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley 3431ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley if (TT.pos & 32767) { 3442ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley xwrite(TT.outfd, TT.data, TT.pos & 32767); 3452ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley if (TT.crcfunc) TT.crcfunc(TT.data, TT.pos & 32767); 3462ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley } 3472ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley} 3482ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 3492ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley// Deflate from TT.infd to bitbuf 3502ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley// For deflate, TT.len = input read, TT.pos = input consumed 3512ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landleystatic void deflate(struct bitbuf *bb) 3522ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley{ 3532ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley char *data = TT.data; 3542ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley int len, final = 0; 3552ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 3562ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley TT.crc = ~0; 3572ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 3582ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley while (!final) { 3592ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley // Read next half-window of data if we haven't hit EOF yet. 3602ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley len = readall(TT.infd, data+(TT.len&32768), 32768); 3612ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley if (len < 0) perror_exit("read"); // todo: add filename 3622ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley if (len != 32768) final++; 3632ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley if (TT.crcfunc) TT.crcfunc(data+(TT.len&32768), len); 3642ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley // TT.len += len; crcfunc advances len 3652ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 3662ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley // store block as literal 3672ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_put(bb, final, 1); 3682ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_put(bb, 0, 1); 3692ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 3702ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_put(bb, 0, (8-bb->bitpos)&7); 3712ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_put(bb, len, 16); 3722ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_put(bb, 0xffff & ~len, 16); 3732ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 3742ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley // repeat until spanked 3752ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley while (TT.pos != TT.len) { 3762ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley unsigned pos = TT.pos & 65535; 3772ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 3782ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_put(bb, data[pos], 8); 3792ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 3802ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley // need to refill buffer? 3812ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley if (!(32767 & ++TT.pos) && !final) break; 3822ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley } 383fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley } 3842ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_flush(bb); 385b34b237e6229344ce460e117eb442db9a32fe813Rob Landley} 386b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 3871ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley// Allocate memory for deflate/inflate. 3881ba12b427e84c5c6578aa767a096f5859e7283ceRob Landleystatic void init_deflate(int compress) 389b34b237e6229344ce460e117eb442db9a32fe813Rob Landley{ 3906c64f5f186d26d4c95d408979d33831935e026f1Rob Landley int i, n = 1; 391b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 3922ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley // compress needs 64k data and 32k each for hashhead and hashchain. 3932ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley // decompress just needs 32k data. 3942ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley TT.data = xmalloc(32768*(compress ? 4 : 1)); 3951ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley if (compress) { 3962ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley TT.hashhead = (unsigned short *)(TT.data + 65536); 3972ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley TT.hashchain = (unsigned short *)(TT.data + 65536 + 32768); 3981ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley } 3993cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley 400b34b237e6229344ce460e117eb442db9a32fe813Rob Landley // Calculate lenbits, lenbase, distbits, distbase 401b34b237e6229344ce460e117eb442db9a32fe813Rob Landley *TT.lenbase = 3; 402b34b237e6229344ce460e117eb442db9a32fe813Rob Landley for (i = 0; i<sizeof(TT.lenbits)-1; i++) { 403b34b237e6229344ce460e117eb442db9a32fe813Rob Landley if (i>4) { 404b34b237e6229344ce460e117eb442db9a32fe813Rob Landley if (!(i&3)) { 405b34b237e6229344ce460e117eb442db9a32fe813Rob Landley TT.lenbits[i]++; 406b34b237e6229344ce460e117eb442db9a32fe813Rob Landley n <<= 1; 407b34b237e6229344ce460e117eb442db9a32fe813Rob Landley } 408b34b237e6229344ce460e117eb442db9a32fe813Rob Landley if (i == 27) n--; 409b34b237e6229344ce460e117eb442db9a32fe813Rob Landley else TT.lenbits[i+1] = TT.lenbits[i]; 410b34b237e6229344ce460e117eb442db9a32fe813Rob Landley } 411b34b237e6229344ce460e117eb442db9a32fe813Rob Landley TT.lenbase[i+1] = n + TT.lenbase[i]; 412b34b237e6229344ce460e117eb442db9a32fe813Rob Landley } 413b34b237e6229344ce460e117eb442db9a32fe813Rob Landley n = 0; 414b34b237e6229344ce460e117eb442db9a32fe813Rob Landley for (i = 0; i<sizeof(TT.distbits); i++) { 415b34b237e6229344ce460e117eb442db9a32fe813Rob Landley TT.distbase[i] = 1<<n; 416b34b237e6229344ce460e117eb442db9a32fe813Rob Landley if (i) TT.distbase[i] += TT.distbase[i-1]; 417b34b237e6229344ce460e117eb442db9a32fe813Rob Landley if (i>3 && !(i&1)) n++; 418b34b237e6229344ce460e117eb442db9a32fe813Rob Landley TT.distbits[i] = n; 419b34b237e6229344ce460e117eb442db9a32fe813Rob Landley } 420c5dabf136495a69e9226eaa8316332de57ad481eRob Landley 421c5dabf136495a69e9226eaa8316332de57ad481eRob Landley // Init fixed huffman tables 422c5dabf136495a69e9226eaa8316332de57ad481eRob Landley for (i=0; i<288; i++) toybuf[i] = 8 + (i>143) - ((i>255)<<1) + (i>279); 423fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley len2huff(TT.fixlithuff = ((struct huff *)toybuf)+3, toybuf, 288); 424c5dabf136495a69e9226eaa8316332de57ad481eRob Landley memset(toybuf, 5, 30); 425fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley len2huff(TT.fixdisthuff = ((struct huff *)toybuf)+4, toybuf, 30); 426b34b237e6229344ce460e117eb442db9a32fe813Rob Landley} 427b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 428b34b237e6229344ce460e117eb442db9a32fe813Rob Landley// Return true/false whether we consumed a gzip header. 429b34b237e6229344ce460e117eb442db9a32fe813Rob Landleystatic int is_gzip(struct bitbuf *bb) 430b34b237e6229344ce460e117eb442db9a32fe813Rob Landley{ 431b34b237e6229344ce460e117eb442db9a32fe813Rob Landley int flags; 432b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 433b34b237e6229344ce460e117eb442db9a32fe813Rob Landley // Confirm signature 4343cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (bitbuf_get(bb, 24) != 0x088b1f || (flags = bitbuf_get(bb, 8)) > 31) 4353cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley return 0; 4363cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley bitbuf_skip(bb, 6*8); 437b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 438b34b237e6229344ce460e117eb442db9a32fe813Rob Landley // Skip extra, name, comment, header CRC fields 4393cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (flags & 4) bitbuf_skip(bb, 16); 4403cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (flags & 8) while (bitbuf_get(bb, 8)); 4413cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (flags & 16) while (bitbuf_get(bb, 8)); 4423cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (flags & 2) bitbuf_skip(bb, 16); 443b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 444b34b237e6229344ce460e117eb442db9a32fe813Rob Landley return 1; 445b34b237e6229344ce460e117eb442db9a32fe813Rob Landley} 446b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 447fa1625d84e803df9a6a92551a106d42c62464e88Rob Landleyvoid gzip_crc(char *data, int len) 448fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley{ 449fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley int i; 450fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley unsigned crc, *crc_table = (unsigned *)(toybuf+sizeof(toybuf)-1024); 451fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley 452fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley crc = TT.crc; 4532ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley for (i=0; i<len; i++) crc = crc_table[(crc^data[i])&0xff] ^ (crc>>8); 454fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley TT.crc = crc; 455fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley TT.len += len; 456fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley} 457fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley 4582ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landleystatic void do_gzip(int fd, char *name) 4591ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley{ 4601ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley struct bitbuf *bb = bitbuf_init(1, sizeof(toybuf)); 4611ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley 4621ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley // Header from RFC 1952 section 2.2: 4631ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley // 2 ID bytes (1F, 8b), gzip method byte (8=deflate), FLAG byte (none), 4641ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley // 4 byte MTIME (zeroed), Extra Flags (2=maximum compression), 4651ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley // Operating System (FF=unknown) 4661ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley 4672ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley TT.infd = fd; 4682ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley xwrite(bb->fd, "\x1f\x8b\x08\0\0\0\0\0\x02\xff", 10); 4692ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 4702ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley // Use last 1k of toybuf for little endian crc table 4712ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley crc_init((unsigned *)(toybuf+sizeof(toybuf)-1024), 1); 4722ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley TT.crcfunc = gzip_crc; 4731ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley 4741ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley deflate(bb); 4751ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley 4762ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley // tail: crc32, len32 4772ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 4782ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_put(bb, 0, (8-bb->bitpos)&7); 4792ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_put(bb, ~TT.crc, 32); 4802ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_put(bb, TT.len, 32); 4812ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley 4822ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley bitbuf_flush(bb); 4831ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley free(bb); 4841ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley} 4851ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley 486c5dabf136495a69e9226eaa8316332de57ad481eRob Landleystatic void do_zcat(int fd, char *name) 487b34b237e6229344ce460e117eb442db9a32fe813Rob Landley{ 4883cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley struct bitbuf *bb = bitbuf_init(fd, sizeof(toybuf)); 489b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 4903cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley if (!is_gzip(bb)) error_exit("not gzip"); 4912ebbefb1a429022235c8db8b39e94ad01f03a8b6Rob Landley TT.outfd = 1; 492fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley 493fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley // Use last 1k of toybuf for little endian crc table 494fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley crc_init((unsigned *)(toybuf+sizeof(toybuf)-1024), 1); 495fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley TT.crcfunc = gzip_crc; 496fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley 4973cd89c3f640e8ad2cdb422d0504554c2636a8412Rob Landley inflate(bb); 498b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 499b34b237e6229344ce460e117eb442db9a32fe813Rob Landley // tail: crc32, len32 500b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 501fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley bitbuf_skip(bb, (8-bb->bitpos)&7); 502fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley if (~TT.crc != bitbuf_get(bb, 32) || TT.len != bitbuf_get(bb, 32)) 503fa1625d84e803df9a6a92551a106d42c62464e88Rob Landley error_exit("bad crc"); 504b34b237e6229344ce460e117eb442db9a32fe813Rob Landley free(bb); 505b34b237e6229344ce460e117eb442db9a32fe813Rob Landley} 506b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 507b34b237e6229344ce460e117eb442db9a32fe813Rob Landley// Parse many different kinds of command line argument: 508b34b237e6229344ce460e117eb442db9a32fe813Rob Landley 509b34b237e6229344ce460e117eb442db9a32fe813Rob Landleyvoid compress_main(void) 510b34b237e6229344ce460e117eb442db9a32fe813Rob Landley{ 5111ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley // todo: this 5121ba12b427e84c5c6578aa767a096f5859e7283ceRob Landley printf("hello world"); 513c5dabf136495a69e9226eaa8316332de57ad481eRob Landley} 514