src/utilfuns/zlib/inftrees.c File Reference

#include "zutil.h"
#include "inftrees.h"
Include dependency graph for inftrees.c:

Go to the source code of this file.

Classes

struct  internal_state

Defines

#define bits   word.what.Bits
#define BMAX   15
#define BUILDFIXED
#define C0   *p++ = 0;
#define C2   C0 C0 C0 C0
#define C4   C2 C2 C2 C2
#define exop   word.what.Exop
#define FIXEDH   544

Functions

local int huft_build (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)
int inflate_trees_bits (uIntf *c, uIntf *bb, inflate_huft *FAR *tb, inflate_huft *hp, z_streamp z)
int inflate_trees_dynamic (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 inflate_trees_fixed (uIntf *bl, uIntf *bd, inflate_huft *FAR *tl, inflate_huft *FAR *td, z_streamp z)
local int huft_build OF ((uIntf *, uInt, uInt, const uIntf *, const uIntf *, inflate_huft *FAR *, uIntf *, inflate_huft *, uInt *, uIntf *))

Variables

local const uInt cpdext [30]
local const uInt cpdist [30]
local const uInt cplens [31]
local const uInt cplext [31]
local uInt fixed_bd
local uInt fixed_bl
local int fixed_built = 0
local inflate_huft fixed_mem [FIXEDH]
local inflate_huftfixed_td
local inflate_huftfixed_tl
const char inflate_copyright []

Define Documentation

#define bits   word.what.Bits

Definition at line 25 of file inftrees.c.

#define BMAX   15

Definition at line 91 of file inftrees.c.

#define BUILDFIXED

Definition at line 10 of file inftrees.c.

#define C0   *p++ = 0;
#define C2   C0 C0 C0 C0
#define C4   C2 C2 C2 C2
#define exop   word.what.Exop

Definition at line 24 of file inftrees.c.

#define FIXEDH   544

Definition at line 387 of file inftrees.c.


Function Documentation

local int huft_build ( 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 
)

Definition at line 93 of file inftrees.c.

00099                                  : 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 }

int inflate_trees_bits ( uIntf c,
uIntf bb,
inflate_huft * FAR *  tb,
inflate_huft hp,
z_streamp  z 
)

Definition at line 293 of file inftrees.c.

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 }

int inflate_trees_dynamic ( uInt  nl,
uInt  nd,
uIntf c,
uIntf bl,
uIntf bd,
inflate_huft * FAR *  tl,
inflate_huft * FAR *  td,
inflate_huft hp,
z_streamp  z 
)

Definition at line 320 of file inftrees.c.

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 }

int inflate_trees_fixed ( uIntf bl,
uIntf bd,
inflate_huft * FAR *  tl,
inflate_huft * FAR *  td,
z_streamp  z 
)

Definition at line 398 of file inftrees.c.

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 }

local int huft_build OF ( (uIntf *, uInt, uInt, const uIntf *, const uIntf *, inflate_huft *FAR *, uIntf *, inflate_huft *, uInt *, uIntf *)   ) 

Variable Documentation

local const uInt cpdext[30]
Initial value:
 { 
        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}

Definition at line 52 of file inftrees.c.

local const uInt cpdist[30]
Initial value:
 { 
        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}

Definition at line 48 of file inftrees.c.

local const uInt cplens[31]
Initial value:
 { 
        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}

Definition at line 41 of file inftrees.c.

local const uInt cplext[31]
Initial value:
 { 
        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}

Definition at line 45 of file inftrees.c.

local uInt fixed_bd

Definition at line 390 of file inftrees.c.

local uInt fixed_bl

Definition at line 389 of file inftrees.c.

local int fixed_built = 0

Definition at line 386 of file inftrees.c.

local inflate_huft fixed_mem[FIXEDH]

Definition at line 388 of file inftrees.c.

Definition at line 392 of file inftrees.c.

Definition at line 391 of file inftrees.c.

const char inflate_copyright[]
Initial value:
   " inflate 1.1.4 Copyright 1995-2002 Mark Adler "

Definition at line 13 of file inftrees.c.


Generated on 18 Mar 2013 for The SWORD Project by  doxygen 1.6.1