inflate.c

空战游戏flacon源码

    NEEDBITS(16)
    n = ((unsigned)b & 0xffff);
    DUMPBITS(16)

    NEEDBITS(16)
    if (n != (unsigned)((~b) & 0xffff))
       return 1;               /* error in compressed data */
    DUMPBITS(16)

    /* read and output the compressed data */
    while (n--)
    {
        NEEDBITS(8)
        cmp->slide[w++] = (uch) b;

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

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

    return 0;
}


/* Globals for literal tables (built once) */

struct huft * fixed_tl = NULL,
            * fixed_td;
int           fixed_bl,
              fixed_bd;

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

   FUNCTION:   inflate_fixed()

   PURPOSE:    Decompress an inflated type 1 (fixed 
               Huffman codes) block.  We should either 
               replace this with a custom decoder, or at 
               least precompute the Huffman tables.

   PARAMETERS: Ptr to compressed file wrapper.

   RETURNS:    Error code if any.

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

int inflate_fixed( COMPRESSED_FILE * cmp )
{
    Trace((stderr, "\nliteral block"));

    /* if first time, set up tables for fixed blocks */

    if( fixed_tl == NULL )
    {
        int   i;                /* temporary variable */
        static unsigned l[288]; /* length list for huft_build */

        /* literal table */
        for (i = 0; i < 144; i++)
            l[i] = 8;

        for (; i < 256; i++)
            l[i] = 9;

        for (; i < 280; i++)
            l[i] = 7;

        for (; i < 288; i++)    /* make a complete, but wrong code set */
            l[i] = 8;

        fixed_bl = 7;

        if((i = huft_build(l, 288, 257, cplens, cplext, &fixed_tl, &fixed_bl)) != 0)
        {
            fixed_tl = NULL;
            return i;
        }

        /* distance table */
        for (i = 0; i < 30; i++)    /* make an incomplete code set */
            l[i] = 5;

        fixed_bd = 5;

        if((i = huft_build(l, 30, 0, cpdist, cpdext, &fixed_td, &fixed_bd)) > 1)
        {
            huft_free(fixed_tl);
            fixed_tl = NULL;
            return i;
        }
    }

    /* decompress until an end-of-block code */
    return inflate_codes(fixed_tl, fixed_td, fixed_bl, fixed_bd, cmp) != 0;
}



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

   FUNCTION:   inflate_dynamic()

   PURPOSE:    Decompress an inflated type 2 (dynamic 
               Huffman codes) block.

   PARAMETERS: Ptr to compressed file wrapper.

   RETURNS:    Error code if any.

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

