deflate.c

linux上播放midi音乐,但是要一些设置.可网上查找. 软件名称: TiMidity++-2.13.0.tar

local void ct_init(DeflateHandler encoder)
{
    int n;	/* iterates over tree elements */
    int bits;	/* bit counter */
    int length;	/* length value */
    int code;	/* code value */
    int dist;	/* distance index */

    if(encoder->static_dtree[0].Len != 0) return; /* ct_init already called */

    encoder->l_desc.dyn_tree	= encoder->dyn_ltree;
    encoder->l_desc.static_tree = encoder->static_ltree;
    encoder->l_desc.extra_bits	= extra_lbits;
    encoder->l_desc.extra_base	= LITERALS + 1;
    encoder->l_desc.elems	= L_CODES;
    encoder->l_desc.max_length	= MAX_BITS;
    encoder->l_desc.max_code	= 0;

    encoder->d_desc.dyn_tree	= encoder->dyn_dtree;
    encoder->d_desc.static_tree = encoder->static_dtree;
    encoder->d_desc.extra_bits	= extra_dbits;
    encoder->d_desc.extra_base	= 0;
    encoder->d_desc.elems	= D_CODES;
    encoder->d_desc.max_length	= MAX_BITS;
    encoder->d_desc.max_code	= 0;

    encoder->bl_desc.dyn_tree	 = encoder->bl_tree;
    encoder->bl_desc.static_tree = NULL;
    encoder->bl_desc.extra_bits	 = extra_blbits;
    encoder->bl_desc.extra_base	 = 0;
    encoder->bl_desc.elems	 = BL_CODES;
    encoder->bl_desc.max_length	 = MAX_BL_BITS;
    encoder->bl_desc.max_code	 = 0;

    /* Initialize the mapping length (0..255) -> length code (0..28) */
    length = 0;
    for(code = 0; code < LENGTH_CODES-1; code++) {
	encoder->base_length[code] = length;
	for(n = 0; n < (1<<extra_lbits[code]); n++) {
	    encoder->length_code[length++] = (uch)code;
	}
    }
    Assert (length == 256, "ct_init: length != 256");
    /* Note that the length 255 (match length 258) can be represented
     * in two different ways: code 284 + 5 bits or code 285, so we
     * overwrite length_code[255] to use the best encoding:
     */
    encoder->length_code[length-1] = (uch)code;

    /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
    dist = 0;
    for(code = 0 ; code < 16; code++) {
	encoder->base_dist[code] = dist;
	for(n = 0; n < (1<<extra_dbits[code]); n++) {
	    encoder->dist_code[dist++] = (uch)code;
	}
    }
    Assert (dist == 256, "ct_init: dist != 256");
    dist >>= 7; /* from now on, all distances are divided by 128 */
    for( ; code < D_CODES; code++) {
	encoder->base_dist[code] = dist << 7;
	for(n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
	    encoder->dist_code[256 + dist++] = (uch)code;
	}
    }
    Assert (dist == 256, "ct_init: 256+dist != 512");

    /* Construct the codes of the static literal tree */
    for(bits = 0; bits <= MAX_BITS; bits++) encoder->bl_count[bits] = 0;
    n = 0;
    while(n <= 143) encoder->static_ltree[n++].Len = 8, encoder->bl_count[8]++;
    while(n <= 255) encoder->static_ltree[n++].Len = 9, encoder->bl_count[9]++;
    while(n <= 279) encoder->static_ltree[n++].Len = 7, encoder->bl_count[7]++;
    while(n <= 287) encoder->static_ltree[n++].Len = 8, encoder->bl_count[8]++;
    /* Codes 286 and 287 do not exist, but we must include them in the
     * tree construction to get a canonical Huffman tree (longest code
     * all ones)
     */
    gen_codes(encoder, (ct_data near *)encoder->static_ltree, L_CODES+1);

    /* The static distance tree is trivial: */
    for(n = 0; n < D_CODES; n++) {
	encoder->static_dtree[n].Len = 5;
	encoder->static_dtree[n].Code = bi_reverse(n, 5);
    }

    /* Initialize the first block of the first file: */
    init_block(encoder);
}

/* ===========================================================================
 * Initialize a new block.
 */
local void init_block(DeflateHandler encoder)
{
    int n; /* iterates over tree elements */

    /* Initialize the trees. */
    for(n = 0; n < L_CODES;  n++) encoder->dyn_ltree[n].Freq = 0;
    for(n = 0; n < D_CODES;  n++) encoder->dyn_dtree[n].Freq = 0;
    for(n = 0; n < BL_CODES; n++) encoder->bl_tree[n].Freq = 0;

    encoder->dyn_ltree[END_BLOCK].Freq = 1;
    encoder->opt_len = encoder->static_len = 0L;
    encoder->last_lit = encoder->last_dist = encoder->last_flags = 0;
    encoder->flags = 0;
    encoder->flag_bit = 1;
}

