unlzh.c

MIDI解码程序(用VC编写)

}

static void reconst(UNLZHHandler decoder, int start, int end)
{
    int i, j, k, l, b;
    unsigned int f, g;

    b = 0;
    for(i = j = start; i < end; i++)
    {
	if((k = decoder->child[i]) < 0)
	{
	    decoder->freq[j] = (decoder->freq[i] + 1) / 2;
	    decoder->child[j] = k;
	    j++;
	}
	if(decoder->edge[b = decoder->block[i]] == i)
	{
	    decoder->stock[--decoder->avail] = b;
	}
    }
    j--;
    i = end - 1;
    l = end - 2;
    while(i >= start)
    {
	while (i >= l)
	{
	    decoder->freq[i] = decoder->freq[j];
	    decoder->child[i] = decoder->child[j];
	    i--;
	    j--;
	}
	f = decoder->freq[l] + decoder->freq[l + 1];
	for(k = start; f < decoder->freq[k]; k++)
	    ;
	while(j >= k)
	{
	    decoder->freq[i] = decoder->freq[j];
	    decoder->child[i] = decoder->child[j];
	    i--;
	    j--;
	}
	decoder->freq[i] = f;
	decoder->child[i] = l + 1;
	i--;
	l -= 2;
    }
    f = 0;
    for(i = start; i < end; i++)
    {
	if((j = decoder->child[i]) < 0)
	    decoder->node[~j] = i;
	else
	    decoder->parent[j] = decoder->parent[j - 1] = i;
	if((g = decoder->freq[i]) == f)
	{
	    decoder->block[i] = b;
	}
	else
	{
	    decoder->edge[b = decoder->block[i]
			  = decoder->stock[decoder->avail++]] = i;
	    f = g;
	}
    }
}

static int swap_inc(UNLZHHandler decoder, int p)
{
    int b, q, r, s;

    b = decoder->block[p];
    if((q = decoder->edge[b]) != p)
    {	/* swap for leader */
	r = decoder->child[p];
	s = decoder->child[q];
	decoder->child[p] = s;
	decoder->child[q] = r;
	if(r >= 0)
	    decoder->parent[r] = decoder->parent[r - 1] = q;
	else
	    decoder->node[~r] = q;
	if(s >= 0)
	    decoder->parent[s] = decoder->parent[s - 1] = p;
	else
	    decoder->node[~s] = p;
	p = q;
	goto Adjust;
    }
    else if(b == decoder->block[p + 1])
    {
      Adjust:
	decoder->edge[b]++;
	if(++decoder->freq[p] == decoder->freq[p - 1])
	{
	    decoder->block[p] = decoder->block[p - 1];
	}
	else
	{
	    decoder->edge[decoder->block[p] =
		 decoder->stock[decoder->avail++]] = p;	/* create block */
	}
    }
    else if (++decoder->freq[p] == decoder->freq[p - 1])
    {
	decoder->stock[--decoder->avail] = b;		/* delete block */
	decoder->block[p] = decoder->block[p - 1];
    }
    return decoder->parent[p];
}

static void update_c(UNLZHHandler decoder, int p)
{
    int q;

    if(decoder->freq[ROOT_C] == 0x8000)
    {
	reconst(decoder, 0, decoder->n_max * 2 - 1);
    }
    decoder->freq[ROOT_C]++;
    q = decoder->node[p];
    do
    {
	q = swap_inc(decoder, q);
    } while(q != ROOT_C);
}

static void update_p(UNLZHHandler decoder, int p)
{
    int q;

    if(decoder->total_p == 0x8000)
    {
	reconst(decoder, ROOT_P, decoder->most_p + 1);
	decoder->total_p = decoder->freq[ROOT_P];
	decoder->freq[ROOT_P] = 0xffff;
    }
    q = decoder->node[p + N_CHAR];
    while(q != ROOT_P)
    {
	q = swap_inc(decoder, q);
    }
    decoder->total_p++;
}

