sl@0: /* inftrees.c -- generate Huffman trees for efficient decoding
sl@0:  * Copyright (C) 1995-1998 Mark Adler
sl@0:  * For conditions of distribution and use, see copyright notice in zlib.h 
sl@0:  */
sl@0: 
sl@0: #include "zutil.h"
sl@0: #include "inftrees.h"
sl@0: 
sl@0: #if !defined(BUILDFIXED) && !defined(STDC)
sl@0: #  define BUILDFIXED   /* non ANSI compilers may not accept inffixed.h */
sl@0: #endif
sl@0: 
sl@0: const char inflate_copyright[] =
sl@0:    " inflate 1.1.3 Copyright 1995-1998 Mark Adler ";
sl@0: /*
sl@0:   If you use the zlib library in a product, an acknowledgment is welcome
sl@0:   in the documentation of your product. If for some reason you cannot
sl@0:   include such an acknowledgment, I would appreciate that you keep this
sl@0:   copyright string in the executable of your product.
sl@0:  */
sl@0: struct internal_state  {int dummy;}; /* for buggy compilers */
sl@0: 
sl@0: /* simplify the use of the inflate_huft type with some defines */
sl@0: #define exop word.what.Exop
sl@0: #define bits word.what.Bits
sl@0: 
sl@0: 
sl@0: local int huft_build OF((
sl@0:     uIntf *,            /* code lengths in bits */
sl@0:     uInt,               /* number of codes */
sl@0:     uInt,               /* number of "simple" codes */
sl@0:     const uIntf *,      /* list of base values for non-simple codes */
sl@0:     const uIntf *,      /* list of extra bits for non-simple codes */
sl@0:     inflate_huft * FAR*,/* result: starting table */
sl@0:     uIntf *,            /* maximum lookup bits (returns actual) */
sl@0:     inflate_huft *,     /* space for trees */
sl@0:     uInt *,             /* hufts used in space */
sl@0:     uIntf * ));         /* space for values */
sl@0: 
sl@0: /* Tables for deflate from PKZIP's appnote.txt. */
sl@0: local const uInt cplens[31] = { /* Copy lengths for literal codes 257..285 */
sl@0:         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
sl@0:         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
sl@0:         /* see note #13 above about 258 */
sl@0: local const uInt cplext[31] = { /* Extra bits for literal codes 257..285 */
sl@0:         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
sl@0:         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 112, 112}; /* 112==invalid */
sl@0: local const uInt cpdist[30] = { /* Copy offsets for distance codes 0..29 */
sl@0:         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
sl@0:         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
sl@0:         8193, 12289, 16385, 24577};
sl@0: local const uInt cpdext[30] = { /* Extra bits for distance codes */
sl@0:         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
sl@0:         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
sl@0:         12, 12, 13, 13};
sl@0: 
sl@0: /*
sl@0:    Huffman code decoding is performed using a multi-level table lookup.
sl@0:    The fastest way to decode is to simply build a lookup table whose
sl@0:    size is determined by the longest code.  However, the time it takes
sl@0:    to build this table can also be a factor if the data being decoded
sl@0:    is not very long.  The most common codes are necessarily the
sl@0:    shortest codes, so those codes dominate the decoding time, and hence
sl@0:    the speed.  The idea is you can have a shorter table that decodes the
sl@0:    shorter, more probable codes, and then point to subsidiary tables for
sl@0:    the longer codes.  The time it costs to decode the longer codes is
sl@0:    then traded against the time it takes to make longer tables.
sl@0: 
sl@0:    This results of this trade are in the variables lbits and dbits
sl@0:    below.  lbits is the number of bits the first level table for literal/
sl@0:    length codes can decode in one step, and dbits is the same thing for
sl@0:    the distance codes.  Subsequent tables are also less than or equal to
sl@0:    those sizes.  These values may be adjusted either when all of the
sl@0:    codes are shorter than that, in which case the longest code length in
sl@0:    bits is used, or when the shortest code is *longer* than the requested
sl@0:    table size, in which case the length of the shortest code in bits is
sl@0:    used.
sl@0: 
sl@0:    There are two different values for the two tables, since they code a
sl@0:    different number of possibilities each.  The literal/length table
sl@0:    codes 286 possible values, or in a flat code, a little over eight
sl@0:    bits.  The distance table codes 30 possible values, or a little less
sl@0:    than five bits, flat.  The optimum values for speed end up being
sl@0:    about one bit more than those, so lbits is 8+1 and dbits is 5+1.
sl@0:    The optimum values may differ though from machine to machine, and
sl@0:    possibly even between compilers.  Your mileage may vary.
sl@0:  */
sl@0: 
sl@0: 
sl@0: /* If BMAX needs to be larger than 16, then h and x[] should be uLong. */
sl@0: #define BMAX 15         /* maximum bit length of any code */
sl@0: 
sl@0: 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)
sl@0: /* uIntf *b;                code lengths in bits (all assumed <= BMAX) */
sl@0: /* uInt n;                  number of codes (assumed <= 288) */
sl@0: /* uInt s;                  number of simple-valued codes (0..s-1) */
sl@0: /* const uIntf *d;          list of base values for non-simple codes */
sl@0: /* const uIntf *e;          list of extra bits for non-simple codes */
sl@0: /* inflate_huft * FAR *t;   result: starting table */
sl@0: /* uIntf *m;                maximum lookup bits, returns actual */
sl@0: /* inflate_huft *hp;        space for trees */
sl@0: /* uInt *hn;                hufts used in space */
sl@0: /* uIntf *v;                working area: values in order of bit length */
sl@0: 
sl@0: /* Given a list of code lengths and a maximum table size, make a set of
sl@0:    tables to decode that set of codes.  Return Z_OK on success, Z_BUF_ERROR
sl@0:    if the given code set is incomplete (the tables are still built in this
sl@0:    case), Z_DATA_ERROR if the input is invalid (an over-subscribed set of
sl@0:    lengths), or Z_MEM_ERROR if not enough memory. */
sl@0: {
sl@0: 
sl@0:   uInt a;                       /* counter for codes of length k */
sl@0:   uInt c[BMAX+1];               /* bit length count table */
sl@0:   uInt f;                       /* i repeats in table every f entries */
sl@0:   int g;                        /* maximum code length */
sl@0:   int h;                        /* table level */
sl@0:   register uInt i;              /* counter, current code */
sl@0:   register uInt j;              /* counter */
sl@0:   register int k;               /* number of bits in current code */
sl@0:   int l;                        /* bits per table (returned in m) */
sl@0:   uInt mask;                    /* (1 << w) - 1, to avoid cc -O bug on HP */
sl@0:   register uIntf *p;            /* pointer into c[], b[], or v[] */
sl@0:   inflate_huft *q;              /* points to current table */
sl@0:   struct inflate_huft_s r;      /* table entry for structure assignment */
sl@0:   inflate_huft *u[BMAX];        /* table stack */
sl@0:   register int w;               /* bits before this table == (l * h) */
sl@0:   uInt x[BMAX+1];               /* bit offsets, then code stack */
sl@0:   uIntf *xp;                    /* pointer into x */
sl@0:   int y;                        /* number of dummy codes added */
sl@0:   uInt z;                       /* number of entries in current table */
sl@0: 
sl@0: 
sl@0:   /* Generate counts for each bit length */
sl@0:   p = c;
sl@0: #define C0 *p++ = 0;
sl@0: #define C2 C0 C0 C0 C0
sl@0: #define C4 C2 C2 C2 C2
sl@0:   C4                            /* clear c[]--assume BMAX+1 is 16 */
sl@0:   p = b;  i = n;
sl@0:   do {
sl@0:     c[*p++]++;                  /* assume all entries <= BMAX */
sl@0:   } while (--i);
sl@0:   if (c[0] == n)                /* null input--all zero length codes */
sl@0:   {
sl@0:     *t = (inflate_huft *)Z_NULL;
sl@0:     *m = 0;
sl@0:     return Z_OK;
sl@0:   }
sl@0: 
sl@0: 
sl@0:   /* Find minimum and maximum length, bound *m by those */
sl@0:   l = *m;
sl@0:   for (j = 1; j <= BMAX; j++)
sl@0:     if (c[j])
sl@0:       break;
sl@0:   k = j;                        /* minimum code length */
sl@0:   if ((uInt)l < j)
sl@0:     l = j;
sl@0:   for (i = BMAX; i; i--)
sl@0:     if (c[i])
sl@0:       break;
sl@0:   g = i;                        /* maximum code length */
sl@0:   if ((uInt)l > i)
sl@0:     l = i;
sl@0:   *m = l;
sl@0: 
sl@0: 
sl@0:   /* Adjust last length count to fill out codes, if needed */
sl@0:   for (y = 1 << j; j < i; j++, y <<= 1)
sl@0:     if ((y -= c[j]) < 0)
sl@0:       return Z_DATA_ERROR;
sl@0:   if ((y -= c[i]) < 0)
sl@0:     return Z_DATA_ERROR;
sl@0:   c[i] += y;
sl@0: 
sl@0: 
sl@0:   /* Generate starting offsets into the value table for each length */
sl@0:   x[1] = j = 0;
sl@0:   p = c + 1;  xp = x + 2;
sl@0:   while (--i) {                 /* note that i == g from above */
sl@0:     *xp++ = (j += *p++);
sl@0:   }
sl@0: 
sl@0: 
sl@0:   /* Make a table of values in order of bit lengths */
sl@0:   p = b;  i = 0;
sl@0:   do {
sl@0:     if ((j = *p++) != 0)
sl@0:       v[x[j]++] = i;
sl@0:   } while (++i < n);
sl@0:   n = x[g];                     /* set n to length of v */
sl@0: 
sl@0: 
sl@0:   /* Generate the Huffman codes and for each, make the table entries */
sl@0:   x[0] = i = 0;                 /* first Huffman code is zero */
sl@0:   p = v;                        /* grab values in bit order */
sl@0:   h = -1;                       /* no tables yet--level -1 */
sl@0:   w = -l;                       /* bits decoded == (l * h) */
sl@0:   u[0] = (inflate_huft *)Z_NULL;        /* just to keep compilers happy */
sl@0:   q = (inflate_huft *)Z_NULL;   /* ditto */
sl@0:   z = 0;                        /* ditto */
sl@0: 
sl@0:   /* go through the bit lengths (k already is bits in shortest code) */
sl@0:   for (; k <= g; k++)
sl@0:   {
sl@0:     a = c[k];
sl@0:     while (a--)
sl@0:     {
sl@0:       /* here i is the Huffman code of length k bits for value *p */
sl@0:       /* make tables up to required level */
sl@0:       while (k > w + l)
sl@0:       {
sl@0:         h++;
sl@0:         w += l;                 /* previous table always l bits */
sl@0: 
sl@0:         /* compute minimum size table less than or equal to l bits */
sl@0:         z = g - w;
sl@0:         z = z > (uInt)l ? l : z;        /* table size upper limit */
sl@0:         if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
sl@0:         {                       /* too few codes for k-w bit table */
sl@0:           f -= a + 1;           /* deduct codes from patterns left */
sl@0:           xp = c + k;
sl@0:           if (j < z)
sl@0:             while (++j < z)     /* try smaller tables up to z bits */
sl@0:             {
sl@0:               if ((f <<= 1) <= *++xp)
sl@0:                 break;          /* enough codes to use up j bits */
sl@0:               f -= *xp;         /* else deduct codes from patterns */
sl@0:             }
sl@0:         }
sl@0:         z = 1 << j;             /* table entries for j-bit table */
sl@0: 
sl@0:         /* allocate new table */
sl@0:         if (*hn + z > MANY)     /* (note: doesn't matter for fixed) */
sl@0:           return Z_MEM_ERROR;   /* not enough memory */
sl@0:         u[h] = q = hp + *hn;
sl@0:         *hn += z;
sl@0: 
sl@0:         /* connect to last table, if there is one */
sl@0:         if (h)
sl@0:         {
sl@0:           x[h] = i;             /* save pattern for backing up */
sl@0:           r.bits = (Byte)l;     /* bits to dump before this table */
sl@0:           r.exop = (Byte)j;     /* bits in this table */
sl@0:           j = i >> (w - l);
sl@0:           r.base = (uInt)(q - u[h-1] - j);   /* offset to this table */
sl@0:           u[h-1][j] = r;        /* connect to last table */
sl@0:         }
sl@0:         else
sl@0:           *t = q;               /* first table is returned result */
sl@0:       }
sl@0: 
sl@0:       /* set up table entry in r */
sl@0:       r.bits = (Byte)(k - w);
sl@0:       if (p >= v + n)
sl@0:         r.exop = 128 + 64;      /* out of values--invalid code */
sl@0:       else if (*p < s)
sl@0:       {
sl@0:         r.exop = (Byte)(*p < 256 ? 0 : 32 + 64);     /* 256 is end-of-block */
sl@0:         r.base = *p++;          /* simple code is just the value */
sl@0:       }
sl@0:       else
sl@0:       {
sl@0:         r.exop = (Byte)(e[*p - s] + 16 + 64);/* non-simple--look up in lists */
sl@0:         r.base = d[*p++ - s];
sl@0:       }
sl@0: 
sl@0:       /* fill code-like entries with r */
sl@0:       f = 1 << (k - w);
sl@0:       for (j = i >> w; j < z; j += f)
sl@0:         q[j] = r;
sl@0: 
sl@0:       /* backwards increment the k-bit code i */
sl@0:       for (j = 1 << (k - 1); i & j; j >>= 1)
sl@0:         i ^= j;
sl@0:       i ^= j;
sl@0: 
sl@0:       /* backup over finished tables */
sl@0:       mask = (1 << w) - 1;      /* needed on HP, cc -O bug */
sl@0:       while ((i & mask) != x[h])
sl@0:       {
sl@0:         h--;                    /* don't need to update q */
sl@0:         w -= l;
sl@0:         mask = (1 << w) - 1;
sl@0:       }
sl@0:     }
sl@0:   }
sl@0: 
sl@0: 
sl@0:   /* Return Z_BUF_ERROR if we were given an incomplete table */
sl@0:   return y != 0 && g != 1 ? Z_BUF_ERROR : Z_OK;
sl@0: }
sl@0: 
sl@0: 
sl@0: int inflate_trees_bits(uIntf *c, uIntf *bb, inflate_huft * FAR *tb, inflate_huft *hp, z_streamp z)
sl@0: /* uIntf *c;                19 code lengths */
sl@0: /* uIntf *bb;               bits tree desired/actual depth */
sl@0: /* inflate_huft * FAR *tb;  bits tree result */
sl@0: /* inflate_huft *hp;        space for trees */
sl@0: /* z_streamp z;             for messages */
sl@0: 
sl@0: 
sl@0: {
sl@0:   int r;
sl@0:   uInt hn = 0;          /* hufts used in space */
sl@0:   uIntf *v;             /* work area for huft_build */
sl@0: 
sl@0:   if ((v = (uIntf*)ZALLOC(z, 19, sizeof(uInt))) == Z_NULL)
sl@0:     return Z_MEM_ERROR;
sl@0:   r = huft_build(c, 19, 19, (uIntf*)Z_NULL, (uIntf*)Z_NULL,
sl@0:                  tb, bb, hp, &hn, v);
sl@0:   if (r == Z_DATA_ERROR)
sl@0:     z->msg = (char*)"oversubscribed dynamic bit lengths tree";
sl@0:   else if (r == Z_BUF_ERROR || *bb == 0)
sl@0:   {
sl@0:     z->msg = (char*)"incomplete dynamic bit lengths tree";
sl@0:     r = Z_DATA_ERROR;
sl@0:   }
sl@0:   ZFREE(z, v);
sl@0:   return r;
sl@0: }
sl@0: 
sl@0: 
sl@0: 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)
sl@0: /* uInt nl;                 number of literal/length codes */
sl@0: /* uInt nd;                 number of distance codes */
sl@0: /* uIntf *c;                that many (total) code lengths */
sl@0: /* uIntf *bl;               literal desired/actual bit depth */
sl@0: /* uIntf *bd;               distance desired/actual bit depth */
sl@0: /* inflate_huft * FAR *tl;  literal/length tree result */
sl@0: /* inflate_huft * FAR *td;  distance tree result */
sl@0: /* inflate_huft *hp;        space for trees */
sl@0: /* z_streamp z;             for messages */
sl@0: 
sl@0: 
sl@0: {
sl@0:   int r;
sl@0:   uInt hn = 0;          /* hufts used in space */
sl@0:   uIntf *v;             /* work area for huft_build */
sl@0: 
sl@0:   /* allocate work area */
sl@0:   if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
sl@0:     return Z_MEM_ERROR;
sl@0: 
sl@0:   /* build literal/length tree */
sl@0:   r = huft_build(c, nl, 257, cplens, cplext, tl, bl, hp, &hn, v);
sl@0:   if (r != Z_OK || *bl == 0)
sl@0:   {
sl@0:     if (r == Z_DATA_ERROR)
sl@0:       z->msg = (char*)"oversubscribed literal/length tree";
sl@0:     else if (r != Z_MEM_ERROR)
sl@0:     {
sl@0:       z->msg = (char*)"incomplete literal/length tree";
sl@0:       r = Z_DATA_ERROR;
sl@0:     }
sl@0:     ZFREE(z, v);
sl@0:     return r;
sl@0:   }
sl@0: 
sl@0:   /* build distance tree */
sl@0:   r = huft_build(c + nl, nd, 0, cpdist, cpdext, td, bd, hp, &hn, v);
sl@0:   if (r != Z_OK || (*bd == 0 && nl > 257))
sl@0:   {
sl@0:     if (r == Z_DATA_ERROR)
sl@0:       z->msg = (char*)"oversubscribed distance tree";
sl@0:     else if (r == Z_BUF_ERROR) {
sl@0: #ifdef PKZIP_BUG_WORKAROUND
sl@0:       r = Z_OK;
sl@0:     }
sl@0: #else
sl@0:       z->msg = (char*)"incomplete distance tree";
sl@0:       r = Z_DATA_ERROR;
sl@0:     }
sl@0:     else if (r != Z_MEM_ERROR)
sl@0:     {
sl@0:       z->msg = (char*)"empty distance tree with lengths";
sl@0:       r = Z_DATA_ERROR;
sl@0:     }
sl@0:     ZFREE(z, v);
sl@0:     return r;
sl@0: #endif
sl@0:   }
sl@0: 
sl@0:   /* done */
sl@0:   ZFREE(z, v);
sl@0:   return Z_OK;
sl@0: }
sl@0: 
sl@0: 
sl@0: /* build fixed tables only once--keep them here */
sl@0: #ifdef BUILDFIXED
sl@0: local int fixed_built = 0;
sl@0: #define FIXEDH 544      /* number of hufts used by fixed tables */
sl@0: local inflate_huft fixed_mem[FIXEDH];
sl@0: local uInt fixed_bl;
sl@0: local uInt fixed_bd;
sl@0: local inflate_huft *fixed_tl;
sl@0: local inflate_huft *fixed_td;
sl@0: #else
sl@0: #include "inffixed.h"
sl@0: #endif
sl@0: 
sl@0: int inflate_trees_fixed(uIntf *bl, uIntf *bd, inflate_huft * FAR *tl, inflate_huft * FAR *td, z_streamp z)
sl@0: /* uIntf *bl;                literal desired/actual bit depth */
sl@0: /* uIntf *bd;                distance desired/actual bit depth */
sl@0: /* inflate_huft * FAR *tl;   literal/length tree result */
sl@0: /* inflate_huft * FAR *td;   distance tree result */
sl@0: /* z_streamp z;              for memory allocation */
sl@0: {
sl@0: #ifdef BUILDFIXED
sl@0:   /* build fixed tables if not already */
sl@0:   if (!fixed_built)
sl@0:   {
sl@0:     int k;              /* temporary variable */
sl@0:     uInt f = 0;         /* number of hufts used in fixed_mem */
sl@0:     uIntf *c;           /* length list for huft_build */
sl@0:     uIntf *v;           /* work area for huft_build */
sl@0: 
sl@0:     /* allocate memory */
sl@0:     if ((c = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
sl@0:       return Z_MEM_ERROR;
sl@0:     if ((v = (uIntf*)ZALLOC(z, 288, sizeof(uInt))) == Z_NULL)
sl@0:     {
sl@0:       ZFREE(z, c);
sl@0:       return Z_MEM_ERROR;
sl@0:     }
sl@0: 
sl@0:     /* literal table */
sl@0:     for (k = 0; k < 144; k++)
sl@0:       c[k] = 8;
sl@0:     for (; k < 256; k++)
sl@0:       c[k] = 9;
sl@0:     for (; k < 280; k++)
sl@0:       c[k] = 7;
sl@0:     for (; k < 288; k++)
sl@0:       c[k] = 8;
sl@0:     fixed_bl = 9;
sl@0:     huft_build(c, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl,
sl@0:                fixed_mem, &f, v);
sl@0: 
sl@0:     /* distance table */
sl@0:     for (k = 0; k < 30; k++)
sl@0:       c[k] = 5;
sl@0:     fixed_bd = 5;
sl@0:     huft_build(c, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd,
sl@0:                fixed_mem, &f, v);
sl@0: 
sl@0:     /* done */
sl@0:     ZFREE(z, v);
sl@0:     ZFREE(z, c);
sl@0:     fixed_built = 1;
sl@0:   }
sl@0: #endif
sl@0:   *bl = fixed_bl;
sl@0:   *bd = fixed_bd;
sl@0:   *tl = fixed_tl;
sl@0:   *td = fixed_td;
sl@0:   z->data_type = z->data_type; /* Here to prevent TOOLS2 warning about z being unused. */  
sl@0:   return Z_OK;
sl@0: }