zip.cpp

这是CODEPROJECT上的zip压缩解压代码

               100L - out_length*100L/in_length);
        if (state.ts.last_dist < state.ts.last_lit/2 && out_length < in_length/2) return 1;
    }
    return (state.ts.last_lit == LIT_BUFSIZE-1 || state.ts.last_dist == DIST_BUFSIZE);
    /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K
     * on 16 bit machines and because stored blocks are restricted to
     * 64K-1 bytes.
     */
}

/* ===========================================================================
 * Send the block data compressed using the given Huffman trees
 */
void compress_block(TState &state,ct_data *ltree, ct_data *dtree)
{
    unsigned dist;      /* distance of matched string */
    int lc;             /* match length or unmatched char (if dist == 0) */
    unsigned lx = 0;    /* running index in l_buf */
    unsigned dx = 0;    /* running index in d_buf */
    unsigned fx = 0;    /* running index in flag_buf */
    uch flag = 0;       /* current flags */
    unsigned code;      /* the code to send */
    int extra;          /* number of extra bits to send */

    if (state.ts.last_lit != 0) do {
        if ((lx & 7) == 0) flag = state.ts.flag_buf[fx++];
        lc = state.ts.l_buf[lx++];
        if ((flag & 1) == 0) {
            send_code(state,lc, ltree); /* send a literal byte */
        } else {
            /* Here, lc is the match length - MIN_MATCH */
            code = state.ts.length_code[lc];
            send_code(state,code+LITERALS+1, ltree); /* send the length code */
            extra = extra_lbits[code];
            if (extra != 0) {
                lc -= state.ts.base_length[code];
                send_bits(state,lc, extra);        /* send the extra length bits */
            }
            dist = state.ts.d_buf[dx++];
            /* Here, dist is the match distance - 1 */
            code = d_code(dist);
            Assert(state,code < D_CODES, "bad d_code");

            send_code(state,code, dtree);       /* send the distance code */
            extra = extra_dbits[code];
            if (extra != 0) {
                dist -= state.ts.base_dist[code];
                send_bits(state,dist, extra);   /* send the extra distance bits */
            }
        } /* literal or match pair ? */
        flag >>= 1;
    } while (lx < state.ts.last_lit);

    send_code(state,END_BLOCK, ltree);
}

/* ===========================================================================
 * Set the file type to ASCII or BINARY, using a crude approximation:
 * binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
 * IN assertion: the fields freq of dyn_ltree are set and the total of all
 * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
 */
void set_file_type(TState &state)
{
    int n = 0;
    unsigned ascii_freq = 0;
    unsigned bin_freq = 0;
    while (n < 7)        bin_freq += state.ts.dyn_ltree[n++].fc.freq;
    while (n < 128)    ascii_freq += state.ts.dyn_ltree[n++].fc.freq;
    while (n < LITERALS) bin_freq += state.ts.dyn_ltree[n++].fc.freq;
    *state.ts.file_type = (ush)(bin_freq > (ascii_freq >> 2) ? BINARY : ASCII);
}


/* ===========================================================================
 * Initialize the bit string routines.
 */
void bi_init (TState &state,char *tgt_buf, unsigned tgt_size, int flsh_allowed)
{
    state.bs.out_buf = tgt_buf;
    state.bs.out_size = tgt_size;
    state.bs.out_offset = 0;
    state.bs.flush_flg = flsh_allowed;

    state.bs.bi_buf = 0;
    state.bs.bi_valid = 0;
    state.bs.bits_sent = 0L;
}

/* ===========================================================================
 * Send a value on a given number of bits.
 * IN assertion: length <= 16 and value fits in length bits.
 */
void send_bits(TState &state,int value, int length)
{
    Assert(state,length > 0 && length <= 15, "invalid length");
    state.bs.bits_sent += (ulg)length;
    /* If not enough room in bi_buf, use (bi_valid) bits from bi_buf and
     * (Buf_size - bi_valid) bits from value to flush the filled bi_buf,
     * then fill in the rest of (value), leaving (length - (Buf_size-bi_valid))
     * unused bits in bi_buf.
     */
    state.bs.bi_buf |= (value << state.bs.bi_valid);
    state.bs.bi_valid += length;
    if (state.bs.bi_valid > (int)Buf_size) {
        PUTSHORT(state,state.bs.bi_buf);
        state.bs.bi_valid -= Buf_size;
        state.bs.bi_buf = (unsigned)value >> (length - state.bs.bi_valid);
    }
}

/* ===========================================================================
 * Reverse the first len bits of a code, using straightforward code (a faster
 * method would use a table)
 * IN assertion: 1 <= len <= 15
 */
unsigned bi_reverse(unsigned code, int len)
{
    register unsigned res = 0;
    do {
        res |= code & 1;
        code >>= 1, res <<= 1;
    } while (--len > 0);
    return res >> 1;
}

/* ===========================================================================
 * Write out any remaining bits in an incomplete byte.
 */
void bi_windup(TState &state)
{
    if (state.bs.bi_valid > 8) {
        PUTSHORT(state,state.bs.bi_buf);
    } else if (state.bs.bi_valid > 0) {
        PUTBYTE(state,state.bs.bi_buf);
    }
    if (state.bs.flush_flg) {
        state.flush_outbuf(state.param,state.bs.out_buf, &state.bs.out_offset);
    }
    state.bs.bi_buf = 0;
    state.bs.bi_valid = 0;
    state.bs.bits_sent = (state.bs.bits_sent+7) & ~7;
}

