Back to index

plt-scheme  4.2.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         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 }