gunzip.c

i386的bootloader源码grub

	  if (!n)
	    code_state--;

	  /* did we break from the loop too soon? */
	  if (w == WSIZE)
	    break;
	}
    }

  /* restore the globals from the locals */
  inflate_d = d;
  inflate_n = n;
  wp = w;			/* restore global window pointer */
  bb = b;			/* restore global bit buffer */
  bk = k;

  return !block_len;
}


/* get header for an inflated type 0 (stored) block. */

static void
init_stored_block (void)
{
  register ulg b;		/* bit buffer */
  register unsigned k;		/* number of bits in bit buffer */

  /* make local copies of globals */
  b = bb;			/* initialize bit buffer */
  k = bk;

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

  /* get the length and its complement */
  NEEDBITS (16);
  block_len = ((unsigned) b & 0xffff);
  DUMPBITS (16);
  NEEDBITS (16);
  if (block_len != (unsigned) ((~b) & 0xffff))
    errnum = ERR_BAD_GZIP_DATA;
  DUMPBITS (16);

  /* restore global variables */
  bb = b;
  bk = k;
}


/* get header for an inflated type 1 (fixed Huffman codes) block.  We should
   either replace this with a custom decoder, or at least precompute the
   Huffman tables. */

static void
init_fixed_block ()
{
  int i;			/* temporary variable */
  unsigned l[288];		/* length list for huft_build */

  /* set up 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;
  bl = 7;
  if ((i = huft_build (l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
    {
      errnum = ERR_BAD_GZIP_DATA;
      return;
    }

  /* set up distance table */
  for (i = 0; i < 30; i++)	/* make an incomplete code set */
    l[i] = 5;
  bd = 5;
  if ((i = huft_build (l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
    {
      errnum = ERR_BAD_GZIP_DATA;
      return;
    }

  /* indicate we're now working on a block */
  code_state = 0;
  block_len++;
}


/* get header for an inflated type 2 (dynamic Huffman codes) block. */

static void
init_dynamic_block (void)
{
  int i;			/* temporary variables */
  unsigned j;
  unsigned l;			/* last length */
  unsigned m;			/* mask for bit lengths table */
  unsigned n;			/* number of lengths to get */
  unsigned nb;			/* number of bit length codes */
  unsigned nl;			/* number of literal/length codes */
  unsigned nd;			/* number of distance codes */
  unsigned ll[286 + 30];	/* literal/length and distance code lengths */
  register ulg b;		/* bit buffer */
  register unsigned k;		/* number of bits in bit buffer */

  /* make local bit buffer */
  b = bb;
  k = 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 > 286 || nd > 30)
    {
      errnum = ERR_BAD_GZIP_DATA;
      return;
    }

  /* read in bit-length-code lengths */
  for (j = 0; j < nb; j++)
    {
      NEEDBITS (3);
      ll[bitorder[j]] = (unsigned) b & 7;
      DUMPBITS (3);
    }
  for (; j < 19; j++)
    ll[bitorder[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)
    {
      errnum = ERR_BAD_GZIP_DATA;
      return;
    }

  /* read in literal and distance code lengths */
  n = nl + nd;
  m = mask_bits[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)
	    {
	      errnum = ERR_BAD_GZIP_DATA;
	      return;
	    }
	  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)
	    {
	      errnum = ERR_BAD_GZIP_DATA;
	      return;
	    }
	  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)
	    {
	      errnum = ERR_BAD_GZIP_DATA;
	      return;
	    }
	  while (j--)
	    ll[i++] = 0;
	  l = 0;
	}
    }

  /* free decoding table for trees */
  reset_linalloc ();

  /* restore the global bit buffer */
  bb = b;
  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 0
      if (i == 1)
	printf ("gunzip: incomplete literal tree\n");
#endif

      errnum = ERR_BAD_GZIP_DATA;
      return;
    }
  bd = dbits;
  if ((i = huft_build (ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
    {
#if 0
      if (i == 1)
	printf ("gunzip: incomplete distance tree\n");
#endif

      errnum = ERR_BAD_GZIP_DATA;
      return;
    }

  /* indicate we're now working on a block */
  code_state = 0;
  block_len++;
}


static void
get_new_block (void)
{
  register ulg b;		/* bit buffer */
  register unsigned k;		/* number of bits in bit buffer */

  hufts = 0;

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

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

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

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

  if (block_type == INFLATE_STORED)
    init_stored_block ();
  if (block_type == INFLATE_FIXED)
    init_fixed_block ();
  if (block_type == INFLATE_DYNAMIC)
    init_dynamic_block ();
}


static void
inflate_window (void)
{
  /* initialize window */
  wp = 0;

  /*
   *  Main decompression loop.
   */

  while (wp < WSIZE && !errnum)
    {
      if (!block_len)
	{
	  if (last_block)
	    break;

	  get_new_block ();
	}

      if (block_type > INFLATE_DYNAMIC)
	errnum = ERR_BAD_GZIP_DATA;

      if (errnum)
	return;

      /*
       *  Expand stored block here.
       */
      if (block_type == INFLATE_STORED)
	{
	  int w = wp;

	  /*
	   *  This is basically a glorified pass-through
	   */

	  while (block_len && w < WSIZE && !errnum)
	    {
	      slide[w++] = get_byte ();
	      block_len--;
	    }

	  wp = w;

	  continue;
	}

      /*
       *  Expand other kind of block.
       */

      if (inflate_codes_in_window ())
	reset_linalloc ();
    }

  saved_filepos += WSIZE;

  /* XXX do CRC calculation here! */
}


static void
initialize_tables (void)
{
  saved_filepos = 0;
  filepos = gzip_data_offset;

  /* initialize window, bit buffer */
  bk = 0;
  bb = 0;

  /* reset partial decompression code */
  last_block = 0;
  block_len = 0;

  /* reset memory allocation stuff */
  reset_linalloc ();
}


int
gunzip_read (char *buf, int len)
{
  int ret = 0;

  compressed_file = 0;
  gunzip_swap_values ();
  /*
   *  Now "gzip_*" values refer to the uncompressed data.
   */

  /* do we reset decompression to the beginning of the file? */
  if (saved_filepos > gzip_filepos + WSIZE)
    initialize_tables ();

  /*
   *  This loop operates upon uncompressed data only.  The only
   *  special thing it does is to make sure the decompression
   *  window is within the range of data it needs.
   */

  while (len > 0 && !errnum)
    {
      register int size;
      register char *srcaddr;

      while (gzip_filepos >= saved_filepos)
	inflate_window ();

      srcaddr = (char *) ((gzip_filepos & (WSIZE - 1)) + slide);
      size = saved_filepos - gzip_filepos;
      if (size > len)
	size = len;

      memmove (buf, srcaddr, size);

      buf += size;
      len -= size;
      gzip_filepos += size;
      ret += size;
    }

  compressed_file = 1;
  gunzip_swap_values ();
  /*
   *  Now "gzip_*" values refer to the compressed data.
   */

  if (errnum)
    ret = 0;

  return ret;
}

#endif /* ! NO_DECOMPRESSION */