/* ===========================================================================
 * Copy a stored block to the zip file, storing first the length and its
 * one's complement if requested.
 */
void copy_block(TState &state, char *block, unsigned len, int header)
{
    bi_windup(state);              /* align on byte boundary */

    if (header) {
        PUTSHORT(state,(ush)len);
        PUTSHORT(state,(ush)~len);
        state.bs.bits_sent += 2*16;
    }
    if (state.bs.flush_flg) {
        state.flush_outbuf(state.param,state.bs.out_buf, &state.bs.out_offset);
        state.bs.out_offset = len;
        state.flush_outbuf(state.param,block, &state.bs.out_offset);
    } else if (state.bs.out_offset + len > state.bs.out_size) {
        Assert(state,false,"output buffer too small for in-memory compression");
    } else {
        memcpy(state.bs.out_buf + state.bs.out_offset, block, len);
        state.bs.out_offset += len;
    }
    state.bs.bits_sent += (ulg)len<<3;
}








/* ===========================================================================
 *  Prototypes for functions.
 */

void fill_window  (TState &state);
ulg deflate_fast  (TState &state);

int  longest_match (TState &state,IPos cur_match);


/* ===========================================================================
 * 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(state.ds.ins_h, state.ds.window[(s) + (MIN_MATCH-1)]), \
    state.ds.prev[(s) & WMASK] = match_head = state.ds.head[state.ds.ins_h], \
    state.ds.head[state.ds.ins_h] = (s))

/* ===========================================================================
 * Initialize the "longest match" routines for a new file
 *
 * IN assertion: window_size is > 0 if the input file is already read or
 *    mmap'ed in the window[] array, 0 otherwise. In the first case,
 *    window_size is sufficient to contain the whole input file plus
 *    MIN_LOOKAHEAD bytes (to avoid referencing memory beyond the end
 *    of window[] when looking for matches towards the end).
 */
void lm_init (TState &state, int pack_level, ush *flags)
{
    register unsigned j;

    Assert(state,pack_level>=1 && pack_level<=8,"bad pack level");

    /* Do not slide the window if the whole input is already in memory
     * (window_size > 0)
     */
    state.ds.sliding = 0;
    if (state.ds.window_size == 0L) {
        state.ds.sliding = 1;
        state.ds.window_size = (ulg)2L*WSIZE;
    }

    /* Initialize the hash table (avoiding 64K overflow for 16 bit systems).
     * prev[] will be initialized on the fly.
     */
    state.ds.head[HASH_SIZE-1] = NIL;
    memset((char*)state.ds.head, NIL, (unsigned)(HASH_SIZE-1)*sizeof(*state.ds.head));

    /* Set the default configuration parameters:
     */
    state.ds.max_lazy_match   = configuration_table[pack_level].max_lazy;
    state.ds.good_match       = configuration_table[pack_level].good_length;
    state.ds.nice_match       = configuration_table[pack_level].nice_length;
    state.ds.max_chain_length = configuration_table[pack_level].max_chain;
    if (pack_level <= 2) {
       *flags |= FAST;
    } else if (pack_level >= 8) {
       *flags |= SLOW;
    }
    /* ??? reduce max_chain_length for binary files */

    state.ds.strstart = 0;
    state.ds.block_start = 0L;

    j = WSIZE;
    j <<= 1; // Can read 64K in one step
    state.ds.lookahead = state.readfunc(state, (char*)state.ds.window, j);

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

    state.ds.ins_h = 0;
    for (j=0; j<MIN_MATCH-1; j++) UPDATE_HASH(state.ds.ins_h, state.ds.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
 */
// For 80x86 and 680x0 and ARM, an optimized version is in match.asm or
// match.S. The code is functionally equivalent, so you can use the C version
// if desired. Which I do so desire!
int longest_match(TState &state,IPos cur_match)
{
    unsigned chain_length = state.ds.max_chain_length;   /* max hash chain length */
    register uch far *scan = state.ds.window + state.ds.strstart; /* current string */
    register uch far *match;                    /* matched string */
    register int len;                           /* length of current match */
    int best_len = state.ds.prev_length;                 /* best match length so far */
    IPos limit = state.ds.strstart > (IPos)MAX_DIST ? state.ds.strstart - (IPos)MAX_DIST : NIL;
    /* Stop when cur_match becomes <= limit. To simplify the code,
     * we prevent matches with the string of window index 0.
     */

  // The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
  // It is easy to get rid of this optimization if necessary.
    Assert(state,HASH_BITS>=8 && MAX_MATCH==258,"Code too clever");



    register uch far *strend = state.ds.window + state.ds.strstart + MAX_MATCH;
    register uch scan_end1  = scan[best_len-1];
    register uch scan_end   = scan[best_len];

    /* Do not waste too much time if we already have a good match: */
    if (state.ds.prev_length >= state.ds.good_match) {
        chain_length >>= 2;
    }

    Assert(state,state.ds.strstart <= state.ds.window_size-MIN_LOOKAHEAD, "insufficient lookahead");

    do {
        Assert(state,cur_match < state.ds.strstart, "no future");
        match = state.ds.window + cur_match;