static void make_new_node(UNLZHHandler decoder, int p)
{
    int q, r;

    r = decoder->most_p + 1;
    q = r + 1;
    decoder->node[~(decoder->child[r] = decoder->child[decoder->most_p])] = r;
    decoder->child[q] = ~(p + N_CHAR);
    decoder->child[decoder->most_p] = q;
    decoder->freq[r] = decoder->freq[decoder->most_p];
    decoder->freq[q] = 0;
    decoder->block[r] = decoder->block[decoder->most_p];
    if(decoder->most_p == ROOT_P)
    {
	decoder->freq[ROOT_P] = 0xffff;
	decoder->edge[decoder->block[ROOT_P]]++;
    }
    decoder->parent[r] = decoder->parent[q] = decoder->most_p;
    decoder->edge[decoder->block[q] = decoder->stock[decoder->avail++]]
	= decoder->node[p + N_CHAR] = decoder->most_p = q;
    update_p(decoder, p);
}

static unsigned short decode_c_dyn(UNLZHHandler decoder)
{
    int c;
    short buf, cnt;

    c = decoder->child[ROOT_C];
    buf = decoder->bitbuf;
    cnt = 0;
    do
    {
	c = decoder->child[c - (buf < 0)];
	buf <<= 1;
	if(++cnt == 16)
	{
	    fillbuf(decoder, 16);
	    buf = decoder->bitbuf;
	    cnt = 0;
	}
    }while (c > 0);
    fillbuf(decoder, cnt);
    c = ~c;
    update_c(decoder, c);
    if(c == decoder->n1)
	c += getbits(decoder, 8);
    return c;
}

static unsigned short decode_p_dyn(UNLZHHandler decoder)
{
    int c;
    short buf, cnt;

    while(decoder->count > decoder->nextcount)
    {
	make_new_node(decoder, (int)(decoder->nextcount / 64));
	if((decoder->nextcount += 64) >= decoder->nn)
	    decoder->nextcount = 0xffffffff;
    }
    c = decoder->child[ROOT_P];
    buf = decoder->bitbuf;
    cnt = 0;
    while(c > 0)
    {
	c = decoder->child[c - (buf < 0)];
	buf <<= 1;
	if(++cnt == 16)
	{
	    fillbuf(decoder, 16);
	    buf = decoder->bitbuf;
	    cnt = 0;
	}
    }
    fillbuf(decoder, cnt);
    c = (~c) - N_CHAR;
    update_p(decoder, c);

    return (c << 6) + getbits(decoder, 6);
}

static void decode_start_st0(UNLZHHandler decoder)
{
    decoder->n_max = 286;
    decoder->maxmatch = MAXMATCH;
    init_getbits(decoder);
    decoder->snp = 1 << (MAX_DICBIT - 6);
    decoder->blocksize = 0;
}

static int fixed[2][16] = {
    {3, 0x01, 0x04, 0x0c, 0x18, 0x30, 0},		/* old compatible */
    {2, 0x01, 0x01, 0x03, 0x06, 0x0D, 0x1F, 0x4E, 0}	/* 8K buf */
};

static void ready_made(UNLZHHandler decoder, int method)
{
    int i, j;
    unsigned int code, weight;
    int *tbl;

    tbl = fixed[method];
    j = *tbl++;
    weight = 1 << (16 - j);
    code = 0;
    for(i = 0; i < decoder->snp; i++)
    {
	while(*tbl == i)
	{
	    j++;
	    tbl++;
	    weight >>= 1;
	}
	decoder->pt_len[i] = j;
	code += weight;
    }
}

static void read_tree_c(UNLZHHandler decoder)  /* read tree from file */
{
    int i, c;

    i = 0;
    while(i < N1)
    {
	if(getbits(decoder, 1))
	    decoder->c_len[i] = getbits(decoder, LENFIELD) + 1;
	else
	    decoder->c_len[i] = 0;
	if(++i == 3 && decoder->c_len[0] == 1 &&
	   decoder->c_len[1] == 1 && decoder->c_len[2] == 1)
	{
	    c = getbits(decoder, CBIT);
	    for(i = 0; i < N1; i++)
		decoder->c_len[i] = 0;
	    for(i = 0; i < 4096; i++)
		decoder->c_table[i] = c;
	    return;
	}
    }
    make_table(decoder, N1, decoder->c_len, 12, decoder->c_table);
}

static void read_tree_p(UNLZHHandler decoder)  /* read tree from file */
{
    int i, c;

    i = 0;
    while(i < SNP)
    {
	decoder->pt_len[i] = getbits(decoder, LENFIELD);
	if(++i == 3 && decoder->pt_len[0] == 1 &&
	   decoder->pt_len[1] == 1 && decoder->pt_len[2] == 1)
	{
	    c = getbits(decoder, MAX_DICBIT - 6);
	    for(i = 0; i < SNP; i++)
		decoder->c_len[i] = 0;
	    for(i = 0; i < 256; i++)
		decoder->c_table[i] = c;
	    return;
	}
    }
}

