zip.cpp

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

// The lengths of the bit length codes are sent in order of decreasing
// probability, to avoid transmitting the lengths for unused bit length codes.


typedef struct config {
   ush good_length; // reduce lazy search above this match length
   ush max_lazy;    // do not perform lazy search above this match length
   ush nice_length; // quit search above this match length
   ush max_chain;
} config;

// Values for max_lazy_match, good_match, nice_match and max_chain_length,
// depending on the desired pack level (0..9). The values given below have
// been tuned to exclude worst case performance for pathological files.
// Better values may be found for specific files.
//

const config configuration_table[10] = {
//  good lazy nice chain
    {0,    0,  0,    0},  // 0 store only
    {4,    4,  8,    4},  // 1 maximum speed, no lazy matches
    {4,    5, 16,    8},  // 2
    {4,    6, 32,   32},  // 3
    {4,    4, 16,   16},  // 4 lazy matches */
    {8,   16, 32,   32},  // 5
    {8,   16, 128, 128},  // 6
    {8,   32, 128, 256},  // 7
    {32, 128, 258, 1024}, // 8
    {32, 258, 258, 4096}};// 9 maximum compression */

// Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
// For deflate_fast() (levels <= 3) good is ignored and lazy has a different meaning.







// Data structure describing a single value and its code string.
typedef struct ct_data {
    union {
        ush  freq;       // frequency count
        ush  code;       // bit string
    } fc;
    union {
        ush  dad;        // father node in Huffman tree
        ush  len;        // length of bit string
    } dl;
} ct_data;

typedef struct tree_desc {
    ct_data *dyn_tree;      // the dynamic tree
    ct_data *static_tree;   // corresponding static tree or NULL
    const int *extra_bits;  // extra bits for each code or NULL
    int     extra_base;     // base index for extra_bits
    int     elems;          // max number of elements in the tree
    int     max_length;     // max bit length for the codes
    int     max_code;       // largest code with non zero frequency
} tree_desc;




class TTreeState
{ public:
  TTreeState();

  ct_data dyn_ltree[HEAP_SIZE];    // literal and length tree
  ct_data dyn_dtree[2*D_CODES+1];  // distance tree
  ct_data static_ltree[L_CODES+2]; // the static literal tree...
  // ... Since the bit lengths are imposed, there is no need for the L_CODES
  // extra codes used during heap construction. However the codes 286 and 287
  // are needed to build a canonical tree (see ct_init below).
  ct_data static_dtree[D_CODES]; // the static distance tree...
  // ... (Actually a trivial tree since all codes use 5 bits.)
  ct_data bl_tree[2*BL_CODES+1];  // Huffman tree for the bit lengths

  tree_desc l_desc;
  tree_desc d_desc;
  tree_desc bl_desc;

  ush bl_count[MAX_BITS+1];  // number of codes at each bit length for an optimal tree

  int heap[2*L_CODES+1]; // heap used to build the Huffman trees
  int heap_len;               // number of elements in the heap
  int heap_max;               // element of largest frequency
  // The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.
  // The same heap array is used to build all trees.

  uch 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 base_length[LENGTH_CODES];
  // First normalized length for each code (0 = MIN_MATCH)

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

  uch far l_buf[LIT_BUFSIZE];  // buffer for literals/lengths
  ush far d_buf[DIST_BUFSIZE]; // buffer for distances

  uch flag_buf[(LIT_BUFSIZE/8)];
  // flag_buf is a bit array distinguishing literals from lengths in
  // l_buf, and 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
  // bits are filled in flags starting at bit 0 (least significant).
  // Note: these flags are overkill in the current code since we don't
  // take advantage of DIST_BUFSIZE == LIT_BUFSIZE.

  ulg opt_len;          // bit length of current block with optimal trees
  ulg static_len;       // bit length of current block with static trees

  ulg cmpr_bytelen;     // total byte length of compressed file
  ulg cmpr_len_bits;    // number of bits past 'cmpr_bytelen'

  ulg input_len;        // total byte length of input file
  // input_len is for debugging only since we can get it by other means.

  ush *file_type;       // pointer to UNKNOWN, BINARY or ASCII
//  int *file_method;     // pointer to DEFLATE or STORE
};

TTreeState::TTreeState()
{ tree_desc a = {dyn_ltree, static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS, 0};  l_desc = a;
  tree_desc b = {dyn_dtree, static_dtree, extra_dbits, 0,          D_CODES, MAX_BITS, 0};  d_desc = b;
  tree_desc c = {bl_tree, NULL,       extra_blbits, 0,         BL_CODES, MAX_BL_BITS, 0};  bl_desc = c;
  last_lit=0;
  last_dist=0;
  last_flags=0;
}



class TBitState
{ public:

  int flush_flg;
  //
  unsigned bi_buf;
  // Output buffer. bits are inserted starting at the bottom (least significant
  // bits). The width of bi_buf must be at least 16 bits.
  int bi_valid;
  // Number of valid bits in bi_buf.  All bits above the last valid bit
  // are always zero.
  char *out_buf;
  // Current output buffer.
  unsigned out_offset;
  // Current offset in output buffer.
  // On 16 bit machines, the buffer is limited to 64K.
  unsigned out_size;
  // Size of current output buffer
  ulg bits_sent;   // bit length of the compressed data  only needed for debugging???
};







class TDeflateState
{ public:
  TDeflateState() {window_size=0;}

