Back to index

avfs  1.0.1
inftrees.c
Go to the documentation of this file.
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       {
00255         r.exop = 128 + 64;      /* out of values--invalid code */
00256         r.base = 0;
00257       }
00258       else if (*p < s)
00259       {
00260         r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);     /* 256 is end-of-block */
00261         r.base = *p++;          /* simple code is just the value */
00262       }
00263       else
00264       {
00265         r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */
00266         r.base = d[*p++ - s];
00267       }
00268 
00269       /* fill code-like entries with r */
00270       f = 1 << (k - w);
00271       for (j = i >> w; j < z; j += f)
00272         q[j] = r;
00273 
00274       /* backwards increment the k-bit code i */
00275       for (j = 1 << (k - 1); i & j; j >>= 1)
00276         i ^= j;
00277       i ^= j;
00278 
00279       /* backup over finished tables */
00280       mask = (1 << w) - 1;      /* needed on HP, cc -O bug */
00281       while ((i & mask) != x[h])
00282       {
00283         h--;                    /* don't need to update q */
00284         w -= l;
00285         mask = (1 << w) - 1;
00286       }
00287     }
00288   }
00289 
00290 
00291   /* Return Z_BUF_ERROR if we were given an incomplete table */
00292   return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
00293 }
00294 
00295 
00296 int inflate_trees_bits(c, bb, tb, hp, z)
00297 uIntf *c;               /* 19 code lengths */
00298 uIntf *bb;              /* bits tree desired/actual depth */
00299 inflate_huft * FAR *tb; /* bits tree result */
00300 inflate_huft *hp;       /* space for trees */
00301 z_streamp z;            /* for messages */
00302 {
00303   int r;
00304   uInt hn = 0;          /* hufts used in space */
00305   uIntf *v;             /* work area for huft_build */
00306 
00307   if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL)
00308     return Z_MEM_ERROR;
00309   r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL,
00310                  tb, bb, hp, &hn, v);
00311   if (r == Z_DATA_ERROR)
00312     z->msg = (char*)"oversubscribed dynamic bit lengths tree";
00313   else if (r == Z_BUF_ERROR || *bb == 0)
00314   {
00315     z->msg = (char*)"incomplete dynamic bit lengths tree";
00316     r = Z_DATA_ERROR;
00317   }
00318   ZFREE(z, v);
00319   return r;
00320 }
00321 
00322 
00323 int inflate_trees_dynamic(nl, nd, c, bl, bd, tl, td, hp, z)
00324 uInt nl;                /* number of literal/length codes */
00325 uInt nd;                /* number of distance codes */
00326 uIntf *c;               /* that many (total) code lengths */
00327 uIntf *bl;              /* literal desired/actual bit depth */
00328 uIntf *bd;              /* distance desired/actual bit depth */
00329 inflate_huft * FAR *tl; /* literal/length tree result */
00330 inflate_huft * FAR *td; /* distance tree result */
00331 inflate_huft *hp;       /* space for trees */
00332 z_streamp z;            /* for messages */
00333 {
00334   int r;
00335   uInt hn = 0;          /* hufts used in space */
00336   uIntf *v;             /* work area for huft_build */
00337 
00338   /* allocate work area */
00339   if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
00340     return Z_MEM_ERROR;
00341 
00342   /* build literal/length tree */
00343   r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
00344   if (r != Z_OK || *bl == 0)
00345   {
00346     if (r == Z_DATA_ERROR)
00347       z->msg = (char*)"oversubscribed literal/length tree";
00348     else if (r != Z_MEM_ERROR)
00349     {
00350       z->msg = (char*)"incomplete literal/length tree";
00351       r = Z_DATA_ERROR;
00352     }
00353     ZFREE(z, v);
00354     return r;
00355   }
00356 
00357   /* build distance tree */
00358   r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
00359   if (r != Z_OK || (*bd == 0 && nl > 257))
00360   {
00361     if (r == Z_DATA_ERROR)
00362       z->msg = (char*)"oversubscribed distance tree";
00363     else if (r == Z_BUF_ERROR) {
00364 #ifdef PKZIP_BUG_WORKAROUND
00365       r = Z_OK;
00366     }
00367 #else
00368       z->msg = (char*)"incomplete distance tree";
00369       r = Z_DATA_ERROR;
00370     }
00371     else if (r != Z_MEM_ERROR)
00372     {
00373       z->msg = (char*)"empty distance tree with lengths";
00374       r = Z_DATA_ERROR;
00375     }
00376     ZFREE(z, v);
00377     return r;
00378 #endif
00379   }
00380 
00381   /* done */
00382   ZFREE(z, v);
00383   return Z_OK;
00384 }
00385 
00386 
00387 /* build fixed tables only once--keep them here */
00388 #ifdef BUILDFIXED
00389 local int fixed_built = 0;
00390 #define FIXEDH 544      /* number of hufts used by fixed tables */
00391 local inflate_huft fixed_mem[FIXEDH];
00392 local uInt fixed_bl;
00393 local uInt fixed_bd;
00394 local inflate_huft *fixed_tl;
00395 local inflate_huft *fixed_td;
00396 #else
00397 #include "inffixed.h"
00398 #endif
00399 
00400 
00401 int inflate_trees_fixed(bl, bd, tl, td, z)
00402 uIntf *bl;               /* literal desired/actual bit depth */
00403 uIntf *bd;               /* distance desired/actual bit depth */
00404 inflate_huft * FAR *tl;  /* literal/length tree result */
00405 inflate_huft * FAR *td;  /* distance tree result */
00406 z_streamp z;             /* for memory allocation */
00407 {
00408 #ifdef BUILDFIXED
00409   /* build fixed tables if not already */
00410   if (!fixed_built)
00411   {
00412     int k;              /* temporary variable */
00413     uInt f = 0;         /* number of hufts used in fixed_mem */
00414     uIntf *c;           /* length list for huft_build */
00415     uIntf *v;           /* work area for huft_build */
00416 
00417     /* allocate memory */
00418     if ((c = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
00419       return Z_MEM_ERROR;
00420     if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
00421     {
00422       ZFREE(z, c);
00423       return Z_MEM_ERROR;
00424     }
00425 
00426     /* literal table */
00427     for (k = 0; k < 144; k++)
00428       c[k] = 8;
00429     for (; k < 256; k++)
00430       c[k] = 9;
00431     for (; k < 280; k++)
00432       c[k] = 7;
00433     for (; k < 288; k++)
00434       c[k] = 8;
00435     fixed_bl = 9;
00436     huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl,
00437                fixed_mem, &f, v);
00438 
00439     /* distance table */
00440     for (k = 0; k < 30; k++)
00441       c[k] = 5;
00442     fixed_bd = 5;
00443     huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd,
00444                fixed_mem, &f, v);
00445 
00446     /* done */
00447     ZFREE(z, v);
00448     ZFREE(z, c);
00449     fixed_built = 1;
00450   }
00451 #endif
00452   *bl = fixed_bl;
00453   *bd = fixed_bd;
00454   *tl = fixed_tl;
00455   *td = fixed_td;
00456   return Z_OK;
00457 }