www.pudn.com > ZLib-check.rar > inftrees.c
#include "zutil.h"
#include "inftrees.h"
#if !defined(BUILDFIXED) && !defined(STDC)
# define BUILDFIXED
#endif
const char inflate_copyright[] =
" inflate 1.1.4 Copyright 1995-2002 Mark Adler ";
struct internal_state {int dummy;};
#define exop word.what.Exop
#define bits word.what.Bits
local int huft_build OF((
uIntf *,
uInt,
uInt,
const uIntf *,
const uIntf *,
inflate_huft * FAR*,
uIntf *,
inflate_huft *,
uInt *,
uIntf * ));
local const uInt cplens[31] = {
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
local const uInt cplext[31] = {
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112};
local const uInt cpdist[30] = {
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
8193, 12289, 16385, 24577};
local const uInt cpdext[30] = {
0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
12, 12, 13, 13};
#define BMAX 15
local int huft_build(b, n, s, d, e, t, m, hp, hn, v)
uIntf *b;
uInt n;
uInt s;
const uIntf *d;
const uIntf *e;
inflate_huft * FAR *t;
uIntf *m;
inflate_huft *hp;
uInt *hn;
uIntf *v;
{
uInt a;
uInt c[BMAX+1];
uInt f;
int g;
int h;
register uInt i;
register uInt j;
register int k;
int l;
uInt mask;
register uIntf *p;
inflate_huft *q;
struct inflate_huft_s r;
inflate_huft *u[BMAX];
register int w;
uInt x[BMAX+1];
uIntf *xp;
int y;
uInt z;
p = c;
#define C0 *p++ = 0;
#define C2 C0 C0 C0 C0
#define C4 C2 C2 C2 C2
C4
p = b; i = n;
do {
c[*p++]++;
} while (--i);
if (c[0] == n)
{
*t = (inflate_huft *)Z_NULL;
*m = 0;
return Z_OK;
}
l = *m;
for (j = 1; j <= BMAX; j++)
if (c[j])
break;
k = j;
if ((uInt)l < j)
l = j;
for (i = BMAX; i; i--)
if (c[i])
break;
g = i;
if ((uInt)l > i)
l = i;
*m = l;
for (y = 1 << j; j < i; j++, y <<= 1)
if ((y -= c[j]) < 0)
return Z_DATA_ERROR;
if ((y -= c[i]) < 0)
return Z_DATA_ERROR;
c[i] += y;
x[1] = j = 0;
p = c + 1; xp = x + 2;
while (--i) {
*xp++ = (j += *p++);
}
p = b; i = 0;
do {
if ((j = *p++) != 0)
v[x[j]++] = i;
} while (++i < n);
n = x[g];
x[0] = i = 0;
p = v;
h = -1;
w = -l;
u[0] = (inflate_huft *)Z_NULL;
q = (inflate_huft *)Z_NULL;
z = 0;
for (; k <= g; k++)
{
a = c[k];
while (a--)
{
while (k > w + l)
{
h++;
w += l;
z = g - w;
z = z > (uInt)l ? l : z;
if ((f = 1 << (j = k - w)) > a + 1)
{
f -= a + 1;
xp = c + k;
if (j < z)
while (++j < z)
{
if ((f <<= 1) <= *++xp)
break;
f -= *xp;
}
}
z = 1 << j;
if (*hn + z > MANY)
return Z_DATA_ERROR;
u[h] = q = hp + *hn;
*hn += z;
if (h)
{
x[h] = i;
r.bits = (Byte)l;
r.exop = (Byte)j;
j = i >> (w - l);
r.base = (uInt)(q - u[h-1] - j);
u[h-1][j] = r;
}
else
*t = q;
}
r.bits = (Byte)(k - w);
if (p >= v + n)
r.exop = 128 + 64;
else if (*p < s)
{
r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);
r.base = *p++;
}
else
{
r.exop = (Byte)(e[*p - s] + 16 + 64);
r.base = d[*p++ - s];
}
f = 1 << (k - w);
for (j = i >> w; j < z; j += f)
q[j] = r;
for (j = 1 << (k - 1); i & j; j >>= 1)
i ^= j;
i ^= j;
mask = (1 << w) - 1;
while ((i & mask) != x[h])
{
h--;
w -= l;
mask = (1 << w) - 1;
}
}
}
return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
}
int inflate_trees_bits(c, bb, tb, hp, z)
uIntf *c;
uIntf *bb;
inflate_huft * FAR *tb;
inflate_huft *hp;
z_streamp z;
{
int r;
uInt hn = 0;
uIntf *v;
if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL)
return Z_MEM_ERROR;
r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL,
tb, bb, hp, &hn, v);
if (r == Z_DATA_ERROR)
z->msg = (char*)"oversubscribed dynamic bit lengths tree";
else if (r == Z_BUF_ERROR || *bb == 0)
{
z->msg = (char*)"incomplete dynamic bit lengths tree";
r = Z_DATA_ERROR;
}
ZFREE(z, v);
return r;
}
int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, hp, z)
uInt nl;
uInt nd;
uIntf *c;
uIntf *bl;
uIntf *bd;
inflate_huft * FAR *tl;
inflate_huft * FAR *td;
inflate_huft *hp;
z_streamp z;
{
int r;
uInt hn = 0;
uIntf *v;
if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
return Z_MEM_ERROR;
r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
if (r != Z_OK || *bl == 0)
{
if (r == Z_DATA_ERROR)
z->msg = (char*)"oversubscribed literal/length tree";
else if (r != Z_MEM_ERROR)
{
z->msg = (char*)"incomplete literal/length tree";
r = Z_DATA_ERROR;
}
ZFREE(z, v);
return r;
}
r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
if (r != Z_OK || (*bd == 0 && nl > 257))
{
if (r == Z_DATA_ERROR)
z->msg = (char*)"oversubscribed distance tree";
else if (r == Z_BUF_ERROR) {
#ifdef PKZIP_BUG_WORKAROUND
r = Z_OK;
}
#else
z->msg = (char*)"incomplete distance tree";
r = Z_DATA_ERROR;
}
else if (r != Z_MEM_ERROR)
{
z->msg = (char*)"empty distance tree with lengths";
r = Z_DATA_ERROR;
}
ZFREE(z, v);
return r;
#endif
}
ZFREE(z, v);
return Z_OK;
}
#ifdef BUILDFIXED
local int fixed_built = 0;
#define FIXEDH 544
local inflate_huft fixed_mem[FIXEDH];
local uInt fixed_bl;
local uInt fixed_bd;
local inflate_huft *fixed_tl;
local inflate_huft *fixed_td;
#else
#include "inffixed.h"
#endif
int inflate_trees_fixed(bl, bd, tl, td, z)
uIntf *bl;
uIntf *bd;
inflate_huft * FAR *tl;
inflate_huft * FAR *td;
z_streamp z;
{
#ifdef BUILDFIXED
if (!fixed_built)
{
int k;
uInt f = 0;
uIntf *c;
uIntf *v;
if ((c = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
return Z_MEM_ERROR;
if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
{
ZFREE(z, c);
return Z_MEM_ERROR;
}
for (k = 0; k < 144; k++)
c[k] = 8;
for (; k < 256; k++)
c[k] = 9;
for (; k < 280; k++)
c[k] = 7;
for (; k < 288; k++)
c[k] = 8;
fixed_bl = 9;
huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl,
fixed_mem, &f, v);
for (k = 0; k < 30; k++)
c[k] = 5;
fixed_bd = 5;
huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd,
fixed_mem, &f, v);
ZFREE(z, v);
ZFREE(z, c);
fixed_built = 1;
}
#endif
*bl = fixed_bl;
*bd = fixed_bd;
*tl = fixed_tl;
*td = fixed_td;
return Z_OK;
}