deflate.c

MIDI解码程序(用VC编写)

 * The same heap array is used to build all trees.
 */

    uch near depth[2*L_CODES+1];
/* Depth of each subtree used as tie breaker for trees of equal frequency */

    uch length_code[MAX_MATCH-MIN_MATCH+1];
/* length code for each normalized match length (0 == MIN_MATCH) */

    uch dist_code[512];
/* distance codes. The first 256 values correspond to the distances
 * 3 .. 258, the last 256 values correspond to the top 8 bits of
 * the 15 bit distances.
 */

    int near base_length[LENGTH_CODES];
/* First normalized length for each code (0 = MIN_MATCH) */

    int near base_dist[D_CODES];
/* First normalized distance for each code (0 = distance of 1) */

    uch near flag_buf[(LIT_BUFSIZE/8)];
/* flag_buf is a bit array distinguishing literals from lengths in
 * l_buf, thus indicating the presence or absence of a distance.
 */

    unsigned last_lit;	/* running index in l_buf */
    unsigned last_dist;	/* running index in d_buf */
    unsigned last_flags;/* running index in flag_buf */
    uch flags;		/* current flags not yet saved in flag_buf */
    uch flag_bit;	/* current bit used in flags */
    ulg opt_len;	/* bit length of current block with optimal trees */
    ulg static_len;	/* bit length of current block with static trees */
};

local void lm_init(DeflateHandler);
local int  longest_match(DeflateHandler,unsigned cur_match);
local void fill_window(DeflateHandler);
local void deflate_fast(DeflateHandler);
local void deflate_better(DeflateHandler);
local long qcopy(DeflateHandler encoder, char *buff, long buff_size);
local void ct_init(DeflateHandler);
local void init_block(DeflateHandler);
local void pqdownheap(DeflateHandler,ct_data near *, int);
local void gen_bitlen(DeflateHandler,tree_desc near *);
local void gen_codes(DeflateHandler,ct_data near *, int);
local void build_tree(DeflateHandler,tree_desc near *);
local void scan_tree(DeflateHandler,ct_data near *, int);
local void send_tree(DeflateHandler,ct_data near *, int);
local int  build_bl_tree(DeflateHandler);
local void send_all_trees(DeflateHandler,int,int,int);
local void flush_block(DeflateHandler,int);
local int  ct_tally(DeflateHandler,int,int);
local void compress_block(DeflateHandler,ct_data near *, ct_data near *);
local void send_bits(DeflateHandler,int,int);
local unsigned bi_reverse(unsigned, int);
local void bi_windup(DeflateHandler);
local void qoutbuf(DeflateHandler);

#ifdef DEBUG
local void error(char *m)
{
    fprintf(stderr, "%s\n", m);
    exit(1);
}
#define Assert(cond,msg) {if(!(cond)) error(msg);}
local int verbose = 0;		/* verbose */
local void check_match (DeflateHandler,unsigned, unsigned, int);
#else
#define Assert(cond,msg)
#endif

#ifndef MAX
#define MAX(a,b) (a >= b ? a : b)
#endif /* MAX */

#define head(i) ((encoder->prev+WSIZE)[i])

/* put_byte is used for the compressed output, put_ubyte for the
 * uncompressed output. However unlzw() uses window for its
 * suffix table instead of its output buffer, so it does not use put_ubyte
 * (to be cleaned up).
 */
#define put_byte(c) {encoder->outbuf[encoder->outoff + encoder->outcnt++] = \
  (uch)(c); if(encoder->outoff + encoder->outcnt == OUTBUFSIZ) \
  qoutbuf(encoder);}

/* Output a 16 bit value, lsb first */
#define put_short(w) \
{ if(encoder->outoff + encoder->outcnt < OUTBUFSIZ - 2) { \
    encoder->outbuf[encoder->outoff+encoder->outcnt++] = (uch) ((w) & 0xff); \
    encoder->outbuf[encoder->outoff+encoder->outcnt++] = (uch) ((ush)(w) >> 8); \
  } else { put_byte((uch)((w) & 0xff));	 put_byte((uch)((ush)(w) >> 8)); }}
/* ===========================================================================
 * Update a hash value with the given input byte
 * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
 *    input characters, so that a running hash key can be computed from the
 *    previous key instead of complete recalculation each time.
 */
#define UPDATE_HASH(h,c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)

/* ===========================================================================
 * Insert string s in the dictionary and set match_head to the previous head
 * of the hash chain (the most recent string with same hash key). Return
 * the previous length of the hash chain.
 * IN  assertion: all calls to to INSERT_STRING are made with consecutive
 *    input characters and the first MIN_MATCH bytes of s are valid
 *    (except for the last MIN_MATCH-1 bytes of the input file).
 */
#define INSERT_STRING(s, match_head) \
   (UPDATE_HASH(encoder->ins_h, encoder->window[(s) + MIN_MATCH-1]), \
    encoder->prev[(s) & WMASK] =match_head = head(encoder->ins_h), \
    head(encoder->ins_h) = (s))

