00001
00002
00003
00004
00005
00006 #include "zutil.h"
00007 #include "inftrees.h"
00008
00009 #if !defined(BUILDFIXED) && !defined(STDC)
00010 # define BUILDFIXED
00011 #endif
00012
00013 const char inflate_copyright[] =
00014 " inflate 1.1.3 Copyright 1995-1998 Mark Adler ";
00015
00016
00017
00018
00019
00020
00021 struct internal_state {int dummy;};
00022
00023
00024 #define exop word.what.Exop
00025 #define bits word.what.Bits
00026
00027
00028 local int huft_build OF((
00029 uIntf *,
00030 uInt,
00031 uInt,
00032 const uIntf *,
00033 const uIntf *,
00034 inflate_huft * FAR*,
00035 uIntf *,
00036 inflate_huft *,
00037 uInt *,
00038 uIntf * ));
00039
00040
00041 local const uInt cplens[31] = {
00042 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
00043 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
00044
00045 local const uInt cplext[31] = {
00046 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
00047 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112};
00048 local const uInt cpdist[30] = {
00049 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
00050 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
00051 8193, 12289, 16385, 24577};
00052 local const uInt cpdext[30] = {
00053 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
00054 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
00055 12, 12, 13, 13};
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082
00083
00084
00085
00086
00087
00088
00089
00090
00091 #define BMAX 15
00092
00093 local int huft_build(b, n, s, d, e, t, m, hp, hn, v)
00094 uIntf *b;
00095 uInt n;
00096 uInt s;
00097 const uIntf *d;
00098 const uIntf *e;
00099 inflate_huft * FAR *t;
00100 uIntf *m;
00101 inflate_huft *hp;
00102 uInt *hn;
00103 uIntf *v;
00104
00105
00106
00107
00108
00109 {
00110
00111 uInt a;
00112 uInt c[BMAX+1];
00113 uInt f;
00114 int g;
00115 int h;
00116 register uInt i;
00117 register uInt j;
00118 register int k;
00119 int l;
00120 uInt mask;
00121 register uIntf *p;
00122 inflate_huft *q;
00123 struct inflate_huft_s r;
00124 inflate_huft *u[BMAX];
00125 register int w;
00126 uInt x[BMAX+1];
00127 uIntf *xp;
00128 int y;
00129 uInt z;
00130
00131
00132
00133 p = c;
00134 #define C0 *p++ = 0;
00135 #define C2 C0 C0 C0 C0
00136 #define C4 C2 C2 C2 C2
00137 C4
00138 p = b; i = n;
00139 do {
00140 c[*p++]++;
00141 } while (--i);
00142 if (c[0] == n)
00143 {
00144 *t = (inflate_huft *)Z_NULL;
00145 *m = 0;
00146 return Z_OK;
00147 }
00148
00149
00150
00151 l = *m;
00152 for (j = 1; j <= BMAX; j++)
00153 if (c[j])
00154 break;
00155 k = j;
00156 if ((uInt)l < j)
00157 l = j;
00158 for (i = BMAX; i; i--)
00159 if (c[i])
00160 break;
00161 g = i;
00162 if ((uInt)l > i)
00163 l = i;
00164 *m = l;
00165
00166
00167
00168 for (y = 1 << j; j < i; j++, y <<= 1)
00169 if ((y -= c[j]) < 0)
00170 return Z_DATA_ERROR;
00171 if ((y -= c[i]) < 0)
00172 return Z_DATA_ERROR;
00173 c[i] += y;
00174
00175
00176
00177 x[1] = j = 0;
00178 p = c + 1; xp = x + 2;
00179 while (--i) {
00180 *xp++ = (j += *p++);
00181 }
00182
00183
00184
00185 p = b; i = 0;
00186 do {
00187 if ((j = *p++) != 0)
00188 v[x[j]++] = i;
00189 } while (++i < n);
00190 n = x[g];
00191
00192
00193
00194 x[0] = i = 0;
00195 p = v;
00196 h = -1;
00197 w = -l;
00198 u[0] = (inflate_huft *)Z_NULL;
00199 q = (inflate_huft *)Z_NULL;
00200 z = 0;
00201
00202
00203 for (; k <= g; k++)
00204 {
00205 a = c[k];
00206 while (a--)
00207 {
00208
00209
00210 while (k > w + l)
00211 {
00212 h++;
00213 w += l;
00214
00215
00216 z = g - w;
00217 z = z > (uInt)l ? l : z;
00218 if ((f = 1 << (j = k - w)) > a + 1)
00219 {
00220 f -= a + 1;
00221 xp = c + k;
00222 if (j < z)
00223 while (++j < z)
00224 {
00225 if ((f <<= 1) <= *++xp)
00226 break;
00227 f -= *xp;
00228 }
00229 }
00230 z = 1 << j;
00231
00232
00233 if (*hn + z > MANY)
00234 return Z_MEM_ERROR;
00235 u[h] = q = hp + *hn;
00236 *hn += z;
00237
00238
00239 if (h)
00240 {
00241 x[h] = i;
00242 r.bits = (Byte)l;
00243 r.exop = (Byte)j;
00244 j = i >> (w - l);
00245 r.base = (uInt)(q - u[h-1] - j);
00246 u[h-1][j] = r;
00247 }
00248 else
00249 *t = q;
00250 }
00251
00252
00253 r.bits = (Byte)(k - w);
00254 if (p >= v + n)
00255 r.exop = 128 + 64;
00256 else if (*p < s)
00257 {
00258 r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);
00259 r.base = *p++;
00260 }
00261 else
00262 {
00263 r.exop = (Byte)(e[*p - s] + 16 + 64);
00264 r.base = d[*p++ - s];
00265 }
00266
00267
00268 f = 1 << (k - w);
00269 for (j = i >> w; j < z; j += f)
00270 q[j] = r;
00271
00272
00273 for (j = 1 << (k - 1); i & j; j >>= 1)
00274 i ^= j;
00275 i ^= j;
00276
00277
00278 mask = (1 << w) - 1;
00279 while ((i & mask) != x[h])
00280 {
00281 h--;
00282 w -= l;
00283 mask = (1 << w) - 1;
00284 }
00285 }
00286 }
00287
00288
00289
00290 return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
00291 }
00292
00293
00294 int inflate_trees_bits(c, bb, tb, hp, z)
00295 uIntf *c;
00296 uIntf *bb;
00297 inflate_huft * FAR *tb;
00298 inflate_huft *hp;
00299 z_streamp z;
00300 {
00301 int r;
00302 uInt hn = 0;
00303 uIntf *v;
00304
00305 if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL)
00306 return Z_MEM_ERROR;
00307 r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL,
00308 tb, bb, hp, &hn, v);
00309 if (r == Z_DATA_ERROR)
00310 z->msg = (char*)"oversubscribed dynamic bit lengths tree";
00311 else if (r == Z_BUF_ERROR || *bb == 0)
00312 {
00313 z->msg = (char*)"incomplete dynamic bit lengths tree";
00314 r = Z_DATA_ERROR;
00315 }
00316 ZFREE(z, v);
00317 return r;
00318 }
00319
00320
00321 int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, hp, z)
00322 uInt nl;
00323 uInt nd;
00324 uIntf *c;
00325 uIntf *bl;
00326 uIntf *bd;
00327 inflate_huft * FAR *tl;
00328 inflate_huft * FAR *td;
00329 inflate_huft *hp;
00330 z_streamp z;
00331 {
00332 int r;
00333 uInt hn = 0;
00334 uIntf *v;
00335
00336
00337 if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
00338 return Z_MEM_ERROR;
00339
00340
00341 r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
00342 if (r != Z_OK || *bl == 0)
00343 {
00344 if (r == Z_DATA_ERROR)
00345 z->msg = (char*)"oversubscribed literal/length tree";
00346 else if (r != Z_MEM_ERROR)
00347 {
00348 z->msg = (char*)"incomplete literal/length tree";
00349 r = Z_DATA_ERROR;
00350 }
00351 ZFREE(z, v);
00352 return r;
00353 }
00354
00355
00356 r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
00357 if (r != Z_OK || (*bd == 0 && nl > 257))
00358 {
00359 if (r == Z_DATA_ERROR)
00360 z->msg = (char*)"oversubscribed distance tree";
00361 else if (r == Z_BUF_ERROR) {
00362 #ifdef PKZIP_BUG_WORKAROUND
00363 r = Z_OK;
00364 }
00365 #else
00366 z->msg = (char*)"incomplete distance tree";
00367 r = Z_DATA_ERROR;
00368 }
00369 else if (r != Z_MEM_ERROR)
00370 {
00371 z->msg = (char*)"empty distance tree with lengths";
00372 r = Z_DATA_ERROR;
00373 }
00374 ZFREE(z, v);
00375 return r;
00376 #endif
00377 }
00378
00379
00380 ZFREE(z, v);
00381 return Z_OK;
00382 }
00383
00384
00385
00386 #ifdef BUILDFIXED
00387 local int fixed_built = 0;
00388 #define FIXEDH 544
00389 local inflate_huft fixed_mem[FIXEDH];
00390 local uInt fixed_bl;
00391 local uInt fixed_bd;
00392 local inflate_huft *fixed_tl;
00393 local inflate_huft *fixed_td;
00394 #else
00395 #include "inffixed.h"
00396 #endif
00397
00398
00399 int inflate_trees_fixed(bl, bd, tl, td, z)
00400 uIntf *bl;
00401 uIntf *bd;
00402 inflate_huft * FAR *tl;
00403 inflate_huft * FAR *td;
00404 z_streamp z;
00405 {
00406 #ifdef BUILDFIXED
00407
00408 if (!fixed_built)
00409 {
00410 int k;
00411 uInt f = 0;
00412 uIntf *c;
00413 uIntf *v;
00414
00415
00416 if ((c = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
00417 return Z_MEM_ERROR;
00418 if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
00419 {
00420 ZFREE(z, c);
00421 return Z_MEM_ERROR;
00422 }
00423
00424
00425 for (k = 0; k < 144; k++)
00426 c[k] = 8;
00427 for (; k < 256; k++)
00428 c[k] = 9;
00429 for (; k < 280; k++)
00430 c[k] = 7;
00431 for (; k < 288; k++)
00432 c[k] = 8;
00433 fixed_bl = 9;
00434 huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl,
00435 fixed_mem, &f, v);
00436
00437
00438 for (k = 0; k < 30; k++)
00439 c[k] = 5;
00440 fixed_bd = 5;
00441 huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd,
00442 fixed_mem, &f, v);
00443
00444
00445 ZFREE(z, v);
00446 ZFREE(z, c);
00447 fixed_built = 1;
00448 }
00449 #endif
00450 *bl = fixed_bl;
00451 *bd = fixed_bd;
00452 *tl = fixed_tl;
00453 *td = fixed_td;
00454 return Z_OK;
00455 }