static void decode_start_fix(UNLZHHandler decoder)
{
    decoder->n_max = 314;
    decoder->maxmatch = 60;
    init_getbits(decoder);
    decoder->snp = 1 << (12 - 6);
    start_c_dyn(decoder);
    ready_made(decoder, 0);
    make_table(decoder, decoder->snp, decoder->pt_len, 8, decoder->pt_table);
}

static unsigned short decode_c_st0(UNLZHHandler decoder)
{
    int i, j;

    if(decoder->blocksize == 0) /* read block head */
    {
	/* read block blocksize */
	decoder->blocksize = getbits(decoder, BUFBITS);
	read_tree_c(decoder);
	if(getbits(decoder, 1))
	{
	    read_tree_p(decoder);
	}
	else
	{
	    ready_made(decoder, 1);
	}
	make_table(decoder, SNP, decoder->pt_len, 8, decoder->pt_table);
    }
    decoder->blocksize--;
    j = decoder->c_table[decoder->bitbuf >> 4];
    if(j < N1)
	fillbuf(decoder, decoder->c_len[j]);
    else
    {
	fillbuf(decoder, 12);
	i = decoder->bitbuf;
	do
	{
	    if((short)i < 0)
		j = decoder->right[j];
	    else
		j = decoder->left [j];
	    i <<= 1;
	} while(j >= N1);
	fillbuf(decoder, decoder->c_len[j] - 12);
    }
    if(j == N1 - 1)
	j += getbits(decoder, EXTRABITS);
    return j;
}

static unsigned short decode_p_st0(UNLZHHandler decoder)
{
    int i, j;

    j = decoder->pt_table[decoder->bitbuf >> 8];
    if(j < decoder->snp)
    {
	fillbuf(decoder, decoder->pt_len[j]);
    }
    else
    {
	fillbuf(decoder, 8);
	i = decoder->bitbuf;
	do
	{
	    if((short)i < 0)
		j = decoder->right[j];
	    else
		j = decoder->left[j];
	    i <<= 1;
	} while(j >= decoder->snp);
	fillbuf(decoder, decoder->pt_len[j] - 8);
    }
    return (j << 6) + getbits(decoder, 6);
}

static unsigned short decode_c_lzs(UNLZHHandler decoder)
{
    if(getbits(decoder, 1))
	return getbits(decoder, 8);
    decoder->matchpos = getbits(decoder, 11);
    return getbits(decoder, 4) + 0x100;
}

static unsigned short decode_p_lzs(UNLZHHandler decoder)
{
    return (decoder->loc - decoder->matchpos - MAGIC0) & 0x7ff;
}

static void decode_start_lzs(UNLZHHandler decoder)
{
    init_getbits(decoder);
}

static unsigned short decode_c_lz5(UNLZHHandler decoder)
{
    int c;

    if(decoder->flagcnt == 0)
    {
	decoder->flagcnt = 8;
	decoder->flag = NEXTBYTE;
    }
    decoder->flagcnt--;
    c = NEXTBYTE;
    if((decoder->flag & 1) == 0)
    {
	decoder->matchpos = c;
	c = NEXTBYTE;
	decoder->matchpos += (c & 0xf0) << 4;
	c &= 0x0f;
	c += 0x100;
    }
    decoder->flag >>= 1;
    return c;
}

static unsigned short decode_p_lz5(UNLZHHandler decoder)
{
    return (decoder->loc - decoder->matchpos - MAGIC5) & 0xfff;
}

static void decode_start_lz5(UNLZHHandler decoder)
{
    int i;

    decoder->flagcnt = 0;
    for(i = 0; i < 256; i++)
	memset(&decoder->text[i * 13 + 18], i, 13);
    for(i = 0; i < 256; i++)
	decoder->text[256 * 13 + 18 + i] = i;
    for(i = 0; i < 256; i++)
	decoder->text[256 * 13 + 256 + 18 + i] = 255 - i;
    memset(&decoder->text[256 * 13 + 512 + 18], 0, 128);
    memset(&decoder->text[256 * 13 + 512 + 128 + 18], ' ', 128 - 18);
}

