inflate.c

空战游戏flacon源码

               goes ok.

   ======================================================= */

int huft_build( unsigned * b, unsigned n, unsigned s, ush * d, ush * e, struct huft ** t, int * m )
{
  unsigned a;                   /* counter for codes of length k */
  unsigned c[BMAX+1];           /* bit length count table */
  unsigned el;                  /* length of EOB code (value 256) */
  unsigned f;                   /* i repeats in table every f entries */
  int g;                        /* maximum code length */
  int h;                        /* table level */
  register unsigned i;          /* counter, current code */
  register unsigned j;          /* counter */
  register int k;               /* number of bits in current code */
  int lx[BMAX+1];               /* memory for l[-1..BMAX-1] */
  int *l = lx+1;                /* stack of bits per table */
  register unsigned *p;         /* pointer into c[], b[], or v[] */
  register struct huft *q;      /* points to current table */
  struct huft r;                /* table entry for structure assignment */
  struct huft *u[BMAX];         /* table stack */
  static unsigned v[N_MAX];     /* values in order of bit length */
  register int w;               /* bits before this table == (l * h) */
  unsigned x[BMAX+1];           /* bit offsets, then code stack */
  unsigned *xp;                 /* pointer into x */
  int y;                        /* number of dummy codes added */
  unsigned z;                   /* number of entries in current table */


  /* Generate counts for each bit length */
  el = n > 256 ? b[256] : BMAX; /* set length of EOB code, if any */
  memzero((char *)c, sizeof(c));
  p = b;  i = n;
  do {
    c[*p]++; p++;               /* assume all entries <= BMAX */
  } while (--i);
  if (c[0] == n)                /* null input--all zero length codes */
  {
    *t = (struct huft *)NULL;
    *m = 0;
    return 0;
  }


  /* Find minimum and maximum length, bound *m by those */
  for (j = 1; j <= BMAX; j++)
    if (c[j])
      break;
  k = j;                        /* minimum code length */
  if ((unsigned)*m < j)
    *m = j;
  for (i = BMAX; i; i--)
    if (c[i])
      break;
  g = i;                        /* maximum code length */
  if ((unsigned)*m > i)
    *m = i;


  /* Adjust last length count to fill out codes, if needed */
  for (y = 1 << j; j < i; j++, y <<= 1)
    if ((y -= c[j]) < 0)
      return 2;                 /* bad input: more codes than bits */
  if ((y -= c[i]) < 0)
    return 2;
  c[i] += y;


  /* Generate starting offsets into the value table for each length */
  x[1] = j = 0;
  p = c + 1;  xp = x + 2;
  while (--i) {                 /* note that i == g from above */
    *xp++ = (j += *p++);
  }


  /* Make a table of values in order of bit lengths */
  p = b;  i = 0;
  do {
    if ((j = *p++) != 0)
      v[x[j]++] = i;
  } while (++i < n);


  /* Generate the Huffman codes and for each, make the table entries */
  x[0] = i = 0;                 /* first Huffman code is zero */
  p = v;                        /* grab values in bit order */
  h = -1;                       /* no tables yet--level -1 */
  w = l[-1] = 0;                /* no bits decoded yet */
  u[0] = (struct huft *)NULL;   /* just to keep compilers happy */
  q = (struct huft *)NULL;      /* ditto */
  z = 0;                        /* ditto */

  /* go through the bit lengths (k already is bits in shortest code) */
  for (; k <= g; k++)
  {
    a = c[k];
    while (a--)
    {
      /* here i is the Huffman code of length k bits for value *p */
      /* make tables up to required level */
      while (k > w + l[h])
      {
        w += l[h++];            /* add bits already decoded */

        /* compute minimum size table less than or equal to *m bits */
        z = (z = g - w) > (unsigned)*m ? *m : z;        /* upper limit */
        if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
        {                       /* too few codes for k-w bit table */
          f -= a + 1;           /* deduct codes from patterns left */
          xp = c + k;
          while (++j < z)       /* try smaller tables up to z bits */
          {
            if ((f <<= 1) <= *++xp)
              break;            /* enough codes to use up j bits */
            f -= *xp;           /* else deduct codes from patterns */
          }
        }
        if (w + j > el && (unsigned)w < el)
          j = el - w;           /* make EOB code end at table */
        z = 1 << j;             /* table entries for j-bit table */
        l[h] = j;               /* set table size in stack */

        /* allocate and link in new table */
		#ifdef USE_SH_POOLS
        if ((q = (struct huft *)MemAllocPtr(gResmgrMemPool, (z + 1)*sizeof(struct huft), 0)) ==
            (struct huft *)NULL)
        {
          if (h)
            huft_free(u[0]);
          return 3;             /* not enough memory */
        }
		#else
        if ((q = (struct huft *)MemMalloc((z + 1)*sizeof(struct huft), "huft")) ==
            (struct huft *)NULL)
        {
          if (h)
            huft_free(u[0]);
          return 3;             /* not enough memory */
        }
		#endif
        hufts += z + 1;         /* track memory usage */
        *t = q + 1;             /* link to list for huft_free() */
        *(t = &(q->v.t)) = (struct huft *)NULL;
        u[h] = ++q;             /* table starts after link */

        /* connect to last table, if there is one */
        if (h)
        {
          x[h] = i;             /* save pattern for backing up */
          r.b = (uch)l[h-1];    /* bits to dump before this table */
          r.e = (uch)(16 + j);  /* bits in this table */
          r.v.t = q;            /* pointer to this table */
          j = (i & ((1 << w) - 1)) >> (w - l[h-1]);
          u[h-1][j] = r;        /* connect to last table */
        }
      }

      /* set up table entry in r */
      r.b = (uch)(k - w);
      if (p >= v + n)
        r.e = 99;               /* out of values--invalid code */
      else if (*p < s)
      {
        r.e = (uch)(*p < 256 ? 16 : 15);    /* 256 is end-of-block code */
        r.v.n = (ush)*p++;           /* simple code is just the value */
      }
      else
      {
        r.e = (uch)e[*p - s];   /* non-simple--look up in lists */
        r.v.n = d[*p++ - s];
      }

      /* fill code-like entries with r */
      f = 1 << (k - w);
      for (j = i >> w; j < z; j += f)
        q[j] = r;

      /* backwards increment the k-bit code i */
      for (j = 1 << (k - 1); i & j; j >>= 1)
        i ^= j;
      i ^= j;

      /* backup over finished tables */
      while ((i & ((1 << w) - 1)) != x[h])
        w -= l[--h];            /* don't need to update q */
    }
  }


  /* return actual size of base table */
  *m = l[0];


  /* Return true (1) if we were given an incomplete table */
  return y != 0 && g != 1;
}



