diff options
Diffstat (limited to 'toys/pending')
| -rw-r--r-- | toys/pending/gzip.c | 1878 |
1 files changed, 0 insertions, 1878 deletions
diff --git a/toys/pending/gzip.c b/toys/pending/gzip.c deleted file mode 100644 index 87fc2fda..00000000 --- a/toys/pending/gzip.c +++ /dev/null @@ -1,1878 +0,0 @@ -/* gzip.c - deflate and inflate code rolled into a ball. - * - * Copyright 2009 Szabolcs Nagy <nszabolcs@gmail.com> - * - * 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; 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; - } - - 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); -} |