static int make_table(UNLZHHandler decoder,
		       int nchar, unsigned char bitlen[],
		       int tablebits, unsigned short table[])
{
    unsigned short cnttable[17];  /* count of bitlen */
    unsigned short weight[17]; /* 0x10000ul >> bitlen */
    unsigned short start[17];  /* first code of bitlen */
    unsigned short total;
    unsigned int i;
    int j, k, l, m, n, available;
    unsigned short *p;

    available = nchar;

/* initialize */
    for(i = 1; i <= 16; i++)
    {
	cnttable[i] = 0;
	weight[i] = 1 << (16 - i);
    }

/* cnttable */
    for(i = 0; i < nchar; i++)
	cnttable[bitlen[i]]++;

/* calculate first code */
    total = 0;
    for(i = 1; i <= 16; i++)
    {
	start[i] = total;
	total += weight[i] * cnttable[i];
    }
    if((total & 0xffff) != 0)
    {
	fprintf(stderr, "Decode: Bad table (5)\n");
	/*exit(1);*/ /* for win32gui i/f  2002/8/17 */
	return 1;
    }

/* shift data for make table. */
    m = 16 - tablebits;
    for(i = 1; i <= tablebits; i++)
    {
	start[i] >>= m;
	weight[i] >>= m;
    }

/* initialize */
    j = start[tablebits + 1] >> m;
    k = 1 << tablebits;
    if(j != 0)
	for(i = j; i < k; i++)
	    table[i] = 0;

/* create table and tree */
    for(j = 0; j < nchar; j++)
    {
	k = bitlen[j];
	if(k == 0)
	    continue;
	l = start[k] + weight[k];
	if(k <= tablebits)
	{
	    /* code in table */
	    for(i = start[k]; i < l; i++)
		table[i] = j;
	}
	else
	{
	    /* code not in table */
	    p = &table[(i = start[k]) >> m];
	    i <<= tablebits;
	    n = k - tablebits;
	    /* make tree (n length) */
	    while(--n >= 0)
	    {
		if(*p == 0)
		{
		    decoder->right[available] = decoder->left[available] = 0;
		    *p = available++;
		}
		if(i & 0x8000)
		    p = &decoder->right[*p];
		else
		    p = &decoder->left[*p];
		i <<= 1;
	    }
	    *p = j;
	}
	start[k] = l;
    }
    return 0;
}

static int fill_inbuf(UNLZHHandler decoder)
{
    long n, i;

    if(decoder->compsize == 0)
	return EOF;
    i = INBUFSIZ;
    if(i > decoder->compsize)
	i = (long)decoder->compsize;
    n = decoder->read_func((char *)decoder->inbuf, i, decoder->user_val);
    if(n <= 0)
	return EOF;
    decoder->inbuf_size = n;
    decoder->inbuf_cnt = 1;
    decoder->compsize -= n;
    return (int)decoder->inbuf[0];
}

/* Shift bitbuf n bits left, read n bits */
static void fillbuf(UNLZHHandler decoder, unsigned char n)
{
    unsigned char bitcount;
    unsigned short bitbuf;

    bitcount = decoder->bitcount;
    bitbuf   = decoder->bitbuf;
    while(n > bitcount)
    {
	n -= bitcount;
	bitbuf = (bitbuf << bitcount)
	    + (decoder->subbitbuf >> (CHAR_BIT - bitcount));
	decoder->subbitbuf = (unsigned char)NEXTBYTE;
	bitcount = CHAR_BIT;
    }
    bitcount -= n;
    bitbuf = (bitbuf << n) + (decoder->subbitbuf >> (CHAR_BIT - n));
    decoder->subbitbuf <<= n;
    decoder->bitcount = bitcount;
    decoder->bitbuf   = bitbuf;
}

static unsigned short getbits(UNLZHHandler decoder, unsigned char n)
{
    unsigned short x;

    x = decoder->bitbuf >> (2 * CHAR_BIT - n);
    fillbuf(decoder, n);
    return x;
}

static void init_getbits(UNLZHHandler decoder)
{
    decoder->bitbuf = 0;
    decoder->subbitbuf = 0;
    decoder->bitcount = 0;
    decoder->inbuf_cnt = 0;
    decoder->inbuf_size = 0;
    fillbuf(decoder, 2 * CHAR_BIT);
}