inlib
1.2.0
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Go to the source code of this file.
Classes | |
struct | huft |
Defines | |
#define | WSIZE 0x8000 |
#define | NEXTBYTE csz__ReadByte() |
#define | FPRINTF fprintf |
#define | FLUSH(n) csz__WriteData(n) |
#define | Trace(x) |
#define | CHECK_EOF |
#define | NEEDBITS(n) |
#define | DUMPBITS(n) {b>>=(n);k-=(n);} |
#define | BMAX 16 |
#define | N_MAX 288 |
Typedefs | |
typedef char | boolean |
typedef unsigned char | uch |
typedef unsigned short | ush |
typedef unsigned long | ulg |
Functions | |
int | csz__huft_build (unsigned *, unsigned, unsigned, ush *, ush *, struct huft **, int *) |
int | csz__huft_free (struct huft *) |
int | csz__Inflate_codes (struct huft *, struct huft *, int, int) |
int | csz__Inflate_stored (void) |
int | csz__Inflate_fixed (void) |
int | csz__Inflate_dynamic (void) |
int | csz__Inflate_block (int *) |
int | csz__Inflate (void) |
int | csz__Inflate_free (void) |
void | csz__Init_Inflate (long a_ibufcnt, unsigned char *a_ibufptr, long a_obufcnt, unsigned char *a_obufptr) |
unsigned char * | csz__obufptr () |
Variables | |
static uch * | obufptr |
static long | obufcnt |
struct huft * | csz__fixed_tl = (struct huft *)NULL |
struct huft * | csz__fixed_td |
int | csz__fixed_bl |
int | csz__fixed_bd |
#define NEEDBITS | ( | n | ) |
int csz__huft_build | ( | unsigned * | b, |
unsigned | n, | ||
unsigned | s, | ||
ush * | d, | ||
ush * | e, | ||
struct huft ** | t, | ||
int * | m | ||
) |
Definition at line 426 of file inflate.c.
{ unsigned a; /* counter for codes of length k */ unsigned c[BMAX+1]; /* bit length count table */ unsigned el; /* length of EOB code (value 256) */ unsigned f; /* i repeats in table every f entries */ int g; /* maximum code length */ int h; /* table level */ register unsigned i; /* counter, current code */ register unsigned j; /* counter */ register int k; /* number of bits in current code */ int lx[BMAX+1]; /* memory for l[-1..BMAX-1] */ int *l = lx+1; /* stack of bits per table */ register unsigned *p; /* pointer into c[], b[], or v[] */ register struct huft *q; /* points to current table */ struct huft r; /* table entry for structure assignment */ struct huft *u[BMAX]; /* table stack */ static unsigned v[N_MAX]; /* values in order of bit length */ register int w; /* bits before this table == (l * h) */ unsigned x[BMAX+1]; /* bit offsets, then code stack */ unsigned *xp; /* pointer into x */ int y; /* number of dummy codes added */ unsigned z; /* number of entries in current table */ /* Generate counts for each bit length */ el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */ memset((char *)c,0,sizeof(c)); p = b; i = n; do { c[*p]++; p++; /* assume all entries <= BMAX */ } while (--i); if (c[0] == n) /* null input--all zero length codes */ { *t = (struct huft *)NULL; *m = 0; return 0; } /* Find minimum and maximum length, bound *m by those */ for (j = 1; j <= BMAX; j++) if (c[j]) break; k = j; /* minimum code length */ if ((unsigned)*m < j) *m = j; for (i = BMAX; i; i--) if (c[i]) break; g = i; /* maximum code length */ if ((unsigned)*m > i) *m = i; /* Adjust last length count to fill out codes, if needed */ for (y = 1 << j; j < i; j++, y <<= 1) if ((y -= c[j]) < 0) return 2; /* bad input: more codes than bits */ if ((y -= c[i]) < 0) return 2; c[i] += y; /* Generate starting offsets into the value table for each length */ x[1] = j = 0; p = c + 1; xp = x + 2; while (--i) { /* note that i == g from above */ *xp++ = (j += *p++); } /* Make a table of values in order of bit lengths */ p = b; i = 0; do { if ((j = *p++) != 0) v[x[j]++] = i; } while (++i < n); /* Generate the Huffman codes and for each, make the table entries */ x[0] = i = 0; /* first Huffman code is zero */ p = v; /* grab values in bit order */ h = -1; /* no tables yet--level -1 */ w = l[-1] = 0; /* no bits decoded yet */ u[0] = (struct huft *)NULL; /* just to keep compilers happy */ q = (struct huft *)NULL; /* ditto */ z = 0; /* ditto */ /* go through the bit lengths (k already is bits in shortest code) */ for (; k <= g; k++) { a = c[k]; while (a--) { /* here i is the Huffman code of length k bits for value *p */ /* make tables up to required level */ while (k > w + l[h]) { w += l[h++]; /* add bits already decoded */ /* compute minimum size table less than or equal to *m bits */ z = (z = g - w) > (unsigned)*m ? (unsigned) *m : z; /* upper limit */ if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */ { /* too few codes for k-w bit table */ f -= a + 1; /* deduct codes from patterns left */ xp = c + k; while (++j < z) /* try smaller tables up to z bits */ { if ((f <<= 1) <= *++xp) break; /* enough codes to use up j bits */ f -= *xp; /* else deduct codes from patterns */ } } if ((unsigned)w + j > el && (unsigned)w < el) j = el - w; /* make EOB code end at table */ z = 1 << j; /* table entries for j-bit table */ l[h] = j; /* set table size in stack */ /* allocate and link in new table */ if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) == (struct huft *)NULL) { if (h) csz__huft_free(u[0]); return 3; /* not enough memory */ } hufts += z + 1; /* track memory usage */ *t = q + 1; /* link to list for huft_free() */ *(t = &(q->v.t)) = (struct huft *)NULL; u[h] = ++q; /* table starts after link */ /* connect to last table, if there is one */ if (h) { x[h] = i; /* save pattern for backing up */ r.b = (uch)l[h-1]; /* bits to dump before this table */ r.e = (uch)(16 + j); /* bits in this table */ r.v.t = q; /* pointer to this table */ j = (i & ((1 << w) - 1)) >> (w - l[h-1]); u[h-1][j] = r; /* connect to last table */ } } /* set up table entry in r */ r.b = (uch)(k - w); if (p >= v + n) r.e = 99; /* out of values--invalid code */ else if (*p < s) { r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */ r.v.n = *p++; /* simple code is just the value */ } else if(e && d) { r.e = (uch)e[*p - s]; /* non-simple--look up in lists */ r.v.n = d[*p++ - s]; } else return 1; /* fill code-like entries with r */ f = 1 << (k - w); for (j = i >> w; j < z; j += f) q[j] = r; /* backwards increment the k-bit code i */ for (j = 1 << (k - 1); i & j; j >>= 1) i ^= j; i ^= j; /* backup over finished tables */ while ((i & ((1 << w) - 1)) != x[h]) w -= l[--h]; /* don't need to update q */ } } /* return actual size of base table */ *m = l[0]; /* Return true (1) if we were given an incomplete table */ return y != 0 && g != 1; }
int csz__huft_free | ( | struct huft * | t | ) |
int csz__Inflate | ( | void | ) |
Definition at line 1083 of file inflate.c.
{ int e; /* last block flag */ int r; /* result code */ unsigned h; /* maximum struct huft's malloc'ed */ /* initialize window, bit buffer */ wp = 0; bk = 0; bb = 0; /* decompress until the last block */ h = 0; do { hufts = 0; if ((r = csz__Inflate_block(&e)) != 0) return r; if (hufts > h) h = hufts; } while (!e); /* flush out slide */ FLUSH(wp); /* return success */ Trace((stderr, "\n%lu bytes in Huffman tables (%lu/entry)\n", h * sizeof(struct huft), sizeof(struct huft))); return 0; }
int csz__Inflate_block | ( | int * | e | ) |
Definition at line 1035 of file inflate.c.
{ unsigned t; /* block type */ register ulg b; /* bit buffer */ register unsigned k; /* number of bits in bit buffer */ /* make local bit buffer */ b = bb; k = bk; /* read in last block bit */ NEEDBITS(1) *e = (int)b & 1; DUMPBITS(1) /* read in block type */ NEEDBITS(2) t = (unsigned)b & 3; DUMPBITS(2) /* restore the global bit buffer */ bb = b; bk = k; /* inflate that block type */ if (t == 2) return csz__Inflate_dynamic(); if (t == 0) return csz__Inflate_stored(); if (t == 1) return csz__Inflate_fixed(); /* bad block type */ return 2; }
Definition at line 653 of file inflate.c.
{ register unsigned e; /* table entry flag/number of extra bits */ unsigned n, d; /* length and index for copy */ unsigned w; /* current window position */ struct huft *t; /* pointer to table entry */ unsigned ml, md; /* masks for bl and bd bits */ register ulg b; /* bit buffer */ register unsigned k; /* number of bits in bit buffer */ /* make local copies of globals */ b = bb; /* initialize bit buffer */ k = bk; w = wp; /* initialize window position */ /* inflate the coded data */ ml = mask[bl]; /* precompute masks for speed */ md = mask[bd]; while (1) /* do until end of block */ { NEEDBITS((unsigned)bl) if ((e = (t = tl + ((unsigned)b & ml))->e) > 16) do { if (e == 99) return 1; DUMPBITS(t->b) e -= 16; NEEDBITS(e) } while ((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16); DUMPBITS(t->b) if (e == 16) /* then it's a literal */ { csz__slide[w++] = (uch)t->v.n; if (w == WSIZE) { FLUSH(w); w = 0; } } else /* it's an EOB or a length */ { /* exit if end of block */ if (e == 15) break; /* get length of block to copy */ NEEDBITS(e) n = t->v.n + ((unsigned)b & mask[e]); DUMPBITS(e); /* decode distance of block to copy */ NEEDBITS((unsigned)bd) if ((e = (t = td + ((unsigned)b & md))->e) > 16) do { if (e == 99) return 1; DUMPBITS(t->b) e -= 16; NEEDBITS(e) } while ((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16); DUMPBITS(t->b) NEEDBITS(e) d = w - t->v.n - ((unsigned)b & mask[e]); DUMPBITS(e) /* do the copy */ do { n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e); #ifndef NOMEMCPY if (w - d >= e) /* (this test assumes unsigned comparison) */ { memcpy(csz__slide + w, csz__slide + d, e); w += e; d += e; } else /* do it slow to avoid memcpy() overlap */ #endif /* !NOMEMCPY */ do { csz__slide[w++] = csz__slide[d++]; } while (--e); if (w == WSIZE) { FLUSH(w); w = 0; } } while (n); } } /* restore the globals from the locals */ wp = w; /* restore global window pointer */ bb = b; /* restore global bit buffer */ bk = k; /* done */ return 0; }
int csz__Inflate_dynamic | ( | void | ) |
Definition at line 869 of file inflate.c.
{ int i; /* temporary variables */ unsigned j; unsigned l; /* last length */ unsigned m; /* mask for bit lengths table */ unsigned n; /* number of lengths to get */ struct huft *tl; /* literal/length code table */ struct huft *td; /* distance code table */ int bl; /* lookup bits for tl */ int bd; /* lookup bits for td */ unsigned nb; /* number of bit length codes */ unsigned nl; /* number of literal/length codes */ unsigned nd; /* number of distance codes */ #ifdef PKZIP_BUG_WORKAROUND static unsigned ll[288+32]; /* literal/length and distance code lengths */ #else static unsigned ll[286+30]; /* literal/length and distance code lengths */ #endif register ulg b; /* bit buffer */ register unsigned k; /* number of bits in bit buffer */ static int qflag = 0; /*G.Barrand*/ /* make local bit buffer */ Trace((stderr, "\ndynamic block")); b = bb; k = bk; /* read in table lengths */ NEEDBITS(5) nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */ DUMPBITS(5) NEEDBITS(5) nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */ DUMPBITS(5) NEEDBITS(4) nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */ DUMPBITS(4) #ifdef PKZIP_BUG_WORKAROUND if (nl > 288 || nd > 32) #else if (nl > 286 || nd > 30) #endif return 1; /* bad lengths */ /* read in bit-length-code lengths */ for (j = 0; j < nb; j++) { NEEDBITS(3) ll[border[j]] = (unsigned)b & 7; DUMPBITS(3) } for (; j < 19; j++) ll[border[j]] = 0; /* build decoding table for trees--single level, 7 bit lookup */ bl = 7; if ((i = csz__huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) { if (i == 1) csz__huft_free(tl); return i; /* incomplete code set */ } /* read in literal and distance code lengths */ n = nl + nd; m = mask[bl]; i = l = 0; while ((unsigned)i < n) { NEEDBITS((unsigned)bl) j = (td = tl + ((unsigned)b & m))->b; DUMPBITS(j) j = td->v.n; if (j < 16) /* length of code in bits (0..15) */ ll[i++] = l = j; /* save last length in l */ else if (j == 16) /* repeat last length 3 to 6 times */ { NEEDBITS(2) j = 3 + ((unsigned)b & 3); DUMPBITS(2) if ((unsigned)i + j > n) return 1; while (j--) ll[i++] = l; } else if (j == 17) /* 3 to 10 zero length codes */ { NEEDBITS(3) j = 3 + ((unsigned)b & 7); DUMPBITS(3) if ((unsigned)i + j > n) return 1; while (j--) ll[i++] = 0; l = 0; } else /* j == 18: 11 to 138 zero length codes */ { NEEDBITS(7) j = 11 + ((unsigned)b & 0x7f); DUMPBITS(7) if ((unsigned)i + j > n) return 1; while (j--) ll[i++] = 0; l = 0; } } /* free decoding table for trees */ csz__huft_free(tl); /* restore the global bit buffer */ bb = b; bk = k; /* build the decoding tables for literal/length and distance codes */ bl = lbits; if ((i = csz__huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) { if (i == 1 && !qflag) { FPRINTF(stderr, "(incomplete l-tree) "); csz__huft_free(tl); } return i; /* incomplete code set */ } bd = dbits; if ((i = csz__huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) { if (i == 1 && !qflag) { FPRINTF(stderr, "(incomplete d-tree) "); #ifdef PKZIP_BUG_WORKAROUND i = 0; } #else csz__huft_free(td); } csz__huft_free(tl); return i; /* incomplete code set */ #endif } /* decompress until an end-of-block code */ if (csz__Inflate_codes(tl, td, bl, bd)) return 1; /* free the decoding tables, return */ csz__huft_free(tl); csz__huft_free(td); return 0; }
int csz__Inflate_fixed | ( | void | ) |
Definition at line 821 of file inflate.c.
{ /* if first time, set up tables for fixed blocks */ Trace((stderr, "\nliteral block")); if (csz__fixed_tl == (struct huft *)NULL) { int i; /* temporary variable */ static unsigned l[288]; /* length list for huft_build */ /* literal table */ for (i = 0; i < 144; i++) l[i] = 8; for (; i < 256; i++) l[i] = 9; for (; i < 280; i++) l[i] = 7; for (; i < 288; i++) /* make a complete, but wrong code set */ l[i] = 8; csz__fixed_bl = 7; if ((i = csz__huft_build(l, 288, 257, cplens, cplext, &csz__fixed_tl, &csz__fixed_bl)) != 0) { csz__fixed_tl = (struct huft *)NULL; return i; } /* distance table */ for (i = 0; i < 30; i++) /* make an incomplete code set */ l[i] = 5; csz__fixed_bd = 5; if ((i = csz__huft_build(l, 30, 0, cpdist, cpdext, &csz__fixed_td, &csz__fixed_bd)) > 1) { csz__huft_free(csz__fixed_tl); csz__fixed_tl = (struct huft *)NULL; return i; } } /* decompress until an end-of-block code */ return csz__Inflate_codes(csz__fixed_tl, csz__fixed_td, csz__fixed_bl, csz__fixed_bd) != 0; }
int csz__Inflate_free | ( | void | ) |
Definition at line 1118 of file inflate.c.
{ if (csz__fixed_tl != (struct huft *)NULL) { csz__huft_free(csz__fixed_td); csz__huft_free(csz__fixed_tl); csz__fixed_td = csz__fixed_tl = (struct huft *)NULL; } return 0; }
int csz__Inflate_stored | ( | void | ) |
Definition at line 763 of file inflate.c.
{ unsigned n; /* number of bytes in block */ unsigned w; /* current window position */ register ulg b; /* bit buffer */ register unsigned k; /* number of bits in bit buffer */ /* make local copies of globals */ Trace((stderr, "\nstored block")); b = bb; /* initialize bit buffer */ k = bk; w = wp; /* initialize window position */ /* go to byte boundary */ n = k & 7; DUMPBITS(n); /* get the length and its complement */ NEEDBITS(16) n = ((unsigned)b & 0xffff); DUMPBITS(16) NEEDBITS(16) if (n != (unsigned)((~b) & 0xffff)) return 1; /* error in compressed data */ DUMPBITS(16) /* read and output the compressed data */ while (n--) { NEEDBITS(8) csz__slide[w++] = (uch)b; if (w == WSIZE) { FLUSH(w); w = 0; } DUMPBITS(8) } /* restore the globals from the locals */ wp = w; /* restore global window pointer */ bb = b; /* restore global bit buffer */ bk = k; return 0; }
void csz__Init_Inflate | ( | long | a_ibufcnt, |
unsigned char * | a_ibufptr, | ||
long | a_obufcnt, | ||
unsigned char * | a_obufptr | ||
) |
int csz__fixed_bd |
int csz__fixed_bl |
struct huft* csz__fixed_td |
struct huft* csz__fixed_tl = (struct huft *)NULL |