int inflate_dynamic( COMPRESSED_FILE * cmp )
{
  int i;                /* temporary variables */
  unsigned j;
  unsigned l;           /* last length */
  unsigned m;           /* mask for bit lengths table */
  unsigned n;           /* number of lengths to get */
  struct huft *tl;      /* literal/length code table */
  struct huft *td;      /* distance code table */
  int bl;               /* lookup bits for tl */
  int bd;               /* lookup bits for td */
  unsigned nb;          /* number of bit length codes */
  unsigned nl;          /* number of literal/length codes */
  unsigned nd;          /* number of distance codes */
  static unsigned ll[288+32]; /* literal/length and distance code lengths */
  register ulg b;       /* bit buffer */
  register unsigned k;  /* number of bits in bit buffer */


  /* make local bit buffer */
  Trace((stderr, "\ndynamic block"));
  b = cmp -> bb;
  k = cmp -> bk;


  /* read in table lengths */
  NEEDBITS(5)
  nl = 257 + ((unsigned)b & 0x1f);      /* number of literal/length codes */
  DUMPBITS(5)
  NEEDBITS(5)
  nd = 1 + ((unsigned)b & 0x1f);        /* number of distance codes */
  DUMPBITS(5)
  NEEDBITS(4)
  nb = 4 + ((unsigned)b & 0xf);         /* number of bit length codes */
  DUMPBITS(4)
  if (nl > 288 || nd > 32)
    return 1;                   /* bad lengths */


  /* read in bit-length-code lengths */
  for (j = 0; j < nb; j++)
  {
    NEEDBITS(3)
    ll[border[j]] = (unsigned)b & 7;
    DUMPBITS(3)
  }
  for (; j < 19; j++)
    ll[border[j]] = 0;


  /* build decoding table for trees--single level, 7 bit lookup */
  bl = 7;
  if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
  {
    if (i == 1)
      huft_free(tl);
    return i;                   /* incomplete code set */
  }


  /* read in literal and distance code lengths */
  n = nl + nd;
  m = mask[bl];
  i = l = 0;
  while ((unsigned)i < n)
  {
    NEEDBITS((unsigned)bl)
    j = (td = tl + ((unsigned)b & m))->b;
    DUMPBITS(j)
    j = td->v.n;
    if (j < 16)                 /* length of code in bits (0..15) */
      ll[i++] = l = j;          /* save last length in l */
    else if (j == 16)           /* repeat last length 3 to 6 times */
    {
      NEEDBITS(2)
      j = 3 + ((unsigned)b & 3);
      DUMPBITS(2)
      if ((unsigned)i + j > n)
        return 1;
      while (j--)
        ll[i++] = l;
    }
    else if (j == 17)           /* 3 to 10 zero length codes */
    {
      NEEDBITS(3)
      j = 3 + ((unsigned)b & 7);
      DUMPBITS(3)
      if ((unsigned)i + j > n)
        return 1;
      while (j--)
        ll[i++] = 0;
      l = 0;
    }
    else                        /* j == 18: 11 to 138 zero length codes */
    {
      NEEDBITS(7)
      j = 11 + ((unsigned)b & 0x7f);
      DUMPBITS(7)
      if ((unsigned)i + j > n)
        return 1;
      while (j--)
        ll[i++] = 0;
      l = 0;
    }
  }


  /* free decoding table for trees */
  huft_free(tl);


  /* restore the global bit buffer */
  cmp -> bb = b;
  cmp -> bk = k;


  /* build the decoding tables for literal/length and distance codes */
  bl = lbits;
  if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) {
//    if (i == 1 && !qflag) {
//      fprintf(stderr, "(incomplete l-tree)  ");
//      huft_free(tl);
//    }
    return i;                   /* incomplete code set */
  }
  bd = dbits;
  if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) {
//    if (i == 1 && !qflag) {
//      fprintf(stderr, "(incomplete d-tree)  ");
//      i = 0;
//    }
  }


  /* decompress until an end-of-block code */
  if (inflate_codes(tl, td, bl, bd, cmp))
    return 1;


  /* free the decoding tables, return */
  huft_free(tl);
  huft_free(td);
  return 0;
}




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

   FUNCTION:   inflate_block()

   PURPOSE:    Decompress an inflated block

   PARAMETERS: Ptr to block, ptr to compressed file 
               wrapper.

   RETURNS:    Error code if any.

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

int inflate_block(int *e, COMPRESSED_FILE * cmp)
{
    unsigned t;                 /* block type */
    register ulg b;             /* bit buffer */
    register unsigned k;        /* number of bits in bit buffer */


    /* make local bit buffer */
    b = cmp->bb;
    k = cmp->bk;

    /* read in last block bit */
    NEEDBITS(1)
    * e = (int)b & 1;
    DUMPBITS(1)


    /* read in block type */
    NEEDBITS(2)
    t = (unsigned)b & 3;
    DUMPBITS(2)


    /* restore the global bit buffer */
    cmp->bb = b;
    cmp->bk = k;


    /* inflate that block type */
    if (t == 2)
        return inflate_dynamic(cmp);
    if (t == 0)
        return inflate_stored(cmp);
    if (t == 1)
        return inflate_fixed(cmp);


    /* bad block type */
    return 2;
}






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

   FUNCTION:   inflate

   PURPOSE:    Entry point into inflation (decompression)
               code.

   PARAMETERS: Compressed file wrapper.

   RETURNS:    Error code if any.

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

int inflate( COMPRESSED_FILE * cmp )
{
    int   e;                    /* last block flag */
    int   r;                    /* result code */
    unsigned h;                 /* maximum struct huft's malloc'ed */


    /* initialize window, bit buffer */

    cmp -> wp = 0;
    cmp -> bk = 0;
    cmp -> bb = 0;


    /* decompress until the last block */

    h = 0;

    do {
        hufts = 0;

        if ((r = inflate_block(&e, cmp)) != 0)
            return( r );

        if (hufts > h)
            h = hufts;

    } while (!e);


    /* flush out slide */
    FLUSH( cmp -> wp );

    //Trace((stderr, "\n%u bytes in Huffman tables (%d/entry)", h * sizeof(struct huft), sizeof(struct huft)));

    /* return success */
    return( 0 );
}



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

   FUNCTION:   inflate_free()

   PURPOSE:    Free allocations used for huftman trees

   PARAMETERS: Compressed file wrapper.

   RETURNS:    Error code if any.

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

int inflate_free( void )
{
   if( fixed_tl != NULL ) {
       huft_free( fixed_td );
       huft_free( fixed_tl );

       fixed_td = NULL;
       fixed_tl = NULL;
   }

   return( 0 );
}