#define SEND_CODE(c, tree) send_bits(encoder, (tree)[c].Code, (tree)[c].Len)
/* Send a code of the given tree. c and tree must not have side effects */

#define D_CODE(dist) ((dist)<256 ? encoder->dist_code[dist] : encoder->dist_code[256+((dist)>>7)])
/* Mapping from a distance to a distance code. dist is the distance - 1 and
 * must not have side effects. dist_code[256] and dist_code[257] are never
 * used.
 */

/* ===========================================================================
 * Compares to subtrees, using the tree depth as tie breaker when
 * the subtrees have equal frequency. This minimizes the worst case length.
 */
#define SMALLER(tree, n, m) \
   ((tree)[n].Freq < (tree)[m].Freq || \
   ((tree)[n].Freq == (tree)[m].Freq && encoder->depth[n] <= encoder->depth[m]))


/* ===========================================================================
 * Initialize the "longest match" routines for a new file
 */
local void lm_init(DeflateHandler encoder)
{
    register unsigned j;

    /* Initialize the hash table. */
#if defined(MAXSEG_64K) && HASH_BITS == 15
    for(j = 0; j < HASH_SIZE; j++) head(j) = NIL;
#else
    memset((char*)&head(0), 0, HASH_SIZE*sizeof(head(0)));
#endif
    /* prev will be initialized on the fly */

    /* Set the default configuration parameters:
     */
    encoder->max_lazy_match   = configuration_table[encoder->compr_level].max_lazy;
    encoder->good_match	      = configuration_table[encoder->compr_level].good_length;
#ifndef FULL_SEARCH
    encoder->nice_match	      = configuration_table[encoder->compr_level].nice_length;
#endif
    encoder->max_chain_length = configuration_table[encoder->compr_level].max_chain;

    encoder->strstart = 0;
    encoder->block_start = 0L;

    encoder->lookahead =
	encoder->read_func((char*)encoder->window,
			   (long)(sizeof(int)<=2 ? (unsigned)WSIZE : 2*WSIZE),
			   encoder->user_val);

    if(encoder->lookahead == 0 || encoder->lookahead == (unsigned)EOF) {
	encoder->eofile = 1;
	encoder->lookahead = 0;
	return;
    }
    encoder->eofile = 0;
    /* Make sure that we always have enough lookahead. This is important
     * if input comes from a device such as a tty.
     */
    while(encoder->lookahead < MIN_LOOKAHEAD && !encoder->eofile)
	fill_window(encoder);

    encoder->ins_h = 0;
    for(j=0; j<MIN_MATCH-1; j++)
	UPDATE_HASH(encoder->ins_h, encoder->window[j]);
    /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
     * not important since only literal bytes will be emitted.
     */
}

/* ===========================================================================
 * Set match_start to the longest match starting at the given string and
 * return its length. Matches shorter or equal to prev_length are discarded,
 * in which case the result is equal to prev_length and match_start is
 * garbage.
 * IN assertions: cur_match is the head of the hash chain for the current
 *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
 */
