inflate.c

MIDI解码程序(用VC编写)

    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((unsigned)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 */
		if(pool == NULL)
		    q = (struct huft *)malloc((z + 1)*sizeof(struct huft));
		else
		    q = (struct huft *)
			new_segment(pool, (z + 1)*sizeof(struct huft));
		if(q == NULL)
		{
		    if(h && pool == NULL)
			huft_free(u[0]);
		    return 3;	/* not enough memory */
		}

		*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;
}

local int huft_free(struct huft *t)
/* Free the malloc'ed 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. */
{
    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;
	free((char*)p);
	p = q;
    }
    return 0;
}

local long inflate_codes(InflateHandler decoder, char *buff, long size)
/* inflate (decompress) the codes in a deflated (compressed) block.
   Return an error code or zero if it all goes ok. */
{
    register unsigned e;/* table entry flag/number of extra bits */
    struct huft *t;	/* pointer to table entry */
    int n;
    struct huft *tl, *td;/* literal/length and distance decoder tables */
    int bl, bd;		/* number of bits decoded by tl[] and td[] */
    unsigned l, w, d;
    uch *slide;

    BITS_SAVE;

    if(size == 0)
	return 0;

    slide = decoder->slide;
    tl = decoder->tl;
    td = decoder->td;
    bl = decoder->bl;
    bd = decoder->bd;

#ifdef DEBUG
    if(decoder->copy_leng != 0)
    {
	fprintf(stderr, "What ? (decoder->copy_leng = %d)\n",
		decoder->copy_leng);
	abort();
    }
#endif /* DEBUG */
    w = decoder->wp;

    /* inflate the coded data */
    n = 0;
    for(;;)			/* do until end of block */
    {
	NEEDBITS((unsigned)bl);
	t = tl + GETBITS(bl);
	e = t->e;
	while(e > 16)
	{
	    if(e == 99)
		return -1;
	    DUMPBITS(t->b);
	    e -= 16;
	    NEEDBITS(e);
	    t = t->v.t + GETBITS(e);
	    e = t->e;
	}
	DUMPBITS(t->b);

	if(e == 16)		/* then it's a literal */
	{
	    w &= WSIZE - 1;
	    buff[n++] = slide[w++] = (uch)t->v.n;
	    if(n == size)
	    {
		decoder->wp = w;
		BITS_RESTORE;
		return size;
	    }
	    continue;
	}

	/* exit if end of block */
	if(e == 15)
	    break;

	/* it's an EOB or a length */

	/* get length of block to copy */
	NEEDBITS(e);
	l = t->v.n + GETBITS(e);
	DUMPBITS(e);

	/* decode distance of block to copy */
	NEEDBITS((unsigned)bd);
	t = td + GETBITS(bd);
	e = t->e;
	while(e > 16)
	{
	    if(e == 99)
		return -1;
	    DUMPBITS(t->b);
	    e -= 16;
	    NEEDBITS(e);
	    t = t->v.t + GETBITS(e);
	    e = t->e;
	}
	DUMPBITS(t->b);
	NEEDBITS(e);
	d = w - t->v.n - GETBITS(e);
	DUMPBITS(e);

	/* do the copy */
	while(l > 0 && n < size)
	{
	    l--;
	    d &= WSIZE - 1;
	    w &= WSIZE - 1;
	    buff[n++] = slide[w++] = slide[d++];
	}

	if(n == size)
	{
	    decoder->copy_leng = l;
	    decoder->wp = w;
	    decoder->copy_dist = d;
	    BITS_RESTORE;
	    return n;
	}
    }

    decoder->wp = w;
    decoder->method = -1; /* done */
    BITS_RESTORE;
    return n;
}

local long inflate_stored(InflateHandler decoder, char *buff, long size)
/* "decompress" an inflated type 0 (stored) block. */
{
    unsigned n, l, w;
    BITS_SAVE;

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

    /* get the length and its complement */
    NEEDBITS(16);
    n = GETBITS(16);
    DUMPBITS(16);
    NEEDBITS(16);
    if(n != (unsigned)((~bit_buf) & 0xffff))
    {
	BITS_RESTORE;
	return -1;			/* error in compressed data */
    }
    DUMPBITS(16);

    /* read and output the compressed data */
    decoder->copy_leng = n;

    n = 0;
    l = decoder->copy_leng;
    w = decoder->wp;
    while(l > 0 && n < size)
    {
	l--;
	w &= WSIZE - 1;
	NEEDBITS(8);
	buff[n++] = decoder->slide[w++] = (uch)GETBITS(8);
	DUMPBITS(8);
    }
    if(l == 0)
	decoder->method = -1; /* done */
    decoder->copy_leng = l;
    decoder->wp = w;
    BITS_RESTORE;
    return (long)n;
}

local long inflate_fixed(InflateHandler decoder, char *buff, long size)
/* 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. */
{
    /* if first time, set up tables for fixed blocks */
    if(decoder->fixed_tl == NULL)
    {
	int i;		  /* temporary variable */
	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;
	decoder->fixed_bl = 7;
	if((i = huft_build(l, 288, 257, cplens, cplext,
			   &decoder->fixed_tl, &decoder->fixed_bl, NULL))
	    != 0)
	{
	    decoder->fixed_tl = NULL;
	    return -1;
	}

	/* distance table */
	for(i = 0; i < 30; i++)	  /* make an incomplete code set */
	    l[i] = 5;
	decoder->fixed_bd = 5;
	if((i = huft_build(l, 30, 0, cpdist, cpdext,
			   &decoder->fixed_td, &decoder->fixed_bd, NULL)) > 1)
	{
	    huft_free(decoder->fixed_tl);
	    decoder->fixed_tl = NULL;
	    return -1;
	}
    }

    decoder->tl = decoder->fixed_tl;
    decoder->td = decoder->fixed_td;
    decoder->bl = decoder->fixed_bl;
    decoder->bd = decoder->fixed_bd;
    return inflate_codes(decoder, buff, size);
}

local long inflate_dynamic(InflateHandler decoder, char *buff, long size)
/* decompress an inflated type 2 (dynamic Huffman codes) block. */
{
    int i;		/* temporary variables */
    unsigned j;
    unsigned l;		/* last length */
    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 */
#ifdef PKZIP_BUG_WORKAROUND