- Main Page
- Namespaces
- Classes
- Files
- Directories

- File List
- File Members

# inftrees.c

    00001 /* inftrees.c -- generate Huffman trees for efficient decoding
    00002  * Copyright (C) 1995-2002 Mark Adler
    00003  * For conditions of distribution and use, see copyright notice in zlib.h
    00004  */
    00005
    00006 #include "zutil.h"
    00007 #include "inftrees.h"
    00008
    00009 #if !defined(BUILDFIXED) && !defined(STDC)
    00010 #  define BUILDFIXED   /* non ANSI compilers may not accept inffixed.h */
    00011 #endif
    00012
    00013 const char inflate_copyright[] =
    00014    " inflate 1.1.4 Copyright 1995-2002 Mark Adler ";
    00015 /*
    00016   If you use the zlib library in a product, an acknowledgment is welcome
    00017   in the documentation of your product. If for some reason you cannot
    00018   include such an acknowledgment, I would appreciate that you keep this
    00019   copyright string in the executable of your product.
    00020  */
    00021 struct internal_state  {int dummy;}; /* for buggy compilers */
    00022
    00023 /* simplify the use of the inflate_huft type with some defines */
    00024 #define exop word.what.Exop
    00025 #define bits word.what.Bits
    00026
    00027
    00028 local int huft_build OF((
    00029     uIntf *,            /* code lengths in bits */
    00030     uInt,               /* number of codes */
    00031     uInt,               /* number of "simple" codes */
    00032     const uIntf *,      /* list of base values for non-simple codes */
    00033     const uIntf *,      /* list of extra bits for non-simple codes */
    00034     inflate_huft * FAR*,/* result: starting table */
    00035     uIntf *,            /* maximum lookup bits (returns actual) */
    00036     inflate_huft *,     /* space for trees */
    00037     uInt *,             /* hufts used in space */
    00038     uIntf * ));         /* space for values */
    00039
    00040 /* Tables for deflate from PKZIP's appnote.txt. */
    00041 local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */
    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         /* see note #13 above about 258 */
    00045 local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */
    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}; /* 112==invalid */
    00048 local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */
    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] = { /* Extra bits for distance codes */
    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    Huffman code decoding is performed using a multi-level table lookup.
    00059    The fastest way to decode is to simply build a lookup table whose
    00060    size is determined by the longest code.  However, the time it takes
    00061    to build this table can also be a factor if the data being decoded
    00062    is not very long.  The most common codes are necessarily the
    00063    shortest codes, so those codes dominate the decoding time, and hence
    00064    the speed.  The idea is you can have a shorter table that decodes the
    00065    shorter, more probable codes, and then point to subsidiary tables for
    00066    the longer codes.  The time it costs to decode the longer codes is
    00067    then traded against the time it takes to make longer tables.
    00068
    00069    This results of this trade are in the variables lbits and dbits
    00070    below.  lbits is the number of bits the first level table for literal/
    00071    length codes can decode in one step, and dbits is the same thing for
    00072    the distance codes.  Subsequent tables are also less than or equal to
    00073    those sizes.  These values may be adjusted either when all of the
    00074    codes are shorter than that, in which case the longest code length in
    00075    bits is used, or when the shortest code is *longer* than the requested
    00076    table size, in which case the length of the shortest code in bits is
    00077    used.
    00078
    00079    There are two different values for the two tables, since they code a
    00080    different number of possibilities each.  The literal/length table
    00081    codes 286 possible values, or in a flat code, a little over eight
    00082    bits.  The distance table codes 30 possible values, or a little less
    00083    than five bits, flat.  The optimum values for speed end up being
    00084    about one bit more than those, so lbits is 8+1 and dbits is 5+1.
    00085    The optimum values may differ though from machine to machine, and
    00086    possibly even between compilers.  Your mileage may vary.
    00087  */
    00088
    00089
    00090 /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
    00091 #define BMAX 15         /* maximum bit length of any code */
    00092
    00093 local int huft_build(b, n, s, d, e, t, m, hp, hn, v)
    00094 uIntf *b;               /* code lengths in bits (all assumed <= BMAX) */
    00095 uInt n;                 /* number of codes (assumed <= 288) */
    00096 uInt s;                 /* number of simple-valued codes (0..s-1) */
    00097 const uIntf *d;         /* list of base values for non-simple codes */
    00098 const uIntf *e;         /* list of extra bits for non-simple codes */
    00099 inflate_huft * FAR *t;  /* result: starting table */
    00100 uIntf *m;               /* maximum lookup bits, returns actual */
    00101 inflate_huft *hp;       /* space for trees */
    00102 uInt *hn;               /* hufts used in space */
    00103 uIntf *v;               /* working area: values in order of bit length */
    00104 /* Given a list of code lengths and a maximum table size, make a set of
    00105    tables to decode that set of codes.  Return Z_OK on success, Z_BUF_ERROR
    00106    if the given code set is incomplete (the tables are still built in this
    00107    case), or Z_DATA_ERROR if the input is invalid. */
    00108 {
    00109
    00110   uInt a;                       /* counter for codes of length k */
    00111   uInt c[BMAX+1];               /* bit length count table */
    00112   uInt f;                       /* i repeats in table every f entries */
    00113   int g;                        /* maximum code length */
    00114   int h;                        /* table level */
    00115   register uInt i;              /* counter, current code */
    00116   register uInt j;              /* counter */
    00117   register int k;               /* number of bits in current code */
    00118   int l;                        /* bits per table (returned in m) */
    00119   uInt mask;                    /* (1 << w) - 1, to avoid cc -O bug on HP */
    00120   register uIntf *p;            /* pointer into c[], b[], or v[] */
    00121   inflate_huft *q;              /* points to current table */
    00122   struct inflate_huft_s r;      /* table entry for structure assignment */
    00123   inflate_huft *u[BMAX];        /* table stack */
    00124   register int w;               /* bits before this table == (l * h) */
    00125   uInt x[BMAX+1];               /* bit offsets, then code stack */
    00126   uIntf *xp;                    /* pointer into x */
    00127   int y;                        /* number of dummy codes added */
    00128   uInt z;                       /* number of entries in current table */
    00129
    00130
    00131   /* Generate counts for each bit length */
    00132   p = c;
    00133 #define C0 *p++ = 0;
    00134 #define C2 C0 C0 C0 C0
    00135 #define C4 C2 C2 C2 C2
    00136   C4                            /* clear c[]--assume BMAX+1 is 16 */
    00137   p = b;  i = n;
    00138   do {
    00139     c[*p++]++;                  /* assume all entries <= BMAX */
    00140   } while (--i);
    00141   if (c[0] == n)                /* null input--all zero length codes */
    00142   {
    00143     *t = (inflate_huft *)Z_NULL;
    00144     *m = 0;
    00145     return Z_OK;
    00146   }
    00147
    00148
    00149   /* Find minimum and maximum length, bound *m by those */
    00150   l = *m;
    00151   for (j = 1; j <= BMAX; j++)
    00152     if (c[j])
    00153       break;
    00154   k = j;                        /* minimum code length */
    00155   if ((uInt)l < j)
    00156     l = j;
    00157   for (i = BMAX; i; i--)
    00158     if (c[i])
    00159       break;
    00160   g = i;                        /* maximum code length */
    00161   if ((uInt)l > i)
    00162     l = i;
    00163   *m = l;
    00164
    00165
    00166   /* Adjust last length count to fill out codes, if needed */
    00167   for (y = 1 << j; j < i; j++, y <<= 1)
    00168     if ((y -= c[j]) < 0)
    00169       return Z_DATA_ERROR;
    00170   if ((y -= c[i]) < 0)
    00171     return Z_DATA_ERROR;
    00172   c[i] += y;
    00173
    00174
    00175   /* Generate starting offsets into the value table for each length */
    00176   x[1] = j = 0;
    00177   p = c + 1;  xp = x + 2;
    00178   while (--i) {                 /* note that i == g from above */
    00179     *xp++ = (j += *p++);
    00180   }
    00181
    00182
    00183   /* Make a table of values in order of bit lengths */
    00184   p = b;  i = 0;
    00185   do {
    00186     if ((j = *p++) != 0)
    00187       v[x[j]++] = i;
    00188   } while (++i < n);
    00189   n = x[g];                     /* set n to length of v */
    00190
    00191
    00192   /* Generate the Huffman codes and for each, make the table entries */
    00193   x[0] = i = 0;                 /* first Huffman code is zero */
    00194   p = v;                        /* grab values in bit order */
    00195   h = -1;                       /* no tables yet--level -1 */
    00196   w = -l;                       /* bits decoded == (l * h) */
    00197   u[0] = (inflate_huft *)Z_NULL;        /* just to keep compilers happy */
    00198   q = (inflate_huft *)Z_NULL;   /* ditto */
    00199   z = 0;                        /* ditto */
    00200
    00201   /* go through the bit lengths (k already is bits in shortest code) */
    00202   for (; k <= g; k++)
    00203   {
    00204     a = c[k];
    00205     while (a--)
    00206     {
    00207       /* here i is the Huffman code of length k bits for value *p */
    00208       /* make tables up to required level */
    00209       while (k > w + l)
    00210       {
    00211         h++;
    00212         w += l;                 /* previous table always l bits */
    00213
    00214         /* compute minimum size table less than or equal to l bits */
    00215         z = g - w;
    00216         z = z > (uInt)l ? l : z;        /* table size upper limit */
    00217         if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
    00218         {                       /* too few codes for k-w bit table */
    00219           f -= a + 1;           /* deduct codes from patterns left */
    00220           xp = c + k;
    00221           if (j < z)
    00222             while (++j < z)     /* try smaller tables up to z bits */
    00223             {
    00224               if ((f <<= 1) <= *++xp)
    00225                 break;          /* enough codes to use up j bits */
    00226               f -= *xp;         /* else deduct codes from patterns */
    00227             }
    00228         }
    00229         z = 1 << j;             /* table entries for j-bit table */
    00230
    00231         /* allocate new table */
    00232         if (*hn + z > MANY)     /* (note: doesn't matter for fixed) */
    00233           return Z_DATA_ERROR;  /* overflow of MANY */
    00234         u[h] = q = hp + *hn;
    00235         *hn += z;
    00236
    00237         /* connect to last table, if there is one */
    00238         if (h)
    00239         {
    00240           x[h] = i;             /* save pattern for backing up */
    00241           r.bits = (Byte)l;     /* bits to dump before this table */
    00242           r.exop = (Byte)j;     /* bits in this table */
    00243           j = i >> (w - l);
    00244           r.base = (uInt)(q - u[h-1] - j);   /* offset to this table */
    00245           u[h-1][j] = r;        /* connect to last table */
    00246         }
    00247         else
    00248           *t = q;               /* first table is returned result */
    00249       }
    00250
    00251       /* set up table entry in r */
    00252       r.bits = (Byte)(k - w);
    00253       if (p >= v + n)
    00254         r.exop = 128 + 64;      /* out of values--invalid code */
    00255       else if (*p < s)
    00256       {
    00257         r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);     /* 256 is end-of-block */
    00258         r.base = *p++;          /* simple code is just the value */
    00259       }
    00260       else
    00261       {
    00262         r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */
    00263         r.base = d[*p++ - s];
    00264       }
    00265
    00266       /* fill code-like entries with r */
    00267       f = 1 << (k - w);
    00268       for (j = i >> w; j < z; j += f)
    00269         q[j] = r;
    00270
    00271       /* backwards increment the k-bit code i */
    00272       for (j = 1 << (k - 1); i & j; j >>= 1)
    00273         i ^= j;
    00274       i ^= j;
    00275
    00276       /* backup over finished tables */
    00277       mask = (1 << w) - 1;      /* needed on HP, cc -O bug */
    00278       while ((i & mask) != x[h])
    00279       {
    00280         h--;                    /* don't need to update q */
    00281         w -= l;
    00282         mask = (1 << w) - 1;
    00283       }
    00284     }
    00285   }
    00286
    00287
    00288   /* Return Z_BUF_ERROR if we were given an incomplete table */
    00289   return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
    00290 }
    00291
    00292
    00293 int inflate_trees_bits(c, bb, tb, hp, z)
    00294 uIntf *c;               /* 19 code lengths */
    00295 uIntf *bb;              /* bits tree desired/actual depth */
    00296 inflate_huft * FAR *tb; /* bits tree result */
    00297 inflate_huft *hp;       /* space for trees */
    00298 z_streamp z;            /* for messages */
    00299 {
    00300   int r;
    00301   uInt hn = 0;          /* hufts used in space */
    00302   uIntf *v;             /* work area for huft_build */
    00303
    00304   if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL)
    00305     return Z_MEM_ERROR;
    00306   r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL,
    00307                  tb, bb, hp, &hn, v);
    00308   if (r == Z_DATA_ERROR)
    00309     z->msg = (char*)"oversubscribed dynamic bit lengths tree";
    00310   else if (r == Z_BUF_ERROR || *bb == 0)
    00311   {
    00312     z->msg = (char*)"incomplete dynamic bit lengths tree";
    00313     r = Z_DATA_ERROR;
    00314   }
    00315   ZFREE(z, v);
    00316   return r;
    00317 }
    00318
    00319
    00320 int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, hp, z)
    00321 uInt nl;                /* number of literal/length codes */
    00322 uInt nd;                /* number of distance codes */
    00323 uIntf *c;               /* that many (total) code lengths */
    00324 uIntf *bl;              /* literal desired/actual bit depth */
    00325 uIntf *bd;              /* distance desired/actual bit depth */
    00326 inflate_huft * FAR *tl; /* literal/length tree result */
    00327 inflate_huft * FAR *td; /* distance tree result */
    00328 inflate_huft *hp;       /* space for trees */
    00329 z_streamp z;            /* for messages */
    00330 {
    00331   int r;
    00332   uInt hn = 0;          /* hufts used in space */
    00333   uIntf *v;             /* work area for huft_build */
    00334
    00335   /* allocate work area */
    00336   if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
    00337     return Z_MEM_ERROR;
    00338
    00339   /* build literal/length tree */
    00340   r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
    00341   if (r != Z_OK || *bl == 0)
    00342   {
    00343     if (r == Z_DATA_ERROR)
    00344       z->msg = (char*)"oversubscribed literal/length tree";
    00345     else if (r != Z_MEM_ERROR)
    00346     {
    00347       z->msg = (char*)"incomplete literal/length tree";
    00348       r = Z_DATA_ERROR;
    00349     }
    00350     ZFREE(z, v);
    00351     return r;
    00352   }
    00353
    00354   /* build distance tree */
    00355   r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
    00356   if (r != Z_OK || (*bd == 0 && nl > 257))
    00357   {
    00358     if (r == Z_DATA_ERROR)
    00359       z->msg = (char*)"oversubscribed distance tree";
    00360     else if (r == Z_BUF_ERROR) {
    00361 #ifdef PKZIP_BUG_WORKAROUND
    00362       r = Z_OK;
    00363     }
    00364 #else
    00365       z->msg = (char*)"incomplete distance tree";
    00366       r = Z_DATA_ERROR;
    00367     }
    00368     else if (r != Z_MEM_ERROR)
    00369     {
    00370       z->msg = (char*)"empty distance tree with lengths";
    00371       r = Z_DATA_ERROR;
    00372     }
    00373     ZFREE(z, v);
    00374     return r;
    00375 #endif
    00376   }
    00377
    00378   /* done */
    00379   ZFREE(z, v);
    00380   return Z_OK;
    00381 }
    00382
    00383
    00384 /* build fixed tables only once--keep them here */
    00385 #ifdef BUILDFIXED
    00386 local int fixed_built = 0;
    00387 #define FIXEDH 544      /* number of hufts used by fixed tables */
    00388 local inflate_huft fixed_mem[FIXEDH];
    00389 local uInt fixed_bl;
    00390 local uInt fixed_bd;
    00391 local inflate_huft *fixed_tl;
    00392 local inflate_huft *fixed_td;
    00393 #else
    00394 #include "inffixed.h"
    00395 #endif
    00396
    00397
    00398 int inflate_trees_fixed(bl, bd, tl, td, z)
    00399 uIntf *bl;               /* literal desired/actual bit depth */
    00400 uIntf *bd;               /* distance desired/actual bit depth */
    00401 inflate_huft * FAR *tl;  /* literal/length tree result */
    00402 inflate_huft * FAR *td;  /* distance tree result */
    00403 z_streamp z;             /* for memory allocation */
    00404 {
    00405 #ifdef BUILDFIXED
    00406   /* build fixed tables if not already */
    00407   if (!fixed_built)
    00408   {
    00409     int k;              /* temporary variable */
    00410     uInt f = 0;         /* number of hufts used in fixed_mem */
    00411     uIntf *c;           /* length list for huft_build */
    00412     uIntf *v;           /* work area for huft_build */
    00413
    00414     /* allocate memory */
    00415     if ((c = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
    00416       return Z_MEM_ERROR;
    00417     if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
    00418     {
    00419       ZFREE(z, c);
    00420       return Z_MEM_ERROR;
    00421     }
    00422
    00423     /* literal table */
    00424     for (k = 0; k < 144; k++)
    00425       c[k] = 8;
    00426     for (; k < 256; k++)
    00427       c[k] = 9;
    00428     for (; k < 280; k++)
    00429       c[k] = 7;
    00430     for (; k < 288; k++)
    00431       c[k] = 8;
    00432     fixed_bl = 9;
    00433     huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl,
    00434                fixed_mem, &f, v);
    00435
    00436     /* distance table */
    00437     for (k = 0; k < 30; k++)
    00438       c[k] = 5;
    00439     fixed_bd = 5;
    00440     huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd,
    00441                fixed_mem, &f, v);
    00442
    00443     /* done */
    00444     ZFREE(z, v);
    00445     ZFREE(z, c);
    00446     fixed_built = 1;
    00447   }
    00448 #endif
    00449   *bl = fixed_bl;
    00450   *bd = fixed_bd;
    00451   *tl = fixed_tl;
    00452   *td = fixed_td;
    00453   return Z_OK;
    00454 }