/* gzip.c - deflate and inflate code rolled into a ball. * * Copyright 2009 Szabolcs Nagy * * See http://refspecs.linuxfoundation.org/LSB_4.1.0/LSB-Core-generic/LSB-Core-generic/gzip.html * And RFCs 1950, 1951, and 1952 USE_GZIP(NEWTOY(gzip, "qvcdrgzp[-qv][-cd][!rgpz]", TOYFLAG_USR|TOYFLAG_BIN)) config GZIP bool "gzip" default n help usage: gzip [-cdgpqrvz] [FILE] Transitional gzip, needs work. Combines gzip, zlib, and pkzip. -c compress (default) -d decompress -g gzip -p pkzip -q quiet (default) -r raw (default) -v verbose -z zlib */ #define FOR_gzip #include "toys.h" GLOBALS( // base offset and extra bits tables (length and distance) char lenbits[29], distbits[30]; unsigned short lenbase[29], distbase[30]; ) typedef unsigned char uchar; typedef unsigned short ushort; typedef unsigned int uint; /* deflate and inflate return values */ enum { FlateOk = 0, FlateErr = -1, FlateIn = -2, FlateOut = -3 }; enum { CodeBits = 16, /* max number of bits in a code + 1 */ LitlenTableBits = 9, /* litlen code bits used in lookup table */ DistTableBits = 6, /* dist code bits used in lookup table */ ClenTableBits = 6, /* clen code bits used in lookup table */ TableBits = LitlenTableBits, /* log2(lookup table size) */ Nlit = 256, /* number of lit codes */ Nlen = 29, /* number of len codes */ // sizeof(lenbits) Nlitlen = Nlit+Nlen+3, /* litlen codes + block end + 2 unused */ Ndist = 30, /* number of distance codes */ // sizeof(distbits) Nclen = 19, /* number of code length codes */ EOB = 256, /* end of block symbol */ MinMatch = 3, /* min match length */ MaxMatch = 258, /* max match length */ WinSize = 1 << 15, /* sliding window size */ MaxChainLen = 256, /* max length of hash chain */ HashBits = 13, HashSize = 1 << HashBits, /* hash table size */ BigDist = 1 << 12, /* max match distance for short match length */ MaxDist = WinSize, BlockSize = 1 << 15, /* TODO */ SrcSize = 2*WinSize + MaxMatch, DstSize = BlockSize + MaxMatch + 6, /* worst case compressed block size */ LzSize = 1 << 13, /* lz buffer size */ LzGuard = LzSize - 2, LzLitFlag = 1 << 15 /* marks literal run length in lz buffer */ }; /* states */ enum { BlockHead, UncompressedBlock, CopyUncompressed, FixedHuff, DynamicHuff, DynamicHuffClen, DynamicHuffLitlenDist, DynamicHuffContinue, DecodeBlock, DecodeBlockLenBits, DecodeBlockDist, DecodeBlockDistBits, DecodeBlockCopy }; typedef struct { int nin; int nout; uchar *in; uchar *out; char *err; void *state; } FlateStream; typedef struct { short len; /* code length */ ushort sym; /* symbol */ } Entry; /* huffman code tree */ typedef struct { Entry table[1 << TableBits]; /* prefix lookup table */ uint nbits; /* prefix length (table size is 1 << nbits) */ uint sum; /* full codes in table: sum(count[0..nbits]) */ ushort count[CodeBits]; /* number of codes with given length */ ushort symbol[Nlitlen]; /* symbols ordered by code length (lexic.) */ } Huff; typedef struct { uchar *src; /* input buffer pointer */ uchar *srcend; uint bits; uint nbits; uchar win[WinSize]; /* output window */ uint pos; /* window pos */ uint posout; /* used for flushing win */ int state; /* decode state */ int final; /* last block flag */ char *err; /* TODO: error message */ /* for decoding dynamic code trees in inflate() */ int nlit; int ndist; int nclen; /* also used in decode_block() */ int lenpos; /* also used in decode_block() */ uchar lens[Nlitlen + Ndist]; int fixed; /* fixed code tree flag */ Huff lhuff; /* dynamic lit/len huffman code tree */ Huff dhuff; /* dynamic distance huffman code tree */ } DecodeState; int deflate(FlateStream *s); int inflate(FlateStream *s); uint adler32(uchar *p, int n, uint adler); void crc32init(void); uint crc32(uchar *p, int n, uint crc); uint crctab[256]; void crc32init(void) { static const uint poly = 0xedb88320; int i,j; for (i = 0; i < 256; ++i) { uint crc = i; for (j = 0; j < 8; j++) { if (crc & 1) crc = (crc >> 1) ^ poly; else crc >>= 1; } crctab[i] = crc; } } uint crc32(uchar *p, int n, uint crc) { uchar *ep = p + n; crc ^= 0xffffffff; while (p < ep) crc = crctab[(crc & 0xff) ^ *p++] ^ (crc >> 8); return crc ^ 0xffffffff; } enum { AdlerBase = 65521, /* largest 16bit prime */ AdlerN = 5552 /* max iters before 32bit overflow */ }; uint adler32(uchar *p, int n, uint adler) { uint s1 = adler & 0xffff; uint s2 = (adler >> 16) & 0xffff; uchar *ep; int k; for (; n >= 16; n -= k) { k = n < AdlerN ? n : AdlerN; k &= ~0xf; for (ep = p + k; p < ep; p += 16) { s1 += p[0]; s2 += s1; s1 += p[1]; s2 += s1; s1 += p[2]; s2 += s1; s1 += p[3]; s2 += s1; s1 += p[4]; s2 += s1; s1 += p[5]; s2 += s1; s1 += p[6]; s2 += s1; s1 += p[7]; s2 += s1; s1 += p[8]; s2 += s1; s1 += p[9]; s2 += s1; s1 += p[10]; s2 += s1; s1 += p[11]; s2 += s1; s1 += p[12]; s2 += s1; s1 += p[13]; s2 += s1; s1 += p[14]; s2 += s1; s1 += p[15]; s2 += s1; } s1 %= AdlerBase; s2 %= AdlerBase; } if (n) { for (ep = p + n; p < ep; p++) { s1 += p[0]; s2 += s1; } s1 %= AdlerBase; s2 %= AdlerBase; } return (s2 << 16) + s1; } /* TODO: globals.. initialization is not thread safe */ static Huff lhuff; /* fixed lit/len huffman code tree */ static Huff dhuff; /* fixed distance huffman code tree */ /* ordering of code lengths */ static uchar clenorder[Nclen] = { 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 }; /* TODO: this or normal inc + reverse() */ /* increment bitwise reversed n (msb is bit 0, lsb is bit len-1) */ static uint revinc(uint n, uint len) { uint i = 1 << (len - 1); while (n & i) i >>= 1; if (i) { n &= i - 1; n |= i; } else n = 0; return n; } /* build huffman code tree from code lengths (each should be < CodeBits) */ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) { int offs[CodeBits]; int left; uint i, c, sum, code, len, min, max; ushort *count = huff->count; ushort *symbol = huff->symbol; Entry *table = huff->table; Entry entry; /* count code lengths */ for (i = 0; i < CodeBits; i++) count[i] = 0; for (i = 0; i < n; i++) count[lens[i]]++; if (count[0] == n) { huff->nbits = table[0].len = 0; return 0; } count[0] = 0; /* bound code lengths, force nbits to be within the bounds */ for (max = CodeBits - 1; max > 0; max--) if (count[max] != 0) break; if (nbits > max) nbits = max; for (min = 1; min < CodeBits; min++) if (count[min] != 0) break; if (nbits < min) { nbits = min; if (nbits > TableBits) return -1; } huff->nbits = nbits; /* check if length is over-subscribed or incomplete */ for (left = 1 << min, i = min; i <= max; left <<= 1, i++) { left -= count[i]; /* left < 0: over-subscribed, left > 0: incomplete */ if (left < 0) return -1; } for (sum = 0, i = 0; i <= max; i++) { offs[i] = sum; sum += count[i]; } /* needed for decoding codes longer than nbits */ if (nbits < max) huff->sum = offs[nbits + 1]; /* sort symbols by code length (lexicographic order) */ for (i = 0; i < n; i++) if (lens[i]) symbol[offs[lens[i]]++] = i; /* lookup table for decoding nbits from input.. */ for (i = 0; i < 1 << nbits; i++) table[i].len = table[i].sym = 0; code = 0; /* ..if code is at most nbits (bits are in reverse order, sigh..) */ for (len = min; len <= nbits; len++) for (c = count[len]; c > 0; c--) { entry.len = len; entry.sym = *symbol; for (i = code; i < 1 << nbits; i += 1 << len) table[i] = entry; /* next code */ symbol++; code = revinc(code, len); } /* ..if code is longer than nbits: values for simple bitwise decode */ for (i = 0; code; i++) { table[code].len = -1; table[code].sym = i << 1; code = revinc(code, nbits); } return 0; } /* fixed huffman code trees (should be done at compile time..) */ static void init_fixed_huffs(void) { int i; uchar lens[Nlitlen]; for (i = 0; i < 144; i++) lens[i] = 8; for (; i < 256; i++) lens[i] = 9; for (; i < 280; i++) lens[i] = 7; for (; i < Nlitlen; i++) lens[i] = 8; build_huff(&lhuff, lens, Nlitlen, 8); for (i = 0; i < Ndist; i++) lens[i] = 5; build_huff(&dhuff, lens, Ndist, 5); } /* fill *bits with n bits from *src */ static int fillbits_fast(uchar **src, uchar *srcend, uint *bits, uint *nbits, uint n) { while (*nbits < n) { if (*src == srcend) return 0; *bits |= *(*src)++ << *nbits; *nbits += 8; } return 1; } /* get n bits from *bits */ static uint getbits_fast(uint *bits, uint *nbits, int n) { uint k; k = *bits & ((1 << n) - 1); *bits >>= n; *nbits -= n; return k; } static int fillbits(DecodeState *s, uint n) { return fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, n); } static uint getbits(DecodeState *s, uint n) { return getbits_fast(&s->bits, &s->nbits, n); } /* decode symbol bitwise if code is longer than huffbits */ static uint decode_symbol_long(DecodeState *s, Huff *huff, uint bits, uint nbits, int cur) { int sum = huff->sum; uint huffbits = huff->nbits; ushort *count = huff->count + huffbits + 1; /* get bits if we are near the end */ if (s->src + 2 >= s->srcend) { while (nbits < CodeBits - 1 && s->src < s->srcend) { bits |= *s->src++ << nbits; nbits += 8; } s->bits = bits; s->nbits = nbits; } bits >>= huffbits; nbits -= huffbits; for (;;) { if (!nbits--) { if (s->src == s->srcend) return FlateIn; bits = *s->src++; nbits = 7; } cur |= bits & 1; bits >>= 1; sum += *count; cur -= *count; if (cur < 0) break; cur <<= 1; count++; if (count == huff->count + CodeBits) return s->err = "symbol decoding failed.", FlateErr; } s->bits = bits; s->nbits = nbits; return huff->symbol[sum + cur]; } /* decode a symbol from stream with huff code */ static uint decode_symbol(DecodeState *s, Huff *huff) { uint huffbits = huff->nbits; uint nbits = s->nbits; uint bits = s->bits; uint mask = (1 << huffbits) - 1; Entry entry; /* get enough bits efficiently */ if (nbits < huffbits) { uchar *src = s->src; if (src + 2 < s->srcend) { /* we assume huffbits <= 9 */ bits |= *src++ << nbits; nbits += 8; bits |= *src++ << nbits; nbits += 8; bits |= *src++ << nbits; nbits += 8; s->src = src; } else /* rare */ do { if (s->src == s->srcend) { entry = huff->table[bits & mask]; if (entry.len > 0 && entry.len <= nbits) { s->bits = bits >> entry.len; s->nbits = nbits - entry.len; return entry.sym; } s->bits = bits; s->nbits = nbits; return FlateIn; } bits |= *s->src++ << nbits; nbits += 8; } while (nbits < huffbits); } /* decode bits */ entry = huff->table[bits & mask]; if (entry.len > 0) { s->bits = bits >> entry.len; s->nbits = nbits - entry.len; return entry.sym; } else if (entry.len == 0) return s->err = "symbol decoding failed.", FlateErr; return decode_symbol_long(s, huff, bits, nbits, entry.sym); } /* decode a block of data from stream with trees */ static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff) { uchar *win = s->win; uint pos = s->pos; uint sym = s->nclen; uint len = s->lenpos; uint dist = s->nclen; switch (s->state) { case DecodeBlock: for (;;) { sym = decode_symbol(s, lhuff); if (sym < 256) { win[pos++] = sym; if (pos == WinSize) { s->pos = WinSize; s->state = DecodeBlock; return FlateOut; } } else if (sym > 256) { sym -= 257; if (sym >= Nlen) { s->pos = pos; s->state = DecodeBlock; if (sym + 257 == (uint)FlateIn) return FlateIn; return FlateErr; } case DecodeBlockLenBits: if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, TT.lenbits[sym])) { s->nclen = sym; /* using nclen to store sym */ s->pos = pos; s->state = DecodeBlockLenBits; return FlateIn; } len = TT.lenbase[sym] + getbits_fast(&s->bits, &s->nbits, TT.lenbits[sym]); case DecodeBlockDist: sym = decode_symbol(s, dhuff); if (sym == (uint)FlateIn) { s->pos = pos; s->lenpos = len; s->state = DecodeBlockDist; return FlateIn; } if (sym >= Ndist) return FlateErr; case DecodeBlockDistBits: if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, TT.distbits[sym])) { s->nclen = sym; /* using nclen to store sym */ s->pos = pos; s->lenpos = len; s->state = DecodeBlockDistBits; return FlateIn; } dist = TT.distbase[sym] + getbits_fast(&s->bits, &s->nbits, TT.distbits[sym]); /* copy match, loop unroll in common case */ if (pos + len < WinSize) { /* TT.lenbase[sym] >= 3 */ do { win[pos] = win[(pos - dist) % WinSize]; pos++; win[pos] = win[(pos - dist) % WinSize]; pos++; win[pos] = win[(pos - dist) % WinSize]; pos++; len -= 3; } while (len >= 3); if (len--) { win[pos] = win[(pos - dist) % WinSize]; pos++; if (len) { win[pos] = win[(pos - dist) % WinSize]; pos++; } } } else { /* rare */ case DecodeBlockCopy: while (len--) { win[pos] = win[(pos - dist) % WinSize]; pos++; if (pos == WinSize) { s->pos = WinSize; s->lenpos = len; s->nclen = dist; /* using nclen to store dist */ s->state = DecodeBlockCopy; return FlateOut; } } } } else { /* EOB: sym == 256 */ s->pos = pos; return FlateOk; } } /* for (;;) */ } /* switch () */ return s->err = "corrupted state.", FlateErr; } /* inflate state machine (decodes s->src into s->win) */ static int inflate_state(DecodeState *s) { int n; if (s->posout) return FlateOut; for (;;) { switch (s->state) { case BlockHead: if (s->final) { if (s->pos) return FlateOut; else return FlateOk; } if (!fillbits(s, 3)) return FlateIn; s->final = getbits(s, 1); n = getbits(s, 2); if (n == 0) s->state = UncompressedBlock; else if (n == 1) s->state = FixedHuff; else if (n == 2) s->state = DynamicHuff; else return s->err = "corrupt block header.", FlateErr; break; case UncompressedBlock: /* start block on a byte boundary */ s->bits >>= s->nbits & 7; s->nbits &= ~7; if (!fillbits(s, 32)) return FlateIn; s->lenpos = getbits(s, 16); n = getbits(s, 16); if (s->lenpos != (~n & 0xffff)) return s->err = "corrupt uncompressed length.", FlateErr; s->state = CopyUncompressed; case CopyUncompressed: /* TODO: untested, slow, memcpy etc */ /* s->nbits should be 0 here */ while (s->lenpos) { if (s->src == s->srcend) return FlateIn; s->lenpos--; s->win[s->pos++] = *s->src++; if (s->pos == WinSize) return FlateOut; } s->state = BlockHead; break; case FixedHuff: s->fixed = 1; s->state = DecodeBlock; break; case DynamicHuff: /* decode dynamic huffman code trees */ if (!fillbits(s, 14)) return FlateIn; s->nlit = 257 + getbits(s, 5); s->ndist = 1 + getbits(s, 5); s->nclen = 4 + getbits(s, 4); if (s->nlit > Nlitlen || s->ndist > Ndist) return s->err = "corrupt code tree.", FlateErr; /* build code length tree */ for (n = 0; n < Nclen; n++) s->lens[n] = 0; s->fixed = 0; s->state = DynamicHuffClen; s->lenpos = 0; case DynamicHuffClen: for (n = s->lenpos; n < s->nclen; n++) if (fillbits(s, 3)) s->lens[clenorder[n]] = getbits(s, 3); else { s->lenpos = n; return FlateIn; } /* using lhuff for code length huff code */ if (build_huff(&s->lhuff, s->lens, Nclen, ClenTableBits) < 0) return s->err = "building clen tree failed.", FlateErr; s->state = DynamicHuffLitlenDist; s->lenpos = 0; case DynamicHuffLitlenDist: /* decode code lengths for the dynamic trees */ for (n = s->lenpos; n < s->nlit + s->ndist; ) { uint sym = decode_symbol(s, &s->lhuff); uint len; uchar c; if (sym < 16) { s->lens[n++] = sym; continue; } else if (sym == (uint)FlateIn) { s->lenpos = n; return FlateIn; case DynamicHuffContinue: n = s->lenpos; sym = s->nclen; s->state = DynamicHuffLitlenDist; } if (!fillbits(s, 7)) { /* TODO: 7 is too much when an almost empty block is at the end */ if (sym == (uint)FlateErr) return FlateErr; s->nclen = sym; s->lenpos = n; s->state = DynamicHuffContinue; return FlateIn; } /* TODO: bound check s->lens */ if (sym == 16) { /* copy previous code length 3-6 times */ c = s->lens[n - 1]; for (len = 3 + getbits(s, 2); len; len--) s->lens[n++] = c; } else if (sym == 17) { /* repeat 0 for 3-10 times */ for (len = 3 + getbits(s, 3); len; len--) s->lens[n++] = 0; } else if (sym == 18) { /* repeat 0 for 11-138 times */ for (len = 11 + getbits(s, 7); len; len--) s->lens[n++] = 0; } else return s->err = "corrupt code tree.", FlateErr; } /* build dynamic huffman code trees */ if (build_huff(&s->lhuff, s->lens, s->nlit, LitlenTableBits) < 0) return s->err = "building litlen tree failed.", FlateErr; if (build_huff(&s->dhuff, s->lens + s->nlit, s->ndist, DistTableBits) < 0) return s->err = "building dist tree failed.", FlateErr; s->state = DecodeBlock; case DecodeBlock: case DecodeBlockLenBits: case DecodeBlockDist: case DecodeBlockDistBits: case DecodeBlockCopy: n = decode_block(s, s->fixed ? &lhuff : &s->lhuff, s->fixed ? &dhuff : &s->dhuff); if (n != FlateOk) return n; s->state = BlockHead; break; default: return s->err = "corrupt internal state.", FlateErr; } } } static DecodeState *alloc_decode_state(void) { DecodeState *s = malloc(sizeof(DecodeState)); if (s) { s->final = s->pos = s->posout = s->bits = s->nbits = 0; s->state = BlockHead; s->src = s->srcend = 0; s->err = 0; /* TODO: globals.. */ if (lhuff.nbits == 0) init_fixed_huffs(); } return s; } /* extern */ int inflate(FlateStream *stream) { DecodeState *s = stream->state; int n; if (stream->err) { if (s) { free(s); stream->state = 0; } return FlateErr; } if (!s) { s = stream->state = alloc_decode_state(); if (!s) return stream->err = "no mem.", FlateErr; } if (stream->nin) { s->src = stream->in; s->srcend = s->src + stream->nin; stream->nin = 0; } n = inflate_state(s); if (n == FlateOut) { if (s->pos < stream->nout) stream->nout = s->pos; memcpy(stream->out, s->win + s->posout, stream->nout); s->pos -= stream->nout; if (s->pos) s->posout += stream->nout; else s->posout = 0; } if (n == FlateOk || n == FlateErr) { if (s->nbits || s->src < s->srcend) { s->nbits /= 8; stream->in = s->src - s->nbits; stream->nin = s->srcend - s->src + s->nbits; } stream->err = s->err; free(s); stream->state = 0; } return n; } typedef struct { ushort dist; ushort len; } Match; typedef struct { ushort n; ushort bits; } LzCode; typedef struct { int pos; /* position in input src */ int startpos; /* block start pos in input src */ int endpos; /* end of available bytes in src */ int skip; /* skipped hash chain updates (until next iter) */ Match prevm; /* previous (deferred) match */ int state; /* prev return value */ int eof; /* end of input */ uchar *in; /* input data (not yet in src) */ uchar *inend; uint bits; /* for output */ int nbits; /* for output */ uchar *dst; /* compressed output (position in dstbuf) */ uchar *dstbegin; /* start position of unflushed data in dstbuf */ LzCode *lz; /* current pos in lzbuf */ int nlit; /* literal run length in lzbuf */ ushort head[HashSize]; /* position of hash chain heads */ ushort chain[WinSize]; /* hash chain */ ushort lfreq[Nlitlen]; ushort dfreq[Ndist]; uchar src[SrcSize]; /* input buf */ uchar dstbuf[DstSize]; LzCode lzbuf[LzSize]; /* literal run length, match len, match dist */ } State; static uchar fixllen[Nlitlen]; /* fixed lit/len huffman code tree */ static ushort fixlcode[Nlitlen]; static uchar fixdlen[Ndist]; /* fixed distance huffman code tree */ static ushort fixdcode[Ndist]; static uint revcode(uint c, int n) { int i; uint r = 0; for (i = 0; i < n; i++) { r = (r << 1) | (c & 1); c >>= 1; } return r; } /* build huffman code tree from code lengths */ static void huffcodes(ushort *codes, const uchar *lens, int n) { int c[CodeBits]; int i, code, count; /* count code lengths and calc first code for each length */ for (i = 0; i < CodeBits; i++) c[i] = 0; for (i = 0; i < n; i++) c[lens[i]]++; for (code = 0, i = 1; i < CodeBits; i++) { count = c[i]; c[i] = code; code += count; if (code > (1 << i)) abort(); /* over-subscribed */ code <<= 1; } if (code < (1 << i)) /* incomplete */; for (i = 0; i < n; i++) if (lens[i]) codes[i] = revcode(c[lens[i]]++, lens[i]); else codes[i] = 0; } static int heapparent(int n) {return (n - 2)/4 * 2;} static int heapchild(int n) {return 2 * n + 2;} static int heappush(int *heap, int len, int w, int n) { int p, c, tmp; c = len; heap[len++] = n; heap[len++] = w; while (c > 0) { p = heapparent(c); if (heap[c+1] < heap[p+1]) { tmp = heap[c]; heap[c] = heap[p]; heap[p] = tmp; tmp = heap[c+1]; heap[c+1] = heap[p+1]; heap[p+1] = tmp; c = p; } else break; } return len; } static int heappop(int *heap, int len, int *w, int *n) { int p, c, tmp; *n = heap[0]; *w = heap[1]; heap[1] = heap[--len]; heap[0] = heap[--len]; p = 0; for (;;) { c = heapchild(p); if (c >= len) break; if (c+2 < len && heap[c+3] < heap[c+1]) c += 2; if (heap[p+1] > heap[c+1]) { tmp = heap[p]; heap[p] = heap[c]; heap[c] = tmp; tmp = heap[p+1]; heap[p+1] = heap[c+1]; heap[c+1] = tmp; } else break; p = c; } return len; } /* symbol frequencies -> code lengths (limited to 255) */ static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) { /* 2 <= nsym <= Nlitlen, log(nsym) <= limit <= CodeBits-1 */ int parent[2*Nlitlen-1]; int count[CodeBits]; int heap[2*Nlitlen]; int n, len, top, overflow; int i, j; int wi, wj; for (n = 0; n < limit+1; n++) count[n] = 0; for (len = n = 0; n < nsym; n++) if (freqs[n] > 0) len = heappush(heap, len, freqs[n], n); else lens[n] = 0; /* deflate: fewer than two symbols: add new */ for (n = 0; len < 4; n++) if (freqs[n] == 0) len = heappush(heap, len, ++freqs[n], n); /* build code tree */ top = len; for (n = nsym; len > 2; n++) { len = heappop(heap, len, &wi, &i); len = heappop(heap, len, &wj, &j); parent[i] = n; parent[j] = n; len = heappush(heap, len, wi + wj, n); /* keep an ordered list of nodes at the end */ heap[len+1] = i; heap[len] = j; } /* calc code lengths (deflate: with limit) */ overflow = 0; parent[--n] = 0; for (i = 2; i < top; i++) { n = heap[i]; if (n >= nsym) { /* overwrite parent index with length */ parent[n] = parent[parent[n]] + 1; if (parent[n] > limit) overflow++; } else { lens[n] = parent[parent[n]] + 1; if (lens[n] > limit) { lens[n] = limit; overflow++; } count[lens[n]]++; } } if (overflow == 0) return; /* modify code tree to fix overflow (from zlib) */ while (overflow > 0) { for (n = limit-1; count[n] == 0; n--); count[n]--; count[n+1] += 2; count[limit]--; overflow -= 2; } for (len = limit; len > 0; len--) for (i = count[len]; i > 0;) { n = heap[--top]; if (n < nsym) { lens[n] = len; i--; } } } /* output n (<= 16) bits */ static void putbits(State *s, uint bits, int n) { s->bits |= bits << s->nbits; s->nbits += n; while (s->nbits >= 8) { *s->dst++ = s->bits & 0xff; s->bits >>= 8; s->nbits -= 8; } } /* run length encode literal and dist code lengths into codes and extra */ static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit, uchar *dlen, int ndist) { int i, c, r, rr; int n = 0; for (i = 0; i < nlit; i++) codes[i] = llen[i]; for (i = 0; i < ndist; i++) codes[nlit + i] = dlen[i]; for (i = 0; i < nlit + ndist;) { c = codes[i]; for (r = 1; i + r < nlit + ndist && codes[i + r] == c; r++); i += r; if (c == 0) { while (r >= 11) { rr = r > 138 ? 138 : r; codes[n] = 18; extra[n++] = rr - 11; r -= rr; } if (r >= 3) { codes[n] = 17; extra[n++] = r - 3; r = 0; } } while (r--) { codes[n++] = c; while (r >= 3) { rr = r > 6 ? 6 : r; codes[n] = 16; extra[n++] = rr - 3; r -= rr; } } } return n; } /* compress block data into s->dstbuf using given codes */ static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar *dlen) { int n; LzCode *lz; uchar *p; for (lz = s->lzbuf, p = s->src + s->startpos; lz != s->lz; lz++) { if (lz->bits & LzLitFlag) { for (n = lz->n; n > 0; n--, p++) putbits(s, lcode[*p], llen[*p]); } else { p += TT.lenbase[lz->n] + lz->bits; putbits(s, lcode[Nlit + lz->n + 1], llen[Nlit + lz->n + 1]); putbits(s, lz->bits, TT.lenbits[lz->n]); lz++; putbits(s, dcode[lz->n], dlen[lz->n]); putbits(s, lz->bits, TT.distbits[lz->n]); } } putbits(s, lcode[EOB], llen[EOB]); } /* build code trees and select dynamic/fixed/uncompressed block compression */ static void deflate_block(State *s) { uchar codes[Nlitlen + Ndist], extra[Nlitlen + Ndist]; uchar llen[Nlitlen], dlen[Ndist], clen[Nclen]; ushort cfreq[Nclen]; /* freq can be overwritten by code */ ushort *lcode = s->lfreq, *dcode = s->dfreq, *ccode = cfreq; int i, c, n, ncodes; int nlit, ndist, nclen; LzCode *lz; uchar *p; int dynsize, fixsize, uncsize; int blocklen = s->pos - s->startpos; /* int dyntree; */ /* calc dynamic codes */ hufflens(llen, s->lfreq, Nlitlen, CodeBits-1); hufflens(dlen, s->dfreq, Ndist, CodeBits-1); huffcodes(lcode, llen, Nlitlen); huffcodes(dcode, dlen, Ndist); for (nlit = Nlitlen; nlit > Nlit && llen[nlit-1] == 0; nlit--); for (ndist = Ndist; ndist > 1 && dlen[ndist-1] == 0; ndist--); ncodes = clencodes(codes, extra, llen, nlit, dlen, ndist); memset(cfreq, 0, sizeof(cfreq)); for (i = 0; i < ncodes; i++) cfreq[codes[i]]++; hufflens(clen, cfreq, Nclen, 7); huffcodes(ccode, clen, Nclen); for (nclen = Nclen; nclen > 4 && clen[clenorder[nclen-1]] == 0; nclen--); /* calc compressed size */ uncsize = 3 + 16 + 8 * blocklen + (16 - 3 - s->nbits) % 8; /* byte aligned */ fixsize = 3; dynsize = 3 + 5 + 5 + 4 + 3 * nclen; for (i = 0; i < ncodes; i++) { c = codes[i]; dynsize += clen[c]; if (c == 16) dynsize += 2; if (c == 17) dynsize += 3; if (c == 18) dynsize += 7; } /* dyntree = dynsize - 3; */ for (lz = s->lzbuf, p = s->src + s->startpos; lz != s->lz; lz++) { if (lz->bits & LzLitFlag) { for (n = lz->n; n > 0; n--, p++) { fixsize += fixllen[*p]; dynsize += llen[*p]; } } else { p += TT.lenbase[lz->n] + lz->bits; fixsize += fixllen[Nlit + lz->n + 1]; dynsize += llen[Nlit + lz->n + 1]; fixsize += TT.lenbits[lz->n]; dynsize += TT.lenbits[lz->n]; lz++; fixsize += fixdlen[lz->n]; dynsize += dlen[lz->n]; fixsize += TT.distbits[lz->n]; dynsize += TT.distbits[lz->n]; } } fixsize += fixllen[EOB]; dynsize += llen[EOB]; /* emit block */ putbits(s, s->eof && s->pos == s->endpos, 1); if (dynsize < fixsize && dynsize < uncsize) { /* dynamic code */ putbits(s, 2, 2); putbits(s, nlit - 257, 5); putbits(s, ndist - 1, 5); putbits(s, nclen - 4, 4); for (i = 0; i < nclen; i++) putbits(s, clen[clenorder[i]], 3); for (i = 0; i < ncodes; i++) { c = codes[i]; putbits(s, ccode[c], clen[c]); if (c == 16) putbits(s, extra[i], 2); if (c == 17) putbits(s, extra[i], 3); if (c == 18) putbits(s, extra[i], 7); } putblock(s, lcode, llen, dcode, dlen); } else if (fixsize < uncsize) { /* fixed code */ putbits(s, 1, 2); putblock(s, fixlcode, fixllen, fixdcode, fixdlen); } else { /* uncompressed */ putbits(s, 0, 2); putbits(s, 0, 7); /* align to byte boundary */ s->nbits = 0; putbits(s, blocklen, 16); putbits(s, ~blocklen & 0xffff, 16); memcpy(s->dst, s->src + s->startpos, blocklen); s->dst += blocklen; } /* fprintf(stderr, "blen:%d [%d,%d] lzlen:%d dynlen:%d (tree:%d rate:%.3f) fixlen:%d (rate:%.3f) unclen:%d (rate:%.3f)\n", blocklen, s->startpos, s->pos, s->lz - s->lzbuf, dynsize, dyntree, dynsize/(float)blocklen, fixsize, fixsize/(float)blocklen, uncsize, uncsize/(float)blocklen); */ } /* find n in base */ static int bisect(ushort *base, int len, int n) { int lo = 0; int hi = len; int k; while (lo < hi) { k = (lo + hi) / 2; if (n < base[k]) hi = k; else lo = k + 1; } return lo - 1; } /* add literal run length to lzbuf */ static void flushlit(State *s) { if (s->nlit) { s->lz->bits = LzLitFlag; s->lz->n = s->nlit; s->lz++; s->nlit = 0; } } /* add match to lzbuf and update freq counts */ static void recordmatch(State *s, Match m) { int n; /*fprintf(stderr, "m %d %d\n", m.len, m.dist);*/ flushlit(s); n = bisect(TT.lenbase, Nlen, m.len); s->lz->n = n; s->lz->bits = m.len - TT.lenbase[n]; s->lz++; s->lfreq[Nlit + n + 1]++; n = bisect(TT.distbase, Ndist, m.dist); s->lz->n = n; s->lz->bits = m.dist - TT.distbase[n]; s->lz++; s->dfreq[n]++; } /* update literal run length */ static void recordlit(State *s, int c) { /*fprintf(stderr, "l %c\n", c);*/ s->nlit++; s->lfreq[c]++; } /* multiplicative hash (using a prime close to golden ratio * 2^32) */ static int gethash(uchar *p) { return (0x9e3779b1 * ((p[0]<<16) + (p[1]<<8) + p[2]) >> (32 - HashBits)) % HashSize; } /* update hash chain at the current position */ static int updatechain(State *s) { int hash, next = 0, p = s->pos, i; if (s->endpos - p < MinMatch) p = s->endpos - MinMatch; for (i = s->pos - s->skip; i <= p; i++) { hash = gethash(s->src + i); next = s->head[hash]; s->head[hash] = i; if (next >= i || i - next >= MaxDist) next = 0; s->chain[i % WinSize] = next; } s->skip = 0; return next; } /* find longest match, next position in the hash chain is given */ static Match getmatch(State *s, int next) { Match m = {0, MinMatch-1}; int len; int limit = s->pos - MaxDist; int chainlen = MaxChainLen; uchar *q; uchar *p = s->src + s->pos; uchar *end = p + MaxMatch; do { q = s->src + next; /*fprintf(stderr,"match: next:%d pos:%d limit:%d\n", next, s->pos, limit);*/ /* next match should be at least m.len+1 long */ if (q[m.len] != p[m.len] || q[m.len-1] != p[m.len-1] || q[0] != p[0]) continue; while (++p != end && *++q == *p); len = MaxMatch - (end - p); p -= len; /*fprintf(stderr,"match: len:%d dist:%d\n", len, s->pos - next);*/ if (len > m.len) { m.dist = s->pos - next; m.len = len; if (s->pos + len >= s->endpos) { /* TODO: overflow */ m.len = s->endpos - s->pos; return m; } if (len == MaxMatch) return m; } } while ((next = s->chain[next % WinSize]) > limit && --chainlen); if (m.len < MinMatch || (m.len == MinMatch && m.dist > BigDist)) m.len = 0; return m; } static void startblock(State *s) { s->startpos = s->pos; s->dst = s->dstbegin = s->dstbuf; s->lz = s->lzbuf; s->nlit = 0; memset(s->lfreq, 0, sizeof(s->lfreq)); memset(s->dfreq, 0, sizeof(s->dfreq)); s->lfreq[EOB]++; } static int shiftwin(State *s) { int n; if (s->startpos < WinSize) return 0; memmove(s->src, s->src + WinSize, SrcSize - WinSize); for (n = 0; n < HashSize; n++) s->head[n] = s->head[n] > WinSize ? s->head[n] - WinSize : 0; for (n = 0; n < WinSize; n++) s->chain[n] = s->chain[n] > WinSize ? s->chain[n] - WinSize : 0; s->pos -= WinSize; s->startpos -= WinSize; s->endpos -= WinSize; return 1; } static int endblock(State *s) { if ((s->pos >= 2*WinSize && !shiftwin(s)) || s->pos - s->startpos >= BlockSize || s->lz - s->lzbuf >= LzGuard || (s->eof && s->pos == s->endpos)) { /* deflate block */ flushlit(s); if (s->prevm.len) s->pos--; deflate_block(s); if (s->eof && s->pos == s->endpos) putbits(s, 0, 7); return 1; } return 0; } static int fillsrc(State *s) { int n, k; if (s->endpos < SrcSize && !s->eof) { n = SrcSize - s->endpos; k = s->inend - s->in; if (n > k) n = k; memcpy(s->src + s->endpos, s->in, n); s->in += n; s->endpos += n; if (s->endpos < SrcSize) return 0; } return 1; } static int calcguard(State *s) { int p = s->endpos - MaxMatch; int q = s->startpos + BlockSize; return p < q ? p : q; } /* deflate compress from s->src into s->dstbuf */ static int deflate_state(State *s) { Match m; int next; int guard; if (s->state == FlateIn) s->eof = s->in == s->inend; else if (s->state == FlateOut) { if (s->dstbegin < s->dst) return (s->state = FlateOut); if (s->eof && s->pos == s->endpos) return (s->state = FlateOk); startblock(s); if (s->prevm.len) s->pos++; } else return s->state; guard = calcguard(s); for (;;) { if (s->pos >= guard || s->lz - s->lzbuf >= LzGuard) { /*fprintf(stderr,"guard:%d pos:%d len:%d lzlen:%d end:%d start:%d nin:%d eof:%d\n", guard, s->pos, s->pos - s->startpos, s->lz - s->lzbuf, s->endpos, s->startpos, s->inend - s->in, s->eof);*/ if (endblock(s)) return (s->state = FlateOut); if (!fillsrc(s)) return (s->state = FlateIn); guard = calcguard(s); } next = updatechain(s); if (next) m = getmatch(s, next); if (next && m.len > s->prevm.len) { if (s->prevm.len) recordlit(s, s->src[s->pos-1]); s->prevm = m; } else if (s->prevm.len) { recordmatch(s, s->prevm); s->skip = s->prevm.len - 2; s->prevm.len = 0; s->pos += s->skip; } else recordlit(s, s->src[s->pos]); s->pos++; } } /* alloc and init state */ static State *alloc_state(void) { State *s = malloc(sizeof(State)); int i; if (!s) return s; memset(s->chain, 0, sizeof(s->chain)); memset(s->head, 0, sizeof(s->head)); s->bits = s->nbits = 0; /* TODO: globals */ if (fixllen[0] == 0) { for (i = 0; i < 144; i++) fixllen[i] = 8; for (; i < 256; i++) fixllen[i] = 9; for (; i < 280; i++) fixllen[i] = 7; for (; i < Nlitlen; i++) fixllen[i] = 8; for (i = 0; i < Ndist; i++) fixdlen[i] = 5; huffcodes(fixlcode, fixllen, Nlitlen); huffcodes(fixdcode, fixdlen, Ndist); } s->state = FlateOut; s->in = s->inend = 0; s->dst = s->dstbegin = s->dstbuf; s->pos = s->startpos = s->endpos = WinSize; s->eof = 0; s->skip = 0; s->prevm.len = 0; return s; } /* extern */ int deflate(FlateStream *stream) { State *s = stream->state; int n, k; if (stream->err) { free(s); stream->state = 0; return FlateErr; } if (!s) { s = stream->state = alloc_state(); if (!s) return stream->err = "no mem.", FlateErr; } if (stream->nin) { s->in = stream->in; s->inend = s->in + stream->nin; stream->nin = 0; } n = deflate_state(s); if (n == FlateOut) { k = s->dst - s->dstbegin; if (k < stream->nout) stream->nout = k; memcpy(stream->out, s->dstbegin, stream->nout); s->dstbegin += stream->nout; } if (n == FlateOk || n == FlateErr) { free(s); stream->state = 0; } return n; } static void set32(uchar *p, uint n) { p[0] = n >> 24; p[1] = n >> 16; p[2] = n >> 8; p[3] = n; } static void set32le(uchar *p, uint n) { p[0] = n; p[1] = n >> 8; p[2] = n >> 16; p[3] = n >> 24; } static int check32(uchar *p, uint n) { return n == ((p[0] << 24) | (p[1] << 16) | (p[2] << 8) | p[3]); } static int check32le(uchar *p, uint n) { return n == (p[0] | (p[1] << 8) | (p[2] << 16) | (p[3] << 24)); } enum { ZlibCM = 7 << 4, ZlibCINFO = 8, ZlibFLEV = 3 << 6, ZlibFDICT = 1 << 5, ZlibFCHK = 31 - (((ZlibCM | ZlibCINFO) << 8) | ZlibFLEV) % 31 }; int deflate_zlib_header(uchar *p, int n) { if (n < 2) return FlateErr; p[0] = ZlibCM | ZlibCINFO; /* deflate method, 32K window size */ p[1] = ZlibFLEV | ZlibFCHK; /* highest compression */ return 2; } int deflate_zlib_footer(uchar *p, int n, uint sum, uint len, uint zlen) { if (n < 4) return FlateErr; set32(p, sum); return 4; } int inflate_zlib_header(uchar *p, int n) { if (n < 2) return FlateErr; if (((p[0] << 8) | p[1]) % 31) return FlateErr; if ((p[0] & 0xf0) != ZlibCM || (p[0] & 0x0f) > ZlibCINFO) return FlateErr; if (p[1] & ZlibFDICT) return FlateErr; return 2; } int inflate_zlib_footer(uchar *p, int n, uint sum, uint len, uint zlen) { if (n < 4 || !check32(p, sum)) return FlateErr; return 4; } enum { GZipID1 = 0x1f, GZipID2 = 0x8b, GZipCM = 8, GZipFHCRC = 1 << 1, GZipFEXTRA = 1 << 2, GZipFNAME = 1 << 3, GZipFCOMM = 1 << 4, GZipXFL = 2, GZipOS = 255 }; int deflate_gzip_header(uchar *p, int n) { if (n < 10) return FlateErr; memset(p, 0, 10); p[0] = GZipID1; p[1] = GZipID2; p[2] = GZipCM; p[8] = GZipXFL; p[9] = GZipOS; return 10; } int deflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { if (n < 8) return FlateErr; set32le(p, sum); set32le(p+4, len); return 8; } int inflate_gzip_header(uchar *p, int n) { int k = 10; if (k > n) return FlateErr; if (p[0] != GZipID1 || p[1] != GZipID2 || p[2] != GZipCM) return FlateErr; if (p[3] & GZipFEXTRA) { k += 2 + ((p[k] << 8) | p[k+1]); if (k > n) return FlateErr; } if (p[3] & GZipFNAME) { for (; k < n; k++) if (p[k] == 0) break; k++; if (k > n) return FlateErr; } if (p[3] & GZipFCOMM) { for (; k < n; k++) if (p[k] == 0) break; k++; if (k > n) return FlateErr; } if (p[3] & GZipFHCRC) { k += 2; if (k > n) return FlateErr; } return k; } int inflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { if (n < 8 || !check32le(p, sum) || !check32le(p+4, len)) return FlateErr; return 8; } static char pkname[] = "sflate_stream"; enum { PKHeadID = 0x04034b50, PKDataID = 0x08074b50, PKDirID = 0x02014b50, PKFootID = 0x06054b50, PKVersion = 20, PKFlag = 1 << 3, PKMethod = 8, PKDate = ((2009 - 1980) << 25) | (1 << 21) | (1 << 16), PKHeadSize = 30, PKDirSize = 46, PKNameLen = sizeof(pkname) - 1 }; int deflate_pkzip_header(uchar *p, int n) { if (n < PKHeadSize + PKNameLen) return FlateErr; memset(p, 0, PKHeadSize); set32le(p, PKHeadID); set32le(p+4, PKVersion); set32le(p+6, PKFlag); set32le(p+8, PKMethod); set32le(p+10, PKDate); set32le(p+26, PKNameLen); memcpy(p + PKHeadSize, pkname, PKNameLen); return PKHeadSize + PKNameLen; } int deflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { if (n < PKDirSize + PKNameLen + 22) return FlateErr; /* unzip bug */ /* if (n < 16 + PKDirSize + PKNameLen + 22) return FlateErr; set32le(p, PKDataID); set32le(p+4, sum); set32le(p+8, zlen); set32le(p+12, len); p += 16; */ memset(p, 0, PKDirSize); set32le(p, PKDirID); set32le(p+4, PKVersion | (PKVersion << 16)); set32le(p+8, PKFlag); set32le(p+10, PKMethod); set32le(p+12, PKDate); set32le(p+16, sum); set32le(p+20, zlen); set32le(p+24, len); set32le(p+28, PKNameLen); memcpy(p + PKDirSize, pkname, PKNameLen); p += PKDirSize + PKNameLen; memset(p, 0, 22); set32le(p, PKFootID); p[8] = p[10] = 1; set32le(p+12, PKDirSize + PKNameLen); set32le(p+16, zlen + PKHeadSize + PKNameLen); return PKDirSize + PKNameLen + 22; /* set32le(p+12, 16 + PKDirSize + PKNameLen); set32le(p+16, zlen + PKHeadSize + PKNameLen); return 16 + PKDirSize + PKNameLen + 22; */ } int inflate_pkzip_header(uchar *p, int n) { int k = 30; if (k > n) return FlateErr; if (!check32le(p, PKHeadID)) return FlateErr; if ((p[4] | (p[5] << 8)) > PKVersion) return FlateErr; if ((p[8] | (p[9] << 8)) != PKMethod) return FlateErr; k += p[26] | (p[27] << 8); k += p[28] | (p[29] << 8); if (k > n) return FlateErr; return k; } int inflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { int k = PKDirSize + 22; if (k > n) return FlateErr; if (check32le(p, PKDataID)) { p += 16; k += 16; if (k > n) return FlateErr; } if (!check32le(p, PKDirID)) return FlateErr; if (!check32le(p+16, sum)) return FlateErr; if (!check32le(p+20, zlen)) return FlateErr; if (!check32le(p+24, len)) return FlateErr; return k; } /* example usage */ static int (*header)(uchar *, int); static int (*footer)(uchar *, int, uint, uint, uint); static uint (*checksum)(uchar *, int, uint); static char *err; static uint sum; static uint nin; static uint nout; static uint headerlen; static uint footerlen; static uint extralen; static int dummyheader(uchar *p, int n) { return 0; } static int dummyfooter(uchar *p, int n, uint sum, uint len, uint zlen) { return 0; } static uint dummysum(uchar *p, int n, uint sum) { return 0; } /* compress, using FlateStream interface */ int compress_stream(FILE *in, FILE *out) { FlateStream s; int k, n; enum {Nin = 1<<15, Nout = 1<<15}; s.in = malloc(Nin); s.out = malloc(Nout); s.nin = 0; s.nout = Nout; s.err = 0; s.state = 0; k = header(s.out, s.nout); if (k == FlateErr) { s.err = "header error."; n = FlateErr; } else { headerlen = s.nout = k; n = FlateOut; } for (;; n = deflate(&s)) switch (n) { case FlateOk: k = footer(s.out, s.nout, sum, nin, nout - headerlen); if (k == FlateErr) { s.err = "footer error."; n = FlateErr; } else if (k != fwrite(s.out, 1, k, out)) { s.err = "write error."; n = FlateErr; } else { footerlen = k; nout += k; } case FlateErr: free(s.in); free(s.out); err = s.err; return n; case FlateIn: s.nin = fread(s.in, 1, Nin, in); nin += s.nin; sum = checksum(s.in, s.nin, sum); break; case FlateOut: k = fwrite(s.out, 1, s.nout, out); if (k != s.nout) s.err = "write error."; nout += k; s.nout = Nout; break; } } /* decompress, using FlateStream interface */ int decompress_stream(FILE *in, FILE *out) { FlateStream s; uchar *begin; int k, n; enum {Nin = 1<<15, Nout = 1<<15}; s.in = begin = malloc(Nin); s.out = malloc(Nout); s.nout = Nout; s.err = 0; s.state = 0; s.nin = fread(s.in, 1, Nin, in); nin += s.nin; k = header(s.in, s.nin); if (k == FlateErr) { s.err = "header error."; n = FlateErr; } else { headerlen = k; s.nin -= k; s.in += k; n = inflate(&s); } for (;; n = inflate(&s)) switch (n) { case FlateOk: memmove(begin, s.in, s.nin); k = fread(begin, 1, Nin-s.nin, in); nin += k; s.nin += k; k = footer(begin, s.nin, sum, nout, nin - s.nin - headerlen); if (k == FlateErr) { s.err = "footer error."; n = FlateErr; } else { footerlen = k; extralen = s.nin - k; } case FlateErr: free(begin); free(s.out); err = s.err; return n; case FlateIn: s.in = begin; s.nin = fread(s.in, 1, Nin, in); nin += s.nin; break; case FlateOut: k = fwrite(s.out, 1, s.nout, out); if (k != s.nout) s.err = "write error."; sum = checksum(s.out, k, sum); nout += k; s.nout = Nout; break; } } void gzip_main(void) { int (*call)(FILE *, FILE*); int n = 1, i; // Calculate lenbits, lenbase, distbits, distbase *TT.lenbase = 3; for (i = 0; i4) { 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; i3 && !(i&1)) n++; TT.distbits[i] = n; } call = (toys.optflags & FLAG_c) ? compress_stream : decompress_stream; if (toys.optflags & FLAG_r) { header = dummyheader; footer = dummyfooter; checksum = dummysum; } else if (toys.optflags & FLAG_z) { if (toys.optflags & FLAG_c) { header = deflate_zlib_header; footer = deflate_zlib_footer; } else { header = inflate_zlib_header; footer = inflate_zlib_footer; } checksum = adler32; } else { checksum = crc32; crc32init(); if (toys.optflags & FLAG_p) { if (toys.optflags & FLAG_c) { header = deflate_pkzip_header; footer = deflate_pkzip_footer; } else { header = inflate_pkzip_header; footer = inflate_pkzip_footer; } } else { if (toys.optflags & FLAG_c) { header = deflate_gzip_header; footer = deflate_gzip_footer; } else { header = inflate_gzip_header; footer = inflate_gzip_footer; } } } toys.exitval = call(stdin, stdout); if (toys.optflags & FLAG_v) fprintf(stderr, "in:%d out:%d checksum: 0x%08x (header:%d data:%d footer:%d extra input:%s)\n", nin, nout, sum, headerlen, ((toys.optflags & FLAG_c) ? nout : nin) - headerlen - footerlen - extralen, footerlen, extralen ? "yes" : "no"); if (toys.exitval) fprintf(stderr, "error: %s\n", err); }