/* ===========================================================================
 * Restore the heap property by moving down the tree starting at node k,
 * exchanging a node with the smallest of its two sons if necessary, stopping
 * when the heap property is re-established (each father smaller than its
 * two sons).
 */
local void pqdownheap(
    DeflateHandler encoder,
    ct_data near *tree,	/* the tree to restore */
    int k)		/* node to move down */
{
    int v = encoder->heap[k];
    int j = k << 1;  /* left son of k */
    while(j <= encoder->heap_len) {
	/* Set j to the smallest of the two sons: */
	if(j < encoder->heap_len &&
	   SMALLER(tree, encoder->heap[j+1], encoder->heap[j]))
	    j++;

	/* Exit if v is smaller than both sons */
	if(SMALLER(tree, v, encoder->heap[j]))
	    break;

	/* Exchange v with the smallest son */
	encoder->heap[k] = encoder->heap[j];
	k = j;

	/* And continue down the tree, setting j to the left son of k */
	j <<= 1;
    }
    encoder->heap[k] = v;
}

/* ===========================================================================
 * Compute the optimal bit lengths for a tree and update the total bit length
 * for the current block.
 * IN assertion: the fields freq and dad are set, heap[heap_max] and
 *    above are the tree nodes sorted by increasing frequency.
 * OUT assertions: the field len is set to the optimal bit length, the
 *     array bl_count contains the frequencies for each bit length.
 *     The length opt_len is updated; static_len is also updated if stree is
 *     not null.
 */
local void gen_bitlen(
    DeflateHandler encoder,
    tree_desc near *desc) /* the tree descriptor */
{
    ct_data near *tree	= desc->dyn_tree;
    int near *extra	= desc->extra_bits;
    int base		= desc->extra_base;
    int max_code	= desc->max_code;
    int max_length	= desc->max_length;
    ct_data near *stree = desc->static_tree;
    int h;		/* heap index */
    int n, m;		/* iterate over the tree elements */
    int bits;		/* bit length */
    int xbits;		/* extra bits */
    ush f;		/* frequency */
    int overflow = 0;	/* number of elements with bit length too large */

    for(bits = 0; bits <= MAX_BITS; bits++)
	encoder->bl_count[bits] = 0;

    /* In a first pass, compute the optimal bit lengths (which may
     * overflow in the case of the bit length tree).
     */
    tree[encoder->heap[encoder->heap_max]].Len = 0; /* root of the heap */

    for(h = encoder->heap_max+1; h < HEAP_SIZE; h++) {
	n = encoder->heap[h];
	bits = tree[tree[n].Dad].Len + 1;
	if(bits > max_length)
	    bits = max_length, overflow++;
	tree[n].Len = (ush)bits;
	/* We overwrite tree[n].Dad which is no longer needed */

	if(n > max_code)
	    continue; /* not a leaf node */

	encoder->bl_count[bits]++;
	xbits = 0;
	if(n >= base)
	    xbits = extra[n-base];
	f = tree[n].Freq;
	encoder->opt_len += (ulg)f * (bits + xbits);
	if(stree)
	    encoder->static_len += (ulg)f * (stree[n].Len + xbits);
    }
    if(overflow == 0) return;

    Trace((stderr,"\nbit length overflow\n"));
    /* This happens for example on obj2 and pic of the Calgary corpus */

    /* Find the first bit length which could increase: */
    do {
	bits = max_length-1;
	while(encoder->bl_count[bits] == 0) bits--;
	encoder->bl_count[bits]--;	/* move one leaf down the tree */
	encoder->bl_count[bits+1] += 2; /* move one overflow item as its brother */
	encoder->bl_count[max_length]--;
	/* The brother of the overflow item also moves one step up,
	 * but this does not affect bl_count[max_length]
	 */
	overflow -= 2;
    } while(overflow > 0);

    /* Now recompute all bit lengths, scanning in increasing frequency.
     * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
     * lengths instead of fixing only the wrong ones. This idea is taken
     * from 'ar' written by Haruhiko Okumura.)
     */
    for(bits = max_length; bits != 0; bits--) {
	n = encoder->bl_count[bits];
	while(n != 0) {
	    m = encoder->heap[--h];
	    if(m > max_code) continue;
	    if(tree[m].Len != (unsigned) bits) {
		Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
		encoder->opt_len +=
		    ((long)bits-(long)tree[m].Len)*(long)tree[m].Freq;
		tree[m].Len = (ush)bits;
	    }
	    n--;
	}
    }
}