/* =======================================================

   FUNCTION:   huft_free()

   PURPOSE:    Free the allocated tables built by 
               huft_build(), which makes a linked list of 
               the tables it made, with the links in a 
               dummy first entry of each table.
               
   PARAMETERS: Ptr to huffman tree

   RETURNS:    Return an error code or zero if it all 
               goes ok.

   ======================================================= */

int huft_free( struct huft * t )
{
    register struct huft *p, *q;

    /* Go through linked list, freeing from the malloced (t[-1]) address. */

    p = t;

    while( p != (struct huft *)NULL )
    {
        q = (--p)->v.t;
		#ifdef USE_SH_POOLS
        MemFreePtr(p);
		#else
        MemFree(p);
		#endif
        p = q;
    }

    return 0;
}




/* =======================================================

   FUNCTION:   inflate_codes()

   PURPOSE:    Inflate (decompress) the codes in a 
               deflated (compressed) block. 
               
   PARAMETERS: Ptr to compressed file wrapper.

   RETURNS:    Return an error code or zero if it all 
               goes ok.

   ======================================================= */

int inflate_codes( struct huft * tl, struct huft * td, int bl, int bd, COMPRESSED_FILE * cmp )
{
    register unsigned e;        /* table entry flag/number of extra bits */
    unsigned n,
             d;                    /* length and index for copy */
    unsigned w;                 /* current window position */
    struct huft *t;             /* pointer to table entry */
    unsigned ml,
             md;                   /* masks for bl and bd bits */
    register ulg b;             /* bit buffer */
    register unsigned k;        /* number of bits in bit buffer */


    /* make local copies of globals */
    b = cmp->bb;                /* initialize bit buffer */
    k = cmp->bk;
    w = cmp->wp;                /* initialize window position */


    /* inflate the coded data */
    ml = mask[bl];              /* precompute masks for speed */
    md = mask[bd];
    while (TRUE)                /* do until end of block */
    {
        NEEDBITS((unsigned)bl)
        if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
        do
        {
            if (e == 99)
                return 1;
            DUMPBITS(t->b)
            e -= 16;
            NEEDBITS(e)
        }

        while((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16) ;

        DUMPBITS(t->b)

        if (e == 16)        /* then it's a literal */
        {
            cmp->slide[w++] = (uch) t->v.n;
            if (w == WSIZE)
            {
                FLUSH(w);
                w = 0;
            }
        }
        else /* it's an EOB or a length */
        {
            /* exit if end of block */
            if (e == 15)
                break;

            /* get length of block to copy */
            NEEDBITS(e)
            n = t->v.n + ((unsigned)b & mask[e]);
            DUMPBITS(e);

            /* decode distance of block to copy */
            NEEDBITS((unsigned)bd)
            if ((e = (t = td + ((unsigned)b & md))->e) > 16)
                do
                {
                    if (e == 99)
                        return 1;
                    DUMPBITS(t->b)
                    e -= 16;
                    NEEDBITS(e)
                }

            while ((e = (t = t->v.t + ((unsigned)b & mask[e]))->e) > 16) ;

            DUMPBITS(t->b)
            NEEDBITS(e)
            d = w - t->v.n - ((unsigned)b & mask[e]);
            DUMPBITS(e)

            /* do the copy */
            do
            {
                n -= (e = (e = WSIZE - ((d &= WSIZE - 1) > w ? d : w)) > n ? n : e);
#ifndef NOMEMCPY
                if (w - d >= e) /* (this test assumes unsigned comparison) */
                {
                    memcpy((void *)(cmp->slide + w), (void *)(cmp->slide + d), e);
                    w += e;
                    d += e;
                }
                else            /* do it slow to avoid memcpy() overlap */
#endif  /* !NOMEMCPY */
                    do
                    {
                        cmp->slide[w++] = cmp->slide[d++];
                    } while(--e);

                if (w == WSIZE)
                {
                    FLUSH(w);
                    w = 0;
                }

            } while (n);
        }
    }


    /* restore the globals from the locals */
    cmp->wp = w;                /* restore global window pointer */
    cmp->bb = b;                /* restore global bit buffer */
    cmp->bk = k;


    /* done */
    return 0;
}



/* =======================================================

   FUNCTION:   inflate_fixed()

   PURPOSE:    "Decompress" an inflated type 0 (stored) 
               block.
               
   PARAMETERS: Ptr to compressed file wrapper.

   RETURNS:    Error code if any.

   ======================================================= */

int inflate_stored( COMPRESSED_FILE * cmp )
{
    unsigned n;                 /* number of bytes in block */
    unsigned w;                 /* current window position */
    register ulg b;             /* bit buffer */
    register unsigned k;        /* number of bits in bit buffer */


    /* make local copies of globals */
    Trace((stderr, "\nstored block"));
    b = cmp->bb;                /* initialize bit buffer */
    k = cmp->bk;
    w = cmp->wp;                /* initialize window position */

    /* go to byte boundary */
    n = k & 7;
    DUMPBITS(n);


    /* get the length and its complement */