diff options
| -rw-r--r-- | toys/pending/gzip.c | 627 |
1 files changed, 290 insertions, 337 deletions
diff --git a/toys/pending/gzip.c b/toys/pending/gzip.c index 4c8bdd24..00775934 100644 --- a/toys/pending/gzip.c +++ b/toys/pending/gzip.c @@ -58,7 +58,8 @@ uint crc32(uchar *p, int n, uint crc); uint crctab[256]; -void crc32init(void) { +void crc32init(void) +{ static const uint poly = 0xedb88320; int i,j; @@ -66,21 +67,20 @@ void crc32init(void) { uint crc = i; for (j = 0; j < 8; j++) { - if (crc & 1) - crc = (crc >> 1) ^ poly; - else - crc >>= 1; + if (crc & 1) crc = (crc >> 1) ^ poly; + else crc >>= 1; } crctab[i] = crc; } } -uint crc32(uchar *p, int n, uint 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); + while (p < ep) crc = crctab[(crc & 0xff) ^ *p++] ^ (crc >> 8); + return crc ^ 0xffffffff; } @@ -89,7 +89,8 @@ enum { AdlerN = 5552 /* max iters before 32bit overflow */ }; -uint adler32(uchar *p, int n, uint adler) { +uint adler32(uchar *p, int n, uint adler) +{ uint s1 = adler & 0xffff; uint s2 = (adler >> 16) & 0xffff; uchar *ep; @@ -262,18 +263,18 @@ static uchar clenorder[Nclen] = { static uint revinc(uint n, uint len) { uint i = 1 << (len - 1); - while (n & i) - i >>= 1; + while (n & i) i >>= 1; if (i) { n &= i - 1; n |= i; - } else - n = 0; + } 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) { +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; @@ -283,10 +284,8 @@ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) { Entry entry; /* count code lengths */ - for (i = 0; i < CodeBits; i++) - count[i] = 0; - for (i = 0; i < n; i++) - count[lens[i]]++; + 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; @@ -294,18 +293,12 @@ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) { 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; + 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; + if (nbits > TableBits) return -1; } huff->nbits = nbits; @@ -313,8 +306,7 @@ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) { 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; + if (left < 0) return -1; } for (sum = 0, i = 0; i <= max; i++) { @@ -322,25 +314,20 @@ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) { sum += count[i]; } /* needed for decoding codes longer than nbits */ - if (nbits < max) - huff->sum = offs[nbits + 1]; + 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; + 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; + 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; + for (i = code; i < 1 << nbits; i += 1 << len) table[i] = entry; /* next code */ symbol++; code = revinc(code, len); @@ -351,60 +338,65 @@ static int build_huff(Huff *huff, uchar *lens, uint n, uint nbits) { 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) { +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; + 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; + 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) { +static int fillbits_fast(uchar **src, uchar *srcend, uint *bits, uint *nbits, + uint n) +{ while (*nbits < n) { - if (*src == srcend) - return 0; + 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) { +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) { +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) { +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) { +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; @@ -422,8 +414,7 @@ static uint decode_symbol_long(DecodeState *s, Huff *huff, uint bits, uint nbits nbits -= huffbits; for (;;) { if (!nbits--) { - if (s->src == s->srcend) - return FlateIn; + if (s->src == s->srcend) return FlateIn; bits = *s->src++; nbits = 7; } @@ -431,8 +422,7 @@ static uint decode_symbol_long(DecodeState *s, Huff *huff, uint bits, uint nbits bits >>= 1; sum += *count; cur -= *count; - if (cur < 0) - break; + if (cur < 0) break; cur <<= 1; count++; if (count == huff->count + CodeBits) @@ -440,11 +430,13 @@ static uint decode_symbol_long(DecodeState *s, Huff *huff, uint bits, uint nbits } 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) { +static uint decode_symbol(DecodeState *s, Huff *huff) +{ uint huffbits = huff->nbits; uint nbits = s->nbits; uint bits = s->bits; @@ -493,7 +485,8 @@ static uint decode_symbol(DecodeState *s, Huff *huff) { } /* decode a block of data from stream with trees */ -static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff) { +static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff) +{ uchar *win = s->win; uint pos = s->pos; uint sym = s->nclen; @@ -516,12 +509,12 @@ static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff) { if (sym >= Nlen) { s->pos = pos; s->state = DecodeBlock; - if (sym + 257 == (uint)FlateIn) - return FlateIn; + if (sym + 257 == (uint)FlateIn) return FlateIn; return FlateErr; } case DecodeBlockLenBits: - if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, lenbits[sym])) { + if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, lenbits[sym])) + { s->nclen = sym; /* using nclen to store sym */ s->pos = pos; s->state = DecodeBlockLenBits; @@ -536,8 +529,7 @@ static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff) { s->state = DecodeBlockDist; return FlateIn; } - if (sym >= Ndist) - return FlateErr; + if (sym >= Ndist) return FlateErr; case DecodeBlockDistBits: if (!fillbits_fast(&s->src, s->srcend, &s->bits, &s->nbits, distbits[sym])) { s->nclen = sym; /* using nclen to store sym */ @@ -591,39 +583,31 @@ static int decode_block(DecodeState *s, Huff *lhuff, Huff *dhuff) { } /* inflate state machine (decodes s->src into s->win) */ -static int inflate_state(DecodeState *s) { +static int inflate_state(DecodeState *s) +{ int n; - if (s->posout) - return FlateOut; + if (s->posout) return FlateOut; for (;;) { switch (s->state) { case BlockHead: if (s->final) { - if (s->pos) - return FlateOut; - else - return FlateOk; + if (s->pos) return FlateOut; + else return FlateOk; } - if (!fillbits(s, 3)) - return FlateIn; + 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; + 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; + if (!fillbits(s, 32)) return FlateIn; s->lenpos = getbits(s, 16); n = getbits(s, 16); if (s->lenpos != (~n & 0xffff)) @@ -633,12 +617,10 @@ static int inflate_state(DecodeState *s) { /* TODO: untested, slow, memcpy etc */ /* s->nbits should be 0 here */ while (s->lenpos) { - if (s->src == s->srcend) - return FlateIn; + if (s->src == s->srcend) return FlateIn; s->lenpos--; s->win[s->pos++] = *s->src++; - if (s->pos == WinSize) - return FlateOut; + if (s->pos == WinSize) return FlateOut; } s->state = BlockHead; break; @@ -648,24 +630,21 @@ static int inflate_state(DecodeState *s) { break; case DynamicHuff: /* decode dynamic huffman code trees */ - if (!fillbits(s, 14)) - return FlateIn; + 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; + 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 { + if (fillbits(s, 3)) s->lens[clenorder[n]] = getbits(s, 3); + else { s->lenpos = n; return FlateIn; } @@ -709,14 +688,11 @@ static int inflate_state(DecodeState *s) { 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; + 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; + 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) @@ -740,7 +716,8 @@ static int inflate_state(DecodeState *s) { } } -static DecodeState *alloc_decode_state(void) { +static DecodeState *alloc_decode_state(void) +{ DecodeState *s = malloc(sizeof(DecodeState)); if (s) { @@ -749,8 +726,7 @@ static DecodeState *alloc_decode_state(void) { s->src = s->srcend = 0; s->err = 0; /* TODO: globals.. */ - if (lhuff.nbits == 0) - init_fixed_huffs(); + if (lhuff.nbits == 0) init_fixed_huffs(); } return s; } @@ -758,7 +734,8 @@ static DecodeState *alloc_decode_state(void) { /* extern */ -int inflate(FlateStream *stream) { +int inflate(FlateStream *stream) +{ DecodeState *s = stream->state; int n; @@ -771,8 +748,7 @@ int inflate(FlateStream *stream) { } if (!s) { s = stream->state = alloc_decode_state(); - if (!s) - return stream->err = "no mem.", FlateErr; + if (!s) return stream->err = "no mem.", FlateErr; } if (stream->nin) { s->src = stream->in; @@ -781,14 +757,11 @@ int inflate(FlateStream *stream) { } n = inflate_state(s); if (n == FlateOut) { - if (s->pos < stream->nout) - stream->nout = s->pos; + 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 (s->pos) s->posout += stream->nout; + else s->posout = 0; } if (n == FlateOk || n == FlateErr) { if (s->nbits || s->src < s->srcend) { @@ -843,7 +816,8 @@ static ushort fixlcode[Nlitlen]; static uchar fixdlen[Ndist]; /* fixed distance huffman code tree */ static ushort fixdcode[Ndist]; -static uint revcode(uint c, int n) { +static uint revcode(uint c, int n) +{ int i; uint r = 0; @@ -855,37 +829,34 @@ static uint revcode(uint c, int n) { } /* build huffman code tree from code lengths */ -static void huffcodes(ushort *codes, const uchar *lens, int n) { +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 (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 */ + 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; + 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) { +static int heappush(int *heap, int len, int w, int n) +{ int p, c, tmp; c = len; @@ -897,13 +868,13 @@ static int heappush(int *heap, int len, int w, int n) { 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; + } else break; } return len; } -static int heappop(int *heap, int len, int *w, int *n) { +static int heappop(int *heap, int len, int *w, int *n) +{ int p, c, tmp; *n = heap[0]; @@ -913,22 +884,20 @@ static int heappop(int *heap, int len, int *w, int *n) { p = 0; for (;;) { c = heapchild(p); - if (c >= len) - break; - if (c+2 < len && heap[c+3] < heap[c+1]) - c += 2; + 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; + } else break; p = c; } return len; } /* symbol frequencies -> code lengths (limited to 255) */ -static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) { +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]; @@ -937,17 +906,13 @@ static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) { int i, j; int wi, wj; - for (n = 0; n < limit+1; n++) - count[n] = 0; + 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; + 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); + if (freqs[n] == 0) len = heappush(heap, len, ++freqs[n], n); /* build code tree */ top = len; for (n = nsym; len > 2; n++) { @@ -968,8 +933,7 @@ static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) { if (n >= nsym) { /* overwrite parent index with length */ parent[n] = parent[parent[n]] + 1; - if (parent[n] > limit) - overflow++; + if (parent[n] > limit) overflow++; } else { lens[n] = parent[parent[n]] + 1; if (lens[n] > limit) { @@ -979,8 +943,7 @@ static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) { count[lens[n]]++; } } - if (overflow == 0) - return; + if (overflow == 0) return; /* modify code tree to fix overflow (from zlib) */ while (overflow > 0) { for (n = limit-1; count[n] == 0; n--); @@ -1000,7 +963,8 @@ static void hufflens(uchar *lens, ushort *freqs, int nsym, int limit) { } /* output n (<= 16) bits */ -static void putbits(State *s, uint bits, int n) { +static void putbits(State *s, uint bits, int n) +{ s->bits |= bits << s->nbits; s->nbits += n; while (s->nbits >= 8) { @@ -1011,14 +975,14 @@ static void putbits(State *s, uint bits, int n) { } /* 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) { +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; 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++); @@ -1050,16 +1014,17 @@ static int clencodes(uchar *codes, uchar *extra, uchar *llen, int nlit, uchar *d } /* compress block data into s->dstbuf using given codes */ -static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar *dlen) { +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 { + 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 += lenbase[lz->n] + lz->bits; putbits(s, lcode[Nlit + lz->n + 1], llen[Nlit + lz->n + 1]); putbits(s, lz->bits, lenbits[lz->n]); @@ -1067,11 +1032,13 @@ static void putblock(State *s, ushort *lcode, uchar *llen, ushort *dcode, uchar putbits(s, dcode[lz->n], dlen[lz->n]); putbits(s, lz->bits, 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) { +static void deflate_block(State *s) +{ uchar codes[Nlitlen + Ndist], extra[Nlitlen + Ndist]; uchar llen[Nlitlen], dlen[Ndist], clen[Nclen]; ushort cfreq[Nclen]; @@ -1094,8 +1061,7 @@ static void deflate_block(State *s) { 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]]++; + 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--); @@ -1107,21 +1073,18 @@ static void deflate_block(State *s) { 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; + 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 (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 { + } else { p += lenbase[lz->n] + lz->bits; fixsize += fixllen[Nlit + lz->n + 1]; dynsize += llen[Nlit + lz->n + 1]; @@ -1133,6 +1096,7 @@ static void deflate_block(State *s) { fixsize += distbits[lz->n]; dynsize += distbits[lz->n]; } + } fixsize += fixllen[EOB]; dynsize += llen[EOB]; @@ -1144,17 +1108,13 @@ static void deflate_block(State *s) { 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 < 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); + 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) { @@ -1179,23 +1139,23 @@ fprintf(stderr, "blen:%d [%d,%d] lzlen:%d dynlen:%d (tree:%d rate:%.3f) fixlen:% } /* find n in base */ -static int bisect(ushort *base, int len, int n) { +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; + if (n < base[k]) hi = k; + else lo = k + 1; } return lo - 1; } /* add literal run length to lzbuf */ -static void flushlit(State *s) { +static void flushlit(State *s) +{ if (s->nlit) { s->lz->bits = LzLitFlag; s->lz->n = s->nlit; @@ -1205,7 +1165,8 @@ static void flushlit(State *s) { } /* add match to lzbuf and update freq counts */ -static void recordmatch(State *s, Match m) { +static void recordmatch(State *s, Match m) +{ int n; /*fprintf(stderr, "m %d %d\n", m.len, m.dist);*/ @@ -1223,37 +1184,41 @@ static void recordmatch(State *s, Match m) { } /* update literal run length */ -static void recordlit(State *s, int c) { +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; +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) { +static int updatechain(State *s) +{ int hash, next = 0, p = s->pos, i; - if (s->endpos - p < MinMatch) - p = s->endpos - MinMatch; + 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; + 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) { +static Match getmatch(State *s, int next) +{ Match m = {0, MinMatch-1}; int len; int limit = s->pos - MaxDist; @@ -1279,16 +1244,16 @@ static Match getmatch(State *s, int next) { m.len = s->endpos - s->pos; return m; } - if (len == MaxMatch) - 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; + if (m.len < MinMatch || (m.len == MinMatch && m.dist > BigDist)) m.len = 0; + return m; } -static void startblock(State *s) { +static void startblock(State *s) +{ s->startpos = s->pos; s->dst = s->dstbegin = s->dstbuf; s->lz = s->lzbuf; @@ -1298,11 +1263,11 @@ static void startblock(State *s) { s->lfreq[EOB]++; } -static int shiftwin(State *s) { +static int shiftwin(State *s) +{ int n; - if (s->startpos < WinSize) - return 0; + 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; @@ -1311,37 +1276,40 @@ static int shiftwin(State *s) { 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)) { +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--; + if (s->prevm.len) s->pos--; deflate_block(s); - if (s->eof && s->pos == s->endpos) - putbits(s, 0, 7); + if (s->eof && s->pos == s->endpos) putbits(s, 0, 7); + return 1; } + return 0; } -static int fillsrc(State *s) { +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; + 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; + if (s->endpos < SrcSize) return 0; } return 1; } @@ -1354,74 +1322,61 @@ static int calcguard(State *s) { } /* deflate compress from s->src into s->dstbuf */ -static int deflate_state(State *s) { +static int deflate_state(State *s) +{ Match m; int next; int guard; - if (s->state == FlateIn) - s->eof = s->in == s->inend; + 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); + 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; + 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); + 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 = getmatch(s, next); if (next && m.len > s->prevm.len) { - if (s->prevm.len) - recordlit(s, s->src[s->pos-1]); + 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]); + } else recordlit(s, s->src[s->pos]); s->pos++; } } /* alloc and init state */ -static State *alloc_state(void) { +static State *alloc_state(void) +{ State *s = malloc(sizeof(State)); int i; - if (!s) - return s; + 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; + 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); } @@ -1438,7 +1393,8 @@ static State *alloc_state(void) { /* extern */ -int deflate(FlateStream *stream) { +int deflate(FlateStream *stream) +{ State *s = stream->state; int n, k; @@ -1449,48 +1405,54 @@ int deflate(FlateStream *stream) { } if (!s) { s = stream->state = alloc_state(); - if (!s) - return stream->err = "no mem.", FlateErr; + 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; + 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) { +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) { +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) { +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) { +static int check32le(uchar *p, uint n) +{ return n == (p[0] | (p[1] << 8) | (p[2] << 16) | (p[3] << 24)); } @@ -1502,34 +1464,35 @@ enum { ZlibFCHK = 31 - (((ZlibCM | ZlibCINFO) << 8) | ZlibFLEV) % 31 }; -int deflate_zlib_header(uchar *p, int n) { - if (n < 2) - return FlateErr; +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; +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; +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) { +int inflate_zlib_footer(uchar *p, int n, uint sum, uint len, uint zlen) +{ if (n < 4 || !check32(p, sum)) return FlateErr; return 4; @@ -1548,7 +1511,8 @@ enum { GZipOS = 255 }; -int deflate_gzip_header(uchar *p, int n) { +int deflate_gzip_header(uchar *p, int n) +{ if (n < 10) return FlateErr; memset(p, 0, 10); @@ -1560,7 +1524,8 @@ int deflate_gzip_header(uchar *p, int n) { return 10; } -int deflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { +int deflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) +{ if (n < 8) return FlateErr; set32le(p, sum); @@ -1568,45 +1533,38 @@ int deflate_gzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { return 8; } -int inflate_gzip_header(uchar *p, int n) { +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 (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 (k > n) return FlateErr; } if (p[3] & GZipFNAME) { - for (; k < n; k++) - if (p[k] == 0) - break; + for (; k < n; k++) if (p[k] == 0) break; k++; - if (k > n) - return FlateErr; + if (k > n) return FlateErr; } if (p[3] & GZipFCOMM) { - for (; k < n; k++) - if (p[k] == 0) - break; + for (; k < n; k++) if (p[k] == 0) break; k++; - if (k > n) - return FlateErr; + if (k > n) return FlateErr; } if (p[3] & GZipFHCRC) { k += 2; - if (k > n) - return FlateErr; + 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; +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; } @@ -1627,9 +1585,9 @@ enum { PKNameLen = sizeof(pkname) - 1 }; -int deflate_pkzip_header(uchar *p, int n) { - if (n < PKHeadSize + PKNameLen) - return FlateErr; +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); @@ -1641,13 +1599,12 @@ int deflate_pkzip_header(uchar *p, int n) { return PKHeadSize + PKNameLen; } -int deflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { - if (n < PKDirSize + PKNameLen + 22) - return FlateErr; +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; + if (n < 16 + PKDirSize + PKNameLen + 22) return FlateErr; set32le(p, PKDataID); set32le(p+4, sum); set32le(p+8, zlen); @@ -1679,43 +1636,36 @@ int deflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { */ } -int inflate_pkzip_header(uchar *p, int n) { +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; + 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; + if (k > n) return FlateErr; + return k; } -int inflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) { +int inflate_pkzip_footer(uchar *p, int n, uint sum, uint len, uint zlen) +{ int k = PKDirSize + 22; - if (k > n) - return FlateErr; + if (k > n) return FlateErr; if (check32le(p, PKDataID)) { p += 16; k += 16; - if (k > n) - return FlateErr; + 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; + 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; } @@ -1744,7 +1694,8 @@ static uint dummysum(uchar *p, int n, uint sum) { } /* compress, using FlateStream interface */ -int compress_stream(FILE *in, FILE *out) { +int compress_stream(FILE *in, FILE *out) +{ FlateStream s; int k, n; enum {Nin = 1<<15, Nout = 1<<15}; @@ -1799,7 +1750,8 @@ int compress_stream(FILE *in, FILE *out) { } /* decompress, using FlateStream interface */ -int decompress_stream(FILE *in, FILE *out) { +int decompress_stream(FILE *in, FILE *out) +{ FlateStream s; uchar *begin; int k, n; @@ -1859,7 +1811,8 @@ int decompress_stream(FILE *in, FILE *out) { } } -static int old_main(int argc, char *argv[]) { +static int old_main(int argc, char *argv[]) +{ char comp = 'c'; char fmt = 'r'; char verbose = 'q'; |