/* ===========================================================================
 * Generate the codes for a given tree and bit counts (which need not be
 * optimal).
 * IN assertion: the array bl_count contains the bit length statistics for
 * the given tree and the field len is set for all tree elements.
 * OUT assertion: the field code is set for all tree elements of non
 *     zero code length.
 */
local void gen_codes(
    DeflateHandler encoder,
    ct_data near *tree,	/* the tree to decorate */
    int max_code)	/* largest code with non zero frequency */
{
    ush next_code[MAX_BITS+1];	/* next code value for each bit length */
    ush code = 0;		/* running code value */
    int bits;			/* bit index */
    int n;			/* code index */

    /* The distribution counts are first used to generate the code values
     * without bit reversal.
     */
    for(bits = 1; bits <= MAX_BITS; bits++) {
	next_code[bits] = code = (code + encoder->bl_count[bits-1]) << 1;
    }
    /* Check that the bit counts in bl_count are consistent. The last code
     * must be all ones.
     */
    Assert (code + encoder->bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
	    "inconsistent bit counts");
    Tracev((stderr,"\ngen_codes: max_code %d ", max_code));

    for(n = 0;	 n <= max_code; n++) {
	int len = tree[n].Len;
	if(len == 0)
	    continue;
	/* Now reverse the bits */
	tree[n].Code = bi_reverse(next_code[len]++, len);

	Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
	     n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
    }
}

/* ===========================================================================
 * Construct one Huffman tree and assigns the code bit strings and lengths.
 * Update the total bit length for the current block.
 * IN assertion: the field freq is set for all tree elements.
 * OUT assertions: the fields len and code are set to the optimal bit length
 *     and corresponding code. The length opt_len is updated; static_len is
 *     also updated if stree is not null. The field max_code is set.
 */
local void build_tree(
    DeflateHandler encoder,
    tree_desc near *desc) /* the tree descriptor */
{
    ct_data near *tree	= desc->dyn_tree;
    ct_data near *stree	= desc->static_tree;
    int elems		= desc->elems;
    int n, m;		/* iterate over heap elements */
    int max_code = -1;	/* largest code with non zero frequency */
    int node = elems;	/* next internal node of the tree */

    /* Construct the initial heap, with least frequent element in
     * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
     * heap[0] is not used.
     */
    encoder->heap_len = 0;
    encoder->heap_max = HEAP_SIZE;

    for(n = 0; n < elems; n++) {
	if(tree[n].Freq != 0) {
	    encoder->heap[++encoder->heap_len] = max_code = n;
	    encoder->depth[n] = 0;
	} else {
	    tree[n].Len = 0;
	}
    }

    /* The pkzip format requires that at least one distance code exists,
     * and that at least one bit should be sent even if there is only one
     * possible code. So to avoid special checks later on we force at least
     * two codes of non zero frequency.
     */
    while(encoder->heap_len < 2) {
	int new = encoder->heap[++encoder->heap_len] =
	    (max_code < 2 ? ++max_code : 0);
	tree[new].Freq = 1;
	encoder->depth[new] = 0;
	encoder->opt_len--;
	if(stree)
	    encoder->static_len -= stree[new].Len;
	/* new is 0 or 1 so it does not have extra bits */
    }
    desc->max_code = max_code;

    /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
     * establish sub-heaps of increasing lengths:
     */
    for(n = encoder->heap_len/2; n >= 1; n--)
	pqdownheap(encoder, tree, n);

    /* Construct the Huffman tree by repeatedly combining the least two
     * frequent nodes.
     */
    do {
	n = encoder->heap[SMALLEST];
	encoder->heap[SMALLEST] = encoder->heap[encoder->heap_len--];
	pqdownheap(encoder, tree, SMALLEST);

	m = encoder->heap[SMALLEST];  /* m = node of next least frequency */

	/* keep the nodes sorted by frequency */
	encoder->heap[--encoder->heap_max] = n;
	encoder->heap[--encoder->heap_max] = m;

	/* Create a new node father of n and m */
	tree[node].Freq = tree[n].Freq + tree[m].Freq;
	encoder->depth[node] =
	    (uch)(MAX(encoder->depth[n], encoder->depth[m]) + 1);
	tree[n].Dad = tree[m].Dad = (ush)node;

	/* and insert the new node in the heap */
	encoder->heap[SMALLEST] = node++;
	pqdownheap(encoder, tree, SMALLEST);

    } while(encoder->heap_len >= 2);

    encoder->heap[--encoder->heap_max] = encoder->heap[SMALLEST];

    /* At this point, the fields freq and dad are set. We can now
     * generate the bit lengths.
     */
    gen_bitlen(encoder, (tree_desc near *)desc);

    /* The field len is now set, we can generate the bit codes */
    gen_codes (encoder, (ct_data near *)tree, max_code);
}

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