  uch    window[2L*WSIZE];
  // Sliding window. Input bytes are read into the second half of the window,
  // and move to the first half later to keep a dictionary of at least WSIZE
  // bytes. With this organization, matches are limited to a distance of
  // WSIZE-MAX_MATCH bytes, but this ensures that IO is always
  // performed with a length multiple of the block size. Also, it limits
  // the window size to 64K, which is quite useful on MSDOS.
  // To do: limit the window size to WSIZE+CBSZ if SMALL_MEM (the code would
  // be less efficient since the data would have to be copied WSIZE/CBSZ times)
  Pos    prev[WSIZE];
  // Link to older string with same hash index. To limit the size of this
  // array to 64K, this link is maintained only for the last 32K strings.
  // An index in this array is thus a window index modulo 32K.
  Pos    head[HASH_SIZE];
  // Heads of the hash chains or NIL. If your compiler thinks that
  // HASH_SIZE is a dynamic value, recompile with -DDYN_ALLOC.

  ulg window_size;
  // window size, 2*WSIZE except for MMAP or BIG_MEM, where it is the
  // input file length plus MIN_LOOKAHEAD.

  long block_start;
  // window position at the beginning of the current output block. Gets
  // negative when the window is moved backwards.

  int sliding;
  // Set to false when the input file is already in memory

  unsigned ins_h;  // hash index of string to be inserted

  unsigned int prev_length;
  // Length of the best match at previous step. Matches not greater than this
  // are discarded. This is used in the lazy match evaluation.

  unsigned strstart;         // start of string to insert
  unsigned match_start; // start of matching string
  int      eofile;           // flag set at end of input file
  unsigned lookahead;        // number of valid bytes ahead in window

  unsigned max_chain_length;
  // To speed up deflation, hash chains are never searched beyond this length.
  // A higher limit improves compression ratio but degrades the speed.

  unsigned int max_lazy_match;
  // Attempt to find a better match only when the current match is strictly
  // smaller than this value. This mechanism is used only for compression
  // levels >= 4.

  unsigned good_match;
  // Use a faster search when the previous match is longer than this

  int nice_match; // Stop searching when current match exceeds this
};

typedef __int64 lutime_t;       // define it ourselves since we don't include time.h

typedef struct iztimes {
  lutime_t atime,mtime,ctime;
} iztimes; // access, modify, create times

typedef struct zlist {
  ush vem, ver, flg, how;       // See central header in zipfile.c for what vem..off are
  ulg tim, crc, siz, len;
  extent nam, ext, cext, com;   // offset of ext must be >= LOCHEAD
  ush dsk, att, lflg;           // offset of lflg must be >= LOCHEAD
  ulg atx, off;
  char name[MAX_PATH];          // File name in zip file
  char *extra;                  // Extra field (set only if ext != 0)
  char *cextra;                 // Extra in central (set only if cext != 0)
  char *comment;                // Comment (set only if com != 0)
  char iname[MAX_PATH];         // Internal file name after cleanup
  char zname[MAX_PATH];         // External version of internal name
  int mark;                     // Marker for files to operate on
  int trash;                    // Marker for files to delete
  int dosflag;                  // Set to force MSDOS file attributes
  struct zlist far *nxt;        // Pointer to next header in list
} TZipFileInfo;


struct TState;
typedef unsigned (*READFUNC)(TState &state, char *buf,unsigned size);
typedef unsigned (*FLUSHFUNC)(void *param, const char *buf, unsigned *size);
typedef unsigned (*WRITEFUNC)(void *param, const char *buf, unsigned size);
struct TState
{ void *param;
  int level; bool seekable;
  READFUNC readfunc; FLUSHFUNC flush_outbuf;
  TTreeState ts; TBitState bs; TDeflateState ds;
  const char *err;
};









void Assert(TState &state,bool cond, const char *msg)
{ if (cond) return;
  state.err=msg;
}
void __cdecl Trace(const char *x, ...) {va_list paramList; va_start(paramList, x); paramList; va_end(paramList);}
void __cdecl Tracec(bool ,const char *x, ...) {va_list paramList; va_start(paramList, x); paramList; va_end(paramList);}



// ===========================================================================
// Local (static) routines in this file.
//

void init_block     (TState &);
void pqdownheap     (TState &,ct_data *tree, int k);
void gen_bitlen     (TState &,tree_desc *desc);
void gen_codes      (TState &state,ct_data *tree, int max_code);
void build_tree     (TState &,tree_desc *desc);
void scan_tree      (TState &,ct_data *tree, int max_code);
void send_tree      (TState &state,ct_data *tree, int max_code);
int  build_bl_tree  (TState &);
void send_all_trees (TState &state,int lcodes, int dcodes, int blcodes);
void compress_block (TState &state,ct_data *ltree, ct_data *dtree);
void set_file_type  (TState &);
void send_bits      (TState &state, int value, int length);
unsigned bi_reverse (unsigned code, int len);
void bi_windup      (TState &state);
void copy_block     (TState &state,char *buf, unsigned len, int header);


#define send_code(state, c, tree) send_bits(state, tree[c].fc.code, tree[c].dl.len)
// Send a code of the given tree. c and tree must not have side effects

// alternatively...
//#define send_code(state, c, tree)
//     { if (state.verbose>1) fprintf(stderr,"\ncd %3d ",(c));
//       send_bits(state, tree[c].fc.code, tree[c].dl.len); }

#define d_code(dist) ((dist) < 256 ? state.ts.dist_code[dist] : state.ts.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.

#define Max(a,b) (a >= b ? a : b)
/* the arguments must not have side effects */

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