xzip.cpp

存C写的zip压缩、解压缩源代码。主要对文件操作

    //    Assert(state,buf!=NULL,"block vanished");
    //    copy_block(state,buf, (unsigned)stored_len, 0); // without header
    //    state.ts.cmpr_bytelen = stored_len;
    //    Assert(state,false,"unimplemented *state.ts.file_method = STORE;");
    //    //*state.ts.file_method = STORE;
    //}
    //else
    if (stored_len+4 <= opt_lenb && buf != (char*)NULL) {
                       /* 4: two words for the lengths */
        /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
         * Otherwise we can't have processed more than WSIZE input bytes since
         * the last block flush, because compression would have been
         * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
         * transform a block into a stored block.
         */
        send_bits(state,(STORED_BLOCK<<1)+eof, 3);  /* send block type */
        state.ts.cmpr_bytelen += ((state.ts.cmpr_len_bits + 3 + 7) >> 3) + stored_len + 4;
        state.ts.cmpr_len_bits = 0L;

        copy_block(state,buf, (unsigned)stored_len, 1); /* with header */
    }
    else if (static_lenb == opt_lenb) {
        send_bits(state,(STATIC_TREES<<1)+eof, 3);
        compress_block(state,(ct_data *)state.ts.static_ltree, (ct_data *)state.ts.static_dtree);
        state.ts.cmpr_len_bits += 3 + state.ts.static_len;
        state.ts.cmpr_bytelen += state.ts.cmpr_len_bits >> 3;
        state.ts.cmpr_len_bits &= 7L;
    }
    else {
        send_bits(state,(DYN_TREES<<1)+eof, 3);
        send_all_trees(state,state.ts.l_desc.max_code+1, state.ts.d_desc.max_code+1, max_blindex+1);
        compress_block(state,(ct_data *)state.ts.dyn_ltree, (ct_data *)state.ts.dyn_dtree);
        state.ts.cmpr_len_bits += 3 + state.ts.opt_len;
        state.ts.cmpr_bytelen += state.ts.cmpr_len_bits >> 3;
        state.ts.cmpr_len_bits &= 7L;
    }
    Assert(state,((state.ts.cmpr_bytelen << 3) + state.ts.cmpr_len_bits) == state.bs.bits_sent, "bad compressed size");
    init_block(state);

    if (eof) {
        // Assert(state,input_len == isize, "bad input size");
        bi_windup(state);
        state.ts.cmpr_len_bits += 7;  /* align on byte boundary */
    }
    Trace("\n");

    return state.ts.cmpr_bytelen + (state.ts.cmpr_len_bits >> 3);
}

/* ===========================================================================
 * Save the match info and tally the frequency counts. Return true if
 * the current block must be flushed.
 */
int ct_tally (TState &state,int dist, int lc)
{
    state.ts.l_buf[state.ts.last_lit++] = (uch)lc;
    if (dist == 0) {
        /* lc is the unmatched char */
        state.ts.dyn_ltree[lc].fc.freq++;
    } else {
        /* Here, lc is the match length - MIN_MATCH */
        dist--;             /* dist = match distance - 1 */
        Assert(state,(ush)dist < (ush)MAX_DIST &&
               (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
               (ush)d_code(dist) < (ush)D_CODES,  "ct_tally: bad match");

        state.ts.dyn_ltree[state.ts.length_code[lc]+LITERALS+1].fc.freq++;
        state.ts.dyn_dtree[d_code(dist)].fc.freq++;

        state.ts.d_buf[state.ts.last_dist++] = (ush)dist;
        state.ts.flags |= state.ts.flag_bit;
    }
    state.ts.flag_bit <<= 1;

    /* Output the flags if they fill a byte: */
    if ((state.ts.last_lit & 7) == 0) {
        state.ts.flag_buf[state.ts.last_flags++] = state.ts.flags;
        state.ts.flags = 0, state.ts.flag_bit = 1;
    }
    /* Try to guess if it is profitable to stop the current block here */
    if (state.level > 2 && (state.ts.last_lit & 0xfff) == 0) {
        /* Compute an upper bound for the compressed length */
        ulg out_length = (ulg)state.ts.last_lit*8L;
        ulg in_length = (ulg)state.ds.strstart-state.ds.block_start;
        int dcode;
        for (dcode = 0; dcode < D_CODES; dcode++) {
            out_length += (ulg)state.ts.dyn_dtree[dcode].fc.freq*(5L+extra_dbits[dcode]);
        }
        out_length >>= 3;
        Trace("\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ",
               state.ts.last_lit, state.ts.last_dist, in_length, out_length,
               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.
     */
    stat