local int longest_match(DeflateHandler encoder, unsigned cur_match)
{
    unsigned chain_length = encoder->max_chain_length;
    /* max hash chain length */

    register uch *scan = encoder->window + encoder->strstart;
    /* current string */

    register uch *match;			/* matched string */
    register int len;				/* length of current match */
    int best_len = encoder->prev_length;	 /* best match length so far */

    unsigned limit = (encoder->strstart > (unsigned)MAX_DIST ?
		      encoder->strstart - (unsigned)MAX_DIST : NIL);
    /* Stop when cur_match becomes <= limit. To simplify the code,
     * we prevent matches with the string of window index 0.
     */

#if HASH_BITS < 8 || MAX_MATCH != 258
   error: Code too clever
#endif

#ifdef UNALIGNED_OK
    /* Compare two bytes at a time. Note: this is not always beneficial.
     * Try with and without -DUNALIGNED_OK to check.
     */
    register uch *strend = encoder->window + encoder->strstart + MAX_MATCH - 1;
    register ush scan_start = *(ush*)scan;
    register ush scan_end   = *(ush*)(scan+best_len-1);
#else
    register uch *strend    = encoder->window + encoder->strstart + MAX_MATCH;
    register uch scan_end1  = scan[best_len-1];
    register uch scan_end   = scan[best_len];
#endif

    /* Do not waste too much time if we already have a good match: */
    if(encoder->prev_length >= encoder->good_match) {
	chain_length >>= 2;
    }
    Assert(encoder->strstart <= window_size-MIN_LOOKAHEAD, "insufficient lookahead");

    do {
	Assert(cur_match < encoder->strstart, "no future");
	match = encoder->window + cur_match;

	/* Skip to next match if the match length cannot increase
	 * or if the match length is less than 2:
	 */
#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
	/* This code assumes sizeof(unsigned short) == 2. Do not use
	 * UNALIGNED_OK if your compiler uses a different size.
	 */
	if(*(ush*)(match+best_len-1) != scan_end ||
	   *(ush*)match != scan_start) continue;

	/* It is not necessary to compare scan[2] and match[2] since they are
	 * always equal when the other bytes match, given that the hash keys
	 * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
	 * strstart+3, +5, ... up to strstart+257. We check for insufficient
	 * lookahead only every 4th comparison; the 128th check will be made
	 * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
	 * necessary to put more guard bytes at the end of the window, or
	 * to check more often for insufficient lookahead.
	 */
	scan++, match++;
	do {
	} while(*(ush*)(scan+=2) == *(ush*)(match+=2) &&
		*(ush*)(scan+=2) == *(ush*)(match+=2) &&
		*(ush*)(scan+=2) == *(ush*)(match+=2) &&
		*(ush*)(scan+=2) == *(ush*)(match+=2) &&
		scan < strend);
	/* The funny "do {}" generates better code on most compilers */

	/* Here, scan <= window+strstart+257 */
	Assert(scan <= encoder->window+(unsigned)(window_size-1), "wild scan");
	if(*scan == *match) scan++;

	len = (MAX_MATCH - 1) - (int)(strend-scan);
	scan = strend - (MAX_MATCH-1);

#else /* UNALIGNED_OK */

	if(match[best_len]   != scan_end  ||
	   match[best_len-1] != scan_end1 ||
	   *match	      != *scan	   ||
	   *++match	      != scan[1])      continue;

	/* The check at best_len-1 can be removed because it will be made
	 * again later. (This heuristic is not always a win.)
	 * It is not necessary to compare scan[2] and match[2] since they
	 * are always equal when the other bytes match, given that
	 * the hash keys are equal and that HASH_BITS >= 8.
	 */
	scan += 2, match++;

	/* We check for insufficient lookahead only every 8th comparison;
	 * the 256th check will be made at strstart+258.
	 */
	do {
	} while(*++scan == *++match && *++scan == *++match &&
		*++scan == *++match && *++scan == *++match &&
		*++scan == *++match && *++scan == *++match &&
		*++scan == *++match && *++scan == *++match &&
		scan < strend);

	len = MAX_MATCH - (int)(strend - scan);
	scan = strend - MAX_MATCH;

#endif /* UNALIGNED_OK */

	if(len > best_len) {
	    encoder->match_start = cur_match;
	    best_len = len;
#ifdef FULL_SEARCH
	    if(len >= MAX_MATCH) break;
#else
	    if(len >= encoder->nice_match) break;
#endif /* FULL_SEARCH */


#ifdef UNALIGNED_OK
	    scan_end = *(ush*)(scan+best_len-1);
#else
	    scan_end1  = scan[best_len-1];
	    scan_end   = scan[best_len];
#endif
	}
    } while((cur_match = encoder->prev[cur_match & WMASK]) > limit
	    && --chain_length != 0);

    return best_len;
}

#ifdef DEBUG
/* ===========================================================================
 * Check that the match at match_start is indeed a match.
 */
local void check_match(DeflateHandler encoder,
		       unsigned start, unsigned match, int length)
{
    /* check that the match is indeed a match */
    if(memcmp((char*)encoder->window + match,
	      (char*)encoder->window + start, length) != EQUAL) {
	fprintf(stderr,
	    " start %d, match %d, length %d\n",
	    start, match, length);
	error("invalid match");
    }
    if(verbose > 1) {
	fprintf(stderr,"\\[%d,%d]", start-match, length);
	do { putc(encoder->window[start++], stderr); } while(--length != 0);
    }
}
#else
#  define check_match(encoder, start, match, length)
#endif

/* ===========================================================================
 * Fill the window when the lookahead becomes insufficient.
 * Updates strstart and lookahead, and sets eofile if end of input file.
 * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0
 * OUT assertions: at least one byte has been read, or eofile is set;
 *    file reads are performed for at least two bytes (required for the
 *    translate_eol option).
 */
local void fill_window(DeflateHandler encoder)
{
    register unsigned n, m;
    unsigned more = (unsigned)(window_size - (ulg)encoder->lookahead - (ulg)encoder->strstart);
    /* Amount of free space at the end of the window. */

    /* If the window is almost full and there is insufficient lookahead,
     * move the upper half to the lower one to make room in the upper half.
     */
    if(more == (unsigned)EOF) {
	/* Very unlikely, but possible on 16 bit machine if strstart == 0
	 * and lookahead == 1 (input done one byte at time)
	 */
	more--;
    } else if(encoder->strstart >= WSIZE+MAX_DIST) {
	/* By the IN assertion, the window is not empty so we can't confuse
	 * more == 0 with more == 64K on a 16 bit machine.
	 */